LoopIterator.h Source File (original) (raw)

23#ifndef LLVM_ANALYSIS_LOOPITERATOR_H

24#define LLVM_ANALYSIS_LOOPITERATOR_H

29namespace llvm {

31class LoopBlocksTraversal;

41 using NodeRef = std::pair<const Loop *, BasicBlock *>;

47 WrappedSuccIterator, succ_iterator,

48 typename std::iterator_traits<succ_iterator>::iterator_category,

49 NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {

52 typename std::iterator_traits<succ_iterator>::iterator_category,

55 const Loop *L;

57 public:

59 : BaseT(Begin), L(L) {}

62 };

66 const Loop *L = N.first;

67 return N.second != L->getHeader() && L->contains(N.second);

68 }

69 };

81 .begin();

82 }

89 .end();

90 }

91};

98public:

100 typedef std::vector<BasicBlock*>::const_iterator POIterator;

101 typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;

102

104

105private:

107

108

109

110

112 std::vector<BasicBlock*> PostBlocks;

113

114public:

116 L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {

118 }

119

121

122

124

125

126 bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }

127

128

131 return PostBlocks.begin();

132 }

134

135

138 return PostBlocks.rbegin();

139 }

141

142

144

145

148 return I != PostNumbers.end() && I->second;

149 }

150

151

154 assert(I != PostNumbers.end() && "block not visited by DFS");

155 assert(I->second && "block not finished by DFS");

156 return I->second;

157 }

158

159

161 return 1 + PostBlocks.size() - getPostorder(BB);

162 }

163

165 PostNumbers.clear();

166 PostBlocks.clear();

167 }

168};

169

170

171

173private:

175

176public:

178

179

182 }

183

184

187};

188

189

192public:

194

197};

198

199

201public:

202

204

205private:

208

209public:

211 DFS(Storage), LI(LInfo) {}

212

213

214

215

217 assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");

218 assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");

220 }

222

224 }

225

226

227

228

229

230

233 return false;

234

235 return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;

236 }

237

238

239

241 assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");

242 DFS.PostBlocks.push_back(BB);

243 DFS.PostNumbers[BB] = DFS.PostBlocks.size();

244 }

245};

246

249 return LBT.visitPreorder(To);

250}

251

254 LBT.finishPostorder(BB);

255}

256

257}

258

259#endif

BlockVerifier::State From

This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.

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

LLVM Basic Block Representation.

iterator find(const_arg_type_t< KeyT > Val)

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

void reserve(size_type NumEntries)

Grow the densemap so that it can contain at least NumEntries items before resizing again.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

unsigned getNumBlocks() const

Get the number of blocks in this loop in constant time.

BlockT * getHeader() const

Store the result of a depth first search within basic blocks contained by a single loop.

RPOIterator beginRPO() const

Reverse iterate over the cached postorder blocks.

bool hasPreorder(BasicBlock *BB) const

Return true if this block has been preorder visited.

unsigned getPostorder(BasicBlock *BB) const

Get a block's postorder number.

std::vector< BasicBlock * >::const_reverse_iterator RPOIterator

bool hasPostorder(BasicBlock *BB) const

Return true if this block has a postorder number.

unsigned getRPO(BasicBlock *BB) const

Get a block's reverse postorder number.

LoopBlocksDFS(Loop *Container)

bool isComplete() const

Return true if postorder numbers are assigned to all loop blocks.

POIterator beginPostorder() const

Iterate over the cached postorder blocks.

POIterator endPostorder() const

std::vector< BasicBlock * >::const_iterator POIterator

Postorder list iterators.

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

RPOIterator endRPO() const

Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...

LoopBlocksDFS::RPOIterator end() const

LoopBlocksDFS::RPOIterator begin() const

Reverse iterate over the cached postorder blocks.

LoopBlocksRPO(Loop *Container)

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

Traverse the blocks in a loop using a depth-first search.

bool visitPreorder(BasicBlock *BB)

Called by po_iterator upon reaching a block via a CFG edge.

void finishPostorder(BasicBlock *BB)

Called by po_iterator each time it advances, indicating a block's postorder.

LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo)

po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator

Graph traversal iterator.

POTIterator begin()

Postorder traversal over the graph.

NodeRef operator*() const

WrappedSuccIterator(succ_iterator Begin, const Loop *L)

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Represents a single loop in the control flow graph.

Specialization of filter_iterator_base for forward iteration only.

CRTP base class for adapting an iterator to a different type.

po_iterator_storage(LoopBlocksTraversal &lbs)

Default po_iterator_storage implementation with an internal set object.

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

void finishPostorder(NodeRef BB)

This is an optimization pass for GlobalISel generic memory operations.

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

SuccIterator< Instruction, BasicBlock > succ_iterator

iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)

Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...

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

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

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

constexpr uint64_t NextPowerOf2(uint64_t A)

Returns the next power of two (in 64-bits) that is strictly greater than A.

bool operator()(NodeRef N) const

static ChildIteratorType child_end(NodeRef Node)

std::pair< const Loop *, BasicBlock * > NodeRef

static ChildIteratorType child_begin(NodeRef Node)

static NodeRef getEntryNode(const Loop &G)