<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Sun, Feb 8, 2015 at 1:57 PM, Owen Anderson <span dir="ltr"><<a href="mailto:resistor@mac.com" target="_blank">resistor@mac.com</a>></span> wrote:<br><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">Hi David,<br>
<br>
I have serious doubts about this approach. This is essentially how undef was originally implemented in LLVM, back in the mists of time. It led to a lot of bugs that Dan (and others) fixed in the 2008-2010 timeframe, culminating in the modern definition of undef, and poison as a complementary concept. Unfortunately, I don’t have pointers to those bugs, but I imagine some codebase archeology could turn them up.<br></blockquote><div><br></div><div>Having different notions of undef and poison are problematic as well.</div><div><br></div><div><div>This proposal is motivated from the observation that, in practice, we transform:</div><div><div>define i1 @f(i32 %x, i32 %y, i1 %C) {</div><div> %add = add nsw i32 %x, %y</div><div> %sel = select i1 %C, i32 %add, i32 undef</div><div> %cmp = icmp sgt i32 %sel, %x</div><div> ret i1 %cmp</div><div>}</div></div><div><br></div><div>into:</div><div><div>define i1 @f(i32 %x, i32 %y, i1 %C) {</div><div> %cmp = icmp sgt i32 %y, 0<br></div><div> ret i1 %cmp</div><div>}</div></div></div><div><br></div><div>If undef isn't as strong as poison, this transformation is not valid.</div><div><br></div><div>Why is this the case? Consider that when %C is false, %sel will be undef.</div><div>This leaves us with:</div><div> %cmp = icmp sgt i32 undef, %x</div><div><br></div><div>%x might be INT_MAX which means that %cmp must be optimized to false.</div><div><br></div><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">
<span class=""><font color="#888888"><br>
—Owen<br>
</font></span><span class="im"><br>
> On Feb 8, 2015, at 2:23 AM, David Majnemer <<a href="mailto:david.majnemer@gmail.com">david.majnemer@gmail.com</a>> wrote:<br>
><br>
</span><div class=""><div class="h5">> Hello,<br>
><br>
> I'd like to offer an alternative solution to the "poison problem": remove it.<br>
><br>
> What follows is rather informal. I'd happily write up a nicer document if this RFC stands up to scrutiny.<br>
><br>
> The idea was born from two observations:<br>
> - undef was introduced to model a load of uninitialized memory, a form of undefined behavior.<br>
> - poison was introduced to model integer overflow, another form of undefined behavior.<br>
><br>
> I find it awkward that one form of uninitialized behavior is more or less powerful than another.<br>
><br>
> We rely on the following properties for undef:<br>
> - undef is permitted to be an arbitrary bit-pattern.<br>
> - Instructions may or may not be value dependent on their undef operands.<br>
><br>
> We rely on the following properties for poison:<br>
> - Instructions which have poison operands are capable of providing results which are not consistent with a two's complement operand.<br>
><br>
> Here is a case where we believed distinguishing between poison and undef is essential:<br>
> %add = add nsw i32 %a, %b<br>
> %cmp = icmp sgt i32 %add, %a<br>
><br>
> If %a is INT_MAX and %b is 1, then %add results in overflow.<br>
> If overflow results in undef, then %cmp would be equivalent to:<br>
> %cmp = icmp sgt i32 undef, INT_MIN<br>
><br>
> There is no bit-pattern we could substitute for undef which would make %cmp true, this means that we cannot optimize %cmp to 'icmp sgt i32 %b, 0'.<br>
><br>
> Poison was created to allow us to produce whatever value we'd like for %cmp if %add resulted in overflow.<br>
><br>
> What I would like to do is to remove poison and replace it with undef while still optimizing comparison instructions. The quick-and-dirty way of stating this is: an icmp with an undef operand produces undef regardless of its other operand.<br>
><br>
> I believe this would allow us to exploit and optimize overflow in arithmetic flowing into comparison operations.<br>
><br>
> Could this be problematic?<br>
><br>
> Whether we intended to or not, LLVM's implementation of undef's semantics already allows us to say that a memory location is not equivalent to any possible bit-pattern.<br>
><br>
> Consider the following program:<br>
> define i1 @f() {<br>
> %mem = alloca i1<br>
> %load = load i1* %mem<br>
> %cmp = icmp eq i1 %load, false<br>
> ret i1 %cmp<br>
> }<br>
><br>
> Because it is possible for %load's undef to be either true or false, %cmp must be equivalent to undef as well. This is completely consistent with the above rules.<br>
><br>
> The following program is a little more interesting:<br>
> define i1 @g() {<br>
> %mem = alloca i1<br>
> %load = load i1* %mem<br>
> %cmp0 = icmp eq i1 %load, 0<br>
> %cmp1 = icmp eq i1 %load, 1<br>
> %and = xor i1 %cmp0, %cmp1<br>
> ret i1 %and<br>
> }<br>
><br>
> The intent of this program is to compare a memory location against all possible values the location might have.<br>
><br>
> If we ran LLVM's InstCombine pass then %and would have been replaced with the "expected" result of true.<br>
><br>
> If we instead ran SROA over @g, we would be left with:<br>
> %cmp0 = icmp eq i1 undef, false<br>
> %cmp1 = icmp eq i1 undef, true<br>
> %and = xor i1 %cmp0, %cmp1<br>
><br>
> Now that %cmp0 and %cmp1 have different undef values, %and is now undef.<br>
> This result is sufficient to say that the contents of %mem are neither true nor false!<br>
</div></div><div class=""><div class="h5">> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
</div></div></blockquote></div><br></div></div>