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/combined_pass_visitor.h"
17
18namespace panda::ecmascript::kungfu {
19
20int32_t CombinedPassVisitor::GetGateOrder(GateRef gate)
21{
22    auto id = acc_.GetId(gate);
23    if (id >= orderList_.size()) {
24        Resize(id + 1, -1);
25    }
26    return orderList_[acc_.GetId(gate)];
27}
28
29void CombinedPassVisitor::SetGateOrder(GateRef gate, int32_t orderId)
30{
31    auto id = acc_.GetId(gate);
32    if (id >= orderList_.size()) {
33        Resize(id + 1, -1);
34    }
35    orderList_[acc_.GetId(gate)] = orderId;
36}
37
38void CombinedPassVisitor::Resize(int32_t size, int32_t num)
39{
40    orderList_.resize(size, num);
41}
42
43void CombinedPassVisitor::AddPass(PassVisitor* pass)
44{
45    passList_.emplace_back(pass);
46}
47
48void CombinedPassVisitor::LogicallyReplaceGate(GateRef gate, GateRef replacement)
49{
50    auto uses = acc_.Uses(gate);
51    for (auto it = uses.begin(); it != uses.end();) {
52        if (acc_.GetMark(*it) == MarkCode::FINISHED) {
53            PushChangedGate(*it);
54        }
55        it = acc_.ReplaceIn(it, replacement);
56    }
57}
58void CombinedPassVisitor::RelaxStateAndDepend(GateRef gate)
59{
60    ReplaceGate(gate, StateDepend {acc_.GetState(gate), acc_.GetDep(gate)}, gate);
61}
62
63void CombinedPassVisitor::ReplaceGate(GateRef gate, GateRef replacement)
64{
65    GateRef depend = Circuit::NullGate();
66    if (acc_.GetDependCount(gate) > 0) {
67        ASSERT(acc_.GetDependCount(gate) == 1 || acc_.GetOpCode(replacement) == OpCode::DEAD); // 1: one dep
68        depend = acc_.GetDep(gate);
69    }
70    GateRef state = Circuit::NullGate();
71    if (acc_.GetStateCount(gate) > 0) {
72        ASSERT(acc_.GetStateCount(gate) == 1 || acc_.GetOpCode(replacement) == OpCode::DEAD);  // 1: one state
73        state = acc_.GetState(gate);
74    }
75    ReplaceGate(gate, StateDepend {state, depend}, replacement);
76    acc_.DeleteGate(gate);
77}
78
79void CombinedPassVisitor::ReplaceGate(GateRef gate, StateDepend stateDepend, GateRef replacement)
80{
81    auto state = stateDepend.State();
82    auto depend = stateDepend.Depend();
83    auto uses = acc_.Uses(gate);
84    for (auto it = uses.begin(); it != uses.end();) {
85        if (acc_.GetMark(*it) == MarkCode::FINISHED) {
86            PushChangedGate(*it);
87        }
88        if (acc_.GetOpCode(replacement) == OpCode::DEAD) {
89            it = acc_.ReplaceIn(it, replacement);
90        } else if (acc_.IsStateIn(it)) {
91            ASSERT(state != Circuit::NullGate());
92            it = acc_.ReplaceIn(it, state);
93        } else if (acc_.IsDependIn(it)) {
94            ASSERT(depend != Circuit::NullGate());
95            it = acc_.ReplaceIn(it, depend);
96        } else {
97            it = acc_.ReplaceIn(it, replacement);
98        }
99    }
100#ifndef NDEBUG
101    acc_.GetCircuit()->AddComment(replacement,  "old V " + std::to_string(acc_.GetId(gate)));
102#endif
103}
104
105void CombinedPassVisitor::VistDependSelectorForLoop(GateRef gate)
106{
107    auto use = acc_.Uses(gate);
108    for (auto useIt = use.begin(); useIt != use.end(); useIt++) {
109        if (acc_.GetOpCode(*useIt) == OpCode::DEPEND_SELECTOR) {
110            PushChangedGate(*useIt);
111        }
112    }
113}
114
115void CombinedPassVisitor::VisitGraph()
116{
117    for (auto pass : passList_) {
118        pass->Initialize();
119    }
120    circuit_->AdvanceTime();
121    orderCount_ = 0;
122    Resize(circuit_->GetMaxGateId() + 1, -1);
123    std::vector<GateRef> gateList;
124    circuit_->GetAllGates(gateList);
125    for (auto gate : gateList) {
126        if (acc_.GetOpCode(gate) == OpCode::LOOP_BEGIN) {
127            PushChangedGate(gate);
128            // For empty loop and no RETURN opcode
129            VistDependSelectorForLoop(gate);
130        }
131    }
132    // Visit gate needing to start from RETURN, otherwise it may lead to incomplete early elimination in some scenarios.
133    GateRef returnList = acc_.GetReturnRoot();
134    auto uses = acc_.Uses(returnList);
135    for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
136        PushChangedGate(*useIt);
137    }
138
139    while (true) {
140        if (!workList_.empty()) {
141            Edge& current = workList_.back();
142            VisitTopGate(current);
143        } else if (!changedList_.empty()) {
144            GateRef gate = changedList_.back();
145            changedList_.pop_back();
146            if (acc_.GetMark(gate) == MarkCode::PREVISIT) {
147                PushGate(gate, 0);
148            }
149        } else {
150            for (auto pass : passList_) {
151                pass->Finalize();
152            }
153            break;
154        }
155    }
156}
157
158void CombinedPassVisitor::ReVisitGate(GateRef gate)
159{
160    if (acc_.GetMark(gate) == MarkCode::FINISHED) {
161        PushChangedGate(gate);
162    }
163}
164
165
166GateRef CombinedPassVisitor::VisitGate(GateRef gate)
167{
168    [[maybe_unused]] auto scopedGate = circuit_->VisitGateBegin(gate);
169    auto skip = passList_.end();
170    for (auto i = passList_.begin(); i != passList_.end();) {
171        if (i == skip) {
172            i++;
173            continue;
174        }
175        GateRef replacement = (*i)->VisitGate(gate);
176        if (replacement == gate) {
177            skip = i;
178            i = passList_.begin();
179            continue;
180        } else if (replacement != Circuit::NullGate()) {
181            return replacement;
182        }
183        i++;
184    }
185    if (skip == passList_.end()) {
186        return Circuit::NullGate();
187    }
188    return gate;
189}
190// Reverse post-order
191void CombinedPassVisitor::VisitTopGate(Edge& current)
192{
193    GateRef gate = current.GetGate();
194    // gate is delete or dead
195    if (acc_.IsNop(gate)) {
196        PopGate(gate);
197        return;
198    }
199    auto numIns = acc_.GetNumIns(gate);
200    auto start = current.GetIndex();
201    if (start >= numIns) {
202        start = 0;
203    }
204    for (size_t i = start; i < numIns; i++) {
205        GateRef input = acc_.GetIn(gate, i);
206        if (input == gate) {
207            continue;
208        }
209        // find not visited gate, push stack
210        if (acc_.GetMark(input) < MarkCode::VISITED) {
211            PushGate(input, 0);
212            // next index
213            current.SetIndex(i + 1);
214            return;
215        }
216    }
217    for (size_t i = 0; i < start; i++) {
218        GateRef input = acc_.GetIn(gate, i);
219        if (input == gate) {
220            continue;
221        }
222        // find not visited gate, push stack
223        if (acc_.GetMark(input) < MarkCode::VISITED) {
224            PushGate(input, 0);
225            // next index
226            current.SetIndex(i + 1);
227            return;
228        }
229    }
230    // all input are visited
231    if (GetGateOrder(gate) == -1) { // -1 : not visited before
232        SetGateOrder(gate, ++orderCount_);
233    }
234    GateRef replacement = VisitGate(gate);
235    PopGate(gate);
236    if (replacement == Circuit::NullGate()) {
237        return;
238    }
239    if (replacement != gate) {
240        ReplaceGate(gate, replacement);
241    } else {
242        // revisit not on stack gate.
243        auto uses = acc_.Uses(gate);
244        for (auto it = uses.begin(); it != uses.end(); it++) {
245            if (acc_.GetMark(*it) == MarkCode::FINISHED) {
246                PushChangedGate(*it);
247            }
248        }
249    }
250}
251
252void CombinedPassVisitor::PrintStack()
253{
254    std::string log;
255    for (size_t i = 0; i < workList_.size(); i++) {
256        Edge current = workList_[i];
257        GateRef gate = current.GetGate();
258        log += std::to_string(acc_.GetId(gate)) + ", ";
259    }
260    LOG_COMPILER(INFO) << std::dec << log;
261}
262
263void CombinedPassVisitor::PrintLog(const std::string& phaseName)
264{
265    if (enableLog_) {
266        LOG_COMPILER(INFO) << "";
267        LOG_COMPILER(INFO) << "\033[34m"
268                        << "===================="
269                        << " After " << phaseName << " "
270                        << "[" << methodName_ << "]"
271                        << "===================="
272                        << "\033[0m";
273        circuit_->PrintAllGatesWithBytecode();
274        LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
275    }
276}
277
278} // namespace panda::ecmascript::kungfu
279