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 replacement_.SetState(curRegion->GetState());
152 currentIndex_ = static_cast<int32_t>(curRegion->gateList_.size() - 1); // 1: -1 for size
153 TryLoadDependStart(curRegion);
154 if (dependStart_ == Circuit::NullGate()) {
155 TryFindDependStart(curRegion);
156 }
157 ConnectStateDepend(curRegion);
158 for (; currentIndex_ > 0; currentIndex_--) {
159 auto curGate = curRegion->gateList_[currentIndex_];
160 VisitGate(curGate);
161 }
162 StoreStateDepend(curRegion);
163 }
164
ProcessStateDepend(GateRef currentGate)165 void ProcessStateDepend(GateRef currentGate)
166 {
167 auto currentState = replacement_.State();
168 auto currentDepend = replacement_.Depend();
169 if (acc_.GetStateCount(currentGate) > 0) {
170 ASSERT(acc_.GetStateCount(currentGate) == 1);
171 auto stateInput = acc_.GetState(currentGate);
172 if (currentState != stateInput) {
173 acc_.ReplaceStateIn(currentGate, currentState);
174 }
175 if (!acc_.IsVirtualState(currentGate) && !acc_.IsFixed(currentGate)) {
176 replacement_.SetState(currentGate);
177 }
178 }
179 if (acc_.GetDependCount(currentGate) > 0) {
180 ASSERT(acc_.GetDependCount(currentGate) == 1);
181 auto dependInput = acc_.GetDep(currentGate);
182 if (currentDepend != dependInput) {
183 acc_.ReplaceDependIn(currentGate, currentDepend);
184 }
185 replacement_.SetDepend(currentGate);
186 }
187 }
188
VisitGate(GateRef gate)189 void VisitGate(GateRef gate)
190 {
191 acc_.SetMark(gate, MarkCode::VISITED);
192 auto& lowering = linearizer_->lcrLowering_;
193 auto op = acc_.GetOpCode(gate);
194 switch (op) {
195 case OpCode::FRAME_STATE:
196 frameState_ = gate;
197 break;
198 case OpCode::STATE_SPLIT:
199 case OpCode::DEPEND_RELAY:
200 acc_.DeleteGate(gate);
201 return;
202 case OpCode::CONVERT:
203 ASSERT(replacement_.State() != Circuit::NullGate());
204 replacement_ = lowering.LowerConvert(replacement_, gate);
205 break;
206 case OpCode::LOAD_GETTER:
207 case OpCode::LOAD_SETTER:
208 return;
209 default:
210 break;
211 }
212 ProcessStateDepend(gate);
213 }
214
TryInsertRelay(GateRegion * curRegion)215 void TryInsertRelay(GateRegion* curRegion)
216 {
217 auto currentState = curRegion->GetState();
218 auto curGate = curRegion->gateList_[currentIndex_];
219 if (acc_.GetOpCode(curGate) != OpCode::DEPEND_RELAY ||
220 acc_.GetState(curGate) != currentState) {
221 auto circuit = acc_.GetCircuit();
222 auto dependRelay = circuit->NewGate(
223 circuit->DependRelay(), { currentState, Circuit::NullGate() });
224 replacement_.SetDepend(dependRelay);
225 ASSERT(dependStart_ == Circuit::NullGate());
226 acc_.SetMark(dependRelay, MarkCode::VISITED);
227 dependStart_ = dependRelay;
228 }
229 }
230
TryLoadDependStart(GateRegion * curRegion)231 void TryLoadDependStart(GateRegion* curRegion)
232 {
233 auto currentState = curRegion->GetState();
234 if (dependStart_ == Circuit::NullGate()) {
235 if (curRegion->preds_.size() == 1) {
236 auto &edge = map_.GetEdge(curRegion->preds_[0], curRegion);
237 ASSERT(edge.dependOut != Circuit::NullGate());
238 replacement_.SetDepend(edge.dependOut);
239 frameState_ = edge.frameStateOut;
240 }
241
242 auto opcode = acc_.GetOpCode(currentState);
243 switch (opcode) {
244 case OpCode::IF_EXCEPTION:
245 dependStart_ = currentState;
246 replacement_.SetDepend(dependStart_);
247 break;
248 case OpCode::IF_TRUE:
249 case OpCode::IF_FALSE:
250 TryInsertRelay(curRegion);
251 break;
252 default:
253 break;
254 }
255 }
256 }
257
ConnectStateDepend(GateRegion * curRegion)258 void ConnectStateDepend(GateRegion* curRegion)
259 {
260 auto currentState = curRegion->GetState();
261 ASSERT(dependStart_ == Circuit::NullGate() ||
262 curRegion->preds_.size() == acc_.GetDependCount(dependStart_));
263 ASSERT(curRegion->preds_.size() == acc_.GetStateCount(currentState));
264 for (size_t i = 0; i < curRegion->preds_.size(); i++) {
265 auto pred = curRegion->preds_[i];
266 auto &edge = map_.GetEdge(pred, curRegion);
267 auto stateInput = acc_.GetState(currentState, i);
268 if (edge.stateOut == Circuit::NullGate()) {
269 ASSERT(edge.dependOut == Circuit::NullGate());
270 pendingEdges_.emplace_back(PendingGateRegionEdge(pred, curRegion, dependStart_, i));
271 } else {
272 ConnectEdge(edge, currentState, stateInput, i);
273 }
274 }
275 }
276
ConnectEdge(RegionEdge & edge,GateRef currentState,GateRef stateInput,size_t i)277 void ConnectEdge(RegionEdge& edge, GateRef currentState, GateRef stateInput, size_t i)
278 {
279 if (edge.stateOut != stateInput) {
280 acc_.ReplaceStateIn(currentState, edge.stateOut, i);
281 }
282 if (frameState_ == Circuit::NullGate()) {
283 frameState_ = edge.frameStateOut;
284 }
285 if (dependStart_ != Circuit::NullGate()) {
286 auto dependInput = acc_.GetDep(dependStart_, i);
287 if (edge.dependOut != dependInput) {
288 acc_.ReplaceOrNewDependIn(dependStart_, edge.dependOut, i);
289 }
290 }
291 }
292
ConnectPendingRegionEdges()293 void ConnectPendingRegionEdges()
294 {
295 for (auto regionEdge : pendingEdges_) {
296 auto currentState = regionEdge.to->GetState();
297 auto stateInput = acc_.GetState(currentState, regionEdge.index);
298 auto &edge = map_.GetEdge(regionEdge.from, regionEdge.to);
299 if (edge.stateOut != stateInput) {
300 acc_.ReplaceStateIn(currentState, edge.stateOut, regionEdge.index);
301 }
302 auto dependInput = acc_.GetDep(regionEdge.dependStart, regionEdge.index);
303 if (edge.dependOut != dependInput) {
304 acc_.ReplaceDependIn(regionEdge.dependStart, edge.dependOut, regionEdge.index);
305 }
306 }
307 }
308
StoreStateDepend(GateRegion * curRegion)309 void StoreStateDepend(GateRegion* curRegion)
310 {
311 for (auto succ : curRegion->succs_) {
312 auto &edge = map_.GetEdge(curRegion, succ);
313 if (edge.stateOut == Circuit::NullGate()) {
314 edge.stateOut = replacement_.State();
315 }
316 if (edge.dependOut == Circuit::NullGate()) {
317 edge.dependOut = replacement_.Depend();
318 }
319 if (edge.frameStateOut == Circuit::NullGate()) {
320 edge.frameStateOut = frameState_;
321 }
322 }
323 replacement_.Reset();
324 frameState_ = Circuit::NullGate();
325 dependStart_ = Circuit::NullGate();
326 currentIndex_ = -1;
327 }
328
329 private:
330 GateRef dependStart_ {Circuit::NullGate()};
331 GateRef frameState_ {Circuit::NullGate()};
332 StateDepend replacement_;
333 int32_t currentIndex_ {-1};
334 StateSplitLinearizer* linearizer_ {nullptr};
335 ChunkDeque<GateRegion*> pendingList_;
336 GateAccessor acc_;
337 RegionStateDependMap map_;
338 ChunkVector<PendingGateRegionEdge> pendingEdges_;
339 size_t maxGateId_ {0};
340 };
341
LinearizeStateSplit()342 void StateSplitLinearizer::LinearizeStateSplit()
343 {
344 StateDependBuilder builder(this, graphLinearizer_.chunk_);
345 builder.Run(graphLinearizer_.regionList_);
346 }
347
348 } // namespace panda::ecmascript::kungfu
349