A few thoughts from someone on the sidelines; hope they're helpful.<br><br><div class="gmail_quote">On Tue, Nov 29, 2011 at 3:21 PM, Dan Gohman <span dir="ltr"><<a href="mailto:gohman@apple.com">gohman@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">The first solution for this was to define nsw add to return undef on<br>
overflow, instead of invoking immediate undefined behavior. This way,<br>
overflow can happen and it doesn't cause any harm unless the value<br>
is actually used. With the code motion problem fixed, I proceeded to<br>
implement nsw using this approach, and a sign-extension elimination<br>
optimization on top of it.<br>
<br>
However, I later realized that undef isn't actually expressive enough<br>
for this purpose. Undef can produce any value, but it will still be some<br>
specific value of its type (with fluctuation, but that's not important<br>
here). When an integer add is promoted to a wider type, an expression in<br>
the narrower type which would overflow is converted to an expression in<br>
the wider type which returns a value which can't be expressed in the<br>
narrower type. There is no possible value in the narrower type that<br>
undef could take on which would produce the same behavior.<br></blockquote><div><br></div><div>Part of the confusion seems to come from overloading "undefined."</div><div>The VAX architecture spec nicely dealt with the distinction between</div>
<div>unspecified results and unspecified behavior by consistently using</div><div>distinct terms: _unpredictable_ results, and _undefined_ behavior.</div><div>An operation producing an unpredictable result could produce any</div>
<div>bit-pattern that fit in the output operand; but it would not trap</div><div>or do anything else unfriendly.</div><div>An operation causing undefined behavior means anything could happen,</div><div>from no-effect to machine meltdown.</div>
<div><br></div><div>I always thought these were usefully distinct concepts, and the</div><div>terminology convention really clarified that.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I set out to find some way to say that an nsw add which overflows doesn't<br>
invoke immediate undefined behavior, but invokes undefined behavior only<br>
when its result is used. It can't be just any use though, because I didn't<br>
want to rule out the possibility of hoisting chains of instructions,<br>
like a+b+c+d+e. LLVM doesn't usually speculate this aggressively today,<br>
but there are plausible scenarios where it might want to in the future.<br>
<br>
This led me to think about making nsw overflow return some kind<br>
of poisoned value, like undef, only more powerful. The poison would<br>
propagate down the def-use graph until it reaches an instruction that<br>
is capable of triggering the undefined behavior.<br></blockquote><div><br></div><div>Reminds me of how Itanium does speculation, although the details are</div><div>getting fuzzy (it has been a while). Registers have an associated </div>
<div>"NaT" (Not A Thing) flag, which gets set when something bad happens.</div><div>(Usually loading from nonexistent or protected memory. Can't remember</div><div>whether integer overflows can set this.)</div>
<div>Some operations are NaT-tolerant; any input NaT is simply propagated</div><div>to the output. Arithmetic, sign-extension, bit fiddling, and the like</div><div>are NaT-tolerant.</div><div>Some operations are NaT-intolerant; any input NaT causes a trap.</div>
<div>Storing to memory, pointer derefs, and I think compares are all</div><div>NaT-intolerant.</div><div>There's also a "check" instruction that exists solely to check</div><div>for NaT flags. That might be specific to memory traps; when you trap</div>
<div>on a load, you want to know what address trapped, and the check</div><div>instruction has a memory-address operand to provide that info.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
So initially, one might imagine detecting trouble by adding a bit<br>
to every Value to track whether it is a poison value. That's pretty<br>
heavy-weight, but it's doable. It gets worse though, because poison<br>
values can also be transmitted through memory. So one would also<br>
have to add a flag to bytes of memory which are poisoned. But it gets<br>
even worse, because poison values can be used as branch conditions,<br>
so one would have to do advanced CFG analysis to prove whether branch<br>
decisions based on poisoned values actually matter. And it gets worse<br>
yet, because the control structure of the program may be dynamic, so<br>
what one would really need to do is something like non-deterministic<br>
execution. This can easily take exponential amounts of time and memory.<br></blockquote><div><br></div><div>I suggest that storing to memory, and conditionals, and anything</div><div>else that seems to lead toward the really hairy situations, should</div>
<div>be cases where the nsw/poison/trap is "actually observed."</div><div>- Values in memory can be observable by other parts of the program, or</div><div>by other threads/processes.</div><div>- After you've made a control-flow decision, memory references in the </div>
<div>successor blocks are part of the observable behavior of the program.</div><div><br></div><div>This is taking a broader view of "observable" than what's defined in the</div><div>C or C++ standards, which steadfastly ignore a variety of practical realities.</div>
<div>But I think it's a reasonable and defensible position, that still allows you</div><div>some scope for operating on these things in a sensible way.</div><div><br></div><div>Pogo</div><div><br></div></div>