IndVarSimplify.cpp revision ba4f3f6a419326df190599421fa149c90235cb72
16148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 96148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 10c01ccfd503057b60053c5e8bf4175062de7c3740Chris Lattner// Guarantees that all loops with identifiable, linear, induction variables will 113adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner// be transformed to have a single, canonical, induction variable. After this 12c01ccfd503057b60053c5e8bf4175062de7c3740Chris Lattner// pass runs, it guarantees the the first PHI node of the header block in the 133adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner// loop is the canonical induction variable if there is one. 146148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner// 156148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner//===----------------------------------------------------------------------===// 166148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 17022103b3f33febb7e54b8fdf2c9bc461eea78cbaChris Lattner#include "llvm/Transforms/Scalar.h" 18ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner#include "llvm/Constants.h" 19ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner#include "llvm/Type.h" 206148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner#include "llvm/iPHINode.h" 21394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner#include "llvm/iOther.h" 22ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner#include "llvm/Analysis/InductionVariable.h" 23ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner#include "llvm/Analysis/LoopInfo.h" 24455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 25ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner#include "llvm/Transforms/Utils/Local.h" 266806f5614d2ec260fda954c951d33f58e77ed610Chris Lattner#include "Support/Debug.h" 27a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner#include "Support/Statistic.h" 286806f5614d2ec260fda954c951d33f58e77ed610Chris Lattner#include "Support/STLExtras.h" 29ba4f3f6a419326df190599421fa149c90235cb72Chris Lattnerusing namespace llvm; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 315e76140536ba66fadeced1cd892f79616f407e3cChris Lattnernamespace { 32a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumRemoved ("indvars", "Number of aux indvars removed"); 333adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner Statistic<> NumInserted("indvars", "Number of canonical indvars added"); 345e76140536ba66fadeced1cd892f79616f407e3cChris Lattner} 35394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 36394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner// InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a 37394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner// name... 38394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner// 395e76140536ba66fadeced1cd892f79616f407e3cChris Lattnerstatic Instruction *InsertCast(Value *Val, const Type *Ty, 402a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner Instruction *InsertBefore) { 412a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner return new CastInst(Val, Ty, Val->getName()+"-casted", InsertBefore); 42394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner} 43394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 441b7f7dc4b45a900fae2e9b062d588a995935727aChris Lattnerstatic bool TransformLoop(LoopInfo *Loops, Loop *Loop) { 456148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Transform all subloops before this loop... 466148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(), 476148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner Loop->getSubLoops().end(), 48697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::bind1st(std::ptr_fun(TransformLoop), Loops)); 496148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Get the header node for this loop. All of the phi nodes that could be 506148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // induction variables must live in this basic block. 513dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner // 523adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner BasicBlock *Header = Loop->getHeader(); 536148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 546148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // Loop over all of the PHI nodes in the basic block, calculating the 556148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // induction variables that they represent... stuffing the induction variable 566148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // info into a vector... 576148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // 58697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::vector<InductionVariable> IndVars; // Induction variables for block 597e70829632f82de15db187845666aaca6e04b792Chris Lattner BasicBlock::iterator AfterPHIIt = Header->begin(); 60e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt) 616148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner IndVars.push_back(InductionVariable(PN, Loops)); 62cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // AfterPHIIt now points to first non-phi instruction... 636148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 64394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If there are no phi nodes in this basic block, there can't be indvars... 656148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (IndVars.empty()) return Changed; 666148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 673adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // Loop over the induction variables, looking for a canonical induction 686148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // variable, and checking to make sure they are not all unknown induction 696148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // variables. 706148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // 716148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner bool FoundIndVars = false; 723adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner InductionVariable *Canonical = 0; 736148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner for (unsigned i = 0; i < IndVars.size(); ++i) { 743adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner if (IndVars[i].InductionType == InductionVariable::Canonical && 755e76140536ba66fadeced1cd892f79616f407e3cChris Lattner !isa<PointerType>(IndVars[i].Phi->getType())) 763adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner Canonical = &IndVars[i]; 776148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (IndVars[i].InductionType != InductionVariable::Unknown) 786148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner FoundIndVars = true; 796148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner } 806148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 813adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // No induction variables, bail early... don't add a canonical indvar 826148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner if (!FoundIndVars) return Changed; 836148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 843adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // Okay, we want to convert other induction variables to use a canonical 856148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner // indvar. If we don't have one, add one now... 863adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner if (!Canonical) { 872a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner // Create the PHI node for the new induction variable, and insert the phi 88332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner // node at the start of the PHI nodes... 89332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar", Header->begin()); 90394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 91394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Create the increment instruction to add one to the counter... 92394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Instruction *Add = BinaryOperator::create(Instruction::Add, PN, 93394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner ConstantUInt::get(Type::UIntTy,1), 942a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner "add1-indvar", AfterPHIIt); 95394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 96394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Figure out which block is incoming and which is the backedge for the loop 97394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BasicBlock *Incoming, *BackEdgeBlock; 98455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner pred_iterator PI = pred_begin(Header); 99455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner assert(PI != pred_end(Header) && "Loop headers should have 2 preds!"); 100394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Loop->contains(*PI)) { // First pred is back edge... 101394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BackEdgeBlock = *PI++; 102394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Incoming = *PI++; 103394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } else { 104394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Incoming = *PI++; 105394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner BackEdgeBlock = *PI++; 106394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 107455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner assert(PI == pred_end(Header) && "Loop headers should have 2 preds!"); 108394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 109394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Add incoming values for the PHI node... 1101a18b7cf805fc6bfc6dc44fb66799ad577d57213Chris Lattner PN->addIncoming(Constant::getNullValue(Type::UIntTy), Incoming); 111394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner PN->addIncoming(Add, BackEdgeBlock); 112394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 113394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Analyze the new induction variable... 114394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner IndVars.push_back(InductionVariable(PN, Loops)); 1153adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner assert(IndVars.back().InductionType == InductionVariable::Canonical && 1163adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner "Just inserted canonical indvar that is not canonical!"); 1173adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner Canonical = &IndVars.back(); 1183dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner ++NumInserted; 1194753bf21a4310a20ee1454e9dce48c87a06e8d27Chris Lattner Changed = true; 120332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner } else { 121332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner // If we have a canonical induction variable, make sure that it is the first 122332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner // one in the basic block. 123332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner if (&Header->front() != Canonical->Phi) 124332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner Header->getInstList().splice(Header->begin(), Header->getInstList(), 125332ae7f501e36d88b1dfdff4f18485ef07663085Chris Lattner Canonical->Phi); 126394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 127394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 1285ba99bd124dc18302f527d6e2b0efd0fa866bc9eAnand Shukla DEBUG(std::cerr << "Induction variables:\n"); 129394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 130394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Get the current loop iteration count, which is always the value of the 1313adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // canonical phi node... 132394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 1333adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner PHINode *IterCount = Canonical->Phi; 134394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 1353adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // Loop through and replace all of the auxiliary induction variables with 1363adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // references to the canonical induction variable... 137394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // 138394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner for (unsigned i = 0; i < IndVars.size(); ++i) { 139394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner InductionVariable *IV = &IndVars[i]; 140f016ea4ff80c56c467247a90567dd07bddb590f3Chris Lattner 141a59cbb2043c08f3cfb8fb379f0d336e21e070be8Chris Lattner DEBUG(IV->print(std::cerr)); 142f016ea4ff80c56c467247a90567dd07bddb590f3Chris Lattner 1435e76140536ba66fadeced1cd892f79616f407e3cChris Lattner // Don't do math with pointers... 1445e76140536ba66fadeced1cd892f79616f407e3cChris Lattner const Type *IVTy = IV->Phi->getType(); 1455e76140536ba66fadeced1cd892f79616f407e3cChris Lattner if (isa<PointerType>(IVTy)) IVTy = Type::ULongTy; 1465e76140536ba66fadeced1cd892f79616f407e3cChris Lattner 1473adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner // Don't modify the canonical indvar or unrecognized indvars... 1483adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) { 149394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Instruction *Val = IterCount; 150394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (!isa<ConstantInt>(IV->Step) || // If the step != 1 151394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner !cast<ConstantInt>(IV->Step)->equalsInt(1)) { 152394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 153394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If the types are not compatible, insert a cast now... 1545e76140536ba66fadeced1cd892f79616f407e3cChris Lattner if (Val->getType() != IVTy) 1555e76140536ba66fadeced1cd892f79616f407e3cChris Lattner Val = InsertCast(Val, IVTy, AfterPHIIt); 1565e76140536ba66fadeced1cd892f79616f407e3cChris Lattner if (IV->Step->getType() != IVTy) 1575e76140536ba66fadeced1cd892f79616f407e3cChris Lattner IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt); 158394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 1595e76140536ba66fadeced1cd892f79616f407e3cChris Lattner Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step, 1602a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner IV->Phi->getName()+"-scale", AfterPHIIt); 161394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 162394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 1635e76140536ba66fadeced1cd892f79616f407e3cChris Lattner // If the start != 0 1645e76140536ba66fadeced1cd892f79616f407e3cChris Lattner if (IV->Start != Constant::getNullValue(IV->Start->getType())) { 165394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If the types are not compatible, insert a cast now... 1665e76140536ba66fadeced1cd892f79616f407e3cChris Lattner if (Val->getType() != IVTy) 1675e76140536ba66fadeced1cd892f79616f407e3cChris Lattner Val = InsertCast(Val, IVTy, AfterPHIIt); 1685e76140536ba66fadeced1cd892f79616f407e3cChris Lattner if (IV->Start->getType() != IVTy) 1695e76140536ba66fadeced1cd892f79616f407e3cChris Lattner IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt); 1705e76140536ba66fadeced1cd892f79616f407e3cChris Lattner 1712a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner // Insert the instruction after the phi nodes... 1725e76140536ba66fadeced1cd892f79616f407e3cChris Lattner Val = BinaryOperator::create(Instruction::Add, Val, IV->Start, 1732a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner IV->Phi->getName()+"-offset", AfterPHIIt); 174394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 175394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 176394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // If the PHI node has a different type than val is, insert a cast now... 177394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner if (Val->getType() != IV->Phi->getType()) 1787e70829632f82de15db187845666aaca6e04b792Chris Lattner Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt); 179394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 180394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Replace all uses of the old PHI node with the new computed value... 181394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner IV->Phi->replaceAllUsesWith(Val); 182394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner 183394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Move the PHI name to it's new equivalent value... 184697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::string OldName = IV->Phi->getName(); 185394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner IV->Phi->setName(""); 186394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner Val->setName(OldName); 1876148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 188ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner // Get the incoming values used by the PHI node 189ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner std::vector<Value*> PHIOps; 190ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner PHIOps.reserve(IV->Phi->getNumIncomingValues()); 191ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner for (unsigned i = 0, e = IV->Phi->getNumIncomingValues(); i != e; ++i) 192ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner PHIOps.push_back(IV->Phi->getIncomingValue(i)); 193ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 194394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner // Delete the old, now unused, phi node... 1957e70829632f82de15db187845666aaca6e04b792Chris Lattner Header->getInstList().erase(IV->Phi); 196ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 197ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner // If the PHI is the last user of any instructions for computing PHI nodes 198ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner // that are irrelevant now, delete those instructions. 199ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner while (!PHIOps.empty()) { 200ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back()); 201ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner PHIOps.pop_back(); 202ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 203ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner if (MaybeDead && isInstructionTriviallyDead(MaybeDead)) { 204ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(), 205ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner MaybeDead->op_end()); 206ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner MaybeDead->getParent()->getInstList().erase(MaybeDead); 207ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner } 208ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner } 209ba4f3f6a419326df190599421fa149c90235cb72Chris Lattner 2104753bf21a4310a20ee1454e9dce48c87a06e8d27Chris Lattner Changed = true; 2113dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner ++NumRemoved; 212394437ff7eaccfe1de92fe14d0022ca0addf3e41Chris Lattner } 2136148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner } 2146148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 2156148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner return Changed; 2166148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner} 2176148c02591bd83da7b957589c4bbf6f9720d503fChris Lattner 218bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattnernamespace { 219f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner struct InductionVariableSimplify : public FunctionPass { 2207e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual bool runOnFunction(Function &) { 2213dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner LoopInfo &LI = getAnalysis<LoopInfo>(); 2223dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner 2233dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner // Induction Variables live in the header nodes of loops 2243dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner return reduce_apply_bool(LI.getTopLevelLoops().begin(), 2253dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner LI.getTopLevelLoops().end(), 2263dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner std::bind1st(std::ptr_fun(TransformLoop), &LI)); 227bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner } 228bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner 229f57b845547302d24ecb6a9e79d7bc386f761a6c9Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 2305f0eb8da62308126d5b61e3eee5bee75b9dc5194Chris Lattner AU.addRequired<LoopInfo>(); 23198bf436e2e2ab463d79c54a42a46b12028905330Chris Lattner AU.addRequiredID(LoopSimplifyID); 232cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 233bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner } 234bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner }; 235a6275ccdf5e1aa208afde56c498e2b13e16442f0Chris Lattner RegisterOpt<InductionVariableSimplify> X("indvars", 2363adf51d022348b06a1adeef7649fa35928ad9358Chris Lattner "Canonicalize Induction Variables"); 237793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner} 238793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner 239ba4f3f6a419326df190599421fa149c90235cb72Chris LattnerPass *llvm::createIndVarSimplifyPass() { 240bd0ef77cde9c9e82f2b4ad33e4982c46274d6540Chris Lattner return new InductionVariableSimplify(); 241793c6b80d3e322c3fefb3c7314b054c7880d1691Chris Lattner} 242d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 243