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_FRAME_STATE_H 17 #define ECMASCRIPT_COMPILER_FRAME_STATE_H 18 19 #include "ecmascript/compiler/base/bit_set.h" 20 #include "ecmascript/compiler/circuit.h" 21 #include "ecmascript/compiler/gate.h" 22 #include "ecmascript/compiler/gate_accessor.h" 23 #include "ecmascript/compiler/pgo_type/pgo_type_recorder.h" 24 #include "ecmascript/jspandafile/method_literal.h" 25 26 namespace panda::ecmascript::kungfu { 27 class BytecodeCircuitBuilder; 28 struct BytecodeRegion; 29 30 class FrameLiveOut { 31 public: FrameLiveOut(Chunk * chunk,size_t numVregs)32 explicit FrameLiveOut(Chunk* chunk, size_t numVregs) 33 : liveout_(chunk, numVregs), defRegisters_(chunk, numVregs) {} 34 SetBit(size_t index)35 void SetBit(size_t index) 36 { 37 liveout_.SetBit(index); 38 } 39 ClearBit(size_t index)40 void ClearBit(size_t index) 41 { 42 liveout_.ClearBit(index); 43 } 44 TestBit(size_t index)45 bool TestBit(size_t index) const 46 { 47 return liveout_.TestBit(index); 48 } 49 CopyFrom(FrameLiveOut * other)50 void CopyFrom(FrameLiveOut *other) 51 { 52 liveout_.CopyFrom(other->liveout_); 53 } 54 MergeLiveout(FrameLiveOut * other)55 bool MergeLiveout(FrameLiveOut *other) 56 { 57 return liveout_.UnionWithChanged(other->liveout_); 58 } 59 Reset()60 void Reset() 61 { 62 return liveout_.Reset(); 63 } 64 65 private: 66 // [numVRegs_] [extra args] [numArgs_] [accumulator] 67 BitSet liveout_; 68 BitSet defRegisters_; 69 friend class BlockLoopAnalysis; 70 friend class FrameStateBuilder; 71 }; 72 73 class FrameContext { 74 public: FrameContext(Chunk * chunk,size_t numVregs)75 explicit FrameContext(Chunk* chunk, size_t numVregs) 76 : values_(numVregs, chunk) {} 77 ValuesAt(size_t index)78 GateRef ValuesAt(size_t index) const 79 { 80 ASSERT(index < values_.size()); 81 return values_[index]; 82 } 83 SetValuesAt(size_t index,GateRef gate)84 void SetValuesAt(size_t index, GateRef gate) 85 { 86 ASSERT(index < values_.size()); 87 values_[index] = gate; 88 } 89 CopyCurrentStatus(FrameContext * other)90 void CopyCurrentStatus(FrameContext *other) 91 { 92 currentState_ = other->currentState_; 93 currentDepend_ = other->currentDepend_; 94 needStateSplit_ = other->needStateSplit_; 95 } 96 private: 97 // [numVRegs_] [extra args] [numArgs_] [accumulator] 98 ChunkVector<GateRef> values_; 99 GateRef currentState_ {Circuit::NullGate()}; 100 GateRef currentDepend_ {Circuit::NullGate()}; 101 GateRef loopBackState_ {Circuit::NullGate()}; 102 GateRef loopBackDepend_ {Circuit::NullGate()}; 103 GateRef mergeState_ {Circuit::NullGate()}; 104 GateRef mergeDepend_ {Circuit::NullGate()}; 105 // number of merged phi nodes 106 size_t currentIndex_ {0}; 107 // index of next loop merge phi 108 size_t loopBackIndex_ {0}; 109 // index of next merge phi 110 size_t mergeIndex_ {0}; 111 bool needStateSplit_ {false}; 112 friend class FrameStateBuilder; 113 friend class BlockLoopAnalysis; 114 }; 115 116 struct MergeStateDependInfo { 117 GateRef state; 118 GateRef depend; 119 size_t index; 120 }; 121 122 class FrameStateBuilder { 123 public: 124 FrameStateBuilder(BytecodeCircuitBuilder *builder, 125 Circuit *circuit, const MethodLiteral *literal); 126 ~FrameStateBuilder(); 127 128 void DoBytecodeAnalysis(); 129 void AnalyzeLiveness(); 130 void AdvanceToNextBc(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId); 131 void UpdateFrameValues(const BytecodeInfo &bytecodeInfo, uint32_t bcId, 132 GateRef gate); 133 void UpdateMoveValues(const BytecodeInfo &bytecodeInfo); 134 void UpdateStateDepend(GateRef state, GateRef depend); 135 FrameLiveOut *GetOrOCreateBCEndLiveOut(uint32_t bcIndex); 136 FrameLiveOut *GetOrOCreateBBLiveOut(size_t bbIndex); GetCurrentState()137 GateRef GetCurrentState() const 138 { 139 return liveContext_->currentState_; 140 } 141 GetCurrentDepend()142 GateRef GetCurrentDepend() const 143 { 144 return liveContext_->currentDepend_; 145 } 146 void MergeIntoSuccessor(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 147 void AdvanceToNextBB(const BytecodeRegion &bb, bool isOsrLoopExit = false); 148 void InitEntryBB(const BytecodeRegion &bb); 149 GetRpoList()150 ChunkDeque<size_t>& GetRpoList() 151 { 152 return rpoList_; 153 } 154 HasLoop()155 bool HasLoop() const 156 { 157 return numLoops_ > 0; 158 } 159 UpdateAccumulator(GateRef gate)160 void UpdateAccumulator(GateRef gate) 161 { 162 UpdateVirtualRegister(accumulatorIndex_, gate); 163 } 164 165 void SetOsrLoopHeadBB(const BytecodeRegion &loopHeadOfOSR); 166 167 bool IsOsrLoopExit(const BytecodeRegion &curBB); 168 169 bool OutOfOsrLoop(const BytecodeRegion &curBB); 170 171 size_t GetOsrLoopHeadBBId() const; 172 IsContextExists(uint32_t bbIndex)173 bool IsContextExists(uint32_t bbIndex) const 174 { 175 ASSERT(bbIndex < bbFrameContext_.size()); 176 return bbFrameContext_[bbIndex] != nullptr; 177 } 178 179 FrameContext *GetOrOCreateMergedContext(uint32_t bbIndex); 180 181 private: 182 static constexpr size_t FIXED_ARGS = 2; // ac & env 183 struct LoopInfo { 184 size_t loopIndex {0}; 185 size_t loopHeadId {0}; 186 size_t numLoopBacks {0}; 187 size_t sortIndx {0}; 188 LoopInfo* parentInfo {nullptr}; 189 BitSet* loopBodys {nullptr}; 190 ChunkVector<BytecodeRegion*>* loopExits {nullptr}; 191 BitSet* loopAssignment {nullptr}; 192 FrameContext* mergedContext {nullptr}; 193 }; 194 195 void BuildPostOrderList(size_t size); 196 bool ComputeLiveOut(size_t bbId); 197 void ComputeLiveState(); 198 void ComputeLiveOutBC(const BytecodeInfo &bytecodeInfo); 199 bool MergeIntoPredBC(uint32_t predPc); 200 bool MergeFromSuccBB(size_t bbId); 201 void MergeFromCatchBB(size_t bbId); 202 GetFrameLiveoutAfter(uint32_t bcId)203 FrameLiveOut *GetFrameLiveoutAfter(uint32_t bcId) 204 { 205 return bcEndStateLiveouts_[bcId]; 206 } 207 GetFrameLiveoutBefore(size_t bbId)208 FrameLiveOut *GetFrameLiveoutBefore(size_t bbId) 209 { 210 return bbBeginStateLiveouts_[bbId]; 211 } 212 ValuesAt(size_t index)213 GateRef ValuesAt(size_t index) const 214 { 215 return liveContext_->ValuesAt(index); 216 } 217 ValuesAtAccumulator()218 GateRef ValuesAtAccumulator() const 219 { 220 return ValuesAt(accumulatorIndex_); 221 } 222 UpdateVirtualRegister(size_t index,GateRef gate)223 void UpdateVirtualRegister(size_t index, GateRef gate) 224 { 225 liveContext_->SetValuesAt(index, gate); 226 } 227 GetBcFrameStateCache()228 GateRef GetBcFrameStateCache() 229 { 230 ASSERT(frameStateCache_ != Circuit::NullGate()); 231 auto cache = frameStateCache_; 232 frameStateCache_ = Circuit::NullGate(); 233 return cache; 234 } 235 GetMergedBbContext(uint32_t bbIndex)236 FrameContext *GetMergedBbContext(uint32_t bbIndex) const 237 { 238 ASSERT(bbIndex < bbFrameContext_.size()); 239 return bbFrameContext_[bbIndex]; 240 } 241 242 void FillBcInputs(const BytecodeInfo &bytecodeInfo, GateRef gate); 243 void DumpLiveState(); 244 size_t GetNumOfStatePreds(const BytecodeRegion &bb); 245 GateRef MergeValue(const BytecodeRegion &bb, 246 GateRef currentValue, GateRef nextValue, bool isLoopBack, bool changedInLoop); 247 void NewMerge(const BytecodeRegion &bbNext); 248 void MergeStateDepend(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 249 void CopyLiveoutValues(const BytecodeRegion &bbNext, FrameContext* dest, FrameContext* src); 250 void SaveCurrentContext(const BytecodeRegion &bb); 251 MergeStateDependInfo GetCorrespondingState(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 252 253 void NewLoopExit(const BytecodeRegion &bbNext, BitSet *loopAssignment); 254 size_t ComputeLoopDepth(size_t loopHead); 255 void TryInsertLoopExit(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 256 void ComputeLoopInfo(); 257 void ResizeLoopBody(); 258 void MergeAssignment(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 259 BitSet *GetLoopAssignment(const BytecodeRegion &bb); 260 LoopInfo& GetLoopInfo(const BytecodeRegion &bb); 261 LoopInfo& GetLoopInfo(BytecodeRegion &bb); 262 LoopInfo* GetLoopInfoByLoopBody(const BytecodeRegion &bb); 263 bool IsLoopBackEdge(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 264 bool IsLoopHead(const BytecodeRegion &bb); 265 bool IfLoopNeedMerge(const BytecodeRegion &bb) const; 266 GateRef InitMerge(size_t numOfIns, bool isLoop); 267 bool IsGateNotEmpty(GateRef gate) const; 268 269 GateRef BuildFrameContext(FrameContext* frameContext); 270 void BindStateSplitBefore(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId); 271 void BindStateSplitAfter(const BytecodeInfo &bytecodeInfo, uint32_t bcId, GateRef gate); 272 GateRef BuildFrameValues(FrameContext* frameContext, FrameLiveOut* liveout); 273 GateRef BuildStateSplit(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex); 274 GateRef BuildFrameState(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex); 275 void AddEmptyBlock(BytecodeRegion* bb); 276 FrameContext *GetCachedContext(); 277 278 BytecodeCircuitBuilder *bcBuilder_ {nullptr}; 279 const PGOTypeRecorder *pgoTypeRecorder_ {nullptr}; 280 FrameLiveOut *liveOutResult_ {nullptr}; 281 FrameLiveOut *currentBBliveOut_ {nullptr}; 282 FrameContext *liveContext_ {nullptr}; 283 FrameContext *cachedContext_ {nullptr}; 284 FrameContext *cachedContextBackup_ {nullptr}; 285 size_t numVregs_ {0}; 286 size_t accumulatorIndex_ {0}; 287 size_t envIndex_ {0}; 288 size_t numLoops_ {0}; 289 size_t sortIndx_ {0}; 290 GateRef frameStateCache_ {Circuit::NullGate()}; 291 Circuit *circuit_ {nullptr}; 292 GateAccessor acc_; 293 ChunkVector<FrameLiveOut *> bcEndStateLiveouts_; 294 ChunkVector<FrameLiveOut *> bbBeginStateLiveouts_; 295 ChunkVector<FrameContext *> bbFrameContext_; 296 ChunkVector<LoopInfo> loops_; 297 ChunkDeque<size_t> rpoList_; 298 ChunkVector<size_t> postOrderList_; 299 const BytecodeRegion *loopHeadOfOSR_ {nullptr}; 300 301 friend class BlockLoopAnalysis; 302 friend class SubContextScope; 303 }; 304 } // panda::ecmascript::kungfu 305 #endif // ECMASCRIPT_COMPILER_FRAME_STATE_H 306