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