0cc408c61b7e97a209a4472c754537d5853206fe
[oota-llvm.git] / lib / Transforms / Scalar / IndVarSimplify.cpp
1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
2 // 
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 // 
8 //===----------------------------------------------------------------------===//
9 //
10 // Guarantees that all loops with identifiable, linear, induction variables will
11 // be transformed to have a single, canonical, induction variable.  After this
12 // pass runs, it guarantees the the first PHI node of the header block in the
13 // loop is the canonical induction variable if there is one.
14 //
15 //===----------------------------------------------------------------------===//
16
17 #include "llvm/Transforms/Scalar.h"
18 #include "llvm/Analysis/InductionVariable.h"
19 #include "llvm/Analysis/LoopInfo.h"
20 #include "llvm/iPHINode.h"
21 #include "llvm/iOther.h"
22 #include "llvm/Type.h"
23 #include "llvm/Constants.h"
24 #include "llvm/Support/CFG.h"
25 #include "Support/Debug.h"
26 #include "Support/Statistic.h"
27 #include "Support/STLExtras.h"
28 #include <algorithm>
29
30 namespace llvm {
31
32 namespace {
33   Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
34   Statistic<> NumInserted("indvars", "Number of canonical indvars added");
35 }
36
37 // InsertCast - Cast Val to Ty, setting a useful name on the cast if Val has a
38 // name...
39 //
40 static Instruction *InsertCast(Value *Val, const Type *Ty,
41                                Instruction *InsertBefore) {
42   return new CastInst(Val, Ty, Val->getName()+"-casted", InsertBefore);
43 }
44
45 static bool TransformLoop(LoopInfo *Loops, Loop *Loop) {
46   // Transform all subloops before this loop...
47   bool Changed = reduce_apply_bool(Loop->getSubLoops().begin(),
48                                    Loop->getSubLoops().end(),
49                               std::bind1st(std::ptr_fun(TransformLoop), Loops));
50   // Get the header node for this loop.  All of the phi nodes that could be
51   // induction variables must live in this basic block.
52   //
53   BasicBlock *Header = Loop->getHeader();
54   
55   // Loop over all of the PHI nodes in the basic block, calculating the
56   // induction variables that they represent... stuffing the induction variable
57   // info into a vector...
58   //
59   std::vector<InductionVariable> IndVars;    // Induction variables for block
60   BasicBlock::iterator AfterPHIIt = Header->begin();
61   for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt)
62     IndVars.push_back(InductionVariable(PN, Loops));
63   // AfterPHIIt now points to first non-phi instruction...
64
65   // If there are no phi nodes in this basic block, there can't be indvars...
66   if (IndVars.empty()) return Changed;
67   
68   // Loop over the induction variables, looking for a canonical induction
69   // variable, and checking to make sure they are not all unknown induction
70   // variables.
71   //
72   bool FoundIndVars = false;
73   InductionVariable *Canonical = 0;
74   for (unsigned i = 0; i < IndVars.size(); ++i) {
75     if (IndVars[i].InductionType == InductionVariable::Canonical &&
76         !isa<PointerType>(IndVars[i].Phi->getType()))
77       Canonical = &IndVars[i];
78     if (IndVars[i].InductionType != InductionVariable::Unknown)
79       FoundIndVars = true;
80   }
81
82   // No induction variables, bail early... don't add a canonical indvar
83   if (!FoundIndVars) return Changed;
84
85   // Okay, we want to convert other induction variables to use a canonical
86   // indvar.  If we don't have one, add one now...
87   if (!Canonical) {
88     // Create the PHI node for the new induction variable, and insert the phi
89     // node at the start of the PHI nodes...
90     PHINode *PN = new PHINode(Type::UIntTy, "cann-indvar", Header->begin());
91
92     // Create the increment instruction to add one to the counter...
93     Instruction *Add = BinaryOperator::create(Instruction::Add, PN,
94                                               ConstantUInt::get(Type::UIntTy,1),
95                                               "add1-indvar", AfterPHIIt);
96
97     // Figure out which block is incoming and which is the backedge for the loop
98     BasicBlock *Incoming, *BackEdgeBlock;
99     pred_iterator PI = pred_begin(Header);
100     assert(PI != pred_end(Header) && "Loop headers should have 2 preds!");
101     if (Loop->contains(*PI)) {  // First pred is back edge...
102       BackEdgeBlock = *PI++;
103       Incoming      = *PI++;
104     } else {
105       Incoming      = *PI++;
106       BackEdgeBlock = *PI++;
107     }
108     assert(PI == pred_end(Header) && "Loop headers should have 2 preds!");
109     
110     // Add incoming values for the PHI node...
111     PN->addIncoming(Constant::getNullValue(Type::UIntTy), Incoming);
112     PN->addIncoming(Add, BackEdgeBlock);
113
114     // Analyze the new induction variable...
115     IndVars.push_back(InductionVariable(PN, Loops));
116     assert(IndVars.back().InductionType == InductionVariable::Canonical &&
117            "Just inserted canonical indvar that is not canonical!");
118     Canonical = &IndVars.back();
119     ++NumInserted;
120     Changed = true;
121   } else {
122     // If we have a canonical induction variable, make sure that it is the first
123     // one in the basic block.
124     if (&Header->front() != Canonical->Phi)
125       Header->getInstList().splice(Header->begin(), Header->getInstList(),
126                                    Canonical->Phi);
127   }
128
129   DEBUG(std::cerr << "Induction variables:\n");
130
131   // Get the current loop iteration count, which is always the value of the
132   // canonical phi node...
133   //
134   PHINode *IterCount = Canonical->Phi;
135
136   // Loop through and replace all of the auxiliary induction variables with
137   // references to the canonical induction variable...
138   //
139   for (unsigned i = 0; i < IndVars.size(); ++i) {
140     InductionVariable *IV = &IndVars[i];
141
142     DEBUG(IV->print(std::cerr));
143
144     // Don't do math with pointers...
145     const Type *IVTy = IV->Phi->getType();
146     if (isa<PointerType>(IVTy)) IVTy = Type::ULongTy;
147
148     // Don't modify the canonical indvar or unrecognized indvars...
149     if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
150       Instruction *Val = IterCount;
151       if (!isa<ConstantInt>(IV->Step) ||   // If the step != 1
152           !cast<ConstantInt>(IV->Step)->equalsInt(1)) {
153
154         // If the types are not compatible, insert a cast now...
155         if (Val->getType() != IVTy)
156           Val = InsertCast(Val, IVTy, AfterPHIIt);
157         if (IV->Step->getType() != IVTy)
158           IV->Step = InsertCast(IV->Step, IVTy, AfterPHIIt);
159
160         Val = BinaryOperator::create(Instruction::Mul, Val, IV->Step,
161                                      IV->Phi->getName()+"-scale", AfterPHIIt);
162       }
163
164       // If the start != 0
165       if (IV->Start != Constant::getNullValue(IV->Start->getType())) {
166         // If the types are not compatible, insert a cast now...
167         if (Val->getType() != IVTy)
168           Val = InsertCast(Val, IVTy, AfterPHIIt);
169         if (IV->Start->getType() != IVTy)
170           IV->Start = InsertCast(IV->Start, IVTy, AfterPHIIt);
171
172         // Insert the instruction after the phi nodes...
173         Val = BinaryOperator::create(Instruction::Add, Val, IV->Start,
174                                      IV->Phi->getName()+"-offset", AfterPHIIt);
175       }
176
177       // If the PHI node has a different type than val is, insert a cast now...
178       if (Val->getType() != IV->Phi->getType())
179         Val = InsertCast(Val, IV->Phi->getType(), AfterPHIIt);
180       
181       // Replace all uses of the old PHI node with the new computed value...
182       IV->Phi->replaceAllUsesWith(Val);
183
184       // Move the PHI name to it's new equivalent value...
185       std::string OldName = IV->Phi->getName();
186       IV->Phi->setName("");
187       Val->setName(OldName);
188
189       // Delete the old, now unused, phi node...
190       Header->getInstList().erase(IV->Phi);
191
192       // If the PHI is the last user of any instructions for computing PHI nodes
193       // that are irrelevant now, delete those instructions.
194       while (!PHIOps.empty()) {
195         Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back());
196         PHIOps.pop_back();
197
198         if (MaybeDead && isInstructionTriviallyDead(MaybeDead)) {
199           PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(),
200                         MaybeDead->op_end());
201           MaybeDead->getParent()->getInstList().erase(MaybeDead);
202           
203           // Erase any duplicates entries in the PHIOps list.
204           std::vector<Value*>::iterator It =
205             std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
206           while (It != PHIOps.end()) {
207             PHIOps.erase(It);
208             It = std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
209           }
210
211           // Erasing the instruction could invalidate the AfterPHI iterator!
212           AfterPHIIt = Header->begin();
213         }
214       }
215
216       Changed = true;
217       ++NumRemoved;
218     }
219   }
220
221   return Changed;
222 }
223
224 namespace {
225   struct InductionVariableSimplify : public FunctionPass {
226     virtual bool runOnFunction(Function &) {
227       LoopInfo &LI = getAnalysis<LoopInfo>();
228
229       // Induction Variables live in the header nodes of loops
230       return reduce_apply_bool(LI.getTopLevelLoops().begin(),
231                                LI.getTopLevelLoops().end(),
232                                std::bind1st(std::ptr_fun(TransformLoop), &LI));
233     }
234     
235     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
236       AU.addRequired<LoopInfo>();
237       AU.addRequiredID(LoopSimplifyID);
238       AU.setPreservesCFG();
239     }
240   };
241   RegisterOpt<InductionVariableSimplify> X("indvars",
242                                            "Canonicalize Induction Variables");
243 }
244
245 Pass *createIndVarSimplifyPass() {
246   return new InductionVariableSimplify();
247 }
248
249 } // End llvm namespace