[llvm-dev] RFC: Killing undef and spreading poison

[Sanjoy Das via llvm-dev]

Hi Nuno,

Nuno Lopes wrote:
 >
 > I think the problem is not as bad as it may sound at first sight.
 > There are two important properties: 1) instructions return poison if
 > given poison as input and 2) br poison is UB.  Therefore an analysis
 > is allowed to say "%x | 1" is non-zero. If %x is poison, the result is
 > poison and any transformed expression can be poison or return any
 > non-poison value. If the expression is used later as a condition for
 > branching, it would be UB to branch on poison, so it doesn't matter
 > either.

Yes.

 > So it seems to me that the cases that matter is when we hoist stuff
 > past control-flow (e.g., loop unswitching, LICM, etc).  If we hoist a
 > division out of a loop because some IsNonZero(divisor) analysis said
 > it is fine, then I agree we need utils to ensure the value will indeed
 > be non-zero.

Yup.

 > Currently we don't hoist most divisions out of loops, so we are not
 > making things worse. Going forward we would the utility functions just
 > mentioned.  Not sure what the design of that would look like in
 > general, if we develop separate IsNonZero + EnsureNonZero functions,
 > or one combined function.

Or we could have ComputeKnownBits and other ValueTracking functions
optionally populate a side table with the semantics that the result of
the analysis is valid iff the values inserted in the side table are
not poison.

 > Another idea that popped my mind several times, but I've been trying
 > to avoid is to attach metadata/constraints to freeze instructions.  If
 > we do an optimization that requires the frozen value to be non-zero,
 > leave a constraint there.  The problem (besides the added complexity)
 > is that metadata and assume constraints right now can be discarded at
 > will by optimizers, so correctness guarantees could be voided.

I agree that this will be more complex, but overall this looks pretty
clean (other than the fact that we can't use metadata for restricting
how `freeze` reifies poison because, as you said, it can be dropped).

My initial inclination would be to try to prototype the first solution
(ValueTracking keeps track of values that cannot be poison for its
results to hold) initially.  If it falls over, we can try to be more
clever.

IIUC the overall design intent is to avoid generating too many freezes
anyway?  If so I won't be surprised if we can get away with something
fairly simple.

Thanks!
-- Sanjoy