[InstCombine] Signed saturation patterns
[llvm-core.git] / lib / IR / ModuleSummaryIndex.cpp
blob9f347d8da01d3162004ed76d412bcf2ae086e2bb
1 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the module index and summary classes for the
10 // IR library.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/IR/ModuleSummaryIndex.h"
15 #include "llvm/ADT/SCCIterator.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/ADT/StringMap.h"
18 #include "llvm/Support/Path.h"
19 #include "llvm/Support/raw_ostream.h"
20 using namespace llvm;
22 #define DEBUG_TYPE "module-summary-index"
24 STATISTIC(ReadOnlyLiveGVars,
25 "Number of live global variables marked read only");
26 STATISTIC(WriteOnlyLiveGVars,
27 "Number of live global variables marked write only");
29 FunctionSummary FunctionSummary::ExternalNode =
30 FunctionSummary::makeDummyFunctionSummary({});
32 bool ValueInfo::isDSOLocal() const {
33 // Need to check all summaries are local in case of hash collisions.
34 return getSummaryList().size() &&
35 llvm::all_of(getSummaryList(),
36 [](const std::unique_ptr<GlobalValueSummary> &Summary) {
37 return Summary->isDSOLocal();
38 });
41 bool ValueInfo::canAutoHide() const {
42 // Can only auto hide if all copies are eligible to auto hide.
43 return getSummaryList().size() &&
44 llvm::all_of(getSummaryList(),
45 [](const std::unique_ptr<GlobalValueSummary> &Summary) {
46 return Summary->canAutoHide();
47 });
50 // Gets the number of readonly and writeonly refs in RefEdgeList
51 std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const {
52 // Here we take advantage of having all readonly and writeonly references
53 // located in the end of the RefEdgeList.
54 auto Refs = refs();
55 unsigned RORefCnt = 0, WORefCnt = 0;
56 int I;
57 for (I = Refs.size() - 1; I >= 0 && Refs[I].isWriteOnly(); --I)
58 WORefCnt++;
59 for (; I >= 0 && Refs[I].isReadOnly(); --I)
60 RORefCnt++;
61 return {RORefCnt, WORefCnt};
64 // Collect for the given module the list of function it defines
65 // (GUID -> Summary).
66 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
67 StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
68 for (auto &GlobalList : *this) {
69 auto GUID = GlobalList.first;
70 for (auto &GlobSummary : GlobalList.second.SummaryList) {
71 auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
72 if (!Summary)
73 // Ignore global variable, focus on functions
74 continue;
75 // Ignore summaries from other modules.
76 if (Summary->modulePath() != ModulePath)
77 continue;
78 GVSummaryMap[GUID] = Summary;
83 GlobalValueSummary *
84 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
85 bool PerModuleIndex) const {
86 auto VI = getValueInfo(ValueGUID);
87 assert(VI && "GlobalValue not found in index");
88 assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
89 "Expected a single entry per global value in per-module index");
90 auto &Summary = VI.getSummaryList()[0];
91 return Summary.get();
94 bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
95 auto VI = getValueInfo(GUID);
96 if (!VI)
97 return true;
98 const auto &SummaryList = VI.getSummaryList();
99 if (SummaryList.empty())
100 return true;
101 for (auto &I : SummaryList)
102 if (isGlobalValueLive(I.get()))
103 return true;
104 return false;
107 static void propagateAttributesToRefs(GlobalValueSummary *S) {
108 // If reference is not readonly or writeonly then referenced summary is not
109 // read/writeonly either. Note that:
110 // - All references from GlobalVarSummary are conservatively considered as
111 // not readonly or writeonly. Tracking them properly requires more complex
112 // analysis then we have now.
114 // - AliasSummary objects have no refs at all so this function is a no-op
115 // for them.
116 for (auto &VI : S->refs()) {
117 assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
118 for (auto &Ref : VI.getSummaryList())
119 // If references to alias is not read/writeonly then aliasee
120 // is not read/writeonly
121 if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
122 if (!VI.isReadOnly())
123 GVS->setReadOnly(false);
124 if (!VI.isWriteOnly())
125 GVS->setWriteOnly(false);
130 // Do the access attribute propagation in combined index.
131 // The goal of attribute propagation is internalization of readonly (RO)
132 // or writeonly (WO) variables. To determine which variables are RO or WO
133 // and which are not we take following steps:
134 // - During analysis we speculatively assign readonly and writeonly
135 // attribute to all variables which can be internalized. When computing
136 // function summary we also assign readonly or writeonly attribute to a
137 // reference if function doesn't modify referenced variable (readonly)
138 // or doesn't read it (writeonly).
140 // - After computing dead symbols in combined index we do the attribute
141 // propagation. During this step we:
142 // a. clear RO and WO attributes from variables which are preserved or
143 // can't be imported
144 // b. clear RO and WO attributes from variables referenced by any global
145 // variable initializer
146 // c. clear RO attribute from variable referenced by a function when
147 // reference is not readonly
148 // d. clear WO attribute from variable referenced by a function when
149 // reference is not writeonly
151 // Because of (c, d) we don't internalize variables read by function A
152 // and modified by function B.
154 // Internalization itself happens in the backend after import is finished
155 // See internalizeGVsAfterImport.
156 void ModuleSummaryIndex::propagateAttributes(
157 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
158 for (auto &P : *this)
159 for (auto &S : P.second.SummaryList) {
160 if (!isGlobalValueLive(S.get()))
161 // We don't examine references from dead objects
162 continue;
164 // Global variable can't be marked read/writeonly if it is not eligible
165 // to import since we need to ensure that all external references get
166 // a local (imported) copy. It also can't be marked read/writeonly if
167 // it or any alias (since alias points to the same memory) are preserved
168 // or notEligibleToImport, since either of those means there could be
169 // writes (or reads in case of writeonly) that are not visible (because
170 // preserved means it could have external to DSO writes or reads, and
171 // notEligibleToImport means it could have writes or reads via inline
172 // assembly leading it to be in the @llvm.*used).
173 if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
174 // Here we intentionally pass S.get() not GVS, because S could be
175 // an alias.
176 if (!canImportGlobalVar(S.get()) ||
177 GUIDPreservedSymbols.count(P.first)) {
178 GVS->setReadOnly(false);
179 GVS->setWriteOnly(false);
181 propagateAttributesToRefs(S.get());
183 if (llvm::AreStatisticsEnabled())
184 for (auto &P : *this)
185 if (P.second.SummaryList.size())
186 if (auto *GVS = dyn_cast<GlobalVarSummary>(
187 P.second.SummaryList[0]->getBaseObject()))
188 if (isGlobalValueLive(GVS)) {
189 if (GVS->maybeReadOnly())
190 ReadOnlyLiveGVars++;
191 if (GVS->maybeWriteOnly())
192 WriteOnlyLiveGVars++;
196 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
197 // then delete this function and update its tests
198 LLVM_DUMP_METHOD
199 void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
200 for (scc_iterator<ModuleSummaryIndex *> I =
201 scc_begin<ModuleSummaryIndex *>(this);
202 !I.isAtEnd(); ++I) {
203 O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
204 << ") {\n";
205 for (const ValueInfo V : *I) {
206 FunctionSummary *F = nullptr;
207 if (V.getSummaryList().size())
208 F = cast<FunctionSummary>(V.getSummaryList().front().get());
209 O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
210 << (I.hasLoop() ? " (has loop)" : "") << "\n";
212 O << "}\n";
216 namespace {
217 struct Attributes {
218 void add(const Twine &Name, const Twine &Value,
219 const Twine &Comment = Twine());
220 void addComment(const Twine &Comment);
221 std::string getAsString() const;
223 std::vector<std::string> Attrs;
224 std::string Comments;
227 struct Edge {
228 uint64_t SrcMod;
229 int Hotness;
230 GlobalValue::GUID Src;
231 GlobalValue::GUID Dst;
235 void Attributes::add(const Twine &Name, const Twine &Value,
236 const Twine &Comment) {
237 std::string A = Name.str();
238 A += "=\"";
239 A += Value.str();
240 A += "\"";
241 Attrs.push_back(A);
242 addComment(Comment);
245 void Attributes::addComment(const Twine &Comment) {
246 if (!Comment.isTriviallyEmpty()) {
247 if (Comments.empty())
248 Comments = " // ";
249 else
250 Comments += ", ";
251 Comments += Comment.str();
255 std::string Attributes::getAsString() const {
256 if (Attrs.empty())
257 return "";
259 std::string Ret = "[";
260 for (auto &A : Attrs)
261 Ret += A + ",";
262 Ret.pop_back();
263 Ret += "];";
264 Ret += Comments;
265 return Ret;
268 static std::string linkageToString(GlobalValue::LinkageTypes LT) {
269 switch (LT) {
270 case GlobalValue::ExternalLinkage:
271 return "extern";
272 case GlobalValue::AvailableExternallyLinkage:
273 return "av_ext";
274 case GlobalValue::LinkOnceAnyLinkage:
275 return "linkonce";
276 case GlobalValue::LinkOnceODRLinkage:
277 return "linkonce_odr";
278 case GlobalValue::WeakAnyLinkage:
279 return "weak";
280 case GlobalValue::WeakODRLinkage:
281 return "weak_odr";
282 case GlobalValue::AppendingLinkage:
283 return "appending";
284 case GlobalValue::InternalLinkage:
285 return "internal";
286 case GlobalValue::PrivateLinkage:
287 return "private";
288 case GlobalValue::ExternalWeakLinkage:
289 return "extern_weak";
290 case GlobalValue::CommonLinkage:
291 return "common";
294 return "<unknown>";
297 static std::string fflagsToString(FunctionSummary::FFlags F) {
298 auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
299 char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
300 FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias),
301 FlagValue(F.NoInline), 0};
303 return FlagRep;
306 // Get string representation of function instruction count and flags.
307 static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
308 auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
309 if (!FS)
310 return "";
312 return std::string("inst: ") + std::to_string(FS->instCount()) +
313 ", ffl: " + fflagsToString(FS->fflags());
316 static std::string getNodeVisualName(GlobalValue::GUID Id) {
317 return std::string("@") + std::to_string(Id);
320 static std::string getNodeVisualName(const ValueInfo &VI) {
321 return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
324 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
325 if (isa<AliasSummary>(GVS))
326 return getNodeVisualName(VI);
328 std::string Attrs = getSummaryAttributes(GVS);
329 std::string Label =
330 getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
331 if (!Attrs.empty())
332 Label += std::string(" (") + Attrs + ")";
333 Label += "}";
335 return Label;
338 // Write definition of external node, which doesn't have any
339 // specific module associated with it. Typically this is function
340 // or variable defined in native object or library.
341 static void defineExternalNode(raw_ostream &OS, const char *Pfx,
342 const ValueInfo &VI, GlobalValue::GUID Id) {
343 auto StrId = std::to_string(Id);
344 OS << " " << StrId << " [label=\"";
346 if (VI) {
347 OS << getNodeVisualName(VI);
348 } else {
349 OS << getNodeVisualName(Id);
351 OS << "\"]; // defined externally\n";
354 static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
355 if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
356 return GVS->maybeReadOnly();
357 return false;
360 static bool hasWriteOnlyFlag(const GlobalValueSummary *S) {
361 if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
362 return GVS->maybeWriteOnly();
363 return false;
366 void ModuleSummaryIndex::exportToDot(raw_ostream &OS) const {
367 std::vector<Edge> CrossModuleEdges;
368 DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
369 using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
370 std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS;
371 collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
373 // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
374 // because we may have multiple linkonce functions summaries.
375 auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
376 return ModId == (uint64_t)-1 ? std::to_string(Id)
377 : std::string("M") + std::to_string(ModId) +
378 "_" + std::to_string(Id);
381 auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
382 uint64_t DstMod, GlobalValue::GUID DstId,
383 int TypeOrHotness) {
384 // 0 - alias
385 // 1 - reference
386 // 2 - constant reference
387 // 3 - writeonly reference
388 // Other value: (hotness - 4).
389 TypeOrHotness += 4;
390 static const char *EdgeAttrs[] = {
391 " [style=dotted]; // alias",
392 " [style=dashed]; // ref",
393 " [style=dashed,color=forestgreen]; // const-ref",
394 " [style=dashed,color=violetred]; // writeOnly-ref",
395 " // call (hotness : Unknown)",
396 " [color=blue]; // call (hotness : Cold)",
397 " // call (hotness : None)",
398 " [color=brown]; // call (hotness : Hot)",
399 " [style=bold,color=red]; // call (hotness : Critical)"};
401 assert(static_cast<size_t>(TypeOrHotness) <
402 sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
403 OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
404 << EdgeAttrs[TypeOrHotness] << "\n";
407 OS << "digraph Summary {\n";
408 for (auto &ModIt : ModuleToDefinedGVS) {
409 auto ModId = getModuleId(ModIt.first);
410 OS << " // Module: " << ModIt.first << "\n";
411 OS << " subgraph cluster_" << std::to_string(ModId) << " {\n";
412 OS << " style = filled;\n";
413 OS << " color = lightgrey;\n";
414 OS << " label = \"" << sys::path::filename(ModIt.first) << "\";\n";
415 OS << " node [style=filled,fillcolor=lightblue];\n";
417 auto &GVSMap = ModIt.second;
418 auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
419 if (!GVSMap.count(IdTo)) {
420 CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
421 return;
423 DrawEdge(" ", ModId, IdFrom, ModId, IdTo, Hotness);
426 for (auto &SummaryIt : GVSMap) {
427 NodeMap[SummaryIt.first].push_back(ModId);
428 auto Flags = SummaryIt.second->flags();
429 Attributes A;
430 if (isa<FunctionSummary>(SummaryIt.second)) {
431 A.add("shape", "record", "function");
432 } else if (isa<AliasSummary>(SummaryIt.second)) {
433 A.add("style", "dotted,filled", "alias");
434 A.add("shape", "box");
435 } else {
436 A.add("shape", "Mrecord", "variable");
437 if (Flags.Live && hasReadOnlyFlag(SummaryIt.second))
438 A.addComment("immutable");
439 if (Flags.Live && hasWriteOnlyFlag(SummaryIt.second))
440 A.addComment("writeOnly");
442 if (Flags.DSOLocal)
443 A.addComment("dsoLocal");
444 if (Flags.CanAutoHide)
445 A.addComment("canAutoHide");
447 auto VI = getValueInfo(SummaryIt.first);
448 A.add("label", getNodeLabel(VI, SummaryIt.second));
449 if (!Flags.Live)
450 A.add("fillcolor", "red", "dead");
451 else if (Flags.NotEligibleToImport)
452 A.add("fillcolor", "yellow", "not eligible to import");
454 OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
455 << "\n";
457 OS << " // Edges:\n";
459 for (auto &SummaryIt : GVSMap) {
460 auto *GVS = SummaryIt.second;
461 for (auto &R : GVS->refs())
462 Draw(SummaryIt.first, R.getGUID(),
463 R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3));
465 if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
466 Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
467 continue;
470 if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
471 for (auto &CGEdge : FS->calls())
472 Draw(SummaryIt.first, CGEdge.first.getGUID(),
473 static_cast<int>(CGEdge.second.Hotness));
475 OS << " }\n";
478 OS << " // Cross-module edges:\n";
479 for (auto &E : CrossModuleEdges) {
480 auto &ModList = NodeMap[E.Dst];
481 if (ModList.empty()) {
482 defineExternalNode(OS, " ", getValueInfo(E.Dst), E.Dst);
483 // Add fake module to the list to draw an edge to an external node
484 // in the loop below.
485 ModList.push_back(-1);
487 for (auto DstMod : ModList)
488 // The edge representing call or ref is drawn to every module where target
489 // symbol is defined. When target is a linkonce symbol there can be
490 // multiple edges representing a single call or ref, both intra-module and
491 // cross-module. As we've already drawn all intra-module edges before we
492 // skip it here.
493 if (DstMod != E.SrcMod)
494 DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
497 OS << "}";