From patchwork Tue May 7 13:22:40 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Schmidt X-Patchwork-Id: 242199 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]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id C710D2C0150 for ; Tue, 7 May 2013 23:24:09 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:from:to:cc:content-type:date:message-id:mime-version :content-transfer-encoding; q=dns; s=default; b=GuYrtojvBKLO3+r9 NsdIIWgfKcsVSwgc10HAjQPDKQzeyJ6K2Qvz6slvOikbzI+0Km/em7my/bbkTZxJ jKv8de7LYO93nermZCHHDLrzKvbbl6ehomMO8QXOhz3BDl9gxLXH0DNxFnFcsHm0 gByvmrk23DVW8ScwvM4P8fzprTg= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:from:to:cc:content-type:date:message-id:mime-version :content-transfer-encoding; s=default; bh=USX7MXxclrq0+h+p/vsW21 Z6FIk=; b=RdwA72Dg/rwDqdJxBHK+Tt7cBWgj/S0aqYJ6NUceb88V73Fy0zygB7 vJkK2LPpfAfrHCAuVpCdXyHfO4lXX4zMnTkOfACz5iZeD+DKFnMrcNURlF6cDQ1s 88y+pIJ5umbGR2U1oKrPqBlQGKKZhzurfX9DlWMUD0N8MbYxi8TTQ= Received: (qmail 21482 invoked by alias); 7 May 2013 13:24:02 -0000 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 Received: (qmail 21467 invoked by uid 89); 7 May 2013 13:24:02 -0000 X-Spam-SWARE-Status: No, score=-4.6 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, MAY_BE_FORGED, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD autolearn=ham version=3.3.1 Received: from e38.co.us.ibm.com (HELO e38.co.us.ibm.com) (32.97.110.159) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Tue, 07 May 2013 13:24:01 +0000 Received: from /spool/local by e38.co.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 7 May 2013 07:23:59 -0600 Received: from d03dlp03.boulder.ibm.com (9.17.202.179) by e38.co.us.ibm.com (192.168.1.138) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Tue, 7 May 2013 07:23:56 -0600 Received: from d03relay02.boulder.ibm.com (d03relay02.boulder.ibm.com [9.17.195.227]) by d03dlp03.boulder.ibm.com (Postfix) with ESMTP id 53D3619D8067 for ; Tue, 7 May 2013 07:23:49 -0600 (MDT) Received: from d03av06.boulder.ibm.com (d03av06.boulder.ibm.com [9.17.195.245]) by d03relay02.boulder.ibm.com (8.13.8/8.13.8/NCO v10.0) with ESMTP id r47DNiXl060038 for ; Tue, 7 May 2013 07:23:51 -0600 Received: from d03av06.boulder.ibm.com (loopback [127.0.0.1]) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVout) with ESMTP id r47DPcF1011630 for ; Tue, 7 May 2013 07:25:38 -0600 Received: from [9.10.86.97] (oc8801110288.ibm.com.rchland.ibm.com [9.10.86.97] (may be forged)) by d03av06.boulder.ibm.com (8.14.4/8.13.1/NCO v10.0 AVin) with ESMTP id r47DPb4i011605; Tue, 7 May 2013 07:25:38 -0600 Subject: [PATCH] Limit SLSR increment vector size to avoid quadratic behavior From: Bill Schmidt To: gcc-patches@gcc.gnu.org Cc: rguenther@suse.de, bergner@vnet.ibm.com Date: Tue, 07 May 2013 08:22:40 -0500 Message-ID: <1367932960.4938.21.camel@oc8801110288.ibm.com> Mime-Version: 1.0 X-TM-AS-MML: No X-Content-Scanned: Fidelis XPS MAILER x-cbid: 13050713-5518-0000-0000-00000E607009 This handles the unlikely case where there are many different increments associated with a group of related SLSR candidates, which could result in poor performance when doing linear searches of the increment vector. The size of the increment vector is limited to a reasonable constant, and increments that do not appear in the increment vector are not processed. Bootstrapped and tested on powerpc64-unknown-linux-gnu with no new regressions. Ok for trunk? Thanks, Bill 2013-05-06 Bill Schmidt * gimple-ssa-strength-reduction.c (MAX_INCR_VEC_LEN): New constant. (incr_vec_index): Return -1 if increment not found. (create_add_on_incoming_edge): Assert if increment not found. (record_increment): Limit number of increments recorded. (all_phi_incrs_profitable): Return false if an increment not found. (replace_profitable_candidates): Don't process increments that were not recorded. (analyze_candidates_and_replace): Limit size of incr_vec. Index: gcc/gimple-ssa-strength-reduction.c =================================================================== --- gcc/gimple-ssa-strength-reduction.c (revision 198680) +++ gcc/gimple-ssa-strength-reduction.c (working copy) @@ -366,9 +366,11 @@ static struct obstack chain_obstack; /* An array INCR_VEC of incr_infos is used during analysis of related candidates having an SSA name for a stride. INCR_VEC_LEN describes - its current length. */ + its current length. MAX_INCR_VEC_LEN is used to avoid costly + pathological cases. */ static incr_info_t incr_vec; static unsigned incr_vec_len; +const int MAX_INCR_VEC_LEN = 16; /* For a chain of candidates with unknown stride, indicates whether or not we must generate pointer arithmetic when replacing statements. */ @@ -1960,9 +1962,11 @@ replace_unconditional_candidate (slsr_cand_t c) replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump); } -/* Return the index in the increment vector of the given INCREMENT. */ +/* Return the index in the increment vector of the given INCREMENT, + or -1 if not found. The latter can occur if more than + MAX_INCR_VEC_LEN increments have been found. */ -static inline unsigned +static inline int incr_vec_index (double_int increment) { unsigned i; @@ -1970,8 +1974,10 @@ incr_vec_index (double_int increment) for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++) ; - gcc_assert (i < incr_vec_len); - return i; + if (i < incr_vec_len) + return i; + else + return -1; } /* Create a new statement along edge E to add BASIS_NAME to the product @@ -2015,9 +2021,10 @@ create_add_on_incoming_edge (slsr_cand_t c, tree b } else { - unsigned i; + int i; bool negate_incr = (!address_arithmetic_p && increment.is_negative ()); i = incr_vec_index (negate_incr ? -increment : increment); + gcc_assert (i >= 0); if (incr_vec[i].initializer) { @@ -2323,7 +2330,7 @@ record_increment (slsr_cand_t c, double_int increm } } - if (!found) + if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1) { /* The first time we see an increment, create the entry for it. If this is the root candidate which doesn't have a basis, set @@ -3025,7 +3032,7 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph } else { - unsigned j; + int j; slsr_cand_t arg_cand = base_cand_from_table (arg); double_int increment = arg_cand->index - basis->index; @@ -3041,14 +3048,19 @@ all_phi_incrs_profitable (slsr_cand_t c, gimple ph print_gimple_stmt (dump_file, phi, 0, 0); fputs (" increment: ", dump_file); dump_double_int (dump_file, increment, false); - fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); - if (profitable_increment_p (j)) - fputs (" Replacing...\n", dump_file); - else - fputs (" Not replaced.\n", dump_file); + if (j < 0) + fprintf (dump_file, + "\n Not replaced; incr_vec overflow.\n"); + else { + fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); + if (profitable_increment_p (j)) + fputs (" Replacing...\n", dump_file); + else + fputs (" Not replaced.\n", dump_file); + } } - if (!profitable_increment_p (j)) + if (j < 0 || !profitable_increment_p (j)) return false; } } @@ -3268,13 +3280,14 @@ replace_profitable_candidates (slsr_cand_t c) { double_int increment = cand_abs_increment (c); enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt); - unsigned i; + int i; i = incr_vec_index (increment); /* Only process profitable increments. Nothing useful can be done to a cast or copy. */ - if (profitable_increment_p (i) + if (i >= 0 + && profitable_increment_p (i) && orig_code != MODIFY_EXPR && orig_code != NOP_EXPR) { @@ -3378,6 +3391,8 @@ analyze_candidates_and_replace (void) length = count_candidates (c); if (!length) continue; + if (length > MAX_INCR_VEC_LEN) + length = MAX_INCR_VEC_LEN; /* Construct an array of increments for this candidate chain. */ incr_vec = XNEWVEC (incr_info, length);