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
20 namespace panda::ecmascript::kungfu {
21
RemoveDeadState(Circuit * circuit,GateRef gate)22 void GraphEditor::RemoveDeadState(Circuit* circuit, GateRef gate)
23 {
24 GraphEditor editor(circuit);
25 editor.ReplaceGate(gate);
26 editor.RemoveGate();
27 }
28
EliminateRedundantPhi(Circuit * circuit,bool enableLog,const std::string & methodName)29 void 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
ReplaceGate(GateRef gate)44 void 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
RemoveGate()59 void 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
PropagateGate(const Edge & edge)84 void 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
PropagateMerge(const Edge & edge)101 void 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
HasOsrDeoptUse(GateRef gate)125 bool 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
EliminatePhi()149 void 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