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 (divisor < 0) {
670 auto newDiv = builder_.Int64Div(m.Left().Gate(), builder_.Int64(abs(m.Right().ResolvedValue())));
671 auto newGate = builder_.Int64Sub(builder_.Int64(0), newDiv);
672 return ReplaceOld(gate, newGate);
673 }
674 }
675 return Circuit::NullGate();
676 }
677
ReduceInt32Div(GateRef gate)678 GateRef InstructionCombine::ReduceInt32Div(GateRef gate)
679 {
680 Int32BinopMatcher m(gate, circuit_);
681 // 0 / x => 0
682 if (m.Left().Is(0)) {
683 return m.Left().Gate();
684 }
685 // x / 0 => 0
686 if (m.Right().Is(0)) {
687 return m.Right().Gate();
688 }
689 // x / 1 => x
690 if (m.Right().Is(1)) {
691 return m.Left().Gate();
692 }
693 // K / K => K
694 if (m.IsFoldable()) {
695 return builder_.Int32(base::SignedDiv32(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
696 }
697 // x / -1 => 0 - x
698 if (m.Right().Is(-1)) {
699 auto newGate = builder_.Int32Sub(builder_.Int32(0), m.Left().Gate());
700 return ReplaceOld(gate, newGate);
701 }
702
703 // x/-K => 0-(x/K)
704 if (m.Right().HasResolvedValue()) {
705 int32_t const divisor = m.Right().ResolvedValue();
706 if (divisor < 0) {
707 auto newDiv = builder_.Int32Div(m.Left().Gate(), builder_.Int32(abs(m.Right().ResolvedValue())));
708 auto newGate = builder_.Int32Sub(builder_.Int32(0), newDiv);
709 return ReplaceOld(gate, newGate);
710 }
711 }
712 return Circuit::NullGate();
713 }
714
ReduceDoubleAdd(GateRef gate)715 GateRef InstructionCombine::ReduceDoubleAdd(GateRef gate)
716 {
717 Float64BinopMatcher m(gate, circuit_);
718 // x + NaN => NaN
719 if (m.Right().IsNaN()) {
720 return builder_.NanValue();
721 }
722 // NaN + x => NaN
723 if (m.Left().IsNaN()) {
724 return builder_.NanValue();
725 }
726 // K + K => K (K stands for arbitrary constants)
727 if (m.IsFoldable()) {
728 return builder_.Double(m.Left().ResolvedValue() + m.Right().ResolvedValue());
729 }
730 return Circuit::NullGate();
731 }
ReduceDoubleSub(GateRef gate)732 GateRef InstructionCombine::ReduceDoubleSub(GateRef gate)
733 {
734 Float64BinopMatcher m(gate, circuit_);
735 // x - NaN => NaN
736 if (m.Right().IsNaN()) {
737 return builder_.NanValue();
738 }
739 // NaN - x => NaN
740 if (m.Left().IsNaN()) {
741 return builder_.NanValue();
742 }
743 // L - R => (L - R)
744 if (m.IsFoldable()) {
745 return builder_.Double(m.Left().ResolvedValue() - m.Right().ResolvedValue());
746 }
747 return Circuit::NullGate();
748 }
749
ReduceDoubleMul(GateRef gate)750 GateRef InstructionCombine::ReduceDoubleMul(GateRef gate)
751 {
752 Float64BinopMatcher m(gate, circuit_);
753 if (m.Right().Is(-1)) { // x * -1.0 => -0.0 - x
754 auto newGate = builder_.DoubleSub(builder_.Double(-0.0), m.Left().Gate());
755 return ReplaceOld(gate, newGate);
756 }
757 if (m.Right().IsNaN()) { // x * NaN => NaN
758 return builder_.NanValue();
759 }
760 if (m.IsFoldable()) { // K * K => K (K stands for arbitrary constants)
761 return builder_.Double(m.Left().ResolvedValue() * m.Right().ResolvedValue());
762 }
763 if (m.Right().Is(2)) { // x * 2.0 => x + x
764 auto newGate = builder_.DoubleAdd(m.Left().Gate(), m.Left().Gate());
765 return ReplaceOld(gate, newGate);
766 }
767 return Circuit::NullGate();
768 }
769
ReduceDoubleDiv(GateRef gate)770 GateRef InstructionCombine::ReduceDoubleDiv(GateRef gate)
771 {
772 Float64BinopMatcher m(gate, circuit_);
773
774 if (m.Right().IsNaN()) { // x / NaN => NaN
775 return builder_.NanValue();
776 }
777 if (m.Left().IsNaN()) { // NaN / x => NaN
778 return builder_.NanValue();
779 }
780 if (m.IsFoldable()) { // K / K => K (K stands for arbitrary constants)
781 return builder_.Double(base::Divide(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
782 }
783
784 return Circuit::NullGate();
785 }
786
ReduceInt32Mod(GateRef gate)787 GateRef InstructionCombine::ReduceInt32Mod(GateRef gate)
788 {
789 Int32BinopMatcher m(gate, circuit_);
790 // 0 % x => 0
791 if (m.Left().Is(0)) {
792 return m.Left().Gate();
793 }
794 // x % 0 => 0
795 if (m.Right().Is(0)) {
796 return m.Right().Gate();
797 }
798 // x % 1 => 0
799 if (m.Right().Is(1)) {
800 return builder_.Int32(0);
801 }
802 // x % -1 => 0
803 if (m.Right().Is(-1)) {
804 return builder_.Int32(0);
805 }
806 // x % x => 0
807 if (m.LeftEqualsRight()) {
808 return builder_.Int32(0);
809 }
810 // K % K => K (K stands for arbitrary constants)
811 if (m.IsFoldable()) {
812 return builder_.Int32(base::SignedMod32(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
813 }
814
815 return Circuit::NullGate();
816 }
817
ReduceDoubleMod(GateRef gate)818 GateRef InstructionCombine::ReduceDoubleMod(GateRef gate)
819 {
820 Float64BinopMatcher m(gate, circuit_);
821 if (m.Right().Is(0)) { // x % 0 => NaN
822 return builder_.NanValue();
823 }
824 if (m.Right().IsNaN()) { // x % NaN => NaN
825 return builder_.NanValue();
826 }
827 if (m.Left().IsNaN()) { // NaN % x => NaN
828 return builder_.NanValue();
829 }
830 return Circuit::NullGate();
831 }
832
833
ReduceWord64And(GateRef gate)834 GateRef InstructionCombine::ReduceWord64And(GateRef gate)
835 {
836 Int64BinopMatcher m(gate, circuit_);
837 // x & 0 => 0
838 if (m.Right().Is(0)) {
839 return m.Right().Gate();
840 }
841 // x & -1 => x
842 if (m.Right().Is(-1)) {
843 return m.Left().Gate();
844 }
845 // CMP & 1 => CMP
846 if (m.Left().IsIcmp() && m.Right().Is(1)) {
847 return m.Left().Gate();
848 }
849 // K & K => K (K stands for arbitrary constants)
850 if (m.IsFoldable()) {
851 return builder_.Int64(static_cast<uint64_t>(m.Left().ResolvedValue()) &
852 static_cast<uint64_t>(m.Right().ResolvedValue()));
853 }
854 // x & x => x
855 if (m.LeftEqualsRight()) {
856 return m.Left().Gate();
857 }
858 // (x & K) & K => x & K
859 if (m.Left().IsmInt64And() && m.Right().HasResolvedValue()) {
860 Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
861 if (mleft.Right().HasResolvedValue()) {
862 auto newGate = builder_.Int64And(
863 mleft.Left().Gate(), builder_.Int64(static_cast<uint64_t>(m.Right().ResolvedValue()) &
864 static_cast<uint64_t>(mleft.Right().ResolvedValue())));
865 return ReplaceOld(gate, newGate);
866 }
867 }
868 return Circuit::NullGate();
869 }
870
ReduceWord32And(GateRef gate)871 GateRef InstructionCombine::ReduceWord32And(GateRef gate)
872 {
873 Int32BinopMatcher m(gate, circuit_);
874 // x & 0 => 0
875 if (m.Right().Is(0)) {
876 return m.Right().Gate();
877 }
878 // x & -1 => x
879 if (m.Right().Is(-1)) {
880 return m.Left().Gate();
881 }
882 // CMP & 1 => CMP
883 if (m.Left().IsIcmp() && m.Right().Is(1)) {
884 return m.Left().Gate();
885 }
886 // K & K => K (K stands for arbitrary constants)
887 if (m.IsFoldable()) {
888 return builder_.Int32(static_cast<uint32_t>(m.Left().ResolvedValue()) &
889 static_cast<uint32_t>(m.Right().ResolvedValue()));
890 }
891 // x & x => x
892 if (m.LeftEqualsRight()) {
893 return m.Left().Gate();
894 }
895 // (x & K) & K => x & K
896 if (m.Left().IsmInt32And() && m.Right().HasResolvedValue()) {
897 Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
898 if (mleft.Right().HasResolvedValue()) {
899 auto newGate = builder_.Int32And(
900 mleft.Left().Gate(), builder_.Int32(static_cast<uint32_t>(m.Right().ResolvedValue()) &
901 static_cast<uint32_t>(mleft.Right().ResolvedValue())));
902 return ReplaceOld(gate, newGate);
903 }
904 }
905 return Circuit::NullGate();
906 }
907
ReduceWord64Or(GateRef gate)908 GateRef InstructionCombine::ReduceWord64Or(GateRef gate)
909 {
910 Int64BinopMatcher m(gate, circuit_);
911 // x | 0 => x
912 if (m.Right().Is(0)) {
913 return m.Left().Gate();
914 }
915 // x | -1 => -1
916 if (m.Right().Is(-1)) {
917 return m.Right().Gate();
918 }
919 // K | K => K (K stands for arbitrary constants)
920 if (m.IsFoldable()) {
921 return builder_.Int64(static_cast<uint64_t>(m.Left().ResolvedValue()) |
922 static_cast<uint64_t>(m.Right().ResolvedValue()));
923 }
924 // x | x => x
925 if (m.LeftEqualsRight()) {
926 return m.Left().Gate();
927 }
928
929 // (x & K1) | K2 => x | K2 if K2 has ones for every zero bit in K1.
930 if (m.Right().HasResolvedValue() && m.Left().IsmInt64And()) {
931 Int64BinopMatcher mand(m.Left().Gate(), circuit_);
932 if (mand.Right().HasResolvedValue()) {
933 if ((m.Right().ResolvedValue() | mand.Right().ResolvedValue()) == -1) {
934 acc_.ReplaceValueIn(gate, mand.Left().Gate(), 0);
935 return gate;
936 }
937 }
938 }
939 return Circuit::NullGate();
940 }
941
ReduceWord32Or(GateRef gate)942 GateRef InstructionCombine::ReduceWord32Or(GateRef gate)
943 {
944 Int32BinopMatcher m(gate, circuit_);
945 // x | 0 => x
946 if (m.Right().Is(0)) {
947 return m.Left().Gate();
948 }
949 // x | -1 => -1
950 if (m.Right().Is(-1)) {
951 return m.Right().Gate();
952 }
953 // K | K => K (K stands for arbitrary constants)
954 if (m.IsFoldable()) {
955 return builder_.Int32(static_cast<uint32_t>(m.Left().ResolvedValue()) |
956 static_cast<uint32_t>(m.Right().ResolvedValue()));
957 }
958 // x | x => x
959 if (m.LeftEqualsRight()) {
960 return m.Left().Gate();
961 }
962
963 // (x & K1) | K2 => x | K2 if K2 has ones for every zero bit in K1.
964 if (m.Right().HasResolvedValue() && m.Left().IsmInt32And()) {
965 Int32BinopMatcher mand(m.Left().Gate(), circuit_);
966 if (mand.Right().HasResolvedValue()) {
967 if ((m.Right().ResolvedValue() | mand.Right().ResolvedValue()) == -1) {
968 acc_.ReplaceValueIn(gate, mand.Left().Gate(), 0);
969 return gate;
970 }
971 }
972 }
973
974 return Circuit::NullGate();
975 }
976
ReduceWord64Xor(GateRef gate)977 GateRef InstructionCombine::ReduceWord64Xor(GateRef gate)
978 {
979 Int64BinopMatcher m(gate, circuit_);
980 // x ^ 0 => x
981 if (m.Right().Is(0)) {
982 return m.Left().Gate();
983 }
984 // K ^ K => K (K stands for arbitrary constants)
985 if (m.IsFoldable()) {
986 return builder_.Int64(m.Left().ResolvedValue() ^ m.Right().ResolvedValue());
987 }
988 if (m.LeftEqualsRight()) {
989 return builder_.Int64(0); // x ^ x => 0
990 }
991 // (x ^ -1) ^ -1 => x
992 if (m.Left().IsmInt64Xor() && m.Right().Is(-1)) {
993 Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
994 if (mleft.Right().Is(-1)) {
995 return mleft.Left().Gate();
996 }
997 }
998 return Circuit::NullGate();
999 }
1000
ReduceWord32Xor(GateRef gate)1001 GateRef InstructionCombine::ReduceWord32Xor(GateRef gate)
1002 {
1003 Int32BinopMatcher m(gate, circuit_);
1004 // x ^ 0 => x
1005 if (m.Right().Is(0)) {
1006 return m.Left().Gate();
1007 }
1008 // K ^ K => K (K stands for arbitrary constants)
1009 if (m.IsFoldable()) {
1010 return builder_.Int32(m.Left().ResolvedValue() ^ m.Right().ResolvedValue());
1011 }
1012 if (m.LeftEqualsRight()) {
1013 return builder_.Int32(0); // x ^ x => 0
1014 }
1015 // (x ^ -1) ^ -1 => x
1016 if (m.Left().IsmInt32Xor() && m.Right().Is(-1)) {
1017 Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
1018 if (mleft.Right().Is(-1)) {
1019 return mleft.Left().Gate();
1020 }
1021 }
1022 return Circuit::NullGate();
1023 }
ReduceWord64Lsr(GateRef gate)1024 GateRef InstructionCombine::ReduceWord64Lsr(GateRef gate)
1025 {
1026 Uint64BinopMatcher m(gate, circuit_);
1027
1028 // x >>> 0 => x
1029 if (m.Right().Is(0)) {
1030 return m.Left().Gate();
1031 }
1032 if (m.IsFoldable()) {
1033 // 63: The '63' here is used as a mask to limit the shift amount to 0-63 bits, preventing overflow.
1034 return builder_.Int64(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 63));
1035 }
1036 return Circuit::NullGate();
1037 }
1038
ReduceWord32Lsr(GateRef gate)1039 GateRef InstructionCombine::ReduceWord32Lsr(GateRef gate)
1040 {
1041 Uint32BinopMatcher m(gate, circuit_);
1042 // x >>> 0 => x
1043 if (m.Right().Is(0)) {
1044 return m.Left().Gate();
1045 }
1046 if (m.IsFoldable()) {
1047 // 31: The '31' here is used as a mask to limit the shift amount to 0-31 bits, preventing overflow.
1048 return builder_.Int32(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 31));
1049 }
1050 // (m >>> s) == 0 implies ((x & m) >>> s) == 0
1051 if (m.Left().IsmInt32And() && m.Right().HasResolvedValue()) {
1052 Uint32BinopMatcher mleft(m.Left().Gate(), circuit_);
1053 if (mleft.Right().HasResolvedValue()) {
1054 uint32_t shift = m.Right().ResolvedValue() & 31;
1055 uint32_t mask = mleft.Right().ResolvedValue();
1056 if ((mask >> shift) == 0) {
1057 return builder_.Int32(0);
1058 }
1059 }
1060 }
1061 return Circuit::NullGate();
1062 }
1063
ReduceWord64Asr(GateRef gate)1064 GateRef InstructionCombine::ReduceWord64Asr(GateRef gate)
1065 {
1066 Int64BinopMatcher m(gate, circuit_);
1067 // x >> 0 => x
1068 if (m.Right().Is(0)) {
1069 return m.Left().Gate();
1070 }
1071 if (m.IsFoldable()) {
1072 // 63: The '63' here is used as a mask to limit the shift amount to 0-63 bits, preventing overflow.
1073 return builder_.Int64(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 63));
1074 }
1075 return Circuit::NullGate();
1076 }
1077
ReduceWord32Asr(GateRef gate)1078 GateRef InstructionCombine::ReduceWord32Asr(GateRef gate)
1079 {
1080 Int32BinopMatcher m(gate, circuit_);
1081 // x >> 0 => x
1082 if (m.Right().Is(0)) {
1083 return m.Left().Gate();
1084 }
1085 if (m.IsFoldable()) {
1086 // 31: The '31' here is used as a mask to limit the shift amount to 0-31 bits, preventing overflow.
1087 return builder_.Int32(m.Left().ResolvedValue() >> (m.Right().ResolvedValue() & 31));
1088 }
1089 if (m.Left().IsmInt32LSL()) {
1090 Int32BinopMatcher mleft(m.Left().Gate(), circuit_);
1091 if (mleft.Left().IsIcmp()) {
1092 // Check if the right shift amount is 31 (logical shift by 31 bits).
1093 if (m.Right().Is(31) && mleft.Right().Is(31)) {
1094 auto newGate = builder_.Int32Sub(builder_.Int32(0), mleft.Left().Gate());
1095 return ReplaceOld(gate, newGate);
1096 }
1097 } else if (mleft.Left().IsLoad()) {
1098 // Check if the right shift amount is 24 (logical shift by 24 bits).
1099 if (m.Right().Is(24) && mleft.Right().Is(24) &&
1100 acc_.GetMachineType(mleft.Left().Gate()) == MachineType::I8) {
1101 return mleft.Left().Gate();
1102 }
1103 }
1104 }
1105 return Circuit::NullGate();
1106 }
1107
ReduceWord64Lsl(GateRef gate)1108 GateRef InstructionCombine::ReduceWord64Lsl(GateRef gate)
1109 {
1110 Int64BinopMatcher m(gate, circuit_);
1111 // x << 0 => x
1112 if (m.Right().Is(0)) {
1113 return m.Left().Gate();
1114 }
1115 if (m.IsFoldable()) {
1116 return builder_.Int64(base::ShlWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
1117 }
1118 // Check if the right shift amount is in the range of 1 to 63 bits (inclusive).
1119 if (m.Right().IsInRange(1, 63) && (m.Left().IsmInt64ASR() || m.Left().IsmInt64LSR())) {
1120 Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
1121 // (x >>> K) << K => x & ~(2^K - 1)
1122 // (x >> K) << K => x & ~(2^K - 1)
1123 if (mleft.Right().Is(m.Right().ResolvedValue())) {
1124 auto newGate = builder_.Int64And(
1125 mleft.Left().Gate(), builder_.Int64(std::numeric_limits<uint64_t>::max() << m.Right().ResolvedValue()));
1126 return ReplaceOld(gate, newGate);
1127 }
1128 }
1129 return Circuit::NullGate();
1130 }
ReduceWord32Lsl(GateRef gate)1131 GateRef InstructionCombine::ReduceWord32Lsl(GateRef gate)
1132 {
1133 Int32BinopMatcher m(gate, circuit_);
1134 // x << 0 => x
1135 if (m.Right().Is(0)) {
1136 return m.Left().Gate();
1137 }
1138 if (m.IsFoldable()) {
1139 return builder_.Int32(base::ShlWithWraparound(m.Left().ResolvedValue(), m.Right().ResolvedValue()));
1140 }
1141
1142 // Check if the right shift amount is in the range of 1 to 31 bits (inclusive).
1143 if (m.Right().IsInRange(1, 31) && (m.Left().IsmInt32ASR() || m.Left().IsmInt32LSR())) {
1144 Int64BinopMatcher mleft(m.Left().Gate(), circuit_);
1145 // (x >>> K) << K => x & ~(2^K - 1)
1146 // (x >> K) << K => x & ~(2^K - 1)
1147 if (mleft.Right().Is(m.Right().ResolvedValue())) {
1148 auto newGate = builder_.Int32And(
1149 mleft.Left().Gate(), builder_.Int32(std::numeric_limits<uint64_t>::max() << m.Right().ResolvedValue()));
1150 return ReplaceOld(gate, newGate);
1151 }
1152 }
1153 return Circuit::NullGate();
1154 }
1155
1156 } // namespace panda::ecmascript::kungfu