On Wed, Jul 27, 2016 at 11:07 AM, Richard Biener
<richard.guent...@gmail.com> wrote:
> On Tue, Jul 26, 2016 at 7:10 PM, Bin Cheng <bin.ch...@arm.com> wrote:
>> 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?
>
> + 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. */
>
> "in hard to track down bugs in niter/scev consumers"
>
> +static inline void
> +loop_constraint_clr (struct loop *loop, unsigned c)
> +{
>
> use _clear (similar to loops_state_clear). Function comments missing.
>
> I think we want to copy constraints in copy_loop_info.
>
> Please place the 'constraints' field in struct loop somewhere better,
> between two pointers we have 4 bytes wasted on a 64bit arch.
> Maybe you can group all bools and put constraints next to safelen
> (yeah, we'd still waste some padding, not sure if we want to turn
> the bools and estimate_state into a bitfield).
>
> It would be nice to document the constraints in doc/loop.texi.
>
> Ok with that changes.
Hi,
Attachment is the updated patch with comments addressed.
Thanks,
bin
2016-07-27 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.
* cfgloopmanip.c (copy_loop_info): Copy constraints.
* tree-ssa-loop-niter.c (number_of_iterations_exit_assumptions):
Adjust niter analysis wrto loop constraints.
* doc/loop.texi (@node Number of iterations): Add description for 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..5c202eb 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -188,6 +188,29 @@ struct GTY ((chain_next ("%h.next"))) loop {
of the loop can be safely evaluated concurrently. */
int safelen;
+ /* Constraints are generally set by consumers and affect certain
+ semantics of niter analyzer APIs. Currently the APIs affected are
+ number_of_iterations_exit* functions and their callers. One typical
+ use case 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 niter->assumptions computed in step 1).
+ 6) Vectorize the versioned loop in which niter->assumptions is
+ checked 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 down bugs in niter/scev consumers. */
+ unsigned constraints;
+
/* True if this loop should never be vectorized. */
bool dont_vectorize;
@@ -221,6 +244,32 @@ 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)
+
+/* Set C to the LOOP constraint. */
+static inline void
+loop_constraint_set (struct loop *loop, unsigned c)
+{
+ loop->constraints |= c;
+}
+
+/* Clear C from the LOOP constraint. */
+static inline void
+loop_constraint_clear (struct loop *loop, unsigned c)
+{
+ loop->constraints &= ~c;
+}
+
+/* Check if C is set in the LOOP constraint. */
+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/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 707a130..c520b36 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -1022,6 +1022,7 @@ copy_loop_info (struct loop *loop, struct loop *target)
target->any_estimate = loop->any_estimate;
target->nb_iterations_estimate = loop->nb_iterations_estimate;
target->estimate_state = loop->estimate_state;
+ target->constraints = loop->constraints;
target->warned_aggressive_loop_optimizations
|= loop->warned_aggressive_loop_optimizations;
target->in_oacc_kernels_region = loop->in_oacc_kernels_region;
diff --git a/gcc/doc/loop.texi b/gcc/doc/loop.texi
index 8c7a62f..44b528d 100644
--- a/gcc/doc/loop.texi
+++ b/gcc/doc/loop.texi
@@ -476,6 +476,32 @@ The function @code{number_of_cond_exit_executions} can be
used to
determine number of executions of the exit condition of a single-exit
loop (i.e., the @code{number_of_latch_executions} increased by one).
+On GIMPLE, below constraint flags affect semantics of some APIs of number
+of iterations analyzer:
+
+@itemize
+@item @code{LOOP_C_INFINITE}: If this constraint flag is set, the loop
+is known to be infinite. APIs like @code{number_of_iterations_exit} can
+return false directly without doing any analysis.
+@item @code{LOOP_C_FINITE}: If this constraint flag is set, the loop is
+known to be finite, in other words, loop's number of iterations can be
+computed with @code{assumptions} be true.
+@end itemize
+
+Generally, the constraint flags are set/cleared by consumers which are
+loop optimizers. It's also the consumers' responsibility to set/clear
+constraints correctly. Failing to do that might result in hard to track
+down bugs in scev/niter consumers. One typical use case is vectorizer:
+it drives number of iterations analyzer by setting @code{LOOP_C_FINITE}
+and vectorizes possibly infinite loop by versioning loop with analysis
+result. In return, constraints set by consumers can also help number of
+iterations analyzer in following optimizers. For example, @code{niter}
+of a loop versioned under @code{assumptions} is valid unconditionally.
+
+Other constraints may be added in the future, for example, a constraint
+indicating that loops' latch must roll thus @code{may_be_zero} would be
+false unconditionally.
+
@node Dependency analysis
@section Data Dependency Analysis
@cindex Data Dependency Analysis
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,
