[RFC] Have the scalarizer generate vectorizable loops.
Toon Moene
toon@moene.indiv.nluug.nl
Wed Jan 4 19:08:00 GMT 2006
> Toon,
> >I do not ask so much as to whether the above is correct, but
> >whether it is the right approach. For the simple case above it works:
> >
> >
> Bravo!
Unfortunately, as I found out on IRC, in a discussion with Paul
Brook, Andrew Pinski and Danny Berlin, this is *not* the right
approach. The fault is in the scalar evolution code (see bug
PR/18527).
Zdenek already supplied a patch for it. That one didn't apply
completely cleanly, so I had to hand edit the result for one
chunk. The updated patch follows. It works in the sense that
it vectorizes the example I showed yesterday. I still have
to test it extensively (running make -k check, etc.).
- - - - - - - - 8 < - - - - - - - - - - - 8< - - - - - - - - -
Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c (revision 109313)
+++ tree-ssa-loop-niter.c (working copy)
@@ -137,16 +137,20 @@
The results (number of iterations and assumptions as described in
comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
In case we are unable to determine number of iterations, contents of
- this structure is unchanged. */
+ this structure is unchanged.
+
+ NOOVFL0 and NOOVFL1 are true if we know that the lhs and the rhs iv cannot
+ overflow, respectively. */
static void
-number_of_iterations_cond (tree type, tree base0, tree step0,
- enum tree_code code, tree base1, tree step1,
+number_of_iterations_cond (tree type, tree base0, tree step0, bool noovfl0,
+ enum tree_code code,
+ tree base1, tree step1, bool noovfl1,
struct tree_niter_desc *niter)
{
tree step, delta, mmin, mmax;
tree may_xform, bound, s, d, tmp;
- bool was_sharp = false;
+ bool was_sharp = false, noovfl, never_infinite;
tree assumption;
tree assumptions = boolean_true_node;
tree noloop_assumptions = boolean_false_node;
@@ -168,8 +172,21 @@
SWAP (base0, base1);
SWAP (step0, step1);
code = swap_tree_comparison (code);
+
+ noovfl = noovfl1;
+ noovfl1 = noovfl0;
+ noovfl0 = noovfl;
}
+ /* If the control induction variable does not overflow, the loop obviously
+ cannot be infinite. */
+ if (!zero_p (step0) && noovfl0)
+ never_infinite = true;
+ else if (!zero_p (step1) && noovfl1)
+ never_infinite = true;
+ else
+ never_infinite = false;
+
/* We can handle the case when neither of the sides of the comparison is
invariant, provided that the test is NE_EXPR. This rarely occurs in
practice, but it is simple enough to manage. */
@@ -180,6 +197,7 @@
step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1);
step1 = NULL_TREE;
+ noovfl0 = noovfl1 = false;
}
/* If the result is a constant, the loop is weird. More precise handling
@@ -299,7 +317,7 @@
}
else if (zero_p (step0))
{
- if (!mmin)
+ if (!mmin || noovfl1)
may_xform = boolean_true_node;
else
{
@@ -313,7 +331,7 @@
}
else
{
- if (!mmax)
+ if (!mmax || noovfl0)
may_xform = boolean_true_node;
else
{
@@ -389,12 +407,17 @@
(TYPE_PRECISION (niter_type)
- tree_low_cst (bits, 1)));
- assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, base1, d);
- assumption = fold_build2 (EQ_EXPR, boolean_type_node,
- assumption,
- build_int_cst (niter_type, 0));
- assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
- assumptions, assumption);
+ if (!never_infinite)
+ {
+ /* If we cannot assume that the loop is not infinite, record the
+ assumptions for divisibility of c. */
+ assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, base1, d);
+ assumption = fold_build2 (EQ_EXPR, boolean_type_node,
+ assumption,
+ build_int_cst (niter_type, 0));
+ assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ assumptions, assumption);
+ }
tmp = fold_build2 (EXACT_DIV_EXPR, niter_type, base1, d);
tmp = fold_build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound));
@@ -410,7 +433,7 @@
overflow condition using some information about b - a mod s,
but it was already taken into account during LE -> NE transform). */
{
- if (mmax)
+ if (mmax && !noovfl0)
{
bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
@@ -431,7 +454,7 @@
/* Condition in shape a <= b - s * i
We must know that a - s does not overflow and a - s <= b and then
we can again compute number of iterations as (b - (a - s)) / s. */
- if (mmin)
+ if (mmin && !noovfl1)
{
bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
@@ -471,11 +494,12 @@
returns true if the special case was recognized, false otherwise. */
static bool
-number_of_iterations_special (tree type, tree base0, tree step0,
+number_of_iterations_special (tree type, tree base0, tree step0, bool noovfl0,
enum tree_code code, tree base1, tree step1,
- struct tree_niter_desc *niter)
+ bool noovfl1, struct tree_niter_desc *niter)
{
tree niter_type = unsigned_type_for (type), mmax, mmin;
+ bool noovfl;
/* Make < comparison from > ones. */
if (code == GE_EXPR
@@ -483,6 +507,7 @@
{
SWAP (base0, base1);
SWAP (step0, step1);
+ noovfl = noovfl0; noovfl0 = noovfl1; noovfl1 = noovfl;
code = swap_tree_comparison (code);
}
@@ -555,7 +580,7 @@
if (step0 && integer_onep (step0) && zero_p (step1))
{
/* for (i = base0; i <= base1; i++) */
- if (mmax)
+ if (mmax && !noovfl0)
niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
base1, mmax);
else
@@ -566,7 +591,7 @@
else if (step1 && integer_all_onesp (step1) && zero_p (step0))
{
/* for (i = base1; i >= base0; i--) */
- if (mmin)
+ if (mmin && !noovfl1)
niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
base0, mmin);
else
@@ -925,6 +950,7 @@
tree op0, base0, step0;
tree op1, base1, step1;
enum tree_code code;
+ bool cannot_overflow0, cannot_overflow1;
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
@@ -961,20 +987,22 @@
&& !POINTER_TYPE_P (type))
return false;
- if (!simple_iv (loop, stmt, op0, &base0, &step0, false))
+ if (!simple_iv (loop, stmt, op0, &base0, &step0, false, &cannot_overflow0))
return false;
- if (!simple_iv (loop, stmt, op1, &base1, &step1, false))
+ if (!simple_iv (loop, stmt, op1, &base1, &step1, false, &cannot_overflow1))
return false;
niter->niter = NULL_TREE;
/* Handle common special cases first, so that we do not need to use
generic (and slow) analysis very often. */
- if (!number_of_iterations_special (type, base0, step0, code, base1, step1,
+ if (!number_of_iterations_special (type, base0, step0, cannot_overflow0,
+ code, base1, step1, cannot_overflow1,
niter))
{
- number_of_iterations_cond (type, base0, step0, code, base1, step1,
+ number_of_iterations_cond (type, base0, step0, cannot_overflow0,
+ code, base1, step1, cannot_overflow1,
niter);
if (!niter->niter)
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c (revision 109313)
+++ tree-scalar-evolution.c (working copy)
@@ -1831,20 +1831,29 @@
/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
- of VERSION). */
+ of VERSION).
+ FOLDED_CASTS is set to true if resolve_mixers used
+ chrec_convert_aggressive (TODO -- not really, we are way too conservative
+ at the moment in order to keep things simple). */
+
static tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
- tree version)
+ tree version, bool *folded_casts)
{
bool val = false;
- tree ev = version;
+ tree ev = version, tmp;
+ if (folded_casts)
+ *folded_casts = false;
while (1)
{
- ev = analyze_scalar_evolution (use_loop, ev);
- ev = resolve_mixers (use_loop, ev);
+ tmp = analyze_scalar_evolution (use_loop, ev);
+ ev = resolve_mixers (use_loop, tmp);
+ if (folded_casts && tmp != ev)
+ *folded_casts = true;
+
if (use_loop == wrto_loop)
return ev;
@@ -2563,14 +2572,18 @@
/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we
want STEP to be invariant in LOOP. Otherwise we require it to be an
- integer constant. */
+ integer constant.
+
+ NO_OVERFLOW is set to true if we are sure the iv cannot overflow (e.g.
+ because it is computed in signed arithmetics). */
bool
simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step,
- bool allow_nonconstant_step)
+ bool allow_nonconstant_step, bool *no_overflow)
{
basic_block bb = bb_for_stmt (stmt);
tree type, ev;
+ bool folded_casts;
*base = NULL_TREE;
*step = NULL_TREE;
@@ -2580,7 +2593,8 @@
&& TREE_CODE (type) != POINTER_TYPE)
return false;
- ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
+ ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
+ &folded_casts);
if (chrec_contains_undetermined (ev))
return false;
@@ -2588,6 +2602,8 @@
&& !chrec_contains_symbols_defined_in_loop (ev, loop->num))
{
*base = ev;
+ if (no_overflow)
+ *no_overflow = true;
return true;
}
@@ -2610,6 +2626,8 @@
|| chrec_contains_symbols_defined_in_loop (*base, loop->num))
return false;
+ if (no_overflow)
+ *no_overflow = (!flag_wrapv && !TYPE_UNSIGNED (type));
return true;
}
@@ -2756,7 +2774,7 @@
&& !INTEGRAL_TYPE_P (TREE_TYPE (def)))
continue;
- def = analyze_scalar_evolution_in_loop (ex_loop, loop, def);
+ def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
def = compute_overall_effect_of_inner_loop (ex_loop, def);
if (!tree_does_not_contain_chrecs (def)
|| chrec_contains_symbols_defined_in_loop (def, ex_loop->num))
Index: tree-scalar-evolution.h
===================================================================
--- tree-scalar-evolution.h (revision 109313)
+++ tree-scalar-evolution.h (working copy)
@@ -32,7 +32,8 @@
extern tree instantiate_parameters (struct loop *, tree);
extern void gather_stats_on_scev_database (void);
extern void scev_analysis (void);
-extern bool simple_iv (struct loop *, tree, tree, tree *, tree *, bool);
+extern bool simple_iv (struct loop *, tree, tree, tree *, tree *, bool,
+ bool *);
void scev_const_prop (void);
#endif /* GCC_TREE_SCALAR_EVOLUTION_H */
Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c (revision 109313)
+++ tree-ssa-loop-ivopts.c (working copy)
@@ -886,7 +886,7 @@
if (!is_gimple_reg (name))
return NULL_TREE;
- if (!simple_iv (loop, phi, name, &base, &step, true))
+ if (!simple_iv (loop, phi, name, &base, &step, true, NULL))
return NULL_TREE;
if (zero_p (step))
@@ -1063,7 +1063,8 @@
if (TREE_CODE (lhs) != SSA_NAME)
return false;
- if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step, true))
+ if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step, true,
+ NULL))
return false;
*base = expand_simple_operations (*base);
- - - - - - - - 8 < - - - - - - - - - - - 8< - - - - - - - - -
Please, comment.
Kind regards,
--
Toon Moene - e-mail: toon@moene.indiv.nluug.nl - phone: +31 346 214290
Saturnushof 14, 3738 XG Maartensdijk, The Netherlands
A maintainer of GNU Fortran 95: http://gcc.gnu.org/fortran/
More information about the Fortran
mailing list