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