• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * Copyright (c) 2021-2023 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 #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 panda::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     auto 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     return BoundsRange(left, right);
108 }
109 
110 /**
111  * Subtract from current range.
112  * [x1, x2] - [y1, y2] = [x1 - y2, x2 - y1]
113  */
Sub(const BoundsRange & range) const114 BoundsRange BoundsRange::Sub(const BoundsRange &range) const
115 {
116     auto negRight = (range.GetRight() == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -range.GetRight());
117     auto left = AddWithOverflowCheck(left_, negRight);
118     auto negLeft = (range.GetLeft() == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : -range.GetLeft());
119     auto right = AddWithOverflowCheck(right_, negLeft);
120     return BoundsRange(left, right);
121 }
122 
123 /**
124  * Multiply current range.
125  * [x1, x2] * [y1, y2] = [min(x1y1, x1y2, x2y1, x2y2), max(x1y1, x1y2, x2y1, x2y2)]
126  */
Mul(const BoundsRange & range) const127 BoundsRange BoundsRange::Mul(const BoundsRange &range) const
128 {
129     auto m1 = MulWithOverflowCheck(left_, range.GetLeft());
130     auto m2 = MulWithOverflowCheck(left_, range.GetRight());
131     auto m3 = MulWithOverflowCheck(right_, range.GetLeft());
132     auto m4 = MulWithOverflowCheck(right_, range.GetRight());
133     auto left = std::min(m1, std::min(m2, std::min(m3, m4)));
134     auto right = std::max(m1, std::max(m2, std::max(m3, m4)));
135     return BoundsRange(left, right);
136 }
137 
138 /**
139  * Division current range on constant range.
140  * [x1, x2] / [y, y] = [min(x1/y, x2/y), max(x1/y, x2/y)]
141  */
Div(const BoundsRange & range) const142 BoundsRange BoundsRange::Div(const BoundsRange &range) const
143 {
144     if (range.GetLeft() != range.GetRight() || range.GetLeft() == 0) {
145         return BoundsRange();
146     }
147     auto m1 = DivWithOverflowCheck(left_, range.GetLeft());
148     auto m2 = DivWithOverflowCheck(right_, range.GetLeft());
149     auto left = std::min(m1, m2);
150     auto right = std::max(m1, m2);
151     return BoundsRange(left, right);
152 }
153 
154 /**
155  * Modulus of current range.
156  * mod := max(abs(y1), abs(y2))
157  * [x1, x2] % [y1, y2] = [min(max(x1, -(mod - 1)), 0), max(min(x2, mod - 1), 0)]
158  */
159 /* static */
Mod(const BoundsRange & range)160 BoundsRange BoundsRange::Mod(const BoundsRange &range)
161 {
162     int64_t maxMod = 0;
163     if (range.GetRight() > 0) {
164         maxMod = range.GetRight() - 1;
165     }
166     if (range.GetLeft() == MIN_RANGE_VALUE) {
167         maxMod = MAX_RANGE_VALUE;
168     } else if (range.GetLeft() < 0) {
169         maxMod = std::max(maxMod, -range.GetLeft() - 1);
170     }
171     if (maxMod == 0) {
172         return BoundsRange();
173     }
174     auto left = left_ < 0 ? std::max(left_, -maxMod) : 0;
175     auto right = right_ > 0 ? std::min(right_, maxMod) : 0;
176     return BoundsRange(left, right);
177 }
178 
179 // right shift current range, work only if 'range' is positive constant range
Shr(const BoundsRange & range,DataType::Type type)180 BoundsRange BoundsRange::Shr(const BoundsRange &range, DataType::Type type)
181 {
182     if (!range.IsConst() || range.IsNegative()) {
183         return BoundsRange();
184     }
185     uint64_t sizeMask = DataType::GetTypeSize(type, Arch::NONE) - 1;
186     auto n = static_cast<uint64_t>(range.GetLeft()) & sizeMask;
187     auto narrowed = BoundsRange(*this).FitInType(type);
188     // for fixed n > 0 (x Shr n) is increasing on [MIN_RANGE_VALUE, -1] and
189     // on [0, MAX_RANGE_VALUE], but (-1 Shr n) > (0 Shr n)
190     if (narrowed.GetLeft() < 0 && narrowed.GetRight() >= 0 && n > 0) {
191         auto r = static_cast<int64_t>(~static_cast<uint64_t>(0) >> n);
192         return BoundsRange(0, r);
193     }
194     auto l = static_cast<int64_t>(static_cast<uint64_t>(narrowed.GetLeft()) >> n);
195     auto r = static_cast<int64_t>(static_cast<uint64_t>(narrowed.GetRight()) >> n);
196     return BoundsRange(l, r);
197 }
198 
199 // arithmetic right shift current range, work only if 'range' is positive constant range
AShr(const BoundsRange & range,DataType::Type type)200 BoundsRange BoundsRange::AShr(const BoundsRange &range, DataType::Type type)
201 {
202     if (!range.IsConst() || range.IsNegative()) {
203         return BoundsRange();
204     }
205     uint64_t sizeMask = DataType::GetTypeSize(type, Arch::NONE) - 1;
206     auto n = static_cast<uint64_t>(range.GetLeft()) & sizeMask;
207     // NOLINTNEXTLINE(hicpp-signed-bitwise)
208     return BoundsRange(left_ >> n, right_ >> n);
209 }
210 
211 // left shift current range, work only if 'range' is positive constant range
Shl(const BoundsRange & range,DataType::Type type)212 BoundsRange BoundsRange::Shl(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     if (n > 0) {
220         auto maxBits = BITS_PER_UINT64 - n - 1;
221         auto maxValue = static_cast<int64_t>(static_cast<uint64_t>(1) << maxBits);
222         if (left_ < -maxValue || right_ >= maxValue) {
223             // shift can overflow
224             return BoundsRange();
225         }
226     }
227     auto l = static_cast<int64_t>(static_cast<uint64_t>(left_) << n);
228     auto r = static_cast<int64_t>(static_cast<uint64_t>(right_) << n);
229     return BoundsRange(l, r);
230 }
231 
And(const BoundsRange & range)232 BoundsRange BoundsRange::And(const BoundsRange &range)
233 {
234     if (!range.IsConst()) {
235         return BoundsRange();
236     }
237     uint64_t n = range.GetLeft();
238     static constexpr uint32_t BITS_63 = 63;
239     if ((n >> BITS_63) == 1) {
240         return BoundsRange();
241     }
242     return BoundsRange(0, n);
243 }
244 
IsConst() const245 bool BoundsRange::IsConst() const
246 {
247     return left_ == right_;
248 }
249 
IsMaxRange(DataType::Type type) const250 bool BoundsRange::IsMaxRange(DataType::Type type) const
251 {
252     return left_ <= GetMin(type) && right_ >= GetMax(type);
253 }
254 
IsEqual(const BoundsRange & range) const255 bool BoundsRange::IsEqual(const BoundsRange &range) const
256 {
257     return left_ == range.GetLeft() && right_ == range.GetRight();
258 }
259 
IsLess(const BoundsRange & range) const260 bool BoundsRange::IsLess(const BoundsRange &range) const
261 {
262     return right_ < range.GetLeft();
263 }
264 
IsLess(const Inst * inst) const265 bool BoundsRange::IsLess(const Inst *inst) const
266 {
267     ASSERT(inst != nullptr);
268     if (!IsLenArray(inst)) {
269         return false;
270     }
271     return inst == lenArray_;
272 }
273 
IsMore(const BoundsRange & range) const274 bool BoundsRange::IsMore(const BoundsRange &range) const
275 {
276     return left_ > range.GetRight();
277 }
278 
IsMoreOrEqual(const BoundsRange & range) const279 bool BoundsRange::IsMoreOrEqual(const BoundsRange &range) const
280 {
281     return left_ >= range.GetRight();
282 }
283 
IsNotNegative() const284 bool BoundsRange::IsNotNegative() const
285 {
286     return left_ >= 0;
287 }
288 
IsNegative() const289 bool BoundsRange::IsNegative() const
290 {
291     return right_ < 0;
292 }
293 
IsPositive() const294 bool BoundsRange::IsPositive() const
295 {
296     return left_ > 0;
297 }
298 
IsNotPositive() const299 bool BoundsRange::IsNotPositive() const
300 {
301     return right_ <= 0;
302 }
303 
CanOverflow(DataType::Type type) const304 bool BoundsRange::CanOverflow(DataType::Type type) const
305 {
306     return left_ <= GetMin(type) || right_ >= GetMax(type);
307 }
308 
CanOverflowNeg(DataType::Type type) const309 bool BoundsRange::CanOverflowNeg(DataType::Type type) const
310 {
311     return right_ >= GetMax(type) || (left_ <= 0 && 0 <= right_);
312 }
313 
314 /**
315  * Return the minimal value for a type.
316  *
317  * We consider that REFERENCE type has only non-negative address values
318  */
GetMin(DataType::Type type)319 int64_t BoundsRange::GetMin(DataType::Type type)
320 {
321     ASSERT(!IsFloatType(type));
322     switch (type) {
323         case DataType::BOOL:
324         case DataType::UINT8:
325         case DataType::UINT16:
326         case DataType::UINT32:
327         case DataType::UINT64:
328         case DataType::REFERENCE:
329             return 0;
330         case DataType::INT8:
331             return INT8_MIN;
332         case DataType::INT16:
333             return INT16_MIN;
334         case DataType::INT32:
335             return INT32_MIN;
336         case DataType::INT64:
337             return INT64_MIN;
338         default:
339             UNREACHABLE();
340     }
341 }
342 
343 /**
344  * Return the maximal value for a type.
345  *
346  * For REFERENCE we are interested in whether it is NULL or not.  Set the
347  * maximum to INT64_MAX regardless the real architecture bitness.
348  */
GetMax(DataType::Type type)349 int64_t BoundsRange::GetMax(DataType::Type type)
350 {
351     ASSERT(!IsFloatType(type));
352     ASSERT(type != DataType::UINT64);
353     switch (type) {
354         case DataType::BOOL:
355             return 1;
356         case DataType::UINT8:
357             return UINT8_MAX;
358         case DataType::UINT16:
359             return UINT16_MAX;
360         case DataType::UINT32:
361             return UINT32_MAX;
362         case DataType::INT8:
363             return INT8_MAX;
364         case DataType::INT16:
365             return INT16_MAX;
366         case DataType::INT32:
367             return INT32_MAX;
368         // NOLINTNEXTLINE(bugprone-branch-clone)
369         case DataType::INT64:
370             return INT64_MAX;
371         case DataType::REFERENCE:
372             return INT64_MAX;
373         default:
374             UNREACHABLE();
375     }
376 }
377 
FitInType(DataType::Type type) const378 BoundsRange BoundsRange::FitInType(DataType::Type type) const
379 {
380     auto typeMin = BoundsRange::GetMin(type);
381     auto typeMax = BoundsRange::GetMax(type);
382     if (left_ < typeMin || left_ > typeMax || right_ < typeMin || right_ > typeMax) {
383         return BoundsRange(typeMin, typeMax);
384     }
385     return *this;
386 }
387 
Union(const ArenaVector<BoundsRange> & ranges)388 BoundsRange BoundsRange::Union(const ArenaVector<BoundsRange> &ranges)
389 {
390     int64_t min = MAX_RANGE_VALUE;
391     int64_t max = MIN_RANGE_VALUE;
392     for (const auto &range : ranges) {
393         if (range.GetLeft() < min) {
394             min = range.GetLeft();
395         }
396         if (range.GetRight() > max) {
397             max = range.GetRight();
398         }
399     }
400     return BoundsRange(min, max);
401 }
402 
NarrowBoundsByNE(BoundsRange::RangePair const & ranges)403 BoundsRange::RangePair BoundsRange::NarrowBoundsByNE(BoundsRange::RangePair const &ranges)
404 {
405     auto &[left_range, right_range] = ranges;
406     int64_t ll = left_range.GetLeft();
407     int64_t lr = left_range.GetRight();
408     int64_t rl = right_range.GetLeft();
409     int64_t rr = right_range.GetRight();
410     // We can narrow bounds of a range if another is a constant and matches one of the bounds
411     // Mostly needed for a reference comparison with null
412     if (left_range.IsConst() && !right_range.IsConst()) {
413         if (ll == rl) {
414             return {left_range, BoundsRange(rl + 1, rr)};
415         }
416         if (ll == rr) {
417             return {left_range, BoundsRange(rl, rr - 1)};
418         }
419     }
420     if (!left_range.IsConst() && right_range.IsConst()) {
421         if (rl == ll) {
422             return {BoundsRange(ll + 1, lr), right_range};
423         }
424         if (rl == lr) {
425             return {BoundsRange(ll, lr - 1), right_range};
426         }
427     }
428     return ranges;
429 }
430 
NarrowBoundsCase1(ConditionCode cc,BoundsRange::RangePair const & ranges)431 BoundsRange::RangePair BoundsRange::NarrowBoundsCase1(ConditionCode cc, BoundsRange::RangePair const &ranges)
432 {
433     auto &[left_range, right_range] = ranges;
434     int64_t lr = left_range.GetRight();
435     int64_t rl = right_range.GetLeft();
436     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
437         // With equal rl and lr left_range cannot be greater than right_range
438         if (rl == lr) {
439             return {BoundsRange(), BoundsRange()};
440         }
441         return {BoundsRange(rl + 1, lr), BoundsRange(rl, lr - 1)};
442     }
443     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE || cc == ConditionCode::CC_EQ) {
444         return {BoundsRange(rl, lr), BoundsRange(rl, lr)};
445     }
446     return ranges;
447 }
448 
NarrowBoundsCase2(ConditionCode cc,BoundsRange::RangePair const & ranges)449 BoundsRange::RangePair BoundsRange::NarrowBoundsCase2(ConditionCode cc, BoundsRange::RangePair const &ranges)
450 {
451     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_GE || cc == ConditionCode::CC_EQ ||
452         cc == ConditionCode::CC_A || cc == ConditionCode::CC_AE) {
453         return {BoundsRange(), BoundsRange()};
454     }
455     return ranges;
456 }
457 
NarrowBoundsCase3(ConditionCode cc,BoundsRange::RangePair const & ranges)458 BoundsRange::RangePair BoundsRange::NarrowBoundsCase3(ConditionCode cc, BoundsRange::RangePair const &ranges)
459 {
460     auto &[left_range, right_range] = ranges;
461     int64_t ll = left_range.GetLeft();
462     int64_t lr = left_range.GetRight();
463     int64_t rl = right_range.GetLeft();
464     int64_t rr = right_range.GetRight();
465     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
466         // rl == lr handled in case 1
467         return {BoundsRange(rl + 1, lr), right_range};
468     }
469     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE) {
470         return {BoundsRange(rl, lr), right_range};
471     }
472     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
473         // With equal ll and rr left_range cannot be less than right_range
474         if (ll == rr) {
475             return {BoundsRange(), BoundsRange()};
476         }
477         return {BoundsRange(ll, rr - 1), right_range};
478     }
479     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE) {
480         return {BoundsRange(ll, rr), right_range};
481     }
482     if (cc == ConditionCode::CC_EQ) {
483         return {BoundsRange(rl, rr), right_range};
484     }
485     return ranges;
486 }
487 
NarrowBoundsCase4(ConditionCode cc,BoundsRange::RangePair const & ranges)488 BoundsRange::RangePair BoundsRange::NarrowBoundsCase4(ConditionCode cc, BoundsRange::RangePair const &ranges)
489 {
490     auto &[left_range, right_range] = ranges;
491     int64_t ll = left_range.GetLeft();
492     int64_t rr = right_range.GetRight();
493     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
494         // With equal ll and rr left_range cannot be less than right_range
495         if (ll == rr) {
496             return {BoundsRange(), BoundsRange()};
497         }
498         return {BoundsRange(ll, rr - 1), BoundsRange(ll + 1, rr)};
499     }
500     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE || cc == ConditionCode::CC_EQ) {
501         return {BoundsRange(ll, rr), BoundsRange(ll, rr)};
502     }
503     return ranges;
504 }
505 
NarrowBoundsCase5(ConditionCode cc,BoundsRange::RangePair const & ranges)506 BoundsRange::RangePair BoundsRange::NarrowBoundsCase5(ConditionCode cc, BoundsRange::RangePair const &ranges)
507 {
508     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_LE || cc == ConditionCode::CC_EQ ||
509         cc == ConditionCode::CC_B || cc == ConditionCode::CC_BE) {
510         return {BoundsRange(), BoundsRange()};
511     }
512     return ranges;
513 }
514 
NarrowBoundsCase6(ConditionCode cc,BoundsRange::RangePair const & ranges)515 BoundsRange::RangePair BoundsRange::NarrowBoundsCase6(ConditionCode cc, BoundsRange::RangePair const &ranges)
516 {
517     auto &[left_range, right_range] = ranges;
518     int64_t ll = left_range.GetLeft();
519     int64_t lr = left_range.GetRight();
520     int64_t rl = right_range.GetLeft();
521     int64_t rr = right_range.GetRight();
522     if (cc == ConditionCode::CC_GT || cc == ConditionCode::CC_A) {
523         // rl == lr handled in case 1
524         return {left_range, BoundsRange(rl, lr - 1)};
525     }
526     if (cc == ConditionCode::CC_GE || cc == ConditionCode::CC_AE) {
527         return {left_range, BoundsRange(rl, lr)};
528     }
529     if (cc == ConditionCode::CC_LT || cc == ConditionCode::CC_B) {
530         // ll == rr handled in case 4
531         return {left_range, BoundsRange(ll + 1, rr)};
532     }
533     if (cc == ConditionCode::CC_LE || cc == ConditionCode::CC_BE) {
534         return {left_range, BoundsRange(ll, rr)};
535     }
536     if (cc == ConditionCode::CC_EQ) {
537         return {left_range, BoundsRange(ll, lr)};
538     }
539     return ranges;
540 }
541 
542 /**
543  * Try narrow bounds range for <if (left CC right)> situation
544  * Return a pair of narrowed left and right intervals
545  */
TryNarrowBoundsByCC(ConditionCode cc,BoundsRange::RangePair const & ranges)546 BoundsRange::RangePair BoundsRange::TryNarrowBoundsByCC(ConditionCode cc, BoundsRange::RangePair const &ranges)
547 {
548     if (cc == ConditionCode::CC_NE) {
549         return NarrowBoundsByNE(ranges);
550     }
551     auto &[left_range, right_range] = ranges;
552     int64_t ll = left_range.GetLeft();
553     int64_t lr = left_range.GetRight();
554     int64_t rl = right_range.GetLeft();
555     int64_t rr = right_range.GetRight();
556     // For further description () is for left_range bounds and [] is for right_range bounds
557     // case 1: ( [ ) ]
558     if (ll <= rl && rl <= lr && lr <= rr) {
559         return NarrowBoundsCase1(cc, ranges);
560     }
561     // case 2: ( ) [ ]
562     if (ll <= lr && lr < rl && rl <= rr) {
563         return NarrowBoundsCase2(cc, ranges);
564     }
565     // case 3: ( [ ] )
566     if (ll <= rl && rl <= rr && rr <= lr) {
567         return NarrowBoundsCase3(cc, ranges);
568     }
569     // case 4: [ ( ] )
570     if (rl <= ll && ll <= rr && rr <= lr) {
571         return NarrowBoundsCase4(cc, ranges);
572     }
573     // case 5: [ ] ( )
574     if (rl <= rr && rr < ll && ll <= lr) {
575         return NarrowBoundsCase5(cc, ranges);
576     }
577     // case 6: [ ( ) ]
578     if (rl <= ll && ll <= lr && lr <= rr) {
579         return NarrowBoundsCase6(cc, ranges);
580     }
581     return ranges;
582 }
583 
584 /// Return (left + right) or if overflows or underflows return max or min of range type.
AddWithOverflowCheck(int64_t left,int64_t right)585 int64_t BoundsRange::AddWithOverflowCheck(int64_t left, int64_t right)
586 {
587     if (right == 0) {
588         return left;
589     }
590     if (right > 0) {
591         if (left <= (MAX_RANGE_VALUE - right)) {
592             // No overflow.
593             return left + right;
594         }
595         return MAX_RANGE_VALUE;
596     }
597     if (left >= (MIN_RANGE_VALUE - right)) {
598         // No overflow.
599         return left + right;
600     }
601     return MIN_RANGE_VALUE;
602 }
603 
604 /// Return (left * right) or if overflows or underflows return max or min of range type.
MulWithOverflowCheck(int64_t left,int64_t right)605 int64_t BoundsRange::MulWithOverflowCheck(int64_t left, int64_t right)
606 {
607     if (left == 0 || right == 0) {
608         return 0;
609     }
610     int64_t leftAbs = (left == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(left));
611     int64_t rightAbs = (right == MIN_RANGE_VALUE ? MAX_RANGE_VALUE : std::abs(right));
612     if (leftAbs <= (MAX_RANGE_VALUE / rightAbs)) {
613         // No overflow.
614         return left * right;
615     }
616     if ((right > 0 && left > 0) || (right < 0 && left < 0)) {
617         return MAX_RANGE_VALUE;
618     }
619     return MIN_RANGE_VALUE;
620 }
621 
622 /// Return (left / right) or MIN_RANGE VALUE for MIN_RANGE_VALUE / -1.
DivWithOverflowCheck(int64_t left,int64_t right)623 int64_t BoundsRange::DivWithOverflowCheck(int64_t left, int64_t right)
624 {
625     ASSERT(right != 0);
626     if (left == MIN_RANGE_VALUE && right == -1) {
627         return MIN_RANGE_VALUE;
628     }
629     return left / right;
630 }
631 
FindBoundsRange(const BasicBlock * block,const Inst * inst) const632 BoundsRange BoundsRangeInfo::FindBoundsRange(const BasicBlock *block, const Inst *inst) const
633 {
634     ASSERT(block != nullptr && inst != nullptr);
635     ASSERT(!IsFloatType(inst->GetType()));
636     ASSERT(inst->GetType() == DataType::REFERENCE || DataType::GetCommonType(inst->GetType()) == DataType::INT64);
637     if (inst->GetOpcode() == Opcode::NullPtr) {
638         ASSERT(inst->GetType() == DataType::REFERENCE);
639         return BoundsRange(0);
640     }
641     if (IsInstNotNull(inst)) {
642         ASSERT(inst->GetType() == DataType::REFERENCE);
643         return BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
644     }
645     while (block != nullptr) {
646         if (boundsRangeInfo_.find(block) != boundsRangeInfo_.end() &&
647             boundsRangeInfo_.at(block).find(inst) != boundsRangeInfo_.at(block).end()) {
648             return boundsRangeInfo_.at(block).at(inst);
649         }
650         block = block->GetDominator();
651     }
652     // BoundsRange for constant can have len_array, so we should process it after the loop above
653     if (inst->IsConst()) {
654         ASSERT(inst->GetType() == DataType::INT64);
655         auto val = static_cast<int64_t>(inst->CastToConstant()->GetIntValue());
656         return BoundsRange(val);
657     }
658     if (IsLenArray(inst)) {
659         ASSERT(inst->GetType() == DataType::INT32);
660         auto maxLength = INT32_MAX;
661         if (inst->GetOpcode() == Opcode::LenArray) {
662             auto arrayInst = inst->CastToLenArray()->GetDataFlowInput(0);
663             auto typeInfo = arrayInst->GetObjectTypeInfo();
664             if (typeInfo) {
665                 auto klass = typeInfo.GetClass();
666                 auto runtime = inst->GetBasicBlock()->GetGraph()->GetRuntime();
667                 maxLength = runtime->GetMaxArrayLength(klass);
668             }
669         }
670         return BoundsRange(0, maxLength, nullptr, inst->GetType());
671     }
672     // if we know nothing about inst return the complete range of type
673     return BoundsRange(inst->GetType());
674 }
675 
SetBoundsRange(const BasicBlock * block,const Inst * inst,BoundsRange range)676 void BoundsRangeInfo::SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range)
677 {
678     if (inst->IsConst() && range.GetLenArray() == nullptr) {
679         return;
680     }
681     if (inst->IsConst()) {
682         auto val = static_cast<int64_t>(static_cast<const ConstantInst *>(inst)->GetIntValue());
683         range = BoundsRange(val, val, range.GetLenArray());
684     }
685     ASSERT(inst->GetType() == DataType::REFERENCE || DataType::GetCommonType(inst->GetType()) == DataType::INT64);
686     ASSERT(range.GetLeft() >= BoundsRange::GetMin(inst->GetType()));
687     ASSERT(range.GetRight() <= BoundsRange::GetMax(inst->GetType()));
688     if (!range.IsMaxRange() || range.GetLenArray() != nullptr) {
689         if (boundsRangeInfo_.find(block) == boundsRangeInfo_.end()) {
690             auto it1 = boundsRangeInfo_.emplace(block, aa_.Adapter());
691             ASSERT(it1.second);
692             it1.first->second.emplace(inst, range);
693         } else if (boundsRangeInfo_.at(block).find(inst) == boundsRangeInfo_.at(block).end()) {
694             boundsRangeInfo_.at(block).emplace(inst, range);
695         } else {
696             boundsRangeInfo_.at(block).at(inst) = range;
697         }
698     }
699 }
700 
BoundsAnalysis(Graph * graph)701 BoundsAnalysis::BoundsAnalysis(Graph *graph) : Analysis(graph), boundsRangeInfo_(graph->GetAllocator()) {}
702 
RunImpl()703 bool BoundsAnalysis::RunImpl()
704 {
705     ASSERT(!GetGraph()->IsBytecodeOptimizer());
706     boundsRangeInfo_.Clear();
707 
708     GetGraph()->RunPass<DominatorsTree>();
709     GetGraph()->RunPass<LoopAnalyzer>();
710 
711     VisitGraph();
712 
713     return true;
714 }
715 
IsInstNotNull(const Inst * inst,BasicBlock * block)716 bool BoundsAnalysis::IsInstNotNull(const Inst *inst, BasicBlock *block)
717 {
718     if (compiler::IsInstNotNull(inst)) {
719         return true;
720     }
721     auto bri = block->GetGraph()->GetBoundsRangeInfo();
722     auto range = bri->FindBoundsRange(block, inst);
723     return range.IsMore(BoundsRange(0));
724 }
725 
GetBlocksToVisit() const726 const ArenaVector<BasicBlock *> &BoundsAnalysis::GetBlocksToVisit() const
727 {
728     return GetGraph()->GetBlocksRPO();
729 }
730 
VisitNeg(GraphVisitor * v,Inst * inst)731 void BoundsAnalysis::VisitNeg(GraphVisitor *v, Inst *inst)
732 {
733     CalcNewBoundsRangeUnary<Opcode::Neg>(v, inst);
734 }
735 
VisitNegOverflowAndZeroCheck(GraphVisitor * v,Inst * inst)736 void BoundsAnalysis::VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst)
737 {
738     CalcNewBoundsRangeUnary<Opcode::Neg>(v, inst);
739 }
740 
VisitAbs(GraphVisitor * v,Inst * inst)741 void BoundsAnalysis::VisitAbs(GraphVisitor *v, Inst *inst)
742 {
743     CalcNewBoundsRangeUnary<Opcode::Abs>(v, inst);
744 }
745 
VisitAdd(GraphVisitor * v,Inst * inst)746 void BoundsAnalysis::VisitAdd(GraphVisitor *v, Inst *inst)
747 {
748     CalcNewBoundsRangeBinary<Opcode::Add>(v, inst);
749 }
750 
VisitAddOverflowCheck(GraphVisitor * v,Inst * inst)751 void BoundsAnalysis::VisitAddOverflowCheck(GraphVisitor *v, Inst *inst)
752 {
753     CalcNewBoundsRangeBinary<Opcode::Add>(v, inst);
754 }
755 
VisitSub(GraphVisitor * v,Inst * inst)756 void BoundsAnalysis::VisitSub(GraphVisitor *v, Inst *inst)
757 {
758     CalcNewBoundsRangeBinary<Opcode::Sub>(v, inst);
759 }
760 
VisitSubOverflowCheck(GraphVisitor * v,Inst * inst)761 void BoundsAnalysis::VisitSubOverflowCheck(GraphVisitor *v, Inst *inst)
762 {
763     CalcNewBoundsRangeBinary<Opcode::Sub>(v, inst);
764 }
765 
VisitMod(GraphVisitor * v,Inst * inst)766 void BoundsAnalysis::VisitMod(GraphVisitor *v, Inst *inst)
767 {
768     CalcNewBoundsRangeBinary<Opcode::Mod>(v, inst);
769 }
770 
VisitDiv(GraphVisitor * v,Inst * inst)771 void BoundsAnalysis::VisitDiv(GraphVisitor *v, Inst *inst)
772 {
773     CalcNewBoundsRangeBinary<Opcode::Div>(v, inst);
774 }
775 
VisitMul(GraphVisitor * v,Inst * inst)776 void BoundsAnalysis::VisitMul(GraphVisitor *v, Inst *inst)
777 {
778     CalcNewBoundsRangeBinary<Opcode::Mul>(v, inst);
779 }
780 
VisitAnd(GraphVisitor * v,Inst * inst)781 void BoundsAnalysis::VisitAnd(GraphVisitor *v, Inst *inst)
782 {
783     CalcNewBoundsRangeBinary<Opcode::And>(v, inst);
784 }
785 
VisitShr(GraphVisitor * v,Inst * inst)786 void BoundsAnalysis::VisitShr(GraphVisitor *v, Inst *inst)
787 {
788     CalcNewBoundsRangeBinary<Opcode::Shr>(v, inst);
789 }
790 
791 // check that AShr is div, if it's true calc range as div, if not like AShr.
792 // Note: div can be replaced by ashr + shr + add + ashr in Peepholes::TryReplaceDivByShrAndAshr
VisitAShr(GraphVisitor * v,Inst * inst)793 void BoundsAnalysis::VisitAShr(GraphVisitor *v, Inst *inst)
794 {
795     auto typeSize = DataType::GetTypeSize(inst->GetType(), inst->GetBasicBlock()->GetGraph()->GetArch());
796     bool isDiv = true;
797     uint64_t n = 0;
798     Inst *x = nullptr;
799     auto add = inst->GetInput(0).GetInst();
800     auto cnst = inst->GetInput(1).GetInst();
801     isDiv &= cnst->IsConst() && add->GetOpcode() == Opcode::Add;
802     if (isDiv) {
803         n = cnst->CastToConstant()->GetInt64Value();
804         auto shr = add->GetInput(0).GetInst();
805         x = add->GetInput(1).GetInst();
806         isDiv &= shr->GetOpcode() == Opcode::Shr;
807         if (isDiv) {
808             auto ashr = shr->GetInput(0).GetInst();
809             cnst = shr->GetInput(1).GetInst();
810             isDiv &= ashr->GetOpcode() == Opcode::AShr && cnst->IsConst() &&
811                      cnst->CastToConstant()->GetInt64Value() == (typeSize - n);
812             if (isDiv) {
813                 isDiv &= ashr->GetInput(0).GetInst() == x;
814                 cnst = ashr->GetInput(1).GetInst();
815                 isDiv &= cnst->IsConst() && cnst->CastToConstant()->GetInt64Value() == (typeSize - 1U);
816             }
817         }
818     }
819     if (isDiv) {
820         auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
821         auto range = bri->FindBoundsRange(inst->GetBasicBlock(), x);
822         auto lenArray = range.GetLenArray();
823         auto res = range.Div(BoundsRange(1U << n));
824         if (range.IsNotNegative() && lenArray != nullptr) {
825             res.SetLenArray(lenArray);
826         }
827         bri->SetBoundsRange(inst->GetBasicBlock(), inst, res);
828         return;
829     }
830     CalcNewBoundsRangeBinary<Opcode::AShr>(v, inst);
831 }
832 
VisitShl(GraphVisitor * v,Inst * inst)833 void BoundsAnalysis::VisitShl(GraphVisitor *v, Inst *inst)
834 {
835     CalcNewBoundsRangeBinary<Opcode::Shl>(v, inst);
836 }
837 
VisitIfImm(GraphVisitor * v,Inst * inst)838 void BoundsAnalysis::VisitIfImm(GraphVisitor *v, Inst *inst)
839 {
840     auto ifInst = inst->CastToIfImm();
841     if (ifInst->GetOperandsType() != DataType::BOOL) {
842         return;
843     }
844     ASSERT(ifInst->GetCc() == ConditionCode::CC_NE || ifInst->GetCc() == ConditionCode::CC_EQ);
845     ASSERT(ifInst->GetImm() == 0);
846 
847     auto input = inst->GetInput(0).GetInst();
848     if (input->GetOpcode() == Opcode::IsInstance) {
849         CalcNewBoundsRangeForIsInstanceInput(v, input->CastToIsInstance(), ifInst);
850         return;
851     }
852     if (input->GetOpcode() != Opcode::Compare) {
853         return;
854     }
855     auto compare = input->CastToCompare();
856     if (compare->GetOperandsType() == DataType::UINT64) {
857         return;
858     }
859     auto op0 = compare->GetInput(0).GetInst();
860     auto op1 = compare->GetInput(1).GetInst();
861     if ((DataType::GetCommonType(op0->GetType()) != DataType::INT64 && op0->GetType() != DataType::REFERENCE) ||
862         (DataType::GetCommonType(op1->GetType()) != DataType::INT64 && op1->GetType() != DataType::REFERENCE)) {
863         return;
864     }
865 
866     auto cc = compare->GetCc();
867     auto block = inst->GetBasicBlock();
868     BasicBlock *trueBlock;
869     BasicBlock *falseBlock;
870     if (ifInst->GetCc() == ConditionCode::CC_NE) {
871         // Corresponds to Compare result
872         trueBlock = block->GetTrueSuccessor();
873         falseBlock = block->GetFalseSuccessor();
874     } else if (ifInst->GetCc() == ConditionCode::CC_EQ) {
875         // Corresponds to inversion of Compare result
876         trueBlock = block->GetFalseSuccessor();
877         falseBlock = block->GetTrueSuccessor();
878     } else {
879         UNREACHABLE();
880     }
881     CalcNewBoundsRangeForCompare(v, block, cc, op0, op1, trueBlock);
882     CalcNewBoundsRangeForCompare(v, block, GetInverseConditionCode(cc), op0, op1, falseBlock);
883 }
884 
VisitPhi(GraphVisitor * v,Inst * inst)885 void BoundsAnalysis::VisitPhi(GraphVisitor *v, Inst *inst)
886 {
887     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::UINT64 || inst->GetType() == DataType::ANY ||
888         inst->GetType() == DataType::POINTER) {
889         return;
890     }
891     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
892     auto phi = inst->CastToPhi();
893     if (inst->GetType() != DataType::REFERENCE && ProcessCountableLoop(phi, bri)) {
894         return;
895     }
896     auto phiBlock = phi->GetBasicBlock();
897     ArenaVector<BoundsRange> ranges(phiBlock->GetGraph()->GetLocalAllocator()->Adapter());
898     for (auto &block : phiBlock->GetPredsBlocks()) {
899         ranges.emplace_back(bri->FindBoundsRange(block, phi->GetPhiInput(block)));
900     }
901     bri->SetBoundsRange(phiBlock, phi, BoundsRange::Union(ranges).FitInType(phi->GetType()));
902 }
903 
VisitNullCheck(GraphVisitor * v,Inst * inst)904 void BoundsAnalysis::VisitNullCheck(GraphVisitor *v, Inst *inst)
905 {
906     ProcessNullCheck(v, inst, inst->GetDataFlowInput(0));
907 }
908 
ProcessCountableLoop(PhiInst * phi,BoundsRangeInfo * bri)909 bool BoundsAnalysis::ProcessCountableLoop(PhiInst *phi, BoundsRangeInfo *bri)
910 {
911     auto phiBlock = phi->GetBasicBlock();
912     auto phiType = phi->GetType();
913     auto loop = phiBlock->GetLoop();
914     auto loopParser = CountableLoopParser(*loop);
915     auto loopInfo = loopParser.Parse();
916     // check that loop is countable and phi is index
917     if (!loopInfo || phi != loopInfo->index) {
918         return false;
919     }
920     auto loopInfoValue = loopInfo.value();
921     ASSERT(loopInfoValue.update->IsAddSub());
922     auto lower = loopInfoValue.init;
923     auto upper = loopInfoValue.test;
924     auto cc = loopInfoValue.normalizedCc;
925     ASSERT(cc == CC_LE || cc == CC_LT || cc == CC_GE || cc == CC_GT);
926     if (!loopInfoValue.isInc) {
927         lower = loopInfoValue.test;
928         upper = loopInfoValue.init;
929     }
930     auto lowerRange = bri->FindBoundsRange(phiBlock, lower);
931     auto upperRange = bri->FindBoundsRange(phiBlock, upper);
932     if (cc == CC_GT) {
933         lowerRange = lowerRange.Add(BoundsRange(1));
934     } else if (cc == CC_LT) {
935         upperRange = upperRange.Sub(BoundsRange(1));
936         if (IsLenArray(upper)) {
937             upperRange.SetLenArray(upper);
938         }
939     }
940     if (lowerRange.GetLeft() > upperRange.GetRight()) {
941         return false;
942     }
943     auto left = lowerRange.GetLeft();
944     auto right = upperRange.GetRight();
945     auto lenArray = upperRange.GetLenArray();
946     auto isHeadLoopExit = loopInfoValue.ifImm->GetBasicBlock() == loop->GetHeader();
947     if (!upperRange.IsMoreOrEqual(lowerRange) && !isHeadLoopExit) {
948         return false;
949     }
950     if (!upperRange.IsMoreOrEqual(lowerRange) && !CountableLoopParser::HasPreHeaderCompare(loop, loopInfoValue)) {
951         ASSERT(phiBlock == loop->GetHeader());
952         if (loopInfoValue.ifImm->GetBasicBlock() == phiBlock) {
953             auto nextLoopBlock = phiBlock->GetTrueSuccessor();
954             if (nextLoopBlock->GetLoop() != loop && !nextLoopBlock->GetLoop()->IsInside(loop)) {
955                 nextLoopBlock = phiBlock->GetFalseSuccessor();
956                 ASSERT(nextLoopBlock->GetLoop() == loop || nextLoopBlock->GetLoop()->IsInside(loop));
957             }
958             if (nextLoopBlock != phiBlock) {
959                 auto range = BoundsRange(left, right, lenArray);
960                 bri->SetBoundsRange(nextLoopBlock, phi, range.FitInType(phiType));
961             }
962         }
963         // index can be more (less) than loop bound on first iteration
964         if (cc == CC_LE || cc == CC_LT) {
965             right = std::max(right, lowerRange.GetRight());
966             lenArray = nullptr;
967         } else {
968             left = std::min(left, upperRange.GetLeft());
969         }
970     }
971     auto range = BoundsRange(left, right, lenArray);
972     bri->SetBoundsRange(phiBlock, phi, range.FitInType(phiType));
973     return true;
974 }
975 
CheckTriangleCase(const BasicBlock * block,const BasicBlock * tgtBlock)976 bool BoundsAnalysis::CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgtBlock)
977 {
978     auto &predsBlocks = tgtBlock->GetPredsBlocks();
979     auto loop = tgtBlock->GetLoop();
980     auto &backEdges = loop->GetBackEdges();
981     if (predsBlocks.size() == 1) {
982         return true;
983     }
984     if (!loop->IsRoot() && backEdges.size() == 1 && predsBlocks.size() == 2U) {
985         if (predsBlocks[0] == block && predsBlocks[1] == backEdges[0]) {
986             return true;
987         }
988         if (predsBlocks[1] == block && predsBlocks[0] == backEdges[0]) {
989             return true;
990         }
991         return false;
992     }
993     return false;
994 }
995 
ProcessNullCheck(GraphVisitor * v,const Inst * checkInst,const Inst * refInput)996 void BoundsAnalysis::ProcessNullCheck(GraphVisitor *v, const Inst *checkInst, const Inst *refInput)
997 {
998     ASSERT(checkInst->IsNullCheck() || checkInst->GetOpcode() == Opcode::DeoptimizeIf);
999     ASSERT(refInput->GetType() == DataType::REFERENCE);
1000     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1001     auto block = checkInst->GetBasicBlock();
1002     auto range = BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
1003     for (auto domBlock : block->GetDominatedBlocks()) {
1004         bri->SetBoundsRange(domBlock, refInput, range);
1005     }
1006 }
1007 
CalcNewBoundsRangeForIsInstanceInput(GraphVisitor * v,IsInstanceInst * isInstance,IfImmInst * ifImm)1008 void BoundsAnalysis::CalcNewBoundsRangeForIsInstanceInput(GraphVisitor *v, IsInstanceInst *isInstance, IfImmInst *ifImm)
1009 {
1010     ASSERT(isInstance == ifImm->GetInput(0).GetInst());
1011     auto block = ifImm->GetBasicBlock();
1012     auto trueBlock = ifImm->GetEdgeIfInputTrue();
1013     if (CheckTriangleCase(block, trueBlock)) {
1014         auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1015         auto ref = isInstance->GetInput(0).GetInst();
1016         // if IsInstance evaluates to True, its input is not null
1017         auto range = BoundsRange(1, BoundsRange::GetMax(DataType::REFERENCE));
1018         bri->SetBoundsRange(trueBlock, ref, range);
1019     }
1020 }
1021 
CalcNewBoundsRangeForCompare(GraphVisitor * v,BasicBlock * block,ConditionCode cc,Inst * left,Inst * right,BasicBlock * tgtBlock)1022 void BoundsAnalysis::CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, Inst *left,
1023                                                   Inst *right, BasicBlock *tgtBlock)
1024 {
1025     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1026     auto leftRange = bri->FindBoundsRange(block, left);
1027     auto rightRange = bri->FindBoundsRange(block, right);
1028     // try to skip triangle:
1029     /* [block]
1030      *    |  \
1031      *    |   \
1032      *    |   [BB]
1033      *    |   /
1034      *    |  /
1035      * [tgt_block]
1036      */
1037     if (CheckTriangleCase(block, tgtBlock)) {
1038         auto ranges = BoundsRange::TryNarrowBoundsByCC(cc, {leftRange, rightRange});
1039         if (cc == ConditionCode::CC_LT && IsLenArray(right)) {
1040             ranges.first.SetLenArray(right);
1041         } else if (cc == ConditionCode::CC_GT && IsLenArray(left)) {
1042             ranges.second.SetLenArray(left);
1043         } else if (leftRange.GetLenArray() != nullptr) {
1044             ranges.first.SetLenArray(leftRange.GetLenArray());
1045         } else if (rightRange.GetLenArray() != nullptr) {
1046             ranges.second.SetLenArray(rightRange.GetLenArray());
1047         }
1048         bri->SetBoundsRange(tgtBlock, left, ranges.first.FitInType(left->GetType()));
1049         bri->SetBoundsRange(tgtBlock, right, ranges.second.FitInType(right->GetType()));
1050     }
1051 }
1052 
1053 template <Opcode OPC>
CalcNewBoundsRangeUnary(GraphVisitor * v,const Inst * inst)1054 void BoundsAnalysis::CalcNewBoundsRangeUnary(GraphVisitor *v, const Inst *inst)
1055 {
1056     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::REFERENCE || inst->GetType() == DataType::UINT64) {
1057         return;
1058     }
1059     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1060     auto input0 = inst->GetInput(0).GetInst();
1061     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1062     BoundsRange range;
1063     // clang-format off
1064         // NOLINTNEXTLINE(readability-braces-around-statements)
1065         if constexpr (OPC == Opcode::Neg) {
1066             range = range0.Neg();
1067         // NOLINTNEXTLINE(readability-braces-around-statements, readability-misleading-indentation)
1068         } else if constexpr (OPC == Opcode::Abs) {
1069             range = range0.Abs();
1070         } else {
1071             UNREACHABLE();
1072         }
1073     // clang-format on
1074     bri->SetBoundsRange(inst->GetBasicBlock(), inst, range.FitInType(inst->GetType()));
1075 }
1076 
1077 template <Opcode OPC>
CalcNewBoundsRangeBinary(GraphVisitor * v,const Inst * inst)1078 void BoundsAnalysis::CalcNewBoundsRangeBinary(GraphVisitor *v, const Inst *inst)
1079 {
1080     if (IsFloatType(inst->GetType()) || inst->GetType() == DataType::REFERENCE || inst->GetType() == DataType::UINT64) {
1081         return;
1082     }
1083     auto bri = static_cast<BoundsAnalysis *>(v)->GetBoundsRangeInfo();
1084     auto input0 = inst->GetDataFlowInput(inst->GetInput(0).GetInst());
1085     auto input1 = inst->GetDataFlowInput(inst->GetInput(1).GetInst());
1086     auto range0 = bri->FindBoundsRange(inst->GetBasicBlock(), input0);
1087     auto range1 = bri->FindBoundsRange(inst->GetBasicBlock(), input1);
1088     auto lenArray0 = range0.GetLenArray();
1089     auto lenArray1 = range1.GetLenArray();
1090     BoundsRange range;
1091     if constexpr (OPC == Opcode::Add) {  // NOLINT
1092         range = range0.Add(range1);
1093         if (!range.IsMaxRange(inst->GetType())) {
1094             if (BoundsRange(0).IsMoreOrEqual(range1) && lenArray0 != nullptr) {
1095                 range.SetLenArray(lenArray0);
1096             } else if (BoundsRange(0).IsMoreOrEqual(range0) && lenArray1 != nullptr) {
1097                 range.SetLenArray(lenArray1);
1098             } else if (IsLenArray(input0) && range1.IsNegative()) {
1099                 range.SetLenArray(input0);
1100             } else if (IsLenArray(input1) && range0.IsNegative()) {
1101                 range.SetLenArray(input1);
1102             }
1103         }
1104     } else if constexpr (OPC == Opcode::Sub) {  // NOLINT
1105         range = range0.Sub(range1);
1106         if (!range.IsMaxRange(inst->GetType())) {
1107             if (range1.IsNotNegative() && lenArray0 != nullptr) {
1108                 range.SetLenArray(lenArray0);
1109             } else if (IsLenArray(input0) && range1.IsMore(BoundsRange(0))) {
1110                 range.SetLenArray(input0);
1111             }
1112         }
1113     } else if constexpr (OPC == Opcode::Mod) {  // NOLINT
1114         range = range0.Mod(range1);
1115         if (lenArray1 != nullptr && range1.IsNotNegative()) {
1116             range.SetLenArray(lenArray1);
1117         } else if (lenArray0 != nullptr) {
1118             // a % b always has the same sign as a, so if a < LenArray, then (a % b) < LenArray
1119             range.SetLenArray(lenArray0);
1120         } else if (IsLenArray(input1)) {
1121             range.SetLenArray(input1);
1122         }
1123     } else if constexpr (OPC == Opcode::Mul) {  // NOLINT
1124         if (!range0.IsMaxRange() || !range1.IsMaxRange()) {
1125             range = range0.Mul(range1);
1126         }
1127     } else if constexpr (OPC == Opcode::Div) {  // NOLINT
1128         range = range0.Div(range1);
1129         if (range0.IsNotNegative() && range1.IsNotNegative() && lenArray0 != nullptr) {
1130             range.SetLenArray(lenArray0);
1131         }
1132     } else if constexpr (OPC == Opcode::Shr) {  // NOLINT
1133         range = range0.Shr(range1, inst->GetType());
1134         if (range0.IsNotNegative() && lenArray0 != nullptr) {
1135             range.SetLenArray(lenArray0);
1136         }
1137     } else if constexpr (OPC == Opcode::AShr) {  // NOLINT
1138         range = range0.AShr(range1, inst->GetType());
1139         if (lenArray0 != nullptr) {
1140             range.SetLenArray(lenArray0);
1141         }
1142     } else if constexpr (OPC == Opcode::Shl) {  // NOLINT
1143         range = range0.Shl(range1, inst->GetType());
1144     } else if constexpr (OPC == Opcode::And) {
1145         range = range0.And(range1);
1146     } else {
1147         UNREACHABLE();
1148     }
1149     // clang on
1150     bri->SetBoundsRange(inst->GetBasicBlock(), inst, range.FitInType(inst->GetType()));
1151 }
1152 
1153 }  // namespace panda::compiler
1154