LCOV - code coverage report
Current view: top level - lib/IR - ModuleSummaryIndex.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 160 163 98.2 %
Date: 2018-06-17 00:07:59 Functions: 21 21 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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      202338 : FunctionSummary FunctionSummary::ExternalNode =
      23             :     FunctionSummary::makeDummyFunctionSummary({});
      24        1819 : bool ValueInfo::isDSOLocal() const {
      25             :   // Need to check all summaries are local in case of hash collisions.
      26        3540 :   return getSummaryList().size() &&
      27             :          llvm::all_of(getSummaryList(),
      28             :                       [](const std::unique_ptr<GlobalValueSummary> &Summary) {
      29             :                         return Summary->isDSOLocal();
      30        1819 :                       });
      31             : }
      32             : 
      33             : // Collect for the given module the list of function it defines
      34             : // (GUID -> Summary).
      35          18 : void ModuleSummaryIndex::collectDefinedFunctionsForModule(
      36             :     StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
      37         170 :   for (auto &GlobalList : *this) {
      38         152 :     auto GUID = GlobalList.first;
      39         152 :     for (auto &GlobSummary : GlobalList.second.SummaryList) {
      40             :       auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
      41           4 :       if (!Summary)
      42             :         // Ignore global variable, focus on functions
      43           4 :         continue;
      44             :       // Ignore summaries from other modules.
      45         128 :       if (Summary->modulePath() != ModulePath)
      46         128 :         continue;
      47          20 :       GVSummaryMap[GUID] = Summary;
      48             :     }
      49             :   }
      50          18 : }
      51             : 
      52             : // Collect for each module the list of function it defines (GUID -> Summary).
      53         325 : void ModuleSummaryIndex::collectDefinedGVSummariesPerModule(
      54             :     StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const {
      55        1564 :   for (auto &GlobalList : *this) {
      56        1239 :     auto GUID = GlobalList.first;
      57        1239 :     for (auto &Summary : GlobalList.second.SummaryList) {
      58        1273 :       ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
      59             :     }
      60             :   }
      61         325 : }
      62             : 
      63             : GlobalValueSummary *
      64         260 : ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
      65             :                                           bool PerModuleIndex) const {
      66         260 :   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         260 :   return Summary.get();
      72             : }
      73             : 
      74         375 : bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
      75         375 :   auto VI = getValueInfo(GUID);
      76         375 :   if (!VI)
      77             :     return true;
      78             :   const auto &SummaryList = VI.getSummaryList();
      79         356 :   if (SummaryList.empty())
      80             :     return true;
      81         376 :   for (auto &I : SummaryList)
      82         346 :     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           1 : void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
      91             :   for (scc_iterator<ModuleSummaryIndex *> I =
      92           1 :            scc_begin<ModuleSummaryIndex *>(this);
      93           6 :        !I.isAtEnd(); ++I) {
      94          25 :     O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
      95           5 :       << ") {\n";
      96           5 :     for (const ValueInfo V : *I) {
      97             :       FunctionSummary *F = nullptr;
      98           6 :       if (V.getSummaryList().size())
      99             :         F = cast<FunctionSummary>(V.getSummaryList().front().get());
     100          18 :       O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
     101           6 :         << (I.hasLoop() ? " (has loop)" : "") << "\n";
     102             :     }
     103           5 :     O << "}\n";
     104             :   }
     105           1 : }
     106             : 
     107             : namespace {
     108         460 : 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         547 : void Attributes::add(const Twine &Name, const Twine &Value,
     126             :                      const Twine &Comment) {
     127         547 :   std::string A = Name.str();
     128             :   A += "=\"";
     129        1094 :   A += Value.str();
     130             :   A += "\"";
     131         547 :   Attrs.push_back(A);
     132             :   if (!Comment.isTriviallyEmpty()) {
     133         304 :     if (Comments.empty())
     134         230 :       Comments = " // ";
     135             :     else
     136          74 :       Comments += ", ";
     137         608 :     Comments += Comment.str();
     138             :   }
     139         547 : }
     140             : 
     141         230 : std::string Attributes::getAsString() const {
     142         230 :   if (Attrs.empty())
     143           0 :     return "";
     144             : 
     145         230 :   std::string Ret = "[";
     146         230 :   for (auto &A : Attrs)
     147        1094 :     Ret += A + ",";
     148             :   Ret.pop_back();
     149             :   Ret += "];";
     150             :   Ret += Comments;
     151             :   return Ret;
     152             : }
     153             : 
     154         217 : static std::string linkageToString(GlobalValue::LinkageTypes LT) {
     155         217 :   switch (LT) {
     156             :   case GlobalValue::ExternalLinkage:
     157         157 :     return "extern";
     158             :   case GlobalValue::AvailableExternallyLinkage:
     159           2 :     return "av_ext";
     160             :   case GlobalValue::LinkOnceAnyLinkage:
     161           5 :     return "linkonce";
     162             :   case GlobalValue::LinkOnceODRLinkage:
     163          11 :     return "linkonce_odr";
     164             :   case GlobalValue::WeakAnyLinkage:
     165           8 :     return "weak";
     166             :   case GlobalValue::WeakODRLinkage:
     167           2 :     return "weak_odr";
     168             :   case GlobalValue::AppendingLinkage:
     169           5 :     return "appending";
     170             :   case GlobalValue::InternalLinkage:
     171          25 :     return "internal";
     172             :   case GlobalValue::PrivateLinkage:
     173           1 :     return "private";
     174             :   case GlobalValue::ExternalWeakLinkage:
     175           0 :     return "extern_weak";
     176             :   case GlobalValue::CommonLinkage:
     177           1 :     return "common";
     178             :   }
     179             : 
     180           0 :   return "<unknown>";
     181             : }
     182             : 
     183         190 : static std::string fflagsToString(FunctionSummary::FFlags F) {
     184         760 :   auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
     185         380 :   char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
     186         760 :                     FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias), 0};
     187             : 
     188         190 :   return FlagRep;
     189             : }
     190             : 
     191             : // Get string representation of function instruction count and flags.
     192         217 : static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
     193             :   auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
     194             :   if (!FS)
     195          27 :     return "";
     196             : 
     197        1140 :   return std::string("inst: ") + std::to_string(FS->instCount()) +
     198         570 :          ", ffl: " + fflagsToString(FS->fflags());
     199             : }
     200             : 
     201         243 : static std::string getNodeVisualName(const ValueInfo &VI) {
     202         974 :   return VI.name().empty() ? std::string("@") + std::to_string(VI.getGUID())
     203         731 :                            : VI.name().str();
     204             : }
     205             : 
     206         230 : static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
     207         230 :   if (isa<AliasSummary>(GVS))
     208          13 :     return getNodeVisualName(VI);
     209             : 
     210         217 :   std::string Attrs = getSummaryAttributes(GVS);
     211             :   std::string Label =
     212         868 :       getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
     213         217 :   if (!Attrs.empty())
     214         760 :     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          13 : static void defineExternalNode(raw_ostream &OS, const char *Pfx,
     224             :                                const ValueInfo &VI) {
     225             :   auto StrId = std::to_string(VI.getGUID());
     226          39 :   OS << "  " << StrId << " [label=\"" << getNodeVisualName(VI)
     227          13 :      << "\"]; // defined externally\n";
     228          13 : }
     229             : 
     230          61 : void ModuleSummaryIndex::exportToDot(raw_ostream& OS) const {
     231             :   std::vector<Edge> CrossModuleEdges;
     232             :   DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
     233          61 :   StringMap<GVSummaryMapTy> ModuleToDefinedGVS;
     234          61 :   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         572 :   auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
     239             :     return ModId == (uint64_t)-1 ? std::to_string(Id)
     240        3412 :                                  : std::string("M") + std::to_string(ModId) +
     241        1144 :                                        "_" + std::to_string(Id);
     242        1696 :   };
     243             : 
     244             :   auto DrawEdge = [&](const char *Pfx, int SrcMod, GlobalValue::GUID SrcId,
     245         171 :                       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         171 :     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         684 :     OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
     261         171 :        << EdgeAttrs[TypeOrHotness] << "\n";
     262         232 :   };
     263             : 
     264          61 :   OS << "digraph Summary {\n";
     265         232 :   for (auto &ModIt : ModuleToDefinedGVS) {
     266         110 :     auto ModId = getModuleId(ModIt.first());
     267         220 :     OS << "  // Module: " << ModIt.first() << "\n";
     268         330 :     OS << "  subgraph cluster_" << std::to_string(ModId) << " {\n";
     269         110 :     OS << "    style = filled;\n";
     270         110 :     OS << "    color = lightgrey;\n";
     271         220 :     OS << "    label = \"" << sys::path::filename(ModIt.first()) << "\";\n";
     272         110 :     OS << "    node [style=filled,fillcolor=lightblue];\n";
     273             : 
     274         110 :     auto &GVSMap = ModIt.second;
     275         171 :     auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
     276         171 :       if (!GVSMap.count(IdTo)) {
     277         253 :         CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
     278          82 :         return;
     279             :       }
     280         178 :       DrawEdge("    ", ModId, IdFrom, ModId, IdTo, Hotness);
     281         110 :     };
     282             : 
     283         450 :     for (auto &SummaryIt : GVSMap) {
     284         460 :       NodeMap[SummaryIt.first].push_back(ModId);
     285         230 :       auto Flags = SummaryIt.second->flags();
     286         230 :       Attributes A;
     287         460 :       if (isa<FunctionSummary>(SummaryIt.second)) {
     288         190 :         A.add("shape", "record", "function");
     289          40 :       } else if (isa<AliasSummary>(SummaryIt.second)) {
     290          13 :         A.add("style", "dotted,filled", "alias");
     291          13 :         A.add("shape", "box");
     292             :       } else {
     293          27 :         A.add("shape", "Mrecord", "variable");
     294             :       }
     295             : 
     296         230 :       auto VI = getValueInfo(SummaryIt.first);
     297         690 :       A.add("label", getNodeLabel(VI, SummaryIt.second));
     298         230 :       if (!Flags.Live)
     299          52 :         A.add("fillcolor", "red", "dead");
     300         178 :       else if (Flags.NotEligibleToImport)
     301          22 :         A.add("fillcolor", "yellow", "not eligible to import");
     302             : 
     303         920 :       OS << "    " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
     304         230 :          << "\n";
     305             :     }
     306         110 :     OS << "    // Edges:\n";
     307             : 
     308         450 :     for (auto &SummaryIt : GVSMap) {
     309         230 :       auto *GVS = SummaryIt.second;
     310         316 :       for (auto &R : GVS->refs())
     311          43 :         Draw(SummaryIt.first, R.getGUID(), -1);
     312             : 
     313         230 :       if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
     314          13 :         auto AliaseeOrigId = AS->getAliasee().getOriginalName();
     315             :         auto AliaseeId = getGUIDFromOriginalID(AliaseeOrigId);
     316             : 
     317           1 :         Draw(SummaryIt.first, AliaseeId ? AliaseeId : AliaseeOrigId, -2);
     318          13 :         continue;
     319             :       }
     320             : 
     321             :       if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
     322         420 :         for (auto &CGEdge : FS->calls())
     323         230 :           Draw(SummaryIt.first, CGEdge.first.getGUID(),
     324         115 :                static_cast<int>(CGEdge.second.Hotness));
     325             :     }
     326         110 :     OS << "  }\n";
     327             :   }
     328             : 
     329          61 :   OS << "  // Cross-module edges:\n";
     330         143 :   for (auto &E : CrossModuleEdges) {
     331          82 :     auto &ModList = NodeMap[E.Dst];
     332          82 :     if (ModList.empty()) {
     333          13 :       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          26 :       ModList.push_back(-1);
     337             :     }
     338         164 :     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          82 :       if (DstMod != E.SrcMod)
     345          82 :         DrawEdge("  ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
     346             :   }
     347             : 
     348          61 :   OS << "}";
     349      303568 : }

Generated by: LCOV version 1.13