1//===-- StableFunctionMapRecord.cpp ---------------------------------------===//
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 implements the functionality for the StableFunctionMapRecord class,
10// including methods for serialization and deserialization of stable function
11// maps to and from raw and YAML streams. It also includes utilities for
12// managing function entries and their metadata.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/CGData/StableFunctionMapRecord.h"
17#include "llvm/Support/EndianStream.h"
18
19#define DEBUG_TYPE "stable-function-map-record"
20
21using namespace llvm;
22using namespace llvm::support;
23
24LLVM_YAML_IS_SEQUENCE_VECTOR(IndexPairHash)
25LLVM_YAML_IS_SEQUENCE_VECTOR(StableFunction)
26
27namespace llvm {
28namespace yaml {
29
30template <> struct MappingTraits<IndexPairHash> {
31 static void mapping(IO &IO, IndexPairHash &Key) {
32 IO.mapRequired(Key: "InstIndex", Val&: Key.first.first);
33 IO.mapRequired(Key: "OpndIndex", Val&: Key.first.second);
34 IO.mapRequired(Key: "OpndHash", Val&: Key.second);
35 }
36};
37
38template <> struct MappingTraits<StableFunction> {
39 static void mapping(IO &IO, StableFunction &Func) {
40 IO.mapRequired(Key: "Hash", Val&: Func.Hash);
41 IO.mapRequired(Key: "FunctionName", Val&: Func.FunctionName);
42 IO.mapRequired(Key: "ModuleName", Val&: Func.ModuleName);
43 IO.mapRequired(Key: "InstCount", Val&: Func.InstCount);
44 IO.mapRequired(Key: "IndexOperandHashes", Val&: Func.IndexOperandHashes);
45 }
46};
47
48} // namespace yaml
49} // namespace llvm
50
51// Get a sorted vector of StableFunctionEntry pointers.
52static SmallVector<const StableFunctionMap::StableFunctionEntry *>
53getStableFunctionEntries(const StableFunctionMap &SFM) {
54 SmallVector<const StableFunctionMap::StableFunctionEntry *> FuncEntries;
55 for (const auto &P : SFM.getFunctionMap())
56 for (auto &Func : P.second.Entries)
57 FuncEntries.emplace_back(Args: Func.get());
58
59 llvm::stable_sort(
60 Range&: FuncEntries, C: [&](auto &A, auto &B) {
61 return std::tuple(A->Hash, SFM.getNameForId(Id: A->ModuleNameId),
62 SFM.getNameForId(Id: A->FunctionNameId)) <
63 std::tuple(B->Hash, SFM.getNameForId(Id: B->ModuleNameId),
64 SFM.getNameForId(Id: B->FunctionNameId));
65 });
66 return FuncEntries;
67}
68
69// Get a sorted vector of IndexOperandHashes.
70static IndexOperandHashVecType getStableIndexOperandHashes(
71 const StableFunctionMap::StableFunctionEntry *FuncEntry) {
72 IndexOperandHashVecType IndexOperandHashes;
73 for (auto &[Indices, OpndHash] : *FuncEntry->IndexOperandHashMap)
74 IndexOperandHashes.emplace_back(Args&: Indices, Args&: OpndHash);
75 // The indices are unique, so we can just sort by the first.
76 llvm::sort(C&: IndexOperandHashes);
77 return IndexOperandHashes;
78}
79
80void StableFunctionMapRecord::serialize(
81 raw_ostream &OS, std::vector<CGDataPatchItem> &PatchItems) const {
82 serialize(OS, FunctionMap: FunctionMap.get(), PatchItems);
83}
84
85void StableFunctionMapRecord::serialize(
86 raw_ostream &OS, const StableFunctionMap *FunctionMap,
87 std::vector<CGDataPatchItem> &PatchItems) {
88 support::endian::Writer Writer(OS, endianness::little);
89
90 // Write Names.
91 ArrayRef<std::string> Names = FunctionMap->getNames();
92 Writer.write<uint32_t>(Val: Names.size());
93 // Remember the position, write back the total size of Names, so we can skip
94 // reading them if needed.
95 const uint64_t NamesByteSizeOffset = Writer.OS.tell();
96 Writer.write<uint64_t>(Val: 0);
97 for (auto &Name : Names)
98 Writer.OS << Name << '\0';
99 // Align current position to 4 bytes.
100 uint32_t Padding = offsetToAlignment(Value: Writer.OS.tell(), Alignment: Align(4));
101 for (uint32_t I = 0; I < Padding; ++I)
102 Writer.OS << '\0';
103 const auto NamesByteSize =
104 Writer.OS.tell() - NamesByteSizeOffset - sizeof(NamesByteSizeOffset);
105 PatchItems.emplace_back(args: NamesByteSizeOffset, args: &NamesByteSize, args: 1);
106
107 // Write StableFunctionEntries whose pointers are sorted.
108 auto FuncEntries = getStableFunctionEntries(SFM: *FunctionMap);
109 Writer.write<uint32_t>(Val: FuncEntries.size());
110 for (const auto *FuncRef : FuncEntries)
111 Writer.write<stable_hash>(Val: FuncRef->Hash);
112 std::vector<uint64_t> IndexOperandHashesOffsets;
113 IndexOperandHashesOffsets.reserve(n: FuncEntries.size());
114 for (const auto *FuncRef : FuncEntries) {
115 Writer.write<uint32_t>(Val: FuncRef->FunctionNameId);
116 Writer.write<uint32_t>(Val: FuncRef->ModuleNameId);
117 Writer.write<uint32_t>(Val: FuncRef->InstCount);
118 const uint64_t Offset = Writer.OS.tell();
119 IndexOperandHashesOffsets.push_back(x: Offset);
120 Writer.write<uint64_t>(Val: 0);
121 }
122 const uint64_t IndexOperandHashesByteSizeOffset = Writer.OS.tell();
123 Writer.write<uint64_t>(Val: 0);
124 for (size_t I = 0; I < FuncEntries.size(); ++I) {
125 const uint64_t Offset = Writer.OS.tell() - IndexOperandHashesOffsets[I];
126 PatchItems.emplace_back(args&: IndexOperandHashesOffsets[I], args: &Offset, args: 1);
127 // Emit IndexOperandHashes sorted from IndexOperandHashMap.
128 const auto *FuncRef = FuncEntries[I];
129 IndexOperandHashVecType IndexOperandHashes =
130 getStableIndexOperandHashes(FuncEntry: FuncRef);
131 Writer.write<uint32_t>(Val: IndexOperandHashes.size());
132 for (auto &IndexOperandHash : IndexOperandHashes) {
133 Writer.write<uint32_t>(Val: IndexOperandHash.first.first);
134 Writer.write<uint32_t>(Val: IndexOperandHash.first.second);
135 Writer.write<stable_hash>(Val: IndexOperandHash.second);
136 }
137 }
138 // Write the total size of IndexOperandHashes.
139 const uint64_t IndexOperandHashesByteSize =
140 Writer.OS.tell() - IndexOperandHashesByteSizeOffset - sizeof(uint64_t);
141 PatchItems.emplace_back(args: IndexOperandHashesByteSizeOffset,
142 args: &IndexOperandHashesByteSize, args: 1);
143}
144
145void StableFunctionMapRecord::deserializeEntry(const unsigned char *Ptr,
146 stable_hash Hash,
147 StableFunctionMap *FunctionMap) {
148 auto FunctionNameId =
149 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
150 if (FunctionMap->ReadStableFunctionMapNames)
151 assert(FunctionMap->getNameForId(FunctionNameId) &&
152 "FunctionNameId out of range");
153 auto ModuleNameId =
154 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
155 if (FunctionMap->ReadStableFunctionMapNames)
156 assert(FunctionMap->getNameForId(ModuleNameId) &&
157 "ModuleNameId out of range");
158 auto InstCount =
159 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
160
161 // Read IndexOperandHashes to build IndexOperandHashMap
162 auto CurrentPosition = reinterpret_cast<uintptr_t>(Ptr);
163 auto IndexOperandHashesOffset =
164 endian::readNext<uint64_t, endianness::little, unaligned>(memory&: Ptr);
165 auto *IndexOperandHashesPtr = reinterpret_cast<const unsigned char *>(
166 CurrentPosition + IndexOperandHashesOffset);
167 auto NumIndexOperandHashes =
168 endian::readNext<uint32_t, endianness::little, unaligned>(
169 memory&: IndexOperandHashesPtr);
170 auto IndexOperandHashMap = std::make_unique<IndexOperandHashMapType>();
171 for (unsigned J = 0; J < NumIndexOperandHashes; ++J) {
172 auto InstIndex = endian::readNext<uint32_t, endianness::little, unaligned>(
173 memory&: IndexOperandHashesPtr);
174 auto OpndIndex = endian::readNext<uint32_t, endianness::little, unaligned>(
175 memory&: IndexOperandHashesPtr);
176 auto OpndHash =
177 endian::readNext<stable_hash, endianness::little, unaligned>(
178 memory&: IndexOperandHashesPtr);
179 assert(InstIndex < InstCount && "InstIndex out of range");
180
181 IndexOperandHashMap->try_emplace(Key: {InstIndex, OpndIndex}, Args&: OpndHash);
182 }
183
184 // Insert a new StableFunctionEntry into the map.
185 auto FuncEntry = std::make_unique<StableFunctionMap::StableFunctionEntry>(
186 args&: Hash, args&: FunctionNameId, args&: ModuleNameId, args&: InstCount,
187 args: std::move(IndexOperandHashMap));
188
189 FunctionMap->insert(FuncEntry: std::move(FuncEntry));
190}
191
192void StableFunctionMapRecord::deserialize(const unsigned char *&Ptr,
193 bool Lazy) {
194 // Assert that Ptr is 4-byte aligned
195 assert(((uintptr_t)Ptr % 4) == 0);
196 // Read Names.
197 auto NumNames =
198 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
199 // Early exit if there is no name.
200 if (NumNames == 0)
201 return;
202 const auto NamesByteSize =
203 endian::readNext<uint64_t, endianness::little, unaligned>(memory&: Ptr);
204 const auto NamesOffset = reinterpret_cast<uintptr_t>(Ptr);
205 if (FunctionMap->ReadStableFunctionMapNames) {
206 for (unsigned I = 0; I < NumNames; ++I) {
207 StringRef Name(reinterpret_cast<const char *>(Ptr));
208 Ptr += Name.size() + 1;
209 FunctionMap->getIdOrCreateForName(Name);
210 }
211 // Align Ptr to 4 bytes.
212 Ptr = reinterpret_cast<const uint8_t *>(alignAddr(Addr: Ptr, Alignment: Align(4)));
213 assert(reinterpret_cast<uintptr_t>(Ptr) - NamesOffset == NamesByteSize &&
214 "NamesByteSize does not match the actual size of names");
215 } else {
216 // skip reading Names by advancing the pointer.
217 Ptr = reinterpret_cast<const uint8_t *>(NamesOffset + NamesByteSize);
218 }
219
220 // Read StableFunctionEntries.
221 auto NumFuncs =
222 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
223 auto FixedSizeFieldsOffset =
224 reinterpret_cast<uintptr_t>(Ptr) + NumFuncs * sizeof(stable_hash);
225 constexpr uint32_t FixedSizeFieldsSizePerEntry =
226 // FunctionNameId
227 sizeof(uint32_t) +
228 // ModuleNameId
229 sizeof(uint32_t) +
230 // InstCount
231 sizeof(uint32_t) +
232 // Relative offset to IndexOperandHashes
233 sizeof(uint64_t);
234 for (unsigned I = 0; I < NumFuncs; ++I) {
235 auto Hash =
236 endian::readNext<stable_hash, endianness::little, unaligned>(memory&: Ptr);
237 if (Lazy) {
238 auto It = FunctionMap->HashToFuncs.try_emplace(k: Hash).first;
239 StableFunctionMap::EntryStorage &Storage = It->second;
240 Storage.Offsets.push_back(Elt: FixedSizeFieldsOffset);
241 } else {
242 deserializeEntry(
243 Ptr: reinterpret_cast<const unsigned char *>(FixedSizeFieldsOffset), Hash,
244 FunctionMap: FunctionMap.get());
245 }
246 FixedSizeFieldsOffset += FixedSizeFieldsSizePerEntry;
247 }
248
249 // Update Ptr to the end of the serialized map to meet the expectation of
250 // CodeGenDataReader.
251 Ptr = reinterpret_cast<const unsigned char *>(FixedSizeFieldsOffset);
252 auto IndexOperandHashesByteSize =
253 endian::readNext<uint64_t, endianness::little, unaligned>(memory&: Ptr);
254 Ptr = reinterpret_cast<const unsigned char *>(
255 reinterpret_cast<uintptr_t>(Ptr) + IndexOperandHashesByteSize);
256}
257
258void StableFunctionMapRecord::deserialize(const unsigned char *&Ptr) {
259 deserialize(Ptr, /*Lazy=*/false);
260}
261
262void StableFunctionMapRecord::lazyDeserialize(
263 std::shared_ptr<MemoryBuffer> Buffer, uint64_t Offset) {
264 const auto *Ptr = reinterpret_cast<const unsigned char *>(
265 reinterpret_cast<uintptr_t>(Buffer->getBufferStart()) + Offset);
266 deserialize(Ptr, /*Lazy=*/true);
267 FunctionMap->Buffer = std::move(Buffer);
268}
269
270void StableFunctionMapRecord::serializeYAML(yaml::Output &YOS) const {
271 auto FuncEntries = getStableFunctionEntries(SFM: *FunctionMap);
272 SmallVector<StableFunction> Functions;
273 for (const auto *FuncEntry : FuncEntries) {
274 auto IndexOperandHashes = getStableIndexOperandHashes(FuncEntry);
275 Functions.emplace_back(
276 Args: FuncEntry->Hash, Args: *FunctionMap->getNameForId(Id: FuncEntry->FunctionNameId),
277 Args: *FunctionMap->getNameForId(Id: FuncEntry->ModuleNameId),
278 Args: FuncEntry->InstCount, Args: std::move(IndexOperandHashes));
279 }
280
281 YOS << Functions;
282}
283
284void StableFunctionMapRecord::deserializeYAML(yaml::Input &YIS) {
285 std::vector<StableFunction> Funcs;
286 YIS >> Funcs;
287 for (auto &Func : Funcs)
288 FunctionMap->insert(Func);
289 YIS.nextDocument();
290}
291