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#include "ecmascript/compiler/loop_analysis.h"
17#include "ecmascript/compiler/loop_peeling.h"
18#include "ecmascript/compiler/bytecodes.h"
19#include "ecmascript/compiler/share_gate_meta_data.h"
20#include "ecmascript/log_wrapper.h"
21
22namespace panda::ecmascript::kungfu {
23void LoopAnalysis::PrintLoop(LoopInfo* loopInfo)
24{
25    LOG_COMPILER(INFO) << "--------------------------------- LoopInfo Start ---------------------------------";
26    LOG_COMPILER(INFO) << "Head: " << acc_.GetId(loopInfo->loopHead);
27    LOG_COMPILER(INFO) << "Size: " << loopInfo->size;
28    LOG_COMPILER(INFO) << "MaxDepth: " << loopInfo->maxDepth;
29    LOG_COMPILER(INFO) << "Body: [";
30    for (auto gate : loopInfo->loopBodys) {
31        acc_.ShortPrint(gate);
32    }
33    LOG_COMPILER(INFO) << "]";
34    LOG_COMPILER(INFO) << "Exit: [";
35    for (auto gate : loopInfo->loopExits) {
36        acc_.ShortPrint(gate);
37    }
38    LOG_COMPILER(INFO) << "]";
39    LOG_COMPILER(INFO) << "--------------------------------- LoopInfo End ---------------------------------";
40}
41
42void LoopAnalysis::Run()
43{
44    ChunkVector<GateRef>& headerGates = bcBuilder_->GetLoopHeaderGates();
45    for (auto it = headerGates.rbegin(); it != headerGates.rend(); ++it) {
46        auto gate = *it;
47        if (gate == Circuit::NullGate()) {
48            continue;
49        }
50        auto loopInfo = chunk_->New<LoopInfo>(chunk_, gate);
51        loopInfos_.emplace_back(loopInfo);
52    }
53}
54
55void LoopAnalysis::CollectUseGate(ChunkUnorderedMap<GateRef, size_t>& gateToDepth,
56    ChunkQueue<GateRef>& firstList, ChunkQueue<GateRef>& secondList,
57    LoopInfo* loopInfo, GateRef cur)
58{
59    auto use = acc_.Uses(cur);
60    ASSERT(use.begin() != use.end());
61    bool isCurLoop = gateToDepth[cur] == 1; // 1: loopDepth
62    for (auto it = use.begin(); it != use.end(); ++it) {
63        auto nex = *it;
64        if (isCurLoop && acc_.IsLoopExit(cur) && (!acc_.IsFixed(*it))) {
65            continue;
66        } else if (isCurLoop && acc_.IsLoopExitRelated(cur) && acc_.IsFixed(cur)) {
67            continue;
68        } else if (acc_.GetDependCount(nex) == 0 && acc_.GetStateCount(nex) == 0) {
69            continue;
70        }
71        if (gateToDepth.count(nex)) {
72            // loop back
73            if (acc_.IsStateIn(it) || acc_.IsDependIn(it)) {
74                ASSERT(gateToDepth[nex] == ComputeLoopDepth(cur, nex, gateToDepth[cur]));
75            }
76            continue;
77        }
78        if (acc_.IsStateIn(it) || acc_.IsDependIn(it)) {
79            // only calculate loop depth for state & depend edges,
80            // since there is no phi of each value and each loop head.
81            gateToDepth[nex] = ComputeLoopDepth(cur, nex, gateToDepth[cur]);
82            if (acc_.HasFrameState(nex)) {
83                auto frameState = acc_.GetFrameState(nex);
84                if (acc_.GetOpCode(frameState) == OpCode::FRAME_STATE) {
85                    gateToDepth[frameState] = gateToDepth[nex];
86                    gateToDepth[acc_.GetValueIn(frameState, 1)] = gateToDepth[nex];
87                }
88            }
89            // state and depend edge should be visited first.
90            firstList.push(nex);
91            UpdateLoopInfo(loopInfo, nex, gateToDepth.at(nex));
92        } else {
93            secondList.push(nex);
94        }
95    }
96}
97
98void LoopAnalysis::CollectLoopBody(LoopInfo* loopInfo)
99{
100    ASSERT(acc_.IsLoopHead(loopInfo->loopHead));
101    ChunkUnorderedMap<GateRef, size_t> gateToDepth(chunk_);
102    ChunkQueue<GateRef> firstList(chunk_);  // for state and depend edges
103    ChunkQueue<GateRef> secondList(chunk_); // for other edges
104    gateToDepth[loopInfo->loopHead] = 1;
105    firstList.push(loopInfo->loopHead);
106    while ((!firstList.empty()) || (!secondList.empty())) {
107        GateRef cur = Circuit::NullGate();
108        if (!firstList.empty()) {
109            cur = firstList.front();
110            firstList.pop();
111        } else {
112            cur = secondList.front();
113            secondList.pop();
114        }
115        ASSERT(gateToDepth.count(cur) > 0);
116        CollectUseGate(gateToDepth, firstList, secondList, loopInfo, cur);
117    }
118}
119
120void LoopAnalysis::UpdateLoopInfo(LoopInfo* loopInfo, GateRef gate, size_t dep)
121{
122    auto op = acc_.GetOpCode(gate);
123    loopInfo->maxDepth = std::max(loopInfo->maxDepth, dep);
124    loopInfo->size++;
125    switch (op) {
126        case OpCode::LOOP_BACK: {
127            if (dep == 1) { // 1: depth of loop head
128                loopInfo->loopBacks.emplace_back(gate);
129                return;
130            }
131            break;
132        }
133        case OpCode::LOOP_EXIT: {
134            if (dep == 1) { // 1: depth of loop head
135                loopInfo->loopExits.emplace_back(gate);
136                return;
137            }
138            break;
139        }
140        case OpCode::LOOP_EXIT_DEPEND:
141        case OpCode::LOOP_EXIT_VALUE: {
142            if (dep == 1) {
143                return;
144            }
145            break;
146        }
147        default:
148            break;
149    }
150    if (acc_.HasFrameState(gate)) {
151        auto frameState = acc_.GetFrameState(gate);
152        if (acc_.GetOpCode(frameState) == OpCode::FRAME_STATE) {
153            loopInfo->size += 2;    // 2: framestate and framevalues
154            loopInfo->loopBodys.emplace_back(frameState);
155            loopInfo->loopBodys.emplace_back(acc_.GetValueIn(frameState, 1));
156        }
157    }
158    loopInfo->loopBodys.emplace_back(gate);
159}
160
161// only receive state or depend edge (cur -> dep)
162size_t LoopAnalysis::ComputeLoopDepth(GateRef cur, GateRef nex, size_t curDep)
163{
164    if (acc_.IsLoopExitRelated(cur)) {
165        if ((!acc_.IsLoopExit(cur)) || (!acc_.IsFixed(nex))) {
166            // exit from some loop
167            ASSERT(curDep > 0);
168            curDep--;
169        }
170    }
171    auto nexOp = acc_.GetOpCode(nex);
172    switch (nexOp) {
173        case OpCode::LOOP_BEGIN: {
174            if (acc_.GetState(nex) == cur) {
175                // enter new loop by state edge
176                curDep++;
177            }
178            break;
179        }
180        case OpCode::DEPEND_SELECTOR: {
181            GateRef state = acc_.GetState(nex);
182            if (acc_.IsLoopHead(state) && (cur == acc_.GetDep(nex))) {
183                // enter new loop by depend edge
184                curDep++;
185            }
186            break;
187        }
188        default: {
189            break;
190        }
191    }
192    return curDep;
193}
194
195void LoopAnalysis::LoopExitElimination()
196{
197    std::vector<GateRef> gateList;
198    acc_.GetAllGates(gateList);
199    ChunkQueue<GateRef> workList(chunk_);
200    ChunkSet<GateRef> inList(chunk_);
201    for (auto gate : gateList) {
202        auto op = acc_.GetOpCode(gate);
203        switch (op) {
204            case OpCode::LOOP_EXIT: {
205                acc_.UpdateAllUses(gate, acc_.GetIn(gate, 0));
206                acc_.DeleteGate(gate);
207                break;
208            }
209            case OpCode::LOOP_EXIT_DEPEND:
210            case OpCode::LOOP_EXIT_VALUE: {
211                acc_.UpdateAllUses(gate, acc_.GetIn(gate, 1));
212                acc_.DeleteGate(gate);
213                break;
214            }
215            default:
216                break;
217        }
218    }
219}
220}  // namespace panda::ecmascript::kungfu
221