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. 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/87cf349e/attachment.html>
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/bba889ad/attachment.html>
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>