[LLVMdev] Missed devirtualization opportunities

[John McCall]

On Oct 11, 2010, at 10:43 AM, Kenneth Uildriks wrote:

> On Mon, Oct 11, 2010 at 12:30 PM, John McCall <rjmccall at apple.com> wrote:
>> On Oct 11, 2010, at 9:12 AM, Kenneth Uildriks wrote:
>>> 3. The front-end, recognizing that scribbling on an instance's vtbl
>>> pointer has undefined results, eliminated the loads of the vtbl
>>> pointer and replaced them with @classvtbl.TestVirtual.  This would
>>> allow devirtualization within a function at least, but (I think) would
>>> do less to allow analysis to spot devirtualization opportunities
>>> across functions.  (Although ArgPromotion could arrange to have the
>>> vtbl pointer passed in separately, and then inlining and/or partial
>>> specialization could be made to see that it's a pointer to a constant
>>> and thus add in the IndirectCallBonus)
>> 
>> There are always going to be cases that can only be deduced with
>> language knowledge.  We already do some frontend de-virtualization;
>> this may just be a missing case.  Can you post your test?
> 
> I compiled the attached c++ code to bitcode using clang++ -O3, then
> ran it through opt -std-compile-opts.  I got a reload of the vtbl
> pointer after the printf call.  The compiler is allowed to cache the
> vtbl pointer as soon as the object is constructed or passed into a
> function, right?

Yes.  This is [basic.life]p7, which lists the conditions under which a pointer
or reference to an object are considered to automatically forward to a new
object that's created at that location (as opposed to formally still pointing
at the destroyed object).  One key constraint is that the objects have to be
of identical type, i.e. their pointers would have to match exactly.  So this is
a fair optimization as long as we make sure that we keep pointers separate.

For example, consider the following test case:
  struct A { virtual void foo(); };
  struct B : A { virtual void foo(); };
  void test() {
    A *a = new A();
    a->foo();  // 1
    a->foo();  // 2: can assume object type is still A
    a->~A();
    A *b = new (a) B();
    a->foo();  // 3: illegal use after end of lifetime
    b->foo();  // 4: okay, can assume object type is still B
  }
Here we happen to be able to prove that 'a' and 'b' have identical values,
but they nonetheless have different properties for this optimization because
'a' doesn't meet the criteria for having been forwarded, whereas 'b' points to
the new object.

Right now, we don't have any good machinery for doing this kind of
language-specific optimization in the backend.  Doing it in the front-end
for your test case would require inter-statement analysis, which we've tried
to avoid in clang.

So I think the best bet for this optimization for now is to do it based on the
knowledge that printf doesn't modify that particular argument.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101011/ee16db77/attachment.html>