1 /* 2 * Copyright (c) 2021-2025 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 #ifndef COMPILER_OPTIMIZER_ANALYSIS_BOUNDSRANGE_ANALYSIS_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_BOUNDSRANGE_ANALYSIS_H 18 19 #include "optimizer/analysis/countable_loop_parser.h" 20 #include "optimizer/ir/graph_visitor.h" 21 #include "optimizer/ir/datatype.h" 22 #include "optimizer/ir/inst.h" 23 #include "optimizer/pass.h" 24 #include "utils/arena_containers.h" 25 26 namespace ark::compiler { 27 /** 28 * Represents a range of values that a variable might have. 29 * 30 * It is used to represent variables of integral types according to their size 31 * and sign. 32 * It is used for REFERENCE type as well but only for reasoning whether a 33 * variable is NULL or not. 34 */ 35 class BoundsRange { 36 public: 37 using RangePair = std::pair<BoundsRange, BoundsRange>; 38 left_(GetMin (type))39 explicit BoundsRange(DataType::Type type = DataType::INT64) : left_(GetMin(type)), right_(GetMax(type)) {}; 40 41 explicit BoundsRange(int64_t left, int64_t right, const Inst *inst = nullptr, 42 DataType::Type type = DataType::INT64); 43 44 explicit BoundsRange(int64_t val, DataType::Type type = DataType::INT64); 45 46 DEFAULT_COPY_SEMANTIC(BoundsRange); 47 DEFAULT_MOVE_SEMANTIC(BoundsRange); 48 ~BoundsRange() = default; 49 50 void SetLenArray(const Inst *inst); 51 GetLenArray()52 const Inst *GetLenArray() 53 { 54 return lenArray_; 55 } 56 SetRange(int64_t left,int64_t right)57 void SetRange(int64_t left, int64_t right) 58 { 59 left_ = left; 60 right_ = right; 61 } 62 SetActualLengthLoop(Loop * loop)63 void SetActualLengthLoop(Loop *loop) 64 { 65 actualLengthLoop_ = loop; 66 } 67 GetActualLengthLoop()68 Loop *GetActualLengthLoop() const 69 { 70 return actualLengthLoop_; 71 } 72 HasActualLengthLoop()73 bool HasActualLengthLoop() const 74 { 75 return actualLengthLoop_ != nullptr; 76 } 77 IsWithinActualLengthRange()78 bool IsWithinActualLengthRange() const 79 { 80 return HasActualLengthLoop() && GetLeft() >= 0 && GetRight() < ACTUAL_LENGTH_VALUE; 81 } 82 83 int64_t GetLeft() const; 84 85 int64_t GetRight() const; 86 87 BoundsRange FitInType(DataType::Type type) const; 88 89 BoundsRange Neg() const; 90 91 BoundsRange Abs() const; 92 93 BoundsRange Add(const BoundsRange &range) const; 94 95 BoundsRange Sub(const BoundsRange &range) const; 96 97 BoundsRange Mul(const BoundsRange &range) const; 98 99 BoundsRange Div(const BoundsRange &range) const; 100 101 BoundsRange Mod(const BoundsRange &range); 102 103 BoundsRange And(const BoundsRange &range); 104 105 BoundsRange Shr(const BoundsRange &range, DataType::Type type = DataType::INT64); 106 107 BoundsRange AShr(const BoundsRange &range, DataType::Type type = DataType::INT64); 108 109 BoundsRange Shl(const BoundsRange &range, DataType::Type type = DataType::INT64); 110 111 BoundsRange Diff(const BoundsRange &range) const; 112 113 bool IsConst() const; 114 115 bool IsMaxRange(DataType::Type type = DataType::INT64) const; 116 117 bool IsEqual(const BoundsRange &range) const; 118 119 bool IsLess(const BoundsRange &range) const; 120 121 bool IsLess(const Inst *inst) const; 122 123 bool IsMore(const BoundsRange &range) const; 124 125 bool IsMoreOrEqual(const BoundsRange &range) const; 126 127 bool IsWithin(const BoundsRange &range) const; 128 129 bool IsNotNegative() const; 130 131 bool IsNegative() const; 132 133 bool IsPositive() const; 134 135 bool IsNotPositive() const; 136 137 bool CanOverflow(DataType::Type type = DataType::INT64) const; 138 139 bool CanOverflowNeg(DataType::Type type = DataType::INT64) const; 140 141 static int64_t GetMin(DataType::Type type); 142 143 static int64_t GetMax(DataType::Type type); 144 145 static BoundsRange Union(const ArenaVector<BoundsRange> &ranges); 146 147 static RangePair NarrowBoundsByNE(RangePair const &ranges); 148 static RangePair NarrowBoundsCase1(ConditionCode cc, RangePair const &ranges); 149 static RangePair NarrowBoundsCase2(ConditionCode cc, RangePair const &ranges); 150 static RangePair NarrowBoundsCase3(ConditionCode cc, RangePair const &ranges); 151 static RangePair NarrowBoundsCase4(ConditionCode cc, RangePair const &ranges); 152 static RangePair NarrowBoundsCase5(ConditionCode cc, RangePair const &ranges); 153 static RangePair NarrowBoundsCase6(ConditionCode cc, RangePair const &ranges); 154 155 static RangePair TryNarrowBoundsByCC(ConditionCode cc, RangePair const &ranges); 156 157 static std::optional<int64_t> AddWithOverflowCheck(int64_t left, int64_t right); 158 static std::optional<uint64_t> AddWithOverflowCheck(uint64_t left, uint64_t right); 159 160 static std::optional<int64_t> MulWithOverflowCheck(int64_t left, int64_t right); 161 static std::optional<uint64_t> MulWithOverflowCheck(uint64_t left, uint64_t right); 162 163 static std::optional<int64_t> DivWithOverflowCheck(int64_t left, int64_t right); 164 165 static constexpr int64_t MAX_RANGE_VALUE = INT64_MAX; 166 static constexpr int64_t MIN_RANGE_VALUE = INT64_MIN; 167 static constexpr int64_t ACTUAL_LENGTH_VALUE = INT32_MAX; 168 169 bool operator==(const BoundsRange &rhs) const 170 { 171 return left_ == rhs.left_ && right_ == rhs.right_ && lenArray_ == rhs.lenArray_; 172 } 173 174 void Dump(std::ostream &out = std::cerr) const 175 { 176 out << "Range = [" << left_ << ", "; 177 out << right_ << "]"; 178 if (lenArray_ != nullptr) { 179 out << ", len_array = " << lenArray_->GetId(); 180 } 181 if (actualLengthLoop_ != nullptr) { 182 out << ", actual_length_loop = " << actualLengthLoop_; 183 } 184 out << "\n"; 185 } 186 187 private: 188 int64_t left_ = MIN_RANGE_VALUE; 189 int64_t right_ = MAX_RANGE_VALUE; 190 const Inst *lenArray_ {nullptr}; 191 Loop *actualLengthLoop_ {nullptr}; 192 }; 193 194 class BoundsRangeInfo { 195 public: BoundsRangeInfo(ArenaAllocator * aa)196 explicit BoundsRangeInfo(ArenaAllocator *aa) : aa_(*aa), boundsRangeInfo_(aa->Adapter()) {} 197 NO_COPY_SEMANTIC(BoundsRangeInfo); 198 NO_MOVE_SEMANTIC(BoundsRangeInfo); 199 ~BoundsRangeInfo() = default; 200 201 BoundsRange FindBoundsRange(const BasicBlock *block, const Inst *inst) const; 202 203 void SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range); 204 Clear()205 void Clear() 206 { 207 boundsRangeInfo_.clear(); 208 } 209 210 private: 211 ArenaAllocator &aa_; 212 ArenaDoubleUnorderedMap<const BasicBlock *, const Inst *, BoundsRange> boundsRangeInfo_; 213 }; 214 215 // index phi, iterations 216 using LoopIterationsInfo = std::pair<CountableLoopInfo, uint64_t>; 217 218 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 219 class BoundsAnalysis : public Analysis, public GraphVisitor { 220 public: 221 using InstPair = std::pair<Inst *, Inst *>; 222 223 explicit BoundsAnalysis(Graph *graph); 224 NO_MOVE_SEMANTIC(BoundsAnalysis); 225 NO_COPY_SEMANTIC(BoundsAnalysis); 226 ~BoundsAnalysis() override = default; 227 228 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override; 229 230 bool RunImpl() override; 231 GetPassName()232 const char *GetPassName() const override 233 { 234 return "BoundsAnalysis"; 235 } 236 GetBoundsRangeInfo()237 BoundsRangeInfo *GetBoundsRangeInfo() 238 { 239 return &boundsRangeInfo_; 240 } 241 GetBoundsRangeInfo()242 const BoundsRangeInfo *GetBoundsRangeInfo() const 243 { 244 return &boundsRangeInfo_; 245 } 246 247 static bool IsInstNotNull(const Inst *inst, BasicBlock *block); 248 249 static void VisitNeg(GraphVisitor *v, Inst *inst); 250 static void VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst); 251 static void VisitAbs(GraphVisitor *v, Inst *inst); 252 static void VisitAdd(GraphVisitor *v, Inst *inst); 253 static void VisitAddOverflowCheck(GraphVisitor *v, Inst *inst); 254 static void VisitSub(GraphVisitor *v, Inst *inst); 255 static void VisitSubOverflowCheck(GraphVisitor *v, Inst *inst); 256 static void VisitMod(GraphVisitor *v, Inst *inst); 257 static void VisitDiv(GraphVisitor *v, Inst *inst); 258 static void VisitMul(GraphVisitor *v, Inst *inst); 259 static void VisitAnd(GraphVisitor *v, Inst *inst); 260 static void VisitShr(GraphVisitor *v, Inst *inst); 261 static void VisitAShr(GraphVisitor *v, Inst *inst); 262 static void VisitShl(GraphVisitor *v, Inst *inst); 263 static void VisitIfImm(GraphVisitor *v, Inst *inst); 264 static void VisitPhi(GraphVisitor *v, Inst *inst); 265 static void VisitNullCheck(GraphVisitor *v, Inst *inst); 266 static void VisitBoundsCheck(GraphVisitor *v, Inst *inst); 267 static void VisitLoadObject(GraphVisitor *v, Inst *inst); 268 269 #include "optimizer/ir/visitor.inc" 270 private: 271 static bool CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgtBlock); 272 static void ProcessNullCheck(GraphVisitor *v, const Inst *checkInst, const Inst *refInput); 273 274 static BoundsRange UpdateLenArray(BoundsRange range, const Inst *lenArray, const Inst *upper); 275 static void CalcNewBoundsRangeForIsInstanceInput(GraphVisitor *v, IsInstanceInst *isInstance, IfImmInst *ifImm); 276 static void CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, InstPair args, 277 BasicBlock *tgtBlock); 278 template <Opcode OPC> 279 static void CalcNewBoundsRangeUnary(GraphVisitor *v, const Inst *inst); 280 template <Opcode OPC> 281 static void CalcNewBoundsRangeBinary(GraphVisitor *v, const Inst *inst); 282 static BoundsRange CalcNewBoundsRangeAdd(const BoundsRangeInfo *bri, const Inst *inst); 283 static BoundsRange CalcNewBoundsRangeSub(const BoundsRangeInfo *bri, const Inst *inst); 284 static BoundsRange CalcNewBoundsRangeMod(const BoundsRangeInfo *bri, const Inst *inst); 285 static BoundsRange CalcNewBoundsRangeMul(const BoundsRangeInfo *bri, const Inst *inst); 286 static BoundsRange CalcNewBoundsRangeDiv(const BoundsRangeInfo *bri, const Inst *inst); 287 static BoundsRange CalcNewBoundsRangeShr(const BoundsRangeInfo *bri, const Inst *inst); 288 static BoundsRange CalcNewBoundsRangeAShr(const BoundsRangeInfo *bri, const Inst *inst); 289 static BoundsRange CalcNewBoundsRangeShl(const BoundsRangeInfo *bri, const Inst *inst); 290 static BoundsRange CalcNewBoundsRangeAnd(const BoundsRangeInfo *bri, const Inst *inst); 291 static bool CheckBoundsRange(const BoundsRangeInfo *bri, const Inst *inst); 292 template <bool CHECK_TYPE = false> 293 static bool MergePhiPredecessors(PhiInst *phi, BoundsRangeInfo *bri); 294 bool ProcessCountableLoop(PhiInst *phi, BoundsRangeInfo *bri); 295 std::optional<uint64_t> GetNestedLoopIterations(Loop *loop, CountableLoopInfo &loopInfo); 296 std::optional<LoopIterationsInfo> GetSimpleLoopIterationsInfo(Loop *loop); 297 std::optional<LoopIterationsInfo> GetNestedLoopIterationsInfo(Loop *loop); 298 Inst *TryFindCorrespondingInitPhi(PhiInst *updatePhi, BasicBlock *header); 299 bool ProcessIndexPhi(Loop *loop, BoundsRangeInfo *bri, CountableLoopInfo &loopInfo); 300 bool ProcessInitPhi(PhiInst *initPhi, BoundsRangeInfo *bri); 301 bool ProcessUpdatePhi(PhiInst *updatePhi, BoundsRangeInfo *bri, uint64_t iterations); 302 void VisitLoop(BasicBlock *header, BasicBlock *updatePhiBlock); 303 304 private: 305 bool loopsRevisiting_ {false}; 306 Marker visited_ {UNDEF_MARKER}; 307 BoundsRangeInfo boundsRangeInfo_; 308 ArenaUnorderedMap<Loop *, std::optional<LoopIterationsInfo>> loopsInfoTable_; 309 }; 310 } // namespace ark::compiler 311 312 #endif // COMPILER_OPTIMIZER_ANALYSIS_BOUNDS_ANALYSIS_H 313