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

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

On Thu, Sep 24, 2015 at 5:15 PM, Hans Wennborg <hans at chromium.org>
wrote:
> 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.
Ah, yes, this makes perfect sense to me. Thank you for the explanation!

~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

I threw together a patch which implements this (attached.)  If we decide 
that this is actually a legal transform, I'm happy to post this for review.

In addition to the version proposed here, I also implemented a case 
where a trivially escaped alloca's address is not equal to any other 
value.  I believe both are valid, but we should confirm.

Philip

On 09/24/2015 02:34 PM, Aaron Ballman via llvm-dev
wrote:
> On Thu, Sep 24, 2015 at 5:15 PM, Hans Wennborg <hans at chromium.org>
wrote:
>> 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.
> Ah, yes, this makes perfect sense to me. Thank you for the explanation!
>
> ~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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: AllocaEscape.diff
Type: text/x-diff
Size: 1933 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150924/6f97cc16/attachment.diff>