[llvm-dev] The nsw story revisited

Wed Jun 28 12:42:46 PDT 2017

Hal,
Chandler,
               Can we get back on topic, IE if you’ve actually read the paper I’d like to 
hear some feedback on its technical content

Peter Lawrence.

> On Jun 28, 2017, at 12:34 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> 
> 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/80535a98/attachment-0001.html>