LLVM  10.0.0svn
ModuleSummaryIndex.cpp
Go to the documentation of this file.
1 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
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 file implements the module index and summary classes for the
10 // IR library.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SCCIterator.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/ADT/StringMap.h"
18 #include "llvm/Support/Path.h"
20 using namespace llvm;
21 
22 #define DEBUG_TYPE "module-summary-index"
23 
24 STATISTIC(ReadOnlyLiveGVars,
25  "Number of live global variables marked read only");
26 STATISTIC(WriteOnlyLiveGVars,
27  "Number of live global variables marked write only");
28 
31 
32 bool ValueInfo::isDSOLocal() const {
33  // Need to check all summaries are local in case of hash collisions.
34  return getSummaryList().size() &&
36  [](const std::unique_ptr<GlobalValueSummary> &Summary) {
37  return Summary->isDSOLocal();
38  });
39 }
40 
41 bool ValueInfo::canAutoHide() const {
42  // Can only auto hide if all copies are eligible to auto hide.
43  return getSummaryList().size() &&
45  [](const std::unique_ptr<GlobalValueSummary> &Summary) {
46  return Summary->canAutoHide();
47  });
48 }
49 
50 // Gets the number of readonly and writeonly refs in RefEdgeList
51 std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const {
52  // Here we take advantage of having all readonly and writeonly references
53  // located in the end of the RefEdgeList.
54  auto Refs = refs();
55  unsigned RORefCnt = 0, WORefCnt = 0;
56  int I;
57  for (I = Refs.size() - 1; I >= 0 && Refs[I].isWriteOnly(); --I)
58  WORefCnt++;
59  for (; I >= 0 && Refs[I].isReadOnly(); --I)
60  RORefCnt++;
61  return {RORefCnt, WORefCnt};
62 }
63 
64 // Collect for the given module the list of function it defines
65 // (GUID -> Summary).
67  StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
68  for (auto &GlobalList : *this) {
69  auto GUID = GlobalList.first;
70  for (auto &GlobSummary : GlobalList.second.SummaryList) {
71  auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
72  if (!Summary)
73  // Ignore global variable, focus on functions
74  continue;
75  // Ignore summaries from other modules.
76  if (Summary->modulePath() != ModulePath)
77  continue;
78  GVSummaryMap[GUID] = Summary;
79  }
80  }
81 }
82 
85  bool PerModuleIndex) const {
86  auto VI = getValueInfo(ValueGUID);
87  assert(VI && "GlobalValue not found in index");
88  assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
89  "Expected a single entry per global value in per-module index");
90  auto &Summary = VI.getSummaryList()[0];
91  return Summary.get();
92 }
93 
95  auto VI = getValueInfo(GUID);
96  if (!VI)
97  return true;
98  const auto &SummaryList = VI.getSummaryList();
99  if (SummaryList.empty())
100  return true;
101  for (auto &I : SummaryList)
102  if (isGlobalValueLive(I.get()))
103  return true;
104  return false;
105 }
106 
108  // If reference is not readonly or writeonly then referenced summary is not
109  // read/writeonly either. Note that:
110  // - All references from GlobalVarSummary are conservatively considered as
111  // not readonly or writeonly. Tracking them properly requires more complex
112  // analysis then we have now.
113  //
114  // - AliasSummary objects have no refs at all so this function is a no-op
115  // for them.
116  for (auto &VI : S->refs()) {
117  assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
118  for (auto &Ref : VI.getSummaryList())
119  // If references to alias is not read/writeonly then aliasee
120  // is not read/writeonly
121  if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
122  if (!VI.isReadOnly())
123  GVS->setReadOnly(false);
124  if (!VI.isWriteOnly())
125  GVS->setWriteOnly(false);
126  }
127  }
128 }
129 
130 // Do the access attribute propagation in combined index.
131 // The goal of attribute propagation is internalization of readonly (RO)
132 // or writeonly (WO) variables. To determine which variables are RO or WO
133 // and which are not we take following steps:
134 // - During analysis we speculatively assign readonly and writeonly
135 // attribute to all variables which can be internalized. When computing
136 // function summary we also assign readonly or writeonly attribute to a
137 // reference if function doesn't modify referenced variable (readonly)
138 // or doesn't read it (writeonly).
139 //
140 // - After computing dead symbols in combined index we do the attribute
141 // propagation. During this step we:
142 // a. clear RO and WO attributes from variables which are preserved or
143 // can't be imported
144 // b. clear RO and WO attributes from variables referenced by any global
145 // variable initializer
146 // c. clear RO attribute from variable referenced by a function when
147 // reference is not readonly
148 // d. clear WO attribute from variable referenced by a function when
149 // reference is not writeonly
150 //
151 // Because of (c, d) we don't internalize variables read by function A
152 // and modified by function B.
153 //
154 // Internalization itself happens in the backend after import is finished
155 // See internalizeGVsAfterImport.
157  const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
158  for (auto &P : *this)
159  for (auto &S : P.second.SummaryList) {
160  if (!isGlobalValueLive(S.get()))
161  // We don't examine references from dead objects
162  continue;
163 
164  // Global variable can't be marked read/writeonly if it is not eligible
165  // to import since we need to ensure that all external references get
166  // a local (imported) copy. It also can't be marked read/writeonly if
167  // it or any alias (since alias points to the same memory) are preserved
168  // or notEligibleToImport, since either of those means there could be
169  // writes (or reads in case of writeonly) that are not visible (because
170  // preserved means it could have external to DSO writes or reads, and
171  // notEligibleToImport means it could have writes or reads via inline
172  // assembly leading it to be in the @llvm.*used).
173  if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
174  // Here we intentionally pass S.get() not GVS, because S could be
175  // an alias.
176  if (!canImportGlobalVar(S.get()) ||
177  GUIDPreservedSymbols.count(P.first)) {
178  GVS->setReadOnly(false);
179  GVS->setWriteOnly(false);
180  }
181  propagateAttributesToRefs(S.get());
182  }
184  for (auto &P : *this)
185  if (P.second.SummaryList.size())
186  if (auto *GVS = dyn_cast<GlobalVarSummary>(
187  P.second.SummaryList[0]->getBaseObject()))
188  if (isGlobalValueLive(GVS)) {
189  if (GVS->maybeReadOnly())
190  ReadOnlyLiveGVars++;
191  if (GVS->maybeWriteOnly())
192  WriteOnlyLiveGVars++;
193  }
194 }
195 
196 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
197 // then delete this function and update its tests
201  scc_begin<ModuleSummaryIndex *>(this);
202  !I.isAtEnd(); ++I) {
203  O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
204  << ") {\n";
205  for (const ValueInfo V : *I) {
206  FunctionSummary *F = nullptr;
207  if (V.getSummaryList().size())
208  F = cast<FunctionSummary>(V.getSummaryList().front().get());
209  O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
210  << (I.hasLoop() ? " (has loop)" : "") << "\n";
211  }
212  O << "}\n";
213  }
214 }
215 
216 namespace {
217 struct Attributes {
218  void add(const Twine &Name, const Twine &Value,
219  const Twine &Comment = Twine());
220  void addComment(const Twine &Comment);
221  std::string getAsString() const;
222 
223  std::vector<std::string> Attrs;
224  std::string Comments;
225 };
226 
227 struct Edge {
228  uint64_t SrcMod;
229  int Hotness;
230  GlobalValue::GUID Src;
231  GlobalValue::GUID Dst;
232 };
233 }
234 
235 void Attributes::add(const Twine &Name, const Twine &Value,
236  const Twine &Comment) {
237  std::string A = Name.str();
238  A += "=\"";
239  A += Value.str();
240  A += "\"";
241  Attrs.push_back(A);
242  addComment(Comment);
243 }
244 
245 void Attributes::addComment(const Twine &Comment) {
246  if (!Comment.isTriviallyEmpty()) {
247  if (Comments.empty())
248  Comments = " // ";
249  else
250  Comments += ", ";
251  Comments += Comment.str();
252  }
253 }
254 
255 std::string Attributes::getAsString() const {
256  if (Attrs.empty())
257  return "";
258 
259  std::string Ret = "[";
260  for (auto &A : Attrs)
261  Ret += A + ",";
262  Ret.pop_back();
263  Ret += "];";
264  Ret += Comments;
265  return Ret;
266 }
267 
269  switch (LT) {
271  return "extern";
273  return "av_ext";
275  return "linkonce";
277  return "linkonce_odr";
279  return "weak";
281  return "weak_odr";
283  return "appending";
285  return "internal";
287  return "private";
289  return "extern_weak";
291  return "common";
292  }
293 
294  return "<unknown>";
295 }
296 
298  auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
299  char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
300  FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias),
301  FlagValue(F.NoInline), 0};
302 
303  return FlagRep;
304 }
305 
306 // Get string representation of function instruction count and flags.
307 static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
308  auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
309  if (!FS)
310  return "";
311 
312  return std::string("inst: ") + std::to_string(FS->instCount()) +
313  ", ffl: " + fflagsToString(FS->fflags());
314 }
315 
317  return std::string("@") + std::to_string(Id);
318 }
319 
320 static std::string getNodeVisualName(const ValueInfo &VI) {
321  return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
322 }
323 
324 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
325  if (isa<AliasSummary>(GVS))
326  return getNodeVisualName(VI);
327 
328  std::string Attrs = getSummaryAttributes(GVS);
329  std::string Label =
330  getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
331  if (!Attrs.empty())
332  Label += std::string(" (") + Attrs + ")";
333  Label += "}";
334 
335  return Label;
336 }
337 
338 // Write definition of external node, which doesn't have any
339 // specific module associated with it. Typically this is function
340 // or variable defined in native object or library.
341 static void defineExternalNode(raw_ostream &OS, const char *Pfx,
342  const ValueInfo &VI, GlobalValue::GUID Id) {
343  auto StrId = std::to_string(Id);
344  OS << " " << StrId << " [label=\"";
345 
346  if (VI) {
347  OS << getNodeVisualName(VI);
348  } else {
349  OS << getNodeVisualName(Id);
350  }
351  OS << "\"]; // defined externally\n";
352 }
353 
354 static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
355  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
356  return GVS->maybeReadOnly();
357  return false;
358 }
359 
360 static bool hasWriteOnlyFlag(const GlobalValueSummary *S) {
361  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
362  return GVS->maybeWriteOnly();
363  return false;
364 }
365 
367  std::vector<Edge> CrossModuleEdges;
369  using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
370  std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS;
371  collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
372 
373  // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
374  // because we may have multiple linkonce functions summaries.
375  auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
376  return ModId == (uint64_t)-1 ? std::to_string(Id)
377  : std::string("M") + std::to_string(ModId) +
378  "_" + std::to_string(Id);
379  };
380 
381  auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
382  uint64_t DstMod, GlobalValue::GUID DstId,
383  int TypeOrHotness) {
384  // 0 - alias
385  // 1 - reference
386  // 2 - constant reference
387  // 3 - writeonly reference
388  // Other value: (hotness - 4).
389  TypeOrHotness += 4;
390  static const char *EdgeAttrs[] = {
391  " [style=dotted]; // alias",
392  " [style=dashed]; // ref",
393  " [style=dashed,color=forestgreen]; // const-ref",
394  " [style=dashed,color=violetred]; // writeOnly-ref",
395  " // call (hotness : Unknown)",
396  " [color=blue]; // call (hotness : Cold)",
397  " // call (hotness : None)",
398  " [color=brown]; // call (hotness : Hot)",
399  " [style=bold,color=red]; // call (hotness : Critical)"};
400 
401  assert(static_cast<size_t>(TypeOrHotness) <
402  sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
403  OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
404  << EdgeAttrs[TypeOrHotness] << "\n";
405  };
406 
407  OS << "digraph Summary {\n";
408  for (auto &ModIt : ModuleToDefinedGVS) {
409  auto ModId = getModuleId(ModIt.first);
410  OS << " // Module: " << ModIt.first << "\n";
411  OS << " subgraph cluster_" << std::to_string(ModId) << " {\n";
412  OS << " style = filled;\n";
413  OS << " color = lightgrey;\n";
414  OS << " label = \"" << sys::path::filename(ModIt.first) << "\";\n";
415  OS << " node [style=filled,fillcolor=lightblue];\n";
416 
417  auto &GVSMap = ModIt.second;
418  auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
419  if (!GVSMap.count(IdTo)) {
420  CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
421  return;
422  }
423  DrawEdge(" ", ModId, IdFrom, ModId, IdTo, Hotness);
424  };
425 
426  for (auto &SummaryIt : GVSMap) {
427  NodeMap[SummaryIt.first].push_back(ModId);
428  auto Flags = SummaryIt.second->flags();
429  Attributes A;
430  if (isa<FunctionSummary>(SummaryIt.second)) {
431  A.add("shape", "record", "function");
432  } else if (isa<AliasSummary>(SummaryIt.second)) {
433  A.add("style", "dotted,filled", "alias");
434  A.add("shape", "box");
435  } else {
436  A.add("shape", "Mrecord", "variable");
437  if (Flags.Live && hasReadOnlyFlag(SummaryIt.second))
438  A.addComment("immutable");
439  if (Flags.Live && hasWriteOnlyFlag(SummaryIt.second))
440  A.addComment("writeOnly");
441  }
442  if (Flags.DSOLocal)
443  A.addComment("dsoLocal");
444  if (Flags.CanAutoHide)
445  A.addComment("canAutoHide");
446 
447  auto VI = getValueInfo(SummaryIt.first);
448  A.add("label", getNodeLabel(VI, SummaryIt.second));
449  if (!Flags.Live)
450  A.add("fillcolor", "red", "dead");
451  else if (Flags.NotEligibleToImport)
452  A.add("fillcolor", "yellow", "not eligible to import");
453 
454  OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
455  << "\n";
456  }
457  OS << " // Edges:\n";
458 
459  for (auto &SummaryIt : GVSMap) {
460  auto *GVS = SummaryIt.second;
461  for (auto &R : GVS->refs())
462  Draw(SummaryIt.first, R.getGUID(),
463  R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3));
464 
465  if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
466  Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
467  continue;
468  }
469 
470  if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
471  for (auto &CGEdge : FS->calls())
472  Draw(SummaryIt.first, CGEdge.first.getGUID(),
473  static_cast<int>(CGEdge.second.Hotness));
474  }
475  OS << " }\n";
476  }
477 
478  OS << " // Cross-module edges:\n";
479  for (auto &E : CrossModuleEdges) {
480  auto &ModList = NodeMap[E.Dst];
481  if (ModList.empty()) {
482  defineExternalNode(OS, " ", getValueInfo(E.Dst), E.Dst);
483  // Add fake module to the list to draw an edge to an external node
484  // in the loop below.
485  ModList.push_back(-1);
486  }
487  for (auto DstMod : ModList)
488  // The edge representing call or ref is drawn to every module where target
489  // symbol is defined. When target is a linkonce symbol there can be
490  // multiple edges representing a single call or ref, both intra-module and
491  // cross-module. As we've already drawn all intra-module edges before we
492  // skip it here.
493  if (DstMod != E.SrcMod)
494  DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
495  }
496 
497  OS << "}";
498 }
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
Special purpose, only applies to global arrays.
Definition: GlobalValue.h:54
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:218
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:502
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
static std::string linkageToString(GlobalValue::LinkageTypes LT)
Same, but only replaced by something equivalent.
Definition: GlobalValue.h:53
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
GlobalValueSummary * getGlobalValueSummary(const GlobalValue &GV, bool PerModuleIndex=true) const
Returns the first GlobalValueSummary for GV, asserting that there is only one if PerModuleIndex.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
Available for inspection, not emission.
Definition: GlobalValue.h:49
ArrayRef< ValueInfo > refs() const
Return the list of values referenced by this global value definition.
bool isTriviallyEmpty() const
Check if this twine is trivially empty; a false return value does not necessarily mean the twine is e...
Definition: Twine.h:400
uint32_t NodeId
Definition: RDFGraph.h:260
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:56
Externally visible function.
Definition: GlobalValue.h:48
GlobalValue::LinkageTypes linkage() const
Return linkage type recorded for this global value.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
STATISTIC(NumFunctions, "Total number of functions")
F(f)
Tentative definitions.
Definition: GlobalValue.h:58
GlobalValue::GUID getGUID() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
The access may reference the value stored in memory.
static bool canImportGlobalVar(GlobalValueSummary *S)
LLVM_NODISCARD bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:126
static std::string getSummaryAttributes(GlobalValueSummary *GVS)
bool canAutoHide() const
Checks if all copies are eligible for auto-hiding (have flag set).
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
ArrayRef< std::unique_ptr< GlobalValueSummary > > getSummaryList() const
static bool hasReadOnlyFlag(const GlobalValueSummary *S)
ExternalWeak linkage description.
Definition: GlobalValue.h:57
#define P(N)
Same, but only replaced by something equivalent.
Definition: GlobalValue.h:51
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
StringRef name() const
bool isGUIDLive(GlobalValue::GUID GUID) const
static void propagateAttributesToRefs(GlobalValueSummary *S)
Function and variable summary information to aid decisions and implementation of importing.
Struct that holds a reference to a particular GUID in a global value summary.
static std::string fflagsToString(FunctionSummary::FFlags F)
bool isDSOLocal() const
static bool hasWriteOnlyFlag(const GlobalValueSummary *S)
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:207
Keep one copy of function when linking (inline)
Definition: GlobalValue.h:50
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:223
static FunctionSummary makeDummyFunctionSummary(std::vector< FunctionSummary::EdgeTy > Edges)
Create an empty FunctionSummary (with specified call edges).
LinkageTypes
An enumeration for the kinds of linkage for global values.
Definition: GlobalValue.h:47
void propagateAttributes(const DenseSet< GlobalValue::GUID > &PreservedSymbols)
Analyze index and detect unmodified globals.
StringRef filename(StringRef path, Style style=Style::native)
Get filename.
Definition: Path.cpp:565
void exportToDot(raw_ostream &OS) const
Export summary to dot file for GraphViz.
static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS)
void dumpSCCs(raw_ostream &OS)
Print out strongly connected components for debugging.
#define I(x, y, z)
Definition: MD5.cpp:58
static void defineExternalNode(raw_ostream &OS, const char *Pfx, const ValueInfo &VI, GlobalValue::GUID Id)
Keep one copy of named function when linking (weak)
Definition: GlobalValue.h:52
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
Flags specific to function summaries.
Function summary information to aid decisions and implementation of importing.
std::string str() const
Return the twine contents as a std::string.
Definition: Twine.cpp:17
static std::string getNodeVisualName(GlobalValue::GUID Id)
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
std::pair< unsigned, unsigned > specialRefCounts() const
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:133
void collectDefinedFunctionsForModule(StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const
Collect for the given module the list of functions it defines (GUID -> Summary).
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
static FunctionSummary ExternalNode
A dummy node to reference external functions that aren&#39;t in the index.