llvm dev - Jun 2017 - RFC: Killing undef and spreading poison

Sanjoy,
            in your blog post 
https://www.playingwithpointers.com/problem-with-undef.html
<https://www.playingwithpointers.com/problem-with-undef.html>
you describe a problem with LLVM “undef”,
yet in your paper http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf
<http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf>
you do not suggest fixing this problem, even though in chpt. 9 you identify
other
compilers that do attempt to avoid it.

It seems to me that since transforming a program with multiple uses of an
“undef” variable
into one with multiple distinct “undef”s results in behavior that is
inconsistent (and that
violates users expectations) we should not allow it.

This seems to me to be one of those situations where the phrase “extraordinary
claims
require extraordinary evidence” applies, and I’m not seeing any, are you ?


IIUC, a “freeze” operation can always be inserted over an “undef” (now “poison”)
that forces a single consistent value, but why the extra overhead of “freeze”,
as
there doesn’t seem to be a convincing argument for ever allowing the same
variable
to have inconsistent values, or am I missing something ?


Peter Lawrence.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170608/14b5cb27/attachment.html>

Hi,

On Thu, Jun 8, 2017 at 12:29 PM, Peter Lawrence
<peterl95124 at sbcglobal.net> wrote:
>
> Sanjoy,
>             in your blog post
> https://www.playingwithpointers.com/problem-with-undef.html
> you describe a problem with LLVM “undef”,
> yet in your paper http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf
> you do not suggest fixing this problem, even though in chpt. 9 you identify
> other
> compilers that do attempt to avoid it.
That problem is mentioned in section 3.2 (which quotes the same
example as in the blog post), and section 4 (the paragraph starting
with "Defining branching on poison to be UB further enables analyses
to assume that...") addresses how the new semantics plugs this gap.
> The reason I keep asking for additional examples is that this one where
> You have illegally transformed the ‘nsw’ isn’t convincing. So please,
Maybe we're talking past each other.  Let me first discuss the framing
of the problem as I see it:

 1. Whether a transform is illegal or not is decided by the semantics
    we've assigned to the IR.  In this case, whether hoisting the
    multiplication with the nsw intact is illegal or not is decided by
    the semantics we've assigned to nsw.

 2. We want certain transforms to be legal, which limits the kinds of
    semantics we can possibly have for the IR.  For instance, we
    certainly don't want a semantics for IR that disallows constant
    folding `add i32 1, 2`.

The example I gave was to demonstrate why the current (albeit not very
clearly specified) semantics is incorrect.

So when you ask for an example, are you asking why the set of
transforms we want to be correct in the new semantics (i.e. (2))
includes "hoist nsw-arithmetic out of control flow while still keeping
the flags"?  IOW, in the language used in the paper I linked to, are
you asking "why can't we have a overflowing nsw addition be immediate
UB"?  If so, that is covered in section 2.2 (but we can get into more
detail if you want).

-- Sanjoy

Sanjoy,
            Sorry, I guess I wasn’t specific enough, I’ll try again.  Excerpt 
from your blog post:

	"Another way to look at this is that undef isn’t a normal SSA value, and
uses of an undefvalue are also its defs.”

IMHO this was a bad definition from the get-go.

It seems to me that transforming a program with multiple uses of a single
undefined variable
into one with multiple distinct IR “undef”s results in behavior that is
inconsistent, and that
violates users expectations, and therefore we should not do it.

In other words the aspect of the current definition of “undef” in LLVM-IR that
seems to force
programs with undefined variables to be mis-represented is broken, and the
definition of “undef"
needs to be fixed.

Your proposal with “freeze” makes it possible to force all uses of an undefined
variable to be
consistent, but why not just do the simpler fix to “undef” / “poison” and allow
them to have
multiple uses, as opposed to “use once only, by definition of the IR”, which
does not seem
to have any benefit.

So again, “freeze” seems to be a workaround, rather than fixing the underlying
problem.


Thoughts ?


Peter Lawrence.


> On Jun 8, 2017, at 1:29 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi,
> 
> On Thu, Jun 8, 2017 at 12:29 PM, Peter Lawrence
> <peterl95124 at sbcglobal.net> wrote:
>> 
>> Sanjoy,
>>            in your blog post
>> https://www.playingwithpointers.com/problem-with-undef.html
>> you describe a problem with LLVM “undef”,
>> yet in your paper
http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf
>> you do not suggest fixing this problem, even though in chpt. 9 you
identify
>> other
>> compilers that do attempt to avoid it.
> 
> That problem is mentioned in section 3.2 (which quotes the same
> example as in the blog post), and section 4 (the paragraph starting
> with "Defining branching on poison to be UB further enables analyses
> to assume that...") addresses how the new semantics plugs this gap.
> 
>> The reason I keep asking for additional examples is that this one where
>> You have illegally transformed the ‘nsw’ isn’t convincing. So please,
> 
> Maybe we're talking past each other.  Let me first discuss the framing
> of the problem as I see it:
> 
> 1. Whether a transform is illegal or not is decided by the semantics
>    we've assigned to the IR.  In this case, whether hoisting the
>    multiplication with the nsw intact is illegal or not is decided by
>    the semantics we've assigned to nsw.
> 
> 2. We want certain transforms to be legal, which limits the kinds of
>    semantics we can possibly have for the IR.  For instance, we
>    certainly don't want a semantics for IR that disallows constant
>    folding `add i32 1, 2`.
> 
> The example I gave was to demonstrate why the current (albeit not very
> clearly specified) semantics is incorrect.
> 
> So when you ask for an example, are you asking why the set of
> transforms we want to be correct in the new semantics (i.e. (2))
> includes "hoist nsw-arithmetic out of control flow while still keeping
> the flags"?  IOW, in the language used in the paper I linked to, are
> you asking "why can't we have a overflowing nsw addition be
immediate
> UB"?  If so, that is covered in section 2.2 (but we can get into more
> detail if you want).
> 
> -- Sanjoy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170608/4e4ff249/attachment.html>