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

404

Document new functions.

1053

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

1058

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

1060

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

1095

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.

1162

This guard went away - why?

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1053

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

1058

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

1095

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).

1162

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

[pcc]

• Address review comments

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1058

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

1058

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);
 
   void rebuildGlobal(VTableBits &B);
 
+  void importResolution(VTableSlotInfo &SlotInfo,
+                        const WholeProgramDevirtResolution &Res);
+
+  void removeUnusedTypeTests();
+
   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(VTableSlotInfo &SlotInfo,
+                                    const WholeProgramDevirtResolution &Res) {
+  if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
+    auto *SingleImpl = M.getOrInsertFunction(
+        Res.SingleImplName, Type::getVoidTy(M.getContext()), nullptr);
+    bool IsExported;
+    applySingleImplDevirt(SlotInfo, SingleImpl, IsExported);
+  }
+}
+
+void DevirtModule::removeUnusedTypeTests() {
+  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));
 
   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) {
+      auto &Res =
+          Summary->getTypeIdSummary(cast<MDString>(S.first.TypeID)->getString())
+              .WPDRes[S.first.ByteOffset];
+      importResolution(S.second, Res);
+    }
+
+    removeUnusedTypeTests();
+    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;
 
   if (Action == PassSummaryAction::Export) {
for (const auto &DT : DevirtTargets) {
       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) {
-        U.first->replaceAllUsesWith(True);
-        U.first->eraseFromParent();
-      }
-    }
-  }
+  removeUnusedTypeTests();
 
   // 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)