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 ]
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170628/b7f3636b/attachment.html>
On Wed, Jun 28, 2017 at 9:39 AM Peter Lawrence <peterl95124 at sbcglobal.net> wrote:> > > 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. >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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170628/e7f49162/attachment.html>
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.
> On Jun 28, 2017, at 12:16 PM, Chandler Carruth <chandlerc at
gmail.com> wrote:
>
> On Wed, Jun 28, 2017 at 9:39 AM Peter Lawrence <peterl95124 at
sbcglobal.net <mailto:peterl95124 at sbcglobal.net>> wrote:
>
>
> 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.
>
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170628/0588c54a/attachment-0001.html>