On 5/19/21 5:13 AM, Richard Biener wrote:
On Tue, May 18, 2021 at 6:35 PM Andrew MacLeod <amacl...@redhat.com> wrote:
On 5/18/21 3:22 AM, Richard Biener wrote:
On Tue, May 18, 2021 at 1:23 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
The code in PR 100512 triggers an interaction between ranger and the
propagation engine related to undefined values.
I put the detailed analysis in the PR, but it boils down to the early
VRP pass has concluded that something is a constant and can be replaced,
and removes the definition expecting the constant to be propagated
everywhere.
If the code is in an undefined region that the CFG is going to remove,
we can find impossible situations,a nd ranger then changes that value ot
UNDEFINED.. because, well, it is. But then the propagation engine
panics because it doesnt have a constant any more, so odesnt replace it,
and now we have a used but not defined value.
Once we get to a globally constant range where further refinements can
only end up in an UNDEFINED state, stop further evaluating the range.
This is typically in places which are about to be removed by CFG cleanup
anyway, and it will make the propagation engine happy with no surprises.
Yeah, the propagation engine and EVRP as I know it relies on not visiting
"unexecutable" (as figured by anaysis) paths in the CFG and thus considering
edges coming from such regions not contributing conditions/values/etc. that
would cause such "undefinedness" to appear. Not sure how it works with
ranger, maybe that can as well get a mode where it does only traverse
EDGE_EXECUTABLE edges. Might be a bit difficult since IIRC it works
with SSA edges and not CFG edges.
Well it does do CFG based work as well, and I do not currently check
EDGE_EXECUTABLE... I just tried checking the EXECUTABLE_EDGE flag and
not processing it, but it doesn't resolve the problem. I think its
because the edge has not been determined unexecutable until after the
pass is done.. which is too late.
Bootstraps on x86_64-pc-linux-gnu with no regressions, and fixes the PR.
So that means the lattice isn't an optimistic lattice, right? EVRPs wasn't
optimistic either, but VRPs is/was. Whatever this means in this context ;)
It is optimistic, this just tells it to stop being optimistic if we get
to a constant so we don't mess up propagation.
Guess I'm confused - in classical terms an optimistic lattice
propagator only allows downward transitions UNDEF -> CONSTANT -> VARYING
while a non-optimistic one doesn't need to iterate and thus by definition
has no lattice "transition" other than from the initial VARYING to the
possibly non-VARYING but final state.
well, its not really a lattice, but to use those terms, we have aspects
of both.
We start with the global range which is calculated as best we can. That
forms the initial value (which may well be varying). We may later find
a better range for one or more inputs and recalculate that global range
and refine it. It only ever moves towards the UNDEFINED state from that
point..
When we initially propagate a value through the CFG via the on-entry
cache, we start with all affected blocks at UNDEFINED, mark the block(s)
which may generate/affect a range. We then calculate the range at each
of those points, and push those values thru the CFG. the range on entry
at each block is the union of all ranges on predecessor edges. This
means the propagator iteratively moves things from UNDEFINED towards the
initial global value... which provides the optimistic aspect of the
algorithm when setting the values in blocks.
If we later update the range of the ssa-name because we've discovered a
more refined range for an input, we "push" that new range into the
cache. That change is propagated thru the affected blocks in the CFG.
We look at each successor and see if this new value would affect its
value, and push it there if needed. That is the iterative aspect. At
this point, we are back to taking an existing known range, and further
refining it.
The on-demand part is that we only visit blocks that are needed between
the request and the Definition. We may later ask for a range in a
different part of the CFG, and we do the initial propagation from
UNDEFINED on just those blocks which haven't been previously calcluated
and do the optimistic propagation.
That is what is happening in that PR. we have started with a range,
evolved it to a constant, and then further refined it to undefined. In
general terms, I would say that is our model, but we have an optimistic
propagator which catches all the stuff VRP does with it optimistic lattice.
I will do a full on writeup of this eventually... complete with
drawings :-)
Andrew
