blob: 4950780ae757822c0499321722e22e0d08f8cc47 [file] [log] [blame]
Teresa Johnson2d5487c2016-04-11 13:58:45 +00001//===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass builds a ModuleSummaryIndex object for the module, to be written
11// to bitcode or LLVM assembly.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/ModuleSummaryAnalysis.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000016#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseSet.h"
Peter Collingbourne0c30f082016-12-20 21:12:28 +000018#include "llvm/ADT/MapVector.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000019#include "llvm/ADT/STLExtras.h"
Peter Collingbourne0c30f082016-12-20 21:12:28 +000020#include "llvm/ADT/SetVector.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000021#include "llvm/ADT/SmallPtrSet.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/StringRef.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000024#include "llvm/Analysis/BlockFrequencyInfo.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000025#include "llvm/Analysis/BranchProbabilityInfo.h"
Teresa Johnsoncd21a642016-07-17 14:47:01 +000026#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000027#include "llvm/Analysis/LoopInfo.h"
Piotr Padlewskid9830eb2016-09-26 20:37:32 +000028#include "llvm/Analysis/ProfileSummaryInfo.h"
Peter Collingbourne1b4137a72016-12-21 23:03:45 +000029#include "llvm/Analysis/TypeMetadataUtils.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000030#include "llvm/IR/Attributes.h"
31#include "llvm/IR/BasicBlock.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000032#include "llvm/IR/CallSite.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000033#include "llvm/IR/Constant.h"
34#include "llvm/IR/Constants.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000035#include "llvm/IR/Dominators.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000036#include "llvm/IR/Function.h"
37#include "llvm/IR/GlobalAlias.h"
38#include "llvm/IR/GlobalValue.h"
39#include "llvm/IR/GlobalVariable.h"
40#include "llvm/IR/Instructions.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000041#include "llvm/IR/IntrinsicInst.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000042#include "llvm/IR/Intrinsics.h"
43#include "llvm/IR/Metadata.h"
44#include "llvm/IR/Module.h"
45#include "llvm/IR/ModuleSummaryIndex.h"
46#include "llvm/IR/Use.h"
47#include "llvm/IR/User.h"
Peter Collingbourne61781ac2017-03-31 00:08:24 +000048#include "llvm/Object/ModuleSymbolTable.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000049#include "llvm/Object/SymbolicFile.h"
Teresa Johnson2d5487c2016-04-11 13:58:45 +000050#include "llvm/Pass.h"
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +000051#include "llvm/Support/Casting.h"
52#include <algorithm>
53#include <cassert>
54#include <cstdint>
55#include <vector>
56
Teresa Johnson2d5487c2016-04-11 13:58:45 +000057using namespace llvm;
58
59#define DEBUG_TYPE "module-summary-analysis"
60
61// Walk through the operands of a given User via worklist iteration and populate
62// the set of GlobalValue references encountered. Invoked either on an
63// Instruction or a GlobalVariable (which walks its initializer).
Peter Collingbourne9667b912017-05-04 18:03:25 +000064static void findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
65 SetVector<ValueInfo> &RefEdges,
Teresa Johnson2d5487c2016-04-11 13:58:45 +000066 SmallPtrSet<const User *, 8> &Visited) {
67 SmallVector<const User *, 32> Worklist;
68 Worklist.push_back(CurUser);
69
70 while (!Worklist.empty()) {
71 const User *U = Worklist.pop_back_val();
72
73 if (!Visited.insert(U).second)
74 continue;
75
76 ImmutableCallSite CS(U);
77
78 for (const auto &OI : U->operands()) {
79 const User *Operand = dyn_cast<User>(OI);
80 if (!Operand)
81 continue;
82 if (isa<BlockAddress>(Operand))
83 continue;
Peter Collingbourne0c30f082016-12-20 21:12:28 +000084 if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
Teresa Johnson2d5487c2016-04-11 13:58:45 +000085 // We have a reference to a global value. This should be added to
86 // the reference set unless it is a callee. Callees are handled
87 // specially by WriteFunction and are added to a separate list.
88 if (!(CS && CS.isCallee(&OI)))
Peter Collingbourne9667b912017-05-04 18:03:25 +000089 RefEdges.insert(Index.getOrInsertValueInfo(GV));
Teresa Johnson2d5487c2016-04-11 13:58:45 +000090 continue;
91 }
92 Worklist.push_back(Operand);
93 }
94 }
95}
96
Piotr Padlewskid9830eb2016-09-26 20:37:32 +000097static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
98 ProfileSummaryInfo *PSI) {
99 if (!PSI)
100 return CalleeInfo::HotnessType::Unknown;
101 if (PSI->isHotCount(ProfileCount))
102 return CalleeInfo::HotnessType::Hot;
103 if (PSI->isColdCount(ProfileCount))
104 return CalleeInfo::HotnessType::Cold;
105 return CalleeInfo::HotnessType::None;
106}
107
Teresa Johnson519465b2017-01-05 14:32:16 +0000108static bool isNonRenamableLocal(const GlobalValue &GV) {
109 return GV.hasSection() && GV.hasLocalLinkage();
110}
111
Peter Collingbournebe9ffaa2017-02-10 22:29:38 +0000112/// Determine whether this call has all constant integer arguments (excluding
113/// "this") and summarize it to VCalls or ConstVCalls as appropriate.
114static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid,
115 SetVector<FunctionSummary::VFuncId> &VCalls,
116 SetVector<FunctionSummary::ConstVCall> &ConstVCalls) {
117 std::vector<uint64_t> Args;
118 // Start from the second argument to skip the "this" pointer.
119 for (auto &Arg : make_range(Call.CS.arg_begin() + 1, Call.CS.arg_end())) {
120 auto *CI = dyn_cast<ConstantInt>(Arg);
121 if (!CI || CI->getBitWidth() > 64) {
122 VCalls.insert({Guid, Call.Offset});
123 return;
124 }
125 Args.push_back(CI->getZExtValue());
126 }
127 ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
128}
129
130/// If this intrinsic call requires that we add information to the function
131/// summary, do so via the non-constant reference arguments.
132static void addIntrinsicToSummary(
133 const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
134 SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
135 SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
136 SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
137 SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls) {
138 switch (CI->getCalledFunction()->getIntrinsicID()) {
139 case Intrinsic::type_test: {
140 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
141 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
142 if (!TypeId)
143 break;
144 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
145
146 // Produce a summary from type.test intrinsics. We only summarize type.test
147 // intrinsics that are used other than by an llvm.assume intrinsic.
148 // Intrinsics that are assumed are relevant only to the devirtualization
149 // pass, not the type test lowering pass.
150 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
151 auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
152 if (!AssumeCI)
153 return true;
154 Function *F = AssumeCI->getCalledFunction();
155 return !F || F->getIntrinsicID() != Intrinsic::assume;
156 });
157 if (HasNonAssumeUses)
158 TypeTests.insert(Guid);
159
160 SmallVector<DevirtCallSite, 4> DevirtCalls;
161 SmallVector<CallInst *, 4> Assumes;
162 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI);
163 for (auto &Call : DevirtCalls)
164 addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
165 TypeTestAssumeConstVCalls);
166
167 break;
168 }
169
170 case Intrinsic::type_checked_load: {
171 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
172 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
173 if (!TypeId)
174 break;
175 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
176
177 SmallVector<DevirtCallSite, 4> DevirtCalls;
178 SmallVector<Instruction *, 4> LoadedPtrs;
179 SmallVector<Instruction *, 4> Preds;
180 bool HasNonCallUses = false;
181 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
182 HasNonCallUses, CI);
183 // Any non-call uses of the result of llvm.type.checked.load will
184 // prevent us from optimizing away the llvm.type.test.
185 if (HasNonCallUses)
186 TypeTests.insert(Guid);
187 for (auto &Call : DevirtCalls)
188 addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
189 TypeCheckedLoadConstVCalls);
190
191 break;
192 }
193 default:
194 break;
195 }
196}
197
Teresa Johnson519465b2017-01-05 14:32:16 +0000198static void
199computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
200 const Function &F, BlockFrequencyInfo *BFI,
Peter Collingbourne5e8b94c12017-09-01 16:24:02 +0000201 ProfileSummaryInfo *PSI, bool HasLocalsInUsedOrAsm,
Teresa Johnsone27b0582017-01-05 14:59:56 +0000202 DenseSet<GlobalValue::GUID> &CantBePromoted) {
Teresa Johnson02563cd2016-10-28 02:39:38 +0000203 // Summary not currently supported for anonymous functions, they should
204 // have been named.
205 assert(F.hasName());
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000206
207 unsigned NumInsts = 0;
208 // Map from callee ValueId to profile count. Used to accumulate profile
209 // counts for all static calls to a given callee.
Peter Collingbourne0c30f082016-12-20 21:12:28 +0000210 MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
211 SetVector<ValueInfo> RefEdges;
Peter Collingbourne1b4137a72016-12-21 23:03:45 +0000212 SetVector<GlobalValue::GUID> TypeTests;
Peter Collingbournebe9ffaa2017-02-10 22:29:38 +0000213 SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
214 TypeCheckedLoadVCalls;
215 SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
216 TypeCheckedLoadConstVCalls;
Teresa Johnsoncd21a642016-07-17 14:47:01 +0000217 ICallPromotionAnalysis ICallAnalysis;
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000218
Teresa Johnsond5033a42016-11-14 16:40:19 +0000219 bool HasInlineAsmMaybeReferencingInternal = false;
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000220 SmallPtrSet<const User *, 8> Visited;
Benjamin Krameraa209152016-06-26 17:27:42 +0000221 for (const BasicBlock &BB : F)
222 for (const Instruction &I : BB) {
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000223 if (isa<DbgInfoIntrinsic>(I))
224 continue;
225 ++NumInsts;
Peter Collingbourne9667b912017-05-04 18:03:25 +0000226 findRefEdges(Index, &I, RefEdges, Visited);
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000227 auto CS = ImmutableCallSite(&I);
228 if (!CS)
229 continue;
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000230
231 const auto *CI = dyn_cast<CallInst>(&I);
232 // Since we don't know exactly which local values are referenced in inline
Teresa Johnsond5033a42016-11-14 16:40:19 +0000233 // assembly, conservatively mark the function as possibly referencing
234 // a local value from inline assembly to ensure we don't export a
235 // reference (which would require renaming and promotion of the
236 // referenced value).
Peter Collingbourne5e8b94c12017-09-01 16:24:02 +0000237 if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm())
Teresa Johnsond5033a42016-11-14 16:40:19 +0000238 HasInlineAsmMaybeReferencingInternal = true;
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000239
Teresa Johnson897bab92016-10-08 16:11:42 +0000240 auto *CalledValue = CS.getCalledValue();
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000241 auto *CalledFunction = CS.getCalledFunction();
Teresa Johnson897bab92016-10-08 16:11:42 +0000242 // Check if this is an alias to a function. If so, get the
243 // called aliasee for the checks below.
244 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
245 assert(!CalledFunction && "Expected null called function in callsite for alias");
246 CalledFunction = dyn_cast<Function>(GA->getBaseObject());
247 }
Peter Collingbourne1b4137a72016-12-21 23:03:45 +0000248 // Check if this is a direct call to a known function or a known
249 // intrinsic, or an indirect call with profile data.
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000250 if (CalledFunction) {
Peter Collingbournebe9ffaa2017-02-10 22:29:38 +0000251 if (CI && CalledFunction->isIntrinsic()) {
252 addIntrinsicToSummary(
253 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
254 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls);
255 continue;
Peter Collingbourne1b4137a72016-12-21 23:03:45 +0000256 }
Teresa Johnson02563cd2016-10-28 02:39:38 +0000257 // We should have named any anonymous globals
258 assert(CalledFunction->hasName());
Easwaran Ramanf5f91602017-05-09 23:21:10 +0000259 auto ScaledCount = PSI->getProfileCount(&I, BFI);
Peter Collingbourne0c30f082016-12-20 21:12:28 +0000260 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
261 : CalleeInfo::HotnessType::Unknown;
262
Teresa Johnson897bab92016-10-08 16:11:42 +0000263 // Use the original CalledValue, in case it was an alias. We want
264 // to record the call edge to the alias in that case. Eventually
265 // an alias summary will be created to associate the alias and
266 // aliasee.
Peter Collingbourne9667b912017-05-04 18:03:25 +0000267 CallGraphEdges[Index.getOrInsertValueInfo(
268 cast<GlobalValue>(CalledValue))]
269 .updateHotness(Hotness);
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000270 } else {
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000271 // Skip inline assembly calls.
272 if (CI && CI->isInlineAsm())
273 continue;
274 // Skip direct calls.
275 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
276 continue;
277
278 uint32_t NumVals, NumCandidates;
279 uint64_t TotalCount;
280 auto CandidateProfileData =
281 ICallAnalysis.getPromotionCandidatesForInstruction(
282 &I, NumVals, TotalCount, NumCandidates);
283 for (auto &Candidate : CandidateProfileData)
Peter Collingbourne9667b912017-05-04 18:03:25 +0000284 CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
285 .updateHotness(getHotness(Candidate.Count, PSI));
Piotr Padlewski442d38c2016-08-30 00:46:26 +0000286 }
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000287 }
288
Dehao Chena60cdd32017-02-28 18:09:44 +0000289 // Explicit add hot edges to enforce importing for designated GUIDs for
290 // sample PGO, to enable the same inlines as the profiled optimized binary.
291 for (auto &I : F.getImportGUIDs())
Peter Collingbourne9667b912017-05-04 18:03:25 +0000292 CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
Dehao Chen64c46572017-07-07 21:01:00 +0000293 CalleeInfo::HotnessType::Critical);
Dehao Chena60cdd32017-02-28 18:09:44 +0000294
Teresa Johnson519465b2017-01-05 14:32:16 +0000295 bool NonRenamableLocal = isNonRenamableLocal(F);
296 bool NotEligibleForImport =
297 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
298 // Inliner doesn't handle variadic functions.
299 // FIXME: refactor this to use the same code that inliner is using.
300 F.isVarArg();
Teresa Johnson6c475a72017-01-05 21:34:18 +0000301 GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
Evgeniy Stepanov56584bb2017-06-01 20:30:06 +0000302 /* Live = */ false);
Charles Saternos75da10d2017-08-04 16:00:58 +0000303 FunctionSummary::FFlags FunFlags{
304 F.hasFnAttribute(Attribute::ReadNone),
305 F.hasFnAttribute(Attribute::ReadOnly),
306 F.hasFnAttribute(Attribute::NoRecurse),
307 F.returnDoesNotAlias(),
308 };
Peter Collingbourne0c30f082016-12-20 21:12:28 +0000309 auto FuncSummary = llvm::make_unique<FunctionSummary>(
Charles Saternos75da10d2017-08-04 16:00:58 +0000310 Flags, NumInsts, FunFlags, RefEdges.takeVector(),
311 CallGraphEdges.takeVector(), TypeTests.takeVector(),
312 TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
Peter Collingbournebe9ffaa2017-02-10 22:29:38 +0000313 TypeTestAssumeConstVCalls.takeVector(),
314 TypeCheckedLoadConstVCalls.takeVector());
Teresa Johnson519465b2017-01-05 14:32:16 +0000315 if (NonRenamableLocal)
316 CantBePromoted.insert(F.getGUID());
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000317 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000318}
319
Teresa Johnson519465b2017-01-05 14:32:16 +0000320static void
321computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
Teresa Johnsone27b0582017-01-05 14:59:56 +0000322 DenseSet<GlobalValue::GUID> &CantBePromoted) {
Peter Collingbourne0c30f082016-12-20 21:12:28 +0000323 SetVector<ValueInfo> RefEdges;
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000324 SmallPtrSet<const User *, 8> Visited;
Peter Collingbourne9667b912017-05-04 18:03:25 +0000325 findRefEdges(Index, &V, RefEdges, Visited);
Teresa Johnson519465b2017-01-05 14:32:16 +0000326 bool NonRenamableLocal = isNonRenamableLocal(V);
Teresa Johnson6c475a72017-01-05 21:34:18 +0000327 GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
Evgeniy Stepanov56584bb2017-06-01 20:30:06 +0000328 /* Live = */ false);
Peter Collingbourne0c30f082016-12-20 21:12:28 +0000329 auto GVarSummary =
330 llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
Teresa Johnson519465b2017-01-05 14:32:16 +0000331 if (NonRenamableLocal)
332 CantBePromoted.insert(V.getGUID());
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000333 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000334}
335
Teresa Johnson519465b2017-01-05 14:32:16 +0000336static void
337computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
Teresa Johnsone27b0582017-01-05 14:59:56 +0000338 DenseSet<GlobalValue::GUID> &CantBePromoted) {
Teresa Johnson519465b2017-01-05 14:32:16 +0000339 bool NonRenamableLocal = isNonRenamableLocal(A);
Teresa Johnson6c475a72017-01-05 21:34:18 +0000340 GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
Evgeniy Stepanov56584bb2017-06-01 20:30:06 +0000341 /* Live = */ false);
Peter Collingbourne0c30f082016-12-20 21:12:28 +0000342 auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{});
Teresa Johnson02563cd2016-10-28 02:39:38 +0000343 auto *Aliasee = A.getBaseObject();
344 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
345 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
346 AS->setAliasee(AliaseeSummary);
Teresa Johnson519465b2017-01-05 14:32:16 +0000347 if (NonRenamableLocal)
348 CantBePromoted.insert(A.getGUID());
Teresa Johnson02563cd2016-10-28 02:39:38 +0000349 Index.addGlobalValueSummary(A.getName(), std::move(AS));
350}
351
Teresa Johnson6c475a72017-01-05 21:34:18 +0000352// Set LiveRoot flag on entries matching the given value name.
353static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
Peter Collingbourne9667b912017-05-04 18:03:25 +0000354 if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
355 for (auto &Summary : VI.getSummaryList())
Evgeniy Stepanov56584bb2017-06-01 20:30:06 +0000356 Summary->setLive(true);
Teresa Johnson6c475a72017-01-05 21:34:18 +0000357}
358
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000359ModuleSummaryIndex llvm::buildModuleSummaryIndex(
360 const Module &M,
Piotr Padlewskid9830eb2016-09-26 20:37:32 +0000361 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
362 ProfileSummaryInfo *PSI) {
Teresa Johnson94624ac2017-05-10 18:52:16 +0000363 assert(PSI);
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000364 ModuleSummaryIndex Index;
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000365
Teresa Johnsona0811452016-11-10 16:57:32 +0000366 // Identify the local values in the llvm.used and llvm.compiler.used sets,
367 // which should not be exported as they would then require renaming and
368 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
369 // here because we use this information to mark functions containing inline
370 // assembly calls as not importable.
Mehdi Aminib6a11a72016-11-09 01:45:13 +0000371 SmallPtrSet<GlobalValue *, 8> LocalsUsed;
Teresa Johnsona0811452016-11-10 16:57:32 +0000372 SmallPtrSet<GlobalValue *, 8> Used;
373 // First collect those in the llvm.used set.
374 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
Teresa Johnsona0811452016-11-10 16:57:32 +0000375 // Next collect those in the llvm.compiler.used set.
376 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
Teresa Johnsone27b0582017-01-05 14:59:56 +0000377 DenseSet<GlobalValue::GUID> CantBePromoted;
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000378 for (auto *V : Used) {
Teresa Johnson519465b2017-01-05 14:32:16 +0000379 if (V->hasLocalLinkage()) {
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000380 LocalsUsed.insert(V);
Teresa Johnson519465b2017-01-05 14:32:16 +0000381 CantBePromoted.insert(V->getGUID());
382 }
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000383 }
Teresa Johnsonb35cc692016-04-20 14:39:45 +0000384
Peter Collingbourne5e8b94c12017-09-01 16:24:02 +0000385 bool HasLocalInlineAsmSymbol = false;
386 if (!M.getModuleInlineAsm().empty()) {
387 // Collect the local values defined by module level asm, and set up
388 // summaries for these symbols so that they can be marked as NoRename,
389 // to prevent export of any use of them in regular IR that would require
390 // renaming within the module level asm. Note we don't need to create a
391 // summary for weak or global defs, as they don't need to be flagged as
392 // NoRename, and defs in module level asm can't be imported anyway.
393 // Also, any values used but not defined within module level asm should
394 // be listed on the llvm.used or llvm.compiler.used global and marked as
395 // referenced from there.
396 ModuleSymbolTable::CollectAsmSymbols(
397 M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) {
398 // Symbols not marked as Weak or Global are local definitions.
399 if (Flags & (object::BasicSymbolRef::SF_Weak |
400 object::BasicSymbolRef::SF_Global))
401 return;
402 HasLocalInlineAsmSymbol = true;
403 GlobalValue *GV = M.getNamedValue(Name);
404 if (!GV)
405 return;
406 assert(GV->isDeclaration() && "Def in module asm already has definition");
407 GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
408 /* NotEligibleToImport = */ true,
409 /* Live = */ true);
410 CantBePromoted.insert(GlobalValue::getGUID(Name));
411 // Create the appropriate summary type.
412 if (Function *F = dyn_cast<Function>(GV)) {
413 std::unique_ptr<FunctionSummary> Summary =
414 llvm::make_unique<FunctionSummary>(
415 GVFlags, 0,
416 FunctionSummary::FFlags{
417 F->hasFnAttribute(Attribute::ReadNone),
418 F->hasFnAttribute(Attribute::ReadOnly),
419 F->hasFnAttribute(Attribute::NoRecurse),
420 F->returnDoesNotAlias()},
421 ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{},
422 ArrayRef<GlobalValue::GUID>{},
423 ArrayRef<FunctionSummary::VFuncId>{},
424 ArrayRef<FunctionSummary::VFuncId>{},
425 ArrayRef<FunctionSummary::ConstVCall>{},
426 ArrayRef<FunctionSummary::ConstVCall>{});
427 Index.addGlobalValueSummary(Name, std::move(Summary));
428 } else {
429 std::unique_ptr<GlobalVarSummary> Summary =
430 llvm::make_unique<GlobalVarSummary>(GVFlags,
431 ArrayRef<ValueInfo>{});
432 Index.addGlobalValueSummary(Name, std::move(Summary));
433 }
434 });
435 }
436
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000437 // Compute summaries for all functions defined in module, and save in the
438 // index.
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000439 for (auto &F : M) {
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000440 if (F.isDeclaration())
441 continue;
442
443 BlockFrequencyInfo *BFI = nullptr;
444 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000445 if (GetBFICallback)
446 BFI = GetBFICallback(F);
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000447 else if (F.getEntryCount().hasValue()) {
448 LoopInfo LI{DominatorTree(const_cast<Function &>(F))};
449 BranchProbabilityInfo BPI{F, LI};
450 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
451 BFI = BFIPtr.get();
452 }
453
Peter Collingbourne5e8b94c12017-09-01 16:24:02 +0000454 computeFunctionSummary(Index, M, F, BFI, PSI,
455 !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
Teresa Johnson519465b2017-01-05 14:32:16 +0000456 CantBePromoted);
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000457 }
458
George Rimar1e94ca12017-08-22 08:50:56 +0000459 // Set live flag for all personality functions. That allows to
460 // preserve them during DCE.
461 for (const llvm::Function &F : M)
462 if (!F.isDeclaration() && F.hasPersonalityFn())
463 setLiveRoot(Index, F.getPersonalityFn()->getName());
464
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000465 // Compute summaries for all variables defined in module, and save in the
466 // index.
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000467 for (const GlobalVariable &G : M.globals()) {
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000468 if (G.isDeclaration())
469 continue;
Teresa Johnson519465b2017-01-05 14:32:16 +0000470 computeVariableSummary(Index, G, CantBePromoted);
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000471 }
Teresa Johnson02563cd2016-10-28 02:39:38 +0000472
473 // Compute summaries for all aliases defined in module, and save in the
474 // index.
475 for (const GlobalAlias &A : M.aliases())
Teresa Johnson519465b2017-01-05 14:32:16 +0000476 computeAliasSummary(Index, A, CantBePromoted);
Teresa Johnson02563cd2016-10-28 02:39:38 +0000477
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000478 for (auto *V : LocalsUsed) {
479 auto *Summary = Index.getGlobalValueSummary(*V);
480 assert(Summary && "Missing summary for global value");
Teresa Johnson519465b2017-01-05 14:32:16 +0000481 Summary->setNotEligibleToImport();
Teresa Johnsonbf28c8f2016-10-30 05:40:44 +0000482 }
483
Teresa Johnson6c475a72017-01-05 21:34:18 +0000484 // The linker doesn't know about these LLVM produced values, so we need
485 // to flag them as live in the index to ensure index-based dead value
486 // analysis treats them as live roots of the analysis.
487 setLiveRoot(Index, "llvm.used");
488 setLiveRoot(Index, "llvm.compiler.used");
489 setLiveRoot(Index, "llvm.global_ctors");
490 setLiveRoot(Index, "llvm.global_dtors");
491 setLiveRoot(Index, "llvm.global.annotations");
492
Peter Collingbournee357fbd2017-06-08 23:01:49 +0000493 bool IsThinLTO = true;
494 if (auto *MD =
495 mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))
496 IsThinLTO = MD->getZExtValue();
497
Teresa Johnson519465b2017-01-05 14:32:16 +0000498 for (auto &GlobalList : Index) {
Peter Collingbourne9667b912017-05-04 18:03:25 +0000499 // Ignore entries for references that are undefined in the current module.
500 if (GlobalList.second.SummaryList.empty())
501 continue;
502
503 assert(GlobalList.second.SummaryList.size() == 1 &&
Teresa Johnson519465b2017-01-05 14:32:16 +0000504 "Expected module's index to have one summary per GUID");
Peter Collingbourne9667b912017-05-04 18:03:25 +0000505 auto &Summary = GlobalList.second.SummaryList[0];
Peter Collingbournee357fbd2017-06-08 23:01:49 +0000506 if (!IsThinLTO) {
507 Summary->setNotEligibleToImport();
508 continue;
509 }
510
Teresa Johnson519465b2017-01-05 14:32:16 +0000511 bool AllRefsCanBeExternallyReferenced =
512 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
Peter Collingbourne9667b912017-05-04 18:03:25 +0000513 return !CantBePromoted.count(VI.getGUID());
Teresa Johnson519465b2017-01-05 14:32:16 +0000514 });
515 if (!AllRefsCanBeExternallyReferenced) {
516 Summary->setNotEligibleToImport();
517 continue;
518 }
519
520 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
521 bool AllCallsCanBeExternallyReferenced = llvm::all_of(
522 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
Peter Collingbourne9667b912017-05-04 18:03:25 +0000523 return !CantBePromoted.count(Edge.first.getGUID());
Teresa Johnson519465b2017-01-05 14:32:16 +0000524 });
525 if (!AllCallsCanBeExternallyReferenced)
526 Summary->setNotEligibleToImport();
527 }
528 }
529
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000530 return Index;
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000531}
532
Chandler Carruthdab4eae2016-11-23 17:53:26 +0000533AnalysisKey ModuleSummaryIndexAnalysis::Key;
Teresa Johnsonf93b2462016-08-12 13:53:02 +0000534
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000535ModuleSummaryIndex
Teresa Johnsonf93b2462016-08-12 13:53:02 +0000536ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
Piotr Padlewskid9830eb2016-09-26 20:37:32 +0000537 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
Teresa Johnsonf93b2462016-08-12 13:53:02 +0000538 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
Piotr Padlewskid9830eb2016-09-26 20:37:32 +0000539 return buildModuleSummaryIndex(
540 M,
541 [&FAM](const Function &F) {
542 return &FAM.getResult<BlockFrequencyAnalysis>(
543 *const_cast<Function *>(&F));
544 },
545 &PSI);
Teresa Johnsonf93b2462016-08-12 13:53:02 +0000546}
547
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000548char ModuleSummaryIndexWrapperPass::ID = 0;
Eugene Zelenkobb1b2d02017-08-16 22:07:40 +0000549
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000550INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
551 "Module Summary Analysis", false, true)
552INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
Mehdi Amini89029482017-01-21 06:01:22 +0000553INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000554INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
555 "Module Summary Analysis", false, true)
556
557ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
558 return new ModuleSummaryIndexWrapperPass();
559}
560
561ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
562 : ModulePass(ID) {
563 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
564}
565
566bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
Dehao Chen5461d8b2016-09-28 21:00:58 +0000567 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
Piotr Padlewskid9830eb2016-09-26 20:37:32 +0000568 Index = buildModuleSummaryIndex(
569 M,
570 [this](const Function &F) {
571 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
572 *const_cast<Function *>(&F))
573 .getBFI());
574 },
575 &PSI);
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000576 return false;
577}
578
579bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
Chandler Carruthb7be5b62016-08-19 07:49:19 +0000580 Index.reset();
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000581 return false;
582}
583
584void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
585 AU.setPreservesAll();
586 AU.addRequired<BlockFrequencyInfoWrapperPass>();
Piotr Padlewskid9830eb2016-09-26 20:37:32 +0000587 AU.addRequired<ProfileSummaryInfoWrapperPass>();
Teresa Johnson2d5487c2016-04-11 13:58:45 +0000588}