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