+ // Delete the old PHI for sure, and the GEP if its otherwise unused.
+ DeadInsts.insert(PN);
+
+ ++NumPointer;
+ Changed = true;
+ }
+}
+
+/// LinearFunctionTestReplace - This method rewrites the exit condition of the
+/// loop to be a canonical != comparison against the incremented loop induction
+/// variable. This pass is able to rewrite the exit tests of any loop where the
+/// SCEV analysis can determine a loop-invariant trip count of the loop, which
+/// is actually a much broader range than just linear tests.
+///
+/// This method returns a "potentially dead" instruction whose computation chain
+/// should be deleted when convenient.
+Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
+ SCEV *IterationCount,
+ SCEVExpander &RW) {
+ // Find the exit block for the loop. We can currently only handle loops with
+ // a single exit.
+ SmallVector<BasicBlock*, 8> ExitBlocks;
+ L->getExitBlocks(ExitBlocks);
+ if (ExitBlocks.size() != 1) return 0;
+ BasicBlock *ExitBlock = ExitBlocks[0];
+
+ // Make sure there is only one predecessor block in the loop.
+ BasicBlock *ExitingBlock = 0;
+ for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
+ PI != PE; ++PI)
+ if (L->contains(*PI)) {
+ if (ExitingBlock == 0)
+ ExitingBlock = *PI;
+ else
+ return 0; // Multiple exits from loop to this block.
+ }
+ assert(ExitingBlock && "Loop info is broken");
+
+ if (!isa<BranchInst>(ExitingBlock->getTerminator()))
+ return 0; // Can't rewrite non-branch yet
+ BranchInst *BI = cast<BranchInst>(ExitingBlock->getTerminator());
+ assert(BI->isConditional() && "Must be conditional to be part of loop!");
+
+ Instruction *PotentiallyDeadInst = dyn_cast<Instruction>(BI->getCondition());
+
+ // If the exiting block is not the same as the backedge block, we must compare
+ // against the preincremented value, otherwise we prefer to compare against
+ // the post-incremented value.
+ BasicBlock *Header = L->getHeader();
+ pred_iterator HPI = pred_begin(Header);
+ assert(HPI != pred_end(Header) && "Loop with zero preds???");
+ if (!L->contains(*HPI)) ++HPI;
+ assert(HPI != pred_end(Header) && L->contains(*HPI) &&
+ "No backedge in loop?");
+
+ SCEVHandle TripCount = IterationCount;
+ Value *IndVar;
+ if (*HPI == ExitingBlock) {
+ // The IterationCount expression contains the number of times that the
+ // backedge actually branches to the loop header. This is one less than the
+ // number of times the loop executes, so add one to it.
+ ConstantInt *OneC = ConstantInt::get(IterationCount->getType(), 1);
+ TripCount = SE->getAddExpr(IterationCount, SE->getConstant(OneC));
+ IndVar = L->getCanonicalInductionVariableIncrement();
+ } else {
+ // We have to use the preincremented value...
+ IndVar = L->getCanonicalInductionVariable();
+ }
+
+ DOUT << "INDVARS: LFTR: TripCount = " << *TripCount
+ << " IndVar = " << *IndVar << "\n";
+
+ // Expand the code for the iteration count into the preheader of the loop.
+ BasicBlock *Preheader = L->getLoopPreheader();
+ Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator());
+
+ // Insert a new icmp_ne or icmp_eq instruction before the branch.
+ ICmpInst::Predicate Opcode;
+ if (L->contains(BI->getSuccessor(0)))
+ Opcode = ICmpInst::ICMP_NE;
+ else
+ Opcode = ICmpInst::ICMP_EQ;
+
+ Value *Cond = new ICmpInst(Opcode, IndVar, ExitCnt, "exitcond", BI);
+ BI->setCondition(Cond);
+ ++NumLFTR;
+ Changed = true;
+ return PotentiallyDeadInst;
+}
+
+
+/// RewriteLoopExitValues - Check to see if this loop has a computable
+/// loop-invariant execution count. If so, this means that we can compute the
+/// final value of any expressions that are recurrent in the loop, and
+/// substitute the exit values from the loop into any instructions outside of
+/// the loop that use the final values of the current expressions.
+void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
+ BasicBlock *Preheader = L->getLoopPreheader();
+
+ // Scan all of the instructions in the loop, looking at those that have
+ // extra-loop users and which are recurrences.
+ SCEVExpander Rewriter(*SE, *LI);
+
+ // We insert the code into the preheader of the loop if the loop contains
+ // multiple exit blocks, or in the exit block if there is exactly one.
+ BasicBlock *BlockToInsertInto;
+ SmallVector<BasicBlock*, 8> ExitBlocks;
+ L->getUniqueExitBlocks(ExitBlocks);
+ if (ExitBlocks.size() == 1)
+ BlockToInsertInto = ExitBlocks[0];
+ else
+ BlockToInsertInto = Preheader;
+ BasicBlock::iterator InsertPt = BlockToInsertInto->begin();
+ while (isa<PHINode>(InsertPt)) ++InsertPt;
+
+ bool HasConstantItCount = isa<SCEVConstant>(SE->getIterationCount(L));
+
+ std::set<Instruction*> InstructionsToDelete;
+ std::map<Instruction*, Value*> ExitValues;
+
+ // Find all values that are computed inside the loop, but used outside of it.
+ // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
+ // the exit blocks of the loop to find them.
+ for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
+ BasicBlock *ExitBB = ExitBlocks[i];
+
+ // If there are no PHI nodes in this exit block, then no values defined
+ // inside the loop are used on this path, skip it.
+ PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
+ if (!PN) continue;
+
+ unsigned NumPreds = PN->getNumIncomingValues();
+
+ // Iterate over all of the PHI nodes.
+ BasicBlock::iterator BBI = ExitBB->begin();
+ while ((PN = dyn_cast<PHINode>(BBI++))) {