1 /*
2  * Copyright (c) 2022 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 #include "ecmascript/compiler/frame_states.h"
16 
17 #include <cstddef>
18 
19 #include "ecmascript/compiler/bytecode_circuit_builder.h"
20 
21 namespace panda::ecmascript::kungfu {
FrameStateBuilder(BytecodeCircuitBuilder *builder, Circuit *circuit, const MethodLiteral *literal)22 FrameStateBuilder::FrameStateBuilder(BytecodeCircuitBuilder *builder,
23     Circuit *circuit, const MethodLiteral *literal)
24     : bcBuilder_(builder),
25       pgoTypeRecorder_(builder->GetPGOTypeRecorder()),
26       numVregs_(literal->GetNumberVRegs() + FIXED_ARGS),
27       accumulatorIndex_(literal->GetNumberVRegs() + 1), // 1: acc
28       envIndex_(literal->GetNumberVRegs()),
29       circuit_(circuit),
30       acc_(circuit),
31       bcEndStateLiveouts_(circuit->chunk()),
32       bbBeginStateLiveouts_(circuit->chunk()),
33       bbFrameContext_(circuit->chunk()),
34       loops_(circuit->chunk()),
35       rpoList_(circuit->chunk()),
36       postOrderList_(circuit->chunk())
37 {
38 }
39 
~FrameStateBuilder()40 FrameStateBuilder::~FrameStateBuilder()
41 {
42     liveOutResult_ = nullptr;
43     bcEndStateLiveouts_.clear();
44     bbBeginStateLiveouts_.clear();
45     bbFrameContext_.clear();
46     bcBuilder_ = nullptr;
47 }
48 
BuildPostOrderList(size_t size)49 void FrameStateBuilder::BuildPostOrderList(size_t size)
50 {
51     postOrderList_.clear();
52     std::deque<size_t> pendingList;
53     std::vector<bool> visited(size, false);
54     // entry block (bbid=0) is a empty block, need skip
55     auto firstBlockId = 1;
56     pendingList.emplace_back(firstBlockId);
57 
58     while (!pendingList.empty()) {
59         size_t curBlockId = pendingList.back();
60         visited[curBlockId] = true;
61 
62         bool change = false;
63         auto &bb = bcBuilder_->GetBasicBlockById(curBlockId);
64         for (const auto &succBlock: bb.succs) {
65             if (!visited[succBlock->id]) {
66                 pendingList.emplace_back(succBlock->id);
67                 change = true;
68                 break;
69             }
70         }
71         if (change) {
72             continue;
73         }
74         for (const auto &succBlock: bb.catches) {
75             if (!visited[succBlock->id]) {
76                 pendingList.emplace_back(succBlock->id);
77                 change = true;
78                 break;
79             }
80         }
81         if (!change) {
82             postOrderList_.emplace_back(curBlockId);
83             pendingList.pop_back();
84         }
85     }
86 }
87 
MergeIntoPredBC(uint32_t predPc)88 bool FrameStateBuilder::MergeIntoPredBC(uint32_t predPc)
89 {
90     // liveout next
91     auto liveout = GetOrOCreateBCEndLiveOut(predPc);
92     FrameLiveOut *predliveOut = liveOutResult_;
93     return liveout->MergeLiveout(predliveOut);
94 }
95 
MergeFromSuccBB(size_t bbId)96 bool FrameStateBuilder::MergeFromSuccBB(size_t bbId)
97 {
98     // liveout next
99     auto liveout = GetOrOCreateBBLiveOut(bbId);
100     return liveOutResult_->MergeLiveout(liveout);
101 }
102 
MergeFromCatchBB(size_t bbId)103 void FrameStateBuilder::MergeFromCatchBB(size_t bbId)
104 {
105     // liveout next
106     bool accumulatorIsLive = liveOutResult_->TestBit(accumulatorIndex_);
107     auto liveout = GetOrOCreateBBLiveOut(bbId);
108     liveOutResult_->MergeLiveout(liveout);
109     // accumulatorIndex_ is exeception object
110     if (!accumulatorIsLive) {
111         liveOutResult_->ClearBit(accumulatorIndex_);
112     }
113 }
114 
ComputeLiveOut(size_t bbId)115 bool FrameStateBuilder::ComputeLiveOut(size_t bbId)
116 {
117     auto &bb = bcBuilder_->GetBasicBlockById(bbId);
118     bool changed = false;
119     // iterator bc
120     auto &iterator = bb.GetBytecodeIterator();
121     iterator.GotoEnd();
122     ASSERT(bb.end == iterator.Index());
123     auto bbLiveout = GetOrOCreateBBLiveOut(bb.id);
124     auto liveout = GetOrOCreateBCEndLiveOut(bb.end);
125     liveOutResult_->CopyFrom(liveout);
126     // init frameContext
127     currentBBliveOut_ = bbLiveout;
128     while (true) {
129         auto &bytecodeInfo = iterator.GetBytecodeInfo();
130         if (!bb.catches.empty() && !bytecodeInfo.NoThrow()) {
131             ASSERT(bb.catches.size() == 1); // 1: one catch
132             MergeFromCatchBB(bb.catches.at(0)->id);
133         }
134         ComputeLiveOutBC(bytecodeInfo);
135         --iterator;
136         if (iterator.Done()) {
137             break;
138         }
139         auto prevPc = iterator.Index();
140         changed |= MergeIntoPredBC(prevPc);
141     }
142     if (!bb.trys.empty()) {
143         // clear GET_EXCEPTION gate if this is a catch block
144         liveOutResult_->ClearBit(accumulatorIndex_);
145     }
146     bbLiveout->CopyFrom(liveOutResult_);
147     // merge current into pred bb
148     for (auto bbPred : bb.preds) {
149         changed |= MergeIntoPredBC(bbPred->end);
150     }
151 
152     return changed;
153 }
154 
ComputeLiveState()155 void FrameStateBuilder::ComputeLiveState()
156 {
157     // recompute liveout
158     bool changed = true;
159     while (changed) {
160         changed = false;
161         for (size_t i = 0; i < postOrderList_.size(); i++) {
162             changed |= ComputeLiveOut(postOrderList_[i]);
163         }
164     }
165 }
166 
DoBytecodeAnalysis()167 void FrameStateBuilder::DoBytecodeAnalysis()
168 {
169     auto bcSize = bcBuilder_->GetLastBcIndex() + 1; // 1: +1 pcOffsets size
170     auto bbSize = bcBuilder_->GetBasicBlockCount();
171     bcEndStateLiveouts_.resize(bcSize, nullptr);
172     bbBeginStateLiveouts_.resize(bbSize, nullptr);
173     auto chunk = circuit_->chunk();
174     liveOutResult_ = chunk->New<FrameLiveOut>(chunk, numVregs_);
175     bbFrameContext_.resize(bbSize, nullptr);
176     BuildPostOrderList(bbSize);
177     ComputeLiveState();
178     if (bcBuilder_->IsLogEnabled()) {
179         DumpLiveState();
180     }
181     ComputeLoopInfo();
182 }
183 
ComputeLiveOutBC(const BytecodeInfo &bytecodeInfo)184 void FrameStateBuilder::ComputeLiveOutBC(const BytecodeInfo &bytecodeInfo)
185 {
186     if (bytecodeInfo.GetOpcode() == EcmaOpcode::RESUMEGENERATOR) {
187         currentBBliveOut_->defRegisters_.Union(liveOutResult_->liveout_);
188     }
189     // variable kill
190     if (bytecodeInfo.AccOut()) {
191         liveOutResult_->ClearBit(accumulatorIndex_);
192         currentBBliveOut_->defRegisters_.SetBit(accumulatorIndex_);
193     }
194     for (const auto &out: bytecodeInfo.vregOut) {
195         liveOutResult_->ClearBit(out);
196         currentBBliveOut_->defRegisters_.SetBit(out);
197     }
198 
199     // variable use
200     if (bytecodeInfo.AccIn()) {
201         liveOutResult_->SetBit(accumulatorIndex_);
202     }
203     for (size_t i = 0; i < bytecodeInfo.inputs.size(); i++) {
204         auto in = bytecodeInfo.inputs[i];
205         if (std::holds_alternative<VirtualRegister>(in)) {
206             auto vreg = std::get<VirtualRegister>(in).GetId();
207             liveOutResult_->SetBit(vreg);
208         }
209     }
210 }
211 
GetOrOCreateBCEndLiveOut(uint32_t bcIndex)212 FrameLiveOut *FrameStateBuilder::GetOrOCreateBCEndLiveOut(uint32_t bcIndex)
213 {
214     auto liveout = bcEndStateLiveouts_[bcIndex];
215     if (liveout == nullptr) {
216         auto chunk = circuit_->chunk();
217         liveout = chunk->New<FrameLiveOut>(chunk, numVregs_);
218         bcEndStateLiveouts_[bcIndex] = liveout;
219     }
220     return liveout;
221 }
222 
GetOrOCreateBBLiveOut(size_t bbIndex)223 FrameLiveOut *FrameStateBuilder::GetOrOCreateBBLiveOut(size_t bbIndex)
224 {
225     // As BB0 is empty, its bbBeginStateLiveouts is the same as BB1.
226     if (bbIndex == 0) {
227         if (bcBuilder_->IsOSR()) {
228             bbIndex = GetOsrLoopHeadBBId();
229         } else {
230             bbIndex = 1;
231         }
232     }
233     auto liveout = bbBeginStateLiveouts_[bbIndex];
234     if (liveout == nullptr) {
235         auto chunk = circuit_->chunk();
236         liveout = chunk->New<FrameLiveOut>(chunk, numVregs_);
237         bbBeginStateLiveouts_[bbIndex] = liveout;
238     }
239     return liveout;
240 }
241 
GetOrOCreateMergedContext(uint32_t bbIndex)242 FrameContext *FrameStateBuilder::GetOrOCreateMergedContext(uint32_t bbIndex)
243 {
244     auto context = bbFrameContext_[bbIndex];
245     if (context == nullptr) {
246         auto chunk = circuit_->chunk();
247         context = chunk->New<FrameContext>(chunk, numVregs_);
248         for (size_t i = 0; i < numVregs_; i++) {
249             context->SetValuesAt(i, Circuit::NullGate());
250         }
251         bbFrameContext_[bbIndex] = context;
252     }
253     return context;
254 }
255 
FillBcInputs(const BytecodeInfo &bytecodeInfo, GateRef gate)256 void FrameStateBuilder::FillBcInputs(const BytecodeInfo &bytecodeInfo, GateRef gate)
257 {
258     auto pgoType = pgoTypeRecorder_->GetPGOType(acc_.TryGetPcOffset(gate));
259     acc_.TrySetPGOType(gate, pgoType);
260 
261     auto valueCount = acc_.GetInValueCount(gate);
262     [[maybe_unused]] size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
263     [[maybe_unused]] size_t numValueOutputs = bytecodeInfo.ComputeOutCount();
264     // RETURNUNDEFINED has value input, but not from acc
265     ASSERT(numValueInputs == valueCount || bytecodeInfo.GetOpcode() == EcmaOpcode::RETURNUNDEFINED);
266     ASSERT(numValueOutputs <= 1 + (bytecodeInfo.EnvOut() ? 1 : 0));
267     auto valueStarts = acc_.GetInValueStarts(gate);
268     for (size_t valueIdx = 0; valueIdx < valueCount; valueIdx++) {
269         auto inIdx = valueIdx + valueStarts;
270         if (!acc_.IsInGateNull(gate, inIdx)) {
271             continue;
272         }
273         if (valueIdx < bytecodeInfo.inputs.size()) {
274             auto vregId = std::get<VirtualRegister>(bytecodeInfo.inputs.at(valueIdx)).GetId();
275             GateRef defVreg = liveContext_->ValuesAt(vregId);
276             acc_.NewIn(gate, inIdx, defVreg);
277         } else {
278             GateRef defAcc = liveContext_->ValuesAt(accumulatorIndex_);
279             acc_.NewIn(gate, inIdx, defAcc);
280         }
281     }
282 }
283 
AdvanceToNextBc(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId)284 void FrameStateBuilder::AdvanceToNextBc(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId)
285 {
286     if (bytecodeInfo.IsGeneral()) {
287         BindStateSplitBefore(bytecodeInfo, liveout, bcId);
288         if (bytecodeInfo.GetOpcode() == EcmaOpcode::SUSPENDGENERATOR_V8 ||
289             bytecodeInfo.GetOpcode() == EcmaOpcode::ASYNCGENERATORRESOLVE_V8_V8_V8) {
290             auto hole = circuit_->GetConstantGate(MachineType::I64,
291                                                   JSTaggedValue::VALUE_HOLE,
292                                                   GateType::TaggedValue());
293             uint32_t numRegs = accumulatorIndex_;
294             std::vector<GateRef> vec(numRegs + 1, hole);
295             vec[0] = liveContext_->currentDepend_;
296             // accumulator is res
297             for (size_t i = 0; i < numRegs; i++) {
298                 if (liveout->TestBit(i)) {
299                     vec[i + 1] = liveContext_->ValuesAt(i);  // 1: skip dep
300                 } else {
301                     vec[i + 1] = hole; // 1: skip dep
302                 }
303             }
304             auto res = circuit_->NewGate(circuit_->SaveRegister(numRegs), vec);
305             liveContext_->currentDepend_ = res;
306         }
307     }
308 }
309 
UpdateStateDepend(GateRef state, GateRef depend)310 void FrameStateBuilder::UpdateStateDepend(GateRef state, GateRef depend)
311 {
312     liveContext_->currentState_ = state;
313     liveContext_->currentDepend_ = depend;
314 }
315 
UpdateMoveValues(const BytecodeInfo &bytecodeInfo)316 void FrameStateBuilder::UpdateMoveValues(const BytecodeInfo &bytecodeInfo)
317 {
318     GateRef gate = Circuit::NullGate();
319     if (bytecodeInfo.AccIn()) {
320         gate = liveContext_->ValuesAt(accumulatorIndex_);
321     } else if (bytecodeInfo.inputs.size() != 0) {
322         auto vreg = std::get<VirtualRegister>(bytecodeInfo.inputs.at(0)).GetId();
323         gate = liveContext_->ValuesAt(vreg);
324     }
325     // variable kill
326     if (bytecodeInfo.AccOut()) {
327         liveContext_->SetValuesAt(accumulatorIndex_, gate);
328     } else if (bytecodeInfo.vregOut.size() != 0) {
329         auto vreg = bytecodeInfo.vregOut[0];
330         liveContext_->SetValuesAt(vreg, gate);
331     }
332 }
333 
UpdateFrameValues(const BytecodeInfo &bytecodeInfo, uint32_t bcId, GateRef gate)334 void FrameStateBuilder::UpdateFrameValues(const BytecodeInfo &bytecodeInfo,
335     uint32_t bcId, GateRef gate)
336 {
337     ASSERT(!bytecodeInfo.IsDiscarded() && !bytecodeInfo.IsMov());
338     if (bytecodeInfo.IsSetConstant()) {
339         liveContext_->SetValuesAt(accumulatorIndex_, gate);
340         return;
341     }
342     // jump gate is null
343     if (IsGateNotEmpty(gate)) {
344         FillBcInputs(bytecodeInfo, gate);
345     }
346     auto liveout = GetFrameLiveoutAfter(bcId);
347     // variable kill
348     if (bytecodeInfo.AccOut()) {
349         liveContext_->SetValuesAt(accumulatorIndex_, gate);
350     }
351     for (const auto &out: bytecodeInfo.vregOut) {
352         liveContext_->SetValuesAt(out, gate);
353     }
354     if (bytecodeInfo.GetOpcode() == EcmaOpcode::RESUMEGENERATOR) {
355         // accumulator is generator object
356         for (size_t i = 0; i < accumulatorIndex_; i++) {
357             if (liveout->TestBit(i)) {
358                 auto restore = circuit_->NewGate(circuit_->RestoreRegister(i),
359                     MachineType::I64, { gate }, GateType::AnyType());
360                 liveContext_->SetValuesAt(i, restore);
361             }
362         }
363     }
364     BindStateSplitAfter(bytecodeInfo, bcId, gate);
365 }
366 
SetOsrLoopHeadBB(const BytecodeRegion &osrLoopBodyBB)367 void FrameStateBuilder::SetOsrLoopHeadBB(const BytecodeRegion &osrLoopBodyBB)
368 {
369     auto *loopInfo = GetLoopInfoByLoopBody(osrLoopBodyBB);
370     if (loopInfo == nullptr) {
371         loopHeadOfOSR_ = nullptr;
372     } else {
373         loopHeadOfOSR_ = &(bcBuilder_->GetBasicBlockById(loopInfo->loopHeadId));
374     }
375     return;
376 }
377 
IsOsrLoopExit(const BytecodeRegion &curBB)378 bool FrameStateBuilder::IsOsrLoopExit(const BytecodeRegion &curBB)
379 {
380     if (loopHeadOfOSR_ == nullptr) {
381         return false;
382     }
383     auto *loopInfo = GetLoopInfoByLoopBody(*loopHeadOfOSR_);
384     if (!loopInfo || !loopInfo->loopExits) {
385         return false;
386     }
387     for (auto *exit : *loopInfo->loopExits) {
388         if (exit == &curBB) {
389             return true;
390         }
391     }
392     return false;
393 }
394 
OutOfOsrLoop(const BytecodeRegion &curBB)395 bool FrameStateBuilder::OutOfOsrLoop(const BytecodeRegion &curBB)
396 {
397     if (loopHeadOfOSR_ == nullptr) {
398         return false;
399     }
400     const LoopInfo &loopInfoOfOSR = GetLoopInfo(*loopHeadOfOSR_);
401     const LoopInfo *curLoop = GetLoopInfoByLoopBody(curBB);
402     while (curLoop != nullptr) {
403         if (curLoop == &loopInfoOfOSR) {
404             return false;
405         }
406         curLoop = curLoop->parentInfo;
407     }
408     return true;
409 }
410 
GetOsrLoopHeadBBId() const411 size_t FrameStateBuilder::GetOsrLoopHeadBBId() const
412 {
413     if (loopHeadOfOSR_ == nullptr) {
414         return -1;
415     }
416     return loopHeadOfOSR_->id;
417 }
418 
InitEntryBB(const BytecodeRegion &bb)419 void FrameStateBuilder::InitEntryBB(const BytecodeRegion &bb)
420 {
421     auto frameContext = GetOrOCreateMergedContext(bb.id);
422     frameContext->currentState_ = circuit_->GetStateRoot();
423     frameContext->currentDepend_ = circuit_->GetDependRoot();
424     frameContext->needStateSplit_ = true;
425     // initialize argumnets
426     ASSERT(bcBuilder_->IsFirstBasicBlock(1)); // 1: is firstBlock
427     auto liveout = GetFrameLiveoutBefore(1); // 1: is firstBlock
428     GateRef frameArgs = bcBuilder_->GetFrameArgs();
429     if (liveout->TestBit(envIndex_)) {
430         GateRef jsFunc = acc_.GetValueIn(frameArgs, static_cast<size_t>(FrameArgIdx::FUNC));
431         auto env = acc_.GetInitialEnvGate(frameContext->currentDepend_, jsFunc);
432         frameContext->SetValuesAt(envIndex_, env);
433         frameContext->currentDepend_ = env;
434     }
435     auto holeGate = circuit_->GetConstantGate(MachineType::I64,
436                                               JSTaggedValue::VALUE_HOLE,
437                                               GateType::TaggedValue());
438     for (size_t i = 0; i < envIndex_; i++) {
439         if (liveout->TestBit(i)) {
440             if (bcBuilder_->ArgGateNotExisted(i)) {
441                 frameContext->SetValuesAt(i, holeGate);
442             } else {
443                 GateRef arg = bcBuilder_->GetArgGate(i);
444                 frameContext->SetValuesAt(i, arg);
445             }
446         }
447     }
448 
449     // init live interpreter registers
450     if (!bcBuilder_->IsOSR()) {
451         return;
452     }
453     auto *liveOut = GetFrameLiveoutBefore(GetOsrLoopHeadBBId());
454     for (size_t i = 0; i < envIndex_; i++) {
455         if (!liveOut->TestBit(i)) {
456             continue;
457         }
458         GateRef init = circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(i), MachineType::I64,
459                                          {circuit_->GetArgRoot()}, GateType::TaggedValue());
460         frameContext->SetValuesAt(i, init);
461     }
462     if (liveOut->TestBit(envIndex_)) {
463         // -7: env
464         GateRef env = circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_ENV), MachineType::I64,
465                                         {circuit_->GetArgRoot()}, GateType::TaggedValue());
466         frameContext->SetValuesAt(envIndex_, env);
467     }
468 }
469 
IsLoopHead(const BytecodeRegion &bb)470 bool FrameStateBuilder::IsLoopHead(const BytecodeRegion &bb)
471 {
472     return !(bcBuilder_->IsOSR() && OutOfOsrLoop(bb)) && bb.loopNumber > 0;
473 }
474 
IfLoopNeedMerge(const BytecodeRegion &bb) const475 bool FrameStateBuilder::IfLoopNeedMerge(const BytecodeRegion &bb) const
476 {
477     return !bcBuilder_->IsOSR() && bb.numOfStatePreds - bb.numOfLoopBack != 1; // 1: loop in
478 }
479 
InitMerge(size_t numOfIns, bool isLoop)480 GateRef FrameStateBuilder::InitMerge(size_t numOfIns, bool isLoop)
481 {
482     const GateMetaData *metaData = isLoop ? circuit_->LoopBegin(numOfIns) : circuit_->Merge(numOfIns);
483     return circuit_->NewGate(metaData, std::vector<GateRef>(numOfIns, Circuit::NullGate()));
484 }
485 
IsGateNotEmpty(GateRef gate) const486 bool FrameStateBuilder::IsGateNotEmpty(GateRef gate) const
487 {
488     return gate != Circuit::NullGate();
489 }
490 
NewMerge(const BytecodeRegion &bbNext)491 void FrameStateBuilder::NewMerge(const BytecodeRegion &bbNext)
492 {
493     auto frameContext = GetMergedBbContext(bbNext.id);
494     size_t numOfIns = bbNext.numOfStatePreds;
495     if (IsOsrLoopExit(bbNext)) {
496         // Only the precursor within the OSR loop is required.
497         numOfIns = 0;
498         for (const BytecodeRegion *bb : bbNext.preds) {
499             if (OutOfOsrLoop(*bb)) {
500                 continue;
501             }
502             numOfIns++;
503         }
504     }
505 
506     bool isLoopHead = IsLoopHead(bbNext);
507     GateRef merge;
508     GateRef dependMerge;
509     if (isLoopHead) {
510         if (!IfLoopNeedMerge(bbNext)) {
511             // only generate loop begin
512             merge = InitMerge(numOfIns, true);
513             dependMerge = circuit_->NewGate(circuit_->DependSelector(numOfIns),
514                 std::vector<GateRef>(numOfIns + 1, Circuit::NullGate())); // 1: merge
515         } else {
516             // generate both loop begin and merge
517             ASSERT(numOfIns - bbNext.numOfLoopBack > 1); // 1: loop in
518             size_t numOfLoopIns = bbNext.numOfLoopBack + 1; // 1: loop in
519             merge = InitMerge(numOfLoopIns, true);
520             dependMerge = circuit_->NewGate(circuit_->DependSelector(numOfLoopIns),
521                 std::vector<GateRef>(numOfLoopIns + 1, Circuit::NullGate())); // 1: merge
522             size_t numOfMergeIns = numOfIns - bbNext.numOfLoopBack;
523             frameContext->mergeState_ = InitMerge(numOfMergeIns, false);
524             frameContext->mergeDepend_ = circuit_->NewGate(circuit_->DependSelector(numOfMergeIns),
525                 std::vector<GateRef>(numOfMergeIns + 1, Circuit::NullGate())); // 1: merge
526             acc_.NewIn(frameContext->mergeDepend_, 0, frameContext->mergeState_);
527             acc_.NewIn(dependMerge, 1, frameContext->mergeDepend_); // 1: phi of merge
528             acc_.NewIn(merge, 0, frameContext->mergeState_);
529             frameContext->loopBackIndex_++;
530         }
531         frameContext->loopBackDepend_ = dependMerge;
532         frameContext->loopBackState_ = merge;
533     } else {
534         // only merge
535         merge = InitMerge(numOfIns, false);
536         dependMerge = circuit_->NewGate(circuit_->DependSelector(numOfIns),
537             std::vector<GateRef>(numOfIns + 1, Circuit::NullGate())); // 1: merge
538         frameContext->mergeDepend_ = dependMerge;
539         frameContext->mergeState_ = merge;
540     }
541     acc_.NewIn(dependMerge, 0, merge);  // 0: is state
542     // reset current state and depend
543     frameContext->currentState_ = merge;
544     frameContext->currentDepend_ = dependMerge;
545 
546     if (isLoopHead) {
547         ChunkVector<GateRef>& headerGates = bcBuilder_->GetLoopHeaderGates();
548         auto& loopInfo = GetLoopInfo(bbNext);
549         headerGates[loopInfo.sortIndx] = merge;
550     }
551 }
552 
MergeStateDepend(const BytecodeRegion &bb, const BytecodeRegion &bbNext)553 void FrameStateBuilder::MergeStateDepend(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
554 {
555     GateRef entryState = liveContext_->currentState_;
556     GateRef entryDepend = liveContext_->currentDepend_;
557     auto mergedContext = GetMergedBbContext(bbNext.id);
558     if (bbNext.numOfStatePreds == 1) { // 1: one entry edge
559         mergedContext->currentState_ = liveContext_->currentState_;
560         mergedContext->currentDepend_ = liveContext_->currentDepend_;
561         return;
562     }
563     auto index = mergedContext->currentIndex_;
564     // lazy first edge
565     if (index == 0) {
566         NewMerge(bbNext);
567     }
568     if (IsLoopBackEdge(bb, bbNext)) {
569         if (!(bcBuilder_->IsOSR() && IsOsrLoopExit(bbNext))) {
570             ASSERT(index != 0);
571         }
572         entryState = circuit_->NewGate(circuit_->LoopBack(), { entryState });
573     }
574     auto mergeInfo = GetCorrespondingState(bb, bbNext);
575     acc_.NewIn(mergeInfo.state, mergeInfo.index, entryState);
576     acc_.NewIn(mergeInfo.depend, mergeInfo.index + 1, entryDepend); // 1: skip state
577     mergedContext->needStateSplit_ = true;
578 }
579 
GetNumOfStatePreds(const BytecodeRegion &bb)580 size_t FrameStateBuilder::GetNumOfStatePreds(const BytecodeRegion &bb)
581 {
582     size_t numOfIns = bb.numOfStatePreds;
583     if (bcBuilder_->IsOSR() && IsOsrLoopExit(bb)) {
584         numOfIns = 0;
585         for (const BytecodeRegion *b : bb.preds) {
586             if (OutOfOsrLoop(*b)) {
587                 continue;
588             }
589             numOfIns++;
590         }
591     }
592     return numOfIns;
593 }
594 
MergeValue(const BytecodeRegion &bb, GateRef currentValue, GateRef nextValue, bool isLoopBack, bool changedInLoop)595 GateRef FrameStateBuilder::MergeValue(const BytecodeRegion &bb,
596     GateRef currentValue, GateRef nextValue, bool isLoopBack, bool changedInLoop)
597 {
598     ASSERT(IsGateNotEmpty(currentValue));
599     auto mergedContext = GetMergedBbContext(bb.id);
600     GateRef result = currentValue;
601     GateRef mergeValueSelector;
602 
603     // if already a merged gate
604     if (IsGateNotEmpty(nextValue) &&
605         (acc_.GetOpCode(nextValue) == OpCode::VALUE_SELECTOR &&
606         acc_.GetState(nextValue) == mergedContext->currentState_)) {
607         ASSERT(IsGateNotEmpty(currentValue));
608         if (isLoopBack) {
609             ASSERT(IsGateNotEmpty(mergedContext->loopBackState_));
610             acc_.NewIn(nextValue, mergedContext->loopBackIndex_ + 1, currentValue); // 1: merge
611         } else {
612             ASSERT(IsGateNotEmpty(mergedContext->mergeState_));
613             if (!IsGateNotEmpty(mergedContext->loopBackState_)) {
614                 acc_.NewIn(nextValue, mergedContext->mergeIndex_ + 1, currentValue);  // 1: merge
615             } else {
616                 mergeValueSelector = acc_.GetIn(nextValue, 1); // 1: index of phi of merge
617                 acc_.NewIn(mergeValueSelector, mergedContext->mergeIndex_ + 1, currentValue); // 1: merge
618             }
619         }
620         result = nextValue;
621     } else if (currentValue != nextValue) {
622         bool needMergeValues = IsGateNotEmpty(mergedContext->mergeState_);
623         // build value selector for merge.
624         if (needMergeValues) {
625             size_t numOfIns = acc_.GetNumIns(mergedContext->mergeState_);
626             auto inList = std::vector<GateRef>(numOfIns + 1, Circuit::NullGate());  // 1: state
627             auto phi = circuit_->NewGate(
628                 circuit_->ValueSelector(numOfIns), MachineType::I64, inList.size(), inList.data(),
629                 GateType::AnyType());
630             acc_.NewIn(phi, 0, mergedContext->mergeState_);
631             for (size_t i = 0; i < mergedContext->mergeIndex_; i++) {
632                 acc_.NewIn(phi, i + 1, nextValue);  // 1: merge
633             }
634             if (!isLoopBack) {
635                 acc_.NewIn(phi, mergedContext->mergeIndex_ + 1, currentValue); // 1: merge
636             }
637             mergeValueSelector = result = phi;
638         }
639         // build value selector for loop begin.
640         // If the register value of the corresponding bit is changed in the loop or
641         // there is a state that needs to be merged (e.g.Multiple values or branches need to be merged into a phi node)
642         // need to create or update the phi node.
643         if (IsGateNotEmpty(mergedContext->loopBackState_) && (changedInLoop || needMergeValues)) {
644             size_t numOfIns = acc_.GetNumIns(mergedContext->loopBackState_);
645             auto inList = std::vector<GateRef>(numOfIns + 1, Circuit::NullGate());  // 1: state
646             auto phi = circuit_->NewGate(
647                 circuit_->ValueSelector(numOfIns), MachineType::I64, inList.size(), inList.data(),
648                 GateType::AnyType());
649             acc_.NewIn(phi, 0, mergedContext->loopBackState_);
650             if (IsGateNotEmpty(mergedContext->mergeState_)) {
651                 acc_.NewIn(phi, 1, mergeValueSelector); // 1: merge
652             }
653             if (IsGateNotEmpty(nextValue)) {
654                 for (size_t i = 0; i < mergedContext->loopBackIndex_; i++) {
655                     acc_.NewIn(phi, i + 1, nextValue); // 1: merge
656                 }
657             }
658             if (isLoopBack || !IsGateNotEmpty(mergedContext->mergeState_)) {
659                 acc_.NewIn(phi, mergedContext->loopBackIndex_ + 1, currentValue); // 1: merge
660             }
661             result = phi;
662         }
663     }
664     return result;
665 }
666 
GetCorrespondingState(const BytecodeRegion &bb, const BytecodeRegion &bbNext)667 MergeStateDependInfo FrameStateBuilder::GetCorrespondingState(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
668 {
669     auto mergedContext = GetMergedBbContext(bbNext.id);
670     if (IsLoopHead(bbNext)) {
671         if (!IfLoopNeedMerge(bbNext)) { // 1: only one loop in
672             ASSERT(!IsGateNotEmpty(mergedContext->mergeState_));
673             ASSERT(!IsGateNotEmpty(mergedContext->mergeDepend_));
674             return {mergedContext->loopBackState_, mergedContext->loopBackDepend_, mergedContext->loopBackIndex_};
675         }
676         if (bbNext.IsLoopBack(bb)) {
677             return {mergedContext->loopBackState_, mergedContext->loopBackDepend_, mergedContext->loopBackIndex_};
678         } else {
679             return {mergedContext->mergeState_, mergedContext->mergeDepend_, mergedContext->mergeIndex_};
680         }
681     } else {
682         ASSERT(!IsGateNotEmpty(mergedContext->loopBackState_));
683         ASSERT(!IsGateNotEmpty(mergedContext->loopBackDepend_));
684         return {mergedContext->mergeState_, mergedContext->mergeDepend_, mergedContext->mergeIndex_};
685     }
686 }
687 
MergeAssignment(const BytecodeRegion &bb, const BytecodeRegion &bbNext)688 void FrameStateBuilder::MergeAssignment(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
689 {
690     auto mergedContext = GetMergedBbContext(bbNext.id);
691     [[maybe_unused]] auto mergeInfo = GetCorrespondingState(bb, bbNext);
692     ASSERT(acc_.IsCFGMerge(mergeInfo.state));
693     auto liveout = GetFrameLiveoutBefore(bbNext.id);
694     auto *loopAssignment = GetLoopAssignment(bbNext);
695     for (size_t i = 0; i < numVregs_; i++) {
696         if (liveout->TestBit(i)) {
697             auto current = liveContext_->ValuesAt(i);
698             auto next = mergedContext->ValuesAt(i);
699             GateRef value = Circuit::NullGate();
700 #ifndef NDEBUG
701             if (loopAssignment == nullptr) {
702                 ASSERT(IsGateNotEmpty(current) && IsGateNotEmpty(next));
703             } else if (loopAssignment->TestBit(i)) {
704                 // next is null or phi
705                 ASSERT(!IsGateNotEmpty(next) ||
706                     ((acc_.GetOpCode(next) == OpCode::VALUE_SELECTOR) &&
707                     acc_.GetState(next) == mergedContext->currentState_));
708             } else if (!IsGateNotEmpty(mergedContext->mergeState_)) {
709                 ASSERT(!IsGateNotEmpty(next) || current == next);
710             }
711 #endif
712             bool changedInLoop = loopAssignment != nullptr && loopAssignment->TestBit(i);
713             value = MergeValue(bbNext, current, next, bbNext.IsLoopBack(bb), changedInLoop);
714             mergedContext->SetValuesAt(i, value);
715         }
716     }
717 }
718 
CopyLiveoutValues(const BytecodeRegion &bbNext, FrameContext* dest, FrameContext* src)719 void FrameStateBuilder::CopyLiveoutValues(const BytecodeRegion &bbNext,
720     FrameContext* dest, FrameContext* src)
721 {
722     auto liveout = GetFrameLiveoutBefore(bbNext.id);
723     for (size_t i = 0; i < numVregs_; i++) {
724         if (liveout->TestBit(i)) {
725             auto value = src->ValuesAt(i);
726             dest->SetValuesAt(i, value);
727         } else {
728             dest->SetValuesAt(i, Circuit::NullGate());
729         }
730     }
731 }
732 
GetCachedContext()733 FrameContext *FrameStateBuilder::GetCachedContext()
734 {
735     // lazy init cachedContext
736     if (cachedContext_ == nullptr) {
737         auto chunk = circuit_->chunk();
738         cachedContext_ = chunk->New<FrameContext>(chunk, numVregs_);
739     }
740     auto result = cachedContext_;
741     if (cachedContext_ == liveContext_) {
742         if (cachedContextBackup_ == nullptr) {
743             auto chunk = circuit_->chunk();
744             cachedContextBackup_ = chunk->New<FrameContext>(chunk, numVregs_);
745         }
746         result = cachedContextBackup_;
747     }
748     return result;
749 }
750 
SaveCurrentContext(const BytecodeRegion &bb)751 void FrameStateBuilder::SaveCurrentContext(const BytecodeRegion &bb)
752 {
753     auto newContext = GetCachedContext();
754     ASSERT(newContext != liveContext_);
755     newContext->CopyCurrentStatus(liveContext_);
756     CopyLiveoutValues(bb, newContext, liveContext_);
757     liveContext_ = newContext;
758 }
759 
NewLoopExit(const BytecodeRegion &bbNext, BitSet *loopAssignment)760 void FrameStateBuilder::NewLoopExit(const BytecodeRegion &bbNext, BitSet *loopAssignment)
761 {
762     auto state = liveContext_->currentState_;
763     auto depend = liveContext_->currentDepend_;
764     auto loopExit = circuit_->NewGate(circuit_->LoopExit(), { state });
765     auto loopExitDepend = circuit_->NewGate(circuit_->LoopExitDepend(),
766         { loopExit, depend });
767     auto liveout = GetFrameLiveoutBefore(bbNext.id);
768     for (size_t i = 0; i < numVregs_; i++) {
769         if (liveout->TestBit(i)) {
770             auto current = liveContext_->ValuesAt(i);
771             if (loopAssignment->TestBit(i)) {
772                 current = circuit_->NewGate(circuit_->LoopExitValue(), acc_.GetMachineType(current),
773                     {loopExit, current}, acc_.GetGateType(current));
774             }
775             liveContext_->SetValuesAt(i, current);
776         } else {
777             ASSERT(!IsGateNotEmpty(liveContext_->ValuesAt(i)));
778         }
779     }
780     liveContext_->currentState_ = loopExit;
781     liveContext_->currentDepend_ = loopExitDepend;
782     if (!bcBuilder_->IsTypeLoweringEnabled()) {
783         return;
784     }
785     auto stateSplit = BuildStateSplit(liveContext_, liveout, bbNext.start);
786     liveContext_->currentDepend_ = stateSplit;
787 }
788 
TryInsertLoopExit(const BytecodeRegion &bb, const BytecodeRegion &bbNext)789 void FrameStateBuilder::TryInsertLoopExit(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
790 {
791     if (!bcBuilder_->EnableLoopOptimization() && !bcBuilder_->IsOSR()) {
792         return;
793     }
794     if (bcBuilder_->IsOSR() && bcBuilder_->IsCacheBBOfOSRLoop(bbNext)) {
795         return;
796     }
797     auto currentLoop = GetLoopInfoByLoopBody(bb);
798     if (currentLoop != nullptr && !currentLoop->loopBodys->TestBit(bbNext.id)) {
799         // use bbNext as merged values
800         SaveCurrentContext(bbNext);
801     }
802     while (currentLoop != nullptr && !currentLoop->loopBodys->TestBit(bbNext.id)) {
803         ASSERT(currentLoop->loopExits != nullptr);
804 #ifndef NDEBUG
805         bool found = false;
806         for (auto current : *currentLoop->loopExits) {
807             if (current->id == bbNext.id) {
808                 found = true;
809                 break;
810             }
811         }
812         ASSERT(found);
813 #endif
814         NewLoopExit(bbNext, currentLoop->loopAssignment);
815         currentLoop = currentLoop->parentInfo;
816     }
817 }
818 
AdvanceToNextBB(const BytecodeRegion &bb, bool isOsrLoopExit)819 void FrameStateBuilder::AdvanceToNextBB(const BytecodeRegion &bb, bool isOsrLoopExit)
820 {
821     liveContext_ = GetMergedBbContext(bb.id);
822     ASSERT(liveContext_ != nullptr);
823     if (bb.loopNumber > 0) {
824         // use bb as merged values
825         SaveCurrentContext(bb);
826     } else if (!isOsrLoopExit) {
827         // all input merged
828         ASSERT(liveContext_->currentIndex_ == bb.numOfStatePreds);
829     }
830     if (liveContext_->needStateSplit_) {
831         liveContext_->needStateSplit_ = false;
832         if (!bcBuilder_->IsTypeLoweringEnabled()) {
833             return;
834         }
835         auto liveout = GetOrOCreateBBLiveOut(bb.id);
836         auto stateSplit = BuildStateSplit(liveContext_, liveout, bb.start);
837         liveContext_->currentDepend_ = stateSplit;
838     }
839 }
840 
841 class SubContextScope {
842 public:
SubContextScope(FrameStateBuilder* frameBuilder)843     explicit SubContextScope(FrameStateBuilder* frameBuilder)
844         : frameBuilder_(frameBuilder)
845     {
846         originContext_ = frameBuilder->liveContext_;
847     }
848 
~SubContextScope()849     ~SubContextScope()
850     {
851         frameBuilder_->liveContext_ = originContext_;
852     }
853 private:
854     FrameContext* originContext_ {nullptr};
855     FrameStateBuilder* frameBuilder_ {nullptr};
856 };
857 
MergeIntoSuccessor(const BytecodeRegion &bb, const BytecodeRegion &bbNext)858 void FrameStateBuilder::MergeIntoSuccessor(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
859 {
860     [[maybe_unused]] SubContextScope scope(this);
861     TryInsertLoopExit(bb, bbNext);
862     auto mergedContext = GetOrOCreateMergedContext(bbNext.id);
863     MergeStateDepend(bb, bbNext);
864     if (mergedContext->currentIndex_ == 0) {
865         if (bbNext.loopNumber > 0) {
866             MergeAssignment(bb, bbNext);
867         } else {
868             CopyLiveoutValues(bbNext, mergedContext, liveContext_);
869         }
870     } else {
871         MergeAssignment(bb, bbNext);
872     }
873     // We should connect this gate to loop begin although it's not a loop back edge
874     // if there is no merge state, which means it's the sole loop in.
875     if (bbNext.IsLoopBack(bb) || !IsGateNotEmpty(mergedContext->mergeState_)) {
876         mergedContext->loopBackIndex_++;
877     } else {
878         mergedContext->mergeIndex_++;
879     }
880     mergedContext->currentIndex_++;
881 }
882 
IsLoopBackEdge(const BytecodeRegion &bb, const BytecodeRegion &bbNext)883 bool FrameStateBuilder::IsLoopBackEdge(const BytecodeRegion &bb, const BytecodeRegion &bbNext)
884 {
885     if (bcBuilder_->IsOSR() && OutOfOsrLoop(bbNext)) {
886         return false;
887     } else if (bbNext.loopNumber > 0) {
888         auto& loopInfo = GetLoopInfo(bbNext);
889         return loopInfo.loopBodys->TestBit(bb.id);
890     }
891     return false;
892 }
893 
GetLoopInfo(const BytecodeRegion &bb)894 FrameStateBuilder::LoopInfo& FrameStateBuilder::GetLoopInfo(const BytecodeRegion &bb)
895 {
896     ASSERT(bb.loopNumber > 0);
897     return loops_[bb.loopNumber - 1]; // -1: for index
898 }
899 
GetLoopInfo(BytecodeRegion &bb)900 FrameStateBuilder::LoopInfo& FrameStateBuilder::GetLoopInfo(BytecodeRegion &bb)
901 {
902     ASSERT(bb.loopNumber > 0);
903     return loops_[bb.loopNumber - 1]; // -1: for index
904 }
905 
GetLoopInfoByLoopBody(const BytecodeRegion &bb)906 FrameStateBuilder::LoopInfo* FrameStateBuilder::GetLoopInfoByLoopBody(const BytecodeRegion &bb)
907 {
908     if (bb.loopIndex == 0) {
909         return nullptr;
910     }
911     auto& loopInfo = loops_[bb.loopIndex - 1];
912     ASSERT(loopInfo.loopBodys->TestBit(bb.id));
913     return &loopInfo;
914 }
915 
GetLoopAssignment(const BytecodeRegion &bb)916 BitSet *FrameStateBuilder::GetLoopAssignment(const BytecodeRegion &bb)
917 {
918     if (bb.loopNumber > 0) {
919         auto& loopInfo = GetLoopInfo(bb);
920         return loopInfo.loopAssignment;
921     }
922     return nullptr;
923 }
924 
AddEmptyBlock(BytecodeRegion* bb)925 void FrameStateBuilder::AddEmptyBlock(BytecodeRegion* bb)
926 {
927     bbBeginStateLiveouts_.emplace_back(nullptr);
928     bbFrameContext_.emplace_back(nullptr);
929     auto liveout = GetOrOCreateBBLiveOut(bb->id);
930     liveout->CopyFrom(liveOutResult_);
931     GetOrOCreateMergedContext(bb->id);
932     bcBuilder_->AddBasicBlock(bb);
933 }
934 
935 class BlockLoopAnalysis {
936 public:
BlockLoopAnalysis(FrameStateBuilder *builder, Chunk* chunk)937     explicit BlockLoopAnalysis(FrameStateBuilder *builder, Chunk* chunk)
938         : frameBuilder_(builder), bcBuilder_(builder->bcBuilder_),
939         pendingList_(chunk), loopbacks_(chunk),
940         dfsStack_(chunk), visitState_(chunk), chunk_(chunk) {}
941 
Run()942     void Run()
943     {
944         ComputeLoopBack();
945         if (bcBuilder_->TerminateAnalysis()) {
946             return;
947         }
948         TryClearDeadBlock();
949         bcBuilder_->ComputeNumOfLoopBack();
950         frameBuilder_->numLoops_ = numLoops_;
951         if (numLoops_ > 0) {
952             ComputeLoopInfo();
953             if (bcBuilder_->IsLogEnabled()) {
954                 for (size_t i = 0; i < numLoops_; i++) {
955                     auto& loopInfo = frameBuilder_->loops_[i];
956                     PrintLoop(loopInfo);
957                 }
958             }
959         }
960     }
961 
CountLoopBackEdge(size_t fromId, size_t toId)962     void CountLoopBackEdge(size_t fromId, size_t toId)
963     {
964         loopbacks_.push_back({fromId, toId});
965         auto &toBlock = bcBuilder_->GetBasicBlockById(toId);
966         toBlock.loopBacks.insert(fromId);
967         if (toBlock.loopNumber == 0) {
968             toBlock.loopNumber = ++numLoops_;
969         }
970     }
971 
CheckDominance()972     void CheckDominance()
973     {
974         for (size_t i = 0; i < loopbacks_.size(); i++) {
975             auto loopBackinfo = loopbacks_[i];
976             bool isDom = bcBuilder_->IsAncestor(loopBackinfo.toId, loopBackinfo.fromId);
977             if (!isDom) {
978                 bcBuilder_->SetIrreducibleLoop();
979                 LOG_COMPILER(INFO) << "CFG is not reducible. Compilation aborted.";
980                 break;
981             }
982         }
983     }
984 
ComputeLoopBack()985     void ComputeLoopBack()
986     {
987         auto size = bcBuilder_->GetBasicBlockCount();
988         visitState_.resize(size, MarkState::UNVISITED);
989         size_t entryId = 0; // entry id
990         VisitedInfo info = {0, false};
991         visitedInfo_.resize(size, info);
992         pendingList_.emplace_back(entryId);
993         while (!pendingList_.empty()) {
994             size_t bbId = pendingList_.back();
995             auto &bb = bcBuilder_->GetBasicBlockById(bbId);
996             bool allVisited = true;
997             visitState_[bbId] = MarkState::PENDING;
998             BytecodeRegion* catchBlock = bb.catches.empty() ? nullptr : bb.catches.at(0);
999             for (size_t i = visitedInfo_[bbId].needVisitIndex; i < bb.succs.size(); i++) {
1000                 BytecodeRegion* succBlock = bb.succs[i];
1001                 size_t succId = succBlock->id;
1002                 visitedInfo_[bbId].needVisitIndex = i + 1;
1003                 if (visitState_[succId] == MarkState::UNVISITED) {
1004                     pendingList_.emplace_back(succId);
1005                     visitState_[succId] = MarkState::ON_STACK;
1006                     allVisited = false;
1007                     break;
1008                 } else if (visitState_[succId] == MarkState::PENDING) {
1009                     // back edge
1010                     CountLoopBackEdge(bbId, succId);
1011                 }
1012             }
1013             // we consider catchBlock as a special succ, which means if we have visited a succ,
1014             // visiting catchBlock is not allowed due to the rule of RPO.
1015             if (allVisited && catchBlock != nullptr && !visitedInfo_[bbId].isVisitedCatchBlock) {
1016                 size_t catchId = catchBlock->id;
1017                 visitedInfo_[bbId].isVisitedCatchBlock = true;
1018                 if (visitState_[catchId] == MarkState::UNVISITED) {
1019                     pendingList_.emplace_back(catchId);
1020                     visitState_[catchId] = MarkState::ON_STACK;
1021                     allVisited = false;
1022                 } else if (visitState_[catchId] == MarkState::PENDING) {
1023                     // back edge
1024                     CountLoopBackEdge(bbId, catchId);
1025                 }
1026             }
1027             if (allVisited) {
1028                 visitState_[bbId] = MarkState::VISITED;
1029                 pendingList_.pop_back();
1030                 frameBuilder_->rpoList_.push_front(bbId);
1031             }
1032         }
1033 
1034         if (bcBuilder_->NeedIrreducibleLoopCheck()) {
1035             CheckDominance();
1036         }
1037     }
1038 
TryClearDeadBlock()1039     void TryClearDeadBlock()
1040     {
1041         if (frameBuilder_->rpoList_.size() == bcBuilder_->NumberOfLiveBlock()) {
1042             return;
1043         }
1044         auto size = bcBuilder_->GetBasicBlockCount();
1045         for (size_t i = 0; i < size; i++) {
1046             auto &bb = bcBuilder_->GetBasicBlockById(i);
1047             if (bb.numOfStatePreds != 0 && visitState_[i] == MarkState::UNVISITED) {
1048                 bb.numOfStatePreds = 0;
1049             }
1050         }
1051         bcBuilder_->RemoveUnreachableRegion();
1052     }
1053 
CountLoopBody(FrameStateBuilder::LoopInfo& loopInfo, size_t bbId)1054     void CountLoopBody(FrameStateBuilder::LoopInfo& loopInfo, size_t bbId)
1055     {
1056         if (bbId != loopInfo.loopHeadId && !loopInfo.loopBodys->TestBit(bbId)) {
1057             loopInfo.loopBodys->SetBit(bbId);
1058             pendingList_.emplace_back(bbId);
1059             auto liveout = frameBuilder_->GetOrOCreateBBLiveOut(bbId);
1060             ASSERT(liveout != nullptr);
1061             loopInfo.loopAssignment->Union(liveout->defRegisters_);
1062         }
1063     }
1064 
PropagateLoopBody(FrameStateBuilder::LoopInfo& loopInfo)1065     void PropagateLoopBody(FrameStateBuilder::LoopInfo& loopInfo)
1066     {
1067         while (!pendingList_.empty()) {
1068             auto cur = pendingList_.back();
1069             auto &curBlock = bcBuilder_->GetBasicBlockById(cur);
1070             pendingList_.pop_back();
1071             for (auto pred : curBlock.preds) {
1072                 CountLoopBody(loopInfo, pred->id);
1073             }
1074             for (auto pred : curBlock.trys) {
1075                 CountLoopBody(loopInfo, pred->id);
1076             }
1077         }
1078     }
1079 
InitLoopInfo(FrameStateBuilder::LoopInfo& loopInfo, BytecodeRegion& loopHeader, size_t backId)1080     void InitLoopInfo(FrameStateBuilder::LoopInfo& loopInfo, BytecodeRegion& loopHeader, size_t backId)
1081     {
1082         if (loopInfo.loopHeadId == 0) {
1083             auto size = bcBuilder_->GetBasicBlockCount();
1084             loopInfo.loopHeadId = loopHeader.id;
1085             loopInfo.loopIndex = loopHeader.loopNumber;
1086             loopInfo.loopBodys = chunk_->New<BitSet>(chunk_, size);
1087             loopInfo.loopAssignment = chunk_->New<BitSet>(chunk_, frameBuilder_->numVregs_);
1088             loopHeader.loopIndex = loopInfo.loopIndex;
1089             loopInfo.loopBodys->SetBit(loopInfo.loopHeadId);
1090             auto liveout = frameBuilder_->GetOrOCreateBBLiveOut(loopInfo.loopHeadId);
1091             loopInfo.loopAssignment->Union(liveout->defRegisters_);
1092             loopInfo.numLoopBacks = 1;
1093             loopInfo.loopBodys->SetBit(backId);
1094         } else {
1095             if (!loopInfo.loopBodys->TestBit(backId)) {
1096                 loopInfo.loopBodys->SetBit(backId);
1097             }
1098             loopInfo.numLoopBacks++;
1099         }
1100     }
1101 
ComputeLoopInfo()1102     void ComputeLoopInfo()
1103     {
1104         frameBuilder_->loops_.resize(numLoops_, FrameStateBuilder::LoopInfo());
1105         for (auto& info : loopbacks_) {
1106             auto& toBlock = bcBuilder_->GetBasicBlockById(info.toId);
1107             auto& loopInfo = frameBuilder_->GetLoopInfo(toBlock);
1108             InitLoopInfo(loopInfo, toBlock, info.fromId);
1109         }
1110         TryMergeLoopEntry();
1111         ResizeLoopBody(); // tryMerge will insert region, need resize loop body.
1112         for (auto& info : loopbacks_) {
1113             auto& toBlock = bcBuilder_->GetBasicBlockById(info.toId);
1114             auto& loopInfo = frameBuilder_->GetLoopInfo(toBlock);
1115             CountLoopBody(loopInfo, info.fromId);
1116             PropagateLoopBody(loopInfo);
1117         }
1118 
1119         if (!bcBuilder_->EnableLoopOptimization() && !bcBuilder_->IsOSR()) {
1120             return;
1121         }
1122 
1123         auto size = bcBuilder_->GetBasicBlockCount();
1124         dfsStack_.resize(size, DFSState(0, 0));
1125         ComputeLoopTree();
1126     }
1127 
InsertEmptyBytecodeRegion(FrameStateBuilder::LoopInfo& loopInfo, BytecodeRegion& loopHeader, size_t numOfEntries)1128     void InsertEmptyBytecodeRegion(FrameStateBuilder::LoopInfo& loopInfo,
1129         BytecodeRegion& loopHeader, size_t numOfEntries)
1130     {
1131         auto size = bcBuilder_->GetBasicBlockCount();
1132         auto block = chunk_->New<BytecodeRegion>(chunk_);
1133         block->id = size;
1134         block->numOfStatePreds = numOfEntries;
1135         block->start = loopHeader.start;
1136         ASSERT(loopHeader.start != 0);
1137         block->end = BytecodeIterator::INVALID_INDEX;
1138         block->bytecodeIterator_.Reset(bcBuilder_, block->start, block->end);
1139 
1140         frameBuilder_->liveOutResult_->Reset();
1141         for (auto it = loopHeader.preds.begin(); it != loopHeader.preds.end();) {
1142             auto bbPred = *it;
1143             // not loop back
1144             if (!loopInfo.loopBodys->TestBit(bbPred->id)) {
1145                 it = loopHeader.preds.erase(it);
1146                 std::replace(bbPred->succs.begin(), bbPred->succs.end(), &loopHeader, block);
1147                 block->preds.emplace_back(bbPred);
1148             } else {
1149                 it++;
1150             }
1151         }
1152         frameBuilder_->MergeFromSuccBB(loopHeader.id);
1153         block->succs.emplace_back(&loopHeader);
1154         loopHeader.preds.insert(loopHeader.preds.begin(), block);
1155         frameBuilder_->AddEmptyBlock(block);
1156 
1157         ASSERT(loopHeader.trys.empty() && numOfEntries > 0);
1158         loopHeader.numOfStatePreds -= (numOfEntries - 1); // 1: one entry
1159         auto it = std::find(frameBuilder_->rpoList_.begin(), frameBuilder_->rpoList_.end(), loopHeader.id);
1160         ASSERT(it != frameBuilder_->rpoList_.end());
1161         frameBuilder_->rpoList_.insert(it, block->id);
1162         visitState_.emplace_back(MarkState::UNVISITED1);
1163     }
1164 
TryMergeLoopEntry()1165     void TryMergeLoopEntry()
1166     {
1167         for (size_t i = 0; i < numLoops_; i++) {
1168             auto& loopInfo = frameBuilder_->loops_[i];
1169             auto& loopHeader = bcBuilder_->GetBasicBlockById(loopInfo.loopHeadId);
1170             ASSERT(loopHeader.numOfStatePreds > loopInfo.numLoopBacks);
1171             size_t numOfEntries = static_cast<size_t>(loopHeader.numOfStatePreds - loopInfo.numLoopBacks);
1172             if (numOfEntries > 1 && loopHeader.trys.size() == 0) {
1173                 InsertEmptyBytecodeRegion(loopInfo, loopHeader, numOfEntries);
1174             }
1175             // clear loopback bits for visit body
1176             loopInfo.loopBodys->Reset();
1177             loopInfo.loopBodys->SetBit(loopInfo.loopHeadId);
1178         }
1179     }
1180 
ResizeLoopBody()1181     void ResizeLoopBody()
1182     {
1183         for (auto& info : loopbacks_) {
1184             auto size = bcBuilder_->GetBasicBlockCount();
1185             auto& toBlock = bcBuilder_->GetBasicBlockById(info.toId);
1186             auto& loopInfo = frameBuilder_->GetLoopInfo(toBlock);
1187             if (loopInfo.loopBodys->ShouldExpand(size)) {
1188                 auto tmp = loopInfo.loopBodys;
1189                 loopInfo.loopBodys = chunk_->New<BitSet>(chunk_, size);
1190                 loopInfo.loopBodys->CopyDataFrom(*tmp);
1191             }
1192         }
1193     }
1194 
EnterInnerLoop(FrameStateBuilder::LoopInfo* loopInfo, size_t bbId)1195     FrameStateBuilder::LoopInfo* EnterInnerLoop(FrameStateBuilder::LoopInfo* loopInfo, size_t bbId)
1196     {
1197         auto &bb = bcBuilder_->GetBasicBlockById(bbId);
1198         if (bb.loopNumber > 0) {
1199             auto &innerInfo = frameBuilder_->GetLoopInfo(bb);
1200             ASSERT(innerInfo.parentInfo == nullptr);
1201             innerInfo.parentInfo = loopInfo;
1202             innerInfo.sortIndx = frameBuilder_->sortIndx_++;
1203             loopInfo = &innerInfo;
1204         } else if (loopInfo != nullptr) {
1205             bb.loopIndex = loopInfo->loopIndex;
1206         }
1207         return loopInfo;
1208     }
1209 
ComputeLoopTree()1210     void ComputeLoopTree()
1211     {
1212         FrameStateBuilder::LoopInfo* loopInfo = nullptr;
1213         auto currentDepth = Push(0, 0); // entry id
1214         while (currentDepth > 0) {
1215             auto &curState = dfsStack_[currentDepth - 1]; // -1: for current
1216             auto const &bb = bcBuilder_->GetBasicBlockById(curState.bbId);
1217             if (!bcBuilder_->IsOSR()) {
1218                 ASSERT(bb.catches.empty());
1219             }
1220             auto index = curState.index;
1221             BytecodeRegion* bbNext = nullptr;
1222             if (index >= bb.succs.size()) {
1223                 if (bb.loopNumber > 0) {
1224                     if (visitState_[curState.bbId] == MarkState::ON_STACK) {
1225                         if (loopInfo == nullptr) {
1226                             continue;
1227                         }
1228                         ASSERT(loopInfo->loopHeadId == curState.bbId);
1229                         loopInfo = loopInfo->parentInfo;
1230                         visitState_[curState.bbId] = MarkState::VISITED1;
1231                     }
1232                     bbNext = PushLoopExist(bb, currentDepth);
1233                 }
1234             } else {
1235                 bbNext = bb.succs[curState.index++]; // 1: goto next
1236             }
1237             if (bbNext != nullptr) {
1238                 if (loopInfo != nullptr && !loopInfo->loopBodys->TestBit(bbNext->id)) {
1239                     AddLoopExit(bbNext, loopInfo);
1240                 } else if (visitState_[bbNext->id] == MarkState::UNVISITED1) {
1241                     currentDepth = Push(bbNext->id, currentDepth);
1242                     loopInfo = EnterInnerLoop(loopInfo, bbNext->id);
1243                 }
1244             } else {
1245                 if (bb.loopNumber == 0) {
1246                     visitState_[curState.bbId] = MarkState::VISITED1;
1247                 }
1248                 currentDepth--;
1249             }
1250         }
1251     }
1252 
Push(size_t bbId, size_t depth)1253     size_t Push(size_t bbId, size_t depth)
1254     {
1255         if (visitState_[bbId] == MarkState::UNVISITED1) {
1256             dfsStack_[depth].bbId = bbId;
1257             dfsStack_[depth].index = 0;
1258             visitState_[bbId] = MarkState::ON_STACK;
1259             return depth + 1;
1260         }
1261         return depth;
1262     }
1263 
PushLoopExist(const BytecodeRegion& bb, size_t depth)1264     BytecodeRegion* PushLoopExist(const BytecodeRegion& bb, size_t depth)
1265     {
1266         ASSERT(depth > 0);
1267         auto &curState = dfsStack_[depth - 1]; // -1: for current
1268         auto loopExitIndex = curState.index - bb.succs.size();
1269         auto& currentInfo = frameBuilder_->GetLoopInfo(bb);
1270         BytecodeRegion* bbNext = nullptr;
1271         if (currentInfo.loopExits != nullptr && loopExitIndex < currentInfo.loopExits->size()) {
1272             bbNext = currentInfo.loopExits->at(loopExitIndex);
1273             curState.index++; // 1: goto next
1274         }
1275         return bbNext;
1276     }
1277 
AddLoopExit(BytecodeRegion *bb, FrameStateBuilder::LoopInfo *loopInfo)1278     void AddLoopExit(BytecodeRegion *bb, FrameStateBuilder::LoopInfo *loopInfo)
1279     {
1280         if (loopInfo->loopExits == nullptr) {
1281             loopInfo->loopExits = chunk_->New<ChunkVector<BytecodeRegion*>>(chunk_);
1282         }
1283         loopInfo->loopExits->emplace_back(bb);
1284     }
1285 
PrintLoop(FrameStateBuilder::LoopInfo& loopInfo)1286     void PrintLoop(FrameStateBuilder::LoopInfo& loopInfo)
1287     {
1288         auto size = bcBuilder_->GetBasicBlockCount();
1289         LOG_COMPILER(INFO) << "--------------------------------- LoopInfo Start ---------------------------------";
1290         LOG_COMPILER(INFO) << "LoopHead: " << loopInfo.loopHeadId;
1291         if (loopInfo.parentInfo != nullptr) {
1292             LOG_COMPILER(INFO) << "ParentLoopHead: " << loopInfo.parentInfo->loopHeadId;
1293         }
1294         std::string log = "Body: [";
1295         for (size_t i = 0; i < size; i++) {
1296             if (loopInfo.loopBodys->TestBit(i)) {
1297                 log += std::to_string(i) + ", ";
1298             }
1299         }
1300         LOG_COMPILER(INFO) << log << "]";
1301         std::string log1 = "Exit: [";
1302         if (loopInfo.loopExits != nullptr) {
1303             for (auto bb : *loopInfo.loopExits) {
1304                 log1 += std::to_string(bb->id) + ", ";
1305             }
1306         }
1307         LOG_COMPILER(INFO) << log1 << "]";
1308         std::string log2 = "LoopAssignment [";
1309         bool firset = true;
1310         for (size_t i = 0; i < frameBuilder_->numVregs_; i++) {
1311             if (loopInfo.loopAssignment->TestBit(i)) {
1312                 if (!firset) {
1313                     log2 += ",";
1314                 }
1315                 firset = false;
1316                 log2 += std::to_string(i);
1317             }
1318         }
1319         LOG_COMPILER(INFO) << log2 << "]";
1320         LOG_COMPILER(INFO) << "--------------------------------- LoopInfo End ---------------------------------";
1321     }
1322 
1323 private:
1324     struct EndToHead {
1325         size_t fromId;
1326         size_t toId;
1327     };
1328     struct DFSState {
DFSStatepanda::ecmascript::kungfu::BlockLoopAnalysis::DFSState1329         DFSState(size_t bbId, size_t index)
1330             : bbId(bbId), index(index) {}
1331 
1332         size_t bbId;
1333         size_t index;
1334     };
1335     struct VisitedInfo {
1336         size_t needVisitIndex;
1337         bool isVisitedCatchBlock = false;
1338     };
1339     enum class MarkState : uint8_t {
1340         UNVISITED = 0,
1341         ON_STACK,
1342         PENDING,
1343         VISITED,
1344         VISITED1,
1345         UNVISITED1 = VISITED
1346     };
1347     FrameStateBuilder* frameBuilder_ {nullptr};
1348     BytecodeCircuitBuilder *bcBuilder_ {nullptr};
1349     ChunkDeque<size_t> pendingList_;
1350     ChunkVector<EndToHead> loopbacks_;
1351     ChunkVector<DFSState> dfsStack_;
1352     ChunkVector<MarkState> visitState_;
1353     Chunk* chunk_ {nullptr};
1354     size_t numLoops_ {0};
1355     std::vector<VisitedInfo> visitedInfo_;
1356 };
1357 
ComputeLoopInfo()1358 void FrameStateBuilder::ComputeLoopInfo()
1359 {
1360     BlockLoopAnalysis loopAnalysis(this, circuit_->chunk());
1361     loopAnalysis.Run();
1362     if (numLoops_ != 0 && !bcBuilder_->HasIrreducibleLoop()) {
1363         ChunkVector<GateRef>& headerGates = bcBuilder_->GetLoopHeaderGates();
1364         headerGates.resize(numLoops_, Circuit::NullGate());
1365     }
1366 }
1367 
DumpLiveState()1368 void FrameStateBuilder::DumpLiveState()
1369 {
1370     LOG_COMPILER(INFO) << "DumpLiveState";
1371     for (size_t i = 0; i < bcEndStateLiveouts_.size(); i++) {
1372         auto liveout = GetFrameLiveoutAfter(i);
1373         if (liveout == nullptr) {
1374             continue;
1375         }
1376         std::string log = "BC: " + std::to_string(i) + " {";
1377         bool firset = true;
1378         for (size_t j = 0; j < numVregs_; j++) {
1379             if (liveout->TestBit(j)) {
1380                 if (!firset) {
1381                     log += ",";
1382                 }
1383                 firset = false;
1384                 log += std::to_string(j);
1385             }
1386         }
1387         log += "}";
1388         LOG_COMPILER(INFO) << log;
1389     }
1390     for (size_t i = 1; i < bbBeginStateLiveouts_.size(); i++) { // 1: skip entry
1391         auto liveout = GetFrameLiveoutBefore(i);
1392         if (liveout == nullptr) {
1393             continue;
1394         }
1395         std::string log = "BB: " + std::to_string(i) + " {";
1396         bool firset = true;
1397         for (size_t j = 0; j < numVregs_; j++) {
1398             if (liveout->TestBit(j)) {
1399                 if (!firset) {
1400                     log += ",";
1401                 }
1402                 firset = false;
1403                 log += std::to_string(j);
1404             }
1405         }
1406         log += "}";
1407         LOG_COMPILER(INFO) << log;
1408     }
1409 }
1410 
BuildFrameState(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex)1411 GateRef FrameStateBuilder::BuildFrameState(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex)
1412 {
1413     auto pcOffset = bcBuilder_->GetPcOffset(bcIndex);
1414     GateRef gateValues = BuildFrameValues(frameContext, liveout);
1415 
1416     GateRef frameArgs = bcBuilder_->GetFrameArgs();
1417     GateRef preFrameState = bcBuilder_->GetPreFrameState();
1418     UInt32PairAccessor accessor(static_cast<uint32_t>(pcOffset),
1419         FrameStateOutput::Invalid().GetValue());
1420     auto frameState = circuit_->NewGate(circuit_->FrameState(accessor.ToValue()),
1421         {frameArgs, gateValues, preFrameState});
1422     return frameState;
1423 }
1424 
BuildStateSplit(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex)1425 GateRef FrameStateBuilder::BuildStateSplit(FrameContext* frameContext, FrameLiveOut* liveout, size_t bcIndex)
1426 {
1427     auto frameState = BuildFrameState(frameContext, liveout, bcIndex);
1428     auto state = frameContext->currentState_;
1429     auto depend = frameContext->currentDepend_;
1430     ASSERT(IsGateNotEmpty(state));
1431     ASSERT(IsGateNotEmpty(depend));
1432     return circuit_->NewGate(circuit_->StateSplit(), {state, depend, frameState});
1433 }
1434 
BindStateSplitBefore(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId)1435 void FrameStateBuilder::BindStateSplitBefore(const BytecodeInfo &bytecodeInfo, FrameLiveOut* liveout, uint32_t bcId)
1436 {
1437     if (!bcBuilder_->IsTypeLoweringEnabled()) {
1438         return;
1439     }
1440     if (bytecodeInfo.IsCall() || bytecodeInfo.IsAccessorBC()) {
1441         frameStateCache_ = BuildFrameState(liveContext_, liveout, bcId);
1442     }
1443     ASSERT(!liveContext_->needStateSplit_);
1444 }
1445 
BindStateSplitAfter(const BytecodeInfo &bytecodeInfo, uint32_t bcId, GateRef gate)1446 void FrameStateBuilder::BindStateSplitAfter(const BytecodeInfo &bytecodeInfo,
1447     uint32_t bcId, GateRef gate)
1448 {
1449     if (!bcBuilder_->IsTypeLoweringEnabled()) {
1450         return;
1451     }
1452     if (bytecodeInfo.IsCall() || bytecodeInfo.IsAccessorBC()) {
1453         auto frameState = GetBcFrameStateCache();
1454         acc_.ReplaceFrameStateIn(gate, frameState);
1455     }
1456     if (!bytecodeInfo.NoSideEffects() && !bytecodeInfo.IsThrow()) {
1457         auto stateSplit = BuildStateSplit(liveContext_, GetOrOCreateBCEndLiveOut(bcId), bcId + 1); // 1: for after
1458         liveContext_->currentDepend_ = stateSplit;
1459     }
1460 }
1461 
BuildFrameValues(FrameContext* frameContext, FrameLiveOut* liveout)1462 GateRef FrameStateBuilder::BuildFrameValues(FrameContext* frameContext, FrameLiveOut* liveout)
1463 {
1464     size_t frameStateInputs = numVregs_;
1465     std::vector<GateRef> inList(frameStateInputs, Circuit::NullGate());
1466     auto optimizedGate = circuit_->GetConstantGate(MachineType::I64,
1467                                                    JSTaggedValue::VALUE_OPTIMIZED_OUT,
1468                                                    GateType::TaggedValue());
1469     for (size_t i = 0; i < numVregs_; i++) {
1470         auto value = frameContext->ValuesAt(i);
1471         if (!IsGateNotEmpty(value) || !liveout->TestBit(i)) {
1472             value = optimizedGate;
1473         }
1474         inList[i] = value;
1475     }
1476     return circuit_->NewGate(circuit_->FrameValues(frameStateInputs), inList);
1477 }
1478 }
1479