The undef story

Part I.

The original LangRef appeared to be “nice and pretty”
and originally ‘undef’ did not seem to stick out.

Then evidence came to light in the form of bug reports, and
in the form of Dan Gohman’s email “the nsw story”, that all
was not good for ‘undef’ [1,2].

A proposal was made based on that evidence.
A presentation was made at an llvm gathering.
A paper was written. The proposal has even been
implemented and tested.

The IR might not be so “nice and pretty” anymore,
but at least all the known bugs could be closed.
I think everyone agreed that the case could be closed
based on the evidence at hand.

However new evidence has come to light,
the function-inlining example for one,
which the proposal does not address.

This means the case must be re-opened.

Now some folks seem upset over the fact that the new
evidence implies that the original bugs had not been
fully root-caused and that a simpler solution exists.

But this is not a reason to be upset, rather it is a reason to
be pleased that the IR can be restored to its original “nice
and pretty” status,

and I think Dan Gohman would be pleased.

Part II.

That the current LangRef IR definition of “undef” is incorrect
is not immediately obvious, it has gone unnoticed for a long
time, and has become lodged in peoples minds as unquestionable.
Instead folks have viewed it as insufficient, and piled on
fixes in the form of “poison” and “freeze”.

Here are examples of why the current definition of “undef”,
which explicitly assumes that it is correct to copy-propagate
“x = undef” everywhere “x” occurs, is incorrect:

From 3.2 in “Taming Undefined Behavior in LLVM” [3]

*** This shows that the current definition blocks a
highly desirable and otherwise legal optimization. ***

if (k != 0) {
while (cond) {
t = 1/k;
use(t);
}
}
-----> hoist loop invariant ----->
if (k != 0) {
t = 1/k;
while (cond) {
use(t);
}
}

This becomes illegal when later “k” is replaced
with “undef” because then “(undef != 0)” and
“t = 1/undef” need not be consistent,and the
program can incorrectly divide-by-zero. So this
is an example of why copy-propagation of “undef”
is undesirable.

From “Function Inlining and undef / poison question” [4]

*** This shows that the current definition creates illegal
translations. ***

this function always executes statement S
foo(a)
{
if (a == a)
S;
}
but in llvm when foo is inlined and “a” is replaced
with “undef” then nothing can be said about whether
statement S is executed because “(undef == undef)”
can go either way with the current definition. So this
is an example of why copy-propagation of “undef” is
illegal.

These problems cannot be fixed by adding “poison” or “freeze”,
it is “undef” itself that is inherently flawed.

Part III.

Here is the offending paragraph in the LangRef, from “Undefined Values” :

This example points out that two ‘undef‘ operands are not necessarily
the same. This can be surprising to people (and also matches C
semantics) where they assume that “X^X” is always zero, even if X is
undefined. This isn’t true for a number of reasons, but the short
answer is that an ‘undef‘ “variable” can arbitrarily change its value
over its “live range”. This is true because the variable doesn’t
actually have a live range. Instead, the value is logically read from
arbitrary registers that happen to be around when needed, so the value
is not necessarily consistent over time.

The purported benefit of this definition comes down to a register allocation
argument in that you don’t need a register for an uninitialized variable.
But this benefit has never been shown, and if it ever does become important then
it should be handled in the register allocator, not in the IR.

While the evidence of the harm of this definition is overwhelming. It leads to
translations like “x ^ x” not necessarily being 0 that are non-sensical (no
matter what you think the C standard says), the inability to hoist a loop
invariant divide out of a loop, and the function-inlining example which is
patently illegal.

The LangRef’s definition of “undef” needs to be rewritten so that “x = undef”
simply means that this is where the live range of x starts, and that it is
uninitialized. Another way to think of it is as an incoming argument register,
which similarly has an unknown (ie “undef”) but stable bit pattern.

(in fact you’ll know the compiler correctly implements “undef” when you
can insert “x = undef” into a function’s entry block for each incomming
argument, and (without any inlining or other IPA of course) it still compiles
AOK at the IR level (you’d have to strip them back out before codegen))

The LangRef’s mathematical examples of “undef” all need to be deleted because
while technically correct thay all presume copy-propagation, but you cannot
copy-propagate the “undef” symbol itself because doing so leads to absurdities
and mis-compiles.

Once the definition of “undef” is changed then there are no longer any
examples of optimizatitons that need “poison” instead of “undef”, so
“poison” needs to be deleted, and “freeze” no longer needs to be considered.

Peter Lawrence.

References

[1. llvm-dev, Dan Gohman, Tue Nov 29 15:21:58 PST 2011 ]
[2. llvm-dev, Dan Gohman, Mon Dec 12 12:58:31 PST 2011 ]
[3. http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf ]
[4. llvm-dev, Peter Lawrence, Thu Jun 15 10:27:40 PDT 2017 ]

Peter,

People have been continuing to work on these issues for years. This is not new, and and it is not only now being reopened.

Unfortunately, at this point I think you are repeating well known and well understood information in email after email. I don’t think that is a productive way to discuss this. However, I don’t want to dissuade you from contributing to the project. But I don’t think new emails on this subject will not be a good use of anyone’s time.

Instead, someone needs to go do the very hard work of building, testing, and understanding solutions to some of these problems. In fact, a few others are already doing exactly this.

I understand you disagree with the approach others are taking, and that is perfectly fine, even good! You have explained your concern, and there remains a technical disagreement. This is OK. Repeating your position won’t really help move forward.

Contributing technical perspectives (especially different ones!) is always valuable, and I don’t want to ever discourage it. But when there remains a strong technical disagreement, we have to find some way to make progress.Typically, LLVM lends weight towards those who have the most significant contributions to LLVM in the area and are actually doing the work to realize a path forward. This doesn’t make them any more “right” or their opinions “better”. It is just about having a path forward.

But this should also show you how to make progress. Continuing to debate in email probably won’t help as you’re relatively new to the LLVM project. Instead, write the code, get the data and benchmark results to support your position and approach, and come back to us. I think you will have to do the engineering work of building the solution you want (and others disagree with) and showing why it is objectively better.

Chandler,
where we disagree is in whether the current project is moving the issue
forward. It is not. It is making the compiler more complex for no additional value.

The current project is not based in evidence, I have asked for any SPEC benchmark
that shows performance gain by the compiler taking advantage of “undefined behavior”
and no one can show that.

The current project doesn’t even address some of the bugs described in the paper,
in particular those derived from the incorrect definition of “undef” in the LangRef.

The current project perpetuates the myth that “poison” is somehow required.
It isn’t, and when I show proof of that you reply with “its in bug reports, etc”,
that’s BS and you know it, this hasn’t been explored. The same thing happened
before when I said “nsw” shouldn’t be hoisted, folks replied with “that’s already
been studied and rejected”, but I did the research and found out no, it had not
been fully explored, Dan discarded the idea based on incorrect analysis and people
never questioned it. Dan created “poison” on a whim, and people picked up on it too
without question. We’ve been stuck with this self-inflicted wound ever since, and it is
time to heal it.

The entire situation here can be summarized as incorrect analysis, and failure to
fully root-cause problems, because people didn’t question their assumptions.
And we should not be surprised, it is one of the most common problems in software
engineering. Haven’t you ever gone in to fix a bug only to find that what you are doing
is correcting someone else’s bug fix that didn’t actually fix anything because the person
doing the fix didn’t fully understand the problem? Happens to me all the time.

The correct software engineering decision here is to fix the definition of “undef”,
delete “poison”, and not hoist “nsw” attributes. That is a no-brainer. There is nothing
to try out, or test, ormeasure. That is simply the way it has to be to avoid the current
set of problems.

I cannot emphasize that last point enough, fixing the definition of “undef”, deleting
“poison”, and not allowing “nsw” attributes to be hoisted, fixes all known problems,
even including ones that weren’t thought of before these discussions started, and
I don’t think there is any technical disagreement here, not even from John, Sanjoy,
or Nuno. This is a no-brainer.

John and I do not have a technical disagreement, John is having an emotional
reaction to the fact that he doesn’t have an answer to the function-inlining question.
We can’t disagree until he actually has an opinion to disagree with, but he is not
willing to express one.

The work on “poison” and “freeze” should be in new analysis and transform passes
in which folks can do whatever they want to propagate “undefined behavior” around
in a function (but “undefined behavior" should be an analysis attribute not an IR
instruction). Then folks can try to see if they can actually measure a performance gain
on any SPEC benchmarks. I think we all know this is going to turn out negative, but that’s
besides the point, the point is that “poison” and “freeze” are an experiment and need
to be treated as such and not just simply forced into the trunk because someone likes it.

What you are saying about ’the llvm way" goes against everything we know about
"software engineering”, that things have to be evidence based, have utility, and
be the least complex solution to avoid confusion. And we do engineering reviews
and take review feedback seriously. I suggest you take a step back and think about
that, because it sure seems to me like you’re advocating that we don’t do reviews and
we don’t base decisions on evidence.

Peter Lawrence.

Declaring victory and expecting everyone in a foreign community to
fall into line is probably the the second-least productive approach
that could possibly be taken in this situation. Surpassed only by
actually insulting a regular at the same time.

Tim.

Chandler,
where we disagree is in whether the current project is moving the issue
forward. It is not. It is making the compiler more complex for no additional value.

I mean, I also disagree with your analysis of where we disagree, and what is happening, but I don’t think that matters much or will convince you of anything.

The current project perpetuates the myth that “poison” is somehow required.

No one thinks it is required at a theoretical level. Current transformations made by LLVM require it. We could always disable those transformations. The current project is attempting to see if there is a pragmatic set of transformations we can keep with a better definition.

It isn’t, and when I show proof of that you reply with “its in bug reports, etc”,
that’s BS and you know it, this hasn’t been explored.

I’m sorry that I didn’t have readily available citations in the other thread. If you can show what searches you have done that didn’t find any results, I’m happy to try and help find them. But the way you say this doesn’t come across as assuming good faith on the part of myself and others in these discussions. Within the LLVM community, please always assume good faith and don’t accuse people of “BS”.

Dan created “poison” on a whim, and people picked up on it too

without question. We’ve been stuck with this self-inflicted wound ever since, and it is
time to heal it.

The way you have described this comes across as both hyperbolic and insulting to specific individuals.

This kind of behavior and rhetoric is not acceptable in the LLVM community, and multiple people have asked you to change tone and avoid this behavior. Bluntly, stop.

John and I do not have a technical disagreement, John is having an emotional

reaction to the fact that he doesn’t have an answer to the function-inlining question.

This is yet another personal attack in your email.

After talking to several people involved in these threads, I think that whatever technical points you are trying to make have been completely lost due to the repeated pattern of apparent hostility. Your emails are perceived as insulting and attacking people which is not an appropriate or professional way to engage in a technical discussion here.

The attitude and approach you are taking on the list is completely incompatible with this community and project.

I still encourage you to modify LLVM and implement your approach. It is open source and easy to fork on GitHub. However, please don’t continue sending emails to LLVM lists until you can do so without repeating this behavior.

-Chandler

Tim,
       Can you make a case for why this isn’t the right thing to do ?

I think this is a no-brainer because this is the situation we would be
in if folks hadn’t gone off the deep end with “poison” which hasn’t
actually solved any problems (other than the mis-adventure with
“+nsw” which never actually needed “poison” in the first place).

And AFAICT this is the situation that gcc is in, it gets along just fine
without “poison”.

If you think there is a problem that this approach doesn’t solve then
you need to demonstrate it.

Peter.

Chandler,
I am puzzled by the statement "Current transformations made by LLVM require it.”
Can you clarify with a C source code example ?

Peter Lawrence.

Chandler,
               where we disagree is in whether the current project is
moving the issue
forward. It is not. It is making the compiler more complex for no
additional value.

The current project is not based in evidence, I have asked for any SPEC
benchmark
that shows performance gain by the compiler taking advantage of “undefined
behavior”
and no one can show that.

One easy way to measure this is to enable -fwrapv/-ftrapv on the compiler
command line, which impede the compiler's usual exploitation of signed wrap
UB in C. Last I heard, those options lead to substantial performance
regressions.

It sounds like you are implicitly claiming that there would be no
performance regression. If the -fwrapv/-ftrapv measurements are in line
with this, that will be useful new information for the discussion. But I
think that you need to do the work here (and it isn't that much work
compared to writing out emails; or perhaps I'm just a slow email writer).

I don't think anybody has really up to date numbers on the performance
effect of those options on SPEC. Could you please get some up to date
numbers before continuing this discussion? If the results are as you seem
to imply, then that will be very convincing support for your point.

If you can't be bothered to do that, I have to question how invested you
are in pushing the LLVM project toward a better solution to its current
woes with the poison/undef situation.

-- Sean Silva

Not interested in trying. I look forward to being included in the list
of the emotionally damaged that can't cope with the manifest glory of
your proposals.

Tim.

Chandler,
I am not a “politically correct” person, never have been, never will be.
If you are waiting for me to make a politically incorrect statement so you can jump
on it, let me assure you that you will never be disappointed.

But if that’s all you do then you and llvm lose out. If you want to actually help
llvm move forward then you should judge what I say based on its merit, not on its
delivery.

The thing I will agree with you about is that people on this list are well intentioned.
But I still don’t believe my description of “poison” has ever been discussed before,
you were will intentioned in saying it has, but there is no reason to believe it has,
because every time I dig deeper into these issues I run into mis-conceptions and
mis-information. Faulty analysis based on faulty assumptions. Every time. If I sound
hyperbolic it is because I have gotten frustrated from continually running into this.

And before you claim that I have insulted Dan, you might want to get his
opinion on the subject. My bet is he will react by saying “why didn’t I think
of that”, but in spite of my trying to contact him I have gotten no response.
Perhaps you will have better luck.

Finally, regarding John, when I pushed on the function-inlining example,
rather than responding to it he lashed out at me. That is unprofessional.
I said nothing about it at the time because I try to refrain from meta-discussions.
But it is another reason why I sound so hyperbolic.

Now, getting back to technical, I’m waiting for some C source code examples
showing how "Current transformations made by LLVM require [posion]”

Peter Lawrence.

Chandler,
I am not a “politically correct” person, never have been, never will be.
If you are waiting for me to make a politically incorrect statement so you can jump
on it, let me assure you that you will never be disappointed.

But if that’s all you do then you and llvm lose out. If you want to actually help
llvm move forward then you should judge what I say based on its merit, not on its
delivery.

I don’t care if you call it “politically correct” (I wouldn’t), but you will have to find a way to deliver what you say in a way others don’t perceive as attacking them, insulting them, and being hostile. Those are the baseline requirements to participate in this community and work on this project. As I said before, you are always free to work on other compiler projects or start your own if you find this community not to your liking. Open source is a big place. =]

The thing I will agree with you about is that people on this list are well intentioned.
But I still don’t believe my description of “poison” has ever been discussed before,
you were will intentioned in saying it has, but there is no reason to believe it has,
because every time I dig deeper into these issues I run into mis-conceptions and
mis-information. Faulty analysis based on faulty assumptions. Every time. If I sound
hyperbolic it is because I have gotten frustrated from continually running into this.

I understand you are frustrated, but I have said on several occasions that repeating yourself is not helpful.

Now, getting back to technical, I’m waiting for some C source code examples

showing how "Current transformations made by LLVM require [posion]”

I’m sorry, but given the tone and approach you have taken, I don’t have time, energy, or motivation to continue to invest here. I’m going back to other things. Having read all of these threads, I am thoroughly convinced by the positions put forward by others.

My advice to you in my first email stands. If you want to make progress, more emails will not help. I encourage you to start writing code and demonstrating through specific proposed modifications (likely prototyped on a local branch or GitHub fork) and demonstrate clear evidence of the improved reliability without degraded performance of benchmarks.

I think that is your path forward, and I don’t plan on continuing to engage in what comes off to me as a hostile and repetitive email thread (this one, and the others you have started).

Sean,
Many thanks for taking the time to respond. I didn’t make
myself clear, I will try to be brief…

Chandler,
where we disagree is in whether the current project is moving the issue
forward. It is not. It is making the compiler more complex for no additional value.

The current project is not based in evidence, I have asked for any SPEC benchmark
that shows performance gain by the compiler taking advantage of “undefined behavior”
and no one can show that.

One easy way to measure this is to enable -fwrapv/-ftrapv on the compiler command line, which impede the compiler’s usual exploitation of signed wrap UB in C. Last I heard, those options lead to substantial performance regressions.

In my other emails I point out that Dan achieved the goal of hoisting sign-extension
out of loops for LP64 targets by exploiting “+nsw”, and that this appears to be
the only example of a performance benefit. I am not suggesting we remove this
optimization, and my emails point out that keeping this opt does not require that the
compiler model “undefined behavior”.

Heres what gcc says about those options

`-ftrapv`
This option generates traps for signed overflow on addition, subtraction, multiplication operations.
`-fwrapv`
This option instructs the compiler to assume that signed arithmetic overflow of addition, subtraction and multiplication wraps around using twos-complement representation. This flag enables some optimizations and disables others. This option is enabled by default for the Java front end, as required by the Java language specification.

Sounds like -fwrapv has equivocal results, at least for gcc,
my guess is that the same applies to llvm,

If anyone can show that -fwrapv makes a significant drop in SPEC-INT performance on
a plain old 32-bit machine then we need to look into it because it is kind of hard to believe
and doesn’t sound consistent with gcc.

I would do the tests myself, but all I have is my Mac-mini which is an LP64 machine,
(and no license for SPEC sources)

On an LP64 machine we would need a flag to disable all but Dan’s optimization to
to do a comparison. It would take some time, but it is doable.

Well, I guess that wasn’t brief, sorry!

Peter Lawrence.

<snip />

I'm sorry, but given the tone and approach you have taken, I don't have
time, energy, or motivation to continue to invest here. I'm going back to
other things. Having read all of these threads, I am thoroughly convinced
by the positions put forward by others.

My advice to you in my first email stands. If you want to make progress,
more emails will not help. I encourage you to start writing code and
demonstrating through specific proposed modifications (likely prototyped on
a local branch or GitHub fork) and demonstrate clear evidence of the
improved reliability without degraded performance of benchmarks.

I think that is your path forward, and I don't plan on continuing to
engage in what comes off to me as a hostile and repetitive email thread
(this one, and the others you have started).

Hey!

Can we all just reset our hurt feelings and get back to the issue for a
minute.
/* Chandler being a dick is my job and you can't have it, ok? Snarky
intelligence comments masked in a thin veil of rudeness is no better than
the things I typically do. */

Having read all of these threads, I am thoroughly convinced by the positions put forward by others.

Chandler,
               others have decided to let the compiler continue mis-compiling the
function-inlining example, others have decided to not fix the inability to hoist
a loop invariant divide out of a loop. It sounds like you haven’t even thought
about these things let alone be convinced by anything. Am I missing something
or have you forgotten what we are talking about here ?

Peter Lawrence.

Peter - Is there bug reports on each of the issues you’re referencing. It may be best to ensure that there is and continue the technical discussion on each on their own merit (case by case). This could be a deep rabbit hole, but slowly tackling things point by point is probably the only way to end up with a positive conclusion.

A different way to view this - If your opinion on what’s technically best and what they view isn’t aligned and they will block you overwriting their approach - try to see if an alternative can co-exists and introduce it as a flag. UD is such a religious argument that disagreements are bound to happen.

I think maybe there is some missing context here…

#1 Is there technical merit to what Peter is trying to convey? if yes please reset.

A bunch of people carefully looked at everything Peter said in multiple (fairly long) threads. This is just the latest iteration.

For example, Sanjoy, Nuno, and John discussed many of these issues with Peter in detail here:
http://lists.llvm.org/pipermail/llvm-dev/2017-June/113610.html

The discussion was then forked into several more threads. So I think that there has been a very reasonable set of chances to gather anything we can here. I’ve also checked with at least Sanjoy, John, Hal, and a few others about this when the threads were originally going to see if there was anything substantive materializing.

And if I missed someone or something, I’m sure folks in the community will pipe up to help explain it.

I’m actually very sympathetic. I didn’t want to push back so firmly, but I ended up with numerous people specifically asking that the repeated inappropriate discussion be called out. =/ In the thread I list above, John started trying to help guide the tone of the discussion to a more constructive way.

Anyways, I genuinely think the most positive path forward doesn’t involve more discussion at this point. So far, I remain completely unconvinced of any important technical merit here, and it seems so does everyone else working in this area. We may well all be wrong, but repeating that won’t help IMO.

-Chandler

Please stop with (what I can only interpret as) personal attacks. I haven’t forgotten what we are talking about.

Chandler,
Al right then, stay on topic, what do you actually think
should be done about the fact that the current proposal will mis-compile
the function-inlining example, and won’t be able to hoist a loop-invariat
divide out of a loop.

Peter Lawrence.

Peter,

I strongly suggest that you take a break from this email thread and careful consider the points Chandler has made about community norms and expectations before returning to this discussion.

Chandler has been exceedingly patient with explaining why your behaviour is problematic and made several concrete suggestions as to productive next steps you should take.

You are actively violating the community expectations around interaction on the public mailing lists. Your behaviour on this thread is not acceptable and must stop.

Philip

Hi Peter,

I've tried to specifically address the technical points below.

That the current LangRef IR definition of "undef" is incorrect
is not immediately obvious, it has gone unnoticed for a long
time, and has become lodged in peoples minds as unquestionable.
Instead folks have viewed it as insufficient, and piled on
fixes in the form of "poison" and "freeze".

Here are examples of why the current definition of "undef",
which explicitly assumes that it is correct to copy-propagate
"x = undef" everywhere "x" occurs, is incorrect:

From 3.2 in "Taming Undefined Behavior in LLVM" [3]

*** This shows that the current definition blocks a
highly desirable and otherwise legal optimization. ***

if (k != 0) {
  while (cond) {
    t = 1/k;
    use(t);
  }
}
-----> hoist loop invariant ----->
if (k != 0) {
    t = 1/k;
  while (cond) {
    use(t);
  }
}

This becomes illegal when later "k" is replaced
with "undef" because then "(undef != 0)" and
"t = 1/undef" need not be consistent,and the
program can incorrectly divide-by-zero. So this
is an example of why copy-propagation of "undef"
is undesirable.

This problem is fixed in semantics mentioned in the paper.

From "Function Inlining and undef / poison question" [4]

*** This shows that the current definition creates illegal
translations. ***

this function always executes statement S
foo(a)
{
  if (a == a)
    S;
}
but in llvm when foo is inlined and "a" is replaced
with "undef" then nothing can be said about whether
statement S is executed because "(undef == undef)"
can go either way with the current definition. So this
is an example of why copy-propagation of "undef" is
illegal.

This too is fixed in the semantics mentioned in the paper. This also
isn't new to us, it is covered in section 3.1 "Duplicate SSA Uses".

If you're trying to say that the new behavior (undefined behavior on
branch on poison) is "unintuitive", then that's off base. You can
design a programming language that will never generate IR that
encounters such a scenario (for instance, a Java frontend), so an "end
user" will never have to deal with this.

In the other thread you vaguely said something about compiler IRs
"taking a stance on undefined behavior" on this matter. That too is
off base. If a C/C++ implementation wants to avoid unintuitive
"catch-fire" semantics they can generate IR in a way that the
situation you outline never happens.

These problems cannot be fixed by adding "poison" or "freeze",
it is "undef" itself that is inherently flawed.

undef *is* "flawed", which is why we're removing it. Please refer to the paper.

The LangRef's definition of “undef” needs to be rewritten so that “x =
undef”
simply means that this is where the live range of x starts, and that it is
uninitialized. Another way to think of it is as an incoming argument
register,
which similarly has an unknown (ie "undef") but stable bit pattern.

This world you're proposing with:

- An undef "instruction"
- Undefined behavior on a overflowing nsw/nuw arithmetic (equivalent
to "strip nsw/nuw on hoisting")

is radically different from where LLVM is right now and the burden is
on you to show that this end result is realistic. The biggest hurdle
of the new semantics was implementing it (many thanks to Juyeyoung Lee
who did most of the hard work) to show that it actually works and does
not regress performance. You need to do the same thing for your
proposal to sit at the same table.

-- Sanjoy