[PATCH] Loop unswitching: support gswitch statements.
Tue Nov 9 16:44:45 GMT 2021
On 11/9/21 14:37, Richard Biener wrote:
> On Mon, Nov 8, 2021 at 8:45 PM Andrew MacLeod <firstname.lastname@example.org> 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)
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 24697 bytes
Desc: not available
More information about the Gcc-patches