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
18 namespace panda::ecmascript::kungfu {
Run()19 void StateSplitLinearizer::Run()
20 {
21 graphLinearizer_.SetScheduleJSOpcode();
22 graphLinearizer_.LinearizeGraph();
23 LinearizeStateSplit();
24 if (IsLogEnabled()) {
25 LOG_COMPILER(INFO) << "";
26 LOG_COMPILER(INFO) << "\033[34m"
27 << "===================="
28 << " After state split linearizer "
29 << "[" << GetMethodName() << "]"
30 << "===================="
31 << "\033[0m";
32 circuit_->PrintAllGatesWithBytecode();
33 LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
34 }
35 #ifndef NDEBUG
36 graphLinearizer_.Reset();
37 graphLinearizer_.EnableScheduleUpperBound();
38 graphLinearizer_.SetScheduleJSOpcode();
39 graphLinearizer_.LinearizeGraph();
40 if (IsLogEnabled()) {
41 LOG_COMPILER(INFO) << "";
42 LOG_COMPILER(INFO) << "\033[34m"
43 << "===================="
44 << " verify split linearizer "
45 << "[" << GetMethodName() << "]"
46 << "===================="
47 << "\033[0m";
48 graphLinearizer_.PrintGraph("Build Basic Block");
49 LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
50 }
51 #endif
52 }
53
54 struct RegionEdge {
55 GateRef stateOut {Circuit::NullGate()};
56 GateRef dependOut {Circuit::NullGate()};
57 GateRef frameStateOut {Circuit::NullGate()};
58 };
59
60 struct PendingGateRegionEdge {
PendingGateRegionEdgepanda::ecmascript::kungfu::PendingGateRegionEdge61 explicit PendingGateRegionEdge(GateRegion* from, GateRegion* to,
62 GateRef dependStart, size_t index) : from(from), to(to),
63 dependStart(dependStart), index(index) {}
64
65 GateRegion* from;
66 GateRegion* to;
67 GateRef dependStart;
68 size_t index;
69 };
70
71 class RegionStateDependMap {
72 public:
RegionStateDependMap(Chunk * chunk)73 explicit RegionStateDependMap(Chunk* chunk) : regionMap_(chunk) {}
GetEdge(GateRegion * from,GateRegion * to)74 RegionEdge& GetEdge(GateRegion* from, GateRegion* to)
75 {
76 return regionMap_[std::make_pair(from->GetId(), to->GetId())];
77 }
78 private:
79 ChunkMap<std::pair<size_t, size_t>, RegionEdge> regionMap_;
80 };
81
82 class StateDependBuilder {
83 public:
StateDependBuilder(StateSplitLinearizer * linearizer,Chunk * chunk)84 explicit StateDependBuilder(StateSplitLinearizer* linearizer, Chunk* chunk)
85 : linearizer_(linearizer), pendingList_(chunk),
86 acc_(linearizer->circuit_), map_(chunk), pendingEdges_(chunk) {}
87
Run(ChunkVector<GateRegion * > & regionList)88 void Run(ChunkVector<GateRegion*>& regionList)
89 {
90 maxGateId_ = acc_.GetCircuit()->GetMaxGateId();
91 replacement_.SetDepend(acc_.GetDependRoot());
92 dependStart_ = replacement_.Depend();
93 auto entry = regionList.front();
94 acc_.GetCircuit()->AdvanceTime();
95 entry->SetVisited(acc_);
96 ASSERT(pendingList_.empty());
97 pendingList_.emplace_back(entry);
98 while (!pendingList_.empty()) {
99 auto curRegion = pendingList_.back();
100 pendingList_.pop_back();
101 VisitRegion(curRegion);
102 for (auto succ : curRegion->succs_) {
103 if (!succ->IsVisited(acc_)) {
104 succ->SetVisited(acc_);
105 pendingList_.emplace_back(succ);
106 }
107 }
108 }
109 ConnectPendingRegionEdges();
110 DeleteUnusedGates();
111 }
112
DeleteUnusedGates()113 void DeleteUnusedGates()
114 {
115 std::vector<GateRef> gateList;
116 auto circuit = acc_.GetCircuit();
117 circuit->GetAllGates(gateList);
118
119 for (const auto &gate : gateList) {
120 if (acc_.GetMark(gate) == MarkCode::NO_MARK &&
121 !acc_.IsProlog(gate) && !acc_.IsRoot(gate) &&
122 acc_.GetId(gate) <= maxGateId_) {
123 acc_.DeleteGate(gate);
124 }
125 }
126 }
127
TryFindDependStart(GateRegion * curRegion)128 void TryFindDependStart(GateRegion* curRegion)
129 {
130 // 0: is state
131 for (; currentIndex_ > 0; currentIndex_--) {
132 auto curGate = curRegion->gateList_[currentIndex_];
133 auto op = acc_.GetOpCode(curGate);
134 if (op == OpCode::DEPEND_SELECTOR || op == OpCode::DEPEND_RELAY) {
135 replacement_.SetDepend(curGate);
136 dependStart_ = curGate;
137 acc_.SetMark(curGate, MarkCode::VISITED);
138 } else {
139 VisitGate(curGate);
140 }
141 if (dependStart_ != Circuit::NullGate()) {
142 currentIndex_--;
143 break;
144 }
145 }
146 }
147
VisitRegion(GateRegion * curRegion)148 void VisitRegion(GateRegion* curRegion)
149 {
150 ASSERT(curRegion->gateList_.size() > 0);
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 default:
207 break;
208 }
209 ProcessStateDepend(gate);
210 }
211
TryInsertRelay(GateRegion * curRegion)212 void TryInsertRelay(GateRegion* curRegion)
213 {
214 auto currentState = curRegion->GetState();
215 auto curGate = curRegion->gateList_[currentIndex_];
216 if (acc_.GetOpCode(curGate) != OpCode::DEPEND_RELAY ||
217 acc_.GetState(curGate) != currentState) {
218 auto circuit = acc_.GetCircuit();
219 auto dependRelay = circuit->NewGate(
220 circuit->DependRelay(), { currentState, Circuit::NullGate() });
221 replacement_.SetDepend(dependRelay);
222 ASSERT(dependStart_ == Circuit::NullGate());
223 acc_.SetMark(dependRelay, MarkCode::VISITED);
224 dependStart_ = dependRelay;
225 }
226 }
227
TryLoadDependStart(GateRegion * curRegion)228 void TryLoadDependStart(GateRegion* curRegion)
229 {
230 auto currentState = curRegion->GetState();
231 if (dependStart_ == Circuit::NullGate()) {
232 if (curRegion->preds_.size() == 1) {
233 auto &edge = map_.GetEdge(curRegion->preds_[0], curRegion);
234 ASSERT(edge.dependOut != Circuit::NullGate());
235 replacement_.SetDepend(edge.dependOut);
236 frameState_ = edge.frameStateOut;
237 }
238
239 auto opcode = acc_.GetOpCode(currentState);
240 switch (opcode) {
241 case OpCode::IF_EXCEPTION:
242 dependStart_ = currentState;
243 replacement_.SetDepend(dependStart_);
244 break;
245 case OpCode::IF_TRUE:
246 case OpCode::IF_FALSE:
247 TryInsertRelay(curRegion);
248 break;
249 default:
250 break;
251 }
252 }
253 }
254
ConnectStateDepend(GateRegion * curRegion)255 void ConnectStateDepend(GateRegion* curRegion)
256 {
257 auto currentState = curRegion->GetState();
258 ASSERT(dependStart_ == Circuit::NullGate() ||
259 curRegion->preds_.size() == acc_.GetDependCount(dependStart_));
260 ASSERT(curRegion->preds_.size() == acc_.GetStateCount(currentState));
261 for (size_t i = 0; i < curRegion->preds_.size(); i++) {
262 auto pred = curRegion->preds_[i];
263 auto &edge = map_.GetEdge(pred, curRegion);
264 auto stateInput = acc_.GetState(currentState, i);
265 if (edge.stateOut == Circuit::NullGate()) {
266 ASSERT(edge.dependOut == Circuit::NullGate());
267 pendingEdges_.emplace_back(PendingGateRegionEdge(pred, curRegion, dependStart_, i));
268 } else {
269 ConnectEdge(edge, currentState, stateInput, i);
270 }
271 }
272 }
273
ConnectEdge(RegionEdge & edge,GateRef currentState,GateRef stateInput,size_t i)274 void ConnectEdge(RegionEdge& edge, GateRef currentState, GateRef stateInput, size_t i)
275 {
276 if (edge.stateOut != stateInput) {
277 acc_.ReplaceStateIn(currentState, edge.stateOut, i);
278 }
279 if (frameState_ == Circuit::NullGate()) {
280 frameState_ = edge.frameStateOut;
281 }
282 if (dependStart_ != Circuit::NullGate()) {
283 auto dependInput = acc_.GetDep(dependStart_, i);
284 if (edge.dependOut != dependInput) {
285 acc_.ReplaceOrNewDependIn(dependStart_, edge.dependOut, i);
286 }
287 }
288 }
289
ConnectPendingRegionEdges()290 void ConnectPendingRegionEdges()
291 {
292 for (auto regionEdge : pendingEdges_) {
293 auto currentState = regionEdge.to->GetState();
294 auto stateInput = acc_.GetState(currentState, regionEdge.index);
295 auto &edge = map_.GetEdge(regionEdge.from, regionEdge.to);
296 if (edge.stateOut != stateInput) {
297 acc_.ReplaceStateIn(currentState, edge.stateOut, regionEdge.index);
298 }
299 // fuzz: not all the region has depend edge
300 if (regionEdge.dependStart != Circuit::NullGate()) {
301 auto dependInput = acc_.GetDep(regionEdge.dependStart, regionEdge.index);
302 if (edge.dependOut != dependInput) {
303 acc_.ReplaceDependIn(regionEdge.dependStart, edge.dependOut, regionEdge.index);
304 }
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