Index: llvm/include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- llvm/include/llvm/IR/ModuleSummaryIndex.h +++ llvm/include/llvm/IR/ModuleSummaryIndex.h @@ -407,8 +407,38 @@ unsigned SizeM1BitWidth = 0; }; +struct WholeProgramDevirtResolution { + enum Kind { + Indir, ///< Just do a regular virtual call + SingleImpl, ///< Single implementation devirtualization + } TheKind = Indir; + + std::string SingleImplName; + + struct ByArg { + enum Kind { + Indir, ///< Just do a regular virtual call + UniformRetVal, ///< Uniform return value optimization + UniqueRetVal, ///< Unique return value optimization + VirtualConstProp, ///< Virtual constant propagation + } TheKind = Indir; + + /// Additional information for the resolution: + /// - UniformRetVal: the uniform return value. + /// - UniqueRetVal: the return value associated with the unique vtable (0 or + /// 1). + uint64_t Info = 0; + }; + + std::map, ByArg> ResByArg; +}; + struct TypeIdSummary { TypeTestResolution TTRes; + + /// Mapping from byte offset to whole-program devirt resolution for that + /// (typeid, byte offset) pair. + std::map WPDRes; }; /// 160 bits SHA1 Index: llvm/include/llvm/IR/ModuleSummaryIndexYAML.h =================================================================== --- llvm/include/llvm/IR/ModuleSummaryIndexYAML.h +++ llvm/include/llvm/IR/ModuleSummaryIndexYAML.h @@ -33,14 +33,106 @@ } }; +template <> +struct ScalarEnumerationTraits { + static void enumeration(IO &io, + WholeProgramDevirtResolution::ByArg::Kind &value) { + io.enumCase(value, "Indir", WholeProgramDevirtResolution::ByArg::Indir); + io.enumCase(value, "UniformRetVal", + WholeProgramDevirtResolution::ByArg::UniformRetVal); + io.enumCase(value, "UniqueRetVal", + WholeProgramDevirtResolution::ByArg::UniqueRetVal); + io.enumCase(value, "VirtualConstProp", + WholeProgramDevirtResolution::ByArg::VirtualConstProp); + } +}; + +template <> struct MappingTraits { + static void mapping(IO &io, WholeProgramDevirtResolution::ByArg &res) { + io.mapOptional("Kind", res.TheKind); + io.mapOptional("Info", res.Info); + } +}; + +template <> +struct CustomMappingTraits< + std::map, WholeProgramDevirtResolution::ByArg>> { + static void inputOne( + IO &io, StringRef Key, + std::map, WholeProgramDevirtResolution::ByArg> &V) { + std::vector Args; + std::pair P = {"", Key}; + while (!P.second.empty()) { + P = P.second.split(','); + uint64_t Arg; + if (P.first.getAsInteger(0, Arg)) { + io.setError("key not an integer"); + return; + } + Args.push_back(Arg); + } + io.mapRequired(Key.str().c_str(), V[Args]); + } + static void output( + IO &io, + std::map, WholeProgramDevirtResolution::ByArg> &V) { + for (auto &P : V) { + std::string Key; + for (uint64_t Arg : P.first) { + if (!Key.empty()) + Key += ','; + Key += llvm::utostr(Arg); + } + io.mapRequired(Key.c_str(), P.second); + } + } +}; + +template <> struct ScalarEnumerationTraits { + static void enumeration(IO &io, WholeProgramDevirtResolution::Kind &value) { + io.enumCase(value, "Indir", WholeProgramDevirtResolution::Indir); + io.enumCase(value, "SingleImpl", WholeProgramDevirtResolution::SingleImpl); + } +}; + +template <> struct MappingTraits { + static void mapping(IO &io, WholeProgramDevirtResolution &res) { + io.mapOptional("Kind", res.TheKind); + io.mapOptional("SingleImplName", res.SingleImplName); + io.mapOptional("ResByArg", res.ResByArg); + } +}; + +template <> +struct CustomMappingTraits> { + static void inputOne(IO &io, StringRef Key, + std::map &V) { + uint64_t KeyInt; + if (Key.getAsInteger(0, KeyInt)) { + io.setError("key not an integer"); + return; + } + io.mapRequired(Key.str().c_str(), V[KeyInt]); + } + static void output(IO &io, std::map &V) { + for (auto &P : V) + io.mapRequired(llvm::utostr(P.first).c_str(), P.second); + } +}; + template <> struct MappingTraits { static void mapping(IO &io, TypeIdSummary& summary) { io.mapOptional("TTRes", summary.TTRes); + io.mapOptional("WPDRes", summary.WPDRes); } }; struct FunctionSummaryYaml { std::vector TypeTests; + std::vector TypeTestAssumeVCalls, + TypeCheckedLoadVCalls; + std::vector TypeTestAssumeConstVCalls, + TypeCheckedLoadConstVCalls; }; } // End yaml namespace @@ -51,9 +143,38 @@ namespace llvm { namespace yaml { +template <> struct MappingTraits { + static void mapping(IO &io, FunctionSummary::VFuncId& id) { + io.mapOptional("GUID", id.GUID); + io.mapOptional("Offset", id.Offset); + } +}; + +template <> struct MappingTraits { + static void mapping(IO &io, FunctionSummary::ConstVCall& id) { + io.mapOptional("VFunc", id.VFunc); + io.mapOptional("Args", id.Args); + } +}; + +} // End yaml namespace +} // End llvm namespace + +LLVM_YAML_IS_SEQUENCE_VECTOR(FunctionSummary::VFuncId) +LLVM_YAML_IS_SEQUENCE_VECTOR(FunctionSummary::ConstVCall) + +namespace llvm { +namespace yaml { + template <> struct MappingTraits { static void mapping(IO &io, FunctionSummaryYaml& summary) { io.mapOptional("TypeTests", summary.TypeTests); + io.mapOptional("TypeTestAssumeVCalls", summary.TypeTestAssumeVCalls); + io.mapOptional("TypeCheckedLoadVCalls", summary.TypeCheckedLoadVCalls); + io.mapOptional("TypeTestAssumeConstVCalls", + summary.TypeTestAssumeConstVCalls); + io.mapOptional("TypeCheckedLoadConstVCalls", + summary.TypeCheckedLoadConstVCalls); } }; @@ -83,10 +204,10 @@ Elem.push_back(llvm::make_unique( GVFlags, 0, ArrayRef{}, ArrayRef{}, std::move(FSum.TypeTests), - ArrayRef{}, - ArrayRef{}, - ArrayRef{}, - ArrayRef{})); + std::move(FSum.TypeTestAssumeVCalls), + std::move(FSum.TypeCheckedLoadVCalls), + std::move(FSum.TypeTestAssumeConstVCalls), + std::move(FSum.TypeCheckedLoadConstVCalls))); } } static void output(IO &io, GlobalValueSummaryMapTy &V) { @@ -94,7 +215,11 @@ std::vector FSums; for (auto &Sum : P.second) { if (auto *FSum = dyn_cast(Sum.get())) - FSums.push_back(FunctionSummaryYaml{FSum->type_tests()}); + FSums.push_back(FunctionSummaryYaml{ + FSum->type_tests(), FSum->type_test_assume_vcalls(), + FSum->type_checked_load_vcalls(), + FSum->type_test_assume_const_vcalls(), + FSum->type_checked_load_const_vcalls()}); } if (!FSums.empty()) io.mapRequired(llvm::utostr(P.first).c_str(), FSums); Index: llvm/include/llvm/Transforms/IPO.h =================================================================== --- llvm/include/llvm/Transforms/IPO.h +++ llvm/include/llvm/Transforms/IPO.h @@ -235,7 +235,8 @@ /// \brief This pass implements whole-program devirtualization using type /// metadata. -ModulePass *createWholeProgramDevirtPass(); +ModulePass *createWholeProgramDevirtPass(PassSummaryAction Action, + ModuleSummaryIndex *Index); /// This pass splits globals into pieces for the benefit of whole-program /// devirtualization and control-flow integrity. Index: llvm/lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -700,7 +700,8 @@ PM.add(createGlobalSplitPass()); // Apply whole-program devirtualization and virtual constant propagation. - PM.add(createWholeProgramDevirtPass()); + PM.add(createWholeProgramDevirtPass( + Summary ? PassSummaryAction::Export : PassSummaryAction::None, Summary)); // That's all we need at opt level 1. if (OptLevel == 1) Index: llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp =================================================================== --- llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp +++ llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp @@ -54,10 +54,13 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" +#include "llvm/IR/ModuleSummaryIndexYAML.h" #include "llvm/Pass.h" #include "llvm/PassRegistry.h" #include "llvm/PassSupport.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/FileSystem.h" #include "llvm/Support/MathExtras.h" #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/Utils/Evaluator.h" @@ -72,6 +75,26 @@ #define DEBUG_TYPE "wholeprogramdevirt" +static cl::opt ClSummaryAction( + "wholeprogramdevirt-summary-action", + cl::desc("What to do with the summary when running this pass"), + cl::values(clEnumValN(PassSummaryAction::None, "none", "Do nothing"), + clEnumValN(PassSummaryAction::Import, "import", + "Import typeid resolutions from summary and globals"), + clEnumValN(PassSummaryAction::Export, "export", + "Export typeid resolutions to summary and globals")), + cl::Hidden); + +static cl::opt ClReadSummary( + "wholeprogramdevirt-read-summary", + cl::desc("Read summary from given YAML file before running pass"), + cl::Hidden); + +static cl::opt ClWriteSummary( + "wholeprogramdevirt-write-summary", + cl::desc("Write summary to given YAML file after running pass"), + cl::Hidden); + // Find the minimum offset that we may store a value of size Size bits at. If // IsAfter is set, look for an offset before the object, otherwise look for an // offset after the object. @@ -294,6 +317,10 @@ struct DevirtModule { Module &M; + + PassSummaryAction Action; + ModuleSummaryIndex *Summary; + IntegerType *Int8Ty; PointerType *Int8PtrTy; IntegerType *Int32Ty; @@ -313,8 +340,9 @@ // true. std::map NumUnsafeUsesForTypeTest; - DevirtModule(Module &M) - : M(M), Int8Ty(Type::getInt8Ty(M.getContext())), + DevirtModule(Module &M, PassSummaryAction Action, ModuleSummaryIndex *Summary) + : M(M), Action(Action), Summary(Summary), + Int8Ty(Type::getInt8Ty(M.getContext())), Int8PtrTy(Type::getInt8PtrTy(M.getContext())), Int32Ty(Type::getInt32Ty(M.getContext())), Int64Ty(Type::getInt64Ty(M.getContext())), @@ -361,20 +389,35 @@ void rebuildGlobal(VTableBits &B); bool run(); + + // Lower the module using the action and summary passed as command line + // arguments. For testing purposes only. + static bool runForTesting(Module &M); }; struct WholeProgramDevirt : public ModulePass { static char ID; - WholeProgramDevirt() : ModulePass(ID) { + bool UseCommandLine = false; + + PassSummaryAction Action; + ModuleSummaryIndex *Summary; + + WholeProgramDevirt() : ModulePass(ID), UseCommandLine(true) { + initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry()); + } + + WholeProgramDevirt(PassSummaryAction Action, ModuleSummaryIndex *Summary) + : ModulePass(ID), Action(Action), Summary(Summary) { initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry()); } bool runOnModule(Module &M) override { if (skipModule(M)) return false; - - return DevirtModule(M).run(); + if (UseCommandLine) + return DevirtModule::runForTesting(M); + return DevirtModule(M, Action, Summary).run(); } }; @@ -384,17 +427,50 @@ "Whole program devirtualization", false, false) char WholeProgramDevirt::ID = 0; -ModulePass *llvm::createWholeProgramDevirtPass() { - return new WholeProgramDevirt; +ModulePass *llvm::createWholeProgramDevirtPass(PassSummaryAction Action, + ModuleSummaryIndex *Summary) { + return new WholeProgramDevirt(Action, Summary); } PreservedAnalyses WholeProgramDevirtPass::run(Module &M, ModuleAnalysisManager &) { - if (!DevirtModule(M).run()) + if (!DevirtModule(M, PassSummaryAction::None, nullptr).run()) return PreservedAnalyses::all(); return PreservedAnalyses::none(); } +bool DevirtModule::runForTesting(Module &M) { + ModuleSummaryIndex Summary; + + // Handle the command-line summary arguments. This code is for testing + // purposes only, so we handle errors directly. + if (!ClReadSummary.empty()) { + ExitOnError ExitOnErr("-wholeprogramdevirt-read-summary: " + ClReadSummary + + ": "); + auto ReadSummaryFile = + ExitOnErr(errorOrToExpected(MemoryBuffer::getFile(ClReadSummary))); + + yaml::Input In(ReadSummaryFile->getBuffer()); + In >> Summary; + ExitOnErr(errorCodeToError(In.error())); + } + + bool Changed = DevirtModule(M, ClSummaryAction, &Summary).run(); + + if (!ClWriteSummary.empty()) { + ExitOnError ExitOnErr( + "-wholeprogramdevirt-write-summary: " + ClWriteSummary + ": "); + std::error_code EC; + raw_fd_ostream OS(ClWriteSummary, EC, sys::fs::F_Text); + ExitOnErr(errorCodeToError(EC)); + + yaml::Output Out(OS); + Out << Summary; + } + + return Changed; +} + void DevirtModule::buildTypeIdentifierMap( std::vector &Bits, DenseMap> &TypeIdMap) { Index: llvm/test/Transforms/LowerTypeTests/export-allones.ll =================================================================== --- llvm/test/Transforms/LowerTypeTests/export-allones.ll +++ llvm/test/Transforms/LowerTypeTests/export-allones.ll @@ -153,7 +153,9 @@ ; SUMMARY-NEXT: TTRes: ; SUMMARY-NEXT: Kind: AllOnes ; SUMMARY-NEXT: SizeM1BitWidth: 7 +; SUMMARY-NEXT: WPDRes: ; SUMMARY-NEXT: typeid2: ; SUMMARY-NEXT: TTRes: ; SUMMARY-NEXT: Kind: AllOnes ; SUMMARY-NEXT: SizeM1BitWidth: 32 +; SUMMARY-NEXT: WPDRes: Index: llvm/test/Transforms/LowerTypeTests/export-bytearray.ll =================================================================== --- llvm/test/Transforms/LowerTypeTests/export-bytearray.ll +++ llvm/test/Transforms/LowerTypeTests/export-bytearray.ll @@ -32,7 +32,9 @@ ; SUMMARY-NEXT: TTRes: ; SUMMARY-NEXT: Kind: ByteArray ; SUMMARY-NEXT: SizeM1BitWidth: 7 +; SUMMARY-NEXT: WPDRes: ; SUMMARY-NEXT: typeid2: ; SUMMARY-NEXT: TTRes: ; SUMMARY-NEXT: Kind: ByteArray ; SUMMARY-NEXT: SizeM1BitWidth: 32 +; SUMMARY-NEXT: WPDRes: Index: llvm/test/Transforms/LowerTypeTests/export-inline.ll =================================================================== --- llvm/test/Transforms/LowerTypeTests/export-inline.ll +++ llvm/test/Transforms/LowerTypeTests/export-inline.ll @@ -27,7 +27,9 @@ ; SUMMARY-NEXT: TTRes: ; SUMMARY-NEXT: Kind: Inline ; SUMMARY-NEXT: SizeM1BitWidth: 5 +; SUMMARY-NEXT: WPDRes: ; SUMMARY-NEXT: typeid2: ; SUMMARY-NEXT: TTRes: ; SUMMARY-NEXT: Kind: Inline ; SUMMARY-NEXT: SizeM1BitWidth: 6 +; SUMMARY-NEXT: WPDRes: Index: llvm/test/Transforms/WholeProgramDevirt/Inputs/import-indir.yaml =================================================================== --- /dev/null +++ llvm/test/Transforms/WholeProgramDevirt/Inputs/import-indir.yaml @@ -0,0 +1,41 @@ +--- +GlobalValueMap: + 42: + - TypeTestAssumeVCalls: + - GUID: 123 + Offset: 0 + - GUID: 456 + Offset: 4 + TypeCheckedLoadVCalls: + - GUID: 789 + Offset: 8 + - GUID: 1234 + Offset: 16 + TypeTestAssumeConstVCalls: + - VFunc: + GUID: 123 + Offset: 4 + Args: [12, 24] + TypeCheckedLoadConstVCalls: + - VFunc: + GUID: 456 + Offset: 8 + Args: [24, 12] +TypeIdMap: + typeid1: + WPDRes: + 0: + Kind: Indir + 4: + Kind: Indir + ResByArg: + "": + Kind: UniformRetVal + Info: 12 + 12: + Kind: UniformRetVal + Info: 24 + "12,24": + Kind: UniformRetVal + Info: 48 +... Index: llvm/test/Transforms/WholeProgramDevirt/export-nothing.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/WholeProgramDevirt/export-nothing.ll @@ -0,0 +1,7 @@ +; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-write-summary=%t -o /dev/null %s +; RUN: FileCheck %s < %t + +; CHECK: --- +; CHECK-NEXT: GlobalValueMap: +; CHECK-NEXT: TypeIdMap: +; CHECK-NEXT: ... Index: llvm/test/Transforms/WholeProgramDevirt/import-indir.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/WholeProgramDevirt/import-indir.ll @@ -0,0 +1,99 @@ +; Test that we correctly import an indir resolution for type identifier "typeid1". +; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-indir.yaml -wholeprogramdevirt-write-summary=%t < %s | FileCheck %s +; RUN: FileCheck --check-prefix=SUMMARY %s < %t + +; SUMMARY: GlobalValueMap: +; SUMMARY-NEXT: 42: +; SUMMARY-NEXT: - TypeTests: +; SUMMARY-NEXT: TypeTestAssumeVCalls: +; SUMMARY-NEXT: - GUID: 123 +; SUMMARY-NEXT: Offset: 0 +; SUMMARY-NEXT: - GUID: 456 +; SUMMARY-NEXT: Offset: 4 +; SUMMARY-NEXT: TypeCheckedLoadVCalls: +; SUMMARY-NEXT: - GUID: 789 +; SUMMARY-NEXT: Offset: 8 +; SUMMARY-NEXT: - GUID: 1234 +; SUMMARY-NEXT: Offset: 16 +; SUMMARY-NEXT: TypeTestAssumeConstVCalls: +; SUMMARY-NEXT: - VFunc: +; SUMMARY-NEXT: GUID: 123 +; SUMMARY-NEXT: Offset: 4 +; SUMMARY-NEXT: Args: +; SUMMARY-NEXT: - 12 +; SUMMARY-NEXT: - 24 +; SUMMARY-NEXT: TypeCheckedLoadConstVCalls: +; SUMMARY-NEXT: - VFunc: +; SUMMARY-NEXT: GUID: 456 +; SUMMARY-NEXT: Offset: 8 +; SUMMARY-NEXT: Args: +; SUMMARY-NEXT: - 24 +; SUMMARY-NEXT: - 12 +; SUMMARY-NEXT: TypeIdMap: +; SUMMARY-NEXT: typeid1: +; SUMMARY-NEXT: TTRes: +; SUMMARY-NEXT: Kind: Unsat +; SUMMARY-NEXT: SizeM1BitWidth: 0 +; SUMMARY-NEXT: WPDRes: +; SUMMARY-NEXT: 0: +; SUMMARY-NEXT: Kind: Indir +; SUMMARY-NEXT: SingleImplName: '' +; SUMMARY-NEXT: ResByArg: +; SUMMARY-NEXT: 4: +; SUMMARY-NEXT: Kind: Indir +; SUMMARY-NEXT: SingleImplName: '' +; SUMMARY-NEXT: ResByArg: +; SUMMARY-NEXT: : +; SUMMARY-NEXT: Kind: UniformRetVal +; SUMMARY-NEXT: Info: 12 +; SUMMARY-NEXT: 12: +; SUMMARY-NEXT: Kind: UniformRetVal +; SUMMARY-NEXT: Info: 24 +; SUMMARY-NEXT: 12,24: +; SUMMARY-NEXT: Kind: UniformRetVal +; SUMMARY-NEXT: Info: 48 + +target datalayout = "e-p:32:32" + +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) + +; CHECK: define i1 @f1 +define i1 @f1(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* + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid1") + call void @llvm.assume(i1 %p) + %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 + %fptr = load i8*, i8** %fptrptr + %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)* + ; CHECK: call i1 % + %result = call i1 %fptr_casted(i8* %obj, i32 5) + ret i1 %result +} + +; CHECK: define i1 @f2 +define i1 @f2(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 4, metadata !"typeid1") + %fptr = extractvalue {i8*, i1} %pair, 0 + %p = extractvalue {i8*, i1} %pair, 1 + ; CHECK: [[P:%.*]] = call i1 @llvm.type.test + ; CHECK: br i1 [[P]] + br i1 %p, label %cont, label %trap + +cont: + %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)* + ; CHECK: call i1 % + %result = call i1 %fptr_casted(i8* %obj, i32 undef) + ret i1 %result + +trap: + call void @llvm.trap() + unreachable +}