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

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>

On Fri, Dec 30, 2016 at 10:54 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> 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 :)
>
In particular, this would have to  fall *down* to overdefined, not go back
*up* to undef.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/ee61cd96/attachment.html>

Hi Daniel,

On Fri, Dec 30, 2016 at 10:55 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>> 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 :)
If the kind of simplification (I think) you've mentioned is allowed,
then I think even Davide's lattice is problematic.  Say we have:

loop:
  X = phi(entry: undef, loop: T)
  ...
  T = undef
  if C then br loop else br outside

When we first visit X then we'll compute its state as (Undef MEET
Unknown) = Undef.  My guess is that you're implying that the Undef
lattice state (or some other computation hanging off of it) can be
folded immediately to, say, 50, but once we mark the backedge as
executable we'll set it to undef (or mark it as 49)?  And both of
these are bad because you're making a non-monotonic transition?  Given
this, I'm not sure what prevents the bad transform from happening even
if we have separate Unknown and Undef states.

If the solution is to not fold X into undef (which, by assumption, can
"spontaneously decay" into any value) until you're sure every
incoming
value is also undef then I suppose we'll need some special handling
for undef values to prevent breaking cases like (as shown earlier):

loop:
  X = phi(entry: 10, loop: T)
  if X == 10 then br outside else br loop

=>

loop:
  X = phi(entry: 10, loop: T)
  br outside

(i.e. to keep the algorithm properly optimistic)?

And if we do have a way of keeping undefs as undefs (i.e. prevent X
from decaying into 50 when we first visit the first loop) then why
can't we re-use the same mechanism to avoid spuriously decaying "phi
undef undef-but-actually-unknown" to "50"?

Another way of stating my suggestion is that, if you agree that this
is a correct lattice (different from Davide's proposal) and pretend
the "spontaneous undef decay" problem does not exist, then:

digraph G {
  Unknown -> Undef
  Undef -> Constant1
  Undef -> Constant2
  Undef -> Constant3
  Constant1 -> Bottom
  Constant2 -> Bottom
  Constant3-> Bottom
}

then it should be legal / correct to first drop every lattice element
from "Unknown" to "Undef" before running the algorithm.  The
only
cases where this would give us a conservative result is a place where
we'd have otherwise gotten "Unknown" for a used value; and the
algorithm should never have terminated in such a state.

-- Sanjoy