From 18767ebc32eaed40760aab394fe77d0815454efd Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 29 Jul 2016 15:44:00 +0000 Subject: [PATCH] cfgloop.h (struct loop): New field constraints. * 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. From-SVN: r238876 --- gcc/ChangeLog | 13 +++++++++++++ gcc/cfgloop.c | 1 + gcc/cfgloop.h | 49 +++++++++++++++++++++++++++++++++++++++++++++++ gcc/cfgloopmanip.c | 1 + gcc/doc/loop.texi | 26 +++++++++++++++++++++++++ gcc/tree-ssa-loop-niter.c | 9 +++++++++ 6 files changed, 99 insertions(+) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 37c5c8e..62a75c9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,16 @@ +2016-07-29 Bin Cheng + + * 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. + 2016-07-29 Marek Polacek PR c/7652 diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 8f531b0..205562f 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -339,6 +339,7 @@ alloc_loop (void) loop->exits = ggc_cleared_alloc (); 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 6bd2d85..20476d7 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1015,6 +1015,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 95bb5cf..191a071 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2151,6 +2151,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) @@ -2236,6 +2240,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, -- 2.7.4