Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/SCCIterator.h
Line
Count
Source (jump to first uncovered line)
1
//===- ADT/SCCIterator.h - Strongly Connected Comp. Iter. -------*- 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
/// \file
10
///
11
/// This builds on the llvm/ADT/GraphTraits.h file to find the strongly
12
/// connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS
13
/// algorithm.
14
///
15
/// The SCC iterator has the important property that if a node in SCC S1 has an
16
/// edge to a node in SCC S2, then it visits S1 *after* S2.
17
///
18
/// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE:
19
/// This requires some simple wrappers and is not supported yet.)
20
///
21
//===----------------------------------------------------------------------===//
22
23
#ifndef LLVM_ADT_SCCITERATOR_H
24
#define LLVM_ADT_SCCITERATOR_H
25
26
#include "llvm/ADT/DenseMap.h"
27
#include "llvm/ADT/GraphTraits.h"
28
#include "llvm/ADT/iterator.h"
29
#include <cassert>
30
#include <cstddef>
31
#include <iterator>
32
#include <vector>
33
34
namespace llvm {
35
36
/// \brief Enumerate the SCCs of a directed graph in reverse topological order
37
/// of the SCC DAG.
38
///
39
/// This is implemented using Tarjan's DFS algorithm using an internal stack to
40
/// build up a vector of nodes in a particular SCC. Note that it is a forward
41
/// iterator and thus you cannot backtrack or re-visit nodes.
42
template <class GraphT, class GT = GraphTraits<GraphT>>
43
class scc_iterator : public iterator_facade_base<
44
                         scc_iterator<GraphT, GT>, std::forward_iterator_tag,
45
                         const std::vector<typename GT::NodeRef>, ptrdiff_t> {
46
  using NodeRef = typename GT::NodeRef;
47
  using ChildItTy = typename GT::ChildIteratorType;
48
  using SccTy = std::vector<NodeRef>;
49
  using reference = typename scc_iterator::reference;
50
51
  /// Element of VisitStack during DFS.
52
  struct StackElement {
53
    NodeRef Node;         ///< The current node pointer.
54
    ChildItTy NextChild;  ///< The next child, modified inplace during DFS.
55
    unsigned MinVisited;  ///< Minimum uplink value of all children of Node.
56
57
    StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
58
5.86M
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::StackElement::StackElement(std::__1::pair<llvm::Loop const*, llvm::BasicBlock*>, llvm::filter_iterator<llvm::LoopBodyTraits::WrappedSuccIterator, llvm::LoopBodyTraits::LoopBodyFilter> const&, unsigned int)
Line
Count
Source
58
573k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::StackElement::StackElement(llvm::CallGraphNode*, llvm::mapped_iterator<std::__1::__wrap_iter<std::__1::pair<llvm::WeakTrackingVH, llvm::CallGraphNode*>*>, llvm::CallGraphNode* (*)(std::__1::pair<llvm::WeakTrackingVH, llvm::CallGraphNode*>)> const&, unsigned int)
Line
Count
Source
58
4.53M
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::StackElement::StackElement(llvm::MachineBasicBlock*, std::__1::__wrap_iter<llvm::MachineBasicBlock**> const&, unsigned int)
Line
Count
Source
58
2.17k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::StackElement::StackElement(llvm::bfi_detail::IrreducibleGraph::IrrNode const*, std::__1::__deque_iterator<llvm::bfi_detail::IrreducibleGraph::IrrNode const*, llvm::bfi_detail::IrreducibleGraph::IrrNode const* const*, llvm::bfi_detail::IrreducibleGraph::IrrNode const* const&, llvm::bfi_detail::IrreducibleGraph::IrrNode const* const* const*, long, 512l> const&, unsigned int)
Line
Count
Source
58
21.5k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::StackElement::StackElement((anonymous namespace)::ArgumentGraphNode*, (anonymous namespace)::ArgumentGraphNode** const&, unsigned int)
Line
Count
Source
58
728k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::StackElement::StackElement(llvm::BasicBlock*, llvm::TerminatorInst::SuccIterator<llvm::TerminatorInst*, llvm::BasicBlock> const&, unsigned int)
59
60
0
    bool operator==(const StackElement &Other) const {
61
0
      return Node == Other.Node &&
62
0
             NextChild == Other.NextChild &&
63
0
             MinVisited == Other.MinVisited;
64
0
    }
65
  };
66
67
  /// The visit counters used to detect when a complete SCC is on the stack.
68
  /// visitNum is the global counter.
69
  ///
70
  /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
71
  unsigned visitNum;
72
  DenseMap<NodeRef, unsigned> nodeVisitNumbers;
73
74
  /// Stack holding nodes of the SCC.
75
  std::vector<NodeRef> SCCNodeStack;
76
77
  /// The current SCC, retrieved using operator*().
78
  SccTy CurrentSCC;
79
80
  /// DFS stack, Used to maintain the ordering.  The top contains the current
81
  /// node, the next child to visit, and the minimum uplink value of all child
82
  std::vector<StackElement> VisitStack;
83
84
  /// A single "visit" within the non-recursive DFS traversal.
85
  void DFSVisitOne(NodeRef N);
86
87
  /// The stack-based DFS traversal; defined below.
88
  void DFSVisitChildren();
89
90
  /// Compute the next SCC using the DFS traversal.
91
  void GetNextSCC();
92
93
1.09M
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
1.09M
    DFSVisitOne(entryN);
95
1.09M
    GetNextSCC();
96
1.09M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::scc_iterator(llvm::BasicBlock*)
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::scc_iterator(llvm::CallGraphNode*)
Line
Count
Source
93
113k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
113k
    DFSVisitOne(entryN);
95
113k
    GetNextSCC();
96
113k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::scc_iterator(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
93
584
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
584
    DFSVisitOne(entryN);
95
584
    GetNextSCC();
96
584
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::scc_iterator((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
93
726k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
726k
    DFSVisitOne(entryN);
95
726k
    GetNextSCC();
96
726k
  }
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::scc_iterator(std::__1::pair<llvm::Loop const*, llvm::BasicBlock*>)
Line
Count
Source
93
253k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
253k
    DFSVisitOne(entryN);
95
253k
    GetNextSCC();
96
253k
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::scc_iterator(llvm::MachineBasicBlock*)
Line
Count
Source
93
2.05k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
2.05k
    DFSVisitOne(entryN);
95
2.05k
    GetNextSCC();
96
2.05k
  }
97
98
  /// End is when the DFS stack is empty.
99
253k
  scc_iterator() = default;
100
101
public:
102
1.09M
  static scc_iterator begin(const GraphT &G) {
103
1.09M
    return scc_iterator(GT::getEntryNode(G));
104
1.09M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::begin(llvm::Function* const&)
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::begin(llvm::bfi_detail::IrreducibleGraph const&)
Line
Count
Source
102
584
  static scc_iterator begin(const GraphT &G) {
103
584
    return scc_iterator(GT::getEntryNode(G));
104
584
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::begin(llvm::MachineFunction* const&)
Line
Count
Source
102
2.05k
  static scc_iterator begin(const GraphT &G) {
103
2.05k
    return scc_iterator(GT::getEntryNode(G));
104
2.05k
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::begin(llvm::CallGraph* const&)
Line
Count
Source
102
113k
  static scc_iterator begin(const GraphT &G) {
103
113k
    return scc_iterator(GT::getEntryNode(G));
104
113k
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::begin((anonymous namespace)::ArgumentGraph* const&)
Line
Count
Source
102
726k
  static scc_iterator begin(const GraphT &G) {
103
726k
    return scc_iterator(GT::getEntryNode(G));
104
726k
  }
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::begin(llvm::Loop const&)
Line
Count
Source
102
253k
  static scc_iterator begin(const GraphT &G) {
103
253k
    return scc_iterator(GT::getEntryNode(G));
104
253k
  }
105
253k
  static scc_iterator end(const GraphT &) { return scc_iterator(); }
106
107
  /// \brief Direct loop termination test which is more efficient than
108
  /// comparison with \c end().
109
6.12M
  bool isAtEnd() const {
110
6.12M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
6.12M
    return CurrentSCC.empty();
112
6.12M
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::isAtEnd() const
Line
Count
Source
109
1.45M
  bool isAtEnd() const {
110
1.45M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
1.45M
    return CurrentSCC.empty();
112
1.45M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::isAtEnd() const
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::isAtEnd() const
Line
Count
Source
109
4.64M
  bool isAtEnd() const {
110
4.64M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
4.64M
    return CurrentSCC.empty();
112
4.64M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::isAtEnd() const
Line
Count
Source
109
4.21k
  bool isAtEnd() const {
110
4.21k
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
4.21k
    return CurrentSCC.empty();
112
4.21k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::isAtEnd() const
Line
Count
Source
109
14.1k
  bool isAtEnd() const {
110
14.1k
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
14.1k
    return CurrentSCC.empty();
112
14.1k
  }
113
114
826k
  bool operator==(const scc_iterator &x) const {
115
506k
    return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
116
826k
  }
117
118
5.85M
  scc_iterator &operator++() {
119
5.85M
    GetNextSCC();
120
5.85M
    return *this;
121
5.85M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator++()
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator++()
Line
Count
Source
118
4.53M
  scc_iterator &operator++() {
119
4.53M
    GetNextSCC();
120
4.53M
    return *this;
121
4.53M
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator++()
Line
Count
Source
118
13.5k
  scc_iterator &operator++() {
119
13.5k
    GetNextSCC();
120
13.5k
    return *this;
121
13.5k
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator++()
Line
Count
Source
118
727k
  scc_iterator &operator++() {
119
727k
    GetNextSCC();
120
727k
    return *this;
121
727k
  }
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::operator++()
Line
Count
Source
118
573k
  scc_iterator &operator++() {
119
573k
    GetNextSCC();
120
573k
    return *this;
121
573k
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator++()
Line
Count
Source
118
2.15k
  scc_iterator &operator++() {
119
2.15k
    GetNextSCC();
120
2.15k
    return *this;
121
2.15k
  }
122
123
6.56M
  reference operator*() const {
124
6.56M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
6.56M
    return CurrentSCC;
126
6.56M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator*() const
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator*() const
Line
Count
Source
123
5.24M
  reference operator*() const {
124
5.24M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
5.24M
    return CurrentSCC;
126
5.24M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator*() const
Line
Count
Source
123
2.15k
  reference operator*() const {
124
2.15k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
2.15k
    return CurrentSCC;
126
2.15k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator*() const
Line
Count
Source
123
14.3k
  reference operator*() const {
124
14.3k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
14.3k
    return CurrentSCC;
126
14.3k
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator*() const
Line
Count
Source
123
727k
  reference operator*() const {
124
727k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
727k
    return CurrentSCC;
126
727k
  }
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::operator*() const
Line
Count
Source
123
573k
  reference operator*() const {
124
573k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
573k
    return CurrentSCC;
126
573k
  }
127
128
  /// \brief Test if the current SCC has a loop.
129
  ///
130
  /// If the SCC has more than one node, this is trivially true.  If not, it may
131
  /// still contain a loop if the node has an edge back to itself.
132
  bool hasLoop() const;
133
134
  /// This informs the \c scc_iterator that the specified \c Old node
135
  /// has been deleted, and \c New is to be used in its place.
136
2.70k
  void ReplaceNode(NodeRef Old, NodeRef New) {
137
2.70k
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
138
2.70k
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
139
2.70k
    nodeVisitNumbers.erase(Old);
140
2.70k
  }
141
};
142
143
template <class GraphT, class GT>
144
5.86M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
5.86M
  ++visitNum;
146
5.86M
  nodeVisitNumbers[N] = visitNum;
147
5.86M
  SCCNodeStack.push_back(N);
148
5.86M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
#if 0 // Enable if needed when debugging.
150
  dbgs() << "TarjanSCC: Node " << N <<
151
        " : visitNum = " << visitNum << "\n";
152
#endif
153
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitOne((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
144
728k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
728k
  ++visitNum;
146
728k
  nodeVisitNumbers[N] = visitNum;
147
728k
  SCCNodeStack.push_back(N);
148
728k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
#if 0 // Enable if needed when debugging.
150
  dbgs() << "TarjanSCC: Node " << N <<
151
        " : visitNum = " << visitNum << "\n";
152
#endif
153
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitOne(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
144
21.5k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
21.5k
  ++visitNum;
146
21.5k
  nodeVisitNumbers[N] = visitNum;
147
21.5k
  SCCNodeStack.push_back(N);
148
21.5k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
#if 0 // Enable if needed when debugging.
150
  dbgs() << "TarjanSCC: Node " << N <<
151
        " : visitNum = " << visitNum << "\n";
152
#endif
153
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitOne(llvm::MachineBasicBlock*)
Line
Count
Source
144
2.17k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
2.17k
  ++visitNum;
146
2.17k
  nodeVisitNumbers[N] = visitNum;
147
2.17k
  SCCNodeStack.push_back(N);
148
2.17k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
#if 0 // Enable if needed when debugging.
150
  dbgs() << "TarjanSCC: Node " << N <<
151
        " : visitNum = " << visitNum << "\n";
152
#endif
153
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitOne(llvm::CallGraphNode*)
Line
Count
Source
144
4.53M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
4.53M
  ++visitNum;
146
4.53M
  nodeVisitNumbers[N] = visitNum;
147
4.53M
  SCCNodeStack.push_back(N);
148
4.53M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
#if 0 // Enable if needed when debugging.
150
  dbgs() << "TarjanSCC: Node " << N <<
151
        " : visitNum = " << visitNum << "\n";
152
#endif
153
}
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::DFSVisitOne(std::__1::pair<llvm::Loop const*, llvm::BasicBlock*>)
Line
Count
Source
144
573k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
573k
  ++visitNum;
146
573k
  nodeVisitNumbers[N] = visitNum;
147
573k
  SCCNodeStack.push_back(N);
148
573k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
#if 0 // Enable if needed when debugging.
150
  dbgs() << "TarjanSCC: Node " << N <<
151
        " : visitNum = " << visitNum << "\n";
152
#endif
153
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitOne(llvm::BasicBlock*)
154
155
template <class GraphT, class GT>
156
5.86M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
5.86M
  assert(!VisitStack.empty());
158
26.1M
  while (
VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)26.1M
) {
159
20.2M
    // TOS has at least one more child so continue DFS
160
20.2M
    NodeRef childN = *VisitStack.back().NextChild++;
161
20.2M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
20.2M
        nodeVisitNumbers.find(childN);
163
20.2M
    if (
Visited == nodeVisitNumbers.end()20.2M
) {
164
4.76M
      // this node has never been seen.
165
4.76M
      DFSVisitOne(childN);
166
4.76M
      continue;
167
4.76M
    }
168
20.2M
169
15.5M
    unsigned childNum = Visited->second;
170
15.5M
    if (VisitStack.back().MinVisited > childNum)
171
5.23k
      VisitStack.back().MinVisited = childNum;
172
20.2M
  }
173
5.86M
}
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::DFSVisitChildren()
Line
Count
Source
156
573k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
573k
  assert(!VisitStack.empty());
158
1.04M
  while (
VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)1.04M
) {
159
475k
    // TOS has at least one more child so continue DFS
160
475k
    NodeRef childN = *VisitStack.back().NextChild++;
161
475k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
475k
        nodeVisitNumbers.find(childN);
163
475k
    if (
Visited == nodeVisitNumbers.end()475k
) {
164
320k
      // this node has never been seen.
165
320k
      DFSVisitOne(childN);
166
320k
      continue;
167
320k
    }
168
475k
169
155k
    unsigned childNum = Visited->second;
170
155k
    if (VisitStack.back().MinVisited > childNum)
171
5
      VisitStack.back().MinVisited = childNum;
172
475k
  }
173
573k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitChildren()
Line
Count
Source
156
21.5k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
21.5k
  assert(!VisitStack.empty());
158
61.4k
  while (
VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)61.4k
) {
159
39.8k
    // TOS has at least one more child so continue DFS
160
39.8k
    NodeRef childN = *VisitStack.back().NextChild++;
161
39.8k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
39.8k
        nodeVisitNumbers.find(childN);
163
39.8k
    if (
Visited == nodeVisitNumbers.end()39.8k
) {
164
20.9k
      // this node has never been seen.
165
20.9k
      DFSVisitOne(childN);
166
20.9k
      continue;
167
20.9k
    }
168
39.8k
169
18.8k
    unsigned childNum = Visited->second;
170
18.8k
    if (VisitStack.back().MinVisited > childNum)
171
2.86k
      VisitStack.back().MinVisited = childNum;
172
39.8k
  }
173
21.5k
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitChildren()
Line
Count
Source
156
2.17k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
2.17k
  assert(!VisitStack.empty());
158
2.34k
  while (
VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)2.34k
) {
159
171
    // TOS has at least one more child so continue DFS
160
171
    NodeRef childN = *VisitStack.back().NextChild++;
161
171
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
171
        nodeVisitNumbers.find(childN);
163
171
    if (
Visited == nodeVisitNumbers.end()171
) {
164
117
      // this node has never been seen.
165
117
      DFSVisitOne(childN);
166
117
      continue;
167
117
    }
168
171
169
54
    unsigned childNum = Visited->second;
170
54
    if (VisitStack.back().MinVisited > childNum)
171
4
      VisitStack.back().MinVisited = childNum;
172
171
  }
173
2.17k
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitChildren()
Line
Count
Source
156
4.53M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
4.53M
  assert(!VisitStack.empty());
158
24.2M
  while (
VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)24.2M
) {
159
19.7M
    // TOS has at least one more child so continue DFS
160
19.7M
    NodeRef childN = *VisitStack.back().NextChild++;
161
19.7M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
19.7M
        nodeVisitNumbers.find(childN);
163
19.7M
    if (
Visited == nodeVisitNumbers.end()19.7M
) {
164
4.42M
      // this node has never been seen.
165
4.42M
      DFSVisitOne(childN);
166
4.42M
      continue;
167
4.42M
    }
168
19.7M
169
15.3M
    unsigned childNum = Visited->second;
170
15.3M
    if (VisitStack.back().MinVisited > childNum)
171
2.31k
      VisitStack.back().MinVisited = childNum;
172
19.7M
  }
173
4.53M
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitChildren()
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitChildren()
Line
Count
Source
156
728k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
728k
  assert(!VisitStack.empty());
158
731k
  while (
VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)731k
) {
159
3.88k
    // TOS has at least one more child so continue DFS
160
3.88k
    NodeRef childN = *VisitStack.back().NextChild++;
161
3.88k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
3.88k
        nodeVisitNumbers.find(childN);
163
3.88k
    if (
Visited == nodeVisitNumbers.end()3.88k
) {
164
1.05k
      // this node has never been seen.
165
1.05k
      DFSVisitOne(childN);
166
1.05k
      continue;
167
1.05k
    }
168
3.88k
169
2.82k
    unsigned childNum = Visited->second;
170
2.82k
    if (VisitStack.back().MinVisited > childNum)
171
45
      VisitStack.back().MinVisited = childNum;
172
3.88k
  }
173
728k
}
174
175
6.94M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
6.94M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
6.96M
  while (
!VisitStack.empty()6.96M
) {
178
5.86M
    DFSVisitChildren();
179
5.86M
180
5.86M
    // Pop the leaf on top of the VisitStack.
181
5.86M
    NodeRef visitingN = VisitStack.back().Node;
182
5.86M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
5.86M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
5.86M
    VisitStack.pop_back();
185
5.86M
186
5.86M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
5.86M
    if (
!VisitStack.empty() && 5.86M
VisitStack.back().MinVisited > minVisitNum4.76M
)
188
6.64k
      VisitStack.back().MinVisited = minVisitNum;
189
5.86M
190
#if 0 // Enable if needed when debugging.
191
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
          nodeVisitNumbers[visitingN] << "\n";
194
#endif
195
196
5.86M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
11.3k
      continue;
198
5.86M
199
5.86M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
5.86M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
5.86M
    // reset their minVisit values, and return (this suspends
202
5.86M
    // the DFS traversal till the next ++).
203
5.85M
    
do 5.85M
{
204
5.86M
      CurrentSCC.push_back(SCCNodeStack.back());
205
5.86M
      SCCNodeStack.pop_back();
206
5.86M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
5.86M
    } while (CurrentSCC.back() != visitingN);
208
5.85M
    return;
209
5.86M
  }
210
6.94M
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::GetNextSCC()
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::GetNextSCC()
Line
Count
Source
175
1.45M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
1.45M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
1.45M
  while (
!VisitStack.empty()1.45M
) {
178
728k
    DFSVisitChildren();
179
728k
180
728k
    // Pop the leaf on top of the VisitStack.
181
728k
    NodeRef visitingN = VisitStack.back().Node;
182
728k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
728k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
728k
    VisitStack.pop_back();
185
728k
186
728k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
728k
    if (
!VisitStack.empty() && 728k
VisitStack.back().MinVisited > minVisitNum1.05k
)
188
4
      VisitStack.back().MinVisited = minVisitNum;
189
728k
190
#if 0 // Enable if needed when debugging.
191
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
          nodeVisitNumbers[visitingN] << "\n";
194
#endif
195
196
728k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
49
      continue;
198
728k
199
728k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
728k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
728k
    // reset their minVisit values, and return (this suspends
202
728k
    // the DFS traversal till the next ++).
203
727k
    
do 727k
{
204
728k
      CurrentSCC.push_back(SCCNodeStack.back());
205
728k
      SCCNodeStack.pop_back();
206
728k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
728k
    } while (CurrentSCC.back() != visitingN);
208
727k
    return;
209
728k
  }
210
1.45M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::GetNextSCC()
Line
Count
Source
175
4.64M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
4.64M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
4.65M
  while (
!VisitStack.empty()4.65M
) {
178
4.53M
    DFSVisitChildren();
179
4.53M
180
4.53M
    // Pop the leaf on top of the VisitStack.
181
4.53M
    NodeRef visitingN = VisitStack.back().Node;
182
4.53M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
4.53M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
4.53M
    VisitStack.pop_back();
185
4.53M
186
4.53M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
4.53M
    if (
!VisitStack.empty() && 4.53M
VisitStack.back().MinVisited > minVisitNum4.42M
)
188
1.20k
      VisitStack.back().MinVisited = minVisitNum;
189
4.53M
190
#if 0 // Enable if needed when debugging.
191
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
          nodeVisitNumbers[visitingN] << "\n";
194
#endif
195
196
4.53M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.24k
      continue;
198
4.53M
199
4.53M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
4.53M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
4.53M
    // reset their minVisit values, and return (this suspends
202
4.53M
    // the DFS traversal till the next ++).
203
4.53M
    
do 4.53M
{
204
4.53M
      CurrentSCC.push_back(SCCNodeStack.back());
205
4.53M
      SCCNodeStack.pop_back();
206
4.53M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
4.53M
    } while (CurrentSCC.back() != visitingN);
208
4.53M
    return;
209
4.53M
  }
210
4.64M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::GetNextSCC()
Line
Count
Source
175
4.21k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
4.21k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
4.23k
  while (
!VisitStack.empty()4.23k
) {
178
2.17k
    DFSVisitChildren();
179
2.17k
180
2.17k
    // Pop the leaf on top of the VisitStack.
181
2.17k
    NodeRef visitingN = VisitStack.back().Node;
182
2.17k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
2.17k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
2.17k
    VisitStack.pop_back();
185
2.17k
186
2.17k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
2.17k
    if (
!VisitStack.empty() && 2.17k
VisitStack.back().MinVisited > minVisitNum117
)
188
16
      VisitStack.back().MinVisited = minVisitNum;
189
2.17k
190
#if 0 // Enable if needed when debugging.
191
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
          nodeVisitNumbers[visitingN] << "\n";
194
#endif
195
196
2.17k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
20
      continue;
198
2.17k
199
2.17k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
2.17k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
2.17k
    // reset their minVisit values, and return (this suspends
202
2.17k
    // the DFS traversal till the next ++).
203
2.15k
    
do 2.15k
{
204
2.17k
      CurrentSCC.push_back(SCCNodeStack.back());
205
2.17k
      SCCNodeStack.pop_back();
206
2.17k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
2.17k
    } while (CurrentSCC.back() != visitingN);
208
2.15k
    return;
209
2.17k
  }
210
4.21k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::GetNextSCC()
Line
Count
Source
175
14.1k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
14.1k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
22.1k
  while (
!VisitStack.empty()22.1k
) {
178
21.5k
    DFSVisitChildren();
179
21.5k
180
21.5k
    // Pop the leaf on top of the VisitStack.
181
21.5k
    NodeRef visitingN = VisitStack.back().Node;
182
21.5k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
21.5k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
21.5k
    VisitStack.pop_back();
185
21.5k
186
21.5k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
21.5k
    if (
!VisitStack.empty() && 21.5k
VisitStack.back().MinVisited > minVisitNum20.9k
)
188
5.42k
      VisitStack.back().MinVisited = minVisitNum;
189
21.5k
190
#if 0 // Enable if needed when debugging.
191
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
          nodeVisitNumbers[visitingN] << "\n";
194
#endif
195
196
21.5k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
8.00k
      continue;
198
21.5k
199
21.5k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
21.5k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
21.5k
    // reset their minVisit values, and return (this suspends
202
21.5k
    // the DFS traversal till the next ++).
203
13.5k
    
do 13.5k
{
204
21.5k
      CurrentSCC.push_back(SCCNodeStack.back());
205
21.5k
      SCCNodeStack.pop_back();
206
21.5k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
21.5k
    } while (CurrentSCC.back() != visitingN);
208
13.5k
    return;
209
21.5k
  }
210
14.1k
}
llvm::scc_iterator<llvm::Loop, llvm::LoopBodyTraits>::GetNextSCC()
Line
Count
Source
175
826k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
826k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
826k
  while (
!VisitStack.empty()826k
) {
178
573k
    DFSVisitChildren();
179
573k
180
573k
    // Pop the leaf on top of the VisitStack.
181
573k
    NodeRef visitingN = VisitStack.back().Node;
182
573k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
573k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
573k
    VisitStack.pop_back();
185
573k
186
573k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
573k
    if (
!VisitStack.empty() && 573k
VisitStack.back().MinVisited > minVisitNum320k
)
188
4
      VisitStack.back().MinVisited = minVisitNum;
189
573k
190
#if 0 // Enable if needed when debugging.
191
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
          nodeVisitNumbers[visitingN] << "\n";
194
#endif
195
196
573k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
9
      continue;
198
573k
199
573k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
573k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
573k
    // reset their minVisit values, and return (this suspends
202
573k
    // the DFS traversal till the next ++).
203
573k
    
do 573k
{
204
573k
      CurrentSCC.push_back(SCCNodeStack.back());
205
573k
      SCCNodeStack.pop_back();
206
573k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
573k
    } while (CurrentSCC.back() != visitingN);
208
573k
    return;
209
573k
  }
210
826k
}
211
212
template <class GraphT, class GT>
213
0
bool scc_iterator<GraphT, GT>::hasLoop() const {
214
0
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
215
0
    if (CurrentSCC.size() > 1)
216
0
      return true;
217
0
    NodeRef N = CurrentSCC.front();
218
0
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
219
0
         ++CI)
220
0
      
if (0
*CI == N0
)
221
0
        return true;
222
0
    return false;
223
0
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::hasLoop() const
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::hasLoop() const
224
225
/// \brief Construct the begin iterator for a deduced graph type T.
226
843k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
843k
  return scc_iterator<T>::begin(G);
228
843k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> > llvm::scc_begin<llvm::Function*>(llvm::Function* const&)
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> > llvm::scc_begin<llvm::CallGraph*>(llvm::CallGraph* const&)
Line
Count
Source
226
113k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
113k
  return scc_iterator<T>::begin(G);
228
113k
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> > llvm::scc_begin<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
226
2.05k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
2.05k
  return scc_iterator<T>::begin(G);
228
2.05k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> > llvm::scc_begin<llvm::bfi_detail::IrreducibleGraph>(llvm::bfi_detail::IrreducibleGraph const&)
Line
Count
Source
226
584
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
584
  return scc_iterator<T>::begin(G);
228
584
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> > llvm::scc_begin<(anonymous namespace)::ArgumentGraph*>((anonymous namespace)::ArgumentGraph* const&)
Line
Count
Source
226
726k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
726k
  return scc_iterator<T>::begin(G);
228
726k
}
229
230
/// \brief Construct the end iterator for a deduced graph type T.
231
template <class T> scc_iterator<T> scc_end(const T &G) {
232
  return scc_iterator<T>::end(G);
233
}
234
235
} // end namespace llvm
236
237
#endif // LLVM_ADT_SCCITERATOR_H