Coverage Report

Created: 2018-07-12 09:57

/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
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file defines the little GraphTraits<X> template class that should be
11
// specialized by classes that want to be iteratable by generic graph iterators.
12
//
13
// This file also defines the marker class Inverse that is used to iterate over
14
// graphs in a graph defined, inverse ordering...
15
//
16
//===----------------------------------------------------------------------===//
17
18
#ifndef LLVM_ADT_GRAPHTRAITS_H
19
#define LLVM_ADT_GRAPHTRAITS_H
20
21
#include "llvm/ADT/iterator_range.h"
22
23
namespace llvm {
24
25
// GraphTraits - This class should be specialized by different graph types...
26
// which is why the default version is empty.
27
//
28
template<class GraphType>
29
struct GraphTraits {
30
  // Elements to provide:
31
32
  // typedef NodeRef           - Type of Node token in the graph, which should
33
  //                             be cheap to copy.
34
  // typedef ChildIteratorType - Type used to iterate over children in graph,
35
  //                             dereference to a NodeRef.
36
37
  // static NodeRef getEntryNode(const GraphType &)
38
  //    Return the entry node of the graph
39
40
  // static ChildIteratorType child_begin(NodeRef)
41
  // static ChildIteratorType child_end  (NodeRef)
42
  //    Return iterators that point to the beginning and ending of the child
43
  //    node list for the specified node.
44
45
  // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
46
  // static nodes_iterator nodes_begin(GraphType *G)
47
  // static nodes_iterator nodes_end  (GraphType *G)
48
  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
49
50
  // typedef EdgeRef           - Type of Edge token in the graph, which should
51
  //                             be cheap to copy.
52
  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
53
  //                             graph, dereference to a EdgeRef.
54
55
  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
56
  // static ChildEdgeIteratorType child_edge_end(NodeRef)
57
  //     Return iterators that point to the beginning and ending of the
58
  //     edge list for the given callgraph node.
59
  //
60
  // static NodeRef edge_dest(EdgeRef)
61
  //     Return the destination node of an edge.
62
63
  // static unsigned       size       (GraphType *G)
64
  //    Return total number of nodes in the graph
65
66
  // If anyone tries to use this class without having an appropriate
67
  // specialization, make an error.  If you get this error, it's because you
68
  // need to include the appropriate specialization of GraphTraits<> for your
69
  // graph, or you need to define it for a new graph type. Either that or
70
  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
71
  // file #include'd.
72
  using NodeRef = typename GraphType::UnknownGraphTypeError;
73
};
74
75
// Inverse - This class is used as a little marker class to tell the graph
76
// iterator to iterate over the graph in a graph defined "Inverse" ordering.
77
// Not all graphs define an inverse ordering, and if they do, it depends on
78
// the graph exactly what that is.  Here's an example of usage with the
79
// df_iterator:
80
//
81
// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
82
// for (; I != E; ++I) { ... }
83
//
84
// Which is equivalent to:
85
// df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
86
// for (; I != E; ++I) { ... }
87
//
88
template <class GraphType>
89
struct Inverse {
90
  const GraphType &Graph;
91
92
273k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::MachineBasicBlock*>::Inverse(llvm::MachineBasicBlock* const&)
Line
Count
Source
92
38
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::MachineBasicBlock const*>::Inverse(llvm::MachineBasicBlock const* const&)
Line
Count
Source
92
270k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::BasicBlock*>::Inverse(llvm::BasicBlock* const&)
Line
Count
Source
92
1.75k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::BasicBlock const*>::Inverse(llvm::BasicBlock const* const&)
Line
Count
Source
92
612
  inline Inverse(const GraphType &G) : Graph(G) {}
93
};
94
95
// Provide a partial specialization of GraphTraits so that the inverse of an
96
// inverse falls back to the original graph.
97
template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
98
99
// Provide iterator ranges for the graph traits nodes and children
100
template <class GraphType>
101
iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
102
1.89M
nodes(const GraphType &G) {
103
1.89M
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
104
1.89M
                    GraphTraits<GraphType>::nodes_end(G));
105
1.89M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineFunction*>::nodes_iterator> llvm::nodes<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
102
1.36M
nodes(const GraphType &G) {
103
1.36M
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
104
1.36M
                    GraphTraits<GraphType>::nodes_end(G));
105
1.36M
}
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
102
2
nodes(const GraphType &G) {
103
2
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
104
2
                    GraphTraits<GraphType>::nodes_end(G));
105
2
}
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
102
302
nodes(const GraphType &G) {
103
302
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
104
302
                    GraphTraits<GraphType>::nodes_end(G));
105
302
}
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
102
533k
nodes(const GraphType &G) {
103
533k
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
104
533k
                    GraphTraits<GraphType>::nodes_end(G));
105
533k
}
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&)
llvm::iterator_range<llvm::GraphTraits<polly::ScopDetectionWrapperPass*>::nodes_iterator> llvm::nodes<polly::ScopDetectionWrapperPass*>(polly::ScopDetectionWrapperPass* const&)
Line
Count
Source
102
1
nodes(const GraphType &G) {
103
1
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
104
1
                    GraphTraits<GraphType>::nodes_end(G));
105
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&)
106
template <class GraphType>
107
iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
108
inverse_nodes(const GraphType &G) {
109
  return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
110
                    GraphTraits<Inverse<GraphType>>::nodes_end(G));
111
}
112
113
template <class GraphType>
114
iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
115
261M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
261M
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
261M
                    GraphTraits<GraphType>::child_end(G));
118
261M
}
llvm::iterator_range<llvm::GraphTraits<llvm::BasicBlock const*>::ChildIteratorType> llvm::children<llvm::BasicBlock const*>(llvm::GraphTraits<llvm::BasicBlock const*>::NodeRef const&)
Line
Count
Source
115
683k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
683k
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
683k
                    GraphTraits<GraphType>::child_end(G));
118
683k
}
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
115
11.7M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
11.7M
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
11.7M
                    GraphTraits<GraphType>::child_end(G));
118
11.7M
}
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
115
82.2M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
82.2M
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
82.2M
                    GraphTraits<GraphType>::child_end(G));
118
82.2M
}
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
115
54.0k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
54.0k
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
54.0k
                    GraphTraits<GraphType>::child_end(G));
118
54.0k
}
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
115
449k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
449k
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
449k
                    GraphTraits<GraphType>::child_end(G));
118
449k
}
llvm::iterator_range<llvm::GraphTraits<llvm::BasicBlock*>::ChildIteratorType> llvm::children<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef const&)
Line
Count
Source
115
139M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
139M
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
139M
                    GraphTraits<GraphType>::child_end(G));
118
139M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineBasicBlock const*>::ChildIteratorType> llvm::children<llvm::MachineBasicBlock const*>(llvm::GraphTraits<llvm::MachineBasicBlock const*>::NodeRef const&)
Line
Count
Source
115
3.96M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
3.96M
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
3.96M
                    GraphTraits<GraphType>::child_end(G));
118
3.96M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineBasicBlock*>::ChildIteratorType> llvm::children<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef const&)
Line
Count
Source
115
23.2M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
23.2M
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
23.2M
                    GraphTraits<GraphType>::child_end(G));
118
23.2M
}
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<clang::CFGBlock*>::ChildIteratorType> llvm::children<clang::CFGBlock*>(llvm::GraphTraits<clang::CFGBlock*>::NodeRef const&)
Line
Count
Source
115
52
children(const typename GraphTraits<GraphType>::NodeRef &G) {
116
52
  return make_range(GraphTraits<GraphType>::child_begin(G),
117
52
                    GraphTraits<GraphType>::child_end(G));
118
52
}
119
120
template <class GraphType>
121
iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
122
22.7M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
22.7M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
124
22.7M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
125
22.7M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::ChildIteratorType> llvm::inverse_children<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef const&)
Line
Count
Source
122
16.5M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
16.5M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
124
16.5M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
125
16.5M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::ChildIteratorType> llvm::inverse_children<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef const&)
Line
Count
Source
122
6.18M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
6.18M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
124
6.18M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
125
6.18M
}
126
127
template <class GraphType>
128
iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
129
19
children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
130
19
  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
131
19
                    GraphTraits<GraphType>::child_edge_end(G));
132
19
}
133
134
} // end namespace llvm
135
136
#endif // LLVM_ADT_GRAPHTRAITS_H