[LLVMdev] The nsw story

[Dan Gohman]

On Nov 30, 2011, at 12:21 PM, Paul Robinson wrote:

> 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.

LLVM IR does make these distinctions, though the language is a bit
subtle.

"Undefined behavior" and "behavior is undefined" mean anything could
happen. Demons may fly out your nose.

"undef" is an arbitrary fluctuating bit pattern. Also it causes
operations that use it to exhibit constrained fluctuation.

"Result is undefined" means an arbitrary bit pattern may be returned.
Sometimes this means "undef" and sometimes this means a fixed bit
pattern, though this inconsistency may be unintentional.

> 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.

Prohibiting poison values from propogating through memory would mean
that the reg2mem pass would no longer be a semantics-preserving pass.
Prohibiting it from propogating through control flow would mean that a
select instruction wouldn't be equivalent to a conditional branch and
a phi. These are problems that aren't really important for hardware
ISAs, but are important for LLVM IR.

Dan