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/state_split_linearizer.h"
17 #include "ecmascript/compiler/scheduler.h"
18
19 namespace panda::ecmascript::kungfu {
Run()20 void StateSplitLinearizer::Run()
21 {
22 graphLinearizer_.SetScheduleJSOpcode();
23 graphLinearizer_.LinearizeGraph();
24 LinearizeStateSplit();
25 if (IsLogEnabled()) {
26 LOG_COMPILER(INFO) << "";
27 LOG_COMPILER(INFO) << "\033[34m"
28 << "===================="
29 << " After state split linearizer "
30 << "[" << GetMethodName() << "]"
31 << "===================="
32 << "\033[0m";
33 circuit_->PrintAllGatesWithBytecode();
34 LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
35 }
36 #ifndef NDEBUG
37 graphLinearizer_.Reset();
38 graphLinearizer_.EnableScheduleUpperBound();
39 graphLinearizer_.SetScheduleJSOpcode();
40 graphLinearizer_.LinearizeGraph();
41 if (IsLogEnabled()) {
42 LOG_COMPILER(INFO) << "";
43 LOG_COMPILER(INFO) << "\033[34m"
44 << "===================="
45 << " verify split linearizer "
46 << "[" << GetMethodName() << "]"
47 << "===================="
48 << "\033[0m";
49 graphLinearizer_.PrintGraph("Build Basic Block");
50 LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
51 }
52 #endif
53 }
54
55 struct RegionEdge {
56 GateRef stateOut {Circuit::NullGate()};
57 GateRef dependOut {Circuit::NullGate()};
58 GateRef frameStateOut {Circuit::NullGate()};
59 };
60
61 struct PendingGateRegionEdge {
PendingGateRegionEdgepanda::ecmascript::kungfu::PendingGateRegionEdge62 explicit PendingGateRegionEdge(GateRegion* from, GateRegion* to,
63 GateRef dependStart, size_t index) : from(from), to(to),
64 dependStart(dependStart), index(index) {}
65
66 GateRegion* from;
67 GateRegion* to;
68 GateRef dependStart;
69 size_t index;
70 };
71
72 class RegionStateDependMap {
73 public:
RegionStateDependMap(Chunk * chunk)74 explicit RegionStateDependMap(Chunk* chunk) : regionMap_(chunk) {}
GetEdge(GateRegion * from,GateRegion * to)75 RegionEdge& GetEdge(GateRegion* from, GateRegion* to)
76 {
77 return regionMap_[std::make_pair(from->GetId(), to->GetId())];
78 }
79 private:
80 ChunkMap<std::pair<size_t, size_t>, RegionEdge> regionMap_;
81 };
82
83 class StateDependBuilder {
84 public:
StateDependBuilder(StateSplitLinearizer * linearizer,Chunk * chunk)85 explicit StateDependBuilder(StateSplitLinearizer* linearizer, Chunk* chunk)
86 : linearizer_(linearizer), pendingList_(chunk),
87 acc_(linearizer->circuit_), map_(chunk), pendingEdges_(chunk) {}
88
Run(ChunkVector<GateRegion * > & regionList)89 void Run(ChunkVector<GateRegion*>& regionList)
90 {
91 maxGateId_ = acc_.GetCircuit()->GetMaxGateId();
92 replacement_.SetDepend(acc_.GetDependRoot());
93 dependStart_ = replacement_.Depend();
94 auto entry = regionList.front();
95 acc_.GetCircuit()->AdvanceTime();
96 entry->SetVisited(acc_);
97 ASSERT(pendingList_.empty());
98 pendingList_.emplace_back(entry);
99 while (!pendingList_.empty()) {
100 auto curRegion = pendingList_.back();
101 pendingList_.pop_back();
102 VisitRegion(curRegion);
103 for (auto succ : curRegion->succs_) {
104 if (!succ->IsVisited(acc_)) {
105 succ->SetVisited(acc_);
106 pendingList_.emplace_back(succ);
107 }
108 }
109 }
110 ConnectPendingRegionEdges();
111 DeleteUnusedGates();
112 }
113
DeleteUnusedGates()114 void DeleteUnusedGates()
115 {
116 std::vector<GateRef> gateList;
117 auto circuit = acc_.GetCircuit();
118 circuit->GetAllGates(gateList);
119
120 for (const auto &gate : gateList) {
121 if (acc_.GetMark(gate) == MarkCode::NO_MARK &&
122 !acc_.IsProlog(gate) && !acc_.IsRoot(gate) &&
123 acc_.GetId(gate) <= maxGateId_) {
124 acc_.DeleteGate(gate);
125 }
126 }
127 }
128
TryFindDependStart(GateRegion * curRegion)129 void TryFindDependStart(GateRegion* curRegion)
130 {
131 // 0: is state
132 for (; currentIndex_ > 0; currentIndex_--) {
133 auto curGate = curRegion->gateList_[currentIndex_];
134 auto op = acc_.GetOpCode(curGate);
135 if (op == OpCode::DEPEND_SELECTOR || op == OpCode::DEPEND_RELAY) {
136 replacement_.SetDepend(curGate);
137 dependStart_ = curGate;
138 acc_.SetMark(curGate, MarkCode::VISITED);
139 } else {
140 VisitGate(curGate);
141 }
142 if (dependStart_ != Circuit::NullGate()) {
143 currentIndex_--;
144 break;
145 }
146 }
147 }
148
VisitRegion(GateRegion * curRegion)149 void VisitRegion(GateRegion* curRegion)
150 {
151 ASSERT(curRegion->gateList_.size() > 0);
152 replacement_.SetState(curRegion->GetState());
153 currentIndex_ = static_cast<int32_t>(curRegion->gateList_.size() - 1); // 1: -1 for size
154 TryLoadDependStart(curRegion);
155 if (dependStart_ == Circuit::NullGate()) {
156 TryFindDependStart(curRegion);
157 }
158 ConnectStateDepend(curRegion);
159 for (; currentIndex_ > 0; currentIndex_--) {
160 auto curGate = curRegion->gateList_[currentIndex_];
161 VisitGate(curGate);
162 }
163 StoreStateDepend(curRegion);
164 }
165
ProcessStateDepend(GateRef currentGate)166 void ProcessStateDepend(GateRef currentGate)
167 {
168 auto currentState = replacement_.State();
169 auto currentDepend = replacement_.Depend();
170 if (acc_.GetStateCount(currentGate) > 0) {
171 ASSERT(acc_.GetStateCount(currentGate) == 1);
172 auto stateInput = acc_.GetState(currentGate);
173 if (currentState != stateInput) {
174 acc_.ReplaceStateIn(currentGate, currentState);
175 }
176 if (!acc_.IsVirtualState(currentGate) && !acc_.IsFixed(currentGate)) {
177 replacement_.SetState(currentGate);
178 }
179 }
180 if (acc_.GetDependCount(currentGate) > 0) {
181 ASSERT(acc_.GetDependCount(currentGate) == 1);
182 auto dependInput = acc_.GetDep(currentGate);
183 if (currentDepend != dependInput) {
184 acc_.ReplaceDependIn(currentGate, currentDepend);
185 }
186 replacement_.SetDepend(currentGate);
187 }
188 }
189
VisitGate(GateRef gate)190 void VisitGate(GateRef gate)
191 {
192 acc_.SetMark(gate, MarkCode::VISITED);
193 auto& lowering = linearizer_->lcrLowering_;
194 auto op = acc_.GetOpCode(gate);
195 switch (op) {
196 case OpCode::FRAME_STATE:
197 frameState_ = gate;
198 break;
199 case OpCode::STATE_SPLIT:
200 case OpCode::DEPEND_RELAY:
201 acc_.DeleteGate(gate);
202 return;
203 case OpCode::CONVERT:
204 ASSERT(replacement_.State() != Circuit::NullGate());
205 replacement_ = lowering.LowerConvert(replacement_, gate);
206 break;
207 default:
208 break;
209 }
210 ProcessStateDepend(gate);
211 }
212
TryInsertRelay(GateRegion * curRegion)213 void TryInsertRelay(GateRegion* curRegion)
214 {
215 auto currentState = curRegion->GetState();
216 auto curGate = curRegion->gateList_[currentIndex_];
217 if (acc_.GetOpCode(curGate) != OpCode::DEPEND_RELAY ||
218 acc_.GetState(curGate) != currentState) {
219 auto circuit = acc_.GetCircuit();
220 auto dependRelay = circuit->NewGate(
221 circuit->DependRelay(), { currentState, Circuit::NullGate() });
222 replacement_.SetDepend(dependRelay);
223 ASSERT(dependStart_ == Circuit::NullGate());
224 acc_.SetMark(dependRelay, MarkCode::VISITED);
225 dependStart_ = dependRelay;
226 }
227 }
228
TryLoadDependStart(GateRegion * curRegion)229 void TryLoadDependStart(GateRegion* curRegion)
230 {
231 auto currentState = curRegion->GetState();
232 if (dependStart_ == Circuit::NullGate()) {
233 if (curRegion->preds_.size() == 1) {
234 auto &edge = map_.GetEdge(curRegion->preds_[0], curRegion);
235 ASSERT(edge.dependOut != Circuit::NullGate());
236 replacement_.SetDepend(edge.dependOut);
237 frameState_ = edge.frameStateOut;
238 }
239
240 auto opcode = acc_.GetOpCode(currentState);
241 switch (opcode) {
242 case OpCode::IF_EXCEPTION:
243 dependStart_ = currentState;
244 replacement_.SetDepend(dependStart_);
245 break;
246 case OpCode::IF_TRUE:
247 case OpCode::IF_FALSE:
248 TryInsertRelay(curRegion);
249 break;
250 default:
251 break;
252 }
253 }
254 }
255
ConnectStateDepend(GateRegion * curRegion)256 void ConnectStateDepend(GateRegion* curRegion)
257 {
258 auto currentState = curRegion->GetState();
259 ASSERT(dependStart_ == Circuit::NullGate() ||
260 curRegion->preds_.size() == acc_.GetDependCount(dependStart_));
261 ASSERT(curRegion->preds_.size() == acc_.GetStateCount(currentState));
262 for (size_t i = 0; i < curRegion->preds_.size(); i++) {
263 auto pred = curRegion->preds_[i];
264 auto &edge = map_.GetEdge(pred, curRegion);
265 auto stateInput = acc_.GetState(currentState, i);
266 if (edge.stateOut == Circuit::NullGate()) {
267 ASSERT(edge.dependOut == Circuit::NullGate());
268 pendingEdges_.emplace_back(PendingGateRegionEdge(pred, curRegion, dependStart_, i));
269 } else {
270 ConnectEdge(edge, currentState, stateInput, i);
271 }
272 }
273 }
274
ConnectEdge(RegionEdge & edge,GateRef currentState,GateRef stateInput,size_t i)275 void ConnectEdge(RegionEdge& edge, GateRef currentState, GateRef stateInput, size_t i)
276 {
277 if (edge.stateOut != stateInput) {
278 acc_.ReplaceStateIn(currentState, edge.stateOut, i);
279 }
280 if (frameState_ == Circuit::NullGate()) {
281 frameState_ = edge.frameStateOut;
282 }
283 if (dependStart_ != Circuit::NullGate()) {
284 auto dependInput = acc_.GetDep(dependStart_, i);
285 if (edge.dependOut != dependInput) {
286 acc_.ReplaceOrNewDependIn(dependStart_, edge.dependOut, i);
287 }
288 }
289 }
290
ConnectPendingRegionEdges()291 void ConnectPendingRegionEdges()
292 {
293 for (auto regionEdge : pendingEdges_) {
294 auto currentState = regionEdge.to->GetState();
295 auto stateInput = acc_.GetState(currentState, regionEdge.index);
296 auto &edge = map_.GetEdge(regionEdge.from, regionEdge.to);
297 if (edge.stateOut != stateInput) {
298 acc_.ReplaceStateIn(currentState, edge.stateOut, regionEdge.index);
299 }
300 auto dependInput = acc_.GetDep(regionEdge.dependStart, regionEdge.index);
301 if (edge.dependOut != dependInput) {
302 acc_.ReplaceDependIn(regionEdge.dependStart, edge.dependOut, regionEdge.index);
303 }
304 }
305 }
306
StoreStateDepend(GateRegion * curRegion)307 void StoreStateDepend(GateRegion* curRegion)
308 {
309 for (auto succ : curRegion->succs_) {
310 auto &edge = map_.GetEdge(curRegion, succ);
311 if (edge.stateOut == Circuit::NullGate()) {
312 edge.stateOut = replacement_.State();
313 }
314 if (edge.dependOut == Circuit::NullGate()) {
315 edge.dependOut = replacement_.Depend();
316 }
317 if (edge.frameStateOut == Circuit::NullGate()) {
318 edge.frameStateOut = frameState_;
319 }
320 }
321 replacement_.Reset();
322 frameState_ = Circuit::NullGate();
323 dependStart_ = Circuit::NullGate();
324 currentIndex_ = -1;
325 }
326
327 private:
328 GateRef dependStart_ {Circuit::NullGate()};
329 GateRef frameState_ {Circuit::NullGate()};
330 StateDepend replacement_;
331 int32_t currentIndex_ {-1};
332 StateSplitLinearizer* linearizer_ {nullptr};
333 ChunkDeque<GateRegion*> pendingList_;
334 GateAccessor acc_;
335 RegionStateDependMap map_;
336 ChunkVector<PendingGateRegionEdge> pendingEdges_;
337 size_t maxGateId_ {0};
338 };
339
LinearizeStateSplit()340 void StateSplitLinearizer::LinearizeStateSplit()
341 {
342 StateDependBuilder builder(this, graphLinearizer_.chunk_);
343 builder.Run(graphLinearizer_.regionList_);
344 }
345
346 } // namespace panda::ecmascript::kungfu
347