1 /* 2 * Copyright (c) 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 ECMASCRIPT_COMPILER_CIRCUIT_OPTIMIZER_H_ 17 #define ECMASCRIPT_COMPILER_CIRCUIT_OPTIMIZER_H_ 18 19 #include <queue> 20 21 #include "ecmascript/base/bit_helper.h" 22 #include "ecmascript/compiler/circuit.h" 23 #include "ecmascript/compiler/gate_accessor.h" 24 25 namespace panda::ecmascript::kungfu { 26 enum class LatticeStatus { 27 TOP, 28 MID, 29 BOT, 30 }; 31 32 class ValueLattice { 33 public: 34 explicit ValueLattice(); 35 explicit ValueLattice(LatticeStatus status); 36 explicit ValueLattice(uint64_t value); 37 ~ValueLattice() = default; 38 [[nodiscard]] bool IsTop() const; 39 [[nodiscard]] bool IsMid() const; 40 [[nodiscard]] bool IsBot() const; 41 [[nodiscard]] LatticeStatus GetStatus() const; 42 [[nodiscard]] std::optional<uint64_t> GetValue() const; 43 ValueLattice Meet(const ValueLattice &other); 44 bool operator==(const ValueLattice &other) const; 45 bool operator!=(const ValueLattice &other) const; 46 bool operator<(const ValueLattice &other) const; 47 bool operator>(const ValueLattice &other) const; 48 bool operator<=(const ValueLattice &other) const; 49 bool operator>=(const ValueLattice &other) const; 50 [[nodiscard]] ValueLattice Implies(const ValueLattice &other) const; 51 void Print(std::ostream &os) const; 52 53 private: 54 uint64_t value_; 55 LatticeStatus status_; 56 }; 57 58 class ReachabilityLattice { 59 public: 60 explicit ReachabilityLattice(); 61 explicit ReachabilityLattice(bool reachable); 62 ~ReachabilityLattice() = default; 63 [[nodiscard]] bool IsReachable() const; 64 [[nodiscard]] bool IsUnreachable() const; 65 bool operator==(const ReachabilityLattice &other) const; 66 bool operator!=(const ReachabilityLattice &other) const; 67 ReachabilityLattice operator+(const ReachabilityLattice &other) const; 68 ReachabilityLattice operator*(const ReachabilityLattice &other) const; 69 [[nodiscard]] ValueLattice Implies(const ValueLattice &other) const; 70 void Print(std::ostream &os) const; 71 72 private: 73 bool reachable_; 74 }; 75 76 class LatticeUpdateRule { 77 public: 78 void Initialize(Circuit *circuit, 79 std::function<ValueLattice &(GateRef)> valueLattice, 80 std::function<ReachabilityLattice &(GateRef)> reachabilityLattice); 81 bool UpdateValueLattice(GateRef gate, const ValueLattice &valueLattice); 82 bool UpdateReachabilityLattice(GateRef gate, const ReachabilityLattice &reachabilityLattice); 83 virtual bool Run(GateRef gate) = 0; LatticeUpdateRule()84 LatticeUpdateRule() : circuit_(nullptr), acc_(circuit_) {} ~LatticeUpdateRule()85 virtual ~LatticeUpdateRule() {} 86 87 protected: 88 std::function<ValueLattice &(GateRef)> valueLatticeMap_; 89 std::function<ReachabilityLattice &(GateRef)> reachabilityLatticeMap_; 90 Circuit *circuit_; 91 GateAccessor acc_; 92 }; 93 94 class LatticeUpdateRuleSCCP : public LatticeUpdateRule { 95 public: ~LatticeUpdateRuleSCCP()96 ~LatticeUpdateRuleSCCP() override {} 97 uint64_t RunBoolArithmetic(bool valueA, bool valueB, OpCode op); 98 template<class T> 99 uint64_t RunFixedPointArithmetic(T valueA, T valueB, OpCode op); 100 template<class T> 101 double RunFloatingPointArithmetic(T valueA, T valueB, OpCode op); 102 uint64_t RunBasicArithmetic(ValueLattice operandA, ValueLattice operandB, OpCode op, MachineType machineType); 103 uint64_t RunFCompareArithmetic(ValueLattice operandA, ValueLattice operandB, 104 FCmpCondition cond, MachineType machineType); 105 uint64_t RunICompareArithmetic(ValueLattice operandA, ValueLattice operandB, 106 ICmpCondition cond, MachineType machineType); 107 uint64_t RunBoolCompare(bool valueA, bool valueB, ICmpCondition cond); 108 template<class T> 109 uint64_t RunFixedPointCompare(T valueA, T valueB, ICmpCondition cond); 110 template<class T> 111 uint64_t RunFloatingPointCompare(T valueA, T valueB, FCmpCondition cond); 112 bool Run(GateRef gate) override; 113 bool RunCircuitRoot(GateRef gate); 114 bool RunStateEntry(GateRef gate); 115 bool RunDependEntry(GateRef gate); 116 bool RunFrameStateEntry(GateRef gate); 117 bool RunReturnList(GateRef gate); 118 bool RunThrowList(GateRef gate); 119 bool RunConstantList(GateRef gate); 120 bool RunAllocaList(GateRef gate); 121 bool RunArgList(GateRef gate); 122 bool RunReturn(GateRef gate); 123 bool RunReturnVoid(GateRef gate); 124 bool RunThrow(GateRef gate); 125 bool RunOrdinaryBlock(GateRef gate); 126 bool RunIfBranch(GateRef gate); 127 bool RunSwitchBranch(GateRef gate); 128 bool RunIfTrue(GateRef gate); 129 bool RunIfFalse(GateRef gate); 130 bool RunSwitchCase(GateRef gate); 131 bool RunDefaultCase(GateRef gate); 132 bool RunMerge(GateRef gate); 133 bool RunLoopBegin(GateRef gate); 134 bool RunLoopBack(GateRef gate); 135 bool RunValueSelector(GateRef gate); 136 bool RunDependSelector(GateRef gate); 137 bool RunDependRelay(GateRef gate); 138 bool RunDependAnd(GateRef gate); 139 bool RunJSBytecode(GateRef gate); 140 bool RunIfSuccess(GateRef gate); 141 bool RunIfException(GateRef gate); 142 bool RunGetException(GateRef gate); 143 bool RunRuntimeCall(GateRef gate); 144 bool RunNoGCRuntimeCall(GateRef gate); 145 bool RunBytecodeCall(GateRef gate); 146 bool RunDebuggerBytecodeCall(GateRef gate); 147 bool RunBuiltinsCall(GateRef gate); 148 bool RunBuiltinsCallWithArgv(GateRef gate); 149 bool RunCall(GateRef gate); 150 bool RunRuntimeCallWithArgv(GateRef gate); 151 bool RunAlloca(GateRef gate); 152 bool RunArg(GateRef gate); 153 bool RunMutableData(GateRef gate); 154 bool RunConstData(GateRef gate); 155 bool RunRelocatableData(GateRef gate); 156 bool RunConstant(GateRef gate); 157 bool RunZExtToIntOrArch(GateRef gate); 158 bool RunSExtToIntOrArch(GateRef gate); 159 bool RunTruncToInt(GateRef gate); 160 bool RunRev(GateRef gate); 161 bool RunAdd(GateRef gate); 162 bool RunSub(GateRef gate); 163 bool RunMul(GateRef gate); 164 bool RunExp(GateRef gate); 165 bool RunSDiv(GateRef gate); 166 bool RunSMod(GateRef gate); 167 bool RunUDiv(GateRef gate); 168 bool RunUMod(GateRef gate); 169 bool RunFDiv(GateRef gate); 170 bool RunFMod(GateRef gate); 171 bool RunAnd(GateRef gate); 172 bool RunXor(GateRef gate); 173 bool RunOr(GateRef gate); 174 bool RunLSL(GateRef gate); 175 bool RunLSR(GateRef gate); 176 bool RunASR(GateRef gate); 177 bool RunIcmp(GateRef gate); 178 bool RunFcmp(GateRef gate); 179 bool RunLoad(GateRef gate); 180 bool RunStore(GateRef gate); 181 bool RunTaggedToInt64(GateRef gate); 182 bool RunInt64ToTagged(GateRef gate); 183 bool RunSignedIntToFloat(GateRef gate); 184 bool RunUnsignedIntToFloat(GateRef gate); 185 bool RunFloatToSignedInt(GateRef gate); 186 bool RunUnsignedFloatToInt(GateRef gate); 187 bool RunBitCast(GateRef gate); 188 }; 189 190 class SubgraphRewriteRule { 191 public: SubgraphRewriteRule()192 SubgraphRewriteRule() : circuit_(nullptr), acc_(circuit_) 193 { 194 } 195 void Initialize(Circuit *circuit); 196 virtual bool Run(GateRef gate) = 0; 197 198 protected: 199 Circuit *circuit_ = nullptr; 200 GateAccessor acc_; 201 }; 202 203 class SubgraphRewriteRuleCP : public SubgraphRewriteRule { 204 public: 205 bool Run(GateRef gate) override; 206 bool RunAdd(GateRef gate); 207 bool RunSub(GateRef gate); 208 }; 209 210 class LatticeEquationsSystemSolverFramework { 211 public: 212 explicit LatticeEquationsSystemSolverFramework(LatticeUpdateRule *latticeUpdateRule); 213 ~LatticeEquationsSystemSolverFramework() = default; 214 bool Run(Circuit *circuit, bool enableLogging = false); 215 [[nodiscard]] const ValueLattice &GetValueLattice(GateRef gate) const; 216 [[nodiscard]] const ReachabilityLattice &GetReachabilityLattice(GateRef gate) const; 217 218 private: 219 Circuit *circuit_; 220 GateAccessor acc_; 221 LatticeUpdateRule *latticeUpdateRule_; 222 std::map<GateRef, ValueLattice> valueLatticesMap_; 223 std::map<GateRef, ReachabilityLattice> reachabilityLatticesMap_; 224 }; 225 226 class SubGraphRewriteFramework { 227 public: 228 explicit SubGraphRewriteFramework(SubgraphRewriteRule *subgraphRewriteRule); 229 ~SubGraphRewriteFramework() = default; 230 bool Run(Circuit *circuit, bool enableLogging = false); 231 232 private: 233 Circuit *circuit_; 234 GateAccessor acc_; 235 SubgraphRewriteRule *subgraphRewriteRule_; 236 }; 237 238 class Partition; 239 240 class PartitionNode { 241 public: 242 PartitionNode(); 243 PartitionNode(GateRef gate); 244 ~PartitionNode() = default; 245 std::shared_ptr<PartitionNode> GetPrev() const; 246 std::shared_ptr<PartitionNode> GetNext() const; 247 std::shared_ptr<Partition> GetBelong() const; 248 GateRef GetGate() const; 249 void SetPrev(std::shared_ptr<PartitionNode> prev); 250 void SetNext(std::shared_ptr<PartitionNode> next); 251 void SetBelong(std::shared_ptr<Partition> belong); 252 bool ExistUseByIndex(uint32_t index) const; 253 void SetUseByIndex(uint32_t index, std::shared_ptr<PartitionNode> node); 254 void GetUsesVector(std::vector<std::pair<uint32_t, std::vector<std::shared_ptr<PartitionNode>>>> &uses) const; 255 private: 256 std::weak_ptr<PartitionNode> prev_; 257 std::weak_ptr<PartitionNode> next_; 258 std::weak_ptr<Partition> belong_; 259 GateRef gate_; 260 std::map<uint32_t, std::vector<std::shared_ptr<PartitionNode>>> indexToUses_; 261 }; 262 263 class Partition { 264 public: 265 Partition(); 266 ~Partition() = default; 267 std::shared_ptr<PartitionNode> GetHead() const; 268 void SetHead(std::shared_ptr<PartitionNode> head); 269 void SetTouched(); 270 void SetNotTouched(); 271 void SetOnWorkList(); 272 void SetNotOnWorkList(); 273 bool IsTouched() const; 274 bool IsOnWorkList() const; 275 uint32_t GetSize() const; 276 void SizeUp(); 277 void SizeDown(); 278 void AddTouchedNode(std::shared_ptr<PartitionNode> node); 279 void CleanTouchedNode(); 280 size_t GetTouchedSize() const; 281 void Insert(std::shared_ptr<PartitionNode> node); 282 void Delete(std::shared_ptr<PartitionNode> node); 283 std::shared_ptr<Partition> SplitByTouched(); 284 void MergeUses(std::map<uint32_t, std::vector<std::shared_ptr<PartitionNode>>> &indexToUses) const; 285 private: 286 std::weak_ptr<PartitionNode> head_; 287 bool isTouched_; 288 bool onWorkList_; 289 uint32_t size_; 290 std::vector<std::shared_ptr<PartitionNode>> touched_; 291 }; 292 293 class GlobalValueNumbering { 294 public: 295 GlobalValueNumbering(Circuit *circuit, bool enableLog); 296 ~GlobalValueNumbering() = default; 297 void GetPartitionNodes(std::vector<std::shared_ptr<PartitionNode>> &nodes); 298 void SplitByOpCode(const std::vector<std::shared_ptr<PartitionNode>> &nodes, 299 std::vector<std::shared_ptr<Partition>> &partitions); 300 uint32_t GetMaxIndex(std::shared_ptr<Partition> partition) const; 301 void TrySplit(std::queue<std::shared_ptr<Partition>> &workList, 302 std::vector<std::shared_ptr<Partition>> &partitions); 303 void EliminateRedundantGates(const std::vector<std::shared_ptr<Partition>> &partitions); 304 void Run(); 305 void Print(const std::vector<std::shared_ptr<Partition>> &partitions); 306 private: IsLogEnabled()307 bool IsLogEnabled() const 308 { 309 return enableLog_; 310 } 311 GateAccessor acc_; 312 bool enableLog_ {false}; 313 }; 314 } // namespace panda::ecmascript::kungfu 315 316 #endif // ECMASCRIPT_COMPILER_CIRCUIT_OPTIMIZER_H_ 317