On 11/9/21 8:37 AM, Richard Biener wrote:
On Mon, Nov 8, 2021 at 8:45 PM Andrew MacLeod <amacl...@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
