1 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements the module index and summary classes for the
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/CommandLine.h"
19 #include "llvm/Support/Path.h"
20 #include "llvm/Support/raw_ostream.h"
23 #define DEBUG_TYPE "module-summary-index"
25 STATISTIC(ReadOnlyLiveGVars,
26 "Number of live global variables marked read only");
27 STATISTIC(WriteOnlyLiveGVars,
28 "Number of live global variables marked write only");
30 static cl::opt<bool> PropagateAttrs("propagate-attrs", cl::init(true),
32 cl::desc("Propagate attributes in index"));
34 static cl::opt<bool> ImportConstantsWithRefs(
35 "import-constants-with-refs", cl::init(true), cl::Hidden,
36 cl::desc("Import constant global variables with references"));
38 constexpr uint32_t FunctionSummary::ParamAccess::RangeWidth;
40 FunctionSummary FunctionSummary::ExternalNode =
41 FunctionSummary::makeDummyFunctionSummary({});
43 bool ValueInfo::isDSOLocal() const {
44 // Need to check all summaries are local in case of hash collisions.
45 return getSummaryList().size() &&
46 llvm::all_of(getSummaryList(),
47 [](const std::unique_ptr<GlobalValueSummary> &Summary) {
48 return Summary->isDSOLocal();
52 bool ValueInfo::canAutoHide() const {
53 // Can only auto hide if all copies are eligible to auto hide.
54 return getSummaryList().size() &&
55 llvm::all_of(getSummaryList(),
56 [](const std::unique_ptr<GlobalValueSummary> &Summary) {
57 return Summary->canAutoHide();
61 // Gets the number of readonly and writeonly refs in RefEdgeList
62 std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const {
63 // Here we take advantage of having all readonly and writeonly references
64 // located in the end of the RefEdgeList.
66 unsigned RORefCnt = 0, WORefCnt = 0;
68 for (I = Refs.size() - 1; I >= 0 && Refs[I].isWriteOnly(); --I)
70 for (; I >= 0 && Refs[I].isReadOnly(); --I)
72 return {RORefCnt, WORefCnt};
75 constexpr uint64_t ModuleSummaryIndex::BitcodeSummaryVersion;
77 uint64_t ModuleSummaryIndex::getFlags() const {
79 if (withGlobalValueDeadStripping())
81 if (skipModuleByDistributedBackend())
83 if (hasSyntheticEntryCounts())
85 if (enableSplitLTOUnit())
87 if (partiallySplitLTOUnits())
89 if (withAttributePropagation())
94 void ModuleSummaryIndex::setFlags(uint64_t Flags) {
95 assert(Flags <= 0x3f && "Unexpected bits in flag");
96 // 1 bit: WithGlobalValueDeadStripping flag.
97 // Set on combined index only.
99 setWithGlobalValueDeadStripping();
100 // 1 bit: SkipModuleByDistributedBackend flag.
101 // Set on combined index only.
103 setSkipModuleByDistributedBackend();
104 // 1 bit: HasSyntheticEntryCounts flag.
105 // Set on combined index only.
107 setHasSyntheticEntryCounts();
108 // 1 bit: DisableSplitLTOUnit flag.
109 // Set on per module indexes. It is up to the client to validate
110 // the consistency of this flag across modules being linked.
112 setEnableSplitLTOUnit();
113 // 1 bit: PartiallySplitLTOUnits flag.
114 // Set on combined index only.
116 setPartiallySplitLTOUnits();
117 // 1 bit: WithAttributePropagation flag.
118 // Set on combined index only.
120 setWithAttributePropagation();
123 // Collect for the given module the list of function it defines
124 // (GUID -> Summary).
125 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
126 StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
127 for (auto &GlobalList : *this) {
128 auto GUID = GlobalList.first;
129 for (auto &GlobSummary : GlobalList.second.SummaryList) {
130 auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
132 // Ignore global variable, focus on functions
134 // Ignore summaries from other modules.
135 if (Summary->modulePath() != ModulePath)
137 GVSummaryMap[GUID] = Summary;
143 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
144 bool PerModuleIndex) const {
145 auto VI = getValueInfo(ValueGUID);
146 assert(VI && "GlobalValue not found in index");
147 assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
148 "Expected a single entry per global value in per-module index");
149 auto &Summary = VI.getSummaryList()[0];
150 return Summary.get();
153 bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
154 auto VI = getValueInfo(GUID);
157 const auto &SummaryList = VI.getSummaryList();
158 if (SummaryList.empty())
160 for (auto &I : SummaryList)
161 if (isGlobalValueLive(I.get()))
166 static void propagateAttributesToRefs(GlobalValueSummary *S) {
167 // If reference is not readonly or writeonly then referenced summary is not
168 // read/writeonly either. Note that:
169 // - All references from GlobalVarSummary are conservatively considered as
170 // not readonly or writeonly. Tracking them properly requires more complex
171 // analysis then we have now.
173 // - AliasSummary objects have no refs at all so this function is a no-op
175 for (auto &VI : S->refs()) {
176 assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
177 for (auto &Ref : VI.getSummaryList())
178 // If references to alias is not read/writeonly then aliasee
179 // is not read/writeonly
180 if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
181 if (!VI.isReadOnly())
182 GVS->setReadOnly(false);
183 if (!VI.isWriteOnly())
184 GVS->setWriteOnly(false);
189 // Do the access attribute propagation in combined index.
190 // The goal of attribute propagation is internalization of readonly (RO)
191 // or writeonly (WO) variables. To determine which variables are RO or WO
192 // and which are not we take following steps:
193 // - During analysis we speculatively assign readonly and writeonly
194 // attribute to all variables which can be internalized. When computing
195 // function summary we also assign readonly or writeonly attribute to a
196 // reference if function doesn't modify referenced variable (readonly)
197 // or doesn't read it (writeonly).
199 // - After computing dead symbols in combined index we do the attribute
200 // propagation. During this step we:
201 // a. clear RO and WO attributes from variables which are preserved or
203 // b. clear RO and WO attributes from variables referenced by any global
204 // variable initializer
205 // c. clear RO attribute from variable referenced by a function when
206 // reference is not readonly
207 // d. clear WO attribute from variable referenced by a function when
208 // reference is not writeonly
210 // Because of (c, d) we don't internalize variables read by function A
211 // and modified by function B.
213 // Internalization itself happens in the backend after import is finished
214 // See internalizeGVsAfterImport.
215 void ModuleSummaryIndex::propagateAttributes(
216 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
219 for (auto &P : *this)
220 for (auto &S : P.second.SummaryList) {
221 if (!isGlobalValueLive(S.get()))
222 // We don't examine references from dead objects
225 // Global variable can't be marked read/writeonly if it is not eligible
226 // to import since we need to ensure that all external references get
227 // a local (imported) copy. It also can't be marked read/writeonly if
228 // it or any alias (since alias points to the same memory) are preserved
229 // or notEligibleToImport, since either of those means there could be
230 // writes (or reads in case of writeonly) that are not visible (because
231 // preserved means it could have external to DSO writes or reads, and
232 // notEligibleToImport means it could have writes or reads via inline
233 // assembly leading it to be in the @llvm.*used).
234 if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
235 // Here we intentionally pass S.get() not GVS, because S could be
236 // an alias. We don't analyze references here, because we have to
237 // know exactly if GV is readonly to do so.
238 if (!canImportGlobalVar(S.get(), /* AnalyzeRefs */ false) ||
239 GUIDPreservedSymbols.count(P.first)) {
240 GVS->setReadOnly(false);
241 GVS->setWriteOnly(false);
243 propagateAttributesToRefs(S.get());
245 setWithAttributePropagation();
246 if (llvm::AreStatisticsEnabled())
247 for (auto &P : *this)
248 if (P.second.SummaryList.size())
249 if (auto *GVS = dyn_cast<GlobalVarSummary>(
250 P.second.SummaryList[0]->getBaseObject()))
251 if (isGlobalValueLive(GVS)) {
252 if (GVS->maybeReadOnly())
254 if (GVS->maybeWriteOnly())
255 WriteOnlyLiveGVars++;
259 bool ModuleSummaryIndex::canImportGlobalVar(GlobalValueSummary *S,
260 bool AnalyzeRefs) const {
261 auto HasRefsPreventingImport = [this](const GlobalVarSummary *GVS) {
262 // We don't analyze GV references during attribute propagation, so
263 // GV with non-trivial initializer can be marked either read or
265 // Importing definiton of readonly GV with non-trivial initializer
266 // allows us doing some extra optimizations (like converting indirect
268 // Definition of writeonly GV with non-trivial initializer should also
269 // be imported. Not doing so will result in:
270 // a) GV internalization in source module (because it's writeonly)
271 // b) Importing of GV declaration to destination module as a result
273 // c) Link error (external declaration with internal definition).
274 // However we do not promote objects referenced by writeonly GV
275 // initializer by means of converting it to 'zeroinitializer'
276 return !(ImportConstantsWithRefs && GVS->isConstant()) &&
277 !isReadOnly(GVS) && !isWriteOnly(GVS) && GVS->refs().size();
279 auto *GVS = cast<GlobalVarSummary>(S->getBaseObject());
281 // Global variable with non-trivial initializer can be imported
282 // if it's readonly. This gives us extra opportunities for constant
283 // folding and converting indirect calls to direct calls. We don't
284 // analyze GV references during attribute propagation, because we
285 // don't know yet if it is readonly or not.
286 return !GlobalValue::isInterposableLinkage(S->linkage()) &&
287 !S->notEligibleToImport() &&
288 (!AnalyzeRefs || !HasRefsPreventingImport(GVS));
291 // TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
292 // then delete this function and update its tests
294 void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
295 for (scc_iterator<ModuleSummaryIndex *> I =
296 scc_begin<ModuleSummaryIndex *>(this);
298 O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
300 for (const ValueInfo &V : *I) {
301 FunctionSummary *F = nullptr;
302 if (V.getSummaryList().size())
303 F = cast<FunctionSummary>(V.getSummaryList().front().get());
304 O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
305 << (I.hasCycle() ? " (has cycle)" : "") << "\n";
313 void add(const Twine &Name, const Twine &Value,
314 const Twine &Comment = Twine());
315 void addComment(const Twine &Comment);
316 std::string getAsString() const;
318 std::vector<std::string> Attrs;
319 std::string Comments;
325 GlobalValue::GUID Src;
326 GlobalValue::GUID Dst;
330 void Attributes::add(const Twine &Name, const Twine &Value,
331 const Twine &Comment) {
332 std::string A = Name.str();
340 void Attributes::addComment(const Twine &Comment) {
341 if (!Comment.isTriviallyEmpty()) {
342 if (Comments.empty())
346 Comments += Comment.str();
350 std::string Attributes::getAsString() const {
354 std::string Ret = "[";
355 for (auto &A : Attrs)
363 static std::string linkageToString(GlobalValue::LinkageTypes LT) {
365 case GlobalValue::ExternalLinkage:
367 case GlobalValue::AvailableExternallyLinkage:
369 case GlobalValue::LinkOnceAnyLinkage:
371 case GlobalValue::LinkOnceODRLinkage:
372 return "linkonce_odr";
373 case GlobalValue::WeakAnyLinkage:
375 case GlobalValue::WeakODRLinkage:
377 case GlobalValue::AppendingLinkage:
379 case GlobalValue::InternalLinkage:
381 case GlobalValue::PrivateLinkage:
383 case GlobalValue::ExternalWeakLinkage:
384 return "extern_weak";
385 case GlobalValue::CommonLinkage:
392 static std::string fflagsToString(FunctionSummary::FFlags F) {
393 auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
394 char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
395 FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias),
396 FlagValue(F.NoInline), FlagValue(F.AlwaysInline), 0};
401 // Get string representation of function instruction count and flags.
402 static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
403 auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
407 return std::string("inst: ") + std::to_string(FS->instCount()) +
408 ", ffl: " + fflagsToString(FS->fflags());
411 static std::string getNodeVisualName(GlobalValue::GUID Id) {
412 return std::string("@") + std::to_string(Id);
415 static std::string getNodeVisualName(const ValueInfo &VI) {
416 return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
419 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
420 if (isa<AliasSummary>(GVS))
421 return getNodeVisualName(VI);
423 std::string Attrs = getSummaryAttributes(GVS);
425 getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
427 Label += std::string(" (") + Attrs + ")";
433 // Write definition of external node, which doesn't have any
434 // specific module associated with it. Typically this is function
435 // or variable defined in native object or library.
436 static void defineExternalNode(raw_ostream &OS, const char *Pfx,
437 const ValueInfo &VI, GlobalValue::GUID Id) {
438 auto StrId = std::to_string(Id);
439 OS << " " << StrId << " [label=\"";
442 OS << getNodeVisualName(VI);
444 OS << getNodeVisualName(Id);
446 OS << "\"]; // defined externally\n";
449 static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
450 if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
451 return GVS->maybeReadOnly();
455 static bool hasWriteOnlyFlag(const GlobalValueSummary *S) {
456 if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
457 return GVS->maybeWriteOnly();
461 static bool hasConstantFlag(const GlobalValueSummary *S) {
462 if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
463 return GVS->isConstant();
467 void ModuleSummaryIndex::exportToDot(
469 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const {
470 std::vector<Edge> CrossModuleEdges;
471 DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
472 using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
473 std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS;
474 collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
476 // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
477 // because we may have multiple linkonce functions summaries.
478 auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
479 return ModId == (uint64_t)-1 ? std::to_string(Id)
480 : std::string("M") + std::to_string(ModId) +
481 "_" + std::to_string(Id);
484 auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
485 uint64_t DstMod, GlobalValue::GUID DstId,
489 // 2 - constant reference
490 // 3 - writeonly reference
491 // Other value: (hotness - 4).
493 static const char *EdgeAttrs[] = {
494 " [style=dotted]; // alias",
495 " [style=dashed]; // ref",
496 " [style=dashed,color=forestgreen]; // const-ref",
497 " [style=dashed,color=violetred]; // writeOnly-ref",
498 " // call (hotness : Unknown)",
499 " [color=blue]; // call (hotness : Cold)",
500 " // call (hotness : None)",
501 " [color=brown]; // call (hotness : Hot)",
502 " [style=bold,color=red]; // call (hotness : Critical)"};
504 assert(static_cast<size_t>(TypeOrHotness) <
505 sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
506 OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
507 << EdgeAttrs[TypeOrHotness] << "\n";
510 OS << "digraph Summary {\n";
511 for (auto &ModIt : ModuleToDefinedGVS) {
512 auto ModId = getModuleId(ModIt.first);
513 OS << " // Module: " << ModIt.first << "\n";
514 OS << " subgraph cluster_" << std::to_string(ModId) << " {\n";
515 OS << " style = filled;\n";
516 OS << " color = lightgrey;\n";
517 OS << " label = \"" << sys::path::filename(ModIt.first) << "\";\n";
518 OS << " node [style=filled,fillcolor=lightblue];\n";
520 auto &GVSMap = ModIt.second;
521 auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
522 if (!GVSMap.count(IdTo)) {
523 CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
526 DrawEdge(" ", ModId, IdFrom, ModId, IdTo, Hotness);
529 for (auto &SummaryIt : GVSMap) {
530 NodeMap[SummaryIt.first].push_back(ModId);
531 auto Flags = SummaryIt.second->flags();
533 if (isa<FunctionSummary>(SummaryIt.second)) {
534 A.add("shape", "record", "function");
535 } else if (isa<AliasSummary>(SummaryIt.second)) {
536 A.add("style", "dotted,filled", "alias");
537 A.add("shape", "box");
539 A.add("shape", "Mrecord", "variable");
540 if (Flags.Live && hasReadOnlyFlag(SummaryIt.second))
541 A.addComment("immutable");
542 if (Flags.Live && hasWriteOnlyFlag(SummaryIt.second))
543 A.addComment("writeOnly");
544 if (Flags.Live && hasConstantFlag(SummaryIt.second))
545 A.addComment("constant");
548 A.addComment("dsoLocal");
549 if (Flags.CanAutoHide)
550 A.addComment("canAutoHide");
551 if (GUIDPreservedSymbols.count(SummaryIt.first))
552 A.addComment("preserved");
554 auto VI = getValueInfo(SummaryIt.first);
555 A.add("label", getNodeLabel(VI, SummaryIt.second));
557 A.add("fillcolor", "red", "dead");
558 else if (Flags.NotEligibleToImport)
559 A.add("fillcolor", "yellow", "not eligible to import");
561 OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
564 OS << " // Edges:\n";
566 for (auto &SummaryIt : GVSMap) {
567 auto *GVS = SummaryIt.second;
568 for (auto &R : GVS->refs())
569 Draw(SummaryIt.first, R.getGUID(),
570 R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3));
572 if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
573 Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
577 if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
578 for (auto &CGEdge : FS->calls())
579 Draw(SummaryIt.first, CGEdge.first.getGUID(),
580 static_cast<int>(CGEdge.second.Hotness));
585 OS << " // Cross-module edges:\n";
586 for (auto &E : CrossModuleEdges) {
587 auto &ModList = NodeMap[E.Dst];
588 if (ModList.empty()) {
589 defineExternalNode(OS, " ", getValueInfo(E.Dst), E.Dst);
590 // Add fake module to the list to draw an edge to an external node
591 // in the loop below.
592 ModList.push_back(-1);
594 for (auto DstMod : ModList)
595 // The edge representing call or ref is drawn to every module where target
596 // symbol is defined. When target is a linkonce symbol there can be
597 // multiple edges representing a single call or ref, both intra-module and
598 // cross-module. As we've already drawn all intra-module edges before we
600 if (DstMod != E.SrcMod)
601 DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);