• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021-2024 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     if (left_ < typeMin || left_ > typeMax || right_ < typeMin || right_ > typeMax) {
416         return BoundsRange(typeMin, typeMax);
417     }
418     return *this;
419 }
420 
Union(const ArenaVector<BoundsRange> & ranges)421 BoundsRange BoundsRange::Union(const ArenaVector<BoundsRange> &ranges)
422 {
423     int64_t min = MAX_RANGE_VALUE;
424     int64_t max = MIN_RANGE_VALUE;
425     for (const auto &range : ranges) {
426         if (range.GetLeft() < min) {
427             min = range.GetLeft();
428         }
429         if (range.GetRight() > max) {
430             max = range.GetRight();
431         }
432     }
433     return BoundsRange(min, max);
434 }
435 
NarrowBoundsByNE(BoundsRange::RangePair const & ranges)436 BoundsRange::RangePair BoundsRange::NarrowBoundsByNE(BoundsRange::RangePair const &ranges)
437 {
438     auto &[left_range, right_range] = ranges;
439     int64_t ll = left_range.GetLeft();
440     int64_t lr = left_range.GetRight();
441     int64_t rl = right_range.GetLeft();
442     int64_t rr = right_range.GetRight();
443     // We can narrow bounds of a range if another is a constant and matches one of the bounds
444     // Mostly needed for a reference comparison with null
445     if (left_range.IsConst() && !right_range.IsConst()) {
446         if (ll == rl) {
447             return {left_range, BoundsRange(rl + 1, rr)};
448         }
449         if (ll == rr) {
450             return {left_range, BoundsRange(rl, rr - 1)};
451         }
452     }
453     if (!left_range.IsConst() && right_range.IsConst()) {
454         if (rl == ll) {
455             return {BoundsRange(ll + 1, lr), right_range};
456         }
457         if (rl == lr) {
458             return {BoundsRange(ll, lr - 1), right_range};
459         }
460     }
461     return ranges;
462 }
463 
NarrowBoundsCase1(ConditionCode cc,BoundsRange::RangePair const & ranges)464 BoundsRange::RangePair BoundsRange::NarrowBoundsCase1(ConditionCode cc, BoundsRange::RangePair const &ranges)
465 {
466     auto &[left_range, right_range] = ranges;
467     int64_t lr = left_range.GetRight();
468     int64_t rl = right_range.GetLeft();
469     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
470         // With equal rl and lr left_range cannot be greater than right_range
471         if (rl == lr) {
472             return {BoundsRange(), BoundsRange()};
473         }
474         return {BoundsRange(rl + 1, lr), BoundsRange(rl, lr - 1)};
475     }
476     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE || cc == ConditionCode::CC_EQ) {
477         return {BoundsRange(rl, lr), BoundsRange(rl, lr)};
478     }
479     return ranges;
480 }
481 
NarrowBoundsCase2(ConditionCode cc,BoundsRange::RangePair const & ranges)482 BoundsRange::RangePair BoundsRange::NarrowBoundsCase2(ConditionCode cc, BoundsRange::RangePair const &ranges)
483 {
484     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_GE || cc == ConditionCode::CC_EQ ||
485         cc == ConditionCode::CC_A || cc == ConditionCode::CC_AE) {
486         return {BoundsRange(), BoundsRange()};
487     }
488     return ranges;
489 }
490 
NarrowBoundsCase3(ConditionCode cc,BoundsRange::RangePair const & ranges)491 BoundsRange::RangePair BoundsRange::NarrowBoundsCase3(ConditionCode cc, BoundsRange::RangePair const &ranges)
492 {
493     auto &[left_range, right_range] = ranges;
494     int64_t ll = left_range.GetLeft();
495     int64_t lr = left_range.GetRight();
496     int64_t rl = right_range.GetLeft();
497     int64_t rr = right_range.GetRight();
498     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
499         // rl == lr handled in case 1
500         return {BoundsRange(rl + 1, lr), right_range};
501     }
502     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE) {
503         return {BoundsRange(rl, lr), right_range};
504     }
505     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
506         // With equal ll and rr left_range cannot be less than right_range
507         if (ll == rr) {
508             return {BoundsRange(), BoundsRange()};
509         }
510         return {BoundsRange(ll, rr - 1), right_range};
511     }
512     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE) {
513         return {BoundsRange(ll, rr), right_range};
514     }
515     if (cc == ConditionCode::CC_EQ) {
516         return {BoundsRange(rl, rr), right_range};
517     }
518     return ranges;
519 }
520 
NarrowBoundsCase4(ConditionCode cc,BoundsRange::RangePair const & ranges)521 BoundsRange::RangePair BoundsRange::NarrowBoundsCase4(ConditionCode cc, BoundsRange::RangePair const &ranges)
522 {
523     auto &[left_range, right_range] = ranges;
524     int64_t ll = left_range.GetLeft();
525     int64_t rr = right_range.GetRight();
526     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
527         // With equal ll and rr left_range cannot be less than right_range
528         if (ll == rr) {
529             return {BoundsRange(), BoundsRange()};
530         }
531         return {BoundsRange(ll, rr - 1), BoundsRange(ll + 1, rr)};
532     }
533     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE || cc == ConditionCode::CC_EQ) {
534         return {BoundsRange(ll, rr), BoundsRange(ll, rr)};
535     }
536     return ranges;
537 }
538 
NarrowBoundsCase5(ConditionCode cc,BoundsRange::RangePair const & ranges)539 BoundsRange::RangePair BoundsRange::NarrowBoundsCase5(ConditionCode cc, BoundsRange::RangePair const &ranges)
540 {
541     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_LE || cc == ConditionCode::CC_EQ ||
542         cc == ConditionCode::CC_B || cc == ConditionCode::CC_BE) {
543         return {BoundsRange(), BoundsRange()};
544     }
545     return ranges;
546 }
547 
NarrowBoundsCase6(ConditionCode cc,BoundsRange::RangePair const & ranges)548 BoundsRange::RangePair BoundsRange::NarrowBoundsCase6(ConditionCode cc, BoundsRange::RangePair const &ranges)
549 {
550     auto &[left_range, right_range] = ranges;
551     int64_t ll = left_range.GetLeft();
552     int64_t lr = left_range.GetRight();
553     int64_t rl = right_range.GetLeft();
554     int64_t rr = right_range.GetRight();
555     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
556         // rl == lr handled in case 1
557         return {left_range, BoundsRange(rl, lr - 1)};
558     }
559     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE) {
560         return {left_range, BoundsRange(rl, lr)};
561     }
562     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
563         // ll == rr handled in case 4
564         return {left_range, BoundsRange(ll + 1, rr)};
565     }
566     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE) {
567         return {left_range, BoundsRange(ll, rr)};
568     }
569     if (cc == ConditionCode::CC_EQ) {
570         return {left_range, BoundsRange(ll, lr)};
571     }
572     return ranges;
573 }
574 
575 /**
576  * Try narrow bounds range for <if (left CC right)> situation
577  * Return a pair of narrowed left and right intervals
578  */
TryNarrowBoundsByCC(ConditionCode cc,BoundsRange::RangePair const & ranges)579 BoundsRange::RangePair BoundsRange::TryNarrowBoundsByCC(ConditionCode cc, BoundsRange::RangePair const &ranges)
580 {
581     if (cc == ConditionCode::CC_NE) {
582         return NarrowBoundsByNE(ranges);
583     }
584     auto &[left_range, right_range] = ranges;
585     int64_t ll = left_range.GetLeft();
586     int64_t lr = left_range.GetRight();
587     int64_t rl = right_range.GetLeft();
588     int64_t rr = right_range.GetRight();
589     // For further description () is for left_range bounds and [] is for right_range bounds
590     // case 1: ( [ ) ]
591     if (ll <= rl && rl <= lr && lr <= rr) {
592         return NarrowBoundsCase1(cc, ranges);
593     }
594     // case 2: ( ) [ ]
595     if (ll <= lr && lr < rl && rl <= rr) {
596         return NarrowBoundsCase2(cc, ranges);
597     }
598     // case 3: ( [ ] )
599     if (ll <= rl && rl <= rr && rr <= lr) {
600         return NarrowBoundsCase3(cc, ranges);
601     }
602     // case 4: [ ( ] )
603     if (rl <= ll && ll <= rr && rr <= lr) {
604         return NarrowBoundsCase4(cc, ranges);
605     }
606     // case 5: [ ] ( )
607     if (rl <= rr && rr < ll && ll <= lr) {
608         return NarrowBoundsCase5(cc, ranges);
609     }
610     // case 6: [ ( ) ]
611     if (rl <= ll && ll <= lr && lr <= rr) {
612         return NarrowBoundsCase6(cc, ranges);
613     }
614     return ranges;
615 }
616 
617 /// Return (left + right) or if overflows or underflows return nullopt of range type.
AddWithOverflowCheck(int64_t left,int64_t right)618 std::optional<int64_t> BoundsRange::AddWithOverflowCheck(int64_t left, int64_t right)
619 {
620     if (right == 0) {
621         return left;
622     }
623     if (right > 0) {
624         if (left <= (MAX_RANGE_VALUE - right)) {
625             // No overflow.
626             return left + right;
627         }
628         return std::nullopt;
629     }
630     if (left >= (MIN_RANGE_VALUE - right)) {
631         // No overflow.
632         return left + right;
633     }
634     return std::nullopt;
635 }
636 
AddWithOverflowCheck(uint64_t left,uint64_t right)637 std::optional<uint64_t> BoundsRange::AddWithOverflowCheck(uint64_t left, uint64_t right)
638 {
639     if (right == 0) {
640         return left;
641     }
642     if (left <= (UINT64_MAX - right)) {
643         // No overflow.
644         return left + right;
645     }
646     return std::nullopt;
647 }
648 
649 /// Return (left * right) or if overflows or underflows return nullopt of range type.
MulWithOverflowCheck(int64_t left,int64_t right)650 std::optional<int64_t> BoundsRange::MulWithOverflowCheck(int64_t left, int64_t right)
651 {
652     if (left == 0 || right == 0) {
653         return 0;
654     }
655     int64_t leftAbs = (left == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(left));
656     int64_t rightAbs = (right == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(right));
657     if (leftAbs <= (MAX_RANGE_VALUE / rightAbs)) {
658         // No overflow.
659         return left * right;
660     }
661     if ((right > 0 && left > 0) || (right < 0 && left < 0)) {
662         return std::nullopt;
663     }
664     return std::nullopt;
665 }
666 
MulWithOverflowCheck(uint64_t left,uint64_t right)667 std::optional<uint64_t> BoundsRange::MulWithOverflowCheck(uint64_t left, uint64_t right)
668 {
669     if (left == 0 || right == 0) {
670         return 0;
671     }
672     if (left <= (UINT64_MAX / right)) {
673         // No overflow.
674         return left * right;
675     }
676     return std::nullopt;
677 }
678 
679 /// Return (left / right) or nullopt VALUE for MIN_RANGE_VALUE / -1.
DivWithOverflowCheck(int64_t left,int64_t right)680 std::optional<int64_t> BoundsRange::DivWithOverflowCheck(int64_t left, int64_t right)
681 {
682     ASSERT(right != 0);
683     if (left == MIN_RANGE_VALUE && right == -1) {
684         return std::nullopt;
685     }
686     return left / right;
687 }
688 
FindBoundsRange(const BasicBlock * block,const Inst * inst) const689 BoundsRange BoundsRangeInfo::FindBoundsRange(const BasicBlock *block, const Inst *inst) const
690 {
691     ASSERT(block != nullptr && inst != nullptr);
692     ASSERT(!IsFloatType(inst->GetType()));
693     ASSERT(inst->GetType() == DataType::REFERENCE || DataType::GetCommonType(inst->GetType()) == DataType::INT64);
694     if (inst->GetOpcode() == Opcode::NullPtr) {
695         ASSERT(inst->GetType() == DataType::REFERENCE);
696         return BoundsRange(0);
697     }
698     if (IsInstNotNull(inst)) {
699         ASSERT(inst->GetType() == DataType::REFERENCE);
700         return BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
701     }
702     while (block != nullptr) {
703         if (boundsRangeInfo_.find(block) != boundsRangeInfo_.end() &&
704             boundsRangeInfo_.at(block).find(inst) != boundsRangeInfo_.at(block).end()) {
705             return boundsRangeInfo_.at(block).at(inst);
706         }
707         block = block->GetDominator();
708     }
709     // BoundsRange for constant can have len_array, so we should process it after the loop above
710     if (inst->IsConst()) {
711         ASSERT(inst->GetType() == DataType::INT64);
712         auto val = static_cast<int64_t>(inst->CastToConstant()->GetIntValue());
713         return BoundsRange(val);
714     }
715     if (IsLenArray(inst)) {
716         ASSERT(inst->GetType() == DataType::INT32);
717         auto maxLength = INT32_MAX;
718         if (inst->GetOpcode() == Opcode::LenArray) {
719             auto arrayInst = inst->CastToLenArray()->GetDataFlowInput(0);
720             auto typeInfo = arrayInst->GetObjectTypeInfo();
721             if (typeInfo) {
722                 auto klass = typeInfo.GetClass();
723                 auto runtime = inst->GetBasicBlock()->GetGraph()->GetRuntime();
724                 maxLength = runtime->GetMaxArrayLength(klass);
725             }
726         }
727         return BoundsRange(0, maxLength, nullptr, inst->GetType());
728     }
729     // if we know nothing about inst return the complete range of type
730     return BoundsRange(inst->GetType());
731 }
732 
SetBoundsRange(const BasicBlock * block,const Inst * inst,BoundsRange range)733 void BoundsRangeInfo::SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range)
734 {
735     if (inst->IsConst() && range.GetLenArray() == nullptr) {
736         return;
737     }
738     if (inst->IsConst()) {
739         auto val = static_cast<int64_t>(static_cast<const ConstantInst *>(inst)->GetIntValue());
740         range = BoundsRange(val, val, range.GetLenArray());
741     }
742     ASSERT(inst->GetType() == DataType::REFERENCE || DataType::GetCommonType(inst->GetType()) == DataType::INT64);
743     ASSERT(range.GetLeft() >= BoundsRange::GetMin(inst->GetType()));
744     ASSERT(range.GetRight() <= BoundsRange::GetMax(inst->GetType()));
745     if (!range.IsMaxRange() || range.GetLenArray() != nullptr) {
746         if (boundsRangeInfo_.find(block) == boundsRangeInfo_.end()) {
747             auto it1 = boundsRangeInfo_.emplace(block, aa_.Adapter());
748             ASSERT(it1.second);
749             it1.first->second.emplace(inst, range);
750         } else if (boundsRangeInfo_.at(block).find(inst) == boundsRangeInfo_.at(block).end()) {
751             boundsRangeInfo_.at(block).emplace(inst, range);
752         } else {
753             boundsRangeInfo_.at(block).at(inst) = range;
754         }
755     }
756 }
757 
BoundsAnalysis(Graph * graph)758 BoundsAnalysis::BoundsAnalysis(Graph *graph)
759     : Analysis(graph), boundsRangeInfo_(graph->GetAllocator()), loopsInfoTable_(graph->GetAllocator()->Adapter())
760 {
761 }
762 
RunImpl()763 bool BoundsAnalysis::RunImpl()
764 {
765     MarkerHolder holder {GetGraph()};
766     visited_ = holder.GetMarker();
767     ASSERT(!GetGraph()->IsBytecodeOptimizer());
768     boundsRangeInfo_.Clear();
769     loopsInfoTable_.clear();
770 
771     GetGraph()->RunPass<DominatorsTree>();
772     GetGraph()->RunPass<LoopAnalyzer>();
773 
774     VisitGraph();
775 
776     return true;
777 }
778 
IsInstNotNull(const Inst * inst,BasicBlock * block)779 bool BoundsAnalysis::IsInstNotNull(const Inst *inst, BasicBlock *block)
780 {
781     if (compiler::IsInstNotNull(inst)) {
782         return true;
783     }
784     auto bri = block->GetGraph()->GetBoundsRangeInfo();
785     auto range = bri->FindBoundsRange(block, inst);
786     return range.IsMore(BoundsRange(0));
787 }
788 
GetBlocksToVisit() const789 const ArenaVector<BasicBlock *> &BoundsAnalysis::GetBlocksToVisit() const
790 {
791     return GetGraph()->GetBlocksRPO();
792 }
793 
VisitNeg(GraphVisitor * v,Inst * inst)794 void BoundsAnalysis::VisitNeg(GraphVisitor *v, Inst *inst)
795 {
796     CalcNewBoundsRangeUnary<Opcode::Neg>(v, inst);
797 }
798 
VisitNegOverflowAndZeroCheck(GraphVisitor * v,Inst * inst)799 void BoundsAnalysis::VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst)
800 {
801     CalcNewBoundsRangeUnary<Opcode::Neg>(v, inst);
802 }
803 
VisitAbs(GraphVisitor * v,Inst * inst)804 void BoundsAnalysis::VisitAbs(GraphVisitor *v, Inst *inst)
805 {
806     CalcNewBoundsRangeUnary<Opcode::Abs>(v, inst);
807 }
808 
VisitAdd(GraphVisitor * v,Inst * inst)809 void BoundsAnalysis::VisitAdd(GraphVisitor *v, Inst *inst)
810 {
811     CalcNewBoundsRangeBinary<Opcode::Add>(v, inst);
812 }
813 
VisitAddOverflowCheck(GraphVisitor * v,Inst * inst)814 void BoundsAnalysis::VisitAddOverflowCheck(GraphVisitor *v, Inst *inst)
815 {
816     CalcNewBoundsRangeBinary<Opcode::Add>(v, inst);
817 }
818 
VisitSub(GraphVisitor * v,Inst * inst)819 void BoundsAnalysis::VisitSub(GraphVisitor *v, Inst *inst)
820 {
821     CalcNewBoundsRangeBinary<Opcode::Sub>(v, inst);
822 }
823 
VisitSubOverflowCheck(GraphVisitor * v,Inst * inst)824 void BoundsAnalysis::VisitSubOverflowCheck(GraphVisitor *v, Inst *inst)
825 {
826     CalcNewBoundsRangeBinary<Opcode::Sub>(v, inst);
827 }
828 
VisitMod(GraphVisitor * v,Inst * inst)829 void BoundsAnalysis::VisitMod(GraphVisitor *v, Inst *inst)
830 {
831     CalcNewBoundsRangeBinary<Opcode::Mod>(v, inst);
832 }
833 
VisitDiv(GraphVisitor * v,Inst * inst)834 void BoundsAnalysis::VisitDiv(GraphVisitor *v, Inst *inst)
835 {
836     CalcNewBoundsRangeBinary<Opcode::Div>(v, inst);
837 }
838 
VisitMul(GraphVisitor * v,Inst * inst)839 void BoundsAnalysis::VisitMul(GraphVisitor *v, Inst *inst)
840 {
841     CalcNewBoundsRangeBinary<Opcode::Mul>(v, inst);
842 }
843 
VisitAnd(GraphVisitor * v,Inst * inst)844 void BoundsAnalysis::VisitAnd(GraphVisitor *v, Inst *inst)
845 {
846     CalcNewBoundsRangeBinary<Opcode::And>(v, inst);
847 }
848 
VisitShr(GraphVisitor * v,Inst * inst)849 void BoundsAnalysis::VisitShr(GraphVisitor *v, Inst *inst)
850 {
851     CalcNewBoundsRangeBinary<Opcode::Shr>(v, inst);
852 }
853 
VisitAShr(GraphVisitor * v,Inst * inst)854 void BoundsAnalysis::VisitAShr(GraphVisitor *v, Inst *inst)
855 {
856     CalcNewBoundsRangeBinary<Opcode::AShr>(v, inst);
857 }
858 
VisitShl(GraphVisitor * v,Inst * inst)859 void BoundsAnalysis::VisitShl(GraphVisitor *v, Inst *inst)
860 {
861     CalcNewBoundsRangeBinary<Opcode::Shl>(v, inst);
862 }
863 
VisitIfImm(GraphVisitor * v,Inst * inst)864 void BoundsAnalysis::VisitIfImm(GraphVisitor *v, Inst *inst)
865 {
866     auto ifInst = inst->CastToIfImm();
867     if (ifInst->GetOperandsType() != DataType::BOOL) {
868         return;
869     }
870     ASSERT(ifInst->GetCc() == ConditionCode::CC_NE || ifInst->GetCc() == ConditionCode::CC_EQ);
871     ASSERT(ifInst->GetImm() == 0);
872 
873     auto input = inst->GetInput(0).GetInst();
874     if (input->GetOpcode() == Opcode::IsInstance) {
875         CalcNewBoundsRangeForIsInstanceInput(v, input->CastToIsInstance(), ifInst);
876         return;
877     }
878     if (input->GetOpcode() != Opcode::Compare) {
879         return;
880     }
881     auto compare = input->CastToCompare();
882     auto op0 = compare->GetInput(0).GetInst();
883     auto op1 = compare->GetInput(1).GetInst();
884     if ((DataType::GetCommonType(op0->GetType()) != DataType::INT64 && op0->GetType() != DataType::REFERENCE) ||
885         (DataType::GetCommonType(op1->GetType()) != DataType::INT64 && op1->GetType() != DataType::REFERENCE)) {
886         return;
887     }
888 
889     auto cc = compare->GetCc();
890     auto block = inst->GetBasicBlock();
891     BasicBlock *trueBlock;
892     BasicBlock *falseBlock;
893     if (ifInst->GetCc() == ConditionCode::CC_NE) {
894         // Corresponds to Compare result
895         trueBlock = block->GetTrueSuccessor();
896         falseBlock = block->GetFalseSuccessor();
897     } else if (ifInst->GetCc() == ConditionCode::CC_EQ) {
898         // Corresponds to inversion of Compare result
899         trueBlock = block->GetFalseSuccessor();
900         falseBlock = block->GetTrueSuccessor();
901     } else {
902         UNREACHABLE();
903     }
904     CalcNewBoundsRangeForCompare(v, block, cc, {op0, op1}, trueBlock);
905     CalcNewBoundsRangeForCompare(v, block, GetInverseConditionCode(cc), {op0, op1}, falseBlock);
906 }
907 
VisitPhi(GraphVisitor * v,Inst * inst)908 void BoundsAnalysis::VisitPhi(GraphVisitor *v, Inst *inst)
909 {
910     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::ANY || inst->GetType() == DataType::POINTER) {
911         return;
912     }
913     auto boundsAnalysis = static_cast<BoundsAnalysis *>(v);
914     auto bri = boundsAnalysis->GetBoundsRangeInfo();
915     auto phi = inst->CastToPhi();
916     // for phi in a countable loop
917     if (inst->GetType() != DataType::REFERENCE && boundsAnalysis->ProcessCountableLoop(phi, bri)) {
918         return;
919     }
920     // for other phis
921     MergePhiPredecessors(phi, bri);
922 }
923 
924 template <bool CHECK_TYPE>
MergePhiPredecessors(PhiInst * phi,BoundsRangeInfo * bri)925 bool BoundsAnalysis::MergePhiPredecessors(PhiInst *phi, BoundsRangeInfo *bri)
926 {
927     auto phiBlock = phi->GetBasicBlock();
928     ArenaVector<BoundsRange> ranges(phiBlock->GetGraph()->GetLocalAllocator()->Adapter());
929     for (auto *block : phiBlock->GetPredsBlocks()) {
930         auto *inst = phi->GetPhiInput(block);
931         if constexpr (CHECK_TYPE) {
932             if (inst->GetInputs().size() <= 1) {
933                 return false;
934             }
935             auto loop = phi->GetBasicBlock()->GetLoop();
936             auto input0 = inst->GetInput(0).GetInst();
937             auto loop0 = input0->GetBasicBlock()->GetLoop();
938             auto input1 = inst->GetInput(1).GetInst();
939             auto loop1 = input1->GetBasicBlock()->GetLoop();
940             if (!(inst->IsAddSub() && (input0->IsPhi() || input1->IsPhi()) &&
941                   (!loop0->IsInside(loop) || !loop1->IsInside(loop))) &&
942                 !inst->IsPhi()) {
943                 // NOTE: support Mul-Div and maybe more cases
944                 return false;
945             }
946         }
947         ranges.emplace_back(bri->FindBoundsRange(block, inst));
948     }
949     bri->SetBoundsRange(phiBlock, phi, BoundsRange::Union(ranges).FitInType(phi->GetType()));
950     return true;
951 }
952 
VisitNullCheck(GraphVisitor * v,Inst * inst)953 void BoundsAnalysis::VisitNullCheck(GraphVisitor *v, Inst *inst)
954 {
955     ProcessNullCheck(v, inst, inst->GetDataFlowInput(0));
956 }
957 
GetNestedLoopIterations(Loop * loop,CountableLoopInfo & loopInfo)958 std::optional<uint64_t> BoundsAnalysis::GetNestedLoopIterations(Loop *loop, CountableLoopInfo &loopInfo)
959 {
960     auto iterations = CountableLoopParser::GetLoopIterations(loopInfo);
961     if (!iterations.has_value()) {
962         return std::nullopt;
963     }
964     auto iterationsValue = iterations.value();
965     auto *outer = loop->GetOuterLoop();
966     if (outer->IsRoot()) {
967         return iterationsValue;
968     }
969     auto it = loopsInfoTable_.find(loop->GetOuterLoop());
970     if (it == loopsInfoTable_.end()) {
971         return std::nullopt;
972     }
973     auto outerLoopInfo = (*it).second;
974     if (!outerLoopInfo.has_value()) {
975         return std::nullopt;
976     }
977     auto outerIters = outerLoopInfo.value().second;
978     if (outerIters == std::numeric_limits<uint64_t>::max()) {
979         return outerIters;
980     }
981     return BoundsRange::MulWithOverflowCheck(iterationsValue, outerIters);
982 }
983 
GetSimpleLoopIterationsInfo(Loop * loop)984 std::optional<LoopIterationsInfo> BoundsAnalysis::GetSimpleLoopIterationsInfo(Loop *loop)
985 {
986     auto loopParser = CountableLoopParser(*loop);
987     auto loopInfo = loopParser.Parse();
988     if (!loopInfo.has_value()) {
989         // Loop is not countable
990         loopsInfoTable_.emplace(std::make_pair(loop, std::nullopt));
991         return std::nullopt;
992     }
993     auto loopInfoValue = loopInfo.value();
994     // Generally speaking, countable loop can have compile-time unknown number of iterations,
995     // i.e. when its init instruction is not a constant
996     // In this case it is possible to get the index phi range, but not for other phis
997     auto iterations = GetNestedLoopIterations(loop, loopInfoValue);
998     auto iterationsValue = std::numeric_limits<uint64_t>::max();
999     if (iterations.has_value()) {
1000         iterationsValue = iterations.value();
1001     }
1002     auto loopIterInfo = std::make_pair(loopInfoValue, iterationsValue);
1003     loopsInfoTable_.emplace(std::make_pair(loop, loopIterInfo));
1004     return loopIterInfo;
1005 }
1006 
GetNestedLoopIterationsInfo(Loop * loop)1007 std::optional<LoopIterationsInfo> BoundsAnalysis::GetNestedLoopIterationsInfo(Loop *loop)
1008 {
1009     auto it = loopsInfoTable_.find(loop);
1010     if (it == loopsInfoTable_.end()) {
1011         auto loopIterInfo = GetSimpleLoopIterationsInfo(loop);
1012         // If loop is visited first time - parse loop and fill the table
1013         for (auto *innerLoop : loop->GetInnerLoops()) {
1014             // If some of inner loops is not countable - we cannot process phis, except index
1015             if (!GetSimpleLoopIterationsInfo(innerLoop).has_value()) {
1016                 return std::nullopt;
1017             }
1018         }
1019         return loopIterInfo;
1020     }
1021     auto loopIterInfo = (*it).second;
1022     if (!loopIterInfo.has_value()) {
1023         // Loop has been visited and it is not countable
1024         return std::nullopt;
1025     }
1026     return loopIterInfo.value();
1027 }
1028 
ProcessCountableLoop(PhiInst * phi,BoundsRangeInfo * bri)1029 bool BoundsAnalysis::ProcessCountableLoop(PhiInst *phi, BoundsRangeInfo *bri)
1030 {
1031     auto *phiBlock = phi->GetBasicBlock();
1032     auto *loop = phiBlock->GetLoop();
1033     auto loopIterInfo = GetNestedLoopIterationsInfo(loop);
1034     if (!loopIterInfo.has_value()) {
1035         // loop is not countable
1036         return false;
1037     }
1038     [[maybe_unused]] auto [loopInfo, iterations] = loopIterInfo.value();
1039     if (phi == loopInfo.index) {
1040         // Index phi was processed while parsing the loop
1041         return loopsRevisiting_ ? true : ProcessIndexPhi(loop, bri, loopInfo);
1042     }
1043     if (iterations != std::numeric_limits<uint64_t>::max()) {
1044         if (phiBlock == loop->GetHeader()) {
1045             // At the beginning assign init phi a value range from its input
1046             return ProcessInitPhi(phi, bri);
1047         } else {  // NOLINT(readability-else-after-return)
1048             // For update phi merge predecessors and propagate bounds info to a loop
1049             return ProcessUpdatePhi(phi, bri, iterations);
1050         }
1051     }
1052     return false;
1053 }
1054 
1055 // "static" keyword for internal linkage
MoveRangeAccordingCC(ConditionCode cc,BoundsRange & lowerRange,BoundsRange & upperRange,const Inst * upper)1056 static void MoveRangeAccordingCC(ConditionCode cc, BoundsRange &lowerRange, BoundsRange &upperRange, const Inst *upper)
1057 {
1058     if (cc == CC_GT) {
1059         lowerRange = lowerRange.Add(BoundsRange(1));
1060     } else if (cc == CC_LT) {
1061         upperRange = upperRange.Sub(BoundsRange(1));
1062         if (IsLenArray(upper)) {
1063             upperRange.SetLenArray(upper);
1064         }
1065     }
1066 }
1067 
ProcessIndexPhi(Loop * loop,BoundsRangeInfo * bri,CountableLoopInfo & loopInfoValue)1068 bool BoundsAnalysis::ProcessIndexPhi(Loop *loop, BoundsRangeInfo *bri, CountableLoopInfo &loopInfoValue)
1069 {
1070     auto *indexPhi = loopInfoValue.index;
1071     auto *phiBlock = indexPhi->GetBasicBlock();
1072     ASSERT(loopInfoValue.update->IsAddSub());
1073     auto *lower = loopInfoValue.init;
1074     auto *upper = loopInfoValue.test;
1075     auto cc = loopInfoValue.normalizedCc;
1076     ASSERT(cc == CC_LE || cc == CC_LT || cc == CC_GE || cc == CC_GT);
1077     if (!loopInfoValue.isInc) {
1078         lower = loopInfoValue.test;
1079         upper = loopInfoValue.init;
1080     }
1081     auto lowerRange = bri->FindBoundsRange(phiBlock, lower);
1082     auto upperRange = bri->FindBoundsRange(phiBlock, upper);
1083     MoveRangeAccordingCC(cc, lowerRange, upperRange, upper);
1084     if (lowerRange.GetLeft() > upperRange.GetRight()) {
1085         return false;
1086     }
1087     auto phiType = indexPhi->GetType();
1088     auto left = lowerRange.GetLeft();
1089     auto right = upperRange.GetRight();
1090     auto lenArray = upperRange.GetLenArray();
1091     auto isHeadLoopExit = loopInfoValue.ifImm->GetBasicBlock() == loop->GetHeader();
1092     if (!upperRange.IsMoreOrEqual(lowerRange) && !isHeadLoopExit) {
1093         return false;
1094     }
1095     if (!upperRange.IsMoreOrEqual(lowerRange) && !CountableLoopParser::HasPreHeaderCompare(loop, loopInfoValue)) {
1096         ASSERT(phiBlock == loop->GetHeader());
1097         if (loopInfoValue.ifImm->GetBasicBlock() == phiBlock) {
1098             auto nextLoopBlock = phiBlock->GetTrueSuccessor();
1099             if (nextLoopBlock->GetLoop() != loop && !nextLoopBlock->GetLoop()->IsInside(loop)) {
1100                 nextLoopBlock = phiBlock->GetFalseSuccessor();
1101                 ASSERT(nextLoopBlock->GetLoop() == loop || nextLoopBlock->GetLoop()->IsInside(loop));
1102             }
1103             if (nextLoopBlock != phiBlock) {
1104                 auto range = BoundsRange(left, right, lenArray);
1105                 bri->SetBoundsRange(nextLoopBlock, indexPhi, range.FitInType(phiType));
1106             }
1107         }
1108         // index can be more (less) than loop bound on first iteration
1109         if (cc == CC_LE || cc == CC_LT) {
1110             right = std::max(right, lowerRange.GetRight());
1111             lenArray = nullptr;
1112         } else {
1113             left = std::min(left, upperRange.GetLeft());
1114         }
1115     }
1116     auto range = BoundsRange(left, right, lenArray);
1117     bri->SetBoundsRange(phiBlock, indexPhi, range.FitInType(phiType));
1118     return true;
1119 }
1120 
ProcessInitPhi(PhiInst * initPhi,BoundsRangeInfo * bri)1121 bool BoundsAnalysis::ProcessInitPhi(PhiInst *initPhi, BoundsRangeInfo *bri)
1122 {
1123     auto *phiBlock = initPhi->GetBasicBlock();
1124     auto *curLoop = phiBlock->GetLoop();
1125     auto inputs = initPhi->GetInputs();
1126 
1127     // Find an init instruction, coming inside of the current loop
1128     auto *initInst = inputs[0].GetInst();
1129     auto *updateInst = inputs[1].GetInst();
1130     if (curLoop->IsInside(updateInst->GetBasicBlock()->GetLoop())) {
1131         std::swap(initInst, updateInst);
1132     }
1133 
1134     if (!loopsRevisiting_) {
1135         if (!updateInst->IsPhi()) {
1136             // For cases, when an init phi has no corresponding update phi
1137             return false;
1138         }
1139         auto initRange = bri->FindBoundsRange(initInst->GetBasicBlock(), initInst);
1140         bri->SetBoundsRange(phiBlock, initPhi, initRange.FitInType(initPhi->GetType()));
1141         return true;
1142     }
1143 
1144     // Else init phi range is the union range
1145     // (which is [min(init.left, update.left), max(init.right, update.right)])
1146     if (!updateInst->IsMarked(visited_)) {
1147         // If corresponding update phi was not processed yet
1148         return true;
1149     }
1150     auto *lenArray = bri->FindBoundsRange(initPhi->GetBasicBlock(), initPhi).GetLenArray();
1151     MergePhiPredecessors<false>(initPhi, bri);
1152     if (lenArray != nullptr) {
1153         bri->FindBoundsRange(initPhi->GetBasicBlock(), initPhi).SetLenArray(lenArray);
1154     }
1155     return true;
1156 }
1157 
ProcessUpdatePhi(PhiInst * updatePhi,BoundsRangeInfo * bri,uint64_t iterations)1158 bool BoundsAnalysis::ProcessUpdatePhi(PhiInst *updatePhi, BoundsRangeInfo *bri, uint64_t iterations)
1159 {
1160     auto *updatePhiBlock = updatePhi->GetBasicBlock();
1161     auto *loop = updatePhiBlock->GetLoop();
1162     auto *header = loop->GetHeader();
1163 
1164     // Find corresponding init phi
1165     auto *initPhi = TryFindCorrespondingInitPhi(updatePhi, header);
1166     if (initPhi == nullptr) {
1167         // For the case, when an update phi has no init phi prototype in the header
1168         // (i.e. some local loop variable control flow)
1169         // it is not required to reprocess the loop
1170         return true;
1171     }
1172 
1173     // Unite inputs' bounds range info
1174     if (!MergePhiPredecessors<true>(updatePhi, bri)) {
1175         // Cannot count update phi range => need to invalidate init phi range
1176         // Set maximal possible range and revisit loop to invalidate dependent ranges
1177         bri->SetBoundsRange(header, initPhi, BoundsRange(initPhi->GetType()));
1178         VisitLoop(header, updatePhiBlock);
1179         return false;
1180     }
1181 
1182     // While revisiting, we just merge predecessors, because they can be changed
1183     if (loopsRevisiting_) {
1184         return true;
1185     }
1186 
1187     auto initRange = bri->FindBoundsRange(header, initPhi);
1188     auto updateRange = bri->FindBoundsRange(updatePhiBlock, updatePhi);
1189     auto iterRange = BoundsRange(iterations);
1190 
1191     // Update phi range is changing by adding a range difference multiplied by iterations number
1192     auto diffRange = updateRange.Diff(initRange);
1193     auto updateNewRange = initRange.Add(diffRange.Mul(iterRange));
1194     bri->SetBoundsRange(updatePhiBlock, updatePhi, updateNewRange.FitInType(updatePhi->GetType()));
1195     updatePhi->SetMarker(visited_);
1196 
1197     // Propagate init phi bounds info to a loop
1198     VisitLoop(header, updatePhiBlock);
1199     return true;
1200 }
1201 
TryFindCorrespondingInitPhi(PhiInst * updatePhi,BasicBlock * header)1202 Inst *BoundsAnalysis::TryFindCorrespondingInitPhi(PhiInst *updatePhi, BasicBlock *header)
1203 {
1204     for (auto &user : updatePhi->GetUsers()) {
1205         if (user.GetInst()->GetBasicBlock() != header) {
1206             continue;
1207         }
1208         auto initPhi = user.GetInst();
1209         ASSERT(initPhi->IsPhi());
1210         return initPhi;
1211     }
1212     return nullptr;
1213 }
1214 
VisitLoop(BasicBlock * header,BasicBlock * updatePhiBlock)1215 void BoundsAnalysis::VisitLoop(BasicBlock *header, BasicBlock *updatePhiBlock)
1216 {
1217     auto &rpo = GetGraph()->GetBlocksRPO();
1218     auto *curLoop = header->GetLoop();
1219     auto startIt = std::find(rpo.begin(), rpo.end(), header);
1220     auto endIt = std::find(rpo.begin(), rpo.end(), updatePhiBlock);
1221     loopsRevisiting_ = true;  // To avoid complex recalculations and not to loop the algorithm
1222 
1223     // First part: revisit current loop and its inner loops, which have been visited before
1224     for (auto it = startIt; it != endIt; ++it) {
1225         auto *block = *it;
1226         // Process loop and its nested loops only
1227         if (block->GetLoop() != curLoop && !block->GetLoop()->IsInside(curLoop)) {
1228             continue;
1229         }
1230         for (auto *inst : block->AllInsts()) {
1231             TABLE[static_cast<unsigned>(inst->GetOpcode())](this, inst);
1232         }
1233     }
1234 
1235     // Second part: revisit outer loops, going out of nest
1236     curLoop = curLoop->GetOuterLoop();
1237     auto *innerHeader = header;
1238     while (!curLoop->IsRoot()) {
1239         auto *curHeader = curLoop->GetHeader();
1240         startIt = std::find(rpo.begin(), rpo.end(), curHeader);
1241         endIt = std::find(rpo.begin(), rpo.end(), innerHeader);
1242         for (auto it = startIt; it != endIt; ++it) {
1243             auto *block = *it;
1244             // Process this loop only
1245             if (block->GetLoop() != curLoop) {
1246                 continue;
1247             }
1248             for (auto *inst : block->AllInsts()) {
1249                 TABLE[static_cast<unsigned>(inst->GetOpcode())](this, inst);
1250             }
1251         }
1252         curLoop = curLoop->GetOuterLoop();
1253         innerHeader = curHeader;
1254     }
1255 
1256     loopsRevisiting_ = false;
1257 }
1258 
CheckTriangleCase(const BasicBlock * block,const BasicBlock * tgtBlock)1259 bool BoundsAnalysis::CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgtBlock)
1260 {
1261     auto &predsBlocks = tgtBlock->GetPredsBlocks();
1262     auto loop = tgtBlock->GetLoop();
1263     auto &backEdges = loop->GetBackEdges();
1264     if (predsBlocks.size() == 1) {
1265         return true;
1266     }
1267     if (!loop->IsRoot() && backEdges.size() == 1 && predsBlocks.size() == 2U) {
1268         if (predsBlocks[0] == block && predsBlocks[1] == backEdges[0]) {
1269             return true;
1270         }
1271         if (predsBlocks[1] == block && predsBlocks[0] == backEdges[0]) {
1272             return true;
1273         }
1274         return false;
1275     }
1276     return false;
1277 }
1278 
ProcessNullCheck(GraphVisitor * v,const Inst * checkInst,const Inst * refInput)1279 void BoundsAnalysis::ProcessNullCheck(GraphVisitor *v, const Inst *checkInst, const Inst *refInput)
1280 {
1281     ASSERT(checkInst->IsNullCheck() || checkInst->GetOpcode() == Opcode::DeoptimizeIf);
1282     ASSERT(refInput->GetType() == DataType::REFERENCE);
1283     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1284     auto block = checkInst->GetBasicBlock();
1285     auto range = BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
1286     for (auto domBlock : block->GetDominatedBlocks()) {
1287         bri->SetBoundsRange(domBlock, refInput, range);
1288     }
1289 }
1290 
CalcNewBoundsRangeForIsInstanceInput(GraphVisitor * v,IsInstanceInst * isInstance,IfImmInst * ifImm)1291 void BoundsAnalysis::CalcNewBoundsRangeForIsInstanceInput(GraphVisitor *v, IsInstanceInst *isInstance, IfImmInst *ifImm)
1292 {
1293     ASSERT(isInstance == ifImm->GetInput(0).GetInst());
1294     auto block = ifImm->GetBasicBlock();
1295     auto trueBlock = ifImm->GetEdgeIfInputTrue();
1296     if (CheckTriangleCase(block, trueBlock)) {
1297         auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1298         auto ref = isInstance->GetInput(0).GetInst();
1299         // if IsInstance evaluates to True, its input is not null
1300         auto range = BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
1301         bri->SetBoundsRange(trueBlock, ref, range);
1302     }
1303 }
1304 
CalcNewBoundsRangeForCompare(GraphVisitor * v,BasicBlock * block,ConditionCode cc,InstPair args,BasicBlock * tgtBlock)1305 void BoundsAnalysis::CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, InstPair args,
1306                                                   BasicBlock *tgtBlock)
1307 {
1308     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1309     auto [left, right] = args;
1310     auto leftRange = bri->FindBoundsRange(block, left);
1311     auto rightRange = bri->FindBoundsRange(block, right);
1312     // try to skip triangle:
1313     /* [block]
1314      *    |  \
1315      *    |   \
1316      *    |   [BB]
1317      *    |   /
1318      *    |  /
1319      * [tgt_block]
1320      */
1321     if (CheckTriangleCase(block, tgtBlock)) {
1322         auto ranges = BoundsRange::TryNarrowBoundsByCC(cc, {leftRange, rightRange});
1323         if (cc == ConditionCode::CC_LT && IsLenArray(right)) {
1324             ranges.first.SetLenArray(right);
1325         } else if (cc == ConditionCode::CC_GT && IsLenArray(left)) {
1326             ranges.second.SetLenArray(left);
1327         } else if (leftRange.GetLenArray() != nullptr) {
1328             ranges.first.SetLenArray(leftRange.GetLenArray());
1329         } else if (rightRange.GetLenArray() != nullptr) {
1330             ranges.second.SetLenArray(rightRange.GetLenArray());
1331         }
1332         bri->SetBoundsRange(tgtBlock, left, ranges.first.FitInType(left->GetType()));
1333         bri->SetBoundsRange(tgtBlock, right, ranges.second.FitInType(right->GetType()));
1334     }
1335 }
1336 
1337 template <Opcode OPC>
CalcNewBoundsRangeUnary(GraphVisitor * v,const Inst * inst)1338 void BoundsAnalysis::CalcNewBoundsRangeUnary(GraphVisitor *v, const Inst *inst)
1339 {
1340     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::REFERENCE) {
1341         return;
1342     }
1343     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1344     auto input0 = inst->GetInput(0).GetInst();
1345     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1346     BoundsRange range;
1347     // clang-format off
1348         // NOLINTNEXTLINE(readability-braces-around-statements)
1349         if constexpr (OPC == Opcode::Neg) {
1350             range = range0.Neg();
1351         // NOLINTNEXTLINE(readability-braces-around-statements, readability-misleading-indentation)
1352         } else if constexpr (OPC == Opcode::Abs) {
1353             range = range0.Abs();
1354         } else {
1355             UNREACHABLE();
1356         }
1357     // clang-format on
1358     bri->SetBoundsRange(inst->GetBasicBlock(), inst, range.FitInType(inst->GetType()));
1359 }
1360 
CalcNewBoundsRangeAdd(const BoundsRangeInfo * bri,const Inst * inst)1361 BoundsRange BoundsAnalysis::CalcNewBoundsRangeAdd(const BoundsRangeInfo *bri, const Inst *inst)
1362 {
1363     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1364     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1365     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1366     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1367     auto lenArray0 = range0.GetLenArray();
1368     auto lenArray1 = range1.GetLenArray();
1369 
1370     BoundsRange range = range0.Add(range1);
1371     if (!range.IsMaxRange(inst->GetType())) {
1372         if (BoundsRange(0).IsMoreOrEqual(range1) && lenArray0 != nullptr) {
1373             range.SetLenArray(lenArray0);
1374         } else if (BoundsRange(0).IsMoreOrEqual(range0) && lenArray1 != nullptr) {
1375             range.SetLenArray(lenArray1);
1376         } else if (IsLenArray(input0) && range1.IsNegative()) {
1377             range.SetLenArray(input0);
1378         } else if (IsLenArray(input1) && range0.IsNegative()) {
1379             range.SetLenArray(input1);
1380         }
1381     }
1382     return range;
1383 }
1384 
CalcNewBoundsRangeSub(const BoundsRangeInfo * bri,const Inst * inst)1385 BoundsRange BoundsAnalysis::CalcNewBoundsRangeSub(const BoundsRangeInfo *bri, const Inst *inst)
1386 {
1387     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1388     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1389     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1390     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1391     auto lenArray0 = range0.GetLenArray();
1392 
1393     BoundsRange range = range0.Sub(range1);
1394     if (!range.IsMaxRange(inst->GetType())) {
1395         if (range1.IsNotNegative() && lenArray0 != nullptr) {
1396             range.SetLenArray(lenArray0);
1397         } else if (IsLenArray(input0) && range1.IsMore(BoundsRange(0))) {
1398             range.SetLenArray(input0);
1399         }
1400     }
1401     return range;
1402 }
1403 
CalcNewBoundsRangeMod(const BoundsRangeInfo * bri,const Inst * inst)1404 BoundsRange BoundsAnalysis::CalcNewBoundsRangeMod(const BoundsRangeInfo *bri, const Inst *inst)
1405 {
1406     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1407     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1408     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1409     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1410     auto lenArray0 = range0.GetLenArray();
1411     auto lenArray1 = range1.GetLenArray();
1412 
1413     BoundsRange range = range0.Mod(range1);
1414     if (lenArray1 != nullptr && range1.IsNotNegative()) {
1415         range.SetLenArray(lenArray1);
1416     } else if (lenArray0 != nullptr) {
1417         // a % b always has the same sign as a, so if a < LenArray, then (a % b) < LenArray
1418         range.SetLenArray(lenArray0);
1419     } else if (IsLenArray(input1)) {
1420         range.SetLenArray(input1);
1421     }
1422     return range;
1423 }
1424 
CalcNewBoundsRangeMul(const BoundsRangeInfo * bri,const Inst * inst)1425 BoundsRange BoundsAnalysis::CalcNewBoundsRangeMul(const BoundsRangeInfo *bri, const Inst *inst)
1426 {
1427     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1428     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1429     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1430     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1431     if (!range0.IsMaxRange() || !range1.IsMaxRange()) {
1432         return range0.Mul(range1);
1433     }
1434     return BoundsRange();
1435 }
1436 
CalcNewBoundsRangeDiv(const BoundsRangeInfo * bri,const Inst * inst)1437 BoundsRange BoundsAnalysis::CalcNewBoundsRangeDiv(const BoundsRangeInfo *bri, const Inst *inst)
1438 {
1439     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1440     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1441     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1442     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1443     auto lenArray0 = range0.GetLenArray();
1444 
1445     BoundsRange range = range0.Div(range1);
1446     if (range0.IsNotNegative() && range1.IsNotNegative() && lenArray0 != nullptr) {
1447         range.SetLenArray(lenArray0);
1448     }
1449     return range;
1450 }
1451 
CalcNewBoundsRangeShr(const BoundsRangeInfo * bri,const Inst * inst)1452 BoundsRange BoundsAnalysis::CalcNewBoundsRangeShr(const BoundsRangeInfo *bri, const Inst *inst)
1453 {
1454     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1455     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1456     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1457     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1458     auto lenArray0 = range0.GetLenArray();
1459 
1460     BoundsRange range = range0.Shr(range1, inst->GetType());
1461     if (range0.IsNotNegative() && lenArray0 != nullptr) {
1462         range.SetLenArray(lenArray0);
1463     }
1464     return range;
1465 }
1466 
CalcNewBoundsRangeAShr(const BoundsRangeInfo * bri,const Inst * inst)1467 BoundsRange BoundsAnalysis::CalcNewBoundsRangeAShr(const BoundsRangeInfo *bri, const Inst *inst)
1468 {
1469     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1470     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1471     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1472     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1473     auto lenArray0 = range0.GetLenArray();
1474 
1475     BoundsRange range = range0.AShr(range1, inst->GetType());
1476     if (lenArray0 != nullptr) {
1477         range.SetLenArray(lenArray0);
1478     }
1479     return range;
1480 }
1481 
CalcNewBoundsRangeShl(const BoundsRangeInfo * bri,const Inst * inst)1482 BoundsRange BoundsAnalysis::CalcNewBoundsRangeShl(const BoundsRangeInfo *bri, const Inst *inst)
1483 {
1484     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1485     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1486     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1487     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1488 
1489     return range0.Shl(range1, inst->GetType());
1490 }
1491 
CalcNewBoundsRangeAnd(const BoundsRangeInfo * bri,const Inst * inst)1492 BoundsRange BoundsAnalysis::CalcNewBoundsRangeAnd(const BoundsRangeInfo *bri, const Inst *inst)
1493 {
1494     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1495     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1496     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1497     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1498 
1499     return range0.And(range1);
1500 }
1501 
CheckBoundsRange(const BoundsRangeInfo * bri,const Inst * inst)1502 bool BoundsAnalysis::CheckBoundsRange(const BoundsRangeInfo *bri, const Inst *inst)
1503 {
1504     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1505     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1506     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1507     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1508     return (input0->GetType() != DataType::UINT64 || !range0.IsMaxRange(DataType::UINT64) ||
1509             range0.GetLenArray() != nullptr) &&
1510            (input1->GetType() != DataType::UINT64 || !range1.IsMaxRange(DataType::UINT64) ||
1511             range1.GetLenArray() != nullptr);
1512 }
1513 
1514 template <Opcode OPC>
CalcNewBoundsRangeBinary(GraphVisitor * v,const Inst * inst)1515 void BoundsAnalysis::CalcNewBoundsRangeBinary(GraphVisitor *v, const Inst *inst)
1516 {
1517     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::REFERENCE) {
1518         return;
1519     }
1520     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1521     BoundsRange range;
1522     if (CheckBoundsRange(bri, inst)) {
1523         if constexpr (OPC == Opcode::Add) {  // NOLINT
1524             range = CalcNewBoundsRangeAdd(bri, inst);
1525         } else if constexpr (OPC == Opcode::Sub) {  // NOLINT
1526             range = CalcNewBoundsRangeSub(bri, inst);
1527         } else if constexpr (OPC == Opcode::Mod) {  // NOLINT
1528             range = CalcNewBoundsRangeMod(bri, inst);
1529         } else if constexpr (OPC == Opcode::Mul) {  // NOLINT
1530             range = CalcNewBoundsRangeMul(bri, inst);
1531         } else if constexpr (OPC == Opcode::Div) {  // NOLINT
1532             range = CalcNewBoundsRangeDiv(bri, inst);
1533         } else if constexpr (OPC == Opcode::Shr) {  // NOLINT
1534             range = CalcNewBoundsRangeShr(bri, inst);
1535         } else if constexpr (OPC == Opcode::AShr) {  // NOLINT
1536             range = CalcNewBoundsRangeAShr(bri, inst);
1537         } else if constexpr (OPC == Opcode::Shl) {  // NOLINT
1538             range = CalcNewBoundsRangeShl(bri, inst);
1539         } else if constexpr (OPC == Opcode::And) {
1540             range = CalcNewBoundsRangeAnd(bri, inst);
1541         } else {
1542             UNREACHABLE();
1543         }
1544     }
1545     bri->SetBoundsRange(inst->GetBasicBlock(), inst, range.FitInType(inst->GetType()));
1546 }
1547 
1548 }  // namespace ark::compiler
1549