1 /* 2 * Copyright (c) 2021 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_GATE_H 17 #define ECMASCRIPT_COMPILER_GATE_H 18 19 #include <array> 20 #include <iostream> 21 #include <map> 22 #include <optional> 23 #include <set> 24 #include <sstream> 25 #include <string> 26 #include <type_traits> 27 #include <vector> 28 29 #include "ecmascript/compiler/type.h" 30 #include "libpandabase/macros.h" 31 32 namespace panda::ecmascript::kungfu { 33 using GateRef = int32_t; // for external users 34 using GateId = uint32_t; 35 using GateOp = uint8_t; 36 using GateMark = uint8_t; 37 using TimeStamp = uint8_t; 38 using SecondaryOp = uint8_t; 39 using BitField = uint64_t; 40 using OutIdx = uint32_t; 41 class Gate; 42 struct Properties; 43 class BytecodeCircuitBuilder; 44 45 enum MachineType { // bit whith 46 NOVALUE, 47 ANYVALUE, 48 ARCH, 49 FLEX, 50 I1, 51 I8, 52 I16, 53 I32, 54 I64, 55 F32, 56 F64, 57 }; 58 59 std::string MachineTypeToStr(MachineType machineType); 60 61 class OpCode { 62 public: 63 enum Op : GateOp { 64 // SHARED 65 NOP, 66 CIRCUIT_ROOT, 67 STATE_ENTRY, 68 DEPEND_ENTRY, 69 FRAMESTATE_ENTRY, 70 RETURN_LIST, 71 THROW_LIST, 72 CONSTANT_LIST, 73 ALLOCA_LIST, 74 ARG_LIST, 75 RETURN, 76 RETURN_VOID, 77 THROW, 78 ORDINARY_BLOCK, 79 IF_BRANCH, 80 SWITCH_BRANCH, 81 IF_TRUE, 82 IF_FALSE, 83 SWITCH_CASE, 84 DEFAULT_CASE, 85 MERGE, 86 LOOP_BEGIN, 87 LOOP_BACK, 88 VALUE_SELECTOR, 89 DEPEND_SELECTOR, 90 DEPEND_RELAY, 91 DEPEND_AND, 92 // High Level IR 93 JS_BYTECODE, 94 IF_SUCCESS, 95 IF_EXCEPTION, 96 GET_EXCEPTION, 97 // Middle Level IR 98 RUNTIME_CALL, 99 CALL, 100 BYTECODE_CALL, 101 ALLOCA, 102 ARG, 103 MUTABLE_DATA, 104 RELOCATABLE_DATA, 105 CONST_DATA, 106 CONSTANT, 107 ZEXT_TO_INT64, 108 ZEXT_TO_INT32, 109 ZEXT_TO_INT16, 110 SEXT_TO_INT64, 111 SEXT_TO_INT32, 112 TRUNC_TO_INT32, 113 TRUNC_TO_INT1, 114 REV, 115 ADD, 116 SUB, 117 MUL, 118 EXP, 119 SDIV, 120 SMOD, 121 UDIV, 122 UMOD, 123 FDIV, 124 FMOD, 125 AND, 126 XOR, 127 OR, 128 LSL, 129 LSR, 130 ASR, 131 SLT, 132 SLE, 133 SGT, 134 SGE, 135 ULT, 136 ULE, 137 UGT, 138 UGE, 139 FLT, 140 FLE, 141 FGT, 142 FGE, 143 EQ, 144 NE, 145 LOAD, 146 STORE, 147 TAGGED_TO_INT64, 148 INT64_TO_TAGGED, 149 SIGNED_INT_TO_FLOAT, 150 UNSIGNED_INT_TO_FLOAT, 151 FLOAT_TO_SIGNED_INT, 152 UNSIGNED_FLOAT_TO_INT, 153 BITCAST, 154 }; 155 156 OpCode() = default; OpCode(Op op)157 explicit constexpr OpCode(Op op) : op_(op) {} Op()158 operator Op() const 159 { 160 return op_; 161 } 162 explicit operator bool() const = delete; 163 [[nodiscard]] Properties GetProperties() const; 164 [[nodiscard]] std::array<size_t, 4> GetOpCodeNumInsArray(BitField bitfield) const; 165 [[nodiscard]] size_t GetOpCodeNumIns(BitField bitfield) const; 166 [[nodiscard]] MachineType GetMachineType() const; 167 [[nodiscard]] MachineType GetInMachineType(BitField bitfield, size_t idx) const; 168 [[nodiscard]] OpCode GetInStateCode(size_t idx) const; 169 [[nodiscard]] std::string Str() const; 170 [[nodiscard]] bool IsRoot() const; 171 [[nodiscard]] bool IsProlog() const; 172 [[nodiscard]] bool IsFixed() const; 173 [[nodiscard]] bool IsSchedulable() const; 174 [[nodiscard]] bool IsState() const; // note: IsState(STATE_ENTRY) == false 175 [[nodiscard]] bool IsGeneralState() const; 176 [[nodiscard]] bool IsTerminalState() const; 177 [[nodiscard]] bool IsCFGMerge() const; 178 [[nodiscard]] bool IsControlCase() const; 179 [[nodiscard]] bool IsLoopHead() const; 180 [[nodiscard]] bool IsNop() const; 181 ~OpCode() = default; 182 183 private: 184 Op op_; 185 }; 186 187 struct Properties { 188 MachineType returnValue; 189 std::optional<std::pair<std::vector<OpCode>, bool>> statesIn; 190 size_t dependsIn; 191 std::optional<std::pair<std::vector<MachineType>, bool>> valuesIn; 192 std::optional<OpCode> states; 193 }; 194 195 enum MarkCode : GateMark { 196 NO_MARK, 197 VISITED, 198 FINISHED, 199 }; 200 201 MachineType JSMachineType(); 202 203 class Out { 204 public: 205 Out() = default; 206 void SetNextOut(const Out *ptr); 207 [[nodiscard]] Out *GetNextOut(); 208 [[nodiscard]] const Out *GetNextOutConst() const; 209 void SetPrevOut(const Out *ptr); 210 [[nodiscard]] Out *GetPrevOut(); 211 [[nodiscard]] const Out *GetPrevOutConst() const; 212 void SetIndex(OutIdx idx); 213 [[nodiscard]] OutIdx GetIndex() const; 214 [[nodiscard]] Gate *GetGate(); 215 [[nodiscard]] const Gate *GetGateConst() const; 216 void SetPrevOutNull(); 217 [[nodiscard]] bool IsPrevOutNull() const; 218 void SetNextOutNull(); 219 [[nodiscard]] bool IsNextOutNull() const; 220 ~Out() = default; 221 222 private: 223 OutIdx idx_; 224 GateRef nextOut_; 225 GateRef prevOut_; 226 }; 227 228 class In { 229 public: 230 In() = default; 231 void SetGate(const Gate *ptr); 232 [[nodiscard]] Gate *GetGate(); 233 [[nodiscard]] const Gate *GetGateConst() const; 234 void SetGateNull(); 235 [[nodiscard]] bool IsGateNull() const; 236 ~In() = default; 237 238 private: 239 GateRef gatePtr_; 240 }; 241 242 // Gate structure 243 // for example: 244 // ``` 245 // g0 = op0(...) 246 // g1 = op1(...) 247 // g2 = op2(g0, g1) 248 // g3 = op3(g2) 249 // g4 = op4(g2, g0, g1) 250 // g5 = op5(g3, g4) 251 252 // +---- out[1] ----+---- out[0] ----+-------- g2 --------+-- in[0] --+-- in[1] --+ 253 // | | | | | | 254 // | prev=null | prev=null | ... | | | 255 // | idx=1 | idx=0 | | g0 | g1 | 256 // | next=g4.out[2] | next=g4.out[1] | firstOut=g4.out[0] | | | 257 // | | | | | | 258 // +----------------+----------------+--------------------+-----------+-----------+ 259 // /\ /\ 260 // || || 261 // || || 262 // || || +---- out[0] ----+-------- g3 --------+-- in[0] --+ 263 // || || | | | | 264 // || || | prev=g4.out[0] | ... | | 265 // || || | idx=0 | | g2 | 266 // || || | next=null | firstOut=g5.out[0] | | 267 // || || | | | | 268 // || || +----------------+--------------------+-----------+ 269 // || || /\ 270 // || || || 271 // || || || 272 // \/ \/ \/ 273 // +---- out[2] ----+---- out[1] ----+---- out[0] ----+-------- g4 --------+-- in[0] --+-- in[1] --+-- in[2] --+ 274 // | | | | | | | | 275 // | prev=g2.out[1] | prev=g2.out[0] | prev=null | ... | | | | 276 // | idx=2 | idx=1 | idx=0 | | g2 | g0 | g1 | 277 // | next=null | next=null | next=g3.out[0] | firstOut=g5.out[1] | | | | 278 // | | | | | | | | 279 // +----------------+----------------+----------------+--------------------+-----------+-----------+-----------+ 280 // ``` 281 282 class Gate { 283 public: 284 // NOLINTNEXTLINE(modernize-avoid-c-arrays) 285 Gate(GateId id, OpCode opcode, MachineType bitValue, BitField bitfield, Gate *inList[], GateType type, 286 MarkCode mark); 287 Gate(GateId id, OpCode opcode, BitField bitfield, Gate *inList[], GateType type, MarkCode mark); 288 [[nodiscard]] static size_t GetGateSize(size_t numIns); 289 [[nodiscard]] size_t GetGateSize() const; 290 [[nodiscard]] static size_t GetOutListSize(size_t numIns); 291 [[nodiscard]] size_t GetOutListSize() const; 292 [[nodiscard]] static size_t GetInListSize(size_t numIns); 293 [[nodiscard]] size_t GetInListSize() const; 294 void NewIn(size_t idx, Gate *in); 295 void ModifyIn(size_t idx, Gate *in); 296 void DeleteIn(size_t idx); 297 void DeleteGate(); 298 [[nodiscard]] Out *GetOut(size_t idx); 299 [[nodiscard]] Out *GetFirstOut(); 300 [[nodiscard]] const Out *GetFirstOutConst() const; 301 // note: GetFirstOut() is not equal to GetOut(0) 302 // note: behavior of GetFirstOut() is undefined when there are no Outs 303 // note: use IsFirstOutNull() to check first if there may be no Outs 304 void SetFirstOut(const Out *firstOut); 305 void SetFirstOutNull(); 306 [[nodiscard]] bool IsFirstOutNull() const; 307 [[nodiscard]] In *GetIn(size_t idx); 308 [[nodiscard]] const In *GetInConst(size_t idx) const; 309 [[nodiscard]] Gate *GetInGate(size_t idx); 310 [[nodiscard]] const Gate *GetInGateConst(size_t idx) const; 311 // note: behavior of GetInGate(idx) is undefined when Ins[idx] is deleted or not assigned 312 // note: use IsInGateNull(idx) to check first if Ins[idx] may be deleted or not assigned 313 [[nodiscard]] bool IsInGateNull(size_t idx) const; 314 [[nodiscard]] OpCode GetOpCode() const; 315 void SetOpCode(OpCode opcode); 316 [[nodiscard]] GateType GetGateType() const; 317 void SetGateType(GateType type); 318 [[nodiscard]] GateId GetId() const; 319 [[nodiscard]] size_t GetNumIns() const; 320 [[nodiscard]] std::array<size_t, 4> GetNumInsArray() const; 321 [[nodiscard]] BitField GetBitField() const; 322 void SetBitField(BitField bitfield); 323 void AppendIn(const Gate *in); // considered very slow 324 void Print(std::string bytecode = "", bool inListPreview = false, size_t highlightIdx = -1) const; 325 size_t PrintInGate(size_t numIns, size_t idx, size_t size, bool inListPreview, size_t highlightIdx, 326 bool isEnd = false) const; 327 void PrintByteCode(std::string bytecode) const; 328 std::optional<std::pair<std::string, size_t>> CheckNullInput() const; 329 std::optional<std::pair<std::string, size_t>> CheckStateInput() const; 330 std::optional<std::pair<std::string, size_t>> CheckValueInput() const; 331 std::optional<std::pair<std::string, size_t>> CheckDependInput() const; 332 std::optional<std::pair<std::string, size_t>> CheckStateOutput() const; 333 std::optional<std::pair<std::string, size_t>> CheckBranchOutput() const; 334 std::optional<std::pair<std::string, size_t>> CheckNOP() const; 335 std::optional<std::pair<std::string, size_t>> CheckSelector() const; 336 std::optional<std::pair<std::string, size_t>> CheckRelay() const; 337 std::optional<std::pair<std::string, size_t>> SpecialCheck() const; 338 [[nodiscard]] bool Verify() const; 339 [[nodiscard]] MarkCode GetMark(TimeStamp stamp) const; 340 void SetMark(MarkCode mark, TimeStamp stamp); 341 [[nodiscard]] MachineType GetMachineType() const; 342 void SetMachineType(MachineType MachineType); 343 std::string MachineTypeStr(MachineType machineType) const; 344 std::string GateTypeStr(GateType gateType) const; 345 ~Gate() = default; 346 347 private: 348 // ... 349 // out(2) 350 // out(1) 351 // out(0) 352 GateId id_ {0}; 353 OpCode opcode_; 354 MachineType bitValue_ = MachineType::NOVALUE; 355 GateType type_; 356 TimeStamp stamp_; 357 MarkCode mark_; 358 BitField bitfield_; 359 GateRef firstOut_; 360 // in(0) 361 // in(1) 362 // in(2) 363 // ... 364 }; 365 } // namespace panda::ecmascript::kungfu 366 367 #endif // ECMASCRIPT_COMPILER_GATE_H 368