1 /*
2 * Copyright (c) 2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 #ifndef ECMASCRIPT_COMPILER_GATE_MATCHERS_H
16 #define ECMASCRIPT_COMPILER_GATE_MATCHERS_H
17
18 #include "ecmascript/compiler/circuit.h"
19 #include "ecmascript/compiler/circuit_builder.h"
20 #include "utils/bit_utils.h"
21
22
23 namespace panda::ecmascript::kungfu {
24
25 // Checks if value is in range [lowerLimit, higherLimit] using a single
26 // branch.
IsValueInRange(T value,U lowerLimit,U higherLimit)27 template <typename T, typename U> inline constexpr bool IsValueInRange(T value, U lowerLimit, U higherLimit)
28 {
29 static_assert(sizeof(U) <= sizeof(T));
30 using unsigned_T = typename std::make_unsigned<T>::type;
31 // Use static_cast to support enum classes.
32 return static_cast<unsigned_T>(static_cast<unsigned_T>(value) - static_cast<unsigned_T>(lowerLimit)) <=
33 static_cast<unsigned_T>(static_cast<unsigned_T>(higherLimit) - static_cast<unsigned_T>(lowerLimit));
34 }
35
36 class GateMatcher {
37 public:
GateMatcher(GateRef gate,Circuit * circuit)38 explicit GateMatcher(GateRef gate, Circuit *circuit) : acc_(circuit), gate_(gate)
39 {
40 }
41
Gate()42 GateRef Gate() const
43 {
44 return gate_;
45 }
46
ValueIn(uint32_t index)47 GateRef ValueIn(uint32_t index)
48 {
49 return acc_.GetValueIn(gate_, index);
50 }
51
Opcode()52 OpCode Opcode() const
53 {
54 return acc_.GetOpCode(gate_);
55 }
56
MachineType()57 MachineType MachineType() const
58 {
59 return acc_.GetMachineType(gate_);
60 }
InputAt(int index)61 GateRef InputAt(int index) const
62 {
63 return acc_.GetValueIn(gate_, index);
64 }
65
66 #define DECLARE_IS_GATE(NAME, OP, R, S, D, V) \
67 bool Is##NAME() const \
68 { \
69 return (Opcode() == (OpCode::OP)); \
70 }
71 IMMUTABLE_META_DATA_CACHE_LIST(DECLARE_IS_GATE)
GATE_META_DATA_LIST_WITH_BOOL(DECLARE_IS_GATE)72 GATE_META_DATA_LIST_WITH_BOOL(DECLARE_IS_GATE)
73 GATE_META_DATA_LIST_WITH_BOOL_VALUE_IN(DECLARE_IS_GATE)
74 GATE_META_DATA_LIST_WITH_SIZE(DECLARE_IS_GATE)
75 GATE_META_DATA_LIST_WITH_ONE_PARAMETER(DECLARE_IS_GATE) GATE_META_DATA_LIST_WITH_PC_OFFSET(DECLARE_IS_GATE)
76 GATE_META_DATA_LIST_FOR_CALL(DECLARE_IS_GATE) GATE_META_DATA_LIST_WITH_PC_OFFSET_FIXED_VALUE(DECLARE_IS_GATE)
77 #undef DECLARE_IS_GATE
78
79 #define DECLARE_IS_INST(NAME, OPCODEID, MACHINETYPEID) \
80 bool Ism##NAME() const \
81 { \
82 return Is##OPCODEID() && MachineType() == (MACHINETYPEID); \
83 }
84 BINARY_ARITHMETIC_METHOD_LIST_WITH_BITWIDTH(DECLARE_IS_INST)
85 UNARY_ARITHMETIC_METHOD_LIST_WITH_BITWIDTH(DECLARE_IS_INST)
86 UNARY_ARITHMETIC_METHOD_LIST_WITH_BITWIDTH_PRIVATE(DECLARE_IS_INST)
87 #undef DECLARE_IS_INST
88
89 #define DECLARE_IS_INST(NAME, OPCODEID, CONDITION) \
90 bool Ism##NAME() const \
91 { \
92 return Is##OPCODEID() && static_cast<uint64_t>(CONDITION) == ConditionValue(); \
93 }; \
94 BINARY_CMP_METHOD_LIST_WITHOUT_BITWIDTH(DECLARE_IS_INST)
95 #undef DECLARE_IS_INST
96
97 bool Equals(const GateRef gate)
98 {
99 return gate == Gate();
100 }
101
102 GateAccessor acc_;
103
ConditionValue()104 BitField ConditionValue()
105 {
106 ASSERT(IsFcmp() || IsIcmp());
107 return acc_.TryGetValue(Gate());
108 }
109 private:
110 GateRef gate_;
111 };
112
113 // A pattern matcher for abitrary value constants.
114 //
115 // Note that value identities on the input gate are skipped when matching. The
116 // resolved value may not be a parameter of the input gate. The Gate() method
117 // returns the unmodified input gate. This is by design, as reducers may wish to
118 // match value constants but delay reducing the gate until a later phase.
119 template <typename T, OpCode kOpcode, MachineType kMachineType> struct ValueMatcher : public GateMatcher {
120 using ValueType = T;
121
ValueMatcherValueMatcher122 explicit ValueMatcher(GateRef gate, Circuit *circuit)
123 : GateMatcher(gate, circuit), resolvedValue_(), hasResolvedValue_(false)
124 {
125 if (acc_.GetOpCode(gate) == kOpcode && acc_.GetMachineType(gate) == kMachineType) {
126 hasResolvedValue_ = true;
127 }
128
129 if (hasResolvedValue_) {
130 if (kMachineType == F64) {
131 resolvedValue_ = acc_.GetFloat64FromConstant(gate);
132 } else if (kMachineType == I32) {
133 resolvedValue_ = acc_.GetInt32FromConstant(gate);
134 } else if (kMachineType == I64) {
135 resolvedValue_ = acc_.GetConstantValue(gate);
136 } else {
137 hasResolvedValue_ = false;
138 }
139 }
140 }
141
HasResolvedValueValueMatcher142 bool HasResolvedValue() const
143 {
144 return hasResolvedValue_;
145 }
ResolvedValueValueMatcher146 const T &ResolvedValue() const
147 {
148 ASSERT(HasResolvedValue());
149 return resolvedValue_;
150 }
151
152 private:
153 T resolvedValue_;
154 bool hasResolvedValue_;
155 };
156
157 // A pattern matcher for integer constants.
158 template <typename T, OpCode kOpcode, MachineType kMachineType>
159 struct IntMatcher final : public ValueMatcher<T, kOpcode, kMachineType> {
IntMatcherfinal160 explicit IntMatcher(GateRef gate, Circuit *circuit) : ValueMatcher<T, kOpcode, kMachineType>(gate, circuit)
161 {
162 }
163
Isfinal164 bool Is(const T &value) const
165 {
166 return this->HasResolvedValue() && this->ResolvedValue() == value;
167 }
168
IsInRangefinal169 bool IsInRange(const T &low, const T &high) const
170 {
171 return this->HasResolvedValue() && IsValueInRange(this->ResolvedValue(), low, high);
172 }
IsMultipleOffinal173 bool IsMultipleOf(T n) const
174 {
175 if (!this->HasResolvedValue()) {
176 return false;
177 }
178 return (this->ResolvedValue() % n) == 0;
179 }
180
IsPowerOf2final181 bool IsPowerOf2() const
182 {
183 if (!this->HasResolvedValue() || this->ResolvedValue() <= 0) {
184 return false;
185 }
186 return (this->ResolvedValue() & (this->ResolvedValue() - 1)) == 0;
187 }
188
IsNegativePowerOf2final189 bool IsNegativePowerOf2() const
190 {
191 if (!this->HasResolvedValue() || this->ResolvedValue() >= 0) {
192 return false;
193 }
194 return ((this->ResolvedValue() == std::numeric_limits<T>::min()) ||
195 (-this->ResolvedValue() & (-this->ResolvedValue() - 1)) == 0);
196 }
197
IsNegativefinal198 bool IsNegative() const
199 {
200 if (!this->HasResolvedValue()) {
201 return false;
202 }
203 return this->ResolvedValue() < 0;
204 }
205 };
206
207 using Int32Matcher = IntMatcher<int32_t, OpCode::CONSTANT, MachineType::I32>;
208 using Uint32Matcher = IntMatcher<uint32_t, OpCode::CONSTANT, MachineType::I32>;
209 using Int64Matcher = IntMatcher<int64_t, OpCode::CONSTANT, MachineType::I64>;
210 using Uint64Matcher = IntMatcher<uint64_t, OpCode::CONSTANT, MachineType::I64>;
211
212
213 // A pattern matcher for floating point constants.
214 template <typename T, OpCode kOpcode, MachineType kMachineType>
215 struct FloatMatcher final : public ValueMatcher<T, kOpcode, kMachineType> {
FloatMatcherfinal216 explicit FloatMatcher(GateRef gate, Circuit *circuit) : ValueMatcher<T, kOpcode, kMachineType>(gate, circuit)
217 {
218 }
219
Isfinal220 bool Is(const T &value) const
221 {
222 return this->HasResolvedValue() && this->ResolvedValue() == value;
223 }
IsInRangefinal224 bool IsInRange(const T &low, const T &high) const
225 {
226 return this->HasResolvedValue() && low <= this->ResolvedValue() && this->ResolvedValue() <= high;
227 }
IsMinusZerofinal228 bool IsMinusZero() const
229 {
230 if (!this->HasResolvedValue()) {
231 return false;
232 }
233 return this->Is(0.0) && std::signbit(this->ResolvedValue());
234 }
235
IsNegativefinal236 bool IsNegative() const
237 {
238 if (!this->HasResolvedValue()) {
239 return false;
240 }
241 return this->ResolvedValue() < 0.0;
242 }
243
IsNaNfinal244 bool IsNaN() const
245 {
246 if (!this->HasResolvedValue()) {
247 return false;
248 }
249 return std::isnan(this->ResolvedValue());
250 }
251
IsZerofinal252 bool IsZero() const
253 {
254 if (!this->HasResolvedValue()) {
255 return false;
256 }
257 return this->Is(0.0) && !std::signbit(this->ResolvedValue());
258 }
259
IsNormalfinal260 bool IsNormal() const
261 {
262 if (!this->HasResolvedValue()) {
263 return false;
264 }
265 return std::isnormal(this->ResolvedValue());
266 }
267
IsIntegerfinal268 bool IsInteger() const
269 {
270 if (!this->HasResolvedValue()) {
271 return false;
272 }
273 return std::nearbyint(this->ResolvedValue()) == this->ResolvedValue();
274 }
275 };
276
277 using Float32Matcher = FloatMatcher<float, OpCode::CONSTANT, MachineType::F32>;
278 using Float64Matcher = FloatMatcher<double, OpCode::CONSTANT, MachineType::F64>;
279
280
281 // For shorter pattern matching code, this struct matches both the left and
282 // right hand sides of a binary operation and can put constants on the right
283 // if they appear on the left hand side of a commutative operation.
284 template <typename LeftExpr, typename RightExpr, MachineType rep> struct BinopMatcher : public GateMatcher {
BinopMatcherBinopMatcher285 explicit BinopMatcher(GateRef gate, Circuit *circuit)
286 : GateMatcher(gate, circuit), left_(InputAt(0), circuit), right_(InputAt(1), circuit)
287 {
288 if (IsCommutative(Opcode())) {
289 PutConstantOnRight();
290 }
291 }
292
BinopMatcherBinopMatcher293 BinopMatcher(GateRef gate, bool allowInputSwap, Circuit *circuit)
294 : GateMatcher(gate, circuit), left_(InputAt(0), circuit), right_(InputAt(1), circuit)
295 {
296 if (allowInputSwap) {
297 PutConstantOnRight();
298 }
299 }
300
301 using LeftMatcher = LeftExpr;
302 using RightMatcher = RightExpr;
303
304 // static constexpr MachineType representation = rep;
305
LeftBinopMatcher306 const LeftExpr &Left() const
307 {
308 return left_;
309 }
310
RightBinopMatcher311 const RightExpr &Right() const
312 {
313 return right_;
314 }
315
SetLeftBinopMatcher316 void SetLeft(GateRef left, Circuit* circuit)
317 {
318 left_ = LeftExpr(left, circuit);
319 }
320
SetRightBinopMatcher321 void SetRight(GateRef right, Circuit* circuit)
322 {
323 right_ = RightExpr(right, circuit);
324 }
325
IsFoldableBinopMatcher326 bool IsFoldable() const
327 {
328 return Left().HasResolvedValue() && Right().HasResolvedValue();
329 }
LeftEqualsRightBinopMatcher330 bool LeftEqualsRight() const
331 {
332 return Left().Gate() == Right().Gate();
333 }
334
OwnsInputBinopMatcher335 bool OwnsInput(GateRef input)
336 {
337 auto use = acc_.Uses(input);
338 for (auto it = use.begin(); it != use.end(); it++) {
339 if (*it != Gate()) {
340 return false;
341 }
342 }
343 return true;
344 }
345
346 protected:
SwapInputsBinopMatcher347 void SwapInputs()
348 {
349 std::swap(left_, right_);
350 acc_.ReplaceValueIn(Gate(), Left().Gate(), 0);
351 acc_.ReplaceValueIn(Gate(), Right().Gate(), 1);
352 }
353
354 private:
PutConstantOnRightBinopMatcher355 void PutConstantOnRight()
356 {
357 if (Left().HasResolvedValue() && !Right().HasResolvedValue()) {
358 SwapInputs();
359 }
360 }
IsCommutativeBinopMatcher361 static bool IsCommutative(OpCode opcode)
362 {
363 switch (opcode) {
364 case OpCode::ADD:
365 case OpCode::AND:
366 case OpCode::OR:
367 case OpCode::XOR:
368 case OpCode::MUL:
369 case OpCode::ADD_WITH_OVERFLOW:
370 case OpCode::MUL_WITH_OVERFLOW:
371 return true;
372 default:
373 return false;
374 }
375 return false;
376 }
377 LeftExpr left_;
378 RightExpr right_;
379 };
380
381 using Int32BinopMatcher = BinopMatcher<Int32Matcher, Int32Matcher, MachineType::I32>;
382 using Uint32BinopMatcher = BinopMatcher<Uint32Matcher, Uint32Matcher, MachineType::I32>;
383 using Int64BinopMatcher = BinopMatcher<Int64Matcher, Int64Matcher, MachineType::I64>;
384 using Uint64BinopMatcher = BinopMatcher<Uint64Matcher, Uint64Matcher, MachineType::I64>;
385 using Float32BinopMatcher = BinopMatcher<Float32Matcher, Float32Matcher, MachineType::F32>;
386 using Float64BinopMatcher = BinopMatcher<Float64Matcher, Float64Matcher, MachineType::F64>;
387
388
389 } // namespace panda::ecmascript::kungfu
390 #endif // ECMASCRIPT_COMPILER_GATE_MATCHERS_H