Coverage Report

Created: 2019-07-24 05: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
// 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
19.9M
        : 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.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
57
27.6k
        : 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
15.6M
        : 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.60M
        : 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
624k
        : 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.25M
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
3.25M
    DFSVisitOne(entryN);
94
3.25M
    GetNextSCC();
95
3.25M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::scc_iterator(llvm::MachineBasicBlock*)
Line
Count
Source
92
2.29k
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
2.29k
    DFSVisitOne(entryN);
94
2.29k
    GetNextSCC();
95
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
92
717
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
717
    DFSVisitOne(entryN);
94
717
    GetNextSCC();
95
717
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::scc_iterator(llvm::BasicBlock const*)
Line
Count
Source
92
2.52M
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
2.52M
    DFSVisitOne(entryN);
94
2.52M
    GetNextSCC();
95
2.52M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::scc_iterator(llvm::CallGraphNode*)
Line
Count
Source
92
98.6k
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
98.6k
    DFSVisitOne(entryN);
94
98.6k
    GetNextSCC();
95
98.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
623k
  scc_iterator(NodeRef entryN) : visitNum(0) {
93
623k
    DFSVisitOne(entryN);
94
623k
    GetNextSCC();
95
623k
  }
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.25M
  static scc_iterator begin(const GraphT &G) {
102
3.25M
    return scc_iterator(GT::getEntryNode(G));
103
3.25M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::begin(llvm::MachineFunction* const&)
Line
Count
Source
101
2.29k
  static scc_iterator begin(const GraphT &G) {
102
2.29k
    return scc_iterator(GT::getEntryNode(G));
103
2.29k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::begin(llvm::bfi_detail::IrreducibleGraph const&)
Line
Count
Source
101
717
  static scc_iterator begin(const GraphT &G) {
102
717
    return scc_iterator(GT::getEntryNode(G));
103
717
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::begin(llvm::Function const* const&)
Line
Count
Source
101
2.52M
  static scc_iterator begin(const GraphT &G) {
102
2.52M
    return scc_iterator(GT::getEntryNode(G));
103
2.52M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::begin(llvm::CallGraph* const&)
Line
Count
Source
101
98.5k
  static scc_iterator begin(const GraphT &G) {
102
98.5k
    return scc_iterator(GT::getEntryNode(G));
103
98.5k
  }
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
623k
  static scc_iterator begin(const GraphT &G) {
102
623k
    return scc_iterator(GT::getEntryNode(G));
103
623k
  }
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
20.0M
  bool isAtEnd() const {
109
20.0M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
20.0M
    return CurrentSCC.empty();
111
20.0M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::isAtEnd() const
Line
Count
Source
108
4.69k
  bool isAtEnd() const {
109
4.69k
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
4.69k
    return CurrentSCC.empty();
111
4.69k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::isAtEnd() const
Line
Count
Source
108
17.0k
  bool isAtEnd() const {
109
17.0k
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
17.0k
    return CurrentSCC.empty();
111
17.0k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::isAtEnd() const
Line
Count
Source
108
15.0M
  bool isAtEnd() const {
109
15.0M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
15.0M
    return CurrentSCC.empty();
111
15.0M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::isAtEnd() const
Line
Count
Source
108
3.70M
  bool isAtEnd() const {
109
3.70M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
3.70M
    return CurrentSCC.empty();
111
3.70M
  }
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.24M
  bool isAtEnd() const {
109
1.24M
    assert(!CurrentSCC.empty() || VisitStack.empty());
110
1.24M
    return CurrentSCC.empty();
111
1.24M
  }
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
16.8M
  scc_iterator &operator++() {
118
16.8M
    GetNextSCC();
119
16.8M
    return *this;
120
16.8M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator++()
Line
Count
Source
117
2.40k
  scc_iterator &operator++() {
118
2.40k
    GetNextSCC();
119
2.40k
    return *this;
120
2.40k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator++()
Line
Count
Source
117
16.3k
  scc_iterator &operator++() {
118
16.3k
    GetNextSCC();
119
16.3k
    return *this;
120
16.3k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator++()
Line
Count
Source
117
12.5M
  scc_iterator &operator++() {
118
12.5M
    GetNextSCC();
119
12.5M
    return *this;
120
12.5M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator++()
Line
Count
Source
117
3.60M
  scc_iterator &operator++() {
118
3.60M
    GetNextSCC();
119
3.60M
    return *this;
120
3.60M
  }
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
624k
  scc_iterator &operator++() {
118
624k
    GetNextSCC();
119
624k
    return *this;
120
624k
  }
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::operator++()
121
122
17.2M
  reference operator*() const {
123
17.2M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
17.2M
    return CurrentSCC;
125
17.2M
  }
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::operator*() const
Line
Count
Source
122
2.40k
  reference operator*() const {
123
2.40k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
2.40k
    return CurrentSCC;
125
2.40k
  }
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::operator*() const
Line
Count
Source
122
17.1k
  reference operator*() const {
123
17.1k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
17.1k
    return CurrentSCC;
125
17.1k
  }
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::operator*() const
Line
Count
Source
122
12.5M
  reference operator*() const {
123
12.5M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
12.5M
    return CurrentSCC;
125
12.5M
  }
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::operator*() const
Line
Count
Source
122
4.06M
  reference operator*() const {
123
4.06M
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
4.06M
    return CurrentSCC;
125
4.06M
  }
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
624k
  reference operator*() const {
123
624k
    assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
124
624k
    return CurrentSCC;
125
624k
  }
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.83k
  void ReplaceNode(NodeRef Old, NodeRef New) {
136
1.83k
    assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
137
1.83k
    nodeVisitNumbers[New] = nodeVisitNumbers[Old];
138
1.83k
    nodeVisitNumbers.erase(Old);
139
1.83k
  }
140
};
141
142
template <class GraphT, class GT>
143
19.9M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
19.9M
  ++visitNum;
145
19.9M
  nodeVisitNumbers[N] = visitNum;
146
19.9M
  SCCNodeStack.push_back(N);
147
19.9M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitOne(llvm::MachineBasicBlock*)
Line
Count
Source
143
2.42k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
2.42k
  ++visitNum;
145
2.42k
  nodeVisitNumbers[N] = visitNum;
146
2.42k
  SCCNodeStack.push_back(N);
147
2.42k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitOne(llvm::bfi_detail::IrreducibleGraph::IrrNode const*)
Line
Count
Source
143
27.6k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
27.6k
  ++visitNum;
145
27.6k
  nodeVisitNumbers[N] = visitNum;
146
27.6k
  SCCNodeStack.push_back(N);
147
27.6k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitOne(llvm::BasicBlock const*)
Line
Count
Source
143
15.6M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
15.6M
  ++visitNum;
145
15.6M
  nodeVisitNumbers[N] = visitNum;
146
15.6M
  SCCNodeStack.push_back(N);
147
15.6M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitOne(llvm::CallGraphNode*)
Line
Count
Source
143
3.60M
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
3.60M
  ++visitNum;
145
3.60M
  nodeVisitNumbers[N] = visitNum;
146
3.60M
  SCCNodeStack.push_back(N);
147
3.60M
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
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
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
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
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
FunctionAttrs.cpp:llvm::scc_iterator<(anonymous namespace)::ArgumentGraph*, llvm::GraphTraits<(anonymous namespace)::ArgumentGraph*> >::DFSVisitOne((anonymous namespace)::ArgumentGraphNode*)
Line
Count
Source
143
624k
void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
144
624k
  ++visitNum;
145
624k
  nodeVisitNumbers[N] = visitNum;
146
624k
  SCCNodeStack.push_back(N);
147
624k
  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
148
#if 0 // Enable if needed when debugging.
149
  dbgs() << "TarjanSCC: Node " << N <<
150
        " : visitNum = " << visitNum << "\n";
151
#endif
152
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitOne(llvm::BasicBlock*)
153
154
template <class GraphT, class GT>
155
19.9M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
19.9M
  assert(!VisitStack.empty());
157
54.4M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
34.5M
    // TOS has at least one more child so continue DFS
159
34.5M
    NodeRef childN = *VisitStack.back().NextChild++;
160
34.5M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
34.5M
        nodeVisitNumbers.find(childN);
162
34.5M
    if (Visited == nodeVisitNumbers.end()) {
163
16.6M
      // this node has never been seen.
164
16.6M
      DFSVisitOne(childN);
165
16.6M
      continue;
166
16.6M
    }
167
17.8M
168
17.8M
    unsigned childNum = Visited->second;
169
17.8M
    if (VisitStack.back().MinVisited > childNum)
170
1.26M
      VisitStack.back().MinVisited = childNum;
171
17.8M
  }
172
19.9M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::DFSVisitChildren()
Line
Count
Source
155
2.42k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
2.42k
  assert(!VisitStack.empty());
157
2.61k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
192
    // TOS has at least one more child so continue DFS
159
192
    NodeRef childN = *VisitStack.back().NextChild++;
160
192
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
192
        nodeVisitNumbers.find(childN);
162
192
    if (Visited == nodeVisitNumbers.end()) {
163
129
      // this node has never been seen.
164
129
      DFSVisitOne(childN);
165
129
      continue;
166
129
    }
167
63
168
63
    unsigned childNum = Visited->second;
169
63
    if (VisitStack.back().MinVisited > childNum)
170
4
      VisitStack.back().MinVisited = childNum;
171
63
  }
172
2.42k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::DFSVisitChildren()
Line
Count
Source
155
27.6k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
27.6k
  assert(!VisitStack.empty());
157
69.6k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
41.9k
    // TOS has at least one more child so continue DFS
159
41.9k
    NodeRef childN = *VisitStack.back().NextChild++;
160
41.9k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
41.9k
        nodeVisitNumbers.find(childN);
162
41.9k
    if (Visited == nodeVisitNumbers.end()) {
163
26.9k
      // this node has never been seen.
164
26.9k
      DFSVisitOne(childN);
165
26.9k
      continue;
166
26.9k
    }
167
15.0k
168
15.0k
    unsigned childNum = Visited->second;
169
15.0k
    if (VisitStack.back().MinVisited > childNum)
170
3.92k
      VisitStack.back().MinVisited = childNum;
171
15.0k
  }
172
27.6k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::DFSVisitChildren()
Line
Count
Source
155
15.6M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
15.6M
  assert(!VisitStack.empty());
157
35.9M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
20.3M
    // TOS has at least one more child so continue DFS
159
20.3M
    NodeRef childN = *VisitStack.back().NextChild++;
160
20.3M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
20.3M
        nodeVisitNumbers.find(childN);
162
20.3M
    if (Visited == nodeVisitNumbers.end()) {
163
13.1M
      // this node has never been seen.
164
13.1M
      DFSVisitOne(childN);
165
13.1M
      continue;
166
13.1M
    }
167
7.20M
168
7.20M
    unsigned childNum = Visited->second;
169
7.20M
    if (VisitStack.back().MinVisited > childNum)
170
1.25M
      VisitStack.back().MinVisited = childNum;
171
7.20M
  }
172
15.6M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::DFSVisitChildren()
Line
Count
Source
155
3.60M
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
3.60M
  assert(!VisitStack.empty());
157
17.7M
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
14.1M
    // TOS has at least one more child so continue DFS
159
14.1M
    NodeRef childN = *VisitStack.back().NextChild++;
160
14.1M
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
14.1M
        nodeVisitNumbers.find(childN);
162
14.1M
    if (Visited == nodeVisitNumbers.end()) {
163
3.50M
      // this node has never been seen.
164
3.50M
      DFSVisitOne(childN);
165
3.50M
      continue;
166
3.50M
    }
167
10.6M
168
10.6M
    unsigned childNum = Visited->second;
169
10.6M
    if (VisitStack.back().MinVisited > childNum)
170
1.76k
      VisitStack.back().MinVisited = childNum;
171
10.6M
  }
172
3.60M
}
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
624k
void scc_iterator<GraphT, GT>::DFSVisitChildren() {
156
624k
  assert(!VisitStack.empty());
157
626k
  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
158
2.46k
    // TOS has at least one more child so continue DFS
159
2.46k
    NodeRef childN = *VisitStack.back().NextChild++;
160
2.46k
    typename DenseMap<NodeRef, unsigned>::iterator Visited =
161
2.46k
        nodeVisitNumbers.find(childN);
162
2.46k
    if (Visited == nodeVisitNumbers.end()) {
163
681
      // this node has never been seen.
164
681
      DFSVisitOne(childN);
165
681
      continue;
166
681
    }
167
1.78k
168
1.78k
    unsigned childNum = Visited->second;
169
1.78k
    if (VisitStack.back().MinVisited > childNum)
170
27
      VisitStack.back().MinVisited = childNum;
171
1.78k
  }
172
624k
}
Unexecuted instantiation: llvm::scc_iterator<llvm::Function*, llvm::GraphTraits<llvm::Function*> >::DFSVisitChildren()
173
174
20.0M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
20.0M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
23.1M
  while (!VisitStack.empty()) {
177
19.9M
    DFSVisitChildren();
178
19.9M
179
19.9M
    // Pop the leaf on top of the VisitStack.
180
19.9M
    NodeRef visitingN = VisitStack.back().Node;
181
19.9M
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
19.9M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
19.9M
    VisitStack.pop_back();
184
19.9M
185
19.9M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
19.9M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum16.6M
)
187
1.93M
      VisitStack.back().MinVisited = minVisitNum;
188
19.9M
189
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
195
19.9M
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
3.10M
      continue;
197
16.8M
198
16.8M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
16.8M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
16.8M
    // reset their minVisit values, and return (this suspends
201
16.8M
    // the DFS traversal till the next ++).
202
19.9M
    
do 16.8M
{
203
19.9M
      CurrentSCC.push_back(SCCNodeStack.back());
204
19.9M
      SCCNodeStack.pop_back();
205
19.9M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
19.9M
    } while (CurrentSCC.back() != visitingN);
207
16.8M
    return;
208
16.8M
  }
209
20.0M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> >::GetNextSCC()
Line
Count
Source
174
4.69k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
4.69k
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
4.71k
  while (!VisitStack.empty()) {
177
2.42k
    DFSVisitChildren();
178
2.42k
179
2.42k
    // Pop the leaf on top of the VisitStack.
180
2.42k
    NodeRef visitingN = VisitStack.back().Node;
181
2.42k
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
2.42k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
2.42k
    VisitStack.pop_back();
184
2.42k
185
2.42k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
2.42k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum129
)
187
16
      VisitStack.back().MinVisited = minVisitNum;
188
2.42k
189
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
195
2.42k
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
20
      continue;
197
2.40k
198
2.40k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
2.40k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
2.40k
    // reset their minVisit values, and return (this suspends
201
2.40k
    // the DFS traversal till the next ++).
202
2.42k
    
do 2.40k
{
203
2.42k
      CurrentSCC.push_back(SCCNodeStack.back());
204
2.42k
      SCCNodeStack.pop_back();
205
2.42k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
2.42k
    } while (CurrentSCC.back() != visitingN);
207
2.40k
    return;
208
2.40k
  }
209
4.69k
}
llvm::scc_iterator<llvm::bfi_detail::IrreducibleGraph, llvm::GraphTraits<llvm::bfi_detail::IrreducibleGraph> >::GetNextSCC()
Line
Count
Source
174
17.0k
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
17.0k
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
28.3k
  while (!VisitStack.empty()) {
177
27.6k
    DFSVisitChildren();
178
27.6k
179
27.6k
    // Pop the leaf on top of the VisitStack.
180
27.6k
    NodeRef visitingN = VisitStack.back().Node;
181
27.6k
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
27.6k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
27.6k
    VisitStack.pop_back();
184
27.6k
185
27.6k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
27.6k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum26.9k
)
187
7.62k
      VisitStack.back().MinVisited = minVisitNum;
188
27.6k
189
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
195
27.6k
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
11.3k
      continue;
197
16.3k
198
16.3k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
16.3k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
16.3k
    // reset their minVisit values, and return (this suspends
201
16.3k
    // the DFS traversal till the next ++).
202
27.6k
    
do 16.3k
{
203
27.6k
      CurrentSCC.push_back(SCCNodeStack.back());
204
27.6k
      SCCNodeStack.pop_back();
205
27.6k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
27.6k
    } while (CurrentSCC.back() != visitingN);
207
16.3k
    return;
208
16.3k
  }
209
17.0k
}
llvm::scc_iterator<llvm::Function const*, llvm::GraphTraits<llvm::Function const*> >::GetNextSCC()
Line
Count
Source
174
15.0M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
15.0M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
18.1M
  while (!VisitStack.empty()) {
177
15.6M
    DFSVisitChildren();
178
15.6M
179
15.6M
    // Pop the leaf on top of the VisitStack.
180
15.6M
    NodeRef visitingN = VisitStack.back().Node;
181
15.6M
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
15.6M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
15.6M
    VisitStack.pop_back();
184
15.6M
185
15.6M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
15.6M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum13.1M
)
187
1.92M
      VisitStack.back().MinVisited = minVisitNum;
188
15.6M
189
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
195
15.6M
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
3.09M
      continue;
197
12.5M
198
12.5M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
12.5M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
12.5M
    // reset their minVisit values, and return (this suspends
201
12.5M
    // the DFS traversal till the next ++).
202
15.6M
    
do 12.5M
{
203
15.6M
      CurrentSCC.push_back(SCCNodeStack.back());
204
15.6M
      SCCNodeStack.pop_back();
205
15.6M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
15.6M
    } while (CurrentSCC.back() != visitingN);
207
12.5M
    return;
208
12.5M
  }
209
15.0M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> >::GetNextSCC()
Line
Count
Source
174
3.70M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
3.70M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
3.70M
  while (!VisitStack.empty()) {
177
3.60M
    DFSVisitChildren();
178
3.60M
179
3.60M
    // Pop the leaf on top of the VisitStack.
180
3.60M
    NodeRef visitingN = VisitStack.back().Node;
181
3.60M
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
3.60M
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
3.60M
    VisitStack.pop_back();
184
3.60M
185
3.60M
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
3.60M
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum3.50M
)
187
1.49k
      VisitStack.back().MinVisited = minVisitNum;
188
3.60M
189
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
195
3.60M
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
3.06k
      continue;
197
3.60M
198
3.60M
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
3.60M
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
3.60M
    // reset their minVisit values, and return (this suspends
201
3.60M
    // the DFS traversal till the next ++).
202
3.60M
    
do 3.60M
{
203
3.60M
      CurrentSCC.push_back(SCCNodeStack.back());
204
3.60M
      SCCNodeStack.pop_back();
205
3.60M
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
3.60M
    } while (CurrentSCC.back() != visitingN);
207
3.60M
    return;
208
3.60M
  }
209
3.70M
}
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
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
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
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
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.24M
template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
175
1.24M
  CurrentSCC.clear(); // Prepare to compute the next SCC
176
1.24M
  while (!VisitStack.empty()) {
177
624k
    DFSVisitChildren();
178
624k
179
624k
    // Pop the leaf on top of the VisitStack.
180
624k
    NodeRef visitingN = VisitStack.back().Node;
181
624k
    unsigned minVisitNum = VisitStack.back().MinVisited;
182
624k
    assert(VisitStack.back().NextChild == GT::child_end(visitingN));
183
624k
    VisitStack.pop_back();
184
624k
185
624k
    // Propagate MinVisitNum to parent so we can detect the SCC starting node.
186
624k
    if (!VisitStack.empty() && 
VisitStack.back().MinVisited > minVisitNum681
)
187
2
      VisitStack.back().MinVisited = minVisitNum;
188
624k
189
#if 0 // Enable if needed when debugging.
190
    dbgs() << "TarjanSCC: Popped node " << visitingN <<
191
          " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
192
          nodeVisitNumbers[visitingN] << "\n";
193
#endif
194
195
624k
    if (minVisitNum != nodeVisitNumbers[visitingN])
196
29
      continue;
197
624k
198
624k
    // A full SCC is on the SCCNodeStack!  It includes all nodes below
199
624k
    // visitingN on the stack.  Copy those nodes to CurrentSCC,
200
624k
    // reset their minVisit values, and return (this suspends
201
624k
    // the DFS traversal till the next ++).
202
624k
    
do 624k
{
203
624k
      CurrentSCC.push_back(SCCNodeStack.back());
204
624k
      SCCNodeStack.pop_back();
205
624k
      nodeVisitNumbers[CurrentSCC.back()] = ~0U;
206
624k
    } while (CurrentSCC.back() != visitingN);
207
624k
    return;
208
624k
  }
209
1.24M
}
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.25M
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
3.25M
  return scc_iterator<T>::begin(G);
227
3.25M
}
llvm::scc_iterator<llvm::MachineFunction*, llvm::GraphTraits<llvm::MachineFunction*> > llvm::scc_begin<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
225
2.29k
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
2.29k
  return scc_iterator<T>::begin(G);
227
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
225
717
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
717
  return scc_iterator<T>::begin(G);
227
717
}
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.52M
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
2.52M
  return scc_iterator<T>::begin(G);
227
2.52M
}
llvm::scc_iterator<llvm::CallGraph*, llvm::GraphTraits<llvm::CallGraph*> > llvm::scc_begin<llvm::CallGraph*>(llvm::CallGraph* const&)
Line
Count
Source
225
98.5k
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
98.5k
  return scc_iterator<T>::begin(G);
227
98.5k
}
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
623k
template <class T> scc_iterator<T> scc_begin(const T &G) {
226
623k
  return scc_iterator<T>::begin(G);
227
623k
}
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