From patchwork Mon Sep 10 14:40:07 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Schmidt X-Patchwork-Id: 182899 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 6E7AB2C0086 for ; Tue, 11 Sep 2012 00:41:36 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1347892897; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Received:Subject:From:To:Cc: Content-Type:Date:Message-ID:Mime-Version: Content-Transfer-Encoding:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=zS/d9/DEsLQT8g/zDLupbBwLR2A=; b=B6tbwzyIEUNAjJ0 akzvaX1bVaXtVsAivfDHwp33omsn+sL7IJnNcLy3QHebUW+BbRI4Yfl0i99oG7Fs XrY2gNJDA+vTvhWNNsSj+n7BAFKq2RkZl/WiQePsb3r3ZplrShnToTfcDyIORFMv 8NJ316s708Vz30PHWErxbZmBIsfw= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Received:Received:Received:Subject:From:To:Cc:Content-Type:Date:Message-ID:Mime-Version:Content-Transfer-Encoding:X-Content-Scanned:x-cbid:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=J3x+lE8EVOosZ8TCKO9xwUOLJgBpNiMIGqZ4a2p38I24Z5WUnWxZQj/8yAOBe+ O9EtWWwxKO/xQFnwwJlX46R6pWhrrGmNG+mnXrDLSYvbV35mdhwOqQKrPJ6ktDRu y6/q8qmzZE3B45s5SjRQhEJ4qiBcN4Q73hSsA0oEJIaYM=; Received: (qmail 8543 invoked by alias); 10 Sep 2012 14:41:28 -0000 Received: (qmail 8527 invoked by uid 22791); 10 Sep 2012 14:41:26 -0000 X-SWARE-Spam-Status: No, hits=-4.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, MAY_BE_FORGED, RCVD_IN_DNSWL_HI, RCVD_IN_HOSTKARMA_W, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from e9.ny.us.ibm.com (HELO e9.ny.us.ibm.com) (32.97.182.139) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 10 Sep 2012 14:41:12 +0000 Received: from /spool/local by e9.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Mon, 10 Sep 2012 10:41:08 -0400 Received: from d01dlp01.pok.ibm.com (9.56.250.166) by e9.ny.us.ibm.com (192.168.1.109) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Mon, 10 Sep 2012 10:40:51 -0400 Received: from d01relay03.pok.ibm.com (d01relay03.pok.ibm.com [9.56.227.235]) by d01dlp01.pok.ibm.com (Postfix) with ESMTP id 37D7E38C80B3 for ; Mon, 10 Sep 2012 10:40:40 -0400 (EDT) Received: from d03av04.boulder.ibm.com (d03av04.boulder.ibm.com [9.17.195.170]) by d01relay03.pok.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id q8AEedjh132572 for ; Mon, 10 Sep 2012 10:40:39 -0400 Received: from d03av04.boulder.ibm.com (loopback [127.0.0.1]) by d03av04.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id q8AEe8LV016264 for ; Mon, 10 Sep 2012 08:40:08 -0600 Received: from [9.10.86.196] (gressett-6474cv1-r8dvc59.rchland.ibm.com [9.10.86.196] (may be forged)) by d03av04.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id q8AEe8jP016165; Mon, 10 Sep 2012 08:40:08 -0600 Subject: [PATCH] Fix PR54492 From: "William J. Schmidt" To: gcc-patches@gcc.gnu.org Cc: bergner@vnet.ibm.com, rguenther@suse.de Date: Mon, 10 Sep 2012 09:40:07 -0500 Message-ID: <1347288007.4740.4.camel@oc2474580526.ibm.com> Mime-Version: 1.0 X-Content-Scanned: Fidelis XPS MAILER x-cbid: 12091014-7182-0000-0000-0000028DE207 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Richard found some N^2 behavior in SLSR that has to be suppressed. Searching for the best possible basis is overkill when there are hundreds of thousands of possibilities. This patch constrains the search to "good enough" in such cases. Bootstrapped and tested on powerpc64-unknown-linux-gnu with no regressions. Ok for trunk? Thanks, Bill 2012-08-10 Bill Schmidt * gimple-ssa-strength-reduction.c (find_basis_for_candidate): Limit the time spent searching for a basis. Index: gcc/gimple-ssa-strength-reduction.c =================================================================== --- gcc/gimple-ssa-strength-reduction.c (revision 191135) +++ gcc/gimple-ssa-strength-reduction.c (working copy) @@ -353,10 +353,14 @@ find_basis_for_candidate (slsr_cand_t c) cand_chain_t chain; slsr_cand_t basis = NULL; + // Limit potential of N^2 behavior for long candidate chains. + int iters = 0; + const int MAX_ITERS = 50; + mapping_key.base_expr = c->base_expr; chain = (cand_chain_t) htab_find (base_cand_map, &mapping_key); - for (; chain; chain = chain->next) + for (; chain && iters < MAX_ITERS; chain = chain->next, ++iters) { slsr_cand_t one_basis = chain->cand;