1//===----------------------------------------------------------------------===//
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#include "DecoderTableEmitter.h"
10#include "llvm/ADT/StringExtras.h"
11#include "llvm/Support/Format.h"
12#include "llvm/Support/LEB128.h"
13
14using namespace llvm;
15
16unsigned
17DecoderTableEmitter::computeNodeSize(const DecoderTreeNode *Node) const {
18 // To make the arithmetic below clearer.
19 static constexpr unsigned OpcodeSize = 1;
20 static constexpr unsigned FieldWidthSize = 1;
21
22 switch (Node->getKind()) {
23 case DecoderTreeNode::CheckAny: {
24 const auto *N = static_cast<const CheckAnyNode *>(Node);
25 // Pretend the node was optimized. See the comment in emitCheckAnyNode.
26 if (range_size(Range: N->children()) == 1)
27 return computeNodeSize(Node: *N->child_begin());
28 unsigned Size = 0;
29 // All children except the last one are preceded by OPC_Scope opcode and
30 // the size of the child.
31 for (const DecoderTreeNode *Child : drop_end(RangeOrContainer: N->children())) {
32 unsigned ChildSize = computeNodeSize(Node: Child);
33 Size += OpcodeSize + getULEB128Size(Value: ChildSize) + ChildSize;
34 }
35 const DecoderTreeNode *Child = *std::prev(x: N->child_end());
36 return Size + computeNodeSize(Node: Child);
37 }
38 case DecoderTreeNode::CheckAll: {
39 const auto *N = static_cast<const CheckAllNode *>(Node);
40 unsigned Size = 0;
41 for (const DecoderTreeNode *Child : N->children())
42 Size += computeNodeSize(Node: Child);
43 return Size;
44 }
45 case DecoderTreeNode::CheckField: {
46 const auto *N = static_cast<const CheckFieldNode *>(Node);
47 return OpcodeSize + getULEB128Size(Value: N->getStartBit()) + FieldWidthSize +
48 getULEB128Size(Value: N->getValue());
49 }
50 case DecoderTreeNode::SwitchField: {
51 const auto *N = static_cast<const SwitchFieldNode *>(Node);
52 unsigned Size =
53 OpcodeSize + getULEB128Size(Value: N->getStartBit()) + FieldWidthSize;
54
55 for (auto [Val, Child] : drop_end(RangeOrContainer: N->cases())) {
56 unsigned ChildSize = computeNodeSize(Node: Child);
57 Size += getULEB128Size(Value: Val) + getULEB128Size(Value: ChildSize) + ChildSize;
58 }
59
60 // The last child is emitted with sentinel value 0 instead of the size.
61 // See the comment in emitSwitchFieldNode.
62 auto [Val, Child] = *std::prev(x: N->case_end());
63 unsigned ChildSize = computeNodeSize(Node: Child);
64 Size += getULEB128Size(Value: Val) + getULEB128Size(Value: 0) + ChildSize;
65 return Size;
66 }
67 case DecoderTreeNode::CheckPredicate: {
68 const auto *N = static_cast<const CheckPredicateNode *>(Node);
69 unsigned PredicateIndex = N->getPredicateIndex();
70 return OpcodeSize + getULEB128Size(Value: PredicateIndex);
71 }
72 case DecoderTreeNode::SoftFail: {
73 const auto *N = static_cast<const SoftFailNode *>(Node);
74 return OpcodeSize + getULEB128Size(Value: N->getPositiveMask()) +
75 getULEB128Size(Value: N->getNegativeMask());
76 }
77 case DecoderTreeNode::Decode: {
78 const auto *N = static_cast<const DecodeNode *>(Node);
79 return OpcodeSize + getULEB128Size(Value: N->getInstOpcode()) +
80 getULEB128Size(Value: N->getDecoderIndex());
81 }
82 }
83 llvm_unreachable("Unknown node kind");
84}
85
86unsigned DecoderTableEmitter::computeTableSize(const DecoderTreeNode *Root,
87 unsigned BitWidth) const {
88 unsigned Size = 0;
89 if (BitWidth)
90 Size += getULEB128Size(Value: BitWidth);
91 Size += computeNodeSize(Node: Root);
92 return Size;
93}
94
95void DecoderTableEmitter::emitStartLine() {
96 LineStartIndex = CurrentIndex;
97 OS.indent(NumSpaces: 2);
98}
99
100void DecoderTableEmitter::emitOpcode(StringRef Name) {
101 emitStartLine();
102 OS << Name << ", ";
103 ++CurrentIndex;
104}
105
106void DecoderTableEmitter::emitByte(uint8_t Val) {
107 OS << static_cast<unsigned>(Val) << ", ";
108 ++CurrentIndex;
109}
110
111void DecoderTableEmitter::emitUInt8(unsigned Val) {
112 assert(isUInt<8>(Val));
113 emitByte(Val);
114}
115
116void DecoderTableEmitter::emitULEB128(uint64_t Val) {
117 while (Val >= 0x80) {
118 emitByte(Val: (Val & 0x7F) | 0x80);
119 Val >>= 7;
120 }
121 emitByte(Val);
122}
123
124raw_ostream &DecoderTableEmitter::emitComment(indent Indent) {
125 constexpr unsigned CommentColumn = 45;
126 if (OS.getColumn() > CommentColumn)
127 OS << '\n';
128 OS.PadToColumn(NewCol: CommentColumn);
129 OS << "// " << format_decimal(N: LineStartIndex, Width: IndexWidth) << ": " << Indent;
130 return OS;
131}
132
133namespace {
134
135/// Helper class for printing bit ranges.
136struct BitRange {
137 unsigned MSB, LSB;
138
139 friend raw_ostream &operator<<(raw_ostream &OS, BitRange R) {
140 if (R.MSB == R.LSB)
141 OS << '[' << R.LSB << ']';
142 else
143 OS << '[' << R.MSB << ':' << R.LSB << ']';
144 return OS;
145 }
146};
147
148} // namespace
149
150void DecoderTableEmitter::emitCheckAnyNode(const CheckAnyNode *N,
151 indent Indent) {
152 // TODO: Single-child CheckAny node should be optimized out. For now,
153 // pretend this is the case and print the single child unindented.
154 if (range_size(Range: N->children()) == 1) {
155 emitNode(N: *N->child_begin(), Indent);
156 return;
157 }
158
159 ListSeparator LS("} else ");
160 for (const DecoderTreeNode *Child : drop_end(RangeOrContainer: N->children())) {
161 emitOpcode(Name: "OPC_Scope");
162 emitULEB128(Val: computeNodeSize(Node: Child));
163
164 emitComment(Indent) << LS << "try {\n";
165 emitNode(N: Child, Indent: Indent + 1);
166 }
167
168 // Don't emit OPC_Scope for the last child so that we leave the current scope
169 // if it fails. Otherwise, we would need some kind of OPC_LeaveScope opcode.
170 const DecoderTreeNode *Child = *std::prev(x: N->child_end());
171
172 emitComment(Indent) << LS << "try {\n";
173 emitNode(N: Child, Indent: Indent + 1);
174 emitComment(Indent) << "}\n";
175}
176
177void DecoderTableEmitter::emitCheckAllNode(const CheckAllNode *N,
178 indent Indent) {
179 // TODO: Single-child CheckAll should be optimized out.
180 // TODO: Nested CheckAll nodes should be flattened.
181 // TODO: Sibling CheckAll and other Check* nodes should be merged together.
182 for (const DecoderTreeNode *Child : N->children())
183 emitNode(N: Child, Indent);
184}
185
186void DecoderTableEmitter::emitSwitchFieldNode(const SwitchFieldNode *N,
187 indent Indent) {
188 unsigned LSB = N->getStartBit();
189 unsigned Width = N->getNumBits();
190 unsigned MSB = LSB + Width - 1;
191
192 emitOpcode(Name: "OPC_SwitchField");
193 emitULEB128(Val: LSB);
194 emitUInt8(Val: Width);
195
196 emitComment(Indent) << "switch Inst" << BitRange{.MSB: MSB, .LSB: LSB} << " {\n";
197
198 for (auto [Val, Child] : drop_end(RangeOrContainer: N->cases())) {
199 emitStartLine();
200 emitULEB128(Val);
201 emitULEB128(Val: computeNodeSize(Node: Child));
202
203 emitComment(Indent) << "case " << format_hex(N: Val, Width: 0) << ": {\n";
204 emitNode(N: Child, Indent: Indent + 1);
205 emitComment(Indent) << "}\n";
206 }
207
208 // Don't emit the size of the last child and instead emit a sentinel value,
209 // which tells the interpreter that this is the last case. The interpreter
210 // doesn't need to know its size because SwitchField node never falls through
211 // (we either successfully decode an instruction, or leave the current scope).
212 auto [Val, Child] = *std::prev(x: N->case_end());
213 emitStartLine();
214 emitULEB128(Val);
215 emitULEB128(Val: 0);
216
217 emitComment(Indent) << "case " << format_hex(N: Val, Width: 0) << ": {\n";
218 emitNode(N: Child, Indent: Indent + 1);
219 emitComment(Indent) << "}\n";
220
221 emitComment(Indent) << "} // switch Inst" << BitRange{.MSB: MSB, .LSB: LSB} << "\n";
222}
223
224void DecoderTableEmitter::emitCheckFieldNode(const CheckFieldNode *N,
225 indent Indent) {
226 unsigned LSB = N->getStartBit();
227 unsigned Width = N->getNumBits();
228 unsigned MSB = LSB + Width - 1;
229 uint64_t Val = N->getValue();
230
231 emitOpcode(Name: "OPC_CheckField");
232 emitULEB128(Val: LSB);
233 emitUInt8(Val: Width);
234 emitULEB128(Val);
235
236 emitComment(Indent) << "check Inst" << BitRange{.MSB: MSB, .LSB: LSB}
237 << " == " << format_hex(N: Val, Width: 0) << '\n';
238}
239
240void DecoderTableEmitter::emitCheckPredicateNode(const CheckPredicateNode *N,
241 indent Indent) {
242 unsigned PredicateIndex = N->getPredicateIndex();
243
244 emitOpcode(Name: "OPC_CheckPredicate");
245 emitULEB128(Val: PredicateIndex);
246 TableInfo.HasCheckPredicate = true;
247
248 emitComment(Indent) << "check predicate " << PredicateIndex << "\n";
249}
250
251void DecoderTableEmitter::emitSoftFailNode(const SoftFailNode *N,
252 indent Indent) {
253 uint64_t PositiveMask = N->getPositiveMask();
254 uint64_t NegativeMask = N->getNegativeMask();
255
256 emitOpcode(Name: "OPC_SoftFail");
257 emitULEB128(Val: PositiveMask);
258 emitULEB128(Val: NegativeMask);
259 TableInfo.HasSoftFail = true;
260
261 emitComment(Indent) << "softfail";
262 OS << " pos=" << format_hex(N: PositiveMask, Width: 10);
263 OS << " neg=" << format_hex(N: NegativeMask, Width: 10) << '\n';
264}
265
266void DecoderTableEmitter::emitDecodeNode(const DecodeNode *N, indent Indent) {
267 StringRef EncodingName = N->getEncodingName();
268 unsigned InstOpcode = N->getInstOpcode();
269 unsigned DecoderIndex = N->getDecoderIndex();
270
271 emitOpcode(Name: "OPC_Decode");
272 emitULEB128(Val: InstOpcode);
273 emitULEB128(Val: DecoderIndex);
274
275 emitComment(Indent) << "decode to " << EncodingName << " using decoder "
276 << DecoderIndex << '\n';
277}
278
279void DecoderTableEmitter::emitNode(const DecoderTreeNode *N, indent Indent) {
280 switch (N->getKind()) {
281 case DecoderTreeNode::CheckAny:
282 return emitCheckAnyNode(N: static_cast<const CheckAnyNode *>(N), Indent);
283 case DecoderTreeNode::CheckAll:
284 return emitCheckAllNode(N: static_cast<const CheckAllNode *>(N), Indent);
285 case DecoderTreeNode::SwitchField:
286 return emitSwitchFieldNode(N: static_cast<const SwitchFieldNode *>(N), Indent);
287 case DecoderTreeNode::CheckField:
288 return emitCheckFieldNode(N: static_cast<const CheckFieldNode *>(N), Indent);
289 case DecoderTreeNode::CheckPredicate:
290 return emitCheckPredicateNode(N: static_cast<const CheckPredicateNode *>(N),
291 Indent);
292 case DecoderTreeNode::SoftFail:
293 return emitSoftFailNode(N: static_cast<const SoftFailNode *>(N), Indent);
294 case DecoderTreeNode::Decode:
295 return emitDecodeNode(N: static_cast<const DecodeNode *>(N), Indent);
296 }
297 llvm_unreachable("Unknown node kind");
298}
299
300void DecoderTableEmitter::emitTable(StringRef TableName, unsigned BitWidth,
301 const DecoderTreeNode *Root) {
302 unsigned TableSize = computeTableSize(Root, BitWidth);
303 OS << "static const uint8_t " << TableName << "[" << TableSize << "] = {\n";
304
305 // Calculate the number of decimal places for table indices.
306 // This is simply log10 of the table size.
307 IndexWidth = 1;
308 for (unsigned S = TableSize; S /= 10;)
309 ++IndexWidth;
310
311 CurrentIndex = 0;
312
313 // When specializing decoders per bit width, each decoder table will begin
314 // with the bitwidth for that table.
315 if (BitWidth) {
316 emitStartLine();
317 emitULEB128(Val: BitWidth);
318 emitComment(Indent: indent(0)) << "BitWidth " << BitWidth << '\n';
319 }
320
321 emitNode(N: Root, Indent: indent(0));
322 assert(CurrentIndex == TableSize &&
323 "The size of the emitted table differs from the calculated one");
324
325 OS << "};\n";
326}
327