0c4807d31aa6163ca0d16a161a8f6e8c047ca495
[oota-llvm.git] / lib / Transforms / Scalar / LoopStrengthReduce.cpp
1 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by Nate Begeman and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass performs a strength reduction on array references inside loops that
11 // have as one or more of their components the loop induction variable.  This is
12 // accomplished by creating a new Value to hold the initial value of the array
13 // access for the first iteration, and then creating a new GEP instruction in
14 // the loop to increment the value by the appropriate amount.
15 //
16 //===----------------------------------------------------------------------===//
17
18 #define DEBUG_TYPE "loop-reduce"
19 #include "llvm/Transforms/Scalar.h"
20 #include "llvm/Constants.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/IntrinsicInst.h"
23 #include "llvm/Type.h"
24 #include "llvm/DerivedTypes.h"
25 #include "llvm/Analysis/Dominators.h"
26 #include "llvm/Analysis/LoopInfo.h"
27 #include "llvm/Analysis/LoopPass.h"
28 #include "llvm/Analysis/ScalarEvolutionExpander.h"
29 #include "llvm/Support/CFG.h"
30 #include "llvm/Support/GetElementPtrTypeIterator.h"
31 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
32 #include "llvm/Transforms/Utils/Local.h"
33 #include "llvm/Target/TargetData.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/Compiler.h"
37 #include "llvm/Target/TargetLowering.h"
38 #include <algorithm>
39 #include <set>
40 using namespace llvm;
41
42 STATISTIC(NumReduced , "Number of GEPs strength reduced");
43 STATISTIC(NumInserted, "Number of PHIs inserted");
44 STATISTIC(NumVariable, "Number of PHIs with variable strides");
45
46 namespace {
47
48   struct BasedUser;
49
50   /// IVStrideUse - Keep track of one use of a strided induction variable, where
51   /// the stride is stored externally.  The Offset member keeps track of the 
52   /// offset from the IV, User is the actual user of the operand, and 'Operand'
53   /// is the operand # of the User that is the use.
54   struct VISIBILITY_HIDDEN IVStrideUse {
55     SCEVHandle Offset;
56     Instruction *User;
57     Value *OperandValToReplace;
58
59     // isUseOfPostIncrementedValue - True if this should use the
60     // post-incremented version of this IV, not the preincremented version.
61     // This can only be set in special cases, such as the terminating setcc
62     // instruction for a loop or uses dominated by the loop.
63     bool isUseOfPostIncrementedValue;
64     
65     IVStrideUse(const SCEVHandle &Offs, Instruction *U, Value *O)
66       : Offset(Offs), User(U), OperandValToReplace(O),
67         isUseOfPostIncrementedValue(false) {}
68   };
69   
70   /// IVUsersOfOneStride - This structure keeps track of all instructions that
71   /// have an operand that is based on the trip count multiplied by some stride.
72   /// The stride for all of these users is common and kept external to this
73   /// structure.
74   struct VISIBILITY_HIDDEN IVUsersOfOneStride {
75     /// Users - Keep track of all of the users of this stride as well as the
76     /// initial value and the operand that uses the IV.
77     std::vector<IVStrideUse> Users;
78     
79     void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand) {
80       Users.push_back(IVStrideUse(Offset, User, Operand));
81     }
82   };
83
84   /// IVInfo - This structure keeps track of one IV expression inserted during
85   /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as
86   /// well as the PHI node and increment value created for rewrite.
87   struct VISIBILITY_HIDDEN IVExpr {
88     SCEVHandle  Stride;
89     SCEVHandle  Base;
90     PHINode    *PHI;
91     Value      *IncV;
92
93     IVExpr()
94       : Stride(SCEVUnknown::getIntegerSCEV(0, Type::Int32Ty)),
95         Base  (SCEVUnknown::getIntegerSCEV(0, Type::Int32Ty)) {}
96     IVExpr(const SCEVHandle &stride, const SCEVHandle &base, PHINode *phi,
97            Value *incv)
98       : Stride(stride), Base(base), PHI(phi), IncV(incv) {}
99   };
100
101   /// IVsOfOneStride - This structure keeps track of all IV expression inserted
102   /// during StrengthReduceStridedIVUsers for a particular stride of the IV.
103   struct VISIBILITY_HIDDEN IVsOfOneStride {
104     std::vector<IVExpr> IVs;
105
106     void addIV(const SCEVHandle &Stride, const SCEVHandle &Base, PHINode *PHI,
107                Value *IncV) {
108       IVs.push_back(IVExpr(Stride, Base, PHI, IncV));
109     }
110   };
111
112   class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
113     LoopInfo *LI;
114     DominatorTree *DT;
115     ScalarEvolution *SE;
116     const TargetData *TD;
117     const Type *UIntPtrTy;
118     bool Changed;
119
120     /// IVUsesByStride - Keep track of all uses of induction variables that we
121     /// are interested in.  The key of the map is the stride of the access.
122     std::map<SCEVHandle, IVUsersOfOneStride> IVUsesByStride;
123
124     /// IVsByStride - Keep track of all IVs that have been inserted for a
125     /// particular stride.
126     std::map<SCEVHandle, IVsOfOneStride> IVsByStride;
127
128     /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
129     /// We use this to iterate over the IVUsesByStride collection without being
130     /// dependent on random ordering of pointers in the process.
131     std::vector<SCEVHandle> StrideOrder;
132
133     /// CastedValues - As we need to cast values to uintptr_t, this keeps track
134     /// of the casted version of each value.  This is accessed by
135     /// getCastedVersionOf.
136     std::map<Value*, Value*> CastedPointers;
137
138     /// DeadInsts - Keep track of instructions we may have made dead, so that
139     /// we can remove them after we are done working.
140     std::set<Instruction*> DeadInsts;
141
142     /// TLI - Keep a pointer of a TargetLowering to consult for determining
143     /// transformation profitability.
144     const TargetLowering *TLI;
145
146   public:
147     static char ID; // Pass ID, replacement for typeid
148     LoopStrengthReduce(const TargetLowering *tli = NULL) : 
149       LoopPass((intptr_t)&ID), TLI(tli) {
150     }
151
152     bool runOnLoop(Loop *L, LPPassManager &LPM);
153
154     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
155       // We split critical edges, so we change the CFG.  However, we do update
156       // many analyses if they are around.
157       AU.addPreservedID(LoopSimplifyID);
158       AU.addPreserved<LoopInfo>();
159       AU.addPreserved<DominanceFrontier>();
160       AU.addPreserved<DominatorTree>();
161
162       AU.addRequiredID(LoopSimplifyID);
163       AU.addRequired<LoopInfo>();
164       AU.addRequired<DominatorTree>();
165       AU.addRequired<TargetData>();
166       AU.addRequired<ScalarEvolution>();
167     }
168     
169     /// getCastedVersionOf - Return the specified value casted to uintptr_t.
170     ///
171     Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V);
172 private:
173     bool AddUsersIfInteresting(Instruction *I, Loop *L,
174                                std::set<Instruction*> &Processed);
175     SCEVHandle GetExpressionSCEV(Instruction *E, Loop *L);
176
177     void OptimizeIndvars(Loop *L);
178     bool FindIVForUser(ICmpInst *Cond, IVStrideUse *&CondUse,
179                        const SCEVHandle *&CondStride);
180
181     unsigned CheckForIVReuse(const SCEVHandle&, IVExpr&, const Type*,
182                              const std::vector<BasedUser>& UsersToProcess);
183
184     bool ValidStride(int64_t, const std::vector<BasedUser>& UsersToProcess);
185
186     void StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
187                                       IVUsersOfOneStride &Uses,
188                                       Loop *L, bool isOnlyStride);
189     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
190   };
191   char LoopStrengthReduce::ID = 0;
192   RegisterPass<LoopStrengthReduce> X("loop-reduce", "Loop Strength Reduction");
193 }
194
195 LoopPass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
196   return new LoopStrengthReduce(TLI);
197 }
198
199 /// getCastedVersionOf - Return the specified value casted to uintptr_t. This
200 /// assumes that the Value* V is of integer or pointer type only.
201 ///
202 Value *LoopStrengthReduce::getCastedVersionOf(Instruction::CastOps opcode, 
203                                               Value *V) {
204   if (V->getType() == UIntPtrTy) return V;
205   if (Constant *CB = dyn_cast<Constant>(V))
206     return ConstantExpr::getCast(opcode, CB, UIntPtrTy);
207
208   Value *&New = CastedPointers[V];
209   if (New) return New;
210   
211   New = SCEVExpander::InsertCastOfTo(opcode, V, UIntPtrTy);
212   DeadInsts.insert(cast<Instruction>(New));
213   return New;
214 }
215
216
217 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
218 /// specified set are trivially dead, delete them and see if this makes any of
219 /// their operands subsequently dead.
220 void LoopStrengthReduce::
221 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
222   while (!Insts.empty()) {
223     Instruction *I = *Insts.begin();
224     Insts.erase(Insts.begin());
225     if (isInstructionTriviallyDead(I)) {
226       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
227         if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
228           Insts.insert(U);
229       SE->deleteInstructionFromRecords(I);
230       I->eraseFromParent();
231       Changed = true;
232     }
233   }
234 }
235
236
237 /// GetExpressionSCEV - Compute and return the SCEV for the specified
238 /// instruction.
239 SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp, Loop *L) {
240   // Pointer to pointer bitcast instructions return the same value as their
241   // operand.
242   if (BitCastInst *BCI = dyn_cast<BitCastInst>(Exp)) {
243     if (SE->hasSCEV(BCI) || !isa<Instruction>(BCI->getOperand(0)))
244       return SE->getSCEV(BCI);
245     SCEVHandle R = GetExpressionSCEV(cast<Instruction>(BCI->getOperand(0)), L);
246     SE->setSCEV(BCI, R);
247     return R;
248   }
249
250   // Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions.
251   // If this is a GEP that SE doesn't know about, compute it now and insert it.
252   // If this is not a GEP, or if we have already done this computation, just let
253   // SE figure it out.
254   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Exp);
255   if (!GEP || SE->hasSCEV(GEP))
256     return SE->getSCEV(Exp);
257     
258   // Analyze all of the subscripts of this getelementptr instruction, looking
259   // for uses that are determined by the trip count of L.  First, skip all
260   // operands the are not dependent on the IV.
261
262   // Build up the base expression.  Insert an LLVM cast of the pointer to
263   // uintptr_t first.
264   SCEVHandle GEPVal = SCEVUnknown::get(
265       getCastedVersionOf(Instruction::PtrToInt, GEP->getOperand(0)));
266
267   gep_type_iterator GTI = gep_type_begin(GEP);
268   
269   for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
270     // If this is a use of a recurrence that we can analyze, and it comes before
271     // Op does in the GEP operand list, we will handle this when we process this
272     // operand.
273     if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
274       const StructLayout *SL = TD->getStructLayout(STy);
275       unsigned Idx = cast<ConstantInt>(GEP->getOperand(i))->getZExtValue();
276       uint64_t Offset = SL->getElementOffset(Idx);
277       GEPVal = SCEVAddExpr::get(GEPVal,
278                                 SCEVUnknown::getIntegerSCEV(Offset, UIntPtrTy));
279     } else {
280       unsigned GEPOpiBits = 
281         GEP->getOperand(i)->getType()->getPrimitiveSizeInBits();
282       unsigned IntPtrBits = UIntPtrTy->getPrimitiveSizeInBits();
283       Instruction::CastOps opcode = (GEPOpiBits < IntPtrBits ? 
284           Instruction::SExt : (GEPOpiBits > IntPtrBits ? Instruction::Trunc :
285             Instruction::BitCast));
286       Value *OpVal = getCastedVersionOf(opcode, GEP->getOperand(i));
287       SCEVHandle Idx = SE->getSCEV(OpVal);
288
289       uint64_t TypeSize = TD->getTypeSize(GTI.getIndexedType());
290       if (TypeSize != 1)
291         Idx = SCEVMulExpr::get(Idx,
292                                SCEVConstant::get(ConstantInt::get(UIntPtrTy,
293                                                                    TypeSize)));
294       GEPVal = SCEVAddExpr::get(GEPVal, Idx);
295     }
296   }
297
298   SE->setSCEV(GEP, GEPVal);
299   return GEPVal;
300 }
301
302 /// getSCEVStartAndStride - Compute the start and stride of this expression,
303 /// returning false if the expression is not a start/stride pair, or true if it
304 /// is.  The stride must be a loop invariant expression, but the start may be
305 /// a mix of loop invariant and loop variant expressions.
306 static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L,
307                                   SCEVHandle &Start, SCEVHandle &Stride) {
308   SCEVHandle TheAddRec = Start;   // Initialize to zero.
309
310   // If the outer level is an AddExpr, the operands are all start values except
311   // for a nested AddRecExpr.
312   if (SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(SH)) {
313     for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i)
314       if (SCEVAddRecExpr *AddRec =
315              dyn_cast<SCEVAddRecExpr>(AE->getOperand(i))) {
316         if (AddRec->getLoop() == L)
317           TheAddRec = SCEVAddExpr::get(AddRec, TheAddRec);
318         else
319           return false;  // Nested IV of some sort?
320       } else {
321         Start = SCEVAddExpr::get(Start, AE->getOperand(i));
322       }
323         
324   } else if (isa<SCEVAddRecExpr>(SH)) {
325     TheAddRec = SH;
326   } else {
327     return false;  // not analyzable.
328   }
329   
330   SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(TheAddRec);
331   if (!AddRec || AddRec->getLoop() != L) return false;
332   
333   // FIXME: Generalize to non-affine IV's.
334   if (!AddRec->isAffine()) return false;
335
336   Start = SCEVAddExpr::get(Start, AddRec->getOperand(0));
337   
338   if (!isa<SCEVConstant>(AddRec->getOperand(1)))
339     DOUT << "[" << L->getHeader()->getName()
340          << "] Variable stride: " << *AddRec << "\n";
341
342   Stride = AddRec->getOperand(1);
343   return true;
344 }
345
346 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
347 /// and now we need to decide whether the user should use the preinc or post-inc
348 /// value.  If this user should use the post-inc version of the IV, return true.
349 ///
350 /// Choosing wrong here can break dominance properties (if we choose to use the
351 /// post-inc value when we cannot) or it can end up adding extra live-ranges to
352 /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
353 /// should use the post-inc value).
354 static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
355                                        Loop *L, DominatorTree *DT, Pass *P) {
356   // If the user is in the loop, use the preinc value.
357   if (L->contains(User->getParent())) return false;
358   
359   BasicBlock *LatchBlock = L->getLoopLatch();
360   
361   // Ok, the user is outside of the loop.  If it is dominated by the latch
362   // block, use the post-inc value.
363   if (DT->dominates(LatchBlock, User->getParent()))
364     return true;
365
366   // There is one case we have to be careful of: PHI nodes.  These little guys
367   // can live in blocks that do not dominate the latch block, but (since their
368   // uses occur in the predecessor block, not the block the PHI lives in) should
369   // still use the post-inc value.  Check for this case now.
370   PHINode *PN = dyn_cast<PHINode>(User);
371   if (!PN) return false;  // not a phi, not dominated by latch block.
372   
373   // Look at all of the uses of IV by the PHI node.  If any use corresponds to
374   // a block that is not dominated by the latch block, give up and use the
375   // preincremented value.
376   unsigned NumUses = 0;
377   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
378     if (PN->getIncomingValue(i) == IV) {
379       ++NumUses;
380       if (!DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
381         return false;
382     }
383
384   // Okay, all uses of IV by PN are in predecessor blocks that really are
385   // dominated by the latch block.  Split the critical edges and use the
386   // post-incremented value.
387   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
388     if (PN->getIncomingValue(i) == IV) {
389       SplitCriticalEdge(PN->getIncomingBlock(i), PN->getParent(), P,
390                         true);
391       // Splitting the critical edge can reduce the number of entries in this
392       // PHI.
393       e = PN->getNumIncomingValues();
394       if (--NumUses == 0) break;
395     }
396   
397   return true;
398 }
399
400   
401
402 /// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
403 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
404 /// return true.  Otherwise, return false.
405 bool LoopStrengthReduce::AddUsersIfInteresting(Instruction *I, Loop *L,
406                                             std::set<Instruction*> &Processed) {
407   if (!I->getType()->isInteger() && !isa<PointerType>(I->getType()))
408       return false;   // Void and FP expressions cannot be reduced.
409   if (!Processed.insert(I).second)
410     return true;    // Instruction already handled.
411   
412   // Get the symbolic expression for this instruction.
413   SCEVHandle ISE = GetExpressionSCEV(I, L);
414   if (isa<SCEVCouldNotCompute>(ISE)) return false;
415   
416   // Get the start and stride for this expression.
417   SCEVHandle Start = SCEVUnknown::getIntegerSCEV(0, ISE->getType());
418   SCEVHandle Stride = Start;
419   if (!getSCEVStartAndStride(ISE, L, Start, Stride))
420     return false;  // Non-reducible symbolic expression, bail out.
421
422   std::vector<Instruction *> IUsers;
423   // Collect all I uses now because IVUseShouldUsePostIncValue may 
424   // invalidate use_iterator.
425   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
426     IUsers.push_back(cast<Instruction>(*UI));
427
428   for (unsigned iused_index = 0, iused_size = IUsers.size(); 
429        iused_index != iused_size; ++iused_index) {
430
431     Instruction *User = IUsers[iused_index];
432
433     // Do not infinitely recurse on PHI nodes.
434     if (isa<PHINode>(User) && Processed.count(User))
435       continue;
436
437     // If this is an instruction defined in a nested loop, or outside this loop,
438     // don't recurse into it.
439     bool AddUserToIVUsers = false;
440     if (LI->getLoopFor(User->getParent()) != L) {
441       DOUT << "FOUND USER in other loop: " << *User
442            << "   OF SCEV: " << *ISE << "\n";
443       AddUserToIVUsers = true;
444     } else if (!AddUsersIfInteresting(User, L, Processed)) {
445       DOUT << "FOUND USER: " << *User
446            << "   OF SCEV: " << *ISE << "\n";
447       AddUserToIVUsers = true;
448     }
449
450     if (AddUserToIVUsers) {
451       IVUsersOfOneStride &StrideUses = IVUsesByStride[Stride];
452       if (StrideUses.Users.empty())     // First occurance of this stride?
453         StrideOrder.push_back(Stride);
454       
455       // Okay, we found a user that we cannot reduce.  Analyze the instruction
456       // and decide what to do with it.  If we are a use inside of the loop, use
457       // the value before incrementation, otherwise use it after incrementation.
458       if (IVUseShouldUsePostIncValue(User, I, L, DT, this)) {
459         // The value used will be incremented by the stride more than we are
460         // expecting, so subtract this off.
461         SCEVHandle NewStart = SCEV::getMinusSCEV(Start, Stride);
462         StrideUses.addUser(NewStart, User, I);
463         StrideUses.Users.back().isUseOfPostIncrementedValue = true;
464         DOUT << "   USING POSTINC SCEV, START=" << *NewStart<< "\n";
465       } else {        
466         StrideUses.addUser(Start, User, I);
467       }
468     }
469   }
470   return true;
471 }
472
473 namespace {
474   /// BasedUser - For a particular base value, keep information about how we've
475   /// partitioned the expression so far.
476   struct BasedUser {
477     /// Base - The Base value for the PHI node that needs to be inserted for
478     /// this use.  As the use is processed, information gets moved from this
479     /// field to the Imm field (below).  BasedUser values are sorted by this
480     /// field.
481     SCEVHandle Base;
482     
483     /// Inst - The instruction using the induction variable.
484     Instruction *Inst;
485
486     /// OperandValToReplace - The operand value of Inst to replace with the
487     /// EmittedBase.
488     Value *OperandValToReplace;
489
490     /// Imm - The immediate value that should be added to the base immediately
491     /// before Inst, because it will be folded into the imm field of the
492     /// instruction.
493     SCEVHandle Imm;
494
495     /// EmittedBase - The actual value* to use for the base value of this
496     /// operation.  This is null if we should just use zero so far.
497     Value *EmittedBase;
498
499     // isUseOfPostIncrementedValue - True if this should use the
500     // post-incremented version of this IV, not the preincremented version.
501     // This can only be set in special cases, such as the terminating setcc
502     // instruction for a loop and uses outside the loop that are dominated by
503     // the loop.
504     bool isUseOfPostIncrementedValue;
505     
506     BasedUser(IVStrideUse &IVSU)
507       : Base(IVSU.Offset), Inst(IVSU.User), 
508         OperandValToReplace(IVSU.OperandValToReplace), 
509         Imm(SCEVUnknown::getIntegerSCEV(0, Base->getType())), EmittedBase(0),
510         isUseOfPostIncrementedValue(IVSU.isUseOfPostIncrementedValue) {}
511
512     // Once we rewrite the code to insert the new IVs we want, update the
513     // operands of Inst to use the new expression 'NewBase', with 'Imm' added
514     // to it.
515     void RewriteInstructionToUseNewBase(const SCEVHandle &NewBase,
516                                         SCEVExpander &Rewriter, Loop *L,
517                                         Pass *P);
518     
519     Value *InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, 
520                                        SCEVExpander &Rewriter,
521                                        Instruction *IP, Loop *L);
522     void dump() const;
523   };
524 }
525
526 void BasedUser::dump() const {
527   cerr << " Base=" << *Base;
528   cerr << " Imm=" << *Imm;
529   if (EmittedBase)
530     cerr << "  EB=" << *EmittedBase;
531
532   cerr << "   Inst: " << *Inst;
533 }
534
535 Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase, 
536                                               SCEVExpander &Rewriter,
537                                               Instruction *IP, Loop *L) {
538   // Figure out where we *really* want to insert this code.  In particular, if
539   // the user is inside of a loop that is nested inside of L, we really don't
540   // want to insert this expression before the user, we'd rather pull it out as
541   // many loops as possible.
542   LoopInfo &LI = Rewriter.getLoopInfo();
543   Instruction *BaseInsertPt = IP;
544   
545   // Figure out the most-nested loop that IP is in.
546   Loop *InsertLoop = LI.getLoopFor(IP->getParent());
547   
548   // If InsertLoop is not L, and InsertLoop is nested inside of L, figure out
549   // the preheader of the outer-most loop where NewBase is not loop invariant.
550   while (InsertLoop && NewBase->isLoopInvariant(InsertLoop)) {
551     BaseInsertPt = InsertLoop->getLoopPreheader()->getTerminator();
552     InsertLoop = InsertLoop->getParentLoop();
553   }
554   
555   // If there is no immediate value, skip the next part.
556   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Imm))
557     if (SC->getValue()->isZero())
558       return Rewriter.expandCodeFor(NewBase, BaseInsertPt);
559
560   Value *Base = Rewriter.expandCodeFor(NewBase, BaseInsertPt);
561
562   // If we are inserting the base and imm values in the same block, make sure to
563   // adjust the IP position if insertion reused a result.
564   if (IP == BaseInsertPt)
565     IP = Rewriter.getInsertionPoint();
566   
567   // Always emit the immediate (if non-zero) into the same block as the user.
568   SCEVHandle NewValSCEV = SCEVAddExpr::get(SCEVUnknown::get(Base), Imm);
569   return Rewriter.expandCodeFor(NewValSCEV, IP);
570   
571 }
572
573
574 // Once we rewrite the code to insert the new IVs we want, update the
575 // operands of Inst to use the new expression 'NewBase', with 'Imm' added
576 // to it.
577 void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase,
578                                                SCEVExpander &Rewriter,
579                                                Loop *L, Pass *P) {
580   if (!isa<PHINode>(Inst)) {
581     // By default, insert code at the user instruction.
582     BasicBlock::iterator InsertPt = Inst;
583     
584     // However, if the Operand is itself an instruction, the (potentially
585     // complex) inserted code may be shared by many users.  Because of this, we
586     // want to emit code for the computation of the operand right before its old
587     // computation.  This is usually safe, because we obviously used to use the
588     // computation when it was computed in its current block.  However, in some
589     // cases (e.g. use of a post-incremented induction variable) the NewBase
590     // value will be pinned to live somewhere after the original computation.
591     // In this case, we have to back off.
592     if (!isUseOfPostIncrementedValue) {
593       if (Instruction *OpInst = dyn_cast<Instruction>(OperandValToReplace)) { 
594         InsertPt = OpInst;
595         while (isa<PHINode>(InsertPt)) ++InsertPt;
596       }
597     }
598     Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
599     // Adjust the type back to match the Inst.
600     if (isa<PointerType>(OperandValToReplace->getType())) {
601       NewVal = new IntToPtrInst(NewVal, OperandValToReplace->getType(), "cast",
602                                 InsertPt);
603     }
604     // Replace the use of the operand Value with the new Phi we just created.
605     Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
606     DOUT << "    CHANGED: IMM =" << *Imm;
607     DOUT << "  \tNEWBASE =" << *NewBase;
608     DOUT << "  \tInst = " << *Inst;
609     return;
610   }
611   
612   // PHI nodes are more complex.  We have to insert one copy of the NewBase+Imm
613   // expression into each operand block that uses it.  Note that PHI nodes can
614   // have multiple entries for the same predecessor.  We use a map to make sure
615   // that a PHI node only has a single Value* for each predecessor (which also
616   // prevents us from inserting duplicate code in some blocks).
617   std::map<BasicBlock*, Value*> InsertedCode;
618   PHINode *PN = cast<PHINode>(Inst);
619   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
620     if (PN->getIncomingValue(i) == OperandValToReplace) {
621       // If this is a critical edge, split the edge so that we do not insert the
622       // code on all predecessor/successor paths.  We do this unless this is the
623       // canonical backedge for this loop, as this can make some inserted code
624       // be in an illegal position.
625       BasicBlock *PHIPred = PN->getIncomingBlock(i);
626       if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 &&
627           (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) {
628         
629         // First step, split the critical edge.
630         SplitCriticalEdge(PHIPred, PN->getParent(), P, true);
631             
632         // Next step: move the basic block.  In particular, if the PHI node
633         // is outside of the loop, and PredTI is in the loop, we want to
634         // move the block to be immediately before the PHI block, not
635         // immediately after PredTI.
636         if (L->contains(PHIPred) && !L->contains(PN->getParent())) {
637           BasicBlock *NewBB = PN->getIncomingBlock(i);
638           NewBB->moveBefore(PN->getParent());
639         }
640         
641         // Splitting the edge can reduce the number of PHI entries we have.
642         e = PN->getNumIncomingValues();
643       }
644
645       Value *&Code = InsertedCode[PN->getIncomingBlock(i)];
646       if (!Code) {
647         // Insert the code into the end of the predecessor block.
648         Instruction *InsertPt = PN->getIncomingBlock(i)->getTerminator();
649         Code = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
650
651         // Adjust the type back to match the PHI.
652         if (isa<PointerType>(PN->getType())) {
653           Code = new IntToPtrInst(Code, PN->getType(), "cast", InsertPt);
654         }
655       }
656       
657       // Replace the use of the operand Value with the new Phi we just created.
658       PN->setIncomingValue(i, Code);
659       Rewriter.clear();
660     }
661   }
662   DOUT << "    CHANGED: IMM =" << *Imm << "  Inst = " << *Inst;
663 }
664
665
666 /// isTargetConstant - Return true if the following can be referenced by the
667 /// immediate field of a target instruction.
668 static bool isTargetConstant(const SCEVHandle &V, const Type *UseTy,
669                              const TargetLowering *TLI) {
670   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
671     int64_t VC = SC->getValue()->getSExtValue();
672     if (TLI) {
673       TargetLowering::AddrMode AM;
674       AM.BaseOffs = VC;
675       return TLI->isLegalAddressingMode(AM, UseTy);
676     } else {
677       // Defaults to PPC. PPC allows a sign-extended 16-bit immediate field.
678       return (VC > -(1 << 16) && VC < (1 << 16)-1);
679     }
680   }
681
682   if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V))
683     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(SU->getValue()))
684       if (TLI && CE->getOpcode() == Instruction::PtrToInt) {
685         Constant *Op0 = CE->getOperand(0);
686         if (GlobalValue *GV = dyn_cast<GlobalValue>(Op0)) {
687           TargetLowering::AddrMode AM;
688           AM.BaseGV = GV;
689           return TLI->isLegalAddressingMode(AM, UseTy);
690         }
691       }
692   return false;
693 }
694
695 /// MoveLoopVariantsToImediateField - Move any subexpressions from Val that are
696 /// loop varying to the Imm operand.
697 static void MoveLoopVariantsToImediateField(SCEVHandle &Val, SCEVHandle &Imm,
698                                             Loop *L) {
699   if (Val->isLoopInvariant(L)) return;  // Nothing to do.
700   
701   if (SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) {
702     std::vector<SCEVHandle> NewOps;
703     NewOps.reserve(SAE->getNumOperands());
704     
705     for (unsigned i = 0; i != SAE->getNumOperands(); ++i)
706       if (!SAE->getOperand(i)->isLoopInvariant(L)) {
707         // If this is a loop-variant expression, it must stay in the immediate
708         // field of the expression.
709         Imm = SCEVAddExpr::get(Imm, SAE->getOperand(i));
710       } else {
711         NewOps.push_back(SAE->getOperand(i));
712       }
713
714     if (NewOps.empty())
715       Val = SCEVUnknown::getIntegerSCEV(0, Val->getType());
716     else
717       Val = SCEVAddExpr::get(NewOps);
718   } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) {
719     // Try to pull immediates out of the start value of nested addrec's.
720     SCEVHandle Start = SARE->getStart();
721     MoveLoopVariantsToImediateField(Start, Imm, L);
722     
723     std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
724     Ops[0] = Start;
725     Val = SCEVAddRecExpr::get(Ops, SARE->getLoop());
726   } else {
727     // Otherwise, all of Val is variant, move the whole thing over.
728     Imm = SCEVAddExpr::get(Imm, Val);
729     Val = SCEVUnknown::getIntegerSCEV(0, Val->getType());
730   }
731 }
732
733
734 /// MoveImmediateValues - Look at Val, and pull out any additions of constants
735 /// that can fit into the immediate field of instructions in the target.
736 /// Accumulate these immediate values into the Imm value.
737 static void MoveImmediateValues(const TargetLowering *TLI,
738                                 Instruction *User,
739                                 SCEVHandle &Val, SCEVHandle &Imm,
740                                 bool isAddress, Loop *L) {
741   const Type *UseTy = User->getType();
742   if (StoreInst *SI = dyn_cast<StoreInst>(User))
743     UseTy = SI->getOperand(0)->getType();
744
745   if (SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) {
746     std::vector<SCEVHandle> NewOps;
747     NewOps.reserve(SAE->getNumOperands());
748     
749     for (unsigned i = 0; i != SAE->getNumOperands(); ++i) {
750       SCEVHandle NewOp = SAE->getOperand(i);
751       MoveImmediateValues(TLI, User, NewOp, Imm, isAddress, L);
752       
753       if (!NewOp->isLoopInvariant(L)) {
754         // If this is a loop-variant expression, it must stay in the immediate
755         // field of the expression.
756         Imm = SCEVAddExpr::get(Imm, NewOp);
757       } else {
758         NewOps.push_back(NewOp);
759       }
760     }
761
762     if (NewOps.empty())
763       Val = SCEVUnknown::getIntegerSCEV(0, Val->getType());
764     else
765       Val = SCEVAddExpr::get(NewOps);
766     return;
767   } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) {
768     // Try to pull immediates out of the start value of nested addrec's.
769     SCEVHandle Start = SARE->getStart();
770     MoveImmediateValues(TLI, User, Start, Imm, isAddress, L);
771     
772     if (Start != SARE->getStart()) {
773       std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
774       Ops[0] = Start;
775       Val = SCEVAddRecExpr::get(Ops, SARE->getLoop());
776     }
777     return;
778   } else if (SCEVMulExpr *SME = dyn_cast<SCEVMulExpr>(Val)) {
779     // Transform "8 * (4 + v)" -> "32 + 8*V" if "32" fits in the immed field.
780     if (isAddress && isTargetConstant(SME->getOperand(0), UseTy, TLI) &&
781         SME->getNumOperands() == 2 && SME->isLoopInvariant(L)) {
782
783       SCEVHandle SubImm = SCEVUnknown::getIntegerSCEV(0, Val->getType());
784       SCEVHandle NewOp = SME->getOperand(1);
785       MoveImmediateValues(TLI, User, NewOp, SubImm, isAddress, L);
786       
787       // If we extracted something out of the subexpressions, see if we can 
788       // simplify this!
789       if (NewOp != SME->getOperand(1)) {
790         // Scale SubImm up by "8".  If the result is a target constant, we are
791         // good.
792         SubImm = SCEVMulExpr::get(SubImm, SME->getOperand(0));
793         if (isTargetConstant(SubImm, UseTy, TLI)) {
794           // Accumulate the immediate.
795           Imm = SCEVAddExpr::get(Imm, SubImm);
796           
797           // Update what is left of 'Val'.
798           Val = SCEVMulExpr::get(SME->getOperand(0), NewOp);
799           return;
800         }
801       }
802     }
803   }
804
805   // Loop-variant expressions must stay in the immediate field of the
806   // expression.
807   if ((isAddress && isTargetConstant(Val, UseTy, TLI)) ||
808       !Val->isLoopInvariant(L)) {
809     Imm = SCEVAddExpr::get(Imm, Val);
810     Val = SCEVUnknown::getIntegerSCEV(0, Val->getType());
811     return;
812   }
813
814   // Otherwise, no immediates to move.
815 }
816
817
818 /// SeparateSubExprs - Decompose Expr into all of the subexpressions that are
819 /// added together.  This is used to reassociate common addition subexprs
820 /// together for maximal sharing when rewriting bases.
821 static void SeparateSubExprs(std::vector<SCEVHandle> &SubExprs,
822                              SCEVHandle Expr) {
823   if (SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(Expr)) {
824     for (unsigned j = 0, e = AE->getNumOperands(); j != e; ++j)
825       SeparateSubExprs(SubExprs, AE->getOperand(j));
826   } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Expr)) {
827     SCEVHandle Zero = SCEVUnknown::getIntegerSCEV(0, Expr->getType());
828     if (SARE->getOperand(0) == Zero) {
829       SubExprs.push_back(Expr);
830     } else {
831       // Compute the addrec with zero as its base.
832       std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
833       Ops[0] = Zero;   // Start with zero base.
834       SubExprs.push_back(SCEVAddRecExpr::get(Ops, SARE->getLoop()));
835       
836
837       SeparateSubExprs(SubExprs, SARE->getOperand(0));
838     }
839   } else if (!isa<SCEVConstant>(Expr) ||
840              !cast<SCEVConstant>(Expr)->getValue()->isZero()) {
841     // Do not add zero.
842     SubExprs.push_back(Expr);
843   }
844 }
845
846
847 /// RemoveCommonExpressionsFromUseBases - Look through all of the uses in Bases,
848 /// removing any common subexpressions from it.  Anything truly common is
849 /// removed, accumulated, and returned.  This looks for things like (a+b+c) and
850 /// (a+c+d) -> (a+c).  The common expression is *removed* from the Bases.
851 static SCEVHandle 
852 RemoveCommonExpressionsFromUseBases(std::vector<BasedUser> &Uses) {
853   unsigned NumUses = Uses.size();
854
855   // Only one use?  Use its base, regardless of what it is!
856   SCEVHandle Zero = SCEVUnknown::getIntegerSCEV(0, Uses[0].Base->getType());
857   SCEVHandle Result = Zero;
858   if (NumUses == 1) {
859     std::swap(Result, Uses[0].Base);
860     return Result;
861   }
862
863   // To find common subexpressions, count how many of Uses use each expression.
864   // If any subexpressions are used Uses.size() times, they are common.
865   std::map<SCEVHandle, unsigned> SubExpressionUseCounts;
866   
867   // UniqueSubExprs - Keep track of all of the subexpressions we see in the
868   // order we see them.
869   std::vector<SCEVHandle> UniqueSubExprs;
870
871   std::vector<SCEVHandle> SubExprs;
872   for (unsigned i = 0; i != NumUses; ++i) {
873     // If the base is zero (which is common), return zero now, there are no
874     // CSEs we can find.
875     if (Uses[i].Base == Zero) return Zero;
876
877     // Split the expression into subexprs.
878     SeparateSubExprs(SubExprs, Uses[i].Base);
879     // Add one to SubExpressionUseCounts for each subexpr present.
880     for (unsigned j = 0, e = SubExprs.size(); j != e; ++j)
881       if (++SubExpressionUseCounts[SubExprs[j]] == 1)
882         UniqueSubExprs.push_back(SubExprs[j]);
883     SubExprs.clear();
884   }
885
886   // Now that we know how many times each is used, build Result.  Iterate over
887   // UniqueSubexprs so that we have a stable ordering.
888   for (unsigned i = 0, e = UniqueSubExprs.size(); i != e; ++i) {
889     std::map<SCEVHandle, unsigned>::iterator I = 
890        SubExpressionUseCounts.find(UniqueSubExprs[i]);
891     assert(I != SubExpressionUseCounts.end() && "Entry not found?");
892     if (I->second == NumUses) {  // Found CSE!
893       Result = SCEVAddExpr::get(Result, I->first);
894     } else {
895       // Remove non-cse's from SubExpressionUseCounts.
896       SubExpressionUseCounts.erase(I);
897     }
898   }
899   
900   // If we found no CSE's, return now.
901   if (Result == Zero) return Result;
902   
903   // Otherwise, remove all of the CSE's we found from each of the base values.
904   for (unsigned i = 0; i != NumUses; ++i) {
905     // Split the expression into subexprs.
906     SeparateSubExprs(SubExprs, Uses[i].Base);
907
908     // Remove any common subexpressions.
909     for (unsigned j = 0, e = SubExprs.size(); j != e; ++j)
910       if (SubExpressionUseCounts.count(SubExprs[j])) {
911         SubExprs.erase(SubExprs.begin()+j);
912         --j; --e;
913       }
914     
915     // Finally, the non-shared expressions together.
916     if (SubExprs.empty())
917       Uses[i].Base = Zero;
918     else
919       Uses[i].Base = SCEVAddExpr::get(SubExprs);
920     SubExprs.clear();
921   }
922  
923   return Result;
924 }
925
926 /// isZero - returns true if the scalar evolution expression is zero.
927 ///
928 static bool isZero(SCEVHandle &V) {
929   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V))
930     return SC->getValue()->isZero();
931   return false;
932 }
933
934 /// ValidStride - Check whether the given Scale is valid for all loads and 
935 /// stores in UsersToProcess.
936 ///
937 bool LoopStrengthReduce::ValidStride(int64_t Scale, 
938                                const std::vector<BasedUser>& UsersToProcess) {
939   for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
940     // If this is a load or other access, pass the type of the access in.
941     const Type *AccessTy = Type::VoidTy;
942     if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst))
943       AccessTy = SI->getOperand(0)->getType();
944     else if (LoadInst *LI = dyn_cast<LoadInst>(UsersToProcess[i].Inst))
945       AccessTy = LI->getType();
946     
947     TargetLowering::AddrMode AM;
948     if (SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm))
949       AM.BaseOffs = SC->getValue()->getSExtValue();
950     AM.Scale = Scale;
951
952     // If load[imm+r*scale] is illegal, bail out.
953     if (!TLI->isLegalAddressingMode(AM, AccessTy))
954       return false;
955   }
956   return true;
957 }
958
959 /// CheckForIVReuse - Returns the multiple if the stride is the multiple
960 /// of a previous stride and it is a legal value for the target addressing
961 /// mode scale component. This allows the users of this stride to be rewritten
962 /// as prev iv * factor. It returns 0 if no reuse is possible.
963 unsigned LoopStrengthReduce::CheckForIVReuse(const SCEVHandle &Stride, 
964                                 IVExpr &IV, const Type *Ty,
965                                 const std::vector<BasedUser>& UsersToProcess) {
966   if (!TLI) return 0;
967
968   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) {
969     int64_t SInt = SC->getValue()->getSExtValue();
970     if (SInt == 1) return 0;
971
972     for (std::map<SCEVHandle, IVsOfOneStride>::iterator SI= IVsByStride.begin(),
973            SE = IVsByStride.end(); SI != SE; ++SI) {
974       int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
975       if (SInt != -SSInt &&
976           (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0))
977         continue;
978       int64_t Scale = SInt / SSInt;
979       // Check that this stride is valid for all the types used for loads and
980       // stores; if it can be used for some and not others, we might as well use
981       // the original stride everywhere, since we have to create the IV for it
982       // anyway.
983       if (ValidStride(Scale, UsersToProcess))
984         for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(),
985                IE = SI->second.IVs.end(); II != IE; ++II)
986           // FIXME: Only handle base == 0 for now.
987           // Only reuse previous IV if it would not require a type conversion.
988           if (isZero(II->Base) && II->Base->getType() == Ty) {
989             IV = *II;
990             return Scale;
991           }
992     }
993   }
994   return 0;
995 }
996
997 /// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that
998 /// returns true if Val's isUseOfPostIncrementedValue is true.
999 static bool PartitionByIsUseOfPostIncrementedValue(const BasedUser &Val) {
1000   return Val.isUseOfPostIncrementedValue;
1001 }
1002
1003 /// isNonConstantNegative - REturn true if the specified scev is negated, but
1004 /// not a constant.
1005 static bool isNonConstantNegative(const SCEVHandle &Expr) {
1006   SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Expr);
1007   if (!Mul) return false;
1008   
1009   // If there is a constant factor, it will be first.
1010   SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
1011   if (!SC) return false;
1012   
1013   // Return true if the value is negative, this matches things like (-42 * V).
1014   return SC->getValue()->getValue().isNegative();
1015 }
1016
1017 /// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
1018 /// stride of IV.  All of the users may have different starting values, and this
1019 /// may not be the only stride (we know it is if isOnlyStride is true).
1020 void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
1021                                                       IVUsersOfOneStride &Uses,
1022                                                       Loop *L,
1023                                                       bool isOnlyStride) {
1024   // Transform our list of users and offsets to a bit more complex table.  In
1025   // this new vector, each 'BasedUser' contains 'Base' the base of the
1026   // strided accessas well as the old information from Uses.  We progressively
1027   // move information from the Base field to the Imm field, until we eventually
1028   // have the full access expression to rewrite the use.
1029   std::vector<BasedUser> UsersToProcess;
1030   UsersToProcess.reserve(Uses.Users.size());
1031   for (unsigned i = 0, e = Uses.Users.size(); i != e; ++i) {
1032     UsersToProcess.push_back(Uses.Users[i]);
1033     
1034     // Move any loop invariant operands from the offset field to the immediate
1035     // field of the use, so that we don't try to use something before it is
1036     // computed.
1037     MoveLoopVariantsToImediateField(UsersToProcess.back().Base,
1038                                     UsersToProcess.back().Imm, L);
1039     assert(UsersToProcess.back().Base->isLoopInvariant(L) &&
1040            "Base value is not loop invariant!");
1041   }
1042
1043   // We now have a whole bunch of uses of like-strided induction variables, but
1044   // they might all have different bases.  We want to emit one PHI node for this
1045   // stride which we fold as many common expressions (between the IVs) into as
1046   // possible.  Start by identifying the common expressions in the base values 
1047   // for the strides (e.g. if we have "A+C+B" and "A+B+D" as our bases, find
1048   // "A+B"), emit it to the preheader, then remove the expression from the
1049   // UsersToProcess base values.
1050   SCEVHandle CommonExprs =
1051     RemoveCommonExpressionsFromUseBases(UsersToProcess);
1052   
1053   // Next, figure out what we can represent in the immediate fields of
1054   // instructions.  If we can represent anything there, move it to the imm
1055   // fields of the BasedUsers.  We do this so that it increases the commonality
1056   // of the remaining uses.
1057   for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
1058     // If the user is not in the current loop, this means it is using the exit
1059     // value of the IV.  Do not put anything in the base, make sure it's all in
1060     // the immediate field to allow as much factoring as possible.
1061     if (!L->contains(UsersToProcess[i].Inst->getParent())) {
1062       UsersToProcess[i].Imm = SCEVAddExpr::get(UsersToProcess[i].Imm,
1063                                                UsersToProcess[i].Base);
1064       UsersToProcess[i].Base = 
1065         SCEVUnknown::getIntegerSCEV(0, UsersToProcess[i].Base->getType());
1066     } else {
1067       
1068       // Addressing modes can be folded into loads and stores.  Be careful that
1069       // the store is through the expression, not of the expression though.
1070       bool isAddress = isa<LoadInst>(UsersToProcess[i].Inst);
1071       if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst)) {
1072         if (SI->getOperand(1) == UsersToProcess[i].OperandValToReplace)
1073           isAddress = true;
1074       } else if (IntrinsicInst *II =
1075                    dyn_cast<IntrinsicInst>(UsersToProcess[i].Inst)) {
1076         // Addressing modes can also be folded into prefetches.
1077         if (II->getIntrinsicID() == Intrinsic::prefetch &&
1078             II->getOperand(1) == UsersToProcess[i].OperandValToReplace)
1079           isAddress = true;
1080       }
1081       
1082       MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base,
1083                           UsersToProcess[i].Imm, isAddress, L);
1084     }
1085   }
1086
1087   // Check if it is possible to reuse a IV with stride that is factor of this
1088   // stride. And the multiple is a number that can be encoded in the scale
1089   // field of the target addressing mode.  And we will have a valid
1090   // instruction after this substition, including the immediate field, if any.
1091   PHINode *NewPHI = NULL;
1092   Value   *IncV   = NULL;
1093   IVExpr   ReuseIV;
1094   unsigned RewriteFactor = CheckForIVReuse(Stride, ReuseIV,
1095                                            CommonExprs->getType(),
1096                                            UsersToProcess);
1097   if (RewriteFactor != 0) {
1098     DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride
1099          << " and BASE " << *ReuseIV.Base << " :\n";
1100     NewPHI = ReuseIV.PHI;
1101     IncV   = ReuseIV.IncV;
1102   }
1103
1104   const Type *ReplacedTy = CommonExprs->getType();
1105   
1106   // Now that we know what we need to do, insert the PHI node itself.
1107   //
1108   DOUT << "INSERTING IV of TYPE " << *ReplacedTy << " of STRIDE "
1109        << *Stride << " and BASE " << *CommonExprs << ": ";
1110
1111   SCEVExpander Rewriter(*SE, *LI);
1112   SCEVExpander PreheaderRewriter(*SE, *LI);
1113   
1114   BasicBlock  *Preheader = L->getLoopPreheader();
1115   Instruction *PreInsertPt = Preheader->getTerminator();
1116   Instruction *PhiInsertBefore = L->getHeader()->begin();
1117   
1118   BasicBlock *LatchBlock = L->getLoopLatch();
1119
1120
1121   // Emit the initial base value into the loop preheader.
1122   Value *CommonBaseV
1123     = PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt);
1124
1125   if (RewriteFactor == 0) {
1126     // Create a new Phi for this base, and stick it in the loop header.
1127     NewPHI = new PHINode(ReplacedTy, "iv.", PhiInsertBefore);
1128     ++NumInserted;
1129   
1130     // Add common base to the new Phi node.
1131     NewPHI->addIncoming(CommonBaseV, Preheader);
1132
1133     // If the stride is negative, insert a sub instead of an add for the
1134     // increment.
1135     bool isNegative = isNonConstantNegative(Stride);
1136     SCEVHandle IncAmount = Stride;
1137     if (isNegative)
1138       IncAmount = SCEV::getNegativeSCEV(Stride);
1139     
1140     // Insert the stride into the preheader.
1141     Value *StrideV = PreheaderRewriter.expandCodeFor(IncAmount, PreInsertPt);
1142     if (!isa<ConstantInt>(StrideV)) ++NumVariable;
1143
1144     // Emit the increment of the base value before the terminator of the loop
1145     // latch block, and add it to the Phi node.
1146     SCEVHandle IncExp = SCEVUnknown::get(StrideV);
1147     if (isNegative)
1148       IncExp = SCEV::getNegativeSCEV(IncExp);
1149     IncExp = SCEVAddExpr::get(SCEVUnknown::get(NewPHI), IncExp);
1150   
1151     IncV = Rewriter.expandCodeFor(IncExp, LatchBlock->getTerminator());
1152     IncV->setName(NewPHI->getName()+".inc");
1153     NewPHI->addIncoming(IncV, LatchBlock);
1154
1155     // Remember this in case a later stride is multiple of this.
1156     IVsByStride[Stride].addIV(Stride, CommonExprs, NewPHI, IncV);
1157     
1158     DOUT << " IV=%" << NewPHI->getNameStr() << " INC=%" << IncV->getNameStr();
1159   } else {
1160     Constant *C = dyn_cast<Constant>(CommonBaseV);
1161     if (!C ||
1162         (!C->isNullValue() &&
1163          !isTargetConstant(SCEVUnknown::get(CommonBaseV), ReplacedTy, TLI)))
1164       // We want the common base emitted into the preheader! This is just
1165       // using cast as a copy so BitCast (no-op cast) is appropriate
1166       CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV->getType(), 
1167                                     "commonbase", PreInsertPt);
1168   }
1169   DOUT << "\n";
1170
1171   // We want to emit code for users inside the loop first.  To do this, we
1172   // rearrange BasedUser so that the entries at the end have
1173   // isUseOfPostIncrementedValue = false, because we pop off the end of the
1174   // vector (so we handle them first).
1175   std::partition(UsersToProcess.begin(), UsersToProcess.end(),
1176                  PartitionByIsUseOfPostIncrementedValue);
1177   
1178   // Sort this by base, so that things with the same base are handled
1179   // together.  By partitioning first and stable-sorting later, we are
1180   // guaranteed that within each base we will pop off users from within the
1181   // loop before users outside of the loop with a particular base.
1182   //
1183   // We would like to use stable_sort here, but we can't.  The problem is that
1184   // SCEVHandle's don't have a deterministic ordering w.r.t to each other, so
1185   // we don't have anything to do a '<' comparison on.  Because we think the
1186   // number of uses is small, do a horrible bubble sort which just relies on
1187   // ==.
1188   for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
1189     // Get a base value.
1190     SCEVHandle Base = UsersToProcess[i].Base;
1191     
1192     // Compact everything with this base to be consequetive with this one.
1193     for (unsigned j = i+1; j != e; ++j) {
1194       if (UsersToProcess[j].Base == Base) {
1195         std::swap(UsersToProcess[i+1], UsersToProcess[j]);
1196         ++i;
1197       }
1198     }
1199   }
1200
1201   // Process all the users now.  This outer loop handles all bases, the inner
1202   // loop handles all users of a particular base.
1203   while (!UsersToProcess.empty()) {
1204     SCEVHandle Base = UsersToProcess.back().Base;
1205
1206     // Emit the code for Base into the preheader.
1207     Value *BaseV = PreheaderRewriter.expandCodeFor(Base, PreInsertPt);
1208
1209     DOUT << "  INSERTING code for BASE = " << *Base << ":";
1210     if (BaseV->hasName())
1211       DOUT << " Result value name = %" << BaseV->getNameStr();
1212     DOUT << "\n";
1213
1214     // If BaseV is a constant other than 0, make sure that it gets inserted into
1215     // the preheader, instead of being forward substituted into the uses.  We do
1216     // this by forcing a BitCast (noop cast) to be inserted into the preheader 
1217     // in this case.
1218     if (Constant *C = dyn_cast<Constant>(BaseV)) {
1219       if (!C->isNullValue() && !isTargetConstant(Base, ReplacedTy, TLI)) {
1220         // We want this constant emitted into the preheader! This is just
1221         // using cast as a copy so BitCast (no-op cast) is appropriate
1222         BaseV = new BitCastInst(BaseV, BaseV->getType(), "preheaderinsert",
1223                              PreInsertPt);       
1224       }
1225     }
1226
1227     // Emit the code to add the immediate offset to the Phi value, just before
1228     // the instructions that we identified as using this stride and base.
1229     do {
1230       // FIXME: Use emitted users to emit other users.
1231       BasedUser &User = UsersToProcess.back();
1232
1233       // If this instruction wants to use the post-incremented value, move it
1234       // after the post-inc and use its value instead of the PHI.
1235       Value *RewriteOp = NewPHI;
1236       if (User.isUseOfPostIncrementedValue) {
1237         RewriteOp = IncV;
1238
1239         // If this user is in the loop, make sure it is the last thing in the
1240         // loop to ensure it is dominated by the increment.
1241         if (L->contains(User.Inst->getParent()))
1242           User.Inst->moveBefore(LatchBlock->getTerminator());
1243       }
1244       if (RewriteOp->getType() != ReplacedTy) {
1245         Instruction::CastOps opcode = Instruction::Trunc;
1246         if (ReplacedTy->getPrimitiveSizeInBits() ==
1247             RewriteOp->getType()->getPrimitiveSizeInBits())
1248           opcode = Instruction::BitCast;
1249         RewriteOp = SCEVExpander::InsertCastOfTo(opcode, RewriteOp, ReplacedTy);
1250       }
1251
1252       SCEVHandle RewriteExpr = SCEVUnknown::get(RewriteOp);
1253
1254       // Clear the SCEVExpander's expression map so that we are guaranteed
1255       // to have the code emitted where we expect it.
1256       Rewriter.clear();
1257
1258       // If we are reusing the iv, then it must be multiplied by a constant
1259       // factor take advantage of addressing mode scale component.
1260       if (RewriteFactor != 0) {
1261         RewriteExpr =
1262           SCEVMulExpr::get(SCEVUnknown::getIntegerSCEV(RewriteFactor,
1263                                                        RewriteExpr->getType()),
1264                            RewriteExpr);
1265
1266         // The common base is emitted in the loop preheader. But since we
1267         // are reusing an IV, it has not been used to initialize the PHI node.
1268         // Add it to the expression used to rewrite the uses.
1269         if (!isa<ConstantInt>(CommonBaseV) ||
1270             !cast<ConstantInt>(CommonBaseV)->isZero())
1271           RewriteExpr = SCEVAddExpr::get(RewriteExpr,
1272                                          SCEVUnknown::get(CommonBaseV));
1273       }
1274
1275       // Now that we know what we need to do, insert code before User for the
1276       // immediate and any loop-variant expressions.
1277       if (!isa<ConstantInt>(BaseV) || !cast<ConstantInt>(BaseV)->isZero())
1278         // Add BaseV to the PHI value if needed.
1279         RewriteExpr = SCEVAddExpr::get(RewriteExpr, SCEVUnknown::get(BaseV));
1280
1281       User.RewriteInstructionToUseNewBase(RewriteExpr, Rewriter, L, this);
1282
1283       // Mark old value we replaced as possibly dead, so that it is elminated
1284       // if we just replaced the last use of that value.
1285       DeadInsts.insert(cast<Instruction>(User.OperandValToReplace));
1286
1287       UsersToProcess.pop_back();
1288       ++NumReduced;
1289
1290       // If there are any more users to process with the same base, process them
1291       // now.  We sorted by base above, so we just have to check the last elt.
1292     } while (!UsersToProcess.empty() && UsersToProcess.back().Base == Base);
1293     // TODO: Next, find out which base index is the most common, pull it out.
1294   }
1295
1296   // IMPORTANT TODO: Figure out how to partition the IV's with this stride, but
1297   // different starting values, into different PHIs.
1298 }
1299
1300 /// FindIVForUser - If Cond has an operand that is an expression of an IV,
1301 /// set the IV user and stride information and return true, otherwise return
1302 /// false.
1303 bool LoopStrengthReduce::FindIVForUser(ICmpInst *Cond, IVStrideUse *&CondUse,
1304                                        const SCEVHandle *&CondStride) {
1305   for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e && !CondUse;
1306        ++Stride) {
1307     std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI = 
1308     IVUsesByStride.find(StrideOrder[Stride]);
1309     assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
1310     
1311     for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
1312          E = SI->second.Users.end(); UI != E; ++UI)
1313       if (UI->User == Cond) {
1314         // NOTE: we could handle setcc instructions with multiple uses here, but
1315         // InstCombine does it as well for simple uses, it's not clear that it
1316         // occurs enough in real life to handle.
1317         CondUse = &*UI;
1318         CondStride = &SI->first;
1319         return true;
1320       }
1321   }
1322   return false;
1323 }    
1324
1325 // OptimizeIndvars - Now that IVUsesByStride is set up with all of the indvar
1326 // uses in the loop, look to see if we can eliminate some, in favor of using
1327 // common indvars for the different uses.
1328 void LoopStrengthReduce::OptimizeIndvars(Loop *L) {
1329   // TODO: implement optzns here.
1330
1331   // Finally, get the terminating condition for the loop if possible.  If we
1332   // can, we want to change it to use a post-incremented version of its
1333   // induction variable, to allow coalescing the live ranges for the IV into
1334   // one register value.
1335   PHINode *SomePHI = cast<PHINode>(L->getHeader()->begin());
1336   BasicBlock  *Preheader = L->getLoopPreheader();
1337   BasicBlock *LatchBlock =
1338    SomePHI->getIncomingBlock(SomePHI->getIncomingBlock(0) == Preheader);
1339   BranchInst *TermBr = dyn_cast<BranchInst>(LatchBlock->getTerminator());
1340   if (!TermBr || TermBr->isUnconditional() || 
1341       !isa<ICmpInst>(TermBr->getCondition()))
1342     return;
1343   ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition());
1344
1345   // Search IVUsesByStride to find Cond's IVUse if there is one.
1346   IVStrideUse *CondUse = 0;
1347   const SCEVHandle *CondStride = 0;
1348
1349   if (!FindIVForUser(Cond, CondUse, CondStride))
1350     return; // setcc doesn't use the IV.
1351   
1352
1353   // It's possible for the setcc instruction to be anywhere in the loop, and
1354   // possible for it to have multiple users.  If it is not immediately before
1355   // the latch block branch, move it.
1356   if (&*++BasicBlock::iterator(Cond) != (Instruction*)TermBr) {
1357     if (Cond->hasOneUse()) {   // Condition has a single use, just move it.
1358       Cond->moveBefore(TermBr);
1359     } else {
1360       // Otherwise, clone the terminating condition and insert into the loopend.
1361       Cond = cast<ICmpInst>(Cond->clone());
1362       Cond->setName(L->getHeader()->getName() + ".termcond");
1363       LatchBlock->getInstList().insert(TermBr, Cond);
1364       
1365       // Clone the IVUse, as the old use still exists!
1366       IVUsesByStride[*CondStride].addUser(CondUse->Offset, Cond,
1367                                          CondUse->OperandValToReplace);
1368       CondUse = &IVUsesByStride[*CondStride].Users.back();
1369     }
1370   }
1371
1372   // If we get to here, we know that we can transform the setcc instruction to
1373   // use the post-incremented version of the IV, allowing us to coalesce the
1374   // live ranges for the IV correctly.
1375   CondUse->Offset = SCEV::getMinusSCEV(CondUse->Offset, *CondStride);
1376   CondUse->isUseOfPostIncrementedValue = true;
1377 }
1378
1379 namespace {
1380   // Constant strides come first which in turns are sorted by their absolute
1381   // values. If absolute values are the same, then positive strides comes first.
1382   // e.g.
1383   // 4, -1, X, 1, 2 ==> 1, -1, 2, 4, X
1384   struct StrideCompare {
1385     bool operator()(const SCEVHandle &LHS, const SCEVHandle &RHS) {
1386       SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS);
1387       SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS);
1388       if (LHSC && RHSC) {
1389         int64_t  LV = LHSC->getValue()->getSExtValue();
1390         int64_t  RV = RHSC->getValue()->getSExtValue();
1391         uint64_t ALV = (LV < 0) ? -LV : LV;
1392         uint64_t ARV = (RV < 0) ? -RV : RV;
1393         if (ALV == ARV)
1394           return LV > RV;
1395         else
1396           return ALV < ARV;
1397       }
1398       return (LHSC && !RHSC);
1399     }
1400   };
1401 }
1402
1403 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) {
1404
1405   LI = &getAnalysis<LoopInfo>();
1406   DT = &getAnalysis<DominatorTree>();
1407   SE = &getAnalysis<ScalarEvolution>();
1408   TD = &getAnalysis<TargetData>();
1409   UIntPtrTy = TD->getIntPtrType();
1410
1411   // Find all uses of induction variables in this loop, and catagorize
1412   // them by stride.  Start by finding all of the PHI nodes in the header for
1413   // this loop.  If they are induction variables, inspect their uses.
1414   std::set<Instruction*> Processed;   // Don't reprocess instructions.
1415   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
1416     AddUsersIfInteresting(I, L, Processed);
1417
1418   // If we have nothing to do, return.
1419   if (IVUsesByStride.empty()) return false;
1420
1421   // Optimize induction variables.  Some indvar uses can be transformed to use
1422   // strides that will be needed for other purposes.  A common example of this
1423   // is the exit test for the loop, which can often be rewritten to use the
1424   // computation of some other indvar to decide when to terminate the loop.
1425   OptimizeIndvars(L);
1426
1427
1428   // FIXME: We can widen subreg IV's here for RISC targets.  e.g. instead of
1429   // doing computation in byte values, promote to 32-bit values if safe.
1430
1431   // FIXME: Attempt to reuse values across multiple IV's.  In particular, we
1432   // could have something like "for(i) { foo(i*8); bar(i*16) }", which should be
1433   // codegened as "for (j = 0;; j+=8) { foo(j); bar(j+j); }" on X86/PPC.  Need
1434   // to be careful that IV's are all the same type.  Only works for intptr_t
1435   // indvars.
1436
1437   // If we only have one stride, we can more aggressively eliminate some things.
1438   bool HasOneStride = IVUsesByStride.size() == 1;
1439
1440 #ifndef NDEBUG
1441   DOUT << "\nLSR on ";
1442   DEBUG(L->dump());
1443 #endif
1444
1445   // IVsByStride keeps IVs for one particular loop.
1446   IVsByStride.clear();
1447
1448   // Sort the StrideOrder so we process larger strides first.
1449   std::stable_sort(StrideOrder.begin(), StrideOrder.end(), StrideCompare());
1450
1451   // Note: this processes each stride/type pair individually.  All users passed
1452   // into StrengthReduceStridedIVUsers have the same type AND stride.  Also,
1453   // node that we iterate over IVUsesByStride indirectly by using StrideOrder.
1454   // This extra layer of indirection makes the ordering of strides deterministic
1455   // - not dependent on map order.
1456   for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e; ++Stride) {
1457     std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI = 
1458       IVUsesByStride.find(StrideOrder[Stride]);
1459     assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
1460     StrengthReduceStridedIVUsers(SI->first, SI->second, L, HasOneStride);
1461   }
1462
1463   // Clean up after ourselves
1464   if (!DeadInsts.empty()) {
1465     DeleteTriviallyDeadInstructions(DeadInsts);
1466
1467     BasicBlock::iterator I = L->getHeader()->begin();
1468     PHINode *PN;
1469     while ((PN = dyn_cast<PHINode>(I))) {
1470       ++I;  // Preincrement iterator to avoid invalidating it when deleting PN.
1471       
1472       // At this point, we know that we have killed one or more GEP
1473       // instructions.  It is worth checking to see if the cann indvar is also
1474       // dead, so that we can remove it as well.  The requirements for the cann
1475       // indvar to be considered dead are:
1476       // 1. the cann indvar has one use
1477       // 2. the use is an add instruction
1478       // 3. the add has one use
1479       // 4. the add is used by the cann indvar
1480       // If all four cases above are true, then we can remove both the add and
1481       // the cann indvar.
1482       // FIXME: this needs to eliminate an induction variable even if it's being
1483       // compared against some value to decide loop termination.
1484       if (PN->hasOneUse()) {
1485         Instruction *BO = dyn_cast<Instruction>(*PN->use_begin());
1486         if (BO && (isa<BinaryOperator>(BO) || isa<CmpInst>(BO))) {
1487           if (BO->hasOneUse() && PN == *(BO->use_begin())) {
1488             DeadInsts.insert(BO);
1489             // Break the cycle, then delete the PHI.
1490             PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
1491             SE->deleteInstructionFromRecords(PN);
1492             PN->eraseFromParent();
1493           }
1494         }
1495       }
1496     }
1497     DeleteTriviallyDeadInstructions(DeadInsts);
1498   }
1499
1500   CastedPointers.clear();
1501   IVUsesByStride.clear();
1502   StrideOrder.clear();
1503   return false;
1504 }