1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass builds a ModuleSummaryIndex object for the module, to be written
11 // to bitcode or LLVM assembly.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
16 #include "llvm/ADT/MapVector.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/Triple.h"
19 #include "llvm/Analysis/BlockFrequencyInfo.h"
20 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
21 #include "llvm/Analysis/BranchProbabilityInfo.h"
22 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
23 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Analysis/ProfileSummaryInfo.h"
25 #include "llvm/Analysis/TypeMetadataUtils.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/Dominators.h"
28 #include "llvm/IR/InstIterator.h"
29 #include "llvm/IR/IntrinsicInst.h"
30 #include "llvm/IR/ValueSymbolTable.h"
31 #include "llvm/Object/IRObjectFile.h"
32 #include "llvm/Pass.h"
35 #define DEBUG_TYPE "module-summary-analysis"
37 // Walk through the operands of a given User via worklist iteration and populate
38 // the set of GlobalValue references encountered. Invoked either on an
39 // Instruction or a GlobalVariable (which walks its initializer).
40 static void findRefEdges(const User *CurUser, SetVector<ValueInfo> &RefEdges,
41 SmallPtrSet<const User *, 8> &Visited) {
42 SmallVector<const User *, 32> Worklist;
43 Worklist.push_back(CurUser);
45 while (!Worklist.empty()) {
46 const User *U = Worklist.pop_back_val();
48 if (!Visited.insert(U).second)
51 ImmutableCallSite CS(U);
53 for (const auto &OI : U->operands()) {
54 const User *Operand = dyn_cast<User>(OI);
57 if (isa<BlockAddress>(Operand))
59 if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
60 // We have a reference to a global value. This should be added to
61 // the reference set unless it is a callee. Callees are handled
62 // specially by WriteFunction and are added to a separate list.
63 if (!(CS && CS.isCallee(&OI)))
67 Worklist.push_back(Operand);
72 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
73 ProfileSummaryInfo *PSI) {
75 return CalleeInfo::HotnessType::Unknown;
76 if (PSI->isHotCount(ProfileCount))
77 return CalleeInfo::HotnessType::Hot;
78 if (PSI->isColdCount(ProfileCount))
79 return CalleeInfo::HotnessType::Cold;
80 return CalleeInfo::HotnessType::None;
83 static bool isNonRenamableLocal(const GlobalValue &GV) {
84 return GV.hasSection() && GV.hasLocalLinkage();
88 computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
89 const Function &F, BlockFrequencyInfo *BFI,
90 ProfileSummaryInfo *PSI, bool HasLocalsInUsed,
91 DenseSet<GlobalValue::GUID> &CantBePromoted) {
92 // Summary not currently supported for anonymous functions, they should
96 unsigned NumInsts = 0;
97 // Map from callee ValueId to profile count. Used to accumulate profile
98 // counts for all static calls to a given callee.
99 MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
100 SetVector<ValueInfo> RefEdges;
101 SetVector<GlobalValue::GUID> TypeTests;
102 ICallPromotionAnalysis ICallAnalysis;
104 bool HasInlineAsmMaybeReferencingInternal = false;
105 SmallPtrSet<const User *, 8> Visited;
106 for (const BasicBlock &BB : F)
107 for (const Instruction &I : BB) {
108 if (isa<DbgInfoIntrinsic>(I))
111 findRefEdges(&I, RefEdges, Visited);
112 auto CS = ImmutableCallSite(&I);
116 const auto *CI = dyn_cast<CallInst>(&I);
117 // Since we don't know exactly which local values are referenced in inline
118 // assembly, conservatively mark the function as possibly referencing
119 // a local value from inline assembly to ensure we don't export a
120 // reference (which would require renaming and promotion of the
121 // referenced value).
122 if (HasLocalsInUsed && CI && CI->isInlineAsm())
123 HasInlineAsmMaybeReferencingInternal = true;
125 auto *CalledValue = CS.getCalledValue();
126 auto *CalledFunction = CS.getCalledFunction();
127 // Check if this is an alias to a function. If so, get the
128 // called aliasee for the checks below.
129 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
130 assert(!CalledFunction && "Expected null called function in callsite for alias");
131 CalledFunction = dyn_cast<Function>(GA->getBaseObject());
133 // Check if this is a direct call to a known function or a known
134 // intrinsic, or an indirect call with profile data.
135 if (CalledFunction) {
136 if (CalledFunction->isIntrinsic()) {
137 if (CalledFunction->getIntrinsicID() != Intrinsic::type_test)
139 // Produce a summary from type.test intrinsics. We only summarize
140 // type.test intrinsics that are used other than by an llvm.assume
141 // intrinsic. Intrinsics that are assumed are relevant only to the
142 // devirtualization pass, not the type test lowering pass.
143 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
144 auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
147 Function *F = AssumeCI->getCalledFunction();
148 return !F || F->getIntrinsicID() != Intrinsic::assume;
150 if (HasNonAssumeUses) {
151 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
152 if (auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()))
153 TypeTests.insert(GlobalValue::getGUID(TypeId->getString()));
156 // We should have named any anonymous globals
157 assert(CalledFunction->hasName());
158 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
159 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
160 : CalleeInfo::HotnessType::Unknown;
162 // Use the original CalledValue, in case it was an alias. We want
163 // to record the call edge to the alias in that case. Eventually
164 // an alias summary will be created to associate the alias and
166 CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
168 // Skip inline assembly calls.
169 if (CI && CI->isInlineAsm())
171 // Skip direct calls.
172 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
175 uint32_t NumVals, NumCandidates;
177 auto CandidateProfileData =
178 ICallAnalysis.getPromotionCandidatesForInstruction(
179 &I, NumVals, TotalCount, NumCandidates);
180 for (auto &Candidate : CandidateProfileData)
181 CallGraphEdges[Candidate.Value].updateHotness(
182 getHotness(Candidate.Count, PSI));
186 bool NonRenamableLocal = isNonRenamableLocal(F);
187 bool NotEligibleForImport =
188 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
189 // Inliner doesn't handle variadic functions.
190 // FIXME: refactor this to use the same code that inliner is using.
192 GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
193 /* LiveRoot = */ false,
194 /* AutoHide */ false);
195 auto FuncSummary = llvm::make_unique<FunctionSummary>(
196 Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
197 TypeTests.takeVector());
198 if (NonRenamableLocal)
199 CantBePromoted.insert(F.getGUID());
200 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
204 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
205 DenseSet<GlobalValue::GUID> &CantBePromoted) {
206 SetVector<ValueInfo> RefEdges;
207 SmallPtrSet<const User *, 8> Visited;
208 findRefEdges(&V, RefEdges, Visited);
209 bool NonRenamableLocal = isNonRenamableLocal(V);
210 GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
211 /* LiveRoot = */ false,
212 /* AutoHide */ false);
214 llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
215 if (NonRenamableLocal)
216 CantBePromoted.insert(V.getGUID());
217 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
221 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
222 DenseSet<GlobalValue::GUID> &CantBePromoted) {
223 bool NonRenamableLocal = isNonRenamableLocal(A);
224 GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
225 /* LiveRoot = */ false,
226 /* AutoHide */ false);
227 auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
228 auto *Aliasee = A.getBaseObject();
229 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
230 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
231 AS->setAliasee(AliaseeSummary);
232 if (NonRenamableLocal)
233 CantBePromoted.insert(A.getGUID());
234 Index.addGlobalValueSummary(A.getName(), std::move(AS));
237 // Set LiveRoot flag on entries matching the given value name.
238 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
240 Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name));
241 if (SummaryList == Index.end())
243 for (auto &Summary : SummaryList->second)
244 Summary->setLiveRoot();
247 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
249 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
250 ProfileSummaryInfo *PSI) {
251 ModuleSummaryIndex Index;
253 // Identify the local values in the llvm.used and llvm.compiler.used sets,
254 // which should not be exported as they would then require renaming and
255 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
256 // here because we use this information to mark functions containing inline
257 // assembly calls as not importable.
258 SmallPtrSet<GlobalValue *, 8> LocalsUsed;
259 SmallPtrSet<GlobalValue *, 8> Used;
260 // First collect those in the llvm.used set.
261 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
262 // Next collect those in the llvm.compiler.used set.
263 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
264 DenseSet<GlobalValue::GUID> CantBePromoted;
265 for (auto *V : Used) {
266 if (V->hasLocalLinkage()) {
267 LocalsUsed.insert(V);
268 CantBePromoted.insert(V->getGUID());
272 // Compute summaries for all functions defined in module, and save in the
275 if (F.isDeclaration())
278 BlockFrequencyInfo *BFI = nullptr;
279 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
281 BFI = GetBFICallback(F);
282 else if (F.getEntryCount().hasValue()) {
283 LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
284 BranchProbabilityInfo BPI{F, LI};
285 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
289 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(),
293 // Compute summaries for all variables defined in module, and save in the
295 for (const GlobalVariable &G : M.globals()) {
296 if (G.isDeclaration())
298 computeVariableSummary(Index, G, CantBePromoted);
301 // Compute summaries for all aliases defined in module, and save in the
303 for (const GlobalAlias &A : M.aliases())
304 computeAliasSummary(Index, A, CantBePromoted);
306 for (auto *V : LocalsUsed) {
307 auto *Summary = Index.getGlobalValueSummary(*V);
308 assert(Summary && "Missing summary for global value");
309 Summary->setNotEligibleToImport();
312 // The linker doesn't know about these LLVM produced values, so we need
313 // to flag them as live in the index to ensure index-based dead value
314 // analysis treats them as live roots of the analysis.
315 setLiveRoot(Index, "llvm.used");
316 setLiveRoot(Index, "llvm.compiler.used");
317 setLiveRoot(Index, "llvm.global_ctors");
318 setLiveRoot(Index, "llvm.global_dtors");
319 setLiveRoot(Index, "llvm.global.annotations");
321 if (!M.getModuleInlineAsm().empty()) {
322 // Collect the local values defined by module level asm, and set up
323 // summaries for these symbols so that they can be marked as NoRename,
324 // to prevent export of any use of them in regular IR that would require
325 // renaming within the module level asm. Note we don't need to create a
326 // summary for weak or global defs, as they don't need to be flagged as
327 // NoRename, and defs in module level asm can't be imported anyway.
328 // Also, any values used but not defined within module level asm should
329 // be listed on the llvm.used or llvm.compiler.used global and marked as
330 // referenced from there.
331 ModuleSymbolTable::CollectAsmSymbols(
332 Triple(M.getTargetTriple()), M.getModuleInlineAsm(),
333 [&M, &Index, &CantBePromoted](StringRef Name,
334 object::BasicSymbolRef::Flags Flags) {
335 // Symbols not marked as Weak or Global are local definitions.
336 if (Flags & (object::BasicSymbolRef::SF_Weak |
337 object::BasicSymbolRef::SF_Global))
339 GlobalValue *GV = M.getNamedValue(Name);
342 assert(GV->isDeclaration() && "Def in module asm already has definition");
343 GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
344 /* NotEligibleToImport */ true,
346 /* AutoHide */ false);
347 CantBePromoted.insert(GlobalValue::getGUID(Name));
348 // Create the appropriate summary type.
349 if (isa<Function>(GV)) {
350 std::unique_ptr<FunctionSummary> Summary =
351 llvm::make_unique<FunctionSummary>(
352 GVFlags, 0, ArrayRef<ValueInfo>{},
353 ArrayRef<FunctionSummary::EdgeTy>{},
354 ArrayRef<GlobalValue::GUID>{});
355 Index.addGlobalValueSummary(Name, std::move(Summary));
357 std::unique_ptr<GlobalVarSummary> Summary =
358 llvm::make_unique<GlobalVarSummary>(GVFlags,
359 ArrayRef<ValueInfo>{});
360 Index.addGlobalValueSummary(Name, std::move(Summary));
365 for (auto &GlobalList : Index) {
366 assert(GlobalList.second.size() == 1 &&
367 "Expected module's index to have one summary per GUID");
368 auto &Summary = GlobalList.second[0];
369 bool AllRefsCanBeExternallyReferenced =
370 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
371 return !CantBePromoted.count(VI.getValue()->getGUID());
373 if (!AllRefsCanBeExternallyReferenced) {
374 Summary->setNotEligibleToImport();
378 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
379 bool AllCallsCanBeExternallyReferenced = llvm::all_of(
380 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
381 auto GUID = Edge.first.isGUID() ? Edge.first.getGUID()
382 : Edge.first.getValue()->getGUID();
383 return !CantBePromoted.count(GUID);
385 if (!AllCallsCanBeExternallyReferenced)
386 Summary->setNotEligibleToImport();
393 AnalysisKey ModuleSummaryIndexAnalysis::Key;
396 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
397 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
398 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
399 return buildModuleSummaryIndex(
401 [&FAM](const Function &F) {
402 return &FAM.getResult<BlockFrequencyAnalysis>(
403 *const_cast<Function *>(&F));
408 char ModuleSummaryIndexWrapperPass::ID = 0;
409 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
410 "Module Summary Analysis", false, true)
411 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
412 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
413 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
414 "Module Summary Analysis", false, true)
416 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
417 return new ModuleSummaryIndexWrapperPass();
420 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
422 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
425 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
426 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
427 Index = buildModuleSummaryIndex(
429 [this](const Function &F) {
430 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
431 *const_cast<Function *>(&F))
438 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
443 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
444 AU.setPreservesAll();
445 AU.addRequired<BlockFrequencyInfoWrapperPass>();
446 AU.addRequired<ProfileSummaryInfoWrapperPass>();