Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
On Mon, May 6, 2019 at 5:04 AM Feng Xue OS wrote:
>
> Hi Richard,
>
>
>Since gcc 9 has been released, will you get some time to take a look at
> this patch? Thanks.
I'm working through the backlog but I also hope Micha can have a look
here since he
authored the loop splitting code.
Richard.
>
> Feng
>
>
> From: Richard Biener
> 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
> 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 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 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
> > +
> > + 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
> >
> > 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 mot
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Hi Richard,
Since gcc 9 has been released, will you get some time to take a look at this
patch? Thanks.
Feng
From: Richard Biener
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 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 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 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
> +
> + 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
>
> 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 i
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
Ok. Got it. And I will add some cases.
Thanks,
Feng
From: Kyrill Tkachov
Sent: Wednesday, March 13, 2019 5:40:37 PM
To: Feng Xue OS; Richard Biener
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] Loop split upon semi-invariant condition (PR
tree-optimization/89134)
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
> 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
> 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 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 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
> > +
> > + 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
> >
> > PR middle-end/896
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
On 3/13/19 12:07 PM, Richard Biener wrote:
On Wed, Mar 13, 2019 at 10:40 AM Kyrill Tkachov
wrote:
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.
Note GCC 10 is due only next year.
Errr, yes. I meant that GCC 10 *development* will start once GCC 9 is
*released*.
Thanks,
Kyrill
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
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
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 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 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
+
+ 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
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
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
On Wed, Mar 13, 2019 at 10:40 AM Kyrill Tkachov
wrote:
>
> 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.
Note GCC 10 is due only next year.
> 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
> > 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
> > 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 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 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
> > > +
> > > + 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_con
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
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
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
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 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 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
> +
> + 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
>
> 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
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
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?
Regards,
Feng
From: Richard Biener
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 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 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 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
> +
> + 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
>
> 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,
> &quo
Re: [PATCH] Loop split upon semi-invariant condition (PR tree-optimization/89134)
On Tue, Mar 12, 2019 at 7:20 AM Feng Xue OS 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 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 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
> +
> + 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
>
> 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
