LoopSimplifyCFG.cpp Source File (original) (raw)

32#include

33using namespace llvm;

35#define DEBUG_TYPE "loop-simplifycfg"

41 "Number of terminators folded to unconditional branches");

43 "Number of loop blocks deleted");

45 "Number of loop exiting edges deleted");

52 if (BranchInst *BI = dyn_cast(TI)) {

53 if (BI->isUnconditional())

54 return nullptr;

55 if (BI->getSuccessor(0) == BI->getSuccessor(1))

57 ConstantInt *Cond = dyn_cast(BI->getCondition());

59 return nullptr;

60 return Cond->isZero() ? BI->getSuccessor(1) : BI->getSuccessor(0);

61 }

63 if (SwitchInst *SI = dyn_cast(TI)) {

64 auto *CI = dyn_cast(SI->getCondition());

65 if (!CI)

66 return nullptr;

67 for (auto Case : SI->cases())

68 if (Case.getCaseValue() == CI)

69 return Case.getCaseSuccessor();

70 return SI->getDefaultDest();

71 }

73 return nullptr;

74}

78 Loop *LastLoop = nullptr) {

79 assert((!LastLoop || LastLoop->contains(FirstLoop->getHeader())) &&

80 "First loop is supposed to be inside of last loop!");

81 assert(FirstLoop->contains(BB) && "Must be a loop block!");

82 for (Loop *Current = FirstLoop; Current != LastLoop;

84 Current->removeBlockFromLoop(BB);

85}

91 Loop *Innermost = nullptr;

94 while (BBL && !BBL->contains(L.getHeader()))

96 if (BBL == &L)

98 if (!BBL)

99 continue;

101 Innermost = BBL;

102 }

103 return Innermost;

104}

105

106namespace {

107

108

109class ConstantTerminatorFoldingImpl {

110private:

119

120

121 bool HasIrreducibleCFG = false;

122

123

124

125

126

127

128

129

130 bool DeleteCurrentLoop = false;

131

132

133

135

136

138

139

141

142

144

146

147

148

150

151 void dump() const {

152 dbgs() << "Constant terminator folding for loop " << L << "\n";

153 dbgs() << "After terminator constant-folding, the loop will";

154 if (!DeleteCurrentLoop)

155 dbgs() << " not";

156 dbgs() << " be destroyed\n";

157 auto PrintOutVector = [&](const char *Message,

159 dbgs() << Message << "\n";

161 dbgs() << "\t" << BB->getName() << "\n";

162 };

163 auto PrintOutSet = [&](const char *Message,

165 dbgs() << Message << "\n";

167 dbgs() << "\t" << BB->getName() << "\n";

168 };

169 PrintOutVector("Blocks in which we can constant-fold terminator:",

170 FoldCandidates);

171 PrintOutSet("Live blocks from the original loop:", LiveLoopBlocks);

172 PrintOutVector("Dead blocks from the original loop:", DeadLoopBlocks);

173 PrintOutSet("Live exit blocks:", LiveExitBlocks);

174 PrintOutVector("Dead exit blocks:", DeadExitBlocks);

175 if (!DeleteCurrentLoop)

176 PrintOutSet("The following blocks will still be part of the loop:",

177 BlocksInLoopAfterFolding);

178 }

179

180

182 assert(DFS.isComplete() && "DFS is expected to be finished");

183

185 unsigned Current = 0;

187 RPO[*I] = Current++;

188

192 if (L.contains(Succ) && !LI.isLoopHeader(Succ) && RPO[BB] > RPO[Succ])

193

194

195

196 return true;

197 }

198 return false;

199 }

200

201

202

203 void analyze() {

205 assert(DFS.isComplete() && "DFS is expected to be finished");

206

207

208

209

210

211

212

213

214 if (hasIrreducibleCFG(DFS)) {

215 HasIrreducibleCFG = true;

216 return;

217 }

218

219

220 LiveLoopBlocks.insert(L.getHeader());

223

224

225 if (!LiveLoopBlocks.count(BB)) {

227 continue;

228 }

229

231

232

233

234

235

236 bool TakeFoldCandidate = TheOnlySucc && LI.getLoopFor(BB) == &L;

237 if (TakeFoldCandidate)

239

240

242 if (!TakeFoldCandidate || TheOnlySucc == Succ) {

243 if (L.contains(Succ))

244 LiveLoopBlocks.insert(Succ);

245 else

246 LiveExitBlocks.insert(Succ);

247 }

248 }

249

250

251

252 assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&

253 "Malformed block sets?");

254

255

256

257

259 L.getExitBlocks(ExitBlocks);

261 for (auto *ExitBlock : ExitBlocks)

262 if (!LiveExitBlocks.count(ExitBlock) &&

263 UniqueDeadExits.insert(ExitBlock).second &&

265 [this](BasicBlock *Pred) { return L.contains(Pred); }))

266 DeadExitBlocks.push_back(ExitBlock);

267

268

269

272 return false;

274 return !TheOnlySucc || TheOnlySucc == To || LI.getLoopFor(From) != &L;

275 };

276

277

278 DeleteCurrentLoop = !IsEdgeLive(L.getLoopLatch(), L.getHeader());

279

280

281

282 if (DeleteCurrentLoop)

283 return;

284

285

286

287 BlocksInLoopAfterFolding.insert(L.getLoopLatch());

288

289

290

291

292 auto BlockIsInLoop = [&](BasicBlock *BB) {

294 return BlocksInLoopAfterFolding.count(Succ) && IsEdgeLive(BB, Succ);

295 });

296 };

299 if (BlockIsInLoop(BB))

300 BlocksInLoopAfterFolding.insert(BB);

301 }

302

303 assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&

304 "Header not in loop?");

305 assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&

306 "All blocks that stay in loop should be live!");

307 }

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344 void handleDeadExits() {

345

346 if (DeadExitBlocks.empty())

347 return;

348

349

350

351 BasicBlock *Preheader = L.getLoopPreheader();

353 Preheader, Preheader->getTerminator(), &DT, &LI, MSSAU);

354

357 Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);

359

360 unsigned DummyIdx = 1;

361 for (BasicBlock *BB : DeadExitBlocks) {

362

363

365 for (auto &PN : BB->phis())

367

368 if (auto *LandingPad = dyn_cast(BB->getFirstNonPHI()))

370

374 I->eraseFromParent();

375 }

376

377 assert(DummyIdx != 0 && "Too many dead exits!");

378 DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);

379 DTUpdates.push_back({DominatorTree::Insert, Preheader, BB});

380 ++NumLoopExitsDeleted;

381 }

382

383 assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");

385

386

387

388

390

391

392

393 if (StillReachable != OuterLoop) {

396 for (auto *BB : L.blocks())

398 OuterLoop->removeChildLoop(&L);

399 if (StillReachable)

401 else

403

404

405

406

407 Loop *FixLCSSALoop = OuterLoop;

408 while (FixLCSSALoop->getParentLoop() != StillReachable)

410 assert(FixLCSSALoop && "Should be a loop!");

411

412 if (MSSAU)

413 MSSAU->applyUpdates(DTUpdates, DT, true);

414 else

416 DTUpdates.clear();

419 }

420 }

421

422 if (MSSAU) {

423

424 MSSAU->applyUpdates(DTUpdates, DT, true);

425 DTUpdates.clear();

428 }

429 }

430

431

432

433 void deleteDeadLoopBlocks() {

434 if (MSSAU) {

436 DeadLoopBlocks.end());

438 }

439

440

441

442

443

444

445

446 for (auto *BB : DeadLoopBlocks)

448 assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");

450 if (->isOutermost()) {

451 for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())

452 for (auto *BB : DL->getBlocks())

453 PL->removeBlockFromLoop(BB);

454 DL->getParentLoop()->removeChildLoop(DL);

456 }

458 }

459

460 for (auto *BB : DeadLoopBlocks) {

461 assert(BB != L.getHeader() &&

462 "Header of the current loop cannot be dead!");

464 << "\n");

466 }

467

468 detachDeadBlocks(DeadLoopBlocks, &DTUpdates, true);

470 DTUpdates.clear();

471 for (auto *BB : DeadLoopBlocks)

473

474 NumLoopBlocksDeleted += DeadLoopBlocks.size();

475 }

476

477

478

479 void foldTerminators() {

480 for (BasicBlock *BB : FoldCandidates) {

481 assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");

483 assert(TheOnlySucc && "Should have one live successor!");

484

486 << " with an unconditional branch to the block "

487 << TheOnlySucc->getName() << "\n");

488

490

491 unsigned TheOnlySuccDuplicates = 0;

493 if (Succ != TheOnlySucc) {

494 DeadSuccessors.insert(Succ);

495

496

497 bool PreserveLCSSAPhi = .contains(Succ);

499 if (MSSAU)

501 } else

502 ++TheOnlySuccDuplicates;

503

504 assert(TheOnlySuccDuplicates > 0 && "Should be!");

505

506

507

508 bool PreserveLCSSAPhi = .contains(TheOnlySucc);

509 for (unsigned Dup = 1; Dup < TheOnlySuccDuplicates; ++Dup)

511 if (MSSAU && TheOnlySuccDuplicates > 1)

513

516 Builder.SetInsertPoint(Term);

517 Builder.CreateBr(TheOnlySucc);

518 Term->eraseFromParent();

519

520 for (auto *DeadSucc : DeadSuccessors)

521 DTUpdates.push_back({DominatorTree::Delete, BB, DeadSucc});

522

523 ++NumTerminatorsFolded;

524 }

525 }

526

527public:

531 : L(L), LI(LI), DT(DT), SE(SE), MSSAU(MSSAU), DFS(&L),

533 bool run() {

534 assert(L.getLoopLatch() && "Should be single latch!");

535

536

537

538 analyze();

540 (void)Header;

541

542 LLVM_DEBUG(dbgs() << "In function " << Header->getParent()->getName()

543 << ": ");

544

545 if (HasIrreducibleCFG) {

546 LLVM_DEBUG(dbgs() << "Loops with irreducible CFG are not supported!\n");

547 return false;

548 }

549

550

551 if (FoldCandidates.empty()) {

553 dbgs() << "No constant terminator folding candidates found in loop "

554 << Header->getName() << "\n");

555 return false;

556 }

557

558

559 if (DeleteCurrentLoop) {

562 << "Give up constant terminator folding in loop " << Header->getName()

563 << ": we don't currently support deletion of the current loop.\n");

564 return false;

565 }

566

567

568

569 if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=

570 L.getNumBlocks()) {

572 dbgs() << "Give up constant terminator folding in loop "

573 << Header->getName() << ": we don't currently"

574 " support blocks that are not dead, but will stop "

575 "being a part of the loop after constant-folding.\n");

576 return false;

577 }

578

579

580

581

582 if (!DeadExitBlocks.empty() && .isLCSSAForm(DT, false)) {

583 assert(L.isLCSSAForm(DT, true) &&

584 "LCSSA broken not by tokens?");

585 LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "

586 << Header->getName()

587 << ": tokens uses potentially break LCSSA form.\n");

588 return false;

589 }

590

592

594

595 LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()

596 << " terminators in loop " << Header->getName() << "\n");

597

598 if (!DeadLoopBlocks.empty())

600

601

602 handleDeadExits();

603 foldTerminators();

604

605 if (!DeadLoopBlocks.empty()) {

606 LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()

607 << " dead blocks in loop " << Header->getName() << "\n");

608 deleteDeadLoopBlocks();

609 } else {

610

612 DTUpdates.clear();

613 }

614

617

618#ifndef NDEBUG

619

620#if defined(EXPENSIVE_CHECKS)

621 assert(DT.verify(DominatorTree::VerificationLevel::Full) &&

622 "DT broken after transform!");

623#else

624 assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&

625 "DT broken after transform!");

626#endif

629#endif

630

631 return true;

632 }

633

634 bool foldingBreaksCurrentLoop() const {

635 return DeleteCurrentLoop;

636 }

637};

638}

639

640

641

645 bool &IsLoopDeleted) {

647 return false;

648

649

650

651 if (!L.getLoopLatch())

652 return false;

653

654 ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE, MSSAU);

656 IsLoopDeleted = Changed && BranchFolder.foldingBreaksCurrentLoop();

657 return Changed;

658}

659

663 bool Changed = false;

664 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);

665

666

668

670

671

673 if (!Succ)

674 continue;

675

678 continue;

679

680

682

685

686 Changed = true;

687 }

688

689 if (Changed)

691

692 return Changed;

693}

694

697 bool &IsLoopDeleted) {

698 bool Changed = false;

699

700

702

703 if (IsLoopDeleted)

704 return true;

705

706

708

709 if (Changed)

711

712 return Changed;

713}

714

718 std::optional MSSAU;

721 bool DeleteCurrentLoop = false;

723 DeleteCurrentLoop))

725

726 if (DeleteCurrentLoop)

728

732 return PA;

733}

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

BlockVerifier::State From

DenseMap< Block *, BlockRelaxAux > Blocks

This header provides classes for managing a pipeline of passes over loops in LLVM IR.

static BasicBlock * getOnlyLiveSuccessor(BasicBlock *BB)

If BB is a switch or a conditional branch, but only one of its successors can be reached from this bl...

static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)

Turn branches and switches with known constant conditions into unconditional branches.

static Loop * getInnermostLoopFor(SmallPtrSetImpl< BasicBlock * > &BBs, Loop &L, LoopInfo &LI)

Find innermost loop that contains at least one block from BBs and contains the header of loop L.

static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution &SE)

static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution &SE, MemorySSAUpdater *MSSAU, bool &IsLoopDeleted)

static cl::opt< bool > EnableTermFolding("enable-loop-simplifycfg-term-folding", cl::init(true))

static void removeBlockFromLoops(BasicBlock *BB, Loop *FirstLoop, Loop *LastLoop=nullptr)

Removes BB from all loops from [FirstLoop, LastLoop) in parent chain.

This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...

const SmallVectorImpl< MachineOperand > & Cond

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

This file defines the SmallVector class.

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

A container for analyses that lazily runs them and caches their results.

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

Returns a range that iterates over the phis in the basic block.

const Instruction * getFirstNonPHI() const

Returns a pointer to the first instruction in this block that is not a PHINode instruction.

const BasicBlock * getSinglePredecessor() const

Return the predecessor of this block if it has a single predecessor block.

const BasicBlock * getSingleSuccessor() const

Return the successor of this block if it has a single successor.

LLVMContext & getContext() const

Get the context in which this basic block lives.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)

Update PHI nodes in this BasicBlock before removal of predecessor Pred.

Conditional or Unconditional Branch instruction.

This is the shared class of boolean and integer constants.

void deleteBB(BasicBlock *DelBB)

Delete DelBB.

bool verify(VerificationLevel VL=VerificationLevel::Full) const

verify - checks if the tree is correct.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

void applyUpdates(ArrayRef< UpdateT > Updates)

Submit updates to all available trees.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

void markLoopAsDeleted(Loop &L, llvm::StringRef Name)

Loop passes should use this method to indicate they have deleted a loop from the nest.

bool contains(const LoopT *L) const

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

BlockT * getHeader() const

unsigned getLoopDepth() const

Return the nesting level of this loop.

void addChildLoop(LoopT *NewChild)

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

LoopT * getParentLoop() const

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

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

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

RPOIterator endRPO() const

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

void addTopLevelLoop(LoopT *New)

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

void removeBlock(BlockT *BB)

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

bool isLoopHeader(const BlockT *BB) const

void changeLoopFor(BlockT *BB, LoopT *L)

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

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

MemorySSA * getMemorySSA() const

Get handle on MemorySSA.

void removeEdge(BasicBlock *From, BasicBlock *To)

Update the MemoryPhi in To following an edge deletion between From and To.

void removeDuplicatePhiEdgesBetween(const BasicBlock *From, const BasicBlock *To)

Update the MemoryPhi in To to have a single incoming edge from From, following a CFG change that repl...

void removeBlocks(const SmallSetVector< BasicBlock *, 8 > &DeadBlocks)

Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.

void applyUpdates(ArrayRef< CFGUpdate > Updates, DominatorTree &DT, bool UpdateDTFirst=false)

Apply CFG updates, analogous with the DT edge updates.

void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const

Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

The main scalar evolution driver.

void forgetTopmostLoop(const Loop *L)

void forgetBlockAndLoopDispositions(Value *V=nullptr)

Called when the client has changed the disposition of values in a loop or block.

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

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.

A SetVector that performs no allocations if smaller than a certain size.

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

void addCase(ConstantInt *OnVal, BasicBlock *Dest)

Add an entry to the switch instruction.

StringRef getName() const

Return a constant reference to the value's name.

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

This is an optimization pass for GlobalISel generic memory operations.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

bool all_of(R &&range, UnaryPredicate P)

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

void detachDeadBlocks(ArrayRef< BasicBlock * > BBs, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs=false)

Replace contents of every block in BBs with single unreachable instruction.

auto successors(const MachineBasicBlock *BB)

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

bool any_of(R &&range, UnaryPredicate P)

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

raw_ostream & dbgs()

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

bool VerifyMemorySSA

Enables verification of MemorySSA.

bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)

Attempts to merge a block into its predecessor, if possible.

BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

PreservedAnalyses getLoopPassPreservedAnalyses()

Returns the minimum set of Analyses that all loop passes must preserve.

auto predecessors(const MachineBasicBlock *BB)

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...