diff options
| author | Zdenek Dvorak <dvorakz@suse.cz> | 2005-10-05 11:27:54 +0000 |
|---|---|---|
| committer | Zdenek Dvorak <dvorakz@suse.cz> | 2005-10-05 11:27:54 +0000 |
| commit | 202b9afc2cfdd2201d6bb0deb002333238bd77d8 (patch) | |
| tree | a150ace9145fdaeedc3b4c60901ee6c5d09c8414 | |
| parent | 9dbbf46eb38edb9d89c237c6f403930942d266e0 (diff) | |
* Makefile.in (tree-ssa-loop-niter.o): Add tree-affine.h dependency.
* cfgloop.h (struct nb_iter_bound): Removed.
(struct loop): Fields estimated_nb_iterations and bounds removed,
fields niter_bounds_state, max_nb_iterations, is_finite and
iv_no_overflow added.
(record_estimate): Declaration removed.
* hwint.h (double_int): Declaration moved from tree-affine.h.
* tree-affine.c (restrict_cst_to_precision, double_int_fits_in_hwi_p,
double_int_negative_p, double_int_to_hwi, double_int_mul,
double_int_add, double_int_negate): Take mask instead of affine
combination as an argument.
(double_int_fits_in_unsigned_hwi_p, double_int_to_unsigned_hwi,
double_int_divide, double_int_fits_to_type_p, double_int_smaller_p,
double_int_split_digit, dump_double_int): New functions.
(affine_combination_set_mask): Replaced with ...
(double_int_mask): ... new function.
(aff_combination_zero, aff_combination_const, aff_combination_scale,
aff_combination_add_elt, aff_combination_add, aff_combination_convert,
add_elt_to_tree, aff_combination_to_tree): Use new calling conventions
of double_int functions.
* tree-affine.h (double_int): Moved to hwint.h.
(double_int_fits_in_hwi_p, double_int_to_hwi, double_int_mul,
double_int_add, double_int_negate, double_int_negative_p): Declaration
changed.
(double_int_fits_to_type_p, double_int_fits_in_unsigned_hwi_p,
double_int_to_unsigned_hwi, double_int_divide, double_int_smaller_p,
dump_double_int, double_int_mask): Declare.
(double_int_all): New inline function.
(double_int_minus_one_p): Take mask instead of affine combination as
an argument.
* tree-data-ref.c (estimate_niter_from_size_of_data,
analyze_array_indexes): Use array bounds instead of type size.
(compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine):
Use get_max_loop_niter.
* tree-flow.h (struct tree_niter_desc): Removed additional_info field.
(select_condition_shape): Declaration changed.
(loop_iterations_at_most_p, condition_holds_in_loop_p,
get_max_loop_niter, record_niter_bound, record_nonwrapping_iv): Declare.
* tree-ssa-address.c (most_expensive_mult_to_index): Use new calling
conventions of double_int functions.
* tree-ssa-loop-endcond.c (modify_to_compare_with_zero,
may_wrap_around_type_range_p, select_condition_shape,
endcond_candidate_cost, best_endcond_candidate_cost): Use information
about bounds on # of iterations.
(try_removing_addition_from_bound): Removed.
* tree-ssa-loop-ivopts.c (decl_rtl_to_reset): Removed.
(tree_ssa_iv_optimize_init, free_loop_data,
tree_ssa_iv_optimize_finalize): Do not set decl_rtl_to_reset.
(produce_memory_decl_rtl, prepare_decl_rtl, computation_cost): Removed.
(integer_cost, fixed_address_cost): New functions.
(force_expr_to_var_cost): Do not use computation_cost.
(niter_for_exit): Expand simple operations in # of iterations.
(get_computation_aff, (aff_combination_cost,
aff_combination_cost_address, get_computation_cost_at): Use new calling
conventions of double_int functions.
(may_eliminate_iv): Pass loop to select_condition_shape.
* tree-ssa-loop-niter.c: Include tree-affine.h.
(number_of_iterations_special, simplify_using_initial_conditions,
number_of_iterations_exit): Do not set additional_info field.
(struct iv_no_overflow): New.
(record_estimate, compute_estimated_nb_iterations): Replaced by ...
(record_niter_bound, record_nonwrapping_iv): ... new functions.
(nonnegative_in_loop_p, derive_integral_bound, nonwrapping_due_to,
in_nonwrapping_ivs_list_p): New functions.
(infer_loop_bounds_from_array): Use record_nonwrapping_iv.
(infer_loop_bounds_from_signedness): New function.
(infer_loop_bounds_from_undefined): Split some code to
infer_loop_bounds_from_signedness.
(estimate_numbers_of_iterations_loop): Set state of # of iterations
estimation.
(stmt_dominates_stmt_p): Removed.
(proved_non_wrapping_p): Replaced with ...
(loop_iterations_at_most_p): ... new function.
(convert_step_widening, scev_probably_wraps_p): Use
in_nonwrapping_ivs_list_p and loop_iterations_at_most_p.
(free_numbers_of_iterations_estimates_loop, substitute_in_loop_info):
Modified.
(condition_holds_in_loop_p, get_max_loop_niter): New functions.
* testsuite/gcc.dg/tree-ssa/loop-13.c: New test.
git-svn-id: https://gcc.gnu.org/svn/gcc/branches/killloop-branch@104987 138bc75d-0d04-0410-961f-82ee72b054a4
| -rw-r--r-- | gcc/ChangeLog.killloop | 83 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/cfgloop.h | 39 | ||||
| -rw-r--r-- | gcc/hwint.h | 7 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/loop-13.c | 58 | ||||
| -rw-r--r-- | gcc/tree-affine.c | 201 | ||||
| -rw-r--r-- | gcc/tree-affine.h | 40 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 176 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 20 | ||||
| -rw-r--r-- | gcc/tree-ssa-address.c | 6 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-endcond.c | 164 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivopts.c | 310 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 740 |
13 files changed, 1093 insertions, 753 deletions
diff --git a/gcc/ChangeLog.killloop b/gcc/ChangeLog.killloop index 7428bc3edaa..835c5bb6cc2 100644 --- a/gcc/ChangeLog.killloop +++ b/gcc/ChangeLog.killloop @@ -1,3 +1,86 @@ +2005-10-05 Zdenek Dvorak <dvorakz@suse.cz> + + * Makefile.in (tree-ssa-loop-niter.o): Add tree-affine.h dependency. + * cfgloop.h (struct nb_iter_bound): Removed. + (struct loop): Fields estimated_nb_iterations and bounds removed, + fields niter_bounds_state, max_nb_iterations, is_finite and + iv_no_overflow added. + (record_estimate): Declaration removed. + * hwint.h (double_int): Declaration moved from tree-affine.h. + * tree-affine.c (restrict_cst_to_precision, double_int_fits_in_hwi_p, + double_int_negative_p, double_int_to_hwi, double_int_mul, + double_int_add, double_int_negate): Take mask instead of affine + combination as an argument. + (double_int_fits_in_unsigned_hwi_p, double_int_to_unsigned_hwi, + double_int_divide, double_int_fits_to_type_p, double_int_smaller_p, + double_int_split_digit, dump_double_int): New functions. + (affine_combination_set_mask): Replaced with ... + (double_int_mask): ... new function. + (aff_combination_zero, aff_combination_const, aff_combination_scale, + aff_combination_add_elt, aff_combination_add, aff_combination_convert, + add_elt_to_tree, aff_combination_to_tree): Use new calling conventions + of double_int functions. + * tree-affine.h (double_int): Moved to hwint.h. + (double_int_fits_in_hwi_p, double_int_to_hwi, double_int_mul, + double_int_add, double_int_negate, double_int_negative_p): Declaration + changed. + (double_int_fits_to_type_p, double_int_fits_in_unsigned_hwi_p, + double_int_to_unsigned_hwi, double_int_divide, double_int_smaller_p, + dump_double_int, double_int_mask): Declare. + (double_int_all): New inline function. + (double_int_minus_one_p): Take mask instead of affine combination as + an argument. + * tree-data-ref.c (estimate_niter_from_size_of_data, + analyze_array_indexes): Use array bounds instead of type size. + (compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine): + Use get_max_loop_niter. + * tree-flow.h (struct tree_niter_desc): Removed additional_info field. + (select_condition_shape): Declaration changed. + (loop_iterations_at_most_p, condition_holds_in_loop_p, + get_max_loop_niter, record_niter_bound, record_nonwrapping_iv): Declare. + * tree-ssa-address.c (most_expensive_mult_to_index): Use new calling + conventions of double_int functions. + * tree-ssa-loop-endcond.c (modify_to_compare_with_zero, + may_wrap_around_type_range_p, select_condition_shape, + endcond_candidate_cost, best_endcond_candidate_cost): Use information + about bounds on # of iterations. + (try_removing_addition_from_bound): Removed. + * tree-ssa-loop-ivopts.c (decl_rtl_to_reset): Removed. + (tree_ssa_iv_optimize_init, free_loop_data, + tree_ssa_iv_optimize_finalize): Do not set decl_rtl_to_reset. + (produce_memory_decl_rtl, prepare_decl_rtl, computation_cost): Removed. + (integer_cost, fixed_address_cost): New functions. + (force_expr_to_var_cost): Do not use computation_cost. + (niter_for_exit): Expand simple operations in # of iterations. + (get_computation_aff, (aff_combination_cost, + aff_combination_cost_address, get_computation_cost_at): Use new calling + conventions of double_int functions. + (may_eliminate_iv): Pass loop to select_condition_shape. + * tree-ssa-loop-niter.c: Include tree-affine.h. + (number_of_iterations_special, simplify_using_initial_conditions, + number_of_iterations_exit): Do not set additional_info field. + (struct iv_no_overflow): New. + (record_estimate, compute_estimated_nb_iterations): Replaced by ... + (record_niter_bound, record_nonwrapping_iv): ... new functions. + (nonnegative_in_loop_p, derive_integral_bound, nonwrapping_due_to, + in_nonwrapping_ivs_list_p): New functions. + (infer_loop_bounds_from_array): Use record_nonwrapping_iv. + (infer_loop_bounds_from_signedness): New function. + (infer_loop_bounds_from_undefined): Split some code to + infer_loop_bounds_from_signedness. + (estimate_numbers_of_iterations_loop): Set state of # of iterations + estimation. + (stmt_dominates_stmt_p): Removed. + (proved_non_wrapping_p): Replaced with ... + (loop_iterations_at_most_p): ... new function. + (convert_step_widening, scev_probably_wraps_p): Use + in_nonwrapping_ivs_list_p and loop_iterations_at_most_p. + (free_numbers_of_iterations_estimates_loop, substitute_in_loop_info): + Modified. + (condition_holds_in_loop_p, get_max_loop_niter): New functions. + + * testsuite/gcc.dg/tree-ssa/loop-13.c: New test. + 2005-09-20 Zdenek Dvorak <dvorakz@suse.cz> * Makefile.in (loop-iv.o): Add HASHTAB_H dependency. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 28247b04639..733d7cb8ab5 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1880,7 +1880,7 @@ tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \ tree-inline.h output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ $(FLAGS_H) tree-pass.h $(SCEV_H) $(TREE_DATA_REF_H) $(BASIC_BLOCK_H) \ - $(GGC_H) hard-reg-set.h tree-chrec.h intl.h + $(GGC_H) hard-reg-set.h tree-chrec.h intl.h tree-affine.h tree-ssa-loop-ivcanon.o : tree-ssa-loop-ivcanon.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \ tree-inline.h output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index f56fd3f2854..5a8cd2d5167 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -43,19 +43,9 @@ struct lpt_decision unsigned times; }; -/* The structure describing a bound on number of iterations of a loop. */ +/* The structure describing an induction variable that does not overflow. */ -struct nb_iter_bound -{ - tree bound; /* The expression whose value is an upper bound on the - number of executions of anything after ... */ - tree at_stmt; /* ... this statement during one execution of loop. */ - tree additional; /* A conjunction of conditions the operands of BOUND - satisfy. The additional information about the value - of the bound may be derived from it. */ - struct nb_iter_bound *next; - /* The next bound in a list. */ -}; +struct iv_no_overflow; /* Structure to hold information for each natural loop. */ struct loop @@ -151,19 +141,31 @@ struct loop loops nested inside it. */ int exit_count; - /* The probable number of times the loop is executed at runtime. + /* The number of times the loop is executed at runtime. This is an INTEGER_CST or an expression containing symbolic names. Don't access this field directly: number_of_iterations_in_loop computes and caches the computed information in this field. */ tree nb_iterations; - /* An INTEGER_CST estimation of the number of iterations. NULL_TREE - if there is no estimation. */ - tree estimated_nb_iterations; + /* State of the estimate on number of iterations of the loop. */ + enum + { + NBS_NONE, /* No estimate available. */ + NBS_RECORDING, /* Currently determining the estimate. */ + NBS_READY /* The estimate is recorded. */ + } niter_bounds_state; + + /* An upper bound on the number of iterations. */ + double_int max_nb_iterations; - /* Upper bound on number of iterations of a loop. */ - struct nb_iter_bound *bounds; + /* True if the estimates on number of iterations exclude the case + that the loop is infinite. */ + bool is_finite; + + /* Information about induction variables that do not overflow in the + loop. */ + struct iv_no_overflow *iv_no_overflow; /* If not NULL, loop has just single exit edge stored here (edges to the EXIT_BLOCK_PTR do not count. */ @@ -452,7 +454,6 @@ enum extern void unroll_and_peel_loops (struct loops *, int); extern void doloop_optimize_loops (struct loops *); extern void move_loop_invariants (struct loops *); -extern void record_estimate (struct loop *, tree, tree, tree); /* Old loop optimizer interface. */ diff --git a/gcc/hwint.h b/gcc/hwint.h index 9b28a3ada07..51eab6eb455 100644 --- a/gcc/hwint.h +++ b/gcc/hwint.h @@ -147,4 +147,11 @@ extern char sizeof_long_long_must_be_8[sizeof(long long) == 8 ? 1 : -1]; # define HOST_BITS_PER_WIDEST_FAST_INT HOST_BITS_PER_LONG #endif +/* A structure containing a large integer. */ + +typedef struct +{ + unsigned HOST_WIDE_INT low, high; +} double_int; + #endif /* ! GCC_HWINT_H */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-13.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-13.c new file mode 100644 index 00000000000..f97a3ef1dda --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-13.c @@ -0,0 +1,58 @@ +/* A test for ending condition selection. */ + +/* { dg-options "-O2 -fdump-tree-vars" } */ + +void foo(int); +void bar(void); + +void xxx1(void) +{ + int i; + + /* i != 100 */ + for (i = 0; i < 100; i++) + foo (i); +} + +void xxx2(int n) +{ + int i; + + /* n > i */ + for (i = 0; i < n; i++) + foo (i); +} + +void xxx3(int n) +{ + int i; + + /* i >= 0 */ + for (i = 0; i < n; i++) + foo (n - i - 1); +} + +void xxx4(int n) +{ + int i; + + /* i != 0 */ + for (i = 0; i < n; i++) + foo (n - i); +} + +void xxx5(int n) +{ + int i; + + /* i != 0 */ + for (i = 0; i < n; i++) + bar (); +} + +/* { dg-final { scan-tree-dump-times "!= 100" 1 "vars" } } */ +/* { dg-final { scan-tree-dump-times "!= 0" 2 "vars" } } */ +/* { dg-final { scan-tree-dump-times "n > i" 1 "vars" } } */ +/* { dg-final { scan-tree-dump-times ">= 0" 1 "vars" } } */ + +/* { dg-final { cleanup-tree-dump "vars" } } */ diff --git a/gcc/tree-affine.c b/gcc/tree-affine.c index aab9dae6e1c..dac60be177f 100644 --- a/gcc/tree-affine.c +++ b/gcc/tree-affine.c @@ -34,51 +34,70 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA /* Restricts constant CST according to precision of combination COMB. */ static inline double_int -restrict_cst_to_precision (aff_tree *comb, double_int cst) +restrict_cst_to_precision (double_int mask, double_int cst) { double_int r; - r.low = cst.low & comb->mask.low; - r.high = cst.high & comb->mask.high; + r.low = cst.low & mask.low; + r.high = cst.high & mask.high; return r; } /* Returns true if X fits in HOST_WIDE_INT, with respect to precision - of COMB. */ + of MASK. */ bool -double_int_fits_in_hwi_p (aff_tree *comb, double_int x) +double_int_fits_in_hwi_p (double_int mask, double_int x) { - return x.high == comb->mask.high; + if (double_int_negative_p (mask, x)) + return x.high == mask.high; + else + return x.high == 0 && (HOST_WIDE_INT) x.low >= 0; } -/* Returns true if SCALE is negative in precision of COMB. */ +/* Returns true if X fits in unsigned HOST_WIDE_INT. */ bool -double_int_negative_p (aff_tree *comb, double_int scale) +double_int_fits_in_unsigned_hwi_p (double_int x) { - if (comb->mask.high) - return (scale.high & ~(comb->mask.high >> 1)) != 0; + return x.high == 0; +} + +/* Returns true if SCALE is negative in precision of MASK. */ + +bool +double_int_negative_p (double_int mask, double_int scale) +{ + if (mask.high) + return (scale.high & ~(mask.high >> 1)) != 0; else - return (scale.low & ~(comb->mask.low >> 1)) != 0; + return (scale.low & ~(mask.low >> 1)) != 0; } -/* Returns value of X with respect to precision of COMB. */ +/* Returns value of X with respect to precision of MASK. */ HOST_WIDE_INT -double_int_to_hwi (aff_tree *comb, double_int x) +double_int_to_hwi (double_int mask, double_int x) { - if (comb->mask.high || !double_int_negative_p (comb, x)) + if (mask.high || !double_int_negative_p (mask, x)) return x.low; else - return x.low | ~comb->mask.low; + return x.low | ~mask.low; } -/* Returns A * B, truncated so that it fits COMB. */ +/* Returns value of X. */ + +unsigned HOST_WIDE_INT +double_int_to_unsigned_hwi (double_int x) +{ + return x.low; +} + +/* Returns A * B, truncated so that it fits MASK. */ double_int -double_int_mul (aff_tree *comb, double_int a, double_int b) +double_int_mul (double_int mask, double_int a, double_int b) { unsigned HOST_WIDE_INT lo; HOST_WIDE_INT hi; @@ -88,13 +107,13 @@ double_int_mul (aff_tree *comb, double_int a, double_int b) ret.low = lo; ret.high = hi; - return restrict_cst_to_precision (comb, ret); + return restrict_cst_to_precision (mask, ret); } -/* Returns A + B, truncated so that it fits COMB. */ +/* Returns A + B, truncated so that it fits MASK. */ double_int -double_int_add (aff_tree *comb, double_int a, double_int b) +double_int_add (double_int mask, double_int a, double_int b) { unsigned HOST_WIDE_INT lo; HOST_WIDE_INT hi; @@ -104,13 +123,13 @@ double_int_add (aff_tree *comb, double_int a, double_int b) ret.low = lo; ret.high = hi; - return restrict_cst_to_precision (comb, ret); + return restrict_cst_to_precision (mask, ret); } -/* Returns -A, truncated so that it fits COMB. */ +/* Returns -A, truncated so that it fits MASK. */ double_int -double_int_negate (aff_tree *comb, double_int a) +double_int_negate (double_int mask, double_int a) { unsigned HOST_WIDE_INT lo; HOST_WIDE_INT hi; @@ -120,9 +139,25 @@ double_int_negate (aff_tree *comb, double_int a) ret.low = lo; ret.high = hi; - return restrict_cst_to_precision (comb, ret); + return restrict_cst_to_precision (mask, ret); } +/* Returns A / B (computed as unsigned, rounded down). */ + +double_int +double_int_divide (double_int a, double_int b) +{ + unsigned HOST_WIDE_INT lo, rem_lo; + HOST_WIDE_INT hi, rem_hi; + double_int ret; + + div_and_round_double (FLOOR_DIV_EXPR, true, a.low, a.high, b.low, b.high, + &lo, &hi, &rem_lo, &rem_hi); + ret.low = lo; + ret.high = hi; + + return ret; +} /* Constructs tree in type TYPE from double_int CST. */ tree @@ -153,24 +188,94 @@ double_int_to_tree (tree type, double_int cst) return build_int_cst_wide (type, lo, hi); } -/* Initializes mask of COMB according to its type. */ +/* Returns true if VAL is smaller or equal to the maximal value + representable in TYPE. */ -static void -affine_combination_set_mask (aff_tree *comb) +bool +double_int_fits_to_type_p (tree type, double_int val) +{ + unsigned prec = TYPE_PRECISION (type); + double_int mask = double_int_mask (TYPE_UNSIGNED (type) ? prec : prec - 1); + + return (((val.low & mask.low) == val.low) + && ((val.high & mask.high) == val.high)); +} + +/* Returns true if A < B, unsigned comparison. */ + +bool +double_int_smaller_p (double_int a, double_int b) +{ + if (a.high < b.high) + return true; + if (a.high > b.high) + return false; + return a.low < b.low; +} + +/* Splits last digit of *X in BASE and returns it. */ + +static unsigned +double_int_split_digit (double_int *x, unsigned base) +{ + unsigned HOST_WIDE_INT resl, reml; + HOST_WIDE_INT resh, remh; + + div_and_round_double (FLOOR_DIV_EXPR, true, x->low, x->high, base, 0, + &resl, &resh, &reml, &remh); + x->high = resh; + x->low = resl; + + return reml; +} + +/* Dumps X (in precision MASK) to FILE. If SIGN is true, X is considered to + be signed. */ + +void +dump_double_int (FILE *file, double_int mask, double_int x, bool sign) { - unsigned prec = TYPE_PRECISION (comb->type); + unsigned digits[100], n; + int i; + + if (double_int_zero_p (x)) + { + fprintf (file, "0"); + return; + } + + if (sign && double_int_negative_p (mask, x)) + { + fprintf (file, "-"); + x = double_int_negate (mask, x); + } + + for (n = 0; !double_int_zero_p (x); n++) + digits[n] = double_int_split_digit (&x, 10); + for (i = n - 1; i >= 0; i--) + fprintf (file, "%u", digits[i]); +} + +/* Returns a MASK for PREC bytes. */ + +double_int +double_int_mask (unsigned prec) +{ + double_int mask; if (prec > HOST_BITS_PER_WIDE_INT) { prec -= HOST_BITS_PER_WIDE_INT; - comb->mask.high = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); - comb->mask.low = ~(unsigned HOST_WIDE_INT) 0; + mask.high = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); + mask.low = ~(unsigned HOST_WIDE_INT) 0; } else { - comb->mask.high = 0; - comb->mask.low = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); + mask.high = 0; + mask.low = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1); } + + return mask; } /* Initializes affine combination COMB so that its value is zero in TYPE. */ @@ -179,7 +284,7 @@ static void aff_combination_zero (aff_tree *comb, tree type) { comb->type = type; - affine_combination_set_mask (comb); + comb->mask = double_int_mask (TYPE_PRECISION (type)); comb->offset.low = 0; comb->offset.high = 0; @@ -193,7 +298,7 @@ void aff_combination_const (aff_tree *comb, tree type, double_int cst) { aff_combination_zero (comb, type); - comb->offset = restrict_cst_to_precision (comb, cst); + comb->offset = restrict_cst_to_precision (comb->mask, cst); } /* Sets COMB to single element ELT. */ @@ -215,7 +320,7 @@ aff_combination_scale (aff_tree *comb, double_int scale) { unsigned i, j; - scale = restrict_cst_to_precision (comb, scale); + scale = restrict_cst_to_precision (comb->mask, scale); if (double_int_one_p (scale)) return; @@ -225,10 +330,10 @@ aff_combination_scale (aff_tree *comb, double_int scale) return; } - comb->offset = double_int_mul (comb, scale, comb->offset); + comb->offset = double_int_mul (comb->mask, scale, comb->offset); for (i = 0, j = 0; i < comb->n; i++) { - comb->coefs[j] = double_int_mul (comb, scale, comb->coefs[i]); + comb->coefs[j] = double_int_mul (comb->mask, scale, comb->coefs[i]); comb->elts[j] = comb->elts[i]; /* A coefficient may become zero due to overflow. Remove the zero elements. */ @@ -265,7 +370,7 @@ aff_combination_add_elt (aff_tree *comb, tree elt, double_int scale) for (i = 0; i < comb->n; i++) if (operand_equal_p (comb->elts[i], elt, 0)) { - comb->coefs[i] = double_int_add (comb, comb->coefs[i], scale); + comb->coefs[i] = double_int_add (comb->mask, comb->coefs[i], scale); if (!double_int_zero_p (comb->coefs[i])) return; @@ -302,7 +407,7 @@ aff_combination_add (aff_tree *comb1, aff_tree *comb2) { unsigned i; - comb1->offset = double_int_add (comb1, comb1->offset, comb2->offset); + comb1->offset = double_int_add (comb1->mask, comb1->offset, comb2->offset); for (i = 0; i < comb2->n; i++) aff_combination_add_elt (comb1, comb2->elts[i], comb2->coefs[i]); if (comb2->rest) @@ -324,12 +429,12 @@ aff_combination_convert (aff_tree *comb, tree type) if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type)) return; - affine_combination_set_mask (comb); + comb->mask = double_int_mask (TYPE_PRECISION (type)); - comb->offset = restrict_cst_to_precision (comb, comb->offset); + comb->offset = restrict_cst_to_precision (comb->mask, comb->offset); for (i = j = 0; i < comb->n; i++) { - comb->coefs[j] = restrict_cst_to_precision (comb, comb->coefs[i]); + comb->coefs[j] = restrict_cst_to_precision (comb->mask, comb->coefs[i]); if (double_int_zero_p (comb->coefs[j])) continue; comb->elts[j] = fold_convert (type, comb->elts[i]); @@ -428,7 +533,7 @@ add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, { enum tree_code code; - scale = restrict_cst_to_precision (comb, scale); + scale = restrict_cst_to_precision (comb->mask, scale); elt = fold_convert (type, elt); if (double_int_one_p (scale)) @@ -439,7 +544,7 @@ add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, return fold_build2 (PLUS_EXPR, type, expr, elt); } - if (double_int_minus_one_p (comb, scale)) + if (double_int_minus_one_p (comb->mask, scale)) { if (!expr) return fold_build1 (NEGATE_EXPR, type, elt); @@ -451,10 +556,10 @@ add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, return fold_build2 (MULT_EXPR, type, elt, double_int_to_tree (type, scale)); - if (double_int_negative_p (comb, scale)) + if (double_int_negative_p (comb->mask, scale)) { code = MINUS_EXPR; - scale = double_int_negate (comb, scale); + scale = double_int_negate (comb->mask, scale); } else code = PLUS_EXPR; @@ -479,10 +584,10 @@ aff_combination_to_tree (aff_tree *comb) for (i = 0; i < comb->n; i++) expr = add_elt_to_tree (expr, type, comb->elts[i], comb->coefs[i], comb); - if (double_int_negative_p (comb, comb->offset)) + if (double_int_negative_p (comb->mask, comb->offset)) { /* Offset is negative. */ - off = double_int_negate (comb, comb->offset); + off = double_int_negate (comb->mask, comb->offset); sgn = comb->mask; } else diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h index b86b00afe25..aff34bf94bd 100644 --- a/gcc/tree-affine.h +++ b/gcc/tree-affine.h @@ -18,13 +18,6 @@ along with GCC; see the file COPYING. If not, write to the Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -/* A structure containing a large integer. */ - -typedef struct -{ - unsigned HOST_WIDE_INT low, high; -} double_int; - /* Affine combination of trees. We keep track of at most MAX_AFF_ELTS elements to make things simpler; this is sufficient in most cases. */ @@ -66,12 +59,19 @@ void tree_to_aff_combination (tree, tree, aff_tree *); tree aff_combination_to_tree (aff_tree *); void unshare_aff_combination (aff_tree *); tree double_int_to_tree (tree, double_int); -bool double_int_fits_in_hwi_p (aff_tree *, double_int); -HOST_WIDE_INT double_int_to_hwi (aff_tree *, double_int); -double_int double_int_mul (aff_tree *, double_int, double_int); -double_int double_int_add (aff_tree *, double_int, double_int); -double_int double_int_negate (aff_tree *, double_int); -bool double_int_negative_p (aff_tree *, double_int); +bool double_int_fits_to_type_p (tree, double_int); +bool double_int_fits_in_hwi_p (double_int, double_int); +HOST_WIDE_INT double_int_to_hwi (double_int, double_int); +bool double_int_fits_in_unsigned_hwi_p (double_int); +unsigned HOST_WIDE_INT double_int_to_unsigned_hwi (double_int); +double_int double_int_mul (double_int, double_int, double_int); +double_int double_int_add (double_int, double_int, double_int); +double_int double_int_negate (double_int, double_int); +double_int double_int_divide (double_int, double_int); +bool double_int_negative_p (double_int, double_int); +bool double_int_smaller_p (double_int, double_int); +void dump_double_int (FILE *, double_int, double_int, bool); +double_int double_int_mask (unsigned); /* Constructs double_int from tree CST. */ @@ -99,6 +99,14 @@ hwi_to_double_int (HOST_WIDE_INT cst) return r; } +/* Constructs mask with all bits 1. */ + +static inline double_int +double_int_all (void) +{ + return hwi_to_double_int (-1); +} + /* Returns true if CST is zero. */ static inline bool @@ -115,12 +123,12 @@ double_int_one_p (double_int cst) return cst.low == 1 && cst.high == 0; } -/* Returns true if CST is minus one in precision of COMB. */ +/* Returns true if CST is minus one in precision of MASK. */ static inline bool -double_int_minus_one_p (aff_tree *comb, double_int cst) +double_int_minus_one_p (double_int mask, double_int cst) { - return cst.low == comb->mask.low && cst.high == comb->mask.high; + return cst.low == mask.low && cst.high == mask.high; } /* Returns true if CST1 == CST2. */ diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 84d531839a6..4a322cf26fe 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -749,51 +749,53 @@ estimate_niter_from_size_of_data (struct loop *loop, tree access_fn, tree stmt) { - tree estimation = NULL_TREE; - tree array_size, data_size, element_size; - tree init, step; + tree low, high, next; + tree init, step, type; + bool sign; init = initial_condition (access_fn); step = evolution_part_in_loop_num (access_fn, loop->num); + if (!init + || !step + || TREE_CODE (step) != INTEGER_CST + || zero_p (step) + || tree_contains_chrecs (init, NULL) + || chrec_contains_symbols_defined_in_loop (init, loop->num)) + return; + + low = array_ref_low_bound (opnd0); + high = array_ref_up_bound (opnd0); - array_size = TYPE_SIZE (TREE_TYPE (opnd0)); - element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0))); - if (array_size == NULL_TREE - || TREE_CODE (array_size) != INTEGER_CST - || TREE_CODE (element_size) != INTEGER_CST) + /* The case of nonconstant bounds could be handled, but it would be + complicated. */ + if (TREE_CODE (low) != INTEGER_CST + || !high + || TREE_CODE (high) != INTEGER_CST) + return; + sign = tree_int_cst_sign_bit (step); + type = TREE_TYPE (step); + + /* In case the relevant bound of the array does not fit in type, or + it does, but bound + step (in type) falls into the range of the + array, the index still might overflow. To make things simpler, + we require both bounds to fit into type, although there are cases + where this would not be strightly necessary. */ + if (!int_fits_type_p (high, type) + || !int_fits_type_p (low, type)) return; + low = fold_convert (type, low); + high = fold_convert (type, high); - data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node, - array_size, element_size); - - if (init != NULL_TREE - && step != NULL_TREE - && TREE_CODE (init) == INTEGER_CST - && TREE_CODE (step) == INTEGER_CST) - { - tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step); - tree sign = fold_build2 (GT_EXPR, boolean_type_node, i_plus_s, init); - - if (sign == boolean_true_node) - estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node, - fold_build2 (MINUS_EXPR, integer_type_node, - data_size, init), step); - - /* When the step is negative, as in PR23386: (init = 3, step = - 0ffffffff, data_size = 100), we have to compute the - estimation as ceil_div (init, 0 - step) + 1. */ - else if (sign == boolean_false_node) - estimation = - fold_build2 (PLUS_EXPR, integer_type_node, - fold_build2 (CEIL_DIV_EXPR, integer_type_node, - init, - fold_build2 (MINUS_EXPR, unsigned_type_node, - integer_zero_node, step)), - integer_one_node); - - if (estimation) - record_estimate (loop, estimation, boolean_true_node, stmt); - } + if (sign) + next = fold_build2 (PLUS_EXPR, type, low, step); + else + next = fold_build2 (PLUS_EXPR, type, high, step); + + if (nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, low, next)) + && nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, next, high))) + return; + + record_nonwrapping_iv (loop, init, step, stmt, low, high); } /* Given an ARRAY_REF node REF, records its access functions. @@ -820,8 +822,8 @@ analyze_array_indexes (struct loop *loop, access_fn = instantiate_parameters (loop, analyze_scalar_evolution (loop, opnd1)); - if (chrec_contains_undetermined (loop->estimated_nb_iterations)) - estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt); + if (loop->niter_bounds_state == NBS_RECORDING) + estimate_niter_from_size_of_data (loop, ref, access_fn, stmt); VEC_safe_push (tree, heap, *access_fns, access_fn); @@ -2358,39 +2360,21 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, { bool xz_p, yz_p, xyz_p; int step_x, step_y, step_z; - int niter_x, niter_y, niter_z, niter; - tree numiter_x, numiter_y, numiter_z; + unsigned HOST_WIDE_INT niter_x, niter_y, niter_z, niter; tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz; tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz; tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz; + struct loop *loop_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]; + struct loop *loop_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]; + struct loop *loop_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]; step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a))); step_y = int_cst_value (CHREC_RIGHT (chrec_a)); step_z = int_cst_value (CHREC_RIGHT (chrec_b)); - numiter_x = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]); - numiter_y = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); - numiter_z = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_b)]); - - if (TREE_CODE (numiter_x) != INTEGER_CST) - numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_y) != INTEGER_CST) - numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_z) != INTEGER_CST) - numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)] - ->estimated_nb_iterations; - - if (chrec_contains_undetermined (numiter_x) - || chrec_contains_undetermined (numiter_y) - || chrec_contains_undetermined (numiter_z) - || TREE_CODE (numiter_x) != INTEGER_CST - || TREE_CODE (numiter_y) != INTEGER_CST - || TREE_CODE (numiter_z) != INTEGER_CST) + if (!get_max_loop_niter (loop_x, &niter_x) + || !get_max_loop_niter (loop_y, &niter_y) + || !get_max_loop_niter (loop_z, &niter_z)) { *overlaps_a = chrec_dont_know; *overlaps_b = chrec_dont_know; @@ -2398,10 +2382,6 @@ compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b, return; } - niter_x = int_cst_value (numiter_x); - niter_y = int_cst_value (numiter_y); - niter_z = int_cst_value (numiter_z); - niter = MIN (niter_x, niter_z); compute_overlap_steps_for_affine_univar (niter, step_x, step_z, &overlaps_a_xz, @@ -2524,24 +2504,12 @@ analyze_subscript_affine_affine (tree chrec_a, if (nb_vars_a == 1 && nb_vars_b == 1) { int step_a, step_b; - int niter, niter_a, niter_b; - tree numiter_a, numiter_b; - - numiter_a = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); - numiter_b = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_b)]); - - if (TREE_CODE (numiter_a) != INTEGER_CST) - numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_b) != INTEGER_CST) - numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] - ->estimated_nb_iterations; - if (chrec_contains_undetermined (numiter_a) - || chrec_contains_undetermined (numiter_b) - || TREE_CODE (numiter_a) != INTEGER_CST - || TREE_CODE (numiter_b) != INTEGER_CST) + unsigned HOST_WIDE_INT niter, niter_a, niter_b; + struct loop *loop_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]; + struct loop *loop_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]; + + if (!get_max_loop_niter (loop_a, &niter_a) + || !get_max_loop_niter (loop_b, &niter_b)) { *overlaps_a = chrec_dont_know; *overlaps_b = chrec_dont_know; @@ -2549,8 +2517,6 @@ analyze_subscript_affine_affine (tree chrec_a, return; } - niter_a = int_cst_value (numiter_a); - niter_b = int_cst_value (numiter_b); niter = MIN (niter_a, niter_b); step_a = int_cst_value (CHREC_RIGHT (chrec_a)); @@ -2628,24 +2594,12 @@ analyze_subscript_affine_affine (tree chrec_a, dependence. X0, Y0 are two solutions of the Diophantine equation: chrec_a (X0) = chrec_b (Y0). */ int x0, y0; - int niter, niter_a, niter_b; - tree numiter_a, numiter_b; - - numiter_a = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_a)]); - numiter_b = number_of_iterations_in_loop - (current_loops->parray[CHREC_VARIABLE (chrec_b)]); - - if (TREE_CODE (numiter_a) != INTEGER_CST) - numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)] - ->estimated_nb_iterations; - if (TREE_CODE (numiter_b) != INTEGER_CST) - numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)] - ->estimated_nb_iterations; - if (chrec_contains_undetermined (numiter_a) - || chrec_contains_undetermined (numiter_b) - || TREE_CODE (numiter_a) != INTEGER_CST - || TREE_CODE (numiter_b) != INTEGER_CST) + unsigned HOST_WIDE_INT niter, niter_a, niter_b; + struct loop *loop_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]; + struct loop *loop_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]; + + if (!get_max_loop_niter (loop_a, &niter_a) + || !get_max_loop_niter (loop_b, &niter_b)) { *overlaps_a = chrec_dont_know; *overlaps_b = chrec_dont_know; @@ -2653,8 +2607,6 @@ analyze_subscript_affine_affine (tree chrec_a, return; } - niter_a = int_cst_value (numiter_a); - niter_b = int_cst_value (numiter_b); niter = MIN (niter_a, niter_b); i0 = U[0][0] * gamma / gcd_alpha_beta; @@ -2679,13 +2631,13 @@ analyze_subscript_affine_affine (tree chrec_a, if (i1 > 0) { tau1 = CEIL (-i0, i1); - tau2 = FLOOR_DIV (niter - i0, i1); + tau2 = FLOOR_DIV ((int) niter - i0, i1); if (j1 > 0) { int last_conflict, min_multiple; tau1 = MAX (tau1, CEIL (-j0, j1)); - tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1)); + tau2 = MIN (tau2, FLOOR_DIV ((int) niter - j0, j1)); x0 = i1 * tau1 + i0; y0 = j1 * tau1 + j0; diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index e77f699d808..1ff125ac487 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -693,18 +693,6 @@ struct tree_niter_desc a loop (provided that assumptions == true and may_be_zero == false), more precisely the number of executions of the latch of the loop. */ - tree additional_info; /* The boolean expression. Sometimes we use additional - knowledge to simplify the other expressions - contained in this structure (for example the - knowledge about value ranges of operands on entry to - the loop). If this is a case, conjunction of such - condition is stored in this field, so that we do not - lose the information: for example if may_be_zero - is (n <= 0) and niter is (unsigned) n, we know - that the number of iterations is at most - MAX_SIGNED_INT. However if the (n <= 0) assumption - is eliminated (by looking at the guard on entry of - the loop), then the information would be lost. */ }; /* In tree-vectorizer.c */ @@ -762,8 +750,14 @@ struct loop *tree_ssa_loop_version (struct loops *, struct loop *, tree, edge single_dom_exit (const struct loop *); tree expand_simple_operations (tree); void substitute_in_loop_info (struct loop *, tree, tree); -bool select_condition_shape (tree, tree, tree, bool, enum tree_code *, tree *); +bool select_condition_shape (struct loop *, tree, tree, tree, bool, + enum tree_code *, tree *); unsigned compare_cost (tree); +bool loop_iterations_at_most_p (struct loop *, tree, tree); +bool condition_holds_in_loop_p (struct loop *, tree); +bool get_max_loop_niter (struct loop *, unsigned HOST_WIDE_INT *); +void record_niter_bound (struct loop *, tree, bool); +void record_nonwrapping_iv (struct loop *, tree, tree, tree, tree, tree); /* In tree-ssa-loop-im.c */ /* The possibilities of statement movement. */ diff --git a/gcc/tree-ssa-address.c b/gcc/tree-ssa-address.c index 2d2b8a22bfe..d0a03c716e2 100644 --- a/gcc/tree-ssa-address.c +++ b/gcc/tree-ssa-address.c @@ -395,10 +395,10 @@ most_expensive_mult_to_index (struct mem_address *parts, tree type, for (i = 0; i < addr->n; i++) { - if (!double_int_fits_in_hwi_p (addr, addr->coefs[i])) + if (!double_int_fits_in_hwi_p (addr->mask, addr->coefs[i])) continue; - coef = double_int_to_hwi (addr, addr->coefs[i]); + coef = double_int_to_hwi (addr->mask, addr->coefs[i]); if (coef == 1 || !multiplier_allowed_in_address_p (coef)) continue; @@ -419,7 +419,7 @@ most_expensive_mult_to_index (struct mem_address *parts, tree type, for (i = j = 0; i < addr->n; i++) { amult = addr->coefs[i]; - amult_neg = double_int_negate (addr, amult); + amult_neg = double_int_negate (addr->mask, amult); if (double_int_equal_p (amult, best_mult)) op_code = PLUS_EXPR; diff --git a/gcc/tree-ssa-loop-endcond.c b/gcc/tree-ssa-loop-endcond.c index 953f267cfb1..bfbdfd30cc8 100644 --- a/gcc/tree-ssa-loop-endcond.c +++ b/gcc/tree-ssa-loop-endcond.c @@ -43,15 +43,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA ((signed) STEP > 0), whose final value V satisfies -STEP <= V < 0 and whose initial value satisfies (signed) BASE >= 0, we use (signed) X >= 0 compare. - -- if X = BASE + STEP * i and final value V is of shape V' + C, where - 0 < C <= STEP, and there is no overflow, then we use - X <= V' compare. - -- otherwise we use X != V compare. - - TODO: implement loop reversal - addition removal in condition shape selection - use information about bounds on number of iterations in condition - shape selection */ + -- otherwise we use X != V compare. */ #include "config.h" #include "system.h" @@ -105,23 +97,53 @@ iv_period (tree step) return period; } -/* Given exit condition based on induction variable BASE + STEP * i, +/* Check whether iv of LOOP with step STEP may wraps around the range of + the type. */ + +static bool +may_wrap_around_type_range_p (struct loop *loop, tree step) +{ + tree unsigned_type = unsigned_type_for (TREE_TYPE (step)); + tree range = iv_period (build_int_cst_type (unsigned_type, 1)); + + step = fold_convert (unsigned_type, step); + if (tree_int_cst_sign_bit (step)) + step = fold_build1 (NEGATE_EXPR, unsigned_type, step); + if (tree_int_cst_sign_bit (step)) + return true; + + /* We need to check whether niter * step <= range. */ + range = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, range, step); + + return !loop_iterations_at_most_p (loop, range, NULL_TREE); +} + +/* Given exit condition of LOOP based on induction variable BASE + STEP * i, whose final value is *BOUND, try altering comparison operator *CMP so that the *BOUND can be replaced by zero. Return true if this succeeds, false otherwise. */ static bool -modify_to_compare_with_zero (tree base, tree step, +modify_to_compare_with_zero (struct loop *loop, + tree base, tree step, enum tree_code *cmp, tree *bound) { tree type = TREE_TYPE (step), signed_type = signed_type_for (type); + tree unsigned_type = unsigned_type_for (type); tree signed_bound = fold_convert (signed_type, *bound); tree signed_step = fold_convert (signed_type, step); tree signed_base = fold_convert (signed_type, base); tree signed_zero = build_int_cst_type (signed_type, 0); + tree nit_bound; + enum tree_code ok_cmp = ERROR_MARK; + + if (may_wrap_around_type_range_p (loop, step)) + return false; if (tree_int_cst_sign_bit (step)) { + ok_cmp = GE_EXPR; + step = fold_build1 (NEGATE_EXPR, type, step); if (tree_int_cst_sign_bit (step)) { @@ -135,69 +157,69 @@ modify_to_compare_with_zero (tree base, tree step, if (!nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, signed_step, signed_bound)) || !nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, - signed_bound, signed_zero)) - /* We can apply the optimization, assuming that BASE >= 0. */ - || !nonzero_p (fold_build2 (GE_EXPR, boolean_type_node, - signed_base, signed_zero))) + signed_bound, signed_zero))) return false; - *cmp = GE_EXPR; + + /* We can apply the optimization, assuming that the initial value + of the counter (signed_base) is >= the final value (signed_bound). */ + if (condition_holds_in_loop_p (loop, + fold_build2 (GE_EXPR, boolean_type_node, + signed_base, signed_bound))) + goto ok; + + /* The other way how to check this is using the fact that + signed_base = signed_bound + step * niter, and to prove that + + niter <= (signed_max - bound) / step. */ + nit_bound = fold_convert (unsigned_type, + upper_bound_in_type (signed_type, signed_type)); + step = fold_convert (unsigned_type, step); + nit_bound = fold_build2 (PLUS_EXPR, unsigned_type, + nit_bound, + fold_convert (unsigned_type, *bound)); + nit_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, nit_bound, step); + if (loop_iterations_at_most_p (loop, nit_bound, NULL_TREE)) + goto ok; } else { + ok_cmp = LE_EXPR; /* Condition in shape base + step * i. This case does not appear as often in practice, but let's try anyway. Check whether 0 < bound <= step. */ if (!nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, signed_zero, signed_bound)) || !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, - signed_bound, signed_step)) - /* We can apply the optimization, assuming that BASE <= 0. */ - || !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, - signed_base, signed_zero))) + signed_bound, signed_step))) return false; - *cmp = LE_EXPR; + if (condition_holds_in_loop_p (loop, + fold_build2 (LE_EXPR, boolean_type_node, + signed_base, signed_bound))) + goto ok; + + /* The other way how to check this is using the fact that + signed_base = signed_bound - step * niter, and to prove that + + niter <= (bound - signed_min) / step. */ + nit_bound = fold_convert (unsigned_type, + lower_bound_in_type (signed_type, signed_type)); + step = fold_convert (unsigned_type, step); + nit_bound = fold_build2 (MINUS_EXPR, unsigned_type, + fold_convert (unsigned_type, *bound), + nit_bound); + nit_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, nit_bound, step); + if (loop_iterations_at_most_p (loop, nit_bound, NULL_TREE)) + goto ok; } - - *bound = signed_zero; - return true; -} - -/* Given exit condition based on induction variable BASE + STEP * i, - whose final value is *BOUND, try altering comparison operator *CMP and - *BOUND so that *BOUND does not contain unnecessary additions. Return - true if this succeeds, false otherwise. */ - -static bool -try_removing_addition_from_bound (tree base ATTRIBUTE_UNUSED, - tree step ATTRIBUTE_UNUSED, - enum tree_code *cmp ATTRIBUTE_UNUSED, - tree *bound ATTRIBUTE_UNUSED) -{ - /* NIY. */ + return false; -} - -/* Check whether iv with step STEP wraps around the range of the type - after at most NITER iterations. */ -static bool -may_wrap_around_type_range_p (tree niter, tree step) -{ - tree unsigned_type = unsigned_type_for (TREE_TYPE (step)); - tree range = iv_period (build_int_cst_type (unsigned_type, 1)); - - step = fold_convert (unsigned_type, step); - if (tree_int_cst_sign_bit (step)) - step = fold_build1 (NEGATE_EXPR, unsigned_type, step); - if (tree_int_cst_sign_bit (step)) - return true; - niter = fold_convert (unsigned_type, niter); - - /* We need to check whether niter * step <= range. */ - range = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, range, step); - return !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, niter, range)); +ok: + *cmp = ok_cmp; + *bound = signed_zero; + return true; } /* Determines the final value of iv with base BASE and step STEP, in loop @@ -225,7 +247,7 @@ final_value_of_iv (tree base, tree step, tree niter) if we succeed. */ bool -select_condition_shape (tree niter, tree base, tree step, +select_condition_shape (struct loop *loop, tree niter, tree base, tree step, bool exit_p, enum tree_code *cmp, tree *bound) { tree nit_type = TREE_TYPE (niter), per_type, wider_type; @@ -257,19 +279,8 @@ select_condition_shape (tree niter, tree base, tree step, if (zero_p (final)) goto end; - /* Check whether the variable wraps around the type range, i.e., whether - niter * step >= range. If this is the case, we cannot do any of the - following optimizations. */ - if (may_wrap_around_type_range_p (niter, step)) - goto end; - - /* Else try transforming the condition to a compare with zero. */ - if (!modify_to_compare_with_zero (base, step, cmp, bound)) - { - /* If everything else failed, try removing addition or subtraction - from the bound. */ - try_removing_addition_from_bound (base, step, cmp, bound); - } + /* Try transforming the condition to a compare with zero. */ + modify_to_compare_with_zero (loop, base, step, cmp, bound); end: if (exit_p) @@ -389,12 +400,13 @@ may_reverse_loop_p (struct loop *loop, varray_type *datarefs, tree *niter) return ret; } -/* Returns cost of basing exit condition for loop that exits after NITER +/* Returns cost of basing exit condition for LOOP that exits after NITER iterations on induction variable with BASE and STEP. If REVERSED is true, we reverse the variable first. */ static unsigned -endcond_candidate_cost (tree base, tree step, tree niter, bool reversed) +endcond_candidate_cost (struct loop *loop, + tree base, tree step, tree niter, bool reversed) { tree bound; enum tree_code cmp; @@ -405,7 +417,7 @@ endcond_candidate_cost (tree base, tree step, tree niter, bool reversed) step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step); } - if (!select_condition_shape (niter, base, step, true, &cmp, &bound)) + if (!select_condition_shape (loop, niter, base, step, true, &cmp, &bound)) return 10; return compare_cost (bound); @@ -442,7 +454,7 @@ best_endcond_candidate_cost (struct loop *loop, varray_type datarefs, || chrec_contains_symbols_defined_in_loop (base, loop->num)) continue; - act = endcond_candidate_cost (base, step, niter, reversed); + act = endcond_candidate_cost (loop, base, step, niter, reversed); if (act < best) best = act; } diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index fb72232ca8d..c01f64131ed 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -322,11 +322,6 @@ struct iv_ca_delta #define ALWAYS_PRUNE_CAND_SET_BOUND \ ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND)) -/* The list of trees for that the decl_rtl field must be reset is stored - here. */ - -static VEC(tree,heap) *decl_rtl_to_reset; - /* Number of uses recorded in DATA. */ static inline unsigned @@ -726,6 +721,10 @@ niter_for_exit (struct ivopts_data *data, edge exit) exit, &nfe_desc->niter, true); *slot = nfe_desc; + + if (nfe_desc->valid_p) + nfe_desc->niter.niter + = expand_simple_operations (nfe_desc->niter.niter); } else nfe_desc = *slot; @@ -773,7 +772,6 @@ tree_ssa_iv_optimize_init (struct loops *loops, struct ivopts_data *data) data->iv_uses = VEC_alloc (iv_use_p, heap, 20); data->iv_candidates = VEC_alloc (iv_cand_p, heap, 20); - decl_rtl_to_reset = VEC_alloc (tree, heap, 20); } /* Returns a memory object to that EXPR points. In case we are able to @@ -2582,106 +2580,6 @@ seq_cost (rtx seq) return cost; } -/* Produce DECL_RTL for object obj so it looks like it is stored in memory. */ -static rtx -produce_memory_decl_rtl (tree obj, int *regno) -{ - rtx x; - - gcc_assert (obj); - if (TREE_STATIC (obj) || DECL_EXTERNAL (obj)) - { - const char *name = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (obj)); - x = gen_rtx_SYMBOL_REF (Pmode, name); - } - else - x = gen_raw_REG (Pmode, (*regno)++); - - return gen_rtx_MEM (DECL_MODE (obj), x); -} - -/* Prepares decl_rtl for variables referred in *EXPR_P. Callback for - walk_tree. DATA contains the actual fake register number. */ - -static tree -prepare_decl_rtl (tree *expr_p, int *ws, void *data) -{ - tree obj = NULL_TREE; - rtx x = NULL_RTX; - int *regno = data; - - switch (TREE_CODE (*expr_p)) - { - case ADDR_EXPR: - for (expr_p = &TREE_OPERAND (*expr_p, 0); - handled_component_p (*expr_p); - expr_p = &TREE_OPERAND (*expr_p, 0)) - continue; - obj = *expr_p; - if (DECL_P (obj)) - x = produce_memory_decl_rtl (obj, regno); - break; - - case SSA_NAME: - *ws = 0; - obj = SSA_NAME_VAR (*expr_p); - if (!DECL_RTL_SET_P (obj)) - x = gen_raw_REG (DECL_MODE (obj), (*regno)++); - break; - - case VAR_DECL: - case PARM_DECL: - case RESULT_DECL: - *ws = 0; - obj = *expr_p; - - if (DECL_RTL_SET_P (obj)) - break; - - if (DECL_MODE (obj) == BLKmode) - x = produce_memory_decl_rtl (obj, regno); - else - x = gen_raw_REG (DECL_MODE (obj), (*regno)++); - - break; - - default: - break; - } - - if (x) - { - VEC_safe_push (tree, heap, decl_rtl_to_reset, obj); - SET_DECL_RTL (obj, x); - } - - return NULL_TREE; -} - -/* Determines cost of the computation of EXPR. */ - -static unsigned -computation_cost (tree expr) -{ - rtx seq, rslt; - tree type = TREE_TYPE (expr); - unsigned cost; - /* Avoid using hard regs in ways which may be unsupported. */ - int regno = LAST_VIRTUAL_REGISTER + 1; - - walk_tree (&expr, prepare_decl_rtl, ®no, NULL); - start_sequence (); - rslt = expand_expr (expr, NULL_RTX, TYPE_MODE (type), EXPAND_NORMAL); - seq = get_insns (); - end_sequence (); - - cost = seq_cost (seq); - if (MEM_P (rslt)) - cost += address_cost (XEXP (rslt, 0), TYPE_MODE (type)); - - return cost; -} - /* Returns variable containing the value of candidate CAND at statement AT. */ static tree @@ -2869,7 +2767,7 @@ get_computation_aff (struct loop *loop, happen, fold is able to apply the distributive law to obtain this form anyway. */ - aff_combination_scale (&cbase_aff, double_int_negate (&cbase_aff, rat)); + aff_combination_scale (&cbase_aff, double_int_negate (cbase_aff.mask, rat)); aff_combination_scale (&expr_aff, rat); aff_combination_add (aff, &cbase_aff); aff_combination_add (aff, &expr_aff); @@ -3226,78 +3124,77 @@ convert_cost (enum machine_mode mode_to, enum machine_mode mode_from, costs[mode_to][mode_from][unsigned_p] = cost; if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Conversion from %sto %s costs %d\n", + fprintf (dump_file, "Conversion from %sto %s costs %d\n", GET_MODE_NAME (mode_from), GET_MODE_NAME (mode_to), cost); return cost; } -/* Estimates cost of forcing expression EXPR into a variable. */ +/* Returns the cost of forcing an integer constant in MODE to be + an operand. Not implemented yet, for now we assume all constants + are cheap (which is not always the case). */ -unsigned -force_expr_to_var_cost (tree expr) +static unsigned +integer_cost (enum machine_mode mode) { - static bool costs_initialized = false; - static unsigned integer_cost; - static unsigned symbol_cost; - static unsigned address_cost; - tree op0 = NULL_TREE, op1 = NULL_TREE, inner_type; - unsigned cost0 = 0, cost1 = 0, cost; - enum machine_mode mode; + static unsigned costs[NUM_MACHINE_MODES]; - if (!costs_initialized) + if (!costs[mode]) { - tree var = create_tmp_var_raw (integer_type_node, "test_var"); - rtx x = gen_rtx_MEM (DECL_MODE (var), - gen_rtx_SYMBOL_REF (Pmode, "test_var")); - tree addr; - tree type = build_pointer_type (integer_type_node); + /* TODO -- determine the cost. */ + costs[mode] = 1; - integer_cost = computation_cost (build_int_cst_type (integer_type_node, - 2000)); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Cost of integer constant in %s is 0\n", + GET_MODE_NAME (mode)); + } + return costs[mode] - 1; +} - SET_DECL_RTL (var, x); - TREE_STATIC (var) = 1; - addr = build1 (ADDR_EXPR, type, var); - symbol_cost = computation_cost (addr) + 1; +/* Retunrs the cost of using a fixed address as an operand. Not implemented + yet, for now we assume all such expressions are cheap (which is not always + the case). */ - address_cost - = computation_cost (build2 (PLUS_EXPR, type, - addr, - build_int_cst_type (type, 2000))) + 1; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "force_expr_to_var_cost:\n"); - fprintf (dump_file, " integer %d\n", (int) integer_cost); - fprintf (dump_file, " symbol %d\n", (int) symbol_cost); - fprintf (dump_file, " address %d\n", (int) address_cost); - fprintf (dump_file, " other %d\n", (int) target_spill_cost); - fprintf (dump_file, "\n"); - } +static unsigned +fixed_address_cost (void) +{ + static unsigned cost = 0; - costs_initialized = true; + if (!cost) + { + /* TODO -- determine the cost. */ + cost = 1; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Cost of taking a fixed address is 0\n"); } + return cost - 1; +} + +/* Estimates cost of forcing expression EXPR into a variable. */ + +unsigned +force_expr_to_var_cost (tree expr) +{ + tree op0 = NULL_TREE, op1 = NULL_TREE, inner_type; + unsigned cost0 = 0, cost1 = 0, cost; + enum machine_mode mode; + STRIP_NOPS (expr); if (SSA_VAR_P (expr)) return 0; + mode = TYPE_MODE (TREE_TYPE (expr)); + if (TREE_INVARIANT (expr)) { if (TREE_CODE (expr) == INTEGER_CST) - return integer_cost; - - if (TREE_CODE (expr) == ADDR_EXPR) - { - tree obj = TREE_OPERAND (expr, 0); - - if (TREE_CODE (obj) == VAR_DECL - || TREE_CODE (obj) == PARM_DECL - || TREE_CODE (obj) == RESULT_DECL) - return symbol_cost; - } + return integer_cost (mode); - return address_cost; + /* TODO -- this might also be address of parameter, or other invariants + that do not really qualify as object with fixed address. */ + return fixed_address_cost (); } switch (TREE_CODE (expr)) @@ -3330,7 +3227,6 @@ force_expr_to_var_cost (tree expr) return target_spill_cost; } - mode = TYPE_MODE (TREE_TYPE (expr)); switch (TREE_CODE (expr)) { case PLUS_EXPR: @@ -3386,16 +3282,22 @@ force_var_cost (struct ivopts_data *data, /* Determines the cost of the computation COMP. A set of invariants the expression depends on is stored in DEPENDS_ON. COMP is modified - in the progress. */ + in the progress. OUTER_ADDITION is set to true if there is an + addition outside any multiplication in the final expression. */ static unsigned aff_combination_cost (struct ivopts_data *data, aff_tree *comp, - bitmap *depends_on) + bitmap *depends_on, bool *outer_addition) { int n_adds = comp->n - 1; unsigned i, j, cost = 0; - bool all_negated = true; + unsigned positive_terms = 0; enum machine_mode mode = TYPE_MODE (comp->type); + double_int positive, negative; + bool seen_positive; + + if (outer_addition) + *outer_addition = false; if (comp->n == 0 && !comp->rest) { @@ -3408,56 +3310,76 @@ aff_combination_cost (struct ivopts_data *data, aff_tree *comp, { n_adds++; cost += force_var_cost (data, comp->rest, depends_on); - all_negated = false; + positive_terms++; } if (!double_int_zero_p (comp->offset)) { n_adds++; - all_negated = false; + positive_terms++; } - /* Compute the cost of multiplications. Using distributivity, each - coefficient needs to be considered only once. Furthermore, we - do not need to consider both constant and its negation. + for (i = 0; i < comp->n; i++) + cost += force_var_cost (data, comp->elts[i], depends_on); + + /* Compute the cost of multiplications and number of additions. Using + distributivity, each coefficient needs to be considered only once. + Furthermore, we do not need to consider both constant and its negation. If all elements are multiplied by negative number, we must perform one multiplication by a negative constant (and use MINUS_EXPR for the rest). - Otherwise, it is possible to always multiply be a positive constant. */ + Otherwise, it is possible to always multiply be a positive constant, + which should usually be cheaper. */ for (i = 0; i < comp->n; i++) { - cost += force_var_cost (data, comp->elts[i], depends_on); - if (double_int_negative_p (comp, comp->coefs[i])) - comp->coefs[i] = double_int_negate (comp, comp->coefs[i]); - else - all_negated = false; - - if (double_int_one_p (comp->coefs[i])) + if (double_int_zero_p (comp->coefs[i])) continue; - for (j = 0; j < i; j++) - if (double_int_equal_p (comp->coefs[i], comp->coefs[j])) - break; - if (j < i) - continue; + if (double_int_negative_p (comp->mask, comp->coefs[i])) + { + negative = comp->coefs[i]; + positive = double_int_negate (comp->mask, comp->coefs[i]); + seen_positive = false; + } + else + { + positive = comp->coefs[i]; + negative = double_int_negate (comp->mask, comp->coefs[i]); + seen_positive = true; + } + + for (j = i + 1; j < comp->n; j++) + { + if (double_int_equal_p (positive, comp->coefs[j])) + seen_positive = true; + else if (!double_int_equal_p (negative, comp->coefs[j])) + continue; + comp->coefs[j] = hwi_to_double_int (0); + } - if (double_int_fits_in_hwi_p (comp, comp->coefs[i])) + if (!double_int_fits_in_hwi_p (comp->mask, comp->coefs[i])) { /* comp->coefs[i] almost always fits into HOST_WIDE_INT, so do not worry about this this case. */ cost += target_spill_cost; } else - cost += multiply_by_cost (double_int_to_hwi (comp, comp->coefs[i]), + cost += multiply_by_cost (double_int_to_hwi (comp->mask, comp->coefs[i]), mode); + + if (seen_positive) + positive_terms++; } - if (all_negated) + if (positive_terms == 0) { /* This is not really precise -- multiplying by a negative constant could be cheaper than multiplyiing by its negation and negating. */ cost += multiply_by_cost (-1, mode); } + if (outer_addition) + *outer_addition = (positive_terms >= 2); + return cost + n_adds * add_cost (mode); } @@ -3474,6 +3396,7 @@ aff_combination_cost_address (struct ivopts_data *data, aff_tree *comp, unsigned cost = 0, i, nelts; bool symbol_present = false, var_present = false, index_used = false; enum machine_mode mode = TYPE_MODE (comp->type); + bool outer_addition; /* Try finding a symbol. */ for (i = 0; i < comp->n; i++) @@ -3489,7 +3412,7 @@ aff_combination_cost_address (struct ivopts_data *data, aff_tree *comp, } } - if (double_int_fits_in_hwi_p (comp, ratio) + if (double_int_fits_in_hwi_p (comp->mask, ratio) && !double_int_one_p (ratio)) { /* Try separating index from comp. */ @@ -3499,9 +3422,9 @@ aff_combination_cost_address (struct ivopts_data *data, aff_tree *comp, if (i < comp->n) { - double_int ratio_neg = double_int_negate (comp, ratio); + double_int ratio_neg = double_int_negate (comp->mask, ratio); int n_add = -1; - rat = double_int_to_hwi (comp, ratio); + rat = double_int_to_hwi (comp->mask, ratio); for (; i < comp->n; ) { @@ -3525,9 +3448,9 @@ aff_combination_cost_address (struct ivopts_data *data, aff_tree *comp, if (!double_int_zero_p (comp->offset)) { - if (double_int_fits_in_hwi_p (comp, comp->offset)) + if (double_int_fits_in_hwi_p (comp->mask, comp->offset)) { - off = double_int_to_hwi (comp, comp->offset); + off = double_int_to_hwi (comp->mask, comp->offset); comp->offset = hwi_to_double_int (0); } else @@ -3538,13 +3461,13 @@ aff_combination_cost_address (struct ivopts_data *data, aff_tree *comp, if (nelts) { - cost += aff_combination_cost (data, comp, depends_on); + cost += aff_combination_cost (data, comp, depends_on, &outer_addition); /* We can save one addition by using BASE + INDEX addressing mode, if present and if index is not used already. */ if (index_used) var_present = true; - else if (nelts > 1) + else if (outer_addition) { var_present = true; cost -= add_cost (mode); @@ -3606,7 +3529,7 @@ get_computation_cost_at (struct ivopts_data *data, if (address_p) cost = aff_combination_cost_address (data, &comp, depends_on, rat); else - cost = aff_combination_cost (data, &comp, depends_on); + cost = aff_combination_cost (data, &comp, depends_on, NULL); gcc_assert ((signed) cost >= 0); return cost; @@ -3722,7 +3645,7 @@ may_eliminate_iv (struct ivopts_data *data, if (stmt_after_increment (loop, cand, use->stmt)) base = fold_build2 (PLUS_EXPR, type, base, step); - return select_condition_shape (niter->niter, base, step, + return select_condition_shape (loop, niter->niter, base, step, (exit->flags & EDGE_TRUE_VALUE) != 0, cmp, bound); } @@ -5616,7 +5539,6 @@ free_loop_data (struct ivopts_data *data) { unsigned i, j; bitmap_iterator bi; - tree obj; htab_empty (data->niters); @@ -5670,11 +5592,6 @@ free_loop_data (struct ivopts_data *data) } data->max_inv_id = 0; - - for (i = 0; VEC_iterate (tree, decl_rtl_to_reset, i, obj); i++) - SET_DECL_RTL (obj, NULL_RTX); - - VEC_truncate (tree, decl_rtl_to_reset, 0); } /* Finalizes data structures used by the iv optimization pass. LOOPS is the @@ -5698,7 +5615,6 @@ tree_ssa_iv_optimize_finalize (struct loops *loops, struct ivopts_data *data) BITMAP_FREE (data->important_candidates); htab_delete (data->niters); - VEC_free (tree, heap, decl_rtl_to_reset); VEC_free (iv_use_p, heap, data->iv_uses); VEC_free (iv_cand_p, heap, data->iv_candidates); } diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index d6fe90876a5..ed344ccdd70 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -42,6 +42,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "flags.h" #include "toplev.h" #include "tree-inline.h" +#include "tree-affine.h" #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) @@ -475,7 +476,6 @@ number_of_iterations_special (tree type, tree base0, tree step0, niter->assumptions = boolean_true_node; niter->may_be_zero = boolean_false_node; niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0); - niter->additional_info = boolean_true_node; } else if (integer_all_onesp (step0)) { @@ -557,7 +557,6 @@ number_of_iterations_special (tree type, tree base0, tree step0, } niter->niter = fold_convert (niter_type, niter->niter); - niter->additional_info = boolean_true_node; return true; } @@ -776,17 +775,15 @@ tree_simplify_using_condition (tree cond, tree expr) } /* Tries to simplify EXPR using the conditions on entry to LOOP. - Record the conditions used for simplification to CONDS_USED. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).*/ static tree -simplify_using_initial_conditions (struct loop *loop, tree expr, - tree *conds_used) +simplify_using_initial_conditions (struct loop *loop, tree expr) { edge e; basic_block bb; - tree exp, cond; + tree cond; if (TREE_CODE (expr) == INTEGER_CST) return expr; @@ -805,15 +802,7 @@ simplify_using_initial_conditions (struct loop *loop, tree expr, cond = COND_EXPR_COND (last_stmt (e->src)); if (e->flags & EDGE_FALSE_VALUE) cond = invert_truthvalue (cond); - exp = tree_simplify_using_condition (cond, expr); - - if (exp != expr) - *conds_used = fold_build2 (TRUTH_AND_EXPR, - boolean_type_node, - *conds_used, - cond); - - expr = exp; + expr = tree_simplify_using_condition (cond, expr); } return expr; @@ -956,15 +945,10 @@ number_of_iterations_exit (struct loop *loop, edge exit, niter->niter = simplify_using_outer_evolutions (loop, niter->niter); } - niter->additional_info = boolean_true_node; niter->assumptions - = simplify_using_initial_conditions (loop, - niter->assumptions, - &niter->additional_info); + = simplify_using_initial_conditions (loop, niter->assumptions); niter->may_be_zero - = simplify_using_initial_conditions (loop, - niter->may_be_zero, - &niter->additional_info); + = simplify_using_initial_conditions (loop, niter->may_be_zero); if (integer_onep (niter->assumptions)) return true; @@ -1327,45 +1311,374 @@ find_loop_niter_by_eval (struct loop *loop, edge *exit) */ -/* Records that AT_STMT is executed at most BOUND times in LOOP. The - additional condition ADDITIONAL is recorded with the bound. */ +/* The structure describing an induction variable that does not overflow. */ + +struct iv_no_overflow +{ + tree base, step; /* The induction variable BASE + STEP * i does not + overflow, ... */ + tree at_stmt; /* ... when evaluated at this statement. */ + struct iv_no_overflow *next; + /* The next bound in a list. */ +}; + +/* Returns true if we can infer that EXPR is always nonnegative in LOOP, + false otherwise. */ + +static bool +nonnegative_in_loop_p (struct loop *loop, tree expr) +{ + tree zero, type = TREE_TYPE (expr); + + if (TYPE_UNSIGNED (type)) + return true; + + zero = build_int_cst_type (type, 0); + return condition_holds_in_loop_p (loop, + fold_build2 (GE_EXPR, boolean_type_node, + expr, zero)); +} + +/* Determine an integral upper bound on the value of EXPR in LOOP. The + expression is considered to be unsigned. If its type is signed, its + value must be nonnegative. + + TODO -- much of this duplicates work of VRP (admitedly in much simpler + way, since we do not need to handle everything, and only care about + nonnegative values). Perhaps some code sharing would be possible? */ + +static double_int +derive_integral_bound (struct loop *loop, tree expr) +{ + tree type = TREE_TYPE (expr), op0, op1, cst, subtype; + double_int bnd, val, max, mmax; + unsigned prec = TYPE_PRECISION (type); + + /* Set to the number of bits of the largest positive value. */ + if (!TYPE_UNSIGNED (type)) + prec--; + max = double_int_mask (prec); + + switch (TREE_CODE (expr)) + { + case INTEGER_CST: + return tree_to_double_int (expr); + + case NOP_EXPR: + case CONVERT_EXPR: + op0 = TREE_OPERAND (expr, 0); + subtype = TREE_TYPE (op0); + if (!TYPE_UNSIGNED (subtype) + /* If TYPE is also signed, the fact that EXPR is nonnegative implies + that OP0 is nonnegative. */ + && TYPE_UNSIGNED (type) + && !nonnegative_in_loop_p (loop, op0)) + { + /* If we cannot prove that the casted expression is nonnegative, + we cannot establish more useful upper bound than the precision + of the type gives us. */ + return max; + } + + /* We now know that op0 is an nonnegative value. Try deriving an upper + bound for it. */ + bnd = derive_integral_bound (loop, op0); + + /* If the bound does not fit in TYPE, max. value of TYPE could be + attained. */ + if (double_int_smaller_p (max, bnd)) + return max; + + return bnd; + + case PLUS_EXPR: + case MINUS_EXPR: + op0 = TREE_OPERAND (expr, 0); + op1 = TREE_OPERAND (expr, 1); + + if (TREE_CODE (op1) != INTEGER_CST + || !nonnegative_in_loop_p (loop, op0)) + return max;; + + /* Canonicalize to OP0 - CST. */ + if (TREE_CODE (expr) == PLUS_EXPR) + cst = fold_build1 (NEGATE_EXPR, type, op1); + else + cst = op1; + + bnd = derive_integral_bound (loop, op0); + + if (tree_int_cst_sign_bit (cst)) + { + cst = fold_build1 (NEGATE_EXPR, type, cst); + if (tree_int_cst_sign_bit (cst)) + return max;; + val = tree_to_double_int (cst); + + /* Case OP0 + CST. We need to check that + BND <= MAX (type) - CST. */ + + mmax = double_int_add (double_int_all (), max, + double_int_negate (double_int_all (), val)); + if (double_int_smaller_p (mmax, bnd)) + return max; + + return double_int_add (double_int_all (), bnd, val); + } + else + { + val = tree_to_double_int (cst); + if (double_int_smaller_p (bnd, val)) + return max; + + bnd = double_int_add (double_int_all (), bnd, + double_int_negate (double_int_all (), val)); + } + + return bnd; + + case FLOOR_DIV_EXPR: + case EXACT_DIV_EXPR: + op0 = TREE_OPERAND (expr, 0); + op1 = TREE_OPERAND (expr, 1); + if (TREE_CODE (op1) != INTEGER_CST + || tree_int_cst_sign_bit (op1)) + return max; + + bnd = derive_integral_bound (loop, op0); + return double_int_divide (bnd, tree_to_double_int (op1)); + + default: + return max; + } +} + +/* Returns true if the fact that IV does not overflow in LOOP + implies that basic induction variable BASE + STEP * iteration + evaluated at AT_STMT does not overflow. */ + +static bool +nonwrapping_due_to (struct loop *loop, struct iv_no_overflow *iv, + tree base, tree step, tree at_stmt) +{ + tree iv_type = TREE_TYPE (iv->base), type = TREE_TYPE (base); + + if (!at_stmt) + at_stmt = first_stmt (loop->header); + + /* To be sure that the fact that IV does not overflow implies that + the considered induction variable does not overflow, we need to + know that in the iteration when AT_STMT is evaluated, IV is + evaluated as well. We could be more aggressive, but the + dominance test should cover most useful cases. */ + if (!dominated_by_p (CDI_DOMINATORS, bb_for_stmt (at_stmt), + bb_for_stmt (iv->at_stmt))) + return false; + + /* TODO -- handle the cases when: + -- signedness differs, but step is positive + -- signedness differs, iv is unsigned, and step is negative + -- type of iv is narrower */ + if (TYPE_UNSIGNED (iv_type) == TYPE_UNSIGNED (type) + && operand_equal_p (iv->step, step, 0)) + { + enum tree_code cmp = tree_int_cst_sign_bit (step) ? GE_EXPR : LE_EXPR; + return nonzero_p (fold_build2 (cmp, boolean_type_node, base, iv->base)); + } + + return false; +} + +/* Returns true if we can prove that induction variable BASE + STEP * i + evaluated in statement AT_STMT in LOOP does not wrap. */ + +static bool +in_nonwrapping_ivs_list_p (struct loop *loop, tree base, tree step, + tree at_stmt) +{ + struct iv_no_overflow *elt; + + for (elt = loop->iv_no_overflow; elt; elt = elt->next) + if (nonwrapping_due_to (loop, elt, base, step, at_stmt)) + return true; + + return false; +} + +/* Records that number of executions of the latch of the LOOP is at most + BOUND. LATCH_EXECS is true if this is number of executions of the latch + edge, i.e., the number we want to record. Otherwise BOUND is upper bound + on number of executions of some statement in loop body, and # of executions + of latch may be BOUNDS + 1. */ + +void +record_niter_bound (struct loop *loop, tree bound, bool latch_execs) +{ + double_int int_bound; + + gcc_assert (loop->niter_bounds_state == NBS_RECORDING); + int_bound = derive_integral_bound (loop, bound); + + if (!latch_execs) + { + int_bound = double_int_add (double_int_all (), int_bound, + hwi_to_double_int (1)); + /* If an overflow occurs, give up. */ + if (double_int_zero_p (int_bound)) + return; + } + + if (loop->is_finite + && !double_int_smaller_p (int_bound, loop->max_nb_iterations)) + return; + + loop->is_finite = true; + loop->max_nb_iterations = int_bound; + if (dump_file && (dump_flags & TDF_ANALYSIS)) + { + fprintf (dump_file, "Upper bound on # of iterations of loop %d is ", loop->num); + dump_double_int (dump_file, double_int_all (), int_bound, false); + fprintf (dump_file, "\n"); + } +} + +/* Records that induction variable BASE + STEP * i evaluated in AT_STMT does + not wrap in LOOP and falls within range LOW ... HIGH. */ void -record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt) +record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree at_stmt, + tree low, tree high) { - struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); + struct iv_no_overflow *elt = xmalloc (sizeof (struct iv_no_overflow)); + tree niter_bound, extreme, delta; + tree type = TREE_TYPE (base), unsigned_type = unsigned_type_for (type); - if (dump_file && (dump_flags & TDF_DETAILS)) + gcc_assert (loop->niter_bounds_state == NBS_RECORDING); + + if (TREE_CODE (step) != INTEGER_CST || zero_p (step)) + return; + + if (dump_file && (dump_flags & TDF_ANALYSIS)) { - fprintf (dump_file, "Statements after "); + fprintf (dump_file, "Induction variable ("); + print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM); + fprintf (dump_file, ") "); + print_generic_expr (dump_file, base, TDF_SLIM); + fprintf (dump_file, " + "); + print_generic_expr (dump_file, step, TDF_SLIM); + fprintf (dump_file, " * iteration does not wrap in statement "); print_generic_expr (dump_file, at_stmt, TDF_SLIM); - fprintf (dump_file, " are executed at most "); - print_generic_expr (dump_file, bound, TDF_SLIM); - fprintf (dump_file, " times in loop %d.\n", loop->num); + fprintf (dump_file, " in loop %d.\n", loop->num); } - elt->bound = bound; + /* Record that the variable does not wrap. */ + elt->base = base; + elt->step = step; elt->at_stmt = at_stmt; - elt->additional = additional; - elt->next = loop->bounds; - loop->bounds = elt; + elt->next = loop->iv_no_overflow; + loop->iv_no_overflow = elt; + + /* Record also the derived estimate on number of iterations of the loop. + Make the base constant if it is not altready, using the fact that the + iv stays in the given bounds. Do it only if we are sure iv is evaluated + in each iteration. */ + + if (!just_once_each_iteration_p (loop, bb_for_stmt (at_stmt))) + return; + + base = fold_convert (unsigned_type, base); + step = fold_convert (unsigned_type, step); + if (tree_int_cst_sign_bit (step)) + { + extreme = fold_convert (unsigned_type, low); + delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); + step = fold_build1 (NEGATE_EXPR, unsigned_type, step); + if (TREE_CODE (base) != INTEGER_CST) + base = fold_convert (unsigned_type, high); + } + else + { + extreme = fold_convert (unsigned_type, high); + delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); + if (TREE_CODE (base) != INTEGER_CST) + base = fold_convert (unsigned_type, low); + } + + /* AT_STMT (and therefore also loop latch) is executed at most + NITER_BOUND + 1 times, since otherwise the value would wrap. + TODO: In case AT_STMT is before all loop exits, we could bound this + number by NITER_BOUND. */ + niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); + record_niter_bound (loop, niter_bound, false); } -/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe - approximation of the number of iterations for LOOP. */ +/* Determine information about number of iterations of a loop from the way + arrays are used in STMT. */ static void -compute_estimated_nb_iterations (struct loop *loop) +infer_loop_bounds_from_array (tree stmt) { - struct nb_iter_bound *bound; - - for (bound = loop->bounds; bound; bound = bound->next) - if (TREE_CODE (bound->bound) == INTEGER_CST - /* Update only when there is no previous estimation. */ - && (chrec_contains_undetermined (loop->estimated_nb_iterations) - /* Or when the current estimation is smaller. */ - || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))) - loop->estimated_nb_iterations = bound->bound; + if (TREE_CODE (stmt) == MODIFY_EXPR) + { + tree op0 = TREE_OPERAND (stmt, 0); + tree op1 = TREE_OPERAND (stmt, 1); + + /* For each array access, analyze its access function + and record a bound on the loop iteration domain. */ + if (TREE_CODE (op1) == ARRAY_REF) + analyze_array (stmt, op1, true); + + if (TREE_CODE (op0) == ARRAY_REF) + analyze_array (stmt, op0, false); + } + else if (TREE_CODE (stmt) == CALL_EXPR) + { + tree args; + + for (args = TREE_OPERAND (stmt, 1); args; args = TREE_CHAIN (args)) + if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF) + analyze_array (stmt, TREE_VALUE (args), true); + } +} + +/* Determine information about number of iterations of a LOOP from the fact + that signed arithmetics does not overflow. */ + +static void +infer_loop_bounds_from_signedness (struct loop *loop, tree stmt) +{ + tree def, base, step, scev, type, low, high; + + if (flag_wrapv || TREE_CODE (stmt) != MODIFY_EXPR) + return; + + def = TREE_OPERAND (stmt, 0); + + if (TREE_CODE (def) != SSA_NAME) + return; + + type = TREE_TYPE (def); + if (!INTEGRAL_TYPE_P (type) + || TYPE_UNSIGNED (type)) + return; + + scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); + if (chrec_contains_undetermined (scev)) + return; + + base = initial_condition_in_loop_num (scev, loop->num); + step = evolution_part_in_loop_num (scev, loop->num); + + if (!base || !step + || TREE_CODE (step) != INTEGER_CST + || tree_contains_chrecs (base, NULL) + || chrec_contains_symbols_defined_in_loop (base, loop->num)) + return; + + low = lower_bound_in_type (type, type); + high = upper_bound_in_type (type, type); + + record_nonwrapping_iv (loop, base, step, stmt, low, high); } /* The following analyzers are extracting informations on the bounds @@ -1394,84 +1707,10 @@ infer_loop_bounds_from_undefined (struct loop *loop) { tree stmt = bsi_stmt (bsi); - switch (TREE_CODE (stmt)) - { - case MODIFY_EXPR: - { - tree op0 = TREE_OPERAND (stmt, 0); - tree op1 = TREE_OPERAND (stmt, 1); - - /* For each array access, analyze its access function - and record a bound on the loop iteration domain. */ - if (TREE_CODE (op1) == ARRAY_REF) - analyze_array (stmt, op1, true); - - if (TREE_CODE (op0) == ARRAY_REF) - analyze_array (stmt, op0, false); - - /* For each signed type variable in LOOP, analyze its - scalar evolution and record a bound of the loop - based on the type's ranges. */ - else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME) - { - tree init, step, diff, estimation; - tree scev = instantiate_parameters - (loop, analyze_scalar_evolution (loop, op0)); - tree type = chrec_type (scev); - tree utype; - - if (chrec_contains_undetermined (scev) - || TYPE_UNSIGNED (type)) - break; - - init = initial_condition_in_loop_num (scev, loop->num); - step = evolution_part_in_loop_num (scev, loop->num); - - if (init == NULL_TREE - || step == NULL_TREE - || TREE_CODE (init) != INTEGER_CST - || TREE_CODE (step) != INTEGER_CST - || TYPE_MIN_VALUE (type) == NULL_TREE - || TYPE_MAX_VALUE (type) == NULL_TREE) - break; - - utype = unsigned_type_for (type); - if (tree_int_cst_lt (step, integer_zero_node)) - diff = fold_build2 (MINUS_EXPR, utype, init, - TYPE_MIN_VALUE (type)); - else - diff = fold_build2 (MINUS_EXPR, utype, - TYPE_MAX_VALUE (type), init); - - estimation = fold_build2 (CEIL_DIV_EXPR, utype, diff, - step); - record_estimate (loop, estimation, boolean_true_node, stmt); - } - - break; - } - - case CALL_EXPR: - { - tree args; - - for (args = TREE_OPERAND (stmt, 1); args; - args = TREE_CHAIN (args)) - if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF) - analyze_array (stmt, TREE_VALUE (args), true); - - break; - } - - default: - break; - } + infer_loop_bounds_from_array (stmt); + infer_loop_bounds_from_signedness (loop, stmt); } - - if (chrec_contains_undetermined (loop->estimated_nb_iterations)) - compute_estimated_nb_iterations (loop); } - free (bbs); } @@ -1486,13 +1725,14 @@ estimate_numbers_of_iterations_loop (struct loop *loop) struct tree_niter_desc niter_desc; /* Give up if we already have tried to compute an estimation. */ - if (loop->estimated_nb_iterations == chrec_dont_know - /* Or when we already have an estimation. */ - || (loop->estimated_nb_iterations != NULL_TREE - && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST)) + if (loop->niter_bounds_state == NBS_READY + /* Scev and # of iterations analysis and bound estimation are a quite + messy mutually recursive code. It probably may happen that bounds + estimation will get called via scev analysis from within bounds + estimation, so prevent infinite cycle. */ + || loop->niter_bounds_state == NBS_RECORDING) return; - else - loop->estimated_nb_iterations = chrec_dont_know; + loop->niter_bounds_state = NBS_RECORDING; exits = get_loop_exit_edges (loop, &n_exits); for (i = 0; i < n_exits; i++) @@ -1507,14 +1747,16 @@ estimate_numbers_of_iterations_loop (struct loop *loop) niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, build_int_cst_type (type, 0), niter); - record_estimate (loop, niter, - niter_desc.additional_info, - last_stmt (exits[i]->src)); + + /* TODO: # of iterations analysis often determines that the control + induction variable does not wrap. If that happens, record this + fact. */ + record_niter_bound (loop, niter, true); } free (exits); - if (chrec_contains_undetermined (loop->estimated_nb_iterations)) - infer_loop_bounds_from_undefined (loop); + infer_loop_bounds_from_undefined (loop); + loop->niter_bounds_state = NBS_READY; } /* Records estimates on numbers of iterations of LOOPS. */ @@ -1560,95 +1802,31 @@ compare_trees (tree a, tree b) return 2; } -/* Returns true if statement S1 dominates statement S2. */ +/* Returns true if we can prove that number of executions of AT_STMT + in LOOP is at most VAL. */ -static bool -stmt_dominates_stmt_p (tree s1, tree s2) +bool +loop_iterations_at_most_p (struct loop *loop, tree val, + tree at_stmt ATTRIBUTE_UNUSED) { - basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2); + tree type = TREE_TYPE (val), nit; - if (!bb1 - || s1 == s2) - return true; + gcc_assert (TYPE_UNSIGNED (type)); - if (bb1 == bb2) - { - block_stmt_iterator bsi; - - for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi)) - if (bsi_stmt (bsi) == s1) - return true; + estimate_numbers_of_iterations_loop (loop); + if (!loop->is_finite) + return false; + if (!double_int_fits_to_type_p (type, loop->max_nb_iterations)) + { + /* If # of iterations is greater than anything what can possibly + fit into type, fail. */ return false; } - - return dominated_by_p (CDI_DOMINATORS, bb2, bb1); -} - -/* 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. - - 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) - do - { - something; - } while (++i < n) - - If the n > 0 condition is taken into account, the number of iterations of the - loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL - 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 bool -proved_non_wrapping_p (tree at_stmt, - struct nb_iter_bound *niter_bound, - tree new_type, - tree valid_niter) -{ - tree cond; - tree bound = niter_bound->bound; - enum tree_code cmp; - - 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); - - /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434. */ - if (TREE_CODE (bound) != INTEGER_CST) - return false; - - /* 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)) - cmp = GE_EXPR; - /* Before the statement niter_bound->at_stmt we know that anything - is executed at most BOUND + 1 times. */ - else - cmp = GT_EXPR; - - cond = fold_binary (cmp, boolean_type_node, valid_niter, bound); - if (nonzero_p (cond)) - return true; - - cond = build2 (cmp, boolean_type_node, valid_niter, bound); - /* Try taking additional conditions into account. */ - cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node, - invert_truthvalue (niter_bound->additional), - cond); - - if (nonzero_p (cond)) + nit = double_int_to_tree (type, loop->max_nb_iterations); + if (condition_holds_in_loop_p (loop, + fold_build2 (LE_EXPR, boolean_type_node, + nit, val))) return true; return false; @@ -1664,7 +1842,6 @@ 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; @@ -1694,47 +1871,56 @@ convert_step_widening (struct loop *loop, tree new_type, tree base, tree step, if (TREE_CODE (step_in_new_type) != INTEGER_CST) return NULL_TREE; - switch (compare_trees (base_plus_step_in_new_type, base_in_new_type)) - { - case -1: - { - 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; - } + /* If the new step is zero, there is nothing to do. */ + if (zero_p (step_in_new_type)) + return step_in_new_type; - case 1: - { - 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; - } + /* Check whether the iv is nonwrapping by comparing it with the list + of ivs we know not to wrap. */ + if (!in_nonwrapping_ivs_list_p (loop, base, step, at_stmt)) + { + /* If this fails, try using estimates on number of iterations of + the loop. */ - case 0: - return step_in_new_type; + switch (compare_trees (base_plus_step_in_new_type, base_in_new_type)) + { + case -1: + { + 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; + } - default: - return NULL_TREE; - } + case 1: + { + 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; + } - unsigned_type = unsigned_type_for (new_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); + case 0: + /* This should not happen, since we checked for zero step + earlier. */ + gcc_unreachable (); - estimate_numbers_of_iterations_loop (loop); - 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; + default: + return NULL_TREE; + } + unsigned_type = unsigned_type_for (new_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); + + if (!loop_iterations_at_most_p (loop, valid_niter, at_stmt)) + return NULL_TREE; + } - /* Fail when the loop has no bound estimations, or when no bound can - be used for verifying the conversion. */ - return NULL_TREE; + return step_in_new_type; } /* Returns true when VAR is used in pointer arithmetics. DEPTH is @@ -1790,7 +1976,6 @@ scev_probably_wraps_p (tree type, tree base, tree step, tree at_stmt, struct loop *loop, bool *init_is_max, bool *unknown_max) { - struct nb_iter_bound *bound; tree delta, step_abs; tree unsigned_type, valid_niter; tree base_plus_step, bpsps; @@ -1929,10 +2114,8 @@ scev_probably_wraps_p (tree type, tree base, tree step, step_abs = fold_convert (unsigned_type, step_abs); valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); - estimate_numbers_of_iterations_loop (loop); - for (bound = loop->bounds; bound; bound = bound->next) - if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) - return false; + if (loop_iterations_at_most_p (loop, valid_niter, at_stmt)) + return false; /* At this point we still don't have a proof that the iv does not overflow: give up. */ @@ -1965,15 +2148,15 @@ convert_step (struct loop *loop, tree new_type, tree base, tree step, static void free_numbers_of_iterations_estimates_loop (struct loop *loop) { - struct nb_iter_bound *bound, *next; + struct iv_no_overflow *iv, *next; - for (bound = loop->bounds; bound; bound = next) + for (iv = loop->iv_no_overflow; iv; iv = next) { - next = bound->next; - free (bound); + next = iv->next; + free (iv); } - loop->bounds = NULL; + loop->iv_no_overflow = NULL; } /* Frees the information on upper bounds on numbers of iterations of LOOPS. */ @@ -1998,14 +2181,35 @@ free_numbers_of_iterations_estimates (struct loops *loops) void substitute_in_loop_info (struct loop *loop, tree name, tree val) { - struct nb_iter_bound *bound; + struct iv_no_overflow *iv; loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); - loop->estimated_nb_iterations - = simplify_replace_tree (loop->estimated_nb_iterations, name, val); - for (bound = loop->bounds; bound; bound = bound->next) + for (iv = loop->iv_no_overflow; iv; iv = iv->next) { - bound->bound = simplify_replace_tree (bound->bound, name, val); - bound->additional = simplify_replace_tree (bound->additional, name, val); + iv->base = simplify_replace_tree (iv->base, name, val); + iv->step = simplify_replace_tree (iv->step, name, val); } } + +/* Returns true if COND holds inside loop. */ + +bool +condition_holds_in_loop_p (struct loop *loop, tree cond) +{ + return nonzero_p (simplify_using_initial_conditions (loop, cond)); +} + +/* If estimated number of iterations of LOOP fits in host_wide_int, + it is stored in NITER and true is returned. Otherwise false is returned. */ + +bool +get_max_loop_niter (struct loop *loop, unsigned HOST_WIDE_INT *niter) +{ + if (loop->niter_bounds_state == NBS_NONE + || !loop->is_finite + || !double_int_fits_in_unsigned_hwi_p (loop->max_nb_iterations)) + return false; + + *niter = double_int_to_unsigned_hwi (loop->max_nb_iterations); + return true; +} |