X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FIndVarSimplify.cpp;h=ff2b9939c70cdd952207c5e893a63ccad91d81d2;hb=6c2e2e52870230838380778415d9ad543e66dae3;hp=a115e050d17f2aa77251f21f117ef36cadaf00c4;hpb=31bcdb822fe9133b1973de51519d34e5813a6184;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp index a115e050d17..ff2b9939c70 100644 --- a/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -5,32 +5,28 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar/IndVarSimplify.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Analysis/InductionVariable.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/iPHINode.h" #include "llvm/iOther.h" #include "llvm/Type.h" -#include "llvm/BasicBlock.h" #include "llvm/Constants.h" -#include "llvm/Pass.h" #include "llvm/Support/CFG.h" #include "Support/STLExtras.h" +#include "Support/Statistic.h" -#if 0 -#define DEBUG -#include "llvm/Analysis/Writer.h" -#endif +namespace { + Statistic<> NumRemoved ("indvars", "Number of aux indvars removed"); + Statistic<> NumInserted("indvars", "Number of cannonical indvars added"); +} // InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a // name... // -static Instruction *InsertCast(Instruction *Val, const Type *Ty, - BasicBlock::iterator It) { - Instruction *Cast = new CastInst(Val, Ty); - if (Val->hasName()) Cast->setName(Val->getName()+"-casted"); - Val->getParent()->getInstList().insert(It, Cast); - return Cast; +static Instruction *InsertCast(Value *Val, const Type *Ty, + Instruction *InsertBefore) { + return new CastInst(Val, Ty, Val->getName()+"-casted", InsertBefore); } static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { @@ -40,16 +36,18 @@ static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { std::bind1st(std::ptr_fun(TransformLoop), Loops)); // Get the header node for this loop. All of the phi nodes that could be // induction variables must live in this basic block. - BasicBlock *Header = (BasicBlock*)Loop->getBlocks().front(); + // + BasicBlock *Header = Loop->getBlocks().front(); // Loop over all of the PHI nodes in the basic block, calculating the // induction variables that they represent... stuffing the induction variable // info into a vector... // std::vector IndVars; // Induction variables for block - for (BasicBlock::iterator I = Header->begin(); - PHINode *PN = dyn_cast(*I); ++I) + BasicBlock::iterator AfterPHIIt = Header->begin(); + for (; PHINode *PN = dyn_cast(&*AfterPHIIt); ++AfterPHIIt) IndVars.push_back(InductionVariable(PN, Loops)); + // AfterPHIIt now points to first nonphi instruction... // If there are no phi nodes in this basic block, there can't be indvars... if (IndVars.empty()) return Changed; @@ -61,7 +59,8 @@ static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { bool FoundIndVars = false; InductionVariable *Cannonical = 0; for (unsigned i = 0; i < IndVars.size(); ++i) { - if (IndVars[i].InductionType == InductionVariable::Cannonical) + if (IndVars[i].InductionType == InductionVariable::Cannonical && + !isa(IndVars[i].Phi->getType())) Cannonical = &IndVars[i]; if (IndVars[i].InductionType != InductionVariable::Unknown) FoundIndVars = true; @@ -73,19 +72,14 @@ static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { // Okay, we want to convert other induction variables to use a cannonical // indvar. If we don't have one, add one now... if (!Cannonical) { - // Create the PHI node for the new induction variable - PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar"); - - // Insert the phi node at the end of the other phi nodes... - Header->getInstList().insert(Header->begin()+IndVars.size(), PN); + // Create the PHI node for the new induction variable, and insert the phi + // node at the end of the other phi nodes... + PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar", AfterPHIIt); // Create the increment instruction to add one to the counter... Instruction *Add = BinaryOperator::create(Instruction::Add, PN, ConstantUInt::get(Type::UIntTy,1), - "add1-indvar"); - - // Insert the add instruction after all of the PHI nodes... - Header->getInstList().insert(Header->begin()+(IndVars.size()+1), Add); + "add1-indvar", AfterPHIIt); // Figure out which block is incoming and which is the backedge for the loop BasicBlock *Incoming, *BackEdgeBlock; @@ -109,12 +103,11 @@ static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { assert(IndVars.back().InductionType == InductionVariable::Cannonical && "Just inserted cannonical indvar that is not cannonical!"); Cannonical = &IndVars.back(); + ++NumInserted; Changed = true; } -#ifdef DEBUG - cerr << "Induction variables:\n"; -#endif + DEBUG(std::cerr << "Induction variables:\n"); // Get the current loop iteration count, which is always the value of the // cannonical phi node... @@ -124,49 +117,47 @@ static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { // Loop through and replace all of the auxillary induction variables with // references to the primary induction variable... // - unsigned InsertPos = IndVars.size(); for (unsigned i = 0; i < IndVars.size(); ++i) { InductionVariable *IV = &IndVars[i]; -#ifdef DEBUG - cerr << IndVars[i]; -#endif + + DEBUG(IV->print(std::cerr)); + + // Don't do math with pointers... + const Type *IVTy = IV->Phi->getType(); + if (isa(IVTy)) IVTy = Type::ULongTy; + // Don't modify the cannonical indvar or unrecognized indvars... if (IV != Cannonical && IV->InductionType != InductionVariable::Unknown) { Instruction *Val = IterCount; if (!isa(IV->Step) || // If the step != 1 !cast(IV->Step)->equalsInt(1)) { - std::string Name; // Create a scale by the step value... - if (IV->Phi->hasName()) Name = IV->Phi->getName()+"-scale"; // If the types are not compatible, insert a cast now... - if (Val->getType() != IV->Step->getType()) - Val = InsertCast(Val, IV->Step->getType(), - Header->begin()+InsertPos++); + if (Val->getType() != IVTy) + Val = InsertCast(Val, IVTy, AfterPHIIt); + if (IV->Step->getType() != IVTy) + IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt); - Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step, Name); - // Insert the phi node at the end of the other phi nodes... - Header->getInstList().insert(Header->begin()+InsertPos++, Val); + Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step, + IV->Phi->getName()+"-scale", AfterPHIIt); } - if (!isa(IV->Start) || // If the start != 0 - !cast(IV->Start)->isNullValue()) { - std::string Name; // Create a offset by the start value... - if (IV->Phi->hasName()) Name = IV->Phi->getName()+"-offset"; - + // If the start != 0 + if (IV->Start != Constant::getNullValue(IV->Start->getType())) { // If the types are not compatible, insert a cast now... - if (Val->getType() != IV->Start->getType()) - Val = InsertCast(Val, IV->Start->getType(), - Header->begin()+InsertPos++); - - Val = BinaryOperator::create(Instruction::Add, Val, IV->Start, Name); - // Insert the phi node at the end of the other phi nodes... - Header->getInstList().insert(Header->begin()+InsertPos++, Val); + if (Val->getType() != IVTy) + Val = InsertCast(Val, IVTy, AfterPHIIt); + if (IV->Start->getType() != IVTy) + IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt); + + // Insert the instruction after the phi nodes... + Val = BinaryOperator::create(Instruction::Add, Val, IV->Start, + IV->Phi->getName()+"-offset", AfterPHIIt); } // If the PHI node has a different type than val is, insert a cast now... if (Val->getType() != IV->Phi->getType()) - Val = InsertCast(Val, IV->Phi->getType(), - Header->begin()+InsertPos++); + Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt); // Replace all uses of the old PHI node with the new computed value... IV->Phi->replaceAllUsesWith(Val); @@ -177,37 +168,35 @@ static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { Val->setName(OldName); // Delete the old, now unused, phi node... - Header->getInstList().remove(IV->Phi); - delete IV->Phi; - InsertPos--; // Deleted an instr, decrement insert position + Header->getInstList().erase(IV->Phi); Changed = true; + ++NumRemoved; } } return Changed; } -static bool doit(Function *M, LoopInfo &Loops) { - // Induction Variables live in the header nodes of the loops of the function - return reduce_apply_bool(Loops.getTopLevelLoops().begin(), - Loops.getTopLevelLoops().end(), - std::bind1st(std::ptr_fun(TransformLoop), &Loops)); -} - - namespace { struct InductionVariableSimplify : public FunctionPass { - virtual bool runOnFunction(Function *F) { - return doit(F, getAnalysis()); + virtual bool runOnFunction(Function &) { + LoopInfo &LI = getAnalysis(); + + // Induction Variables live in the header nodes of loops + return reduce_apply_bool(LI.getTopLevelLoops().begin(), + LI.getTopLevelLoops().end(), + std::bind1st(std::ptr_fun(TransformLoop), &LI)); } virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(LoopInfo::ID); + AU.addRequired(); + AU.setPreservesCFG(); } }; + RegisterOpt X("indvars", + "Cannonicalize Induction Variables"); } Pass *createIndVarSimplifyPass() { return new InductionVariableSimplify(); } -