Lines Matching refs:Loop
14 // If the trip count of a loop is computable, this pass also makes the following
16 // 1. The exit condition for the loop is canonicalized to compare the
19 // 2. Any use outside of the loop of an expression derived from the indvar
20 // is changed to compute the derived value outside of the loop, eliminating
22 // purpose of the loop is to compute the exit value of some derived
23 // expression, this transformation will make the loop dead.
61 STATISTIC(NumLFTR , "Number of loop exit tests replaced");
107 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
129 void handleFloatingPointIV(Loop *L, PHINode *PH);
130 void rewriteNonIntegerIVs(Loop *L);
132 void simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
134 bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
135 void rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
137 Value *linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
140 void sinkUnusedInvariants(Loop *L);
142 Value *expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S, Loop *L,
215 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
216 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
271 /// If the loop has floating induction variable then insert corresponding
280 void IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
324 // of the loop. If not, the new IV can overflow and no one will notice.
325 // The branch block must be in the loop and one of the successors must be out
326 // of the loop.
382 // Check for infinite loop, either:
409 // Check for infinite loop, either:
461 // in the loop uses its value. In order to canonicalize the induction
476 void IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
492 // If the loop previously had floating-point IV, ScalarEvolution
515 Loop *L, Instruction *InsertPt,
528 // rewriteLoopExitValues - Optimize IV users outside the loop.
529 // As a side effect, reduces the amount of IV processing within the loop.
532 /// Check to see if this loop has a computable loop-invariant execution count.
534 /// that are recurrent in the loop, and substitute the exit values from the loop
535 /// into any instructions outside of the loop that use the final values of the
541 /// constant operands at the beginning of the loop.
542 void IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
550 // Find all values that are computed inside the loop, but used outside of it.
552 // the exit blocks of the loop to find them.
557 // inside the loop are used on this path, skip it.
565 // While the computed exit value is no longer varying in *this* loop, the
566 // exit block may be an exit block for an outer containing loop as well,
567 // the exit value may be varying in the outer loop, and thus it may still
570 // part of the enclosing loop, or this is the outer most loop of the nest.
572 // loop body as the phi node itself. Thus if it is in turn used outside of
573 // an enclosing loop it will only be via a separate LCSSA node.
591 // may not be a def-use connection between the loop and every instruction
592 // which got a SCEVAddRecExpr for that loop.
598 // in the loop, skip it.
607 // Check that InVal is defined in the loop.
612 // Okay, this instruction has a user outside of the current loop
613 // and varies predictably *inside* the loop. Evaluate the value it
614 // contains when the loop exits, if possible.
620 // Computing the value outside of the loop brings no benefit if :
621 // - it is definitely used inside the loop in a way which can not be
623 // - no use outside of the loop can take advantage of hoisting the
624 // computation out of the loop
715 /// Check whether it is possible to delete the loop after rewriting exit
719 Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
722 // If there is no preheader, the loop will not be deleted.
726 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
743 // could be rewritten to use a loop invariant value in transformation
744 // phase later. Skip it in the loop invariant check below.
859 Loop *L;
916 /// Perform a quick domtree based check for loop invariance assuming that V is
917 /// used within the loop. LoopInfo::isLoopInvariant() seems gratuitous for this
919 static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) {
931 // Hoist the insertion point into loop preheaders as far as possible.
932 for (const Loop *L = LI->getLoopFor(Use->getParent());
974 // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1102 /// operands is an AddRec for this loop, return it.
1152 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1188 // loop preheader as far as possible.
1234 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1237 // For LCSSA phis, sink the truncate outside the loop.
1238 // After SimplifyCFG most loop exit targets have a single predecessor.
1239 // Otherwise fall back to a truncate within the loop.
1288 // new loop phi. If we preserved IVUsers analysis, we would also want to
1301 // If use is a loop condition, try to promote the condition instead of
1329 // extended outside the loop without overflow. This suggests that the wide use
1386 // Can the IV be extended outside the loop without overflow?
1391 // An AddRec must have loop-invariant operands. Since this AddRec is
1392 // materialized by a loop header phi, the expression cannot have any post-loop
1393 // operands, so they must dominate the loop header.
1396 && "Loop header phi recurrence inputs do not dominate the loop");
1401 // of the phi-SCC dominates the loop entry.
1443 // Live IV Reduction - Minimize IVs live across the loop.
1481 void IndVarSimplify::simplifyAndExtend(Loop *L,
1525 // linearFunctionTestReplace and its kin. Rewrite the loop exit condition.
1528 /// Return true if this loop's backedge taken count expression can be safely and
1532 /// TODO: This fails for pointer-type loop counters with greater than one byte
1534 /// we could skip this check in the case that the LFTR loop counter (chosen by
1536 /// the loop test to an inequality test by checking the target data's alignment
1539 /// However, we don't yet have a strong motivation for converting loop tests
1541 static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE,
1561 /// Return the loop header phi IFF IncV adds a loop invariant value to the phi.
1562 static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) {
1597 /// Return the compare guarding the loop latch, or NULL for unrecognized tests.
1598 static ICmpInst *getLoopTest(Loop *L) {
1599 assert(L->getExitingBlock() && "expected loop exit");
1602 // Don't bother with LFTR if the loop is not properly simplified.
1614 static bool needsLFTR(Loop *L, DominatorTree *DT) {
1625 // Look for a loop invariant RHS
1641 // Do LFTR if PHI node is defined in the loop, but is *not* a counter.
1694 /// loop exit test.
1720 static PHINode *FindLoopCounter(Loop *L, const SCEV *BECount,
1727 // Loop over all of the PHI nodes, looking for a simple counter.
1731 assert(LatchBlock && "needsLFTR should guarantee a loop latch");
1767 // the loop test. In this case we assume that performing LFTR could not
1779 // Don't force a live loop counter if another IV can be used.
1802 /// the new loop test.
1803 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L,
1806 assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter");
1817 // signed value. IVCount on the other hand represents the loop trip count,
1827 "Computed iteration count is not loop invariant!");
1832 assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter");
1874 "Computed iteration count is not loop invariant!");
1884 /// This method rewrites the exit condition of the loop to be a canonical !=
1885 /// comparison against the incremented loop induction variable. This pass is
1886 /// able to rewrite the exit tests of any loop where the SCEV analysis can
1887 /// determine a loop-invariant trip count of the loop, which is actually a much
1890 linearFunctionTestReplace(Loop *L,
1910 // backedge branches to the loop header. This is one less than the
1911 // number of times the loop executes, so use the incremented indvar.
1927 DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
1985 // sinkUnusedInvariants. A late subpass to cleanup loop preheaders.
1988 /// If there's a single exit block, sink any loop-invariant values that
1989 /// were defined in the preheader but not used inside the loop into the
1990 /// exit block to reduce register pressure in the loop.
1991 void IndVarSimplify::sinkUnusedInvariants(Loop *L) {
2007 // effects need to complete before instructions inside the loop. Also don't
2008 // move instructions which might read memory, since the loop may modify
2030 // Determine if there is a use in or before the loop (direct or
2077 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
2086 // Loop::getCanonicalInductionVariable only supports loops with preheaders,
2120 // other expressions involving loop IVs have been evaluated. This helps SCEV
2125 // Check to see if this loop has a computable loop-invariant execution count.
2127 // that are recurrent in the loop, and substitute the exit values from the
2128 // loop into any instructions outside of the loop that use the final values of
2138 // If we have a trip count expression, rewrite the loop's exit condition
2146 // loop passes because SCEVExpander makes assumptions about all loops,
2147 // while LoopPassManager only forces the current loop to be simplified.
2158 // can be deleted in the loop below, causing the AssertingVH in the cache to
2171 // Loop-invariant instructions in the preheader that aren't used in the
2172 // loop may be sunk below the loop to reduce register pressure.
