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