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