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 // Terminology note: this code has a lot of handling for "post-increment" or
  21 // "post-inc" users. This is not talking about post-increment addressing modes;
  22 // it is instead talking about code like this:
  23 //
  24 //   %i = phi [ 0, %entry ], [ %i.next, %latch ]
  25 //   ...
  26 //   %i.next = add %i, 1
  27 //   %c = icmp eq %i.next, %n
  28 //
  29 // The SCEV for %i is {0,+,1}<%L>. The SCEV for %i.next is {1,+,1}<%L>, however
  30 // it's useful to think about these as the same register, with some uses using
  31 // the value of the register before the add and some using it after. In this
  32 // example, the icmp is a post-increment user, since it uses %i.next, which is
  33 // the value of the induction variable after the increment. The other common
  34 // case of post-increment users is users outside the loop.
  35 //
  36 // TODO: More sophistication in the way Formulae are generated and filtered.
  37 //
  38 // TODO: Handle multiple loops at a time.
  39 //
  40 // TODO: Should the addressing mode BaseGV be changed to a ConstantExpr instead
  41 //       of a GlobalValue?
  42 //
  43 // TODO: When truncation is free, truncate ICmp users' operands to make it a
  44 //       smaller encoding (on x86 at least).
  45 //
  46 // TODO: When a negated register is used by an add (such as in a list of
  47 //       multiple base registers, or as the increment expression in an addrec),
  48 //       we may not actually need both reg and (-1 * reg) in registers; the
  49 //       negation can be implemented by using a sub instead of an add. The
  50 //       lack of support for taking this into consideration when making
  51 //       register pressure decisions is partly worked around by the "Special"
  52 //       use kind.
  53 //
  54 //===----------------------------------------------------------------------===//
  55
  56 #include "llvm/Transforms/Scalar.h"
  57 #include "llvm/ADT/DenseSet.h"
  58 #include "llvm/ADT/Hashing.h"
  59 #include "llvm/ADT/STLExtras.h"
  60 #include "llvm/ADT/SetVector.h"
  61 #include "llvm/ADT/SmallBitVector.h"
  62 #include "llvm/Analysis/IVUsers.h"
  63 #include "llvm/Analysis/LoopPass.h"
  64 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  65 #include "llvm/Analysis/TargetTransformInfo.h"
  66 #include "llvm/IR/Constants.h"
  67 #include "llvm/IR/DerivedTypes.h"
  68 #include "llvm/IR/Dominators.h"
  69 #include "llvm/IR/Instructions.h"
  70 #include "llvm/IR/IntrinsicInst.h"
  71 #include "llvm/IR/Module.h"
  72 #include "llvm/IR/ValueHandle.h"
  73 #include "llvm/Support/CommandLine.h"
  74 #include "llvm/Support/Debug.h"
  75 #include "llvm/Support/raw_ostream.h"
  76 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  77 #include "llvm/Transforms/Utils/Local.h"
  78 #include <algorithm>
  79 using namespace llvm;
  80
  81 #define DEBUG_TYPE "loop-reduce"
  82
  83 /// MaxIVUsers is an arbitrary threshold that provides an early opportunitiy for
  84 /// bail out. This threshold is far beyond the number of users that LSR can
  85 /// conceivably solve, so it should not affect generated code, but catches the
  86 /// worst cases before LSR burns too much compile time and stack space.
  87 static const unsigned MaxIVUsers = 200;
  88
  89 // Temporary flag to cleanup congruent phis after LSR phi expansion.
  90 // It's currently disabled until we can determine whether it's truly useful or
  91 // not. The flag should be removed after the v3.0 release.
  92 // This is now needed for ivchains.
  93 static cl::opt<bool> EnablePhiElim(
  94   "enable-lsr-phielim", cl::Hidden, cl::init(true),
  95   cl::desc("Enable LSR phi elimination"));
  96
  97 #ifndef NDEBUG
  98 // Stress test IV chain generation.
  99 static cl::opt<bool> StressIVChain(
 100   "stress-ivchain", cl::Hidden, cl::init(false),
 101   cl::desc("Stress test LSR IV chains"));
 102 #else
 103 static bool StressIVChain = false;
 104 #endif
 105
 106 namespace {
 107
 108 struct MemAccessTy {
 109   /// Used in situations where the accessed memory type is unknown.
 110   static const unsigned UnknownAddressSpace = ~0u;
 111
 112   Type *MemTy;
 113   unsigned AddrSpace;
 114
 115   MemAccessTy() : MemTy(nullptr), AddrSpace(UnknownAddressSpace) {}
 116
 117   MemAccessTy(Type *Ty, unsigned AS) :
 118     MemTy(Ty), AddrSpace(AS) {}
 119
 120   bool operator==(MemAccessTy Other) const {
 121     return MemTy == Other.MemTy && AddrSpace == Other.AddrSpace;
 122   }
 123
 124   bool operator!=(MemAccessTy Other) const { return !(*this == Other); }
 125
 126   static MemAccessTy getUnknown(LLVMContext &Ctx) {
 127     return MemAccessTy(Type::getVoidTy(Ctx), UnknownAddressSpace);
 128   }
 129 };
 130
 131 /// This class holds data which is used to order reuse candidates.
 132 class RegSortData {
 133 public:
 134   /// This represents the set of LSRUse indices which reference
 135   /// a particular register.
 136   SmallBitVector UsedByIndices;
 137
 138   void print(raw_ostream &OS) const;
 139   void dump() const;
 140 };
 141
 142 }
 143
 144 void RegSortData::print(raw_ostream &OS) const {
 145   OS << "[NumUses=" << UsedByIndices.count() << ']';
 146 }
 147
 148 LLVM_DUMP_METHOD
 149 void RegSortData::dump() const {
 150   print(errs()); errs() << '\n';
 151 }
 152
 153 namespace {
 154
 155 /// Map register candidates to information about how they are used.
 156 class RegUseTracker {
 157   typedef DenseMap<const SCEV *, RegSortData> RegUsesTy;
 158
 159   RegUsesTy RegUsesMap;
 160   SmallVector<const SCEV *, 16> RegSequence;
 161
 162 public:
 163   void countRegister(const SCEV *Reg, size_t LUIdx);
 164   void dropRegister(const SCEV *Reg, size_t LUIdx);
 165   void swapAndDropUse(size_t LUIdx, size_t LastLUIdx);
 166
 167   bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const;
 168
 169   const SmallBitVector &getUsedByIndices(const SCEV *Reg) const;
 170
 171   void clear();
 172
 173   typedef SmallVectorImpl<const SCEV *>::iterator iterator;
 174   typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator;
 175   iterator begin() { return RegSequence.begin(); }
 176   iterator end()   { return RegSequence.end(); }
 177   const_iterator begin() const { return RegSequence.begin(); }
 178   const_iterator end() const   { return RegSequence.end(); }
 179 };
 180
 181 }
 182
 183 void
 184 RegUseTracker::countRegister(const SCEV *Reg, size_t LUIdx) {
 185   std::pair<RegUsesTy::iterator, bool> Pair =
 186     RegUsesMap.insert(std::make_pair(Reg, RegSortData()));
 187   RegSortData &RSD = Pair.first->second;
 188   if (Pair.second)
 189     RegSequence.push_back(Reg);
 190   RSD.UsedByIndices.resize(std::max(RSD.UsedByIndices.size(), LUIdx + 1));
 191   RSD.UsedByIndices.set(LUIdx);
 192 }
 193
 194 void
 195 RegUseTracker::dropRegister(const SCEV *Reg, size_t LUIdx) {
 196   RegUsesTy::iterator It = RegUsesMap.find(Reg);
 197   assert(It != RegUsesMap.end());
 198   RegSortData &RSD = It->second;
 199   assert(RSD.UsedByIndices.size() > LUIdx);
 200   RSD.UsedByIndices.reset(LUIdx);
 201 }
 202
 203 void
 204 RegUseTracker::swapAndDropUse(size_t LUIdx, size_t LastLUIdx) {
 205   assert(LUIdx <= LastLUIdx);
 206
 207   // Update RegUses. The data structure is not optimized for this purpose;
 208   // we must iterate through it and update each of the bit vectors.
 209   for (auto &Pair : RegUsesMap) {
 210     SmallBitVector &UsedByIndices = Pair.second.UsedByIndices;
 211     if (LUIdx < UsedByIndices.size())
 212       UsedByIndices[LUIdx] =
 213         LastLUIdx < UsedByIndices.size() ? UsedByIndices[LastLUIdx] : 0;
 214     UsedByIndices.resize(std::min(UsedByIndices.size(), LastLUIdx));
 215   }
 216 }
 217
 218 bool
 219 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const {
 220   RegUsesTy::const_iterator I = RegUsesMap.find(Reg);
 221   if (I == RegUsesMap.end())
 222     return false;
 223   const SmallBitVector &UsedByIndices = I->second.UsedByIndices;
 224   int i = UsedByIndices.find_first();
 225   if (i == -1) return false;
 226   if ((size_t)i != LUIdx) return true;
 227   return UsedByIndices.find_next(i) != -1;
 228 }
 229
 230 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const {
 231   RegUsesTy::const_iterator I = RegUsesMap.find(Reg);
 232   assert(I != RegUsesMap.end() && "Unknown register!");
 233   return I->second.UsedByIndices;
 234 }
 235
 236 void RegUseTracker::clear() {
 237   RegUsesMap.clear();
 238   RegSequence.clear();
 239 }
 240
 241 namespace {
 242
 243 /// This class holds information that describes a formula for computing
 244 /// satisfying a use. It may include broken-out immediates and scaled registers.
 245 struct Formula {
 246   /// Global base address used for complex addressing.
 247   GlobalValue *BaseGV;
 248
 249   /// Base offset for complex addressing.
 250   int64_t BaseOffset;
 251
 252   /// Whether any complex addressing has a base register.
 253   bool HasBaseReg;
 254
 255   /// The scale of any complex addressing.
 256   int64_t Scale;
 257
 258   /// The list of "base" registers for this use. When this is non-empty. The
 259   /// canonical representation of a formula is
 260   /// 1. BaseRegs.size > 1 implies ScaledReg != NULL and
 261   /// 2. ScaledReg != NULL implies Scale != 1 || !BaseRegs.empty().
 262   /// #1 enforces that the scaled register is always used when at least two
 263   /// registers are needed by the formula: e.g., reg1 + reg2 is reg1 + 1 * reg2.
 264   /// #2 enforces that 1 * reg is reg.
 265   /// This invariant can be temporarly broken while building a formula.
 266   /// However, every formula inserted into the LSRInstance must be in canonical
 267   /// form.
 268   SmallVector<const SCEV *, 4> BaseRegs;
 269
 270   /// The 'scaled' register for this use. This should be non-null when Scale is
 271   /// not zero.
 272   const SCEV *ScaledReg;
 273
 274   /// An additional constant offset which added near the use. This requires a
 275   /// temporary register, but the offset itself can live in an add immediate
 276   /// field rather than a register.
 277   int64_t UnfoldedOffset;
 278
 279   Formula()
 280       : BaseGV(nullptr), BaseOffset(0), HasBaseReg(false), Scale(0),
 281         ScaledReg(nullptr), UnfoldedOffset(0) {}
 282
 283   void initialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE);
 284
 285   bool isCanonical() const;
 286
 287   void canonicalize();
 288
 289   bool unscale();
 290
 291   size_t getNumRegs() const;
 292   Type *getType() const;
 293
 294   void deleteBaseReg(const SCEV *&S);
 295
 296   bool referencesReg(const SCEV *S) const;
 297   bool hasRegsUsedByUsesOtherThan(size_t LUIdx,
 298                                   const RegUseTracker &RegUses) const;
 299
 300   void print(raw_ostream &OS) const;
 301   void dump() const;
 302 };
 303
 304 }
 305
 306 /// Recursion helper for initialMatch.
 307 static void DoInitialMatch(const SCEV *S, Loop *L,
 308                            SmallVectorImpl<const SCEV *> &Good,
 309                            SmallVectorImpl<const SCEV *> &Bad,
 310                            ScalarEvolution &SE) {
 311   // Collect expressions which properly dominate the loop header.
 312   if (SE.properlyDominates(S, L->getHeader())) {
 313     Good.push_back(S);
 314     return;
 315   }
 316
 317   // Look at add operands.
 318   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 319     for (const SCEV *S : Add->operands())
 320       DoInitialMatch(S, L, Good, Bad, SE);
 321     return;
 322   }
 323
 324   // Look at addrec operands.
 325   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
 326     if (!AR->getStart()->isZero()) {
 327       DoInitialMatch(AR->getStart(), L, Good, Bad, SE);
 328       DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0),
 329                                       AR->getStepRecurrence(SE),
 330                                       // FIXME: AR->getNoWrapFlags()
 331                                       AR->getLoop(), SCEV::FlagAnyWrap),
 332                      L, Good, Bad, SE);
 333       return;
 334     }
 335
 336   // Handle a multiplication by -1 (negation) if it didn't fold.
 337   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S))
 338     if (Mul->getOperand(0)->isAllOnesValue()) {
 339       SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end());
 340       const SCEV *NewMul = SE.getMulExpr(Ops);
 341
 342       SmallVector<const SCEV *, 4> MyGood;
 343       SmallVector<const SCEV *, 4> MyBad;
 344       DoInitialMatch(NewMul, L, MyGood, MyBad, SE);
 345       const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue(
 346         SE.getEffectiveSCEVType(NewMul->getType())));
 347       for (const SCEV *S : MyGood)
 348         Good.push_back(SE.getMulExpr(NegOne, S));
 349       for (const SCEV *S : MyBad)
 350         Bad.push_back(SE.getMulExpr(NegOne, S));
 351       return;
 352     }
 353
 354   // Ok, we can't do anything interesting. Just stuff the whole thing into a
 355   // register and hope for the best.
 356   Bad.push_back(S);
 357 }
 358
 359 /// Incorporate loop-variant parts of S into this Formula, attempting to keep
 360 /// all loop-invariant and loop-computable values in a single base register.
 361 void Formula::initialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) {
 362   SmallVector<const SCEV *, 4> Good;
 363   SmallVector<const SCEV *, 4> Bad;
 364   DoInitialMatch(S, L, Good, Bad, SE);
 365   if (!Good.empty()) {
 366     const SCEV *Sum = SE.getAddExpr(Good);
 367     if (!Sum->isZero())
 368       BaseRegs.push_back(Sum);
 369     HasBaseReg = true;
 370   }
 371   if (!Bad.empty()) {
 372     const SCEV *Sum = SE.getAddExpr(Bad);
 373     if (!Sum->isZero())
 374       BaseRegs.push_back(Sum);
 375     HasBaseReg = true;
 376   }
 377   canonicalize();
 378 }
 379
 380 /// \brief Check whether or not this formula statisfies the canonical
 381 /// representation.
 382 /// \see Formula::BaseRegs.
 383 bool Formula::isCanonical() const {
 384   if (ScaledReg)
 385     return Scale != 1 || !BaseRegs.empty();
 386   return BaseRegs.size() <= 1;
 387 }
 388
 389 /// \brief Helper method to morph a formula into its canonical representation.
 390 /// \see Formula::BaseRegs.
 391 /// Every formula having more than one base register, must use the ScaledReg
 392 /// field. Otherwise, we would have to do special cases everywhere in LSR
 393 /// to treat reg1 + reg2 + ... the same way as reg1 + 1*reg2 + ...
 394 /// On the other hand, 1*reg should be canonicalized into reg.
 395 void Formula::canonicalize() {
 396   if (isCanonical())
 397     return;
 398   // So far we did not need this case. This is easy to implement but it is
 399   // useless to maintain dead code. Beside it could hurt compile time.
 400   assert(!BaseRegs.empty() && "1*reg => reg, should not be needed.");
 401   // Keep the invariant sum in BaseRegs and one of the variant sum in ScaledReg.
 402   ScaledReg = BaseRegs.back();
 403   BaseRegs.pop_back();
 404   Scale = 1;
 405   size_t BaseRegsSize = BaseRegs.size();
 406   size_t Try = 0;
 407   // If ScaledReg is an invariant, try to find a variant expression.
 408   while (Try < BaseRegsSize && !isa<SCEVAddRecExpr>(ScaledReg))
 409     std::swap(ScaledReg, BaseRegs[Try++]);
 410 }
 411
 412 /// \brief Get rid of the scale in the formula.
 413 /// In other words, this method morphes reg1 + 1*reg2 into reg1 + reg2.
 414 /// \return true if it was possible to get rid of the scale, false otherwise.
 415 /// \note After this operation the formula may not be in the canonical form.
 416 bool Formula::unscale() {
 417   if (Scale != 1)
 418     return false;
 419   Scale = 0;
 420   BaseRegs.push_back(ScaledReg);
 421   ScaledReg = nullptr;
 422   return true;
 423 }
 424
 425 /// Return the total number of register operands used by this formula. This does
 426 /// not include register uses implied by non-constant addrec strides.
 427 size_t Formula::getNumRegs() const {
 428   return !!ScaledReg + BaseRegs.size();
 429 }
 430
 431 /// Return the type of this formula, if it has one, or null otherwise. This type
 432 /// is meaningless except for the bit size.
 433 Type *Formula::getType() const {
 434   return !BaseRegs.empty() ? BaseRegs.front()->getType() :
 435          ScaledReg ? ScaledReg->getType() :
 436          BaseGV ? BaseGV->getType() :
 437          nullptr;
 438 }
 439
 440 /// Delete the given base reg from the BaseRegs list.
 441 void Formula::deleteBaseReg(const SCEV *&S) {
 442   if (&S != &BaseRegs.back())
 443     std::swap(S, BaseRegs.back());
 444   BaseRegs.pop_back();
 445 }
 446
 447 /// Test if this formula references the given register.
 448 bool Formula::referencesReg(const SCEV *S) const {
 449   return S == ScaledReg ||
 450          std::find(BaseRegs.begin(), BaseRegs.end(), S) != BaseRegs.end();
 451 }
 452
 453 /// Test whether this formula uses registers which are used by uses other than
 454 /// the use with the given index.
 455 bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx,
 456                                          const RegUseTracker &RegUses) const {
 457   if (ScaledReg)
 458     if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx))
 459       return true;
 460   for (const SCEV *BaseReg : BaseRegs)
 461     if (RegUses.isRegUsedByUsesOtherThan(BaseReg, LUIdx))
 462       return true;
 463   return false;
 464 }
 465
 466 void Formula::print(raw_ostream &OS) const {
 467   bool First = true;
 468   if (BaseGV) {
 469     if (!First) OS << " + "; else First = false;
 470     BaseGV->printAsOperand(OS, /*PrintType=*/false);
 471   }
 472   if (BaseOffset != 0) {
 473     if (!First) OS << " + "; else First = false;
 474     OS << BaseOffset;
 475   }
 476   for (const SCEV *BaseReg : BaseRegs) {
 477     if (!First) OS << " + "; else First = false;
 478     OS << "reg(" << *BaseReg << ')';
 479   }
 480   if (HasBaseReg && BaseRegs.empty()) {
 481     if (!First) OS << " + "; else First = false;
 482     OS << "**error: HasBaseReg**";
 483   } else if (!HasBaseReg && !BaseRegs.empty()) {
 484     if (!First) OS << " + "; else First = false;
 485     OS << "**error: !HasBaseReg**";
 486   }
 487   if (Scale != 0) {
 488     if (!First) OS << " + "; else First = false;
 489     OS << Scale << "*reg(";
 490     if (ScaledReg)
 491       OS << *ScaledReg;
 492     else
 493       OS << "<unknown>";
 494     OS << ')';
 495   }
 496   if (UnfoldedOffset != 0) {
 497     if (!First) OS << " + ";
 498     OS << "imm(" << UnfoldedOffset << ')';
 499   }
 500 }
 501
 502 LLVM_DUMP_METHOD
 503 void Formula::dump() const {
 504   print(errs()); errs() << '\n';
 505 }
 506
 507 /// Return true if the given addrec can be sign-extended without changing its
 508 /// value.
 509 static bool isAddRecSExtable(const SCEVAddRecExpr *AR, ScalarEvolution &SE) {
 510   Type *WideTy =
 511     IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(AR->getType()) + 1);
 512   return isa<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
 513 }
 514
 515 /// Return true if the given add can be sign-extended without changing its
 516 /// value.
 517 static bool isAddSExtable(const SCEVAddExpr *A, ScalarEvolution &SE) {
 518   Type *WideTy =
 519     IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(A->getType()) + 1);
 520   return isa<SCEVAddExpr>(SE.getSignExtendExpr(A, WideTy));
 521 }
 522
 523 /// Return true if the given mul can be sign-extended without changing its
 524 /// value.
 525 static bool isMulSExtable(const SCEVMulExpr *M, ScalarEvolution &SE) {
 526   Type *WideTy =
 527     IntegerType::get(SE.getContext(),
 528                      SE.getTypeSizeInBits(M->getType()) * M->getNumOperands());
 529   return isa<SCEVMulExpr>(SE.getSignExtendExpr(M, WideTy));
 530 }
 531
 532 /// Return an expression for LHS /s RHS, if it can be determined and if the
 533 /// remainder is known to be zero, or null otherwise. If IgnoreSignificantBits
 534 /// is true, expressions like (X * Y) /s Y are simplified to Y, ignoring that
 535 /// the multiplication may overflow, which is useful when the result will be
 536 /// used in a context where the most significant bits are ignored.
 537 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS,
 538                                 ScalarEvolution &SE,
 539                                 bool IgnoreSignificantBits = false) {
 540   // Handle the trivial case, which works for any SCEV type.
 541   if (LHS == RHS)
 542     return SE.getConstant(LHS->getType(), 1);
 543
 544   // Handle a few RHS special cases.
 545   const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS);
 546   if (RC) {
 547     const APInt &RA = RC->getAPInt();
 548     // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do
 549     // some folding.
 550     if (RA.isAllOnesValue())
 551       return SE.getMulExpr(LHS, RC);
 552     // Handle x /s 1 as x.
 553     if (RA == 1)
 554       return LHS;
 555   }
 556
 557   // Check for a division of a constant by a constant.
 558   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) {
 559     if (!RC)
 560       return nullptr;
 561     const APInt &LA = C->getAPInt();
 562     const APInt &RA = RC->getAPInt();
 563     if (LA.srem(RA) != 0)
 564       return nullptr;
 565     return SE.getConstant(LA.sdiv(RA));
 566   }
 567
 568   // Distribute the sdiv over addrec operands, if the addrec doesn't overflow.
 569   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) {
 570     if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) {
 571       const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE,
 572                                       IgnoreSignificantBits);
 573       if (!Step) return nullptr;
 574       const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE,
 575                                        IgnoreSignificantBits);
 576       if (!Start) return nullptr;
 577       // FlagNW is independent of the start value, step direction, and is
 578       // preserved with smaller magnitude steps.
 579       // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
 580       return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
 581     }
 582     return nullptr;
 583   }
 584
 585   // Distribute the sdiv over add operands, if the add doesn't overflow.
 586   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) {
 587     if (IgnoreSignificantBits || isAddSExtable(Add, SE)) {
 588       SmallVector<const SCEV *, 8> Ops;
 589       for (const SCEV *S : Add->operands()) {
 590         const SCEV *Op = getExactSDiv(S, RHS, SE, IgnoreSignificantBits);
 591         if (!Op) return nullptr;
 592         Ops.push_back(Op);
 593       }
 594       return SE.getAddExpr(Ops);
 595     }
 596     return nullptr;
 597   }
 598
 599   // Check for a multiply operand that we can pull RHS out of.
 600   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(LHS)) {
 601     if (IgnoreSignificantBits || isMulSExtable(Mul, SE)) {
 602       SmallVector<const SCEV *, 4> Ops;
 603       bool Found = false;
 604       for (const SCEV *S : Mul->operands()) {
 605         if (!Found)
 606           if (const SCEV *Q = getExactSDiv(S, RHS, SE,
 607                                            IgnoreSignificantBits)) {
 608             S = Q;
 609             Found = true;
 610           }
 611         Ops.push_back(S);
 612       }
 613       return Found ? SE.getMulExpr(Ops) : nullptr;
 614     }
 615     return nullptr;
 616   }
 617
 618   // Otherwise we don't know.
 619   return nullptr;
 620 }
 621
 622 /// If S involves the addition of a constant integer value, return that integer
 623 /// value, and mutate S to point to a new SCEV with that value excluded.
 624 static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) {
 625   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
 626     if (C->getAPInt().getMinSignedBits() <= 64) {
 627       S = SE.getConstant(C->getType(), 0);
 628       return C->getValue()->getSExtValue();
 629     }
 630   } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 631     SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
 632     int64_t Result = ExtractImmediate(NewOps.front(), SE);
 633     if (Result != 0)
 634       S = SE.getAddExpr(NewOps);
 635     return Result;
 636   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 637     SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
 638     int64_t Result = ExtractImmediate(NewOps.front(), SE);
 639     if (Result != 0)
 640       S = SE.getAddRecExpr(NewOps, AR->getLoop(),
 641                            // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
 642                            SCEV::FlagAnyWrap);
 643     return Result;
 644   }
 645   return 0;
 646 }
 647
 648 /// If S involves the addition of a GlobalValue address, return that symbol, and
 649 /// mutate S to point to a new SCEV with that value excluded.
 650 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) {
 651   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
 652     if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) {
 653       S = SE.getConstant(GV->getType(), 0);
 654       return GV;
 655     }
 656   } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 657     SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
 658     GlobalValue *Result = ExtractSymbol(NewOps.back(), SE);
 659     if (Result)
 660       S = SE.getAddExpr(NewOps);
 661     return Result;
 662   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 663     SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
 664     GlobalValue *Result = ExtractSymbol(NewOps.front(), SE);
 665     if (Result)
 666       S = SE.getAddRecExpr(NewOps, AR->getLoop(),
 667                            // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
 668                            SCEV::FlagAnyWrap);
 669     return Result;
 670   }
 671   return nullptr;
 672 }
 673
 674 /// Returns true if the specified instruction is using the specified value as an
 675 /// address.
 676 static bool isAddressUse(Instruction *Inst, Value *OperandVal) {
 677   bool isAddress = isa<LoadInst>(Inst);
 678   if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 679     if (SI->getOperand(1) == OperandVal)
 680       isAddress = true;
 681   } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
 682     // Addressing modes can also be folded into prefetches and a variety
 683     // of intrinsics.
 684     switch (II->getIntrinsicID()) {
 685       default: break;
 686       case Intrinsic::prefetch:
 687       case Intrinsic::x86_sse_storeu_ps:
 688       case Intrinsic::x86_sse2_storeu_pd:
 689       case Intrinsic::x86_sse2_storeu_dq:
 690       case Intrinsic::x86_sse2_storel_dq:
 691         if (II->getArgOperand(0) == OperandVal)
 692           isAddress = true;
 693         break;
 694     }
 695   }
 696   return isAddress;
 697 }
 698
 699 /// Return the type of the memory being accessed.
 700 static MemAccessTy getAccessType(const Instruction *Inst) {
 701   MemAccessTy AccessTy(Inst->getType(), MemAccessTy::UnknownAddressSpace);
 702   if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 703     AccessTy.MemTy = SI->getOperand(0)->getType();
 704     AccessTy.AddrSpace = SI->getPointerAddressSpace();
 705   } else if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 706     AccessTy.AddrSpace = LI->getPointerAddressSpace();
 707   } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
 708     // Addressing modes can also be folded into prefetches and a variety
 709     // of intrinsics.
 710     switch (II->getIntrinsicID()) {
 711     default: break;
 712     case Intrinsic::x86_sse_storeu_ps:
 713     case Intrinsic::x86_sse2_storeu_pd:
 714     case Intrinsic::x86_sse2_storeu_dq:
 715     case Intrinsic::x86_sse2_storel_dq:
 716       AccessTy.MemTy = II->getArgOperand(0)->getType();
 717       break;
 718     }
 719   }
 720
 721   // All pointers have the same requirements, so canonicalize them to an
 722   // arbitrary pointer type to minimize variation.
 723   if (PointerType *PTy = dyn_cast<PointerType>(AccessTy.MemTy))
 724     AccessTy.MemTy = PointerType::get(IntegerType::get(PTy->getContext(), 1),
 725                                       PTy->getAddressSpace());
 726
 727   return AccessTy;
 728 }
 729
 730 /// Return true if this AddRec is already a phi in its loop.
 731 static bool isExistingPhi(const SCEVAddRecExpr *AR, ScalarEvolution &SE) {
 732   for (BasicBlock::iterator I = AR->getLoop()->getHeader()->begin();
 733        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
 734     if (SE.isSCEVable(PN->getType()) &&
 735         (SE.getEffectiveSCEVType(PN->getType()) ==
 736          SE.getEffectiveSCEVType(AR->getType())) &&
 737         SE.getSCEV(PN) == AR)
 738       return true;
 739   }
 740   return false;
 741 }
 742
 743 /// Check if expanding this expression is likely to incur significant cost. This
 744 /// is tricky because SCEV doesn't track which expressions are actually computed
 745 /// by the current IR.
 746 ///
 747 /// We currently allow expansion of IV increments that involve adds,
 748 /// multiplication by constants, and AddRecs from existing phis.
 749 ///
 750 /// TODO: Allow UDivExpr if we can find an existing IV increment that is an
 751 /// obvious multiple of the UDivExpr.
 752 static bool isHighCostExpansion(const SCEV *S,
 753                                 SmallPtrSetImpl<const SCEV*> &Processed,
 754                                 ScalarEvolution &SE) {
 755   // Zero/One operand expressions
 756   switch (S->getSCEVType()) {
 757   case scUnknown:
 758   case scConstant:
 759     return false;
 760   case scTruncate:
 761     return isHighCostExpansion(cast<SCEVTruncateExpr>(S)->getOperand(),
 762                                Processed, SE);
 763   case scZeroExtend:
 764     return isHighCostExpansion(cast<SCEVZeroExtendExpr>(S)->getOperand(),
 765                                Processed, SE);
 766   case scSignExtend:
 767     return isHighCostExpansion(cast<SCEVSignExtendExpr>(S)->getOperand(),
 768                                Processed, SE);
 769   }
 770
 771   if (!Processed.insert(S).second)
 772     return false;
 773
 774   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 775     for (const SCEV *S : Add->operands()) {
 776       if (isHighCostExpansion(S, Processed, SE))
 777         return true;
 778     }
 779     return false;
 780   }
 781
 782   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
 783     if (Mul->getNumOperands() == 2) {
 784       // Multiplication by a constant is ok
 785       if (isa<SCEVConstant>(Mul->getOperand(0)))
 786         return isHighCostExpansion(Mul->getOperand(1), Processed, SE);
 787
 788       // If we have the value of one operand, check if an existing
 789       // multiplication already generates this expression.
 790       if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Mul->getOperand(1))) {
 791         Value *UVal = U->getValue();
 792         for (User *UR : UVal->users()) {
 793           // If U is a constant, it may be used by a ConstantExpr.
 794           Instruction *UI = dyn_cast<Instruction>(UR);
 795           if (UI && UI->getOpcode() == Instruction::Mul &&
 796               SE.isSCEVable(UI->getType())) {
 797             return SE.getSCEV(UI) == Mul;
 798           }
 799         }
 800       }
 801     }
 802   }
 803
 804   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 805     if (isExistingPhi(AR, SE))
 806       return false;
 807   }
 808
 809   // Fow now, consider any other type of expression (div/mul/min/max) high cost.
 810   return true;
 811 }
 812
 813 /// If any of the instructions is the specified set are trivially dead, delete
 814 /// them and see if this makes any of their operands subsequently dead.
 815 static bool
 816 DeleteTriviallyDeadInstructions(SmallVectorImpl<WeakVH> &DeadInsts) {
 817   bool Changed = false;
 818
 819   while (!DeadInsts.empty()) {
 820     Value *V = DeadInsts.pop_back_val();
 821     Instruction *I = dyn_cast_or_null<Instruction>(V);
 822
 823     if (!I || !isInstructionTriviallyDead(I))
 824       continue;
 825
 826     for (Use &O : I->operands())
 827       if (Instruction *U = dyn_cast<Instruction>(O)) {
 828         O = nullptr;
 829         if (U->use_empty())
 830           DeadInsts.emplace_back(U);
 831       }
 832
 833     I->eraseFromParent();
 834     Changed = true;
 835   }
 836
 837   return Changed;
 838 }
 839
 840 namespace {
 841 class LSRUse;
 842 }
 843
 844 /// \brief Check if the addressing mode defined by \p F is completely
 845 /// folded in \p LU at isel time.
 846 /// This includes address-mode folding and special icmp tricks.
 847 /// This function returns true if \p LU can accommodate what \p F
 848 /// defines and up to 1 base + 1 scaled + offset.
 849 /// In other words, if \p F has several base registers, this function may
 850 /// still return true. Therefore, users still need to account for
 851 /// additional base registers and/or unfolded offsets to derive an
 852 /// accurate cost model.
 853 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
 854                                  const LSRUse &LU, const Formula &F);
 855 // Get the cost of the scaling factor used in F for LU.
 856 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI,
 857                                      const LSRUse &LU, const Formula &F);
 858
 859 namespace {
 860
 861 /// This class is used to measure and compare candidate formulae.
 862 class Cost {
 863   /// TODO: Some of these could be merged. Also, a lexical ordering
 864   /// isn't always optimal.
 865   unsigned NumRegs;
 866   unsigned AddRecCost;
 867   unsigned NumIVMuls;
 868   unsigned NumBaseAdds;
 869   unsigned ImmCost;
 870   unsigned SetupCost;
 871   unsigned ScaleCost;
 872
 873 public:
 874   Cost()
 875     : NumRegs(0), AddRecCost(0), NumIVMuls(0), NumBaseAdds(0), ImmCost(0),
 876       SetupCost(0), ScaleCost(0) {}
 877
 878   bool operator<(const Cost &Other) const;
 879
 880   void Lose();
 881
 882 #ifndef NDEBUG
 883   // Once any of the metrics loses, they must all remain losers.
 884   bool isValid() {
 885     return ((NumRegs | AddRecCost | NumIVMuls | NumBaseAdds
 886              | ImmCost | SetupCost | ScaleCost) != ~0u)
 887       || ((NumRegs & AddRecCost & NumIVMuls & NumBaseAdds
 888            & ImmCost & SetupCost & ScaleCost) == ~0u);
 889   }
 890 #endif
 891
 892   bool isLoser() {
 893     assert(isValid() && "invalid cost");
 894     return NumRegs == ~0u;
 895   }
 896
 897   void RateFormula(const TargetTransformInfo &TTI,
 898                    const Formula &F,
 899                    SmallPtrSetImpl<const SCEV *> &Regs,
 900                    const DenseSet<const SCEV *> &VisitedRegs,
 901                    const Loop *L,
 902                    const SmallVectorImpl<int64_t> &Offsets,
 903                    ScalarEvolution &SE, DominatorTree &DT,
 904                    const LSRUse &LU,
 905                    SmallPtrSetImpl<const SCEV *> *LoserRegs = nullptr);
 906
 907   void print(raw_ostream &OS) const;
 908   void dump() const;
 909
 910 private:
 911   void RateRegister(const SCEV *Reg,
 912                     SmallPtrSetImpl<const SCEV *> &Regs,
 913                     const Loop *L,
 914                     ScalarEvolution &SE, DominatorTree &DT);
 915   void RatePrimaryRegister(const SCEV *Reg,
 916                            SmallPtrSetImpl<const SCEV *> &Regs,
 917                            const Loop *L,
 918                            ScalarEvolution &SE, DominatorTree &DT,
 919                            SmallPtrSetImpl<const SCEV *> *LoserRegs);
 920 };
 921
 922 }
 923
 924 /// Tally up interesting quantities from the given register.
 925 void Cost::RateRegister(const SCEV *Reg,
 926                         SmallPtrSetImpl<const SCEV *> &Regs,
 927                         const Loop *L,
 928                         ScalarEvolution &SE, DominatorTree &DT) {
 929   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Reg)) {
 930     // If this is an addrec for another loop, don't second-guess its addrec phi
 931     // nodes. LSR isn't currently smart enough to reason about more than one
 932     // loop at a time. LSR has already run on inner loops, will not run on outer
 933     // loops, and cannot be expected to change sibling loops.
 934     if (AR->getLoop() != L) {
 935       // If the AddRec exists, consider it's register free and leave it alone.
 936       if (isExistingPhi(AR, SE))
 937         return;
 938
 939       // Otherwise, do not consider this formula at all.
 940       Lose();
 941       return;
 942     }
 943     AddRecCost += 1; /// TODO: This should be a function of the stride.
 944
 945     // Add the step value register, if it needs one.
 946     // TODO: The non-affine case isn't precisely modeled here.
 947     if (!AR->isAffine() || !isa<SCEVConstant>(AR->getOperand(1))) {
 948       if (!Regs.count(AR->getOperand(1))) {
 949         RateRegister(AR->getOperand(1), Regs, L, SE, DT);
 950         if (isLoser())
 951           return;
 952       }
 953     }
 954   }
 955   ++NumRegs;
 956
 957   // Rough heuristic; favor registers which don't require extra setup
 958   // instructions in the preheader.
 959   if (!isa<SCEVUnknown>(Reg) &&
 960       !isa<SCEVConstant>(Reg) &&
 961       !(isa<SCEVAddRecExpr>(Reg) &&
 962         (isa<SCEVUnknown>(cast<SCEVAddRecExpr>(Reg)->getStart()) ||
 963          isa<SCEVConstant>(cast<SCEVAddRecExpr>(Reg)->getStart()))))
 964     ++SetupCost;
 965
 966     NumIVMuls += isa<SCEVMulExpr>(Reg) &&
 967                  SE.hasComputableLoopEvolution(Reg, L);
 968 }
 969
 970 /// Record this register in the set. If we haven't seen it before, rate
 971 /// it. Optional LoserRegs provides a way to declare any formula that refers to
 972 /// one of those regs an instant loser.
 973 void Cost::RatePrimaryRegister(const SCEV *Reg,
 974                                SmallPtrSetImpl<const SCEV *> &Regs,
 975                                const Loop *L,
 976                                ScalarEvolution &SE, DominatorTree &DT,
 977                                SmallPtrSetImpl<const SCEV *> *LoserRegs) {
 978   if (LoserRegs && LoserRegs->count(Reg)) {
 979     Lose();
 980     return;
 981   }
 982   if (Regs.insert(Reg).second) {
 983     RateRegister(Reg, Regs, L, SE, DT);
 984     if (LoserRegs && isLoser())
 985       LoserRegs->insert(Reg);
 986   }
 987 }
 988
 989 void Cost::RateFormula(const TargetTransformInfo &TTI,
 990                        const Formula &F,
 991                        SmallPtrSetImpl<const SCEV *> &Regs,
 992                        const DenseSet<const SCEV *> &VisitedRegs,
 993                        const Loop *L,
 994                        const SmallVectorImpl<int64_t> &Offsets,
 995                        ScalarEvolution &SE, DominatorTree &DT,
 996                        const LSRUse &LU,
 997                        SmallPtrSetImpl<const SCEV *> *LoserRegs) {
 998   assert(F.isCanonical() && "Cost is accurate only for canonical formula");
 999   // Tally up the registers.
1000   if (const SCEV *ScaledReg = F.ScaledReg) {
1001     if (VisitedRegs.count(ScaledReg)) {
1002       Lose();
1003       return;
1004     }
1005     RatePrimaryRegister(ScaledReg, Regs, L, SE, DT, LoserRegs);
1006     if (isLoser())
1007       return;
1008   }
1009   for (const SCEV *BaseReg : F.BaseRegs) {
1010     if (VisitedRegs.count(BaseReg)) {
1011       Lose();
1012       return;
1013     }
1014     RatePrimaryRegister(BaseReg, Regs, L, SE, DT, LoserRegs);
1015     if (isLoser())
1016       return;
1017   }
1018
1019   // Determine how many (unfolded) adds we'll need inside the loop.
1020   size_t NumBaseParts = F.getNumRegs();
1021   if (NumBaseParts > 1)
1022     // Do not count the base and a possible second register if the target
1023     // allows to fold 2 registers.
1024     NumBaseAdds +=
1025         NumBaseParts - (1 + (F.Scale && isAMCompletelyFolded(TTI, LU, F)));
1026   NumBaseAdds += (F.UnfoldedOffset != 0);
1027
1028   // Accumulate non-free scaling amounts.
1029   ScaleCost += getScalingFactorCost(TTI, LU, F);
1030
1031   // Tally up the non-zero immediates.
1032   for (int64_t O : Offsets) {
1033     int64_t Offset = (uint64_t)O + F.BaseOffset;
1034     if (F.BaseGV)
1035       ImmCost += 64; // Handle symbolic values conservatively.
1036                      // TODO: This should probably be the pointer size.
1037     else if (Offset != 0)
1038       ImmCost += APInt(64, Offset, true).getMinSignedBits();
1039   }
1040   assert(isValid() && "invalid cost");
1041 }
1042
1043 /// Set this cost to a losing value.
1044 void Cost::Lose() {
1045   NumRegs = ~0u;
1046   AddRecCost = ~0u;
1047   NumIVMuls = ~0u;
1048   NumBaseAdds = ~0u;
1049   ImmCost = ~0u;
1050   SetupCost = ~0u;
1051   ScaleCost = ~0u;
1052 }
1053
1054 /// Choose the lower cost.
1055 bool Cost::operator<(const Cost &Other) const {
1056   return std::tie(NumRegs, AddRecCost, NumIVMuls, NumBaseAdds, ScaleCost,
1057                   ImmCost, SetupCost) <
1058          std::tie(Other.NumRegs, Other.AddRecCost, Other.NumIVMuls,
1059                   Other.NumBaseAdds, Other.ScaleCost, Other.ImmCost,
1060                   Other.SetupCost);
1061 }
1062
1063 void Cost::print(raw_ostream &OS) const {
1064   OS << NumRegs << " reg" << (NumRegs == 1 ? "" : "s");
1065   if (AddRecCost != 0)
1066     OS << ", with addrec cost " << AddRecCost;
1067   if (NumIVMuls != 0)
1068     OS << ", plus " << NumIVMuls << " IV mul" << (NumIVMuls == 1 ? "" : "s");
1069   if (NumBaseAdds != 0)
1070     OS << ", plus " << NumBaseAdds << " base add"
1071        << (NumBaseAdds == 1 ? "" : "s");
1072   if (ScaleCost != 0)
1073     OS << ", plus " << ScaleCost << " scale cost";
1074   if (ImmCost != 0)
1075     OS << ", plus " << ImmCost << " imm cost";
1076   if (SetupCost != 0)
1077     OS << ", plus " << SetupCost << " setup cost";
1078 }
1079
1080 LLVM_DUMP_METHOD
1081 void Cost::dump() const {
1082   print(errs()); errs() << '\n';
1083 }
1084
1085 namespace {
1086
1087 /// An operand value in an instruction which is to be replaced with some
1088 /// equivalent, possibly strength-reduced, replacement.
1089 struct LSRFixup {
1090   /// The instruction which will be updated.
1091   Instruction *UserInst;
1092
1093   /// The operand of the instruction which will be replaced. The operand may be
1094   /// used more than once; every instance will be replaced.
1095   Value *OperandValToReplace;
1096
1097   /// If this user is to use the post-incremented value of an induction
1098   /// variable, this variable is non-null and holds the loop associated with the
1099   /// induction variable.
1100   PostIncLoopSet PostIncLoops;
1101
1102   /// The index of the LSRUse describing the expression which this fixup needs,
1103   /// minus an offset (below).
1104   size_t LUIdx;
1105
1106   /// A constant offset to be added to the LSRUse expression.  This allows
1107   /// multiple fixups to share the same LSRUse with different offsets, for
1108   /// example in an unrolled loop.
1109   int64_t Offset;
1110
1111   bool isUseFullyOutsideLoop(const Loop *L) const;
1112
1113   LSRFixup();
1114
1115   void print(raw_ostream &OS) const;
1116   void dump() const;
1117 };
1118
1119 }
1120
1121 LSRFixup::LSRFixup()
1122   : UserInst(nullptr), OperandValToReplace(nullptr), LUIdx(~size_t(0)),
1123     Offset(0) {}
1124
1125 /// Test whether this fixup always uses its value outside of the given loop.
1126 bool LSRFixup::isUseFullyOutsideLoop(const Loop *L) const {
1127   // PHI nodes use their value in their incoming blocks.
1128   if (const PHINode *PN = dyn_cast<PHINode>(UserInst)) {
1129     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1130       if (PN->getIncomingValue(i) == OperandValToReplace &&
1131           L->contains(PN->getIncomingBlock(i)))
1132         return false;
1133     return true;
1134   }
1135
1136   return !L->contains(UserInst);
1137 }
1138
1139 void LSRFixup::print(raw_ostream &OS) const {
1140   OS << "UserInst=";
1141   // Store is common and interesting enough to be worth special-casing.
1142   if (StoreInst *Store = dyn_cast<StoreInst>(UserInst)) {
1143     OS << "store ";
1144     Store->getOperand(0)->printAsOperand(OS, /*PrintType=*/false);
1145   } else if (UserInst->getType()->isVoidTy())
1146     OS << UserInst->getOpcodeName();
1147   else
1148     UserInst->printAsOperand(OS, /*PrintType=*/false);
1149
1150   OS << ", OperandValToReplace=";
1151   OperandValToReplace->printAsOperand(OS, /*PrintType=*/false);
1152
1153   for (const Loop *PIL : PostIncLoops) {
1154     OS << ", PostIncLoop=";
1155     PIL->getHeader()->printAsOperand(OS, /*PrintType=*/false);
1156   }
1157
1158   if (LUIdx != ~size_t(0))
1159     OS << ", LUIdx=" << LUIdx;
1160
1161   if (Offset != 0)
1162     OS << ", Offset=" << Offset;
1163 }
1164
1165 LLVM_DUMP_METHOD
1166 void LSRFixup::dump() const {
1167   print(errs()); errs() << '\n';
1168 }
1169
1170 namespace {
1171
1172 /// A DenseMapInfo implementation for holding DenseMaps and DenseSets of sorted
1173 /// SmallVectors of const SCEV*.
1174 struct UniquifierDenseMapInfo {
1175   static SmallVector<const SCEV *, 4> getEmptyKey() {
1176     SmallVector<const SCEV *, 4>  V;
1177     V.push_back(reinterpret_cast<const SCEV *>(-1));
1178     return V;
1179   }
1180
1181   static SmallVector<const SCEV *, 4> getTombstoneKey() {
1182     SmallVector<const SCEV *, 4> V;
1183     V.push_back(reinterpret_cast<const SCEV *>(-2));
1184     return V;
1185   }
1186
1187   static unsigned getHashValue(const SmallVector<const SCEV *, 4> &V) {
1188     return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
1189   }
1190
1191   static bool isEqual(const SmallVector<const SCEV *, 4> &LHS,
1192                       const SmallVector<const SCEV *, 4> &RHS) {
1193     return LHS == RHS;
1194   }
1195 };
1196
1197 /// This class holds the state that LSR keeps for each use in IVUsers, as well
1198 /// as uses invented by LSR itself. It includes information about what kinds of
1199 /// things can be folded into the user, information about the user itself, and
1200 /// information about how the use may be satisfied.  TODO: Represent multiple
1201 /// users of the same expression in common?
1202 class LSRUse {
1203   DenseSet<SmallVector<const SCEV *, 4>, UniquifierDenseMapInfo> Uniquifier;
1204
1205 public:
1206   /// An enum for a kind of use, indicating what types of scaled and immediate
1207   /// operands it might support.
1208   enum KindType {
1209     Basic,   ///< A normal use, with no folding.
1210     Special, ///< A special case of basic, allowing -1 scales.
1211     Address, ///< An address use; folding according to TargetLowering
1212     ICmpZero ///< An equality icmp with both operands folded into one.
1213     // TODO: Add a generic icmp too?
1214   };
1215
1216   typedef PointerIntPair<const SCEV *, 2, KindType> SCEVUseKindPair;
1217
1218   KindType Kind;
1219   MemAccessTy AccessTy;
1220
1221   SmallVector<int64_t, 8> Offsets;
1222   int64_t MinOffset;
1223   int64_t MaxOffset;
1224
1225   /// This records whether all of the fixups using this LSRUse are outside of
1226   /// the loop, in which case some special-case heuristics may be used.
1227   bool AllFixupsOutsideLoop;
1228
1229   /// RigidFormula is set to true to guarantee that this use will be associated
1230   /// with a single formula--the one that initially matched. Some SCEV
1231   /// expressions cannot be expanded. This allows LSR to consider the registers
1232   /// used by those expressions without the need to expand them later after
1233   /// changing the formula.
1234   bool RigidFormula;
1235
1236   /// This records the widest use type for any fixup using this
1237   /// LSRUse. FindUseWithSimilarFormula can't consider uses with different max
1238   /// fixup widths to be equivalent, because the narrower one may be relying on
1239   /// the implicit truncation to truncate away bogus bits.
1240   Type *WidestFixupType;
1241
1242   /// A list of ways to build a value that can satisfy this user.  After the
1243   /// list is populated, one of these is selected heuristically and used to
1244   /// formulate a replacement for OperandValToReplace in UserInst.
1245   SmallVector<Formula, 12> Formulae;
1246
1247   /// The set of register candidates used by all formulae in this LSRUse.
1248   SmallPtrSet<const SCEV *, 4> Regs;
1249
1250   LSRUse(KindType K, MemAccessTy AT)
1251       : Kind(K), AccessTy(AT), MinOffset(INT64_MAX), MaxOffset(INT64_MIN),
1252         AllFixupsOutsideLoop(true), RigidFormula(false),
1253         WidestFixupType(nullptr) {}
1254
1255   bool HasFormulaWithSameRegs(const Formula &F) const;
1256   bool InsertFormula(const Formula &F);
1257   void DeleteFormula(Formula &F);
1258   void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses);
1259
1260   void print(raw_ostream &OS) const;
1261   void dump() const;
1262 };
1263
1264 }
1265
1266 /// Test whether this use as a formula which has the same registers as the given
1267 /// formula.
1268 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const {
1269   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
1270   if (F.ScaledReg) Key.push_back(F.ScaledReg);
1271   // Unstable sort by host order ok, because this is only used for uniquifying.
1272   std::sort(Key.begin(), Key.end());
1273   return Uniquifier.count(Key);
1274 }
1275
1276 /// If the given formula has not yet been inserted, add it to the list, and
1277 /// return true. Return false otherwise.  The formula must be in canonical form.
1278 bool LSRUse::InsertFormula(const Formula &F) {
1279   assert(F.isCanonical() && "Invalid canonical representation");
1280
1281   if (!Formulae.empty() && RigidFormula)
1282     return false;
1283
1284   SmallVector<const SCEV *, 4> Key = F.BaseRegs;
1285   if (F.ScaledReg) Key.push_back(F.ScaledReg);
1286   // Unstable sort by host order ok, because this is only used for uniquifying.
1287   std::sort(Key.begin(), Key.end());
1288
1289   if (!Uniquifier.insert(Key).second)
1290     return false;
1291
1292   // Using a register to hold the value of 0 is not profitable.
1293   assert((!F.ScaledReg || !F.ScaledReg->isZero()) &&
1294          "Zero allocated in a scaled register!");
1295 #ifndef NDEBUG
1296   for (const SCEV *BaseReg : F.BaseRegs)
1297     assert(!BaseReg->isZero() && "Zero allocated in a base register!");
1298 #endif
1299
1300   // Add the formula to the list.
1301   Formulae.push_back(F);
1302
1303   // Record registers now being used by this use.
1304   Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end());
1305   if (F.ScaledReg)
1306     Regs.insert(F.ScaledReg);
1307
1308   return true;
1309 }
1310
1311 /// Remove the given formula from this use's list.
1312 void LSRUse::DeleteFormula(Formula &F) {
1313   if (&F != &Formulae.back())
1314     std::swap(F, Formulae.back());
1315   Formulae.pop_back();
1316 }
1317
1318 /// Recompute the Regs field, and update RegUses.
1319 void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) {
1320   // Now that we've filtered out some formulae, recompute the Regs set.
1321   SmallPtrSet<const SCEV *, 4> OldRegs = std::move(Regs);
1322   Regs.clear();
1323   for (const Formula &F : Formulae) {
1324     if (F.ScaledReg) Regs.insert(F.ScaledReg);
1325     Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end());
1326   }
1327
1328   // Update the RegTracker.
1329   for (const SCEV *S : OldRegs)
1330     if (!Regs.count(S))
1331       RegUses.dropRegister(S, LUIdx);
1332 }
1333
1334 void LSRUse::print(raw_ostream &OS) const {
1335   OS << "LSR Use: Kind=";
1336   switch (Kind) {
1337   case Basic:    OS << "Basic"; break;
1338   case Special:  OS << "Special"; break;
1339   case ICmpZero: OS << "ICmpZero"; break;
1340   case Address:
1341     OS << "Address of ";
1342     if (AccessTy.MemTy->isPointerTy())
1343       OS << "pointer"; // the full pointer type could be really verbose
1344     else {
1345       OS << *AccessTy.MemTy;
1346     }
1347
1348     OS << " in addrspace(" << AccessTy.AddrSpace << ')';
1349   }
1350
1351   OS << ", Offsets={";
1352   bool NeedComma = false;
1353   for (int64_t O : Offsets) {
1354     if (NeedComma) OS << ',';
1355     OS << O;
1356     NeedComma = true;
1357   }
1358   OS << '}';
1359
1360   if (AllFixupsOutsideLoop)
1361     OS << ", all-fixups-outside-loop";
1362
1363   if (WidestFixupType)
1364     OS << ", widest fixup type: " << *WidestFixupType;
1365 }
1366
1367 LLVM_DUMP_METHOD
1368 void LSRUse::dump() const {
1369   print(errs()); errs() << '\n';
1370 }
1371
1372 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
1373                                  LSRUse::KindType Kind, MemAccessTy AccessTy,
1374                                  GlobalValue *BaseGV, int64_t BaseOffset,
1375                                  bool HasBaseReg, int64_t Scale) {
1376   switch (Kind) {
1377   case LSRUse::Address:
1378     return TTI.isLegalAddressingMode(AccessTy.MemTy, BaseGV, BaseOffset,
1379                                      HasBaseReg, Scale, AccessTy.AddrSpace);
1380
1381   case LSRUse::ICmpZero:
1382     // There's not even a target hook for querying whether it would be legal to
1383     // fold a GV into an ICmp.
1384     if (BaseGV)
1385       return false;
1386
1387     // ICmp only has two operands; don't allow more than two non-trivial parts.
1388     if (Scale != 0 && HasBaseReg && BaseOffset != 0)
1389       return false;
1390
1391     // ICmp only supports no scale or a -1 scale, as we can "fold" a -1 scale by
1392     // putting the scaled register in the other operand of the icmp.
1393     if (Scale != 0 && Scale != -1)
1394       return false;
1395
1396     // If we have low-level target information, ask the target if it can fold an
1397     // integer immediate on an icmp.
1398     if (BaseOffset != 0) {
1399       // We have one of:
1400       // ICmpZero     BaseReg + BaseOffset => ICmp BaseReg, -BaseOffset
1401       // ICmpZero -1*ScaleReg + BaseOffset => ICmp ScaleReg, BaseOffset
1402       // Offs is the ICmp immediate.
1403       if (Scale == 0)
1404         // The cast does the right thing with INT64_MIN.
1405         BaseOffset = -(uint64_t)BaseOffset;
1406       return TTI.isLegalICmpImmediate(BaseOffset);
1407     }
1408
1409     // ICmpZero BaseReg + -1*ScaleReg => ICmp BaseReg, ScaleReg
1410     return true;
1411
1412   case LSRUse::Basic:
1413     // Only handle single-register values.
1414     return !BaseGV && Scale == 0 && BaseOffset == 0;
1415
1416   case LSRUse::Special:
1417     // Special case Basic to handle -1 scales.
1418     return !BaseGV && (Scale == 0 || Scale == -1) && BaseOffset == 0;
1419   }
1420
1421   llvm_unreachable("Invalid LSRUse Kind!");
1422 }
1423
1424 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
1425                                  int64_t MinOffset, int64_t MaxOffset,
1426                                  LSRUse::KindType Kind, MemAccessTy AccessTy,
1427                                  GlobalValue *BaseGV, int64_t BaseOffset,
1428                                  bool HasBaseReg, int64_t Scale) {
1429   // Check for overflow.
1430   if (((int64_t)((uint64_t)BaseOffset + MinOffset) > BaseOffset) !=
1431       (MinOffset > 0))
1432     return false;
1433   MinOffset = (uint64_t)BaseOffset + MinOffset;
1434   if (((int64_t)((uint64_t)BaseOffset + MaxOffset) > BaseOffset) !=
1435       (MaxOffset > 0))
1436     return false;
1437   MaxOffset = (uint64_t)BaseOffset + MaxOffset;
1438
1439   return isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, MinOffset,
1440                               HasBaseReg, Scale) &&
1441          isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, MaxOffset,
1442                               HasBaseReg, Scale);
1443 }
1444
1445 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
1446                                  int64_t MinOffset, int64_t MaxOffset,
1447                                  LSRUse::KindType Kind, MemAccessTy AccessTy,
1448                                  const Formula &F) {
1449   // For the purpose of isAMCompletelyFolded either having a canonical formula
1450   // or a scale not equal to zero is correct.
1451   // Problems may arise from non canonical formulae having a scale == 0.
1452   // Strictly speaking it would best to just rely on canonical formulae.
1453   // However, when we generate the scaled formulae, we first check that the
1454   // scaling factor is profitable before computing the actual ScaledReg for
1455   // compile time sake.
1456   assert((F.isCanonical() || F.Scale != 0));
1457   return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy,
1458                               F.BaseGV, F.BaseOffset, F.HasBaseReg, F.Scale);
1459 }
1460
1461 /// Test whether we know how to expand the current formula.
1462 static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset,
1463                        int64_t MaxOffset, LSRUse::KindType Kind,
1464                        MemAccessTy AccessTy, GlobalValue *BaseGV,
1465                        int64_t BaseOffset, bool HasBaseReg, int64_t Scale) {
1466   // We know how to expand completely foldable formulae.
1467   return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, BaseGV,
1468                               BaseOffset, HasBaseReg, Scale) ||
1469          // Or formulae that use a base register produced by a sum of base
1470          // registers.
1471          (Scale == 1 &&
1472           isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy,
1473                                BaseGV, BaseOffset, true, 0));
1474 }
1475
1476 static bool isLegalUse(const TargetTransformInfo &TTI, int64_t MinOffset,
1477                        int64_t MaxOffset, LSRUse::KindType Kind,
1478                        MemAccessTy AccessTy, const Formula &F) {
1479   return isLegalUse(TTI, MinOffset, MaxOffset, Kind, AccessTy, F.BaseGV,
1480                     F.BaseOffset, F.HasBaseReg, F.Scale);
1481 }
1482
1483 static bool isAMCompletelyFolded(const TargetTransformInfo &TTI,
1484                                  const LSRUse &LU, const Formula &F) {
1485   return isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind,
1486                               LU.AccessTy, F.BaseGV, F.BaseOffset, F.HasBaseReg,
1487                               F.Scale);
1488 }
1489
1490 static unsigned getScalingFactorCost(const TargetTransformInfo &TTI,
1491                                      const LSRUse &LU, const Formula &F) {
1492   if (!F.Scale)
1493     return 0;
1494
1495   // If the use is not completely folded in that instruction, we will have to
1496   // pay an extra cost only for scale != 1.
1497   if (!isAMCompletelyFolded(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind,
1498                             LU.AccessTy, F))
1499     return F.Scale != 1;
1500
1501   switch (LU.Kind) {
1502   case LSRUse::Address: {
1503     // Check the scaling factor cost with both the min and max offsets.
1504     int ScaleCostMinOffset = TTI.getScalingFactorCost(
1505         LU.AccessTy.MemTy, F.BaseGV, F.BaseOffset + LU.MinOffset, F.HasBaseReg,
1506         F.Scale, LU.AccessTy.AddrSpace);
1507     int ScaleCostMaxOffset = TTI.getScalingFactorCost(
1508         LU.AccessTy.MemTy, F.BaseGV, F.BaseOffset + LU.MaxOffset, F.HasBaseReg,
1509         F.Scale, LU.AccessTy.AddrSpace);
1510
1511     assert(ScaleCostMinOffset >= 0 && ScaleCostMaxOffset >= 0 &&
1512            "Legal addressing mode has an illegal cost!");
1513     return std::max(ScaleCostMinOffset, ScaleCostMaxOffset);
1514   }
1515   case LSRUse::ICmpZero:
1516   case LSRUse::Basic:
1517   case LSRUse::Special:
1518     // The use is completely folded, i.e., everything is folded into the
1519     // instruction.
1520     return 0;
1521   }
1522
1523   llvm_unreachable("Invalid LSRUse Kind!");
1524 }
1525
1526 static bool isAlwaysFoldable(const TargetTransformInfo &TTI,
1527                              LSRUse::KindType Kind, MemAccessTy AccessTy,
1528                              GlobalValue *BaseGV, int64_t BaseOffset,
1529                              bool HasBaseReg) {
1530   // Fast-path: zero is always foldable.
1531   if (BaseOffset == 0 && !BaseGV) return true;
1532
1533   // Conservatively, create an address with an immediate and a
1534   // base and a scale.
1535   int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1;
1536
1537   // Canonicalize a scale of 1 to a base register if the formula doesn't
1538   // already have a base register.
1539   if (!HasBaseReg && Scale == 1) {
1540     Scale = 0;
1541     HasBaseReg = true;
1542   }
1543
1544   return isAMCompletelyFolded(TTI, Kind, AccessTy, BaseGV, BaseOffset,
1545                               HasBaseReg, Scale);
1546 }
1547
1548 static bool isAlwaysFoldable(const TargetTransformInfo &TTI,
1549                              ScalarEvolution &SE, int64_t MinOffset,
1550                              int64_t MaxOffset, LSRUse::KindType Kind,
1551                              MemAccessTy AccessTy, const SCEV *S,
1552                              bool HasBaseReg) {
1553   // Fast-path: zero is always foldable.
1554   if (S->isZero()) return true;
1555
1556   // Conservatively, create an address with an immediate and a
1557   // base and a scale.
1558   int64_t BaseOffset = ExtractImmediate(S, SE);
1559   GlobalValue *BaseGV = ExtractSymbol(S, SE);
1560
1561   // If there's anything else involved, it's not foldable.
1562   if (!S->isZero()) return false;
1563
1564   // Fast-path: zero is always foldable.
1565   if (BaseOffset == 0 && !BaseGV) return true;
1566
1567   // Conservatively, create an address with an immediate and a
1568   // base and a scale.
1569   int64_t Scale = Kind == LSRUse::ICmpZero ? -1 : 1;
1570
1571   return isAMCompletelyFolded(TTI, MinOffset, MaxOffset, Kind, AccessTy, BaseGV,
1572                               BaseOffset, HasBaseReg, Scale);
1573 }
1574
1575 namespace {
1576
1577 /// An individual increment in a Chain of IV increments.  Relate an IV user to
1578 /// an expression that computes the IV it uses from the IV used by the previous
1579 /// link in the Chain.
1580 ///
1581 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the
1582 /// original IVOperand. The head of the chain's IVOperand is only valid during
1583 /// chain collection, before LSR replaces IV users. During chain generation,
1584 /// IncExpr can be used to find the new IVOperand that computes the same
1585 /// expression.
1586 struct IVInc {
1587   Instruction *UserInst;
1588   Value* IVOperand;
1589   const SCEV *IncExpr;
1590
1591   IVInc(Instruction *U, Value *O, const SCEV *E):
1592     UserInst(U), IVOperand(O), IncExpr(E) {}
1593 };
1594
1595 // The list of IV increments in program order.  We typically add the head of a
1596 // chain without finding subsequent links.
1597 struct IVChain {
1598   SmallVector<IVInc,1> Incs;
1599   const SCEV *ExprBase;
1600
1601   IVChain() : ExprBase(nullptr) {}
1602
1603   IVChain(const IVInc &Head, const SCEV *Base)
1604     : Incs(1, Head), ExprBase(Base) {}
1605
1606   typedef SmallVectorImpl<IVInc>::const_iterator const_iterator;
1607
1608   // Return the first increment in the chain.
1609   const_iterator begin() const {
1610     assert(!Incs.empty());
1611     return std::next(Incs.begin());
1612   }
1613   const_iterator end() const {
1614     return Incs.end();
1615   }
1616
1617   // Returns true if this chain contains any increments.
1618   bool hasIncs() const { return Incs.size() >= 2; }
1619
1620   // Add an IVInc to the end of this chain.
1621   void add(const IVInc &X) { Incs.push_back(X); }
1622
1623   // Returns the last UserInst in the chain.
1624   Instruction *tailUserInst() const { return Incs.back().UserInst; }
1625
1626   // Returns true if IncExpr can be profitably added to this chain.
1627   bool isProfitableIncrement(const SCEV *OperExpr,
1628                              const SCEV *IncExpr,
1629                              ScalarEvolution&);
1630 };
1631
1632 /// Helper for CollectChains to track multiple IV increment uses.  Distinguish
1633 /// between FarUsers that definitely cross IV increments and NearUsers that may
1634 /// be used between IV increments.
1635 struct ChainUsers {
1636   SmallPtrSet<Instruction*, 4> FarUsers;
1637   SmallPtrSet<Instruction*, 4> NearUsers;
1638 };
1639
1640 /// This class holds state for the main loop strength reduction logic.
1641 class LSRInstance {
1642   IVUsers &IU;
1643   ScalarEvolution &SE;
1644   DominatorTree &DT;
1645   LoopInfo &LI;
1646   const TargetTransformInfo &TTI;
1647   Loop *const L;
1648   bool Changed;
1649
1650   /// This is the insert position that the current loop's induction variable
1651   /// increment should be placed. In simple loops, this is the latch block's
1652   /// terminator. But in more complicated cases, this is a position which will
1653   /// dominate all the in-loop post-increment users.
1654   Instruction *IVIncInsertPos;
1655
1656   /// Interesting factors between use strides.
1657   SmallSetVector<int64_t, 8> Factors;
1658
1659   /// Interesting use types, to facilitate truncation reuse.
1660   SmallSetVector<Type *, 4> Types;
1661
1662   /// The list of operands which are to be replaced.
1663   SmallVector<LSRFixup, 16> Fixups;
1664
1665   /// The list of interesting uses.
1666   SmallVector<LSRUse, 16> Uses;
1667
1668   /// Track which uses use which register candidates.
1669   RegUseTracker RegUses;
1670
1671   // Limit the number of chains to avoid quadratic behavior. We don't expect to
1672   // have more than a few IV increment chains in a loop. Missing a Chain falls
1673   // back to normal LSR behavior for those uses.
1674   static const unsigned MaxChains = 8;
1675
1676   /// IV users can form a chain of IV increments.
1677   SmallVector<IVChain, MaxChains> IVChainVec;
1678
1679   /// IV users that belong to profitable IVChains.
1680   SmallPtrSet<Use*, MaxChains> IVIncSet;
1681
1682   void OptimizeShadowIV();
1683   bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse);
1684   ICmpInst *OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse);
1685   void OptimizeLoopTermCond();
1686
1687   void ChainInstruction(Instruction *UserInst, Instruction *IVOper,
1688                         SmallVectorImpl<ChainUsers> &ChainUsersVec);
1689   void FinalizeChain(IVChain &Chain);
1690   void CollectChains();
1691   void GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter,
1692                        SmallVectorImpl<WeakVH> &DeadInsts);
1693
1694   void CollectInterestingTypesAndFactors();
1695   void CollectFixupsAndInitialFormulae();
1696
1697   LSRFixup &getNewFixup() {
1698     Fixups.push_back(LSRFixup());
1699     return Fixups.back();
1700   }
1701
1702   // Support for sharing of LSRUses between LSRFixups.
1703   typedef DenseMap<LSRUse::SCEVUseKindPair, size_t> UseMapTy;
1704   UseMapTy UseMap;
1705
1706   bool reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg,
1707                           LSRUse::KindType Kind, MemAccessTy AccessTy);
1708
1709   std::pair<size_t, int64_t> getUse(const SCEV *&Expr, LSRUse::KindType Kind,
1710                                     MemAccessTy AccessTy);
1711
1712   void DeleteUse(LSRUse &LU, size_t LUIdx);
1713
1714   LSRUse *FindUseWithSimilarFormula(const Formula &F, const LSRUse &OrigLU);
1715
1716   void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1717   void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1718   void CountRegisters(const Formula &F, size_t LUIdx);
1719   bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F);
1720
1721   void CollectLoopInvariantFixupsAndFormulae();
1722
1723   void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base,
1724                               unsigned Depth = 0);
1725
1726   void GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx,
1727                                   const Formula &Base, unsigned Depth,
1728                                   size_t Idx, bool IsScaledReg = false);
1729   void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base);
1730   void GenerateSymbolicOffsetsImpl(LSRUse &LU, unsigned LUIdx,
1731                                    const Formula &Base, size_t Idx,
1732                                    bool IsScaledReg = false);
1733   void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
1734   void GenerateConstantOffsetsImpl(LSRUse &LU, unsigned LUIdx,
1735                                    const Formula &Base,
1736                                    const SmallVectorImpl<int64_t> &Worklist,
1737                                    size_t Idx, bool IsScaledReg = false);
1738   void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
1739   void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base);
1740   void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base);
1741   void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base);
1742   void GenerateCrossUseConstantOffsets();
1743   void GenerateAllReuseFormulae();
1744
1745   void FilterOutUndesirableDedicatedRegisters();
1746
1747   size_t EstimateSearchSpaceComplexity() const;
1748   void NarrowSearchSpaceByDetectingSupersets();
1749   void NarrowSearchSpaceByCollapsingUnrolledCode();
1750   void NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
1751   void NarrowSearchSpaceByPickingWinnerRegs();
1752   void NarrowSearchSpaceUsingHeuristics();
1753
1754   void SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
1755                     Cost &SolutionCost,
1756                     SmallVectorImpl<const Formula *> &Workspace,
1757                     const Cost &CurCost,
1758                     const SmallPtrSet<const SCEV *, 16> &CurRegs,
1759                     DenseSet<const SCEV *> &VisitedRegs) const;
1760   void Solve(SmallVectorImpl<const Formula *> &Solution) const;
1761
1762   BasicBlock::iterator
1763     HoistInsertPosition(BasicBlock::iterator IP,
1764                         const SmallVectorImpl<Instruction *> &Inputs) const;
1765   BasicBlock::iterator
1766     AdjustInsertPositionForExpand(BasicBlock::iterator IP,
1767                                   const LSRFixup &LF,
1768                                   const LSRUse &LU,
1769                                   SCEVExpander &Rewriter) const;
1770
1771   Value *Expand(const LSRFixup &LF,
1772                 const Formula &F,
1773                 BasicBlock::iterator IP,
1774                 SCEVExpander &Rewriter,
1775                 SmallVectorImpl<WeakVH> &DeadInsts) const;
1776   void RewriteForPHI(PHINode *PN, const LSRFixup &LF,
1777                      const Formula &F,
1778                      SCEVExpander &Rewriter,
1779                      SmallVectorImpl<WeakVH> &DeadInsts) const;
1780   void Rewrite(const LSRFixup &LF,
1781                const Formula &F,
1782                SCEVExpander &Rewriter,
1783                SmallVectorImpl<WeakVH> &DeadInsts) const;
1784   void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution);
1785
1786 public:
1787   LSRInstance(Loop *L, IVUsers &IU, ScalarEvolution &SE, DominatorTree &DT,
1788               LoopInfo &LI, const TargetTransformInfo &TTI);
1789
1790   bool getChanged() const { return Changed; }
1791
1792   void print_factors_and_types(raw_ostream &OS) const;
1793   void print_fixups(raw_ostream &OS) const;
1794   void print_uses(raw_ostream &OS) const;
1795   void print(raw_ostream &OS) const;
1796   void dump() const;
1797 };
1798
1799 }
1800
1801 /// If IV is used in a int-to-float cast inside the loop then try to eliminate
1802 /// the cast operation.
1803 void LSRInstance::OptimizeShadowIV() {
1804   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
1805   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount))
1806     return;
1807
1808   for (IVUsers::const_iterator UI = IU.begin(), E = IU.end();
1809        UI != E; /* empty */) {
1810     IVUsers::const_iterator CandidateUI = UI;
1811     ++UI;
1812     Instruction *ShadowUse = CandidateUI->getUser();
1813     Type *DestTy = nullptr;
1814     bool IsSigned = false;
1815
1816     /* If shadow use is a int->float cast then insert a second IV
1817        to eliminate this cast.
1818
1819          for (unsigned i = 0; i < n; ++i)
1820            foo((double)i);
1821
1822        is transformed into
1823
1824          double d = 0.0;
1825          for (unsigned i = 0; i < n; ++i, ++d)
1826            foo(d);
1827     */
1828     if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) {
1829       IsSigned = false;
1830       DestTy = UCast->getDestTy();
1831     }
1832     else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) {
1833       IsSigned = true;
1834       DestTy = SCast->getDestTy();
1835     }
1836     if (!DestTy) continue;
1837
1838     // If target does not support DestTy natively then do not apply
1839     // this transformation.
1840     if (!TTI.isTypeLegal(DestTy)) continue;
1841
1842     PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0));
1843     if (!PH) continue;
1844     if (PH->getNumIncomingValues() != 2) continue;
1845
1846     Type *SrcTy = PH->getType();
1847     int Mantissa = DestTy->getFPMantissaWidth();
1848     if (Mantissa == -1) continue;
1849     if ((int)SE.getTypeSizeInBits(SrcTy) > Mantissa)
1850       continue;
1851
1852     unsigned Entry, Latch;
1853     if (PH->getIncomingBlock(0) == L->getLoopPreheader()) {
1854       Entry = 0;
1855       Latch = 1;
1856     } else {
1857       Entry = 1;
1858       Latch = 0;
1859     }
1860
1861     ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry));
1862     if (!Init) continue;
1863     Constant *NewInit = ConstantFP::get(DestTy, IsSigned ?
1864                                         (double)Init->getSExtValue() :
1865                                         (double)Init->getZExtValue());
1866
1867     BinaryOperator *Incr =
1868       dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch));
1869     if (!Incr) continue;
1870     if (Incr->getOpcode() != Instruction::Add
1871         && Incr->getOpcode() != Instruction::Sub)
1872       continue;
1873
1874     /* Initialize new IV, double d = 0.0 in above example. */
1875     ConstantInt *C = nullptr;
1876     if (Incr->getOperand(0) == PH)
1877       C = dyn_cast<ConstantInt>(Incr->getOperand(1));
1878     else if (Incr->getOperand(1) == PH)
1879       C = dyn_cast<ConstantInt>(Incr->getOperand(0));
1880     else
1881       continue;
1882
1883     if (!C) continue;
1884
1885     // Ignore negative constants, as the code below doesn't handle them
1886     // correctly. TODO: Remove this restriction.
1887     if (!C->getValue().isStrictlyPositive()) continue;
1888
1889     /* Add new PHINode. */
1890     PHINode *NewPH = PHINode::Create(DestTy, 2, "IV.S.", PH);
1891
1892     /* create new increment. '++d' in above example. */
1893     Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue());
1894     BinaryOperator *NewIncr =
1895       BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ?
1896                                Instruction::FAdd : Instruction::FSub,
1897                              NewPH, CFP, "IV.S.next.", Incr);
1898
1899     NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry));
1900     NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch));
1901
1902     /* Remove cast operation */
1903     ShadowUse->replaceAllUsesWith(NewPH);
1904     ShadowUse->eraseFromParent();
1905     Changed = true;
1906     break;
1907   }
1908 }
1909
1910 /// If Cond has an operand that is an expression of an IV, set the IV user and
1911 /// stride information and return true, otherwise return false.
1912 bool LSRInstance::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse) {
1913   for (IVStrideUse &U : IU)
1914     if (U.getUser() == Cond) {
1915       // NOTE: we could handle setcc instructions with multiple uses here, but
1916       // InstCombine does it as well for simple uses, it's not clear that it
1917       // occurs enough in real life to handle.
1918       CondUse = &U;
1919       return true;
1920     }
1921   return false;
1922 }
1923
1924 /// Rewrite the loop's terminating condition if it uses a max computation.
1925 ///
1926 /// This is a narrow solution to a specific, but acute, problem. For loops
1927 /// like this:
1928 ///
1929 ///   i = 0;
1930 ///   do {
1931 ///     p[i] = 0.0;
1932 ///   } while (++i < n);
1933 ///
1934 /// the trip count isn't just 'n', because 'n' might not be positive. And
1935 /// unfortunately this can come up even for loops where the user didn't use
1936 /// a C do-while loop. For example, seemingly well-behaved top-test loops
1937 /// will commonly be lowered like this:
1938 //
1939 ///   if (n > 0) {
1940 ///     i = 0;
1941 ///     do {
1942 ///       p[i] = 0.0;
1943 ///     } while (++i < n);
1944 ///   }
1945 ///
1946 /// and then it's possible for subsequent optimization to obscure the if
1947 /// test in such a way that indvars can't find it.
1948 ///
1949 /// When indvars can't find the if test in loops like this, it creates a
1950 /// max expression, which allows it to give the loop a canonical
1951 /// induction variable:
1952 ///
1953 ///   i = 0;
1954 ///   max = n < 1 ? 1 : n;
1955 ///   do {
1956 ///     p[i] = 0.0;
1957 ///   } while (++i != max);
1958 ///
1959 /// Canonical induction variables are necessary because the loop passes
1960 /// are designed around them. The most obvious example of this is the
1961 /// LoopInfo analysis, which doesn't remember trip count values. It
1962 /// expects to be able to rediscover the trip count each time it is
1963 /// needed, and it does this using a simple analysis that only succeeds if
1964 /// the loop has a canonical induction variable.
1965 ///
1966 /// However, when it comes time to generate code, the maximum operation
1967 /// can be quite costly, especially if it's inside of an outer loop.
1968 ///
1969 /// This function solves this problem by detecting this type of loop and
1970 /// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting
1971 /// the instructions for the maximum computation.
1972 ///
1973 ICmpInst *LSRInstance::OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse) {
1974   // Check that the loop matches the pattern we're looking for.
1975   if (Cond->getPredicate() != CmpInst::ICMP_EQ &&
1976       Cond->getPredicate() != CmpInst::ICMP_NE)
1977     return Cond;
1978
1979   SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1));
1980   if (!Sel || !Sel->hasOneUse()) return Cond;
1981
1982   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
1983   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount))
1984     return Cond;
1985   const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1);
1986
1987   // Add one to the backedge-taken count to get the trip count.
1988   const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount);
1989   if (IterationCount != SE.getSCEV(Sel)) return Cond;
1990
1991   // Check for a max calculation that matches the pattern. There's no check
1992   // for ICMP_ULE here because the comparison would be with zero, which
1993   // isn't interesting.
1994   CmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
1995   const SCEVNAryExpr *Max = nullptr;
1996   if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(BackedgeTakenCount)) {
1997     Pred = ICmpInst::ICMP_SLE;
1998     Max = S;
1999   } else if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(IterationCount)) {
2000     Pred = ICmpInst::ICMP_SLT;
2001     Max = S;
2002   } else if (const SCEVUMaxExpr *U = dyn_cast<SCEVUMaxExpr>(IterationCount)) {
2003     Pred = ICmpInst::ICMP_ULT;
2004     Max = U;
2005   } else {
2006     // No match; bail.
2007     return Cond;
2008   }
2009
2010   // To handle a max with more than two operands, this optimization would
2011   // require additional checking and setup.
2012   if (Max->getNumOperands() != 2)
2013     return Cond;
2014
2015   const SCEV *MaxLHS = Max->getOperand(0);
2016   const SCEV *MaxRHS = Max->getOperand(1);
2017
2018   // ScalarEvolution canonicalizes constants to the left. For < and >, look
2019   // for a comparison with 1. For <= and >=, a comparison with zero.
2020   if (!MaxLHS ||
2021       (ICmpInst::isTrueWhenEqual(Pred) ? !MaxLHS->isZero() : (MaxLHS != One)))
2022     return Cond;
2023
2024   // Check the relevant induction variable for conformance to
2025   // the pattern.
2026   const SCEV *IV = SE.getSCEV(Cond->getOperand(0));
2027   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV);
2028   if (!AR || !AR->isAffine() ||
2029       AR->getStart() != One ||
2030       AR->getStepRecurrence(SE) != One)
2031     return Cond;
2032
2033   assert(AR->getLoop() == L &&
2034          "Loop condition operand is an addrec in a different loop!");
2035
2036   // Check the right operand of the select, and remember it, as it will
2037   // be used in the new comparison instruction.
2038   Value *NewRHS = nullptr;
2039   if (ICmpInst::isTrueWhenEqual(Pred)) {
2040     // Look for n+1, and grab n.
2041     if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(1)))
2042       if (ConstantInt *BO1 = dyn_cast<ConstantInt>(BO->getOperand(1)))
2043          if (BO1->isOne() && SE.getSCEV(BO->getOperand(0)) == MaxRHS)
2044            NewRHS = BO->getOperand(0);
2045     if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(2)))
2046       if (ConstantInt *BO1 = dyn_cast<ConstantInt>(BO->getOperand(1)))
2047         if (BO1->isOne() && SE.getSCEV(BO->getOperand(0)) == MaxRHS)
2048           NewRHS = BO->getOperand(0);
2049     if (!NewRHS)
2050       return Cond;
2051   } else if (SE.getSCEV(Sel->getOperand(1)) == MaxRHS)
2052     NewRHS = Sel->getOperand(1);
2053   else if (SE.getSCEV(Sel->getOperand(2)) == MaxRHS)
2054     NewRHS = Sel->getOperand(2);
2055   else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(MaxRHS))
2056     NewRHS = SU->getValue();
2057   else
2058     // Max doesn't match expected pattern.
2059     return Cond;
2060
2061   // Determine the new comparison opcode. It may be signed or unsigned,
2062   // and the original comparison may be either equality or inequality.
2063   if (Cond->getPredicate() == CmpInst::ICMP_EQ)
2064     Pred = CmpInst::getInversePredicate(Pred);
2065
2066   // Ok, everything looks ok to change the condition into an SLT or SGE and
2067   // delete the max calculation.
2068   ICmpInst *NewCond =
2069     new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp");
2070
2071   // Delete the max calculation instructions.
2072   Cond->replaceAllUsesWith(NewCond);
2073   CondUse->setUser(NewCond);
2074   Instruction *Cmp = cast<Instruction>(Sel->getOperand(0));
2075   Cond->eraseFromParent();
2076   Sel->eraseFromParent();
2077   if (Cmp->use_empty())
2078     Cmp->eraseFromParent();
2079   return NewCond;
2080 }
2081
2082 /// Change loop terminating condition to use the postinc iv when possible.
2083 void
2084 LSRInstance::OptimizeLoopTermCond() {
2085   SmallPtrSet<Instruction *, 4> PostIncs;
2086
2087   BasicBlock *LatchBlock = L->getLoopLatch();
2088   SmallVector<BasicBlock*, 8> ExitingBlocks;
2089   L->getExitingBlocks(ExitingBlocks);
2090
2091   for (BasicBlock *ExitingBlock : ExitingBlocks) {
2092
2093     // Get the terminating condition for the loop if possible.  If we
2094     // can, we want to change it to use a post-incremented version of its
2095     // induction variable, to allow coalescing the live ranges for the IV into
2096     // one register value.
2097
2098     BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
2099     if (!TermBr)
2100       continue;
2101     // FIXME: Overly conservative, termination condition could be an 'or' etc..
2102     if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition()))
2103       continue;
2104
2105     // Search IVUsesByStride to find Cond's IVUse if there is one.
2106     IVStrideUse *CondUse = nullptr;
2107     ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition());
2108     if (!FindIVUserForCond(Cond, CondUse))
2109       continue;
2110
2111     // If the trip count is computed in terms of a max (due to ScalarEvolution
2112     // being unable to find a sufficient guard, for example), change the loop
2113     // comparison to use SLT or ULT instead of NE.
2114     // One consequence of doing this now is that it disrupts the count-down
2115     // optimization. That's not always a bad thing though, because in such
2116     // cases it may still be worthwhile to avoid a max.
2117     Cond = OptimizeMax(Cond, CondUse);
2118
2119     // If this exiting block dominates the latch block, it may also use
2120     // the post-inc value if it won't be shared with other uses.
2121     // Check for dominance.
2122     if (!DT.dominates(ExitingBlock, LatchBlock))
2123       continue;
2124
2125     // Conservatively avoid trying to use the post-inc value in non-latch
2126     // exits if there may be pre-inc users in intervening blocks.
2127     if (LatchBlock != ExitingBlock)
2128       for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI)
2129         // Test if the use is reachable from the exiting block. This dominator
2130         // query is a conservative approximation of reachability.
2131         if (&*UI != CondUse &&
2132             !DT.properlyDominates(UI->getUser()->getParent(), ExitingBlock)) {
2133           // Conservatively assume there may be reuse if the quotient of their
2134           // strides could be a legal scale.
2135           const SCEV *A = IU.getStride(*CondUse, L);
2136           const SCEV *B = IU.getStride(*UI, L);
2137           if (!A || !B) continue;
2138           if (SE.getTypeSizeInBits(A->getType()) !=
2139               SE.getTypeSizeInBits(B->getType())) {
2140             if (SE.getTypeSizeInBits(A->getType()) >
2141                 SE.getTypeSizeInBits(B->getType()))
2142               B = SE.getSignExtendExpr(B, A->getType());
2143             else
2144               A = SE.getSignExtendExpr(A, B->getType());
2145           }
2146           if (const SCEVConstant *D =
2147                 dyn_cast_or_null<SCEVConstant>(getExactSDiv(B, A, SE))) {
2148             const ConstantInt *C = D->getValue();
2149             // Stride of one or negative one can have reuse with non-addresses.
2150             if (C->isOne() || C->isAllOnesValue())
2151               goto decline_post_inc;
2152             // Avoid weird situations.
2153             if (C->getValue().getMinSignedBits() >= 64 ||
2154                 C->getValue().isMinSignedValue())
2155               goto decline_post_inc;
2156             // Check for possible scaled-address reuse.
2157             MemAccessTy AccessTy = getAccessType(UI->getUser());
2158             int64_t Scale = C->getSExtValue();
2159             if (TTI.isLegalAddressingMode(AccessTy.MemTy, /*BaseGV=*/nullptr,
2160                                           /*BaseOffset=*/0,
2161                                           /*HasBaseReg=*/false, Scale,
2162                                           AccessTy.AddrSpace))
2163               goto decline_post_inc;
2164             Scale = -Scale;
2165             if (TTI.isLegalAddressingMode(AccessTy.MemTy, /*BaseGV=*/nullptr,
2166                                           /*BaseOffset=*/0,
2167                                           /*HasBaseReg=*/false, Scale,
2168                                           AccessTy.AddrSpace))
2169               goto decline_post_inc;
2170           }
2171         }
2172
2173     DEBUG(dbgs() << "  Change loop exiting icmp to use postinc iv: "
2174                  << *Cond << '\n');
2175
2176     // It's possible for the setcc instruction to be anywhere in the loop, and
2177     // possible for it to have multiple users.  If it is not immediately before
2178     // the exiting block branch, move it.
2179     if (&*++BasicBlock::iterator(Cond) != TermBr) {
2180       if (Cond->hasOneUse()) {
2181         Cond->moveBefore(TermBr);
2182       } else {
2183         // Clone the terminating condition and insert into the loopend.
2184         ICmpInst *OldCond = Cond;
2185         Cond = cast<ICmpInst>(Cond->clone());
2186         Cond->setName(L->getHeader()->getName() + ".termcond");
2187         ExitingBlock->getInstList().insert(TermBr->getIterator(), Cond);
2188
2189         // Clone the IVUse, as the old use still exists!
2190         CondUse = &IU.AddUser(Cond, CondUse->getOperandValToReplace());
2191         TermBr->replaceUsesOfWith(OldCond, Cond);
2192       }
2193     }
2194
2195     // If we get to here, we know that we can transform the setcc instruction to
2196     // use the post-incremented version of the IV, allowing us to coalesce the
2197     // live ranges for the IV correctly.
2198     CondUse->transformToPostInc(L);
2199     Changed = true;
2200
2201     PostIncs.insert(Cond);
2202   decline_post_inc:;
2203   }
2204
2205   // Determine an insertion point for the loop induction variable increment. It
2206   // must dominate all the post-inc comparisons we just set up, and it must
2207   // dominate the loop latch edge.
2208   IVIncInsertPos = L->getLoopLatch()->getTerminator();
2209   for (Instruction *Inst : PostIncs) {
2210     BasicBlock *BB =
2211       DT.findNearestCommonDominator(IVIncInsertPos->getParent(),
2212                                     Inst->getParent());
2213     if (BB == Inst->getParent())
2214       IVIncInsertPos = Inst;
2215     else if (BB != IVIncInsertPos->getParent())
2216       IVIncInsertPos = BB->getTerminator();
2217   }
2218 }
2219
2220 /// Determine if the given use can accommodate a fixup at the given offset and
2221 /// other details. If so, update the use and return true.
2222 bool LSRInstance::reconcileNewOffset(LSRUse &LU, int64_t NewOffset,
2223                                      bool HasBaseReg, LSRUse::KindType Kind,
2224                                      MemAccessTy AccessTy) {
2225   int64_t NewMinOffset = LU.MinOffset;
2226   int64_t NewMaxOffset = LU.MaxOffset;
2227   MemAccessTy NewAccessTy = AccessTy;
2228
2229   // Check for a mismatched kind. It's tempting to collapse mismatched kinds to
2230   // something conservative, however this can pessimize in the case that one of
2231   // the uses will have all its uses outside the loop, for example.
2232   if (LU.Kind != Kind)
2233     return false;
2234
2235   // Check for a mismatched access type, and fall back conservatively as needed.
2236   // TODO: Be less conservative when the type is similar and can use the same
2237   // addressing modes.
2238   if (Kind == LSRUse::Address) {
2239     if (AccessTy != LU.AccessTy)
2240       NewAccessTy = MemAccessTy::getUnknown(AccessTy.MemTy->getContext());
2241   }
2242
2243   // Conservatively assume HasBaseReg is true for now.
2244   if (NewOffset < LU.MinOffset) {
2245     if (!isAlwaysFoldable(TTI, Kind, NewAccessTy, /*BaseGV=*/nullptr,
2246                           LU.MaxOffset - NewOffset, HasBaseReg))
2247       return false;
2248     NewMinOffset = NewOffset;
2249   } else if (NewOffset > LU.MaxOffset) {
2250     if (!isAlwaysFoldable(TTI, Kind, NewAccessTy, /*BaseGV=*/nullptr,
2251                           NewOffset - LU.MinOffset, HasBaseReg))
2252       return false;
2253     NewMaxOffset = NewOffset;
2254   }
2255
2256   // Update the use.
2257   LU.MinOffset = NewMinOffset;
2258   LU.MaxOffset = NewMaxOffset;
2259   LU.AccessTy = NewAccessTy;
2260   if (NewOffset != LU.Offsets.back())
2261     LU.Offsets.push_back(NewOffset);
2262   return true;
2263 }
2264
2265 /// Return an LSRUse index and an offset value for a fixup which needs the given
2266 /// expression, with the given kind and optional access type.  Either reuse an
2267 /// existing use or create a new one, as needed.
2268 std::pair<size_t, int64_t> LSRInstance::getUse(const SCEV *&Expr,
2269                                                LSRUse::KindType Kind,
2270                                                MemAccessTy AccessTy) {
2271   const SCEV *Copy = Expr;
2272   int64_t Offset = ExtractImmediate(Expr, SE);
2273
2274   // Basic uses can't accept any offset, for example.
2275   if (!isAlwaysFoldable(TTI, Kind, AccessTy, /*BaseGV=*/ nullptr,
2276                         Offset, /*HasBaseReg=*/ true)) {
2277     Expr = Copy;
2278     Offset = 0;
2279   }
2280
2281   std::pair<UseMapTy::iterator, bool> P =
2282     UseMap.insert(std::make_pair(LSRUse::SCEVUseKindPair(Expr, Kind), 0));
2283   if (!P.second) {
2284     // A use already existed with this base.
2285     size_t LUIdx = P.first->second;
2286     LSRUse &LU = Uses[LUIdx];
2287     if (reconcileNewOffset(LU, Offset, /*HasBaseReg=*/true, Kind, AccessTy))
2288       // Reuse this use.
2289       return std::make_pair(LUIdx, Offset);
2290   }
2291
2292   // Create a new use.
2293   size_t LUIdx = Uses.size();
2294   P.first->second = LUIdx;
2295   Uses.push_back(LSRUse(Kind, AccessTy));
2296   LSRUse &LU = Uses[LUIdx];
2297
2298   // We don't need to track redundant offsets, but we don't need to go out
2299   // of our way here to avoid them.
2300   if (LU.Offsets.empty() || Offset != LU.Offsets.back())
2301     LU.Offsets.push_back(Offset);
2302
2303   LU.MinOffset = Offset;
2304   LU.MaxOffset = Offset;
2305   return std::make_pair(LUIdx, Offset);
2306 }
2307
2308 /// Delete the given use from the Uses list.
2309 void LSRInstance::DeleteUse(LSRUse &LU, size_t LUIdx) {
2310   if (&LU != &Uses.back())
2311     std::swap(LU, Uses.back());
2312   Uses.pop_back();
2313
2314   // Update RegUses.
2315   RegUses.swapAndDropUse(LUIdx, Uses.size());
2316 }
2317
2318 /// Look for a use distinct from OrigLU which is has a formula that has the same
2319 /// registers as the given formula.
2320 LSRUse *
2321 LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF,
2322                                        const LSRUse &OrigLU) {
2323   // Search all uses for the formula. This could be more clever.
2324   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
2325     LSRUse &LU = Uses[LUIdx];
2326     // Check whether this use is close enough to OrigLU, to see whether it's
2327     // worthwhile looking through its formulae.
2328     // Ignore ICmpZero uses because they may contain formulae generated by
2329     // GenerateICmpZeroScales, in which case adding fixup offsets may
2330     // be invalid.
2331     if (&LU != &OrigLU &&
2332         LU.Kind != LSRUse::ICmpZero &&
2333         LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy &&
2334         LU.WidestFixupType == OrigLU.WidestFixupType &&
2335         LU.HasFormulaWithSameRegs(OrigF)) {
2336       // Scan through this use's formulae.
2337       for (const Formula &F : LU.Formulae) {
2338         // Check to see if this formula has the same registers and symbols
2339         // as OrigF.
2340         if (F.BaseRegs == OrigF.BaseRegs &&
2341             F.ScaledReg == OrigF.ScaledReg &&
2342             F.BaseGV == OrigF.BaseGV &&
2343             F.Scale == OrigF.Scale &&
2344             F.UnfoldedOffset == OrigF.UnfoldedOffset) {
2345           if (F.BaseOffset == 0)
2346             return &LU;
2347           // This is the formula where all the registers and symbols matched;
2348           // there aren't going to be any others. Since we declined it, we
2349           // can skip the rest of the formulae and proceed to the next LSRUse.
2350           break;
2351         }
2352       }
2353     }
2354   }
2355
2356   // Nothing looked good.
2357   return nullptr;
2358 }
2359
2360 void LSRInstance::CollectInterestingTypesAndFactors() {
2361   SmallSetVector<const SCEV *, 4> Strides;
2362
2363   // Collect interesting types and strides.
2364   SmallVector<const SCEV *, 4> Worklist;
2365   for (const IVStrideUse &U : IU) {
2366     const SCEV *Expr = IU.getExpr(U);
2367
2368     // Collect interesting types.
2369     Types.insert(SE.getEffectiveSCEVType(Expr->getType()));
2370
2371     // Add strides for mentioned loops.
2372     Worklist.push_back(Expr);
2373     do {
2374       const SCEV *S = Worklist.pop_back_val();
2375       if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2376         if (AR->getLoop() == L)
2377           Strides.insert(AR->getStepRecurrence(SE));
2378         Worklist.push_back(AR->getStart());
2379       } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
2380         Worklist.append(Add->op_begin(), Add->op_end());
2381       }
2382     } while (!Worklist.empty());
2383   }
2384
2385   // Compute interesting factors from the set of interesting strides.
2386   for (SmallSetVector<const SCEV *, 4>::const_iterator
2387        I = Strides.begin(), E = Strides.end(); I != E; ++I)
2388     for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
2389          std::next(I); NewStrideIter != E; ++NewStrideIter) {
2390       const SCEV *OldStride = *I;
2391       const SCEV *NewStride = *NewStrideIter;
2392
2393       if (SE.getTypeSizeInBits(OldStride->getType()) !=
2394           SE.getTypeSizeInBits(NewStride->getType())) {
2395         if (SE.getTypeSizeInBits(OldStride->getType()) >
2396             SE.getTypeSizeInBits(NewStride->getType()))
2397           NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType());
2398         else
2399           OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType());
2400       }
2401       if (const SCEVConstant *Factor =
2402             dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride,
2403                                                         SE, true))) {
2404         if (Factor->getAPInt().getMinSignedBits() <= 64)
2405           Factors.insert(Factor->getAPInt().getSExtValue());
2406       } else if (const SCEVConstant *Factor =
2407                    dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride,
2408                                                                NewStride,
2409                                                                SE, true))) {
2410         if (Factor->getAPInt().getMinSignedBits() <= 64)
2411           Factors.insert(Factor->getAPInt().getSExtValue());
2412       }
2413     }
2414
2415   // If all uses use the same type, don't bother looking for truncation-based
2416   // reuse.
2417   if (Types.size() == 1)
2418     Types.clear();
2419
2420   DEBUG(print_factors_and_types(dbgs()));
2421 }
2422
2423 /// Helper for CollectChains that finds an IV operand (computed by an AddRec in
2424 /// this loop) within [OI,OE) or returns OE. If IVUsers mapped Instructions to
2425 /// IVStrideUses, we could partially skip this.
2426 static User::op_iterator
2427 findIVOperand(User::op_iterator OI, User::op_iterator OE,
2428               Loop *L, ScalarEvolution &SE) {
2429   for(; OI != OE; ++OI) {
2430     if (Instruction *Oper = dyn_cast<Instruction>(*OI)) {
2431       if (!SE.isSCEVable(Oper->getType()))
2432         continue;
2433
2434       if (const SCEVAddRecExpr *AR =
2435           dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Oper))) {
2436         if (AR->getLoop() == L)
2437           break;
2438       }
2439     }
2440   }
2441   return OI;
2442 }
2443
2444 /// IVChain logic must consistenctly peek base TruncInst operands, so wrap it in
2445 /// a convenient helper.
2446 static Value *getWideOperand(Value *Oper) {
2447   if (TruncInst *Trunc = dyn_cast<TruncInst>(Oper))
2448     return Trunc->getOperand(0);
2449   return Oper;
2450 }
2451
2452 /// Return true if we allow an IV chain to include both types.
2453 static bool isCompatibleIVType(Value *LVal, Value *RVal) {
2454   Type *LType = LVal->getType();
2455   Type *RType = RVal->getType();
2456   return (LType == RType) || (LType->isPointerTy() && RType->isPointerTy());
2457 }
2458
2459 /// Return an approximation of this SCEV expression's "base", or NULL for any
2460 /// constant. Returning the expression itself is conservative. Returning a
2461 /// deeper subexpression is more precise and valid as long as it isn't less
2462 /// complex than another subexpression. For expressions involving multiple
2463 /// unscaled values, we need to return the pointer-type SCEVUnknown. This avoids
2464 /// forming chains across objects, such as: PrevOper==a[i], IVOper==b[i],
2465 /// IVInc==b-a.
2466 ///
2467 /// Since SCEVUnknown is the rightmost type, and pointers are the rightmost
2468 /// SCEVUnknown, we simply return the rightmost SCEV operand.
2469 static const SCEV *getExprBase(const SCEV *S) {
2470   switch (S->getSCEVType()) {
2471   default: // uncluding scUnknown.
2472     return S;
2473   case scConstant:
2474     return nullptr;
2475   case scTruncate:
2476     return getExprBase(cast<SCEVTruncateExpr>(S)->getOperand());
2477   case scZeroExtend:
2478     return getExprBase(cast<SCEVZeroExtendExpr>(S)->getOperand());
2479   case scSignExtend:
2480     return getExprBase(cast<SCEVSignExtendExpr>(S)->getOperand());
2481   case scAddExpr: {
2482     // Skip over scaled operands (scMulExpr) to follow add operands as long as
2483     // there's nothing more complex.
2484     // FIXME: not sure if we want to recognize negation.
2485     const SCEVAddExpr *Add = cast<SCEVAddExpr>(S);
2486     for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(Add->op_end()),
2487            E(Add->op_begin()); I != E; ++I) {
2488       const SCEV *SubExpr = *I;
2489       if (SubExpr->getSCEVType() == scAddExpr)
2490         return getExprBase(SubExpr);
2491
2492       if (SubExpr->getSCEVType() != scMulExpr)
2493         return SubExpr;
2494     }
2495     return S; // all operands are scaled, be conservative.
2496   }
2497   case scAddRecExpr:
2498     return getExprBase(cast<SCEVAddRecExpr>(S)->getStart());
2499   }
2500 }
2501
2502 /// Return true if the chain increment is profitable to expand into a loop
2503 /// invariant value, which may require its own register. A profitable chain
2504 /// increment will be an offset relative to the same base. We allow such offsets
2505 /// to potentially be used as chain increment as long as it's not obviously
2506 /// expensive to expand using real instructions.
2507 bool IVChain::isProfitableIncrement(const SCEV *OperExpr,
2508                                     const SCEV *IncExpr,
2509                                     ScalarEvolution &SE) {
2510   // Aggressively form chains when -stress-ivchain.
2511   if (StressIVChain)
2512     return true;
2513
2514   // Do not replace a constant offset from IV head with a nonconstant IV
2515   // increment.
2516   if (!isa<SCEVConstant>(IncExpr)) {
2517     const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Incs[0].IVOperand));
2518     if (isa<SCEVConstant>(SE.getMinusSCEV(OperExpr, HeadExpr)))
2519       return 0;
2520   }
2521
2522   SmallPtrSet<const SCEV*, 8> Processed;
2523   return !isHighCostExpansion(IncExpr, Processed, SE);
2524 }
2525
2526 /// Return true if the number of registers needed for the chain is estimated to
2527 /// be less than the number required for the individual IV users. First prohibit
2528 /// any IV users that keep the IV live across increments (the Users set should
2529 /// be empty). Next count the number and type of increments in the chain.
2530 ///
2531 /// Chaining IVs can lead to considerable code bloat if ISEL doesn't
2532 /// effectively use postinc addressing modes. Only consider it profitable it the
2533 /// increments can be computed in fewer registers when chained.
2534 ///
2535 /// TODO: Consider IVInc free if it's already used in another chains.
2536 static bool
2537 isProfitableChain(IVChain &Chain, SmallPtrSetImpl<Instruction*> &Users,
2538                   ScalarEvolution &SE, const TargetTransformInfo &TTI) {
2539   if (StressIVChain)
2540     return true;
2541
2542   if (!Chain.hasIncs())
2543     return false;
2544
2545   if (!Users.empty()) {
2546     DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " users:\n";
2547           for (Instruction *Inst : Users) {
2548             dbgs() << "  " << *Inst << "\n";
2549           });
2550     return false;
2551   }
2552   assert(!Chain.Incs.empty() && "empty IV chains are not allowed");
2553
2554   // The chain itself may require a register, so intialize cost to 1.
2555   int cost = 1;
2556
2557   // A complete chain likely eliminates the need for keeping the original IV in
2558   // a register. LSR does not currently know how to form a complete chain unless
2559   // the header phi already exists.
2560   if (isa<PHINode>(Chain.tailUserInst())
2561       && SE.getSCEV(Chain.tailUserInst()) == Chain.Incs[0].IncExpr) {
2562     --cost;
2563   }
2564   const SCEV *LastIncExpr = nullptr;
2565   unsigned NumConstIncrements = 0;
2566   unsigned NumVarIncrements = 0;
2567   unsigned NumReusedIncrements = 0;
2568   for (const IVInc &Inc : Chain) {
2569     if (Inc.IncExpr->isZero())
2570       continue;
2571
2572     // Incrementing by zero or some constant is neutral. We assume constants can
2573     // be folded into an addressing mode or an add's immediate operand.
2574     if (isa<SCEVConstant>(Inc.IncExpr)) {
2575       ++NumConstIncrements;
2576       continue;
2577     }
2578
2579     if (Inc.IncExpr == LastIncExpr)
2580       ++NumReusedIncrements;
2581     else
2582       ++NumVarIncrements;
2583
2584     LastIncExpr = Inc.IncExpr;
2585   }
2586   // An IV chain with a single increment is handled by LSR's postinc
2587   // uses. However, a chain with multiple increments requires keeping the IV's
2588   // value live longer than it needs to be if chained.
2589   if (NumConstIncrements > 1)
2590     --cost;
2591
2592   // Materializing increment expressions in the preheader that didn't exist in
2593   // the original code may cost a register. For example, sign-extended array
2594   // indices can produce ridiculous increments like this:
2595   // IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64)))
2596   cost += NumVarIncrements;
2597
2598   // Reusing variable increments likely saves a register to hold the multiple of
2599   // the stride.
2600   cost -= NumReusedIncrements;
2601
2602   DEBUG(dbgs() << "Chain: " << *Chain.Incs[0].UserInst << " Cost: " << cost
2603                << "\n");
2604
2605   return cost < 0;
2606 }
2607
2608 /// Add this IV user to an existing chain or make it the head of a new chain.
2609 void LSRInstance::ChainInstruction(Instruction *UserInst, Instruction *IVOper,
2610                                    SmallVectorImpl<ChainUsers> &ChainUsersVec) {
2611   // When IVs are used as types of varying widths, they are generally converted
2612   // to a wider type with some uses remaining narrow under a (free) trunc.
2613   Value *const NextIV = getWideOperand(IVOper);
2614   const SCEV *const OperExpr = SE.getSCEV(NextIV);
2615   const SCEV *const OperExprBase = getExprBase(OperExpr);
2616
2617   // Visit all existing chains. Check if its IVOper can be computed as a
2618   // profitable loop invariant increment from the last link in the Chain.
2619   unsigned ChainIdx = 0, NChains = IVChainVec.size();
2620   const SCEV *LastIncExpr = nullptr;
2621   for (; ChainIdx < NChains; ++ChainIdx) {
2622     IVChain &Chain = IVChainVec[ChainIdx];
2623
2624     // Prune the solution space aggressively by checking that both IV operands
2625     // are expressions that operate on the same unscaled SCEVUnknown. This
2626     // "base" will be canceled by the subsequent getMinusSCEV call. Checking
2627     // first avoids creating extra SCEV expressions.
2628     if (!StressIVChain && Chain.ExprBase != OperExprBase)
2629       continue;
2630
2631     Value *PrevIV = getWideOperand(Chain.Incs.back().IVOperand);
2632     if (!isCompatibleIVType(PrevIV, NextIV))
2633       continue;
2634
2635     // A phi node terminates a chain.
2636     if (isa<PHINode>(UserInst) && isa<PHINode>(Chain.tailUserInst()))
2637       continue;
2638
2639     // The increment must be loop-invariant so it can be kept in a register.
2640     const SCEV *PrevExpr = SE.getSCEV(PrevIV);
2641     const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr);
2642     if (!SE.isLoopInvariant(IncExpr, L))
2643       continue;
2644
2645     if (Chain.isProfitableIncrement(OperExpr, IncExpr, SE)) {
2646       LastIncExpr = IncExpr;
2647       break;
2648     }
2649   }
2650   // If we haven't found a chain, create a new one, unless we hit the max. Don't
2651   // bother for phi nodes, because they must be last in the chain.
2652   if (ChainIdx == NChains) {
2653     if (isa<PHINode>(UserInst))
2654       return;
2655     if (NChains >= MaxChains && !StressIVChain) {
2656       DEBUG(dbgs() << "IV Chain Limit\n");
2657       return;
2658     }
2659     LastIncExpr = OperExpr;
2660     // IVUsers may have skipped over sign/zero extensions. We don't currently
2661     // attempt to form chains involving extensions unless they can be hoisted
2662     // into this loop's AddRec.
2663     if (!isa<SCEVAddRecExpr>(LastIncExpr))
2664       return;
2665     ++NChains;
2666     IVChainVec.push_back(IVChain(IVInc(UserInst, IVOper, LastIncExpr),
2667                                  OperExprBase));
2668     ChainUsersVec.resize(NChains);
2669     DEBUG(dbgs() << "IV Chain#" << ChainIdx << " Head: (" << *UserInst
2670                  << ") IV=" << *LastIncExpr << "\n");
2671   } else {
2672     DEBUG(dbgs() << "IV Chain#" << ChainIdx << "  Inc: (" << *UserInst
2673                  << ") IV+" << *LastIncExpr << "\n");
2674     // Add this IV user to the end of the chain.
2675     IVChainVec[ChainIdx].add(IVInc(UserInst, IVOper, LastIncExpr));
2676   }
2677   IVChain &Chain = IVChainVec[ChainIdx];
2678
2679   SmallPtrSet<Instruction*,4> &NearUsers = ChainUsersVec[ChainIdx].NearUsers;
2680   // This chain's NearUsers become FarUsers.
2681   if (!LastIncExpr->isZero()) {
2682     ChainUsersVec[ChainIdx].FarUsers.insert(NearUsers.begin(),
2683                                             NearUsers.end());
2684     NearUsers.clear();
2685   }
2686
2687   // All other uses of IVOperand become near uses of the chain.
2688   // We currently ignore intermediate values within SCEV expressions, assuming
2689   // they will eventually be used be the current chain, or can be computed
2690   // from one of the chain increments. To be more precise we could
2691   // transitively follow its user and only add leaf IV users to the set.
2692   for (User *U : IVOper->users()) {
2693     Instruction *OtherUse = dyn_cast<Instruction>(U);
2694     if (!OtherUse)
2695       continue;
2696     // Uses in the chain will no longer be uses if the chain is formed.
2697     // Include the head of the chain in this iteration (not Chain.begin()).
2698     IVChain::const_iterator IncIter = Chain.Incs.begin();
2699     IVChain::const_iterator IncEnd = Chain.Incs.end();
2700     for( ; IncIter != IncEnd; ++IncIter) {
2701       if (IncIter->UserInst == OtherUse)
2702         break;
2703     }
2704     if (IncIter != IncEnd)
2705       continue;
2706
2707     if (SE.isSCEVable(OtherUse->getType())
2708         && !isa<SCEVUnknown>(SE.getSCEV(OtherUse))
2709         && IU.isIVUserOrOperand(OtherUse)) {
2710       continue;
2711     }
2712     NearUsers.insert(OtherUse);
2713   }
2714
2715   // Since this user is part of the chain, it's no longer considered a use
2716   // of the chain.
2717   ChainUsersVec[ChainIdx].FarUsers.erase(UserInst);
2718 }
2719
2720 /// Populate the vector of Chains.
2721 ///
2722 /// This decreases ILP at the architecture level. Targets with ample registers,
2723 /// multiple memory ports, and no register renaming probably don't want
2724 /// this. However, such targets should probably disable LSR altogether.
2725 ///
2726 /// The job of LSR is to make a reasonable choice of induction variables across
2727 /// the loop. Subsequent passes can easily "unchain" computation exposing more
2728 /// ILP *within the loop* if the target wants it.
2729 ///
2730 /// Finding the best IV chain is potentially a scheduling problem. Since LSR
2731 /// will not reorder memory operations, it will recognize this as a chain, but
2732 /// will generate redundant IV increments. Ideally this would be corrected later
2733 /// by a smart scheduler:
2734 ///        = A[i]
2735 ///        = A[i+x]
2736 /// A[i]   =
2737 /// A[i+x] =
2738 ///
2739 /// TODO: Walk the entire domtree within this loop, not just the path to the
2740 /// loop latch. This will discover chains on side paths, but requires
2741 /// maintaining multiple copies of the Chains state.
2742 void LSRInstance::CollectChains() {
2743   DEBUG(dbgs() << "Collecting IV Chains.\n");
2744   SmallVector<ChainUsers, 8> ChainUsersVec;
2745
2746   SmallVector<BasicBlock *,8> LatchPath;
2747   BasicBlock *LoopHeader = L->getHeader();
2748   for (DomTreeNode *Rung = DT.getNode(L->getLoopLatch());
2749        Rung->getBlock() != LoopHeader; Rung = Rung->getIDom()) {
2750     LatchPath.push_back(Rung->getBlock());
2751   }
2752   LatchPath.push_back(LoopHeader);
2753
2754   // Walk the instruction stream from the loop header to the loop latch.
2755   for (SmallVectorImpl<BasicBlock *>::reverse_iterator
2756          BBIter = LatchPath.rbegin(), BBEnd = LatchPath.rend();
2757        BBIter != BBEnd; ++BBIter) {
2758     for (BasicBlock::iterator I = (*BBIter)->begin(), E = (*BBIter)->end();
2759          I != E; ++I) {
2760       // Skip instructions that weren't seen by IVUsers analysis.
2761       if (isa<PHINode>(I) || !IU.isIVUserOrOperand(&*I))
2762         continue;
2763
2764       // Ignore users that are part of a SCEV expression. This way we only
2765       // consider leaf IV Users. This effectively rediscovers a portion of
2766       // IVUsers analysis but in program order this time.
2767       if (SE.isSCEVable(I->getType()) && !isa<SCEVUnknown>(SE.getSCEV(&*I)))
2768         continue;
2769
2770       // Remove this instruction from any NearUsers set it may be in.
2771       for (unsigned ChainIdx = 0, NChains = IVChainVec.size();
2772            ChainIdx < NChains; ++ChainIdx) {
2773         ChainUsersVec[ChainIdx].NearUsers.erase(&*I);
2774       }
2775       // Search for operands that can be chained.
2776       SmallPtrSet<Instruction*, 4> UniqueOperands;
2777       User::op_iterator IVOpEnd = I->op_end();
2778       User::op_iterator IVOpIter = findIVOperand(I->op_begin(), IVOpEnd, L, SE);
2779       while (IVOpIter != IVOpEnd) {
2780         Instruction *IVOpInst = cast<Instruction>(*IVOpIter);
2781         if (UniqueOperands.insert(IVOpInst).second)
2782           ChainInstruction(&*I, IVOpInst, ChainUsersVec);
2783         IVOpIter = findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE);
2784       }
2785     } // Continue walking down the instructions.
2786   } // Continue walking down the domtree.
2787   // Visit phi backedges to determine if the chain can generate the IV postinc.
2788   for (BasicBlock::iterator I = L->getHeader()->begin();
2789        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
2790     if (!SE.isSCEVable(PN->getType()))
2791       continue;
2792
2793     Instruction *IncV =
2794       dyn_cast<Instruction>(PN->getIncomingValueForBlock(L->getLoopLatch()));
2795     if (IncV)
2796       ChainInstruction(PN, IncV, ChainUsersVec);
2797   }
2798   // Remove any unprofitable chains.
2799   unsigned ChainIdx = 0;
2800   for (unsigned UsersIdx = 0, NChains = IVChainVec.size();
2801        UsersIdx < NChains; ++UsersIdx) {
2802     if (!isProfitableChain(IVChainVec[UsersIdx],
2803                            ChainUsersVec[UsersIdx].FarUsers, SE, TTI))
2804       continue;
2805     // Preserve the chain at UsesIdx.
2806     if (ChainIdx != UsersIdx)
2807       IVChainVec[ChainIdx] = IVChainVec[UsersIdx];
2808     FinalizeChain(IVChainVec[ChainIdx]);
2809     ++ChainIdx;
2810   }
2811   IVChainVec.resize(ChainIdx);
2812 }
2813
2814 void LSRInstance::FinalizeChain(IVChain &Chain) {
2815   assert(!Chain.Incs.empty() && "empty IV chains are not allowed");
2816   DEBUG(dbgs() << "Final Chain: " << *Chain.Incs[0].UserInst << "\n");
2817
2818   for (const IVInc &Inc : Chain) {
2819     DEBUG(dbgs() << "        Inc: " << Inc.UserInst << "\n");
2820     auto UseI = std::find(Inc.UserInst->op_begin(), Inc.UserInst->op_end(),
2821                           Inc.IVOperand);
2822     assert(UseI != Inc.UserInst->op_end() && "cannot find IV operand");
2823     IVIncSet.insert(UseI);
2824   }
2825 }
2826
2827 /// Return true if the IVInc can be folded into an addressing mode.
2828 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst,
2829                              Value *Operand, const TargetTransformInfo &TTI) {
2830   const SCEVConstant *IncConst = dyn_cast<SCEVConstant>(IncExpr);
2831   if (!IncConst || !isAddressUse(UserInst, Operand))
2832     return false;
2833
2834   if (IncConst->getAPInt().getMinSignedBits() > 64)
2835     return false;
2836
2837   MemAccessTy AccessTy = getAccessType(UserInst);
2838   int64_t IncOffset = IncConst->getValue()->getSExtValue();
2839   if (!isAlwaysFoldable(TTI, LSRUse::Address, AccessTy, /*BaseGV=*/nullptr,
2840                         IncOffset, /*HaseBaseReg=*/false))
2841     return false;
2842
2843   return true;
2844 }
2845
2846 /// Generate an add or subtract for each IVInc in a chain to materialize the IV
2847 /// user's operand from the previous IV user's operand.
2848 void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter,
2849                                   SmallVectorImpl<WeakVH> &DeadInsts) {
2850   // Find the new IVOperand for the head of the chain. It may have been replaced
2851   // by LSR.
2852   const IVInc &Head = Chain.Incs[0];
2853   User::op_iterator IVOpEnd = Head.UserInst->op_end();
2854   // findIVOperand returns IVOpEnd if it can no longer find a valid IV user.
2855   User::op_iterator IVOpIter = findIVOperand(Head.UserInst->op_begin(),
2856                                              IVOpEnd, L, SE);
2857   Value *IVSrc = nullptr;
2858   while (IVOpIter != IVOpEnd) {
2859     IVSrc = getWideOperand(*IVOpIter);
2860
2861     // If this operand computes the expression that the chain needs, we may use
2862     // it. (Check this after setting IVSrc which is used below.)
2863     //
2864     // Note that if Head.IncExpr is wider than IVSrc, then this phi is too
2865     // narrow for the chain, so we can no longer use it. We do allow using a
2866     // wider phi, assuming the LSR checked for free truncation. In that case we
2867     // should already have a truncate on this operand such that
2868     // getSCEV(IVSrc) == IncExpr.
2869     if (SE.getSCEV(*IVOpIter) == Head.IncExpr
2870         || SE.getSCEV(IVSrc) == Head.IncExpr) {
2871       break;
2872     }
2873     IVOpIter = findIVOperand(std::next(IVOpIter), IVOpEnd, L, SE);
2874   }
2875   if (IVOpIter == IVOpEnd) {
2876     // Gracefully give up on this chain.
2877     DEBUG(dbgs() << "Concealed chain head: " << *Head.UserInst << "\n");
2878     return;
2879   }
2880
2881   DEBUG(dbgs() << "Generate chain at: " << *IVSrc << "\n");
2882   Type *IVTy = IVSrc->getType();
2883   Type *IntTy = SE.getEffectiveSCEVType(IVTy);
2884   const SCEV *LeftOverExpr = nullptr;
2885   for (const IVInc &Inc : Chain) {
2886     Instruction *InsertPt = Inc.UserInst;
2887     if (isa<PHINode>(InsertPt))
2888       InsertPt = L->getLoopLatch()->getTerminator();
2889
2890     // IVOper will replace the current IV User's operand. IVSrc is the IV
2891     // value currently held in a register.
2892     Value *IVOper = IVSrc;
2893     if (!Inc.IncExpr->isZero()) {
2894       // IncExpr was the result of subtraction of two narrow values, so must
2895       // be signed.
2896       const SCEV *IncExpr = SE.getNoopOrSignExtend(Inc.IncExpr, IntTy);
2897       LeftOverExpr = LeftOverExpr ?
2898         SE.getAddExpr(LeftOverExpr, IncExpr) : IncExpr;
2899     }
2900     if (LeftOverExpr && !LeftOverExpr->isZero()) {
2901       // Expand the IV increment.
2902       Rewriter.clearPostInc();
2903       Value *IncV = Rewriter.expandCodeFor(LeftOverExpr, IntTy, InsertPt);
2904       const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc),
2905                                              SE.getUnknown(IncV));
2906       IVOper = Rewriter.expandCodeFor(IVOperExpr, IVTy, InsertPt);
2907
2908       // If an IV increment can't be folded, use it as the next IV value.
2909       if (!canFoldIVIncExpr(LeftOverExpr, Inc.UserInst, Inc.IVOperand, TTI)) {
2910         assert(IVTy == IVOper->getType() && "inconsistent IV increment type");
2911         IVSrc = IVOper;
2912         LeftOverExpr = nullptr;
2913       }
2914     }
2915     Type *OperTy = Inc.IVOperand->getType();
2916     if (IVTy != OperTy) {
2917       assert(SE.getTypeSizeInBits(IVTy) >= SE.getTypeSizeInBits(OperTy) &&
2918              "cannot extend a chained IV");
2919       IRBuilder<> Builder(InsertPt);
2920       IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy, "lsr.chain");
2921     }
2922     Inc.UserInst->replaceUsesOfWith(Inc.IVOperand, IVOper);
2923     DeadInsts.emplace_back(Inc.IVOperand);
2924   }
2925   // If LSR created a new, wider phi, we may also replace its postinc. We only
2926   // do this if we also found a wide value for the head of the chain.
2927   if (isa<PHINode>(Chain.tailUserInst())) {
2928     for (BasicBlock::iterator I = L->getHeader()->begin();
2929          PHINode *Phi = dyn_cast<PHINode>(I); ++I) {
2930       if (!isCompatibleIVType(Phi, IVSrc))
2931         continue;
2932       Instruction *PostIncV = dyn_cast<Instruction>(
2933         Phi->getIncomingValueForBlock(L->getLoopLatch()));
2934       if (!PostIncV || (SE.getSCEV(PostIncV) != SE.getSCEV(IVSrc)))
2935         continue;
2936       Value *IVOper = IVSrc;
2937       Type *PostIncTy = PostIncV->getType();
2938       if (IVTy != PostIncTy) {
2939         assert(PostIncTy->isPointerTy() && "mixing int/ptr IV types");
2940         IRBuilder<> Builder(L->getLoopLatch()->getTerminator());
2941         Builder.SetCurrentDebugLocation(PostIncV->getDebugLoc());
2942         IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy, "lsr.chain");
2943       }
2944       Phi->replaceUsesOfWith(PostIncV, IVOper);
2945       DeadInsts.emplace_back(PostIncV);
2946     }
2947   }
2948 }
2949
2950 void LSRInstance::CollectFixupsAndInitialFormulae() {
2951   for (const IVStrideUse &U : IU) {
2952     Instruction *UserInst = U.getUser();
2953     // Skip IV users that are part of profitable IV Chains.
2954     User::op_iterator UseI = std::find(UserInst->op_begin(), UserInst->op_end(),
2955                                        U.getOperandValToReplace());
2956     assert(UseI != UserInst->op_end() && "cannot find IV operand");
2957     if (IVIncSet.count(UseI))
2958       continue;
2959
2960     // Record the uses.
2961     LSRFixup &LF = getNewFixup();
2962     LF.UserInst = UserInst;
2963     LF.OperandValToReplace = U.getOperandValToReplace();
2964     LF.PostIncLoops = U.getPostIncLoops();
2965
2966     LSRUse::KindType Kind = LSRUse::Basic;
2967     MemAccessTy AccessTy;
2968     if (isAddressUse(LF.UserInst, LF.OperandValToReplace)) {
2969       Kind = LSRUse::Address;
2970       AccessTy = getAccessType(LF.UserInst);
2971     }
2972
2973     const SCEV *S = IU.getExpr(U);
2974
2975     // Equality (== and !=) ICmps are special. We can rewrite (i == N) as
2976     // (N - i == 0), and this allows (N - i) to be the expression that we work
2977     // with rather than just N or i, so we can consider the register
2978     // requirements for both N and i at the same time. Limiting this code to
2979     // equality icmps is not a problem because all interesting loops use
2980     // equality icmps, thanks to IndVarSimplify.
2981     if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst))
2982       if (CI->isEquality()) {
2983         // Swap the operands if needed to put the OperandValToReplace on the
2984         // left, for consistency.
2985         Value *NV = CI->getOperand(1);
2986         if (NV == LF.OperandValToReplace) {
2987           CI->setOperand(1, CI->getOperand(0));
2988           CI->setOperand(0, NV);
2989           NV = CI->getOperand(1);
2990           Changed = true;
2991         }
2992
2993         // x == y  -->  x - y == 0
2994         const SCEV *N = SE.getSCEV(NV);
2995         if (SE.isLoopInvariant(N, L) && isSafeToExpand(N, SE)) {
2996           // S is normalized, so normalize N before folding it into S
2997           // to keep the result normalized.
2998           N = TransformForPostIncUse(Normalize, N, CI, nullptr,
2999                                      LF.PostIncLoops, SE, DT);
3000           Kind = LSRUse::ICmpZero;
3001           S = SE.getMinusSCEV(N, S);
3002         }
3003
3004         // -1 and the negations of all interesting strides (except the negation
3005         // of -1) are now also interesting.
3006         for (size_t i = 0, e = Factors.size(); i != e; ++i)
3007           if (Factors[i] != -1)
3008             Factors.insert(-(uint64_t)Factors[i]);
3009         Factors.insert(-1);
3010       }
3011
3012     // Set up the initial formula for this use.
3013     std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy);
3014     LF.LUIdx = P.first;
3015     LF.Offset = P.second;
3016     LSRUse &LU = Uses[LF.LUIdx];
3017     LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
3018     if (!LU.WidestFixupType ||
3019         SE.getTypeSizeInBits(LU.WidestFixupType) <
3020         SE.getTypeSizeInBits(LF.OperandValToReplace->getType()))
3021       LU.WidestFixupType = LF.OperandValToReplace->getType();
3022
3023     // If this is the first use of this LSRUse, give it a formula.
3024     if (LU.Formulae.empty()) {
3025       InsertInitialFormula(S, LU, LF.LUIdx);
3026       CountRegisters(LU.Formulae.back(), LF.LUIdx);
3027     }
3028   }
3029
3030   DEBUG(print_fixups(dbgs()));
3031 }
3032
3033 /// Insert a formula for the given expression into the given use, separating out
3034 /// loop-variant portions from loop-invariant and loop-computable portions.
3035 void
3036 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) {
3037   // Mark uses whose expressions cannot be expanded.
3038   if (!isSafeToExpand(S, SE))
3039     LU.RigidFormula = true;
3040
3041   Formula F;
3042   F.initialMatch(S, L, SE);
3043   bool Inserted = InsertFormula(LU, LUIdx, F);
3044   assert(Inserted && "Initial formula already exists!"); (void)Inserted;
3045 }
3046
3047 /// Insert a simple single-register formula for the given expression into the
3048 /// given use.
3049 void
3050 LSRInstance::InsertSupplementalFormula(const SCEV *S,
3051                                        LSRUse &LU, size_t LUIdx) {
3052   Formula F;
3053   F.BaseRegs.push_back(S);
3054   F.HasBaseReg = true;
3055   bool Inserted = InsertFormula(LU, LUIdx, F);
3056   assert(Inserted && "Supplemental formula already exists!"); (void)Inserted;
3057 }
3058
3059 /// Note which registers are used by the given formula, updating RegUses.
3060 void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) {
3061   if (F.ScaledReg)
3062     RegUses.countRegister(F.ScaledReg, LUIdx);
3063   for (const SCEV *BaseReg : F.BaseRegs)
3064     RegUses.countRegister(BaseReg, LUIdx);
3065 }
3066
3067 /// If the given formula has not yet been inserted, add it to the list, and
3068 /// return true. Return false otherwise.
3069 bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) {
3070   // Do not insert formula that we will not be able to expand.
3071   assert(isLegalUse(TTI, LU.MinOffset, LU.MaxOffset, LU.Kind, LU.AccessTy, F) &&
3072          "Formula is illegal");
3073   if (!LU.InsertFormula(F))
3074     return false;
3075
3076   CountRegisters(F, LUIdx);
3077   return true;
3078 }
3079
3080 /// Check for other uses of loop-invariant values which we're tracking. These
3081 /// other uses will pin these values in registers, making them less profitable
3082 /// for elimination.
3083 /// TODO: This currently misses non-constant addrec step registers.
3084 /// TODO: Should this give more weight to users inside the loop?
3085 void
3086 LSRInstance::CollectLoopInvariantFixupsAndFormulae() {
3087   SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end());
3088   SmallPtrSet<const SCEV *, 32> Visited;
3089
3090   while (!Worklist.empty()) {
3091     const SCEV *S = Worklist.pop_back_val();
3092
3093     // Don't process the same SCEV twice
3094     if (!Visited.insert(S).second)
3095       continue;
3096
3097     if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S))
3098       Worklist.append(N->op_begin(), N->op_end());
3099     else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S))
3100       Worklist.push_back(C->getOperand());
3101     else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
3102       Worklist.push_back(D->getLHS());
3103       Worklist.push_back(D->getRHS());
3104     } else if (const SCEVUnknown *US = dyn_cast<SCEVUnknown>(S)) {
3105       const Value *V = US->getValue();
3106       if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
3107         // Look for instructions defined outside the loop.
3108         if (L->contains(Inst)) continue;
3109       } else if (isa<UndefValue>(V))
3110         // Undef doesn't have a live range, so it doesn't matter.
3111         continue;
3112       for (const Use &U : V->uses()) {
3113         const Instruction *UserInst = dyn_cast<Instruction>(U.getUser());
3114         // Ignore non-instructions.
3115         if (!UserInst)
3116           continue;
3117         // Ignore instructions in other functions (as can happen with
3118         // Constants).
3119         if (UserInst->getParent()->getParent() != L->getHeader()->getParent())
3120           continue;
3121         // Ignore instructions not dominated by the loop.
3122         const BasicBlock *UseBB = !isa<PHINode>(UserInst) ?
3123           UserInst->getParent() :
3124           cast<PHINode>(UserInst)->getIncomingBlock(
3125             PHINode::getIncomingValueNumForOperand(U.getOperandNo()));
3126         if (!DT.dominates(L->getHeader(), UseBB))
3127           continue;
3128         // Don't bother if the instruction is in a BB which ends in an EHPad.
3129         if (UseBB->getTerminator()->isEHPad())
3130           continue;
3131         // Ignore uses which are part of other SCEV expressions, to avoid
3132         // analyzing them multiple times.
3133         if (SE.isSCEVable(UserInst->getType())) {
3134           const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst));
3135           // If the user is a no-op, look through to its uses.
3136           if (!isa<SCEVUnknown>(UserS))
3137             continue;
3138           if (UserS == US) {
3139             Worklist.push_back(
3140               SE.getUnknown(const_cast<Instruction *>(UserInst)));
3141             continue;
3142           }
3143         }
3144         // Ignore icmp instructions which are already being analyzed.
3145         if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UserInst)) {
3146           unsigned OtherIdx = !U.getOperandNo();
3147           Value *OtherOp = const_cast<Value *>(ICI->getOperand(OtherIdx));
3148           if (SE.hasComputableLoopEvolution(SE.getSCEV(OtherOp), L))
3149             continue;
3150         }
3151
3152         LSRFixup &LF = getNewFixup();
3153         LF.UserInst = const_cast<Instruction *>(UserInst);
3154         LF.OperandValToReplace = U;
3155         std::pair<size_t, int64_t> P = getUse(
3156             S, LSRUse::Basic, MemAccessTy());
3157         LF.LUIdx = P.first;
3158         LF.Offset = P.second;
3159         LSRUse &LU = Uses[LF.LUIdx];
3160         LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
3161         if (!LU.WidestFixupType ||
3162             SE.getTypeSizeInBits(LU.WidestFixupType) <
3163             SE.getTypeSizeInBits(LF.OperandValToReplace->getType()))
3164           LU.WidestFixupType = LF.OperandValToReplace->getType();
3165         InsertSupplementalFormula(US, LU, LF.LUIdx);
3166         CountRegisters(LU.Formulae.back(), Uses.size() - 1);
3167         break;
3168       }
3169     }
3170   }
3171 }
3172
3173 /// Split S into subexpressions which can be pulled out into separate
3174 /// registers. If C is non-null, multiply each subexpression by C.
3175 ///
3176 /// Return remainder expression after factoring the subexpressions captured by
3177 /// Ops. If Ops is complete, return NULL.
3178 static const SCEV *CollectSubexprs(const SCEV *S, const SCEVConstant *C,
3179                                    SmallVectorImpl<const SCEV *> &Ops,
3180                                    const Loop *L,
3181                                    ScalarEvolution &SE,
3182                                    unsigned Depth = 0) {
3183   // Arbitrarily cap recursion to protect compile time.
3184   if (Depth >= 3)
3185     return S;
3186
3187   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
3188     // Break out add operands.
3189     for (const SCEV *S : Add->operands()) {
3190       const SCEV *Remainder = CollectSubexprs(S, C, Ops, L, SE, Depth+1);
3191       if (Remainder)
3192         Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder);
3193     }
3194     return nullptr;
3195   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
3196     // Split a non-zero base out of an addrec.
3197     if (AR->getStart()->isZero())
3198       return S;
3199
3200     const SCEV *Remainder = CollectSubexprs(AR->getStart(),
3201                                             C, Ops, L, SE, Depth+1);
3202     // Split the non-zero AddRec unless it is part of a nested recurrence that
3203     // does not pertain to this loop.
3204     if (Remainder && (AR->getLoop() == L || !isa<SCEVAddRecExpr>(Remainder))) {
3205       Ops.push_back(C ? SE.getMulExpr(C, Remainder) : Remainder);
3206       Remainder = nullptr;
3207     }
3208     if (Remainder != AR->getStart()) {
3209       if (!Remainder)
3210         Remainder = SE.getConstant(AR->getType(), 0);
3211       return SE.getAddRecExpr(Remainder,
3212                               AR->getStepRecurrence(SE),
3213                               AR->getLoop(),
3214                               //FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
3215                               SCEV::FlagAnyWrap);
3216     }
3217   } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
3218     // Break (C * (a + b + c)) into C*a + C*b + C*c.
3219     if (Mul->getNumOperands() != 2)
3220       return S;
3221     if (const SCEVConstant *Op0 =
3222         dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
3223       C = C ? cast<SCEVConstant>(SE.getMulExpr(C, Op0)) : Op0;
3224       const SCEV *Remainder =
3225         CollectSubexprs(Mul->getOperand(1), C, Ops, L, SE, Depth+1);
3226       if (Remainder)
3227         Ops.push_back(SE.getMulExpr(C, Remainder));
3228       return nullptr;
3229     }
3230   }
3231   return S;
3232 }
3233
3234 /// \brief Helper function for LSRInstance::GenerateReassociations.
3235 void LSRInstance::GenerateReassociationsImpl(LSRUse &LU, unsigned LUIdx,
3236                                              const Formula &Base,
3237                                              unsigned Depth, size_t Idx,
3238                                              bool IsScaledReg) {
3239   const SCEV *BaseReg = IsScaledReg ? Base.ScaledReg : Base.BaseRegs[Idx];
3240   SmallVector<const SCEV *, 8> AddOps;
3241   const SCEV *Remainder = CollectSubexprs(BaseReg, nullptr, AddOps, L, SE);
3242   if (Remainder)
3243     AddOps.push_back(Remainder);
3244
3245   if (AddOps.size() == 1)
3246     return;
3247
3248   for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(),
3249                                                      JE = AddOps.end();
3250        J != JE; ++J) {
3251
3252     // Loop-variant "unknown" values are uninteresting; we won't be able to
3253     // do anything meaningful with them.
3254     if (isa<SCEVUnknown>(*J) && !SE.isLoopInvariant(*J, L))
3255       continue;
3256
3257     // Don't pull a constant into a register if the constant could be folded
3258     // into an immediate field.
3259     if (isAlwaysFoldable(TTI, SE, LU.MinOffset, LU.MaxOffset, LU.Kind,
3260                          LU.AccessTy, *J, Base.getNumRegs() > 1))
3261       continue;
3262
3263     // Collect all operands except *J.
3264     SmallVector<const SCEV *, 8> InnerAddOps(
3265         ((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J);
3266     InnerAddOps.append(std::next(J),
3267                        ((const SmallVector<const SCEV *, 8> &)AddOps).end());
3268
3269     // Don't leave just a constant behind in a register if the constant could
3270     // be folded into an immediate field.
3271     if (InnerAddOps.size() == 1 &&
3272         isAlwaysFoldable(TTI, SE, LU.MinOffset, LU.MaxOffset, LU.Kind,
3273                          LU.AccessTy, InnerAddOps[0], Base.getNumRegs() > 1))
3274       continue;
3275
3276     const SCEV *InnerSum = SE.getAddExpr(InnerAddOps);
3277     if (InnerSum->isZero())
3278       continue;
3279     Formula F = Base;
3280
3281     // Add the remaining pieces of the add back into the new formula.
3282     const SCEVConstant *InnerSumSC = dyn_cast<SCEVConstant>(InnerSum);
3283     if (InnerSumSC && SE.getTypeSizeInBits(InnerSumSC->getType()) <= 64 &&
3284         TTI.isLegalAddImmediate((uint64_t)F.UnfoldedOffset +
3285                                 InnerSumSC->getValue()->getZExtValue())) {
3286       F.UnfoldedOffset =
3287           (uint64_t)F.UnfoldedOffset + InnerSumSC->getValue()->getZExtValue();
3288       if (IsScaledReg)
3289         F.ScaledReg = nullptr;
3290       else
3291         F.BaseRegs.erase(F.BaseRegs.begin() + Idx);
3292     } else if (IsScaledReg)
3293       F.ScaledReg = InnerSum;
3294     else
3295       F.BaseRegs[Idx] = InnerSum;
3296
3297     // Add J as its own register, or an unfolded immediate.
3298     const SCEVConstant *SC = dyn_cast<SCEVConstant>(*J);
3299     if (SC && SE.getTypeSizeInBits(SC->getType()) <= 64 &&
3300         TTI.isLegalAddImmediate((uint64_t)F.UnfoldedOffset +
3301                                 SC->getValue()->getZExtValue()))
3302       F.UnfoldedOffset =
3303           (uint64_t)F.UnfoldedOffset + SC->getValue()->getZExtValue();
3304     else
3305       F.BaseRegs.push_back(*J);
3306     // We may have changed the number of register&nbs