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

[Daniel Berlin via llvm-dev]

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

Whoops, hit send earlier.

Most of this gets taken care of by iterating in def-use order, but not for
phis or things dependent on them.

(especially if you want to resolve a phi node from a real value to undef)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161230/2bd8f75e/attachment.html>