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)29 void GraphEditor::EliminateRedundantPhi(Circuit* circuit)
30 {
31 GraphEditor editor(circuit);
32 editor.EliminatePhi();
33 }
34
ReplaceGate(GateRef gate)35 void GraphEditor::ReplaceGate(GateRef gate)
36 {
37 auto uses = acc_.Uses(gate);
38 for (auto useIt = uses.begin(); useIt != uses.end();) {
39 if (acc_.IsDependIn(useIt)) {
40 GateRef depend = acc_.GetDep(gate);
41 useIt = acc_.ReplaceIn(useIt, depend);
42 } else {
43 workList_.push_back(useIt.GetEdge());
44 useIt = acc_.ReplaceIn(useIt, circuit_->DeadGate());
45 }
46 }
47 acc_.DeleteGate(gate);
48 }
49
RemoveGate()50 void GraphEditor::RemoveGate()
51 {
52 while (!workList_.empty()) {
53 Edge& edge = workList_.back();
54 GateRef gate = edge.GetGate();
55 workList_.pop_back();
56 auto opcode = acc_.GetOpCode(gate);
57 switch (opcode) {
58 case OpCode::NOP:
59 case OpCode::DEAD:
60 case OpCode::VALUE_SELECTOR:
61 case OpCode::DEPEND_SELECTOR:
62 // dead op, just continue
63 break;
64 case OpCode::LOOP_BEGIN:
65 case OpCode::MERGE:
66 PropagateMerge(edge);
67 break;
68 default:
69 PropagateGate(edge);
70 break;
71 }
72 }
73 }
74
PropagateGate(const Edge & edge)75 void GraphEditor::PropagateGate(const Edge& edge)
76 {
77 GateRef gate = edge.GetGate();
78 // isStateIn
79 if (acc_.IsStateIn(gate, edge.GetIndex())) {
80 // 2: is loop begin
81 ASSERT(acc_.GetStateCount(gate) == 1 ||
82 acc_.GetStateCount(gate) == 2); // 2: LOOP_BEGIN
83 ReplaceGate(gate);
84 return;
85 }
86
87 // IsValueIn
88 if (acc_.IsValueIn(gate, edge.GetIndex())) {
89 // value gate
90 ReplaceGate(gate);
91 }
92 }
93
PropagateMerge(const Edge & edge)94 void GraphEditor::PropagateMerge(const Edge& edge)
95 {
96 GateRef gate = edge.GetGate();
97 auto numIns = acc_.GetNumIns(gate);
98 if (numIns == 1) {
99 ReplaceGate(gate);
100 } else {
101 auto uses = acc_.Uses(gate);
102 for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
103 GateRef use = *useIt;
104 // (Gate1) (Dead) (Gate2) (Gate1) (Gate2)
105 // | | | | |
106 // ___________________ ==> __________
107 // | |
108 // (phi) (phi)
109 if (acc_.GetOpCode(use) == OpCode::VALUE_SELECTOR ||
110 acc_.GetOpCode(use) == OpCode::DEPEND_SELECTOR) {
111 acc_.DecreaseIn(use, edge.GetIndex() + 1); // +1 skip state input
112 }
113 }
114 acc_.DecreaseIn(gate, edge.GetIndex());
115 }
116 }
117
EliminatePhi()118 void GraphEditor::EliminatePhi()
119 {
120 std::vector<GateRef> gateList;
121 acc_.GetAllGates(gateList);
122 std::queue<GateRef> workList;
123 std::set<GateRef> inList;
124 for (auto gate : gateList) {
125 if (acc_.IsValueSelector(gate)) {
126 workList.push(gate);
127 inList.insert(gate);
128 }
129 }
130
131 while (!workList.empty()) {
132 auto cur = workList.front();
133 workList.pop();
134 ASSERT(acc_.IsValueSelector(cur));
135 GateRef first = acc_.GetValueIn(cur, 0);
136 auto use = acc_.Uses(cur);
137 bool sameIns = true;
138 bool selfUse = first == cur;
139 bool noUses = use.begin() == use.end();
140 auto valueNum = acc_.GetNumValueIn(cur);
141 for (size_t i = 1; i < valueNum; ++i) {
142 GateRef input = acc_.GetValueIn(cur, i);
143 if (input != first) {
144 sameIns = false;
145 }
146 if (input == cur) {
147 ASSERT(acc_.IsLoopHead(acc_.GetState(cur)));
148 selfUse = true;
149 }
150 }
151 if ((!sameIns) && (!selfUse) && (!noUses)) {
152 inList.erase(cur);
153 continue;
154 }
155 for (auto it = use.begin(); it != use.end(); ++it) {
156 if (((*it) == cur) || (!acc_.IsValueSelector(*it)) || inList.count(*it)) {
157 // selfUse or notPhi or inListPhi
158 continue;
159 }
160 workList.push(*it);
161 inList.insert(*it);
162 }
163 acc_.UpdateAllUses(cur, first);
164 }
165 for (auto phi : inList) {
166 ASSERT(acc_.IsValueSelector(phi));
167 acc_.DeleteGate(phi);
168 }
169 }
170 } // namespace panda::ecmascript::kungfu
171