[llvm-dev] The nsw story revisited
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Wed Jun 28 12:34:24 PDT 2017
On 06/28/2017 02:18 PM, Chandler Carruth wrote:
> On Wed, Jun 28, 2017 at 12:09 PM Peter Lawrence
> <peterl95124 at sbcglobal.net <mailto:peterl95124 at sbcglobal.net>> wrote:
>
> Chandler,
> Please give some citations, I’ve search the
> llvm-dev archives and didn't find any.
>
>
> They are all in the discussions from Nuno, Sanjoy, John and others
> around poison semantics. I won't be able to find the citations any
> easier than you, I simply wanted to point out that rather than
> conclude this is novel, you should probably ask folks who have
> participated in these discussions for reference points that they may have.
Peter, I'll also point out that, in general, information on the subject
of our UB handling is also spread throughout numerous bug reports, patch
reviews, and in addition, has been the subject of many, many hours of
in-person discussions. The fact that there's no one place to get a good
in-depth overview is something that we, as a community, should strive to
improve. This is a very important topic. However, I can assure you that
what you've found by searching llvm-dev is only part of the relevant
history.
-Hal
>
> Peter Lawrence.
>
>
>> On Jun 28, 2017, at 12:01 PM, Chandler Carruth
>> <chandlerc at gmail.com <mailto: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:
>>
>>
>> Preface: This paper shows that "poison" was never actually
>> necessary
>> in the first place. “Poison"s existence is based on incorrect
>> assumptions
>> that are being explored for the first time.
>>
>>
>> Just so you are aware, there have been numerous people in the
>> community who have been exploring the issues you bring up for
>> many years. So I don't think it is correct to say that they are
>> being explored for the first time.
>>
>>
>>
>>
>> I have been re-reading Dan Gohman's original post "the nsw
>> story" [1]
>> and have come to the conclusion that Dan got it wrong in some
>> respects.
>>
>> He came up with "no signed wrap" ("nsw") which in his words means
>> "The purpose of the nsw flag is to indicate instructions
>> which are
>> known to have no overflow". The key operative word here is
>> "known".
>>
>> This means literally an operation with an additional
>> "llvm.assume".
>> For example (a +nsw b) when a and b are i32 is really
>>
>> ((llvm.assume((INT_MIN <= ((i64)a+(i64)b) <= INT_MAX) , (a + b))
>>
>> It is this "assume" that justifies the transformation that
>> Dan does
>> to optimize sign-extension of i32 induction variables out of
>> loops
>> on LP64 targets. So far so good.
>>
>> Note that there is no "undef" in the IR either before or
>> after the
>> transform, this doesn't just fall out because of a clever
>> definition
>> of IR "undef".
>>
>> Note that even the concept of "undefined" never enters into the
>> justification, only that "nsw" ==> "assume" ==> the loop
>> iteration
>> bounds don't wrap ==> i64 arithmetic will generate the exact same
>> iterations as i32 arithmetic ==> the induction variable can be
>> promoted ==> there is no longer any sign-extend inside the loop.
>>
>> Note that clang can generate "+nsw" for signed “+" regardless
>> of whether the precise C standard wording is "undefined behavior"
>> or more simply "unspecified value".
>>
>>
>>
>> Where Dan goes wrong is in thinking that "+nsw" is an operation
>> rather than an operation with an assume, and therefore he feels
>> the need to define what the result of this operation is when it
>> overflows, which then seems to require a new "poison" instruction
>> because "undef" isn't good enough.
>>
>> But there is no need to ask what the result of overflow is
>> because "+nsw" is like a "+" inside of an if-statement whose
>> condition precludes overflow, and if it can't overflow then
>> asking about it is a non sequitor.
>>
>> And speculatively hoisting the "+nsw" doesn't cause problems
>> because hoisting a "+nsw" is like taking a "+" outside of the
>> if-statement that guarantees no overflow, it is then simply
>> a plain old un-attributed "+" operation which has no undefined
>> behavior.
>>
>> Dan's follow on email "nsw is still inconsistent" [2] shows by
>> example why it is illegal to hoist the "nsw" attribute along
>> with the "+" operation.
>>
>> It therefore makes no sense to discuss the result of "+nsw" as
>> ever being either "undef" or "poison", and so the need for
>> "poison"
>> is gone.
>>
>>
>>
>> Here's what Dan thought at the time about this "poison" creation
>>
>> "I wrote up a description of this concept, and it's
>> been in
>> LangRef ever since. It sticks out though, because it
>> got pretty
>> big and complex, especially in view of its relative
>> obscurity.
>> Realistically speaking, it's probably not fully
>> watertight yet."
>>
>> I agree with Dan here "it's probably not fully watertight
>> yet", and
>> apparently other folks agree because yet another instruction,
>> "freeze", is being proposed to fix "poison"s problems. My guess
>> is that "freeze is probably not fully watertight yet" either, but
>> since "poison" isn't needed it is time to delete it from the
>> LangRef,
>> and we can therefore stop considering "freeze".
>>
>>
>> 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 ]
>>
>
--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170628/3e901af0/attachment.html>
More information about the llvm-dev
mailing list