Coverage Report

Created: 2018-12-14 11:24

/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.5M
        : 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.42k
        : 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.5k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::StackElement::StackElement(llvm::BasicBlock const*, llvm::SuccIterator<llvm::Instruction const, llvm::BasicBlock const> const&, unsigned int)
Line
Count
Source
58
18.4M
        : 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.45M
        : 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
15
        : 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
605k
        : Node(Node), NextChild(Child), MinVisited(Min) {}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::StackElement::StackElement(llvm::BasicBlock*, llvm::SuccIterator<llvm::Instruction, 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
3.45M
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
3.45M
    DFSVisitOne(entryN);
95
3.45M
    GetNextSCC();
96
3.45M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::scc_iterator(llvm::MachineBasicBlock*)
Line
Count
Source
93
2.29k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
2.29k
    DFSVisitOne(entryN);
95
2.29k
    GetNextSCC();
96
2.29k
  }
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
656
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
656
    DFSVisitOne(entryN);
95
656
    GetNextSCC();
96
656
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::scc_iterator(llvm::BasicBlock const*)
Line
Count
Source
93
2.75M
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
2.75M
    DFSVisitOne(entryN);
95
2.75M
    GetNextSCC();
96
2.75M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::scc_iterator(llvm::CallGraphNode*)
Line
Count
Source
93
92.2k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
92.2k
    DFSVisitOne(entryN);
95
92.2k
    GetNextSCC();
96
92.2k
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::scc_iterator(llvm::CallGraphNode const*)
Line
Count
Source
93
3
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
3
    DFSVisitOne(entryN);
95
3
    GetNextSCC();
96
3
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::scc_iterator(llvm::ValueInfo)
Line
Count
Source
93
4
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
4
    DFSVisitOne(entryN);
95
4
    GetNextSCC();
96
4
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::scc_iterator((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
93
604k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
604k
    DFSVisitOne(entryN);
95
604k
    GetNextSCC();
96
604k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::scc_iterator(llvm::BasicBlock*)
97
98
  /// End is when the DFS stack is empty.
99
  scc_iterator() = default;
100
101
public:
102
3.45M
  static scc_iterator begin(const GraphT &G) {
103
3.45M
    return scc_iterator(GT::getEntryNode(G));
104
3.45M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::begin(llvm::MachineFunction* const&)
Line
Count
Source
102
2.29k
  static scc_iterator begin(const GraphT &G) {
103
2.29k
    return scc_iterator(GT::getEntryNode(G));
104
2.29k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::begin(llvm::bfi_detail::IrreducibleGraph const&)
Line
Count
Source
102
656
  static scc_iterator begin(const GraphT &G) {
103
656
    return scc_iterator(GT::getEntryNode(G));
104
656
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::begin(llvm::Function const* const&)
Line
Count
Source
102
2.75M
  static scc_iterator begin(const GraphT &G) {
103
2.75M
    return scc_iterator(GT::getEntryNode(G));
104
2.75M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::begin(llvm::CallGraph* const&)
Line
Count
Source
102
92.2k
  static scc_iterator begin(const GraphT &G) {
103
92.2k
    return scc_iterator(GT::getEntryNode(G));
104
92.2k
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::begin(llvm::CallGraph const* const&)
Line
Count
Source
102
3
  static scc_iterator begin(const GraphT &G) {
103
3
    return scc_iterator(GT::getEntryNode(G));
104
3
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::begin(llvm::ModuleSummaryIndex* const&)
Line
Count
Source
102
4
  static scc_iterator begin(const GraphT &G) {
103
4
    return scc_iterator(GT::getEntryNode(G));
104
4
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::begin((anonymous namespace)::ArgumentGraph* const&)
Line
Count
Source
102
604k
  static scc_iterator begin(const GraphT &G) {
103
604k
    return scc_iterator(GT::getEntryNode(G));
104
604k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::begin(llvm::Function* const&)
105
  static scc_iterator end(const GraphT &) { return scc_iterator(); }
106
107
  /// Direct loop termination test which is more efficient than
108
  /// comparison with \c end().
109
22.2M
  bool isAtEnd() const {
110
22.2M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
22.2M
    return CurrentSCC.empty();
112
22.2M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::isAtEnd() const
Line
Count
Source
109
4.70k
  bool isAtEnd() const {
110
4.70k
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
4.70k
    return CurrentSCC.empty();
112
4.70k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::isAtEnd() const
Line
Count
Source
109
15.7k
  bool isAtEnd() const {
110
15.7k
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
15.7k
    return CurrentSCC.empty();
112
15.7k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::isAtEnd() const
Line
Count
Source
109
17.4M
  bool isAtEnd() const {
110
17.4M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
17.4M
    return CurrentSCC.empty();
112
17.4M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::isAtEnd() const
Line
Count
Source
109
3.54M
  bool isAtEnd() const {
110
3.54M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
3.54M
    return CurrentSCC.empty();
112
3.54M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::isAtEnd() const
Line
Count
Source
109
20
  bool isAtEnd() const {
110
20
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
20
    return CurrentSCC.empty();
112
20
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::isAtEnd() const
Line
Count
Source
109
18
  bool isAtEnd() const {
110
18
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
18
    return CurrentSCC.empty();
112
18
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::isAtEnd() const
Line
Count
Source
109
1.20M
  bool isAtEnd() const {
110
1.20M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
1.20M
    return CurrentSCC.empty();
112
1.20M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::isAtEnd() const
113
114
  bool operator==(const scc_iterator &x) const {
115
    return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
116
  }
117
118
18.7M
  scc_iterator &operator++() {
119
18.7M
    GetNextSCC();
120
18.7M
    return *this;
121
18.7M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator++()
Line
Count
Source
118
2.40k
  scc_iterator &operator++() {
119
2.40k
    GetNextSCC();
120
2.40k
    return *this;
121
2.40k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator++()
Line
Count
Source
118
15.1k
  scc_iterator &operator++() {
119
15.1k
    GetNextSCC();
120
15.1k
    return *this;
121
15.1k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator++()
Line
Count
Source
118
14.6M
  scc_iterator &operator++() {
119
14.6M
    GetNextSCC();
120
14.6M
    return *this;
121
14.6M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator++()
Line
Count
Source
118
3.44M
  scc_iterator &operator++() {
119
3.44M
    GetNextSCC();
120
3.44M
    return *this;
121
3.44M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::operator++()
Line
Count
Source
118
17
  scc_iterator &operator++() {
119
17
    GetNextSCC();
120
17
    return *this;
121
17
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::operator++()
Line
Count
Source
118
14
  scc_iterator &operator++() {
119
14
    GetNextSCC();
120
14
    return *this;
121
14
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator++()
Line
Count
Source
118
605k
  scc_iterator &operator++() {
119
605k
    GetNextSCC();
120
605k
    return *this;
121
605k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator++()
122
123
19.2M
  reference operator*() const {
124
19.2M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
19.2M
    return CurrentSCC;
126
19.2M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator*() const
Line
Count
Source
123
2.40k
  reference operator*() const {
124
2.40k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
2.40k
    return CurrentSCC;
126
2.40k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator*() const
Line
Count
Source
123
15.9k
  reference operator*() const {
124
15.9k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
15.9k
    return CurrentSCC;
126
15.9k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator*() const
Line
Count
Source
123
14.6M
  reference operator*() const {
124
14.6M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
14.6M
    return CurrentSCC;
126
14.6M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator*() const
Line
Count
Source
123
3.90M
  reference operator*() const {
124
3.90M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
3.90M
    return CurrentSCC;
126
3.90M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::operator*() const
Line
Count
Source
123
17
  reference operator*() const {
124
17
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
17
    return CurrentSCC;
126
17
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::operator*() const
Line
Count
Source
123
24
  reference operator*() const {
124
24
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
24
    return CurrentSCC;
126
24
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator*() const
Line
Count
Source
123
605k
  reference operator*() const {
124
605k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
605k
    return CurrentSCC;
126
605k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator*() const
127
128
  /// 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
1.83k
  void ReplaceNode(NodeRef Old, NodeRef New) {
137
1.83k
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
138
1.83k
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
139
1.83k
    nodeVisitNumbers.erase(Old);
140
1.83k
  }
141
};
142
143
template <class GraphT, class GT>
144
22.5M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
22.5M
  ++visitNum;
146
22.5M
  nodeVisitNumbers[N] = visitNum;
147
22.5M
  SCCNodeStack.push_back(N);
148
22.5M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
22.5M
#if 0 // Enable if needed when debugging.
150
22.5M
  dbgs() << "TarjanSCC: Node " << N <<
151
22.5M
        " : visitNum = " << visitNum << "\n";
152
22.5M
#endif
153
22.5M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitOne(llvm::MachineBasicBlock*)
Line
Count
Source
144
2.42k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
2.42k
  ++visitNum;
146
2.42k
  nodeVisitNumbers[N] = visitNum;
147
2.42k
  SCCNodeStack.push_back(N);
148
2.42k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
2.42k
#if 0 // Enable if needed when debugging.
150
2.42k
  dbgs() << "TarjanSCC: Node " << N <<
151
2.42k
        " : visitNum = " << visitNum << "\n";
152
2.42k
#endif
153
2.42k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitOne(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
144
25.5k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
25.5k
  ++visitNum;
146
25.5k
  nodeVisitNumbers[N] = visitNum;
147
25.5k
  SCCNodeStack.push_back(N);
148
25.5k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
25.5k
#if 0 // Enable if needed when debugging.
150
25.5k
  dbgs() << "TarjanSCC: Node " << N <<
151
25.5k
        " : visitNum = " << visitNum << "\n";
152
25.5k
#endif
153
25.5k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitOne(llvm::BasicBlock const*)
Line
Count
Source
144
18.4M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
18.4M
  ++visitNum;
146
18.4M
  nodeVisitNumbers[N] = visitNum;
147
18.4M
  SCCNodeStack.push_back(N);
148
18.4M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
18.4M
#if 0 // Enable if needed when debugging.
150
18.4M
  dbgs() << "TarjanSCC: Node " << N <<
151
18.4M
        " : visitNum = " << visitNum << "\n";
152
18.4M
#endif
153
18.4M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitOne(llvm::CallGraphNode*)
Line
Count
Source
144
3.45M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
3.45M
  ++visitNum;
146
3.45M
  nodeVisitNumbers[N] = visitNum;
147
3.45M
  SCCNodeStack.push_back(N);
148
3.45M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
3.45M
#if 0 // Enable if needed when debugging.
150
3.45M
  dbgs() << "TarjanSCC: Node " << N <<
151
3.45M
        " : visitNum = " << visitNum << "\n";
152
3.45M
#endif
153
3.45M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::DFSVisitOne(llvm::CallGraphNode const*)
Line
Count
Source
144
19
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
19
  ++visitNum;
146
19
  nodeVisitNumbers[N] = visitNum;
147
19
  SCCNodeStack.push_back(N);
148
19
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
19
#if 0 // Enable if needed when debugging.
150
19
  dbgs() << "TarjanSCC: Node " << N <<
151
19
        " : visitNum = " << visitNum << "\n";
152
19
#endif
153
19
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::DFSVisitOne(llvm::ValueInfo)
Line
Count
Source
144
15
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
15
  ++visitNum;
146
15
  nodeVisitNumbers[N] = visitNum;
147
15
  SCCNodeStack.push_back(N);
148
15
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
15
#if 0 // Enable if needed when debugging.
150
15
  dbgs() << "TarjanSCC: Node " << N <<
151
15
        " : visitNum = " << visitNum << "\n";
152
15
#endif
153
15
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitOne((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
144
605k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
605k
  ++visitNum;
146
605k
  nodeVisitNumbers[N] = visitNum;
147
605k
  SCCNodeStack.push_back(N);
148
605k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
605k
#if 0 // Enable if needed when debugging.
150
605k
  dbgs() << "TarjanSCC: Node " << N <<
151
605k
        " : visitNum = " << visitNum << "\n";
152
605k
#endif
153
605k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitOne(llvm::BasicBlock*)
154
155
template <class GraphT, class GT>
156
22.5M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
22.5M
  assert(!VisitStack.empty());
158
60.7M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
38.2M
    // TOS has at least one more child so continue DFS
160
38.2M
    NodeRef childN = *VisitStack.back().NextChild++;
161
38.2M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
38.2M
        nodeVisitNumbers.find(childN);
163
38.2M
    if (Visited == nodeVisitNumbers.end()) {
164
19.0M
      // this node has never been seen.
165
19.0M
      DFSVisitOne(childN);
166
19.0M
      continue;
167
19.0M
    }
168
19.1M
169
19.1M
    unsigned childNum = Visited->second;
170
19.1M
    if (VisitStack.back().MinVisited > childNum)
171
1.51M
      VisitStack.back().MinVisited = childNum;
172
19.1M
  }
173
22.5M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitChildren()
Line
Count
Source
156
2.42k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
2.42k
  assert(!VisitStack.empty());
158
2.61k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
186
    // TOS has at least one more child so continue DFS
160
186
    NodeRef childN = *VisitStack.back().NextChild++;
161
186
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
186
        nodeVisitNumbers.find(childN);
163
186
    if (Visited == nodeVisitNumbers.end()) {
164
125
      // this node has never been seen.
165
125
      DFSVisitOne(childN);
166
125
      continue;
167
125
    }
168
61
169
61
    unsigned childNum = Visited->second;
170
61
    if (VisitStack.back().MinVisited > childNum)
171
4
      VisitStack.back().MinVisited = childNum;
172
61
  }
173
2.42k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitChildren()
Line
Count
Source
156
25.5k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
25.5k
  assert(!VisitStack.empty());
158
68.1k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
42.6k
    // TOS has at least one more child so continue DFS
160
42.6k
    NodeRef childN = *VisitStack.back().NextChild++;
161
42.6k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
42.6k
        nodeVisitNumbers.find(childN);
163
42.6k
    if (Visited == nodeVisitNumbers.end()) {
164
24.9k
      // this node has never been seen.
165
24.9k
      DFSVisitOne(childN);
166
24.9k
      continue;
167
24.9k
    }
168
17.6k
169
17.6k
    unsigned childNum = Visited->second;
170
17.6k
    if (VisitStack.back().MinVisited > childNum)
171
3.54k
      VisitStack.back().MinVisited = childNum;
172
17.6k
  }
173
25.5k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitChildren()
Line
Count
Source
156
18.4M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
18.4M
  assert(!VisitStack.empty());
158
42.7M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
24.3M
    // TOS has at least one more child so continue DFS
160
24.3M
    NodeRef childN = *VisitStack.back().NextChild++;
161
24.3M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
24.3M
        nodeVisitNumbers.find(childN);
163
24.3M
    if (Visited == nodeVisitNumbers.end()) {
164
15.6M
      // this node has never been seen.
165
15.6M
      DFSVisitOne(childN);
166
15.6M
      continue;
167
15.6M
    }
168
8.64M
169
8.64M
    unsigned childNum = Visited->second;
170
8.64M
    if (VisitStack.back().MinVisited > childNum)
171
1.51M
      VisitStack.back().MinVisited = childNum;
172
8.64M
  }
173
18.4M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitChildren()
Line
Count
Source
156
3.45M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
3.45M
  assert(!VisitStack.empty());
158
17.3M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
13.8M
    // TOS has at least one more child so continue DFS
160
13.8M
    NodeRef childN = *VisitStack.back().NextChild++;
161
13.8M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
13.8M
        nodeVisitNumbers.find(childN);
163
13.8M
    if (Visited == nodeVisitNumbers.end()) {
164
3.36M
      // this node has never been seen.
165
3.36M
      DFSVisitOne(childN);
166
3.36M
      continue;
167
3.36M
    }
168
10.5M
169
10.5M
    unsigned childNum = Visited->second;
170
10.5M
    if (VisitStack.back().MinVisited > childNum)
171
1.73k
      VisitStack.back().MinVisited = childNum;
172
10.5M
  }
173
3.45M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::DFSVisitChildren()
Line
Count
Source
156
19
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
19
  assert(!VisitStack.empty());
158
41
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
22
    // TOS has at least one more child so continue DFS
160
22
    NodeRef childN = *VisitStack.back().NextChild++;
161
22
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
22
        nodeVisitNumbers.find(childN);
163
22
    if (Visited == nodeVisitNumbers.end()) {
164
16
      // this node has never been seen.
165
16
      DFSVisitOne(childN);
166
16
      continue;
167
16
    }
168
6
169
6
    unsigned childNum = Visited->second;
170
6
    if (VisitStack.back().MinVisited > childNum)
171
2
      VisitStack.back().MinVisited = childNum;
172
6
  }
173
19
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::DFSVisitChildren()
Line
Count
Source
156
15
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
15
  assert(!VisitStack.empty());
158
28
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
13
    // TOS has at least one more child so continue DFS
160
13
    NodeRef childN = *VisitStack.back().NextChild++;
161
13
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
13
        nodeVisitNumbers.find(childN);
163
13
    if (Visited == nodeVisitNumbers.end()) {
164
11
      // this node has never been seen.
165
11
      DFSVisitOne(childN);
166
11
      continue;
167
11
    }
168
2
169
2
    unsigned childNum = Visited->second;
170
2
    if (VisitStack.back().MinVisited > childNum)
171
1
      VisitStack.back().MinVisited = childNum;
172
2
  }
173
15
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitChildren()
Line
Count
Source
156
605k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
605k
  assert(!VisitStack.empty());
158
607k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
2.32k
    // TOS has at least one more child so continue DFS
160
2.32k
    NodeRef childN = *VisitStack.back().NextChild++;
161
2.32k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
2.32k
        nodeVisitNumbers.find(childN);
163
2.32k
    if (Visited == nodeVisitNumbers.end()) {
164
625
      // this node has never been seen.
165
625
      DFSVisitOne(childN);
166
625
      continue;
167
625
    }
168
1.69k
169
1.69k
    unsigned childNum = Visited->second;
170
1.69k
    if (VisitStack.back().MinVisited > childNum)
171
27
      VisitStack.back().MinVisited = childNum;
172
1.69k
  }
173
605k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitChildren()
174
175
22.2M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
22.2M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
25.9M
  while (!VisitStack.empty()) {
178
22.5M
    DFSVisitChildren();
179
22.5M
180
22.5M
    // Pop the leaf on top of the VisitStack.
181
22.5M
    NodeRef visitingN = VisitStack.back().Node;
182
22.5M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
22.5M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
22.5M
    VisitStack.pop_back();
185
22.5M
186
22.5M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
22.5M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum19.0M
)
188
2.33M
      VisitStack.back().MinVisited = minVisitNum;
189
22.5M
190
22.5M
#if 0 // Enable if needed when debugging.
191
22.5M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
22.5M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
22.5M
          nodeVisitNumbers[visitingN] << "\n";
194
22.5M
#endif
195
22.5M
196
22.5M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.73M
      continue;
198
18.7M
199
18.7M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
18.7M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
18.7M
    // reset their minVisit values, and return (this suspends
202
18.7M
    // the DFS traversal till the next ++).
203
22.5M
    
do 18.7M
{
204
22.5M
      CurrentSCC.push_back(SCCNodeStack.back());
205
22.5M
      SCCNodeStack.pop_back();
206
22.5M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
22.5M
    } while (CurrentSCC.back() != visitingN);
208
18.7M
    return;
209
18.7M
  }
210
22.2M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::GetNextSCC()
Line
Count
Source
175
4.70k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
4.70k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
4.72k
  while (!VisitStack.empty()) {
178
2.42k
    DFSVisitChildren();
179
2.42k
180
2.42k
    // Pop the leaf on top of the VisitStack.
181
2.42k
    NodeRef visitingN = VisitStack.back().Node;
182
2.42k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
2.42k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
2.42k
    VisitStack.pop_back();
185
2.42k
186
2.42k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
2.42k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum125
)
188
16
      VisitStack.back().MinVisited = minVisitNum;
189
2.42k
190
2.42k
#if 0 // Enable if needed when debugging.
191
2.42k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
2.42k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
2.42k
          nodeVisitNumbers[visitingN] << "\n";
194
2.42k
#endif
195
2.42k
196
2.42k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
20
      continue;
198
2.40k
199
2.40k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
2.40k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
2.40k
    // reset their minVisit values, and return (this suspends
202
2.40k
    // the DFS traversal till the next ++).
203
2.42k
    
do 2.40k
{
204
2.42k
      CurrentSCC.push_back(SCCNodeStack.back());
205
2.42k
      SCCNodeStack.pop_back();
206
2.42k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
2.42k
    } while (CurrentSCC.back() != visitingN);
208
2.40k
    return;
209
2.40k
  }
210
4.70k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::GetNextSCC()
Line
Count
Source
175
15.7k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
15.7k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
26.2k
  while (!VisitStack.empty()) {
178
25.5k
    DFSVisitChildren();
179
25.5k
180
25.5k
    // Pop the leaf on top of the VisitStack.
181
25.5k
    NodeRef visitingN = VisitStack.back().Node;
182
25.5k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
25.5k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
25.5k
    VisitStack.pop_back();
185
25.5k
186
25.5k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
25.5k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum24.9k
)
188
7.11k
      VisitStack.back().MinVisited = minVisitNum;
189
25.5k
190
25.5k
#if 0 // Enable if needed when debugging.
191
25.5k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
25.5k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
25.5k
          nodeVisitNumbers[visitingN] << "\n";
194
25.5k
#endif
195
25.5k
196
25.5k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
10.4k
      continue;
198
15.1k
199
15.1k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
15.1k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
15.1k
    // reset their minVisit values, and return (this suspends
202
15.1k
    // the DFS traversal till the next ++).
203
25.5k
    
do 15.1k
{
204
25.5k
      CurrentSCC.push_back(SCCNodeStack.back());
205
25.5k
      SCCNodeStack.pop_back();
206
25.5k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
25.5k
    } while (CurrentSCC.back() != visitingN);
208
15.1k
    return;
209
15.1k
  }
210
15.7k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::GetNextSCC()
Line
Count
Source
175
17.4M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
17.4M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
21.1M
  while (!VisitStack.empty()) {
178
18.4M
    DFSVisitChildren();
179
18.4M
180
18.4M
    // Pop the leaf on top of the VisitStack.
181
18.4M
    NodeRef visitingN = VisitStack.back().Node;
182
18.4M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
18.4M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
18.4M
    VisitStack.pop_back();
185
18.4M
186
18.4M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
18.4M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum15.6M
)
188
2.32M
      VisitStack.back().MinVisited = minVisitNum;
189
18.4M
190
18.4M
#if 0 // Enable if needed when debugging.
191
18.4M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
18.4M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
18.4M
          nodeVisitNumbers[visitingN] << "\n";
194
18.4M
#endif
195
18.4M
196
18.4M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.71M
      continue;
198
14.6M
199
14.6M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
14.6M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
14.6M
    // reset their minVisit values, and return (this suspends
202
14.6M
    // the DFS traversal till the next ++).
203
18.4M
    
do 14.6M
{
204
18.4M
      CurrentSCC.push_back(SCCNodeStack.back());
205
18.4M
      SCCNodeStack.pop_back();
206
18.4M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
18.4M
    } while (CurrentSCC.back() != visitingN);
208
14.6M
    return;
209
14.6M
  }
210
17.4M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::GetNextSCC()
Line
Count
Source
175
3.54M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
3.54M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
3.54M
  while (!VisitStack.empty()) {
178
3.45M
    DFSVisitChildren();
179
3.45M
180
3.45M
    // Pop the leaf on top of the VisitStack.
181
3.45M
    NodeRef visitingN = VisitStack.back().Node;
182
3.45M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
3.45M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
3.45M
    VisitStack.pop_back();
185
3.45M
186
3.45M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
3.45M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum3.36M
)
188
1.48k
      VisitStack.back().MinVisited = minVisitNum;
189
3.45M
190
3.45M
#if 0 // Enable if needed when debugging.
191
3.45M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
3.45M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
3.45M
          nodeVisitNumbers[visitingN] << "\n";
194
3.45M
#endif
195
3.45M
196
3.45M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.03k
      continue;
198
3.45M
199
3.45M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
3.45M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
3.45M
    // reset their minVisit values, and return (this suspends
202
3.45M
    // the DFS traversal till the next ++).
203
3.45M
    
do 3.45M
{
204
3.45M
      CurrentSCC.push_back(SCCNodeStack.back());
205
3.45M
      SCCNodeStack.pop_back();
206
3.45M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
3.45M
    } while (CurrentSCC.back() != visitingN);
208
3.45M
    return;
209
3.45M
  }
210
3.54M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::GetNextSCC()
Line
Count
Source
175
20
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
20
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
22
  while (!VisitStack.empty()) {
178
19
    DFSVisitChildren();
179
19
180
19
    // Pop the leaf on top of the VisitStack.
181
19
    NodeRef visitingN = VisitStack.back().Node;
182
19
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
19
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
19
    VisitStack.pop_back();
185
19
186
19
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
19
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum16
)
188
0
      VisitStack.back().MinVisited = minVisitNum;
189
19
190
19
#if 0 // Enable if needed when debugging.
191
19
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
19
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
19
          nodeVisitNumbers[visitingN] << "\n";
194
19
#endif
195
19
196
19
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
2
      continue;
198
17
199
17
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
17
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
17
    // reset their minVisit values, and return (this suspends
202
17
    // the DFS traversal till the next ++).
203
19
    
do 17
{
204
19
      CurrentSCC.push_back(SCCNodeStack.back());
205
19
      SCCNodeStack.pop_back();
206
19
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
19
    } while (CurrentSCC.back() != visitingN);
208
17
    return;
209
17
  }
210
20
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::GetNextSCC()
Line
Count
Source
175
18
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
18
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
19
  while (!VisitStack.empty()) {
178
15
    DFSVisitChildren();
179
15
180
15
    // Pop the leaf on top of the VisitStack.
181
15
    NodeRef visitingN = VisitStack.back().Node;
182
15
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
15
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
15
    VisitStack.pop_back();
185
15
186
15
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
15
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum11
)
188
0
      VisitStack.back().MinVisited = minVisitNum;
189
15
190
15
#if 0 // Enable if needed when debugging.
191
15
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
15
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
15
          nodeVisitNumbers[visitingN] << "\n";
194
15
#endif
195
15
196
15
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
1
      continue;
198
14
199
14
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
14
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
14
    // reset their minVisit values, and return (this suspends
202
14
    // the DFS traversal till the next ++).
203
15
    
do 14
{
204
15
      CurrentSCC.push_back(SCCNodeStack.back());
205
15
      SCCNodeStack.pop_back();
206
15
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
15
    } while (CurrentSCC.back() != visitingN);
208
14
    return;
209
14
  }
210
18
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::GetNextSCC()
Line
Count
Source
175
1.20M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
1.20M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
1.20M
  while (!VisitStack.empty()) {
178
605k
    DFSVisitChildren();
179
605k
180
605k
    // Pop the leaf on top of the VisitStack.
181
605k
    NodeRef visitingN = VisitStack.back().Node;
182
605k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
605k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
605k
    VisitStack.pop_back();
185
605k
186
605k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
605k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum625
)
188
2
      VisitStack.back().MinVisited = minVisitNum;
189
605k
190
605k
#if 0 // Enable if needed when debugging.
191
605k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
605k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
605k
          nodeVisitNumbers[visitingN] << "\n";
194
605k
#endif
195
605k
196
605k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
29
      continue;
198
605k
199
605k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
605k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
605k
    // reset their minVisit values, and return (this suspends
202
605k
    // the DFS traversal till the next ++).
203
605k
    
do 605k
{
204
605k
      CurrentSCC.push_back(SCCNodeStack.back());
205
605k
      SCCNodeStack.pop_back();
206
605k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
605k
    } while (CurrentSCC.back() != visitingN);
208
605k
    return;
209
605k
  }
210
1.20M
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::GetNextSCC()
211
212
template <class GraphT, class GT>
213
6
bool scc_iterator<GraphT, GT>::hasLoop() const {
214
6
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
215
6
    if (CurrentSCC.size() > 1)
216
2
      return true;
217
4
    NodeRef N = CurrentSCC.front();
218
9
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
219
5
         ++CI)
220
5
      if (*CI == N)
221
0
        return true;
222
4
    return false;
223
4
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::hasLoop() const
Line
Count
Source
213
6
bool scc_iterator<GraphT, GT>::hasLoop() const {
214
6
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
215
6
    if (CurrentSCC.size() > 1)
216
2
      return true;
217
4
    NodeRef N = CurrentSCC.front();
218
9
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
219
5
         ++CI)
220
5
      if (*CI == N)
221
0
        return true;
222
4
    return false;
223
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
224
225
/// Construct the begin iterator for a deduced graph type T.
226
3.45M
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
3.45M
  return scc_iterator<T>::begin(G);
228
3.45M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> > llvm::scc_begin<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
226
2.29k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
2.29k
  return scc_iterator<T>::begin(G);
228
2.29k
}
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
656
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
656
  return scc_iterator<T>::begin(G);
228
656
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> > llvm::scc_begin<llvm::Function const*>(llvm::Function const* const&)
Line
Count
Source
226
2.75M
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
2.75M
  return scc_iterator<T>::begin(G);
228
2.75M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> > llvm::scc_begin<llvm::CallGraph*>(llvm::CallGraph* const&)
Line
Count
Source
226
92.2k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
92.2k
  return scc_iterator<T>::begin(G);
228
92.2k
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> > llvm::scc_begin<llvm::CallGraph const*>(llvm::CallGraph const* const&)
Line
Count
Source
226
3
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
3
  return scc_iterator<T>::begin(G);
228
3
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> > llvm::scc_begin<llvm::ModuleSummaryIndex*>(llvm::ModuleSummaryIndex* const&)
Line
Count
Source
226
4
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
4
  return scc_iterator<T>::begin(G);
228
4
}
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
604k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
604k
  return scc_iterator<T>::begin(G);
228
604k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> > llvm::scc_begin<llvm::Function*>(llvm::Function* const&)
229
230
/// 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