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