1 /*
2 * Copyright (c) 2022 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
16 #include "ecmascript/compiler/circuit_optimizer.h"
17
18 namespace panda::ecmascript::kungfu {
ValueLattice()19 ValueLattice::ValueLattice() : value_(0), status_(LatticeStatus::TOP)
20 {
21 }
22
ValueLattice(LatticeStatus status)23 ValueLattice::ValueLattice(LatticeStatus status) : value_(0), status_(status)
24 {
25 }
26
ValueLattice(uint64_t value)27 ValueLattice::ValueLattice(uint64_t value) : value_(value), status_(LatticeStatus::MID)
28 {
29 }
30
IsTop() const31 bool ValueLattice::IsTop() const
32 {
33 return GetStatus() == LatticeStatus::TOP;
34 }
35
IsMid() const36 bool ValueLattice::IsMid() const
37 {
38 return GetStatus() == LatticeStatus::MID;
39 }
40
IsBot() const41 bool ValueLattice::IsBot() const
42 {
43 return GetStatus() == LatticeStatus::BOT;
44 }
45
GetStatus() const46 LatticeStatus ValueLattice::GetStatus() const
47 {
48 return status_;
49 }
50
GetValue() const51 std::optional<uint64_t> ValueLattice::GetValue() const
52 {
53 if (IsTop() || IsBot()) {
54 return std::nullopt;
55 }
56 return value_;
57 }
58
Meet(const ValueLattice & other)59 ValueLattice ValueLattice::Meet(const ValueLattice &other)
60 {
61 if (this->IsTop()) {
62 return other;
63 }
64 if (other.IsTop()) {
65 return *this;
66 }
67 if (this->IsBot() || other.IsBot()) {
68 return ValueLattice(LatticeStatus::BOT);
69 }
70 // both are single
71 if (this->GetValue().value() != other.GetValue().value()) {
72 return ValueLattice(LatticeStatus::BOT);
73 }
74 return *this;
75 }
76
operator ==(const ValueLattice & other) const77 bool ValueLattice::operator==(const ValueLattice &other) const
78 {
79 if (this->IsTop() && other.IsTop()) {
80 return true;
81 }
82 if (this->IsBot() && other.IsBot()) {
83 return true;
84 }
85 if (this->IsMid() && other.IsMid()) {
86 return this->GetValue().value() == other.GetValue().value();
87 }
88 return false;
89 }
90
operator !=(const ValueLattice & other) const91 bool ValueLattice::operator!=(const ValueLattice &other) const
92 {
93 return !(*this == other);
94 }
95
operator <(const ValueLattice & other) const96 bool ValueLattice::operator<(const ValueLattice &other) const
97 {
98 if (this->IsMid() && other.IsTop()) {
99 return true;
100 }
101 if (this->IsBot() && other.IsMid()) {
102 return true;
103 }
104 if (this->IsBot() && other.IsTop()) {
105 return true;
106 }
107 return false;
108 }
109
operator >(const ValueLattice & other) const110 bool ValueLattice::operator>(const ValueLattice &other) const
111 {
112 return !(*this < other);
113 }
114
operator <=(const ValueLattice & other) const115 bool ValueLattice::operator<=(const ValueLattice &other) const
116 {
117 return (*this < other) || (*this == other);
118 }
119
operator >=(const ValueLattice & other) const120 bool ValueLattice::operator>=(const ValueLattice &other) const
121 {
122 return (*this > other) || (*this == other);
123 }
124
Implies(const ValueLattice & other) const125 ValueLattice ValueLattice::Implies(const ValueLattice &other) const
126 {
127 if (!this->IsTop()) {
128 return other;
129 }
130 return ValueLattice(LatticeStatus::TOP);
131 }
132
Print(std::ostream & os) const133 void ValueLattice::Print(std::ostream &os) const
134 {
135 if (IsTop()) {
136 os << "TOP";
137 } else {
138 if (IsBot()) {
139 os << "BOT";
140 } else {
141 os << GetValue().value();
142 }
143 }
144 }
145
ReachabilityLattice()146 ReachabilityLattice::ReachabilityLattice() : reachable_(false)
147 {
148 }
149
ReachabilityLattice(bool reachable)150 ReachabilityLattice::ReachabilityLattice(bool reachable) : reachable_(reachable)
151 {
152 }
153
IsReachable() const154 bool ReachabilityLattice::IsReachable() const
155 {
156 return reachable_;
157 }
158
IsUnreachable() const159 bool ReachabilityLattice::IsUnreachable() const
160 {
161 return !reachable_;
162 }
163
operator ==(const ReachabilityLattice & other) const164 bool ReachabilityLattice::operator==(const ReachabilityLattice &other) const
165 {
166 return this->IsReachable() == other.IsReachable();
167 }
168
operator !=(const ReachabilityLattice & other) const169 bool ReachabilityLattice::operator!=(const ReachabilityLattice &other) const
170 {
171 return !(*this == other);
172 }
173
operator +(const ReachabilityLattice & other) const174 ReachabilityLattice ReachabilityLattice::operator+(const ReachabilityLattice &other) const
175 {
176 return ReachabilityLattice(this->IsReachable() || other.IsReachable());
177 }
178
operator *(const ReachabilityLattice & other) const179 ReachabilityLattice ReachabilityLattice::operator*(const ReachabilityLattice &other) const
180 {
181 return ReachabilityLattice(this->IsReachable() && other.IsReachable());
182 }
183
Implies(const ValueLattice & other) const184 ValueLattice ReachabilityLattice::Implies(const ValueLattice &other) const
185 {
186 if (this->IsReachable()) {
187 return other;
188 }
189 return ValueLattice(LatticeStatus::TOP);
190 }
191
Print(std::ostream & os) const192 void ReachabilityLattice::Print(std::ostream &os) const
193 {
194 if (this->IsReachable()) {
195 os << "reachable";
196 } else {
197 os << "unreachable";
198 }
199 }
200
Initialize(Circuit * circuit,std::function<ValueLattice & (GateRef)> valueLattice,std::function<ReachabilityLattice & (GateRef)> reachabilityLattice)201 void LatticeUpdateRule::Initialize(Circuit *circuit,
202 std::function<ValueLattice &(GateRef)> valueLattice,
203 std::function<ReachabilityLattice &(GateRef)> reachabilityLattice)
204 {
205 circuit_ = circuit;
206 acc_ = GateAccessor(circuit);
207 valueLatticeMap_ = std::move(valueLattice);
208 reachabilityLatticeMap_ = std::move(reachabilityLattice);
209 }
210
UpdateValueLattice(GateRef gate,const ValueLattice & valueLattice)211 bool LatticeUpdateRule::UpdateValueLattice(GateRef gate, const ValueLattice &valueLattice)
212 {
213 if (valueLatticeMap_(gate) != valueLattice) {
214 valueLatticeMap_(gate) = valueLattice;
215 return true;
216 }
217 return false;
218 }
219
UpdateReachabilityLattice(GateRef gate,const ReachabilityLattice & reachabilityLattice)220 bool LatticeUpdateRule::UpdateReachabilityLattice(GateRef gate, const ReachabilityLattice &reachabilityLattice)
221 {
222 if (reachabilityLatticeMap_(gate) != reachabilityLattice) {
223 reachabilityLatticeMap_(gate) = reachabilityLattice;
224 return true;
225 }
226 return false;
227 }
228
RunBoolArithmetic(bool valueA,bool valueB,OpCode op)229 uint64_t LatticeUpdateRuleSCCP::RunBoolArithmetic(bool valueA, bool valueB, OpCode op)
230 {
231 switch (op) {
232 case OpCode::ADD:
233 return (valueA + valueB);
234 case OpCode::SUB:
235 return (valueA - valueB);
236 case OpCode::MUL:
237 return (valueA * valueB);
238 case OpCode::AND:
239 return (valueA & valueB);
240 case OpCode::XOR:
241 return (valueA ^ valueB);
242 case OpCode::OR:
243 return (valueA | valueB);
244 default:
245 LOG_COMPILER(ERROR) << "unexpected op!";
246 return 0;
247 }
248 return 0;
249 }
250
251 template<class T>
RunFixedPointArithmetic(T valueA,T valueB,OpCode op)252 uint64_t LatticeUpdateRuleSCCP::RunFixedPointArithmetic(T valueA, T valueB, OpCode op)
253 {
254 static_assert(std::is_unsigned<T>::value, "T should be an unsigned type");
255 using make_signed_t = typename std::make_signed<T>::type;
256 switch (op) {
257 case OpCode::ADD:
258 return (valueA + valueB);
259 case OpCode::SUB:
260 return (valueA - valueB);
261 case OpCode::MUL:
262 return (valueA * valueB);
263 case OpCode::SDIV:
264 return (static_cast<make_signed_t>(valueA) / static_cast<make_signed_t>(valueB));
265 case OpCode::UDIV:
266 return (valueA / valueB);
267 case OpCode::SMOD:
268 return (static_cast<make_signed_t>(valueA) % static_cast<make_signed_t>(valueB));
269 case OpCode::UMOD:
270 return (valueA % valueB);
271 case OpCode::AND:
272 return (valueA & valueB);
273 case OpCode::XOR:
274 return (valueA ^ valueB);
275 case OpCode::OR:
276 return (valueA | valueB);
277 case OpCode::LSL:
278 return (valueA << valueB);
279 case OpCode::LSR:
280 return (valueA >> valueB);
281 case OpCode::ASR:
282 return (static_cast<make_signed_t>(valueA) >> static_cast<make_signed_t>(valueB));
283 default:
284 LOG_COMPILER(ERROR) << "unexpected op!";
285 return 0;
286 }
287 return 0;
288 }
289
290 template<class T>
RunFloatingPointArithmetic(T valueA,T valueB,OpCode op)291 double LatticeUpdateRuleSCCP::RunFloatingPointArithmetic(T valueA, T valueB, OpCode op)
292 {
293 switch (op) {
294 case OpCode::ADD:
295 return (valueA + valueB);
296 case OpCode::SUB:
297 return (valueA - valueB);
298 case OpCode::MUL:
299 return (valueA * valueB);
300 case OpCode::FDIV:
301 return (valueA / valueB);
302 case OpCode::FMOD:
303 return fmod(valueA, valueB);
304 default:
305 LOG_COMPILER(ERROR) << "unexpected op!";
306 return 0;
307 }
308 return 0;
309 }
310
RunBasicArithmetic(ValueLattice operandA,ValueLattice operandB,OpCode op,MachineType machineType)311 uint64_t LatticeUpdateRuleSCCP::RunBasicArithmetic(ValueLattice operandA, ValueLattice operandB,
312 OpCode op, MachineType machineType)
313 {
314 auto valueA = operandA.GetValue().value();
315 auto valueB = operandB.GetValue().value();
316 if (machineType == MachineType::I1) {
317 return static_cast<bool>(RunBoolArithmetic(static_cast<bool>(valueA),
318 static_cast<bool>(valueB), op));
319 } else if (machineType == MachineType::I8) {
320 return static_cast<uint8_t>(RunFixedPointArithmetic(static_cast<uint8_t>(valueA),
321 static_cast<uint8_t>(valueB), op));
322 } else if (machineType == MachineType::I16) {
323 return static_cast<uint16_t>(RunFixedPointArithmetic(static_cast<uint16_t>(valueA),
324 static_cast<uint16_t>(valueB), op));
325 } else if (machineType == MachineType::I32) {
326 return static_cast<uint32_t>(RunFixedPointArithmetic(static_cast<uint32_t>(valueA),
327 static_cast<uint32_t>(valueB), op));
328 } else if (machineType == MachineType::I64) {
329 return RunFixedPointArithmetic(static_cast<uint64_t>(valueA), static_cast<uint64_t>(valueB), op);
330 } else if (machineType == MachineType::F32) {
331 float valueA_ = base::bit_cast<float>(static_cast<uint32_t>(valueA));
332 float valueB_ = base::bit_cast<float>(static_cast<uint32_t>(valueB));
333 return base::bit_cast<uint64_t>(RunFloatingPointArithmetic(valueA_, valueB_, op));
334 } else if (machineType == MachineType::F64) {
335 double valueA_ = base::bit_cast<double>(static_cast<uint64_t>(valueA));
336 double valueB_ = base::bit_cast<double>(static_cast<uint64_t>(valueB));
337 return base::bit_cast<uint64_t>(RunFloatingPointArithmetic(valueA_, valueB_, op));
338 } else {
339 LOG_COMPILER(ERROR) << "unexpected machineType!";
340 }
341 return 0;
342 }
343
RunFCompareArithmetic(ValueLattice operandA,ValueLattice operandB,FCmpCondition cond,MachineType machineType)344 uint64_t LatticeUpdateRuleSCCP::RunFCompareArithmetic(ValueLattice operandA, ValueLattice operandB,
345 FCmpCondition cond, MachineType machineType)
346 {
347 auto valueA = operandA.GetValue().value();
348 auto valueB = operandB.GetValue().value();
349 if (machineType == MachineType::F32) {
350 float valueA_ = base::bit_cast<float>(static_cast<uint32_t>(valueA));
351 float valueB_ = base::bit_cast<float>(static_cast<uint32_t>(valueB));
352 return base::bit_cast<uint64_t>(RunFloatingPointCompare(valueA_, valueB_, cond));
353 } else if (machineType == MachineType::F64) {
354 double valueA_ = base::bit_cast<double>(static_cast<uint64_t>(valueA));
355 double valueB_ = base::bit_cast<double>(static_cast<uint64_t>(valueB));
356 return base::bit_cast<uint64_t>(RunFloatingPointCompare(valueA_, valueB_, cond));
357 } else {
358 LOG_COMPILER(ERROR) << "unexpected machineType!";
359 }
360 return 0;
361 }
362
RunICompareArithmetic(ValueLattice operandA,ValueLattice operandB,ICmpCondition cond,MachineType machineType)363 uint64_t LatticeUpdateRuleSCCP::RunICompareArithmetic(ValueLattice operandA, ValueLattice operandB,
364 ICmpCondition cond, MachineType machineType)
365 {
366 auto valueA = operandA.GetValue().value();
367 auto valueB = operandB.GetValue().value();
368 if (machineType == MachineType::I1) {
369 return static_cast<bool>(RunBoolCompare(static_cast<bool>(valueA),
370 static_cast<bool>(valueB), cond));
371 } else if (machineType == MachineType::I8) {
372 return static_cast<uint8_t>(RunFixedPointCompare(static_cast<uint8_t>(valueA),
373 static_cast<uint8_t>(valueB), cond));
374 } else if (machineType == MachineType::I16) {
375 return static_cast<uint16_t>(RunFixedPointCompare(static_cast<uint16_t>(valueA),
376 static_cast<uint16_t>(valueB), cond));
377 } else if (machineType == MachineType::I32) {
378 return static_cast<uint32_t>(RunFixedPointCompare(static_cast<uint32_t>(valueA),
379 static_cast<uint32_t>(valueB), cond));
380 } else if (machineType == MachineType::I64) {
381 return RunFixedPointCompare(static_cast<uint64_t>(valueA), static_cast<uint64_t>(valueB), cond);
382 } else {
383 LOG_COMPILER(ERROR) << "unexpected machineType!";
384 }
385 return 0;
386 }
387
RunBoolCompare(bool valueA,bool valueB,ICmpCondition cond)388 uint64_t LatticeUpdateRuleSCCP::RunBoolCompare(bool valueA, bool valueB, ICmpCondition cond)
389 {
390 switch (cond) {
391 case ICmpCondition::EQ:
392 return (valueA == valueB ? 1 : 0);
393 case ICmpCondition::NE:
394 return (valueA != valueB ? 1 : 0);
395 default:
396 LOG_COMPILER(ERROR) << "unexpected cond!";
397 return 0;
398 }
399 }
400
401 template<class T>
RunFixedPointCompare(T valueA,T valueB,ICmpCondition cond)402 uint64_t LatticeUpdateRuleSCCP::RunFixedPointCompare(T valueA, T valueB, ICmpCondition cond)
403 {
404 static_assert(std::is_unsigned<T>::value, "T should be an unsigned type");
405 using make_signed_t = typename std::make_signed<T>::type;
406 switch (cond) {
407 case ICmpCondition::SLT:
408 return (static_cast<make_signed_t>(valueA) < static_cast<make_signed_t>(valueB));
409 case ICmpCondition::SLE:
410 return (static_cast<make_signed_t>(valueA) <= static_cast<make_signed_t>(valueB));
411 case ICmpCondition::SGT:
412 return (static_cast<make_signed_t>(valueA) > static_cast<make_signed_t>(valueB));
413 case ICmpCondition::SGE:
414 return (static_cast<make_signed_t>(valueA) >= static_cast<make_signed_t>(valueB));
415 case ICmpCondition::ULT:
416 return (valueA < valueB);
417 case ICmpCondition::ULE:
418 return (valueA <= valueB);
419 case ICmpCondition::UGT:
420 return (valueA > valueB);
421 case ICmpCondition::UGE:
422 return (valueA >= valueB);
423 case ICmpCondition::NE:
424 return (valueA == valueB ? 1 : 0);
425 case ICmpCondition::EQ:
426 return (valueA != valueB ? 1 : 0);
427 default:
428 UNREACHABLE();
429 }
430 }
431
432 template<class T>
RunFloatingPointCompare(T valueA,T valueB,FCmpCondition cond)433 uint64_t LatticeUpdateRuleSCCP::RunFloatingPointCompare(T valueA, T valueB, FCmpCondition cond)
434 {
435 switch (cond) {
436 case FCmpCondition::OLT:
437 return (valueA < valueB);
438 case FCmpCondition::OLE:
439 return (valueA <= valueB);
440 case FCmpCondition::OGT:
441 return (valueA > valueB);
442 case FCmpCondition::OGE:
443 return (valueA >= valueB);
444 case FCmpCondition::ONE:
445 return (valueA != valueB ? 1 : 0);
446 case FCmpCondition::OEQ:
447 return (valueA == valueB ? 1 : 0);
448 default:
449 LOG_COMPILER(ERROR) << "unexpected cond!";
450 return 0;
451 }
452 return 0;
453 }
454
Run(GateRef gate)455 bool LatticeUpdateRuleSCCP::Run(GateRef gate)
456 {
457 const std::map<OpCode, std::function<bool(void)>> functionTable = {
458 {OpCode::CIRCUIT_ROOT, [&]() -> bool { return RunCircuitRoot(gate); }},
459 {OpCode::STATE_ENTRY, [&]() -> bool { return RunStateEntry(gate); }},
460 {OpCode::DEPEND_ENTRY, [&]() -> bool { return RunDependEntry(gate); }},
461 {OpCode::RETURN_LIST, [&]() -> bool { return RunReturnList(gate); }},
462 {OpCode::ARG_LIST, [&]() -> bool { return RunArgList(gate); }},
463 {OpCode::RETURN, [&]() -> bool { return RunReturn(gate); }},
464 {OpCode::RETURN_VOID, [&]() -> bool { return RunReturnVoid(gate); }},
465 {OpCode::THROW, [&]() -> bool { return RunThrow(gate); }},
466 {OpCode::ORDINARY_BLOCK, [&]() -> bool { return RunOrdinaryBlock(gate); }},
467 {OpCode::IF_BRANCH, [&]() -> bool { return RunIfBranch(gate); }},
468 {OpCode::SWITCH_BRANCH, [&]() -> bool { return RunSwitchBranch(gate); }},
469 {OpCode::IF_TRUE, [&]() -> bool { return RunIfTrue(gate); }},
470 {OpCode::IF_FALSE, [&]() -> bool { return RunIfFalse(gate); }},
471 {OpCode::SWITCH_CASE, [&]() -> bool { return RunSwitchCase(gate); }},
472 {OpCode::DEFAULT_CASE, [&]() -> bool { return RunDefaultCase(gate); }},
473 {OpCode::MERGE, [&]() -> bool { return RunMerge(gate); }},
474 {OpCode::LOOP_BEGIN, [&]() -> bool { return RunLoopBegin(gate); }},
475 {OpCode::LOOP_BACK, [&]() -> bool { return RunLoopBack(gate); }},
476 {OpCode::VALUE_SELECTOR, [&]() -> bool { return RunValueSelector(gate); }},
477 {OpCode::DEPEND_SELECTOR, [&]() -> bool { return RunDependSelector(gate); }},
478 {OpCode::DEPEND_RELAY, [&]() -> bool { return RunDependRelay(gate); }},
479 {OpCode::DEPEND_AND, [&]() -> bool { return RunDependAnd(gate); }},
480 {OpCode::JS_BYTECODE, [&]() -> bool { return RunJSBytecode(gate); }},
481 {OpCode::IF_SUCCESS, [&]() -> bool { return RunIfSuccess(gate); }},
482 {OpCode::IF_EXCEPTION, [&]() -> bool { return RunIfException(gate); }},
483 {OpCode::GET_EXCEPTION, [&]() -> bool { return RunGetException(gate); }},
484 {OpCode::RUNTIME_CALL, [&]() -> bool { return RunRuntimeCall(gate); }},
485 {OpCode::NOGC_RUNTIME_CALL, [&]() -> bool { return RunNoGCRuntimeCall(gate); }},
486 {OpCode::BYTECODE_CALL, [&]() -> bool { return RunBytecodeCall(gate); }},
487 {OpCode::BUILTINS_CALL, [&]() -> bool { return RunBuiltinsCall(gate); }},
488 {OpCode::BUILTINS_CALL_WITH_ARGV, [&]() -> bool { return RunBuiltinsCallWithArgv(gate); }},
489 {OpCode::DEBUGGER_BYTECODE_CALL, [&]() -> bool { return RunDebuggerBytecodeCall(gate); }},
490 {OpCode::CALL, [&]() -> bool { return RunCall(gate); }},
491 {OpCode::RUNTIME_CALL_WITH_ARGV, [&]() -> bool { return RunRuntimeCallWithArgv(gate); }},
492 {OpCode::ALLOCA, [&]() -> bool { return RunAlloca(gate); }},
493 {OpCode::ARG, [&]() -> bool { return RunArg(gate); }},
494 {OpCode::CONST_DATA, [&]() -> bool { return RunConstData(gate); }},
495 {OpCode::RELOCATABLE_DATA, [&]() -> bool { return RunRelocatableData(gate); }},
496 {OpCode::CONSTANT, [&]() -> bool { return RunConstant(gate); }},
497 {OpCode::ZEXT, [&]() -> bool { return RunZExtToIntOrArch(gate); }},
498 {OpCode::SEXT, [&]() -> bool { return RunSExtToIntOrArch(gate); }},
499 {OpCode::TRUNC, [&]() -> bool { return RunTruncToInt(gate); }},
500 {OpCode::REV, [&]() -> bool { return RunRev(gate); }},
501 {OpCode::ADD, [&]() -> bool { return RunAdd(gate); }},
502 {OpCode::SUB, [&]() -> bool { return RunSub(gate); }},
503 {OpCode::MUL, [&]() -> bool { return RunMul(gate); }},
504 {OpCode::EXP, [&]() -> bool { return RunExp(gate); }},
505 {OpCode::SDIV, [&]() -> bool { return RunSDiv(gate); }},
506 {OpCode::SMOD, [&]() -> bool { return RunSMod(gate); }},
507 {OpCode::UDIV, [&]() -> bool { return RunUDiv(gate); }},
508 {OpCode::UMOD, [&]() -> bool { return RunUMod(gate); }},
509 {OpCode::FDIV, [&]() -> bool { return RunFDiv(gate); }},
510 {OpCode::FMOD, [&]() -> bool { return RunFMod(gate); }},
511 {OpCode::AND, [&]() -> bool { return RunAnd(gate); }},
512 {OpCode::XOR, [&]() -> bool { return RunXor(gate); }},
513 {OpCode::OR, [&]() -> bool { return RunOr(gate); }},
514 {OpCode::LSL, [&]() -> bool { return RunLSL(gate); }},
515 {OpCode::LSR, [&]() -> bool { return RunLSR(gate); }},
516 {OpCode::ASR, [&]() -> bool { return RunASR(gate); }},
517 {OpCode::ICMP, [&]() -> bool { return RunIcmp(gate); }},
518 {OpCode::FCMP, [&]() -> bool { return RunFcmp(gate); }},
519 {OpCode::LOAD, [&]() -> bool { return RunLoad(gate); }},
520 {OpCode::STORE, [&]() -> bool { return RunStore(gate); }},
521 {OpCode::TAGGED_TO_INT64, [&]() -> bool { return RunTaggedToInt64(gate); }},
522 {OpCode::INT64_TO_TAGGED, [&]() -> bool { return RunInt64ToTagged(gate); }},
523 {OpCode::SIGNED_INT_TO_FLOAT, [&]() -> bool { return RunSignedIntToFloat(gate); }},
524 {OpCode::UNSIGNED_INT_TO_FLOAT, [&]() -> bool { return RunUnsignedIntToFloat(gate); }},
525 {OpCode::FLOAT_TO_SIGNED_INT, [&]() -> bool { return RunFloatToSignedInt(gate); }},
526 {OpCode::UNSIGNED_FLOAT_TO_INT, [&]() -> bool { return RunUnsignedFloatToInt(gate); }},
527 {OpCode::BITCAST, [&]() -> bool { return RunBitCast(gate); }},
528 };
529 return functionTable.at(acc_.GetOpCode(gate))();
530 }
531
RunCircuitRoot(GateRef gate)532 bool LatticeUpdateRuleSCCP::RunCircuitRoot([[maybe_unused]] GateRef gate)
533 {
534 return false;
535 }
536
RunStateEntry(GateRef gate)537 bool LatticeUpdateRuleSCCP::RunStateEntry(GateRef gate)
538 {
539 return UpdateReachabilityLattice(gate, ReachabilityLattice(true));
540 }
541
RunDependEntry(GateRef gate)542 bool LatticeUpdateRuleSCCP::RunDependEntry(GateRef gate)
543 {
544 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
545 }
546
RunFrameStateEntry(GateRef gate)547 bool LatticeUpdateRuleSCCP::RunFrameStateEntry([[maybe_unused]] GateRef gate)
548 {
549 return false;
550 }
551
RunReturnList(GateRef gate)552 bool LatticeUpdateRuleSCCP::RunReturnList([[maybe_unused]] GateRef gate)
553 {
554 return false;
555 }
556
RunThrowList(GateRef gate)557 bool LatticeUpdateRuleSCCP::RunThrowList([[maybe_unused]] GateRef gate)
558 {
559 return false;
560 }
561
RunConstantList(GateRef gate)562 bool LatticeUpdateRuleSCCP::RunConstantList([[maybe_unused]] GateRef gate)
563 {
564 return false;
565 }
566
RunAllocaList(GateRef gate)567 bool LatticeUpdateRuleSCCP::RunAllocaList([[maybe_unused]] GateRef gate)
568 {
569 return false;
570 }
571
RunArgList(GateRef gate)572 bool LatticeUpdateRuleSCCP::RunArgList([[maybe_unused]] GateRef gate)
573 {
574 return false;
575 }
576
RunReturn(GateRef gate)577 bool LatticeUpdateRuleSCCP::RunReturn(GateRef gate)
578 {
579 const auto previousState = acc_.GetIn(gate, 0);
580 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
581 }
582
RunReturnVoid(GateRef gate)583 bool LatticeUpdateRuleSCCP::RunReturnVoid(GateRef gate)
584 {
585 const auto previousState = acc_.GetIn(gate, 0);
586 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
587 }
588
RunThrow(GateRef gate)589 bool LatticeUpdateRuleSCCP::RunThrow(GateRef gate)
590 {
591 const auto previousState = acc_.GetIn(gate, 0);
592 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
593 }
594
RunOrdinaryBlock(GateRef gate)595 bool LatticeUpdateRuleSCCP::RunOrdinaryBlock(GateRef gate)
596 {
597 const auto previousState = acc_.GetIn(gate, 0);
598 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
599 }
600
RunIfBranch(GateRef gate)601 bool LatticeUpdateRuleSCCP::RunIfBranch(GateRef gate)
602 {
603 const auto previousState = acc_.GetIn(gate, 0);
604 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
605 }
606
RunSwitchBranch(GateRef gate)607 bool LatticeUpdateRuleSCCP::RunSwitchBranch(GateRef gate)
608 {
609 const auto previousState = acc_.GetIn(gate, 0);
610 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
611 }
612
RunIfTrue(GateRef gate)613 bool LatticeUpdateRuleSCCP::RunIfTrue(GateRef gate)
614 {
615 const auto previousState = acc_.GetIn(gate, 0);
616 const bool predicateMayBeTrue =
617 valueLatticeMap_(acc_.GetIn(previousState, 1)) <= ValueLattice(1);
618 return UpdateReachabilityLattice(gate,
619 reachabilityLatticeMap_(previousState)
620 * ReachabilityLattice(predicateMayBeTrue));
621 }
622
RunIfFalse(GateRef gate)623 bool LatticeUpdateRuleSCCP::RunIfFalse(GateRef gate)
624 {
625 const auto previousState = acc_.GetIn(gate, 0);
626 const bool predicateMayBeFalse =
627 valueLatticeMap_(acc_.GetIn(previousState, 1)) <= ValueLattice(0);
628 return UpdateReachabilityLattice(gate,
629 reachabilityLatticeMap_(previousState)
630 * ReachabilityLattice(predicateMayBeFalse));
631 }
632
RunSwitchCase(GateRef gate)633 bool LatticeUpdateRuleSCCP::RunSwitchCase(GateRef gate)
634 {
635 const bool valueMayMatch =
636 valueLatticeMap_(acc_.GetIn(acc_.GetIn(gate, 0), 1))
637 <= ValueLattice(acc_.TryGetValue(gate));
638 return UpdateReachabilityLattice(gate,
639 reachabilityLatticeMap_(acc_.GetIn(gate, 0)) * ReachabilityLattice(valueMayMatch));
640 }
641
RunDefaultCase(GateRef gate)642 bool LatticeUpdateRuleSCCP::RunDefaultCase(GateRef gate)
643 {
644 const auto previousState = acc_.GetIn(gate, 0);
645 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
646 }
647
RunMerge(GateRef gate)648 bool LatticeUpdateRuleSCCP::RunMerge(GateRef gate)
649 {
650 ReachabilityLattice reachable;
651 for (const auto &input : acc_.ConstIns(gate)) {
652 reachable = reachable + reachabilityLatticeMap_(input);
653 }
654 return UpdateReachabilityLattice(gate, reachable);
655 }
656
RunLoopBegin(GateRef gate)657 bool LatticeUpdateRuleSCCP::RunLoopBegin(GateRef gate)
658 {
659 ReachabilityLattice reachable;
660 for (const auto &input : acc_.ConstIns(gate)) {
661 reachable = reachable + reachabilityLatticeMap_(input);
662 }
663 return UpdateReachabilityLattice(gate, reachable);
664 }
665
RunLoopBack(GateRef gate)666 bool LatticeUpdateRuleSCCP::RunLoopBack(GateRef gate)
667 {
668 const auto previousState = acc_.GetIn(gate, 0);
669 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
670 }
671
RunValueSelector(GateRef gate)672 bool LatticeUpdateRuleSCCP::RunValueSelector(GateRef gate)
673 {
674 const auto relatedState = acc_.GetIn(gate, 0);
675 ValueLattice value;
676 size_t cnt = 0;
677 for (const auto &input : acc_.ConstIns(gate)) {
678 if (cnt > 0) {
679 value = value.Meet(reachabilityLatticeMap_(
680 acc_.GetIn(relatedState, cnt - 1)).Implies(valueLatticeMap_(input)));
681 }
682 cnt++;
683 }
684 return UpdateValueLattice(gate, value);
685 }
686
RunDependSelector(GateRef gate)687 bool LatticeUpdateRuleSCCP::RunDependSelector(GateRef gate)
688 {
689 const auto relatedState = acc_.GetIn(gate, 0);
690 ValueLattice value;
691 size_t cnt = 0;
692 for (const auto &input : acc_.ConstIns(gate)) {
693 if (cnt > 0) {
694 value = value.Meet(reachabilityLatticeMap_(
695 acc_.GetIn(relatedState, cnt - 1)).Implies(valueLatticeMap_(input)));
696 }
697 cnt++;
698 }
699 if (!value.IsTop()) {
700 value = ValueLattice(LatticeStatus::BOT);
701 }
702 return UpdateValueLattice(gate, value);
703 }
704
RunDependRelay(GateRef gate)705 bool LatticeUpdateRuleSCCP::RunDependRelay(GateRef gate)
706 {
707 const auto relatedState = acc_.GetIn(gate, 0);
708 ValueLattice value = valueLatticeMap_(acc_.GetIn(gate, 1));
709 if (!value.IsTop()) {
710 value = ValueLattice(LatticeStatus::BOT);
711 }
712 return UpdateValueLattice(gate, reachabilityLatticeMap_(relatedState).Implies(value));
713 }
714
RunDependAnd(GateRef gate)715 bool LatticeUpdateRuleSCCP::RunDependAnd(GateRef gate)
716 {
717 ValueLattice value = ValueLattice(LatticeStatus::BOT);
718 for (const auto &input : acc_.ConstIns(gate)) {
719 if (valueLatticeMap_(input).IsTop()) {
720 value = ValueLattice(LatticeStatus::TOP);
721 }
722 }
723 return UpdateValueLattice(gate, value);
724 }
725
RunJSBytecode(GateRef gate)726 bool LatticeUpdateRuleSCCP::RunJSBytecode(GateRef gate)
727 {
728 const auto previousState = acc_.GetIn(gate, 0);
729 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState))
730 || UpdateValueLattice(gate, reachabilityLatticeMap_(gate).Implies(ValueLattice(LatticeStatus::BOT)));
731 }
732
RunIfSuccess(GateRef gate)733 bool LatticeUpdateRuleSCCP::RunIfSuccess(GateRef gate)
734 {
735 const auto previousState = acc_.GetIn(gate, 0);
736 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
737 }
738
RunIfException(GateRef gate)739 bool LatticeUpdateRuleSCCP::RunIfException(GateRef gate)
740 {
741 const auto previousState = acc_.GetIn(gate, 0);
742 return UpdateReachabilityLattice(gate, reachabilityLatticeMap_(previousState));
743 }
744
RunGetException(GateRef gate)745 bool LatticeUpdateRuleSCCP::RunGetException(GateRef gate)
746 {
747 return UpdateValueLattice(gate, valueLatticeMap_(acc_.GetIn(gate, 0)).Implies(
748 ValueLattice(LatticeStatus::BOT)));
749 }
750
RunRuntimeCall(GateRef gate)751 bool LatticeUpdateRuleSCCP::RunRuntimeCall(GateRef gate)
752 {
753 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
754 }
755
RunNoGCRuntimeCall(GateRef gate)756 bool LatticeUpdateRuleSCCP::RunNoGCRuntimeCall(GateRef gate)
757 {
758 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
759 }
760
RunBytecodeCall(GateRef gate)761 bool LatticeUpdateRuleSCCP::RunBytecodeCall(GateRef gate)
762 {
763 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
764 }
765
RunDebuggerBytecodeCall(GateRef gate)766 bool LatticeUpdateRuleSCCP::RunDebuggerBytecodeCall(GateRef gate)
767 {
768 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
769 }
770
RunBuiltinsCall(GateRef gate)771 bool LatticeUpdateRuleSCCP::RunBuiltinsCall(GateRef gate)
772 {
773 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
774 }
775
RunBuiltinsCallWithArgv(GateRef gate)776 bool LatticeUpdateRuleSCCP::RunBuiltinsCallWithArgv(GateRef gate)
777 {
778 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
779 }
780
RunCall(GateRef gate)781 bool LatticeUpdateRuleSCCP::RunCall(GateRef gate)
782 {
783 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
784 }
785
RunRuntimeCallWithArgv(GateRef gate)786 bool LatticeUpdateRuleSCCP::RunRuntimeCallWithArgv(GateRef gate)
787 {
788 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
789 }
790
RunAlloca(GateRef gate)791 bool LatticeUpdateRuleSCCP::RunAlloca(GateRef gate)
792 {
793 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
794 }
795
RunArg(GateRef gate)796 bool LatticeUpdateRuleSCCP::RunArg(GateRef gate)
797 {
798 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
799 }
800
RunMutableData(GateRef gate)801 bool LatticeUpdateRuleSCCP::RunMutableData(GateRef gate)
802 {
803 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
804 }
805
RunConstData(GateRef gate)806 bool LatticeUpdateRuleSCCP::RunConstData(GateRef gate)
807 {
808 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
809 }
810
RunRelocatableData(GateRef gate)811 bool LatticeUpdateRuleSCCP::RunRelocatableData(GateRef gate)
812 {
813 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
814 }
815
RunConstant(GateRef gate)816 bool LatticeUpdateRuleSCCP::RunConstant(GateRef gate)
817 {
818 const auto constantValue = ValueLattice(acc_.GetConstantValue(gate));
819 return UpdateValueLattice(gate, constantValue);
820 }
821
RunZExtToIntOrArch(GateRef gate)822 bool LatticeUpdateRuleSCCP::RunZExtToIntOrArch(GateRef gate)
823 {
824 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
825 return UpdateValueLattice(gate, operandA);
826 }
827
RunSExtToIntOrArch(GateRef gate)828 bool LatticeUpdateRuleSCCP::RunSExtToIntOrArch(GateRef gate)
829 {
830 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
831 return UpdateValueLattice(gate, operandA);
832 }
833
RunTruncToInt(GateRef gate)834 bool LatticeUpdateRuleSCCP::RunTruncToInt(GateRef gate)
835 {
836 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
837 return UpdateValueLattice(gate, operandA);
838 }
839
RunRev(GateRef gate)840 bool LatticeUpdateRuleSCCP::RunRev(GateRef gate)
841 {
842 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
843 if (operandA.IsMid()) {
844 return UpdateValueLattice(gate, ValueLattice(operandA.GetValue().value()));
845 }
846 return UpdateValueLattice(gate, operandA);
847 }
848
RunAdd(GateRef gate)849 bool LatticeUpdateRuleSCCP::RunAdd(GateRef gate)
850 {
851 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
852 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
853 if (operandA.IsTop() || operandB.IsTop()) {
854 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
855 }
856 if (operandA.IsBot() || operandB.IsBot()) {
857 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
858 }
859 auto machineType = acc_.GetMachineType(gate);
860 auto value = RunBasicArithmetic(operandA, operandB, OpCode::ADD, machineType);
861 return UpdateValueLattice(gate, ValueLattice(value));
862 }
863
RunSub(GateRef gate)864 bool LatticeUpdateRuleSCCP::RunSub(GateRef gate)
865 {
866 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
867 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
868 if (operandA.IsTop() || operandB.IsTop()) {
869 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
870 }
871 if (operandA.IsBot() || operandB.IsBot()) {
872 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
873 }
874 auto machineType = acc_.GetMachineType(gate);
875 auto value = RunBasicArithmetic(operandA, operandB, OpCode::SUB, machineType);
876 return UpdateValueLattice(gate, ValueLattice(value));
877 }
878
RunMul(GateRef gate)879 bool LatticeUpdateRuleSCCP::RunMul(GateRef gate)
880 {
881 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
882 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
883 if (operandA.IsTop() || operandB.IsTop()) {
884 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
885 }
886 if ((operandA.IsMid() && operandA.GetValue().value() == 0) ||
887 (operandB.IsMid() && operandB.GetValue().value() == 0)) {
888 return UpdateValueLattice(gate, ValueLattice(0));
889 }
890 if (operandA.IsBot() || operandB.IsBot()) {
891 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
892 }
893 auto machineType = acc_.GetMachineType(gate);
894 auto value = RunBasicArithmetic(operandA, operandB, OpCode::MUL, machineType);
895 return UpdateValueLattice(gate, ValueLattice(value));
896 }
897
RunExp(GateRef gate)898 bool LatticeUpdateRuleSCCP::RunExp(GateRef gate)
899 {
900 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
901 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
902 if (operandA.IsTop() || operandB.IsTop()) {
903 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
904 }
905 if (operandA.IsBot() || operandB.IsBot()) {
906 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
907 }
908 auto fastPow = [](uint64_t a, uint64_t b) {
909 uint64_t result = 1;
910 uint64_t power = a;
911 while (b) {
912 if (b & 1) {
913 result = result * power;
914 }
915 power = power * power;
916 b >>= 1;
917 }
918 return result;
919 };
920 return UpdateValueLattice(gate, ValueLattice(fastPow(operandA.GetValue().value(), operandB.GetValue().value())));
921 }
922
RunSDiv(GateRef gate)923 bool LatticeUpdateRuleSCCP::RunSDiv(GateRef gate)
924 {
925 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
926 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
927 if (operandA.IsTop() || operandB.IsTop()) {
928 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
929 }
930 if (operandA.IsBot() || operandB.IsBot()) {
931 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
932 }
933 auto machineType = acc_.GetMachineType(gate);
934 auto value = RunBasicArithmetic(operandA, operandB, OpCode::SDIV, machineType);
935 return UpdateValueLattice(gate, ValueLattice(value));
936 }
937
RunSMod(GateRef gate)938 bool LatticeUpdateRuleSCCP::RunSMod(GateRef gate)
939 {
940 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
941 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
942 if (operandA.IsTop() || operandB.IsTop()) {
943 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
944 }
945 if (operandA.IsBot() || operandB.IsBot()) {
946 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
947 }
948 auto machineType = acc_.GetMachineType(gate);
949 auto value = RunBasicArithmetic(operandA, operandB, OpCode::SMOD, machineType);
950 return UpdateValueLattice(gate, ValueLattice(value));
951 }
952
RunUDiv(GateRef gate)953 bool LatticeUpdateRuleSCCP::RunUDiv(GateRef gate)
954 {
955 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
956 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
957 if (operandA.IsTop() || operandB.IsTop()) {
958 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
959 }
960 if (operandA.IsBot() || operandB.IsBot()) {
961 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
962 }
963 auto machineType = acc_.GetMachineType(gate);
964 auto value = RunBasicArithmetic(operandA, operandB, OpCode::UDIV, machineType);
965 return UpdateValueLattice(gate, ValueLattice(value));
966 }
967
RunUMod(GateRef gate)968 bool LatticeUpdateRuleSCCP::RunUMod(GateRef gate)
969 {
970 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
971 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
972 if (operandA.IsTop() || operandB.IsTop()) {
973 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
974 }
975 if (operandA.IsBot() || operandB.IsBot()) {
976 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
977 }
978 auto machineType = acc_.GetMachineType(gate);
979 auto value = RunBasicArithmetic(operandA, operandB, OpCode::UMOD, machineType);
980 return UpdateValueLattice(gate, ValueLattice(value));
981 }
982
RunFDiv(GateRef gate)983 bool LatticeUpdateRuleSCCP::RunFDiv(GateRef gate)
984 {
985 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
986 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
987 if (operandA.IsTop() || operandB.IsTop()) {
988 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
989 }
990 if (operandA.IsBot() || operandB.IsBot()) {
991 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
992 }
993 auto machineType = acc_.GetMachineType(gate);
994 auto value = RunBasicArithmetic(operandA, operandB, OpCode::FDIV, machineType);
995 return UpdateValueLattice(gate, ValueLattice(value));
996 }
997
RunFMod(GateRef gate)998 bool LatticeUpdateRuleSCCP::RunFMod(GateRef gate)
999 {
1000 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1001 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1002 if (operandA.IsTop() || operandB.IsTop()) {
1003 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1004 }
1005 if (operandA.IsBot() || operandB.IsBot()) {
1006 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1007 }
1008 auto machineType = acc_.GetMachineType(gate);
1009 auto value = RunBasicArithmetic(operandA, operandB, OpCode::FMOD, machineType);
1010 return UpdateValueLattice(gate, ValueLattice(value));
1011 }
1012
RunAnd(GateRef gate)1013 bool LatticeUpdateRuleSCCP::RunAnd(GateRef gate)
1014 {
1015 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1016 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1017 if (operandA.IsTop() || operandB.IsTop()) {
1018 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1019 }
1020 if (operandA.IsBot() || operandB.IsBot()) {
1021 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1022 }
1023 auto machineType = acc_.GetMachineType(gate);
1024 auto value = RunBasicArithmetic(operandA, operandB, OpCode::AND, machineType);
1025 return UpdateValueLattice(gate, ValueLattice(value));
1026 }
1027
RunXor(GateRef gate)1028 bool LatticeUpdateRuleSCCP::RunXor(GateRef gate)
1029 {
1030 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1031 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1032 if (operandA.IsTop() || operandB.IsTop()) {
1033 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1034 }
1035 if (operandA.IsBot() || operandB.IsBot()) {
1036 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1037 }
1038 auto machineType = acc_.GetMachineType(gate);
1039 auto value = RunBasicArithmetic(operandA, operandB, OpCode::XOR, machineType);
1040 return UpdateValueLattice(gate, ValueLattice(value));
1041 }
1042
RunOr(GateRef gate)1043 bool LatticeUpdateRuleSCCP::RunOr(GateRef gate)
1044 {
1045 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1046 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1047 if (operandA.IsTop() || operandB.IsTop()) {
1048 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1049 }
1050 if (operandA.IsBot() || operandB.IsBot()) {
1051 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1052 }
1053 auto machineType = acc_.GetMachineType(gate);
1054 auto value = RunBasicArithmetic(operandA, operandB, OpCode::OR, machineType);
1055 return UpdateValueLattice(gate, ValueLattice(value));
1056 }
1057
RunLSL(GateRef gate)1058 bool LatticeUpdateRuleSCCP::RunLSL(GateRef gate)
1059 {
1060 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1061 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1062 if (operandA.IsTop() || operandB.IsTop()) {
1063 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1064 }
1065 if (operandA.IsBot() || operandB.IsBot()) {
1066 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1067 }
1068 auto machineType = acc_.GetMachineType(gate);
1069 auto value = RunBasicArithmetic(operandA, operandB, OpCode::LSL, machineType);
1070 return UpdateValueLattice(gate, ValueLattice(value));
1071 }
1072
RunLSR(GateRef gate)1073 bool LatticeUpdateRuleSCCP::RunLSR(GateRef gate)
1074 {
1075 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1076 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1077 if (operandA.IsTop() || operandB.IsTop()) {
1078 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1079 }
1080 if (operandA.IsBot() || operandB.IsBot()) {
1081 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1082 }
1083 auto machineType = acc_.GetMachineType(gate);
1084 auto value = RunBasicArithmetic(operandA, operandB, OpCode::LSR, machineType);
1085 return UpdateValueLattice(gate, ValueLattice(value));
1086 }
1087
RunASR(GateRef gate)1088 bool LatticeUpdateRuleSCCP::RunASR(GateRef gate)
1089 {
1090 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1091 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1092 if (operandA.IsTop() || operandB.IsTop()) {
1093 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1094 }
1095 if (operandA.IsBot() || operandB.IsBot()) {
1096 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1097 }
1098 auto machineType = acc_.GetMachineType(gate);
1099 auto value = RunBasicArithmetic(operandA, operandB, OpCode::ASR, machineType);
1100 return UpdateValueLattice(gate, ValueLattice(value));
1101 }
1102
RunIcmp(GateRef gate)1103 bool LatticeUpdateRuleSCCP::RunIcmp(GateRef gate)
1104 {
1105 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1106 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1107 ICmpCondition cond = acc_.GetICmpCondition(gate);
1108 if (operandA.IsTop() || operandB.IsTop()) {
1109 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1110 }
1111 if (operandA.IsBot() || operandB.IsBot()) {
1112 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1113 }
1114 auto machineType = acc_.GetMachineType(gate);
1115 auto value = RunICompareArithmetic(operandA, operandB, cond, machineType);
1116 return UpdateValueLattice(gate, ValueLattice(value));
1117 }
1118
RunFcmp(GateRef gate)1119 bool LatticeUpdateRuleSCCP::RunFcmp(GateRef gate)
1120 {
1121 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1122 const ValueLattice &operandB = valueLatticeMap_(acc_.GetIn(gate, 1));
1123 FCmpCondition cond = acc_.GetFCmpCondition(gate);
1124 if (operandA.IsTop() || operandB.IsTop()) {
1125 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::TOP));
1126 }
1127 if (operandA.IsBot() || operandB.IsBot()) {
1128 return UpdateValueLattice(gate, ValueLattice(LatticeStatus::BOT));
1129 }
1130 auto machineType = acc_.GetMachineType(gate);
1131 auto value = RunFCompareArithmetic(operandA, operandB, cond, machineType);
1132 return UpdateValueLattice(gate, ValueLattice(value));
1133 }
1134
RunLoad(GateRef gate)1135 bool LatticeUpdateRuleSCCP::RunLoad(GateRef gate)
1136 {
1137 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
1138 }
1139
RunStore(GateRef gate)1140 bool LatticeUpdateRuleSCCP::RunStore(GateRef gate)
1141 {
1142 return LatticeUpdateRuleSCCP::RunDependAnd(gate);
1143 }
1144
RunTaggedToInt64(GateRef gate)1145 bool LatticeUpdateRuleSCCP::RunTaggedToInt64(GateRef gate)
1146 {
1147 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1148 return UpdateValueLattice(gate, operandA);
1149 }
1150
RunInt64ToTagged(GateRef gate)1151 bool LatticeUpdateRuleSCCP::RunInt64ToTagged(GateRef gate)
1152 {
1153 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1154 return UpdateValueLattice(gate, operandA);
1155 }
1156
RunSignedIntToFloat(GateRef gate)1157 bool LatticeUpdateRuleSCCP::RunSignedIntToFloat(GateRef gate)
1158 {
1159 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1160 return UpdateValueLattice(gate, operandA);
1161 }
1162
RunUnsignedIntToFloat(GateRef gate)1163 bool LatticeUpdateRuleSCCP::RunUnsignedIntToFloat(GateRef gate)
1164 {
1165 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1166 return UpdateValueLattice(gate, operandA);
1167 }
1168
RunFloatToSignedInt(GateRef gate)1169 bool LatticeUpdateRuleSCCP::RunFloatToSignedInt(GateRef gate)
1170 {
1171 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1172 return UpdateValueLattice(gate, operandA);
1173 }
1174
RunUnsignedFloatToInt(GateRef gate)1175 bool LatticeUpdateRuleSCCP::RunUnsignedFloatToInt(GateRef gate)
1176 {
1177 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1178 return UpdateValueLattice(gate, operandA);
1179 }
1180
RunBitCast(GateRef gate)1181 bool LatticeUpdateRuleSCCP::RunBitCast(GateRef gate)
1182 {
1183 const ValueLattice &operandA = valueLatticeMap_(acc_.GetIn(gate, 0));
1184 return UpdateValueLattice(gate, operandA);
1185 }
1186
Initialize(Circuit * circuit)1187 void SubgraphRewriteRule::Initialize(Circuit *circuit)
1188 {
1189 circuit_ = circuit;
1190 acc_ = GateAccessor(circuit);
1191 }
1192
Run(GateRef gate)1193 bool SubgraphRewriteRuleCP::Run(GateRef gate)
1194 {
1195 const std::map<OpCode, std::function<bool(void)>> functionTable = {
1196 {OpCode::ADD, [&]() -> bool { return RunAdd(gate); }},
1197 {OpCode::SUB, [&]() -> bool { return RunSub(gate); }},
1198 };
1199 if (!functionTable.count(acc_.GetOpCode(gate))) {
1200 return false;
1201 }
1202 return functionTable.at(acc_.GetOpCode(gate))();
1203 }
1204
RunAdd(GateRef gate)1205 bool SubgraphRewriteRuleCP::RunAdd(GateRef gate)
1206 {
1207 GateAccessor acc(circuit_);
1208 const auto &operandA = acc_.GetIn(gate, 0);
1209 const auto &operandB = acc_.GetIn(gate, 1);
1210 if (acc_.GetOpCode(operandA) == OpCode::CONSTANT &&
1211 acc_.GetOpCode(operandB) == OpCode::CONSTANT) {
1212 acc_.DeleteIn(gate, 0);
1213 acc_.DeleteIn(gate, 1);
1214 const auto valueA = acc_.GetConstantValue(operandA);
1215 const auto valueB = acc_.GetConstantValue(operandB);
1216 acc_.SetMetaData(gate, circuit_->Constant(valueA + valueB));
1217 return true;
1218 }
1219 return false;
1220 }
1221
RunSub(GateRef gate)1222 bool SubgraphRewriteRuleCP::RunSub(GateRef gate)
1223 {
1224 GateAccessor acc(circuit_);
1225 const auto &operandA = acc_.GetIn(gate, 0);
1226 const auto &operandB = acc_.GetIn(gate, 1);
1227 if (acc_.GetOpCode(operandA) == OpCode::CONSTANT &&
1228 acc_.GetOpCode(operandB) == OpCode::CONSTANT) {
1229 acc_.DeleteIn(gate, 0);
1230 acc_.DeleteIn(gate, 1);
1231 const auto valueA = acc_.GetConstantValue(operandA);
1232 const auto valueB = acc_.GetConstantValue(operandB);
1233 acc_.SetMetaData(gate, circuit_->Constant(valueA - valueB));
1234 return true;
1235 }
1236 return false;
1237 }
1238
LatticeEquationsSystemSolverFramework(LatticeUpdateRule * latticeUpdateRule)1239 LatticeEquationsSystemSolverFramework::LatticeEquationsSystemSolverFramework(LatticeUpdateRule *latticeUpdateRule)
1240 : circuit_(nullptr), acc_(nullptr), latticeUpdateRule_(latticeUpdateRule)
1241 {
1242 }
1243
Run(Circuit * circuit,bool enableLogging)1244 bool LatticeEquationsSystemSolverFramework::Run(Circuit *circuit, bool enableLogging)
1245 {
1246 circuit_ = circuit;
1247 acc_ = GateAccessor(circuit);
1248 auto valueLatticeMapFunction = [&](GateRef gate) -> ValueLattice & {
1249 return valueLatticesMap_[gate];
1250 };
1251 auto reachabilityLatticeMapFunction = [&](GateRef gate) -> ReachabilityLattice & {
1252 return reachabilityLatticesMap_[gate];
1253 };
1254 latticeUpdateRule_->Initialize(circuit_, valueLatticeMapFunction, reachabilityLatticeMapFunction);
1255 std::deque<GateRef> workList;
1256 std::set<GateRef> workSet;
1257 std::vector<GateRef> gates;
1258 circuit_->GetAllGates(gates);
1259 for (auto gate : gates) {
1260 workList.push_back(gate);
1261 workSet.insert(gate);
1262 }
1263 while (!workList.empty()) {
1264 const auto gate = workList.front();
1265 workList.pop_front();
1266 workSet.erase(gate);
1267 if (latticeUpdateRule_->Run(gate) || acc_.GetMetaData(gate)->IsCFGMerge()) {
1268 for (const auto &output : acc_.ConstUses(gate)) {
1269 if (!workSet.count(output)) {
1270 workList.push_back(output); // work queue
1271 workSet.insert(output);
1272 }
1273 }
1274 }
1275 }
1276 if (enableLogging) {
1277 circuit_->GetAllGates(gates);
1278 for (auto gate : gates) {
1279 if (valueLatticesMap_.count(gate)) {
1280 if (valueLatticesMap_.at(gate).IsTop()) {
1281 std::cerr << "[Top]";
1282 } else if (valueLatticesMap_.at(gate).IsBot()) {
1283 std::cerr << "[Bot]";
1284 } else {
1285 std::cerr << "[" << valueLatticesMap_.at(gate).GetValue().value() << "]";
1286 }
1287 }
1288 if (reachabilityLatticesMap_.count(gate)) {
1289 if (reachabilityLatticesMap_.at(gate).IsReachable()) {
1290 std::cerr << "[Reachable]";
1291 } else {
1292 std::cerr << "[Unreachable]";
1293 }
1294 }
1295 std::cerr << " ";
1296 acc_.Print(gate);
1297 }
1298 }
1299 return true;
1300 }
1301
GetValueLattice(GateRef gate) const1302 const ValueLattice &LatticeEquationsSystemSolverFramework::GetValueLattice(GateRef gate) const
1303 {
1304 return valueLatticesMap_.at(gate);
1305 }
1306
GetReachabilityLattice(GateRef gate) const1307 const ReachabilityLattice &LatticeEquationsSystemSolverFramework::GetReachabilityLattice(GateRef gate) const
1308 {
1309 return reachabilityLatticesMap_.at(gate);
1310 }
1311
SubGraphRewriteFramework(SubgraphRewriteRule * subgraphRewriteRule)1312 SubGraphRewriteFramework::SubGraphRewriteFramework(SubgraphRewriteRule *subgraphRewriteRule)
1313 : circuit_(nullptr), acc_(nullptr), subgraphRewriteRule_(subgraphRewriteRule)
1314 {
1315 }
1316
Run(Circuit * circuit,bool enableLogging)1317 bool SubGraphRewriteFramework::Run(Circuit *circuit, bool enableLogging)
1318 {
1319 circuit_ = circuit;
1320 acc_ = GateAccessor(circuit);
1321 subgraphRewriteRule_->Initialize(circuit_);
1322 std::deque<GateRef> workList;
1323 std::set<GateRef> workSet;
1324 std::vector<GateRef> gates;
1325 circuit_->GetAllGates(gates);
1326 for (auto gate : gates) {
1327 workList.push_back(gate);
1328 workSet.insert(gate);
1329 }
1330 while (!workList.empty()) {
1331 const auto gate = workList.front();
1332 workList.pop_front();
1333 workSet.erase(gate);
1334 if (subgraphRewriteRule_->Run(gate)) {
1335 for (const auto &output : acc_.ConstUses(gate)) {
1336 if (!workSet.count(output)) {
1337 workList.push_front(output); // work stack
1338 workSet.insert(output);
1339 }
1340 }
1341 }
1342 }
1343 if (enableLogging) {
1344 circuit_->GetAllGates(gates);
1345 for (auto gate : gates) {
1346 acc_.Print(gate);
1347 }
1348 }
1349 return true;
1350 }
1351
PartitionNode()1352 PartitionNode::PartitionNode() : gate_(Circuit::NullGate())
1353 {
1354 }
1355
PartitionNode(GateRef gate)1356 PartitionNode::PartitionNode(GateRef gate) : gate_(gate)
1357 {
1358 }
1359
GetPrev() const1360 std::shared_ptr<PartitionNode> PartitionNode::GetPrev() const
1361 {
1362 return prev_.lock();
1363 }
1364
GetNext() const1365 std::shared_ptr<PartitionNode> PartitionNode::GetNext() const
1366 {
1367 return next_.lock();
1368 }
1369
GetBelong() const1370 std::shared_ptr<Partition> PartitionNode::GetBelong() const
1371 {
1372 return belong_.lock();
1373 }
1374
GetGate() const1375 GateRef PartitionNode::GetGate() const
1376 {
1377 return gate_;
1378 }
1379
SetPrev(std::shared_ptr<PartitionNode> prev)1380 void PartitionNode::SetPrev(std::shared_ptr<PartitionNode> prev)
1381 {
1382 prev_ = prev;
1383 }
1384
SetNext(std::shared_ptr<PartitionNode> next)1385 void PartitionNode::SetNext(std::shared_ptr<PartitionNode> next)
1386 {
1387 next_ = next;
1388 }
1389
SetBelong(std::shared_ptr<Partition> belong)1390 void PartitionNode::SetBelong(std::shared_ptr<Partition> belong)
1391 {
1392 belong_ = belong;
1393 }
1394
ExistUseByIndex(uint32_t index) const1395 bool PartitionNode::ExistUseByIndex(uint32_t index) const
1396 {
1397 return indexToUses_.count(index) > 0;
1398 }
1399
SetUseByIndex(uint32_t index,std::shared_ptr<PartitionNode> node)1400 void PartitionNode::SetUseByIndex(uint32_t index, std::shared_ptr<PartitionNode> node)
1401 {
1402 if (!ExistUseByIndex(index)) {
1403 indexToUses_.emplace(index, std::vector<std::shared_ptr<PartitionNode>>(0));
1404 }
1405 indexToUses_[index].emplace_back(node);
1406 }
1407
GetUsesVector(std::vector<std::pair<uint32_t,std::vector<std::shared_ptr<PartitionNode>>>> & uses) const1408 void PartitionNode::GetUsesVector(std::vector<std::pair<uint32_t,
1409 std::vector<std::shared_ptr<PartitionNode>>>> &uses) const
1410 {
1411 for (const auto &p : indexToUses_) {
1412 uses.emplace_back(p);
1413 }
1414 }
1415
Partition()1416 Partition::Partition() : isTouched_(false), onWorkList_(false), size_(0)
1417 {
1418 }
1419
GetHead() const1420 std::shared_ptr<PartitionNode> Partition::GetHead() const
1421 {
1422 return head_.lock();
1423 }
1424
SetHead(std::shared_ptr<PartitionNode> head)1425 void Partition::SetHead(std::shared_ptr<PartitionNode> head)
1426 {
1427 head_ = head;
1428 }
1429
SetTouched()1430 void Partition::SetTouched()
1431 {
1432 isTouched_ = true;
1433 }
1434
SetNotTouched()1435 void Partition::SetNotTouched()
1436 {
1437 isTouched_ = false;
1438 }
1439
SetOnWorkList()1440 void Partition::SetOnWorkList()
1441 {
1442 onWorkList_ = true;
1443 }
1444
SetNotOnWorkList()1445 void Partition::SetNotOnWorkList()
1446 {
1447 onWorkList_ = false;
1448 }
1449
IsTouched() const1450 bool Partition::IsTouched() const
1451 {
1452 return isTouched_;
1453 }
1454
IsOnWorkList() const1455 bool Partition::IsOnWorkList() const
1456 {
1457 return onWorkList_;
1458 }
1459
GetSize() const1460 uint32_t Partition::GetSize() const
1461 {
1462 return size_;
1463 }
1464
SizeUp()1465 void Partition::SizeUp()
1466 {
1467 ++size_;
1468 }
1469
SizeDown()1470 void Partition::SizeDown()
1471 {
1472 --size_;
1473 }
1474
AddTouchedNode(std::shared_ptr<PartitionNode> node)1475 void Partition::AddTouchedNode(std::shared_ptr<PartitionNode> node)
1476 {
1477 touched_.emplace_back(node);
1478 }
1479
CleanTouchedNode()1480 void Partition::CleanTouchedNode()
1481 {
1482 touched_.clear();
1483 }
1484
GetTouchedSize() const1485 size_t Partition::GetTouchedSize() const
1486 {
1487 return touched_.size();
1488 }
1489
Insert(std::shared_ptr<PartitionNode> node)1490 void Partition::Insert(std::shared_ptr<PartitionNode> node)
1491 {
1492 if (this->GetHead() != nullptr) {
1493 this->GetHead()->SetPrev(node);
1494 }
1495 node->SetPrev(nullptr);
1496 node->SetNext(this->GetHead());
1497 this->SetHead(node);
1498 this->SizeUp();
1499 }
1500
Delete(std::shared_ptr<PartitionNode> node)1501 void Partition::Delete(std::shared_ptr<PartitionNode> node)
1502 {
1503 if (node->GetPrev() != nullptr) {
1504 node->GetPrev()->SetNext(node->GetNext());
1505 } else {
1506 this->SetHead(node->GetNext());
1507 }
1508 if (node->GetNext() != nullptr) {
1509 node->GetNext()->SetPrev(node->GetPrev());
1510 }
1511 node->SetPrev(nullptr);
1512 node->SetNext(nullptr);
1513 this->SizeDown();
1514 }
1515
SplitByTouched()1516 std::shared_ptr<Partition> Partition::SplitByTouched()
1517 {
1518 for (auto node : touched_) {
1519 this->Delete(node);
1520 }
1521 auto newPartition = std::make_shared<Partition>(Partition());
1522 for (auto node : touched_) {
1523 newPartition->Insert(node);
1524 node->SetBelong(newPartition);
1525 }
1526 return newPartition;
1527 }
1528
MergeUses(std::map<uint32_t,std::vector<std::shared_ptr<PartitionNode>>> & indexToUses) const1529 void Partition::MergeUses(std::map<uint32_t, std::vector<std::shared_ptr<PartitionNode>>> &indexToUses) const
1530 {
1531 std::vector<std::pair<uint32_t, std::vector<std::shared_ptr<PartitionNode>>>> uses;
1532 for (auto defNode = this->GetHead(); defNode != nullptr; defNode = defNode->GetNext()) {
1533 uses.clear();
1534 defNode->GetUsesVector(uses);
1535 for (const auto &use : uses) {
1536 auto index = use.first;
1537 const auto &useNodes = use.second;
1538 if (indexToUses.count(index) == 0) {
1539 indexToUses.emplace(index, std::vector<std::shared_ptr<PartitionNode>>(0));
1540 }
1541 for (auto useNode : useNodes) {
1542 indexToUses[index].emplace_back(useNode);
1543 }
1544 }
1545 }
1546 }
1547
GlobalValueNumbering(Circuit * circuit,bool enableLog)1548 GlobalValueNumbering::GlobalValueNumbering(Circuit *circuit, bool enableLog)
1549 : acc_(GateAccessor(circuit)), enableLog_(enableLog)
1550 {
1551 }
1552
GetPartitionNodes(std::vector<std::shared_ptr<PartitionNode>> & pNodes)1553 void GlobalValueNumbering::GetPartitionNodes(std::vector<std::shared_ptr<PartitionNode>> &pNodes)
1554 {
1555 std::vector<GateRef> gates;
1556 std::map<GateRef, std::shared_ptr<PartitionNode>> gateToNode;
1557 acc_.GetAllGates(gates);
1558 for (auto gate : gates) {
1559 auto node = std::make_shared<PartitionNode>(PartitionNode(gate));
1560 pNodes.emplace_back(node);
1561 gateToNode[gate] = node;
1562 }
1563 for (auto gate : gates) {
1564 size_t count = acc_.GetNumIns(gate);
1565 auto node = gateToNode[gate];
1566 for (size_t i = 0; i < count; ++i) {
1567 GateRef r = acc_.GetIn(gate, i);
1568 auto defNode = gateToNode[r];
1569 defNode->SetUseByIndex(i, node);
1570 }
1571 }
1572 }
1573
SplitByOpCode(const std::vector<std::shared_ptr<PartitionNode>> & nodes,std::vector<std::shared_ptr<Partition>> & partitions)1574 void GlobalValueNumbering::SplitByOpCode(const std::vector<std::shared_ptr<PartitionNode>> &nodes,
1575 std::vector<std::shared_ptr<Partition>> &partitions)
1576 {
1577 std::map<std::tuple<OpCode, BitField, MachineType, uint32_t>, std::shared_ptr<Partition>> opToPartition;
1578 for (auto node : nodes) {
1579 auto op = OpCode(acc_.GetOpCode(node->GetGate()));
1580 auto bit = acc_.TryGetValue(node->GetGate());
1581 auto mt = acc_.GetMachineType(node->GetGate());
1582 auto gt = acc_.GetGateType(node->GetGate()).Value();
1583 auto tp = std::make_tuple(op, bit, mt, gt);
1584 if (opToPartition.count(tp) == 0) {
1585 auto p = std::make_shared<Partition>(Partition());
1586 opToPartition[tp] = p;
1587 partitions.emplace_back(p);
1588 }
1589 auto p = opToPartition[tp];
1590 node->SetBelong(p);
1591 p->Insert(node);
1592 }
1593 }
1594
TrySplit(std::queue<std::shared_ptr<Partition>> & workList,std::vector<std::shared_ptr<Partition>> & partitions)1595 void GlobalValueNumbering::TrySplit(std::queue<std::shared_ptr<Partition>> &workList,
1596 std::vector<std::shared_ptr<Partition>> &partitions)
1597 {
1598 auto curPartition = workList.front();
1599 workList.pop();
1600 curPartition->SetNotOnWorkList();
1601 std::vector<std::shared_ptr<Partition>> touchedPartition;
1602 std::map<uint32_t, std::vector<std::shared_ptr<PartitionNode>>> indexToUses;
1603 curPartition->MergeUses(indexToUses);
1604 for (const auto &use : indexToUses) {
1605 const auto &useNodes = use.second;
1606 for (auto useNode : useNodes) {
1607 if (!useNode->GetBelong()->IsTouched()) {
1608 useNode->GetBelong()->SetTouched();
1609 touchedPartition.emplace_back(useNode->GetBelong());
1610 }
1611 useNode->GetBelong()->AddTouchedNode(useNode);
1612 }
1613 for (auto partition : touchedPartition) {
1614 if (partition->GetSize() != static_cast<uint32_t>(partition->GetTouchedSize())) {
1615 auto newPartition = partition->SplitByTouched();
1616 if (partition->IsOnWorkList() || partition->GetSize() > newPartition->GetSize()) {
1617 workList.push(newPartition);
1618 newPartition->SetOnWorkList();
1619 } else {
1620 workList.push(partition);
1621 partition->SetOnWorkList();
1622 }
1623 partitions.emplace_back(newPartition);
1624 }
1625 partition->CleanTouchedNode();
1626 }
1627 for (auto partition : touchedPartition) {
1628 partition->SetNotTouched();
1629 }
1630 touchedPartition.clear();
1631 }
1632 }
1633
EliminateRedundantGates(const std::vector<std::shared_ptr<Partition>> & partitions)1634 void GlobalValueNumbering::EliminateRedundantGates(const std::vector<std::shared_ptr<Partition>> &partitions)
1635 {
1636 if (IsLogEnabled()) {
1637 Print(partitions);
1638 }
1639 for (auto partition : partitions) {
1640 std::map<uint32_t, std::vector<std::shared_ptr<PartitionNode>>> indexToUses;
1641 partition->MergeUses(indexToUses);
1642 auto kingNode = partition->GetHead();
1643 for (const auto &uses : indexToUses) {
1644 auto index = uses.first;
1645 const auto &useNodes = uses.second;
1646 for (auto useNode : useNodes) {
1647 acc_.ReplaceIn(useNode->GetGate(), index, kingNode->GetGate());
1648 }
1649 }
1650 }
1651 for (auto partition : partitions) {
1652 auto kingNode = partition->GetHead();
1653 for (auto node = kingNode->GetNext(); node != nullptr; node = node->GetNext()) {
1654 acc_.DeleteGate(node->GetGate());
1655 }
1656 }
1657 }
1658
Run()1659 void GlobalValueNumbering::Run()
1660 {
1661 std::vector<std::shared_ptr<PartitionNode>> pNodes;
1662 GetPartitionNodes(pNodes);
1663 std::vector<std::shared_ptr<Partition>> partitions;
1664 SplitByOpCode(pNodes, partitions);
1665 std::queue<std::shared_ptr<Partition>> workList;
1666 for (auto p : partitions) {
1667 workList.push(p);
1668 p->SetOnWorkList();
1669 }
1670 while (!workList.empty()) {
1671 TrySplit(workList, partitions);
1672 }
1673 EliminateRedundantGates(partitions);
1674 }
1675
Print(const std::vector<std::shared_ptr<Partition>> & partitions)1676 void GlobalValueNumbering::Print(const std::vector<std::shared_ptr<Partition>> &partitions)
1677 {
1678 for (auto partition : partitions) {
1679 auto kingNode = partition->GetHead();
1680 std::string log = "[global-value-numbering] replace [";
1681 bool noGateReplaced = true;
1682 for (auto node = kingNode->GetNext(); node != nullptr; node = node->GetNext()) {
1683 if (noGateReplaced) {
1684 noGateReplaced = false;
1685 } else {
1686 log += ", ";
1687 }
1688 log += std::to_string(acc_.GetId(node->GetGate()));
1689 }
1690 if (noGateReplaced) {
1691 continue;
1692 }
1693 log += "] with " + GateMetaData::Str(acc_.GetOpCode(kingNode->GetGate())) + " " +
1694 std::to_string(acc_.GetId(kingNode->GetGate()));
1695 LOG_COMPILER(INFO) << log;
1696 }
1697 }
1698 } // namespace panda::ecmascript::kungfu
1699