Predicates should handle poison

[davemenendez]

Alive newsema accepts this optimization:

Pre: isPowerOf2(%a)
  %a = shl i4 1, %x
  %b = select 1, %x, %a
  %c = icmp ult %b, 4
=>
  %c = true

See also http://rise4fun.com/Alive/U4o

LLVM's isKnownToBeAPowerOfTwo analysis is always true for %a, no matter what is known about %x. In other words, the precondition should not constrain %x at all. This is allowed by LLVM because the analysis is not required to be accurate when its input is poison, which it will be in any case where the optimization is not a refinement.

[nunoplopes]

Thanks Dave! I agree this is a bug; this predicate should ensure power-of-2 OR poison. Right now it's missing the "OR poison" part.
This is a long discussion to have re. what are the semantics of LLVM's analyses. Most LLVM analyses have similar semantics to this power-of-2, but not all. (and it keeps changing)

[davemenendez]

Fortunately, it seems pretty hard to trigger this bug. You need a situation where (1) the optimization is invalid when a particular source value is poison, and (2) the precondition involves an analysis of that value. My example essentially uses isPowerOf2 to indirectly bound the size of %x, but then doesn't actually use the value that's been analyzed.

It would be interesting to know whether a less-contrived example is possible.