Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 1 | //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// |
| 2 | // |
Chris Lattner | c01ccfd | 2003-09-10 05:10:34 +0000 | [diff] [blame] | 3 | // Guarantees that all loops with identifiable, linear, induction variables will |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 4 | // be transformed to have a single, canonical, induction variable. After this |
Chris Lattner | c01ccfd | 2003-09-10 05:10:34 +0000 | [diff] [blame] | 5 | // pass runs, it guarantees the the first PHI node of the header block in the |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 6 | // loop is the canonical induction variable if there is one. |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | |
Chris Lattner | 022103b | 2002-05-07 20:03:00 +0000 | [diff] [blame] | 10 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 11 | #include "llvm/Analysis/InductionVariable.h" |
| 12 | #include "llvm/Analysis/LoopInfo.h" |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 13 | #include "llvm/iPHINode.h" |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 14 | #include "llvm/iOther.h" |
| 15 | #include "llvm/Type.h" |
Chris Lattner | 31bcdb8 | 2002-04-28 19:55:58 +0000 | [diff] [blame] | 16 | #include "llvm/Constants.h" |
Chris Lattner | 455889a | 2002-02-12 22:39:50 +0000 | [diff] [blame] | 17 | #include "llvm/Support/CFG.h" |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 18 | #include "Support/Debug.h" |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 19 | #include "Support/Statistic.h" |
Chris Lattner | 6806f56 | 2003-08-01 22:15:03 +0000 | [diff] [blame] | 20 | #include "Support/STLExtras.h" |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 21 | |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 22 | namespace { |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 23 | Statistic<> NumRemoved ("indvars", "Number of aux indvars removed"); |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 24 | Statistic<> NumInserted("indvars", "Number of canonical indvars added"); |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 25 | } |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 26 | |
| 27 | // InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a |
| 28 | // name... |
| 29 | // |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 30 | static Instruction *InsertCast(Value *Val, const Type *Ty, |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 31 | Instruction *InsertBefore) { |
| 32 | return new CastInst(Val, Ty, Val->getName()+"-casted", InsertBefore); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 33 | } |
| 34 | |
Chris Lattner | 1b7f7dc | 2002-04-28 16:21:30 +0000 | [diff] [blame] | 35 | static bool TransformLoop(LoopInfo *Loops, Loop *Loop) { |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 36 | // Transform all subloops before this loop... |
| 37 | bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(), |
| 38 | Loop->getSubLoops().end(), |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 39 | std::bind1st(std::ptr_fun(TransformLoop), Loops)); |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 40 | // Get the header node for this loop. All of the phi nodes that could be |
| 41 | // induction variables must live in this basic block. |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 42 | // |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 43 | BasicBlock *Header = Loop->getHeader(); |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 44 | |
| 45 | // Loop over all of the PHI nodes in the basic block, calculating the |
| 46 | // induction variables that they represent... stuffing the induction variable |
| 47 | // info into a vector... |
| 48 | // |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 49 | std::vector<InductionVariable> IndVars; // Induction variables for block |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 50 | BasicBlock::iterator AfterPHIIt = Header->begin(); |
Chris Lattner | e408e25 | 2003-04-23 16:37:45 +0000 | [diff] [blame] | 51 | for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt) |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 52 | IndVars.push_back(InductionVariable(PN, Loops)); |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 53 | // AfterPHIIt now points to first nonphi instruction... |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 54 | |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 55 | // If there are no phi nodes in this basic block, there can't be indvars... |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 56 | if (IndVars.empty()) return Changed; |
| 57 | |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 58 | // Loop over the induction variables, looking for a canonical induction |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 59 | // variable, and checking to make sure they are not all unknown induction |
| 60 | // variables. |
| 61 | // |
| 62 | bool FoundIndVars = false; |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 63 | InductionVariable *Canonical = 0; |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 64 | for (unsigned i = 0; i < IndVars.size(); ++i) { |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 65 | if (IndVars[i].InductionType == InductionVariable::Canonical && |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 66 | !isa<PointerType>(IndVars[i].Phi->getType())) |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 67 | Canonical = &IndVars[i]; |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 68 | if (IndVars[i].InductionType != InductionVariable::Unknown) |
| 69 | FoundIndVars = true; |
| 70 | } |
| 71 | |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 72 | // No induction variables, bail early... don't add a canonical indvar |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 73 | if (!FoundIndVars) return Changed; |
| 74 | |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 75 | // Okay, we want to convert other induction variables to use a canonical |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 76 | // indvar. If we don't have one, add one now... |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 77 | if (!Canonical) { |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 78 | // Create the PHI node for the new induction variable, and insert the phi |
| 79 | // node at the end of the other phi nodes... |
| 80 | PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar", AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 81 | |
| 82 | // Create the increment instruction to add one to the counter... |
| 83 | Instruction *Add = BinaryOperator::create(Instruction::Add, PN, |
| 84 | ConstantUInt::get(Type::UIntTy,1), |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 85 | "add1-indvar", AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 86 | |
| 87 | // Figure out which block is incoming and which is the backedge for the loop |
| 88 | BasicBlock *Incoming, *BackEdgeBlock; |
Chris Lattner | 455889a | 2002-02-12 22:39:50 +0000 | [diff] [blame] | 89 | pred_iterator PI = pred_begin(Header); |
| 90 | assert(PI != pred_end(Header) && "Loop headers should have 2 preds!"); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 91 | if (Loop->contains(*PI)) { // First pred is back edge... |
| 92 | BackEdgeBlock = *PI++; |
| 93 | Incoming = *PI++; |
| 94 | } else { |
| 95 | Incoming = *PI++; |
| 96 | BackEdgeBlock = *PI++; |
| 97 | } |
Chris Lattner | 455889a | 2002-02-12 22:39:50 +0000 | [diff] [blame] | 98 | assert(PI == pred_end(Header) && "Loop headers should have 2 preds!"); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 99 | |
| 100 | // Add incoming values for the PHI node... |
Chris Lattner | 1a18b7c | 2002-04-27 02:25:14 +0000 | [diff] [blame] | 101 | PN->addIncoming(Constant::getNullValue(Type::UIntTy), Incoming); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 102 | PN->addIncoming(Add, BackEdgeBlock); |
| 103 | |
| 104 | // Analyze the new induction variable... |
| 105 | IndVars.push_back(InductionVariable(PN, Loops)); |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 106 | assert(IndVars.back().InductionType == InductionVariable::Canonical && |
| 107 | "Just inserted canonical indvar that is not canonical!"); |
| 108 | Canonical = &IndVars.back(); |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 109 | ++NumInserted; |
Chris Lattner | 4753bf2 | 2001-12-05 19:41:33 +0000 | [diff] [blame] | 110 | Changed = true; |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 111 | } |
| 112 | |
Anand Shukla | 5ba99bd | 2002-06-25 21:07:58 +0000 | [diff] [blame] | 113 | DEBUG(std::cerr << "Induction variables:\n"); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 114 | |
| 115 | // Get the current loop iteration count, which is always the value of the |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 116 | // canonical phi node... |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 117 | // |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 118 | PHINode *IterCount = Canonical->Phi; |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 119 | |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 120 | // Loop through and replace all of the auxiliary induction variables with |
| 121 | // references to the canonical induction variable... |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 122 | // |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 123 | for (unsigned i = 0; i < IndVars.size(); ++i) { |
| 124 | InductionVariable *IV = &IndVars[i]; |
Chris Lattner | f016ea4 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 125 | |
Chris Lattner | a59cbb2 | 2002-07-27 01:12:17 +0000 | [diff] [blame] | 126 | DEBUG(IV->print(std::cerr)); |
Chris Lattner | f016ea4 | 2002-05-22 17:17:27 +0000 | [diff] [blame] | 127 | |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 128 | // Don't do math with pointers... |
| 129 | const Type *IVTy = IV->Phi->getType(); |
| 130 | if (isa<PointerType>(IVTy)) IVTy = Type::ULongTy; |
| 131 | |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 132 | // Don't modify the canonical indvar or unrecognized indvars... |
| 133 | if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) { |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 134 | Instruction *Val = IterCount; |
| 135 | if (!isa<ConstantInt>(IV->Step) || // If the step != 1 |
| 136 | !cast<ConstantInt>(IV->Step)->equalsInt(1)) { |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 137 | |
| 138 | // If the types are not compatible, insert a cast now... |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 139 | if (Val->getType() != IVTy) |
| 140 | Val = InsertCast(Val, IVTy, AfterPHIIt); |
| 141 | if (IV->Step->getType() != IVTy) |
| 142 | IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 143 | |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 144 | Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step, |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 145 | IV->Phi->getName()+"-scale", AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 146 | } |
| 147 | |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 148 | // If the start != 0 |
| 149 | if (IV->Start != Constant::getNullValue(IV->Start->getType())) { |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 150 | // If the types are not compatible, insert a cast now... |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 151 | if (Val->getType() != IVTy) |
| 152 | Val = InsertCast(Val, IVTy, AfterPHIIt); |
| 153 | if (IV->Start->getType() != IVTy) |
| 154 | IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 155 | |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 156 | // Insert the instruction after the phi nodes... |
Chris Lattner | 5e76140 | 2002-09-10 05:24:05 +0000 | [diff] [blame] | 157 | Val = BinaryOperator::create(Instruction::Add, Val, IV->Start, |
Chris Lattner | 2a7c23e | 2002-09-10 17:04:02 +0000 | [diff] [blame] | 158 | IV->Phi->getName()+"-offset", AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 159 | } |
| 160 | |
| 161 | // If the PHI node has a different type than val is, insert a cast now... |
| 162 | if (Val->getType() != IV->Phi->getType()) |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 163 | Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 164 | |
| 165 | // Replace all uses of the old PHI node with the new computed value... |
| 166 | IV->Phi->replaceAllUsesWith(Val); |
| 167 | |
| 168 | // Move the PHI name to it's new equivalent value... |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 169 | std::string OldName = IV->Phi->getName(); |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 170 | IV->Phi->setName(""); |
| 171 | Val->setName(OldName); |
| 172 | |
| 173 | // Delete the old, now unused, phi node... |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 174 | Header->getInstList().erase(IV->Phi); |
Chris Lattner | 4753bf2 | 2001-12-05 19:41:33 +0000 | [diff] [blame] | 175 | Changed = true; |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 176 | ++NumRemoved; |
Chris Lattner | 394437f | 2001-12-04 04:32:29 +0000 | [diff] [blame] | 177 | } |
Chris Lattner | 6148c02 | 2001-12-03 17:28:42 +0000 | [diff] [blame] | 178 | } |
| 179 | |
| 180 | return Changed; |
| 181 | } |
| 182 | |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 183 | namespace { |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 184 | struct InductionVariableSimplify : public FunctionPass { |
Chris Lattner | 7e70829 | 2002-06-25 16:13:24 +0000 | [diff] [blame] | 185 | virtual bool runOnFunction(Function &) { |
Chris Lattner | 3dec1f2 | 2002-05-10 15:38:35 +0000 | [diff] [blame] | 186 | LoopInfo &LI = getAnalysis<LoopInfo>(); |
| 187 | |
| 188 | // Induction Variables live in the header nodes of loops |
| 189 | return reduce_apply_bool(LI.getTopLevelLoops().begin(), |
| 190 | LI.getTopLevelLoops().end(), |
| 191 | std::bind1st(std::ptr_fun(TransformLoop), &LI)); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 192 | } |
| 193 | |
Chris Lattner | f57b845 | 2002-04-27 06:56:12 +0000 | [diff] [blame] | 194 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Chris Lattner | 5f0eb8d | 2002-08-08 19:01:30 +0000 | [diff] [blame] | 195 | AU.addRequired<LoopInfo>(); |
Chris Lattner | cb2610e | 2002-10-21 20:00:28 +0000 | [diff] [blame] | 196 | AU.setPreservesCFG(); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 197 | } |
| 198 | }; |
Chris Lattner | a6275cc | 2002-07-26 21:12:46 +0000 | [diff] [blame] | 199 | RegisterOpt<InductionVariableSimplify> X("indvars", |
Chris Lattner | 3adf51d | 2003-09-10 05:24:46 +0000 | [diff] [blame^] | 200 | "Canonicalize Induction Variables"); |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 201 | } |
| 202 | |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 203 | Pass *createIndVarSimplifyPass() { |
| 204 | return new InductionVariableSimplify(); |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 205 | } |