1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 2 // 3 // InductionVariableSimplify - Transform induction variables in a program 4 // to all use a single cannonical induction variable per loop. 5 // 6 //===----------------------------------------------------------------------===// 7 8 #include "llvm/Transforms/Scalar/IndVarSimplify.h" 9 #include "llvm/Analysis/InductionVariable.h" 10 #include "llvm/Analysis/LoopInfo.h" 11 #include "llvm/Analysis/Dominators.h" 12 #include "llvm/iPHINode.h" 13 #include "Support/STLExtras.h" 14 15 static bool TransformLoop(cfg::LoopInfo *Loops, cfg::Loop *Loop) { 16 // Transform all subloops before this loop... 17 bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(), 18 Loop->getSubLoops().end(), 19 std::bind1st(ptr_fun(TransformLoop), Loops)); 20 // Get the header node for this loop. All of the phi nodes that could be 21 // induction variables must live in this basic block. 22 BasicBlock *Header = (BasicBlock*)Loop->getBlocks().front(); 23 24 // Loop over all of the PHI nodes in the basic block, calculating the 25 // induction variables that they represent... stuffing the induction variable 26 // info into a vector... 27 // 28 vector<InductionVariable> IndVars; // Induction variables for block 29 for (BasicBlock::iterator I = Header->begin(); 30 PHINode *PN = dyn_cast<PHINode>(*I); ++I) 31 IndVars.push_back(InductionVariable(PN, Loops)); 32 33 // If there are phi nodes in this basic block, there can't be indvars... 34 if (IndVars.empty()) return Changed; 35 36 // Loop over the induction variables, looking for a cannonical induction 37 // variable, and checking to make sure they are not all unknown induction 38 // variables. 39 // 40 bool FoundIndVars = false; 41 InductionVariable *Cannonical = 0; 42 for (unsigned i = 0; i < IndVars.size(); ++i) { 43 if (IndVars[i].InductionType == InductionVariable::Cannonical) 44 Cannonical = &IndVars[i]; 45 if (IndVars[i].InductionType != InductionVariable::Unknown) 46 FoundIndVars = true; 47 } 48 49 // No induction variables, bail early... don't add a cannonnical indvar 50 if (!FoundIndVars) return Changed; 51 52 // Okay, we want to convert other induction variables to use a cannonical 53 // indvar. If we don't have one, add one now... 54 if (!Cannonical) { 55 56 } 57 58 return Changed; 59 } 60 61 bool InductionVariableSimplify::doit(Method *M) { 62 // Figure out the loop structure of the method... 63 cfg::LoopInfo Loops(M); 64 65 // Induction Variables live in the header nodes of the loops of the method... 66 return reduce_apply_bool(Loops.getTopLevelLoops().begin(), 67 Loops.getTopLevelLoops().end(), 68 std::bind1st(std::ptr_fun(TransformLoop), &Loops)); 69 } 70