llvm/lib/IR/ModuleSummaryIndex.cpp

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