Re: [PATCH] Replace EVRP in DOM with ranger.

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

On Thu, Apr 28, 2022 at 8:44 PM Jeff Law via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 4/28/2022 10:30 AM, Aldy Hernandez wrote:
> > [Jeff, this is the same patch I sent you last week with minor tweaks
> > to the commit message.]
> And I just dropped it into the tester.  We should have the vast majority
> of targets tested by this time tomorrow.
>
> >
> > [Despite the verbosity of the message, this is actually a pretty
> > straightforward patch.  It should've gone in last cycle, but there
> > was a nagging regression I couldn't get to until after stage1
> > had closed.]
> You had other, non-work/gcc priorities.  No worries at missing gcc-12.
>
>
> >
> > There are 3 uses of EVRP in DOM that must be converted.
> > Unfortunately, they need to be converted in one go, so further
> > splitting of this patch would be problematic.
> ACK
>
>
> > There's nothing here earth shattering.  It's all pretty obvious in
> > retrospect, but I've added a short description of each use to aid in
> > reviewing:
> >
> > * Convert evrp use in cprop to ranger.
> >
> >    This is easy, as cprop in DOM was converted to the ranger API last
> >    cycle, so this is just a matter of using a ranger instead of an
> >    evrp_range_analyzer.
> Yea.  We may have covered this before, but what does ranger do with a
> conditional equivalence?
>
> ie if we have something like
>
> if (a == b)
>    {
>      blah blah
>    }
>
> Within the true arm we know there's an equivalence.  *But* we don't want
> to just blindly replace a with b or vice-versa.  The equivalence is
> primarily useful for simplification rather than propagation.
>
> In fact, we every much do not want to cprop in these cases.   It rarely
> helps in a meaningful way and there's no good way to know which is the
> better value to use.  Canonicalization on SSA_NAMEs doesn't  really help
> due to SSA_NAME recycling.
>
>
> >
> > * Convert evrp use in threader to ranger.
> >
> >    The idea here is to use the hybrid approach we used for the initial
> >    VRP threader conversion last cycle.  The DOM threader will continue
> >    using the forward threader infrastructure while continuing to query
> >    DOM data structures, and only if the conditional does not relsolve,
> >    using the ranger.  This gives us the best of both worlds, and is a
> >    proven approach.
> >
> >    Furthermore, as frange and prange come live in the next cycle, we
> >    can move away from the forward threader altogether, and just add
> >    another backward threader.  This will not only remove the last use
> >    of the forward threader, but will allow us to remove at least 1 or 2
> >    threader instances.
> Excellent.
>
> >
> > * Convert conditional folding to use the method used by the ranger and
> >    evrp.  Previously DOM was calling into the guts of
> >    simplify_using_ranges::vrp_visit_cond_stmt.  The blessed way now is
> >    using fold_cond() which rewrites the conditional and edges
> >    automatically.
> >
> >    When legacy is removed, simplify_using_ranges will be further
> >    cleaned up, and there will only be one entry point into simplifying
> >    a statement.
> Sure.
>
> >
> > * DOM was setting global ranges determined from unreachable edges as a
> >    side-effect of using the evrp engine.  We must handle these cases
> >    before nuking evrp, and DOM seems like a good fit.  I've just moved
> >    the snippet to DOM, but it could live anywhere else we do a DOM
> >    walk.
>   It was a semi-desirable to record/refine global ranges in DOM, but I'd
> be surprised if too much code depended on that.  Presumably there's a
> testcase in the suite which we don't handle well if we don't let DOM
> refine/record global ranges?
>
> >
> >    For the record, this is the case *vrp handled:
> >
> >       <bb C>:
> >       ...
> >       if (c_5(D) != 5)
> >       goto <bb N>;
> >       else
> >       goto <bb M>;
> >       <bb N>:
> >       __builtin_unreachable ();
> >       <bb M>:
> >
> >    If M dominates all uses of c_5, we can set the global range of c_5
> >    to [5,5].
> And that will only happen if M eventually loops back to the conditional,
> right?  Otherwise all the uses wouldn't be dominated. I suspect this is
> exceedingly rare in practice an it looks really familiar.  This is
> coming from a testcase, right?

This is how we make use of assert() when it uses __builtin_unreachable.

Note the difficulty here is that we have to do this at a very specific point
in the pass pipeline (setting the global range), since the first time we'll
fold the if (c_5(D) != 5) it will be folded to false and the IL representation
of the assert() is gone.

So the idea was that with the IL present value-range analysis can determine
the range omf c_5(D) on the false path but once we remove it (and we do
want to remove it) we want to put a global range on c_5(D).

That means the best of both worlds would be to detect this pattern at
a specific point in the pass pipeline (somewhen before loop opts for sure)
and do both - remove the IL _and_ set the global range.  The fear of
doing this too early is of course that we lose the range by copy propagation
or similar transforms.  The fear of doing this change at a single place only
is that we miss it because there's a stray use before the conditional.

Note DOM is also run in pass_ipa_oacc_kernels which may be too early.

In the end we want to perform dead code elimination here so maybe
DCE is the best fit to do this (but as said we want to avoid doing this too
early).

> This is the only part of the patch that makes me go "ewwww", so I would
> like to at least explore if we can rethink the value of that test.
>
> > There is a a regression on Wstringop-overflow-4.C which I'm planning
> > on XFAILing.  It's another variant of the usual middle-end false
> > positives: having no ranges produces no warnings, but slightly refined
> > ranges, or worse-- isolating specific problematic cases in the
> > threader causes flare-ups.
> ACK.
>
>
> >
> > As an aside, as Richi has suggested, I think we should discuss
> > restricting the threader's ability to thread highly unlikely paths.
> > These cause no end of pain for middle-end warnings.  However,
> > I don't know if this would conflict with path isolation for
> > things like null dereferencing.  ISTR you were interested in this.
> I've never though too  much about it.  You're thinking of Richi :-)
>
> It's a balance.  I bet if we stop threading those paths we're going to
> see other issues start popping up like uninitialized warnings.
>
> It may be the case that it's really the constant propagation on an
> isolated path that's more problematical for those warnings.  But I would
> probably contend that what isolation is doing is showing how certain
> constant values can flow into places where they're not expected and
> could cause problems.  So I wouldn't necessary suggest throttling it.
>
> Happy to be proven wrong here!

I think we need to revisit the whole costing of threading which is of course
best done when we only have the backwards threader left.  I also always
wanted to play with some kind of optimistic code generation & rollback
on things like threading and unrolling, basically value-number the
duplicated stmts on-the-fly and make it "stop" when we reach a defined
threshold (and then throw away the result).  I never went around to
do this for unrolling since there we can end up duplicating diverging
control flow, but that at least doesn't happen with threading(?)

And just a note - please wait with installing this change - if approved - until
after GCC 12 is actually released.

Thanks,
Richard.

>
> >
> > BTW, I think the Wstringop-overflow-4.C test is problematic and I've
> > attached my analysis.  Basically the regression is caused by a bad
> > interaction with the rounding/alignment that placement new has inlined
> > into the IL.  This happens for int16_r[] which the test is testing.
> > Ranger can glean some range info, which causes DOM threading to
> > isolate a path which causes a warning.
> Presumably this is triggering a warning at the new() call?
>
> jeff