Re: [PATCH] Loop unswitching: support gswitch statements.

[Richard Biener <richard.guenther@gmail.com>]

On Tue, Nov 9, 2021 at 5:41 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 11/9/21 8:37 AM, Richard Biener wrote:
> > On Mon, Nov 8, 2021 at 8:45 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> >> On 11/8/21 10:05 AM, Martin Liška wrote:
> >>> On 9/28/21 22:39, Andrew MacLeod wrote:
> >>>> In Theory, modifying the IL should be fine, it happens already in
> >>>> places, but its not extensively tested under those conditions yet.
> >>> Hello Andrew.
> >>>
> >>> I've just tried using a global gimple_ranger and it crashes when loop
> >>> unswitching duplicates
> >>> some BBs.
> >>>
> >>> Please try the attached patch for:
> >> hey Martin,
> >>
> >> try using this in your tree.  Since nothing else is using a growing BB
> >> right now, I'll let you work with it and see if everything works as
> >> expected before checking it in, just in case we need more tweaking.
> >> With this,
> >>
> >> make RUNTESTFLAGS=dg.exp=loop-unswitch*.c check-gcc
> >>
> >> runs clean.
> >>
> >>
> >> basically, I tried to grow it by either a factor of 10% for the current
> >> BB size when the grow is requested, or some double the needed extra
> >> size, or 128... whichever value is "maximum"    That means it shoudnt be
> >> asking for tooo much each time, but also not a minimum amount.
> >>
> >> Im certainly open to suggestion on how much to grow it each time.
> >> Note the vector being grown is ONLY fo the SSA_NAme being asked for.. so
> >> it really an on-demand thing just for specific names, in your case,
> >> mostly just the switch index.
> >>
> >> Let me know how this works for you, and if you have any other issues.
> > So I think in the end we shouldn't need the growing.  Ideally we'd do all
> > the analysis before the first transform, but for that we'd need ranger to
> > be able to "simplify" conditions based on a known true/false predicate
> > that's not yet in the IL.  Consider
> >
> >   for (;;)
> >     {
> >          if (invariant < 3) // A
> >            {
> > ...
> >            }
> >          if (invariant < 5) // B
> >            {
> > ...
> >            }
> >     }
> >
> > unswitch analysis will run into the condition 'A' and determine the loop
> > can be unswitched with the condition 'invariant < 3'.  To be able to
> > perform cost assessment and to avoid redundant unswitching we
> > want to determine that if we unswitch with 'invariant < 3' being
> > true then the condition at 'B' is true as well before actually inserting
> > the if (invariant < 3) outside of the loop.
> >
> > So I'm thinking of assigning a gimple_uid to each condition we want to
> > unswitch on and have an array indexed by the uid with meta-data on
> > the unswitch opportunity, the "related" conditions could be marked with
> > the same uid (or some other), and the folding result recorded so that
> > at transform time we can just do the appropriate replacement without
> > invoking ranger again.
> >
> > Now, but how do we arrange for the ranger analysis here?
>
> well, i think there are multiple ways we could do this.    are you
> always doing this on
>
>    if (invariant < constant) or might it be another ssa-name?

It can be any other SSA name, including local (but also invariant)
defs that need to be moved.

> because if its always a  constant, you could ask for the range of
> invariant at  if (invariant < 3) when you unswitch it and it will
> provide you with [MIN, 2].
>
> when you look at  if (invariant < 5), you can try folding that stmt
> using the range you know already from above..   theres an API to
> fold_stmt() independent from ranger (in gimple-range-fold.h) which lets
> you supply ranges for ssa_names in the order they are found in the stmt,
>
>           bool fold_range (irange &r, gimple *s, irange &r1);
>
> so putting it together, you can do something like:
>
> // decide to unswitch this, as for the range of invariant on the TRUE edge:
> s1 = first_stmt   :  if (invariant < 3)
> range_of_expr (&ivrange, invariant, TRUE_EDGE)  //  This will set
> ivrange to [MIN, 2].. its value on the TRUE edge
>
> // Now we come to the second if, we try to fold it using the range from
> the first stmt.   if fold_stmt returns true, it mean stmt2_range will
> have the result of folding the stmt. only one range is supplied, so it
> will apply ivrange [MIN, 2] to the first ssa-name it encounters in the
> stmt, and [MIN, 2] < 5  so it will return bool [1,1] for the range of
> the stmt.
>
> s2 = second_stmt  : if (invariant < 5)
> if (fold_range (&stmt2_range, second_stmt, ivrange) &&
> stmt2_range.singleton_p ()
>    {
>        if (!stmt2_range.zero_p ())
>               // result is not zero, so that means this stmt will always
> be true given the range in ivrange substituted for "invariant",
>
> There is a fair amount of flexibility on exactly what you can do,
> depending on how complex you want to get.

So in some sense I want to evaluate general predicates, a more
complex example might be that we unswitch on

   if (pred1)

and later we see

   tem = pred1 & pred2;
   if (tem)

where for example pred2 might not be invariant and ideally we'd like to see that
by unswitching on 'pred1' on the false path the if (tem) part is dead
(so cost-wise it's free).  The current code doesn't get this - it simply
compares a gcond literally against the gcond of the current unswitching,
so in principle we can preserve exactly this capability but I thought that
the relation oracle could do better here - of course with the twist that
half of the IL is not there.  Basically I'd like to know whether there's a
way to "seed" the relation oracle with known true/false predicates on some
edge (or BB) and then do followup queries and then also roll back
the seeds and any possible effect the followup queries had on the cache.

Going further it would be nice to discover the unswitch predicate that
allows to resolve the most other predicates in the loop ;)

>    In some ways, you might be able to utilize Aldy's path-ranger that he
> uses in the threader.. and then it wouldn't matter how complex the
> conditions are, if you decide to unswitch the first condition, then
> you'd create a path thru the loop using the true edge and it would
> automatically pick up *all* the ranges that are true on that edge and
> apply them to the other conditions in the path you create.   In theory,
> without doing anything else, the the second condition should
> automatically fold to [1,1]  .  My guess is its too late in the cycle to
> be fooling around with that, because Im not sure if the path ranger is
> dynamically adjustable enough to build paths on the fly like that, or
> whether its more focused on its thread specific bits.. It may also work
> bottom to top, Im not sure.  But it also includes relations that turn
> out to be true and false as well as it goes.
>
> Regardless, we could work on enhancements that would function in this way.
>
> >
> > We might also somehow want to remember that on the
> > 'invariant < 3' == false copy of the loop there's still the
> > unswitching opportunity on 'invariant < 5', but not on the
> > 'invariant < 5' == true copy.
>
> tracking the same thing for the false edge would give you a range of [3,
> MAX]   when thats applied to invariant < 5, it'll return a range of bool
> [0,1], and singleton_p() will be false so you would know it doesnt
> resolve in that case
>
> Instead of tracking the ranges, if you are stashing the meta data which
> includes stmt, you can always pick up the ranges you want as you need
> them by making the range_of_expr() query. on the appropriate outgoing
> edge from the block with the condition
>
> ie, to get the range from the first stmt, you can simply ask for the
> range-of-expr() on  whichever edge you happen to care about (true or
> false) just when you want it.  You could stash it in the meta data or
> just re-ask when you need it depending on which decision was made.
>
> So you would just need to be able to key off the ssa-name in the
> condition that you unswitched I guess?

I agree that with conditions that resolve to constant ranges we could work
on those.  But I guess that's not general enough.

Anyway, I'll tell Martin to not use ranger for now but instead just replicate
the existing functionality.  The difficulty was originally in the fact that
we want to deal with switches, but that's not going to be simpler with
ranger - apart from the fact that for switches we _do_ have constant
ranges.  So there your suggestions above might indeed help.

Richard.

> Andrew
>