WholeProgramDevirt: generate more detailed and accurate remarks.

[krasin]

Summary

Keep track of all methods for which we have devirtualized at least
one call and then print them sorted alphabetically. That allows to
avoid duplicates and also makes the order deterministic.

Add optimization names into the remarks, so that it's easier to
understand how has each method been devirtualized.

Fix a bug when wrong methods could have been reported for
tryVirtualConstProp.

[krasin]

fix a typo (simple->single); simplify a condition; sync

[mehdi_amini]

Hey Ivan, thanks for following up on this!
Some quick comments inlined.

lib/Transforms/IPO/WholeProgramDevirt.cpp

225

I don't think you need the explicit Twine() around the literal string.

824

I don't think we'd like to create a map when reporting is disabled though. And I don't know if we can detect that actually.

Anyway, if we'd go with a container here, why a map instead of a DenseSet<Function *>?

834–836

No need for braces here.

837

&&T? Why not const auto &T?

[krasin]

Address comments.

lib/Transforms/IPO/WholeProgramDevirt.cpp

824

Yes, I share the same concern. Initially I tried to avoid having a map at all, but that produces too many duplicates, and no better than having a map.

Then I decided to go with a map, and while I also don't know a good way to check if remarks are enabled, it's certainly possible to make one. At the same time, before we go deep into this hole, I would like to actually see how much time does this pass take on the large targets (like Chrome) with and without the map. If profile shows that we considerably slowdown the pass, then we'll find a way to detect -pass-remarks=wholeprogramdevirt.

As for using DenseSet<Function*>: it does not have any guarantees about iterating order, and I would like to have a stable output. Certainly, it's possible to use DenseMap, then sort, but that feels like a premature optimization at this point.

Theoretically I could use std::set<Function*> with a comparator. That would save memory a little bit.

I am very open to your ideas here, especially, given that I am not yet native to LLVM, and don't have a map of LLVM collections types in my head, only http://llvm.org/docs/ProgrammersManual.html

837

In this particular place, no good reason. Done.

In other places, where I modify T.WasDevirt, I tried to be consistent with the rest of the code.

[krasin]

test/Transforms/WholeProgramDevirt/virtual-const-prop-check.ll

6

One thing that I want to include into this change, but didn't have time to work on this yet, is to also check the line numbers reported by the remarks. Just an FYI that the change will get an update into the tests.

[krasin]

Add line numbers into a test

[krasin]

Mehdi,

please, take another look.

test/Transforms/WholeProgramDevirt/virtual-const-prop-check.ll

6–11

I have added debug info and checks for the line numbers into one of the tests. I think it's reasonable to only do it once, as debug metadata adds quite a bit of a low value / high noise info.

[krasin]

Mehdi,

please, take another look.

lib/Transforms/IPO/WholeProgramDevirt.cpp

824

I have some numbers to share. Whole program devirtualization pass takes 1.4 sec / 0.1% of the time when linking Chrome. This includes collecting and generating all the remarks in this CL.

Most of the time is spent on the real work; I might also collect the same stats without the patch applied, but it's probably not worth it. There's not much we can save here.

[mehdi_amini]

I'm bothered by doing work that will be thrown away in *most* cases (i.e. -pass-remark is "rare"), this is the path of slowly but surely bloating the compiler as whole.

Talked to Chandler on IRC and he shared the same impression I don't find the argument that "the rest of the thing is too slow" to be compelling that we should do work that gets thrown away.

lib/Transforms/IPO/WholeProgramDevirt.cpp

838–848

One line comment for this loop.

843

const auto &?
Also one line comment before the loop.

[mehdi_amini]

Note: for the ThinLTO import/inline statistics, I think we are controlling this as a cl::opt.

[krasin]

Thank you for the hint. I will take a look at ThinLTO statistics and try to add a switch to these remarks too.

Note: I appreciate getting a useful feedback on the priorities of the LLVM project. The very same question might be answered differently in different projects. Thank you for correcting me, and please continue to do so when you feel my judgement is not aligned with the rest of the team.

[krasin]

Only collect stats if remarks are enabled for the pass.

[krasin]

Hi Mehdi,

I have added checks to avoid doing unnecessary work. Please, take a look.

[mehdi_amini]

LGTM.

lib/Transforms/IPO/WholeProgramDevirt.cpp

679

Interesting, I didn't know about that.

[krasin]

Mehdi,

thank you for your review!

And huge thanks for spotting bugs in my previous CL that introduces these remarks.

lib/Transforms/IPO/WholeProgramDevirt.cpp

679

It was surprisingly quick to discover using Peter's http://llvm-cs.pcc.me.uk (or may be I was just lucky)

[mehdi_amini]

r278389

include/llvm/Transforms/IPO/WholeProgramDevirt.h

struct VirtualCallTarget {
 
   // When doing virtual constant propagation, this stores the return value for
   // the function when passed the currently considered argument list.
   uint64_t RetVal;
 
   // Whether the target is big endian.
   bool IsBigEndian;
 
+  // Whether at least one call site to the target was devirtualized.
+  bool WasDevirt;
+
   // The minimum byte offset before the address point. This covers the bytes in
   // the vtable object before the address point (e.g. RTTI, access-to-top,
   // vtables for other base classes) and is equal to the offset from the start
   // of the vtable object to the address point.
   uint64_t minBeforeBytes() const { return TM->Offset; }
 
   // The minimum byte offset after the address point. This covers the bytes in
   // the vtable object after the address point (e.g. the vtable for the current

lib/Transforms/IPO/WholeProgramDevirt.cpp

struct VirtualCallSite {
   Value *VTable;
   CallSite CS;
 
   // If non-null, this field points to the associated unsafe use count stored in
   // the DevirtModule::NumUnsafeUsesForTypeTest map below. See the description
   // of that field for details.
   unsigned *NumUnsafeUses;
 
-  void emitRemark() {
+  void emitRemark(const Twine &OptName, const Twine &TargetName) {
     Function *F = CS.getCaller();
-    emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F,
-                           CS.getInstruction()->getDebugLoc(),
-                           "devirtualized call");
+    emitOptimizationRemark(
+        F->getContext(), DEBUG_TYPE, *F,
+        OptName + ": devirtualized a call to " + TargetName);
   }
 
-  void replaceAndErase(Value *New) {
-    emitRemark();
+  void replaceAndErase(const Twine &OptName, const Twine &TargetName, Value *New) {
+    emitRemark(OptName, TargetName);
     CS->replaceAllUsesWith(New);
     if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
       BranchInst::Create(II->getNormalDest(), CS.getInstruction());
       II->getUnwindDest()->removePredecessor(II->getParent());
     }
     CS->eraseFromParent();
     // This use is no longer unsafe.
     if (NumUnsafeUses)
struct DevirtModule {
 
   void buildTypeIdentifierMap(
       std::vector<VTableBits> &Bits,
       DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
   bool
   tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
                             const std::set<TypeMemberInfo> &TypeMemberInfos,
                             uint64_t ByteOffset);
-  bool trySingleImplDevirt(ArrayRef<VirtualCallTarget> TargetsForSlot,
+  bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            MutableArrayRef<VirtualCallSite> CallSites);
   bool tryEvaluateFunctionsWithArgs(
       MutableArrayRef<VirtualCallTarget> TargetsForSlot,
       ArrayRef<ConstantInt *> Args);
   bool tryUniformRetValOpt(IntegerType *RetType,
-                           ArrayRef<VirtualCallTarget> TargetsForSlot,
+                           MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            MutableArrayRef<VirtualCallSite> CallSites);
   bool tryUniqueRetValOpt(unsigned BitWidth,
-                          ArrayRef<VirtualCallTarget> TargetsForSlot,
+                          MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                           MutableArrayRef<VirtualCallSite> CallSites);
   bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            ArrayRef<VirtualCallSite> CallSites);
 
   void rebuildGlobal(VTableBits &B);
 
   bool run();
 };
for (const TypeMemberInfo &TM : TypeMemberInfos) {
     TargetsForSlot.push_back({Fn, &TM});
   }
 
   // Give up if we couldn't find any targets.
   return !TargetsForSlot.empty();
 }
 
 bool DevirtModule::trySingleImplDevirt(
-    ArrayRef<VirtualCallTarget> TargetsForSlot,
+    MutableArrayRef<VirtualCallTarget> TargetsForSlot,
     MutableArrayRef<VirtualCallSite> CallSites) {
   // See if the program contains a single implementation of this virtual
   // function.
   Function *TheFn = TargetsForSlot[0].Fn;
   for (auto &&Target : TargetsForSlot)
     if (TheFn != Target.Fn)
       return false;
 
+  TargetsForSlot[0].WasDevirt = true;
   // If so, update each call site to call that implementation directly.
   for (auto &&VCallSite : CallSites) {
-    VCallSite.emitRemark();
+    VCallSite.emitRemark("single-impl", TheFn->getName());
     VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
         TheFn, VCallSite.CS.getCalledValue()->getType()));
     // This use is no longer unsafe.
     if (VCallSite.NumUnsafeUses)
       --*VCallSite.NumUnsafeUses;
   }
   return true;
 }
if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
         !isa<ConstantInt>(RetVal))
       return false;
     Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
   }
   return true;
 }
 
 bool DevirtModule::tryUniformRetValOpt(
-    IntegerType *RetType, ArrayRef<VirtualCallTarget> TargetsForSlot,
+    IntegerType *RetType, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
     MutableArrayRef<VirtualCallSite> CallSites) {
   // Uniform return value optimization. If all functions return the same
   // constant, replace all calls with that constant.
   uint64_t TheRetVal = TargetsForSlot[0].RetVal;
   for (const VirtualCallTarget &Target : TargetsForSlot)
     if (Target.RetVal != TheRetVal)
       return false;
 
   auto TheRetValConst = ConstantInt::get(RetType, TheRetVal);
   for (auto Call : CallSites)
-    Call.replaceAndErase(TheRetValConst);
+    Call.replaceAndErase("uniform-ret-val", TargetsForSlot[0].Fn->getName(),
+                         TheRetValConst);
+  for (auto &&Target : TargetsForSlot)
+    Target.WasDevirt = true;
   return true;
 }
 
 bool DevirtModule::tryUniqueRetValOpt(
-    unsigned BitWidth, ArrayRef<VirtualCallTarget> TargetsForSlot,
+    unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
     MutableArrayRef<VirtualCallSite> CallSites) {
   // IsOne controls whether we look for a 0 or a 1.
   auto tryUniqueRetValOptFor = [&](bool IsOne) {
     const TypeMemberInfo *UniqueMember = 0;
     for (const VirtualCallTarget &Target : TargetsForSlot) {
       if (Target.RetVal == (IsOne ? 1 : 0)) {
         if (UniqueMember)
           return false;
         UniqueMember = Target.TM;
       }
     }
 
     // We should have found a unique member or bailed out by now. We already
     // checked for a uniform return value in tryUniformRetValOpt.
     assert(UniqueMember);
 
     // Replace each call with the comparison.
     for (auto &&Call : CallSites) {
       IRBuilder<> B(Call.CS.getInstruction());
       Value *OneAddr = B.CreateBitCast(UniqueMember->Bits->GV, Int8PtrTy);
       OneAddr = B.CreateConstGEP1_64(OneAddr, UniqueMember->Offset);
       Value *Cmp = B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
                                 Call.VTable, OneAddr);
-      Call.replaceAndErase(Cmp);
+      Call.replaceAndErase("unique-ret-val", TargetsForSlot[0].Fn->getName(), Cmp);
     }
+    // Update devirtualization statistics for targets.
+    for (auto &&Target : TargetsForSlot)
+      Target.WasDevirt = true;
+
     return true;
   };
 
   if (BitWidth == 1) {
     if (tryUniqueRetValOptFor(true))
       return true;
     if (tryUniqueRetValOptFor(false))
       return true;
for (auto &&CSByConstantArg : VCallSitesByConstantArg) {
     uint64_t OffsetBit;
     if (TotalPaddingBefore <= TotalPaddingAfter)
       setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
                             OffsetBit);
     else
       setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
                            OffsetBit);
 
+    for (auto &&Target : TargetsForSlot)
+      Target.WasDevirt = true;
+
     // Rewrite each call to a load from OffsetByte/OffsetBit.
     for (auto Call : CSByConstantArg.second) {
       IRBuilder<> B(Call.CS.getInstruction());
       Value *Addr = B.CreateConstGEP1_64(Call.VTable, OffsetByte);
       if (BitWidth == 1) {
         Value *Bits = B.CreateLoad(Addr);
         Value *Bit = ConstantInt::get(Int8Ty, 1ULL << OffsetBit);
         Value *BitsAndBit = B.CreateAnd(Bits, Bit);
         auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
-        Call.replaceAndErase(IsBitSet);
+        Call.replaceAndErase("virtual-const-prop-1-bit",
+                             TargetsForSlot[0].Fn->getName(), IsBitSet);
       } else {
         Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
         Value *Val = B.CreateLoad(RetType, ValAddr);
-        Call.replaceAndErase(Val);
+        Call.replaceAndErase("virtual-const-prop",
+                             TargetsForSlot[0].Fn->getName(), Val);
       }
     }
   }
   return true;
 }
 
-static void emitTargetsRemarks(const std::vector<VirtualCallTarget> &TargetsForSlot) {
-  for (const VirtualCallTarget &Target : TargetsForSlot) {
-    Function *F = Target.Fn;
-    DISubprogram *SP = F->getSubprogram();
-    DebugLoc DL = SP ? DebugLoc::get(SP->getScopeLine(), 0, SP) : DebugLoc();
-    emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, DL,
-                           std::string("devirtualized ") + F->getName().str());
-  }
-}
-
 void DevirtModule::rebuildGlobal(VTableBits &B) {
   if (B.Before.Bytes.empty() && B.After.Bytes.empty())
     return;
 
   // Align each byte array to pointer width.
   unsigned PointerSize = M.getDataLayout().getPointerSize();
   B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), PointerSize));
   B.After.Bytes.resize(alignTo(B.After.Bytes.size(), PointerSize));

 }
 
 void DevirtModule::scanTypeTestUsers(Function *TypeTestFunc,
                                      Function *AssumeFunc) {
   // Find all virtual calls via a virtual table pointer %p under an assumption
   // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p
   // points to a member of the type identifier %md. Group calls by (type ID,
   // offset) pair (effectively the identity of the virtual function) and store
   // to CallSlots.
   DenseSet<Value *> SeenPtrs;
   for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end();
        I != E;) {
     auto CI = dyn_cast<CallInst>(I->getUser());
     ++I;
     if (!CI)
       continue;
 
bool DevirtModule::run() {
   std::vector<VTableBits> Bits;
   DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
   buildTypeIdentifierMap(Bits, TypeIdMap);
   if (TypeIdMap.empty())
     return true;
 
   // For each (type, offset) pair:
   bool DidVirtualConstProp = false;
+  std::map<std::string, Function*> DevirtTargets;
   for (auto &S : CallSlots) {
     // Search each of the members of the type identifier for the virtual
     // function implementation at offset S.first.ByteOffset, and add to
     // TargetsForSlot.
     std::vector<VirtualCallTarget> TargetsForSlot;
     if (!tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
                                    S.first.ByteOffset))
       continue;
 
-    if (trySingleImplDevirt(TargetsForSlot, S.second)) {
-      emitTargetsRemarks(TargetsForSlot);
-      continue;
-    }
-
-    if (tryVirtualConstProp(TargetsForSlot, S.second)) {
-      emitTargetsRemarks(TargetsForSlot);
+    if (!trySingleImplDevirt(TargetsForSlot, S.second) &&
+        tryVirtualConstProp(TargetsForSlot, S.second))
         DidVirtualConstProp = true;
-    }
+
+    for (const auto &T : TargetsForSlot)
+      if (T.WasDevirt)
+        DevirtTargets[T.Fn->getName()] = T.Fn;
+
+  for (auto &DT : DevirtTargets) {
+    Function *F = DT.second;
+    DISubprogram *SP = F->getSubprogram();
+    DebugLoc DL = SP ? DebugLoc::get(SP->getScopeLine(), 0, SP) : DebugLoc();
+    emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, DL,
+                           Twine("devirtualized ") + F->getName());
   }
 
   // If we were able to eliminate all unsafe uses for a type checked load,
   // eliminate the type test by replacing it with true.
   if (TypeCheckedLoadFunc) {
     auto True = ConstantInt::getTrue(M.getContext());
     for (auto &&U : NumUnsafeUsesForTypeTest) {
       if (U.second == 0) {

test/Transforms/WholeProgramDevirt/devirt-single-impl-check.ll

 ; RUN: opt -S -wholeprogramdevirt -pass-remarks=wholeprogramdevirt %s 2>&1 | FileCheck %s
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
-; CHECK: remark: <unknown>:0:0: devirtualized call
-; CHECK-NOT: devirtualized call
+; CHECK: remark: <unknown>:0:0: single-impl: devirtualized a call to vf
+; CHECK: remark: <unknown>:0:0: devirtualized vf
+; CHECK-NOT: devirtualized
 
 @vt1 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0
 @vt2 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0
 
 define void @vf(i8* %this) {
   ret void
 }
 

test/Transforms/WholeProgramDevirt/devirt-single-impl.ll

 ; RUN: opt -S -wholeprogramdevirt -pass-remarks=wholeprogramdevirt %s 2>&1 | FileCheck %s
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
-; CHECK: remark: <unknown>:0:0: devirtualized call
-; CHECK: remark: <unknown>:0:0: devirtualized vf
+; CHECK: remark: <unknown>:0:0: single-impl: devirtualized a call to vf
 ; CHECK: remark: <unknown>:0:0: devirtualized vf
+; CHECK-NOT: devirtualized
 
 @vt1 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0
 @vt2 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0
 
 define void @vf(i8* %this) {
   ret void
 }
 

test/Transforms/WholeProgramDevirt/virtual-const-prop-check.ll

 ; RUN: opt -S -wholeprogramdevirt -pass-remarks=wholeprogramdevirt %s 2>&1 | FileCheck %s
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
-; CHECK: remark: <unknown>:0:0: devirtualized call
+; CHECK: remark: <unknown>:0:0: virtual-const-prop: devirtualized a call to vf1i32
+; CHECK: remark: <unknown>:0:0: virtual-const-prop-1-bit: devirtualized a call to vf1i1
+; CHECK: remark: <unknown>:0:0: virtual-const-prop-1-bit: devirtualized a call to vf0i1
+; CHECK: remark: <unknown>:0:0: devirtualized vf0i1
+; CHECK: remark: <unknown>:0:0: devirtualized vf1i1
 ; CHECK: remark: <unknown>:0:0: devirtualized vf1i32
 ; CHECK: remark: <unknown>:0:0: devirtualized vf2i32
 ; CHECK: remark: <unknown>:0:0: devirtualized vf3i32
 ; CHECK: remark: <unknown>:0:0: devirtualized vf4i32
-; CHECK: remark: <unknown>:0:0: devirtualized call
-; CHECK: remark: <unknown>:0:0: devirtualized vf1i1
-; CHECK: remark: <unknown>:0:0: devirtualized vf0i1
-; CHECK: remark: <unknown>:0:0: devirtualized vf1i1
-; CHECK: remark: <unknown>:0:0: devirtualized vf0i1
-; CHECK: remark: <unknown>:0:0: devirtualized call
-; CHECK: remark: <unknown>:0:0: devirtualized vf0i1
-; CHECK: remark: <unknown>:0:0: devirtualized vf1i1
-; CHECK: remark: <unknown>:0:0: devirtualized vf0i1
-; CHECK: remark: <unknown>:0:0: devirtualized vf1i1
-; CHECK-NOT: devirtualized call
+; CHECK-NOT: devirtualized
 
 ; CHECK: [[VT1DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\01\01\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf1i32 to i8*)], [0 x i8] zeroinitializer }, section "vt1sec", !type [[T8:![0-9]+]]
 @vt1 = constant [3 x i8*] [
 i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
 i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
 i8* bitcast (i32 (i8*)* @vf1i32 to i8*)
 ], section "vt1sec", !type !0