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;
115 this->
insertEdge(std::optional<NodeRef>(), BB);
116 VisitStack.
emplace_back(BB, GT::child_begin(BB), GT::child_end(BB));
124 if (this->
insertEdge(std::optional<NodeRef>(), BB)) {
125 VisitStack.
emplace_back(BB, GT::child_begin(BB), GT::child_end(BB));
130 po_iterator(SetType &S)
131 : po_iterator_storage<SetType, ExtStorage>(S) {
134 void traverseChild() {
136 auto &Entry = VisitStack.
back();
137 if (std::get<1>(Entry) == std::get<2>(Entry))
139 NodeRef BB = *std::get<1>(Entry)++;
140 if (this->
insertEdge(std::optional<NodeRef>(std::get<0>(Entry)), BB)) {
142 VisitStack.
emplace_back(BB, GT::child_begin(BB), GT::child_end(BB));
160 return VisitStack == x.VisitStack;
175 if (!VisitStack.
empty())
199template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
205template<
class T,
class SetType>
210template<
class T,
class SetType>
215template <
class T,
class SetType>
221template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>,
222 bool External =
false>
244template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
252template <
class T,
class SetType>
257template <
class T,
class SetType>
262template <
class T,
class SetType>
263iterator_range<ipo_ext_iterator<T, SetType>>
295template<
class GraphT,
class GT = GraphTraits<GraphT>>
297 using NodeRef =
typename GT::NodeRef;
302 void Initialize(
const GraphT &
G) {
BlockVerifier::State From
DenseMap< Block *, BlockRelaxAux > Blocks
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
ReversePostOrderTraversal(const GraphT &G)
typename VecTy::reverse_iterator rpo_iterator
typename VecTy::const_reverse_iterator const_rpo_iterator
reference emplace_back(ArgTypes &&... Args)
std::reverse_iterator< const_iterator > const_reverse_iterator
std::reverse_iterator< iterator > reverse_iterator
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)
reference operator*() const
std::ptrdiff_t difference_type
static po_iterator end(const GraphT &G)
const value_type & reference
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)