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
26namespace panda::ecmascript::kungfu {
27class BytecodeCircuitBuilder;
28struct BytecodeRegion;
29
30class FrameLiveOut {
31public:
32    explicit FrameLiveOut(Chunk* chunk, size_t numVregs)
33        : liveout_(chunk, numVregs), defRegisters_(chunk, numVregs) {}
34
35    void SetBit(size_t index)
36    {
37        liveout_.SetBit(index);
38    }
39
40    void ClearBit(size_t index)
41    {
42        liveout_.ClearBit(index);
43    }
44
45    bool TestBit(size_t index) const
46    {
47        return liveout_.TestBit(index);
48    }
49
50    void CopyFrom(FrameLiveOut *other)
51    {
52        liveout_.CopyFrom(other->liveout_);
53    }
54
55    bool MergeLiveout(FrameLiveOut *other)
56    {
57        return liveout_.UnionWithChanged(other->liveout_);
58    }
59
60    void Reset()
61    {
62        return liveout_.Reset();
63    }
64
65private:
66    // [numVRegs_] [extra args] [numArgs_] [accumulator]
67    BitSet liveout_;
68    BitSet defRegisters_;
69    friend class BlockLoopAnalysis;
70    friend class FrameStateBuilder;
71};
72
73class FrameContext {
74public:
75    explicit FrameContext(Chunk* chunk, size_t numVregs)
76        : values_(numVregs, chunk) {}
77
78    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    }
96private:
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
113struct MergeStateDependInfo {
114    GateRef state;
115    GateRef depend;
116    size_t index;
117};
118
119class FrameStateBuilder {
120public:
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
177private:
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