• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021-2025 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 #include "bounds_analysis.h"
16 #include "dominators_tree.h"
17 #include "optimizer/ir/datatype.h"
18 #include "optimizer/ir/graph.h"
19 #include "optimizer/ir/graph_visitor.h"
20 #include "optimizer/ir/basicblock.h"
21 #include "optimizer/ir/inst.h"
22 #include "compiler/optimizer/ir/analysis.h"
23 #include "optimizer/analysis/loop_analyzer.h"
24 
25 namespace ark::compiler {
BoundsRange(int64_t val,DataType::Type type)26 BoundsRange::BoundsRange(int64_t val, DataType::Type type) : BoundsRange(val, val, nullptr, type) {}
27 
IsStringLength(const Inst * inst)28 static bool IsStringLength(const Inst *inst)
29 {
30     ASSERT(inst != nullptr);
31     if (inst->GetOpcode() != Opcode::Shr || inst->GetInput(0).GetInst()->GetOpcode() != Opcode::LenArray) {
32         return false;
33     }
34     auto c = inst->GetInput(1).GetInst();
35     return c->IsConst() && c->CastToConstant()->GetInt64Value() == 1;
36 }
37 
IsLenArray(const Inst * inst)38 static bool IsLenArray(const Inst *inst)
39 {
40     ASSERT(inst != nullptr);
41     return inst->GetOpcode() == Opcode::LenArray || IsStringLength(inst);
42 }
43 
BoundsRange(int64_t left,int64_t right,const Inst * inst,DataType::Type type)44 BoundsRange::BoundsRange(int64_t left, int64_t right, const Inst *inst, [[maybe_unused]] DataType::Type type)
45     : left_(left), right_(right), lenArray_(inst)
46 {
47     ASSERT(inst == nullptr || IsLenArray(inst));
48     ASSERT(left <= right);
49     ASSERT(GetMin(type) <= left);
50     ASSERT(right <= GetMax(type));
51 }
52 
SetLenArray(const Inst * inst)53 void BoundsRange::SetLenArray(const Inst *inst)
54 {
55     ASSERT(inst != nullptr && IsLenArray(inst));
56     lenArray_ = inst;
57 }
58 
GetLeft() const59 int64_t BoundsRange::GetLeft() const
60 {
61     return left_;
62 }
63 
GetRight() const64 int64_t BoundsRange::GetRight() const
65 {
66     return right_;
67 }
68 
69 /**
70  * Neg current range.  Type of current range is saved.
71  * NEG([x1, x2]) = [-x2, -x1]
72  */
Neg() const73 BoundsRange BoundsRange::Neg() const
74 {
75     auto right = left_ == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -left_;
76     auto left = right_ == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -right_;
77     return BoundsRange(left, right);
78 }
79 
80 /**
81  * Abs current range.  Type of current range is saved.
82  * 1. if (x1 >= 0 && x2 >= 0) -> ABS([x1, x2]) = [x1, x2]
83  * 2. if (x1 < 0 && x2 < 0) -> ABS([x1, x2]) = [-x2, -x1]
84  * 3. if (x1 * x2 < 0) -> ABS([x1, x2]) = [0, MAX(ABS(x1), ABS(x2))]
85  */
Abs() const86 BoundsRange BoundsRange::Abs() const
87 {
88     auto val1 = left_ == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(left_);
89     auto val2 = right_ == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(right_);
90     auto right = std::max(val1, val2);
91     int64_t left = 0;
92     // NOLINTNEXTLINE (hicpp-signed-bitwise)
93     if ((left_ ^ right_) >= 0) {
94         left = std::min(val1, val2);
95     }
96     return BoundsRange(left, right);
97 }
98 
99 /**
100  * Add to current range.  Type of current range is saved.
101  * [x1, x2] + [y1, y2] = [x1 + y1, x2 + y2]
102  */
Add(const BoundsRange & range) const103 BoundsRange BoundsRange::Add(const BoundsRange &range) const
104 {
105     auto left = AddWithOverflowCheck(left_, range.GetLeft());
106     auto right = AddWithOverflowCheck(right_, range.GetRight());
107     if (!left || !right) {
108         return BoundsRange();
109     }
110     return BoundsRange(left.value(), right.value());
111 }
112 
113 /**
114  * Subtract from current range.
115  * [x1, x2] - [y1, y2] = [x1 - y2, x2 - y1]
116  */
Sub(const BoundsRange & range) const117 BoundsRange BoundsRange::Sub(const BoundsRange &range) const
118 {
119     auto negRight = (range.GetRight() == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -range.GetRight());
120     auto left = AddWithOverflowCheck(left_, negRight);
121     auto negLeft = (range.GetLeft() == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -range.GetLeft());
122     auto right = AddWithOverflowCheck(right_, negLeft);
123     if (!left || !right) {
124         return BoundsRange();
125     }
126     return BoundsRange(left.value(), right.value());
127 }
128 
129 /**
130  * Multiply current range.
131  * [x1, x2] * [y1, y2] = [min(x1y1, x1y2, x2y1, x2y2), max(x1y1, x1y2, x2y1, x2y2)]
132  */
Mul(const BoundsRange & range) const133 BoundsRange BoundsRange::Mul(const BoundsRange &range) const
134 {
135     auto m1 = MulWithOverflowCheck(left_, range.GetLeft());
136     auto m2 = MulWithOverflowCheck(left_, range.GetRight());
137     auto m3 = MulWithOverflowCheck(right_, range.GetLeft());
138     auto m4 = MulWithOverflowCheck(right_, range.GetRight());
139     if (!m1 || !m2 || !m3 || !m4) {
140         return BoundsRange();
141     }
142     auto left = std::min(m1.value(), std::min(m2.value(), std::min(m3.value(), m4.value())));
143     auto right = std::max(m1.value(), std::max(m2.value(), std::max(m3.value(), m4.value())));
144     return BoundsRange(left, right);
145 }
146 
147 /**
148  * Division current range on constant range.
149  * [x1, x2] / [y, y] = [min(x1/y, x2/y), max(x1/y, x2/y)]
150  */
Div(const BoundsRange & range) const151 BoundsRange BoundsRange::Div(const BoundsRange &range) const
152 {
153     if (range.GetLeft() != range.GetRight() || range.GetLeft() == 0) {
154         return BoundsRange();
155     }
156     auto m1 = DivWithOverflowCheck(left_, range.GetLeft());
157     auto m2 = DivWithOverflowCheck(right_, range.GetLeft());
158     if (!m1 || !m2) {
159         return BoundsRange();
160     }
161     auto left = std::min(m1.value(), m2.value());
162     auto right = std::max(m1.value(), m2.value());
163     return BoundsRange(left, right);
164 }
165 
166 /**
167  * Modulus of current range.
168  * mod := max(abs(y1), abs(y2))
169  * [x1, x2] % [y1, y2] = [min(max(x1, -(mod - 1)), 0), max(min(x2, mod - 1), 0)]
170  */
171 /* static */
Mod(const BoundsRange & range)172 BoundsRange BoundsRange::Mod(const BoundsRange &range)
173 {
174     int64_t maxMod = 0;
175     if (range.GetRight() > 0) {
176         maxMod = range.GetRight() - 1;
177     }
178     if (range.GetLeft() == MIN_RANGE_VALUE) {
179         maxMod = MAX_RANGE_VALUE;
180     } else if (range.GetLeft() < 0) {
181         maxMod = std::max(maxMod, -range.GetLeft() - 1);
182     }
183     if (maxMod == 0) {
184         return BoundsRange();
185     }
186     auto left = left_ < 0 ? std::max(left_, -maxMod) : 0;
187     auto right = right_ > 0 ? std::min(right_, maxMod) : 0;
188     return BoundsRange(left, right);
189 }
190 
191 // right shift current range, work only if 'range' is positive constant range
Shr(const BoundsRange & range,DataType::Type type)192 BoundsRange BoundsRange::Shr(const BoundsRange &range, DataType::Type type)
193 {
194     if (!range.IsConst() || range.IsNegative()) {
195         return BoundsRange();
196     }
197     uint64_t sizeMask = DataType::GetTypeSize(type, Arch::NONE) - 1;
198     auto n = static_cast<uint64_t>(range.GetLeft()) & sizeMask;
199     auto narrowed = BoundsRange(*this).FitInType(type);
200     // for fixed n > 0 (x Shr n) is increasing on [MIN_RANGE_VALUE, -1] and
201     // on [0, MAX_RANGE_VALUE], but (-1 Shr n) > (0 Shr n)
202     if (narrowed.GetLeft() < 0 && narrowed.GetRight() >= 0 && n > 0) {
203         auto r = static_cast<int64_t>(~static_cast<uint64_t>(0) >> n);
204         return BoundsRange(0, r);
205     }
206     auto l = static_cast<int64_t>(static_cast<uint64_t>(narrowed.GetLeft()) >> n);
207     auto r = static_cast<int64_t>(static_cast<uint64_t>(narrowed.GetRight()) >> n);
208     return BoundsRange(l, r);
209 }
210 
211 // arithmetic right shift current range, work only if 'range' is positive constant range
AShr(const BoundsRange & range,DataType::Type type)212 BoundsRange BoundsRange::AShr(const BoundsRange &range, DataType::Type type)
213 {
214     if (!range.IsConst() || range.IsNegative()) {
215         return BoundsRange();
216     }
217     uint64_t sizeMask = DataType::GetTypeSize(type, Arch::NONE) - 1;
218     auto n = static_cast<uint64_t>(range.GetLeft()) & sizeMask;
219     // NOLINTNEXTLINE(hicpp-signed-bitwise)
220     return BoundsRange(left_ >> n, right_ >> n);
221 }
222 
223 // left shift current range, work only if 'range' is positive constant range
Shl(const BoundsRange & range,DataType::Type type)224 BoundsRange BoundsRange::Shl(const BoundsRange &range, DataType::Type type)
225 {
226     if (!range.IsConst() || range.IsNegative()) {
227         return BoundsRange();
228     }
229     uint64_t sizeMask = DataType::GetTypeSize(type, Arch::NONE) - 1;
230     auto n = static_cast<uint64_t>(range.GetLeft()) & sizeMask;
231     if (n > 0) {
232         auto maxBits = BITS_PER_UINT64 - n - 1;
233         auto maxValue = static_cast<int64_t>(static_cast<uint64_t>(1) << maxBits);
234         if (left_ < -maxValue || right_ >= maxValue) {
235             // shift can overflow
236             return BoundsRange();
237         }
238     }
239     auto l = static_cast<int64_t>(static_cast<uint64_t>(left_) << n);
240     auto r = static_cast<int64_t>(static_cast<uint64_t>(right_) << n);
241     return BoundsRange(l, r);
242 }
243 
244 /**
245  * Count difference between range and current range. Type of current range is saved.
246  * DIFF([x1, x2], [y1, y2]) = [x1 - y1, x2 - y2]
247  * If result range is incorrect (left > right), it returns maximal range
248  */
Diff(const BoundsRange & range) const249 BoundsRange BoundsRange::Diff(const BoundsRange &range) const
250 {
251     auto negLeft = (range.GetLeft() == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -range.GetLeft());
252     auto left = AddWithOverflowCheck(left_, negLeft);
253     auto negRight = (range.GetRight() == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -range.GetRight());
254     auto right = AddWithOverflowCheck(right_, negRight);
255     if (!left || !right || left.value() > right.value()) {
256         return BoundsRange();
257     }
258     return BoundsRange(left.value(), right.value());
259 }
260 
And(const BoundsRange & range)261 BoundsRange BoundsRange::And(const BoundsRange &range)
262 {
263     if (!range.IsConst()) {
264         return BoundsRange();
265     }
266     auto n = static_cast<uint64_t>(range.GetLeft());
267     static constexpr uint32_t BITS_63 = 63;
268     if ((n >> BITS_63) == 1) {
269         return BoundsRange();
270     }
271     return BoundsRange(0, n);
272 }
273 
IsConst() const274 bool BoundsRange::IsConst() const
275 {
276     return left_ == right_;
277 }
278 
IsMaxRange(DataType::Type type) const279 bool BoundsRange::IsMaxRange(DataType::Type type) const
280 {
281     return left_ <= GetMin(type) && right_ >= GetMax(type);
282 }
283 
IsEqual(const BoundsRange & range) const284 bool BoundsRange::IsEqual(const BoundsRange &range) const
285 {
286     return left_ == range.GetLeft() && right_ == range.GetRight();
287 }
288 
IsLess(const BoundsRange & range) const289 bool BoundsRange::IsLess(const BoundsRange &range) const
290 {
291     return right_ < range.GetLeft();
292 }
293 
IsLess(const Inst * inst) const294 bool BoundsRange::IsLess(const Inst *inst) const
295 {
296     ASSERT(inst != nullptr);
297     if (!IsLenArray(inst)) {
298         return false;
299     }
300     return inst == lenArray_;
301 }
302 
IsMore(const BoundsRange & range) const303 bool BoundsRange::IsMore(const BoundsRange &range) const
304 {
305     return left_ > range.GetRight();
306 }
307 
IsMoreOrEqual(const BoundsRange & range) const308 bool BoundsRange::IsMoreOrEqual(const BoundsRange &range) const
309 {
310     return left_ >= range.GetRight();
311 }
312 
IsWithin(const BoundsRange & range) const313 bool BoundsRange::IsWithin(const BoundsRange &range) const
314 {
315     return left_ > range.GetLeft() && right_ < range.GetRight();
316 }
317 
IsNotNegative() const318 bool BoundsRange::IsNotNegative() const
319 {
320     return left_ >= 0;
321 }
322 
IsNegative() const323 bool BoundsRange::IsNegative() const
324 {
325     return right_ < 0;
326 }
327 
IsPositive() const328 bool BoundsRange::IsPositive() const
329 {
330     return left_ > 0;
331 }
332 
IsNotPositive() const333 bool BoundsRange::IsNotPositive() const
334 {
335     return right_ <= 0;
336 }
337 
CanOverflow(DataType::Type type) const338 bool BoundsRange::CanOverflow(DataType::Type type) const
339 {
340     return left_ <= GetMin(type) || right_ >= GetMax(type);
341 }
342 
CanOverflowNeg(DataType::Type type) const343 bool BoundsRange::CanOverflowNeg(DataType::Type type) const
344 {
345     return right_ >= GetMax(type) || (left_ <= 0 && 0 <= right_);
346 }
347 
348 /**
349  * Return the minimal value for a type.
350  *
351  * We consider that REFERENCE type has only non-negative address values
352  */
GetMin(DataType::Type type)353 int64_t BoundsRange::GetMin(DataType::Type type)
354 {
355     ASSERT(!IsFloatType(type));
356     switch (type) {
357         case DataType::BOOL:
358         case DataType::UINT8:
359         case DataType::UINT16:
360         case DataType::UINT32:
361         case DataType::UINT64:
362         case DataType::REFERENCE:
363             return 0;
364         case DataType::INT8:
365             return INT8_MIN;
366         case DataType::INT16:
367             return INT16_MIN;
368         case DataType::INT32:
369             return INT32_MIN;
370         case DataType::INT64:
371             return INT64_MIN;
372         default:
373             UNREACHABLE();
374     }
375 }
376 
377 /**
378  * Return the maximal value for a type.
379  *
380  * For REFERENCE we are interested in whether it is NULL or not.  Set the
381  * maximum to INT64_MAX regardless the real architecture bitness.
382  */
GetMax(DataType::Type type)383 int64_t BoundsRange::GetMax(DataType::Type type)
384 {
385     ASSERT(!IsFloatType(type));
386     switch (type) {
387         case DataType::BOOL:
388             return 1;
389         case DataType::UINT8:
390             return UINT8_MAX;
391         case DataType::UINT16:
392             return UINT16_MAX;
393         case DataType::UINT32:
394             return UINT32_MAX;
395         case DataType::INT8:
396             return INT8_MAX;
397         case DataType::INT16:
398             return INT16_MAX;
399         case DataType::INT32:
400             return INT32_MAX;
401         case DataType::INT64:
402         case DataType::UINT64:
403             return INT64_MAX;
404         case DataType::REFERENCE:
405             return INT64_MAX;
406         default:
407             UNREACHABLE();
408     }
409 }
410 
FitInType(DataType::Type type) const411 BoundsRange BoundsRange::FitInType(DataType::Type type) const
412 {
413     auto typeMin = BoundsRange::GetMin(type);
414     auto typeMax = BoundsRange::GetMax(type);
415     BoundsRange res = *this;
416     if (left_ < typeMin || left_ > typeMax || right_ < typeMin || right_ > typeMax) {
417         res = BoundsRange(typeMin, typeMax);
418         res.SetActualLengthLoop(GetActualLengthLoop());
419     }
420     return res;
421 }
422 
Union(const ArenaVector<BoundsRange> & ranges)423 BoundsRange BoundsRange::Union(const ArenaVector<BoundsRange> &ranges)
424 {
425     int64_t min = MAX_RANGE_VALUE;
426     int64_t max = MIN_RANGE_VALUE;
427     for (const auto &range : ranges) {
428         if (range.GetLeft() < min) {
429             min = range.GetLeft();
430         }
431         if (range.GetRight() > max) {
432             max = range.GetRight();
433         }
434     }
435     return BoundsRange(min, max);
436 }
437 
NarrowBoundsByNE(BoundsRange::RangePair const & ranges)438 BoundsRange::RangePair BoundsRange::NarrowBoundsByNE(BoundsRange::RangePair const &ranges)
439 {
440     auto &[left_range, right_range] = ranges;
441     int64_t ll = left_range.GetLeft();
442     int64_t lr = left_range.GetRight();
443     int64_t rl = right_range.GetLeft();
444     int64_t rr = right_range.GetRight();
445     // We can narrow bounds of a range if another is a constant and matches one of the bounds
446     // Mostly needed for a reference comparison with null
447     if (left_range.IsConst() && !right_range.IsConst()) {
448         if (ll == rl) {
449             return {left_range, BoundsRange(rl + 1, rr)};
450         }
451         if (ll == rr) {
452             return {left_range, BoundsRange(rl, rr - 1)};
453         }
454     }
455     if (!left_range.IsConst() && right_range.IsConst()) {
456         if (rl == ll) {
457             return {BoundsRange(ll + 1, lr), right_range};
458         }
459         if (rl == lr) {
460             return {BoundsRange(ll, lr - 1), right_range};
461         }
462     }
463     return ranges;
464 }
465 
NarrowBoundsCase1(ConditionCode cc,BoundsRange::RangePair const & ranges)466 BoundsRange::RangePair BoundsRange::NarrowBoundsCase1(ConditionCode cc, BoundsRange::RangePair const &ranges)
467 {
468     auto &[left_range, right_range] = ranges;
469     int64_t lr = left_range.GetRight();
470     int64_t rl = right_range.GetLeft();
471     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
472         // With equal rl and lr left_range cannot be greater than right_range
473         if (rl == lr) {
474             return {BoundsRange(), BoundsRange()};
475         }
476         return {BoundsRange(rl + 1, lr), BoundsRange(rl, lr - 1)};
477     }
478     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE || cc == ConditionCode::CC_EQ) {
479         return {BoundsRange(rl, lr), BoundsRange(rl, lr)};
480     }
481     return ranges;
482 }
483 
NarrowBoundsCase2(ConditionCode cc,BoundsRange::RangePair const & ranges)484 BoundsRange::RangePair BoundsRange::NarrowBoundsCase2(ConditionCode cc, BoundsRange::RangePair const &ranges)
485 {
486     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_GE || cc == ConditionCode::CC_EQ ||
487         cc == ConditionCode::CC_A || cc == ConditionCode::CC_AE) {
488         return {BoundsRange(), BoundsRange()};
489     }
490     return ranges;
491 }
492 
NarrowBoundsCase3(ConditionCode cc,BoundsRange::RangePair const & ranges)493 BoundsRange::RangePair BoundsRange::NarrowBoundsCase3(ConditionCode cc, BoundsRange::RangePair const &ranges)
494 {
495     auto &[left_range, right_range] = ranges;
496     int64_t ll = left_range.GetLeft();
497     int64_t lr = left_range.GetRight();
498     int64_t rl = right_range.GetLeft();
499     int64_t rr = right_range.GetRight();
500     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
501         // rl == lr handled in case 1
502         return {BoundsRange(rl + 1, lr), right_range};
503     }
504     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE) {
505         return {BoundsRange(rl, lr), right_range};
506     }
507     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
508         // With equal ll and rr left_range cannot be less than right_range
509         if (ll == rr) {
510             return {BoundsRange(), BoundsRange()};
511         }
512         return {BoundsRange(ll, rr - 1), right_range};
513     }
514     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE) {
515         return {BoundsRange(ll, rr), right_range};
516     }
517     if (cc == ConditionCode::CC_EQ) {
518         return {BoundsRange(rl, rr), right_range};
519     }
520     return ranges;
521 }
522 
NarrowBoundsCase4(ConditionCode cc,BoundsRange::RangePair const & ranges)523 BoundsRange::RangePair BoundsRange::NarrowBoundsCase4(ConditionCode cc, BoundsRange::RangePair const &ranges)
524 {
525     auto &[left_range, right_range] = ranges;
526     int64_t ll = left_range.GetLeft();
527     int64_t rr = right_range.GetRight();
528     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
529         // With equal ll and rr left_range cannot be less than right_range
530         if (ll == rr) {
531             return {BoundsRange(), BoundsRange()};
532         }
533         return {BoundsRange(ll, rr - 1), BoundsRange(ll + 1, rr)};
534     }
535     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE || cc == ConditionCode::CC_EQ) {
536         return {BoundsRange(ll, rr), BoundsRange(ll, rr)};
537     }
538     return ranges;
539 }
540 
NarrowBoundsCase5(ConditionCode cc,BoundsRange::RangePair const & ranges)541 BoundsRange::RangePair BoundsRange::NarrowBoundsCase5(ConditionCode cc, BoundsRange::RangePair const &ranges)
542 {
543     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_LE || cc == ConditionCode::CC_EQ ||
544         cc == ConditionCode::CC_B || cc == ConditionCode::CC_BE) {
545         return {BoundsRange(), BoundsRange()};
546     }
547     return ranges;
548 }
549 
NarrowBoundsCase6(ConditionCode cc,BoundsRange::RangePair const & ranges)550 BoundsRange::RangePair BoundsRange::NarrowBoundsCase6(ConditionCode cc, BoundsRange::RangePair const &ranges)
551 {
552     auto &[left_range, right_range] = ranges;
553     int64_t ll = left_range.GetLeft();
554     int64_t lr = left_range.GetRight();
555     int64_t rl = right_range.GetLeft();
556     int64_t rr = right_range.GetRight();
557     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
558         // rl == lr handled in case 1
559         return {left_range, BoundsRange(rl, lr - 1)};
560     }
561     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE) {
562         return {left_range, BoundsRange(rl, lr)};
563     }
564     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
565         // ll == rr handled in case 4
566         return {left_range, BoundsRange(ll + 1, rr)};
567     }
568     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE) {
569         return {left_range, BoundsRange(ll, rr)};
570     }
571     if (cc == ConditionCode::CC_EQ) {
572         return {left_range, BoundsRange(ll, lr)};
573     }
574     return ranges;
575 }
576 
577 /**
578  * Try narrow bounds range for <if (left CC right)> situation
579  * Return a pair of narrowed left and right intervals
580  */
TryNarrowBoundsByCC(ConditionCode cc,BoundsRange::RangePair const & ranges)581 BoundsRange::RangePair BoundsRange::TryNarrowBoundsByCC(ConditionCode cc, BoundsRange::RangePair const &ranges)
582 {
583     if (cc == ConditionCode::CC_NE) {
584         return NarrowBoundsByNE(ranges);
585     }
586     auto &[left_range, right_range] = ranges;
587     int64_t ll = left_range.GetLeft();
588     int64_t lr = left_range.GetRight();
589     int64_t rl = right_range.GetLeft();
590     int64_t rr = right_range.GetRight();
591     // For further description () is for left_range bounds and [] is for right_range bounds
592     // case 1: ( [ ) ]
593     if (ll <= rl && rl <= lr && lr <= rr) {
594         return NarrowBoundsCase1(cc, ranges);
595     }
596     // case 2: ( ) [ ]
597     if (ll <= lr && lr < rl && rl <= rr) {
598         return NarrowBoundsCase2(cc, ranges);
599     }
600     // case 3: ( [ ] )
601     if (ll <= rl && rl <= rr && rr <= lr) {
602         return NarrowBoundsCase3(cc, ranges);
603     }
604     // case 4: [ ( ] )
605     if (rl <= ll && ll <= rr && rr <= lr) {
606         return NarrowBoundsCase4(cc, ranges);
607     }
608     // case 5: [ ] ( )
609     if (rl <= rr && rr < ll && ll <= lr) {
610         return NarrowBoundsCase5(cc, ranges);
611     }
612     // case 6: [ ( ) ]
613     if (rl <= ll && ll <= lr && lr <= rr) {
614         return NarrowBoundsCase6(cc, ranges);
615     }
616     return ranges;
617 }
618 
619 /// Return (left + right) or if overflows or underflows return nullopt of range type.
AddWithOverflowCheck(int64_t left,int64_t right)620 std::optional<int64_t> BoundsRange::AddWithOverflowCheck(int64_t left, int64_t right)
621 {
622     if (right == 0) {
623         return left;
624     }
625     if (right > 0) {
626         if (left <= (MAX_RANGE_VALUE - right)) {
627             // No overflow.
628             return left + right;
629         }
630         return std::nullopt;
631     }
632     if (left >= (MIN_RANGE_VALUE - right)) {
633         // No overflow.
634         return left + right;
635     }
636     return std::nullopt;
637 }
638 
AddWithOverflowCheck(uint64_t left,uint64_t right)639 std::optional<uint64_t> BoundsRange::AddWithOverflowCheck(uint64_t left, uint64_t right)
640 {
641     if (right == 0) {
642         return left;
643     }
644     if (left <= (UINT64_MAX - right)) {
645         // No overflow.
646         return left + right;
647     }
648     return std::nullopt;
649 }
650 
651 /// Return (left * right) or if overflows or underflows return nullopt of range type.
MulWithOverflowCheck(int64_t left,int64_t right)652 std::optional<int64_t> BoundsRange::MulWithOverflowCheck(int64_t left, int64_t right)
653 {
654     if (left == 0 || right == 0) {
655         return 0;
656     }
657     int64_t leftAbs = (left == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(left));
658     int64_t rightAbs = (right == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(right));
659     if (leftAbs <= (MAX_RANGE_VALUE / rightAbs)) {
660         // No overflow.
661         return left * right;
662     }
663     if ((right > 0 && left > 0) || (right < 0 && left < 0)) {
664         return std::nullopt;
665     }
666     return std::nullopt;
667 }
668 
MulWithOverflowCheck(uint64_t left,uint64_t right)669 std::optional<uint64_t> BoundsRange::MulWithOverflowCheck(uint64_t left, uint64_t right)
670 {
671     if (left == 0 || right == 0) {
672         return 0;
673     }
674     if (left <= (UINT64_MAX / right)) {
675         // No overflow.
676         return left * right;
677     }
678     return std::nullopt;
679 }
680 
681 /// Return (left / right) or nullopt VALUE for MIN_RANGE_VALUE / -1.
DivWithOverflowCheck(int64_t left,int64_t right)682 std::optional<int64_t> BoundsRange::DivWithOverflowCheck(int64_t left, int64_t right)
683 {
684     ASSERT(right != 0);
685     if (left == MIN_RANGE_VALUE && right == -1) {
686         return std::nullopt;
687     }
688     return left / right;
689 }
690 
FindBoundsRange(const BasicBlock * block,const Inst * inst) const691 BoundsRange BoundsRangeInfo::FindBoundsRange(const BasicBlock *block, const Inst *inst) const
692 {
693     ASSERT(block != nullptr && inst != nullptr);
694     ASSERT(!IsFloatType(inst->GetType()));
695     ASSERT(inst->GetType() == DataType::REFERENCE || DataType::GetCommonType(inst->GetType()) == DataType::INT64);
696     if (inst->GetOpcode() == Opcode::NullPtr) {
697         ASSERT(inst->GetType() == DataType::REFERENCE);
698         return BoundsRange(0);
699     }
700     if (IsInstNotNull(inst)) {
701         ASSERT(inst->GetType() == DataType::REFERENCE);
702         return BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
703     }
704     while (block != nullptr) {
705         if (boundsRangeInfo_.find(block) != boundsRangeInfo_.end() &&
706             boundsRangeInfo_.at(block).find(inst) != boundsRangeInfo_.at(block).end()) {
707             return boundsRangeInfo_.at(block).at(inst);
708         }
709         block = block->GetDominator();
710     }
711     // BoundsRange for constant can have len_array, so we should process it after the loop above
712     if (inst->IsConst()) {
713         ASSERT(inst->GetType() == DataType::INT64);
714         auto val = static_cast<int64_t>(inst->CastToConstant()->GetIntValue());
715         return BoundsRange(val);
716     }
717     if (IsLenArray(inst)) {
718         ASSERT(inst->GetType() == DataType::INT32);
719         auto maxLength = INT32_MAX;
720         if (inst->GetOpcode() == Opcode::LenArray) {
721             auto arrayInst = inst->CastToLenArray()->GetDataFlowInput(0);
722             auto typeInfo = arrayInst->GetObjectTypeInfo();
723             if (typeInfo) {
724                 auto klass = typeInfo.GetClass();
725                 auto runtime = inst->GetBasicBlock()->GetGraph()->GetRuntime();
726                 maxLength = static_cast<int32_t>(runtime->GetMaxArrayLength(klass));
727             }
728         }
729         return BoundsRange(0, maxLength, nullptr, inst->GetType());
730     }
731     // if we know nothing about inst return the complete range of type
732     return BoundsRange(inst->GetType());
733 }
734 
SetBoundsRange(const BasicBlock * block,const Inst * inst,BoundsRange range)735 void BoundsRangeInfo::SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range)
736 {
737     if (inst->IsConst() && range.GetLenArray() == nullptr) {
738         return;
739     }
740     if (inst->IsConst()) {
741         auto val = static_cast<int64_t>(static_cast<const ConstantInst *>(inst)->GetIntValue());
742         range = BoundsRange(val, val, range.GetLenArray());
743     }
744     ASSERT(inst->GetType() == DataType::REFERENCE || DataType::GetCommonType(inst->GetType()) == DataType::INT64);
745     ASSERT(range.GetLeft() >= BoundsRange::GetMin(inst->GetType()));
746     ASSERT(range.GetRight() <= BoundsRange::GetMax(inst->GetType()));
747     if (!range.IsMaxRange() || range.GetLenArray() != nullptr || range.HasActualLengthLoop()) {
748         if (boundsRangeInfo_.find(block) == boundsRangeInfo_.end()) {
749             auto it1 = boundsRangeInfo_.emplace(block, aa_.Adapter());
750             ASSERT(it1.second);
751             it1.first->second.emplace(inst, range);
752         } else if (boundsRangeInfo_.at(block).find(inst) == boundsRangeInfo_.at(block).end()) {
753             boundsRangeInfo_.at(block).emplace(inst, range);
754         } else {
755             if (boundsRangeInfo_.at(block).at(inst).HasActualLengthLoop() && !range.HasActualLengthLoop()) {
756                 range.SetActualLengthLoop(boundsRangeInfo_.at(block).at(inst).GetActualLengthLoop());
757             }
758             boundsRangeInfo_.at(block).at(inst) = range;
759         }
760     }
761 }
762 
BoundsAnalysis(Graph * graph)763 BoundsAnalysis::BoundsAnalysis(Graph *graph)
764     : Analysis(graph), boundsRangeInfo_(graph->GetAllocator()), loopsInfoTable_(graph->GetAllocator()->Adapter())
765 {
766 }
767 
RunImpl()768 bool BoundsAnalysis::RunImpl()
769 {
770     MarkerHolder holder {GetGraph()};
771     visited_ = holder.GetMarker();
772     ASSERT(!GetGraph()->IsBytecodeOptimizer());
773     boundsRangeInfo_.Clear();
774     loopsInfoTable_.clear();
775 
776     GetGraph()->RunPass<DominatorsTree>();
777     GetGraph()->RunPass<LoopAnalyzer>();
778 
779     VisitGraph();
780 
781     return true;
782 }
783 
IsInstNotNull(const Inst * inst,BasicBlock * block)784 bool BoundsAnalysis::IsInstNotNull(const Inst *inst, BasicBlock *block)
785 {
786     if (compiler::IsInstNotNull(inst)) {
787         return true;
788     }
789     auto bri = block->GetGraph()->GetBoundsRangeInfo();
790     auto range = bri->FindBoundsRange(block, inst);
791     return range.IsMore(BoundsRange(0));
792 }
793 
GetBlocksToVisit() const794 const ArenaVector<BasicBlock *> &BoundsAnalysis::GetBlocksToVisit() const
795 {
796     return GetGraph()->GetBlocksRPO();
797 }
798 
VisitNeg(GraphVisitor * v,Inst * inst)799 void BoundsAnalysis::VisitNeg(GraphVisitor *v, Inst *inst)
800 {
801     CalcNewBoundsRangeUnary<Opcode::Neg>(v, inst);
802 }
803 
VisitNegOverflowAndZeroCheck(GraphVisitor * v,Inst * inst)804 void BoundsAnalysis::VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst)
805 {
806     CalcNewBoundsRangeUnary<Opcode::Neg>(v, inst);
807 }
808 
VisitAbs(GraphVisitor * v,Inst * inst)809 void BoundsAnalysis::VisitAbs(GraphVisitor *v, Inst *inst)
810 {
811     CalcNewBoundsRangeUnary<Opcode::Abs>(v, inst);
812 }
813 
VisitAdd(GraphVisitor * v,Inst * inst)814 void BoundsAnalysis::VisitAdd(GraphVisitor *v, Inst *inst)
815 {
816     CalcNewBoundsRangeBinary<Opcode::Add>(v, inst);
817 }
818 
VisitAddOverflowCheck(GraphVisitor * v,Inst * inst)819 void BoundsAnalysis::VisitAddOverflowCheck(GraphVisitor *v, Inst *inst)
820 {
821     CalcNewBoundsRangeBinary<Opcode::Add>(v, inst);
822 }
823 
VisitSub(GraphVisitor * v,Inst * inst)824 void BoundsAnalysis::VisitSub(GraphVisitor *v, Inst *inst)
825 {
826     CalcNewBoundsRangeBinary<Opcode::Sub>(v, inst);
827 }
828 
VisitSubOverflowCheck(GraphVisitor * v,Inst * inst)829 void BoundsAnalysis::VisitSubOverflowCheck(GraphVisitor *v, Inst *inst)
830 {
831     CalcNewBoundsRangeBinary<Opcode::Sub>(v, inst);
832 }
833 
VisitMod(GraphVisitor * v,Inst * inst)834 void BoundsAnalysis::VisitMod(GraphVisitor *v, Inst *inst)
835 {
836     CalcNewBoundsRangeBinary<Opcode::Mod>(v, inst);
837 }
838 
VisitDiv(GraphVisitor * v,Inst * inst)839 void BoundsAnalysis::VisitDiv(GraphVisitor *v, Inst *inst)
840 {
841     CalcNewBoundsRangeBinary<Opcode::Div>(v, inst);
842 }
843 
VisitMul(GraphVisitor * v,Inst * inst)844 void BoundsAnalysis::VisitMul(GraphVisitor *v, Inst *inst)
845 {
846     CalcNewBoundsRangeBinary<Opcode::Mul>(v, inst);
847 }
848 
VisitAnd(GraphVisitor * v,Inst * inst)849 void BoundsAnalysis::VisitAnd(GraphVisitor *v, Inst *inst)
850 {
851     CalcNewBoundsRangeBinary<Opcode::And>(v, inst);
852 }
853 
VisitShr(GraphVisitor * v,Inst * inst)854 void BoundsAnalysis::VisitShr(GraphVisitor *v, Inst *inst)
855 {
856     CalcNewBoundsRangeBinary<Opcode::Shr>(v, inst);
857 }
858 
VisitAShr(GraphVisitor * v,Inst * inst)859 void BoundsAnalysis::VisitAShr(GraphVisitor *v, Inst *inst)
860 {
861     CalcNewBoundsRangeBinary<Opcode::AShr>(v, inst);
862 }
863 
VisitShl(GraphVisitor * v,Inst * inst)864 void BoundsAnalysis::VisitShl(GraphVisitor *v, Inst *inst)
865 {
866     CalcNewBoundsRangeBinary<Opcode::Shl>(v, inst);
867 }
868 
VisitIfImm(GraphVisitor * v,Inst * inst)869 void BoundsAnalysis::VisitIfImm(GraphVisitor *v, Inst *inst)
870 {
871     auto ifInst = inst->CastToIfImm();
872     if (ifInst->GetOperandsType() != DataType::BOOL) {
873         return;
874     }
875     ASSERT(ifInst->GetCc() == ConditionCode::CC_NE || ifInst->GetCc() == ConditionCode::CC_EQ);
876     ASSERT(ifInst->GetImm() == 0);
877 
878     auto input = inst->GetInput(0).GetInst();
879     if (input->GetOpcode() == Opcode::IsInstance) {
880         CalcNewBoundsRangeForIsInstanceInput(v, input->CastToIsInstance(), ifInst);
881         return;
882     }
883     if (input->GetOpcode() != Opcode::Compare) {
884         return;
885     }
886     auto compare = input->CastToCompare();
887     auto op0 = compare->GetInput(0).GetInst();
888     auto op1 = compare->GetInput(1).GetInst();
889     if ((DataType::GetCommonType(op0->GetType()) != DataType::INT64 && op0->GetType() != DataType::REFERENCE) ||
890         (DataType::GetCommonType(op1->GetType()) != DataType::INT64 && op1->GetType() != DataType::REFERENCE)) {
891         return;
892     }
893 
894     auto cc = compare->GetCc();
895     auto block = inst->GetBasicBlock();
896     BasicBlock *trueBlock;
897     BasicBlock *falseBlock;
898     if (ifInst->GetCc() == ConditionCode::CC_NE) {
899         // Corresponds to Compare result
900         trueBlock = block->GetTrueSuccessor();
901         falseBlock = block->GetFalseSuccessor();
902     } else if (ifInst->GetCc() == ConditionCode::CC_EQ) {
903         // Corresponds to inversion of Compare result
904         trueBlock = block->GetFalseSuccessor();
905         falseBlock = block->GetTrueSuccessor();
906     } else {
907         UNREACHABLE();
908     }
909     CalcNewBoundsRangeForCompare(v, block, cc, {op0, op1}, trueBlock);
910     CalcNewBoundsRangeForCompare(v, block, GetInverseConditionCode(cc), {op0, op1}, falseBlock);
911 }
912 
VisitPhi(GraphVisitor * v,Inst * inst)913 void BoundsAnalysis::VisitPhi(GraphVisitor *v, Inst *inst)
914 {
915     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::ANY || inst->GetType() == DataType::POINTER) {
916         return;
917     }
918     auto boundsAnalysis = static_cast<BoundsAnalysis *>(v);
919     auto bri = boundsAnalysis->GetBoundsRangeInfo();
920     auto phi = inst->CastToPhi();
921     auto setPhiArrayIndexRange = [&bri](Inst *phiInst) {
922         Loop *loop = phiInst->GetBasicBlock()->GetLoop();
923         if (loop->IsRoot()) {
924             return;
925         }
926         if (loop->GetArrayIndexVariable() != phiInst) {
927             return;
928         }
929         if (loop->GetHeader() != phiInst->GetBasicBlock()) {
930             return;
931         }
932         auto loopBodyBlock = phiInst->GetBasicBlock()->GetFalseSuccessor();
933         auto range = bri->FindBoundsRange(loopBodyBlock, phiInst);
934         range.SetRange(0, BoundsRange::ACTUAL_LENGTH_VALUE - 1);
935         range.SetActualLengthLoop(loop);
936         bri->SetBoundsRange(loopBodyBlock, phiInst, range);
937     };
938     // for phi in a countable loop
939     if (inst->GetType() != DataType::REFERENCE && boundsAnalysis->ProcessCountableLoop(phi, bri)) {
940         setPhiArrayIndexRange(inst);
941         return;
942     }
943     // for other phis
944     MergePhiPredecessors(phi, bri);
945     setPhiArrayIndexRange(inst);
946 }
947 
948 template <bool CHECK_TYPE>
MergePhiPredecessors(PhiInst * phi,BoundsRangeInfo * bri)949 bool BoundsAnalysis::MergePhiPredecessors(PhiInst *phi, BoundsRangeInfo *bri)
950 {
951     auto phiBlock = phi->GetBasicBlock();
952     ArenaVector<BoundsRange> ranges(phiBlock->GetGraph()->GetLocalAllocator()->Adapter());
953     for (auto *block : phiBlock->GetPredsBlocks()) {
954         auto *inst = phi->GetPhiInput(block);
955         if constexpr (CHECK_TYPE) {
956             if (inst->GetInputs().size() <= 1) {
957                 return false;
958             }
959             auto loop = phi->GetBasicBlock()->GetLoop();
960             auto input0 = inst->GetInput(0).GetInst();
961             auto loop0 = input0->GetBasicBlock()->GetLoop();
962             auto input1 = inst->GetInput(1).GetInst();
963             auto loop1 = input1->GetBasicBlock()->GetLoop();
964             if (!(inst->IsAddSub() && (input0->IsPhi() || input1->IsPhi()) &&
965                   (!loop0->IsInside(loop) || !loop1->IsInside(loop))) &&
966                 !inst->IsPhi()) {
967                 // NOTE: support Mul-Div and maybe more cases
968                 return false;
969             }
970         }
971         ranges.emplace_back(bri->FindBoundsRange(block, inst));
972     }
973     bri->SetBoundsRange(phiBlock, phi, BoundsRange::Union(ranges).FitInType(phi->GetType()));
974     return true;
975 }
976 
VisitNullCheck(GraphVisitor * v,Inst * inst)977 void BoundsAnalysis::VisitNullCheck(GraphVisitor *v, Inst *inst)
978 {
979     ProcessNullCheck(v, inst, inst->GetDataFlowInput(0));
980 }
981 
GetNestedLoopIterations(Loop * loop,CountableLoopInfo & loopInfo)982 std::optional<uint64_t> BoundsAnalysis::GetNestedLoopIterations(Loop *loop, CountableLoopInfo &loopInfo)
983 {
984     auto iterations = CountableLoopParser::GetLoopIterations(loopInfo);
985     if (!iterations.has_value()) {
986         return std::nullopt;
987     }
988     auto iterationsValue = iterations.value();
989     auto *outer = loop->GetOuterLoop();
990     if (outer->IsRoot()) {
991         return iterationsValue;
992     }
993     auto it = loopsInfoTable_.find(loop->GetOuterLoop());
994     if (it == loopsInfoTable_.end()) {
995         return std::nullopt;
996     }
997     auto outerLoopInfo = (*it).second;
998     if (!outerLoopInfo.has_value()) {
999         return std::nullopt;
1000     }
1001     auto outerIters = outerLoopInfo.value().second;
1002     if (outerIters == std::numeric_limits<uint64_t>::max()) {
1003         return outerIters;
1004     }
1005     return BoundsRange::MulWithOverflowCheck(iterationsValue, outerIters);
1006 }
1007 
GetSimpleLoopIterationsInfo(Loop * loop)1008 std::optional<LoopIterationsInfo> BoundsAnalysis::GetSimpleLoopIterationsInfo(Loop *loop)
1009 {
1010     auto loopParser = CountableLoopParser(*loop);
1011     auto loopInfo = loopParser.Parse();
1012     if (!loopInfo.has_value()) {
1013         // Loop is not countable
1014         loopsInfoTable_.emplace(std::make_pair(loop, std::nullopt));
1015         return std::nullopt;
1016     }
1017     auto loopInfoValue = loopInfo.value();
1018     // Generally speaking, countable loop can have compile-time unknown number of iterations,
1019     // i.e. when its init instruction is not a constant
1020     // In this case it is possible to get the index phi range, but not for other phis
1021     auto iterations = GetNestedLoopIterations(loop, loopInfoValue);
1022     auto iterationsValue = std::numeric_limits<uint64_t>::max();
1023     if (iterations.has_value()) {
1024         iterationsValue = iterations.value();
1025     }
1026     auto loopIterInfo = std::make_pair(loopInfoValue, iterationsValue);
1027     loopsInfoTable_.emplace(std::make_pair(loop, loopIterInfo));
1028     return loopIterInfo;
1029 }
1030 
GetNestedLoopIterationsInfo(Loop * loop)1031 std::optional<LoopIterationsInfo> BoundsAnalysis::GetNestedLoopIterationsInfo(Loop *loop)
1032 {
1033     auto it = loopsInfoTable_.find(loop);
1034     if (it == loopsInfoTable_.end()) {
1035         auto loopIterInfo = GetSimpleLoopIterationsInfo(loop);
1036         // If loop is visited first time - parse loop and fill the table
1037         for (auto *innerLoop : loop->GetInnerLoops()) {
1038             // If some of inner loops is not countable - we cannot process phis, except index
1039             if (!GetSimpleLoopIterationsInfo(innerLoop).has_value()) {
1040                 return std::nullopt;
1041             }
1042         }
1043         return loopIterInfo;
1044     }
1045     auto loopIterInfo = (*it).second;
1046     if (!loopIterInfo.has_value()) {
1047         // Loop has been visited and it is not countable
1048         return std::nullopt;
1049     }
1050     return loopIterInfo.value();
1051 }
1052 
ProcessCountableLoop(PhiInst * phi,BoundsRangeInfo * bri)1053 bool BoundsAnalysis::ProcessCountableLoop(PhiInst *phi, BoundsRangeInfo *bri)
1054 {
1055     auto *phiBlock = phi->GetBasicBlock();
1056     auto *loop = phiBlock->GetLoop();
1057     auto loopIterInfo = GetNestedLoopIterationsInfo(loop);
1058     if (!loopIterInfo.has_value()) {
1059         // loop is not countable
1060         return false;
1061     }
1062     [[maybe_unused]] auto [loopInfo, iterations] = loopIterInfo.value();
1063     if (phi == loopInfo.index) {
1064         // Index phi was processed while parsing the loop
1065         return loopsRevisiting_ ? true : ProcessIndexPhi(loop, bri, loopInfo);
1066     }
1067     if (iterations != std::numeric_limits<uint64_t>::max()) {
1068         if (phiBlock == loop->GetHeader()) {
1069             // At the beginning assign init phi a value range from its input
1070             return ProcessInitPhi(phi, bri);
1071         } else {  // NOLINT(readability-else-after-return)
1072             // For update phi merge predecessors and propagate bounds info to a loop
1073             return ProcessUpdatePhi(phi, bri, iterations);
1074         }
1075     }
1076     return false;
1077 }
1078 
1079 // "static" keyword for internal linkage
MoveRangeAccordingCC(ConditionCode cc,BoundsRange & lowerRange,BoundsRange & upperRange,const Inst * upper)1080 static void MoveRangeAccordingCC(ConditionCode cc, BoundsRange &lowerRange, BoundsRange &upperRange, const Inst *upper)
1081 {
1082     if (cc == CC_GT) {
1083         lowerRange = lowerRange.Add(BoundsRange(1));
1084     } else if (cc == CC_LT) {
1085         upperRange = upperRange.Sub(BoundsRange(1));
1086         if (IsLenArray(upper)) {
1087             upperRange.SetLenArray(upper);
1088         }
1089     }
1090 }
1091 
ProcessIndexPhi(Loop * loop,BoundsRangeInfo * bri,CountableLoopInfo & loopInfoValue)1092 bool BoundsAnalysis::ProcessIndexPhi(Loop *loop, BoundsRangeInfo *bri, CountableLoopInfo &loopInfoValue)
1093 {
1094     auto *indexPhi = loopInfoValue.index;
1095     auto *phiBlock = indexPhi->GetBasicBlock();
1096     ASSERT(loopInfoValue.update->IsAddSub());
1097     auto *lower = loopInfoValue.init;
1098     auto *upper = loopInfoValue.test;
1099     auto cc = loopInfoValue.normalizedCc;
1100     ASSERT(cc == CC_LE || cc == CC_LT || cc == CC_GE || cc == CC_GT);
1101     if (!loopInfoValue.isInc) {
1102         lower = loopInfoValue.test;
1103         upper = loopInfoValue.init;
1104     }
1105     auto lowerRange = bri->FindBoundsRange(phiBlock, lower);
1106     auto upperRange = bri->FindBoundsRange(phiBlock, upper);
1107     MoveRangeAccordingCC(cc, lowerRange, upperRange, upper);
1108     if (lowerRange.GetLeft() > upperRange.GetRight()) {
1109         return false;
1110     }
1111     auto phiType = indexPhi->GetType();
1112     auto left = lowerRange.GetLeft();
1113     auto right = upperRange.GetRight();
1114     auto lenArray = upperRange.GetLenArray();
1115     auto isHeadLoopExit = loopInfoValue.ifImm->GetBasicBlock() == loop->GetHeader();
1116     if (!upperRange.IsMoreOrEqual(lowerRange) && !isHeadLoopExit) {
1117         return false;
1118     }
1119     if (!upperRange.IsMoreOrEqual(lowerRange) && !CountableLoopParser::HasPreHeaderCompare(loop, loopInfoValue)) {
1120         ASSERT(phiBlock == loop->GetHeader());
1121         if (loopInfoValue.ifImm->GetBasicBlock() == phiBlock) {
1122             auto nextLoopBlock = phiBlock->GetTrueSuccessor();
1123             if (nextLoopBlock->GetLoop() != loop && !nextLoopBlock->GetLoop()->IsInside(loop)) {
1124                 nextLoopBlock = phiBlock->GetFalseSuccessor();
1125                 ASSERT(nextLoopBlock->GetLoop() == loop || nextLoopBlock->GetLoop()->IsInside(loop));
1126             }
1127             if (nextLoopBlock != phiBlock) {
1128                 auto range = BoundsRange(left, right, lenArray);
1129                 bri->SetBoundsRange(nextLoopBlock, indexPhi, range.FitInType(phiType));
1130             }
1131         }
1132         // index can be more (less) than loop bound on first iteration
1133         if (cc == CC_LE || cc == CC_LT) {
1134             right = std::max(right, lowerRange.GetRight());
1135             lenArray = nullptr;
1136         } else {
1137             left = std::min(left, upperRange.GetLeft());
1138         }
1139     }
1140     auto range = BoundsRange(left, right, lenArray);
1141     bri->SetBoundsRange(phiBlock, indexPhi, range.FitInType(phiType));
1142     return true;
1143 }
1144 
ProcessInitPhi(PhiInst * initPhi,BoundsRangeInfo * bri)1145 bool BoundsAnalysis::ProcessInitPhi(PhiInst *initPhi, BoundsRangeInfo *bri)
1146 {
1147     auto *phiBlock = initPhi->GetBasicBlock();
1148     auto *curLoop = phiBlock->GetLoop();
1149     auto inputs = initPhi->GetInputs();
1150 
1151     // Find an init instruction, coming inside of the current loop
1152     auto *initInst = inputs[0].GetInst();
1153     auto *updateInst = inputs[1].GetInst();
1154     if (curLoop->IsInside(updateInst->GetBasicBlock()->GetLoop())) {
1155         std::swap(initInst, updateInst);
1156     }
1157 
1158     if (!loopsRevisiting_) {
1159         if (!updateInst->IsPhi()) {
1160             // For cases, when an init phi has no corresponding update phi
1161             return false;
1162         }
1163         auto initRange = bri->FindBoundsRange(initInst->GetBasicBlock(), initInst);
1164         bri->SetBoundsRange(phiBlock, initPhi, initRange.FitInType(initPhi->GetType()));
1165         return true;
1166     }
1167 
1168     // Else init phi range is the union range
1169     // (which is [min(init.left, update.left), max(init.right, update.right)])
1170     if (!updateInst->IsMarked(visited_)) {
1171         // If corresponding update phi was not processed yet
1172         return true;
1173     }
1174     auto *lenArray = bri->FindBoundsRange(initPhi->GetBasicBlock(), initPhi).GetLenArray();
1175     MergePhiPredecessors<false>(initPhi, bri);
1176     if (lenArray != nullptr) {
1177         bri->FindBoundsRange(initPhi->GetBasicBlock(), initPhi).SetLenArray(lenArray);
1178     }
1179     return true;
1180 }
1181 
ProcessUpdatePhi(PhiInst * updatePhi,BoundsRangeInfo * bri,uint64_t iterations)1182 bool BoundsAnalysis::ProcessUpdatePhi(PhiInst *updatePhi, BoundsRangeInfo *bri, uint64_t iterations)
1183 {
1184     auto *updatePhiBlock = updatePhi->GetBasicBlock();
1185     auto *loop = updatePhiBlock->GetLoop();
1186     auto *header = loop->GetHeader();
1187 
1188     // Find corresponding init phi
1189     auto *initPhi = TryFindCorrespondingInitPhi(updatePhi, header);
1190     if (initPhi == nullptr) {
1191         // For the case, when an update phi has no init phi prototype in the header
1192         // (i.e. some local loop variable control flow)
1193         // it is not required to reprocess the loop
1194         return true;
1195     }
1196 
1197     // Unite inputs' bounds range info
1198     if (!MergePhiPredecessors<true>(updatePhi, bri)) {
1199         // Cannot count update phi range => need to invalidate init phi range
1200         // Set maximal possible range and revisit loop to invalidate dependent ranges
1201         bri->SetBoundsRange(header, initPhi, BoundsRange(initPhi->GetType()));
1202         VisitLoop(header, updatePhiBlock);
1203         return false;
1204     }
1205 
1206     // While revisiting, we just merge predecessors, because they can be changed
1207     if (loopsRevisiting_) {
1208         return true;
1209     }
1210 
1211     auto initRange = bri->FindBoundsRange(header, initPhi);
1212     auto updateRange = bri->FindBoundsRange(updatePhiBlock, updatePhi);
1213     auto iterRange = BoundsRange(iterations);
1214 
1215     // Update phi range is changing by adding a range difference multiplied by iterations number
1216     auto diffRange = updateRange.Diff(initRange);
1217     auto updateNewRange = initRange.Add(diffRange.Mul(iterRange));
1218     bri->SetBoundsRange(updatePhiBlock, updatePhi, updateNewRange.FitInType(updatePhi->GetType()));
1219     updatePhi->SetMarker(visited_);
1220 
1221     // Propagate init phi bounds info to a loop
1222     VisitLoop(header, updatePhiBlock);
1223     return true;
1224 }
1225 
TryFindCorrespondingInitPhi(PhiInst * updatePhi,BasicBlock * header)1226 Inst *BoundsAnalysis::TryFindCorrespondingInitPhi(PhiInst *updatePhi, BasicBlock *header)
1227 {
1228     for (auto &user : updatePhi->GetUsers()) {
1229         if (user.GetInst()->GetBasicBlock() != header) {
1230             continue;
1231         }
1232         auto initPhi = user.GetInst();
1233         ASSERT(initPhi->IsPhi());
1234         return initPhi;
1235     }
1236     return nullptr;
1237 }
1238 
VisitLoop(BasicBlock * header,BasicBlock * updatePhiBlock)1239 void BoundsAnalysis::VisitLoop(BasicBlock *header, BasicBlock *updatePhiBlock)
1240 {
1241     auto &rpo = GetGraph()->GetBlocksRPO();
1242     auto *curLoop = header->GetLoop();
1243     auto startIt = std::find(rpo.begin(), rpo.end(), header);
1244     auto endIt = std::find(rpo.begin(), rpo.end(), updatePhiBlock);
1245     loopsRevisiting_ = true;  // To avoid complex recalculations and not to loop the algorithm
1246 
1247     // First part: revisit current loop and its inner loops, which have been visited before
1248     for (auto it = startIt; it != endIt; ++it) {
1249         auto *block = *it;
1250         // Process loop and its nested loops only
1251         if (block->GetLoop() != curLoop && !block->GetLoop()->IsInside(curLoop)) {
1252             continue;
1253         }
1254         for (auto *inst : block->AllInsts()) {
1255             TABLE[static_cast<unsigned>(inst->GetOpcode())](this, inst);
1256         }
1257     }
1258 
1259     // Second part: revisit outer loops, going out of nest
1260     curLoop = curLoop->GetOuterLoop();
1261     auto *innerHeader = header;
1262     while (!curLoop->IsRoot()) {
1263         auto *curHeader = curLoop->GetHeader();
1264         startIt = std::find(rpo.begin(), rpo.end(), curHeader);
1265         endIt = std::find(rpo.begin(), rpo.end(), innerHeader);
1266         for (auto it = startIt; it != endIt; ++it) {
1267             auto *block = *it;
1268             // Process this loop only
1269             if (block->GetLoop() != curLoop) {
1270                 continue;
1271             }
1272             for (auto *inst : block->AllInsts()) {
1273                 TABLE[static_cast<unsigned>(inst->GetOpcode())](this, inst);
1274             }
1275         }
1276         curLoop = curLoop->GetOuterLoop();
1277         innerHeader = curHeader;
1278     }
1279 
1280     loopsRevisiting_ = false;
1281 }
1282 
CheckTriangleCase(const BasicBlock * block,const BasicBlock * tgtBlock)1283 bool BoundsAnalysis::CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgtBlock)
1284 {
1285     auto &predsBlocks = tgtBlock->GetPredsBlocks();
1286     auto loop = tgtBlock->GetLoop();
1287     auto &backEdges = loop->GetBackEdges();
1288     if (predsBlocks.size() == 1) {
1289         return true;
1290     }
1291     if (!loop->IsRoot() && backEdges.size() == 1 && predsBlocks.size() == 2U) {
1292         if (predsBlocks[0] == block && predsBlocks[1] == backEdges[0]) {
1293             return true;
1294         }
1295         if (predsBlocks[1] == block && predsBlocks[0] == backEdges[0]) {
1296             return true;
1297         }
1298         return false;
1299     }
1300     return false;
1301 }
1302 
ProcessNullCheck(GraphVisitor * v,const Inst * checkInst,const Inst * refInput)1303 void BoundsAnalysis::ProcessNullCheck(GraphVisitor *v, const Inst *checkInst, const Inst *refInput)
1304 {
1305     ASSERT(checkInst->IsNullCheck() || checkInst->GetOpcode() == Opcode::DeoptimizeIf);
1306     ASSERT(refInput->GetType() == DataType::REFERENCE);
1307     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1308     auto block = checkInst->GetBasicBlock();
1309     auto range = BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
1310     for (auto domBlock : block->GetDominatedBlocks()) {
1311         bri->SetBoundsRange(domBlock, refInput, range);
1312     }
1313 }
1314 
VisitBoundsCheck(GraphVisitor * v,Inst * inst)1315 void BoundsAnalysis::VisitBoundsCheck(GraphVisitor *v, Inst *inst)
1316 {
1317     Loop *thisLoop = inst->GetBasicBlock()->GetLoop();
1318     if (thisLoop->IsRoot()) {
1319         return;
1320     }
1321     Inst *lenArrayInst = inst->GetInput(0).GetInst();
1322     auto opcode = lenArrayInst->GetOpcode();
1323     if (opcode != Opcode::LenArray && opcode != Opcode::LoadObject) {
1324         return;
1325     }
1326     auto boundsAnalysis = static_cast<BoundsAnalysis *>(v);
1327     auto bri = boundsAnalysis->GetBoundsRangeInfo();
1328     auto indexRange = bri->FindBoundsRange(inst->GetBasicBlock(), inst->GetInput(1).GetInst());
1329     Loop *actualLengthLoop = indexRange.GetActualLengthLoop();
1330     // Within actualLengthLoop and its inner loops, the bounds range can be propagated.
1331     if (actualLengthLoop == nullptr || (thisLoop != actualLengthLoop && !thisLoop->IsInside(actualLengthLoop))) {
1332         return;
1333     }
1334     Inst *arrayOriginRef = actualLengthLoop->GetArrayOriginRef();
1335     if (opcode == Opcode::LenArray &&
1336         !CheckArrayField(RuntimeInterface::ArrayField::BUFFER, lenArrayInst, arrayOriginRef)) {
1337         return;
1338     }
1339     if (opcode == Opcode::LoadObject &&
1340         !CheckArrayField(RuntimeInterface::ArrayField::ACTUAL_LENGTH, lenArrayInst, arrayOriginRef)) {
1341         return;
1342     }
1343     auto saveState = inst->GetSaveState();
1344     ASSERT(saveState != nullptr);
1345     auto callerInst = saveState->GetCallerInst();
1346     auto runtime = inst->GetBasicBlock()->GetGraph()->GetRuntime();
1347     RuntimeInterface::MethodPtr method = nullptr;
1348     if (callerInst != nullptr) {
1349         method = callerInst->GetCallMethod();
1350     } else {
1351         method = inst->GetBasicBlock()->GetGraph()->GetMethod();
1352     }
1353     // only support bounds check opt for array methods
1354     if (!runtime->IsClassEscompatArray(runtime->GetClass(method))) {
1355         indexRange = BoundsRange(inst->GetInput(1).GetInst()->GetType());
1356         bri->SetBoundsRange(inst->GetBasicBlock(), inst->GetInput(1).GetInst(), indexRange);
1357     }
1358     bri->SetBoundsRange(inst->GetBasicBlock(), inst, indexRange);
1359 }
1360 
VisitLoadObject(GraphVisitor * v,Inst * inst)1361 void BoundsAnalysis::VisitLoadObject(GraphVisitor *v, Inst *inst)
1362 {
1363     Inst *arrayOriginRef = nullptr;
1364     if (CheckArrayField(RuntimeInterface::ArrayField::ACTUAL_LENGTH, inst, arrayOriginRef)) {
1365         auto boundsAnalysis = static_cast<BoundsAnalysis *>(v);
1366         auto bri = boundsAnalysis->GetBoundsRangeInfo();
1367         auto range = BoundsRange(BoundsRange::ACTUAL_LENGTH_VALUE);
1368         bri->SetBoundsRange(inst->GetBasicBlock(), inst, range);
1369     }
1370 }
1371 
CalcNewBoundsRangeForIsInstanceInput(GraphVisitor * v,IsInstanceInst * isInstance,IfImmInst * ifImm)1372 void BoundsAnalysis::CalcNewBoundsRangeForIsInstanceInput(GraphVisitor *v, IsInstanceInst *isInstance, IfImmInst *ifImm)
1373 {
1374     ASSERT(isInstance == ifImm->GetInput(0).GetInst());
1375     auto block = ifImm->GetBasicBlock();
1376     auto trueBlock = ifImm->GetEdgeIfInputTrue();
1377     if (CheckTriangleCase(block, trueBlock)) {
1378         auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1379         auto ref = isInstance->GetInput(0).GetInst();
1380         // if IsInstance evaluates to True, its input is not null
1381         auto range = BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
1382         bri->SetBoundsRange(trueBlock, ref, range);
1383     }
1384 }
1385 
CalcNewBoundsRangeForCompare(GraphVisitor * v,BasicBlock * block,ConditionCode cc,InstPair args,BasicBlock * tgtBlock)1386 void BoundsAnalysis::CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, InstPair args,
1387                                                   BasicBlock *tgtBlock)
1388 {
1389     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1390     auto [left, right] = args;
1391     auto leftRange = bri->FindBoundsRange(block, left);
1392     auto rightRange = bri->FindBoundsRange(block, right);
1393     // try to skip triangle:
1394     /* [block]
1395      *    |  \
1396      *    |   \
1397      *    |   [BB]
1398      *    |   /
1399      *    |  /
1400      * [tgt_block]
1401      */
1402     if (CheckTriangleCase(block, tgtBlock)) {
1403         auto ranges = BoundsRange::TryNarrowBoundsByCC(cc, {leftRange, rightRange});
1404         if (cc == ConditionCode::CC_LT && IsLenArray(right)) {
1405             ranges.first.SetLenArray(right);
1406         } else if (cc == ConditionCode::CC_GT && IsLenArray(left)) {
1407             ranges.second.SetLenArray(left);
1408         } else if (leftRange.GetLenArray() != nullptr) {
1409             ranges.first.SetLenArray(leftRange.GetLenArray());
1410         } else if (rightRange.GetLenArray() != nullptr) {
1411             ranges.second.SetLenArray(rightRange.GetLenArray());
1412         }
1413         if (leftRange.HasActualLengthLoop()) {
1414             ranges.first.SetActualLengthLoop(leftRange.GetActualLengthLoop());
1415         }
1416         if (rightRange.HasActualLengthLoop()) {
1417             ranges.second.SetActualLengthLoop(rightRange.GetActualLengthLoop());
1418         }
1419         if (!bri->FindBoundsRange(tgtBlock, left).HasActualLengthLoop()) {
1420             bri->SetBoundsRange(tgtBlock, left, ranges.first.FitInType(left->GetType()));
1421         }
1422         if (!bri->FindBoundsRange(tgtBlock, right).HasActualLengthLoop()) {
1423             bri->SetBoundsRange(tgtBlock, right, ranges.second.FitInType(right->GetType()));
1424         }
1425     }
1426 }
1427 
1428 template <Opcode OPC>
CalcNewBoundsRangeUnary(GraphVisitor * v,const Inst * inst)1429 void BoundsAnalysis::CalcNewBoundsRangeUnary(GraphVisitor *v, const Inst *inst)
1430 {
1431     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::REFERENCE) {
1432         return;
1433     }
1434     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1435     auto input0 = inst->GetInput(0).GetInst();
1436     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1437     BoundsRange range;
1438     Loop *loop = nullptr;
1439     // clang-format off
1440         // NOLINTNEXTLINE(readability-braces-around-statements)
1441         if constexpr (OPC == Opcode::Neg) {
1442             range = range0.Neg();
1443             loop = range0.GetActualLengthLoop();
1444         // NOLINTNEXTLINE(readability-braces-around-statements, readability-misleading-indentation)
1445         } else if constexpr (OPC == Opcode::Abs) {
1446             range = range0.Abs();
1447             loop = range0.GetActualLengthLoop();
1448         } else {
1449             UNREACHABLE();
1450         }
1451     // clang-format on
1452     range.SetActualLengthLoop(loop);
1453     bri->SetBoundsRange(inst->GetBasicBlock(), inst, range.FitInType(inst->GetType()));
1454 }
1455 
CalcNewBoundsRangeAdd(const BoundsRangeInfo * bri,const Inst * inst)1456 BoundsRange BoundsAnalysis::CalcNewBoundsRangeAdd(const BoundsRangeInfo *bri, const Inst *inst)
1457 {
1458     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1459     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1460     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1461     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1462     auto lenArray0 = range0.GetLenArray();
1463     auto lenArray1 = range1.GetLenArray();
1464 
1465     BoundsRange range = range0.Add(range1);
1466     if (!range.IsMaxRange(inst->GetType())) {
1467         if (BoundsRange(0).IsMoreOrEqual(range1) && lenArray0 != nullptr) {
1468             range.SetLenArray(lenArray0);
1469         } else if (BoundsRange(0).IsMoreOrEqual(range0) && lenArray1 != nullptr) {
1470             range.SetLenArray(lenArray1);
1471         } else if (IsLenArray(input0) && range1.IsNegative()) {
1472             range.SetLenArray(input0);
1473         } else if (IsLenArray(input1) && range0.IsNegative()) {
1474             range.SetLenArray(input1);
1475         }
1476     }
1477     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1478         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1479     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1480         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1481     }
1482     return range;
1483 }
1484 
CalcNewBoundsRangeSub(const BoundsRangeInfo * bri,const Inst * inst)1485 BoundsRange BoundsAnalysis::CalcNewBoundsRangeSub(const BoundsRangeInfo *bri, const Inst *inst)
1486 {
1487     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1488     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1489     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1490     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1491     auto lenArray0 = range0.GetLenArray();
1492 
1493     BoundsRange range = range0.Sub(range1);
1494     if (!range.IsMaxRange(inst->GetType())) {
1495         if (range1.IsNotNegative() && lenArray0 != nullptr) {
1496             range.SetLenArray(lenArray0);
1497         } else if (IsLenArray(input0) && range1.IsMore(BoundsRange(0))) {
1498             range.SetLenArray(input0);
1499         }
1500     }
1501     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1502         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1503     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1504         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1505     }
1506     return range;
1507 }
1508 
CalcNewBoundsRangeMod(const BoundsRangeInfo * bri,const Inst * inst)1509 BoundsRange BoundsAnalysis::CalcNewBoundsRangeMod(const BoundsRangeInfo *bri, const Inst *inst)
1510 {
1511     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1512     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1513     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1514     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1515     auto lenArray0 = range0.GetLenArray();
1516     auto lenArray1 = range1.GetLenArray();
1517 
1518     BoundsRange range = range0.Mod(range1);
1519     if (lenArray1 != nullptr && range1.IsNotNegative()) {
1520         range.SetLenArray(lenArray1);
1521     } else if (lenArray0 != nullptr) {
1522         // a % b always has the same sign as a, so if a < LenArray, then (a % b) < LenArray
1523         range.SetLenArray(lenArray0);
1524     } else if (IsLenArray(input1)) {
1525         range.SetLenArray(input1);
1526     }
1527     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1528         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1529     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1530         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1531     }
1532     return range;
1533 }
1534 
CalcNewBoundsRangeMul(const BoundsRangeInfo * bri,const Inst * inst)1535 BoundsRange BoundsAnalysis::CalcNewBoundsRangeMul(const BoundsRangeInfo *bri, const Inst *inst)
1536 {
1537     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1538     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1539     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1540     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1541     BoundsRange range;
1542     if (!range0.IsMaxRange() || !range1.IsMaxRange()) {
1543         range = range0.Mul(range1);
1544     }
1545     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1546         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1547     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1548         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1549     }
1550     return range;
1551 }
1552 
CalcNewBoundsRangeDiv(const BoundsRangeInfo * bri,const Inst * inst)1553 BoundsRange BoundsAnalysis::CalcNewBoundsRangeDiv(const BoundsRangeInfo *bri, const Inst *inst)
1554 {
1555     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1556     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1557     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1558     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1559     auto lenArray0 = range0.GetLenArray();
1560 
1561     BoundsRange range = range0.Div(range1);
1562     if (range0.IsNotNegative() && range1.IsNotNegative() && lenArray0 != nullptr) {
1563         range.SetLenArray(lenArray0);
1564     }
1565     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1566         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1567     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1568         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1569     }
1570     return range;
1571 }
1572 
CalcNewBoundsRangeShr(const BoundsRangeInfo * bri,const Inst * inst)1573 BoundsRange BoundsAnalysis::CalcNewBoundsRangeShr(const BoundsRangeInfo *bri, const Inst *inst)
1574 {
1575     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1576     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1577     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1578     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1579     auto lenArray0 = range0.GetLenArray();
1580 
1581     BoundsRange range = range0.Shr(range1, inst->GetType());
1582     if (range0.IsNotNegative() && lenArray0 != nullptr) {
1583         range.SetLenArray(lenArray0);
1584     }
1585     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1586         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1587     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1588         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1589     }
1590     return range;
1591 }
1592 
CalcNewBoundsRangeAShr(const BoundsRangeInfo * bri,const Inst * inst)1593 BoundsRange BoundsAnalysis::CalcNewBoundsRangeAShr(const BoundsRangeInfo *bri, const Inst *inst)
1594 {
1595     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1596     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1597     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1598     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1599     auto lenArray0 = range0.GetLenArray();
1600 
1601     BoundsRange range = range0.AShr(range1, inst->GetType());
1602     if (lenArray0 != nullptr) {
1603         range.SetLenArray(lenArray0);
1604     }
1605     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1606         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1607     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1608         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1609     }
1610     return range;
1611 }
1612 
CalcNewBoundsRangeShl(const BoundsRangeInfo * bri,const Inst * inst)1613 BoundsRange BoundsAnalysis::CalcNewBoundsRangeShl(const BoundsRangeInfo *bri, const Inst *inst)
1614 {
1615     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1616     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1617     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1618     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1619 
1620     BoundsRange range = range0.Shl(range1, inst->GetType());
1621     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1622         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1623     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1624         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1625     }
1626     return range;
1627 }
1628 
CalcNewBoundsRangeAnd(const BoundsRangeInfo * bri,const Inst * inst)1629 BoundsRange BoundsAnalysis::CalcNewBoundsRangeAnd(const BoundsRangeInfo *bri, const Inst *inst)
1630 {
1631     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1632     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1633     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1634     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1635 
1636     BoundsRange range = range0.And(range1);
1637     if (range0.HasActualLengthLoop() && (range1.IsConst() || range1.HasActualLengthLoop())) {
1638         range.SetActualLengthLoop(range0.GetActualLengthLoop());
1639     } else if (range1.HasActualLengthLoop() && range0.IsConst()) {
1640         range.SetActualLengthLoop(range1.GetActualLengthLoop());
1641     }
1642     return range;
1643 }
1644 
CheckBoundsRange(const BoundsRangeInfo * bri,const Inst * inst)1645 bool BoundsAnalysis::CheckBoundsRange(const BoundsRangeInfo *bri, const Inst *inst)
1646 {
1647     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1648     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1649     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1650     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1651     return (input0->GetType() != DataType::UINT64 || !range0.IsMaxRange(DataType::UINT64) ||
1652             range0.GetLenArray() != nullptr) &&
1653            (input1->GetType() != DataType::UINT64 || !range1.IsMaxRange(DataType::UINT64) ||
1654             range1.GetLenArray() != nullptr);
1655 }
1656 
1657 template <Opcode OPC>
CalcNewBoundsRangeBinary(GraphVisitor * v,const Inst * inst)1658 void BoundsAnalysis::CalcNewBoundsRangeBinary(GraphVisitor *v, const Inst *inst)
1659 {
1660     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::REFERENCE) {
1661         return;
1662     }
1663     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1664     BoundsRange range;
1665     if (CheckBoundsRange(bri, inst)) {
1666         if constexpr (OPC == Opcode::Add) {  // NOLINT
1667             range = CalcNewBoundsRangeAdd(bri, inst);
1668         } else if constexpr (OPC == Opcode::Sub) {  // NOLINT
1669             range = CalcNewBoundsRangeSub(bri, inst);
1670         } else if constexpr (OPC == Opcode::Mod) {  // NOLINT
1671             range = CalcNewBoundsRangeMod(bri, inst);
1672         } else if constexpr (OPC == Opcode::Mul) {  // NOLINT
1673             range = CalcNewBoundsRangeMul(bri, inst);
1674         } else if constexpr (OPC == Opcode::Div) {  // NOLINT
1675             range = CalcNewBoundsRangeDiv(bri, inst);
1676         } else if constexpr (OPC == Opcode::Shr) {  // NOLINT
1677             range = CalcNewBoundsRangeShr(bri, inst);
1678         } else if constexpr (OPC == Opcode::AShr) {  // NOLINT
1679             range = CalcNewBoundsRangeAShr(bri, inst);
1680         } else if constexpr (OPC == Opcode::Shl) {  // NOLINT
1681             range = CalcNewBoundsRangeShl(bri, inst);
1682         } else if constexpr (OPC == Opcode::And) {
1683             range = CalcNewBoundsRangeAnd(bri, inst);
1684         } else {
1685             UNREACHABLE();
1686         }
1687     }
1688     bri->SetBoundsRange(inst->GetBasicBlock(), inst, range.FitInType(inst->GetType()));
1689 }
1690 
1691 }  // namespace ark::compiler
1692