noalias locals

Right now, I don't see any way to declare that a pointer value within
a function does not alias any pointer not based on it. Basically, I
would like to be able to apply "noalias" to an instruction/virtual reg
the same way that noalias is applied to function arguments.

A few weeks ago when discussing devirtualization possibilities in C++,
it turned out that while you can assume that the vtbl pointer is the
same for every use of a given object pointer, you cannot assume that
the vtbl pointer is the same for every pointer that MustAlias's that
object pointer. This means that, without the ability to apply
"noalias" to the result of placement-new, we cannot simply declare
vtbl pointers to be invariant... that would lead the optimizer to
assume that the vtbl pointer accessed through the placement-new'd
pointer must be the same as the vtbl pointer accessed through a
pointer to an object previously allocated in that same memory
location, which is not required to be the case.

To fix that and compile C++ correctly while aggressively
devirtualizing it, we would need to apply "noalias" to the result of
placement-new in all cases, even when placement-new is inlined. More
generally, when inlining any function with a "noalias" return, the
inlined result needs to have "noalias" applied to it.

To implement it, we can either declare a no-op intrinsic that simply
transfers the value while preventing AliasAnalysis from looking
through it, or we can introduce a new attribute and teach alias
analysis to recognize it. The first one requires small changes to
codegen, while the second one would require changes to every alias
analysis (I don't think the default AA is called unless all AA's
chained to it return MayAlias) in order to stop them from returning
MustAlias on annotated values and force them to return NoAlias
instead.

Is that the right way to go? It seems like that might cause other
optimizers to introduce invalid transformations. For example, if the
instruction scheduler knows that those pointers don't alias, it might
reschedule a store to the memory after the constructor call from the
placement new.

struct Foo {
  int a;
  Foo(int a) : a(a) {}
};

int main(void) {
  Foo f;
  f.a = 1;
  Foo *p = new (&f) Foo(2);
  // what does p->a contain? 1 or 2?
}

There's a lot of problems with this example, but I don't know enough
optimizer details to construct a better one.

Can you get by with a MayAlias? It seems like you can divirtualize
everything that MustAlias and ignore the rest.

If I understood the last discussion on this, the reason you don't need
to worry about placement new getting called within callees is that you
have to use the pointer returned by placement new, or you get
undefined behavior, so you can safely assume the vptr is immutable.

Reid

To fix that and compile C++ correctly while aggressively
devirtualizing it, we would need to apply "noalias" to the result of
placement-new in all cases, even when placement-new is inlined. More
generally, when inlining any function with a "noalias" return, the
inlined result needs to have "noalias" applied to it.

Is that the right way to go? It seems like that might cause other
optimizers to introduce invalid transformations. For example, if the
instruction scheduler knows that those pointers don't alias, it might
reschedule a store to the memory after the constructor call from the
placement new.

struct Foo {
int a;
Foo(int a) : a(a) {}
};

int main(void) {
Foo f;
f.a = 1;
Foo *p = new (&f) Foo(2);
// what does p->a contain? 1 or 2?
}

There's a lot of problems with this example, but I don't know enough
optimizer details to construct a better one.

Can you get by with a MayAlias? It seems like you can divirtualize
everything that MustAlias and ignore the rest.

I see what you mean. If the placement new result mayalias its
original pointer, we can hold both vptrs invariant and have everything
else reloaded from memory as appropriate. Now if the placement-new is
known to place an object of a different type from the original object,
the front-end can NoAlias them instead because pointers to the old
object become invalid according to the standard and any use of them
while the new object is in that memory slot is allowed to cause
undefined behavior. So I guess we need to be able to force either
MayAlias or NoAlias as appropriate.

The trouble comes if placement-new overlays an object of a different
type, we allow the result of placement-new to MustAlias the input to
placement-new (which they most certainly will if placement-new is
inlined), and we try to hold the vptrs invariant. In that case, the
optimizer might assume that the new vptr is equal to the original
vptr, which is *not* a valid assumption to make.

If I understood the last discussion on this, the reason you don't need
to worry about placement new getting called within callees is that you
have to use the pointer returned by placement new, or you get
undefined behavior, so you can safely assume the vptr is immutable.

Reid

You're allowed to safely assume the vptr is immutable every time you
reuse a given pointer to the object. The trouble comes when AA can
prove that two different pointers to two different objects actually
point to the same address - the standard allows both pointers to
coexist and both objects to exist in that memory at different times,
as long as a pointer to one object is never used when the memory
contains the other object - and AA can't (currently) prove any such
thing with respect to a pointer returned from a callee.

I don't think that was quite my meaning. I'm saying that NoAlias
isn't what you want, because it allows other optimizations to make
invalid transformations. In this example, with your suggestion after
inlining, my example might look like:

int main(void) {
  Foo f;
  f.a = 1;
  Foo *p = noalias(&f); // magic aliasing intrinsic
  p->a = 2;
}

Now, because &f must not alias p, it would be valid to perform this
transformation:

int main(void) {
  Foo f;
  Foo *p = noalias(&f); // magic aliasing intrinsic
  p->a = 2;
  f.a = 1;
}

If you use MayAlias, this transformation is not legal. Like I said,
it's a bad example, because it's not clear why that transformation
could be profitable, but the point is that stores may be reordered
unsafely. Using MayAlias forces other optimizations to be
conservative. Devirtualization should still be able to work, because
you it will only fire if it sees a MustAlias.

Reid

And I suppose that would also apply to the store of the vptr if the
constructor were inlined. Which means that even if we only NoAlias
the vptrs themselves, we're still not safe.

Good catch. We want the placement-new result to MayAlias the pointer
passed into it. Then we can hold both vptr's invariant throughout
their lifetimes, and each object pointer can assume its vptr will have
the same value each time it's used. The rest of each object will be
assumed to MayAlias the other and stores to one won't be reordered
with respect to stores to the other.