Lines Matching refs:Loop
33 // types, computes the execution count of a loop, etc.
49 // Symbolic Evaluation of Chains of Recurrences for Loop Optimization
101 "Number of loops with predictable loop counts");
103 "Number of loops without predictable loop counts");
111 "derived loop"),
507 // For instructions, compare their loop depth, and their operand
512 // Compare loop depths.
548 // Compare addrec loop depths.
549 const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
1149 // loop does not exceed this limit before incrementing.
1168 // unsigned overflow as long as the value of the recurrence within the loop does
1245 const Loop *L = AR->getLoop();
1249 // Check for a simple looking step prior to loop entry.
1300 // 3. Loop precondition.
1362 const Loop *L) {
1451 const Loop *L = AR->getLoop();
1664 const Loop *L = AR->getLoop();
1884 // here, but they're in the middle, so just visit the rest with one loop.
2243 // added values are loop invariant. If so, we can fold them into the
2248 // Scan over all recurrences, trying to fold loop invariants into them.
2251 // they are loop invariant w.r.t. the recurrence.
2254 const Loop *AddRecLoop = AddRec->getLoop();
2262 // If we found some loop invariants, fold them into the recurrence.
2277 // If all of the other operands were loop invariant, we are done.
2289 // Okay, if there weren't any loop invariants to be folded, check to see if
2290 // there are multiple AddRec's with the same loop induction variable being
2499 // added values are loop invariant. If so, we can fold them into the
2504 // Scan over all recurrences, trying to fold loop invariants into them.
2507 // they are loop invariant w.r.t. the recurrence.
2510 const Loop *AddRecLoop = AddRec->getLoop();
2518 // If we found some loop invariants, fold them into the recurrence.
2535 // If all of the other operands were loop invariant, we are done.
2547 // Okay, if there weren't any loop invariants to be folded, check to see if
2548 // there are multiple AddRec's with the same loop induction variable being
2824 /// getAddRecExpr - Get an add recurrence expression for the specified loop.
2827 const Loop *L,
2841 /// getAddRecExpr - Get an add recurrence expression for the specified loop.
2845 const Loop *L, SCEV::NoWrapFlags Flags) {
2854 "SCEVAddRecExpr operand is not loop-invariant!");
2870 // Canonicalize nested AddRecs in by nesting them in order of loop depth.
2872 const Loop *NestedLoop = NestedAR->getLoop();
2880 // AddRecs require their operands be loop-invariant with respect to their
2887 // Create a recurrence for the outer loop with the same step size.
3397 // relative to a loop that is to be found in a recurrence in LHS and
3600 // additional loop trip count information isn't going to change anything.
3619 static const SCEV *rewrite(const SCEV *Scev, const Loop *L,
3626 SCEVInitRewriter(const Loop *L, ScalarEvolution &SE)
3636 // Only allow AddRecExprs for this loop.
3646 const Loop *L;
3652 static const SCEV *rewrite(const SCEV *Scev, const Loop *L,
3659 SCEVShiftRewriter(const Loop *L, ScalarEvolution &SE)
3663 // Only allow AddRecExprs for this loop.
3678 const Loop *L;
3684 const Loop *L = LI.getLoopFor(PN->getParent());
3688 // The loop may have multiple entrances or multiple exits; we can analyze
3719 // NOTE: If BEValue is loop invariant, we know that the PHI node just
3720 // has a special value for the first iteration of the loop.
3744 // loop iteration, but is not itself an addrec in this loop.
3796 // Otherwise, this could be a loop like this:
3827 static bool IsAvailableOnEntry(const Loop *L, DominatorTree &DT, const SCEV *S,
3833 const Loop *L = nullptr; // The loop BB is in (can be nullptr)
3837 CheckAvailable(const Loop *L, BasicBlock *BB, DominatorTree &DT)
3854 // We allow add recurrences that are on the loop BB is in, or some
3855 // outer loop. This guarantees availability because the value of the
3858 // recurrence on a sibling dominating loop is also available at BB.
3933 const Loop *L = LI.getLoopFor(PN->getParent());
3976 // PHI's incoming blocks are in a different loop, in which case doing so
3983 // If it's not a loop phi, we can't handle it yet.
3992 // loop pass transforms an inner loop and moves on to process the outer loop.
4103 /// guaranteed to end in (at every loop iteration). It is, at the same time,
4425 // Here we check that BinOp is in the header of the innermost loop
4426 // containing BinOp, since we only deal with instructions in the loop
4427 // header. The actual loop we need to check later will come from an add
4431 Loop *innermostContainingLoop = LI.getLoopFor(BinOp->getParent());
4446 // loop that V is considered in relation to and prove that V is executed for
4447 // every iteration of that loop. That implies that the value that V
4448 // calculates does not wrap anywhere in the loop, so then we can apply the
4452 // recurrences from different loops, so that we know which loop to prove
4616 // X*4+1 which got turned into X*4|1. Handle this as an Add so loop
4803 unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L) {
4811 /// getSmallConstantTripCount - Returns the maximum trip count of this loop as a
4819 /// number times that the loop header executes because the loop may exit
4821 unsigned ScalarEvolution::getSmallConstantTripCount(Loop *L,
4825 "Exiting block must actually branch out of the loop!");
4841 unsigned ScalarEvolution::getSmallConstantTripMultiple(Loop *L) {
4850 /// trip count of this loop as a normal unsigned value, if possible. This
4860 /// that control exits the loop via ExitingBlock.
4862 ScalarEvolution::getSmallConstantTripMultiple(Loop *L,
4866 "Exiting block must actually branch out of the loop!");
4894 // getExitCount - Get the expression for the number of loop iterations for which
4895 // this loop is guaranteed not to exit via ExitingBlock. Otherwise return
4897 const SCEV *ScalarEvolution::getExitCount(Loop *L, BasicBlock *ExitingBlock) {
4901 /// getBackedgeTakenCount - If the specified loop has a predictable
4903 /// object. The backedge-taken count is the number of times the loop header
4904 /// will be branched to from within the loop. This is one less than the
4905 /// trip count of the loop, since it doesn't count the first iteration,
4906 /// when the header is branched to from outside the loop.
4908 /// Note that it is not valid to call this method on a loop without a
4909 /// loop-invariant backedge-taken count (see
4912 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
4919 const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
4923 loop
4926 PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
4929 // Push all Loop-header PHIs onto the Worklist stack.
4936 ScalarEvolution::getBackedgeTakenInfo(const Loop *L) {
4937 // Initially insert an invalid entry for this loop. If the insertion
4942 std::pair<DenseMap<const Loop *, BackedgeTakenInfo>::iterator, bool> Pair =
4955 "Computed backedge-taken count isn't loop invariant for loop!");
4964 // Now that we know more about the trip count for this loop, forget any
4965 // existing SCEV values for PHI nodes in this loop since they are only
4986 // by createNodeForPHI. In the former case, additional loop trip
5005 // loop), which would invalidate the iterator computed
5011 /// changed a loop in a way that may effect ScalarEvolution's ability to
5012 /// compute a trip count, or if the loop is deleted.
5013 void ScalarEvolution::forgetLoop(const Loop *L) {
5015 DenseMap<const Loop*, BackedgeTakenInfo>::iterator BTCPos =
5022 // Drop information about expressions based on loop-header PHIs.
5046 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
5052 /// disconnect it from a def-use chain linking it to a loop.
5057 // Drop information about expressions based on loop-header PHIs.
5080 /// getExact - Get the exact loop backedge taken count considering all loop
5083 /// because one of the loop's exit limit's may have been skipped. HowFarToZero
5084 /// assumes that the limit of each loop test is never skipped. This is a valid
5085 /// assumption as long as the loop exits via that test. For precise results, it
5086 /// is the caller's responsibility to specify the relevant loop exit using
5090 // If any exits were not computable, the loop is not computable.
5108 assert(BECount && "Invalid not taken count for loop exit");
5112 /// getExact - Get the exact not taken count for this loop exit.
5125 /// getMax - Get the max backedge taken count for the loop.
5185 /// of the specified loop will execute.
5187 ScalarEvolution::computeBackedgeTakenCount(const Loop *L) {
5197 // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts
5207 // we won't be able to compute an exact value for the loop.
5212 // 2. Derive the loop's MaxBECount from each exit's max number of
5213 // non-exiting iterations. Partition the loop exits into two kinds:
5216 // If the exit dominates the loop latch, it is a LoopMustExit otherwise it
5244 ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock) {
5248 // lead to the loop header.
5262 // the loop is exited. However, we don't know if the branch is executed each
5263 // time through the loop. If not, then the execution count of the branch will
5264 // not be equal to the trip count of the loop.
5267 // the loop header. If so, we know it will always execute the same number of
5268 // times as the loop. We also handle the case where the exit block *is* the
5269 // loop header. This is common for un-rotated loops.
5272 // header, stopping if there is an edge that doesn't exit the loop. If the
5274 // trip count of the loop.
5291 // outside the loop, assume the worst.
5308 assert(BI->isConditional() && "If unconditional, it can't be in loop!");
5323 /// backedge of the specified loop will execute if its exit condition
5327 /// branch. In this case, we can assume that the loop exits only if the
5331 ScalarEvolution::computeExitLimitFromCond(const Loop *L,
5336 // Check if the controlling expression for this loop is an And or Or.
5348 // Both conditions must be true for the loop to continue executing.
5362 // Both conditions must be true at the same time for the loop to exit.
5364 assert(L->contains(FBB) && "Loop block has no successor in loop!");
5383 // Both conditions must be false for the loop to continue executing.
5397 // Both conditions must be false at the same time for the loop to exit.
5399 assert(L->contains(TBB) && "Loop block has no successor in loop!");
5433 ScalarEvolution::computeExitLimitFromICmp(const Loop *L,
5463 // Try to evaluate any dependencies out of the loop.
5468 // loop the predicate will return true for these inputs.
5470 // If there is a loop-invariant, force it into the RHS.
5525 ScalarEvolution::computeExitLimitFromSingleExitSwitch(const Loop *L,
5536 "Default case must not exit the loop!");
5565 const Loop *L,
5597 // Loop-invariant loads may be a byproduct of loop optimization. Skip them.
5602 // Check to see if X is a loop variant variable value now.
5606 // We can only recognize very limited forms of loop index expressions, in
5639 Value *LHS, Value *RHSV, const Loop *L, ICmpInst::Predicate Pred) {
5674 // loop:
5675 // %iv = phi i32 [ %iv.shifted, %loop ], [ %val, %preheader ]
5796 /// Determine whether this instruction can constant evolve within this loop
5798 static bool canConstantEvolve(Instruction *I, const Loop *L) {
5799 // An instruction outside of the loop can't be derived from a loop PHI.
5814 /// recursing through each instruction operand until reaching a loop header phi.
5816 getConstantEvolvingPHIOperands(Instruction *UseInst, const Loop *L,
5850 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
5851 /// in the loop that V is derived from. We allow arbitrary operations along the
5855 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) {
5862 // Record non-constant instructions contained by the loop.
5869 /// in the loop has the value PHIVal. If we can't fold this expression for some
5871 static Constant *EvaluateExpression(Value *V, const Loop *L,
5882 // An instruction inside the loop depends on a value outside the loop that we
5883 // weren't given a mapping for, or a value such as a call inside the loop.
5886 // An unmapped PHI can be due to a branch or another loop inside this loop,
5887 // or due to this not being the initial iteration through a loop where we
5942 /// in the header of its containing loop, we know the loop executes a
5948 const Loop *L) {
5960 assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
5978 // Execute the loop symbolically to determine the exit value.
6023 // iterating, the loop can't continue to change.
6031 const SCEV *ScalarEvolution::computeExitCountExhaustively(const Loop *L,
6037 // If the loop is canonicalized, the PHI will have exactly two entries.
6043 assert(PN->getParent() == Header && "Can't evaluate PHI not in loop header!");
6059 // Okay, we find a PHI node that defines the trip count of this loop. Execute
6060 // the loop symbolically to determine when the condition gets a value of
6103 /// at the specified scope in the program. The L value specifies a loop
6105 /// specified loop is immediately inside of the loop.
6108 /// in a loop by querying what the value will hold in the parent loop.
6110 /// In the case that a relevant loop exit value cannot be computed, the
6112 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) {
6113 SmallVector<std::pair<const Loop *, const SCEV *>, 2> &Values =
6115 // Check to see if we've folded this expression at this loop before.
6231 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
6235 // exit value from the loop without using SCEVs.
6238 const Loop *LI = this->LI[I->getParent()];
6239 if (LI && LI->getParentLoop() == L) // Looking for loop exit value.
6243 // to see if the loop that contains it has a known backedge-taken
6249 // Okay, we know how many times the containing loop executes. If
6261 // result. This is particularly useful for computing loop exit values.
6316 // expression has no loop-variant portions.
6320 // Okay, at least one of these operands is loop variant but might be
6341 // If we got here, all operands are loop invariant.
6349 return Div; // must be loop invariant
6353 // If this is a loop recurrence for a loop that does not contain L, then we
6354 // are dealing with the final value computed by the loop.
6358 // expression has no loop-variant portions.
6364 // Okay, at least one of these operands is loop variant but might be
6384 // If the scope is outside the addrec's loop, evaluate it by using the
6385 // loop exit value of the addrec.
6388 // loop iterates. Compute this now.
6402 return Cast; // must be loop invariant
6409 return Cast; // must be loop invariant
6416 return Cast; // must be loop invariant
6425 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) {
6518 // The loop is provably infinite.
6556 ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L, bool ControlsExit) {
6561 return getCouldNotCompute(); // Otherwise it will loop infinitely.
6610 // Get the initial value for the loop.
6703 // If the condition controls loop exit (the loop exits only if the expression
6706 // distance, but we don't care because if the condition is "missed" the loop
6725 ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
6735 return getCouldNotCompute(); // Otherwise it will loop infinitely.
6756 // A loop's header is defined to be a block that dominates the loop.
6757 // If the header has a unique predecessor outside the loop, it must be
6758 // a block that has exactly one successor that can reach the loop.
6759 if (Loop *L = LI.getLoopFor(BB))
6767 /// looking for a condition guarding a loop, it can be useful to be a little
6824 // If we're comparing an addrec with a value which is loop-invariant in the
6825 // addrec's loop, put the addrec on the left. Also make a dominance check,
6826 // as both operands could be addrecs loop-invariant in each other's loop.
6828 const Loop *L = AR->getLoop();
7099 // every iteration of the loop.
7101 // every iteration of the loop.
7107 const Loop *L = LAR->getLoop();
7115 const Loop *L = RAR->getLoop();
7158 // loop invariant value. We don't really depend on the predicate actually
7209 ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L,
7213 // If there is a loop-invariant, force it into the RHS, otherwise bail out.
7231 // true as the loop iterates, and the backedge is control dependent on
7235 // is never evaluated again, since the loop exits without taking the
7241 // For both the above possibilities, we can replace the loop varying
7242 // predicate with its value on the first iteration of the loop (which is
7243 // loop invariant).
7411 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is
7415 ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L,
7418 // Interpret a null as meaning no loop, where there is obviously no guard
7447 // We know that Latch branches back to the loop header exactly
7471 // If the loop is not reachable from the entry block, we risk running into an
7472 // infinite loop as we walk up into the dom tree. These loops do not matter
7480 assert(DTN && "should reach the loop header before reaching the root!");
7493 // If we have an edge `E` within the loop body that dominates the only
7500 // loop body that dominate the latch. The dominator tree better agree
7513 /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected
7515 /// expressions in loop trip counts, and to eliminate casts.
7517 ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L,
7520 // Interpret a null as meaning no loop, where there is obviously no guard
7526 // Starting at the loop predecessor, climb up the predecessor chain, as long
7607 // Now that we found a conditional branch that dominates the loop or controls
7608 // the loop latch. Check to see if it is the comparison we are looking for.
7843 // both the inequalities to be about add recurrences on the same loop. This
7846 const Loop *L = AddRecFoundLHS->getLoop();
7970 // If both sides are affine addrecs for the same loop, with equal
8201 const Loop *L, bool IsSigned,
8281 const Loop *L, bool IsSigned,
8361 /// getNumIterationsInRange - Return the number of iterations of this loop that
8368 if (Range.isFullSet()) // Infinite loop.
8405 // If A is negative then the lower of the range is the last possible loop
8922 /// For example: when analyzing the memory access A[i][j][k] in this loop nest
9089 // that a loop had multiple computable exits.
9098 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) {
9103 const Loop *L) {
9105 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
9108 OS << "Loop ";
9124 "Loop ";
9162 const Loop *L = LI.getLoopFor(I.getParent());
9189 OS << "Determining loop execution counts for: ";
9197 ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
9216 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
9227 // If L is the addrec's loop, it's computable.
9231 // Add recurrences are never invariant in the function-body (null loop).
9235 // This recurrence is variant w.r.t. L if L contains AR's loop.
9239 // This recurrence is invariant w.r.t. L if AR's loop contains L.
9249 // Otherwise it's loop-invariant.
9278 // All non-instruction values are loop invariant. All instructions are loop
9279 // invariant if they are not contained in the specified loop.
9281 // (null loop) because they are defined within the "loop".
9291 bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) {
9295 bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) {
9416 for (DenseMap<const Loop*, BackedgeTakenInfo>::iterator I =
9428 typedef DenseMap<const Loop *, std::string> VerifyMap;
9441 getLoopBackedgeTakenCounts(Loop *L, VerifyMap &Map, ScalarEvolution &SE) {
9442 for (Loop::reverse_iterator I = L->rbegin(), E = L->rend(); I != E; ++I) {
9486 assert(OldI->first == NewI->first && "Loop order changed!");
9498 dbgs() << "SCEVValidator: SCEV for loop '"
