Coverage Report

Created: 2019-02-15 18:59

/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