From patchwork Wed Jun 30 22:01:25 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Maxim Kuvyrkov X-Patchwork-Id: 57458 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 88174B6F3E for ; Thu, 1 Jul 2010 08:01:43 +1000 (EST) Received: (qmail 21006 invoked by alias); 30 Jun 2010 22:01:41 -0000 Received: (qmail 19904 invoked by uid 22791); 30 Jun 2010 22:01:38 -0000 X-SWARE-Spam-Status: No, hits=0.8 required=5.0 tests=AWL, BAYES_00, KAM_STOCKTIP, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 30 Jun 2010 22:01:30 +0000 Received: (qmail 420 invoked from network); 30 Jun 2010 22:01:27 -0000 Received: from unknown (HELO ?172.16.1.24?) (maxim@127.0.0.2) by mail.codesourcery.com with ESMTPA; 30 Jun 2010 22:01:27 -0000 Message-ID: <4C2BBEB5.4080209@codesourcery.com> Date: Thu, 01 Jul 2010 02:01:25 +0400 From: Maxim Kuvyrkov User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.2.4) Gecko/20100608 Thunderbird/3.1 MIME-Version: 1.0 To: Jeff Law CC: gcc-patches Subject: Re: 0006-GCSE-complex-constants.patch References: <4C18F225.2040509@codesourcery.com> <4C18F4BD.5000906@codesourcery.com> <4C1901B3.8080908@redhat.com> <4C226A4F.8040808@codesourcery.com> In-Reply-To: <4C226A4F.8040808@codesourcery.com> 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 On 6/24/10 12:10 AM, Maxim Kuvyrkov wrote: > On 6/16/10 8:54 PM, Jeff Law wrote: >>> Certain architectures (e.g., ARM) cannot easily operate with >>> constants, they need to emit sequences of several instructions to load >>> constants into registers. The common procedure to do this is to emit a >>> (parallel [(set) (clobber (reg1)) ... (clobber (regN))]) instruction >>> which later splits into several instructions using pseudos (regX) to >>> store intermediate values. >>> >>> Currently PRE and hoist do not GCSE constants, and there is a good >>> reason for that, to avoid increasing register pressure; interestingly, >>> symbol_refs are allowed to be GCSE'ed, is this intentional or by >>> accident? >> It's intentional; a SYMBOL_REF if often be rather expensive. Some >> CONST_INTs can have that same property. One could argue that an >> expensive CONST_INT shouldn't be appearing in RTL, but certainly some >> ports have chosen to handle splitting insns with expensive constants >> later in the pipeline. >> >>> >>> In any case, it seems like a good idea to GCSE constants and >>> symbol_refs that need something beyond a simple (set) to get into a >>> register, and not GCSE them otherwise. >> Rather than triggering this on the PARALLEL it might be better to >> trigger it on the cost of the RTX. Triggering on the PARALLEL looks like >> a hack to me -- IMHO we'd be better off fixing the costing mechanism and >> using costing as the trigger. > > Here is reworked patch that > > (a) introduces max_distance property to expressions (counted in > instructions), > > (b) uses RTX cost model to estimate how far an expression can travel > (the greater the cost, the farther the distance), and > > (c) adds two new parameters to tweak the above. > > I am yet to do benchmarking on ARM and x86[_64] to find out what the > optimal parameter values are. Before starting with testing I would like > to get feedback on the concept and its implementation. Ping. The optimal settings turned out to be almost exactly as expected: unrestricted hoisting is best for expressions with "rtx_cost >= COSTS_N_INSNS(3)" and for expression cheaper than that, movement freedom is about 4 instructions per one unit of COSTS_N_INSNS. E.g., an expression of COSTS_N_INSNS(2) will be allowed to move at most 8 instructions up. I did the tuning for ARM -Os with all other patches applied. The result is 0.2% size reduction for non-PIC code and 0.8% size reduction for PIC code. For x86 and x86_64 I verified that the patches provide size improvement, though a smaller one: 0.1-0.2% for PIC and 0.0-0.1% for both non-PIC. In both cases code size metric is geomean across all object files in SPEC2K. OK to check in? Thanks, diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index aafff44..f6d4c04 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -8219,6 +8219,19 @@ when @option{-ftree-vectorize} is used. The number of iterations after vectorization needs to be greater than the value specified by this option to allow vectorization. The default value is 0. +@item gcse-cost-distance-ratio +Scaling factor in calculation of maximum distance an expression +can be moved by GCSE optimizations. This is currently supported only in +code hoisting pass. The bigger the ratio, the more agressive code hoisting +will be with expressions which have cost less than +@option{gcse-unrestricted-cost}. The default value is 10. + +@item gcse-unrestricted-cost +Cost at which GCSE optimizations will not constraint the distance +an expression can travel. This is currently supported only in +code hoisting pass. The lesser the cost, the more aggressive code hoisting +will be. The default value is 3. + @item max-unrolled-insns The maximum number of instructions that a loop should have if that loop is unrolled, and if the loop is unrolled, it determines how many times diff --git a/gcc/gcse.c b/gcc/gcse.c index 1dbd2f0..d734fa4 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -295,6 +295,12 @@ struct expr The value is the newly created pseudo-reg to record a copy of the expression in all the places that reach the redundant copy. */ rtx reaching_reg; + /* Maximum distance in instructions this expression can travel. + We avoid moving simple expressions for more than a few instructions + to keep register pressure under control. + A value of "0" removes restrictions on how far the expression can + travel. */ + int max_distance; }; /* Occurrence of an expression. @@ -418,6 +424,9 @@ static int global_const_prop_count; /* Number of global copies propagated. */ static int global_copy_prop_count; +/* Doing code hoisting. */ +static bool doing_code_hoisting_p = false; + /* For available exprs */ static sbitmap *ae_kill; @@ -431,12 +440,12 @@ static void hash_scan_insn (rtx, struct hash_table_d *); static void hash_scan_set (rtx, rtx, struct hash_table_d *); static void hash_scan_clobber (rtx, rtx, struct hash_table_d *); static void hash_scan_call (rtx, rtx, struct hash_table_d *); -static int want_to_gcse_p (rtx); +static int want_to_gcse_p (rtx, int *); static bool gcse_constant_p (const_rtx); static int oprs_unchanged_p (const_rtx, const_rtx, int); static int oprs_anticipatable_p (const_rtx, const_rtx); static int oprs_available_p (const_rtx, const_rtx); -static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, +static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, int, struct hash_table_d *); static void insert_set_in_table (rtx, rtx, struct hash_table_d *); static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int); @@ -496,7 +505,8 @@ static void alloc_code_hoist_mem (int, int); static void free_code_hoist_mem (void); static void compute_code_hoist_vbeinout (void); static void compute_code_hoist_data (void); -static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *); +static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *, + int, int *); static int hoist_code (void); static int one_code_hoisting_pass (void); static rtx process_insert_insn (struct expr *); @@ -754,7 +764,7 @@ static basic_block current_bb; GCSE. */ static int -want_to_gcse_p (rtx x) +want_to_gcse_p (rtx x, int *max_distance_ptr) { #ifdef STACK_REGS /* On register stack architectures, don't GCSE constants from the @@ -764,18 +774,67 @@ want_to_gcse_p (rtx x) x = avoid_constant_pool_reference (x); #endif + /* GCSE'ing constants: + + We do not specifically distinguish between constant and non-constant + expressions in PRE and Hoist. We use rtx_cost below to limit + the maximum distance simple expressions can travel. + + Nevertheless, constants are much easier to GCSE, and, hence, + it is easy to overdo the optimizations. Usually, excessive PRE and + Hoisting of constant leads to increased register pressure. + + RA can deal with this by rematerialing some of the constants. + Therefore, it is important that the back-end generates sets of constants + in a way that allows reload rematerialize them under high register + pressure, i.e., a pseudo register with REG_EQUAL to constant + is set only once. Failing to do so will result in IRA/reload + spilling such constants under high register pressure instead of + rematerializing them. */ + switch (GET_CODE (x)) { case REG: case SUBREG: + case CALL: + return 0; + case CONST_INT: case CONST_DOUBLE: case CONST_FIXED: case CONST_VECTOR: - case CALL: - return 0; + if (!doing_code_hoisting_p) + /* Do not PRE constants. */ + return 0; + + /* FALLTHRU */ default: + if (doing_code_hoisting_p) + /* PRE doesn't implement max_distance restriction. */ + { + int cost; + int max_distance; + + gcc_assert (!optimize_function_for_speed_p (cfun) + && optimize_function_for_size_p (cfun)); + cost = rtx_cost (x, SET, 0); + + if (cost < COSTS_N_INSNS (GCSE_UNRESTRICTED_COST)) + { + max_distance = (GCSE_COST_DISTANCE_RATIO * cost) / 10; + if (max_distance == 0) + return 0; + + gcc_assert (max_distance > 0); + } + else + max_distance = 0; + + if (max_distance_ptr) + *max_distance_ptr = max_distance; + } + return can_assign_to_reg_without_clobbers_p (x); } } @@ -1089,11 +1148,15 @@ expr_equiv_p (const_rtx x, const_rtx y) It is only used if X is a CONST_INT. ANTIC_P is nonzero if X is an anticipatable expression. - AVAIL_P is nonzero if X is an available expression. */ + AVAIL_P is nonzero if X is an available expression. + + MAX_DISTANCE is the maximum distance in instructions this expression can + be moved. +*/ static void insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, - int avail_p, struct hash_table_d *table) + int avail_p, int max_distance, struct hash_table_d *table) { int found, do_not_record_p; unsigned int hash; @@ -1136,7 +1199,11 @@ insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p, cur_expr->next_same_hash = NULL; cur_expr->antic_occr = NULL; cur_expr->avail_occr = NULL; + gcc_assert (max_distance >= 0); + cur_expr->max_distance = max_distance; } + else + gcc_assert (cur_expr->max_distance == max_distance); /* Now record the occurrence(s). */ if (antic_p) @@ -1237,6 +1304,7 @@ insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table) cur_expr->next_same_hash = NULL; cur_expr->antic_occr = NULL; cur_expr->avail_occr = NULL; + cur_expr->max_distance = 0; /* Not used for set_p tables. */ } /* Now record the occurrence. */ @@ -1306,6 +1374,7 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) { unsigned int regno = REGNO (dest); rtx tmp; + int max_distance = 0; /* See if a REG_EQUAL note shows this equivalent to a simpler expression. @@ -1328,7 +1397,7 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) && !REG_P (src) && (table->set_p ? gcse_constant_p (XEXP (note, 0)) - : want_to_gcse_p (XEXP (note, 0)))) + : want_to_gcse_p (XEXP (note, 0), NULL))) src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src); /* Only record sets of pseudo-regs in the hash table. */ @@ -1343,7 +1412,7 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) can't do the same thing at the rtl level. */ && !can_throw_internal (insn) /* Is SET_SRC something we want to gcse? */ - && want_to_gcse_p (src) + && want_to_gcse_p (src, &max_distance) /* Don't CSE a nop. */ && ! set_noop_p (pat) /* Don't GCSE if it has attached REG_EQUIV note. @@ -1367,7 +1436,8 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) int avail_p = (oprs_available_p (src, insn) && ! JUMP_P (insn)); - insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table); + insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, + max_distance, table); } /* Record sets for constant/copy propagation. */ @@ -1404,7 +1474,7 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) do that easily for EH edges so disable GCSE on these for now. */ && !can_throw_internal (insn) /* Is SET_DEST something we want to gcse? */ - && want_to_gcse_p (dest) + && want_to_gcse_p (dest, NULL) /* Don't CSE a nop. */ && ! set_noop_p (pat) /* Don't GCSE if it has attached REG_EQUIV note. @@ -1425,7 +1495,7 @@ hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table) && ! JUMP_P (insn); /* Record the memory expression (DEST) in the hash table. */ - insert_expr_in_table (dest, GET_MODE (dest), insn, + insert_expr_in_table (dest, GET_MODE (dest), insn, 0, antic_p, avail_p, table); } } @@ -1512,8 +1582,8 @@ dump_hash_table (FILE *file, const char *name, struct hash_table_d *table) if (flat_table[i] != 0) { expr = flat_table[i]; - fprintf (file, "Index %d (hash value %d)\n ", - expr->bitmap_index, hash_val[i]); + fprintf (file, "Index %d (hash value %d; max distance %d)\n ", + expr->bitmap_index, hash_val[i], expr->max_distance); print_rtl (file, expr->expr); fprintf (file, "\n"); } @@ -4196,6 +4266,8 @@ compute_code_hoist_data (void) /* Determine if the expression identified by EXPR_INDEX would reach BB unimpared if it was placed at the end of EXPR_BB. + Stop the search if the expression would need to be moved more + than DISTANCE instructions. It's unclear exactly what Muchnick meant by "unimpared". It seems to me that the expression must either be computed or transparent in @@ -4208,12 +4280,24 @@ compute_code_hoist_data (void) paths. */ static int -hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited) +hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, + char *visited, int distance, int *bb_size) { edge pred; edge_iterator ei; int visited_allocated_locally = 0; + /* Terminate the search if distance, for which EXPR is allowed to move, + is exhausted. */ + if (distance > 0) + { + distance -= bb_size[bb->index]; + + if (distance <= 0) + return 0; + } + else + gcc_assert (distance == 0); if (visited == NULL) { @@ -4242,8 +4326,8 @@ hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, else { visited[pred_bb->index] = 1; - if (! hoist_expr_reaches_here_p (expr_bb, expr_index, - pred_bb, visited)) + if (! hoist_expr_reaches_here_p (expr_bb, expr_index, pred_bb, + visited, distance, bb_size)) break; } } @@ -4253,6 +4337,17 @@ hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, return (pred == NULL); } +/* Find occurence in BB. */ +static struct occr * +find_occr_in_bb (struct occr *occr, basic_block bb) +{ + /* Find the right occurrence of this expression. */ + while (BLOCK_FOR_INSN (occr->insn) != bb && occr) + occr = occr->next; + + return occr; +} + /* Actually perform code hoisting. */ static int @@ -4263,6 +4358,8 @@ hoist_code (void) unsigned int i,j; struct expr **index_map; struct expr *expr; + int *to_bb_head; + int *bb_size; int changed = 0; sbitmap_vector_zero (hoist_exprs, last_basic_block); @@ -4275,6 +4372,30 @@ hoist_code (void) for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash) index_map[expr->bitmap_index] = expr; + to_bb_head = XCNEWVEC (int, get_max_uid ()); + bb_size = XCNEWVEC (int, last_basic_block); + + FOR_EACH_BB (bb) + { + rtx insn; + rtx bb_end; + int to_head; + + insn = BB_HEAD (bb); + bb_end = BB_END (bb); + to_head = 0; + + while (insn != bb_end) + { + if (NONDEBUG_INSN_P (insn)) + to_bb_head[INSN_UID (insn)] = to_head++; + + insn = NEXT_INSN (insn); + } + + bb_size[bb->index] = to_head; + } + /* Walk over each basic block looking for potentially hoistable expressions, nothing gets hoisted from the entry block. */ FOR_EACH_BB (bb) @@ -4297,6 +4418,9 @@ hoist_code (void) computes the expression. */ for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) { + struct expr *expr = index_map[i]; + int max_distance; + /* Ignore self dominance. */ if (bb == dominated) continue; @@ -4306,12 +4430,30 @@ hoist_code (void) if (!TEST_BIT (antloc[dominated->index], i)) continue; + max_distance = expr->max_distance; + if (max_distance > 0) + { + struct occr *occr; + + occr = find_occr_in_bb (expr->antic_occr, dominated); + gcc_assert (occr); + + gcc_assert (NONDEBUG_INSN_P (occr->insn)); + + /* Adjust MAX_DISTANCE to account for the fact that + OCCR won't have to travel all of DOMINATED, but + only part of it. */ + max_distance += (bb_size[dominated->index] + - to_bb_head[INSN_UID (occr->insn)]); + } + /* Note if the expression would reach the dominated block unimpared if it was placed at the end of BB. Keep track of how many times this expression is hoistable from a dominated block into BB. */ - if (hoist_expr_reaches_here_p (bb, i, dominated, NULL)) + if (hoist_expr_reaches_here_p (bb, i, dominated, NULL, + max_distance, bb_size)) hoistable++; } @@ -4354,6 +4496,10 @@ hoist_code (void) computes the expression. */ for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++) { + struct expr *expr = index_map[i]; + struct occr *occr = NULL; + int max_distance; + /* Ignore self dominance. */ if (bb == dominated) continue; @@ -4364,23 +4510,42 @@ hoist_code (void) if (!TEST_BIT (antloc[dominated->index], i)) continue; + max_distance = expr->max_distance; + if (max_distance > 0) + { + occr = find_occr_in_bb (expr->antic_occr, dominated); + gcc_assert (occr); + + gcc_assert (NONDEBUG_INSN_P (occr->insn)); + + /* Adjust MAX_DISTANCE to account for the fact that + OCCR won't have to travel all of DOMINATED, but + only part of it. */ + max_distance += (bb_size[dominated->index] + - to_bb_head[INSN_UID (occr->insn)]); + } + /* The expression is computed in the dominated block and it would be safe to compute it at the start of the dominated block. Now we have to determine if the expression would reach the dominated block if it was - placed at the end of BB. */ - if (hoist_expr_reaches_here_p (bb, i, dominated, NULL)) + placed at the end of BB. + Note: the fact that hoist_exprs has i-th bit set means + that /some/, not necesserilly all, occurences from + the dominated blocks can be hoisted to BB. Here we check + if a specific occurence can be hoisted to BB. */ + if (hoist_expr_reaches_here_p (bb, i, dominated, NULL, + max_distance, bb_size)) { - struct expr *expr = index_map[i]; - struct occr *occr = expr->antic_occr; rtx insn; rtx set; - /* Find the right occurrence of this expression. */ - while (BLOCK_FOR_INSN (occr->insn) != dominated && occr) - occr = occr->next; + if (!occr) + { + occr = find_occr_in_bb (expr->antic_occr, dominated); + gcc_assert (occr); + } - gcc_assert (occr); insn = occr->insn; set = single_set (insn); gcc_assert (set); @@ -4410,6 +4575,8 @@ hoist_code (void) VEC_free (basic_block, heap, domby); } + free (bb_size); + free (to_bb_head); free (index_map); return changed; @@ -4432,6 +4599,8 @@ one_code_hoisting_pass (void) || is_too_expensive (_("GCSE disabled"))) return 0; + doing_code_hoisting_p = true; + /* We need alias. */ init_alias_analysis (); @@ -4467,6 +4636,8 @@ one_code_hoisting_pass (void) gcse_subst_count, gcse_create_count); } + doing_code_hoisting_p = false; + return changed; } diff --git a/gcc/params.def b/gcc/params.def index d4321e4..551e8e2 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -225,6 +225,21 @@ DEFPARAM(PARAM_GCSE_AFTER_RELOAD_CRITICAL_FRACTION, "gcse-after-reload-critical-fraction", "The threshold ratio of critical edges execution count that permit performing redundancy elimination after reload", 10, 0, 0) + +/* GCSE will use GCSE_COST_DISTANCE_RATION as a scaling factor + to calculate maximum distance for which an expression is allowed to move + from its rtx_cost. */ +DEFPARAM(PARAM_GCSE_COST_DISTANCE_RATIO, + "gcse-cost-distance-ratio", + "Scaling factor in calculation of maximum distance an expression can be moved by GCSE optimizations", + 10, 0, 0) +/* GCSE won't restrict distance for which an expression with rtx_cost greater + than COSTS_N_INSN(GCSE_UNRESTRICTED_COST) is allowed to move. */ +DEFPARAM(PARAM_GCSE_UNRESTRICTED_COST, + "gcse-unrestricted-cost", + "Cost at which GCSE optimizations will not constraint the distance an expression can travel", + 3, 0, 0) + /* This parameter limits the number of insns in a loop that will be unrolled, and by how much the loop is unrolled. diff --git a/gcc/params.h b/gcc/params.h index 833fc3b..174edc1 100644 --- a/gcc/params.h +++ b/gcc/params.h @@ -125,6 +125,10 @@ typedef enum compiler_param PARAM_VALUE (PARAM_GCSE_AFTER_RELOAD_PARTIAL_FRACTION) #define GCSE_AFTER_RELOAD_CRITICAL_FRACTION \ PARAM_VALUE (PARAM_GCSE_AFTER_RELOAD_CRITICAL_FRACTION) +#define GCSE_COST_DISTANCE_RATIO \ + PARAM_VALUE (PARAM_GCSE_COST_DISTANCE_RATIO) +#define GCSE_UNRESTRICTED_COST \ + PARAM_VALUE (PARAM_GCSE_UNRESTRICTED_COST) #define MAX_UNROLLED_INSNS \ PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) #define MAX_SMS_LOOP_NUMBER \