[LangRef] Clarify poison semantics

[nikic]

Summary

I find the current documentation of poison rather confusing, mainly because its use of "undefined behavior" doesn't seem to align with our usual interpretation (of immediate UB). Especially the sentence "any instruction that has a dependence on a poison value has undefined behavior" is very confusing.

Clarify poison semantics by:

• Replacing the introductory paragraph with the standard rationale for having poison value.
• Spelling out that an instruction depending on poison returns poison.
• Spelling out how we go from a poison value to immediate undefined behavior and give the two examples we currently use in ValueTracking.
• Spelling out that side effects depending on poison are UB.

(Context: Discussion in D62939 on when exactly poison turns into UB.)

[nlopes]

Sounds great! Just 1 comment inline.

llvm/docs/LangRef.rst

3275 ↗

(On Diff #203676)

This implies that doing a volatile store of a poison to memory is UB. Is this intended? I don't know of a use case that requires such behavior.

[nikic]

llvm/docs/LangRef.rst

3275 ↗

(On Diff #203676)

One of the examples below explicitly lists volatile store of poison value as UB, which is why I mentioned it here:

store volatile i32 %poison, i32* @g  ; External observation; undefined behavior.

The only code I'm aware of that does does reasoning in terms of side-effects with (control) dependence on poison is https://github.com/llvm-mirror/llvm/blob/1cbbb3f527a5aa13eda990e3dfa31f2ca4f64e07/lib/Analysis/ScalarEvolution.cpp#L6010-L6030, which does not care about the classification of any particular operation.

Personally I don't think it makes sense to classify a volatile store of poison as UB for two reasons: First, a volatile operation can have side-effects, but does not need to. If it does have side-effects then it is UB, but for the purposes of generic IR reasoning, we have to assume here that it might just be a store to normal memory that happens to be marked volatile. Second, making an operation volatile generally allows strictly less transformations to be performed. This would be a case where marking something volatile would allow more aggressive optimizations using poison-based reasoning, which does not seem right.

I'd be happy to drop the provision about volatile operations here, as well as the example below.

[jdoerfert]

llvm/docs/LangRef.rst

3270 ↗

(On Diff #203676)

Why do you make null special here? Generally, there are a lot of non-dereferenceable addresses and null is just a special one. I'd argue, loading poison, etc., is bad even if null is a valid address.

[nlopes]

llvm/docs/LangRef.rst

3270 ↗

(On Diff #203676)

I agree. Dereferencing poison should always be UB, since that pointer is not based on a valid object.

3275 ↗

(On Diff #203676)

Thank you, sounds good. I don't see why external observability actually matters for poison.
I agree with removing this part.

[nikic]

Remove provision that a volatile store of a poison value is UB.

[nikic]

Dereferencing poison is always UB, independent of whether dereferencing null is UB.

[nikic]

llvm/docs/LangRef.rst

3270 ↗

(On Diff #203676)

I mentioned null here because I thought it is the only way in which UB for dereferencing follows directly from existing semantics (poison -> undef -> null -> UB).

Apparently that's not right. Looking around the code, https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Utils/Local.cpp#L2102-L2109 does indeed assume that storing to undef is always UB, independent of whether null is dereferencable.

I assume that this is a consequence of https://llvm.org/docs/LangRef.html#pointer-aliasing-rules. I've added an explicit bullet for it there, as it wasn't obvious to me that this is the case.

[nikic]

Update example: Store to poison was not marked as UB.

[jdoerfert]

llvm/docs/LangRef.rst

2160 ↗

(On Diff #203752)

IMHO this is great, regardless of the poison discussion. Thanks for adding it.

3276 ↗

(On Diff #203752)

Now, side effects, what do we count and why do we have it explicitly.

Also, should we explicitly mention control flow or is it sufficiently covered by the "*depends*" definition above?

[aqjune]

llvm/docs/LangRef.rst

3274 ↗

(On Diff #203752)

How about mentioning right-shift operations on poison (e.g. ashr x, poison) as well?
Its semantics is equivalent to x / 2^y when x and y are non-poison(and non-undef), but LLVM seems to hoist ashr x, poison during optimization, implying that it cannot be UB : https://godbolt.org/z/2LG0xX .

3276 ↗

(On Diff #203752)

I also think that control flow on poison is an important issue.

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/LoopUnswitch.cpp#L585 also mentions that there's discrepancy between semantics of branch on undef/poison.
My suggestion is to mention the discrepancy explicitly here so people can acknowledge the issue while reading LangRef.

[nikic]

Explicitly mention control dependent side-effects.

[nikic]

llvm/docs/LangRef.rst

3274 ↗

(On Diff #203752)

ashr does not have any special semantics in this context: It propagates poison, i.e. ashr x, poison is poison again. (Oversize shifts are defined as poison, not as UB.)

3276 ↗

(On Diff #203752)

Now, side effects, what do we count and why do we have it explicitly.

I don't think there is anything in the LLVM IR where we can say that it definitely has a side-effect, just operations that might have one (volatile, calls, etc). We need this to be UB to allow reasoning like https://github.com/llvm-mirror/llvm/blob/1cbbb3f527a5aa13eda990e3dfa31f2ca4f64e07/lib/Analysis/ScalarEvolution.cpp#L6010-L6030, but don't really care about what exactly a side-effect is -- just that if one exists, a dependence on poison is UB.

Also, should we explicitly mention control flow or is it sufficiently covered by the "*depends*" definition above?

Control flow is covered by the dependence definition, but as this is an important case, I've added an explicit note now.

[nlopes]

LGTM, thank you!

[reames]

Also LGTM. Nice cleanup.

I will separately raise a conversation of whether storing poison should be immediate UB, but I'm explicitly OK w/it being removed in this patch given nothing actually appears to implement that semantic at the moment.

[jdoerfert]

LGTM as well. Thanks!

llvm/trunk/docs/LangRef.rst

 -  A pointer value is associated with the addresses associated with any
    value it is *based* on.
 -  An address of a global variable is associated with the address range
    of the variable's storage.
 -  The result value of an allocation instruction is associated with the
    address range of the allocated storage.
 -  A null pointer in the default address-space is associated with no
    address.
+-  An :ref:`undef value <undefvalues>` in *any* address-space is
+   associated with no address.
 -  An integer constant other than zero or a pointer value returned from
    a function not defined within LLVM may be associated with address
    ranges allocated through mechanisms other than those provided by
    LLVM. Such ranges shall not overlap with any ranges of addresses
    allocated by mechanisms provided by LLVM.
 
 A pointer value is *based* on another pointer value according to the
 following rules:

 location could clobber arbitrary memory, therefore, it has undefined
 behavior.
 
 .. _poisonvalues:
 
 Poison Values
 -------------
 
-Poison values are similar to :ref:`undef values <undefvalues>`, however
-they also represent the fact that an instruction or constant expression
-that cannot evoke side effects has nevertheless detected a condition
-that results in undefined behavior.
+In order to facilitate speculative execution, many instructions do not
+invoke immediate undefined behavior when provided with illegal operands,
+and return a poison value instead.
 
 There is currently no way of representing a poison value in the IR; they
 only exist when produced by operations such as :ref:`add <i_add>` with
 the ``nsw`` flag.
 
 Poison value behavior is defined in terms of value *dependence*:
 
 -  Values other than :ref:`phi <i_phi>` nodes depend on their operands.
-  An instruction *control-depends* on a :ref:`terminator
    control transfers to one of the successors, and may not be executed
    when control is transferred to another.
 -  Additionally, an instruction also *control-depends* on a terminator
    instruction if the set of instructions it otherwise depends on would
    be different if the terminator had transferred control to a different
    successor.
 -  Dependence is transitive.
 
-Poison values have the same behavior as :ref:`undef values <undefvalues>`,
-with the additional effect that any instruction that has a *dependence*
-on a poison value has undefined behavior.
+An instruction that *depends* on a poison value, produces a poison value
+itself. A poison value may be relaxed into an
+:ref:`undef value <undefvalues>`, which takes an arbitrary bit-pattern.
+
+This means that immediate undefined behavior occurs if a poison value is
+used as an instruction operand that has any values that trigger undefined
+behavior. Notably this includes (but is not limited to):
+
+-  The pointer operand of a :ref:`load <i_load>`, :ref:`store <i_store>` or
+   any other pointer dereferencing instruction (independent of address
+   space).
+-  The divisor operand of a ``udiv``, ``sdiv``, ``urem`` or ``srem``
+   instruction.
+
+Additionally, undefined behavior occurs if a side effect *depends* on poison.
+This includes side effects that are control dependent on a poisoned branch.
 
 Here are some examples:
 
 .. code-block:: llvm
 
     entry:
       %poison = sub nuw i32 0, 1           ; Results in a poison value.
       %still_poison = and i32 %poison, 0   ; 0, but also poison.
       %poison_yet_again = getelementptr i32, i32* @h, i32 %still_poison
-      store i32 0, i32* %poison_yet_again  ; memory at @h[0] is poisoned
+      store i32 0, i32* %poison_yet_again  ; Undefined behavior due to
+                                           ; store to poison.
 
       store i32 %poison, i32* @g           ; Poison value stored to memory.
       %poison2 = load i32, i32* @g         ; Poison value loaded back from memory.
 
-      store volatile i32 %poison, i32* @g  ; External observation; undefined behavior.
-
       %narrowaddr = bitcast i32* @g to i16*
       %wideaddr = bitcast i32* @g to i64*
       %poison3 = load i16, i16* %narrowaddr ; Returns a poison value.
       %poison4 = load i64, i64* %wideaddr  ; Returns a poison value.
 
       %cmp = icmp slt i32 %poison, 0       ; Returns a poison value.
       br i1 %cmp, label %true, label %end  ; Branch to either destination.
 

llvm/trunk/lib/Analysis/ValueTracking.cpp

bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I,
   for (const Instruction &LI : *L->getHeader()) {
     if (&LI == I) return true;
     if (!isGuaranteedToTransferExecutionToSuccessor(&LI)) return false;
   }
   llvm_unreachable("Instruction not contained in its own parent basic block.");
 }
 
 bool llvm::propagatesFullPoison(const Instruction *I) {
+  // TODO: This should include all instructions apart from phis, selects and
+  // call-like instructions.
   switch (I->getOpcode()) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Xor:
   case Instruction::Trunc:
   case Instruction::BitCast:
   case Instruction::AddrSpaceCast:
   case Instruction::Mul: