1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass builds a ModuleSummaryIndex object for the module, to be written
11 // to bitcode or LLVM assembly.
12 //
13 //===----------------------------------------------------------------------===//
14 
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"
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "module-summary-analysis"
30 
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);
38 
39   while (!Worklist.empty()) {
40     const User *U = Worklist.pop_back_val();
41 
42     if (!Visited.insert(U).second)
43       continue;
44 
45     ImmutableCallSite CS(U);
46 
47     for (const auto &OI : U->operands()) {
48       const User *Operand = dyn_cast<User>(OI);
49       if (!Operand)
50         continue;
51       if (isa<BlockAddress>(Operand))
52         continue;
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);
59         continue;
60       }
61       Worklist.push_back(Operand);
62     }
63   }
64 }
65 
66 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
67                                    const Function &F, BlockFrequencyInfo *BFI) {
68   // Summary not currently supported for anonymous functions, they must
69   // be renamed.
70   if (!F.hasName())
71     return;
72 
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;
80 
81   SmallPtrSet<const User *, 8> Visited;
82   for (const BasicBlock &BB : F)
83     for (const Instruction &I : BB) {
84       if (isa<DbgInfoIntrinsic>(I))
85         continue;
86       ++NumInsts;
87       findRefEdges(&I, RefEdges, Visited);
88       auto CS = ImmutableCallSite(&I);
89       if (!CS)
90         continue;
91       auto *CalledFunction = CS.getCalledFunction();
92       // Check if this is a direct call to a known function.
93       if (CalledFunction) {
94         // Skip nameless and intrinsics.
95         if (!CalledFunction->hasName() || CalledFunction->isIntrinsic())
96           continue;
97         auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
98         auto *CalleeId =
99             M.getValueSymbolTable().lookup(CalledFunction->getName());
100         CallGraphEdges[CalleeId] += (ScaledCount ? ScaledCount.getValue() : 0);
101       } else {
102         const auto *CI = dyn_cast<CallInst>(&I);
103         // Skip inline assembly calls.
104         if (CI && CI->isInlineAsm())
105           continue;
106         // Skip direct calls.
107         if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
108           continue;
109 
110         uint32_t NumVals, NumCandidates;
111         uint64_t TotalCount;
112         auto CandidateProfileData =
113             ICallAnalysis.getPromotionCandidatesForInstruction(
114                 &I, NumVals, TotalCount, NumCandidates);
115         for (auto &Candidate : CandidateProfileData)
116           IndirectCallEdges[Candidate.Value] += Candidate.Count;
117       }
118     }
119 
120   GlobalValueSummary::GVFlags Flags(F);
121   std::unique_ptr<FunctionSummary> FuncSummary =
122       llvm::make_unique<FunctionSummary>(Flags, NumInsts);
123   FuncSummary->addCallGraphEdges(CallGraphEdges);
124   FuncSummary->addCallGraphEdges(IndirectCallEdges);
125   FuncSummary->addRefEdges(RefEdges);
126   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
127 }
128 
129 static void computeVariableSummary(ModuleSummaryIndex &Index,
130                                    const GlobalVariable &V) {
131   DenseSet<const Value *> RefEdges;
132   SmallPtrSet<const User *, 8> Visited;
133   findRefEdges(&V, RefEdges, Visited);
134   GlobalValueSummary::GVFlags Flags(V);
135   std::unique_ptr<GlobalVarSummary> GVarSummary =
136       llvm::make_unique<GlobalVarSummary>(Flags);
137   GVarSummary->addRefEdges(RefEdges);
138   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
139 }
140 
141 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
142     const Module &M,
143     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback) {
144   ModuleSummaryIndex Index;
145   // Check if the module can be promoted, otherwise just disable importing from
146   // it by not emitting any summary.
147   // FIXME: we could still import *into* it most of the time.
148   if (!moduleCanBeRenamedForThinLTO(M))
149     return Index;
150 
151   // Compute summaries for all functions defined in module, and save in the
152   // index.
153   for (auto &F : M) {
154     if (F.isDeclaration())
155       continue;
156 
157     BlockFrequencyInfo *BFI = nullptr;
158     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
159     if (GetBFICallback)
160       BFI = GetBFICallback(F);
161     else if (F.getEntryCount().hasValue()) {
162       LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
163       BranchProbabilityInfo BPI{F, LI};
164       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
165       BFI = BFIPtr.get();
166     }
167 
168     computeFunctionSummary(Index, M, F, BFI);
169   }
170 
171   // Compute summaries for all variables defined in module, and save in the
172   // index.
173   for (const GlobalVariable &G : M.globals()) {
174     if (G.isDeclaration())
175       continue;
176     computeVariableSummary(Index, G);
177   }
178   return Index;
179 }
180 
181 char ModuleSummaryIndexAnalysis::PassID;
182 
183 ModuleSummaryIndex
184 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
185   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
186   return buildModuleSummaryIndex(M, [&FAM](const Function &F) {
187     return &FAM.getResult<BlockFrequencyAnalysis>(*const_cast<Function *>(&F));
188   });
189 }
190 
191 char ModuleSummaryIndexWrapperPass::ID = 0;
192 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
193                       "Module Summary Analysis", false, true)
194 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
195 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
196                     "Module Summary Analysis", false, true)
197 
198 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
199   return new ModuleSummaryIndexWrapperPass();
200 }
201 
202 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
203     : ModulePass(ID) {
204   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
205 }
206 
207 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
208   Index = buildModuleSummaryIndex(M, [this](const Function &F) {
209     return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
210                      *const_cast<Function *>(&F))
211                  .getBFI());
212   });
213   return false;
214 }
215 
216 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
217   Index.reset();
218   return false;
219 }
220 
221 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
222   AU.setPreservesAll();
223   AU.addRequired<BlockFrequencyInfoWrapperPass>();
224 }
225 
226 bool llvm::moduleCanBeRenamedForThinLTO(const Module &M) {
227   // We cannot currently promote or rename anything used in inline assembly,
228   // which are not visible to the compiler. Detect a possible case by looking
229   // for a llvm.used local value, in conjunction with an inline assembly call
230   // in the module. Prevent importing of any modules containing these uses by
231   // suppressing generation of the index. This also prevents importing
232   // into this module, which is also necessary to avoid needing to rename
233   // in case of a name clash between a local in this module and an imported
234   // global.
235   // FIXME: If we find we need a finer-grained approach of preventing promotion
236   // and renaming of just the functions using inline assembly we will need to:
237   // - Add flag in the function summaries to identify those with inline asm.
238   // - Prevent importing of any functions with flag set.
239   // - Prevent importing of any global function with the same name as a
240   //   function in current module that has the flag set.
241   // - For any llvm.used value that is exported and promoted, add a private
242   //   alias to the original name in the current module (even if we don't
243   //   export the function using those values in inline asm, another function
244   //   with a reference could be exported).
245   SmallPtrSet<GlobalValue *, 8> Used;
246   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
247   bool LocalIsUsed =
248       any_of(Used, [](GlobalValue *V) { return V->hasLocalLinkage(); });
249   if (!LocalIsUsed)
250     return true;
251 
252   // Walk all the instructions in the module and find if one is inline ASM
253   auto HasInlineAsm = any_of(M, [](const Function &F) {
254     return any_of(instructions(F), [](const Instruction &I) {
255       const CallInst *CallI = dyn_cast<CallInst>(&I);
256       if (!CallI)
257         return false;
258       return CallI->isInlineAsm();
259     });
260   });
261   return !HasInlineAsm;
262 }
263