llvm dev - Oct 2016 - RFC: Killing undef and spreading poison

Hi Dan,

Thanks a lot for the feedback and apologies for the delay!
>> br poison -> UB
> What impact does this have on API contracts? Some library functions might
currently tolerate being passed an uninitialized value (at the LLVM level;
C's semantics are different). However, with the new poison, if the
implementation of a function happens to do a branch on the input, the code has
UB if passed an uninitialized value.
Right, I guess any LLVM-IR-level API would have to be upgraded to take the new
semantics into account.
I'm not sure that 'br poison -> UB' is new rather than a
clarification, but it's true that there were multiple interpretations for
'br poison'.
I'm curious, btw: did you have any concrete API in mind?

>> and 0, poison -> poison
>
> This is similar to the existing poison, and it raises similar questions.
Consider the following code:
> 
>   %x = call i32 @foo()
>   %y = or i32 %x, 1
>   %c = call i1 @some_condition()
>   br i1 %c, label %true, label %false
> true:
>   %d = udiv i32 -1, %y
> false:
>   %z = phi i32 [ %true, %d ], [ %false, 0 ]
> 
> Is it safe to turn the phi into a select? (ignoring profitability)
> 
> KnownBits can tell us that %y always has at least one bit set, so it's
never zero, so the udiv can never divide by zero, so it's safe to speculate,
so the transform is safe. However, if %x is poison and %c is 0, the original
program has no UB, and the transformed program does. It would then execute the
udiv unconditionally, with a divisor of poison.
> 
> Inserting a freeze could fix this. However, where does the freeze go? %y is
an input to the if-conversion pattern as SimpifyCFG knows it, however freezing
%y doesn't help. Instead, the thing that needs to be frozen is %x, because
that was the input to the KnownBits analysis that said it was safe. It would
seem that either KnownBits would need to record the values it looked at, or
there'd have to be a way to recompute the set on demand, so that these
values could be frozen if needed. These might be manageable for KnownBits,
though more complicated analyses (perhaps an Andersen's-style points-to
system?) could be more awkward.
Right, that's a very good point. We already have this problem today as well,
though.
We can translate this into a select by using freeze, as you say (that's
exactly for these cases why we are proposing to introduce freeze).
What we need to settle on, and we didn't touch this on our proposal, is how
LLVM's analyses API will look like. Most (if not all) LLVM analyses today
report a result that doesn't exclude that the value might be poison. 
That's because if you report %v to be non-null and it's actually poison
it's fine since poison can be restricted to be non-null.  We will need to
introduce a isNotPoison() analysis and a ensureIsNonPoison() utility (that needs
to be used by all transformations doing speculation).
I would freeze %y. What's the argument against?

> Auto-vectorization, converting adjacent scalar memory accesses into vector
accesses, or into wider combined scalar accesses is a concern. If widening a
load causes it to read a poison that it didn't previously read, and if the
value is subsequently stored, this would put poison in more individually
addressable places than in the original program, so it could inject UB into a
program that didn't previously have it. This is related to the memcpy topic
that's been raised.
The problem with widening Is already there today. We are not really changing the
semantics of poison, just creating more opportunities for it to appear.
We have a solution for widening, which is to use vectors. Since we define poison
at value-level, we can widen, say, a "load i32" into "load <2
x i32>" (but not to "load i64").  One may argue that this
representation is even better, since it actually exposes the fact that we are
loading multiple, independent values.  But we need to make sure the rest of LLVM
pipeline is fine with increased usage of vectors throughout.

> It's also related to the bitfield assignment topic. The solution where
the first initialization writes a frozen poison over the adjacent bytes, thereby
protecting subsequent assignments from unfrozen poison, is clever. However, it
also raises some questions: Is the width at which any given bitfield field is
initialized to be an ABI-exposed detail (all front-ends must emit the same width
accesses for a given bitfield)? And, does this constrain the optimizer's
ability to shrink such stores?
That's an interesting point; didn't think about it before.  You're
right that all frontends manipulating a given bitfield would have to agree on
the access size (at IR level; at assembly level it shouldn't matter).
Regarding store shrinking, I feel it's something better suited to SDAG/MI
level.  There if we stick with undef, we can support shrinking.  If we introduce
poison up to (and including) MI, then things become tricky.

Thanks,
Nuno

Hi Nuno,

Nuno Lopes wrote:
  > Right, that's a very good point. We already have this problem today 
as well, though.
 > We can translate this into a select by using freeze, as you say 
(that's exactly for these cases why we are proposing to introduce freeze).
 > What we need to settle on, and we didn't touch this on our proposal, 
is how LLVM's analyses API will look like. Most (if not all) LLVM 
analyses today report a result that doesn't exclude that the value might 
be poison.  That's because if you report %v to be non-null and it's 
actually poison it's fine since poison can be restricted to be non-null. 
  We will need to introduce a isNotPoison() analysis and a 
ensureIsNonPoison() utility (that needs to be used by all 
transformations doing speculation).
 > I would freeze %y. What's the argument against?

frozen %y can be zero if %x (and thus %y) is poison.

ensureIsNonPoison will have to work in concert with whatever inferred
%y to be non-zero.



What follows is rather vague, so take with a pinch of salt:

However, I don't think there is an easy way to solve the problem Dan
pointed out (beyond "freeze the right things") as long as both of
these hold:

  1. We infer properties for values based on how they're computed (i.e.
     (or X 1) != 0).

  2. We allow behavior that cannot be explained by assigning to each
     SSA register a value that is legal in the type of the SSA
     register.

What I mean by this is, say you have:

   %val0 = load ...
   %val1 = load ...
   %result = add nsw i32 %val0, %val1
   %result.sext = sext %result to i64

The high 32 bits of %result.sext have to be 0 or -1 because it is
computed via a sext (by (1)).  However if we commute the sext through
the addition (because %result is nsw, and you want to exploit (2))
then that is no longer true.  That is, Once you've assumed that the
high 32 bits of %result.sext are 0 or -1, then you fundamentally
_need_ an optimization barrier to prevent (2) from occurring.

-- Sanjoy

> Nuno Lopes wrote:
> > Right, that's a very good point. We already have this problem
today as well, though.
> > We can translate this into a select by using freeze, as you say
(that's exactly for these cases why we are proposing to introduce freeze).
> > What we need to settle on, and we didn't touch this on our
proposal, is how LLVM's analyses API will look like. Most (if not all) LLVM
analyses today report a result that doesn't exclude that the value might be
poison.  That's because if you report %v to be non-null and it's
actually poison it's fine since poison can be restricted to be non-null.
> >  We will need to introduce a isNotPoison() analysis and a
ensureIsNonPoison() utility (that needs to be used by all transformations doing
speculation).
> > I would freeze %y. What's the argument against?
> 
> frozen %y can be zero if %x (and thus %y) is poison.
> 
> ensureIsNonPoison will have to work in concert with whatever inferred %y to
be non-zero.
Ah, you're very right. Freeze(%y) is not sufficient.

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.
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.
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.
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.

Nuno

On 10/21/2016 01:53 PM, Nuno Lopes via llvm-dev wrote:
>> Auto-vectorization, converting adjacent scalar memory accesses into
vector accesses, or into wider combined scalar accesses is a concern. If
widening a load causes it to read a poison that it didn't previously read,
and if the value is subsequently stored, this would put poison in more
individually addressable places than in the original program, so it could inject
UB into a program that didn't previously have it. This is related to the
memcpy topic that's been raised.
> The problem with widening Is already there today. We are not really
changing the semantics of poison, just creating more opportunities for it to
appear.
> We have a solution for widening, which is to use vectors. Since we define
poison at value-level, we can widen, say, a "load i32" into "load
<2 x i32>" (but not to "load i64").  One may argue that
this representation is even better, since it actually exposes the fact that we
are loading multiple, independent values.  But we need to make sure the rest of
LLVM pipeline is fine with increased usage of vectors throughout.
Specifically to this point, we have independent reasons to prefer a 
vector representation for a set of widened loads.  Specifically, if the 
loads in question are atomic, we need to be able to represent the 
individual elements' atomicity (as opposed to the widened widths 
atomicity), if we want a chance to reverse the transformation later.  If 
widening is to be a canonicalization at the IR level, being able to 
reverse it is a must.

Worth noting though is that this doesn't stop with vectors.  It might 
very well be worthwhile to widen a pair of adjacent i8 loads with a 
adjacent i16 load.  The same argument which leads us to wanting to 
preserve the elements of the vector, would now lead us directly to 
structs being a first class IR construct.  And we do love FCAs don't we?  :)

Philip
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161102/178e08c8/attachment.html>

On Wed, Nov 2, 2016 at 5:55 PM Philip Reames via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
>
> On 10/21/2016 01:53 PM, Nuno Lopes via llvm-dev wrote:
>
> Auto-vectorization, converting adjacent scalar memory accesses into vector
accesses, or into wider combined scalar accesses is a concern. If widening a
load causes it to read a poison that it didn't previously read, and if the
value is subsequently stored, this would put poison in more individually
addressable places than in the original program, so it could inject UB into a
program that didn't previously have it. This is related to the memcpy topic
that's been raised.
>
> The problem with widening Is already there today. We are not really
changing the semantics of poison, just creating more opportunities for it to
appear.
> We have a solution for widening, which is to use vectors. Since we define
poison at value-level, we can widen, say, a "load i32" into "load
<2 x i32>" (but not to "load i64").  One may argue that
this representation is even better, since it actually exposes the fact that we
are loading multiple, independent values.  But we need to make sure the rest of
LLVM pipeline is fine with increased usage of vectors throughout.
>
> Specifically to this point, we have independent reasons to prefer a vector
> representation for a set of widened loads.  Specifically, if the loads in
> question are atomic, we need to be able to represent the individual
> elements' atomicity (as opposed to the widened widths atomicity),
>
But that's not how atomic vectors work -- they're atomic for the
*vector*
and not for the elements!

Put differently, the atomicity is on the *operation*.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161104/dba11a85/attachment.html>