+ ExitBr->getParent() != L->getHeader()) {
+ // The simple checks failed, try climbing the unique predecessor chain
+ // up to the header.
+ bool Ok = false;
+ for (BasicBlock *BB = ExitBr->getParent(); BB; ) {
+ BasicBlock *Pred = BB->getUniquePredecessor();
+ if (!Pred)
+ return getCouldNotCompute();
+ TerminatorInst *PredTerm = Pred->getTerminator();
+ for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) {
+ BasicBlock *PredSucc = PredTerm->getSuccessor(i);
+ if (PredSucc == BB)
+ continue;
+ // If the predecessor has a successor that isn't BB and isn't
+ // outside the loop, assume the worst.
+ if (L->contains(PredSucc))
+ return getCouldNotCompute();
+ }
+ if (Pred == L->getHeader()) {
+ Ok = true;
+ break;
+ }
+ BB = Pred;
+ }
+ if (!Ok)
+ return getCouldNotCompute();
+ }
+
+ // Procede to the next level to examine the exit condition expression.
+ return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(),
+ ExitBr->getSuccessor(0),
+ ExitBr->getSuccessor(1));
+}
+
+/// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the
+/// backedge of the specified loop will execute if its exit condition
+/// were a conditional branch of ExitCond, TBB, and FBB.
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L,
+ Value *ExitCond,
+ BasicBlock *TBB,
+ BasicBlock *FBB) {
+ // Check if the controlling expression for this loop is an And or Or.
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) {
+ if (BO->getOpcode() == Instruction::And) {
+ // Recurse on the operands of the and.
+ BackedgeTakenInfo BTI0 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
+ BackedgeTakenInfo BTI1 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
+ const SCEV* BECount = getCouldNotCompute();
+ const SCEV* MaxBECount = getCouldNotCompute();
+ if (L->contains(TBB)) {
+ // Both conditions must be true for the loop to continue executing.
+ // Choose the less conservative count.
+ if (BTI0.Exact == getCouldNotCompute() ||
+ BTI1.Exact == getCouldNotCompute())
+ BECount = getCouldNotCompute();
+ else
+ BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max == getCouldNotCompute())
+ MaxBECount = BTI1.Max;
+ else if (BTI1.Max == getCouldNotCompute())
+ MaxBECount = BTI0.Max;
+ else
+ MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ } else {
+ // Both conditions must be true for the loop to exit.
+ assert(L->contains(FBB) && "Loop block has no successor in loop!");
+ if (BTI0.Exact != getCouldNotCompute() &&
+ BTI1.Exact != getCouldNotCompute())
+ BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max != getCouldNotCompute() &&
+ BTI1.Max != getCouldNotCompute())
+ MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ }
+
+ return BackedgeTakenInfo(BECount, MaxBECount);
+ }
+ if (BO->getOpcode() == Instruction::Or) {
+ // Recurse on the operands of the or.
+ BackedgeTakenInfo BTI0 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB);
+ BackedgeTakenInfo BTI1 =
+ ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB);
+ const SCEV* BECount = getCouldNotCompute();
+ const SCEV* MaxBECount = getCouldNotCompute();
+ if (L->contains(FBB)) {
+ // Both conditions must be false for the loop to continue executing.
+ // Choose the less conservative count.
+ if (BTI0.Exact == getCouldNotCompute() ||
+ BTI1.Exact == getCouldNotCompute())
+ BECount = getCouldNotCompute();
+ else
+ BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max == getCouldNotCompute())
+ MaxBECount = BTI1.Max;
+ else if (BTI1.Max == getCouldNotCompute())
+ MaxBECount = BTI0.Max;
+ else
+ MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ } else {
+ // Both conditions must be false for the loop to exit.
+ assert(L->contains(TBB) && "Loop block has no successor in loop!");
+ if (BTI0.Exact != getCouldNotCompute() &&
+ BTI1.Exact != getCouldNotCompute())
+ BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact);
+ if (BTI0.Max != getCouldNotCompute() &&
+ BTI1.Max != getCouldNotCompute())
+ MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max);
+ }
+
+ return BackedgeTakenInfo(BECount, MaxBECount);
+ }
+ }
+
+ // With an icmp, it may be feasible to compute an exact backedge-taken count.
+ // Procede to the next level to examine the icmp.
+ if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
+ return ComputeBackedgeTakenCountFromExitCondICmp(L, ExitCondICmp, TBB, FBB);
+
+ // If it's not an integer or pointer comparison then compute it the hard way.
+ return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB));
+}
+
+/// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the
+/// backedge of the specified loop will execute if its exit condition
+/// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB.
+ScalarEvolution::BackedgeTakenInfo
+ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L,
+ ICmpInst *ExitCond,
+ BasicBlock *TBB,
+ BasicBlock *FBB) {