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