/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Analysis/RegionIterator.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // This file defines the iterators to iterate over the elements of a Region. |
10 | | //===----------------------------------------------------------------------===// |
11 | | |
12 | | #ifndef LLVM_ANALYSIS_REGIONITERATOR_H |
13 | | #define LLVM_ANALYSIS_REGIONITERATOR_H |
14 | | |
15 | | #include "llvm/ADT/DepthFirstIterator.h" |
16 | | #include "llvm/ADT/GraphTraits.h" |
17 | | #include "llvm/ADT/PointerIntPair.h" |
18 | | #include "llvm/Analysis/RegionInfo.h" |
19 | | #include "llvm/IR/CFG.h" |
20 | | #include <cassert> |
21 | | #include <iterator> |
22 | | #include <type_traits> |
23 | | |
24 | | namespace llvm { |
25 | | |
26 | | class BasicBlock; |
27 | | |
28 | | //===----------------------------------------------------------------------===// |
29 | | /// @brief Hierarchical RegionNode successor iterator. |
30 | | /// |
31 | | /// This iterator iterates over all successors of a RegionNode. |
32 | | /// |
33 | | /// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of |
34 | | /// the parent Region. Furthermore for BasicBlocks that start a subregion, a |
35 | | /// RegionNode representing the subregion is returned. |
36 | | /// |
37 | | /// For a subregion RegionNode there is just one successor. The RegionNode |
38 | | /// representing the exit of the subregion. |
39 | | template <class NodeRef, class BlockT, class RegionT> |
40 | | class RNSuccIterator |
41 | | : public std::iterator<std::forward_iterator_tag, NodeRef> { |
42 | | using super = std::iterator<std::forward_iterator_tag, NodeRef>; |
43 | | using BlockTraits = GraphTraits<BlockT *>; |
44 | | using SuccIterTy = typename BlockTraits::ChildIteratorType; |
45 | | |
46 | | // The iterator works in two modes, bb mode or region mode. |
47 | | enum ItMode { |
48 | | // In BB mode it returns all successors of this BasicBlock as its |
49 | | // successors. |
50 | | ItBB, |
51 | | // In region mode there is only one successor, thats the regionnode mapping |
52 | | // to the exit block of the regionnode |
53 | | ItRgBegin, // At the beginning of the regionnode successor. |
54 | | ItRgEnd // At the end of the regionnode successor. |
55 | | }; |
56 | | |
57 | | static_assert(std::is_pointer<NodeRef>::value, |
58 | | "FIXME: Currently RNSuccIterator only supports NodeRef as " |
59 | | "pointers due to the use of pointer-specific data structures " |
60 | | "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize " |
61 | | "it to support non-pointer types"); |
62 | | |
63 | | // Use two bit to represent the mode iterator. |
64 | | PointerIntPair<NodeRef, 2, ItMode> Node; |
65 | | |
66 | | // The block successor iterator. |
67 | | SuccIterTy BItor; |
68 | | |
69 | | // advanceRegionSucc - A region node has only one successor. It reaches end |
70 | | // once we advance it. |
71 | 7.09k | void advanceRegionSucc() { |
72 | 7.09k | assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); |
73 | 7.09k | Node.setInt(ItRgEnd); |
74 | 7.09k | } Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::advanceRegionSucc() llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::advanceRegionSucc() Line | Count | Source | 71 | 7.09k | void advanceRegionSucc() { | 72 | 7.09k | assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); | 73 | 7.09k | Node.setInt(ItRgEnd); | 74 | 7.09k | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::advanceRegionSucc() llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::advanceRegionSucc() Line | Count | Source | 71 | 2 | void advanceRegionSucc() { | 72 | 2 | assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!"); | 73 | 2 | Node.setInt(ItRgEnd); | 74 | 2 | } |
|
75 | | |
76 | 127k | NodeRef getNode() const { return Node.getPointer(); } Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::getNode() const llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::getNode() const Line | Count | Source | 76 | 22 | NodeRef getNode() const { return Node.getPointer(); } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::getNode() const llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::getNode() const Line | Count | Source | 76 | 127k | NodeRef getNode() const { return Node.getPointer(); } |
|
77 | | |
78 | | // isRegionMode - Is the current iterator in region mode? |
79 | 207k | bool isRegionMode() const { return Node.getInt() != ItBB; } Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::isRegionMode() const Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::isRegionMode() const llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::isRegionMode() const Line | Count | Source | 79 | 36 | bool isRegionMode() const { return Node.getInt() != ItBB; } |
llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::isRegionMode() const Line | Count | Source | 79 | 207k | bool isRegionMode() const { return Node.getInt() != ItBB; } |
|
80 | | |
81 | | // Get the immediate successor. This function may return a Basic Block |
82 | | // RegionNode or a subregion RegionNode. |
83 | 32.3k | NodeRef getISucc(BlockT *BB) const { |
84 | 32.3k | NodeRef succ; |
85 | 32.3k | succ = getNode()->getParent()->getNode(BB); |
86 | 32.3k | assert(succ && "BB not in Region or entered subregion!"); |
87 | 32.3k | return succ; |
88 | 32.3k | } llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::getISucc(llvm::BasicBlock*) const Line | Count | Source | 83 | 4 | NodeRef getISucc(BlockT *BB) const { | 84 | 4 | NodeRef succ; | 85 | 4 | succ = getNode()->getParent()->getNode(BB); | 86 | 4 | assert(succ && "BB not in Region or entered subregion!"); | 87 | 4 | return succ; | 88 | 4 | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::getISucc(llvm::MachineBasicBlock*) const Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::getISucc(llvm::MachineBasicBlock*) const llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::getISucc(llvm::BasicBlock*) const Line | Count | Source | 83 | 32.3k | NodeRef getISucc(BlockT *BB) const { | 84 | 32.3k | NodeRef succ; | 85 | 32.3k | succ = getNode()->getParent()->getNode(BB); | 86 | 32.3k | assert(succ && "BB not in Region or entered subregion!"); | 87 | 32.3k | return succ; | 88 | 32.3k | } |
|
89 | | |
90 | | // getRegionSucc - Return the successor basic block of a SubRegion RegionNode. |
91 | 13.0k | inline BlockT* getRegionSucc() const { |
92 | 13.0k | assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); |
93 | 13.0k | return getNode()->template getNodeAs<RegionT>()->getExit(); |
94 | 13.0k | } llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::getRegionSucc() const Line | Count | Source | 91 | 4 | inline BlockT* getRegionSucc() const { | 92 | 4 | assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); | 93 | 4 | return getNode()->template getNodeAs<RegionT>()->getExit(); | 94 | 4 | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::getRegionSucc() const Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::getRegionSucc() const llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::getRegionSucc() const Line | Count | Source | 91 | 13.0k | inline BlockT* getRegionSucc() const { | 92 | 13.0k | assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!"); | 93 | 13.0k | return getNode()->template getNodeAs<RegionT>()->getExit(); | 94 | 13.0k | } |
|
95 | | |
96 | | // isExit - Is this the exit BB of the Region? |
97 | 47.8k | inline bool isExit(BlockT* BB) const { |
98 | 47.8k | return getNode()->getParent()->getExit() == BB; |
99 | 47.8k | } llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::isExit(llvm::BasicBlock*) const Line | Count | Source | 97 | 47.7k | inline bool isExit(BlockT* BB) const { | 98 | 47.7k | return getNode()->getParent()->getExit() == BB; | 99 | 47.7k | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::isExit(llvm::MachineBasicBlock*) const Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::isExit(llvm::MachineBasicBlock*) const llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::isExit(llvm::BasicBlock*) const Line | Count | Source | 97 | 10 | inline bool isExit(BlockT* BB) const { | 98 | 10 | return getNode()->getParent()->getExit() == BB; | 99 | 10 | } |
|
100 | | |
101 | | public: |
102 | | using Self = RNSuccIterator<NodeRef, BlockT, RegionT>; |
103 | | using value_type = typename super::value_type; |
104 | | |
105 | | /// @brief Create begin iterator of a RegionNode. |
106 | | inline RNSuccIterator(NodeRef node) |
107 | | : Node(node, node->isSubRegion() ? ItRgBegin : ItBB), |
108 | 36.6k | BItor(BlockTraits::child_begin(node->getEntry())) { |
109 | 36.6k | // Skip the exit block |
110 | 36.6k | if (!isRegionMode()) |
111 | 35.7k | while (29.5k BlockTraits::child_end(node->getEntry()) != BItor && 35.7k isExit(*BItor)31.4k ) |
112 | 6.16k | ++BItor; |
113 | 36.6k | |
114 | 36.6k | if (isRegionMode() && 36.6k isExit(getRegionSucc())7.09k ) |
115 | 1.08k | advanceRegionSucc(); |
116 | 36.6k | } llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::RNSuccIterator(llvm::RegionNode const*) Line | Count | Source | 108 | 8 | BItor(BlockTraits::child_begin(node->getEntry())) { | 109 | 8 | // Skip the exit block | 110 | 8 | if (!isRegionMode()) | 111 | 10 | while (6 BlockTraits::child_end(node->getEntry()) != BItor && 10 isExit(*BItor)6 ) | 112 | 4 | ++BItor; | 113 | 8 | | 114 | 8 | if (isRegionMode() && 8 isExit(getRegionSucc())2 ) | 115 | 0 | advanceRegionSucc(); | 116 | 8 | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::RNSuccIterator(llvm::MachineRegionNode*) Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::RNSuccIterator(llvm::MachineRegionNode const*) llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::RNSuccIterator(llvm::RegionNode*) Line | Count | Source | 108 | 36.6k | BItor(BlockTraits::child_begin(node->getEntry())) { | 109 | 36.6k | // Skip the exit block | 110 | 36.6k | if (!isRegionMode()) | 111 | 35.7k | while (29.5k BlockTraits::child_end(node->getEntry()) != BItor && 35.7k isExit(*BItor)31.4k ) | 112 | 6.15k | ++BItor; | 113 | 36.6k | | 114 | 36.6k | if (isRegionMode() && 36.6k isExit(getRegionSucc())7.09k ) | 115 | 1.08k | advanceRegionSucc(); | 116 | 36.6k | } |
|
117 | | |
118 | | /// @brief Create an end iterator. |
119 | | inline RNSuccIterator(NodeRef node, bool) |
120 | | : Node(node, node->isSubRegion() ? ItRgEnd : ItBB), |
121 | 69.0k | BItor(BlockTraits::child_end(node->getEntry())) {} llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::RNSuccIterator(llvm::RegionNode*, bool) Line | Count | Source | 121 | 69.0k | BItor(BlockTraits::child_end(node->getEntry())) {} |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::RNSuccIterator(llvm::MachineRegionNode const*, bool) Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::RNSuccIterator(llvm::MachineRegionNode*, bool) llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::RNSuccIterator(llvm::RegionNode const*, bool) Line | Count | Source | 121 | 12 | BItor(BlockTraits::child_end(node->getEntry())) {} |
|
122 | | |
123 | 69.0k | inline bool operator==(const Self& x) const { |
124 | 69.0k | assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); |
125 | 69.0k | if (isRegionMode()) |
126 | 13.0k | return Node.getInt() == x.Node.getInt(); |
127 | 69.0k | else |
128 | 55.9k | return BItor == x.BItor; |
129 | 69.0k | } llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::operator==(llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region> const&) const Line | Count | Source | 123 | 69.0k | inline bool operator==(const Self& x) const { | 124 | 69.0k | assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); | 125 | 69.0k | if (isRegionMode()) | 126 | 13.0k | return Node.getInt() == x.Node.getInt(); | 127 | 69.0k | else | 128 | 55.9k | return BItor == x.BItor; | 129 | 69.0k | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator==(llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion> const&) const llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::operator==(llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region> const&) const Line | Count | Source | 123 | 12 | inline bool operator==(const Self& x) const { | 124 | 12 | assert(isRegionMode() == x.isRegionMode() && "Broken iterator!"); | 125 | 12 | if (isRegionMode()) | 126 | 4 | return Node.getInt() == x.Node.getInt(); | 127 | 12 | else | 128 | 8 | return BItor == x.BItor; | 129 | 12 | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator==(llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion> const&) const |
130 | | |
131 | 69.0k | inline bool operator!=(const Self& x) const { return !operator==(x); } Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator!=(llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion> const&) const llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::operator!=(llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region> const&) const Line | Count | Source | 131 | 12 | inline bool operator!=(const Self& x) const { return !operator==(x); } |
llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::operator!=(llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region> const&) const Line | Count | Source | 131 | 69.0k | inline bool operator!=(const Self& x) const { return !operator==(x); } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator!=(llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion> const&) const |
132 | | |
133 | 32.3k | inline value_type operator*() const { |
134 | 32.3k | BlockT *BB = isRegionMode() ? getRegionSucc()6.00k : *BItor26.3k ; |
135 | 32.3k | assert(!isExit(BB) && "Iterator out of range!"); |
136 | 32.3k | return getISucc(BB); |
137 | 32.3k | } Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator*() const llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::operator*() const Line | Count | Source | 133 | 4 | inline value_type operator*() const { | 134 | 4 | BlockT *BB = isRegionMode() ? getRegionSucc()2 : *BItor2 ; | 135 | 4 | assert(!isExit(BB) && "Iterator out of range!"); | 136 | 4 | return getISucc(BB); | 137 | 4 | } |
llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::operator*() const Line | Count | Source | 133 | 32.3k | inline value_type operator*() const { | 134 | 32.3k | BlockT *BB = isRegionMode() ? getRegionSucc()6.00k : *BItor26.3k ; | 135 | 32.3k | assert(!isExit(BB) && "Iterator out of range!"); | 136 | 32.3k | return getISucc(BB); | 137 | 32.3k | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator*() const |
138 | | |
139 | 32.3k | inline Self& operator++() { |
140 | 32.3k | if(isRegionMode()32.3k ) { |
141 | 6.00k | // The Region only has 1 successor. |
142 | 6.00k | advanceRegionSucc(); |
143 | 32.3k | } else { |
144 | 26.3k | // Skip the exit. |
145 | 26.3k | do |
146 | 34.5k | ++BItor; |
147 | 34.5k | while (BItor != BlockTraits::child_end(getNode()->getEntry()) |
148 | 9.23k | && isExit(*BItor)); |
149 | 26.3k | } |
150 | 32.3k | return *this; |
151 | 32.3k | } Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator++() llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::operator++() Line | Count | Source | 139 | 32.3k | inline Self& operator++() { | 140 | 32.3k | if(isRegionMode()32.3k ) { | 141 | 6.00k | // The Region only has 1 successor. | 142 | 6.00k | advanceRegionSucc(); | 143 | 32.3k | } else { | 144 | 26.3k | // Skip the exit. | 145 | 26.3k | do | 146 | 34.5k | ++BItor; | 147 | 34.5k | while (BItor != BlockTraits::child_end(getNode()->getEntry()) | 148 | 9.23k | && isExit(*BItor)); | 149 | 26.3k | } | 150 | 32.3k | return *this; | 151 | 32.3k | } |
llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::operator++() Line | Count | Source | 139 | 4 | inline Self& operator++() { | 140 | 4 | if(isRegionMode()4 ) { | 141 | 2 | // The Region only has 1 successor. | 142 | 2 | advanceRegionSucc(); | 143 | 4 | } else { | 144 | 2 | // Skip the exit. | 145 | 2 | do | 146 | 4 | ++BItor; | 147 | 4 | while (BItor != BlockTraits::child_end(getNode()->getEntry()) | 148 | 2 | && isExit(*BItor)); | 149 | 2 | } | 150 | 4 | return *this; | 151 | 4 | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator++() |
152 | | |
153 | 32.3k | inline Self operator++(int) { |
154 | 32.3k | Self tmp = *this; |
155 | 32.3k | ++*this; |
156 | 32.3k | return tmp; |
157 | 32.3k | } llvm::RNSuccIterator<llvm::RegionNode*, llvm::BasicBlock, llvm::Region>::operator++(int) Line | Count | Source | 153 | 32.3k | inline Self operator++(int) { | 154 | 32.3k | Self tmp = *this; | 155 | 32.3k | ++*this; | 156 | 32.3k | return tmp; | 157 | 32.3k | } |
Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator++(int) Unexecuted instantiation: llvm::RNSuccIterator<llvm::MachineRegionNode const*, llvm::MachineBasicBlock, llvm::MachineRegion>::operator++(int) llvm::RNSuccIterator<llvm::RegionNode const*, llvm::BasicBlock, llvm::Region>::operator++(int) Line | Count | Source | 153 | 4 | inline Self operator++(int) { | 154 | 4 | Self tmp = *this; | 155 | 4 | ++*this; | 156 | 4 | return tmp; | 157 | 4 | } |
|
158 | | }; |
159 | | |
160 | | //===----------------------------------------------------------------------===// |
161 | | /// @brief Flat RegionNode iterator. |
162 | | /// |
163 | | /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that |
164 | | /// are contained in the Region and its subregions. This is close to a virtual |
165 | | /// control flow graph of the Region. |
166 | | template <class NodeRef, class BlockT, class RegionT> |
167 | | class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> |
168 | | : public std::iterator<std::forward_iterator_tag, NodeRef> { |
169 | | using super = std::iterator<std::forward_iterator_tag, NodeRef>; |
170 | | using BlockTraits = GraphTraits<BlockT *>; |
171 | | using SuccIterTy = typename BlockTraits::ChildIteratorType; |
172 | | |
173 | | NodeRef Node; |
174 | | SuccIterTy Itor; |
175 | | |
176 | | public: |
177 | | using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>; |
178 | | using value_type = typename super::value_type; |
179 | | |
180 | | /// @brief Create the iterator from a RegionNode. |
181 | | /// |
182 | | /// Note that the incoming node must be a bb node, otherwise it will trigger |
183 | | /// an assertion when we try to get a BasicBlock. |
184 | | inline RNSuccIterator(NodeRef node) |
185 | 27 | : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) { |
186 | 27 | assert(!Node->isSubRegion() && |
187 | 27 | "Subregion node not allowed in flat iterating mode!"); |
188 | 27 | assert(Node->getParent() && "A BB node must have a parent!"); |
189 | 27 | |
190 | 27 | // Skip the exit block of the iterating region. |
191 | 27 | while (BlockTraits::child_end(Node->getEntry()) != Itor && |
192 | 24 | Node->getParent()->getExit() == *Itor) |
193 | 0 | ++Itor; |
194 | 27 | } |
195 | | |
196 | | /// @brief Create an end iterator |
197 | | inline RNSuccIterator(NodeRef node, bool) |
198 | 37 | : Node(node), Itor(BlockTraits::child_end(node->getEntry())) { |
199 | 37 | assert(!Node->isSubRegion() && |
200 | 37 | "Subregion node not allowed in flat iterating mode!"); |
201 | 37 | } |
202 | | |
203 | 75 | inline bool operator==(const Self& x) const { |
204 | 75 | assert(Node->getParent() == x.Node->getParent() |
205 | 75 | && "Cannot compare iterators of different regions!"); |
206 | 75 | |
207 | 45 | return Itor == x.Itor && Node == x.Node; |
208 | 75 | } |
209 | | |
210 | 75 | inline bool operator!=(const Self& x) const { return !operator==(x); } |
211 | | |
212 | 40 | inline value_type operator*() const { |
213 | 40 | BlockT *BB = *Itor; |
214 | 40 | |
215 | 40 | // Get the iterating region. |
216 | 40 | RegionT *Parent = Node->getParent(); |
217 | 40 | |
218 | 40 | // The only case that the successor reaches out of the region is it reaches |
219 | 40 | // the exit of the region. |
220 | 40 | assert(Parent->getExit() != BB && "iterator out of range!"); |
221 | 40 | |
222 | 40 | return Parent->getBBNode(BB); |
223 | 40 | } |
224 | | |
225 | 30 | inline Self& operator++() { |
226 | 30 | // Skip the exit block of the iterating region. |
227 | 30 | do |
228 | 30 | ++Itor; |
229 | 30 | while (Itor != succ_end(Node->getEntry()) |
230 | 6 | && Node->getParent()->getExit() == *Itor); |
231 | 30 | |
232 | 30 | return *this; |
233 | 30 | } |
234 | | |
235 | 10 | inline Self operator++(int) { |
236 | 10 | Self tmp = *this; |
237 | 10 | ++*this; |
238 | 10 | return tmp; |
239 | 10 | } |
240 | | }; |
241 | | |
242 | | template <class NodeRef, class BlockT, class RegionT> |
243 | | inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) { |
244 | | return RNSuccIterator<NodeRef, BlockT, RegionT>(Node); |
245 | | } |
246 | | |
247 | | template <class NodeRef, class BlockT, class RegionT> |
248 | | inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) { |
249 | | return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true); |
250 | | } |
251 | | |
252 | | //===--------------------------------------------------------------------===// |
253 | | // RegionNode GraphTraits specialization so the bbs in the region can be |
254 | | // iterate by generic graph iterators. |
255 | | // |
256 | | // NodeT can either be region node or const region node, otherwise child_begin |
257 | | // and child_end fail. |
258 | | |
259 | | #define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \ |
260 | | template <> struct GraphTraits<NodeT *> { \ |
261 | | using NodeRef = NodeT *; \ |
262 | | using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>; \ |
263 | 12.7k | static NodeRef getEntryNode(NodeRef N) { return N; } \ Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegionNode*>::getEntryNode(llvm::MachineRegionNode*) Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegionNode const*>::getEntryNode(llvm::MachineRegionNode const*) llvm::GraphTraits<llvm::RegionNode const*>::getEntryNode(llvm::RegionNode const*) Line | Count | Source | 263 | 4 | static NodeRef getEntryNode(NodeRef N) { return N; } \ |
llvm::GraphTraits<llvm::RegionNode*>::getEntryNode(llvm::RegionNode*) Line | Count | Source | 263 | 12.7k | static NodeRef getEntryNode(NodeRef N) { return N; } \ |
|
264 | 36.6k | static inline ChildIteratorType child_begin(NodeRef N) { \ |
265 | 36.6k | return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \ |
266 | 36.6k | } \ llvm::GraphTraits<llvm::RegionNode*>::child_begin(llvm::RegionNode*) Line | Count | Source | 264 | 36.6k | static inline ChildIteratorType child_begin(NodeRef N) { \ | 265 | 36.6k | return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \ | 266 | 36.6k | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegionNode const*>::child_begin(llvm::MachineRegionNode const*) llvm::GraphTraits<llvm::RegionNode const*>::child_begin(llvm::RegionNode const*) Line | Count | Source | 264 | 8 | static inline ChildIteratorType child_begin(NodeRef N) { \ | 265 | 8 | return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \ | 266 | 8 | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegionNode*>::child_begin(llvm::MachineRegionNode*) |
267 | 69.0k | static inline ChildIteratorType child_end(NodeRef N) { \ |
268 | 69.0k | return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \ |
269 | 69.0k | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegionNode*>::child_end(llvm::MachineRegionNode*) Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegionNode const*>::child_end(llvm::MachineRegionNode const*) llvm::GraphTraits<llvm::RegionNode const*>::child_end(llvm::RegionNode const*) Line | Count | Source | 267 | 12 | static inline ChildIteratorType child_end(NodeRef N) { \ | 268 | 12 | return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \ | 269 | 12 | } \ |
llvm::GraphTraits<llvm::RegionNode*>::child_end(llvm::RegionNode*) Line | Count | Source | 267 | 69.0k | static inline ChildIteratorType child_end(NodeRef N) { \ | 268 | 69.0k | return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \ | 269 | 69.0k | } \ |
|
270 | | }; \ |
271 | | template <> struct GraphTraits<FlatIt<NodeT *>> { \ |
272 | | using NodeRef = NodeT *; \ |
273 | | using ChildIteratorType = \ |
274 | | RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>; \ |
275 | 1 | static NodeRef getEntryNode(NodeRef N) { return N; } \ Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::RegionNode const*> >::getEntryNode(llvm::RegionNode const*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegionNode const*> >::getEntryNode(llvm::MachineRegionNode const*) llvm::GraphTraits<llvm::FlatIt<llvm::RegionNode*> >::getEntryNode(llvm::RegionNode*) Line | Count | Source | 275 | 1 | static NodeRef getEntryNode(NodeRef N) { return N; } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegionNode*> >::getEntryNode(llvm::MachineRegionNode*) |
276 | 27 | static inline ChildIteratorType child_begin(NodeRef N) { \ |
277 | 27 | return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N); \ |
278 | 27 | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::RegionNode const*> >::child_begin(llvm::RegionNode const*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegionNode const*> >::child_begin(llvm::MachineRegionNode const*) llvm::GraphTraits<llvm::FlatIt<llvm::RegionNode*> >::child_begin(llvm::RegionNode*) Line | Count | Source | 276 | 27 | static inline ChildIteratorType child_begin(NodeRef N) { \ | 277 | 27 | return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N); \ | 278 | 27 | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegionNode*> >::child_begin(llvm::MachineRegionNode*) |
279 | 37 | static inline ChildIteratorType child_end(NodeRef N) { \ |
280 | 37 | return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true); \ |
281 | 37 | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegionNode const*> >::child_end(llvm::MachineRegionNode const*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegionNode*> >::child_end(llvm::MachineRegionNode*) llvm::GraphTraits<llvm::FlatIt<llvm::RegionNode*> >::child_end(llvm::RegionNode*) Line | Count | Source | 279 | 37 | static inline ChildIteratorType child_end(NodeRef N) { \ | 280 | 37 | return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true); \ | 281 | 37 | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::RegionNode const*> >::child_end(llvm::RegionNode const*) |
282 | | } |
283 | | |
284 | | #define RegionGraphTraits(RegionT, NodeT) \ |
285 | | template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> { \ |
286 | | using nodes_iterator = df_iterator<NodeRef>; \ |
287 | 15.8k | static NodeRef getEntryNode(RegionT *R) { \ |
288 | 15.8k | return R->getNode(R->getEntry()); \ |
289 | 15.8k | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegion*>::getEntryNode(llvm::MachineRegion*) Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegion const*>::getEntryNode(llvm::MachineRegion const*) llvm::GraphTraits<llvm::Region const*>::getEntryNode(llvm::Region const*) Line | Count | Source | 287 | 8 | static NodeRef getEntryNode(RegionT *R) { \ | 288 | 8 | return R->getNode(R->getEntry()); \ | 289 | 8 | } \ |
llvm::GraphTraits<llvm::Region*>::getEntryNode(llvm::Region*) Line | Count | Source | 287 | 15.7k | static NodeRef getEntryNode(RegionT *R) { \ | 288 | 15.7k | return R->getNode(R->getEntry()); \ | 289 | 15.7k | } \ |
|
290 | 3.09k | static nodes_iterator nodes_begin(RegionT *R) { \ |
291 | 3.09k | return nodes_iterator::begin(getEntryNode(R)); \ |
292 | 3.09k | } \ llvm::GraphTraits<llvm::Region*>::nodes_begin(llvm::Region*) Line | Count | Source | 290 | 3.09k | static nodes_iterator nodes_begin(RegionT *R) { \ | 291 | 3.09k | return nodes_iterator::begin(getEntryNode(R)); \ | 292 | 3.09k | } \ |
llvm::GraphTraits<llvm::Region const*>::nodes_begin(llvm::Region const*) Line | Count | Source | 290 | 4 | static nodes_iterator nodes_begin(RegionT *R) { \ | 291 | 4 | return nodes_iterator::begin(getEntryNode(R)); \ | 292 | 4 | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegion const*>::nodes_begin(llvm::MachineRegion const*) Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegion*>::nodes_begin(llvm::MachineRegion*) |
293 | 3.09k | static nodes_iterator nodes_end(RegionT *R) { \ |
294 | 3.09k | return nodes_iterator::end(getEntryNode(R)); \ |
295 | 3.09k | } \ llvm::GraphTraits<llvm::Region const*>::nodes_end(llvm::Region const*) Line | Count | Source | 293 | 4 | static nodes_iterator nodes_end(RegionT *R) { \ | 294 | 4 | return nodes_iterator::end(getEntryNode(R)); \ | 295 | 4 | } \ |
llvm::GraphTraits<llvm::Region*>::nodes_end(llvm::Region*) Line | Count | Source | 293 | 3.09k | static nodes_iterator nodes_end(RegionT *R) { \ | 294 | 3.09k | return nodes_iterator::end(getEntryNode(R)); \ | 295 | 3.09k | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegion*>::nodes_end(llvm::MachineRegion*) Unexecuted instantiation: llvm::GraphTraits<llvm::MachineRegion const*>::nodes_end(llvm::MachineRegion const*) |
296 | | }; \ |
297 | | template <> \ |
298 | | struct GraphTraits<FlatIt<RegionT *>> \ |
299 | | : public GraphTraits<FlatIt<NodeT *>> { \ |
300 | | using nodes_iterator = \ |
301 | | df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, \ |
302 | | GraphTraits<FlatIt<NodeRef>>>; \ |
303 | 2 | static NodeRef getEntryNode(RegionT *R) { \ |
304 | 2 | return R->getBBNode(R->getEntry()); \ |
305 | 2 | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::Region const*> >::getEntryNode(llvm::Region const*) llvm::GraphTraits<llvm::FlatIt<llvm::Region*> >::getEntryNode(llvm::Region*) Line | Count | Source | 303 | 2 | static NodeRef getEntryNode(RegionT *R) { \ | 304 | 2 | return R->getBBNode(R->getEntry()); \ | 305 | 2 | } \ |
Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegion*> >::getEntryNode(llvm::MachineRegion*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegion const*> >::getEntryNode(llvm::MachineRegion const*) |
306 | 0 | static nodes_iterator nodes_begin(RegionT *R) { \ |
307 | 0 | return nodes_iterator::begin(getEntryNode(R)); \ |
308 | 0 | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::Region const*> >::nodes_begin(llvm::Region const*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::Region*> >::nodes_begin(llvm::Region*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegion*> >::nodes_begin(llvm::MachineRegion*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegion const*> >::nodes_begin(llvm::MachineRegion const*) |
309 | 0 | static nodes_iterator nodes_end(RegionT *R) { \ |
310 | 0 | return nodes_iterator::end(getEntryNode(R)); \ |
311 | 0 | } \ Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegion const*> >::nodes_end(llvm::MachineRegion const*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::MachineRegion*> >::nodes_end(llvm::MachineRegion*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::Region const*> >::nodes_end(llvm::Region const*) Unexecuted instantiation: llvm::GraphTraits<llvm::FlatIt<llvm::Region*> >::nodes_end(llvm::Region*) |
312 | | } |
313 | | |
314 | | RegionNodeGraphTraits(RegionNode, BasicBlock, Region); |
315 | | RegionNodeGraphTraits(const RegionNode, BasicBlock, Region); |
316 | | |
317 | | RegionGraphTraits(Region, RegionNode); |
318 | | RegionGraphTraits(const Region, const RegionNode); |
319 | | |
320 | | template <> struct GraphTraits<RegionInfo*> |
321 | | : public GraphTraits<FlatIt<RegionNode*>> { |
322 | | using nodes_iterator = |
323 | | df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, |
324 | | GraphTraits<FlatIt<NodeRef>>>; |
325 | | |
326 | 2 | static NodeRef getEntryNode(RegionInfo *RI) { |
327 | 2 | return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion()); |
328 | 2 | } |
329 | | |
330 | 0 | static nodes_iterator nodes_begin(RegionInfo* RI) { |
331 | 0 | return nodes_iterator::begin(getEntryNode(RI)); |
332 | 0 | } |
333 | | |
334 | 0 | static nodes_iterator nodes_end(RegionInfo *RI) { |
335 | 0 | return nodes_iterator::end(getEntryNode(RI)); |
336 | 0 | } |
337 | | }; |
338 | | |
339 | | template <> struct GraphTraits<RegionInfoPass*> |
340 | | : public GraphTraits<RegionInfo *> { |
341 | | using nodes_iterator = |
342 | | df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, |
343 | | GraphTraits<FlatIt<NodeRef>>>; |
344 | | |
345 | 0 | static NodeRef getEntryNode(RegionInfoPass *RI) { |
346 | 0 | return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo()); |
347 | 0 | } |
348 | | |
349 | 0 | static nodes_iterator nodes_begin(RegionInfoPass* RI) { |
350 | 0 | return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo()); |
351 | 0 | } |
352 | | |
353 | 0 | static nodes_iterator nodes_end(RegionInfoPass *RI) { |
354 | 0 | return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo()); |
355 | 0 | } |
356 | | }; |
357 | | |
358 | | } // end namespace llvm |
359 | | |
360 | | #endif // LLVM_ANALYSIS_REGIONITERATOR_H |