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
21namespace panda::ecmascript::kungfu {
22FrameStateBuilder::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
40FrameStateBuilder::~FrameStateBuilder()
41{
42    liveOutResult_ = nullptr;
43    bcEndStateLiveouts_.clear();
44    bbBeginStateLiveouts_.clear();
45    bbFrameContext_.clear();
46    bcBuilder_ = nullptr;
47}
48
49void 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
88bool 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
96bool FrameStateBuilder::MergeFromSuccBB(size_t bbId)
97{
98    // liveout next
99    auto liveout = GetOrOCreateBBLiveOut(bbId);
100    return liveOutResult_->MergeLiveout(liveout);
101}
102
103void 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
115bool 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
155void 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
167void 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
184void 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
212FrameLiveOut *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
223FrameLiveOut *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
242FrameContext *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
256void 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
284void 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
310void FrameStateBuilder::UpdateStateDepend(GateRef state, GateRef depend)
311{
312    liveContext_->currentState_ = state;
313    liveContext_->currentDepend_ = depend;
314}
315
316void 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
334void 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
367void 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
378bool 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
395bool 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
411size_t FrameStateBuilder::GetOsrLoopHeadBBId() const
412{
413    if (loopHeadOfOSR_ == nullptr) {
414        return -1;
415    }
416    return loopHeadOfOSR_->id;
417}
418
419void 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
470bool FrameStateBuilder::IsLoopHead(const BytecodeRegion &bb)
471{
472    return !(bcBuilder_->IsOSR() && OutOfOsrLoop(bb)) && bb.loopNumber > 0;
473}
474
475bool FrameStateBuilder::IfLoopNeedMerge(const BytecodeRegion &bb) const
476{
477    return !bcBuilder_->IsOSR() && bb.numOfStatePreds - bb.numOfLoopBack != 1; // 1: loop in
478}
479
480GateRef 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
486bool FrameStateBuilder::IsGateNotEmpty(GateRef gate) const
487{
488    return gate != Circuit::NullGate();
489}
490
491void 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
553void 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
580size_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
595GateRef 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
667MergeStateDependInfo 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
688void 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
719void 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
733FrameContext *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
751void 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
760void 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
789void 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
819void 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
841class SubContextScope {
842public:
843    explicit SubContextScope(FrameStateBuilder* frameBuilder)
844        : frameBuilder_(frameBuilder)
845    {
846        originContext_ = frameBuilder->liveContext_;
847    }
848
849    ~SubContextScope()
850    {
851        frameBuilder_->liveContext_ = originContext_;
852    }
853private:
854    FrameContext* originContext_ {nullptr};
855    FrameStateBuilder* frameBuilder_ {nullptr};
856};
857
858void 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
883bool 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
894FrameStateBuilder::LoopInfo& FrameStateBuilder::GetLoopInfo(const BytecodeRegion &bb)
895{
896    ASSERT(bb.loopNumber > 0);
897    return loops_[bb.loopNumber - 1]; // -1: for index
898}
899
900FrameStateBuilder::LoopInfo& FrameStateBuilder::GetLoopInfo(BytecodeRegion &bb)
901{
902    ASSERT(bb.loopNumber > 0);
903    return loops_[bb.loopNumber - 1]; // -1: for index
904}
905
906FrameStateBuilder::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
916BitSet *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
925void 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
935class BlockLoopAnalysis {
936public:
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1323private:
1324    struct EndToHead {
1325        size_t fromId;
1326        size_t toId;
1327    };
1328    struct DFSState {
1329        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
1358void 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
1368void 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
1411GateRef 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
1425GateRef 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
1435void 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
1446void 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
1462GateRef 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