This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[killloop] Condition selection and bounds on # of iterations
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 5 Oct 2005 13:26:15 +0200
- Subject: [killloop] Condition selection and bounds on # of iterations
Hello,
this patch:
-- makes condition shape selection use bounds on # of iterations
estimations, which should make it actually useful for non-constant
rolling loops
-- cleans up bounds on # of iterations analysis and its usage
-- removes decl_rtl_to_reset hack from ivopts.
All the functionality I wanted is now enabled in the branch (except for loop
reversal, which still causes misscompilations due to data dependence
analysis problem). It of course needs lots of testing and tuning, but
everything should be ready to removal of the old loop optimizer.
Zdenek
* 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.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1530.2.8
diff -c -3 -p -r1.1530.2.8 Makefile.in
*** Makefile.in 20 Sep 2005 12:01:21 -0000 1.1530.2.8
--- Makefile.in 4 Oct 2005 23:13:41 -0000
*************** tree-ssa-loop-niter.o : tree-ssa-loop-ni
*** 1880,1886 ****
$(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
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) \
--- 1880,1886 ----
$(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 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) \
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.48.2.4
diff -c -3 -p -r1.48.2.4 cfgloop.h
*** cfgloop.h 20 Sep 2005 12:01:25 -0000 1.48.2.4
--- cfgloop.h 4 Oct 2005 23:13:41 -0000
*************** struct lpt_decision
*** 43,61 ****
unsigned times;
};
! /* The structure describing a bound on number of iterations of a loop. */
! 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. */
! };
/* Structure to hold information for each natural loop. */
struct loop
--- 43,51 ----
unsigned times;
};
! /* The structure describing an induction variable that does not overflow. */
! struct iv_no_overflow;
/* Structure to hold information for each natural loop. */
struct loop
*************** struct loop
*** 151,169 ****
loops nested inside it. */
int exit_count;
! /* The probable 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;
! /* Upper bound on number of iterations of a loop. */
! struct nb_iter_bound *bounds;
/* If not NULL, loop has just single exit edge stored here (edges to the
EXIT_BLOCK_PTR do not count. */
--- 141,171 ----
loops nested inside it. */
int exit_count;
! /* 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;
! /* 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;
!
! /* 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. */
*************** enum
*** 452,458 ****
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. */
--- 454,459 ----
Index: hwint.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/hwint.h,v
retrieving revision 1.20.22.1
diff -c -3 -p -r1.20.22.1 hwint.h
*** hwint.h 2 Sep 2005 16:42:17 -0000 1.20.22.1
--- hwint.h 4 Oct 2005 23:13:41 -0000
*************** extern char sizeof_long_long_must_be_8[s
*** 147,150 ****
--- 147,157 ----
# 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 */
Index: tree-affine.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-affine.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tree-affine.c
*** tree-affine.c 9 Sep 2005 16:52:21 -0000 1.1.2.1
--- tree-affine.c 4 Oct 2005 23:13:41 -0000
*************** Software Foundation, 51 Franklin Street,
*** 34,84 ****
/* Restricts constant CST according to precision of combination COMB. */
static inline double_int
! restrict_cst_to_precision (aff_tree *comb, double_int cst)
{
double_int r;
! r.low = cst.low & comb->mask.low;
! r.high = cst.high & comb->mask.high;
return r;
}
/* Returns true if X fits in HOST_WIDE_INT, with respect to precision
! of COMB. */
bool
! double_int_fits_in_hwi_p (aff_tree *comb, double_int x)
{
! return x.high == comb->mask.high;
}
! /* Returns true if SCALE is negative in precision of COMB. */
bool
! double_int_negative_p (aff_tree *comb, double_int scale)
{
! if (comb->mask.high)
! return (scale.high & ~(comb->mask.high >> 1)) != 0;
else
! return (scale.low & ~(comb->mask.low >> 1)) != 0;
}
! /* Returns value of X with respect to precision of COMB. */
HOST_WIDE_INT
! double_int_to_hwi (aff_tree *comb, double_int x)
{
! if (comb->mask.high || !double_int_negative_p (comb, x))
return x.low;
else
! return x.low | ~comb->mask.low;
}
! /* Returns A * B, truncated so that it fits COMB. */
double_int
! double_int_mul (aff_tree *comb, double_int a, double_int b)
{
unsigned HOST_WIDE_INT lo;
HOST_WIDE_INT hi;
--- 34,103 ----
/* Restricts constant CST according to precision of combination COMB. */
static inline double_int
! restrict_cst_to_precision (double_int mask, double_int cst)
{
double_int r;
! 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 MASK. */
bool
! double_int_fits_in_hwi_p (double_int mask, double_int x)
{
! 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 X fits in unsigned HOST_WIDE_INT. */
bool
! double_int_fits_in_unsigned_hwi_p (double_int x)
{
! 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 & ~(mask.low >> 1)) != 0;
}
! /* Returns value of X with respect to precision of MASK. */
HOST_WIDE_INT
! double_int_to_hwi (double_int mask, double_int x)
{
! if (mask.high || !double_int_negative_p (mask, x))
return x.low;
else
! return x.low | ~mask.low;
}
! /* 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 (double_int mask, double_int a, double_int b)
{
unsigned HOST_WIDE_INT lo;
HOST_WIDE_INT hi;
*************** double_int_mul (aff_tree *comb, double_i
*** 88,100 ****
ret.low = lo;
ret.high = hi;
! return restrict_cst_to_precision (comb, ret);
}
! /* Returns A + B, truncated so that it fits COMB. */
double_int
! double_int_add (aff_tree *comb, double_int a, double_int b)
{
unsigned HOST_WIDE_INT lo;
HOST_WIDE_INT hi;
--- 107,119 ----
ret.low = lo;
ret.high = hi;
! return restrict_cst_to_precision (mask, ret);
}
! /* Returns A + B, truncated so that it fits MASK. */
double_int
! double_int_add (double_int mask, double_int a, double_int b)
{
unsigned HOST_WIDE_INT lo;
HOST_WIDE_INT hi;
*************** double_int_add (aff_tree *comb, double_i
*** 104,116 ****
ret.low = lo;
ret.high = hi;
! return restrict_cst_to_precision (comb, ret);
}
! /* Returns -A, truncated so that it fits COMB. */
double_int
! double_int_negate (aff_tree *comb, double_int a)
{
unsigned HOST_WIDE_INT lo;
HOST_WIDE_INT hi;
--- 123,135 ----
ret.low = lo;
ret.high = hi;
! return restrict_cst_to_precision (mask, ret);
}
! /* Returns -A, truncated so that it fits MASK. */
double_int
! double_int_negate (double_int mask, double_int a)
{
unsigned HOST_WIDE_INT lo;
HOST_WIDE_INT hi;
*************** double_int_negate (aff_tree *comb, doubl
*** 120,128 ****
ret.low = lo;
ret.high = hi;
! return restrict_cst_to_precision (comb, ret);
}
/* Constructs tree in type TYPE from double_int CST. */
tree
--- 139,163 ----
ret.low = lo;
ret.high = hi;
! 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
*************** double_int_to_tree (tree type, double_in
*** 153,176 ****
return build_int_cst_wide (type, lo, hi);
}
! /* Initializes mask of COMB according to its type. */
! static void
! affine_combination_set_mask (aff_tree *comb)
{
! unsigned prec = TYPE_PRECISION (comb->type);
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;
}
else
{
! comb->mask.high = 0;
! comb->mask.low = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
}
}
/* Initializes affine combination COMB so that its value is zero in TYPE. */
--- 188,281 ----
return build_int_cst_wide (type, lo, hi);
}
! /* Returns true if VAL is smaller or equal to the maximal value
! representable in TYPE. */
! 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 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;
! mask.high = (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1);
! mask.low = ~(unsigned HOST_WIDE_INT) 0;
}
else
{
! 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. */
*************** static void
*** 179,185 ****
aff_combination_zero (aff_tree *comb, tree type)
{
comb->type = type;
! affine_combination_set_mask (comb);
comb->offset.low = 0;
comb->offset.high = 0;
--- 284,290 ----
aff_combination_zero (aff_tree *comb, tree type)
{
comb->type = type;
! comb->mask = double_int_mask (TYPE_PRECISION (type));
comb->offset.low = 0;
comb->offset.high = 0;
*************** void
*** 193,199 ****
aff_combination_const (aff_tree *comb, tree type, double_int cst)
{
aff_combination_zero (comb, type);
! comb->offset = restrict_cst_to_precision (comb, cst);
}
/* Sets COMB to single element ELT. */
--- 298,304 ----
aff_combination_const (aff_tree *comb, tree type, double_int cst)
{
aff_combination_zero (comb, type);
! comb->offset = restrict_cst_to_precision (comb->mask, cst);
}
/* Sets COMB to single element ELT. */
*************** aff_combination_scale (aff_tree *comb, d
*** 215,221 ****
{
unsigned i, j;
! scale = restrict_cst_to_precision (comb, scale);
if (double_int_one_p (scale))
return;
--- 320,326 ----
{
unsigned i, j;
! scale = restrict_cst_to_precision (comb->mask, scale);
if (double_int_one_p (scale))
return;
*************** aff_combination_scale (aff_tree *comb, d
*** 225,234 ****
return;
}
! comb->offset = double_int_mul (comb, scale, comb->offset);
for (i = 0, j = 0; i < comb->n; i++)
{
! comb->coefs[j] = double_int_mul (comb, scale, comb->coefs[i]);
comb->elts[j] = comb->elts[i];
/* A coefficient may become zero due to overflow. Remove the zero
elements. */
--- 330,339 ----
return;
}
! 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->mask, scale, comb->coefs[i]);
comb->elts[j] = comb->elts[i];
/* A coefficient may become zero due to overflow. Remove the zero
elements. */
*************** aff_combination_add_elt (aff_tree *comb,
*** 265,271 ****
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);
if (!double_int_zero_p (comb->coefs[i]))
return;
--- 370,376 ----
for (i = 0; i < comb->n; i++)
if (operand_equal_p (comb->elts[i], elt, 0))
{
! comb->coefs[i] = double_int_add (comb->mask, comb->coefs[i], scale);
if (!double_int_zero_p (comb->coefs[i]))
return;
*************** aff_combination_add (aff_tree *comb1, af
*** 302,308 ****
{
unsigned i;
! comb1->offset = double_int_add (comb1, 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)
--- 407,413 ----
{
unsigned i;
! 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)
*************** aff_combination_convert (aff_tree *comb,
*** 324,335 ****
if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
return;
! affine_combination_set_mask (comb);
! comb->offset = restrict_cst_to_precision (comb, comb->offset);
for (i = j = 0; i < comb->n; i++)
{
! comb->coefs[j] = restrict_cst_to_precision (comb, comb->coefs[i]);
if (double_int_zero_p (comb->coefs[j]))
continue;
comb->elts[j] = fold_convert (type, comb->elts[i]);
--- 429,440 ----
if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type))
return;
! comb->mask = double_int_mask (TYPE_PRECISION (type));
! 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->mask, comb->coefs[i]);
if (double_int_zero_p (comb->coefs[j]))
continue;
comb->elts[j] = fold_convert (type, comb->elts[i]);
*************** add_elt_to_tree (tree expr, tree type, t
*** 428,434 ****
{
enum tree_code code;
! scale = restrict_cst_to_precision (comb, scale);
elt = fold_convert (type, elt);
if (double_int_one_p (scale))
--- 533,539 ----
{
enum tree_code code;
! scale = restrict_cst_to_precision (comb->mask, scale);
elt = fold_convert (type, elt);
if (double_int_one_p (scale))
*************** add_elt_to_tree (tree expr, tree type, t
*** 439,445 ****
return fold_build2 (PLUS_EXPR, type, expr, elt);
}
! if (double_int_minus_one_p (comb, scale))
{
if (!expr)
return fold_build1 (NEGATE_EXPR, type, elt);
--- 544,550 ----
return fold_build2 (PLUS_EXPR, type, expr, elt);
}
! if (double_int_minus_one_p (comb->mask, scale))
{
if (!expr)
return fold_build1 (NEGATE_EXPR, type, elt);
*************** add_elt_to_tree (tree expr, tree type, t
*** 451,460 ****
return fold_build2 (MULT_EXPR, type, elt,
double_int_to_tree (type, scale));
! if (double_int_negative_p (comb, scale))
{
code = MINUS_EXPR;
! scale = double_int_negate (comb, scale);
}
else
code = PLUS_EXPR;
--- 556,565 ----
return fold_build2 (MULT_EXPR, type, elt,
double_int_to_tree (type, scale));
! if (double_int_negative_p (comb->mask, scale))
{
code = MINUS_EXPR;
! scale = double_int_negate (comb->mask, scale);
}
else
code = PLUS_EXPR;
*************** aff_combination_to_tree (aff_tree *comb)
*** 479,488 ****
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))
{
/* Offset is negative. */
! off = double_int_negate (comb, comb->offset);
sgn = comb->mask;
}
else
--- 584,593 ----
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->mask, comb->offset))
{
/* Offset is negative. */
! off = double_int_negate (comb->mask, comb->offset);
sgn = comb->mask;
}
else
Index: tree-affine.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-affine.h,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tree-affine.h
*** tree-affine.h 9 Sep 2005 16:52:21 -0000 1.1.2.1
--- tree-affine.h 4 Oct 2005 23:13:41 -0000
*************** along with GCC; see the file COPYING. I
*** 18,30 ****
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. */
--- 18,23 ----
*************** void tree_to_aff_combination (tree, tree
*** 66,77 ****
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);
/* Constructs double_int from tree CST. */
--- 59,77 ----
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_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. */
*************** hwi_to_double_int (HOST_WIDE_INT cst)
*** 99,104 ****
--- 99,112 ----
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
*************** double_int_one_p (double_int cst)
*** 115,126 ****
return cst.low == 1 && cst.high == 0;
}
! /* Returns true if CST is minus one in precision of COMB. */
static inline bool
! double_int_minus_one_p (aff_tree *comb, double_int cst)
{
! return cst.low == comb->mask.low && cst.high == comb->mask.high;
}
/* Returns true if CST1 == CST2. */
--- 123,134 ----
return cst.low == 1 && cst.high == 0;
}
! /* Returns true if CST is minus one in precision of MASK. */
static inline bool
! double_int_minus_one_p (double_int mask, double_int cst)
{
! return cst.low == mask.low && cst.high == mask.high;
}
/* Returns true if CST1 == CST2. */
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.35.2.2
diff -c -3 -p -r2.35.2.2 tree-data-ref.c
*** tree-data-ref.c 15 Sep 2005 08:29:52 -0000 2.35.2.2
--- tree-data-ref.c 4 Oct 2005 23:13:42 -0000
*************** estimate_niter_from_size_of_data (struct
*** 749,799 ****
tree access_fn,
tree stmt)
{
! tree estimation = NULL_TREE;
! tree array_size, data_size, element_size;
! tree init, step;
init = initial_condition (access_fn);
step = evolution_part_in_loop_num (access_fn, loop->num);
! 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)
return;
! 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);
! }
}
/* Given an ARRAY_REF node REF, records its access functions.
--- 749,801 ----
tree access_fn,
tree stmt)
{
! 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);
! /* 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);
! 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.
*************** analyze_array_indexes (struct loop *loop
*** 820,827 ****
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);
VEC_safe_push (tree, heap, *access_fns, access_fn);
--- 822,829 ----
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
! 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);
*************** compute_overlap_steps_for_affine_1_2 (tr
*** 2358,2396 ****
{
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;
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;
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)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
--- 2360,2380 ----
{
bool xz_p, yz_p, xyz_p;
int step_x, step_y, step_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));
! 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;
*************** compute_overlap_steps_for_affine_1_2 (tr
*** 2398,2407 ****
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,
--- 2382,2387 ----
*************** analyze_subscript_affine_affine (tree ch
*** 2524,2547 ****
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)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
--- 2504,2515 ----
if (nb_vars_a == 1 && nb_vars_b == 1)
{
int step_a, step_b;
! 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;
*************** analyze_subscript_affine_affine (tree ch
*** 2549,2556 ****
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));
--- 2517,2522 ----
*************** analyze_subscript_affine_affine (tree ch
*** 2628,2651 ****
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)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
--- 2594,2605 ----
dependence. X0, Y0 are two solutions of the Diophantine
equation: chrec_a (X0) = chrec_b (Y0). */
int x0, y0;
! 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;
*************** analyze_subscript_affine_affine (tree ch
*** 2653,2660 ****
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;
--- 2607,2612 ----
*************** analyze_subscript_affine_affine (tree ch
*** 2679,2691 ****
if (i1 > 0)
{
tau1 = CEIL (-i0, i1);
! tau2 = FLOOR_DIV (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));
x0 = i1 * tau1 + i0;
y0 = j1 * tau1 + j0;
--- 2631,2643 ----
if (i1 > 0)
{
tau1 = CEIL (-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 ((int) niter - j0, j1));
x0 = i1 * tau1 + i0;
y0 = j1 * tau1 + j0;
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.130.2.5
diff -c -3 -p -r2.130.2.5 tree-flow.h
*** tree-flow.h 15 Sep 2005 08:29:53 -0000 2.130.2.5
--- tree-flow.h 4 Oct 2005 23:13:42 -0000
*************** struct tree_niter_desc
*** 693,710 ****
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 */
--- 693,698 ----
*************** struct loop *tree_ssa_loop_version (stru
*** 762,769 ****
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 *);
unsigned compare_cost (tree);
/* In tree-ssa-loop-im.c */
/* The possibilities of statement movement. */
--- 750,763 ----
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 (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. */
Index: tree-ssa-address.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-address.c,v
retrieving revision 2.3.8.2
diff -c -3 -p -r2.3.8.2 tree-ssa-address.c
*** tree-ssa-address.c 14 Sep 2005 09:44:18 -0000 2.3.8.2
--- tree-ssa-address.c 4 Oct 2005 23:13:42 -0000
*************** most_expensive_mult_to_index (struct mem
*** 395,404 ****
for (i = 0; i < addr->n; i++)
{
! if (!double_int_fits_in_hwi_p (addr, addr->coefs[i]))
continue;
! coef = double_int_to_hwi (addr, addr->coefs[i]);
if (coef == 1
|| !multiplier_allowed_in_address_p (coef))
continue;
--- 395,404 ----
for (i = 0; i < addr->n; i++)
{
! if (!double_int_fits_in_hwi_p (addr->mask, addr->coefs[i]))
continue;
! coef = double_int_to_hwi (addr->mask, addr->coefs[i]);
if (coef == 1
|| !multiplier_allowed_in_address_p (coef))
continue;
*************** most_expensive_mult_to_index (struct mem
*** 419,425 ****
for (i = j = 0; i < addr->n; i++)
{
amult = addr->coefs[i];
! amult_neg = double_int_negate (addr, amult);
if (double_int_equal_p (amult, best_mult))
op_code = PLUS_EXPR;
--- 419,425 ----
for (i = j = 0; i < addr->n; i++)
{
amult = addr->coefs[i];
! amult_neg = double_int_negate (addr->mask, amult);
if (double_int_equal_p (amult, best_mult))
op_code = PLUS_EXPR;
Index: tree-ssa-loop-endcond.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-endcond.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 tree-ssa-loop-endcond.c
*** tree-ssa-loop-endcond.c 19 Sep 2005 11:09:01 -0000 1.1.2.2
--- tree-ssa-loop-endcond.c 4 Oct 2005 23:13:42 -0000
*************** Software Foundation, 51 Franklin Street,
*** 43,57 ****
((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 */
#include "config.h"
#include "system.h"
--- 43,49 ----
((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.
! -- otherwise we use X != V compare. */
#include "config.h"
#include "system.h"
*************** iv_period (tree step)
*** 105,127 ****
return period;
}
! /* Given exit condition 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,
enum tree_code *cmp, tree *bound)
{
tree type = TREE_TYPE (step), signed_type = signed_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);
if (tree_int_cst_sign_bit (step))
{
step = fold_build1 (NEGATE_EXPR, type, step);
if (tree_int_cst_sign_bit (step))
{
--- 97,149 ----
return period;
}
! /* 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 (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))
{
*************** modify_to_compare_with_zero (tree base,
*** 135,203 ****
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)))
return false;
! *cmp = GE_EXPR;
}
else
{
/* 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)))
return false;
! *cmp = LE_EXPR;
}
!
! *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));
}
/* Determines the final value of iv with base BASE and step STEP, in loop
--- 157,225 ----
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)))
return false;
!
! /* 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)))
return false;
! 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;
}
!
return false;
! ok:
! *cmp = ok_cmp;
! *bound = signed_zero;
! return true;
}
/* Determines the final value of iv with base BASE and step STEP, in loop
*************** final_value_of_iv (tree base, tree step,
*** 225,231 ****
if we succeed. */
bool
! select_condition_shape (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;
--- 247,253 ----
if we succeed. */
bool
! 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;
*************** select_condition_shape (tree niter, tree
*** 257,275 ****
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);
! }
end:
if (exit_p)
--- 279,286 ----
if (zero_p (final))
goto end;
! /* Try transforming the condition to a compare with zero. */
! modify_to_compare_with_zero (loop, base, step, cmp, bound);
end:
if (exit_p)
*************** may_reverse_loop_p (struct loop *loop, v
*** 389,400 ****
return ret;
}
! /* 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)
{
tree bound;
enum tree_code cmp;
--- 400,412 ----
return ret;
}
! /* 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 (struct loop *loop,
! tree base, tree step, tree niter, bool reversed)
{
tree bound;
enum tree_code cmp;
*************** endcond_candidate_cost (tree base, tree
*** 405,411 ****
step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
}
! if (!select_condition_shape (niter, base, step, true, &cmp, &bound))
return 10;
return compare_cost (bound);
--- 417,423 ----
step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
}
! if (!select_condition_shape (loop, niter, base, step, true, &cmp, &bound))
return 10;
return compare_cost (bound);
*************** best_endcond_candidate_cost (struct loop
*** 442,448 ****
|| chrec_contains_symbols_defined_in_loop (base, loop->num))
continue;
! act = endcond_candidate_cost (base, step, niter, reversed);
if (act < best)
best = act;
}
--- 454,460 ----
|| chrec_contains_symbols_defined_in_loop (base, loop->num))
continue;
! act = endcond_candidate_cost (loop, base, step, niter, reversed);
if (act < best)
best = act;
}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.85.2.9
diff -c -3 -p -r2.85.2.9 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 20 Sep 2005 12:01:26 -0000 2.85.2.9
--- tree-ssa-loop-ivopts.c 4 Oct 2005 23:13:42 -0000
*************** struct iv_ca_delta
*** 322,332 ****
#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
--- 322,327 ----
*************** niter_for_exit (struct ivopts_data *data
*** 726,731 ****
--- 721,730 ----
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;
*************** tree_ssa_iv_optimize_init (struct loops
*** 773,779 ****
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
--- 772,777 ----
*************** seq_cost (rtx seq)
*** 2582,2687 ****
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
--- 2580,2585 ----
*************** get_computation_aff (struct loop *loop,
*** 2869,2875 ****
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 (&expr_aff, rat);
aff_combination_add (aff, &cbase_aff);
aff_combination_add (aff, &expr_aff);
--- 2767,2773 ----
happen, fold is able to apply the distributive law to obtain this form
anyway. */
! 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);
*************** convert_cost (enum machine_mode mode_to,
*** 3226,3303 ****
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",
GET_MODE_NAME (mode_from), GET_MODE_NAME (mode_to), cost);
return cost;
}
/* Estimates cost of forcing expression EXPR into a variable. */
unsigned
force_expr_to_var_cost (tree expr)
{
- 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;
- if (!costs_initialized)
- {
- 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);
-
- integer_cost = computation_cost (build_int_cst_type (integer_type_node,
- 2000));
-
- SET_DECL_RTL (var, x);
- TREE_STATIC (var) = 1;
- addr = build1 (ADDR_EXPR, type, var);
- symbol_cost = computation_cost (addr) + 1;
-
- 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");
- }
-
- costs_initialized = true;
- }
-
STRIP_NOPS (expr);
if (SSA_VAR_P (expr))
return 0;
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 address_cost;
}
switch (TREE_CODE (expr))
--- 3124,3200 ----
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",
GET_MODE_NAME (mode_from), GET_MODE_NAME (mode_to), cost);
return cost;
}
+ /* 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). */
+
+ static unsigned
+ integer_cost (enum machine_mode mode)
+ {
+ static unsigned costs[NUM_MACHINE_MODES];
+
+ if (!costs[mode])
+ {
+ /* TODO -- determine the cost. */
+ costs[mode] = 1;
+
+ 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;
+ }
+
+ /* 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). */
+
+ static unsigned
+ fixed_address_cost (void)
+ {
+ static unsigned cost = 0;
+
+ 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 (mode);
! /* 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))
*************** force_expr_to_var_cost (tree expr)
*** 3330,3336 ****
return target_spill_cost;
}
- mode = TYPE_MODE (TREE_TYPE (expr));
switch (TREE_CODE (expr))
{
case PLUS_EXPR:
--- 3227,3232 ----
*************** force_var_cost (struct ivopts_data *data
*** 3386,3401 ****
/* 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. */
static unsigned
aff_combination_cost (struct ivopts_data *data, aff_tree *comp,
! bitmap *depends_on)
{
int n_adds = comp->n - 1;
unsigned i, j, cost = 0;
! bool all_negated = true;
enum machine_mode mode = TYPE_MODE (comp->type);
if (comp->n == 0 && !comp->rest)
{
--- 3282,3303 ----
/* 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. 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, bool *outer_addition)
{
int n_adds = comp->n - 1;
unsigned i, j, cost = 0;
! 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)
{
*************** aff_combination_cost (struct ivopts_data
*** 3408,3463 ****
{
n_adds++;
cost += force_var_cost (data, comp->rest, depends_on);
! all_negated = false;
}
if (!double_int_zero_p (comp->offset))
{
n_adds++;
! all_negated = false;
}
! /* 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.
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. */
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]))
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_fits_in_hwi_p (comp, 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]),
mode);
}
! if (all_negated)
{
/* 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);
}
return cost + n_adds * add_cost (mode);
}
--- 3310,3385 ----
{
n_adds++;
cost += force_var_cost (data, comp->rest, depends_on);
! positive_terms++;
}
if (!double_int_zero_p (comp->offset))
{
n_adds++;
! positive_terms++;
}
! 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,
! which should usually be cheaper. */
for (i = 0; i < comp->n; i++)
{
! if (double_int_zero_p (comp->coefs[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->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->mask, comp->coefs[i]),
mode);
+
+ if (seen_positive)
+ positive_terms++;
}
! 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);
}
*************** aff_combination_cost_address (struct ivo
*** 3474,3479 ****
--- 3396,3402 ----
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++)
*************** aff_combination_cost_address (struct ivo
*** 3489,3495 ****
}
}
! if (double_int_fits_in_hwi_p (comp, ratio)
&& !double_int_one_p (ratio))
{
/* Try separating index from comp. */
--- 3412,3418 ----
}
}
! if (double_int_fits_in_hwi_p (comp->mask, ratio)
&& !double_int_one_p (ratio))
{
/* Try separating index from comp. */
*************** aff_combination_cost_address (struct ivo
*** 3499,3507 ****
if (i < comp->n)
{
! double_int ratio_neg = double_int_negate (comp, ratio);
int n_add = -1;
! rat = double_int_to_hwi (comp, ratio);
for (; i < comp->n; )
{
--- 3422,3430 ----
if (i < comp->n)
{
! double_int ratio_neg = double_int_negate (comp->mask, ratio);
int n_add = -1;
! rat = double_int_to_hwi (comp->mask, ratio);
for (; i < comp->n; )
{
*************** aff_combination_cost_address (struct ivo
*** 3525,3533 ****
if (!double_int_zero_p (comp->offset))
{
! if (double_int_fits_in_hwi_p (comp, comp->offset))
{
! off = double_int_to_hwi (comp, comp->offset);
comp->offset = hwi_to_double_int (0);
}
else
--- 3448,3456 ----
if (!double_int_zero_p (comp->offset))
{
! if (double_int_fits_in_hwi_p (comp->mask, comp->offset))
{
! off = double_int_to_hwi (comp->mask, comp->offset);
comp->offset = hwi_to_double_int (0);
}
else
*************** aff_combination_cost_address (struct ivo
*** 3538,3550 ****
if (nelts)
{
! cost += aff_combination_cost (data, comp, depends_on);
/* 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)
{
var_present = true;
cost -= add_cost (mode);
--- 3461,3473 ----
if (nelts)
{
! 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 (outer_addition)
{
var_present = true;
cost -= add_cost (mode);
*************** get_computation_cost_at (struct ivopts_d
*** 3606,3612 ****
if (address_p)
cost = aff_combination_cost_address (data, &comp, depends_on, rat);
else
! cost = aff_combination_cost (data, &comp, depends_on);
gcc_assert ((signed) cost >= 0);
return cost;
--- 3529,3535 ----
if (address_p)
cost = aff_combination_cost_address (data, &comp, depends_on, rat);
else
! cost = aff_combination_cost (data, &comp, depends_on, NULL);
gcc_assert ((signed) cost >= 0);
return cost;
*************** may_eliminate_iv (struct ivopts_data *da
*** 3722,3728 ****
if (stmt_after_increment (loop, cand, use->stmt))
base = fold_build2 (PLUS_EXPR, type, base, step);
! return select_condition_shape (niter->niter, base, step,
(exit->flags & EDGE_TRUE_VALUE) != 0,
cmp, bound);
}
--- 3645,3651 ----
if (stmt_after_increment (loop, cand, use->stmt))
base = fold_build2 (PLUS_EXPR, type, base, step);
! return select_condition_shape (loop, niter->niter, base, step,
(exit->flags & EDGE_TRUE_VALUE) != 0,
cmp, bound);
}
*************** free_loop_data (struct ivopts_data *data
*** 5616,5622 ****
{
unsigned i, j;
bitmap_iterator bi;
- tree obj;
htab_empty (data->niters);
--- 5539,5544 ----
*************** free_loop_data (struct ivopts_data *data
*** 5670,5680 ****
}
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
--- 5592,5597 ----
*************** tree_ssa_iv_optimize_finalize (struct lo
*** 5698,5704 ****
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);
}
--- 5615,5620 ----
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.33.2.2
diff -c -3 -p -r2.33.2.2 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 2 Sep 2005 16:43:15 -0000 2.33.2.2
--- tree-ssa-loop-niter.c 4 Oct 2005 23:13:42 -0000
*************** Software Foundation, 51 Franklin Street,
*** 42,47 ****
--- 42,48 ----
#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)
*************** number_of_iterations_special (tree type,
*** 475,481 ****
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))
{
--- 476,481 ----
*************** number_of_iterations_special (tree type,
*** 557,563 ****
}
niter->niter = fold_convert (niter_type, niter->niter);
- niter->additional_info = boolean_true_node;
return true;
}
--- 557,562 ----
*************** tree_simplify_using_condition (tree cond
*** 776,792 ****
}
/* 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)
{
edge e;
basic_block bb;
! tree exp, cond;
if (TREE_CODE (expr) == INTEGER_CST)
return expr;
--- 775,789 ----
}
/* Tries to simplify EXPR using the conditions on entry to LOOP.
Returns the simplified expression (or EXPR unchanged, if no
simplification was possible).*/
static tree
! simplify_using_initial_conditions (struct loop *loop, tree expr)
{
edge e;
basic_block bb;
! tree cond;
if (TREE_CODE (expr) == INTEGER_CST)
return expr;
*************** simplify_using_initial_conditions (struc
*** 805,819 ****
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;
}
return expr;
--- 802,808 ----
cond = COND_EXPR_COND (last_stmt (e->src));
if (e->flags & EDGE_FALSE_VALUE)
cond = invert_truthvalue (cond);
! expr = tree_simplify_using_condition (cond, expr);
}
return expr;
*************** number_of_iterations_exit (struct loop *
*** 956,970 ****
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);
niter->may_be_zero
! = simplify_using_initial_conditions (loop,
! niter->may_be_zero,
! &niter->additional_info);
if (integer_onep (niter->assumptions))
return true;
--- 945,954 ----
niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
}
niter->assumptions
! = simplify_using_initial_conditions (loop, niter->assumptions);
niter->may_be_zero
! = simplify_using_initial_conditions (loop, niter->may_be_zero);
if (integer_onep (niter->assumptions))
return true;
*************** find_loop_niter_by_eval (struct loop *lo
*** 1327,1371 ****
*/
! /* Records that AT_STMT is executed at most BOUND times in LOOP. The
! additional condition ADDITIONAL is recorded with the bound. */
void
! record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
{
! struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
! if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Statements after ");
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);
}
! elt->bound = bound;
elt->at_stmt = at_stmt;
! elt->additional = additional;
! elt->next = loop->bounds;
! loop->bounds = elt;
}
! /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
! approximation of the number of iterations for LOOP. */
static void
! compute_estimated_nb_iterations (struct loop *loop)
{
! 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;
}
/* The following analyzers are extracting informations on the bounds
--- 1311,1684 ----
*/
! /* 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_nonwrapping_iv (struct loop *loop, tree base, tree step, tree at_stmt,
! tree low, tree high)
! {
! 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);
!
! 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, "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, " in loop %d.\n", loop->num);
}
! /* Record that the variable does not wrap. */
! elt->base = base;
! elt->step = step;
elt->at_stmt = at_stmt;
! 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);
}
! /* Determine information about number of iterations of a loop from the way
! arrays are used in STMT. */
static void
! infer_loop_bounds_from_array (tree stmt)
{
! 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
*************** infer_loop_bounds_from_undefined (struct
*** 1394,1477 ****
{
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;
! }
}
-
- if (chrec_contains_undetermined (loop->estimated_nb_iterations))
- compute_estimated_nb_iterations (loop);
}
-
free (bbs);
}
--- 1707,1716 ----
{
tree stmt = bsi_stmt (bsi);
! infer_loop_bounds_from_array (stmt);
! infer_loop_bounds_from_signedness (loop, stmt);
}
}
free (bbs);
}
*************** estimate_numbers_of_iterations_loop (str
*** 1486,1498 ****
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))
return;
! else
! loop->estimated_nb_iterations = chrec_dont_know;
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
--- 1725,1738 ----
struct tree_niter_desc niter_desc;
/* Give up if we already have tried to compute an estimation. */
! 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;
! loop->niter_bounds_state = NBS_RECORDING;
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
*************** estimate_numbers_of_iterations_loop (str
*** 1507,1520 ****
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));
}
free (exits);
! if (chrec_contains_undetermined (loop->estimated_nb_iterations))
! infer_loop_bounds_from_undefined (loop);
}
/* Records estimates on numbers of iterations of LOOPS. */
--- 1747,1762 ----
niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
build_int_cst_type (type, 0),
niter);
!
! /* 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);
! infer_loop_bounds_from_undefined (loop);
! loop->niter_bounds_state = NBS_READY;
}
/* Records estimates on numbers of iterations of LOOPS. */
*************** compare_trees (tree a, tree b)
*** 1560,1654 ****
return 2;
}
! /* Returns true if statement S1 dominates statement S2. */
! static bool
! stmt_dominates_stmt_p (tree s1, tree s2)
{
! basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
!
! if (!bb1
! || s1 == s2)
! return true;
! 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;
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))
return true;
return false;
--- 1802,1832 ----
return 2;
}
! /* Returns true if we can prove that number of executions of AT_STMT
! in LOOP is at most VAL. */
! bool
! loop_iterations_at_most_p (struct loop *loop, tree val,
! tree at_stmt ATTRIBUTE_UNUSED)
{
! tree type = TREE_TYPE (val), nit;
! gcc_assert (TYPE_UNSIGNED (type));
! 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;
}
! 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;
*************** static tree
*** 1664,1670 ****
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;
--- 1842,1847 ----
*************** convert_step_widening (struct loop *loop
*** 1694,1740 ****
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;
! }
! 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;
! }
! case 0:
! 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);
! 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;
!
! /* Fail when the loop has no bound estimations, or when no bound can
! be used for verifying the conversion. */
! return NULL_TREE;
}
/* Returns true when VAR is used in pointer arithmetics. DEPTH is
--- 1871,1926 ----
if (TREE_CODE (step_in_new_type) != INTEGER_CST)
return NULL_TREE;
! /* If the new step is zero, there is nothing to do. */
! if (zero_p (step_in_new_type))
! return step_in_new_type;
!
! /* 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. */
! 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;
! }
! 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;
! }
! case 0:
! /* This should not happen, since we checked for zero step
! earlier. */
! gcc_unreachable ();
! 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;
! }
!
! return step_in_new_type;
}
/* Returns true when VAR is used in pointer arithmetics. DEPTH is
*************** scev_probably_wraps_p (tree type, tree b
*** 1790,1796 ****
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;
--- 1976,1981 ----
*************** scev_probably_wraps_p (tree type, tree b
*** 1929,1938 ****
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;
/* At this point we still don't have a proof that the iv does not
overflow: give up. */
--- 2114,2121 ----
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 false;
/* At this point we still don't have a proof that the iv does not
overflow: give up. */
*************** convert_step (struct loop *loop, tree ne
*** 1965,1979 ****
static void
free_numbers_of_iterations_estimates_loop (struct loop *loop)
{
! struct nb_iter_bound *bound, *next;
! for (bound = loop->bounds; bound; bound = next)
{
! next = bound->next;
! free (bound);
}
! loop->bounds = NULL;
}
/* Frees the information on upper bounds on numbers of iterations of LOOPS. */
--- 2148,2162 ----
static void
free_numbers_of_iterations_estimates_loop (struct loop *loop)
{
! struct iv_no_overflow *iv, *next;
! for (iv = loop->iv_no_overflow; iv; iv = next)
{
! next = iv->next;
! free (iv);
}
! loop->iv_no_overflow = NULL;
}
/* Frees the information on upper bounds on numbers of iterations of LOOPS. */
*************** free_numbers_of_iterations_estimates (st
*** 1998,2011 ****
void
substitute_in_loop_info (struct loop *loop, tree name, tree val)
{
! struct nb_iter_bound *bound;
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)
{
! bound->bound = simplify_replace_tree (bound->bound, name, val);
! bound->additional = simplify_replace_tree (bound->additional, name, val);
}
}
--- 2181,2215 ----
void
substitute_in_loop_info (struct loop *loop, tree name, tree val)
{
! struct iv_no_overflow *iv;
loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
! for (iv = loop->iv_no_overflow; iv; iv = iv->next)
{
! 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;
+ }
Index: testsuite/gcc.dg/tree-ssa/loop-13.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/loop-13.c
diff -N testsuite/gcc.dg/tree-ssa/loop-13.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/loop-13.c 4 Oct 2005 23:13:53 -0000
***************
*** 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" } } */