327 lines · cpp
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-exception6//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 16unsigned17DecoderTableEmitter::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(N->children()) == 1)27 return computeNodeSize(*N->child_begin());28 unsigned Size = 0;29 // All children except the last one are preceded by OPC_Scope opcode and30 // the size of the child.31 for (const DecoderTreeNode *Child : drop_end(N->children())) {32 unsigned ChildSize = computeNodeSize(Child);33 Size += OpcodeSize + getULEB128Size(ChildSize) + ChildSize;34 }35 const DecoderTreeNode *Child = *std::prev(N->child_end());36 return Size + computeNodeSize(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(Child);43 return Size;44 }45 case DecoderTreeNode::CheckField: {46 const auto *N = static_cast<const CheckFieldNode *>(Node);47 return OpcodeSize + getULEB128Size(N->getStartBit()) + FieldWidthSize +48 getULEB128Size(N->getValue());49 }50 case DecoderTreeNode::SwitchField: {51 const auto *N = static_cast<const SwitchFieldNode *>(Node);52 unsigned Size =53 OpcodeSize + getULEB128Size(N->getStartBit()) + FieldWidthSize;54 55 for (auto [Val, Child] : drop_end(N->cases())) {56 unsigned ChildSize = computeNodeSize(Child);57 Size += getULEB128Size(Val) + getULEB128Size(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(N->case_end());63 unsigned ChildSize = computeNodeSize(Child);64 Size += getULEB128Size(Val) + getULEB128Size(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(PredicateIndex);71 }72 case DecoderTreeNode::SoftFail: {73 const auto *N = static_cast<const SoftFailNode *>(Node);74 return OpcodeSize + getULEB128Size(N->getPositiveMask()) +75 getULEB128Size(N->getNegativeMask());76 }77 case DecoderTreeNode::Decode: {78 const auto *N = static_cast<const DecodeNode *>(Node);79 return OpcodeSize + getULEB128Size(N->getInstOpcode()) +80 getULEB128Size(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(BitWidth);91 Size += computeNodeSize(Root);92 return Size;93}94 95void DecoderTableEmitter::emitStartLine() {96 LineStartIndex = CurrentIndex;97 OS.indent(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 & 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(CommentColumn);129 OS << "// " << format_decimal(LineStartIndex, 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 else143 OS << '[' << R.MSB << ':' << R.LSB << ']';144 return OS;145 }146};147 148} // namespace149 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(N->children()) == 1) {155 emitNode(*N->child_begin(), Indent);156 return;157 }158 159 ListSeparator LS("} else ");160 for (const DecoderTreeNode *Child : drop_end(N->children())) {161 emitOpcode("OPC_Scope");162 emitULEB128(computeNodeSize(Child));163 164 emitComment(Indent) << LS << "try {\n";165 emitNode(Child, Indent + 1);166 }167 168 // Don't emit OPC_Scope for the last child so that we leave the current scope169 // if it fails. Otherwise, we would need some kind of OPC_LeaveScope opcode.170 const DecoderTreeNode *Child = *std::prev(N->child_end());171 172 emitComment(Indent) << LS << "try {\n";173 emitNode(Child, 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(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("OPC_SwitchField");193 emitULEB128(LSB);194 emitUInt8(Width);195 196 emitComment(Indent) << "switch Inst" << BitRange{MSB, LSB} << " {\n";197 198 for (auto [Val, Child] : drop_end(N->cases())) {199 emitStartLine();200 emitULEB128(Val);201 emitULEB128(computeNodeSize(Child));202 203 emitComment(Indent) << "case " << format_hex(Val, 0) << ": {\n";204 emitNode(Child, 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 interpreter210 // doesn't need to know its size because SwitchField node never falls through211 // (we either successfully decode an instruction, or leave the current scope).212 auto [Val, Child] = *std::prev(N->case_end());213 emitStartLine();214 emitULEB128(Val);215 emitULEB128(0);216 217 emitComment(Indent) << "case " << format_hex(Val, 0) << ": {\n";218 emitNode(Child, Indent + 1);219 emitComment(Indent) << "}\n";220 221 emitComment(Indent) << "} // switch Inst" << BitRange{MSB, 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("OPC_CheckField");232 emitULEB128(LSB);233 emitUInt8(Width);234 emitULEB128(Val);235 236 emitComment(Indent) << "check Inst" << BitRange{MSB, LSB}237 << " == " << format_hex(Val, 0) << '\n';238}239 240void DecoderTableEmitter::emitCheckPredicateNode(const CheckPredicateNode *N,241 indent Indent) {242 unsigned PredicateIndex = N->getPredicateIndex();243 244 emitOpcode("OPC_CheckPredicate");245 emitULEB128(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("OPC_SoftFail");257 emitULEB128(PositiveMask);258 emitULEB128(NegativeMask);259 TableInfo.HasSoftFail = true;260 261 emitComment(Indent) << "softfail";262 OS << " pos=" << format_hex(PositiveMask, 10);263 OS << " neg=" << format_hex(NegativeMask, 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("OPC_Decode");272 emitULEB128(InstOpcode);273 emitULEB128(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(static_cast<const CheckAnyNode *>(N), Indent);283 case DecoderTreeNode::CheckAll:284 return emitCheckAllNode(static_cast<const CheckAllNode *>(N), Indent);285 case DecoderTreeNode::SwitchField:286 return emitSwitchFieldNode(static_cast<const SwitchFieldNode *>(N), Indent);287 case DecoderTreeNode::CheckField:288 return emitCheckFieldNode(static_cast<const CheckFieldNode *>(N), Indent);289 case DecoderTreeNode::CheckPredicate:290 return emitCheckPredicateNode(static_cast<const CheckPredicateNode *>(N),291 Indent);292 case DecoderTreeNode::SoftFail:293 return emitSoftFailNode(static_cast<const SoftFailNode *>(N), Indent);294 case DecoderTreeNode::Decode:295 return emitDecodeNode(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 begin314 // with the bitwidth for that table.315 if (BitWidth) {316 emitStartLine();317 emitULEB128(BitWidth);318 emitComment(indent(0)) << "BitWidth " << BitWidth << '\n';319 }320 321 emitNode(Root, indent(0));322 assert(CurrentIndex == TableSize &&323 "The size of the emitted table differs from the calculated one");324 325 OS << "};\n";326}327