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_EARLY_ELIMINATION_H 17 #define ECMASCRIPT_COMPILER_EARLY_ELIMINATION_H 18 19 #include "ecmascript/compiler/circuit_builder.h" 20 #include "ecmascript/compiler/gate_accessor.h" 21 #include "ecmascript/mem/chunk_containers.h" 22 23 namespace panda::ecmascript::kungfu { 24 class ElementInfo : public ChunkObject { 25 public: ElementInfo(TypedLoadOp loadOp,GateRef receiver,GateRef index)26 ElementInfo(TypedLoadOp loadOp, GateRef receiver, GateRef index) 27 : loadOp_(loadOp), receiver_(receiver), index_(index) {}; 28 ~ElementInfo() = default; 29 bool operator < (const ElementInfo& rhs) const 30 { 31 if (loadOp_ != rhs.loadOp_) { 32 return loadOp_ < rhs.loadOp_; 33 } else if (receiver_ != rhs.receiver_) { 34 return receiver_ < rhs.receiver_; 35 } else { 36 return index_ < rhs.index_; 37 } 38 } 39 40 private: 41 TypedLoadOp loadOp_ {0}; 42 GateRef receiver_ {Circuit::NullGate()}; 43 GateRef index_ {Circuit::NullGate()}; 44 }; 45 46 class PropertyInfo : public ChunkObject { 47 public: PropertyInfo(GateRef receiver,GateRef offset)48 PropertyInfo(GateRef receiver, GateRef offset) : receiver_(receiver), offset_(offset) {}; 49 ~PropertyInfo() = default; 50 bool operator < (const PropertyInfo& rhs) const 51 { 52 if (receiver_ != rhs.receiver_) { 53 return receiver_ < rhs.receiver_; 54 } else { 55 return offset_ < rhs.offset_; 56 } 57 } 58 59 private: 60 GateRef receiver_ {Circuit::NullGate()}; 61 GateRef offset_ {Circuit::NullGate()}; 62 }; 63 64 class ArrayLengthInfo : public ChunkObject { 65 public: ArrayLengthInfo(GateRef receiver)66 ArrayLengthInfo(GateRef receiver) : receiver_(receiver){}; 67 ~ArrayLengthInfo() = default; 68 bool operator < (const ArrayLengthInfo& rhs) const 69 { 70 return receiver_ < rhs.receiver_; 71 } 72 73 private: 74 GateRef receiver_ {Circuit::NullGate()}; 75 }; 76 77 class PrimitiveTypeCheckInfo : public ChunkObject { 78 public: PrimitiveTypeCheckInfo(GateType type,GateRef value)79 PrimitiveTypeCheckInfo(GateType type, GateRef value) : type_(type), value_(value) {}; 80 ~PrimitiveTypeCheckInfo() = default; 81 bool operator < (const PrimitiveTypeCheckInfo& rhs) const 82 { 83 if (type_ != rhs.type_) { 84 return type_ < rhs.type_; 85 } else { 86 return value_ < rhs.value_; 87 } 88 } 89 90 private: 91 GateType type_ {GateType::Empty()}; 92 GateRef value_ {Circuit::NullGate()}; 93 }; 94 95 class Int32OverflowCheckInfo : public ChunkObject { 96 public: Int32OverflowCheckInfo(TypedUnOp unOp,GateRef value)97 Int32OverflowCheckInfo(TypedUnOp unOp, GateRef value) : unOp_(unOp), value_(value) {}; 98 ~Int32OverflowCheckInfo() = default; 99 bool operator < (const Int32OverflowCheckInfo& rhs) const 100 { 101 if (unOp_ != rhs.unOp_) { 102 return unOp_ < rhs.unOp_; 103 } else { 104 return value_ < rhs.value_; 105 } 106 } 107 108 private: 109 TypedUnOp unOp_ {0}; 110 GateRef value_ {Circuit::NullGate()}; 111 }; 112 113 class ArrayCheckInfo : public ChunkObject { 114 public: ArrayCheckInfo(GateRef receiver)115 ArrayCheckInfo(GateRef receiver) : receiver_(receiver){}; 116 ~ArrayCheckInfo() = default; 117 bool operator < (const ArrayCheckInfo& rhs) const 118 { 119 return receiver_ < rhs.receiver_; 120 } 121 122 private: 123 GateRef receiver_ {Circuit::NullGate()}; 124 }; 125 126 class StableArrayCheckInfo : public ChunkObject { 127 public: StableArrayCheckInfo(GateRef receiver)128 StableArrayCheckInfo(GateRef receiver) : receiver_(receiver){}; 129 ~StableArrayCheckInfo() = default; 130 bool operator < (const StableArrayCheckInfo& rhs) const 131 { 132 return receiver_ < rhs.receiver_; 133 } 134 135 private: 136 GateRef receiver_ {Circuit::NullGate()}; 137 }; 138 139 class TypedArrayCheckInfo : public ChunkObject { 140 public: TypedArrayCheckInfo(GateType type,GateRef receiver)141 TypedArrayCheckInfo(GateType type, GateRef receiver) 142 : type_(type), receiver_(receiver) {}; 143 ~TypedArrayCheckInfo() = default; 144 bool operator < (const TypedArrayCheckInfo& rhs) const 145 { 146 if (type_ != rhs.type_) { 147 return type_ < rhs.type_; 148 } else { 149 return receiver_ < rhs.receiver_; 150 } 151 } 152 153 private: 154 GateType type_ {GateType::Empty()}; 155 GateRef receiver_ {Circuit::NullGate()}; 156 }; 157 158 class ObjectTypeCheckInfo : public ChunkObject { 159 public: ObjectTypeCheckInfo(GateType type,GateRef receiver,GateRef offset)160 ObjectTypeCheckInfo(GateType type, GateRef receiver, GateRef offset) 161 : type_(type), receiver_(receiver), offset_(offset) {}; 162 ~ObjectTypeCheckInfo() = default; 163 bool operator < (const ObjectTypeCheckInfo& rhs) const 164 { 165 if (type_ != rhs.type_) { 166 return type_ < rhs.type_; 167 } else if (receiver_ != rhs.receiver_) { 168 return receiver_ < rhs.receiver_; 169 } else { 170 return offset_ < rhs.offset_; 171 } 172 } 173 174 private: 175 GateType type_ {GateType::Empty()}; 176 GateRef receiver_ {Circuit::NullGate()}; 177 GateRef offset_ {Circuit::NullGate()}; 178 }; 179 180 class IndexCheckInfo : public ChunkObject { 181 public: IndexCheckInfo(GateType type,GateRef receiver,GateRef index)182 IndexCheckInfo(GateType type, GateRef receiver, GateRef index) 183 : type_(type), receiver_(receiver), index_(index) {}; 184 ~IndexCheckInfo() = default; 185 bool operator < (const IndexCheckInfo& rhs) const 186 { 187 if (type_ != rhs.type_) { 188 return type_ < rhs.type_; 189 } else if (receiver_ != rhs.receiver_) { 190 return receiver_ < rhs.receiver_; 191 } else { 192 return index_ < rhs.index_; 193 } 194 } 195 196 private: 197 GateType type_ {GateType::Empty()}; 198 GateRef receiver_ {Circuit::NullGate()}; 199 GateRef index_ {Circuit::NullGate()}; 200 }; 201 202 class TypedCallCheckInfo : public ChunkObject { 203 public: TypedCallCheckInfo(GateRef func,GateRef id,GateRef para)204 TypedCallCheckInfo(GateRef func, GateRef id, GateRef para) 205 : func_(func), id_(id), para_(para) {}; 206 ~TypedCallCheckInfo() = default; 207 bool operator < (const TypedCallCheckInfo& rhs) const 208 { 209 if (func_ != rhs.func_) { 210 return func_ < rhs.func_; 211 } else if (id_ != rhs.id_) { 212 return id_ < rhs.id_; 213 } else { 214 return para_ < rhs.para_; 215 } 216 } 217 218 private: 219 GateRef func_ {Circuit::NullGate()}; 220 GateRef id_ {Circuit::NullGate()}; 221 GateRef para_ {Circuit::NullGate()}; 222 }; 223 224 class DependChainInfo : public ChunkObject { 225 public: DependChainInfo(Chunk * chunk)226 DependChainInfo(Chunk* chunk) : chunk_(chunk) {}; 227 ~DependChainInfo() = default; 228 229 bool operator == (const DependChainInfo& rhs) const 230 { 231 return (elementMap_ == rhs.elementMap_) && 232 (propertyMap_ == rhs.propertyMap_) && 233 (arrayLengthMap_ == rhs.arrayLengthMap_) && 234 (primitiveTypeCheckSet_ == rhs.primitiveTypeCheckSet_) && 235 (int32OverflowCheckSet_ == rhs.int32OverflowCheckSet_) && 236 (arrayCheckSet_ == rhs.arrayCheckSet_) && 237 (stableArrayCheckSet_ == rhs.stableArrayCheckSet_) && 238 (typedArrayCheckSet_ == rhs.typedArrayCheckSet_) && 239 (objectTypeCheckSet_ == rhs.objectTypeCheckSet_) && 240 (indexCheckSet_ == rhs.indexCheckSet_) && 241 (typedCallCheckSet_ == rhs.typedCallCheckSet_) && 242 (frameState_ == rhs.frameState_); 243 } 244 245 GateRef LookUpElement(ElementInfo* info) const; 246 GateRef LookUpProperty(PropertyInfo* info) const; 247 GateRef LookUpArrayLength(ArrayLengthInfo* info) const; 248 bool LookUpPrimitiveTypeCheck(PrimitiveTypeCheckInfo* info) const; 249 bool LookUpInt32OverflowCheck(Int32OverflowCheckInfo* info) const; 250 bool LookUpArrayCheck(ArrayCheckInfo* info) const; 251 bool LookUpStableArrayCheck(StableArrayCheckInfo* info) const; 252 bool LookUpTypedArrayCheck(TypedArrayCheckInfo* info) const; 253 bool LookUpObjectTypeCheck(ObjectTypeCheckInfo* info) const; 254 bool LookUpIndexCheck(IndexCheckInfo* info) const; 255 bool LookUpTypedCallCheck(TypedCallCheckInfo* info) const; 256 GateRef LookUpFrameState() const; 257 258 DependChainInfo* UpdateElement(ElementInfo* info, GateRef gate); 259 DependChainInfo* UpdateProperty(PropertyInfo* info, GateRef gate); 260 DependChainInfo* UpdateArrayLength(ArrayLengthInfo* info, GateRef gate); 261 DependChainInfo* UpdatePrimitiveTypeCheck(PrimitiveTypeCheckInfo* info); 262 DependChainInfo* UpdateInt32OverflowCheck(Int32OverflowCheckInfo* info); 263 DependChainInfo* UpdateArrayCheck(ArrayCheckInfo* info); 264 DependChainInfo* UpdateStableArrayCheck(StableArrayCheckInfo* info); 265 DependChainInfo* UpdateTypedArrayCheck(TypedArrayCheckInfo* info); 266 DependChainInfo* UpdateObjectTypeCheck(ObjectTypeCheckInfo* info); 267 DependChainInfo* UpdateIndexCheck(IndexCheckInfo* info); 268 DependChainInfo* UpdateTypedCallCheck(TypedCallCheckInfo* info); 269 DependChainInfo* UpdateFrameState(GateRef gate); 270 DependChainInfo* UpdateWrite(); 271 272 bool Empty() const; 273 bool Equal(DependChainInfo* that); 274 template<typename K, typename V> 275 ChunkMap<K, V>* MergeMap(ChunkMap<K, V>* thisMap, ChunkMap<K, V>* thatMap); 276 template<typename K> 277 ChunkSet<K>* MergeSet(ChunkSet<K>* thisSet, ChunkSet<K>* thatSet); 278 DependChainInfo* Merge(DependChainInfo* that); 279 280 private: 281 ChunkMap<ElementInfo, GateRef>* elementMap_ {nullptr}; 282 ChunkMap<PropertyInfo, GateRef>* propertyMap_ {nullptr}; 283 ChunkMap<ArrayLengthInfo, GateRef>* arrayLengthMap_ {nullptr}; 284 ChunkSet<PrimitiveTypeCheckInfo>* primitiveTypeCheckSet_ {nullptr}; 285 ChunkSet<Int32OverflowCheckInfo>* int32OverflowCheckSet_ {nullptr}; 286 ChunkSet<ArrayCheckInfo>* arrayCheckSet_ {nullptr}; 287 ChunkSet<StableArrayCheckInfo>* stableArrayCheckSet_ {nullptr}; 288 ChunkSet<TypedArrayCheckInfo>* typedArrayCheckSet_ {nullptr}; 289 ChunkSet<ObjectTypeCheckInfo>* objectTypeCheckSet_ {nullptr}; 290 ChunkSet<IndexCheckInfo>* indexCheckSet_ {nullptr}; 291 ChunkSet<TypedCallCheckInfo>* typedCallCheckSet_ {nullptr}; 292 GateRef frameState_ {Circuit::NullGate()}; 293 Chunk* chunk_; 294 }; 295 296 class EarlyElimination { 297 public: EarlyElimination(Circuit * circuit,bool enableLog,const std::string & name,NativeAreaAllocator * allocator)298 EarlyElimination(Circuit *circuit, bool enableLog, const std::string& name, NativeAreaAllocator *allocator) 299 : circuit_(circuit), acc_(circuit), enableLog_(enableLog), 300 methodName_(name), chunk_(allocator), dependInfos_(&chunk_), stateSplits_(&chunk_) {} 301 302 ~EarlyElimination() = default; 303 304 void Run(); 305 306 private: IsLogEnabled()307 bool IsLogEnabled() const 308 { 309 return enableLog_; 310 } 311 GetMethodName()312 const std::string& GetMethodName() const 313 { 314 return methodName_; 315 } 316 GetChunk()317 Chunk *GetChunk() const 318 { 319 return const_cast<Chunk *>(&chunk_); 320 } 321 322 ElementInfo* GetElementInfo(GateRef gate) const; 323 PropertyInfo* GetPropertyInfo(GateRef gate) const; 324 ArrayLengthInfo* GetArrayLengthInfo(GateRef gate) const; 325 PrimitiveTypeCheckInfo* GetPrimitiveTypeCheckInfo(GateRef gate) const; 326 Int32OverflowCheckInfo* GetInt32OverflowCheckInfo(GateRef gate) const; 327 ArrayCheckInfo* GetArrayCheckInfo(GateRef gate) const; 328 StableArrayCheckInfo* GetStableArrayCheckInfo(GateRef gate) const; 329 TypedArrayCheckInfo* GetTypedArrayCheckInfo(GateRef gate) const; 330 ObjectTypeCheckInfo* GetObjectTypeCheckInfo(GateRef gate) const; 331 IndexCheckInfo* GetIndexCheckInfo(GateRef gate) const; 332 TypedCallCheckInfo* GetTypedCallCheckInfo(GateRef gate) const; 333 334 bool IsSideEffectLoop(GateRef gate); 335 336 void TryEliminate(GateRef gate); 337 void TryEliminateElement(GateRef gate); 338 void TryEliminateProperty(GateRef gate); 339 void TryEliminateArrayLength(GateRef gate); 340 void TryEliminatePrimitiveTypeCheck(GateRef gate); 341 void TryEliminateInt32OverflowCheck(GateRef gate); 342 void TryEliminateArrayCheck(GateRef gate); 343 void TryEliminateStableArrayCheck(GateRef gate); 344 void TryEliminateTypedArrayCheck(GateRef gate); 345 void TryEliminateObjectTypeCheck(GateRef gate); 346 void TryEliminateIndexCheck(GateRef gate); 347 void TryEliminateTypedCallCheck(GateRef gate); 348 void TryEliminateStateSplitAndFrameState(GateRef gate); 349 void TryEliminateDependSelector(GateRef gate); 350 void TryEliminateDependAnd(GateRef gate); 351 void TryEliminateOther(GateRef gate); 352 353 bool IsTrustedType(GateRef gate) const; 354 bool IsPrimitiveTypeCheck(GateRef gate) const; 355 void TrustedTypePropagate(ChunkQueue<GateRef>& workList, const ChunkVector<GateRef>& checkList); 356 void RemoveGate(GateRef gate, GateRef value); 357 void RemoveRedundantGate(); 358 void RemoveTypeTrustedCheck(); 359 360 Circuit *circuit_ {nullptr}; 361 GateAccessor acc_; 362 bool enableLog_ {false}; 363 std::string methodName_; 364 Chunk chunk_; 365 ChunkVector<DependChainInfo*> dependInfos_; 366 ChunkVector<GateRef> stateSplits_; 367 GateId maxId_ {0}; 368 }; 369 } // panda::ecmascript::kungfu 370 #endif // ECMASCRIPT_COMPILER_EARLY_ELIMINATION_H