1 /** 2 * Copyright (c) 2021-2022 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 GetLenArray()49 const Inst *GetLenArray() 50 { 51 return len_array_; 52 } 53 int64_t GetLeft() const; 54 55 int64_t GetRight() const; 56 57 BoundsRange FitInType(DataType::Type type) const; 58 59 bool IsConst() const; 60 61 bool IsMaxRange(DataType::Type type = DataType::INT64) const; 62 63 bool IsEqual(const BoundsRange &range) const; 64 65 bool IsLess(const BoundsRange &range) const; 66 67 bool IsLess(const Inst *inst) const; 68 69 bool IsMore(const BoundsRange &range) const; 70 71 bool IsMoreOrEqual(const BoundsRange &range) const; 72 73 bool IsNotNegative() const; 74 75 bool IsNegative() const; 76 77 static int64_t GetMin(DataType::Type type); 78 79 static int64_t GetMax(DataType::Type type); 80 81 static BoundsRange Union(const ArenaVector<BoundsRange> &ranges); 82 83 static RangePair NarrowBoundsByNE(RangePair const &ranges); 84 static RangePair NarrowBoundsCase1(ConditionCode cc, RangePair const &ranges); 85 static RangePair NarrowBoundsCase2(ConditionCode cc, RangePair const &ranges); 86 static RangePair NarrowBoundsCase3(ConditionCode cc, RangePair const &ranges); 87 static RangePair NarrowBoundsCase4(ConditionCode cc, RangePair const &ranges); 88 static RangePair NarrowBoundsCase5(ConditionCode cc, RangePair const &ranges); 89 static RangePair NarrowBoundsCase6(ConditionCode cc, RangePair const &ranges); 90 91 static RangePair TryNarrowBoundsByCC(ConditionCode cc, RangePair const &ranges); 92 93 static constexpr int64_t MAX_RANGE_VALUE = INT64_MAX; 94 static constexpr int64_t MIN_RANGE_VALUE = INT64_MIN; 95 96 private: 97 int64_t left_ = MIN_RANGE_VALUE; 98 int64_t right_ = MAX_RANGE_VALUE; 99 const Inst *len_array_ {nullptr}; 100 }; 101 102 class BoundsRangeInfo { 103 public: BoundsRangeInfo(ArenaAllocator * aa)104 explicit BoundsRangeInfo(ArenaAllocator *aa) : aa_(*aa), bounds_range_info_(aa->Adapter()) {} 105 NO_COPY_SEMANTIC(BoundsRangeInfo); 106 NO_MOVE_SEMANTIC(BoundsRangeInfo); 107 ~BoundsRangeInfo() = default; 108 109 BoundsRange FindBoundsRange(const BasicBlock *block, Inst *inst) const; 110 111 void SetBoundsRange(const BasicBlock *block, const Inst *inst, BoundsRange range); 112 113 private: 114 ArenaAllocator &aa_; 115 ArenaDoubleUnorderedMap<const BasicBlock *, const Inst *, BoundsRange> bounds_range_info_; 116 }; 117 118 // NOLINTNEXTLINE(fuchsia-multiple-inheritance) 119 class BoundsAnalysis : public Analysis, public GraphVisitor { 120 public: 121 explicit BoundsAnalysis(Graph *graph); 122 NO_MOVE_SEMANTIC(BoundsAnalysis); 123 NO_COPY_SEMANTIC(BoundsAnalysis); 124 ~BoundsAnalysis() override = default; 125 126 const ArenaVector<BasicBlock *> &GetBlocksToVisit() const override; 127 128 bool RunImpl() override; 129 GetPassName()130 const char *GetPassName() const override 131 { 132 return "BoundsAnalysis"; 133 } 134 GetBoundsRangeInfo()135 BoundsRangeInfo *GetBoundsRangeInfo() 136 { 137 return &bounds_range_info_; 138 } 139 GetBoundsRangeInfo()140 const BoundsRangeInfo *GetBoundsRangeInfo() const 141 { 142 return &bounds_range_info_; 143 } 144 145 static void VisitIf([[maybe_unused]] GraphVisitor *v, [[maybe_unused]] Inst *inst); 146 static void VisitIfImm(GraphVisitor *v, Inst *inst); 147 static void VisitPhi(GraphVisitor *v, Inst *inst); 148 149 #include "optimizer/ir/visitor.inc" 150 private: 151 static bool CheckTriangleCase(const BasicBlock *block, const BasicBlock *tgt_block); 152 153 static void CalcNewBoundsRangeForCompare(GraphVisitor *v, BasicBlock *block, ConditionCode cc, Inst *left, 154 Inst *right, BasicBlock *tgt_block); 155 private: 156 BoundsRangeInfo bounds_range_info_; 157 }; 158 } // namespace panda::compiler 159 160 #endif // COMPILER_OPTIMIZER_ANALYSIS_BOUNDS_ANALYSIS_H 161