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

74 LoopBase(const LoopBase<BlockT, LoopT> &) = delete;

75 const LoopBase<BlockT, LoopT> &

76 operator=(const LoopBase<BlockT, LoopT> &) = delete;

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 using iterator = typename std::vector<LoopT *>::const_iterator;

155 typename std::vector<LoopT *>::const_reverse_iterator;

160

161

162

163

164

165

166

168

169

171

172

184

185

186

189 return Blocks.size();

190 }

191

192

193

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

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 using Edge = std::pair<BlockT *, BlockT *>;

306

307

309

310

311

312

313

314

315

317

318

319

320

321

323

324

325

327

328

329

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

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

434 Blocks.reserve(size);

435 }

436

437

438

441 if (Blocks[0] == BB)

442 return;

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

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

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

446 Blocks[i] = Blocks[0];

447 Blocks[0] = BB;

448 return;

449 }

450 }

451 }

452

453

454

455

458 auto I = find(Blocks, BB);

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

460 Blocks.erase(I);

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

509 Blocks.clear();

510 DenseBlockSet.clear();

511 ParentLoop = nullptr;

512 }

513};

514

515template <class BlockT, class LoopT>

520

521

522

523

524

525

526template <class BlockT, class LoopT> class LoopInfoBase {

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

562 BBMap.clear();

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 using iterator = typename std::vector<LoopT *>::const_iterator;

580 typename std::vector<LoopT *>::const_reverse_iterator;

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

606 LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); }

607

608

610

611

612

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

616 }

617

618

619

620

621

623

624

625

626

628

629

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

633 }

634

635

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

637

638

640

641

642

643

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

646 LoopT *L = *I;

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

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

649 return L;

650 }

651

652

653

654

656 if (!L) {

657 BBMap.erase(BB);

658 return;

659 }

660 BBMap[BB] = L;

661 }

662

663

664

666 auto I = find(TopLevelLoops, OldLoop);

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

668 *I = NewLoop;

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

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

671 }

672

673

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

676 TopLevelLoops.push_back(New);

677 }

678

679

680

681

683 auto I = BBMap.find(BB);

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

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

686 L->removeBlockFromLoop(BB);

687

688 BBMap.erase(I);

689 }

690 }

691

692

693

695 const LoopT *ParentLoop) {

696 if (!SubLoop)

697 return true;

698 if (SubLoop == ParentLoop)

699 return false;

701 }

702

703

705

706

708

710

711

712

713

714

715

716

717

718

719

720

722 L->~LoopT();

723

724

725

726 LoopAllocator.Deallocate(L);

727 }

728};

729

730}

731

732#endif

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

This file defines the BumpPtrAllocator interface.

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

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

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

This file defines the DenseSet and SmallDenseSet classes.

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.

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),...

const_pointer const_iterator

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.

Definition GenericLoopInfo.h:59

bool isAnnotatedParallel() const

Returns true if the loop is annotated parallel.

Definition GenericLoopInfo.h:475

bool contains(const LoopT *L) const

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

Definition GenericLoopInfo.h:124

SmallPtrSetImpl< const BlockT * > & getBlocksSet()

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

Definition GenericLoopInfo.h:200

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...

Definition GenericLoopInfo.h:341

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

Definition GenericLoopInfo.h:153

bool isOutermost() const

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

Definition GenericLoopInfo.h:170

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.

Definition GenericLoopInfo.h:167

void removeBlockFromLoop(BlockT *BB)

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

Definition GenericLoopInfo.h:456

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

Return all of the successor blocks of this loop.

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

Edge type.

Definition GenericLoopInfo.h:305

bool contains(const InstT *Inst) const

Return true if the specified instruction is in this loop.

Definition GenericLoopInfo.h:140

unsigned getNumBlocks() const

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

Definition GenericLoopInfo.h:187

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

Definition GenericLoopInfo.h:364

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

Definition GenericLoopInfo.h:154

unsigned getNumBackEdges() const

Calculate the number of back edges to the loop header.

Definition GenericLoopInfo.h:248

void reverseBlock(unsigned from)

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

Definition GenericLoopInfo.h:426

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...

Definition GenericLoopInfo.h:357

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.

LoopBase(BlockT *BB)

Definition GenericLoopInfo.h:487

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

Return the loops contained entirely within this loop.

Definition GenericLoopInfo.h:145

BlockT * getHeader() const

Definition GenericLoopInfo.h:90

const LoopT * getOutermostLoop() const

Get the outermost loop in which this loop is contained.

Definition GenericLoopInfo.h:103

~LoopBase()

Definition GenericLoopInfo.h:501

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

Return all loop latch blocks of this loop.

Definition GenericLoopInfo.h:330

unsigned getLoopDepth() const

Return the nesting level of this loop.

Definition GenericLoopInfo.h:82

LoopBase()

This creates an empty loop.

Definition GenericLoopInfo.h:485

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...

Definition GenericLoopInfo.h:194

LoopT * removeChildLoop(LoopT *Child)

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

Definition GenericLoopInfo.h:412

void reserveBlocks(unsigned size)

interface to do reserve() for Blocks

Definition GenericLoopInfo.h:432

iterator_range< block_iterator > blocks() const

Definition GenericLoopInfo.h:180

block_iterator block_end() const

Definition GenericLoopInfo.h:179

bool isInvalid() const

Return true if this loop is no longer valid.

Definition GenericLoopInfo.h:217

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.

Definition GenericLoopInfo.h:134

bool isLoopLatch(const BlockT *BB) const

Definition GenericLoopInfo.h:241

iterator end() const

Definition GenericLoopInfo.h:157

void addChildLoop(LoopT *NewChild)

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

Definition GenericLoopInfo.h:391

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.

Definition GenericLoopInfo.h:419

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

Definition GenericLoopInfo.h:149

reverse_iterator rbegin() const

Definition GenericLoopInfo.h:158

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.

Definition GenericLoopInfo.h:173

reverse_iterator rend() const

Definition GenericLoopInfo.h:159

BlockT * getExitingBlock() const

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

LoopT * getOutermostLoop()

Definition GenericLoopInfo.h:110

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.

Definition GenericLoopInfo.h:118

LoopT * getParentLoop() const

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

Definition GenericLoopInfo.h:99

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...

iterator begin() const

Definition GenericLoopInfo.h:156

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

Return a direct, immutable handle to the blocks set.

Definition GenericLoopInfo.h:206

bool isLoopExiting(const BlockT *BB) const

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

Definition GenericLoopInfo.h:227

block_iterator block_begin() const

Definition GenericLoopInfo.h:178

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...

Definition GenericLoopInfo.h:439

typename ArrayRef< BlockT * >::const_iterator block_iterator

Definition GenericLoopInfo.h:177

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.

Definition GenericLoopInfo.h:400

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

Definition GenericLoopInfo.h:526

~LoopInfoBase()

Definition GenericLoopInfo.h:540

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

Return the top-level loops.

Definition GenericLoopInfo.h:636

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

void addTopLevelLoop(LoopT *New)

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

Definition GenericLoopInfo.h:674

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

Definition GenericLoopInfo.h:584

void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)

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

Definition GenericLoopInfo.h:665

iterator end() const

Definition GenericLoopInfo.h:582

void removeBlock(BlockT *BB)

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

Definition GenericLoopInfo.h:682

LoopInfoBase(LoopInfoBase &&Arg)

Definition GenericLoopInfo.h:542

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

Definition GenericLoopInfo.h:570

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

Same as getLoopFor.

Definition GenericLoopInfo.h:609

bool isLoopHeader(const BlockT *BB) const

Definition GenericLoopInfo.h:630

LoopT * removeLoop(iterator I)

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

Definition GenericLoopInfo.h:644

LoopT * getSmallestCommonLoop(BlockT *A, BlockT *B) const

Find the innermost loop containing both given blocks.

bool empty() const

Definition GenericLoopInfo.h:585

SmallVector< LoopT *, 4 > getLoopsInPreorder() const

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

LoopT * getSmallestCommonLoop(LoopT *A, LoopT *B) const

Find the innermost loop containing both given loops.

void changeLoopFor(BlockT *BB, LoopT *L)

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

Definition GenericLoopInfo.h:655

typename std::vector< Loop * >::const_iterator iterator

Definition GenericLoopInfo.h:578

typename std::vector< Loop * >::const_reverse_iterator reverse_iterator

Definition GenericLoopInfo.h:579

unsigned getLoopDepth(const BlockT *BB) const

Return the loop nesting level of the specified block.

Definition GenericLoopInfo.h:613

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

Return the top-level loops.

Definition GenericLoopInfo.h:639

iterator begin() const

Definition GenericLoopInfo.h:581

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

Definition GenericLoopInfo.h:694

reverse_iterator rbegin() const

Definition GenericLoopInfo.h:583

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

Definition GenericLoopInfo.h:606

LoopInfoBase & operator=(LoopInfoBase &&RHS)

Definition GenericLoopInfo.h:549

void destroy(LoopT *L)

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

Definition GenericLoopInfo.h:721

void releaseMemory()

Definition GenericLoopInfo.h:561

friend class LoopInfo

Definition GenericLoopInfo.h:533

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...

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.

iterator_range< typename GraphTraits< Inverse< GraphType > >::ChildIteratorType > inverse_children(const typename GraphTraits< GraphType >::NodeRef &G)

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...

iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)

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

Returns true if Element is found in Range.

BumpPtrAllocatorImpl<> BumpPtrAllocator

The standard BumpPtrAllocator which just uses the default template parameters.

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