On Thu, 21 Oct 2021, Xionghu Luo wrote:
>
>
> On 2021/10/15 13:51, Xionghu Luo via Gcc-patches wrote:
> >
> >
> > On 2021/9/23 20:17, Richard Biener wrote:
> >> On Wed, 22 Sep 2021, Xionghu Luo wrote:
> >>
> >>>
> >>>
> >>> On 2021/8/11 17:16, Richard Biener wrote:
> >>>> On Wed, 11 Aug 2021, Xionghu Luo wrote:
> >>>>
> >>>>>
> >>>>>
> >>>>> On 2021/8/10 22:47, Richard Biener wrote:
> >>>>>> On Mon, 9 Aug 2021, Xionghu Luo wrote:
> >>>>>>
> >>>>>>> Thanks,
> >>>>>>>
> >>>>>>> On 2021/8/6 19:46, Richard Biener wrote:
> >>>>>>>> On Tue, 3 Aug 2021, Xionghu Luo wrote:
> >>>>>>>>
> >>>>>>>>> loop split condition is moved between loop1 and loop2, the split
> >>>>>>>>> bb's
> >>>>>>>>> count and probability should also be duplicated instead of (100% vs
> >>>>>>>>> INV),
> >>>>>>>>> secondly, the original loop1 and loop2 count need be propotional
> >>>>>>>>> from
> >>>>>>>>> the
> >>>>>>>>> original loop.
> >>>>>>>>>
> >>>>>>>>>
> >>>>>>>>> diff base/loop-cond-split-1.c.151t.lsplit
> >>>>>>>>> patched/loop-cond-split-1.c.151t.lsplit:
> >>>>>>>>> ...
> >>>>>>>>> int prephitmp_16;
> >>>>>>>>> int prephitmp_25;
> >>>>>>>>>
> >>>>>>>>> <bb 2> [local count: 118111600]:
> >>>>>>>>> if (n_7(D) > 0)
> >>>>>>>>> goto <bb 4>; [89.00%]
> >>>>>>>>> else
> >>>>>>>>> goto <bb 3>; [11.00%]
> >>>>>>>>>
> >>>>>>>>> <bb 3> [local count: 118111600]:
> >>>>>>>>> return;
> >>>>>>>>>
> >>>>>>>>> <bb 4> [local count: 105119324]:
> >>>>>>>>> pretmp_3 = ga;
> >>>>>>>>>
> >>>>>>>>> - <bb 5> [local count: 955630225]:
> >>>>>>>>> + <bb 5> [local count: 315357973]:
> >>>>>>>>> # i_13 = PHI <i_10(20), 0(4)>
> >>>>>>>>> # prephitmp_12 = PHI <prephitmp_5(20), pretmp_3(4)>
> >>>>>>>>> if (prephitmp_12 != 0)
> >>>>>>>>> goto <bb 6>; [33.00%]
> >>>>>>>>> else
> >>>>>>>>> goto <bb 7>; [67.00%]
> >>>>>>>>>
> >>>>>>>>> - <bb 6> [local count: 315357972]:
> >>>>>>>>> + <bb 6> [local count: 104068130]:
> >>>>>>>>> _2 = do_something ();
> >>>>>>>>> ga = _2;
> >>>>>>>>>
> >>>>>>>>> - <bb 7> [local count: 955630225]:
> >>>>>>>>> + <bb 7> [local count: 315357973]:
> >>>>>>>>> # prephitmp_5 = PHI <prephitmp_12(5), _2(6)>
> >>>>>>>>> i_10 = inc (i_13);
> >>>>>>>>> if (n_7(D) > i_10)
> >>>>>>>>> goto <bb 21>; [89.00%]
> >>>>>>>>> else
> >>>>>>>>> goto <bb 11>; [11.00%]
> >>>>>>>>>
> >>>>>>>>> <bb 11> [local count: 105119324]:
> >>>>>>>>> goto <bb 3>; [100.00%]
> >>>>>>>>>
> >>>>>>>>> - <bb 21> [local count: 850510901]:
> >>>>>>>>> + <bb 21> [local count: 280668596]:
> >>>>>>>>> if (prephitmp_12 != 0)
> >>>>>>>>> - goto <bb 20>; [100.00%]
> >>>>>>>>> + goto <bb 20>; [33.00%]
> >>>>>>>>> else
> >>>>>>>>> - goto <bb 19>; [INV]
> >>>>>>>>> + goto <bb 19>; [67.00%]
> >>>>>>>>>
> >>>>>>>>> - <bb 20> [local count: 850510901]:
> >>>>>>>>> + <bb 20> [local count: 280668596]:
> >>>>>>>>> goto <bb 5>; [100.00%]
> >>>>>>>>>
> >>>>>>>>> - <bb 19> [count: 0]:
> >>>>>>>>> + <bb 19> [local count: 70429947]:
> >>>>>>>>> # i_23 = PHI <i_10(21)>
> >>>>>>>>> # prephitmp_25 = PHI <prephitmp_5(21)>
> >>>>>>>>>
> >>>>>>>>> - <bb 12> [local count: 955630225]:
> >>>>>>>>> + <bb 12> [local count: 640272252]:
> >>>>>>>>> # i_15 = PHI <i_23(19), i_22(16)>
> >>>>>>>>> # prephitmp_16 = PHI <prephitmp_25(19), prephitmp_16(16)>
> >>>>>>>>> i_22 = inc (i_15);
> >>>>>>>>> if (n_7(D) > i_22)
> >>>>>>>>> goto <bb 16>; [89.00%]
> >>>>>>>>> else
> >>>>>>>>> goto <bb 11>; [11.00%]
> >>>>>>>>>
> >>>>>>>>> - <bb 16> [local count: 850510901]:
> >>>>>>>>> + <bb 16> [local count: 569842305]:
> >>>>>>>>> goto <bb 12>; [100.00%]
> >>>>>>>>>
> >>>>>>>>> }
> >>>>>>>>>
> >>>>>>>>> gcc/ChangeLog:
> >>>>>>>>>
> >>>>>>>>> * tree-ssa-loop-split.c (split_loop): Fix incorrect probability.
> >>>>>>>>> (do_split_loop_on_cond): Likewise.
> >>>>>>>>> ---
> >>>>>>>>> gcc/tree-ssa-loop-split.c | 16 ++++++++--------
> >>>>>>>>> 1 file changed, 8 insertions(+), 8 deletions(-)
> >>>>>>>>>
> >>>>>>>>> diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c
> >>>>>>>>> index 3a09bbc39e5..8e5a7ded0f7 100644
> >>>>>>>>> --- a/gcc/tree-ssa-loop-split.c
> >>>>>>>>> +++ b/gcc/tree-ssa-loop-split.c
> >>>>>>>>> @@ -583,10 +583,10 @@ split_loop (class loop *loop1)
> >>>>>>>>> basic_block cond_bb;
> >>>>>>>
> >>>>>>> if (!initial_true)
> >>>>>>> - cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
> >>>>>>> + cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond);
> >>>>>>> +
> >>>>>>> + edge true_edge = EDGE_SUCC (bbs[i], 0)->flags & EDGE_TRUE_VALUE
> >>>>>>> + ? EDGE_SUCC (bbs[i], 0)
> >>>>>>> + : EDGE_SUCC (bbs[i], 1);
> >>>>>>>
> >>>>>>>>>
> >>>>>>>>> class loop *loop2 = loop_version (loop1, cond, &cond_bb,
> >>>>>>>>> - profile_probability::always
> >>>>>>>>> (),
> >>>>>>>>> - profile_probability::always
> >>>>>>>>> (),
> >>>>>>>>> - profile_probability::always
> >>>>>>>>> (),
> >>>>>>>>> - profile_probability::always
> >>>>>>>>> (),
> >>>>>>>>> + true_edge->probability,
> >>>>>>>>> +
> >>>>>>>>> true_edge->probability.invert (),
> >>>>>>>>> + true_edge->probability,
> >>>>>>>>> +
> >>>>>>>>> true_edge->probability.invert (),
> >>>>>>>>> true);
> >>>>>>>>
> >>>>>>>> there is no 'true_edge' variable at this point.
> >>>>>>>
> >>>>>>> Sorry, missed the above hunk when split the patch.
> >>>>>>>
> >>>>>>>>
> >>>>>>>>> gcc_assert (loop2);
> >>>>>>>>> @@ -1486,10 +1486,10 @@ do_split_loop_on_cond (struct loop
> >>>>>>>>> *loop1,
> >>>>>>>>> edge invar_branch)
> >>>>>>>>> initialize_original_copy_tables ();
> >>>>>>>>>
> >>>>>>>>> struct loop *loop2 = loop_version (loop1, boolean_true_node,
> >>>>>>>>> NULL,
> >>>>>>>>> - profile_probability::always (),
> >>>>>>>>> - profile_probability::never (),
> >>>>>>>>> - profile_probability::always (),
> >>>>>>>>> - profile_probability::always (),
> >>>>>>>>> + invar_branch->probability.invert
> >>>>>>>>> (),
> >>>>>>>>> + invar_branch->probability,
> >>>>>>>>> + invar_branch->probability.invert
> >>>>>>>>> (),
> >>>>>>>>> + invar_branch->probability,
> >>>>>>>>> true);
> >>>>>>>>> if (!loop2)
> >>>>>>>>> {
> >>>>>>>>
> >>>>>>>> The patch introduction seems to talk about do_split_loop_on_cond
> >>>>>>>> only.
> >>>>>>>
> >>>>>>> split_loop faces similar issue though it sets the two branches to
> >>>>>>> 100% vs
> >>>>>>> 100%
> >>>>>>> and no scaling which seems also incorrect.
> >>>>>>>
> >>>>>>>> Since loop versioning inserts a condition with the passed
> >>>>>>>> probabilities
> >>>>>>>> but in this case a 'boolean_true_node' condition the then and else
> >>>>>>>> probabilities passed look correct. It's just the scaling arguments
> >>>>>>>> that look wrong? This loop_version call should get a comment as to
> >>>>>>>> why we are passing probabilities the way we do.
> >>>>>>>
> >>>>>>> This optimization is transforming from:
> >>>>>>>
> >>>>>>> for (i = 0; i < n; i = inc (i))
> >>>>>>> {
> >>>>>>> if (ga)
> >>>>>>> ga = do_something ();
> >>>>>>> }
> >>>>>>>
> >>>>>>> to:
> >>>>>>>
> >>>>>>> for (i = 0; i < x; i = inc (i))
> >>>>>>> {
> >>>>>>> if (true)
> >>>>>>> ga = do_something ();
> >>>>>>> if (!ga)
> >>>>>>> break;
> >>>>>>> }
> >>>>>>> for (; i < n; i = inc (i))
> >>>>>>> {
> >>>>>>> if (false)
> >>>>>>> ga = do_something ();
> >>>>>>> }
> >>>>>>>
> >>>>>>>
> >>>>>>> `boolean_true_node` is passed in to make the first loop's condition
> >>>>>>> statement to be 'true', after returning from loop_version, there is a
> >>>>>>> piece of code forcing the condition in second loop to be false,
> >>>>>>> and the original condition is moved from *in loop* to *exit edge*
> >>>>>>> between loop1 and loop2.
> >>>>>>
> >>>>>> Yes, one complication is that we use loop_version but do not retain
> >>>>>> the CFG it creates. Something like the vectorizers
> >>>>>> slpeel_tree_duplicate_loop_to_edge_cfg would be a better "fit"
> >>>>>> but then that code doesn't do any scaling yet. But then
> >>>>>> loop_version uses cfg_hook_duplicate_loop_to_header_edge and I suppose
> >>>>>> we could write a variant that simply doesn't mangle the CFG
> >>>>>> with a new condition switching between both loops but keeps them
> >>>>>> executed after each other ...
> >>>>>>
> >>>>>> As said, this adds to the confusion and some awkwardness.
> >>>>>
> >>>>> Then loop_version in loop split requires two types of variant, one
> >>>>> is to insert condition to loop preheader for 'split_loops' usage,
> >>>>> another is to insert condition to loop exit for 'do_split_loop_on_cond'
> >>>>> usage, it needs one extra function to encapsulate these cfg alterations
> >>>>> from outside to inside.
> >>>>>
> >>>>> unswitching only execute one loop as it only moves the invariant
> >>>>> condition
> >>>>> to first loop's pre-header. While 'split_loops' and
> >>>>> 'do_split_loop_on_cond'
> >>>>> may execute both loops no matter the condition is moved to the first
> >>>>> loop's
> >>>>> preheader or exit.
> >>>>>
> >>>>> The condition stmt in loop unswitching is invariant, but it is variant
> >>>>> in loop splitting, that's why loop unswitching execute only one loop
> >>>>> but loop splitting executes both loops.
> >>>>>
> >>>>> Seems we need two condition arguments for loop_version, one for
> >>>>> connecting
> >>>>> loop1 preheader to loop2 preheader, another one for connecting loop1's
> >>>>> exit
> >>>>> to loop2's header? Then it will be more generic for both unswitching
> >>>>> pass
> >>>>> and splitting pass. Looks a bit complicated and conflicted with
> >>>>> loop_version's
> >>>>> comments:
> >>>>>
> >>>>> /* Main entry point for Loop Versioning transformation.
> >>>>>
> >>>>> This transformation given a condition and a loop, creates
> >>>>> -if (condition) { loop_copy1 } else { loop_copy2 }, ... */
> >>>>>
> >>>>>
> >>>>> And this only works for loop split usage, those many other places
> >>>>> doesn't use loop_version like this?
> >>>>
> >>>> Yes, as said if you don't want the above CFG then you probably
> >>>> shouldn't use loop_version but instead use its building blocks
> >>>> (and some refactoring of loop_version can make that easier).
> >>>>
> >>>> I think splitting wants
> >>>>
> >>>> loop_copy1
> >>>> if (condition)
> >>>> loop_copy2
> >>>>
> >>>> IMHO it would be good to split 'loopify' into the actual loopification
> >>>> and the scaling. Basically make the part of loop_version that
> >>>> copies the loop on the header edge and creates a loop structure for
> >>>> it separate.
> >>>>
> >>>> loop distribution uses slpeel_tree_duplicate_loop_to_edge_cfg
> >>>> (copy_loop_before).
> >>>>
> >>>
> >>> Unfortunately slpeel_tree_duplicate_loop_to_edge_cfg only supports
> >>> copying loops with single exit, it would cause many ICEs in it even
> >>> building GCC stage1 (line 1065, line 1184 due to exit or new_exit
> >>> is NULL returning from single_exit (loop).). Seems loop_version is
> >>> more flexible for loop split.
> >>
> >> Hmm, sure - loop_version does not need to do anything special with
> >> exits since control flow either enters the original or the loop copy.
> >>
> >> But slpeel_tree_duplicate_loop_to_edge_cfg intends to create
> >> control flow that enters _both_ loops, so it needs to have
> >> an edge from the first loop exit to the second loop entry.
> >>
> >> One could extend this to a region copy, copying eventual CFG merges
> >> of exits and specifying which exit of a SEME region is supposed
> >> to be connected to the original region entry.
> >>
> >> After all that's what loop splitting needs in the end - though not
> >> sure what exactly it does with more than one exit.
> >
> > In tree-ssa-loop-split.c, split_loop only accepts single exit loop,
> > the recently added split_loop_on_cond could process multiple exits loop.
> >
> > For example, do some changes to the loop-cond-split-1.c,
> >
> > int ga;
> > extern int a;
> > extern int b;
> > extern int c;
> >
> > void test1 (int n) {
> > int i;
> > for (i = 0; i < n; i = inc (i)). {
> > if (a+3 > 0)
> > break;
> >
> > if (ga)
> > ga = do_something ();
> >
> > for (int j = 0; j < n; j++)
> > {
> > b+=5;
> > if (b > c) break;
> > }
> > }
> > }
> >
> > the "if (ga)" will be a new exit edge from loop_copy1 to loop_copy2.
> > I am not sure whether it is valuable to do semi-invariant loop split to such
> > cases with multiple exits, but obviously the split_loop_on_cond is a special
> > case from split_loop both duplicate loop to
> > if (condition1) {loop_copy1} if (condition2) {loop_copy2}
> > The only difference is condition1 is true for split_loop_on_cond.
> >
> >>
> >> So there's another set of "loop" copying, gimple_duplicate_sese_region,
> >> which doesn't actually require a single exit but a single "important"
> >> exit. That might match how you treat multiple exits.
> >
> > gimple_duplicate_sese_region doesn't handle subloops and latches. Finally,
> > I found that loop_version is still much better
> > than slpeel_tree_duplicate_loop_to_edge_cfg and gimple_duplicate_sese_region
> > since it could handle all cases like multiple exits/subloops, etc. I did
> > some
> > refactor to the code to introduce loop_version2 to create duplicated loops
> > with two input conditions as attached patch, is this reasonable enough?
> >
> > I also tried to copy the code in loop_version out of it to don't call
> > loop_version
> > in loop_version2, but it seems useless with many duplicate code and NOT get
> > rid
> > of creating "if (condition1) {loop_copy1}" at first?
> >
> >
>
> The previous attached patch
> 0001-Add-loop_version2-to-support-loop-transformation-wit.patch
> had issues when connecting two loops, reason is split_loop connect_loops at
> *exit* edge,
> do_split_loop_on_cond connect_loops at latch_edge. So they have different
> CFGs even
> both with two conditions :(. It seems not so that useful to also define
> another new function
> 'connect_loops_at_latch' given the limited usage in loop split only? And the
> loop_version2
> also looks not so general again ...
All I wanted to say is that none of the current high-level APIs we have
are a 1:1 match for loop splitting and that they in fact might do
stuff that's unnecessary or counter-productive. If inventing a new API
doesn't sound appealing then maybe refactoring an existing
(maybe loop_version) to expose re-usable pieces would make more sense.
For example loop_version currently does lv_adjust_loop_entry_edge
before it loopifys the copy inserted on the header. I wonder if
the condition generation can be done later and thus we can
have three pieces - 1) duplicating the loop on the entry edge,
2) adjusting the CFG to insert a condition branching to either loop,
3) from loopify extract the scale_loop_frequencies bits (in fact
loopify is only used from within cfgloopmanip.c)
That said, it shouldn't be a requirement to do all this to fix the
profile for loop splitting it's just that the current situation
does not help understanding of how the adjustment works.
Richard.
