LoopIterator.h Source File (original) (raw)

23#ifndef LLVM_ANALYSIS_LOOPITERATOR_H

24#define LLVM_ANALYSIS_LOOPITERATOR_H

29namespace llvm {

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

47 WrappedSuccIterator, succ_iterator,

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

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

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

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 };

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())) {

117 PostBlocks.reserve(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

163

165 PostNumbers.clear();

166 PostBlocks.clear();

167 }

168};

169

170

171

173private:

175

176public:

178

179

181 DFS.perform(LI);

182 }

183

184

187};

188

189

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");

219 return po_ext_begin(DFS.L->getHeader(), *this);

220 }

222

223 return po_ext_end(DFS.L->getHeader(), *this);

224 }

225

226

227

228

229

230

232 if (!DFS.L->contains(LI->getLoopFor(BB)))

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

248 std::optional<BasicBlock *> From, BasicBlock *To) {

249 return LBT.visitPreorder(To);

250}

251

254 LBT.finishPostorder(BB);

255}

256

257}

258

259#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

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

LLVM Basic Block Representation.

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator

unsigned getNumBlocks() const

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

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

Definition LoopIterator.h:97

RPOIterator beginRPO() const

Reverse iterate over the cached postorder blocks.

Definition LoopIterator.h:136

bool hasPreorder(BasicBlock *BB) const

Return true if this block has been preorder visited.

Definition LoopIterator.h:143

unsigned getPostorder(BasicBlock *BB) const

Get a block's postorder number.

Definition LoopIterator.h:152

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

Definition LoopIterator.h:101

bool hasPostorder(BasicBlock *BB) const

Return true if this block has a postorder number.

Definition LoopIterator.h:146

unsigned getRPO(BasicBlock *BB) const

Get a block's reverse postorder number.

Definition LoopIterator.h:160

Loop * getLoop() const

Definition LoopIterator.h:120

LoopBlocksDFS(Loop *Container)

Definition LoopIterator.h:115

friend class LoopBlocksTraversal

Definition LoopIterator.h:103

bool isComplete() const

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

Definition LoopIterator.h:126

POIterator beginPostorder() const

Iterate over the cached postorder blocks.

Definition LoopIterator.h:129

POIterator endPostorder() const

Definition LoopIterator.h:133

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

Postorder list iterators.

Definition LoopIterator.h:100

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

void clear()

Definition LoopIterator.h:164

RPOIterator endRPO() const

Definition LoopIterator.h:140

LoopBlocksDFS::RPOIterator end() const

Definition LoopIterator.h:186

LoopBlocksDFS::RPOIterator begin() const

Reverse iterate over the cached postorder blocks.

Definition LoopIterator.h:185

LoopBlocksRPO(Loop *Container)

Definition LoopIterator.h:177

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

Definition LoopIterator.h:180

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

Definition LoopIterator.h:200

POTIterator end()

Definition LoopIterator.h:221

bool visitPreorder(BasicBlock *BB)

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

Definition LoopIterator.h:231

void finishPostorder(BasicBlock *BB)

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

Definition LoopIterator.h:240

LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo)

Definition LoopIterator.h:210

po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator

Graph traversal iterator.

Definition LoopIterator.h:203

POTIterator begin()

Postorder traversal over the graph.

Definition LoopIterator.h:216

NodeRef operator*() const

Definition LoopIterator.h:61

WrappedSuccIterator(succ_iterator Begin, const Loop *L)

Definition LoopIterator.h:58

Represents a single loop in the control flow graph.

iterator_adaptor_base()=default

po_iterator_storage(LoopBlocksTraversal &lbs)

Definition LoopIterator.h:193

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

void finishPostorder(NodeRef BB)

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

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

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)

SuccIterator< Instruction, BasicBlock > succ_iterator

filter_iterator_impl< WrappedIteratorT, PredicateT, detail::fwd_or_bidi_tag< WrappedIteratorT > > filter_iterator

Defines filter_iterator to a suitable specialization of filter_iterator_impl, based on the underlying...

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.

Definition LoopIterator.h:64

bool operator()(NodeRef N) const

Definition LoopIterator.h:65

Definition LoopIterator.h:40

static ChildIteratorType child_end(NodeRef Node)

Definition LoopIterator.h:84

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

Definition LoopIterator.h:41

filter_iterator< WrappedSuccIterator, LoopBodyFilter > ChildIteratorType

Definition LoopIterator.h:71

static ChildIteratorType child_begin(NodeRef Node)

Definition LoopIterator.h:76

static NodeRef getEntryNode(const Loop &G)

Definition LoopIterator.h:74