GenericLoopInfo.h Source File (original) (raw)

40#ifndef LLVM_SUPPORT_GENERICLOOPINFO_H

41#define LLVM_SUPPORT_GENERICLOOPINFO_H

50namespace llvm {

52template <class N, class M> class LoopInfoBase;

53template <class N, class M> class LoopBase;

59template <class BlockT, class LoopT> class LoopBase {

60 LoopT *ParentLoop;

62 std::vector<LoopT *> SubLoops;

65 std::vector<BlockT *> Blocks;

69#if LLVM_ENABLE_ABI_BREAKING_CHECKS

71 bool IsInvalid = false;

72#endif

78public:

84 unsigned D = 1;

85 for (const LoopT *CurLoop = ParentLoop; CurLoop;

86 CurLoop = CurLoop->ParentLoop)

87 ++D;

88 return D;

89 }

100

101

102

104 const LoopT *L = static_cast<const LoopT *>(this);

105 while (L->ParentLoop)

106 L = L->ParentLoop;

107 return L;

108 }

109

111 LoopT *L = static_cast<LoopT *>(this);

112 while (L->ParentLoop)

113 L = L->ParentLoop;

114 return L;

115 }

116

117

120 ParentLoop = L;

121 }

122

123

126 if (L == this)

127 return true;

128 if (!L)

129 return false;

130 return contains(L->getParentLoop());

131 }

132

133

136 return DenseBlockSet.count(BB);

137 }

138

139

140 template bool contains(const InstT *Inst) const {

141 return contains(Inst->getParent());

142 }

143

144

147 return SubLoops;

148 }

151 return SubLoops;

152 }

153 typedef typename std::vector<LoopT *>::const_iterator iterator;

154 typedef

160

161

162

163

164

165

166

168

169

171

172

176 }

183 }

184

185

186

189 return Blocks.size();

190 }

191

192

193

197 }

198

199

202 return DenseBlockSet;

203 }

204

205

208 return DenseBlockSet;

209 }

210

211

212

213

214

215

216

218#if LLVM_ENABLE_ABI_BREAKING_CHECKS

219 return IsInvalid;

220#else

221 return false;

222#endif

223 }

224

225

226

229 assert(contains(BB) && "Exiting block must be part of the loop");

230 for (const auto *Succ : children<const BlockT *>(BB)) {

232 return true;

233 }

234 return false;

235 }

236

237

238

239

240

243 assert(contains(BB) && "block does not belong to the loop");

245 }

246

247

251 [&](BlockT *Pred) { return contains(Pred); });

252 }

253

254

255

256

257

258

259

260

261

262

263

264

266

267

268

270

271

272

274

275

276

278

279

280

282

283

284

286

287

288

289

290

292

293

294

296

297

298

300

301

303

304

305 typedef std::pair<BlockT *, BlockT *> Edge;

306

307

309

310

311

312

313

314

315

317

318

319

320

321

323

324

325

327

328

329

333 for (const auto Pred : inverse_children<BlockT *>(H))

336 }

337

338

339

340 template

344 PreOrderWorklist.append(L.rbegin(), L.rend());

345

346 while (!PreOrderWorklist.empty()) {

348

349

350 PreOrderWorklist.append(L->rbegin(), L->rend());

352 }

353 }

354

355

356

359 const LoopT *CurLoop = static_cast<const LoopT *>(this);

360 PreOrderLoops.push_back(CurLoop);

362 return PreOrderLoops;

363 }

366 LoopT *CurLoop = static_cast<LoopT *>(this);

367 PreOrderLoops.push_back(CurLoop);

369 return PreOrderLoops;

370 }

371

372

373

374

375

376

377

378

379

380

382

383

384

385

386

388

389

390

393 assert(!NewChild->ParentLoop && "NewChild already has a parent!");

394 NewChild->ParentLoop = static_cast<LoopT *>(this);

395 SubLoops.push_back(NewChild);

396 }

397

398

399

402 assert(I != SubLoops.end() && "Cannot remove end iterator!");

403 LoopT *Child = *I;

404 assert(Child->ParentLoop == this && "Child is not a child of this loop!");

405 SubLoops.erase(SubLoops.begin() + (I - begin()));

406 Child->ParentLoop = nullptr;

407 return Child;

408 }

409

410

411

414 }

415

416

417

418

421 Blocks.push_back(BB);

422 DenseBlockSet.insert(BB);

423 }

424

425

428 std::reverse(Blocks.begin() + from, Blocks.end());

429 }

430

431

435 }

436

437

438

442 return;

443 for (unsigned i = 0;; ++i) {

444 assert(i != Blocks.size() && "Loop does not contain BB!");

445 if (Blocks[i] == BB) {

448 return;

449 }

450 }

451 }

452

453

454

455

459 assert(I != Blocks.end() && "N is not in this list!");

461

462 DenseBlockSet.erase(BB);

463 }

464

465

467

468

470

471

472

473

474

476

477

479 unsigned Depth = 0) const;

480

481protected:

483

484

486

487 explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) {

488 Blocks.push_back(BB);

489 DenseBlockSet.insert(BB);

490 }

491

492

493

494

495

496

497

498

499

500

502 for (auto *SubLoop : SubLoops)

503 SubLoop->~LoopT();

504

505#if LLVM_ENABLE_ABI_BREAKING_CHECKS

506 IsInvalid = true;

507#endif

508 SubLoops.clear();

510 DenseBlockSet.clear();

511 ParentLoop = nullptr;

512 }

513};

514

515template <class BlockT, class LoopT>

518 return OS;

519}

520

521

522

523

524

525

527

529 std::vector<LoopT *> TopLevelLoops;

531

532 friend class LoopBase<BlockT, LoopT>;

534

535 void operator=(const LoopInfoBase &) = delete;

537

538public:

541

543 : BBMap(std::move(Arg.BBMap)),

544 TopLevelLoops(std::move(Arg.TopLevelLoops)),

545 LoopAllocator(std::move(Arg.LoopAllocator)) {

546

547 Arg.TopLevelLoops.clear();

548 }

550 BBMap = std::move(RHS.BBMap);

551

552 for (auto *L : TopLevelLoops)

553 L->~LoopT();

554

555 TopLevelLoops = std::move(RHS.TopLevelLoops);

556 LoopAllocator = std::move(RHS.LoopAllocator);

557 RHS.TopLevelLoops.clear();

558 return *this;

559 }

560

563

564 for (auto *L : TopLevelLoops)

565 L->~LoopT();

566 TopLevelLoops.clear();

567 LoopAllocator.Reset();

568 }

569

570 template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&...Args) {

571 LoopT *Storage = LoopAllocator.Allocate();

572 return new (Storage) LoopT(std::forward(Args)...);

573 }

574

575

576

577

578 typedef typename std::vector<LoopT *>::const_iterator iterator;

579 typedef

585 bool empty() const { return TopLevelLoops.empty(); }

586

587

588

589

590

591

593

594

595

596

597

598

599

600

601

603

604

605

607

608

610

611

612

615 return L ? L->getLoopDepth() : 0;

616 }

617

618

621 return L && L->getHeader() == BB;

622 }

623

624

625 const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }

626

627

629

630

631

632

634 assert(I != end() && "Cannot remove end iterator!");

635 LoopT *L = *I;

636 assert(L->isOutermost() && "Not a top-level loop!");

637 TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));

638 return L;

639 }

640

641

642

643

645 if (!L) {

647 return;

648 }

649 BBMap[BB] = L;

650 }

651

652

653

655 auto I = find(TopLevelLoops, OldLoop);

656 assert(I != TopLevelLoops.end() && "Old loop not at top level!");

657 *I = NewLoop;

658 assert(!NewLoop->ParentLoop && !OldLoop->ParentLoop &&

659 "Loops already embedded into a subloop!");

660 }

661

662

664 assert(New->isOutermost() && "Loop already in subloop!");

665 TopLevelLoops.push_back(New);

666 }

667

668

669

670

672 auto I = BBMap.find(BB);

673 if (I != BBMap.end()) {

674 for (LoopT *L = I->second; L; L = L->getParentLoop())

675 L->removeBlockFromLoop(BB);

676

678 }

679 }

680

681

682

684 const LoopT *ParentLoop) {

685 if (!SubLoop)

686 return true;

687 if (SubLoop == ParentLoop)

688 return false;

690 }

691

692

694

695

697

699

700

701

702

703

704

705

706

707

708

709

711 L->~LoopT();

712

713

714

716 }

717};

718

719}

720

721#endif

This file defines the BumpPtrAllocator interface.

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

This file defines the DenseSet and SmallDenseSet classes.

DenseMap< Block *, BlockRelaxAux > Blocks

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

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

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

This file defines generic set operations that may be used on set's of different types,...

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Allocate memory in an ever growing pool, as if by bump-pointer.

LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)

Allocate space at the specified alignment.

void Reset()

Deallocate all but the current slab and reset the current pointer to the beginning of it,...

void Deallocate(const void *Ptr, size_t Size, size_t)

ValueT lookup(const_arg_type_t< KeyT > Val) const

lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...

iterator find(const_arg_type_t< KeyT > Val)

bool erase(const KeyT &Val)

Implements a dense probed hash-table based set.

Core dominator tree base class.

Instances of this class are used to represent loops that are detected in the flow graph.

bool isAnnotatedParallel() const

Returns true if the loop is annotated parallel.

bool contains(const LoopT *L) const

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

SmallPtrSetImpl< const BlockT * > & getBlocksSet()

Return a direct, mutable handle to the blocks set so that we can mutate it efficiently.

static void getInnerLoopsInPreorder(const LoopT &L, SmallVectorImpl< Type > &PreOrderLoops)

Return all inner loops in the loop nest rooted by the loop in preorder, with siblings in forward prog...

bool isOutermost() const

Return true if the loop does not have a parent (natural) loop.

BlockT * getLoopLatch() const

If there is a single latch block for this loop, return it.

bool isInnermost() const

Return true if the loop does not contain any (natural) loops.

void removeBlockFromLoop(BlockT *BB)

This removes the specified basic block from the current loop, updating the Blocks as appropriate.

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

Return all of the successor blocks of this loop.

bool contains(const InstT *Inst) const

Return true if the specified instruction is in this loop.

unsigned getNumBlocks() const

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

void verifyLoop() const

Verify loop structure.

void verifyLoopNest(DenseSet< const LoopT * > *Loops) const

Verify loop structure of this loop and all nested loops.

SmallVector< LoopT *, 4 > getLoopsInPreorder()

unsigned getNumBackEdges() const

Calculate the number of back edges to the loop header.

void reverseBlock(unsigned from)

interface to reverse Blocks[from, end of loop] in this loop

SmallVector< const LoopT *, 4 > getLoopsInPreorder() const

Return all loops in the loop nest rooted by the loop in preorder, with siblings in forward program or...

BlockT * getUniqueLatchExitBlock() const

Return the unique exit block for the latch, or null if there are multiple different exit blocks or th...

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

Return all blocks inside the loop that have successors outside of the loop.

const std::vector< LoopT * > & getSubLoops() const

Return the loops contained entirely within this loop.

BlockT * getHeader() const

const LoopT * getOutermostLoop() const

Get the outermost loop in which this loop is contained.

void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const

Return all loop latch blocks of this loop.

unsigned getLoopDepth() const

Return the nesting level of this loop.

LoopBase()

This creates an empty loop.

void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const

Print loop with all the BBs inside it.

void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase< BlockT, LoopT > &LI)

This method is used by other analyses to update loop information.

std::vector< BlockT * > & getBlocksVector()

Return a direct, mutable handle to the blocks vector so that we can mutate it efficiently with techni...

std::vector< LoopT * >::const_reverse_iterator reverse_iterator

LoopT * removeChildLoop(LoopT *Child)

This removes the specified child from being a subloop of this loop.

std::vector< LoopT * >::const_iterator iterator

void reserveBlocks(unsigned size)

interface to do reserve() for Blocks

iterator_range< block_iterator > blocks() const

block_iterator block_end() const

std::pair< BlockT *, BlockT * > Edge

Edge type.

bool isInvalid() const

Return true if this loop is no longer valid.

BlockT * getLoopPredecessor() const

If the given loop's header has exactly one unique predecessor outside the loop, return it.

bool contains(const BlockT *BB) const

Return true if the specified basic block is in this loop.

bool isLoopLatch(const BlockT *BB) const

void addChildLoop(LoopT *NewChild)

Add the specified loop to be a child of this loop.

void getExitEdges(SmallVectorImpl< Edge > &ExitEdges) const

Return all pairs of (inside_block,outside_block).

void addBlockEntry(BlockT *BB)

This adds a basic block directly to the basic block list.

ArrayRef< BlockT * >::const_iterator block_iterator

std::vector< LoopT * > & getSubLoopsVector()

reverse_iterator rbegin() const

BlockT * getExitBlock() const

If getExitBlocks would return exactly one block, return that block.

bool hasNoExitBlocks() const

Return true if this loop does not have any exit blocks.

void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild)

This is used when splitting loops up.

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

ArrayRef< BlockT * > getBlocks() const

Get a list of the basic blocks which make up this loop.

reverse_iterator rend() const

BlockT * getExitingBlock() const

If getExitingBlocks would return exactly one block, return that block.

LoopT * getOutermostLoop()

void getUniqueExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const

Return all unique successor blocks of this loop.

void setParentLoop(LoopT *L)

This is a raw interface for bypassing addChildLoop.

LoopT * getParentLoop() const

Return the parent loop if it exists or nullptr for top level loops.

bool hasDedicatedExits() const

Return true if no exit block for the loop has a predecessor that is outside the loop.

void getUniqueNonLatchExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const

Return all unique successor blocks of this loop except successors from Latch block are not considered...

const SmallPtrSetImpl< const BlockT * > & getBlocksSet() const

Return a direct, immutable handle to the blocks set.

bool isLoopExiting(const BlockT *BB) const

True if terminator in the block can branch to another block that is outside of the current loop.

block_iterator block_begin() const

void moveToHeader(BlockT *BB)

This method is used to move BB (which must be part of this loop) to be the loop header of the loop (t...

BlockT * getUniqueExitBlock() const

If getUniqueExitBlocks would return exactly one block, return that block.

LoopT * removeChildLoop(iterator I)

This removes the specified child from being a subloop of this loop.

This class builds and contains all of the top-level loop structures in the specified function.

const std::vector< LoopT * > & getTopLevelLoops() const

Return the top-level loops.

void addTopLevelLoop(LoopT *New)

This adds the specified loop to the collection of top-level loops.

void analyze(const DominatorTreeBase< BlockT, false > &DomTree)

Create the loop forest using a stable algorithm.

SmallVector< LoopT *, 4 > getLoopsInReverseSiblingPreorder() const

Return all of the loops in the function in preorder across the loop nests, with siblings in reverse p...

void print(raw_ostream &OS) const

reverse_iterator rend() const

void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)

Replace the specified loop in the top-level loops list with the indicated loop.

void removeBlock(BlockT *BB)

This method completely removes BB from all data structures, including all of the Loop objects it is n...

LoopInfoBase(LoopInfoBase &&Arg)

LoopT * AllocateLoop(ArgsTy &&...Args)

const LoopT * operator[](const BlockT *BB) const

Same as getLoopFor.

bool isLoopHeader(const BlockT *BB) const

LoopT * removeLoop(iterator I)

This removes the specified top-level loop from this loop info object.

SmallVector< LoopT *, 4 > getLoopsInPreorder() const

Return all of the loops in the function in preorder across the loop nests, with siblings in forward p...

void changeLoopFor(BlockT *BB, LoopT *L)

Change the top-level loop that contains BB to the specified loop.

unsigned getLoopDepth(const BlockT *BB) const

Return the loop nesting level of the specified block.

std::vector< LoopT * > & getTopLevelLoopsVector()

Return the top-level loops.

static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop)

std::vector< LoopT * >::const_reverse_iterator reverse_iterator

reverse_iterator rbegin() const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

LoopInfoBase & operator=(LoopInfoBase &&RHS)

void destroy(LoopT *L)

Destroy a loop that has been removed from the LoopInfo nest.

std::vector< LoopT * >::const_iterator iterator

iterator/begin/end - The interface to the top-level loops in the current function.

Represents a single loop in the control flow graph.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

bool erase(PtrType Ptr)

Remove pointer from the set.

size_type count(ConstPtrType Ptr) const

count - Return 1 if the specified pointer is in the set, 0 otherwise.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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.

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

This is an optimization pass for GlobalISel generic memory operations.

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

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

Convenience function for iterating over sub-ranges.

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

auto count_if(R &&Range, UnaryPredicate P)

Wrapper function around std::count_if to count the number of times an element satisfying a given pred...

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

Returns true if Element is found in Range.

Implement std::hash so that hash_code can be used in STL containers.