[PATCH] Loop unswitching: support gswitch statements.

[Martin Liška]

On 11/9/21 14:37, 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.

Calculating all this before transformation is quite ambitious based on the code
we have now.

Note one can have in a loop:

if (a > 100)
    ...

switch (a)
    case 1000:
      ...
    case 20:
      ...
    case 200:
      ...

which means the first predicate effectively makes some cases unreachable. Moreover
one can have

if (a > 100 && b < 300)
    ...

and more complex conditions.

> 
> Now, but how do we arrange for the ranger analysis here?

That's likely something we need support from ranger, yes.

> 
> 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.
> 
> Currently unswitching uses a custom simplify_using_entry_checks
> which tries to do simplification only after the fact (and so costing
> also is far from costing the true cost and ordering of the opportunities
> to do the best first is not implemented either).

I'm sending updated version of the patch where I changed:
- simplify_using_entry_checks is put back for the floating point expressions
- all scans utilize scan-tree-dump-times
- some new tests were added
- global ranger is used (I rely on the growing patch provided by Andrew)
- better ranger API is used for gcond expression: ranger.range_of_stmt (r, stmt) && r.singleton_p (&result))
- auto_edge_flag is used now

Patch can bootstrap on x86_64-linux-gnu and survives regression tests.

Thoughts?
Martin

> 
> Richard.
> 
>> Andrew
>>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Loop-unswitching-support-gswitch-statements.patch
Type: text/x-patch
Size: 24697 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20211109/6aa10035/attachment-0001.bin>