OSDN Git Service

[ThinLTO] Add an auto-hide feature
[android-x86/external-llvm.git] / lib / Analysis / ModuleSummaryAnalysis.cpp
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/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/IRObjectFile.h"
32 #include "llvm/Pass.h"
33 using namespace llvm;
34
35 #define DEBUG_TYPE "module-summary-analysis"
36
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);
44
45   while (!Worklist.empty()) {
46     const User *U = Worklist.pop_back_val();
47
48     if (!Visited.insert(U).second)
49       continue;
50
51     ImmutableCallSite CS(U);
52
53     for (const auto &OI : U->operands()) {
54       const User *Operand = dyn_cast<User>(OI);
55       if (!Operand)
56         continue;
57       if (isa<BlockAddress>(Operand))
58         continue;
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)))
64           RefEdges.insert(GV);
65         continue;
66       }
67       Worklist.push_back(Operand);
68     }
69   }
70 }
71
72 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
73                                           ProfileSummaryInfo *PSI) {
74   if (!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;
81 }
82
83 static bool isNonRenamableLocal(const GlobalValue &GV) {
84   return GV.hasSection() && GV.hasLocalLinkage();
85 }
86
87 static void
88 computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
89                        const Function &F, BlockFrequencyInfo *BFI,
90                        ProfileSummaryInfo *PSI, bool HasLocalsInUsed,
91                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
92   // Summary not currently supported for anonymous functions, they should
93   // have been named.
94   assert(F.hasName());
95
96   unsigned NumInsts = 0;
97   // Map from callee ValueId to profile count. Used to accumulate profile
98   // counts for all static calls to a given callee.
99   MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
100   SetVector<ValueInfo> RefEdges;
101   SetVector<GlobalValue::GUID> TypeTests;
102   ICallPromotionAnalysis ICallAnalysis;
103
104   bool HasInlineAsmMaybeReferencingInternal = false;
105   SmallPtrSet<const User *, 8> Visited;
106   for (const BasicBlock &BB : F)
107     for (const Instruction &I : BB) {
108       if (isa<DbgInfoIntrinsic>(I))
109         continue;
110       ++NumInsts;
111       findRefEdges(&I, RefEdges, Visited);
112       auto CS = ImmutableCallSite(&I);
113       if (!CS)
114         continue;
115
116       const auto *CI = dyn_cast<CallInst>(&I);
117       // Since we don't know exactly which local values are referenced in inline
118       // assembly, conservatively mark the function as possibly referencing
119       // a local value from inline assembly to ensure we don't export a
120       // reference (which would require renaming and promotion of the
121       // referenced value).
122       if (HasLocalsInUsed && CI && CI->isInlineAsm())
123         HasInlineAsmMaybeReferencingInternal = true;
124
125       auto *CalledValue = CS.getCalledValue();
126       auto *CalledFunction = CS.getCalledFunction();
127       // Check if this is an alias to a function. If so, get the
128       // called aliasee for the checks below.
129       if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
130         assert(!CalledFunction && "Expected null called function in callsite for alias");
131         CalledFunction = dyn_cast<Function>(GA->getBaseObject());
132       }
133       // Check if this is a direct call to a known function or a known
134       // intrinsic, or an indirect call with profile data.
135       if (CalledFunction) {
136         if (CalledFunction->isIntrinsic()) {
137           if (CalledFunction->getIntrinsicID() != Intrinsic::type_test)
138             continue;
139           // Produce a summary from type.test intrinsics. We only summarize
140           // type.test intrinsics that are used other than by an llvm.assume
141           // intrinsic. Intrinsics that are assumed are relevant only to the
142           // devirtualization pass, not the type test lowering pass.
143           bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
144             auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
145             if (!AssumeCI)
146               return true;
147             Function *F = AssumeCI->getCalledFunction();
148             return !F || F->getIntrinsicID() != Intrinsic::assume;
149           });
150           if (HasNonAssumeUses) {
151             auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
152             if (auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()))
153               TypeTests.insert(GlobalValue::getGUID(TypeId->getString()));
154           }
155         }
156         // We should have named any anonymous globals
157         assert(CalledFunction->hasName());
158         auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None;
159         auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
160                                    : CalleeInfo::HotnessType::Unknown;
161
162         // Use the original CalledValue, in case it was an alias. We want
163         // to record the call edge to the alias in that case. Eventually
164         // an alias summary will be created to associate the alias and
165         // aliasee.
166         CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
167       } else {
168         // Skip inline assembly calls.
169         if (CI && CI->isInlineAsm())
170           continue;
171         // Skip direct calls.
172         if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
173           continue;
174
175         uint32_t NumVals, NumCandidates;
176         uint64_t TotalCount;
177         auto CandidateProfileData =
178             ICallAnalysis.getPromotionCandidatesForInstruction(
179                 &I, NumVals, TotalCount, NumCandidates);
180         for (auto &Candidate : CandidateProfileData)
181           CallGraphEdges[Candidate.Value].updateHotness(
182               getHotness(Candidate.Count, PSI));
183       }
184     }
185
186   bool NonRenamableLocal = isNonRenamableLocal(F);
187   bool NotEligibleForImport =
188       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
189       // Inliner doesn't handle variadic functions.
190       // FIXME: refactor this to use the same code that inliner is using.
191       F.isVarArg();
192   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
193                                     /* LiveRoot = */ false,
194                                     /* AutoHide */ false);
195   auto FuncSummary = llvm::make_unique<FunctionSummary>(
196       Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(),
197       TypeTests.takeVector());
198   if (NonRenamableLocal)
199     CantBePromoted.insert(F.getGUID());
200   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
201 }
202
203 static void
204 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
205                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
206   SetVector<ValueInfo> RefEdges;
207   SmallPtrSet<const User *, 8> Visited;
208   findRefEdges(&V, RefEdges, Visited);
209   bool NonRenamableLocal = isNonRenamableLocal(V);
210   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
211                                     /* LiveRoot = */ false,
212                                     /* AutoHide */ false);
213   auto GVarSummary =
214       llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
215   if (NonRenamableLocal)
216     CantBePromoted.insert(V.getGUID());
217   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
218 }
219
220 static void
221 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
222                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
223   bool NonRenamableLocal = isNonRenamableLocal(A);
224   GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
225                                     /* LiveRoot = */ false,
226                                     /* AutoHide */ false);
227   auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
228   auto *Aliasee = A.getBaseObject();
229   auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
230   assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
231   AS->setAliasee(AliaseeSummary);
232   if (NonRenamableLocal)
233     CantBePromoted.insert(A.getGUID());
234   Index.addGlobalValueSummary(A.getName(), std::move(AS));
235 }
236
237 // Set LiveRoot flag on entries matching the given value name.
238 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
239   auto SummaryList =
240       Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name));
241   if (SummaryList == Index.end())
242     return;
243   for (auto &Summary : SummaryList->second)
244     Summary->setLiveRoot();
245 }
246
247 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
248     const Module &M,
249     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
250     ProfileSummaryInfo *PSI) {
251   ModuleSummaryIndex Index;
252
253   // Identify the local values in the llvm.used and llvm.compiler.used sets,
254   // which should not be exported as they would then require renaming and
255   // promotion, but we may have opaque uses e.g. in inline asm. We collect them
256   // here because we use this information to mark functions containing inline
257   // assembly calls as not importable.
258   SmallPtrSet<GlobalValue *, 8> LocalsUsed;
259   SmallPtrSet<GlobalValue *, 8> Used;
260   // First collect those in the llvm.used set.
261   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
262   // Next collect those in the llvm.compiler.used set.
263   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
264   DenseSet<GlobalValue::GUID> CantBePromoted;
265   for (auto *V : Used) {
266     if (V->hasLocalLinkage()) {
267       LocalsUsed.insert(V);
268       CantBePromoted.insert(V->getGUID());
269     }
270   }
271
272   // Compute summaries for all functions defined in module, and save in the
273   // index.
274   for (auto &F : M) {
275     if (F.isDeclaration())
276       continue;
277
278     BlockFrequencyInfo *BFI = nullptr;
279     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
280     if (GetBFICallback)
281       BFI = GetBFICallback(F);
282     else if (F.getEntryCount().hasValue()) {
283       LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
284       BranchProbabilityInfo BPI{F, LI};
285       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
286       BFI = BFIPtr.get();
287     }
288
289     computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(),
290                            CantBePromoted);
291   }
292
293   // Compute summaries for all variables defined in module, and save in the
294   // index.
295   for (const GlobalVariable &G : M.globals()) {
296     if (G.isDeclaration())
297       continue;
298     computeVariableSummary(Index, G, CantBePromoted);
299   }
300
301   // Compute summaries for all aliases defined in module, and save in the
302   // index.
303   for (const GlobalAlias &A : M.aliases())
304     computeAliasSummary(Index, A, CantBePromoted);
305
306   for (auto *V : LocalsUsed) {
307     auto *Summary = Index.getGlobalValueSummary(*V);
308     assert(Summary && "Missing summary for global value");
309     Summary->setNotEligibleToImport();
310   }
311
312   // The linker doesn't know about these LLVM produced values, so we need
313   // to flag them as live in the index to ensure index-based dead value
314   // analysis treats them as live roots of the analysis.
315   setLiveRoot(Index, "llvm.used");
316   setLiveRoot(Index, "llvm.compiler.used");
317   setLiveRoot(Index, "llvm.global_ctors");
318   setLiveRoot(Index, "llvm.global_dtors");
319   setLiveRoot(Index, "llvm.global.annotations");
320
321   if (!M.getModuleInlineAsm().empty()) {
322     // Collect the local values defined by module level asm, and set up
323     // summaries for these symbols so that they can be marked as NoRename,
324     // to prevent export of any use of them in regular IR that would require
325     // renaming within the module level asm. Note we don't need to create a
326     // summary for weak or global defs, as they don't need to be flagged as
327     // NoRename, and defs in module level asm can't be imported anyway.
328     // Also, any values used but not defined within module level asm should
329     // be listed on the llvm.used or llvm.compiler.used global and marked as
330     // referenced from there.
331     ModuleSymbolTable::CollectAsmSymbols(
332         Triple(M.getTargetTriple()), M.getModuleInlineAsm(),
333         [&M, &Index, &CantBePromoted](StringRef Name,
334                                       object::BasicSymbolRef::Flags Flags) {
335           // Symbols not marked as Weak or Global are local definitions.
336           if (Flags & (object::BasicSymbolRef::SF_Weak |
337                        object::BasicSymbolRef::SF_Global))
338             return;
339           GlobalValue *GV = M.getNamedValue(Name);
340           if (!GV)
341             return;
342           assert(GV->isDeclaration() && "Def in module asm already has definition");
343           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
344                                               /* NotEligibleToImport */ true,
345                                               /* LiveRoot */ true,
346                                               /* AutoHide */ false);
347           CantBePromoted.insert(GlobalValue::getGUID(Name));
348           // Create the appropriate summary type.
349           if (isa<Function>(GV)) {
350             std::unique_ptr<FunctionSummary> Summary =
351                 llvm::make_unique<FunctionSummary>(
352                     GVFlags, 0, ArrayRef<ValueInfo>{},
353                     ArrayRef<FunctionSummary::EdgeTy>{},
354                     ArrayRef<GlobalValue::GUID>{});
355             Index.addGlobalValueSummary(Name, std::move(Summary));
356           } else {
357             std::unique_ptr<GlobalVarSummary> Summary =
358                 llvm::make_unique<GlobalVarSummary>(GVFlags,
359                                                     ArrayRef<ValueInfo>{});
360             Index.addGlobalValueSummary(Name, std::move(Summary));
361           }
362         });
363   }
364
365   for (auto &GlobalList : Index) {
366     assert(GlobalList.second.size() == 1 &&
367            "Expected module's index to have one summary per GUID");
368     auto &Summary = GlobalList.second[0];
369     bool AllRefsCanBeExternallyReferenced =
370         llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
371           return !CantBePromoted.count(VI.getValue()->getGUID());
372         });
373     if (!AllRefsCanBeExternallyReferenced) {
374       Summary->setNotEligibleToImport();
375       continue;
376     }
377
378     if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
379       bool AllCallsCanBeExternallyReferenced = llvm::all_of(
380           FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
381             auto GUID = Edge.first.isGUID() ? Edge.first.getGUID()
382                                             : Edge.first.getValue()->getGUID();
383             return !CantBePromoted.count(GUID);
384           });
385       if (!AllCallsCanBeExternallyReferenced)
386         Summary->setNotEligibleToImport();
387     }
388   }
389
390   return Index;
391 }
392
393 AnalysisKey ModuleSummaryIndexAnalysis::Key;
394
395 ModuleSummaryIndex
396 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
397   ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
398   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
399   return buildModuleSummaryIndex(
400       M,
401       [&FAM](const Function &F) {
402         return &FAM.getResult<BlockFrequencyAnalysis>(
403             *const_cast<Function *>(&F));
404       },
405       &PSI);
406 }
407
408 char ModuleSummaryIndexWrapperPass::ID = 0;
409 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
410                       "Module Summary Analysis", false, true)
411 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
412 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
413 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
414                     "Module Summary Analysis", false, true)
415
416 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
417   return new ModuleSummaryIndexWrapperPass();
418 }
419
420 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
421     : ModulePass(ID) {
422   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
423 }
424
425 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
426   auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
427   Index = buildModuleSummaryIndex(
428       M,
429       [this](const Function &F) {
430         return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
431                          *const_cast<Function *>(&F))
432                      .getBFI());
433       },
434       &PSI);
435   return false;
436 }
437
438 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
439   Index.reset();
440   return false;
441 }
442
443 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
444   AU.setPreservesAll();
445   AU.addRequired<BlockFrequencyInfoWrapperPass>();
446   AU.addRequired<ProfileSummaryInfoWrapperPass>();
447 }