xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp (revision fe815331bb40604ba31312acf7e4619674631777)
1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass builds a ModuleSummaryIndex object for the module, to be written
10 // to bitcode or LLVM assembly.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/DenseSet.h"
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/StringRef.h"
23 #include "llvm/Analysis/BlockFrequencyInfo.h"
24 #include "llvm/Analysis/BranchProbabilityInfo.h"
25 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
26 #include "llvm/Analysis/LoopInfo.h"
27 #include "llvm/Analysis/ProfileSummaryInfo.h"
28 #include "llvm/Analysis/StackSafetyAnalysis.h"
29 #include "llvm/Analysis/TypeMetadataUtils.h"
30 #include "llvm/IR/Attributes.h"
31 #include "llvm/IR/BasicBlock.h"
32 #include "llvm/IR/Constant.h"
33 #include "llvm/IR/Constants.h"
34 #include "llvm/IR/Dominators.h"
35 #include "llvm/IR/Function.h"
36 #include "llvm/IR/GlobalAlias.h"
37 #include "llvm/IR/GlobalValue.h"
38 #include "llvm/IR/GlobalVariable.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/Intrinsics.h"
42 #include "llvm/IR/Metadata.h"
43 #include "llvm/IR/Module.h"
44 #include "llvm/IR/ModuleSummaryIndex.h"
45 #include "llvm/IR/Use.h"
46 #include "llvm/IR/User.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Object/ModuleSymbolTable.h"
49 #include "llvm/Object/SymbolicFile.h"
50 #include "llvm/Pass.h"
51 #include "llvm/Support/Casting.h"
52 #include "llvm/Support/CommandLine.h"
53 #include <algorithm>
54 #include <cassert>
55 #include <cstdint>
56 #include <vector>
57 
58 using namespace llvm;
59 
60 #define DEBUG_TYPE "module-summary-analysis"
61 
62 // Option to force edges cold which will block importing when the
63 // -import-cold-multiplier is set to 0. Useful for debugging.
64 FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold =
65     FunctionSummary::FSHT_None;
66 cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC(
67     "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold),
68     cl::desc("Force all edges in the function summary to cold"),
69     cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."),
70                clEnumValN(FunctionSummary::FSHT_AllNonCritical,
71                           "all-non-critical", "All non-critical edges."),
72                clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")));
73 
74 cl::opt<std::string> ModuleSummaryDotFile(
75     "module-summary-dot-file", cl::init(""), cl::Hidden,
76     cl::value_desc("filename"),
77     cl::desc("File to emit dot graph of new summary into."));
78 
79 // Walk through the operands of a given User via worklist iteration and populate
80 // the set of GlobalValue references encountered. Invoked either on an
81 // Instruction or a GlobalVariable (which walks its initializer).
82 // Return true if any of the operands contains blockaddress. This is important
83 // to know when computing summary for global var, because if global variable
84 // references basic block address we can't import it separately from function
85 // containing that basic block. For simplicity we currently don't import such
86 // global vars at all. When importing function we aren't interested if any
87 // instruction in it takes an address of any basic block, because instruction
88 // can only take an address of basic block located in the same function.
89 static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
90                          SetVector<ValueInfo> &RefEdges,
91                          SmallPtrSet<const User *, 8> &Visited) {
92   bool HasBlockAddress = false;
93   SmallVector<const User *, 32> Worklist;
94   Worklist.push_back(CurUser);
95 
96   while (!Worklist.empty()) {
97     const User *U = Worklist.pop_back_val();
98 
99     if (!Visited.insert(U).second)
100       continue;
101 
102     const auto *CB = dyn_cast<CallBase>(U);
103 
104     for (const auto &OI : U->operands()) {
105       const User *Operand = dyn_cast<User>(OI);
106       if (!Operand)
107         continue;
108       if (isa<BlockAddress>(Operand)) {
109         HasBlockAddress = true;
110         continue;
111       }
112       if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
113         // We have a reference to a global value. This should be added to
114         // the reference set unless it is a callee. Callees are handled
115         // specially by WriteFunction and are added to a separate list.
116         if (!(CB && CB->isCallee(&OI)))
117           RefEdges.insert(Index.getOrInsertValueInfo(GV));
118         continue;
119       }
120       Worklist.push_back(Operand);
121     }
122   }
123   return HasBlockAddress;
124 }
125 
126 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
127                                           ProfileSummaryInfo *PSI) {
128   if (!PSI)
129     return CalleeInfo::HotnessType::Unknown;
130   if (PSI->isHotCount(ProfileCount))
131     return CalleeInfo::HotnessType::Hot;
132   if (PSI->isColdCount(ProfileCount))
133     return CalleeInfo::HotnessType::Cold;
134   return CalleeInfo::HotnessType::None;
135 }
136 
137 static bool isNonRenamableLocal(const GlobalValue &GV) {
138   return GV.hasSection() && GV.hasLocalLinkage();
139 }
140 
141 /// Determine whether this call has all constant integer arguments (excluding
142 /// "this") and summarize it to VCalls or ConstVCalls as appropriate.
143 static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid,
144                           SetVector<FunctionSummary::VFuncId> &VCalls,
145                           SetVector<FunctionSummary::ConstVCall> &ConstVCalls) {
146   std::vector<uint64_t> Args;
147   // Start from the second argument to skip the "this" pointer.
148   for (auto &Arg : make_range(Call.CB.arg_begin() + 1, Call.CB.arg_end())) {
149     auto *CI = dyn_cast<ConstantInt>(Arg);
150     if (!CI || CI->getBitWidth() > 64) {
151       VCalls.insert({Guid, Call.Offset});
152       return;
153     }
154     Args.push_back(CI->getZExtValue());
155   }
156   ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
157 }
158 
159 /// If this intrinsic call requires that we add information to the function
160 /// summary, do so via the non-constant reference arguments.
161 static void addIntrinsicToSummary(
162     const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
163     SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
164     SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
165     SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
166     SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls,
167     DominatorTree &DT) {
168   switch (CI->getCalledFunction()->getIntrinsicID()) {
169   case Intrinsic::type_test: {
170     auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
171     auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
172     if (!TypeId)
173       break;
174     GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
175 
176     // Produce a summary from type.test intrinsics. We only summarize type.test
177     // intrinsics that are used other than by an llvm.assume intrinsic.
178     // Intrinsics that are assumed are relevant only to the devirtualization
179     // pass, not the type test lowering pass.
180     bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
181       auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
182       if (!AssumeCI)
183         return true;
184       Function *F = AssumeCI->getCalledFunction();
185       return !F || F->getIntrinsicID() != Intrinsic::assume;
186     });
187     if (HasNonAssumeUses)
188       TypeTests.insert(Guid);
189 
190     SmallVector<DevirtCallSite, 4> DevirtCalls;
191     SmallVector<CallInst *, 4> Assumes;
192     findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
193     for (auto &Call : DevirtCalls)
194       addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
195                     TypeTestAssumeConstVCalls);
196 
197     break;
198   }
199 
200   case Intrinsic::type_checked_load: {
201     auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
202     auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
203     if (!TypeId)
204       break;
205     GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
206 
207     SmallVector<DevirtCallSite, 4> DevirtCalls;
208     SmallVector<Instruction *, 4> LoadedPtrs;
209     SmallVector<Instruction *, 4> Preds;
210     bool HasNonCallUses = false;
211     findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
212                                                HasNonCallUses, CI, DT);
213     // Any non-call uses of the result of llvm.type.checked.load will
214     // prevent us from optimizing away the llvm.type.test.
215     if (HasNonCallUses)
216       TypeTests.insert(Guid);
217     for (auto &Call : DevirtCalls)
218       addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
219                     TypeCheckedLoadConstVCalls);
220 
221     break;
222   }
223   default:
224     break;
225   }
226 }
227 
228 static bool isNonVolatileLoad(const Instruction *I) {
229   if (const auto *LI = dyn_cast<LoadInst>(I))
230     return !LI->isVolatile();
231 
232   return false;
233 }
234 
235 static bool isNonVolatileStore(const Instruction *I) {
236   if (const auto *SI = dyn_cast<StoreInst>(I))
237     return !SI->isVolatile();
238 
239   return false;
240 }
241 
242 static void computeFunctionSummary(
243     ModuleSummaryIndex &Index, const Module &M, const Function &F,
244     BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, DominatorTree &DT,
245     bool HasLocalsInUsedOrAsm, DenseSet<GlobalValue::GUID> &CantBePromoted,
246     bool IsThinLTO,
247     std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) {
248   // Summary not currently supported for anonymous functions, they should
249   // have been named.
250   assert(F.hasName());
251 
252   unsigned NumInsts = 0;
253   // Map from callee ValueId to profile count. Used to accumulate profile
254   // counts for all static calls to a given callee.
255   MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
256   SetVector<ValueInfo> RefEdges, LoadRefEdges, StoreRefEdges;
257   SetVector<GlobalValue::GUID> TypeTests;
258   SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
259       TypeCheckedLoadVCalls;
260   SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
261       TypeCheckedLoadConstVCalls;
262   ICallPromotionAnalysis ICallAnalysis;
263   SmallPtrSet<const User *, 8> Visited;
264 
265   // Add personality function, prefix data and prologue data to function's ref
266   // list.
267   findRefEdges(Index, &F, RefEdges, Visited);
268   std::vector<const Instruction *> NonVolatileLoads;
269   std::vector<const Instruction *> NonVolatileStores;
270 
271   bool HasInlineAsmMaybeReferencingInternal = false;
272   for (const BasicBlock &BB : F)
273     for (const Instruction &I : BB) {
274       if (isa<DbgInfoIntrinsic>(I))
275         continue;
276       ++NumInsts;
277       // Regular LTO module doesn't participate in ThinLTO import,
278       // so no reference from it can be read/writeonly, since this
279       // would require importing variable as local copy
280       if (IsThinLTO) {
281         if (isNonVolatileLoad(&I)) {
282           // Postpone processing of non-volatile load instructions
283           // See comments below
284           Visited.insert(&I);
285           NonVolatileLoads.push_back(&I);
286           continue;
287         } else if (isNonVolatileStore(&I)) {
288           Visited.insert(&I);
289           NonVolatileStores.push_back(&I);
290           // All references from second operand of store (destination address)
291           // can be considered write-only if they're not referenced by any
292           // non-store instruction. References from first operand of store
293           // (stored value) can't be treated either as read- or as write-only
294           // so we add them to RefEdges as we do with all other instructions
295           // except non-volatile load.
296           Value *Stored = I.getOperand(0);
297           if (auto *GV = dyn_cast<GlobalValue>(Stored))
298             // findRefEdges will try to examine GV operands, so instead
299             // of calling it we should add GV to RefEdges directly.
300             RefEdges.insert(Index.getOrInsertValueInfo(GV));
301           else if (auto *U = dyn_cast<User>(Stored))
302             findRefEdges(Index, U, RefEdges, Visited);
303           continue;
304         }
305       }
306       findRefEdges(Index, &I, RefEdges, Visited);
307       const auto *CB = dyn_cast<CallBase>(&I);
308       if (!CB)
309         continue;
310 
311       const auto *CI = dyn_cast<CallInst>(&I);
312       // Since we don't know exactly which local values are referenced in inline
313       // assembly, conservatively mark the function as possibly referencing
314       // a local value from inline assembly to ensure we don't export a
315       // reference (which would require renaming and promotion of the
316       // referenced value).
317       if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm())
318         HasInlineAsmMaybeReferencingInternal = true;
319 
320       auto *CalledValue = CB->getCalledOperand();
321       auto *CalledFunction = CB->getCalledFunction();
322       if (CalledValue && !CalledFunction) {
323         CalledValue = CalledValue->stripPointerCasts();
324         // Stripping pointer casts can reveal a called function.
325         CalledFunction = dyn_cast<Function>(CalledValue);
326       }
327       // Check if this is an alias to a function. If so, get the
328       // called aliasee for the checks below.
329       if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
330         assert(!CalledFunction && "Expected null called function in callsite for alias");
331         CalledFunction = dyn_cast<Function>(GA->getBaseObject());
332       }
333       // Check if this is a direct call to a known function or a known
334       // intrinsic, or an indirect call with profile data.
335       if (CalledFunction) {
336         if (CI && CalledFunction->isIntrinsic()) {
337           addIntrinsicToSummary(
338               CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
339               TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT);
340           continue;
341         }
342         // We should have named any anonymous globals
343         assert(CalledFunction->hasName());
344         auto ScaledCount = PSI->getProfileCount(*CB, BFI);
345         auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
346                                    : CalleeInfo::HotnessType::Unknown;
347         if (ForceSummaryEdgesCold != FunctionSummary::FSHT_None)
348           Hotness = CalleeInfo::HotnessType::Cold;
349 
350         // Use the original CalledValue, in case it was an alias. We want
351         // to record the call edge to the alias in that case. Eventually
352         // an alias summary will be created to associate the alias and
353         // aliasee.
354         auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo(
355             cast<GlobalValue>(CalledValue))];
356         ValueInfo.updateHotness(Hotness);
357         // Add the relative block frequency to CalleeInfo if there is no profile
358         // information.
359         if (BFI != nullptr && Hotness == CalleeInfo::HotnessType::Unknown) {
360           uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency();
361           uint64_t EntryFreq = BFI->getEntryFreq();
362           ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq);
363         }
364       } else {
365         // Skip inline assembly calls.
366         if (CI && CI->isInlineAsm())
367           continue;
368         // Skip direct calls.
369         if (!CalledValue || isa<Constant>(CalledValue))
370           continue;
371 
372         // Check if the instruction has a callees metadata. If so, add callees
373         // to CallGraphEdges to reflect the references from the metadata, and
374         // to enable importing for subsequent indirect call promotion and
375         // inlining.
376         if (auto *MD = I.getMetadata(LLVMContext::MD_callees)) {
377           for (auto &Op : MD->operands()) {
378             Function *Callee = mdconst::extract_or_null<Function>(Op);
379             if (Callee)
380               CallGraphEdges[Index.getOrInsertValueInfo(Callee)];
381           }
382         }
383 
384         uint32_t NumVals, NumCandidates;
385         uint64_t TotalCount;
386         auto CandidateProfileData =
387             ICallAnalysis.getPromotionCandidatesForInstruction(
388                 &I, NumVals, TotalCount, NumCandidates);
389         for (auto &Candidate : CandidateProfileData)
390           CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
391               .updateHotness(getHotness(Candidate.Count, PSI));
392       }
393     }
394   Index.addBlockCount(F.size());
395 
396   std::vector<ValueInfo> Refs;
397   if (IsThinLTO) {
398     auto AddRefEdges = [&](const std::vector<const Instruction *> &Instrs,
399                            SetVector<ValueInfo> &Edges,
400                            SmallPtrSet<const User *, 8> &Cache) {
401       for (const auto *I : Instrs) {
402         Cache.erase(I);
403         findRefEdges(Index, I, Edges, Cache);
404       }
405     };
406 
407     // By now we processed all instructions in a function, except
408     // non-volatile loads and non-volatile value stores. Let's find
409     // ref edges for both of instruction sets
410     AddRefEdges(NonVolatileLoads, LoadRefEdges, Visited);
411     // We can add some values to the Visited set when processing load
412     // instructions which are also used by stores in NonVolatileStores.
413     // For example this can happen if we have following code:
414     //
415     // store %Derived* @foo, %Derived** bitcast (%Base** @bar to %Derived**)
416     // %42 = load %Derived*, %Derived** bitcast (%Base** @bar to %Derived**)
417     //
418     // After processing loads we'll add bitcast to the Visited set, and if
419     // we use the same set while processing stores, we'll never see store
420     // to @bar and @bar will be mistakenly treated as readonly.
421     SmallPtrSet<const llvm::User *, 8> StoreCache;
422     AddRefEdges(NonVolatileStores, StoreRefEdges, StoreCache);
423 
424     // If both load and store instruction reference the same variable
425     // we won't be able to optimize it. Add all such reference edges
426     // to RefEdges set.
427     for (auto &VI : StoreRefEdges)
428       if (LoadRefEdges.remove(VI))
429         RefEdges.insert(VI);
430 
431     unsigned RefCnt = RefEdges.size();
432     // All new reference edges inserted in two loops below are either
433     // read or write only. They will be grouped in the end of RefEdges
434     // vector, so we can use a single integer value to identify them.
435     for (auto &VI : LoadRefEdges)
436       RefEdges.insert(VI);
437 
438     unsigned FirstWORef = RefEdges.size();
439     for (auto &VI : StoreRefEdges)
440       RefEdges.insert(VI);
441 
442     Refs = RefEdges.takeVector();
443     for (; RefCnt < FirstWORef; ++RefCnt)
444       Refs[RefCnt].setReadOnly();
445 
446     for (; RefCnt < Refs.size(); ++RefCnt)
447       Refs[RefCnt].setWriteOnly();
448   } else {
449     Refs = RefEdges.takeVector();
450   }
451   // Explicit add hot edges to enforce importing for designated GUIDs for
452   // sample PGO, to enable the same inlines as the profiled optimized binary.
453   for (auto &I : F.getImportGUIDs())
454     CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
455         ForceSummaryEdgesCold == FunctionSummary::FSHT_All
456             ? CalleeInfo::HotnessType::Cold
457             : CalleeInfo::HotnessType::Critical);
458 
459   bool NonRenamableLocal = isNonRenamableLocal(F);
460   bool NotEligibleForImport =
461       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal;
462   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
463                                     /* Live = */ false, F.isDSOLocal(),
464                                     F.hasLinkOnceODRLinkage() && F.hasGlobalUnnamedAddr());
465   FunctionSummary::FFlags FunFlags{
466       F.hasFnAttribute(Attribute::ReadNone),
467       F.hasFnAttribute(Attribute::ReadOnly),
468       F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(),
469       // FIXME: refactor this to use the same code that inliner is using.
470       // Don't try to import functions with noinline attribute.
471       F.getAttributes().hasFnAttribute(Attribute::NoInline),
472       F.hasFnAttribute(Attribute::AlwaysInline)};
473   std::vector<FunctionSummary::ParamAccess> ParamAccesses;
474   if (auto *SSI = GetSSICallback(F))
475     ParamAccesses = SSI->getParamAccesses();
476   auto FuncSummary = std::make_unique<FunctionSummary>(
477       Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs),
478       CallGraphEdges.takeVector(), TypeTests.takeVector(),
479       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
480       TypeTestAssumeConstVCalls.takeVector(),
481       TypeCheckedLoadConstVCalls.takeVector(), std::move(ParamAccesses));
482   if (NonRenamableLocal)
483     CantBePromoted.insert(F.getGUID());
484   Index.addGlobalValueSummary(F, std::move(FuncSummary));
485 }
486 
487 /// Find function pointers referenced within the given vtable initializer
488 /// (or subset of an initializer) \p I. The starting offset of \p I within
489 /// the vtable initializer is \p StartingOffset. Any discovered function
490 /// pointers are added to \p VTableFuncs along with their cumulative offset
491 /// within the initializer.
492 static void findFuncPointers(const Constant *I, uint64_t StartingOffset,
493                              const Module &M, ModuleSummaryIndex &Index,
494                              VTableFuncList &VTableFuncs) {
495   // First check if this is a function pointer.
496   if (I->getType()->isPointerTy()) {
497     auto Fn = dyn_cast<Function>(I->stripPointerCasts());
498     // We can disregard __cxa_pure_virtual as a possible call target, as
499     // calls to pure virtuals are UB.
500     if (Fn && Fn->getName() != "__cxa_pure_virtual")
501       VTableFuncs.push_back({Index.getOrInsertValueInfo(Fn), StartingOffset});
502     return;
503   }
504 
505   // Walk through the elements in the constant struct or array and recursively
506   // look for virtual function pointers.
507   const DataLayout &DL = M.getDataLayout();
508   if (auto *C = dyn_cast<ConstantStruct>(I)) {
509     StructType *STy = dyn_cast<StructType>(C->getType());
510     assert(STy);
511     const StructLayout *SL = DL.getStructLayout(C->getType());
512 
513     for (StructType::element_iterator EB = STy->element_begin(), EI = EB,
514                                       EE = STy->element_end();
515          EI != EE; ++EI) {
516       auto Offset = SL->getElementOffset(EI - EB);
517       unsigned Op = SL->getElementContainingOffset(Offset);
518       findFuncPointers(cast<Constant>(I->getOperand(Op)),
519                        StartingOffset + Offset, M, Index, VTableFuncs);
520     }
521   } else if (auto *C = dyn_cast<ConstantArray>(I)) {
522     ArrayType *ATy = C->getType();
523     Type *EltTy = ATy->getElementType();
524     uint64_t EltSize = DL.getTypeAllocSize(EltTy);
525     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
526       findFuncPointers(cast<Constant>(I->getOperand(i)),
527                        StartingOffset + i * EltSize, M, Index, VTableFuncs);
528     }
529   }
530 }
531 
532 // Identify the function pointers referenced by vtable definition \p V.
533 static void computeVTableFuncs(ModuleSummaryIndex &Index,
534                                const GlobalVariable &V, const Module &M,
535                                VTableFuncList &VTableFuncs) {
536   if (!V.isConstant())
537     return;
538 
539   findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index,
540                    VTableFuncs);
541 
542 #ifndef NDEBUG
543   // Validate that the VTableFuncs list is ordered by offset.
544   uint64_t PrevOffset = 0;
545   for (auto &P : VTableFuncs) {
546     // The findVFuncPointers traversal should have encountered the
547     // functions in offset order. We need to use ">=" since PrevOffset
548     // starts at 0.
549     assert(P.VTableOffset >= PrevOffset);
550     PrevOffset = P.VTableOffset;
551   }
552 #endif
553 }
554 
555 /// Record vtable definition \p V for each type metadata it references.
556 static void
557 recordTypeIdCompatibleVtableReferences(ModuleSummaryIndex &Index,
558                                        const GlobalVariable &V,
559                                        SmallVectorImpl<MDNode *> &Types) {
560   for (MDNode *Type : Types) {
561     auto TypeID = Type->getOperand(1).get();
562 
563     uint64_t Offset =
564         cast<ConstantInt>(
565             cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
566             ->getZExtValue();
567 
568     if (auto *TypeId = dyn_cast<MDString>(TypeID))
569       Index.getOrInsertTypeIdCompatibleVtableSummary(TypeId->getString())
570           .push_back({Offset, Index.getOrInsertValueInfo(&V)});
571   }
572 }
573 
574 static void computeVariableSummary(ModuleSummaryIndex &Index,
575                                    const GlobalVariable &V,
576                                    DenseSet<GlobalValue::GUID> &CantBePromoted,
577                                    const Module &M,
578                                    SmallVectorImpl<MDNode *> &Types) {
579   SetVector<ValueInfo> RefEdges;
580   SmallPtrSet<const User *, 8> Visited;
581   bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited);
582   bool NonRenamableLocal = isNonRenamableLocal(V);
583   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
584                                     /* Live = */ false, V.isDSOLocal(),
585                                     V.hasLinkOnceODRLinkage() && V.hasGlobalUnnamedAddr());
586 
587   VTableFuncList VTableFuncs;
588   // If splitting is not enabled, then we compute the summary information
589   // necessary for index-based whole program devirtualization.
590   if (!Index.enableSplitLTOUnit()) {
591     Types.clear();
592     V.getMetadata(LLVMContext::MD_type, Types);
593     if (!Types.empty()) {
594       // Identify the function pointers referenced by this vtable definition.
595       computeVTableFuncs(Index, V, M, VTableFuncs);
596 
597       // Record this vtable definition for each type metadata it references.
598       recordTypeIdCompatibleVtableReferences(Index, V, Types);
599     }
600   }
601 
602   // Don't mark variables we won't be able to internalize as read/write-only.
603   bool CanBeInternalized =
604       !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() &&
605       !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass();
606   bool Constant = V.isConstant();
607   GlobalVarSummary::GVarFlags VarFlags(CanBeInternalized,
608                                        Constant ? false : CanBeInternalized,
609                                        Constant, V.getVCallVisibility());
610   auto GVarSummary = std::make_unique<GlobalVarSummary>(Flags, VarFlags,
611                                                          RefEdges.takeVector());
612   if (NonRenamableLocal)
613     CantBePromoted.insert(V.getGUID());
614   if (HasBlockAddress)
615     GVarSummary->setNotEligibleToImport();
616   if (!VTableFuncs.empty())
617     GVarSummary->setVTableFuncs(VTableFuncs);
618   Index.addGlobalValueSummary(V, std::move(GVarSummary));
619 }
620 
621 static void
622 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
623                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
624   bool NonRenamableLocal = isNonRenamableLocal(A);
625   GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
626                                     /* Live = */ false, A.isDSOLocal(),
627                                     A.hasLinkOnceODRLinkage() && A.hasGlobalUnnamedAddr());
628   auto AS = std::make_unique<AliasSummary>(Flags);
629   auto *Aliasee = A.getBaseObject();
630   auto AliaseeVI = Index.getValueInfo(Aliasee->getGUID());
631   assert(AliaseeVI && "Alias expects aliasee summary to be available");
632   assert(AliaseeVI.getSummaryList().size() == 1 &&
633          "Expected a single entry per aliasee in per-module index");
634   AS->setAliasee(AliaseeVI, AliaseeVI.getSummaryList()[0].get());
635   if (NonRenamableLocal)
636     CantBePromoted.insert(A.getGUID());
637   Index.addGlobalValueSummary(A, std::move(AS));
638 }
639 
640 // Set LiveRoot flag on entries matching the given value name.
641 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
642   if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
643     for (auto &Summary : VI.getSummaryList())
644       Summary->setLive(true);
645 }
646 
647 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
648     const Module &M,
649     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
650     ProfileSummaryInfo *PSI,
651     std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) {
652   assert(PSI);
653   bool EnableSplitLTOUnit = false;
654   if (auto *MD = mdconst::extract_or_null<ConstantInt>(
655           M.getModuleFlag("EnableSplitLTOUnit")))
656     EnableSplitLTOUnit = MD->getZExtValue();
657   ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit);
658 
659   // Identify the local values in the llvm.used and llvm.compiler.used sets,
660   // which should not be exported as they would then require renaming and
661   // promotion, but we may have opaque uses e.g. in inline asm. We collect them
662   // here because we use this information to mark functions containing inline
663   // assembly calls as not importable.
664   SmallPtrSet<GlobalValue *, 8> LocalsUsed;
665   SmallPtrSet<GlobalValue *, 8> Used;
666   // First collect those in the llvm.used set.
667   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
668   // Next collect those in the llvm.compiler.used set.
669   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
670   DenseSet<GlobalValue::GUID> CantBePromoted;
671   for (auto *V : Used) {
672     if (V->hasLocalLinkage()) {
673       LocalsUsed.insert(V);
674       CantBePromoted.insert(V->getGUID());
675     }
676   }
677 
678   bool HasLocalInlineAsmSymbol = false;
679   if (!M.getModuleInlineAsm().empty()) {
680     // Collect the local values defined by module level asm, and set up
681     // summaries for these symbols so that they can be marked as NoRename,
682     // to prevent export of any use of them in regular IR that would require
683     // renaming within the module level asm. Note we don't need to create a
684     // summary for weak or global defs, as they don't need to be flagged as
685     // NoRename, and defs in module level asm can't be imported anyway.
686     // Also, any values used but not defined within module level asm should
687     // be listed on the llvm.used or llvm.compiler.used global and marked as
688     // referenced from there.
689     ModuleSymbolTable::CollectAsmSymbols(
690         M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) {
691           // Symbols not marked as Weak or Global are local definitions.
692           if (Flags & (object::BasicSymbolRef::SF_Weak |
693                        object::BasicSymbolRef::SF_Global))
694             return;
695           HasLocalInlineAsmSymbol = true;
696           GlobalValue *GV = M.getNamedValue(Name);
697           if (!GV)
698             return;
699           assert(GV->isDeclaration() && "Def in module asm already has definition");
700           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
701                                               /* NotEligibleToImport = */ true,
702                                               /* Live = */ true,
703                                               /* Local */ GV->isDSOLocal(),
704                                               GV->hasLinkOnceODRLinkage() && GV->hasGlobalUnnamedAddr());
705           CantBePromoted.insert(GV->getGUID());
706           // Create the appropriate summary type.
707           if (Function *F = dyn_cast<Function>(GV)) {
708             std::unique_ptr<FunctionSummary> Summary =
709                 std::make_unique<FunctionSummary>(
710                     GVFlags, /*InstCount=*/0,
711                     FunctionSummary::FFlags{
712                         F->hasFnAttribute(Attribute::ReadNone),
713                         F->hasFnAttribute(Attribute::ReadOnly),
714                         F->hasFnAttribute(Attribute::NoRecurse),
715                         F->returnDoesNotAlias(),
716                         /* NoInline = */ false,
717                         F->hasFnAttribute(Attribute::AlwaysInline)},
718                     /*EntryCount=*/0, ArrayRef<ValueInfo>{},
719                     ArrayRef<FunctionSummary::EdgeTy>{},
720                     ArrayRef<GlobalValue::GUID>{},
721                     ArrayRef<FunctionSummary::VFuncId>{},
722                     ArrayRef<FunctionSummary::VFuncId>{},
723                     ArrayRef<FunctionSummary::ConstVCall>{},
724                     ArrayRef<FunctionSummary::ConstVCall>{},
725                     ArrayRef<FunctionSummary::ParamAccess>{});
726             Index.addGlobalValueSummary(*GV, std::move(Summary));
727           } else {
728             std::unique_ptr<GlobalVarSummary> Summary =
729                 std::make_unique<GlobalVarSummary>(
730                     GVFlags,
731                     GlobalVarSummary::GVarFlags(
732                         false, false, cast<GlobalVariable>(GV)->isConstant(),
733                         GlobalObject::VCallVisibilityPublic),
734                     ArrayRef<ValueInfo>{});
735             Index.addGlobalValueSummary(*GV, std::move(Summary));
736           }
737         });
738   }
739 
740   bool IsThinLTO = true;
741   if (auto *MD =
742           mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))
743     IsThinLTO = MD->getZExtValue();
744 
745   // Compute summaries for all functions defined in module, and save in the
746   // index.
747   for (auto &F : M) {
748     if (F.isDeclaration())
749       continue;
750 
751     DominatorTree DT(const_cast<Function &>(F));
752     BlockFrequencyInfo *BFI = nullptr;
753     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
754     if (GetBFICallback)
755       BFI = GetBFICallback(F);
756     else if (F.hasProfileData()) {
757       LoopInfo LI{DT};
758       BranchProbabilityInfo BPI{F, LI};
759       BFIPtr = std::make_unique<BlockFrequencyInfo>(F, BPI, LI);
760       BFI = BFIPtr.get();
761     }
762 
763     computeFunctionSummary(Index, M, F, BFI, PSI, DT,
764                            !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
765                            CantBePromoted, IsThinLTO, GetSSICallback);
766   }
767 
768   // Compute summaries for all variables defined in module, and save in the
769   // index.
770   SmallVector<MDNode *, 2> Types;
771   for (const GlobalVariable &G : M.globals()) {
772     if (G.isDeclaration())
773       continue;
774     computeVariableSummary(Index, G, CantBePromoted, M, Types);
775   }
776 
777   // Compute summaries for all aliases defined in module, and save in the
778   // index.
779   for (const GlobalAlias &A : M.aliases())
780     computeAliasSummary(Index, A, CantBePromoted);
781 
782   for (auto *V : LocalsUsed) {
783     auto *Summary = Index.getGlobalValueSummary(*V);
784     assert(Summary && "Missing summary for global value");
785     Summary->setNotEligibleToImport();
786   }
787 
788   // The linker doesn't know about these LLVM produced values, so we need
789   // to flag them as live in the index to ensure index-based dead value
790   // analysis treats them as live roots of the analysis.
791   setLiveRoot(Index, "llvm.used");
792   setLiveRoot(Index, "llvm.compiler.used");
793   setLiveRoot(Index, "llvm.global_ctors");
794   setLiveRoot(Index, "llvm.global_dtors");
795   setLiveRoot(Index, "llvm.global.annotations");
796 
797   for (auto &GlobalList : Index) {
798     // Ignore entries for references that are undefined in the current module.
799     if (GlobalList.second.SummaryList.empty())
800       continue;
801 
802     assert(GlobalList.second.SummaryList.size() == 1 &&
803            "Expected module's index to have one summary per GUID");
804     auto &Summary = GlobalList.second.SummaryList[0];
805     if (!IsThinLTO) {
806       Summary->setNotEligibleToImport();
807       continue;
808     }
809 
810     bool AllRefsCanBeExternallyReferenced =
811         llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
812           return !CantBePromoted.count(VI.getGUID());
813         });
814     if (!AllRefsCanBeExternallyReferenced) {
815       Summary->setNotEligibleToImport();
816       continue;
817     }
818 
819     if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
820       bool AllCallsCanBeExternallyReferenced = llvm::all_of(
821           FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
822             return !CantBePromoted.count(Edge.first.getGUID());
823           });
824       if (!AllCallsCanBeExternallyReferenced)
825         Summary->setNotEligibleToImport();
826     }
827   }
828 
829   if (!ModuleSummaryDotFile.empty()) {
830     std::error_code EC;
831     raw_fd_ostream OSDot(ModuleSummaryDotFile, EC, sys::fs::OpenFlags::OF_None);
832     if (EC)
833       report_fatal_error(Twine("Failed to open dot file ") +
834                          ModuleSummaryDotFile + ": " + EC.message() + "\n");
835     Index.exportToDot(OSDot, {});
836   }
837 
838   return Index;
839 }
840 
841 AnalysisKey ModuleSummaryIndexAnalysis::Key;
842 
843 ModuleSummaryIndex
844 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
845   ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
846   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
847   bool NeedSSI = needsParamAccessSummary(M);
848   return buildModuleSummaryIndex(
849       M,
850       [&FAM](const Function &F) {
851         return &FAM.getResult<BlockFrequencyAnalysis>(
852             *const_cast<Function *>(&F));
853       },
854       &PSI,
855       [&FAM, NeedSSI](const Function &F) -> const StackSafetyInfo * {
856         return NeedSSI ? &FAM.getResult<StackSafetyAnalysis>(
857                              const_cast<Function &>(F))
858                        : nullptr;
859       });
860 }
861 
862 char ModuleSummaryIndexWrapperPass::ID = 0;
863 
864 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
865                       "Module Summary Analysis", false, true)
866 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
867 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
868 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
869 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
870                     "Module Summary Analysis", false, true)
871 
872 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
873   return new ModuleSummaryIndexWrapperPass();
874 }
875 
876 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
877     : ModulePass(ID) {
878   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
879 }
880 
881 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
882   auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
883   bool NeedSSI = needsParamAccessSummary(M);
884   Index.emplace(buildModuleSummaryIndex(
885       M,
886       [this](const Function &F) {
887         return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
888                          *const_cast<Function *>(&F))
889                      .getBFI());
890       },
891       PSI,
892       [&](const Function &F) -> const StackSafetyInfo * {
893         return NeedSSI ? &getAnalysis<StackSafetyInfoWrapperPass>(
894                               const_cast<Function &>(F))
895                               .getResult()
896                        : nullptr;
897       }));
898   return false;
899 }
900 
901 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
902   Index.reset();
903   return false;
904 }
905 
906 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
907   AU.setPreservesAll();
908   AU.addRequired<BlockFrequencyInfoWrapperPass>();
909   AU.addRequired<ProfileSummaryInfoWrapperPass>();
910   AU.addRequired<StackSafetyInfoWrapperPass>();
911 }
912 
913 char ImmutableModuleSummaryIndexWrapperPass::ID = 0;
914 
915 ImmutableModuleSummaryIndexWrapperPass::ImmutableModuleSummaryIndexWrapperPass(
916     const ModuleSummaryIndex *Index)
917     : ImmutablePass(ID), Index(Index) {
918   initializeImmutableModuleSummaryIndexWrapperPassPass(
919       *PassRegistry::getPassRegistry());
920 }
921 
922 void ImmutableModuleSummaryIndexWrapperPass::getAnalysisUsage(
923     AnalysisUsage &AU) const {
924   AU.setPreservesAll();
925 }
926 
927 ImmutablePass *llvm::createImmutableModuleSummaryIndexWrapperPass(
928     const ModuleSummaryIndex *Index) {
929   return new ImmutableModuleSummaryIndexWrapperPass(Index);
930 }
931 
932 INITIALIZE_PASS(ImmutableModuleSummaryIndexWrapperPass, "module-summary-info",
933                 "Module summary info", false, true)
934