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 
18 namespace panda::ecmascript::kungfu {
19 
GetGateOrder(GateRef gate)20 int32_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 
SetGateOrder(GateRef gate, int32_t orderId)29 void 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 
Resize(int32_t size, int32_t num)38 void CombinedPassVisitor::Resize(int32_t size, int32_t num)
39 {
40     orderList_.resize(size, num);
41 }
42 
AddPass(PassVisitor* pass)43 void CombinedPassVisitor::AddPass(PassVisitor* pass)
44 {
45     passList_.emplace_back(pass);
46 }
47 
LogicallyReplaceGate(GateRef gate, GateRef replacement)48 void 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 }
RelaxStateAndDepend(GateRef gate)58 void CombinedPassVisitor::RelaxStateAndDepend(GateRef gate)
59 {
60     ReplaceGate(gate, StateDepend {acc_.GetState(gate), acc_.GetDep(gate)}, gate);
61 }
62 
ReplaceGate(GateRef gate, GateRef replacement)63 void 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 
ReplaceGate(GateRef gate, StateDepend stateDepend, GateRef replacement)79 void 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 
VistDependSelectorForLoop(GateRef gate)105 void 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 
VisitGraph()115 void 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 
ReVisitGate(GateRef gate)158 void CombinedPassVisitor::ReVisitGate(GateRef gate)
159 {
160     if (acc_.GetMark(gate) == MarkCode::FINISHED) {
161         PushChangedGate(gate);
162     }
163 }
164 
165 
VisitGate(GateRef gate)166 GateRef 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
VisitTopGate(Edge& current)191 void 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 
PrintStack()252 void 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 
PrintLog(const std::string& phaseName)263 void 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