16#ifndef LLVM_ADT_POSTORDERITERATOR_H
17#define LLVM_ADT_POSTORDERITERATOR_H
58template<
class SetType,
bool External>
64 template <
typename NodeRef>
66 return Visited.insert(To).second;
74template<
class SetType>
85 template <
class NodeRef>
87 return Visited.insert(To).second;
94template <
class GraphT,
95 class SetType = SmallPtrSet<typename GraphTraits<GraphT>::NodeRef, 8>,
96 bool ExtStorage =
false,
class GT = GraphTraits<GraphT>>
106 using NodeRef =
typename GT::NodeRef;
107 using ChildItTy =
typename GT::ChildIteratorType;
114 this->
insertEdge(std::optional<NodeRef>(), BB);
115 VisitStack.
push_back(std::make_pair(BB, GT::child_begin(BB)));
123 if (this->
insertEdge(std::optional<NodeRef>(), BB)) {
124 VisitStack.
push_back(std::make_pair(BB, GT::child_begin(BB)));
129 po_iterator(SetType &S)
130 : po_iterator_storage<SetType, ExtStorage>(S) {
133 void traverseChild() {
134 while (VisitStack.
back().second != GT::child_end(VisitStack.
back().first)) {
135 NodeRef BB = *VisitStack.
back().second++;
136 if (this->
insertEdge(std::optional<NodeRef>(VisitStack.
back().first),
139 VisitStack.
push_back(std::make_pair(BB, GT::child_begin(BB)));
157 return VisitStack == x.VisitStack;
172 if (!VisitStack.
empty())
196template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
202template<
class T,
class SetType>
207template<
class T,
class SetType>
212template <
class T,
class SetType>
218template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>,
219 bool External =
false>
241template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
249template <
class T,
class SetType>
254template <
class T,
class SetType>
259template <
class T,
class SetType>
260iterator_range<ipo_ext_iterator<T, SetType>>
292template<
class GraphT,
class GT = GraphTraits<GraphT>>
294 using NodeRef =
typename GT::NodeRef;
296 std::vector<NodeRef> Blocks;
298 void Initialize(
const GraphT &
G) {
BlockVerifier::State From
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
const_rpo_iterator end() const
const_rpo_iterator begin() const
typename std::vector< NodeRef >::const_reverse_iterator const_rpo_iterator
ReversePostOrderTraversal(const GraphT &G)
typename std::vector< NodeRef >::reverse_iterator rpo_iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A range adaptor for a pair of iterators.
void finishPostorder(NodeRef BB)
po_iterator_storage(const po_iterator_storage &S)
bool insertEdge(std::optional< NodeRef > From, NodeRef To)
po_iterator_storage(SetType &VSet)
Default po_iterator_storage implementation with an internal set object.
bool insertEdge(std::optional< NodeRef > From, NodeRef To)
void finishPostorder(NodeRef BB)
static po_iterator end(const GraphT &G, SetType &S)
std::ptrdiff_t difference_type
static po_iterator end(const GraphT &G)
const NodeRef & operator*() const
std::forward_iterator_tag iterator_category
NodeRef operator->() const
typename GT::NodeRef value_type
static po_iterator begin(const GraphT &G)
po_iterator & operator++()
po_iterator operator++(int)
bool operator==(const po_iterator &x) const
bool operator!=(const po_iterator &x) const
static po_iterator begin(const GraphT &G, SetType &S)
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
ipo_iterator< T > ipo_end(const T &G)
iterator_range< po_ext_iterator< T, SetType > > post_order_ext(const T &G, SetType &S)
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
ipo_ext_iterator< T, SetType > ipo_ext_begin(const T &G, SetType &S)
iterator_range< ipo_iterator< T > > inverse_post_order(const T &G)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
iterator_range< po_iterator< T > > post_order(const T &G)
po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)
po_iterator< T > po_begin(const T &G)
ipo_ext_iterator< T, SetType > ipo_ext_end(const T &G, SetType &S)
ipo_iterator< T > ipo_begin(const T &G)
po_iterator< T > po_end(const T &G)
po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)
ipo_ext_iterator(const ipo_iterator< T, SetType, true > &V)
ipo_ext_iterator(const po_iterator< Inverse< T >, SetType, true > &V)
ipo_iterator(const po_iterator< Inverse< T >, SetType, External > &V)
po_ext_iterator(const po_iterator< T, SetType, true > &V)