[llvm-dev] The nsw story revisited

[Chandler Carruth via llvm-dev]

On Wed, Jun 28, 2017 at 12:09 PM Peter Lawrence <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 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>
> 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/130dfe10/attachment-0001.html>