| Message ID | HE1PR0801MB17556D6A341D222778096716E70E0@HE1PR0801MB1755.eurprd08.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
On Tue, Jul 26, 2016 at 7:10 PM, Bin Cheng <Bin.Cheng@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. Thanks, Richard. > Thanks, > bin > > 2016-07-25 Bin Cheng <bin.cheng@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,
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.cheng@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.