llvm dev - Feb 2015 - [LLVMdev] Proposal to Remove Poison

Hello,

I'd like to offer an alternative solution to the "poison problem":
remove
it.

What follows is rather informal.  I'd happily write up a nicer document if
this RFC stands up to scrutiny.

The idea was born from two observations:
- undef was introduced to model a load of uninitialized memory, a form of
undefined behavior.
- poison was introduced to model integer overflow, another form of
undefined behavior.

I find it awkward that one form of uninitialized behavior is more or less
powerful than another.

We rely on the following properties for undef:
- undef is permitted to be an arbitrary bit-pattern.
- Instructions may or may not be value dependent on their undef operands.

We rely on the following properties for poison:
- Instructions which have poison operands are capable of providing results
which are not consistent with a two's complement operand.

Here is a case where we believed distinguishing between poison and undef is
essential:
%add = add nsw i32 %a, %b
%cmp = icmp sgt i32 %add, %a

If %a is INT_MAX and %b is 1, then %add results in overflow.
If overflow results in undef, then %cmp would be equivalent to:
%cmp = icmp sgt i32 undef, INT_MIN

There is no bit-pattern we could substitute for undef which would make %cmp
true, this means that we cannot optimize %cmp to 'icmp sgt i32 %b, 0'.

Poison was created to allow us to produce whatever value we'd like for %cmp
if %add resulted in overflow.

What I would like to do is to remove poison and replace it with undef while
still optimizing comparison instructions.  The quick-and-dirty way of
stating this is: an icmp with an undef operand produces undef regardless of
its other operand.

I believe this would allow us to exploit and optimize overflow in
arithmetic flowing into comparison operations.

Could this be problematic?

Whether we intended to or not, LLVM's implementation of undef's
semantics
already allows us to say that a memory location is not equivalent to any
possible bit-pattern.

Consider the following program:
define i1 @f() {
  %mem = alloca i1
  %load = load i1* %mem
  %cmp = icmp eq i1 %load, false
  ret i1 %cmp
}

Because it is possible for %load's undef to be either true or false, %cmp
must be equivalent to undef as well.  This is completely consistent with
the above rules.

The following program is a little more interesting:
define i1 @g() {
  %mem = alloca i1
  %load = load i1* %mem
  %cmp0 = icmp eq i1 %load, 0
  %cmp1 = icmp eq i1 %load, 1
  %and = xor i1 %cmp0, %cmp1
  ret i1 %and
}

The intent of this program is to compare a memory location against all
possible values the location might have.

If we ran LLVM's InstCombine pass then %and would have been replaced with
the "expected" result of true.

If we instead ran SROA over @g, we would be left with:
  %cmp0 = icmp eq i1 undef, false
  %cmp1 = icmp eq i1 undef, true
  %and = xor i1 %cmp0, %cmp1

Now that %cmp0 and %cmp1 have different undef values, %and is now undef.
This result is sufficient to say that the contents of %mem are neither true
nor false!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150208/b61ad4fe/attachment.html>

----- Original Message -----
> From: "David Majnemer" <david.majnemer at gmail.com>
> To: llvmdev at cs.uiuc.edu
> Cc: "Nuno Lopes" <nuno.lopes at ist.utl.pt>, "John
Regehr" <regehr at cs.utah.edu>
> Sent: Sunday, February 8, 2015 4:23:15 AM
> Subject: [LLVMdev] RFC: Proposal to Remove Poison
> 
> Hello,
> 
> 
> I'd like to offer an alternative solution to the "poison
problem":
> remove it.
> 
> 
> What follows is rather informal. I'd happily write up a nicer
> document if this RFC stands up to scrutiny.
> 
> 
> The idea was born from two observations:
> - undef was introduced to model a load of uninitialized memory, a
> form of undefined behavior.
> - poison was introduced to model integer overflow, another form of
> undefined behavior.
> 
> 
> I find it awkward that one form of uninitialized behavior is more or
> less powerful than another.
> 
> 
> We rely on the following properties for undef:
> - undef is permitted to be an arbitrary bit-pattern.
> - Instructions may or may not be value dependent on their undef
> operands.
> 
> 
> 
> We rely on the following properties for poison:
> - Instructions which have poison operands are capable of providing
> results which are not consistent with a two's complement operand.
> 
> 
> Here is a case where we believed distinguishing between poison and
> undef is essential:
> %add = add nsw i32 %a, %b
> %cmp = icmp sgt i32 %add, %a
> 
> 
> If %a is INT_MAX and %b is 1, then %add results in overflow.
> 
> If overflow results in undef, then %cmp would be equivalent to:
> %cmp = icmp sgt i32 undef, INT_MIN
> 
> 
> There is no bit-pattern we could substitute for undef which would
> make %cmp true, this means that we cannot optimize %cmp to 'icmp sgt
> i32 %b, 0'.
> 
> 
> Poison was created to allow us to produce whatever value we'd like
> for %cmp if %add resulted in overflow.
> 
> 
> What I would like to do is to remove poison and replace it with undef
> while still optimizing comparison instructions. The quick-and-dirty
> way of stating this is: an icmp with an undef operand produces undef
> regardless of its other operand.
Currently, we might replace:
  %cmp = icmp sgt i32 undef, INT_MAX -> i1 false

According to this proposal, we could replace:
 %cmp = icmp sgt i32 undef, INT_MAX -> i1 undef

While replacing it with false is still allowed, so is replacing it with true.
I'm not sure this makes sense.
> 
> 
> I believe this would allow us to exploit and optimize overflow in
> arithmetic flowing into comparison operations.
> 
> 
> Could this be problematic?
> 
> 
> Whether we intended to or not, LLVM's implementation of undef's
> semantics already allows us to say that a memory location is not
> equivalent to any possible bit-pattern.
> 
> 
> 
> Consider the following program:
> 
> define i1 @f() {
> %mem = alloca i1
> %load = load i1* %mem
> %cmp = icmp eq i1 %load, false
> ret i1 %cmp
> }
> 
> 
> Because it is possible for %load's undef to be either true or false,
> %cmp must be equivalent to undef as well. This is completely
> consistent with the above rules.
> 
> 
> The following program is a little more interesting:
> 
> define i1 @g() {
> %mem = alloca i1
> %load = load i1* %mem
> %cmp0 = icmp eq i1 %load, 0
> %cmp1 = icmp eq i1 %load, 1
> %and = xor i1 %cmp0, %cmp1
> ret i1 %and
> }
> 
> 
> The intent of this program is to compare a memory location against
> all possible values the location might have.
> 
> If we ran LLVM's InstCombine pass then %and would have been replaced
> with the "expected" result of true.
> 
> 
> 
> If we instead ran SROA over @g, we would be left with:
> 
> 
> %cmp0 = icmp eq i1 undef, false
> %cmp1 = icmp eq i1 undef, true
> %and = xor i1 %cmp0, %cmp1
> 
> 
> Now that %cmp0 and %cmp1 have different undef values, %and is now
> undef.
> This result is sufficient to say that the contents of %mem are
> neither true nor false!
In the past, this has been explained to me in the following way: undef values
have a definitive bit pattern per use, consistent with all relevant constraints,
but may have a different pattern at each use. Thus, the reason that the SROA
transformation is allowable is that the undef is 'used' twice, once in
each comparison, and is otherwise unconstrained, and so make take on a different
value (0 or 1 here) at each comparison.

That having been said, this is also somewhat loose, because IR-level operations
have no atomicity. An i32 add could be replaced by i16 operations (that would
'use' the undef input multiple times).

 -Hal
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

On Sun, Feb 8, 2015 at 8:38 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
>
> Currently, we might replace:
>   %cmp = icmp sgt i32 undef, INT_MAX -> i1 false
>
> According to this proposal, we could replace:
>  %cmp = icmp sgt i32 undef, INT_MAX -> i1 undef
>
> While replacing it with false is still allowed, so is replacing it with
> true. I'm not sure this makes sense.

I think your example is a compelling argument for making icmp more powerful
and less obvious when you replace INT_MAX with an unknown variable %a:
%cmp = icmp sgt i32 undef, %a

We'd like to make %cmp undef without having to prove that %a is not
INT_MAX. I'm pretty sure instcombine does something like this today, and
this change would provide the basis for it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150208/844417cc/attachment.html>

> On Feb 8, 2015, at 2:23 AM, David Majnemer <david.majnemer at
gmail.com> wrote:
> 
> Hello,
> 
> I'd like to offer an alternative solution to the "poison
problem": remove it.
> 
> What follows is rather informal.  I'd happily write up a nicer document
if this RFC stands up to scrutiny.
> 
> The idea was born from two observations:
> - undef was introduced to model a load of uninitialized memory, a form of
undefined behavior.
> - poison was introduced to model integer overflow, another form of
undefined behavior.
> 
> I find it awkward that one form of uninitialized behavior is more or less
powerful than another.
> 
> We rely on the following properties for undef:
> - undef is permitted to be an arbitrary bit-pattern.
> - Instructions may or may not be value dependent on their undef operands.
> 
> We rely on the following properties for poison:
> - Instructions which have poison operands are capable of providing results
which are not consistent with a two's complement operand.
> 
> Here is a case where we believed distinguishing between poison and undef is
essential:
> %add = add nsw i32 %a, %b
> %cmp = icmp sgt i32 %add, %a
> 
> If %a is INT_MAX and %b is 1, then %add results in overflow.
> If overflow results in undef, then %cmp would be equivalent to:
> %cmp = icmp sgt i32 undef, INT_MIN
> 
> There is no bit-pattern we could substitute for undef which would make %cmp
true, this means that we cannot optimize %cmp to 'icmp sgt i32 %b, 0'.
> 
> Poison was created to allow us to produce whatever value we'd like for
%cmp if %add resulted in overflow.
> 
> What I would like to do is to remove poison and replace it with undef while
still optimizing comparison instructions.  The quick-and-dirty way of stating
this is: an icmp with an undef operand produces undef regardless of its other
operand.
> 
> I believe this would allow us to exploit and optimize overflow in
arithmetic flowing into comparison operations.
> 
> Could this be problematic?
> 
> Whether we intended to or not, LLVM's implementation of undef's
semantics already allows us to say that a memory location is not equivalent to
any possible bit-pattern.
> 
> Consider the following program:
> define i1 @f() {
>   %mem = alloca i1
>   %load = load i1* %mem
>   %cmp = icmp eq i1 %load, false
>   ret i1 %cmp
> }
> 
> Because it is possible for %load's undef to be either true or false,
%cmp must be equivalent to undef as well.  This is completely consistent with
the above rules.
> 
> The following program is a little more interesting:
> define i1 @g() {
>   %mem = alloca i1
>   %load = load i1* %mem
>   %cmp0 = icmp eq i1 %load, 0
>   %cmp1 = icmp eq i1 %load, 1
>   %and = xor i1 %cmp0, %cmp1
>   ret i1 %and
> }
> 
> The intent of this program is to compare a memory location against all
possible values the location might have.
> 
> If we ran LLVM's InstCombine pass then %and would have been replaced
with the "expected" result of true.
> 
> If we instead ran SROA over @g, we would be left with:
>   %cmp0 = icmp eq i1 undef, false
>   %cmp1 = icmp eq i1 undef, true
>   %and = xor i1 %cmp0, %cmp1
> 
> Now that %cmp0 and %cmp1 have different undef values, %and is now undef.

 In your example above, it seems to me that the replacement of all %load uses
with “undef" is the reason we are losing the information that the compares
operate on the same value. I’m curious about why isn’t undef attached to a
value?
Wouldn’t it be desirable to be able to distinguish “undef" when they have
to be the same value or not?

Thanks,

— 
Mehdi

David, this sounds promising.  One thing we should do is dig up some of 
Dan Gohman's old emails on this topic and make sure that your idea passes 
his litmus tests.

A few random things that want to be discussed in the detailed RFC:

- what constitutes separate reads of an undef? for example is "%1 = xor 
undef, undef" different from "%0 = undef ; %1 = xor %0, %0"?

- how do select and phi and br work in the value dependent and 
not-value-dependent cases?

- what is the list of "true UBs" that do not fall into your proposed 
model?  for example, I assume divide by zero and OOB store

John

Hi David,

I have serious doubts about this approach.  This is essentially how undef was
originally implemented in LLVM, back in the mists of time.  It led to a lot of
bugs that Dan (and others) fixed in the 2008-2010 timeframe, culminating in the
modern definition of undef, and poison as a complementary concept. 
Unfortunately, I don’t have pointers to those bugs, but I imagine some codebase
archeology could turn them up.

—Owen
> On Feb 8, 2015, at 2:23 AM, David Majnemer <david.majnemer at
gmail.com> wrote:
> 
> Hello,
> 
> I'd like to offer an alternative solution to the "poison
problem": remove it.
> 
> What follows is rather informal.  I'd happily write up a nicer document
if this RFC stands up to scrutiny.
> 
> The idea was born from two observations:
> - undef was introduced to model a load of uninitialized memory, a form of
undefined behavior.
> - poison was introduced to model integer overflow, another form of
undefined behavior.
> 
> I find it awkward that one form of uninitialized behavior is more or less
powerful than another.
> 
> We rely on the following properties for undef:
> - undef is permitted to be an arbitrary bit-pattern.
> - Instructions may or may not be value dependent on their undef operands.
> 
> We rely on the following properties for poison:
> - Instructions which have poison operands are capable of providing results
which are not consistent with a two's complement operand.
> 
> Here is a case where we believed distinguishing between poison and undef is
essential:
> %add = add nsw i32 %a, %b
> %cmp = icmp sgt i32 %add, %a
> 
> If %a is INT_MAX and %b is 1, then %add results in overflow.
> If overflow results in undef, then %cmp would be equivalent to:
> %cmp = icmp sgt i32 undef, INT_MIN
> 
> There is no bit-pattern we could substitute for undef which would make %cmp
true, this means that we cannot optimize %cmp to 'icmp sgt i32 %b, 0'.
> 
> Poison was created to allow us to produce whatever value we'd like for
%cmp if %add resulted in overflow.
> 
> What I would like to do is to remove poison and replace it with undef while
still optimizing comparison instructions.  The quick-and-dirty way of stating
this is: an icmp with an undef operand produces undef regardless of its other
operand.
> 
> I believe this would allow us to exploit and optimize overflow in
arithmetic flowing into comparison operations.
> 
> Could this be problematic?
> 
> Whether we intended to or not, LLVM's implementation of undef's
semantics already allows us to say that a memory location is not equivalent to
any possible bit-pattern.
> 
> Consider the following program:
> define i1 @f() {
>   %mem = alloca i1
>   %load = load i1* %mem
>   %cmp = icmp eq i1 %load, false
>   ret i1 %cmp
> }
> 
> Because it is possible for %load's undef to be either true or false,
%cmp must be equivalent to undef as well.  This is completely consistent with
the above rules.
> 
> The following program is a little more interesting:
> define i1 @g() {
>   %mem = alloca i1
>   %load = load i1* %mem
>   %cmp0 = icmp eq i1 %load, 0
>   %cmp1 = icmp eq i1 %load, 1
>   %and = xor i1 %cmp0, %cmp1
>   ret i1 %and
> }
> 
> The intent of this program is to compare a memory location against all
possible values the location might have.
> 
> If we ran LLVM's InstCombine pass then %and would have been replaced
with the "expected" result of true.
> 
> If we instead ran SROA over @g, we would be left with:
>   %cmp0 = icmp eq i1 undef, false
>   %cmp1 = icmp eq i1 undef, true
>   %and = xor i1 %cmp0, %cmp1
> 
> Now that %cmp0 and %cmp1 have different undef values, %and is now undef.
> This result is sufficient to say that the contents of %mem are neither true
nor false!
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

> I have serious doubts about this approach.  This is essentially how 
> undef was originally implemented in LLVM, back in the mists of time. 
> It led to a lot of bugs that Dan (and others) fixed in the 2008-2010 
> timeframe, culminating in the modern definition of undef, and poison as 
> a complementary concept.  Unfortunately, I don?t have pointers to those 
> bugs, but I imagine some codebase archeology could turn them up.
We need a library of allowed / disallowed / disputed transformations, 
including the rationale for each.  I'm happy to start working on this 
though my available bandwidth isn't too high right now.  Does a github 
repo sound like the right thing here?

John

On Sun, Feb 8, 2015 at 1:57 PM, Owen Anderson <resistor at mac.com> wrote:
> Hi David,
>
> I have serious doubts about this approach.  This is essentially how undef
> was originally implemented in LLVM, back in the mists of time.  It led to a
> lot of bugs that Dan (and others) fixed in the 2008-2010 timeframe,
> culminating in the modern definition of undef, and poison as a
> complementary concept.  Unfortunately, I don’t have pointers to those bugs,
> but I imagine some codebase archeology could turn them up.
>
Having different notions of undef and poison are problematic as well.

This proposal is motivated from the observation that, in practice, we
transform:
define i1 @f(i32 %x, i32 %y, i1 %C) {
  %add = add nsw i32 %x, %y
  %sel = select i1 %C, i32 %add, i32 undef
  %cmp = icmp sgt i32 %sel, %x
  ret i1 %cmp
}

into:
define i1 @f(i32 %x, i32 %y, i1 %C) {
  %cmp = icmp sgt i32 %y, 0
  ret i1 %cmp
}

If undef isn't as strong as poison, this transformation is not valid.

Why is this the case? Consider that when %C is false, %sel will be undef.
This leaves us with:
  %cmp = icmp sgt i32 undef, %x

%x might be INT_MAX which means that %cmp must be optimized to false.

> —Owen
>
> > On Feb 8, 2015, at 2:23 AM, David Majnemer <david.majnemer at
gmail.com>
> wrote:
> >
> > Hello,
> >
> > I'd like to offer an alternative solution to the "poison
problem":
> remove it.
> >
> > What follows is rather informal.  I'd happily write up a nicer
document
> if this RFC stands up to scrutiny.
> >
> > The idea was born from two observations:
> > - undef was introduced to model a load of uninitialized memory, a form
> of undefined behavior.
> > - poison was introduced to model integer overflow, another form of
> undefined behavior.
> >
> > I find it awkward that one form of uninitialized behavior is more or
> less powerful than another.
> >
> > We rely on the following properties for undef:
> > - undef is permitted to be an arbitrary bit-pattern.
> > - Instructions may or may not be value dependent on their undef
operands.
> >
> > We rely on the following properties for poison:
> > - Instructions which have poison operands are capable of providing
> results which are not consistent with a two's complement operand.
> >
> > Here is a case where we believed distinguishing between poison and
undef
> is essential:
> > %add = add nsw i32 %a, %b
> > %cmp = icmp sgt i32 %add, %a
> >
> > If %a is INT_MAX and %b is 1, then %add results in overflow.
> > If overflow results in undef, then %cmp would be equivalent to:
> > %cmp = icmp sgt i32 undef, INT_MIN
> >
> > There is no bit-pattern we could substitute for undef which would make
> %cmp true, this means that we cannot optimize %cmp to 'icmp sgt i32 %b,
0'.
> >
> > Poison was created to allow us to produce whatever value we'd like
for
> %cmp if %add resulted in overflow.
> >
> > What I would like to do is to remove poison and replace it with undef
> while still optimizing comparison instructions.  The quick-and-dirty way of
> stating this is: an icmp with an undef operand produces undef regardless of
> its other operand.
> >
> > I believe this would allow us to exploit and optimize overflow in
> arithmetic flowing into comparison operations.
> >
> > Could this be problematic?
> >
> > Whether we intended to or not, LLVM's implementation of
undef's
> semantics already allows us to say that a memory location is not equivalent
> to any possible bit-pattern.
> >
> > Consider the following program:
> > define i1 @f() {
> >   %mem = alloca i1
> >   %load = load i1* %mem
> >   %cmp = icmp eq i1 %load, false
> >   ret i1 %cmp
> > }
> >
> > Because it is possible for %load's undef to be either true or
false,
> %cmp must be equivalent to undef as well.  This is completely consistent
> with the above rules.
> >
> > The following program is a little more interesting:
> > define i1 @g() {
> >   %mem = alloca i1
> >   %load = load i1* %mem
> >   %cmp0 = icmp eq i1 %load, 0
> >   %cmp1 = icmp eq i1 %load, 1
> >   %and = xor i1 %cmp0, %cmp1
> >   ret i1 %and
> > }
> >
> > The intent of this program is to compare a memory location against all
> possible values the location might have.
> >
> > If we ran LLVM's InstCombine pass then %and would have been
replaced
> with the "expected" result of true.
> >
> > If we instead ran SROA over @g, we would be left with:
> >   %cmp0 = icmp eq i1 undef, false
> >   %cmp1 = icmp eq i1 undef, true
> >   %and = xor i1 %cmp0, %cmp1
> >
> > Now that %cmp0 and %cmp1 have different undef values, %and is now
undef.
> > This result is sufficient to say that the contents of %mem are neither
> true nor false!
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150208/2d437e81/attachment.html>

> If we instead ran SROA over @g, we would be left with:
>   %cmp0 = icmp eq i1 undef, false
>   %cmp1 = icmp eq i1 undef, true
>   %and = xor i1 %cmp0, %cmp1
I think it has to be that way, since otherwise the two programs:

 %x = load %M
 %y = load %M
 use(%x, %y)

and

 %x = load %M
 use(%x, %x)

would not be equivalent and we would not be able to do load commoning
(I'm somewhat speculating here -- I'm not actually sure if the two
programs above are equivalent).  And those load instructions are
independently undef.  In other words, the "problem" here is that the
two programs above are supposed to be equivalent *and* that a load
from an uninitialized location is undef.

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
think this also justifies existence of undef -- if uninitialized loads
were supposed to be just some value consistently, then you could get
the same semantics by saying that uninitialized locations contain
"some arbitrary N bit value".  Stating that loads from uninitialized
values are undef is strictly stronger, as your example shows.

-- Sanjoy
>
> Now that %cmp0 and %cmp1 have different undef values, %and is now undef.
> This result is sufficient to say that the contents of %mem are neither true
> nor false!
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

> 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

> The following program is a little more interesting:
> define i1 @g() {
>   %mem = alloca i1
>   %load = load i1* %mem
>   %cmp0 = icmp eq i1 %load, 0
>   %cmp1 = icmp eq i1 %load, 1
>   %and = xor i1 %cmp0, %cmp1
>   ret i1 %and
> }
> 
> The intent of this program is to compare a memory location against all
possible values the location might have.
> 
> If we ran LLVM's InstCombine pass then %and would have been replaced
with the "expected" result of true.
> 
> If we instead ran SROA over @g, we would be left with:
>   %cmp0 = icmp eq i1 undef, false
>   %cmp1 = icmp eq i1 undef, true
>   %and = xor i1 %cmp0, %cmp1
This transformation is invalid in the light of current LLVM's semantics.
Although it's fine according to the C standard (it's undefined
behavior), it's highly non-intuitive.  (now I recall why 'xor %a,
%a' could be different than 0).
 Sanjoy proposed in another email to make undef an instruction. That would
actually solve this problem. SROA could replace the load with an undef
instruction, forcing %and to be true. Undef instructions could be determinized
to 0 in codegen (if not removed beforehand).

The downsize of having just one type of undef is that then all undefs are the
same in the following sense:
%mem = alloca
%load = load %mem
%cmp = icmp slt %load, INT_MIN

With current LLVM, %cmp will always be false. With your proposal, %cmp will be
undef, and therefore potentially true, which is strange.


Nuno

>  Sanjoy proposed in another email to make undef an instruction. That would
actually solve this problem. SROA could replace the load with an undef
instruction, forcing %and to be true. Undef instructions could be determinized
to 0 in codegen (if not removed beforehand).
Undef-as-an-instruction has a problem when combined with "loads from
uninitialized memory are undef".  If by "loads from uninitialized
memory are undef" we mean the old "undef" then we have the same
problem of "xor %x, %x" not always being zero.  And if by "loads
from
uninitialized memory are undef" we mean "the load is equivalent to an
gen_undef instruction" then we cannot duplicate loads unless we know
that the load is from initialized memory since

%x = load P
%y = xor %x, %x

is not the same as

%x0 = load P
%x1 = load P
%y = xor %x0, %x1

for an uninitialized *P

-- Sanjoy
>
> The downsize of having just one type of undef is that then all undefs are
the same in the following sense:
> %mem = alloca
> %load = load %mem
> %cmp = icmp slt %load, INT_MIN
>
> With current LLVM, %cmp will always be false. With your proposal, %cmp will
be undef, and therefore potentially true, which is strange.
>
>
> Nuno
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev