• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "ecmascript/compiler/instruction_combine.h"
16 #include "ecmascript/compiler/circuit_builder-inl.h"
17 #include "ecmascript/compiler/gate_matchers.h"
18 
19 namespace panda::ecmascript::kungfu {
20 
21 template <typename T, typename = typename std::enable_if<std::is_integral<T>::value>::type>
WhichPowerOfTwo(T value)22 inline constexpr int WhichPowerOfTwo(T value)
23 {
24     // Ensure the size of the integer is no more than 8 bytes (64 bits).
25     static_assert(sizeof(T) <= 8);
26     // Use __builtin_ctzll for 8 bytes (64 bits) and __builtin_ctz for 32-bit integers.
27     return sizeof(T) == 8 ? __builtin_ctzll(static_cast<uint64_t>(value)) : __builtin_ctz(static_cast<uint32_t>(value));
28 }
29 
30 
SignedDiv32(int32_t lhs,int32_t rhs)31 int32_t SignedDiv32(int32_t lhs, int32_t rhs)
32 {
33     if (rhs == 0) {
34         return 0;
35     }
36     if (rhs == -1) {
37         return lhs == std::numeric_limits<int32_t>::min() ? lhs : -lhs;
38     }
39     return lhs / rhs;
40 }
41 
SignedDiv64(int64_t lhs,int64_t rhs)42 int64_t SignedDiv64(int64_t lhs, int64_t rhs)
43 {
44     if (rhs == 0) {
45         return 0;
46     }
47     if (rhs == -1) {
48         return lhs == std::numeric_limits<int64_t>::min() ? lhs : -lhs;
49     }
50     return lhs / rhs;
51 }
52 
SignedMod32(int32_t lhs,int32_t rhs)53 int32_t SignedMod32(int32_t lhs, int32_t rhs)
54 {
55     if (rhs == 0 || rhs == -1) {
56         return 0;
57     }
58     return lhs % rhs;
59 }
60 
61 
SignedAddOverflow32(int32_t lhs,int32_t rhs,int32_t * val)62 inline bool SignedAddOverflow32(int32_t lhs, int32_t rhs, int32_t *val)
63 {
64     uint32_t res = static_cast<uint32_t>(lhs) + static_cast<uint32_t>(rhs);
65     *val = base::bit_cast<int32_t>(res);
66     // Check for overflow by examining the sign bit.(bit 31 in a 32-bit integer)
67     return ((res ^ static_cast<uint32_t>(lhs)) & (res ^ static_cast<uint32_t>(rhs)) & (1U << 31)) != 0;
68 }
69 
70 
SignedSubOverflow32(int32_t lhs,int32_t rhs,int32_t * val)71 inline bool SignedSubOverflow32(int32_t lhs, int32_t rhs, int32_t *val)
72 {
73     uint32_t res = static_cast<uint32_t>(lhs) - static_cast<uint32_t>(rhs);
74     *val = base::bit_cast<int32_t>(res);
75     // Check for overflow by examining the sign bit.(bit 31 in a 32-bit integer)
76     return ((res ^ static_cast<uint32_t>(lhs)) & (res ^ ~static_cast<uint32_t>(rhs)) & (1U << 31)) != 0;
77 }
78 
SignedMulOverflow32(int32_t lhs,int32_t rhs,int32_t * val)79 inline bool SignedMulOverflow32(int32_t lhs, int32_t rhs, int32_t *val)
80 {
81     int64_t result = int64_t{lhs} * int64_t{rhs};
82     *val = static_cast<int32_t>(result);
83     using limits = std::numeric_limits<int32_t>;
84     return result < limits::min() || result > limits::max();
85 }
86 
87 
88 // Returns the quotient x/y, avoiding C++ undefined behavior if y == 0.
Divide(T x,T y)89 template <typename T> inline T Divide(T x, T y)
90 {
91     if (y != 0) {
92         return x / y;
93     }
94     if (x == 0 || x != x) {
95         return std::numeric_limits<T>::quiet_NaN();
96     }
97     if ((x >= 0) == (std::signbit(y) == 0)) {
98         return std::numeric_limits<T>::infinity();
99     }
100     return -std::numeric_limits<T>::infinity();
101 }
102 
103 // Helpers for performing overflowing arithmetic operations without relying
104 // on C++ undefined behavior.
105 #define ASSERT_SIGNED_INTEGER_TYPE(Type)                                                                               \
106     static_assert(std::is_integral<Type>::value && std::is_signed<Type>::value, "use this for signed integer types")
107 #define OP_WITH_WRAPAROUND(Name, OP)                                                                                   \
108     template <typename signed_type> inline signed_type Name##WithWraparound(signed_type a, signed_type b)              \
109     {                                                                                                                  \
110         ASSERT_SIGNED_INTEGER_TYPE(signed_type);                                                                       \
111         using unsigned_type = typename std::make_unsigned<signed_type>::type;                                          \
112         unsigned_type a_unsigned = static_cast<unsigned_type>(a);                                                      \
113         unsigned_type b_unsigned = static_cast<unsigned_type>(b);                                                      \
114         unsigned_type result = a_unsigned OP b_unsigned;                                                               \
115         return static_cast<signed_type>(result);                                                                       \
116     }
117 
118 OP_WITH_WRAPAROUND(Add, +)
119 OP_WITH_WRAPAROUND(Sub, -)
120 OP_WITH_WRAPAROUND(Mul, *)
121 
ShlWithWraparound(signed_type a,signed_type b)122 template <typename signed_type> inline signed_type ShlWithWraparound(signed_type a, signed_type b)
123 {
124     using unsigned_type = typename std::make_unsigned<signed_type>::type;
125     const unsigned_type kMask = (sizeof(a) * 8) - 1;
126     return static_cast<signed_type>(static_cast<unsigned_type>(a) << (b & kMask));
127 }
128 
NegateWithWraparound(signed_type a)129 template <typename signed_type> inline signed_type NegateWithWraparound(signed_type a)
130 {
131     ASSERT_SIGNED_INTEGER_TYPE(signed_type);
132     if (a == std::numeric_limits<signed_type>::min()) {
133         return a;
134     }
135     return -a;
136 }
137 
ReplaceOld(GateRef gate,GateRef newGate)138 GateRef InstructionCombine::ReplaceOld(GateRef gate, GateRef newGate)
139 {
140     acc_.UpdateAllUses(gate, newGate);
141     return newGate;
142 }
143 
144 
VisitGate(GateRef gate)145 GateRef InstructionCombine::VisitGate(GateRef gate)
146 {
147     OpCode op = acc_.GetOpCode(gate);
148     GateRef result = Circuit::NullGate();
149     ;
150     switch (op) {
151         case OpCode::ADD:
152             result = VisitADD(gate);
153             break;
154         case OpCode::SUB:
155             result = VisitSUB(gate);
156             break;
157         case OpCode::MUL:
158             result = VisitMUL(gate);
159             break;
160         case OpCode::SDIV:
161             result = VisitSDIV(gate);
162             break;
163         case OpCode::FDIV:
164             result = VisitFDIV(gate);
165             break;
166         case OpCode::SMOD:
167             result = VisitSMOD(gate);
168             break;
169         case OpCode::AND:
170             result = VisitAND(gate);
171             break;
172         case OpCode::OR:
173             result = VisitOR(gate);
174             break;
175         case OpCode::XOR:
176             result = VisitXOR(gate);
177             break;
178         case OpCode::ASR:
179             result = VisitASR(gate);
180             break;
181         case OpCode::LSL:
182             result = VisitLSL(gate);
183             break;
184         case OpCode::LSR:
185             result = VisitLSR(gate);
186             break;
187         case OpCode::ICMP:
188             result = VisitICMP(gate);
189             break;
190         case OpCode::REV:
191             result = VisitREV(gate);
192             break;
193         case OpCode::IF_BRANCH:
194             result = VisitBranch(gate);
195             break;
196         case OpCode::EXTRACT_VALUE:
197             return VisitExtractValue(gate);
198         case OpCode::TAGGED_TO_INT64:
199         case OpCode::INT64_TO_TAGGED:
200         case OpCode::SIGNED_INT_TO_FLOAT:
201         case OpCode::FLOAT_TO_SIGNED_INT:
202         case OpCode::UNSIGNED_FLOAT_TO_INT:
203         case OpCode::BITCAST:
204         case OpCode::ZEXT:
205         case OpCode::SEXT:
206         case OpCode::TRUNC:
207         case OpCode::FEXT:
208         case OpCode::FTRUNC:
209             return VisitConvert(gate);
210             break;
211         default:
212             break;
213     }
214     if (enableLog_ && result != Circuit::NullGate()) {
215         LOG_COMPILER(INFO) << "InstructionCombine opt befor -> afert";
216         acc_.Print(gate);
217         acc_.Print(result);
218     }
219     return result;
220 }
221 
222 // Wait for the implementation of constant folding and partial redundancy elimination.
223 // The Convert-related IR operations need refactoring for more effective optimization.
224 // 1. Merge or differentiate the functionalities of SignIntToFloat and Bitcast
225 //    as both handle Int-to-Float conversions. Int32ToFloat32 also exhibits similar behavior.
226 // 2. Clarify the roles of TruncFloatToInt64 and FTrunc, ensuring they are distinct or unified.
227 // 3. Standardize naming conventions for operations that are inverse or similar to each other
228 //    to avoid confusion. ex: ChangeTaggedPointerToInt64 and Int64ToTaggedPtr perform similar functions,
229 //    yet their names are significantly different
230 // 4. .................
VisitConvert(GateRef gate)231 GateRef InstructionCombine::VisitConvert(GateRef gate)
232 {
233     // For the meanings of the following Opcodes, please refer to
234     // UNARY_ARITHMETIC_METHOD_LIST_WITH_BITWIDTH
235     switch (acc_.GetOpCode(gate)) {
236         case OpCode::TAGGED_TO_INT64:
237             {
238                 GateMatcher in(acc_.GetValueIn(gate, 0), circuit_);
239                 if (in.IsInt64ToTagged()) {
240                     return in.ValueIn(0);
241                 }
242                 break;
243             }
244         case OpCode::INT64_TO_TAGGED:
245             {
246                 GateMatcher in(acc_.GetValueIn(gate, 0), circuit_);
247                 if (in.IsTaggedToInt64()) {
248                     return in.ValueIn(0);
249                 }
250                 break;
251             }
252         case OpCode::SIGNED_INT_TO_FLOAT:
253             {
254                 GateMatcher in(acc_.GetValueIn(gate, 0), circuit_);
255                 if (in.IsFloatToSignedInt()) {
256                     return in.ValueIn(0);
257                 }
258                 break;
259             }
260         case OpCode::FLOAT_TO_SIGNED_INT:
261             {
262                 GateMatcher in(acc_.GetValueIn(gate, 0), circuit_);
263                 if (in.IsSignedIntToFloat()) {
264                     return in.ValueIn(0);
265                 }
266                 break;
267             }
268         case OpCode::UNSIGNED_FLOAT_TO_INT:
269             break;
270         case OpCode::BITCAST:
271         case OpCode::ZEXT:
272         case OpCode::SEXT:
273         case OpCode::TRUNC:
274         case OpCode::FEXT:
275         case OpCode::FTRUNC:
276             break;
277         default:
278             break;
279     }
280     return Circuit::NullGate();
281 }
282 
VisitBranch(GateRef gate)283 GateRef InstructionCombine::VisitBranch(GateRef gate)
284 {
285     (void)gate;
286     return Circuit::NullGate();
287 }
288 
VisitREV(GateRef gate)289 GateRef InstructionCombine::VisitREV(GateRef gate)
290 {
291     // REV Constant => Constant
292     auto revValue = acc_.GetValueIn(gate, 0);
293     if (acc_.GetOpCode(revValue) == OpCode::CONSTANT && acc_.GetMachineType(revValue) == I1) {
294         if (acc_.GetConstantValue(revValue) == 0) {
295             return builder_.True();
296         } else {
297             return builder_.False();
298         }
299     }
300     return Circuit::NullGate();
301 }
302 
VisitICMP(GateRef gate)303 GateRef InstructionCombine::VisitICMP(GateRef gate)
304 {
305     Int64BinopMatcher m(gate, circuit_);
306     // Match {EQ ((x or constant1) , constant2)} {((constant1 | constant2) != constant2)} => false
307     GateRef result = Circuit::NullGate();
308     if (m.ConditionValue() == static_cast<uint64_t>(ICmpCondition::EQ) && m.Right().HasResolvedValue()) {
309         // In essence, it's all about comparing I64, so we can optimize further
310         // Subsequently, considering whether it can be automated within the gateMatcher
311         if (m.Left().Opcode() == OpCode::INT64_TO_TAGGED) {
312             m.SetLeft(m.Left().InputAt(0), circuit_);
313         }
314 
315         if (m.Left().IsOr()) {
316             Int64BinopMatcher cmpLeft(m.Left().Gate(), circuit_);
317             if (cmpLeft.Right().HasResolvedValue()) {
318                 uint64_t constant1 = static_cast<uint64_t>(cmpLeft.Right().ResolvedValue());
319                 uint64_t constant2 = static_cast<uint64_t>(m.Right().ResolvedValue());
320                 bool flag = ((constant1 | constant2) != constant2);
321                 result = flag ? builder_.False() : Circuit::NullGate();
322             }
323         }
324 
325         if (result != Circuit::NullGate()) {
326             return result;
327         }
328 
329         // Match {EQ((X or constant1) & constant2, 0)} { (constan2 !=0 && constant1 & constant2 !=0) }=> false
330         if (m.Left().IsAnd() && m.Right().ResolvedValue() == 0) {
331             Int64BinopMatcher andOp(m.Left().Gate(), circuit_);
332             if (andOp.Left().IsOr() && andOp.Right().HasResolvedValue() && andOp.Right().ResolvedValue() != 0) {
333                 // The awkwardness in writing it this way is simply to reduce cyclomatic complexity.
334                 Int64BinopMatcher orOp(andOp.Left().Gate(), circuit_);
335                 auto constant2 = andOp.Right().ResolvedValue();
336                 auto constant1 = orOp.Right().HasResolvedValue() ? orOp.Right().ResolvedValue() : 0;
337                 bool flag = ((constant1 & constant2) != 0);
338                 result = flag ? builder_.False() : Circuit::NullGate();
339             }
340         }
341         if (result != Circuit::NullGate()) {
342             return result;
343         }
344     }
345 
346     return Circuit::NullGate();
347 }
348 
VisitADD(GateRef gate)349 GateRef InstructionCombine::VisitADD(GateRef gate)
350 {
351     auto machineType = acc_.GetMachineType(gate);
352     switch (machineType) {
353         case MachineType::I32:
354             return ReduceInt32Add(gate);
355         case MachineType::I64:
356             return ReduceInt64Add(gate);
357         case MachineType::F64:
358             return ReduceDoubleAdd(gate);
359         default:
360             break;
361     }
362     return Circuit::NullGate();
363 }
364 
VisitSUB(GateRef gate)365 GateRef InstructionCombine::VisitSUB(GateRef gate)
366 {
367     auto machineType = acc_.GetMachineType(gate);
368     switch (machineType) {
369         case MachineType::I32:
370             return ReduceInt32Sub(gate);
371         case MachineType::I64:
372             return ReduceInt64Sub(gate);
373         case MachineType::F64:
374             return ReduceDoubleSub(gate);
375         default:
376             break;
377     }
378     return Circuit::NullGate();
379 }
380 
VisitMUL(GateRef gate)381 GateRef InstructionCombine::VisitMUL(GateRef gate)
382 {
383     auto machineType = acc_.GetMachineType(gate);
384     switch (machineType) {
385         case MachineType::I32:
386             return ReduceInt32Mul(gate);
387         case MachineType::I64:
388             return ReduceInt64Mul(gate);
389         case MachineType::F64:
390             return ReduceDoubleMul(gate);
391         default:
392             break;
393     }
394     return Circuit::NullGate();
395 }
396 
VisitSDIV(GateRef gate)397 GateRef InstructionCombine::VisitSDIV(GateRef gate)
398 {
399     auto machineType = acc_.GetMachineType(gate);
400     switch (machineType) {
401         case MachineType::I32:
402             return ReduceInt32Div(gate);
403         case MachineType::I64:
404             return ReduceInt64Div(gate);
405         default:
406             break;
407     }
408     return Circuit::NullGate();
409 }
410 
VisitFDIV(GateRef gate)411 GateRef InstructionCombine::VisitFDIV(GateRef gate)
412 {
413     auto machineType = acc_.GetMachineType(gate);
414     switch (machineType) {
415         case MachineType::F64:
416             return ReduceDoubleDiv(gate);
417         default:
418             break;
419     }
420     return Circuit::NullGate();
421 }
422 
VisitSMOD(GateRef gate)423 GateRef InstructionCombine::VisitSMOD(GateRef gate)
424 {
425     auto machineType = acc_.GetMachineType(gate);
426     switch (machineType) {
427         case MachineType::I32:
428             return ReduceInt32Mod(gate);
429         case MachineType::F64:
430             return ReduceDoubleMod(gate);
431         default:
432             break;
433     }
434     return Circuit::NullGate();
435 }
436 
437 
VisitAND(GateRef gate)438 GateRef InstructionCombine::VisitAND(GateRef gate)
439 {
440     auto machineType = acc_.GetMachineType(gate);
441     switch (machineType) {
442         case MachineType::I32:
443             return ReduceWord32And(gate);
444         case MachineType::I64:
445             return ReduceWord64And(gate);
446         default:
447             break;
448     }
449     return Circuit::NullGate();
450 }
451 
VisitOR(GateRef gate)452 GateRef InstructionCombine::VisitOR(GateRef gate)
453 {
454     auto machineType = acc_.GetMachineType(gate);
455     switch (machineType) {
456         case MachineType::I32:
457             return ReduceWord32Or(gate);
458         case MachineType::I64:
459             return ReduceWord64Or(gate);
460         default:
461             break;
462     }
463     return Circuit::NullGate();
464 }
465 
VisitXOR(GateRef gate)466 GateRef InstructionCombine::VisitXOR(GateRef gate)
467 {
468     auto machineType = acc_.GetMachineType(gate);
469     switch (machineType) {
470         case MachineType::I32:
471             return ReduceWord32Xor(gate);
472         case MachineType::I64:
473             return ReduceWord64Xor(gate);
474         default:
475             break;
476     }
477     return Circuit::NullGate();
478 }
479 
VisitLSR(GateRef gate)480 GateRef InstructionCombine::VisitLSR(GateRef gate)
481 {
482     auto machineType = acc_.GetMachineType(gate);
483     switch (machineType) {
484         case MachineType::I32:
485             return ReduceWord32Lsr(gate);
486         case MachineType::I64:
487             return ReduceWord64Lsr(gate);
488         default:
489             break;
490     }
491     return Circuit::NullGate();
492 }
493 
VisitASR(GateRef gate)494 GateRef InstructionCombine::VisitASR(GateRef gate)
495 {
496     auto machineType = acc_.GetMachineType(gate);
497     switch (machineType) {
498         case MachineType::I32:
499             return ReduceWord32Asr(gate);
500         case MachineType::I64:
501             return ReduceWord64Asr(gate);
502         default:
503             break;
504     }
505     return Circuit::NullGate();
506 }
507 
508 
VisitLSL(GateRef gate)509 GateRef InstructionCombine::VisitLSL(GateRef gate)
510 {
511     auto machineType = acc_.GetMachineType(gate);
512     switch (machineType) {
513         case MachineType::I32:
514             return ReduceWord32Lsl(gate);
515         case MachineType::I64:
516             return ReduceWord64Lsl(gate);
517         default:
518             break;
519     }
520     return Circuit::NullGate();
521 }
522 
523 
VisitExtractValue(GateRef gate)524 GateRef InstructionCombine::VisitExtractValue(GateRef gate)
525 {
526     Int32BinopMatcher n(gate, circuit_);
527     int32_t index = n.Right().ResolvedValue();
528     int32_t val;
529     assert(index == 0 || index == 1);
530     switch (n.Left().Opcode()) {
531         case OpCode::ADD_WITH_OVERFLOW:
532             {
533                 Int32BinopMatcher m(n.Left().Gate(), circuit_);
534                 if (m.IsFoldable()) {
535                     bool ovf = SignedAddOverflow32(m.Left().ResolvedValue(), m.Right().ResolvedValue(), &val);
536                     return index == 0 ? builder_.Int32(val) : builder_.Boolean(ovf);
537                 }
538                 if (m.Right().Is(0)) {
539                     return (index == 0 ? m.Left().Gate() : builder_.Boolean(false));
540                 }
541                 break;
542             }
543         case OpCode::SUB_WITH_OVERFLOW:
544             {
545                 Int32BinopMatcher m(n.Left().Gate(), circuit_);
546                 if (m.IsFoldable()) {
547                     bool ovf = SignedSubOverflow32(m.Left().ResolvedValue(), m.Right().ResolvedValue(), &val);
548                     return index == 0 ? builder_.Int32(val) : builder_.Boolean(ovf);
549                 }
550                 if (m.Right().Is(0)) {
551                     return (index == 0 ? m.Left().Gate() : builder_.Boolean(false));
552                 }
553                 break;
554             }
555         case OpCode::MUL_WITH_OVERFLOW:
556             {
557                 Int32BinopMatcher m(n.Left().Gate(), circuit_);
558                 if (m.IsFoldable()) {
559                     bool ovf = SignedMulOverflow32(m.Left().ResolvedValue(), m.Right().ResolvedValue(), &val);
560                     return index == 0 ? builder_.Int32(val) : builder_.Boolean(ovf);
561                 }
562                 if (m.Right().Is(0)) {
563                     return (index == 0 ? builder_.Int32(0) : builder_.Boolean(false));
564                 }
565                 if (m.Right().Is(1)) {
566                     return (index == 0 ? m.Left().Gate() : builder_.Boolean(false));
567                 }
568                 break;
569             }
570         default:
571             break;
572     }
573     return Circuit::NullGate();
574 }
575 
ReduceInt64Add(GateRef gate)576 GateRef InstructionCombine::ReduceInt64Add(GateRef gate)
577 {
578     Int64BinopMatcher m(gate, circuit_);
579 
580     if (m.Right().Is(0)) {
581         return m.Left().Gate();
582     }
583 
584     if (m.IsFoldable()) {
585         return builder_.Int64(AddWithWraparound(m.Right().ResolvedValue(), m.Left().ResolvedValue()));
586     }
587 
588     // (x + Int64Constant(a)) + Int64Constant(b) => x + Int64Constant(a + b)
589     if (m.Right().HasResolvedValue() && m.Left().IsmInt64Add()) {
590         Int64BinopMatcher mLeft(m.Left().Gate(), circuit_);
591         if (mLeft.Right().HasResolvedValue() && m.OwnsInput(m.Left().Gate())) {
592             acc_.ReplaceValueIn(gate, mLeft.Left().Gate(), 0);
593             acc_.ReplaceValueIn(
594                 gate, builder_.Int64(AddWithWraparound(m.Right().ResolvedValue(), mLeft.Right().ResolvedValue())), 1);
595             return gate;
596         }
597     }
598 
599     return Circuit::NullGate();
600 }
601 
ReduceInt32Add(GateRef gate)602 GateRef InstructionCombine::ReduceInt32Add(GateRef gate)
603 {
604     Int32BinopMatcher m(gate, circuit_);
605     // x + 0 => x
606     if (m.Right().Is(0)) {
607         return m.Left().Gate();
608     }
609 
610     if (m.IsFoldable()) {
611         return builder_.Int32(AddWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
612     }
613 
614     if (m.Left().IsmInt32Sub()) {
615         Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
616         // (0 - x) + y => y - x
617         if (mleft.Left().Is(0)) {
618             auto newGate = builder_.Int32Sub(m.Right().Gate(), mleft.Right().Gate());
619             return ReplaceOld(gate, newGate);
620         }
621     }
622 
623     if (m.Right().IsmInt32Sub()) {
624         Int32BinopMatcher mright(m.Right().Gate(), circuit_);
625         // y + (0 - x) => y - x
626         if (mright.Left().Is(0)) {
627             auto newGate = builder_.Int32Sub(m.Left().Gate(), mright.Right().Gate());
628             return ReplaceOld(gate, newGate);
629         }
630     }
631     // (x + Int32Constant(a)) + Int32Constant(b)) => x + Int32Constant(a + b)
632     if (m.Right().HasResolvedValue() && m.Left().IsmInt32Add()) {
633         Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
634         if (mleft.Right().HasResolvedValue() && m.OwnsInput(m.Left().Gate())) {
635             acc_.ReplaceValueIn(gate, mleft.Left().Gate(), 0);
636             acc_.ReplaceValueIn(
637                 gate, builder_.Int32(AddWithWraparound(mleft.Right().ResolvedValue(), m.Right().ResolvedValue())), 1);
638             return gate;
639         }
640     }
641     return Circuit::NullGate();
642 }
643 
ReduceInt64Sub(GateRef gate)644 GateRef InstructionCombine::ReduceInt64Sub(GateRef gate)
645 {
646     Int64BinopMatcher m(gate, circuit_);
647     // x - 0 => x
648     if (m.Right().Is(0)) {
649         return (m.Left().Gate());
650     }
651     if (m.IsFoldable()) {
652         return builder_.Int64(SubWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
653     }
654     // x - x => 0
655     if (m.LeftEqualsRight()) {
656         return builder_.Int64(0);
657     }
658     // x - K => x + -K
659     if (m.Right().HasResolvedValue()) {
660         auto newGate =
661             builder_.Int64Add(m.Left().Gate(), builder_.Int64(NegateWithWraparound(m.Right().ResolvedValue())));
662         return ReplaceOld(gate, newGate);
663     }
664     return Circuit::NullGate();
665 }
666 
ReduceInt32Sub(GateRef gate)667 GateRef InstructionCombine::ReduceInt32Sub(GateRef gate)
668 {
669     Int32BinopMatcher m(gate, circuit_);
670     // x - 0 => x
671     if (m.Right().Is(0)) {
672         return (m.Left().Gate());
673     }
674     if (m.IsFoldable()) {
675         return builder_.Int32(SubWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
676     }
677     // x - x => 0
678     if (m.LeftEqualsRight()) {
679         return builder_.Int32(0);
680     }
681     // x - K => x + -K
682     if (m.Right().HasResolvedValue()) {
683         auto newGate =
684             builder_.Int32Add(m.Left().Gate(), builder_.Int32(NegateWithWraparound(m.Right().ResolvedValue())));
685         return ReplaceOld(gate, newGate);
686     }
687     return Circuit::NullGate();
688 }
689 
ReduceInt64Mul(GateRef gate)690 GateRef InstructionCombine::ReduceInt64Mul(GateRef gate)
691 {
692     Int64BinopMatcher m(gate, circuit_);
693     // x * 0 => 0
694     if (m.Right().Is(0)) {
695         return m.Right().Gate();
696     }
697     // x * 1 => x
698     if (m.Right().Is(1)) {
699         return m.Left().Gate();
700     }
701     // K * K => K  (K stands for arbitrary constants)
702     if (m.IsFoldable()) {
703         return builder_.Int64(MulWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
704     }
705     // x * -1 => 0 - x
706     if (m.Right().Is(-1)) {
707         auto newGate = builder_.Int64Sub(builder_.Int64(0), m.Left().Gate());
708         return ReplaceOld(gate, newGate);
709     }
710     // x * 2^n => x << n
711     if (m.Right().IsPowerOf2()) {
712         auto newGate = builder_.Int64LSL(m.Left().Gate(), builder_.Int64(WhichPowerOfTwo(m.Right().ResolvedValue())));
713         return ReplaceOld(gate, newGate);
714     }
715 
716     // (x * Int64Constant(a)) * Int64Constant(b)) => x * Int64Constant(a * b)
717     if (m.Right().HasResolvedValue() && m.Left().IsmInt64Mul()) {
718         Int64BinopMatcher n(m.Left().Gate(), circuit_);
719         if (n.Right().HasResolvedValue() && m.OwnsInput(m.Left().Gate())) {
720             acc_.ReplaceValueIn(gate, n.Left().Gate(), 0);
721             acc_.ReplaceValueIn(
722                 gate, builder_.Int64(MulWithWraparound(n.Right().ResolvedValue(), m.Right().ResolvedValue())), 1);
723             return gate;
724         }
725     }
726 
727     return Circuit::NullGate();
728 }
729 
ReduceInt32Mul(GateRef gate)730 GateRef InstructionCombine::ReduceInt32Mul(GateRef gate)
731 {
732     Int32BinopMatcher m(gate, circuit_);
733     // x * 0 => 0
734     if (m.Right().Is(0)) {
735         return m.Right().Gate();
736     }
737     // x * 1 => x
738     if (m.Right().Is(1)) {
739         return m.Left().Gate();
740     }
741     // K * K => K  (K stands for arbitrary constants)
742     if (m.IsFoldable()) {
743         return builder_.Int32(MulWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
744     }
745     // x * -1 => 0 - x
746     if (m.Right().Is(-1)) {
747         auto newGate = builder_.Int32Sub(builder_.Int32(0), m.Left().Gate());
748         return ReplaceOld(gate, newGate);
749     }
750     // x * 2^n => x << n
751     if (m.Right().IsPowerOf2()) {
752         auto newGate = builder_.Int32LSL(m.Left().Gate(), builder_.Int32(WhichPowerOfTwo(m.Right().ResolvedValue())));
753         return ReplaceOld(gate, newGate);
754     }
755 
756     // (x * Int32Constant(a)) * Int32Constant(b)) => x * Int32Constant(a * b)
757     if (m.Right().HasResolvedValue() && m.Left().IsmInt32Mul()) {
758         Int32BinopMatcher n(m.Left().Gate(), circuit_);
759         if (n.Right().HasResolvedValue() && m.OwnsInput(m.Left().Gate())) {
760             acc_.ReplaceValueIn(gate, n.Left().Gate(), 0);
761             acc_.ReplaceValueIn(
762                 gate, builder_.Int32(MulWithWraparound(n.Right().ResolvedValue(), m.Right().ResolvedValue())), 1);
763             return gate;
764         }
765     }
766 
767     return Circuit::NullGate();
768 }
769 
770 
ReduceInt64Div(GateRef gate)771 GateRef InstructionCombine::ReduceInt64Div(GateRef gate)
772 {
773     Int64BinopMatcher m(gate, circuit_);
774     // 0 / x => 0
775     if (m.Left().Is(0)) {
776         return m.Left().Gate();
777     }
778     // x / 0 => 0
779     if (m.Right().Is(0)) {
780         return m.Right().Gate();
781     }
782     // x / 1 => x
783     if (m.Right().Is(1)) {
784         return m.Left().Gate();
785     }
786     // K / K => K
787     if (m.IsFoldable()) {
788         return builder_.Int64(SignedDiv64(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
789     }
790     // x / -1 => 0 - x
791     if (m.Right().Is(-1)) {
792         auto newGate = builder_.Int64Sub(builder_.Int64(0), m.Left().Gate());
793         return ReplaceOld(gate, newGate);
794     }
795 
796     //  x/-K => 0-(x/K)
797     if (m.Right().HasResolvedValue()) {
798         int64_t const divisor = m.Right().ResolvedValue();
799         if (divisor < 0) {
800             auto newDiv = builder_.Int64Div(m.Left().Gate(), builder_.Int64(abs(m.Right().ResolvedValue())));
801             auto newGate = builder_.Int64Sub(builder_.Int64(0), newDiv);
802             return ReplaceOld(gate, newGate);
803         }
804     }
805     return Circuit::NullGate();
806 }
807 
ReduceInt32Div(GateRef gate)808 GateRef InstructionCombine::ReduceInt32Div(GateRef gate)
809 {
810     Int32BinopMatcher m(gate, circuit_);
811     // 0 / x => 0
812     if (m.Left().Is(0)) {
813         return m.Left().Gate();
814     }
815     // x / 0 => 0
816     if (m.Right().Is(0)) {
817         return m.Right().Gate();
818     }
819     // x / 1 => x
820     if (m.Right().Is(1)) {
821         return m.Left().Gate();
822     }
823     // K / K => K
824     if (m.IsFoldable()) {
825         return builder_.Int32(SignedDiv32(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
826     }
827     // x / -1 => 0 - x
828     if (m.Right().Is(-1)) {
829         auto newGate = builder_.Int32Sub(builder_.Int32(0), m.Left().Gate());
830         return ReplaceOld(gate, newGate);
831     }
832 
833     //  x/-K => 0-(x/K)
834     if (m.Right().HasResolvedValue()) {
835         int32_t const divisor = m.Right().ResolvedValue();
836         if (divisor < 0) {
837             auto newDiv = builder_.Int32Div(m.Left().Gate(), builder_.Int32(abs(m.Right().ResolvedValue())));
838             auto newGate = builder_.Int32Sub(builder_.Int32(0), newDiv);
839             return ReplaceOld(gate, newGate);
840         }
841     }
842     return Circuit::NullGate();
843 }
844 
ReduceDoubleAdd(GateRef gate)845 GateRef InstructionCombine::ReduceDoubleAdd(GateRef gate)
846 {
847     Float64BinopMatcher m(gate, circuit_);
848     // x + NaN => NaN
849     if (m.Right().IsNaN()) {
850         return builder_.NanValue();
851     }
852     // NaN + x => NaN
853     if (m.Left().IsNaN()) {
854         return builder_.NanValue();
855     }
856     // K + K => K  (K stands for arbitrary constants)
857     if (m.IsFoldable()) {
858         return builder_.Double(m.Left().ResolvedValue() + m.Right().ResolvedValue());
859     }
860     return Circuit::NullGate();
861 }
ReduceDoubleSub(GateRef gate)862 GateRef InstructionCombine::ReduceDoubleSub(GateRef gate)
863 {
864     Float64BinopMatcher m(gate, circuit_);
865     // x - NaN => NaN
866     if (m.Right().IsNaN()) {
867         return builder_.NanValue();
868     }
869     // NaN - x => NaN
870     if (m.Left().IsNaN()) {
871         return builder_.NanValue();
872     }
873     // L - R => (L - R)
874     if (m.IsFoldable()) {
875         return builder_.Double(m.Left().ResolvedValue() - m.Right().ResolvedValue());
876     }
877     return Circuit::NullGate();
878 }
879 
ReduceDoubleMul(GateRef gate)880 GateRef InstructionCombine::ReduceDoubleMul(GateRef gate)
881 {
882     Float64BinopMatcher m(gate, circuit_);
883     if (m.Right().Is(-1)) { // x * -1.0 => -0.0 - x
884         auto newGate = builder_.DoubleSub(builder_.Double(-0.0), m.Left().Gate());
885         return ReplaceOld(gate, newGate);
886     }
887     if (m.Right().IsNaN()) { // x * NaN => NaN
888         return builder_.NanValue();
889     }
890     if (m.IsFoldable()) { // K * K => K  (K stands for arbitrary constants)
891         return builder_.Double(m.Left().ResolvedValue() * m.Right().ResolvedValue());
892     }
893     if (m.Right().Is(2)) { // x * 2.0 => x + x
894         auto newGate = builder_.DoubleAdd(m.Left().Gate(), m.Left().Gate());
895         return ReplaceOld(gate, newGate);
896     }
897     return Circuit::NullGate();
898 }
899 
ReduceDoubleDiv(GateRef gate)900 GateRef InstructionCombine::ReduceDoubleDiv(GateRef gate)
901 {
902     Float64BinopMatcher m(gate, circuit_);
903 
904     if (m.Right().IsNaN()) { // x / NaN => NaN
905         return builder_.NanValue();
906     }
907     if (m.Left().IsNaN()) { // NaN / x => NaN
908         return builder_.NanValue();
909     }
910     if (m.IsFoldable()) { // K / K => K  (K stands for arbitrary constants)
911         return builder_.Double(Divide(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
912     }
913 
914     return Circuit::NullGate();
915 }
916 
ReduceInt32Mod(GateRef gate)917 GateRef InstructionCombine::ReduceInt32Mod(GateRef gate)
918 {
919     Int32BinopMatcher m(gate, circuit_);
920     // 0 % x  => 0
921     if (m.Left().Is(0)) {
922         return m.Left().Gate();
923     }
924     // x % 0  => 0
925     if (m.Right().Is(0)) {
926         return m.Right().Gate();
927     }
928     // x % 1  => 0
929     if (m.Right().Is(1)) {
930         return builder_.Int32(0);
931     }
932     // x % -1 => 0
933     if (m.Right().Is(-1)) {
934         return builder_.Int32(0);
935     }
936     // x % x  => 0
937     if (m.LeftEqualsRight()) {
938         return builder_.Int32(0);
939     }
940     // K % K => K  (K stands for arbitrary constants)
941     if (m.IsFoldable()) {
942         return builder_.Int32(SignedMod32(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
943     }
944 
945     return Circuit::NullGate();
946 }
947 
ReduceDoubleMod(GateRef gate)948 GateRef InstructionCombine::ReduceDoubleMod(GateRef gate)
949 {
950     Float64BinopMatcher m(gate, circuit_);
951     if (m.Right().Is(0)) { // x % 0 => NaN
952         return builder_.NanValue();
953     }
954     if (m.Right().IsNaN()) { // x % NaN => NaN
955         return builder_.NanValue();
956     }
957     if (m.Left().IsNaN()) { // NaN % x => NaN
958         return builder_.NanValue();
959     }
960     return Circuit::NullGate();
961 }
962 
963 
ReduceWord64And(GateRef gate)964 GateRef InstructionCombine::ReduceWord64And(GateRef gate)
965 {
966     Int64BinopMatcher m(gate, circuit_);
967     // x & 0  => 0
968     if (m.Right().Is(0)) {
969         return m.Right().Gate();
970     }
971     // x & -1 => x
972     if (m.Right().Is(-1)) {
973         return m.Left().Gate();
974     }
975     // CMP & 1 => CMP
976     if (m.Left().IsIcmp() && m.Right().Is(1)) {
977         return m.Left().Gate();
978     }
979     // K & K  => K  (K stands for arbitrary constants)
980     if (m.IsFoldable()) {
981         return builder_.Int64(static_cast<uint64_t>(m.Left().ResolvedValue()) &
982             static_cast<uint64_t>(m.Right().ResolvedValue()));
983     }
984     // x & x => x
985     if (m.LeftEqualsRight()) {
986         return m.Left().Gate();
987     }
988     // (x & K) & K => x & K
989     if (m.Left().IsmInt64And() && m.Right().HasResolvedValue()) {
990         Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
991         if (mleft.Right().HasResolvedValue()) {
992             auto newGate = builder_.Int64And(
993                 mleft.Left().Gate(), builder_.Int64(static_cast<uint64_t>(m.Right().ResolvedValue()) &
994                 static_cast<uint64_t>(mleft.Right().ResolvedValue())));
995             return ReplaceOld(gate, newGate);
996         }
997     }
998     return Circuit::NullGate();
999 }
1000 
ReduceWord32And(GateRef gate)1001 GateRef InstructionCombine::ReduceWord32And(GateRef gate)
1002 {
1003     Int32BinopMatcher m(gate, circuit_);
1004     // x & 0  => 0
1005     if (m.Right().Is(0)) {
1006         return m.Right().Gate();
1007     }
1008     // x & -1 => x
1009     if (m.Right().Is(-1)) {
1010         return m.Left().Gate();
1011     }
1012     // CMP & 1 => CMP
1013     if (m.Left().IsIcmp() && m.Right().Is(1)) {
1014         return m.Left().Gate();
1015     }
1016     // K & K  => K  (K stands for arbitrary constants)
1017     if (m.IsFoldable()) {
1018         return builder_.Int32(static_cast<uint32_t>(m.Left().ResolvedValue()) &
1019             static_cast<uint32_t>(m.Right().ResolvedValue()));
1020     }
1021     // x & x => x
1022     if (m.LeftEqualsRight()) {
1023         return m.Left().Gate();
1024     }
1025     // (x & K) & K => x & K
1026     if (m.Left().IsmInt32And() && m.Right().HasResolvedValue()) {
1027         Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
1028         if (mleft.Right().HasResolvedValue()) {
1029             auto newGate = builder_.Int32And(
1030                 mleft.Left().Gate(), builder_.Int32(static_cast<uint32_t>(m.Right().ResolvedValue()) &
1031                 static_cast<uint32_t>(mleft.Right().ResolvedValue())));
1032             return ReplaceOld(gate, newGate);
1033         }
1034     }
1035     return Circuit::NullGate();
1036 }
1037 
ReduceWord64Or(GateRef gate)1038 GateRef InstructionCombine::ReduceWord64Or(GateRef gate)
1039 {
1040     Int64BinopMatcher m(gate, circuit_);
1041     // x | 0  => x
1042     if (m.Right().Is(0)) {
1043         return m.Left().Gate();
1044     }
1045     // x | -1 => -1
1046     if (m.Right().Is(-1)) {
1047         return m.Right().Gate();
1048     }
1049     // K | K  => K  (K stands for arbitrary constants)
1050     if (m.IsFoldable()) {
1051         return builder_.Int64(static_cast<uint64_t>(m.Left().ResolvedValue()) |
1052             static_cast<uint64_t>(m.Right().ResolvedValue()));
1053     }
1054     // x | x => x
1055     if (m.LeftEqualsRight()) {
1056         return m.Left().Gate();
1057     }
1058 
1059     // (x & K1) | K2 => x | K2 if K2 has ones for every zero bit in K1.
1060     if (m.Right().HasResolvedValue() && m.Left().IsmInt64And()) {
1061         Int64BinopMatcher mand(m.Left().Gate(), circuit_);
1062         if (mand.Right().HasResolvedValue()) {
1063             if ((m.Right().ResolvedValue() | mand.Right().ResolvedValue()) == -1) {
1064                 acc_.ReplaceValueIn(gate, mand.Left().Gate(), 0);
1065                 return gate;
1066             }
1067         }
1068     }
1069     return Circuit::NullGate();
1070 }
1071 
ReduceWord32Or(GateRef gate)1072 GateRef InstructionCombine::ReduceWord32Or(GateRef gate)
1073 {
1074     Int32BinopMatcher m(gate, circuit_);
1075     // x | 0  => x
1076     if (m.Right().Is(0)) {
1077         return m.Left().Gate();
1078     }
1079     // x | -1 => -1
1080     if (m.Right().Is(-1)) {
1081         return m.Right().Gate();
1082     }
1083     // K | K  => K  (K stands for arbitrary constants)
1084     if (m.IsFoldable()) {
1085         return builder_.Int32(static_cast<uint32_t>(m.Left().ResolvedValue()) |
1086             static_cast<uint32_t>(m.Right().ResolvedValue()));
1087     }
1088     // x | x => x
1089     if (m.LeftEqualsRight()) {
1090         return m.Left().Gate();
1091     }
1092 
1093     // (x & K1) | K2 => x | K2 if K2 has ones for every zero bit in K1.
1094     if (m.Right().HasResolvedValue() && m.Left().IsmInt32And()) {
1095         Int32BinopMatcher mand(m.Left().Gate(), circuit_);
1096         if (mand.Right().HasResolvedValue()) {
1097             if ((m.Right().ResolvedValue() | mand.Right().ResolvedValue()) == -1) {
1098                 acc_.ReplaceValueIn(gate, mand.Left().Gate(), 0);
1099                 return gate;
1100             }
1101         }
1102     }
1103 
1104     return Circuit::NullGate();
1105 }
1106 
ReduceWord64Xor(GateRef gate)1107 GateRef InstructionCombine::ReduceWord64Xor(GateRef gate)
1108 {
1109     Int64BinopMatcher m(gate, circuit_);
1110     // x ^ 0 => x
1111     if (m.Right().Is(0)) {
1112         return m.Left().Gate();
1113     }
1114     // K ^ K => K  (K stands for arbitrary constants)
1115     if (m.IsFoldable()) {
1116         return builder_.Int64(static_cast<uint64_t>(m.Left().ResolvedValue()) ^
1117             static_cast<uint64_t>(m.Right().ResolvedValue()));
1118     }
1119     if (m.LeftEqualsRight()) {
1120         return builder_.Int64(0); // x ^ x => 0
1121     }
1122     // (x ^ -1) ^ -1 => x
1123     if (m.Left().IsmInt64Xor() && m.Right().Is(-1)) {
1124         Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
1125         if (mleft.Right().Is(-1)) {
1126             return mleft.Left().Gate();
1127         }
1128     }
1129     return Circuit::NullGate();
1130 }
1131 
ReduceWord32Xor(GateRef gate)1132 GateRef InstructionCombine::ReduceWord32Xor(GateRef gate)
1133 {
1134     Int32BinopMatcher m(gate, circuit_);
1135     // x ^ 0 => x
1136     if (m.Right().Is(0)) {
1137         return m.Left().Gate();
1138     }
1139     // K ^ K => K  (K stands for arbitrary constants)
1140     if (m.IsFoldable()) {
1141         return builder_.Int32(static_cast<uint32_t>(m.Left().ResolvedValue()) ^
1142             static_cast<uint32_t>(m.Right().ResolvedValue()));
1143     }
1144     if (m.LeftEqualsRight()) {
1145         return builder_.Int32(0); // x ^ x => 0
1146     }
1147     // (x ^ -1) ^ -1 => x
1148     if (m.Left().IsmInt32Xor() && m.Right().Is(-1)) {
1149         Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
1150         if (mleft.Right().Is(-1)) {
1151             return mleft.Left().Gate();
1152         }
1153     }
1154     return Circuit::NullGate();
1155 }
ReduceWord64Lsr(GateRef gate)1156 GateRef InstructionCombine::ReduceWord64Lsr(GateRef gate)
1157 {
1158     Uint64BinopMatcher m(gate, circuit_);
1159 
1160     // x >>> 0 => x
1161     if (m.Right().Is(0)) {
1162         return m.Left().Gate();
1163     }
1164     if (m.IsFoldable()) {
1165         // The '63' here is used as a mask to limit the shift amount to 0-63 bits, preventing overflow.
1166         return builder_.Int64(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 63));
1167     }
1168     return Circuit::NullGate();
1169 }
1170 
ReduceWord32Lsr(GateRef gate)1171 GateRef InstructionCombine::ReduceWord32Lsr(GateRef gate)
1172 {
1173     Uint32BinopMatcher m(gate, circuit_);
1174     // x >>> 0 => x
1175     if (m.Right().Is(0)) {
1176         return m.Left().Gate();
1177     }
1178     if (m.IsFoldable()) {
1179         // The '31' here is used as a mask to limit the shift amount to 0-31 bits, preventing overflow.
1180         return builder_.Int32(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 31));
1181     }
1182     // (m >>> s) == 0 implies ((x & m) >>> s) == 0
1183     if (m.Left().IsmInt32And() && m.Right().HasResolvedValue()) {
1184         Uint32BinopMatcher mleft(m.Left().Gate(), circuit_);
1185         if (mleft.Right().HasResolvedValue()) {
1186             uint32_t shift = m.Right().ResolvedValue() & 31;
1187             uint32_t mask = mleft.Right().ResolvedValue();
1188             if ((mask >> shift) == 0) {
1189                 return builder_.Int32(0);
1190             }
1191         }
1192     }
1193     return Circuit::NullGate();
1194 }
1195 
ReduceWord64Asr(GateRef gate)1196 GateRef InstructionCombine::ReduceWord64Asr(GateRef gate)
1197 {
1198     Int64BinopMatcher m(gate, circuit_);
1199     // x >> 0 => x
1200     if (m.Right().Is(0)) {
1201         return m.Left().Gate();
1202     }
1203     if (m.IsFoldable()) {
1204         // The '63' here is used as a mask to limit the shift amount to 0-63 bits, preventing overflow.
1205         return builder_.Int64(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 63));
1206     }
1207     return Circuit::NullGate();
1208 }
1209 
ReduceWord32Asr(GateRef gate)1210 GateRef InstructionCombine::ReduceWord32Asr(GateRef gate)
1211 {
1212     Int32BinopMatcher m(gate, circuit_);
1213     // x >> 0 => x
1214     if (m.Right().Is(0)) {
1215         return m.Left().Gate();
1216     }
1217     if (m.IsFoldable()) {
1218         // The '31' here is used as a mask to limit the shift amount to 0-31 bits, preventing overflow.
1219         return builder_.Int32(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 31));
1220     }
1221     if (m.Left().IsmInt32LSL()) {
1222         Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
1223         if (mleft.Left().IsIcmp()) {
1224             // Check if the right shift amount is 31 (logical shift by 31 bits).
1225             if (m.Right().Is(31) && mleft.Right().Is(31)) {
1226                 auto newGate = builder_.Int32Sub(builder_.Int32(0), mleft.Left().Gate());
1227                 return ReplaceOld(gate, newGate);
1228             }
1229         } else if (mleft.Left().IsLoad()) {
1230             // Check if the right shift amount is 24 (logical shift by 24 bits).
1231             if (m.Right().Is(24) && mleft.Right().Is(24) &&
1232                 acc_.GetMachineType(mleft.Left().Gate()) == MachineType::I8) {
1233                 return mleft.Left().Gate();
1234             }
1235         }
1236     }
1237     return Circuit::NullGate();
1238 }
1239 
ReduceWord64Lsl(GateRef gate)1240 GateRef InstructionCombine::ReduceWord64Lsl(GateRef gate)
1241 {
1242     Int64BinopMatcher m(gate, circuit_);
1243     // x << 0 => x
1244     if (m.Right().Is(0)) {
1245         return m.Left().Gate();
1246     }
1247     if (m.IsFoldable()) {
1248         return builder_.Int64(ShlWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
1249     }
1250     // Check if the right shift amount is in the range of 1 to 63 bits (inclusive).
1251     if (m.Right().IsInRange(1, 63) && (m.Left().IsmInt64ASR() || m.Left().IsmInt64LSR())) {
1252         Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
1253         // (x >>> K) << K => x & ~(2^K - 1)
1254         // (x >> K) << K => x & ~(2^K - 1)
1255         if (mleft.Right().Is(m.Right().ResolvedValue())) {
1256             auto newGate = builder_.Int64And(
1257                 mleft.Left().Gate(), builder_.Int64(std::numeric_limits<uint64_t>::max() << m.Right().ResolvedValue()));
1258             return ReplaceOld(gate, newGate);
1259         }
1260     }
1261     return Circuit::NullGate();
1262 }
ReduceWord32Lsl(GateRef gate)1263 GateRef InstructionCombine::ReduceWord32Lsl(GateRef gate)
1264 {
1265     Int32BinopMatcher m(gate, circuit_);
1266     // x << 0 => x
1267     if (m.Right().Is(0)) {
1268         return m.Left().Gate();
1269     }
1270     if (m.IsFoldable()) {
1271         return builder_.Int32(ShlWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
1272     }
1273 
1274     // Check if the right shift amount is in the range of 1 to 31 bits (inclusive).
1275     if (m.Right().IsInRange(1, 31) && (m.Left().IsmInt32ASR() || m.Left().IsmInt32LSR())) {
1276         Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
1277         // (x >>> K) << K => x & ~(2^K - 1)
1278         // (x >> K) << K => x & ~(2^K - 1)
1279         if (mleft.Right().Is(m.Right().ResolvedValue())) {
1280             auto newGate = builder_.Int32And(
1281                 mleft.Left().Gate(), builder_.Int32(std::numeric_limits<uint64_t>::max() << m.Right().ResolvedValue()));
1282             return ReplaceOld(gate, newGate);
1283         }
1284     }
1285     return Circuit::NullGate();
1286 }
1287 
1288 } // namespace panda::ecmascript::kungfu