diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp')
-rw-r--r-- | contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp | 416 |
1 files changed, 305 insertions, 111 deletions
diff --git a/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp index c9ac2bd..f5ba637 100644 --- a/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp +++ b/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -13,16 +13,22 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/ModuleSummaryAnalysis.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/Triple.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/ProfileSummaryInfo.h" +#include "llvm/Analysis/TypeMetadataUtils.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/ValueSymbolTable.h" +#include "llvm/Object/IRObjectFile.h" #include "llvm/Pass.h" using namespace llvm; @@ -31,7 +37,7 @@ using namespace llvm; // Walk through the operands of a given User via worklist iteration and populate // the set of GlobalValue references encountered. Invoked either on an // Instruction or a GlobalVariable (which walks its initializer). -static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, +static void findRefEdges(const User *CurUser, SetVector<ValueInfo> &RefEdges, SmallPtrSet<const User *, 8> &Visited) { SmallVector<const User *, 32> Worklist; Worklist.push_back(CurUser); @@ -50,12 +56,12 @@ static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, continue; if (isa<BlockAddress>(Operand)) continue; - if (isa<GlobalValue>(Operand)) { + if (auto *GV = dyn_cast<GlobalValue>(Operand)) { // We have a reference to a global value. This should be added to // the reference set unless it is a callee. Callees are handled // specially by WriteFunction and are added to a separate list. if (!(CS && CS.isCallee(&OI))) - RefEdges.insert(Operand); + RefEdges.insert(GV); continue; } Worklist.push_back(Operand); @@ -63,98 +69,213 @@ static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, } } -void ModuleSummaryIndexBuilder::computeFunctionSummary( - const Function &F, BlockFrequencyInfo *BFI) { - // Summary not currently supported for anonymous functions, they must - // be renamed. - if (!F.hasName()) - return; +static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, + ProfileSummaryInfo *PSI) { + if (!PSI) + return CalleeInfo::HotnessType::Unknown; + if (PSI->isHotCount(ProfileCount)) + return CalleeInfo::HotnessType::Hot; + if (PSI->isColdCount(ProfileCount)) + return CalleeInfo::HotnessType::Cold; + return CalleeInfo::HotnessType::None; +} + +static bool isNonRenamableLocal(const GlobalValue &GV) { + return GV.hasSection() && GV.hasLocalLinkage(); +} + +static void +computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, + const Function &F, BlockFrequencyInfo *BFI, + ProfileSummaryInfo *PSI, bool HasLocalsInUsed, + DenseSet<GlobalValue::GUID> &CantBePromoted) { + // Summary not currently supported for anonymous functions, they should + // have been named. + assert(F.hasName()); unsigned NumInsts = 0; // Map from callee ValueId to profile count. Used to accumulate profile // counts for all static calls to a given callee. - DenseMap<const Value *, CalleeInfo> CallGraphEdges; - DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges; - DenseSet<const Value *> RefEdges; + MapVector<ValueInfo, CalleeInfo> CallGraphEdges; + SetVector<ValueInfo> RefEdges; + SetVector<GlobalValue::GUID> TypeTests; ICallPromotionAnalysis ICallAnalysis; + bool HasInlineAsmMaybeReferencingInternal = false; SmallPtrSet<const User *, 8> Visited; for (const BasicBlock &BB : F) for (const Instruction &I : BB) { - if (!isa<DbgInfoIntrinsic>(I)) - ++NumInsts; - - if (auto CS = ImmutableCallSite(&I)) { - auto *CalledFunction = CS.getCalledFunction(); - // Check if this is a direct call to a known function. - if (CalledFunction) { - if (CalledFunction->hasName() && !CalledFunction->isIntrinsic()) { - auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; - auto *CalleeId = - M->getValueSymbolTable().lookup(CalledFunction->getName()); - CallGraphEdges[CalleeId] += - (ScaledCount ? ScaledCount.getValue() : 0); - } - } else { - // Otherwise, check for an indirect call (call to a non-const value - // that isn't an inline assembly call). - const CallInst *CI = dyn_cast<CallInst>(&I); - if (CS.getCalledValue() && !isa<Constant>(CS.getCalledValue()) && - !(CI && CI->isInlineAsm())) { - uint32_t NumVals, NumCandidates; - uint64_t TotalCount; - auto CandidateProfileData = - ICallAnalysis.getPromotionCandidatesForInstruction( - &I, NumVals, TotalCount, NumCandidates); - for (auto &Candidate : CandidateProfileData) - IndirectCallEdges[Candidate.Value] += Candidate.Count; + if (isa<DbgInfoIntrinsic>(I)) + continue; + ++NumInsts; + findRefEdges(&I, RefEdges, Visited); + auto CS = ImmutableCallSite(&I); + if (!CS) + continue; + + const auto *CI = dyn_cast<CallInst>(&I); + // Since we don't know exactly which local values are referenced in inline + // assembly, conservatively mark the function as possibly referencing + // a local value from inline assembly to ensure we don't export a + // reference (which would require renaming and promotion of the + // referenced value). + if (HasLocalsInUsed && CI && CI->isInlineAsm()) + HasInlineAsmMaybeReferencingInternal = true; + + auto *CalledValue = CS.getCalledValue(); + auto *CalledFunction = CS.getCalledFunction(); + // Check if this is an alias to a function. If so, get the + // called aliasee for the checks below. + if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { + assert(!CalledFunction && "Expected null called function in callsite for alias"); + CalledFunction = dyn_cast<Function>(GA->getBaseObject()); + } + // Check if this is a direct call to a known function or a known + // intrinsic, or an indirect call with profile data. + if (CalledFunction) { + if (CalledFunction->isIntrinsic()) { + if (CalledFunction->getIntrinsicID() != Intrinsic::type_test) + continue; + // Produce a summary from type.test intrinsics. We only summarize + // type.test intrinsics that are used other than by an llvm.assume + // intrinsic. Intrinsics that are assumed are relevant only to the + // devirtualization pass, not the type test lowering pass. + bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) { + auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser()); + if (!AssumeCI) + return true; + Function *F = AssumeCI->getCalledFunction(); + return !F || F->getIntrinsicID() != Intrinsic::assume; + }); + if (HasNonAssumeUses) { + auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1)); + if (auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata())) + TypeTests.insert(GlobalValue::getGUID(TypeId->getString())); } } + // We should have named any anonymous globals + assert(CalledFunction->hasName()); + auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; + auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) + : CalleeInfo::HotnessType::Unknown; + + // Use the original CalledValue, in case it was an alias. We want + // to record the call edge to the alias in that case. Eventually + // an alias summary will be created to associate the alias and + // aliasee. + CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness); + } else { + // Skip inline assembly calls. + if (CI && CI->isInlineAsm()) + continue; + // Skip direct calls. + if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue())) + continue; + + uint32_t NumVals, NumCandidates; + uint64_t TotalCount; + auto CandidateProfileData = + ICallAnalysis.getPromotionCandidatesForInstruction( + &I, NumVals, TotalCount, NumCandidates); + for (auto &Candidate : CandidateProfileData) + CallGraphEdges[Candidate.Value].updateHotness( + getHotness(Candidate.Count, PSI)); } - findRefEdges(&I, RefEdges, Visited); } - GlobalValueSummary::GVFlags Flags(F); - std::unique_ptr<FunctionSummary> FuncSummary = - llvm::make_unique<FunctionSummary>(Flags, NumInsts); - FuncSummary->addCallGraphEdges(CallGraphEdges); - FuncSummary->addCallGraphEdges(IndirectCallEdges); - FuncSummary->addRefEdges(RefEdges); - Index->addGlobalValueSummary(F.getName(), std::move(FuncSummary)); + bool NonRenamableLocal = isNonRenamableLocal(F); + bool NotEligibleForImport = + NonRenamableLocal || HasInlineAsmMaybeReferencingInternal || + // Inliner doesn't handle variadic functions. + // FIXME: refactor this to use the same code that inliner is using. + F.isVarArg(); + GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport, + /* LiveRoot = */ false); + auto FuncSummary = llvm::make_unique<FunctionSummary>( + Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(), + TypeTests.takeVector()); + if (NonRenamableLocal) + CantBePromoted.insert(F.getGUID()); + Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary)); } -void ModuleSummaryIndexBuilder::computeVariableSummary( - const GlobalVariable &V) { - DenseSet<const Value *> RefEdges; +static void +computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, + DenseSet<GlobalValue::GUID> &CantBePromoted) { + SetVector<ValueInfo> RefEdges; SmallPtrSet<const User *, 8> Visited; findRefEdges(&V, RefEdges, Visited); - GlobalValueSummary::GVFlags Flags(V); - std::unique_ptr<GlobalVarSummary> GVarSummary = - llvm::make_unique<GlobalVarSummary>(Flags); - GVarSummary->addRefEdges(RefEdges); - Index->addGlobalValueSummary(V.getName(), std::move(GVarSummary)); + bool NonRenamableLocal = isNonRenamableLocal(V); + GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal, + /* LiveRoot = */ false); + auto GVarSummary = + llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector()); + if (NonRenamableLocal) + CantBePromoted.insert(V.getGUID()); + Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary)); } -ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder( - const Module *M, - std::function<BlockFrequencyInfo *(const Function &F)> Ftor) - : Index(llvm::make_unique<ModuleSummaryIndex>()), M(M) { - // Check if the module can be promoted, otherwise just disable importing from - // it by not emitting any summary. - // FIXME: we could still import *into* it most of the time. - if (!moduleCanBeRenamedForThinLTO(*M)) +static void +computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A, + DenseSet<GlobalValue::GUID> &CantBePromoted) { + bool NonRenamableLocal = isNonRenamableLocal(A); + GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal, + /* LiveRoot = */ false); + auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{}); + auto *Aliasee = A.getBaseObject(); + auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); + assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); + AS->setAliasee(AliaseeSummary); + if (NonRenamableLocal) + CantBePromoted.insert(A.getGUID()); + Index.addGlobalValueSummary(A.getName(), std::move(AS)); +} + +// Set LiveRoot flag on entries matching the given value name. +static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) { + auto SummaryList = + Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name)); + if (SummaryList == Index.end()) return; + for (auto &Summary : SummaryList->second) + Summary->setLiveRoot(); +} + +ModuleSummaryIndex llvm::buildModuleSummaryIndex( + const Module &M, + std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, + ProfileSummaryInfo *PSI) { + ModuleSummaryIndex Index; + + // Identify the local values in the llvm.used and llvm.compiler.used sets, + // which should not be exported as they would then require renaming and + // promotion, but we may have opaque uses e.g. in inline asm. We collect them + // here because we use this information to mark functions containing inline + // assembly calls as not importable. + SmallPtrSet<GlobalValue *, 8> LocalsUsed; + SmallPtrSet<GlobalValue *, 8> Used; + // First collect those in the llvm.used set. + collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); + // Next collect those in the llvm.compiler.used set. + collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true); + DenseSet<GlobalValue::GUID> CantBePromoted; + for (auto *V : Used) { + if (V->hasLocalLinkage()) { + LocalsUsed.insert(V); + CantBePromoted.insert(V->getGUID()); + } + } // Compute summaries for all functions defined in module, and save in the // index. - for (auto &F : *M) { + for (auto &F : M) { if (F.isDeclaration()) continue; BlockFrequencyInfo *BFI = nullptr; std::unique_ptr<BlockFrequencyInfo> BFIPtr; - if (Ftor) - BFI = Ftor(F); + if (GetBFICallback) + BFI = GetBFICallback(F); else if (F.getEntryCount().hasValue()) { LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; BranchProbabilityInfo BPI{F, LI}; @@ -162,22 +283,129 @@ ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder( BFI = BFIPtr.get(); } - computeFunctionSummary(F, BFI); + computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(), + CantBePromoted); } // Compute summaries for all variables defined in module, and save in the // index. - for (const GlobalVariable &G : M->globals()) { + for (const GlobalVariable &G : M.globals()) { if (G.isDeclaration()) continue; - computeVariableSummary(G); + computeVariableSummary(Index, G, CantBePromoted); + } + + // Compute summaries for all aliases defined in module, and save in the + // index. + for (const GlobalAlias &A : M.aliases()) + computeAliasSummary(Index, A, CantBePromoted); + + for (auto *V : LocalsUsed) { + auto *Summary = Index.getGlobalValueSummary(*V); + assert(Summary && "Missing summary for global value"); + Summary->setNotEligibleToImport(); + } + + // The linker doesn't know about these LLVM produced values, so we need + // to flag them as live in the index to ensure index-based dead value + // analysis treats them as live roots of the analysis. + setLiveRoot(Index, "llvm.used"); + setLiveRoot(Index, "llvm.compiler.used"); + setLiveRoot(Index, "llvm.global_ctors"); + setLiveRoot(Index, "llvm.global_dtors"); + setLiveRoot(Index, "llvm.global.annotations"); + + if (!M.getModuleInlineAsm().empty()) { + // Collect the local values defined by module level asm, and set up + // summaries for these symbols so that they can be marked as NoRename, + // to prevent export of any use of them in regular IR that would require + // renaming within the module level asm. Note we don't need to create a + // summary for weak or global defs, as they don't need to be flagged as + // NoRename, and defs in module level asm can't be imported anyway. + // Also, any values used but not defined within module level asm should + // be listed on the llvm.used or llvm.compiler.used global and marked as + // referenced from there. + ModuleSymbolTable::CollectAsmSymbols( + Triple(M.getTargetTriple()), M.getModuleInlineAsm(), + [&M, &Index, &CantBePromoted](StringRef Name, + object::BasicSymbolRef::Flags Flags) { + // Symbols not marked as Weak or Global are local definitions. + if (Flags & (object::BasicSymbolRef::SF_Weak | + object::BasicSymbolRef::SF_Global)) + return; + GlobalValue *GV = M.getNamedValue(Name); + if (!GV) + return; + assert(GV->isDeclaration() && "Def in module asm already has definition"); + GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage, + /* NotEligibleToImport */ true, + /* LiveRoot */ true); + CantBePromoted.insert(GlobalValue::getGUID(Name)); + // Create the appropriate summary type. + if (isa<Function>(GV)) { + std::unique_ptr<FunctionSummary> Summary = + llvm::make_unique<FunctionSummary>( + GVFlags, 0, ArrayRef<ValueInfo>{}, + ArrayRef<FunctionSummary::EdgeTy>{}, + ArrayRef<GlobalValue::GUID>{}); + Index.addGlobalValueSummary(Name, std::move(Summary)); + } else { + std::unique_ptr<GlobalVarSummary> Summary = + llvm::make_unique<GlobalVarSummary>(GVFlags, + ArrayRef<ValueInfo>{}); + Index.addGlobalValueSummary(Name, std::move(Summary)); + } + }); } + + for (auto &GlobalList : Index) { + assert(GlobalList.second.size() == 1 && + "Expected module's index to have one summary per GUID"); + auto &Summary = GlobalList.second[0]; + bool AllRefsCanBeExternallyReferenced = + llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) { + return !CantBePromoted.count(VI.getValue()->getGUID()); + }); + if (!AllRefsCanBeExternallyReferenced) { + Summary->setNotEligibleToImport(); + continue; + } + + if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) { + bool AllCallsCanBeExternallyReferenced = llvm::all_of( + FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) { + auto GUID = Edge.first.isGUID() ? Edge.first.getGUID() + : Edge.first.getValue()->getGUID(); + return !CantBePromoted.count(GUID); + }); + if (!AllCallsCanBeExternallyReferenced) + Summary->setNotEligibleToImport(); + } + } + + return Index; +} + +AnalysisKey ModuleSummaryIndexAnalysis::Key; + +ModuleSummaryIndex +ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { + ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); + auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); + return buildModuleSummaryIndex( + M, + [&FAM](const Function &F) { + return &FAM.getResult<BlockFrequencyAnalysis>( + *const_cast<Function *>(&F)); + }, + &PSI); } char ModuleSummaryIndexWrapperPass::ID = 0; INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", "Module Summary Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", "Module Summary Analysis", false, true) @@ -191,59 +419,25 @@ ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() } bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { - IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>( - &M, [this](const Function &F) { + auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); + Index = buildModuleSummaryIndex( + M, + [this](const Function &F) { return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( *const_cast<Function *>(&F)) .getBFI()); - }); + }, + &PSI); return false; } bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { - IndexBuilder.reset(); + Index.reset(); return false; } void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired<BlockFrequencyInfoWrapperPass>(); -} - -bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) { - // We cannot currently promote or rename anything used in inline assembly, - // which are not visible to the compiler. Detect a possible case by looking - // for a llvm.used local value, in conjunction with an inline assembly call - // in the module. Prevent importing of any modules containing these uses by - // suppressing generation of the index. This also prevents importing - // into this module, which is also necessary to avoid needing to rename - // in case of a name clash between a local in this module and an imported - // global. - // FIXME: If we find we need a finer-grained approach of preventing promotion - // and renaming of just the functions using inline assembly we will need to: - // - Add flag in the function summaries to identify those with inline asm. - // - Prevent importing of any functions with flag set. - // - Prevent importing of any global function with the same name as a - // function in current module that has the flag set. - // - For any llvm.used value that is exported and promoted, add a private - // alias to the original name in the current module (even if we don't - // export the function using those values in inline asm, another function - // with a reference could be exported). - SmallPtrSet<GlobalValue *, 8> Used; - collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); - bool LocalIsUsed = - llvm::any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); }); - if (!LocalIsUsed) - return true; - - // Walk all the instructions in the module and find if one is inline ASM - auto HasInlineAsm = llvm::any_of(M, [](const Function &F) { - return llvm::any_of(instructions(F), [](const Instruction &I) { - const CallInst *CallI = dyn_cast<CallInst>(&I); - if (!CallI) - return false; - return CallI->isInlineAsm(); - }); - }); - return !HasInlineAsm; + AU.addRequired<ProfileSummaryInfoWrapperPass>(); } |