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