RegionIterator.h Source File (original) (raw)

11#ifndef LLVM_ANALYSIS_REGIONITERATOR_H

12#define LLVM_ANALYSIS_REGIONITERATOR_H

18#include

19#include

20#include <type_traits>

22namespace llvm {

25class RegionInfo;

38template <class NodeRef, class BlockT, class RegionT> class RNSuccIterator {

39public:

46private:

48 using SuccIterTy = typename BlockTraits::ChildIteratorType;

51 enum ItMode {

54 ItBB,

57 ItRgBegin,

58 ItRgEnd

59 };

61 static_assert(std::is_pointer::value,

62 "FIXME: Currently RNSuccIterator only supports NodeRef as "

63 "pointers due to the use of pointer-specific data structures "

64 "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "

65 "it to support non-pointer types");

71 SuccIterTy BItor;

75 void advanceRegionSucc() {

76 assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");

77 Node.setInt(ItRgEnd);

78 }

80 NodeRef getNode() const { return Node.getPointer(); }

83 bool isRegionMode() const { return Node.getInt() != ItBB; }

87 NodeRef getISucc(BlockT *BB) const {

89 succ = getNode()->getParent()->getNode(BB);

90 assert(succ && "BB not in Region or entered subregion!");

91 return succ;

92 }

95 inline BlockT* getRegionSucc() const {

96 assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");

97 return getNode()->template getNodeAs()->getExit();

98 }

100

101 inline bool isExit(BlockT* BB) const {

102 return getNode()->getParent()->getExit() == BB;

103 }

104

105public:

107

108

110 : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),

111 BItor(BlockTraits::child_begin(node->getEntry())) {

112

113 if (!isRegionMode())

114 while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))

115 ++BItor;

116

117 if (isRegionMode() && isExit(getRegionSucc()))

118 advanceRegionSucc();

119 }

120

121

123 : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),

124 BItor(BlockTraits::child_end(node->getEntry())) {}

125

127 assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");

128 if (isRegionMode())

129 return Node.getInt() == x.Node.getInt();

130 else

131 return BItor == x.BItor;

132 }

133

135

137 BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;

138 assert(!isExit(BB) && "Iterator out of range!");

139 return getISucc(BB);

140 }

141

143 if(isRegionMode()) {

144

145 advanceRegionSucc();

146 } else {

147

148 do

149 ++BItor;

150 while (BItor != BlockTraits::child_end(getNode()->getEntry())

151 && isExit(*BItor));

152 }

153 return *this;

154 }

155

157 Self tmp = *this;

158 ++*this;

159 return tmp;

160 }

161};

162

163

164

165

166

167

168

169template <class NodeRef, class BlockT, class RegionT>

172 using SuccIterTy = typename BlockTraits::ChildIteratorType;

173

174 NodeRef Node;

175 SuccIterTy Itor;

176

177public:

183

185

186

187

188

189

191 : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {

193 "Subregion node not allowed in flat iterating mode!");

194 assert(Node->getParent() && "A BB node must have a parent!");

195

196

197 while (BlockTraits::child_end(Node->getEntry()) != Itor &&

198 Node->getParent()->getExit() == *Itor)

199 ++Itor;

200 }

201

202

204 : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {

206 "Subregion node not allowed in flat iterating mode!");

207 }

208

210 assert(Node->getParent() == x.Node->getParent()

211 && "Cannot compare iterators of different regions!");

212

213 return Itor == x.Itor && Node == x.Node;

214 }

215

216 inline bool operator!=(const Self& x) const { return !operator==(x); }

217

219 BlockT *BB = *Itor;

220

221

222 RegionT *Parent = Node->getParent();

223

224

225

226 assert(Parent->getExit() != BB && "iterator out of range!");

227

228 return Parent->getBBNode(BB);

229 }

230

232

233 do

234 ++Itor;

236 && Node->getParent()->getExit() == *Itor);

237

238 return *this;

239 }

240

242 Self tmp = *this;

243 ++*this;

244 return tmp;

245 }

246};

247

248template <class NodeRef, class BlockT, class RegionT>

251}

252

253template <class NodeRef, class BlockT, class RegionT>

256}

257

258

259

260

261

262

263

264

265#define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \

266 template <> struct GraphTraits<NodeT *> { \

267 using NodeRef = NodeT *; \

268 using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>; \

269 static NodeRef getEntryNode(NodeRef N) { return N; } \

270 static inline ChildIteratorType child_begin(NodeRef N) { \

271 return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \

272 } \

273 static inline ChildIteratorType child_end(NodeRef N) { \

274 return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \

275 } \

276 }; \

277 template <> struct GraphTraits<FlatIt<NodeT *>> { \

278 using NodeRef = NodeT *; \

279 using ChildIteratorType = \

280 RNSuccIterator<FlatIt, BlockT, RegionT>; \

281 static NodeRef getEntryNode(NodeRef N) { return N; } \

282 static inline ChildIteratorType child_begin(NodeRef N) { \

283 return RNSuccIterator<FlatIt, BlockT, RegionT>(N); \

284 } \

285 static inline ChildIteratorType child_end(NodeRef N) { \

286 return RNSuccIterator<FlatIt, BlockT, RegionT>(N, true); \

287 } \

288 }

289

290#define RegionGraphTraits(RegionT, NodeT) \

291 template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> { \

292 using nodes_iterator = df_iterator; \

293 static NodeRef getEntryNode(RegionT *R) { \

294 return R->getNode(R->getEntry()); \

295 } \

296 static nodes_iterator nodes_begin(RegionT *R) { \

297 return nodes_iterator::begin(getEntryNode(R)); \

298 } \

299 static nodes_iterator nodes_end(RegionT *R) { \

300 return nodes_iterator::end(getEntryNode(R)); \

301 } \

302 }; \

303 template <> \

304 struct GraphTraits<FlatIt<RegionT *>> \

305 : public GraphTraits<FlatIt<NodeT *>> { \

306 using nodes_iterator = \

307 df_iterator<NodeRef, df_iterator_default_set, false, \

308 GraphTraits<FlatIt>>; \

309 static NodeRef getEntryNode(RegionT *R) { \

310 return R->getBBNode(R->getEntry()); \

311 } \

312 static nodes_iterator nodes_begin(RegionT *R) { \

313 return nodes_iterator::begin(getEntryNode(R)); \

314 } \

315 static nodes_iterator nodes_end(RegionT *R) { \

316 return nodes_iterator::end(getEntryNode(R)); \

317 } \

318 }

319

322

325

331

334 }

335

337 return nodes_iterator::begin(getEntryNode(RI));

338 }

339

341 return nodes_iterator::end(getEntryNode(RI));

342 }

343};

344

350

353 }

354

357 }

358

361 }

362};

363

364}

365

366#endif

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

This file defines the little GraphTraits template class that should be specialized by classes that...

This file defines the PointerIntPair class.

#define RegionNodeGraphTraits(NodeT, BlockT, RegionT)

#define RegionGraphTraits(RegionT, NodeT)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

LLVM Basic Block Representation.

Marker class to iterate over the elements of a Region in flat mode.

PointerIntPair - This class implements a pair of a pointer and small integer.

Flat RegionNode iterator.

std::forward_iterator_tag iterator_category

bool operator==(const Self &x) const

RNSuccIterator(NodeRef node, bool)

Create an end iterator.

value_type operator*() const

RNSuccIterator(NodeRef node)

Create the iterator from a RegionNode.

bool operator!=(const Self &x) const

std::ptrdiff_t difference_type

Hierarchical RegionNode successor iterator.

value_type operator*() const

RNSuccIterator(NodeRef node, bool)

Create an end iterator.

std::forward_iterator_tag iterator_category

std::ptrdiff_t difference_type

bool operator!=(const Self &x) const

bool operator==(const Self &x) const

RNSuccIterator(NodeRef node)

Create begin iterator of a RegionNode.

RegionT * getTopLevelRegion() const

RegionInfo & getRegionInfo()

@ BasicBlock

Various leaf nodes.

std::pair< NodeId, LaneBitmask > NodeRef

This is an optimization pass for GlobalISel generic memory operations.

RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)

RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)

static nodes_iterator nodes_begin(RegionInfoPass *RI)

static nodes_iterator nodes_end(RegionInfoPass *RI)

static NodeRef getEntryNode(RegionInfoPass *RI)

static nodes_iterator nodes_begin(RegionInfo *RI)

static nodes_iterator nodes_end(RegionInfo *RI)

static NodeRef getEntryNode(RegionInfo *RI)

typename GraphType::UnknownGraphTypeError NodeRef