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