GenericCycleInfo.h Source File (original) (raw)

28#ifndef LLVM_ADT_GENERICCYCLEINFO_H

29#define LLVM_ADT_GENERICCYCLEINFO_H

38namespace llvm {

44template class GenericCycle {

45public:

46 using BlockT = typename ContextT::BlockT;

47 using FunctionT = typename ContextT::FunctionT;

51private:

54 GenericCycle *ParentCycle = nullptr;

62 std::vector<std::unique_ptr> Children;

68 BlockSetVectorT Blocks;

75 unsigned Depth = 0;

80 void clear() {

82 Children.clear();

83 Blocks.clear();

84 Depth = 0;

85 ParentCycle = nullptr;

87 }

92 }

97 }

100 GenericCycle &operator=(const GenericCycle &) = delete;

102 GenericCycle &operator=(GenericCycle &&Rhs) = delete;

103

104public:

106

107

108 bool isReducible() const { return Entries.size() == 1; }

109

111

113 return Entries;

114 }

115

116

117

118

119 void clearCache() const { ExitBlocksCache.clear(); }

120

121

125

126

129 Entries.clear();

130 Entries.push_back(Block);

132 }

133

134

136

137

138

139

140

142

143 const GenericCycle *getParentCycle() const { return ParentCycle; }

145 unsigned getDepth() const { return Depth; }

146

147

148

149

150

152

153

154

156

157

158

159

160

162

163

164

166

169

170

171

173 typename std::vector<std::unique_ptr>::const_iterator;

185

197

198

199

200

202

213

214

215

216

229

230

233 bool First = true;

234 for (auto *Entry : Entries) {

236 Out << ' ';

238 Out << Ctx.print(Entry);

239 }

240 });

241 }

242

245 Out << "depth=" << Depth << ": entries(" << printEntries(Ctx) << ')';

246

247 for (auto *Block : Blocks) {

249 continue;

250

251 Out << ' ' << Ctx.print(Block);

252 }

253 });

254 }

255};

256

257

259public:

260 using BlockT = typename ContextT::BlockT;

262 using FunctionT = typename ContextT::FunctionT;

265

266private:

267 ContextT Context;

268

269

271

272

274

275

276

277

278

279 std::vector<std::unique_ptr> TopLevelCycles;

280

281

282

283

284

285 void moveTopLevelCycleToNewParent(CycleT *NewParent, CycleT *Child);

286

287public:

291

295

298

304

305

306

307

308

310

311

312

318

319

320

321

323 typename std::vector<std::unique_ptr>::const_iterator;

326 const_toplevel_iterator_base> {

329

333

336 };

337

339 return const_toplevel_iterator{TopLevelCycles.begin()};

340 }

342 return const_toplevel_iterator{TopLevelCycles.end()};

343 }

344

346 return llvm::make_range(const_toplevel_iterator{TopLevelCycles.begin()},

347 const_toplevel_iterator{TopLevelCycles.end()});

348 }

349

350};

351

352

353template <typename CycleRefT, typename ChildIteratorT> struct CycleGraphTraits {

355

358

360

362 return Ref->child_begin();

363 }

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385};

386

387template

391template

395

396}

397

398#endif

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

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

This file defines the DenseSet and SmallDenseSet classes.

This file defines the little GenericSSAContext template class that can be used to implement IR ana...

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

This file implements a set that has insertion order iteration characteristics.

Implements a dense probed hash-table based set.

Helper class for computing cycle information.

Cycle information for a function.

Definition GenericCycleInfo.h:258

typename ContextT::FunctionT FunctionT

Definition GenericCycleInfo.h:262

GenericCycleInfo()=default

void verify() const

Verify that the entire cycle tree well-formed.

void addBlockToCycle(BlockT *Block, CycleT *Cycle)

Assumes that Cycle is the innermost cycle containing Block.

typename std::vector< std::unique_ptr< CycleT > >::const_iterator const_toplevel_iterator_base

Iteration over top-level cycles.

Definition GenericCycleInfo.h:322

iterator_range< const_toplevel_iterator > toplevel_cycles() const

Definition GenericCycleInfo.h:345

CycleT * getSmallestCommonCycle(BlockT *A, BlockT *B) const

Find the innermost cycle containing both given blocks.

friend class GenericCycleInfoCompute

Definition GenericCycleInfo.h:264

const_toplevel_iterator toplevel_end() const

Definition GenericCycleInfo.h:341

const FunctionT * getFunction() const

Definition GenericCycleInfo.h:296

friend class GenericCycle

Definition GenericCycleInfo.h:263

void print(raw_ostream &Out) const

Print the cycle info.

CycleT * getSmallestCommonCycle(CycleT *A, CycleT *B) const

Find the innermost cycle containing both given cycles.

GenericCycleInfo & operator=(GenericCycleInfo &&)=default

void clear()

Reset the object to its initial state.

GenericCycle< ContextT > CycleT

Definition GenericCycleInfo.h:261

void compute(FunctionT &F)

Compute the cycle info for a function.

void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)

const ContextT & getSSAContext() const

Definition GenericCycleInfo.h:297

void dump() const

Definition GenericCycleInfo.h:316

GenericCycleInfo(GenericCycleInfo &&)=default

Printable print(const CycleT *Cycle)

Definition GenericCycleInfo.h:317

unsigned getCycleDepth(const BlockT *Block) const

get the depth for the cycle which containing a given block.

void verifyCycleNest(bool VerifyFull=false) const

Methods for debug and self-test.

typename ContextT::BlockT BlockT

Definition GenericCycleInfo.h:260

CycleT * getTopLevelParentCycle(BlockT *Block)

const_toplevel_iterator toplevel_begin() const

Definition GenericCycleInfo.h:338

CycleT * getCycle(const BlockT *Block) const

Find the innermost cycle containing a given block.

A possibly irreducible generalization of a Loop.

Definition GenericCycleInfo.h:44

void clearCache() const

Clear the cache of the cycle.

Definition GenericCycleInfo.h:119

BlockT * getHeader() const

Definition GenericCycleInfo.h:110

bool isReducible() const

Whether the cycle is a natural loop.

Definition GenericCycleInfo.h:108

typename ContextT::FunctionT FunctionT

Definition GenericCycleInfo.h:47

const_entry_iterator entry_end() const

Definition GenericCycleInfo.h:220

friend class GenericCycleInfoCompute

Definition GenericCycleInfo.h:49

void getExitingBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const

Return all blocks of this cycle that have successor outside of this cycle.

const_entry_iterator entry_begin() const

Definition GenericCycleInfo.h:219

void verifyCycle() const

Verify that this is actually a well-formed cycle in the CFG.

const_child_iterator child_begin() const

Definition GenericCycleInfo.h:186

iterator_range< const_entry_iterator > entries() const

Definition GenericCycleInfo.h:222

void verifyCycleNest() const

Verify the parent-child relations of this cycle.

typename SmallVectorImpl< BlockT * >::const_reverse_iterator const_reverse_entry_iterator

Definition GenericCycleInfo.h:225

Printable print(const ContextT &Ctx) const

Definition GenericCycleInfo.h:243

iterator_range< const_block_iterator > blocks() const

Definition GenericCycleInfo.h:210

const SmallVectorImpl< BlockT * > & getEntries() const

Definition GenericCycleInfo.h:112

BlockT * getCyclePreheader() const

Return the preheader block for this cycle.

typename BlockSetVectorT::const_iterator const_block_iterator

Iteration over blocks in the cycle (including entry blocks).

Definition GenericCycleInfo.h:201

bool isEntry(const BlockT *Block) const

Return whether Block is an entry block of the cycle.

Definition GenericCycleInfo.h:122

const_reverse_entry_iterator entry_rend() const

Definition GenericCycleInfo.h:228

const_block_iterator block_begin() const

Definition GenericCycleInfo.h:203

const_reverse_entry_iterator entry_rbegin() const

Definition GenericCycleInfo.h:227

void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const

Return all of the successor blocks of this cycle.

BlockT * getCyclePredecessor() const

If the cycle has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.

bool contains(const BlockT *Block) const

Return whether Block is contained in the cycle.

Definition GenericCycleInfo.h:135

Printable printEntries(const ContextT &Ctx) const

Definition GenericCycleInfo.h:231

size_t getNumEntries() const

Definition GenericCycleInfo.h:221

const_child_iterator child_end() const

Definition GenericCycleInfo.h:189

size_t getNumChildren() const

Definition GenericCycleInfo.h:192

typename SmallVectorImpl< BlockT * >::const_iterator const_entry_iterator

Iteration over entry blocks.

Definition GenericCycleInfo.h:217

typename ContextT::BlockT BlockT

Definition GenericCycleInfo.h:46

const GenericCycle * getParentCycle() const

Definition GenericCycleInfo.h:143

void setSingleEntry(BlockT *Block)

Replace all entries with Block as single entry.

Definition GenericCycleInfo.h:127

GenericCycle * getParentCycle()

Definition GenericCycleInfo.h:144

friend class GenericCycleInfo

Definition GenericCycleInfo.h:48

unsigned getDepth() const

Definition GenericCycleInfo.h:145

const_block_iterator block_end() const

Definition GenericCycleInfo.h:206

typename std::vector< std::unique_ptr< GenericCycle > >::const_iterator const_child_iterator_base

Iteration over child cycles.

Definition GenericCycleInfo.h:172

size_t getNumBlocks() const

Definition GenericCycleInfo.h:209

iterator_range< const_child_iterator > children() const

Definition GenericCycleInfo.h:193

Simple wrapper around std::function<void(raw_ostream&)>.

A vector that has set insertion semantics.

typename vector_type::const_iterator const_iterator

bool insert(const value_type &X)

Insert a new element into the SetVector.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

typename SuperClass::const_iterator const_iterator

void push_back(const T &Elt)

std::reverse_iterator< const_iterator > const_reverse_iterator

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

const const_child_iterator_base & wrapped() const

const_child_iterator_base I

iterator_adaptor_base()=default

A range adaptor for a pair of iterators.

This class implements an extremely fast bulk output stream that can only output to a stream.

@ C

The default llvm calling convention, compatible with C.

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.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

@ Ref

The access may reference the value stored in memory.

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

GraphTraits for iterating over a sub-tree of the CycleT tree.

Definition GenericCycleInfo.h:353

static ChildIteratorType child_begin(NodeRef Ref)

Definition GenericCycleInfo.h:361

nodes_iterator ChildIteratorType

Definition GenericCycleInfo.h:357

ChildIteratorT nodes_iterator

Definition GenericCycleInfo.h:356

static NodeRef getEntryNode(NodeRef Graph)

Definition GenericCycleInfo.h:359

static ChildIteratorType child_end(NodeRef Ref)

Definition GenericCycleInfo.h:364

CycleRefT NodeRef

Definition GenericCycleInfo.h:354

const_toplevel_iterator()=default

iterator_adaptor_base< const_toplevel_iterator, const_toplevel_iterator_base > Base

Definition GenericCycleInfo.h:327

const const_toplevel_iterator_base & wrapped()

Definition GenericCycleInfo.h:334

const_toplevel_iterator(const_toplevel_iterator_base I)

Definition GenericCycleInfo.h:331

CycleT * operator*() const

Definition GenericCycleInfo.h:335

Definition GenericCycleInfo.h:175

const_child_iterator()=default

const_child_iterator(const_child_iterator_base I)

Definition GenericCycleInfo.h:180

GenericCycle * operator*() const

Definition GenericCycleInfo.h:183

const const_child_iterator_base & wrapped()

Definition GenericCycleInfo.h:182

iterator_adaptor_base< const_child_iterator, const_child_iterator_base > Base

Definition GenericCycleInfo.h:176