diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp | 443 |
1 files changed, 443 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp new file mode 100644 index 000000000000..f5ba637e58e2 --- /dev/null +++ b/contrib/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -0,0 +1,443 @@ +//===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass builds a ModuleSummaryIndex object for the module, to be written +// to bitcode or LLVM assembly. +// +//===----------------------------------------------------------------------===// + +#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; + +#define DEBUG_TYPE "module-summary-analysis" + +// 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, SetVector<ValueInfo> &RefEdges, + SmallPtrSet<const User *, 8> &Visited) { + SmallVector<const User *, 32> Worklist; + Worklist.push_back(CurUser); + + while (!Worklist.empty()) { + const User *U = Worklist.pop_back_val(); + + if (!Visited.insert(U).second) + continue; + + ImmutableCallSite CS(U); + + for (const auto &OI : U->operands()) { + const User *Operand = dyn_cast<User>(OI); + if (!Operand) + continue; + if (isa<BlockAddress>(Operand)) + continue; + 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(GV); + continue; + } + Worklist.push_back(Operand); + } + } +} + +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. + 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)) + 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)); + } + } + + 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)); +} + +static void +computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, + DenseSet<GlobalValue::GUID> &CantBePromoted) { + SetVector<ValueInfo> RefEdges; + SmallPtrSet<const User *, 8> Visited; + findRefEdges(&V, RefEdges, Visited); + 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)); +} + +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) { + if (F.isDeclaration()) + continue; + + BlockFrequencyInfo *BFI = nullptr; + std::unique_ptr<BlockFrequencyInfo> BFIPtr; + if (GetBFICallback) + BFI = GetBFICallback(F); + else if (F.getEntryCount().hasValue()) { + LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; + BranchProbabilityInfo BPI{F, LI}; + BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); + BFI = BFIPtr.get(); + } + + 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()) { + if (G.isDeclaration()) + continue; + 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) + +ModulePass *llvm::createModuleSummaryIndexWrapperPass() { + return new ModuleSummaryIndexWrapperPass(); +} + +ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() + : ModulePass(ID) { + initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); +} + +bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { + 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) { + Index.reset(); + return false; +} + +void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<BlockFrequencyInfoWrapperPass>(); + AU.addRequired<ProfileSummaryInfoWrapperPass>(); +} |