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/dead_code_elimination.h"
17
18namespace panda::ecmascript::kungfu {
19
20GateRef DeadCodeElimination::VisitGate(GateRef gate)
21{
22    auto opcode = acc_.GetOpCode(gate);
23    switch (opcode) {
24        case OpCode::SWITCH_BRANCH:
25        case OpCode::IF_BRANCH:
26            return EliminateBranch(gate);
27        case OpCode::MERGE:
28        case OpCode::LOOP_BEGIN:
29            return EliminateMergeAndLoopBegin(gate);
30        case OpCode::DEPEND_SELECTOR:
31            return EliminateDependSelector(gate);
32        case OpCode::IF_EXCEPTION:
33            return EliminateIfException(gate);
34        case OpCode::LOOP_EXIT:
35            return EliminateLoopExit(gate);
36        default :
37            return EliminateGate(gate);
38    }
39    return Circuit::NullGate();
40}
41
42GateRef DeadCodeElimination::StateIsDead(GateRef gate)
43{
44    auto state = acc_.GetState(gate);
45    if (acc_.IsDead(state)) {
46        return state;
47    }
48    return Circuit::NullGate();
49}
50
51GateRef DeadCodeElimination::EliminateDependSelector(GateRef gate)
52{
53    GateRef state = StateIsDead(gate);
54    if (state != Circuit::NullGate() && acc_.IsDead(state)) {
55        return state;
56    }
57    auto stateInput = acc_.GetState(gate);
58    size_t dependCount = acc_.GetDependCount(gate);
59    GateRef result = Circuit::NullGate();
60    for (size_t i = 0; i < dependCount; i++) {
61        auto depend = acc_.GetDep(gate, i);
62        if (acc_.IsDead(depend)) {
63            acc_.ReplaceStateIn(stateInput, deadGate_, i);
64            visitor_->ReVisitGate(stateInput);
65            result = gate;
66        }
67    }
68    return result;
69}
70
71GateRef DeadCodeElimination::EliminateIfException(GateRef gate)
72{
73    GateRef state = StateIsDead(gate);
74    if (state != Circuit::NullGate() && acc_.IsDead(state)) {
75        return state;
76    }
77    GateRef depend = acc_.GetDep(gate);
78    if (acc_.IsDead(depend)) {
79        return deadGate_;
80    }
81    return Circuit::NullGate();
82}
83
84GateRef DeadCodeElimination::EliminateLoopExit(GateRef gate)
85{
86    GateRef state = StateIsDead(gate);
87    if (state != Circuit::NullGate() && acc_.IsDead(state)) {
88        return DeleteLoopExit(gate);
89    }
90    return Circuit::NullGate();
91}
92
93GateRef DeadCodeElimination::EliminateBranch(GateRef gate)
94{
95    GateRef state = StateIsDead(gate);
96    if (state != Circuit::NullGate() && acc_.IsDead(state)) {
97        return state;
98    }
99    GateRef value = acc_.GetValueIn(gate, 0);
100    if (acc_.IsDead(value)) {
101        auto uses = acc_.Uses(gate);
102        for (auto it = uses.begin(); it != uses.end(); it++) {
103            if (acc_.IsIfOrSwitchRelated(*it)) {
104                ReplaceGate(*it, acc_.GetState(gate));
105                return deadGate_;
106            }
107        }
108        UNREACHABLE();
109    }
110    return gate;
111}
112
113void DeadCodeElimination::DecreaseAllSelectors(GateRef gate, size_t count)
114{
115    auto uses = acc_.Uses(gate);
116    for (auto it = uses.begin(); it != uses.end(); it++) {
117        if (acc_.IsSelector(*it)) {
118            acc_.DecreaseIn(*it, count + 1);
119        }
120    }
121}
122GateRef DeadCodeElimination::EliminateMergeAndLoopBegin(GateRef gate)
123{
124    if (acc_.GetOpCode(gate) == OpCode::LOOP_BEGIN) {
125        auto loopEntry = acc_.GetIn(gate, 0);
126        if (acc_.IsDead(loopEntry)) {
127            return deadGate_;
128        }
129    }
130    size_t count = 0;
131    size_t inputCount = acc_.GetNumIns(gate);
132    for (size_t i = 0; i < inputCount; i++) {
133        auto input = acc_.GetIn(gate, count);
134        if (acc_.IsDead(input)) {
135            acc_.DecreaseIn(gate, count);
136            DecreaseAllSelectors(gate, count);
137        } else {
138            count++;
139        }
140    }
141    if (count == 0) {
142        return deadGate_;
143    } else if (count == 1) {
144        auto uses = acc_.Uses(gate);
145        for (auto it = uses.begin(); it != uses.end(); it++) {
146            if (acc_.IsSelector(*it)) {
147                TryFindAndDeleteLoopExit(*it);
148                auto selectorInput = acc_.GetIn(*it, 1);
149                ReplaceGate(*it, selectorInput);
150            }
151        }
152        return acc_.GetIn(gate, 0);
153    }
154    if (count < inputCount) {
155        auto uses = acc_.Uses(gate);
156        for (auto it = uses.begin(); it != uses.end(); it++) {
157            if (acc_.IsSelector(*it)) {
158                visitor_->ReVisitGate(*it);
159            }
160        }
161        return gate;
162    }
163    return Circuit::NullGate();
164}
165
166void DeadCodeElimination::TryFindAndDeleteLoopExit(GateRef gate)
167{
168    auto uses = acc_.Uses(gate);
169    for (auto it = uses.begin(); it != uses.end(); it++) {
170        if (acc_.GetOpCode(*it) == OpCode::LOOP_EXIT_VALUE || acc_.GetOpCode(*it) == OpCode::LOOP_EXIT_DEPEND) {
171            GateRef loopExit = acc_.GetState(gate);
172            DeleteLoopExit(loopExit);
173        }
174    }
175}
176GateRef DeadCodeElimination::DeleteLoopExit(GateRef gate)
177{
178    auto uses = acc_.Uses(gate);
179    for (auto it = uses.begin(); it != uses.end(); it++) {
180        if (acc_.GetOpCode(*it) == OpCode::LOOP_EXIT_VALUE) {
181            ReplaceGate(*it, acc_.GetValueIn(*it));
182        } else if (acc_.GetOpCode(*it) == OpCode::LOOP_EXIT_DEPEND) {
183            ReplaceGate(*it, acc_.GetDep(*it));
184        }
185    }
186    return acc_.GetState(gate);
187}
188
189GateRef DeadCodeElimination::EliminateGate(GateRef gate)
190{
191    if (acc_.GetStateCount(gate) == 1) {
192        return StateIsDead(gate);
193    }
194    return Circuit::NullGate();
195}
196
197}