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),
187                     FlagValue(F.NoInline), 0};
188 
189   return FlagRep;
190 }
191 
192 // Get string representation of function instruction count and flags.
193 static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
194   auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
195   if (!FS)
196     return "";
197 
198   return std::string("inst: ") + std::to_string(FS->instCount()) +
199          ", ffl: " + fflagsToString(FS->fflags());
200 }
201 
202 static std::string getNodeVisualName(GlobalValue::GUID Id) {
203   return std::string("@") + std::to_string(Id);
204 }
205 
206 static std::string getNodeVisualName(const ValueInfo &VI) {
207   return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
208 }
209 
210 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
211   if (isa<AliasSummary>(GVS))
212     return getNodeVisualName(VI);
213 
214   std::string Attrs = getSummaryAttributes(GVS);
215   std::string Label =
216       getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
217   if (!Attrs.empty())
218     Label += std::string(" (") + Attrs + ")";
219   Label += "}";
220 
221   return Label;
222 }
223 
224 // Write definition of external node, which doesn't have any
225 // specific module associated with it. Typically this is function
226 // or variable defined in native object or library.
227 static void defineExternalNode(raw_ostream &OS, const char *Pfx,
228                                const ValueInfo &VI, GlobalValue::GUID Id) {
229   auto StrId = std::to_string(Id);
230   OS << "  " << StrId << " [label=\"";
231 
232   if (VI) {
233     OS << getNodeVisualName(VI);
234   } else {
235     OS << getNodeVisualName(Id);
236   }
237   OS << "\"]; // defined externally\n";
238 }
239 
240 void ModuleSummaryIndex::exportToDot(raw_ostream &OS) const {
241   std::vector<Edge> CrossModuleEdges;
242   DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
243   StringMap<GVSummaryMapTy> ModuleToDefinedGVS;
244   collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
245 
246   // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
247   // because we may have multiple linkonce functions summaries.
248   auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
249     return ModId == (uint64_t)-1 ? std::to_string(Id)
250                                  : std::string("M") + std::to_string(ModId) +
251                                        "_" + std::to_string(Id);
252   };
253 
254   auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
255                       uint64_t DstMod, GlobalValue::GUID DstId, int TypeOrHotness) {
256     // 0 corresponds to alias edge, 1 to ref edge, 2 to call with unknown
257     // hotness, ...
258     TypeOrHotness += 2;
259     static const char *EdgeAttrs[] = {
260         " [style=dotted]; // alias",
261         " [style=dashed]; // ref",
262         " // call (hotness : Unknown)",
263         " [color=blue]; // call (hotness : Cold)",
264         " // call (hotness : None)",
265         " [color=brown]; // call (hotness : Hot)",
266         " [style=bold,color=red]; // call (hotness : Critical)"};
267 
268     assert(static_cast<size_t>(TypeOrHotness) <
269            sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
270     OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
271        << EdgeAttrs[TypeOrHotness] << "\n";
272   };
273 
274   OS << "digraph Summary {\n";
275   for (auto &ModIt : ModuleToDefinedGVS) {
276     auto ModId = getModuleId(ModIt.first());
277     OS << "  // Module: " << ModIt.first() << "\n";
278     OS << "  subgraph cluster_" << std::to_string(ModId) << " {\n";
279     OS << "    style = filled;\n";
280     OS << "    color = lightgrey;\n";
281     OS << "    label = \"" << sys::path::filename(ModIt.first()) << "\";\n";
282     OS << "    node [style=filled,fillcolor=lightblue];\n";
283 
284     auto &GVSMap = ModIt.second;
285     auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
286       if (!GVSMap.count(IdTo)) {
287         CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
288         return;
289       }
290       DrawEdge("    ", ModId, IdFrom, ModId, IdTo, Hotness);
291     };
292 
293     for (auto &SummaryIt : GVSMap) {
294       NodeMap[SummaryIt.first].push_back(ModId);
295       auto Flags = SummaryIt.second->flags();
296       Attributes A;
297       if (isa<FunctionSummary>(SummaryIt.second)) {
298         A.add("shape", "record", "function");
299       } else if (isa<AliasSummary>(SummaryIt.second)) {
300         A.add("style", "dotted,filled", "alias");
301         A.add("shape", "box");
302       } else {
303         A.add("shape", "Mrecord", "variable");
304       }
305 
306       auto VI = getValueInfo(SummaryIt.first);
307       A.add("label", getNodeLabel(VI, SummaryIt.second));
308       if (!Flags.Live)
309         A.add("fillcolor", "red", "dead");
310       else if (Flags.NotEligibleToImport)
311         A.add("fillcolor", "yellow", "not eligible to import");
312 
313       OS << "    " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
314          << "\n";
315     }
316     OS << "    // Edges:\n";
317 
318     for (auto &SummaryIt : GVSMap) {
319       auto *GVS = SummaryIt.second;
320       for (auto &R : GVS->refs())
321         Draw(SummaryIt.first, R.getGUID(), -1);
322 
323       if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
324         GlobalValue::GUID AliaseeId;
325         if (AS->hasAliaseeGUID())
326           AliaseeId = AS->getAliaseeGUID();
327         else {
328           auto AliaseeOrigId = AS->getAliasee().getOriginalName();
329           AliaseeId = getGUIDFromOriginalID(AliaseeOrigId);
330           if (!AliaseeId)
331             AliaseeId = AliaseeOrigId;
332         }
333 
334         Draw(SummaryIt.first, AliaseeId, -2);
335         continue;
336       }
337 
338       if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
339         for (auto &CGEdge : FS->calls())
340           Draw(SummaryIt.first, CGEdge.first.getGUID(),
341                static_cast<int>(CGEdge.second.Hotness));
342     }
343     OS << "  }\n";
344   }
345 
346   OS << "  // Cross-module edges:\n";
347   for (auto &E : CrossModuleEdges) {
348     auto &ModList = NodeMap[E.Dst];
349     if (ModList.empty()) {
350       defineExternalNode(OS, "  ", getValueInfo(E.Dst), E.Dst);
351       // Add fake module to the list to draw an edge to an external node
352       // in the loop below.
353       ModList.push_back(-1);
354     }
355     for (auto DstMod : ModList)
356       // The edge representing call or ref is drawn to every module where target
357       // symbol is defined. When target is a linkonce symbol there can be
358       // multiple edges representing a single call or ref, both intra-module and
359       // cross-module. As we've already drawn all intra-module edges before we
360       // skip it here.
361       if (DstMod != E.SrcMod)
362         DrawEdge("  ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
363   }
364 
365   OS << "}";
366 }
367