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