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(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();
87 /// Determine whether this call has all constant integer arguments (excluding
88 /// "this") and summarize it to VCalls or ConstVCalls as appropriate.
89 static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid,
90 SetVector<FunctionSummary::VFuncId> &VCalls,
91 SetVector<FunctionSummary::ConstVCall> &ConstVCalls) {
92 std::vector<uint64_t> Args;
93 // Start from the second argument to skip the "this" pointer.
94 for (auto &Arg : make_range(Call.CS.arg_begin() + 1, Call.CS.arg_end())) {
95 auto *CI = dyn_cast<ConstantInt>(Arg);
96 if (!CI || CI->getBitWidth() > 64) {
97 VCalls.insert({Guid, Call.Offset});
100 Args.push_back(CI->getZExtValue());
102 ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
105 /// If this intrinsic call requires that we add information to the function
106 /// summary, do so via the non-constant reference arguments.
107 static void addIntrinsicToSummary(
108 const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
109 SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
110 SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
111 SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
112 SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls) {
113 switch (CI->getCalledFunction()->getIntrinsicID()) {
114 case Intrinsic::type_test: {
115 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
116 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
119 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
121 // Produce a summary from type.test intrinsics. We only summarize type.test
122 // intrinsics that are used other than by an llvm.assume intrinsic.
123 // Intrinsics that are assumed are relevant only to the devirtualization
124 // pass, not the type test lowering pass.
125 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
126 auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
129 Function *F = AssumeCI->getCalledFunction();
130 return !F || F->getIntrinsicID() != Intrinsic::assume;
132 if (HasNonAssumeUses)
133 TypeTests.insert(Guid);
135 SmallVector<DevirtCallSite, 4> DevirtCalls;
136 SmallVector<CallInst *, 4> Assumes;
137 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI);
138 for (auto &Call : DevirtCalls)
139 addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
140 TypeTestAssumeConstVCalls);
145 case Intrinsic::type_checked_load: {
146 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
147 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
150 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
152 SmallVector<DevirtCallSite, 4> DevirtCalls;
153 SmallVector<Instruction *, 4> LoadedPtrs;
154 SmallVector<Instruction *, 4> Preds;
155 bool HasNonCallUses = false;
156 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
158 // Any non-call uses of the result of llvm.type.checked.load will
159 // prevent us from optimizing away the llvm.type.test.
161 TypeTests.insert(Guid);
162 for (auto &Call : DevirtCalls)
163 addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
164 TypeCheckedLoadConstVCalls);
174 computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
175 const Function &F, BlockFrequencyInfo *BFI,
176 ProfileSummaryInfo *PSI, bool HasLocalsInUsed,
177 DenseSet<GlobalValue::GUID> &CantBePromoted) {
178 // Summary not currently supported for anonymous functions, they should
182 unsigned NumInsts = 0;
183 // Map from callee ValueId to profile count. Used to accumulate profile
184 // counts for all static calls to a given callee.
185 MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
186 SetVector<ValueInfo> RefEdges;
187 SetVector<GlobalValue::GUID> TypeTests;
188 SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
189 TypeCheckedLoadVCalls;
190 SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
191 TypeCheckedLoadConstVCalls;
192 ICallPromotionAnalysis ICallAnalysis;
194 bool HasInlineAsmMaybeReferencingInternal = false;
195 SmallPtrSet<const User *, 8> Visited;
196 for (const BasicBlock &BB : F)
197 for (const Instruction &I : BB) {
198 if (isa<DbgInfoIntrinsic>(I))
201 findRefEdges(&I, RefEdges, Visited);
202 auto CS = ImmutableCallSite(&I);
206 const auto *CI = dyn_cast<CallInst>(&I);
207 // Since we don't know exactly which local values are referenced in inline
208 // assembly, conservatively mark the function as possibly referencing
209 // a local value from inline assembly to ensure we don't export a
210 // reference (which would require renaming and promotion of the
211 // referenced value).
212 if (HasLocalsInUsed && CI && CI->isInlineAsm())
213 HasInlineAsmMaybeReferencingInternal = true;
215 auto *CalledValue = CS.getCalledValue();
216 auto *CalledFunction = CS.getCalledFunction();
217 // Check if this is an alias to a function. If so, get the
218 // called aliasee for the checks below.
219 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
220 assert(!CalledFunction && "Expected null called function in callsite for alias");
221 CalledFunction = dyn_cast<Function>(GA->getBaseObject());
223 // Check if this is a direct call to a known function or a known
224 // intrinsic, or an indirect call with profile data.
225 if (CalledFunction) {
226 if (CI && CalledFunction->isIntrinsic()) {
227 addIntrinsicToSummary(
228 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
229 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls);
232 // We should have named any anonymous globals
233 assert(CalledFunction->hasName());
234 auto ScaledCount = ProfileSummaryInfo::getProfileCount(&I, BFI);
235 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
236 : CalleeInfo::HotnessType::Unknown;
238 // Use the original CalledValue, in case it was an alias. We want
239 // to record the call edge to the alias in that case. Eventually
240 // an alias summary will be created to associate the alias and
242 CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
244 // Skip inline assembly calls.
245 if (CI && CI->isInlineAsm())
247 // Skip direct calls.
248 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
251 uint32_t NumVals, NumCandidates;
253 auto CandidateProfileData =
254 ICallAnalysis.getPromotionCandidatesForInstruction(
255 &I, NumVals, TotalCount, NumCandidates);
256 for (auto &Candidate : CandidateProfileData)
257 CallGraphEdges[Candidate.Value].updateHotness(
258 getHotness(Candidate.Count, PSI));
262 // Explicit add hot edges to enforce importing for designated GUIDs for
263 // sample PGO, to enable the same inlines as the profiled optimized binary.
264 for (auto &I : F.getImportGUIDs())
265 CallGraphEdges[I].updateHotness(CalleeInfo::HotnessType::Hot);
267 bool NonRenamableLocal = isNonRenamableLocal(F);
268 bool NotEligibleForImport =
269 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
270 // Inliner doesn't handle variadic functions.
271 // FIXME: refactor this to use the same code that inliner is using.
273 GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
274 /* LiveRoot = */ false);
275 auto FuncSummary = llvm::make_unique<FunctionSummary>(
276 Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
277 TypeTests.takeVector(), TypeTestAssumeVCalls.takeVector(),
278 TypeCheckedLoadVCalls.takeVector(),
279 TypeTestAssumeConstVCalls.takeVector(),
280 TypeCheckedLoadConstVCalls.takeVector());
281 if (NonRenamableLocal)
282 CantBePromoted.insert(F.getGUID());
283 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
287 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
288 DenseSet<GlobalValue::GUID> &CantBePromoted) {
289 SetVector<ValueInfo> RefEdges;
290 SmallPtrSet<const User *, 8> Visited;
291 findRefEdges(&V, RefEdges, Visited);
292 bool NonRenamableLocal = isNonRenamableLocal(V);
293 GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
294 /* LiveRoot = */ false);
296 llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
297 if (NonRenamableLocal)
298 CantBePromoted.insert(V.getGUID());
299 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
303 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
304 DenseSet<GlobalValue::GUID> &CantBePromoted) {
305 bool NonRenamableLocal = isNonRenamableLocal(A);
306 GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
307 /* LiveRoot = */ false);
308 auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
309 auto *Aliasee = A.getBaseObject();
310 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
311 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
312 AS->setAliasee(AliaseeSummary);
313 if (NonRenamableLocal)
314 CantBePromoted.insert(A.getGUID());
315 Index.addGlobalValueSummary(A.getName(), std::move(AS));
318 // Set LiveRoot flag on entries matching the given value name.
319 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
321 Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name));
322 if (SummaryList == Index.end())
324 for (auto &Summary : SummaryList->second)
325 Summary->setLiveRoot();
328 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
330 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
331 ProfileSummaryInfo *PSI) {
332 ModuleSummaryIndex Index;
334 // Identify the local values in the llvm.used and llvm.compiler.used sets,
335 // which should not be exported as they would then require renaming and
336 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
337 // here because we use this information to mark functions containing inline
338 // assembly calls as not importable.
339 SmallPtrSet<GlobalValue *, 8> LocalsUsed;
340 SmallPtrSet<GlobalValue *, 8> Used;
341 // First collect those in the llvm.used set.
342 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
343 // Next collect those in the llvm.compiler.used set.
344 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
345 DenseSet<GlobalValue::GUID> CantBePromoted;
346 for (auto *V : Used) {
347 if (V->hasLocalLinkage()) {
348 LocalsUsed.insert(V);
349 CantBePromoted.insert(V->getGUID());
353 // Compute summaries for all functions defined in module, and save in the
356 if (F.isDeclaration())
359 BlockFrequencyInfo *BFI = nullptr;
360 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
362 BFI = GetBFICallback(F);
363 else if (F.getEntryCount().hasValue()) {
364 LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
365 BranchProbabilityInfo BPI{F, LI};
366 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
370 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(),
374 // Compute summaries for all variables defined in module, and save in the
376 for (const GlobalVariable &G : M.globals()) {
377 if (G.isDeclaration())
379 computeVariableSummary(Index, G, CantBePromoted);
382 // Compute summaries for all aliases defined in module, and save in the
384 for (const GlobalAlias &A : M.aliases())
385 computeAliasSummary(Index, A, CantBePromoted);
387 for (auto *V : LocalsUsed) {
388 auto *Summary = Index.getGlobalValueSummary(*V);
389 assert(Summary && "Missing summary for global value");
390 Summary->setNotEligibleToImport();
393 // The linker doesn't know about these LLVM produced values, so we need
394 // to flag them as live in the index to ensure index-based dead value
395 // analysis treats them as live roots of the analysis.
396 setLiveRoot(Index, "llvm.used");
397 setLiveRoot(Index, "llvm.compiler.used");
398 setLiveRoot(Index, "llvm.global_ctors");
399 setLiveRoot(Index, "llvm.global_dtors");
400 setLiveRoot(Index, "llvm.global.annotations");
402 if (!M.getModuleInlineAsm().empty()) {
403 // Collect the local values defined by module level asm, and set up
404 // summaries for these symbols so that they can be marked as NoRename,
405 // to prevent export of any use of them in regular IR that would require
406 // renaming within the module level asm. Note we don't need to create a
407 // summary for weak or global defs, as they don't need to be flagged as
408 // NoRename, and defs in module level asm can't be imported anyway.
409 // Also, any values used but not defined within module level asm should
410 // be listed on the llvm.used or llvm.compiler.used global and marked as
411 // referenced from there.
412 ModuleSymbolTable::CollectAsmSymbols(
413 M, [&M, &Index, &CantBePromoted](StringRef Name,
414 object::BasicSymbolRef::Flags Flags) {
415 // Symbols not marked as Weak or Global are local definitions.
416 if (Flags & (object::BasicSymbolRef::SF_Weak |
417 object::BasicSymbolRef::SF_Global))
419 GlobalValue *GV = M.getNamedValue(Name);
422 assert(GV->isDeclaration() && "Def in module asm already has definition");
423 GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
424 /* NotEligibleToImport */ true,
425 /* LiveRoot */ true);
426 CantBePromoted.insert(GlobalValue::getGUID(Name));
427 // Create the appropriate summary type.
428 if (isa<Function>(GV)) {
429 std::unique_ptr<FunctionSummary> Summary =
430 llvm::make_unique<FunctionSummary>(
431 GVFlags, 0, ArrayRef<ValueInfo>{},
432 ArrayRef<FunctionSummary::EdgeTy>{},
433 ArrayRef<GlobalValue::GUID>{},
434 ArrayRef<FunctionSummary::VFuncId>{},
435 ArrayRef<FunctionSummary::VFuncId>{},
436 ArrayRef<FunctionSummary::ConstVCall>{},
437 ArrayRef<FunctionSummary::ConstVCall>{});
438 Index.addGlobalValueSummary(Name, std::move(Summary));
440 std::unique_ptr<GlobalVarSummary> Summary =
441 llvm::make_unique<GlobalVarSummary>(GVFlags,
442 ArrayRef<ValueInfo>{});
443 Index.addGlobalValueSummary(Name, std::move(Summary));
448 for (auto &GlobalList : Index) {
449 assert(GlobalList.second.size() == 1 &&
450 "Expected module's index to have one summary per GUID");
451 auto &Summary = GlobalList.second[0];
452 bool AllRefsCanBeExternallyReferenced =
453 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
454 // If a global value definition references an unnamed global,
455 // be conservative. They're valid IR so we don't want to crash
456 // when we encounter any of them but they're infrequent enough
457 // that we don't bother optimizing them.
458 if (!VI.getValue()->hasName())
460 return !CantBePromoted.count(VI.getValue()->getGUID());
462 if (!AllRefsCanBeExternallyReferenced) {
463 Summary->setNotEligibleToImport();
467 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
468 bool AllCallsCanBeExternallyReferenced = llvm::all_of(
469 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
470 auto GUID = Edge.first.isGUID() ? Edge.first.getGUID()
471 : Edge.first.getValue()->getGUID();
472 return !CantBePromoted.count(GUID);
474 if (!AllCallsCanBeExternallyReferenced)
475 Summary->setNotEligibleToImport();
482 AnalysisKey ModuleSummaryIndexAnalysis::Key;
485 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
486 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
487 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
488 return buildModuleSummaryIndex(
490 [&FAM](const Function &F) {
491 return &FAM.getResult<BlockFrequencyAnalysis>(
492 *const_cast<Function *>(&F));
497 char ModuleSummaryIndexWrapperPass::ID = 0;
498 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
499 "Module Summary Analysis", false, true)
500 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
501 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
502 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
503 "Module Summary Analysis", false, true)
505 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
506 return new ModuleSummaryIndexWrapperPass();
509 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
511 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
514 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
515 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
516 Index = buildModuleSummaryIndex(
518 [this](const Function &F) {
519 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
520 *const_cast<Function *>(&F))
527 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
532 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
533 AU.setPreservesAll();
534 AU.addRequired<BlockFrequencyInfoWrapperPass>();
535 AU.addRequired<ProfileSummaryInfoWrapperPass>();