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