aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/CGData
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CGData')
-rw-r--r--llvm/lib/CGData/CMakeLists.txt2
-rw-r--r--llvm/lib/CGData/StableFunctionMap.cpp170
-rw-r--r--llvm/lib/CGData/StableFunctionMapRecord.cpp203
3 files changed, 375 insertions, 0 deletions
diff --git a/llvm/lib/CGData/CMakeLists.txt b/llvm/lib/CGData/CMakeLists.txt
index 157b0df..0031731 100644
--- a/llvm/lib/CGData/CMakeLists.txt
+++ b/llvm/lib/CGData/CMakeLists.txt
@@ -4,6 +4,8 @@ add_llvm_component_library(LLVMCGData
CodeGenDataWriter.cpp
OutlinedHashTree.cpp
OutlinedHashTreeRecord.cpp
+ StableFunctionMap.cpp
+ StableFunctionMapRecord.cpp
ADDITIONAL_HEADER_DIRS
${LLVM_MAIN_INCLUDE_DIR}/llvm/CGData
diff --git a/llvm/lib/CGData/StableFunctionMap.cpp b/llvm/lib/CGData/StableFunctionMap.cpp
new file mode 100644
index 0000000..638f92d
--- /dev/null
+++ b/llvm/lib/CGData/StableFunctionMap.cpp
@@ -0,0 +1,170 @@
+//===-- StableFunctionMap.cpp ---------------------------------------------===//
+//
+// 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 implements the functionality for the StableFunctionMap class, which
+// manages the mapping of stable function hashes to their metadata. It includes
+// methods for inserting, merging, and finalizing function entries, as well as
+// utilities for handling function names and IDs.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CGData/StableFunctionMap.h"
+
+#define DEBUG_TYPE "stable-function-map"
+
+using namespace llvm;
+
+unsigned StableFunctionMap::getIdOrCreateForName(StringRef Name) {
+ auto It = NameToId.find(Name);
+ if (It == NameToId.end()) {
+ unsigned Id = IdToName.size();
+ assert(Id == NameToId.size() && "ID collision");
+ IdToName.emplace_back(Name.str());
+ NameToId[IdToName.back()] = Id;
+ return Id;
+ } else {
+ return It->second;
+ }
+}
+
+std::optional<std::string> StableFunctionMap::getNameForId(unsigned Id) const {
+ if (Id >= IdToName.size())
+ return std::nullopt;
+ return IdToName[Id];
+}
+
+void StableFunctionMap::insert(const StableFunction &Func) {
+ assert(!Finalized && "Cannot insert after finalization");
+ auto FuncNameId = getIdOrCreateForName(Func.FunctionName);
+ auto ModuleNameId = getIdOrCreateForName(Func.ModuleName);
+ auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
+ for (auto &[Index, Hash] : Func.IndexOperandHashes)
+ (*IndexOperandHashMap)[Index] = Hash;
+ auto FuncEntry = std::make_unique<StableFunctionEntry>(
+ Func.Hash, FuncNameId, ModuleNameId, Func.InstCount,
+ std::move(IndexOperandHashMap));
+ insert(std::move(FuncEntry));
+}
+
+void StableFunctionMap::merge(const StableFunctionMap &OtherMap) {
+ assert(!Finalized && "Cannot merge after finalization");
+ for (auto &[Hash, Funcs] : OtherMap.HashToFuncs) {
+ auto &ThisFuncs = HashToFuncs[Hash];
+ for (auto &Func : Funcs) {
+ auto FuncNameId =
+ getIdOrCreateForName(*OtherMap.getNameForId(Func->FunctionNameId));
+ auto ModuleNameId =
+ getIdOrCreateForName(*OtherMap.getNameForId(Func->ModuleNameId));
+ auto ClonedIndexOperandHashMap =
+ std::make_unique<IndexOperandHashMapType>(*Func->IndexOperandHashMap);
+ ThisFuncs.emplace_back(std::make_unique<StableFunctionEntry>(
+ Func->Hash, FuncNameId, ModuleNameId, Func->InstCount,
+ std::move(ClonedIndexOperandHashMap)));
+ }
+ }
+}
+
+size_t StableFunctionMap::size(SizeType Type) const {
+ switch (Type) {
+ case UniqueHashCount:
+ return HashToFuncs.size();
+ case TotalFunctionCount: {
+ size_t Count = 0;
+ for (auto &Funcs : HashToFuncs)
+ Count += Funcs.second.size();
+ return Count;
+ }
+ case MergeableFunctionCount: {
+ size_t Count = 0;
+ for (auto &[Hash, Funcs] : HashToFuncs)
+ if (Funcs.size() >= 2)
+ Count += Funcs.size();
+ return Count;
+ }
+ }
+ return 0;
+}
+
+using ParamLocs = SmallVector<IndexPair>;
+static void removeIdenticalIndexPair(
+ SmallVector<std::unique_ptr<StableFunctionEntry>> &SFS) {
+ auto &RSF = SFS[0];
+ unsigned StableFunctionCount = SFS.size();
+
+ SmallVector<IndexPair> ToDelete;
+ for (auto &[Pair, Hash] : *(RSF->IndexOperandHashMap)) {
+ bool Identical = true;
+ for (unsigned J = 1; J < StableFunctionCount; ++J) {
+ auto &SF = SFS[J];
+ assert(SF->IndexOperandHashMap->count(Pair));
+ auto SHash = (*SF->IndexOperandHashMap)[Pair];
+ if (Hash != SHash) {
+ Identical = false;
+ break;
+ }
+ }
+
+ // No need to parameterize them if the hashes are identical across stable
+ // functions.
+ if (Identical)
+ ToDelete.emplace_back(Pair);
+ }
+
+ for (auto &Pair : ToDelete)
+ for (auto &SF : SFS)
+ SF->IndexOperandHashMap->erase(Pair);
+}
+
+void StableFunctionMap::finalize() {
+ Finalized = true;
+
+ for (auto It = HashToFuncs.begin(); It != HashToFuncs.end(); ++It) {
+ auto &[StableHash, SFS] = *It;
+
+ // Group stable functions by ModuleIdentifier.
+ std::stable_sort(SFS.begin(), SFS.end(),
+ [&](const std::unique_ptr<StableFunctionEntry> &L,
+ const std::unique_ptr<StableFunctionEntry> &R) {
+ return *getNameForId(L->ModuleNameId) <
+ *getNameForId(R->ModuleNameId);
+ });
+
+ // Consider the first function as the root function.
+ auto &RSF = SFS[0];
+
+ bool IsValid = true;
+ unsigned StableFunctionCount = SFS.size();
+ for (unsigned I = 1; I < StableFunctionCount; ++I) {
+ auto &SF = SFS[I];
+ assert(RSF->Hash == SF->Hash);
+ if (RSF->InstCount != SF->InstCount) {
+ IsValid = false;
+ break;
+ }
+ if (RSF->IndexOperandHashMap->size() != SF->IndexOperandHashMap->size()) {
+ IsValid = false;
+ break;
+ }
+ for (auto &P : *RSF->IndexOperandHashMap) {
+ auto &InstOpndIndex = P.first;
+ if (!SF->IndexOperandHashMap->count(InstOpndIndex)) {
+ IsValid = false;
+ break;
+ }
+ }
+ }
+ if (!IsValid) {
+ HashToFuncs.erase(It);
+ continue;
+ }
+
+ // Trim the index pair that has the same operand hash across
+ // stable functions.
+ removeIdenticalIndexPair(SFS);
+ }
+}
diff --git a/llvm/lib/CGData/StableFunctionMapRecord.cpp b/llvm/lib/CGData/StableFunctionMapRecord.cpp
new file mode 100644
index 0000000..05c96f8
--- /dev/null
+++ b/llvm/lib/CGData/StableFunctionMapRecord.cpp
@@ -0,0 +1,203 @@
+//===-- StableFunctionMapRecord.cpp ---------------------------------------===//
+//
+// 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 implements the functionality for the StableFunctionMapRecord class,
+// including methods for serialization and deserialization of stable function
+// maps to and from raw and YAML streams. It also includes utilities for
+// managing function entries and their metadata.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CGData/StableFunctionMapRecord.h"
+#include "llvm/Support/EndianStream.h"
+
+#define DEBUG_TYPE "stable-function-map-record"
+
+using namespace llvm;
+using namespace llvm::support;
+
+LLVM_YAML_IS_SEQUENCE_VECTOR(IndexPairHash)
+LLVM_YAML_IS_SEQUENCE_VECTOR(StableFunction)
+
+namespace llvm {
+namespace yaml {
+
+template <> struct MappingTraits<IndexPairHash> {
+ static void mapping(IO &IO, IndexPairHash &Key) {
+ IO.mapRequired("InstIndex", Key.first.first);
+ IO.mapRequired("OpndIndex", Key.first.second);
+ IO.mapRequired("OpndHash", Key.second);
+ }
+};
+
+template <> struct MappingTraits<StableFunction> {
+ static void mapping(IO &IO, StableFunction &Func) {
+ IO.mapRequired("Hash", Func.Hash);
+ IO.mapRequired("FunctionName", Func.FunctionName);
+ IO.mapRequired("ModuleName", Func.ModuleName);
+ IO.mapRequired("InstCount", Func.InstCount);
+ IO.mapRequired("IndexOperandHashes", Func.IndexOperandHashes);
+ }
+};
+
+} // namespace yaml
+} // namespace llvm
+
+// Get a sorted vector of StableFunctionEntry pointers.
+static SmallVector<const StableFunctionEntry *>
+getStableFunctionEntries(const StableFunctionMap &SFM) {
+ SmallVector<const StableFunctionEntry *> FuncEntries;
+ for (const auto &P : SFM.getFunctionMap())
+ for (auto &Func : P.second)
+ FuncEntries.emplace_back(Func.get());
+
+ std::stable_sort(
+ FuncEntries.begin(), FuncEntries.end(), [&](auto &A, auto &B) {
+ return std::tuple(A->Hash, SFM.getNameForId(A->ModuleNameId),
+ SFM.getNameForId(A->FunctionNameId)) <
+ std::tuple(B->Hash, SFM.getNameForId(B->ModuleNameId),
+ SFM.getNameForId(B->FunctionNameId));
+ });
+ return FuncEntries;
+}
+
+// Get a sorted vector of IndexOperandHashes.
+static IndexOperandHashVecType
+getStableIndexOperandHashes(const StableFunctionEntry *FuncEntry) {
+ IndexOperandHashVecType IndexOperandHashes;
+ for (auto &[Indices, OpndHash] : *FuncEntry->IndexOperandHashMap)
+ IndexOperandHashes.emplace_back(Indices, OpndHash);
+ std::sort(IndexOperandHashes.begin(), IndexOperandHashes.end(),
+ [](auto &A, auto &B) { return A.first < B.first; });
+ return IndexOperandHashes;
+}
+
+void StableFunctionMapRecord::serialize(raw_ostream &OS) const {
+ serialize(OS, FunctionMap.get());
+}
+
+void StableFunctionMapRecord::serialize(raw_ostream &OS,
+ const StableFunctionMap *FunctionMap) {
+ support::endian::Writer Writer(OS, endianness::little);
+
+ // Write Names.
+ auto &Names = FunctionMap->getNames();
+ uint32_t ByteSize = 4;
+ Writer.write<uint32_t>(Names.size());
+ for (auto &Name : Names) {
+ Writer.OS << Name << '\0';
+ ByteSize += Name.size() + 1;
+ }
+ // Align ByteSize to 4 bytes.
+ uint32_t Padding = offsetToAlignment(ByteSize, Align(4));
+ for (uint32_t I = 0; I < Padding; ++I)
+ Writer.OS << '\0';
+
+ // Write StableFunctionEntries whose pointers are sorted.
+ auto FuncEntries = getStableFunctionEntries(*FunctionMap);
+ Writer.write<uint32_t>(FuncEntries.size());
+
+ for (const auto *FuncRef : FuncEntries) {
+ Writer.write<stable_hash>(FuncRef->Hash);
+ Writer.write<uint32_t>(FuncRef->FunctionNameId);
+ Writer.write<uint32_t>(FuncRef->ModuleNameId);
+ Writer.write<uint32_t>(FuncRef->InstCount);
+
+ // Emit IndexOperandHashes sorted from IndexOperandHashMap.
+ IndexOperandHashVecType IndexOperandHashes =
+ getStableIndexOperandHashes(FuncRef);
+ Writer.write<uint32_t>(IndexOperandHashes.size());
+ for (auto &IndexOperandHash : IndexOperandHashes) {
+ Writer.write<uint32_t>(IndexOperandHash.first.first);
+ Writer.write<uint32_t>(IndexOperandHash.first.second);
+ Writer.write<stable_hash>(IndexOperandHash.second);
+ }
+ }
+}
+
+void StableFunctionMapRecord::deserialize(const unsigned char *&Ptr) {
+ // Assert that Ptr is 4-byte aligned
+ assert(((uintptr_t)Ptr % 4) == 0);
+ // Read Names.
+ auto NumNames =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ // Early exit if there is no name.
+ if (NumNames == 0)
+ return;
+ for (unsigned I = 0; I < NumNames; ++I) {
+ std::string Name(reinterpret_cast<const char *>(Ptr));
+ Ptr += Name.size() + 1;
+ FunctionMap->getIdOrCreateForName(Name);
+ }
+ // Align Ptr to 4 bytes.
+ Ptr = reinterpret_cast<const uint8_t *>(alignAddr(Ptr, Align(4)));
+
+ // Read StableFunctionEntries.
+ auto NumFuncs =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ for (unsigned I = 0; I < NumFuncs; ++I) {
+ auto Hash =
+ endian::readNext<stable_hash, endianness::little, unaligned>(Ptr);
+ auto FunctionNameId =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ assert(FunctionMap->getNameForId(FunctionNameId) &&
+ "FunctionNameId out of range");
+ auto ModuleNameId =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ assert(FunctionMap->getNameForId(ModuleNameId) &&
+ "ModuleNameId out of range");
+ auto InstCount =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+
+ // Read IndexOperandHashes to build IndexOperandHashMap
+ auto NumIndexOperandHashes =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
+ for (unsigned J = 0; J < NumIndexOperandHashes; ++J) {
+ auto InstIndex =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ auto OpndIndex =
+ endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
+ auto OpndHash =
+ endian::readNext<stable_hash, endianness::little, unaligned>(Ptr);
+ assert(InstIndex < InstCount && "InstIndex out of range");
+
+ auto Indices = std::make_pair(InstIndex, OpndIndex);
+ (*IndexOperandHashMap)[Indices] = OpndHash;
+ }
+
+ // Insert a new StableFunctionEntry into the map.
+ auto FuncEntry = std::make_unique<StableFunctionEntry>(
+ Hash, FunctionNameId, ModuleNameId, InstCount,
+ std::move(IndexOperandHashMap));
+
+ FunctionMap->insert(std::move(FuncEntry));
+ }
+}
+
+void StableFunctionMapRecord::serializeYAML(yaml::Output &YOS) const {
+ auto FuncEntries = getStableFunctionEntries(*FunctionMap);
+ SmallVector<StableFunction> Functions;
+ for (const auto *FuncEntry : FuncEntries) {
+ auto IndexOperandHashes = getStableIndexOperandHashes(FuncEntry);
+ Functions.emplace_back(
+ FuncEntry->Hash, *FunctionMap->getNameForId(FuncEntry->FunctionNameId),
+ *FunctionMap->getNameForId(FuncEntry->ModuleNameId),
+ FuncEntry->InstCount, std::move(IndexOperandHashes));
+ }
+
+ YOS << Functions;
+}
+
+void StableFunctionMapRecord::deserializeYAML(yaml::Input &YIS) {
+ std::vector<StableFunction> Funcs;
+ YIS >> Funcs;
+ for (auto &Func : Funcs)
+ FunctionMap->insert(Func);
+ YIS.nextDocument();
+}
generated by cgit v1.1 at 2025-09-28 01:27:40 +0000