+bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
+
+
+ LI = &getAnalysis<LoopInfo>();
+ SE = &getAnalysis<ScalarEvolution>();
+
+ Changed = false;
+ BasicBlock *Header = L->getHeader();
+ std::set<Instruction*> DeadInsts;
+
+ // Verify the input to the pass in already in LCSSA form.
+ assert(L->isLCSSAForm());
+
+ // 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(); isa<PHINode>(I); ++I) {
+ PHINode *PN = cast<PHINode>(I);
+ if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable!
+ SCEVHandle SCEV = SE->getSCEV(PN);
+ if (SCEV->hasComputableLoopEvolution(L))
+ // FIXME: It is an extremely bad idea to indvar substitute anything more
+ // complex than affine induction variables. Doing so will put expensive
+ // polynomial evaluations inside of the loop, and the str reduction pass
+ // currently can only reduce affine polynomials. For now just disable
+ // indvar subst on anything more complex than an affine addrec.
+ if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV))
+ if (AR->isAffine())
+ 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()) {
+ // Actually, if we know how many times the loop iterates, lets insert a
+ // canonical induction variable to help subsequent passes.
+ if (!isa<SCEVCouldNotCompute>(IterationCount)) {
+ SCEVExpander Rewriter(*SE, *LI);
+ Rewriter.getOrInsertCanonicalInductionVariable(L,
+ IterationCount->getType());
+ if (Instruction *I = LinearFunctionTestReplace(L, IterationCount,
+ Rewriter)) {
+ std::set<Instruction*> InstructionsToDelete;
+ InstructionsToDelete.insert(I);
+ DeleteTriviallyDeadInstructions(InstructionsToDelete);
+ }
+ }
+ return Changed;
+ }
+
+ // 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->getPrimitiveSizeInBits() != LargestType->getPrimitiveSizeInBits();
+ if (Ty->getPrimitiveSizeInBits() > LargestType->getPrimitiveSizeInBits())
+ LargestType = Ty;
+ }
+
+ // Create a rewriter object which we'll use to transform the code with.
+ SCEVExpander 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;
+ DOUT << "INDVARS: New CanIV: " << *IndVar;
+
+ if (!isa<SCEVCouldNotCompute>(IterationCount)) {
+ if (IterationCount->getType()->getPrimitiveSizeInBits() <
+ LargestType->getPrimitiveSizeInBits())
+ IterationCount = SE->getZeroExtendExpr(IterationCount, LargestType);
+ else if (IterationCount->getType() != LargestType)
+ IterationCount = SE->getTruncateExpr(IterationCount, LargestType);
+ if (Instruction *DI = LinearFunctionTestReplace(L, IterationCount,Rewriter))
+ DeadInsts.insert(DI);
+ }
+
+ // 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;
+
+ // 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.
+ if (DifferingSizes) {
+ SmallVector<unsigned,4> InsertedSizes;
+ InsertedSizes.push_back(LargestType->getPrimitiveSizeInBits());
+ for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
+ unsigned ithSize = IndVars[i].first->getType()->getPrimitiveSizeInBits();
+ if (std::find(InsertedSizes.begin(), InsertedSizes.end(), ithSize)
+ == InsertedSizes.end()) {
+ PHINode *PN = IndVars[i].first;
+ InsertedSizes.push_back(ithSize);
+ Instruction *New = new TruncInst(IndVar, PN->getType(), "indvar",
+ InsertPt);
+ Rewriter.addInsertedValue(New, SE->getSCEV(New));
+ DOUT << "INDVARS: Made trunc IV for " << *PN
+ << " NewVal = " << *New << "\n";
+ }
+ }
+ }
+
+ // Rewrite all induction variables in terms of the canonical induction
+ // variable.
+ std::map<unsigned, Value*> InsertedSizes;
+ while (!IndVars.empty()) {
+ PHINode *PN = IndVars.back().first;
+ Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt);
+ DOUT << "INDVARS: Rewrote IV '" << *IndVars.back().second << "' " << *PN
+ << " into = " << *NewVal << "\n";
+ NewVal->takeName(PN);
+
+ // Replace the old PHI Node with the inserted computation.
+ PN->replaceAllUsesWith(NewVal);
+ DeadInsts.insert(PN);
+ IndVars.pop_back();
+ ++NumRemoved;
+ Changed = true;
+ }
+
+#if 0
+ // Now replace all derived expressions in the loop body with simpler
+ // expressions.
+ 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
+ !I->use_empty() &&
+ !Rewriter.isInsertedInstruction(I)) {
+ SCEVHandle SH = SE->getSCEV(I);
+ Value *V = Rewriter.expandCodeFor(SH, I, I->getType());
+ if (V != I) {
+ if (isa<Instruction>(V))
+ V->takeName(I);
+ I->replaceAllUsesWith(V);
+ DeadInsts.insert(I);
+ ++NumRemoved;
+ Changed = true;
+ }
+ }
+ }
+#endif
+
+ DeleteTriviallyDeadInstructions(DeadInsts);
+
+ assert(L->isLCSSAForm());
+ return Changed;
+}