[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: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>