1 /* 2 * Copyright (c) 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 ECMASCRIPT_COMPILER_ARRAY_BOUNDS_CHECK_ELIMINATION_H 17 #define ECMASCRIPT_COMPILER_ARRAY_BOUNDS_CHECK_ELIMINATION_H 18 19 #include "ecmascript/compiler/circuit_builder.h" 20 #include "ecmascript/compiler/mcr_gate_meta_data.h" 21 #include "ecmascript/compiler/gate_accessor.h" 22 #include "ecmascript/compiler/graph_linearizer.h" 23 #include "ecmascript/compiler/pass_manager.h" 24 #include "ecmascript/mem/chunk_containers.h" 25 26 namespace panda::ecmascript::kungfu { 27 class ArrayBoundsCheckElimination { 28 public: ArrayBoundsCheckElimination(Circuit * circuit,bool enableLog,const std::string & name,Chunk * chunk)29 ArrayBoundsCheckElimination(Circuit *circuit, bool enableLog, const std::string& name, Chunk* chunk) 30 : acc_(circuit), bounds_(chunk), circuit_(circuit), builder_(circuit), chunk_(chunk), enableLog_(enableLog), 31 graphLinearizer_(circuit, enableLog, name, chunk, true, true), methodName_(name), indexCheckInfo_(chunk) {} 32 33 ~ArrayBoundsCheckElimination() = default; 34 void Run(); 35 36 private: 37 class Bound { 38 public: 39 Bound(); 40 explicit Bound(GateRef v); 41 Bound(int lower, GateRef lowerGate, int upper, GateRef upperGate); 42 Bound(TypedBinOp op, GateRef gate, int constant); ~Bound()43 ~Bound(){}; 44 Upper()45 int Upper() 46 { 47 return upper_; 48 } 49 UpperGate()50 GateRef UpperGate() 51 { 52 return upperGate_; 53 } 54 Lower()55 int Lower() 56 { 57 return lower_; 58 } 59 LowerGate()60 GateRef LowerGate() 61 { 62 return lowerGate_; 63 } 64 HasUpper()65 bool HasUpper() 66 { 67 return upperGate_ != Circuit::NullGate() || upper_ < INT_MAX; 68 } 69 HasLower()70 bool HasLower() 71 { 72 return lowerGate_ != Circuit::NullGate() || lower_ > INT_MIN; 73 } 74 RemoveUpper()75 void RemoveUpper() 76 { 77 upperGate_ = Circuit::NullGate(); 78 upper_ = INT_MAX; 79 } 80 RemoveLower()81 void RemoveLower() 82 { 83 lowerGate_ = Circuit::NullGate(); 84 lower_ = INT_MIN; 85 } 86 IsSmaller(Bound * b)87 bool IsSmaller(Bound *b) 88 { 89 if (b->LowerGate() != upperGate_) { 90 return false; 91 } 92 return upper_ < b->Lower(); 93 } 94 Copy()95 Bound* Copy() 96 { 97 return new Bound(lower_, lowerGate_, upper_, upperGate_); 98 } 99 100 private: 101 int upper_; 102 GateRef upperGate_; 103 int lower_; 104 GateRef lowerGate_; 105 106 friend ArrayBoundsCheckElimination; 107 }; 108 IsLogEnabled()109 bool IsLogEnabled() const 110 { 111 return enableLog_; 112 } 113 GetMethodName()114 const std::string& GetMethodName() const 115 { 116 return methodName_; 117 } 118 119 typedef ChunkVector<Bound*> BoundStack; 120 typedef ChunkVector<BoundStack*> BoundMap; 121 typedef ChunkVector<int> IntegerStack; 122 typedef ChunkVector<GateRef> GateLists; 123 124 void AddAccessIndexedInfo(GateLists &indices, GateRef gate, int idx, GateRef indexCheck); 125 void AddIfCondition(IntegerStack &pushed, GateRef x, GateRef y, TypedBinOp op); 126 Bound *AndOp(Bound *bound, Bound *b); 127 Bound *OrOp(Bound *bound, Bound *b); 128 bool Contain(GateLists &gateLists, GateRef gate); 129 void CalcBounds(GateRegion *block, GateRegion *loopHeader); 130 bool CheckLoop(GateRef array, GateRef lowerGate, int lower, GateRef upperGate, int upper); 131 GateRef FindBoundGate(GateRef gate); 132 void InBlockMotion(GateLists &indexChecked, GateLists &arrays); 133 bool InLoop(GateRef loopHeader, GateRef gate); 134 bool IsArrayLength(GateRef gate); 135 bool LoopInvariant(GateRegion *loopHeader, GateRef gate); 136 void UpdateBound(IntegerStack &pushed, GateRef gate, Bound *bound); 137 void UpdateBound(IntegerStack &pushed, GateRef x, TypedBinOp op, GateRef y, int constValue); 138 void ProcessIndexCheck(GateRegion *loopHeader, GateRef gate); 139 void RemoveIndexCheck(GateRef gate); 140 void CopyStateInAndDependIn(GateRef &stateIn, GateRef &dependIn, GateRef insertAfter); 141 void LoopInvariantMotionForIndexCheck(GateRef array, GateRef length, GateRef lowerGate, int lower, 142 GateRef upperGate, int upper, bool isTypedArray); 143 bool GetInstrAndConstValueFromUnaryOp(GateRef gate, GateRef &other, int& value); 144 bool GetInstrAndConstValueFromBinaryOp(GateRef gate, GateRef &other, int& value); 145 void GetInstrAndConstValueFromOp(GateRef gate, GateRef &instrValue, int& constValue); 146 Bound *GetBound(GateRef gate); 147 Bound *DoConstant(GateRef gate); 148 Bound *DoBinaryArithmeticOp(GateRef gate); 149 Bound *DoUnaryArithmeticOp(GateRef gate); 150 Bound *DoPhi(GateRef gate); 151 void SetBound(GateRef gate, Bound *bound); 152 void ProcessIf(IntegerStack &pushed, GateRegion *parent, OpCode cond); 153 bool InArrayBound(Bound *bound, GateRef length, GateRef array); 154 Bound *VisitGate(GateRef gate); 155 156 void ReplaceIn(GateRef stateIn, GateRef dependIn, GateRef newGate); 157 158 GateRef Predicate(GateRef left, TypedBinOp cond, GateRef right); 159 GateRef PredicateCmpWithConst(GateRef left, TypedBinOp cond, int right); 160 GateRef PredicateAdd(GateRef left, int leftConst, TypedBinOp cond, GateRef right); 161 GateRef PredicateAddCmpWithConst(GateRef left, int leftConst, TypedBinOp cond, int right); 162 163 GateAccessor acc_; 164 BoundMap bounds_; 165 Circuit *circuit_ {nullptr}; 166 CircuitBuilder builder_; 167 Chunk *chunk_ {nullptr}; 168 bool enableLog_ {false}; 169 GraphLinearizer graphLinearizer_; 170 std::string methodName_; 171 172 class IndexCheckInfo { 173 public: IndexCheckInfo(Chunk * chunk)174 IndexCheckInfo(Chunk* chunk): list_(chunk) {} 175 GateLists list_; 176 int min_; 177 int max_; 178 }; 179 typedef ChunkVector<IndexCheckInfo*> IndexCheckInfoList; 180 IndexCheckInfoList indexCheckInfo_; 181 }; 182 } 183 #endif