LLVM 20.0.0git
OutlinedHashTreeRecord.cpp
Go to the documentation of this file.
1//===-- OutlinedHashTreeRecord.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 defines the OutlinedHashTreeRecord class. This class holds the outlined
10// hash tree for both serialization and deserialization processes. It utilizes
11// two data formats for serialization: raw binary data and YAML.
12// These two formats can be used interchangeably.
13//
14//===----------------------------------------------------------------------===//
15
18#include "llvm/Support/Endian.h"
20
21#define DEBUG_TYPE "outlined-hash-tree"
22
23using namespace llvm;
24using namespace llvm::support;
25
26namespace llvm {
27namespace yaml {
28
29template <> struct MappingTraits<HashNodeStable> {
30 static void mapping(IO &io, HashNodeStable &res) {
31 io.mapRequired("Hash", res.Hash);
32 io.mapRequired("Terminals", res.Terminals);
33 io.mapRequired("SuccessorIds", res.SuccessorIds);
34 }
35};
36
37template <> struct CustomMappingTraits<IdHashNodeStableMapTy> {
38 static void inputOne(IO &io, StringRef Key, IdHashNodeStableMapTy &V) {
39 HashNodeStable NodeStable;
40 io.mapRequired(Key.str().c_str(), NodeStable);
41 unsigned Id;
42 if (Key.getAsInteger(0, Id)) {
43 io.setError("Id not an integer");
44 return;
45 }
46 V.insert({Id, NodeStable});
47 }
48
49 static void output(IO &io, IdHashNodeStableMapTy &V) {
50 for (auto Iter = V.begin(); Iter != V.end(); ++Iter)
51 io.mapRequired(utostr(Iter->first).c_str(), Iter->second);
52 }
53};
54
55} // namespace yaml
56} // namespace llvm
57
59 IdHashNodeStableMapTy IdNodeStableMap;
60 convertToStableData(IdNodeStableMap);
62 Writer.write<uint32_t>(IdNodeStableMap.size());
63
64 for (const auto &[Id, NodeStable] : IdNodeStableMap) {
65 Writer.write<uint32_t>(Id);
66 Writer.write<uint64_t>(NodeStable.Hash);
67 Writer.write<uint32_t>(NodeStable.Terminals);
68 Writer.write<uint32_t>(NodeStable.SuccessorIds.size());
69 for (auto SuccessorId : NodeStable.SuccessorIds)
70 Writer.write<uint32_t>(SuccessorId);
71 }
72}
73
74void OutlinedHashTreeRecord::deserialize(const unsigned char *&Ptr) {
75 IdHashNodeStableMapTy IdNodeStableMap;
76 auto NumIdNodeStableMap =
77 endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
78
79 for (unsigned I = 0; I < NumIdNodeStableMap; ++I) {
80 auto Id = endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
81 HashNodeStable NodeStable;
82 NodeStable.Hash =
83 endian::readNext<uint64_t, endianness::little, unaligned>(Ptr);
84 NodeStable.Terminals =
85 endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
86 auto NumSuccessorIds =
87 endian::readNext<uint32_t, endianness::little, unaligned>(Ptr);
88 for (unsigned J = 0; J < NumSuccessorIds; ++J)
89 NodeStable.SuccessorIds.push_back(
90 endian::readNext<uint32_t, endianness::little, unaligned>(Ptr));
91
92 IdNodeStableMap[Id] = std::move(NodeStable);
93 }
94
95 convertFromStableData(IdNodeStableMap);
96}
97
98void OutlinedHashTreeRecord::serializeYAML(yaml::Output &YOS) const {
99 IdHashNodeStableMapTy IdNodeStableMap;
100 convertToStableData(IdNodeStableMap);
101
102 YOS << IdNodeStableMap;
103}
104
106 IdHashNodeStableMapTy IdNodeStableMap;
107
108 YIS >> IdNodeStableMap;
109 YIS.nextDocument();
110
111 convertFromStableData(IdNodeStableMap);
112}
113
114void OutlinedHashTreeRecord::convertToStableData(
115 IdHashNodeStableMapTy &IdNodeStableMap) const {
116 // Build NodeIdMap
117 HashNodeIdMapTy NodeIdMap;
118 HashTree->walkGraph(
119 [&NodeIdMap](const HashNode *Current) {
120 size_t Index = NodeIdMap.size();
121 NodeIdMap[Current] = Index;
122 assert((Index + 1 == NodeIdMap.size()) &&
123 "Duplicate key in NodeIdMap: 'Current' should be unique.");
124 },
125 /*EdgeCallbackFn=*/nullptr, /*SortedWork=*/true);
126
127 // Convert NodeIdMap to NodeStableMap
128 for (auto &P : NodeIdMap) {
129 auto *Node = P.first;
130 auto Id = P.second;
131 HashNodeStable NodeStable;
132 NodeStable.Hash = Node->Hash;
133 NodeStable.Terminals = Node->Terminals ? *Node->Terminals : 0;
134 for (auto &P : Node->Successors)
135 NodeStable.SuccessorIds.push_back(NodeIdMap[P.second.get()]);
136 IdNodeStableMap[Id] = NodeStable;
137 }
138
139 // Sort the Successors so that they come out in the same order as in the map.
140 for (auto &P : IdNodeStableMap)
141 llvm::sort(P.second.SuccessorIds);
142}
143
144void OutlinedHashTreeRecord::convertFromStableData(
145 const IdHashNodeStableMapTy &IdNodeStableMap) {
146 IdHashNodeMapTy IdNodeMap;
147 // Initialize the root node at 0.
148 IdNodeMap[0] = HashTree->getRoot();
149 assert(IdNodeMap[0]->Successors.empty());
150
151 for (auto &P : IdNodeStableMap) {
152 auto Id = P.first;
153 const HashNodeStable &NodeStable = P.second;
154 assert(IdNodeMap.count(Id));
155 HashNode *Curr = IdNodeMap[Id];
156 Curr->Hash = NodeStable.Hash;
157 if (NodeStable.Terminals)
158 Curr->Terminals = NodeStable.Terminals;
159 auto &Successors = Curr->Successors;
160 assert(Successors.empty());
161 for (auto SuccessorId : NodeStable.SuccessorIds) {
162 auto Sucessor = std::make_unique<HashNode>();
163 IdNodeMap[SuccessorId] = Sucessor.get();
164 auto Hash = IdNodeStableMap.at(SuccessorId).Hash;
165 Successors[Hash] = std::move(Sucessor);
166 }
167 }
168}
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
unsigned size() const
Definition: DenseMap.h:99
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
Definition: DenseMap.h:202
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
std::map< unsigned, HashNodeStable > IdHashNodeStableMapTy
HashNodeStable is the serialized, stable, and compact representation of a HashNode.
std::vector< unsigned > SuccessorIds
A HashNode is an entry in an OutlinedHashTree, holding a hash value and a collection of Successors (o...
std::unordered_map< stable_hash, std::unique_ptr< HashNode > > Successors
The successors of this node.
std::optional< unsigned > Terminals
The number of terminals in the sequence ending at this node.
stable_hash Hash
The hash value of the node.
void serializeYAML(yaml::Output &YOS) const
Serialize the outlined hash tree to a YAML stream.
void deserializeYAML(yaml::Input &YIS)
Deserialize the outlined hash tree from a YAML stream.
void deserialize(const unsigned char *&Ptr)
Deserialize the outlined hash tree from a raw_ostream.
void serialize(raw_ostream &OS) const
Serialize the outlined hash tree to a raw_ostream.
std::unique_ptr< OutlinedHashTree > HashTree
Adapter to write values to a stream in a particular byte order.
Definition: EndianStream.h:67
void write(ArrayRef< value_type > Val)
Definition: EndianStream.h:71
static void output(IO &io, IdHashNodeStableMapTy &V)
static void inputOne(IO &io, StringRef Key, IdHashNodeStableMapTy &V)
static void mapping(IO &io, HashNodeStable &res)