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

>
>
> >
> > You need to distinguish between not visited and visited but undef.
>
> What I'm getting at is, if you're implementing something close to
the
> paper mentioned, I can't think of a case where you'd care to
> distinguish between "not visited" and "visited but
undef".  That is,
> instead of starting from "map each each instruction as not
visited" we
> should be able to (my unproven conjecture) start from "map each
> instruction to undef", making the "unknown" element
superfluous.
>
See the email i just sent.

Your scheme would work if you didn't want to optimize undef, because
you'd
just make meet (anything, undef) -> overdefined.
It's the "we want to fill in values for undef" that makes it so
you need to
know when you can actually do that.
(and as mentioned, you don't need a separate post-resolver to do *what we
do now*, and so far, it has just been a source of bugs :()
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/a0a0ac7d/attachment.html>

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.

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).

Otherwise we won't be able to get cases like:

loop:
  %x = phi [ 0 , entry ], [ 1, loop ]
  if (x != 0) br loop else br leave_loop
leave_loop;

  =>

loop:
  br leave_loop
leave_loop;


As far as I can tell, the <unknown> has the semantic "given the
viable
set of edges so far, there is no value assigned to this slot by the
program".  This has the same rewrite rules as undef as far as I can
tell.

However, if you have a case like

loop:
  %x = phi [ 0 , entry ], [ t, loop ]
  t = undef | 1
  if (condition) br loop else br leave_loop
leave_loop;

and you end up with x as phi(0, undef) *after* the algorithm has
terminated, then that is a bug in the undef propagation, since "undef
| 1" is not undef.
> (a, a, a, a of course, is just an example, you also don't know if
it's valid
> to always return undef, or 0, or 1, or anything at all, really).
>
> It's not until you hit this node for the 4th time, that you can really
> safely choose a value.
>
> If you have unknown and undef, it goes from
>
> phi [a, unknown, unknown, unknown] to phi [a, undef, unknown, unknown] to
> ...
>
> you know, once you have no unknown values, that everything you need to know
> to resolve it is known.
>
> (this is also why there is no need for a resolver. There really is no safe
> logic in the resolver that can't be pushed into the solver, though it
may
> make sense to structure it as a resolver if you think it's easier)
>
> Similarly for or %x, undef.
> You need to know if it's really undef, not "something i
haven't visited
> yet".
-- Sanjoy

On Fri, Dec 30, 2016 at 9:53 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>>
>> >
>> > You need to distinguish between not visited and visited but undef.
>>
>> What I'm getting at is, if you're implementing something close
to the
>> paper mentioned, I can't think of a case where you'd care to
>> distinguish between "not visited" and "visited but
undef".  That is,
>> instead of starting from "map each each instruction as not
visited" we
>> should be able to (my unproven conjecture) start from "map each
>> instruction to undef", making the "unknown" element
superfluous.
>
>
> See the email i just sent.
>
> Your scheme would work if you didn't want to optimize undef, because
you'd
> just make meet (anything, undef) -> overdefined.
> It's the "we want to fill in values for undef" that makes it
so you need to
> know when you can actually do that.
> (and as mentioned, you don't need a separate post-resolver to do *what
we do
> now*, and so far, it has just been a source of bugs :()
>


-- 
Sanjoy Das
http://playingwithpointers.com

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>