Coverage Report

Created: 2019-03-22 08:08

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/GraphTraits.h
Line
Count
Source
1
//===- llvm/ADT/GraphTraits.h - Graph traits template -----------*- 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
//
9
// This file defines the little GraphTraits<X> template class that should be
10
// specialized by classes that want to be iteratable by generic graph iterators.
11
//
12
// This file also defines the marker class Inverse that is used to iterate over
13
// graphs in a graph defined, inverse ordering...
14
//
15
//===----------------------------------------------------------------------===//
16
17
#ifndef LLVM_ADT_GRAPHTRAITS_H
18
#define LLVM_ADT_GRAPHTRAITS_H
19
20
#include "llvm/ADT/iterator_range.h"
21
22
namespace llvm {
23
24
// GraphTraits - This class should be specialized by different graph types...
25
// which is why the default version is empty.
26
//
27
// This template evolved from supporting `BasicBlock` to also later supporting
28
// more complex types (e.g. CFG and DomTree).
29
//
30
// GraphTraits can be used to create a view over a graph interpreting it
31
// differently without requiring a copy of the original graph. This could
32
// be achieved by carrying more data in NodeRef. See LoopBodyTraits for one
33
// example.
34
template<class GraphType>
35
struct GraphTraits {
36
  // Elements to provide:
37
38
  // typedef NodeRef           - Type of Node token in the graph, which should
39
  //                             be cheap to copy.
40
  // typedef ChildIteratorType - Type used to iterate over children in graph,
41
  //                             dereference to a NodeRef.
42
43
  // static NodeRef getEntryNode(const GraphType &)
44
  //    Return the entry node of the graph
45
46
  // static ChildIteratorType child_begin(NodeRef)
47
  // static ChildIteratorType child_end  (NodeRef)
48
  //    Return iterators that point to the beginning and ending of the child
49
  //    node list for the specified node.
50
51
  // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
52
  // static nodes_iterator nodes_begin(GraphType *G)
53
  // static nodes_iterator nodes_end  (GraphType *G)
54
  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
55
56
  // typedef EdgeRef           - Type of Edge token in the graph, which should
57
  //                             be cheap to copy.
58
  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
59
  //                             graph, dereference to a EdgeRef.
60
61
  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
62
  // static ChildEdgeIteratorType child_edge_end(NodeRef)
63
  //     Return iterators that point to the beginning and ending of the
64
  //     edge list for the given callgraph node.
65
  //
66
  // static NodeRef edge_dest(EdgeRef)
67
  //     Return the destination node of an edge.
68
69
  // static unsigned       size       (GraphType *G)
70
  //    Return total number of nodes in the graph
71
72
  // If anyone tries to use this class without having an appropriate
73
  // specialization, make an error.  If you get this error, it's because you
74
  // need to include the appropriate specialization of GraphTraits<> for your
75
  // graph, or you need to define it for a new graph type. Either that or
76
  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
77
  // file #include'd.
78
  using NodeRef = typename GraphType::UnknownGraphTypeError;
79
};
80
81
// Inverse - This class is used as a little marker class to tell the graph
82
// iterator to iterate over the graph in a graph defined "Inverse" ordering.
83
// Not all graphs define an inverse ordering, and if they do, it depends on
84
// the graph exactly what that is.  Here's an example of usage with the
85
// df_iterator:
86
//
87
// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
88
// for (; I != E; ++I) { ... }
89
//
90
// Which is equivalent to:
91
// df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
92
// for (; I != E; ++I) { ... }
93
//
94
template <class GraphType>
95
struct Inverse {
96
  const GraphType &Graph;
97
98
292k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::MachineBasicBlock const*>::Inverse(llvm::MachineBasicBlock const* const&)
Line
Count
Source
98
289k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::BasicBlock*>::Inverse(llvm::BasicBlock* const&)
Line
Count
Source
98
1.95k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::BasicBlock const*>::Inverse(llvm::BasicBlock const* const&)
Line
Count
Source
98
638
  inline Inverse(const GraphType &G) : Graph(G) {}
99
};
100
101
// Provide a partial specialization of GraphTraits so that the inverse of an
102
// inverse falls back to the original graph.
103
template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
104
105
// Provide iterator ranges for the graph traits nodes and children
106
template <class GraphType>
107
iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
108
2.01M
nodes(const GraphType &G) {
109
2.01M
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
110
2.01M
                    GraphTraits<GraphType>::nodes_end(G));
111
2.01M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineFunction*>::nodes_iterator> llvm::nodes<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
108
1.43M
nodes(const GraphType &G) {
109
1.43M
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
110
1.43M
                    GraphTraits<GraphType>::nodes_end(G));
111
1.43M
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::BlockFrequencyInfo*>::nodes_iterator> llvm::nodes<llvm::BlockFrequencyInfo*>(llvm::BlockFrequencyInfo* const&)
llvm::iterator_range<llvm::GraphTraits<llvm::Function const*>::nodes_iterator> llvm::nodes<llvm::Function const*>(llvm::Function const* const&)
Line
Count
Source
108
3
nodes(const GraphType &G) {
109
3
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
110
3
                    GraphTraits<GraphType>::nodes_end(G));
111
3
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::CallGraph*>::nodes_iterator> llvm::nodes<llvm::CallGraph*>(llvm::CallGraph* const&)
llvm::iterator_range<llvm::GraphTraits<llvm::DominatorTree*>::nodes_iterator> llvm::nodes<llvm::DominatorTree*>(llvm::DominatorTree* const&)
Line
Count
Source
108
327
nodes(const GraphType &G) {
109
327
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
110
327
                    GraphTraits<GraphType>::nodes_end(G));
111
327
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::PostDominatorTree*>::nodes_iterator> llvm::nodes<llvm::PostDominatorTree*>(llvm::PostDominatorTree* const&)
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::RegionInfo*>::nodes_iterator> llvm::nodes<llvm::RegionInfo*>(llvm::RegionInfo* const&)
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::MachineBlockFrequencyInfo*>::nodes_iterator> llvm::nodes<llvm::MachineBlockFrequencyInfo*>(llvm::MachineBlockFrequencyInfo* const&)
llvm::iterator_range<llvm::GraphTraits<llvm::Function*>::nodes_iterator> llvm::nodes<llvm::Function*>(llvm::Function* const&)
Line
Count
Source
108
578k
nodes(const GraphType &G) {
109
578k
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
110
578k
                    GraphTraits<GraphType>::nodes_end(G));
111
578k
}
Unexecuted instantiation: PGOInstrumentation.cpp:llvm::iterator_range<llvm::GraphTraits<(anonymous namespace)::PGOUseFunc*>::nodes_iterator> llvm::nodes<(anonymous namespace)::PGOUseFunc*>((anonymous namespace)::PGOUseFunc* const&)
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::slpvectorizer::BoUpSLP*>::nodes_iterator> llvm::nodes<llvm::slpvectorizer::BoUpSLP*>(llvm::slpvectorizer::BoUpSLP* const&)
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::VPRegionBlock*>::nodes_iterator> llvm::nodes<llvm::VPRegionBlock*>(llvm::VPRegionBlock* const&)
llvm::iterator_range<llvm::GraphTraits<polly::ScopDetectionWrapperPass*>::nodes_iterator> llvm::nodes<polly::ScopDetectionWrapperPass*>(polly::ScopDetectionWrapperPass* const&)
Line
Count
Source
108
1
nodes(const GraphType &G) {
109
1
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
110
1
                    GraphTraits<GraphType>::nodes_end(G));
111
1
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<clang::CFG*>::nodes_iterator> llvm::nodes<clang::CFG*>(clang::CFG* const&)
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<clang::CallGraph const*>::nodes_iterator> llvm::nodes<clang::CallGraph const*>(clang::CallGraph const* const&)
112
template <class GraphType>
113
iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
114
inverse_nodes(const GraphType &G) {
115
  return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
116
                    GraphTraits<Inverse<GraphType>>::nodes_end(G));
117
}
118
119
template <class GraphType>
120
iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
121
295M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
295M
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
295M
                    GraphTraits<GraphType>::child_end(G));
124
295M
}
llvm::iterator_range<llvm::GraphTraits<llvm::BasicBlock const*>::ChildIteratorType> llvm::children<llvm::BasicBlock const*>(llvm::GraphTraits<llvm::BasicBlock const*>::NodeRef const&)
Line
Count
Source
121
712k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
712k
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
712k
                    GraphTraits<GraphType>::child_end(G));
124
712k
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::Inverse<llvm::MachineBasicBlock*> > >::ChildIteratorType> llvm::children<llvm::Inverse<llvm::Inverse<llvm::MachineBasicBlock*> > >(llvm::GraphTraits<llvm::Inverse<llvm::Inverse<llvm::MachineBasicBlock*> > >::NodeRef const&)
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::ChildIteratorType> llvm::children<llvm::Inverse<llvm::MachineBasicBlock*> >(llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::NodeRef const&)
Line
Count
Source
121
11.8M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
11.8M
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
11.8M
                    GraphTraits<GraphType>::child_end(G));
124
11.8M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::ChildIteratorType> llvm::children<llvm::Inverse<llvm::BasicBlock*> >(llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::NodeRef const&)
Line
Count
Source
121
89.4M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
89.4M
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
89.4M
                    GraphTraits<GraphType>::child_end(G));
124
89.4M
}
llvm::iterator_range<llvm::GraphTraits<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*>::ChildIteratorType> llvm::children<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*>(llvm::GraphTraits<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*>::NodeRef const&)
Line
Count
Source
121
51.7k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
51.7k
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
51.7k
                    GraphTraits<GraphType>::child_end(G));
124
51.7k
}
llvm::iterator_range<llvm::GraphTraits<llvm::DomTreeNodeBase<llvm::BasicBlock>*>::ChildIteratorType> llvm::children<llvm::DomTreeNodeBase<llvm::BasicBlock>*>(llvm::GraphTraits<llvm::DomTreeNodeBase<llvm::BasicBlock>*>::NodeRef const&)
Line
Count
Source
121
473k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
473k
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
473k
                    GraphTraits<GraphType>::child_end(G));
124
473k
}
llvm::iterator_range<llvm::GraphTraits<llvm::BasicBlock*>::ChildIteratorType> llvm::children<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef const&)
Line
Count
Source
121
164M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
164M
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
164M
                    GraphTraits<GraphType>::child_end(G));
124
164M
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, false> const*, llvm::BasicBlock*> >::ChildIteratorType> llvm::children<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, false> const*, llvm::BasicBlock*> >(llvm::GraphTraits<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, false> const*, llvm::BasicBlock*> >::NodeRef const&)
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, true> const*, llvm::Inverse<llvm::BasicBlock*> > >::ChildIteratorType> llvm::children<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, true> const*, llvm::Inverse<llvm::BasicBlock*> > >(llvm::GraphTraits<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, true> const*, llvm::Inverse<llvm::BasicBlock*> > >::NodeRef const&)
llvm::iterator_range<llvm::GraphTraits<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, false> const*, llvm::Inverse<llvm::BasicBlock*> > >::ChildIteratorType> llvm::children<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, false> const*, llvm::Inverse<llvm::BasicBlock*> > >(llvm::GraphTraits<std::__1::pair<llvm::GraphDiff<llvm::BasicBlock*, false> const*, llvm::Inverse<llvm::BasicBlock*> > >::NodeRef const&)
Line
Count
Source
121
10.2k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
10.2k
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
10.2k
                    GraphTraits<GraphType>::child_end(G));
124
10.2k
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineBasicBlock const*>::ChildIteratorType> llvm::children<llvm::MachineBasicBlock const*>(llvm::GraphTraits<llvm::MachineBasicBlock const*>::NodeRef const&)
Line
Count
Source
121
4.65M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
4.65M
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
4.65M
                    GraphTraits<GraphType>::child_end(G));
124
4.65M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineBasicBlock*>::ChildIteratorType> llvm::children<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef const&)
Line
Count
Source
121
23.5M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
23.5M
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
23.5M
                    GraphTraits<GraphType>::child_end(G));
124
23.5M
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::Inverse<llvm::BasicBlock*> > >::ChildIteratorType> llvm::children<llvm::Inverse<llvm::Inverse<llvm::BasicBlock*> > >(llvm::GraphTraits<llvm::Inverse<llvm::Inverse<llvm::BasicBlock*> > >::NodeRef const&)
llvm::iterator_range<llvm::GraphTraits<llvm::VPBlockBase*>::ChildIteratorType> llvm::children<llvm::VPBlockBase*>(llvm::GraphTraits<llvm::VPBlockBase*>::NodeRef const&)
Line
Count
Source
121
118
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
118
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
118
                    GraphTraits<GraphType>::child_end(G));
124
118
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::VPBlockBase*> >::ChildIteratorType> llvm::children<llvm::Inverse<llvm::VPBlockBase*> >(llvm::GraphTraits<llvm::Inverse<llvm::VPBlockBase*> >::NodeRef const&)
Line
Count
Source
121
92
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
92
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
92
                    GraphTraits<GraphType>::child_end(G));
124
92
}
llvm::iterator_range<llvm::GraphTraits<clang::CFGBlock*>::ChildIteratorType> llvm::children<clang::CFGBlock*>(llvm::GraphTraits<clang::CFGBlock*>::NodeRef const&)
Line
Count
Source
121
52
children(const typename GraphTraits<GraphType>::NodeRef &G) {
122
52
  return make_range(GraphTraits<GraphType>::child_begin(G),
123
52
                    GraphTraits<GraphType>::child_end(G));
124
52
}
125
126
template <class GraphType>
127
iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
128
23.0M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
129
23.0M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
130
23.0M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
131
23.0M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::ChildIteratorType> llvm::inverse_children<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef const&)
Line
Count
Source
128
16.7M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
129
16.7M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
130
16.7M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
131
16.7M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::ChildIteratorType> llvm::inverse_children<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef const&)
Line
Count
Source
128
6.35M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
129
6.35M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
130
6.35M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
131
6.35M
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::VPBlockBase*> >::ChildIteratorType> llvm::inverse_children<llvm::VPBlockBase*>(llvm::GraphTraits<llvm::VPBlockBase*>::NodeRef const&)
132
133
template <class GraphType>
134
iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
135
28
children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
136
28
  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
137
28
                    GraphTraits<GraphType>::child_edge_end(G));
138
28
}
llvm::iterator_range<llvm::GraphTraits<llvm::CallGraph const*>::ChildEdgeIteratorType> llvm::children_edges<llvm::CallGraph const*>(llvm::GraphTraits<llvm::CallGraph const*>::NodeRef const&)
Line
Count
Source
135
19
children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
136
19
  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
137
19
                    GraphTraits<GraphType>::child_edge_end(G));
138
19
}
llvm::iterator_range<llvm::GraphTraits<llvm::ModuleSummaryIndex*>::ChildEdgeIteratorType> llvm::children_edges<llvm::ModuleSummaryIndex*>(llvm::GraphTraits<llvm::ModuleSummaryIndex*>::NodeRef const&)
Line
Count
Source
135
9
children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
136
9
  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
137
9
                    GraphTraits<GraphType>::child_edge_end(G));
138
9
}
139
140
} // end namespace llvm
141
142
#endif // LLVM_ADT_GRAPHTRAITS_H