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/graph_linearizer.h"
17 #include "ecmascript/compiler/gate.h"
18 #include "ecmascript/compiler/scheduler.h"
19
20 namespace panda::ecmascript::kungfu {
Run(ControlFlowGraph & result)21 void GraphLinearizer::Run(ControlFlowGraph &result)
22 {
23 LinearizeGraph();
24 LinearizeRegions(result);
25
26 if (IsLogEnabled()) {
27 LOG_COMPILER(INFO) << "";
28 LOG_COMPILER(INFO) << "\033[34m"
29 << "===================="
30 << " After graph linearizer "
31 << "[" << GetMethodName() << "]"
32 << "===================="
33 << "\033[0m";
34 PrintGraph("Build Basic Block");
35 LOG_COMPILER(INFO) << "\033[34m" << "========================= End ==========================" << "\033[0m";
36 }
37 }
38
39 class CFGBuilder {
40 public:
CFGBuilder(GraphLinearizer * linearizer)41 explicit CFGBuilder(GraphLinearizer *linearizer)
42 : linearizer_(linearizer), pendingList_(linearizer->chunk_),
43 endStateList_(linearizer->chunk_),
44 acc_(linearizer->circuit_), scheduleLIR_(linearizer->IsSchedueLIR()) {}
45
Run()46 void Run()
47 {
48 VisitStateGates();
49 // connect region
50 for (auto rootGate : linearizer_->regionRootList_) {
51 auto toRegion = linearizer_->GateToRegion(rootGate);
52 auto numStateIn = acc_.GetStateCount(rootGate);
53 for (size_t i = 0; i < numStateIn; i++) {
54 auto input = acc_.GetState(rootGate, i);
55 ASSERT(acc_.IsState(input) || acc_.GetOpCode(input) == OpCode::STATE_ENTRY);
56 auto fromRegion = linearizer_->FindPredRegion(input);
57 fromRegion->AddSucc(toRegion);
58 }
59 }
60 for (auto fixedGate : endStateList_) {
61 auto state = acc_.GetState(fixedGate);
62 auto region = linearizer_->FindPredRegion(state);
63 linearizer_->AddFixedGateToRegion(fixedGate, region);
64 linearizer_->BindGate(fixedGate, region);
65 }
66 }
67
VisitStateGates()68 void VisitStateGates()
69 {
70 ASSERT(pendingList_.empty());
71 linearizer_->circuit_->AdvanceTime();
72 auto startGate = acc_.GetStateRoot();
73 acc_.SetMark(startGate, MarkCode::VISITED);
74 pendingList_.emplace_back(startGate);
75 bool litecg = linearizer_->enableLiteCG();
76 while (!pendingList_.empty()) {
77 auto curGate = pendingList_.back();
78 pendingList_.pop_back();
79 VisitStateGate(curGate);
80 if (acc_.GetOpCode(curGate) != OpCode::LOOP_BACK) {
81 auto uses = acc_.Uses(curGate);
82 // The LiteCG backend is unable to perform branch prediction scheduling, thus requiring advance
83 // preparation
84 if (litecg && acc_.GetOpCode(curGate) == OpCode::IF_BRANCH && acc_.HasBranchWeight(curGate)) {
85 std::vector<GateRef> outs;
86 acc_.GetOutStates(curGate, outs);
87 GateRef bTrue = (acc_.GetOpCode(outs[0]) == OpCode::IF_TRUE) ? outs[0] : outs[1];
88 GateRef bFalse = (acc_.GetOpCode(outs[0]) == OpCode::IF_FALSE) ? outs[0] : outs[1];
89 if (acc_.GetTrueWeight(curGate) >= acc_.GetFalseWeight(curGate)) {
90 std::swap(bTrue, bFalse);
91 }
92 if (acc_.GetMark(bTrue) == MarkCode::NO_MARK) {
93 acc_.SetMark(bTrue, MarkCode::VISITED);
94 pendingList_.emplace_back(bTrue);
95 }
96 if (acc_.GetMark(bFalse) == MarkCode::NO_MARK) {
97 acc_.SetMark(bFalse, MarkCode::VISITED);
98 pendingList_.emplace_back(bFalse);
99 }
100 continue;
101 }
102 for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
103 if (acc_.IsStateIn(useIt) && acc_.IsState(*useIt) && acc_.GetMark(*useIt) == MarkCode::NO_MARK) {
104 acc_.SetMark(*useIt, MarkCode::VISITED);
105 pendingList_.emplace_back(*useIt);
106 }
107 }
108 }
109 }
110 }
111
VisitStateGate(GateRef gate)112 void VisitStateGate(GateRef gate)
113 {
114 if (scheduleLIR_) {
115 linearizer_->CreateGateRegion(gate);
116 } else {
117 auto op = acc_.GetOpCode(gate);
118 switch (op) {
119 case OpCode::LOOP_BEGIN:
120 case OpCode::MERGE:
121 case OpCode::IF_TRUE:
122 case OpCode::IF_FALSE:
123 case OpCode::SWITCH_CASE:
124 case OpCode::STATE_ENTRY:
125 case OpCode::IF_EXCEPTION:
126 case OpCode::IF_SUCCESS: {
127 linearizer_->CreateGateRegion(gate);
128 if (linearizer_->onlyBB_) {
129 currentRegion_ = linearizer_->GateToRegion(gate);
130 }
131 break;
132 }
133 case OpCode::LOOP_BACK:
134 case OpCode::IF_BRANCH:
135 case OpCode::SWITCH_BRANCH:
136 case OpCode::RETURN:
137 case OpCode::RETURN_VOID:
138 case OpCode::TYPED_CONDITION_JUMP:
139 endStateList_.emplace_back(gate);
140 break;
141 case OpCode::JS_BYTECODE:
142 if (IsStateSplit(gate)) {
143 endStateList_.emplace_back(gate);
144 }
145 break;
146 default: {
147 if (linearizer_->onlyBB_) {
148 auto &info = linearizer_->GetGateInfo(gate);
149 info.region = currentRegion_;
150 linearizer_->BindGate(gate, currentRegion_);
151 }
152 break;
153 }
154 }
155 }
156 }
157
IsStateSplit(GateRef gate)158 bool IsStateSplit(GateRef gate)
159 {
160 size_t stateOut = 0;
161 auto uses = acc_.Uses(gate);
162 for (auto it = uses.begin(); it != uses.end(); it++) {
163 if (acc_.IsStateIn(it)) {
164 auto op = acc_.GetOpCode(*it);
165 switch (op) {
166 case OpCode::IF_TRUE:
167 case OpCode::IF_FALSE:
168 case OpCode::IF_EXCEPTION:
169 case OpCode::IF_SUCCESS:
170 stateOut++;
171 break;
172 default:
173 break;
174 }
175 }
176 }
177 return stateOut > 1; // 1: depend out
178 }
179
180 private:
181 GraphLinearizer* linearizer_;
182 ChunkDeque<GateRef> pendingList_;
183 ChunkVector<GateRef> endStateList_;
184 GateAccessor acc_;
185 GateRegion* currentRegion_ {nullptr};
186 bool scheduleLIR_;
187 };
188
189 class ImmediateDominatorsGenerator {
190 public:
ImmediateDominatorsGenerator(GraphLinearizer * linearizer,Chunk * chunk,size_t size)191 explicit ImmediateDominatorsGenerator(GraphLinearizer *linearizer, Chunk* chunk, size_t size)
192 : linearizer_(linearizer), pendingList_(chunk),
193 dfsList_(chunk), dfsTimestamp_(size, chunk), dfsFatherIdx_(size, chunk),
194 bbDfsTimestampToIdx_(size, chunk), semiDom_(size, chunk), immDom_(size, chunk),
195 minIdx_(size, chunk), parentIdx_(size, chunk), semiDomTree_(chunk) {}
196
Run()197 void Run()
198 {
199 BuildDfsFather();
200 BuildDomTree();
201 BuildImmediateDominator();
202 BuildImmediateDominatorDepth();
203 }
204
BuildDfsFather()205 void BuildDfsFather()
206 {
207 size_t timestamp = 0;
208 auto entry = linearizer_->regionList_.front();
209 linearizer_->circuit_->AdvanceTime();
210 entry->SetVisited(linearizer_->acc_);
211 ASSERT(pendingList_.empty());
212 pendingList_.emplace_back(entry);
213 while (!pendingList_.empty()) {
214 auto curRegion = pendingList_.back();
215 pendingList_.pop_back();
216 dfsList_.emplace_back(curRegion->id_);
217 dfsTimestamp_[curRegion->id_] = timestamp++;
218 for (auto succ : curRegion->succs_) {
219 if (!succ->IsVisited(linearizer_->acc_)) {
220 succ->SetVisited(linearizer_->acc_);
221 pendingList_.emplace_back(succ);
222 dfsFatherIdx_[succ->id_] = dfsTimestamp_[curRegion->id_];
223 }
224 }
225 }
226 for (size_t idx = 0; idx < dfsList_.size(); idx++) {
227 bbDfsTimestampToIdx_[dfsList_[idx]] = idx;
228 }
229 ASSERT(timestamp == linearizer_->regionList_.size());
230 }
231
UnionFind(size_t idx)232 size_t UnionFind(size_t idx)
233 {
234 std::stack<size_t> allIdxs;
235 allIdxs.emplace(idx);
236 size_t pIdx = parentIdx_[idx];
237 while (pIdx != allIdxs.top()) {
238 allIdxs.emplace(pIdx);
239 pIdx = parentIdx_[pIdx];
240 }
241 size_t unionFindSetRoot = pIdx;
242 while (!allIdxs.empty()) {
243 if (semiDom_[minIdx_[allIdxs.top()]] > semiDom_[minIdx_[pIdx]]) {
244 minIdx_[allIdxs.top()] = minIdx_[pIdx];
245 }
246 parentIdx_[allIdxs.top()] = unionFindSetRoot;
247 pIdx = allIdxs.top();
248 allIdxs.pop();
249 }
250 return unionFindSetRoot;
251 }
252
Merge(size_t fatherIdx,size_t sonIdx)253 void Merge(size_t fatherIdx, size_t sonIdx)
254 {
255 size_t parentFatherIdx = UnionFind(fatherIdx);
256 size_t parentSonIdx = UnionFind(sonIdx);
257 parentIdx_[parentSonIdx] = parentFatherIdx;
258 }
259
BuildDomTree()260 void BuildDomTree()
261 {
262 auto ®ionList = linearizer_->regionList_;
263 for (size_t i = 0; i < dfsList_.size(); i++) {
264 ChunkDeque<size_t> sonList(linearizer_->chunk_);
265 semiDomTree_.emplace_back(std::move(sonList));
266 }
267 std::iota(parentIdx_.begin(), parentIdx_.end(), 0);
268 std::iota(semiDom_.begin(), semiDom_.end(), 0);
269 semiDom_[0] = semiDom_.size();
270
271 ASSERT(dfsList_.size() > 0);
272 for (size_t idx = dfsList_.size() - 1; idx >= 1; idx--) {
273 for (const auto &preRegion : regionList[dfsList_[idx]]->preds_) {
274 size_t preRegionIdx = bbDfsTimestampToIdx_[preRegion->id_];
275 if (bbDfsTimestampToIdx_[preRegion->id_] < idx) {
276 semiDom_[idx] = std::min(semiDom_[idx], preRegionIdx);
277 } else {
278 UnionFind(preRegionIdx);
279 semiDom_[idx] = std::min(semiDom_[idx], semiDom_[minIdx_[preRegionIdx]]);
280 }
281 }
282 for (const auto &succDomIdx : semiDomTree_[idx]) {
283 UnionFind(succDomIdx);
284 if (idx == semiDom_[minIdx_[succDomIdx]]) {
285 immDom_[succDomIdx] = idx;
286 } else {
287 immDom_[succDomIdx] = minIdx_[succDomIdx];
288 }
289 }
290 minIdx_[idx] = idx;
291 Merge(dfsFatherIdx_[dfsList_[idx]], idx);
292 semiDomTree_[semiDom_[idx]].emplace_back(idx);
293 }
294 }
295
BuildImmediateDominator()296 void BuildImmediateDominator()
297 {
298 for (size_t idx = 1; idx < dfsList_.size(); idx++) {
299 if (immDom_[idx] != semiDom_[idx]) {
300 immDom_[idx] = immDom_[immDom_[idx]];
301 }
302 }
303 auto entry = linearizer_->regionList_.front();
304 entry->iDominator_ = entry;
305 entry->depth_ = 0;
306 auto ®ionList = linearizer_->regionList_;
307 for (size_t i = 1; i < immDom_.size(); i++) {
308 auto index = dfsList_[i];
309 auto dominatedRegion = regionList[index];
310 auto domIndex = dfsList_[immDom_[i]];
311 auto immDomRegion = regionList[domIndex];
312 immDomRegion->depth_ = static_cast<int32_t>(immDom_[i]);
313 dominatedRegion->iDominator_ = immDomRegion;
314 immDomRegion->dominatedRegions_.emplace_back(dominatedRegion);
315 }
316 }
317
BuildImmediateDominatorDepth()318 void BuildImmediateDominatorDepth()
319 {
320 auto entry = linearizer_->regionList_.front();
321 entry->depth_ = 0;
322
323 ASSERT(pendingList_.empty());
324 pendingList_.emplace_back(entry);
325 while (!pendingList_.empty()) {
326 auto curRegion = pendingList_.back();
327 pendingList_.pop_back();
328
329 for (auto succ : curRegion->dominatedRegions_) {
330 ASSERT(succ->iDominator_->depth_ != GateRegion::INVALID_DEPTH);
331 succ->depth_ = succ->iDominator_->depth_ + 1;
332 pendingList_.emplace_back(succ);
333 }
334 }
335 }
336
337 private:
338 GraphLinearizer* linearizer_;
339 ChunkDeque<GateRegion*> pendingList_;
340 ChunkVector<size_t> dfsList_;
341 ChunkVector<size_t> dfsTimestamp_;
342 ChunkVector<size_t> dfsFatherIdx_;
343 ChunkVector<size_t> bbDfsTimestampToIdx_;
344 ChunkVector<size_t> semiDom_;
345 ChunkVector<size_t> immDom_;
346 ChunkVector<size_t> minIdx_;
347 ChunkVector<size_t> parentIdx_;
348 ChunkVector<ChunkDeque<size_t>> semiDomTree_;
349 };
350
351 class LoopInfoBuilder {
352 public:
LoopInfoBuilder(GraphLinearizer * linearizer,Chunk * chunk)353 explicit LoopInfoBuilder(GraphLinearizer *linearizer, Chunk* chunk)
354 : linearizer_(linearizer), pendingList_(chunk),
355 loopbacks_(chunk), chunk_(chunk),
356 dfsStack_(chunk), acc_(linearizer->circuit_) {}
357
Run()358 void Run()
359 {
360 ComputeLoopNumber();
361 ComputeLoopInfo();
362 ComputeLoopTree();
363 if (linearizer_->IsLogEnabled()) {
364 for (size_t i = 0; i < numLoops_; i++) {
365 auto& loopInfo = linearizer_->loops_[i];
366 PrintLoop(loopInfo);
367 }
368 }
369 }
370
PrintLoop(GraphLinearizer::LoopInfo & loopInfo)371 void PrintLoop(GraphLinearizer::LoopInfo& loopInfo)
372 {
373 auto size = linearizer_->regionList_.size();
374 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo Start ---------------------------------";
375 LOG_COMPILER(INFO) << "Head: " << acc_.GetId(loopInfo.loopHead->state_);
376 LOG_COMPILER(INFO) << "loopNumber: " << loopInfo.loopHead->loopNumber_;
377 LOG_COMPILER(INFO) << "Body: [";
378 for (size_t i = 0; i < size; i++) {
379 if (loopInfo.loopBodys->TestBit(i)) {
380 auto current = linearizer_->regionList_.at(i)->state_;
381 LOG_COMPILER(INFO) << acc_.GetId(current) << ", ";
382 }
383 }
384 LOG_COMPILER(INFO) << "]";
385 LOG_COMPILER(INFO) << "Exit: [";
386 if (loopInfo.loopExits != nullptr) {
387 for (auto region : *loopInfo.loopExits) {
388 auto current = region->state_;
389 LOG_COMPILER(INFO) << acc_.GetId(current) << ", ";
390 }
391 }
392 LOG_COMPILER(INFO) << "]";
393 LOG_COMPILER(INFO) << "--------------------------------- LoopInfo End ---------------------------------";
394 }
395
ComputeLoopInfo()396 void ComputeLoopInfo()
397 {
398 linearizer_->loops_.clear();
399 auto size = linearizer_->regionList_.size();
400 linearizer_->loops_.resize(numLoops_, GraphLinearizer::LoopInfo());
401
402 for (auto curState : loopbacks_) {
403 GateRegion* curRegion = curState.region;
404 GateRegion* loopHead = curRegion->succs_[curState.index];
405 auto loopNumber = loopHead->GetLoopNumber();
406 auto& loopInfo = linearizer_->loops_[loopNumber];
407
408 if (loopInfo.loopHead == nullptr) {
409 loopInfo.loopHead = loopHead;
410 loopInfo.loopBodys = chunk_->New<BitSet>(chunk_, size);
411 loopInfo.loopIndex = static_cast<size_t>(loopNumber);
412 loopInfo.loopHead->loopIndex_ = static_cast<int32_t>(loopInfo.loopIndex);
413 }
414 if (curRegion != loopHead) {
415 loopInfo.loopBodys->SetBit(curRegion->GetId());
416 pendingList_.emplace_back(curRegion);
417 }
418 PropagateLoopBody(loopInfo);
419 }
420 }
421
PropagateLoopBody(GraphLinearizer::LoopInfo & loopInfo)422 void PropagateLoopBody(GraphLinearizer::LoopInfo& loopInfo)
423 {
424 while (!pendingList_.empty()) {
425 auto curRegion = pendingList_.back();
426 pendingList_.pop_back();
427 for (auto pred : curRegion->preds_) {
428 if (pred != loopInfo.loopHead) {
429 if (!loopInfo.loopBodys->TestBit(pred->GetId())) {
430 loopInfo.loopBodys->SetBit(pred->GetId());
431 pendingList_.emplace_back(pred);
432 }
433 }
434 }
435 }
436 }
437
ComputeLoopNumber()438 void ComputeLoopNumber()
439 {
440 auto size = linearizer_->regionList_.size();
441 dfsStack_.resize(size, DFSState(nullptr, 0));
442 linearizer_->circuit_->AdvanceTime();
443
444 auto entry = linearizer_->regionList_.front();
445 auto currentDepth = Push(entry, 0);
446 while (currentDepth > 0) {
447 auto& curState = dfsStack_[currentDepth - 1]; // -1: for current
448 auto curRegion = curState.region;
449 auto index = curState.index;
450
451 if (index == curRegion->succs_.size()) {
452 currentDepth--;
453 curRegion->SetFinished(acc_);
454 } else {
455 GateRegion* succ = curRegion->succs_[index];
456 curState.index = ++index;
457 if (succ->IsFinished(acc_)) {
458 continue;
459 }
460 if (succ->IsUnvisited(acc_)) {
461 currentDepth = Push(succ, currentDepth);
462 } else {
463 ASSERT(succ->IsVisited(acc_) && index > 0);
464 loopbacks_.emplace_back(DFSState(curRegion, index - 1)); // -1: for prev
465 if (!succ->HasLoopNumber()) {
466 succ->SetLoopNumber(numLoops_++);
467 }
468 }
469 }
470 }
471 }
472
ComputeLoopTree()473 void ComputeLoopTree()
474 {
475 linearizer_->circuit_->AdvanceTime();
476 auto entry = linearizer_->regionList_.front();
477 GraphLinearizer::LoopInfo *loopInfo = nullptr;
478 auto currentDepth = Push(entry, 0);
479 while (currentDepth > 0) {
480 auto &curState = dfsStack_[currentDepth - 1]; // -1: for current
481 auto curRegion = curState.region;
482 auto index = curState.index;
483 GateRegion* succ = nullptr;
484 if (index >= curRegion->succs_.size()) {
485 if (curRegion->HasLoopNumber()) {
486 if (curRegion->IsVisited(acc_)) {
487 ASSERT(loopInfo != nullptr && loopInfo->loopHead == curRegion);
488 loopInfo = loopInfo->outer;
489 curRegion->SetFinished(acc_);
490 }
491 auto loopExitIndex = index - curRegion->succs_.size();
492 auto& currentInfo = linearizer_->loops_[curRegion->GetLoopNumber()];
493 if (currentInfo.loopExits != nullptr && loopExitIndex < currentInfo.loopExits->size()) {
494 succ = currentInfo.loopExits->at(loopExitIndex);
495 curState.index++;
496 }
497 }
498 } else {
499 succ = curRegion->succs_[curState.index++]; // goto next
500 }
501 if (succ != nullptr) {
502 if (!succ->IsUnvisited(acc_)) {
503 continue;
504 }
505 if (loopInfo != nullptr && !loopInfo->loopBodys->TestBit(succ->GetId())) {
506 AddLoopExit(succ, loopInfo);
507 } else if (succ->IsUnvisited(acc_)) {
508 currentDepth = Push(succ, currentDepth);
509 loopInfo = EnterInnerLoop(succ, loopInfo);
510 }
511 } else {
512 if (!curRegion->HasLoopNumber()) {
513 curRegion->SetFinished(acc_);
514 }
515 currentDepth--;
516 }
517 }
518 }
519
AddLoopExit(GateRegion * succ,GraphLinearizer::LoopInfo * loopInfo)520 void AddLoopExit(GateRegion* succ, GraphLinearizer::LoopInfo *loopInfo)
521 {
522 if (loopInfo->loopExits == nullptr) {
523 loopInfo->loopExits = chunk_->New<ChunkVector<GateRegion*>>(chunk_);
524 }
525 loopInfo->loopExits->emplace_back(succ);
526 }
527
EnterInnerLoop(GateRegion * succ,GraphLinearizer::LoopInfo * loopInfo)528 GraphLinearizer::LoopInfo *EnterInnerLoop(GateRegion* succ, GraphLinearizer::LoopInfo *loopInfo)
529 {
530 // enter inner loop
531 if (succ->HasLoopNumber()) {
532 ASSERT_PRINT(succ->loopIndex_ != GateRegion::INVALID_INDEX, "GateRegion's index should be assigned");
533 auto& innerLoop = linearizer_->loops_[succ->GetLoopNumber()];
534 innerLoop.outer = loopInfo;
535 if (loopInfo != nullptr) {
536 innerLoop.loopDepth = loopInfo->loopDepth + 1;
537 } else {
538 innerLoop.loopDepth = 1;
539 }
540 succ->loopDepth_ = static_cast<int32_t>(innerLoop.loopDepth);
541 loopInfo = &innerLoop;
542 } else if (loopInfo != nullptr) {
543 succ->loopIndex_ = static_cast<int32_t>(loopInfo->loopIndex);
544 succ->loopDepth_ = static_cast<int32_t>(loopInfo->loopDepth);
545 }
546 return loopInfo;
547 }
548
Push(GateRegion * region,size_t depth)549 size_t Push(GateRegion *region, size_t depth)
550 {
551 if (region->IsUnvisited(acc_)) {
552 dfsStack_[depth].region = region;
553 dfsStack_[depth].index = 0;
554 region->SetVisited(acc_);
555 return depth + 1;
556 }
557 return depth;
558 }
559
560 private:
561 struct DFSState {
DFSStatepanda::ecmascript::kungfu::LoopInfoBuilder::DFSState562 DFSState(GateRegion *region, size_t index)
563 : region(region), index(index) {}
564
565 GateRegion *region;
566 size_t index;
567 };
568 GraphLinearizer* linearizer_ {nullptr};
569 ChunkDeque<GateRegion*> pendingList_;
570 ChunkVector<DFSState> loopbacks_;
571 Chunk* chunk_ {nullptr};
572 ChunkVector<DFSState> dfsStack_;
573 GateAccessor acc_;
574 size_t numLoops_{0};
575 };
576
577 class GateScheduler {
578 public:
GateScheduler(GraphLinearizer * linearizer)579 explicit GateScheduler(GraphLinearizer *linearizer)
580 : linearizer_(linearizer), fixedGateList_(linearizer->chunk_),
581 pendingList_(linearizer->chunk_), acc_(linearizer->circuit_),
582 scheduleUpperBound_(linearizer_->scheduleUpperBound_) {}
583
InitializeFixedGate()584 void InitializeFixedGate()
585 {
586 auto ®ionRoots = linearizer_->regionRootList_;
587 auto size = regionRoots.size();
588 for (size_t i = 0; i < size; i++) {
589 auto fixedGate = regionRoots[i];
590 auto region = linearizer_->GateToRegion(fixedGate);
591 // fixed Gate's output
592 auto uses = acc_.Uses(fixedGate);
593 for (auto it = uses.begin(); it != uses.end(); it++) {
594 GateRef succGate = *it;
595 if (acc_.IsStateIn(it) && acc_.IsSelector(succGate)) {
596 linearizer_->AddFixedGateToRegion(succGate, region);
597 fixedGateList_.emplace_back(succGate);
598 }
599 }
600 }
601 }
602
Prepare()603 void Prepare()
604 {
605 InitializeFixedGate();
606 auto ®ionRoots = linearizer_->regionRootList_;
607 ASSERT(pendingList_.empty());
608 for (const auto rootGate : regionRoots) {
609 pendingList_.emplace_back(rootGate);
610 }
611 while (!pendingList_.empty()) {
612 auto curGate = pendingList_.back();
613 pendingList_.pop_back();
614 auto numIns = acc_.GetNumIns(curGate);
615 for (size_t i = 0; i < numIns; i++) {
616 VisitPreparedGate(Edge(curGate, i));
617 }
618 }
619 }
620
ScheduleUpperBound()621 void ScheduleUpperBound()
622 {
623 if (!scheduleUpperBound_) {
624 return;
625 }
626 auto ®ionRoots = linearizer_->regionRootList_;
627 ASSERT(pendingList_.empty());
628 for (const auto rootGate : regionRoots) {
629 pendingList_.emplace_back(rootGate);
630 }
631 while (!pendingList_.empty()) {
632 auto curGate = pendingList_.back();
633 pendingList_.pop_back();
634 auto uses = acc_.Uses(curGate);
635 for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
636 VisitUpperBoundGate(useIt.GetEdge());
637 }
638 }
639 }
640
VisitUpperBoundGate(Edge edge)641 void VisitUpperBoundGate(Edge edge)
642 {
643 GateRef succGate = edge.GetGate();
644 auto& succInfo = linearizer_->GetGateInfo(succGate);
645 if (!succInfo.IsSchedulable()) {
646 return;
647 }
648 ASSERT(succInfo.upperBound != nullptr);
649 auto curGate = acc_.GetIn(succGate, edge.GetIndex());
650 auto curUpperBound = linearizer_->GateToUpperBound(curGate);
651 ASSERT(IsInSameDominatorChain(curUpperBound, succInfo.upperBound));
652 if (curUpperBound->depth_ > succInfo.upperBound->depth_) {
653 succInfo.upperBound = curUpperBound;
654 pendingList_.emplace_back(succGate);
655 }
656 }
657
ScheduleFloatingGate()658 void ScheduleFloatingGate()
659 {
660 auto ®ionRoots = linearizer_->regionRootList_;
661 for (const auto rootGate : regionRoots) {
662 auto ins = acc_.Ins(rootGate);
663 for (auto it = ins.begin(); it != ins.end(); it++) {
664 pendingList_.emplace_back(*it);
665 while (!pendingList_.empty()) {
666 auto curGate = pendingList_.back();
667 pendingList_.pop_back();
668 ComputeLowerBoundAndScheduleGate(curGate);
669 }
670 }
671 }
672 }
673
VisitPreparedGate(Edge edge)674 void VisitPreparedGate(Edge edge)
675 {
676 auto curGate = edge.GetGate();
677 auto prevGate = acc_.GetIn(curGate, edge.GetIndex());
678 if (acc_.IsProlog(prevGate) || acc_.IsRoot(prevGate)) {
679 return;
680 }
681 auto& prevInfo = linearizer_->GetGateInfo(prevGate);
682 if (prevInfo.IsNone()) {
683 if (scheduleUpperBound_) {
684 prevInfo.upperBound = linearizer_->GetEntryRegion();
685 }
686 ASSERT(prevInfo.schedulableUseCount == 0);
687 prevInfo.state_ = GraphLinearizer::ScheduleState::SCHEDELABLE;
688 pendingList_.emplace_back(prevGate);
689 }
690 auto& curInfo = linearizer_->GetGateInfo(curGate);
691 if (prevInfo.IsSchedulable() && curInfo.IsSchedulable()) {
692 prevInfo.schedulableUseCount++;
693 }
694 }
695
ComputeLowerBoundAndScheduleGate(GateRef curGate)696 void ComputeLowerBoundAndScheduleGate(GateRef curGate)
697 {
698 auto& curInfo = linearizer_->GetGateInfo(curGate);
699 if (!curInfo.IsSchedulable() ||
700 (curInfo.schedulableUseCount != 0) || (curInfo.region != nullptr)) {
701 return;
702 }
703 auto region = GetCommonDominatorOfAllUses(curGate);
704 if (scheduleUpperBound_) {
705 ASSERT(curInfo.upperBound != nullptr);
706 ASSERT(linearizer_->GetCommonDominator(region, curInfo.upperBound) == curInfo.upperBound);
707 auto uppermost = curInfo.upperBound->depth_;
708 auto upperRegion = GetUpperBoundRegion(region);
709 while (upperRegion != nullptr && upperRegion->depth_ >= uppermost) {
710 region = upperRegion;
711 upperRegion = GetUpperBoundRegion(region);
712 }
713 }
714 if (acc_.GetOpCode(curGate) == OpCode::FINISH_ALLOCATE) {
715 ScheduleAllocRegion(curGate, region);
716 } else {
717 ScheduleGate(curGate, region);
718 }
719 }
720
GetUpperBoundRegion(GateRegion * region)721 GateRegion* GetUpperBoundRegion(GateRegion* region)
722 {
723 if (region->IsLoopHead()) {
724 return region->iDominator_;
725 }
726 auto loopInfo = linearizer_->GetLoopInfo(region);
727 if (loopInfo != nullptr) {
728 if (!CheckRegionDomLoopExist(region, loopInfo)) {
729 return nullptr;
730 }
731 return loopInfo->loopHead->iDominator_;
732 }
733 return nullptr;
734 }
735
ScheduleAllocRegion(GateRef gate,GateRegion * region)736 void ScheduleAllocRegion(GateRef gate, GateRegion* region)
737 {
738 ASSERT(acc_.GetOpCode(gate) == OpCode::FINISH_ALLOCATE);
739 // 1. schedule FINISH_ALLOCATE first
740 ScheduleGate(gate, region);
741 GateRef curGate = acc_.GetDep(gate);
742 [[maybe_unused]]GateRef output = acc_.GetValueIn(gate, 0);
743 // 2. schedule all gates from end to start
744 while (acc_.GetOpCode(curGate) != OpCode::START_ALLOCATE) {
745 [[maybe_unused]] auto& curInfo = linearizer_->GetGateInfo(curGate);
746 ASSERT(curInfo.IsSchedulable());
747 ASSERT(curInfo.schedulableUseCount == 0);
748 ASSERT(curInfo.region == nullptr);
749 ASSERT(acc_.GetStateCount(curGate) == 0);
750 ASSERT(acc_.GetDependCount(curGate) == 1);
751 ASSERT(acc_.GetValueUsesCount(curGate) == 0 || curGate == output);
752
753 ScheduleGate(curGate, region);
754 curGate = acc_.GetDep(curGate);
755 }
756 // 3. schedule START_ALLOCATE
757 ASSERT(linearizer_->GetGateInfo(curGate).schedulableUseCount == 0);
758 ScheduleGate(curGate, region);
759 }
760
CheckRegionDomLoopExist(GateRegion * region,GraphLinearizer::LoopInfo * loopInfo)761 bool CheckRegionDomLoopExist(GateRegion* region, GraphLinearizer::LoopInfo* loopInfo)
762 {
763 if (loopInfo->loopExits == nullptr) {
764 return true;
765 }
766 for (auto exitRegion : *loopInfo->loopExits) {
767 if (linearizer_->GetCommonDominator(region, exitRegion) != region) {
768 return false;
769 }
770 }
771 return true;
772 }
773
ScheduleGate(GateRef gate,GateRegion * region)774 void ScheduleGate(GateRef gate, GateRegion* region)
775 {
776 auto ins = acc_.Ins(gate);
777 for (auto it = ins.begin(); it != ins.end(); it++) {
778 auto inputGate = *it;
779 auto& inputInfo = linearizer_->GetGateInfo(inputGate);
780 if (!inputInfo.IsSchedulable()) {
781 continue;
782 }
783 inputInfo.schedulableUseCount--;
784 if (inputInfo.schedulableUseCount == 0) {
785 pendingList_.emplace_back(inputGate);
786 }
787 }
788 ASSERT(!linearizer_->IsScheduled(gate));
789 linearizer_->BindGate(gate, region);
790 }
791
GetCommonDominatorOfAllUses(GateRef curGate)792 GateRegion* GetCommonDominatorOfAllUses(GateRef curGate)
793 {
794 GateRegion* region = nullptr;
795 auto uses = acc_.Uses(curGate);
796 for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
797 GateRef useGate = *useIt;
798 auto& useInfo = linearizer_->GetGateInfo(useGate);
799 if (useInfo.IsNone()) {
800 continue;
801 }
802 GateRegion* useRegion = useInfo.region;
803 if (useInfo.IsSelector()) {
804 GateRef state = acc_.GetState(useGate);
805 ASSERT(acc_.IsCFGMerge(state) && useIt.GetIndex() > 0);
806 useGate = acc_.GetIn(state, useIt.GetIndex() - 1); // -1: for state
807 useRegion = linearizer_->FindPredRegion(useGate);
808 } else if (acc_.IsCFGMerge(useGate)) {
809 useGate = acc_.GetIn(useGate, useIt.GetIndex());
810 useRegion = linearizer_->FindPredRegion(useGate);
811 }
812
813 if (region == nullptr) {
814 region = useRegion;
815 } else {
816 ASSERT(useRegion != nullptr);
817 region = linearizer_->GetCommonDominator(region, useRegion);
818 }
819 }
820 return region;
821 }
822
IsInSameDominatorChain(GateRegion * left,GateRegion * right) const823 bool IsInSameDominatorChain(GateRegion* left, GateRegion* right) const
824 {
825 auto dom = linearizer_->GetCommonDominator(left, right);
826 return left == dom || right == dom;
827 }
828
ScheduleFixedGate()829 void ScheduleFixedGate()
830 {
831 for (auto gate : fixedGateList_) {
832 GateRegion* region = linearizer_->GateToRegion(gate);
833 linearizer_->BindGate(gate, region);
834 }
835 #ifndef NDEBUG
836 Verify();
837 #endif
838 }
839
Verify()840 void Verify()
841 {
842 std::vector<GateRef> gateList;
843 linearizer_->circuit_->GetAllGates(gateList);
844 for (const auto &gate : gateList) {
845 auto& gateInfo = linearizer_->GetGateInfo(gate);
846 if (gateInfo.IsSchedulable()) {
847 ASSERT(linearizer_->IsScheduled(gate));
848 }
849 ASSERT(gateInfo.schedulableUseCount == 0);
850 }
851 }
852
853 private:
854 GraphLinearizer* linearizer_ {nullptr};
855 ChunkVector<GateRef> fixedGateList_;
856 ChunkDeque<GateRef> pendingList_;
857 GateAccessor acc_;
858 bool scheduleUpperBound_{false};
859 };
860
LinearizeGraph()861 void GraphLinearizer::LinearizeGraph()
862 {
863 gateIdToGateInfo_.resize(circuit_->GetMaxGateId() + 1, GateInfo{nullptr}); // 1: max + 1 = size
864 CFGBuilder builder(this);
865 builder.Run();
866 ImmediateDominatorsGenerator generator(this, chunk_, regionList_.size());
867 generator.Run();
868 if (IsEnableLoopInvariantCodeMotion() && loopNumber_ > 0) {
869 scheduleUpperBound_ = true;
870 LoopInfoBuilder loopInfoBuilder(this, chunk_);
871 loopInfoBuilder.Run();
872 }
873 if (!onlyBB_) {
874 GateScheduler scheduler(this);
875 scheduler.Prepare();
876 scheduler.ScheduleUpperBound();
877 scheduler.ScheduleFloatingGate();
878 scheduler.ScheduleFixedGate();
879 }
880 }
881
CreateGateRegion(GateRef gate)882 void GraphLinearizer::CreateGateRegion(GateRef gate)
883 {
884 ASSERT(GateToRegion(gate) == nullptr);
885 auto region = new (chunk_) GateRegion(chunk_);
886 region->id_ = regionList_.size();
887 regionList_.emplace_back(region);
888 if (acc_.GetOpCode(gate) == OpCode::LOOP_BEGIN) {
889 loopNumber_++;
890 region->stateKind_ = GateRegion::StateKind::LOOP_HEAD;
891 }
892 AddRootGateToRegion(gate, region);
893 }
894
LinearizeRegions(ControlFlowGraph & result)895 void GraphLinearizer::LinearizeRegions(ControlFlowGraph &result)
896 {
897 size_t liveNum = OptimizeCFG();
898
899 ASSERT(result.size() == 0);
900 result.resize(liveNum);
901 auto uses = acc_.Uses(acc_.GetArgRoot());
902 for (auto useIt = uses.begin(); useIt != uses.end(); useIt++) {
903 regionList_.front()->gateList_.emplace_back(*useIt);
904 }
905
906 size_t i = 0;
907 for (size_t id = 0; id < regionList_.size(); id++) {
908 GateRegion* r = regionList_[id];
909 if (r->IsDead()) {
910 continue;
911 }
912 auto& gates = r->GetGates();
913 auto& bb = result[i];
914 bb.insert(bb.end(), gates.begin(), gates.end());
915 i++;
916 }
917 }
918
IsSimple(GateAccessor * acc) const919 bool GateRegion::IsSimple(GateAccessor *acc) const
920 {
921 for (auto g : gateList_) {
922 bool isSimple = acc->IsSimpleState(g);
923 bool complexOut = HasComplexOuts();
924 if (!isSimple || complexOut) {
925 return false;
926 }
927 }
928 return true;
929 }
930
OptimizeControls(GateRegion * region)931 size_t GraphLinearizer::OptimizeControls(GateRegion *region)
932 {
933 size_t deads = 0;
934 GateRegion* target = region;
935 do {
936 GateRegion* succ = target->GetSimpleSuccRegion();
937 if (succ == nullptr) {
938 break;
939 }
940 MoveAndClear(target, succ);
941 target = succ;
942 deads++;
943 } while (target->IsSimple(&acc_));
944 return deads;
945 }
946
MoveAndClear(GateRegion * from,GateRegion * to)947 void GraphLinearizer::MoveAndClear(GateRegion* from, GateRegion* to)
948 {
949 ASSERT(from != to);
950 ASSERT(to->GetPreds().size() == 1);
951 for (GateRef g: from->GetGates()) {
952 ASSERT(acc_.IsSimpleState(g));
953 OpCode op = acc_.GetOpCode(g);
954 switch (op) {
955 case OpCode::IF_TRUE:
956 case OpCode::IF_FALSE:
957 case OpCode::SWITCH_CASE:
958 case OpCode::DEFAULT_CASE:
959 case OpCode::LOOP_BACK:
960 case OpCode::ORDINARY_BLOCK:
961 case OpCode::MERGE:
962 case OpCode::VALUE_SELECTOR:
963 to->AddGate(g);
964 break;
965 default:
966 break;
967 }
968 }
969 for (auto p : from->GetPreds()) {
970 p->ReplaceSucc(from, to);
971 }
972 to->RemovePred(from);
973 from->SetDead();
974 #ifndef NDEBUG
975 from->Clear();
976 #endif
977 }
978
OptimizeCFG()979 size_t GraphLinearizer::OptimizeCFG()
980 {
981 size_t liveNum = regionList_.size();
982 for (size_t i = 0; i < regionList_.size(); i++) {
983 GateRegion* src = regionList_[i];
984 if (!src->IsDead() && src->IsSimple(&acc_)) {
985 size_t dead = OptimizeControls(src);
986 ASSERT(liveNum >= dead);
987 liveNum -= dead;
988 }
989 }
990 return liveNum;
991 }
992
FindPredRegion(GateRef input)993 GateRegion* GraphLinearizer::FindPredRegion(GateRef input)
994 {
995 GateRegion* predRegion = GateToRegion(input);
996 while (predRegion == nullptr) {
997 ASSERT(acc_.GetStateCount(input) == 1); // 1: fall through block
998 input = acc_.GetState(input);
999 predRegion = GateToRegion(input);
1000 }
1001 ASSERT(predRegion != nullptr);
1002 return predRegion;
1003 }
1004
GetCommonDominator(GateRegion * left,GateRegion * right) const1005 GateRegion* GraphLinearizer::GetCommonDominator(GateRegion* left, GateRegion* right) const
1006 {
1007 while (left != right) {
1008 if (left->depth_ < right->depth_) {
1009 right = right->iDominator_;
1010 } else {
1011 left = left->iDominator_;
1012 }
1013 }
1014 return left;
1015 }
1016
PrintGraph(const char * title)1017 void GraphLinearizer::PrintGraph(const char* title)
1018 {
1019 LOG_COMPILER(INFO) << "======================== " << title << " ========================";
1020 int bbIdx = 0;
1021 for (size_t i = 0; i < regionList_.size(); i++) {
1022 auto bb = regionList_[i];
1023 if (bb->IsDead()) {
1024 continue;
1025 }
1026 auto front = bb->gateList_.front();
1027 auto opcode = acc_.GetOpCode(front);
1028 size_t loopHeadId = 0;
1029 auto loopInfo = GetLoopInfo(bb);
1030 if (loopInfo != nullptr) {
1031 loopHeadId = loopInfo->loopHead->id_;
1032 }
1033 LOG_COMPILER(INFO) << "B" << bb->id_ << "_LB" << bbIdx << ": " << "depth: [" << bb->depth_ << "] "
1034 << opcode << "(" << acc_.GetId(front) << ") "
1035 << "IDom B" << bb->iDominator_->id_ << " loop Header: " << loopHeadId;
1036 std::string log("\tPreds: ");
1037 for (size_t k = 0; k < bb->preds_.size(); ++k) {
1038 log += std::to_string(bb->preds_[k]->id_) + ", ";
1039 }
1040 LOG_COMPILER(INFO) << log;
1041 std::string log1("\tSucces: ");
1042 for (size_t j = 0; j < bb->succs_.size(); j++) {
1043 log1 += std::to_string(bb->succs_[j]->id_) + ", ";
1044 }
1045 LOG_COMPILER(INFO) << log1;
1046 for (auto it = bb->gateList_.crbegin(); it != bb->gateList_.crend(); it++) {
1047 acc_.Print(*it);
1048 }
1049 LOG_COMPILER(INFO) << "";
1050 bbIdx++;
1051 }
1052 }
1053 } // namespace panda::ecmascript::kungfu
1054