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/Support/CommandLine.h"
18#include "llvm/Support/Path.h"
19#include "llvm/Support/raw_ostream.h"
20using namespace llvm;
21
22#define DEBUG_TYPE "module-summary-index"
23
24STATISTIC(ReadOnlyLiveGVars,
25          "Number of live global variables marked read only");
26STATISTIC(WriteOnlyLiveGVars,
27          "Number of live global variables marked write only");
28
29static cl::opt<bool> PropagateAttrs("propagate-attrs", cl::init(true),
30                                    cl::Hidden,
31                                    cl::desc("Propagate attributes in index"));
32
33static cl::opt<bool> ImportConstantsWithRefs(
34    "import-constants-with-refs", cl::init(true), cl::Hidden,
35    cl::desc("Import constant global variables with references"));
36
37constexpr uint32_t FunctionSummary::ParamAccess::RangeWidth;
38
39FunctionSummary FunctionSummary::ExternalNode =
40    FunctionSummary::makeDummyFunctionSummary({});
41
42GlobalValue::VisibilityTypes ValueInfo::getELFVisibility() const {
43  bool HasProtected = false;
44  for (const auto &S : make_pointee_range(getSummaryList())) {
45    if (S.getVisibility() == GlobalValue::HiddenVisibility)
46      return GlobalValue::HiddenVisibility;
47    if (S.getVisibility() == GlobalValue::ProtectedVisibility)
48      HasProtected = true;
49  }
50  return HasProtected ? GlobalValue::ProtectedVisibility
51                      : GlobalValue::DefaultVisibility;
52}
53
54bool ValueInfo::isDSOLocal(bool WithDSOLocalPropagation) const {
55  // With DSOLocal propagation done, the flag in evey summary is the same.
56  // Check the first one is enough.
57  return WithDSOLocalPropagation
58             ? getSummaryList().size() && getSummaryList()[0]->isDSOLocal()
59             : getSummaryList().size() &&
60                   llvm::all_of(
61                       getSummaryList(),
62                       [](const std::unique_ptr<GlobalValueSummary> &Summary) {
63                         return Summary->isDSOLocal();
64                       });
65}
66
67bool ValueInfo::canAutoHide() const {
68  // Can only auto hide if all copies are eligible to auto hide.
69  return getSummaryList().size() &&
70         llvm::all_of(getSummaryList(),
71                      [](const std::unique_ptr<GlobalValueSummary> &Summary) {
72                        return Summary->canAutoHide();
73                      });
74}
75
76// Gets the number of readonly and writeonly refs in RefEdgeList
77std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const {
78  // Here we take advantage of having all readonly and writeonly references
79  // located in the end of the RefEdgeList.
80  auto Refs = refs();
81  unsigned RORefCnt = 0, WORefCnt = 0;
82  int I;
83  for (I = Refs.size() - 1; I >= 0 && Refs[I].isWriteOnly(); --I)
84    WORefCnt++;
85  for (; I >= 0 && Refs[I].isReadOnly(); --I)
86    RORefCnt++;
87  return {RORefCnt, WORefCnt};
88}
89
90constexpr uint64_t ModuleSummaryIndex::BitcodeSummaryVersion;
91
92uint64_t ModuleSummaryIndex::getFlags() const {
93  uint64_t Flags = 0;
94  if (withGlobalValueDeadStripping())
95    Flags |= 0x1;
96  if (skipModuleByDistributedBackend())
97    Flags |= 0x2;
98  if (hasSyntheticEntryCounts())
99    Flags |= 0x4;
100  if (enableSplitLTOUnit())
101    Flags |= 0x8;
102  if (partiallySplitLTOUnits())
103    Flags |= 0x10;
104  if (withAttributePropagation())
105    Flags |= 0x20;
106  if (withDSOLocalPropagation())
107    Flags |= 0x40;
108  if (withWholeProgramVisibility())
109    Flags |= 0x80;
110  if (withSupportsHotColdNew())
111    Flags |= 0x100;
112  if (hasUnifiedLTO())
113    Flags |= 0x200;
114  return Flags;
115}
116
117void ModuleSummaryIndex::setFlags(uint64_t Flags) {
118  assert(Flags <= 0x2ff && "Unexpected bits in flag");
119  // 1 bit: WithGlobalValueDeadStripping flag.
120  // Set on combined index only.
121  if (Flags & 0x1)
122    setWithGlobalValueDeadStripping();
123  // 1 bit: SkipModuleByDistributedBackend flag.
124  // Set on combined index only.
125  if (Flags & 0x2)
126    setSkipModuleByDistributedBackend();
127  // 1 bit: HasSyntheticEntryCounts flag.
128  // Set on combined index only.
129  if (Flags & 0x4)
130    setHasSyntheticEntryCounts();
131  // 1 bit: DisableSplitLTOUnit flag.
132  // Set on per module indexes. It is up to the client to validate
133  // the consistency of this flag across modules being linked.
134  if (Flags & 0x8)
135    setEnableSplitLTOUnit();
136  // 1 bit: PartiallySplitLTOUnits flag.
137  // Set on combined index only.
138  if (Flags & 0x10)
139    setPartiallySplitLTOUnits();
140  // 1 bit: WithAttributePropagation flag.
141  // Set on combined index only.
142  if (Flags & 0x20)
143    setWithAttributePropagation();
144  // 1 bit: WithDSOLocalPropagation flag.
145  // Set on combined index only.
146  if (Flags & 0x40)
147    setWithDSOLocalPropagation();
148  // 1 bit: WithWholeProgramVisibility flag.
149  // Set on combined index only.
150  if (Flags & 0x80)
151    setWithWholeProgramVisibility();
152  // 1 bit: WithSupportsHotColdNew flag.
153  // Set on combined index only.
154  if (Flags & 0x100)
155    setWithSupportsHotColdNew();
156  // 1 bit: WithUnifiedLTO flag.
157  // Set on combined index only.
158  if (Flags & 0x200)
159    setUnifiedLTO();
160}
161
162// Collect for the given module the list of function it defines
163// (GUID -> Summary).
164void ModuleSummaryIndex::collectDefinedFunctionsForModule(
165    StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
166  for (auto &GlobalList : *this) {
167    auto GUID = GlobalList.first;
168    for (auto &GlobSummary : GlobalList.second.SummaryList) {
169      auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
170      if (!Summary)
171        // Ignore global variable, focus on functions
172        continue;
173      // Ignore summaries from other modules.
174      if (Summary->modulePath() != ModulePath)
175        continue;
176      GVSummaryMap[GUID] = Summary;
177    }
178  }
179}
180
181GlobalValueSummary *
182ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
183                                          bool PerModuleIndex) const {
184  auto VI = getValueInfo(ValueGUID);
185  assert(VI && "GlobalValue not found in index");
186  assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
187         "Expected a single entry per global value in per-module index");
188  auto &Summary = VI.getSummaryList()[0];
189  return Summary.get();
190}
191
192bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
193  auto VI = getValueInfo(GUID);
194  if (!VI)
195    return true;
196  const auto &SummaryList = VI.getSummaryList();
197  if (SummaryList.empty())
198    return true;
199  for (auto &I : SummaryList)
200    if (isGlobalValueLive(I.get()))
201      return true;
202  return false;
203}
204
205static void
206propagateAttributesToRefs(GlobalValueSummary *S,
207                          DenseSet<ValueInfo> &MarkedNonReadWriteOnly) {
208  // If reference is not readonly or writeonly then referenced summary is not
209  // read/writeonly either. Note that:
210  // - All references from GlobalVarSummary are conservatively considered as
211  //   not readonly or writeonly. Tracking them properly requires more complex
212  //   analysis then we have now.
213  //
214  // - AliasSummary objects have no refs at all so this function is a no-op
215  //   for them.
216  for (auto &VI : S->refs()) {
217    assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
218    if (!VI.getAccessSpecifier()) {
219      if (!MarkedNonReadWriteOnly.insert(VI).second)
220        continue;
221    } else if (MarkedNonReadWriteOnly.contains(VI))
222      continue;
223    for (auto &Ref : VI.getSummaryList())
224      // If references to alias is not read/writeonly then aliasee
225      // is not read/writeonly
226      if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
227        if (!VI.isReadOnly())
228          GVS->setReadOnly(false);
229        if (!VI.isWriteOnly())
230          GVS->setWriteOnly(false);
231      }
232  }
233}
234
235// Do the access attribute and DSOLocal propagation in combined index.
236// The goal of attribute propagation is internalization of readonly (RO)
237// or writeonly (WO) variables. To determine which variables are RO or WO
238// and which are not we take following steps:
239// - During analysis we speculatively assign readonly and writeonly
240//   attribute to all variables which can be internalized. When computing
241//   function summary we also assign readonly or writeonly attribute to a
242//   reference if function doesn't modify referenced variable (readonly)
243//   or doesn't read it (writeonly).
244//
245// - After computing dead symbols in combined index we do the attribute
246//   and DSOLocal propagation. During this step we:
247//   a. clear RO and WO attributes from variables which are preserved or
248//      can't be imported
249//   b. clear RO and WO attributes from variables referenced by any global
250//      variable initializer
251//   c. clear RO attribute from variable referenced by a function when
252//      reference is not readonly
253//   d. clear WO attribute from variable referenced by a function when
254//      reference is not writeonly
255//   e. clear IsDSOLocal flag in every summary if any of them is false.
256//
257//   Because of (c, d) we don't internalize variables read by function A
258//   and modified by function B.
259//
260// Internalization itself happens in the backend after import is finished
261// See internalizeGVsAfterImport.
262void ModuleSummaryIndex::propagateAttributes(
263    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
264  if (!PropagateAttrs)
265    return;
266  DenseSet<ValueInfo> MarkedNonReadWriteOnly;
267  for (auto &P : *this) {
268    bool IsDSOLocal = true;
269    for (auto &S : P.second.SummaryList) {
270      if (!isGlobalValueLive(S.get())) {
271        // computeDeadSymbolsAndUpdateIndirectCalls should have marked all
272        // copies live. Note that it is possible that there is a GUID collision
273        // between internal symbols with the same name in different files of the
274        // same name but not enough distinguishing path. Because
275        // computeDeadSymbolsAndUpdateIndirectCalls should conservatively mark
276        // all copies live we can assert here that all are dead if any copy is
277        // dead.
278        assert(llvm::none_of(
279            P.second.SummaryList,
280            [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
281              return isGlobalValueLive(Summary.get());
282            }));
283        // We don't examine references from dead objects
284        break;
285      }
286
287      // Global variable can't be marked read/writeonly if it is not eligible
288      // to import since we need to ensure that all external references get
289      // a local (imported) copy. It also can't be marked read/writeonly if
290      // it or any alias (since alias points to the same memory) are preserved
291      // or notEligibleToImport, since either of those means there could be
292      // writes (or reads in case of writeonly) that are not visible (because
293      // preserved means it could have external to DSO writes or reads, and
294      // notEligibleToImport means it could have writes or reads via inline
295      // assembly leading it to be in the @llvm.*used).
296      if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
297        // Here we intentionally pass S.get() not GVS, because S could be
298        // an alias. We don't analyze references here, because we have to
299        // know exactly if GV is readonly to do so.
300        if (!canImportGlobalVar(S.get(), /* AnalyzeRefs */ false) ||
301            GUIDPreservedSymbols.count(P.first)) {
302          GVS->setReadOnly(false);
303          GVS->setWriteOnly(false);
304        }
305      propagateAttributesToRefs(S.get(), MarkedNonReadWriteOnly);
306
307      // If the flag from any summary is false, the GV is not DSOLocal.
308      IsDSOLocal &= S->isDSOLocal();
309    }
310    if (!IsDSOLocal)
311      // Mark the flag in all summaries false so that we can do quick check
312      // without going through the whole list.
313      for (const std::unique_ptr<GlobalValueSummary> &Summary :
314           P.second.SummaryList)
315        Summary->setDSOLocal(false);
316  }
317  setWithAttributePropagation();
318  setWithDSOLocalPropagation();
319  if (llvm::AreStatisticsEnabled())
320    for (auto &P : *this)
321      if (P.second.SummaryList.size())
322        if (auto *GVS = dyn_cast<GlobalVarSummary>(
323                P.second.SummaryList[0]->getBaseObject()))
324          if (isGlobalValueLive(GVS)) {
325            if (GVS->maybeReadOnly())
326              ReadOnlyLiveGVars++;
327            if (GVS->maybeWriteOnly())
328              WriteOnlyLiveGVars++;
329          }
330}
331
332bool ModuleSummaryIndex::canImportGlobalVar(const GlobalValueSummary *S,
333                                            bool AnalyzeRefs) const {
334  auto HasRefsPreventingImport = [this](const GlobalVarSummary *GVS) {
335    // We don't analyze GV references during attribute propagation, so
336    // GV with non-trivial initializer can be marked either read or
337    // write-only.
338    // Importing definiton of readonly GV with non-trivial initializer
339    // allows us doing some extra optimizations (like converting indirect
340    // calls to direct).
341    // Definition of writeonly GV with non-trivial initializer should also
342    // be imported. Not doing so will result in:
343    // a) GV internalization in source module (because it's writeonly)
344    // b) Importing of GV declaration to destination module as a result
345    //    of promotion.
346    // c) Link error (external declaration with internal definition).
347    // However we do not promote objects referenced by writeonly GV
348    // initializer by means of converting it to 'zeroinitializer'
349    return !(ImportConstantsWithRefs && GVS->isConstant()) &&
350           !isReadOnly(GVS) && !isWriteOnly(GVS) && GVS->refs().size();
351  };
352  auto *GVS = cast<GlobalVarSummary>(S->getBaseObject());
353
354  // Global variable with non-trivial initializer can be imported
355  // if it's readonly. This gives us extra opportunities for constant
356  // folding and converting indirect calls to direct calls. We don't
357  // analyze GV references during attribute propagation, because we
358  // don't know yet if it is readonly or not.
359  return !GlobalValue::isInterposableLinkage(S->linkage()) &&
360         !S->notEligibleToImport() &&
361         (!AnalyzeRefs || !HasRefsPreventingImport(GVS));
362}
363
364// TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
365// then delete this function and update its tests
366LLVM_DUMP_METHOD
367void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
368  for (scc_iterator<ModuleSummaryIndex *> I =
369           scc_begin<ModuleSummaryIndex *>(this);
370       !I.isAtEnd(); ++I) {
371    O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
372      << ") {\n";
373    for (const ValueInfo &V : *I) {
374      FunctionSummary *F = nullptr;
375      if (V.getSummaryList().size())
376        F = cast<FunctionSummary>(V.getSummaryList().front().get());
377      O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
378        << (I.hasCycle() ? " (has cycle)" : "") << "\n";
379    }
380    O << "}\n";
381  }
382}
383
384namespace {
385struct Attributes {
386  void add(const Twine &Name, const Twine &Value,
387           const Twine &Comment = Twine());
388  void addComment(const Twine &Comment);
389  std::string getAsString() const;
390
391  std::vector<std::string> Attrs;
392  std::string Comments;
393};
394
395struct Edge {
396  uint64_t SrcMod;
397  int Hotness;
398  GlobalValue::GUID Src;
399  GlobalValue::GUID Dst;
400};
401}
402
403void Attributes::add(const Twine &Name, const Twine &Value,
404                     const Twine &Comment) {
405  std::string A = Name.str();
406  A += "=\"";
407  A += Value.str();
408  A += "\"";
409  Attrs.push_back(A);
410  addComment(Comment);
411}
412
413void Attributes::addComment(const Twine &Comment) {
414  if (!Comment.isTriviallyEmpty()) {
415    if (Comments.empty())
416      Comments = " // ";
417    else
418      Comments += ", ";
419    Comments += Comment.str();
420  }
421}
422
423std::string Attributes::getAsString() const {
424  if (Attrs.empty())
425    return "";
426
427  std::string Ret = "[";
428  for (auto &A : Attrs)
429    Ret += A + ",";
430  Ret.pop_back();
431  Ret += "];";
432  Ret += Comments;
433  return Ret;
434}
435
436static std::string linkageToString(GlobalValue::LinkageTypes LT) {
437  switch (LT) {
438  case GlobalValue::ExternalLinkage:
439    return "extern";
440  case GlobalValue::AvailableExternallyLinkage:
441    return "av_ext";
442  case GlobalValue::LinkOnceAnyLinkage:
443    return "linkonce";
444  case GlobalValue::LinkOnceODRLinkage:
445    return "linkonce_odr";
446  case GlobalValue::WeakAnyLinkage:
447    return "weak";
448  case GlobalValue::WeakODRLinkage:
449    return "weak_odr";
450  case GlobalValue::AppendingLinkage:
451    return "appending";
452  case GlobalValue::InternalLinkage:
453    return "internal";
454  case GlobalValue::PrivateLinkage:
455    return "private";
456  case GlobalValue::ExternalWeakLinkage:
457    return "extern_weak";
458  case GlobalValue::CommonLinkage:
459    return "common";
460  }
461
462  return "<unknown>";
463}
464
465static std::string fflagsToString(FunctionSummary::FFlags F) {
466  auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
467  char FlagRep[] = {FlagValue(F.ReadNone),
468                    FlagValue(F.ReadOnly),
469                    FlagValue(F.NoRecurse),
470                    FlagValue(F.ReturnDoesNotAlias),
471                    FlagValue(F.NoInline),
472                    FlagValue(F.AlwaysInline),
473                    FlagValue(F.NoUnwind),
474                    FlagValue(F.MayThrow),
475                    FlagValue(F.HasUnknownCall),
476                    FlagValue(F.MustBeUnreachable),
477                    0};
478
479  return FlagRep;
480}
481
482// Get string representation of function instruction count and flags.
483static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
484  auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
485  if (!FS)
486    return "";
487
488  return std::string("inst: ") + std::to_string(FS->instCount()) +
489         ", ffl: " + fflagsToString(FS->fflags());
490}
491
492static std::string getNodeVisualName(GlobalValue::GUID Id) {
493  return std::string("@") + std::to_string(Id);
494}
495
496static std::string getNodeVisualName(const ValueInfo &VI) {
497  return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
498}
499
500static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
501  if (isa<AliasSummary>(GVS))
502    return getNodeVisualName(VI);
503
504  std::string Attrs = getSummaryAttributes(GVS);
505  std::string Label =
506      getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
507  if (!Attrs.empty())
508    Label += std::string(" (") + Attrs + ")";
509  Label += "}";
510
511  return Label;
512}
513
514// Write definition of external node, which doesn't have any
515// specific module associated with it. Typically this is function
516// or variable defined in native object or library.
517static void defineExternalNode(raw_ostream &OS, const char *Pfx,
518                               const ValueInfo &VI, GlobalValue::GUID Id) {
519  auto StrId = std::to_string(Id);
520  OS << "  " << StrId << " [label=\"";
521
522  if (VI) {
523    OS << getNodeVisualName(VI);
524  } else {
525    OS << getNodeVisualName(Id);
526  }
527  OS << "\"]; // defined externally\n";
528}
529
530static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
531  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
532    return GVS->maybeReadOnly();
533  return false;
534}
535
536static bool hasWriteOnlyFlag(const GlobalValueSummary *S) {
537  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
538    return GVS->maybeWriteOnly();
539  return false;
540}
541
542static bool hasConstantFlag(const GlobalValueSummary *S) {
543  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
544    return GVS->isConstant();
545  return false;
546}
547
548void ModuleSummaryIndex::exportToDot(
549    raw_ostream &OS,
550    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const {
551  std::vector<Edge> CrossModuleEdges;
552  DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
553  using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
554  std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS;
555  collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
556
557  // Assign an id to each module path for use in graph labels. Since the
558  // StringMap iteration order isn't guaranteed, order by path string before
559  // assigning ids.
560  std::vector<StringRef> ModulePaths;
561  for (auto &[ModPath, _] : modulePaths())
562    ModulePaths.push_back(ModPath);
563  llvm::sort(ModulePaths);
564  DenseMap<StringRef, uint64_t> ModuleIdMap;
565  for (auto &ModPath : ModulePaths)
566    ModuleIdMap.try_emplace(ModPath, ModuleIdMap.size());
567
568  // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
569  // because we may have multiple linkonce functions summaries.
570  auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
571    return ModId == (uint64_t)-1 ? std::to_string(Id)
572                                 : std::string("M") + std::to_string(ModId) +
573                                       "_" + std::to_string(Id);
574  };
575
576  auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
577                      uint64_t DstMod, GlobalValue::GUID DstId,
578                      int TypeOrHotness) {
579    // 0 - alias
580    // 1 - reference
581    // 2 - constant reference
582    // 3 - writeonly reference
583    // Other value: (hotness - 4).
584    TypeOrHotness += 4;
585    static const char *EdgeAttrs[] = {
586        " [style=dotted]; // alias",
587        " [style=dashed]; // ref",
588        " [style=dashed,color=forestgreen]; // const-ref",
589        " [style=dashed,color=violetred]; // writeOnly-ref",
590        " // call (hotness : Unknown)",
591        " [color=blue]; // call (hotness : Cold)",
592        " // call (hotness : None)",
593        " [color=brown]; // call (hotness : Hot)",
594        " [style=bold,color=red]; // call (hotness : Critical)"};
595
596    assert(static_cast<size_t>(TypeOrHotness) < std::size(EdgeAttrs));
597    OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
598       << EdgeAttrs[TypeOrHotness] << "\n";
599  };
600
601  OS << "digraph Summary {\n";
602  for (auto &ModIt : ModuleToDefinedGVS) {
603    // Will be empty for a just built per-module index, which doesn't setup a
604    // module paths table. In that case use 0 as the module id.
605    assert(ModuleIdMap.count(ModIt.first) || ModuleIdMap.empty());
606    auto ModId = ModuleIdMap.empty() ? 0 : ModuleIdMap[ModIt.first];
607    OS << "  // Module: " << ModIt.first << "\n";
608    OS << "  subgraph cluster_" << std::to_string(ModId) << " {\n";
609    OS << "    style = filled;\n";
610    OS << "    color = lightgrey;\n";
611    OS << "    label = \"" << sys::path::filename(ModIt.first) << "\";\n";
612    OS << "    node [style=filled,fillcolor=lightblue];\n";
613
614    auto &GVSMap = ModIt.second;
615    auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
616      if (!GVSMap.count(IdTo)) {
617        CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
618        return;
619      }
620      DrawEdge("    ", ModId, IdFrom, ModId, IdTo, Hotness);
621    };
622
623    for (auto &SummaryIt : GVSMap) {
624      NodeMap[SummaryIt.first].push_back(ModId);
625      auto Flags = SummaryIt.second->flags();
626      Attributes A;
627      if (isa<FunctionSummary>(SummaryIt.second)) {
628        A.add("shape", "record", "function");
629      } else if (isa<AliasSummary>(SummaryIt.second)) {
630        A.add("style", "dotted,filled", "alias");
631        A.add("shape", "box");
632      } else {
633        A.add("shape", "Mrecord", "variable");
634        if (Flags.Live && hasReadOnlyFlag(SummaryIt.second))
635          A.addComment("immutable");
636        if (Flags.Live && hasWriteOnlyFlag(SummaryIt.second))
637          A.addComment("writeOnly");
638        if (Flags.Live && hasConstantFlag(SummaryIt.second))
639          A.addComment("constant");
640      }
641      if (Flags.Visibility)
642        A.addComment("visibility");
643      if (Flags.DSOLocal)
644        A.addComment("dsoLocal");
645      if (Flags.CanAutoHide)
646        A.addComment("canAutoHide");
647      if (GUIDPreservedSymbols.count(SummaryIt.first))
648        A.addComment("preserved");
649
650      auto VI = getValueInfo(SummaryIt.first);
651      A.add("label", getNodeLabel(VI, SummaryIt.second));
652      if (!Flags.Live)
653        A.add("fillcolor", "red", "dead");
654      else if (Flags.NotEligibleToImport)
655        A.add("fillcolor", "yellow", "not eligible to import");
656
657      OS << "    " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
658         << "\n";
659    }
660    OS << "    // Edges:\n";
661
662    for (auto &SummaryIt : GVSMap) {
663      auto *GVS = SummaryIt.second;
664      for (auto &R : GVS->refs())
665        Draw(SummaryIt.first, R.getGUID(),
666             R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3));
667
668      if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
669        Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
670        continue;
671      }
672
673      if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
674        for (auto &CGEdge : FS->calls())
675          Draw(SummaryIt.first, CGEdge.first.getGUID(),
676               static_cast<int>(CGEdge.second.Hotness));
677    }
678    OS << "  }\n";
679  }
680
681  OS << "  // Cross-module edges:\n";
682  for (auto &E : CrossModuleEdges) {
683    auto &ModList = NodeMap[E.Dst];
684    if (ModList.empty()) {
685      defineExternalNode(OS, "  ", getValueInfo(E.Dst), E.Dst);
686      // Add fake module to the list to draw an edge to an external node
687      // in the loop below.
688      ModList.push_back(-1);
689    }
690    for (auto DstMod : ModList)
691      // The edge representing call or ref is drawn to every module where target
692      // symbol is defined. When target is a linkonce symbol there can be
693      // multiple edges representing a single call or ref, both intra-module and
694      // cross-module. As we've already drawn all intra-module edges before we
695      // skip it here.
696      if (DstMod != E.SrcMod)
697        DrawEdge("  ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
698  }
699
700  OS << "}";
701}
702