LLVM  8.0.0svn
ModuleSummaryIndex.cpp
Go to the documentation of this file.
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 
16 #include "llvm/ADT/SCCIterator.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/ADT/StringMap.h"
19 #include "llvm/Support/Path.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 
30 bool ValueInfo::isDSOLocal() const {
31  // Need to check all summaries are local in case of hash collisions.
32  return getSummaryList().size() &&
34  [](const std::unique_ptr<GlobalValueSummary> &Summary) {
35  return Summary->isDSOLocal();
36  });
37 }
38 
39 // Gets the number of immutable refs in RefEdgeList
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).
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).
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 
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 
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 
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.
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  }
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
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 
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 
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 
237 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 
251  switch (LT) {
253  return "extern";
255  return "av_ext";
257  return "linkonce";
259  return "linkonce_odr";
261  return "weak";
263  return "weak_odr";
265  return "appending";
267  return "internal";
269  return "private";
271  return "extern_weak";
273  return "common";
274  }
275 
276  return "<unknown>";
277 }
278 
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.
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 
299  return std::string("@") + std::to_string(Id);
300 }
301 
302 static std::string getNodeVisualName(const ValueInfo &VI) {
303  return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
304 }
305 
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.
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 
336 static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
337  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
338  return GVS->isReadOnly();
339  return false;
340 }
341 
343  std::vector<Edge> CrossModuleEdges;
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 }
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
void collectDefinedGVSummariesPerModule(StringMap< GVSummaryMapTy > &ModuleToDefinedGVSummaries) const
Collect for each module the list of Summaries it defines (GUID -> Summary).
Special purpose, only applies to global arrays.
Definition: GlobalValue.h:55
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:228
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:493
This class represents lattice values for constants.
Definition: AllocatorList.h:24
static std::string linkageToString(GlobalValue::LinkageTypes LT)
Same, but only replaced by something equivalent.
Definition: GlobalValue.h:54
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:250
Available for inspection, not emission.
Definition: GlobalValue.h:50
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:398
uint32_t NodeId
Definition: RDFGraph.h:261
Like Internal, but omit from symbol table.
Definition: GlobalValue.h:57
Externally visible function.
Definition: GlobalValue.h:49
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:1186
STATISTIC(NumFunctions, "Total number of functions")
F(f)
Tentative definitions.
Definition: GlobalValue.h:59
GlobalValue::GUID getGUID() const
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
static void propagateConstantsToRefs(GlobalValueSummary *S)
The access may reference the value stored in memory.
static bool canImportGlobalVar(GlobalValueSummary *S)
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
static std::string getSummaryAttributes(GlobalValueSummary *GVS)
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
void propagateConstants(const DenseSet< GlobalValue::GUID > &PreservedSymbols)
Analyze index and detect unmodified globals.
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:58
#define P(N)
Same, but only replaced by something equivalent.
Definition: GlobalValue.h:52
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
unsigned immutableRefCount() const
StringRef name() const
bool isGUIDLive(GlobalValue::GUID GUID) const
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
Keep one copy of function when linking (inline)
Definition: GlobalValue.h:51
std::string utostr(uint64_t X, bool isNeg=false)
Definition: StringExtras.h:224
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:220
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:48
StringRef filename(StringRef path, Style style=Style::native)
Get filename.
Definition: Path.cpp:590
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:53
Rename collisions when linking (static functions).
Definition: GlobalValue.h:56
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:92
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:18
static std::string getNodeVisualName(GlobalValue::GUID Id)
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:62
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:73
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
bool AreStatisticsEnabled()
Check if statistics are enabled.
Definition: Statistic.cpp:134
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:43
static FunctionSummary ExternalNode
A dummy node to reference external functions that aren&#39;t in the index.