Lines Matching +full:non +full:- +full:live
1 //===- LoopDeletion.cpp - Dead Loop Deletion Pass ---------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 // for eliminating loops with non-infinite computable trip counts that have no
14 //===----------------------------------------------------------------------===//
34 #define DEBUG_TYPE "loop-delete"
41 "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true),
70 // sufficient to guarantee that no loop-variant values are used outside
75 for (PHINode &P : ExitBlock->phis()) {
91 if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator(),
103 // Make sure that no instructions in the block have potential side-effects.
106 for (const auto &I : L->blocks())
112 // The loop or any of its sub-loops looping infinitely is legal. The loop can
115 // b. all (sub-)loops are mustprogress or have a known trip-count.
116 if (L->getHeader()->getParent()->mustProgress())
139 WorkList.append(Current->begin(), Current->end());
150 auto *Preheader = L->getLoopPreheader();
155 if (Preheader->isEntryBlock())
158 // branch, with the loop's preheader as not-taken.
162 if (!match(Pred->getTerminator(),
165 if (!Cond->getZExtValue())
172 // All the predecessors have the loop preheader as not-taken target.
179 // Quick hack: do not flood cache with non-instruction values.
185 return Existing->second;
189 getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ);
191 getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ);
192 FirstIterV = simplifyBinOp(BO->getOpcode(), LHS, RHS, SQ);
195 getValueOnFirstIteration(Cmp->getOperand(0), FirstIterValue, SQ);
197 getValueOnFirstIteration(Cmp->getOperand(1), FirstIterValue, SQ);
198 FirstIterV = simplifyICmpInst(Cmp->getPredicate(), LHS, RHS, SQ);
201 getValueOnFirstIteration(Select->getCondition(), FirstIterValue, SQ);
203 auto *Selected = C->isAllOnesValue() ? Select->getTrueValue()
204 : Select->getFalseValue();
222 BasicBlock *Predecessor = L->getLoopPredecessor();
223 BasicBlock *Latch = L->getLoopLatch();
239 BasicBlock *Header = L->getHeader();
248 assert(LiveBlocks.count(From) && "Must be live!");
262 // Check if there is only one value coming from all live predecessor blocks.
264 // (non-latch) predecessors.
265 auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
277 // the non-poison input.
286 assert(HasLivePreds && "No live predecessors?");
287 // If all incoming live value were poison, return poison.
299 // iteration, mark this successor live.
301 // live.
302 auto &DL = Header->getDataLayout();
317 // If Phi has only one input from all live input blocks, use it.
318 for (auto &PN : BB->phis()) {
319 if (!PN.getType()->isIntegerTy())
322 if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
332 auto *Term = BB->getTerminator();
336 if (!ICmp || !ICmp->getType()->isIntegerTy()) {
351 // without marking any successors as live. However, we are not certain
355 // If there is a non-loop successor, always assume this branch leaves the
359 // other transforms, we should not mark any successors live here.
360 if (L->contains(IfTrue) && L->contains(IfFalse))
366 // Non-constant condition, cannot analyze any further.
370 if (ConstCondition->isAllOnesValue())
375 auto *SwitchValue = SI->getCondition();
383 auto CaseIterator = SI->findCaseValue(ConstSwitchValue);
384 MarkLiveEdge(BB, CaseIterator->getCaseSuccessor());
391 // We can break the latch if it wasn't live.
402 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
404 if (!L->getLoopLatch())
408 if (!BTCMax->isZero()) {
410 if (!BTC->isZero()) {
440 assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
445 BasicBlock *Preheader = L->getLoopPreheader();
446 if (!Preheader || !L->hasDedicatedExits()) {
453 BasicBlock *ExitBlock = L->getUniqueExitBlock();
457 if (ExitBlock && ExitBlock->isEHPad()) {
469 for (PHINode &P : ExitBlock->phis()) {
474 return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
475 L->getHeader())
486 L->getExitingBlocks(ExitingBlocks);
492 if (!ExitBlock && !L->hasNoExitBlocks()) {
507 return OptimizationRemark(DEBUG_TYPE, "Invariant", L->getStartLoc(),
508 L->getHeader())
527 OptimizationRemarkEmitter ORE(L.getHeader()->getParent());