WholeProgramDevirt: Implement importing for single-impl devirtualization.

[pcc]

Summary

Depends on D29811

[pcc]

• Change the signature of importResolution for an upcoming change

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

448

Document new functions.

1115

On the export side there were checks on whether TypeID was an MDString, needed here too?

1120

I forget - is there a constraint that the single implementation function return void and not take any args?

1122

I assume IsExported should never be true since we invoke this on import? Should that be checked?

1168

Why can we skip the rest of the function in import mode? E.g. we won't get an optimization remark emitted. Or is the rest of the code only necessary on the export side? Needs a comment at least.

1228

This guard went away - why?

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1115

No, on the import side all type IDs are MDStrings (ensured by ThinLTOBitcodeWriter).

1120

The type of the function in the declaration is irrelevant because every call site will cast it to the correct type. Added comment.

1168

Yes, the rest of the code is only necessary on the export side or during regular LTO (the remarks as well -- the export phase will emit remarks for the whole program).

1228

It is unnecessary. The map NumUnsafeUsesForTypeTest will be empty if TypeCheckedLoadFunc is null.

[pcc]

• Address review comments

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1120

I suppose you could get the correct type then from the IR? Not sure if there is any benefit though...

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1120

Not really. The FunctionType of a declaration is completely unused (or at least it ought to be).

There's also not necessarily one "correct" type because there may be multiple call sites and each call site may use a different type for "this".

This is one of the reasons why I would like to see FunctionType removed.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

struct DevirtModule {
   void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
                              Constant *Byte, Constant *Bit);
   bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            VTableSlotInfo &SlotInfo,
                            WholeProgramDevirtResolution *Res);
 
   void rebuildGlobal(VTableBits &B);
 
+  // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
+  void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
+
+  // If we were able to eliminate all unsafe uses for a type checked load,
+  // eliminate the associated type tests by replacing them with true.
+  void removeRedundantTypeTests();
+
   bool run();
 
   // Lower the module using the action and summary passed as command line
   // arguments. For testing purposes only.
   static bool runForTesting(Module &M,
                             function_ref<AAResults &(Function &)> AARGetter);
 };
 
for (DevirtCallSite Call : DevirtCalls) {
       CallSlots[{TypeId, Call.Offset}].addCallSite(Ptr, Call.CS,
                                                    &NumUnsafeUses);
     }
 
     CI->eraseFromParent();
   }
 }
 
+void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
+  const WholeProgramDevirtResolution &Res =
+      Summary->getTypeIdSummary(cast<MDString>(Slot.TypeID)->getString())
+          .WPDRes[Slot.ByteOffset];
+
+  if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
+    // The type of the function in the declaration is irrelevant because every
+    // call site will cast it to the correct type.
+    auto *SingleImpl = M.getOrInsertFunction(
+        Res.SingleImplName, Type::getVoidTy(M.getContext()), nullptr);
+
+    // This is the import phase so we should not be exporting anything.
+    bool IsExported = false;
+    applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
+    assert(!IsExported);
+  }
+}
+
+void DevirtModule::removeRedundantTypeTests() {
+  auto True = ConstantInt::getTrue(M.getContext());
+  for (auto &&U : NumUnsafeUsesForTypeTest) {
+    if (U.second == 0) {
+      U.first->replaceAllUsesWith(True);
+      U.first->eraseFromParent();
+    }
+  }
+}
+
 bool DevirtModule::run() {
   Function *TypeTestFunc =
       M.getFunction(Intrinsic::getName(Intrinsic::type_test));
   Function *TypeCheckedLoadFunc =
       M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
   Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
 
   // Normally if there are no users of the devirtualization intrinsics in the
   // module, this pass has nothing to do. But if we are exporting, we also need
   // to handle any users that appear only in the function summaries.
   if (Action != PassSummaryAction::Export &&
       (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
        AssumeFunc->use_empty()) &&
       (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
     return false;
 
   if (TypeTestFunc && AssumeFunc)
     scanTypeTestUsers(TypeTestFunc, AssumeFunc);
 
   if (TypeCheckedLoadFunc)
     scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
 
+  if (Action == PassSummaryAction::Import) {
+    for (auto &S : CallSlots)
+      importResolution(S.first, S.second);
+
+    removeRedundantTypeTests();
+
+    // The rest of the code is only necessary when exporting or during regular
+    // LTO, so we are done.
+    return true;
+  }
+
   // Rebuild type metadata into a map for easy lookup.
   std::vector<VTableBits> Bits;
   DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
   buildTypeIdentifierMap(Bits, TypeIdMap);
   if (TypeIdMap.empty())
     return true;
 
   // Collect information from summary about which calls to try to devirtualize.
if (RemarksEnabled) {
     for (const auto &DT : DevirtTargets) {
       Function *F = DT.second;
       DISubprogram *SP = F->getSubprogram();
       emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, SP,
                              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) {
-        U.first->replaceAllUsesWith(True);
-        U.first->eraseFromParent();
-      }
-    }
-  }
+  removeRedundantTypeTests();
 
   // Rebuild each global we touched as part of virtual constant propagation to
   // include the before and after bytes.
   if (DidVirtualConstProp)
     for (VTableBits &B : Bits)
       rebuildGlobal(B);
 
   return true;
 }

llvm/test/Transforms/WholeProgramDevirt/Inputs/import-single-impl.yaml

+---
+TypeIdMap:
+  typeid1:
+    WPDRes:
+      0:
+        Kind: SingleImpl
+        SingleImplName: singleimpl1
+  typeid2:
+    WPDRes:
+      8:
+        Kind: SingleImpl
+        SingleImplName: singleimpl2
+...

llvm/test/Transforms/WholeProgramDevirt/import.ll

+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-single-impl.yaml < %s | FileCheck --check-prefixes=CHECK,SINGLE-IMPL %s
+
+target datalayout = "e-p:64:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+; CHECK: define i32 @call1
+define i32 @call1(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid1")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; SINGLE-IMPL: call i32 bitcast (void ()* @singleimpl1 to i32 (i8*, i32)*)
+  %result = call i32 %fptr_casted(i8* %obj, i32 1)
+  ret i32 %result
+}
+
+; CHECK: define i1 @call2
+define i1 @call2(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %pair = call {i8*, i1} @llvm.type.checked.load(i8* %vtablei8, i32 8, metadata !"typeid2")
+  %fptr = extractvalue {i8*, i1} %pair, 0
+  %p = extractvalue {i8*, i1} %pair, 1
+  ; SINGLE-IMPL: br i1 true,
+  br i1 %p, label %cont, label %trap
+
+cont:
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
+  ; SINGLE-IMPL: call i1 bitcast (void ()* @singleimpl2 to i1 (i8*, i32)*)
+  %result = call i1 %fptr_casted(i8* %obj, i32 undef)
+  ret i1 %result
+
+trap:
+  call void @llvm.trap()
+  unreachable
+}
+
+; SINGLE-IMPL-DAG: declare void @singleimpl1()
+; SINGLE-IMPL-DAG: declare void @singleimpl2()
+
+declare void @llvm.assume(i1)
+declare void @llvm.trap()
+declare {i8*, i1} @llvm.type.checked.load(i8*, i32, metadata)
+declare i1 @llvm.type.test(i8*, metadata)