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/ModuleSymbolTable.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(ModuleSummaryIndex &Index, const User *CurUser,
41 SetVector<ValueInfo> &RefEdges,
42 SmallPtrSet<const User *, 8> &Visited) {
43 SmallVector<const User *, 32> Worklist;
44 Worklist.push_back(CurUser);
46 while (!Worklist.empty()) {
47 const User *U = Worklist.pop_back_val();
49 if (!Visited.insert(U).second)
52 ImmutableCallSite CS(U);
54 for (const auto &OI : U->operands()) {
55 const User *Operand = dyn_cast<User>(OI);
58 if (isa<BlockAddress>(Operand))
60 if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
61 // We have a reference to a global value. This should be added to
62 // the reference set unless it is a callee. Callees are handled
63 // specially by WriteFunction and are added to a separate list.
64 if (!(CS && CS.isCallee(&OI)))
65 RefEdges.insert(Index.getOrInsertValueInfo(GV));
68 Worklist.push_back(Operand);
73 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
74 ProfileSummaryInfo *PSI) {
76 return CalleeInfo::HotnessType::Unknown;
77 if (PSI->isHotCount(ProfileCount))
78 return CalleeInfo::HotnessType::Hot;
79 if (PSI->isColdCount(ProfileCount))
80 return CalleeInfo::HotnessType::Cold;
81 return CalleeInfo::HotnessType::None;
84 static bool isNonRenamableLocal(const GlobalValue &GV) {
85 return GV.hasSection() && GV.hasLocalLinkage();
88 /// Determine whether this call has all constant integer arguments (excluding
89 /// "this") and summarize it to VCalls or ConstVCalls as appropriate.
90 static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid,
91 SetVector<FunctionSummary::VFuncId> &VCalls,
92 SetVector<FunctionSummary::ConstVCall> &ConstVCalls) {
93 std::vector<uint64_t> Args;
94 // Start from the second argument to skip the "this" pointer.
95 for (auto &Arg : make_range(Call.CS.arg_begin() + 1, Call.CS.arg_end())) {
96 auto *CI = dyn_cast<ConstantInt>(Arg);
97 if (!CI || CI->getBitWidth() > 64) {
98 VCalls.insert({Guid, Call.Offset});
101 Args.push_back(CI->getZExtValue());
103 ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
106 /// If this intrinsic call requires that we add information to the function
107 /// summary, do so via the non-constant reference arguments.
108 static void addIntrinsicToSummary(
109 const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
110 SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
111 SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
112 SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
113 SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls) {
114 switch (CI->getCalledFunction()->getIntrinsicID()) {
115 case Intrinsic::type_test: {
116 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
117 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
120 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
122 // Produce a summary from type.test intrinsics. We only summarize type.test
123 // intrinsics that are used other than by an llvm.assume intrinsic.
124 // Intrinsics that are assumed are relevant only to the devirtualization
125 // pass, not the type test lowering pass.
126 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
127 auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
130 Function *F = AssumeCI->getCalledFunction();
131 return !F || F->getIntrinsicID() != Intrinsic::assume;
133 if (HasNonAssumeUses)
134 TypeTests.insert(Guid);
136 SmallVector<DevirtCallSite, 4> DevirtCalls;
137 SmallVector<CallInst *, 4> Assumes;
138 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI);
139 for (auto &Call : DevirtCalls)
140 addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
141 TypeTestAssumeConstVCalls);
146 case Intrinsic::type_checked_load: {
147 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
148 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
151 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
153 SmallVector<DevirtCallSite, 4> DevirtCalls;
154 SmallVector<Instruction *, 4> LoadedPtrs;
155 SmallVector<Instruction *, 4> Preds;
156 bool HasNonCallUses = false;
157 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
159 // Any non-call uses of the result of llvm.type.checked.load will
160 // prevent us from optimizing away the llvm.type.test.
162 TypeTests.insert(Guid);
163 for (auto &Call : DevirtCalls)
164 addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
165 TypeCheckedLoadConstVCalls);
175 computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
176 const Function &F, BlockFrequencyInfo *BFI,
177 ProfileSummaryInfo *PSI, bool HasLocalsInUsed,
178 DenseSet<GlobalValue::GUID> &CantBePromoted) {
179 // Summary not currently supported for anonymous functions, they should
183 unsigned NumInsts = 0;
184 // Map from callee ValueId to profile count. Used to accumulate profile
185 // counts for all static calls to a given callee.
186 MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
187 SetVector<ValueInfo> RefEdges;
188 SetVector<GlobalValue::GUID> TypeTests;
189 SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
190 TypeCheckedLoadVCalls;
191 SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
192 TypeCheckedLoadConstVCalls;
193 ICallPromotionAnalysis ICallAnalysis;
195 bool HasInlineAsmMaybeReferencingInternal = false;
196 SmallPtrSet<const User *, 8> Visited;
197 for (const BasicBlock &BB : F)
198 for (const Instruction &I : BB) {
199 if (isa<DbgInfoIntrinsic>(I))
202 findRefEdges(Index, &I, RefEdges, Visited);
203 auto CS = ImmutableCallSite(&I);
207 const auto *CI = dyn_cast<CallInst>(&I);
208 // Since we don't know exactly which local values are referenced in inline
209 // assembly, conservatively mark the function as possibly referencing
210 // a local value from inline assembly to ensure we don't export a
211 // reference (which would require renaming and promotion of the
212 // referenced value).
213 if (HasLocalsInUsed && CI && CI->isInlineAsm())
214 HasInlineAsmMaybeReferencingInternal = true;
216 auto *CalledValue = CS.getCalledValue();
217 auto *CalledFunction = CS.getCalledFunction();
218 // Check if this is an alias to a function. If so, get the
219 // called aliasee for the checks below.
220 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
221 assert(!CalledFunction && "Expected null called function in callsite for alias");
222 CalledFunction = dyn_cast<Function>(GA->getBaseObject());
224 // Check if this is a direct call to a known function or a known
225 // intrinsic, or an indirect call with profile data.
226 if (CalledFunction) {
227 if (CI && CalledFunction->isIntrinsic()) {
228 addIntrinsicToSummary(
229 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
230 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls);
233 // We should have named any anonymous globals
234 assert(CalledFunction->hasName());
235 auto ScaledCount = ProfileSummaryInfo::getProfileCount(&I, BFI);
236 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
237 : CalleeInfo::HotnessType::Unknown;
239 // Use the original CalledValue, in case it was an alias. We want
240 // to record the call edge to the alias in that case. Eventually
241 // an alias summary will be created to associate the alias and
243 CallGraphEdges[Index.getOrInsertValueInfo(
244 cast<GlobalValue>(CalledValue))]
245 .updateHotness(Hotness);
247 // Skip inline assembly calls.
248 if (CI && CI->isInlineAsm())
250 // Skip direct calls.
251 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
254 uint32_t NumVals, NumCandidates;
256 auto CandidateProfileData =
257 ICallAnalysis.getPromotionCandidatesForInstruction(
258 &I, NumVals, TotalCount, NumCandidates);
259 for (auto &Candidate : CandidateProfileData)
260 CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
261 .updateHotness(getHotness(Candidate.Count, PSI));
265 // Explicit add hot edges to enforce importing for designated GUIDs for
266 // sample PGO, to enable the same inlines as the profiled optimized binary.
267 for (auto &I : F.getImportGUIDs())
268 CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
269 CalleeInfo::HotnessType::Hot);
271 bool NonRenamableLocal = isNonRenamableLocal(F);
272 bool NotEligibleForImport =
273 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
274 // Inliner doesn't handle variadic functions.
275 // FIXME: refactor this to use the same code that inliner is using.
277 GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
278 /* LiveRoot = */ false);
279 auto FuncSummary = llvm::make_unique<FunctionSummary>(
280 Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
281 TypeTests.takeVector(), TypeTestAssumeVCalls.takeVector(),
282 TypeCheckedLoadVCalls.takeVector(),
283 TypeTestAssumeConstVCalls.takeVector(),
284 TypeCheckedLoadConstVCalls.takeVector());
285 if (NonRenamableLocal)
286 CantBePromoted.insert(F.getGUID());
287 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
291 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
292 DenseSet<GlobalValue::GUID> &CantBePromoted) {
293 SetVector<ValueInfo> RefEdges;
294 SmallPtrSet<const User *, 8> Visited;
295 findRefEdges(Index, &V, RefEdges, Visited);
296 bool NonRenamableLocal = isNonRenamableLocal(V);
297 GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
298 /* LiveRoot = */ false);
300 llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
301 if (NonRenamableLocal)
302 CantBePromoted.insert(V.getGUID());
303 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
307 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
308 DenseSet<GlobalValue::GUID> &CantBePromoted) {
309 bool NonRenamableLocal = isNonRenamableLocal(A);
310 GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
311 /* LiveRoot = */ false);
312 auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
313 auto *Aliasee = A.getBaseObject();
314 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
315 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
316 AS->setAliasee(AliaseeSummary);
317 if (NonRenamableLocal)
318 CantBePromoted.insert(A.getGUID());
319 Index.addGlobalValueSummary(A.getName(), std::move(AS));
322 // Set LiveRoot flag on entries matching the given value name.
323 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
324 if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
325 for (auto &Summary : VI.getSummaryList())
326 Summary->setLiveRoot();
329 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
331 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
332 ProfileSummaryInfo *PSI) {
333 ModuleSummaryIndex Index;
335 // Identify the local values in the llvm.used and llvm.compiler.used sets,
336 // which should not be exported as they would then require renaming and
337 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
338 // here because we use this information to mark functions containing inline
339 // assembly calls as not importable.
340 SmallPtrSet<GlobalValue *, 8> LocalsUsed;
341 SmallPtrSet<GlobalValue *, 8> Used;
342 // First collect those in the llvm.used set.
343 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
344 // Next collect those in the llvm.compiler.used set.
345 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
346 DenseSet<GlobalValue::GUID> CantBePromoted;
347 for (auto *V : Used) {
348 if (V->hasLocalLinkage()) {
349 LocalsUsed.insert(V);
350 CantBePromoted.insert(V->getGUID());
354 // Compute summaries for all functions defined in module, and save in the
357 if (F.isDeclaration())
360 BlockFrequencyInfo *BFI = nullptr;
361 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
363 BFI = GetBFICallback(F);
364 else if (F.getEntryCount().hasValue()) {
365 LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
366 BranchProbabilityInfo BPI{F, LI};
367 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
371 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(),
375 // Compute summaries for all variables defined in module, and save in the
377 for (const GlobalVariable &G : M.globals()) {
378 if (G.isDeclaration())
380 computeVariableSummary(Index, G, CantBePromoted);
383 // Compute summaries for all aliases defined in module, and save in the
385 for (const GlobalAlias &A : M.aliases())
386 computeAliasSummary(Index, A, CantBePromoted);
388 for (auto *V : LocalsUsed) {
389 auto *Summary = Index.getGlobalValueSummary(*V);
390 assert(Summary && "Missing summary for global value");
391 Summary->setNotEligibleToImport();
394 // The linker doesn't know about these LLVM produced values, so we need
395 // to flag them as live in the index to ensure index-based dead value
396 // analysis treats them as live roots of the analysis.
397 setLiveRoot(Index, "llvm.used");
398 setLiveRoot(Index, "llvm.compiler.used");
399 setLiveRoot(Index, "llvm.global_ctors");
400 setLiveRoot(Index, "llvm.global_dtors");
401 setLiveRoot(Index, "llvm.global.annotations");
403 if (!M.getModuleInlineAsm().empty()) {
404 // Collect the local values defined by module level asm, and set up
405 // summaries for these symbols so that they can be marked as NoRename,
406 // to prevent export of any use of them in regular IR that would require
407 // renaming within the module level asm. Note we don't need to create a
408 // summary for weak or global defs, as they don't need to be flagged as
409 // NoRename, and defs in module level asm can't be imported anyway.
410 // Also, any values used but not defined within module level asm should
411 // be listed on the llvm.used or llvm.compiler.used global and marked as
412 // referenced from there.
413 ModuleSymbolTable::CollectAsmSymbols(
414 M, [&M, &Index, &CantBePromoted](StringRef Name,
415 object::BasicSymbolRef::Flags Flags) {
416 // Symbols not marked as Weak or Global are local definitions.
417 if (Flags & (object::BasicSymbolRef::SF_Weak |
418 object::BasicSymbolRef::SF_Global))
420 GlobalValue *GV = M.getNamedValue(Name);
423 assert(GV->isDeclaration() && "Def in module asm already has definition");
424 GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
425 /* NotEligibleToImport */ true,
426 /* LiveRoot */ true);
427 CantBePromoted.insert(GlobalValue::getGUID(Name));
428 // Create the appropriate summary type.
429 if (isa<Function>(GV)) {
430 std::unique_ptr<FunctionSummary> Summary =
431 llvm::make_unique<FunctionSummary>(
432 GVFlags, 0, ArrayRef<ValueInfo>{},
433 ArrayRef<FunctionSummary::EdgeTy>{},
434 ArrayRef<GlobalValue::GUID>{},
435 ArrayRef<FunctionSummary::VFuncId>{},
436 ArrayRef<FunctionSummary::VFuncId>{},
437 ArrayRef<FunctionSummary::ConstVCall>{},
438 ArrayRef<FunctionSummary::ConstVCall>{});
439 Index.addGlobalValueSummary(Name, std::move(Summary));
441 std::unique_ptr<GlobalVarSummary> Summary =
442 llvm::make_unique<GlobalVarSummary>(GVFlags,
443 ArrayRef<ValueInfo>{});
444 Index.addGlobalValueSummary(Name, std::move(Summary));
449 for (auto &GlobalList : Index) {
450 // Ignore entries for references that are undefined in the current module.
451 if (GlobalList.second.SummaryList.empty())
454 assert(GlobalList.second.SummaryList.size() == 1 &&
455 "Expected module's index to have one summary per GUID");
456 auto &Summary = GlobalList.second.SummaryList[0];
457 bool AllRefsCanBeExternallyReferenced =
458 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
459 return !CantBePromoted.count(VI.getGUID());
461 if (!AllRefsCanBeExternallyReferenced) {
462 Summary->setNotEligibleToImport();
466 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
467 bool AllCallsCanBeExternallyReferenced = llvm::all_of(
468 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
469 return !CantBePromoted.count(Edge.first.getGUID());
471 if (!AllCallsCanBeExternallyReferenced)
472 Summary->setNotEligibleToImport();
479 AnalysisKey ModuleSummaryIndexAnalysis::Key;
482 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
483 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
484 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
485 return buildModuleSummaryIndex(
487 [&FAM](const Function &F) {
488 return &FAM.getResult<BlockFrequencyAnalysis>(
489 *const_cast<Function *>(&F));
494 char ModuleSummaryIndexWrapperPass::ID = 0;
495 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
496 "Module Summary Analysis", false, true)
497 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
498 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
499 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
500 "Module Summary Analysis", false, true)
502 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
503 return new ModuleSummaryIndexWrapperPass();
506 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
508 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
511 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
512 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
513 Index = buildModuleSummaryIndex(
515 [this](const Function &F) {
516 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
517 *const_cast<Function *>(&F))
524 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
529 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
530 AU.setPreservesAll();
531 AU.addRequired<BlockFrequencyInfoWrapperPass>();
532 AU.addRequired<ProfileSummaryInfoWrapperPass>();