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
16 #include <queue>
17 #include <stack>
18
19 #include "ecmascript/compiler/early_elimination.h"
20
21 namespace panda::ecmascript::kungfu {
22
LookUpElement(ElementInfo * info) const23 GateRef DependChainInfo::LookUpElement(ElementInfo* info) const
24 {
25 if ((elementMap_ != nullptr) && (elementMap_->count(*info) > 0)) {
26 return elementMap_->at(*info);
27 } else {
28 return Circuit::NullGate();
29 }
30 }
31
LookUpProperty(PropertyInfo * info) const32 GateRef DependChainInfo::LookUpProperty(PropertyInfo* info) const
33 {
34 if ((propertyMap_ != nullptr) && (propertyMap_->count(*info) > 0)) {
35 return propertyMap_->at(*info);
36 } else {
37 return Circuit::NullGate();
38 }
39 }
40
LookUpArrayLength(ArrayLengthInfo * info) const41 GateRef DependChainInfo::LookUpArrayLength(ArrayLengthInfo* info) const
42 {
43 if ((arrayLengthMap_ != nullptr) && (arrayLengthMap_->count(*info) > 0)) {
44 return arrayLengthMap_->at(*info);
45 } else {
46 return Circuit::NullGate();
47 }
48 }
49
LookUpPrimitiveTypeCheck(PrimitiveTypeCheckInfo * info) const50 bool DependChainInfo::LookUpPrimitiveTypeCheck(PrimitiveTypeCheckInfo* info) const
51 {
52 return (primitiveTypeCheckSet_ != nullptr) && (primitiveTypeCheckSet_->count(*info) > 0);
53 }
54
LookUpInt32OverflowCheck(Int32OverflowCheckInfo * info) const55 bool DependChainInfo::LookUpInt32OverflowCheck(Int32OverflowCheckInfo* info) const
56 {
57 return (int32OverflowCheckSet_ != nullptr) && (int32OverflowCheckSet_->count(*info) > 0);
58 }
59
LookUpArrayCheck(ArrayCheckInfo * info) const60 bool DependChainInfo::LookUpArrayCheck(ArrayCheckInfo* info) const
61 {
62 return (arrayCheckSet_ != nullptr) && (arrayCheckSet_->count(*info) > 0);
63 }
64
LookUpStableArrayCheck(StableArrayCheckInfo * info) const65 bool DependChainInfo::LookUpStableArrayCheck(StableArrayCheckInfo* info) const
66 {
67 return (stableArrayCheckSet_ != nullptr) && (stableArrayCheckSet_->count(*info) > 0);
68 }
69
LookUpTypedArrayCheck(TypedArrayCheckInfo * info) const70 bool DependChainInfo::LookUpTypedArrayCheck(TypedArrayCheckInfo* info) const
71 {
72 return (typedArrayCheckSet_ != nullptr) && (typedArrayCheckSet_->count(*info) > 0);
73 }
74
LookUpObjectTypeCheck(ObjectTypeCheckInfo * info) const75 bool DependChainInfo::LookUpObjectTypeCheck(ObjectTypeCheckInfo* info) const
76 {
77 return (objectTypeCheckSet_ != nullptr) && (objectTypeCheckSet_->count(*info) > 0);
78 }
79
LookUpIndexCheck(IndexCheckInfo * info) const80 bool DependChainInfo::LookUpIndexCheck(IndexCheckInfo* info) const
81 {
82 return (indexCheckSet_ != nullptr) && (indexCheckSet_->count(*info) > 0);
83 }
84
LookUpTypedCallCheck(TypedCallCheckInfo * info) const85 bool DependChainInfo::LookUpTypedCallCheck(TypedCallCheckInfo* info) const
86 {
87 return (typedCallCheckSet_ != nullptr) && (typedCallCheckSet_->count(*info) > 0);
88 }
89
LookUpFrameState() const90 GateRef DependChainInfo::LookUpFrameState() const
91 {
92 return frameState_;
93 }
94
UpdateProperty(PropertyInfo * info,GateRef gate)95 DependChainInfo* DependChainInfo::UpdateProperty(PropertyInfo* info, GateRef gate)
96 {
97 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
98 if (propertyMap_ != nullptr) {
99 that->propertyMap_ = new ChunkMap<PropertyInfo, GateRef>(*propertyMap_);
100 } else {
101 that->propertyMap_ = new ChunkMap<PropertyInfo, GateRef>(chunk_);
102 }
103 that->propertyMap_->insert(std::make_pair(*info, gate));
104 return that;
105 }
106
UpdateElement(ElementInfo * info,GateRef gate)107 DependChainInfo* DependChainInfo::UpdateElement(ElementInfo* info, GateRef gate)
108 {
109 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
110 if (elementMap_ != nullptr) {
111 that->elementMap_ = new ChunkMap<ElementInfo, GateRef>(*elementMap_);
112 } else {
113 that->elementMap_ = new ChunkMap<ElementInfo, GateRef>(chunk_);
114 }
115 that->elementMap_->insert(std::make_pair(*info, gate));
116 return that;
117 }
118
UpdateArrayLength(ArrayLengthInfo * info,GateRef gate)119 DependChainInfo* DependChainInfo::UpdateArrayLength(ArrayLengthInfo* info, GateRef gate)
120 {
121 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
122 if (arrayLengthMap_ != nullptr) {
123 that->arrayLengthMap_ = new ChunkMap<ArrayLengthInfo, GateRef>(*arrayLengthMap_);
124 } else {
125 that->arrayLengthMap_ = new ChunkMap<ArrayLengthInfo, GateRef>(chunk_);
126 }
127 that->arrayLengthMap_->insert(std::make_pair(*info, gate));
128 return that;
129 }
130
UpdatePrimitiveTypeCheck(PrimitiveTypeCheckInfo * info)131 DependChainInfo* DependChainInfo::UpdatePrimitiveTypeCheck(PrimitiveTypeCheckInfo* info)
132 {
133 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
134 if (primitiveTypeCheckSet_ != nullptr) {
135 that->primitiveTypeCheckSet_ = new ChunkSet<PrimitiveTypeCheckInfo>(*primitiveTypeCheckSet_);
136 } else {
137 that->primitiveTypeCheckSet_ = new ChunkSet<PrimitiveTypeCheckInfo>(chunk_);
138 }
139 that->primitiveTypeCheckSet_->insert(*info);
140 return that;
141 }
142
UpdateInt32OverflowCheck(Int32OverflowCheckInfo * info)143 DependChainInfo* DependChainInfo::UpdateInt32OverflowCheck(Int32OverflowCheckInfo* info)
144 {
145 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
146 if (int32OverflowCheckSet_ != nullptr) {
147 that->int32OverflowCheckSet_ = new ChunkSet<Int32OverflowCheckInfo>(*int32OverflowCheckSet_);
148 } else {
149 that->int32OverflowCheckSet_ = new ChunkSet<Int32OverflowCheckInfo>(chunk_);
150 }
151 that->int32OverflowCheckSet_->insert(*info);
152 return that;
153 }
154
UpdateArrayCheck(ArrayCheckInfo * info)155 DependChainInfo* DependChainInfo::UpdateArrayCheck(ArrayCheckInfo* info)
156 {
157 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
158 if (arrayCheckSet_ != nullptr) {
159 that->arrayCheckSet_ = new ChunkSet<ArrayCheckInfo>(*arrayCheckSet_);
160 } else {
161 that->arrayCheckSet_ = new ChunkSet<ArrayCheckInfo>(chunk_);
162 }
163 that->arrayCheckSet_->insert(*info);
164 return that;
165 }
166
UpdateStableArrayCheck(StableArrayCheckInfo * info)167 DependChainInfo* DependChainInfo::UpdateStableArrayCheck(StableArrayCheckInfo* info)
168 {
169 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
170 if (stableArrayCheckSet_ != nullptr) {
171 that->stableArrayCheckSet_ = new ChunkSet<StableArrayCheckInfo>(*stableArrayCheckSet_);
172 } else {
173 that->stableArrayCheckSet_ = new ChunkSet<StableArrayCheckInfo>(chunk_);
174 }
175 that->stableArrayCheckSet_->insert(*info);
176 return that;
177 }
178
UpdateTypedArrayCheck(TypedArrayCheckInfo * info)179 DependChainInfo* DependChainInfo::UpdateTypedArrayCheck(TypedArrayCheckInfo* info)
180 {
181 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
182 if (typedArrayCheckSet_ != nullptr) {
183 that->typedArrayCheckSet_ = new ChunkSet<TypedArrayCheckInfo>(*typedArrayCheckSet_);
184 } else {
185 that->typedArrayCheckSet_ = new ChunkSet<TypedArrayCheckInfo>(chunk_);
186 }
187 that->typedArrayCheckSet_->insert(*info);
188 return that;
189 }
190
UpdateObjectTypeCheck(ObjectTypeCheckInfo * info)191 DependChainInfo* DependChainInfo::UpdateObjectTypeCheck(ObjectTypeCheckInfo* info)
192 {
193 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
194 if (objectTypeCheckSet_ != nullptr) {
195 that->objectTypeCheckSet_ = new ChunkSet<ObjectTypeCheckInfo>(*objectTypeCheckSet_);
196 } else {
197 that->objectTypeCheckSet_ = new ChunkSet<ObjectTypeCheckInfo>(chunk_);
198 }
199 that->objectTypeCheckSet_->insert(*info);
200 return that;
201 }
202
UpdateIndexCheck(IndexCheckInfo * info)203 DependChainInfo* DependChainInfo::UpdateIndexCheck(IndexCheckInfo* info)
204 {
205 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
206 if (indexCheckSet_ != nullptr) {
207 that->indexCheckSet_ = new ChunkSet<IndexCheckInfo>(*indexCheckSet_);
208 } else {
209 that->indexCheckSet_ = new ChunkSet<IndexCheckInfo>(chunk_);
210 }
211 that->indexCheckSet_->insert(*info);
212 return that;
213 }
214
UpdateTypedCallCheck(TypedCallCheckInfo * info)215 DependChainInfo* DependChainInfo::UpdateTypedCallCheck(TypedCallCheckInfo* info)
216 {
217 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
218 if (typedCallCheckSet_ != nullptr) {
219 that->typedCallCheckSet_ = new ChunkSet<TypedCallCheckInfo>(*typedCallCheckSet_);
220 } else {
221 that->typedCallCheckSet_ = new ChunkSet<TypedCallCheckInfo>(chunk_);
222 }
223 that->typedCallCheckSet_->insert(*info);
224 return that;
225 }
226
UpdateFrameState(GateRef gate)227 DependChainInfo* DependChainInfo::UpdateFrameState(GateRef gate)
228 {
229 DependChainInfo* that = new (chunk_) DependChainInfo(*this);
230 that->frameState_ = gate;
231 return that;
232 }
233
UpdateWrite()234 DependChainInfo* DependChainInfo::UpdateWrite()
235 {
236 // save primitiveTypeCheckSet_ and int32OverflowCheckSet_ since these checks have no side effect
237 DependChainInfo* that = new (chunk_) DependChainInfo(chunk_);
238 that->primitiveTypeCheckSet_ = primitiveTypeCheckSet_;
239 that->int32OverflowCheckSet_ = int32OverflowCheckSet_;
240 return that;
241 }
242
Empty() const243 bool DependChainInfo::Empty() const
244 {
245 return (elementMap_ == nullptr) &&
246 (propertyMap_ == nullptr) &&
247 (arrayLengthMap_ == nullptr) &&
248 (primitiveTypeCheckSet_ == nullptr) &&
249 (int32OverflowCheckSet_ == nullptr) &&
250 (arrayCheckSet_ == nullptr) &&
251 (stableArrayCheckSet_ == nullptr) &&
252 (typedArrayCheckSet_ == nullptr) &&
253 (objectTypeCheckSet_ == nullptr) &&
254 (indexCheckSet_ == nullptr) &&
255 (typedCallCheckSet_ == nullptr) &&
256 (frameState_ == Circuit::NullGate());
257 }
258
Equal(DependChainInfo * that)259 bool DependChainInfo::Equal(DependChainInfo* that)
260 {
261 if (this == that) return true;
262 if (that == nullptr) return false;
263 return *this == *that;
264 }
265
266 template<typename K, typename V>
MergeMap(ChunkMap<K,V> * thisMap,ChunkMap<K,V> * thatMap)267 ChunkMap<K, V>* DependChainInfo::MergeMap(ChunkMap<K, V>* thisMap, ChunkMap<K, V>* thatMap)
268 {
269 if (thisMap == thatMap) {
270 return thisMap;
271 } else if (thisMap == nullptr || thatMap == nullptr) {
272 return nullptr;
273 } else {
274 auto newMap = new ChunkMap<K, V>(chunk_);
275 const auto &tempMap = *thisMap;
276 for (const auto &pr : tempMap) {
277 if (thatMap->count(pr.first) && thatMap->at(pr.first) == pr.second) {
278 newMap->insert(pr);
279 }
280 }
281 return newMap;
282 }
283 }
284
285 template<typename K>
MergeSet(ChunkSet<K> * thisSet,ChunkSet<K> * thatSet)286 ChunkSet<K>* DependChainInfo::MergeSet(ChunkSet<K>* thisSet, ChunkSet<K>* thatSet)
287 {
288 if (thisSet == thatSet) {
289 return thisSet;
290 } else if (thisSet == nullptr || thatSet == nullptr) {
291 return nullptr;
292 } else {
293 auto newSet = new ChunkSet<K>(chunk_);
294 const auto &tempSet = *thisSet;
295 for (const auto &it : tempSet) {
296 if (thatSet->count(it)) {
297 newSet->insert(it);
298 }
299 }
300 return newSet;
301 }
302 }
303
Merge(DependChainInfo * that)304 DependChainInfo* DependChainInfo::Merge(DependChainInfo* that)
305 {
306 if (Equal(that)) {
307 return that;
308 }
309 DependChainInfo* newInfo = new (chunk_) DependChainInfo(*this);
310 newInfo->elementMap_ = MergeMap<ElementInfo, GateRef>(elementMap_, that->elementMap_);
311 newInfo->propertyMap_ = MergeMap<PropertyInfo, GateRef>(propertyMap_, that->propertyMap_);
312 newInfo->arrayLengthMap_ = MergeMap<ArrayLengthInfo, GateRef>(arrayLengthMap_, that->arrayLengthMap_);
313 newInfo->primitiveTypeCheckSet_ =
314 MergeSet<PrimitiveTypeCheckInfo>(primitiveTypeCheckSet_, that->primitiveTypeCheckSet_);
315 newInfo->int32OverflowCheckSet_ =
316 MergeSet<Int32OverflowCheckInfo>(int32OverflowCheckSet_, that->int32OverflowCheckSet_);
317 newInfo->arrayCheckSet_ = MergeSet<ArrayCheckInfo>(arrayCheckSet_, that->arrayCheckSet_);
318 newInfo->stableArrayCheckSet_ = MergeSet<StableArrayCheckInfo>(stableArrayCheckSet_, that->stableArrayCheckSet_);
319 newInfo->typedArrayCheckSet_ = MergeSet<TypedArrayCheckInfo>(typedArrayCheckSet_, that->typedArrayCheckSet_);
320 newInfo->objectTypeCheckSet_ = MergeSet<ObjectTypeCheckInfo>(objectTypeCheckSet_, that->objectTypeCheckSet_);
321 newInfo->indexCheckSet_ = MergeSet<IndexCheckInfo>(indexCheckSet_, that->indexCheckSet_);
322 newInfo->typedCallCheckSet_ = MergeSet<TypedCallCheckInfo>(typedCallCheckSet_, that->typedCallCheckSet_);
323 newInfo->frameState_ = frameState_ == that->frameState_ ? frameState_ : Circuit::NullGate();
324 return newInfo;
325 }
326
Run()327 void EarlyElimination::Run()
328 {
329 RemoveRedundantGate();
330
331 if (IsLogEnabled()) {
332 LOG_COMPILER(INFO) << "";
333 LOG_COMPILER(INFO) << "\033[34m"
334 << "===================="
335 << " After check eliminating "
336 << "[" << GetMethodName() << "]"
337 << "===================="
338 << "\033[0m";
339 circuit_->PrintAllGatesWithBytecode();
340 LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
341 }
342 }
343
IsSideEffectLoop(GateRef depend)344 bool EarlyElimination::IsSideEffectLoop(GateRef depend)
345 {
346 ChunkSet<GateRef> visited(GetChunk());
347 ChunkQueue<GateRef> workList(GetChunk());
348 workList.push(depend);
349 visited.insert(acc_.GetDep(depend));
350 while (!workList.empty()) {
351 auto curDep = workList.front();
352 workList.pop();
353 if (visited.count(curDep)) {
354 continue;
355 }
356 if (!acc_.IsNotWrite(curDep)) {
357 return true;
358 }
359 visited.insert(curDep);
360 auto depCount = acc_.GetDependCount(curDep);
361 for (size_t i = 0; i < depCount; ++i) {
362 workList.push(acc_.GetDep(curDep, i));
363 }
364 }
365 return false;
366 }
367
GetElementInfo(GateRef gate) const368 ElementInfo* EarlyElimination::GetElementInfo(GateRef gate) const
369 {
370 auto op = acc_.GetTypedLoadOp(gate);
371 auto v0 = acc_.GetValueIn(gate, 0);
372 auto v1 = acc_.GetValueIn(gate, 1);
373 return new (GetChunk()) ElementInfo(op, v0, v1);
374 }
375
GetPropertyInfo(GateRef gate) const376 PropertyInfo* EarlyElimination::GetPropertyInfo(GateRef gate) const
377 {
378 auto v0 = acc_.GetValueIn(gate, 0);
379 auto v1 = acc_.GetValueIn(gate, 1);
380 return new (GetChunk()) PropertyInfo(v0, v1);
381 }
382
GetArrayLengthInfo(GateRef gate) const383 ArrayLengthInfo* EarlyElimination::GetArrayLengthInfo(GateRef gate) const
384 {
385 auto v0 = acc_.GetValueIn(gate, 0);
386 return new (GetChunk()) ArrayLengthInfo(v0);
387 }
388
GetPrimitiveTypeCheckInfo(GateRef gate) const389 PrimitiveTypeCheckInfo* EarlyElimination::GetPrimitiveTypeCheckInfo(GateRef gate) const
390 {
391 auto type = acc_.GetParamGateType(gate);
392 auto v0 = acc_.GetValueIn(gate, 0);
393 return new (GetChunk()) PrimitiveTypeCheckInfo(type, v0);
394 }
395
GetInt32OverflowCheckInfo(GateRef gate) const396 Int32OverflowCheckInfo* EarlyElimination::GetInt32OverflowCheckInfo(GateRef gate) const
397 {
398 TypedUnaryAccessor accessor(acc_.TryGetValue(gate));
399 auto op = accessor.GetTypedUnOp();
400 auto v0 = acc_.GetValueIn(gate, 0);
401 return new (GetChunk()) Int32OverflowCheckInfo(op, v0);
402 }
403
GetArrayCheckInfo(GateRef gate) const404 ArrayCheckInfo* EarlyElimination::GetArrayCheckInfo(GateRef gate) const
405 {
406 auto v0 = acc_.GetValueIn(gate, 0);
407 return new (GetChunk()) ArrayCheckInfo(v0);
408 }
409
GetStableArrayCheckInfo(GateRef gate) const410 StableArrayCheckInfo* EarlyElimination::GetStableArrayCheckInfo(GateRef gate) const
411 {
412 auto v0 = acc_.GetValueIn(gate, 0);
413 return new (GetChunk()) StableArrayCheckInfo(v0);
414 }
415
GetTypedArrayCheckInfo(GateRef gate) const416 TypedArrayCheckInfo* EarlyElimination::GetTypedArrayCheckInfo(GateRef gate) const
417 {
418 auto type = acc_.GetParamGateType(gate);
419 auto v0 = acc_.GetValueIn(gate, 0);
420 return new (GetChunk()) TypedArrayCheckInfo(type, v0);
421 }
422
GetObjectTypeCheckInfo(GateRef gate) const423 ObjectTypeCheckInfo* EarlyElimination::GetObjectTypeCheckInfo(GateRef gate) const
424 {
425 auto type = acc_.GetParamGateType(gate);
426 auto v0 = acc_.GetValueIn(gate, 0);
427 auto v1 = acc_.GetValueIn(gate, 1);
428 return new (GetChunk()) ObjectTypeCheckInfo(type, v0, v1);
429 }
430
GetIndexCheckInfo(GateRef gate) const431 IndexCheckInfo* EarlyElimination::GetIndexCheckInfo(GateRef gate) const
432 {
433 auto type = acc_.GetParamGateType(gate);
434 auto v0 = acc_.GetValueIn(gate, 0);
435 auto v1 = acc_.GetValueIn(gate, 1);
436 return new (GetChunk()) IndexCheckInfo(type, v0, v1);
437 }
438
GetTypedCallCheckInfo(GateRef gate) const439 TypedCallCheckInfo* EarlyElimination::GetTypedCallCheckInfo(GateRef gate) const
440 {
441 auto v0 = acc_.GetValueIn(gate, 0);
442 auto v1 = acc_.GetValueIn(gate, 1);
443 auto v2 = acc_.GetValueIn(gate, 2);
444 return new (GetChunk()) TypedCallCheckInfo(v0, v1, v2);
445 }
446
IsPrimitiveTypeCheck(GateRef gate) const447 bool EarlyElimination::IsPrimitiveTypeCheck(GateRef gate) const
448 {
449 auto op = acc_.GetOpCode(gate);
450 return op == OpCode::PRIMITIVE_TYPE_CHECK;
451 }
452
IsTrustedType(GateRef gate) const453 bool EarlyElimination::IsTrustedType(GateRef gate) const
454 {
455 if (acc_.IsConstant(gate)) {
456 return true;
457 }
458 if (acc_.IsTypedOperator(gate)) {
459 if (acc_.GetOpCode(gate) == OpCode::TYPED_BINARY_OP) {
460 return !acc_.GetGateType(gate).IsIntType();
461 } else {
462 return true;
463 }
464 }
465 return false;
466 }
467
TrustedTypePropagate(ChunkQueue<GateRef> & workList,const ChunkVector<GateRef> & checkList)468 void EarlyElimination::TrustedTypePropagate(ChunkQueue<GateRef>& workList, const ChunkVector<GateRef>& checkList)
469 {
470 ChunkUnorderedMap<GateRef, size_t> trustedInCount(GetChunk());
471 while (!workList.empty()) {
472 auto gate = workList.front();
473 workList.pop();
474 auto uses = acc_.Uses(gate);
475 for (auto i = uses.begin(); i != uses.end(); i++) {
476 GateRef phi = *i;
477 if ((acc_.GetOpCode(phi) != OpCode::VALUE_SELECTOR) ||
478 (acc_.GetGateType(phi) != acc_.GetGateType(gate))) {
479 continue;
480 }
481 trustedInCount[phi]++;
482 if (trustedInCount.at(phi) == acc_.GetNumValueIn(phi)) {
483 workList.push(phi);
484 }
485 }
486 }
487 for (auto check : checkList) {
488 ASSERT(acc_.GetOpCode(check) == OpCode::PRIMITIVE_TYPE_CHECK);
489 auto value = acc_.GetValueIn(check, 0);
490 ASSERT(acc_.GetGateType(value) == acc_.GetParamGateType(check));
491 if (IsTrustedType(value)) {
492 RemoveGate(check, Circuit::NullGate());
493 continue;
494 }
495 if ((trustedInCount.count(value) != 0) &&
496 (trustedInCount.at(value) == acc_.GetNumValueIn(value))) {
497 RemoveGate(check, Circuit::NullGate());
498 continue;
499 }
500 // remove check
501 }
502 }
503
TryEliminate(GateRef gate)504 void EarlyElimination::TryEliminate(GateRef gate)
505 {
506 auto op = acc_.GetOpCode(gate);
507 switch (op) {
508 case OpCode::LOAD_PROPERTY:
509 TryEliminateProperty(gate);
510 break;
511 case OpCode::LOAD_ELEMENT:
512 TryEliminateElement(gate);
513 break;
514 case OpCode::LOAD_ARRAY_LENGTH:
515 TryEliminateArrayLength(gate);
516 break;
517 case OpCode::PRIMITIVE_TYPE_CHECK:
518 TryEliminatePrimitiveTypeCheck(gate);
519 break;
520 case OpCode::INT32_OVERFLOW_CHECK:
521 TryEliminateInt32OverflowCheck(gate);
522 break;
523 case OpCode::ARRAY_CHECK:
524 TryEliminateArrayCheck(gate);
525 break;
526 case OpCode::STABLE_ARRAY_CHECK:
527 TryEliminateStableArrayCheck(gate);
528 break;
529 case OpCode::TYPED_ARRAY_CHECK:
530 TryEliminateTypedArrayCheck(gate);
531 break;
532 case OpCode::OBJECT_TYPE_CHECK:
533 TryEliminateObjectTypeCheck(gate);
534 break;
535 case OpCode::INDEX_CHECK:
536 TryEliminateIndexCheck(gate);
537 break;
538 case OpCode::TYPED_CALL_CHECK:
539 TryEliminateTypedCallCheck(gate);
540 break;
541 case OpCode::STATE_SPLIT:
542 TryEliminateStateSplitAndFrameState(gate);
543 break;
544 case OpCode::DEPEND_SELECTOR:
545 TryEliminateDependSelector(gate);
546 break;
547 case OpCode::DEPEND_AND:
548 TryEliminateDependAnd(gate);
549 break;
550 case OpCode::DEPEND_ENTRY:
551 return;
552 default:
553 TryEliminateOther(gate);
554 break;
555 }
556 }
557
TryEliminateElement(GateRef gate)558 void EarlyElimination::TryEliminateElement(GateRef gate)
559 {
560 auto depIn = acc_.GetDep(gate);
561 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
562 auto info = GetElementInfo(gate);
563 auto preGate = dependInfo->LookUpElement(info);
564 if (preGate != Circuit::NullGate()) {
565 RemoveGate(gate, preGate);
566 } else {
567 dependInfo = dependInfo->UpdateElement(info, gate);
568 dependInfos_[acc_.GetId(gate)] = dependInfo;
569 }
570 }
571
TryEliminateProperty(GateRef gate)572 void EarlyElimination::TryEliminateProperty(GateRef gate)
573 {
574 auto depIn = acc_.GetDep(gate);
575 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
576 auto info = GetPropertyInfo(gate);
577 auto preGate = dependInfo->LookUpProperty(info);
578 if (preGate != Circuit::NullGate()) {
579 RemoveGate(gate, preGate);
580 } else {
581 dependInfo = dependInfo->UpdateProperty(info, gate);
582 dependInfos_[acc_.GetId(gate)] = dependInfo;
583 }
584 }
585
TryEliminateArrayLength(GateRef gate)586 void EarlyElimination::TryEliminateArrayLength(GateRef gate)
587 {
588 auto depIn = acc_.GetDep(gate);
589 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
590 auto info = GetArrayLengthInfo(gate);
591 auto preGate = dependInfo->LookUpArrayLength(info);
592 if (preGate != Circuit::NullGate()) {
593 RemoveGate(gate, preGate);
594 } else {
595 dependInfo = dependInfo->UpdateArrayLength(info, gate);
596 dependInfos_[acc_.GetId(gate)] = dependInfo;
597 }
598 }
599
TryEliminatePrimitiveTypeCheck(GateRef gate)600 void EarlyElimination::TryEliminatePrimitiveTypeCheck(GateRef gate)
601 {
602 auto depIn = acc_.GetDep(gate);
603 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
604 auto info = GetPrimitiveTypeCheckInfo(gate);
605 if (dependInfo->LookUpPrimitiveTypeCheck(info)) {
606 RemoveGate(gate, Circuit::NullGate());
607 } else {
608 dependInfo = dependInfo->UpdatePrimitiveTypeCheck(info);
609 dependInfos_[acc_.GetId(gate)] = dependInfo;
610 }
611 }
612
TryEliminateInt32OverflowCheck(GateRef gate)613 void EarlyElimination::TryEliminateInt32OverflowCheck(GateRef gate)
614 {
615 auto depIn = acc_.GetDep(gate);
616 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
617 auto info = GetInt32OverflowCheckInfo(gate);
618 if (dependInfo->LookUpInt32OverflowCheck(info)) {
619 RemoveGate(gate, Circuit::NullGate());
620 } else {
621 dependInfo = dependInfo->UpdateInt32OverflowCheck(info);
622 dependInfos_[acc_.GetId(gate)] = dependInfo;
623 }
624 }
625
TryEliminateArrayCheck(GateRef gate)626 void EarlyElimination::TryEliminateArrayCheck(GateRef gate)
627 {
628 auto depIn = acc_.GetDep(gate);
629 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
630 auto info = GetArrayCheckInfo(gate);
631 if (dependInfo->LookUpArrayCheck(info)) {
632 RemoveGate(gate, Circuit::NullGate());
633 } else {
634 dependInfo = dependInfo->UpdateArrayCheck(info);
635 dependInfos_[acc_.GetId(gate)] = dependInfo;
636 }
637 }
638
TryEliminateStableArrayCheck(GateRef gate)639 void EarlyElimination::TryEliminateStableArrayCheck(GateRef gate)
640 {
641 auto depIn = acc_.GetDep(gate);
642 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
643 auto info = GetStableArrayCheckInfo(gate);
644 if (dependInfo->LookUpStableArrayCheck(info)) {
645 RemoveGate(gate, Circuit::NullGate());
646 } else {
647 dependInfo = dependInfo->UpdateStableArrayCheck(info);
648 dependInfos_[acc_.GetId(gate)] = dependInfo;
649 }
650 }
651
TryEliminateTypedArrayCheck(GateRef gate)652 void EarlyElimination::TryEliminateTypedArrayCheck(GateRef gate)
653 {
654 auto depIn = acc_.GetDep(gate);
655 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
656 auto info = GetTypedArrayCheckInfo(gate);
657 if (dependInfo->LookUpTypedArrayCheck(info)) {
658 RemoveGate(gate, Circuit::NullGate());
659 } else {
660 dependInfo = dependInfo->UpdateTypedArrayCheck(info);
661 dependInfos_[acc_.GetId(gate)] = dependInfo;
662 }
663 }
664
TryEliminateObjectTypeCheck(GateRef gate)665 void EarlyElimination::TryEliminateObjectTypeCheck(GateRef gate)
666 {
667 auto depIn = acc_.GetDep(gate);
668 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
669 auto info = GetObjectTypeCheckInfo(gate);
670 if (dependInfo->LookUpObjectTypeCheck(info)) {
671 RemoveGate(gate, Circuit::NullGate());
672 } else {
673 dependInfo = dependInfo->UpdateObjectTypeCheck(info);
674 dependInfos_[acc_.GetId(gate)] = dependInfo;
675 }
676 }
677
TryEliminateIndexCheck(GateRef gate)678 void EarlyElimination::TryEliminateIndexCheck(GateRef gate)
679 {
680 auto depIn = acc_.GetDep(gate);
681 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
682 auto info = GetIndexCheckInfo(gate);
683 if (dependInfo->LookUpIndexCheck(info)) {
684 RemoveGate(gate, Circuit::NullGate());
685 } else {
686 dependInfo = dependInfo->UpdateIndexCheck(info);
687 dependInfos_[acc_.GetId(gate)] = dependInfo;
688 }
689 }
690
TryEliminateTypedCallCheck(GateRef gate)691 void EarlyElimination::TryEliminateTypedCallCheck(GateRef gate)
692 {
693 auto depIn = acc_.GetDep(gate);
694 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
695 auto info = GetTypedCallCheckInfo(gate);
696 if (dependInfo->LookUpTypedCallCheck(info)) {
697 RemoveGate(gate, Circuit::NullGate());
698 } else {
699 dependInfo = dependInfo->UpdateTypedCallCheck(info);
700 dependInfos_[acc_.GetId(gate)] = dependInfo;
701 }
702 }
703
TryEliminateStateSplitAndFrameState(GateRef gate)704 void EarlyElimination::TryEliminateStateSplitAndFrameState(GateRef gate)
705 {
706 auto depIn = acc_.GetDep(gate);
707 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
708 auto frameState = dependInfo->LookUpFrameState();
709 auto curFrameState = acc_.GetFrameState(gate);
710 if (frameState != Circuit::NullGate()) {
711 acc_.UpdateAllUses(curFrameState, frameState);
712 RemoveGate(gate, Circuit::NullGate());
713 acc_.DeleteGate(curFrameState);
714 } else {
715 dependInfo = dependInfo->UpdateFrameState(curFrameState);
716 dependInfos_[acc_.GetId(gate)] = dependInfo;
717 stateSplits_.emplace_back(gate);
718 }
719 return ;
720 }
721
TryEliminateOther(GateRef gate)722 void EarlyElimination::TryEliminateOther(GateRef gate)
723 {
724 auto depIn = acc_.GetDep(gate);
725 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
726 if (!acc_.IsNotWrite(gate)) {
727 dependInfo = dependInfo->UpdateWrite();
728 }
729 dependInfos_[acc_.GetId(gate)] = dependInfo;
730 return ;
731 }
732
TryEliminateDependSelector(GateRef gate)733 void EarlyElimination::TryEliminateDependSelector(GateRef gate)
734 {
735 auto state = acc_.GetState(gate);
736 DependChainInfo* dependInfo = nullptr;
737 if (acc_.IsLoopHead(state)) {
738 auto depIn = acc_.GetDep(gate);
739 dependInfo = dependInfos_[acc_.GetId(depIn)];
740 if (IsSideEffectLoop(gate)) {
741 dependInfo = dependInfo->UpdateWrite();
742 }
743 } else {
744 auto dependCount = acc_.GetDependCount(gate);
745 for (size_t i = 0; i < dependCount; ++i) {
746 auto depIn = acc_.GetDep(gate, i);
747 auto tempInfo = dependInfos_[acc_.GetId(depIn)];
748 if (dependInfo == nullptr) {
749 dependInfo = tempInfo;
750 } else {
751 dependInfo = dependInfo->Merge(tempInfo);
752 }
753 }
754 }
755 dependInfos_[acc_.GetId(gate)] = dependInfo;
756 }
757
TryEliminateDependAnd(GateRef gate)758 void EarlyElimination::TryEliminateDependAnd(GateRef gate)
759 {
760 auto dep0 = acc_.GetDep(gate, 0);
761 auto info0 = dependInfos_[acc_.GetId(dep0)];
762 auto dep1 = acc_.GetDep(gate, 1);
763 auto info1 = dependInfos_[acc_.GetId(dep1)];
764 ASSERT(info0->Empty() || info1->Empty());
765 dependInfos_[acc_.GetId(gate)] = (!info0->Empty()) ? info0 : info1;
766 }
767
RemoveGate(GateRef gate,GateRef value)768 void EarlyElimination::RemoveGate(GateRef gate, GateRef value)
769 {
770 auto state = acc_.GetStateCount(gate) > 0 ? acc_.GetState(gate) : Circuit::NullGate();
771 auto depend = acc_.GetDependCount(gate) > 0 ? acc_.GetDep(gate) : Circuit::NullGate();
772 auto uses = acc_.Uses(gate);
773 for (auto i = uses.begin(); i != uses.end();) {
774 if (acc_.IsStateIn(i)) {
775 i = acc_.ReplaceIn(i, state);
776 } else if (acc_.IsDependIn(i)) {
777 i = acc_.ReplaceIn(i, depend);
778 } else {
779 i = acc_.ReplaceIn(i, value);
780 }
781 }
782 acc_.DeleteGate(gate);
783 }
784
RemoveRedundantGate()785 void EarlyElimination::RemoveRedundantGate()
786 {
787 RemoveTypeTrustedCheck();
788 auto emptyInfo = new (GetChunk()) DependChainInfo(GetChunk());
789 dependInfos_.resize(maxId_ + 1, emptyInfo);
790 ChunkQueue<GateRef> workList(GetChunk());
791 workList.push(acc_.GetDependRoot());
792 ChunkMap<GateRef, size_t> mergeVisits(GetChunk());
793 std::vector<GateRef> depUses;
794 while (!workList.empty()) {
795 auto curDep = workList.front();
796 workList.pop();
797 if (acc_.IsDependSelector(curDep) && !acc_.IsLoopHead(acc_.GetState(curDep))) {
798 ASSERT(acc_.GetOpCode(acc_.GetState(curDep)) == OpCode::MERGE);
799 mergeVisits[curDep]++;
800 if (mergeVisits.at(curDep) != acc_.GetDependCount(curDep)) {
801 continue;
802 }
803 }
804 acc_.GetDependUses(curDep, depUses);
805 for (auto use : depUses) {
806 workList.push(use);
807 }
808 TryEliminate(curDep);
809 }
810 for (auto gate : stateSplits_) {
811 RemoveGate(gate, Circuit::NullGate());
812 }
813 }
814
RemoveTypeTrustedCheck()815 void EarlyElimination::RemoveTypeTrustedCheck()
816 {
817 // eliminate type check for type trusted gate (for primitive type check)
818 std::vector<GateRef> allGates;
819 acc_.GetAllGates(allGates);
820 ChunkQueue<GateRef> workList(GetChunk());
821 ChunkVector<GateRef> checkList(GetChunk());
822 for (auto gate : allGates) {
823 maxId_ = std::max(maxId_, acc_.GetId(gate));
824 if (IsTrustedType(gate)) {
825 workList.push(gate);
826 }
827 if (IsPrimitiveTypeCheck(gate)) {
828 checkList.emplace_back(gate);
829 }
830 }
831 TrustedTypePropagate(workList, checkList);
832 }
833 } // namespace panda::ecmascript::kungfu