<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Chandler,<div class=""> .</div><div class="">I mis-phrased the “nsw” as “llvm.assume”, I really mean it should be thought of</div><div class="">as a combination, not that we should actually represent it that way in the IR,</div><div class="">I think putting it in as an explicit assume would be terribly cumbersome,</div><div class="">just look at it, it is awful to try to read !, and if I thought it should be literally inserted</div><div class="">I would not have use the non-C notation (INT_MIN <= X <= INT_MAX) !!!</div><div class="">The current implementation as an attribute is best, note that later on I say it is</div><div class="">illegal to hoist the “attribute”, not the “assume”. As far as leaving the nsw/assume</div><div class="">where the operation was hoisted from, that’s a choice. As has been noted before</div><div class="">you can delete all the attributes from a program and it still compiles correctly,</div><div class="">The nsw/assume is just extra information that isn’t necessary for correct compilation.</div><div class=""><br class=""></div><div class="">This should be done now because there is absolutely no disagreement now</div><div class="">that this is the correct way to proceed.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">As far as “modeling uninitialized memory”, why do you think that is important,</div><div class="">I don’t see this as ever having a benefit to optimization. If folks really think this</div><div class="">is important then my suggestion is that they create new analysis and transform</div><div class="">passes in which they can do what ever they want with respect to uninitialized</div><div class="">memory and other “undefined behaviors”, and “poison” should be implemented</div><div class="">as an analysis attribute, not as an IR instruction. If and when this effort ever</div><div class="">shows any performance benefit we can discuss what to do about it, but my</div><div class="">bet is that this won’t ever be the case. This might be an interesting academic</div><div class="">research project, but that isn’t any reason to put “poison" into the LangRef.</div><div class=""><br class=""></div><div class="">My point is that “poison” serves no purpose, and must be deleted. As for</div><div class="">“undef” it is not there to take “poison”s place, it is there to satisfy requirements</div><div class="">of SSA representation of scalar values, and it is illegal to copy-propagate it.</div><div class="">Thats all. It is not there to represent uninitialized memory, since that isn’t an SSA</div><div class="">problem, in fact I don’t believe it is a problem at all. Uninitialized memory is</div><div class="">an interesting problem for static analyzers, but that isn’t the purpose of LLVM</div><div class="">as I understand it, and if it ever does become so then use the technique above,</div><div class="">use a “poison” attribute, not a “poison” instruction.</div><div class=""><br class=""></div><div class="">Think about it this way, if you were writing such a static analyses would you</div><div class="">replace a reference to uninitialized memory with a “poison” instruction,</div><div class="">no, because doing so would lose information that you want to relay back</div><div class="">to the user. Same thing in LLVM. A “poison” instruction is useless.</div><div class=""><br class=""></div><div class="">Thanks,</div><div class="">Peter Lawrence.</div><div class=""><br class=""></div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jun 28, 2017, at 6:07 PM, Chandler Carruth <<a href="mailto:chandlerc@gmail.com" class="">chandlerc@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_quote"><div dir="ltr" class="">On Wed, Jun 28, 2017 at 12:42 PM Peter Lawrence <<a href="mailto:peterl95124@sbcglobal.net" class="">peterl95124@sbcglobal.net</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">Hal,<div class="">Chandler,</div><div class=""> Can we get back on topic, IE if you’ve actually read the paper I’d like to </div><div class="">hear some feedback on its technical content</div></div></blockquote><div class=""><br class=""></div><div class="">Sure, I was mostly mentioning prior discussion because I don't think this is going to add a lot to the discussion around `nsw` and the `llvm.assume` intrinsic back when Hal and I started discussing modeling assumptions as first class entities in the IR.</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><div class=""><blockquote type="cite" class=""><div class=""><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)" class=""><div dir="ltr" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><div class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div dir="auto" style="word-wrap:break-word" class=""><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><div style="margin:0px;line-height:normal;min-height:16px" class=""><br class=""></div></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">I have been re-reading Dan Gohman's original post "the nsw story" [1]</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">and have come to the conclusion that Dan got it wrong in some respects.</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">He came up with "no signed wrap" ("nsw") which in his words means</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">"The purpose of the nsw flag is to indicate instructions which are</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">known to have no overflow". The key operative word here is "known".</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">This means literally an operation with an additional "llvm.assume".</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">For example (a +nsw b) when a and b are i32 is really</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""> <span class="m_-2105736059564455628Apple-converted-space"> </span>((llvm.assume((INT_MIN <= ((i64)a+(i64)b) <= INT_MAX) , (a + b))</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">It is this "assume" that justifies the transformation that Dan does</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">to optimize sign-extension of i32 induction variables out of loops</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">on LP64 targets. So far so good.</span></div></div></div></blockquote></div></div></div></blockquote></div></div></div></blockquote></div></div></blockquote></div></blockquote></div></div></div></blockquote><div class=""><br class=""></div><div class="">I just want to point out that this isn't complete.</div><div class=""><br class=""></div><div class="">*Before* an `add nsw` instruction is hoisted, it could be thought of as a normal `add` plus `llvm.assume`. But the `llvm.assume` cannot be hoisted above predicates. So what this would end up doing is allowing the hoisting of the `add` by separating the invariant and keeping the invariant below the predicate. This is a fairly minor point, but I didn't want it to be unstated.</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><blockquote type="cite" class=""><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)" class=""><div dir="ltr" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div dir="auto" style="word-wrap:break-word" class=""><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class=""></span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">Where Dan goes wrong is in thinking that "+nsw" is an operation</span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">rather than an operation with an assume, and therefore he feels</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">the need to define what the result of this operation is when it</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">overflows, which then seems to require a new "poison" instruction</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">because "undef" isn't good enough.</span></div></div></div></blockquote></div></div></blockquote></div></div></blockquote></div></div></blockquote></blockquote></div></div></blockquote><div class=""><br class=""></div><div class="">A meta comment. I think it would be helpful for you to phrase your discussion in a less personalized way. Rather than talking about "So-and-so went wrong when they thought ...", I would instead merely discuss the situation as it is today. This helps keep the discussion from sliding into inappropriate areas, which has already been a concern, so it seems worth pointing out as a suggestion for future emails.</div><div class=""><br class=""></div><div class="">To the actual point, it seems backwards to say that we made a mistake in specifying `nsw` as an operation rather than an `assume`. At the time we specified `nsw` there was no such construct as `llvm.assume`. Perhaps introducing `llvm.assume` would have been better than introducing `nsw`, perhaps not. But it doesn't actually matter. This kind of historical critique doesn't seem like a useful way to frame the discussion.</div><div class=""><br class=""></div><div class="">The point is, we have `llvm.assume` now, and we can and should consider whether it is a better tool for the job. Hopefully I have understood the point you are trying to make?</div><div class=""><br class=""></div><div class="">My response is that I don't think this is clearly a superior tool for the job. We did actually discuss things like `nsw` when designing `llvm.assume`. One serious issue with `llvm.assume` is that it *cannot be speculated*. Even though we gain the ability to speculate the `add` by decoupling the invariant, we would retain a large amount of IR that could not be speculated and would cause us to retain control flow and be a significant barrier to optimization.</div><div class=""><br class=""></div><div class="">In fact, `llvm.assume` is *incredibly* expensive already. We talked at length when introducing it about how it should be relatively sparingly used and used with care to provide the most impactful hints to the optimizer rather than trying to encode everything that might possibly be assumed to be true.</div><div class=""><br class=""></div><div class="">On the flip side, `add nsw` is extremely common in the IR produced by many frontends. So it would seem like a poor fit to use a very expensive and heavyweight tool to represent something that is very common.</div><div class=""><br class=""></div><div class="">I'm happy to view `add nsw` as an `add` with an implicit `llvm.assume` inside of control flow where the result is "used" (for a complex definition of "used" that should be discussed on the `undef` thread and not here) if that is a useful notional or theoretical model. But the *representation optimization* of `add nsw` still seems quite useful.</div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><blockquote type="cite" class=""><blockquote type="cite" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255)" class=""><div dir="ltr" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""><blockquote type="cite" class=""><div dir="ltr" class=""><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div dir="auto" style="word-wrap:break-word" class=""><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255);min-height:16px" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">It therefore makes no sense to discuss the result of "+nsw" as</span><br class=""></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">ever being either "undef" or "poison", and so the need for "poison"</span></div><div style="margin:0px;font-size:14px;line-height:normal;font-family:Menlo;background-color:rgb(255,255,255)" class=""><span style="font-variant-ligatures:no-common-ligatures" class="">is gone.</span></div></div></div></blockquote></div></div></blockquote></div></div></blockquote></div></div></blockquote></blockquote></div></div></blockquote><div class="">Note that there have been examples which show that the `undef` semantics alone as used to model reading from uninitialized memory are effectively equivalent to `poison`. So I don't believe that removing `nsw` would necessarily be sufficient here. I think it would also require other changes. And in your emails about `undef` you seem to agree that we would have to change `undef` itself.</div><div class=""><br class=""></div><div class="">I think it would be more productive to focus on that thread. If we decide to get rid of poison entirely (including changing `undef`), *then* we can have a discussion about how to model `nsw`.</div></div></div>
</div></blockquote></div><br class=""></div></body></html>