This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: GCC loop iterations and wrapping
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- Cc: David Edelsohn <dje at watson dot ibm dot com>,GCC Patches <gcc-patches at gcc dot gnu dot org>,Daniel Berlin <dberlin at dberlin dot org>
- Date: Sat, 22 Oct 2005 23:21:20 +0200
- Subject: Re: GCC loop iterations and wrapping
- References: <200510171439.j9HEdRq29556@makai.watson.ibm.com> <20051017161246.GA5937@napoca.cri.ensmp.fr> <200510171705.j9HH53q28188@makai.watson.ibm.com> <20051017182521.GA929@napoca.cri.ensmp.fr> <200510171833.j9HIXvq39648@makai.watson.ibm.com> <20051017185146.GA19710@napoca.cri.ensmp.fr> <200510181925.j9IJPtq27920@makai.watson.ibm.com> <20051021172109.GA31610@napoca.cri.ensmp.fr> <20051021180623.GA13448@atrey.karlin.mff.cuni.cz> <20051021181953.GA348@napoca.cri.ensmp.fr>
Hello,
> > > - /* FIXME: convert_step should not be used outside chrec_convert: fix
> > > - this by calling chrec_convert. */
> > > - iv_step = convert_step (dta->ivopts_data->current_loop,
> > > - sizetype, iv->base, iv->step, dta->stmt);
> > > + chrec = build_polynomial_chrec (loop->num, iv->base, iv->step);
> > > + chrec = chrec_convert (sizetype, chrec, dta->stmt);
> >
> > I don't like this change. You just waste memory creating a
> > polynomial_chrec, without any reason.
> >
>
> It is possible to add the same check to as in chrec_convert
>
> if (!flag_unsafe_loop_optimizations
> && scev_probably_wraps_p (type, base, step, at_stmt, loop,
> &dummy, &dummy))
>
> and then call convert_step, for avoiding to waste memory.
I would prefer having the check whether the conversion is valid
split to a separate function, so that it can be used without code
duplication; something like the following patch, bootstrapped &
regtested on ia64.
Zdenek
* Makefile.in (tree-ssa-loop-niter.o): Add langhooks.h dependency.
* tree-chrec.c (chrec_convert_1): Split from chrec_convert.
Use can_convert_iv_p.
(chrec_convert, chrec_convert_aggressive): Use chrec_convert_1.
* tree-chrec.h (chrec_convert_aggressive): Add argument.
* tree-flow.h (convert_step): Removed.
(can_convert_iv_p, step_after_conversion): Declare.
* tree-scalar-evolution.c (instantiate_parameters_1): Changed due to
chrec_convert_aggressive change.
* tree-ssa-loop-ivopts.c (idx_find_step): Use can_convert_iv_p.
* tree-ssa-loop-niter.c: Include langhooks.h.
(compare_trees): Removed.
(proved_non_wrapping_p): Renamed to ...
(loop_iterations_at_most_p): ... this.
(convert_step_widening): Removed.
(scev_probably_wraps_p): Use can_convert_iv_p..
(step_after_conversion, can_convert_iv_narrowing_p,
can_convert_iv_widening_p, can_convert_iv_p): New functions.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1547
diff -c -3 -p -r1.1547 Makefile.in
*** Makefile.in 12 Oct 2005 12:38:00 -0000 1.1547
--- Makefile.in 21 Oct 2005 20:28:46 -0000
*************** tree-ssa-loop-niter.o : tree-ssa-loop-ni
*** 1895,1901 ****
$(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) \
--- 1895,1901 ----
$(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 langhooks.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: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.28
diff -c -3 -p -r2.28 tree-chrec.c
*** tree-chrec.c 20 Sep 2005 07:09:18 -0000 2.28
--- tree-chrec.c 21 Oct 2005 20:28:46 -0000
*************** nb_vars_in_chrec (tree chrec)
*** 1096,1101 ****
--- 1096,1103 ----
conversion is less accurate: the information is used for
determining a more accurate estimation of the number of iterations.
By default AT_STMT could be safely set to NULL_TREE.
+ If AVOID_WRAPS is true, conversions that would create wrapping
+ ivs are avoided.
The following rule is always true: TREE_TYPE (chrec) ==
TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE (CHREC_RIGHT (chrec)).
*************** nb_vars_in_chrec (tree chrec)
*** 1114,1121 ****
{(uint) 0, +, (uint) 260}
*/
! tree
! chrec_convert (tree type, tree chrec, tree at_stmt)
{
tree ct, res;
--- 1116,1123 ----
{(uint) 0, +, (uint) 260}
*/
! static tree
! chrec_convert_1 (tree type, tree chrec, tree at_stmt, bool avoid_wraps)
{
tree ct, res;
*************** chrec_convert (tree type, tree chrec, tr
*** 1129,1155 ****
if (evolution_function_is_affine_p (chrec))
{
tree base, step;
- bool dummy;
struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
base = instantiate_parameters (loop, CHREC_LEFT (chrec));
step = instantiate_parameters (loop, CHREC_RIGHT (chrec));
! /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
! when it is not possible to prove that the scev does not wrap.
! See PR22236, where a sequence 1, 2, ..., 255 has to be
! converted to signed char, but this would wrap:
! 1, 2, ..., 127, -128, ... The result should not be
! {(schar)1, +, (schar)1}_x, but instead, we should keep the
! conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
! if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
! &dummy, &dummy))
! goto failed_to_convert;
!
! step = convert_step (loop, type, base, step, at_stmt);
! if (!step)
{
- failed_to_convert:;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(failed conversion:");
--- 1131,1143 ----
if (evolution_function_is_affine_p (chrec))
{
tree base, step;
struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
base = instantiate_parameters (loop, CHREC_LEFT (chrec));
step = instantiate_parameters (loop, CHREC_RIGHT (chrec));
! if (!can_convert_iv_p (loop, type, base, step, at_stmt, avoid_wraps))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(failed conversion:");
*************** chrec_convert (tree type, tree chrec, tr
*** 1167,1175 ****
return fold_convert (type, chrec);
}
return build_polynomial_chrec (CHREC_VARIABLE (chrec),
! chrec_convert (type, CHREC_LEFT (chrec),
! at_stmt),
step);
}
--- 1155,1164 ----
return fold_convert (type, chrec);
}
+ step = step_after_conversion (type, step);
return build_polynomial_chrec (CHREC_VARIABLE (chrec),
! chrec_convert_1 (type, CHREC_LEFT (chrec),
! at_stmt, avoid_wraps),
step);
}
*************** chrec_convert (tree type, tree chrec, tr
*** 1199,1231 ****
return res;
}
! /* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
! chrec if something else than what chrec_convert would do happens, NULL_TREE
! otherwise. */
tree
! chrec_convert_aggressive (tree type, tree chrec)
{
! tree inner_type, left, right, lc, rc;
!
! if (automatically_generated_chrec_p (chrec)
! || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
! return NULL_TREE;
!
! inner_type = TREE_TYPE (chrec);
! if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
! return NULL_TREE;
! left = CHREC_LEFT (chrec);
! right = CHREC_RIGHT (chrec);
! lc = chrec_convert_aggressive (type, left);
! if (!lc)
! lc = chrec_convert (type, left, NULL_TREE);
! rc = chrec_convert_aggressive (type, right);
! if (!rc)
! rc = chrec_convert (type, right, NULL_TREE);
! return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
}
/* Returns the type of the chrec. */
--- 1188,1207 ----
return res;
}
! /* Convert CHREC to TYPE in AT_STMT. The signed overflows are avoided. */
tree
! chrec_convert (tree type, tree chrec, tree at_stmt)
{
! return chrec_convert_1 (type, chrec, at_stmt, true);
! }
! /* Convert CHREC to TYPE in AT_STMT, without regard to signed overflows. */
! tree
! chrec_convert_aggressive (tree type, tree chrec, tree at_stmt)
! {
! return chrec_convert_1 (type, chrec, at_stmt, false);
}
/* Returns the type of the chrec. */
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.h,v
retrieving revision 2.11
diff -c -3 -p -r2.11 tree-chrec.h
*** tree-chrec.h 20 Sep 2005 07:09:20 -0000 2.11
--- tree-chrec.h 21 Oct 2005 20:28:46 -0000
*************** extern tree chrec_fold_plus (tree, tree,
*** 68,74 ****
extern tree chrec_fold_minus (tree, tree, tree);
extern tree chrec_fold_multiply (tree, tree, tree);
extern tree chrec_convert (tree, tree, tree);
! extern tree chrec_convert_aggressive (tree, tree);
extern tree chrec_type (tree);
/* Operations. */
--- 68,74 ----
extern tree chrec_fold_minus (tree, tree, tree);
extern tree chrec_fold_multiply (tree, tree, tree);
extern tree chrec_convert (tree, tree, tree);
! extern tree chrec_convert_aggressive (tree, tree, tree);
extern tree chrec_type (tree);
/* Operations. */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.139
diff -c -3 -p -r2.139 tree-flow.h
*** tree-flow.h 16 Oct 2005 00:07:17 -0000 2.139
--- tree-flow.h 21 Oct 2005 20:28:46 -0000
*************** tree find_loop_niter_by_eval (struct loo
*** 732,738 ****
void estimate_numbers_of_iterations (struct loops *);
bool scev_probably_wraps_p (tree, tree, tree, tree, struct loop *, bool *,
bool *);
! tree convert_step (struct loop *, tree, tree, tree, tree);
void free_numbers_of_iterations_estimates (struct loops *);
void free_numbers_of_iterations_estimates_loop (struct loop *);
void rewrite_into_loop_closed_ssa (bitmap, unsigned);
--- 732,739 ----
void estimate_numbers_of_iterations (struct loops *);
bool scev_probably_wraps_p (tree, tree, tree, tree, struct loop *, bool *,
bool *);
! bool can_convert_iv_p (struct loop *, tree, tree, tree, tree, bool);
! tree step_after_conversion (tree, tree);
void free_numbers_of_iterations_estimates (struct loops *);
void free_numbers_of_iterations_estimates_loop (struct loop *);
void rewrite_into_loop_closed_ssa (bitmap, unsigned);
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.39
diff -c -3 -p -r2.39 tree-scalar-evolution.c
*** tree-scalar-evolution.c 26 Sep 2005 18:43:09 -0000 2.39
--- tree-scalar-evolution.c 21 Oct 2005 20:28:46 -0000
*************** instantiate_parameters_1 (struct loop *l
*** 2149,2159 ****
return chrec_dont_know;
if (flags & FOLD_CONVERSIONS)
! {
! tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
! if (tmp)
! return tmp;
! }
if (op0 == TREE_OPERAND (chrec, 0))
return chrec;
--- 2149,2155 ----
return chrec_dont_know;
if (flags & FOLD_CONVERSIONS)
! return chrec_convert_aggressive (TREE_TYPE (chrec), op0, NULL_TREE);
if (op0 == TREE_OPERAND (chrec, 0))
return chrec;
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.89
diff -c -3 -p -r2.89 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 22 Sep 2005 11:24:00 -0000 2.89
--- tree-ssa-loop-ivopts.c 21 Oct 2005 20:28:47 -0000
*************** idx_find_step (tree base, tree *idx, voi
*** 1445,1458 ****
/* FIXME: convert_step should not be used outside chrec_convert: fix
this by calling chrec_convert. */
! iv_step = convert_step (dta->ivopts_data->current_loop,
! sizetype, iv->base, iv->step, dta->stmt);
!
! if (!iv_step)
{
/* The index might wrap. */
return false;
}
step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
--- 1445,1457 ----
/* FIXME: convert_step should not be used outside chrec_convert: fix
this by calling chrec_convert. */
! if (!can_convert_iv_p (dta->ivopts_data->current_loop,
! sizetype, iv->base, iv->step, dta->stmt, false))
{
/* The index might wrap. */
return false;
}
+ iv_step = step_after_conversion (sizetype, iv->step);
step = fold_build2 (MULT_EXPR, sizetype, step, iv_step);
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.46
diff -c -3 -p -r2.46 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 9 Oct 2005 22:50:01 -0000 2.46
--- tree-ssa-loop-niter.c 21 Oct 2005 20:28:47 -0000
*************** Software Foundation, 51 Franklin Street,
*** 42,47 ****
--- 42,48 ----
#include "flags.h"
#include "toplev.h"
#include "tree-inline.h"
+ #include "langhooks.h"
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
*************** estimate_numbers_of_iterations (struct l
*** 1570,1602 ****
}
}
- /* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1.
- If neither of these relations can be proved, returns 2. */
-
- static int
- compare_trees (tree a, tree b)
- {
- tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
- tree type;
-
- if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
- type = typea;
- else
- type = typeb;
-
- a = fold_convert (type, a);
- b = fold_convert (type, b);
-
- if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
- return 0;
- if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
- return 1;
- if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
- return -1;
-
- return 2;
- }
-
/* Returns true if statement S1 dominates statement S2. */
static bool
--- 1571,1576 ----
*************** stmt_dominates_stmt_p (tree s1, tree s2)
*** 1622,1632 ****
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.
--- 1596,1603 ----
return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
}
! /* Return true when it is possible to prove that AT_STMT is executed
! at most VALID_NITER times
The statement NITER_BOUND->AT_STMT is executed at most
NITER_BOUND->BOUND times in the loop.
*************** stmt_dominates_stmt_p (tree s1, tree s2)
*** 1648,1666 ****
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)
--- 1619,1638 ----
most MAX_TYPE - 1 (without this assumption, it might overflow). */
static bool
! loop_iterations_at_most_p (tree at_stmt,
! struct nb_iter_bound *niter_bound,
! tree new_type,
! tree valid_niter)
{
tree cond;
! tree bound = niter_bound->bound, type = TREE_TYPE (valid_niter);
! tree bound_type = TREE_TYPE (bound);
enum tree_code cmp;
! if (TYPE_PRECISION (new_type) > TYPE_PRECISION (bound_type))
! bound = fold_convert (type, bound);
else
! valid_niter = fold_convert (bound_type, valid_niter);
/* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434. */
if (TREE_CODE (bound) != INTEGER_CST)
*************** proved_non_wrapping_p (tree at_stmt,
*** 1691,1777 ****
return false;
}
! /* Checks whether it is correct to count the induction variable BASE +
! STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
! numbers of iterations of a LOOP. If it is possible, return the
! value of step of the induction variable in the NEW_TYPE, otherwise
! return NULL_TREE. */
! static tree
! convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
! tree at_stmt)
{
! struct nb_iter_bound *bound;
! tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
! tree delta, step_abs;
! tree unsigned_type, valid_niter;
! /* Compute the new step. For example, {(uchar) 100, +, (uchar) 240}
! is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
! keep the values of the induction variable unchanged: 100, 84, 68,
! ...
!
! Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
! to {(uint)100, +, (uint)3}.
!
! Before returning the new step, verify that the number of
! iterations is less than DELTA / STEP_ABS (i.e. in the previous
! example (256 - 100) / 3) such that the iv does not wrap (in which
! case the operations are too difficult to be represented and
! handled: the values of the iv should be taken modulo 256 in the
! wider type; this is not implemented). */
! base_in_new_type = fold_convert (new_type, base);
! base_plus_step_in_new_type =
! fold_convert (new_type,
! fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
! step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
! base_plus_step_in_new_type,
! base_in_new_type);
! if (TREE_CODE (step_in_new_type) != INTEGER_CST)
! return NULL_TREE;
- switch (compare_trees (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
--- 1663,1698 ----
return false;
}
! /* Returns value of STEP after converting the induction variable to
! TYPE. The validity of the conversion should be verified by
! can_convert_iv_p. */
! tree
! step_after_conversion (tree new_type, tree step)
{
! tree step_type = TREE_TYPE (step);
! /* If we are narrowing the variable, we just need to cast the step. */
! if (TYPE_PRECISION (new_type) <= TYPE_PRECISION (step_type))
! return fold_convert (new_type, step);
! /* The step must always be sign extended, regardless of what signedness
! the type have. For example, when extending unsigned char variable
! with step 255 to unsigned int, we want the value of the step to
! still be ~0. */
! if (TYPE_UNSIGNED (step_type)
! && (TREE_CODE (step) != INTEGER_CST
! || tree_int_cst_sign_bit (step)))
! {
! /* This should force sign extension. */
! unsigned size = TYPE_PRECISION (step_type);
! tree stype = lang_hooks.types.type_for_size (size, false);
! step = fold_convert (stype, step);
}
! return fold_convert (new_type, step);
}
/* Returns true when VAR is used in pointer arithmetics. DEPTH is
*************** scev_probably_wraps_p (tree type, tree b
*** 1828,1837 ****
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;
- int cps, cpsps;
/* FIXME: The following code will not be used anymore once
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
--- 1749,1756 ----
bool *init_is_max, bool *unknown_max)
{
struct nb_iter_bound *bound;
! tree delta, step_abs, extreme;
tree unsigned_type, valid_niter;
/* FIXME: The following code will not be used anymore once
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
*************** scev_probably_wraps_p (tree type, tree b
*** 1866,1920 ****
if (chrec_contains_undetermined (base)
|| chrec_contains_undetermined (step)
! || TREE_CODE (base) == REAL_CST
! || TREE_CODE (step) == REAL_CST)
{
*unknown_max = true;
return true;
}
*unknown_max = false;
- base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
- bpsps = fold_build2 (PLUS_EXPR, type, base_plus_step, step);
- cps = compare_trees (base_plus_step, base);
- cpsps = compare_trees (bpsps, base_plus_step);
-
- /* Check that the sequence is not wrapping in the first step: it
- should have the same monotonicity for the first two steps. See
- PR23410. */
- if (cps != cpsps)
- return true;
! switch (cps)
{
! case -1:
! {
! tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
! delta = fold_build2 (MINUS_EXPR, type, extreme, base);
! step_abs = step;
! *init_is_max = false;
! break;
! }
!
! case 1:
! {
! tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
! delta = fold_build2 (MINUS_EXPR, type, base, extreme);
! step_abs = fold_build1 (NEGATE_EXPR, type, step);
! *init_is_max = true;
! break;
! }
!
! case 0:
! /* This means step is equal to 0. This should not happen. It
! could happen in convert step, but not here. Safely answer
! don't know as in the default case. */
!
! default:
! *unknown_max = true;
return true;
}
/* If AT_STMT represents a cast operation, we may not be able to
take advantage of the undefinedness of signed type evolutions.
--- 1785,1821 ----
if (chrec_contains_undetermined (base)
|| chrec_contains_undetermined (step)
! || TREE_CODE (step) != INTEGER_CST)
{
*unknown_max = true;
return true;
}
*unknown_max = false;
! step = step_after_conversion (type, step);
! if (zero_p (step))
{
! /* Obviously, the scev cannot wrap. */
! *init_is_max = true;
return true;
}
+ if (tree_int_cst_sign_bit (step))
+ {
+ extreme = lower_bound_in_type (type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, type, base, extreme);
+ step_abs = fold_build1 (NEGATE_EXPR, type, step);
+ *init_is_max = true;
+ }
+ else
+ {
+ extreme = upper_bound_in_type (type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, type, extreme, base);
+ step_abs = step;
+ *init_is_max = false;
+ }
+
/* If AT_STMT represents a cast operation, we may not be able to
take advantage of the undefinedness of signed type evolutions.
*************** scev_probably_wraps_p (tree type, tree b
*** 1970,1976 ****
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
--- 1871,1877 ----
estimate_numbers_of_iterations_loop (loop);
for (bound = loop->bounds; bound; bound = bound->next)
! if (loop_iterations_at_most_p (at_stmt, bound, type, valid_niter))
return false;
/* At this point we still don't have a proof that the iv does not
*************** scev_probably_wraps_p (tree type, tree b
*** 1979,2008 ****
return true;
}
! /* Return the conversion to NEW_TYPE of the STEP of an induction
! variable BASE + STEP * I at AT_STMT. When it fails, return
! NULL_TREE. */
! tree
! convert_step (struct loop *loop, tree new_type, tree base, tree step,
! tree at_stmt)
{
tree base_type;
if (chrec_contains_undetermined (base)
|| chrec_contains_undetermined (step))
! return NULL_TREE;
base_type = TREE_TYPE (base);
! /* When not using wrapping arithmetic, signed types don't wrap. */
! if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
! return fold_convert (new_type, step);
!
! if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
! return convert_step_widening (loop, new_type, base, step, at_stmt);
!
! return fold_convert (new_type, step);
}
/* Frees the information on upper bounds on numbers of iterations of LOOP. */
--- 1880,1954 ----
return true;
}
! /* Returns true if iv BASE + STEP * i can be converted to NEW_TYPE,
! that is narrower or of the same width as the original type of the iv.
! The meaning of the parameters is the same as in can_convert_iv_p. */
! static bool
! can_convert_iv_narrowing_p (struct loop *loop, tree new_type,
! tree base, tree step,
! tree at_stmt, bool avoid_wraps)
! {
! bool dummy;
!
! /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
! when it is not possible to prove that the scev does not wrap.
! See PR22236, where a sequence 1, 2, ..., 255 has to be
! converted to signed char, but this would wrap:
! 1, 2, ..., 127, -128, ... The result should not be
! {(schar)1, +, (schar)1}_x, but instead, we should keep the
! conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
! if (!flag_unsafe_loop_optimizations
! && avoid_wraps
! && scev_probably_wraps_p (new_type, base, step, at_stmt, loop,
! &dummy, &dummy))
! return false;
!
! return true;
! }
!
! /* Returns true if iv BASE + STEP * i can be converted to NEW_TYPE,
! that is wider than the original type of the iv. The meaning of the
! parameters is the same as in can_convert_iv_p. */
!
! static bool
! can_convert_iv_widening_p (struct loop *loop, tree new_type,
! tree base, tree step,
! tree at_stmt)
! {
! bool dummy;
!
! if (!flag_unsafe_loop_optimizations
! && scev_probably_wraps_p (new_type, base, step, at_stmt, loop,
! &dummy, &dummy))
! return false;
!
! return true;
! }
!
! /* Returns true if it is possible to convert the induction variable
! BASE + STEP * I to NEW_TYPE, where the variable is evaluated
! at AT_STMT. If AVOID_WRAPS is true, avoid converting the variable
! if the converted iv could wrap. */
!
! bool
! can_convert_iv_p (struct loop *loop, tree new_type, tree base, tree step,
! tree at_stmt, bool avoid_wraps)
{
tree base_type;
if (chrec_contains_undetermined (base)
|| chrec_contains_undetermined (step))
! return false;
base_type = TREE_TYPE (base);
! if (TYPE_PRECISION (new_type) <= TYPE_PRECISION (base_type))
! return can_convert_iv_narrowing_p (loop, new_type, base, step,
! at_stmt, avoid_wraps);
! else
! return can_convert_iv_widening_p (loop, new_type, base, step,
! at_stmt);
}
/* Frees the information on upper bounds on numbers of iterations of LOOP. */