IndVarSimplify.cpp revision 793c6b80d3e322c3fefb3c7314b054c7880d1691
16148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 26148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 36148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// InductionVariableSimplify - Transform induction variables in a program 46148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// to all use a single cannonical induction variable per loop. 56148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 66148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===----------------------------------------------------------------------===// 76148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 86148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner#include "llvm/Transforms/Scalar/IndVarSimplify.h" 96148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner#include "llvm/Analysis/InductionVariable.h" 106148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner#include "llvm/Analysis/LoopInfo.h" 116148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner#include "llvm/iPHINode.h" 12394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#include "llvm/iOther.h" 13394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#include "llvm/Type.h" 14394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#include "llvm/ConstantVals.h" 156148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner#include "Support/STLExtras.h" 166148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 17394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#if 0 18394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#define DEBUG 19394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#include "llvm/Analysis/Writer.h" 20394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#endif 21394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 22394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner// InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a 23394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner// name... 24394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner// 25394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattnerstatic Instruction *InsertCast(Instruction *Val, const Type *Ty, 26394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BasicBlock::iterator It) { 27394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Instruction *Cast = new CastInst(Val, Ty); 28394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Val->hasName()) Cast->setName(Val->getName()+"-casted"); 29394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val->getParent()->getInstList().insert(It, Cast); 30394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner return Cast; 31394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 32394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 336148c02591bd83da7b957589c4bbf6f9720d503fChris Lattnerstatic bool TransformLoop(cfg::LoopInfo *Loops, cfg::Loop *Loop) { 346148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Transform all subloops before this loop... 356148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(), 366148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner Loop->getSubLoops().end(), 37697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::bind1st(std::ptr_fun(TransformLoop), Loops)); 386148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Get the header node for this loop. All of the phi nodes that could be 396148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // induction variables must live in this basic block. 406148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner BasicBlock *Header = (BasicBlock*)Loop->getBlocks().front(); 416148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 426148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Loop over all of the PHI nodes in the basic block, calculating the 436148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // induction variables that they represent... stuffing the induction variable 446148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // info into a vector... 456148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // 46697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::vector<InductionVariable> IndVars; // Induction variables for block 476148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner for (BasicBlock::iterator I = Header->begin(); 486148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner PHINode *PN = dyn_cast<PHINode>(*I); ++I) 496148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner IndVars.push_back(InductionVariable(PN, Loops)); 506148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 51394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If there are no phi nodes in this basic block, there can't be indvars... 526148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (IndVars.empty()) return Changed; 536148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 546148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Loop over the induction variables, looking for a cannonical induction 556148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // variable, and checking to make sure they are not all unknown induction 566148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // variables. 576148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // 586148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner bool FoundIndVars = false; 596148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner InductionVariable *Cannonical = 0; 606148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner for (unsigned i = 0; i < IndVars.size(); ++i) { 616148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (IndVars[i].InductionType == InductionVariable::Cannonical) 626148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner Cannonical = &IndVars[i]; 636148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (IndVars[i].InductionType != InductionVariable::Unknown) 646148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner FoundIndVars = true; 656148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner } 666148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 676148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // No induction variables, bail early... don't add a cannonnical indvar 686148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (!FoundIndVars) return Changed; 696148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 706148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Okay, we want to convert other induction variables to use a cannonical 716148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // indvar. If we don't have one, add one now... 726148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (!Cannonical) { 73394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Create the PHI node for the new induction variable 74394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar"); 75394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 76394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Insert the phi node at the end of the other phi nodes... 77394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->getInstList().insert(Header->begin()+IndVars.size(), PN); 78394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 79394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Create the increment instruction to add one to the counter... 80394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Instruction *Add = BinaryOperator::create(Instruction::Add, PN, 81394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner ConstantUInt::get(Type::UIntTy,1), 82394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner "add1-indvar"); 83394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 84394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Insert the add instruction after all of the PHI nodes... 85394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->getInstList().insert(Header->begin()+(IndVars.size()+1), Add); 86394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 87394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Figure out which block is incoming and which is the backedge for the loop 88394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BasicBlock *Incoming, *BackEdgeBlock; 89394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BasicBlock::pred_iterator PI = Header->pred_begin(); 90394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner assert(PI != Header->pred_end() && "Loop headers should have 2 preds!"); 91394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Loop->contains(*PI)) { // First pred is back edge... 92394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BackEdgeBlock = *PI++; 93394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Incoming = *PI++; 94394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } else { 95394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Incoming = *PI++; 96394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BackEdgeBlock = *PI++; 97394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 98394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner assert(PI == Header->pred_end() && "Loop headers should have 2 preds!"); 99394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 100394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Add incoming values for the PHI node... 101394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner PN->addIncoming(Constant::getNullConstant(Type::UIntTy), Incoming); 102394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner PN->addIncoming(Add, BackEdgeBlock); 103394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 104394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Analyze the new induction variable... 105394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner IndVars.push_back(InductionVariable(PN, Loops)); 106394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner assert(IndVars.back().InductionType == InductionVariable::Cannonical && 107394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner "Just inserted cannonical indvar that is not cannonical!"); 108394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Cannonical = &IndVars.back(); 1094753bf21a4310a20ee1454e9dce48c87a06e8d27Chris Lattner Changed = true; 110394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 111394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 112394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#ifdef DEBUG 113394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner cerr << "Induction variables:\n"; 114394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#endif 115394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 116394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Get the current loop iteration count, which is always the value of the 117394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // cannonical phi node... 118394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 119394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner PHINode *IterCount = Cannonical->Phi; 120394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 121394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Loop through and replace all of the auxillary induction variables with 122394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // references to the primary induction variable... 123394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 124394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner unsigned InsertPos = IndVars.size(); 125394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner for (unsigned i = 0; i < IndVars.size(); ++i) { 126394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner InductionVariable *IV = &IndVars[i]; 127394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#ifdef DEBUG 128394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner cerr << IndVars[i]; 129394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#endif 1303bf915f2a296472a6bead0502c88bf74e90ec19bChris Lattner // Don't modify the cannonical indvar or unrecognized indvars... 1313bf915f2a296472a6bead0502c88bf74e90ec19bChris Lattner if (IV != Cannonical && IV->InductionType != InductionVariable::Unknown) { 132394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Instruction *Val = IterCount; 133394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (!isa<ConstantInt>(IV->Step) || // If the step != 1 134394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner !cast<ConstantInt>(IV->Step)->equalsInt(1)) { 135697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::string Name; // Create a scale by the step value... 136394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (IV->Phi->hasName()) Name = IV->Phi->getName()+"-scale"; 137394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 138394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If the types are not compatible, insert a cast now... 139394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Val->getType() != IV->Step->getType()) 140394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val = InsertCast(Val, IV->Step->getType(), 141394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->begin()+InsertPos++); 142394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 143394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step, Name); 144394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Insert the phi node at the end of the other phi nodes... 145394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->getInstList().insert(Header->begin()+InsertPos++, Val); 146394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 147394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 148394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (!isa<Constant>(IV->Start) || // If the start != 0 149394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner !cast<Constant>(IV->Start)->isNullValue()) { 150697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::string Name; // Create a offset by the start value... 151394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (IV->Phi->hasName()) Name = IV->Phi->getName()+"-offset"; 152394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 153394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If the types are not compatible, insert a cast now... 154394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Val->getType() != IV->Start->getType()) 155394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val = InsertCast(Val, IV->Start->getType(), 156394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->begin()+InsertPos++); 157394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 158394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val = BinaryOperator::create(Instruction::Add, Val, IV->Start, Name); 159394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Insert the phi node at the end of the other phi nodes... 160394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->getInstList().insert(Header->begin()+InsertPos++, Val); 161394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 162394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 163394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If the PHI node has a different type than val is, insert a cast now... 164394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Val->getType() != IV->Phi->getType()) 165394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val = InsertCast(Val, IV->Phi->getType(), 166394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->begin()+InsertPos++); 167394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 168394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Replace all uses of the old PHI node with the new computed value... 169394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner IV->Phi->replaceAllUsesWith(Val); 170394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 171394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Move the PHI name to it's new equivalent value... 172697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::string OldName = IV->Phi->getName(); 173394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner IV->Phi->setName(""); 174394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val->setName(OldName); 1756148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 176394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Delete the old, now unused, phi node... 177394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Header->getInstList().remove(IV->Phi); 178394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner delete IV->Phi; 179394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner InsertPos--; // Deleted an instr, decrement insert position 1804753bf21a4310a20ee1454e9dce48c87a06e8d27Chris Lattner Changed = true; 181394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 1826148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner } 1836148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 1846148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner return Changed; 1856148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner} 1866148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 187793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattnerbool InductionVariableSimplify::doit(Method *M, cfg::LoopInfo &Loops) { 1883bf915f2a296472a6bead0502c88bf74e90ec19bChris Lattner if (M->isExternal()) return false; 1893bf915f2a296472a6bead0502c88bf74e90ec19bChris Lattner 1906148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Induction Variables live in the header nodes of the loops of the method... 1916148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner return reduce_apply_bool(Loops.getTopLevelLoops().begin(), 1926148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner Loops.getTopLevelLoops().end(), 1936148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner std::bind1st(std::ptr_fun(TransformLoop), &Loops)); 1946148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner} 195793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner 196793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattnerbool InductionVariableSimplify::runOnMethod(Method *M) { 197793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner return doit(M, getAnalysis<cfg::LoopInfo>()); 198793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner} 199793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner 200793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattnervoid InductionVariableSimplify::getAnalysisUsageInfo(Pass::AnalysisSet &Req, 201793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner Pass::AnalysisSet &Dest, 202793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner Pass::AnalysisSet &Prov) { 203793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner Req.push_back(cfg::LoopInfo::ID); 204793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner} 205