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_visitor.h"
19
20 namespace panda::ecmascript::kungfu {
21
ReplaceGate(GateRef gate,GateRef replacement)22 void GraphVisitor::ReplaceGate(GateRef gate, GateRef replacement)
23 {
24 GateRef depend = Circuit::NullGate();
25 if (acc_.GetDependCount(gate) > 0) {
26 ASSERT(acc_.GetDependCount(gate) == 1); // 1: one dep
27 depend = acc_.GetDep(gate);
28 }
29 GateRef state = Circuit::NullGate();
30 if (acc_.GetStateCount(gate) > 0) {
31 ASSERT(acc_.GetStateCount(gate) == 1); // 1: one state
32 state = acc_.GetState(gate);
33 }
34 return ReplaceGate(gate, StateDepend {state, depend}, replacement);
35 }
36
ReplaceGate(GateRef gate,StateDepend stateDepend,GateRef replacement)37 void GraphVisitor::ReplaceGate(GateRef gate, StateDepend stateDepend, GateRef replacement)
38 {
39 ASSERT(gate != replacement);
40 auto state = stateDepend.State();
41 auto depend = stateDepend.Depend();
42 auto uses = acc_.Uses(gate);
43 for (auto it = uses.begin(); it != uses.end();) {
44 if (acc_.GetMark(*it) == MarkCode::FINISHED) {
45 PushChangedGate(*it);
46 }
47 if (acc_.IsStateIn(it)) {
48 ASSERT(state != Circuit::NullGate());
49 it = acc_.ReplaceIn(it, state);
50 } else if (acc_.IsDependIn(it)) {
51 ASSERT(depend != Circuit::NullGate());
52 it = acc_.ReplaceIn(it, depend);
53 } else {
54 it = acc_.ReplaceIn(it, replacement);
55 }
56 }
57 acc_.DeleteGate(gate);
58 }
59
VisitGraph()60 void GraphVisitor::VisitGraph()
61 {
62 circuit_->AdvanceTime();
63 orderCount_ = 0;
64 orderList_.resize(circuit_->GetMaxGateId() + 1, -1);
65 GateRef returnList = acc_.GetReturnRoot();
66 auto uses = acc_.Uses(returnList);
67 for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
68 PushChangedGate(*useIt);
69 }
70
71 while (true) {
72 if (!workList_.empty()) {
73 Edge& current = workList_.back();
74 VisitTopGate(current);
75 } else if (!changedList_.empty()) {
76 GateRef gate = changedList_.back();
77 changedList_.pop_back();
78 if (acc_.GetMark(gate) == MarkCode::PREVISIT) {
79 PushGate(gate, 0);
80 }
81 } else {
82 break;
83 }
84 }
85 }
86
ReVisitGate(GateRef gate)87 void GraphVisitor::ReVisitGate(GateRef gate)
88 {
89 if (acc_.GetMark(gate) == MarkCode::FINISHED) {
90 PushChangedGate(gate);
91 }
92 }
93
GetGateOrder(GateRef gate) const94 int32_t GraphVisitor::GetGateOrder(GateRef gate) const
95 {
96 return orderList_[acc_.GetId(gate)];
97 }
98
SetGateOrder(GateRef gate,int32_t orderId)99 void GraphVisitor::SetGateOrder(GateRef gate, int32_t orderId)
100 {
101 orderList_[acc_.GetId(gate)] = orderId;
102 }
103
104 // Reverse post-order
VisitTopGate(Edge & current)105 void GraphVisitor::VisitTopGate(Edge& current)
106 {
107 GateRef gate = current.GetGate();
108 // gate is delete or dead
109 if (acc_.IsNop(gate)) {
110 PopGate(gate);
111 return;
112 }
113 auto numIns = acc_.GetNumIns(gate);
114 for (size_t i = current.GetIndex(); i < numIns; i++) {
115 GateRef input = acc_.GetIn(gate, i);
116 if (input == gate) {
117 continue;
118 }
119 // find not visited gate, push stack
120 if (acc_.GetMark(input) < MarkCode::VISITED) {
121 PushGate(input, 0);
122 // next index
123 current.SetIndex(i + 1);
124 return;
125 }
126 }
127 // all input are visited
128 if (GetGateOrder(gate) == -1) { // -1 : not visited before
129 SetGateOrder(gate, ++orderCount_);
130 }
131 GateRef replacement = VisitGate(gate);
132 PopGate(gate);
133 if (replacement == Circuit::NullGate()) {
134 return;
135 }
136 if (replacement != gate) {
137 ReplaceGate(gate, replacement);
138 } else {
139 // revisit not on stack gate.
140 auto uses = acc_.Uses(gate);
141 for (auto it = uses.begin(); it != uses.end(); it++) {
142 if (acc_.GetMark(*it) == MarkCode::FINISHED) {
143 PushChangedGate(*it);
144 }
145 }
146 }
147 }
148
PrintStack()149 void GraphVisitor::PrintStack()
150 {
151 std::string log;
152 for (size_t i = 0; i < workList_.size(); i++) {
153 Edge current = workList_[i];
154 GateRef gate = current.GetGate();
155 log += std::to_string(acc_.GetId(gate)) + ", ";
156 }
157 LOG_COMPILER(INFO) << std::dec << log;
158 }
159
160 } // namespace panda::ecmascript::kungfu