226 lines · c
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#ifndef LLVM_UTILS_TABLEGEN_DECODERTREE_H10#define LLVM_UTILS_TABLEGEN_DECODERTREE_H11 12#include "llvm/ADT/CachedHashString.h"13#include "llvm/ADT/STLExtras.h"14#include "llvm/ADT/SetVector.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/ADT/StringRef.h"17#include <map>18#include <memory>19 20namespace llvm {21 22class InstructionEncoding;23 24using PredicateSet = SetVector<CachedHashString>;25using DecoderSet = SetVector<CachedHashString>;26 27/// Context shared across decoder trees.28/// Predicates and decoders are shared across decoder trees to provide more29/// opportunities for uniqueness. If SpecializeDecodersPerBitwidth is enabled,30/// decoders are shared across all trees for a given bitwidth, else they are31/// shared across all trees. Predicates are always shared across all trees.32struct DecoderContext {33 PredicateSet Predicates;34 DecoderSet Decoders;35 36 unsigned getPredicateIndex(StringRef Predicate) {37 Predicates.insert(CachedHashString(Predicate));38 PredicateSet::const_iterator I = find(Predicates, Predicate);39 return std::distance(Predicates.begin(), I);40 }41 42 unsigned getDecoderIndex(StringRef Decoder) {43 Decoders.insert(CachedHashString(Decoder));44 DecoderSet::const_iterator I = find(Decoders, Decoder);45 return std::distance(Decoders.begin(), I);46 }47};48 49class DecoderTreeNode {50public:51 virtual ~DecoderTreeNode();52 53 enum KindTy {54 CheckAny,55 CheckAll,56 CheckField,57 SwitchField,58 CheckPredicate,59 SoftFail,60 Decode,61 };62 63 KindTy getKind() const { return Kind; }64 65protected:66 explicit DecoderTreeNode(KindTy Kind) : Kind(Kind) {}67 68private:69 KindTy Kind;70};71 72/// Common base class for nodes with multiple children.73class CheckManyNode : public DecoderTreeNode {74 SmallVector<std::unique_ptr<DecoderTreeNode>, 0> Children;75 76 static const DecoderTreeNode *77 mapElement(decltype(Children)::const_reference Element) {78 return Element.get();79 }80 81protected:82 explicit CheckManyNode(KindTy Kind) : DecoderTreeNode(Kind) {}83 84public:85 void addChild(std::unique_ptr<DecoderTreeNode> Child) {86 Children.push_back(std::move(Child));87 }88 89 using child_iterator = mapped_iterator<decltype(Children)::const_iterator,90 decltype(&mapElement)>;91 92 child_iterator child_begin() const {93 return child_iterator(Children.begin(), mapElement);94 }95 96 child_iterator child_end() const {97 return child_iterator(Children.end(), mapElement);98 }99 100 iterator_range<child_iterator> children() const {101 return make_range(child_begin(), child_end());102 }103};104 105/// Executes child nodes one by one until one of them succeeds or all fail.106/// The node fails if all child nodes fail. It never succeeds, because if a107/// child node succeeds, it does not return.108class CheckAnyNode : public CheckManyNode {109public:110 CheckAnyNode() : CheckManyNode(CheckAny) {}111};112 113/// Executes child nodes one by one until one of them fails all all succeed.114/// The node fails if any of the child nodes fails.115class CheckAllNode : public CheckManyNode {116public:117 CheckAllNode() : CheckManyNode(CheckAll) {}118};119 120/// Checks the value of encoding bits in the specified range.121class CheckFieldNode : public DecoderTreeNode {122 unsigned StartBit;123 unsigned NumBits;124 uint64_t Value;125 126public:127 CheckFieldNode(unsigned StartBit, unsigned NumBits, uint64_t Value)128 : DecoderTreeNode(CheckField), StartBit(StartBit), NumBits(NumBits),129 Value(Value) {}130 131 unsigned getStartBit() const { return StartBit; }132 133 unsigned getNumBits() const { return NumBits; }134 135 uint64_t getValue() const { return Value; }136};137 138/// Switch based on the value of encoding bits in the specified range.139/// If the value of the bits in the range doesn't match any of the cases,140/// the node fails. This is semantically equivalent to CheckAny node where141/// every child is a CheckField node, but is faster.142class SwitchFieldNode : public DecoderTreeNode {143 unsigned StartBit;144 unsigned NumBits;145 std::map<uint64_t, std::unique_ptr<DecoderTreeNode>> Cases;146 147 static std::pair<uint64_t, const DecoderTreeNode *>148 mapElement(decltype(Cases)::const_reference Element) {149 return std::pair(Element.first, Element.second.get());150 }151 152public:153 SwitchFieldNode(unsigned StartBit, unsigned NumBits)154 : DecoderTreeNode(SwitchField), StartBit(StartBit), NumBits(NumBits) {}155 156 void addCase(uint64_t Value, std::unique_ptr<DecoderTreeNode> N) {157 Cases.try_emplace(Value, std::move(N));158 }159 160 unsigned getStartBit() const { return StartBit; }161 162 unsigned getNumBits() const { return NumBits; }163 164 using case_iterator =165 mapped_iterator<decltype(Cases)::const_iterator, decltype(&mapElement)>;166 167 case_iterator case_begin() const {168 return case_iterator(Cases.begin(), mapElement);169 }170 171 case_iterator case_end() const {172 return case_iterator(Cases.end(), mapElement);173 }174 175 iterator_range<case_iterator> cases() const {176 return make_range(case_begin(), case_end());177 }178};179 180/// Checks that the instruction to be decoded has its predicates satisfied.181class CheckPredicateNode : public DecoderTreeNode {182 unsigned PredicateIndex;183 184public:185 explicit CheckPredicateNode(unsigned PredicateIndex)186 : DecoderTreeNode(CheckPredicate), PredicateIndex(PredicateIndex) {}187 188 unsigned getPredicateIndex() const { return PredicateIndex; }189};190 191/// Checks if the encoding bits are correct w.r.t. SoftFail semantics.192/// This is the only node that can never fail.193class SoftFailNode : public DecoderTreeNode {194 uint64_t PositiveMask, NegativeMask;195 196public:197 SoftFailNode(uint64_t PositiveMask, uint64_t NegativeMask)198 : DecoderTreeNode(SoftFail), PositiveMask(PositiveMask),199 NegativeMask(NegativeMask) {}200 201 uint64_t getPositiveMask() const { return PositiveMask; }202 uint64_t getNegativeMask() const { return NegativeMask; }203};204 205/// Attempts to decode the specified encoding as the specified instruction.206class DecodeNode : public DecoderTreeNode {207 StringRef EncodingName;208 unsigned InstOpcode;209 unsigned DecoderIndex;210 211public:212 DecodeNode(StringRef EncodingName, unsigned InstOpcode, unsigned DecoderIndex)213 : DecoderTreeNode(Decode), EncodingName(EncodingName),214 InstOpcode(InstOpcode), DecoderIndex(DecoderIndex) {}215 216 StringRef getEncodingName() const { return EncodingName; }217 218 unsigned getInstOpcode() const { return InstOpcode; }219 220 unsigned getDecoderIndex() const { return DecoderIndex; }221};222 223} // namespace llvm224 225#endif // LLVM_UTILS_TABLEGEN_DECODERTREE_H226