1/*
2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 *     http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "ecmascript/compiler/bytecode_circuit_builder.h"
17
18#include <algorithm>
19#include <cstddef>
20
21#include "ecmascript/base/number_helper.h"
22#include "ecmascript/compiler/gate_accessor.h"
23#include "ecmascript/deoptimizer/deoptimizer.h"
24#include "ecmascript/interpreter/interpreter-inl.h"
25#include "libpandafile/bytecode_instruction-inl.h"
26
27
28namespace panda::ecmascript::kungfu {
29void BytecodeCircuitBuilder::BytecodeToCircuit()
30{
31    ExceptionInfo exceptionInfo = {};
32
33    // collect try catch block info
34    CollectTryCatchBlockInfo(exceptionInfo);
35    hasTryCatch_ = exceptionInfo.size() != 0;
36    BuildRegionInfo();
37    // Building the basic block diagram of bytecode
38    BuildRegions(exceptionInfo);
39}
40
41void BytecodeCircuitBuilder::BuildRegionInfo()
42{
43    uint32_t size = pcOffsets_.size();
44    ASSERT(size > 0);
45    uint32_t end = size - 1;  // 1: end
46    BytecodeIterator iterator(this, 0, end);
47
48    infoData_.resize(size);
49    byteCodeToJSGates_.resize(size, std::vector<GateRef>(0));
50    regionsInfo_.InsertHead(0); // 0: start pc
51    iterator.GotoStart();
52    while (!iterator.Done()) {
53        auto index = iterator.Index();
54        auto &info = infoData_[index];
55        auto pc = pcOffsets_[index];
56        info.metaData_ = bytecodes_->GetBytecodeMetaData(pc);
57        ASSERT(!info.metaData_.IsInvalid());
58        BytecodeInfo::InitBytecodeInfo(this, info, pc);
59        CollectRegionInfo(index);
60        ++iterator;
61    }
62}
63
64void BytecodeCircuitBuilder::CollectRegionInfo(uint32_t bcIndex)
65{
66    auto pc = pcOffsets_[bcIndex];
67    auto &info = infoData_[bcIndex];
68    int32_t offset = 0;
69    if (info.IsJump()) {
70        switch (info.GetOpcode()) {
71            case EcmaOpcode::JEQZ_IMM8:
72            case EcmaOpcode::JNEZ_IMM8:
73            case EcmaOpcode::JMP_IMM8:
74                offset = static_cast<int8_t>(READ_INST_8_0());
75                break;
76            case EcmaOpcode::JNEZ_IMM16:
77            case EcmaOpcode::JEQZ_IMM16:
78            case EcmaOpcode::JMP_IMM16:
79                offset = static_cast<int16_t>(READ_INST_16_0());
80                break;
81            case EcmaOpcode::JMP_IMM32:
82            case EcmaOpcode::JNEZ_IMM32:
83            case EcmaOpcode::JEQZ_IMM32:
84                offset = static_cast<int32_t>(READ_INST_32_0());
85                break;
86            default:
87                LOG_ECMA(FATAL) << "this branch is unreachable";
88                UNREACHABLE();
89                break;
90        }
91        auto nextIndex = bcIndex + 1; // 1: next pc
92        auto targetIndex = FindBcIndexByPc(pc + offset);
93        // condition branch current basic block end
94        if (info.IsCondJump()) {
95            regionsInfo_.InsertSplit(nextIndex);
96            regionsInfo_.InsertJump(targetIndex, bcIndex, false);
97        } else {
98            if (bcIndex != GetLastBcIndex()) {
99                regionsInfo_.InsertHead(nextIndex);
100            }
101            regionsInfo_.InsertJump(targetIndex, bcIndex, true);
102        }
103    } else if (info.IsReturn() || info.IsThrow()) {
104        if (bcIndex != GetLastBcIndex()) {
105            auto nextIndex = bcIndex + 1; // 1: next pc
106            regionsInfo_.InsertHead(nextIndex);
107        }
108    }
109}
110
111void BytecodeCircuitBuilder::CollectTryCatchBlockInfo(ExceptionInfo &byteCodeException)
112{
113    auto pf = file_->GetPandaFile();
114    panda_file::MethodDataAccessor mda(*pf, method_->GetMethodId());
115    panda_file::CodeDataAccessor cda(*pf, mda.GetCodeId().value());
116
117    cda.EnumerateTryBlocks([this, &byteCodeException](
118        panda_file::CodeDataAccessor::TryBlock &tryBlock) {
119        auto tryStartOffset = tryBlock.GetStartPc();
120        auto tryEndOffset = tryBlock.GetStartPc() + tryBlock.GetLength();
121
122        auto tryStartPc = const_cast<uint8_t *>(method_->GetBytecodeArray() + tryStartOffset);
123        auto tryEndPc = const_cast<uint8_t *>(method_->GetBytecodeArray() + tryEndOffset);
124        // skip try blocks with same pc in start and end label
125        if (tryStartPc == tryEndPc) {
126            return true;
127        }
128
129        auto tryStartBcIndex = FindBcIndexByPc(tryStartPc);
130        regionsInfo_.InsertSplit(tryStartBcIndex);
131        if (tryEndPc <= GetLastPC()) {
132            auto tryEndBcIndex = FindBcIndexByPc(tryEndPc);
133            regionsInfo_.InsertSplit(tryEndBcIndex);
134        }
135        byteCodeException.emplace_back(ExceptionItem { tryStartPc, tryEndPc, {} });
136        tryBlock.EnumerateCatchBlocks([&](panda_file::CodeDataAccessor::CatchBlock &catchBlock) {
137            auto pcOffset = catchBlock.GetHandlerPc();
138            auto catchBlockPc = const_cast<uint8_t *>(method_->GetBytecodeArray() + pcOffset);
139            auto catchBlockBcIndex = FindBcIndexByPc(catchBlockPc);
140            regionsInfo_.InsertHead(catchBlockBcIndex);
141            // try block associate catch block
142            byteCodeException.back().catches.emplace_back(catchBlockPc);
143            return true;
144        });
145        return true;
146    });
147}
148
149bool BytecodeCircuitBuilder::IsAncestor(size_t nodeA, size_t nodeB)
150{
151    return timeIn_[bbIdToDfsTimestamp_[nodeA]] <= timeIn_[bbIdToDfsTimestamp_[nodeB]] &&
152        timeOut_[bbIdToDfsTimestamp_[nodeA]] >= timeOut_[bbIdToDfsTimestamp_[nodeB]];
153}
154
155void BytecodeCircuitBuilder::PerformDFS(const std::vector<size_t> &immDom, size_t listSize)
156{
157    std::vector<std::vector<size_t>> sonList(listSize);
158    for (size_t idx = 1; idx < immDom.size(); idx++) {
159        sonList[immDom[idx]].push_back(idx);
160    }
161
162    {
163        size_t timestamp = 0;
164        struct DFSState {
165            size_t cur;
166            std::vector<size_t> &succList;
167            size_t idx;
168        };
169        std::stack<DFSState> dfsStack;
170        size_t root = 0;
171        dfsStack.push({root, sonList[root], 0});
172        timeIn_[root] = timestamp++;
173        while (!dfsStack.empty()) {
174            auto &curState = dfsStack.top();
175            auto &cur = curState.cur;
176            auto &succList = curState.succList;
177            auto &idx = curState.idx;
178            if (idx == succList.size()) {
179                timeOut_[cur] = timestamp++;
180                dfsStack.pop();
181                continue;
182            }
183            const auto &succ = succList[idx];
184            dfsStack.push({succ, sonList[succ], 0});
185            timeIn_[succ] = timestamp++;
186            idx++;
187        }
188    }
189}
190
191
192void BytecodeCircuitBuilder::ReducibilityCheck()
193{
194    std::vector<size_t> basicBlockList;
195    std::vector<size_t> immDom;
196    std::unordered_map<size_t, size_t> bbDfsTimestampToIdx;
197    ComputeDominatorTree(basicBlockList, immDom, bbDfsTimestampToIdx);
198    timeIn_.resize(basicBlockList.size());
199    timeOut_.resize(basicBlockList.size());
200    PerformDFS(immDom, basicBlockList.size());
201}
202
203void BytecodeCircuitBuilder::ComputeImmediateDominators(const std::vector<size_t> &basicBlockList,
204                                                        std::unordered_map<size_t, size_t> &dfsFatherIdx,
205                                                        std::vector<size_t> &immDom,
206                                                        std::unordered_map<size_t, size_t> &bbDfsTimestampToIdx)
207{
208    std::vector<size_t> semiDom(basicBlockList.size());
209    std::vector<std::vector<size_t> > semiDomTree(basicBlockList.size());
210    {
211        std::vector<size_t> parent(basicBlockList.size());
212        std::iota(parent.begin(), parent.end(), 0);
213        std::vector<size_t> minIdx(basicBlockList.size());
214        std::function<size_t(size_t)> unionFind = [&] (size_t idx) -> size_t {
215            if (parent[idx] == idx) return idx;
216            size_t unionFindSetRoot = unionFind(parent[idx]);
217            if (semiDom[minIdx[idx]] > semiDom[minIdx[parent[idx]]]) {
218                minIdx[idx] = minIdx[parent[idx]];
219            }
220            return parent[idx] = unionFindSetRoot;
221        };
222        auto merge = [&] (size_t fatherIdx, size_t sonIdx) -> void {
223            size_t parentFatherIdx = unionFind(fatherIdx);
224            size_t parentSonIdx = unionFind(sonIdx);
225            parent[parentSonIdx] = parentFatherIdx;
226        };
227        auto calculateSemiDom = [&](size_t idx, const ChunkVector<BytecodeRegion *> &blocks) {
228            for (const auto &preBlock : blocks) {
229                if (bbDfsTimestampToIdx[preBlock->id] < idx) {
230                    semiDom[idx] = std::min(semiDom[idx], bbDfsTimestampToIdx[preBlock->id]);
231                } else {
232                    unionFind(bbDfsTimestampToIdx[preBlock->id]);
233                    semiDom[idx] = std::min(semiDom[idx], semiDom[minIdx[bbDfsTimestampToIdx[preBlock->id]]]);
234                }
235            }
236        };
237        std::iota(semiDom.begin(), semiDom.end(), 0);
238        semiDom[0] = semiDom.size();
239        for (size_t idx = basicBlockList.size() - 1; idx >= 1; idx--) {
240            calculateSemiDom(idx, graph_[basicBlockList[idx]]->preds);
241            if (!graph_[basicBlockList[idx]]->trys.empty()) {
242                calculateSemiDom(idx, graph_[basicBlockList[idx]]->trys);
243            }
244            for (const auto &succDomIdx : semiDomTree[idx]) {
245                unionFind(succDomIdx);
246                if (idx == semiDom[minIdx[succDomIdx]]) {
247                    immDom[succDomIdx] = idx;
248                } else {
249                    immDom[succDomIdx] = minIdx[succDomIdx];
250                }
251            }
252            minIdx[idx] = idx;
253            merge(dfsFatherIdx[basicBlockList[idx]], idx);
254            semiDomTree[semiDom[idx]].emplace_back(idx);
255        }
256        for (size_t idx = 1; idx < basicBlockList.size(); idx++) {
257            if (immDom[idx] != semiDom[idx]) {
258                immDom[idx] = immDom[immDom[idx]];
259            }
260        }
261        semiDom[0] = 0;
262    }
263}
264
265void BytecodeCircuitBuilder::ComputeDominatorTree(std::vector<size_t> &basicBlockList, std::vector<size_t> &immDom,
266    std::unordered_map<size_t, size_t> &bbDfsTimestampToIdx)
267{
268    std::unordered_map<size_t, size_t> dfsFatherIdx;
269    size_t timestamp = 0;
270    std::deque<size_t> pendingList;
271    std::vector<size_t> visited(graph_.size(), 0);
272    auto basicBlockId = graph_[0]->id;
273    visited[graph_[0]->id] = 1;
274    pendingList.emplace_back(basicBlockId);
275
276    auto visitConnectedBlocks = [&](const ChunkVector<BytecodeRegion *> &succs, size_t curBlockId) {
277        for (const auto &succBlock : succs) {
278            if (visited[succBlock->id] == 0) {
279                visited[succBlock->id] = 1;
280                pendingList.emplace_back(succBlock->id);
281                dfsFatherIdx[succBlock->id] = bbIdToDfsTimestamp_[curBlockId];
282            }
283        }
284    };
285
286    while (!pendingList.empty()) {
287        size_t curBlockId = pendingList.back();
288        pendingList.pop_back();
289        basicBlockList.emplace_back(curBlockId);
290        bbIdToDfsTimestamp_[curBlockId] = timestamp++;
291        visitConnectedBlocks(graph_[curBlockId]->succs, curBlockId);
292        if (!graph_[curBlockId]->catches.empty()) {
293            visitConnectedBlocks(graph_[curBlockId]->catches, curBlockId);
294        }
295    }
296    for (size_t idx = 0; idx < basicBlockList.size(); idx++) {
297        bbDfsTimestampToIdx[basicBlockList[idx]] = idx;
298    }
299
300    immDom.resize(basicBlockList.size());
301    ComputeImmediateDominators(basicBlockList, dfsFatherIdx, immDom, bbDfsTimestampToIdx);
302}
303
304void BytecodeCircuitBuilder::BuildEntryBlock()
305{
306    BytecodeRegion &entryBlock = RegionAt(0);
307    BytecodeRegion &nextBlock = RegionAt(1);
308    entryBlock.succs.emplace_back(&nextBlock);
309    nextBlock.preds.emplace_back(&entryBlock);
310    entryBlock.bytecodeIterator_.Reset(this, 0, BytecodeIterator::INVALID_INDEX);
311}
312
313void BytecodeCircuitBuilder::BuildBasicBlock()
314{
315    auto &items = regionsInfo_.GetBlockItems();
316    size_t blockId = 1;
317    for (const auto &item : items) {
318        auto &curBlock = GetBasicBlockById(blockId);
319        curBlock.id = blockId;
320        curBlock.start = item.GetStartBcIndex();
321        if (blockId != 1) {
322            auto &prevBlock = RegionAt(blockId - 1);
323            ASSERT(curBlock.start >= 1);
324            prevBlock.end = curBlock.start - 1;
325            prevBlock.bytecodeIterator_.Reset(this, prevBlock.start, prevBlock.end);
326            // fall through
327            if (!item.IsHeadBlock()) {
328                curBlock.preds.emplace_back(&prevBlock);
329                prevBlock.succs.emplace_back(&curBlock);
330            }
331        }
332        blockId++;
333    }
334    auto &lastBlock = RegionAt(blockId - 1); // 1: last block
335    lastBlock.end = GetLastBcIndex();
336    lastBlock.bytecodeIterator_.Reset(this, lastBlock.start, lastBlock.end);
337}
338
339void BytecodeCircuitBuilder::BuildRegions(const ExceptionInfo &byteCodeException)
340{
341    auto blockSize = regionsInfo_.GetBlockItems().size();
342
343    // 1 : entry block. if the loop head is in the first bb block, the variables used in the head cannot correctly
344    // generate Phi nodes through the dominator-tree algorithm, resulting in an infinite loop. Therefore, an empty
345    // BB block is generated as an entry block
346    graph_.resize(blockSize + 1, nullptr);
347    for (size_t i = 0; i < graph_.size(); i++) {
348        graph_[i] = circuit_->chunk()->New<BytecodeRegion>(circuit_->chunk());
349    }
350
351    // build entry block
352    BuildEntryBlock();
353
354    // build basic block
355    BuildBasicBlock();
356
357    auto &splitItems = regionsInfo_.GetSplitItems();
358    for (const auto &item : splitItems) {
359        auto curIndex = regionsInfo_.FindBBIndexByBcIndex(item.startBcIndex);
360        auto &curBlock = GetBasicBlockById(curIndex);
361        auto predIndex = regionsInfo_.FindBBIndexByBcIndex(item.predBcIndex);
362        auto &predBlock = GetBasicBlockById(predIndex);
363        curBlock.preds.emplace_back(&predBlock);
364        predBlock.succs.emplace_back(&curBlock);
365    }
366
367    if (byteCodeException.size() != 0) {
368        BuildCatchBlocks(byteCodeException);
369    }
370    UpdateCFG();
371    if (HasTryCatch()) {
372        CollectTryPredsInfo();
373    }
374    RemoveUnreachableRegion();
375    if (NeedIrreducibleLoopCheck()) {
376        ReducibilityCheck();
377    }
378    if (IsLogEnabled() && !IsPreAnalysis()) {
379        PrintGraph(std::string("Update CFG [" + methodName_ + "]").c_str());
380    }
381    BuildCircuit();
382}
383
384void BytecodeCircuitBuilder::BuildCatchBlocks(const ExceptionInfo &byteCodeException)
385{
386    // try catch block associate
387    for (size_t i = 0; i < graph_.size(); i++) {
388        auto &bb = RegionAt(i);
389        auto startIndex = bb.start;
390        bool noThrow = true;
391        EnumerateBlock(bb, [&noThrow](const BytecodeInfo &bytecodeInfo) -> bool {
392            if (bytecodeInfo.IsGeneral()) {
393                if (!bytecodeInfo.NoThrow()) {
394                    noThrow = false;
395                    return false;
396                }
397            }
398            return true;
399        });
400        if (noThrow) {
401            continue;
402        }
403        const auto pc = pcOffsets_[startIndex];
404        for (auto it = byteCodeException.cbegin(); it != byteCodeException.cend(); it++) {
405            if (pc < it->startPc || pc >= it->endPc) {
406                continue;
407            }
408            // try block interval
409            const auto &catches = it->catches; // catches start pc
410            for (size_t j = i + 1; j < graph_.size(); j++) {
411                auto &catchBB = RegionAt(j);
412                const auto catchStart = pcOffsets_[catchBB.start];
413                if (std::find(catches.cbegin(), catches.cend(), catchStart) != catches.cend()) {
414                    bb.catches.insert(bb.catches.cbegin(), &catchBB);
415                }
416            }
417        }
418
419        // When there are multiple catch blocks in the current block, the set of catch blocks
420        // needs to be sorted to satisfy the order of execution of catch blocks.
421        bb.SortCatches();
422    }
423}
424
425void BytecodeCircuitBuilder::CollectTryPredsInfo()
426{
427    for (size_t i = 0; i < graph_.size(); i++) {
428        auto &bb = RegionAt(i);
429        if (bb.catches.empty()) {
430            continue;
431        } else if (bb.catches.size() > 1) { // 1: cache size
432            for (auto it = bb.catches.begin() + 1; it != bb.catches.end();) { // 1: invalid catch bb
433                bb.EraseThisBlock((*it)->trys);
434                it = bb.catches.erase(it);
435            }
436        }
437
438        EnumerateBlock(bb, [&bb](const BytecodeInfo &bytecodeInfo) -> bool {
439            if (bytecodeInfo.IsGeneral()) {
440                // if block which can throw exception has serval catchs block,
441                // only the innermost catch block is useful
442                ASSERT(bb.catches.size() == 1); // 1: cache size
443                if (!bytecodeInfo.NoThrow()) {
444                    bb.catches.at(0)->numOfStatePreds++;
445                }
446            }
447            return true;
448        });
449    }
450}
451
452void BytecodeCircuitBuilder::RemoveUnusedPredsInfo(BytecodeRegion& bb)
453{
454    EnumerateBlock(bb, [&bb](const BytecodeInfo &bytecodeInfo) -> bool {
455        if (bytecodeInfo.IsGeneral()) {
456            ASSERT(bb.catches.size() == 1); // 1: cache size
457            if (!bytecodeInfo.NoThrow()) {
458                bb.catches.at(0)->numOfStatePreds--;
459            }
460        }
461        return true;
462    });
463}
464
465void BytecodeCircuitBuilder::ClearUnreachableRegion(ChunkVector<BytecodeRegion*>& pendingList)
466{
467    auto bb = pendingList.back();
468    pendingList.pop_back();
469    for (auto it = bb->preds.begin(); it != bb->preds.end(); it++) {
470        ASSERT((*it)->numOfStatePreds >= 0);
471        if ((*it)->numOfStatePreds != 0) {
472            bb->EraseThisBlock((*it)->succs);
473        }
474    }
475    for (auto it = bb->succs.begin(); it != bb->succs.end(); it++) {
476        auto bbNext = *it;
477        ASSERT(bbNext->numOfStatePreds >= 0);
478        if (bbNext->numOfStatePreds != 0) {
479            bb->EraseThisBlock(bbNext->preds);
480            bbNext->numOfStatePreds--;
481            if (bbNext->numOfStatePreds == 0) {
482                pendingList.emplace_back(bbNext);
483            }
484        }
485    }
486    for (auto it = bb->trys.begin(); it != bb->trys.end(); it++) {
487        ASSERT((*it)->numOfStatePreds >= 0);
488        if ((*it)->numOfStatePreds != 0) {
489            bb->EraseThisBlock((*it)->catches);
490        }
491    }
492    for (auto it = bb->catches.begin(); it != bb->catches.end(); it++) {
493        auto bbNext = *it;
494        ASSERT(bbNext->numOfStatePreds >= 0);
495        if (bbNext->numOfStatePreds != 0) {
496            RemoveUnusedPredsInfo(*bb);
497            bb->EraseThisBlock(bbNext->trys);
498            if (bbNext->numOfStatePreds == 0) {
499                pendingList.emplace_back(bbNext);
500            }
501        }
502    }
503    bb->preds.clear();
504    bb->succs.clear();
505    bb->trys.clear();
506    bb->catches.clear();
507    numOfLiveBB_--;
508
509    RemoveIfInRpoList(bb);
510}
511
512void BytecodeCircuitBuilder::RemoveIfInRpoList(BytecodeRegion *bb)
513{
514    auto& rpoList = frameStateBuilder_.GetRpoList();
515    for (auto iter = rpoList.begin(); iter != rpoList.end(); iter++) {
516        if (*iter == bb->id) {
517            rpoList.erase(iter);
518            break;
519        }
520    }
521}
522
523void BytecodeCircuitBuilder::RemoveUnreachableRegion()
524{
525    numOfLiveBB_ = graph_.size();
526    ChunkVector<BytecodeRegion*> pendingList(circuit_->chunk());
527    for (size_t i = 1; i < graph_.size(); i++) { // 1: skip entry bb
528        auto &bb = RegionAt(i);
529        ASSERT(bb.numOfStatePreds >= 0);
530        if (bb.numOfStatePreds == 0) {
531            pendingList.emplace_back(&bb);
532        }
533    }
534    while (!pendingList.empty()) {
535        ClearUnreachableRegion(pendingList);
536    }
537}
538
539void BytecodeCircuitBuilder::ComputeNumOfLoopBack()
540{
541    for (size_t i = 0; i < graph_.size(); i++) {
542        auto &bb = RegionAt(i);
543        if (!IsEntryBlock(bb.id) && bb.numOfStatePreds == 0) {
544            continue;
545        }
546        for (auto &succ: bb.succs) {
547            if (succ->IsLoopBack(bb)) {
548                succ->numOfLoopBack++;
549            }
550        }
551        if (bb.catches.empty()) {
552            continue;
553        }
554
555        EnumerateBlock(bb, [&bb](const BytecodeInfo &bytecodeInfo) -> bool {
556            if (bytecodeInfo.IsGeneral() && !bytecodeInfo.NoThrow() && bb.catches.at(0)->IsLoopBack(bb)) {
557                // if block which can throw exception has serval catchs block,
558                // only the innermost catch block is useful
559                ASSERT(bb.catches.size() == 1); // 1: cache size
560                bb.catches.at(0)->numOfLoopBack++;
561            }
562            return true;
563        });
564    }
565}
566// Update CFG's predecessor, successor and try catch associations
567void BytecodeCircuitBuilder::UpdateCFG()
568{
569    for (size_t i = 0; i < graph_.size(); i++) {
570        auto &bb = RegionAt(i);
571        bb.preds.clear();
572        bb.trys.clear();
573    }
574    for (size_t i = 0; i < graph_.size(); i++) {
575        auto &bb = RegionAt(i);
576        for (auto &succ: bb.succs) {
577            succ->preds.emplace_back(&bb);
578            succ->numOfStatePreds++;
579        }
580        for (auto &catchBlock: bb.catches) {
581            catchBlock->trys.emplace_back(&bb);
582        }
583    }
584}
585
586// build circuit
587void BytecodeCircuitBuilder::BuildCircuitArgs()
588{
589    argAcc_.NewCommonArg(CommonArgIdx::GLUE, MachineType::I64, GateType::NJSValue());
590    if (!method_->IsFastCall()) {
591        argAcc_.NewCommonArg(CommonArgIdx::ACTUAL_ARGC, MachineType::I64, GateType::NJSValue());
592        argAcc_.NewCommonArg(CommonArgIdx::ACTUAL_ARGV, MachineType::ARCH, GateType::NJSValue());
593        auto funcIdx = static_cast<size_t>(CommonArgIdx::FUNC);
594        const size_t actualNumArgs = argAcc_.GetActualNumArgs();
595        // new actual argument gates
596        for (size_t argIdx = funcIdx; argIdx < actualNumArgs; argIdx++) {
597            argAcc_.NewArg(argIdx);
598        }
599    } else {
600        auto funcIdx = static_cast<size_t>(FastCallArgIdx::FUNC);
601        size_t actualNumArgs = static_cast<size_t>(FastCallArgIdx::NUM_OF_ARGS) + method_->GetNumArgsWithCallField();
602        for (size_t argIdx = funcIdx; argIdx < actualNumArgs; argIdx++) {
603            argAcc_.NewArg(argIdx);
604        }
605    }
606    argAcc_.CollectArgs();
607    BuildFrameArgs();
608}
609
610void BytecodeCircuitBuilder::BuildFrameArgs()
611{
612    UInt32PairAccessor accessor(0, 0);
613    auto metaData = circuit_->FrameArgs(accessor.ToValue());
614    size_t numArgs = metaData->GetNumIns();
615    std::vector<GateRef> args(numArgs, Circuit::NullGate());
616    size_t idx = 0;
617    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::FUNC);
618    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::NEW_TARGET);
619    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::THIS_OBJECT);
620    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::ACTUAL_ARGC);
621    args[idx++] = argAcc_.GetCommonArgGate(CommonArgIdx::ACTUAL_ARGV);
622    GateRef sharedConstpool = Circuit::NullGate();
623    GateRef unSharedConstpool = Circuit::NullGate();
624    GetCurrentConstpool(argAcc_.GetCommonArgGate(CommonArgIdx::FUNC), sharedConstpool, unSharedConstpool);
625    args[idx++] = sharedConstpool;
626    args[idx++] = unSharedConstpool;
627    args[idx++] = GetPreFrameArgs();
628    GateRef frameArgs = circuit_->NewGate(metaData, args);
629    argAcc_.SetFrameArgs(frameArgs);
630}
631
632void BytecodeCircuitBuilder::BuildOSRArgs()
633{
634    // offset -1 : glue
635    (void)circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_GLUE), MachineType::I64,
636                            {circuit_->GetArgRoot()}, GateType::NJSValue());
637    // offset -2 : argc
638    GateRef argc = method_->IsFastCall()
639                       ? circuit_->GetConstantGate(MachineType::I64, 0, GateType::NJSValue())
640                       : circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_ARGS), MachineType::I64,
641                                           {circuit_->GetArgRoot()}, GateType::TaggedValue());
642    // offset -3 : argv
643    GateRef argv = method_->IsFastCall()
644                       ? circuit_->GetConstantGate(MachineType::ARCH, 0, GateType::NJSValue())
645                       : circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_ARGV), MachineType::I64,
646                                           {circuit_->GetArgRoot()}, GateType::TaggedValue());
647    // offset -4 : func
648    (void)circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_FUNCTION), MachineType::I64,
649                            {circuit_->GetArgRoot()}, GateType::TaggedValue());
650    // offset -5 : new_target
651    GateRef newTarget =
652        method_->IsFastCall()
653            ? circuit_->GetConstantGate(MachineType::I64, JSTaggedValue::VALUE_UNDEFINED, GateType::UndefinedType())
654            : circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_NEW_TARGET), MachineType::I64,
655                                {circuit_->GetArgRoot()}, GateType::TaggedValue());
656    // offset -6 : this_object
657    (void)circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_THIS_OBJECT), MachineType::I64,
658                            {circuit_->GetArgRoot()}, GateType::TaggedValue());
659    // offset -7 : numargs
660    (void)circuit_->NewGate(circuit_->GetMetaBuilder()->InitVreg(INIT_VRGE_NUM_ARGS), MachineType::I64,
661                            {circuit_->GetArgRoot()}, GateType::TaggedValue());
662    for (size_t argIdx = 1; argIdx <= method_->GetNumArgsWithCallField(); argIdx++) {
663        // common args
664        argAcc_.NewArg(method_->IsFastCall() ? static_cast<size_t>(FastCallArgIdx::NUM_OF_ARGS)
665                                             : static_cast<size_t>(CommonArgIdx::NUM_OF_ARGS) + argIdx);
666    }
667
668    auto &args = argAcc_.args_;
669    if (args.size() == 0) {
670        GateAccessor(circuit_).GetArgsOuts(args);
671        std::reverse(args.begin(), args.end());
672        if (method_->IsFastCall() && args.size() >= static_cast<uint8_t>(FastCallArgIdx::NUM_OF_ARGS)) {
673            args.insert(args.begin() + static_cast<uint8_t>(CommonArgIdx::ACTUAL_ARGC), argc);
674            args.insert(args.begin() + static_cast<uint8_t>(CommonArgIdx::ACTUAL_ARGV), argv);
675            // 3: newtarget index
676            args.insert(args.begin() + static_cast<uint8_t>(CommonArgIdx::NEW_TARGET), newTarget);
677        }
678    }
679
680    BuildFrameArgs();
681}
682
683std::vector<GateRef> BytecodeCircuitBuilder::CreateGateInList(
684    const BytecodeInfo &info, const GateMetaData *meta)
685{
686    auto numValues = meta->GetNumIns();
687    const size_t length = meta->GetInValueStarts();
688    std::vector<GateRef> inList(numValues, Circuit::NullGate());
689    auto inputSize = info.inputs.size();
690    for (size_t i = 0; i < inputSize; i++) {
691        auto &input = info.inputs[i];
692        if (std::holds_alternative<ConstDataId>(input)) {
693            inList[i + length] = circuit_->GetConstantGate(MachineType::I64,
694                                                           std::get<ConstDataId>(input).GetId(),
695                                                           GateType::NJSValue());
696        } else if (std::holds_alternative<Immediate>(input)) {
697            inList[i + length] = circuit_->GetConstantGate(MachineType::I64,
698                                                           std::get<Immediate>(input).GetValue(),
699                                                           GateType::NJSValue());
700        } else if (std::holds_alternative<ICSlotId>(input)) {
701            inList[i + length] = circuit_->GetConstantGate(MachineType::I16,
702                                                           std::get<ICSlotId>(input).GetId(),
703                                                           GateType::NJSValue());
704        } else {
705            ASSERT(std::holds_alternative<VirtualRegister>(input));
706            continue;
707        }
708    }
709    if (info.AccIn()) {
710        inputSize++;
711    }
712    if (meta->HasFrameState()) {
713        inList[inputSize + length] = GetFrameArgs();
714    }
715    return inList;
716}
717
718GateRef BytecodeCircuitBuilder::NewConst(const BytecodeInfo &info)
719{
720    auto opcode = info.GetOpcode();
721    GateRef gate = 0;
722    switch (opcode) {
723        case EcmaOpcode::LDNAN:
724            gate = circuit_->GetConstantGate(MachineType::I64,
725                                             base::NumberHelper::GetNaN(),
726                                             GateType::NumberType());
727            break;
728        case EcmaOpcode::LDINFINITY:
729            gate = circuit_->GetConstantGate(MachineType::I64,
730                                             base::NumberHelper::GetPositiveInfinity(),
731                                             GateType::NumberType());
732            break;
733        case EcmaOpcode::LDUNDEFINED:
734            gate = circuit_->GetConstantGate(MachineType::I64,
735                                             JSTaggedValue::VALUE_UNDEFINED,
736                                             GateType::UndefinedType());
737            break;
738        case EcmaOpcode::LDNULL:
739            gate = circuit_->GetConstantGate(MachineType::I64,
740                                             JSTaggedValue::VALUE_NULL,
741                                             GateType::NullType());
742            break;
743        case EcmaOpcode::LDTRUE:
744            gate = circuit_->GetConstantGate(MachineType::I64,
745                                             JSTaggedValue::VALUE_TRUE,
746                                             GateType::BooleanType());
747            break;
748        case EcmaOpcode::LDFALSE:
749            gate = circuit_->GetConstantGate(MachineType::I64,
750                                             JSTaggedValue::VALUE_FALSE,
751                                             GateType::BooleanType());
752            break;
753        case EcmaOpcode::LDHOLE:
754            gate = circuit_->GetConstantGate(MachineType::I64,
755                                             JSTaggedValue::VALUE_HOLE,
756                                             GateType::TaggedValue());
757            break;
758        case EcmaOpcode::LDAI_IMM32:
759            gate = circuit_->GetConstantGate(MachineType::I64,
760                                             std::get<Immediate>(info.inputs[0]).ToJSTaggedValueInt(),
761                                             GateType::IntType());
762            break;
763        case EcmaOpcode::FLDAI_IMM64:
764            gate = circuit_->GetConstantGate(MachineType::I64,
765                                             std::get<Immediate>(info.inputs.at(0)).ToJSTaggedValueDouble(),
766                                             GateType::DoubleType());
767            break;
768        case EcmaOpcode::LDFUNCTION:
769            gate = argAcc_.GetCommonArgGate(CommonArgIdx::FUNC);
770            break;
771        case EcmaOpcode::LDNEWTARGET:
772            gate = argAcc_.GetCommonArgGate(CommonArgIdx::NEW_TARGET);
773            break;
774        case EcmaOpcode::LDTHIS:
775            gate = argAcc_.GetCommonArgGate(CommonArgIdx::THIS_OBJECT);
776            break;
777        default:
778            LOG_ECMA(FATAL) << "this branch is unreachable";
779            UNREACHABLE();
780    }
781    return gate;
782}
783
784void BytecodeCircuitBuilder::MergeThrowGate(BytecodeRegion &bb, uint32_t bcIndex)
785{
786    auto state = frameStateBuilder_.GetCurrentState();
787    auto depend = frameStateBuilder_.GetCurrentDepend();
788    if (!bb.catches.empty()) {
789        auto ifSuccess = circuit_->NewGate(circuit_->IfSuccess(), {state});
790        auto dependRelay = circuit_->NewGate(circuit_->DependRelay(), {ifSuccess, depend});
791        auto ifException = circuit_->NewGate(circuit_->IfException(), {state, depend});
792        frameStateBuilder_.UpdateStateDepend(ifException, ifException);
793        ASSERT(bb.catches.size() == 1); // 1: one catch
794        auto bbNext = bb.catches.at(0);
795        frameStateBuilder_.MergeIntoSuccessor(bb, *bbNext);
796        bbNext->expandedPreds.push_back({bb.id, bcIndex, true});
797        state = ifSuccess;
798        depend = dependRelay;
799    }
800    auto constant = circuit_->GetConstantGate(MachineType::I64,
801                                              JSTaggedValue::VALUE_EXCEPTION,
802                                              GateType::TaggedValue());
803    circuit_->NewGate(circuit_->Return(),
804        { state, depend, constant, circuit_->GetReturnRoot() });
805}
806
807void BytecodeCircuitBuilder::MergeExceptionGete(BytecodeRegion &bb,
808    const BytecodeInfo& bytecodeInfo, uint32_t bcIndex)
809{
810    auto state = frameStateBuilder_.GetCurrentState();
811    auto depend = frameStateBuilder_.GetCurrentDepend();
812    auto ifSuccess = circuit_->NewGate(circuit_->IfSuccess(), {state});
813    auto dependRelay = circuit_->NewGate(circuit_->DependRelay(), {ifSuccess, depend});
814    ASSERT(bb.catches.size() == 1); // 1: one catch
815    auto bbNext = bb.catches.at(0);
816    auto ifException = circuit_->NewGate(circuit_->IfException(), {state, depend});
817    frameStateBuilder_.UpdateStateDepend(ifException, ifException);
818    frameStateBuilder_.MergeIntoSuccessor(bb, *bbNext);
819    if (bytecodeInfo.GetOpcode() == EcmaOpcode::CREATEASYNCGENERATOROBJ_V8) {
820        bbNext->expandedPreds.push_back({bb.id, bcIndex + 1, true}); // 1: next pc
821    } else {
822        bbNext->expandedPreds.push_back({bb.id, bcIndex, true});
823    }
824    depend = dependRelay;
825    frameStateBuilder_.UpdateStateDepend(ifSuccess, depend);
826}
827
828void BytecodeCircuitBuilder::NewJSGate(BytecodeRegion &bb)
829{
830    auto &iterator = bb.GetBytecodeIterator();
831    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
832    GateRef state = frameStateBuilder_.GetCurrentState();
833    GateRef depend = frameStateBuilder_.GetCurrentDepend();
834    size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
835    GateRef gate = 0;
836    bool writable = !bytecodeInfo.NoSideEffects();
837    bool hasFrameState = bytecodeInfo.HasFrameState();
838    size_t pcOffset = GetPcOffset(iterator.Index());
839    auto methodOffset = method_->GetMethodId().GetOffset();
840    auto meta = circuit_->JSBytecode(
841        numValueInputs, methodOffset, bytecodeInfo.GetOpcode(), pcOffset, iterator.Index(), writable, hasFrameState);
842    std::vector<GateRef> inList = CreateGateInList(bytecodeInfo, meta);
843    if (bytecodeInfo.IsDef()) {
844        gate = circuit_->NewGate(meta, MachineType::I64, inList.size(),
845                                 inList.data(), GateType::AnyType());
846    } else {
847        gate = circuit_->NewGate(meta, MachineType::NOVALUE, inList.size(),
848                                 inList.data(), GateType::Empty());
849    }
850    byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
851    jsGatesToByteCode_[gate] = iterator.Index();
852    gateAcc_.NewIn(gate, 0, state);
853    gateAcc_.NewIn(gate, 1, depend);
854    frameStateBuilder_.UpdateStateDepend(gate, gate);
855    frameStateBuilder_.UpdateFrameValues(bytecodeInfo, iterator.Index(), gate);
856    if (bytecodeInfo.IsThrow()) {
857        MergeThrowGate(bb, iterator.Index());
858        return;
859    }
860
861    if (!bb.catches.empty() && !bytecodeInfo.NoThrow()) {
862        MergeExceptionGete(bb, bytecodeInfo, iterator.Index());
863    } else if (!bb.catches.empty()) {
864        frameStateBuilder_.GetOrOCreateMergedContext(bb.catches.at(0)->id);
865    }
866    if (bytecodeInfo.IsGeneratorRelative()) {
867        suspendAndResumeGates_.emplace_back(gate);
868    }
869}
870
871void BytecodeCircuitBuilder::NewJump(BytecodeRegion &bb)
872{
873    auto &iterator = bb.GetBytecodeIterator();
874    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
875    GateRef state = frameStateBuilder_.GetCurrentState();
876    GateRef depend = frameStateBuilder_.GetCurrentDepend();
877    size_t numValueInputs = bytecodeInfo.ComputeValueInputCount();
878    if (bytecodeInfo.IsCondJump() && bb.succs.size() == 2) { // 2: two succ
879        size_t pcOffset = GetPcOffset(iterator.Index());
880        auto methodOffset = method_->GetMethodId().GetOffset();
881        auto meta = circuit_->JSBytecode(
882            numValueInputs, methodOffset, bytecodeInfo.GetOpcode(), pcOffset, iterator.Index(), false, false);
883        auto numValues = meta->GetNumIns();
884        GateRef gate = circuit_->NewGate(meta, std::vector<GateRef>(numValues, Circuit::NullGate()));
885        gateAcc_.NewIn(gate, 0, state);
886        gateAcc_.NewIn(gate, 1, depend);
887        frameStateBuilder_.UpdateStateDepend(gate, gate);
888        frameStateBuilder_.UpdateFrameValues(bytecodeInfo, iterator.Index(), gate);
889
890        auto ifTrue = circuit_->NewGate(circuit_->IfTrue(), {gate});
891        auto trueRelay = circuit_->NewGate(circuit_->DependRelay(), {ifTrue, gate});
892        auto ifFalse = circuit_->NewGate(circuit_->IfFalse(), {gate});
893        auto falseRelay = circuit_->NewGate(circuit_->DependRelay(), {ifFalse, gate});
894        for (auto &bbNext: bb.succs) {
895            if (iterator.Index() + 1 == bbNext->start) {
896                frameStateBuilder_.UpdateStateDepend(ifFalse, falseRelay);
897                frameStateBuilder_.MergeIntoSuccessor(bb, *bbNext);
898                bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
899            } else {
900                frameStateBuilder_.UpdateStateDepend(ifTrue, trueRelay);
901                frameStateBuilder_.MergeIntoSuccessor(bb, *bbNext);
902                bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
903            }
904        }
905        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
906        jsGatesToByteCode_[gate] = iterator.Index();
907    } else {
908        ASSERT(bb.succs.size() == 1); // 1: only one succ if not condjump
909        auto &bbNext = bb.succs.at(0);
910        frameStateBuilder_.MergeIntoSuccessor(bb, *bbNext);
911        bbNext->expandedPreds.push_back({bb.id, iterator.Index(), false});
912    }
913
914    if (!bb.catches.empty()) {
915        frameStateBuilder_.GetOrOCreateMergedContext(bb.catches.at(0)->id);
916    }
917}
918
919GateRef BytecodeCircuitBuilder::NewReturn(BytecodeRegion &bb)
920{
921    ASSERT(bb.succs.empty());
922    auto &iterator = bb.GetBytecodeIterator();
923    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
924    GateRef state = frameStateBuilder_.GetCurrentState();
925    GateRef depend = frameStateBuilder_.GetCurrentDepend();
926    GateRef gate = Circuit::NullGate();
927    if (bytecodeInfo.GetOpcode() == EcmaOpcode::RETURN) {
928        // handle return.dyn bytecode
929        gate = circuit_->NewGate(circuit_->Return(),
930            { state, depend, Circuit::NullGate(), circuit_->GetReturnRoot() });
931        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
932        jsGatesToByteCode_[gate] = iterator.Index();
933    } else if (bytecodeInfo.GetOpcode() == EcmaOpcode::RETURNUNDEFINED) {
934        // handle returnundefined bytecode
935        auto constant = circuit_->GetConstantGate(MachineType::I64,
936                                                  JSTaggedValue::VALUE_UNDEFINED,
937                                                  GateType::TaggedValue());
938        gate = circuit_->NewGate(circuit_->Return(),
939            { state, depend, constant, circuit_->GetReturnRoot() });
940        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
941        jsGatesToByteCode_[gate] = iterator.Index();
942    }
943    return gate;
944}
945
946void BytecodeCircuitBuilder::NewByteCode(BytecodeRegion &bb)
947{
948    auto &iterator = bb.GetBytecodeIterator();
949    const BytecodeInfo& bytecodeInfo = iterator.GetBytecodeInfo();
950    FrameLiveOut* liveout;
951    auto bcId = iterator.Index();
952    if (bcId != 0 && iterator.IsInRange(bcId - 1)) {
953        liveout = frameStateBuilder_.GetOrOCreateBCEndLiveOut(bcId - 1);
954    } else {
955        liveout = frameStateBuilder_.GetOrOCreateBBLiveOut(bb.id);
956    }
957    frameStateBuilder_.AdvanceToNextBc(bytecodeInfo, liveout, bcId);
958    GateRef gate = Circuit::NullGate();
959    if (bytecodeInfo.IsSetConstant()) {
960        // handle bytecode command to get constants
961        gate = NewConst(bytecodeInfo);
962        byteCodeToJSGates_[iterator.Index()].emplace_back(gate);
963        jsGatesToByteCode_[gate] = iterator.Index();
964    } else if (bytecodeInfo.IsGeneral()) {
965        // handle general ecma.* bytecodes
966        NewJSGate(bb);
967    } else if (bytecodeInfo.IsJump()) {
968        // handle conditional jump and unconditional jump bytecodes
969        NewJump(bb);
970    } else if (bytecodeInfo.IsReturn()) {
971        // handle return.dyn and returnundefined bytecodes
972        gate = NewReturn(bb);
973    } else if (bytecodeInfo.IsMov()) {
974        frameStateBuilder_.UpdateMoveValues(bytecodeInfo);
975    } else if (!bytecodeInfo.IsDiscarded()) {
976        LOG_ECMA(FATAL) << "this branch is unreachable";
977        UNREACHABLE();
978    }
979    if (gate != Circuit::NullGate()) {
980        frameStateBuilder_.UpdateFrameValues(bytecodeInfo, iterator.Index(), gate);
981    }
982}
983
984void BytecodeCircuitBuilder::BuildSubCircuit()
985{
986    auto &entryBlock = RegionAt(0);
987    frameStateBuilder_.InitEntryBB(entryBlock);
988    auto& rpoList = frameStateBuilder_.GetRpoList();
989    for (auto &bbId: rpoList) {
990        auto &bb = RegionAt(bbId);
991        frameStateBuilder_.AdvanceToNextBB(bb);
992        if (IsEntryBlock(bb.id)) {
993            if (NeedCheckSafePointAndStackOver()) {
994                GateRef state = frameStateBuilder_.GetCurrentState();
995                GateRef depend = frameStateBuilder_.GetCurrentDepend();
996                auto stackCheck = circuit_->NewGate(circuit_->CheckSafePointAndStackOver(), {state, depend});
997                bb.dependCache = stackCheck;
998                frameStateBuilder_.UpdateStateDepend(stackCheck, stackCheck);
999            }
1000            auto &bbNext = RegionAt(bb.id + 1);
1001            frameStateBuilder_.MergeIntoSuccessor(bb, bbNext);
1002            bbNext.expandedPreds.push_back({bb.id, bb.end, false});
1003            continue;
1004        }
1005        if (!bb.trys.empty()) {
1006            GateRef state = frameStateBuilder_.GetCurrentState();
1007            GateRef depend = frameStateBuilder_.GetCurrentDepend();
1008            auto getException = circuit_->NewGate(circuit_->GetException(),
1009                MachineType::I64, {state, depend}, GateType::AnyType());
1010            frameStateBuilder_.UpdateAccumulator(getException);
1011            frameStateBuilder_.UpdateStateDepend(state, getException);
1012        }
1013        EnumerateBlock(bb, [this, &bb]
1014            (const BytecodeInfo &bytecodeInfo) -> bool {
1015            NewByteCode(bb);
1016            if (bytecodeInfo.IsJump() || bytecodeInfo.IsThrow()) {
1017                return false;
1018            }
1019            return true;
1020        });
1021        bool needFallThrough = true;
1022        if (!bb.IsEmptryBlock()) {
1023            const BytecodeInfo& bytecodeInfo = GetBytecodeInfo(bb.end);
1024            needFallThrough = bytecodeInfo.needFallThrough();
1025        }
1026        // fallThrough or empty merge bb
1027        if (needFallThrough) {
1028            ASSERT(bb.succs.size() == 1); // 1: fall through
1029            auto &bbNext = RegionAt(bb.succs[0]->id);
1030            frameStateBuilder_.MergeIntoSuccessor(bb, bbNext);
1031            bbNext.expandedPreds.push_back({bb.id, bb.end, false});
1032        }
1033    }
1034}
1035
1036bool BytecodeCircuitBuilder::FindOsrLoopHeadBB()
1037{
1038    int32_t loopBackBcIndex {-1};
1039    for (size_t k = 0; k < pcOffsets_.size(); k++) {
1040        if (static_cast<int32_t>(pcOffsets_[k] - pcOffsets_[0]) == osrOffset_) {
1041            loopBackBcIndex = static_cast<int32_t>(k);
1042        }
1043    }
1044    if (loopBackBcIndex == -1) {
1045        LOG_COMPILER(ERROR) << "Unable to find the loop back of OSR.";
1046        return false;
1047    }
1048    auto &rpoList = frameStateBuilder_.GetRpoList();
1049    for (auto &bbId : rpoList) {
1050        auto &bb = RegionAt(bbId);
1051        if (bb.end == static_cast<uint32_t>(loopBackBcIndex)) {
1052            frameStateBuilder_.SetOsrLoopHeadBB(bb);
1053            return true;
1054        }
1055    }
1056    LOG_COMPILER(ERROR) << "Unable to find the loop head bb of OSR.";
1057    return false;
1058}
1059
1060void BytecodeCircuitBuilder::GenDeoptAndReturnForOsrLoopExit(BytecodeRegion &osrLoopExitBB)
1061{
1062    frameStateBuilder_.AdvanceToNextBB(osrLoopExitBB, true);
1063    GateRef state = frameStateBuilder_.GetCurrentState();
1064    GateRef depend = frameStateBuilder_.GetCurrentDepend();
1065    std::string comment = Deoptimizier::DisplayItems(DeoptType::OSRLOOPEXIT);
1066    GateRef type =
1067        circuit_->GetConstantGate(MachineType::I64, static_cast<int64_t>(DeoptType::OSRLOOPEXIT), GateType::NJSValue());
1068    GateRef condition = circuit_->GetConstantGate(MachineType::I1, 0, GateType::NJSValue());
1069    GateRef deopt = circuit_->NewGate(circuit_->DeoptCheck(), MachineType::I1,
1070                                      {state, depend, condition, gateAcc_.GetFrameState(depend), type},
1071                                      GateType::NJSValue(), comment.c_str());
1072    GateRef dependRelay = circuit_->NewGate(circuit_->DependRelay(), {deopt, depend});
1073    GateRef undef =
1074        circuit_->GetConstantGate(MachineType::I64, JSTaggedValue::VALUE_UNDEFINED, GateType::TaggedValue());
1075    circuit_->NewGate(circuit_->Return(), {state, dependRelay, undef, circuit_->GetReturnRoot()});
1076}
1077
1078void BytecodeCircuitBuilder::CollectCacheBBforOSRLoop(BytecodeRegion *bb)
1079{
1080    catchBBOfOSRLoop_.insert(bb);
1081    for (BytecodeRegion *succBB : bb->succs) {
1082        CollectCacheBBforOSRLoop(succBB);
1083    }
1084}
1085
1086void BytecodeCircuitBuilder::HandleOsrLoopBody(BytecodeRegion &osrLoopBodyBB)
1087{
1088    if (!osrLoopBodyBB.trys.empty()) {
1089        GateRef state = frameStateBuilder_.GetCurrentState();
1090        GateRef depend = frameStateBuilder_.GetCurrentDepend();
1091        auto getException =
1092            circuit_->NewGate(circuit_->GetException(), MachineType::I64, {state, depend}, GateType::AnyType());
1093        frameStateBuilder_.UpdateAccumulator(getException);
1094        frameStateBuilder_.UpdateStateDepend(state, getException);
1095    }
1096    // collect catch BB.
1097    if (!osrLoopBodyBB.catches.empty()) {
1098        for (BytecodeRegion *targetBB : osrLoopBodyBB.catches) {
1099            CollectCacheBBforOSRLoop(targetBB);
1100        }
1101    }
1102    EnumerateBlock(osrLoopBodyBB, [this, &osrLoopBodyBB](const BytecodeInfo &bytecodeInfo) -> bool {
1103        NewByteCode(osrLoopBodyBB);
1104        if (bytecodeInfo.IsJump() || bytecodeInfo.IsThrow()) {
1105            return false;
1106        }
1107        return true;
1108    });
1109    bool needFallThrough = true;
1110    if (!osrLoopBodyBB.IsEmptryBlock()) {
1111        const BytecodeInfo &bytecodeInfo = GetBytecodeInfo(osrLoopBodyBB.end);
1112        needFallThrough = bytecodeInfo.needFallThrough();
1113    }
1114    // fallThrough or empty merge osrLoopBodyBB
1115    if (needFallThrough) {
1116        ASSERT(osrLoopBodyBB.succs.size() == 1);  // 1: fall through
1117        auto &bbNext = RegionAt(osrLoopBodyBB.succs[0]->id);
1118        frameStateBuilder_.MergeIntoSuccessor(osrLoopBodyBB, bbNext);
1119        bbNext.expandedPreds.push_back({osrLoopBodyBB.id, osrLoopBodyBB.end, false});
1120    }
1121}
1122
1123void BytecodeCircuitBuilder::BuildOsrCircuit()
1124{
1125    if (!FindOsrLoopHeadBB()) {
1126        LOG_COMPILER(FATAL) << "invalid osr offset";
1127    }
1128    circuit_->SetIsOsr();
1129    auto &entryBlock = RegionAt(0);
1130    frameStateBuilder_.InitEntryBB(entryBlock);
1131    std::set<size_t> osrLoopExitBBIds;
1132    auto &rpoList = frameStateBuilder_.GetRpoList();
1133    for (auto &bbId : rpoList) {
1134        auto &bb = RegionAt(bbId);
1135        if (frameStateBuilder_.IsOsrLoopExit(bb)) {
1136            // The loop exit BB is in front of the loop head BB. At this time,
1137            // the loop exit BB does not have the context object, and the processing of the loop exit BB is delayed.
1138            if (frameStateBuilder_.IsContextExists(bb.id)) {
1139                GenDeoptAndReturnForOsrLoopExit(bb);
1140            } else {
1141                osrLoopExitBBIds.insert(bbId);
1142            }
1143            continue;
1144        }
1145
1146        // Processes only the BBs related to the loop specified by the OSR.
1147        if (!IsEntryBlock(bb.id) && frameStateBuilder_.OutOfOsrLoop(bb) && !IsCacheBBOfOSRLoop(bb)) {
1148            continue;
1149        }
1150
1151        frameStateBuilder_.AdvanceToNextBB(bb);
1152        if (IsEntryBlock(bb.id)) {
1153            if (NeedCheckSafePointAndStackOver()) {
1154                GateRef state = frameStateBuilder_.GetCurrentState();
1155                GateRef depend = frameStateBuilder_.GetCurrentDepend();
1156                auto stackCheck = circuit_->NewGate(circuit_->CheckSafePointAndStackOver(), {state, depend});
1157                bb.dependCache = stackCheck;
1158                frameStateBuilder_.UpdateStateDepend(stackCheck, stackCheck);
1159            }
1160            auto *bbNext = &RegionAt(bb.id + 1);
1161            while (!IsEntryBlock(bbNext->id) && frameStateBuilder_.OutOfOsrLoop(*bbNext)) {
1162                bbNext = &RegionAt(bbNext->id + 1);
1163            }
1164            frameStateBuilder_.MergeIntoSuccessor(bb, *bbNext);
1165            bbNext->expandedPreds.push_back({bb.id, bb.end, false});
1166            continue;
1167        }
1168
1169        HandleOsrLoopBody(bb);
1170    }
1171    for (size_t bbId : osrLoopExitBBIds) {
1172        auto &bb = RegionAt(bbId);
1173        GenDeoptAndReturnForOsrLoopExit(bb);
1174    }
1175}
1176
1177void BytecodeCircuitBuilder::BuildCircuit()
1178{
1179    if (IsOSR()) {
1180        // create osr arg gates array
1181        BuildOSRArgs();
1182        frameStateBuilder_.DoBytecodeAnalysis();
1183        if (TerminateAnalysis()) {
1184            return;
1185        }
1186        // build states sub-circuit of osr block
1187        BuildOsrCircuit();
1188    } else {
1189        // create arg gates array
1190        BuildCircuitArgs();
1191        frameStateBuilder_.DoBytecodeAnalysis();
1192        if (TerminateAnalysis()) {
1193            return;
1194        }
1195        // build states sub-circuit of each block
1196        BuildSubCircuit();
1197    }
1198    if (IsLogEnabled()) {
1199        PrintGraph(std::string("Bytecode2Gate [" + methodName_ + "]").c_str());
1200        LOG_COMPILER(INFO) << "\033[34m" << "============= "
1201                           << "After bytecode2circuit lowering ["
1202                           << methodName_ << "]"
1203                           << " =============" << "\033[0m";
1204        circuit_->PrintAllGatesWithBytecode();
1205        LOG_COMPILER(INFO) << "\033[34m" << "=========================== End ===========================" << "\033[0m";
1206    }
1207}
1208
1209void BytecodeCircuitBuilder::PrintGraph(const char* title)
1210{
1211    LOG_COMPILER(INFO) << "======================== " << title << " ========================";
1212    for (size_t i = 0; i < graph_.size(); i++) {
1213        BytecodeRegion& bb = RegionAt(i);
1214        if (!IsEntryBlock(bb.id) && bb.numOfStatePreds == 0) {
1215            LOG_COMPILER(INFO) << "B" << bb.id << ":                               ;preds= invalid BB";
1216            LOG_COMPILER(INFO) << "\tBytecodePC: [" << std::to_string(bb.start) << ", "
1217                               << std::to_string(bb.end) << ")";
1218            continue;
1219        }
1220        std::string log("B" + std::to_string(bb.id) + ":                               ;preds= ");
1221        for (size_t k = 0; k < bb.preds.size(); ++k) {
1222            log += std::to_string(bb.preds[k]->id) + ", ";
1223        }
1224        LOG_COMPILER(INFO) << log;
1225        if (IsEntryBlock(bb.id)) {
1226            LOG_COMPILER(INFO) << "\tBytecodePC: Empty";
1227        } else {
1228            LOG_COMPILER(INFO) << "\tBytecodePC: [" << std::to_string(bb.start) << ", "
1229                << std::to_string(bb.end) << ")";
1230        }
1231
1232        std::string log1("\tSucces: ");
1233        for (size_t j = 0; j < bb.succs.size(); j++) {
1234            log1 += std::to_string(bb.succs[j]->id) + ", ";
1235        }
1236        LOG_COMPILER(INFO) << log1;
1237
1238        for (size_t j = 0; j < bb.catches.size(); j++) {
1239            LOG_COMPILER(INFO) << "\tcatch [: " << std::to_string(bb.catches[j]->start) << ", "
1240                               << std::to_string(bb.catches[j]->end) << ")";
1241        }
1242
1243        std::string log2("\tTrys: ");
1244        for (auto tryBlock: bb.trys) {
1245            log2 += std::to_string(tryBlock->id) + " , ";
1246        }
1247        LOG_COMPILER(INFO) << log2;
1248
1249        PrintBytecodeInfo(bb);
1250        LOG_COMPILER(INFO) << "";
1251    }
1252}
1253
1254void BytecodeCircuitBuilder::PrintBytecodeInfo(BytecodeRegion& bb)
1255{
1256    if (IsEntryBlock(bb.id)) {
1257        LOG_COMPILER(INFO) << "\tBytecode[] = Empty";
1258        return;
1259    }
1260    LOG_COMPILER(INFO) << "\tBytecode[] = ";
1261    EnumerateBlock(bb, [&](const BytecodeInfo &bytecodeInfo) -> bool {
1262        auto &iterator = bb.GetBytecodeIterator();
1263        std::string log;
1264        log += std::string("\t\t< ") + std::to_string(iterator.Index()) + ": ";
1265        log += GetEcmaOpcodeStr(iterator.GetBytecodeInfo().GetOpcode()) + ", " + "In=[";
1266        if (bytecodeInfo.AccIn()) {
1267            log += "acc,";
1268        }
1269        for (const auto &in: bytecodeInfo.inputs) {
1270            if (std::holds_alternative<VirtualRegister>(in)) {
1271                log += std::to_string(std::get<VirtualRegister>(in).GetId()) + ",";
1272            }
1273        }
1274        log += "], Out=[";
1275        if (bytecodeInfo.AccOut()) {
1276            log += "acc,";
1277        }
1278        for (const auto &out: bytecodeInfo.vregOut) {
1279            log += std::to_string(out) + ",";
1280        }
1281        log += "] >";
1282        LOG_COMPILER(INFO) << log;
1283
1284        auto gate = GetGateByBcIndex(iterator.Index());
1285        if (gate != Circuit::NullGate()) {
1286            this->gateAcc_.ShortPrint(gate);
1287        }
1288        return true;
1289    });
1290}
1291}  // namespace panda::ecmascript::kungfu
1292