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.empty()) return false;
354 if (visited.count(curDep)) {
355 continue;
356 }
357 if (!acc_.IsNotWrite(curDep)) {
358 return true;
359 }
360 visited.insert(curDep);
361 auto depCount = acc_.GetDependCount(curDep);
362 for (size_t i = 0; i < depCount; ++i) {
363 workList.push(acc_.GetDep(curDep, i));
364 }
365 }
366 return false;
367 }
368
GetElementInfo(GateRef gate) const369 ElementInfo* EarlyElimination::GetElementInfo(GateRef gate) const
370 {
371 auto op = acc_.GetTypedLoadOp(gate);
372 auto v0 = acc_.GetValueIn(gate, 0);
373 auto v1 = acc_.GetValueIn(gate, 1);
374 return new (GetChunk()) ElementInfo(op, v0, v1);
375 }
376
GetPropertyInfo(GateRef gate) const377 PropertyInfo* EarlyElimination::GetPropertyInfo(GateRef gate) const
378 {
379 auto v0 = acc_.GetValueIn(gate, 0);
380 auto v1 = acc_.GetValueIn(gate, 1);
381 return new (GetChunk()) PropertyInfo(v0, v1);
382 }
383
GetArrayLengthInfo(GateRef gate) const384 ArrayLengthInfo* EarlyElimination::GetArrayLengthInfo(GateRef gate) const
385 {
386 auto v0 = acc_.GetValueIn(gate, 0);
387 return new (GetChunk()) ArrayLengthInfo(v0);
388 }
389
GetPrimitiveTypeCheckInfo(GateRef gate) const390 PrimitiveTypeCheckInfo* EarlyElimination::GetPrimitiveTypeCheckInfo(GateRef gate) const
391 {
392 auto type = acc_.GetParamGateType(gate);
393 auto v0 = acc_.GetValueIn(gate, 0);
394 return new (GetChunk()) PrimitiveTypeCheckInfo(type, v0);
395 }
396
GetInt32OverflowCheckInfo(GateRef gate) const397 Int32OverflowCheckInfo* EarlyElimination::GetInt32OverflowCheckInfo(GateRef gate) const
398 {
399 TypedUnaryAccessor accessor(acc_.TryGetValue(gate));
400 auto op = accessor.GetTypedUnOp();
401 auto v0 = acc_.GetValueIn(gate, 0);
402 return new (GetChunk()) Int32OverflowCheckInfo(op, v0);
403 }
404
GetArrayCheckInfo(GateRef gate) const405 ArrayCheckInfo* EarlyElimination::GetArrayCheckInfo(GateRef gate) const
406 {
407 auto v0 = acc_.GetValueIn(gate, 0);
408 return new (GetChunk()) ArrayCheckInfo(v0);
409 }
410
GetStableArrayCheckInfo(GateRef gate) const411 StableArrayCheckInfo* EarlyElimination::GetStableArrayCheckInfo(GateRef gate) const
412 {
413 auto v0 = acc_.GetValueIn(gate, 0);
414 return new (GetChunk()) StableArrayCheckInfo(v0);
415 }
416
GetTypedArrayCheckInfo(GateRef gate) const417 TypedArrayCheckInfo* EarlyElimination::GetTypedArrayCheckInfo(GateRef gate) const
418 {
419 auto type = acc_.GetParamGateType(gate);
420 auto v0 = acc_.GetValueIn(gate, 0);
421 return new (GetChunk()) TypedArrayCheckInfo(type, v0);
422 }
423
GetObjectTypeCheckInfo(GateRef gate) const424 ObjectTypeCheckInfo* EarlyElimination::GetObjectTypeCheckInfo(GateRef gate) const
425 {
426 auto type = acc_.GetParamGateType(gate);
427 auto v0 = acc_.GetValueIn(gate, 0);
428 auto v1 = acc_.GetValueIn(gate, 1);
429 return new (GetChunk()) ObjectTypeCheckInfo(type, v0, v1);
430 }
431
GetIndexCheckInfo(GateRef gate) const432 IndexCheckInfo* EarlyElimination::GetIndexCheckInfo(GateRef gate) const
433 {
434 auto type = acc_.GetParamGateType(gate);
435 auto v0 = acc_.GetValueIn(gate, 0);
436 auto v1 = acc_.GetValueIn(gate, 1);
437 return new (GetChunk()) IndexCheckInfo(type, v0, v1);
438 }
439
GetTypedCallCheckInfo(GateRef gate) const440 TypedCallCheckInfo* EarlyElimination::GetTypedCallCheckInfo(GateRef gate) const
441 {
442 auto v0 = acc_.GetValueIn(gate, 0);
443 auto v1 = acc_.GetValueIn(gate, 1);
444 auto v2 = acc_.GetValueIn(gate, 2);
445 return new (GetChunk()) TypedCallCheckInfo(v0, v1, v2);
446 }
447
IsPrimitiveTypeCheck(GateRef gate) const448 bool EarlyElimination::IsPrimitiveTypeCheck(GateRef gate) const
449 {
450 auto op = acc_.GetOpCode(gate);
451 return op == OpCode::PRIMITIVE_TYPE_CHECK;
452 }
453
IsTrustedType(GateRef gate) const454 bool EarlyElimination::IsTrustedType(GateRef gate) const
455 {
456 if (acc_.IsConstant(gate)) {
457 return true;
458 }
459 if (acc_.IsTypedOperator(gate)) {
460 if (acc_.GetOpCode(gate) == OpCode::TYPED_BINARY_OP) {
461 return !acc_.GetGateType(gate).IsIntType();
462 } else {
463 return true;
464 }
465 }
466 return false;
467 }
468
TrustedTypePropagate(ChunkQueue<GateRef> & workList,const ChunkVector<GateRef> & checkList)469 void EarlyElimination::TrustedTypePropagate(ChunkQueue<GateRef>& workList, const ChunkVector<GateRef>& checkList)
470 {
471 ChunkUnorderedMap<GateRef, size_t> trustedInCount(GetChunk());
472 while (!workList.empty()) {
473 auto gate = workList.front();
474 workList.pop();
475 auto uses = acc_.Uses(gate);
476 for (auto i = uses.begin(); i != uses.end(); i++) {
477 GateRef phi = *i;
478 if ((acc_.GetOpCode(phi) != OpCode::VALUE_SELECTOR) ||
479 (acc_.GetGateType(phi) != acc_.GetGateType(gate))) {
480 continue;
481 }
482 trustedInCount[phi]++;
483 if (trustedInCount.at(phi) == acc_.GetNumValueIn(phi)) {
484 workList.push(phi);
485 }
486 }
487 }
488 for (auto check : checkList) {
489 ASSERT(acc_.GetOpCode(check) == OpCode::PRIMITIVE_TYPE_CHECK);
490 auto value = acc_.GetValueIn(check, 0);
491 ASSERT(acc_.GetGateType(value) == acc_.GetParamGateType(check));
492 if (IsTrustedType(value)) {
493 RemoveGate(check, Circuit::NullGate());
494 continue;
495 }
496 if ((trustedInCount.count(value) != 0) &&
497 (trustedInCount.at(value) == acc_.GetNumValueIn(value))) {
498 RemoveGate(check, Circuit::NullGate());
499 continue;
500 }
501 // remove check
502 }
503 }
504
TryEliminate(GateRef gate)505 void EarlyElimination::TryEliminate(GateRef gate)
506 {
507 auto op = acc_.GetOpCode(gate);
508 switch (op) {
509 case OpCode::LOAD_PROPERTY:
510 TryEliminateProperty(gate);
511 break;
512 case OpCode::LOAD_ELEMENT:
513 TryEliminateElement(gate);
514 break;
515 case OpCode::LOAD_ARRAY_LENGTH:
516 TryEliminateArrayLength(gate);
517 break;
518 case OpCode::PRIMITIVE_TYPE_CHECK:
519 TryEliminatePrimitiveTypeCheck(gate);
520 break;
521 case OpCode::INT32_OVERFLOW_CHECK:
522 TryEliminateInt32OverflowCheck(gate);
523 break;
524 case OpCode::ARRAY_CHECK:
525 TryEliminateArrayCheck(gate);
526 break;
527 case OpCode::STABLE_ARRAY_CHECK:
528 TryEliminateStableArrayCheck(gate);
529 break;
530 case OpCode::TYPED_ARRAY_CHECK:
531 TryEliminateTypedArrayCheck(gate);
532 break;
533 case OpCode::OBJECT_TYPE_CHECK:
534 TryEliminateObjectTypeCheck(gate);
535 break;
536 case OpCode::INDEX_CHECK:
537 TryEliminateIndexCheck(gate);
538 break;
539 case OpCode::TYPED_CALL_CHECK:
540 TryEliminateTypedCallCheck(gate);
541 break;
542 case OpCode::STATE_SPLIT:
543 TryEliminateStateSplitAndFrameState(gate);
544 break;
545 case OpCode::DEPEND_SELECTOR:
546 TryEliminateDependSelector(gate);
547 break;
548 case OpCode::DEPEND_AND:
549 TryEliminateDependAnd(gate);
550 break;
551 case OpCode::DEPEND_ENTRY:
552 return;
553 default:
554 TryEliminateOther(gate);
555 break;
556 }
557 }
558
TryEliminateElement(GateRef gate)559 void EarlyElimination::TryEliminateElement(GateRef gate)
560 {
561 auto depIn = acc_.GetDep(gate);
562 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
563 auto info = GetElementInfo(gate);
564 auto preGate = dependInfo->LookUpElement(info);
565 if (preGate != Circuit::NullGate()) {
566 RemoveGate(gate, preGate);
567 } else {
568 dependInfo = dependInfo->UpdateElement(info, gate);
569 dependInfos_[acc_.GetId(gate)] = dependInfo;
570 }
571 }
572
TryEliminateProperty(GateRef gate)573 void EarlyElimination::TryEliminateProperty(GateRef gate)
574 {
575 auto depIn = acc_.GetDep(gate);
576 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
577 auto info = GetPropertyInfo(gate);
578 auto preGate = dependInfo->LookUpProperty(info);
579 if (preGate != Circuit::NullGate()) {
580 RemoveGate(gate, preGate);
581 } else {
582 dependInfo = dependInfo->UpdateProperty(info, gate);
583 dependInfos_[acc_.GetId(gate)] = dependInfo;
584 }
585 }
586
TryEliminateArrayLength(GateRef gate)587 void EarlyElimination::TryEliminateArrayLength(GateRef gate)
588 {
589 auto depIn = acc_.GetDep(gate);
590 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
591 auto info = GetArrayLengthInfo(gate);
592 auto preGate = dependInfo->LookUpArrayLength(info);
593 if (preGate != Circuit::NullGate()) {
594 RemoveGate(gate, preGate);
595 } else {
596 dependInfo = dependInfo->UpdateArrayLength(info, gate);
597 dependInfos_[acc_.GetId(gate)] = dependInfo;
598 }
599 }
600
TryEliminatePrimitiveTypeCheck(GateRef gate)601 void EarlyElimination::TryEliminatePrimitiveTypeCheck(GateRef gate)
602 {
603 auto depIn = acc_.GetDep(gate);
604 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
605 auto info = GetPrimitiveTypeCheckInfo(gate);
606 if (dependInfo->LookUpPrimitiveTypeCheck(info)) {
607 RemoveGate(gate, Circuit::NullGate());
608 } else {
609 dependInfo = dependInfo->UpdatePrimitiveTypeCheck(info);
610 dependInfos_[acc_.GetId(gate)] = dependInfo;
611 }
612 }
613
TryEliminateInt32OverflowCheck(GateRef gate)614 void EarlyElimination::TryEliminateInt32OverflowCheck(GateRef gate)
615 {
616 auto depIn = acc_.GetDep(gate);
617 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
618 auto info = GetInt32OverflowCheckInfo(gate);
619 if (dependInfo->LookUpInt32OverflowCheck(info)) {
620 RemoveGate(gate, Circuit::NullGate());
621 } else {
622 dependInfo = dependInfo->UpdateInt32OverflowCheck(info);
623 dependInfos_[acc_.GetId(gate)] = dependInfo;
624 }
625 }
626
TryEliminateArrayCheck(GateRef gate)627 void EarlyElimination::TryEliminateArrayCheck(GateRef gate)
628 {
629 auto depIn = acc_.GetDep(gate);
630 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
631 auto info = GetArrayCheckInfo(gate);
632 if (dependInfo->LookUpArrayCheck(info)) {
633 RemoveGate(gate, Circuit::NullGate());
634 } else {
635 dependInfo = dependInfo->UpdateArrayCheck(info);
636 dependInfos_[acc_.GetId(gate)] = dependInfo;
637 }
638 }
639
TryEliminateStableArrayCheck(GateRef gate)640 void EarlyElimination::TryEliminateStableArrayCheck(GateRef gate)
641 {
642 auto depIn = acc_.GetDep(gate);
643 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
644 auto info = GetStableArrayCheckInfo(gate);
645 if (dependInfo->LookUpStableArrayCheck(info)) {
646 RemoveGate(gate, Circuit::NullGate());
647 } else {
648 dependInfo = dependInfo->UpdateStableArrayCheck(info);
649 dependInfos_[acc_.GetId(gate)] = dependInfo;
650 }
651 }
652
TryEliminateTypedArrayCheck(GateRef gate)653 void EarlyElimination::TryEliminateTypedArrayCheck(GateRef gate)
654 {
655 auto depIn = acc_.GetDep(gate);
656 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
657 auto info = GetTypedArrayCheckInfo(gate);
658 if (dependInfo->LookUpTypedArrayCheck(info)) {
659 RemoveGate(gate, Circuit::NullGate());
660 } else {
661 dependInfo = dependInfo->UpdateTypedArrayCheck(info);
662 dependInfos_[acc_.GetId(gate)] = dependInfo;
663 }
664 }
665
TryEliminateObjectTypeCheck(GateRef gate)666 void EarlyElimination::TryEliminateObjectTypeCheck(GateRef gate)
667 {
668 auto depIn = acc_.GetDep(gate);
669 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
670 auto info = GetObjectTypeCheckInfo(gate);
671 if (dependInfo->LookUpObjectTypeCheck(info)) {
672 RemoveGate(gate, Circuit::NullGate());
673 } else {
674 dependInfo = dependInfo->UpdateObjectTypeCheck(info);
675 dependInfos_[acc_.GetId(gate)] = dependInfo;
676 }
677 }
678
TryEliminateIndexCheck(GateRef gate)679 void EarlyElimination::TryEliminateIndexCheck(GateRef gate)
680 {
681 auto depIn = acc_.GetDep(gate);
682 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
683 auto info = GetIndexCheckInfo(gate);
684 if (dependInfo->LookUpIndexCheck(info)) {
685 RemoveGate(gate, Circuit::NullGate());
686 } else {
687 dependInfo = dependInfo->UpdateIndexCheck(info);
688 dependInfos_[acc_.GetId(gate)] = dependInfo;
689 }
690 }
691
TryEliminateTypedCallCheck(GateRef gate)692 void EarlyElimination::TryEliminateTypedCallCheck(GateRef gate)
693 {
694 auto depIn = acc_.GetDep(gate);
695 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
696 auto info = GetTypedCallCheckInfo(gate);
697 if (dependInfo->LookUpTypedCallCheck(info)) {
698 RemoveGate(gate, Circuit::NullGate());
699 } else {
700 dependInfo = dependInfo->UpdateTypedCallCheck(info);
701 dependInfos_[acc_.GetId(gate)] = dependInfo;
702 }
703 }
704
TryEliminateStateSplitAndFrameState(GateRef gate)705 void EarlyElimination::TryEliminateStateSplitAndFrameState(GateRef gate)
706 {
707 auto depIn = acc_.GetDep(gate);
708 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
709 auto frameState = dependInfo->LookUpFrameState();
710 auto curFrameState = acc_.GetFrameState(gate);
711 if (frameState != Circuit::NullGate()) {
712 acc_.UpdateAllUses(curFrameState, frameState);
713 RemoveGate(gate, Circuit::NullGate());
714 acc_.DeleteGate(curFrameState);
715 } else {
716 dependInfo = dependInfo->UpdateFrameState(curFrameState);
717 dependInfos_[acc_.GetId(gate)] = dependInfo;
718 stateSplits_.emplace_back(gate);
719 }
720 return ;
721 }
722
TryEliminateOther(GateRef gate)723 void EarlyElimination::TryEliminateOther(GateRef gate)
724 {
725 auto depIn = acc_.GetDep(gate);
726 auto dependInfo = dependInfos_[acc_.GetId(depIn)];
727 if (!acc_.IsNotWrite(gate)) {
728 dependInfo = dependInfo->UpdateWrite();
729 }
730 dependInfos_[acc_.GetId(gate)] = dependInfo;
731 return ;
732 }
733
TryEliminateDependSelector(GateRef gate)734 void EarlyElimination::TryEliminateDependSelector(GateRef gate)
735 {
736 auto state = acc_.GetState(gate);
737 DependChainInfo* dependInfo = nullptr;
738 if (acc_.IsLoopHead(state)) {
739 auto depIn = acc_.GetDep(gate);
740 dependInfo = dependInfos_[acc_.GetId(depIn)];
741 if (IsSideEffectLoop(gate)) {
742 dependInfo = dependInfo->UpdateWrite();
743 }
744 } else {
745 auto dependCount = acc_.GetDependCount(gate);
746 for (size_t i = 0; i < dependCount; ++i) {
747 auto depIn = acc_.GetDep(gate, i);
748 auto tempInfo = dependInfos_[acc_.GetId(depIn)];
749 if (dependInfo == nullptr) {
750 dependInfo = tempInfo;
751 } else {
752 dependInfo = dependInfo->Merge(tempInfo);
753 }
754 }
755 }
756 dependInfos_[acc_.GetId(gate)] = dependInfo;
757 }
758
TryEliminateDependAnd(GateRef gate)759 void EarlyElimination::TryEliminateDependAnd(GateRef gate)
760 {
761 auto dep0 = acc_.GetDep(gate, 0);
762 auto info0 = dependInfos_[acc_.GetId(dep0)];
763 auto dep1 = acc_.GetDep(gate, 1);
764 auto info1 = dependInfos_[acc_.GetId(dep1)];
765 ASSERT(info0->Empty() || info1->Empty());
766 dependInfos_[acc_.GetId(gate)] = (!info0->Empty()) ? info0 : info1;
767 }
768
RemoveGate(GateRef gate,GateRef value)769 void EarlyElimination::RemoveGate(GateRef gate, GateRef value)
770 {
771 auto state = acc_.GetStateCount(gate) > 0 ? acc_.GetState(gate) : Circuit::NullGate();
772 auto depend = acc_.GetDependCount(gate) > 0 ? acc_.GetDep(gate) : Circuit::NullGate();
773 auto uses = acc_.Uses(gate);
774 for (auto i = uses.begin(); i != uses.end();) {
775 if (acc_.IsStateIn(i)) {
776 i = acc_.ReplaceIn(i, state);
777 } else if (acc_.IsDependIn(i)) {
778 i = acc_.ReplaceIn(i, depend);
779 } else {
780 i = acc_.ReplaceIn(i, value);
781 }
782 }
783 acc_.DeleteGate(gate);
784 }
785
RemoveRedundantGate()786 void EarlyElimination::RemoveRedundantGate()
787 {
788 RemoveTypeTrustedCheck();
789 auto emptyInfo = new (GetChunk()) DependChainInfo(GetChunk());
790 dependInfos_.resize(maxId_ + 1, emptyInfo);
791 ChunkQueue<GateRef> workList(GetChunk());
792 workList.push(acc_.GetDependRoot());
793 ChunkMap<GateRef, size_t> mergeVisits(GetChunk());
794 std::vector<GateRef> depUses;
795 while (!workList.empty()) {
796 auto curDep = workList.front();
797 workList.pop();
798 if (acc_.IsDependSelector(curDep) && !acc_.IsLoopHead(acc_.GetState(curDep))) {
799 ASSERT(acc_.GetOpCode(acc_.GetState(curDep)) == OpCode::MERGE);
800 mergeVisits[curDep]++;
801 if (mergeVisits.at(curDep) != acc_.GetDependCount(curDep)) {
802 continue;
803 }
804 }
805 acc_.GetDependUses(curDep, depUses);
806 for (auto use : depUses) {
807 workList.push(use);
808 }
809 TryEliminate(curDep);
810 }
811 for (auto gate : stateSplits_) {
812 RemoveGate(gate, Circuit::NullGate());
813 }
814 }
815
RemoveTypeTrustedCheck()816 void EarlyElimination::RemoveTypeTrustedCheck()
817 {
818 // eliminate type check for type trusted gate (for primitive type check)
819 std::vector<GateRef> allGates;
820 acc_.GetAllGates(allGates);
821 ChunkQueue<GateRef> workList(GetChunk());
822 ChunkVector<GateRef> checkList(GetChunk());
823 for (auto gate : allGates) {
824 maxId_ = std::max(maxId_, acc_.GetId(gate));
825 if (IsTrustedType(gate)) {
826 workList.push(gate);
827 }
828 if (IsPrimitiveTypeCheck(gate)) {
829 checkList.emplace_back(gate);
830 }
831 }
832 TrustedTypePropagate(workList, checkList);
833 }
834 } // namespace panda::ecmascript::kungfu