Coverage Report

Created: 2017-10-03 07:32

/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