From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 112600 invoked by alias); 15 Oct 2019 15:49:41 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 112589 invoked by uid 89); 15 Oct 2019 15:49:40 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.7 required=5.0 tests=BAYES_00,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,KHOP_HELO_FCRDNS,SPF_NEUTRAL autolearn=ham version=3.3.1 spammy=enters, HX-Spam-Relays-External:sk:mail.th, H*RU:sk:mail.th, HX-HELO:sk:mail.th X-HELO: mail.theobroma-systems.com Received: from vegas.theobroma-systems.com (HELO mail.theobroma-systems.com) (144.76.126.164) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 15 Oct 2019 15:49:35 +0000 Received: from ip092042140082.rev.nessus.at ([92.42.140.82]:53948 helo=[10.4.9.214]) by mail.theobroma-systems.com with esmtpsa (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1iKP4j-0004hS-Cs; Tue, 15 Oct 2019 17:49:29 +0200 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Subject: Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134) From: Philipp Tomsich In-Reply-To: Date: Tue, 15 Oct 2019 16:01:00 -0000 Cc: Michael Matz , Richard Biener , "gcc-patches@gcc.gnu.org" , =?utf-8?Q?Christoph_M=C3=BCllner?= , erick.ochoa@theobroma-systems.com Content-Transfer-Encoding: quoted-printable Message-Id: <570EF6F3-6A76-4550-B8AB-0BD2486F3C3E@theobroma-systems.com> References: To: Feng Xue OS X-SW-Source: 2019-10/txt/msg01099.txt.bz2 Feng, This looks good from our side and has shown useful (combined with the other= 2 patches) in our testing with SPEC2017. Given that this looks final: what is the plan for getting this merged? Thanks, Philipp. > On 12.09.2019, at 12:23, Feng Xue OS wrote: >=20 > --- > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi > index 1391a562c35..28981fa1048 100644 > --- a/gcc/doc/invoke.texi > +++ b/gcc/doc/invoke.texi > @@ -11418,6 +11418,19 @@ The maximum number of branches unswitched in a s= ingle loop. > @item lim-expensive > The minimum cost of an expensive expression in the loop invariant motion. >=20 > +@item max-cond-loop-split-insns > +In a loop, if a branch of a conditional statement is selected since cert= ain > +loop iteration, any operand that contributes to computation of the condi= tional > +expression remains unchanged in all following iterations, the statement = is > +semi-invariant, upon which we can do a kind of loop split transformation. > +@option{max-cond-loop-split-insns} controls maximum number of insns to be > +added due to loop split on semi-invariant conditional statement. > + > +@item min-cond-loop-split-prob > +When FDO profile information is available, @option{min-cond-loop-split-p= rob} > +specifies minimum threshold for probability of semi-invariant 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 13001a7bb2d..12bc8c26c9e 100644 > --- a/gcc/params.def > +++ b/gcc/params.def > @@ -386,6 +386,20 @@ DEFPARAM(PARAM_MAX_UNSWITCH_LEVEL, > "The maximum number of unswitchings in a single loop.", > 3, 0, 0) >=20 > +/* The maximum number of increased insns due to loop split on semi-invar= iant > + condition statement. */ > +DEFPARAM(PARAM_MAX_COND_LOOP_SPLIT_INSNS, > + "max-cond-loop-split-insns", > + "The maximum number of insns to be added 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-invariant 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, >=20 > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C b/gcc/test= suite/g++.dg/tree-ssa/loop-cond-split-1.C > new file mode 100644 > index 00000000000..51f9da22fc7 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > @@ -0,0 +1,33 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-lsplit-details" } */ > + > +#include > +#include > + > +using namespace std; > + > +class A > +{ > +public: > + bool empty; > + void set (string s); > +}; > + > +class B > +{ > + map m; > + void f (); > +}; > + > +extern A *ga; > + > +void B::f () > +{ > + for (map::iterator iter =3D m.begin (); iter !=3D m.end (= ); ++iter) > + { > + if (ga->empty) > + ga->set (iter->second); > + } > +} > + > +/* { dg-final { scan-tree-dump-times "split loop 1 at branch" 1 "lsplit"= } } */ > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c b/gcc/test= suite/gcc.dg/tree-ssa/loop-cond-split-1.c > new file mode 100644 > index 00000000000..bbd522d6bcd > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c > @@ -0,0 +1,23 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-lsplit-details" } */ > + > +__attribute__((pure)) __attribute__((noinline)) int inc (int i) > +{ > + return i + 1; > +} > + > +extern int do_something (void); > +extern int b; > + > +void test(int n) > +{ > + int i; > + > + for (i =3D 0; i < n; i =3D inc (i)) > + { > + if (b) > + b =3D do_something(); > + } > +} > + > +/* { dg-final { scan-tree-dump-times "split loop 1 at branch" 1 "lsplit"= } } */ > diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c > index f5f083384bc..e4a1b6d2019 100644 > --- a/gcc/tree-ssa-loop-split.c > +++ b/gcc/tree-ssa-loop-split.c > @@ -32,7 +32,10 @@ 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 "tree-cfgcleanup.h" > #include "cfgloop.h" > +#include "params.h" > #include "tree-scalar-evolution.h" > #include "gimple-iterator.h" > #include "gimple-pretty-print.h" > @@ -40,7 +43,9 @@ along with GCC; see the file COPYING3. If not see > #include "gimple-fold.h" > #include "gimplify-me.h" >=20 > -/* This file implements loop splitting, i.e. transformation of loops like > +/* This file implements two kinds of loop splitting. > + > + One transformation of loops like: >=20 > for (i =3D 0; i < 100; i++) > { > @@ -612,6 +617,722 @@ split_loop (class loop *loop1, class tree_niter_des= c *niter) > return changed; > } >=20 > +/* Another transformation of loops like: > + > + for (i =3D INIT (); CHECK (i); i =3D NEXT ()) > + { > + if (expr (a_1, a_2, ..., a_n)) // expr is pure > + a_j =3D ...; // change at least one a_j > + else > + S; // not change any a_j > + } > + > + into: > + > + for (i =3D INIT (); CHECK (i); i =3D NEXT ()) > + { > + if (expr (a_1, a_2, ..., a_n)) > + a_j =3D ...; > + else > + { > + S; > + i =3D NEXT (); > + break; > + } > + } > + > + for (; CHECK (i); i =3D 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 memory_stores; > + > + /* Whether above memory stores vector has been filled. */ > + int need_init; > + > + split_info () : bbs (NULL), need_init (true) { } > + > + ~split_info () > + { > + if (bbs) > + free (bbs); > + } > +}; > + > +/* Find all statements with memory-write effect in LOOP, including memory > + store and non-pure function call, and keep those in a vector. This w= ork > + is only done one time, for the vector should be constant during analy= sis > + stage of semi-invariant condition. */ > + > +static void > +find_vdef_in_loop (struct loop *loop) > +{ > + split_info *info =3D (split_info *) loop->aux; > + gphi *vphi =3D get_virtual_phi (loop->header); > + > + /* Indicate memory store vector has been filled. */ > + info->need_init =3D false; > + > + /* If loop contains memory operation, there must be a virtual PHI node= in > + loop header basic block. */ > + if (vphi =3D=3D 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 j= ust > + links the first and the last virtual SSA names, by using the last as > + PHI operand to define the first. */ > + const edge latch =3D loop_latch_edge (loop); > + const tree first =3D gimple_phi_result (vphi); > + const tree last =3D 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 =3D 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 =3D=3D last) > + return; > + > + auto_vec other_stores; > + auto_vec 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 =3D worklist.pop (); > + gimple *stmt =3D SSA_NAME_DEF_STMT (vuse); > + > + /* We mark the first and last SSA names as visited at the beginnin= g, > + and reversely start the process from the last SSA name towards the > + first, which ensures 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) =3D=3D GIMPLE_PHI) > + { > + gphi *phi =3D as_a (stmt); > + > + for (unsigned i =3D 0; i < gimple_phi_num_args (phi); ++i) > + { > + tree arg =3D gimple_phi_arg_def (stmt, i); > + > + if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg))) > + worklist.safe_push (arg); > + } > + } > + else > + { > + tree prev =3D 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 an idea of of using them as shortcut > + terminators to memory alias analysis. */ > + if (gimple_code (stmt) =3D=3D GIMPLE_CALL) > + info->memory_stores.safe_push (stmt); > + else > + other_stores.safe_push (stmt); > + > + if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev))) > + worklist.safe_push (prev); > + } > + } while (!worklist.is_empty ()); > + > + info->memory_stores.safe_splice (other_stores); > +} > + > + > +/* Given STMT, memory load or pure call statement, check whether it is i= mpacted > + by some memory store in LOOP, excluding trace starting from SKIP_HEAD= (the > + trace is composed of SKIP_HEAD and those basic block dominated by it,= always > + corresponds to one branch of a conditional statement). If SKIP_HEAD = is > + NULL, all basic blocks of LOOP are checked. */ > + > +static bool > +vuse_semi_invariant_p (struct loop *loop, gimple *stmt, > + const_basic_block skip_head) > +{ > + split_info *info =3D (split_info *) loop->aux; > + > + /* Collect memory store/clobber statements if have not do that. */ > + if (info->need_init) > + find_vdef_in_loop (loop); > + > + tree rhs =3D is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NUL= L_TREE; > + ao_ref ref; > + gimple *store; > + unsigned i; > + > + ao_ref_init (&ref, rhs); > + > + FOR_EACH_VEC_ELT (info->memory_stores, i, store) > + { > + /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL. */ > + if (skip_head > + && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head)) > + continue; > + > + 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 since > + certain iteration of LOOP, check whether an SSA name (NAME) remains > + unchanged in next interation. We 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. If no= n- > + NULL, SSA name to check is supposed to be defined before SKIP_HEAD. = */ > + > +static bool > +ssa_semi_invariant_p (struct loop *loop, const tree name, > + const_basic_block skip_head) > +{ > + gimple *def =3D SSA_NAME_DEF_STMT (name); > + const_basic_block def_bb =3D 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; > + > + if (gimple_code (def) =3D=3D GIMPLE_PHI) > + { > + /* For PHI node that is not in loop header, its source operands sh= ould > + be defined inside the loop, which are seen as loop variant. */ > + if (def_bb !=3D loop->header || !skip_head) > + return false; > + > + const_edge latch =3D loop_latch_edge (loop); > + tree from =3D PHI_ARG_DEF_FROM_EDGE (as_a (def), latch); > + > + /* A PHI node in loop header 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 the PHI node to definition > + of latch value, if excluding branch trace from 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 =3D PHI | > + | | > + v | > + .------- if (cond) -------. | > + | | | > + | [ SKIP ] | > + | | | > + | x_2 =3D ... | > + | | | > + '---- T ---->.<---- F ----' | > + | | > + v | > + x_3 =3D PHI | > + | | > + '----------------------' > + > + 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 !=3D name) > + { > + /* A new value comes from a CONSTANT. */ > + if (TREE_CODE (from) !=3D SSA_NAME) > + return false; > + > + gimple *stmt =3D SSA_NAME_DEF_STMT (from); > + const_basic_block bb =3D gimple_bb (stmt); > + > + /* A new value comes from outside of loop. */ > + if (!bb || !flow_bb_inside_loop_p (loop, bb)) > + return false; > + > + from =3D NULL_TREE; > + > + if (gimple_code (stmt) =3D=3D GIMPLE_PHI) > + { > + gphi *phi =3D as_a (stmt); > + > + for (unsigned i =3D 0; i < gimple_phi_num_args (phi); ++i) > + { > + const_edge e =3D gimple_phi_arg_edge (phi, i); > + > + /* Not consider redefinitions in excluded basic blocks. */ > + 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, it is variant. */ > + if (from) > + return false; > + > + from =3D gimple_phi_arg_def (phi, i); > + } > + } > + } > + else if (gimple_code (stmt) =3D=3D GIMPLE_ASSIGN) > + { > + /* For simple value copy, check its rhs instead. */ > + if (gimple_assign_ssa_name_copy_p (stmt)) > + from =3D 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 iteratio= n. */ > + 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 STMT is semi-invariant in LOOP, iff all its operands are > + semi-invariant. Trace composed of basic block SKIP_HEAD and basic bl= ocks > + dominated by it are excluded from the loop. */ > + > +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 VARD= ECL, > + here we only need to check SSA name operands. This is because chec= k on > + VARDECL operands, which involve memory loads, must have been done > + prior to invocation of this function in vuse_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 when conditional statement never transfers execution to one= of its > + branch, whether we can remove the branch's leading basic block (BRANC= H_BB) > + and those basic blocks dominated by BRANCH_BB. */ > + > +static bool > +branch_removable_p (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 from opposite branch, or from some > + statement not dominated by the conditional statement. */ > + return false; > + } > + > + return true; > +} > + > +/* Find out which branch of a conditional statement (COND) is invariant = in the > + execution context of LOOP. That is: once the branch is selected in c= ertain > + iteration of the loop, any operand that contributes to computation of= the > + conditional statement remains unchanged in all following iterations. = */ > + > +static edge > +get_cond_invariant_branch (struct loop *loop, gcond *cond) > +{ > + basic_block cond_bb =3D gimple_bb (cond); > + basic_block targ_bb[2]; > + bool invar[2]; > + unsigned invar_checks; > + > + for (unsigned i =3D 0; i < 2; i++) > + { > + targ_bb[i] =3D 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 to break loop. 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 NULL; > + } > + > + invar_checks =3D 0; > + > + for (unsigned i =3D 0; i < 2; i++) > + { > + invar[!i] =3D false; > + > + if (!branch_removable_p (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] =3D 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 NULL; > + > + /* Found a real loop-invariant condition, do nothing. */ > + if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL)) > + return NULL; > + > + return EDGE_SUCC (cond_bb, (unsigned) invar[1]); > +} > + > +/* Calculate increased code size measured by estimated insn number if ap= plying > + loop split upon certain branch (BRANCH_EDGE) of a conditional stateme= nt. */ > + > +static int > +compute_added_num_insns (struct loop *loop, const_edge branch_edge) > +{ > + basic_block cond_bb =3D branch_edge->src; > + unsigned branch =3D EDGE_SUCC (cond_bb, 1) =3D=3D branch_edge; > + basic_block opposite_bb =3D EDGE_SUCC (cond_bb, !branch)->dest; > + basic_block *bbs =3D ((split_info *) loop->aux)->bbs; > + int num =3D 0; > + > + for (unsigned i =3D 0; i < loop->num_nodes; i++) > + { > + /* Do no count basic blocks only in opposite branch. */ > + if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb)) > + continue; > + > + num +=3D estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weight= s); > + } > + > + /* It is unnecessary to evaluate expression of the conditional stateme= nt > + in new loop that contains only invariant branch. This expresion sh= ould > + be constant value (either true or false). Exclude code size of ins= ns > + that contribute to computation of the expression. */ > + > + auto_vec worklist; > + hash_set removed; > + gimple *stmt =3D last_stmt (cond_bb); > + > + worklist.safe_push (stmt); > + removed.add (stmt); > + num -=3D estimate_num_insns (stmt, &eni_size_weights); > + > + do > + { > + ssa_op_iter opnd_iter; > + use_operand_p opnd_p; > + > + stmt =3D worklist.pop (); > + FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE) > + { > + tree opnd =3D USE_FROM_PTR (opnd_p); > + > + if (TREE_CODE (opnd) !=3D SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd)) > + continue; > + > + gimple *opnd_stmt =3D SSA_NAME_DEF_STMT (opnd); > + use_operand_p use_p; > + imm_use_iterator use_iter; > + > + if (removed.contains (opnd_stmt) > + || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt))) > + continue; > + > + FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd) > + { > + gimple *use_stmt =3D USE_STMT (use_p); > + > + if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt)) > + { > + opnd_stmt =3D NULL; > + break; > + } > + } > + > + if (opnd_stmt) > + { > + worklist.safe_push (opnd_stmt); > + removed.add (opnd_stmt); > + num -=3D estimate_num_insns (opnd_stmt, &eni_size_weights); > + } > + } > + } while (!worklist.is_empty ()); > + > + gcc_assert (num >=3D 0); > + return num; > +} > + > +/* Find out loop-invariant branch of a conditional statement (COND) if i= t has, > + and check whether it is eligible and profitable to perform loop split= upon > + this branch in LOOP. */ > + > +static edge > +get_cond_branch_to_split_loop (struct loop *loop, gcond *cond) > +{ > + edge invar_branch =3D get_cond_invariant_branch (loop, cond); > + > + if (!invar_branch) > + return NULL; > + > + profile_probability prob =3D invar_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 =3D PARAM_VALUE (PARAM_MIN_COND_LOOP_SPLIT_PROB); > + > + if (prob < profile_probability::always ().apply_scale (thres, 100)) > + return NULL; > + } > + > + /* Add a threshold for increased code size to disable loop split. */ > + if (compute_added_num_insns (loop, invar_branch) > + > PARAM_VALUE (PARAM_MAX_COND_LOOP_SPLIT_INSNS)) > + return NULL; > + > + return invar_branch; > +} > + > +/* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of s= ome > + conditional statement, 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 =3D 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 p= art > + of original one being splitted out. In loop1, a new bool temporary (= r) > + is introduced to keep value of the condition result. In original lat= ch > + edge of loop1, we insert a new conditional statement whose value comes > + from previous temporary (r), one of its branch goes back to loop1 hea= der > + 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 condit= ional > + statement candidate by setting a constant bool condition, based on wh= ich > + branch is semi-invariant. */ > + > +static bool > +do_split_loop_on_cond (struct loop *loop1, edge invar_branch) > +{ > + basic_block cond_bb =3D invar_branch->src; > + bool true_invar =3D !!(invar_branch->flags & EDGE_TRUE_VALUE); > + gcond *cond =3D as_a (last_stmt (cond_bb)); > + > + gcc_assert (cond_bb->loop_father =3D=3D loop1); > + > + 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 =3D 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 =3D make_ssa_name (boolean_type_node); > + gimple_stmt_iterator gsi =3D gsi_last_bb (cond_bb); > + gimple *stmt =3D 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); > + > + basic_block cond_bb_copy =3D get_bb_copy (cond_bb); > + gcond *cond_copy =3D as_a (last_stmt (cond_bb_copy)); > + > + /* Replace the condition in loop2 with a bool constant to let PassMana= ger > + remove the variant branch after current pass completes. */ > + 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 loop= 2, > + when loop1 enters into invariant state. */ > + basic_block latch_bb =3D split_edge (loop_latch_edge (loop1)); > + basic_block break_bb =3D split_edge (single_pred_edge (latch_bb)); > + gimple *break_cond =3D gimple_build_cond (EQ_EXPR, tmp, boolean_true_n= ode, > + NULL_TREE, NULL_TREE); > + > + gsi =3D gsi_last_bb (break_bb); > + gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT); > + > + edge to_loop1 =3D single_succ_edge (break_bb); > + edge to_loop2 =3D make_edge (break_bb, loop_preheader_edge (loop2)->sr= c, 0); > + > + to_loop1->flags &=3D ~EDGE_FALLTHRU; > + to_loop1->flags |=3D true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE; > + to_loop2->flags |=3D true_invar ? EDGE_TRUE_VALUE : 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 connecti= on > + 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; > +} > + > +/* Traverse all conditional statements in LOOP, to find out a good candi= date > + upon which we can do loop split. */ > + > +static bool > +split_loop_on_cond (struct loop *loop) > +{ > + split_info *info =3D new split_info (); > + basic_block *bbs =3D info->bbs =3D get_loop_body (loop); > + bool do_split =3D false; > + > + /* Allocate an area to keep temporary info, and associate its address > + with loop aux field. */ > + loop->aux =3D info; > + > + for (unsigned i =3D 0; i < loop->num_nodes; i++) > + { > + basic_block bb =3D bbs[i]; > + > + /* We only consider conditional statement, which be executed at mo= st once > + in each iteration of the loop. So skip statements in inner loops. */ > + if ((bb->loop_father !=3D loop) || (bb->flags & BB_IRREDUCIBLE_LOO= P)) > + continue; > + > + /* Actually this check is not a must constraint. With it, we can e= nsure > + conditional statement will always be executed in each iteration. */ > + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) > + continue; > + > + gimple *last =3D last_stmt (bb); > + > + if (!last || gimple_code (last) !=3D GIMPLE_COND) > + continue; > + > + gcond *cond =3D as_a (last); > + edge branch_edge =3D get_cond_branch_to_split_loop (loop, cond); > + > + if (branch_edge) > + { > + do_split_loop_on_cond (loop, branch_edge); > + do_split =3D true; > + break; > + } > + } > + > + delete info; > + loop->aux =3D NULL; > + > + return do_split; > +} > + > /* Main entry point. Perform loop splitting on all suitable loops. */ >=20 > static unsigned int > @@ -662,6 +1383,32 @@ tree_ssa_split_loops (void) > } > } >=20 > + if (changed) > + { > + cleanup_tree_cfg (); > + changed =3D false; > + } > + > + /* Perform loop splitting for suitable if-conditions in all loops. */ > + FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) > + loop->aux =3D NULL; > + > + FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) > + { > + if (loop->aux) > + { > + loop_outer (loop)->aux =3D loop; > + continue; > + } > + > + if (!optimize_loop_for_size_p (loop) > + && split_loop_on_cond (loop)) > + { > + loop_outer (loop)->aux =3D loop; > + changed =3D true; > + } > + } > + > FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) > loop->aux =3D NULL; >=20 > --=20 > 2.17.1 >=20