Mercurial > hg > CbC > CbC_llvm

comparison lib/Analysis/ModuleSummaryAnalysis.cpp @ 120:1172e4bd9c6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 4.0.0
author mir3636
date Fri, 25 Nov 2016 19:14:25 +0900
parents
children 803732b1fca8
comparison
equal deleted inserted replaced
101:34baf5011add 120:1172e4bd9c6f
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/ADT/Triple.h"
17 #include "llvm/Analysis/BlockFrequencyInfo.h"
18 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
19 #include "llvm/Analysis/BranchProbabilityInfo.h"
20 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/ProfileSummaryInfo.h"
23 #include "llvm/IR/CallSite.h"
24 #include "llvm/IR/Dominators.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/ValueSymbolTable.h"
28 #include "llvm/Object/IRObjectFile.h"
29 #include "llvm/Pass.h"
30 using namespace llvm;
31
32 #define DEBUG_TYPE "module-summary-analysis"
33
34 // Walk through the operands of a given User via worklist iteration and populate
35 // the set of GlobalValue references encountered. Invoked either on an
36 // Instruction or a GlobalVariable (which walks its initializer).
37 static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges,
38 SmallPtrSet<const User *, 8> &Visited) {
39 SmallVector<const User *, 32> Worklist;
40 Worklist.push_back(CurUser);
41
42 while (!Worklist.empty()) {
43 const User *U = Worklist.pop_back_val();
44
45 if (!Visited.insert(U).second)
46 continue;
47
48 ImmutableCallSite CS(U);
49
50 for (const auto &OI : U->operands()) {
51 const User *Operand = dyn_cast<User>(OI);
52 if (!Operand)
53 continue;
54 if (isa<BlockAddress>(Operand))
55 continue;
56 if (isa<GlobalValue>(Operand)) {
57 // We have a reference to a global value. This should be added to
58 // the reference set unless it is a callee. Callees are handled
59 // specially by WriteFunction and are added to a separate list.
60 if (!(CS && CS.isCallee(&OI)))
61 RefEdges.insert(Operand);
62 continue;
63 }
64 Worklist.push_back(Operand);
65 }
66 }
67 }
68
69 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
70 ProfileSummaryInfo *PSI) {
71 if (!PSI)
72 return CalleeInfo::HotnessType::Unknown;
73 if (PSI->isHotCount(ProfileCount))
74 return CalleeInfo::HotnessType::Hot;
75 if (PSI->isColdCount(ProfileCount))
76 return CalleeInfo::HotnessType::Cold;
77 return CalleeInfo::HotnessType::None;
78 }
79
80 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
81 const Function &F, BlockFrequencyInfo *BFI,
82 ProfileSummaryInfo *PSI,
83 bool HasLocalsInUsed) {
84 // Summary not currently supported for anonymous functions, they should
85 // have been named.
86 assert(F.hasName());
87
88 unsigned NumInsts = 0;
89 // Map from callee ValueId to profile count. Used to accumulate profile
90 // counts for all static calls to a given callee.
91 DenseMap<const Value *, CalleeInfo> CallGraphEdges;
92 DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges;
93 DenseSet<const Value *> RefEdges;
94 ICallPromotionAnalysis ICallAnalysis;
95
96 bool HasInlineAsmMaybeReferencingInternal = false;
97 SmallPtrSet<const User *, 8> Visited;
98 for (const BasicBlock &BB : F)
99 for (const Instruction &I : BB) {
100 if (isa<DbgInfoIntrinsic>(I))
101 continue;
102 ++NumInsts;
103 findRefEdges(&I, RefEdges, Visited);
104 auto CS = ImmutableCallSite(&I);
105 if (!CS)
106 continue;
107
108 const auto *CI = dyn_cast<CallInst>(&I);
109 // Since we don't know exactly which local values are referenced in inline
110 // assembly, conservatively mark the function as possibly referencing
111 // a local value from inline assembly to ensure we don't export a
112 // reference (which would require renaming and promotion of the
113 // referenced value).
114 if (HasLocalsInUsed && CI && CI->isInlineAsm())
115 HasInlineAsmMaybeReferencingInternal = true;
116
117 auto *CalledValue = CS.getCalledValue();
118 auto *CalledFunction = CS.getCalledFunction();
119 // Check if this is an alias to a function. If so, get the
120 // called aliasee for the checks below.
121 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
122 assert(!CalledFunction && "Expected null called function in callsite for alias");
123 CalledFunction = dyn_cast<Function>(GA->getBaseObject());
124 }
125 // Check if this is a direct call to a known function.
126 if (CalledFunction) {
127 // Skip intrinsics.
128 if (CalledFunction->isIntrinsic())
129 continue;
130 // We should have named any anonymous globals
131 assert(CalledFunction->hasName());
132 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
133 // Use the original CalledValue, in case it was an alias. We want
134 // to record the call edge to the alias in that case. Eventually
135 // an alias summary will be created to associate the alias and
136 // aliasee.
137 auto *CalleeId =
138 M.getValueSymbolTable().lookup(CalledValue->getName());
139
140 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
141 : CalleeInfo::HotnessType::Unknown;
142 CallGraphEdges[CalleeId].updateHotness(Hotness);
143 } else {
144 // Skip inline assembly calls.
145 if (CI && CI->isInlineAsm())
146 continue;
147 // Skip direct calls.
148 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
149 continue;
150
151 uint32_t NumVals, NumCandidates;
152 uint64_t TotalCount;
153 auto CandidateProfileData =
154 ICallAnalysis.getPromotionCandidatesForInstruction(
155 &I, NumVals, TotalCount, NumCandidates);
156 for (auto &Candidate : CandidateProfileData)
157 IndirectCallEdges[Candidate.Value].updateHotness(
158 getHotness(Candidate.Count, PSI));
159 }
160 }
161
162 GlobalValueSummary::GVFlags Flags(F);
163 std::unique_ptr<FunctionSummary> FuncSummary =
164 llvm::make_unique<FunctionSummary>(Flags, NumInsts);
165 FuncSummary->addCallGraphEdges(CallGraphEdges);
166 FuncSummary->addCallGraphEdges(IndirectCallEdges);
167 FuncSummary->addRefEdges(RefEdges);
168 if (HasInlineAsmMaybeReferencingInternal)
169 FuncSummary->setHasInlineAsmMaybeReferencingInternal();
170 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
171 }
172
173 static void computeVariableSummary(ModuleSummaryIndex &Index,
174 const GlobalVariable &V) {
175 DenseSet<const Value *> RefEdges;
176 SmallPtrSet<const User *, 8> Visited;
177 findRefEdges(&V, RefEdges, Visited);
178 GlobalValueSummary::GVFlags Flags(V);
179 std::unique_ptr<GlobalVarSummary> GVarSummary =
180 llvm::make_unique<GlobalVarSummary>(Flags);
181 GVarSummary->addRefEdges(RefEdges);
182 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
183 }
184
185 static void computeAliasSummary(ModuleSummaryIndex &Index,
186 const GlobalAlias &A) {
187 GlobalValueSummary::GVFlags Flags(A);
188 std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags);
189 auto *Aliasee = A.getBaseObject();
190 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
191 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
192 AS->setAliasee(AliaseeSummary);
193 Index.addGlobalValueSummary(A.getName(), std::move(AS));
194 }
195
196 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
197 const Module &M,
198 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
199 ProfileSummaryInfo *PSI) {
200 ModuleSummaryIndex Index;
201
202 // Identify the local values in the llvm.used and llvm.compiler.used sets,
203 // which should not be exported as they would then require renaming and
204 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
205 // here because we use this information to mark functions containing inline
206 // assembly calls as not importable.
207 SmallPtrSet<GlobalValue *, 8> LocalsUsed;
208 SmallPtrSet<GlobalValue *, 8> Used;
209 // First collect those in the llvm.used set.
210 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
211 for (auto *V : Used) {
212 if (V->hasLocalLinkage())
213 LocalsUsed.insert(V);
214 }
215 Used.clear();
216 // Next collect those in the llvm.compiler.used set.
217 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
218 for (auto *V : Used) {
219 if (V->hasLocalLinkage())
220 LocalsUsed.insert(V);
221 }
222
223 // Compute summaries for all functions defined in module, and save in the
224 // index.
225 for (auto &F : M) {
226 if (F.isDeclaration())
227 continue;
228
229 BlockFrequencyInfo *BFI = nullptr;
230 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
231 if (GetBFICallback)
232 BFI = GetBFICallback(F);
233 else if (F.getEntryCount().hasValue()) {
234 LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
235 BranchProbabilityInfo BPI{F, LI};
236 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
237 BFI = BFIPtr.get();
238 }
239
240 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty());
241 }
242
243 // Compute summaries for all variables defined in module, and save in the
244 // index.
245 for (const GlobalVariable &G : M.globals()) {
246 if (G.isDeclaration())
247 continue;
248 computeVariableSummary(Index, G);
249 }
250
251 // Compute summaries for all aliases defined in module, and save in the
252 // index.
253 for (const GlobalAlias &A : M.aliases())
254 computeAliasSummary(Index, A);
255
256 for (auto *V : LocalsUsed) {
257 auto *Summary = Index.getGlobalValueSummary(*V);
258 assert(Summary && "Missing summary for global value");
259 Summary->setNoRename();
260 }
261
262 if (!M.getModuleInlineAsm().empty()) {
263 // Collect the local values defined by module level asm, and set up
264 // summaries for these symbols so that they can be marked as NoRename,
265 // to prevent export of any use of them in regular IR that would require
266 // renaming within the module level asm. Note we don't need to create a
267 // summary for weak or global defs, as they don't need to be flagged as
268 // NoRename, and defs in module level asm can't be imported anyway.
269 // Also, any values used but not defined within module level asm should
270 // be listed on the llvm.used or llvm.compiler.used global and marked as
271 // referenced from there.
272 // FIXME: Rename CollectAsmUndefinedRefs to something more general, as we
273 // are also using it to find the file-scope locals defined in module asm.
274 object::IRObjectFile::CollectAsmUndefinedRefs(
275 Triple(M.getTargetTriple()), M.getModuleInlineAsm(),
276 [&M, &Index](StringRef Name, object::BasicSymbolRef::Flags Flags) {
277 // Symbols not marked as Weak or Global are local definitions.
278 if (Flags & (object::BasicSymbolRef::SF_Weak ||
279 object::BasicSymbolRef::SF_Global))
280 return;
281 GlobalValue *GV = M.getNamedValue(Name);
282 if (!GV)
283 return;
284 assert(GV->isDeclaration() && "Def in module asm already has definition");
285 GlobalValueSummary::GVFlags GVFlags(
286 GlobalValue::InternalLinkage,
287 /* NoRename */ true,
288 /* HasInlineAsmMaybeReferencingInternal */ false,
289 /* IsNotViableToInline */ true);
290 // Create the appropriate summary type.
291 if (isa<Function>(GV)) {
292 std::unique_ptr<FunctionSummary> Summary =
293 llvm::make_unique<FunctionSummary>(GVFlags, 0);
294 Summary->setNoRename();
295 Index.addGlobalValueSummary(Name, std::move(Summary));
296 } else {
297 std::unique_ptr<GlobalVarSummary> Summary =
298 llvm::make_unique<GlobalVarSummary>(GVFlags);
299 Summary->setNoRename();
300 Index.addGlobalValueSummary(Name, std::move(Summary));
301 }
302 });
303 }
304
305 return Index;
306 }
307
308 AnalysisKey ModuleSummaryIndexAnalysis::Key;
309
310 ModuleSummaryIndex
311 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
312 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
313 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
314 return buildModuleSummaryIndex(
315 M,
316 [&FAM](const Function &F) {
317 return &FAM.getResult<BlockFrequencyAnalysis>(
318 *const_cast<Function *>(&F));
319 },
320 &PSI);
321 }
322
323 char ModuleSummaryIndexWrapperPass::ID = 0;
324 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
325 "Module Summary Analysis", false, true)
326 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
327 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
328 "Module Summary Analysis", false, true)
329
330 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
331 return new ModuleSummaryIndexWrapperPass();
332 }
333
334 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
335 : ModulePass(ID) {
336 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
337 }
338
339 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
340 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
341 Index = buildModuleSummaryIndex(
342 M,
343 [this](const Function &F) {
344 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
345 *const_cast<Function *>(&F))
346 .getBFI());
347 },
348 &PSI);
349 return false;
350 }
351
352 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
353 Index.reset();
354 return false;
355 }
356
357 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
358 AU.setPreservesAll();
359 AU.addRequired<BlockFrequencyInfoWrapperPass>();
360 AU.addRequired<ProfileSummaryInfoWrapperPass>();
361 }