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#ifndef LLVM_UTILS_TABLEGEN_DECODERTREE_H
10#define LLVM_UTILS_TABLEGEN_DECODERTREE_H
11
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 more
29/// opportunities for uniqueness. If SpecializeDecodersPerBitwidth is enabled,
30/// decoders are shared across all trees for a given bitwidth, else they are
31/// 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(X: CachedHashString(Predicate));
38 PredicateSet::const_iterator I = find(Range&: Predicates, Val: Predicate);
39 return std::distance(first: Predicates.begin(), last: I);
40 }
41
42 unsigned getDecoderIndex(StringRef Decoder) {
43 Decoders.insert(X: CachedHashString(Decoder));
44 DecoderSet::const_iterator I = find(Range&: Decoders, Val: Decoder);
45 return std::distance(first: Decoders.begin(), last: 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(Elt: 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(x: child_begin(), y: 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 a
107/// 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 where
141/// 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(k: Value, args: 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(x: case_begin(), y: 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 llvm
224
225#endif // LLVM_UTILS_TABLEGEN_DECODERTREE_H
226