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