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 BuildStateSplitBeforeCatch(uint32_t bcId, FrameLiveOut *liveout); 129 void UpdateCatchState(uint32_t bcId, FrameLiveOut* liveout); 130 void DoBytecodeAnalysis(); 131 void AnalyzeLiveness(); 132 void AdvanceToNextBc(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId); 133 void UpdateFrameValues(const BytecodeInfo &bytecodeInfo, uint32_t bcId, 134 GateRef gate); 135 void UpdateMoveValues(const BytecodeInfo &bytecodeInfo); 136 void UpdateStateDepend(GateRef state, GateRef depend); 137 FrameLiveOut *GetOrOCreateBCEndLiveOut(uint32_t bcIndex); 138 FrameLiveOut *GetOrOCreateBBLiveOut(size_t bbIndex); GetCurrentState()139 GateRef GetCurrentState() const 140 { 141 return liveContext_->currentState_; 142 } 143 GetCurrentDepend()144 GateRef GetCurrentDepend() const 145 { 146 return liveContext_->currentDepend_; 147 } 148 void MergeIntoSuccessor(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 149 void AdvanceToNextBB(const BytecodeRegion &bb, bool isOsrLoopExit = false); 150 void InitEntryBB(const BytecodeRegion &bb); 151 GetRpoList()152 ChunkDeque<size_t>& GetRpoList() 153 { 154 return rpoList_; 155 } 156 HasLoop()157 bool HasLoop() const 158 { 159 return numLoops_ > 0; 160 } 161 UpdateAccumulator(GateRef gate)162 void UpdateAccumulator(GateRef gate) 163 { 164 UpdateVirtualRegister(accumulatorIndex_, gate); 165 } 166 167 void SetOsrLoopHeadBB(const BytecodeRegion &loopHeadOfOSR); 168 169 bool IsOsrLoopExit(const BytecodeRegion &curBB); 170 171 bool OutOfOsrLoop(const BytecodeRegion &curBB); 172 173 size_t GetOsrLoopHeadBBId() const; 174 IsContextExists(uint32_t bbIndex)175 bool IsContextExists(uint32_t bbIndex) const 176 { 177 ASSERT(bbIndex < bbFrameContext_.size()); 178 return bbFrameContext_[bbIndex] != nullptr; 179 } 180 181 FrameContext *GetOrOCreateMergedContext(uint32_t bbIndex); 182 GetBcFrameStateCache()183 GateRef GetBcFrameStateCache() 184 { 185 ASSERT(frameStateCache_ != Circuit::NullGate()); 186 auto cache = frameStateCache_; 187 frameStateCache_ = Circuit::NullGate(); 188 return cache; 189 } 190 191 private: 192 static constexpr size_t FIXED_ARGS = 2; // ac & env 193 struct LoopInfo { 194 size_t loopIndex {0}; 195 size_t loopHeadId {0}; 196 size_t numLoopBacks {0}; 197 size_t sortIndx {0}; 198 LoopInfo* parentInfo {nullptr}; 199 BitSet* loopBodys {nullptr}; 200 ChunkVector<BytecodeRegion*>* loopExits {nullptr}; 201 BitSet* loopAssignment {nullptr}; 202 FrameContext* mergedContext {nullptr}; 203 }; 204 205 void BuildPostOrderList(size_t size); 206 bool ComputeLiveOut(size_t bbId); 207 void ComputeLiveState(); 208 void ComputeLiveOutBC(const BytecodeInfo &bytecodeInfo); 209 bool MergeIntoPredBC(uint32_t predPc); 210 bool MergeFromSuccBB(size_t bbId); 211 void MergeFromCatchBB(size_t bbId); 212 GetFrameLiveoutAfter(uint32_t bcId)213 FrameLiveOut *GetFrameLiveoutAfter(uint32_t bcId) 214 { 215 return bcEndStateLiveouts_[bcId]; 216 } 217 GetFrameLiveoutBefore(size_t bbId)218 FrameLiveOut *GetFrameLiveoutBefore(size_t bbId) 219 { 220 return bbBeginStateLiveouts_[bbId]; 221 } 222 ValuesAt(size_t index)223 GateRef ValuesAt(size_t index) const 224 { 225 return liveContext_->ValuesAt(index); 226 } 227 ValuesAtAccumulator()228 GateRef ValuesAtAccumulator() const 229 { 230 return ValuesAt(accumulatorIndex_); 231 } 232 UpdateVirtualRegister(size_t index,GateRef gate)233 void UpdateVirtualRegister(size_t index, GateRef gate) 234 { 235 liveContext_->SetValuesAt(index, gate); 236 } 237 GetMergedBbContext(uint32_t bbIndex)238 FrameContext *GetMergedBbContext(uint32_t bbIndex) const 239 { 240 ASSERT(bbIndex < bbFrameContext_.size()); 241 return bbFrameContext_[bbIndex]; 242 } 243 244 void FillBcInputs(const BytecodeInfo &bytecodeInfo, GateRef gate); 245 void DumpLiveState(); 246 size_t GetNumOfStatePreds(const BytecodeRegion &bb); 247 GateRef MergeValue(const BytecodeRegion &bb, 248 GateRef currentValue, GateRef nextValue, bool isLoopBack, bool changedInLoop); 249 void NewMerge(const BytecodeRegion &bbNext); 250 void MergeStateDepend(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 251 void CopyLiveoutValues(const BytecodeRegion &bbNext, FrameContext* dest, FrameContext* src); 252 void SaveCurrentContext(const BytecodeRegion &bb); 253 MergeStateDependInfo GetCorrespondingState(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 254 255 void NewLoopExit(const BytecodeRegion &bbNext, BitSet *loopAssignment); 256 size_t ComputeLoopDepth(size_t loopHead); 257 void TryInsertLoopExit(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 258 void ComputeLoopInfo(); 259 void ResizeLoopBody(); 260 void MergeAssignment(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 261 BitSet *GetLoopAssignment(const BytecodeRegion &bb); 262 LoopInfo& GetLoopInfo(const BytecodeRegion &bb); 263 LoopInfo& GetLoopInfo(BytecodeRegion &bb); 264 LoopInfo* GetLoopInfoByLoopBody(const BytecodeRegion &bb); 265 bool IsLoopBackEdge(const BytecodeRegion &bb, const BytecodeRegion &bbNext); 266 bool IsLoopHead(const BytecodeRegion &bb); 267 bool IfLoopNeedMerge(const BytecodeRegion &bb) const; 268 GateRef InitMerge(size_t numOfIns, bool isLoop); 269 bool IsGateNotEmpty(GateRef gate) const; 270 271 GateRef BuildFrameContext(FrameContext* frameContext); 272 void BuildFrameStateBefore(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId); 273 void BindFrameStateAndStateSplitAfter(const BytecodeInfo &bytecodeInfo, uint32_t bcId, GateRef gate); 274 GateRef BuildFrameValues(FrameContext* frameContext, FrameLiveOut* liveout); 275 GateRef BuildStateSplit(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex); 276 GateRef BuildFrameState(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex); 277 void AddEmptyBlock(BytecodeRegion* bb); 278 FrameContext *GetCachedContext(); 279 280 BytecodeCircuitBuilder *bcBuilder_ {nullptr}; 281 const PGOTypeRecorder *pgoTypeRecorder_ {nullptr}; 282 FrameLiveOut *liveOutResult_ {nullptr}; 283 FrameLiveOut *currentBBliveOut_ {nullptr}; 284 FrameContext *liveContext_ {nullptr}; 285 FrameContext *cachedContext_ {nullptr}; 286 FrameContext *cachedContextBackup_ {nullptr}; 287 size_t numVregs_ {0}; 288 size_t accumulatorIndex_ {0}; 289 size_t envIndex_ {0}; 290 size_t numLoops_ {0}; 291 size_t sortIndx_ {0}; 292 GateRef frameStateCache_ {Circuit::NullGate()}; 293 Circuit *circuit_ {nullptr}; 294 GateAccessor acc_; 295 ChunkVector<FrameLiveOut *> bcEndStateLiveouts_; 296 ChunkVector<FrameLiveOut *> bbBeginStateLiveouts_; 297 ChunkVector<FrameContext *> bbFrameContext_; 298 ChunkVector<LoopInfo> loops_; 299 ChunkDeque<size_t> rpoList_; 300 ChunkVector<size_t> postOrderList_; 301 const BytecodeRegion *loopHeadOfOSR_ {nullptr}; 302 303 friend class BlockLoopAnalysis; 304 friend class SubContextScope; 305 }; 306 } // panda::ecmascript::kungfu 307 #endif // ECMASCRIPT_COMPILER_FRAME_STATE_H 308