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 "llvm/iOther.h" 14 #include "llvm/Type.h" 15 #include "llvm/ConstantVals.h" 16 #include "Support/STLExtras.h" 17 18 #if 0 19 #define DEBUG 20 #include "llvm/Analysis/Writer.h" 21 #endif 22 23 // InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a 24 // name... 25 // 26 static Instruction *InsertCast(Instruction *Val, const Type *Ty, 27 BasicBlock::iterator It) { 28 Instruction *Cast = new CastInst(Val, Ty); 29 if (Val->hasName()) Cast->setName(Val->getName()+"-casted"); 30 Val->getParent()->getInstList().insert(It, Cast); 31 return Cast; 32 } 33 34 static bool TransformLoop(cfg::LoopInfo *Loops, cfg::Loop *Loop) { 35 // Transform all subloops before this loop... 36 bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(), 37 Loop->getSubLoops().end(), 38 std::bind1st(ptr_fun(TransformLoop), Loops)); 39 // Get the header node for this loop. All of the phi nodes that could be 40 // induction variables must live in this basic block. 41 BasicBlock *Header = (BasicBlock*)Loop->getBlocks().front(); 42 43 // Loop over all of the PHI nodes in the basic block, calculating the 44 // induction variables that they represent... stuffing the induction variable 45 // info into a vector... 46 // 47 vector<InductionVariable> IndVars; // Induction variables for block 48 for (BasicBlock::iterator I = Header->begin(); 49 PHINode *PN = dyn_cast<PHINode>(*I); ++I) 50 IndVars.push_back(InductionVariable(PN, Loops)); 51 52 // If there are no phi nodes in this basic block, there can't be indvars... 53 if (IndVars.empty()) return Changed; 54 55 // Loop over the induction variables, looking for a cannonical induction 56 // variable, and checking to make sure they are not all unknown induction 57 // variables. 58 // 59 bool FoundIndVars = false; 60 InductionVariable *Cannonical = 0; 61 for (unsigned i = 0; i < IndVars.size(); ++i) { 62 if (IndVars[i].InductionType == InductionVariable::Cannonical) 63 Cannonical = &IndVars[i]; 64 if (IndVars[i].InductionType != InductionVariable::Unknown) 65 FoundIndVars = true; 66 } 67 68 // No induction variables, bail early... don't add a cannonnical indvar 69 if (!FoundIndVars) return Changed; 70 71 // Okay, we want to convert other induction variables to use a cannonical 72 // indvar. If we don't have one, add one now... 73 if (!Cannonical) { 74 // Create the PHI node for the new induction variable 75 PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar"); 76 77 // Insert the phi node at the end of the other phi nodes... 78 Header->getInstList().insert(Header->begin()+IndVars.size(), PN); 79 80 // Create the increment instruction to add one to the counter... 81 Instruction *Add = BinaryOperator::create(Instruction::Add, PN, 82 ConstantUInt::get(Type::UIntTy,1), 83 "add1-indvar"); 84 85 // Insert the add instruction after all of the PHI nodes... 86 Header->getInstList().insert(Header->begin()+(IndVars.size()+1), Add); 87 88 // Figure out which block is incoming and which is the backedge for the loop 89 BasicBlock *Incoming, *BackEdgeBlock; 90 BasicBlock::pred_iterator PI = Header->pred_begin(); 91 assert(PI != Header->pred_end() && "Loop headers should have 2 preds!"); 92 if (Loop->contains(*PI)) { // First pred is back edge... 93 BackEdgeBlock = *PI++; 94 Incoming = *PI++; 95 } else { 96 Incoming = *PI++; 97 BackEdgeBlock = *PI++; 98 } 99 assert(PI == Header->pred_end() && "Loop headers should have 2 preds!"); 100 101 // Add incoming values for the PHI node... 102 PN->addIncoming(Constant::getNullConstant(Type::UIntTy), Incoming); 103 PN->addIncoming(Add, BackEdgeBlock); 104 105 // Analyze the new induction variable... 106 IndVars.push_back(InductionVariable(PN, Loops)); 107 assert(IndVars.back().InductionType == InductionVariable::Cannonical && 108 "Just inserted cannonical indvar that is not cannonical!"); 109 Cannonical = &IndVars.back(); 110 } 111 112 #ifdef DEBUG 113 cerr << "Induction variables:\n"; 114 #endif 115 116 // Get the current loop iteration count, which is always the value of the 117 // cannonical phi node... 118 // 119 PHINode *IterCount = Cannonical->Phi; 120 121 // Loop through and replace all of the auxillary induction variables with 122 // references to the primary induction variable... 123 // 124 unsigned InsertPos = IndVars.size(); 125 for (unsigned i = 0; i < IndVars.size(); ++i) { 126 InductionVariable *IV = &IndVars[i]; 127 #ifdef DEBUG 128 cerr << IndVars[i]; 129 #endif 130 if (IV != Cannonical) { // Don't modify the cannonical indvar 131 Instruction *Val = IterCount; 132 if (!isa<ConstantInt>(IV->Step) || // If the step != 1 133 !cast<ConstantInt>(IV->Step)->equalsInt(1)) { 134 string Name; // Create a scale by the step value... 135 if (IV->Phi->hasName()) Name = IV->Phi->getName()+"-scale"; 136 137 // If the types are not compatible, insert a cast now... 138 if (Val->getType() != IV->Step->getType()) 139 Val = InsertCast(Val, IV->Step->getType(), 140 Header->begin()+InsertPos++); 141 142 Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step, Name); 143 // Insert the phi node at the end of the other phi nodes... 144 Header->getInstList().insert(Header->begin()+InsertPos++, Val); 145 } 146 147 if (!isa<Constant>(IV->Start) || // If the start != 0 148 !cast<Constant>(IV->Start)->isNullValue()) { 149 string Name; // Create a offset by the start value... 150 if (IV->Phi->hasName()) Name = IV->Phi->getName()+"-offset"; 151 152 // If the types are not compatible, insert a cast now... 153 if (Val->getType() != IV->Start->getType()) 154 Val = InsertCast(Val, IV->Start->getType(), 155 Header->begin()+InsertPos++); 156 157 Val = BinaryOperator::create(Instruction::Add, Val, IV->Start, Name); 158 // Insert the phi node at the end of the other phi nodes... 159 Header->getInstList().insert(Header->begin()+InsertPos++, Val); 160 } 161 162 // If the PHI node has a different type than val is, insert a cast now... 163 if (Val->getType() != IV->Phi->getType()) 164 Val = InsertCast(Val, IV->Phi->getType(), 165 Header->begin()+InsertPos++); 166 167 // Replace all uses of the old PHI node with the new computed value... 168 IV->Phi->replaceAllUsesWith(Val); 169 170 // Move the PHI name to it's new equivalent value... 171 string OldName = IV->Phi->getName(); 172 IV->Phi->setName(""); 173 Val->setName(OldName); 174 175 // Delete the old, now unused, phi node... 176 Header->getInstList().remove(IV->Phi); 177 delete IV->Phi; 178 InsertPos--; // Deleted an instr, decrement insert position 179 } 180 } 181 182 return Changed; 183 } 184 185 bool InductionVariableSimplify::doit(Method *M) { 186 // Figure out the loop structure of the method... 187 cfg::LoopInfo Loops(M); 188 189 // Induction Variables live in the header nodes of the loops of the method... 190 return reduce_apply_bool(Loops.getTopLevelLoops().begin(), 191 Loops.getTopLevelLoops().end(), 192 std::bind1st(std::ptr_fun(TransformLoop), &Loops)); 193 } 194