[llvm-dev] SCCP is not always correct in presence of undef (+ proposed fix)

[Daniel Berlin via llvm-dev]

On Fri, Dec 30, 2016 at 10:01 PM, Sanjoy Das <sanjoy at playingwithpointers.com
> wrote:

> Hi Daniel,
>
> On Fri, Dec 30, 2016 at 9:47 PM, Daniel Berlin <dberlin at dberlin.org>
> wrote:
> >>
> >>>   Is there a case in your algorithm in which treating an
> >>> unknown as an undef will be a problem?
> >>>
> > Yes, if you try to optimize undefs in any way, no if you move them to
> > overdefined :)
> >
> > IE given phi [a, undef, undef, undef]
> >
> > with just as many back edges, you will visit this node 4 times.
> >
> > If you start out with
> >
> > phi [a, undef, undef, undef], you may think "I know, i will make  these
> > undef's a".
> >
> > So you move everything to value
> >
> > phi [a, a, a, a]
> >
> > But remember, you really haven't visited the other 4 edges yet, so you
> don't
> > know if this is a valid value for undef (because of the rules around
> > and/or/etc, see http://llvm.org/docs/LangRef.html#undefined-values).
>
> But that's the same as case as:
>
>   %x = phi [a, <unknown>]
>
>

> Unless I know for sure that <unknown> is a, the *final result* can't
> report the phi as a.

Right, but we are talking about "when, in the intermediate state, can i
transform an undef to a different value".

Remember you can only go down the lattice. So you can't make undef
constant, and then discover it's wrong, and go back up :)
IE  can't change phi undef, undef to constant value 50, , discover 50
doesn't work, and say, well actually, let's make it undef again for an
iteration :)

So you need to know the point, *in the intermediate state*, when it is safe
to change the undefs.
That point is when all unknowns disappear because you have completed
visiting the entire CFG..


> However, the I thought the algorithm we're talking about here is
> optimistic, and we will initially fold %x to `a`, and then "try to
> see" if other edges are viable or not.  You're allowed to incorrectly
> optimistic results in the midst of the algorithm run (by design).
>

Yes, but, again, you still can't shove things back up the lattice :)

Maybe this will help:
In the past, the resolver forced things to be constant.  This is shoving
them down the lattice too far.  There was, as i said no way to push them
back up the lattice when they turned out wrong (and this  happened often
due to the iteration order differences).
If you want to do the stuff the resolver did, but do it at the right time,
you need the bit to tell you when you *can* shove them down to a constant.

You can store that bit however you want. You can store a bit that all
operands of an operation were visited at least once.
That is equivalent to "all operands != unknown".
But you can't dual purpose the bit with undef, because undef is an actual
value state. it tells you nothing about visited or unvisited, only the
value.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/7c6eef58/attachment.html>