Debian Codegraph @

visa/iga/IGALibrary/IR/Traversals.hpp

raw
1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2017-2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 #ifndef IR_TRAVERSALS_HPP
10 #define IR_TRAVERSALS_HPP
11
12 #include "../asserts.hpp"
13 #include "Instruction.hpp"
14 #include "Kernel.hpp" // BlockList TODO: move to Blocks.hpp (elide Encoder def)
15
16 namespace iga {
17
18 class BranchIterator {
19 Instruction *m_inst;
20 size_t m_currSrcIx, m_srcCount;
21 Instruction *m_nextTarget;
22
23 void findNext();
24
25 public:
26 BranchIterator(Instruction *_inst, size_t _nextIx = 0);
27
28 // TODO: should this return a kernel iterator?
29 Instruction &operator*() const {
30 IGA_ASSERT(m_currSrcIx < m_srcCount, "BranchIterator overflow");
31 return *m_nextTarget;
32 }
33 bool operator==(const BranchIterator &rhs) const {
34 IGA_ASSERT(m_inst == rhs.m_inst,
35 "BranchIterator's point to different instructions");
36 return m_currSrcIx == rhs.m_currSrcIx;
37 }
38 bool operator!=(const BranchIterator &rhs) const { return !(*this == rhs); }
39
40 // post-increment
41 BranchIterator operator++(int) {
42 auto v = *this;
43 IGA_ASSERT(m_currSrcIx < m_srcCount, "BranchIterator at end");
44 findNext();
45 return v;
46 }
47
48 // pre increment
49 BranchIterator &operator++() {
50 IGA_ASSERT(m_currSrcIx < m_srcCount, "BranchIterator overflow");
51 findNext();
52 return *this;
53 }
54 };
55
56 // TODO: we need a
57 // KernelIterator
58 // KernelRevIterator (builds map for PRED)
59
60 // walks the branches of an instruction
61 class BranchWalker {
62 Instruction *inst;
63 BranchIterator end_itr;
64
65 BranchWalker(Instruction *_inst)
66 : inst(_inst), end_itr(_inst, _inst->getSourceCount()) {}
67 BranchIterator begin() { return BranchIterator(inst, 0); }
68 BranchIterator &end() { return end_itr; }
69 };
70
71 class KernelIterator {
72 // INVARIANTS:
73 // 1. bi and be both valid always
74 // 2. (bi == be) ==> (m_currBlock == mCurrInst == nullptr)
75 // 3. ii and ie always valid for current block OR (bi != be)
76 // if be == be then ii and ie are the end position of the last
77 // block's iterator or default values if the empty kernel is given
78 BlockList::iterator bi, be;
79 InstList::iterator ii, ie;
80 // non-null after construction until we reach end()
81 Block *m_currBlock = nullptr;
82 Instruction *m_currInst = nullptr;
83
84 void nextBlock();
85 void nextInst();
86
87 public:
88 KernelIterator(const BlockList::iterator &_bi,
89 const BlockList::iterator &_be);
90
91 Instruction *currInst();
92 Block &currBlock();
93
94 // returns an iterator of KernelIterators for branches
95 // TODO: or successors()
96 BranchIterator branches() const { return BranchIterator(m_currInst); }
97
98 // I.e. we can write
99 // for (Instruction &i : KernelIterator(...)) {
100 // ..
101 // }
102 Instruction &operator*() const {
103 IGA_ASSERT(bi != be, "KernelIterator at end");
104 return *m_currInst;
105 }
106 bool operator==(const KernelIterator &rhs) const {
107 return bi == rhs.bi && (bi == be || ii == rhs.ii);
108 }
109 bool operator!=(const KernelIterator &rhs) const { return !(*this == rhs); }
110 KernelIterator operator++(int); // post-increment
111 KernelIterator &operator++() {
112 nextInst();
113 return *this;
114 } // pre increment
115 };
116
117 struct KernelWalker {
118 BlockList &blocks;
119 KernelIterator end_itr;
120
121 KernelWalker(BlockList &_blocks);
122 KernelWalker(Kernel &k) : KernelWalker(k.getBlockList()) {}
123 KernelIterator begin() const {
124 return KernelIterator(blocks.begin(), blocks.end());
125 }
126 const KernelIterator &end() const { return end_itr; }
127 };
128
129 } // namespace iga
130
131 #endif // IR_TRAVERSALS_HPP