+/// 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.
+ ScalarEvolutionRewriter 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;
+ if (L->getExitBlocks().size() == 1)
+ BlockToInsertInto = L->getExitBlocks()[0];
+ else
+ BlockToInsertInto = Preheader;
+ BasicBlock::iterator InsertPt = BlockToInsertInto->begin();
+ while (isa<PHINode>(InsertPt)) ++InsertPt;
+
+ std::set<Instruction*> InstructionsToDelete;
+
+ for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i)
+ if (LI->getLoopFor(L->getBlocks()[i]) == L) { // Not in a subloop...
+ BasicBlock *BB = L->getBlocks()[i];
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
+ if (I->getType()->isInteger()) { // Is an integer instruction
+ SCEVHandle SH = SE->getSCEV(I);
+ if (SH->hasComputableLoopEvolution(L)) { // Varies predictably
+ // Find out if this predictably varying value is actually used
+ // outside of the loop. "extra" as opposed to "intra".
+ std::vector<User*> ExtraLoopUsers;
+ for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
+ UI != E; ++UI)
+ if (!L->contains(cast<Instruction>(*UI)->getParent()))
+ ExtraLoopUsers.push_back(*UI);
+ if (!ExtraLoopUsers.empty()) {
+ // Okay, this instruction has a user outside of the current loop
+ // and varies predictably in this loop. Evaluate the value it
+ // contains when the loop exits, and insert code for it.
+ SCEVHandle ExitValue = SE->getSCEVAtScope(I,L->getParentLoop());
+ if (!isa<SCEVCouldNotCompute>(ExitValue)) {
+ Changed = true;
+ ++NumReplaced;
+ Value *NewVal = Rewriter.ExpandCodeFor(ExitValue, InsertPt,
+ I->getType());
+
+ // Rewrite any users of the computed value outside of the loop
+ // with the newly computed value.
+ for (unsigned i = 0, e = ExtraLoopUsers.size(); i != e; ++i)
+ ExtraLoopUsers[i]->replaceUsesOfWith(I, NewVal);
+
+ // If this instruction is dead now, schedule it to be removed.
+ if (I->use_empty())
+ InstructionsToDelete.insert(I);
+ }
+ }
+ }
+ }
+ }