X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FIndVarSimplify.cpp;h=5e82ad0f7b5b199d3f754ad98185ca6a2c6e8fea;hp=5b7e4e1fd9ecdebfec5337ebaf33dedf4f8535fa;hb=b8f74793b9d161bc666fe27fc92fe112b6ec169b;hpb=4bd09d70cceb3851f7eb1c2f98338b3071d405f3 diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index 5b7e4e1fd9e..5e82ad0f7b5 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -11,7 +11,7 @@ // computations derived from them) into simpler forms suitable for subsequent // analysis and transformation. // -// This transformation make the following changes to each loop with an +// This transformation makes the following changes to each loop with an // identifiable induction variable: // 1. All loops are transformed to have a SINGLE canonical induction variable // which starts at zero and steps by one. @@ -37,301 +37,69 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "indvars" #include "llvm/Transforms/Scalar.h" #include "llvm/BasicBlock.h" #include "llvm/Constants.h" #include "llvm/Instructions.h" #include "llvm/Type.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CommandLine.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" using namespace llvm; -namespace { - /// SCEVExpander - This class uses information about analyze scalars to - /// rewrite expressions in canonical form. - /// - /// Clients should create an instance of this class when rewriting is needed, - /// and destroying it when finished to allow the release of the associated - /// memory. - struct SCEVExpander : public SCEVVisitor { - ScalarEvolution &SE; - LoopInfo &LI; - std::map InsertedExpressions; - std::set InsertedInstructions; - - Instruction *InsertPt; - - friend struct SCEVVisitor; - public: - SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {} - - /// isInsertedInstruction - Return true if the specified instruction was - /// inserted by the code rewriter. If so, the client should not modify the - /// instruction. - bool isInsertedInstruction(Instruction *I) const { - return InsertedInstructions.count(I); - } - - /// getOrInsertCanonicalInductionVariable - This method returns the - /// canonical induction variable of the specified type for the specified - /// loop (inserting one if there is none). A canonical induction variable - /// starts at zero and steps by one on each iteration. - Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ - assert((Ty->isInteger() || Ty->isFloatingPoint()) && - "Can only insert integer or floating point induction variables!"); - SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty), - SCEVUnknown::getIntegerSCEV(1, Ty), L); - return expand(H); - } - - /// addInsertedValue - Remember the specified instruction as being the - /// canonical form for the specified SCEV. - void addInsertedValue(Instruction *I, SCEV *S) { - InsertedExpressions[S] = (Value*)I; - InsertedInstructions.insert(I); - } - - /// expandCodeFor - Insert code to directly compute the specified SCEV - /// expression into the program. The inserted code is inserted into the - /// specified block. - /// - /// If a particular value sign is required, a type may be specified for the - /// result. - Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) { - // Expand the code for this SCEV. - this->InsertPt = IP; - return expandInTy(SH, Ty); - } - - protected: - Value *expand(SCEV *S) { - // Check to see if we already expanded this. - std::map::iterator I = InsertedExpressions.find(S); - if (I != InsertedExpressions.end()) - return I->second; - - Value *V = visit(S); - InsertedExpressions[S] = V; - return V; - } - - Value *expandInTy(SCEV *S, const Type *Ty) { - Value *V = expand(S); - if (Ty && V->getType() != Ty) { - // FIXME: keep track of the cast instruction. - if (Constant *C = dyn_cast(V)) - return ConstantExpr::getCast(C, Ty); - else if (Instruction *I = dyn_cast(V)) { - // Check to see if there is already a cast. If there is, use it. - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - if ((*UI)->getType() == Ty) - if (CastInst *CI = dyn_cast(cast(*UI))) { - BasicBlock::iterator It = I; ++It; - if (isa(I)) - It = cast(I)->getNormalDest()->begin(); - while (isa(It)) ++It; - if (It != BasicBlock::iterator(CI)) { - // Splice the cast immediately after the operand in question. - BasicBlock::InstListType &InstList = - It->getParent()->getInstList(); - InstList.splice(It, CI->getParent()->getInstList(), CI); - } - return CI; - } - } - BasicBlock::iterator IP = I; ++IP; - if (InvokeInst *II = dyn_cast(I)) - IP = II->getNormalDest()->begin(); - while (isa(IP)) ++IP; - return new CastInst(V, Ty, V->getName(), IP); - } else { - // FIXME: check to see if there is already a cast! - return new CastInst(V, Ty, V->getName(), InsertPt); - } - } - return V; - } - - Value *visitConstant(SCEVConstant *S) { - return S->getValue(); - } - - Value *visitTruncateExpr(SCEVTruncateExpr *S) { - Value *V = expand(S->getOperand()); - return new CastInst(V, S->getType(), "tmp.", InsertPt); - } - - Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) { - Value *V = expandInTy(S->getOperand(),S->getType()->getUnsignedVersion()); - return new CastInst(V, S->getType(), "tmp.", InsertPt); - } - - Value *visitAddExpr(SCEVAddExpr *S) { - const Type *Ty = S->getType(); - Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty); - - // Emit a bunch of add instructions - for (int i = S->getNumOperands()-2; i >= 0; --i) - V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty), - "tmp.", InsertPt); - return V; - } - - Value *visitMulExpr(SCEVMulExpr *S); - - Value *visitUDivExpr(SCEVUDivExpr *S) { - const Type *Ty = S->getType(); - Value *LHS = expandInTy(S->getLHS(), Ty); - Value *RHS = expandInTy(S->getRHS(), Ty); - return BinaryOperator::createDiv(LHS, RHS, "tmp.", InsertPt); - } - - Value *visitAddRecExpr(SCEVAddRecExpr *S); - - Value *visitUnknown(SCEVUnknown *S) { - return S->getValue(); - } - }; -} - -Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) { - const Type *Ty = S->getType(); - int FirstOp = 0; // Set if we should emit a subtract. - if (SCEVConstant *SC = dyn_cast(S->getOperand(0))) - if (SC->getValue()->isAllOnesValue()) - FirstOp = 1; - - int i = S->getNumOperands()-2; - Value *V = expandInTy(S->getOperand(i+1), Ty); - - // Emit a bunch of multiply instructions - for (; i >= FirstOp; --i) - V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty), - "tmp.", InsertPt); - // -1 * ... ---> 0 - ... - if (FirstOp == 1) - V = BinaryOperator::createNeg(V, "tmp.", InsertPt); - return V; -} - -Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { - const Type *Ty = S->getType(); - const Loop *L = S->getLoop(); - // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} - assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!"); - - // {X,+,F} --> X + {0,+,F} - if (!isa(S->getStart()) || - !cast(S->getStart())->getValue()->isNullValue()) { - Value *Start = expandInTy(S->getStart(), Ty); - std::vector NewOps(S->op_begin(), S->op_end()); - NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty); - Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty); - - // FIXME: look for an existing add to use. - return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt); - } - - // {0,+,1} --> Insert a canonical induction variable into the loop! - if (S->getNumOperands() == 2 && - S->getOperand(1) == SCEVUnknown::getIntegerSCEV(1, Ty)) { - // Create and insert the PHI node for the induction variable in the - // specified loop. - BasicBlock *Header = L->getHeader(); - PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); - PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); - - 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?"); - - // Insert a unit add instruction right before the terminator corresponding - // to the back-edge. - Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0) - : ConstantInt::get(Ty, 1); - Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next", - (*HPI)->getTerminator()); - - pred_iterator PI = pred_begin(Header); - if (*PI == L->getLoopPreheader()) - ++PI; - PN->addIncoming(Add, *PI); - return PN; - } - - // Get the canonical induction variable I for this loop. - Value *I = getOrInsertCanonicalInductionVariable(L, Ty); - - if (S->getNumOperands() == 2) { // {0,+,F} --> i*F - Value *F = expandInTy(S->getOperand(1), Ty); - return BinaryOperator::createMul(I, F, "tmp.", InsertPt); - } - - // If this is a chain of recurrences, turn it into a closed form, using the - // folders, then expandCodeFor the closed form. This allows the folders to - // simplify the expression without having to build a bunch of special code - // into this folder. - SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. - - SCEVHandle V = S->evaluateAtIteration(IH); - //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; - - return expandInTy(V, Ty); -} - +STATISTIC(NumRemoved , "Number of aux indvars removed"); +STATISTIC(NumPointer , "Number of pointer indvars promoted"); +STATISTIC(NumInserted, "Number of canonical indvars added"); +STATISTIC(NumReplaced, "Number of exit values replaced"); +STATISTIC(NumLFTR , "Number of loop exit tests replaced"); namespace { - Statistic<> NumRemoved ("indvars", "Number of aux indvars removed"); - Statistic<> NumPointer ("indvars", "Number of pointer indvars promoted"); - Statistic<> NumInserted("indvars", "Number of canonical indvars added"); - Statistic<> NumReplaced("indvars", "Number of exit values replaced"); - Statistic<> NumLFTR ("indvars", "Number of loop exit tests replaced"); - - class IndVarSimplify : public FunctionPass { + class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { LoopInfo *LI; ScalarEvolution *SE; bool Changed; public: - virtual bool runOnFunction(Function &) { - LI = &getAnalysis(); - SE = &getAnalysis(); - Changed = false; - - // Induction Variables live in the header nodes of loops - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - runOnLoop(*I); - return Changed; - } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequiredID(LoopSimplifyID); - AU.addRequired(); - AU.addRequired(); - AU.addPreservedID(LoopSimplifyID); - AU.setPreservesCFG(); - } + static char ID; // Pass identification, replacement for typeid + IndVarSimplify() : LoopPass((intptr_t)&ID) {} + + bool runOnLoop(Loop *L, LPPassManager &LPM); + bool doInitialization(Loop *L, LPPassManager &LPM); + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredID(LCSSAID); + AU.addRequiredID(LoopSimplifyID); + AU.addRequired(); + AU.addRequired(); + AU.addPreservedID(LoopSimplifyID); + AU.addPreservedID(LCSSAID); + AU.setPreservesCFG(); + } + private: - void runOnLoop(Loop *L); + void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader, std::set &DeadInsts); - void LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, - SCEVExpander &RW); + Instruction *LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, + SCEVExpander &RW); void RewriteLoopExitValues(Loop *L); void DeleteTriviallyDeadInstructions(std::set &Insts); }; - RegisterOpt X("indvars", "Canonicalize Induction Variables"); + + char IndVarSimplify::ID = 0; + RegisterPass X("indvars", "Canonicalize Induction Variables"); } -FunctionPass *llvm::createIndVarSimplifyPass() { +LoopPass *llvm::createIndVarSimplifyPass() { return new IndVarSimplify(); } @@ -347,7 +115,8 @@ DeleteTriviallyDeadInstructions(std::set &Insts) { for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (Instruction *U = dyn_cast(I->getOperand(i))) Insts.insert(U); - SE->deleteInstructionFromRecords(I); + SE->deleteValueFromRecords(I); + DOUT << "INDVARS: Deleting: " << *I; I->eraseFromParent(); Changed = true; } @@ -365,10 +134,11 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader); unsigned BackedgeIdx = PreheaderIdx^1; if (GetElementPtrInst *GEPI = - dyn_cast(PN->getIncomingValue(BackedgeIdx))) + dyn_cast(PN->getIncomingValue(BackedgeIdx))) if (GEPI->getOperand(0) == PN) { - assert(GEPI->getNumOperands() == 2 && "GEP types must mismatch!"); - + assert(GEPI->getNumOperands() == 2 && "GEP types must match!"); + DOUT << "INDVARS: Eliminating pointer recurrence: " << *GEPI; + // Okay, we found a pointer recurrence. Transform this pointer // recurrence into an integer recurrence. Compute the value that gets // added to the pointer at every iteration. @@ -398,18 +168,23 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, assert(NumOps > 1 && "CE folding didn't work!"); if (CE->getOperand(NumOps-1)->isNullValue()) { // Check to make sure the last index really is an array index. - gep_type_iterator GTI = gep_type_begin(GEPI); - for (unsigned i = 1, e = GEPI->getNumOperands()-1; + gep_type_iterator GTI = gep_type_begin(CE); + for (unsigned i = 1, e = CE->getNumOperands()-1; i != e; ++i, ++GTI) /*empty*/; if (isa(*GTI)) { // Pull the last index out of the constant expr GEP. - std::vector CEIdxs(CE->op_begin()+1, CE->op_end()-1); + SmallVector CEIdxs(CE->op_begin()+1, CE->op_end()-1); Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0), - CEIdxs); - GetElementPtrInst *NGEPI = - new GetElementPtrInst(NCE, Constant::getNullValue(Type::IntTy), - NewAdd, GEPI->getName(), GEPI); + &CEIdxs[0], + CEIdxs.size()); + Value *Idx[2]; + Idx[0] = Constant::getNullValue(Type::Int32Ty); + Idx[1] = NewAdd; + GetElementPtrInst *NGEPI = new GetElementPtrInst( + NCE, Idx, Idx + 2, + GEPI->getName(), GEPI); + SE->deleteValueFromRecords(GEPI); GEPI->replaceAllUsesWith(NGEPI); GEPI->eraseFromParent(); GEPI = NGEPI; @@ -424,11 +199,10 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, if (!PN->use_empty()) { BasicBlock::iterator InsertPos = PN; ++InsertPos; while (isa(InsertPos)) ++InsertPos; - std::string Name = PN->getName(); PN->setName(""); Value *PreInc = new GetElementPtrInst(PN->getIncomingValue(PreheaderIdx), - std::vector(1, NewPhi), Name, - InsertPos); + NewPhi, "", InsertPos); + PreInc->takeName(PN); PN->replaceAllUsesWith(PreInc); } @@ -445,13 +219,17 @@ void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, /// 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. -void IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, - SCEVExpander &RW) { +/// +/// 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. - std::vector ExitBlocks; + SmallVector ExitBlocks; L->getExitBlocks(ExitBlocks); - if (ExitBlocks.size() != 1) return; + if (ExitBlocks.size() != 1) return 0; BasicBlock *ExitBlock = ExitBlocks[0]; // Make sure there is only one predecessor block in the loop. @@ -462,19 +240,17 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, if (ExitingBlock == 0) ExitingBlock = *PI; else - return; // Multiple exits from loop to this block. + return 0; // Multiple exits from loop to this block. } assert(ExitingBlock && "Loop info is broken"); if (!isa(ExitingBlock->getTerminator())) - return; // Can't rewrite non-branch yet + return 0; // Can't rewrite non-branch yet BranchInst *BI = cast(ExitingBlock->getTerminator()); assert(BI->isConditional() && "Must be conditional to be part of loop!"); - std::set InstructionsToDelete; - if (Instruction *Cond = dyn_cast(BI->getCondition())) - InstructionsToDelete.insert(Cond); - + Instruction *PotentiallyDeadInst = dyn_cast(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. @@ -491,32 +267,33 @@ void IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, // 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. - Constant *OneC = ConstantInt::get(IterationCount->getType(), 1); - TripCount = SCEVAddExpr::get(IterationCount, SCEVUnknown::get(OneC)); + ConstantInt *OneC = ConstantInt::get(IterationCount->getType(), 1); + TripCount = SCEVAddExpr::get(IterationCount, SCEVConstant::get(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(), - IndVar->getType()); + Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator()); - // Insert a new setne or seteq instruction before the branch. - Instruction::BinaryOps Opcode; + // Insert a new icmp_ne or icmp_eq instruction before the branch. + ICmpInst::Predicate Opcode; if (L->contains(BI->getSuccessor(0))) - Opcode = Instruction::SetNE; + Opcode = ICmpInst::ICMP_NE; else - Opcode = Instruction::SetEQ; + Opcode = ICmpInst::ICMP_EQ; - Value *Cond = new SetCondInst(Opcode, IndVar, ExitCnt, "exitcond", BI); + Value *Cond = new ICmpInst(Opcode, IndVar, ExitCnt, "exitcond", BI); BI->setCondition(Cond); ++NumLFTR; Changed = true; - - DeleteTriviallyDeadInstructions(InstructionsToDelete); + return PotentiallyDeadInst; } @@ -535,8 +312,8 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L) { // 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; - std::vector ExitBlocks; - L->getExitBlocks(ExitBlocks); + SmallVector ExitBlocks; + L->getUniqueExitBlocks(ExitBlocks); if (ExitBlocks.size() == 1) BlockToInsertInto = ExitBlocks[0]; else @@ -547,68 +324,105 @@ void IndVarSimplify::RewriteLoopExitValues(Loop *L) { bool HasConstantItCount = isa(SE->getIterationCount(L)); std::set 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;) { - if (I->getType()->isInteger()) { // Is an integer instruction - SCEVHandle SH = SE->getSCEV(I); - if (SH->hasComputableLoopEvolution(L) || // Varies predictably - HasConstantItCount) { - // Find out if this predictably varying value is actually used - // outside of the loop. "extra" as opposed to "intra". - std::vector ExtraLoopUsers; - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) - if (!L->contains(cast(*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(ExitValue)) { - Changed = true; - ++NumReplaced; - // Remember the next instruction. The rewriter can move code - // around in some cases. - BasicBlock::iterator NextI = I; ++NextI; - - 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); - I = NextI; - continue; // Skip the ++I - } - } - } + std::map 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(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(BBI++))) { + + // Iterate over all of the values in all the PHI nodes. + for (unsigned i = 0; i != NumPreds; ++i) { + // If the value being merged in is not integer or is not defined + // in the loop, skip it. + Value *InVal = PN->getIncomingValue(i); + if (!isa(InVal) || + // SCEV only supports integer expressions for now. + !isa(InVal->getType())) + continue; + + // If this pred is for a subloop, not L itself, skip it. + if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) + continue; // The Block is in a subloop, skip it. + + // Check that InVal is defined in the loop. + Instruction *Inst = cast(InVal); + if (!L->contains(Inst->getParent())) + continue; + + // We require that this value either have a computable evolution or that + // the loop have a constant iteration count. In the case where the loop + // has a constant iteration count, we can sometimes force evaluation of + // the exit value through brute force. + SCEVHandle SH = SE->getSCEV(Inst); + if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount) + continue; // Cannot get exit evolution for the loop value. + + // Okay, this instruction has a user outside of the current loop + // and varies predictably *inside* the loop. Evaluate the value it + // contains when the loop exits, if possible. + SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); + if (isa(ExitValue) || + !ExitValue->isLoopInvariant(L)) + continue; + + Changed = true; + ++NumReplaced; + + // See if we already computed the exit value for the instruction, if so, + // just reuse it. + Value *&ExitVal = ExitValues[Inst]; + if (!ExitVal) + ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt); + + DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal + << " LoopVal = " << *Inst << "\n"; + + PN->setIncomingValue(i, ExitVal); + + // If this instruction is dead now, schedule it to be removed. + if (Inst->use_empty()) + InstructionsToDelete.insert(Inst); + + // See if this is a single-entry LCSSA PHI node. If so, we can (and + // have to) remove + // the PHI entirely. This is safe, because the NewVal won't be variant + // in the loop, so we don't need an LCSSA phi node anymore. + if (NumPreds == 1) { + SE->deleteValueFromRecords(PN); + PN->replaceAllUsesWith(ExitVal); + PN->eraseFromParent(); + break; } - - // Next instruction. Continue instruction skips this. - ++I; } } - + } + DeleteTriviallyDeadInstructions(InstructionsToDelete); } +bool IndVarSimplify::doInitialization(Loop *L, LPPassManager &LPM) { -void IndVarSimplify::runOnLoop(Loop *L) { + Changed = false; // 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(); + SE = &LPM.getAnalysis(); std::set DeadInsts; for (BasicBlock::iterator I = Header->begin(); isa(I); ++I) { @@ -620,10 +434,21 @@ void IndVarSimplify::runOnLoop(Loop *L) { if (!DeadInsts.empty()) DeleteTriviallyDeadInstructions(DeadInsts); + return Changed; +} + +bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { + - // Next, transform all loops nesting inside of this loop. - for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I) - runOnLoop(*I); + LI = &getAnalysis(); + SE = &getAnalysis(); + + Changed = false; + BasicBlock *Header = L->getHeader(); + std::set 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 @@ -641,16 +466,16 @@ void IndVarSimplify::runOnLoop(Loop *L) { for (BasicBlock::iterator I = Header->begin(); isa(I); ++I) { PHINode *PN = cast(I); - if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable! + if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable! SCEVHandle SCEV = SE->getSCEV(PN); if (SCEV->hasComputableLoopEvolution(L)) - // FIXME: Without a strength reduction pass, it is an extremely bad idea - // to indvar substitute anything more complex than a linear induction - // variable. Doing so will put expensive multiply instructions inside - // of the loop. For now just disable indvar subst on anything more - // complex than a linear addrec. + // 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(SCEV)) - if (AR->getNumOperands() == 2 && isa(AR->getOperand(1))) + if (AR->isAffine()) IndVars.push_back(std::make_pair(PN, SCEV)); } } @@ -664,9 +489,14 @@ void IndVarSimplify::runOnLoop(Loop *L) { SCEVExpander Rewriter(*SE, *LI); Rewriter.getOrInsertCanonicalInductionVariable(L, IterationCount->getType()); - LinearFunctionTestReplace(L, IterationCount, Rewriter); + if (Instruction *I = LinearFunctionTestReplace(L, IterationCount, + Rewriter)) { + std::set InstructionsToDelete; + InstructionsToDelete.insert(I); + DeleteTriviallyDeadInstructions(InstructionsToDelete); + } } - return; + return Changed; } // Compute the type of the largest recurrence expression. @@ -675,8 +505,9 @@ void IndVarSimplify::runOnLoop(Loop *L) { 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()) + DifferingSizes |= + Ty->getPrimitiveSizeInBits() != LargestType->getPrimitiveSizeInBits(); + if (Ty->getPrimitiveSizeInBits() > LargestType->getPrimitiveSizeInBits()) LargestType = Ty; } @@ -685,13 +516,20 @@ void IndVarSimplify::runOnLoop(Loop *L) { // Now that we know the largest of of the induction variables in this loop, // insert a canonical induction variable of the largest size. - LargestType = LargestType->getUnsignedVersion(); Value *IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); ++NumInserted; Changed = true; - - if (!isa(IterationCount)) - LinearFunctionTestReplace(L, IterationCount, Rewriter); + DOUT << "INDVARS: New CanIV: " << *IndVar; + + if (!isa(IterationCount)) { + if (IterationCount->getType()->getPrimitiveSizeInBits() < + LargestType->getPrimitiveSizeInBits()) + IterationCount = SCEVZeroExtendExpr::get(IterationCount, LargestType); + else if (IterationCount->getType() != LargestType) + IterationCount = SCEVTruncateExpr::get(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 @@ -703,30 +541,32 @@ void IndVarSimplify::runOnLoop(Loop *L) { // 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) { - bool InsertedSizes[17] = { false }; - InsertedSizes[LargestType->getPrimitiveSize()] = true; - for (unsigned i = 0, e = IndVars.size(); i != e; ++i) - if (!InsertedSizes[IndVars[i].first->getType()->getPrimitiveSize()]) { + SmallVector 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[PN->getType()->getPrimitiveSize()] = true; - Instruction *New = new CastInst(IndVar, - PN->getType()->getUnsignedVersion(), - "indvar", InsertPt); + 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"; } + } } - // 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. + // Rewrite all induction variables in terms of the canonical induction + // variable. std::map InsertedSizes; while (!IndVars.empty()) { PHINode *PN = IndVars.back().first; - Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt, - PN->getType()); - std::string Name = PN->getName(); - PN->setName(""); - NewVal->setName(Name); + 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); @@ -749,11 +589,8 @@ void IndVarSimplify::runOnLoop(Loop *L) { SCEVHandle SH = SE->getSCEV(I); Value *V = Rewriter.expandCodeFor(SH, I, I->getType()); if (V != I) { - if (isa(V)) { - std::string Name = I->getName(); - I->setName(""); - V->setName(Name); - } + if (isa(V)) + V->takeName(I); I->replaceAllUsesWith(V); DeadInsts.insert(I); ++NumRemoved; @@ -764,4 +601,7 @@ void IndVarSimplify::runOnLoop(Loop *L) { #endif DeleteTriviallyDeadInstructions(DeadInsts); + + assert(L->isLCSSAForm()); + return Changed; }