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 "ecmascript/compiler/array_bounds_check_elimination.h"
17
18 namespace panda::ecmascript::kungfu {
Run()19 void ArrayBoundsCheckElimination::Run()
20 {
21 bounds_.resize(circuit_->GetMaxGateId() + 1, nullptr); // 1: +1 for size
22 indexCheckInfo_.resize(circuit_->GetMaxGateId() + 1, nullptr);
23 graphLinearizer_.SetScheduleJSOpcode();
24 graphLinearizer_.LinearizeGraph();
25 CalcBounds(graphLinearizer_.GetEntryRegion(), nullptr);
26 }
27
28 /*
29 i_lower + c_lower <= x <= i_upper + c_upper
30 Initially, when nothing about the bounds is known yet, every instrution has the bounds:
31 MIN <= x <= MAX
32 */
Bound()33 ArrayBoundsCheckElimination::Bound::Bound()
34 {
35 lower_ = INT_MIN;
36 upper_ = INT_MAX;
37 lowerGate_ = Circuit::NullGate();
38 upperGate_ = Circuit::NullGate();
39 }
40
Bound(int lower,GateRef lowerGate,int upper,GateRef upperGate)41 ArrayBoundsCheckElimination::Bound::Bound(int lower, GateRef lowerGate, int upper, GateRef upperGate)
42 {
43 lower_ = lower;
44 upper_ = upper;
45 lowerGate_ = lowerGate;
46 upperGate_ = upperGate;
47 }
48
Bound(TypedBinOp op,GateRef gate,int constant)49 ArrayBoundsCheckElimination::Bound::Bound(TypedBinOp op, GateRef gate, int constant)
50 {
51 switch (op) {
52 case TypedBinOp::TYPED_EQ: {
53 lower_ = constant;
54 lowerGate_ = gate;
55 upper_ = constant;
56 upperGate_ = gate;
57 break;
58 }
59 case TypedBinOp::TYPED_NOTEQ: {
60 lower_ = INT_MIN;
61 lowerGate_ = Circuit::NullGate();
62 upper_ = INT_MAX;
63 upperGate_ = Circuit::NullGate();
64 if (gate == Circuit::NullGate()) {
65 if (constant == INT_MIN) {
66 lower_++;
67 }
68 if (constant == INT_MAX) {
69 upper_--;
70 }
71 }
72 break;
73 }
74 case TypedBinOp::TYPED_GREATEREQ: {
75 lower_ = constant;
76 lowerGate_ = gate;
77 upper_ = INT_MAX;
78 upperGate_ = Circuit::NullGate();
79 break;
80 }
81 case TypedBinOp::TYPED_LESSEQ: {
82 lower_ = INT_MIN;
83 lowerGate_ = Circuit::NullGate();
84 upper_ = constant;
85 upperGate_ = gate;
86 break;
87 }
88 default: {
89 LOG_ECMA(FATAL) << "unknown binary op";
90 UNREACHABLE();
91 }
92 }
93 }
94
AndOp(Bound * bound,Bound * b)95 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::AndOp(Bound *bound, Bound *b)
96 {
97 // Update lower bound
98 if (bound->lowerGate_ == b->lowerGate_) {
99 bound->lower_ = std::max(bound->lower_, b->lower_);
100 }
101 if (b->HasLower()) {
102 bool set = true;
103 if (bound->lowerGate_ != Circuit::NullGate() && b->lowerGate_ != Circuit::NullGate()) {
104 auto boundLowerGateRegion = graphLinearizer_.GateToRegion(bound->lowerGate_);
105 auto bLowerGateRegion = graphLinearizer_.GateToRegion(b->lowerGate_);
106 int32_t boundLowerDominatorDepth = -1;
107 if (boundLowerGateRegion) {
108 boundLowerDominatorDepth = boundLowerGateRegion->GetDepth();
109 }
110 int32_t bLowerDominatorDepth = -1;
111 if (bLowerGateRegion) {
112 bLowerDominatorDepth = bLowerGateRegion->GetDepth();
113 }
114 set = (boundLowerDominatorDepth < bLowerDominatorDepth);
115 }
116 if (set) {
117 bound->lower_ = b->lower_;
118 bound->lowerGate_ = b->lowerGate_;
119 }
120 }
121
122 // Update upper bound
123 if (bound->upperGate_ == b->upperGate_) {
124 bound->upper_ = std::min(bound->upper_, b->upper_);
125 }
126 if (b->HasUpper()) {
127 bool set = true;
128 if (bound->upperGate_ != Circuit::NullGate() && b->upperGate_ != Circuit::NullGate()) {
129 auto boundUpperGateRegion = graphLinearizer_.GateToRegion(bound->upperGate_);
130 auto bUpperGateRegion = graphLinearizer_.GateToRegion(b->upperGate_);
131 int32_t boundUpperDominatorDepth = -1;
132 if (boundUpperGateRegion) {
133 boundUpperDominatorDepth = boundUpperGateRegion->GetDepth();
134 }
135 int32_t bUpperDominatorDepth = -1;
136 if (bUpperGateRegion) {
137 bUpperDominatorDepth = bUpperGateRegion->GetDepth();
138 }
139 set = (boundUpperDominatorDepth < bUpperDominatorDepth);
140 }
141 if (set) {
142 bound->upper_ = b->upper_;
143 bound->upperGate_ = b->upperGate_;
144 }
145 }
146
147 return bound;
148 }
149
OrOp(Bound * bound,Bound * b)150 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::OrOp(Bound *bound, Bound *b)
151 {
152 // Update lower bound
153 if (bound->lowerGate_ != b->lowerGate_) {
154 bound->lowerGate_ = Circuit::NullGate();
155 bound->lower_ = INT_MIN;
156 } else {
157 bound->lower_ = std::min(bound->lower_, b->lower_);
158 }
159 // Update upper bound
160 if (bound->upperGate_ != b->upperGate_) {
161 bound->upperGate_ = Circuit::NullGate();
162 bound->upper_ = INT_MAX;
163 } else {
164 bound->upper_ = std::max(bound->upper_, b->upper_);
165 }
166
167 return bound;
168 }
169
DoConstant(GateRef gate)170 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::DoConstant(GateRef gate)
171 {
172 int constValue = static_cast<int>(acc_.GetConstantValue(gate));
173 return new Bound(constValue, Circuit::NullGate(), constValue, Circuit::NullGate());
174 }
175
DoBinaryArithmeticOp(GateRef gate)176 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::DoBinaryArithmeticOp(GateRef gate)
177 {
178 auto op = acc_.GetTypedBinaryOp(gate);
179 auto x = FindBoundGate(acc_.GetValueIn(gate, 0));
180 auto y = FindBoundGate(acc_.GetValueIn(gate, 1));
181 if (!acc_.IsConstant(x) || !acc_.IsConstant(y)) { // One of the operands must be non-constant!
182 if (op == TypedBinOp::TYPED_AND && (acc_.IsConstant(x) || acc_.IsConstant(y))) {
183 int constValue = 0;
184 if (acc_.IsConstant(x)) {
185 constValue = static_cast<int>(acc_.GetConstantValue(x));
186 } else {
187 constValue = static_cast<int>(acc_.GetConstantValue(y));
188 }
189 if (constValue >= 0) {
190 return new Bound(0, Circuit::NullGate(), constValue, Circuit::NullGate());
191 }
192 } else if (op == TypedBinOp::TYPED_MOD) {
193 Bound *xBound = GetBound(x);
194 if (xBound->Lower() >= 0 && xBound->LowerGate() == Circuit::NullGate() && IsArrayLength(y)) {
195 return new Bound(0, Circuit::NullGate(), -1, y);
196 } else if (xBound->HasLower() && xBound->Lower() >= 0 && acc_.IsConstant(y)
197 && acc_.GetConstantValue(y) != 0) {
198 int constValue = static_cast<int>(acc_.GetConstantValue(y));
199 if (constValue != INT_MIN) {
200 return new Bound(0, Circuit::NullGate(), abs(constValue) - 1, Circuit::NullGate());
201 } else {
202 return new Bound();
203 }
204 } else {
205 return new Bound();
206 }
207 } else if (((acc_.IsConstant(x) || acc_.IsConstant(y)) && op == TypedBinOp::TYPED_ADD) ||
208 (acc_.IsConstant(y) && op == TypedBinOp::TYPED_SUB)) {
209 // x is constant, y is variable.
210 if (acc_.IsConstant(y)) {
211 std::swap(x, y);
212 }
213
214 // Add, Constant now in x
215 int constValue = static_cast<int>(acc_.GetConstantValue(x));
216 if (op == TypedBinOp::TYPED_SUB) {
217 constValue = -constValue;
218 }
219
220 Bound *bound = GetBound(y);
221 if (!bound->HasUpper() || !bound->HasLower()) {
222 return new Bound();
223 }
224
225 int lower = bound->Lower();
226 int upper = bound->Upper();
227 int newLower = lower + constValue;
228 int newUpper = upper + constValue;
229 bool overflow = ((constValue < 0 && (newLower > lower)) ||
230 (constValue > 0 && (newUpper < upper)));
231 if (overflow) {
232 return new Bound();
233 } else {
234 return new Bound(newLower, bound->LowerGate(), newUpper, bound->UpperGate());
235 }
236 } else if (op == TypedBinOp::TYPED_SUB) {
237 Bound *bound = GetBound(x);
238 if (bound->LowerGate() == y) {
239 return new Bound(TypedBinOp::TYPED_GREATEREQ, Circuit::NullGate(), bound->Lower());
240 } else {
241 return new Bound();
242 }
243 } else {
244 return new Bound();
245 }
246 }
247 return nullptr;
248 }
249
DoUnaryArithmeticOp(GateRef gate)250 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::DoUnaryArithmeticOp(GateRef gate)
251 {
252 auto op = acc_.GetTypedUnAccessor(gate).GetTypedUnOp();
253 auto x = FindBoundGate(acc_.GetValueIn(gate, 0));
254 int constValue = 0;
255 if (op == TypedUnOp::TYPED_INC) {
256 constValue = 1;
257 } else if (op == TypedUnOp::TYPED_DEC) {
258 constValue = -1;
259 } else {
260 return new Bound();
261 }
262 Bound *bound = GetBound(x);
263 // only support which bounds has been calculated
264 if (!bound->HasUpper() || !bound->HasLower()) {
265 return new Bound();
266 }
267
268 int lower = bound->Lower();
269 int upper = bound->Upper();
270 int newLower = lower + constValue;
271 int newUpper = upper + constValue;
272 bool overflow = ((constValue < 0 && (newLower > lower)) ||
273 (constValue > 0 && (newUpper < upper)));
274 if (overflow) {
275 return new Bound();
276 } else {
277 return new Bound(newLower, bound->LowerGate(), newUpper, bound->UpperGate());
278 }
279 }
280
InLoop(GateRef loopHeader,GateRef gate)281 bool ArrayBoundsCheckElimination::InLoop(GateRef loopHeader, GateRef gate)
282 {
283 while (gate != acc_.GetStateRoot()) {
284 if (gate == loopHeader) {
285 return true;
286 } else {
287 gate = acc_.GetState(gate, 0);
288 }
289 }
290 return false;
291 }
292
DoPhi(GateRef gate)293 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::DoPhi(GateRef gate)
294 {
295 Bound *bound = nullptr;
296 size_t valueSize = acc_.GetInValueCount(gate);
297 GateRef stateIn = acc_.GetState(gate);
298 bool isLoopHead = acc_.IsLoopHead(stateIn);
299 bool hasUpper = true;
300 bool hasLower = true;
301 for (size_t i = 0; i < valueSize; i++) {
302 GateRef value = FindBoundGate(acc_.GetValueIn(gate, i));
303 // Check if instruction is connected with phi itself
304 if (isLoopHead && acc_.GetOpCode(value) == OpCode::TYPED_UNARY_OP
305 && InLoop(stateIn, value)) {
306 auto unOp = acc_.GetTypedUnAccessor(value).GetTypedUnOp();
307 switch (unOp) {
308 case TypedUnOp::TYPED_INC: {
309 hasUpper = false;
310 break;
311 }
312 case TypedUnOp::TYPED_DEC: {
313 hasLower = false;
314 break;
315 }
316 default:
317 break;
318 }
319 continue;
320 }
321
322 Bound *vBound = GetBound(value);
323 Bound *curBound;
324 GateRef curGate;
325 int curConstant;
326 GetInstrAndConstValueFromOp(value, curGate, curConstant);
327 if (!vBound->HasUpper() || !vBound->HasLower()) {
328 curBound = new Bound(curConstant, curGate, curConstant, curGate);
329 } else {
330 curBound = vBound;
331 }
332
333 if (curBound) {
334 if (!bound) {
335 bound = curBound->Copy();
336 } else {
337 bound = OrOp(bound, curBound);
338 }
339 } else {
340 bound = new Bound();
341 break;
342 }
343 }
344
345 if (!hasUpper) {
346 bound->RemoveUpper();
347 }
348 if (!hasLower) {
349 bound->RemoveLower();
350 }
351 return bound;
352 }
353
VisitGate(GateRef gate)354 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::VisitGate(GateRef gate)
355 {
356 OpCode op = acc_.GetOpCode(gate);
357 switch (op) {
358 case OpCode::CONSTANT:
359 return DoConstant(gate);
360 case OpCode::TYPED_BINARY_OP:
361 return DoBinaryArithmeticOp(gate);
362 case OpCode::TYPED_UNARY_OP:
363 return DoUnaryArithmeticOp(gate);
364 case OpCode::VALUE_SELECTOR:
365 return DoPhi(gate);
366 default:
367 return nullptr;
368 }
369 return nullptr;
370 }
371
GetInstrAndConstValueFromBinaryOp(GateRef gate,GateRef & other,int & value)372 bool ArrayBoundsCheckElimination::GetInstrAndConstValueFromBinaryOp(GateRef gate, GateRef& other, int& value)
373 {
374 ASSERT(acc_.GetOpCode(gate) == OpCode::TYPED_BINARY_OP);
375 auto op = acc_.GetTypedBinaryOp(gate);
376 auto x = FindBoundGate(acc_.GetValueIn(gate, 0));
377 auto y = FindBoundGate(acc_.GetValueIn(gate, 1));
378 other = x;
379 if ((op == TypedBinOp::TYPED_ADD && (acc_.IsConstant(x) || acc_.IsConstant(y)))
380 || (op == TypedBinOp::TYPED_SUB && acc_.IsConstant(y))) {
381 if (acc_.IsConstant(x)) {
382 value = static_cast<int>(acc_.GetConstantValue(x));
383 other = y;
384 } else {
385 value = static_cast<int>(acc_.GetConstantValue(y));
386 other = x;
387 }
388 if (op == TypedBinOp::TYPED_SUB) {
389 value = -value;
390 }
391 } else {
392 return false;
393 }
394 return true;
395 }
396
GetInstrAndConstValueFromUnaryOp(GateRef gate,GateRef & other,int & value)397 bool ArrayBoundsCheckElimination::GetInstrAndConstValueFromUnaryOp(GateRef gate, GateRef& other, int& value)
398 {
399 ASSERT(acc_.GetOpCode(gate) == OpCode::TYPED_UNARY_OP);
400 auto op = acc_.GetTypedUnAccessor(gate).GetTypedUnOp();
401 auto x = FindBoundGate(acc_.GetValueIn(gate, 0));
402 if (op == TypedUnOp::TYPED_INC) {
403 value = 1;
404 other = x;
405 } else if (op == TypedUnOp::TYPED_DEC) {
406 value = -1;
407 other = x;
408 } else {
409 return false;
410 }
411 return true;
412 }
413
GetInstrAndConstValueFromOp(GateRef gate,GateRef & instrValue,int & constValue)414 void ArrayBoundsCheckElimination::GetInstrAndConstValueFromOp(GateRef gate, GateRef& instrValue, int& constValue)
415 {
416 int base = 0;
417 constValue = 0;
418 instrValue = gate;
419 if (acc_.IsConstant(gate)) {
420 constValue = static_cast<int>(acc_.GetConstantValue(gate));
421 instrValue = Circuit::NullGate();
422 return ;
423 }
424
425 while (acc_.GetOpCode(gate) == OpCode::TYPED_BINARY_OP ||
426 acc_.GetOpCode(gate) == OpCode::TYPED_UNARY_OP) {
427 bool flag = false;
428 int value = 0;
429 GateRef other = Circuit::NullGate();
430 if (acc_.GetOpCode(gate) == OpCode::TYPED_BINARY_OP) {
431 flag = GetInstrAndConstValueFromBinaryOp(gate, other, value);
432 } else if (acc_.GetOpCode(gate) == OpCode::TYPED_UNARY_OP) {
433 flag = GetInstrAndConstValueFromUnaryOp(gate, other, value);
434 }
435 if (!flag) {
436 break;
437 }
438 if (acc_.IsConstant(other)) {
439 base += value + static_cast<int>(acc_.GetConstantValue(other));
440 constValue = base;
441 instrValue = Circuit::NullGate();
442 break ;
443 } else {
444 base += value;
445 constValue = base;
446 instrValue = other;
447 gate = other;
448 }
449 }
450 }
451
GetBound(GateRef gate)452 ArrayBoundsCheckElimination::Bound *ArrayBoundsCheckElimination::GetBound(GateRef gate)
453 {
454 if (gate == Circuit::NullGate()) {
455 return nullptr;
456 }
457 if (!bounds_[acc_.GetId(gate)]) {
458 bounds_[acc_.GetId(gate)] = new BoundStack(chunk_);
459 Bound *bound = VisitGate(gate);
460 if (bound) {
461 bounds_[acc_.GetId(gate)]->push_back(bound);
462 }
463 if (bounds_[acc_.GetId(gate)]->size() == 0) {
464 bounds_[acc_.GetId(gate)]->push_back(new Bound());
465 }
466 } else if (bounds_[acc_.GetId(gate)]->size() == 0) {
467 return new Bound();
468 }
469 return bounds_[acc_.GetId(gate)]->back();
470 }
471
UpdateBound(IntegerStack & pushed,GateRef gate,Bound * bound)472 void ArrayBoundsCheckElimination::UpdateBound(IntegerStack &pushed, GateRef gate, Bound *bound)
473 {
474 if (acc_.IsConstant(gate)) {
475 // No bound update for constants
476 return;
477 }
478 if (!bounds_[acc_.GetId(gate)]) {
479 GetBound(gate);
480 }
481 Bound* top = nullptr;
482 if (bounds_[acc_.GetId(gate)]->size() > 0) {
483 top = bounds_[acc_.GetId(gate)]->back();
484 }
485 if (top) {
486 bound = AndOp(bound, top);
487 }
488 bounds_[acc_.GetId(gate)]->push_back(bound);
489 pushed.push_back(acc_.GetId(gate));
490 }
491
492 /*
493 x op y + constValue
494 for example:
495 x >= Circuit::NullGate() + 0
496 x < Length + 0
497 */
UpdateBound(IntegerStack & pushed,GateRef x,TypedBinOp op,GateRef instrValue,int constValue)498 void ArrayBoundsCheckElimination::UpdateBound(IntegerStack &pushed, GateRef x, TypedBinOp op,
499 GateRef instrValue, int constValue)
500 {
501 if (op == TypedBinOp::TYPED_GREATER) { // x < 3 -> x <= 4
502 op = TypedBinOp::TYPED_GREATEREQ;
503 // Cannot Represent c > INT_MAX, do not update bounds
504 if (constValue == INT_MAX && instrValue == Circuit::NullGate()) {
505 return;
506 }
507 constValue++;
508 } else if (op == TypedBinOp::TYPED_LESS) { // x > 3 -> x >= 2
509 op = TypedBinOp::TYPED_LESSEQ;
510 // Cannot Represent c < INT_MIN, do not update bounds
511 if (constValue == INT_MIN && instrValue == Circuit::NullGate()) {
512 return;
513 }
514 constValue--;
515 }
516 Bound *bound = new Bound(op, instrValue, constValue);
517 UpdateBound(pushed, x, bound);
518 }
519
520 // Add if condition when x is a variable, x op y
AddIfCondition(IntegerStack & pushed,GateRef x,GateRef y,TypedBinOp op)521 void ArrayBoundsCheckElimination::AddIfCondition(IntegerStack &pushed, GateRef x, GateRef y, TypedBinOp op)
522 {
523 if (acc_.IsConstant(x)) { // x must be non-constant!
524 return;
525 }
526 int constValue;
527 GateRef instrValue;
528 GetInstrAndConstValueFromOp(y, instrValue, constValue);
529 UpdateBound(pushed, x, op, instrValue, constValue);
530 }
531
IsArrayLength(GateRef gate)532 bool ArrayBoundsCheckElimination::IsArrayLength(GateRef gate)
533 {
534 if (gate == Circuit::NullGate()) {
535 return false;
536 }
537 OpCode op = acc_.GetOpCode(gate);
538 switch (op) {
539 case OpCode::LOAD_ARRAY_LENGTH:
540 case OpCode::LOAD_TYPED_ARRAY_LENGTH:
541 return true;
542 default:
543 return false;
544 }
545 UNREACHABLE();
546 return false;
547 }
548
FindBoundGate(GateRef gate)549 GateRef ArrayBoundsCheckElimination::FindBoundGate(GateRef gate)
550 {
551 OpCode op = acc_.GetOpCode(gate);
552 switch (op) {
553 // skip gate
554 case OpCode::RANGE_GUARD:
555 gate = FindBoundGate(acc_.GetValueIn(gate, 0));
556 break;
557 case OpCode::INDEX_CHECK: // get index
558 gate = FindBoundGate(acc_.GetValueIn(gate, 1));
559 break;
560 default:
561 break;
562 }
563 return gate;
564 }
565
InArrayBound(Bound * bound,GateRef length,GateRef array)566 bool ArrayBoundsCheckElimination::InArrayBound(Bound *bound, GateRef length, GateRef array)
567 {
568 if (!bound || array == Circuit::NullGate()) {
569 return false;
570 }
571
572 if (bound->Lower() >= 0 && bound->LowerGate() == Circuit::NullGate() &&
573 bound->Upper() < 0 && bound->UpperGate() != Circuit::NullGate()) {
574 if (length != Circuit::NullGate() && bound->UpperGate() == length) {
575 return true;
576 }
577 }
578
579 return false;
580 }
581
RemoveIndexCheck(GateRef gate)582 void ArrayBoundsCheckElimination::RemoveIndexCheck(GateRef gate)
583 {
584 ASSERT(acc_.GetDependCount(gate) == 1);
585 ASSERT(acc_.GetStateCount(gate) == 1);
586 ASSERT(acc_.GetInValueCount(gate) == 2); // 2: ValueCount
587
588 GateRef depend = acc_.GetDep(gate);
589 GateRef state = acc_.GetState(gate);
590 GateRef value = acc_.GetValueIn(gate, 1); // Index
591
592 acc_.ReplaceGate(gate, state, depend, value);
593 }
594
CheckLoop(GateRef array,GateRef lowerGate,int lower,GateRef upperGate,int upper)595 bool ArrayBoundsCheckElimination::CheckLoop(GateRef array, GateRef lowerGate, int lower, GateRef upperGate, int upper)
596 {
597 if (IsArrayLength(upperGate) && FindBoundGate(acc_.GetValueIn(upperGate, 0)) == array) {
598 if (upper >= 0) {
599 return false;
600 }
601 }
602 if (IsArrayLength(lowerGate) && FindBoundGate(acc_.GetValueIn(lowerGate, 0)) == array) {
603 if (lower >= 0) {
604 return false;
605 }
606 }
607 return true;
608 }
609
LoopInvariant(GateRegion * loopHeader,GateRef gate)610 bool ArrayBoundsCheckElimination::LoopInvariant(GateRegion *loopHeader, GateRef gate)
611 {
612 if (gate == Circuit::NullGate()) {
613 return true;
614 }
615 auto gateRegion = graphLinearizer_.GateToRegion(gate);
616 GateRegion* g = loopHeader->GetDominator();
617 while (g != nullptr) {
618 if (g == gateRegion) {
619 return true;
620 }
621 if (g == g->GetDominator()) { // entry
622 break ;
623 }
624 g = g->GetDominator();
625 }
626 return false;
627 }
628
Predicate(GateRef left,TypedBinOp cond,GateRef right)629 GateRef ArrayBoundsCheckElimination::Predicate(GateRef left, TypedBinOp cond, GateRef right)
630 {
631 return builder_.InsertRangeCheckPredicate(left, cond, right);
632 }
633
PredicateCmpWithConst(GateRef left,TypedBinOp cond,int32_t right)634 GateRef ArrayBoundsCheckElimination::PredicateCmpWithConst(GateRef left, TypedBinOp cond, int32_t right)
635 {
636 GateRef constGate = builder_.Int32(right);
637 return Predicate(left, cond, constGate);
638 }
639
PredicateAdd(GateRef left,int32_t leftConst,TypedBinOp cond,GateRef right)640 GateRef ArrayBoundsCheckElimination::PredicateAdd(GateRef left, int32_t leftConst, TypedBinOp cond, GateRef right)
641 {
642 GateRef constGate = builder_.Int32(leftConst);
643 GateRef binaryOpGate = builder_.InsertTypedBinaryop(left, constGate, GateType::NumberType(),
644 GateType::NumberType(), GateType::AnyType(),
645 PGOTypeRef::NoneType(), TypedBinOp::TYPED_ADD);
646 return Predicate(binaryOpGate, cond, right);
647 }
648
PredicateAddCmpWithConst(GateRef left,int32_t leftConst,TypedBinOp cond,int32_t right)649 GateRef ArrayBoundsCheckElimination::PredicateAddCmpWithConst(GateRef left, int32_t leftConst,
650 TypedBinOp cond, int32_t right)
651 {
652 GateRef constGate = builder_.Int32(right);
653 return PredicateAdd(left, leftConst, cond, constGate);
654 }
655
LoopInvariantMotionForIndexCheck(GateRef array,GateRef length,GateRef lowerGate,int lower,GateRef upperGate,int upper,bool isTypedArray)656 void ArrayBoundsCheckElimination::LoopInvariantMotionForIndexCheck(GateRef array, GateRef length,
657 GateRef lowerGate, int lower,
658 GateRef upperGate, int upper,
659 bool isTypedArray)
660 {
661 // lower > 0
662 if (lowerGate != Circuit::NullGate()) {
663 if (lower == 0) {
664 // lowerGate >= 0
665 PredicateCmpWithConst(lowerGate, TypedBinOp::TYPED_GREATEREQ, 0);
666 } else if (lower > 0) {
667 // lowerGate + lower >= 0
668 PredicateAddCmpWithConst(lowerGate, lower, TypedBinOp::TYPED_GREATEREQ, 0);
669 } else {
670 // lowerGate + lower < 0
671 // lower < 0
672 // lowerGate < -lower
673 lower++;
674 lower = -lower;
675 PredicateCmpWithConst(lowerGate, TypedBinOp::TYPED_GREATER, lower);
676 }
677 }
678
679 // LOAD LENGTH if necessary
680 if (length == Circuit::NullGate()) {
681 length = builder_.InsertLoadArrayLength(array, isTypedArray);
682 }
683
684 if (upperGate == Circuit::NullGate()) {
685 ASSERT(upper >= 0);
686 PredicateCmpWithConst(length, TypedBinOp::TYPED_GREATER, upper);
687 } else {
688 if (upper == 0) {
689 Predicate(upperGate, TypedBinOp::TYPED_LESS, length);
690 } else if (upper > 0) {
691 // upperGate + upper < length
692 PredicateAdd(upperGate, upper, TypedBinOp::TYPED_LESS, length);
693 } else {
694 // upperGate + upper < length
695 // upper < 0
696 // upperGate < length + (-upper)
697 PredicateAdd(length, -upper, TypedBinOp::TYPED_GREATER, upperGate);
698 }
699 }
700 }
701
ProcessIndexCheck(GateRegion * loopHeader,GateRef gate)702 void ArrayBoundsCheckElimination::ProcessIndexCheck(GateRegion *loopHeader, GateRef gate)
703 {
704 auto length = FindBoundGate(acc_.GetValueIn(gate, 0));
705 auto array = FindBoundGate(acc_.GetValueIn(length, 0));
706 auto index = FindBoundGate(acc_.GetValueIn(gate, 1));
707 Bound *indexBound = GetBound(index);
708 if (!indexBound->HasLower() || !indexBound->HasUpper()) {
709 return;
710 }
711
712 if (InArrayBound(indexBound, length, array)) {
713 RemoveIndexCheck(gate);
714 } else if (loopHeader) {
715 if (!LoopInvariant(loopHeader, array)
716 || !LoopInvariant(loopHeader, indexBound->LowerGate())
717 || !LoopInvariant(loopHeader, indexBound->UpperGate())
718 || (indexBound->LowerGate() == Circuit::NullGate() && indexBound->Lower() < 0)
719 || (indexBound->UpperGate() == Circuit::NullGate() && indexBound->Upper() < 0)) {
720 return;
721 }
722
723 ASSERT(length != Circuit::NullGate());
724 bool isTypedArray = false;
725 if (acc_.GetOpCode(length) == OpCode::LOAD_TYPED_ARRAY_LENGTH) {
726 isTypedArray = true;
727 }
728
729 // Length instrution
730 if (!LoopInvariant(loopHeader, length)) {
731 // Generate length instruction yourself
732 length = Circuit::NullGate();
733 }
734
735 // Insert Before loopHeader State, and if find IF_TRUE and IF_FALSE, insert after the DEPEND_RELAY
736 // if find MERGE, insert after DEPEND_SELECTOR
737 GateRef insertAfter = acc_.GetState(loopHeader->GetState(), 0); // after end
738 GateRef stateIn = insertAfter;
739 GateRef dependIn = insertAfter;
740 acc_.GetStateInAndDependIn(insertAfter, stateIn, dependIn);
741
742 if (!CheckLoop(array, indexBound->LowerGate(), indexBound->Lower(),
743 indexBound->UpperGate(), indexBound->Upper())) {
744 return;
745 }
746
747 Environment env(stateIn, dependIn, {}, circuit_, &builder_);
748 LoopInvariantMotionForIndexCheck(array, length, indexBound->LowerGate(), indexBound->Lower(),
749 indexBound->UpperGate(), indexBound->Upper(), isTypedArray);
750 RemoveIndexCheck(gate);
751 }
752 }
753
ProcessIf(IntegerStack & pushed,GateRegion * parent,OpCode cond)754 void ArrayBoundsCheckElimination::ProcessIf(IntegerStack &pushed, GateRegion *parent, OpCode cond)
755 {
756 auto& gateLists = parent->GetGates();
757 for (int i = static_cast<int>(gateLists.size()) - 1; i >= 0; i--) { // Found the last BinaryOp
758 GateRef gate = gateLists[i];
759 if (gate == Circuit::NullGate()) continue;
760 OpCode opGate = acc_.GetOpCode(gate);
761 if (opGate != OpCode::TYPED_BINARY_OP) {
762 continue ;
763 }
764
765 TypedBinOp op = acc_.GetTypedBinaryOp(gate);
766 GateRef x = FindBoundGate(acc_.GetValueIn(gate, 0));
767 GateRef y = FindBoundGate(acc_.GetValueIn(gate, 1));
768
769 switch (op) {
770 case TypedBinOp::TYPED_LESS:
771 case TypedBinOp::TYPED_LESSEQ:
772 case TypedBinOp::TYPED_GREATER:
773 case TypedBinOp::TYPED_GREATEREQ:
774 case TypedBinOp::TYPED_EQ:
775 case TypedBinOp::TYPED_NOTEQ: {
776 if (cond == OpCode::IF_TRUE) {
777 op = TypedBinaryMetaData::GetRevCompareOp(op);
778 }
779 AddIfCondition(pushed, x, y, op);
780 AddIfCondition(pushed, y, x, TypedBinaryMetaData::GetSwapCompareOp(op));
781 break;
782 }
783 default:
784 break;
785 }
786 break;
787 }
788 }
789
Contain(GateLists & gateLists,GateRef gate)790 bool ArrayBoundsCheckElimination::Contain(GateLists &gateLists, GateRef gate)
791 {
792 for (size_t i = 0; i < gateLists.size(); i++) {
793 if (gateLists[i] == gate) {
794 return true;
795 }
796 }
797 return false;
798 }
799
AddAccessIndexedInfo(GateLists & indices,GateRef gate,int idx,GateRef indexCheck)800 void ArrayBoundsCheckElimination::AddAccessIndexedInfo(GateLists &indices, GateRef gate, int idx, GateRef indexCheck)
801 {
802 IndexCheckInfo *indexCheckInfo = indexCheckInfo_[acc_.GetId(gate)];
803 if (indexCheckInfo == nullptr) {
804 indexCheckInfo = new IndexCheckInfo(chunk_);
805 indexCheckInfo_[acc_.GetId(gate)] = indexCheckInfo;
806 indices.push_back(gate);
807 indexCheckInfo->min_ = idx;
808 indexCheckInfo->max_ = idx;
809 } else if (idx >= indexCheckInfo->min_ && idx <= indexCheckInfo->max_) {
810 RemoveIndexCheck(indexCheck);
811 return;
812 }
813 indexCheckInfo->min_ = std::min(indexCheckInfo->min_, idx);
814 indexCheckInfo->max_ = std::max(indexCheckInfo->max_, idx);
815 indexCheckInfo->list_.push_back(indexCheck);
816 }
817
InBlockMotion(GateLists & indexChecked,GateLists & arrays)818 void ArrayBoundsCheckElimination::InBlockMotion(GateLists &indexChecked, GateLists &arrays)
819 {
820 GateLists indices(chunk_);
821 for (size_t i = 0; i < arrays.size(); i++) {
822 int maxConstant = -1;
823 GateLists listConstant(chunk_);
824 GateRef arrayGate = arrays[i];
825 for (size_t j = 0; j < indexChecked.size(); j++) {
826 GateRef indexCheck = indexChecked[j];
827 // INDEX_CHECK may be dead
828 if (acc_.GetOpCode(indexCheck) != OpCode::INDEX_CHECK) {
829 continue;
830 }
831 GateRef length = FindBoundGate(acc_.GetValueIn(indexCheck, 0));
832 GateRef index = FindBoundGate(acc_.GetValueIn(indexCheck, 1));
833 GateRef array = FindBoundGate(acc_.GetValueIn(length, 0));
834 if (array != arrayGate) {
835 continue;
836 }
837 if (acc_.IsConstant(index)) {
838 int constValue = static_cast<int>(acc_.GetConstantValue(index));
839 if (constValue >= 0 && constValue <= maxConstant) {
840 RemoveIndexCheck(indexCheck);
841 } else if (constValue >= 0 && constValue > maxConstant) {
842 maxConstant = constValue;
843 listConstant.push_back(indexCheck);
844 }
845 } else {
846 int lastInteger;
847 GateRef lastGate;
848 GetInstrAndConstValueFromOp(index, lastGate, lastInteger);
849 if (lastInteger >= 0 && lastGate == Circuit::NullGate()) { // IsConstant
850 if (lastInteger <= maxConstant) {
851 RemoveIndexCheck(indexCheck);
852 } else {
853 maxConstant = lastInteger;
854 listConstant.push_back(indexCheck);
855 }
856 } else if (lastGate != Circuit::NullGate()) {
857 AddAccessIndexedInfo(indices, lastGate, lastInteger, indexCheck);
858 } // when lastInteger < 0, dont remove IndexCheck
859 }
860 }
861
862 // Iterate over all different indices
863 for (size_t j = 0; j < indices.size(); j++) {
864 GateRef index = indices[j];
865
866 IndexCheckInfo *info = indexCheckInfo_[acc_.GetId(index)];
867 ASSERT(info != nullptr);
868
869 // maybe index < 0, max > 0
870 // max + index in [0, a.length)
871 // min + index overflow !!!, min + index > 0
872 // so, min + index >= INT_MIN, min >= INT_MIN - index
873 // max in [-index, a.length - index)
874 // min >= INT_MIN + max
875 bool rangeCond = (info->max_ < 0 || info->max_ + INT_MIN <= info->min_);
876 if (info->list_.size() > 2 && rangeCond) { // 2: size
877 GateRef insertAfter = info->list_.front();
878 GateRef length = FindBoundGate(acc_.GetValueIn(insertAfter, 0));
879 ASSERT(length != Circuit::NullGate());
880
881 Environment env(insertAfter, circuit_, &builder_);
882
883 // Calculate lower bound
884 GateRef lowerCompare = index;
885 if (info->min_ > 0) {
886 GateRef minGate = builder_.Int32(info->min_);
887 lowerCompare = builder_.InsertTypedBinaryop(lowerCompare, minGate,
888 GateType::NumberType(), GateType::NumberType(),
889 GateType::AnyType(), PGOTypeRef::NoneType(),
890 TypedBinOp::TYPED_ADD);
891 } else if (info->min_ < 0) {
892 GateRef minGate = builder_.Int32(-info->min_);
893 lowerCompare = builder_.InsertTypedBinaryop(lowerCompare, minGate,
894 GateType::NumberType(), GateType::NumberType(),
895 GateType::AnyType(), PGOTypeRef::NoneType(),
896 TypedBinOp::TYPED_SUB);
897 }
898
899 PredicateCmpWithConst(lowerCompare, TypedBinOp::TYPED_GREATEREQ, 0);
900
901 // Calculate upper bound
902 GateRef upperCompare = index;
903 if (info->max_ != 0) {
904 if (info->max_ > 0) {
905 GateRef maxGate = builder_.Int32(info->max_);
906 upperCompare = builder_.InsertTypedBinaryop(upperCompare, maxGate,
907 GateType::NumberType(), GateType::NumberType(),
908 GateType::AnyType(), PGOTypeRef::NoneType(),
909 TypedBinOp::TYPED_ADD);
910 } else if (info->max_ < 0) {
911 GateRef maxGate = builder_.Int32(-info->max_);
912 upperCompare = builder_.InsertTypedBinaryop(upperCompare, maxGate,
913 GateType::NumberType(), GateType::NumberType(),
914 GateType::AnyType(), PGOTypeRef::NoneType(),
915 TypedBinOp::TYPED_SUB);
916 }
917 }
918
919 Predicate(upperCompare, TypedBinOp::TYPED_LESS, length);
920 for (auto& indexCheck: (info->list_)) {
921 RemoveIndexCheck(indexCheck);
922 }
923 }
924 }
925
926 // index only constant
927 if (listConstant.size() > 1) {
928 GateRef firIndexCheckGate = listConstant.front();
929 Environment env(firIndexCheckGate, circuit_, &builder_);
930 GateRef length = FindBoundGate(acc_.GetValueIn(firIndexCheckGate, 0));
931 ASSERT(length != Circuit::NullGate());
932 ASSERT(maxConstant >= 0);
933 PredicateCmpWithConst(length, TypedBinOp::TYPED_GREATER, maxConstant); // length > index
934 for (size_t j = 0; j < listConstant.size(); j++) {
935 GateRef indexCheck = listConstant[j];
936 RemoveIndexCheck(indexCheck);
937 }
938 }
939
940 for (size_t j = 0; j < indices.size(); j++) {
941 indexCheckInfo_[acc_.GetId(indices[j])] = nullptr;
942 }
943 indices.clear();
944 }
945 }
946
CalcBounds(GateRegion * block,GateRegion * loopHeader)947 void ArrayBoundsCheckElimination::CalcBounds(GateRegion *block, GateRegion *loopHeader)
948 {
949 // Pushed stack for condition
950 IntegerStack pushed(chunk_);
951
952 // Process If
953 GateRegion *parent = block->GetDominator();
954 if (parent != nullptr) {
955 auto gate = block->GetGates().front();
956 auto op = acc_.GetOpCode(gate);
957 if (op == OpCode::IF_TRUE || op == OpCode::IF_FALSE) { // Recognize If (including the condition in forloop)
958 ProcessIf(pushed, parent, op);
959 }
960 }
961
962 GateLists indexChecked(chunk_);
963 GateLists arrays(chunk_);
964
965 auto& gateList_ = block->GetGates();
966 for (size_t i = 0; i < gateList_.size(); i++) { // Visit GateUnion
967 GateRef gate = gateList_[i];
968 auto op = acc_.GetOpCode(gate);
969 if (op == OpCode::INDEX_CHECK) {
970 auto length = FindBoundGate(acc_.GetValueIn(gate, 0));
971 auto index = FindBoundGate(acc_.GetValueIn(gate, 1));
972 auto array = FindBoundGate(acc_.GetValueIn(length, 0));
973
974 ProcessIndexCheck(loopHeader, gate);
975 indexChecked.push_back(gate);
976
977 if (!Contain(arrays, array)) {
978 arrays.push_back(array);
979 }
980
981 // Give IndexCheck a bound [0, Length - 1]
982 Bound *b = GetBound(index);
983 if (b->LowerGate() == Circuit::NullGate()) { // LowerBound is the Constant !!!
984 UpdateBound(pushed, index, TypedBinOp::TYPED_GREATEREQ, Circuit::NullGate(), 0);
985 }
986 if (!b->HasUpper() && length != Circuit::NullGate()) { // default dont know the Length
987 UpdateBound(pushed, index, TypedBinOp::TYPED_LESS, length, 0);
988 }
989 }
990 }
991
992 InBlockMotion(indexChecked, arrays);
993
994 auto& dominatedRegions_ = block->GetDominatedRegions();
995 for (size_t i = 0; i < dominatedRegions_.size(); i++) {
996 GateRegion *nex = dominatedRegions_[i];
997 if (block->IsLoopHead() && (block->GetLoopIndex() == nex->GetLoopIndex()
998 || nex->GetLoopDepth() > block->GetLoopDepth())) {
999 CalcBounds(nex, block);
1000 } else {
1001 CalcBounds(nex, loopHeader);
1002 }
1003 }
1004
1005 for (size_t i = 0; i < pushed.size(); i++) {
1006 bounds_[pushed[i]]->pop_back();
1007 }
1008 }
1009 }
1010