CbC/CbC_llvm: lib/IR/ModuleSummaryIndex.cpp comparison

comparison lib/IR/ModuleSummaryIndex.cpp @ 148:63bd29f05246

merged

author	Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date	Wed, 14 Aug 2019 19:46:37 +0900
parents	c2174574ed3a
children

comparison

equal deleted inserted replaced

-:3fc4d5c3e21e
+:63bd29f05246
 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
 //
-//                     The LLVM Compiler Infrastructure
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-//
+// See https://llvm.org/LICENSE.txt for license information.
-// This file is distributed under the University of Illinois Open Source
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // 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(
 GVSummaryMap[GUID] = Summary;
 }
 }
 }
-// Collect for each module the list of function it defines (GUID -> Summary).
-void ModuleSummaryIndex::collectDefinedGVSummariesPerModule(
-StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const {
-for (auto &GlobalList : *this) {
-auto GUID = GlobalList.first;
-for (auto &Summary : GlobalList.second.SummaryList) {
-ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
-}
-}
-}
 GlobalValueSummary *
 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
 bool PerModuleIndex) const {
 auto VI = getValueInfo(ValueGUID);
 assert(VI && "GlobalValue not found in index");
 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;
 };
 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 += ", ";
 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),
+char FlagRep[] = {FlagValue(F.ReadNone),     FlagValue(F.ReadOnly),
-FlagValue(F.NoRecurse), FlagValue(F.ReturnDoesNotAlias), 0};
+FlagValue(F.NoRecurse),    FlagValue(F.ReturnDoesNotAlias),
+FlagValue(F.NoInline), 0};
 return FlagRep;
 }
 // Get string representation of function instruction count and flags.
 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() ? std::string("@") + std::to_string(VI.getGUID())
+return VI.name().empty() ? getNodeVisualName(VI.getGUID()) : VI.name().str();
-: VI.name().str();
 }
 static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
 if (isa<AliasSummary>(GVS))
 return getNodeVisualName(VI);
 // 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) {
+const ValueInfo &VI, GlobalValue::GUID Id) {
-auto StrId = std::to_string(VI.getGUID());
+auto StrId = std::to_string(Id);
-OS << "  " << StrId << " [label=\"" << getNodeVisualName(VI)
+OS << "  " << StrId << " [label=\"";
-<< "\"]; // defined externally\n";
-}
+if (VI) {
+OS << getNodeVisualName(VI);
-void ModuleSummaryIndex::exportToDot(raw_ostream& OS) const {
+} 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;
-StringMap<GVSummaryMapTy> ModuleToDefinedGVS;
+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, int SrcMod, GlobalValue::GUID SrcId,
+auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
-int DstMod, GlobalValue::GUID DstId, int TypeOrHotness) {
+uint64_t DstMod, GlobalValue::GUID DstId,
-// 0 corresponds to alias edge, 1 to ref edge, 2 to call with unknown
+int TypeOrHotness) {
-// hotness, ...
+// 0 - alias
-TypeOrHotness += 2;
+// 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)"};
 << EdgeAttrs[TypeOrHotness] << "\n";
 };
 OS << "digraph Summary {\n";
 for (auto &ModIt : ModuleToDefinedGVS) {
-auto ModId = getModuleId(ModIt.first());
+auto ModId = getModuleId(ModIt.first);
-OS << "  // Module: " << ModIt.first() << "\n";
+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 << "    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)) {
 } 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");
 OS << "    // Edges:\n";
 for (auto &SummaryIt : GVSMap) {
 auto *GVS = SummaryIt.second;
 for (auto &R : GVS->refs())
-Draw(SummaryIt.first, R.getGUID(), -1);
+Draw(SummaryIt.first, R.getGUID(),
+R.isWriteOnly() ? -1 : (R.isReadOnly() ? -2 : -3));
 if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
-auto AliaseeOrigId = AS->getAliasee().getOriginalName();
+Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
-auto AliaseeId = getGUIDFromOriginalID(AliaseeOrigId);
-Draw(SummaryIt.first, AliaseeId ? AliaseeId : AliaseeOrigId, -2);
 continue;
 }
 if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
 for (auto &CGEdge : FS->calls())
 OS << "  // Cross-module edges:\n";
 for (auto &E : CrossModuleEdges) {
 auto &ModList = NodeMap[E.Dst];
 if (ModList.empty()) {
-defineExternalNode(OS, "  ", getValueInfo(E.Dst));
+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)

Mercurial > hg > CbC > CbC_llvm

comparison lib/IR/ModuleSummaryIndex.cpp @ 148:63bd29f05246