1 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
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 file implements the module index and summary classes for the
11 // IR library.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/IR/ModuleSummaryIndex.h"
16 #include "llvm/ADT/SCCIterator.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/StringMap.h"
19 #include "llvm/Support/Path.h"
20 #include "llvm/Support/raw_ostream.h"
21 using namespace llvm;
22
23 #define DEBUG_TYPE "module-summary-index"
24
25 STATISTIC(ReadOnlyLiveGVars,
26 "Number of live global variables marked read only");
27
28 FunctionSummary FunctionSummary::ExternalNode =
29 FunctionSummary::makeDummyFunctionSummary({});
isDSOLocal() const30 bool ValueInfo::isDSOLocal() const {
31 // Need to check all summaries are local in case of hash collisions.
32 return getSummaryList().size() &&
33 llvm::all_of(getSummaryList(),
34 [](const std::unique_ptr<GlobalValueSummary> &Summary) {
35 return Summary->isDSOLocal();
36 });
37 }
38
39 // Gets the number of immutable refs in RefEdgeList
immutableRefCount() const40 unsigned FunctionSummary::immutableRefCount() const {
41 // Here we take advantage of having all readonly references
42 // located in the end of the RefEdgeList.
43 auto Refs = refs();
44 unsigned ImmutableRefCnt = 0;
45 for (int I = Refs.size() - 1; I >= 0 && Refs[I].isReadOnly(); --I)
46 ImmutableRefCnt++;
47 return ImmutableRefCnt;
48 }
49
50 // Collect for the given module the list of function it defines
51 // (GUID -> Summary).
collectDefinedFunctionsForModule(StringRef ModulePath,GVSummaryMapTy & GVSummaryMap) const52 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
53 StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
54 for (auto &GlobalList : *this) {
55 auto GUID = GlobalList.first;
56 for (auto &GlobSummary : GlobalList.second.SummaryList) {
57 auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
58 if (!Summary)
59 // Ignore global variable, focus on functions
60 continue;
61 // Ignore summaries from other modules.
62 if (Summary->modulePath() != ModulePath)
63 continue;
64 GVSummaryMap[GUID] = Summary;
65 }
66 }
67 }
68
69 // Collect for each module the list of function it defines (GUID -> Summary).
collectDefinedGVSummariesPerModule(StringMap<GVSummaryMapTy> & ModuleToDefinedGVSummaries) const70 void ModuleSummaryIndex::collectDefinedGVSummariesPerModule(
71 StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const {
72 for (auto &GlobalList : *this) {
73 auto GUID = GlobalList.first;
74 for (auto &Summary : GlobalList.second.SummaryList) {
75 ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
76 }
77 }
78 }
79
80 GlobalValueSummary *
getGlobalValueSummary(uint64_t ValueGUID,bool PerModuleIndex) const81 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
82 bool PerModuleIndex) const {
83 auto VI = getValueInfo(ValueGUID);
84 assert(VI && "GlobalValue not found in index");
85 assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
86 "Expected a single entry per global value in per-module index");
87 auto &Summary = VI.getSummaryList()[0];
88 return Summary.get();
89 }
90
isGUIDLive(GlobalValue::GUID GUID) const91 bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
92 auto VI = getValueInfo(GUID);
93 if (!VI)
94 return true;
95 const auto &SummaryList = VI.getSummaryList();
96 if (SummaryList.empty())
97 return true;
98 for (auto &I : SummaryList)
99 if (isGlobalValueLive(I.get()))
100 return true;
101 return false;
102 }
103
propagateConstantsToRefs(GlobalValueSummary * S)104 static void propagateConstantsToRefs(GlobalValueSummary *S) {
105 // If reference is not readonly then referenced summary is not
106 // readonly either. Note that:
107 // - All references from GlobalVarSummary are conservatively considered as
108 // not readonly. Tracking them properly requires more complex analysis
109 // then we have now.
110 //
111 // - AliasSummary objects have no refs at all so this function is a no-op
112 // for them.
113 for (auto &VI : S->refs()) {
114 if (VI.isReadOnly()) {
115 // We only mark refs as readonly when computing function summaries on
116 // analysis phase.
117 assert(isa<FunctionSummary>(S));
118 continue;
119 }
120 for (auto &Ref : VI.getSummaryList())
121 // If references to alias is not readonly then aliasee is not readonly
122 if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject()))
123 GVS->setReadOnly(false);
124 }
125 }
126
127 // Do the constant propagation in combined index.
128 // The goal of constant propagation is internalization of readonly
129 // variables. To determine which variables are readonly and which
130 // are not we take following steps:
131 // - During analysis we speculatively assign readonly attribute to
132 // all variables which can be internalized. When computing function
133 // summary we also assign readonly attribute to a reference if
134 // function doesn't modify referenced variable.
135 //
136 // - After computing dead symbols in combined index we do the constant
137 // propagation. During this step we clear readonly attribute from
138 // all variables which:
139 // a. are preserved or can't be imported
140 // b. referenced by any global variable initializer
141 // c. referenced by a function and reference is not readonly
142 //
143 // Internalization itself happens in the backend after import is finished
144 // See internalizeImmutableGVs.
propagateConstants(const DenseSet<GlobalValue::GUID> & GUIDPreservedSymbols)145 void ModuleSummaryIndex::propagateConstants(
146 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
147 for (auto &P : *this)
148 for (auto &S : P.second.SummaryList) {
149 if (!isGlobalValueLive(S.get()))
150 // We don't examine references from dead objects
151 continue;
152
153 // Global variable can't be marked read only if it is not eligible
154 // to import since we need to ensure that all external references
155 // get a local (imported) copy. It also can't be marked read only
156 // if it or any alias (since alias points to the same memory) are
157 // preserved or notEligibleToImport, since either of those means
158 // there could be writes that are not visible (because preserved
159 // means it could have external to DSO writes, and notEligibleToImport
160 // means it could have writes via inline assembly leading it to be
161 // in the @llvm.*used).
162 if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
163 // Here we intentionally pass S.get() not GVS, because S could be
164 // an alias.
165 if (!canImportGlobalVar(S.get()) || GUIDPreservedSymbols.count(P.first))
166 GVS->setReadOnly(false);
167 propagateConstantsToRefs(S.get());
168 }
169 if (llvm::AreStatisticsEnabled())
170 for (auto &P : *this)
171 if (P.second.SummaryList.size())
172 if (auto *GVS = dyn_cast<GlobalVarSummary>(
173 P.second.SummaryList[0]->getBaseObject()))
174 if (isGlobalValueLive(GVS) && GVS->isReadOnly())
175 ReadOnlyLiveGVars++;
176 }
177
178 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
179 // then delete this function and update its tests
180 LLVM_DUMP_METHOD
dumpSCCs(raw_ostream & O)181 void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
182 for (scc_iterator<ModuleSummaryIndex *> I =
183 scc_begin<ModuleSummaryIndex *>(this);
184 !I.isAtEnd(); ++I) {
185 O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
186 << ") {\n";
187 for (const ValueInfo V : *I) {
188 FunctionSummary *F = nullptr;
189 if (V.getSummaryList().size())
190 F = cast<FunctionSummary>(V.getSummaryList().front().get());
191 O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
192 << (I.hasLoop() ? " (has loop)" : "") << "\n";
193 }
194 O << "}\n";
195 }
196 }
197
198 namespace {
199 struct Attributes {
200 void add(const Twine &Name, const Twine &Value,
201 const Twine &Comment = Twine());
202 void addComment(const Twine &Comment);
203 std::string getAsString() const;
204
205 std::vector<std::string> Attrs;
206 std::string Comments;
207 };
208
209 struct Edge {
210 uint64_t SrcMod;
211 int Hotness;
212 GlobalValue::GUID Src;
213 GlobalValue::GUID Dst;
214 };
215 }
216
add(const Twine & Name,const Twine & Value,const Twine & Comment)217 void Attributes::add(const Twine &Name, const Twine &Value,
218 const Twine &Comment) {
219 std::string A = Name.str();
220 A += "=\"";
221 A += Value.str();
222 A += "\"";
223 Attrs.push_back(A);
224 addComment(Comment);
225 }
226
addComment(const Twine & Comment)227 void Attributes::addComment(const Twine &Comment) {
228 if (!Comment.isTriviallyEmpty()) {
229 if (Comments.empty())
230 Comments = " // ";
231 else
232 Comments += ", ";
233 Comments += Comment.str();
234 }
235 }
236
getAsString() const237 std::string Attributes::getAsString() const {
238 if (Attrs.empty())
239 return "";
240
241 std::string Ret = "[";
242 for (auto &A : Attrs)
243 Ret += A + ",";
244 Ret.pop_back();
245 Ret += "];";
246 Ret += Comments;
247 return Ret;
248 }
249
linkageToString(GlobalValue::LinkageTypes LT)250 static std::string linkageToString(GlobalValue::LinkageTypes LT) {
251 switch (LT) {
252 case GlobalValue::ExternalLinkage:
253 return "extern";
254 case GlobalValue::AvailableExternallyLinkage:
255 return "av_ext";
256 case GlobalValue::LinkOnceAnyLinkage:
257 return "linkonce";
258 case GlobalValue::LinkOnceODRLinkage:
259 return "linkonce_odr";
260 case GlobalValue::WeakAnyLinkage:
261 return "weak";
262 case GlobalValue::WeakODRLinkage:
263 return "weak_odr";
264 case GlobalValue::AppendingLinkage:
265 return "appending";
266 case GlobalValue::InternalLinkage:
267 return "internal";
268 case GlobalValue::PrivateLinkage:
269 return "private";
270 case GlobalValue::ExternalWeakLinkage:
271 return "extern_weak";
272 case GlobalValue::CommonLinkage:
273 return "common";
274 }
275
276 return "<unknown>";
277 }
278
fflagsToString(FunctionSummary::FFlags F)279 static std::string fflagsToString(FunctionSummary::FFlags F) {
280 auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
281 char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
282 FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias),
283 FlagValue(F.NoInline), 0};
284
285 return FlagRep;
286 }
287
288 // Get string representation of function instruction count and flags.
getSummaryAttributes(GlobalValueSummary * GVS)289 static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
290 auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
291 if (!FS)
292 return "";
293
294 return std::string("inst: ") + std::to_string(FS->instCount()) +
295 ", ffl: " + fflagsToString(FS->fflags());
296 }
297
getNodeVisualName(GlobalValue::GUID Id)298 static std::string getNodeVisualName(GlobalValue::GUID Id) {
299 return std::string("@") + std::to_string(Id);
300 }
301
getNodeVisualName(const ValueInfo & VI)302 static std::string getNodeVisualName(const ValueInfo &VI) {
303 return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
304 }
305
getNodeLabel(const ValueInfo & VI,GlobalValueSummary * GVS)306 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
307 if (isa<AliasSummary>(GVS))
308 return getNodeVisualName(VI);
309
310 std::string Attrs = getSummaryAttributes(GVS);
311 std::string Label =
312 getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
313 if (!Attrs.empty())
314 Label += std::string(" (") + Attrs + ")";
315 Label += "}";
316
317 return Label;
318 }
319
320 // Write definition of external node, which doesn't have any
321 // specific module associated with it. Typically this is function
322 // or variable defined in native object or library.
defineExternalNode(raw_ostream & OS,const char * Pfx,const ValueInfo & VI,GlobalValue::GUID Id)323 static void defineExternalNode(raw_ostream &OS, const char *Pfx,
324 const ValueInfo &VI, GlobalValue::GUID Id) {
325 auto StrId = std::to_string(Id);
326 OS << " " << StrId << " [label=\"";
327
328 if (VI) {
329 OS << getNodeVisualName(VI);
330 } else {
331 OS << getNodeVisualName(Id);
332 }
333 OS << "\"]; // defined externally\n";
334 }
335
hasReadOnlyFlag(const GlobalValueSummary * S)336 static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
337 if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
338 return GVS->isReadOnly();
339 return false;
340 }
341
exportToDot(raw_ostream & OS) const342 void ModuleSummaryIndex::exportToDot(raw_ostream &OS) const {
343 std::vector<Edge> CrossModuleEdges;
344 DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
345 StringMap<GVSummaryMapTy> ModuleToDefinedGVS;
346 collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
347
348 // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
349 // because we may have multiple linkonce functions summaries.
350 auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
351 return ModId == (uint64_t)-1 ? std::to_string(Id)
352 : std::string("M") + std::to_string(ModId) +
353 "_" + std::to_string(Id);
354 };
355
356 auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
357 uint64_t DstMod, GlobalValue::GUID DstId,
358 int TypeOrHotness) {
359 // 0 - alias
360 // 1 - reference
361 // 2 - constant reference
362 // Other value: (hotness - 3).
363 TypeOrHotness += 3;
364 static const char *EdgeAttrs[] = {
365 " [style=dotted]; // alias",
366 " [style=dashed]; // ref",
367 " [style=dashed,color=forestgreen]; // const-ref",
368 " // call (hotness : Unknown)",
369 " [color=blue]; // call (hotness : Cold)",
370 " // call (hotness : None)",
371 " [color=brown]; // call (hotness : Hot)",
372 " [style=bold,color=red]; // call (hotness : Critical)"};
373
374 assert(static_cast<size_t>(TypeOrHotness) <
375 sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
376 OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
377 << EdgeAttrs[TypeOrHotness] << "\n";
378 };
379
380 OS << "digraph Summary {\n";
381 for (auto &ModIt : ModuleToDefinedGVS) {
382 auto ModId = getModuleId(ModIt.first());
383 OS << " // Module: " << ModIt.first() << "\n";
384 OS << " subgraph cluster_" << std::to_string(ModId) << " {\n";
385 OS << " style = filled;\n";
386 OS << " color = lightgrey;\n";
387 OS << " label = \"" << sys::path::filename(ModIt.first()) << "\";\n";
388 OS << " node [style=filled,fillcolor=lightblue];\n";
389
390 auto &GVSMap = ModIt.second;
391 auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
392 if (!GVSMap.count(IdTo)) {
393 CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
394 return;
395 }
396 DrawEdge(" ", ModId, IdFrom, ModId, IdTo, Hotness);
397 };
398
399 for (auto &SummaryIt : GVSMap) {
400 NodeMap[SummaryIt.first].push_back(ModId);
401 auto Flags = SummaryIt.second->flags();
402 Attributes A;
403 if (isa<FunctionSummary>(SummaryIt.second)) {
404 A.add("shape", "record", "function");
405 } else if (isa<AliasSummary>(SummaryIt.second)) {
406 A.add("style", "dotted,filled", "alias");
407 A.add("shape", "box");
408 } else {
409 A.add("shape", "Mrecord", "variable");
410 if (Flags.Live && hasReadOnlyFlag(SummaryIt.second))
411 A.addComment("immutable");
412 }
413
414 auto VI = getValueInfo(SummaryIt.first);
415 A.add("label", getNodeLabel(VI, SummaryIt.second));
416 if (!Flags.Live)
417 A.add("fillcolor", "red", "dead");
418 else if (Flags.NotEligibleToImport)
419 A.add("fillcolor", "yellow", "not eligible to import");
420
421 OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
422 << "\n";
423 }
424 OS << " // Edges:\n";
425
426 for (auto &SummaryIt : GVSMap) {
427 auto *GVS = SummaryIt.second;
428 for (auto &R : GVS->refs())
429 Draw(SummaryIt.first, R.getGUID(), R.isReadOnly() ? -1 : -2);
430
431 if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
432 GlobalValue::GUID AliaseeId;
433 if (AS->hasAliaseeGUID())
434 AliaseeId = AS->getAliaseeGUID();
435 else {
436 auto AliaseeOrigId = AS->getAliasee().getOriginalName();
437 AliaseeId = getGUIDFromOriginalID(AliaseeOrigId);
438 if (!AliaseeId)
439 AliaseeId = AliaseeOrigId;
440 }
441
442 Draw(SummaryIt.first, AliaseeId, -3);
443 continue;
444 }
445
446 if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
447 for (auto &CGEdge : FS->calls())
448 Draw(SummaryIt.first, CGEdge.first.getGUID(),
449 static_cast<int>(CGEdge.second.Hotness));
450 }
451 OS << " }\n";
452 }
453
454 OS << " // Cross-module edges:\n";
455 for (auto &E : CrossModuleEdges) {
456 auto &ModList = NodeMap[E.Dst];
457 if (ModList.empty()) {
458 defineExternalNode(OS, " ", getValueInfo(E.Dst), E.Dst);
459 // Add fake module to the list to draw an edge to an external node
460 // in the loop below.
461 ModList.push_back(-1);
462 }
463 for (auto DstMod : ModList)
464 // The edge representing call or ref is drawn to every module where target
465 // symbol is defined. When target is a linkonce symbol there can be
466 // multiple edges representing a single call or ref, both intra-module and
467 // cross-module. As we've already drawn all intra-module edges before we
468 // skip it here.
469 if (DstMod != E.SrcMod)
470 DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
471 }
472
473 OS << "}";
474 }
475