lib/Transforms/Scalar/LoopStrengthReduce.cpp

   1 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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 STATISTIC(NumShadow,      "Number of Shadow IVs optimized");
  48
  49 namespace {
  50
  51   struct BasedUser;
  52
  53   /// IVStrideUse - Keep track of one use of a strided induction variable, where
  54   /// the stride is stored externally.  The Offset member keeps track of the
  55   /// offset from the IV, User is the actual user of the operand, and
  56   /// 'OperandValToReplace' is the operand of the User that is the use.
  57   struct VISIBILITY_HIDDEN IVStrideUse {
  58     SCEVHandle Offset;
  59     Instruction *User;
  60     Value *OperandValToReplace;
  61
  62     // isUseOfPostIncrementedValue - True if this should use the
  63     // post-incremented version of this IV, not the preincremented version.
  64     // This can only be set in special cases, such as the terminating setcc
  65     // instruction for a loop or uses dominated by the loop.
  66     bool isUseOfPostIncrementedValue;
  67
  68     IVStrideUse(const SCEVHandle &Offs, Instruction *U, Value *O)
  69       : Offset(Offs), User(U), OperandValToReplace(O),
  70         isUseOfPostIncrementedValue(false) {}
  71   };
  72
  73   /// IVUsersOfOneStride - This structure keeps track of all instructions that
  74   /// have an operand that is based on the trip count multiplied by some stride.
  75   /// The stride for all of these users is common and kept external to this
  76   /// structure.
  77   struct VISIBILITY_HIDDEN IVUsersOfOneStride {
  78     /// Users - Keep track of all of the users of this stride as well as the
  79     /// initial value and the operand that uses the IV.
  80     std::vector<IVStrideUse> Users;
  81
  82     void addUser(const SCEVHandle &Offset,Instruction *User, Value *Operand) {
  83       Users.push_back(IVStrideUse(Offset, User, Operand));
  84     }
  85   };
  86
  87   /// IVInfo - This structure keeps track of one IV expression inserted during
  88   /// StrengthReduceStridedIVUsers. It contains the stride, the common base, as
  89   /// well as the PHI node and increment value created for rewrite.
  90   struct VISIBILITY_HIDDEN IVExpr {
  91     SCEVHandle  Stride;
  92     SCEVHandle  Base;
  93     PHINode    *PHI;
  94     Value      *IncV;
  95
  96     IVExpr(const SCEVHandle &stride, const SCEVHandle &base, PHINode *phi,
  97            Value *incv)
  98       : Stride(stride), Base(base), PHI(phi), IncV(incv) {}
  99   };
 100
 101   /// IVsOfOneStride - This structure keeps track of all IV expression inserted
 102   /// during StrengthReduceStridedIVUsers for a particular stride of the IV.
 103   struct VISIBILITY_HIDDEN IVsOfOneStride {
 104     std::vector<IVExpr> IVs;
 105
 106     void addIV(const SCEVHandle &Stride, const SCEVHandle &Base, PHINode *PHI,
 107                Value *IncV) {
 108       IVs.push_back(IVExpr(Stride, Base, PHI, IncV));
 109     }
 110   };
 111
 112   class VISIBILITY_HIDDEN LoopStrengthReduce : public LoopPass {
 113     LoopInfo *LI;
 114     DominatorTree *DT;
 115     ScalarEvolution *SE;
 116     const TargetData *TD;
 117     const Type *UIntPtrTy;
 118     bool Changed;
 119
 120     /// IVUsesByStride - Keep track of all uses of induction variables that we
 121     /// are interested in.  The key of the map is the stride of the access.
 122     std::map<SCEVHandle, IVUsersOfOneStride> IVUsesByStride;
 123
 124     /// IVsByStride - Keep track of all IVs that have been inserted for a
 125     /// particular stride.
 126     std::map<SCEVHandle, IVsOfOneStride> IVsByStride;
 127
 128     /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
 129     /// We use this to iterate over the IVUsesByStride collection without being
 130     /// dependent on random ordering of pointers in the process.
 131     SmallVector<SCEVHandle, 16> StrideOrder;
 132
 133     /// GEPlist - A list of the GEP's that have been remembered in the SCEV
 134     /// data structures.  SCEV does not know to update these when the operands
 135     /// of the GEP are changed, which means we cannot leave them live across
 136     /// loops.
 137     SmallVector<GetElementPtrInst *, 16> GEPlist;
 138
 139     /// CastedValues - As we need to cast values to uintptr_t, this keeps track
 140     /// of the casted version of each value.  This is accessed by
 141     /// getCastedVersionOf.
 142     DenseMap<Value*, Value*> CastedPointers;
 143
 144     /// DeadInsts - Keep track of instructions we may have made dead, so that
 145     /// we can remove them after we are done working.
 146     SmallVector<Instruction*, 16> DeadInsts;
 147
 148     /// TLI - Keep a pointer of a TargetLowering to consult for determining
 149     /// transformation profitability.
 150     const TargetLowering *TLI;
 151
 152   public:
 153     static char ID; // Pass ID, replacement for typeid
 154     explicit LoopStrengthReduce(const TargetLowering *tli = NULL) :
 155       LoopPass(&ID), TLI(tli) {
 156     }
 157
 158     bool runOnLoop(Loop *L, LPPassManager &LPM);
 159
 160     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 161       // We split critical edges, so we change the CFG.  However, we do update
 162       // many analyses if they are around.
 163       AU.addPreservedID(LoopSimplifyID);
 164       AU.addPreserved<LoopInfo>();
 165       AU.addPreserved<DominanceFrontier>();
 166       AU.addPreserved<DominatorTree>();
 167
 168       AU.addRequiredID(LoopSimplifyID);
 169       AU.addRequired<LoopInfo>();
 170       AU.addRequired<DominatorTree>();
 171       AU.addRequired<TargetData>();
 172       AU.addRequired<ScalarEvolution>();
 173       AU.addPreserved<ScalarEvolution>();
 174     }
 175
 176     /// getCastedVersionOf - Return the specified value casted to uintptr_t.
 177     ///
 178     Value *getCastedVersionOf(Instruction::CastOps opcode, Value *V);
 179 private:
 180     bool AddUsersIfInteresting(Instruction *I, Loop *L,
 181                                SmallPtrSet<Instruction*,16> &Processed);
 182     SCEVHandle GetExpressionSCEV(Instruction *E);
 183     ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
 184                                   IVStrideUse* &CondUse,
 185                                   const SCEVHandle* &CondStride);
 186     void OptimizeIndvars(Loop *L);
 187
 188     /// OptimizeShadowIV - If IV is used in a int-to-float cast
 189     /// inside the loop then try to eliminate the cast opeation.
 190     void OptimizeShadowIV(Loop *L);
 191
 192     /// OptimizeSMax - Rewrite the loop's terminating condition
 193     /// if it uses an smax computation.
 194     ICmpInst *OptimizeSMax(Loop *L, ICmpInst *Cond,
 195                            IVStrideUse* &CondUse);
 196
 197     bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
 198                            const SCEVHandle *&CondStride);
 199     bool RequiresTypeConversion(const Type *Ty, const Type *NewTy);
 200     SCEVHandle CheckForIVReuse(bool, bool, bool, const SCEVHandle&,
 201                              IVExpr&, const Type*,
 202                              const std::vector<BasedUser>& UsersToProcess);
 203     bool ValidStride(bool, int64_t,
 204                      const std::vector<BasedUser>& UsersToProcess);
 205     SCEVHandle CollectIVUsers(const SCEVHandle &Stride,
 206                               IVUsersOfOneStride &Uses,
 207                               Loop *L,
 208                               bool &AllUsesAreAddresses,
 209                               bool &AllUsesAreOutsideLoop,
 210                               std::vector<BasedUser> &UsersToProcess);
 211     void StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
 212                                       IVUsersOfOneStride &Uses,
 213                                       Loop *L, bool isOnlyStride);
 214     void DeleteTriviallyDeadInstructions();
 215   };
 216 }
 217
 218 char LoopStrengthReduce::ID = 0;
 219 static RegisterPass<LoopStrengthReduce>
 220 X("loop-reduce", "Loop Strength Reduction");
 221
 222 Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
 223   return new LoopStrengthReduce(TLI);
 224 }
 225
 226 /// getCastedVersionOf - Return the specified value casted to uintptr_t. This
 227 /// assumes that the Value* V is of integer or pointer type only.
 228 ///
 229 Value *LoopStrengthReduce::getCastedVersionOf(Instruction::CastOps opcode,
 230                                               Value *V) {
 231   if (V->getType() == UIntPtrTy) return V;
 232   if (Constant *CB = dyn_cast<Constant>(V))
 233     return ConstantExpr::getCast(opcode, CB, UIntPtrTy);
 234
 235   Value *&New = CastedPointers[V];
 236   if (New) return New;
 237
 238   New = SCEVExpander::InsertCastOfTo(opcode, V, UIntPtrTy);
 239   DeadInsts.push_back(cast<Instruction>(New));
 240   return New;
 241 }
 242
 243
 244 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
 245 /// specified set are trivially dead, delete them and see if this makes any of
 246 /// their operands subsequently dead.
 247 void LoopStrengthReduce::DeleteTriviallyDeadInstructions() {
 248   if (DeadInsts.empty()) return;
 249
 250   // Sort the deadinsts list so that we can trivially eliminate duplicates as we
 251   // go.  The code below never adds a non-dead instruction to the worklist, but
 252   // callers may not be so careful.
 253   array_pod_sort(DeadInsts.begin(), DeadInsts.end());
 254
 255   // Drop duplicate instructions and those with uses.
 256   for (unsigned i = 0, e = DeadInsts.size()-1; i < e; ++i) {
 257     Instruction *I = DeadInsts[i];
 258     if (!I->use_empty()) DeadInsts[i] = 0;
 259     while (i != e && DeadInsts[i+1] == I)
 260       DeadInsts[++i] = 0;
 261   }
 262
 263   while (!DeadInsts.empty()) {
 264     Instruction *I = DeadInsts.back();
 265     DeadInsts.pop_back();
 266
 267     if (I == 0 || !isInstructionTriviallyDead(I))
 268       continue;
 269
 270     SE->deleteValueFromRecords(I);
 271
 272     for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) {
 273       if (Instruction *U = dyn_cast<Instruction>(*OI)) {
 274         *OI = 0;
 275         if (U->use_empty())
 276           DeadInsts.push_back(U);
 277       }
 278     }
 279
 280     I->eraseFromParent();
 281     Changed = true;
 282   }
 283 }
 284
 285
 286 /// GetExpressionSCEV - Compute and return the SCEV for the specified
 287 /// instruction.
 288 SCEVHandle LoopStrengthReduce::GetExpressionSCEV(Instruction *Exp) {
 289   // Pointer to pointer bitcast instructions return the same value as their
 290   // operand.
 291   if (BitCastInst *BCI = dyn_cast<BitCastInst>(Exp)) {
 292     if (SE->hasSCEV(BCI) || !isa<Instruction>(BCI->getOperand(0)))
 293       return SE->getSCEV(BCI);
 294     SCEVHandle R = GetExpressionSCEV(cast<Instruction>(BCI->getOperand(0)));
 295     SE->setSCEV(BCI, R);
 296     return R;
 297   }
 298
 299   // Scalar Evolutions doesn't know how to compute SCEV's for GEP instructions.
 300   // If this is a GEP that SE doesn't know about, compute it now and insert it.
 301   // If this is not a GEP, or if we have already done this computation, just let
 302   // SE figure it out.
 303   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Exp);
 304   if (!GEP || SE->hasSCEV(GEP))
 305     return SE->getSCEV(Exp);
 306
 307   // Analyze all of the subscripts of this getelementptr instruction, looking
 308   // for uses that are determined by the trip count of the loop.  First, skip
 309   // all operands the are not dependent on the IV.
 310
 311   // Build up the base expression.  Insert an LLVM cast of the pointer to
 312   // uintptr_t first.
 313   SCEVHandle GEPVal = SE->getUnknown(
 314       getCastedVersionOf(Instruction::PtrToInt, GEP->getOperand(0)));
 315
 316   gep_type_iterator GTI = gep_type_begin(GEP);
 317
 318   for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
 319        i != e; ++i, ++GTI) {
 320     // If this is a use of a recurrence that we can analyze, and it comes before
 321     // Op does in the GEP operand list, we will handle this when we process this
 322     // operand.
 323     if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 324       const StructLayout *SL = TD->getStructLayout(STy);
 325       unsigned Idx = cast<ConstantInt>(*i)->getZExtValue();
 326       uint64_t Offset = SL->getElementOffset(Idx);
 327       GEPVal = SE->getAddExpr(GEPVal,
 328                              SE->getIntegerSCEV(Offset, UIntPtrTy));
 329     } else {
 330       unsigned GEPOpiBits =
 331         (*i)->getType()->getPrimitiveSizeInBits();
 332       unsigned IntPtrBits = UIntPtrTy->getPrimitiveSizeInBits();
 333       Instruction::CastOps opcode = (GEPOpiBits < IntPtrBits ?
 334           Instruction::SExt : (GEPOpiBits > IntPtrBits ? Instruction::Trunc :
 335             Instruction::BitCast));
 336       Value *OpVal = getCastedVersionOf(opcode, *i);
 337       SCEVHandle Idx = SE->getSCEV(OpVal);
 338
 339       uint64_t TypeSize = TD->getTypePaddedSize(GTI.getIndexedType());
 340       if (TypeSize != 1)
 341         Idx = SE->getMulExpr(Idx,
 342                             SE->getConstant(ConstantInt::get(UIntPtrTy,
 343                                                              TypeSize)));
 344       GEPVal = SE->getAddExpr(GEPVal, Idx);
 345     }
 346   }
 347
 348   SE->setSCEV(GEP, GEPVal);
 349   GEPlist.push_back(GEP);
 350   return GEPVal;
 351 }
 352
 353 /// containsAddRecFromDifferentLoop - Determine whether expression S involves a
 354 /// subexpression that is an AddRec from a loop other than L.  An outer loop
 355 /// of L is OK, but not an inner loop nor a disjoint loop.
 356 static bool containsAddRecFromDifferentLoop(SCEVHandle S, Loop *L) {
 357   // This is very common, put it first.
 358   if (isa<SCEVConstant>(S))
 359     return false;
 360   if (SCEVCommutativeExpr *AE = dyn_cast<SCEVCommutativeExpr>(S)) {
 361     for (unsigned int i=0; i< AE->getNumOperands(); i++)
 362       if (containsAddRecFromDifferentLoop(AE->getOperand(i), L))
 363         return true;
 364     return false;
 365   }
 366   if (SCEVAddRecExpr *AE = dyn_cast<SCEVAddRecExpr>(S)) {
 367     if (const Loop *newLoop = AE->getLoop()) {
 368       if (newLoop == L)
 369         return false;
 370       // if newLoop is an outer loop of L, this is OK.
 371       if (!LoopInfoBase<BasicBlock>::isNotAlreadyContainedIn(L, newLoop))
 372         return false;
 373     }
 374     return true;
 375   }
 376   if (SCEVUDivExpr *DE = dyn_cast<SCEVUDivExpr>(S))
 377     return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
 378            containsAddRecFromDifferentLoop(DE->getRHS(), L);
 379 #if 0
 380   // SCEVSDivExpr has been backed out temporarily, but will be back; we'll
 381   // need this when it is.
 382   if (SCEVSDivExpr *DE = dyn_cast<SCEVSDivExpr>(S))
 383     return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
 384            containsAddRecFromDifferentLoop(DE->getRHS(), L);
 385 #endif
 386   if (SCEVTruncateExpr *TE = dyn_cast<SCEVTruncateExpr>(S))
 387     return containsAddRecFromDifferentLoop(TE->getOperand(), L);
 388   if (SCEVZeroExtendExpr *ZE = dyn_cast<SCEVZeroExtendExpr>(S))
 389     return containsAddRecFromDifferentLoop(ZE->getOperand(), L);
 390   if (SCEVSignExtendExpr *SE = dyn_cast<SCEVSignExtendExpr>(S))
 391     return containsAddRecFromDifferentLoop(SE->getOperand(), L);
 392   return false;
 393 }
 394
 395 /// getSCEVStartAndStride - Compute the start and stride of this expression,
 396 /// returning false if the expression is not a start/stride pair, or true if it
 397 /// is.  The stride must be a loop invariant expression, but the start may be
 398 /// a mix of loop invariant and loop variant expressions.  The start cannot,
 399 /// however, contain an AddRec from a different loop, unless that loop is an
 400 /// outer loop of the current loop.
 401 static bool getSCEVStartAndStride(const SCEVHandle &SH, Loop *L,
 402                                   SCEVHandle &Start, SCEVHandle &Stride,
 403                                   ScalarEvolution *SE) {
 404   SCEVHandle TheAddRec = Start;   // Initialize to zero.
 405
 406   // If the outer level is an AddExpr, the operands are all start values except
 407   // for a nested AddRecExpr.
 408   if (SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(SH)) {
 409     for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i)
 410       if (SCEVAddRecExpr *AddRec =
 411              dyn_cast<SCEVAddRecExpr>(AE->getOperand(i))) {
 412         if (AddRec->getLoop() == L)
 413           TheAddRec = SE->getAddExpr(AddRec, TheAddRec);
 414         else
 415           return false;  // Nested IV of some sort?
 416       } else {
 417         Start = SE->getAddExpr(Start, AE->getOperand(i));
 418       }
 419
 420   } else if (isa<SCEVAddRecExpr>(SH)) {
 421     TheAddRec = SH;
 422   } else {
 423     return false;  // not analyzable.
 424   }
 425
 426   SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(TheAddRec);
 427   if (!AddRec || AddRec->getLoop() != L) return false;
 428
 429   // FIXME: Generalize to non-affine IV's.
 430   if (!AddRec->isAffine()) return false;
 431
 432   // If Start contains an SCEVAddRecExpr from a different loop, other than an
 433   // outer loop of the current loop, reject it.  SCEV has no concept of
 434   // operating on one loop at a time so don't confuse it with such expressions.
 435   if (containsAddRecFromDifferentLoop(Start, L))
 436     return false;
 437
 438   Start = SE->getAddExpr(Start, AddRec->getOperand(0));
 439
 440   if (!isa<SCEVConstant>(AddRec->getOperand(1)))
 441     DOUT << "[" << L->getHeader()->getName()
 442          << "] Variable stride: " << *AddRec << "\n";
 443
 444   Stride = AddRec->getOperand(1);
 445   return true;
 446 }
 447
 448 /// IVUseShouldUsePostIncValue - We have discovered a "User" of an IV expression
 449 /// and now we need to decide whether the user should use the preinc or post-inc
 450 /// value.  If this user should use the post-inc version of the IV, return true.
 451 ///
 452 /// Choosing wrong here can break dominance properties (if we choose to use the
 453 /// post-inc value when we cannot) or it can end up adding extra live-ranges to
 454 /// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
 455 /// should use the post-inc value).
 456 static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
 457                                        Loop *L, DominatorTree *DT, Pass *P,
 458                                       SmallVectorImpl<Instruction*> &DeadInsts){
 459   // If the user is in the loop, use the preinc value.
 460   if (L->contains(User->getParent())) return false;
 461
 462   BasicBlock *LatchBlock = L->getLoopLatch();
 463
 464   // Ok, the user is outside of the loop.  If it is dominated by the latch
 465   // block, use the post-inc value.
 466   if (DT->dominates(LatchBlock, User->getParent()))
 467     return true;
 468
 469   // There is one case we have to be careful of: PHI nodes.  These little guys
 470   // can live in blocks that do not dominate the latch block, but (since their
 471   // uses occur in the predecessor block, not the block the PHI lives in) should
 472   // still use the post-inc value.  Check for this case now.
 473   PHINode *PN = dyn_cast<PHINode>(User);
 474   if (!PN) return false;  // not a phi, not dominated by latch block.
 475
 476   // Look at all of the uses of IV by the PHI node.  If any use corresponds to
 477   // a block that is not dominated by the latch block, give up and use the
 478   // preincremented value.
 479   unsigned NumUses = 0;
 480   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 481     if (PN->getIncomingValue(i) == IV) {
 482       ++NumUses;
 483       if (!DT->dominates(LatchBlock, PN->getIncomingBlock(i)))
 484         return false;
 485     }
 486
 487   // Okay, all uses of IV by PN are in predecessor blocks that really are
 488   // dominated by the latch block.  Split the critical edges and use the
 489   // post-incremented value.
 490   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 491     if (PN->getIncomingValue(i) == IV) {
 492       SplitCriticalEdge(PN->getIncomingBlock(i), PN->getParent(), P, false);
 493       // Splitting the critical edge can reduce the number of entries in this
 494       // PHI.
 495       e = PN->getNumIncomingValues();
 496       if (--NumUses == 0) break;
 497     }
 498
 499   // PHI node might have become a constant value after SplitCriticalEdge.
 500   DeadInsts.push_back(User);
 501
 502   return true;
 503 }
 504
 505 /// isAddress - Returns true if the specified instruction is using the
 506 /// specified value as an address.
 507 static bool isAddressUse(Instruction *Inst, Value *OperandVal) {
 508   bool isAddress = isa<LoadInst>(Inst);
 509   if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 510     if (SI->getOperand(1) == OperandVal)
 511       isAddress = true;
 512   } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
 513     // Addressing modes can also be folded into prefetches and a variety
 514     // of intrinsics.
 515     switch (II->getIntrinsicID()) {
 516       default: break;
 517       case Intrinsic::prefetch:
 518       case Intrinsic::x86_sse2_loadu_dq:
 519       case Intrinsic::x86_sse2_loadu_pd:
 520       case Intrinsic::x86_sse_loadu_ps:
 521       case Intrinsic::x86_sse_storeu_ps:
 522       case Intrinsic::x86_sse2_storeu_pd:
 523       case Intrinsic::x86_sse2_storeu_dq:
 524       case Intrinsic::x86_sse2_storel_dq:
 525         if (II->getOperand(1) == OperandVal)
 526           isAddress = true;
 527         break;
 528     }
 529   }
 530   return isAddress;
 531 }
 532
 533 /// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
 534 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
 535 /// return true.  Otherwise, return false.
 536 bool LoopStrengthReduce::AddUsersIfInteresting(Instruction *I, Loop *L,
 537                                       SmallPtrSet<Instruction*,16> &Processed) {
 538   if (!I->getType()->isInteger() && !isa<PointerType>(I->getType()))
 539     return false;   // Void and FP expressions cannot be reduced.
 540   if (!Processed.insert(I))
 541     return true;    // Instruction already handled.
 542
 543   // Get the symbolic expression for this instruction.
 544   SCEVHandle ISE = GetExpressionSCEV(I);
 545   if (isa<SCEVCouldNotCompute>(ISE)) return false;
 546
 547   // Get the start and stride for this expression.
 548   SCEVHandle Start = SE->getIntegerSCEV(0, ISE->getType());
 549   SCEVHandle Stride = Start;
 550   if (!getSCEVStartAndStride(ISE, L, Start, Stride, SE))
 551     return false;  // Non-reducible symbolic expression, bail out.
 552
 553   std::vector<Instruction *> IUsers;
 554   // Collect all I uses now because IVUseShouldUsePostIncValue may
 555   // invalidate use_iterator.
 556   for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI)
 557     IUsers.push_back(cast<Instruction>(*UI));
 558
 559   for (unsigned iused_index = 0, iused_size = IUsers.size();
 560        iused_index != iused_size; ++iused_index) {
 561
 562     Instruction *User = IUsers[iused_index];
 563
 564     // Do not infinitely recurse on PHI nodes.
 565     if (isa<PHINode>(User) && Processed.count(User))
 566       continue;
 567
 568     // Descend recursively, but not into PHI nodes outside the current loop.
 569     // It's important to see the entire expression outside the loop to get
 570     // choices that depend on addressing mode use right, although we won't
 571     // consider references ouside the loop in all cases.
 572     // If User is already in Processed, we don't want to recurse into it again,
 573     // but do want to record a second reference in the same instruction.
 574     bool AddUserToIVUsers = false;
 575     if (LI->getLoopFor(User->getParent()) != L) {
 576       if (isa<PHINode>(User) || Processed.count(User) ||
 577           !AddUsersIfInteresting(User, L, Processed)) {
 578         DOUT << "FOUND USER in other loop: " << *User
 579              << "   OF SCEV: " << *ISE << "\n";
 580         AddUserToIVUsers = true;
 581       }
 582     } else if (Processed.count(User) ||
 583                !AddUsersIfInteresting(User, L, Processed)) {
 584       DOUT << "FOUND USER: " << *User
 585            << "   OF SCEV: " << *ISE << "\n";
 586       AddUserToIVUsers = true;
 587     }
 588
 589     if (AddUserToIVUsers) {
 590       IVUsersOfOneStride &StrideUses = IVUsesByStride[Stride];
 591       if (StrideUses.Users.empty())     // First occurrence of this stride?
 592         StrideOrder.push_back(Stride);
 593
 594       // Okay, we found a user that we cannot reduce.  Analyze the instruction
 595       // and decide what to do with it.  If we are a use inside of the loop, use
 596       // the value before incrementation, otherwise use it after incrementation.
 597       if (IVUseShouldUsePostIncValue(User, I, L, DT, this, DeadInsts)) {
 598         // The value used will be incremented by the stride more than we are
 599         // expecting, so subtract this off.
 600         SCEVHandle NewStart = SE->getMinusSCEV(Start, Stride);
 601         StrideUses.addUser(NewStart, User, I);
 602         StrideUses.Users.back().isUseOfPostIncrementedValue = true;
 603         DOUT << "   USING POSTINC SCEV, START=" << *NewStart<< "\n";
 604       } else {
 605         StrideUses.addUser(Start, User, I);
 606       }
 607     }
 608   }
 609   return true;
 610 }
 611
 612 namespace {
 613   /// BasedUser - For a particular base value, keep information about how we've
 614   /// partitioned the expression so far.
 615   struct BasedUser {
 616     /// SE - The current ScalarEvolution object.
 617     ScalarEvolution *SE;
 618
 619     /// Base - The Base value for the PHI node that needs to be inserted for
 620     /// this use.  As the use is processed, information gets moved from this
 621     /// field to the Imm field (below).  BasedUser values are sorted by this
 622     /// field.
 623     SCEVHandle Base;
 624
 625     /// Inst - The instruction using the induction variable.
 626     Instruction *Inst;
 627
 628     /// OperandValToReplace - The operand value of Inst to replace with the
 629     /// EmittedBase.
 630     Value *OperandValToReplace;
 631
 632     /// Imm - The immediate value that should be added to the base immediately
 633     /// before Inst, because it will be folded into the imm field of the
 634     /// instruction.
 635     SCEVHandle Imm;
 636
 637     // isUseOfPostIncrementedValue - True if this should use the
 638     // post-incremented version of this IV, not the preincremented version.
 639     // This can only be set in special cases, such as the terminating setcc
 640     // instruction for a loop and uses outside the loop that are dominated by
 641     // the loop.
 642     bool isUseOfPostIncrementedValue;
 643
 644     BasedUser(IVStrideUse &IVSU, ScalarEvolution *se)
 645       : SE(se), Base(IVSU.Offset), Inst(IVSU.User),
 646         OperandValToReplace(IVSU.OperandValToReplace),
 647         Imm(SE->getIntegerSCEV(0, Base->getType())),
 648         isUseOfPostIncrementedValue(IVSU.isUseOfPostIncrementedValue) {}
 649
 650     // Once we rewrite the code to insert the new IVs we want, update the
 651     // operands of Inst to use the new expression 'NewBase', with 'Imm' added
 652     // to it.
 653     void RewriteInstructionToUseNewBase(const SCEVHandle &NewBase,
 654                                         Instruction *InsertPt,
 655                                        SCEVExpander &Rewriter, Loop *L, Pass *P,
 656                                       SmallVectorImpl<Instruction*> &DeadInsts);
 657
 658     Value *InsertCodeForBaseAtPosition(const SCEVHandle &NewBase,
 659                                        SCEVExpander &Rewriter,
 660                                        Instruction *IP, Loop *L);
 661     void dump() const;
 662   };
 663 }
 664
 665 void BasedUser::dump() const {
 666   cerr << " Base=" << *Base;
 667   cerr << " Imm=" << *Imm;
 668   cerr << "   Inst: " << *Inst;
 669 }
 670
 671 Value *BasedUser::InsertCodeForBaseAtPosition(const SCEVHandle &NewBase,
 672                                               SCEVExpander &Rewriter,
 673                                               Instruction *IP, Loop *L) {
 674   // Figure out where we *really* want to insert this code.  In particular, if
 675   // the user is inside of a loop that is nested inside of L, we really don't
 676   // want to insert this expression before the user, we'd rather pull it out as
 677   // many loops as possible.
 678   LoopInfo &LI = Rewriter.getLoopInfo();
 679   Instruction *BaseInsertPt = IP;
 680
 681   // Figure out the most-nested loop that IP is in.
 682   Loop *InsertLoop = LI.getLoopFor(IP->getParent());
 683
 684   // If InsertLoop is not L, and InsertLoop is nested inside of L, figure out
 685   // the preheader of the outer-most loop where NewBase is not loop invariant.
 686   if (L->contains(IP->getParent()))
 687     while (InsertLoop && NewBase->isLoopInvariant(InsertLoop)) {
 688       BaseInsertPt = InsertLoop->getLoopPreheader()->getTerminator();
 689       InsertLoop = InsertLoop->getParentLoop();
 690     }
 691
 692   // If there is no immediate value, skip the next part.
 693   if (Imm->isZero())
 694     return Rewriter.expandCodeFor(NewBase, BaseInsertPt);
 695
 696   Value *Base = Rewriter.expandCodeFor(NewBase, BaseInsertPt);
 697
 698   // If we are inserting the base and imm values in the same block, make sure to
 699   // adjust the IP position if insertion reused a result.
 700   if (IP == BaseInsertPt)
 701     IP = Rewriter.getInsertionPoint();
 702
 703   // Always emit the immediate (if non-zero) into the same block as the user.
 704   SCEVHandle NewValSCEV = SE->getAddExpr(SE->getUnknown(Base), Imm);
 705   return Rewriter.expandCodeFor(NewValSCEV, IP);
 706
 707 }
 708
 709
 710 // Once we rewrite the code to insert the new IVs we want, update the
 711 // operands of Inst to use the new expression 'NewBase', with 'Imm' added
 712 // to it. NewBasePt is the last instruction which contributes to the
 713 // value of NewBase in the case that it's a diffferent instruction from
 714 // the PHI that NewBase is computed from, or null otherwise.
 715 //
 716 void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase,
 717                                                Instruction *NewBasePt,
 718                                       SCEVExpander &Rewriter, Loop *L, Pass *P,
 719                                       SmallVectorImpl<Instruction*> &DeadInsts){
 720   if (!isa<PHINode>(Inst)) {
 721     // By default, insert code at the user instruction.
 722     BasicBlock::iterator InsertPt = Inst;
 723
 724     // However, if the Operand is itself an instruction, the (potentially
 725     // complex) inserted code may be shared by many users.  Because of this, we
 726     // want to emit code for the computation of the operand right before its old
 727     // computation.  This is usually safe, because we obviously used to use the
 728     // computation when it was computed in its current block.  However, in some
 729     // cases (e.g. use of a post-incremented induction variable) the NewBase
 730     // value will be pinned to live somewhere after the original computation.
 731     // In this case, we have to back off.
 732     //
 733     // If this is a use outside the loop (which means after, since it is based
 734     // on a loop indvar) we use the post-incremented value, so that we don't
 735     // artificially make the preinc value live out the bottom of the loop.
 736     if (!isUseOfPostIncrementedValue && L->contains(Inst->getParent())) {
 737       if (NewBasePt && isa<PHINode>(OperandValToReplace)) {
 738         InsertPt = NewBasePt;
 739         ++InsertPt;
 740       } else if (Instruction *OpInst
 741                  = dyn_cast<Instruction>(OperandValToReplace)) {
 742         InsertPt = OpInst;
 743         while (isa<PHINode>(InsertPt)) ++InsertPt;
 744       }
 745     }
 746     Value *NewVal = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
 747     // Adjust the type back to match the Inst. Note that we can't use InsertPt
 748     // here because the SCEVExpander may have inserted the instructions after
 749     // that point, in its efforts to avoid inserting redundant expressions.
 750     if (isa<PointerType>(OperandValToReplace->getType())) {
 751       NewVal = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr,
 752                                             NewVal,
 753                                             OperandValToReplace->getType());
 754     }
 755     // Replace the use of the operand Value with the new Phi we just created.
 756     Inst->replaceUsesOfWith(OperandValToReplace, NewVal);
 757     DOUT << "    CHANGED: IMM =" << *Imm;
 758     DOUT << "  \tNEWBASE =" << *NewBase;
 759     DOUT << "  \tInst = " << *Inst;
 760     return;
 761   }
 762
 763   // PHI nodes are more complex.  We have to insert one copy of the NewBase+Imm
 764   // expression into each operand block that uses it.  Note that PHI nodes can
 765   // have multiple entries for the same predecessor.  We use a map to make sure
 766   // that a PHI node only has a single Value* for each predecessor (which also
 767   // prevents us from inserting duplicate code in some blocks).
 768   DenseMap<BasicBlock*, Value*> InsertedCode;
 769   PHINode *PN = cast<PHINode>(Inst);
 770   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 771     if (PN->getIncomingValue(i) == OperandValToReplace) {
 772       // If the original expression is outside the loop, put the replacement
 773       // code in the same place as the original expression,
 774       // which need not be an immediate predecessor of this PHI.  This way we
 775       // need only one copy of it even if it is referenced multiple times in
 776       // the PHI.  We don't do this when the original expression is inside the
 777       // loop because multiple copies sometimes do useful sinking of code in
 778       // that case(?).
 779       Instruction *OldLoc = dyn_cast<Instruction>(OperandValToReplace);
 780       if (L->contains(OldLoc->getParent())) {
 781         // If this is a critical edge, split the edge so that we do not insert
 782         // the code on all predecessor/successor paths.  We do this unless this
 783         // is the canonical backedge for this loop, as this can make some
 784         // inserted code be in an illegal position.
 785         BasicBlock *PHIPred = PN->getIncomingBlock(i);
 786         if (e != 1 && PHIPred->getTerminator()->getNumSuccessors() > 1 &&
 787             (PN->getParent() != L->getHeader() || !L->contains(PHIPred))) {
 788
 789           // First step, split the critical edge.
 790           SplitCriticalEdge(PHIPred, PN->getParent(), P, false);
 791
 792           // Next step: move the basic block.  In particular, if the PHI node
 793           // is outside of the loop, and PredTI is in the loop, we want to
 794           // move the block to be immediately before the PHI block, not
 795           // immediately after PredTI.
 796           if (L->contains(PHIPred) && !L->contains(PN->getParent())) {
 797             BasicBlock *NewBB = PN->getIncomingBlock(i);
 798             NewBB->moveBefore(PN->getParent());
 799           }
 800
 801           // Splitting the edge can reduce the number of PHI entries we have.
 802           e = PN->getNumIncomingValues();
 803         }
 804       }
 805       Value *&Code = InsertedCode[PN->getIncomingBlock(i)];
 806       if (!Code) {
 807         // Insert the code into the end of the predecessor block.
 808         Instruction *InsertPt = (L->contains(OldLoc->getParent())) ?
 809                                 PN->getIncomingBlock(i)->getTerminator() :
 810                                 OldLoc->getParent()->getTerminator();
 811         Code = InsertCodeForBaseAtPosition(NewBase, Rewriter, InsertPt, L);
 812
 813         // Adjust the type back to match the PHI. Note that we can't use
 814         // InsertPt here because the SCEVExpander may have inserted its
 815         // instructions after that point, in its efforts to avoid inserting
 816         // redundant expressions.
 817         if (isa<PointerType>(PN->getType())) {
 818           Code = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr,
 819                                               Code,
 820                                               PN->getType());
 821         }
 822       }
 823
 824       // Replace the use of the operand Value with the new Phi we just created.
 825       PN->setIncomingValue(i, Code);
 826       Rewriter.clear();
 827     }
 828   }
 829
 830   // PHI node might have become a constant value after SplitCriticalEdge.
 831   DeadInsts.push_back(Inst);
 832
 833   DOUT << "    CHANGED: IMM =" << *Imm << "  Inst = " << *Inst;
 834 }
 835
 836
 837 /// fitsInAddressMode - Return true if V can be subsumed within an addressing
 838 /// mode, and does not need to be put in a register first.
 839 static bool fitsInAddressMode(const SCEVHandle &V, const Type *UseTy,
 840                              const TargetLowering *TLI, bool HasBaseReg) {
 841   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(V)) {
 842     int64_t VC = SC->getValue()->getSExtValue();
 843     if (TLI) {
 844       TargetLowering::AddrMode AM;
 845       AM.BaseOffs = VC;
 846       AM.HasBaseReg = HasBaseReg;
 847       return TLI->isLegalAddressingMode(AM, UseTy);
 848     } else {
 849       // Defaults to PPC. PPC allows a sign-extended 16-bit immediate field.
 850       return (VC > -(1 << 16) && VC < (1 << 16)-1);
 851     }
 852   }
 853
 854   if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V))
 855     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(SU->getValue()))
 856       if (TLI && CE->getOpcode() == Instruction::PtrToInt) {
 857         Constant *Op0 = CE->getOperand(0);
 858         if (GlobalValue *GV = dyn_cast<GlobalValue>(Op0)) {
 859           TargetLowering::AddrMode AM;
 860           AM.BaseGV = GV;
 861           AM.HasBaseReg = HasBaseReg;
 862           return TLI->isLegalAddressingMode(AM, UseTy);
 863         }
 864       }
 865   return false;
 866 }
 867
 868 /// MoveLoopVariantsToImmediateField - Move any subexpressions from Val that are
 869 /// loop varying to the Imm operand.
 870 static void MoveLoopVariantsToImmediateField(SCEVHandle &Val, SCEVHandle &Imm,
 871                                             Loop *L, ScalarEvolution *SE) {
 872   if (Val->isLoopInvariant(L)) return;  // Nothing to do.
 873
 874   if (SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) {
 875     std::vector<SCEVHandle> NewOps;
 876     NewOps.reserve(SAE->getNumOperands());
 877
 878     for (unsigned i = 0; i != SAE->getNumOperands(); ++i)
 879       if (!SAE->getOperand(i)->isLoopInvariant(L)) {
 880         // If this is a loop-variant expression, it must stay in the immediate
 881         // field of the expression.
 882         Imm = SE->getAddExpr(Imm, SAE->getOperand(i));
 883       } else {
 884         NewOps.push_back(SAE->getOperand(i));
 885       }
 886
 887     if (NewOps.empty())
 888       Val = SE->getIntegerSCEV(0, Val->getType());
 889     else
 890       Val = SE->getAddExpr(NewOps);
 891   } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) {
 892     // Try to pull immediates out of the start value of nested addrec's.
 893     SCEVHandle Start = SARE->getStart();
 894     MoveLoopVariantsToImmediateField(Start, Imm, L, SE);
 895
 896     std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
 897     Ops[0] = Start;
 898     Val = SE->getAddRecExpr(Ops, SARE->getLoop());
 899   } else {
 900     // Otherwise, all of Val is variant, move the whole thing over.
 901     Imm = SE->getAddExpr(Imm, Val);
 902     Val = SE->getIntegerSCEV(0, Val->getType());
 903   }
 904 }
 905
 906
 907 /// MoveImmediateValues - Look at Val, and pull out any additions of constants
 908 /// that can fit into the immediate field of instructions in the target.
 909 /// Accumulate these immediate values into the Imm value.
 910 static void MoveImmediateValues(const TargetLowering *TLI,
 911                                 Instruction *User,
 912                                 SCEVHandle &Val, SCEVHandle &Imm,
 913                                 bool isAddress, Loop *L,
 914                                 ScalarEvolution *SE) {
 915   const Type *UseTy = User->getType();
 916   if (StoreInst *SI = dyn_cast<StoreInst>(User))
 917     UseTy = SI->getOperand(0)->getType();
 918
 919   if (SCEVAddExpr *SAE = dyn_cast<SCEVAddExpr>(Val)) {
 920     std::vector<SCEVHandle> NewOps;
 921     NewOps.reserve(SAE->getNumOperands());
 922
 923     for (unsigned i = 0; i != SAE->getNumOperands(); ++i) {
 924       SCEVHandle NewOp = SAE->getOperand(i);
 925       MoveImmediateValues(TLI, User, NewOp, Imm, isAddress, L, SE);
 926
 927       if (!NewOp->isLoopInvariant(L)) {
 928         // If this is a loop-variant expression, it must stay in the immediate
 929         // field of the expression.
 930         Imm = SE->getAddExpr(Imm, NewOp);
 931       } else {
 932         NewOps.push_back(NewOp);
 933       }
 934     }
 935
 936     if (NewOps.empty())
 937       Val = SE->getIntegerSCEV(0, Val->getType());
 938     else
 939       Val = SE->getAddExpr(NewOps);
 940     return;
 941   } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Val)) {
 942     // Try to pull immediates out of the start value of nested addrec's.
 943     SCEVHandle Start = SARE->getStart();
 944     MoveImmediateValues(TLI, User, Start, Imm, isAddress, L, SE);
 945
 946     if (Start != SARE->getStart()) {
 947       std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
 948       Ops[0] = Start;
 949       Val = SE->getAddRecExpr(Ops, SARE->getLoop());
 950     }
 951     return;
 952   } else if (SCEVMulExpr *SME = dyn_cast<SCEVMulExpr>(Val)) {
 953     // Transform "8 * (4 + v)" -> "32 + 8*V" if "32" fits in the immed field.
 954     if (isAddress && fitsInAddressMode(SME->getOperand(0), UseTy, TLI, false) &&
 955         SME->getNumOperands() == 2 && SME->isLoopInvariant(L)) {
 956
 957       SCEVHandle SubImm = SE->getIntegerSCEV(0, Val->getType());
 958       SCEVHandle NewOp = SME->getOperand(1);
 959       MoveImmediateValues(TLI, User, NewOp, SubImm, isAddress, L, SE);
 960
 961       // If we extracted something out of the subexpressions, see if we can
 962       // simplify this!
 963       if (NewOp != SME->getOperand(1)) {
 964         // Scale SubImm up by "8".  If the result is a target constant, we are
 965         // good.
 966         SubImm = SE->getMulExpr(SubImm, SME->getOperand(0));
 967         if (fitsInAddressMode(SubImm, UseTy, TLI, false)) {
 968           // Accumulate the immediate.
 969           Imm = SE->getAddExpr(Imm, SubImm);
 970
 971           // Update what is left of 'Val'.
 972           Val = SE->getMulExpr(SME->getOperand(0), NewOp);
 973           return;
 974         }
 975       }
 976     }
 977   }
 978
 979   // Loop-variant expressions must stay in the immediate field of the
 980   // expression.
 981   if ((isAddress && fitsInAddressMode(Val, UseTy, TLI, false)) ||
 982       !Val->isLoopInvariant(L)) {
 983     Imm = SE->getAddExpr(Imm, Val);
 984     Val = SE->getIntegerSCEV(0, Val->getType());
 985     return;
 986   }
 987
 988   // Otherwise, no immediates to move.
 989 }
 990
 991
 992 /// SeparateSubExprs - Decompose Expr into all of the subexpressions that are
 993 /// added together.  This is used to reassociate common addition subexprs
 994 /// together for maximal sharing when rewriting bases.
 995 static void SeparateSubExprs(std::vector<SCEVHandle> &SubExprs,
 996                              SCEVHandle Expr,
 997                              ScalarEvolution *SE) {
 998   if (SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(Expr)) {
 999     for (unsigned j = 0, e = AE->getNumOperands(); j != e; ++j)
1000       SeparateSubExprs(SubExprs, AE->getOperand(j), SE);
1001   } else if (SCEVAddRecExpr *SARE = dyn_cast<SCEVAddRecExpr>(Expr)) {
1002     SCEVHandle Zero = SE->getIntegerSCEV(0, Expr->getType());
1003     if (SARE->getOperand(0) == Zero) {
1004       SubExprs.push_back(Expr);
1005     } else {
1006       // Compute the addrec with zero as its base.
1007       std::vector<SCEVHandle> Ops(SARE->op_begin(), SARE->op_end());
1008       Ops[0] = Zero;   // Start with zero base.
1009       SubExprs.push_back(SE->getAddRecExpr(Ops, SARE->getLoop()));
1010
1011
1012       SeparateSubExprs(SubExprs, SARE->getOperand(0), SE);
1013     }
1014   } else if (!Expr->isZero()) {
1015     // Do not add zero.
1016     SubExprs.push_back(Expr);
1017   }
1018 }
1019
1020 // This is logically local to the following function, but C++ says we have
1021 // to make it file scope.
1022 struct SubExprUseData { unsigned Count; bool notAllUsesAreFree; };
1023
1024 /// RemoveCommonExpressionsFromUseBases - Look through all of the Bases of all
1025 /// the Uses, removing any common subexpressions, except that if all such
1026 /// subexpressions can be folded into an addressing mode for all uses inside
1027 /// the loop (this case is referred to as "free" in comments herein) we do
1028 /// not remove anything.  This looks for things like (a+b+c) and
1029 /// (a+c+d) and computes the common (a+c) subexpression.  The common expression
1030 /// is *removed* from the Bases and returned.
1031 static SCEVHandle
1032 RemoveCommonExpressionsFromUseBases(std::vector<BasedUser> &Uses,
1033                                     ScalarEvolution *SE, Loop *L,
1034                                     const TargetLowering *TLI) {
1035   unsigned NumUses = Uses.size();
1036
1037   // Only one use?  This is a very common case, so we handle it specially and
1038   // cheaply.
1039   SCEVHandle Zero = SE->getIntegerSCEV(0, Uses[0].Base->getType());
1040   SCEVHandle Result = Zero;
1041   SCEVHandle FreeResult = Zero;
1042   if (NumUses == 1) {
1043     // If the use is inside the loop, use its base, regardless of what it is:
1044     // it is clearly shared across all the IV's.  If the use is outside the loop
1045     // (which means after it) we don't want to factor anything *into* the loop,
1046     // so just use 0 as the base.
1047     if (L->contains(Uses[0].Inst->getParent()))
1048       std::swap(Result, Uses[0].Base);
1049     return Result;
1050   }
1051
1052   // To find common subexpressions, count how many of Uses use each expression.
1053   // If any subexpressions are used Uses.size() times, they are common.
1054   // Also track whether all uses of each expression can be moved into an
1055   // an addressing mode "for free"; such expressions are left within the loop.
1056   // struct SubExprUseData { unsigned Count; bool notAllUsesAreFree; };
1057   std::map<SCEVHandle, SubExprUseData> SubExpressionUseData;
1058
1059   // UniqueSubExprs - Keep track of all of the subexpressions we see in the
1060   // order we see them.
1061   std::vector<SCEVHandle> UniqueSubExprs;
1062
1063   std::vector<SCEVHandle> SubExprs;
1064   unsigned NumUsesInsideLoop = 0;
1065   for (unsigned i = 0; i != NumUses; ++i) {
1066     // If the user is outside the loop, just ignore it for base computation.
1067     // Since the user is outside the loop, it must be *after* the loop (if it
1068     // were before, it could not be based on the loop IV).  We don't want users
1069     // after the loop to affect base computation of values *inside* the loop,
1070     // because we can always add their offsets to the result IV after the loop
1071     // is done, ensuring we get good code inside the loop.
1072     if (!L->contains(Uses[i].Inst->getParent()))
1073       continue;
1074     NumUsesInsideLoop++;
1075
1076     // If the base is zero (which is common), return zero now, there are no
1077     // CSEs we can find.
1078     if (Uses[i].Base == Zero) return Zero;
1079
1080     // If this use is as an address we may be able to put CSEs in the addressing
1081     // mode rather than hoisting them.
1082     bool isAddrUse = isAddressUse(Uses[i].Inst, Uses[i].OperandValToReplace);
1083     // We may need the UseTy below, but only when isAddrUse, so compute it
1084     // only in that case.
1085     const Type *UseTy = 0;
1086     if (isAddrUse) {
1087       UseTy  = Uses[i].Inst->getType();
1088       if (StoreInst *SI = dyn_cast<StoreInst>(Uses[i].Inst))
1089         UseTy = SI->getOperand(0)->getType();
1090     }
1091
1092     // Split the expression into subexprs.
1093     SeparateSubExprs(SubExprs, Uses[i].Base, SE);
1094     // Add one to SubExpressionUseData.Count for each subexpr present, and
1095     // if the subexpr is not a valid immediate within an addressing mode use,
1096     // set SubExpressionUseData.notAllUsesAreFree.  We definitely want to
1097     // hoist these out of the loop (if they are common to all uses).
1098     for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) {
1099       if (++SubExpressionUseData[SubExprs[j]].Count == 1)
1100         UniqueSubExprs.push_back(SubExprs[j]);
1101       if (!isAddrUse || !fitsInAddressMode(SubExprs[j], UseTy, TLI, false))
1102         SubExpressionUseData[SubExprs[j]].notAllUsesAreFree = true;
1103     }
1104     SubExprs.clear();
1105   }
1106
1107   // Now that we know how many times each is used, build Result.  Iterate over
1108   // UniqueSubexprs so that we have a stable ordering.
1109   for (unsigned i = 0, e = UniqueSubExprs.size(); i != e; ++i) {
1110     std::map<SCEVHandle, SubExprUseData>::iterator I =
1111        SubExpressionUseData.find(UniqueSubExprs[i]);
1112     assert(I != SubExpressionUseData.end() && "Entry not found?");
1113     if (I->second.Count == NumUsesInsideLoop) { // Found CSE!
1114       if (I->second.notAllUsesAreFree)
1115         Result = SE->getAddExpr(Result, I->first);
1116       else
1117         FreeResult = SE->getAddExpr(FreeResult, I->first);
1118     } else
1119       // Remove non-cse's from SubExpressionUseData.
1120       SubExpressionUseData.erase(I);
1121   }
1122
1123   if (FreeResult != Zero) {
1124     // We have some subexpressions that can be subsumed into addressing
1125     // modes in every use inside the loop.  However, it's possible that
1126     // there are so many of them that the combined FreeResult cannot
1127     // be subsumed, or that the target cannot handle both a FreeResult
1128     // and a Result in the same instruction (for example because it would
1129     // require too many registers).  Check this.
1130     for (unsigned i=0; i<NumUses; ++i) {
1131       if (!L->contains(Uses[i].Inst->getParent()))
1132         continue;
1133       // We know this is an addressing mode use; if there are any uses that
1134       // are not, FreeResult would be Zero.
1135       const Type *UseTy = Uses[i].Inst->getType();
1136       if (StoreInst *SI = dyn_cast<StoreInst>(Uses[i].Inst))
1137         UseTy = SI->getOperand(0)->getType();
1138       if (!fitsInAddressMode(FreeResult, UseTy, TLI, Result!=Zero)) {
1139         // FIXME:  could split up FreeResult into pieces here, some hoisted
1140         // and some not.  There is no obvious advantage to this.
1141         Result = SE->getAddExpr(Result, FreeResult);
1142         FreeResult = Zero;
1143         break;
1144       }
1145     }
1146   }
1147
1148   // If we found no CSE's, return now.
1149   if (Result == Zero) return Result;
1150
1151   // If we still have a FreeResult, remove its subexpressions from
1152   // SubExpressionUseData.  This means they will remain in the use Bases.
1153   if (FreeResult != Zero) {
1154     SeparateSubExprs(SubExprs, FreeResult, SE);
1155     for (unsigned j = 0, e = SubExprs.size(); j != e; ++j) {
1156       std::map<SCEVHandle, SubExprUseData>::iterator I =
1157          SubExpressionUseData.find(SubExprs[j]);
1158       SubExpressionUseData.erase(I);
1159     }
1160     SubExprs.clear();
1161   }
1162
1163   // Otherwise, remove all of the CSE's we found from each of the base values.
1164   for (unsigned i = 0; i != NumUses; ++i) {
1165     // Uses outside the loop don't necessarily include the common base, but
1166     // the final IV value coming into those uses does.  Instead of trying to
1167     // remove the pieces of the common base, which might not be there,
1168     // subtract off the base to compensate for this.
1169     if (!L->contains(Uses[i].Inst->getParent())) {
1170       Uses[i].Base = SE->getMinusSCEV(Uses[i].Base, Result);
1171       continue;
1172     }
1173
1174     // Split the expression into subexprs.
1175     SeparateSubExprs(SubExprs, Uses[i].Base, SE);
1176
1177     // Remove any common subexpressions.
1178     for (unsigned j = 0, e = SubExprs.size(); j != e; ++j)
1179       if (SubExpressionUseData.count(SubExprs[j])) {
1180         SubExprs.erase(SubExprs.begin()+j);
1181         --j; --e;
1182       }
1183
1184     // Finally, add the non-shared expressions together.
1185     if (SubExprs.empty())
1186       Uses[i].Base = Zero;
1187     else
1188       Uses[i].Base = SE->getAddExpr(SubExprs);
1189     SubExprs.clear();
1190   }
1191
1192   return Result;
1193 }
1194
1195 /// ValidStride - Check whether the given Scale is valid for all loads and
1196 /// stores in UsersToProcess.
1197 ///
1198 bool LoopStrengthReduce::ValidStride(bool HasBaseReg,
1199                                int64_t Scale,
1200                                const std::vector<BasedUser>& UsersToProcess) {
1201   if (!TLI)
1202     return true;
1203
1204   for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
1205     // If this is a load or other access, pass the type of the access in.
1206     const Type *AccessTy = Type::VoidTy;
1207     if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst))
1208       AccessTy = SI->getOperand(0)->getType();
1209     else if (LoadInst *LI = dyn_cast<LoadInst>(UsersToProcess[i].Inst))
1210       AccessTy = LI->getType();
1211     else if (isa<PHINode>(UsersToProcess[i].Inst))
1212       continue;
1213
1214     TargetLowering::AddrMode AM;
1215     if (SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm))
1216       AM.BaseOffs = SC->getValue()->getSExtValue();
1217     AM.HasBaseReg = HasBaseReg || !UsersToProcess[i].Base->isZero();
1218     AM.Scale = Scale;
1219
1220     // If load[imm+r*scale] is illegal, bail out.
1221     if (!TLI->isLegalAddressingMode(AM, AccessTy))
1222       return false;
1223   }
1224   return true;
1225 }
1226
1227 /// RequiresTypeConversion - Returns true if converting Ty1 to Ty2 is not
1228 /// a nop.
1229 bool LoopStrengthReduce::RequiresTypeConversion(const Type *Ty1,
1230                                                 const Type *Ty2) {
1231   if (Ty1 == Ty2)
1232     return false;
1233   if (Ty1->canLosslesslyBitCastTo(Ty2))
1234     return false;
1235   if (TLI && TLI->isTruncateFree(Ty1, Ty2))
1236     return false;
1237   if (isa<PointerType>(Ty2) && Ty1->canLosslesslyBitCastTo(UIntPtrTy))
1238     return false;
1239   if (isa<PointerType>(Ty1) && Ty2->canLosslesslyBitCastTo(UIntPtrTy))
1240     return false;
1241   return true;
1242 }
1243
1244 /// CheckForIVReuse - Returns the multiple if the stride is the multiple
1245 /// of a previous stride and it is a legal value for the target addressing
1246 /// mode scale component and optional base reg. This allows the users of
1247 /// this stride to be rewritten as prev iv * factor. It returns 0 if no
1248 /// reuse is possible.  Factors can be negative on same targets, e.g. ARM.
1249 ///
1250 /// If all uses are outside the loop, we don't require that all multiplies
1251 /// be folded into the addressing mode, nor even that the factor be constant;
1252 /// a multiply (executed once) outside the loop is better than another IV
1253 /// within.  Well, usually.
1254 SCEVHandle LoopStrengthReduce::CheckForIVReuse(bool HasBaseReg,
1255                                 bool AllUsesAreAddresses,
1256                                 bool AllUsesAreOutsideLoop,
1257                                 const SCEVHandle &Stride,
1258                                 IVExpr &IV, const Type *Ty,
1259                                 const std::vector<BasedUser>& UsersToProcess) {
1260   if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) {
1261     int64_t SInt = SC->getValue()->getSExtValue();
1262     for (unsigned NewStride = 0, e = StrideOrder.size(); NewStride != e;
1263          ++NewStride) {
1264       std::map<SCEVHandle, IVsOfOneStride>::iterator SI =
1265                 IVsByStride.find(StrideOrder[NewStride]);
1266       if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first))
1267         continue;
1268       int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
1269       if (SI->first != Stride &&
1270           (unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0))
1271         continue;
1272       int64_t Scale = SInt / SSInt;
1273       // Check that this stride is valid for all the types used for loads and
1274       // stores; if it can be used for some and not others, we might as well use
1275       // the original stride everywhere, since we have to create the IV for it
1276       // anyway. If the scale is 1, then we don't need to worry about folding
1277       // multiplications.
1278       if (Scale == 1 ||
1279           (AllUsesAreAddresses &&
1280            ValidStride(HasBaseReg, Scale, UsersToProcess)))
1281         for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(),
1282                IE = SI->second.IVs.end(); II != IE; ++II)
1283           // FIXME: Only handle base == 0 for now.
1284           // Only reuse previous IV if it would not require a type conversion.
1285           if (II->Base->isZero() &&
1286               !RequiresTypeConversion(II->Base->getType(), Ty)) {
1287             IV = *II;
1288             return SE->getIntegerSCEV(Scale, Stride->getType());
1289           }
1290     }
1291   } else if (AllUsesAreOutsideLoop) {
1292     // Accept nonconstant strides here; it is really really right to substitute
1293     // an existing IV if we can.
1294     for (unsigned NewStride = 0, e = StrideOrder.size(); NewStride != e;
1295          ++NewStride) {
1296       std::map<SCEVHandle, IVsOfOneStride>::iterator SI =
1297                 IVsByStride.find(StrideOrder[NewStride]);
1298       if (SI == IVsByStride.end() || !isa<SCEVConstant>(SI->first))
1299         continue;
1300       int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
1301       if (SI->first != Stride && SSInt != 1)
1302         continue;
1303       for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(),
1304              IE = SI->second.IVs.end(); II != IE; ++II)
1305         // Accept nonzero base here.
1306         // Only reuse previous IV if it would not require a type conversion.
1307         if (!RequiresTypeConversion(II->Base->getType(), Ty)) {
1308           IV = *II;
1309           return Stride;
1310         }
1311     }
1312     // Special case, old IV is -1*x and this one is x.  Can treat this one as
1313     // -1*old.
1314     for (unsigned NewStride = 0, e = StrideOrder.size(); NewStride != e;
1315          ++NewStride) {
1316       std::map<SCEVHandle, IVsOfOneStride>::iterator SI =
1317                 IVsByStride.find(StrideOrder[NewStride]);
1318       if (SI == IVsByStride.end())
1319         continue;
1320       if (SCEVMulExpr *ME = dyn_cast<SCEVMulExpr>(SI->first))
1321         if (SCEVConstant *SC = dyn_cast<SCEVConstant>(ME->getOperand(0)))
1322           if (Stride == ME->getOperand(1) &&
1323               SC->getValue()->getSExtValue() == -1LL)
1324             for (std::vector<IVExpr>::iterator II = SI->second.IVs.begin(),
1325                    IE = SI->second.IVs.end(); II != IE; ++II)
1326               // Accept nonzero base here.
1327               // Only reuse previous IV if it would not require type conversion.
1328               if (!RequiresTypeConversion(II->Base->getType(), Ty)) {
1329                 IV = *II;
1330                 return SE->getIntegerSCEV(-1LL, Stride->getType());
1331               }
1332     }
1333   }
1334   return SE->getIntegerSCEV(0, Stride->getType());
1335 }
1336
1337 /// PartitionByIsUseOfPostIncrementedValue - Simple boolean predicate that
1338 /// returns true if Val's isUseOfPostIncrementedValue is true.
1339 static bool PartitionByIsUseOfPostIncrementedValue(const BasedUser &Val) {
1340   return Val.isUseOfPostIncrementedValue;
1341 }
1342
1343 /// isNonConstantNegative - Return true if the specified scev is negated, but
1344 /// not a constant.
1345 static bool isNonConstantNegative(const SCEVHandle &Expr) {
1346   SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Expr);
1347   if (!Mul) return false;
1348
1349   // If there is a constant factor, it will be first.
1350   SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
1351   if (!SC) return false;
1352
1353   // Return true if the value is negative, this matches things like (-42 * V).
1354   return SC->getValue()->getValue().isNegative();
1355 }
1356
1357 // CollectIVUsers - Transform our list of users and offsets to a bit more
1358 // complex table. In this new vector, each 'BasedUser' contains 'Base', the base
1359 // of the strided accesses, as well as the old information from Uses. We
1360 // progressively move information from the Base field to the Imm field, until
1361 // we eventually have the full access expression to rewrite the use.
1362 SCEVHandle LoopStrengthReduce::CollectIVUsers(const SCEVHandle &Stride,
1363                                               IVUsersOfOneStride &Uses,
1364                                               Loop *L,
1365                                               bool &AllUsesAreAddresses,
1366                                               bool &AllUsesAreOutsideLoop,
1367                                        std::vector<BasedUser> &UsersToProcess) {
1368   UsersToProcess.reserve(Uses.Users.size());
1369   for (unsigned i = 0, e = Uses.Users.size(); i != e; ++i) {
1370     UsersToProcess.push_back(BasedUser(Uses.Users[i], SE));
1371
1372     // Move any loop variant operands from the offset field to the immediate
1373     // field of the use, so that we don't try to use something before it is
1374     // computed.
1375     MoveLoopVariantsToImmediateField(UsersToProcess.back().Base,
1376                                     UsersToProcess.back().Imm, L, SE);
1377     assert(UsersToProcess.back().Base->isLoopInvariant(L) &&
1378            "Base value is not loop invariant!");
1379   }
1380
1381   // We now have a whole bunch of uses of like-strided induction variables, but
1382   // they might all have different bases.  We want to emit one PHI node for this
1383   // stride which we fold as many common expressions (between the IVs) into as
1384   // possible.  Start by identifying the common expressions in the base values
1385   // for the strides (e.g. if we have "A+C+B" and "A+B+D" as our bases, find
1386   // "A+B"), emit it to the preheader, then remove the expression from the
1387   // UsersToProcess base values.
1388   SCEVHandle CommonExprs =
1389     RemoveCommonExpressionsFromUseBases(UsersToProcess, SE, L, TLI);
1390
1391   // Next, figure out what we can represent in the immediate fields of
1392   // instructions.  If we can represent anything there, move it to the imm
1393   // fields of the BasedUsers.  We do this so that it increases the commonality
1394   // of the remaining uses.
1395   unsigned NumPHI = 0;
1396   for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
1397     // If the user is not in the current loop, this means it is using the exit
1398     // value of the IV.  Do not put anything in the base, make sure it's all in
1399     // the immediate field to allow as much factoring as possible.
1400     if (!L->contains(UsersToProcess[i].Inst->getParent())) {
1401       UsersToProcess[i].Imm = SE->getAddExpr(UsersToProcess[i].Imm,
1402                                              UsersToProcess[i].Base);
1403       UsersToProcess[i].Base =
1404         SE->getIntegerSCEV(0, UsersToProcess[i].Base->getType());
1405     } else {
1406
1407       // Addressing modes can be folded into loads and stores.  Be careful that
1408       // the store is through the expression, not of the expression though.
1409       bool isPHI = false;
1410       bool isAddress = isAddressUse(UsersToProcess[i].Inst,
1411                                     UsersToProcess[i].OperandValToReplace);
1412       if (isa<PHINode>(UsersToProcess[i].Inst)) {
1413         isPHI = true;
1414         ++NumPHI;
1415       }
1416
1417       // Not all uses are outside the loop.
1418       AllUsesAreOutsideLoop = false;
1419
1420       // If this use isn't an address, then not all uses are addresses.
1421       if (!isAddress && !isPHI)
1422         AllUsesAreAddresses = false;
1423
1424       MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base,
1425                           UsersToProcess[i].Imm, isAddress, L, SE);
1426     }
1427   }
1428
1429   // If one of the use if a PHI node and all other uses are addresses, still
1430   // allow iv reuse. Essentially we are trading one constant multiplication
1431   // for one fewer iv.
1432   if (NumPHI > 1)
1433     AllUsesAreAddresses = false;
1434
1435   return CommonExprs;
1436 }
1437
1438 /// StrengthReduceStridedIVUsers - Strength reduce all of the users of a single
1439 /// stride of IV.  All of the users may have different starting values, and this
1440 /// may not be the only stride (we know it is if isOnlyStride is true).
1441 void LoopStrengthReduce::StrengthReduceStridedIVUsers(const SCEVHandle &Stride,
1442                                                       IVUsersOfOneStride &Uses,
1443                                                       Loop *L,
1444                                                       bool isOnlyStride) {
1445   // If all the users are moved to another stride, then there is nothing to do.
1446   if (Uses.Users.empty())
1447     return;
1448
1449   // Keep track if every use in UsersToProcess is an address. If they all are,
1450   // we may be able to rewrite the entire collection of them in terms of a
1451   // smaller-stride IV.
1452   bool AllUsesAreAddresses = true;
1453
1454   // Keep track if every use of a single stride is outside the loop.  If so,
1455   // we want to be more aggressive about reusing a smaller-stride IV; a
1456   // multiply outside the loop is better than another IV inside.  Well, usually.
1457   bool AllUsesAreOutsideLoop = true;
1458
1459   // Transform our list of users and offsets to a bit more complex table.  In
1460   // this new vector, each 'BasedUser' contains 'Base' the base of the
1461   // strided accessas well as the old information from Uses.  We progressively
1462   // move information from the Base field to the Imm field, until we eventually
1463   // have the full access expression to rewrite the use.
1464   std::vector<BasedUser> UsersToProcess;
1465   SCEVHandle CommonExprs = CollectIVUsers(Stride, Uses, L, AllUsesAreAddresses,
1466                                           AllUsesAreOutsideLoop,
1467                                           UsersToProcess);
1468
1469   // If we managed to find some expressions in common, we'll need to carry
1470   // their value in a register and add it in for each use. This will take up
1471   // a register operand, which potentially restricts what stride values are
1472   // valid.
1473   bool HaveCommonExprs = !CommonExprs->isZero();
1474
1475   // If all uses are addresses, check if it is possible to reuse an IV with a
1476   // stride that is a factor of this stride. And that the multiple is a number
1477   // that can be encoded in the scale field of the target addressing mode. And
1478   // that we will have a valid instruction after this substition, including the
1479   // immediate field, if any.
1480   PHINode *NewPHI = NULL;
1481   Value   *IncV   = NULL;
1482   IVExpr   ReuseIV(SE->getIntegerSCEV(0, Type::Int32Ty),
1483                    SE->getIntegerSCEV(0, Type::Int32Ty),
1484                    0, 0);
1485   SCEVHandle RewriteFactor =
1486                   CheckForIVReuse(HaveCommonExprs, AllUsesAreAddresses,
1487                                   AllUsesAreOutsideLoop,
1488                                   Stride, ReuseIV, CommonExprs->getType(),
1489                                   UsersToProcess);
1490   if (!isa<SCEVConstant>(RewriteFactor) ||
1491       !cast<SCEVConstant>(RewriteFactor)->isZero()) {
1492     DOUT << "BASED ON IV of STRIDE " << *ReuseIV.Stride
1493          << " and BASE " << *ReuseIV.Base << " :\n";
1494     NewPHI = ReuseIV.PHI;
1495     IncV   = ReuseIV.IncV;
1496   }
1497
1498   const Type *ReplacedTy = CommonExprs->getType();
1499
1500   // Now that we know what we need to do, insert the PHI node itself.
1501   //
1502   DOUT << "INSERTING IV of TYPE " << *ReplacedTy << " of STRIDE "
1503        << *Stride << " and BASE " << *CommonExprs << ": ";
1504
1505   SCEVExpander Rewriter(*SE, *LI);
1506   SCEVExpander PreheaderRewriter(*SE, *LI);
1507
1508   BasicBlock  *Preheader = L->getLoopPreheader();
1509   Instruction *PreInsertPt = Preheader->getTerminator();
1510   Instruction *PhiInsertBefore = L->getHeader()->begin();
1511
1512   BasicBlock *LatchBlock = L->getLoopLatch();
1513
1514
1515   // Emit the initial base value into the loop preheader.
1516   Value *CommonBaseV
1517     = PreheaderRewriter.expandCodeFor(CommonExprs, PreInsertPt);
1518
1519   if (isa<SCEVConstant>(RewriteFactor) &&
1520       cast<SCEVConstant>(RewriteFactor)->isZero()) {
1521     // Create a new Phi for this base, and stick it in the loop header.
1522     NewPHI = PHINode::Create(ReplacedTy, "iv.", PhiInsertBefore);
1523     ++NumInserted;
1524
1525     // Add common base to the new Phi node.
1526     NewPHI->addIncoming(CommonBaseV, Preheader);
1527
1528     // If the stride is negative, insert a sub instead of an add for the
1529     // increment.
1530     bool isNegative = isNonConstantNegative(Stride);
1531     SCEVHandle IncAmount = Stride;
1532     if (isNegative)
1533       IncAmount = SE->getNegativeSCEV(Stride);
1534
1535     // Insert the stride into the preheader.
1536     Value *StrideV = PreheaderRewriter.expandCodeFor(IncAmount, PreInsertPt);
1537     if (!isa<ConstantInt>(StrideV)) ++NumVariable;
1538
1539     // Emit the increment of the base value before the terminator of the loop
1540     // latch block, and add it to the Phi node.
1541     SCEVHandle IncExp = SE->getUnknown(StrideV);
1542     if (isNegative)
1543       IncExp = SE->getNegativeSCEV(IncExp);
1544     IncExp = SE->getAddExpr(SE->getUnknown(NewPHI), IncExp);
1545
1546     IncV = Rewriter.expandCodeFor(IncExp, LatchBlock->getTerminator());
1547     IncV->setName(NewPHI->getName()+".inc");
1548     NewPHI->addIncoming(IncV, LatchBlock);
1549
1550     // Remember this in case a later stride is multiple of this.
1551     IVsByStride[Stride].addIV(Stride, CommonExprs, NewPHI, IncV);
1552
1553     DOUT << " IV=%" << NewPHI->getNameStr() << " INC=%" << IncV->getNameStr();
1554   } else {
1555     Constant *C = dyn_cast<Constant>(CommonBaseV);
1556     if (!C ||
1557         (!C->isNullValue() &&
1558          !fitsInAddressMode(SE->getUnknown(CommonBaseV), ReplacedTy,
1559                            TLI, false)))
1560       // We want the common base emitted into the preheader! This is just
1561       // using cast as a copy so BitCast (no-op cast) is appropriate
1562       CommonBaseV = new BitCastInst(CommonBaseV, CommonBaseV->getType(),
1563                                     "commonbase", PreInsertPt);
1564   }
1565   DOUT << "\n";
1566
1567   // We want to emit code for users inside the loop first.  To do this, we
1568   // rearrange BasedUser so that the entries at the end have
1569   // isUseOfPostIncrementedValue = false, because we pop off the end of the
1570   // vector (so we handle them first).
1571   std::partition(UsersToProcess.begin(), UsersToProcess.end(),
1572                  PartitionByIsUseOfPostIncrementedValue);
1573
1574   // Sort this by base, so that things with the same base are handled
1575   // together.  By partitioning first and stable-sorting later, we are
1576   // guaranteed that within each base we will pop off users from within the
1577   // loop before users outside of the loop with a particular base.
1578   //
1579   // We would like to use stable_sort here, but we can't.  The problem is that
1580   // SCEVHandle's don't have a deterministic ordering w.r.t to each other, so
1581   // we don't have anything to do a '<' comparison on.  Because we think the
1582   // number of uses is small, do a horrible bubble sort which just relies on
1583   // ==.
1584   for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
1585     // Get a base value.
1586     SCEVHandle Base = UsersToProcess[i].Base;
1587
1588     // Compact everything with this base to be consecutive with this one.
1589     for (unsigned j = i+1; j != e; ++j) {
1590       if (UsersToProcess[j].Base == Base) {
1591         std::swap(UsersToProcess[i+1], UsersToProcess[j]);
1592         ++i;
1593       }
1594     }
1595   }
1596
1597   // Process all the users now.  This outer loop handles all bases, the inner
1598   // loop handles all users of a particular base.
1599   while (!UsersToProcess.empty()) {
1600     SCEVHandle Base = UsersToProcess.back().Base;
1601
1602     // Emit the code for Base into the preheader.
1603     Value *BaseV = PreheaderRewriter.expandCodeFor(Base, PreInsertPt);
1604
1605     DOUT << "  INSERTING code for BASE = " << *Base << ":";
1606     if (BaseV->hasName())
1607       DOUT << " Result value name = %" << BaseV->getNameStr();
1608     DOUT << "\n";
1609
1610     // If BaseV is a constant other than 0, make sure that it gets inserted into
1611     // the preheader, instead of being forward substituted into the uses.  We do
1612     // this by forcing a BitCast (noop cast) to be inserted into the preheader
1613     // in this case.
1614     if (Constant *C = dyn_cast<Constant>(BaseV)) {
1615       if (!C->isNullValue() && !fitsInAddressMode(Base, ReplacedTy,
1616                                                  TLI, false)) {
1617         // We want this constant emitted into the preheader! This is just
1618         // using cast as a copy so BitCast (no-op cast) is appropriate
1619         BaseV = new BitCastInst(BaseV, BaseV->getType(), "preheaderinsert",
1620                                 PreInsertPt);
1621       }
1622     }
1623
1624     // Emit the code to add the immediate offset to the Phi value, just before
1625     // the instructions that we identified as using this stride and base.
1626     do {
1627       // FIXME: Use emitted users to emit other users.
1628       BasedUser &User = UsersToProcess.back();
1629
1630       // If this instruction wants to use the post-incremented value, move it
1631       // after the post-inc and use its value instead of the PHI.
1632       Value *RewriteOp = NewPHI;
1633       if (User.isUseOfPostIncrementedValue) {
1634         RewriteOp = IncV;
1635
1636         // If this user is in the loop, make sure it is the last thing in the
1637         // loop to ensure it is dominated by the increment.
1638         if (L->contains(User.Inst->getParent()))
1639           User.Inst->moveBefore(LatchBlock->getTerminator());
1640       }
1641       if (RewriteOp->getType() != ReplacedTy) {
1642         Instruction::CastOps opcode = Instruction::Trunc;
1643         if (ReplacedTy->getPrimitiveSizeInBits() ==
1644             RewriteOp->getType()->getPrimitiveSizeInBits())
1645           opcode = Instruction::BitCast;
1646         RewriteOp = SCEVExpander::InsertCastOfTo(opcode, RewriteOp, ReplacedTy);
1647       }
1648
1649       SCEVHandle RewriteExpr = SE->getUnknown(RewriteOp);
1650
1651       // If we had to insert new instructions for RewriteOp, we have to
1652       // consider that they may not have been able to end up immediately
1653       // next to RewriteOp, because non-PHI instructions may never precede
1654       // PHI instructions in a block. In this case, remember where the last
1655       // instruction was inserted so that if we're replacing a different
1656       // PHI node, we can use the later point to expand the final
1657       // RewriteExpr.
1658       Instruction *NewBasePt = dyn_cast<Instruction>(RewriteOp);
1659       if (RewriteOp == NewPHI) NewBasePt = 0;
1660
1661       // Clear the SCEVExpander's expression map so that we are guaranteed
1662       // to have the code emitted where we expect it.
1663       Rewriter.clear();
1664
1665       // If we are reusing the iv, then it must be multiplied by a constant
1666       // factor to take advantage of the addressing mode scale component.
1667       if (!isa<SCEVConstant>(RewriteFactor) ||
1668           !cast<SCEVConstant>(RewriteFactor)->isZero()) {
1669         // If we're reusing an IV with a nonzero base (currently this happens
1670         // only when all reuses are outside the loop) subtract that base here.
1671         // The base has been used to initialize the PHI node but we don't want
1672         // it here.
1673         if (!ReuseIV.Base->isZero()) {
1674           SCEVHandle typedBase = ReuseIV.Base;
1675           if (RewriteExpr->getType()->getPrimitiveSizeInBits() !=
1676               ReuseIV.Base->getType()->getPrimitiveSizeInBits()) {
1677             // It's possible the original IV is a larger type than the new IV,
1678             // in which case we have to truncate the Base.  We checked in
1679             // RequiresTypeConversion that this is valid.
1680             assert (RewriteExpr->getType()->getPrimitiveSizeInBits() <
1681                     ReuseIV.Base->getType()->getPrimitiveSizeInBits() &&
1682                     "Unexpected lengthening conversion!");
1683             typedBase = SE->getTruncateExpr(ReuseIV.Base,
1684                                             RewriteExpr->getType());
1685           }
1686           RewriteExpr = SE->getMinusSCEV(RewriteExpr, typedBase);
1687         }
1688
1689         // Multiply old variable, with base removed, by new scale factor.
1690         RewriteExpr = SE->getMulExpr(RewriteFactor,
1691                                      RewriteExpr);
1692
1693         // The common base is emitted in the loop preheader. But since we
1694         // are reusing an IV, it has not been used to initialize the PHI node.
1695         // Add it to the expression used to rewrite the uses.
1696         // When this use is outside the loop, we earlier subtracted the
1697         // common base, and are adding it back here.  Use the same expression
1698         // as before, rather than CommonBaseV, so DAGCombiner will zap it.
1699         if (!isa<ConstantInt>(CommonBaseV) ||
1700             !cast<ConstantInt>(CommonBaseV)->isZero()) {
1701           if (L->contains(User.Inst->getParent()))
1702             RewriteExpr = SE->getAddExpr(RewriteExpr,
1703                                        SE->getUnknown(CommonBaseV));
1704           else
1705             RewriteExpr = SE->getAddExpr(RewriteExpr, CommonExprs);
1706         }
1707       }
1708
1709       // Now that we know what we need to do, insert code before User for the
1710       // immediate and any loop-variant expressions.
1711       if (!isa<ConstantInt>(BaseV) || !cast<ConstantInt>(BaseV)->isZero())
1712         // Add BaseV to the PHI value if needed.
1713         RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV));
1714
1715       User.RewriteInstructionToUseNewBase(RewriteExpr, NewBasePt,
1716                                           Rewriter, L, this,
1717                                           DeadInsts);
1718
1719       // Mark old value we replaced as possibly dead, so that it is eliminated
1720       // if we just replaced the last use of that value.
1721       DeadInsts.push_back(cast<Instruction>(User.OperandValToReplace));
1722
1723       UsersToProcess.pop_back();
1724       ++NumReduced;
1725
1726       // If there are any more users to process with the same base, process them
1727       // now.  We sorted by base above, so we just have to check the last elt.
1728     } while (!UsersToProcess.empty() && UsersToProcess.back().Base == Base);
1729     // TODO: Next, find out which base index is the most common, pull it out.
1730   }
1731
1732   // IMPORTANT TODO: Figure out how to partition the IV's with this stride, but
1733   // different starting values, into different PHIs.
1734 }
1735
1736 /// FindIVUserForCond - If Cond has an operand that is an expression of an IV,
1737 /// set the IV user and stride information and return true, otherwise return
1738 /// false.
1739 bool LoopStrengthReduce::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
1740                                        const SCEVHandle *&CondStride) {
1741   for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e && !CondUse;
1742        ++Stride) {
1743     std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
1744     IVUsesByStride.find(StrideOrder[Stride]);
1745     assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
1746
1747     for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
1748          E = SI->second.Users.end(); UI != E; ++UI)
1749       if (UI->User == Cond) {
1750         // NOTE: we could handle setcc instructions with multiple uses here, but
1751         // InstCombine does it as well for simple uses, it's not clear that it
1752         // occurs enough in real life to handle.
1753         CondUse = &*UI;
1754         CondStride = &SI->first;
1755         return true;
1756       }
1757   }
1758   return false;
1759 }
1760
1761 namespace {
1762   // Constant strides come first which in turns are sorted by their absolute
1763   // values. If absolute values are the same, then positive strides comes first.
1764   // e.g.
1765   // 4, -1, X, 1, 2 ==> 1, -1, 2, 4, X
1766   struct StrideCompare {
1767     bool operator()(const SCEVHandle &LHS, const SCEVHandle &RHS) {
1768       SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS);
1769       SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS);
1770       if (LHSC && RHSC) {
1771         int64_t  LV = LHSC->getValue()->getSExtValue();
1772         int64_t  RV = RHSC->getValue()->getSExtValue();
1773         uint64_t ALV = (LV < 0) ? -LV : LV;
1774         uint64_t ARV = (RV < 0) ? -RV : RV;
1775         if (ALV == ARV)
1776           return LV > RV;
1777         else
1778           return ALV < ARV;
1779       }
1780       return (LHSC && !RHSC);
1781     }
1782   };
1783 }
1784
1785 /// ChangeCompareStride - If a loop termination compare instruction is the
1786 /// only use of its stride, and the compaison is against a constant value,
1787 /// try eliminate the stride by moving the compare instruction to another
1788 /// stride and change its constant operand accordingly. e.g.
1789 ///
1790 /// loop:
1791 /// ...
1792 /// v1 = v1 + 3
1793 /// v2 = v2 + 1
1794 /// if (v2 < 10) goto loop
1795 /// =>
1796 /// loop:
1797 /// ...
1798 /// v1 = v1 + 3
1799 /// if (v1 < 30) goto loop
1800 ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond,
1801                                                 IVStrideUse* &CondUse,
1802                                                 const SCEVHandle* &CondStride) {
1803   if (StrideOrder.size() < 2 ||
1804       IVUsesByStride[*CondStride].Users.size() != 1)
1805     return Cond;
1806   const SCEVConstant *SC = dyn_cast<SCEVConstant>(*CondStride);
1807   if (!SC) return Cond;
1808   ConstantInt *C = dyn_cast<ConstantInt>(Cond->getOperand(1));
1809   if (!C) return Cond;
1810
1811   ICmpInst::Predicate Predicate = Cond->getPredicate();
1812   int64_t CmpSSInt = SC->getValue()->getSExtValue();
1813   int64_t CmpVal = C->getValue().getSExtValue();
1814   unsigned BitWidth = C->getValue().getBitWidth();
1815   uint64_t SignBit = 1ULL << (BitWidth-1);
1816   const Type *CmpTy = C->getType();
1817   const Type *NewCmpTy = NULL;
1818   unsigned TyBits = CmpTy->getPrimitiveSizeInBits();
1819   unsigned NewTyBits = 0;
1820   int64_t NewCmpVal = CmpVal;
1821   SCEVHandle *NewStride = NULL;
1822   Value *NewIncV = NULL;
1823   int64_t Scale = 1;
1824
1825   // Check stride constant and the comparision constant signs to detect
1826   // overflow.
1827   if ((CmpVal & SignBit) != (CmpSSInt & SignBit))
1828     return Cond;
1829
1830   // Look for a suitable stride / iv as replacement.
1831   std::stable_sort(StrideOrder.begin(), StrideOrder.end(), StrideCompare());
1832   for (unsigned i = 0, e = StrideOrder.size(); i != e; ++i) {
1833     std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
1834       IVUsesByStride.find(StrideOrder[i]);
1835     if (!isa<SCEVConstant>(SI->first))
1836       continue;
1837     int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
1838     if (abs(SSInt) <= abs(CmpSSInt) || (SSInt % CmpSSInt) != 0)
1839       continue;
1840
1841     Scale = SSInt / CmpSSInt;
1842     NewCmpVal = CmpVal * Scale;
1843     APInt Mul = APInt(BitWidth, NewCmpVal);
1844     // Check for overflow.
1845     if (Mul.getSExtValue() != NewCmpVal) {
1846       NewCmpVal = CmpVal;
1847       continue;
1848     }
1849
1850     // Watch out for overflow.
1851     if (ICmpInst::isSignedPredicate(Predicate) &&
1852         (CmpVal & SignBit) != (NewCmpVal & SignBit))
1853       NewCmpVal = CmpVal;
1854
1855     if (NewCmpVal != CmpVal) {
1856       // Pick the best iv to use trying to avoid a cast.
1857       NewIncV = NULL;
1858       for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
1859              E = SI->second.Users.end(); UI != E; ++UI) {
1860         NewIncV = UI->OperandValToReplace;
1861         if (NewIncV->getType() == CmpTy)
1862           break;
1863       }
1864       if (!NewIncV) {
1865         NewCmpVal = CmpVal;
1866         continue;
1867       }
1868
1869       NewCmpTy = NewIncV->getType();
1870       NewTyBits = isa<PointerType>(NewCmpTy)
1871         ? UIntPtrTy->getPrimitiveSizeInBits()
1872         : NewCmpTy->getPrimitiveSizeInBits();
1873       if (RequiresTypeConversion(NewCmpTy, CmpTy)) {
1874         // Check if it is possible to rewrite it using
1875         // an iv / stride of a smaller integer type.
1876         bool TruncOk = false;
1877         if (NewCmpTy->isInteger()) {
1878           unsigned Bits = NewTyBits;
1879           if (ICmpInst::isSignedPredicate(Predicate))
1880             --Bits;
1881           uint64_t Mask = (1ULL << Bits) - 1;
1882           if (((uint64_t)NewCmpVal & Mask) == (uint64_t)NewCmpVal)
1883             TruncOk = true;
1884         }
1885         if (!TruncOk) {
1886           NewCmpVal = CmpVal;
1887           continue;
1888         }
1889       }
1890
1891       // Don't rewrite if use offset is non-constant and the new type is
1892       // of a different type.
1893       // FIXME: too conservative?
1894       if (NewTyBits != TyBits && !isa<SCEVConstant>(CondUse->Offset)) {
1895         NewCmpVal = CmpVal;
1896         continue;
1897       }
1898
1899       bool AllUsesAreAddresses = true;
1900       bool AllUsesAreOutsideLoop = true;
1901       std::vector<BasedUser> UsersToProcess;
1902       SCEVHandle CommonExprs = CollectIVUsers(SI->first, SI->second, L,
1903                                               AllUsesAreAddresses,
1904                                               AllUsesAreOutsideLoop,
1905                                               UsersToProcess);
1906       // Avoid rewriting the compare instruction with an iv of new stride
1907       // if it's likely the new stride uses will be rewritten using the
1908       if (AllUsesAreAddresses &&
1909           ValidStride(!CommonExprs->isZero(), Scale, UsersToProcess)) {
1910         NewCmpVal = CmpVal;
1911         continue;
1912       }
1913
1914       // If scale is negative, use swapped predicate unless it's testing
1915       // for equality.
1916       if (Scale < 0 && !Cond->isEquality())
1917         Predicate = ICmpInst::getSwappedPredicate(Predicate);
1918
1919       NewStride = &StrideOrder[i];
1920       break;
1921     }
1922   }
1923
1924   // Forgo this transformation if it the increment happens to be
1925   // unfortunately positioned after the condition, and the condition
1926   // has multiple uses which prevent it from being moved immediately
1927   // before the branch. See
1928   // test/Transforms/LoopStrengthReduce/change-compare-stride-trickiness-*.ll
1929   // for an example of this situation.
1930   if (!Cond->hasOneUse()) {
1931     for (BasicBlock::iterator I = Cond, E = Cond->getParent()->end();
1932          I != E; ++I)
1933       if (I == NewIncV)
1934         return Cond;
1935   }
1936
1937   if (NewCmpVal != CmpVal) {
1938     // Create a new compare instruction using new stride / iv.
1939     ICmpInst *OldCond = Cond;
1940     Value *RHS;
1941     if (!isa<PointerType>(NewCmpTy))
1942       RHS = ConstantInt::get(NewCmpTy, NewCmpVal);
1943     else {
1944       RHS = ConstantInt::get(UIntPtrTy, NewCmpVal);
1945       RHS = SCEVExpander::InsertCastOfTo(Instruction::IntToPtr, RHS, NewCmpTy);
1946     }
1947     // Insert new compare instruction.
1948     Cond = new ICmpInst(Predicate, NewIncV, RHS,
1949                         L->getHeader()->getName() + ".termcond",
1950                         OldCond);
1951
1952     // Remove the old compare instruction. The old indvar is probably dead too.
1953     DeadInsts.push_back(cast<Instruction>(CondUse->OperandValToReplace));
1954     SE->deleteValueFromRecords(OldCond);
1955     OldCond->replaceAllUsesWith(Cond);
1956     OldCond->eraseFromParent();
1957
1958     IVUsesByStride[*CondStride].Users.pop_back();
1959     SCEVHandle NewOffset = TyBits == NewTyBits
1960       ? SE->getMulExpr(CondUse->Offset,
1961                        SE->getConstant(ConstantInt::get(CmpTy, Scale)))
1962       : SE->getConstant(ConstantInt::get(NewCmpTy,
1963         cast<SCEVConstant>(CondUse->Offset)->getValue()->getSExtValue()*Scale));
1964     IVUsesByStride[*NewStride].addUser(NewOffset, Cond, NewIncV);
1965     CondUse = &IVUsesByStride[*NewStride].Users.back();
1966     CondStride = NewStride;
1967     ++NumEliminated;
1968   }
1969
1970   return Cond;
1971 }
1972
1973 /// OptimizeSMax - Rewrite the loop's terminating condition if it uses
1974 /// an smax computation.
1975 ///
1976 /// This is a narrow solution to a specific, but acute, problem. For loops
1977 /// like this:
1978 ///
1979 ///   i = 0;
1980 ///   do {
1981 ///     p[i] = 0.0;
1982 ///   } while (++i < n);
1983 ///
1984 /// where the comparison is signed, the trip count isn't just 'n', because
1985 /// 'n' could be negative. And unfortunately this can come up even for loops
1986 /// where the user didn't use a C do-while loop. For example, seemingly
1987 /// well-behaved top-test loops will commonly be lowered like this:
1988 //
1989 ///   if (n > 0) {
1990 ///     i = 0;
1991 ///     do {
1992 ///       p[i] = 0.0;
1993 ///     } while (++i < n);
1994 ///   }
1995 ///
1996 /// and then it's possible for subsequent optimization to obscure the if
1997 /// test in such a way that indvars can't find it.
1998 ///
1999 /// When indvars can't find the if test in loops like this, it creates a
2000 /// signed-max expression, which allows it to give the loop a canonical
2001 /// induction variable:
2002 ///
2003 ///   i = 0;
2004 ///   smax = n < 1 ? 1 : n;
2005 ///   do {
2006 ///     p[i] = 0.0;
2007 ///   } while (++i != smax);
2008 ///
2009 /// Canonical induction variables are necessary because the loop passes
2010 /// are designed around them. The most obvious example of this is the
2011 /// LoopInfo analysis, which doesn't remember trip count values. It
2012 /// expects to be able to rediscover the trip count each time it is
2013 /// needed, and it does this using a simple analyis that only succeeds if
2014 /// the loop has a canonical induction variable.
2015 ///
2016 /// However, when it comes time to generate code, the maximum operation
2017 /// can be quite costly, especially if it's inside of an outer loop.
2018 ///
2019 /// This function solves this problem by detecting this type of loop and
2020 /// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting
2021 /// the instructions for the maximum computation.
2022 ///
2023 ICmpInst *LoopStrengthReduce::OptimizeSMax(Loop *L, ICmpInst *Cond,
2024                                            IVStrideUse* &CondUse) {
2025   // Check that the loop matches the pattern we're looking for.
2026   if (Cond->getPredicate() != CmpInst::ICMP_EQ &&
2027       Cond->getPredicate() != CmpInst::ICMP_NE)
2028     return Cond;
2029
2030   SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1));
2031   if (!Sel || !Sel->hasOneUse()) return Cond;
2032
2033   SCEVHandle IterationCount = SE->getIterationCount(L);
2034   if (isa<SCEVCouldNotCompute>(IterationCount))
2035     return Cond;
2036   SCEVHandle One = SE->getIntegerSCEV(1, IterationCount->getType());
2037
2038   // Adjust for an annoying getIterationCount quirk.
2039   IterationCount = SE->getAddExpr(IterationCount, One);
2040
2041   // Check for a max calculation that matches the pattern.
2042   SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(IterationCount);
2043   if (!SMax || SMax != SE->getSCEV(Sel)) return Cond;
2044
2045   SCEVHandle SMaxLHS = SMax->getOperand(0);
2046   SCEVHandle SMaxRHS = SMax->getOperand(1);
2047   if (!SMaxLHS || SMaxLHS != One) return Cond;
2048
2049   // Check the relevant induction variable for conformance to
2050   // the pattern.
2051   SCEVHandle IV = SE->getSCEV(Cond->getOperand(0));
2052   SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV);
2053   if (!AR || !AR->isAffine() ||
2054       AR->getStart() != One ||
2055       AR->getStepRecurrence(*SE) != One)
2056     return Cond;
2057
2058   // Check the right operand of the select, and remember it, as it will
2059   // be used in the new comparison instruction.
2060   Value *NewRHS = 0;
2061   if (SE->getSCEV(Sel->getOperand(1)) == SMaxRHS)
2062     NewRHS = Sel->getOperand(1);
2063   else if (SE->getSCEV(Sel->getOperand(2)) == SMaxRHS)
2064     NewRHS = Sel->getOperand(2);
2065   if (!NewRHS) return Cond;
2066
2067   // Ok, everything looks ok to change the condition into an SLT or SGE and
2068   // delete the max calculation.
2069   ICmpInst *NewCond =
2070     new ICmpInst(Cond->getPredicate() == CmpInst::ICMP_NE ?
2071                    CmpInst::ICMP_SLT :
2072                    CmpInst::ICMP_SGE,
2073                  Cond->getOperand(0), NewRHS, "scmp", Cond);
2074
2075   // Delete the max calculation instructions.
2076   SE->deleteValueFromRecords(Cond);
2077   Cond->replaceAllUsesWith(NewCond);
2078   Cond->eraseFromParent();
2079   Instruction *Cmp = cast<Instruction>(Sel->getOperand(0));
2080   SE->deleteValueFromRecords(Sel);
2081   Sel->eraseFromParent();
2082   if (Cmp->use_empty()) {
2083     SE->deleteValueFromRecords(Cmp);
2084     Cmp->eraseFromParent();
2085   }
2086   CondUse->User = NewCond;
2087   return NewCond;
2088 }
2089
2090 /// OptimizeShadowIV - If IV is used in a int-to-float cast
2091 /// inside the loop then try to eliminate the cast opeation.
2092 void LoopStrengthReduce::OptimizeShadowIV(Loop *L) {
2093
2094   SCEVHandle IterationCount = SE->getIterationCount(L);
2095   if (isa<SCEVCouldNotCompute>(IterationCount))
2096     return;
2097
2098   for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e;
2099        ++Stride) {
2100     std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
2101       IVUsesByStride.find(StrideOrder[Stride]);
2102     assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
2103     if (!isa<SCEVConstant>(SI->first))
2104       continue;
2105
2106     for (std::vector<IVStrideUse>::iterator UI = SI->second.Users.begin(),
2107            E = SI->second.Users.end(); UI != E; /* empty */) {
2108       std::vector<IVStrideUse>::iterator CandidateUI = UI;
2109       ++UI;
2110       Instruction *ShadowUse = CandidateUI->User;
2111       const Type *DestTy = NULL;
2112
2113       /* If shadow use is a int->float cast then insert a second IV
2114          to eliminate this cast.
2115
2116            for (unsigned i = 0; i < n; ++i)
2117              foo((double)i);
2118
2119          is transformed into
2120
2121            double d = 0.0;
2122            for (unsigned i = 0; i < n; ++i, ++d)
2123              foo(d);
2124       */
2125       if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->User))
2126         DestTy = UCast->getDestTy();
2127       else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->User))
2128         DestTy = SCast->getDestTy();
2129       if (!DestTy) continue;
2130
2131       if (TLI) {
2132         /* If target does not support DestTy natively then do not apply
2133            this transformation. */
2134         MVT DVT = TLI->getValueType(DestTy);
2135         if (!TLI->isTypeLegal(DVT)) continue;
2136       }
2137
2138       PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0));
2139       if (!PH) continue;
2140       if (PH->getNumIncomingValues() != 2) continue;
2141
2142       const Type *SrcTy = PH->getType();
2143       int Mantissa = DestTy->getFPMantissaWidth();
2144       if (Mantissa == -1) continue;
2145       if ((int)TD->getTypeSizeInBits(SrcTy) > Mantissa)
2146         continue;
2147
2148       unsigned Entry, Latch;
2149       if (PH->getIncomingBlock(0) == L->getLoopPreheader()) {
2150         Entry = 0;
2151         Latch = 1;
2152       } else {
2153         Entry = 1;
2154         Latch = 0;
2155       }
2156
2157       ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry));
2158       if (!Init) continue;
2159       ConstantFP *NewInit = ConstantFP::get(DestTy, Init->getZExtValue());
2160
2161       BinaryOperator *Incr =
2162         dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch));
2163       if (!Incr) continue;
2164       if (Incr->getOpcode() != Instruction::Add
2165           && Incr->getOpcode() != Instruction::Sub)
2166         continue;
2167
2168       /* Initialize new IV, double d = 0.0 in above example. */
2169       ConstantInt *C = NULL;
2170       if (Incr->getOperand(0) == PH)
2171         C = dyn_cast<ConstantInt>(Incr->getOperand(1));
2172       else if (Incr->getOperand(1) == PH)
2173         C = dyn_cast<ConstantInt>(Incr->getOperand(0));
2174       else
2175         continue;
2176
2177       if (!C) continue;
2178
2179       /* Add new PHINode. */
2180       PHINode *NewPH = PHINode::Create(DestTy, "IV.S.", PH);
2181
2182       /* create new increment. '++d' in above example. */
2183       ConstantFP *CFP = ConstantFP::get(DestTy, C->getZExtValue());
2184       BinaryOperator *NewIncr =
2185         BinaryOperator::Create(Incr->getOpcode(),
2186                                NewPH, CFP, "IV.S.next.", Incr);
2187
2188       NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry));
2189       NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch));
2190
2191       /* Remove cast operation */
2192       SE->deleteValueFromRecords(ShadowUse);
2193       ShadowUse->replaceAllUsesWith(NewPH);
2194       ShadowUse->eraseFromParent();
2195       SI->second.Users.erase(CandidateUI);
2196       NumShadow++;
2197       break;
2198     }
2199   }
2200 }
2201
2202 // OptimizeIndvars - Now that IVUsesByStride is set up with all of the indvar
2203 // uses in the loop, look to see if we can eliminate some, in favor of using
2204 // common indvars for the different uses.
2205 void LoopStrengthReduce::OptimizeIndvars(Loop *L) {
2206   // TODO: implement optzns here.
2207
2208   OptimizeShadowIV(L);
2209
2210   // Finally, get the terminating condition for the loop if possible.  If we
2211   // can, we want to change it to use a post-incremented version of its
2212   // induction variable, to allow coalescing the live ranges for the IV into
2213   // one register value.
2214   PHINode *SomePHI = cast<PHINode>(L->getHeader()->begin());
2215   BasicBlock  *Preheader = L->getLoopPreheader();
2216   BasicBlock *LatchBlock =
2217    SomePHI->getIncomingBlock(SomePHI->getIncomingBlock(0) == Preheader);
2218   BranchInst *TermBr = dyn_cast<BranchInst>(LatchBlock->getTerminator());
2219   if (!TermBr || TermBr->isUnconditional() ||
2220       !isa<ICmpInst>(TermBr->getCondition()))
2221     return;
2222   ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition());
2223
2224   // Search IVUsesByStride to find Cond's IVUse if there is one.
2225   IVStrideUse *CondUse = 0;
2226   const SCEVHandle *CondStride = 0;
2227
2228   if (!FindIVUserForCond(Cond, CondUse, CondStride))
2229     return; // setcc doesn't use the IV.
2230
2231   // If the trip count is computed in terms of an smax (due to ScalarEvolution
2232   // being unable to find a sufficient guard, for example), change the loop
2233   // comparison to use SLT instead of NE.
2234   Cond = OptimizeSMax(L, Cond, CondUse);
2235
2236   // If possible, change stride and operands of the compare instruction to
2237   // eliminate one stride.
2238   Cond = ChangeCompareStride(L, Cond, CondUse, CondStride);
2239
2240   // It's possible for the setcc instruction to be anywhere in the loop, and
2241   // possible for it to have multiple users.  If it is not immediately before
2242   // the latch block branch, move it.
2243   if (&*++BasicBlock::iterator(Cond) != (Instruction*)TermBr) {
2244     if (Cond->hasOneUse()) {   // Condition has a single use, just move it.
2245       Cond->moveBefore(TermBr);
2246     } else {
2247       // Otherwise, clone the terminating condition and insert into the loopend.
2248       Cond = cast<ICmpInst>(Cond->clone());
2249       Cond->setName(L->getHeader()->getName() + ".termcond");
2250       LatchBlock->getInstList().insert(TermBr, Cond);
2251
2252       // Clone the IVUse, as the old use still exists!
2253       IVUsesByStride[*CondStride].addUser(CondUse->Offset, Cond,
2254                                          CondUse->OperandValToReplace);
2255       CondUse = &IVUsesByStride[*CondStride].Users.back();
2256     }
2257   }
2258
2259   // If we get to here, we know that we can transform the setcc instruction to
2260   // use the post-incremented version of the IV, allowing us to coalesce the
2261   // live ranges for the IV correctly.
2262   CondUse->Offset = SE->getMinusSCEV(CondUse->Offset, *CondStride);
2263   CondUse->isUseOfPostIncrementedValue = true;
2264   Changed = true;
2265 }
2266
2267 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager &LPM) {
2268
2269   LI = &getAnalysis<LoopInfo>();
2270   DT = &getAnalysis<DominatorTree>();
2271   SE = &getAnalysis<ScalarEvolution>();
2272   TD = &getAnalysis<TargetData>();
2273   UIntPtrTy = TD->getIntPtrType();
2274   Changed = false;
2275
2276   // Find all uses of induction variables in this loop, and categorize
2277   // them by stride.  Start by finding all of the PHI nodes in the header for
2278   // this loop.  If they are induction variables, inspect their uses.
2279   SmallPtrSet<Instruction*,16> Processed;   // Don't reprocess instructions.
2280   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
2281     AddUsersIfInteresting(I, L, Processed);
2282
2283   if (!IVUsesByStride.empty()) {
2284     // Optimize induction variables.  Some indvar uses can be transformed to use
2285     // strides that will be needed for other purposes.  A common example of this
2286     // is the exit test for the loop, which can often be rewritten to use the
2287     // computation of some other indvar to decide when to terminate the loop.
2288     OptimizeIndvars(L);
2289
2290     // FIXME: We can widen subreg IV's here for RISC targets.  e.g. instead of
2291     // doing computation in byte values, promote to 32-bit values if safe.
2292
2293     // FIXME: Attempt to reuse values across multiple IV's.  In particular, we
2294     // could have something like "for(i) { foo(i*8); bar(i*16) }", which should
2295     // be codegened as "for (j = 0;; j+=8) { foo(j); bar(j+j); }" on X86/PPC.
2296     // Need to be careful that IV's are all the same type.  Only works for
2297     // intptr_t indvars.
2298
2299     // If we only have one stride, we can more aggressively eliminate some
2300     // things.
2301     bool HasOneStride = IVUsesByStride.size() == 1;
2302
2303 #ifndef NDEBUG
2304     DOUT << "\nLSR on ";
2305     DEBUG(L->dump());
2306 #endif
2307
2308     // IVsByStride keeps IVs for one particular loop.
2309     assert(IVsByStride.empty() && "Stale entries in IVsByStride?");
2310
2311     // Sort the StrideOrder so we process larger strides first.
2312     std::stable_sort(StrideOrder.begin(), StrideOrder.end(), StrideCompare());
2313
2314     // Note: this processes each stride/type pair individually.  All users
2315     // passed into StrengthReduceStridedIVUsers have the same type AND stride.
2316     // Also, note that we iterate over IVUsesByStride indirectly by using
2317     // StrideOrder. This extra layer of indirection makes the ordering of
2318     // strides deterministic - not dependent on map order.
2319     for (unsigned Stride = 0, e = StrideOrder.size(); Stride != e; ++Stride) {
2320       std::map<SCEVHandle, IVUsersOfOneStride>::iterator SI =
2321         IVUsesByStride.find(StrideOrder[Stride]);
2322       assert(SI != IVUsesByStride.end() && "Stride doesn't exist!");
2323       StrengthReduceStridedIVUsers(SI->first, SI->second, L, HasOneStride);
2324     }
2325   }
2326
2327   // We're done analyzing this loop; release all the state we built up for it.
2328   CastedPointers.clear();
2329   IVUsesByStride.clear();
2330   IVsByStride.clear();
2331   StrideOrder.clear();
2332   for (unsigned i=0; i<GEPlist.size(); i++)
2333     SE->deleteValueFromRecords(GEPlist[i]);
2334   GEPlist.clear();
2335
2336   // Clean up after ourselves
2337   if (!DeadInsts.empty()) {
2338     DeleteTriviallyDeadInstructions();
2339
2340     BasicBlock::iterator I = L->getHeader()->begin();
2341     while (PHINode *PN = dyn_cast<PHINode>(I++)) {
2342       // At this point, we know that we have killed one or more IV users.
2343       // It is worth checking to see if the cannonical indvar is also
2344       // dead, so that we can remove it as well.
2345       //
2346       // We can remove a PHI if it is on a cycle in the def-use graph
2347       // where each node in the cycle has degree one, i.e. only one use,
2348       // and is an instruction with no side effects.
2349       //
2350       // FIXME: this needs to eliminate an induction variable even if it's being
2351       // compared against some value to decide loop termination.
2352       if (!PN->hasOneUse())
2353         continue;
2354
2355       SmallPtrSet<PHINode *, 4> PHIs;
2356       for (Instruction *J = dyn_cast<Instruction>(*PN->use_begin());
2357            J && J->hasOneUse() && !J->mayWriteToMemory();
2358            J = dyn_cast<Instruction>(*J->use_begin())) {
2359         // If we find the original PHI, we've discovered a cycle.
2360         if (J == PN) {
2361           // Break the cycle and mark the PHI for deletion.
2362           SE->deleteValueFromRecords(PN);
2363           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
2364           DeadInsts.push_back(PN);
2365           Changed = true;
2366           break;
2367         }
2368         // If we find a PHI more than once, we're on a cycle that
2369         // won't prove fruitful.
2370         if (isa<PHINode>(J) && !PHIs.insert(cast<PHINode>(J)))
2371           break;
2372       }
2373     }
2374     DeleteTriviallyDeadInstructions();
2375   }
2376   return Changed;
2377 }