Coverage Report

Created: 2018-07-12 09:57

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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
/// 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
22.0M
        : 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.36k
        : 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
25.3k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::StackElement::StackElement(llvm::BasicBlock const*, llvm::TerminatorInst::SuccIterator<llvm::TerminatorInst const*, llvm::BasicBlock const> const&, unsigned int)
Line
Count
Source
58
18.0M
        : 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*>), llvm::CallGraphNode*> const&, unsigned int)
Line
Count
Source
58
3.39M
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::StackElement::StackElement(llvm::CallGraphNode const*, llvm::mapped_iterator<std::__1::__wrap_iter<std::__1::pair<llvm::WeakTrackingVH, llvm::CallGraphNode*> const*>, llvm::CallGraphNode const* (*)(std::__1::pair<llvm::WeakTrackingVH, llvm::CallGraphNode*>), llvm::CallGraphNode const*> const&, unsigned int)
Line
Count
Source
58
19
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::StackElement::StackElement(llvm::ValueInfo, llvm::mapped_iterator<std::__1::__wrap_iter<std::__1::pair<llvm::ValueInfo, llvm::CalleeInfo>*>, llvm::ValueInfo (*)(std::__1::pair<llvm::ValueInfo, llvm::CalleeInfo>&), llvm::ValueInfo> const&, unsigned int)
Line
Count
Source
58
6
        : 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
588k
        : 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
    bool operator==(const StackElement &Other) const {
61
      return Node == Other.Node &&
62
             NextChild == Other.NextChild &&
63
             MinVisited == Other.MinVisited;
64
    }
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
public:
94
3.34M
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
3.34M
    DFSVisitOne(entryN);
96
3.34M
    GetNextSCC();
97
3.34M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::scc_iterator(llvm::MachineBasicBlock*)
Line
Count
Source
94
2.23k
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
2.23k
    DFSVisitOne(entryN);
96
2.23k
    GetNextSCC();
97
2.23k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::scc_iterator(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
94
629
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
629
    DFSVisitOne(entryN);
96
629
    GetNextSCC();
97
629
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::scc_iterator(llvm::BasicBlock const*)
Line
Count
Source
94
2.65M
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
2.65M
    DFSVisitOne(entryN);
96
2.65M
    GetNextSCC();
97
2.65M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::scc_iterator(llvm::CallGraphNode*)
Line
Count
Source
94
92.3k
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
92.3k
    DFSVisitOne(entryN);
96
92.3k
    GetNextSCC();
97
92.3k
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::scc_iterator(llvm::CallGraphNode const*)
Line
Count
Source
94
3
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
3
    DFSVisitOne(entryN);
96
3
    GetNextSCC();
97
3
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::scc_iterator(llvm::ValueInfo)
Line
Count
Source
94
1
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
1
    DFSVisitOne(entryN);
96
1
    GetNextSCC();
97
1
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::scc_iterator((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
94
588k
  scc_iterator(NodeRef entryN) : visitNum(0) {
95
588k
    DFSVisitOne(entryN);
96
588k
    GetNextSCC();
97
588k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::scc_iterator(llvm::BasicBlock*)
98
99
  /// End is when the DFS stack is empty.
100
  scc_iterator() = default;
101
102
  /// Direct loop termination test which is more efficient than
103
  /// comparison with \c end().
104
22.5M
  bool isAtEnd() const {
105
22.5M
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
22.5M
    return CurrentSCC.empty();
107
22.5M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::isAtEnd() const
Line
Count
Source
104
4.58k
  bool isAtEnd() const {
105
4.58k
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
4.58k
    return CurrentSCC.empty();
107
4.58k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::isAtEnd() const
Line
Count
Source
104
15.8k
  bool isAtEnd() const {
105
15.8k
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
15.8k
    return CurrentSCC.empty();
107
15.8k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::isAtEnd() const
Line
Count
Source
104
17.0M
  bool isAtEnd() const {
105
17.0M
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
17.0M
    return CurrentSCC.empty();
107
17.0M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::isAtEnd() const
Line
Count
Source
104
4.30M
  bool isAtEnd() const {
105
4.30M
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
4.30M
    return CurrentSCC.empty();
107
4.30M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::isAtEnd() const
Line
Count
Source
104
20
  bool isAtEnd() const {
105
20
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
20
    return CurrentSCC.empty();
107
20
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::isAtEnd() const
Line
Count
Source
104
6
  bool isAtEnd() const {
105
6
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
6
    return CurrentSCC.empty();
107
6
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::isAtEnd() const
Line
Count
Source
104
1.17M
  bool isAtEnd() const {
105
1.17M
    assert(!CurrentSCC.empty() || VisitStack.empty());
106
1.17M
    return CurrentSCC.empty();
107
1.17M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::isAtEnd() const
108
109
  bool operator==(const scc_iterator &x) const {
110
    return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
111
  }
112
113
18.4M
  scc_iterator &operator++() {
114
18.4M
    GetNextSCC();
115
18.4M
    return *this;
116
18.4M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator++()
Line
Count
Source
113
2.34k
  scc_iterator &operator++() {
114
2.34k
    GetNextSCC();
115
2.34k
    return *this;
116
2.34k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator++()
Line
Count
Source
113
15.2k
  scc_iterator &operator++() {
114
15.2k
    GetNextSCC();
115
15.2k
    return *this;
116
15.2k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator++()
Line
Count
Source
113
14.4M
  scc_iterator &operator++() {
114
14.4M
    GetNextSCC();
115
14.4M
    return *this;
116
14.4M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator++()
Line
Count
Source
113
3.39M
  scc_iterator &operator++() {
114
3.39M
    GetNextSCC();
115
3.39M
    return *this;
116
3.39M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::operator++()
Line
Count
Source
113
17
  scc_iterator &operator++() {
114
17
    GetNextSCC();
115
17
    return *this;
116
17
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::operator++()
Line
Count
Source
113
5
  scc_iterator &operator++() {
114
5
    GetNextSCC();
115
5
    return *this;
116
5
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator++()
Line
Count
Source
113
588k
  scc_iterator &operator++() {
114
588k
    GetNextSCC();
115
588k
    return *this;
116
588k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator++()
117
118
18.8M
  reference operator*() const {
119
18.8M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
18.8M
    return CurrentSCC;
121
18.8M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator*() const
Line
Count
Source
118
2.34k
  reference operator*() const {
119
2.34k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
2.34k
    return CurrentSCC;
121
2.34k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator*() const
Line
Count
Source
118
16.0k
  reference operator*() const {
119
16.0k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
16.0k
    return CurrentSCC;
121
16.0k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator*() const
Line
Count
Source
118
14.4M
  reference operator*() const {
119
14.4M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
14.4M
    return CurrentSCC;
121
14.4M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator*() const
Line
Count
Source
118
3.84M
  reference operator*() const {
119
3.84M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
3.84M
    return CurrentSCC;
121
3.84M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::operator*() const
Line
Count
Source
118
17
  reference operator*() const {
119
17
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
17
    return CurrentSCC;
121
17
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::operator*() const
Line
Count
Source
118
15
  reference operator*() const {
119
15
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
15
    return CurrentSCC;
121
15
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator*() const
Line
Count
Source
118
588k
  reference operator*() const {
119
588k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
120
588k
    return CurrentSCC;
121
588k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator*() const
122
123
  /// Test if the current SCC has a loop.
124
  ///
125
  /// If the SCC has more than one node, this is trivially true.  If not, it may
126
  /// still contain a loop if the node has an edge back to itself.
127
  bool hasLoop() const;
128
129
  /// This informs the \c scc_iterator that the specified \c Old node
130
  /// has been deleted, and \c New is to be used in its place.
131
1.69k
  void ReplaceNode(NodeRef Old, NodeRef New) {
132
1.69k
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
133
1.69k
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
134
1.69k
    nodeVisitNumbers.erase(Old);
135
1.69k
  }
136
};
137
138
template <class GraphT, class GT>
139
22.0M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
22.0M
  ++visitNum;
141
22.0M
  nodeVisitNumbers[N] = visitNum;
142
22.0M
  SCCNodeStack.push_back(N);
143
22.0M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
22.0M
#if 0 // Enable if needed when debugging.
145
22.0M
  dbgs() << "TarjanSCC: Node " << N <<
146
22.0M
        " : visitNum = " << visitNum << "\n";
147
22.0M
#endif
148
22.0M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitOne(llvm::MachineBasicBlock*)
Line
Count
Source
139
2.36k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
2.36k
  ++visitNum;
141
2.36k
  nodeVisitNumbers[N] = visitNum;
142
2.36k
  SCCNodeStack.push_back(N);
143
2.36k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
2.36k
#if 0 // Enable if needed when debugging.
145
2.36k
  dbgs() << "TarjanSCC: Node " << N <<
146
2.36k
        " : visitNum = " << visitNum << "\n";
147
2.36k
#endif
148
2.36k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitOne(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
139
25.3k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
25.3k
  ++visitNum;
141
25.3k
  nodeVisitNumbers[N] = visitNum;
142
25.3k
  SCCNodeStack.push_back(N);
143
25.3k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
25.3k
#if 0 // Enable if needed when debugging.
145
25.3k
  dbgs() << "TarjanSCC: Node " << N <<
146
25.3k
        " : visitNum = " << visitNum << "\n";
147
25.3k
#endif
148
25.3k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitOne(llvm::BasicBlock const*)
Line
Count
Source
139
18.0M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
18.0M
  ++visitNum;
141
18.0M
  nodeVisitNumbers[N] = visitNum;
142
18.0M
  SCCNodeStack.push_back(N);
143
18.0M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
18.0M
#if 0 // Enable if needed when debugging.
145
18.0M
  dbgs() << "TarjanSCC: Node " << N <<
146
18.0M
        " : visitNum = " << visitNum << "\n";
147
18.0M
#endif
148
18.0M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitOne(llvm::CallGraphNode*)
Line
Count
Source
139
3.39M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
3.39M
  ++visitNum;
141
3.39M
  nodeVisitNumbers[N] = visitNum;
142
3.39M
  SCCNodeStack.push_back(N);
143
3.39M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
3.39M
#if 0 // Enable if needed when debugging.
145
3.39M
  dbgs() << "TarjanSCC: Node " << N <<
146
3.39M
        " : visitNum = " << visitNum << "\n";
147
3.39M
#endif
148
3.39M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::DFSVisitOne(llvm::CallGraphNode const*)
Line
Count
Source
139
19
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
19
  ++visitNum;
141
19
  nodeVisitNumbers[N] = visitNum;
142
19
  SCCNodeStack.push_back(N);
143
19
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
19
#if 0 // Enable if needed when debugging.
145
19
  dbgs() << "TarjanSCC: Node " << N <<
146
19
        " : visitNum = " << visitNum << "\n";
147
19
#endif
148
19
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::DFSVisitOne(llvm::ValueInfo)
Line
Count
Source
139
6
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
6
  ++visitNum;
141
6
  nodeVisitNumbers[N] = visitNum;
142
6
  SCCNodeStack.push_back(N);
143
6
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
6
#if 0 // Enable if needed when debugging.
145
6
  dbgs() << "TarjanSCC: Node " << N <<
146
6
        " : visitNum = " << visitNum << "\n";
147
6
#endif
148
6
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitOne((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
139
588k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
140
588k
  ++visitNum;
141
588k
  nodeVisitNumbers[N] = visitNum;
142
588k
  SCCNodeStack.push_back(N);
143
588k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
144
588k
#if 0 // Enable if needed when debugging.
145
588k
  dbgs() << "TarjanSCC: Node " << N <<
146
588k
        " : visitNum = " << visitNum << "\n";
147
588k
#endif
148
588k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitOne(llvm::BasicBlock*)
149
150
template <class GraphT, class GT>
151
22.0M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
22.0M
  assert(!VisitStack.empty());
153
59.6M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
37.5M
    // TOS has at least one more child so continue DFS
155
37.5M
    NodeRef childN = *VisitStack.back().NextChild++;
156
37.5M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
37.5M
        nodeVisitNumbers.find(childN);
158
37.5M
    if (Visited == nodeVisitNumbers.end()) {
159
18.7M
      // this node has never been seen.
160
18.7M
      DFSVisitOne(childN);
161
18.7M
      continue;
162
18.7M
    }
163
18.8M
164
18.8M
    unsigned childNum = Visited->second;
165
18.8M
    if (VisitStack.back().MinVisited > childNum)
166
1.48M
      VisitStack.back().MinVisited = childNum;
167
18.8M
  }
168
22.0M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitChildren()
Line
Count
Source
151
2.36k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
2.36k
  assert(!VisitStack.empty());
153
2.54k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
186
    // TOS has at least one more child so continue DFS
155
186
    NodeRef childN = *VisitStack.back().NextChild++;
156
186
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
186
        nodeVisitNumbers.find(childN);
158
186
    if (Visited == nodeVisitNumbers.end()) {
159
125
      // this node has never been seen.
160
125
      DFSVisitOne(childN);
161
125
      continue;
162
125
    }
163
61
164
61
    unsigned childNum = Visited->second;
165
61
    if (VisitStack.back().MinVisited > childNum)
166
4
      VisitStack.back().MinVisited = childNum;
167
61
  }
168
2.36k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitChildren()
Line
Count
Source
151
25.3k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
25.3k
  assert(!VisitStack.empty());
153
67.1k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
41.7k
    // TOS has at least one more child so continue DFS
155
41.7k
    NodeRef childN = *VisitStack.back().NextChild++;
156
41.7k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
41.7k
        nodeVisitNumbers.find(childN);
158
41.7k
    if (Visited == nodeVisitNumbers.end()) {
159
24.7k
      // this node has never been seen.
160
24.7k
      DFSVisitOne(childN);
161
24.7k
      continue;
162
24.7k
    }
163
16.9k
164
16.9k
    unsigned childNum = Visited->second;
165
16.9k
    if (VisitStack.back().MinVisited > childNum)
166
3.40k
      VisitStack.back().MinVisited = childNum;
167
16.9k
  }
168
25.3k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitChildren()
Line
Count
Source
151
18.0M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
18.0M
  assert(!VisitStack.empty());
153
41.9M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
23.8M
    // TOS has at least one more child so continue DFS
155
23.8M
    NodeRef childN = *VisitStack.back().NextChild++;
156
23.8M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
23.8M
        nodeVisitNumbers.find(childN);
158
23.8M
    if (Visited == nodeVisitNumbers.end()) {
159
15.3M
      // this node has never been seen.
160
15.3M
      DFSVisitOne(childN);
161
15.3M
      continue;
162
15.3M
    }
163
8.49M
164
8.49M
    unsigned childNum = Visited->second;
165
8.49M
    if (VisitStack.back().MinVisited > childNum)
166
1.48M
      VisitStack.back().MinVisited = childNum;
167
8.49M
  }
168
18.0M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitChildren()
Line
Count
Source
151
3.39M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
3.39M
  assert(!VisitStack.empty());
153
17.0M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
13.6M
    // TOS has at least one more child so continue DFS
155
13.6M
    NodeRef childN = *VisitStack.back().NextChild++;
156
13.6M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
13.6M
        nodeVisitNumbers.find(childN);
158
13.6M
    if (Visited == nodeVisitNumbers.end()) {
159
3.30M
      // this node has never been seen.
160
3.30M
      DFSVisitOne(childN);
161
3.30M
      continue;
162
3.30M
    }
163
10.3M
164
10.3M
    unsigned childNum = Visited->second;
165
10.3M
    if (VisitStack.back().MinVisited > childNum)
166
1.78k
      VisitStack.back().MinVisited = childNum;
167
10.3M
  }
168
3.39M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::DFSVisitChildren()
Line
Count
Source
151
19
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
19
  assert(!VisitStack.empty());
153
41
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
22
    // TOS has at least one more child so continue DFS
155
22
    NodeRef childN = *VisitStack.back().NextChild++;
156
22
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
22
        nodeVisitNumbers.find(childN);
158
22
    if (Visited == nodeVisitNumbers.end()) {
159
16
      // this node has never been seen.
160
16
      DFSVisitOne(childN);
161
16
      continue;
162
16
    }
163
6
164
6
    unsigned childNum = Visited->second;
165
6
    if (VisitStack.back().MinVisited > childNum)
166
2
      VisitStack.back().MinVisited = childNum;
167
6
  }
168
19
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::DFSVisitChildren()
Line
Count
Source
151
6
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
6
  assert(!VisitStack.empty());
153
13
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
7
    // TOS has at least one more child so continue DFS
155
7
    NodeRef childN = *VisitStack.back().NextChild++;
156
7
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
7
        nodeVisitNumbers.find(childN);
158
7
    if (Visited == nodeVisitNumbers.end()) {
159
5
      // this node has never been seen.
160
5
      DFSVisitOne(childN);
161
5
      continue;
162
5
    }
163
2
164
2
    unsigned childNum = Visited->second;
165
2
    if (VisitStack.back().MinVisited > childNum)
166
1
      VisitStack.back().MinVisited = childNum;
167
2
  }
168
6
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitChildren()
Line
Count
Source
151
588k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
152
588k
  assert(!VisitStack.empty());
153
591k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
154
2.35k
    // TOS has at least one more child so continue DFS
155
2.35k
    NodeRef childN = *VisitStack.back().NextChild++;
156
2.35k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
157
2.35k
        nodeVisitNumbers.find(childN);
158
2.35k
    if (Visited == nodeVisitNumbers.end()) {
159
636
      // this node has never been seen.
160
636
      DFSVisitOne(childN);
161
636
      continue;
162
636
    }
163
1.71k
164
1.71k
    unsigned childNum = Visited->second;
165
1.71k
    if (VisitStack.back().MinVisited > childNum)
166
27
      VisitStack.back().MinVisited = childNum;
167
1.71k
  }
168
588k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitChildren()
169
170
21.7M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
21.7M
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
25.4M
  while (!VisitStack.empty()) {
173
22.0M
    DFSVisitChildren();
174
22.0M
175
22.0M
    // Pop the leaf on top of the VisitStack.
176
22.0M
    NodeRef visitingN = VisitStack.back().Node;
177
22.0M
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
22.0M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
22.0M
    VisitStack.pop_back();
180
22.0M
181
22.0M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
22.0M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum18.7M
)
183
2.26M
      VisitStack.back().MinVisited = minVisitNum;
184
22.0M
185
22.0M
#if 0 // Enable if needed when debugging.
186
22.0M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
22.0M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
22.0M
          nodeVisitNumbers[visitingN] << "\n";
189
22.0M
#endif
190
22.0M
191
22.0M
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
3.64M
      continue;
193
18.4M
194
18.4M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
18.4M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
18.4M
    // reset their minVisit values, and return (this suspends
197
18.4M
    // the DFS traversal till the next ++).
198
22.0M
    
do 18.4M
{
199
22.0M
      CurrentSCC.push_back(SCCNodeStack.back());
200
22.0M
      SCCNodeStack.pop_back();
201
22.0M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
22.0M
    } while (CurrentSCC.back() != visitingN);
203
18.4M
    return;
204
18.4M
  }
205
21.7M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::GetNextSCC()
Line
Count
Source
170
4.58k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
4.58k
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
4.60k
  while (!VisitStack.empty()) {
173
2.36k
    DFSVisitChildren();
174
2.36k
175
2.36k
    // Pop the leaf on top of the VisitStack.
176
2.36k
    NodeRef visitingN = VisitStack.back().Node;
177
2.36k
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
2.36k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
2.36k
    VisitStack.pop_back();
180
2.36k
181
2.36k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
2.36k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum125
)
183
16
      VisitStack.back().MinVisited = minVisitNum;
184
2.36k
185
2.36k
#if 0 // Enable if needed when debugging.
186
2.36k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
2.36k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
2.36k
          nodeVisitNumbers[visitingN] << "\n";
189
2.36k
#endif
190
2.36k
191
2.36k
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
20
      continue;
193
2.34k
194
2.34k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
2.34k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
2.34k
    // reset their minVisit values, and return (this suspends
197
2.34k
    // the DFS traversal till the next ++).
198
2.36k
    
do 2.34k
{
199
2.36k
      CurrentSCC.push_back(SCCNodeStack.back());
200
2.36k
      SCCNodeStack.pop_back();
201
2.36k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
2.36k
    } while (CurrentSCC.back() != visitingN);
203
2.34k
    return;
204
2.34k
  }
205
4.58k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::GetNextSCC()
Line
Count
Source
170
15.8k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
15.8k
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
26.0k
  while (!VisitStack.empty()) {
173
25.3k
    DFSVisitChildren();
174
25.3k
175
25.3k
    // Pop the leaf on top of the VisitStack.
176
25.3k
    NodeRef visitingN = VisitStack.back().Node;
177
25.3k
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
25.3k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
25.3k
    VisitStack.pop_back();
180
25.3k
181
25.3k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
25.3k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum24.7k
)
183
6.97k
      VisitStack.back().MinVisited = minVisitNum;
184
25.3k
185
25.3k
#if 0 // Enable if needed when debugging.
186
25.3k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
25.3k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
25.3k
          nodeVisitNumbers[visitingN] << "\n";
189
25.3k
#endif
190
25.3k
191
25.3k
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
10.1k
      continue;
193
15.2k
194
15.2k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
15.2k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
15.2k
    // reset their minVisit values, and return (this suspends
197
15.2k
    // the DFS traversal till the next ++).
198
25.3k
    
do 15.2k
{
199
25.3k
      CurrentSCC.push_back(SCCNodeStack.back());
200
25.3k
      SCCNodeStack.pop_back();
201
25.3k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
25.3k
    } while (CurrentSCC.back() != visitingN);
203
15.2k
    return;
204
15.2k
  }
205
15.8k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::GetNextSCC()
Line
Count
Source
170
17.0M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
17.0M
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
20.7M
  while (!VisitStack.empty()) {
173
18.0M
    DFSVisitChildren();
174
18.0M
175
18.0M
    // Pop the leaf on top of the VisitStack.
176
18.0M
    NodeRef visitingN = VisitStack.back().Node;
177
18.0M
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
18.0M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
18.0M
    VisitStack.pop_back();
180
18.0M
181
18.0M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
18.0M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum15.3M
)
183
2.25M
      VisitStack.back().MinVisited = minVisitNum;
184
18.0M
185
18.0M
#if 0 // Enable if needed when debugging.
186
18.0M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
18.0M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
18.0M
          nodeVisitNumbers[visitingN] << "\n";
189
18.0M
#endif
190
18.0M
191
18.0M
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
3.63M
      continue;
193
14.4M
194
14.4M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
14.4M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
14.4M
    // reset their minVisit values, and return (this suspends
197
14.4M
    // the DFS traversal till the next ++).
198
18.0M
    
do 14.4M
{
199
18.0M
      CurrentSCC.push_back(SCCNodeStack.back());
200
18.0M
      SCCNodeStack.pop_back();
201
18.0M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
18.0M
    } while (CurrentSCC.back() != visitingN);
203
14.4M
    return;
204
14.4M
  }
205
17.0M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::GetNextSCC()
Line
Count
Source
170
3.48M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
3.48M
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
3.48M
  while (!VisitStack.empty()) {
173
3.39M
    DFSVisitChildren();
174
3.39M
175
3.39M
    // Pop the leaf on top of the VisitStack.
176
3.39M
    NodeRef visitingN = VisitStack.back().Node;
177
3.39M
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
3.39M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
3.39M
    VisitStack.pop_back();
180
3.39M
181
3.39M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
3.39M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum3.30M
)
183
1.62k
      VisitStack.back().MinVisited = minVisitNum;
184
3.39M
185
3.39M
#if 0 // Enable if needed when debugging.
186
3.39M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
3.39M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
3.39M
          nodeVisitNumbers[visitingN] << "\n";
189
3.39M
#endif
190
3.39M
191
3.39M
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
3.21k
      continue;
193
3.39M
194
3.39M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
3.39M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
3.39M
    // reset their minVisit values, and return (this suspends
197
3.39M
    // the DFS traversal till the next ++).
198
3.39M
    
do 3.39M
{
199
3.39M
      CurrentSCC.push_back(SCCNodeStack.back());
200
3.39M
      SCCNodeStack.pop_back();
201
3.39M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
3.39M
    } while (CurrentSCC.back() != visitingN);
203
3.39M
    return;
204
3.39M
  }
205
3.48M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::GetNextSCC()
Line
Count
Source
170
20
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
20
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
22
  while (!VisitStack.empty()) {
173
19
    DFSVisitChildren();
174
19
175
19
    // Pop the leaf on top of the VisitStack.
176
19
    NodeRef visitingN = VisitStack.back().Node;
177
19
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
19
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
19
    VisitStack.pop_back();
180
19
181
19
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
19
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum16
)
183
0
      VisitStack.back().MinVisited = minVisitNum;
184
19
185
19
#if 0 // Enable if needed when debugging.
186
19
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
19
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
19
          nodeVisitNumbers[visitingN] << "\n";
189
19
#endif
190
19
191
19
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
2
      continue;
193
17
194
17
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
17
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
17
    // reset their minVisit values, and return (this suspends
197
17
    // the DFS traversal till the next ++).
198
19
    
do 17
{
199
19
      CurrentSCC.push_back(SCCNodeStack.back());
200
19
      SCCNodeStack.pop_back();
201
19
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
19
    } while (CurrentSCC.back() != visitingN);
203
17
    return;
204
17
  }
205
20
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::GetNextSCC()
Line
Count
Source
170
6
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
6
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
7
  while (!VisitStack.empty()) {
173
6
    DFSVisitChildren();
174
6
175
6
    // Pop the leaf on top of the VisitStack.
176
6
    NodeRef visitingN = VisitStack.back().Node;
177
6
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
6
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
6
    VisitStack.pop_back();
180
6
181
6
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
6
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum5
)
183
0
      VisitStack.back().MinVisited = minVisitNum;
184
6
185
6
#if 0 // Enable if needed when debugging.
186
6
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
6
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
6
          nodeVisitNumbers[visitingN] << "\n";
189
6
#endif
190
6
191
6
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
1
      continue;
193
5
194
5
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
5
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
5
    // reset their minVisit values, and return (this suspends
197
5
    // the DFS traversal till the next ++).
198
6
    
do 5
{
199
6
      CurrentSCC.push_back(SCCNodeStack.back());
200
6
      SCCNodeStack.pop_back();
201
6
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
6
    } while (CurrentSCC.back() != visitingN);
203
5
    return;
204
5
  }
205
6
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::GetNextSCC()
Line
Count
Source
170
1.17M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
171
1.17M
  CurrentSCC.clear(); // Prepare to compute the next SCC
172
1.17M
  while (!VisitStack.empty()) {
173
588k
    DFSVisitChildren();
174
588k
175
588k
    // Pop the leaf on top of the VisitStack.
176
588k
    NodeRef visitingN = VisitStack.back().Node;
177
588k
    unsigned minVisitNum = VisitStack.back().MinVisited;
178
588k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
179
588k
    VisitStack.pop_back();
180
588k
181
588k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
182
588k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum636
)
183
2
      VisitStack.back().MinVisited = minVisitNum;
184
588k
185
588k
#if 0 // Enable if needed when debugging.
186
588k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
187
588k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
188
588k
          nodeVisitNumbers[visitingN] << "\n";
189
588k
#endif
190
588k
191
588k
    if (minVisitNum != nodeVisitNumbers[visitingN])
192
29
      continue;
193
588k
194
588k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
195
588k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
196
588k
    // reset their minVisit values, and return (this suspends
197
588k
    // the DFS traversal till the next ++).
198
588k
    
do 588k
{
199
588k
      CurrentSCC.push_back(SCCNodeStack.back());
200
588k
      SCCNodeStack.pop_back();
201
588k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
202
588k
    } while (CurrentSCC.back() != visitingN);
203
588k
    return;
204
588k
  }
205
1.17M
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::GetNextSCC()
206
207
template <class GraphT, class GT>
208
6
bool scc_iterator<GraphT, GT>::hasLoop() const {
209
6
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
210
6
    if (CurrentSCC.size() > 1)
211
2
      return true;
212
4
    NodeRef N = CurrentSCC.front();
213
9
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
214
5
         ++CI)
215
5
      if (*CI == N)
216
0
        return true;
217
4
    return false;
218
4
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::hasLoop() const
Line
Count
Source
208
6
bool scc_iterator<GraphT, GT>::hasLoop() const {
209
6
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
210
6
    if (CurrentSCC.size() > 1)
211
2
      return true;
212
4
    NodeRef N = CurrentSCC.front();
213
9
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
214
5
         ++CI)
215
5
      if (*CI == N)
216
0
        return true;
217
4
    return false;
218
4
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::hasLoop() const
Unexecuted instantiation: llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::hasLoop() const
219
220
/// Construct the begin iterator for a deduced graph type T, starting from its
221
/// entry node.
222
3.31M
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
3.31M
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
3.31M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> > llvm::scc_begin<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
222
2.23k
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
2.23k
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
2.23k
}
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
222
629
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
629
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
629
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> > llvm::scc_begin<llvm::Function const*>(llvm::Function const* const&)
Line
Count
Source
222
2.65M
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
2.65M
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
2.65M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> > llvm::scc_begin<llvm::CallGraph*>(llvm::CallGraph* const&)
Line
Count
Source
222
65.6k
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
65.6k
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
65.6k
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> > llvm::scc_begin<llvm::CallGraph const*>(llvm::CallGraph const* const&)
Line
Count
Source
222
3
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
3
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
3
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> > llvm::scc_begin<llvm::ModuleSummaryIndex*>(llvm::ModuleSummaryIndex* const&)
Line
Count
Source
222
1
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
1
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
1
}
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
222
588k
template <class T> scc_iterator<T> scc_begin(const T &G) {
223
588k
  return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
224
588k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> > llvm::scc_begin<llvm::Function*>(llvm::Function* const&)
225
226
/// Construct the begin iterator for a graph type T, starting from the specified
227
/// node.
228
template <class T, class U = GraphTraits<T>>
229
26.6k
scc_iterator<T, U> scc_begin(typename U::NodeRef N) {
230
26.6k
  return scc_iterator<T>(N);
231
26.6k
}
232
233
  /// Construct the end iterator for a deduced graph type T.
234
template <class T> scc_iterator<T> scc_end(const T &G) {
235
  return scc_iterator<T>();
236
}
237
238
239
} // end namespace llvm
240
241
#endif // LLVM_ADT_SCCITERATOR_H