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