llvm dev - Sep 2015 - Comparing stack addresses and function args (Was: [llvm] r174131 - Add a comment explaining an unavailable optimization)

Apologies if this has come up before. I couldn't find any previous
discussion, but I did find this commit.

I was wondering why LLVM cannot optimize this code (which GCC does optimize):

  int f(int *p) { int x; return p == &x; }

it would seem that this must always return 0. (This occurs as a
self-assignment check in the code I was looking at; I was hoping we
could fold that check away.)

I'd be interested to hear what those with a stronger understanding of
the standard than myself think about this, and also if there is any
example of something that could break because of this optimization. If
not, I'd like us to optimize it :-)


On Thu, Jan 31, 2013 at 4:49 PM, Dan Gohman <dan433584 at gmail.com>
wrote:
> Author: djg
> Date: Thu Jan 31 18:49:06 2013
> New Revision: 174131
>
> URL: http://llvm.org/viewvc/llvm-project?rev=174131&view=rev
> Log:
> Add a comment explaining an unavailable optimization.
>
> Modified:
>     llvm/trunk/lib/Analysis/InstructionSimplify.cpp
>
> Modified: llvm/trunk/lib/Analysis/InstructionSimplify.cpp
> URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/InstructionSimplify.cpp?rev=174131&r1=174130&r2=174131&view=diff
>
=============================================================================>
--- llvm/trunk/lib/Analysis/InstructionSimplify.cpp (original)
> +++ llvm/trunk/lib/Analysis/InstructionSimplify.cpp Thu Jan 31 18:49:06
2013
> @@ -1688,6 +1688,34 @@ static Value *ExtractEquivalentCondition
>    return 0;
>  }
>
> +// A significant optimization not implemented here is assuming that alloca
> +// addresses are not equal to incoming argument values. They don't
*alias*,
> +// as we say, but that doesn't mean they aren't equal, so we take
a
> +// conservative approach.
> +//
> +// This is inspired in part by C++11 5.10p1:
> +//   "Two pointers of the same type compare equal if and only if they
are both
> +//    null, both point to the same function, or both represent the same
> +//    address."
> +//
> +// This is pretty permissive.
Indeed :-/
> +// It's also partly due to C11 6.5.9p6:
> +//   "Two pointers compare equal if and only if both are null
pointers, both are
> +//    pointers to the same object (including a pointer to an object and a
> +//    subobject at its beginning) or function, both are pointers to one
past the
> +//    last element of the same array object, or one is a pointer to one
past the
> +//    end of one array object and the other is a pointer to the start of a
> +//    different array object that happens to immediately follow the ï¬ rst
array
> +//    object in the address space.)
> +//
> +// C11's version is more restrictive, however there's no reason
why an argument
> +// couldn't be a one-past-the-end value for a stack object in the
caller and be
> +// equal to the beginning of a stack object in the callee.
This is interesting.

For the one-past-the-end pointer to point into the callee, the stack
would have to be growing upwards. So this won't happen on X86. Can we
turn this optimization on for downward-growing-stack targets?

Second, if the stack grows upward, and the function argument does
point into the callee stack frame, "p" and "&x" could
have the same
contents. So per the "represent the same address" part above, they
should compare equal? But they're noalias? Are we allowed to write
through p? It wasn't a pointer to a valid object when we made the
call, but it became valid in the callee? This is all terrifying.

I suppose one could store the value of &x though, and then use it
again later, i.e.:

  int *global;
  int f(int *p) {
    int x;
    global = &x;
    return p == &x;
  }
  int g() {
    f(0);
    return f(global);
  }

Is g() guaranteed to return 1 here? Maybe we could claim it's
implementation dependent? GCC does not seem fold p==&x to 0 here. I
suppose we could make sure to check whether &x escapes the function?

 - Hans

On Thu, Sep 24, 2015 at 2:42 PM, Hans Wennborg <hans at chromium.org>
wrote:
> Apologies if this has come up before. I couldn't find any previous
> discussion, but I did find this commit.
>
> I was wondering why LLVM cannot optimize this code (which GCC does
optimize):
>
>   int f(int *p) { int x; return p == &x; }
>
> it would seem that this must always return 0. (This occurs as a
> self-assignment check in the code I was looking at; I was hoping we
> could fold that check away.)
This is different than a self-assignment check, is it not?

blah& operator=(const blah &b) {
  if (&b == this) {}
  // ...
}

(Because it gets the pointer from the parameter and compares against a
"local" pointer?)

I just want to make sure that you're not suggesting we should optimize
away self-assignment checks in the general case. I agree that the code
you provided should optimize away, based on my understanding of the C
and C++ standards (which may be faulty, and that's why I've CCed in
Richard).

~Aaron
>
> I'd be interested to hear what those with a stronger understanding of
> the standard than myself think about this, and also if there is any
> example of something that could break because of this optimization. If
> not, I'd like us to optimize it :-)
>
>
> On Thu, Jan 31, 2013 at 4:49 PM, Dan Gohman <dan433584 at gmail.com>
wrote:
>> Author: djg
>> Date: Thu Jan 31 18:49:06 2013
>> New Revision: 174131
>>
>> URL: http://llvm.org/viewvc/llvm-project?rev=174131&view=rev
>> Log:
>> Add a comment explaining an unavailable optimization.
>>
>> Modified:
>>     llvm/trunk/lib/Analysis/InstructionSimplify.cpp
>>
>> Modified: llvm/trunk/lib/Analysis/InstructionSimplify.cpp
>> URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/InstructionSimplify.cpp?rev=174131&r1=174130&r2=174131&view=diff
>>
=============================================================================>>
--- llvm/trunk/lib/Analysis/InstructionSimplify.cpp (original)
>> +++ llvm/trunk/lib/Analysis/InstructionSimplify.cpp Thu Jan 31 18:49:06
2013
>> @@ -1688,6 +1688,34 @@ static Value *ExtractEquivalentCondition
>>    return 0;
>>  }
>>
>> +// A significant optimization not implemented here is assuming that
alloca
>> +// addresses are not equal to incoming argument values. They don't
*alias*,
>> +// as we say, but that doesn't mean they aren't equal, so we
take a
>> +// conservative approach.
>> +//
>> +// This is inspired in part by C++11 5.10p1:
>> +//   "Two pointers of the same type compare equal if and only if
they are both
>> +//    null, both point to the same function, or both represent the
same
>> +//    address."
>> +//
>> +// This is pretty permissive.
>
> Indeed :-/
>
>> +// It's also partly due to C11 6.5.9p6:
>> +//   "Two pointers compare equal if and only if both are null
pointers, both are
>> +//    pointers to the same object (including a pointer to an object
and a
>> +//    subobject at its beginning) or function, both are pointers to
one past the
>> +//    last element of the same array object, or one is a pointer to
one past the
>> +//    end of one array object and the other is a pointer to the start
of a
>> +//    different array object that happens to immediately follow the ï¬
rst array
>> +//    object in the address space.)
>> +//
>> +// C11's version is more restrictive, however there's no
reason why an argument
>> +// couldn't be a one-past-the-end value for a stack object in the
caller and be
>> +// equal to the beginning of a stack object in the callee.
>
> This is interesting.
>
> For the one-past-the-end pointer to point into the callee, the stack
> would have to be growing upwards. So this won't happen on X86. Can we
> turn this optimization on for downward-growing-stack targets?
>
> Second, if the stack grows upward, and the function argument does
> point into the callee stack frame, "p" and "&x"
could have the same
> contents. So per the "represent the same address" part above,
they
> should compare equal? But they're noalias? Are we allowed to write
> through p? It wasn't a pointer to a valid object when we made the
> call, but it became valid in the callee? This is all terrifying.
>
> I suppose one could store the value of &x though, and then use it
> again later, i.e.:
>
>   int *global;
>   int f(int *p) {
>     int x;
>     global = &x;
>     return p == &x;
>   }
>   int g() {
>     f(0);
>     return f(global);
>   }
>
> Is g() guaranteed to return 1 here? Maybe we could claim it's
> implementation dependent? GCC does not seem fold p==&x to 0 here. I
> suppose we could make sure to check whether &x escapes the function?
>
>  - Hans

On Thu, Sep 24, 2015 at 12:06 PM, Aaron Ballman <aaron at
aaronballman.com> wrote:
> On Thu, Sep 24, 2015 at 2:42 PM, Hans Wennborg <hans at chromium.org>
wrote:
>> I was wondering why LLVM cannot optimize this code (which GCC does
optimize):
>>
>>   int f(int *p) { int x; return p == &x; }
>>
>> it would seem that this must always return 0. (This occurs as a
>> self-assignment check in the code I was looking at; I was hoping we
>> could fold that check away.)
>
> This is different than a self-assignment check, is it not?
>
> blah& operator=(const blah &b) {
>   if (&b == this) {}
>   // ...
> }
>
> (Because it gets the pointer from the parameter and compares against a
> "local" pointer?)
>
> I just want to make sure that you're not suggesting we should optimize
> away self-assignment checks in the general case.
Right, I'm not suggesting that :-)

The code I looked at went something like this:

  struct S {
    S& operator=(const S& other) {
      if (&other != this)
        val = other.val;
      return *this;
    }
    void foo();
    int val;
  };
  void S::foo() {
    S tmp;
    tmp.val = 42;
    *this = tmp; // operator= gets inlined; we should know(?) that &tmp !=
this
  }

This is of course a silly example, but with GCC we get:

  movl $42, (%rdi)
  ret

whereas Clang generates:

  movl $42, -8(%rsp)
  leaq -8(%rsp), %rax
  cmpq %rdi, %rax
  je .LBB0_2
  movl $42, (%rdi)
  .LBB0_2:
  retq

which made me sad.

>> I'd be interested to hear what those with a stronger understanding
of
>> the standard than myself think about this, and also if there is any
>> example of something that could break because of this optimization. If
>> not, I'd like us to optimize it :-)
>>
>>
>> On Thu, Jan 31, 2013 at 4:49 PM, Dan Gohman <dan433584 at
gmail.com> wrote:
>>> Author: djg
>>> Date: Thu Jan 31 18:49:06 2013
>>> New Revision: 174131
>>>
>>> URL: http://llvm.org/viewvc/llvm-project?rev=174131&view=rev
>>> Log:
>>> Add a comment explaining an unavailable optimization.
>>>
>>> Modified:
>>>     llvm/trunk/lib/Analysis/InstructionSimplify.cpp
>>>
>>> Modified: llvm/trunk/lib/Analysis/InstructionSimplify.cpp
>>> URL:
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/InstructionSimplify.cpp?rev=174131&r1=174130&r2=174131&view=diff
>>>
=============================================================================>>>
--- llvm/trunk/lib/Analysis/InstructionSimplify.cpp (original)
>>> +++ llvm/trunk/lib/Analysis/InstructionSimplify.cpp Thu Jan 31
18:49:06 2013
>>> @@ -1688,6 +1688,34 @@ static Value *ExtractEquivalentCondition
>>>    return 0;
>>>  }
>>>
>>> +// A significant optimization not implemented here is assuming
that alloca
>>> +// addresses are not equal to incoming argument values. They
don't *alias*,
>>> +// as we say, but that doesn't mean they aren't equal, so
we take a
>>> +// conservative approach.
>>> +//
>>> +// This is inspired in part by C++11 5.10p1:
>>> +//   "Two pointers of the same type compare equal if and only
if they are both
>>> +//    null, both point to the same function, or both represent the
same
>>> +//    address."
>>> +//
>>> +// This is pretty permissive.
>>
>> Indeed :-/
>>
>>> +// It's also partly due to C11 6.5.9p6:
>>> +//   "Two pointers compare equal if and only if both are null
pointers, both are
>>> +//    pointers to the same object (including a pointer to an
object and a
>>> +//    subobject at its beginning) or function, both are pointers
to one past the
>>> +//    last element of the same array object, or one is a pointer
to one past the
>>> +//    end of one array object and the other is a pointer to the
start of a
>>> +//    different array object that happens to immediately follow
the ï¬ rst array
>>> +//    object in the address space.)
>>> +//
>>> +// C11's version is more restrictive, however there's no
reason why an argument
>>> +// couldn't be a one-past-the-end value for a stack object in
the caller and be
>>> +// equal to the beginning of a stack object in the callee.
>>
>> This is interesting.
>>
>> For the one-past-the-end pointer to point into the callee, the stack
>> would have to be growing upwards. So this won't happen on X86. Can
we
>> turn this optimization on for downward-growing-stack targets?
>>
>> Second, if the stack grows upward, and the function argument does
>> point into the callee stack frame, "p" and "&x"
could have the same
>> contents. So per the "represent the same address" part above,
they
>> should compare equal? But they're noalias? Are we allowed to write
>> through p? It wasn't a pointer to a valid object when we made the
>> call, but it became valid in the callee? This is all terrifying.
>>
>> I suppose one could store the value of &x though, and then use it
>> again later, i.e.:
>>
>>   int *global;
>>   int f(int *p) {
>>     int x;
>>     global = &x;
>>     return p == &x;
>>   }
>>   int g() {
>>     f(0);
>>     return f(global);
>>   }
>>
>> Is g() guaranteed to return 1 here? Maybe we could claim it's
>> implementation dependent? GCC does not seem fold p==&x to 0 here. I
>> suppose we could make sure to check whether &x escapes the
function?
>>
>>  - Hans

I believe the background for this comment is just general caution resulting
from
 - vague "both represent the same address." wording in a supported
language
standard, and
 - the surprising situation in which pointer equality semantics are almost
entirely distinct from pointer aliasing semantics

In general, ICmp folding shouldn't consult alias analysis or do its own
alias-analysis-like things.

Dan


On Thu, Sep 24, 2015 at 11:42 AM, Hans Wennborg via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Apologies if this has come up before. I couldn't find any previous
> discussion, but I did find this commit.
>
> I was wondering why LLVM cannot optimize this code (which GCC does
> optimize):
>
>   int f(int *p) { int x; return p == &x; }
>
> it would seem that this must always return 0. (This occurs as a
> self-assignment check in the code I was looking at; I was hoping we
> could fold that check away.)
>
> I'd be interested to hear what those with a stronger understanding of
> the standard than myself think about this, and also if there is any
> example of something that could break because of this optimization. If
> not, I'd like us to optimize it :-)
>
>
> On Thu, Jan 31, 2013 at 4:49 PM, Dan Gohman <dan433584 at gmail.com>
wrote:
> > Author: djg
> > Date: Thu Jan 31 18:49:06 2013
> > New Revision: 174131
> >
> > URL: http://llvm.org/viewvc/llvm-project?rev=174131&view=rev
> > Log:
> > Add a comment explaining an unavailable optimization.
> >
> > Modified:
> >     llvm/trunk/lib/Analysis/InstructionSimplify.cpp
> >
> > Modified: llvm/trunk/lib/Analysis/InstructionSimplify.cpp
> > URL:
>
http://llvm.org/viewvc/llvm-project/llvm/trunk/lib/Analysis/InstructionSimplify.cpp?rev=174131&r1=174130&r2=174131&view=diff
> >
>
=============================================================================>
> --- llvm/trunk/lib/Analysis/InstructionSimplify.cpp (original)
> > +++ llvm/trunk/lib/Analysis/InstructionSimplify.cpp Thu Jan 31
18:49:06
> 2013
> > @@ -1688,6 +1688,34 @@ static Value *ExtractEquivalentCondition
> >    return 0;
> >  }
> >
> > +// A significant optimization not implemented here is assuming that
> alloca
> > +// addresses are not equal to incoming argument values. They
don't
> *alias*,
> > +// as we say, but that doesn't mean they aren't equal, so we
take a
> > +// conservative approach.
> > +//
> > +// This is inspired in part by C++11 5.10p1:
> > +//   "Two pointers of the same type compare equal if and only if
they
> are both
> > +//    null, both point to the same function, or both represent the
same
> > +//    address."
> > +//
> > +// This is pretty permissive.
>
> Indeed :-/
>
> > +// It's also partly due to C11 6.5.9p6:
> > +//   "Two pointers compare equal if and only if both are null
pointers,
> both are
> > +//    pointers to the same object (including a pointer to an object
and
> a
> > +//    subobject at its beginning) or function, both are pointers to
one
> past the
> > +//    last element of the same array object, or one is a pointer to
one
> past the
> > +//    end of one array object and the other is a pointer to the start
> of a
> > +//    different array object that happens to immediately follow the
ï¬
> rst array
> > +//    object in the address space.)
> > +//
> > +// C11's version is more restrictive, however there's no
reason why an
> argument
> > +// couldn't be a one-past-the-end value for a stack object in the
> caller and be
> > +// equal to the beginning of a stack object in the callee.
>
> This is interesting.
>
> For the one-past-the-end pointer to point into the callee, the stack
> would have to be growing upwards. So this won't happen on X86. Can we
> turn this optimization on for downward-growing-stack targets?
>
> Second, if the stack grows upward, and the function argument does
> point into the callee stack frame, "p" and "&x"
could have the same
> contents. So per the "represent the same address" part above,
they
> should compare equal? But they're noalias? Are we allowed to write
> through p? It wasn't a pointer to a valid object when we made the
> call, but it became valid in the callee? This is all terrifying.
>
> I suppose one could store the value of &x though, and then use it
> again later, i.e.:
>
>   int *global;
>   int f(int *p) {
>     int x;
>     global = &x;
>     return p == &x;
>   }
>   int g() {
>     f(0);
>     return f(global);
>   }
>
> Is g() guaranteed to return 1 here? Maybe we could claim it's
> implementation dependent? GCC does not seem fold p==&x to 0 here. I
> suppose we could make sure to check whether &x escapes the function?
>
>  - Hans
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150925/d7030760/attachment.html>