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 <queue>
17#include <stack>
18#include "ecmascript/compiler/graph_editor.h"
19
20namespace panda::ecmascript::kungfu {
21
22void GraphEditor::RemoveDeadState(Circuit* circuit, GateRef gate)
23{
24    GraphEditor editor(circuit);
25    editor.ReplaceGate(gate);
26    editor.RemoveGate();
27}
28
29void GraphEditor::EliminateRedundantPhi(Circuit* circuit, bool enableLog, const std::string& methodName)
30{
31    GraphEditor editor(circuit);
32    editor.EliminatePhi();
33    if (enableLog) {
34        LOG_COMPILER(INFO) << " ";
35        LOG_COMPILER(INFO) << "\033[34m" << "================="
36                           << " After Redundant Phi Elimination "
37                           << "[" << methodName << "] "
38                           << "=================" << "\033[0m";
39        circuit->PrintAllGatesWithBytecode();
40        LOG_COMPILER(INFO) << "\033[34m" << "=========================== End ===========================" << "\033[0m";
41    }
42}
43
44void GraphEditor::ReplaceGate(GateRef gate)
45{
46    auto uses = acc_.Uses(gate);
47    for (auto useIt = uses.begin(); useIt != uses.end();) {
48        if (acc_.IsDependIn(useIt)) {
49            GateRef depend = acc_.GetDep(gate);
50            useIt = acc_.ReplaceIn(useIt, depend);
51        } else {
52            workList_.push_back(useIt.GetEdge());
53            useIt = acc_.ReplaceIn(useIt, circuit_->DeadGate());
54        }
55    }
56    acc_.DeleteGate(gate);
57}
58
59void GraphEditor::RemoveGate()
60{
61    while (!workList_.empty()) {
62        Edge& edge = workList_.back();
63        GateRef gate = edge.GetGate();
64        workList_.pop_back();
65        auto opcode = acc_.GetOpCode(gate);
66        switch (opcode) {
67            case OpCode::NOP:
68            case OpCode::DEAD:
69            case OpCode::VALUE_SELECTOR:
70            case OpCode::DEPEND_SELECTOR:
71                // dead op, just continue
72                break;
73            case OpCode::LOOP_BEGIN:
74            case OpCode::MERGE:
75                PropagateMerge(edge);
76                break;
77            default:
78                PropagateGate(edge);
79                break;
80        }
81    }
82}
83
84void GraphEditor::PropagateGate(const Edge& edge)
85{
86    GateRef gate = edge.GetGate();
87    // isStateIn
88    if (acc_.IsStateIn(gate, edge.GetIndex())) {
89        ASSERT(acc_.GetStateCount(gate) == 1);
90        ReplaceGate(gate);
91        return;
92    }
93
94    // IsValueIn
95    if (acc_.IsValueIn(gate, edge.GetIndex())) {
96        // value gate
97        ReplaceGate(gate);
98    }
99}
100
101void GraphEditor::PropagateMerge(const Edge& edge)
102{
103    GateRef gate = edge.GetGate();
104    auto numIns = acc_.GetNumIns(gate);
105    if (numIns == 1) {
106        ReplaceGate(gate);
107    } else {
108        auto uses = acc_.Uses(gate);
109        for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
110            GateRef use = *useIt;
111            //  (Gate1)   (Dead)   (Gate2)       (Gate1)  (Gate2)
112            //     |       |         |              |        |
113            //     ___________________      ==>     __________
114            //             |                             |
115            //           (phi)                         (phi)
116            if (acc_.GetOpCode(use) == OpCode::VALUE_SELECTOR ||
117                acc_.GetOpCode(use) == OpCode::DEPEND_SELECTOR) {
118                acc_.DecreaseIn(use, edge.GetIndex() + 1); // +1 skip state input
119            }
120        }
121        acc_.DecreaseIn(gate, edge.GetIndex());
122    }
123}
124
125bool GraphEditor::HasOsrDeoptUse(GateRef gate)
126{
127    std::vector<GateRef> valueOuts;
128    acc_.GetValueUses(gate, valueOuts);
129    for (auto out : valueOuts) {
130        if (acc_.GetOpCode(out) != OpCode::FRAME_STATE) {
131            continue;
132        }
133        std::vector<GateRef> outs;
134        acc_.GetValueUses(out, outs);
135        for (auto use : outs) {
136            if (acc_.GetOpCode(use) != OpCode::DEOPT_CHECK) {
137                continue;
138            }
139            GateRef deoptType = acc_.GetValueIn(use, 2);  // 2: deopt type
140            uint64_t v = acc_.GetConstantValue(deoptType);
141            if (v == static_cast<uint64_t>(DeoptType::OSRLOOPEXIT)) {
142                return true;
143            }
144        }
145    }
146    return false;
147}
148
149void GraphEditor::EliminatePhi()
150{
151    circuit_->AdvanceTime();
152    std::vector<GateRef> gateList;
153    acc_.GetAllGates(gateList);
154    std::vector<GateRef> phis;
155    std::queue<GateRef> workList;
156    // nomarked phis are unused phis
157    // set previsit for phis in worklist
158    // set visited for used phis
159    // set finished for used gate which is self-use or has same inputs
160
161    for (auto gate : gateList) {
162        if (acc_.IsValueSelector(gate)) {
163            phis.emplace_back(gate);
164            continue;
165        }
166        if (acc_.IsFrameValues(gate) && !HasOsrDeoptUse(gate)) {
167            continue;
168        }
169        // get used phi
170        auto valueNum = acc_.GetNumValueIn(gate);
171        for (size_t i = 0; i < valueNum; ++i) {
172            GateRef input = acc_.GetValueIn(gate, i);
173            if (acc_.IsValueSelector(input) && acc_.IsNotMarked(input)) {
174                acc_.SetPrevisit(input);
175                workList.push(input);
176            }
177        }
178    }
179
180    // visit used phi
181    while (!workList.empty()) {
182        auto cur = workList.front();
183        workList.pop();
184        acc_.SetVisited(cur);
185        auto valueNum = acc_.GetNumValueIn(cur);
186        bool sameIns = true;
187        GateRef first = acc_.GetValueIn(cur, 0);
188        for (size_t i = 0; i < valueNum; ++i) {
189            GateRef input = acc_.GetValueIn(cur, i);
190            if (input != first) {
191                sameIns = false;
192            }
193            if (acc_.IsValueSelector(input) && acc_.IsNotMarked(input)) {
194                workList.push(input);
195                acc_.SetPrevisit(input);
196            }
197        }
198
199        if (!sameIns) {
200            continue;
201        }
202
203        acc_.SetFinished(cur);
204        auto uses = acc_.Uses(cur);
205        for (auto it = uses.begin(); it != uses.end(); it++) {
206            if (acc_.IsValueSelector(*it) && acc_.IsVisited(*it)) {
207                // revisit user
208                acc_.SetPrevisit(*it);
209                workList.push(*it);
210            }
211        }
212        acc_.UpdateAllUses(cur, first);
213        acc_.DeleteGate(cur);
214    }
215
216    // delete unused phi
217    for (auto phi : phis) {
218        if (acc_.IsValueSelector(phi) && acc_.IsNotMarked(phi)) {
219            auto optimizedGate = circuit_->GetConstantGate(MachineType::I64,
220                JSTaggedValue::VALUE_OPTIMIZED_OUT, GateType::TaggedValue());
221            acc_.UpdateAllUses(phi, optimizedGate);
222            acc_.DeleteGate(phi);
223        }
224    }
225}
226}  // namespace panda::ecmascript::kungfu
227