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

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;

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

123 return false;

124

127 while (!WorkList.empty()) {

130 continue;

131

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

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

181 return V;

182

183 auto Existing = FirstIterValue.find(V);

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

185 return Existing->second;

186 Value *FirstIterV = nullptr;

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

237 return false;

238

240

242

244 LiveBlocks.insert(Header);

245

248 assert(LiveBlocks.count(From) && "Must be live!");

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

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

253 LiveBlocks.insert(To);

254 LiveEdges.insert({ From, 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

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

306

307

308 if (!LiveBlocks.count(BB))

309 continue;

310

311

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

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

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 }

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 }

365 if (!ConstCondition) {

366

367 MarkAllSuccessorsLive(BB);

368 continue;

369 }

370 if (ConstCondition->isAllOnesValue())

371 MarkLiveEdge(BB, IfTrue);

372 else

373 MarkLiveEdge(BB, IfFalse);

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

376 auto *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()) {

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

471 }

472 ORE.emit([&]() {

474 L->getHeader())

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

476 });

478 ++NumDeleted;

480 }

481

482

483

485 L->getExitingBlocks(ExitingBlocks);

486

487

488

489

490

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

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

494 }

495

496

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

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

502 }

503

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

505 ORE.emit([&]() {

507 L->getHeader())

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

509 });

511 ++NumDeleted;

512

514}

515

519

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

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

523

524

525

528

529

530

531

534 AR.MSSA, ORE));

535

538

541

545 return PA;

546}

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

AMDGPU Register Bank Select

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

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

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

LoopDeletionResult

Definition LoopDeletion.cpp:45

@ Modified

Definition LoopDeletion.cpp:47

@ Deleted

Definition LoopDeletion.cpp:48

@ Unmodified

Definition LoopDeletion.cpp:46

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.

Definition LoopDeletion.cpp:399

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

Definition LoopDeletion.cpp:177

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

Remove a loop if it is dead.

Definition LoopDeletion.cpp:436

static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)

Definition LoopDeletion.cpp:51

static bool isLoopNeverExecuted(Loop *L)

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

Definition LoopDeletion.cpp:147

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)

Definition LoopDeletion.cpp:216

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

Determines if a loop is dead.

Definition LoopDeletion.cpp:63

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

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)

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.

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

Definition LoopDeletion.cpp:516

bool isLoopHeader(const BlockT *BB) const

LoopT * getLoopFor(const BlockT *BB) const

Return the inner most loop that BB lives in.

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

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

LLVM_ABI bool isKnownNonZero(const SCEV *S)

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

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

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

void fill(R &&Range, T &&Value)

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

bool all_of(R &&range, UnaryPredicate P)

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

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

auto successors(const MachineBasicBlock *BB)

LLVM_ABI bool hasMustProgress(const Loop *L)

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

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

bool any_of(R &&range, UnaryPredicate P)

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

bool containsIrreducibleCFG(RPOTraversalT &RPOTraversal, const LoopInfoT &LI)

Return true if the control flow in RPOTraversal is irreducible.

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

This function deletes dead loops.

LLVM_ABI raw_ostream & dbgs()

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

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

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

@ Unmodified

The loop was not modified.

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

Remove the backedge of the specified loop.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

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

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

ArrayRef(const T &OneElt) -> ArrayRef< T >

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