[LLVMdev] The nsw story

[Paul Robinson]

A few thoughts from someone on the sidelines; hope they're helpful.

On Tue, Nov 29, 2011 at 3:21 PM, Dan Gohman <gohman at apple.com> wrote:

> The first solution for this was to define nsw add to return undef on
> overflow, instead of invoking immediate undefined behavior. This way,
> overflow can happen and it doesn't cause any harm unless the value
> is actually used. With the code motion problem fixed, I proceeded to
> implement nsw using this approach, and a sign-extension elimination
> optimization on top of it.
>
> However, I later realized that undef isn't actually expressive enough
> for this purpose. Undef can produce any value, but it will still be some
> specific value of its type (with fluctuation, but that's not important
> here). When an integer add is promoted to a wider type, an expression in
> the narrower type which would overflow is converted to an expression in
> the wider type which returns a value which can't be expressed in the
> narrower type. There is no possible value in the narrower type that
> undef could take on which would produce the same behavior.
>

Part of the confusion seems to come from overloading "undefined."
The VAX architecture spec nicely dealt with the distinction between
unspecified results and unspecified behavior by consistently using
distinct terms: _unpredictable_ results, and _undefined_ behavior.
An operation producing an unpredictable result could produce any
bit-pattern that fit in the output operand; but it would not trap
or do anything else unfriendly.
An operation causing undefined behavior means anything could happen,
from no-effect to machine meltdown.

I always thought these were usefully distinct concepts, and the
terminology convention really clarified that.

I set out to find some way to say that an nsw add which overflows doesn't
> invoke immediate undefined behavior, but invokes undefined behavior only
> when its result is used. It can't be just any use though, because I didn't
> want to rule out the possibility of hoisting chains of instructions,
> like a+b+c+d+e. LLVM doesn't usually speculate this aggressively today,
> but there are plausible scenarios where it might want to in the future.
>
> This led me to think about making nsw overflow return some kind
> of poisoned value, like undef, only more powerful. The poison would
> propagate down the def-use graph until it reaches an instruction that
> is capable of triggering the undefined behavior.
>

Reminds me of how Itanium does speculation, although the details are
getting fuzzy (it has been a while). Registers have an associated
"NaT" (Not A Thing) flag, which gets set when something bad happens.
(Usually loading from nonexistent or protected memory. Can't remember
whether integer overflows can set this.)
Some operations are NaT-tolerant; any input NaT is simply propagated
to the output. Arithmetic, sign-extension, bit fiddling, and the like
are NaT-tolerant.
Some operations are NaT-intolerant; any input NaT causes a trap.
Storing to memory, pointer derefs, and I think compares are all
NaT-intolerant.
There's also a "check" instruction that exists solely to check
for NaT flags. That might be specific to memory traps; when you trap
on a load, you want to know what address trapped, and the check
instruction has a memory-address operand to provide that info.

So initially, one might imagine detecting trouble by adding a bit
> to every Value to track whether it is a poison value. That's pretty
> heavy-weight, but it's doable. It gets worse though, because poison
> values can also be transmitted through memory. So one would also
> have to add a flag to bytes of memory which are poisoned. But it gets
> even worse, because poison values can be used as branch conditions,
> so one would have to do advanced CFG analysis to prove whether branch
> decisions based on poisoned values actually matter. And it gets worse
> yet, because the control structure of the program may be dynamic, so
> what one would really need to do is something like non-deterministic
> execution. This can easily take exponential amounts of time and memory.
>

I suggest that storing to memory, and conditionals, and anything
else that seems to lead toward the really hairy situations, should
be cases where the nsw/poison/trap is "actually observed."
- Values in memory can be observable by other parts of the program, or
by other threads/processes.
- After you've made a control-flow decision, memory references in the
successor blocks are part of the observable behavior of the program.

This is taking a broader view of "observable" than what's defined in the
C or C++ standards, which steadfastly ignore a variety of practical
realities.
But I think it's a reasonable and defensible position, that still allows you
some scope for operating on these things in a sensible way.

Pogo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111130/41808a9f/attachment.html>