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
EliminatePhi()125 void GraphEditor::EliminatePhi()
126 {
127 circuit_->AdvanceTime();
128 std::vector<GateRef> gateList;
129 acc_.GetAllGates(gateList);
130 std::vector<GateRef> phis;
131 std::queue<GateRef> workList;
132 // nomarked phis are unused phis
133 // set previsit for phis in worklist
134 // set visited for used phis
135 // set finished for used gate which is self-use or has same inputs
136
137 for (auto gate : gateList) {
138 if (acc_.IsValueSelector(gate)) {
139 phis.emplace_back(gate);
140 continue;
141 }
142 if (acc_.IsFrameValues(gate)) {
143 continue;
144 }
145 // get used phi
146 auto valueNum = acc_.GetNumValueIn(gate);
147 for (size_t i = 0; i < valueNum; ++i) {
148 GateRef input = acc_.GetValueIn(gate, i);
149 if (acc_.IsValueSelector(input) && acc_.IsNotMarked(input)) {
150 acc_.SetPrevisit(input);
151 workList.push(input);
152 }
153 }
154 }
155
156 // visit used phi
157 while (!workList.empty()) {
158 auto cur = workList.front();
159 workList.pop();
160 acc_.SetVisited(cur);
161 auto valueNum = acc_.GetNumValueIn(cur);
162 bool sameIns = true;
163 GateRef first = acc_.GetValueIn(cur, 0);
164 for (size_t i = 0; i < valueNum; ++i) {
165 GateRef input = acc_.GetValueIn(cur, i);
166 if (input != first) {
167 sameIns = false;
168 }
169 if (acc_.IsValueSelector(input) && acc_.IsNotMarked(input)) {
170 workList.push(input);
171 acc_.SetPrevisit(input);
172 }
173 }
174
175 if (!sameIns) {
176 continue;
177 }
178
179 acc_.SetFinished(cur);
180 auto uses = acc_.Uses(cur);
181 for (auto it = uses.begin(); it != uses.end(); it++) {
182 if (acc_.IsValueSelector(*it) && acc_.IsVisited(*it)) {
183 // revisit user
184 acc_.SetPrevisit(*it);
185 workList.push(*it);
186 }
187 }
188 acc_.UpdateAllUses(cur, first);
189 acc_.DeleteGate(cur);
190 }
191
192 // delete unused phi
193 for (auto phi : phis) {
194 if (acc_.IsValueSelector(phi) && acc_.IsNotMarked(phi)) {
195 auto optimizedGate = circuit_->GetConstantGate(MachineType::I64,
196 JSTaggedValue::VALUE_OPTIMIZED_OUT, GateType::TaggedValue());
197 acc_.UpdateAllUses(phi, optimizedGate);
198 acc_.DeleteGate(phi);
199 }
200 }
201 }
202 } // namespace panda::ecmascript::kungfu
203