[PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Kyrill Tkachov
kyrylo.tkachov@foss.arm.com
Wed Mar 13 09:43:00 GMT 2019
Hi Feng,
On 3/13/19 1:56 AM, Feng Xue OS wrote:
> Richard,
>
> Â Â Â Thanks for your comment. Yes, it is like kind of jump threading
> with knowledge of loop structure. And what is rough time for GCC 10?
>
>
GCC 10 will be released once the number of P1 regressions gets down to
zero. Past experience shows that it's around the April/May timeframe.
In the meantime my comment on the patch is that you should add some
tests to the testsuite that showcase this transformation.
Thanks,
Kyrill
> Regards,
>
> Feng
>
>
> ________________________________
> From: Richard Biener <richard.guenther@gmail.com>
> Sent: Tuesday, March 12, 2019 4:31:49 PM
> To: Feng Xue OS
> Cc: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] Loop split upon semi-invariant condition (PR
> tree-optimization/89134)
>
> On Tue, Mar 12, 2019 at 7:20 AM Feng Xue OS
> <fxue@os.amperecomputing.com> wrote:
> >
> > This patch is composed to implement a loop transformation on one of
> its conditional statements, which we call it semi-invariant, in that
> its computation is impacted in only one of its branches.
> >
> > Suppose a loop as:
> >
> >Â Â Â Â void f (std::map<int, int> m)
> >Â Â Â Â {
> >Â Â Â Â Â Â Â Â for (auto it = m.begin (); it != m.end (); ++it) {
> >Â Â Â Â Â Â Â Â Â Â Â Â /* if (b) is semi-invariant. */
> >Â Â Â Â Â Â Â Â Â Â Â Â if (b) {
> >Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â b = do_something();Â Â Â /* Has effect on b */
> >Â Â Â Â Â Â Â Â Â Â Â Â } else {
> > /* No effect on b */
> >Â Â Â Â Â Â Â Â Â Â Â Â }
> >Â Â Â Â Â Â Â Â Â Â Â Â statements;Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Also no effect on b */
> >Â Â Â Â Â Â Â Â }
> >Â Â Â Â }
> >
> > A transformation, kind of loop split, could be:
> >
> >Â Â Â Â void f (std::map<int, int> m)
> >Â Â Â Â {
> >Â Â Â Â Â Â Â Â for (auto it = m.begin (); it != m.end (); ++it) {
> >Â Â Â Â Â Â Â Â Â Â Â Â if (b) {
> >Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â b = do_something();
> >Â Â Â Â Â Â Â Â Â Â Â Â } else {
> >Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â ++it;
> >Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â statements;
> >Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â break;
> >Â Â Â Â Â Â Â Â Â Â Â Â }
> >Â Â Â Â Â Â Â Â Â Â Â Â statements;
> >Â Â Â Â Â Â Â Â }
> >
> >Â Â Â Â Â Â Â Â for (; it != m.end (); ++it) {
> >Â Â Â Â Â Â Â Â Â Â Â Â statements;
> >Â Â Â Â Â Â Â Â }
> >Â Â Â Â }
> >
> > If "statements" contains nothing, the second loop becomes an empty
> one, which can be removed. (This part will be given in another patch).
> And if "statements" are straight line instructions, we get an
> opportunity to vectorize the second loop. In practice, this
> optimization is found to improve some real application by %7.
> >
> > Since it is just a kind of loop split, the codes are mainly placed
> in existing tree-ssa-loop-split module, and is controlled by
> -fsplit-loop, and is enabled with -O3.
>
> Note the transform itself is jump-threading with the threading
> duplicating a whole CFG cycle.
>
> I didn't look at the patch details yet since this is suitable for GCC
> 10 only.
>
> Thanks for implementing this.
> Richard.
>
> > Feng
> >
> >
> > diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> > index 64bf6017d16..a6c2878d652 100644
> > --- a/gcc/ChangeLog
> > +++ b/gcc/ChangeLog
> > @@ -1,3 +1,23 @@
> > +2019-03-12Â Feng Xue <fxue@os.amperecomputing.com>
> > +
> > +Â Â Â Â Â Â PR tree-optimization/89134
> > +Â Â Â Â Â Â Â * doc/invoke.texi (max-cond-loop-split-insns): Document new
> --params.
> > +Â Â Â Â Â Â (min-cond-loop-split-prob): Likewise.
> > +Â Â Â Â Â Â * params.def: Add max-cond-loop-split-insns,
> min-cond-loop-split-prob.
> > +Â Â Â Â Â Â * passes.def (pass_cond_loop_split) : New pass.
> > +Â Â Â Â Â Â * timevar.def (TV_COND_LOOP_SPLIT): New time variable.
> > +Â Â Â Â Â Â * tree-pass.h (make_pass_cond_loop_split): New declaration.
> > +Â Â Â Â Â Â * tree-ssa-loop-split.c (split_info): New class.
> > +Â Â Â Â Â Â (find_vdef_in_loop, vuse_semi_invariant_p): New functions.
> > +Â Â Â Â Â Â (ssa_semi_invariant_p, stmt_semi_invariant_p): Likewise.
> > +Â Â Â Â Â Â (can_branch_be_excluded, get_cond_invariant_branch): Likewise.
> > +Â Â Â Â Â Â (is_cond_in_hidden_loop, compute_added_num_insns): Likewise.
> > +Â Â Â Â Â Â (can_split_loop_on_cond, mark_cond_to_split_loop): Likewise.
> > +Â Â Â Â Â Â (split_loop_for_cond, tree_ssa_split_loops_for_cond): Likewise.
> > +Â Â Â Â Â Â (pass_data_cond_loop_split): New variable.
> > +Â Â Â Â Â Â (pass_cond_loop_split): New class.
> > +Â Â Â Â Â Â (make_pass_cond_loop_split): New function.
> > +
> > 2019-03-11 Jakub Jelinek <jakub@redhat.com>
> >
> >Â Â Â Â Â Â Â Â PR middle-end/89655
> > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
> > index df0883f2fc9..f5e09bd71fd 100644
> > --- a/gcc/doc/invoke.texi
> > +++ b/gcc/doc/invoke.texi
> > @@ -11316,6 +11316,14 @@ The maximum number of branches unswitched
> in a single loop.
> >Â @item lim-expensive
> >Â The minimum cost of an expensive expression in the loop invariant
> motion.
> >
> > +@item max-cond-loop-split-insns
> > +The maximum number of insns to be increased due to loop split on
> > +semi-invariant condition statement.
> > +
> > +@item min-cond-loop-split-prob
> > +The minimum threshold for probability of semi-invaraint condition
> > +statement to trigger loop split.
> > +
> >Â @item iv-consider-all-candidates-bound
> >Â Bound on number of candidates for induction variables, below which
> >Â all candidates are considered for each use in induction variable
> > diff --git a/gcc/params.def b/gcc/params.def
> > index 3f1576448be..2e067526958 100644
> > --- a/gcc/params.def
> > +++ b/gcc/params.def
> > @@ -386,6 +386,18 @@ DEFPARAM(PARAM_MAX_UNSWITCH_LEVEL,
> >Â Â Â Â Â Â Â Â "The maximum number of unswitchings in a single loop.",
> >Â Â Â Â Â Â Â Â 3, 0, 0)
> >
> > +/* The maximum number of increased insns due to loop split on
> semi-invariant
> > +  condition statement. */
> > +DEFPARAM(PARAM_MAX_COND_LOOP_SPLIT_INSNS,
> > +Â Â Â Â Â Â "max-cond-loop-split-insns",
> > +Â Â Â Â Â Â "The maximum number of insns to be increased due to loop
> split on semi-invariant condition statement.",
> > +Â Â Â Â Â Â 100, 0, 0)
> > +
> > +DEFPARAM(PARAM_MIN_COND_LOOP_SPLIT_PROB,
> > +Â Â Â Â Â Â "min-cond-loop-split-prob",
> > +Â Â Â Â Â Â "The minimum threshold for probability of semi-invaraint
> condition statement to trigger loop split.",
> > +Â Â Â Â Â Â 30, 0, 100)
> > +
> >Â /* The maximum number of insns in loop header duplicated by the
> copy loop
> >    headers pass. */
> >Â DEFPARAM(PARAM_MAX_LOOP_HEADER_INSNS,
> > diff --git a/gcc/passes.def b/gcc/passes.def
> > index 446a7c48276..bde7f4c50c0 100644
> > --- a/gcc/passes.def
> > +++ b/gcc/passes.def
> > @@ -265,6 +265,7 @@ along with GCC; see the file COPYING3. If not see
> >Â Â Â Â Â Â Â Â Â Â NEXT_PASS (pass_tree_unswitch);
> >Â Â Â Â Â Â Â Â Â Â NEXT_PASS (pass_scev_cprop);
> >Â Â Â Â Â Â Â Â Â Â NEXT_PASS (pass_loop_split);
> > +Â Â Â Â Â Â Â Â NEXT_PASS (pass_cond_loop_split);
> >Â Â Â Â Â Â Â Â Â Â NEXT_PASS (pass_loop_versioning);
> >Â Â Â Â Â Â Â Â Â Â NEXT_PASS (pass_loop_jam);
> >Â Â Â Â Â Â Â Â Â Â /* All unswitching, final value replacement and splitting
> can expose
> > diff --git a/gcc/timevar.def b/gcc/timevar.def
> > index 54154464a58..39f2df0e3ec 100644
> > --- a/gcc/timevar.def
> > +++ b/gcc/timevar.def
> > @@ -189,6 +189,7 @@ DEFTIMEVAR (TV_TREE_LOOP_IVCANONÂ Â Â Â , "tree
> canonical iv")
> >Â DEFTIMEVAR (TV_SCEV_CONSTÂ Â Â Â Â Â Â Â Â Â Â , "scev constant prop")
> >Â DEFTIMEVAR (TV_TREE_LOOP_UNSWITCHÂ Â Â , "tree loop unswitching")
> >Â DEFTIMEVAR (TV_LOOP_SPLITÂ Â Â Â Â Â Â Â Â Â Â , "loop splitting")
> > +DEFTIMEVAR (TV_COND_LOOP_SPLITÂ Â Â Â Â Â , "loop splitting for conditions")
> >Â DEFTIMEVAR (TV_LOOP_JAMÂ Â Â Â Â Â Â Â Â Â Â Â Â , "unroll and jam")
> >Â DEFTIMEVAR (TV_COMPLETE_UNROLLÂ Â Â Â Â Â , "complete unrolling")
> >Â DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops")
> > diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
> > index 47be59b2a11..f441ba36871 100644
> > --- a/gcc/tree-pass.h
> > +++ b/gcc/tree-pass.h
> > @@ -367,6 +367,7 @@ extern gimple_opt_pass *make_pass_lim
> (gcc::context *ctxt);
> >Â extern gimple_opt_pass *make_pass_linterchange (gcc::context *ctxt);
> >Â extern gimple_opt_pass *make_pass_tree_unswitch (gcc::context *ctxt);
> >Â extern gimple_opt_pass *make_pass_loop_split (gcc::context *ctxt);
> > +extern gimple_opt_pass *make_pass_cond_loop_split (gcc::context *ctxt);
> >Â extern gimple_opt_pass *make_pass_loop_jam (gcc::context *ctxt);
> >Â extern gimple_opt_pass *make_pass_predcom (gcc::context *ctxt);
> >Â extern gimple_opt_pass *make_pass_iv_canon (gcc::context *ctxt);
> > diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c
> > index 999c9a30366..d287a0d7d4c 100644
> > --- a/gcc/tree-ssa-loop-split.c
> > +++ b/gcc/tree-ssa-loop-split.c
> > @@ -32,7 +32,9 @@ along with GCC; see the file COPYING3. If not see
> >Â #include "tree-ssa-loop.h"
> >Â #include "tree-ssa-loop-manip.h"
> >Â #include "tree-into-ssa.h"
> > +#include "tree-inline.h"
> >Â #include "cfgloop.h"
> > +#include "params.h"
> >Â #include "tree-scalar-evolution.h"
> >Â #include "gimple-iterator.h"
> >Â #include "gimple-pretty-print.h"
> > @@ -40,7 +42,9 @@ along with GCC; see the file COPYING3. If not see
> >Â #include "gimple-fold.h"
> >Â #include "gimplify-me.h"
> >
> > -/* This file implements loop splitting, i.e. transformation of
> loops like
> > +/* This file implements two kind of loop splitting.
> > +
> > +Â Â One transformation of loops like:
> >
> >Â Â Â Â for (i = 0; i < 100; i++)
> >Â Â Â Â Â Â {
> > @@ -670,6 +674,803 @@ tree_ssa_split_loops (void)
> >Â Â Â return 0;
> >Â }
> >
> > +
> > +/* Another transformation of loops like:
> > +
> > +Â Â for (i = INIT (); CHECK (i); i = NEXT ())
> > +Â Â Â Â {
> > +Â Â Â Â Â Â if (expr (a_1, a_2, ..., a_n))
> > +Â Â Â Â Â Â Â Â a_j = ...;Â // change at least one a_j
> > +Â Â Â Â Â Â else
> > +Â Â Â Â Â Â Â Â S;Â Â Â Â Â Â Â Â Â // not change any a_j
> > +Â Â Â Â }
> > +
> > +Â Â into:
> > +
> > +Â Â for (i = INIT (); CHECK (i); i = NEXT ())
> > +Â Â Â Â {
> > +Â Â Â Â Â Â if (expr (a_1, a_2, ..., a_n))
> > +Â Â Â Â Â Â Â Â a_j = ...;
> > +Â Â Â Â Â Â else
> > +Â Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â Â S;
> > +Â Â Â Â Â Â Â Â Â Â i = NEXT ();
> > +Â Â Â Â Â Â Â Â Â Â break;
> > +Â Â Â Â Â Â Â Â }
> > +Â Â Â Â }
> > +
> > +Â Â for (; CHECK (i); i = NEXT ())
> > +Â Â Â Â {
> > +Â Â Â Â Â Â S;
> > +Â Â Â Â }
> > +
> > +Â Â */
> > +
> > +/* Data structure to hold temporary information during loop split upon
> > +Â Â semi-invariant conditional statement. */
> > +class split_info {
> > +public:
> > +Â /* Array of all basic blocks in a loop, returned by
> get_loop_body(). */
> > +Â basic_block *bbs;
> > +
> > +Â /* All memory store/clobber statements in a loop. */
> > +Â auto_vec<gimple *> stores;
> > +
> > +Â /* Whether above memory stores vector has been filled. */
> > +Â bool set_stores;
> > +
> > +Â /* Semi-invariant conditional statement, upon which to split loop. */
> > +Â gcond *cond;
> > +
> > + split_info () : bbs (NULL), set_stores (false), cond (NULL) { }
> > +
> > +Â ~split_info ()
> > +Â Â Â {
> > +Â Â Â Â Â if (bbs)
> > +Â Â Â Â Â Â Â free (bbs);
> > +Â Â Â }
> > +};
> > +
> > +/* Find all statements with memory-write effect in a loop,
> including memory
> > +Â Â store and non-pure function call, and keep those in a vector.
> This work
> > +Â Â is only done for one time, for the vector should be constant during
> > +Â Â analysis stage of semi-invariant condition. */
> > +
> > +static void
> > +find_vdef_in_loop (struct loop *loop)
> > +{
> > +Â split_info *info = (split_info *) loop->aux;
> > +Â gphi *vphi = get_virtual_phi (loop->header);
> > +
> > +Â /* Indicate memory store vector has been filled. */
> > +Â info->set_stores = true;
> > +
> > +Â /* If loop contains memory operation, there must be a virtual PHI
> node in
> > +Â Â Â Â loop header basic block. */
> > +Â if (vphi == NULL)
> > +Â Â Â return;
> > +
> > +Â /* All virtual SSA names inside the loop are connected to be a cyclic
> > +Â Â Â Â graph via virtual PHI nodes. The virtual PHI node in loop
> header just
> > +Â Â Â Â links the first and the last virtual SSA names, by using the
> last as
> > +Â Â Â Â PHI operand to define the first. */
> > +Â const edge latch = loop_latch_edge (loop);
> > +Â const tree first = gimple_phi_result (vphi);
> > +Â const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
> > +
> > +Â /* The virtual SSA cyclic graph might consist of only one SSA
> name, who
> > +Â Â Â Â is defined by itself.
> > +
> > +Â Â Â Â Â Â Â .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
> > +
> > +Â Â Â Â This means the loop contains only memory loads, so we can skip
> it. */
> > +Â if (first == last)
> > +Â Â Â return;
> > +
> > +Â auto_vec<gimple *> others;
> > +Â auto_vec<tree> worklist;
> > +Â auto_bitmap visited;
> > +
> > +Â bitmap_set_bit (visited, SSA_NAME_VERSION (first));
> > +Â bitmap_set_bit (visited, SSA_NAME_VERSION (last));
> > +Â worklist.safe_push (last);
> > +
> > +Â do
> > +Â Â Â {
> > +Â Â Â Â Â tree vuse = worklist.pop ();
> > +Â Â Â Â Â gimple *stmt = SSA_NAME_DEF_STMT (vuse);
> > +
> > +Â Â Â Â Â /* We mark the first and last SSA names as visited at the
> beginning,
> > +Â Â Â Â Â Â Â Â and reversely start the process from the last SSA name
> toward the
> > +Â Â Â Â Â Â Â Â first, which ensure that this do-while will not touch SSA
> names
> > +Â Â Â Â Â Â Â Â defined outside of the loop. */
> > +Â Â Â Â Â gcc_assert (gimple_bb (stmt)
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
> > +
> > +Â Â Â Â Â if (gimple_code (stmt) == GIMPLE_PHI)
> > +Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â gphi *phi = as_a <gphi *> (stmt);
> > +
> > +Â Â Â Â Â Â Â Â Â for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
> > +Â Â Â Â Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â tree arg = gimple_phi_arg_def (stmt, i);
> > +
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â worklist.safe_push (arg);
> > +Â Â Â Â Â Â Â Â Â Â Â }
> > +Â Â Â Â Â Â Â }
> > +Â Â Â Â Â else
> > +Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â tree prev = gimple_vuse (stmt);
> > +
> > +Â Â Â Â Â Â Â Â Â /* Non-pure call statement is conservatively assumed to
> impact
> > +Â Â Â Â Â Â Â Â Â Â Â Â all memory locations. So place call statements ahead
> of other
> > +Â Â Â Â Â Â Â Â Â Â Â Â memory stores in the vector with the idea of of using
> them as
> > +Â Â Â Â Â Â Â Â Â Â Â Â shortcut terminators to memory alias analysis, kind of
> > +Â Â Â Â Â Â Â Â Â Â Â Â optimization for compilation. */
> > +Â Â Â Â Â Â Â Â Â if (gimple_code (stmt) == GIMPLE_CALL)
> > +Â Â Â Â Â Â Â Â Â Â Â info->stores.safe_push (stmt);
> > +Â Â Â Â Â Â Â Â Â else
> > +Â Â Â Â Â Â Â Â Â Â Â others.safe_push (stmt);
> > +
> > +Â Â Â Â Â Â Â Â Â if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
> > +Â Â Â Â Â Â Â Â Â Â Â worklist.safe_push (prev);
> > +Â Â Â Â Â Â Â }
> > +Â Â Â } while (!worklist.is_empty ());
> > +
> > +Â Â Â info->stores.safe_splice (others);
> > +}
> > +
> > +
> > +/* Given a memory load or pure call statement, check whether it is
> impacted
> > +Â Â by some memory store in the loop excluding those basic blocks
> dominated
> > +Â Â by SKIP_HEAD (those basic blocks always corresponds to one branch of
> > +Â Â a conditional statement). If SKIP_HEAD is NULL, all basic blocks
> of the
> > +Â Â loop are checked. */
> > +
> > +static bool
> > +vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â const_basic_block skip_head)
> > +{
> > +Â split_info *info = (split_info *) loop->aux;
> > +
> > +Â /* Collect memory store/clobber statements if have not do that. */
> > +Â if (!info->set_stores)
> > +Â Â Â find_vdef_in_loop (loop);
> > +
> > +Â tree rhs = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) :
> NULL_TREE;
> > +Â ao_ref ref;
> > +Â gimple *store;
> > +Â unsigned i;
> > +
> > +Â ao_ref_init (&ref, rhs);
> > +
> > +Â FOR_EACH_VEC_ELT (info->stores, i, store)
> > +Â Â Â {
> > +Â Â Â Â Â /* Skip those basic blocks dominated by SKIP_HEAD. */
> > +Â Â Â Â Â if (skip_head
> > +Â Â Â Â Â Â Â Â Â && dominated_by_p (CDI_DOMINATORS, gimple_bb (store),
> skip_head))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â /* For a pure call, it is assumed to be impacted by any
> memory store.
> > +Â Â Â Â Â Â Â Â For a memory load, use memory alias analysis to check that. */
> > +Â Â Â Â Â if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
> > +Â Â Â Â Â Â Â return false;
> > +Â Â Â }
> > +
> > +Â return true;
> > +}
> > +
> > +/* Forward declaration */
> > +
> > +static bool
> > +stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â const_basic_block skip_head);
> > +
> > +/* Suppose one condition branch, led by SKIP_HEAD, is not executed
> in certain
> > +Â Â iteration, check whether an SSA name remains unchanged in next
> interation.
> > +Â Â We can call this characterisic as semi-invariantness. SKIP_HEAD
> might be
> > +Â Â NULL, if so, nothing excluded, all basic blocks and control
> flows in the
> > +Â Â loop will be considered. */
> > +
> > +static bool
> > +ssa_semi_invariant_p (struct loop *loop, const tree name,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â const_basic_block skip_head)
> > +{
> > +Â gimple *def = SSA_NAME_DEF_STMT (name);
> > +Â const_basic_block def_bb = gimple_bb (def);
> > +
> > +Â /* An SSA name defined outside a loop is definitely
> semi-invariant. */
> > +Â if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
> > +Â Â Â return true;
> > +
> > +Â /* This function is used to check semi-invariantness of a condition
> > +Â Â Â Â statement, and SKIP_HEAD is always given as head of one of its
> > +Â Â Â Â branches. So it implies that SSA name to check should be defined
> > +Â Â Â Â before the conditional statement, and also before SKIP_HEAD. */
> > +
> > +Â if (gimple_code (def) == GIMPLE_PHI)
> > +Â Â Â {
> > +Â Â Â Â Â /* In a normal loop, if a PHI node is located not in loop
> header, all
> > +Â Â Â Â Â Â Â Â its source operands should be defined inside the loop. As we
> > +Â Â Â Â Â Â Â Â mentioned before, these source definitions are ahead of
> SKIP_HEAD,
> > +Â Â Â Â Â Â Â Â and will not be bypassed. Therefore, in each iteration, any of
> > +Â Â Â Â Â Â Â Â these sources might be value provider to the SSA name,
> which for
> > +Â Â Â Â Â Â Â Â sure should not be seen as invariant. */
> > +Â Â Â Â Â if (def_bb != loop->header || !skip_head)
> > +Â Â Â Â Â Â Â return false;
> > +
> > +Â Â Â Â Â const_edge latch = loop_latch_edge (loop);
> > +Â Â Â Â Â tree from = PHI_ARG_DEF_FROM_EDGE (as_a <gphi *> (def), latch);
> > +
> > +Â Â Â Â Â /* A PHI node in loop header always contains two source operands,
> > +Â Â Â Â Â Â Â Â one is initial value, the other is the copy of last iteration
> > +Â Â Â Â Â Â Â Â through loop latch, we call it latch value. From this PHI node
> > +Â Â Â Â Â Â Â Â to definition of latch value, if excluding those basic blocks
> > +Â Â Â Â Â Â Â Â dominated by SKIP_HEAD, there is no definition of other
> version
> > +Â Â Â Â Â Â Â Â of same variable, SSA name defined by the PHI node is
> > +Â Â Â Â Â Â Â Â semi-invariant.
> > +
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â loop entry
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â .--- latch ---.
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â |
> > +                             v    v            |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â x_1 = PHI <x_0, x_3>Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +                          v                     |
> > +             .------- if (cond) -------.        |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â [ SKIP ]Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â |
> > +             |                    x_2 = ...    |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â '---- T ---->.<---- F ----'Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +                          v                     |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â x_3 = PHI <x_1, x_2>Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â '----------------------'
> > +
> > +Â Â Â Â Â Â Â Suppose in certain iteration, execution flow in above graph
> goes
> > +Â Â Â Â Â Â Â through true branch, which means that one source value to
> define
> > +Â Â Â Â Â Â Â x_3 in false branch (x2) is skipped, x_3 only comes from
> x_1, and
> > +Â Â Â Â Â Â Â x_1 in next iterations is defined by x_3, we know that x_1 will
> > +Â Â Â Â Â Â Â never changed if COND always chooses true branch from then
> on. */
> > +
> > +Â Â Â Â Â while (from != name)
> > +Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â /* A new value comes from a CONSTANT. */
> > +Â Â Â Â Â Â Â Â Â if (TREE_CODE (from) != SSA_NAME)
> > +Â Â Â Â Â Â Â Â Â Â Â return false;
> > +
> > +Â Â Â Â Â Â Â Â Â gimple *stmt = SSA_NAME_DEF_STMT (from);
> > +Â Â Â Â Â Â Â Â Â const_basic_block bb = gimple_bb (stmt);
> > +
> > +Â Â Â Â Â Â Â Â Â /* A new value comes from outside of loop. */
> > +Â Â Â Â Â Â Â Â Â if (!bb || !flow_bb_inside_loop_p (loop, bb))
> > +Â Â Â Â Â Â Â Â Â Â Â return false;
> > +
> > +Â Â Â Â Â Â Â Â Â from = NULL_TREE;
> > +
> > +Â Â Â Â Â Â Â Â Â if (gimple_code (stmt) == GIMPLE_PHI)
> > +Â Â Â Â Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â gphi *phi = as_a <gphi *> (stmt);
> > +
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â const_edge e = gimple_phi_arg_edge (phi, i);
> > +
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* Skip redefinition from basic blocks being
> excluded. */
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (!dominated_by_p (CDI_DOMINATORS, e->src,
> skip_head))
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* There are more than one source operands
> that can
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â provide value to the SSA name. */
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â if (from)
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â return false;
> > +
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â from = gimple_phi_arg_def (phi, i);
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â }
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â }
> > +Â Â Â Â Â Â Â Â Â Â Â }
> > +Â Â Â Â Â Â Â Â Â else if (gimple_code (stmt) == GIMPLE_ASSIGN)
> > +Â Â Â Â Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â /* For simple value copy, check its rhs instead. */
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â if (gimple_assign_ssa_name_copy_p (stmt))
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â from = gimple_assign_rhs1 (stmt);
> > +Â Â Â Â Â Â Â Â Â Â Â }
> > +
> > +Â Â Â Â Â Â Â Â Â /* Any other kind of definition is deemed to introduce a
> new value
> > +Â Â Â Â Â Â Â Â Â Â Â Â to the SSA name. */
> > +Â Â Â Â Â Â Â Â Â if (!from)
> > +Â Â Â Â Â Â Â Â Â Â Â return false;
> > +Â Â Â Â Â Â Â }
> > +Â Â Â Â Â Â Â return true;
> > +Â Â Â }
> > +
> > +Â /* Value originated from volatile memory load or return of normal
> (non-
> > +Â Â Â Â const/pure) call should not be treated as constant in each
> iteration. */
> > +Â if (gimple_has_side_effects (def))
> > +Â Â Â return false;
> > +
> > +Â /* Check if any memory store may kill memory load at this place. */
> > +Â if (gimple_vuse (def) && !vuse_semi_invariant_p (loop, def,
> skip_head))
> > +Â Â Â return false;
> > +
> > +Â /* Check operands of definition statement of the SSA name. */
> > +Â return stmt_semi_invariant_p (loop, def, skip_head);
> > +}
> > +
> > +/* Check whether a statement is semi-invariant, iff all its
> operands are
> > +Â Â semi-invariant. */
> > +
> > +static bool
> > +stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â const_basic_block skip_head)
> > +{
> > +Â ssa_op_iter iter;
> > +Â tree use;
> > +
> > +Â /* Although operand of a statement might be SSA name, CONSTANT or
> VARDECL,
> > +Â Â Â Â here we only need to check SSA name operands. For VARDECL operand
> > +Â Â Â Â involves memory load, check on VARDECL operand must have been done
> > +Â Â Â Â prior to invocation of this function in ssa_semi_invariant_p. */
> > +Â FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
> > +Â Â Â {
> > +Â Â Â Â Â if (!ssa_semi_invariant_p (loop, use, skip_head))
> > +Â Â Â Â Â Â Â return false;
> > +Â Â Â }
> > +
> > +Â return true;
> > +}
> > +
> > +/* Determine if unselect one branch of a conditional statement,
> whether we
> > +Â Â can exclude leading basic block of the branch and those basic blocks
> > +Â Â dominated by the leading one. */
> > +
> > +static bool
> > +can_branch_be_excluded (basic_block branch_bb)
> > +{
> > +Â if (single_pred_p (branch_bb))
> > +Â Â Â return true;
> > +
> > +Â edge e;
> > +Â edge_iterator ei;
> > +
> > +Â FOR_EACH_EDGE (e, ei, branch_bb->preds)
> > +Â Â Â {
> > +Â Â Â Â Â if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â Â /* The branch can be reached through other path, not just
> from the
> > +Â Â Â Â Â Â Â Â Â conditional statement. */
> > +Â Â Â Â Â return false;
> > +Â Â Â }
> > +
> > +Â return true;
> > +}
> > +
> > +/* Find out which branch of a conditional statement is invariant. That
> > +Â Â is: once the branch is selected in certain loop iteration, any
> operand
> > +Â Â that contributes to computation of the conditional statement remains
> > +Â Â unchanged in all following iterations. */
> > +
> > +static int
> > +get_cond_invariant_branch (struct loop *loop, gcond *cond)
> > +{
> > +Â basic_block cond_bb = gimple_bb (cond);
> > +Â basic_block targ_bb[2];
> > +Â bool invar[2];
> > +Â unsigned invar_checks;
> > +
> > +Â for (unsigned i = 0; i < 2; i++)
> > +Â Â Â {
> > +Â Â Â Â Â targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
> > +
> > +Â Â Â Â Â /* One branch directs to loop exit, no need to perform loop
> split upon
> > +Â Â Â Â Â Â Â Â this conditional statement. Firstly, it is trivial if the exit
> > +Â Â Â Â Â Â Â Â branch is semi-invariant, for the statement is just
> loop-breaking.
> > +Â Â Â Â Â Â Â Â Secondly, if the opposite branch is semi-invariant, it
> means that
> > +Â Â Â Â Â Â Â Â the statement is real loop-invariant, which is covered by loop
> > +Â Â Â Â Â Â Â Â unswitch. */
> > +Â Â Â Â Â if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
> > +Â Â Â Â Â Â Â return -1;
> > +Â Â Â }
> > +
> > +Â invar_checks = 0;
> > +
> > +Â for (unsigned i = 0; i < 2; i++)
> > +Â Â Â {
> > +Â Â Â Â Â invar[!i] = false;
> > +
> > +Â Â Â Â Â if (!can_branch_be_excluded (targ_bb[i]))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â /* Given a semi-invariant branch, if its opposite branch
> dominates
> > +Â Â Â Â Â Â Â Â loop latch, it and its following trace will only be
> executed in
> > +Â Â Â Â Â Â Â Â final iteration of loop, namely it is not part of repeated
> body
> > +Â Â Â Â Â Â Â Â of the loop. Similar to the above case that the branch is loop
> > +Â Â Â Â Â Â Â Â exit, no need to split loop. */
> > +Â Â Â Â Â if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
> > +Â Â Â Â Â invar_checks++;
> > +Â Â Â }
> > +
> > +Â /* With both branches being invariant (handled by loop unswitch) or
> > +Â Â Â Â variant is not what we want. */
> > +Â if (invar[0] ^ !invar[1])
> > +Â Â Â return -1;
> > +
> > +Â /* Found a real loop-invariant condition, do nothing. */
> > +Â if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
> > +Â Â Â return -1;
> > +
> > +Â return invar[1];
> > +}
> > +
> > +/* Return TRUE is conditional statement in a normal loop is also inside
> > +Â Â a nested non-recognized loop, such as an irreducible loop. */
> > +
> > +static bool
> > +is_cond_in_hidden_loop (const struct loop *loop, basic_block cond_bb,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int branch)
> > +{
> > +Â basic_block branch_bb = EDGE_SUCC (cond_bb, branch)->dest;
> > +
> > +Â if (cond_bb == loop->header || branch_bb == loop->latch)
> > +Â Â Â return false;
> > +
> > +Â basic_block *bbs = ((split_info *) loop->aux)->bbs;
> > +Â auto_vec<basic_block> worklist;
> > +
> > +Â for (unsigned i = 0; i < loop->num_nodes; i++)
> > +Â Â Â bbs[i]->flags &= ~BB_REACHABLE;
> > +
> > +Â /* Mark latch basic block as visited to be end point for
> reachablility
> > +Â Â Â Â traversal. */
> > +Â loop->latch->flags |= BB_REACHABLE;
> > +
> > +Â gcc_assert (flow_bb_inside_loop_p (loop, branch_bb));
> > +
> > +Â /* Start from specified branch, the opposite branch is ignored for it
> > +Â Â Â Â will not be executed. */
> > +Â branch_bb->flags |= BB_REACHABLE;
> > +Â worklist.safe_push (branch_bb);
> > +
> > +Â do
> > +Â Â Â {
> > +Â Â Â Â Â basic_block bb = worklist.pop ();
> > +Â Â Â Â Â edge e;
> > +Â Â Â Â Â edge_iterator ei;
> > +
> > +Â Â Â Â Â FOR_EACH_EDGE (e, ei, bb->succs)
> > +Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â basic_block succ_bb = e->dest;
> > +
> > +Â Â Â Â Â Â Â Â Â if (succ_bb == cond_bb)
> > +Â Â Â Â Â Â Â Â Â Â Â return true;
> > +
> > +Â Â Â Â Â Â Â Â Â if (!flow_bb_inside_loop_p (loop, succ_bb))
> > +Â Â Â Â Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â Â Â Â Â if (succ_bb->flags & BB_REACHABLE)
> > +Â Â Â Â Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â Â Â Â Â succ_bb->flags |= BB_REACHABLE;
> > +Â Â Â Â Â Â Â Â Â worklist.safe_push (succ_bb);
> > +Â Â Â Â Â Â Â }
> > +Â Â Â } while (!worklist.is_empty ());
> > +
> > +Â return false;
> > +}
> > +
> > +
> > +/* Calculate increased code size measured by estimated insn number if
> > +Â Â applying loop split upon certain branch of a conditional
> statement. */
> > +
> > +static int
> > +compute_added_num_insns (struct loop *loop, const_basic_block cond_bb,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int branch)
> > +{
> > +Â const_basic_block targ_bb_var = EDGE_SUCC (cond_bb, !branch)->dest;
> > +Â basic_block *bbs = ((split_info *) loop->aux)->bbs;
> > +Â int num = 0;
> > +
> > +Â for (unsigned i = 0; i < loop->num_nodes; i++)
> > +Â Â Â {
> > +Â Â Â Â Â /* Do no count basic blocks only in opposite branch. */
> > +Â Â Â Â Â if (dominated_by_p (CDI_DOMINATORS, bbs[i], targ_bb_var))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
> !gsi_end_p (gsi);
> > +Â Â Â Â Â Â Â Â Â Â gsi_next (&gsi))
> > +Â Â Â Â Â Â Â num += estimate_num_insns (gsi_stmt (gsi), &eni_size_weights);
> > +Â Â Â }
> > +
> > +Â return num;
> > +}
> > +
> > +/* Return true if it is eligible and profitable to perform loop
> split upon
> > +Â Â a conditional statement. */
> > +
> > +static bool
> > +can_split_loop_on_cond (struct loop *loop, gcond *cond)
> > +{
> > +Â int branch = get_cond_invariant_branch (loop, cond);
> > +
> > +Â if (branch < 0)
> > +Â Â Â return false;
> > +
> > +Â basic_block cond_bb = gimple_bb (cond);
> > +
> > +Â /* Add a threshold for increased code size to disable loop split. */
> > +Â if (compute_added_num_insns (loop, cond_bb, branch) >
> > +Â Â Â Â Â PARAM_VALUE (PARAM_MAX_COND_LOOP_SPLIT_INSNS))
> > +Â Â Â return false;
> > +
> > +Â /* In each interation, conditional statement candidate should be
> > +Â Â Â Â executed only once. */
> > +Â if (is_cond_in_hidden_loop (loop, cond_bb, branch))
> > +Â Â Â return false;
> > +
> > +Â profile_probability prob = EDGE_SUCC (cond_bb, branch)->probability;
> > +
> > +Â /* When accurate profile information is available, and execution
> > +Â Â Â Â frequency of the branch is too low, just let it go. */
> > +Â if (prob.reliable_p ())
> > +Â Â Â {
> > +Â Â Â Â Â int thres = PARAM_VALUE (PARAM_MIN_COND_LOOP_SPLIT_PROB);
> > +
> > +Â Â Â Â Â if (prob < profile_probability::always ().apply_scale (thres,
> 100))
> > +Â Â Â Â Â Â Â return false;
> > +Â Â Â }
> > +
> > +Â /* Temporarily keep branch index in conditional statement. */
> > +Â gimple_set_plf (cond, GF_PLF_1, branch);
> > +Â return true;
> > +}
> > +
> > +/* Traverse all conditional statements in a loop, to find out a good
> > +Â Â candidate upon which we can do loop split. */
> > +
> > +static bool
> > +mark_cond_to_split_loop (struct loop *loop)
> > +{
> > +Â split_info *info = new split_info ();
> > +Â basic_block *bbs = info->bbs = get_loop_body (loop);
> > +
> > +Â /* Allocate an area to keep temporary info, and associate its address
> > +Â Â Â Â with loop aux field. */
> > +Â loop->aux = info;
> > +
> > +Â for (unsigned i = 0; i < loop->num_nodes; i++)
> > +Â Â Â {
> > +Â Â Â Â Â basic_block bb = bbs[i];
> > +
> > +Â Â Â Â Â /* Skip statement in inner recognized loop, because we want that
> > +Â Â Â Â Â Â Â Â conditional statement executes at most once in each
> iteration. */
> > +Â Â Â Â Â if (bb->loop_father != loop)
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â /* Actually this check is not a must constraint. With it, we can
> > +Â Â Â Â Â Â Â Â ensure conditional statement will execute at least once in
> > +Â Â Â Â Â Â Â Â each iteration. */
> > +Â Â Â Â Â if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â gimple *last = last_stmt (bb);
> > +
> > +Â Â Â Â Â if (!last || gimple_code (last) != GIMPLE_COND)
> > +Â Â Â Â Â Â Â continue;
> > +
> > +Â Â Â Â Â gcond *cond = as_a <gcond *> (last);
> > +
> > +Â Â Â Â Â if (can_split_loop_on_cond (loop, cond))
> > +Â Â Â Â Â Â Â {
> > +Â Â Â Â Â Â Â Â Â info->cond = cond;
> > +Â Â Â Â Â Â Â Â Â return true;
> > +Â Â Â Â Â Â Â }
> > +Â Â Â }
> > +
> > +Â delete info;
> > +Â loop->aux = NULL;
> > +
> > +Â return false;
> > +}
> > +
> > +/* Given a loop with a chosen conditional statement candidate,
> perform loop
> > +Â Â split transformation illustrated as the following graph.
> > +
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â .-------T------ if (true) ------F------.
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â .---------------. |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â | |
> > +              v                   |              v v
> > +         pre-header               | pre-header
> > +              | .------------.    | | .------------.
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â | | |Â Â Â Â Â Â Â Â Â Â Â |
> > +              | v           |    | | v           |
> > +            header          |    | header          |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â [ bool r = cond; ]Â Â Â Â |Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +     .---- if (r) -----.    |    |       .--- if (true) ---.    |
> > +Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â |Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â |
> > + invariant            |    |    | invariant            |    |
> > +Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â |Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â |
> > +Â Â Â Â Â '---T--->.<---F---'Â Â Â Â |Â Â Â Â | '---T--->.<---F---'Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â / |Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +            stmts           |  / stmts           |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â Â Â |Â / |Â Â Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â / \Â Â Â Â Â Â Â Â Â Â Â Â | /Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â / \Â Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â .-------*Â Â *Â Â Â Â Â Â [ if (!r) ] .-------*Â Â *Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â |Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â |
> > +    |        latch         |            | latch         |
> > +Â Â Â Â |Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â | |Â Â Â Â Â Â Â Â Â Â |Â Â Â Â Â Â Â Â Â Â Â |
> > +Â Â Â Â |Â Â Â Â Â Â Â Â Â Â '------------' |Â Â Â Â Â Â Â Â Â Â '------------'
> > +Â Â Â Â '------------------------. .-----------'
> > +Â Â Â Â Â Â Â Â Â Â Â Â loop1Â Â Â Â Â Â Â Â Â Â Â | | loop2
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â v v
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â exits
> > +
> > +Â Â In the graph, loop1 represents the part derived from original
> one, and
> > +Â Â loop2 is duplicated using loop_version (), which corresponds to
> the part
> > +Â Â of original one being splitted out. In loop1, a new bool
> temporary (r)
> > +Â Â is introduced to keep value of the condition result. In original
> latch
> > +Â Â edge of loop1, we insert a new conditional statement whose value
> comes
> > +Â Â from previous temporary (r), one of its branch goes back to
> loop1 header
> > +Â Â as a latch edge, and the other branch goes to loop2 pre-header as an
> > +Â Â entry edge. And also in loop2, we abandon the variant branch of the
> > +Â Â conditional statement candidate by setting a constant bool
> condition,
> > +Â Â based on which branch is semi-invariant. */
> > +
> > +static bool
> > +split_loop_for_cond (struct loop *loop1)
> > +{
> > +Â split_info *info = (split_info *) loop1->aux;
> > +Â gcond *cond = info->cond;
> > +Â basic_block cond_bb = gimple_bb (cond);
> > +Â int branch = gimple_plf (cond, GF_PLF_1);
> > +Â bool true_invar = !!(EDGE_SUCC (cond_bb, branch)->flags &
> EDGE_TRUE_VALUE);
> > +
> > +Â if (dump_file && (dump_flags & TDF_DETAILS))
> > +Â Â {
> > +Â Â Â Â fprintf (dump_file, "In %s(), split loop %d at branch<%s>, BB
> %d\n",
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â current_function_name (), loop1->num,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â true_invar ? "T" : "F", cond_bb->index);
> > +Â Â Â Â print_gimple_stmt (dump_file, cond, 0, TDF_SLIM | TDF_VOPS);
> > +Â Â }
> > +
> > +Â initialize_original_copy_tables ();
> > +
> > +Â struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
> > + profile_probability::always (),
> > + profile_probability::never (),
> > + profile_probability::always (),
> > + profile_probability::always (),
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â true);
> > +Â if (!loop2)
> > +Â Â Â {
> > +Â Â Â Â Â free_original_copy_tables ();
> > +Â Â Â Â Â return false;
> > +Â Â Â }
> > +
> > +Â /* Generate a bool type temporary to hold result of the condition. */
> > +Â tree tmp = make_ssa_name (boolean_type_node);
> > +Â gimple_stmt_iterator gsi = gsi_last_bb (cond_bb);
> > +Â gimple *stmt = gimple_build_assign (tmp,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â gimple_cond_code (cond),
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â gimple_cond_lhs (cond),
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â gimple_cond_rhs (cond));
> > +
> > +Â gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
> > +Â gimple_cond_set_condition (cond, EQ_EXPR, tmp, boolean_true_node);
> > +Â update_stmt (cond);
> > +
> > +Â /* Replace the condition in loop2 with a bool constant to let pass
> > +Â Â Â Â manager remove the variant branch after current pass finishes. */
> > +Â basic_block cond_bb_copy = get_bb_copy (cond_bb);
> > +Â gcond *cond_copy = as_a<gcond *> (last_stmt (cond_bb_copy));
> > +
> > +Â if (true_invar)
> > +Â Â Â gimple_cond_make_true (cond_copy);
> > +Â else
> > +Â Â Â gimple_cond_make_false (cond_copy);
> > +
> > +Â update_stmt (cond_copy);
> > +
> > +Â /* Insert a new conditional statement on latch edge of loop1. This
> > +Â Â Â Â statement acts as a switch to transfer execution from loop1 to
> > +Â Â Â Â loop2, when loop1 enters into invariant state. */
> > +Â basic_block latch_bb = split_edge (loop_latch_edge (loop1));
> > +Â basic_block break_bb = split_edge (single_pred_edge (latch_bb));
> > +Â gimple *break_cond = gimple_build_cond (EQ_EXPR, tmp,
> boolean_true_node,
> > +Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â NULL_TREE, NULL_TREE);
> > +
> > +Â gsi = gsi_last_bb (break_bb);
> > +Â gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
> > +
> > +Â edge to_loop1 = single_succ_edge (break_bb);
> > +Â edge to_loop2 = make_edge (break_bb, loop_preheader_edge
> (loop2)->src, 0);
> > +
> > +Â to_loop1->flags &= ~EDGE_FALLTHRU;
> > +
> > +Â if (true_invar)
> > +Â Â Â {
> > +Â Â Â Â Â to_loop1->flags |= EDGE_FALSE_VALUE;
> > +Â Â Â Â Â to_loop2->flags |= EDGE_TRUE_VALUE;
> > +Â Â Â }
> > +Â else
> > +Â Â Â {
> > +Â Â Â Â Â to_loop1->flags |= EDGE_TRUE_VALUE;
> > +Â Â Â Â Â to_loop2->flags |= EDGE_FALSE_VALUE;
> > +Â Â Â }
> > +
> > +Â update_ssa (TODO_update_ssa);
> > +
> > +Â /* Due to introduction of a control flow edge from loop1 latch to
> loop2
> > +Â Â Â Â pre-header, we should update PHIs in loop2 to reflect this
> connection
> > +Â Â Â Â between loop1 and loop2. */
> > +Â connect_loop_phis (loop1, loop2, to_loop2);
> > +
> > +Â free_original_copy_tables ();
> > +
> > +Â rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
> > +
> > +Â return true;
> > +}
> > +
> > +/* Main entry point to perform loop splitting for suitable
> if-conditions
> > +Â Â in all loops. */
> > +
> > +static unsigned int
> > +tree_ssa_split_loops_for_cond (void)
> > +{
> > +Â struct loop *loop;
> > +Â auto_vec<struct loop *> loop_list;
> > +Â bool changed = false;
> > +Â unsigned i;
> > +
> > +Â FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
> > +Â Â Â loop->aux = NULL;
> > +
> > +Â /* Go through all loops starting from innermost. */
> > +Â FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
> > +Â Â Â {
> > +Â Â Â Â Â /* Put loop in a list if found a conditional statement
> candidate in
> > +Â Â Â Â Â Â Â Â the loop. This is stage for analysis, no change anything
> in the
> > +Â Â Â Â Â Â Â Â function. */
> > +Â Â Â Â Â if (!loop->aux
> > +Â Â Â Â Â Â Â Â Â && !optimize_loop_for_size_p (loop)
> > +Â Â Â Â Â Â Â Â Â && mark_cond_to_split_loop (loop))
> > +Â Â Â Â Â Â Â loop_list.safe_push (loop);
> > +
> > +Â Â Â Â Â /* If any of our inner loops was split, don't split us,
> > +Â Â Â Â Â Â Â Â and mark our containing loop as having had splits as well. */
> > +Â Â Â Â Â loop_outer (loop)->aux = loop->aux;
> > +Â Â Â }
> > +
> > +Â FOR_EACH_VEC_ELT (loop_list, i, loop)
> > +Â Â Â {
> > +Â Â Â Â Â /* Extract selected loop and perform loop split. This is
> stage for
> > +Â Â Â Â Â Â Â Â transformation. */
> > +Â Â Â Â Â changed |= split_loop_for_cond (loop);
> > +
> > +Â Â Â Â Â delete (split_info *) loop->aux;
> > +Â Â Â }
> > +
> > +Â FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
> > +Â Â Â loop->aux = NULL;
> > +
> > +Â if (changed)
> > +Â Â Â return TODO_cleanup_cfg;
> > +Â return 0;
> > +}
> > +
> > +
> > /* Loop splitting pass. */
> >
> >Â namespace {
> > @@ -716,3 +1517,48 @@ make_pass_loop_split (gcc::context *ctxt)
> >Â {
> >Â Â Â return new pass_loop_split (ctxt);
> >Â }
> > +
> > +namespace {
> > +
> > +const pass_data pass_data_cond_loop_split =
> > +{
> > +Â GIMPLE_PASS, /* type */
> > +Â "cond_lsplit", /* name */
> > +Â OPTGROUP_LOOP, /* optinfo_flags */
> > +Â TV_COND_LOOP_SPLIT, /* tv_id */
> > +Â PROP_cfg, /* properties_required */
> > +Â 0, /* properties_provided */
> > +Â 0, /* properties_destroyed */
> > +Â 0, /* todo_flags_start */
> > +Â 0, /* todo_flags_finish */
> > +};
> > +
> > +class pass_cond_loop_split : public gimple_opt_pass
> > +{
> > +public:
> > +Â pass_cond_loop_split (gcc::context *ctxt)
> > +Â Â Â : gimple_opt_pass (pass_data_cond_loop_split, ctxt)
> > +Â {}
> > +
> > +Â /* opt_pass methods: */
> > +Â virtual bool gate (function *) { return flag_split_loops != 0; }
> > +Â virtual unsigned int execute (function *);
> > +
> > +}; // class pass_cond_loop_split
> > +
> > +unsigned int
> > +pass_cond_loop_split::execute (function *fun)
> > +{
> > +Â if (number_of_loops (fun) <= 1)
> > +Â Â Â return 0;
> > +
> > +Â return tree_ssa_split_loops_for_cond ();
> > +}
> > +
> > +} // anon namespace
> > +
> > +gimple_opt_pass *
> > +make_pass_cond_loop_split (gcc::context *ctxt)
> > +{
> > +Â return new pass_cond_loop_split (ctxt);
> > +}
More information about the Gcc-patches
mailing list