[LLVMdev] "load groups" IR feature to improve C++ devirtualization

[Nick Lewycky]

I'm looking into how we can improve devirtualization in clang, and there a
language in C++ feature I'd like to take advantage of which would let us
perform elimination of more vptr loads. In this code:

  Cls *p = new Cls;
  p->virtual_method1();
  p->method_changing_vptr();  // uses placement new to legally change the
vptr
  p->virtual_method2();  // invalid!
  Cls *q = p;
  q->virtual_method2();  // this must get a new vptr lookup.

there is no need to reload p's vptr, even if the method did update the vptr.

C++ [basic.life] gives us a guarantee that a pointer will only update to
point to a new object allocated at the same place in memory under certain
circumstances. If the C++ code uses the same pointer, reference or name to
refer to the object, then we can prove that the vptr and any const members
did not change.

I'd like clang to compute whether a load is eligible for this treatment per
the rules in C++, and encode that in LLVM IR for further optimization.
(Note that this is different from @llvm.invariant because
method_changing_vptr_through_placement_new may be inlined and is required
to see the updated vptr.)

To implement this, I propose a new intrinsic in LLVM:

  declare {}* @llvm.load.group()

and new metadata on loads:

  !load.group %group

where %group must be the result of a call to llvm.load.group. Any two loads
with the same %group value are known to produce the same value. We can then
choose to eliminate the latter of the loads as redundant in GVN, or in the
event of high register pressure we could choose to reload without spilling
to the stack.

For clang, let us say that two expressions E1 and E2 of the same type
denote the same value if:

 * E1 and E2 both name the same variable, which is either of class or
reference-to-class type or const pointer-to-class type, or is of non-const
pointer type and is known to have not changed between the evaluations of E1
and E2. (By introductory text in [basic.life]).
 * E1 and E2 are of the form E3.x and E4.x, or E3->x and E4->x, or E3[x]
and E4[x], for the same x, and E3 and E4 denote the same value, and the
denoted subobject either has a const-qualified type or is a reference. (By
bullet 3, ibid).
 * (Fudging a bit on E1 and E2 being expressions...) E1 and E2 are both
references to the same vptr slot. (By bullet 2 or 4, ibid).

Let me know if you think this design can be improved, or if there are cases
it doesn't handle (or gets wrong). An explicit non-goal is the "constructor
not defined in TU" problem.

Nick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130509/f4728a42/attachment.html>