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 16 #ifndef COMPILER_OPTIMIZER_ANALYSIS_BOUNDSRANGE_ANALYSIS_H 17 #define COMPILER_OPTIMIZER_ANALYSIS_BOUNDSRANGE_ANALYSIS_H 18 19 #include "optimizer/ir/graph_visitor.h" 20 #include "optimizer/ir/datatype.h" 21 #include "optimizer/ir/inst.h" 22 #include "optimizer/pass.h" 23 #include "utils/arena_containers.h" 24 25 namespace panda::compiler { 26 /** 27 * Represents a range of values that a variable might have. 28 * 29 * It is used to represent variables of integral types according to their size 30 * and sign. 31 * It is used for REFERENCE type as well but only for reasoning whether a 32 * variable is NULL or not. 33 */ 34 class BoundsRange { 35 public: 36 using RangePair = std::pair<BoundsRange, BoundsRange>; 37 left_(GetMin (type))38 explicit BoundsRange(DataType::Type type = DataType::INT64) : left_(GetMin(type)), right_(GetMax(type)) {}; 39 40 explicit BoundsRange(int64_t left, int64_t right, const Inst *inst = nullptr, 41 DataType::Type type = DataType::INT64); 42 43 explicit BoundsRange(int64_t val, DataType::Type type = DataType::INT64); 44 45 DEFAULT_COPY_SEMANTIC(BoundsRange); 46 DEFAULT_MOVE_SEMANTIC(BoundsRange); 47 ~BoundsRange() = default; 48 49 void SetLenArray(const Inst *inst); 50 GetLenArray()51 const Inst *GetLenArray() 52 { 53 return lenArray_; 54 } 55 int64_t GetLeft() const; 56 57 int64_t GetRight() const; 58 59 BoundsRange FitInType(DataType::Type type) const; 60 61 BoundsRange Neg() const; 62 63 BoundsRange Abs() const; 64 65 BoundsRange Add(const BoundsRange &range) const; 66 67 BoundsRange Sub(const BoundsRange &range) const; 68 69 BoundsRange Mul(const BoundsRange &range) const; 70 71 BoundsRange Div(const BoundsRange &range) const; 72 73 BoundsRange Mod(const BoundsRange &range); 74 75 BoundsRange And(const BoundsRange &range); 76 77 BoundsRange Shr(const BoundsRange &range, DataType::Type type = DataType::INT64); 78 79 BoundsRange AShr(const BoundsRange &range, DataType::Type type = DataType::INT64); 80 81 BoundsRange Shl(const BoundsRange &range, DataType::Type type = DataType::INT64); 82 83 bool IsConst() const; 84 85 bool IsMaxRange(DataType::Type type = DataType::INT64) const; 86 87 bool IsEqual(const BoundsRange &range) const; 88 89 bool IsLess(const BoundsRange &range) const; 90 91 bool IsLess(const Inst *inst) const; 92 93 bool IsMore(const BoundsRange &range) const; 94 95 bool IsMoreOrEqual(const BoundsRange &range) const; 96 97 bool IsNotNegative() const; 98 99 bool IsNegative() const; 100 101 bool IsPositive() const; 102 103 bool IsNotPositive() const; 104 105 bool CanOverflow(DataType::Type type = DataType::INT64) const; 106 107 bool CanOverflowNeg(DataType::Type type = DataType::INT64) const; 108 109 static int64_t GetMin(DataType::Type type); 110 111 static int64_t GetMax(DataType::Type type); 112 113 static BoundsRange Union(const ArenaVector<BoundsRange> &ranges); 114 115 static RangePair NarrowBoundsByNE(RangePair const &ranges); 116 static RangePair NarrowBoundsCase1(ConditionCode cc, RangePair const &ranges); 117 static RangePair NarrowBoundsCase2(ConditionCode cc, RangePair const &ranges); 118 static RangePair NarrowBoundsCase3(ConditionCode cc, RangePair const &ranges); 119 static RangePair NarrowBoundsCase4(ConditionCode cc, RangePair const &ranges); 120 static RangePair NarrowBoundsCase5(ConditionCode cc, RangePair const &ranges); 121 static RangePair NarrowBoundsCase6(ConditionCode cc, RangePair const &ranges); 122 123 static RangePair TryNarrowBoundsByCC(ConditionCode cc, RangePair const &ranges); 124 125 static int64_t AddWithOverflowCheck(int64_t left, int64_t right); 126 127 static int64_t MulWithOverflowCheck(int64_t left, int64_t right); 128 129 static int64_t DivWithOverflowCheck(int64_t left, int64_t right); 130 131 static constexpr int64_t MAX_RANGE_VALUE = INT64_MAX; 132 static constexpr int64_t MIN_RANGE_VALUE = INT64_MIN; 133 134 bool operator==(const BoundsRange &rhs) const 135 { 136 return left_ == rhs.left_ && right_ == rhs.right_ && lenArray_ == rhs.lenArray_; 137 } 138 139 void Dump(std::ostream &out = std::cerr) const 140 { 141 out << "Range = [" << left_ << ", "; 142 out << right_ << "]"; 143 if (lenArray_ != nullptr) { 144 out << ", len_array = " << lenArray_->GetId(); 145 } 146 out << "\n"; 147 } 148 149 private: 150 int64_t left_ = MIN_RANGE_VALUE; 151 int64_t right_ = MAX_RANGE_VALUE; 152 const Inst *lenArray_ {nullptr}; 153 }; 154 155 class BoundsRangeInfo { 156 public: BoundsRangeInfo(ArenaAllocator * aa)157 explicit BoundsRangeInfo(ArenaAllocator *aa) : aa_(*aa), boundsRangeInfo_(aa->Adapter()) {} 158 NO_COPY_SEMANTIC(BoundsRangeInfo); 159 NO_MOVE_SEMANTIC(BoundsRangeInfo); 160 ~BoundsRangeInfo() = default; 161 162 BoundsRange FindBoundsRange(const BasicBlock *block, const Inst *inst) const; 163 164 void SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range); 165 Clear()166 void Clear() 167 { 168 boundsRangeInfo_.clear(); 169 } 170 171 private: 172 ArenaAllocator &aa_; 173 ArenaDoubleUnorderedMap<const BasicBlock *, const Inst *, BoundsRange> boundsRangeInfo_; 174 }; 175 176 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 177 class BoundsAnalysis : public Analysis, public GraphVisitor { 178 public: 179 explicit BoundsAnalysis(Graph *graph); 180 NO_MOVE_SEMANTIC(BoundsAnalysis); 181 NO_COPY_SEMANTIC(BoundsAnalysis); 182 ~BoundsAnalysis() override = default; 183 184 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override; 185 186 bool RunImpl() override; 187 GetPassName()188 const char *GetPassName() const override 189 { 190 return "BoundsAnalysis"; 191 } 192 GetBoundsRangeInfo()193 BoundsRangeInfo *GetBoundsRangeInfo() 194 { 195 return &boundsRangeInfo_; 196 } 197 GetBoundsRangeInfo()198 const BoundsRangeInfo *GetBoundsRangeInfo() const 199 { 200 return &boundsRangeInfo_; 201 } 202 203 static bool IsInstNotNull(const Inst *inst, BasicBlock *block); 204 205 static void VisitNeg(GraphVisitor *v, Inst *inst); 206 static void VisitNegOverflowAndZeroCheck(GraphVisitor *v, Inst *inst); 207 static void VisitAbs(GraphVisitor *v, Inst *inst); 208 static void VisitAdd(GraphVisitor *v, Inst *inst); 209 static void VisitAddOverflowCheck(GraphVisitor *v, Inst *inst); 210 static void VisitSub(GraphVisitor *v, Inst *inst); 211 static void VisitSubOverflowCheck(GraphVisitor *v, Inst *inst); 212 static void VisitMod(GraphVisitor *v, Inst *inst); 213 static void VisitDiv(GraphVisitor *v, Inst *inst); 214 static void VisitMul(GraphVisitor *v, Inst *inst); 215 static void VisitAnd(GraphVisitor *v, Inst *inst); 216 static void VisitShr(GraphVisitor *v, Inst *inst); 217 static void VisitAShr(GraphVisitor *v, Inst *inst); 218 static void VisitShl(GraphVisitor *v, Inst *inst); 219 static void VisitIfImm(GraphVisitor *v, Inst *inst); 220 static void VisitPhi(GraphVisitor *v, Inst *inst); 221 static void VisitNullCheck(GraphVisitor *v, Inst *inst); 222 223 #include "optimizer/ir/visitor.inc" 224 private: 225 static bool ProcessCountableLoop(PhiInst *phi, BoundsRangeInfo *bri); 226 static bool CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgtBlock); 227 static void ProcessNullCheck(GraphVisitor *v, const Inst *checkInst, const Inst *refInput); 228 229 static BoundsRange UpdateLenArray(BoundsRange range, const Inst *lenArray, const Inst *upper); 230 static void CalcNewBoundsRangeForIsInstanceInput(GraphVisitor *v, IsInstanceInst *isInstance, IfImmInst *ifImm); 231 static void CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, Inst *left, 232 Inst *right, BasicBlock *tgtBlock); 233 template <Opcode OPC> 234 static void CalcNewBoundsRangeUnary(GraphVisitor *v, const Inst *inst); 235 template <Opcode OPC> 236 static void CalcNewBoundsRangeBinary(GraphVisitor *v, const Inst *inst); 237 238 private: 239 BoundsRangeInfo boundsRangeInfo_; 240 }; 241 } // namespace panda::compiler 242 243 #endif // COMPILER_OPTIMIZER_ANALYSIS_BOUNDS_ANALYSIS_H 244