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

[Hans Wennborg via llvm-dev]

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