diff options
| -rw-r--r-- | gcc/ChangeLog | 26 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/graphite.c | 114 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 5 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 145 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.h | 14 |
6 files changed, 172 insertions, 134 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 743c6081ca5..ef34d8d541d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,29 @@ +2008-09-09 Sebastian Pop <sebastian.pop@amd.com> + + PR tree-optimization/37375 + * tree-scalar-evolution.c (scev_info_str): Add field instantiated_below. + (new_scev_info_str, eq_scev_info, find_var_scev_info, + set_scalar_evolution, get_scalar_evolution, get_instantiated_value, + set_instantiated_value): Pass instantiated_below. + (analyze_scalar_evolution_1, analyze_scalar_evolution): Update calls to + above functions. + (instantiate_scev_1, instantiate_scev): Pass a basic block above which the + definitions are not instantiated. + + * tree-scalar-evolution.h (instantiate_scev): Update declaration. + (block_before_loop): New. + * tree-data-ref.c (dr_analyze_indices): Update uses of instantiate_scev. + * graphite.c (block_before_scop): New. + (loop_affine_expr, stmt_simple_for_scop_p, harmful_stmt_in_bb): Pass a + basic block, not a loop for determining the parameters. + (scopdet_edge_info, build_scops_1): Do not pass outermost loop in the + scop. + (idx_record_params, find_params_in_bb, find_scop_parameters, + build_loop_iteration_domains, add_conditions_to_domain): Update calls + to instantiate_scev. + + * Makefile.in (cfgloopmanip.o): Add missing dependency on TREE_FLOW_H. + 2008-09-09 Vladimir Makarov <vmakarov@redhat.com> PR rtl-opt/37333 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 49c394d79be..f486392433b 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -2816,7 +2816,7 @@ loop-invariant.o : loop-invariant.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \ $(HASHTAB_H) except.h cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \ $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) output.h \ - coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H) + coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H) $(TREE_FLOW_H) loop-init.o : loop-init.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \ $(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) \ coretypes.h $(TM_H) $(OBSTACK_H) tree-pass.h $(TIMEVAR_H) $(FLAGS_H) $(DF_H) diff --git a/gcc/graphite.c b/gcc/graphite.c index 86b0eae6f97..40a317eb5f5 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -717,16 +717,24 @@ outermost_loop_in_scop (scop_p scop, basic_block bb) return nest; } +/* Returns the block preceding the entry of SCOP. */ + +static basic_block +block_before_scop (scop_p scop) +{ + return SESE_ENTRY (SCOP_REGION (scop))->src; +} + /* Return true when EXPR is an affine function in LOOP with parameters - instantiated relative to outermost_loop. */ + instantiated relative to SCOP_ENTRY. */ static bool -loop_affine_expr (struct loop *outermost_loop, struct loop *loop, tree expr) +loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr) { - int n = outermost_loop->num; + int n = scop_entry->loop_father->num; tree scev = analyze_scalar_evolution (loop, expr); - scev = instantiate_scev (outermost_loop, loop, scev); + scev = instantiate_scev (scop_entry, loop, scev); return (evolution_function_is_invariant_p (scev, n) || evolution_function_is_affine_multivariate_p (scev, n)); @@ -751,11 +759,11 @@ is_simple_operand (loop_p loop, gimple stmt, tree op) } /* Return true only when STMT is simple enough for being handled by - Graphite. This depends on OUTERMOST_LOOP, as the parametetrs are - initialized relative to this loop. */ + Graphite. This depends on SCOP_ENTRY, as the parametetrs are + initialized relatively to this basic block. */ static bool -stmt_simple_for_scop_p (struct loop *outermost_loop, gimple stmt) +stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt) { basic_block bb = gimple_bb (stmt); struct loop *loop = bb->loop_father; @@ -791,11 +799,11 @@ stmt_simple_for_scop_p (struct loop *outermost_loop, gimple stmt) || code == GE_EXPR)) return false; - if (!outermost_loop) + if (!scop_entry) return false; FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES) - if (!loop_affine_expr (outermost_loop, loop, op)) + if (!loop_affine_expr (scop_entry, loop, op)) return false; return true; @@ -850,18 +858,17 @@ stmt_simple_for_scop_p (struct loop *outermost_loop, gimple stmt) } /* Returns the statement of BB that contains a harmful operation: that - can be a function call with side effects, data dependences that - cannot be computed in OUTERMOST_LOOP, the induction variables are - not linear with respect to OUTERMOST_LOOP, etc. The current open + can be a function call with side effects, the induction variables + are not linear with respect to SCOP_ENTRY, etc. The current open scop should end before this statement. */ static gimple -harmful_stmt_in_bb (struct loop *outermost_loop, basic_block bb) +harmful_stmt_in_bb (basic_block scop_entry, basic_block bb) { gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - if (!stmt_simple_for_scop_p (outermost_loop, gsi_stmt (gsi))) + if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi))) return gsi_stmt (gsi); return NULL; @@ -1048,20 +1055,28 @@ struct scopdet_info }; static struct scopdet_info build_scops_1 (edge, VEC (scop_p, heap) **, - loop_p, loop_p); + loop_p); /* Checks, if a bb can be added to a SCoP. */ static struct scopdet_info -scopdet_edge_info (edge ee, loop_p outermost_loop, +scopdet_edge_info (edge ee, VEC (scop_p, heap) **scops, gbb_type type, gimple *stmt) { basic_block bb = ee->dest; struct loop *loop = bb->loop_father; struct scopdet_info result; + basic_block scop_entry; - *stmt = harmful_stmt_in_bb (outermost_loop, bb); + if (VEC_length (scop_p, *scops) != 0) + scop_entry = block_before_scop (VEC_last (scop_p, *scops)); + else if (loop->header) + scop_entry = loop->header; + else + scop_entry = ENTRY_BLOCK_PTR; + + *stmt = harmful_stmt_in_bb (scop_entry, bb); result.difficult = (*stmt != NULL); result.last = NULL; @@ -1084,7 +1099,7 @@ scopdet_edge_info (edge ee, loop_p outermost_loop, VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3); struct scopdet_info sinfo; - sinfo = build_scops_1 (ee, &tmp_scops, loop, outermost_loop); + sinfo = build_scops_1 (ee, &tmp_scops, loop); result.last = single_exit (bb->loop_father); @@ -1117,20 +1132,18 @@ scopdet_edge_info (edge ee, loop_p outermost_loop, case GBB_LOOP_MULT_EXIT_HEADER: { /* XXX: Handle loop nests with the same header. */ - /* XXX: Handle iterative optimization of outermost_loop. */ /* XXX: For now we just do not join loops with multiple exits. If the exits lead to the same bb it may be possible to join the loop. */ VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3); VEC (edge, heap) *exits = get_loop_exit_edges (loop); edge e; int i; - build_scops_1 (ee, &tmp_scops, loop, outermost_loop); + build_scops_1 (ee, &tmp_scops, loop); for (i = 0; VEC_iterate (edge, exits, i, e); i++) if (dominated_by_p (CDI_DOMINATORS, e->dest, e->src) && e->dest->loop_father == loop_outer (loop)) - build_scops_1 (e, &tmp_scops, e->dest->loop_father, - outermost_loop); + build_scops_1 (e, &tmp_scops, e->dest->loop_father); result.next = NULL; result.last = NULL; @@ -1199,7 +1212,7 @@ scopdet_edge_info (edge ee, loop_p outermost_loop, continue; } - sinfo = build_scops_1 (e, &tmp_scops, loop, outermost_loop); + sinfo = build_scops_1 (e, &tmp_scops, loop); result.exits |= sinfo.exits; result.last = sinfo.last; @@ -1261,10 +1274,9 @@ scopdet_edge_info (edge ee, loop_p outermost_loop, e = split_block (dom_bb, NULL); if (loop_depth (loop) > loop_depth (dom_bb->loop_father)) - sinfo = build_scops_1 (e, &tmp_scops, loop_outer (loop), - outermost_loop); + sinfo = build_scops_1 (e, &tmp_scops, loop_outer (loop)); else - sinfo = build_scops_1 (e, &tmp_scops, loop, outermost_loop); + sinfo = build_scops_1 (e, &tmp_scops, loop); result.exits |= sinfo.exits; @@ -1335,8 +1347,7 @@ end_scop (scop_p scop, edge exit, bool split_entry) /* Creates the SCoPs and writes entry and exit points for every SCoP. */ static struct scopdet_info -build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop, - loop_p outermost_loop) +build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop) { edge current = start; @@ -1357,7 +1368,7 @@ build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop, and can only be added if all bbs in deeper layers are simple. */ while (current != NULL) { - sinfo = scopdet_edge_info (current, outermost_loop, scops, + sinfo = scopdet_edge_info (current, scops, get_bb_type (current->dest, loop), &stmt); if (!in_scop && !(sinfo.exits || sinfo.difficult)) @@ -1433,7 +1444,7 @@ static void build_scops (void) { struct loop *loop = current_loops->tree_root; - build_scops_1 (single_succ_edge (ENTRY_BLOCK_PTR), ¤t_scops, loop, loop); + build_scops_1 (single_succ_edge (ENTRY_BLOCK_PTR), ¤t_scops, loop); } /* Gather the basic blocks belonging to the SCOP. */ @@ -1895,19 +1906,15 @@ idx_record_params (tree base, tree *idx, void *dta) tree scev; scop_p scop = data->scop; struct loop *loop = data->loop; + Value one; scev = analyze_scalar_evolution (loop, *idx); - scev = instantiate_scev (outermost_loop_in_scop (scop, loop->header), - loop, scev); - - { - Value one; + scev = instantiate_scev (block_before_scop (scop), loop, scev); - value_init (one); - value_set_si (one, 1); - scan_tree_for_params (scop, scev, NULL, 0, one, false); - value_clear (one); - } + value_init (one); + value_set_si (one, 1); + scan_tree_for_params (scop, scev, NULL, 0, one, false); + value_clear (one); } return true; @@ -1957,11 +1964,11 @@ find_params_in_bb (scop_p scop, basic_block bb) lhs = gimple_cond_lhs (stmt); lhs = analyze_scalar_evolution (loop, lhs); - lhs = instantiate_scev (nest, loop, lhs); + lhs = instantiate_scev (block_before_scop (scop), loop, lhs); rhs = gimple_cond_rhs (stmt); rhs = analyze_scalar_evolution (loop, rhs); - rhs = instantiate_scev (nest, loop, rhs); + rhs = instantiate_scev (block_before_scop (scop), loop, rhs); value_init (one); scan_tree_for_params (scop, lhs, NULL, 0, one, false); @@ -2081,8 +2088,7 @@ find_scop_parameters (scop_p scop) continue; nb_iters = analyze_scalar_evolution (loop, nb_iters); - nb_iters = instantiate_scev (outermost_loop_in_scop (scop, loop->header), - loop, nb_iters); + nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters); scan_tree_for_params (scop, nb_iters, NULL, 0, one, false); } @@ -2209,10 +2215,10 @@ build_loop_iteration_domains (scop_p scop, struct loop *loop, row++; value_set_si (cstr->p[row][0], 1); value_set_si (cstr->p[row][loop_col], -1); + nb_iters = analyze_scalar_evolution (loop, nb_iters); - nb_iters = - instantiate_scev (outermost_loop_in_scop (scop, loop->header), - loop, nb_iters); + nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters); + value_init (one); value_set_si (one, 1); scan_tree_for_params (scop, nb_iters, cstr, row, one, false); @@ -2333,15 +2339,15 @@ add_conditions_to_domain (graphite_bb_p gb) tree left; tree right; loop_p loop = GBB_BB (gb)->loop_father; - loop_p outermost = outermost_loop_in_scop (scop, GBB_BB (gb)); left = gimple_cond_lhs (stmt); right = gimple_cond_rhs (stmt); left = analyze_scalar_evolution (loop, left); right = analyze_scalar_evolution (loop, right); - left = instantiate_scev (outermost, loop, left); - right = instantiate_scev (outermost, loop, right); + + left = instantiate_scev (block_before_scop (scop), loop, left); + right = instantiate_scev (block_before_scop (scop), loop, right); code = gimple_cond_code (stmt); @@ -3974,13 +3980,13 @@ gbb_can_be_ignored (graphite_bb_p gb) XXX: Just a heuristic, that needs further investigation. */ case GIMPLE_ASSIGN: { - tree var = gimple_assign_lhs (stmt); + tree var = gimple_assign_lhs (stmt); var = analyze_scalar_evolution (loop, var); - var = instantiate_scev (outermost_loop_in_scop (scop, - GBB_BB (gb)), - loop, var); + var = instantiate_scev (block_before_scop (scop), loop, var); + if (TREE_CODE (var) == SCEV_NOT_KNOWN) return false; + break; } /* Otherwise not ignoreable. */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index af1146c7fef..2be0ad1b401 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -747,6 +747,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) VEC (tree, heap) *access_fns = NULL; tree ref = unshare_expr (DR_REF (dr)), aref = ref, op; tree base, off, access_fn; + basic_block before_loop = block_before_loop (nest); while (handled_component_p (aref)) { @@ -754,7 +755,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) { op = TREE_OPERAND (aref, 1); access_fn = analyze_scalar_evolution (loop, op); - access_fn = instantiate_scev (nest, loop, access_fn); + access_fn = instantiate_scev (before_loop, loop, access_fn); VEC_safe_push (tree, heap, access_fns, access_fn); TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0); @@ -767,7 +768,7 @@ dr_analyze_indices (struct data_reference *dr, struct loop *nest) { op = TREE_OPERAND (aref, 0); access_fn = analyze_scalar_evolution (loop, op); - access_fn = instantiate_scev (nest, loop, access_fn); + access_fn = instantiate_scev (before_loop, loop, access_fn); base = initial_condition (access_fn); split_constant_offset (base, &base, &off); access_fn = chrec_replace_initial_condition (access_fn, diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 67fcd08dda0..64d628a1adf 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -175,8 +175,8 @@ along with GCC; see the file COPYING3. If not see value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is {0, +, 1}_1. To obtain the evolution function in loop_3 and instantiate the scalar variables up to loop_1, one has to use: - instantiate_scev (loop_1, loop_3, "j + k"). The result of this - call is {{0, +, 1}_1, +, 1}_2. + instantiate_scev (block_before_loop (loop_1), loop_3, "j + k"). + The result of this call is {{0, +, 1}_1, +, 1}_2. Example 3: Higher degree polynomials. @@ -278,11 +278,13 @@ along with GCC; see the file COPYING3. If not see static tree analyze_scalar_evolution_1 (struct loop *, tree, tree); -/* The cached information about a ssa name VAR, claiming that inside LOOP, - the value of VAR can be expressed as CHREC. */ +/* The cached information about an SSA name VAR, claiming that below + basic block INSTANTIATED_BELOW, the value of VAR can be expressed + as CHREC. */ struct scev_info_str GTY(()) { + basic_block instantiated_below; tree var; tree chrec; }; @@ -306,22 +308,21 @@ tree chrec_dont_know; happen, then it qualifies it with chrec_known. */ tree chrec_known; -static bitmap already_instantiated; - static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info; -/* Constructs a new SCEV_INFO_STR structure. */ +/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */ static inline struct scev_info_str * -new_scev_info_str (tree var) +new_scev_info_str (basic_block instantiated_below, tree var) { struct scev_info_str *res; res = GGC_NEW (struct scev_info_str); res->var = var; res->chrec = chrec_not_analyzed_yet; - + res->instantiated_below = instantiated_below; + return res; } @@ -341,7 +342,8 @@ eq_scev_info (const void *e1, const void *e2) const struct scev_info_str *elt1 = (const struct scev_info_str *) e1; const struct scev_info_str *elt2 = (const struct scev_info_str *) e2; - return elt1->var == elt2->var; + return (elt1->var == elt2->var + && elt1->instantiated_below == elt2->instantiated_below); } /* Deletes database element E. */ @@ -352,22 +354,22 @@ del_scev_info (void *e) ggc_free (e); } -/* Get the index corresponding to VAR in the current LOOP. If - it's the first time we ask for this VAR, then we return - chrec_not_analyzed_yet for this VAR and return its index. */ +/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block. + A first query on VAR returns chrec_not_analyzed_yet. */ static tree * -find_var_scev_info (tree var) +find_var_scev_info (basic_block instantiated_below, tree var) { struct scev_info_str *res; struct scev_info_str tmp; PTR *slot; tmp.var = var; + tmp.instantiated_below = instantiated_below; slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT); if (!*slot) - *slot = new_scev_info_str (var); + *slot = new_scev_info_str (instantiated_below, var); res = (struct scev_info_str *) *slot; return &res->chrec; @@ -570,20 +572,22 @@ chrec_is_positive (tree chrec, bool *value) /* Associate CHREC to SCALAR. */ static void -set_scalar_evolution (tree scalar, tree chrec) +set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec) { tree *scalar_info; if (TREE_CODE (scalar) != SSA_NAME) return; - scalar_info = find_var_scev_info (scalar); + scalar_info = find_var_scev_info (instantiated_below, scalar); if (dump_file) { if (dump_flags & TDF_DETAILS) { fprintf (dump_file, "(set_scalar_evolution \n"); + fprintf (dump_file, " instantiated_below = %d \n", + instantiated_below->index); fprintf (dump_file, " (scalar = "); print_generic_expr (dump_file, scalar, 0); fprintf (dump_file, ")\n (scalar_evolution = "); @@ -597,10 +601,11 @@ set_scalar_evolution (tree scalar, tree chrec) *scalar_info = chrec; } -/* Retrieve the chrec associated to SCALAR in the LOOP. */ +/* Retrieve the chrec associated to SCALAR instantiated below + INSTANTIATED_BELOW block. */ static tree -get_scalar_evolution (tree scalar) +get_scalar_evolution (basic_block instantiated_below, tree scalar) { tree res; @@ -620,7 +625,7 @@ get_scalar_evolution (tree scalar) switch (TREE_CODE (scalar)) { case SSA_NAME: - res = *find_var_scev_info (scalar); + res = *find_var_scev_info (instantiated_below, scalar); break; case REAL_CST: @@ -1845,7 +1850,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) res = var; if (loop == def_loop) - set_scalar_evolution (var, res); + set_scalar_evolution (block_before_loop (loop), var, res); return res; } @@ -1879,7 +1884,8 @@ analyze_scalar_evolution (struct loop *loop, tree var) fprintf (dump_file, ")\n"); } - res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var)); + res = get_scalar_evolution (block_before_loop (loop), var); + res = analyze_scalar_evolution_1 (loop, var, res); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ")\n"); @@ -1926,14 +1932,17 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, } } -/* Returns instantiated value for VERSION in CACHE. */ +/* Returns from CACHE the value for VERSION instantiated below + INSTANTIATED_BELOW block. */ static tree -get_instantiated_value (htab_t cache, tree version) +get_instantiated_value (htab_t cache, basic_block instantiated_below, + tree version) { struct scev_info_str *info, pattern; pattern.var = version; + pattern.instantiated_below = instantiated_below; info = (struct scev_info_str *) htab_find (cache, &pattern); if (info) @@ -1942,10 +1951,12 @@ get_instantiated_value (htab_t cache, tree version) return NULL_TREE; } -/* Sets instantiated value for VERSION to VAL in CACHE. */ +/* Sets in CACHE the value of VERSION instantiated below basic block + INSTANTIATED_BELOW to VAL. */ static void -set_instantiated_value (htab_t cache, tree version, tree val) +set_instantiated_value (htab_t cache, basic_block instantiated_below, + tree version, tree val) { struct scev_info_str *info, pattern; PTR *slot; @@ -1954,7 +1965,7 @@ set_instantiated_value (htab_t cache, tree version, tree val) slot = htab_find_slot (cache, &pattern, INSERT); if (!*slot) - *slot = new_scev_info_str (version); + *slot = new_scev_info_str (instantiated_below, version); info = (struct scev_info_str *) *slot; info->chrec = val; } @@ -1989,7 +2000,7 @@ loop_closed_phi_def (tree var) return NULL_TREE; } -/* Analyze all the parameters of the chrec, between INSTANTIATION_LOOP +/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW and EVOLUTION_LOOP, that were left under a symbolic form. CHREC is the scalar evolution to instantiate. @@ -2004,7 +2015,7 @@ loop_closed_phi_def (tree var) instantiated, and to stop if it exceeds some limit. */ static tree -instantiate_scev_1 (struct loop *instantiation_loop, +instantiate_scev_1 (basic_block instantiate_below, struct loop *evolution_loop, tree chrec, bool fold_conversions, htab_t cache, int size_expr) { @@ -2030,7 +2041,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, evolutions in outer loops), nothing to do. */ if (!def_bb || loop_depth (def_bb->loop_father) == 0 - || !flow_bb_inside_loop_p (instantiation_loop, def_bb)) + || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb)) return chrec; /* We cache the value of instantiated variable to avoid exponential @@ -2042,31 +2053,17 @@ instantiate_scev_1 (struct loop *instantiation_loop, | a_2 -> {0, +, 1, +, a_2}_1 */ - res = get_instantiated_value (cache, chrec); + res = get_instantiated_value (cache, instantiate_below, chrec); if (res) return res; - /* Store the convenient value for chrec in the structure. If it - is defined outside of the loop, we may just leave it in symbolic - form, otherwise we need to admit that we do not know its behavior - inside the loop. */ - res = !flow_bb_inside_loop_p (instantiation_loop, def_bb) - ? chrec : chrec_dont_know; - set_instantiated_value (cache, chrec, res); - - /* To make things even more complicated, instantiate_scev_1 - calls analyze_scalar_evolution that may call # of iterations - analysis that may in turn call instantiate_scev_1 again. - To prevent the infinite recursion, keep also the bitmap of - ssa names that are being instantiated globally. */ - if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec))) - return res; + res = chrec_dont_know; + set_instantiated_value (cache, instantiate_below, chrec, res); def_loop = find_common_loop (evolution_loop, def_bb->loop_father); /* If the analysis yields a parametric chrec, instantiate the result again. */ - bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec)); res = analyze_scalar_evolution (def_loop, chrec); /* Don't instantiate loop-closed-ssa phi nodes. */ @@ -2085,23 +2082,21 @@ instantiate_scev_1 (struct loop *instantiation_loop, } else if (res != chrec_dont_know) - res = instantiate_scev_1 (instantiation_loop, evolution_loop, res, + res = instantiate_scev_1 (instantiate_below, evolution_loop, res, fold_conversions, cache, size_expr); - bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec)); - /* Store the correct value to the cache. */ - set_instantiated_value (cache, chrec, res); + set_instantiated_value (cache, instantiate_below, chrec, res); return res; case POLYNOMIAL_CHREC: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, CHREC_LEFT (chrec), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, CHREC_RIGHT (chrec), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2117,13 +2112,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, case POINTER_PLUS_EXPR: case PLUS_EXPR: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2139,13 +2134,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, return chrec; case MINUS_EXPR: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2161,13 +2156,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, return chrec; case MULT_EXPR: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2183,7 +2178,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, return chrec; CASE_CONVERT: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) @@ -2221,19 +2216,19 @@ instantiate_scev_1 (struct loop *instantiation_loop, switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) { case 3: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) return chrec_dont_know; - op2 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op2 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 2), fold_conversions, cache, size_expr); if (op2 == chrec_dont_know) @@ -2248,13 +2243,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, TREE_TYPE (chrec), op0, op1, op2); case 2: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) return chrec_dont_know; - op1 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op1 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 1), fold_conversions, cache, size_expr); if (op1 == chrec_dont_know) @@ -2266,7 +2261,7 @@ instantiate_scev_1 (struct loop *instantiation_loop, return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1); case 1: - op0 = instantiate_scev_1 (instantiation_loop, evolution_loop, + op0 = instantiate_scev_1 (instantiate_below, evolution_loop, TREE_OPERAND (chrec, 0), fold_conversions, cache, size_expr); if (op0 == chrec_dont_know) @@ -2287,12 +2282,13 @@ instantiate_scev_1 (struct loop *instantiation_loop, } /* Analyze all the parameters of the chrec that were left under a - symbolic form. INSTANTIATION_LOOP is the loop in which symbolic - names have to be instantiated, and EVOLUTION_LOOP is the loop in - which the evolution of scalars have to be analyzed. */ + symbolic form. INSTANTIATE_BELOW is the basic block that stops the + recursive instantiation of parameters: a parameter is a variable + that is defined in a basic block that dominates INSTANTIATE_BELOW or + a function parameter. */ tree -instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop, +instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop, tree chrec) { tree res; @@ -2301,14 +2297,14 @@ instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop, if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "(instantiate_scev \n"); - fprintf (dump_file, " (instantiation_loop = %d)\n", instantiation_loop->num); + fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index); fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num); fprintf (dump_file, " (chrec = "); print_generic_expr (dump_file, chrec, 0); fprintf (dump_file, ")\n"); } - res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, false, + res = instantiate_scev_1 (instantiate_below, evolution_loop, chrec, false, cache, 0); if (dump_file && (dump_flags & TDF_DETAILS)) @@ -2332,7 +2328,8 @@ tree resolve_mixers (struct loop *loop, tree chrec) { htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info); - tree ret = instantiate_scev_1 (loop, loop, chrec, true, cache, 0); + tree ret = instantiate_scev_1 (block_before_loop (loop), loop, chrec, true, + cache, 0); htab_delete (cache); return ret; } @@ -2677,7 +2674,6 @@ scev_initialize (void) del_scev_info, ggc_calloc, ggc_free); - already_instantiated = BITMAP_ALLOC (NULL); initialize_scalar_evolutions_analyzer (); @@ -2791,7 +2787,6 @@ scev_finalize (void) if (!scalar_evolution_info) return; htab_delete (scalar_evolution_info); - BITMAP_FREE (already_instantiated); scalar_evolution_info = NULL; } diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index 5d6d711afa9..7ba0708354f 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -29,7 +29,7 @@ extern void scev_initialize (void); extern void scev_reset (void); extern void scev_finalize (void); extern tree analyze_scalar_evolution (struct loop *, tree); -extern tree instantiate_scev (struct loop *, struct loop *, tree); +extern tree instantiate_scev (basic_block, struct loop *, tree); extern tree resolve_mixers (struct loop *, tree); extern void gather_stats_on_scev_database (void); extern void scev_analysis (void); @@ -37,6 +37,16 @@ unsigned int scev_const_prop (void); extern bool simple_iv (struct loop *, gimple, tree, affine_iv *, bool); +/* Returns the basic block preceding LOOP or ENTRY_BLOCK_PTR when the + loop is function's body. */ + +static inline basic_block +block_before_loop (loop_p loop) +{ + edge preheader = loop_preheader_edge (loop); + return (preheader ? preheader->src : ENTRY_BLOCK_PTR); +} + /* Analyze all the parameters of the chrec that were left under a symbolic form. LOOP is the loop in which symbolic names have to be analyzed and instantiated. */ @@ -44,7 +54,7 @@ extern bool simple_iv (struct loop *, gimple, tree, affine_iv *, bool); static inline tree instantiate_parameters (struct loop *loop, tree chrec) { - return instantiate_scev (loop, loop, chrec); + return instantiate_scev (block_before_loop (loop), loop, chrec); } /* Returns the loop of the polynomial chrec CHREC. */ |