LLVM  15.0.0git
BreadthFirstIterator.h
Go to the documentation of this file.
1 //===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- 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 /// \file
10 /// This file builds on the ADT/GraphTraits.h file to build a generic breadth
11 /// first graph iterator. This file exposes the following functions/types:
12 ///
13 /// bf_begin/bf_end/bf_iterator
14 /// * Normal breadth-first iteration - visit a graph level-by-level.
15 ///
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H
19 #define LLVM_ADT_BREADTHFIRSTITERATOR_H
20 
21 #include "llvm/ADT/GraphTraits.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/Optional.h"
24 #include "llvm/ADT/SmallPtrSet.h"
26 #include <iterator>
27 #include <queue>
28 #include <utility>
29 
30 namespace llvm {
31 
32 // bf_iterator_storage - A private class which is used to figure out where to
33 // store the visited set. We only provide a non-external variant for now.
34 template <class SetType> class bf_iterator_storage {
35 public:
36  SetType Visited;
37 };
38 
39 // The visited state for the iteration is a simple set.
40 template <typename NodeRef, unsigned SmallSize = 8>
42 
43 // Generic Breadth first search iterator.
44 template <class GraphT,
45  class SetType =
47  class GT = GraphTraits<GraphT>>
48 class bf_iterator : public bf_iterator_storage<SetType> {
49 public:
50  using iterator_category = std::forward_iterator_tag;
51  using value_type = typename GT::NodeRef;
52  using difference_type = std::ptrdiff_t;
53  using pointer = value_type *;
54  using reference = value_type &;
55 
56 private:
57  using NodeRef = typename GT::NodeRef;
58  using ChildItTy = typename GT::ChildIteratorType;
59 
60  // First element is the node reference, second is the next child to visit.
61  using QueueElement = std::pair<NodeRef, Optional<ChildItTy>>;
62 
63  // Visit queue - used to maintain BFS ordering.
64  // Optional<> because we need markers for levels.
65  std::queue<Optional<QueueElement>> VisitQueue;
66 
67  // Current level.
68  unsigned Level = 0;
69 
70  inline bf_iterator(NodeRef Node) {
71  this->Visited.insert(Node);
72  Level = 0;
73 
74  // Also, insert a dummy node as marker.
75  VisitQueue.push(QueueElement(Node, None));
76  VisitQueue.push(None);
77  }
78 
79  inline bf_iterator() = default;
80 
81  inline void toNext() {
82  Optional<QueueElement> Head = VisitQueue.front();
83  QueueElement H = Head.getValue();
84  NodeRef Node = H.first;
85  Optional<ChildItTy> &ChildIt = H.second;
86 
87  if (!ChildIt)
88  ChildIt.emplace(GT::child_begin(Node));
89  while (*ChildIt != GT::child_end(Node)) {
90  NodeRef Next = *(*ChildIt)++;
91 
92  // Already visited?
93  if (this->Visited.insert(Next).second)
94  VisitQueue.push(QueueElement(Next, None));
95  }
96  VisitQueue.pop();
97 
98  // Go to the next element skipping markers if needed.
99  if (!VisitQueue.empty()) {
100  Head = VisitQueue.front();
101  if (Head != None)
102  return;
103  Level += 1;
104  VisitQueue.pop();
105 
106  // Don't push another marker if this is the last
107  // element.
108  if (!VisitQueue.empty())
109  VisitQueue.push(None);
110  }
111  }
112 
113 public:
114  // Provide static begin and end methods as our public "constructors"
115  static bf_iterator begin(const GraphT &G) {
116  return bf_iterator(GT::getEntryNode(G));
117  }
118 
119  static bf_iterator end(const GraphT &G) { return bf_iterator(); }
120 
121  bool operator==(const bf_iterator &RHS) const {
122  return VisitQueue == RHS.VisitQueue;
123  }
124 
125  bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
126 
127  const NodeRef &operator*() const { return VisitQueue.front()->first; }
128 
129  // This is a nonstandard operator-> that dereferences the pointer an extra
130  // time so that you can actually call methods on the node, because the
131  // contained type is a pointer.
132  NodeRef operator->() const { return **this; }
133 
134  bf_iterator &operator++() { // Pre-increment
135  toNext();
136  return *this;
137  }
138 
139  bf_iterator operator++(int) { // Post-increment
140  bf_iterator ItCopy = *this;
141  ++*this;
142  return ItCopy;
143  }
144 
145  unsigned getLevel() const { return Level; }
146 };
147 
148 // Provide global constructors that automatically figure out correct types.
149 template <class T> bf_iterator<T> bf_begin(const T &G) {
150  return bf_iterator<T>::begin(G);
151 }
152 
153 template <class T> bf_iterator<T> bf_end(const T &G) {
154  return bf_iterator<T>::end(G);
155 }
156 
157 // Provide an accessor method to use them in range-based patterns.
158 template <class T> iterator_range<bf_iterator<T>> breadth_first(const T &G) {
159  return make_range(bf_begin(G), bf_end(G));
160 }
161 
162 } // end namespace llvm
163 
164 #endif // LLVM_ADT_BREADTHFIRSTITERATOR_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Optional.h
llvm::bf_iterator::reference
value_type & reference
Definition: BreadthFirstIterator.h:54
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::bf_iterator::operator!=
bool operator!=(const bf_iterator &RHS) const
Definition: BreadthFirstIterator.h:125
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::bf_iterator::pointer
value_type * pointer
Definition: BreadthFirstIterator.h:53
llvm::bf_iterator::operator++
bf_iterator operator++(int)
Definition: BreadthFirstIterator.h:139
GraphTraits.h
llvm::bf_iterator::difference_type
std::ptrdiff_t difference_type
Definition: BreadthFirstIterator.h:52
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:158
llvm::bf_iterator::value_type
typename GT::NodeRef value_type
Definition: BreadthFirstIterator.h:51
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
SmallPtrSet.h
llvm::bf_iterator::getLevel
unsigned getLevel() const
Definition: BreadthFirstIterator.h:145
llvm::None
const NoneType None
Definition: None.h:24
llvm::bf_iterator::begin
static bf_iterator begin(const GraphT &G)
Definition: BreadthFirstIterator.h:115
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::bf_iterator::operator->
NodeRef operator->() const
Definition: BreadthFirstIterator.h:132
llvm::bf_iterator_storage
Definition: BreadthFirstIterator.h:34
llvm::bf_iterator::end
static bf_iterator end(const GraphT &G)
Definition: BreadthFirstIterator.h:119
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:261
llvm::bf_iterator_storage::Visited
SetType Visited
Definition: BreadthFirstIterator.h:36
llvm::Optional::getValue
constexpr const T & getValue() const &
Definition: Optional.h:279
iterator_range.h
llvm::bf_end
bf_iterator< T > bf_end(const T &G)
Definition: BreadthFirstIterator.h:153
None.h
Node
Definition: ItaniumDemangle.h:155
llvm::bf_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: BreadthFirstIterator.h:50
llvm::bf_iterator
Definition: BreadthFirstIterator.h:48
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::bf_begin
bf_iterator< T > bf_begin(const T &G)
Definition: BreadthFirstIterator.h:149
llvm::bf_iterator::operator++
bf_iterator & operator++()
Definition: BreadthFirstIterator.h:134
llvm::AArch64CC::GT
@ GT
Definition: AArch64BaseInfo.h:267
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::bf_iterator::operator*
const NodeRef & operator*() const
Definition: BreadthFirstIterator.h:127
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::bf_iterator::operator==
bool operator==(const bf_iterator &RHS) const
Definition: BreadthFirstIterator.h:121