+
+void IndVarSimplify::runOnLoop(Loop *L) {
+ // First step. Check to see if there are any trivial GEP pointer recurrences.
+ // If there are, change them into integer recurrences, permitting analysis by
+ // the SCEV routines.
+ //
+ BasicBlock *Header = L->getHeader();
+ BasicBlock *Preheader = L->getLoopPreheader();
+
+ std::set<Instruction*> DeadInsts;
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ if (isa<PointerType>(PN->getType()))
+ EliminatePointerRecurrence(PN, Preheader, DeadInsts);
+
+ if (!DeadInsts.empty())
+ DeleteTriviallyDeadInstructions(DeadInsts);
+
+
+ // Next, transform all loops nesting inside of this loop.
+ for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
+ runOnLoop(*I);
+
+ // 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.
+ //
+ SCEVHandle IterationCount = SE->getIterationCount(L);
+ if (!isa<SCEVCouldNotCompute>(IterationCount))
+ RewriteLoopExitValues(L);
+
+ // Next, analyze all of the induction variables in the loop, canonicalizing
+ // auxillary induction variables.
+ std::vector<std::pair<PHINode*, SCEVHandle> > IndVars;
+
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable!
+ SCEVHandle SCEV = SE->getSCEV(PN);
+ if (SCEV->hasComputableLoopEvolution(L))
+ if (SE->shouldSubstituteIndVar(SCEV)) // HACK!
+ IndVars.push_back(std::make_pair(PN, SCEV));
+ }
+
+ // If there are no induction variables in the loop, there is nothing more to
+ // do.
+ if (IndVars.empty()) return;
+
+ // Compute the type of the largest recurrence expression.
+ //
+ const Type *LargestType = IndVars[0].first->getType();
+ bool DifferingSizes = false;
+ for (unsigned i = 1, e = IndVars.size(); i != e; ++i) {
+ const Type *Ty = IndVars[i].first->getType();
+ DifferingSizes |= Ty->getPrimitiveSize() != LargestType->getPrimitiveSize();
+ if (Ty->getPrimitiveSize() > LargestType->getPrimitiveSize())
+ LargestType = Ty;
+ }
+
+ // Create a rewriter object which we'll use to transform the code with.
+ ScalarEvolutionRewriter Rewriter(*SE, *LI);
+
+ // Now that we know the largest of of the induction variables in this loop,
+ // insert a canonical induction variable of the largest size.
+ Value *IndVar = Rewriter.GetOrInsertCanonicalInductionVariable(L,LargestType);
+ ++NumInserted;
+ Changed = true;
+
+ if (!isa<SCEVCouldNotCompute>(IterationCount))
+ LinearFunctionTestReplace(L, IterationCount, IndVar, Rewriter);
+
+#if 0
+ // If there were induction variables of other sizes, cast the primary
+ // induction variable to the right size for them, avoiding the need for the
+ // code evaluation methods to insert induction variables of different sizes.
+ // FIXME!
+ if (DifferingSizes) {
+ std::map<unsigned, Value*> InsertedSizes;
+ for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
+ }
+ }
+#endif
+
+ // Now that we have a canonical induction variable, we can rewrite any
+ // recurrences in terms of the induction variable. Start with the auxillary
+ // induction variables, and recursively rewrite any of their uses.
+ BasicBlock::iterator InsertPt = Header->begin();
+ while (isa<PHINode>(InsertPt)) ++InsertPt;
+
+ while (!IndVars.empty()) {
+ PHINode *PN = IndVars.back().first;
+ Value *NewVal = Rewriter.ExpandCodeFor(IndVars.back().second, InsertPt,
+ PN->getType());
+ // Replace the old PHI Node with the inserted computation.
+ PN->replaceAllUsesWith(NewVal);
+ DeadInsts.insert(PN);
+ IndVars.pop_back();
+ ++NumRemoved;
+ Changed = true;
+ }
+
+ DeleteTriviallyDeadInstructions(DeadInsts);
+
+ // TODO: In the future we could replace all instructions in the loop body with
+ // simpler expressions. It's not clear how useful this would be though or if
+ // the code expansion cost would be worth it! We probably shouldn't do this
+ // until we have a way to reuse expressions already in the code.
+#if 0
+ 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
+ !Rewriter.isInsertedInstruction(I)) {
+ SCEVHandle SH = SE->getSCEV(I);
+ }
+ }
+#endif