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#ifndef COMPILER_OPTIMIZER_IR_BASICBLOCK_H
17#define COMPILER_OPTIMIZER_IR_BASICBLOCK_H
18
19#include <iterator>
20#include "constants.h"
21#include "inst.h"
22#include "marker.h"
23#include "macros.h"
24
25namespace panda::compiler {
26class Graph;
27class Loop;
28
29enum class IterationType : uint8_t {
30    PHI,
31    INST,
32    ALL,
33};
34
35enum class IterationDirection : uint8_t {
36    FORWARD,
37    BACKWARD,
38};
39
40template <const IterationType T>
41class InstForwardIterator;
42template <const IterationType T>
43class InstBackwardIterator;
44template <const IterationType T, const IterationDirection D>
45class InstSafeIterator;
46
47using PhiInstIter = InstForwardIterator<IterationType::PHI>;
48using InstIter = InstForwardIterator<IterationType::INST>;
49using AllInstIter = InstForwardIterator<IterationType::ALL>;
50
51using InstReverseIter = InstBackwardIterator<IterationType::INST>;
52
53using PhiInstSafeIter = InstSafeIterator<IterationType::PHI, IterationDirection::FORWARD>;
54using InstSafeIter = InstSafeIterator<IterationType::INST, IterationDirection::FORWARD>;
55using AllInstSafeIter = InstSafeIterator<IterationType::ALL, IterationDirection::FORWARD>;
56
57using PhiInstSafeReverseIter = InstSafeIterator<IterationType::PHI, IterationDirection::BACKWARD>;
58using InstSafeReverseIter = InstSafeIterator<IterationType::INST, IterationDirection::BACKWARD>;
59using AllInstSafeReverseIter = InstSafeIterator<IterationType::ALL, IterationDirection::BACKWARD>;
60
61class BasicBlock : public MarkerSet {  // , public ArenaObject<ARENA_ALLOC_BASIC_BLOCK>
62public:
63    explicit BasicBlock(Graph *graph, uint32_t guest_pc = INVALID_PC);
64
65public:
66    void SetId(uint32_t id)
67    {
68        bb_id_ = id;
69    }
70    uint32_t GetId() const
71    {
72        return bb_id_;
73    }
74
75    ArenaVector<BasicBlock *> &GetPredsBlocks()
76    {
77        return preds_;
78    }
79    const ArenaVector<BasicBlock *> &GetPredsBlocks() const
80    {
81        return preds_;
82    }
83
84    ArenaVector<BasicBlock *> &GetSuccsBlocks()
85    {
86        return succs_;
87    }
88    const ArenaVector<BasicBlock *> &GetSuccsBlocks() const
89    {
90        return succs_;
91    }
92
93    BasicBlock *GetSuccessor(size_t index) const
94    {
95        ASSERT(index < succs_.size());
96        return succs_[index];
97    }
98
99    BasicBlock *GetPredecessor(size_t index) const
100    {
101        ASSERT(index < preds_.size());
102        return preds_[index];
103    }
104
105    template <bool invert = false>
106    void SwapTrueFalseSuccessors()
107    {
108        ASSERT(succs_.size() > 1);
109        std::swap(succs_[0], succs_[1]);
110        if constexpr (invert) {  // NOLINT(readability-braces-around-statements,bugprone-suspicious-semicolon)
111            inverted_ = !inverted_;
112        }
113        // If both succs are irruducible loop entrypoints, swapping can invalidate that loop header, since it's not
114        // determined
115        succs_[0]->InvalidateLoopIfIrreducible();
116        succs_[1]->InvalidateLoopIfIrreducible();
117    }
118
119    bool IsInverted() const
120    {
121        return inverted_;
122    }
123
124    BasicBlock *GetTrueSuccessor() const
125    {
126        ASSERT(!succs_.empty());
127        return succs_[0];
128    }
129
130    BasicBlock *GetFalseSuccessor() const
131    {
132        ASSERT(succs_.size() > 1);
133        return succs_[1];
134    }
135
136    // Get index of the given block in predecessor container
137    size_t GetPredBlockIndex(const BasicBlock *block) const
138    {
139        auto it = std::find(preds_.begin(), preds_.end(), block);
140        ASSERT(it != preds_.end());
141        ASSERT(std::find(it + 1, preds_.end(), block) == preds_.end());
142        return std::distance(preds_.begin(), it);
143    }
144
145    // Get index of the given block in successor container
146    size_t GetSuccBlockIndex(const BasicBlock *block) const
147    {
148        auto it = std::find(succs_.begin(), succs_.end(), block);
149        ASSERT(it != succs_.end());
150        ASSERT(std::find(it + 1, succs_.end(), block) == succs_.end());
151        return std::distance(succs_.begin(), it);
152    }
153
154    // Get basic block by its index in predecessors container
155    BasicBlock *GetPredBlockByIndex(size_t index) const
156    {
157        ASSERT(index < preds_.size());
158        return preds_[index];
159    }
160
161    bool IsStartBlock() const;
162    bool IsEndBlock() const;
163    bool IsPseudoControlFlowBlock() const;
164
165    Graph *GetGraph()
166    {
167        return graph_;
168    }
169    const Graph *GetGraph() const
170    {
171        return graph_;
172    }
173    void SetGraph(Graph *graph)
174    {
175        graph_ = graph;
176    }
177
178    void SetGuestPc(uint32_t guest_pc)
179    {
180        guest_pc_ = guest_pc;
181    }
182    uint32_t GetGuestPc() const
183    {
184        return guest_pc_;
185    }
186
187    /**
188     * Split block after the given instruction. Current block will contain instructions before the splitting line and
189     * the created block - after.
190     * @param inst instruction after which block will be split
191     * @param make_edge whether to make control flow edge from first block to the second one
192     * @return return created basic block
193     */
194    BasicBlock *SplitBlockAfterInstruction(Inst *inst, bool make_edge);
195
196    // Add successor in the list
197    void AddSucc(BasicBlock *succ, bool can_add_empty_block = false);
198
199    bool HasSucc(BasicBlock *succ)
200    {
201        return std::find(succs_.begin(), succs_.end(), succ) != succs_.end();
202    }
203
204    void ReplacePred(BasicBlock *prev_pred, BasicBlock *new_pred)
205    {
206        preds_[GetPredBlockIndex(prev_pred)] = new_pred;
207        new_pred->succs_.push_back(this);
208    }
209
210    void ReplaceSucc(const BasicBlock *prev_succ, BasicBlock *new_succ, bool can_add_empty_block = false);
211
212    void ReplaceTrueSuccessor(BasicBlock *new_succ)
213    {
214        ASSERT(!succs_.empty());
215        succs_[0] = new_succ;
216        new_succ->preds_.push_back(this);
217    }
218
219    void ReplaceFalseSuccessor(BasicBlock *new_succ)
220    {
221        ASSERT(succs_.size() > 1);
222        succs_[1] = new_succ;
223        new_succ->preds_.push_back(this);
224    }
225
226    BasicBlock *InsertNewBlockToSuccEdge(BasicBlock *succ);
227    BasicBlock *InsertEmptyBlockBefore();
228
229    void InsertBlockBeforeSucc(BasicBlock *block, BasicBlock *succ);
230
231    // Remove empty block with one successor
232    void RemoveEmptyBlock(bool irr_loop = false);
233    void RemoveFixLoopInfo();
234
235    // Join single successor into single predecessor
236    void JoinSuccessorBlock();
237
238    // Add instruction to the end or begin of the BasicBlock
239    template <bool to_end>
240    void AddInst(Inst *inst);
241    // Insert new instruction(NOT PHI) in BasicBlock at the start of instructions
242    void PrependInst(Inst *inst)
243    {
244        AddInst<false>(inst);
245    }
246    // Insert new instruction(NOT PHI) in BasicBlock at the end of instructions
247    void AppendInst(Inst *inst)
248    {
249        AddInst<true>(inst);
250    }
251    // Append range of instructions(NOT PHI) in BasicBlock at the end of instructions
252    // It is implied that for instructions within range was already called correctly SetBasicBlock() and
253    // range_last should dominate range_first.
254    void AppendRangeInst(Inst *range_first, Inst *range_last);
255    // Insert new PHI instruction in BasicBlock at the end of PHI instructions
256    void AppendPhi(Inst *inst);
257    // Insert instruction after given instruction
258    void InsertAfter(Inst *inst, Inst *after);
259    // Insert instruction before given instruction
260    void InsertBefore(Inst *inst, Inst *before);
261    // Insert range of instructions before given instruction.
262    // It is implied that for instructions within range was already called correctly SetBasicBlock() and
263    // range_last should dominate range_first.
264    void InsertRangeBefore(Inst *range_first, Inst *range_last, Inst *before);
265    // Remove instruction from instructions chain. All other data keep unmodified.
266    void EraseInst(Inst *inst, [[maybe_unused]] bool will_be_moved = false);
267    // Remove instructions from instructions chain, remove its inputs and check that it hasn't users.
268    void RemoveInst(Inst *inst);
269    // Replace old_inst in BasicBlock to new_inst
270    void ReplaceInst(Inst *old_inst, Inst *new_inst);
271    // Remove all instructions from bb
272    void Clear();
273
274    Inst *GetLastInst() const
275    {
276        return last_inst_;
277    }
278
279    Inst *GetFirstInst() const
280    {
281        return first_inst_;
282    }
283
284    Inst *GetFirstPhi() const
285    {
286        return first_phi_;
287    }
288
289    bool IsEmpty() const
290    {
291        return first_inst_ == nullptr;
292    }
293
294    bool HasPhi() const
295    {
296        return first_phi_ != nullptr;
297    }
298
299    void SetDominator(BasicBlock *dominator)
300    {
301        dominator_ = dominator;
302    }
303    void ClearDominator()
304    {
305        dominator_ = nullptr;
306    }
307
308    BasicBlock *CreateImmediateDominator();
309
310    void AddDominatedBlock(BasicBlock *block)
311    {
312        dom_blocks_.push_back(block);
313    }
314    void RemoveDominatedBlock(BasicBlock *block)
315    {
316        dom_blocks_.erase(std::find(dom_blocks_.begin(), dom_blocks_.end(), block));
317    }
318    void ClearDominatedBlocks()
319    {
320        dom_blocks_.clear();
321    }
322
323    BasicBlock *GetDominator() const;
324    const ArenaVector<BasicBlock *> &GetDominatedBlocks() const;
325    bool IsDominate(const BasicBlock *other) const;
326
327    void RemovePred(const BasicBlock *pred)
328    {
329        ASSERT(GetPredBlockIndex(pred) < preds_.size());
330        preds_[GetPredBlockIndex(pred)] = preds_.back();
331        preds_.pop_back();
332    }
333
334    void RemovePred(size_t index)
335    {
336        ASSERT(index < preds_.size());
337        preds_[index] = preds_.back();
338        preds_.pop_back();
339    }
340
341    void RemoveSucc(BasicBlock *succ)
342    {
343        auto it = std::find(succs_.begin(), succs_.end(), succ);
344        ASSERT(it != succs_.end());
345        succs_.erase(it);
346    }
347
348    void Dump(std::ostream *out) const;
349
350    Loop *GetLoop() const
351    {
352        return loop_;
353    }
354    void SetLoop(Loop *loop)
355    {
356        loop_ = loop;
357    }
358    bool IsLoopValid() const
359    {
360        return GetLoop() != nullptr;
361    }
362    bool IsLoopHeader() const;
363
364    void SetNextLoop(Loop *loop)
365    {
366        next_loop_ = loop;
367    }
368    Loop *GetNextLoop()
369    {
370        return next_loop_;
371    }
372    bool IsLoopPreHeader() const
373    {
374        return (next_loop_ != nullptr);
375    }
376
377    void InsertBlockBefore(BasicBlock *block);
378
379    template <typename Accessor>
380    typename Accessor::ValueType GetField() const
381    {
382        return Accessor::Get(bit_fields_);
383    }
384
385    template <typename Accessor>
386    void SetField(typename Accessor::ValueType value)
387    {
388        Accessor::Set(value, &bit_fields_);
389    }
390
391    void SetAllFields(uint32_t bit_fields)
392    {
393        bit_fields_ = bit_fields;
394    }
395
396    uint32_t GetAllFields() const
397    {
398        return bit_fields_;
399    }
400
401    void SetMonitorEntryBlock(bool v)
402    {
403        SetField<MonitorEntryBlock>(v);
404    }
405
406    bool GetMonitorEntryBlock()
407    {
408        return GetField<MonitorEntryBlock>();
409    }
410
411    void SetMonitorExitBlock(bool v)
412    {
413        SetField<MonitorExitBlock>(v);
414    }
415
416    bool GetMonitorExitBlock() const
417    {
418        return GetField<MonitorExitBlock>();
419    }
420
421    void SetMonitorBlock(bool v)
422    {
423        SetField<MonitorBlock>(v);
424    }
425
426    bool GetMonitorBlock() const
427    {
428        return GetField<MonitorBlock>();
429    }
430
431    void SetCatch(bool v)
432    {
433        SetField<CatchBlock>(v);
434    }
435
436    bool IsCatch() const
437    {
438        return GetField<CatchBlock>();
439    }
440
441    void SetCatchBegin(bool v)
442    {
443        SetField<CatchBeginBlock>(v);
444    }
445
446    bool IsCatchBegin() const
447    {
448        return GetField<CatchBeginBlock>();
449    }
450
451    void SetCatchEnd(bool v)
452    {
453        SetField<CatchEndBlock>(v);
454    }
455
456    bool IsCatchEnd() const
457    {
458        return GetField<CatchEndBlock>();
459    }
460
461    void SetTry(bool v)
462    {
463        SetField<TryBlock>(v);
464    }
465
466    bool IsTry() const
467    {
468        return GetField<TryBlock>();
469    }
470
471    void SetTryBegin(bool v)
472    {
473        SetField<TryBeginBlock>(v);
474    }
475
476    bool IsTryBegin() const
477    {
478        return GetField<TryBeginBlock>();
479    }
480
481    void SetTryEnd(bool v)
482    {
483        SetField<TryEndBlock>(v);
484    }
485
486    bool IsTryEnd() const
487    {
488        return GetField<TryEndBlock>();
489    }
490
491    void SetOsrEntry(bool v)
492    {
493        SetField<OsrEntry>(v);
494    }
495
496    bool IsOsrEntry() const
497    {
498        return GetField<OsrEntry>();
499    }
500
501    void CopyTryCatchProps(BasicBlock *block)
502    {
503        if (block->IsTry()) {
504            SetTry(true);
505            SetTryId(block->GetTryId());
506        }
507        if (block->IsCatch()) {
508            SetCatch(true);
509        }
510    }
511
512    uint32_t GetTryId() const
513    {
514        return try_id_;
515    }
516
517    void SetTryId(uint32_t try_id)
518    {
519        try_id_ = try_id;
520    }
521
522    template <class Callback>
523    void EnumerateCatchHandlers(const Callback &callback) const
524    {
525        ASSERT(this->IsTryBegin());
526        auto try_inst = GetTryBeginInst(this);
527        auto type_ids = try_inst->GetCatchTypeIds();
528        auto catch_indexes = try_inst->GetCatchEdgeIndexes();
529        ASSERT(type_ids != nullptr && catch_indexes != nullptr);
530        for (size_t idx = 0; idx < type_ids->size(); idx++) {
531            auto succ = GetSuccessor(catch_indexes->at(idx));
532            while (!succ->IsCatchBegin()) {
533                ASSERT(succ->GetSuccsBlocks().size() == 1);
534                succ = succ->GetSuccessor(0);
535            }
536            ASSERT(succ != nullptr);
537            if (!callback(succ, type_ids->at(idx))) {
538                break;
539            }
540        }
541    }
542
543    BasicBlock *Clone(Graph *target_graph) const;
544
545    void SetNeedsJump(bool v)
546    {
547        SetField<JumpFlag>(v);
548    }
549
550    bool NeedsJump() const
551    {
552        return GetField<JumpFlag>();
553    }
554
555    bool IsIfBlock() const
556    {
557        if (last_inst_ != nullptr) {
558            if (last_inst_->GetOpcode() == Opcode::If || last_inst_->GetOpcode() == Opcode::IfImm) {
559                return true;
560            }
561        }
562        return false;
563    }
564
565    Inst *GetFistThrowableInst() const;
566
567    void InvalidateLoopIfIrreducible();
568
569    // Member functions to iterate instructions. `Safe` means that you can delete instructions when iterating
570    PhiInstIter PhiInsts() const;
571    InstIter Insts() const;
572    AllInstIter AllInsts() const;
573
574    InstReverseIter InstsReverse() const;
575
576    PhiInstSafeIter PhiInstsSafe() const;
577    InstSafeIter InstsSafe() const;
578    AllInstSafeIter AllInstsSafe() const;
579
580    PhiInstSafeReverseIter PhiInstsSafeReverse() const;
581    InstSafeReverseIter InstsSafeReverse() const;
582    AllInstSafeReverseIter AllInstsSafeReverse() const;
583
584private:
585    using MonitorEntryBlock = BitField<bool, 0>;           //  block with MonitorEntry
586    using MonitorExitBlock = MonitorEntryBlock::NextFlag;  //  block with MonitorExit
587    using MonitorBlock = MonitorExitBlock::NextFlag;       //  block between MonitorEntryBlock and MonitorExitBlock.
588    using CatchBeginBlock = MonitorBlock::NextFlag;
589    using CatchEndBlock = CatchBeginBlock::NextFlag;
590    using CatchBlock = CatchEndBlock::NextFlag;
591    using TryBeginBlock = CatchBlock::NextFlag;
592    using TryEndBlock = TryBeginBlock::NextFlag;
593    using TryBlock = TryEndBlock::NextFlag;
594    using OsrEntry = TryBlock::NextFlag;
595    using JumpFlag = OsrEntry::NextFlag;  // signals that Codegen should insert a jump to the successor
596    using LastField = JumpFlag;
597
598    struct saved_if_info {
599        BasicBlock *succ;
600        bool swapped;
601        uint64_t if_imm;
602        ConditionCode if_cc;
603        DataType::Type if_type;
604        uint32_t if_pc;
605        Opcode if_opcode;
606        Inst *if_input0;
607        Inst *if_input1;
608    };
609
610    void SelectsFixLoopInfo(BasicBlock *select_bb, BasicBlock *other);
611
612    Graph *graph_;
613
614    // List of predessesor blocks.
615    ArenaVector<BasicBlock *> preds_;
616
617    // List of successors blocks.
618    ArenaVector<BasicBlock *> succs_;
619
620    // List of dominated blocks.
621    ArenaVector<BasicBlock *> dom_blocks_;
622
623    // Dominator block
624    BasicBlock *dominator_ {nullptr};
625
626    /// This value hold properties of the basic block. It accessed via BitField types.
627    uint32_t bit_fields_ {0};
628
629    // pc address from bytecode file
630    uint32_t guest_pc_;
631    uint32_t bb_id_ {INVALID_ID};
632
633    Inst *first_phi_ {nullptr};
634    Inst *first_inst_ {nullptr};
635    Inst *last_inst_ {nullptr};
636
637    Loop *loop_ {nullptr};
638    // Not nullptr if block is pre-header of next_loop_
639    Loop *next_loop_ {nullptr};
640
641    uint32_t try_id_ {INVALID_ID};
642    bool inverted_ {false};
643
644    template <const IterationType T, const IterationDirection D>
645    friend class InstIterator;
646    template <const IterationType T>
647    friend class InstForwardIterator;
648    template <const IterationType T>
649    friend class InstBackwardIterator;
650    template <const IterationType T, const IterationDirection D>
651    friend class InstSafeIterator;
652};
653
654/*
655 * Iterators inheritance-tree
656 *
657 *  ValueObject
658 *   |
659 *   |
660 *   |----> InstIterator<Type, Direction>  [ add field Inst* current_ ]
661 *           |
662 *           |
663 *           |----> InstForwardIterator<Type, Direction::FORWARD>
664 *           |       |
665 *           |       |---->   InstForwardIterator<Type::PHI, Direction::FORWARD>
666 *           |                [ add field Inst* final_ ]
667 *           |
668 *           |
669 *           |----> InstSafeIterator<Type, Direction> [ add field Inst* follower_ ]
670 *                   |
671 *                   |---->   InstSafeIterator<Type::PHI, Direction::FORWARD>
672 *                   |        [ add field Inst* final_ ]
673 *                   |---->   InstSafeIterator<Type::INST, Direction::BACKWARD>
674 *                            [ add field Inst* final_ ]
675 */
676
677template <const IterationType T, const IterationDirection D>
678class InstIterator : public std::iterator<std::forward_iterator_tag, IterationType> {
679public:
680    const Inst *operator*() const
681    {
682        return current_;
683    }
684    Inst *operator*()
685    {
686        return current_;
687    }
688
689    Inst *GetCurrent() const
690    {
691        return current_;
692    }
693
694    void SetCurrent(Inst *current)
695    {
696        current_ = current;
697    }
698
699protected:
700    InstIterator(const BasicBlock &block, Inst *start)
701    {
702#ifndef __clang_analyzer__
703        if constexpr (IterationType::INST == T && IterationDirection::FORWARD == D) {
704            current_ = (start != nullptr) ? start : block.first_inst_;
705            return;
706        }
707        if constexpr (IterationType::ALL == T && IterationDirection::FORWARD == D) {
708            current_ = (block.first_phi_ != nullptr) ? block.first_phi_ : block.first_inst_;
709            current_ = (start != nullptr) ? start : current_;
710            return;
711        }
712        if constexpr (IterationType::PHI == T && IterationDirection::BACKWARD == D) {
713            current_ = (block.first_inst_ != nullptr) ? block.first_inst_->GetPrev() : block.last_inst_;
714            current_ = (start != nullptr) ? start : current_;
715            return;
716        }
717        if constexpr (IterationType::ALL == T && IterationDirection::BACKWARD == D) {
718            current_ = (start != nullptr) ? start : block.last_inst_;
719            return;
720        }
721#else
722        [[maybe_unused]] auto const &tb = block;
723        [[maybe_unused]] auto ts = start;
724#endif
725        UNREACHABLE();
726    }
727    explicit InstIterator(Inst *current) : current_(current) {};
728
729    DEFAULT_COPY_SEMANTIC(InstIterator);
730    DEFAULT_MOVE_SEMANTIC(InstIterator);
731    virtual ~InstIterator() = default;
732
733private:
734    Inst *current_ {nullptr};
735};
736
737/*
738 * Iterates over the instructions in direct order.
739 * Starts with the 'start' instruction if it's initialized
740 * or with the first phi/non-phi instruction in the basic block
741 */
742template <const IterationType T>
743class InstForwardIterator : public InstIterator<T, IterationDirection::FORWARD> {
744public:
745    explicit InstForwardIterator(const BasicBlock &block, Inst *start = nullptr)
746        : InstIterator<T, IterationDirection::FORWARD>(block, start)
747    {
748    }
749
750public:
751    // NOLINTNEXTLINE(readability-identifier-naming)
752    InstForwardIterator begin() const
753    {
754        return InstForwardIterator(this->GetCurrent());
755    }
756    // NOLINTNEXTLINE(readability-identifier-naming)
757    InstForwardIterator end() const
758    {
759        return InstForwardIterator(nullptr);
760    }
761    InstForwardIterator &operator++()
762    {
763        this->SetCurrent(this->GetCurrent()->GetNext());
764        return *this;
765    }
766    bool operator!=(const InstForwardIterator &other) const
767    {
768        return this->GetCurrent() != other.GetCurrent();
769    }
770    bool operator==(const InstForwardIterator &other) const
771    {
772        return this->GetCurrent() == other.GetCurrent();
773    }
774
775protected:
776    explicit InstForwardIterator(Inst *current) : InstIterator<T, IterationDirection::FORWARD>(current) {};
777};
778
779/*
780 * Specialization for PHI instructions
781 */
782template <>
783class InstForwardIterator<IterationType::PHI> : public InstForwardIterator<IterationType::INST> {
784public:
785    explicit InstForwardIterator(const BasicBlock &block, Inst *start = nullptr)
786        : InstForwardIterator<IterationType::INST>(start != nullptr ? start : block.first_phi_)
787    {
788        final_ = ((block.first_phi_ != nullptr) && (block.first_inst_ != nullptr)) ? block.first_inst_ : nullptr;
789    }
790
791public:
792    // NOLINTNEXTLINE(readability-identifier-naming)
793    InstForwardIterator end() const
794    {
795        return InstForwardIterator(final_);
796    }
797    bool operator!=(const InstForwardIterator &other) const
798    {
799        return this->GetCurrent() != other.GetCurrent();
800    }
801    bool operator==(const InstForwardIterator &other) const
802    {
803        return this->GetCurrent() == other.GetCurrent();
804    }
805
806private:
807    explicit InstForwardIterator(Inst *current) : InstForwardIterator<IterationType::INST>(current) {};
808
809private:
810    Inst *final_ {nullptr};
811};
812
813/*
814 * Iterates over the instructions in reverse order.
815 * Starts with the 'start' instruction if it's initialized
816 * or with the first phi/non-phi instruction in the basic block
817 */
818template <const IterationType T>
819class InstBackwardIterator : public InstIterator<T, IterationDirection::BACKWARD> {
820public:
821    explicit InstBackwardIterator(const BasicBlock &block, Inst *start = nullptr)
822        : InstIterator<T, IterationDirection::BACKWARD>(block, start)
823    {
824    }
825
826public:
827    // NOLINTNEXTLINE(readability-identifier-naming)
828    InstBackwardIterator begin() const
829    {
830        return InstBackwardIterator(this->GetCurrent());
831    }
832    // NOLINTNEXTLINE(readability-identifier-naming)
833    InstBackwardIterator end() const
834    {
835        return InstBackwardIterator(nullptr);
836    }
837    InstBackwardIterator &operator++()
838    {
839        this->SetCurrent(this->GetCurrent()->GetPrev());
840        return *this;
841    }
842    bool operator!=(const InstBackwardIterator &other) const
843    {
844        return this->GetCurrent() != other.GetCurrent();
845    }
846    bool operator==(const InstBackwardIterator &other) const
847    {
848        return this->GetCurrent() == other.GetCurrent();
849    }
850
851protected:
852    explicit InstBackwardIterator(Inst *current) : InstIterator<T, IterationDirection::BACKWARD>(current) {}
853};
854
855/*
856 * Specialization for not-PHI instructions
857 */
858template <>
859class InstBackwardIterator<IterationType::INST> : public InstBackwardIterator<IterationType::ALL> {
860public:
861    explicit InstBackwardIterator(const BasicBlock &block, Inst *start = nullptr)
862        : InstBackwardIterator<IterationType::ALL>(nullptr)
863    {
864        auto last_inst = (block.first_inst_ != nullptr) ? block.last_inst_ : nullptr;
865        this->SetCurrent(start != nullptr ? start : last_inst);
866        final_ = (block.first_inst_ != nullptr) ? block.first_inst_->GetPrev() : nullptr;
867    }
868
869public:
870    // NOLINTNEXTLINE(readability-identifier-naming)
871    InstBackwardIterator end() const
872    {
873        return InstBackwardIterator(final_);
874    }
875
876private:
877    explicit InstBackwardIterator(Inst *current) : InstBackwardIterator<IterationType::ALL>(current) {}
878
879private:
880    Inst *final_ {nullptr};
881};
882
883/*
884 * Iterates over the instructions in `IterationDirection` order, keeping next instruction in case of removing current
885 * instruction
886 */
887template <const IterationType T, const IterationDirection D>
888class InstSafeIterator : public InstIterator<T, D> {
889public:
890    explicit InstSafeIterator(const BasicBlock &block, Inst *start = nullptr) : InstIterator<T, D>(block, start)
891    {
892        follower_ = GetFollower();
893    }
894
895public:
896    // NOLINTNEXTLINE(readability-identifier-naming)
897    InstSafeIterator begin() const
898    {
899        return InstSafeIterator(this->GetCurrent(), follower_);
900    }
901    // NOLINTNEXTLINE(readability-identifier-naming)
902    InstSafeIterator end() const
903    {
904        return InstSafeIterator(nullptr);
905    }
906    InstSafeIterator &operator++()
907    {
908        this->SetCurrent(follower_);
909        follower_ = GetFollower();
910        return *this;
911    }
912    bool operator!=(const InstSafeIterator &other) const
913    {
914        return this->GetCurrent() != other.GetCurrent();
915    }
916    bool operator==(const InstSafeIterator &other) const
917    {
918        return this->GetCurrent() == other.GetCurrent();
919    }
920
921protected:
922    explicit InstSafeIterator(Inst *current) : InstIterator<T, D>(current) {};
923    explicit InstSafeIterator(Inst *current, Inst *follower) : InstIterator<T, D>(current), follower_(follower) {};
924
925protected:
926    Inst *GetFollower()
927    {
928#ifndef __clang_analyzer__
929        if constexpr (IterationDirection::FORWARD == D) {
930            return this->GetCurrent() == nullptr ? nullptr : this->GetCurrent()->GetNext();
931        };
932        if constexpr (IterationDirection::BACKWARD == D) {
933            return this->GetCurrent() == nullptr ? nullptr : this->GetCurrent()->GetPrev();
934        };
935#endif
936        UNREACHABLE();
937        return nullptr;
938    }
939
940    void SetFollower(Inst *follower)
941    {
942        follower_ = follower;
943    }
944
945private:
946    Inst *follower_ {nullptr};
947};
948
949/*
950 * Specialization for PHI instructions
951 */
952template <>
953class InstSafeIterator<IterationType::PHI, IterationDirection::FORWARD>
954    : public InstSafeIterator<IterationType::INST, IterationDirection::FORWARD> {
955public:
956    explicit InstSafeIterator(const BasicBlock &block, Inst *start = nullptr)
957        : InstSafeIterator<IterationType::INST, IterationDirection::FORWARD>(start != nullptr ? start
958                                                                                              : block.first_phi_)
959    {
960        final_ = ((block.first_phi_ != nullptr) && (block.first_inst_ != nullptr)) ? block.first_inst_ : nullptr;
961        this->SetFollower(GetFollower());
962    }
963
964public:
965    // NOLINTNEXTLINE(readability-identifier-naming)
966    InstSafeIterator end() const
967    {
968        return InstSafeIterator(final_);
969    }
970    bool operator!=(const InstSafeIterator &other) const
971    {
972        return this->GetCurrent() != other.GetCurrent();
973    }
974    bool operator==(const InstSafeIterator &other) const
975    {
976        return this->GetCurrent() == other.GetCurrent();
977    }
978
979private:
980    explicit InstSafeIterator(Inst *current)
981        : InstSafeIterator<IterationType::INST, IterationDirection::FORWARD>(current) {};
982
983private:
984    Inst *GetFollower()
985    {
986        return this->GetCurrent() == final_ ? nullptr : this->GetCurrent()->GetNext();
987    }
988
989private:
990    Inst *final_ {nullptr};
991};
992
993/*
994 * Specialization for not-PHI instructions
995 */
996template <>
997class InstSafeIterator<IterationType::INST, IterationDirection::BACKWARD>
998    : public InstSafeIterator<IterationType::ALL, IterationDirection::BACKWARD> {
999public:
1000    explicit InstSafeIterator(const BasicBlock &block, Inst *start = nullptr)
1001        : InstSafeIterator<IterationType::ALL, IterationDirection::BACKWARD>(nullptr)
1002    {
1003        auto last_inst = (block.first_inst_ != nullptr) ? block.last_inst_ : nullptr;
1004        this->SetCurrent(start != nullptr ? start : last_inst);
1005        final_ = (block.first_inst_ != nullptr) ? block.first_inst_->GetPrev() : nullptr;
1006        this->SetFollower(GetFollower());
1007    }
1008
1009public:
1010    // NOLINTNEXTLINE(readability-identifier-naming)
1011    InstSafeIterator end() const
1012    {
1013        return InstSafeIterator(final_);
1014    }
1015    bool operator!=(const InstSafeIterator &other) const
1016    {
1017        return this->GetCurrent() != other.GetCurrent();
1018    }
1019    bool operator==(const InstSafeIterator &other) const
1020    {
1021        return this->GetCurrent() == other.GetCurrent();
1022    }
1023
1024private:
1025    explicit InstSafeIterator(Inst *current)
1026        : InstSafeIterator<IterationType::ALL, IterationDirection::BACKWARD>(current) {};
1027
1028private:
1029    Inst *GetFollower()
1030    {
1031        return this->GetCurrent() == final_ ? nullptr : this->GetCurrent()->GetPrev();
1032    }
1033
1034private:
1035    Inst *final_ {nullptr};
1036};
1037
1038/**
1039 * DFS-search to find path between `block` and `target_block`,
1040 * `exclude_block` can be set to search path without this block
1041 */
1042bool BlocksPathDfsSearch(Marker marker, BasicBlock *block, const BasicBlock *target_block,
1043                         const BasicBlock *exclude_block = nullptr);
1044}  // namespace panda::compiler
1045
1046#endif  // COMPILER_OPTIMIZER_IR_BASICBLOCK_H
1047