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