[LLVMdev] RFC: Proposal to Remove Poison

[Sanjoy Das]

> I agree with Hal that the right way to assign semantics to undef is
> that say that it is some N bit value at each *use*; and the N bit
> value undef pretends to be at each use may be a different one.  I

I take back what I said -- deciding what value undef will correspond
to at each use is fairly counter-intuitive.  For instance, this means
inlining is not meaning-preserving:

declare i32 @use(i32, i32)

define i32 @f(i32 %x) alwaysinline {
 entry:
  %r = call i32 @use(i32 %x, i32 %x)
  ret i32 %r
}

define i32 @g() {
 entry:
  %r = call i32 @f(i32 undef)
  ret i32 %r
}

on `opt -always-inline` is transformed to

declare i32 @use(i32, i32)

; Function Attrs: alwaysinline
define i32 @f(i32 %x) #0 {
entry:
  %r = call i32 @use(i32 %x, i32 %x)
  ret i32 %r
}

define i32 @g() {
entry:
  %r.i = call i32 @use(i32 undef, i32 undef)
  ret i32 %r.i
}

attributes #0 = { alwaysinline }


If we say "undef chooses any value at each use", the first program
always calls @use with both parameters equal (so if @use was printing
the xor of its two parameters, it would always print 0) while the
second program calls @use with two arbitrary values.

Another example related to, but slightly different from David's
motivating example:

define i32 @s(i32* %p) {
 entry:
  store i32 undef, i32* %p
  %r = load i32* %p
  %m = call i32 @use(i32 %r, i32 %r)
  ret i32 %r
}

opt -O3 transforms this to

define i32 @s(i32* nocapture readnone %p) {
entry:
  %m = tail call i32 @use(i32 undef, i32 undef)
  ret i32 undef
}

This example has the same problem as the first one -- the value of i32
undef was supposed to have been "decided" at its only use, the store;
but instead LLVM has increased the program's degree of freedom (I'm
using the term informally).

As far as I can tell, there are two ways to fix this:

 1. teach all of LLVM to treat undef specially.  This may be difficult
because unlike every other SSA value, undef's value is decided at
uses, not defs.  For instance, a "fixed" version of the inliner pass
could coerce the "i32 undef" to, say, "i32 0" before inlining the body
of the callee.

 2. represent undef as an instruction, not as a value.  Then the first
example becomes

define i32 @f(i32 %x) alwaysinline {
 entry:
  %r = call i32 @use(i32 %x, i32 %x)
  ret i32 %r
}

define i32 @g() {
 entry:
  %u = undef
  %r = call i32 @f(i32 %u)
  ret i32 %r
}

which opt transforms to

define i32 @g() {
entry:
  %u = undef
  %r.i = call i32 @use(i32 %u, i32 %u)
  ret i32 %r.i
}

I do not want to derail this thread by taking off on a tangent, but if
there is interest in (2) [or (1), but I think (1) is too hard to do
correctly] I can write up a proposal and start a separate thread on
llvmdev.

-- Sanjoy