LoopDeletion.cpp Source File (original) (raw)

32using namespace llvm;

34#define DEBUG_TYPE "loop-delete"

36 STATISTIC(NumDeleted, "Number of loops deleted");

38 "Number of loops for which we managed to break the backedge");

41 "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true),

42 cl::desc("Break backedge through symbolic execution of 1st iteration "

43 "attempting to prove that the backedge is never taken"));

49};

57}

72 bool AllEntriesInvariant = true;

73 bool AllOutgoingValuesSame = true;

74 if (ExitBlock) {

76 Value *incoming = P.getIncomingValueForBlock(ExitingBlocks[0]);

82 AllOutgoingValuesSame =

84 return incoming == P.getIncomingValueForBlock(BB);

85 });

87 if (!AllOutgoingValuesSame)

88 break;

90 if (Instruction *I = dyn_cast(incoming)) {

91 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator(),

92 nullptr, &SE)) {

93 AllEntriesInvariant = false;

94 break;

95 }

96 }

97 }

98 }

100 if (!AllEntriesInvariant || !AllOutgoingValuesSame)

101 return false;

102

103

104

105

106 for (const auto &I : L->blocks())

108 return I.mayHaveSideEffects() && .isDroppable();

109 }))

110 return false;

111

112

113

114

115

116 if (L->getHeader()->getParent()->mustProgress())

117 return true;

118

121

122 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))

123 return false;

124

127 while (!WorkList.empty()) {

130 continue;

131

133 if (isa(S)) {

135 dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was "

136 "not required to make progress.\n");

137 return false;

138 }

140 }

141 return true;

142}

143

144

145

146

148 using namespace PatternMatch;

149

150 auto *Preheader = L->getLoopPreheader();

151

152

153 assert(Preheader && "Needs preheader!");

154

155 if (Preheader->isEntryBlock())

156 return false;

157

158

162 if ( match (Pred->getTerminator(),

164 return false;

165 if ( Cond ->getZExtValue())

167 if (Taken == Preheader)

168 return false;

169 }

171 "Preheader should have predecessors at this point!");

172

173 return true;

174}

175

179

180 if (!isa(V))

181 return V;

182

183 auto Existing = FirstIterValue.find(V);

184 if (Existing != FirstIterValue.end())

185 return Existing->second;

186 Value *FirstIterV = nullptr;

187 if (auto *BO = dyn_cast(V)) {

193 } else if (auto *Cmp = dyn_cast(V)) {

199 } else if (auto *Select = dyn_cast(V)) {

202 if (auto *C = dyn_cast(Cond)) {

203 auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()

204 : Select->getFalseValue();

206 }

207 }

208 if (!FirstIterV)

209 FirstIterV = V;

210 FirstIterValue[V] = FirstIterV;

211 return FirstIterV;

212}

213

214

215

218

220 return false;

221

222 BasicBlock *Predecessor = L->getLoopPredecessor();

223 BasicBlock *Latch = L->getLoopLatch();

224

225 if (!Predecessor || !Latch)

226 return false;

227

230

231

232

233

234

235

236 if (containsIrreducibleCFG<const BasicBlock *>(RPOT, LI))

237 return false;

238

240

242

244 LiveBlocks.insert(Header);

245

250 "Only canonical backedges are allowed. Irreducible CFG?");

252 "We already discarded this block as dead!");

253 LiveBlocks.insert(To);

255 };

256

257 auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {

259 MarkLiveEdge(BB, Succ);

260 };

261

262

263

264

265 auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {

267 bool HasLivePreds = false;

268 (void)HasLivePreds;

269 if (BB == Header)

270 return PN.getIncomingValueForBlock(Predecessor);

271 Value *OnlyInput = nullptr;

273 if (LiveEdges.count({ Pred, BB })) {

274 HasLivePreds = true;

275 Value *Incoming = PN.getIncomingValueForBlock(Pred);

276

277

278 if (isa(Incoming))

279 continue;

280

281 if (OnlyInput && OnlyInput != Incoming)

282 return nullptr;

284 }

285

286 assert(HasLivePreds && "No live predecessors?");

287

288 return OnlyInput ? OnlyInput : PoisonValue::get(PN.getType());

289 };

291

292

293

294

295

296

297

298

299

300

301

302 auto &DL = Header->getDataLayout();

304 for (auto *BB : RPOT) {

305 Visited.insert(BB);

306

307

308 if (!LiveBlocks.count(BB))

309 continue;

310

311

312 if (LI.getLoopFor(BB) != L) {

313 MarkAllSuccessorsLive(BB);

314 continue;

315 }

316

317

318 for (auto &PN : BB->phis()) {

319 if (!PN.getType()->isIntegerTy())

320 continue;

321 auto *Incoming = GetSoleInputOnFirstIteration(PN);

323 Value *FirstIterV =

325 FirstIterValue[&PN] = FirstIterV;

326 }

327 }

328

329 using namespace PatternMatch;

332 auto *Term = BB->getTerminator();

335 auto *ICmp = dyn_cast(Cond);

336 if (!ICmp || !ICmp->getType()->isIntegerTy()) {

337 MarkAllSuccessorsLive(BB);

338 continue;

339 }

340

341

343 if (KnownCondition == ICmp) {

344

345 MarkAllSuccessorsLive(BB);

346 continue;

347 }

348 if (isa(KnownCondition)) {

349

350

351

352

353

354

355

356

357

358

359

360 if (L->contains(IfTrue) && L->contains(IfFalse))

361 MarkLiveEdge(BB, IfTrue);

362 continue;

363 }

364 auto *ConstCondition = dyn_cast(KnownCondition);

365 if (!ConstCondition) {

366

367 MarkAllSuccessorsLive(BB);

368 continue;

369 }

370 if (ConstCondition->isAllOnesValue())

371 MarkLiveEdge(BB, IfTrue);

372 else

373 MarkLiveEdge(BB, IfFalse);

374 } else if (SwitchInst *SI = dyn_cast(Term)) {

375 auto *SwitchValue = SI->getCondition();

376 auto *SwitchValueOnFirstIter =

378 auto *ConstSwitchValue = dyn_cast(SwitchValueOnFirstIter);

379 if (!ConstSwitchValue) {

380 MarkAllSuccessorsLive(BB);

381 continue;

382 }

383 auto CaseIterator = SI->findCaseValue(ConstSwitchValue);

384 MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());

385 } else {

386 MarkAllSuccessorsLive(BB);

387 continue;

388 }

389 }

390

391

392 return !LiveEdges.count({ Latch, Header });

393}

394

395

396

397

402 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");

403

404 if (!L->getLoopLatch())

406

408 if (!BTCMax->isZero()) {

410 if (!BTC->isZero()) {

411 if (!isa(BTC) && SE.isKnownNonZero(BTC))

415 }

416 }

417 ++NumBackedgesBroken;

420}

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

440 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");

441

442

443

444

445 BasicBlock *Preheader = L->getLoopPreheader();

446 if (!Preheader || !L->hasDedicatedExits()) {

449 << "Deletion requires Loop with preheader and dedicated exits.\n");

451 }

452

453 BasicBlock *ExitBlock = L->getUniqueExitBlock();

454

455

456

457 if (ExitBlock && ExitBlock->isEHPad()) {

458 LLVM_DEBUG(dbgs() << "Cannot delete loop exiting to EH pad.\n");

460 }

461

463 LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!\n");

464

465

466

468

470 std::fill(P.incoming_values().begin(), P.incoming_values().end(),

472 }

473 ORE.emit([&]() {

475 L->getHeader())

476 << "Loop deleted because it never executes";

477 });

479 ++NumDeleted;

481 }

482

483

484

486 L->getExitingBlocks(ExitingBlocks);

487

488

489

490

491

492 if (!ExitBlock && !L->hasNoExitBlocks()) {

493 LLVM_DEBUG(dbgs() << "Deletion requires at most one exit block.\n");

495 }

496

497

498 bool Changed = false;

499 if ( isLoopDead (L, SE, ExitingBlocks, ExitBlock, Changed, Preheader, LI)) {

500 LLVM_DEBUG(dbgs() << "Loop is not invariant, cannot delete.\n");

503 }

504

505 LLVM_DEBUG(dbgs() << "Loop is invariant, delete it!\n");

506 ORE.emit([&]() {

508 L->getHeader())

509 << "Loop deleted because it is invariant";

510 });

512 ++NumDeleted;

513

515}

516

520

521 LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");

523 std::string LoopName = std::string(L.getName());

524

525

526

529

530

531

532

533 if (Result != LoopDeletionResult::Deleted)

535 AR.MSSA, ORE));

536

537 if (Result == LoopDeletionResult::Unmodified)

539

540 if (Result == LoopDeletionResult::Deleted)

542

546 return PA;

547}

AMDGPU Register Bank Select

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

BlockVerifier::State From

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

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

static LoopDeletionResult breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)

If we can prove the backedge is untaken, remove it.

static Value * getValueOnFirstIteration(Value *V, DenseMap< Value *, Value * > &FirstIterValue, const SimplifyQuery &SQ)

static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA, OptimizationRemarkEmitter &ORE)

Remove a loop if it is dead.

static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)

static bool isLoopNeverExecuted(Loop *L)

This function returns true if there is no viable path from the entry block to the header of L.

static cl::opt< bool > EnableSymbolicExecution("loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true), cl::desc("Break backedge through symbolic execution of 1st iteration " "attempting to prove that the backedge is never taken"))

static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, LoopInfo &LI)

static bool isLoopDead(Loop *L, ScalarEvolution &SE, SmallVectorImpl< BasicBlock * > &ExitingBlocks, BasicBlock *ExitBlock, bool &Changed, BasicBlock *Preheader, LoopInfo &LI)

Determines if a loop is dead.

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

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.

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

LLVM Basic Block Representation.

iterator_range< const_phi_iterator > phis() const

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

const Function * getParent() const

Return the enclosing method, or null if none.

bool isEHPad() const

Return true if this basic block is an exception handling block.

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

This is the shared class of boolean and integer constants.

iterator find(const_arg_type_t< KeyT > Val)

Implements a dense probed hash-table based set.

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

bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

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.

Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

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

bool isLoopHeader(const BlockT *BB) const

Represents a single loop in the control flow graph.

An analysis that produces MemorySSA for a function.

Encapsulates MemorySSA, including all data associated with memory accesses.

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.

This class represents an analyzed expression in the program.

bool isZero() const

Return true if the expression is a constant zero.

The main scalar evolution driver.

const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)

When successful, this returns a SCEVConstant that is greater than or equal to (i.e.

bool isKnownNonZero(const SCEV *S)

Test if the given expression is known to be non-zero.

const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)

If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...

void forgetLoop(const Loop *L)

This method should be called by the client when it has changed a loop in a way that may effect Scalar...

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.

LLVM Value Representation.

std::pair< iterator, bool > insert(const ValueT &V)

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

@ C

The default llvm calling convention, compatible with C.

bool match(Val *V, const Pattern &P)

class_match< ConstantInt > m_ConstantInt()

Match an arbitrary ConstantInt and ignore it.

brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)

class_match< Value > m_Value()

Match an arbitrary value and ignore it.

class_match< BasicBlock > m_BasicBlock()

Match an arbitrary basic block value and ignore it.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

bool all_of(R &&range, UnaryPredicate P)

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

auto successors(const MachineBasicBlock *BB)

bool hasMustProgress(const Loop *L)

Look for the loop attribute that requires progress within the loop.

bool any_of(R &&range, UnaryPredicate P)

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

void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE, LoopInfo *LI, MemorySSA *MSSA=nullptr)

This function deletes dead loops.

raw_ostream & dbgs()

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

Value * simplifyICmpInst(CmpPredicate Pred, Value *LHS, Value *RHS, const SimplifyQuery &Q)

Given operands for an ICmpInst, fold the result or return null.

void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, MemorySSA *MSSA)

Remove the backedge of the specified loop.

Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)

Given operands for a BinaryOperator, fold the result or return null.

PreservedAnalyses getLoopPassPreservedAnalyses()

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

auto predecessors(const MachineBasicBlock *BB)

bool pred_empty(const BasicBlock *BB)

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.

Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...

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