OpenHarmony-v4.0-Release/s

/*
 * Copyright (c) 2021 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "ecmascript/compiler/bytecode_circuit_builder.h"

#include "ecmascript/base/number_helper.h"
#include "ecmascript/compiler/gate_accessor.h"
#include "ecmascript/ts_types/ts_manager.h"
#include "libpandafile/bytecode_instruction-inl.h"

namespace panda::ecmascript::kungfu {
void BytecodeCircuitBuilder::BytecodeToCircuit()
{
    ExceptionInfo exceptionInfo = {};

    // collect try catch block info
    CollectTryCatchBlockInfo(exceptionInfo);
    hasTryCatch_ = exceptionInfo.size() != 0;
    BuildRegionInfo();
    // Building the basic block diagram of bytecode
    BuildRegions(exceptionInfo);
}

void BytecodeCircuitBuilder::BuildRegionInfo()
{
    uint32_t size = pcOffsets_.size();
    uint32_t end = size - 2;  // 1: end
    BytecodeIterator iterator(this, 0, end);

    infoData_.resize(size);
    byteCodeToJSGates_.resize(size, std::vector<GateRef>(0));
    regionsInfo_.InsertHead(0); // 0: start pc
    for (iterator.GotoStart(); !iterator.Done(); ++iterator) {
        auto index = iterator.Index();
        auto &info = infoData_[index];
        auto pc = pcOffsets_[index];
        info.metaData_ = bytecodes_->GetBytecodeMetaData(pc);
        ASSERT(!info.metaData_.IsInvalid());
        BytecodeInfo::InitBytecodeInfo(this, info, pc);
        CollectRegionInfo(index);
    }
}

void BytecodeCircuitBuilder::CollectRegionInfo(uint32_t bcIndex)
{
    auto pc = pcOffsets_[bcIndex];
    auto &info = infoData_[bcIndex];
    int32_t offset = 0;
    if (info.IsJump()) {
        switch (info.GetOpcode()) {
            case EcmaOpcode::JEQZ_IMM8:
            case EcmaOpcode::JNEZ_IMM8:
            case EcmaOpcode::JMP_IMM8:
                offset = static_cast<int8_t>(READ_INST_8_0());
                break;
            case EcmaOpcode::JNEZ_IMM16:
            case EcmaOpcode::JEQZ_IMM16:
            case EcmaOpcode::JMP_IMM16:
                offset = static_cast<int16_t>(READ_INST_16_0());
                break;
            case EcmaOpcode::JMP_IMM32:
            case EcmaOpcode::JNEZ_IMM32:
            case EcmaOpcode::JEQZ_IMM32:
                offset = static_cast<int32_t>(READ_INST_32_0());
                break;
            default:
                LOG_ECMA(FATAL) << "this branch is unreachable";
                UNREACHABLE();
                break;
        }
        auto nextIndex = bcIndex + 1; // 1: next pc
        auto targetIndex = FindBcIndexByPc(pc + offset);
        // condition branch current basic block end
        if (info.IsCondJump()) {
            regionsInfo_.InsertSplit(nextIndex);
            regionsInfo_.InsertJump(targetIndex, bcIndex, false);
        } else {
            if (bcIndex != GetLastBcIndex()) {
                regionsInfo_.InsertHead(nextIndex);
            }
            regionsInfo_.InsertJump(targetIndex, bcIndex, true);
        }
    } else if (info.IsReturn() || info.IsThrow()) {
        if (bcIndex != GetLastBcIndex()) {
            auto nextIndex = bcIndex + 1; // 1: next pc
            regionsInfo_.InsertHead(nextIndex);
        }
    }
}

void BytecodeCircuitBuilder::CollectTryCatchBlockInfo(ExceptionInfo &byteCodeException)
{
    auto pf = file_->GetPandaFile();
    panda_file::MethodDataAccessor mda(*pf, method_->GetMethodId());
    panda_file::CodeDataAccessor cda(*pf, mda.GetCodeId().value());

    cda.EnumerateTryBlocks([this, &byteCodeException](
        panda_file::CodeDataAccessor::TryBlock &tryBlock) {
        auto tryStartOffset = tryBlock.GetStartPc();
        auto tryEndOffset = tryBlock.GetStartPc() + tryBlock.GetLength();

        auto tryStartPc = const_cast<uint8_t *>(method_->GetBytecodeArray() + tryStartOffset);
        auto tryEndPc = const_cast<uint8_t *>(method_->GetBytecodeArray() + tryEndOffset);
        // skip try blocks with same pc in start and end label
        if (tryStartPc == tryEndPc) {
            return true;
        }

        auto tryStartBcIndex = FindBcIndexByPc(tryStartPc);
        regionsInfo_.InsertSplit(tryStartBcIndex);
        if (tryEndPc <= GetLastPC()) {
            auto tryEndBcIndex = FindBcIndexByPc(tryEndPc);
            regionsInfo_.InsertSplit(tryEndBcIndex);
        }
        byteCodeException.emplace_back(ExceptionItem { tryStartPc, tryEndPc, {} });
        tryBlock.EnumerateCatchBlocks([&](panda_file::CodeDataAccessor::CatchBlock &catchBlock) {
            auto pcOffset = catchBlock.GetHandlerPc();
            auto catchBlockPc = const_cast<uint8_t *>(method_->GetBytecodeArray() + pcOffset);
            auto catchBlockBcIndex = FindBcIndexByPc(catchBlockPc);
            regionsInfo_.InsertHead(catchBlockBcIndex);
            // try block associate catch block
            byteCodeException.back().catchs.emplace_back(catchBlockPc);
            return true;
        });
        return true;
    });
}

void BytecodeCircuitBuilder::BuildEntryBlock()
{
    BytecodeRegion &entryBlock = graph_[0];
    BytecodeRegion &nextBlock = graph_[1];
    entryBlock.succs.emplace_back(&nextBlock);
    nextBlock.preds.emplace_back(&entryBlock);
    entryBlock.bytecodeIterator_.Reset(this, INVALID_INDEX, INVALID_INDEX);
}

void BytecodeCircuitBuilder::BuildRegions(const ExceptionInfo &byteCodeException)
{
    auto &items = regionsInfo_.GetBlockItems();
    auto blockSize = items.size();

    // 1 : entry block. if the loop head is in the first bb block, the variables used in the head cannot correctly
    // generate Phi nodes through the dominator-tree algorithm, resulting in an infinite loop. Therefore, an empty
    // BB block is generated as an entry block
    graph_.resize(blockSize + 1);

    // build entry block
    BuildEntryBlock();

    // build basic block
    size_t blockId = 1;
    for (const auto &item : items) {
        auto &curBlock = GetBasicBlockById(blockId);
        curBlock.id = blockId;
        curBlock.start = item.GetStartBcIndex();
        if (blockId != 1) {
            auto &prevBlock = graph_[blockId - 1];
            prevBlock.end = curBlock.start - 1;
            prevBlock.bytecodeIterator_.Reset(this, prevBlock.start, prevBlock.end);
            // fall through
            if (!item.IsHeadBlock()) {
                curBlock.preds.emplace_back(&prevBlock);
                prevBlock.succs.emplace_back(&curBlock);
            }
        }
        blockId++;
    }
    auto &lastBlock = graph_[blockId - 1]; // 1: last block
    lastBlock.end = GetLastBcIndex();
    lastBlock.bytecodeIterator_.Reset(this, lastBlock.start, lastBlock.end);

    auto &splitItems = regionsInfo_.GetSplitItems();
    for (const auto &item : splitItems) {
        auto curIndex = regionsInfo_.FindBBIndexByBcIndex(item.startBcIndex);
        auto &curBlock = GetBasicBlockById(curIndex);
        auto predIndex = regionsInfo_.FindBBIndexByBcIndex(item.predBcIndex);
        auto &predBlock = GetBasicBlockById(predIndex);
        curBlock.preds.emplace_back(&predBlock);
        predBlock.succs.emplace_back(&curBlock);
    }

    if (byteCodeException.size() != 0) {
        BuildCatchBlocks(byteCodeException);
    }
    if (IsLogEnabled()) {
        PrintGraph("Build Basic Block");
    }
    ComputeDominatorTree();
}

void BytecodeCircuitBuilder::BuildCatchBlocks(const ExceptionInfo &byteCodeException)
{
    // try catch block associate
    for (size_t i = 0; i < graph_.size(); i++) {
        auto &bb = graph_[i];
        auto startIndex = bb.start;
        const auto pc = pcOffsets_[startIndex];
        for (auto it = byteCodeException.cbegin(); it != byteCodeException.cend(); it++) {
            if (pc < it->startPc || pc >= it->endPc) {
                continue;
            }
            // try block interval
            const auto &catchs = it->catchs; // catchs start pc
            for (size_t j = i + 1; j < graph_.size(); j++) {
                auto &catchBB = graph_[j];
                const auto catchStart = pcOffsets_[catchBB.start];
                if (std::find(catchs.cbegin(), catchs.cend(), catchStart) != catchs.cend()) {
                    bb.catchs.insert(bb.catchs.cbegin(), &catchBB);
                    bb.succs.emplace_back(&catchBB);
                    catchBB.preds.emplace_back(&bb);
                }
            }
        }

        // When there are multiple catch blocks in the current block, the set of catch blocks
        // needs to be sorted to satisfy the order of execution of catch blocks.
        bb.SortCatches();
    }
}

void BytecodeCircuitBuilder::ComputeDominatorTree()
{
    // Construct graph backward order
    std::unordered_map<size_t, size_t> bbIdToDfsTimestamp;
    std::unordered_map<size_t, size_t> dfsFatherIdx;
    std::unordered_map<size_t, size_t> bbDfsTimestampToIdx;
    std::vector<size_t> basicBlockList;
    size_t timestamp = 0;
    std::deque<size_t> pendingList;
    std::vector<size_t> visited(graph_.size(), 0);
    auto basicBlockId = graph_[0].id;
    visited[graph_[0].id] = 1;
    pendingList.emplace_back(basicBlockId);
    while (!pendingList.empty()) {
        size_t curBlockId = pendingList.back();
        pendingList.pop_back();
        basicBlockList.emplace_back(curBlockId);
        bbIdToDfsTimestamp[curBlockId] = timestamp++;
        for (const auto &succBlock: graph_[curBlockId].succs) {
            if (visited[succBlock->id] == 0) {
                visited[succBlock->id] = 1;
                pendingList.emplace_back(succBlock->id);
                dfsFatherIdx[succBlock->id] = bbIdToDfsTimestamp[curBlockId];
            }
        }
    }

    for (size_t idx = 0; idx < basicBlockList.size(); idx++) {
        bbDfsTimestampToIdx[basicBlockList[idx]] = idx;
    }
    RemoveDeadRegions(bbIdToDfsTimestamp);

    std::vector<size_t> immDom(basicBlockList.size()); // immediate dominator with dfs order index
    std::vector<size_t> semiDom(basicBlockList.size());
    std::vector<size_t> realImmDom(graph_.size()); // immediate dominator with real index
    std::vector<std::vector<size_t> > semiDomTree(basicBlockList.size());
    {
        std::vector<size_t> parent(basicBlockList.size());
        std::iota(parent.begin(), parent.end(), 0);
        std::vector<size_t> minIdx(basicBlockList.size());
        std::function<size_t(size_t)> unionFind = [&] (size_t idx) -> size_t {
            if (parent[idx] == idx) return idx;
            size_t unionFindSetRoot = unionFind(parent[idx]);
            if (semiDom[minIdx[idx]] > semiDom[minIdx[parent[idx]]]) {
                minIdx[idx] = minIdx[parent[idx]];
            }
            return parent[idx] = unionFindSetRoot;
        };
        auto merge = [&] (size_t fatherIdx, size_t sonIdx) -> void {
            size_t parentFatherIdx = unionFind(fatherIdx);
            size_t parentSonIdx = unionFind(sonIdx);
            parent[parentSonIdx] = parentFatherIdx;
        };
        std::iota(semiDom.begin(), semiDom.end(), 0);
        semiDom[0] = semiDom.size();
        for (size_t idx = basicBlockList.size() - 1; idx >= 1; idx--) {
            for (const auto &preBlock : graph_[basicBlockList[idx]].preds) {
                if (bbDfsTimestampToIdx[preBlock->id] < idx) {
                    semiDom[idx] = std::min(semiDom[idx], bbDfsTimestampToIdx[preBlock->id]);
                } else {
                    unionFind(bbDfsTimestampToIdx[preBlock->id]);
                    semiDom[idx] = std::min(semiDom[idx], semiDom[minIdx[bbDfsTimestampToIdx[preBlock->id]]]);
                }
            }
            for (const auto & succDomIdx : semiDomTree[idx]) {
                unionFind(succDomIdx);
                if (idx == semiDom[minIdx[succDomIdx]]) {
                    immDom[succDomIdx] = idx;
                } else {
                    immDom[succDomIdx] = minIdx[succDomIdx];
                }
            }
            minIdx[idx] = idx;
            merge(dfsFatherIdx[basicBlockList[idx]], idx);
            semiDomTree[semiDom[idx]].emplace_back(idx);
        }
        for (size_t idx = 1; idx < basicBlockList.size(); idx++) {
            if (immDom[idx] != semiDom[idx]) {
                immDom[idx] = immDom[immDom[idx]];
            }
            realImmDom[basicBlockList[idx]] = basicBlockList[immDom[idx]];
        }
        semiDom[0] = 0;
    }

    if (IsLogEnabled()) {
        PrintGraph("Computed Dom Trees");
    }

    BuildImmediateDominator(realImmDom);
}

void BytecodeCircuitBuilder::BuildImmediateDominator(const std::vector<size_t> &immDom)
{
    graph_[0].iDominator = &graph_[0];
    for (size_t i = 1; i < immDom.size(); i++) {
        auto dominatedBlock = &graph_[i];
        if (dominatedBlock->isDead) {
            continue;
        }
        auto immDomBlock = &graph_[immDom[i]];
        dominatedBlock->iDominator = immDomBlock;
    }

    for (auto &block : graph_) {
        if (block.isDead) {
            continue;
        }
        if (block.iDominator->id != block.id) {
            block.iDominator->immDomBlocks.emplace_back(&block);
        }
    }

    ComputeDomFrontiers(immDom);
    InsertPhi();
    UpdateCFG();
    BuildCircuit();
}

void BytecodeCircuitBuilder::ComputeDomFrontiers(const std::vector<size_t> &immDom)
{
    std::vector<std::set<BytecodeRegion *>> domFrontiers(immDom.size());
    for (auto &bb : graph_) {
        if (bb.isDead) {
            continue;
        }
        if (bb.preds.size() < 2) { // 2: pred num
            continue;
        }
        for (size_t i = 0; i < bb.preds.size(); i++) {
            auto runner = bb.preds[i];
            while (runner->id != immDom[bb.id]) {
                domFrontiers[runner->id].insert(&bb);
                runner = &graph_[immDom[runner->id]];
            }
        }
    }

    for (size_t i = 0; i < domFrontiers.size(); i++) {
        for (auto iter = domFrontiers[i].cbegin(); iter != domFrontiers[i].cend(); iter++) {
            graph_[i].domFrontiers.emplace_back(*iter);
        }
    }
}

void BytecodeCircuitBuilder::RemoveDeadRegions(const std::unordered_map<size_t, size_t> &bbIdToDfsTimestamp)
{
    for (auto &block: graph_) {
        std::vector<BytecodeRegion *> newPreds;
        for (auto &bb : block.preds) {
            if (bbIdToDfsTimestamp.count(bb->id)) {
                newPreds.emplace_back(bb);
            }
        }
        block.preds = newPreds;
    }

    for (auto &block : graph_) {
        block.isDead = !bbIdToDfsTimestamp.count(block.id);
        if (block.isDead) {
            block.succs.clear();
        }
    }
}

void BytecodeCircuitBuilder::InsertPhi()
{
    std::unordered_map<uint16_t, std::set<size_t>> defsitesInfo; // <vreg, bbs>
    for (auto &bb : graph_) {
        if (bb.isDead) {
            continue;
        }
        EnumerateBlock(bb, [this, &defsitesInfo, &bb]
            (const BytecodeInfo &bytecodeInfo) -> bool {
            if (bytecodeInfo.IsBc(EcmaOpcode::RESUMEGENERATOR)) {
                auto numVRegs = GetNumberVRegsWithEnv();
                for (size_t i = 0; i < numVRegs; i++) {
                    defsitesInfo[i].insert(bb.id);
                }
            }
            for (const auto &vreg: bytecodeInfo.vregOut) {
                defsitesInfo[vreg].insert(bb.id);
            }
            return true;
        });
    }

    // handle phi generated from multiple control flow in the same source block
    InsertExceptionPhi(defsitesInfo);

    for (const auto&[variable, defsites] : defsitesInfo) {
        std::queue<uint16_t> workList;
        for (auto blockId: defsites) {
            workList.push(blockId);
        }
        while (!workList.empty()) {
            auto currentId = workList.front();
            workList.pop();
            for (auto &block : graph_[currentId].domFrontiers) {
                if (!block->phi.count(variable)) {
                    block->phi.insert(variable);
                    if (!defsitesInfo[variable].count(block->id)) {
                        workList.push(block->id);
                    }
                }
            }
        }
    }

    if (IsLogEnabled()) {
        PrintGraph("Inserted Phis");
    }
}

void BytecodeCircuitBuilder::InsertExceptionPhi(std::unordered_map<uint16_t, std::set<size_t>> &defsitesInfo)
{
    // handle try catch defsite
    for (auto &bb : graph_) {
        if (bb.isDead) {
            continue;
        }
        if (bb.catchs.size() == 0) {
            continue;
        }
        std::set<size_t> vregs;
        EnumerateBlock(bb, [this, &vregs]
        (const BytecodeInfo &bytecodeInfo) -> bool {
            if (bytecodeInfo.IsBc(EcmaOpcode::RESUMEGENERATOR)) {
                auto numVRegs = GetNumberVRegsWithEnv();
                for (size_t i = 0; i < numVRegs; i++) {
                    vregs.insert(i);
                }
                return false;
            }
            for (const auto &vreg: bytecodeInfo.vregOut) {
                vregs.insert(vreg);
            }
            return true;
        });

        for (auto &vreg : vregs) {
            defsitesInfo[vreg].insert(bb.catchs.at(0)->id);
            bb.catchs.at(0)->phi.insert(vreg);
        }
    }
}

// Update CFG's predecessor, successor and try catch associations
void BytecodeCircuitBuilder::UpdateCFG()
{
    for (auto &bb: graph_) {
        if (bb.isDead) {
            continue;
        }
        bb.preds.clear();
        bb.trys.clear();
        std::vector<BytecodeRegion *> newSuccs;
        for (const auto &succ: bb.succs) {
            if (std::count(bb.catchs.cbegin(), bb.catchs.cend(), succ)) {
                continue;
            }
            newSuccs.emplace_back(succ);
        }
        bb.succs = newSuccs;
    }
    for (auto &bb: graph_) {
        if (bb.isDead) {
            continue;
        }
        for (auto &succ: bb.succs) {
            succ->preds.emplace_back(&bb);
        }
        for (auto &catchBlock: bb.catchs) {
            catchBlock->trys.emplace_back(&bb);
        }
    }
}

// build circuit
void BytecodeCircuitBuilder::BuildCircuitArgs()
{
    argAcc_.NewCommonArg(CommonArgIdx::GLUE, MachineType::I64, GateType::NJSValue());
    if (!method_->IsFastCall()) {
        argAcc_.NewCommonArg(CommonArgIdx::ACTUAL_ARGC, MachineType::I64, GateType::NJSValue());
        auto funcIdx = static_cast<size_t>(CommonArgIdx::FUNC);
        const size_t actualNumArgs = argAcc_.GetActualNumArgs();
        // new actual argument gates
        for (size_t argIdx = funcIdx; argIdx < actualNumArgs; argIdx++) {
            argAcc_.NewArg(argIdx);
        }
    } else {
        auto funcIdx = static_cast<size_t>(FastCallArgIdx::FUNC);
        size_t actualNumArgs = static_cast<size_t>(FastCallArgIdx::NUM_OF_ARGS) + method_->GetNumArgsWithCallField();
        for (size_t argIdx = funcIdx; argIdx < actualNumArgs; argIdx++) {
            argAcc_.NewArg(argIdx);
        }
    }
    argAcc_.CollectArgs();
    if (HasTypes()) {
        argAcc_.FillArgsGateType(&typeRecorder_);
    }

    BuildFrameArgs();
}

void BytecodeCircuitBuilder::BuildFrameArgs()
{
    auto metaData = circuit_->FrameArgs();
    size_t numArgs = static_cast<size_t>(FrameArgIdx::NUM_OF_ARGS);
    std::vector<GateRef> args(numArgs, Circuit::NullGate());
    size_t idx = 0;
    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::FUNC);
    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::NEW_TARGET);
    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::THIS_OBJECT);
    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::ACTUAL_ARGC);
    GateRef frameArgs = circuit_->NewGate(metaData, args);
    argAcc_.SetFrameArgs(frameArgs);
}

bool BytecodeCircuitBuilder::ShouldBeDead(BytecodeRegion &curBlock)
{
    if (curBlock.iDominator->isDead) {
        return true;
    }
    auto isDead = false;
    for (auto bbPred : curBlock.preds) {
        if (!bbPred->isDead) {
            return false;
        }
        isDead = true;
    }
    for (auto bbTry : curBlock.trys) {
        if (!bbTry->isDead) {
            return false;
        }
        isDead = true;
    }
    return isDead;
}

void BytecodeCircuitBuilder::CollectPredsInfo()
{
    for (auto &bb: graph_) {
        if (bb.isDead) {
            continue;
        }
        bb.numOfStatePreds = 0;
    }
    // get number of expanded state predicates of each block
    // one block-level try catch edge may correspond to multiple bytecode-level edges
    for (auto &bb: graph_) {
        if (bb.isDead) {
            continue;
        }
        if (ShouldBeDead(bb)) {
            bb.UpdateTryCatchInfoForDeadBlock();
            bb.isDead = true;
            continue;
        }
        bool noThrow = true;
        EnumerateBlock(bb, [&noThrow, &bb]
        (const BytecodeInfo &bytecodeInfo) -> bool {
            if (bytecodeInfo.IsGeneral()) {
                if (!bb.catchs.empty() && !bytecodeInfo.NoThrow()) {
                    noThrow = false;
                    bb.catchs.at(0)->numOfStatePreds++;
                }
            }
            if (bytecodeInfo.IsCondJump() && bb.succs.size() == 1) {
                ASSERT(bb.succs[0]->id == bb.id + 1);
                bb.succs[0]->numOfStatePreds++;
            }
            return true;
        });
        bb.UpdateRedundantTryCatchInfo(noThrow);
        bb.UpdateTryCatchInfoIfNoThrow(noThrow);
        for (auto &succ: bb.succs) {
            succ->numOfStatePreds++;
        }
    }

    CollectLoopBack();
    if (EnableLoopOptimization()) {
        for (auto &head : loopHeads_) {
            loopSize_ = 0;
            ComputeLoopDepth(head.second);
            head.first = loopSize_;
        }
        sort(loopHeads_.begin(), loopHeads_.end());
    }

    for (auto &bb: graph_) {
        if (bb.isDead) {
            continue;
        }
        bb.phiAcc = (bb.numOfStatePreds > 1) || (!bb.trys.empty());
    }
}

void BytecodeCircuitBuilder::NewMerge(GateRef &state, GateRef &depend, size_t numOfIns)
{
    state = circuit_->NewGate(circuit_->Merge(numOfIns),
                              std::vector<GateRef>(numOfIns, Circuit::NullGate()));
    depend = circuit_->NewGate(circuit_->DependSelector(numOfIns),
                               std::vector<GateRef>(numOfIns + 1, Circuit::NullGate()));
    gateAcc_.NewIn(depend, 0, state);
}

void BytecodeCircuitBuilder::NewLoopBegin(BytecodeRegion &bb, GateRef &state, GateRef &depend)
{
    if (bb.numOfLoopBacks > 1) {
        NewMerge(bb.loopBackStateMerge, bb.loopBackDependMerge, bb.numOfLoopBacks);
    }
    auto loopBack = circuit_->NewGate(circuit_->LoopBack(), { Circuit::NullGate() });
    auto loopBegin = circuit_->NewGate(circuit_->LoopBegin(), { Circuit::NullGate(), loopBack });
    // 2: the number of depend inputs and it is in accord with LOOP_BEGIN
    auto loopDepend = circuit_->NewGate(circuit_->DependSelector(2),
        { loopBegin, Circuit::NullGate(), Circuit::NullGate() });
    if (state == circuit_->GetStateRoot()) {
        ASSERT(depend == circuit_->GetDependRoot());
        gateAcc_.NewIn(loopBegin, 0, state);
        gateAcc_.NewIn(loopDepend, 1, depend);
    }
    state = loopBegin;
    depend = loopDepend;
}

void BytecodeCircuitBuilder::NewLoopExit(GateRef &state, GateRef &depend)
{
    auto loopExit = circuit_->NewGate(circuit_->LoopExit(),
        { state });
    depend = circuit_->NewGate(circuit_->LoopExitDepend(),
        { loopExit, depend });
    state = loopExit;
}

void BytecodeCircuitBuilder::TryInsertLoopExit(BytecodeRegion &bb, BytecodeRegion &bbNext,
                                               GateRef &state, GateRef &depend)
{
    size_t diff = LoopExitCount(bb.id, bbNext.id);
    for (size_t i = 0; i < diff; ++i) {
        NewLoopExit(state, depend);
    }
}

void BytecodeCircuitBuilder::BuildBlockCircuitHead(BytecodeRegion &bb, GateRef &state, GateRef &depend)
{
    auto mergeCount = bb.numOfStatePreds - bb.numOfLoopBacks;
    if (mergeCount == 0) {
        state = circuit_->GetStateRoot();
        depend = circuit_->GetDependRoot();
    }

    if (mergeCount > 1) {
        NewMerge(bb.stateMerge, bb.dependMerge, mergeCount);
        state = bb.stateMerge;
        depend = bb.dependMerge;
    }

    if (bb.numOfLoopBacks > 0) {
        NewLoopBegin(bb, state, depend);
    }
}

std::vector<GateRef> BytecodeCircuitBuilder::CreateGateInList(
    const BytecodeInfo &info, const GateMetaData *meta)
{
    auto numValues = meta->GetNumIns();
    const size_t length = meta->GetInValueStarts();
    std::vector<GateRef> inList(numValues, Circuit::NullGate());
    auto inputSize = info.inputs.size();
    for (size_t i = 0; i < inputSize; i++) {
        auto &input = info.inputs[i];
        if (std::holds_alternative<ConstDataId>(input)) {
            inList[i + length] = circuit_->GetConstantGate(MachineType::I64,
                                                           std::get<ConstDataId>(input).GetId(),
                                                           GateType::NJSValue());
        } else if (std::holds_alternative<Immediate>(input)) {
            inList[i + length] = circuit_->GetConstantGate(MachineType::I64,
                                                           std::get<Immediate>(input).GetValue(),
                                                           GateType::NJSValue());
        } else if (std::holds_alternative<ICSlotId>(input)) {
            inList[i + length] = circuit_->GetConstantGate(MachineType::I16,
                                                           std::get<ICSlotId>(input).GetId(),
                                                           GateType::NJSValue());
        } else {
            ASSERT(std::holds_alternative<VirtualRegister>(input));
            continue;
        }
    }
    if (info.AccIn()) {
        inputSize++;
    }
    if (meta->HasFrameState()) {
        inList[inputSize + length] = GetFrameArgs();
    }
    return inList;
}

void BytecodeCircuitBuilder::SetLoopBlockPred(BytecodeRegion &bb, BytecodeRegion &bbNext,
                                              GateRef &state, GateRef &depend)
{
    ASSERT(bbNext.numOfLoopBacks > 0);
    ASSERT(gateAcc_.GetOpCode(bbNext.stateCurrent) == OpCode::LOOP_BEGIN);
    ASSERT(gateAcc_.GetOpCode(bbNext.dependCurrent) == OpCode::DEPEND_SELECTOR);
    // loop back
    if (bbNext.loopbackBlocks.count(bb.id)) {
        if (bbNext.loopBackStateMerge != Circuit::NullGate()) {
            ASSERT(bbNext.loopBackDependMerge != Circuit::NullGate());
            gateAcc_.NewIn(bbNext.loopBackStateMerge, bbNext.loopBackIndex, state);
            gateAcc_.NewIn(bbNext.loopBackDependMerge, bbNext.loopBackIndex + 1, depend);
            state = bbNext.loopBackStateMerge;
            depend = bbNext.loopBackDependMerge;
        }
        if (bbNext.loopBackIndex == 0) {
            auto loopBack = gateAcc_.GetState(bbNext.stateCurrent, 1); // 1: LoopBack
            gateAcc_.NewIn(loopBack, 0, state);
            gateAcc_.NewIn(bbNext.dependCurrent, 2, depend); // 2: loopback depend
        }
        bbNext.loopBackIndex++;
        ASSERT(bbNext.loopBackIndex <= bbNext.numOfLoopBacks);
    } else {
        if (bbNext.stateMerge != Circuit::NullGate()) {
            ASSERT(bbNext.dependMerge != Circuit::NullGate());
            gateAcc_.NewIn(bbNext.stateMerge, bbNext.forwardIndex, state);
            gateAcc_.NewIn(bbNext.dependMerge, bbNext.forwardIndex + 1, depend);
            state = bbNext.stateMerge;
            depend = bbNext.dependMerge;
        }
        if (bbNext.forwardIndex == 0) {
            gateAcc_.NewIn(bbNext.stateCurrent, 0, state);
            gateAcc_.NewIn(bbNext.dependCurrent, 1, depend); // 1: first depend
        }
        bbNext.forwardIndex++;
        ASSERT(bbNext.forwardIndex <= bbNext.numOfStatePreds - bbNext.numOfLoopBacks);
    }
}

void BytecodeCircuitBuilder::SetBlockPred(BytecodeRegion &bb, BytecodeRegion &bbNext,
                                          const GateRef &state, const GateRef &depend)
{
    auto stateCur = state;
    auto dependCur = depend;

    if (EnableLoopOptimization()) {
        TryInsertLoopExit(bb, bbNext, stateCur, dependCur);
    }

    // Init block head if not exists
    if (bbNext.stateCurrent == Circuit::NullGate()) {
        ASSERT(bbNext.dependCurrent == Circuit::NullGate());
        BuildBlockCircuitHead(bbNext, bbNext.stateCurrent, bbNext.dependCurrent);
        // no loop head, no merge bb
        if (bbNext.stateCurrent == Circuit::NullGate()) {
            ASSERT(bbNext.dependCurrent == Circuit::NullGate());
            bbNext.stateCurrent = stateCur;
            bbNext.dependCurrent = dependCur;
            bbNext.statePredIndex++;
            return;
        }
    }

    // loop bb
    if (bbNext.numOfLoopBacks > 0) {
        SetLoopBlockPred(bb, bbNext, stateCur, dependCur);
        bbNext.statePredIndex++;
        return;
    }

    // merge bb
    if (bbNext.stateMerge != Circuit::NullGate()) {
        ASSERT(bbNext.dependMerge != Circuit::NullGate());
        gateAcc_.NewIn(bbNext.stateMerge, bbNext.statePredIndex, stateCur);
        gateAcc_.NewIn(bbNext.dependMerge, bbNext.statePredIndex + 1, dependCur); // 1: skip state
    }
    bbNext.statePredIndex++;
    ASSERT(bbNext.statePredIndex <= bbNext.numOfStatePreds);
}

GateRef BytecodeCircuitBuilder::NewConst(const BytecodeInfo &info)
{
    auto opcode = info.GetOpcode();
    GateRef gate = 0;
    switch (opcode) {
        case EcmaOpcode::LDNAN:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             base::NumberHelper::GetNaN(),
                                             GateType::NumberType());
            break;
        case EcmaOpcode::LDINFINITY:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             base::NumberHelper::GetPositiveInfinity(),
                                             GateType::NumberType());
            break;
        case EcmaOpcode::LDUNDEFINED:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             JSTaggedValue::VALUE_UNDEFINED,
                                             GateType::UndefinedType());
            break;
        case EcmaOpcode::LDNULL:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             JSTaggedValue::VALUE_NULL,
                                             GateType::NullType());
            break;
        case EcmaOpcode::LDTRUE:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             JSTaggedValue::VALUE_TRUE,
                                             GateType::BooleanType());
            break;
        case EcmaOpcode::LDFALSE:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             JSTaggedValue::VALUE_FALSE,
                                             GateType::BooleanType());
            break;
        case EcmaOpcode::LDHOLE:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             JSTaggedValue::VALUE_HOLE,
                                             GateType::TaggedValue());
            break;
        case EcmaOpcode::LDAI_IMM32:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             std::get<Immediate>(info.inputs[0]).ToJSTaggedValueInt(),
                                             GateType::IntType());
            break;
        case EcmaOpcode::FLDAI_IMM64:
            gate = circuit_->GetConstantGate(MachineType::I64,
                                             std::get<Immediate>(info.inputs.at(0)).ToJSTaggedValueDouble(),
                                             GateType::DoubleType());
            break;
        case EcmaOpcode::LDFUNCTION:
            gate = argAcc_.GetCommonArgGate(CommonArgIdx::FUNC);
            break;
        case EcmaOpcode::LDNEWTARGET:
            gate = argAcc_.GetCommonArgGate(CommonArgIdx::NEW_TARGET);
            break;
        case EcmaOpcode::LDTHIS:
            gate = argAcc_.GetCommonArgGate(CommonArgIdx::THIS_OBJECT);
            break;
        default:
            LOG_ECMA(FATAL) << "this branch is unreachable";
            UNREACHABLE();
    }
    return gate;
}

void BytecodeCircuitBuilder::NewJSGate(BytecodeRegion &bb, GateRef &state, GateRef &depend)
{
    auto &iterator = bb.GetBytecodeIterator();
    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
    size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
    GateRef gate = 0;
    bool writable = !bytecodeInfo.NoSideEffects();
    bool hasFrameState = bytecodeInfo.HasFrameArgs();
    size_t pcOffset = GetPcOffset(iterator.Index());
    auto meta = circuit_->JSBytecode(numValueInputs, bytecodeInfo.GetOpcode(), pcOffset, writable, hasFrameState);
    std::vector<GateRef> inList = CreateGateInList(bytecodeInfo, meta);
    if (bytecodeInfo.IsDef()) {
        gate = circuit_->NewGate(meta, MachineType::I64, inList.size(),
                                 inList.data(), GateType::AnyType());
    } else {
        gate = circuit_->NewGate(meta, MachineType::NOVALUE, inList.size(),
                                 inList.data(), GateType::Empty());
    }
    byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
    jsGatesToByteCode_[gate] = iterator.Index();
    gateAcc_.NewIn(gate, 0, state);
    gateAcc_.NewIn(gate, 1, depend);
    state = gate;
    if (bytecodeInfo.IsThrow()) {
        depend = gate;

        if (!bb.catchs.empty()) {
            auto &bbNext = bb.catchs.at(0);
            SetBlockPred(bb, *bbNext, gate, gate);
            bbNext->expandedPreds.push_back({bb.id, iterator.Index(), true});
        } else {
            auto constant = circuit_->GetConstantGate(MachineType::I64,
                                                      JSTaggedValue::VALUE_EXCEPTION,
                                                      GateType::TaggedValue());
            circuit_->NewGate(circuit_->Return(),
                { state, depend, constant, circuit_->GetReturnRoot() });
        }
        return;
    }
    if (!bb.catchs.empty() && !bytecodeInfo.NoThrow()) {
        auto ifSuccess = circuit_->NewGate(circuit_->IfSuccess(), {gate});
        auto ifException = circuit_->NewGate(circuit_->IfException(), {gate, gate});

        auto &bbNext = bb.catchs.at(0);
        SetBlockPred(bb, *bbNext, ifException, ifException);
        if (bytecodeInfo.GetOpcode() == EcmaOpcode::CREATEASYNCGENERATOROBJ_V8) {
            bbNext->expandedPreds.push_back({bb.id, iterator.Index() + 1, true}); // 1: next pc
        } else {
            bbNext->expandedPreds.push_back({bb.id, iterator.Index(), true});
        }
        state = ifSuccess;
    }
    if (bytecodeInfo.IsGeneratorRelative()) {
        //exclude...
        if (bytecodeInfo.GetOpcode() == EcmaOpcode::SUSPENDGENERATOR_V8 ||
            bytecodeInfo.GetOpcode() == EcmaOpcode::ASYNCGENERATORRESOLVE_V8_V8_V8 ||
            bytecodeInfo.GetOpcode() == EcmaOpcode::CREATEOBJECTWITHEXCLUDEDKEYS_IMM8_V8_V8) {
            auto hole = circuit_->GetConstantGate(MachineType::I64,
                                                  JSTaggedValue::VALUE_HOLE,
                                                  GateType::TaggedValue());
            uint32_t numRegs = GetNumberVRegsWithEnv();
            std::vector<GateRef> vec(numRegs + 1, hole);
            vec[0] = depend;
            GateRef saveRegs =
                circuit_->NewGate(circuit_->SaveRegister(numRegs), vec);
            gateAcc_.ReplaceDependIn(gate, saveRegs);
        }
        suspendAndResumeGates_.emplace_back(gate);
    }
    depend = gate;
}

void BytecodeCircuitBuilder::NewJump(BytecodeRegion &bb, GateRef &state, GateRef &depend)
{
    auto &iterator = bb.GetBytecodeIterator();
    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
    size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
    if (bytecodeInfo.IsCondJump()) {
        size_t pcOffset = GetPcOffset(iterator.Index());
        auto meta = circuit_->JSBytecode(numValueInputs, bytecodeInfo.GetOpcode(), pcOffset, false, false);
        auto numValues = meta->GetNumIns();
        GateRef gate = circuit_->NewGate(meta, std::vector<GateRef>(numValues, Circuit::NullGate()));
        gateAcc_.NewIn(gate, 0, state);
        gateAcc_.NewIn(gate, 1, depend);
        auto ifTrue = circuit_->NewGate(circuit_->IfTrue(), {gate});
        auto trueRelay = circuit_->NewGate(circuit_->DependRelay(), {ifTrue, gate});
        auto ifFalse = circuit_->NewGate(circuit_->IfFalse(), {gate});
        auto falseRelay = circuit_->NewGate(circuit_->DependRelay(), {ifFalse, gate});
        if (bb.succs.size() == 1) {
            auto &bbNext = bb.succs[0];
            ASSERT(bbNext->id == bb.id + 1);
            SetBlockPred(bb, *bbNext, ifFalse, falseRelay);
            SetBlockPred(bb, *bbNext, ifTrue, trueRelay);
            bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
            bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
        } else {
            ASSERT(bb.succs.size() == 2); // 2 : 2 num of successors
            [[maybe_unused]] uint32_t bitSet = 0;
            for (auto &bbNext: bb.succs) {
                if (bbNext->id == bb.id + 1) {
                    SetBlockPred(bb, *bbNext, ifFalse, falseRelay);
                    bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
                    bitSet |= 1;
                } else {
                    SetBlockPred(bb, *bbNext, ifTrue, trueRelay);
                    bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
                    bitSet |= 2; // 2:verify
                }
            }
            ASSERT(bitSet == 3); // 3:Verify the number of successor blocks
        }
        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
        jsGatesToByteCode_[gate] = iterator.Index();
    } else {
        ASSERT(bb.succs.size() == 1);
        auto &bbNext = bb.succs.at(0);
        SetBlockPred(bb, *bbNext, state, depend);
        bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
    }
}

void BytecodeCircuitBuilder::NewReturn(BytecodeRegion &bb, GateRef &state, GateRef &depend)
{
    ASSERT(bb.succs.empty());
    auto &iterator = bb.GetBytecodeIterator();
    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
    if (bytecodeInfo.GetOpcode() == EcmaOpcode::RETURN) {
        // handle return.dyn bytecode
        auto gate = circuit_->NewGate(circuit_->Return(),
            { state, depend, Circuit::NullGate(), circuit_->GetReturnRoot() });
        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
        jsGatesToByteCode_[gate] = iterator.Index();
    } else if (bytecodeInfo.GetOpcode() == EcmaOpcode::RETURNUNDEFINED) {
        // handle returnundefined bytecode
        auto constant = circuit_->GetConstantGate(MachineType::I64,
                                                  JSTaggedValue::VALUE_UNDEFINED,
                                                  GateType::TaggedValue());
        auto gate = circuit_->NewGate(circuit_->Return(),
            { state, depend, constant, circuit_->GetReturnRoot() });
        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
        jsGatesToByteCode_[gate] = iterator.Index();
    }
}

void BytecodeCircuitBuilder::NewByteCode(BytecodeRegion &bb, GateRef &state, GateRef &depend)
{
    auto &iterator = bb.GetBytecodeIterator();
    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
    if (bytecodeInfo.IsSetConstant()) {
        // handle bytecode command to get constants
        GateRef gate = NewConst(bytecodeInfo);
        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
        jsGatesToByteCode_[gate] = iterator.Index();
    } else if (bytecodeInfo.IsGeneral()) {
        // handle general ecma.* bytecodes
        NewJSGate(bb, state, depend);
    } else if (bytecodeInfo.IsJump()) {
        // handle conditional jump and unconditional jump bytecodes
        NewJump(bb, state, depend);
    } else if (bytecodeInfo.IsReturn()) {
        // handle return.dyn and returnundefined bytecodes
        NewReturn(bb, state, depend);
    } else if (!bytecodeInfo.IsDiscarded() && !bytecodeInfo.IsMov()) {
        LOG_ECMA(FATAL) << "this branch is unreachable";
        UNREACHABLE();
    }
}

void BytecodeCircuitBuilder::BuildSubCircuit()
{
    auto &entryBlock = graph_[0];
    BuildBlockCircuitHead(entryBlock, entryBlock.stateCurrent, entryBlock.dependCurrent);
    for (auto &bbId: dfsList_) {
        auto &bb = graph_[bbId];
        auto stateCur = bb.stateCurrent;
        auto dependCur = bb.dependCurrent;
        ASSERT(stateCur != Circuit::NullGate());
        ASSERT(dependCur != Circuit::NullGate());
        if (IsEntryBlock(bb.id)) {
            if (NeedCheckSafePointAndStackOver()) {
                stateCur = circuit_->NewGate(circuit_->CheckSafePointAndStackOver(), {stateCur, dependCur});
                dependCur = stateCur;
            }
            auto &bbNext = graph_[bb.id + 1];
            SetBlockPred(bb, bbNext, stateCur, dependCur);
            bbNext.expandedPreds.push_back({bb.id, bb.end, false});
            continue;
        }
        if (!bb.trys.empty()) {
            dependCur = circuit_->NewGate(circuit_->GetException(),
                MachineType::I64, {stateCur, dependCur}, GateType::AnyType());
            bb.dependCurrent = dependCur;
        }
        EnumerateBlock(bb, [this, &stateCur, &dependCur, &bb]
            (const BytecodeInfo &bytecodeInfo) -> bool {
            NewByteCode(bb, stateCur, dependCur);
            if (bytecodeInfo.IsJump() || bytecodeInfo.IsThrow()) {
                return false;
            }
            return true;
        });
        const BytecodeInfo& bytecodeInfo = GetBytecodeInfo(bb.end);
        if (bytecodeInfo.needFallThrough()) {
            auto &bbNext = graph_[bb.id + 1];
            SetBlockPred(bb, bbNext, stateCur, dependCur);
            bbNext.expandedPreds.push_back({bb.id, bb.end, false});
        }
    }
}

GateRef BytecodeCircuitBuilder::NewLoopBackPhi(BytecodeRegion &bb, uint16_t reg, bool acc)
{
    if (bb.numOfLoopBacks == 1) {
        for (size_t i = 0; i < bb.numOfStatePreds; ++i) {
            auto &[predId, predBcIdx, isException] = bb.expandedPreds.at(i);
            if (bb.loopbackBlocks.count(predId)) {
                return NewValueFromPredBB(bb, i, gateAcc_.GetState(bb.stateCurrent, 1), reg, acc);
            }
        }
        UNREACHABLE();
        LOG_COMPILER(FATAL) << "this branch is unreachable";
    }
    auto inList = std::vector<GateRef>(1 + bb.numOfLoopBacks, Circuit::NullGate());
    auto loopBackValue = circuit_->NewGate(circuit_->ValueSelector(bb.numOfLoopBacks),
        MachineType::I64, inList.size(), inList.data(), GateType::AnyType());
    gateAcc_.NewIn(loopBackValue, 0, bb.loopBackStateMerge);
    size_t loopBackIndex = 1;  // 1: start index of value inputs
    for (size_t i = 0; i < bb.numOfStatePreds; ++i) {
        auto &[predId, predBcIdx, isException] = bb.expandedPreds.at(i);
        if (bb.loopbackBlocks.count(predId)) {
            GateRef ans = NewValueFromPredBB(bb, i, gateAcc_.GetState(bb.loopBackStateMerge, loopBackIndex - 1),
                                             reg, acc);
            gateAcc_.NewIn(loopBackValue, loopBackIndex++, ans);
        }
    }
    return loopBackValue;
}

size_t BytecodeCircuitBuilder::LoopExitCount(size_t from, size_t to)
{
    if (!EnableLoopOptimization()) {
        return 0;
    }
    const auto &bb = GetBasicBlockById(from);
    const auto &bbNext = GetBasicBlockById(to);
    size_t headDep = ((bbNext.numOfLoopBacks > 0) && (bbNext.loopbackBlocks.count(bb.id) == 0)) ? 1 : 0;
    ASSERT(bbNext.loopDepth >= headDep);
    size_t nextDep = bbNext.loopDepth - headDep;
    ASSERT(bb.loopDepth >= nextDep);
    return bb.loopDepth > nextDep;
}

GateRef BytecodeCircuitBuilder::NewValueFromPredBB(BytecodeRegion &bb, size_t idx,
                                                   GateRef exit, uint16_t reg, bool acc)
{
    auto &[predId, predBcIdx, isException] = bb.expandedPreds.at(idx);
    if (LoopExitCount(predId, bb.id) == 0) {
        return ResolveDef(predId, predBcIdx, reg, acc);
    }
    while (gateAcc_.GetOpCode(exit) != OpCode::LOOP_EXIT) {
        exit = gateAcc_.GetState(exit);
    }
    if (IsLoopExitValueExists(exit, reg, acc)) {
        return GetLoopExitValue(exit, reg, acc);
    }
    GateRef res = ResolveDef(predId, predBcIdx, reg, acc);
    return NewLoopExitValue(exit, reg, acc, res);
}

GateRef BytecodeCircuitBuilder::NewLoopForwardPhi(BytecodeRegion &bb, uint16_t reg, bool acc)
{
    auto mergeCount = bb.numOfStatePreds - bb.numOfLoopBacks;
    if (mergeCount == 1) {
        for (size_t i = 0; i < bb.numOfStatePreds; ++i) {
            auto &[predId, predBcIdx, isException] = bb.expandedPreds.at(i);
            if (!bb.loopbackBlocks.count(predId)) {
                return NewValueFromPredBB(bb, i, gateAcc_.GetState(bb.stateCurrent, 0), reg, acc);
            }
        }
        UNREACHABLE();
        LOG_COMPILER(FATAL) << "this branch is unreachable";
    }
    auto inList = std::vector<GateRef>(1 + mergeCount, Circuit::NullGate());
    auto forwardValue = circuit_->NewGate(
        circuit_->ValueSelector(mergeCount), MachineType::I64,
        inList.size(), inList.data(), GateType::AnyType());
    gateAcc_.NewIn(forwardValue, 0, bb.stateMerge);
    size_t forwardIndex = 1;  // 1: start index of value inputs
    for (size_t i = 0; i < bb.numOfStatePreds; ++i) {
        auto &[predId, predBcIdx, isException] = bb.expandedPreds.at(i);
        if (!bb.loopbackBlocks.count(predId)) {
            GateRef ans = NewValueFromPredBB(bb, i, gateAcc_.GetState(bb.stateMerge, forwardIndex - 1), reg, acc);
            gateAcc_.NewIn(forwardValue, forwardIndex++, ans);
        }
    }
    return forwardValue;
}

void BytecodeCircuitBuilder::NewPhi(BytecodeRegion &bb, uint16_t reg, bool acc, GateRef &currentPhi)
{
    if (bb.numOfLoopBacks == 0) {
        if (bb.numOfStatePreds == 1) {
            currentPhi = NewValueFromPredBB(bb, 0, bb.stateCurrent, reg, acc);
            ASSERT(currentPhi != 0);
            return;
        }
        ASSERT(bb.stateMerge != Circuit::NullGate());
        auto inList = std::vector<GateRef>(1 + bb.numOfStatePreds, Circuit::NullGate());
        currentPhi =
            circuit_->NewGate(circuit_->ValueSelector(bb.numOfStatePreds), MachineType::I64,
                              inList.size(), inList.data(), GateType::AnyType());
        gateAcc_.NewIn(currentPhi, 0, bb.stateMerge);
        for (size_t i = 0; i < bb.numOfStatePreds; ++i) {
            GateRef ans = NewValueFromPredBB(bb, i, gateAcc_.GetIn(bb.stateMerge, i), reg, acc);
            gateAcc_.NewIn(currentPhi, i + 1, ans);
        }
    } else {
        ASSERT(gateAcc_.GetOpCode(bb.stateCurrent) == OpCode::LOOP_BEGIN);
        // 2: the number of value inputs and it is in accord with LOOP_BEGIN
        currentPhi = circuit_->NewGate(circuit_->ValueSelector(2), MachineType::I64,
            {bb.stateCurrent, Circuit::NullGate(), Circuit::NullGate()}, GateType::AnyType());
        auto loopBackValue = NewLoopBackPhi(bb, reg, acc);
        auto forwardValue = NewLoopForwardPhi(bb, reg, acc);
        gateAcc_.NewIn(currentPhi, 1, forwardValue);   // 1: index of forward value input
        gateAcc_.NewIn(currentPhi, 2, loopBackValue);  // 2: index of loop-back value input
    }
    bb.phiGate.insert(currentPhi);
}

bool BytecodeCircuitBuilder::IsLoopExitValueExists(GateRef loopExit, uint16_t reg, bool acc)
{
    if (acc) {
        return loopExitToAccGate_.count(loopExit) > 0;
    } else {
        return loopExitToVregGate_.count(std::make_pair(loopExit, reg)) > 0;
    }
}

GateRef BytecodeCircuitBuilder::GetLoopExitValue(GateRef loopExit, uint16_t reg, bool acc)
{
    if (acc) {
        return loopExitToAccGate_.at(loopExit);
    } else {
        return loopExitToVregGate_.at(std::make_pair(loopExit, reg));
    }
}

GateRef BytecodeCircuitBuilder::CreateLoopExitValue(GateRef loopExit, uint16_t reg, bool acc, GateRef value)
{
    GateRef newPhi = circuit_->NewGate(circuit_->LoopExitValue(), gateAcc_.GetMachineType(value),
                                       {loopExit, value}, gateAcc_.GetGateType(value));
    if (acc) {
        return loopExitToAccGate_[loopExit] = newPhi;
    } else {
        auto key = std::make_pair(loopExit, reg);
        return loopExitToVregGate_[key] = newPhi;
    }
}

GateRef BytecodeCircuitBuilder::NewLoopExitValue(GateRef loopExit, uint16_t reg, bool acc, GateRef value)
{
    ASSERT(gateAcc_.GetOpCode(loopExit) == OpCode::LOOP_EXIT);
    ChunkVector<GateRef> exitList(circuit_->chunk());
    while (gateAcc_.GetOpCode(loopExit) == OpCode::LOOP_EXIT) {
        exitList.push_back(loopExit);
        loopExit = gateAcc_.GetState(loopExit);
    }
    while (!exitList.empty()) {
        GateRef exit = exitList.back();
        value = CreateLoopExitValue(exit, reg, acc, value);
        exitList.pop_back();
    }
    return value;
}

GateRef BytecodeCircuitBuilder::ResolveDef(const BytecodeRegion &bb, int32_t bcId, const uint16_t reg, const bool acc)
{
    // Ensure that bcId is not negative
    if (bcId == 0) {
        return ResolveDef(bb.id, bcId, reg, acc, false);
    }
    return ResolveDef(bb.id, bcId - 1, reg, acc);
}

// recursive variables renaming algorithm
GateRef BytecodeCircuitBuilder::ResolveDef(const size_t bbId, int32_t bcId,
    const uint16_t reg, const bool acc, bool needIter)
{
    auto tmpReg = reg;
    // find def-site in bytecodes of basic block
    auto ans = Circuit::NullGate();
    auto &bb = graph_.at(bbId);
    GateType type = GateType::AnyType();
    auto tmpAcc = acc;

    if (needIter) {
        BytecodeIterator iterator(this, bb.start, bcId);
        for (iterator.Goto(bcId); !iterator.Done(); --iterator) {
            const BytecodeInfo& curInfo = iterator.GetBytecodeInfo();
            // original bc use acc as input && current bc use acc as output
            bool isTransByAcc = tmpAcc && curInfo.AccOut();
            // 0 : the index in vreg-out list
            bool isTransByVreg = (!tmpAcc && curInfo.IsOut(tmpReg, 0));
            if (isTransByAcc || isTransByVreg) {
                if (curInfo.IsMov()) {
                    tmpAcc = curInfo.AccIn();
                    if (!curInfo.inputs.empty()) {
                        ASSERT(!tmpAcc);
                        ASSERT(curInfo.inputs.size() == 1);
                        tmpReg = std::get<VirtualRegister>(curInfo.inputs.at(0)).GetId();
                    }
                    if (HasTypes()) {
                        type = typeRecorder_.UpdateType(iterator.Index(), type);
                    }
                } else {
                    ans = byteCodeToJSGates_.at(iterator.Index()).at(0);
                    auto oldType = gateAcc_.GetGateType(ans);
                    if (!type.IsAnyType() && oldType.IsAnyType()) {
                        typeRecorder_.GetOrUpdatePGOType(tsManager_, gateAcc_.TryGetPcOffset(ans), type);
                        gateAcc_.SetGateType(ans, type);
                    }
                    break;
                }
            }
            if (curInfo.GetOpcode() != EcmaOpcode::RESUMEGENERATOR) {
                continue;
            }
            // New RESTORE_REGISTER HIR, used to restore the register content when processing resume instruction.
            // New SAVE_REGISTER HIR, used to save register content when processing suspend instruction.
            auto resumeGate = byteCodeToJSGates_.at(iterator.Index()).at(0);
            ans = GetExistingRestore(resumeGate, tmpReg);
            if (ans != Circuit::NullGate()) {
                break;
            }
            ans = circuit_->NewGate(circuit_->RestoreRegister(tmpReg), MachineType::I64,
                                    { resumeGate }, GateType::AnyType());
            SetExistingRestore(resumeGate, tmpReg, ans);
            auto saveRegGate = ResolveDef(bbId, iterator.Index() - 1, tmpReg, tmpAcc);
            [[maybe_unused]] EcmaOpcode opcode = Bytecodes::GetOpcode(iterator.PeekPrevPc(2)); // 2: prev bc
            ASSERT(opcode == EcmaOpcode::SUSPENDGENERATOR_V8 || opcode == EcmaOpcode::ASYNCGENERATORRESOLVE_V8_V8_V8);
            GateRef suspendGate = byteCodeToJSGates_.at(iterator.Index() - 2).at(0); // 2: prev bc
            GateRef saveRegs = gateAcc_.GetDep(suspendGate);
            gateAcc_.ReplaceValueIn(saveRegs, saveRegGate, tmpReg);
            break;
        }
    }
    // find GET_EXCEPTION gate if this is a catch block
    if (ans == Circuit::NullGate() && tmpAcc) {
        if (!bb.trys.empty()) {
            GateRef getExceptionGate = bb.dependCurrent;
            ASSERT(gateAcc_.GetOpCode(getExceptionGate) == OpCode::GET_EXCEPTION);
            ASSERT(getExceptionGate != Circuit::NullGate());
            ans = getExceptionGate;
        }
    }
    // find def-site in value selectors of vregs
    if (ans == Circuit::NullGate() && !tmpAcc && bb.phi.count(tmpReg)) {
        if (!bb.vregToValueGate.count(tmpReg)) {
            NewPhi(bb, tmpReg, tmpAcc, bb.vregToValueGate[tmpReg]);
        }
        ans = bb.vregToValueGate.at(tmpReg);
    }
    // find def-site in value selectors of acc
    if (ans == Circuit::NullGate() && tmpAcc && bb.phiAcc) {
        if (bb.valueSelectorAccGate == Circuit::NullGate()) {
            NewPhi(bb, tmpReg, tmpAcc, bb.valueSelectorAccGate);
        }
        ans = bb.valueSelectorAccGate;
    }
    if (ans == Circuit::NullGate() && IsEntryBlock(bbId)) { // entry block
        // find def-site in function args
        ASSERT(!tmpAcc);
        if (tmpReg == GetEnvVregIdx()) {
            ans = gateAcc_.GetInitialEnvGate(argAcc_.GetCommonArgGate(CommonArgIdx::FUNC));
        } else if (argAcc_.ArgGateNotExisted(tmpReg)) {
            // when GetArgGate fail, return hole
            ans = circuit_->GetConstantGate(MachineType::I64,
                                            JSTaggedValue::VALUE_HOLE,
                                            GateType::TaggedValue());
        } else {
            ans = argAcc_.GetArgGate(tmpReg);
        }
        return ans;
    }
    if (EnableLoopOptimization()) {
        // find def-site in value selectors of vregs
        if (ans == Circuit::NullGate() && !tmpAcc) {
            if (!bb.vregToValueGate.count(tmpReg)) {
                bb.vregToValueGate[tmpReg] = Circuit::NullGate();
                NewPhi(bb, tmpReg, tmpAcc, bb.vregToValueGate[tmpReg]);
            } else if (bb.vregToValueGate.at(tmpReg) == Circuit::NullGate()) {
                NewPhi(bb, tmpReg, tmpAcc, bb.vregToValueGate[tmpReg]);
            }
            ans = bb.vregToValueGate.at(tmpReg);
        }
        // find def-site in value selectors of acc
        if (ans == Circuit::NullGate() && tmpAcc) {
            if (bb.valueSelectorAccGate == Circuit::NullGate()) {
                NewPhi(bb, tmpReg, tmpAcc, bb.valueSelectorAccGate);
            }
            ans = bb.valueSelectorAccGate;
        }
    }
    if (ans == Circuit::NullGate()) {
        // recursively find def-site in dominator block
        GateRef res = ResolveDef(bb.iDominator->id, bb.iDominator->end, tmpReg, tmpAcc);
        return res;
    } else {
        // def-site already found
        return ans;
    }
}

void BytecodeCircuitBuilder::BuildCircuit()
{
    // create arg gates array
    BuildCircuitArgs();
    CollectPredsInfo();
    // build states sub-circuit of each block
    BuildSubCircuit();
    // verification of soundness of CFG
    for (auto &bb: graph_) {
        if (bb.isDead) {
            continue;
        }
        ASSERT(bb.statePredIndex == bb.numOfStatePreds);
        ASSERT(bb.loopBackIndex == bb.numOfLoopBacks);
        if (bb.numOfLoopBacks) {
            ASSERT(bb.forwardIndex == bb.numOfStatePreds - bb.numOfLoopBacks);
        }
        // resolve def-site of virtual regs and set all value inputs
        EnumerateBlock(bb, [&](const BytecodeInfo &bytecodeInfo) -> bool {
            auto &iterator = bb.GetBytecodeIterator();
            const auto bcIndex = iterator.Index();
            const auto bbIndex = bb.id;
            GateRef gate = GetGateByBcIndex(bcIndex);
            if (gate == Circuit::NullGate()) {
                return true;
            }
            if (gateAcc_.IsConstant(gate)) {
                return true;
            }

            auto type = typeRecorder_.GetType(bcIndex);
            gateAcc_.SetGateType(gate, type);
            auto pgoType = typeRecorder_.GetOrUpdatePGOType(tsManager_, gateAcc_.TryGetPcOffset(gate), type);
            gateAcc_.TrySetPGOType(gate, pgoType);

            auto valueCount = gateAcc_.GetInValueCount(gate);
            [[maybe_unused]] size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
            [[maybe_unused]] size_t numValueOutputs = bytecodeInfo.ComputeOutCount();
            // RETURNUNDEFINED has value input, but not from acc
            ASSERT(numValueInputs == valueCount || bytecodeInfo.GetOpcode() == EcmaOpcode::RETURNUNDEFINED);
            ASSERT(numValueOutputs <= 1 + (bytecodeInfo.EnvOut() ? 1 : 0));
            auto valueStarts = gateAcc_.GetInValueStarts(gate);
            for (size_t valueIdx = 0; valueIdx < valueCount; valueIdx++) {
                auto inIdx = valueIdx + valueStarts;
                if (!gateAcc_.IsInGateNull(gate, inIdx)) {
                    continue;
                }
                if (bytecodeInfo.GetOpcode() == EcmaOpcode::CREATEOBJECTWITHEXCLUDEDKEYS_IMM8_V8_V8) {
                    GateRef depIn = gateAcc_.GetDep(gate);
                    size_t depCount = gateAcc_.GetNumValueIn(depIn);
                    GateRef defVreg = Circuit::NullGate();
                    for (size_t idx = 0; idx < depCount; idx++) {
                        defVreg = ResolveDef(bb, bcIndex, idx, false);
                        gateAcc_.ReplaceValueIn(depIn, defVreg, idx);
                    }
                }
                if (valueIdx < bytecodeInfo.inputs.size()) {
                    auto vregId = std::get<VirtualRegister>(bytecodeInfo.inputs.at(valueIdx)).GetId();
                    GateRef defVreg = Circuit::NullGate();
                    if (IsFirstBCEnvIn(bbIndex, bcIndex, vregId)) {
                        defVreg = gateAcc_.GetInitialEnvGate(argAcc_.GetCommonArgGate(CommonArgIdx::FUNC));
                    } else {
                        defVreg = ResolveDef(bb, bcIndex, vregId, false);
                    }
                    gateAcc_.NewIn(gate, inIdx, defVreg);
                } else {
                    GateRef defAcc = ResolveDef(bb, bcIndex, 0, true);
                    if (!Bytecodes::IsCallOp(bytecodeInfo.GetOpcode())) {
                        gateAcc_.NewIn(gate, inIdx, defAcc);
                        continue;
                    }
                    auto oldGt = gateAcc_.GetGateType(defAcc).GetGTRef();
                    GateType callTargetType = typeRecorder_.GetCallTargetType(bcIndex);
                    if (!tsManager_->MethodOffsetIsVaild(oldGt) && !callTargetType.IsAnyType()) {
                        gateAcc_.SetGateType(defAcc, callTargetType);
                    }
                    gateAcc_.NewIn(gate, inIdx, defAcc);
                }
            }
            return true;
        });
    }

    if (IsTypeLoweringEnabled()) {
        frameStateBuilder_.BuildFrameState();
    }

    gateAcc_.EliminateRedundantPhi();

    if (IsLogEnabled()) {
        PrintGraph("Bytecode2Gate");
        LOG_COMPILER(INFO) << "\033[34m" << "============= "
                           << "After bytecode2circuit lowering ["
                           << methodName_ << "]"
                           << " =============" << "\033[0m";
        circuit_->PrintAllGatesWithBytecode();
        LOG_COMPILER(INFO) << "\033[34m" << "=========================== End ===========================" << "\033[0m";
    }
}

GateRef BytecodeCircuitBuilder::GetExistingRestore(GateRef resumeGate, uint16_t tmpReg) const
{
    auto pr = std::make_pair(resumeGate, tmpReg);
    if (resumeRegToRestore_.count(pr)) {
        return resumeRegToRestore_.at(pr);
    }
    return Circuit::NullGate();
}

void BytecodeCircuitBuilder::SetExistingRestore(GateRef resumeGate, uint16_t tmpReg, GateRef restoreGate)
{
    auto pr = std::make_pair(resumeGate, tmpReg);
    resumeRegToRestore_[pr] = restoreGate;
}

void BytecodeCircuitBuilder::CollectLoopBack()
{
    auto size = GetBasicBlockCount();
    ChunkVector<size_t> workList(circuit_->chunk());
    ChunkVector<VisitState> visitState(circuit_->chunk());
    visitState.resize(size, VisitState::UNVISITED);
    size_t entryId = 0; // entry id
    workList.emplace_back(entryId);
    while (!workList.empty()) {
        size_t bbId = workList.back();
        auto &bb = GetBasicBlockById(bbId);
        if (visitState[bbId] == VisitState::UNVISITED) {
            dfsList_.emplace_back(bbId);
            visitState[bbId] = VisitState::PENDING;
        }
        bool allVisited = true;

        for (const auto &succBlock: bb.succs) {
            size_t succId = succBlock->id;
            if (visitState[succId] == VisitState::UNVISITED) {
                // dfs
                workList.emplace_back(succId);
                allVisited = false;
                break;
            } else if (visitState[succId] == VisitState::PENDING) {
                // back edge
                CountLoopBackEdge(bbId, succId);
            }
        }

        for (const auto &succBlock: bb.catchs) {
            size_t succId = succBlock->id;
            if (visitState[succId] == VisitState::UNVISITED) {
                // dfs
                workList.emplace_back(succId);
                allVisited = false;
                break;
            } else if (visitState[succId] == VisitState::PENDING) {
                // back edge
                CountLoopBackEdge(bbId, succId);
            }
        }
        if (allVisited) {
            workList.pop_back();
            visitState[bbId] = VisitState::VISITED;
        }
    }
}

void BytecodeCircuitBuilder::CountLoopBackEdge(size_t fromId, size_t toId)
{
    auto &toBlock = GetBasicBlockById(toId);
    if (toBlock.numOfLoopBacks == 0) {
        loopHeads_.emplace_back(std::make_pair(0, toId));
    }
    toBlock.loopbackBlocks.insert(fromId);
    toBlock.numOfLoopBacks = toBlock.loopbackBlocks.size();
}

void BytecodeCircuitBuilder::ComputeLoopDepth(size_t loopHead)
{
    ChunkSet<size_t> visited (circuit_->chunk());
    ChunkQueue<size_t> workList (circuit_->chunk());
    visited.insert(loopHead);
    auto &headBB = GetBasicBlockById(loopHead);
    headBB.loopDepth++;
    for (auto loopBack : headBB.loopbackBlocks) {
        workList.push(loopBack);
    }
    while (!workList.empty()) {
        size_t cur = workList.front();
        workList.pop();
        if (visited.count(cur) > 0) {
            continue;
        }
        visited.insert(cur);
        auto &curBB = GetBasicBlockById(cur);
        curBB.loopDepth++;
        for (const auto& pred : curBB.preds) {
            workList.push(pred->id);
        }
        for (const auto& pred : curBB.trys) {
            workList.push(pred->id);
        }
    }
    loopSize_ = visited.size();
}

void BytecodeCircuitBuilder::PrintGraph(const char* title)
{
    LOG_COMPILER(INFO) << "======================== " << title << " ========================";
    for (size_t i = 0; i < graph_.size(); i++) {
        BytecodeRegion& bb = graph_[i];
        if (bb.isDead) {
            LOG_COMPILER(INFO) << "B" << bb.id << ":                               ;preds= invalid BB";
            LOG_COMPILER(INFO) << "\tBytecodePC: [" << std::to_string(bb.start) << ", "
                               << std::to_string(bb.end) << ")";
            continue;
        }
        std::string log("B" + std::to_string(bb.id) + ":                               ;preds= ");
        for (size_t k = 0; k < bb.preds.size(); ++k) {
            log += std::to_string(bb.preds[k]->id) + ", ";
        }
        LOG_COMPILER(INFO) << log;
        if (IsEntryBlock(bb.id)) {
            LOG_COMPILER(INFO) << "\tBytecodePC: Empty";
        } else {
            LOG_COMPILER(INFO) << "\tBytecodePC: [" << std::to_string(bb.start) << ", "
                << std::to_string(bb.end) << ")";
        }

        std::string log1("\tSucces: ");
        for (size_t j = 0; j < bb.succs.size(); j++) {
            log1 += std::to_string(bb.succs[j]->id) + ", ";
        }
        LOG_COMPILER(INFO) << log1;

        for (size_t j = 0; j < bb.catchs.size(); j++) {
            LOG_COMPILER(INFO) << "\tcatch [: " << std::to_string(bb.catchs[j]->start) << ", "
                               << std::to_string(bb.catchs[j]->end) << ")";
        }

        std::string log2("\tTrys: ");
        for (auto tryBlock: bb.trys) {
            log2 += std::to_string(tryBlock->id) + " , ";
        }
        LOG_COMPILER(INFO) << log2;

        std::string log3 = "\tDom: ";
        for (size_t j = 0; j < bb.immDomBlocks.size(); j++) {
            log3 += "B" + std::to_string(bb.immDomBlocks[j]->id) + std::string(", ");
        }
        LOG_COMPILER(INFO) << log3;

        if (bb.iDominator) {
            LOG_COMPILER(INFO) << "\tIDom B" << bb.iDominator->id;
        }

        std::string log4("\tDom Frontiers: ");
        for (const auto &frontier: bb.domFrontiers) {
            log4 += std::to_string(frontier->id) + " , ";
        }
        LOG_COMPILER(INFO) << log4;

        std::string log5("\tPhi: ");
        for (auto variable: bb.phi) {
            log5 += std::to_string(variable) + " , ";
        }
        LOG_COMPILER(INFO) << log5;

        std::string log6("\tLoop Depth: ");
        log6 += std::to_string(bb.loopDepth);
        LOG_COMPILER(INFO) << log6;

        PrintBytecodeInfo(bb);
        LOG_COMPILER(INFO) << "";
    }
}

void BytecodeCircuitBuilder::PrintBytecodeInfo(BytecodeRegion& bb)
{
    if (bb.isDead) {
        return;
    }
    if (IsEntryBlock(bb.id)) {
        LOG_COMPILER(INFO) << "\tBytecode[] = Empty";
        return;
    }
    LOG_COMPILER(INFO) << "\tBytecode[] = ";
    EnumerateBlock(bb, [&](const BytecodeInfo &bytecodeInfo) -> bool {
        auto &iterator = bb.GetBytecodeIterator();
        std::string log;
        log += std::string("\t\t< ") + std::to_string(iterator.Index()) + ": ";
        log += GetEcmaOpcodeStr(iterator.GetBytecodeInfo().GetOpcode()) + ", " + "In=[";
        if (bytecodeInfo.AccIn()) {
            log += "acc,";
        }
        for (const auto &in: bytecodeInfo.inputs) {
            if (std::holds_alternative<VirtualRegister>(in)) {
                log += std::to_string(std::get<VirtualRegister>(in).GetId()) + ",";
            }
        }
        log += "], Out=[";
        if (bytecodeInfo.AccOut()) {
            log += "acc,";
        }
        for (const auto &out: bytecodeInfo.vregOut) {
            log += std::to_string(out) + ",";
        }
        log += "] >";
        LOG_COMPILER(INFO) << log;

        auto gate = GetGateByBcIndex(iterator.Index());
        if (gate != Circuit::NullGate()) {
            this->gateAcc_.ShortPrint(gate);
        }
        return true;
    });
}
}  // namespace panda::ecmascript::kungfu