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