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

[Daniel Berlin via llvm-dev]

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

(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".
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/063e2877/attachment.html>