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/Analysis/BlockFrequencyInfo.h"
17 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
18 #include "llvm/Analysis/BranchProbabilityInfo.h"
19 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/IR/CallSite.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/InstIterator.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/ValueSymbolTable.h"
26 #include "llvm/Pass.h"
29 #define DEBUG_TYPE "module-summary-analysis"
31 // Walk through the operands of a given User via worklist iteration and populate
32 // the set of GlobalValue references encountered. Invoked either on an
33 // Instruction or a GlobalVariable (which walks its initializer).
34 static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges,
35 SmallPtrSet<const User *, 8> &Visited) {
36 SmallVector<const User *, 32> Worklist;
37 Worklist.push_back(CurUser);
39 while (!Worklist.empty()) {
40 const User *U = Worklist.pop_back_val();
42 if (!Visited.insert(U).second)
45 ImmutableCallSite CS(U);
47 for (const auto &OI : U->operands()) {
48 const User *Operand = dyn_cast<User>(OI);
51 if (isa<BlockAddress>(Operand))
53 if (isa<GlobalValue>(Operand)) {
54 // We have a reference to a global value. This should be added to
55 // the reference set unless it is a callee. Callees are handled
56 // specially by WriteFunction and are added to a separate list.
57 if (!(CS && CS.isCallee(&OI)))
58 RefEdges.insert(Operand);
61 Worklist.push_back(Operand);
66 void ModuleSummaryIndexBuilder::computeFunctionSummary(
67 const Function &F, BlockFrequencyInfo *BFI) {
68 // Summary not currently supported for anonymous functions, they must
73 unsigned NumInsts = 0;
74 // Map from callee ValueId to profile count. Used to accumulate profile
75 // counts for all static calls to a given callee.
76 DenseMap<const Value *, CalleeInfo> CallGraphEdges;
77 DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges;
78 DenseSet<const Value *> RefEdges;
79 ICallPromotionAnalysis ICallAnalysis;
81 SmallPtrSet<const User *, 8> Visited;
82 for (const BasicBlock &BB : F)
83 for (const Instruction &I : BB) {
84 if (!isa<DbgInfoIntrinsic>(I))
87 if (auto CS = ImmutableCallSite(&I)) {
88 auto *CalledFunction = CS.getCalledFunction();
89 // Check if this is a direct call to a known function.
91 if (CalledFunction->hasName() && !CalledFunction->isIntrinsic()) {
92 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
94 M->getValueSymbolTable().lookup(CalledFunction->getName());
95 CallGraphEdges[CalleeId] +=
96 (ScaledCount ? ScaledCount.getValue() : 0);
99 // Otherwise, check for an indirect call (call to a non-const value
100 // that isn't an inline assembly call).
101 const CallInst *CI = dyn_cast<CallInst>(&I);
102 if (CS.getCalledValue() && !isa<Constant>(CS.getCalledValue()) &&
103 !(CI && CI->isInlineAsm())) {
104 uint32_t NumVals, NumCandidates;
106 auto CandidateProfileData =
107 ICallAnalysis.getPromotionCandidatesForInstruction(
108 &I, NumVals, TotalCount, NumCandidates);
109 for (auto &Candidate : CandidateProfileData)
110 IndirectCallEdges[Candidate.Value] += Candidate.Count;
114 findRefEdges(&I, RefEdges, Visited);
117 GlobalValueSummary::GVFlags Flags(F);
118 std::unique_ptr<FunctionSummary> FuncSummary =
119 llvm::make_unique<FunctionSummary>(Flags, NumInsts);
120 FuncSummary->addCallGraphEdges(CallGraphEdges);
121 FuncSummary->addCallGraphEdges(IndirectCallEdges);
122 FuncSummary->addRefEdges(RefEdges);
123 Index->addGlobalValueSummary(F.getName(), std::move(FuncSummary));
126 void ModuleSummaryIndexBuilder::computeVariableSummary(
127 const GlobalVariable &V) {
128 DenseSet<const Value *> RefEdges;
129 SmallPtrSet<const User *, 8> Visited;
130 findRefEdges(&V, RefEdges, Visited);
131 GlobalValueSummary::GVFlags Flags(V);
132 std::unique_ptr<GlobalVarSummary> GVarSummary =
133 llvm::make_unique<GlobalVarSummary>(Flags);
134 GVarSummary->addRefEdges(RefEdges);
135 Index->addGlobalValueSummary(V.getName(), std::move(GVarSummary));
138 ModuleSummaryIndexBuilder::ModuleSummaryIndexBuilder(
140 std::function<BlockFrequencyInfo *(const Function &F)> Ftor)
141 : Index(llvm::make_unique<ModuleSummaryIndex>()), M(M) {
142 // Check if the module can be promoted, otherwise just disable importing from
143 // it by not emitting any summary.
144 // FIXME: we could still import *into* it most of the time.
145 if (!moduleCanBeRenamedForThinLTO(*M))
148 // Compute summaries for all functions defined in module, and save in the
151 if (F.isDeclaration())
154 BlockFrequencyInfo *BFI = nullptr;
155 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
158 else if (F.getEntryCount().hasValue()) {
159 LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
160 BranchProbabilityInfo BPI{F, LI};
161 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
165 computeFunctionSummary(F, BFI);
168 // Compute summaries for all variables defined in module, and save in the
170 for (const GlobalVariable &G : M->globals()) {
171 if (G.isDeclaration())
173 computeVariableSummary(G);
177 char ModuleSummaryIndexWrapperPass::ID = 0;
178 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
179 "Module Summary Analysis", false, true)
180 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
181 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
182 "Module Summary Analysis", false, true)
184 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
185 return new ModuleSummaryIndexWrapperPass();
188 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
190 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
193 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
194 IndexBuilder = llvm::make_unique<ModuleSummaryIndexBuilder>(
195 &M, [this](const Function &F) {
196 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
197 *const_cast<Function *>(&F))
203 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
204 IndexBuilder.reset();
208 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
209 AU.setPreservesAll();
210 AU.addRequired<BlockFrequencyInfoWrapperPass>();
213 bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) {
214 // We cannot currently promote or rename anything used in inline assembly,
215 // which are not visible to the compiler. Detect a possible case by looking
216 // for a llvm.used local value, in conjunction with an inline assembly call
217 // in the module. Prevent importing of any modules containing these uses by
218 // suppressing generation of the index. This also prevents importing
219 // into this module, which is also necessary to avoid needing to rename
220 // in case of a name clash between a local in this module and an imported
222 // FIXME: If we find we need a finer-grained approach of preventing promotion
223 // and renaming of just the functions using inline assembly we will need to:
224 // - Add flag in the function summaries to identify those with inline asm.
225 // - Prevent importing of any functions with flag set.
226 // - Prevent importing of any global function with the same name as a
227 // function in current module that has the flag set.
228 // - For any llvm.used value that is exported and promoted, add a private
229 // alias to the original name in the current module (even if we don't
230 // export the function using those values in inline asm, another function
231 // with a reference could be exported).
232 SmallPtrSet<GlobalValue *, 8> Used;
233 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
235 llvm::any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); });
239 // Walk all the instructions in the module and find if one is inline ASM
240 auto HasInlineAsm = llvm::any_of(M, [](const Function &F) {
241 return llvm::any_of(instructions(F), [](const Instruction &I) {
242 const CallInst *CallI = dyn_cast<CallInst>(&I);
245 return CallI->isInlineAsm();
248 return !HasInlineAsm;