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