//===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This pass implements whole program optimization of virtual calls in cases // where we know (via !type metadata) that the list of callees is fixed. This // includes the following: // - Single implementation devirtualization: if a virtual call has a single // possible callee, replace all calls with a direct call to that callee. // - Virtual constant propagation: if the virtual function's return type is an // integer <=64 bits and all possible callees are readnone, for each class and // each list of constant arguments: evaluate the function, store the return // value alongside the virtual table, and rewrite each virtual call as a load // from the virtual table. // - Uniform return value optimization: if the conditions for virtual constant // propagation hold and each function returns the same constant value, replace // each virtual call with that constant. // - Unique return value optimization for i1 return values: if the conditions // for virtual constant propagation hold and a single vtable's function // returns 0, or a single vtable's function returns 1, replace each virtual // call with a comparison of the vptr against that vtable's address. // // This pass is intended to be used during the regular and thin LTO pipelines: // // During regular LTO, the pass determines the best optimization for each // virtual call and applies the resolutions directly to virtual calls that are // eligible for virtual call optimization (i.e. calls that use either of the // llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics). // // During hybrid Regular/ThinLTO, the pass operates in two phases: // - Export phase: this is run during the thin link over a single merged module // that contains all vtables with !type metadata that participate in the link. // The pass computes a resolution for each virtual call and stores it in the // type identifier summary. // - Import phase: this is run during the thin backends over the individual // modules. The pass applies the resolutions previously computed during the // import phase to each eligible virtual call. // // During ThinLTO, the pass operates in two phases: // - Export phase: this is run during the thin link over the index which // contains a summary of all vtables with !type metadata that participate in // the link. It computes a resolution for each virtual call and stores it in // the type identifier summary. Only single implementation devirtualization // is supported. // - Import phase: (same as with hybrid case above). // //===----------------------------------------------------------------------===// #include "llvm/Transforms/IPO/WholeProgramDevirt.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseMapInfo.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/TypeMetadataUtils.h" #include "llvm/Bitcode/BitcodeReader.h" #include "llvm/Bitcode/BitcodeWriter.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/GlobalAlias.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/MDBuilder.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/ModuleSummaryIndexYAML.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Errc.h" #include "llvm/Support/Error.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/GlobPattern.h" #include "llvm/Support/MathExtras.h" #include "llvm/TargetParser/Triple.h" #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/CallPromotionUtils.h" #include "llvm/Transforms/Utils/Evaluator.h" #include <algorithm> #include <cstddef> #include <map> #include <set> #include <string> usingnamespacellvm; usingnamespacewholeprogramdevirt; #define DEBUG_TYPE … STATISTIC(NumDevirtTargets, "Number of whole program devirtualization targets"); STATISTIC(NumSingleImpl, "Number of single implementation devirtualizations"); STATISTIC(NumBranchFunnel, "Number of branch funnels"); STATISTIC(NumUniformRetVal, "Number of uniform return value optimizations"); STATISTIC(NumUniqueRetVal, "Number of unique return value optimizations"); STATISTIC(NumVirtConstProp1Bit, "Number of 1 bit virtual constant propagations"); STATISTIC(NumVirtConstProp, "Number of virtual constant propagations"); static cl::opt<PassSummaryAction> 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<std::string> ClReadSummary( "wholeprogramdevirt-read-summary", cl::desc( "Read summary from given bitcode or YAML file before running pass"), cl::Hidden); static cl::opt<std::string> ClWriteSummary( "wholeprogramdevirt-write-summary", cl::desc("Write summary to given bitcode or YAML file after running pass. " "Output file format is deduced from extension: *.bc means writing " "bitcode, otherwise YAML"), cl::Hidden); static cl::opt<unsigned> ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden, cl::init(10), cl::desc("Maximum number of call targets per " "call site to enable branch funnels")); static cl::opt<bool> PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden, cl::desc("Print index-based devirtualization messages")); /// Provide a way to force enable whole program visibility in tests. /// This is needed to support legacy tests that don't contain /// !vcall_visibility metadata (the mere presense of type tests /// previously implied hidden visibility). static cl::opt<bool> WholeProgramVisibility("whole-program-visibility", cl::Hidden, cl::desc("Enable whole program visibility")); /// Provide a way to force disable whole program for debugging or workarounds, /// when enabled via the linker. static cl::opt<bool> DisableWholeProgramVisibility( "disable-whole-program-visibility", cl::Hidden, cl::desc("Disable whole program visibility (overrides enabling options)")); /// Provide way to prevent certain function from being devirtualized static cl::list<std::string> SkipFunctionNames("wholeprogramdevirt-skip", cl::desc("Prevent function(s) from being devirtualized"), cl::Hidden, cl::CommaSeparated); /// Mechanism to add runtime checking of devirtualization decisions, optionally /// trapping or falling back to indirect call on any that are not correct. /// Trapping mode is useful for debugging undefined behavior leading to failures /// with WPD. Fallback mode is useful for ensuring safety when whole program /// visibility may be compromised. enum WPDCheckMode { … }; static cl::opt<WPDCheckMode> DevirtCheckMode( "wholeprogramdevirt-check", cl::Hidden, cl::desc("Type of checking for incorrect devirtualizations"), cl::values(clEnumValN(WPDCheckMode::None, "none", "No checking"), clEnumValN(WPDCheckMode::Trap, "trap", "Trap when incorrect"), clEnumValN(WPDCheckMode::Fallback, "fallback", "Fallback to indirect when incorrect"))); namespace { struct PatternList { … }; } // namespace // 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. uint64_t wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter, uint64_t Size) { … } void wholeprogramdevirt::setBeforeReturnValues( MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) { … } void wholeprogramdevirt::setAfterReturnValues( MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter, unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) { … } VirtualCallTarget::VirtualCallTarget(GlobalValue *Fn, const TypeMemberInfo *TM) : … { … } namespace { // A slot in a set of virtual tables. The TypeID identifies the set of virtual // tables, and the ByteOffset is the offset in bytes from the address point to // the virtual function pointer. struct VTableSlot { … }; } // end anonymous namespace namespace llvm { template <> struct DenseMapInfo<VTableSlot> { … }; template <> struct DenseMapInfo<VTableSlotSummary> { … }; } // end namespace llvm // Returns true if the function must be unreachable based on ValueInfo. // // In particular, identifies a function as unreachable in the following // conditions // 1) All summaries are live. // 2) All function summaries indicate it's unreachable // 3) There is no non-function with the same GUID (which is rare) static bool mustBeUnreachableFunction(ValueInfo TheFnVI) { … } namespace { // A virtual call site. VTable is the loaded virtual table pointer, and CS is // the indirect virtual call. struct VirtualCallSite { … }; // Call site information collected for a specific VTableSlot and possibly a list // of constant integer arguments. The grouping by arguments is handled by the // VTableSlotInfo class. struct CallSiteInfo { … }; // Call site information collected for a specific VTableSlot. struct VTableSlotInfo { … }; CallSiteInfo &VTableSlotInfo::findCallSiteInfo(CallBase &CB) { … } void VTableSlotInfo::addCallSite(Value *VTable, CallBase &CB, unsigned *NumUnsafeUses) { … } struct DevirtModule { … }; struct DevirtIndex { … }; } // end anonymous namespace PreservedAnalyses WholeProgramDevirtPass::run(Module &M, ModuleAnalysisManager &AM) { … } // Enable whole program visibility if enabled by client (e.g. linker) or // internal option, and not force disabled. bool llvm::hasWholeProgramVisibility(bool WholeProgramVisibilityEnabledInLTO) { … } static bool typeIDVisibleToRegularObj(StringRef TypeID, function_ref<bool(StringRef)> IsVisibleToRegularObj) { … } static bool skipUpdateDueToValidation(GlobalVariable &GV, function_ref<bool(StringRef)> IsVisibleToRegularObj) { … } /// If whole program visibility asserted, then upgrade all public vcall /// visibility metadata on vtable definitions to linkage unit visibility in /// Module IR (for regular or hybrid LTO). void llvm::updateVCallVisibilityInModule( Module &M, bool WholeProgramVisibilityEnabledInLTO, const DenseSet<GlobalValue::GUID> &DynamicExportSymbols, bool ValidateAllVtablesHaveTypeInfos, function_ref<bool(StringRef)> IsVisibleToRegularObj) { … } void llvm::updatePublicTypeTestCalls(Module &M, bool WholeProgramVisibilityEnabledInLTO) { … } /// Based on typeID string, get all associated vtable GUIDS that are /// visible to regular objects. void llvm::getVisibleToRegularObjVtableGUIDs( ModuleSummaryIndex &Index, DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols, function_ref<bool(StringRef)> IsVisibleToRegularObj) { … } /// If whole program visibility asserted, then upgrade all public vcall /// visibility metadata on vtable definition summaries to linkage unit /// visibility in Module summary index (for ThinLTO). void llvm::updateVCallVisibilityInIndex( ModuleSummaryIndex &Index, bool WholeProgramVisibilityEnabledInLTO, const DenseSet<GlobalValue::GUID> &DynamicExportSymbols, const DenseSet<GlobalValue::GUID> &VisibleToRegularObjSymbols) { … } void llvm::runWholeProgramDevirtOnIndex( ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs, std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) { … } void llvm::updateIndexWPDForExports( ModuleSummaryIndex &Summary, function_ref<bool(StringRef, ValueInfo)> isExported, std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) { … } static Error checkCombinedSummaryForTesting(ModuleSummaryIndex *Summary) { … } bool DevirtModule::runForTesting( Module &M, function_ref<AAResults &(Function &)> AARGetter, function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter, function_ref<DominatorTree &(Function &)> LookupDomTree) { … } void DevirtModule::buildTypeIdentifierMap( std::vector<VTableBits> &Bits, DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) { … } bool DevirtModule::tryFindVirtualCallTargets( std::vector<VirtualCallTarget> &TargetsForSlot, const std::set<TypeMemberInfo> &TypeMemberInfos, uint64_t ByteOffset, ModuleSummaryIndex *ExportSummary) { … } bool DevirtIndex::tryFindVirtualCallTargets( std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo, uint64_t ByteOffset) { … } void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn, bool &IsExported) { … } static bool AddCalls(VTableSlotInfo &SlotInfo, const ValueInfo &Callee) { … } bool DevirtModule::trySingleImplDevirt( ModuleSummaryIndex *ExportSummary, MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) { … } bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot, VTableSlotSummary &SlotSummary, VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res, std::set<ValueInfo> &DevirtTargets) { … } void DevirtModule::tryICallBranchFunnel( MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res, VTableSlot Slot) { … } void DevirtModule::applyICallBranchFunnel(VTableSlotInfo &SlotInfo, Constant *JT, bool &IsExported) { … } bool DevirtModule::tryEvaluateFunctionsWithArgs( MutableArrayRef<VirtualCallTarget> TargetsForSlot, ArrayRef<uint64_t> Args) { … } void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, uint64_t TheRetVal) { … } bool DevirtModule::tryUniformRetValOpt( MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res) { … } std::string DevirtModule::getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name) { … } bool DevirtModule::shouldExportConstantsAsAbsoluteSymbols() { … } void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, Constant *C) { … } void DevirtModule::exportConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, uint32_t Const, uint32_t &Storage) { … } Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name) { … } Constant *DevirtModule::importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name, IntegerType *IntTy, uint32_t Storage) { … } void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne, Constant *UniqueMemberAddr) { … } Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) { … } bool DevirtModule::tryUniqueRetValOpt( unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res, VTableSlot Slot, ArrayRef<uint64_t> Args) { … } void DevirtModule::applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName, Constant *Byte, Constant *Bit) { … } bool DevirtModule::tryVirtualConstProp( MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res, VTableSlot Slot) { … } void DevirtModule::rebuildGlobal(VTableBits &B) { … } bool DevirtModule::areRemarksEnabled() { … } void DevirtModule::scanTypeTestUsers( Function *TypeTestFunc, DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap) { … } void DevirtModule::scanTypeCheckedLoadUsers(Function *TypeCheckedLoadFunc) { … } void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) { … } void DevirtModule::removeRedundantTypeTests() { … } ValueInfo DevirtModule::lookUpFunctionValueInfo(Function *TheFn, ModuleSummaryIndex *ExportSummary) { … } bool DevirtModule::mustBeUnreachableFunction( Function *const F, ModuleSummaryIndex *ExportSummary) { … } bool DevirtModule::run() { … } void DevirtIndex::run() { … }
Codebase Browser
llvm