PostOrderIterator.h Source File (original) (raw)

16#ifndef LLVM_ADT_POSTORDERITERATOR_H

17#define LLVM_ADT_POSTORDERITERATOR_H

23#include

24#include

25#include

26#include <type_traits>

27#include

29namespace llvm {

58template<class SetType, bool External>

60 SetType Visited;

62public:

64 template

65 bool insertEdge(std::optional From, NodeRef To) {

66 return Visited.insert(To).second;

67 }

71};

74template

76 SetType &Visited;

78public:

85 template

86 bool insertEdge(std::optional From, NodeRef To) {

87 return Visited.insert(To).second;

88 }

92};

94template <class GraphT,

95 class SetType = SmallPtrSet<typename GraphTraits::NodeRef, 8>,

96 bool ExtStorage = false, class GT = GraphTraits>

98public:

101 std::conditional_t<ExtStorage, std::input_iterator_tag,

102 std::forward_iterator_tag>;

107

108private:

109 using NodeRef = typename GT::NodeRef;

110 using ChildItTy = typename GT::ChildIteratorType;

111

112

113

114

116

117 po_iterator(NodeRef BB) {

118 this->insertEdge(std::optional(), BB);

119 VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB));

120 traverseChild();

121 }

122

123 po_iterator() = default;

124

127 if (this->insertEdge(std::optional(), BB)) {

128 VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB));

129 traverseChild();

130 }

131 }

132

133 po_iterator(SetType &S)

134 : po_iterator_storage<SetType, ExtStorage>(S) {

135 }

136

137 void traverseChild() {

138 while (true) {

139 auto &Entry = VisitStack.back();

140 if (std::get<1>(Entry) == std::get<2>(Entry))

141 break;

142 NodeRef BB = *std::get<1>(Entry)++;

143 if (this->insertEdge(std::optional(std::get<0>(Entry)), BB)) {

144

145 VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB));

146 }

147 }

148 }

149

150public:

151

152 static po_iterator begin(const GraphT &G) {

153 return po_iterator(GT::getEntryNode(G));

154 }

155 static po_iterator end(const GraphT &G) { return po_iterator(); }

156

157 static po_iterator begin(const GraphT &G, SetType &S) {

158 return po_iterator(GT::getEntryNode(G), S);

159 }

160 static po_iterator end(const GraphT &G, SetType &S) { return po_iterator(S); }

161

163 return VisitStack == x.VisitStack;

164 }

165 bool operator!=(const po_iterator &x) const { return !(*this == x); }

166

168

169

170

171

172

174

177 VisitStack.pop_back();

178 if (!VisitStack.empty())

179 traverseChild();

180 return *this;

181 }

182

184 po_iterator tmp = *this;

185 ++*this;

186 return tmp;

187 }

188};

189

190

191

192template

194template

196

200

201

202template <class T, class SetType = std::set<typename GraphTraits::NodeRef>>

205 po_iterator<T, SetType, true>(V) {}

206};

207

208template<class T, class SetType>

212

213template<class T, class SetType>

217

218template <class T, class SetType>

222

223

224template <class T, class SetType = std::set<typename GraphTraits::NodeRef>,

225 bool External = false>

226struct ipo_iterator : po_iterator<Inverse, SetType, External> {

228 po_iterator<Inverse<T>, SetType, External> (V) {}

229};

230

231template

235

236template

240

241template

245

246

247template <class T, class SetType = std::set<typename GraphTraits::NodeRef>>

254

255template <class T, class SetType>

259

260template <class T, class SetType>

264

265template <class T, class SetType>

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298template<class GraphT, class GT = GraphTraits>

300 using NodeRef = typename GT::NodeRef;

301

303 VecTy Blocks;

304

305 void Initialize(const GraphT &G) {

306 std::copy(po_begin(G), po_end(G), std::back_inserter(Blocks));

307 }

308

309public:

312

314

315

320};

321

322}

323

324#endif

This file defines the little GraphTraits 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

Definition PostOrderIterator.h:319

const_rpo_iterator begin() const

Definition PostOrderIterator.h:317

ReversePostOrderTraversal(const GraphT &G)

Definition PostOrderIterator.h:313

typename VecTy::reverse_iterator rpo_iterator

Definition PostOrderIterator.h:310

typename VecTy::const_reverse_iterator const_rpo_iterator

Definition PostOrderIterator.h:311

rpo_iterator begin()

Definition PostOrderIterator.h:316

rpo_iterator end()

Definition PostOrderIterator.h:318

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)

Definition PostOrderIterator.h:91

po_iterator_storage(const po_iterator_storage &S)

Definition PostOrderIterator.h:80

bool insertEdge(std::optional< NodeRef > From, NodeRef To)

Definition PostOrderIterator.h:86

po_iterator_storage(SetType &VSet)

Definition PostOrderIterator.h:79

Default po_iterator_storage implementation with an internal set object.

Definition PostOrderIterator.h:59

bool insertEdge(std::optional< NodeRef > From, NodeRef To)

Definition PostOrderIterator.h:65

void finishPostorder(NodeRef BB)

Definition PostOrderIterator.h:70

Definition PostOrderIterator.h:97

static po_iterator end(const GraphT &G, SetType &S)

Definition PostOrderIterator.h:160

reference operator*() const

Definition PostOrderIterator.h:167

std::ptrdiff_t difference_type

Definition PostOrderIterator.h:104

static po_iterator end(const GraphT &G)

Definition PostOrderIterator.h:155

value_type * pointer

Definition PostOrderIterator.h:105

const value_type & reference

Definition PostOrderIterator.h:106

NodeRef operator->() const

Definition PostOrderIterator.h:173

typename GT::NodeRef value_type

Definition PostOrderIterator.h:103

static po_iterator begin(const GraphT &G)

Definition PostOrderIterator.h:152

po_iterator & operator++()

Definition PostOrderIterator.h:175

po_iterator operator++(int)

Definition PostOrderIterator.h:183

std::conditional_t< ExtStorage, std::input_iterator_tag, std::forward_iterator_tag > iterator_category

Definition PostOrderIterator.h:100

bool operator==(const po_iterator &x) const

Definition PostOrderIterator.h:162

bool operator!=(const po_iterator &x) const

Definition PostOrderIterator.h:165

static po_iterator begin(const GraphT &G, SetType &S)

Definition PostOrderIterator.h:157

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)

Definition PostOrderIterator.h:237

iterator_range< po_ext_iterator< T, SetType > > post_order_ext(const T &G, SetType &S)

Definition PostOrderIterator.h:219

iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)

Definition PostOrderIterator.h:267

ipo_ext_iterator< T, SetType > ipo_ext_begin(const T &G, SetType &S)

Definition PostOrderIterator.h:256

iterator_range< ipo_iterator< T > > inverse_post_order(const T &G)

Definition PostOrderIterator.h:242

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)

Definition PostOrderIterator.h:197

po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)

Definition PostOrderIterator.h:214

po_iterator< T > po_begin(const T &G)

Definition PostOrderIterator.h:193

ipo_ext_iterator< T, SetType > ipo_ext_end(const T &G, SetType &S)

Definition PostOrderIterator.h:261

ipo_iterator< T > ipo_begin(const T &G)

Definition PostOrderIterator.h:232

iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >

po_iterator< T > po_end(const T &G)

Definition PostOrderIterator.h:195

po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)

Definition PostOrderIterator.h:209

ipo_ext_iterator(const ipo_iterator< T, SetType, true > &V)

Definition PostOrderIterator.h:249

ipo_ext_iterator(const po_iterator< Inverse< T >, SetType, true > &V)

Definition PostOrderIterator.h:251

ipo_iterator(const po_iterator< Inverse< T >, SetType, External > &V)

Definition PostOrderIterator.h:227

po_ext_iterator(const po_iterator< T, SetType, true > &V)

Definition PostOrderIterator.h:204