Hi,
This patch adds support for constraint flags in loop structure. Different to
existing boolean flags which are set by niter analyzer, constraint flag is
mainly set by consumers and affects certain semantics of niter analyzer APIs.
Currently niter APIs affected are number_of_iterations_exit* and their callers.
Constraint flags are added to support handling of possible infinite loops in
GCC. One typical usecase of constraint is in vectorizer, as described in
patch's comment:
/* ...
1) Compute niter->assumptions by calling niter analyzer API and
record it as possible condition for loop versioning.
2) Clear buffered result of niter/scev analyzer.
3) Set constraint LOOP_C_FINITE assuming the loop is finite.
4) Analyze data references. Since data reference analysis depends
on niter/scev analyzer, the point is that niter/scev analysis
is done under circumstance of LOOP_C_FINITE constraint.
5) Version the loop with assumptions computed in step 1).
6) Vectorize the versioned loop in which assumptions is guarded to
be true.
7) Update constraints in versioned loops so that niter analyzer
in following passes can use it.
Note consumers are usually the loop optimizers and it is consumers'
responsibility to set/clear constraints correctly. Failing to do
that might result in hard to track bugs in niter/scev analyzer. */
Next patch will use constraint to vectorize possible infinite loop by
versioning, I would also expect possible infinite loops (loops with
assumptions) can be handled by more optimizers. This patch itself doesn't
change GCC behavior, bootstrap and test on x86_64. Any comments?
Thanks,
bin
2016-07-25 Bin Cheng <bin.ch...@arm.com>
* cfgloop.h (struct loop): New field constraints.
(LOOP_C_INFINITE, LOOP_C_FINITE): New macros.
(loop_constraint_set, loop_constraint_clr, loop_constraint_set_p): New
functions.
* cfgloop.c (alloc_loop): Initialize new field.
* tree-ssa-loop-niter.c (number_of_iterations_exit_assumptions):
Adjust niter analysis wrto loop constraints.diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 2087b90..b5c920c 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -339,6 +339,7 @@ alloc_loop (void)
loop->exits = ggc_cleared_alloc<loop_exit> ();
loop->exits->next = loop->exits->prev = loop->exits;
loop->can_be_parallel = false;
+ loop->constraints = 0;
loop->nb_iterations_upper_bound = 0;
loop->nb_iterations_likely_upper_bound = 0;
loop->nb_iterations_estimate = 0;
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index dfc7525..c5936f1 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -147,6 +147,30 @@ struct GTY ((chain_next ("%h.next"))) loop {
/* Auxiliary info specific to a pass. */
PTR GTY ((skip (""))) aux;
+ /* Different to other boolean flags which are set by niter analyzer,
+ constraint is set by consumers and it affects certain semantics
+ of niter analyzer APIs. Currently the APIs affected are functions
+ number_of_iterations_exit* and their callers. One typical usecase
+ of constraints is to vectorize possibly infinite loop:
+
+ 1) Compute niter->assumptions by calling niter analyzer API and
+ record it as possible condition for loop versioning.
+ 2) Clear buffered result of niter/scev analyzer.
+ 3) Set constraint LOOP_C_FINITE assuming the loop is finite.
+ 4) Analyze data references. Since data reference analysis depends
+ on niter/scev analyzer, the point is that niter/scev analysis
+ is done under circumstance of LOOP_C_FINITE constraint.
+ 5) Version the loop with assumptions computed in step 1).
+ 6) Vectorize the versioned loop in which assumptions is guarded to
+ be true.
+ 7) Update constraints in versioned loops so that niter analyzer
+ in following passes can use it.
+
+ Note consumers are usually the loop optimizers and it is consumers'
+ responsibility to set/clear constraints correctly. Failing to do
+ that might result in hard to track bugs in niter/scev analyzer. */
+ unsigned constraints;
+
/* The number of times the latch of the loop is executed. This can be an
INTEGER_CST, or a symbolic expression representing the number of
iterations like "N - 1", or a COND_EXPR containing the runtime
@@ -221,6 +245,29 @@ struct GTY ((chain_next ("%h.next"))) loop {
basic_block former_header;
};
+/* Set if the loop is known to be infinite. */
+#define LOOP_C_INFINITE (1 << 0)
+/* Set if the loop is known to be finite without any assumptions. */
+#define LOOP_C_FINITE (1 << 1)
+
+static inline void
+loop_constraint_set (struct loop *loop, unsigned c)
+{
+ loop->constraints |= c;
+}
+
+static inline void
+loop_constraint_clr (struct loop *loop, unsigned c)
+{
+ loop->constraints &= ~c;
+}
+
+static inline bool
+loop_constraint_set_p (struct loop *loop, unsigned c)
+{
+ return (loop->constraints & c) == c;
+}
+
/* Flags for state of loop structure. */
enum
{
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index b7d7c32..b922301 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2148,6 +2148,10 @@ number_of_iterations_exit_assumptions (struct loop
*loop, edge exit,
affine_iv iv0, iv1;
bool safe;
+ /* Nothing to analyze if the loop is known to be infinite. */
+ if (loop_constraint_set_p (loop, LOOP_C_INFINITE))
+ return false;
+
safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
if (every_iteration && !safe)
@@ -2233,6 +2237,11 @@ number_of_iterations_exit_assumptions (struct loop
*loop, edge exit,
niter->max = wi::to_widest (iv_niters);
}
+ /* There is no assumptions if the loop is known to be finite. */
+ if (!integer_zerop (niter->assumptions)
+ && loop_constraint_set_p (loop, LOOP_C_FINITE))
+ niter->assumptions = boolean_true_node;
+
if (optimize >= 3)
{
niter->assumptions = simplify_using_outer_evolutions (loop,
