aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/IR/ModuleSummaryIndex.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/IR/ModuleSummaryIndex.cpp')
-rw-r--r--llvm/lib/IR/ModuleSummaryIndex.cpp498
1 files changed, 498 insertions, 0 deletions
diff --git a/llvm/lib/IR/ModuleSummaryIndex.cpp b/llvm/lib/IR/ModuleSummaryIndex.cpp
new file mode 100644
index 000000000000..9f347d8da01d
--- /dev/null
+++ b/llvm/lib/IR/ModuleSummaryIndex.cpp
@@ -0,0 +1,498 @@
+//===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the module index and summary classes for the
+// IR library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/ModuleSummaryIndex.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "module-summary-index"
+
+STATISTIC(ReadOnlyLiveGVars,
+ "Number of live global variables marked read only");
+STATISTIC(WriteOnlyLiveGVars,
+ "Number of live global variables marked write only");
+
+FunctionSummary FunctionSummary::ExternalNode =
+ FunctionSummary::makeDummyFunctionSummary({});
+
+bool ValueInfo::isDSOLocal() const {
+ // Need to check all summaries are local in case of hash collisions.
+ return getSummaryList().size() &&
+ llvm::all_of(getSummaryList(),
+ [](const std::unique_ptr<GlobalValueSummary> &Summary) {
+ return Summary->isDSOLocal();
+ });
+}
+
+bool ValueInfo::canAutoHide() const {
+ // Can only auto hide if all copies are eligible to auto hide.
+ return getSummaryList().size() &&
+ llvm::all_of(getSummaryList(),
+ [](const std::unique_ptr<GlobalValueSummary> &Summary) {
+ return Summary->canAutoHide();
+ });
+}
+
+// Gets the number of readonly and writeonly refs in RefEdgeList
+std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const {
+ // Here we take advantage of having all readonly and writeonly references
+ // located in the end of the RefEdgeList.
+ auto Refs = refs();
+ unsigned RORefCnt = 0, WORefCnt = 0;
+ int I;
+ for (I = Refs.size() - 1; I >= 0 && Refs[I].isWriteOnly(); --I)
+ WORefCnt++;
+ for (; I >= 0 && Refs[I].isReadOnly(); --I)
+ RORefCnt++;
+ return {RORefCnt, WORefCnt};
+}
+
+// Collect for the given module the list of function it defines
+// (GUID -> Summary).
+void ModuleSummaryIndex::collectDefinedFunctionsForModule(
+ StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
+ for (auto &GlobalList : *this) {
+ auto GUID = GlobalList.first;
+ for (auto &GlobSummary : GlobalList.second.SummaryList) {
+ auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
+ if (!Summary)
+ // Ignore global variable, focus on functions
+ continue;
+ // Ignore summaries from other modules.
+ if (Summary->modulePath() != ModulePath)
+ continue;
+ GVSummaryMap[GUID] = Summary;
+ }
+ }
+}
+
+GlobalValueSummary *
+ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
+ bool PerModuleIndex) const {
+ auto VI = getValueInfo(ValueGUID);
+ assert(VI && "GlobalValue not found in index");
+ assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
+ "Expected a single entry per global value in per-module index");
+ auto &Summary = VI.getSummaryList()[0];
+ return Summary.get();
+}
+
+bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
+ auto VI = getValueInfo(GUID);
+ if (!VI)
+ return true;
+ const auto &SummaryList = VI.getSummaryList();
+ if (SummaryList.empty())
+ return true;
+ for (auto &I : SummaryList)
+ if (isGlobalValueLive(I.get()))
+ return true;
+ return false;
+}
+
+static void propagateAttributesToRefs(GlobalValueSummary *S) {
+ // If reference is not readonly or writeonly then referenced summary is not
+ // read/writeonly either. Note that:
+ // - All references from GlobalVarSummary are conservatively considered as
+ // not readonly or writeonly. Tracking them properly requires more complex
+ // analysis then we have now.
+ //
+ // - AliasSummary objects have no refs at all so this function is a no-op
+ // for them.
+ for (auto &VI : S->refs()) {
+ assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
+ for (auto &Ref : VI.getSummaryList())
+ // If references to alias is not read/writeonly then aliasee
+ // is not read/writeonly
+ if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
+ if (!VI.isReadOnly())
+ GVS->setReadOnly(false);
+ if (!VI.isWriteOnly())
+ GVS->setWriteOnly(false);
+ }
+ }
+}
+
+// Do the access attribute propagation in combined index.
+// The goal of attribute propagation is internalization of readonly (RO)
+// or writeonly (WO) variables. To determine which variables are RO or WO
+// and which are not we take following steps:
+// - During analysis we speculatively assign readonly and writeonly
+// attribute to all variables which can be internalized. When computing
+// function summary we also assign readonly or writeonly attribute to a
+// reference if function doesn't modify referenced variable (readonly)
+// or doesn't read it (writeonly).
+//
+// - After computing dead symbols in combined index we do the attribute
+// propagation. During this step we:
+// a. clear RO and WO attributes from variables which are preserved or
+// can't be imported
+// b. clear RO and WO attributes from variables referenced by any global
+// variable initializer
+// c. clear RO attribute from variable referenced by a function when
+// reference is not readonly
+// d. clear WO attribute from variable referenced by a function when
+// reference is not writeonly
+//
+// Because of (c, d) we don't internalize variables read by function A
+// and modified by function B.
+//
+// Internalization itself happens in the backend after import is finished
+// See internalizeGVsAfterImport.
+void ModuleSummaryIndex::propagateAttributes(
+ const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
+ for (auto &P : *this)
+ for (auto &S : P.second.SummaryList) {
+ if (!isGlobalValueLive(S.get()))
+ // We don't examine references from dead objects
+ continue;
+
+ // Global variable can't be marked read/writeonly if it is not eligible
+ // to import since we need to ensure that all external references get
+ // a local (imported) copy. It also can't be marked read/writeonly if
+ // it or any alias (since alias points to the same memory) are preserved
+ // or notEligibleToImport, since either of those means there could be
+ // writes (or reads in case of writeonly) that are not visible (because
+ // preserved means it could have external to DSO writes or reads, and
+ // notEligibleToImport means it could have writes or reads via inline
+ // assembly leading it to be in the @llvm.*used).
+ if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
+ // Here we intentionally pass S.get() not GVS, because S could be
+ // an alias.
+ if (!canImportGlobalVar(S.get()) ||
+ GUIDPreservedSymbols.count(P.first)) {
+ GVS->setReadOnly(false);
+ GVS->setWriteOnly(false);
+ }
+ propagateAttributesToRefs(S.get());
+ }
+ if (llvm::AreStatisticsEnabled())
+ for (auto &P : *this)
+ if (P.second.SummaryList.size())
+ if (auto *GVS = dyn_cast<GlobalVarSummary>(
+ P.second.SummaryList[0]->getBaseObject()))
+ if (isGlobalValueLive(GVS)) {
+ if (GVS->maybeReadOnly())
+ ReadOnlyLiveGVars++;
+ if (GVS->maybeWriteOnly())
+ WriteOnlyLiveGVars++;
+ }
+}
+
+// TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
+// then delete this function and update its tests
+LLVM_DUMP_METHOD
+void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
+ for (scc_iterator<ModuleSummaryIndex *> I =
+ scc_begin<ModuleSummaryIndex *>(this);
+ !I.isAtEnd(); ++I) {
+ O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
+ << ") {\n";
+ for (const ValueInfo V : *I) {
+ FunctionSummary *F = nullptr;
+ if (V.getSummaryList().size())
+ F = cast<FunctionSummary>(V.getSummaryList().front().get());
+ O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
+ << (I.hasLoop() ? " (has loop)" : "") << "\n";
+ }
+ O << "}\n";
+ }
+}
+
+namespace {
+struct Attributes {
+ void add(const Twine &Name, const Twine &Value,
+ const Twine &Comment = Twine());
+ void addComment(const Twine &Comment);
+ std::string getAsString() const;
+
+ std::vector<std::string> Attrs;
+ std::string Comments;
+};
+
+struct Edge {
+ uint64_t SrcMod;
+ int Hotness;
+ GlobalValue::GUID Src;
+ GlobalValue::GUID Dst;
+};
+}
+
+void Attributes::add(const Twine &Name, const Twine &Value,
+ const Twine &Comment) {
+ std::string A = Name.str();
+ A += "=\"";
+ A += Value.str();
+ A += "\"";
+ Attrs.push_back(A);
+ addComment(Comment);
+}
+
+void Attributes::addComment(const Twine &Comment) {
+ if (!Comment.isTriviallyEmpty()) {
+ if (Comments.empty())
+ Comments = " // ";
+ else
+ Comments += ", ";
+ Comments += Comment.str();
+ }
+}
+
+std::string Attributes::getAsString() const {
+ if (Attrs.empty())
+ return "";
+
+ std::string Ret = "[";
+ for (auto &A : Attrs)
+ Ret += A + ",";
+ Ret.pop_back();
+ Ret += "];";
+ Ret += Comments;
+ return Ret;
+}
+
+static std::string linkageToString(GlobalValue::LinkageTypes LT) {
+ switch (LT) {
+ case GlobalValue::ExternalLinkage:
+ return "extern";
+ case GlobalValue::AvailableExternallyLinkage:
+ return "av_ext";
+ case GlobalValue::LinkOnceAnyLinkage:
+ return "linkonce";
+ case GlobalValue::LinkOnceODRLinkage:
+ return "linkonce_odr";
+ case GlobalValue::WeakAnyLinkage:
+ return "weak";
+ case GlobalValue::WeakODRLinkage:
+ return "weak_odr";
+ case GlobalValue::AppendingLinkage:
+ return "appending";
+ case GlobalValue::InternalLinkage:
+ return "internal";
+ case GlobalValue::PrivateLinkage:
+ return "private";
+ case GlobalValue::ExternalWeakLinkage:
+ return "extern_weak";
+ case GlobalValue::CommonLinkage:
+ return "common";
+ }
+
+ return "<unknown>";
+}
+
+static std::string fflagsToString(FunctionSummary::FFlags F) {
+ auto FlagValue = [](unsigned V) { return V ? '1' : '0'; };
+ char FlagRep[] = {FlagValue(F.ReadNone), FlagValue(F.ReadOnly),
+ FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias),
+ FlagValue(F.NoInline), 0};
+
+ return FlagRep;
+}
+
+// Get string representation of function instruction count and flags.
+static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
+ auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
+ if (!FS)
+ return "";
+
+ return std::string("inst: ") + std::to_string(FS->instCount()) +
+ ", ffl: " + fflagsToString(FS->fflags());
+}
+
+static std::string getNodeVisualName(GlobalValue::GUID Id) {
+ return std::string("@") + std::to_string(Id);
+}
+
+static std::string getNodeVisualName(const ValueInfo &VI) {
+ return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
+}
+
+static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
+ if (isa<AliasSummary>(GVS))
+ return getNodeVisualName(VI);
+
+ std::string Attrs = getSummaryAttributes(GVS);
+ std::string Label =
+ getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
+ if (!Attrs.empty())
+ Label += std::string(" (") + Attrs + ")";
+ Label += "}";
+
+ return Label;
+}
+
+// Write definition of external node, which doesn't have any
+// specific module associated with it. Typically this is function
+// or variable defined in native object or library.
+static void defineExternalNode(raw_ostream &OS, const char *Pfx,
+ const ValueInfo &VI, GlobalValue::GUID Id) {
+ auto StrId = std::to_string(Id);
+ OS << " " << StrId << " [label=\"";
+
+ if (VI) {
+ OS << getNodeVisualName(VI);
+ } else {
+ OS << getNodeVisualName(Id);
+ }
+ OS << "\"]; // defined externally\n";
+}
+
+static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
+ if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
+ return GVS->maybeReadOnly();
+ return false;
+}
+
+static bool hasWriteOnlyFlag(const GlobalValueSummary *S) {
+ if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
+ return GVS->maybeWriteOnly();
+ return false;
+}
+
+void ModuleSummaryIndex::exportToDot(raw_ostream &OS) const {
+ std::vector<Edge> CrossModuleEdges;
+ DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
+ using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
+ std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS;
+ collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
+
+ // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
+ // because we may have multiple linkonce functions summaries.
+ auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
+ return ModId == (uint64_t)-1 ? std::to_string(Id)
+ : std::string("M") + std::to_string(ModId) +
+ "_" + std::to_string(Id);
+ };
+
+ auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
+ uint64_t DstMod, GlobalValue::GUID DstId,
+ int TypeOrHotness) {
+ // 0 - alias
+ // 1 - reference
+ // 2 - constant reference
+ // 3 - writeonly reference
+ // Other value: (hotness - 4).
+ TypeOrHotness += 4;
+ static const char *EdgeAttrs[] = {
+ " [style=dotted]; // alias",
+ " [style=dashed]; // ref",
+ " [style=dashed,color=forestgreen]; // const-ref",
+ " [style=dashed,color=violetred]; // writeOnly-ref",
+ " // call (hotness : Unknown)",
+ " [color=blue]; // call (hotness : Cold)",
+ " // call (hotness : None)",
+ " [color=brown]; // call (hotness : Hot)",
+ " [style=bold,color=red]; // call (hotness : Critical)"};
+
+ assert(static_cast<size_t>(TypeOrHotness) <
+ sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
+ OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
+ << EdgeAttrs[TypeOrHotness] << "\n";
+ };
+
+ OS << "digraph Summary {\n";
+ for (auto &ModIt : ModuleToDefinedGVS) {
+ auto ModId = getModuleId(ModIt.first);
+ OS << " // Module: " << ModIt.first << "\n";
+ OS << " subgraph cluster_" << std::to_string(ModId) << " {\n";
+ OS << " style = filled;\n";
+ OS << " color = lightgrey;\n";
+ OS << " label = \"" << sys::path::filename(ModIt.first) << "\";\n";
+ OS << " node [style=filled,fillcolor=lightblue];\n";
+
+ auto &GVSMap = ModIt.second;
+ auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
+ if (!GVSMap.count(IdTo)) {
+ CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
+ return;
+ }
+ DrawEdge(" ", ModId, IdFrom, ModId, IdTo, Hotness);
+ };
+
+ for (auto &SummaryIt : GVSMap) {
+ NodeMap[SummaryIt.first].push_back(ModId);
+ auto Flags = SummaryIt.second->flags();
+ Attributes A;
+ if (isa<FunctionSummary>(SummaryIt.second)) {
+ A.add("shape", "record", "function");
+ } else if (isa<AliasSummary>(SummaryIt.second)) {
+ A.add("style", "dotted,filled", "alias");
+ A.add("shape", "box");
+ } else {
+ A.add("shape", "Mrecord", "variable");
+ if (Flags.Live && hasReadOnlyFlag(SummaryIt.second))
+ A.addComment("immutable");
+ if (Flags.Live && hasWriteOnlyFlag(SummaryIt.second))
+ A.addComment("writeOnly");
+ }
+ if (Flags.DSOLocal)
+ A.addComment("dsoLocal");
+ if (Flags.CanAutoHide)
+ A.addComment("canAutoHide");
+
+ auto VI = getValueInfo(SummaryIt.first);
+ A.add("label", getNodeLabel(VI, SummaryIt.second));
+ if (!Flags.Live)
+ A.add("fillcolor", "red", "dead");
+ else if (Flags.NotEligibleToImport)
+ A.add("fillcolor", "yellow", "not eligible to import");
+
+ OS << " " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
+ << "\n";
+ }
+ OS << " // Edges:\n";
+
+ for (auto &SummaryIt : GVSMap) {
+ auto *GVS = SummaryIt.second;
+ for (auto &R : GVS->refs())
+ Draw(SummaryIt.first, R.getGUID(),
+ R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3));
+
+ if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
+ Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
+ continue;
+ }
+
+ if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
+ for (auto &CGEdge : FS->calls())
+ Draw(SummaryIt.first, CGEdge.first.getGUID(),
+ static_cast<int>(CGEdge.second.Hotness));
+ }
+ OS << " }\n";
+ }
+
+ OS << " // Cross-module edges:\n";
+ for (auto &E : CrossModuleEdges) {
+ auto &ModList = NodeMap[E.Dst];
+ if (ModList.empty()) {
+ defineExternalNode(OS, " ", getValueInfo(E.Dst), E.Dst);
+ // Add fake module to the list to draw an edge to an external node
+ // in the loop below.
+ ModList.push_back(-1);
+ }
+ for (auto DstMod : ModList)
+ // The edge representing call or ref is drawn to every module where target
+ // symbol is defined. When target is a linkonce symbol there can be
+ // multiple edges representing a single call or ref, both intra-module and
+ // cross-module. As we've already drawn all intra-module edges before we
+ // skip it here.
+ if (DstMod != E.SrcMod)
+ DrawEdge(" ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
+ }
+
+ OS << "}";
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 14:39:16 +0000