lib/IR/ModuleSummaryIndex.cpp

   1 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the module index and summary classes for the
  11 // IR library.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/IR/ModuleSummaryIndex.h"
  16 #include "llvm/ADT/SCCIterator.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 FunctionSummary FunctionSummary::ExternalNode =
  23     FunctionSummary::makeDummyFunctionSummary({});
  24 bool ValueInfo::isDSOLocal() const {
  25   // Need to check all summaries are local in case of hash collisions.
  26   return getSummaryList().size() &&
  27          llvm::all_of(getSummaryList(),
  28                       [](const std::unique_ptr<GlobalValueSummary> &Summary) {
  29                         return Summary->isDSOLocal();
  30                       });
  31 }
  32
  33 // Collect for the given module the list of function it defines
  34 // (GUID -> Summary).
  35 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
  36     StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
  37   for (auto &GlobalList : *this) {
  38     auto GUID = GlobalList.first;
  39     for (auto &GlobSummary : GlobalList.second.SummaryList) {
  40       auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
  41       if (!Summary)
  42         // Ignore global variable, focus on functions
  43         continue;
  44       // Ignore summaries from other modules.
  45       if (Summary->modulePath() != ModulePath)
  46         continue;
  47       GVSummaryMap[GUID] = Summary;
  48     }
  49   }
  50 }
  51
  52 // Collect for each module the list of function it defines (GUID -> Summary).
  53 void ModuleSummaryIndex::collectDefinedGVSummariesPerModule(
  54     StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const {
  55   for (auto &GlobalList : *this) {
  56     auto GUID = GlobalList.first;
  57     for (auto &Summary : GlobalList.second.SummaryList) {
  58       ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
  59     }
  60   }
  61 }
  62
  63 GlobalValueSummary *
  64 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
  65                                           bool PerModuleIndex) const {
  66   auto VI = getValueInfo(ValueGUID);
  67   assert(VI && "GlobalValue not found in index");
  68   assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
  69          "Expected a single entry per global value in per-module index");
  70   auto &Summary = VI.getSummaryList()[0];
  71   return Summary.get();
  72 }
  73
  74 bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
  75   auto VI = getValueInfo(GUID);
  76   if (!VI)
  77     return true;
  78   const auto &SummaryList = VI.getSummaryList();
  79   if (SummaryList.empty())
  80     return true;
  81   for (auto &I : SummaryList)
  82     if (isGlobalValueLive(I.get()))
  83       return true;
  84   return false;
  85 }
  86
  87 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
  88 // then delete this function and update its tests
  89 LLVM_DUMP_METHOD
  90 void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
  91   for (scc_iterator<ModuleSummaryIndex *> I =
  92            scc_begin<ModuleSummaryIndex *>(this);
  93        !I.isAtEnd(); ++I) {
  94     O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
  95       << ") {\n";
  96     for (const ValueInfo V : *I) {
  97       FunctionSummary *F = nullptr;
  98       if (V.getSummaryList().size())
  99         F = cast<FunctionSummary>(V.getSummaryList().front().get());
 100       O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
 101         << (I.hasLoop() ? " (has loop)" : "") << "\n";
 102     }
 103     O << "}\n";
 104   }
 105 }
 106
 107 namespace {
 108 struct Attributes {
 109   void add(const Twine &Name, const Twine &Value,
 110            const Twine &Comment = Twine());
 111   std::string getAsString() const;
 112
 113   std::vector<std::string> Attrs;
 114   std::string Comments;
 115 };
 116
 117 struct Edge {
 118   uint64_t SrcMod;
 119   int Hotness;
 120   GlobalValue::GUID Src;
 121   GlobalValue::GUID Dst;
 122 };
 123 }
 124
 125 void Attributes::add(const Twine &Name, const Twine &Value,
 126                      const Twine &Comment) {
 127   std::string A = Name.str();
 128   A += "=\"";
 129   A += Value.str();
 130   A += "\"";
 131   Attrs.push_back(A);
 132   if (!Comment.isTriviallyEmpty()) {
 133     if (Comments.empty())
 134       Comments = " // ";
 135     else
 136       Comments += ", ";
 137     Comments += Comment.str();
 138   }
 139 }
 140
 141 std::string Attributes::getAsString() const {
 142   if (Attrs.empty())
 143     return "";
 144
 145   std::string Ret = "[";
 146   for (auto &A : Attrs)
 147     Ret += A + ",";
 148   Ret.pop_back();
 149   Ret += "];";
 150   Ret += Comments;
 151   return Ret;
 152 }
 153
 154 static std::string linkageToString(GlobalValue::LinkageTypes LT) {
 155   switch (LT) {
 156   case GlobalValue::ExternalLinkage:
 157     return "extern";
 158   case GlobalValue::AvailableExternallyLinkage:
 159     return "av_ext";
 160   case GlobalValue::LinkOnceAnyLinkage:
 161     return "linkonce";
 162   case GlobalValue::LinkOnceODRLinkage:
 163     return "linkonce_odr";
 164   case GlobalValue::WeakAnyLinkage:
 165     return "weak";
 166   case GlobalValue::WeakODRLinkage:
 167     return "weak_odr";
 168   case GlobalValue::AppendingLinkage:
 169     return "appending";
 170   case GlobalValue::InternalLinkage:
 171     return "internal";
 172   case GlobalValue::PrivateLinkage:
 173     return "private";
 174   case GlobalValue::ExternalWeakLinkage:
 175     return "extern_weak";
 176   case GlobalValue::CommonLinkage:
 177     return "common";
 178   }
 179
 180   return "<unknown>";
 181 }
 182
 183 static std::string fflagsToString(FunctionSummary::FFlags F) {
 184   auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
 185   char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
 186                     FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias), 0};
 187
 188   return FlagRep;
 189 }
 190
 191 // Get string representation of function instruction count and flags.
 192 static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
 193   auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
 194   if (!FS)
 195     return "";
 196
 197   return std::string("inst: ") + std::to_string(FS->instCount()) +
 198          ", ffl: " + fflagsToString(FS->fflags());
 199 }
 200
 201 static std::string getNodeVisualName(const ValueInfo &VI) {
 202   return VI.name().empty() ? std::string("@") + std::to_string(VI.getGUID())
 203                            : VI.name().str();
 204 }
 205
 206 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
 207   if (isa<AliasSummary>(GVS))
 208     return getNodeVisualName(VI);
 209
 210   std::string Attrs = getSummaryAttributes(GVS);
 211   std::string Label =
 212       getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
 213   if (!Attrs.empty())
 214     Label += std::string(" (") + Attrs + ")";
 215   Label += "}";
 216
 217   return Label;
 218 }
 219
 220 // Write definition of external node, which doesn't have any
 221 // specific module associated with it. Typically this is function
 222 // or variable defined in native object or library.
 223 static void defineExternalNode(raw_ostream &OS, const char *Pfx,
 224                                const ValueInfo &VI) {
 225   auto StrId = std::to_string(VI.getGUID());
 226   OS << "  " << StrId << " [label=\"" << getNodeVisualName(VI)
 227      << "\"]; // defined externally\n";
 228 }
 229
 230 void ModuleSummaryIndex::exportToDot(raw_ostream& OS) const {
 231   std::vector<Edge> CrossModuleEdges;
 232   DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
 233   StringMap<GVSummaryMapTy> ModuleToDefinedGVS;
 234   collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
 235
 236   // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
 237   // because we may have multiple linkonce functions summaries.
 238   auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
 239     return ModId == (uint64_t)-1 ? std::to_string(Id)
 240                                  : std::string("M") + std::to_string(ModId) +
 241                                        "_" + std::to_string(Id);
 242   };
 243
 244   auto DrawEdge = [&](const char *Pfx, int SrcMod, GlobalValue::GUID SrcId,
 245                       int DstMod, GlobalValue::GUID DstId, int TypeOrHotness) {
 246     // 0 corresponds to alias edge, 1 to ref edge, 2 to call with unknown
 247     // hotness, ...
 248     TypeOrHotness += 2;
 249     static const char *EdgeAttrs[] = {
 250         " [style=dotted]; // alias",
 251         " [style=dashed]; // ref",
 252         " // call (hotness : Unknown)",
 253         " [color=blue]; // call (hotness : Cold)",
 254         " // call (hotness : None)",
 255         " [color=brown]; // call (hotness : Hot)",
 256         " [style=bold,color=red]; // call (hotness : Critical)"};
 257
 258     assert(static_cast<size_t>(TypeOrHotness) <
 259            sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
 260     OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
 261        << EdgeAttrs[TypeOrHotness] << "\n";
 262   };
 263
 264   OS << "digraph Summary {\n";
 265   for (auto &ModIt : ModuleToDefinedGVS) {
 266     auto ModId = getModuleId(ModIt.first());
 267     OS << "  // Module: " << ModIt.first() << "\n";
 268     OS << "  subgraph cluster_" << std::to_string(ModId) << " {\n";
 269     OS << "    style = filled;\n";
 270     OS << "    color = lightgrey;\n";
 271     OS << "    label = \"" << sys::path::filename(ModIt.first()) << "\";\n";
 272     OS << "    node [style=filled,fillcolor=lightblue];\n";
 273
 274     auto &GVSMap = ModIt.second;
 275     auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
 276       if (!GVSMap.count(IdTo)) {
 277         CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
 278         return;
 279       }
 280       DrawEdge("    ", ModId, IdFrom, ModId, IdTo, Hotness);
 281     };
 282
 283     for (auto &SummaryIt : GVSMap) {
 284       NodeMap[SummaryIt.first].push_back(ModId);
 285       auto Flags = SummaryIt.second->flags();
 286       Attributes A;
 287       if (isa<FunctionSummary>(SummaryIt.second)) {
 288         A.add("shape", "record", "function");
 289       } else if (isa<AliasSummary>(SummaryIt.second)) {
 290         A.add("style", "dotted,filled", "alias");
 291         A.add("shape", "box");
 292       } else {
 293         A.add("shape", "Mrecord", "variable");
 294       }
 295
 296       auto VI = getValueInfo(SummaryIt.first);
 297       A.add("label", getNodeLabel(VI, SummaryIt.second));
 298       if (!Flags.Live)
 299         A.add("fillcolor", "red", "dead");
 300       else if (Flags.NotEligibleToImport)
 301         A.add("fillcolor", "yellow", "not eligible to import");
 302
 303       OS << "    " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
 304          << "\n";
 305     }
 306     OS << "    // Edges:\n";
 307
 308     for (auto &SummaryIt : GVSMap) {
 309       auto *GVS = SummaryIt.second;
 310       for (auto &R : GVS->refs())
 311         Draw(SummaryIt.first, R.getGUID(), -1);
 312
 313       if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
 314         auto AliaseeOrigId = AS->getAliasee().getOriginalName();
 315         auto AliaseeId = getGUIDFromOriginalID(AliaseeOrigId);
 316
 317         Draw(SummaryIt.first, AliaseeId ? AliaseeId : AliaseeOrigId, -2);
 318         continue;
 319       }
 320
 321       if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
 322         for (auto &CGEdge : FS->calls())
 323           Draw(SummaryIt.first, CGEdge.first.getGUID(),
 324                static_cast<int>(CGEdge.second.Hotness));
 325     }
 326     OS << "  }\n";
 327   }
 328
 329   OS << "  // Cross-module edges:\n";
 330   for (auto &E : CrossModuleEdges) {
 331     auto &ModList = NodeMap[E.Dst];
 332     if (ModList.empty()) {
 333       defineExternalNode(OS, "  ", getValueInfo(E.Dst));
 334       // Add fake module to the list to draw an edge to an external node
 335       // in the loop below.
 336       ModList.push_back(-1);
 337     }
 338     for (auto DstMod : ModList)
 339       // The edge representing call or ref is drawn to every module where target
 340       // symbol is defined. When target is a linkonce symbol there can be
 341       // multiple edges representing a single call or ref, both intra-module and
 342       // cross-module. As we've already drawn all intra-module edges before we
 343       // skip it here.
 344       if (DstMod != E.SrcMod)
 345         DrawEdge("  ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
 346   }
 347
 348   OS << "}";
 349 }