[llvm-dev] The nsw story revisited

[Peter Lawrence via llvm-dev]

Chandler,
                Please give some citations, I’ve search the llvm-dev archives and didn't find any.

Peter Lawrence.


> On Jun 28, 2017, at 12:01 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:
> 
> 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 ]
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170628/6d45f8b8/attachment.html>