diff options
| -rw-r--r-- | gcc/ChangeLog | 39 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/vect/vect-77.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/vect/vect-78.c | 4 | ||||
| -rw-r--r-- | gcc/tree-chrec.c | 139 | ||||
| -rw-r--r-- | gcc/tree-chrec.h | 10 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 3 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 91 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivopts.c | 7 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 262 | ||||
| -rw-r--r-- | gcc/tree-vrp.c | 33 |
11 files changed, 387 insertions, 207 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8496165e032..e200023d66b 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,42 @@ +2005-06-07 Sebastian Pop <pop@cri.ensmp.fr> + + PR 18403 and meta PR 21861. + * Makefile.in (tree-chrec.o): Depend on CFGLOOP_H and TREE_FLOW_H. + * tree-chrec.c: Include cfgloop.h and tree-flow.h. + (evolution_function_is_invariant_rec_p, + evolution_function_is_invariant_p): New. + (chrec_convert): Use an extra parameter AT_STMT for refining the + information that is passed down to convert_step. Integrate the + code that was in count_ev_in_wider_type. + * tree-chrec.h (count_ev_in_wider_type): Removed. + (chrec_convert): Modify its declaration. + (evolution_function_is_invariant_p): Declared. + (evolution_function_is_affine_p): Use evolution_function_is_invariant_p. + * tree-flow.h (can_count_iv_in_wider_type): Renamed convert_step. + (scev_probably_wraps_p): Declared. + * tree-scalar-evolution.c (count_ev_in_wider_type): Removed. + (follow_ssa_edge_in_rhs, interpret_rhs_modify_expr): + Use an extra parameter AT_STMT for refining the information that is + passed down to convert_step. + (follow_ssa_edge_inner_loop_phi, follow_ssa_edge, + analyze_scalar_evolution_1): Initialize AT_STMT with the current + analyzed statement. + (instantiate_parameters_1): Don't know yet how to initialize AT_STMT. + * tree-ssa-loop-ivopts.c (idx_find_step): Update the use of + can_count_iv_in_wider_type to use convert_step. + * tree-ssa-loop-niter.c (can_count_iv_in_wider_type_bound): Move + code that is independent of the loop over the known iteration + bounds to convert_step_widening, the rest is moved to + proved_non_wrapping_p. + (scev_probably_wraps_p): New. + (can_count_iv_in_wider_type): Renamed convert_step. + * tree-vrp.c (adjust_range_with_scev): Take an extra AT_STMT parameter. + Use scev_probably_wraps_p for computing init_is_max. + (vrp_visit_assignment): Pass the current analyzed statement to + adjust_range_with_scev. + (execute_vrp): Call estimate_numbers_of_iterations for refining the + information provided by scev analyzer. + 2005-06-07 Eric Christopher <echristo@redhat.com> * config/mips/predicates.md (sleu_operand): Use diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b9f0f1edf3d..9e8bbe09307 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1873,7 +1873,7 @@ tree-browser.o : tree-browser.c tree-browser.def $(CONFIG_H) $(SYSTEM_H) \ $(TM_H) coretypes.h tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h $(PARAMS_H) \ - $(DIAGNOSTIC_H) $(VARRAY_H) + $(DIAGNOSTIC_H) $(VARRAY_H) $(CFGLOOP_H) $(TREE_FLOW_H) tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \ coretypes.h $(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) \ $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) \ diff --git a/gcc/testsuite/gcc.dg/vect/vect-77.c b/gcc/testsuite/gcc.dg/vect/vect-77.c index 14da163a778..8557b298bf8 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-77.c +++ b/gcc/testsuite/gcc.dg/vect/vect-77.c @@ -39,7 +39,7 @@ int main (void) return 0; } -/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { lp64 || vect_no_align } } } } */ -/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { lp64 || vect_no_align } } } } */ +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { vect_no_align } } } } */ +/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { vect_no_align } } } } */ /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 0 "vect" } } */ /* { dg-final { cleanup-tree-dump "vect" } } */ diff --git a/gcc/testsuite/gcc.dg/vect/vect-78.c b/gcc/testsuite/gcc.dg/vect/vect-78.c index e22efcac7c6..a059f308b9c 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-78.c +++ b/gcc/testsuite/gcc.dg/vect/vect-78.c @@ -40,7 +40,7 @@ int main (void) return 0; } -/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { lp64 || vect_no_align } } } } */ -/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { lp64 || vect_no_align } } } } */ +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" { xfail { vect_no_align } } } } */ +/* { dg-final { scan-tree-dump-times "Vectorizing an unaligned access" 1 "vect" { xfail { vect_no_align } } } } */ /* { dg-final { scan-tree-dump-times "Alignment of access forced using peeling" 0 "vect" } } */ /* { dg-final { cleanup-tree-dump "vect" } } */ diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 1a7e8c8c631..ee171506140 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -32,6 +32,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "tree.h" #include "diagnostic.h" #include "varray.h" +#include "cfgloop.h" +#include "tree-flow.h" #include "tree-chrec.h" #include "tree-pass.h" #include "params.h" @@ -909,6 +911,57 @@ tree_contains_chrecs (tree expr, int *size) } } +/* Recursive helper function. */ + +static bool +evolution_function_is_invariant_rec_p (tree chrec, int loopnum) +{ + if (evolution_function_is_constant_p (chrec)) + return true; + + if (TREE_CODE (chrec) == SSA_NAME + && expr_invariant_in_loop_p (current_loops->parray[loopnum], + chrec)) + return true; + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC + && CHREC_VARIABLE (chrec) == (unsigned) loopnum) + return false; + + switch (TREE_CODE_LENGTH (TREE_CODE (chrec))) + { + case 2: + if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), + loopnum)) + return false; + + case 1: + if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), + loopnum)) + return false; + return true; + + default: + return false; + } + + return false; +} + +/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */ + +bool +evolution_function_is_invariant_p (tree chrec, int loopnum) +{ + if (evolution_function_is_constant_p (chrec)) + return true; + + if (current_loops != NULL) + return evolution_function_is_invariant_rec_p (chrec, loopnum); + + return false; +} + /* Determine whether the given tree is an affine multivariate evolution. */ @@ -1019,11 +1072,17 @@ nb_vars_in_chrec (tree chrec) -/* Convert CHREC to TYPE. The following is rule is always true: - TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE - (CHREC_RIGHT (chrec)). An example of what could happen when adding - two chrecs and the type of the CHREC_RIGHT is different than - CHREC_LEFT is: +/* Convert CHREC to TYPE. When the analyzer knows the context in + which the CHREC is built, it sets AT_STMT to the statement that + contains the definition of the analyzed variable, otherwise the + conversion is less accurate: the information is used for + determining a more accurate estimation of the number of iterations. + By default AT_STMT could be safely set to NULL_TREE. + + The following rule is always true: TREE_TYPE (chrec) == + TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)). + An example of what could happen when adding two chrecs and the type + of the CHREC_RIGHT is different than CHREC_LEFT is: {(uint) 0, +, (uchar) 10} + {(uint) 0, +, (uchar) 250} @@ -1038,11 +1097,10 @@ nb_vars_in_chrec (tree chrec) */ tree -chrec_convert (tree type, - tree chrec) +chrec_convert (tree type, tree chrec, tree at_stmt) { - tree ct; - + tree ct, res; + if (automatically_generated_chrec_p (chrec)) return chrec; @@ -1050,43 +1108,44 @@ chrec_convert (tree type, if (ct == type) return chrec; - if (TYPE_PRECISION (ct) < TYPE_PRECISION (type)) - return count_ev_in_wider_type (type, chrec); - - switch (TREE_CODE (chrec)) + if (evolution_function_is_affine_p (chrec)) { - case POLYNOMIAL_CHREC: + tree step = convert_step (current_loops->parray[CHREC_VARIABLE (chrec)], + type, CHREC_LEFT (chrec), CHREC_RIGHT (chrec), + at_stmt); + if (!step) + return fold_convert (type, chrec); + return build_polynomial_chrec (CHREC_VARIABLE (chrec), - chrec_convert (type, - CHREC_LEFT (chrec)), - chrec_convert (type, - CHREC_RIGHT (chrec))); + chrec_convert (type, CHREC_LEFT (chrec), + at_stmt), + step); + } - default: - { - tree res = fold_convert (type, chrec); + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + return chrec_dont_know; - /* Don't propagate overflows. */ - if (CONSTANT_CLASS_P (res)) - { - TREE_CONSTANT_OVERFLOW (res) = 0; - TREE_OVERFLOW (res) = 0; - } + res = fold_convert (type, chrec); - /* But reject constants that don't fit in their type after conversion. - This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the - natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, - and can cause problems later when computing niters of loops. Note - that we don't do the check before converting because we don't want - to reject conversions of negative chrecs to unsigned types. */ - if (TREE_CODE (res) == INTEGER_CST - && TREE_CODE (type) == INTEGER_TYPE - && !int_fits_type_p (res, type)) - res = chrec_dont_know; - - return res; - } + /* Don't propagate overflows. */ + if (CONSTANT_CLASS_P (res)) + { + TREE_CONSTANT_OVERFLOW (res) = 0; + TREE_OVERFLOW (res) = 0; } + + /* But reject constants that don't fit in their type after conversion. + This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the + natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, + and can cause problems later when computing niters of loops. Note + that we don't do the check before converting because we don't want + to reject conversions of negative chrecs to unsigned types. */ + if (TREE_CODE (res) == INTEGER_CST + && TREE_CODE (type) == INTEGER_TYPE + && !int_fits_type_p (res, type)) + res = chrec_dont_know; + + return res; } /* Returns the type of the chrec. */ diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index d101c9b14c7..723c8918e28 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -67,8 +67,7 @@ tree_is_chrec (tree expr) extern tree chrec_fold_plus (tree, tree, tree); extern tree chrec_fold_minus (tree, tree, tree); extern tree chrec_fold_multiply (tree, tree, tree); -extern tree chrec_convert (tree, tree); -extern tree count_ev_in_wider_type (tree, tree); +extern tree chrec_convert (tree, tree, tree); extern tree chrec_type (tree); /* Operations. */ @@ -146,6 +145,7 @@ evolution_function_is_constant_p (tree chrec) } } +extern bool evolution_function_is_invariant_p (tree, int); /* Determine whether the given tree is an affine evolution function or not. */ static inline bool @@ -157,8 +157,10 @@ evolution_function_is_affine_p (tree chrec) switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (evolution_function_is_constant_p (CHREC_LEFT (chrec)) - && evolution_function_is_constant_p (CHREC_RIGHT (chrec))) + if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), + CHREC_VARIABLE (chrec)) + && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), + CHREC_VARIABLE (chrec))) return true; else return false; diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 7d7dc00a01b..d3180196e1c 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -658,7 +658,8 @@ tree find_loop_niter (struct loop *, edge *); tree loop_niter_by_eval (struct loop *, edge); tree find_loop_niter_by_eval (struct loop *, edge *); void estimate_numbers_of_iterations (struct loops *); -tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree); +bool scev_probably_wraps_p (tree, tree, tree, tree, struct loop *, bool *); +tree convert_step (struct loop *, tree, tree, tree, tree); void free_numbers_of_iterations_estimates (struct loops *); void rewrite_into_loop_closed_ssa (bitmap, unsigned); void verify_loop_closed_ssa (void); diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 27531864c3c..49806b2e45d 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -349,33 +349,6 @@ find_var_scev_info (tree var) return &res->chrec; } -/* Tries to express CHREC in wider type TYPE. */ - -tree -count_ev_in_wider_type (tree type, tree chrec) -{ - tree base, step; - struct loop *loop; - - if (!evolution_function_is_affine_p (chrec)) - return fold_convert (type, chrec); - - base = CHREC_LEFT (chrec); - step = CHREC_RIGHT (chrec); - loop = current_loops->parray[CHREC_VARIABLE (chrec)]; - - /* TODO -- if we knew the statement at that the conversion occurs, - we could pass it to can_count_iv_in_wider_type and get a better - result. */ - step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE); - if (!step) - return fold_convert (type, chrec); - base = chrec_convert (type, base); - - return build_polynomial_chrec (CHREC_VARIABLE (chrec), - base, step); -} - /* Return true when CHREC contains symbolic names defined in LOOP_NB. */ @@ -1052,6 +1025,7 @@ static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *); static bool follow_ssa_edge_in_rhs (struct loop *loop, + tree at_stmt, tree rhs, tree halting_phi, tree *evolution_of_loop) @@ -1071,9 +1045,10 @@ follow_ssa_edge_in_rhs (struct loop *loop, { case NOP_EXPR: /* This assignment is under the form "a_1 = (cast) rhs. */ - res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi, - evolution_of_loop); - *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop); + res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0), + halting_phi, evolution_of_loop); + *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), + *evolution_of_loop, at_stmt); break; case INTEGER_CST: @@ -1107,7 +1082,7 @@ follow_ssa_edge_in_rhs (struct loop *loop, if (res) *evolution_of_loop = add_to_evolution (loop->num, - chrec_convert (type_rhs, *evolution_of_loop), + chrec_convert (type_rhs, *evolution_of_loop, at_stmt), PLUS_EXPR, rhs1); else @@ -1119,7 +1094,7 @@ follow_ssa_edge_in_rhs (struct loop *loop, if (res) *evolution_of_loop = add_to_evolution (loop->num, - chrec_convert (type_rhs, *evolution_of_loop), + chrec_convert (type_rhs, *evolution_of_loop, at_stmt), PLUS_EXPR, rhs0); } } @@ -1133,7 +1108,8 @@ follow_ssa_edge_in_rhs (struct loop *loop, evolution_of_loop); if (res) *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, + at_stmt), PLUS_EXPR, rhs1); } } @@ -1147,7 +1123,8 @@ follow_ssa_edge_in_rhs (struct loop *loop, evolution_of_loop); if (res) *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, + at_stmt), PLUS_EXPR, rhs0); } @@ -1174,7 +1151,8 @@ follow_ssa_edge_in_rhs (struct loop *loop, evolution_of_loop); if (res) *evolution_of_loop = add_to_evolution - (loop->num, chrec_convert (type_rhs, *evolution_of_loop), + (loop->num, chrec_convert (type_rhs, *evolution_of_loop, + at_stmt), MINUS_EXPR, rhs1); } else @@ -1391,7 +1369,8 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, /* Follow the edges that exit the inner loop. */ bb = PHI_ARG_EDGE (loop_phi_node, i)->src; if (!flow_bb_inside_loop_p (loop, bb)) - res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi, + res = res || follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, + arg, halting_phi, evolution_of_loop); } @@ -1404,7 +1383,7 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop, /* Otherwise, compute the overall effect of the inner loop. */ ev = compute_overall_effect_of_inner_loop (loop, ev); - return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi, + return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi, evolution_of_loop); } @@ -1456,7 +1435,7 @@ follow_ssa_edge (struct loop *loop, return false; case MODIFY_EXPR: - return follow_ssa_edge_in_rhs (loop, + return follow_ssa_edge_in_rhs (loop, def, TREE_OPERAND (def, 1), halting_phi, evolution_of_loop); @@ -1665,14 +1644,14 @@ interpret_condition_phi (struct loop *loop, tree condition_phi) analyze the effect of an inner loop: see interpret_loop_phi. */ static tree -interpret_rhs_modify_expr (struct loop *loop, +interpret_rhs_modify_expr (struct loop *loop, tree at_stmt, tree opnd1, tree type) { tree res, opnd10, opnd11, chrec10, chrec11; - + if (is_gimple_min_invariant (opnd1)) - return chrec_convert (type, opnd1); - + return chrec_convert (type, opnd1, at_stmt); + switch (TREE_CODE (opnd1)) { case PLUS_EXPR: @@ -1680,8 +1659,8 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_plus (type, chrec10, chrec11); break; @@ -1690,15 +1669,15 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_minus (type, chrec10, chrec11); break; case NEGATE_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); chrec10 = analyze_scalar_evolution (loop, opnd10); - chrec10 = chrec_convert (type, chrec10); + chrec10 = chrec_convert (type, chrec10, at_stmt); res = chrec_fold_minus (type, build_int_cst (type, 0), chrec10); break; @@ -1707,25 +1686,27 @@ interpret_rhs_modify_expr (struct loop *loop, opnd11 = TREE_OPERAND (opnd1, 1); chrec10 = analyze_scalar_evolution (loop, opnd10); chrec11 = analyze_scalar_evolution (loop, opnd11); - chrec10 = chrec_convert (type, chrec10); - chrec11 = chrec_convert (type, chrec11); + chrec10 = chrec_convert (type, chrec10, at_stmt); + chrec11 = chrec_convert (type, chrec11, at_stmt); res = chrec_fold_multiply (type, chrec10, chrec11); break; case SSA_NAME: - res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1)); + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1), + at_stmt); break; case ASSERT_EXPR: opnd10 = ASSERT_EXPR_VAR (opnd1); - res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10)); + res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10), + at_stmt); break; case NOP_EXPR: case CONVERT_EXPR: opnd10 = TREE_OPERAND (opnd1, 0); chrec10 = analyze_scalar_evolution (loop, opnd10); - res = chrec_convert (type, chrec10); + res = chrec_convert (type, chrec10, at_stmt); break; default: @@ -1775,7 +1756,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) return chrec_dont_know; if (TREE_CODE (var) != SSA_NAME) - return interpret_rhs_modify_expr (loop, var, type); + return interpret_rhs_modify_expr (loop, NULL_TREE, var, type); def = SSA_NAME_DEF_STMT (var); bb = bb_for_stmt (def); @@ -1809,7 +1790,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res) switch (TREE_CODE (def)) { case MODIFY_EXPR: - res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type); + res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type); break; case PHI_NODE: @@ -2093,7 +2074,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec, if (op0 == TREE_OPERAND (chrec, 0)) return chrec; - return chrec_convert (TREE_TYPE (chrec), op0); + return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE); case SCEV_NOT_KNOWN: return chrec_dont_know; diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 716d113e75e..ed1072243ae 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -1442,11 +1442,8 @@ idx_find_step (tree base, tree *idx, void *data) /* The step for pointer arithmetics already is 1 byte. */ step = build_int_cst (sizetype, 1); - if (TYPE_PRECISION (TREE_TYPE (iv->base)) < TYPE_PRECISION (sizetype)) - iv_step = can_count_iv_in_wider_type (dta->ivopts_data->current_loop, - sizetype, iv->base, iv->step, dta->stmt); - else - iv_step = fold_convert (sizetype, iv->step); + iv_step = convert_step (dta->ivopts_data->current_loop, + sizetype, iv->base, iv->step, dta->stmt); if (!iv_step) { diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 78f14e9accf..40f8e4525aa 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -1445,13 +1445,18 @@ stmt_dominates_stmt_p (tree s1, tree s2) return dominated_by_p (CDI_DOMINATORS, bb2, bb1); } -/* Checks whether it is correct to count the induction variable BASE + STEP * I - at AT_STMT in wider TYPE, using the fact that statement OF is executed at - most BOUND times in the loop. If it is possible, return the value of step - of the induction variable in the TYPE, otherwise return NULL_TREE. +/* Return true when it is possible to prove that the induction + variable does not wrap: vary outside the type specified bounds. + Checks whether BOUND < VALID_NITER that means in the context of iv + conversion that all the iterations in the loop are safe: not + producing wraps. + + The statement NITER_BOUND->AT_STMT is executed at most + NITER_BOUND->BOUND times in the loop. - ADDITIONAL is the additional condition recorded for operands of the bound. - This is useful in the following case, created by loop header copying: + NITER_BOUND->ADDITIONAL is the additional condition recorded for + operands of the bound. This is useful in the following case, + created by loop header copying: i = 0; if (n > 0) @@ -1465,108 +1470,211 @@ stmt_dominates_stmt_p (tree s1, tree s2) assumption "n > 0" says us that the value of the number of iterations is at most MAX_TYPE - 1 (without this assumption, it might overflow). */ -static tree -can_count_iv_in_wider_type_bound (tree type, tree base, tree step, - tree at_stmt, - tree bound, - tree additional, - tree of) +static bool +proved_non_wrapping_p (tree at_stmt, + struct nb_iter_bound *niter_bound, + tree new_type, + tree valid_niter) { - tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs; - tree valid_niter, extreme, unsigned_type, delta, bound_type; tree cond; + tree bound = niter_bound->bound; + + if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound))) + bound = fold_convert (unsigned_type_for (new_type), bound); + else + valid_niter = fold_convert (TREE_TYPE (bound), valid_niter); + + /* After the statement niter_bound->at_stmt we know that anything is + executed at most BOUND times. */ + if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt)) + cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound); + + /* Before the statement niter_bound->at_stmt we know that anything + is executed at most BOUND + 1 times. */ + else + cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound); + + if (nonzero_p (cond)) + return true; + + /* Try taking additional conditions into account. */ + cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, + invert_truthvalue (niter_bound->additional), + cond); + + if (nonzero_p (cond)) + return true; - b = fold_convert (type, base); - bplusstep = fold_convert (type, - fold_build2 (PLUS_EXPR, inner_type, base, step)); - new_step = fold_build2 (MINUS_EXPR, type, bplusstep, b); - if (TREE_CODE (new_step) != INTEGER_CST) + return false; +} + +/* Checks whether it is correct to count the induction variable BASE + + STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on + numbers of iterations of a LOOP. If it is possible, return the + value of step of the induction variable in the NEW_TYPE, otherwise + return NULL_TREE. */ + +static tree +convert_step_widening (struct loop *loop, tree new_type, tree base, tree step, + tree at_stmt) +{ + struct nb_iter_bound *bound; + tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type; + tree delta, step_abs; + tree unsigned_type, valid_niter; + + /* Compute the new step. For example, {(uchar) 100, +, (uchar) 240} + is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to + keep the values of the induction variable unchanged: 100, 84, 68, + ... + + Another example is: (uint) {(uchar)100, +, (uchar)3} is converted + to {(uint)100, +, (uint)3}. + + Before returning the new step, verify that the number of + iterations is less than DELTA / STEP_ABS (i.e. in the previous + example (256 - 100) / 3) such that the iv does not wrap (in which + case the operations are too difficult to be represented and + handled: the values of the iv should be taken modulo 256 in the + wider type; this is not implemented). */ + base_in_new_type = fold_convert (new_type, base); + base_plus_step_in_new_type = + fold_convert (new_type, + fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step)); + step_in_new_type = fold_build2 (MINUS_EXPR, new_type, + base_plus_step_in_new_type, + base_in_new_type); + + if (TREE_CODE (step_in_new_type) != INTEGER_CST) return NULL_TREE; - switch (compare_trees (bplusstep, b)) + switch (compare_trees (base_plus_step_in_new_type, base_in_new_type)) { case -1: - extreme = upper_bound_in_type (type, inner_type); - delta = fold_build2 (MINUS_EXPR, type, extreme, b); - new_step_abs = new_step; - break; + { + tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base)); + delta = fold_build2 (MINUS_EXPR, new_type, extreme, + base_in_new_type); + step_abs = step_in_new_type; + break; + } case 1: - extreme = lower_bound_in_type (type, inner_type); - new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step); - delta = fold_build2 (MINUS_EXPR, type, b, extreme); - break; + { + tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base)); + delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type, + extreme); + step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type); + break; + } case 0: - return new_step; + return step_in_new_type; default: return NULL_TREE; } - unsigned_type = unsigned_type_for (type); + unsigned_type = unsigned_type_for (new_type); delta = fold_convert (unsigned_type, delta); - new_step_abs = fold_convert (unsigned_type, new_step_abs); + step_abs = fold_convert (unsigned_type, step_abs); valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, - delta, new_step_abs); + delta, step_abs); - bound_type = TREE_TYPE (bound); - if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type)) - bound = fold_convert (unsigned_type, bound); - else - valid_niter = fold_convert (bound_type, valid_niter); - - if (at_stmt && stmt_dominates_stmt_p (of, at_stmt)) - { - /* After the statement OF we know that anything is executed at most - BOUND times. */ - cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound); - } - else + for (bound = loop->bounds; bound; bound = bound->next) + if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter)) + return step_in_new_type; + + /* Fail when the loop has no bound estimations, or when no bound can + be used for verifying the conversion. */ + return NULL_TREE; +} + +/* Return false only when the induction variable BASE + STEP * I is + known to not overflow: i.e. when the number of iterations is small + enough with respect to the step and initial condition in order to + keep the evolution confined in TYPEs bounds. Return true when the + iv is known to overflow or when the property is not computable. + + Initialize INIT_IS_MAX to true when the evolution goes from + INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case, not + defined when the function returns true. */ + +bool +scev_probably_wraps_p (tree type, tree base, tree step, + tree at_stmt, struct loop *loop, + bool *init_is_max) +{ + struct nb_iter_bound *bound; + tree delta, step_abs; + tree unsigned_type, valid_niter; + tree base_plus_step = fold_build2 (PLUS_EXPR, type, base, step); + + switch (compare_trees (base_plus_step, base)) { - /* Before the statement OF we know that anything is executed at most - BOUND + 1 times. */ - cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound); + case -1: + { + tree extreme = upper_bound_in_type (type, TREE_TYPE (base)); + delta = fold_build2 (MINUS_EXPR, type, extreme, base); + step_abs = step; + *init_is_max = false; + break; + } + + case 1: + { + tree extreme = lower_bound_in_type (type, TREE_TYPE (base)); + delta = fold_build2 (MINUS_EXPR, type, base, extreme); + step_abs = fold_build1 (NEGATE_EXPR, type, step); + *init_is_max = true; + break; + } + + case 0: + /* This means step is equal to 0. This should not happen. It + could happen in convert step, but not here. Safely answer + don't know as in the default case. */ + + default: + return true; } - if (nonzero_p (cond)) - return new_step; + /* After having set INIT_IS_MAX, we can return false: when not using + wrapping arithmetic, signed types don't wrap. */ + if (!flag_wrapv && !TYPE_UNSIGNED (type)) + return false; - /* Try taking additional conditions into account. */ - cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, - invert_truthvalue (additional), - cond); - if (nonzero_p (cond)) - return new_step; + unsigned_type = unsigned_type_for (type); + delta = fold_convert (unsigned_type, delta); + step_abs = fold_convert (unsigned_type, step_abs); + valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); - return NULL_TREE; + for (bound = loop->bounds; bound; bound = bound->next) + if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) + return false; + + /* At this point we still don't have a proof that the iv does not + overflow: give up. */ + return true; } -/* Checks whether it is correct to count the induction variable BASE + STEP * I - at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a - LOOP. If it is possible, return the value of step of the induction variable - in the TYPE, otherwise return NULL_TREE. */ +/* Return the conversion to NEW_TYPE of the STEP of an induction + variable BASE + STEP * I at AT_STMT. */ tree -can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step, - tree at_stmt) +convert_step (struct loop *loop, tree new_type, tree base, tree step, + tree at_stmt) { - struct nb_iter_bound *bound; - tree new_step; + tree base_type = TREE_TYPE (base); - for (bound = loop->bounds; bound; bound = bound->next) - { - new_step = can_count_iv_in_wider_type_bound (type, base, step, - at_stmt, - bound->bound, - bound->additional, - bound->at_stmt); - - if (new_step) - return new_step; - } + /* When not using wrapping arithmetic, signed types don't wrap. */ + if (!flag_wrapv && !TYPE_UNSIGNED (base_type)) + return fold_convert (new_type, step); - return NULL_TREE; + if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type)) + return convert_step_widening (loop, new_type, base, step, at_stmt); + + return fold_convert (new_type, step); } /* Frees the information on upper bounds on numbers of iterations of LOOP. */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 373e8d93135..b42da82612a 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -1427,13 +1427,13 @@ extract_range_from_expr (value_range_t *vr, tree expr) set_value_range_to_varying (vr); } - -/* Given a range VR, a loop L and a variable VAR, determine whether it +/* Given a range VR, a LOOP and a variable VAR, determine whether it would be profitable to adjust VR using scalar evolution information for VAR. If so, update VR with the new limits. */ static void -adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var) +adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt, + tree var) { tree init, step, chrec; bool init_is_max; @@ -1443,7 +1443,7 @@ adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var) if (vr->type == VR_ANTI_RANGE) return; - chrec = analyze_scalar_evolution (l, var); + chrec = analyze_scalar_evolution (loop, var); if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) return; @@ -1455,22 +1455,12 @@ adjust_range_with_scev (value_range_t *vr, struct loop *l, tree var) if (!is_gimple_min_invariant (step)) return; - /* FIXME. When dealing with unsigned types, - analyze_scalar_evolution sets STEP to very large unsigned values - when the evolution goes backwards. This confuses this analysis - because we think that INIT is the smallest value that the range - can take, instead of the largest. Ignore these chrecs for now. */ - if (INTEGRAL_TYPE_P (TREE_TYPE (step)) && TYPE_UNSIGNED (TREE_TYPE (step))) - return; - - /* Do not adjust ranges when using wrapping arithmetic. */ - if (flag_wrapv) + /* Do not adjust ranges when chrec may wrap. */ + if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt, + cfg_loops->parray[CHREC_VARIABLE (chrec)], + &init_is_max)) return; - /* If STEP is negative, then INIT is the maximum value the range - will take. Otherwise, INIT is the minimum value. */ - init_is_max = (tree_int_cst_sgn (step) < 0); - if (!POINTER_TYPE_P (TREE_TYPE (init)) && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)) { @@ -2772,7 +2762,7 @@ vrp_visit_assignment (tree stmt, tree *output_p) else about the range of LHS by examining scalar evolution information. */ if (cfg_loops && (l = loop_containing_stmt (stmt))) - adjust_range_with_scev (&new_vr, l, lhs); + adjust_range_with_scev (&new_vr, l, stmt, lhs); if (update_value_range (lhs, &new_vr)) { @@ -3519,7 +3509,10 @@ execute_vrp (void) cfg_loops = loop_optimizer_init (NULL); if (cfg_loops) - scev_initialize (cfg_loops); + { + scev_initialize (cfg_loops); + estimate_numbers_of_iterations (cfg_loops); + } vrp_initialize (); ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); |