1/*
2 * Copyright (c) 2023 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_LOOP_ANALYSIS_H
17#define ECMASCRIPT_COMPILER_LOOP_ANALYSIS_H
18
19#include "ecmascript/compiler/bytecodes.h"
20#include "ecmascript/compiler/circuit.h"
21#include "ecmascript/compiler/gate_accessor.h"
22#include "ecmascript/mem/chunk_containers.h"
23
24namespace panda::ecmascript::kungfu {
25struct LoopInfo {
26    LoopInfo(Chunk* chunk, GateRef head)
27        : loopHead(head), loopBacks(chunk), loopExits(chunk), loopBodys(chunk) {}
28    GateRef loopHead{Circuit::NullGate()};
29    ChunkVector<GateRef> loopBacks;
30    ChunkVector<GateRef> loopExits;
31    ChunkVector<GateRef> loopBodys;
32    size_t size{0};
33    size_t maxDepth{0};
34};
35class LoopAnalysis {
36public:
37    LoopAnalysis(BytecodeCircuitBuilder* bcBuilder, Circuit *circuit, Chunk* chunk)
38        : bcBuilder_(bcBuilder), acc_(circuit), chunk_(chunk), loopInfos_(chunk) {}
39    ~LoopAnalysis() = default;
40    void Run();
41    void CollectLoopBody(LoopInfo* loopInfo);
42    void LoopExitElimination();
43    void PrintGraph();
44    void PrintLoop(LoopInfo* loopInfo);
45    const ChunkVector<LoopInfo*>& GetLoopTree() const
46    {
47        return loopInfos_;
48    }
49
50private:
51    void UpdateLoopInfo(LoopInfo* loopInfo, GateRef gate, size_t dep);
52    size_t ComputeLoopDepth(GateRef cur, GateRef nex, size_t curDep);
53    void CollectUseGate(ChunkUnorderedMap<GateRef, size_t>& gateToDepth,
54        ChunkQueue<GateRef>& firstList, ChunkQueue<GateRef>& secondList,
55        LoopInfo* loopInfo, GateRef cur);
56
57    BytecodeCircuitBuilder* bcBuilder_{nullptr};
58    GateAccessor acc_;
59    Chunk* chunk_{nullptr};
60    ChunkVector<LoopInfo*> loopInfos_;
61};
62
63}  // panda::ecmascript::kungfu
64#endif  // ECMASCRIPT_COMPILER_LOOP_ANALYSIS_H