Coverage Report

Created: 2018-12-11 00:00

/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
// This template evolved from supporting `BasicBlock` to also later supporting
29
// more complex types (e.g. CFG and DomTree).
30
//
31
// GraphTraits can be used to create a view over a graph interpreting it
32
// differently without requiring a copy of the original graph. This could
33
// be achieved by carrying more data in NodeRef. See LoopBodyTraits for one
34
// example.
35
template<class GraphType>
36
struct GraphTraits {
37
  // Elements to provide:
38
39
  // typedef NodeRef           - Type of Node token in the graph, which should
40
  //                             be cheap to copy.
41
  // typedef ChildIteratorType - Type used to iterate over children in graph,
42
  //                             dereference to a NodeRef.
43
44
  // static NodeRef getEntryNode(const GraphType &)
45
  //    Return the entry node of the graph
46
47
  // static ChildIteratorType child_begin(NodeRef)
48
  // static ChildIteratorType child_end  (NodeRef)
49
  //    Return iterators that point to the beginning and ending of the child
50
  //    node list for the specified node.
51
52
  // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
53
  // static nodes_iterator nodes_begin(GraphType *G)
54
  // static nodes_iterator nodes_end  (GraphType *G)
55
  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
56
57
  // typedef EdgeRef           - Type of Edge token in the graph, which should
58
  //                             be cheap to copy.
59
  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
60
  //                             graph, dereference to a EdgeRef.
61
62
  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
63
  // static ChildEdgeIteratorType child_edge_end(NodeRef)
64
  //     Return iterators that point to the beginning and ending of the
65
  //     edge list for the given callgraph node.
66
  //
67
  // static NodeRef edge_dest(EdgeRef)
68
  //     Return the destination node of an edge.
69
70
  // static unsigned       size       (GraphType *G)
71
  //    Return total number of nodes in the graph
72
73
  // If anyone tries to use this class without having an appropriate
74
  // specialization, make an error.  If you get this error, it's because you
75
  // need to include the appropriate specialization of GraphTraits<> for your
76
  // graph, or you need to define it for a new graph type. Either that or
77
  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
78
  // file #include'd.
79
  using NodeRef = typename GraphType::UnknownGraphTypeError;
80
};
81
82
// Inverse - This class is used as a little marker class to tell the graph
83
// iterator to iterate over the graph in a graph defined "Inverse" ordering.
84
// Not all graphs define an inverse ordering, and if they do, it depends on
85
// the graph exactly what that is.  Here's an example of usage with the
86
// df_iterator:
87
//
88
// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
89
// for (; I != E; ++I) { ... }
90
//
91
// Which is equivalent to:
92
// df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
93
// for (; I != E; ++I) { ... }
94
//
95
template <class GraphType>
96
struct Inverse {
97
  const GraphType &Graph;
98
99
286k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::MachineBasicBlock const*>::Inverse(llvm::MachineBasicBlock const* const&)
Line
Count
Source
99
283k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::BasicBlock*>::Inverse(llvm::BasicBlock* const&)
Line
Count
Source
99
1.93k
  inline Inverse(const GraphType &G) : Graph(G) {}
llvm::Inverse<llvm::BasicBlock const*>::Inverse(llvm::BasicBlock const* const&)
Line
Count
Source
99
638
  inline Inverse(const GraphType &G) : Graph(G) {}
100
};
101
102
// Provide a partial specialization of GraphTraits so that the inverse of an
103
// inverse falls back to the original graph.
104
template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
105
106
// Provide iterator ranges for the graph traits nodes and children
107
template <class GraphType>
108
iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
109
2.01M
nodes(const GraphType &G) {
110
2.01M
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
111
2.01M
                    GraphTraits<GraphType>::nodes_end(G));
112
2.01M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineFunction*>::nodes_iterator> llvm::nodes<llvm::MachineFunction*>(llvm::MachineFunction* const&)
Line
Count
Source
109
1.45M
nodes(const GraphType &G) {
110
1.45M
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
111
1.45M
                    GraphTraits<GraphType>::nodes_end(G));
112
1.45M
}
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
109
3
nodes(const GraphType &G) {
110
3
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
111
3
                    GraphTraits<GraphType>::nodes_end(G));
112
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
109
326
nodes(const GraphType &G) {
110
326
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
111
326
                    GraphTraits<GraphType>::nodes_end(G));
112
326
}
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
109
565k
nodes(const GraphType &G) {
110
565k
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
111
565k
                    GraphTraits<GraphType>::nodes_end(G));
112
565k
}
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
109
1
nodes(const GraphType &G) {
110
1
  return make_range(GraphTraits<GraphType>::nodes_begin(G),
111
1
                    GraphTraits<GraphType>::nodes_end(G));
112
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&)
113
template <class GraphType>
114
iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
115
inverse_nodes(const GraphType &G) {
116
  return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
117
                    GraphTraits<Inverse<GraphType>>::nodes_end(G));
118
}
119
120
template <class GraphType>
121
iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
122
284M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
284M
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
284M
                    GraphTraits<GraphType>::child_end(G));
125
284M
}
llvm::iterator_range<llvm::GraphTraits<llvm::BasicBlock const*>::ChildIteratorType> llvm::children<llvm::BasicBlock const*>(llvm::GraphTraits<llvm::BasicBlock const*>::NodeRef const&)
Line
Count
Source
122
706k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
706k
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
706k
                    GraphTraits<GraphType>::child_end(G));
125
706k
}
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
122
12.0M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
12.0M
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
12.0M
                    GraphTraits<GraphType>::child_end(G));
125
12.0M
}
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
122
84.3M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
84.3M
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
84.3M
                    GraphTraits<GraphType>::child_end(G));
125
84.3M
}
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
122
51.3k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
51.3k
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
51.3k
                    GraphTraits<GraphType>::child_end(G));
125
51.3k
}
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
122
465k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
465k
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
465k
                    GraphTraits<GraphType>::child_end(G));
125
465k
}
llvm::iterator_range<llvm::GraphTraits<llvm::BasicBlock*>::ChildIteratorType> llvm::children<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef const&)
Line
Count
Source
122
159M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
159M
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
159M
                    GraphTraits<GraphType>::child_end(G));
125
159M
}
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
122
10.1k
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
10.1k
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
10.1k
                    GraphTraits<GraphType>::child_end(G));
125
10.1k
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineBasicBlock const*>::ChildIteratorType> llvm::children<llvm::MachineBasicBlock const*>(llvm::GraphTraits<llvm::MachineBasicBlock const*>::NodeRef const&)
Line
Count
Source
122
4.04M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
4.04M
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
4.04M
                    GraphTraits<GraphType>::child_end(G));
125
4.04M
}
llvm::iterator_range<llvm::GraphTraits<llvm::MachineBasicBlock*>::ChildIteratorType> llvm::children<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef const&)
Line
Count
Source
122
23.8M
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
23.8M
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
23.8M
                    GraphTraits<GraphType>::child_end(G));
125
23.8M
}
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
122
82
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
82
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
82
                    GraphTraits<GraphType>::child_end(G));
125
82
}
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
122
72
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
72
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
72
                    GraphTraits<GraphType>::child_end(G));
125
72
}
llvm::iterator_range<llvm::GraphTraits<clang::CFGBlock*>::ChildIteratorType> llvm::children<clang::CFGBlock*>(llvm::GraphTraits<clang::CFGBlock*>::NodeRef const&)
Line
Count
Source
122
52
children(const typename GraphTraits<GraphType>::NodeRef &G) {
123
52
  return make_range(GraphTraits<GraphType>::child_begin(G),
124
52
                    GraphTraits<GraphType>::child_end(G));
125
52
}
126
127
template <class GraphType>
128
iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
129
23.3M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
130
23.3M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
131
23.3M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
132
23.3M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::MachineBasicBlock*> >::ChildIteratorType> llvm::inverse_children<llvm::MachineBasicBlock*>(llvm::GraphTraits<llvm::MachineBasicBlock*>::NodeRef const&)
Line
Count
Source
129
16.9M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
130
16.9M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
131
16.9M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
132
16.9M
}
llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::BasicBlock*> >::ChildIteratorType> llvm::inverse_children<llvm::BasicBlock*>(llvm::GraphTraits<llvm::BasicBlock*>::NodeRef const&)
Line
Count
Source
129
6.34M
inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
130
6.34M
  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
131
6.34M
                    GraphTraits<Inverse<GraphType>>::child_end(G));
132
6.34M
}
Unexecuted instantiation: llvm::iterator_range<llvm::GraphTraits<llvm::Inverse<llvm::VPBlockBase*> >::ChildIteratorType> llvm::inverse_children<llvm::VPBlockBase*>(llvm::GraphTraits<llvm::VPBlockBase*>::NodeRef const&)
133
134
template <class GraphType>
135
iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
136
19
children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
137
19
  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
138
19
                    GraphTraits<GraphType>::child_edge_end(G));
139
19
}
140
141
} // end namespace llvm
142
143
#endif // LLVM_ADT_GRAPHTRAITS_H