1/**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#include "basicblock.h"
17#include "graph.h"
18#include "optimizer/analysis/loop_analyzer.h"
19#include "optimizer/analysis/dominators_tree.h"
20
21namespace panda::compiler {
22class Inst;
23BasicBlock::BasicBlock(Graph *graph, uint32_t guest_pc)
24    : graph_(graph),
25      preds_(graph_->GetAllocator()->Adapter()),
26      succs_(graph_->GetAllocator()->Adapter()),
27      dom_blocks_(graph_->GetAllocator()->Adapter()),
28      guest_pc_(guest_pc)
29{
30}
31
32bool BasicBlock::IsStartBlock() const
33{
34    return (graph_->GetStartBlock() == this);
35}
36bool BasicBlock::IsEndBlock() const
37{
38    return (graph_->GetEndBlock() == this);
39}
40bool BasicBlock::IsPseudoControlFlowBlock() const
41{
42    return IsStartBlock() || IsEndBlock() || IsTryBegin() || IsTryEnd() || IsCatchBegin();
43}
44
45bool BasicBlock::IsLoopHeader() const
46{
47    ASSERT(GetLoop() != nullptr);
48    return (GetLoop()->GetHeader() == this);
49}
50
51BasicBlock *BasicBlock::SplitBlockAfterInstruction(Inst *inst, bool make_edge)
52{
53    ASSERT(inst != nullptr);
54    ASSERT(inst->GetBasicBlock() == this);
55    ASSERT(!IsStartBlock() && !IsEndBlock());
56
57    auto next_inst = inst->GetNext();
58    auto new_bb = GetGraph()->CreateEmptyBlock((next_inst != nullptr) ? next_inst->GetPc() : INVALID_PC);
59    new_bb->SetAllFields(this->GetAllFields());
60    GetLoop()->AppendBlock(new_bb);
61
62    for (; next_inst != nullptr; next_inst = next_inst->GetNext()) {
63        new_bb->AppendInst(next_inst);
64    }
65    inst->SetNext(nullptr);
66    last_inst_ = inst;
67    if (inst->IsPhi()) {
68        first_inst_ = nullptr;
69    }
70    for (auto succ : GetSuccsBlocks()) {
71        succ->ReplacePred(this, new_bb);
72    }
73    GetSuccsBlocks().clear();
74
75    ASSERT(GetSuccsBlocks().empty());
76    if (make_edge) {
77        AddSucc(new_bb);
78    }
79    return new_bb;
80}
81
82void BasicBlock::AddSucc(BasicBlock *succ, bool can_add_empty_block)
83{
84    auto it = std::find(succs_.begin(), succs_.end(), succ);
85    ASSERT_PRINT(it == succs_.end() || can_add_empty_block, "Uncovered case where empty block needed to fix CFG");
86    if (it != succs_.end() && can_add_empty_block) {
87        // If edge already exists we create empty block on it
88        auto empty_bb = GetGraph()->CreateEmptyBlock(GetGuestPc());
89        ReplaceSucc(succ, empty_bb);
90        succ->ReplacePred(this, empty_bb);
91    }
92    succs_.push_back(succ);
93    succ->GetPredsBlocks().push_back(this);
94}
95
96void BasicBlock::ReplaceSucc(const BasicBlock *prev_succ, BasicBlock *new_succ, bool can_add_empty_block)
97{
98    auto it = std::find(succs_.begin(), succs_.end(), new_succ);
99    ASSERT_PRINT(it == succs_.end() || can_add_empty_block, "Uncovered case where empty block needed to fix CFG");
100    if (it != succs_.end() && can_add_empty_block) {
101        // If edge already exists we create empty block on it
102        auto empty_bb = GetGraph()->CreateEmptyBlock(GetGuestPc());
103        ReplaceSucc(new_succ, empty_bb);
104        new_succ->ReplacePred(this, empty_bb);
105    }
106    succs_[GetSuccBlockIndex(prev_succ)] = new_succ;
107    new_succ->preds_.push_back(this);
108}
109
110BasicBlock *BasicBlock::InsertNewBlockToSuccEdge(BasicBlock *succ)
111{
112    auto block = GetGraph()->CreateEmptyBlock(succ->GetGuestPc());
113    this->ReplaceSucc(succ, block);
114    succ->ReplacePred(this, block);
115    return block;
116}
117
118BasicBlock *BasicBlock::InsertEmptyBlockBefore()
119{
120    auto block = GetGraph()->CreateEmptyBlock(this->GetGuestPc());
121    for (auto pred : preds_) {
122        pred->ReplaceSucc(this, block);
123        this->RemovePred(pred);
124    }
125    block->AddSucc(this);
126    return block;
127}
128
129void BasicBlock::InsertBlockBeforeSucc(BasicBlock *block, BasicBlock *succ)
130{
131    this->ReplaceSucc(succ, block);
132    succ->ReplacePred(this, block);
133}
134
135static void RemovePhiProcessing(BasicBlock *bb, BasicBlock *succ)
136{
137    size_t num_preds = bb->GetPredsBlocks().size();
138
139    for (auto phi : succ->PhiInsts()) {
140        auto index = phi->CastToPhi()->GetPredBlockIndex(bb);
141        auto inst = phi->GetInput(index).GetInst();
142        if (inst->GetBasicBlock() == bb) {  // When INST is from empty basic block ...
143            ASSERT(inst->IsPhi());
144            // ... we have to copy it's inputs into corresponding inputs of PHI
145            auto pred_bb = bb->GetPredBlockByIndex(0);
146            phi->SetInput(index, inst->CastToPhi()->GetPhiInput(pred_bb));
147            for (size_t i = 1; i < num_preds; i++) {
148                pred_bb = bb->GetPredBlockByIndex(i);
149                phi->AppendInput(inst->CastToPhi()->GetPhiInput(pred_bb));
150            }
151        } else {  // otherwise, just copy inputs for new arrived predecessors
152            for (size_t i = 1; i < num_preds; i++) {
153                phi->AppendInput(inst);
154            }
155        }
156    }
157    // And now we should remove Phis from the empty block
158    for (auto phi : bb->PhiInstsSafe()) {
159        bb->RemoveInst(phi);
160    }
161}
162
163// Remove empty block with one successor, may have more than one predecessors and Phi(s)
164void BasicBlock::RemoveEmptyBlock(bool irr_loop)
165{
166    ASSERT(GetFirstInst() == nullptr);
167    ASSERT(!GetPredsBlocks().empty());
168    ASSERT(GetSuccsBlocks().size() == 1);
169    auto succ = succs_[0];
170
171    // Save old amount of predecessors in successor block
172    size_t succ_preds_num = succ->GetPredsBlocks().size();
173
174    size_t num_preds = preds_.size();
175    // If empty block had more than one predecessors
176    if (num_preds > 1) {
177        if (succ_preds_num > 1) {
178            // We have to process Phi instructions in successor block in a special way
179            RemovePhiProcessing(this, succ);
180        } else {  // successor didn't have other predecessors, we are moving Phi(s) into successor
181            ASSERT(!succ->HasPhi());
182            for (auto phi : PhiInstsSafe()) {
183                succ->AppendPhi(phi);
184            }
185            first_phi_ = nullptr;
186            last_inst_ = nullptr;
187        }
188    }
189
190    // Set successor for all predecessor blocks, at the same time in successor we replace one predecessor
191    // and add others to the end (if there were many of them in empty block)
192    auto pred = preds_[0];
193    pred->succs_[pred->GetSuccBlockIndex(this)] = succ;
194    succ->preds_[succ->GetPredBlockIndex(this)] = pred;
195    for (size_t i = 1; i < num_preds; ++i) {
196        pred = preds_[i];
197        pred->succs_[pred->GetSuccBlockIndex(this)] = succ;
198        succ->preds_.push_back(pred);
199    }
200
201    ASSERT(GetLastInst() == nullptr);
202    ASSERT(GetLoop()->IsIrreducible() == irr_loop);
203    // N.B. info about Irreducible loop can not be fixed on the fly
204    if (!irr_loop) {
205        RemoveFixLoopInfo();
206    }
207    // Finally clean lists
208    preds_.clear();
209    succs_.clear();
210}
211
212static void FixLoopInfoHelper(BasicBlock *bb)
213{
214    ASSERT(!bb->GetPredsBlocks().empty());
215    auto loop = bb->GetLoop();
216    auto first_pred = bb->GetPredBlockByIndex(0);
217    // Do not dup back-edge
218    if (loop->HasBackEdge(first_pred)) {
219        loop->RemoveBackEdge(bb);
220    } else {
221        loop->ReplaceBackEdge(bb, first_pred);
222    }
223    // If empty block has more than 1 predecessor, append others to the loop back-edges' list
224    for (size_t i = 1; i < bb->GetPredsBlocks().size(); ++i) {
225        auto pred = bb->GetPredBlockByIndex(i);
226        if (!loop->HasBackEdge(pred)) {
227            loop->AppendBackEdge(pred);
228        }
229    }
230}
231
232void BasicBlock::RemoveFixLoopInfo()
233{
234    auto loop = GetLoop();
235    ASSERT(loop != nullptr);
236    ASSERT(!loop->IsIrreducible());
237    while (!loop->IsRoot()) {
238        if (loop->HasBackEdge(this)) {
239            FixLoopInfoHelper(this);
240        }
241        loop = loop->GetOuterLoop();
242    }
243    if (this == GetLoop()->GetHeader()) {
244        GetLoop()->MoveHeaderToSucc();
245    }
246    GetLoop()->RemoveBlock(this);
247}
248
249/**
250 * Join single successor into single predecessor.
251 * Block must have one successor, and its successor must have one predecessor (this block).
252 * EXAMPLE:
253 *              [1]
254 *               |
255 *              [2]
256 *
257 * turns into this:
258 *              [1']
259 */
260void BasicBlock::JoinSuccessorBlock()
261{
262    ASSERT(!IsStartBlock());
263
264    ASSERT(GetSuccsBlocks().size() == 1);
265    auto succ = GetSuccessor(0);
266    ASSERT(!succ->IsEndBlock());
267
268    ASSERT(succ->GetPredsBlocks().size() == 1);
269    ASSERT(succ->GetPredBlockByIndex(0) == this);
270
271    // moving instructions from successor
272    ASSERT(!succ->HasPhi());
273    for (auto succ_inst : succ->Insts()) {
274        AppendInst(succ_inst);
275    }
276
277    // moving successor blocks from the successor
278    GetSuccsBlocks().clear();
279    for (auto succ_succ : succ->GetSuccsBlocks()) {
280        succ_succ->ReplacePred(succ, this);
281    }
282
283    // fixing loop information
284    // invariant: succ has one predecessor, so it cannot be a loop header
285    auto loop = succ->GetLoop();
286    ASSERT(loop != nullptr);
287    // Irreducible loop can not be fixed on the fly
288    if (loop->IsIrreducible()) {
289        GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
290    } else {
291        // edge can have 2 successors, so it can be back-edge in 2 loops: own loop and outer loop
292        if (loop->HasBackEdge(succ)) {
293            loop->ReplaceBackEdge(succ, this);
294        }
295        if (auto outer_loop = loop->GetOuterLoop()) {
296            if (outer_loop->HasBackEdge(succ)) {
297                outer_loop->ReplaceBackEdge(succ, this);
298            }
299        }
300
301        for (auto inner_loop : loop->GetInnerLoops()) {
302            if (inner_loop->GetPreHeader() == succ) {
303                inner_loop->SetPreHeader(this);
304            }
305        }
306        loop->RemoveBlock(succ);
307    }
308
309    succ->first_inst_ = nullptr;
310    succ->last_inst_ = nullptr;
311    succ->GetPredsBlocks().clear();
312    succ->GetSuccsBlocks().clear();
313
314    this->bit_fields_ |= succ->bit_fields_;
315    // TODO (a.popov) replace by assert
316    if (succ->try_id_ != INVALID_ID) {
317        this->try_id_ = succ->try_id_;
318    }
319    GetGraph()->RemoveEmptyBlock(succ);
320}
321
322void BasicBlock::SelectsFixLoopInfo(BasicBlock *select_bb, BasicBlock *other)
323{
324    // invariant: 'this' block has one predecessor, so it cannot be a loop header
325    auto loop = GetLoop();
326    ASSERT(loop != nullptr);
327    // Irreducible loop can not be fixed on the fly
328    if (loop->IsIrreducible()) {
329        GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
330    } else {
331        if (loop->HasBackEdge(this)) {
332            loop->RemoveBackEdge(this);
333        }
334        for (auto inner_loop : loop->GetInnerLoops()) {
335            if (inner_loop->GetPreHeader() == this) {
336                inner_loop->SetPreHeader(select_bb);
337                break;
338            }
339        }
340        loop->RemoveBlock(this);
341    }
342
343    // Remove outgoing 'this->other' edge
344    RemoveSucc(other);
345    other->RemovePred(this);
346    // Disconnect
347    GetGraph()->RemoveEmptyBlock(this);
348}
349
350void BasicBlock::AppendPhi(Inst *inst)
351{
352    ASSERT_PRINT(inst->IsPhi(), "Instruction must be phi");
353    inst->SetBasicBlock(this);
354    if (first_phi_ == nullptr) {
355        inst->SetNext(first_inst_);
356        if (first_inst_ != nullptr) {
357            first_inst_->SetPrev(inst);
358        }
359        first_phi_ = inst;
360        if (last_inst_ == nullptr) {
361            last_inst_ = inst;
362        }
363    } else {
364        if (first_inst_ != nullptr) {
365            Inst *prev = first_inst_->GetPrev();
366            ASSERT_PRINT(prev && prev->IsPhi(), "There is no phi in the block");
367            inst->SetPrev(prev);
368            prev->SetNext(inst);
369            inst->SetNext(first_inst_);
370            first_inst_->SetPrev(inst);
371        } else {
372            ASSERT_PRINT(last_inst_ && last_inst_->IsPhi(),
373                         "If first_phi is defined and first_inst is undefined, last_inst must be phi");
374            last_inst_->SetNext(inst);
375            inst->SetPrev(last_inst_);
376            last_inst_ = inst;
377        }
378    }
379}
380
381template <bool to_end>
382void BasicBlock::AddInst(Inst *inst)
383{
384    ASSERT_PRINT(!inst->IsPhi(), "Instruction mustn't be phi");
385    inst->SetBasicBlock(this);
386    if (first_inst_ == nullptr) {
387        inst->SetPrev(last_inst_);
388        if (last_inst_ != nullptr) {
389            ASSERT(last_inst_->IsPhi());
390            last_inst_->SetNext(inst);
391        }
392        first_inst_ = inst;
393        last_inst_ = inst;
394    } else {
395        // NOLINTNEXTLINE(readability-braces-around-statements)
396        if constexpr (to_end) {
397            ASSERT_PRINT(last_inst_, "Last instruction is undefined");
398            inst->SetPrev(last_inst_);
399            last_inst_->SetNext(inst);
400            last_inst_ = inst;
401            // NOLINTNEXTLINE(readability-misleading-indentation)
402        } else {
403            auto first_prev = first_inst_->GetPrev();
404            if (first_prev != nullptr) {
405                first_prev->SetNext(inst);
406            }
407            inst->SetPrev(first_prev);
408            inst->SetNext(first_inst_);
409            first_inst_->SetPrev(inst);
410            first_inst_ = inst;
411        }
412    }
413}
414
415void BasicBlock::AppendRangeInst(Inst *range_first, Inst *range_last)
416{
417#ifndef NDEBUG
418    ASSERT(range_first && range_last && range_first->IsDominate(range_last));
419    ASSERT(range_first->GetPrev() == nullptr);
420    ASSERT(range_last->GetNext() == nullptr);
421    auto inst_db = range_first;
422    while (inst_db != range_last) {
423        ASSERT_PRINT(!inst_db->IsPhi(), "Instruction mustn't be phi");
424        ASSERT_PRINT(inst_db->GetBasicBlock() == this, "Inst::SetBasicBlock() should be called beforehand");
425        inst_db = inst_db->GetNext();
426    }
427    ASSERT_PRINT(!inst_db->IsPhi(), "Instruction mustn't be phi");
428    ASSERT_PRINT(inst_db->GetBasicBlock() == this, "Inst::SetBasicBlock() should be called beforehand");
429#endif
430
431    if (first_inst_ == nullptr) {
432        range_first->SetPrev(last_inst_);
433        if (last_inst_ != nullptr) {
434            ASSERT(last_inst_->IsPhi());
435            last_inst_->SetNext(range_first);
436        }
437        first_inst_ = range_first;
438        last_inst_ = range_last;
439    } else {
440        ASSERT_PRINT(last_inst_, "Last instruction is undefined");
441        range_first->SetPrev(last_inst_);
442        last_inst_->SetNext(range_first);
443        last_inst_ = range_last;
444    }
445}
446
447void BasicBlock::InsertAfter(Inst *inst, Inst *after)
448{
449    ASSERT(inst && after);
450    ASSERT(inst->IsPhi() == after->IsPhi());
451    ASSERT(after->GetBasicBlock() == this);
452    ASSERT(inst->GetBasicBlock() == nullptr);
453    inst->SetBasicBlock(this);
454    Inst *next = after->GetNext();
455    inst->SetPrev(after);
456    inst->SetNext(next);
457    after->SetNext(inst);
458    if (next != nullptr) {
459        next->SetPrev(inst);
460    } else {
461        ASSERT(after == last_inst_);
462        last_inst_ = inst;
463    }
464}
465
466void BasicBlock::InsertBefore(Inst *inst, Inst *before)
467{
468    ASSERT(inst && before);
469    ASSERT(inst->IsPhi() == before->IsPhi());
470    ASSERT(before->GetBasicBlock() == this);
471    ASSERT(inst->GetBasicBlock() == nullptr);
472    inst->SetBasicBlock(this);
473    Inst *prev = before->GetPrev();
474    inst->SetPrev(prev);
475    inst->SetNext(before);
476    before->SetPrev(inst);
477    if (prev != nullptr) {
478        prev->SetNext(inst);
479    }
480    if (before == first_phi_) {
481        first_phi_ = inst;
482    }
483    if (before == first_inst_) {
484        first_inst_ = inst;
485    }
486}
487
488void BasicBlock::InsertRangeBefore(Inst *range_first, Inst *range_last, Inst *before)
489{
490#ifndef NDEBUG
491    ASSERT(range_first && range_last && range_first->IsDominate(range_last));
492    ASSERT(before && !before->IsPhi());
493    ASSERT(range_first->GetPrev() == nullptr);
494    ASSERT(range_last->GetNext() == nullptr);
495    ASSERT(before->GetBasicBlock() == this);
496    auto inst_db = range_first;
497    while (inst_db != range_last) {
498        ASSERT_PRINT(!inst_db->IsPhi(), "Instruction mustn't be phi");
499        ASSERT_PRINT(inst_db->GetBasicBlock() == this, "Inst::SetBasicBlock() should be called beforehand");
500        inst_db = inst_db->GetNext();
501    }
502    ASSERT_PRINT(!inst_db->IsPhi(), "Instruction mustn't be phi");
503    ASSERT_PRINT(inst_db->GetBasicBlock() == this, "Inst::SetBasicBlock() should be called beforehand");
504#endif
505
506    Inst *prev = before->GetPrev();
507    range_first->SetPrev(prev);
508    range_last->SetNext(before);
509    before->SetPrev(range_last);
510    if (prev != nullptr) {
511        prev->SetNext(range_first);
512    }
513    if (before == first_inst_) {
514        first_inst_ = range_first;
515    }
516}
517
518void BasicBlock::ReplaceInst(Inst *old_inst, Inst *new_inst)
519{
520    ASSERT(old_inst && new_inst);
521    ASSERT(old_inst->IsPhi() == new_inst->IsPhi());
522    ASSERT(old_inst->GetBasicBlock() == this);
523    ASSERT(new_inst->GetBasicBlock() == nullptr);
524    new_inst->SetBasicBlock(this);
525    Inst *prev = old_inst->GetPrev();
526    Inst *next = old_inst->GetNext();
527
528    old_inst->SetBasicBlock(nullptr);
529    if (prev != nullptr) {
530        prev->SetNext(new_inst);
531    }
532    if (next != nullptr) {
533        next->SetPrev(new_inst);
534    }
535    new_inst->SetPrev(prev);
536    new_inst->SetNext(next);
537    if (first_phi_ == old_inst) {
538        first_phi_ = new_inst;
539    }
540    if (first_inst_ == old_inst) {
541        first_inst_ = new_inst;
542    }
543    if (last_inst_ == old_inst) {
544        last_inst_ = new_inst;
545    }
546
547    if (graph_->IsInstThrowable(old_inst)) {
548        graph_->ReplaceThrowableInst(old_inst, new_inst);
549    }
550}
551
552void BasicBlock::EraseInst(Inst *inst, [[maybe_unused]] bool will_be_moved)
553{
554    ASSERT(will_be_moved || !GetGraph()->IsInstThrowable(inst));
555    Inst *prev = inst->GetPrev();
556    Inst *next = inst->GetNext();
557
558    ASSERT(inst->GetBasicBlock() == this);
559    inst->SetBasicBlock(nullptr);
560    if (prev != nullptr) {
561        prev->SetNext(next);
562    }
563    if (next != nullptr) {
564        next->SetPrev(prev);
565    }
566    inst->SetPrev(nullptr);
567    inst->SetNext(nullptr);
568    if (inst == first_phi_) {
569        first_phi_ = (next != nullptr && next->IsPhi()) ? next : nullptr;
570    }
571    if (inst == first_inst_) {
572        first_inst_ = next;
573    }
574    if (inst == last_inst_) {
575        last_inst_ = prev;
576    }
577}
578
579void BasicBlock::RemoveInst(Inst *inst)
580{
581    inst->RemoveUsers();
582    ASSERT(!inst->HasUsers());
583    inst->RemoveInputs();
584    if (inst->GetOpcode() == Opcode::Constant) {
585        graph_->RemoveConstFromList(static_cast<ConstantInst *>(inst));
586    }
587
588    if (graph_->IsInstThrowable(inst)) {
589        graph_->RemoveThrowableInst(inst);
590    }
591    EraseInst(inst);
592}
593
594void BasicBlock::Clear()
595{
596    for (auto inst : AllInstsSafeReverse()) {
597        RemoveInst(inst);
598    }
599}
600
601/*
602 * Check if this block is dominate other
603 */
604bool BasicBlock::IsDominate(const BasicBlock *other) const
605{
606    if (other == this) {
607        return true;
608    }
609    ASSERT(GetGraph()->IsAnalysisValid<DominatorsTree>());
610    BasicBlock *dom_block = other->GetDominator();
611    while (dom_block != nullptr) {
612        if (dom_block == this) {
613            return true;
614        }
615        // Otherwise we are in infinite loop!?
616        ASSERT(dom_block != dom_block->GetDominator());
617        dom_block = dom_block->GetDominator();
618    }
619    return false;
620}
621
622BasicBlock *BasicBlock::CreateImmediateDominator()
623{
624    ASSERT(GetGraph()->IsAnalysisValid<DominatorsTree>());
625    auto dominator = GetGraph()->CreateEmptyBlock();
626    GetGraph()->GetAnalysis<DominatorsTree>().SetValid(true);
627    if (GetDominator() != nullptr) {
628        GetDominator()->RemoveDominatedBlock(this);
629        GetDominator()->AddDominatedBlock(dominator);
630        dominator->SetDominator(GetDominator());
631    }
632    dominator->AddDominatedBlock(this);
633    SetDominator(dominator);
634    return dominator;
635}
636
637BasicBlock *BasicBlock::GetDominator() const
638{
639    ASSERT(GetGraph()->IsAnalysisValid<DominatorsTree>());
640    return dominator_;
641}
642
643const ArenaVector<BasicBlock *> &BasicBlock::GetDominatedBlocks() const
644{
645    ASSERT(GetGraph()->IsAnalysisValid<DominatorsTree>());
646    return dom_blocks_;
647}
648
649PhiInstIter BasicBlock::PhiInsts() const
650{
651    return PhiInstIter(*this);
652}
653InstIter BasicBlock::Insts() const
654{
655    return InstIter(*this);
656}
657AllInstIter BasicBlock::AllInsts() const
658{
659    return AllInstIter(*this);
660}
661
662InstReverseIter BasicBlock::InstsReverse() const
663{
664    return InstReverseIter(*this);
665}
666
667PhiInstSafeIter BasicBlock::PhiInstsSafe() const
668{
669    return PhiInstSafeIter(*this);
670}
671InstSafeIter BasicBlock::InstsSafe() const
672{
673    return InstSafeIter(*this);
674}
675AllInstSafeIter BasicBlock::AllInstsSafe() const
676{
677    return AllInstSafeIter(*this);
678}
679
680PhiInstSafeReverseIter BasicBlock::PhiInstsSafeReverse() const
681{
682    return PhiInstSafeReverseIter(*this);
683}
684InstSafeReverseIter BasicBlock::InstsSafeReverse() const
685{
686    return InstSafeReverseIter(*this);
687}
688AllInstSafeReverseIter BasicBlock::AllInstsSafeReverse() const
689{
690    return AllInstSafeReverseIter(*this);
691}
692
693template void BasicBlock::AddInst<false>(Inst *inst);
694template void BasicBlock::AddInst<true>(Inst *inst);
695
696void BasicBlock::InsertBlockBefore(BasicBlock *block)
697{
698    for (auto pred : GetPredsBlocks()) {
699        pred->ReplaceSucc(this, block);
700    }
701    GetPredsBlocks().clear();
702    block->AddSucc(this);
703}
704
705BasicBlock *BasicBlock::Clone(Graph *target_graph) const
706{
707    BasicBlock *clone = nullptr;
708#ifndef NDEBUG
709    if (GetGraph() == target_graph) {
710        clone = target_graph->CreateEmptyBlock();
711    } else {
712        clone = target_graph->CreateEmptyBlock(GetId(), GetGuestPc());
713    }
714#else
715    clone = target_graph->CreateEmptyBlock();
716#endif
717    clone->SetAllFields(this->GetAllFields());
718    clone->try_id_ = GetTryId();
719    if (this->IsStartBlock()) {
720        target_graph->SetStartBlock(clone);
721    } else if (this->IsEndBlock()) {
722        target_graph->SetEndBlock(clone);
723    }
724    return clone;
725}
726
727Inst *BasicBlock::GetFistThrowableInst() const
728{
729    if (!IsTry()) {
730        return nullptr;
731    }
732    for (auto inst : AllInsts()) {
733        if (GetGraph()->IsInstThrowable(inst)) {
734            return inst;
735        }
736    }
737    return nullptr;
738}
739
740void BasicBlock::InvalidateLoopIfIrreducible()
741{
742    auto loop = GetLoop();
743    ASSERT(loop != nullptr);
744    if (IsLoopHeader() && loop->IsIrreducible()) {
745        GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
746    }
747}
748
749bool BlocksPathDfsSearch(Marker marker, BasicBlock *block, const BasicBlock *target_block,
750                         const BasicBlock *exclude_block)
751{
752    ASSERT(marker != UNDEF_MARKER);
753    if (block == target_block) {
754        return true;
755    }
756    block->SetMarker(marker);
757
758    for (auto succ_block : block->GetSuccsBlocks()) {
759        if (!succ_block->IsMarked(marker) && succ_block != exclude_block) {
760            if (BlocksPathDfsSearch(marker, succ_block, target_block, exclude_block)) {
761                return true;
762            }
763        }
764    }
765    return false;
766}
767}  // namespace panda::compiler
768