[LLVMdev] Missed devirtualization opportunities

[Kenneth Uildriks]

On Wed, Oct 13, 2010 at 7:59 PM, Kenneth Uildriks <kennethuil at gmail.com> wrote:
> On Wed, Oct 13, 2010 at 7:26 PM, John McCall <rjmccall at apple.com> wrote:
>> On Oct 13, 2010, at 5:09 PM, Kenneth Uildriks wrote:
>>> But I believe the language does allow "undefined behavior" if there's
>>> a use of pT when the pointed-to object isn't actually of type T.  It's
>>> an invalid use in that case, right?
>>
>> Yes, but not for an arbitrary pointer which aliases pT.  That's why it's
>> a problem that llm.invariant is specified in terms of memory;  if we get
>> a pointer that we can prove aliases the invariant memory, we start
>> making assumptions we aren't allowed to make.
>>
>> This C++ code might be well-formed, depending on what 'foo' does to its
>> argument:
>>  A *a = new A();
>>  a->~A();
>>  B *b = new (a) B();
>>  foo(b);
>>  a->bar();
>
> I see the problem now.  My proposed rule would extend A's invariance
> past A->bar, which would mess up any virtual calls through b before
> foo was called...  Any way you cut it, you've gotta have different
> pointers to the same memory assume different contents depending on
> which one is being used at any particular point.  And since they can
> alternate.... ugh.
>
> Now if alias analysis denied that a and b MustAlias... let's take a few cases:
>
> 1. Placement new inside the function: we have to tell AA that a and b
> don't alias.
> 2. Placement new inside a callee... we see a pointer returned from the
> callee, but don't know what its value is.  alias analysis says that a
> MayAlias b, unless the callee's return value is marked noalias, in
> which case alias analysis says that a NoAlias b.  With either of these
> results, the invariance on a->vtblptr is not applied to any loads of
> b->vtblptr.  It is, however, applied to loads a->vtblptr, which is
> exactly what we want.  And the reverse is true for any invariance
> applied to b->vtblptr.
>
> If the callee is ever inlined, we're back to case 1.
>
> So now we need a way to arrange for pointers returned from placement
> new to not alias pointers passed to placement new.  Preferably without
> declaring placement new "noinline".
>

We could always add an intrinsic called "noalias".  It would simply
"return" the pointer it was passed, but AA would see the return value
as a separate pointer from the argument and declare that they don't
alias.  Codegen would turn it into a noop, inlining would ignore it,
and no pass would ever assume they pointed to the same thing.

If that intrinsic was declared to return a NoAlias pointer, the
argument and the return value of the intrinsic would behave kind of
like pointers to different fields of a union.  Each is assumed to
point to its own kind of object, even though they share memory, and if
you use one while the other's value is actually sitting in that memory
you'd get "undefined behavior".  Your use case should would work
perfectly, and even be fully devirtualized, but would (rightfully)
break if "foo" didn't actually turn that B back into an A.

If the intrinsic wasn't declared to return NoAlias, then a and b would
be MayAlias and no devirtualization would occur at all.

Either way, if placement new used the intrinsic, I believe your use
case and others like it would be handled correctly.