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 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 int64_t GetLeft() const; 57 58 int64_t GetRight() const; 59 60 BoundsRange FitInType(DataType::Type type) const; 61 62 BoundsRange Neg() const; 63 64 BoundsRange Abs() const; 65 66 BoundsRange Add(const BoundsRange &range) const; 67 68 BoundsRange Sub(const BoundsRange &range) const; 69 70 BoundsRange Mul(const BoundsRange &range) const; 71 72 BoundsRange Div(const BoundsRange &range) const; 73 74 BoundsRange Mod(const BoundsRange &range); 75 76 BoundsRange And(const BoundsRange &range); 77 78 BoundsRange Shr(const BoundsRange &range, DataType::Type type = DataType::INT64); 79 80 BoundsRange AShr(const BoundsRange &range, DataType::Type type = DataType::INT64); 81 82 BoundsRange Shl(const BoundsRange &range, DataType::Type type = DataType::INT64); 83 84 BoundsRange Diff(const BoundsRange &range) const; 85 86 bool IsConst() const; 87 88 bool IsMaxRange(DataType::Type type = DataType::INT64) const; 89 90 bool IsEqual(const BoundsRange &range) const; 91 92 bool IsLess(const BoundsRange &range) const; 93 94 bool IsLess(const Inst *inst) const; 95 96 bool IsMore(const BoundsRange &range) const; 97 98 bool IsMoreOrEqual(const BoundsRange &range) const; 99 100 bool IsWithin(const BoundsRange &range) const; 101 102 bool IsNotNegative() const; 103 104 bool IsNegative() const; 105 106 bool IsPositive() const; 107 108 bool IsNotPositive() const; 109 110 bool CanOverflow(DataType::Type type = DataType::INT64) const; 111 112 bool CanOverflowNeg(DataType::Type type = DataType::INT64) const; 113 114 static int64_t GetMin(DataType::Type type); 115 116 static int64_t GetMax(DataType::Type type); 117 118 static BoundsRange Union(const ArenaVector<BoundsRange> &ranges); 119 120 static RangePair NarrowBoundsByNE(RangePair const &ranges); 121 static RangePair NarrowBoundsCase1(ConditionCode cc, RangePair const &ranges); 122 static RangePair NarrowBoundsCase2(ConditionCode cc, RangePair const &ranges); 123 static RangePair NarrowBoundsCase3(ConditionCode cc, RangePair const &ranges); 124 static RangePair NarrowBoundsCase4(ConditionCode cc, RangePair const &ranges); 125 static RangePair NarrowBoundsCase5(ConditionCode cc, RangePair const &ranges); 126 static RangePair NarrowBoundsCase6(ConditionCode cc, RangePair const &ranges); 127 128 static RangePair TryNarrowBoundsByCC(ConditionCode cc, RangePair const &ranges); 129 130 static std::optional<int64_t> AddWithOverflowCheck(int64_t left, int64_t right); 131 static std::optional<uint64_t> AddWithOverflowCheck(uint64_t left, uint64_t right); 132 133 static std::optional<int64_t> MulWithOverflowCheck(int64_t left, int64_t right); 134 static std::optional<uint64_t> MulWithOverflowCheck(uint64_t left, uint64_t right); 135 136 static std::optional<int64_t> DivWithOverflowCheck(int64_t left, int64_t right); 137 138 static constexpr int64_t MAX_RANGE_VALUE = INT64_MAX; 139 static constexpr int64_t MIN_RANGE_VALUE = INT64_MIN; 140 141 bool operator==(const BoundsRange &rhs) const 142 { 143 return left_ == rhs.left_ && right_ == rhs.right_ && lenArray_ == rhs.lenArray_; 144 } 145 146 void Dump(std::ostream &out = std::cerr) const 147 { 148 out << "Range = [" << left_ << ", "; 149 out << right_ << "]"; 150 if (lenArray_ != nullptr) { 151 out << ", len_array = " << lenArray_->GetId(); 152 } 153 out << "\n"; 154 } 155 156 private: 157 int64_t left_ = MIN_RANGE_VALUE; 158 int64_t right_ = MAX_RANGE_VALUE; 159 const Inst *lenArray_ {nullptr}; 160 }; 161 162 class BoundsRangeInfo { 163 public: BoundsRangeInfo(ArenaAllocator * aa)164 explicit BoundsRangeInfo(ArenaAllocator *aa) : aa_(*aa), boundsRangeInfo_(aa->Adapter()) {} 165 NO_COPY_SEMANTIC(BoundsRangeInfo); 166 NO_MOVE_SEMANTIC(BoundsRangeInfo); 167 ~BoundsRangeInfo() = default; 168 169 BoundsRange FindBoundsRange(const BasicBlock *block, const Inst *inst) const; 170 171 void SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range); 172 Clear()173 void Clear() 174 { 175 boundsRangeInfo_.clear(); 176 } 177 178 private: 179 ArenaAllocator &aa_; 180 ArenaDoubleUnorderedMap<const BasicBlock *, const Inst *, BoundsRange> boundsRangeInfo_; 181 }; 182 183 // index phi, iterations 184 using LoopIterationsInfo = std::pair<CountableLoopInfo, uint64_t>; 185 186 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 187 class BoundsAnalysis : public Analysis, public GraphVisitor { 188 public: 189 using InstPair = std::pair<Inst *, Inst *>; 190 191 explicit BoundsAnalysis(Graph *graph); 192 NO_MOVE_SEMANTIC(BoundsAnalysis); 193 NO_COPY_SEMANTIC(BoundsAnalysis); 194 ~BoundsAnalysis() override = default; 195 196 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override; 197 198 bool RunImpl() override; 199 GetPassName()200 const char *GetPassName() const override 201 { 202 return "BoundsAnalysis"; 203 } 204 GetBoundsRangeInfo()205 BoundsRangeInfo *GetBoundsRangeInfo() 206 { 207 return &boundsRangeInfo_; 208 } 209 GetBoundsRangeInfo()210 const BoundsRangeInfo *GetBoundsRangeInfo() const 211 { 212 return &boundsRangeInfo_; 213 } 214 215 static bool IsInstNotNull(const Inst *inst, BasicBlock *block); 216 217 static void VisitNeg(GraphVisitor *v, Inst *inst); 218 static void VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst); 219 static void VisitAbs(GraphVisitor *v, Inst *inst); 220 static void VisitAdd(GraphVisitor *v, Inst *inst); 221 static void VisitAddOverflowCheck(GraphVisitor *v, Inst *inst); 222 static void VisitSub(GraphVisitor *v, Inst *inst); 223 static void VisitSubOverflowCheck(GraphVisitor *v, Inst *inst); 224 static void VisitMod(GraphVisitor *v, Inst *inst); 225 static void VisitDiv(GraphVisitor *v, Inst *inst); 226 static void VisitMul(GraphVisitor *v, Inst *inst); 227 static void VisitAnd(GraphVisitor *v, Inst *inst); 228 static void VisitShr(GraphVisitor *v, Inst *inst); 229 static void VisitAShr(GraphVisitor *v, Inst *inst); 230 static void VisitShl(GraphVisitor *v, Inst *inst); 231 static void VisitIfImm(GraphVisitor *v, Inst *inst); 232 static void VisitPhi(GraphVisitor *v, Inst *inst); 233 static void VisitNullCheck(GraphVisitor *v, Inst *inst); 234 235 #include "optimizer/ir/visitor.inc" 236 private: 237 static bool CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgtBlock); 238 static void ProcessNullCheck(GraphVisitor *v, const Inst *checkInst, const Inst *refInput); 239 240 static BoundsRange UpdateLenArray(BoundsRange range, const Inst *lenArray, const Inst *upper); 241 static void CalcNewBoundsRangeForIsInstanceInput(GraphVisitor *v, IsInstanceInst *isInstance, IfImmInst *ifImm); 242 static void CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, InstPair args, 243 BasicBlock *tgtBlock); 244 template <Opcode OPC> 245 static void CalcNewBoundsRangeUnary(GraphVisitor *v, const Inst *inst); 246 template <Opcode OPC> 247 static void CalcNewBoundsRangeBinary(GraphVisitor *v, const Inst *inst); 248 static BoundsRange CalcNewBoundsRangeAdd(const BoundsRangeInfo *bri, const Inst *inst); 249 static BoundsRange CalcNewBoundsRangeSub(const BoundsRangeInfo *bri, const Inst *inst); 250 static BoundsRange CalcNewBoundsRangeMod(const BoundsRangeInfo *bri, const Inst *inst); 251 static BoundsRange CalcNewBoundsRangeMul(const BoundsRangeInfo *bri, const Inst *inst); 252 static BoundsRange CalcNewBoundsRangeDiv(const BoundsRangeInfo *bri, const Inst *inst); 253 static BoundsRange CalcNewBoundsRangeShr(const BoundsRangeInfo *bri, const Inst *inst); 254 static BoundsRange CalcNewBoundsRangeAShr(const BoundsRangeInfo *bri, const Inst *inst); 255 static BoundsRange CalcNewBoundsRangeShl(const BoundsRangeInfo *bri, const Inst *inst); 256 static BoundsRange CalcNewBoundsRangeAnd(const BoundsRangeInfo *bri, const Inst *inst); 257 static bool CheckBoundsRange(const BoundsRangeInfo *bri, const Inst *inst); 258 template <bool CHECK_TYPE = false> 259 static bool MergePhiPredecessors(PhiInst *phi, BoundsRangeInfo *bri); 260 bool ProcessCountableLoop(PhiInst *phi, BoundsRangeInfo *bri); 261 std::optional<uint64_t> GetNestedLoopIterations(Loop *loop, CountableLoopInfo &loopInfo); 262 std::optional<LoopIterationsInfo> GetSimpleLoopIterationsInfo(Loop *loop); 263 std::optional<LoopIterationsInfo> GetNestedLoopIterationsInfo(Loop *loop); 264 Inst *TryFindCorrespondingInitPhi(PhiInst *updatePhi, BasicBlock *header); 265 bool ProcessIndexPhi(Loop *loop, BoundsRangeInfo *bri, CountableLoopInfo &loopInfo); 266 bool ProcessInitPhi(PhiInst *initPhi, BoundsRangeInfo *bri); 267 bool ProcessUpdatePhi(PhiInst *updatePhi, BoundsRangeInfo *bri, uint64_t iterations); 268 void VisitLoop(BasicBlock *header, BasicBlock *updatePhiBlock); 269 270 private: 271 bool loopsRevisiting_ {false}; 272 Marker visited_ {UNDEF_MARKER}; 273 BoundsRangeInfo boundsRangeInfo_; 274 ArenaUnorderedMap<Loop *, std::optional<LoopIterationsInfo>> loopsInfoTable_; 275 }; 276 } // namespace ark::compiler 277 278 #endif // COMPILER_OPTIMIZER_ANALYSIS_BOUNDS_ANALYSIS_H 279