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