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 : FunctionSummary FunctionSummary::ExternalNode =
23 : FunctionSummary::makeDummyFunctionSummary({});
24 1844 : bool ValueInfo::isDSOLocal() const {
25 : // Need to check all summaries are local in case of hash collisions.
26 1844 : return getSummaryList().size() &&
27 : llvm::all_of(getSummaryList(),
28 : [](const std::unique_ptr<GlobalValueSummary> &Summary) {
29 0 : return Summary->isDSOLocal();
30 1844 : });
31 : }
32 :
33 : // Collect for the given module the list of function it defines
34 : // (GUID -> Summary).
35 17 : void ModuleSummaryIndex::collectDefinedFunctionsForModule(
36 : StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
37 165 : for (auto &GlobalList : *this) {
38 148 : auto GUID = GlobalList.first;
39 296 : 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 18 : GVSummaryMap[GUID] = Summary;
48 : }
49 : }
50 17 : }
51 :
52 : // Collect for each module the list of function it defines (GUID -> Summary).
53 351 : void ModuleSummaryIndex::collectDefinedGVSummariesPerModule(
54 : StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const {
55 1660 : for (auto &GlobalList : *this) {
56 1309 : auto GUID = GlobalList.first;
57 2590 : for (auto &Summary : GlobalList.second.SummaryList) {
58 1281 : ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
59 : }
60 : }
61 351 : }
62 :
63 : GlobalValueSummary *
64 264 : ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
65 : bool PerModuleIndex) const {
66 264 : 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 264 : return Summary.get();
72 : }
73 :
74 445 : bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
75 445 : auto VI = getValueInfo(GUID);
76 445 : if (!VI)
77 : return true;
78 : const auto &SummaryList = VI.getSummaryList();
79 439 : if (SummaryList.empty())
80 : return true;
81 438 : for (auto &I : SummaryList)
82 425 : if (isGlobalValueLive(I.get()))
83 408 : 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 11 : O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
95 5 : << ") {\n";
96 11 : for (const ValueInfo V : *I) {
97 : FunctionSummary *F = nullptr;
98 6 : if (V.getSummaryList().size())
99 : F = cast<FunctionSummary>(V.getSummaryList().front().get());
100 17 : O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
101 10 : << (I.hasLoop() ? " (has loop)" : "") << "\n";
102 : }
103 5 : O << "}\n";
104 : }
105 1 : }
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 583 : void Attributes::add(const Twine &Name, const Twine &Value,
126 : const Twine &Comment) {
127 583 : std::string A = Name.str();
128 : A += "=\"";
129 1166 : A += Value.str();
130 : A += "\"";
131 583 : Attrs.push_back(A);
132 : if (!Comment.isTriviallyEmpty()) {
133 326 : if (Comments.empty())
134 244 : Comments = " // ";
135 : else
136 82 : Comments += ", ";
137 652 : Comments += Comment.str();
138 : }
139 583 : }
140 :
141 244 : std::string Attributes::getAsString() const {
142 244 : if (Attrs.empty())
143 0 : return "";
144 :
145 244 : std::string Ret = "[";
146 827 : for (auto &A : Attrs)
147 1166 : Ret += A + ",";
148 : Ret.pop_back();
149 : Ret += "];";
150 : Ret += Comments;
151 : return Ret;
152 : }
153 :
154 231 : static std::string linkageToString(GlobalValue::LinkageTypes LT) {
155 231 : switch (LT) {
156 : case GlobalValue::ExternalLinkage:
157 174 : return "extern";
158 : case GlobalValue::AvailableExternallyLinkage:
159 0 : return "av_ext";
160 : case GlobalValue::LinkOnceAnyLinkage:
161 5 : return "linkonce";
162 : case GlobalValue::LinkOnceODRLinkage:
163 13 : return "linkonce_odr";
164 : case GlobalValue::WeakAnyLinkage:
165 9 : return "weak";
166 : case GlobalValue::WeakODRLinkage:
167 2 : return "weak_odr";
168 : case GlobalValue::AppendingLinkage:
169 3 : return "appending";
170 : case GlobalValue::InternalLinkage:
171 23 : 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 194 : static std::string fflagsToString(FunctionSummary::FFlags F) {
184 776 : auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
185 194 : char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
186 582 : FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias), 0};
187 :
188 194 : return FlagRep;
189 : }
190 :
191 : // Get string representation of function instruction count and flags.
192 231 : static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
193 : auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
194 : if (!FS)
195 37 : return "";
196 :
197 388 : return std::string("inst: ") + std::to_string(FS->instCount()) +
198 582 : ", ffl: " + fflagsToString(FS->fflags());
199 : }
200 :
201 271 : static std::string getNodeVisualName(const ValueInfo &VI) {
202 544 : return VI.name().empty() ? std::string("@") + std::to_string(VI.getGUID())
203 542 : : VI.name().str();
204 : }
205 :
206 244 : static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
207 244 : if (isa<AliasSummary>(GVS))
208 13 : return getNodeVisualName(VI);
209 :
210 231 : std::string Attrs = getSummaryAttributes(GVS);
211 : std::string Label =
212 462 : getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
213 231 : if (!Attrs.empty())
214 388 : 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 0 : static void defineExternalNode(raw_ostream &OS, const char *Pfx,
224 : const ValueInfo &VI) {
225 : auto StrId = std::to_string(VI.getGUID());
226 0 : OS << " " << StrId << " [label=\"" << getNodeVisualName(VI)
227 0 : << "\"]; // defined externally\n";
228 0 : }
229 :
230 70 : void ModuleSummaryIndex::exportToDot(raw_ostream& OS) const {
231 : std::vector<Edge> CrossModuleEdges;
232 : DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
233 70 : StringMap<GVSummaryMapTy> ModuleToDefinedGVS;
234 70 : 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 70 : };
263 :
264 70 : OS << "digraph Summary {\n";
265 269 : for (auto &ModIt : ModuleToDefinedGVS) {
266 129 : auto ModId = getModuleId(ModIt.first());
267 129 : OS << " // Module: " << ModIt.first() << "\n";
268 258 : OS << " subgraph cluster_" << std::to_string(ModId) << " {\n";
269 129 : OS << " style = filled;\n";
270 129 : OS << " color = lightgrey;\n";
271 129 : OS << " label = \"" << sys::path::filename(ModIt.first()) << "\";\n";
272 129 : OS << " node [style=filled,fillcolor=lightblue];\n";
273 :
274 129 : 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 129 : };
282 :
283 373 : for (auto &SummaryIt : GVSMap) {
284 244 : NodeMap[SummaryIt.first].push_back(ModId);
285 488 : auto Flags = SummaryIt.second->flags();
286 244 : Attributes A;
287 488 : if (isa<FunctionSummary>(SummaryIt.second)) {
288 194 : A.add("shape", "record", "function");
289 50 : } else if (isa<AliasSummary>(SummaryIt.second)) {
290 13 : A.add("style", "dotted,filled", "alias");
291 13 : A.add("shape", "box");
292 : } else {
293 37 : A.add("shape", "Mrecord", "variable");
294 : }
295 :
296 244 : auto VI = getValueInfo(SummaryIt.first);
297 244 : A.add("label", getNodeLabel(VI, SummaryIt.second));
298 244 : if (!Flags.Live)
299 54 : A.add("fillcolor", "red", "dead");
300 190 : else if (Flags.NotEligibleToImport)
301 28 : A.add("fillcolor", "yellow", "not eligible to import");
302 :
303 976 : OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
304 244 : << "\n";
305 : }
306 129 : OS << " // Edges:\n";
307 :
308 373 : for (auto &SummaryIt : GVSMap) {
309 244 : auto *GVS = SummaryIt.second;
310 308 : for (auto &R : GVS->refs())
311 64 : Draw(SummaryIt.first, R.getGUID(), -1);
312 :
313 244 : if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
314 13 : auto AliaseeOrigId = AS->getAliasee().getOriginalName();
315 : auto AliaseeId = getGUIDFromOriginalID(AliaseeOrigId);
316 :
317 13 : Draw(SummaryIt.first, AliaseeId ? AliaseeId : AliaseeOrigId, -2);
318 13 : continue;
319 : }
320 :
321 : if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
322 297 : for (auto &CGEdge : FS->calls())
323 103 : Draw(SummaryIt.first, CGEdge.first.getGUID(),
324 103 : static_cast<int>(CGEdge.second.Hotness));
325 : }
326 129 : OS << " }\n";
327 : }
328 :
329 70 : OS << " // Cross-module edges:\n";
330 171 : for (auto &E : CrossModuleEdges) {
331 101 : auto &ModList = NodeMap[E.Dst];
332 101 : if (ModList.empty()) {
333 27 : 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 27 : ModList.push_back(-1);
337 : }
338 202 : 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 101 : if (DstMod != E.SrcMod)
345 101 : DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
346 : }
347 :
348 70 : OS << "}";
349 70 : }
|
