Coverage Report

Created: 2018-09-25 00:18

/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.6M
        : 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
26.3k
        : 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.5M
        : 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.49M
        : 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
613k
        : 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.42M
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
3.42M
    DFSVisitOne(entryN);
95
3.42M
    GetNextSCC();
96
3.42M
  }
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
664
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
664
    DFSVisitOne(entryN);
95
664
    GetNextSCC();
96
664
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::scc_iterator(llvm::BasicBlock const*)
Line
Count
Source
93
2.71M
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
2.71M
    DFSVisitOne(entryN);
95
2.71M
    GetNextSCC();
96
2.71M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::scc_iterator(llvm::CallGraphNode*)
Line
Count
Source
93
93.0k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
93.0k
    DFSVisitOne(entryN);
95
93.0k
    GetNextSCC();
96
93.0k
  }
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
1
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
1
    DFSVisitOne(entryN);
95
1
    GetNextSCC();
96
1
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::scc_iterator((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
93
612k
  scc_iterator(NodeRef entryN) : visitNum(0) {
94
612k
    DFSVisitOne(entryN);
95
612k
    GetNextSCC();
96
612k
  }
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.42M
  static scc_iterator begin(const GraphT &G) {
103
3.42M
    return scc_iterator(GT::getEntryNode(G));
104
3.42M
  }
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
664
  static scc_iterator begin(const GraphT &G) {
103
664
    return scc_iterator(GT::getEntryNode(G));
104
664
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::begin(llvm::Function const* const&)
Line
Count
Source
102
2.71M
  static scc_iterator begin(const GraphT &G) {
103
2.71M
    return scc_iterator(GT::getEntryNode(G));
104
2.71M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::begin(llvm::CallGraph* const&)
Line
Count
Source
102
93.0k
  static scc_iterator begin(const GraphT &G) {
103
93.0k
    return scc_iterator(GT::getEntryNode(G));
104
93.0k
  }
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
1
  static scc_iterator begin(const GraphT &G) {
103
1
    return scc_iterator(GT::getEntryNode(G));
104
1
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::begin((anonymous namespace)::ArgumentGraph* const&)
Line
Count
Source
102
612k
  static scc_iterator begin(const GraphT &G) {
103
612k
    return scc_iterator(GT::getEntryNode(G));
104
612k
  }
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.3M
  bool isAtEnd() const {
110
22.3M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
22.3M
    return CurrentSCC.empty();
112
22.3M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::isAtEnd() const
Line
Count
Source
109
4.69k
  bool isAtEnd() const {
110
4.69k
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
4.69k
    return CurrentSCC.empty();
112
4.69k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::isAtEnd() const
Line
Count
Source
109
16.2k
  bool isAtEnd() const {
110
16.2k
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
16.2k
    return CurrentSCC.empty();
112
16.2k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::isAtEnd() const
Line
Count
Source
109
17.5M
  bool isAtEnd() const {
110
17.5M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
17.5M
    return CurrentSCC.empty();
112
17.5M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::isAtEnd() const
Line
Count
Source
109
3.58M
  bool isAtEnd() const {
110
3.58M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
3.58M
    return CurrentSCC.empty();
112
3.58M
  }
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
6
  bool isAtEnd() const {
110
6
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
6
    return CurrentSCC.empty();
112
6
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::isAtEnd() const
Line
Count
Source
109
1.22M
  bool isAtEnd() const {
110
1.22M
    assert(!CurrentSCC.empty() || VisitStack.empty());
111
1.22M
    return CurrentSCC.empty();
112
1.22M
  }
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.9M
  scc_iterator &operator++() {
119
18.9M
    GetNextSCC();
120
18.9M
    return *this;
121
18.9M
  }
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.5k
  scc_iterator &operator++() {
119
15.5k
    GetNextSCC();
120
15.5k
    return *this;
121
15.5k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator++()
Line
Count
Source
118
14.7M
  scc_iterator &operator++() {
119
14.7M
    GetNextSCC();
120
14.7M
    return *this;
121
14.7M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator++()
Line
Count
Source
118
3.48M
  scc_iterator &operator++() {
119
3.48M
    GetNextSCC();
120
3.48M
    return *this;
121
3.48M
  }
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
5
  scc_iterator &operator++() {
119
5
    GetNextSCC();
120
5
    return *this;
121
5
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator++()
Line
Count
Source
118
613k
  scc_iterator &operator++() {
119
613k
    GetNextSCC();
120
613k
    return *this;
121
613k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator++()
122
123
19.3M
  reference operator*() const {
124
19.3M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
19.3M
    return CurrentSCC;
126
19.3M
  }
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
16.3k
  reference operator*() const {
124
16.3k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
16.3k
    return CurrentSCC;
126
16.3k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator*() const
Line
Count
Source
123
14.7M
  reference operator*() const {
124
14.7M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
14.7M
    return CurrentSCC;
126
14.7M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator*() const
Line
Count
Source
123
3.94M
  reference operator*() const {
124
3.94M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
3.94M
    return CurrentSCC;
126
3.94M
  }
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
15
  reference operator*() const {
124
15
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
15
    return CurrentSCC;
126
15
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator*() const
Line
Count
Source
123
613k
  reference operator*() const {
124
613k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
125
613k
    return CurrentSCC;
126
613k
  }
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.77k
  void ReplaceNode(NodeRef Old, NodeRef New) {
137
1.77k
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
138
1.77k
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
139
1.77k
    nodeVisitNumbers.erase(Old);
140
1.77k
  }
141
};
142
143
template <class GraphT, class GT>
144
22.6M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
22.6M
  ++visitNum;
146
22.6M
  nodeVisitNumbers[N] = visitNum;
147
22.6M
  SCCNodeStack.push_back(N);
148
22.6M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
22.6M
#if 0 // Enable if needed when debugging.
150
22.6M
  dbgs() << "TarjanSCC: Node " << N <<
151
22.6M
        " : visitNum = " << visitNum << "\n";
152
22.6M
#endif
153
22.6M
}
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
26.3k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
26.3k
  ++visitNum;
146
26.3k
  nodeVisitNumbers[N] = visitNum;
147
26.3k
  SCCNodeStack.push_back(N);
148
26.3k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
26.3k
#if 0 // Enable if needed when debugging.
150
26.3k
  dbgs() << "TarjanSCC: Node " << N <<
151
26.3k
        " : visitNum = " << visitNum << "\n";
152
26.3k
#endif
153
26.3k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitOne(llvm::BasicBlock const*)
Line
Count
Source
144
18.5M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
18.5M
  ++visitNum;
146
18.5M
  nodeVisitNumbers[N] = visitNum;
147
18.5M
  SCCNodeStack.push_back(N);
148
18.5M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
18.5M
#if 0 // Enable if needed when debugging.
150
18.5M
  dbgs() << "TarjanSCC: Node " << N <<
151
18.5M
        " : visitNum = " << visitNum << "\n";
152
18.5M
#endif
153
18.5M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitOne(llvm::CallGraphNode*)
Line
Count
Source
144
3.49M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
3.49M
  ++visitNum;
146
3.49M
  nodeVisitNumbers[N] = visitNum;
147
3.49M
  SCCNodeStack.push_back(N);
148
3.49M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
3.49M
#if 0 // Enable if needed when debugging.
150
3.49M
  dbgs() << "TarjanSCC: Node " << N <<
151
3.49M
        " : visitNum = " << visitNum << "\n";
152
3.49M
#endif
153
3.49M
}
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
6
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
6
  ++visitNum;
146
6
  nodeVisitNumbers[N] = visitNum;
147
6
  SCCNodeStack.push_back(N);
148
6
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
6
#if 0 // Enable if needed when debugging.
150
6
  dbgs() << "TarjanSCC: Node " << N <<
151
6
        " : visitNum = " << visitNum << "\n";
152
6
#endif
153
6
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitOne((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
144
613k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
145
613k
  ++visitNum;
146
613k
  nodeVisitNumbers[N] = visitNum;
147
613k
  SCCNodeStack.push_back(N);
148
613k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
149
613k
#if 0 // Enable if needed when debugging.
150
613k
  dbgs() << "TarjanSCC: Node " << N <<
151
613k
        " : visitNum = " << visitNum << "\n";
152
613k
#endif
153
613k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitOne(llvm::BasicBlock*)
154
155
template <class GraphT, class GT>
156
22.6M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
22.6M
  assert(!VisitStack.empty());
158
61.2M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
38.6M
    // TOS has at least one more child so continue DFS
160
38.6M
    NodeRef childN = *VisitStack.back().NextChild++;
161
38.6M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
38.6M
        nodeVisitNumbers.find(childN);
163
38.6M
    if (Visited == nodeVisitNumbers.end()) {
164
19.2M
      // this node has never been seen.
165
19.2M
      DFSVisitOne(childN);
166
19.2M
      continue;
167
19.2M
    }
168
19.3M
169
19.3M
    unsigned childNum = Visited->second;
170
19.3M
    if (VisitStack.back().MinVisited > childNum)
171
1.52M
      VisitStack.back().MinVisited = childNum;
172
19.3M
  }
173
22.6M
}
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.60k
  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
26.3k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
26.3k
  assert(!VisitStack.empty());
158
70.0k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
43.7k
    // TOS has at least one more child so continue DFS
160
43.7k
    NodeRef childN = *VisitStack.back().NextChild++;
161
43.7k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
43.7k
        nodeVisitNumbers.find(childN);
163
43.7k
    if (Visited == nodeVisitNumbers.end()) {
164
25.6k
      // this node has never been seen.
165
25.6k
      DFSVisitOne(childN);
166
25.6k
      continue;
167
25.6k
    }
168
18.0k
169
18.0k
    unsigned childNum = Visited->second;
170
18.0k
    if (VisitStack.back().MinVisited > childNum)
171
3.65k
      VisitStack.back().MinVisited = childNum;
172
18.0k
  }
173
26.3k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitChildren()
Line
Count
Source
156
18.5M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
18.5M
  assert(!VisitStack.empty());
158
43.0M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
24.5M
    // TOS has at least one more child so continue DFS
160
24.5M
    NodeRef childN = *VisitStack.back().NextChild++;
161
24.5M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
24.5M
        nodeVisitNumbers.find(childN);
163
24.5M
    if (Visited == nodeVisitNumbers.end()) {
164
15.8M
      // this node has never been seen.
165
15.8M
      DFSVisitOne(childN);
166
15.8M
      continue;
167
15.8M
    }
168
8.72M
169
8.72M
    unsigned childNum = Visited->second;
170
8.72M
    if (VisitStack.back().MinVisited > childNum)
171
1.52M
      VisitStack.back().MinVisited = childNum;
172
8.72M
  }
173
18.5M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitChildren()
Line
Count
Source
156
3.49M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
3.49M
  assert(!VisitStack.empty());
158
17.5M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
14.0M
    // TOS has at least one more child so continue DFS
160
14.0M
    NodeRef childN = *VisitStack.back().NextChild++;
161
14.0M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
14.0M
        nodeVisitNumbers.find(childN);
163
14.0M
    if (Visited == nodeVisitNumbers.end()) {
164
3.39M
      // this node has never been seen.
165
3.39M
      DFSVisitOne(childN);
166
3.39M
      continue;
167
3.39M
    }
168
10.6M
169
10.6M
    unsigned childNum = Visited->second;
170
10.6M
    if (VisitStack.back().MinVisited > childNum)
171
1.79k
      VisitStack.back().MinVisited = childNum;
172
10.6M
  }
173
3.49M
}
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
6
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
6
  assert(!VisitStack.empty());
158
13
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
7
    // TOS has at least one more child so continue DFS
160
7
    NodeRef childN = *VisitStack.back().NextChild++;
161
7
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
7
        nodeVisitNumbers.find(childN);
163
7
    if (Visited == nodeVisitNumbers.end()) {
164
5
      // this node has never been seen.
165
5
      DFSVisitOne(childN);
166
5
      continue;
167
5
    }
168
2
169
2
    unsigned childNum = Visited->second;
170
2
    if (VisitStack.back().MinVisited > childNum)
171
1
      VisitStack.back().MinVisited = childNum;
172
2
  }
173
6
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitChildren()
Line
Count
Source
156
613k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
157
613k
  assert(!VisitStack.empty());
158
615k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
159
2.33k
    // TOS has at least one more child so continue DFS
160
2.33k
    NodeRef childN = *VisitStack.back().NextChild++;
161
2.33k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
162
2.33k
        nodeVisitNumbers.find(childN);
163
2.33k
    if (Visited == nodeVisitNumbers.end()) {
164
626
      // this node has never been seen.
165
626
      DFSVisitOne(childN);
166
626
      continue;
167
626
    }
168
1.70k
169
1.70k
    unsigned childNum = Visited->second;
170
1.70k
    if (VisitStack.back().MinVisited > childNum)
171
27
      VisitStack.back().MinVisited = childNum;
172
1.70k
  }
173
613k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitChildren()
174
175
22.3M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
22.3M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
26.0M
  while (!VisitStack.empty()) {
178
22.6M
    DFSVisitChildren();
179
22.6M
180
22.6M
    // Pop the leaf on top of the VisitStack.
181
22.6M
    NodeRef visitingN = VisitStack.back().Node;
182
22.6M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
22.6M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
22.6M
    VisitStack.pop_back();
185
22.6M
186
22.6M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
22.6M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum19.2M
)
188
2.34M
      VisitStack.back().MinVisited = minVisitNum;
189
22.6M
190
22.6M
#if 0 // Enable if needed when debugging.
191
22.6M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
22.6M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
22.6M
          nodeVisitNumbers[visitingN] << "\n";
194
22.6M
#endif
195
22.6M
196
22.6M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.75M
      continue;
198
18.9M
199
18.9M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
18.9M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
18.9M
    // reset their minVisit values, and return (this suspends
202
18.9M
    // the DFS traversal till the next ++).
203
22.6M
    
do 18.9M
{
204
22.6M
      CurrentSCC.push_back(SCCNodeStack.back());
205
22.6M
      SCCNodeStack.pop_back();
206
22.6M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
22.6M
    } while (CurrentSCC.back() != visitingN);
208
18.9M
    return;
209
18.9M
  }
210
22.3M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::GetNextSCC()
Line
Count
Source
175
4.69k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
4.69k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
4.71k
  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.69k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::GetNextSCC()
Line
Count
Source
175
16.2k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
16.2k
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
26.9k
  while (!VisitStack.empty()) {
178
26.3k
    DFSVisitChildren();
179
26.3k
180
26.3k
    // Pop the leaf on top of the VisitStack.
181
26.3k
    NodeRef visitingN = VisitStack.back().Node;
182
26.3k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
26.3k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
26.3k
    VisitStack.pop_back();
185
26.3k
186
26.3k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
26.3k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum25.6k
)
188
7.35k
      VisitStack.back().MinVisited = minVisitNum;
189
26.3k
190
26.3k
#if 0 // Enable if needed when debugging.
191
26.3k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
26.3k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
26.3k
          nodeVisitNumbers[visitingN] << "\n";
194
26.3k
#endif
195
26.3k
196
26.3k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
10.7k
      continue;
198
15.5k
199
15.5k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
15.5k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
15.5k
    // reset their minVisit values, and return (this suspends
202
15.5k
    // the DFS traversal till the next ++).
203
26.3k
    
do 15.5k
{
204
26.3k
      CurrentSCC.push_back(SCCNodeStack.back());
205
26.3k
      SCCNodeStack.pop_back();
206
26.3k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
26.3k
    } while (CurrentSCC.back() != visitingN);
208
15.5k
    return;
209
15.5k
  }
210
16.2k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::GetNextSCC()
Line
Count
Source
175
17.5M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
17.5M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
21.2M
  while (!VisitStack.empty()) {
178
18.5M
    DFSVisitChildren();
179
18.5M
180
18.5M
    // Pop the leaf on top of the VisitStack.
181
18.5M
    NodeRef visitingN = VisitStack.back().Node;
182
18.5M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
18.5M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
18.5M
    VisitStack.pop_back();
185
18.5M
186
18.5M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
18.5M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum15.8M
)
188
2.33M
      VisitStack.back().MinVisited = minVisitNum;
189
18.5M
190
18.5M
#if 0 // Enable if needed when debugging.
191
18.5M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
18.5M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
18.5M
          nodeVisitNumbers[visitingN] << "\n";
194
18.5M
#endif
195
18.5M
196
18.5M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.73M
      continue;
198
14.7M
199
14.7M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
14.7M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
14.7M
    // reset their minVisit values, and return (this suspends
202
14.7M
    // the DFS traversal till the next ++).
203
18.5M
    
do 14.7M
{
204
18.5M
      CurrentSCC.push_back(SCCNodeStack.back());
205
18.5M
      SCCNodeStack.pop_back();
206
18.5M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
18.5M
    } while (CurrentSCC.back() != visitingN);
208
14.7M
    return;
209
14.7M
  }
210
17.5M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::GetNextSCC()
Line
Count
Source
175
3.58M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
3.58M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
3.58M
  while (!VisitStack.empty()) {
178
3.49M
    DFSVisitChildren();
179
3.49M
180
3.49M
    // Pop the leaf on top of the VisitStack.
181
3.49M
    NodeRef visitingN = VisitStack.back().Node;
182
3.49M
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
3.49M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
3.49M
    VisitStack.pop_back();
185
3.49M
186
3.49M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
3.49M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum3.39M
)
188
1.62k
      VisitStack.back().MinVisited = minVisitNum;
189
3.49M
190
3.49M
#if 0 // Enable if needed when debugging.
191
3.49M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
3.49M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
3.49M
          nodeVisitNumbers[visitingN] << "\n";
194
3.49M
#endif
195
3.49M
196
3.49M
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
3.21k
      continue;
198
3.48M
199
3.48M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
3.48M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
3.48M
    // reset their minVisit values, and return (this suspends
202
3.48M
    // the DFS traversal till the next ++).
203
3.49M
    
do 3.48M
{
204
3.49M
      CurrentSCC.push_back(SCCNodeStack.back());
205
3.49M
      SCCNodeStack.pop_back();
206
3.49M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
3.49M
    } while (CurrentSCC.back() != visitingN);
208
3.48M
    return;
209
3.48M
  }
210
3.58M
}
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
6
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
6
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
7
  while (!VisitStack.empty()) {
178
6
    DFSVisitChildren();
179
6
180
6
    // Pop the leaf on top of the VisitStack.
181
6
    NodeRef visitingN = VisitStack.back().Node;
182
6
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
6
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
6
    VisitStack.pop_back();
185
6
186
6
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
6
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum5
)
188
0
      VisitStack.back().MinVisited = minVisitNum;
189
6
190
6
#if 0 // Enable if needed when debugging.
191
6
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
6
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
6
          nodeVisitNumbers[visitingN] << "\n";
194
6
#endif
195
6
196
6
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
1
      continue;
198
5
199
5
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
5
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
5
    // reset their minVisit values, and return (this suspends
202
5
    // the DFS traversal till the next ++).
203
6
    
do 5
{
204
6
      CurrentSCC.push_back(SCCNodeStack.back());
205
6
      SCCNodeStack.pop_back();
206
6
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
6
    } while (CurrentSCC.back() != visitingN);
208
5
    return;
209
5
  }
210
6
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::GetNextSCC()
Line
Count
Source
175
1.22M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
176
1.22M
  CurrentSCC.clear(); // Prepare to compute the next SCC
177
1.22M
  while (!VisitStack.empty()) {
178
613k
    DFSVisitChildren();
179
613k
180
613k
    // Pop the leaf on top of the VisitStack.
181
613k
    NodeRef visitingN = VisitStack.back().Node;
182
613k
    unsigned minVisitNum = VisitStack.back().MinVisited;
183
613k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
184
613k
    VisitStack.pop_back();
185
613k
186
613k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
187
613k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum626
)
188
2
      VisitStack.back().MinVisited = minVisitNum;
189
613k
190
613k
#if 0 // Enable if needed when debugging.
191
613k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
192
613k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
193
613k
          nodeVisitNumbers[visitingN] << "\n";
194
613k
#endif
195
613k
196
613k
    if (minVisitNum != nodeVisitNumbers[visitingN])
197
29
      continue;
198
613k
199
613k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
200
613k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
201
613k
    // reset their minVisit values, and return (this suspends
202
613k
    // the DFS traversal till the next ++).
203
613k
    
do 613k
{
204
613k
      CurrentSCC.push_back(SCCNodeStack.back());
205
613k
      SCCNodeStack.pop_back();
206
613k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
207
613k
    } while (CurrentSCC.back() != visitingN);
208
613k
    return;
209
613k
  }
210
1.22M
}
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.42M
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
3.42M
  return scc_iterator<T>::begin(G);
228
3.42M
}
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
664
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
664
  return scc_iterator<T>::begin(G);
228
664
}
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.71M
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
2.71M
  return scc_iterator<T>::begin(G);
228
2.71M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> > llvm::scc_begin<llvm::CallGraph*>(llvm::CallGraph* const&)
Line
Count
Source
226
93.0k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
93.0k
  return scc_iterator<T>::begin(G);
228
93.0k
}
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
1
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
1
  return scc_iterator<T>::begin(G);
228
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
226
612k
template <class T> scc_iterator<T> scc_begin(const T &G) {
227
612k
  return scc_iterator<T>::begin(G);
228
612k
}
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