Coverage Report

Created: 2019-03-24 22:13

/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
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
/// \file
9
///
10
/// This builds on the llvm/ADT/GraphTraits.h file to find the strongly
11
/// connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS
12
/// algorithm.
13
///
14
/// The SCC iterator has the important property that if a node in SCC S1 has an
15
/// edge to a node in SCC S2, then it visits S1 *after* S2.
16
///
17
/// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE:
18
/// This requires some simple wrappers and is not supported yet.)
19
///
20
//===----------------------------------------------------------------------===//
21
22
#ifndef LLVM_ADT_SCCITERATOR_H
23
#define LLVM_ADT_SCCITERATOR_H
24
25
#include "llvm/ADT/DenseMap.h"
26
#include "llvm/ADT/GraphTraits.h"
27
#include "llvm/ADT/iterator.h"
28
#include <cassert>
29
#include <cstddef>
30
#include <iterator>
31
#include <vector>
32
33
namespace llvm {
34
35
/// Enumerate the SCCs of a directed graph in reverse topological order
36
/// of the SCC DAG.
37
///
38
/// This is implemented using Tarjan's DFS algorithm using an internal stack to
39
/// build up a vector of nodes in a particular SCC. Note that it is a forward
40
/// iterator and thus you cannot backtrack or re-visit nodes.
41
template <class GraphT, class GT = GraphTraits<GraphT>>
42
class scc_iterator : public iterator_facade_base<
43
                         scc_iterator<GraphT, GT>, std::forward_iterator_tag,
44
                         const std::vector<typename GT::NodeRef>, ptrdiff_t> {
45
  using NodeRef = typename GT::NodeRef;
46
  using ChildItTy = typename GT::ChildIteratorType;
47
  using SccTy = std::vector<NodeRef>;
48
  using reference = typename scc_iterator::reference;
49
50
  /// Element of VisitStack during DFS.
51
  struct StackElement {
52
    NodeRef Node;         ///< The current node pointer.
53
    ChildItTy NextChild;  ///< The next child, modified inplace during DFS.
54
    unsigned MinVisited;  ///< Minimum uplink value of all children of Node.
55
56
    StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
57
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
57
2.41k
        : 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
57
29.8k
        : 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
57
18.3M
        : 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
57
3.56M
        : 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
57
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
57
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
57
614k
        : 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)
58
59
    bool operator==(const StackElement &Other) const {
60
      return Node == Other.Node &&
61
             NextChild == Other.NextChild &&
62
             MinVisited == Other.MinVisited;
63
    }
64
  };
65
66
  /// The visit counters used to detect when a complete SCC is on the stack.
67
  /// visitNum is the global counter.
68
  ///
69
  /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
70
  unsigned visitNum;
71
  DenseMap<NodeRef, unsigned> nodeVisitNumbers;
72
73
  /// Stack holding nodes of the SCC.
74
  std::vector<NodeRef> SCCNodeStack;
75
76
  /// The current SCC, retrieved using operator*().
77
  SccTy CurrentSCC;
78
79
  /// DFS stack, Used to maintain the ordering.  The top contains the current
80
  /// node, the next child to visit, and the minimum uplink value of all child
81
  std::vector<StackElement> VisitStack;
82
83
  /// A single "visit" within the non-recursive DFS traversal.
84
  void DFSVisitOne(NodeRef N);
85
86
  /// The stack-based DFS traversal; defined below.
87
  void DFSVisitChildren();
88
89
  /// Compute the next SCC using the DFS traversal.
90
  void GetNextSCC();
91
92
3.46M
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
3.46M
    DFSVisitOne(entryN);
94
3.46M
    GetNextSCC();
95
3.46M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::scc_iterator(llvm::MachineBasicBlock*)
Line
Count
Source
92
2.28k
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
2.28k
    DFSVisitOne(entryN);
94
2.28k
    GetNextSCC();
95
2.28k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::scc_iterator(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
92
735
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
735
    DFSVisitOne(entryN);
94
735
    GetNextSCC();
95
735
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::scc_iterator(llvm::BasicBlock const*)
Line
Count
Source
92
2.75M
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
2.75M
    DFSVisitOne(entryN);
94
2.75M
    GetNextSCC();
95
2.75M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::scc_iterator(llvm::CallGraphNode*)
Line
Count
Source
92
95.6k
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
95.6k
    DFSVisitOne(entryN);
94
95.6k
    GetNextSCC();
95
95.6k
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::scc_iterator(llvm::CallGraphNode const*)
Line
Count
Source
92
3
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
3
    DFSVisitOne(entryN);
94
3
    GetNextSCC();
95
3
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::scc_iterator(llvm::ValueInfo)
Line
Count
Source
92
4
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
4
    DFSVisitOne(entryN);
94
4
    GetNextSCC();
95
4
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::scc_iterator((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
92
613k
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
613k
    DFSVisitOne(entryN);
94
613k
    GetNextSCC();
95
613k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::scc_iterator(llvm::BasicBlock*)
96
97
  /// End is when the DFS stack is empty.
98
  scc_iterator() = default;
99
100
public:
101
3.46M
  static scc_iterator begin(const GraphT &G) {
102
3.46M
    return scc_iterator(GT::getEntryNode(G));
103
3.46M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::begin(llvm::MachineFunction* const&)
Line
Count
Source
101
2.28k
  static scc_iterator begin(const GraphT &G) {
102
2.28k
    return scc_iterator(GT::getEntryNode(G));
103
2.28k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::begin(llvm::bfi_detail::IrreducibleGraph const&)
Line
Count
Source
101
735
  static scc_iterator begin(const GraphT &G) {
102
735
    return scc_iterator(GT::getEntryNode(G));
103
735
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::begin(llvm::Function const* const&)
Line
Count
Source
101
2.75M
  static scc_iterator begin(const GraphT &G) {
102
2.75M
    return scc_iterator(GT::getEntryNode(G));
103
2.75M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::begin(llvm::CallGraph* const&)
Line
Count
Source
101
95.6k
  static scc_iterator begin(const GraphT &G) {
102
95.6k
    return scc_iterator(GT::getEntryNode(G));
103
95.6k
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::begin(llvm::CallGraph const* const&)
Line
Count
Source
101
3
  static scc_iterator begin(const GraphT &G) {
102
3
    return scc_iterator(GT::getEntryNode(G));
103
3
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::begin(llvm::ModuleSummaryIndex* const&)
Line
Count
Source
101
4
  static scc_iterator begin(const GraphT &G) {
102
4
    return scc_iterator(GT::getEntryNode(G));
103
4
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::begin((anonymous namespace)::ArgumentGraph* const&)
Line
Count
Source
101
613k
  static scc_iterator begin(const GraphT &G) {
102
613k
    return scc_iterator(GT::getEntryNode(G));
103
613k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::begin(llvm::Function* const&)
104
  static scc_iterator end(const GraphT &) { return scc_iterator(); }
105
106
  /// Direct loop termination test which is more efficient than
107
  /// comparison with \c end().
108
22.2M
  bool isAtEnd() const {
109
22.2M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
22.2M
    return CurrentSCC.empty();
111
22.2M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::isAtEnd() const
Line
Count
Source
108
4.68k
  bool isAtEnd() const {
109
4.68k
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
4.68k
    return CurrentSCC.empty();
111
4.68k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::isAtEnd() const
Line
Count
Source
108
18.1k
  bool isAtEnd() const {
109
18.1k
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
18.1k
    return CurrentSCC.empty();
111
18.1k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::isAtEnd() const
Line
Count
Source
108
17.3M
  bool isAtEnd() const {
109
17.3M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
17.3M
    return CurrentSCC.empty();
111
17.3M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::isAtEnd() const
Line
Count
Source
108
3.65M
  bool isAtEnd() const {
109
3.65M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
3.65M
    return CurrentSCC.empty();
111
3.65M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::isAtEnd() const
Line
Count
Source
108
20
  bool isAtEnd() const {
109
20
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
20
    return CurrentSCC.empty();
111
20
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::isAtEnd() const
Line
Count
Source
108
18
  bool isAtEnd() const {
109
18
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
18
    return CurrentSCC.empty();
111
18
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::isAtEnd() const
Line
Count
Source
108
1.22M
  bool isAtEnd() const {
109
1.22M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
1.22M
    return CurrentSCC.empty();
111
1.22M
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::isAtEnd() const
112
113
  bool operator==(const scc_iterator &x) const {
114
    return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
115
  }
116
117
18.7M
  scc_iterator &operator++() {
118
18.7M
    GetNextSCC();
119
18.7M
    return *this;
120
18.7M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator++()
Line
Count
Source
117
2.39k
  scc_iterator &operator++() {
118
2.39k
    GetNextSCC();
119
2.39k
    return *this;
120
2.39k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator++()
Line
Count
Source
117
17.3k
  scc_iterator &operator++() {
118
17.3k
    GetNextSCC();
119
17.3k
    return *this;
120
17.3k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator++()
Line
Count
Source
117
14.5M
  scc_iterator &operator++() {
118
14.5M
    GetNextSCC();
119
14.5M
    return *this;
120
14.5M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator++()
Line
Count
Source
117
3.55M
  scc_iterator &operator++() {
118
3.55M
    GetNextSCC();
119
3.55M
    return *this;
120
3.55M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::operator++()
Line
Count
Source
117
17
  scc_iterator &operator++() {
118
17
    GetNextSCC();
119
17
    return *this;
120
17
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::operator++()
Line
Count
Source
117
14
  scc_iterator &operator++() {
118
14
    GetNextSCC();
119
14
    return *this;
120
14
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator++()
Line
Count
Source
117
614k
  scc_iterator &operator++() {
118
614k
    GetNextSCC();
119
614k
    return *this;
120
614k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator++()
121
122
19.2M
  reference operator*() const {
123
19.2M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
19.2M
    return CurrentSCC;
125
19.2M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator*() const
Line
Count
Source
122
2.39k
  reference operator*() const {
123
2.39k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
2.39k
    return CurrentSCC;
125
2.39k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator*() const
Line
Count
Source
122
18.2k
  reference operator*() const {
123
18.2k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
18.2k
    return CurrentSCC;
125
18.2k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator*() const
Line
Count
Source
122
14.5M
  reference operator*() const {
123
14.5M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
14.5M
    return CurrentSCC;
125
14.5M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator*() const
Line
Count
Source
122
4.01M
  reference operator*() const {
123
4.01M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
4.01M
    return CurrentSCC;
125
4.01M
  }
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::operator*() const
Line
Count
Source
122
17
  reference operator*() const {
123
17
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
17
    return CurrentSCC;
125
17
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::operator*() const
Line
Count
Source
122
24
  reference operator*() const {
123
24
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
24
    return CurrentSCC;
125
24
  }
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::operator*() const
Line
Count
Source
122
614k
  reference operator*() const {
123
614k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
614k
    return CurrentSCC;
125
614k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator*() const
126
127
  /// Test if the current SCC has a loop.
128
  ///
129
  /// If the SCC has more than one node, this is trivially true.  If not, it may
130
  /// still contain a loop if the node has an edge back to itself.
131
  bool hasLoop() const;
132
133
  /// This informs the \c scc_iterator that the specified \c Old node
134
  /// has been deleted, and \c New is to be used in its place.
135
1.84k
  void ReplaceNode(NodeRef Old, NodeRef New) {
136
1.84k
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
137
1.84k
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
138
1.84k
    nodeVisitNumbers.erase(Old);
139
1.84k
  }
140
};
141
142
template <class GraphT, class GT>
143
22.5M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
22.5M
  ++visitNum;
145
22.5M
  nodeVisitNumbers[N] = visitNum;
146
22.5M
  SCCNodeStack.push_back(N);
147
22.5M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
22.5M
#if 0 // Enable if needed when debugging.
149
22.5M
  dbgs() << "TarjanSCC: Node " << N <<
150
22.5M
        " : visitNum = " << visitNum << "\n";
151
22.5M
#endif
152
22.5M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitOne(llvm::MachineBasicBlock*)
Line
Count
Source
143
2.41k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
2.41k
  ++visitNum;
145
2.41k
  nodeVisitNumbers[N] = visitNum;
146
2.41k
  SCCNodeStack.push_back(N);
147
2.41k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
2.41k
#if 0 // Enable if needed when debugging.
149
2.41k
  dbgs() << "TarjanSCC: Node " << N <<
150
2.41k
        " : visitNum = " << visitNum << "\n";
151
2.41k
#endif
152
2.41k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitOne(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
143
29.8k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
29.8k
  ++visitNum;
145
29.8k
  nodeVisitNumbers[N] = visitNum;
146
29.8k
  SCCNodeStack.push_back(N);
147
29.8k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
29.8k
#if 0 // Enable if needed when debugging.
149
29.8k
  dbgs() << "TarjanSCC: Node " << N <<
150
29.8k
        " : visitNum = " << visitNum << "\n";
151
29.8k
#endif
152
29.8k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitOne(llvm::BasicBlock const*)
Line
Count
Source
143
18.3M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
18.3M
  ++visitNum;
145
18.3M
  nodeVisitNumbers[N] = visitNum;
146
18.3M
  SCCNodeStack.push_back(N);
147
18.3M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
18.3M
#if 0 // Enable if needed when debugging.
149
18.3M
  dbgs() << "TarjanSCC: Node " << N <<
150
18.3M
        " : visitNum = " << visitNum << "\n";
151
18.3M
#endif
152
18.3M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitOne(llvm::CallGraphNode*)
Line
Count
Source
143
3.56M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
3.56M
  ++visitNum;
145
3.56M
  nodeVisitNumbers[N] = visitNum;
146
3.56M
  SCCNodeStack.push_back(N);
147
3.56M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
3.56M
#if 0 // Enable if needed when debugging.
149
3.56M
  dbgs() << "TarjanSCC: Node " << N <<
150
3.56M
        " : visitNum = " << visitNum << "\n";
151
3.56M
#endif
152
3.56M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::DFSVisitOne(llvm::CallGraphNode const*)
Line
Count
Source
143
19
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
19
  ++visitNum;
145
19
  nodeVisitNumbers[N] = visitNum;
146
19
  SCCNodeStack.push_back(N);
147
19
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
19
#if 0 // Enable if needed when debugging.
149
19
  dbgs() << "TarjanSCC: Node " << N <<
150
19
        " : visitNum = " << visitNum << "\n";
151
19
#endif
152
19
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::DFSVisitOne(llvm::ValueInfo)
Line
Count
Source
143
15
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
15
  ++visitNum;
145
15
  nodeVisitNumbers[N] = visitNum;
146
15
  SCCNodeStack.push_back(N);
147
15
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
15
#if 0 // Enable if needed when debugging.
149
15
  dbgs() << "TarjanSCC: Node " << N <<
150
15
        " : visitNum = " << visitNum << "\n";
151
15
#endif
152
15
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitOne((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
143
614k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
614k
  ++visitNum;
145
614k
  nodeVisitNumbers[N] = visitNum;
146
614k
  SCCNodeStack.push_back(N);
147
614k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
614k
#if 0 // Enable if needed when debugging.
149
614k
  dbgs() << "TarjanSCC: Node " << N <<
150
614k
        " : visitNum = " << visitNum << "\n";
151
614k
#endif
152
614k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitOne(llvm::BasicBlock*)
153
154
template <class GraphT, class GT>
155
22.5M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
22.5M
  assert(!VisitStack.empty());
157
60.7M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
38.2M
    // TOS has at least one more child so continue DFS
159
38.2M
    NodeRef childN = *VisitStack.back().NextChild++;
160
38.2M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
38.2M
        nodeVisitNumbers.find(childN);
162
38.2M
    if (Visited == nodeVisitNumbers.end()) {
163
19.0M
      // this node has never been seen.
164
19.0M
      DFSVisitOne(childN);
165
19.0M
      continue;
166
19.0M
    }
167
19.1M
168
19.1M
    unsigned childNum = Visited->second;
169
19.1M
    if (VisitStack.back().MinVisited > childNum)
170
1.52M
      VisitStack.back().MinVisited = childNum;
171
19.1M
  }
172
22.5M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitChildren()
Line
Count
Source
155
2.41k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
2.41k
  assert(!VisitStack.empty());
157
2.60k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
186
    // TOS has at least one more child so continue DFS
159
186
    NodeRef childN = *VisitStack.back().NextChild++;
160
186
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
186
        nodeVisitNumbers.find(childN);
162
186
    if (Visited == nodeVisitNumbers.end()) {
163
125
      // this node has never been seen.
164
125
      DFSVisitOne(childN);
165
125
      continue;
166
125
    }
167
61
168
61
    unsigned childNum = Visited->second;
169
61
    if (VisitStack.back().MinVisited > childNum)
170
4
      VisitStack.back().MinVisited = childNum;
171
61
  }
172
2.41k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitChildren()
Line
Count
Source
155
29.8k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
29.8k
  assert(!VisitStack.empty());
157
78.4k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
48.6k
    // TOS has at least one more child so continue DFS
159
48.6k
    NodeRef childN = *VisitStack.back().NextChild++;
160
48.6k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
48.6k
        nodeVisitNumbers.find(childN);
162
48.6k
    if (Visited == nodeVisitNumbers.end()) {
163
29.0k
      // this node has never been seen.
164
29.0k
      DFSVisitOne(childN);
165
29.0k
      continue;
166
29.0k
    }
167
19.5k
168
19.5k
    unsigned childNum = Visited->second;
169
19.5k
    if (VisitStack.back().MinVisited > childNum)
170
4.14k
      VisitStack.back().MinVisited = childNum;
171
19.5k
  }
172
29.8k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitChildren()
Line
Count
Source
155
18.3M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
18.3M
  assert(!VisitStack.empty());
157
42.4M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
24.1M
    // TOS has at least one more child so continue DFS
159
24.1M
    NodeRef childN = *VisitStack.back().NextChild++;
160
24.1M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
24.1M
        nodeVisitNumbers.find(childN);
162
24.1M
    if (Visited == nodeVisitNumbers.end()) {
163
15.5M
      // this node has never been seen.
164
15.5M
      DFSVisitOne(childN);
165
15.5M
      continue;
166
15.5M
    }
167
8.58M
168
8.58M
    unsigned childNum = Visited->second;
169
8.58M
    if (VisitStack.back().MinVisited > childNum)
170
1.51M
      VisitStack.back().MinVisited = childNum;
171
8.58M
  }
172
18.3M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitChildren()
Line
Count
Source
155
3.56M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
3.56M
  assert(!VisitStack.empty());
157
17.5M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
14.0M
    // TOS has at least one more child so continue DFS
159
14.0M
    NodeRef childN = *VisitStack.back().NextChild++;
160
14.0M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
14.0M
        nodeVisitNumbers.find(childN);
162
14.0M
    if (Visited == nodeVisitNumbers.end()) {
163
3.46M
      // this node has never been seen.
164
3.46M
      DFSVisitOne(childN);
165
3.46M
      continue;
166
3.46M
    }
167
10.5M
168
10.5M
    unsigned childNum = Visited->second;
169
10.5M
    if (VisitStack.back().MinVisited > childNum)
170
1.73k
      VisitStack.back().MinVisited = childNum;
171
10.5M
  }
172
3.56M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::DFSVisitChildren()
Line
Count
Source
155
19
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
19
  assert(!VisitStack.empty());
157
41
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
22
    // TOS has at least one more child so continue DFS
159
22
    NodeRef childN = *VisitStack.back().NextChild++;
160
22
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
22
        nodeVisitNumbers.find(childN);
162
22
    if (Visited == nodeVisitNumbers.end()) {
163
16
      // this node has never been seen.
164
16
      DFSVisitOne(childN);
165
16
      continue;
166
16
    }
167
6
168
6
    unsigned childNum = Visited->second;
169
6
    if (VisitStack.back().MinVisited > childNum)
170
2
      VisitStack.back().MinVisited = childNum;
171
6
  }
172
19
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::DFSVisitChildren()
Line
Count
Source
155
15
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
15
  assert(!VisitStack.empty());
157
28
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
13
    // TOS has at least one more child so continue DFS
159
13
    NodeRef childN = *VisitStack.back().NextChild++;
160
13
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
13
        nodeVisitNumbers.find(childN);
162
13
    if (Visited == nodeVisitNumbers.end()) {
163
11
      // this node has never been seen.
164
11
      DFSVisitOne(childN);
165
11
      continue;
166
11
    }
167
2
168
2
    unsigned childNum = Visited->second;
169
2
    if (VisitStack.back().MinVisited > childNum)
170
1
      VisitStack.back().MinVisited = childNum;
171
2
  }
172
15
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitChildren()
Line
Count
Source
155
614k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
614k
  assert(!VisitStack.empty());
157
616k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
2.36k
    // TOS has at least one more child so continue DFS
159
2.36k
    NodeRef childN = *VisitStack.back().NextChild++;
160
2.36k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
2.36k
        nodeVisitNumbers.find(childN);
162
2.36k
    if (Visited == nodeVisitNumbers.end()) {
163
637
      // this node has never been seen.
164
637
      DFSVisitOne(childN);
165
637
      continue;
166
637
    }
167
1.72k
168
1.72k
    unsigned childNum = Visited->second;
169
1.72k
    if (VisitStack.back().MinVisited > childNum)
170
27
      VisitStack.back().MinVisited = childNum;
171
1.72k
  }
172
614k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitChildren()
173
174
22.2M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
22.2M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
26.0M
  while (!VisitStack.empty()) {
177
22.5M
    DFSVisitChildren();
178
22.5M
179
22.5M
    // Pop the leaf on top of the VisitStack.
180
22.5M
    NodeRef visitingN = VisitStack.back().Node;
181
22.5M
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
22.5M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
22.5M
    VisitStack.pop_back();
184
22.5M
185
22.5M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
22.5M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum19.0M
)
187
2.34M
      VisitStack.back().MinVisited = minVisitNum;
188
22.5M
189
22.5M
#if 0 // Enable if needed when debugging.
190
22.5M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
22.5M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
22.5M
          nodeVisitNumbers[visitingN] << "\n";
193
22.5M
#endif
194
22.5M
195
22.5M
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
3.75M
      continue;
197
18.7M
198
18.7M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
18.7M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
18.7M
    // reset their minVisit values, and return (this suspends
201
18.7M
    // the DFS traversal till the next ++).
202
22.5M
    
do 18.7M
{
203
22.5M
      CurrentSCC.push_back(SCCNodeStack.back());
204
22.5M
      SCCNodeStack.pop_back();
205
22.5M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
22.5M
    } while (CurrentSCC.back() != visitingN);
207
18.7M
    return;
208
18.7M
  }
209
22.2M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::GetNextSCC()
Line
Count
Source
174
4.68k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
4.68k
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
4.70k
  while (!VisitStack.empty()) {
177
2.41k
    DFSVisitChildren();
178
2.41k
179
2.41k
    // Pop the leaf on top of the VisitStack.
180
2.41k
    NodeRef visitingN = VisitStack.back().Node;
181
2.41k
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
2.41k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
2.41k
    VisitStack.pop_back();
184
2.41k
185
2.41k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
2.41k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum125
)
187
16
      VisitStack.back().MinVisited = minVisitNum;
188
2.41k
189
2.41k
#if 0 // Enable if needed when debugging.
190
2.41k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
2.41k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
2.41k
          nodeVisitNumbers[visitingN] << "\n";
193
2.41k
#endif
194
2.41k
195
2.41k
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
20
      continue;
197
2.39k
198
2.39k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
2.39k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
2.39k
    // reset their minVisit values, and return (this suspends
201
2.39k
    // the DFS traversal till the next ++).
202
2.41k
    
do 2.39k
{
203
2.41k
      CurrentSCC.push_back(SCCNodeStack.back());
204
2.41k
      SCCNodeStack.pop_back();
205
2.41k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
2.41k
    } while (CurrentSCC.back() != visitingN);
207
2.39k
    return;
208
2.39k
  }
209
4.68k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::GetNextSCC()
Line
Count
Source
174
18.1k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
18.1k
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
30.5k
  while (!VisitStack.empty()) {
177
29.8k
    DFSVisitChildren();
178
29.8k
179
29.8k
    // Pop the leaf on top of the VisitStack.
180
29.8k
    NodeRef visitingN = VisitStack.back().Node;
181
29.8k
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
29.8k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
29.8k
    VisitStack.pop_back();
184
29.8k
185
29.8k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
29.8k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum29.0k
)
187
8.51k
      VisitStack.back().MinVisited = minVisitNum;
188
29.8k
189
29.8k
#if 0 // Enable if needed when debugging.
190
29.8k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
29.8k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
29.8k
          nodeVisitNumbers[visitingN] << "\n";
193
29.8k
#endif
194
29.8k
195
29.8k
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
12.4k
      continue;
197
17.3k
198
17.3k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
17.3k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
17.3k
    // reset their minVisit values, and return (this suspends
201
17.3k
    // the DFS traversal till the next ++).
202
29.8k
    
do 17.3k
{
203
29.8k
      CurrentSCC.push_back(SCCNodeStack.back());
204
29.8k
      SCCNodeStack.pop_back();
205
29.8k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
29.8k
    } while (CurrentSCC.back() != visitingN);
207
17.3k
    return;
208
17.3k
  }
209
18.1k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::GetNextSCC()
Line
Count
Source
174
17.3M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
17.3M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
21.0M
  while (!VisitStack.empty()) {
177
18.3M
    DFSVisitChildren();
178
18.3M
179
18.3M
    // Pop the leaf on top of the VisitStack.
180
18.3M
    NodeRef visitingN = VisitStack.back().Node;
181
18.3M
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
18.3M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
18.3M
    VisitStack.pop_back();
184
18.3M
185
18.3M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
18.3M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum15.5M
)
187
2.33M
      VisitStack.back().MinVisited = minVisitNum;
188
18.3M
189
18.3M
#if 0 // Enable if needed when debugging.
190
18.3M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
18.3M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
18.3M
          nodeVisitNumbers[visitingN] << "\n";
193
18.3M
#endif
194
18.3M
195
18.3M
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
3.73M
      continue;
197
14.5M
198
14.5M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
14.5M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
14.5M
    // reset their minVisit values, and return (this suspends
201
14.5M
    // the DFS traversal till the next ++).
202
18.3M
    
do 14.5M
{
203
18.3M
      CurrentSCC.push_back(SCCNodeStack.back());
204
18.3M
      SCCNodeStack.pop_back();
205
18.3M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
18.3M
    } while (CurrentSCC.back() != visitingN);
207
14.5M
    return;
208
14.5M
  }
209
17.3M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::GetNextSCC()
Line
Count
Source
174
3.65M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
3.65M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
3.65M
  while (!VisitStack.empty()) {
177
3.56M
    DFSVisitChildren();
178
3.56M
179
3.56M
    // Pop the leaf on top of the VisitStack.
180
3.56M
    NodeRef visitingN = VisitStack.back().Node;
181
3.56M
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
3.56M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
3.56M
    VisitStack.pop_back();
184
3.56M
185
3.56M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
3.56M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum3.46M
)
187
1.48k
      VisitStack.back().MinVisited = minVisitNum;
188
3.56M
189
3.56M
#if 0 // Enable if needed when debugging.
190
3.56M
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
3.56M
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
3.56M
          nodeVisitNumbers[visitingN] << "\n";
193
3.56M
#endif
194
3.56M
195
3.56M
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
3.03k
      continue;
197
3.55M
198
3.55M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
3.55M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
3.55M
    // reset their minVisit values, and return (this suspends
201
3.55M
    // the DFS traversal till the next ++).
202
3.56M
    
do 3.55M
{
203
3.56M
      CurrentSCC.push_back(SCCNodeStack.back());
204
3.56M
      SCCNodeStack.pop_back();
205
3.56M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
3.56M
    } while (CurrentSCC.back() != visitingN);
207
3.55M
    return;
208
3.55M
  }
209
3.65M
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> >::GetNextSCC()
Line
Count
Source
174
20
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
20
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
22
  while (!VisitStack.empty()) {
177
19
    DFSVisitChildren();
178
19
179
19
    // Pop the leaf on top of the VisitStack.
180
19
    NodeRef visitingN = VisitStack.back().Node;
181
19
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
19
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
19
    VisitStack.pop_back();
184
19
185
19
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
19
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum16
)
187
0
      VisitStack.back().MinVisited = minVisitNum;
188
19
189
19
#if 0 // Enable if needed when debugging.
190
19
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
19
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
19
          nodeVisitNumbers[visitingN] << "\n";
193
19
#endif
194
19
195
19
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
2
      continue;
197
17
198
17
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
17
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
17
    // reset their minVisit values, and return (this suspends
201
17
    // the DFS traversal till the next ++).
202
19
    
do 17
{
203
19
      CurrentSCC.push_back(SCCNodeStack.back());
204
19
      SCCNodeStack.pop_back();
205
19
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
19
    } while (CurrentSCC.back() != visitingN);
207
17
    return;
208
17
  }
209
20
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::GetNextSCC()
Line
Count
Source
174
18
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
18
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
19
  while (!VisitStack.empty()) {
177
15
    DFSVisitChildren();
178
15
179
15
    // Pop the leaf on top of the VisitStack.
180
15
    NodeRef visitingN = VisitStack.back().Node;
181
15
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
15
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
15
    VisitStack.pop_back();
184
15
185
15
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
15
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum11
)
187
0
      VisitStack.back().MinVisited = minVisitNum;
188
15
189
15
#if 0 // Enable if needed when debugging.
190
15
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
15
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
15
          nodeVisitNumbers[visitingN] << "\n";
193
15
#endif
194
15
195
15
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
1
      continue;
197
14
198
14
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
14
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
14
    // reset their minVisit values, and return (this suspends
201
14
    // the DFS traversal till the next ++).
202
15
    
do 14
{
203
15
      CurrentSCC.push_back(SCCNodeStack.back());
204
15
      SCCNodeStack.pop_back();
205
15
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
15
    } while (CurrentSCC.back() != visitingN);
207
14
    return;
208
14
  }
209
18
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::GetNextSCC()
Line
Count
Source
174
1.22M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
1.22M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
1.22M
  while (!VisitStack.empty()) {
177
614k
    DFSVisitChildren();
178
614k
179
614k
    // Pop the leaf on top of the VisitStack.
180
614k
    NodeRef visitingN = VisitStack.back().Node;
181
614k
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
614k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
614k
    VisitStack.pop_back();
184
614k
185
614k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
614k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum637
)
187
2
      VisitStack.back().MinVisited = minVisitNum;
188
614k
189
614k
#if 0 // Enable if needed when debugging.
190
614k
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
614k
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
614k
          nodeVisitNumbers[visitingN] << "\n";
193
614k
#endif
194
614k
195
614k
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
29
      continue;
197
614k
198
614k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
614k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
614k
    // reset their minVisit values, and return (this suspends
201
614k
    // the DFS traversal till the next ++).
202
614k
    
do 614k
{
203
614k
      CurrentSCC.push_back(SCCNodeStack.back());
204
614k
      SCCNodeStack.pop_back();
205
614k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
614k
    } while (CurrentSCC.back() != visitingN);
207
614k
    return;
208
614k
  }
209
1.22M
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::GetNextSCC()
210
211
template <class GraphT, class GT>
212
6
bool scc_iterator<GraphT, GT>::hasLoop() const {
213
6
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
214
6
    if (CurrentSCC.size() > 1)
215
2
      return true;
216
4
    NodeRef N = CurrentSCC.front();
217
9
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
218
5
         ++CI)
219
5
      if (*CI == N)
220
0
        return true;
221
4
    return false;
222
4
  }
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> >::hasLoop() const
Line
Count
Source
212
6
bool scc_iterator<GraphT, GT>::hasLoop() const {
213
6
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
214
6
    if (CurrentSCC.size() > 1)
215
2
      return true;
216
4
    NodeRef N = CurrentSCC.front();
217
9
    for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
218
5
         ++CI)
219
5
      if (*CI == N)
220
0
        return true;
221
4
    return false;
222
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
223
224
/// Construct the begin iterator for a deduced graph type T.
225
3.46M
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
3.46M
  return scc_iterator<T>::begin(G);
227
3.46M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> > llvm::scc_begin<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
225
2.28k
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
2.28k
  return scc_iterator<T>::begin(G);
227
2.28k
}
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
225
735
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
735
  return scc_iterator<T>::begin(G);
227
735
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> > llvm::scc_begin<llvm::Function const*>(llvm::Function const* const&)
Line
Count
Source
225
2.75M
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
2.75M
  return scc_iterator<T>::begin(G);
227
2.75M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> > llvm::scc_begin<llvm::CallGraph*>(llvm::CallGraph* const&)
Line
Count
Source
225
95.6k
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
95.6k
  return scc_iterator<T>::begin(G);
227
95.6k
}
llvm::scc_iterator<llvm::CallGraph const*, llvm::GraphTraits<llvm::CallGraph const*> > llvm::scc_begin<llvm::CallGraph const*>(llvm::CallGraph const* const&)
Line
Count
Source
225
3
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
3
  return scc_iterator<T>::begin(G);
227
3
}
llvm::scc_iterator<llvm::ModuleSummaryIndex*, llvm::GraphTraits<llvm::ModuleSummaryIndex*> > llvm::scc_begin<llvm::ModuleSummaryIndex*>(llvm::ModuleSummaryIndex* const&)
Line
Count
Source
225
4
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
4
  return scc_iterator<T>::begin(G);
227
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
225
613k
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
613k
  return scc_iterator<T>::begin(G);
227
613k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> > llvm::scc_begin<llvm::Function*>(llvm::Function* const&)
228
229
/// Construct the end iterator for a deduced graph type T.
230
template <class T> scc_iterator<T> scc_end(const T &G) {
231
  return scc_iterator<T>::end(G);
232
}
233
234
} // end namespace llvm
235
236
#endif // LLVM_ADT_SCCITERATOR_H