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