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/ConstantFolding.h"
26#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
27#include "llvm/Analysis/LoopInfo.h"
28#include "llvm/Analysis/MemoryProfileInfo.h"
29#include "llvm/Analysis/ProfileSummaryInfo.h"
30#include "llvm/Analysis/StackSafetyAnalysis.h"
31#include "llvm/Analysis/TypeMetadataUtils.h"
32#include "llvm/IR/Attributes.h"
33#include "llvm/IR/BasicBlock.h"
34#include "llvm/IR/Constant.h"
35#include "llvm/IR/Constants.h"
36#include "llvm/IR/Dominators.h"
37#include "llvm/IR/Function.h"
38#include "llvm/IR/GlobalAlias.h"
39#include "llvm/IR/GlobalValue.h"
40#include "llvm/IR/GlobalVariable.h"
41#include "llvm/IR/Instructions.h"
42#include "llvm/IR/IntrinsicInst.h"
43#include "llvm/IR/LLVMContext.h"
44#include "llvm/IR/Metadata.h"
45#include "llvm/IR/Module.h"
46#include "llvm/IR/ModuleSummaryIndex.h"
47#include "llvm/IR/Use.h"
48#include "llvm/IR/User.h"
49#include "llvm/InitializePasses.h"
50#include "llvm/Object/ModuleSymbolTable.h"
51#include "llvm/Object/SymbolicFile.h"
52#include "llvm/Pass.h"
53#include "llvm/Support/Casting.h"
54#include "llvm/Support/CommandLine.h"
55#include "llvm/Support/Compiler.h"
56#include "llvm/Support/FileSystem.h"
57#include <cassert>
58#include <cstdint>
59#include <vector>
60
61using namespace llvm;
62using namespace llvm::memprof;
63
64#define DEBUG_TYPE "module-summary-analysis"
65
66// Option to force edges cold which will block importing when the
67// -import-cold-multiplier is set to 0. Useful for debugging.
68namespace llvm {
69FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold =
70 FunctionSummary::FSHT_None;
71
72static cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC(
73 "force-summary-edges-cold", cl::Hidden, cl::location(L&: ForceSummaryEdgesCold),
74 cl::desc("Force all edges in the function summary to cold"),
75 cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."),
76 clEnumValN(FunctionSummary::FSHT_AllNonCritical,
77 "all-non-critical", "All non-critical edges."),
78 clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")));
79
80static cl::opt<std::string> ModuleSummaryDotFile(
81 "module-summary-dot-file", cl::Hidden, cl::value_desc("filename"),
82 cl::desc("File to emit dot graph of new summary into"));
83
84static cl::opt<bool> EnableMemProfIndirectCallSupport(
85 "enable-memprof-indirect-call-support", cl::init(Val: true), cl::Hidden,
86 cl::desc(
87 "Enable MemProf support for summarizing and cloning indirect calls"));
88
89// This can be used to override the number of callees created from VP metadata
90// normally taken from the -icp-max-prom option with a larger amount, if useful
91// for analysis. Use a separate option so that we can control the number of
92// indirect callees for ThinLTO summary based analysis (e.g. for MemProf which
93// needs this information for a correct and not overly-conservative callsite
94// graph analysis, especially because allocation contexts may not be very
95// frequent), without affecting normal ICP.
96cl::opt<unsigned>
97 MaxSummaryIndirectEdges("module-summary-max-indirect-edges", cl::init(Val: 0),
98 cl::Hidden,
99 cl::desc("Max number of summary edges added from "
100 "indirect call profile metadata"));
101
102LLVM_ABI extern cl::opt<bool> ScalePartialSampleProfileWorkingSetSize;
103
104extern cl::opt<unsigned> MaxNumVTableAnnotations;
105
106extern cl::opt<bool> MemProfReportHintedSizes;
107} // namespace llvm
108
109// Walk through the operands of a given User via worklist iteration and populate
110// the set of GlobalValue references encountered. Invoked either on an
111// Instruction or a GlobalVariable (which walks its initializer).
112// Return true if any of the operands contains blockaddress. This is important
113// to know when computing summary for global var, because if global variable
114// references basic block address we can't import it separately from function
115// containing that basic block. For simplicity we currently don't import such
116// global vars at all. When importing function we aren't interested if any
117// instruction in it takes an address of any basic block, because instruction
118// can only take an address of basic block located in the same function.
119// Set `RefLocalLinkageIFunc` to true if the analyzed value references a
120// local-linkage ifunc.
121static bool
122findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
123 SetVector<ValueInfo, SmallVector<ValueInfo, 0>> &RefEdges,
124 SmallPtrSet<const User *, 8> &Visited,
125 bool &RefLocalLinkageIFunc) {
126 bool HasBlockAddress = false;
127 SmallVector<const User *, 32> Worklist;
128 if (Visited.insert(Ptr: CurUser).second)
129 Worklist.push_back(Elt: CurUser);
130
131 while (!Worklist.empty()) {
132 const User *U = Worklist.pop_back_val();
133 const auto *CB = dyn_cast<CallBase>(Val: U);
134
135 for (const auto &OI : U->operands()) {
136 const User *Operand = dyn_cast<User>(Val: OI);
137 if (!Operand)
138 continue;
139 if (isa<BlockAddress>(Val: Operand)) {
140 HasBlockAddress = true;
141 continue;
142 }
143 if (auto *GV = dyn_cast<GlobalValue>(Val: Operand)) {
144 // We have a reference to a global value. This should be added to
145 // the reference set unless it is a callee. Callees are handled
146 // specially by WriteFunction and are added to a separate list.
147 if (!(CB && CB->isCallee(U: &OI))) {
148 // If an ifunc has local linkage, do not add it into ref edges, and
149 // sets `RefLocalLinkageIFunc` to true. The referencer is not eligible
150 // for import. An ifunc doesn't have summary and ThinLTO cannot
151 // promote it; importing the referencer may cause linkage errors.
152 if (auto *GI = dyn_cast_if_present<GlobalIFunc>(Val: GV);
153 GI && GI->hasLocalLinkage()) {
154 RefLocalLinkageIFunc = true;
155 continue;
156 }
157 RefEdges.insert(X: Index.getOrInsertValueInfo(GV));
158 }
159 continue;
160 }
161 if (Visited.insert(Ptr: Operand).second)
162 Worklist.push_back(Elt: Operand);
163 }
164 }
165
166 const Instruction *I = dyn_cast<Instruction>(Val: CurUser);
167 if (I) {
168 uint64_t TotalCount = 0;
169 // MaxNumVTableAnnotations is the maximum number of vtables annotated on
170 // the instruction.
171 auto ValueDataArray = getValueProfDataFromInst(
172 Inst: *I, ValueKind: IPVK_VTableTarget, MaxNumValueData: MaxNumVTableAnnotations, TotalC&: TotalCount);
173
174 for (const auto &V : ValueDataArray)
175 RefEdges.insert(X: Index.getOrInsertValueInfo(/* VTableGUID = */
176 GUID: V.Value));
177 }
178 return HasBlockAddress;
179}
180
181/// Collect globals referenced via !implicit.ref metadata on a function
182/// and add them as reference edges in the module summary. This ensures
183/// ThinLTO liveness analysis treats them as live when the function is
184/// live, and imports them alongside the function during cross-module
185/// importing.
186static void findImplicitRefEdges(
187 ModuleSummaryIndex &Index, const Function &F,
188 SetVector<ValueInfo, SmallVector<ValueInfo, 0>> &RefEdges) {
189 if (!F.hasMetadata(KindID: LLVMContext::MD_implicit_ref))
190 return;
191 SmallVector<MDNode *, 4> MDs;
192 F.getMetadata(KindID: LLVMContext::MD_implicit_ref, MDs);
193 for (MDNode *MD : MDs) {
194 for (const MDOperand &Op : MD->operands()) {
195 if (auto *VAM = dyn_cast_or_null<ValueAsMetadata>(Val: Op.get()))
196 if (auto *GV = dyn_cast<GlobalValue>(Val: VAM->getValue()))
197 RefEdges.insert(X: Index.getOrInsertValueInfo(GV));
198 }
199 }
200}
201
202static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
203 ProfileSummaryInfo *PSI) {
204 if (!PSI)
205 return CalleeInfo::HotnessType::Unknown;
206 if (PSI->isHotCount(C: ProfileCount))
207 return CalleeInfo::HotnessType::Hot;
208 if (PSI->isColdCount(C: ProfileCount))
209 return CalleeInfo::HotnessType::Cold;
210 return CalleeInfo::HotnessType::None;
211}
212
213static bool isNonRenamableLocal(const GlobalValue &GV) {
214 return GV.hasSection() && GV.hasLocalLinkage();
215}
216
217/// Determine whether this call has all constant integer arguments (excluding
218/// "this") and summarize it to VCalls or ConstVCalls as appropriate.
219static void addVCallToSet(
220 DevirtCallSite Call, GlobalValue::GUID Guid,
221 SetVector<FunctionSummary::VFuncId, std::vector<FunctionSummary::VFuncId>>
222 &VCalls,
223 SetVector<FunctionSummary::ConstVCall,
224 std::vector<FunctionSummary::ConstVCall>> &ConstVCalls) {
225 std::vector<uint64_t> Args;
226 // Start from the second argument to skip the "this" pointer.
227 for (auto &Arg : drop_begin(RangeOrContainer: Call.CB.args())) {
228 auto *CI = dyn_cast<ConstantInt>(Val&: Arg);
229 if (!CI || CI->getBitWidth() > 64) {
230 VCalls.insert(X: {.GUID: Guid, .Offset: Call.Offset});
231 return;
232 }
233 Args.push_back(x: CI->getZExtValue());
234 }
235 ConstVCalls.insert(X: {.VFunc: {.GUID: Guid, .Offset: Call.Offset}, .Args: std::move(Args)});
236}
237
238/// If this intrinsic call requires that we add information to the function
239/// summary, do so via the non-constant reference arguments.
240static void addIntrinsicToSummary(
241 const CallInst *CI,
242 SetVector<GlobalValue::GUID, std::vector<GlobalValue::GUID>> &TypeTests,
243 SetVector<FunctionSummary::VFuncId, std::vector<FunctionSummary::VFuncId>>
244 &TypeTestAssumeVCalls,
245 SetVector<FunctionSummary::VFuncId, std::vector<FunctionSummary::VFuncId>>
246 &TypeCheckedLoadVCalls,
247 SetVector<FunctionSummary::ConstVCall,
248 std::vector<FunctionSummary::ConstVCall>>
249 &TypeTestAssumeConstVCalls,
250 SetVector<FunctionSummary::ConstVCall,
251 std::vector<FunctionSummary::ConstVCall>>
252 &TypeCheckedLoadConstVCalls,
253 DominatorTree &DT) {
254 switch (CI->getCalledFunction()->getIntrinsicID()) {
255 case Intrinsic::type_test:
256 case Intrinsic::public_type_test: {
257 auto *TypeMDVal = cast<MetadataAsValue>(Val: CI->getArgOperand(i: 1));
258 auto *TypeId = dyn_cast<MDString>(Val: TypeMDVal->getMetadata());
259 if (!TypeId)
260 break;
261 GlobalValue::GUID Guid =
262 GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: TypeId->getString());
263
264 // Produce a summary from type.test intrinsics. We only summarize type.test
265 // intrinsics that are used other than by an llvm.assume intrinsic.
266 // Intrinsics that are assumed are relevant only to the devirtualization
267 // pass, not the type test lowering pass.
268 bool HasNonAssumeUses = llvm::any_of(Range: CI->uses(), P: [](const Use &CIU) {
269 return !isa<AssumeInst>(Val: CIU.getUser());
270 });
271 if (HasNonAssumeUses)
272 TypeTests.insert(X: Guid);
273
274 SmallVector<DevirtCallSite, 4> DevirtCalls;
275 SmallVector<CallInst *, 4> Assumes;
276 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
277 for (auto &Call : DevirtCalls)
278 addVCallToSet(Call, Guid, VCalls&: TypeTestAssumeVCalls,
279 ConstVCalls&: TypeTestAssumeConstVCalls);
280
281 break;
282 }
283
284 case Intrinsic::type_checked_load_relative:
285 case Intrinsic::type_checked_load: {
286 auto *TypeMDVal = cast<MetadataAsValue>(Val: CI->getArgOperand(i: 2));
287 auto *TypeId = dyn_cast<MDString>(Val: TypeMDVal->getMetadata());
288 if (!TypeId)
289 break;
290 GlobalValue::GUID Guid =
291 GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: TypeId->getString());
292
293 SmallVector<DevirtCallSite, 4> DevirtCalls;
294 SmallVector<Instruction *, 4> LoadedPtrs;
295 SmallVector<Instruction *, 4> Preds;
296 bool HasNonCallUses = false;
297 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
298 HasNonCallUses, CI, DT);
299 // Any non-call uses of the result of llvm.type.checked.load will
300 // prevent us from optimizing away the llvm.type.test.
301 if (HasNonCallUses)
302 TypeTests.insert(X: Guid);
303 for (auto &Call : DevirtCalls)
304 addVCallToSet(Call, Guid, VCalls&: TypeCheckedLoadVCalls,
305 ConstVCalls&: TypeCheckedLoadConstVCalls);
306
307 break;
308 }
309 default:
310 break;
311 }
312}
313
314static bool isNonVolatileLoad(const Instruction *I) {
315 if (const auto *LI = dyn_cast<LoadInst>(Val: I))
316 return !LI->isVolatile();
317
318 return false;
319}
320
321static bool isNonVolatileStore(const Instruction *I) {
322 if (const auto *SI = dyn_cast<StoreInst>(Val: I))
323 return !SI->isVolatile();
324
325 return false;
326}
327
328// Returns true if the function definition must be unreachable.
329//
330// Note if this helper function returns true, `F` is guaranteed
331// to be unreachable; if it returns false, `F` might still
332// be unreachable but not covered by this helper function.
333static bool mustBeUnreachableFunction(const Function &F) {
334 // A function must be unreachable if its entry block ends with an
335 // 'unreachable'.
336 assert(!F.isDeclaration());
337 return isa<UnreachableInst>(Val: F.getEntryBlock().getTerminator());
338}
339
340static void computeFunctionSummary(
341 ModuleSummaryIndex &Index, const Module &M, const Function &F,
342 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, DominatorTree &DT,
343 bool HasLocalsInUsedOrAsm, DenseSet<GlobalValue::GUID> &CantBePromoted,
344 bool IsThinLTO,
345 std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) {
346 // Summary not currently supported for anonymous functions, they should
347 // have been named.
348 assert(F.hasName());
349
350 unsigned NumInsts = 0;
351 // Map from callee ValueId to profile count. Used to accumulate profile
352 // counts for all static calls to a given callee.
353 MapVector<ValueInfo, CalleeInfo, DenseMap<ValueInfo, unsigned>,
354 SmallVector<FunctionSummary::EdgeTy, 0>>
355 CallGraphEdges;
356 SetVector<ValueInfo, SmallVector<ValueInfo, 0>> RefEdges, LoadRefEdges,
357 StoreRefEdges;
358 SetVector<GlobalValue::GUID, std::vector<GlobalValue::GUID>> TypeTests;
359 SetVector<FunctionSummary::VFuncId, std::vector<FunctionSummary::VFuncId>>
360 TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
361 SetVector<FunctionSummary::ConstVCall,
362 std::vector<FunctionSummary::ConstVCall>>
363 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls;
364 ICallPromotionAnalysis ICallAnalysis;
365 SmallPtrSet<const User *, 8> Visited;
366
367 // Add personality function, prefix data and prologue data to function's ref
368 // list.
369 bool HasLocalIFuncCallOrRef = false;
370 findRefEdges(Index, CurUser: &F, RefEdges, Visited, RefLocalLinkageIFunc&: HasLocalIFuncCallOrRef);
371 findImplicitRefEdges(Index, F, RefEdges);
372
373 std::vector<const Instruction *> NonVolatileLoads;
374 std::vector<const Instruction *> NonVolatileStores;
375
376 std::vector<CallsiteInfo> Callsites;
377 std::vector<AllocInfo> Allocs;
378
379#ifndef NDEBUG
380 DenseSet<const CallBase *> CallsThatMayHaveMemprofSummary;
381#endif
382
383 bool HasInlineAsmMaybeReferencingInternal = false;
384 bool HasIndirBranchToBlockAddress = false;
385 bool HasUnknownCall = false;
386 bool MayThrow = false;
387 for (const BasicBlock &BB : F) {
388 // We don't allow inlining of function with indirect branch to blockaddress.
389 // If the blockaddress escapes the function, e.g., via a global variable,
390 // inlining may lead to an invalid cross-function reference. So we shouldn't
391 // import such function either.
392 if (BB.hasAddressTaken()) {
393 for (User *U : BlockAddress::get(BB: const_cast<BasicBlock *>(&BB))->users())
394 if (!isa<CallBrInst>(Val: *U)) {
395 HasIndirBranchToBlockAddress = true;
396 break;
397 }
398 }
399
400 for (const Instruction &I : BB) {
401 if (I.isDebugOrPseudoInst())
402 continue;
403 ++NumInsts;
404
405 // Regular LTO module doesn't participate in ThinLTO import,
406 // so no reference from it can be read/writeonly, since this
407 // would require importing variable as local copy
408 if (IsThinLTO) {
409 if (isNonVolatileLoad(I: &I)) {
410 // Postpone processing of non-volatile load instructions
411 // See comments below
412 Visited.insert(Ptr: &I);
413 NonVolatileLoads.push_back(x: &I);
414 continue;
415 } else if (isNonVolatileStore(I: &I)) {
416 Visited.insert(Ptr: &I);
417 NonVolatileStores.push_back(x: &I);
418 // All references from second operand of store (destination address)
419 // can be considered write-only if they're not referenced by any
420 // non-store instruction. References from first operand of store
421 // (stored value) can't be treated either as read- or as write-only
422 // so we add them to RefEdges as we do with all other instructions
423 // except non-volatile load.
424 Value *Stored = I.getOperand(i: 0);
425 if (auto *GV = dyn_cast<GlobalValue>(Val: Stored))
426 // findRefEdges will try to examine GV operands, so instead
427 // of calling it we should add GV to RefEdges directly.
428 RefEdges.insert(X: Index.getOrInsertValueInfo(GV));
429 else if (auto *U = dyn_cast<User>(Val: Stored))
430 findRefEdges(Index, CurUser: U, RefEdges, Visited, RefLocalLinkageIFunc&: HasLocalIFuncCallOrRef);
431 continue;
432 }
433 }
434 findRefEdges(Index, CurUser: &I, RefEdges, Visited, RefLocalLinkageIFunc&: HasLocalIFuncCallOrRef);
435 const auto *CB = dyn_cast<CallBase>(Val: &I);
436 if (!CB) {
437 if (I.mayThrow())
438 MayThrow = true;
439 continue;
440 }
441
442 const auto *CI = dyn_cast<CallInst>(Val: &I);
443 // Since we don't know exactly which local values are referenced in inline
444 // assembly, conservatively mark the function as possibly referencing
445 // a local value from inline assembly to ensure we don't export a
446 // reference (which would require renaming and promotion of the
447 // referenced value).
448 if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm())
449 HasInlineAsmMaybeReferencingInternal = true;
450
451 // Compute this once per indirect call.
452 uint32_t NumCandidates = 0;
453 uint64_t TotalCount = 0;
454 MutableArrayRef<InstrProfValueData> CandidateProfileData;
455
456 auto *CalledValue = CB->getCalledOperand();
457 auto *CalledFunction = CB->getCalledFunction();
458 if (CalledValue && !CalledFunction) {
459 CalledValue = CalledValue->stripPointerCasts();
460 // Stripping pointer casts can reveal a called function.
461 CalledFunction = dyn_cast<Function>(Val: CalledValue);
462 }
463 // Check if this is an alias to a function. If so, get the
464 // called aliasee for the checks below.
465 if (auto *GA = dyn_cast<GlobalAlias>(Val: CalledValue)) {
466 assert(!CalledFunction && "Expected null called function in callsite for alias");
467 CalledFunction = dyn_cast<Function>(Val: GA->getAliaseeObject());
468 }
469 // Check if this is a direct call to a known function or a known
470 // intrinsic, or an indirect call with profile data.
471 if (CalledFunction) {
472 if (CI && CalledFunction->isIntrinsic()) {
473 addIntrinsicToSummary(
474 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
475 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT);
476 continue;
477 }
478 // We should have named any anonymous globals
479 assert(CalledFunction->hasName());
480 auto ScaledCount = PSI->getProfileCount(CallInst: *CB, BFI);
481 auto Hotness = ScaledCount ? getHotness(ProfileCount: *ScaledCount, PSI)
482 : CalleeInfo::HotnessType::Unknown;
483 if (ForceSummaryEdgesCold != FunctionSummary::FSHT_None)
484 Hotness = CalleeInfo::HotnessType::Cold;
485
486 // Use the original CalledValue, in case it was an alias. We want
487 // to record the call edge to the alias in that case. Eventually
488 // an alias summary will be created to associate the alias and
489 // aliasee.
490 auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo(
491 GV: cast<GlobalValue>(Val: CalledValue))];
492 ValueInfo.updateHotness(OtherHotness: Hotness);
493 if (CB->isTailCall())
494 ValueInfo.setHasTailCall(true);
495 } else {
496 HasUnknownCall = true;
497 // If F is imported, a local linkage ifunc (e.g. target_clones on a
498 // static function) called by F will be cloned. Since summaries don't
499 // track ifunc, we do not know implementation functions referenced by
500 // the ifunc resolver need to be promoted in the exporter, and we will
501 // get linker errors due to cloned declarations for implementation
502 // functions. As a simple fix, just mark F as not eligible for import.
503 // Non-local ifunc is not cloned and does not have the issue.
504 if (auto *GI = dyn_cast_if_present<GlobalIFunc>(Val: CalledValue))
505 if (GI->hasLocalLinkage())
506 HasLocalIFuncCallOrRef = true;
507 // Skip inline assembly calls.
508 if (CI && CI->isInlineAsm())
509 continue;
510 // Skip direct calls.
511 if (!CalledValue || isa<Constant>(Val: CalledValue))
512 continue;
513
514 // Check if the instruction has a callees metadata. If so, add callees
515 // to CallGraphEdges to reflect the references from the metadata, and
516 // to enable importing for subsequent indirect call promotion and
517 // inlining.
518 if (auto *MD = I.getMetadata(KindID: LLVMContext::MD_callees)) {
519 for (const auto &Op : MD->operands()) {
520 Function *Callee = mdconst::extract_or_null<Function>(MD: Op);
521 if (Callee)
522 CallGraphEdges[Index.getOrInsertValueInfo(GV: Callee)];
523 }
524 }
525
526 CandidateProfileData =
527 ICallAnalysis.getPromotionCandidatesForInstruction(
528 I: &I, TotalCount, NumCandidates, MaxNumValueData: MaxSummaryIndirectEdges);
529 for (const auto &Candidate : CandidateProfileData)
530 CallGraphEdges[Index.getOrInsertValueInfo(GUID: Candidate.Value)]
531 .updateHotness(OtherHotness: getHotness(ProfileCount: Candidate.Count, PSI));
532 }
533
534 // Summarize memprof related metadata. This is only needed for ThinLTO.
535 if (!IsThinLTO)
536 continue;
537
538 // Skip indirect calls if we haven't enabled memprof ICP.
539 if (!CalledFunction && !EnableMemProfIndirectCallSupport)
540 continue;
541
542 // Ensure we keep this analysis in sync with the handling in the ThinLTO
543 // backend (see MemProfContextDisambiguation::applyImport). Save this call
544 // so that we can skip it in checking the reverse case later.
545 assert(mayHaveMemprofSummary(CB));
546#ifndef NDEBUG
547 CallsThatMayHaveMemprofSummary.insert(CB);
548#endif
549
550 // Compute the list of stack ids first (so we can trim them from the stack
551 // ids on any MIBs).
552 CallStack<MDNode, MDNode::op_iterator> InstCallsite(
553 I.getMetadata(KindID: LLVMContext::MD_callsite));
554 auto *MemProfMD = I.getMetadata(KindID: LLVMContext::MD_memprof);
555 if (MemProfMD) {
556 std::vector<MIBInfo> MIBs;
557 std::vector<std::vector<ContextTotalSize>> ContextSizeInfos;
558 bool HasNonZeroContextSizeInfos = false;
559 for (auto &MDOp : MemProfMD->operands()) {
560 auto *MIBMD = cast<const MDNode>(Val: MDOp);
561 MDNode *StackNode = getMIBStackNode(MIB: MIBMD);
562 assert(StackNode);
563 SmallVector<unsigned> StackIdIndices;
564 CallStack<MDNode, MDNode::op_iterator> StackContext(StackNode);
565 // Collapse out any on the allocation call (inlining).
566 for (auto ContextIter =
567 StackContext.beginAfterSharedPrefix(Other: InstCallsite);
568 ContextIter != StackContext.end(); ++ContextIter) {
569 unsigned StackIdIdx = Index.addOrGetStackIdIndex(StackId: *ContextIter);
570 // If this is a direct recursion, simply skip the duplicate
571 // entries. If this is mutual recursion, handling is left to
572 // the LTO link analysis client.
573 if (StackIdIndices.empty() || StackIdIndices.back() != StackIdIdx)
574 StackIdIndices.push_back(Elt: StackIdIdx);
575 }
576 // If we have context size information, collect it for inclusion in
577 // the summary.
578 assert(MIBMD->getNumOperands() > 2 ||
579 !metadataIncludesAllContextSizeInfo());
580 if (MIBMD->getNumOperands() > 2) {
581 std::vector<ContextTotalSize> ContextSizes;
582 for (unsigned I = 2; I < MIBMD->getNumOperands(); I++) {
583 MDNode *ContextSizePair = dyn_cast<MDNode>(Val: MIBMD->getOperand(I));
584 assert(ContextSizePair->getNumOperands() == 2);
585 uint64_t FullStackId = mdconst::dyn_extract<ConstantInt>(
586 MD: ContextSizePair->getOperand(I: 0))
587 ->getZExtValue();
588 uint64_t TS = mdconst::dyn_extract<ConstantInt>(
589 MD: ContextSizePair->getOperand(I: 1))
590 ->getZExtValue();
591 ContextSizes.push_back(x: {.FullStackId: FullStackId, .TotalSize: TS});
592 }
593 // Flag that we need to keep the ContextSizeInfos array for this
594 // alloc as it now contains non-zero context info sizes.
595 HasNonZeroContextSizeInfos = true;
596 ContextSizeInfos.push_back(x: std::move(ContextSizes));
597 } else {
598 // The ContextSizeInfos must be in the same relative position as the
599 // associated MIB. In some cases we only include a ContextSizeInfo
600 // for a subset of MIBs in an allocation. To handle that, eagerly
601 // fill any MIB entries that don't have context size info metadata
602 // with a pair of 0s. Later on we will only use this array if it
603 // ends up containing any non-zero entries (see where we set
604 // HasNonZeroContextSizeInfos above).
605 ContextSizeInfos.push_back(x: {{.FullStackId: 0, .TotalSize: 0}});
606 }
607 MIBs.push_back(
608 x: MIBInfo(getMIBAllocType(MIB: MIBMD), std::move(StackIdIndices)));
609 }
610 Allocs.push_back(x: AllocInfo(std::move(MIBs)));
611 assert(HasNonZeroContextSizeInfos ||
612 !metadataIncludesAllContextSizeInfo());
613 // We eagerly build the ContextSizeInfos array, but it will be filled
614 // with sub arrays of pairs of 0s if no MIBs on this alloc actually
615 // contained context size info metadata. Only save it if any MIBs had
616 // any such metadata.
617 if (HasNonZeroContextSizeInfos) {
618 assert(Allocs.back().MIBs.size() == ContextSizeInfos.size());
619 Allocs.back().ContextSizeInfos = std::move(ContextSizeInfos);
620 }
621 } else if (!InstCallsite.empty()) {
622 SmallVector<unsigned> StackIdIndices;
623 for (auto StackId : InstCallsite)
624 StackIdIndices.push_back(Elt: Index.addOrGetStackIdIndex(StackId));
625 if (CalledFunction) {
626 // Use the original CalledValue, in case it was an alias. We want
627 // to record the call edge to the alias in that case. Eventually
628 // an alias summary will be created to associate the alias and
629 // aliasee.
630 auto CalleeValueInfo =
631 Index.getOrInsertValueInfo(GV: cast<GlobalValue>(Val: CalledValue));
632 Callsites.push_back(x: {CalleeValueInfo, StackIdIndices});
633 } else {
634 assert(EnableMemProfIndirectCallSupport);
635 // For indirect callsites, create multiple Callsites, one per target.
636 // This enables having a different set of clone versions per target,
637 // and we will apply the cloning decisions while speculatively
638 // devirtualizing in the ThinLTO backends.
639 for (const auto &Candidate : CandidateProfileData) {
640 auto CalleeValueInfo = Index.getOrInsertValueInfo(GUID: Candidate.Value);
641 Callsites.push_back(x: {CalleeValueInfo, StackIdIndices});
642 }
643 }
644 }
645 }
646 }
647
648 if (PSI->hasPartialSampleProfile() && ScalePartialSampleProfileWorkingSetSize)
649 Index.addBlockCount(C: F.size());
650
651 SmallVector<ValueInfo, 0> Refs;
652 if (IsThinLTO) {
653 auto AddRefEdges =
654 [&](const std::vector<const Instruction *> &Instrs,
655 SetVector<ValueInfo, SmallVector<ValueInfo, 0>> &Edges,
656 SmallPtrSet<const User *, 8> &Cache) {
657 for (const auto *I : Instrs) {
658 Cache.erase(Ptr: I);
659 findRefEdges(Index, CurUser: I, RefEdges&: Edges, Visited&: Cache, RefLocalLinkageIFunc&: HasLocalIFuncCallOrRef);
660 }
661 };
662
663 // By now we processed all instructions in a function, except
664 // non-volatile loads and non-volatile value stores. Let's find
665 // ref edges for both of instruction sets
666 AddRefEdges(NonVolatileLoads, LoadRefEdges, Visited);
667 // We can add some values to the Visited set when processing load
668 // instructions which are also used by stores in NonVolatileStores.
669 // For example this can happen if we have following code:
670 //
671 // store %Derived* @foo, %Derived** bitcast (%Base** @bar to %Derived**)
672 // %42 = load %Derived*, %Derived** bitcast (%Base** @bar to %Derived**)
673 //
674 // After processing loads we'll add bitcast to the Visited set, and if
675 // we use the same set while processing stores, we'll never see store
676 // to @bar and @bar will be mistakenly treated as readonly.
677 SmallPtrSet<const llvm::User *, 8> StoreCache;
678 AddRefEdges(NonVolatileStores, StoreRefEdges, StoreCache);
679
680 // If both load and store instruction reference the same variable
681 // we won't be able to optimize it. Add all such reference edges
682 // to RefEdges set.
683 for (const auto &VI : StoreRefEdges)
684 if (LoadRefEdges.remove(X: VI))
685 RefEdges.insert(X: VI);
686
687 unsigned RefCnt = RefEdges.size();
688 // All new reference edges inserted in two loops below are either
689 // read or write only. They will be grouped in the end of RefEdges
690 // vector, so we can use a single integer value to identify them.
691 RefEdges.insert_range(R&: LoadRefEdges);
692
693 unsigned FirstWORef = RefEdges.size();
694 RefEdges.insert_range(R&: StoreRefEdges);
695
696 Refs = RefEdges.takeVector();
697 for (; RefCnt < FirstWORef; ++RefCnt)
698 Refs[RefCnt].setReadOnly();
699
700 for (; RefCnt < Refs.size(); ++RefCnt)
701 Refs[RefCnt].setWriteOnly();
702 } else {
703 Refs = RefEdges.takeVector();
704 }
705 // Explicit add hot edges to enforce importing for designated GUIDs for
706 // sample PGO, to enable the same inlines as the profiled optimized binary.
707 for (auto &I : F.getImportGUIDs())
708 CallGraphEdges[Index.getOrInsertValueInfo(GUID: I)].updateHotness(
709 OtherHotness: ForceSummaryEdgesCold == FunctionSummary::FSHT_All
710 ? CalleeInfo::HotnessType::Cold
711 : CalleeInfo::HotnessType::Critical);
712
713#ifndef NDEBUG
714 // Make sure that all calls we decided could not have memprof summaries get a
715 // false value for mayHaveMemprofSummary, to ensure that this handling remains
716 // in sync with the ThinLTO backend handling.
717 if (IsThinLTO) {
718 for (const BasicBlock &BB : F) {
719 for (const Instruction &I : BB) {
720 const auto *CB = dyn_cast<CallBase>(&I);
721 if (!CB)
722 continue;
723 // We already checked these above.
724 if (CallsThatMayHaveMemprofSummary.count(CB))
725 continue;
726 assert(!mayHaveMemprofSummary(CB));
727 }
728 }
729 }
730#endif
731
732 bool NonRenamableLocal = isNonRenamableLocal(GV: F);
733 bool NotEligibleForImport =
734 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
735 HasIndirBranchToBlockAddress || HasLocalIFuncCallOrRef;
736 GlobalValueSummary::GVFlags Flags(
737 F.getLinkage(), F.getVisibility(), NotEligibleForImport,
738 /* Live = */ false, F.isDSOLocal(), F.canBeOmittedFromSymbolTable(),
739 GlobalValueSummary::ImportKind::Definition,
740 /* NoRenameOnPromotion = */ false);
741 FunctionSummary::FFlags FunFlags{
742 .ReadNone: F.doesNotAccessMemory(), .ReadOnly: F.onlyReadsMemory() && !F.doesNotAccessMemory(),
743 .NoRecurse: F.hasFnAttribute(Kind: Attribute::NoRecurse), .ReturnDoesNotAlias: F.returnDoesNotAlias(),
744 // FIXME: refactor this to use the same code that inliner is using.
745 // Don't try to import functions with noinline attribute.
746 .NoInline: F.getAttributes().hasFnAttr(Kind: Attribute::NoInline),
747 .AlwaysInline: F.hasFnAttribute(Kind: Attribute::AlwaysInline),
748 .NoUnwind: F.hasFnAttribute(Kind: Attribute::NoUnwind), .MayThrow: MayThrow, .HasUnknownCall: HasUnknownCall,
749 .MustBeUnreachable: mustBeUnreachableFunction(F)};
750 std::vector<FunctionSummary::ParamAccess> ParamAccesses;
751 if (auto *SSI = GetSSICallback(F))
752 ParamAccesses = SSI->getParamAccesses(Index);
753 auto FuncSummary = std::make_unique<FunctionSummary>(
754 args&: Flags, args&: NumInsts, args&: FunFlags, args: std::move(Refs), args: CallGraphEdges.takeVector(),
755 args: TypeTests.takeVector(), args: TypeTestAssumeVCalls.takeVector(),
756 args: TypeCheckedLoadVCalls.takeVector(),
757 args: TypeTestAssumeConstVCalls.takeVector(),
758 args: TypeCheckedLoadConstVCalls.takeVector(), args: std::move(ParamAccesses),
759 args: std::move(Callsites), args: std::move(Allocs));
760 if (NonRenamableLocal)
761 CantBePromoted.insert(V: F.getGUID());
762 Index.addGlobalValueSummary(GV: F, Summary: std::move(FuncSummary));
763}
764
765/// Find function pointers referenced within the given vtable initializer
766/// (or subset of an initializer) \p I. The starting offset of \p I within
767/// the vtable initializer is \p StartingOffset. Any discovered function
768/// pointers are added to \p VTableFuncs along with their cumulative offset
769/// within the initializer.
770static void findFuncPointers(const Constant *I, uint64_t StartingOffset,
771 const Module &M, ModuleSummaryIndex &Index,
772 VTableFuncList &VTableFuncs,
773 const GlobalVariable &OrigGV) {
774 // First check if this is a function pointer.
775 if (I->getType()->isPointerTy()) {
776 auto C = I->stripPointerCasts();
777 auto A = dyn_cast<GlobalAlias>(Val: C);
778 if (isa<Function>(Val: C) || (A && isa<Function>(Val: A->getAliasee()))) {
779 auto GV = dyn_cast<GlobalValue>(Val: C);
780 assert(GV);
781 // We can disregard __cxa_pure_virtual as a possible call target, as
782 // calls to pure virtuals are UB.
783 if (GV && GV->getName() != "__cxa_pure_virtual")
784 VTableFuncs.push_back(x: {Index.getOrInsertValueInfo(GV), StartingOffset});
785 return;
786 }
787 }
788
789 // Walk through the elements in the constant struct or array and recursively
790 // look for virtual function pointers.
791 const DataLayout &DL = M.getDataLayout();
792 if (auto *C = dyn_cast<ConstantStruct>(Val: I)) {
793 StructType *STy = C->getType();
794 assert(STy);
795 const StructLayout *SL = DL.getStructLayout(Ty: C->getType());
796
797 for (auto EI : llvm::enumerate(First: STy->elements())) {
798 auto Offset = SL->getElementOffset(Idx: EI.index());
799 unsigned Op = SL->getElementContainingOffset(FixedOffset: Offset);
800 findFuncPointers(I: cast<Constant>(Val: I->getOperand(i: Op)),
801 StartingOffset: StartingOffset + Offset, M, Index, VTableFuncs, OrigGV);
802 }
803 } else if (auto *C = dyn_cast<ConstantArray>(Val: I)) {
804 ArrayType *ATy = C->getType();
805 Type *EltTy = ATy->getElementType();
806 uint64_t EltSize = DL.getTypeAllocSize(Ty: EltTy);
807 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
808 findFuncPointers(I: cast<Constant>(Val: I->getOperand(i)),
809 StartingOffset: StartingOffset + i * EltSize, M, Index, VTableFuncs,
810 OrigGV);
811 }
812 } else if (const auto *CE = dyn_cast<ConstantExpr>(Val: I)) {
813 // For relative vtables, the next sub-component should be a trunc.
814 if (CE->getOpcode() != Instruction::Trunc ||
815 !(CE = dyn_cast<ConstantExpr>(Val: CE->getOperand(i_nocapture: 0))))
816 return;
817
818 // If this constant can be reduced to the offset between a function and a
819 // global, then we know this is a valid virtual function if the RHS is the
820 // original vtable we're scanning through.
821 if (CE->getOpcode() == Instruction::Sub) {
822 GlobalValue *LHS, *RHS;
823 APSInt LHSOffset, RHSOffset;
824 if (IsConstantOffsetFromGlobal(C: CE->getOperand(i_nocapture: 0), GV&: LHS, Offset&: LHSOffset, DL) &&
825 IsConstantOffsetFromGlobal(C: CE->getOperand(i_nocapture: 1), GV&: RHS, Offset&: RHSOffset, DL) &&
826 RHS == &OrigGV &&
827
828 // For relative vtables, this component should point to the callable
829 // function without any offsets.
830 LHSOffset == 0 &&
831
832 // Also, the RHS should always point to somewhere within the vtable.
833 RHSOffset <=
834 static_cast<uint64_t>(DL.getTypeAllocSize(Ty: OrigGV.getInitializer()->getType()))) {
835 findFuncPointers(I: LHS, StartingOffset, M, Index, VTableFuncs, OrigGV);
836 }
837 }
838 }
839}
840
841// Identify the function pointers referenced by vtable definition \p V.
842static void computeVTableFuncs(ModuleSummaryIndex &Index,
843 const GlobalVariable &V, const Module &M,
844 VTableFuncList &VTableFuncs) {
845 if (!V.isConstant())
846 return;
847
848 findFuncPointers(I: V.getInitializer(), /*StartingOffset=*/0, M, Index,
849 VTableFuncs, OrigGV: V);
850
851#ifndef NDEBUG
852 // Validate that the VTableFuncs list is ordered by offset.
853 uint64_t PrevOffset = 0;
854 for (auto &P : VTableFuncs) {
855 // The findVFuncPointers traversal should have encountered the
856 // functions in offset order. We need to use ">=" since PrevOffset
857 // starts at 0.
858 assert(P.VTableOffset >= PrevOffset);
859 PrevOffset = P.VTableOffset;
860 }
861#endif
862}
863
864/// Record vtable definition \p V for each type metadata it references.
865static void
866recordTypeIdCompatibleVtableReferences(ModuleSummaryIndex &Index,
867 const GlobalVariable &V,
868 SmallVectorImpl<MDNode *> &Types) {
869 for (MDNode *Type : Types) {
870 auto TypeID = Type->getOperand(I: 1).get();
871
872 uint64_t Offset =
873 cast<ConstantInt>(
874 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
875 ->getZExtValue();
876
877 if (auto *TypeId = dyn_cast<MDString>(Val: TypeID))
878 Index.getOrInsertTypeIdCompatibleVtableSummary(TypeId: TypeId->getString())
879 .push_back(x: {Offset, Index.getOrInsertValueInfo(GV: &V)});
880 }
881}
882
883static void computeVariableSummary(ModuleSummaryIndex &Index,
884 const GlobalVariable &V,
885 DenseSet<GlobalValue::GUID> &CantBePromoted,
886 const Module &M,
887 SmallVectorImpl<MDNode *> &Types) {
888 SetVector<ValueInfo, SmallVector<ValueInfo, 0>> RefEdges;
889 SmallPtrSet<const User *, 8> Visited;
890 bool RefLocalIFunc = false;
891 bool HasBlockAddress =
892 findRefEdges(Index, CurUser: &V, RefEdges, Visited, RefLocalLinkageIFunc&: RefLocalIFunc);
893 const bool NotEligibleForImport = (HasBlockAddress || RefLocalIFunc);
894 bool NonRenamableLocal = isNonRenamableLocal(GV: V);
895 GlobalValueSummary::GVFlags Flags(
896 V.getLinkage(), V.getVisibility(), NonRenamableLocal,
897 /* Live = */ false, V.isDSOLocal(), V.canBeOmittedFromSymbolTable(),
898 GlobalValueSummary::Definition, /* NoRenameOnPromotion = */ false);
899
900 VTableFuncList VTableFuncs;
901 // If splitting is not enabled, then we compute the summary information
902 // necessary for index-based whole program devirtualization.
903 if (!Index.enableSplitLTOUnit()) {
904 Types.clear();
905 V.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
906 if (!Types.empty()) {
907 // Identify the function pointers referenced by this vtable definition.
908 computeVTableFuncs(Index, V, M, VTableFuncs);
909
910 // Record this vtable definition for each type metadata it references.
911 recordTypeIdCompatibleVtableReferences(Index, V, Types);
912 }
913 }
914
915 // Don't mark variables we won't be able to internalize as read/write-only.
916 bool CanBeInternalized =
917 !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() &&
918 !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass();
919 bool Constant = V.isConstant();
920 GlobalVarSummary::GVarFlags VarFlags(CanBeInternalized,
921 Constant ? false : CanBeInternalized,
922 Constant, V.getVCallVisibility());
923 auto GVarSummary = std::make_unique<GlobalVarSummary>(args&: Flags, args&: VarFlags,
924 args: RefEdges.takeVector());
925 if (NonRenamableLocal)
926 CantBePromoted.insert(V: V.getGUID());
927 if (NotEligibleForImport)
928 GVarSummary->setNotEligibleToImport();
929 if (!VTableFuncs.empty())
930 GVarSummary->setVTableFuncs(VTableFuncs);
931 Index.addGlobalValueSummary(GV: V, Summary: std::move(GVarSummary));
932}
933
934static void computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
935 DenseSet<GlobalValue::GUID> &CantBePromoted) {
936 // Skip summary for indirect function aliases as summary for aliasee will not
937 // be emitted.
938 const GlobalObject *Aliasee = A.getAliaseeObject();
939 if (isa<GlobalIFunc>(Val: Aliasee))
940 return;
941 bool NonRenamableLocal = isNonRenamableLocal(GV: A);
942 GlobalValueSummary::GVFlags Flags(
943 A.getLinkage(), A.getVisibility(), NonRenamableLocal,
944 /* Live = */ false, A.isDSOLocal(), A.canBeOmittedFromSymbolTable(),
945 GlobalValueSummary::Definition, /* NoRenameOnPromotion = */ false);
946 auto AS = std::make_unique<AliasSummary>(args&: Flags);
947 auto AliaseeVI = Index.getValueInfo(GUID: Aliasee->getGUID());
948 assert(AliaseeVI && "Alias expects aliasee summary to be available");
949 assert(AliaseeVI.getSummaryList().size() == 1 &&
950 "Expected a single entry per aliasee in per-module index");
951 AS->setAliasee(AliaseeVI, Aliasee: AliaseeVI.getSummaryList()[0].get());
952 if (NonRenamableLocal)
953 CantBePromoted.insert(V: A.getGUID());
954 Index.addGlobalValueSummary(GV: A, Summary: std::move(AS));
955}
956
957// Set LiveRoot flag on entries matching the given value name.
958static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
959 if (ValueInfo VI =
960 Index.getValueInfo(GUID: GlobalValue::getGUIDAssumingExternalLinkage(GlobalName: Name)))
961 for (const auto &Summary : VI.getSummaryList())
962 Summary->setLive(true);
963}
964
965ModuleSummaryIndex llvm::buildModuleSummaryIndex(
966 const Module &M,
967 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
968 ProfileSummaryInfo *PSI,
969 std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) {
970 assert(PSI);
971 bool EnableSplitLTOUnit = false;
972 bool UnifiedLTO = false;
973 if (auto *MD = mdconst::extract_or_null<ConstantInt>(
974 MD: M.getModuleFlag(Key: "EnableSplitLTOUnit")))
975 EnableSplitLTOUnit = MD->getZExtValue();
976 if (auto *MD =
977 mdconst::extract_or_null<ConstantInt>(MD: M.getModuleFlag(Key: "UnifiedLTO")))
978 UnifiedLTO = MD->getZExtValue();
979 ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit, UnifiedLTO);
980
981 // Identify the local values in the llvm.used and llvm.compiler.used sets,
982 // which should not be exported as they would then require renaming and
983 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
984 // here because we use this information to mark functions containing inline
985 // assembly calls as not importable.
986 SmallPtrSet<GlobalValue *, 4> LocalsUsed;
987 SmallVector<GlobalValue *, 4> Used;
988 // First collect those in the llvm.used set.
989 collectUsedGlobalVariables(M, Vec&: Used, /*CompilerUsed=*/false);
990 // Next collect those in the llvm.compiler.used set.
991 collectUsedGlobalVariables(M, Vec&: Used, /*CompilerUsed=*/true);
992 DenseSet<GlobalValue::GUID> CantBePromoted;
993 for (auto *V : Used) {
994 if (V->hasLocalLinkage()) {
995 LocalsUsed.insert(Ptr: V);
996 CantBePromoted.insert(V: V->getGUID());
997 }
998 }
999
1000 bool HasLocalInlineAsmSymbol = false;
1001 if (!M.getModuleInlineAsm().empty()) {
1002 // Collect the local values defined by module level asm, and set up
1003 // summaries for these symbols so that they can be marked as NoRename,
1004 // to prevent export of any use of them in regular IR that would require
1005 // renaming within the module level asm. Note we don't need to create a
1006 // summary for weak or global defs, as they don't need to be flagged as
1007 // NoRename, and defs in module level asm can't be imported anyway.
1008 // Also, any values used but not defined within module level asm should
1009 // be listed on the llvm.used or llvm.compiler.used global and marked as
1010 // referenced from there.
1011 ModuleSymbolTable::CollectAsmSymbols(
1012 M, AsmSymbol: [&](StringRef Name, object::BasicSymbolRef::Flags Flags) {
1013 // Symbols not marked as Weak or Global are local definitions.
1014 if (Flags & (object::BasicSymbolRef::SF_Weak |
1015 object::BasicSymbolRef::SF_Global))
1016 return;
1017 HasLocalInlineAsmSymbol = true;
1018 GlobalValue *GV = M.getNamedValue(Name);
1019 if (!GV)
1020 return;
1021 assert(GV->isDeclaration() && "Def in module asm already has definition");
1022 GlobalValueSummary::GVFlags GVFlags(
1023 GlobalValue::InternalLinkage, GlobalValue::DefaultVisibility,
1024 /* NotEligibleToImport = */ true,
1025 /* Live = */ true,
1026 /* Local */ GV->isDSOLocal(), GV->canBeOmittedFromSymbolTable(),
1027 GlobalValueSummary::Definition,
1028 /* NoRenameOnPromotion = */ false);
1029 CantBePromoted.insert(V: GV->getGUID());
1030 // Create the appropriate summary type.
1031 if (Function *F = dyn_cast<Function>(Val: GV)) {
1032 std::unique_ptr<FunctionSummary> Summary =
1033 std::make_unique<FunctionSummary>(
1034 args&: GVFlags, /*InstCount=*/args: 0,
1035 args: FunctionSummary::FFlags{
1036 .ReadNone: F->hasFnAttribute(Kind: Attribute::ReadNone),
1037 .ReadOnly: F->hasFnAttribute(Kind: Attribute::ReadOnly),
1038 .NoRecurse: F->hasFnAttribute(Kind: Attribute::NoRecurse),
1039 .ReturnDoesNotAlias: F->returnDoesNotAlias(),
1040 /* NoInline = */ false,
1041 .AlwaysInline: F->hasFnAttribute(Kind: Attribute::AlwaysInline),
1042 .NoUnwind: F->hasFnAttribute(Kind: Attribute::NoUnwind),
1043 /* MayThrow */ true,
1044 /* HasUnknownCall */ true,
1045 /* MustBeUnreachable */ false},
1046 args: SmallVector<ValueInfo, 0>{},
1047 args: SmallVector<FunctionSummary::EdgeTy, 0>{},
1048 args: ArrayRef<GlobalValue::GUID>{},
1049 args: ArrayRef<FunctionSummary::VFuncId>{},
1050 args: ArrayRef<FunctionSummary::VFuncId>{},
1051 args: ArrayRef<FunctionSummary::ConstVCall>{},
1052 args: ArrayRef<FunctionSummary::ConstVCall>{},
1053 args: ArrayRef<FunctionSummary::ParamAccess>{},
1054 args: ArrayRef<CallsiteInfo>{}, args: ArrayRef<AllocInfo>{});
1055 Index.addGlobalValueSummary(GV: *GV, Summary: std::move(Summary));
1056 } else {
1057 std::unique_ptr<GlobalVarSummary> Summary =
1058 std::make_unique<GlobalVarSummary>(
1059 args&: GVFlags,
1060 args: GlobalVarSummary::GVarFlags(
1061 false, false, cast<GlobalVariable>(Val: GV)->isConstant(),
1062 GlobalObject::VCallVisibilityPublic),
1063 args: SmallVector<ValueInfo, 0>{});
1064 Index.addGlobalValueSummary(GV: *GV, Summary: std::move(Summary));
1065 }
1066 });
1067 }
1068
1069 bool IsThinLTO = true;
1070 if (auto *MD =
1071 mdconst::extract_or_null<ConstantInt>(MD: M.getModuleFlag(Key: "ThinLTO")))
1072 IsThinLTO = MD->getZExtValue();
1073
1074 // Compute summaries for all functions defined in module, and save in the
1075 // index.
1076 for (const auto &F : M) {
1077 if (F.isDeclaration())
1078 continue;
1079
1080 DominatorTree DT(const_cast<Function &>(F));
1081 BlockFrequencyInfo *BFI = nullptr;
1082 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
1083 if (GetBFICallback)
1084 BFI = GetBFICallback(F);
1085 else if (F.hasProfileData()) {
1086 LoopInfo LI{DT};
1087 BranchProbabilityInfo BPI{F, LI};
1088 BFIPtr = std::make_unique<BlockFrequencyInfo>(args: F, args&: BPI, args&: LI);
1089 BFI = BFIPtr.get();
1090 }
1091
1092 computeFunctionSummary(Index, M, F, BFI, PSI, DT,
1093 HasLocalsInUsedOrAsm: !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
1094 CantBePromoted, IsThinLTO, GetSSICallback);
1095 }
1096
1097 // Compute summaries for all variables defined in module, and save in the
1098 // index.
1099 SmallVector<MDNode *, 2> Types;
1100 for (const GlobalVariable &G : M.globals()) {
1101 if (G.isDeclaration())
1102 continue;
1103 computeVariableSummary(Index, V: G, CantBePromoted, M, Types);
1104 }
1105
1106 // Compute summaries for all aliases defined in module, and save in the
1107 // index.
1108 for (const GlobalAlias &A : M.aliases())
1109 computeAliasSummary(Index, A, CantBePromoted);
1110
1111 // Iterate through ifuncs, set their resolvers all alive.
1112 for (const GlobalIFunc &I : M.ifuncs()) {
1113 I.applyAlongResolverPath(Op: [&Index](const GlobalValue &GV) {
1114 Index.getGlobalValueSummary(GV)->setLive(true);
1115 });
1116 }
1117
1118 for (auto *V : LocalsUsed) {
1119 auto *Summary = Index.getGlobalValueSummary(GV: *V);
1120 assert(Summary && "Missing summary for global value");
1121 Summary->setNotEligibleToImport();
1122 }
1123
1124 // The linker doesn't know about these LLVM produced values, so we need
1125 // to flag them as live in the index to ensure index-based dead value
1126 // analysis treats them as live roots of the analysis.
1127 setLiveRoot(Index, Name: "llvm.used");
1128 setLiveRoot(Index, Name: "llvm.compiler.used");
1129 setLiveRoot(Index, Name: "llvm.global_ctors");
1130 setLiveRoot(Index, Name: "llvm.global_dtors");
1131 setLiveRoot(Index, Name: "llvm.global.annotations");
1132
1133 for (auto &GlobalList : Index) {
1134 // Ignore entries for references that are undefined in the current module.
1135 if (GlobalList.second.getSummaryList().empty())
1136 continue;
1137
1138 assert(GlobalList.second.getSummaryList().size() == 1 &&
1139 "Expected module's index to have one summary per GUID");
1140 auto &Summary = GlobalList.second.getSummaryList()[0];
1141 if (!IsThinLTO) {
1142 Summary->setNotEligibleToImport();
1143 continue;
1144 }
1145
1146 bool AllRefsCanBeExternallyReferenced =
1147 llvm::all_of(Range: Summary->refs(), P: [&](const ValueInfo &VI) {
1148 return !CantBePromoted.count(V: VI.getGUID());
1149 });
1150 if (!AllRefsCanBeExternallyReferenced) {
1151 Summary->setNotEligibleToImport();
1152 continue;
1153 }
1154
1155 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Val: Summary.get())) {
1156 bool AllCallsCanBeExternallyReferenced = llvm::all_of(
1157 Range: FuncSummary->calls(), P: [&](const FunctionSummary::EdgeTy &Edge) {
1158 return !CantBePromoted.count(V: Edge.first.getGUID());
1159 });
1160 if (!AllCallsCanBeExternallyReferenced)
1161 Summary->setNotEligibleToImport();
1162 }
1163 }
1164
1165 if (!ModuleSummaryDotFile.empty()) {
1166 std::error_code EC;
1167 raw_fd_ostream OSDot(ModuleSummaryDotFile, EC, sys::fs::OpenFlags::OF_Text);
1168 if (EC)
1169 report_fatal_error(reason: Twine("Failed to open dot file ") +
1170 ModuleSummaryDotFile + ": " + EC.message() + "\n");
1171 Index.exportToDot(OS&: OSDot, GUIDPreservedSymbols: {});
1172 }
1173
1174 return Index;
1175}
1176
1177AnalysisKey ModuleSummaryIndexAnalysis::Key;
1178
1179ModuleSummaryIndex
1180ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
1181 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(IR&: M);
1182 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
1183 bool NeedSSI = needsParamAccessSummary(M);
1184 return buildModuleSummaryIndex(
1185 M,
1186 GetBFICallback: [&FAM](const Function &F) {
1187 return &FAM.getResult<BlockFrequencyAnalysis>(
1188 IR&: *const_cast<Function *>(&F));
1189 },
1190 PSI: &PSI,
1191 GetSSICallback: [&FAM, NeedSSI](const Function &F) -> const StackSafetyInfo * {
1192 return NeedSSI ? &FAM.getResult<StackSafetyAnalysis>(
1193 IR&: const_cast<Function &>(F))
1194 : nullptr;
1195 });
1196}
1197
1198char ModuleSummaryIndexWrapperPass::ID = 0;
1199
1200INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
1201 "Module Summary Analysis", false, true)
1202INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
1203INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
1204INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)
1205INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
1206 "Module Summary Analysis", false, true)
1207
1208ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
1209 return new ModuleSummaryIndexWrapperPass();
1210}
1211
1212ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
1213 : ModulePass(ID) {}
1214
1215bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
1216 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
1217 bool NeedSSI = needsParamAccessSummary(M);
1218 Index.emplace(args: buildModuleSummaryIndex(
1219 M,
1220 GetBFICallback: [this](const Function &F) {
1221 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
1222 F&: *const_cast<Function *>(&F))
1223 .getBFI());
1224 },
1225 PSI,
1226 GetSSICallback: [&](const Function &F) -> const StackSafetyInfo * {
1227 return NeedSSI ? &getAnalysis<StackSafetyInfoWrapperPass>(
1228 F&: const_cast<Function &>(F))
1229 .getResult()
1230 : nullptr;
1231 }));
1232 return false;
1233}
1234
1235bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
1236 Index.reset();
1237 return false;
1238}
1239
1240void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1241 AU.setPreservesAll();
1242 AU.addRequired<BlockFrequencyInfoWrapperPass>();
1243 AU.addRequired<ProfileSummaryInfoWrapperPass>();
1244 AU.addRequired<StackSafetyInfoWrapperPass>();
1245}
1246
1247char ImmutableModuleSummaryIndexWrapperPass::ID = 0;
1248
1249ImmutableModuleSummaryIndexWrapperPass::ImmutableModuleSummaryIndexWrapperPass(
1250 const ModuleSummaryIndex *Index)
1251 : ImmutablePass(ID), Index(Index) {}
1252
1253void ImmutableModuleSummaryIndexWrapperPass::getAnalysisUsage(
1254 AnalysisUsage &AU) const {
1255 AU.setPreservesAll();
1256}
1257
1258ImmutablePass *llvm::createImmutableModuleSummaryIndexWrapperPass(
1259 const ModuleSummaryIndex *Index) {
1260 return new ImmutableModuleSummaryIndexWrapperPass(Index);
1261}
1262
1263INITIALIZE_PASS(ImmutableModuleSummaryIndexWrapperPass, "module-summary-info",
1264 "Module summary info", false, true)
1265
1266bool llvm::mayHaveMemprofSummary(const CallBase *CB) {
1267 if (!CB)
1268 return false;
1269 if (CB->isDebugOrPseudoInst())
1270 return false;
1271 auto *CI = dyn_cast<CallInst>(Val: CB);
1272 auto *CalledValue = CB->getCalledOperand();
1273 auto *CalledFunction = CB->getCalledFunction();
1274 if (CalledValue && !CalledFunction) {
1275 CalledValue = CalledValue->stripPointerCasts();
1276 // Stripping pointer casts can reveal a called function.
1277 CalledFunction = dyn_cast<Function>(Val: CalledValue);
1278 }
1279 // Check if this is an alias to a function. If so, get the
1280 // called aliasee for the checks below.
1281 if (auto *GA = dyn_cast<GlobalAlias>(Val: CalledValue)) {
1282 assert(!CalledFunction &&
1283 "Expected null called function in callsite for alias");
1284 CalledFunction = dyn_cast<Function>(Val: GA->getAliaseeObject());
1285 }
1286 // Check if this is a direct call to a known function or a known
1287 // intrinsic, or an indirect call with profile data.
1288 if (CalledFunction) {
1289 if (CI && CalledFunction->isIntrinsic())
1290 return false;
1291 } else {
1292 // Skip indirect calls if we haven't enabled memprof ICP.
1293 if (!EnableMemProfIndirectCallSupport)
1294 return false;
1295 // Skip inline assembly calls.
1296 if (CI && CI->isInlineAsm())
1297 return false;
1298 // Skip direct calls via Constant.
1299 if (!CalledValue || isa<Constant>(Val: CalledValue))
1300 return false;
1301 return true;
1302 }
1303 return true;
1304}
1305