[PATCH] Loop unswitching: support gswitch statements.

[Andrew MacLeod]

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?

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.

   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?

Andrew