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