+/// getExact - Get the exact loop backedge taken count considering all loop
+/// exits. A computable result can only be return for loops with a single exit.
+/// Returning the minimum taken count among all exits is incorrect because one
+/// of the loop's exit limit's may have been skipped. HowFarToZero assumes that
+/// the limit of each loop test is never skipped. This is a valid assumption as
+/// long as the loop exits via that test. For precise results, it is the
+/// caller's responsibility to specify the relevant loop exit using
+/// getExact(ExitingBlock, SE).
+const SCEV *
+ScalarEvolution::BackedgeTakenInfo::getExact(ScalarEvolution *SE) const {
+ // If any exits were not computable, the loop is not computable.
+ if (!ExitNotTaken.isCompleteList()) return SE->getCouldNotCompute();
+
+ // We need exactly one computable exit.
+ if (!ExitNotTaken.ExitingBlock) return SE->getCouldNotCompute();
+ assert(ExitNotTaken.ExactNotTaken && "uninitialized not-taken info");
+
+ const SCEV *BECount = 0;
+ for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
+ ENT != 0; ENT = ENT->getNextExit()) {
+
+ assert(ENT->ExactNotTaken != SE->getCouldNotCompute() && "bad exit SCEV");
+
+ if (!BECount)
+ BECount = ENT->ExactNotTaken;
+ else if (BECount != ENT->ExactNotTaken)
+ return SE->getCouldNotCompute();
+ }
+ assert(BECount && "Invalid not taken count for loop exit");
+ return BECount;
+}
+
+/// getExact - Get the exact not taken count for this loop exit.
+const SCEV *
+ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock,
+ ScalarEvolution *SE) const {
+ for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
+ ENT != 0; ENT = ENT->getNextExit()) {
+
+ if (ENT->ExitingBlock == ExitingBlock)
+ return ENT->ExactNotTaken;
+ }
+ return SE->getCouldNotCompute();
+}
+
+/// getMax - Get the max backedge taken count for the loop.
+const SCEV *
+ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const {
+ return Max ? Max : SE->getCouldNotCompute();
+}
+
+/// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
+/// computable exit into a persistent ExitNotTakenInfo array.
+ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
+ SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts,
+ bool Complete, const SCEV *MaxCount) : Max(MaxCount) {
+
+ if (!Complete)
+ ExitNotTaken.setIncomplete();
+
+ unsigned NumExits = ExitCounts.size();
+ if (NumExits == 0) return;
+
+ ExitNotTaken.ExitingBlock = ExitCounts[0].first;
+ ExitNotTaken.ExactNotTaken = ExitCounts[0].second;
+ if (NumExits == 1) return;
+
+ // Handle the rare case of multiple computable exits.
+ ExitNotTakenInfo *ENT = new ExitNotTakenInfo[NumExits-1];
+
+ ExitNotTakenInfo *PrevENT = &ExitNotTaken;
+ for (unsigned i = 1; i < NumExits; ++i, PrevENT = ENT, ++ENT) {
+ PrevENT->setNextExit(ENT);
+ ENT->ExitingBlock = ExitCounts[i].first;
+ ENT->ExactNotTaken = ExitCounts[i].second;
+ }
+}
+
+/// clear - Invalidate this result and free the ExitNotTakenInfo array.
+void ScalarEvolution::BackedgeTakenInfo::clear() {
+ ExitNotTaken.ExitingBlock = 0;
+ ExitNotTaken.ExactNotTaken = 0;
+ delete[] ExitNotTaken.getNextExit();
+}
+