lib/Transforms/Scalar/LoopStrengthReduce.cpp

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