[LLVMdev] poison and select

[John Regehr]

In the section about poison values, the LLVM language reference manual says:

   "Values other than phi nodes depend on their operands."

This implies that a select instruction's output can be poisoned by its 
not-selected argument value. If select were poisoned only by its 
selected argument, we would expect this fact to be mentioned 
specifically, as it is for phi.

Next I'll show how poisoning by the not-selected value can introduce a 
problem. Take this C program:

int printf(const char *, ...);
int foo(int x0) {
   int x3 = x0 >> 27;
   int x4 = x3 - 27;
   int x2 = x4 ? x4 : (1 >> x4);
   int x1 = x2 != 0;
   return x1;
}
int arg;
int main (void) {
   int x1 = foo(arg);
   printf("%x\n", x1);
   return 0;
}

This program has no UB and it should print "1'.

Clang at -O2 turns foo() into this:

define i32 @foo(i32 %x0) #0 {
entry:
   %shr = ashr i32 %x0, 27
   %sub = add nsw i32 %shr, -27
   %tobool = icmp ne i32 %sub, 0
   %shr1 = lshr i32 1, %sub
   %cond = select i1 %tobool, i32 %sub, i32 %shr1
   %cmp = icmp ne i32 %cond, 0
   %conv = zext i1 %cmp to i32
   ret i32 %conv
}

Although the translation is very straightforward, there's a problem: 
%shr1 is a poison value and although it is not selected, it propagates 
through the rest of the function and poisons the return value.

Obviously things are not going well if the source program contains no UB 
and the emitted code returns a poison value. Either there has been a 
miscompilation or else the LLVM documentation should be changed to make 
it clear that the select instruction only has a value dependence on the 
value that is selected.

The immediate problem here is that both Souper and Alive are happy for 
foo() to return 0 instead of 1. Souper actually does this optimization 
-- legally, of course, according to the reference manual.

Anyway this issue seemed tricky enough to bring up here instead of just 
filing a PR.

Thanks,

John