| 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 |