Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Richard, Thanks for your comments. >+ /* For PHI node that is not in loop header, its source operands should >+be defined inside the loop, which are seen as loop variant. */ >+ if (def_bb != loop->header || !skip_head) >+ return false; > so if we have > > for (;;) > { > if (x) > a = ..; > else > a = ...; > if (cond-to-split-on dependent on a) > ... > } > > the above is too restrictive in case 'x' is semi-invariant as well, correct? In above case, cond-on-a will not be identified as semi-invariant, in that a is defined by PHI with real multi-sources. To handle it, besides each source value, we should add extra check on each source's control dependence node (x in the case), which might have not a little code expansion. Anyway, I'll have a try. >+ /* A new value comes from outside of loop. */ >+ if (!bb || !flow_bb_inside_loop_p (loop, bb)) >+ return false; > but that means starting from the second iteration the value is invariant. No. Traversal direction is reverse to loop execution. In the following, start from "x_1 = ", extract latch value x_3, and get x_3 definition, and finally reach "x_1 =". Loop: x_1 = PHI (x_0, x_3) ... x_3 = ... goto Loop; >+ /* Don't 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; > > they might be the same though, for PHIs with > 2 arguments. OK. Will add value equivalence check. > In the cycle handling you are not recursing via stmt_semi_invariant_p > but only handle SSA name copies - any particular reason for that? The cycle handling is specified for ssa that crosses iteration. It is semi-invariant if it remains unchanged after certain iteration, which means its value in previous iteration (coming from latch edge) is just a copy of its self, nothing else. So, recursion via stmt_semi_invariant_p is unnecessary. Loop: x_1 = PHI (x_0, x_3); x_2 = PHI(x_1, value defined in excluded branch); x_3 = x_2; goto Loop; >+static bool >+branch_removable_p (basic_block branch_bb) >+{ >+ if (single_pred_p (branch_bb)) >+return true; > > I'm not sure what this function tests - at least the single_pred_p check > looks odd to me given the dominator checks later. The single predecessor > could simply be a forwarder. I wonder if you are looking for branches forming > an irreducible loop? I think you can then check EDGE_IRREDUCIBLE_LOOP > or BB_IRREDUCIBLE_LOOP on the condition block (btw, I don't see > testcases covering the appearant special-cases in the patch - refering to > existing ones via a comment often helps understanding the code). Upon condition evaluation, if a branch is not selected, This function test a branch is reachable from other place other than its conditional statement. This ensure that when the branch is not selected upon condition evaluation, trace path led by the branch will never be executed so that it can be excluded during semi-invariantness analysis. If single_pred_p, only condition statement can reach the branch. If not, consider a half diamond condition control graph, with a back-edge to true branch. condition | \ | \ | false branch .--->. | / || | / othertrue branch || '---<' If there is an edge from false branch, true branch can not be excluded even it is not selected. And back edge from "other" (dominated by true branch) does not have any impact. >+ >+ return EDGE_SUCC (cond_bb, (unsigned) invar[1]); >+} > > magic ensures that invar[1] is always the invariant edge? Oh, it's a bool. > Ick. I wonder if logic with int invariant_edge = -1; and the loop setting > it to either 0 or 1 would be easier to follow... OK. > Note your stmt_semi_invariant_p check is exponential for a condition > like > > _1 = 1; > _2 = _1 + _1; > _3 = _2 + _2; > if (_3 != param_4(D)) > > because you don't track ops you already proved semi-invariant. We've > run into such situation repeatedly in SCEV analysis so I doubt it can be > disregarded as irrelevant in practice. A worklist approach could then > also get rid of the recursion. You are already computing the stmts > forming the condition in compute_added_num_insns so another option > is to re-use that. OK. > Btw, I wonder if we can simply re-use PARAM_MAX_PEELED_INSNS > instead of adding yet another param (it also happens to have the same > size). Because we are "peeling" the loop. I'll check that. >+ edge invar_branch = get_cond_invariant_branch (loop, cond); >+ >+ if (!invar_branch) >+return NULL; > >
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
gt; Sent: Wednesday, October 23, 2019 5:04 PM > To: Feng Xue OS > Cc: Michael Matz; Philipp Tomsich; gcc-patches@gcc.gnu.org; Christoph > Müllner; erick.oc...@theobroma-systems.com > Subject: Re: [PATCH V3] Loop split upon semi-invariant condition (PR > tree-optimization/89134) > > On Wed, Oct 23, 2019 at 5:36 AM Feng Xue OS > wrote: > > > > Michael, > > > > > I've only noticed a couple typos, and one minor remark. > > Typos corrected. > > > > > I just wonder why you duplicated these three loops instead of integrating > > > the real body into the existing LI_FROM_INNERMOST loop. I would have > > > expected your "if (!optimize_loop_for_size_p && split_loop_on_cond)" block > > > to simply be the else block of the existing > > > "if (... conditions for normal loop splitting ...)" block. > > Adjusted to do two kinds of loop-split in same LI_FROM_INNERMOST loop. > > > > > From my perspective it's okay, but you still need the okay of a proper > > > reviewer, > > > for which you might want to state the testing/regression state of this > > > patch relative to trunk. > > > > Richard, > > > > Is it ok to commit this patch? Bootstrap and regression test passed. And > > for > > performance, we can get about 7% improvement on spec2017 omnetpp with this > > patch. > > Can you please provide the corresponding ChangeLog entries as well and > attach the patch? It seems to be garbled by some encoding. > > Thanks, > Richard. > > > Thanks, > > Feng > > > > --- > > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi > > index 1407d019d14..d41e5aa0215 100644 > > --- a/gcc/doc/invoke.texi > > +++ b/gcc/doc/invoke.texi > > @@ -11481,6 +11481,19 @@ 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-loop-cond-split-insns > > +In a loop, if a branch of a conditional statement is selected since certain > > +loop iteration, any operand that contributes to computation of the > > conditional > > +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-loop-cond-split-insns} controls maximum number of insns to be > > +added due to loop split on semi-invariant conditional statement. > > + > > +@item min-loop-cond-split-prob > > +When FDO profile information is available, > > @option{min-loop-cond-split-prob} > > +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 322c37f8b96..73b59f7465e 100644 > > --- a/gcc/params.def > > +++ b/gcc/params.def > > @@ -415,6 +415,20 @@ 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_LOOP_COND_SPLIT_INSNS, > > + "max-loop-cond-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_LOOP_COND_SPLIT_PROB, > > + "min-loop-cond-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, > > > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > > new file mode 100644 > > index 000..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
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Patch attached. Feng From: Richard Biener Sent: Wednesday, October 23, 2019 5:04 PM To: Feng Xue OS Cc: Michael Matz; Philipp Tomsich; gcc-patches@gcc.gnu.org; Christoph Müllner; erick.oc...@theobroma-systems.com Subject: Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134) On Wed, Oct 23, 2019 at 5:36 AM Feng Xue OS wrote: > > Michael, > > > I've only noticed a couple typos, and one minor remark. > Typos corrected. > > > I just wonder why you duplicated these three loops instead of integrating > > the real body into the existing LI_FROM_INNERMOST loop. I would have > > expected your "if (!optimize_loop_for_size_p && split_loop_on_cond)" block > > to simply be the else block of the existing > > "if (... conditions for normal loop splitting ...)" block. > Adjusted to do two kinds of loop-split in same LI_FROM_INNERMOST loop. > > > From my perspective it's okay, but you still need the okay of a proper > > reviewer, > > for which you might want to state the testing/regression state of this > > patch relative to trunk. > > Richard, > > Is it ok to commit this patch? Bootstrap and regression test passed. And for > performance, we can get about 7% improvement on spec2017 omnetpp with this > patch. Can you please provide the corresponding ChangeLog entries as well and attach the patch? It seems to be garbled by some encoding. Thanks, Richard. > Thanks, > Feng > > --- > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi > index 1407d019d14..d41e5aa0215 100644 > --- a/gcc/doc/invoke.texi > +++ b/gcc/doc/invoke.texi > @@ -11481,6 +11481,19 @@ 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-loop-cond-split-insns > +In a loop, if a branch of a conditional statement is selected since certain > +loop iteration, any operand that contributes to computation of the > conditional > +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-loop-cond-split-insns} controls maximum number of insns to be > +added due to loop split on semi-invariant conditional statement. > + > +@item min-loop-cond-split-prob > +When FDO profile information is available, @option{min-loop-cond-split-prob} > +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 322c37f8b96..73b59f7465e 100644 > --- a/gcc/params.def > +++ b/gcc/params.def > @@ -415,6 +415,20 @@ 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_LOOP_COND_SPLIT_INSNS, > + "max-loop-cond-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_LOOP_COND_SPLIT_PROB, > + "min-loop-cond-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, > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > new file mode 100644 > index 000..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 = m.begin (); iter != m.end (); > ++iter) > +{ > + if (ga->empty) > +ga->set (iter->second); > +} > +} > + >
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
On Wed, Oct 23, 2019 at 5:36 AM Feng Xue OS wrote: > > Michael, > > > I've only noticed a couple typos, and one minor remark. > Typos corrected. > > > I just wonder why you duplicated these three loops instead of integrating > > the real body into the existing LI_FROM_INNERMOST loop. I would have > > expected your "if (!optimize_loop_for_size_p && split_loop_on_cond)" block > > to simply be the else block of the existing > > "if (... conditions for normal loop splitting ...)" block. > Adjusted to do two kinds of loop-split in same LI_FROM_INNERMOST loop. > > > From my perspective it's okay, but you still need the okay of a proper > > reviewer, > > for which you might want to state the testing/regression state of this > > patch relative to trunk. > > Richard, > > Is it ok to commit this patch? Bootstrap and regression test passed. And for > performance, we can get about 7% improvement on spec2017 omnetpp with this > patch. Can you please provide the corresponding ChangeLog entries as well and attach the patch? It seems to be garbled by some encoding. Thanks, Richard. > Thanks, > Feng > > --- > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi > index 1407d019d14..d41e5aa0215 100644 > --- a/gcc/doc/invoke.texi > +++ b/gcc/doc/invoke.texi > @@ -11481,6 +11481,19 @@ 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-loop-cond-split-insns > +In a loop, if a branch of a conditional statement is selected since certain > +loop iteration, any operand that contributes to computation of the > conditional > +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-loop-cond-split-insns} controls maximum number of insns to be > +added due to loop split on semi-invariant conditional statement. > + > +@item min-loop-cond-split-prob > +When FDO profile information is available, @option{min-loop-cond-split-prob} > +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 322c37f8b96..73b59f7465e 100644 > --- a/gcc/params.def > +++ b/gcc/params.def > @@ -415,6 +415,20 @@ 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_LOOP_COND_SPLIT_INSNS, > + "max-loop-cond-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_LOOP_COND_SPLIT_PROB, > + "min-loop-cond-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, > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > new file mode 100644 > index 000..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 = m.begin (); iter != 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/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c > new file mode 100644 > index 000..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 = 0; i < n; i = inc (i)) > +{ > + if (b) > +b = do_something(); > +} > +} > + > +/* { dg-final { scan-tree-dump-times "split loop 1 at branch" 1 "lsplit" } } > */ > diff --git
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Michael, > I've only noticed a couple typos, and one minor remark. Typos corrected. > I just wonder why you duplicated these three loops instead of integrating > the real body into the existing LI_FROM_INNERMOST loop. I would have > expected your "if (!optimize_loop_for_size_p && split_loop_on_cond)" block > to simply be the else block of the existing > "if (... conditions for normal loop splitting ...)" block. Adjusted to do two kinds of loop-split in same LI_FROM_INNERMOST loop. > From my perspective it's okay, but you still need the okay of a proper > reviewer, > for which you might want to state the testing/regression state of this > patch relative to trunk. Richard, Is it ok to commit this patch? Bootstrap and regression test passed. And for performance, we can get about 7% improvement on spec2017 omnetpp with this patch. Thanks, Feng --- diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1407d019d14..d41e5aa0215 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -11481,6 +11481,19 @@ 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-loop-cond-split-insns +In a loop, if a branch of a conditional statement is selected since certain +loop iteration, any operand that contributes to computation of the conditional +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-loop-cond-split-insns} controls maximum number of insns to be +added due to loop split on semi-invariant conditional statement. + +@item min-loop-cond-split-prob +When FDO profile information is available, @option{min-loop-cond-split-prob} +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 322c37f8b96..73b59f7465e 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -415,6 +415,20 @@ 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_LOOP_COND_SPLIT_INSNS, + "max-loop-cond-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_LOOP_COND_SPLIT_PROB, + "min-loop-cond-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, diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C new file mode 100644 index 000..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 = m.begin (); iter != 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/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c new file mode 100644 index 000..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 = 0; i < n; i = inc (i)) +{ + if (b) +b = 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..5cffd4bb508 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" @@
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Hello, I've only noticed a couple typos, and one minor remark. From my perspective it's okay, but you still need the okay of a proper reviewer, for which you might want to state the testing/regression state of this patch relative to trunk. The remarks follow: On Tue, 22 Oct 2019, Feng Xue OS wrote: > > > +/* 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- "iteration", "characteristic", remove "as" > > > + /* Not consider redefinitions in excluded basic blocks. */ "Don't consider" > > > + /* It is unnecessary to evaluate expression of the conditional > > > statement > > > + in new loop that contains only invariant branch. This expresion > > > should "expression" > > > @@ -662,6 +1383,32 @@ tree_ssa_split_loops (void) > > > } > > > } > > > > > > + if (changed) > > > +{ > > > + cleanup_tree_cfg (); > > > + changed = false; > > > +} > > > + > > > + /* Perform loop splitting for suitable if-conditions in all loops. */ > > > + FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) > > > +loop->aux = NULL; > > > + > > > + FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) > > > +{ > > > + if (loop->aux) > > > +{ > > > + loop_outer (loop)->aux = loop; > > > + continue; > > > + } > > > + > > > + if (!optimize_loop_for_size_p (loop) > > > + && split_loop_on_cond (loop)) > > > + { > > > + loop_outer (loop)->aux = loop; > > > + changed = true; > > > + } > > > +} > > > + > > > FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT) > > > loop->aux = NULL; I just wonder why you duplicated these three loops instead of integrating the real body into the existing LI_FROM_INNERMOST loop. I would have expected your "if (!optimize_loop_for_size_p && split_loop_on_cond)" block to simply be the else block of the existing "if (... conditions for normal loop splitting ...)" block. Either way it's okay with me. Ciao, Michael.
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Hi, Michael, Since gcc 10 release is coming, that will be good if we can add this patch before that. Thanks Feng. From: Michael Matz Sent: Wednesday, October 16, 2019 12:01 AM To: Philipp Tomsich Cc: Feng Xue OS; Richard Biener; gcc-patches@gcc.gnu.org; Christoph Müllner; erick.oc...@theobroma-systems.com Subject: Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134) Hi, On Tue, 15 Oct 2019, Philipp Tomsich wrote: > 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? I'll get to review this v3 version this week. Ciao, Michael. > > Thanks, > Philipp. > > > On 12.09.2019, at 12:23, Feng Xue OS > com> wrote: > > > > --- > > 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 > > single loop. > > @item lim-expensive > > The minimum cost of an expensive expression in the loop invariant motion. > > > > +@item max-cond-loop-split-insns > > +In a loop, if a branch of a conditional statement is selected since certain > > +loop iteration, any operand that contributes to computation of the > > conditional > > +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-prob} > > +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) > > > > +/* 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 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, > > > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > > new file mode 100644 > > index 000..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 = m.begin (); iter != 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/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c > > new file mode
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Hi Philipp, This is an updated patch based on comments form Michael, and if he think this is ok, we will merge it into trunk. Thanks, Feng From: Philipp Tomsich Sent: Tuesday, October 15, 2019 11:49 PM To: Feng Xue OS Cc: Michael Matz; Richard Biener; gcc-patches@gcc.gnu.org; Christoph Müllner; erick.oc...@theobroma-systems.com Subject: Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134) 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: > > --- > 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 > single loop. > @item lim-expensive > The minimum cost of an expensive expression in the loop invariant motion. > > +@item max-cond-loop-split-insns > +In a loop, if a branch of a conditional statement is selected since certain > +loop iteration, any operand that contributes to computation of the > conditional > +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-prob} > +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) > > +/* 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 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, > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > new file mode 100644 > index 000..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 = m.begin (); iter != 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/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c > new file mode 100644 > index 000..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 = 0; i < n; i = inc (i)) > +{ > + if (b) > +b = do_something(); > +} > +} > + > +
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Hi, On Tue, 15 Oct 2019, Philipp Tomsich wrote: > 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? I'll get to review this v3 version this week. Ciao, Michael. > > Thanks, > Philipp. > > > On 12.09.2019, at 12:23, Feng Xue OS > com> wrote: > > > > --- > > 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 > > single loop. > > @item lim-expensive > > The minimum cost of an expensive expression in the loop invariant motion. > > > > +@item max-cond-loop-split-insns > > +In a loop, if a branch of a conditional statement is selected since certain > > +loop iteration, any operand that contributes to computation of the > > conditional > > +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-prob} > > +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) > > > > +/* 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 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, > > > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > > new file mode 100644 > > index 000..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 = m.begin (); iter != 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/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c > > new file mode 100644 > > index 000..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 = 0; i < n; i = inc (i)) > > +{ > > + if (b) > > +b = 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
Re: [PATCH V3] Loop split upon semi-invariant condition (PR tree-optimization/89134)
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: > > --- > 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 > single loop. > @item lim-expensive > The minimum cost of an expensive expression in the loop invariant motion. > > +@item max-cond-loop-split-insns > +In a loop, if a branch of a conditional statement is selected since certain > +loop iteration, any operand that contributes to computation of the > conditional > +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-prob} > +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) > > +/* 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 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, > > diff --git a/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > b/gcc/testsuite/g++.dg/tree-ssa/loop-cond-split-1.C > new file mode 100644 > index 000..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 = m.begin (); iter != 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/testsuite/gcc.dg/tree-ssa/loop-cond-split-1.c > new file mode 100644 > index 000..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 = 0; i < n; i = inc (i)) > +{ > + if (b) > +b = 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" > > -/* This file implements loop splitting, i.e. transformation of loops like > +/* This file implements two kinds of loop splitting. > + > + One transformation of loops like: > >for (i = 0; i < 100; i++) > { > @@