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
16#include "llvm/CGData/OutlinedHashTreeRecord.h"
17#include "llvm/ObjectYAML/YAML.h"
18#include "llvm/Support/Endian.h"
19#include "llvm/Support/EndianStream.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(Key: "Hash", Val&: res.Hash);
32 io.mapRequired(Key: "Terminals", Val&: res.Terminals);
33 io.mapRequired(Key: "SuccessorIds", Val&: 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: Key.str().c_str(), Val&: NodeStable);
41 unsigned Id;
42 if (Key.getAsInteger(Radix: 0, Result&: Id)) {
43 io.setError("Id not an integer");
44 return;
45 }
46 V.insert(x: {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(Key: utostr(X: Iter->first).c_str(), Val&: Iter->second);
52 }
53};
54
55} // namespace yaml
56} // namespace llvm
57
58void OutlinedHashTreeRecord::serialize(raw_ostream &OS) const {
59 IdHashNodeStableMapTy IdNodeStableMap;
60 convertToStableData(IdNodeStableMap);
61 support::endian::Writer Writer(OS, endianness::little);
62 Writer.write<uint32_t>(Val: IdNodeStableMap.size());
63
64 for (const auto &[Id, NodeStable] : IdNodeStableMap) {
65 Writer.write<uint32_t>(Val: Id);
66 Writer.write<uint64_t>(Val: NodeStable.Hash);
67 Writer.write<uint32_t>(Val: NodeStable.Terminals);
68 Writer.write<uint32_t>(Val: NodeStable.SuccessorIds.size());
69 for (auto SuccessorId : NodeStable.SuccessorIds)
70 Writer.write<uint32_t>(Val: 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>(memory&: Ptr);
78
79 for (unsigned I = 0; I < NumIdNodeStableMap; ++I) {
80 auto Id = endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
81 HashNodeStable NodeStable;
82 NodeStable.Hash =
83 endian::readNext<uint64_t, endianness::little, unaligned>(memory&: Ptr);
84 NodeStable.Terminals =
85 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
86 auto NumSuccessorIds =
87 endian::readNext<uint32_t, endianness::little, unaligned>(memory&: Ptr);
88 for (unsigned J = 0; J < NumSuccessorIds; ++J)
89 NodeStable.SuccessorIds.push_back(
90 x: endian::readNext<uint32_t, endianness::little, unaligned>(memory&: 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
105void OutlinedHashTreeRecord::deserializeYAML(yaml::Input &YIS) {
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 CallbackNode: [&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=*/CallbackEdge: nullptr, /*SortedWork=*/SortedWalk: 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.value_or(u: 0);
134 for (auto &P : Node->Successors)
135 NodeStable.SuccessorIds.push_back(x: 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(C&: 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(k: SuccessorId).Hash;
165 Successors[Hash] = std::move(Sucessor);
166 }
167 }
168}
169