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