]> CyberLeo.Net >> Repos - FreeBSD/stable/9.git/blob - contrib/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
MFC r234353:
[FreeBSD/stable/9.git] / contrib / llvm / 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 TargetLowering::AddrMode::BaseGV be changed to a ConstantExpr
41 //       instead 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 #define DEBUG_TYPE "loop-reduce"
57 #include "llvm/Transforms/Scalar.h"
58 #include "llvm/Constants.h"
59 #include "llvm/Instructions.h"
60 #include "llvm/IntrinsicInst.h"
61 #include "llvm/DerivedTypes.h"
62 #include "llvm/Analysis/IVUsers.h"
63 #include "llvm/Analysis/Dominators.h"
64 #include "llvm/Analysis/LoopPass.h"
65 #include "llvm/Analysis/ScalarEvolutionExpander.h"
66 #include "llvm/Assembly/Writer.h"
67 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
68 #include "llvm/Transforms/Utils/Local.h"
69 #include "llvm/ADT/SmallBitVector.h"
70 #include "llvm/ADT/SetVector.h"
71 #include "llvm/ADT/DenseSet.h"
72 #include "llvm/Support/Debug.h"
73 #include "llvm/Support/CommandLine.h"
74 #include "llvm/Support/ValueHandle.h"
75 #include "llvm/Support/raw_ostream.h"
76 #include "llvm/Target/TargetLowering.h"
77 #include <algorithm>
78 using namespace llvm;
79
80 /// MaxIVUsers is an arbitrary threshold that provides an early opportunitiy for
81 /// bail out. This threshold is far beyond the number of users that LSR can
82 /// conceivably solve, so it should not affect generated code, but catches the
83 /// worst cases before LSR burns too much compile time and stack space.
84 static const unsigned MaxIVUsers = 200;
85
86 // Temporary flag to cleanup congruent phis after LSR phi expansion.
87 // It's currently disabled until we can determine whether it's truly useful or
88 // not. The flag should be removed after the v3.0 release.
89 // This is now needed for ivchains.
90 static cl::opt<bool> EnablePhiElim(
91   "enable-lsr-phielim", cl::Hidden, cl::init(true),
92   cl::desc("Enable LSR phi elimination"));
93
94 #ifndef NDEBUG
95 // Stress test IV chain generation.
96 static cl::opt<bool> StressIVChain(
97   "stress-ivchain", cl::Hidden, cl::init(false),
98   cl::desc("Stress test LSR IV chains"));
99 #else
100 static bool StressIVChain = false;
101 #endif
102
103 namespace {
104
105 /// RegSortData - This class holds data which is used to order reuse candidates.
106 class RegSortData {
107 public:
108   /// UsedByIndices - This represents the set of LSRUse indices which reference
109   /// a particular register.
110   SmallBitVector UsedByIndices;
111
112   RegSortData() {}
113
114   void print(raw_ostream &OS) const;
115   void dump() const;
116 };
117
118 }
119
120 void RegSortData::print(raw_ostream &OS) const {
121   OS << "[NumUses=" << UsedByIndices.count() << ']';
122 }
123
124 void RegSortData::dump() const {
125   print(errs()); errs() << '\n';
126 }
127
128 namespace {
129
130 /// RegUseTracker - Map register candidates to information about how they are
131 /// used.
132 class RegUseTracker {
133   typedef DenseMap<const SCEV *, RegSortData> RegUsesTy;
134
135   RegUsesTy RegUsesMap;
136   SmallVector<const SCEV *, 16> RegSequence;
137
138 public:
139   void CountRegister(const SCEV *Reg, size_t LUIdx);
140   void DropRegister(const SCEV *Reg, size_t LUIdx);
141   void SwapAndDropUse(size_t LUIdx, size_t LastLUIdx);
142
143   bool isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const;
144
145   const SmallBitVector &getUsedByIndices(const SCEV *Reg) const;
146
147   void clear();
148
149   typedef SmallVectorImpl<const SCEV *>::iterator iterator;
150   typedef SmallVectorImpl<const SCEV *>::const_iterator const_iterator;
151   iterator begin() { return RegSequence.begin(); }
152   iterator end()   { return RegSequence.end(); }
153   const_iterator begin() const { return RegSequence.begin(); }
154   const_iterator end() const   { return RegSequence.end(); }
155 };
156
157 }
158
159 void
160 RegUseTracker::CountRegister(const SCEV *Reg, size_t LUIdx) {
161   std::pair<RegUsesTy::iterator, bool> Pair =
162     RegUsesMap.insert(std::make_pair(Reg, RegSortData()));
163   RegSortData &RSD = Pair.first->second;
164   if (Pair.second)
165     RegSequence.push_back(Reg);
166   RSD.UsedByIndices.resize(std::max(RSD.UsedByIndices.size(), LUIdx + 1));
167   RSD.UsedByIndices.set(LUIdx);
168 }
169
170 void
171 RegUseTracker::DropRegister(const SCEV *Reg, size_t LUIdx) {
172   RegUsesTy::iterator It = RegUsesMap.find(Reg);
173   assert(It != RegUsesMap.end());
174   RegSortData &RSD = It->second;
175   assert(RSD.UsedByIndices.size() > LUIdx);
176   RSD.UsedByIndices.reset(LUIdx);
177 }
178
179 void
180 RegUseTracker::SwapAndDropUse(size_t LUIdx, size_t LastLUIdx) {
181   assert(LUIdx <= LastLUIdx);
182
183   // Update RegUses. The data structure is not optimized for this purpose;
184   // we must iterate through it and update each of the bit vectors.
185   for (RegUsesTy::iterator I = RegUsesMap.begin(), E = RegUsesMap.end();
186        I != E; ++I) {
187     SmallBitVector &UsedByIndices = I->second.UsedByIndices;
188     if (LUIdx < UsedByIndices.size())
189       UsedByIndices[LUIdx] =
190         LastLUIdx < UsedByIndices.size() ? UsedByIndices[LastLUIdx] : 0;
191     UsedByIndices.resize(std::min(UsedByIndices.size(), LastLUIdx));
192   }
193 }
194
195 bool
196 RegUseTracker::isRegUsedByUsesOtherThan(const SCEV *Reg, size_t LUIdx) const {
197   RegUsesTy::const_iterator I = RegUsesMap.find(Reg);
198   if (I == RegUsesMap.end())
199     return false;
200   const SmallBitVector &UsedByIndices = I->second.UsedByIndices;
201   int i = UsedByIndices.find_first();
202   if (i == -1) return false;
203   if ((size_t)i != LUIdx) return true;
204   return UsedByIndices.find_next(i) != -1;
205 }
206
207 const SmallBitVector &RegUseTracker::getUsedByIndices(const SCEV *Reg) const {
208   RegUsesTy::const_iterator I = RegUsesMap.find(Reg);
209   assert(I != RegUsesMap.end() && "Unknown register!");
210   return I->second.UsedByIndices;
211 }
212
213 void RegUseTracker::clear() {
214   RegUsesMap.clear();
215   RegSequence.clear();
216 }
217
218 namespace {
219
220 /// Formula - This class holds information that describes a formula for
221 /// computing satisfying a use. It may include broken-out immediates and scaled
222 /// registers.
223 struct Formula {
224   /// AM - This is used to represent complex addressing, as well as other kinds
225   /// of interesting uses.
226   TargetLowering::AddrMode AM;
227
228   /// BaseRegs - The list of "base" registers for this use. When this is
229   /// non-empty, AM.HasBaseReg should be set to true.
230   SmallVector<const SCEV *, 2> BaseRegs;
231
232   /// ScaledReg - The 'scaled' register for this use. This should be non-null
233   /// when AM.Scale is not zero.
234   const SCEV *ScaledReg;
235
236   /// UnfoldedOffset - An additional constant offset which added near the
237   /// use. This requires a temporary register, but the offset itself can
238   /// live in an add immediate field rather than a register.
239   int64_t UnfoldedOffset;
240
241   Formula() : ScaledReg(0), UnfoldedOffset(0) {}
242
243   void InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE);
244
245   unsigned getNumRegs() const;
246   Type *getType() const;
247
248   void DeleteBaseReg(const SCEV *&S);
249
250   bool referencesReg(const SCEV *S) const;
251   bool hasRegsUsedByUsesOtherThan(size_t LUIdx,
252                                   const RegUseTracker &RegUses) const;
253
254   void print(raw_ostream &OS) const;
255   void dump() const;
256 };
257
258 }
259
260 /// DoInitialMatch - Recursion helper for InitialMatch.
261 static void DoInitialMatch(const SCEV *S, Loop *L,
262                            SmallVectorImpl<const SCEV *> &Good,
263                            SmallVectorImpl<const SCEV *> &Bad,
264                            ScalarEvolution &SE) {
265   // Collect expressions which properly dominate the loop header.
266   if (SE.properlyDominates(S, L->getHeader())) {
267     Good.push_back(S);
268     return;
269   }
270
271   // Look at add operands.
272   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
273     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
274          I != E; ++I)
275       DoInitialMatch(*I, L, Good, Bad, SE);
276     return;
277   }
278
279   // Look at addrec operands.
280   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
281     if (!AR->getStart()->isZero()) {
282       DoInitialMatch(AR->getStart(), L, Good, Bad, SE);
283       DoInitialMatch(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0),
284                                       AR->getStepRecurrence(SE),
285                                       // FIXME: AR->getNoWrapFlags()
286                                       AR->getLoop(), SCEV::FlagAnyWrap),
287                      L, Good, Bad, SE);
288       return;
289     }
290
291   // Handle a multiplication by -1 (negation) if it didn't fold.
292   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S))
293     if (Mul->getOperand(0)->isAllOnesValue()) {
294       SmallVector<const SCEV *, 4> Ops(Mul->op_begin()+1, Mul->op_end());
295       const SCEV *NewMul = SE.getMulExpr(Ops);
296
297       SmallVector<const SCEV *, 4> MyGood;
298       SmallVector<const SCEV *, 4> MyBad;
299       DoInitialMatch(NewMul, L, MyGood, MyBad, SE);
300       const SCEV *NegOne = SE.getSCEV(ConstantInt::getAllOnesValue(
301         SE.getEffectiveSCEVType(NewMul->getType())));
302       for (SmallVectorImpl<const SCEV *>::const_iterator I = MyGood.begin(),
303            E = MyGood.end(); I != E; ++I)
304         Good.push_back(SE.getMulExpr(NegOne, *I));
305       for (SmallVectorImpl<const SCEV *>::const_iterator I = MyBad.begin(),
306            E = MyBad.end(); I != E; ++I)
307         Bad.push_back(SE.getMulExpr(NegOne, *I));
308       return;
309     }
310
311   // Ok, we can't do anything interesting. Just stuff the whole thing into a
312   // register and hope for the best.
313   Bad.push_back(S);
314 }
315
316 /// InitialMatch - Incorporate loop-variant parts of S into this Formula,
317 /// attempting to keep all loop-invariant and loop-computable values in a
318 /// single base register.
319 void Formula::InitialMatch(const SCEV *S, Loop *L, ScalarEvolution &SE) {
320   SmallVector<const SCEV *, 4> Good;
321   SmallVector<const SCEV *, 4> Bad;
322   DoInitialMatch(S, L, Good, Bad, SE);
323   if (!Good.empty()) {
324     const SCEV *Sum = SE.getAddExpr(Good);
325     if (!Sum->isZero())
326       BaseRegs.push_back(Sum);
327     AM.HasBaseReg = true;
328   }
329   if (!Bad.empty()) {
330     const SCEV *Sum = SE.getAddExpr(Bad);
331     if (!Sum->isZero())
332       BaseRegs.push_back(Sum);
333     AM.HasBaseReg = true;
334   }
335 }
336
337 /// getNumRegs - Return the total number of register operands used by this
338 /// formula. This does not include register uses implied by non-constant
339 /// addrec strides.
340 unsigned Formula::getNumRegs() const {
341   return !!ScaledReg + BaseRegs.size();
342 }
343
344 /// getType - Return the type of this formula, if it has one, or null
345 /// otherwise. This type is meaningless except for the bit size.
346 Type *Formula::getType() const {
347   return !BaseRegs.empty() ? BaseRegs.front()->getType() :
348          ScaledReg ? ScaledReg->getType() :
349          AM.BaseGV ? AM.BaseGV->getType() :
350          0;
351 }
352
353 /// DeleteBaseReg - Delete the given base reg from the BaseRegs list.
354 void Formula::DeleteBaseReg(const SCEV *&S) {
355   if (&S != &BaseRegs.back())
356     std::swap(S, BaseRegs.back());
357   BaseRegs.pop_back();
358 }
359
360 /// referencesReg - Test if this formula references the given register.
361 bool Formula::referencesReg(const SCEV *S) const {
362   return S == ScaledReg ||
363          std::find(BaseRegs.begin(), BaseRegs.end(), S) != BaseRegs.end();
364 }
365
366 /// hasRegsUsedByUsesOtherThan - Test whether this formula uses registers
367 /// which are used by uses other than the use with the given index.
368 bool Formula::hasRegsUsedByUsesOtherThan(size_t LUIdx,
369                                          const RegUseTracker &RegUses) const {
370   if (ScaledReg)
371     if (RegUses.isRegUsedByUsesOtherThan(ScaledReg, LUIdx))
372       return true;
373   for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(),
374        E = BaseRegs.end(); I != E; ++I)
375     if (RegUses.isRegUsedByUsesOtherThan(*I, LUIdx))
376       return true;
377   return false;
378 }
379
380 void Formula::print(raw_ostream &OS) const {
381   bool First = true;
382   if (AM.BaseGV) {
383     if (!First) OS << " + "; else First = false;
384     WriteAsOperand(OS, AM.BaseGV, /*PrintType=*/false);
385   }
386   if (AM.BaseOffs != 0) {
387     if (!First) OS << " + "; else First = false;
388     OS << AM.BaseOffs;
389   }
390   for (SmallVectorImpl<const SCEV *>::const_iterator I = BaseRegs.begin(),
391        E = BaseRegs.end(); I != E; ++I) {
392     if (!First) OS << " + "; else First = false;
393     OS << "reg(" << **I << ')';
394   }
395   if (AM.HasBaseReg && BaseRegs.empty()) {
396     if (!First) OS << " + "; else First = false;
397     OS << "**error: HasBaseReg**";
398   } else if (!AM.HasBaseReg && !BaseRegs.empty()) {
399     if (!First) OS << " + "; else First = false;
400     OS << "**error: !HasBaseReg**";
401   }
402   if (AM.Scale != 0) {
403     if (!First) OS << " + "; else First = false;
404     OS << AM.Scale << "*reg(";
405     if (ScaledReg)
406       OS << *ScaledReg;
407     else
408       OS << "<unknown>";
409     OS << ')';
410   }
411   if (UnfoldedOffset != 0) {
412     if (!First) OS << " + "; else First = false;
413     OS << "imm(" << UnfoldedOffset << ')';
414   }
415 }
416
417 void Formula::dump() const {
418   print(errs()); errs() << '\n';
419 }
420
421 /// isAddRecSExtable - Return true if the given addrec can be sign-extended
422 /// without changing its value.
423 static bool isAddRecSExtable(const SCEVAddRecExpr *AR, ScalarEvolution &SE) {
424   Type *WideTy =
425     IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(AR->getType()) + 1);
426   return isa<SCEVAddRecExpr>(SE.getSignExtendExpr(AR, WideTy));
427 }
428
429 /// isAddSExtable - Return true if the given add can be sign-extended
430 /// without changing its value.
431 static bool isAddSExtable(const SCEVAddExpr *A, ScalarEvolution &SE) {
432   Type *WideTy =
433     IntegerType::get(SE.getContext(), SE.getTypeSizeInBits(A->getType()) + 1);
434   return isa<SCEVAddExpr>(SE.getSignExtendExpr(A, WideTy));
435 }
436
437 /// isMulSExtable - Return true if the given mul can be sign-extended
438 /// without changing its value.
439 static bool isMulSExtable(const SCEVMulExpr *M, ScalarEvolution &SE) {
440   Type *WideTy =
441     IntegerType::get(SE.getContext(),
442                      SE.getTypeSizeInBits(M->getType()) * M->getNumOperands());
443   return isa<SCEVMulExpr>(SE.getSignExtendExpr(M, WideTy));
444 }
445
446 /// getExactSDiv - Return an expression for LHS /s RHS, if it can be determined
447 /// and if the remainder is known to be zero,  or null otherwise. If
448 /// IgnoreSignificantBits is true, expressions like (X * Y) /s Y are simplified
449 /// to Y, ignoring that the multiplication may overflow, which is useful when
450 /// the result will be used in a context where the most significant bits are
451 /// ignored.
452 static const SCEV *getExactSDiv(const SCEV *LHS, const SCEV *RHS,
453                                 ScalarEvolution &SE,
454                                 bool IgnoreSignificantBits = false) {
455   // Handle the trivial case, which works for any SCEV type.
456   if (LHS == RHS)
457     return SE.getConstant(LHS->getType(), 1);
458
459   // Handle a few RHS special cases.
460   const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS);
461   if (RC) {
462     const APInt &RA = RC->getValue()->getValue();
463     // Handle x /s -1 as x * -1, to give ScalarEvolution a chance to do
464     // some folding.
465     if (RA.isAllOnesValue())
466       return SE.getMulExpr(LHS, RC);
467     // Handle x /s 1 as x.
468     if (RA == 1)
469       return LHS;
470   }
471
472   // Check for a division of a constant by a constant.
473   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(LHS)) {
474     if (!RC)
475       return 0;
476     const APInt &LA = C->getValue()->getValue();
477     const APInt &RA = RC->getValue()->getValue();
478     if (LA.srem(RA) != 0)
479       return 0;
480     return SE.getConstant(LA.sdiv(RA));
481   }
482
483   // Distribute the sdiv over addrec operands, if the addrec doesn't overflow.
484   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) {
485     if (IgnoreSignificantBits || isAddRecSExtable(AR, SE)) {
486       const SCEV *Step = getExactSDiv(AR->getStepRecurrence(SE), RHS, SE,
487                                       IgnoreSignificantBits);
488       if (!Step) return 0;
489       const SCEV *Start = getExactSDiv(AR->getStart(), RHS, SE,
490                                        IgnoreSignificantBits);
491       if (!Start) return 0;
492       // FlagNW is independent of the start value, step direction, and is
493       // preserved with smaller magnitude steps.
494       // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
495       return SE.getAddRecExpr(Start, Step, AR->getLoop(), SCEV::FlagAnyWrap);
496     }
497     return 0;
498   }
499
500   // Distribute the sdiv over add operands, if the add doesn't overflow.
501   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(LHS)) {
502     if (IgnoreSignificantBits || isAddSExtable(Add, SE)) {
503       SmallVector<const SCEV *, 8> Ops;
504       for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
505            I != E; ++I) {
506         const SCEV *Op = getExactSDiv(*I, RHS, SE,
507                                       IgnoreSignificantBits);
508         if (!Op) return 0;
509         Ops.push_back(Op);
510       }
511       return SE.getAddExpr(Ops);
512     }
513     return 0;
514   }
515
516   // Check for a multiply operand that we can pull RHS out of.
517   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(LHS)) {
518     if (IgnoreSignificantBits || isMulSExtable(Mul, SE)) {
519       SmallVector<const SCEV *, 4> Ops;
520       bool Found = false;
521       for (SCEVMulExpr::op_iterator I = Mul->op_begin(), E = Mul->op_end();
522            I != E; ++I) {
523         const SCEV *S = *I;
524         if (!Found)
525           if (const SCEV *Q = getExactSDiv(S, RHS, SE,
526                                            IgnoreSignificantBits)) {
527             S = Q;
528             Found = true;
529           }
530         Ops.push_back(S);
531       }
532       return Found ? SE.getMulExpr(Ops) : 0;
533     }
534     return 0;
535   }
536
537   // Otherwise we don't know.
538   return 0;
539 }
540
541 /// ExtractImmediate - If S involves the addition of a constant integer value,
542 /// return that integer value, and mutate S to point to a new SCEV with that
543 /// value excluded.
544 static int64_t ExtractImmediate(const SCEV *&S, ScalarEvolution &SE) {
545   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
546     if (C->getValue()->getValue().getMinSignedBits() <= 64) {
547       S = SE.getConstant(C->getType(), 0);
548       return C->getValue()->getSExtValue();
549     }
550   } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
551     SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
552     int64_t Result = ExtractImmediate(NewOps.front(), SE);
553     if (Result != 0)
554       S = SE.getAddExpr(NewOps);
555     return Result;
556   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
557     SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
558     int64_t Result = ExtractImmediate(NewOps.front(), SE);
559     if (Result != 0)
560       S = SE.getAddRecExpr(NewOps, AR->getLoop(),
561                            // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
562                            SCEV::FlagAnyWrap);
563     return Result;
564   }
565   return 0;
566 }
567
568 /// ExtractSymbol - If S involves the addition of a GlobalValue address,
569 /// return that symbol, and mutate S to point to a new SCEV with that
570 /// value excluded.
571 static GlobalValue *ExtractSymbol(const SCEV *&S, ScalarEvolution &SE) {
572   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
573     if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue())) {
574       S = SE.getConstant(GV->getType(), 0);
575       return GV;
576     }
577   } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
578     SmallVector<const SCEV *, 8> NewOps(Add->op_begin(), Add->op_end());
579     GlobalValue *Result = ExtractSymbol(NewOps.back(), SE);
580     if (Result)
581       S = SE.getAddExpr(NewOps);
582     return Result;
583   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
584     SmallVector<const SCEV *, 8> NewOps(AR->op_begin(), AR->op_end());
585     GlobalValue *Result = ExtractSymbol(NewOps.front(), SE);
586     if (Result)
587       S = SE.getAddRecExpr(NewOps, AR->getLoop(),
588                            // FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
589                            SCEV::FlagAnyWrap);
590     return Result;
591   }
592   return 0;
593 }
594
595 /// isAddressUse - Returns true if the specified instruction is using the
596 /// specified value as an address.
597 static bool isAddressUse(Instruction *Inst, Value *OperandVal) {
598   bool isAddress = isa<LoadInst>(Inst);
599   if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
600     if (SI->getOperand(1) == OperandVal)
601       isAddress = true;
602   } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
603     // Addressing modes can also be folded into prefetches and a variety
604     // of intrinsics.
605     switch (II->getIntrinsicID()) {
606       default: break;
607       case Intrinsic::prefetch:
608       case Intrinsic::x86_sse_storeu_ps:
609       case Intrinsic::x86_sse2_storeu_pd:
610       case Intrinsic::x86_sse2_storeu_dq:
611       case Intrinsic::x86_sse2_storel_dq:
612         if (II->getArgOperand(0) == OperandVal)
613           isAddress = true;
614         break;
615     }
616   }
617   return isAddress;
618 }
619
620 /// getAccessType - Return the type of the memory being accessed.
621 static Type *getAccessType(const Instruction *Inst) {
622   Type *AccessTy = Inst->getType();
623   if (const StoreInst *SI = dyn_cast<StoreInst>(Inst))
624     AccessTy = SI->getOperand(0)->getType();
625   else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
626     // Addressing modes can also be folded into prefetches and a variety
627     // of intrinsics.
628     switch (II->getIntrinsicID()) {
629     default: break;
630     case Intrinsic::x86_sse_storeu_ps:
631     case Intrinsic::x86_sse2_storeu_pd:
632     case Intrinsic::x86_sse2_storeu_dq:
633     case Intrinsic::x86_sse2_storel_dq:
634       AccessTy = II->getArgOperand(0)->getType();
635       break;
636     }
637   }
638
639   // All pointers have the same requirements, so canonicalize them to an
640   // arbitrary pointer type to minimize variation.
641   if (PointerType *PTy = dyn_cast<PointerType>(AccessTy))
642     AccessTy = PointerType::get(IntegerType::get(PTy->getContext(), 1),
643                                 PTy->getAddressSpace());
644
645   return AccessTy;
646 }
647
648 /// isExistingPhi - Return true if this AddRec is already a phi in its loop.
649 static bool isExistingPhi(const SCEVAddRecExpr *AR, ScalarEvolution &SE) {
650   for (BasicBlock::iterator I = AR->getLoop()->getHeader()->begin();
651        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
652     if (SE.isSCEVable(PN->getType()) &&
653         (SE.getEffectiveSCEVType(PN->getType()) ==
654          SE.getEffectiveSCEVType(AR->getType())) &&
655         SE.getSCEV(PN) == AR)
656       return true;
657   }
658   return false;
659 }
660
661 /// Check if expanding this expression is likely to incur significant cost. This
662 /// is tricky because SCEV doesn't track which expressions are actually computed
663 /// by the current IR.
664 ///
665 /// We currently allow expansion of IV increments that involve adds,
666 /// multiplication by constants, and AddRecs from existing phis.
667 ///
668 /// TODO: Allow UDivExpr if we can find an existing IV increment that is an
669 /// obvious multiple of the UDivExpr.
670 static bool isHighCostExpansion(const SCEV *S,
671                                 SmallPtrSet<const SCEV*, 8> &Processed,
672                                 ScalarEvolution &SE) {
673   // Zero/One operand expressions
674   switch (S->getSCEVType()) {
675   case scUnknown:
676   case scConstant:
677     return false;
678   case scTruncate:
679     return isHighCostExpansion(cast<SCEVTruncateExpr>(S)->getOperand(),
680                                Processed, SE);
681   case scZeroExtend:
682     return isHighCostExpansion(cast<SCEVZeroExtendExpr>(S)->getOperand(),
683                                Processed, SE);
684   case scSignExtend:
685     return isHighCostExpansion(cast<SCEVSignExtendExpr>(S)->getOperand(),
686                                Processed, SE);
687   }
688
689   if (!Processed.insert(S))
690     return false;
691
692   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
693     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
694          I != E; ++I) {
695       if (isHighCostExpansion(*I, Processed, SE))
696         return true;
697     }
698     return false;
699   }
700
701   if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
702     if (Mul->getNumOperands() == 2) {
703       // Multiplication by a constant is ok
704       if (isa<SCEVConstant>(Mul->getOperand(0)))
705         return isHighCostExpansion(Mul->getOperand(1), Processed, SE);
706
707       // If we have the value of one operand, check if an existing
708       // multiplication already generates this expression.
709       if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(Mul->getOperand(1))) {
710         Value *UVal = U->getValue();
711         for (Value::use_iterator UI = UVal->use_begin(), UE = UVal->use_end();
712              UI != UE; ++UI) {
713           // If U is a constant, it may be used by a ConstantExpr.
714           Instruction *User = dyn_cast<Instruction>(*UI);
715           if (User && User->getOpcode() == Instruction::Mul
716               && SE.isSCEVable(User->getType())) {
717             return SE.getSCEV(User) == Mul;
718           }
719         }
720       }
721     }
722   }
723
724   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
725     if (isExistingPhi(AR, SE))
726       return false;
727   }
728
729   // Fow now, consider any other type of expression (div/mul/min/max) high cost.
730   return true;
731 }
732
733 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
734 /// specified set are trivially dead, delete them and see if this makes any of
735 /// their operands subsequently dead.
736 static bool
737 DeleteTriviallyDeadInstructions(SmallVectorImpl<WeakVH> &DeadInsts) {
738   bool Changed = false;
739
740   while (!DeadInsts.empty()) {
741     Instruction *I = dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val());
742
743     if (I == 0 || !isInstructionTriviallyDead(I))
744       continue;
745
746     for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI)
747       if (Instruction *U = dyn_cast<Instruction>(*OI)) {
748         *OI = 0;
749         if (U->use_empty())
750           DeadInsts.push_back(U);
751       }
752
753     I->eraseFromParent();
754     Changed = true;
755   }
756
757   return Changed;
758 }
759
760 namespace {
761
762 /// Cost - This class is used to measure and compare candidate formulae.
763 class Cost {
764   /// TODO: Some of these could be merged. Also, a lexical ordering
765   /// isn't always optimal.
766   unsigned NumRegs;
767   unsigned AddRecCost;
768   unsigned NumIVMuls;
769   unsigned NumBaseAdds;
770   unsigned ImmCost;
771   unsigned SetupCost;
772
773 public:
774   Cost()
775     : NumRegs(0), AddRecCost(0), NumIVMuls(0), NumBaseAdds(0), ImmCost(0),
776       SetupCost(0) {}
777
778   bool operator<(const Cost &Other) const;
779
780   void Loose();
781
782 #ifndef NDEBUG
783   // Once any of the metrics loses, they must all remain losers.
784   bool isValid() {
785     return ((NumRegs | AddRecCost | NumIVMuls | NumBaseAdds
786              | ImmCost | SetupCost) != ~0u)
787       || ((NumRegs & AddRecCost & NumIVMuls & NumBaseAdds
788            & ImmCost & SetupCost) == ~0u);
789   }
790 #endif
791
792   bool isLoser() {
793     assert(isValid() && "invalid cost");
794     return NumRegs == ~0u;
795   }
796
797   void RateFormula(const Formula &F,
798                    SmallPtrSet<const SCEV *, 16> &Regs,
799                    const DenseSet<const SCEV *> &VisitedRegs,
800                    const Loop *L,
801                    const SmallVectorImpl<int64_t> &Offsets,
802                    ScalarEvolution &SE, DominatorTree &DT,
803                    SmallPtrSet<const SCEV *, 16> *LoserRegs = 0);
804
805   void print(raw_ostream &OS) const;
806   void dump() const;
807
808 private:
809   void RateRegister(const SCEV *Reg,
810                     SmallPtrSet<const SCEV *, 16> &Regs,
811                     const Loop *L,
812                     ScalarEvolution &SE, DominatorTree &DT);
813   void RatePrimaryRegister(const SCEV *Reg,
814                            SmallPtrSet<const SCEV *, 16> &Regs,
815                            const Loop *L,
816                            ScalarEvolution &SE, DominatorTree &DT,
817                            SmallPtrSet<const SCEV *, 16> *LoserRegs);
818 };
819
820 }
821
822 /// RateRegister - Tally up interesting quantities from the given register.
823 void Cost::RateRegister(const SCEV *Reg,
824                         SmallPtrSet<const SCEV *, 16> &Regs,
825                         const Loop *L,
826                         ScalarEvolution &SE, DominatorTree &DT) {
827   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Reg)) {
828     // If this is an addrec for another loop, don't second-guess its addrec phi
829     // nodes. LSR isn't currently smart enough to reason about more than one
830     // loop at a time. LSR has already run on inner loops, will not run on outer
831     // loops, and cannot be expected to change sibling loops.
832     if (AR->getLoop() != L) {
833       // If the AddRec exists, consider it's register free and leave it alone.
834       if (isExistingPhi(AR, SE))
835         return;
836
837       // Otherwise, do not consider this formula at all.
838       Loose();
839       return;
840     }
841     AddRecCost += 1; /// TODO: This should be a function of the stride.
842
843     // Add the step value register, if it needs one.
844     // TODO: The non-affine case isn't precisely modeled here.
845     if (!AR->isAffine() || !isa<SCEVConstant>(AR->getOperand(1))) {
846       if (!Regs.count(AR->getOperand(1))) {
847         RateRegister(AR->getOperand(1), Regs, L, SE, DT);
848         if (isLoser())
849           return;
850       }
851     }
852   }
853   ++NumRegs;
854
855   // Rough heuristic; favor registers which don't require extra setup
856   // instructions in the preheader.
857   if (!isa<SCEVUnknown>(Reg) &&
858       !isa<SCEVConstant>(Reg) &&
859       !(isa<SCEVAddRecExpr>(Reg) &&
860         (isa<SCEVUnknown>(cast<SCEVAddRecExpr>(Reg)->getStart()) ||
861          isa<SCEVConstant>(cast<SCEVAddRecExpr>(Reg)->getStart()))))
862     ++SetupCost;
863
864     NumIVMuls += isa<SCEVMulExpr>(Reg) &&
865                  SE.hasComputableLoopEvolution(Reg, L);
866 }
867
868 /// RatePrimaryRegister - Record this register in the set. If we haven't seen it
869 /// before, rate it. Optional LoserRegs provides a way to declare any formula
870 /// that refers to one of those regs an instant loser.
871 void Cost::RatePrimaryRegister(const SCEV *Reg,
872                                SmallPtrSet<const SCEV *, 16> &Regs,
873                                const Loop *L,
874                                ScalarEvolution &SE, DominatorTree &DT,
875                                SmallPtrSet<const SCEV *, 16> *LoserRegs) {
876   if (LoserRegs && LoserRegs->count(Reg)) {
877     Loose();
878     return;
879   }
880   if (Regs.insert(Reg)) {
881     RateRegister(Reg, Regs, L, SE, DT);
882     if (isLoser())
883       LoserRegs->insert(Reg);
884   }
885 }
886
887 void Cost::RateFormula(const Formula &F,
888                        SmallPtrSet<const SCEV *, 16> &Regs,
889                        const DenseSet<const SCEV *> &VisitedRegs,
890                        const Loop *L,
891                        const SmallVectorImpl<int64_t> &Offsets,
892                        ScalarEvolution &SE, DominatorTree &DT,
893                        SmallPtrSet<const SCEV *, 16> *LoserRegs) {
894   // Tally up the registers.
895   if (const SCEV *ScaledReg = F.ScaledReg) {
896     if (VisitedRegs.count(ScaledReg)) {
897       Loose();
898       return;
899     }
900     RatePrimaryRegister(ScaledReg, Regs, L, SE, DT, LoserRegs);
901     if (isLoser())
902       return;
903   }
904   for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
905        E = F.BaseRegs.end(); I != E; ++I) {
906     const SCEV *BaseReg = *I;
907     if (VisitedRegs.count(BaseReg)) {
908       Loose();
909       return;
910     }
911     RatePrimaryRegister(BaseReg, Regs, L, SE, DT, LoserRegs);
912     if (isLoser())
913       return;
914   }
915
916   // Determine how many (unfolded) adds we'll need inside the loop.
917   size_t NumBaseParts = F.BaseRegs.size() + (F.UnfoldedOffset != 0);
918   if (NumBaseParts > 1)
919     NumBaseAdds += NumBaseParts - 1;
920
921   // Tally up the non-zero immediates.
922   for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(),
923        E = Offsets.end(); I != E; ++I) {
924     int64_t Offset = (uint64_t)*I + F.AM.BaseOffs;
925     if (F.AM.BaseGV)
926       ImmCost += 64; // Handle symbolic values conservatively.
927                      // TODO: This should probably be the pointer size.
928     else if (Offset != 0)
929       ImmCost += APInt(64, Offset, true).getMinSignedBits();
930   }
931   assert(isValid() && "invalid cost");
932 }
933
934 /// Loose - Set this cost to a losing value.
935 void Cost::Loose() {
936   NumRegs = ~0u;
937   AddRecCost = ~0u;
938   NumIVMuls = ~0u;
939   NumBaseAdds = ~0u;
940   ImmCost = ~0u;
941   SetupCost = ~0u;
942 }
943
944 /// operator< - Choose the lower cost.
945 bool Cost::operator<(const Cost &Other) const {
946   if (NumRegs != Other.NumRegs)
947     return NumRegs < Other.NumRegs;
948   if (AddRecCost != Other.AddRecCost)
949     return AddRecCost < Other.AddRecCost;
950   if (NumIVMuls != Other.NumIVMuls)
951     return NumIVMuls < Other.NumIVMuls;
952   if (NumBaseAdds != Other.NumBaseAdds)
953     return NumBaseAdds < Other.NumBaseAdds;
954   if (ImmCost != Other.ImmCost)
955     return ImmCost < Other.ImmCost;
956   if (SetupCost != Other.SetupCost)
957     return SetupCost < Other.SetupCost;
958   return false;
959 }
960
961 void Cost::print(raw_ostream &OS) const {
962   OS << NumRegs << " reg" << (NumRegs == 1 ? "" : "s");
963   if (AddRecCost != 0)
964     OS << ", with addrec cost " << AddRecCost;
965   if (NumIVMuls != 0)
966     OS << ", plus " << NumIVMuls << " IV mul" << (NumIVMuls == 1 ? "" : "s");
967   if (NumBaseAdds != 0)
968     OS << ", plus " << NumBaseAdds << " base add"
969        << (NumBaseAdds == 1 ? "" : "s");
970   if (ImmCost != 0)
971     OS << ", plus " << ImmCost << " imm cost";
972   if (SetupCost != 0)
973     OS << ", plus " << SetupCost << " setup cost";
974 }
975
976 void Cost::dump() const {
977   print(errs()); errs() << '\n';
978 }
979
980 namespace {
981
982 /// LSRFixup - An operand value in an instruction which is to be replaced
983 /// with some equivalent, possibly strength-reduced, replacement.
984 struct LSRFixup {
985   /// UserInst - The instruction which will be updated.
986   Instruction *UserInst;
987
988   /// OperandValToReplace - The operand of the instruction which will
989   /// be replaced. The operand may be used more than once; every instance
990   /// will be replaced.
991   Value *OperandValToReplace;
992
993   /// PostIncLoops - If this user is to use the post-incremented value of an
994   /// induction variable, this variable is non-null and holds the loop
995   /// associated with the induction variable.
996   PostIncLoopSet PostIncLoops;
997
998   /// LUIdx - The index of the LSRUse describing the expression which
999   /// this fixup needs, minus an offset (below).
1000   size_t LUIdx;
1001
1002   /// Offset - A constant offset to be added to the LSRUse expression.
1003   /// This allows multiple fixups to share the same LSRUse with different
1004   /// offsets, for example in an unrolled loop.
1005   int64_t Offset;
1006
1007   bool isUseFullyOutsideLoop(const Loop *L) const;
1008
1009   LSRFixup();
1010
1011   void print(raw_ostream &OS) const;
1012   void dump() const;
1013 };
1014
1015 }
1016
1017 LSRFixup::LSRFixup()
1018   : UserInst(0), OperandValToReplace(0), LUIdx(~size_t(0)), Offset(0) {}
1019
1020 /// isUseFullyOutsideLoop - Test whether this fixup always uses its
1021 /// value outside of the given loop.
1022 bool LSRFixup::isUseFullyOutsideLoop(const Loop *L) const {
1023   // PHI nodes use their value in their incoming blocks.
1024   if (const PHINode *PN = dyn_cast<PHINode>(UserInst)) {
1025     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
1026       if (PN->getIncomingValue(i) == OperandValToReplace &&
1027           L->contains(PN->getIncomingBlock(i)))
1028         return false;
1029     return true;
1030   }
1031
1032   return !L->contains(UserInst);
1033 }
1034
1035 void LSRFixup::print(raw_ostream &OS) const {
1036   OS << "UserInst=";
1037   // Store is common and interesting enough to be worth special-casing.
1038   if (StoreInst *Store = dyn_cast<StoreInst>(UserInst)) {
1039     OS << "store ";
1040     WriteAsOperand(OS, Store->getOperand(0), /*PrintType=*/false);
1041   } else if (UserInst->getType()->isVoidTy())
1042     OS << UserInst->getOpcodeName();
1043   else
1044     WriteAsOperand(OS, UserInst, /*PrintType=*/false);
1045
1046   OS << ", OperandValToReplace=";
1047   WriteAsOperand(OS, OperandValToReplace, /*PrintType=*/false);
1048
1049   for (PostIncLoopSet::const_iterator I = PostIncLoops.begin(),
1050        E = PostIncLoops.end(); I != E; ++I) {
1051     OS << ", PostIncLoop=";
1052     WriteAsOperand(OS, (*I)->getHeader(), /*PrintType=*/false);
1053   }
1054
1055   if (LUIdx != ~size_t(0))
1056     OS << ", LUIdx=" << LUIdx;
1057
1058   if (Offset != 0)
1059     OS << ", Offset=" << Offset;
1060 }
1061
1062 void LSRFixup::dump() const {
1063   print(errs()); errs() << '\n';
1064 }
1065
1066 namespace {
1067
1068 /// UniquifierDenseMapInfo - A DenseMapInfo implementation for holding
1069 /// DenseMaps and DenseSets of sorted SmallVectors of const SCEV*.
1070 struct UniquifierDenseMapInfo {
1071   static SmallVector<const SCEV *, 2> getEmptyKey() {
1072     SmallVector<const SCEV *, 2> V;
1073     V.push_back(reinterpret_cast<const SCEV *>(-1));
1074     return V;
1075   }
1076
1077   static SmallVector<const SCEV *, 2> getTombstoneKey() {
1078     SmallVector<const SCEV *, 2> V;
1079     V.push_back(reinterpret_cast<const SCEV *>(-2));
1080     return V;
1081   }
1082
1083   static unsigned getHashValue(const SmallVector<const SCEV *, 2> &V) {
1084     unsigned Result = 0;
1085     for (SmallVectorImpl<const SCEV *>::const_iterator I = V.begin(),
1086          E = V.end(); I != E; ++I)
1087       Result ^= DenseMapInfo<const SCEV *>::getHashValue(*I);
1088     return Result;
1089   }
1090
1091   static bool isEqual(const SmallVector<const SCEV *, 2> &LHS,
1092                       const SmallVector<const SCEV *, 2> &RHS) {
1093     return LHS == RHS;
1094   }
1095 };
1096
1097 /// LSRUse - This class holds the state that LSR keeps for each use in
1098 /// IVUsers, as well as uses invented by LSR itself. It includes information
1099 /// about what kinds of things can be folded into the user, information about
1100 /// the user itself, and information about how the use may be satisfied.
1101 /// TODO: Represent multiple users of the same expression in common?
1102 class LSRUse {
1103   DenseSet<SmallVector<const SCEV *, 2>, UniquifierDenseMapInfo> Uniquifier;
1104
1105 public:
1106   /// KindType - An enum for a kind of use, indicating what types of
1107   /// scaled and immediate operands it might support.
1108   enum KindType {
1109     Basic,   ///< A normal use, with no folding.
1110     Special, ///< A special case of basic, allowing -1 scales.
1111     Address, ///< An address use; folding according to TargetLowering
1112     ICmpZero ///< An equality icmp with both operands folded into one.
1113     // TODO: Add a generic icmp too?
1114   };
1115
1116   KindType Kind;
1117   Type *AccessTy;
1118
1119   SmallVector<int64_t, 8> Offsets;
1120   int64_t MinOffset;
1121   int64_t MaxOffset;
1122
1123   /// AllFixupsOutsideLoop - This records whether all of the fixups using this
1124   /// LSRUse are outside of the loop, in which case some special-case heuristics
1125   /// may be used.
1126   bool AllFixupsOutsideLoop;
1127
1128   /// WidestFixupType - This records the widest use type for any fixup using
1129   /// this LSRUse. FindUseWithSimilarFormula can't consider uses with different
1130   /// max fixup widths to be equivalent, because the narrower one may be relying
1131   /// on the implicit truncation to truncate away bogus bits.
1132   Type *WidestFixupType;
1133
1134   /// Formulae - A list of ways to build a value that can satisfy this user.
1135   /// After the list is populated, one of these is selected heuristically and
1136   /// used to formulate a replacement for OperandValToReplace in UserInst.
1137   SmallVector<Formula, 12> Formulae;
1138
1139   /// Regs - The set of register candidates used by all formulae in this LSRUse.
1140   SmallPtrSet<const SCEV *, 4> Regs;
1141
1142   LSRUse(KindType K, Type *T) : Kind(K), AccessTy(T),
1143                                       MinOffset(INT64_MAX),
1144                                       MaxOffset(INT64_MIN),
1145                                       AllFixupsOutsideLoop(true),
1146                                       WidestFixupType(0) {}
1147
1148   bool HasFormulaWithSameRegs(const Formula &F) const;
1149   bool InsertFormula(const Formula &F);
1150   void DeleteFormula(Formula &F);
1151   void RecomputeRegs(size_t LUIdx, RegUseTracker &Reguses);
1152
1153   void print(raw_ostream &OS) const;
1154   void dump() const;
1155 };
1156
1157 }
1158
1159 /// HasFormula - Test whether this use as a formula which has the same
1160 /// registers as the given formula.
1161 bool LSRUse::HasFormulaWithSameRegs(const Formula &F) const {
1162   SmallVector<const SCEV *, 2> Key = F.BaseRegs;
1163   if (F.ScaledReg) Key.push_back(F.ScaledReg);
1164   // Unstable sort by host order ok, because this is only used for uniquifying.
1165   std::sort(Key.begin(), Key.end());
1166   return Uniquifier.count(Key);
1167 }
1168
1169 /// InsertFormula - If the given formula has not yet been inserted, add it to
1170 /// the list, and return true. Return false otherwise.
1171 bool LSRUse::InsertFormula(const Formula &F) {
1172   SmallVector<const SCEV *, 2> Key = F.BaseRegs;
1173   if (F.ScaledReg) Key.push_back(F.ScaledReg);
1174   // Unstable sort by host order ok, because this is only used for uniquifying.
1175   std::sort(Key.begin(), Key.end());
1176
1177   if (!Uniquifier.insert(Key).second)
1178     return false;
1179
1180   // Using a register to hold the value of 0 is not profitable.
1181   assert((!F.ScaledReg || !F.ScaledReg->isZero()) &&
1182          "Zero allocated in a scaled register!");
1183 #ifndef NDEBUG
1184   for (SmallVectorImpl<const SCEV *>::const_iterator I =
1185        F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I)
1186     assert(!(*I)->isZero() && "Zero allocated in a base register!");
1187 #endif
1188
1189   // Add the formula to the list.
1190   Formulae.push_back(F);
1191
1192   // Record registers now being used by this use.
1193   Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end());
1194
1195   return true;
1196 }
1197
1198 /// DeleteFormula - Remove the given formula from this use's list.
1199 void LSRUse::DeleteFormula(Formula &F) {
1200   if (&F != &Formulae.back())
1201     std::swap(F, Formulae.back());
1202   Formulae.pop_back();
1203 }
1204
1205 /// RecomputeRegs - Recompute the Regs field, and update RegUses.
1206 void LSRUse::RecomputeRegs(size_t LUIdx, RegUseTracker &RegUses) {
1207   // Now that we've filtered out some formulae, recompute the Regs set.
1208   SmallPtrSet<const SCEV *, 4> OldRegs = Regs;
1209   Regs.clear();
1210   for (SmallVectorImpl<Formula>::const_iterator I = Formulae.begin(),
1211        E = Formulae.end(); I != E; ++I) {
1212     const Formula &F = *I;
1213     if (F.ScaledReg) Regs.insert(F.ScaledReg);
1214     Regs.insert(F.BaseRegs.begin(), F.BaseRegs.end());
1215   }
1216
1217   // Update the RegTracker.
1218   for (SmallPtrSet<const SCEV *, 4>::iterator I = OldRegs.begin(),
1219        E = OldRegs.end(); I != E; ++I)
1220     if (!Regs.count(*I))
1221       RegUses.DropRegister(*I, LUIdx);
1222 }
1223
1224 void LSRUse::print(raw_ostream &OS) const {
1225   OS << "LSR Use: Kind=";
1226   switch (Kind) {
1227   case Basic:    OS << "Basic"; break;
1228   case Special:  OS << "Special"; break;
1229   case ICmpZero: OS << "ICmpZero"; break;
1230   case Address:
1231     OS << "Address of ";
1232     if (AccessTy->isPointerTy())
1233       OS << "pointer"; // the full pointer type could be really verbose
1234     else
1235       OS << *AccessTy;
1236   }
1237
1238   OS << ", Offsets={";
1239   for (SmallVectorImpl<int64_t>::const_iterator I = Offsets.begin(),
1240        E = Offsets.end(); I != E; ++I) {
1241     OS << *I;
1242     if (llvm::next(I) != E)
1243       OS << ',';
1244   }
1245   OS << '}';
1246
1247   if (AllFixupsOutsideLoop)
1248     OS << ", all-fixups-outside-loop";
1249
1250   if (WidestFixupType)
1251     OS << ", widest fixup type: " << *WidestFixupType;
1252 }
1253
1254 void LSRUse::dump() const {
1255   print(errs()); errs() << '\n';
1256 }
1257
1258 /// isLegalUse - Test whether the use described by AM is "legal", meaning it can
1259 /// be completely folded into the user instruction at isel time. This includes
1260 /// address-mode folding and special icmp tricks.
1261 static bool isLegalUse(const TargetLowering::AddrMode &AM,
1262                        LSRUse::KindType Kind, Type *AccessTy,
1263                        const TargetLowering *TLI) {
1264   switch (Kind) {
1265   case LSRUse::Address:
1266     // If we have low-level target information, ask the target if it can
1267     // completely fold this address.
1268     if (TLI) return TLI->isLegalAddressingMode(AM, AccessTy);
1269
1270     // Otherwise, just guess that reg+reg addressing is legal.
1271     return !AM.BaseGV && AM.BaseOffs == 0 && AM.Scale <= 1;
1272
1273   case LSRUse::ICmpZero:
1274     // There's not even a target hook for querying whether it would be legal to
1275     // fold a GV into an ICmp.
1276     if (AM.BaseGV)
1277       return false;
1278
1279     // ICmp only has two operands; don't allow more than two non-trivial parts.
1280     if (AM.Scale != 0 && AM.HasBaseReg && AM.BaseOffs != 0)
1281       return false;
1282
1283     // ICmp only supports no scale or a -1 scale, as we can "fold" a -1 scale by
1284     // putting the scaled register in the other operand of the icmp.
1285     if (AM.Scale != 0 && AM.Scale != -1)
1286       return false;
1287
1288     // If we have low-level target information, ask the target if it can fold an
1289     // integer immediate on an icmp.
1290     if (AM.BaseOffs != 0) {
1291       if (!TLI)
1292         return false;
1293       // We have one of:
1294       // ICmpZero     BaseReg + Offset => ICmp BaseReg, -Offset
1295       // ICmpZero -1*ScaleReg + Offset => ICmp ScaleReg, Offset
1296       // Offs is the ICmp immediate.
1297       int64_t Offs = AM.BaseOffs;
1298       if (AM.Scale == 0)
1299         Offs = -(uint64_t)Offs; // The cast does the right thing with INT64_MIN.
1300       return TLI->isLegalICmpImmediate(Offs);
1301     }
1302
1303     // ICmpZero BaseReg + -1*ScaleReg => ICmp BaseReg, ScaleReg
1304     return true;
1305
1306   case LSRUse::Basic:
1307     // Only handle single-register values.
1308     return !AM.BaseGV && AM.Scale == 0 && AM.BaseOffs == 0;
1309
1310   case LSRUse::Special:
1311     // Only handle -1 scales, or no scale.
1312     return AM.Scale == 0 || AM.Scale == -1;
1313   }
1314
1315   llvm_unreachable("Invalid LSRUse Kind!");
1316 }
1317
1318 static bool isLegalUse(TargetLowering::AddrMode AM,
1319                        int64_t MinOffset, int64_t MaxOffset,
1320                        LSRUse::KindType Kind, Type *AccessTy,
1321                        const TargetLowering *TLI) {
1322   // Check for overflow.
1323   if (((int64_t)((uint64_t)AM.BaseOffs + MinOffset) > AM.BaseOffs) !=
1324       (MinOffset > 0))
1325     return false;
1326   AM.BaseOffs = (uint64_t)AM.BaseOffs + MinOffset;
1327   if (isLegalUse(AM, Kind, AccessTy, TLI)) {
1328     AM.BaseOffs = (uint64_t)AM.BaseOffs - MinOffset;
1329     // Check for overflow.
1330     if (((int64_t)((uint64_t)AM.BaseOffs + MaxOffset) > AM.BaseOffs) !=
1331         (MaxOffset > 0))
1332       return false;
1333     AM.BaseOffs = (uint64_t)AM.BaseOffs + MaxOffset;
1334     return isLegalUse(AM, Kind, AccessTy, TLI);
1335   }
1336   return false;
1337 }
1338
1339 static bool isAlwaysFoldable(int64_t BaseOffs,
1340                              GlobalValue *BaseGV,
1341                              bool HasBaseReg,
1342                              LSRUse::KindType Kind, Type *AccessTy,
1343                              const TargetLowering *TLI) {
1344   // Fast-path: zero is always foldable.
1345   if (BaseOffs == 0 && !BaseGV) return true;
1346
1347   // Conservatively, create an address with an immediate and a
1348   // base and a scale.
1349   TargetLowering::AddrMode AM;
1350   AM.BaseOffs = BaseOffs;
1351   AM.BaseGV = BaseGV;
1352   AM.HasBaseReg = HasBaseReg;
1353   AM.Scale = Kind == LSRUse::ICmpZero ? -1 : 1;
1354
1355   // Canonicalize a scale of 1 to a base register if the formula doesn't
1356   // already have a base register.
1357   if (!AM.HasBaseReg && AM.Scale == 1) {
1358     AM.Scale = 0;
1359     AM.HasBaseReg = true;
1360   }
1361
1362   return isLegalUse(AM, Kind, AccessTy, TLI);
1363 }
1364
1365 static bool isAlwaysFoldable(const SCEV *S,
1366                              int64_t MinOffset, int64_t MaxOffset,
1367                              bool HasBaseReg,
1368                              LSRUse::KindType Kind, Type *AccessTy,
1369                              const TargetLowering *TLI,
1370                              ScalarEvolution &SE) {
1371   // Fast-path: zero is always foldable.
1372   if (S->isZero()) return true;
1373
1374   // Conservatively, create an address with an immediate and a
1375   // base and a scale.
1376   int64_t BaseOffs = ExtractImmediate(S, SE);
1377   GlobalValue *BaseGV = ExtractSymbol(S, SE);
1378
1379   // If there's anything else involved, it's not foldable.
1380   if (!S->isZero()) return false;
1381
1382   // Fast-path: zero is always foldable.
1383   if (BaseOffs == 0 && !BaseGV) return true;
1384
1385   // Conservatively, create an address with an immediate and a
1386   // base and a scale.
1387   TargetLowering::AddrMode AM;
1388   AM.BaseOffs = BaseOffs;
1389   AM.BaseGV = BaseGV;
1390   AM.HasBaseReg = HasBaseReg;
1391   AM.Scale = Kind == LSRUse::ICmpZero ? -1 : 1;
1392
1393   return isLegalUse(AM, MinOffset, MaxOffset, Kind, AccessTy, TLI);
1394 }
1395
1396 namespace {
1397
1398 /// UseMapDenseMapInfo - A DenseMapInfo implementation for holding
1399 /// DenseMaps and DenseSets of pairs of const SCEV* and LSRUse::Kind.
1400 struct UseMapDenseMapInfo {
1401   static std::pair<const SCEV *, LSRUse::KindType> getEmptyKey() {
1402     return std::make_pair(reinterpret_cast<const SCEV *>(-1), LSRUse::Basic);
1403   }
1404
1405   static std::pair<const SCEV *, LSRUse::KindType> getTombstoneKey() {
1406     return std::make_pair(reinterpret_cast<const SCEV *>(-2), LSRUse::Basic);
1407   }
1408
1409   static unsigned
1410   getHashValue(const std::pair<const SCEV *, LSRUse::KindType> &V) {
1411     unsigned Result = DenseMapInfo<const SCEV *>::getHashValue(V.first);
1412     Result ^= DenseMapInfo<unsigned>::getHashValue(unsigned(V.second));
1413     return Result;
1414   }
1415
1416   static bool isEqual(const std::pair<const SCEV *, LSRUse::KindType> &LHS,
1417                       const std::pair<const SCEV *, LSRUse::KindType> &RHS) {
1418     return LHS == RHS;
1419   }
1420 };
1421
1422 /// IVInc - An individual increment in a Chain of IV increments.
1423 /// Relate an IV user to an expression that computes the IV it uses from the IV
1424 /// used by the previous link in the Chain.
1425 ///
1426 /// For the head of a chain, IncExpr holds the absolute SCEV expression for the
1427 /// original IVOperand. The head of the chain's IVOperand is only valid during
1428 /// chain collection, before LSR replaces IV users. During chain generation,
1429 /// IncExpr can be used to find the new IVOperand that computes the same
1430 /// expression.
1431 struct IVInc {
1432   Instruction *UserInst;
1433   Value* IVOperand;
1434   const SCEV *IncExpr;
1435
1436   IVInc(Instruction *U, Value *O, const SCEV *E):
1437     UserInst(U), IVOperand(O), IncExpr(E) {}
1438 };
1439
1440 // IVChain - The list of IV increments in program order.
1441 // We typically add the head of a chain without finding subsequent links.
1442 typedef SmallVector<IVInc,1> IVChain;
1443
1444 /// ChainUsers - Helper for CollectChains to track multiple IV increment uses.
1445 /// Distinguish between FarUsers that definitely cross IV increments and
1446 /// NearUsers that may be used between IV increments.
1447 struct ChainUsers {
1448   SmallPtrSet<Instruction*, 4> FarUsers;
1449   SmallPtrSet<Instruction*, 4> NearUsers;
1450 };
1451
1452 /// LSRInstance - This class holds state for the main loop strength reduction
1453 /// logic.
1454 class LSRInstance {
1455   IVUsers &IU;
1456   ScalarEvolution &SE;
1457   DominatorTree &DT;
1458   LoopInfo &LI;
1459   const TargetLowering *const TLI;
1460   Loop *const L;
1461   bool Changed;
1462
1463   /// IVIncInsertPos - This is the insert position that the current loop's
1464   /// induction variable increment should be placed. In simple loops, this is
1465   /// the latch block's terminator. But in more complicated cases, this is a
1466   /// position which will dominate all the in-loop post-increment users.
1467   Instruction *IVIncInsertPos;
1468
1469   /// Factors - Interesting factors between use strides.
1470   SmallSetVector<int64_t, 8> Factors;
1471
1472   /// Types - Interesting use types, to facilitate truncation reuse.
1473   SmallSetVector<Type *, 4> Types;
1474
1475   /// Fixups - The list of operands which are to be replaced.
1476   SmallVector<LSRFixup, 16> Fixups;
1477
1478   /// Uses - The list of interesting uses.
1479   SmallVector<LSRUse, 16> Uses;
1480
1481   /// RegUses - Track which uses use which register candidates.
1482   RegUseTracker RegUses;
1483
1484   // Limit the number of chains to avoid quadratic behavior. We don't expect to
1485   // have more than a few IV increment chains in a loop. Missing a Chain falls
1486   // back to normal LSR behavior for those uses.
1487   static const unsigned MaxChains = 8;
1488
1489   /// IVChainVec - IV users can form a chain of IV increments.
1490   SmallVector<IVChain, MaxChains> IVChainVec;
1491
1492   /// IVIncSet - IV users that belong to profitable IVChains.
1493   SmallPtrSet<Use*, MaxChains> IVIncSet;
1494
1495   void OptimizeShadowIV();
1496   bool FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse);
1497   ICmpInst *OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse);
1498   void OptimizeLoopTermCond();
1499
1500   void ChainInstruction(Instruction *UserInst, Instruction *IVOper,
1501                         SmallVectorImpl<ChainUsers> &ChainUsersVec);
1502   void FinalizeChain(IVChain &Chain);
1503   void CollectChains();
1504   void GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter,
1505                        SmallVectorImpl<WeakVH> &DeadInsts);
1506
1507   void CollectInterestingTypesAndFactors();
1508   void CollectFixupsAndInitialFormulae();
1509
1510   LSRFixup &getNewFixup() {
1511     Fixups.push_back(LSRFixup());
1512     return Fixups.back();
1513   }
1514
1515   // Support for sharing of LSRUses between LSRFixups.
1516   typedef DenseMap<std::pair<const SCEV *, LSRUse::KindType>,
1517                    size_t,
1518                    UseMapDenseMapInfo> UseMapTy;
1519   UseMapTy UseMap;
1520
1521   bool reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg,
1522                           LSRUse::KindType Kind, Type *AccessTy);
1523
1524   std::pair<size_t, int64_t> getUse(const SCEV *&Expr,
1525                                     LSRUse::KindType Kind,
1526                                     Type *AccessTy);
1527
1528   void DeleteUse(LSRUse &LU, size_t LUIdx);
1529
1530   LSRUse *FindUseWithSimilarFormula(const Formula &F, const LSRUse &OrigLU);
1531
1532   void InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1533   void InsertSupplementalFormula(const SCEV *S, LSRUse &LU, size_t LUIdx);
1534   void CountRegisters(const Formula &F, size_t LUIdx);
1535   bool InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F);
1536
1537   void CollectLoopInvariantFixupsAndFormulae();
1538
1539   void GenerateReassociations(LSRUse &LU, unsigned LUIdx, Formula Base,
1540                               unsigned Depth = 0);
1541   void GenerateCombinations(LSRUse &LU, unsigned LUIdx, Formula Base);
1542   void GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
1543   void GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx, Formula Base);
1544   void GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx, Formula Base);
1545   void GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base);
1546   void GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base);
1547   void GenerateCrossUseConstantOffsets();
1548   void GenerateAllReuseFormulae();
1549
1550   void FilterOutUndesirableDedicatedRegisters();
1551
1552   size_t EstimateSearchSpaceComplexity() const;
1553   void NarrowSearchSpaceByDetectingSupersets();
1554   void NarrowSearchSpaceByCollapsingUnrolledCode();
1555   void NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
1556   void NarrowSearchSpaceByPickingWinnerRegs();
1557   void NarrowSearchSpaceUsingHeuristics();
1558
1559   void SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
1560                     Cost &SolutionCost,
1561                     SmallVectorImpl<const Formula *> &Workspace,
1562                     const Cost &CurCost,
1563                     const SmallPtrSet<const SCEV *, 16> &CurRegs,
1564                     DenseSet<const SCEV *> &VisitedRegs) const;
1565   void Solve(SmallVectorImpl<const Formula *> &Solution) const;
1566
1567   BasicBlock::iterator
1568     HoistInsertPosition(BasicBlock::iterator IP,
1569                         const SmallVectorImpl<Instruction *> &Inputs) const;
1570   BasicBlock::iterator
1571     AdjustInsertPositionForExpand(BasicBlock::iterator IP,
1572                                   const LSRFixup &LF,
1573                                   const LSRUse &LU,
1574                                   SCEVExpander &Rewriter) const;
1575
1576   Value *Expand(const LSRFixup &LF,
1577                 const Formula &F,
1578                 BasicBlock::iterator IP,
1579                 SCEVExpander &Rewriter,
1580                 SmallVectorImpl<WeakVH> &DeadInsts) const;
1581   void RewriteForPHI(PHINode *PN, const LSRFixup &LF,
1582                      const Formula &F,
1583                      SCEVExpander &Rewriter,
1584                      SmallVectorImpl<WeakVH> &DeadInsts,
1585                      Pass *P) const;
1586   void Rewrite(const LSRFixup &LF,
1587                const Formula &F,
1588                SCEVExpander &Rewriter,
1589                SmallVectorImpl<WeakVH> &DeadInsts,
1590                Pass *P) const;
1591   void ImplementSolution(const SmallVectorImpl<const Formula *> &Solution,
1592                          Pass *P);
1593
1594 public:
1595   LSRInstance(const TargetLowering *tli, Loop *l, Pass *P);
1596
1597   bool getChanged() const { return Changed; }
1598
1599   void print_factors_and_types(raw_ostream &OS) const;
1600   void print_fixups(raw_ostream &OS) const;
1601   void print_uses(raw_ostream &OS) const;
1602   void print(raw_ostream &OS) const;
1603   void dump() const;
1604 };
1605
1606 }
1607
1608 /// OptimizeShadowIV - If IV is used in a int-to-float cast
1609 /// inside the loop then try to eliminate the cast operation.
1610 void LSRInstance::OptimizeShadowIV() {
1611   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
1612   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount))
1613     return;
1614
1615   for (IVUsers::const_iterator UI = IU.begin(), E = IU.end();
1616        UI != E; /* empty */) {
1617     IVUsers::const_iterator CandidateUI = UI;
1618     ++UI;
1619     Instruction *ShadowUse = CandidateUI->getUser();
1620     Type *DestTy = NULL;
1621     bool IsSigned = false;
1622
1623     /* If shadow use is a int->float cast then insert a second IV
1624        to eliminate this cast.
1625
1626          for (unsigned i = 0; i < n; ++i)
1627            foo((double)i);
1628
1629        is transformed into
1630
1631          double d = 0.0;
1632          for (unsigned i = 0; i < n; ++i, ++d)
1633            foo(d);
1634     */
1635     if (UIToFPInst *UCast = dyn_cast<UIToFPInst>(CandidateUI->getUser())) {
1636       IsSigned = false;
1637       DestTy = UCast->getDestTy();
1638     }
1639     else if (SIToFPInst *SCast = dyn_cast<SIToFPInst>(CandidateUI->getUser())) {
1640       IsSigned = true;
1641       DestTy = SCast->getDestTy();
1642     }
1643     if (!DestTy) continue;
1644
1645     if (TLI) {
1646       // If target does not support DestTy natively then do not apply
1647       // this transformation.
1648       EVT DVT = TLI->getValueType(DestTy);
1649       if (!TLI->isTypeLegal(DVT)) continue;
1650     }
1651
1652     PHINode *PH = dyn_cast<PHINode>(ShadowUse->getOperand(0));
1653     if (!PH) continue;
1654     if (PH->getNumIncomingValues() != 2) continue;
1655
1656     Type *SrcTy = PH->getType();
1657     int Mantissa = DestTy->getFPMantissaWidth();
1658     if (Mantissa == -1) continue;
1659     if ((int)SE.getTypeSizeInBits(SrcTy) > Mantissa)
1660       continue;
1661
1662     unsigned Entry, Latch;
1663     if (PH->getIncomingBlock(0) == L->getLoopPreheader()) {
1664       Entry = 0;
1665       Latch = 1;
1666     } else {
1667       Entry = 1;
1668       Latch = 0;
1669     }
1670
1671     ConstantInt *Init = dyn_cast<ConstantInt>(PH->getIncomingValue(Entry));
1672     if (!Init) continue;
1673     Constant *NewInit = ConstantFP::get(DestTy, IsSigned ?
1674                                         (double)Init->getSExtValue() :
1675                                         (double)Init->getZExtValue());
1676
1677     BinaryOperator *Incr =
1678       dyn_cast<BinaryOperator>(PH->getIncomingValue(Latch));
1679     if (!Incr) continue;
1680     if (Incr->getOpcode() != Instruction::Add
1681         && Incr->getOpcode() != Instruction::Sub)
1682       continue;
1683
1684     /* Initialize new IV, double d = 0.0 in above example. */
1685     ConstantInt *C = NULL;
1686     if (Incr->getOperand(0) == PH)
1687       C = dyn_cast<ConstantInt>(Incr->getOperand(1));
1688     else if (Incr->getOperand(1) == PH)
1689       C = dyn_cast<ConstantInt>(Incr->getOperand(0));
1690     else
1691       continue;
1692
1693     if (!C) continue;
1694
1695     // Ignore negative constants, as the code below doesn't handle them
1696     // correctly. TODO: Remove this restriction.
1697     if (!C->getValue().isStrictlyPositive()) continue;
1698
1699     /* Add new PHINode. */
1700     PHINode *NewPH = PHINode::Create(DestTy, 2, "IV.S.", PH);
1701
1702     /* create new increment. '++d' in above example. */
1703     Constant *CFP = ConstantFP::get(DestTy, C->getZExtValue());
1704     BinaryOperator *NewIncr =
1705       BinaryOperator::Create(Incr->getOpcode() == Instruction::Add ?
1706                                Instruction::FAdd : Instruction::FSub,
1707                              NewPH, CFP, "IV.S.next.", Incr);
1708
1709     NewPH->addIncoming(NewInit, PH->getIncomingBlock(Entry));
1710     NewPH->addIncoming(NewIncr, PH->getIncomingBlock(Latch));
1711
1712     /* Remove cast operation */
1713     ShadowUse->replaceAllUsesWith(NewPH);
1714     ShadowUse->eraseFromParent();
1715     Changed = true;
1716     break;
1717   }
1718 }
1719
1720 /// FindIVUserForCond - If Cond has an operand that is an expression of an IV,
1721 /// set the IV user and stride information and return true, otherwise return
1722 /// false.
1723 bool LSRInstance::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse) {
1724   for (IVUsers::iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI)
1725     if (UI->getUser() == Cond) {
1726       // NOTE: we could handle setcc instructions with multiple uses here, but
1727       // InstCombine does it as well for simple uses, it's not clear that it
1728       // occurs enough in real life to handle.
1729       CondUse = UI;
1730       return true;
1731     }
1732   return false;
1733 }
1734
1735 /// OptimizeMax - Rewrite the loop's terminating condition if it uses
1736 /// a max computation.
1737 ///
1738 /// This is a narrow solution to a specific, but acute, problem. For loops
1739 /// like this:
1740 ///
1741 ///   i = 0;
1742 ///   do {
1743 ///     p[i] = 0.0;
1744 ///   } while (++i < n);
1745 ///
1746 /// the trip count isn't just 'n', because 'n' might not be positive. And
1747 /// unfortunately this can come up even for loops where the user didn't use
1748 /// a C do-while loop. For example, seemingly well-behaved top-test loops
1749 /// will commonly be lowered like this:
1750 //
1751 ///   if (n > 0) {
1752 ///     i = 0;
1753 ///     do {
1754 ///       p[i] = 0.0;
1755 ///     } while (++i < n);
1756 ///   }
1757 ///
1758 /// and then it's possible for subsequent optimization to obscure the if
1759 /// test in such a way that indvars can't find it.
1760 ///
1761 /// When indvars can't find the if test in loops like this, it creates a
1762 /// max expression, which allows it to give the loop a canonical
1763 /// induction variable:
1764 ///
1765 ///   i = 0;
1766 ///   max = n < 1 ? 1 : n;
1767 ///   do {
1768 ///     p[i] = 0.0;
1769 ///   } while (++i != max);
1770 ///
1771 /// Canonical induction variables are necessary because the loop passes
1772 /// are designed around them. The most obvious example of this is the
1773 /// LoopInfo analysis, which doesn't remember trip count values. It
1774 /// expects to be able to rediscover the trip count each time it is
1775 /// needed, and it does this using a simple analysis that only succeeds if
1776 /// the loop has a canonical induction variable.
1777 ///
1778 /// However, when it comes time to generate code, the maximum operation
1779 /// can be quite costly, especially if it's inside of an outer loop.
1780 ///
1781 /// This function solves this problem by detecting this type of loop and
1782 /// rewriting their conditions from ICMP_NE back to ICMP_SLT, and deleting
1783 /// the instructions for the maximum computation.
1784 ///
1785 ICmpInst *LSRInstance::OptimizeMax(ICmpInst *Cond, IVStrideUse* &CondUse) {
1786   // Check that the loop matches the pattern we're looking for.
1787   if (Cond->getPredicate() != CmpInst::ICMP_EQ &&
1788       Cond->getPredicate() != CmpInst::ICMP_NE)
1789     return Cond;
1790
1791   SelectInst *Sel = dyn_cast<SelectInst>(Cond->getOperand(1));
1792   if (!Sel || !Sel->hasOneUse()) return Cond;
1793
1794   const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(L);
1795   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount))
1796     return Cond;
1797   const SCEV *One = SE.getConstant(BackedgeTakenCount->getType(), 1);
1798
1799   // Add one to the backedge-taken count to get the trip count.
1800   const SCEV *IterationCount = SE.getAddExpr(One, BackedgeTakenCount);
1801   if (IterationCount != SE.getSCEV(Sel)) return Cond;
1802
1803   // Check for a max calculation that matches the pattern. There's no check
1804   // for ICMP_ULE here because the comparison would be with zero, which
1805   // isn't interesting.
1806   CmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
1807   const SCEVNAryExpr *Max = 0;
1808   if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(BackedgeTakenCount)) {
1809     Pred = ICmpInst::ICMP_SLE;
1810     Max = S;
1811   } else if (const SCEVSMaxExpr *S = dyn_cast<SCEVSMaxExpr>(IterationCount)) {
1812     Pred = ICmpInst::ICMP_SLT;
1813     Max = S;
1814   } else if (const SCEVUMaxExpr *U = dyn_cast<SCEVUMaxExpr>(IterationCount)) {
1815     Pred = ICmpInst::ICMP_ULT;
1816     Max = U;
1817   } else {
1818     // No match; bail.
1819     return Cond;
1820   }
1821
1822   // To handle a max with more than two operands, this optimization would
1823   // require additional checking and setup.
1824   if (Max->getNumOperands() != 2)
1825     return Cond;
1826
1827   const SCEV *MaxLHS = Max->getOperand(0);
1828   const SCEV *MaxRHS = Max->getOperand(1);
1829
1830   // ScalarEvolution canonicalizes constants to the left. For < and >, look
1831   // for a comparison with 1. For <= and >=, a comparison with zero.
1832   if (!MaxLHS ||
1833       (ICmpInst::isTrueWhenEqual(Pred) ? !MaxLHS->isZero() : (MaxLHS != One)))
1834     return Cond;
1835
1836   // Check the relevant induction variable for conformance to
1837   // the pattern.
1838   const SCEV *IV = SE.getSCEV(Cond->getOperand(0));
1839   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(IV);
1840   if (!AR || !AR->isAffine() ||
1841       AR->getStart() != One ||
1842       AR->getStepRecurrence(SE) != One)
1843     return Cond;
1844
1845   assert(AR->getLoop() == L &&
1846          "Loop condition operand is an addrec in a different loop!");
1847
1848   // Check the right operand of the select, and remember it, as it will
1849   // be used in the new comparison instruction.
1850   Value *NewRHS = 0;
1851   if (ICmpInst::isTrueWhenEqual(Pred)) {
1852     // Look for n+1, and grab n.
1853     if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(1)))
1854       if (isa<ConstantInt>(BO->getOperand(1)) &&
1855           cast<ConstantInt>(BO->getOperand(1))->isOne() &&
1856           SE.getSCEV(BO->getOperand(0)) == MaxRHS)
1857         NewRHS = BO->getOperand(0);
1858     if (AddOperator *BO = dyn_cast<AddOperator>(Sel->getOperand(2)))
1859       if (isa<ConstantInt>(BO->getOperand(1)) &&
1860           cast<ConstantInt>(BO->getOperand(1))->isOne() &&
1861           SE.getSCEV(BO->getOperand(0)) == MaxRHS)
1862         NewRHS = BO->getOperand(0);
1863     if (!NewRHS)
1864       return Cond;
1865   } else if (SE.getSCEV(Sel->getOperand(1)) == MaxRHS)
1866     NewRHS = Sel->getOperand(1);
1867   else if (SE.getSCEV(Sel->getOperand(2)) == MaxRHS)
1868     NewRHS = Sel->getOperand(2);
1869   else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(MaxRHS))
1870     NewRHS = SU->getValue();
1871   else
1872     // Max doesn't match expected pattern.
1873     return Cond;
1874
1875   // Determine the new comparison opcode. It may be signed or unsigned,
1876   // and the original comparison may be either equality or inequality.
1877   if (Cond->getPredicate() == CmpInst::ICMP_EQ)
1878     Pred = CmpInst::getInversePredicate(Pred);
1879
1880   // Ok, everything looks ok to change the condition into an SLT or SGE and
1881   // delete the max calculation.
1882   ICmpInst *NewCond =
1883     new ICmpInst(Cond, Pred, Cond->getOperand(0), NewRHS, "scmp");
1884
1885   // Delete the max calculation instructions.
1886   Cond->replaceAllUsesWith(NewCond);
1887   CondUse->setUser(NewCond);
1888   Instruction *Cmp = cast<Instruction>(Sel->getOperand(0));
1889   Cond->eraseFromParent();
1890   Sel->eraseFromParent();
1891   if (Cmp->use_empty())
1892     Cmp->eraseFromParent();
1893   return NewCond;
1894 }
1895
1896 /// OptimizeLoopTermCond - Change loop terminating condition to use the
1897 /// postinc iv when possible.
1898 void
1899 LSRInstance::OptimizeLoopTermCond() {
1900   SmallPtrSet<Instruction *, 4> PostIncs;
1901
1902   BasicBlock *LatchBlock = L->getLoopLatch();
1903   SmallVector<BasicBlock*, 8> ExitingBlocks;
1904   L->getExitingBlocks(ExitingBlocks);
1905
1906   for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
1907     BasicBlock *ExitingBlock = ExitingBlocks[i];
1908
1909     // Get the terminating condition for the loop if possible.  If we
1910     // can, we want to change it to use a post-incremented version of its
1911     // induction variable, to allow coalescing the live ranges for the IV into
1912     // one register value.
1913
1914     BranchInst *TermBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
1915     if (!TermBr)
1916       continue;
1917     // FIXME: Overly conservative, termination condition could be an 'or' etc..
1918     if (TermBr->isUnconditional() || !isa<ICmpInst>(TermBr->getCondition()))
1919       continue;
1920
1921     // Search IVUsesByStride to find Cond's IVUse if there is one.
1922     IVStrideUse *CondUse = 0;
1923     ICmpInst *Cond = cast<ICmpInst>(TermBr->getCondition());
1924     if (!FindIVUserForCond(Cond, CondUse))
1925       continue;
1926
1927     // If the trip count is computed in terms of a max (due to ScalarEvolution
1928     // being unable to find a sufficient guard, for example), change the loop
1929     // comparison to use SLT or ULT instead of NE.
1930     // One consequence of doing this now is that it disrupts the count-down
1931     // optimization. That's not always a bad thing though, because in such
1932     // cases it may still be worthwhile to avoid a max.
1933     Cond = OptimizeMax(Cond, CondUse);
1934
1935     // If this exiting block dominates the latch block, it may also use
1936     // the post-inc value if it won't be shared with other uses.
1937     // Check for dominance.
1938     if (!DT.dominates(ExitingBlock, LatchBlock))
1939       continue;
1940
1941     // Conservatively avoid trying to use the post-inc value in non-latch
1942     // exits if there may be pre-inc users in intervening blocks.
1943     if (LatchBlock != ExitingBlock)
1944       for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI)
1945         // Test if the use is reachable from the exiting block. This dominator
1946         // query is a conservative approximation of reachability.
1947         if (&*UI != CondUse &&
1948             !DT.properlyDominates(UI->getUser()->getParent(), ExitingBlock)) {
1949           // Conservatively assume there may be reuse if the quotient of their
1950           // strides could be a legal scale.
1951           const SCEV *A = IU.getStride(*CondUse, L);
1952           const SCEV *B = IU.getStride(*UI, L);
1953           if (!A || !B) continue;
1954           if (SE.getTypeSizeInBits(A->getType()) !=
1955               SE.getTypeSizeInBits(B->getType())) {
1956             if (SE.getTypeSizeInBits(A->getType()) >
1957                 SE.getTypeSizeInBits(B->getType()))
1958               B = SE.getSignExtendExpr(B, A->getType());
1959             else
1960               A = SE.getSignExtendExpr(A, B->getType());
1961           }
1962           if (const SCEVConstant *D =
1963                 dyn_cast_or_null<SCEVConstant>(getExactSDiv(B, A, SE))) {
1964             const ConstantInt *C = D->getValue();
1965             // Stride of one or negative one can have reuse with non-addresses.
1966             if (C->isOne() || C->isAllOnesValue())
1967               goto decline_post_inc;
1968             // Avoid weird situations.
1969             if (C->getValue().getMinSignedBits() >= 64 ||
1970                 C->getValue().isMinSignedValue())
1971               goto decline_post_inc;
1972             // Without TLI, assume that any stride might be valid, and so any
1973             // use might be shared.
1974             if (!TLI)
1975               goto decline_post_inc;
1976             // Check for possible scaled-address reuse.
1977             Type *AccessTy = getAccessType(UI->getUser());
1978             TargetLowering::AddrMode AM;
1979             AM.Scale = C->getSExtValue();
1980             if (TLI->isLegalAddressingMode(AM, AccessTy))
1981               goto decline_post_inc;
1982             AM.Scale = -AM.Scale;
1983             if (TLI->isLegalAddressingMode(AM, AccessTy))
1984               goto decline_post_inc;
1985           }
1986         }
1987
1988     DEBUG(dbgs() << "  Change loop exiting icmp to use postinc iv: "
1989                  << *Cond << '\n');
1990
1991     // It's possible for the setcc instruction to be anywhere in the loop, and
1992     // possible for it to have multiple users.  If it is not immediately before
1993     // the exiting block branch, move it.
1994     if (&*++BasicBlock::iterator(Cond) != TermBr) {
1995       if (Cond->hasOneUse()) {
1996         Cond->moveBefore(TermBr);
1997       } else {
1998         // Clone the terminating condition and insert into the loopend.
1999         ICmpInst *OldCond = Cond;
2000         Cond = cast<ICmpInst>(Cond->clone());
2001         Cond->setName(L->getHeader()->getName() + ".termcond");
2002         ExitingBlock->getInstList().insert(TermBr, Cond);
2003
2004         // Clone the IVUse, as the old use still exists!
2005         CondUse = &IU.AddUser(Cond, CondUse->getOperandValToReplace());
2006         TermBr->replaceUsesOfWith(OldCond, Cond);
2007       }
2008     }
2009
2010     // If we get to here, we know that we can transform the setcc instruction to
2011     // use the post-incremented version of the IV, allowing us to coalesce the
2012     // live ranges for the IV correctly.
2013     CondUse->transformToPostInc(L);
2014     Changed = true;
2015
2016     PostIncs.insert(Cond);
2017   decline_post_inc:;
2018   }
2019
2020   // Determine an insertion point for the loop induction variable increment. It
2021   // must dominate all the post-inc comparisons we just set up, and it must
2022   // dominate the loop latch edge.
2023   IVIncInsertPos = L->getLoopLatch()->getTerminator();
2024   for (SmallPtrSet<Instruction *, 4>::const_iterator I = PostIncs.begin(),
2025        E = PostIncs.end(); I != E; ++I) {
2026     BasicBlock *BB =
2027       DT.findNearestCommonDominator(IVIncInsertPos->getParent(),
2028                                     (*I)->getParent());
2029     if (BB == (*I)->getParent())
2030       IVIncInsertPos = *I;
2031     else if (BB != IVIncInsertPos->getParent())
2032       IVIncInsertPos = BB->getTerminator();
2033   }
2034 }
2035
2036 /// reconcileNewOffset - Determine if the given use can accommodate a fixup
2037 /// at the given offset and other details. If so, update the use and
2038 /// return true.
2039 bool
2040 LSRInstance::reconcileNewOffset(LSRUse &LU, int64_t NewOffset, bool HasBaseReg,
2041                                 LSRUse::KindType Kind, Type *AccessTy) {
2042   int64_t NewMinOffset = LU.MinOffset;
2043   int64_t NewMaxOffset = LU.MaxOffset;
2044   Type *NewAccessTy = AccessTy;
2045
2046   // Check for a mismatched kind. It's tempting to collapse mismatched kinds to
2047   // something conservative, however this can pessimize in the case that one of
2048   // the uses will have all its uses outside the loop, for example.
2049   if (LU.Kind != Kind)
2050     return false;
2051   // Conservatively assume HasBaseReg is true for now.
2052   if (NewOffset < LU.MinOffset) {
2053     if (!isAlwaysFoldable(LU.MaxOffset - NewOffset, 0, HasBaseReg,
2054                           Kind, AccessTy, TLI))
2055       return false;
2056     NewMinOffset = NewOffset;
2057   } else if (NewOffset > LU.MaxOffset) {
2058     if (!isAlwaysFoldable(NewOffset - LU.MinOffset, 0, HasBaseReg,
2059                           Kind, AccessTy, TLI))
2060       return false;
2061     NewMaxOffset = NewOffset;
2062   }
2063   // Check for a mismatched access type, and fall back conservatively as needed.
2064   // TODO: Be less conservative when the type is similar and can use the same
2065   // addressing modes.
2066   if (Kind == LSRUse::Address && AccessTy != LU.AccessTy)
2067     NewAccessTy = Type::getVoidTy(AccessTy->getContext());
2068
2069   // Update the use.
2070   LU.MinOffset = NewMinOffset;
2071   LU.MaxOffset = NewMaxOffset;
2072   LU.AccessTy = NewAccessTy;
2073   if (NewOffset != LU.Offsets.back())
2074     LU.Offsets.push_back(NewOffset);
2075   return true;
2076 }
2077
2078 /// getUse - Return an LSRUse index and an offset value for a fixup which
2079 /// needs the given expression, with the given kind and optional access type.
2080 /// Either reuse an existing use or create a new one, as needed.
2081 std::pair<size_t, int64_t>
2082 LSRInstance::getUse(const SCEV *&Expr,
2083                     LSRUse::KindType Kind, Type *AccessTy) {
2084   const SCEV *Copy = Expr;
2085   int64_t Offset = ExtractImmediate(Expr, SE);
2086
2087   // Basic uses can't accept any offset, for example.
2088   if (!isAlwaysFoldable(Offset, 0, /*HasBaseReg=*/true, Kind, AccessTy, TLI)) {
2089     Expr = Copy;
2090     Offset = 0;
2091   }
2092
2093   std::pair<UseMapTy::iterator, bool> P =
2094     UseMap.insert(std::make_pair(std::make_pair(Expr, Kind), 0));
2095   if (!P.second) {
2096     // A use already existed with this base.
2097     size_t LUIdx = P.first->second;
2098     LSRUse &LU = Uses[LUIdx];
2099     if (reconcileNewOffset(LU, Offset, /*HasBaseReg=*/true, Kind, AccessTy))
2100       // Reuse this use.
2101       return std::make_pair(LUIdx, Offset);
2102   }
2103
2104   // Create a new use.
2105   size_t LUIdx = Uses.size();
2106   P.first->second = LUIdx;
2107   Uses.push_back(LSRUse(Kind, AccessTy));
2108   LSRUse &LU = Uses[LUIdx];
2109
2110   // We don't need to track redundant offsets, but we don't need to go out
2111   // of our way here to avoid them.
2112   if (LU.Offsets.empty() || Offset != LU.Offsets.back())
2113     LU.Offsets.push_back(Offset);
2114
2115   LU.MinOffset = Offset;
2116   LU.MaxOffset = Offset;
2117   return std::make_pair(LUIdx, Offset);
2118 }
2119
2120 /// DeleteUse - Delete the given use from the Uses list.
2121 void LSRInstance::DeleteUse(LSRUse &LU, size_t LUIdx) {
2122   if (&LU != &Uses.back())
2123     std::swap(LU, Uses.back());
2124   Uses.pop_back();
2125
2126   // Update RegUses.
2127   RegUses.SwapAndDropUse(LUIdx, Uses.size());
2128 }
2129
2130 /// FindUseWithFormula - Look for a use distinct from OrigLU which is has
2131 /// a formula that has the same registers as the given formula.
2132 LSRUse *
2133 LSRInstance::FindUseWithSimilarFormula(const Formula &OrigF,
2134                                        const LSRUse &OrigLU) {
2135   // Search all uses for the formula. This could be more clever.
2136   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
2137     LSRUse &LU = Uses[LUIdx];
2138     // Check whether this use is close enough to OrigLU, to see whether it's
2139     // worthwhile looking through its formulae.
2140     // Ignore ICmpZero uses because they may contain formulae generated by
2141     // GenerateICmpZeroScales, in which case adding fixup offsets may
2142     // be invalid.
2143     if (&LU != &OrigLU &&
2144         LU.Kind != LSRUse::ICmpZero &&
2145         LU.Kind == OrigLU.Kind && OrigLU.AccessTy == LU.AccessTy &&
2146         LU.WidestFixupType == OrigLU.WidestFixupType &&
2147         LU.HasFormulaWithSameRegs(OrigF)) {
2148       // Scan through this use's formulae.
2149       for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(),
2150            E = LU.Formulae.end(); I != E; ++I) {
2151         const Formula &F = *I;
2152         // Check to see if this formula has the same registers and symbols
2153         // as OrigF.
2154         if (F.BaseRegs == OrigF.BaseRegs &&
2155             F.ScaledReg == OrigF.ScaledReg &&
2156             F.AM.BaseGV == OrigF.AM.BaseGV &&
2157             F.AM.Scale == OrigF.AM.Scale &&
2158             F.UnfoldedOffset == OrigF.UnfoldedOffset) {
2159           if (F.AM.BaseOffs == 0)
2160             return &LU;
2161           // This is the formula where all the registers and symbols matched;
2162           // there aren't going to be any others. Since we declined it, we
2163           // can skip the rest of the formulae and procede to the next LSRUse.
2164           break;
2165         }
2166       }
2167     }
2168   }
2169
2170   // Nothing looked good.
2171   return 0;
2172 }
2173
2174 void LSRInstance::CollectInterestingTypesAndFactors() {
2175   SmallSetVector<const SCEV *, 4> Strides;
2176
2177   // Collect interesting types and strides.
2178   SmallVector<const SCEV *, 4> Worklist;
2179   for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) {
2180     const SCEV *Expr = IU.getExpr(*UI);
2181
2182     // Collect interesting types.
2183     Types.insert(SE.getEffectiveSCEVType(Expr->getType()));
2184
2185     // Add strides for mentioned loops.
2186     Worklist.push_back(Expr);
2187     do {
2188       const SCEV *S = Worklist.pop_back_val();
2189       if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2190         if (AR->getLoop() == L)
2191           Strides.insert(AR->getStepRecurrence(SE));
2192         Worklist.push_back(AR->getStart());
2193       } else if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
2194         Worklist.append(Add->op_begin(), Add->op_end());
2195       }
2196     } while (!Worklist.empty());
2197   }
2198
2199   // Compute interesting factors from the set of interesting strides.
2200   for (SmallSetVector<const SCEV *, 4>::const_iterator
2201        I = Strides.begin(), E = Strides.end(); I != E; ++I)
2202     for (SmallSetVector<const SCEV *, 4>::const_iterator NewStrideIter =
2203          llvm::next(I); NewStrideIter != E; ++NewStrideIter) {
2204       const SCEV *OldStride = *I;
2205       const SCEV *NewStride = *NewStrideIter;
2206
2207       if (SE.getTypeSizeInBits(OldStride->getType()) !=
2208           SE.getTypeSizeInBits(NewStride->getType())) {
2209         if (SE.getTypeSizeInBits(OldStride->getType()) >
2210             SE.getTypeSizeInBits(NewStride->getType()))
2211           NewStride = SE.getSignExtendExpr(NewStride, OldStride->getType());
2212         else
2213           OldStride = SE.getSignExtendExpr(OldStride, NewStride->getType());
2214       }
2215       if (const SCEVConstant *Factor =
2216             dyn_cast_or_null<SCEVConstant>(getExactSDiv(NewStride, OldStride,
2217                                                         SE, true))) {
2218         if (Factor->getValue()->getValue().getMinSignedBits() <= 64)
2219           Factors.insert(Factor->getValue()->getValue().getSExtValue());
2220       } else if (const SCEVConstant *Factor =
2221                    dyn_cast_or_null<SCEVConstant>(getExactSDiv(OldStride,
2222                                                                NewStride,
2223                                                                SE, true))) {
2224         if (Factor->getValue()->getValue().getMinSignedBits() <= 64)
2225           Factors.insert(Factor->getValue()->getValue().getSExtValue());
2226       }
2227     }
2228
2229   // If all uses use the same type, don't bother looking for truncation-based
2230   // reuse.
2231   if (Types.size() == 1)
2232     Types.clear();
2233
2234   DEBUG(print_factors_and_types(dbgs()));
2235 }
2236
2237 /// findIVOperand - Helper for CollectChains that finds an IV operand (computed
2238 /// by an AddRec in this loop) within [OI,OE) or returns OE. If IVUsers mapped
2239 /// Instructions to IVStrideUses, we could partially skip this.
2240 static User::op_iterator
2241 findIVOperand(User::op_iterator OI, User::op_iterator OE,
2242               Loop *L, ScalarEvolution &SE) {
2243   for(; OI != OE; ++OI) {
2244     if (Instruction *Oper = dyn_cast<Instruction>(*OI)) {
2245       if (!SE.isSCEVable(Oper->getType()))
2246         continue;
2247
2248       if (const SCEVAddRecExpr *AR =
2249           dyn_cast<SCEVAddRecExpr>(SE.getSCEV(Oper))) {
2250         if (AR->getLoop() == L)
2251           break;
2252       }
2253     }
2254   }
2255   return OI;
2256 }
2257
2258 /// getWideOperand - IVChain logic must consistenctly peek base TruncInst
2259 /// operands, so wrap it in a convenient helper.
2260 static Value *getWideOperand(Value *Oper) {
2261   if (TruncInst *Trunc = dyn_cast<TruncInst>(Oper))
2262     return Trunc->getOperand(0);
2263   return Oper;
2264 }
2265
2266 /// isCompatibleIVType - Return true if we allow an IV chain to include both
2267 /// types.
2268 static bool isCompatibleIVType(Value *LVal, Value *RVal) {
2269   Type *LType = LVal->getType();
2270   Type *RType = RVal->getType();
2271   return (LType == RType) || (LType->isPointerTy() && RType->isPointerTy());
2272 }
2273
2274 /// getExprBase - Return an approximation of this SCEV expression's "base", or
2275 /// NULL for any constant. Returning the expression itself is
2276 /// conservative. Returning a deeper subexpression is more precise and valid as
2277 /// long as it isn't less complex than another subexpression. For expressions
2278 /// involving multiple unscaled values, we need to return the pointer-type
2279 /// SCEVUnknown. This avoids forming chains across objects, such as:
2280 /// PrevOper==a[i], IVOper==b[i], IVInc==b-a.
2281 ///
2282 /// Since SCEVUnknown is the rightmost type, and pointers are the rightmost
2283 /// SCEVUnknown, we simply return the rightmost SCEV operand.
2284 static const SCEV *getExprBase(const SCEV *S) {
2285   switch (S->getSCEVType()) {
2286   default: // uncluding scUnknown.
2287     return S;
2288   case scConstant:
2289     return 0;
2290   case scTruncate:
2291     return getExprBase(cast<SCEVTruncateExpr>(S)->getOperand());
2292   case scZeroExtend:
2293     return getExprBase(cast<SCEVZeroExtendExpr>(S)->getOperand());
2294   case scSignExtend:
2295     return getExprBase(cast<SCEVSignExtendExpr>(S)->getOperand());
2296   case scAddExpr: {
2297     // Skip over scaled operands (scMulExpr) to follow add operands as long as
2298     // there's nothing more complex.
2299     // FIXME: not sure if we want to recognize negation.
2300     const SCEVAddExpr *Add = cast<SCEVAddExpr>(S);
2301     for (std::reverse_iterator<SCEVAddExpr::op_iterator> I(Add->op_end()),
2302            E(Add->op_begin()); I != E; ++I) {
2303       const SCEV *SubExpr = *I;
2304       if (SubExpr->getSCEVType() == scAddExpr)
2305         return getExprBase(SubExpr);
2306
2307       if (SubExpr->getSCEVType() != scMulExpr)
2308         return SubExpr;
2309     }
2310     return S; // all operands are scaled, be conservative.
2311   }
2312   case scAddRecExpr:
2313     return getExprBase(cast<SCEVAddRecExpr>(S)->getStart());
2314   }
2315 }
2316
2317 /// Return true if the chain increment is profitable to expand into a loop
2318 /// invariant value, which may require its own register. A profitable chain
2319 /// increment will be an offset relative to the same base. We allow such offsets
2320 /// to potentially be used as chain increment as long as it's not obviously
2321 /// expensive to expand using real instructions.
2322 static const SCEV *
2323 getProfitableChainIncrement(Value *NextIV, Value *PrevIV,
2324                             const IVChain &Chain, Loop *L,
2325                             ScalarEvolution &SE, const TargetLowering *TLI) {
2326   // Prune the solution space aggressively by checking that both IV operands
2327   // are expressions that operate on the same unscaled SCEVUnknown. This
2328   // "base" will be canceled by the subsequent getMinusSCEV call. Checking first
2329   // avoids creating extra SCEV expressions.
2330   const SCEV *OperExpr = SE.getSCEV(NextIV);
2331   const SCEV *PrevExpr = SE.getSCEV(PrevIV);
2332   if (getExprBase(OperExpr) != getExprBase(PrevExpr) && !StressIVChain)
2333     return 0;
2334
2335   const SCEV *IncExpr = SE.getMinusSCEV(OperExpr, PrevExpr);
2336   if (!SE.isLoopInvariant(IncExpr, L))
2337     return 0;
2338
2339   // We are not able to expand an increment unless it is loop invariant,
2340   // however, the following checks are purely for profitability.
2341   if (StressIVChain)
2342     return IncExpr;
2343
2344   // Do not replace a constant offset from IV head with a nonconstant IV
2345   // increment.
2346   if (!isa<SCEVConstant>(IncExpr)) {
2347     const SCEV *HeadExpr = SE.getSCEV(getWideOperand(Chain[0].IVOperand));
2348     if (isa<SCEVConstant>(SE.getMinusSCEV(OperExpr, HeadExpr)))
2349       return 0;
2350   }
2351
2352   SmallPtrSet<const SCEV*, 8> Processed;
2353   if (isHighCostExpansion(IncExpr, Processed, SE))
2354     return 0;
2355
2356   return IncExpr;
2357 }
2358
2359 /// Return true if the number of registers needed for the chain is estimated to
2360 /// be less than the number required for the individual IV users. First prohibit
2361 /// any IV users that keep the IV live across increments (the Users set should
2362 /// be empty). Next count the number and type of increments in the chain.
2363 ///
2364 /// Chaining IVs can lead to considerable code bloat if ISEL doesn't
2365 /// effectively use postinc addressing modes. Only consider it profitable it the
2366 /// increments can be computed in fewer registers when chained.
2367 ///
2368 /// TODO: Consider IVInc free if it's already used in another chains.
2369 static bool
2370 isProfitableChain(IVChain &Chain, SmallPtrSet<Instruction*, 4> &Users,
2371                   ScalarEvolution &SE, const TargetLowering *TLI) {
2372   if (StressIVChain)
2373     return true;
2374
2375   if (Chain.size() <= 2)
2376     return false;
2377
2378   if (!Users.empty()) {
2379     DEBUG(dbgs() << "Chain: " << *Chain[0].UserInst << " users:\n";
2380           for (SmallPtrSet<Instruction*, 4>::const_iterator I = Users.begin(),
2381                  E = Users.end(); I != E; ++I) {
2382             dbgs() << "  " << **I << "\n";
2383           });
2384     return false;
2385   }
2386   assert(!Chain.empty() && "empty IV chains are not allowed");
2387
2388   // The chain itself may require a register, so intialize cost to 1.
2389   int cost = 1;
2390
2391   // A complete chain likely eliminates the need for keeping the original IV in
2392   // a register. LSR does not currently know how to form a complete chain unless
2393   // the header phi already exists.
2394   if (isa<PHINode>(Chain.back().UserInst)
2395       && SE.getSCEV(Chain.back().UserInst) == Chain[0].IncExpr) {
2396     --cost;
2397   }
2398   const SCEV *LastIncExpr = 0;
2399   unsigned NumConstIncrements = 0;
2400   unsigned NumVarIncrements = 0;
2401   unsigned NumReusedIncrements = 0;
2402   for (IVChain::const_iterator I = llvm::next(Chain.begin()), E = Chain.end();
2403        I != E; ++I) {
2404
2405     if (I->IncExpr->isZero())
2406       continue;
2407
2408     // Incrementing by zero or some constant is neutral. We assume constants can
2409     // be folded into an addressing mode or an add's immediate operand.
2410     if (isa<SCEVConstant>(I->IncExpr)) {
2411       ++NumConstIncrements;
2412       continue;
2413     }
2414
2415     if (I->IncExpr == LastIncExpr)
2416       ++NumReusedIncrements;
2417     else
2418       ++NumVarIncrements;
2419
2420     LastIncExpr = I->IncExpr;
2421   }
2422   // An IV chain with a single increment is handled by LSR's postinc
2423   // uses. However, a chain with multiple increments requires keeping the IV's
2424   // value live longer than it needs to be if chained.
2425   if (NumConstIncrements > 1)
2426     --cost;
2427
2428   // Materializing increment expressions in the preheader that didn't exist in
2429   // the original code may cost a register. For example, sign-extended array
2430   // indices can produce ridiculous increments like this:
2431   // IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64)))
2432   cost += NumVarIncrements;
2433
2434   // Reusing variable increments likely saves a register to hold the multiple of
2435   // the stride.
2436   cost -= NumReusedIncrements;
2437
2438   DEBUG(dbgs() << "Chain: " << *Chain[0].UserInst << " Cost: " << cost << "\n");
2439
2440   return cost < 0;
2441 }
2442
2443 /// ChainInstruction - Add this IV user to an existing chain or make it the head
2444 /// of a new chain.
2445 void LSRInstance::ChainInstruction(Instruction *UserInst, Instruction *IVOper,
2446                                    SmallVectorImpl<ChainUsers> &ChainUsersVec) {
2447   // When IVs are used as types of varying widths, they are generally converted
2448   // to a wider type with some uses remaining narrow under a (free) trunc.
2449   Value *NextIV = getWideOperand(IVOper);
2450
2451   // Visit all existing chains. Check if its IVOper can be computed as a
2452   // profitable loop invariant increment from the last link in the Chain.
2453   unsigned ChainIdx = 0, NChains = IVChainVec.size();
2454   const SCEV *LastIncExpr = 0;
2455   for (; ChainIdx < NChains; ++ChainIdx) {
2456     Value *PrevIV = getWideOperand(IVChainVec[ChainIdx].back().IVOperand);
2457     if (!isCompatibleIVType(PrevIV, NextIV))
2458       continue;
2459
2460     // A phi node terminates a chain.
2461     if (isa<PHINode>(UserInst)
2462         && isa<PHINode>(IVChainVec[ChainIdx].back().UserInst))
2463       continue;
2464
2465     if (const SCEV *IncExpr =
2466         getProfitableChainIncrement(NextIV, PrevIV, IVChainVec[ChainIdx],
2467                                     L, SE, TLI)) {
2468       LastIncExpr = IncExpr;
2469       break;
2470     }
2471   }
2472   // If we haven't found a chain, create a new one, unless we hit the max. Don't
2473   // bother for phi nodes, because they must be last in the chain.
2474   if (ChainIdx == NChains) {
2475     if (isa<PHINode>(UserInst))
2476       return;
2477     if (NChains >= MaxChains && !StressIVChain) {
2478       DEBUG(dbgs() << "IV Chain Limit\n");
2479       return;
2480     }
2481     LastIncExpr = SE.getSCEV(NextIV);
2482     // IVUsers may have skipped over sign/zero extensions. We don't currently
2483     // attempt to form chains involving extensions unless they can be hoisted
2484     // into this loop's AddRec.
2485     if (!isa<SCEVAddRecExpr>(LastIncExpr))
2486       return;
2487     ++NChains;
2488     IVChainVec.resize(NChains);
2489     ChainUsersVec.resize(NChains);
2490     DEBUG(dbgs() << "IV Head: (" << *UserInst << ") IV=" << *LastIncExpr
2491           << "\n");
2492   }
2493   else
2494     DEBUG(dbgs() << "IV  Inc: (" << *UserInst << ") IV+" << *LastIncExpr
2495           << "\n");
2496
2497   // Add this IV user to the end of the chain.
2498   IVChainVec[ChainIdx].push_back(IVInc(UserInst, IVOper, LastIncExpr));
2499
2500   SmallPtrSet<Instruction*,4> &NearUsers = ChainUsersVec[ChainIdx].NearUsers;
2501   // This chain's NearUsers become FarUsers.
2502   if (!LastIncExpr->isZero()) {
2503     ChainUsersVec[ChainIdx].FarUsers.insert(NearUsers.begin(),
2504                                             NearUsers.end());
2505     NearUsers.clear();
2506   }
2507
2508   // All other uses of IVOperand become near uses of the chain.
2509   // We currently ignore intermediate values within SCEV expressions, assuming
2510   // they will eventually be used be the current chain, or can be computed
2511   // from one of the chain increments. To be more precise we could
2512   // transitively follow its user and only add leaf IV users to the set.
2513   for (Value::use_iterator UseIter = IVOper->use_begin(),
2514          UseEnd = IVOper->use_end(); UseIter != UseEnd; ++UseIter) {
2515     Instruction *OtherUse = dyn_cast<Instruction>(*UseIter);
2516     if (!OtherUse || OtherUse == UserInst)
2517       continue;
2518     if (SE.isSCEVable(OtherUse->getType())
2519         && !isa<SCEVUnknown>(SE.getSCEV(OtherUse))
2520         && IU.isIVUserOrOperand(OtherUse)) {
2521       continue;
2522     }
2523     NearUsers.insert(OtherUse);
2524   }
2525
2526   // Since this user is part of the chain, it's no longer considered a use
2527   // of the chain.
2528   ChainUsersVec[ChainIdx].FarUsers.erase(UserInst);
2529 }
2530
2531 /// CollectChains - Populate the vector of Chains.
2532 ///
2533 /// This decreases ILP at the architecture level. Targets with ample registers,
2534 /// multiple memory ports, and no register renaming probably don't want
2535 /// this. However, such targets should probably disable LSR altogether.
2536 ///
2537 /// The job of LSR is to make a reasonable choice of induction variables across
2538 /// the loop. Subsequent passes can easily "unchain" computation exposing more
2539 /// ILP *within the loop* if the target wants it.
2540 ///
2541 /// Finding the best IV chain is potentially a scheduling problem. Since LSR
2542 /// will not reorder memory operations, it will recognize this as a chain, but
2543 /// will generate redundant IV increments. Ideally this would be corrected later
2544 /// by a smart scheduler:
2545 ///        = A[i]
2546 ///        = A[i+x]
2547 /// A[i]   =
2548 /// A[i+x] =
2549 ///
2550 /// TODO: Walk the entire domtree within this loop, not just the path to the
2551 /// loop latch. This will discover chains on side paths, but requires
2552 /// maintaining multiple copies of the Chains state.
2553 void LSRInstance::CollectChains() {
2554   SmallVector<ChainUsers, 8> ChainUsersVec;
2555
2556   SmallVector<BasicBlock *,8> LatchPath;
2557   BasicBlock *LoopHeader = L->getHeader();
2558   for (DomTreeNode *Rung = DT.getNode(L->getLoopLatch());
2559        Rung->getBlock() != LoopHeader; Rung = Rung->getIDom()) {
2560     LatchPath.push_back(Rung->getBlock());
2561   }
2562   LatchPath.push_back(LoopHeader);
2563
2564   // Walk the instruction stream from the loop header to the loop latch.
2565   for (SmallVectorImpl<BasicBlock *>::reverse_iterator
2566          BBIter = LatchPath.rbegin(), BBEnd = LatchPath.rend();
2567        BBIter != BBEnd; ++BBIter) {
2568     for (BasicBlock::iterator I = (*BBIter)->begin(), E = (*BBIter)->end();
2569          I != E; ++I) {
2570       // Skip instructions that weren't seen by IVUsers analysis.
2571       if (isa<PHINode>(I) || !IU.isIVUserOrOperand(I))
2572         continue;
2573
2574       // Ignore users that are part of a SCEV expression. This way we only
2575       // consider leaf IV Users. This effectively rediscovers a portion of
2576       // IVUsers analysis but in program order this time.
2577       if (SE.isSCEVable(I->getType()) && !isa<SCEVUnknown>(SE.getSCEV(I)))
2578         continue;
2579
2580       // Remove this instruction from any NearUsers set it may be in.
2581       for (unsigned ChainIdx = 0, NChains = IVChainVec.size();
2582            ChainIdx < NChains; ++ChainIdx) {
2583         ChainUsersVec[ChainIdx].NearUsers.erase(I);
2584       }
2585       // Search for operands that can be chained.
2586       SmallPtrSet<Instruction*, 4> UniqueOperands;
2587       User::op_iterator IVOpEnd = I->op_end();
2588       User::op_iterator IVOpIter = findIVOperand(I->op_begin(), IVOpEnd, L, SE);
2589       while (IVOpIter != IVOpEnd) {
2590         Instruction *IVOpInst = cast<Instruction>(*IVOpIter);
2591         if (UniqueOperands.insert(IVOpInst))
2592           ChainInstruction(I, IVOpInst, ChainUsersVec);
2593         IVOpIter = findIVOperand(llvm::next(IVOpIter), IVOpEnd, L, SE);
2594       }
2595     } // Continue walking down the instructions.
2596   } // Continue walking down the domtree.
2597   // Visit phi backedges to determine if the chain can generate the IV postinc.
2598   for (BasicBlock::iterator I = L->getHeader()->begin();
2599        PHINode *PN = dyn_cast<PHINode>(I); ++I) {
2600     if (!SE.isSCEVable(PN->getType()))
2601       continue;
2602
2603     Instruction *IncV =
2604       dyn_cast<Instruction>(PN->getIncomingValueForBlock(L->getLoopLatch()));
2605     if (IncV)
2606       ChainInstruction(PN, IncV, ChainUsersVec);
2607   }
2608   // Remove any unprofitable chains.
2609   unsigned ChainIdx = 0;
2610   for (unsigned UsersIdx = 0, NChains = IVChainVec.size();
2611        UsersIdx < NChains; ++UsersIdx) {
2612     if (!isProfitableChain(IVChainVec[UsersIdx],
2613                            ChainUsersVec[UsersIdx].FarUsers, SE, TLI))
2614       continue;
2615     // Preserve the chain at UsesIdx.
2616     if (ChainIdx != UsersIdx)
2617       IVChainVec[ChainIdx] = IVChainVec[UsersIdx];
2618     FinalizeChain(IVChainVec[ChainIdx]);
2619     ++ChainIdx;
2620   }
2621   IVChainVec.resize(ChainIdx);
2622 }
2623
2624 void LSRInstance::FinalizeChain(IVChain &Chain) {
2625   assert(!Chain.empty() && "empty IV chains are not allowed");
2626   DEBUG(dbgs() << "Final Chain: " << *Chain[0].UserInst << "\n");
2627
2628   for (IVChain::const_iterator I = llvm::next(Chain.begin()), E = Chain.end();
2629        I != E; ++I) {
2630     DEBUG(dbgs() << "        Inc: " << *I->UserInst << "\n");
2631     User::op_iterator UseI =
2632       std::find(I->UserInst->op_begin(), I->UserInst->op_end(), I->IVOperand);
2633     assert(UseI != I->UserInst->op_end() && "cannot find IV operand");
2634     IVIncSet.insert(UseI);
2635   }
2636 }
2637
2638 /// Return true if the IVInc can be folded into an addressing mode.
2639 static bool canFoldIVIncExpr(const SCEV *IncExpr, Instruction *UserInst,
2640                              Value *Operand, const TargetLowering *TLI) {
2641   const SCEVConstant *IncConst = dyn_cast<SCEVConstant>(IncExpr);
2642   if (!IncConst || !isAddressUse(UserInst, Operand))
2643     return false;
2644
2645   if (IncConst->getValue()->getValue().getMinSignedBits() > 64)
2646     return false;
2647
2648   int64_t IncOffset = IncConst->getValue()->getSExtValue();
2649   if (!isAlwaysFoldable(IncOffset, /*BaseGV=*/0, /*HaseBaseReg=*/false,
2650                        LSRUse::Address, getAccessType(UserInst), TLI))
2651     return false;
2652
2653   return true;
2654 }
2655
2656 /// GenerateIVChains - Generate an add or subtract for each IVInc in a chain to
2657 /// materialize the IV user's operand from the previous IV user's operand.
2658 void LSRInstance::GenerateIVChain(const IVChain &Chain, SCEVExpander &Rewriter,
2659                                   SmallVectorImpl<WeakVH> &DeadInsts) {
2660   // Find the new IVOperand for the head of the chain. It may have been replaced
2661   // by LSR.
2662   const IVInc &Head = Chain[0];
2663   User::op_iterator IVOpEnd = Head.UserInst->op_end();
2664   User::op_iterator IVOpIter = findIVOperand(Head.UserInst->op_begin(),
2665                                              IVOpEnd, L, SE);
2666   Value *IVSrc = 0;
2667   while (IVOpIter != IVOpEnd) {
2668     IVSrc = getWideOperand(*IVOpIter);
2669
2670     // If this operand computes the expression that the chain needs, we may use
2671     // it. (Check this after setting IVSrc which is used below.)
2672     //
2673     // Note that if Head.IncExpr is wider than IVSrc, then this phi is too
2674     // narrow for the chain, so we can no longer use it. We do allow using a
2675     // wider phi, assuming the LSR checked for free truncation. In that case we
2676     // should already have a truncate on this operand such that
2677     // getSCEV(IVSrc) == IncExpr.
2678     if (SE.getSCEV(*IVOpIter) == Head.IncExpr
2679         || SE.getSCEV(IVSrc) == Head.IncExpr) {
2680       break;
2681     }
2682     IVOpIter = findIVOperand(llvm::next(IVOpIter), IVOpEnd, L, SE);
2683   }
2684   if (IVOpIter == IVOpEnd) {
2685     // Gracefully give up on this chain.
2686     DEBUG(dbgs() << "Concealed chain head: " << *Head.UserInst << "\n");
2687     return;
2688   }
2689
2690   DEBUG(dbgs() << "Generate chain at: " << *IVSrc << "\n");
2691   Type *IVTy = IVSrc->getType();
2692   Type *IntTy = SE.getEffectiveSCEVType(IVTy);
2693   const SCEV *LeftOverExpr = 0;
2694   for (IVChain::const_iterator IncI = llvm::next(Chain.begin()),
2695          IncE = Chain.end(); IncI != IncE; ++IncI) {
2696
2697     Instruction *InsertPt = IncI->UserInst;
2698     if (isa<PHINode>(InsertPt))
2699       InsertPt = L->getLoopLatch()->getTerminator();
2700
2701     // IVOper will replace the current IV User's operand. IVSrc is the IV
2702     // value currently held in a register.
2703     Value *IVOper = IVSrc;
2704     if (!IncI->IncExpr->isZero()) {
2705       // IncExpr was the result of subtraction of two narrow values, so must
2706       // be signed.
2707       const SCEV *IncExpr = SE.getNoopOrSignExtend(IncI->IncExpr, IntTy);
2708       LeftOverExpr = LeftOverExpr ?
2709         SE.getAddExpr(LeftOverExpr, IncExpr) : IncExpr;
2710     }
2711     if (LeftOverExpr && !LeftOverExpr->isZero()) {
2712       // Expand the IV increment.
2713       Rewriter.clearPostInc();
2714       Value *IncV = Rewriter.expandCodeFor(LeftOverExpr, IntTy, InsertPt);
2715       const SCEV *IVOperExpr = SE.getAddExpr(SE.getUnknown(IVSrc),
2716                                              SE.getUnknown(IncV));
2717       IVOper = Rewriter.expandCodeFor(IVOperExpr, IVTy, InsertPt);
2718
2719       // If an IV increment can't be folded, use it as the next IV value.
2720       if (!canFoldIVIncExpr(LeftOverExpr, IncI->UserInst, IncI->IVOperand,
2721                             TLI)) {
2722         assert(IVTy == IVOper->getType() && "inconsistent IV increment type");
2723         IVSrc = IVOper;
2724         LeftOverExpr = 0;
2725       }
2726     }
2727     Type *OperTy = IncI->IVOperand->getType();
2728     if (IVTy != OperTy) {
2729       assert(SE.getTypeSizeInBits(IVTy) >= SE.getTypeSizeInBits(OperTy) &&
2730              "cannot extend a chained IV");
2731       IRBuilder<> Builder(InsertPt);
2732       IVOper = Builder.CreateTruncOrBitCast(IVOper, OperTy, "lsr.chain");
2733     }
2734     IncI->UserInst->replaceUsesOfWith(IncI->IVOperand, IVOper);
2735     DeadInsts.push_back(IncI->IVOperand);
2736   }
2737   // If LSR created a new, wider phi, we may also replace its postinc. We only
2738   // do this if we also found a wide value for the head of the chain.
2739   if (isa<PHINode>(Chain.back().UserInst)) {
2740     for (BasicBlock::iterator I = L->getHeader()->begin();
2741          PHINode *Phi = dyn_cast<PHINode>(I); ++I) {
2742       if (!isCompatibleIVType(Phi, IVSrc))
2743         continue;
2744       Instruction *PostIncV = dyn_cast<Instruction>(
2745         Phi->getIncomingValueForBlock(L->getLoopLatch()));
2746       if (!PostIncV || (SE.getSCEV(PostIncV) != SE.getSCEV(IVSrc)))
2747         continue;
2748       Value *IVOper = IVSrc;
2749       Type *PostIncTy = PostIncV->getType();
2750       if (IVTy != PostIncTy) {
2751         assert(PostIncTy->isPointerTy() && "mixing int/ptr IV types");
2752         IRBuilder<> Builder(L->getLoopLatch()->getTerminator());
2753         Builder.SetCurrentDebugLocation(PostIncV->getDebugLoc());
2754         IVOper = Builder.CreatePointerCast(IVSrc, PostIncTy, "lsr.chain");
2755       }
2756       Phi->replaceUsesOfWith(PostIncV, IVOper);
2757       DeadInsts.push_back(PostIncV);
2758     }
2759   }
2760 }
2761
2762 void LSRInstance::CollectFixupsAndInitialFormulae() {
2763   for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) {
2764     Instruction *UserInst = UI->getUser();
2765     // Skip IV users that are part of profitable IV Chains.
2766     User::op_iterator UseI = std::find(UserInst->op_begin(), UserInst->op_end(),
2767                                        UI->getOperandValToReplace());
2768     assert(UseI != UserInst->op_end() && "cannot find IV operand");
2769     if (IVIncSet.count(UseI))
2770       continue;
2771
2772     // Record the uses.
2773     LSRFixup &LF = getNewFixup();
2774     LF.UserInst = UserInst;
2775     LF.OperandValToReplace = UI->getOperandValToReplace();
2776     LF.PostIncLoops = UI->getPostIncLoops();
2777
2778     LSRUse::KindType Kind = LSRUse::Basic;
2779     Type *AccessTy = 0;
2780     if (isAddressUse(LF.UserInst, LF.OperandValToReplace)) {
2781       Kind = LSRUse::Address;
2782       AccessTy = getAccessType(LF.UserInst);
2783     }
2784
2785     const SCEV *S = IU.getExpr(*UI);
2786
2787     // Equality (== and !=) ICmps are special. We can rewrite (i == N) as
2788     // (N - i == 0), and this allows (N - i) to be the expression that we work
2789     // with rather than just N or i, so we can consider the register
2790     // requirements for both N and i at the same time. Limiting this code to
2791     // equality icmps is not a problem because all interesting loops use
2792     // equality icmps, thanks to IndVarSimplify.
2793     if (ICmpInst *CI = dyn_cast<ICmpInst>(LF.UserInst))
2794       if (CI->isEquality()) {
2795         // Swap the operands if needed to put the OperandValToReplace on the
2796         // left, for consistency.
2797         Value *NV = CI->getOperand(1);
2798         if (NV == LF.OperandValToReplace) {
2799           CI->setOperand(1, CI->getOperand(0));
2800           CI->setOperand(0, NV);
2801           NV = CI->getOperand(1);
2802           Changed = true;
2803         }
2804
2805         // x == y  -->  x - y == 0
2806         const SCEV *N = SE.getSCEV(NV);
2807         if (SE.isLoopInvariant(N, L)) {
2808           // S is normalized, so normalize N before folding it into S
2809           // to keep the result normalized.
2810           N = TransformForPostIncUse(Normalize, N, CI, 0,
2811                                      LF.PostIncLoops, SE, DT);
2812           Kind = LSRUse::ICmpZero;
2813           S = SE.getMinusSCEV(N, S);
2814         }
2815
2816         // -1 and the negations of all interesting strides (except the negation
2817         // of -1) are now also interesting.
2818         for (size_t i = 0, e = Factors.size(); i != e; ++i)
2819           if (Factors[i] != -1)
2820             Factors.insert(-(uint64_t)Factors[i]);
2821         Factors.insert(-1);
2822       }
2823
2824     // Set up the initial formula for this use.
2825     std::pair<size_t, int64_t> P = getUse(S, Kind, AccessTy);
2826     LF.LUIdx = P.first;
2827     LF.Offset = P.second;
2828     LSRUse &LU = Uses[LF.LUIdx];
2829     LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
2830     if (!LU.WidestFixupType ||
2831         SE.getTypeSizeInBits(LU.WidestFixupType) <
2832         SE.getTypeSizeInBits(LF.OperandValToReplace->getType()))
2833       LU.WidestFixupType = LF.OperandValToReplace->getType();
2834
2835     // If this is the first use of this LSRUse, give it a formula.
2836     if (LU.Formulae.empty()) {
2837       InsertInitialFormula(S, LU, LF.LUIdx);
2838       CountRegisters(LU.Formulae.back(), LF.LUIdx);
2839     }
2840   }
2841
2842   DEBUG(print_fixups(dbgs()));
2843 }
2844
2845 /// InsertInitialFormula - Insert a formula for the given expression into
2846 /// the given use, separating out loop-variant portions from loop-invariant
2847 /// and loop-computable portions.
2848 void
2849 LSRInstance::InsertInitialFormula(const SCEV *S, LSRUse &LU, size_t LUIdx) {
2850   Formula F;
2851   F.InitialMatch(S, L, SE);
2852   bool Inserted = InsertFormula(LU, LUIdx, F);
2853   assert(Inserted && "Initial formula already exists!"); (void)Inserted;
2854 }
2855
2856 /// InsertSupplementalFormula - Insert a simple single-register formula for
2857 /// the given expression into the given use.
2858 void
2859 LSRInstance::InsertSupplementalFormula(const SCEV *S,
2860                                        LSRUse &LU, size_t LUIdx) {
2861   Formula F;
2862   F.BaseRegs.push_back(S);
2863   F.AM.HasBaseReg = true;
2864   bool Inserted = InsertFormula(LU, LUIdx, F);
2865   assert(Inserted && "Supplemental formula already exists!"); (void)Inserted;
2866 }
2867
2868 /// CountRegisters - Note which registers are used by the given formula,
2869 /// updating RegUses.
2870 void LSRInstance::CountRegisters(const Formula &F, size_t LUIdx) {
2871   if (F.ScaledReg)
2872     RegUses.CountRegister(F.ScaledReg, LUIdx);
2873   for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
2874        E = F.BaseRegs.end(); I != E; ++I)
2875     RegUses.CountRegister(*I, LUIdx);
2876 }
2877
2878 /// InsertFormula - If the given formula has not yet been inserted, add it to
2879 /// the list, and return true. Return false otherwise.
2880 bool LSRInstance::InsertFormula(LSRUse &LU, unsigned LUIdx, const Formula &F) {
2881   if (!LU.InsertFormula(F))
2882     return false;
2883
2884   CountRegisters(F, LUIdx);
2885   return true;
2886 }
2887
2888 /// CollectLoopInvariantFixupsAndFormulae - Check for other uses of
2889 /// loop-invariant values which we're tracking. These other uses will pin these
2890 /// values in registers, making them less profitable for elimination.
2891 /// TODO: This currently misses non-constant addrec step registers.
2892 /// TODO: Should this give more weight to users inside the loop?
2893 void
2894 LSRInstance::CollectLoopInvariantFixupsAndFormulae() {
2895   SmallVector<const SCEV *, 8> Worklist(RegUses.begin(), RegUses.end());
2896   SmallPtrSet<const SCEV *, 8> Inserted;
2897
2898   while (!Worklist.empty()) {
2899     const SCEV *S = Worklist.pop_back_val();
2900
2901     if (const SCEVNAryExpr *N = dyn_cast<SCEVNAryExpr>(S))
2902       Worklist.append(N->op_begin(), N->op_end());
2903     else if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S))
2904       Worklist.push_back(C->getOperand());
2905     else if (const SCEVUDivExpr *D = dyn_cast<SCEVUDivExpr>(S)) {
2906       Worklist.push_back(D->getLHS());
2907       Worklist.push_back(D->getRHS());
2908     } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
2909       if (!Inserted.insert(U)) continue;
2910       const Value *V = U->getValue();
2911       if (const Instruction *Inst = dyn_cast<Instruction>(V)) {
2912         // Look for instructions defined outside the loop.
2913         if (L->contains(Inst)) continue;
2914       } else if (isa<UndefValue>(V))
2915         // Undef doesn't have a live range, so it doesn't matter.
2916         continue;
2917       for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
2918            UI != UE; ++UI) {
2919         const Instruction *UserInst = dyn_cast<Instruction>(*UI);
2920         // Ignore non-instructions.
2921         if (!UserInst)
2922           continue;
2923         // Ignore instructions in other functions (as can happen with
2924         // Constants).
2925         if (UserInst->getParent()->getParent() != L->getHeader()->getParent())
2926           continue;
2927         // Ignore instructions not dominated by the loop.
2928         const BasicBlock *UseBB = !isa<PHINode>(UserInst) ?
2929           UserInst->getParent() :
2930           cast<PHINode>(UserInst)->getIncomingBlock(
2931             PHINode::getIncomingValueNumForOperand(UI.getOperandNo()));
2932         if (!DT.dominates(L->getHeader(), UseBB))
2933           continue;
2934         // Ignore uses which are part of other SCEV expressions, to avoid
2935         // analyzing them multiple times.
2936         if (SE.isSCEVable(UserInst->getType())) {
2937           const SCEV *UserS = SE.getSCEV(const_cast<Instruction *>(UserInst));
2938           // If the user is a no-op, look through to its uses.
2939           if (!isa<SCEVUnknown>(UserS))
2940             continue;
2941           if (UserS == U) {
2942             Worklist.push_back(
2943               SE.getUnknown(const_cast<Instruction *>(UserInst)));
2944             continue;
2945           }
2946         }
2947         // Ignore icmp instructions which are already being analyzed.
2948         if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UserInst)) {
2949           unsigned OtherIdx = !UI.getOperandNo();
2950           Value *OtherOp = const_cast<Value *>(ICI->getOperand(OtherIdx));
2951           if (SE.hasComputableLoopEvolution(SE.getSCEV(OtherOp), L))
2952             continue;
2953         }
2954
2955         LSRFixup &LF = getNewFixup();
2956         LF.UserInst = const_cast<Instruction *>(UserInst);
2957         LF.OperandValToReplace = UI.getUse();
2958         std::pair<size_t, int64_t> P = getUse(S, LSRUse::Basic, 0);
2959         LF.LUIdx = P.first;
2960         LF.Offset = P.second;
2961         LSRUse &LU = Uses[LF.LUIdx];
2962         LU.AllFixupsOutsideLoop &= LF.isUseFullyOutsideLoop(L);
2963         if (!LU.WidestFixupType ||
2964             SE.getTypeSizeInBits(LU.WidestFixupType) <
2965             SE.getTypeSizeInBits(LF.OperandValToReplace->getType()))
2966           LU.WidestFixupType = LF.OperandValToReplace->getType();
2967         InsertSupplementalFormula(U, LU, LF.LUIdx);
2968         CountRegisters(LU.Formulae.back(), Uses.size() - 1);
2969         break;
2970       }
2971     }
2972   }
2973 }
2974
2975 /// CollectSubexprs - Split S into subexpressions which can be pulled out into
2976 /// separate registers. If C is non-null, multiply each subexpression by C.
2977 static void CollectSubexprs(const SCEV *S, const SCEVConstant *C,
2978                             SmallVectorImpl<const SCEV *> &Ops,
2979                             const Loop *L,
2980                             ScalarEvolution &SE) {
2981   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
2982     // Break out add operands.
2983     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
2984          I != E; ++I)
2985       CollectSubexprs(*I, C, Ops, L, SE);
2986     return;
2987   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
2988     // Split a non-zero base out of an addrec.
2989     if (!AR->getStart()->isZero()) {
2990       CollectSubexprs(SE.getAddRecExpr(SE.getConstant(AR->getType(), 0),
2991                                        AR->getStepRecurrence(SE),
2992                                        AR->getLoop(),
2993                                        //FIXME: AR->getNoWrapFlags(SCEV::FlagNW)
2994                                        SCEV::FlagAnyWrap),
2995                       C, Ops, L, SE);
2996       CollectSubexprs(AR->getStart(), C, Ops, L, SE);
2997       return;
2998     }
2999   } else if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) {
3000     // Break (C * (a + b + c)) into C*a + C*b + C*c.
3001     if (Mul->getNumOperands() == 2)
3002       if (const SCEVConstant *Op0 =
3003             dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
3004         CollectSubexprs(Mul->getOperand(1),
3005                         C ? cast<SCEVConstant>(SE.getMulExpr(C, Op0)) : Op0,
3006                         Ops, L, SE);
3007         return;
3008       }
3009   }
3010
3011   // Otherwise use the value itself, optionally with a scale applied.
3012   Ops.push_back(C ? SE.getMulExpr(C, S) : S);
3013 }
3014
3015 /// GenerateReassociations - Split out subexpressions from adds and the bases of
3016 /// addrecs.
3017 void LSRInstance::GenerateReassociations(LSRUse &LU, unsigned LUIdx,
3018                                          Formula Base,
3019                                          unsigned Depth) {
3020   // Arbitrarily cap recursion to protect compile time.
3021   if (Depth >= 3) return;
3022
3023   for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) {
3024     const SCEV *BaseReg = Base.BaseRegs[i];
3025
3026     SmallVector<const SCEV *, 8> AddOps;
3027     CollectSubexprs(BaseReg, 0, AddOps, L, SE);
3028
3029     if (AddOps.size() == 1) continue;
3030
3031     for (SmallVectorImpl<const SCEV *>::const_iterator J = AddOps.begin(),
3032          JE = AddOps.end(); J != JE; ++J) {
3033
3034       // Loop-variant "unknown" values are uninteresting; we won't be able to
3035       // do anything meaningful with them.
3036       if (isa<SCEVUnknown>(*J) && !SE.isLoopInvariant(*J, L))
3037         continue;
3038
3039       // Don't pull a constant into a register if the constant could be folded
3040       // into an immediate field.
3041       if (isAlwaysFoldable(*J, LU.MinOffset, LU.MaxOffset,
3042                            Base.getNumRegs() > 1,
3043                            LU.Kind, LU.AccessTy, TLI, SE))
3044         continue;
3045
3046       // Collect all operands except *J.
3047       SmallVector<const SCEV *, 8> InnerAddOps
3048         (((const SmallVector<const SCEV *, 8> &)AddOps).begin(), J);
3049       InnerAddOps.append
3050         (llvm::next(J), ((const SmallVector<const SCEV *, 8> &)AddOps).end());
3051
3052       // Don't leave just a constant behind in a register if the constant could
3053       // be folded into an immediate field.
3054       if (InnerAddOps.size() == 1 &&
3055           isAlwaysFoldable(InnerAddOps[0], LU.MinOffset, LU.MaxOffset,
3056                            Base.getNumRegs() > 1,
3057                            LU.Kind, LU.AccessTy, TLI, SE))
3058         continue;
3059
3060       const SCEV *InnerSum = SE.getAddExpr(InnerAddOps);
3061       if (InnerSum->isZero())
3062         continue;
3063       Formula F = Base;
3064
3065       // Add the remaining pieces of the add back into the new formula.
3066       const SCEVConstant *InnerSumSC = dyn_cast<SCEVConstant>(InnerSum);
3067       if (TLI && InnerSumSC &&
3068           SE.getTypeSizeInBits(InnerSumSC->getType()) <= 64 &&
3069           TLI->isLegalAddImmediate((uint64_t)F.UnfoldedOffset +
3070                                    InnerSumSC->getValue()->getZExtValue())) {
3071         F.UnfoldedOffset = (uint64_t)F.UnfoldedOffset +
3072                            InnerSumSC->getValue()->getZExtValue();
3073         F.BaseRegs.erase(F.BaseRegs.begin() + i);
3074       } else
3075         F.BaseRegs[i] = InnerSum;
3076
3077       // Add J as its own register, or an unfolded immediate.
3078       const SCEVConstant *SC = dyn_cast<SCEVConstant>(*J);
3079       if (TLI && SC && SE.getTypeSizeInBits(SC->getType()) <= 64 &&
3080           TLI->isLegalAddImmediate((uint64_t)F.UnfoldedOffset +
3081                                    SC->getValue()->getZExtValue()))
3082         F.UnfoldedOffset = (uint64_t)F.UnfoldedOffset +
3083                            SC->getValue()->getZExtValue();
3084       else
3085         F.BaseRegs.push_back(*J);
3086
3087       if (InsertFormula(LU, LUIdx, F))
3088         // If that formula hadn't been seen before, recurse to find more like
3089         // it.
3090         GenerateReassociations(LU, LUIdx, LU.Formulae.back(), Depth+1);
3091     }
3092   }
3093 }
3094
3095 /// GenerateCombinations - Generate a formula consisting of all of the
3096 /// loop-dominating registers added into a single register.
3097 void LSRInstance::GenerateCombinations(LSRUse &LU, unsigned LUIdx,
3098                                        Formula Base) {
3099   // This method is only interesting on a plurality of registers.
3100   if (Base.BaseRegs.size() <= 1) return;
3101
3102   Formula F = Base;
3103   F.BaseRegs.clear();
3104   SmallVector<const SCEV *, 4> Ops;
3105   for (SmallVectorImpl<const SCEV *>::const_iterator
3106        I = Base.BaseRegs.begin(), E = Base.BaseRegs.end(); I != E; ++I) {
3107     const SCEV *BaseReg = *I;
3108     if (SE.properlyDominates(BaseReg, L->getHeader()) &&
3109         !SE.hasComputableLoopEvolution(BaseReg, L))
3110       Ops.push_back(BaseReg);
3111     else
3112       F.BaseRegs.push_back(BaseReg);
3113   }
3114   if (Ops.size() > 1) {
3115     const SCEV *Sum = SE.getAddExpr(Ops);
3116     // TODO: If Sum is zero, it probably means ScalarEvolution missed an
3117     // opportunity to fold something. For now, just ignore such cases
3118     // rather than proceed with zero in a register.
3119     if (!Sum->isZero()) {
3120       F.BaseRegs.push_back(Sum);
3121       (void)InsertFormula(LU, LUIdx, F);
3122     }
3123   }
3124 }
3125
3126 /// GenerateSymbolicOffsets - Generate reuse formulae using symbolic offsets.
3127 void LSRInstance::GenerateSymbolicOffsets(LSRUse &LU, unsigned LUIdx,
3128                                           Formula Base) {
3129   // We can't add a symbolic offset if the address already contains one.
3130   if (Base.AM.BaseGV) return;
3131
3132   for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) {
3133     const SCEV *G = Base.BaseRegs[i];
3134     GlobalValue *GV = ExtractSymbol(G, SE);
3135     if (G->isZero() || !GV)
3136       continue;
3137     Formula F = Base;
3138     F.AM.BaseGV = GV;
3139     if (!isLegalUse(F.AM, LU.MinOffset, LU.MaxOffset,
3140                     LU.Kind, LU.AccessTy, TLI))
3141       continue;
3142     F.BaseRegs[i] = G;
3143     (void)InsertFormula(LU, LUIdx, F);
3144   }
3145 }
3146
3147 /// GenerateConstantOffsets - Generate reuse formulae using symbolic offsets.
3148 void LSRInstance::GenerateConstantOffsets(LSRUse &LU, unsigned LUIdx,
3149                                           Formula Base) {
3150   // TODO: For now, just add the min and max offset, because it usually isn't
3151   // worthwhile looking at everything inbetween.
3152   SmallVector<int64_t, 2> Worklist;
3153   Worklist.push_back(LU.MinOffset);
3154   if (LU.MaxOffset != LU.MinOffset)
3155     Worklist.push_back(LU.MaxOffset);
3156
3157   for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i) {
3158     const SCEV *G = Base.BaseRegs[i];
3159
3160     for (SmallVectorImpl<int64_t>::const_iterator I = Worklist.begin(),
3161          E = Worklist.end(); I != E; ++I) {
3162       Formula F = Base;
3163       F.AM.BaseOffs = (uint64_t)Base.AM.BaseOffs - *I;
3164       if (isLegalUse(F.AM, LU.MinOffset - *I, LU.MaxOffset - *I,
3165                      LU.Kind, LU.AccessTy, TLI)) {
3166         // Add the offset to the base register.
3167         const SCEV *NewG = SE.getAddExpr(SE.getConstant(G->getType(), *I), G);
3168         // If it cancelled out, drop the base register, otherwise update it.
3169         if (NewG->isZero()) {
3170           std::swap(F.BaseRegs[i], F.BaseRegs.back());
3171           F.BaseRegs.pop_back();
3172         } else
3173           F.BaseRegs[i] = NewG;
3174
3175         (void)InsertFormula(LU, LUIdx, F);
3176       }
3177     }
3178
3179     int64_t Imm = ExtractImmediate(G, SE);
3180     if (G->isZero() || Imm == 0)
3181       continue;
3182     Formula F = Base;
3183     F.AM.BaseOffs = (uint64_t)F.AM.BaseOffs + Imm;
3184     if (!isLegalUse(F.AM, LU.MinOffset, LU.MaxOffset,
3185                     LU.Kind, LU.AccessTy, TLI))
3186       continue;
3187     F.BaseRegs[i] = G;
3188     (void)InsertFormula(LU, LUIdx, F);
3189   }
3190 }
3191
3192 /// GenerateICmpZeroScales - For ICmpZero, check to see if we can scale up
3193 /// the comparison. For example, x == y -> x*c == y*c.
3194 void LSRInstance::GenerateICmpZeroScales(LSRUse &LU, unsigned LUIdx,
3195                                          Formula Base) {
3196   if (LU.Kind != LSRUse::ICmpZero) return;
3197
3198   // Determine the integer type for the base formula.
3199   Type *IntTy = Base.getType();
3200   if (!IntTy) return;
3201   if (SE.getTypeSizeInBits(IntTy) > 64) return;
3202
3203   // Don't do this if there is more than one offset.
3204   if (LU.MinOffset != LU.MaxOffset) return;
3205
3206   assert(!Base.AM.BaseGV && "ICmpZero use is not legal!");
3207
3208   // Check each interesting stride.
3209   for (SmallSetVector<int64_t, 8>::const_iterator
3210        I = Factors.begin(), E = Factors.end(); I != E; ++I) {
3211     int64_t Factor = *I;
3212
3213     // Check that the multiplication doesn't overflow.
3214     if (Base.AM.BaseOffs == INT64_MIN && Factor == -1)
3215       continue;
3216     int64_t NewBaseOffs = (uint64_t)Base.AM.BaseOffs * Factor;
3217     if (NewBaseOffs / Factor != Base.AM.BaseOffs)
3218       continue;
3219
3220     // Check that multiplying with the use offset doesn't overflow.
3221     int64_t Offset = LU.MinOffset;
3222     if (Offset == INT64_MIN && Factor == -1)
3223       continue;
3224     Offset = (uint64_t)Offset * Factor;
3225     if (Offset / Factor != LU.MinOffset)
3226       continue;
3227
3228     Formula F = Base;
3229     F.AM.BaseOffs = NewBaseOffs;
3230
3231     // Check that this scale is legal.
3232     if (!isLegalUse(F.AM, Offset, Offset, LU.Kind, LU.AccessTy, TLI))
3233       continue;
3234
3235     // Compensate for the use having MinOffset built into it.
3236     F.AM.BaseOffs = (uint64_t)F.AM.BaseOffs + Offset - LU.MinOffset;
3237
3238     const SCEV *FactorS = SE.getConstant(IntTy, Factor);
3239
3240     // Check that multiplying with each base register doesn't overflow.
3241     for (size_t i = 0, e = F.BaseRegs.size(); i != e; ++i) {
3242       F.BaseRegs[i] = SE.getMulExpr(F.BaseRegs[i], FactorS);
3243       if (getExactSDiv(F.BaseRegs[i], FactorS, SE) != Base.BaseRegs[i])
3244         goto next;
3245     }
3246
3247     // Check that multiplying with the scaled register doesn't overflow.
3248     if (F.ScaledReg) {
3249       F.ScaledReg = SE.getMulExpr(F.ScaledReg, FactorS);
3250       if (getExactSDiv(F.ScaledReg, FactorS, SE) != Base.ScaledReg)
3251         continue;
3252     }
3253
3254     // Check that multiplying with the unfolded offset doesn't overflow.
3255     if (F.UnfoldedOffset != 0) {
3256       if (F.UnfoldedOffset == INT64_MIN && Factor == -1)
3257         continue;
3258       F.UnfoldedOffset = (uint64_t)F.UnfoldedOffset * Factor;
3259       if (F.UnfoldedOffset / Factor != Base.UnfoldedOffset)
3260         continue;
3261     }
3262
3263     // If we make it here and it's legal, add it.
3264     (void)InsertFormula(LU, LUIdx, F);
3265   next:;
3266   }
3267 }
3268
3269 /// GenerateScales - Generate stride factor reuse formulae by making use of
3270 /// scaled-offset address modes, for example.
3271 void LSRInstance::GenerateScales(LSRUse &LU, unsigned LUIdx, Formula Base) {
3272   // Determine the integer type for the base formula.
3273   Type *IntTy = Base.getType();
3274   if (!IntTy) return;
3275
3276   // If this Formula already has a scaled register, we can't add another one.
3277   if (Base.AM.Scale != 0) return;
3278
3279   // Check each interesting stride.
3280   for (SmallSetVector<int64_t, 8>::const_iterator
3281        I = Factors.begin(), E = Factors.end(); I != E; ++I) {
3282     int64_t Factor = *I;
3283
3284     Base.AM.Scale = Factor;
3285     Base.AM.HasBaseReg = Base.BaseRegs.size() > 1;
3286     // Check whether this scale is going to be legal.
3287     if (!isLegalUse(Base.AM, LU.MinOffset, LU.MaxOffset,
3288                     LU.Kind, LU.AccessTy, TLI)) {
3289       // As a special-case, handle special out-of-loop Basic users specially.
3290       // TODO: Reconsider this special case.
3291       if (LU.Kind == LSRUse::Basic &&
3292           isLegalUse(Base.AM, LU.MinOffset, LU.MaxOffset,
3293                      LSRUse::Special, LU.AccessTy, TLI) &&
3294           LU.AllFixupsOutsideLoop)
3295         LU.Kind = LSRUse::Special;
3296       else
3297         continue;
3298     }
3299     // For an ICmpZero, negating a solitary base register won't lead to
3300     // new solutions.
3301     if (LU.Kind == LSRUse::ICmpZero &&
3302         !Base.AM.HasBaseReg && Base.AM.BaseOffs == 0 && !Base.AM.BaseGV)
3303       continue;
3304     // For each addrec base reg, apply the scale, if possible.
3305     for (size_t i = 0, e = Base.BaseRegs.size(); i != e; ++i)
3306       if (const SCEVAddRecExpr *AR =
3307             dyn_cast<SCEVAddRecExpr>(Base.BaseRegs[i])) {
3308         const SCEV *FactorS = SE.getConstant(IntTy, Factor);
3309         if (FactorS->isZero())
3310           continue;
3311         // Divide out the factor, ignoring high bits, since we'll be
3312         // scaling the value back up in the end.
3313         if (const SCEV *Quotient = getExactSDiv(AR, FactorS, SE, true)) {
3314           // TODO: This could be optimized to avoid all the copying.
3315           Formula F = Base;
3316           F.ScaledReg = Quotient;
3317           F.DeleteBaseReg(F.BaseRegs[i]);
3318           (void)InsertFormula(LU, LUIdx, F);
3319         }
3320       }
3321   }
3322 }
3323
3324 /// GenerateTruncates - Generate reuse formulae from different IV types.
3325 void LSRInstance::GenerateTruncates(LSRUse &LU, unsigned LUIdx, Formula Base) {
3326   // This requires TargetLowering to tell us which truncates are free.
3327   if (!TLI) return;
3328
3329   // Don't bother truncating symbolic values.
3330   if (Base.AM.BaseGV) return;
3331
3332   // Determine the integer type for the base formula.
3333   Type *DstTy = Base.getType();
3334   if (!DstTy) return;
3335   DstTy = SE.getEffectiveSCEVType(DstTy);
3336
3337   for (SmallSetVector<Type *, 4>::const_iterator
3338        I = Types.begin(), E = Types.end(); I != E; ++I) {
3339     Type *SrcTy = *I;
3340     if (SrcTy != DstTy && TLI->isTruncateFree(SrcTy, DstTy)) {
3341       Formula F = Base;
3342
3343       if (F.ScaledReg) F.ScaledReg = SE.getAnyExtendExpr(F.ScaledReg, *I);
3344       for (SmallVectorImpl<const SCEV *>::iterator J = F.BaseRegs.begin(),
3345            JE = F.BaseRegs.end(); J != JE; ++J)
3346         *J = SE.getAnyExtendExpr(*J, SrcTy);
3347
3348       // TODO: This assumes we've done basic processing on all uses and
3349       // have an idea what the register usage is.
3350       if (!F.hasRegsUsedByUsesOtherThan(LUIdx, RegUses))
3351         continue;
3352
3353       (void)InsertFormula(LU, LUIdx, F);
3354     }
3355   }
3356 }
3357
3358 namespace {
3359
3360 /// WorkItem - Helper class for GenerateCrossUseConstantOffsets. It's used to
3361 /// defer modifications so that the search phase doesn't have to worry about
3362 /// the data structures moving underneath it.
3363 struct WorkItem {
3364   size_t LUIdx;
3365   int64_t Imm;
3366   const SCEV *OrigReg;
3367
3368   WorkItem(size_t LI, int64_t I, const SCEV *R)
3369     : LUIdx(LI), Imm(I), OrigReg(R) {}
3370
3371   void print(raw_ostream &OS) const;
3372   void dump() const;
3373 };
3374
3375 }
3376
3377 void WorkItem::print(raw_ostream &OS) const {
3378   OS << "in formulae referencing " << *OrigReg << " in use " << LUIdx
3379      << " , add offset " << Imm;
3380 }
3381
3382 void WorkItem::dump() const {
3383   print(errs()); errs() << '\n';
3384 }
3385
3386 /// GenerateCrossUseConstantOffsets - Look for registers which are a constant
3387 /// distance apart and try to form reuse opportunities between them.
3388 void LSRInstance::GenerateCrossUseConstantOffsets() {
3389   // Group the registers by their value without any added constant offset.
3390   typedef std::map<int64_t, const SCEV *> ImmMapTy;
3391   typedef DenseMap<const SCEV *, ImmMapTy> RegMapTy;
3392   RegMapTy Map;
3393   DenseMap<const SCEV *, SmallBitVector> UsedByIndicesMap;
3394   SmallVector<const SCEV *, 8> Sequence;
3395   for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end();
3396        I != E; ++I) {
3397     const SCEV *Reg = *I;
3398     int64_t Imm = ExtractImmediate(Reg, SE);
3399     std::pair<RegMapTy::iterator, bool> Pair =
3400       Map.insert(std::make_pair(Reg, ImmMapTy()));
3401     if (Pair.second)
3402       Sequence.push_back(Reg);
3403     Pair.first->second.insert(std::make_pair(Imm, *I));
3404     UsedByIndicesMap[Reg] |= RegUses.getUsedByIndices(*I);
3405   }
3406
3407   // Now examine each set of registers with the same base value. Build up
3408   // a list of work to do and do the work in a separate step so that we're
3409   // not adding formulae and register counts while we're searching.
3410   SmallVector<WorkItem, 32> WorkItems;
3411   SmallSet<std::pair<size_t, int64_t>, 32> UniqueItems;
3412   for (SmallVectorImpl<const SCEV *>::const_iterator I = Sequence.begin(),
3413        E = Sequence.end(); I != E; ++I) {
3414     const SCEV *Reg = *I;
3415     const ImmMapTy &Imms = Map.find(Reg)->second;
3416
3417     // It's not worthwhile looking for reuse if there's only one offset.
3418     if (Imms.size() == 1)
3419       continue;
3420
3421     DEBUG(dbgs() << "Generating cross-use offsets for " << *Reg << ':';
3422           for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end();
3423                J != JE; ++J)
3424             dbgs() << ' ' << J->first;
3425           dbgs() << '\n');
3426
3427     // Examine each offset.
3428     for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end();
3429          J != JE; ++J) {
3430       const SCEV *OrigReg = J->second;
3431
3432       int64_t JImm = J->first;
3433       const SmallBitVector &UsedByIndices = RegUses.getUsedByIndices(OrigReg);
3434
3435       if (!isa<SCEVConstant>(OrigReg) &&
3436           UsedByIndicesMap[Reg].count() == 1) {
3437         DEBUG(dbgs() << "Skipping cross-use reuse for " << *OrigReg << '\n');
3438         continue;
3439       }
3440
3441       // Conservatively examine offsets between this orig reg a few selected
3442       // other orig regs.
3443       ImmMapTy::const_iterator OtherImms[] = {
3444         Imms.begin(), prior(Imms.end()),
3445         Imms.lower_bound((Imms.begin()->first + prior(Imms.end())->first) / 2)
3446       };
3447       for (size_t i = 0, e = array_lengthof(OtherImms); i != e; ++i) {
3448         ImmMapTy::const_iterator M = OtherImms[i];
3449         if (M == J || M == JE) continue;
3450
3451         // Compute the difference between the two.
3452         int64_t Imm = (uint64_t)JImm - M->first;
3453         for (int LUIdx = UsedByIndices.find_first(); LUIdx != -1;
3454              LUIdx = UsedByIndices.find_next(LUIdx))
3455           // Make a memo of this use, offset, and register tuple.
3456           if (UniqueItems.insert(std::make_pair(LUIdx, Imm)))
3457             WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg));
3458       }
3459     }
3460   }
3461
3462   Map.clear();
3463   Sequence.clear();
3464   UsedByIndicesMap.clear();
3465   UniqueItems.clear();
3466
3467   // Now iterate through the worklist and add new formulae.
3468   for (SmallVectorImpl<WorkItem>::const_iterator I = WorkItems.begin(),
3469        E = WorkItems.end(); I != E; ++I) {
3470     const WorkItem &WI = *I;
3471     size_t LUIdx = WI.LUIdx;
3472     LSRUse &LU = Uses[LUIdx];
3473     int64_t Imm = WI.Imm;
3474     const SCEV *OrigReg = WI.OrigReg;
3475
3476     Type *IntTy = SE.getEffectiveSCEVType(OrigReg->getType());
3477     const SCEV *NegImmS = SE.getSCEV(ConstantInt::get(IntTy, -(uint64_t)Imm));
3478     unsigned BitWidth = SE.getTypeSizeInBits(IntTy);
3479
3480     // TODO: Use a more targeted data structure.
3481     for (size_t L = 0, LE = LU.Formulae.size(); L != LE; ++L) {
3482       const Formula &F = LU.Formulae[L];
3483       // Use the immediate in the scaled register.
3484       if (F.ScaledReg == OrigReg) {
3485         int64_t Offs = (uint64_t)F.AM.BaseOffs +
3486                        Imm * (uint64_t)F.AM.Scale;
3487         // Don't create 50 + reg(-50).
3488         if (F.referencesReg(SE.getSCEV(
3489                    ConstantInt::get(IntTy, -(uint64_t)Offs))))
3490           continue;
3491         Formula NewF = F;
3492         NewF.AM.BaseOffs = Offs;
3493         if (!isLegalUse(NewF.AM, LU.MinOffset, LU.MaxOffset,
3494                         LU.Kind, LU.AccessTy, TLI))
3495           continue;
3496         NewF.ScaledReg = SE.getAddExpr(NegImmS, NewF.ScaledReg);
3497
3498         // If the new scale is a constant in a register, and adding the constant
3499         // value to the immediate would produce a value closer to zero than the
3500         // immediate itself, then the formula isn't worthwhile.
3501         if (const SCEVConstant *C = dyn_cast<SCEVConstant>(NewF.ScaledReg))
3502           if (C->getValue()->isNegative() !=
3503                 (NewF.AM.BaseOffs < 0) &&
3504               (C->getValue()->getValue().abs() * APInt(BitWidth, F.AM.Scale))
3505                 .ule(abs64(NewF.AM.BaseOffs)))
3506             continue;
3507
3508         // OK, looks good.
3509         (void)InsertFormula(LU, LUIdx, NewF);
3510       } else {
3511         // Use the immediate in a base register.
3512         for (size_t N = 0, NE = F.BaseRegs.size(); N != NE; ++N) {
3513           const SCEV *BaseReg = F.BaseRegs[N];
3514           if (BaseReg != OrigReg)
3515             continue;
3516           Formula NewF = F;
3517           NewF.AM.BaseOffs = (uint64_t)NewF.AM.BaseOffs + Imm;
3518           if (!isLegalUse(NewF.AM, LU.MinOffset, LU.MaxOffset,
3519                           LU.Kind, LU.AccessTy, TLI)) {
3520             if (!TLI ||
3521                 !TLI->isLegalAddImmediate((uint64_t)NewF.UnfoldedOffset + Imm))
3522               continue;
3523             NewF = F;
3524             NewF.UnfoldedOffset = (uint64_t)NewF.UnfoldedOffset + Imm;
3525           }
3526           NewF.BaseRegs[N] = SE.getAddExpr(NegImmS, BaseReg);
3527
3528           // If the new formula has a constant in a register, and adding the
3529           // constant value to the immediate would produce a value closer to
3530           // zero than the immediate itself, then the formula isn't worthwhile.
3531           for (SmallVectorImpl<const SCEV *>::const_iterator
3532                J = NewF.BaseRegs.begin(), JE = NewF.BaseRegs.end();
3533                J != JE; ++J)
3534             if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*J))
3535               if ((C->getValue()->getValue() + NewF.AM.BaseOffs).abs().slt(
3536                    abs64(NewF.AM.BaseOffs)) &&
3537                   (C->getValue()->getValue() +
3538                    NewF.AM.BaseOffs).countTrailingZeros() >=
3539                    CountTrailingZeros_64(NewF.AM.BaseOffs))
3540                 goto skip_formula;
3541
3542           // Ok, looks good.
3543           (void)InsertFormula(LU, LUIdx, NewF);
3544           break;
3545         skip_formula:;
3546         }
3547       }
3548     }
3549   }
3550 }
3551
3552 /// GenerateAllReuseFormulae - Generate formulae for each use.
3553 void
3554 LSRInstance::GenerateAllReuseFormulae() {
3555   // This is split into multiple loops so that hasRegsUsedByUsesOtherThan
3556   // queries are more precise.
3557   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3558     LSRUse &LU = Uses[LUIdx];
3559     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3560       GenerateReassociations(LU, LUIdx, LU.Formulae[i]);
3561     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3562       GenerateCombinations(LU, LUIdx, LU.Formulae[i]);
3563   }
3564   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3565     LSRUse &LU = Uses[LUIdx];
3566     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3567       GenerateSymbolicOffsets(LU, LUIdx, LU.Formulae[i]);
3568     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3569       GenerateConstantOffsets(LU, LUIdx, LU.Formulae[i]);
3570     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3571       GenerateICmpZeroScales(LU, LUIdx, LU.Formulae[i]);
3572     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3573       GenerateScales(LU, LUIdx, LU.Formulae[i]);
3574   }
3575   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3576     LSRUse &LU = Uses[LUIdx];
3577     for (size_t i = 0, f = LU.Formulae.size(); i != f; ++i)
3578       GenerateTruncates(LU, LUIdx, LU.Formulae[i]);
3579   }
3580
3581   GenerateCrossUseConstantOffsets();
3582
3583   DEBUG(dbgs() << "\n"
3584                   "After generating reuse formulae:\n";
3585         print_uses(dbgs()));
3586 }
3587
3588 /// If there are multiple formulae with the same set of registers used
3589 /// by other uses, pick the best one and delete the others.
3590 void LSRInstance::FilterOutUndesirableDedicatedRegisters() {
3591   DenseSet<const SCEV *> VisitedRegs;
3592   SmallPtrSet<const SCEV *, 16> Regs;
3593   SmallPtrSet<const SCEV *, 16> LoserRegs;
3594 #ifndef NDEBUG
3595   bool ChangedFormulae = false;
3596 #endif
3597
3598   // Collect the best formula for each unique set of shared registers. This
3599   // is reset for each use.
3600   typedef DenseMap<SmallVector<const SCEV *, 2>, size_t, UniquifierDenseMapInfo>
3601     BestFormulaeTy;
3602   BestFormulaeTy BestFormulae;
3603
3604   for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3605     LSRUse &LU = Uses[LUIdx];
3606     DEBUG(dbgs() << "Filtering for use "; LU.print(dbgs()); dbgs() << '\n');
3607
3608     bool Any = false;
3609     for (size_t FIdx = 0, NumForms = LU.Formulae.size();
3610          FIdx != NumForms; ++FIdx) {
3611       Formula &F = LU.Formulae[FIdx];
3612
3613       // Some formulas are instant losers. For example, they may depend on
3614       // nonexistent AddRecs from other loops. These need to be filtered
3615       // immediately, otherwise heuristics could choose them over others leading
3616       // to an unsatisfactory solution. Passing LoserRegs into RateFormula here
3617       // avoids the need to recompute this information across formulae using the
3618       // same bad AddRec. Passing LoserRegs is also essential unless we remove
3619       // the corresponding bad register from the Regs set.
3620       Cost CostF;
3621       Regs.clear();
3622       CostF.RateFormula(F, Regs, VisitedRegs, L, LU.Offsets, SE, DT,
3623                         &LoserRegs);
3624       if (CostF.isLoser()) {
3625         // During initial formula generation, undesirable formulae are generated
3626         // by uses within other loops that have some non-trivial address mode or
3627         // use the postinc form of the IV. LSR needs to provide these formulae
3628         // as the basis of rediscovering the desired formula that uses an AddRec
3629         // corresponding to the existing phi. Once all formulae have been
3630         // generated, these initial losers may be pruned.
3631         DEBUG(dbgs() << "  Filtering loser "; F.print(dbgs());
3632               dbgs() << "\n");
3633       }
3634       else {
3635         SmallVector<const SCEV *, 2> Key;
3636         for (SmallVectorImpl<const SCEV *>::const_iterator J = F.BaseRegs.begin(),
3637                JE = F.BaseRegs.end(); J != JE; ++J) {
3638           const SCEV *Reg = *J;
3639           if (RegUses.isRegUsedByUsesOtherThan(Reg, LUIdx))
3640             Key.push_back(Reg);
3641         }
3642         if (F.ScaledReg &&
3643             RegUses.isRegUsedByUsesOtherThan(F.ScaledReg, LUIdx))
3644           Key.push_back(F.ScaledReg);
3645         // Unstable sort by host order ok, because this is only used for
3646         // uniquifying.
3647         std::sort(Key.begin(), Key.end());
3648
3649         std::pair<BestFormulaeTy::const_iterator, bool> P =
3650           BestFormulae.insert(std::make_pair(Key, FIdx));
3651         if (P.second)
3652           continue;
3653
3654         Formula &Best = LU.Formulae[P.first->second];
3655
3656         Cost CostBest;
3657         Regs.clear();
3658         CostBest.RateFormula(Best, Regs, VisitedRegs, L, LU.Offsets, SE, DT);
3659         if (CostF < CostBest)
3660           std::swap(F, Best);
3661         DEBUG(dbgs() << "  Filtering out formula "; F.print(dbgs());
3662               dbgs() << "\n"
3663                         "    in favor of formula "; Best.print(dbgs());
3664               dbgs() << '\n');
3665       }
3666 #ifndef NDEBUG
3667       ChangedFormulae = true;
3668 #endif
3669       LU.DeleteFormula(F);
3670       --FIdx;
3671       --NumForms;
3672       Any = true;
3673     }
3674
3675     // Now that we've filtered out some formulae, recompute the Regs set.
3676     if (Any)
3677       LU.RecomputeRegs(LUIdx, RegUses);
3678
3679     // Reset this to prepare for the next use.
3680     BestFormulae.clear();
3681   }
3682
3683   DEBUG(if (ChangedFormulae) {
3684           dbgs() << "\n"
3685                     "After filtering out undesirable candidates:\n";
3686           print_uses(dbgs());
3687         });
3688 }
3689
3690 // This is a rough guess that seems to work fairly well.
3691 static const size_t ComplexityLimit = UINT16_MAX;
3692
3693 /// EstimateSearchSpaceComplexity - Estimate the worst-case number of
3694 /// solutions the solver might have to consider. It almost never considers
3695 /// this many solutions because it prune the search space, but the pruning
3696 /// isn't always sufficient.
3697 size_t LSRInstance::EstimateSearchSpaceComplexity() const {
3698   size_t Power = 1;
3699   for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(),
3700        E = Uses.end(); I != E; ++I) {
3701     size_t FSize = I->Formulae.size();
3702     if (FSize >= ComplexityLimit) {
3703       Power = ComplexityLimit;
3704       break;
3705     }
3706     Power *= FSize;
3707     if (Power >= ComplexityLimit)
3708       break;
3709   }
3710   return Power;
3711 }
3712
3713 /// NarrowSearchSpaceByDetectingSupersets - When one formula uses a superset
3714 /// of the registers of another formula, it won't help reduce register
3715 /// pressure (though it may not necessarily hurt register pressure); remove
3716 /// it to simplify the system.
3717 void LSRInstance::NarrowSearchSpaceByDetectingSupersets() {
3718   if (EstimateSearchSpaceComplexity() >= ComplexityLimit) {
3719     DEBUG(dbgs() << "The search space is too complex.\n");
3720
3721     DEBUG(dbgs() << "Narrowing the search space by eliminating formulae "
3722                     "which use a superset of registers used by other "
3723                     "formulae.\n");
3724
3725     for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3726       LSRUse &LU = Uses[LUIdx];
3727       bool Any = false;
3728       for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
3729         Formula &F = LU.Formulae[i];
3730         // Look for a formula with a constant or GV in a register. If the use
3731         // also has a formula with that same value in an immediate field,
3732         // delete the one that uses a register.
3733         for (SmallVectorImpl<const SCEV *>::const_iterator
3734              I = F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) {
3735           if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*I)) {
3736             Formula NewF = F;
3737             NewF.AM.BaseOffs += C->getValue()->getSExtValue();
3738             NewF.BaseRegs.erase(NewF.BaseRegs.begin() +
3739                                 (I - F.BaseRegs.begin()));
3740             if (LU.HasFormulaWithSameRegs(NewF)) {
3741               DEBUG(dbgs() << "  Deleting "; F.print(dbgs()); dbgs() << '\n');
3742               LU.DeleteFormula(F);
3743               --i;
3744               --e;
3745               Any = true;
3746               break;
3747             }
3748           } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(*I)) {
3749             if (GlobalValue *GV = dyn_cast<GlobalValue>(U->getValue()))
3750               if (!F.AM.BaseGV) {
3751                 Formula NewF = F;
3752                 NewF.AM.BaseGV = GV;
3753                 NewF.BaseRegs.erase(NewF.BaseRegs.begin() +
3754                                     (I - F.BaseRegs.begin()));
3755                 if (LU.HasFormulaWithSameRegs(NewF)) {
3756                   DEBUG(dbgs() << "  Deleting "; F.print(dbgs());
3757                         dbgs() << '\n');
3758                   LU.DeleteFormula(F);
3759                   --i;
3760                   --e;
3761                   Any = true;
3762                   break;
3763                 }
3764               }
3765           }
3766         }
3767       }
3768       if (Any)
3769         LU.RecomputeRegs(LUIdx, RegUses);
3770     }
3771
3772     DEBUG(dbgs() << "After pre-selection:\n";
3773           print_uses(dbgs()));
3774   }
3775 }
3776
3777 /// NarrowSearchSpaceByCollapsingUnrolledCode - When there are many registers
3778 /// for expressions like A, A+1, A+2, etc., allocate a single register for
3779 /// them.
3780 void LSRInstance::NarrowSearchSpaceByCollapsingUnrolledCode() {
3781   if (EstimateSearchSpaceComplexity() >= ComplexityLimit) {
3782     DEBUG(dbgs() << "The search space is too complex.\n");
3783
3784     DEBUG(dbgs() << "Narrowing the search space by assuming that uses "
3785                     "separated by a constant offset will use the same "
3786                     "registers.\n");
3787
3788     // This is especially useful for unrolled loops.
3789
3790     for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3791       LSRUse &LU = Uses[LUIdx];
3792       for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(),
3793            E = LU.Formulae.end(); I != E; ++I) {
3794         const Formula &F = *I;
3795         if (F.AM.BaseOffs != 0 && F.AM.Scale == 0) {
3796           if (LSRUse *LUThatHas = FindUseWithSimilarFormula(F, LU)) {
3797             if (reconcileNewOffset(*LUThatHas, F.AM.BaseOffs,
3798                                    /*HasBaseReg=*/false,
3799                                    LU.Kind, LU.AccessTy)) {
3800               DEBUG(dbgs() << "  Deleting use "; LU.print(dbgs());
3801                     dbgs() << '\n');
3802
3803               LUThatHas->AllFixupsOutsideLoop &= LU.AllFixupsOutsideLoop;
3804
3805               // Update the relocs to reference the new use.
3806               for (SmallVectorImpl<LSRFixup>::iterator I = Fixups.begin(),
3807                    E = Fixups.end(); I != E; ++I) {
3808                 LSRFixup &Fixup = *I;
3809                 if (Fixup.LUIdx == LUIdx) {
3810                   Fixup.LUIdx = LUThatHas - &Uses.front();
3811                   Fixup.Offset += F.AM.BaseOffs;
3812                   // Add the new offset to LUThatHas' offset list.
3813                   if (LUThatHas->Offsets.back() != Fixup.Offset) {
3814                     LUThatHas->Offsets.push_back(Fixup.Offset);
3815                     if (Fixup.Offset > LUThatHas->MaxOffset)
3816                       LUThatHas->MaxOffset = Fixup.Offset;
3817                     if (Fixup.Offset < LUThatHas->MinOffset)
3818                       LUThatHas->MinOffset = Fixup.Offset;
3819                   }
3820                   DEBUG(dbgs() << "New fixup has offset "
3821                                << Fixup.Offset << '\n');
3822                 }
3823                 if (Fixup.LUIdx == NumUses-1)
3824                   Fixup.LUIdx = LUIdx;
3825               }
3826
3827               // Delete formulae from the new use which are no longer legal.
3828               bool Any = false;
3829               for (size_t i = 0, e = LUThatHas->Formulae.size(); i != e; ++i) {
3830                 Formula &F = LUThatHas->Formulae[i];
3831                 if (!isLegalUse(F.AM,
3832                                 LUThatHas->MinOffset, LUThatHas->MaxOffset,
3833                                 LUThatHas->Kind, LUThatHas->AccessTy, TLI)) {
3834                   DEBUG(dbgs() << "  Deleting "; F.print(dbgs());
3835                         dbgs() << '\n');
3836                   LUThatHas->DeleteFormula(F);
3837                   --i;
3838                   --e;
3839                   Any = true;
3840                 }
3841               }
3842               if (Any)
3843                 LUThatHas->RecomputeRegs(LUThatHas - &Uses.front(), RegUses);
3844
3845               // Delete the old use.
3846               DeleteUse(LU, LUIdx);
3847               --LUIdx;
3848               --NumUses;
3849               break;
3850             }
3851           }
3852         }
3853       }
3854     }
3855
3856     DEBUG(dbgs() << "After pre-selection:\n";
3857           print_uses(dbgs()));
3858   }
3859 }
3860
3861 /// NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters - Call
3862 /// FilterOutUndesirableDedicatedRegisters again, if necessary, now that
3863 /// we've done more filtering, as it may be able to find more formulae to
3864 /// eliminate.
3865 void LSRInstance::NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters(){
3866   if (EstimateSearchSpaceComplexity() >= ComplexityLimit) {
3867     DEBUG(dbgs() << "The search space is too complex.\n");
3868
3869     DEBUG(dbgs() << "Narrowing the search space by re-filtering out "
3870                     "undesirable dedicated registers.\n");
3871
3872     FilterOutUndesirableDedicatedRegisters();
3873
3874     DEBUG(dbgs() << "After pre-selection:\n";
3875           print_uses(dbgs()));
3876   }
3877 }
3878
3879 /// NarrowSearchSpaceByPickingWinnerRegs - Pick a register which seems likely
3880 /// to be profitable, and then in any use which has any reference to that
3881 /// register, delete all formulae which do not reference that register.
3882 void LSRInstance::NarrowSearchSpaceByPickingWinnerRegs() {
3883   // With all other options exhausted, loop until the system is simple
3884   // enough to handle.
3885   SmallPtrSet<const SCEV *, 4> Taken;
3886   while (EstimateSearchSpaceComplexity() >= ComplexityLimit) {
3887     // Ok, we have too many of formulae on our hands to conveniently handle.
3888     // Use a rough heuristic to thin out the list.
3889     DEBUG(dbgs() << "The search space is too complex.\n");
3890
3891     // Pick the register which is used by the most LSRUses, which is likely
3892     // to be a good reuse register candidate.
3893     const SCEV *Best = 0;
3894     unsigned BestNum = 0;
3895     for (RegUseTracker::const_iterator I = RegUses.begin(), E = RegUses.end();
3896          I != E; ++I) {
3897       const SCEV *Reg = *I;
3898       if (Taken.count(Reg))
3899         continue;
3900       if (!Best)
3901         Best = Reg;
3902       else {
3903         unsigned Count = RegUses.getUsedByIndices(Reg).count();
3904         if (Count > BestNum) {
3905           Best = Reg;
3906           BestNum = Count;
3907         }
3908       }
3909     }
3910
3911     DEBUG(dbgs() << "Narrowing the search space by assuming " << *Best
3912                  << " will yield profitable reuse.\n");
3913     Taken.insert(Best);
3914
3915     // In any use with formulae which references this register, delete formulae
3916     // which don't reference it.
3917     for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
3918       LSRUse &LU = Uses[LUIdx];
3919       if (!LU.Regs.count(Best)) continue;
3920
3921       bool Any = false;
3922       for (size_t i = 0, e = LU.Formulae.size(); i != e; ++i) {
3923         Formula &F = LU.Formulae[i];
3924         if (!F.referencesReg(Best)) {
3925           DEBUG(dbgs() << "  Deleting "; F.print(dbgs()); dbgs() << '\n');
3926           LU.DeleteFormula(F);
3927           --e;
3928           --i;
3929           Any = true;
3930           assert(e != 0 && "Use has no formulae left! Is Regs inconsistent?");
3931           continue;
3932         }
3933       }
3934
3935       if (Any)
3936         LU.RecomputeRegs(LUIdx, RegUses);
3937     }
3938
3939     DEBUG(dbgs() << "After pre-selection:\n";
3940           print_uses(dbgs()));
3941   }
3942 }
3943
3944 /// NarrowSearchSpaceUsingHeuristics - If there are an extraordinary number of
3945 /// formulae to choose from, use some rough heuristics to prune down the number
3946 /// of formulae. This keeps the main solver from taking an extraordinary amount
3947 /// of time in some worst-case scenarios.
3948 void LSRInstance::NarrowSearchSpaceUsingHeuristics() {
3949   NarrowSearchSpaceByDetectingSupersets();
3950   NarrowSearchSpaceByCollapsingUnrolledCode();
3951   NarrowSearchSpaceByRefilteringUndesirableDedicatedRegisters();
3952   NarrowSearchSpaceByPickingWinnerRegs();
3953 }
3954
3955 /// SolveRecurse - This is the recursive solver.
3956 void LSRInstance::SolveRecurse(SmallVectorImpl<const Formula *> &Solution,
3957                                Cost &SolutionCost,
3958                                SmallVectorImpl<const Formula *> &Workspace,
3959                                const Cost &CurCost,
3960                                const SmallPtrSet<const SCEV *, 16> &CurRegs,
3961                                DenseSet<const SCEV *> &VisitedRegs) const {
3962   // Some ideas:
3963   //  - prune more:
3964   //    - use more aggressive filtering
3965   //    - sort the formula so that the most profitable solutions are found first
3966   //    - sort the uses too
3967   //  - search faster:
3968   //    - don't compute a cost, and then compare. compare while computing a cost
3969   //      and bail early.
3970   //    - track register sets with SmallBitVector
3971
3972   const LSRUse &LU = Uses[Workspace.size()];
3973
3974   // If this use references any register that's already a part of the
3975   // in-progress solution, consider it a requirement that a formula must
3976   // reference that register in order to be considered. This prunes out
3977   // unprofitable searching.
3978   SmallSetVector<const SCEV *, 4> ReqRegs;
3979   for (SmallPtrSet<const SCEV *, 16>::const_iterator I = CurRegs.begin(),
3980        E = CurRegs.end(); I != E; ++I)
3981     if (LU.Regs.count(*I))
3982       ReqRegs.insert(*I);
3983
3984   SmallPtrSet<const SCEV *, 16> NewRegs;
3985   Cost NewCost;
3986   for (SmallVectorImpl<Formula>::const_iterator I = LU.Formulae.begin(),
3987        E = LU.Formulae.end(); I != E; ++I) {
3988     const Formula &F = *I;
3989
3990     // Ignore formulae which do not use any of the required registers.
3991     bool SatisfiedReqReg = true;
3992     for (SmallSetVector<const SCEV *, 4>::const_iterator J = ReqRegs.begin(),
3993          JE = ReqRegs.end(); J != JE; ++J) {
3994       const SCEV *Reg = *J;
3995       if ((!F.ScaledReg || F.ScaledReg != Reg) &&
3996           std::find(F.BaseRegs.begin(), F.BaseRegs.end(), Reg) ==
3997           F.BaseRegs.end()) {
3998         SatisfiedReqReg = false;
3999         break;
4000       }
4001     }
4002     if (!SatisfiedReqReg) {
4003       // If none of the formulae satisfied the required registers, then we could
4004       // clear ReqRegs and try again. Currently, we simply give up in this case.
4005       continue;
4006     }
4007
4008     // Evaluate the cost of the current formula. If it's already worse than
4009     // the current best, prune the search at that point.
4010     NewCost = CurCost;
4011     NewRegs = CurRegs;
4012     NewCost.RateFormula(F, NewRegs, VisitedRegs, L, LU.Offsets, SE, DT);
4013     if (NewCost < SolutionCost) {
4014       Workspace.push_back(&F);
4015       if (Workspace.size() != Uses.size()) {
4016         SolveRecurse(Solution, SolutionCost, Workspace, NewCost,
4017                      NewRegs, VisitedRegs);
4018         if (F.getNumRegs() == 1 && Workspace.size() == 1)
4019           VisitedRegs.insert(F.ScaledReg ? F.ScaledReg : F.BaseRegs[0]);
4020       } else {
4021         DEBUG(dbgs() << "New best at "; NewCost.print(dbgs());
4022               dbgs() << ".\n Regs:";
4023               for (SmallPtrSet<const SCEV *, 16>::const_iterator
4024                    I = NewRegs.begin(), E = NewRegs.end(); I != E; ++I)
4025                 dbgs() << ' ' << **I;
4026               dbgs() << '\n');
4027
4028         SolutionCost = NewCost;
4029         Solution = Workspace;
4030       }
4031       Workspace.pop_back();
4032     }
4033   }
4034 }
4035
4036 /// Solve - Choose one formula from each use. Return the results in the given
4037 /// Solution vector.
4038 void LSRInstance::Solve(SmallVectorImpl<const Formula *> &Solution) const {
4039   SmallVector<const Formula *, 8> Workspace;
4040   Cost SolutionCost;
4041   SolutionCost.Loose();
4042   Cost CurCost;
4043   SmallPtrSet<const SCEV *, 16> CurRegs;
4044   DenseSet<const SCEV *> VisitedRegs;
4045   Workspace.reserve(Uses.size());
4046
4047   // SolveRecurse does all the work.
4048   SolveRecurse(Solution, SolutionCost, Workspace, CurCost,
4049                CurRegs, VisitedRegs);
4050   if (Solution.empty()) {
4051     DEBUG(dbgs() << "\nNo Satisfactory Solution\n");
4052     return;
4053   }
4054
4055   // Ok, we've now made all our decisions.
4056   DEBUG(dbgs() << "\n"
4057                   "The chosen solution requires "; SolutionCost.print(dbgs());
4058         dbgs() << ":\n";
4059         for (size_t i = 0, e = Uses.size(); i != e; ++i) {
4060           dbgs() << "  ";
4061           Uses[i].print(dbgs());
4062           dbgs() << "\n"
4063                     "    ";
4064           Solution[i]->print(dbgs());
4065           dbgs() << '\n';
4066         });
4067
4068   assert(Solution.size() == Uses.size() && "Malformed solution!");
4069 }
4070
4071 /// HoistInsertPosition - Helper for AdjustInsertPositionForExpand. Climb up
4072 /// the dominator tree far as we can go while still being dominated by the
4073 /// input positions. This helps canonicalize the insert position, which
4074 /// encourages sharing.
4075 BasicBlock::iterator
4076 LSRInstance::HoistInsertPosition(BasicBlock::iterator IP,
4077                                  const SmallVectorImpl<Instruction *> &Inputs)
4078                                                                          const {
4079   for (;;) {
4080     const Loop *IPLoop = LI.getLoopFor(IP->getParent());
4081     unsigned IPLoopDepth = IPLoop ? IPLoop->getLoopDepth() : 0;
4082
4083     BasicBlock *IDom;
4084     for (DomTreeNode *Rung = DT.getNode(IP->getParent()); ; ) {
4085       if (!Rung) return IP;
4086       Rung = Rung->getIDom();
4087       if (!Rung) return IP;
4088       IDom = Rung->getBlock();
4089
4090       // Don't climb into a loop though.
4091       const Loop *IDomLoop = LI.getLoopFor(IDom);
4092       unsigned IDomDepth = IDomLoop ? IDomLoop->getLoopDepth() : 0;
4093       if (IDomDepth <= IPLoopDepth &&
4094           (IDomDepth != IPLoopDepth || IDomLoop == IPLoop))
4095         break;
4096     }
4097
4098     bool AllDominate = true;
4099     Instruction *BetterPos = 0;
4100     Instruction *Tentative = IDom->getTerminator();
4101     for (SmallVectorImpl<Instruction *>::const_iterator I = Inputs.begin(),
4102          E = Inputs.end(); I != E; ++I) {
4103       Instruction *Inst = *I;
4104       if (Inst == Tentative || !DT.dominates(Inst, Tentative)) {
4105         AllDominate = false;
4106         break;
4107       }
4108       // Attempt to find an insert position in the middle of the block,
4109       // instead of at the end, so that it can be used for other expansions.
4110       if (IDom == Inst->getParent() &&
4111           (!BetterPos || !DT.dominates(Inst, BetterPos)))
4112         BetterPos = llvm::next(BasicBlock::iterator(Inst));
4113     }
4114     if (!AllDominate)
4115       break;
4116     if (BetterPos)
4117       IP = BetterPos;
4118     else
4119       IP = Tentative;
4120   }
4121
4122   return IP;
4123 }
4124
4125 /// AdjustInsertPositionForExpand - Determine an input position which will be
4126 /// dominated by the operands and which will dominate the result.
4127 BasicBlock::iterator
4128 LSRInstance::AdjustInsertPositionForExpand(BasicBlock::iterator LowestIP,
4129                                            const LSRFixup &LF,
4130                                            const LSRUse &LU,
4131                                            SCEVExpander &Rewriter) const {
4132   // Collect some instructions which must be dominated by the
4133   // expanding replacement. These must be dominated by any operands that
4134   // will be required in the expansion.
4135   SmallVector<Instruction *, 4> Inputs;
4136   if (Instruction *I = dyn_cast<Instruction>(LF.OperandValToReplace))
4137     Inputs.push_back(I);
4138   if (LU.Kind == LSRUse::ICmpZero)
4139     if (Instruction *I =
4140           dyn_cast<Instruction>(cast<ICmpInst>(LF.UserInst)->getOperand(1)))
4141       Inputs.push_back(I);
4142   if (LF.PostIncLoops.count(L)) {
4143     if (LF.isUseFullyOutsideLoop(L))
4144       Inputs.push_back(L->getLoopLatch()->getTerminator());
4145     else
4146       Inputs.push_back(IVIncInsertPos);
4147   }
4148   // The expansion must also be dominated by the increment positions of any
4149   // loops it for which it is using post-inc mode.
4150   for (PostIncLoopSet::const_iterator I = LF.PostIncLoops.begin(),
4151        E = LF.PostIncLoops.end(); I != E; ++I) {
4152     const Loop *PIL = *I;
4153     if (PIL == L) continue;
4154
4155     // Be dominated by the loop exit.
4156     SmallVector<BasicBlock *, 4> ExitingBlocks;
4157     PIL->getExitingBlocks(ExitingBlocks);
4158     if (!ExitingBlocks.empty()) {
4159       BasicBlock *BB = ExitingBlocks[0];
4160       for (unsigned i = 1, e = ExitingBlocks.size(); i != e; ++i)
4161         BB = DT.findNearestCommonDominator(BB, ExitingBlocks[i]);
4162       Inputs.push_back(BB->getTerminator());
4163     }
4164   }
4165
4166   assert(!isa<PHINode>(LowestIP) && !isa<LandingPadInst>(LowestIP)
4167          && !isa<DbgInfoIntrinsic>(LowestIP) &&
4168          "Insertion point must be a normal instruction");
4169
4170   // Then, climb up the immediate dominator tree as far as we can go while
4171   // still being dominated by the input positions.
4172   BasicBlock::iterator IP = HoistInsertPosition(LowestIP, Inputs);
4173
4174   // Don't insert instructions before PHI nodes.
4175   while (isa<PHINode>(IP)) ++IP;
4176
4177   // Ignore landingpad instructions.
4178   while (isa<LandingPadInst>(IP)) ++IP;
4179
4180   // Ignore debug intrinsics.
4181   while (isa<DbgInfoIntrinsic>(IP)) ++IP;
4182
4183   // Set IP below instructions recently inserted by SCEVExpander. This keeps the
4184   // IP consistent across expansions and allows the previously inserted
4185   // instructions to be reused by subsequent expansion.
4186   while (Rewriter.isInsertedInstruction(IP) && IP != LowestIP) ++IP;
4187
4188   return IP;
4189 }
4190
4191 /// Expand - Emit instructions for the leading candidate expression for this
4192 /// LSRUse (this is called "expanding").
4193 Value *LSRInstance::Expand(const LSRFixup &LF,
4194                            const Formula &F,
4195                            BasicBlock::iterator IP,
4196                            SCEVExpander &Rewriter,
4197                            SmallVectorImpl<WeakVH> &DeadInsts) const {
4198   const LSRUse &LU = Uses[LF.LUIdx];
4199
4200   // Determine an input position which will be dominated by the operands and
4201   // which will dominate the result.
4202   IP = AdjustInsertPositionForExpand(IP, LF, LU, Rewriter);
4203
4204   // Inform the Rewriter if we have a post-increment use, so that it can
4205   // perform an advantageous expansion.
4206   Rewriter.setPostInc(LF.PostIncLoops);
4207
4208   // This is the type that the user actually needs.
4209   Type *OpTy = LF.OperandValToReplace->getType();
4210   // This will be the type that we'll initially expand to.
4211   Type *Ty = F.getType();
4212   if (!Ty)
4213     // No type known; just expand directly to the ultimate type.
4214     Ty = OpTy;
4215   else if (SE.getEffectiveSCEVType(Ty) == SE.getEffectiveSCEVType(OpTy))
4216     // Expand directly to the ultimate type if it's the right size.
4217     Ty = OpTy;
4218   // This is the type to do integer arithmetic in.
4219   Type *IntTy = SE.getEffectiveSCEVType(Ty);
4220
4221   // Build up a list of operands to add together to form the full base.
4222   SmallVector<const SCEV *, 8> Ops;
4223
4224   // Expand the BaseRegs portion.
4225   for (SmallVectorImpl<const SCEV *>::const_iterator I = F.BaseRegs.begin(),
4226        E = F.BaseRegs.end(); I != E; ++I) {
4227     const SCEV *Reg = *I;
4228     assert(!Reg->isZero() && "Zero allocated in a base register!");
4229
4230     // If we're expanding for a post-inc user, make the post-inc adjustment.
4231     PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops);
4232     Reg = TransformForPostIncUse(Denormalize, Reg,
4233                                  LF.UserInst, LF.OperandValToReplace,
4234                                  Loops, SE, DT);
4235
4236     Ops.push_back(SE.getUnknown(Rewriter.expandCodeFor(Reg, 0, IP)));
4237   }
4238
4239   // Flush the operand list to suppress SCEVExpander hoisting.
4240   if (!Ops.empty()) {
4241     Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP);
4242     Ops.clear();
4243     Ops.push_back(SE.getUnknown(FullV));
4244   }
4245
4246   // Expand the ScaledReg portion.
4247   Value *ICmpScaledV = 0;
4248   if (F.AM.Scale != 0) {
4249     const SCEV *ScaledS = F.ScaledReg;
4250
4251     // If we're expanding for a post-inc user, make the post-inc adjustment.
4252     PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(LF.PostIncLoops);
4253     ScaledS = TransformForPostIncUse(Denormalize, ScaledS,
4254                                      LF.UserInst, LF.OperandValToReplace,
4255                                      Loops, SE, DT);
4256
4257     if (LU.Kind == LSRUse::ICmpZero) {
4258       // An interesting way of "folding" with an icmp is to use a negated
4259       // scale, which we'll implement by inserting it into the other operand
4260       // of the icmp.
4261       assert(F.AM.Scale == -1 &&
4262              "The only scale supported by ICmpZero uses is -1!");
4263       ICmpScaledV = Rewriter.expandCodeFor(ScaledS, 0, IP);
4264     } else {
4265       // Otherwise just expand the scaled register and an explicit scale,
4266       // which is expected to be matched as part of the address.
4267       ScaledS = SE.getUnknown(Rewriter.expandCodeFor(ScaledS, 0, IP));
4268       ScaledS = SE.getMulExpr(ScaledS,
4269                               SE.getConstant(ScaledS->getType(), F.AM.Scale));
4270       Ops.push_back(ScaledS);
4271
4272       // Flush the operand list to suppress SCEVExpander hoisting.
4273       Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP);
4274       Ops.clear();
4275       Ops.push_back(SE.getUnknown(FullV));
4276     }
4277   }
4278
4279   // Expand the GV portion.
4280   if (F.AM.BaseGV) {
4281     Ops.push_back(SE.getUnknown(F.AM.BaseGV));
4282
4283     // Flush the operand list to suppress SCEVExpander hoisting.
4284     Value *FullV = Rewriter.expandCodeFor(SE.getAddExpr(Ops), Ty, IP);
4285     Ops.clear();
4286     Ops.push_back(SE.getUnknown(FullV));
4287   }
4288
4289   // Expand the immediate portion.
4290   int64_t Offset = (uint64_t)F.AM.BaseOffs + LF.Offset;
4291   if (Offset != 0) {
4292     if (LU.Kind == LSRUse::ICmpZero) {
4293       // The other interesting way of "folding" with an ICmpZero is to use a
4294       // negated immediate.
4295       if (!ICmpScaledV)
4296         ICmpScaledV = ConstantInt::get(IntTy, -(uint64_t)Offset);
4297       else {
4298         Ops.push_back(SE.getUnknown(ICmpScaledV));
4299         ICmpScaledV = ConstantInt::get(IntTy, Offset);
4300       }
4301     } else {
4302       // Just add the immediate values. These again are expected to be matched
4303       // as part of the address.
4304       Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy, Offset)));
4305     }
4306   }
4307
4308   // Expand the unfolded offset portion.
4309   int64_t UnfoldedOffset = F.UnfoldedOffset;
4310   if (UnfoldedOffset != 0) {
4311     // Just add the immediate values.
4312     Ops.push_back(SE.getUnknown(ConstantInt::getSigned(IntTy,
4313                                                        UnfoldedOffset)));
4314   }
4315
4316   // Emit instructions summing all the operands.
4317   const SCEV *FullS = Ops.empty() ?
4318                       SE.getConstant(IntTy, 0) :
4319                       SE.getAddExpr(Ops);
4320   Value *FullV = Rewriter.expandCodeFor(FullS, Ty, IP);
4321
4322   // We're done expanding now, so reset the rewriter.
4323   Rewriter.clearPostInc();
4324
4325   // An ICmpZero Formula represents an ICmp which we're handling as a
4326   // comparison against zero. Now that we've expanded an expression for that
4327   // form, update the ICmp's other operand.
4328   if (LU.Kind == LSRUse::ICmpZero) {
4329     ICmpInst *CI = cast<ICmpInst>(LF.UserInst);
4330     DeadInsts.push_back(CI->getOperand(1));
4331     assert(!F.AM.BaseGV && "ICmp does not support folding a global value and "
4332                            "a scale at the same time!");
4333     if (F.AM.Scale == -1) {
4334       if (ICmpScaledV->getType() != OpTy) {
4335         Instruction *Cast =
4336           CastInst::Create(CastInst::getCastOpcode(ICmpScaledV, false,
4337                                                    OpTy, false),
4338                            ICmpScaledV, OpTy, "tmp", CI);
4339         ICmpScaledV = Cast;
4340       }
4341       CI->setOperand(1, ICmpScaledV);
4342     } else {
4343       assert(F.AM.Scale == 0 &&
4344              "ICmp does not support folding a global value and "
4345              "a scale at the same time!");
4346       Constant *C = ConstantInt::getSigned(SE.getEffectiveSCEVType(OpTy),
4347                                            -(uint64_t)Offset);
4348       if (C->getType() != OpTy)
4349         C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
4350                                                           OpTy, false),
4351                                   C, OpTy);
4352
4353       CI->setOperand(1, C);
4354     }
4355   }
4356
4357   return FullV;
4358 }
4359
4360 /// RewriteForPHI - Helper for Rewrite. PHI nodes are special because the use
4361 /// of their operands effectively happens in their predecessor blocks, so the
4362 /// expression may need to be expanded in multiple places.
4363 void LSRInstance::RewriteForPHI(PHINode *PN,
4364                                 const LSRFixup &LF,
4365                                 const Formula &F,
4366                                 SCEVExpander &Rewriter,
4367                                 SmallVectorImpl<WeakVH> &DeadInsts,
4368                                 Pass *P) const {
4369   DenseMap<BasicBlock *, Value *> Inserted;
4370   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
4371     if (PN->getIncomingValue(i) == LF.OperandValToReplace) {
4372       BasicBlock *BB = PN->getIncomingBlock(i);
4373
4374       // If this is a critical edge, split the edge so that we do not insert
4375       // the code on all predecessor/successor paths.  We do this unless this
4376       // is the canonical backedge for this loop, which complicates post-inc
4377       // users.
4378       if (e != 1 && BB->getTerminator()->getNumSuccessors() > 1 &&
4379           !isa<IndirectBrInst>(BB->getTerminator())) {
4380         BasicBlock *Parent = PN->getParent();
4381         Loop *PNLoop = LI.getLoopFor(Parent);
4382         if (!PNLoop || Parent != PNLoop->getHeader()) {
4383           // Split the critical edge.
4384           BasicBlock *NewBB = 0;
4385           if (!Parent->isLandingPad()) {
4386             NewBB = SplitCriticalEdge(BB, Parent, P,
4387                                       /*MergeIdenticalEdges=*/true,
4388                                       /*DontDeleteUselessPhis=*/true);
4389           } else {
4390             SmallVector<BasicBlock*, 2> NewBBs;
4391             SplitLandingPadPredecessors(Parent, BB, "", "", P, NewBBs);
4392             NewBB = NewBBs[0];
4393           }
4394
4395           // If PN is outside of the loop and BB is in the loop, we want to
4396           // move the block to be immediately before the PHI block, not
4397           // immediately after BB.
4398           if (L->contains(BB) && !L->contains(PN))
4399             NewBB->moveBefore(PN->getParent());
4400
4401           // Splitting the edge can reduce the number of PHI entries we have.
4402           e = PN->getNumIncomingValues();
4403           BB = NewBB;
4404           i = PN->getBasicBlockIndex(BB);
4405         }
4406       }
4407
4408       std::pair<DenseMap<BasicBlock *, Value *>::iterator, bool> Pair =
4409         Inserted.insert(std::make_pair(BB, static_cast<Value *>(0)));
4410       if (!Pair.second)
4411         PN->setIncomingValue(i, Pair.first->second);
4412       else {
4413         Value *FullV = Expand(LF, F, BB->getTerminator(), Rewriter, DeadInsts);
4414
4415         // If this is reuse-by-noop-cast, insert the noop cast.
4416         Type *OpTy = LF.OperandValToReplace->getType();
4417         if (FullV->getType() != OpTy)
4418           FullV =
4419             CastInst::Create(CastInst::getCastOpcode(FullV, false,
4420                                                      OpTy, false),
4421                              FullV, LF.OperandValToReplace->getType(),
4422                              "tmp", BB->getTerminator());
4423
4424         PN->setIncomingValue(i, FullV);
4425         Pair.first->second = FullV;
4426       }
4427     }
4428 }
4429
4430 /// Rewrite - Emit instructions for the leading candidate expression for this
4431 /// LSRUse (this is called "expanding"), and update the UserInst to reference
4432 /// the newly expanded value.
4433 void LSRInstance::Rewrite(const LSRFixup &LF,
4434                           const Formula &F,
4435                           SCEVExpander &Rewriter,
4436                           SmallVectorImpl<WeakVH> &DeadInsts,
4437                           Pass *P) const {
4438   // First, find an insertion point that dominates UserInst. For PHI nodes,
4439   // find the nearest block which dominates all the relevant uses.
4440   if (PHINode *PN = dyn_cast<PHINode>(LF.UserInst)) {
4441     RewriteForPHI(PN, LF, F, Rewriter, DeadInsts, P);
4442   } else {
4443     Value *FullV = Expand(LF, F, LF.UserInst, Rewriter, DeadInsts);
4444
4445     // If this is reuse-by-noop-cast, insert the noop cast.
4446     Type *OpTy = LF.OperandValToReplace->getType();
4447     if (FullV->getType() != OpTy) {
4448       Instruction *Cast =
4449         CastInst::Create(CastInst::getCastOpcode(FullV, false, OpTy, false),
4450                          FullV, OpTy, "tmp", LF.UserInst);
4451       FullV = Cast;
4452     }
4453
4454     // Update the user. ICmpZero is handled specially here (for now) because
4455     // Expand may have updated one of the operands of the icmp already, and
4456     // its new value may happen to be equal to LF.OperandValToReplace, in
4457     // which case doing replaceUsesOfWith leads to replacing both operands
4458     // with the same value. TODO: Reorganize this.
4459     if (Uses[LF.LUIdx].Kind == LSRUse::ICmpZero)
4460       LF.UserInst->setOperand(0, FullV);
4461     else
4462       LF.UserInst->replaceUsesOfWith(LF.OperandValToReplace, FullV);
4463   }
4464
4465   DeadInsts.push_back(LF.OperandValToReplace);
4466 }
4467
4468 /// ImplementSolution - Rewrite all the fixup locations with new values,
4469 /// following the chosen solution.
4470 void
4471 LSRInstance::ImplementSolution(const SmallVectorImpl<const Formula *> &Solution,
4472                                Pass *P) {
4473   // Keep track of instructions we may have made dead, so that
4474   // we can remove them after we are done working.
4475   SmallVector<WeakVH, 16> DeadInsts;
4476
4477   SCEVExpander Rewriter(SE, "lsr");
4478 #ifndef NDEBUG
4479   Rewriter.setDebugType(DEBUG_TYPE);
4480 #endif
4481   Rewriter.disableCanonicalMode();
4482   Rewriter.enableLSRMode();
4483   Rewriter.setIVIncInsertPos(L, IVIncInsertPos);
4484
4485   // Mark phi nodes that terminate chains so the expander tries to reuse them.
4486   for (SmallVectorImpl<IVChain>::const_iterator ChainI = IVChainVec.begin(),
4487          ChainE = IVChainVec.end(); ChainI != ChainE; ++ChainI) {
4488     if (PHINode *PN = dyn_cast<PHINode>(ChainI->back().UserInst))
4489       Rewriter.setChainedPhi(PN);
4490   }
4491
4492   // Expand the new value definitions and update the users.
4493   for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(),
4494        E = Fixups.end(); I != E; ++I) {
4495     const LSRFixup &Fixup = *I;
4496
4497     Rewrite(Fixup, *Solution[Fixup.LUIdx], Rewriter, DeadInsts, P);
4498
4499     Changed = true;
4500   }
4501
4502   for (SmallVectorImpl<IVChain>::const_iterator ChainI = IVChainVec.begin(),
4503          ChainE = IVChainVec.end(); ChainI != ChainE; ++ChainI) {
4504     GenerateIVChain(*ChainI, Rewriter, DeadInsts);
4505     Changed = true;
4506   }
4507   // Clean up after ourselves. This must be done before deleting any
4508   // instructions.
4509   Rewriter.clear();
4510
4511   Changed |= DeleteTriviallyDeadInstructions(DeadInsts);
4512 }
4513
4514 LSRInstance::LSRInstance(const TargetLowering *tli, Loop *l, Pass *P)
4515   : IU(P->getAnalysis<IVUsers>()),
4516     SE(P->getAnalysis<ScalarEvolution>()),
4517     DT(P->getAnalysis<DominatorTree>()),
4518     LI(P->getAnalysis<LoopInfo>()),
4519     TLI(tli), L(l), Changed(false), IVIncInsertPos(0) {
4520
4521   // If LoopSimplify form is not available, stay out of trouble.
4522   if (!L->isLoopSimplifyForm())
4523     return;
4524
4525   // If there's no interesting work to be done, bail early.
4526   if (IU.empty()) return;
4527
4528   // If there's too much analysis to be done, bail early. We won't be able to
4529   // model the problem anyway.
4530   unsigned NumUsers = 0;
4531   for (IVUsers::const_iterator UI = IU.begin(), E = IU.end(); UI != E; ++UI) {
4532     if (++NumUsers > MaxIVUsers) {
4533       DEBUG(dbgs() << "LSR skipping loop, too many IV Users in " << *L
4534             << "\n");
4535       return;
4536     }
4537   }
4538
4539 #ifndef NDEBUG
4540   // All dominating loops must have preheaders, or SCEVExpander may not be able
4541   // to materialize an AddRecExpr whose Start is an outer AddRecExpr.
4542   //
4543   // IVUsers analysis should only create users that are dominated by simple loop
4544   // headers. Since this loop should dominate all of its users, its user list
4545   // should be empty if this loop itself is not within a simple loop nest.
4546   for (DomTreeNode *Rung = DT.getNode(L->getLoopPreheader());
4547        Rung; Rung = Rung->getIDom()) {
4548     BasicBlock *BB = Rung->getBlock();
4549     const Loop *DomLoop = LI.getLoopFor(BB);
4550     if (DomLoop && DomLoop->getHeader() == BB) {
4551       assert(DomLoop->getLoopPreheader() && "LSR needs a simplified loop nest");
4552     }
4553   }
4554 #endif // DEBUG
4555
4556   DEBUG(dbgs() << "\nLSR on loop ";
4557         WriteAsOperand(dbgs(), L->getHeader(), /*PrintType=*/false);
4558         dbgs() << ":\n");
4559
4560   // First, perform some low-level loop optimizations.
4561   OptimizeShadowIV();
4562   OptimizeLoopTermCond();
4563
4564   // If loop preparation eliminates all interesting IV users, bail.
4565   if (IU.empty()) return;
4566
4567   // Skip nested loops until we can model them better with formulae.
4568   if (!L->empty()) {
4569     DEBUG(dbgs() << "LSR skipping outer loop " << *L << "\n");
4570     return;
4571   }
4572
4573   // Start collecting data and preparing for the solver.
4574   CollectChains();
4575   CollectInterestingTypesAndFactors();
4576   CollectFixupsAndInitialFormulae();
4577   CollectLoopInvariantFixupsAndFormulae();
4578
4579   assert(!Uses.empty() && "IVUsers reported at least one use");
4580   DEBUG(dbgs() << "LSR found " << Uses.size() << " uses:\n";
4581         print_uses(dbgs()));
4582
4583   // Now use the reuse data to generate a bunch of interesting ways
4584   // to formulate the values needed for the uses.
4585   GenerateAllReuseFormulae();
4586
4587   FilterOutUndesirableDedicatedRegisters();
4588   NarrowSearchSpaceUsingHeuristics();
4589
4590   SmallVector<const Formula *, 8> Solution;
4591   Solve(Solution);
4592
4593   // Release memory that is no longer needed.
4594   Factors.clear();
4595   Types.clear();
4596   RegUses.clear();
4597
4598   if (Solution.empty())
4599     return;
4600
4601 #ifndef NDEBUG
4602   // Formulae should be legal.
4603   for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(),
4604        E = Uses.end(); I != E; ++I) {
4605      const LSRUse &LU = *I;
4606      for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(),
4607           JE = LU.Formulae.end(); J != JE; ++J)
4608         assert(isLegalUse(J->AM, LU.MinOffset, LU.MaxOffset,
4609                           LU.Kind, LU.AccessTy, TLI) &&
4610                "Illegal formula generated!");
4611   };
4612 #endif
4613
4614   // Now that we've decided what we want, make it so.
4615   ImplementSolution(Solution, P);
4616 }
4617
4618 void LSRInstance::print_factors_and_types(raw_ostream &OS) const {
4619   if (Factors.empty() && Types.empty()) return;
4620
4621   OS << "LSR has identified the following interesting factors and types: ";
4622   bool First = true;
4623
4624   for (SmallSetVector<int64_t, 8>::const_iterator
4625        I = Factors.begin(), E = Factors.end(); I != E; ++I) {
4626     if (!First) OS << ", ";
4627     First = false;
4628     OS << '*' << *I;
4629   }
4630
4631   for (SmallSetVector<Type *, 4>::const_iterator
4632        I = Types.begin(), E = Types.end(); I != E; ++I) {
4633     if (!First) OS << ", ";
4634     First = false;
4635     OS << '(' << **I << ')';
4636   }
4637   OS << '\n';
4638 }
4639
4640 void LSRInstance::print_fixups(raw_ostream &OS) const {
4641   OS << "LSR is examining the following fixup sites:\n";
4642   for (SmallVectorImpl<LSRFixup>::const_iterator I = Fixups.begin(),
4643        E = Fixups.end(); I != E; ++I) {
4644     dbgs() << "  ";
4645     I->print(OS);
4646     OS << '\n';
4647   }
4648 }
4649
4650 void LSRInstance::print_uses(raw_ostream &OS) const {
4651   OS << "LSR is examining the following uses:\n";
4652   for (SmallVectorImpl<LSRUse>::const_iterator I = Uses.begin(),
4653        E = Uses.end(); I != E; ++I) {
4654     const LSRUse &LU = *I;
4655     dbgs() << "  ";
4656     LU.print(OS);
4657     OS << '\n';
4658     for (SmallVectorImpl<Formula>::const_iterator J = LU.Formulae.begin(),
4659          JE = LU.Formulae.end(); J != JE; ++J) {
4660       OS << "    ";
4661       J->print(OS);
4662       OS << '\n';
4663     }
4664   }
4665 }
4666
4667 void LSRInstance::print(raw_ostream &OS) const {
4668   print_factors_and_types(OS);
4669   print_fixups(OS);
4670   print_uses(OS);
4671 }
4672
4673 void LSRInstance::dump() const {
4674   print(errs()); errs() << '\n';
4675 }
4676
4677 namespace {
4678
4679 class LoopStrengthReduce : public LoopPass {
4680   /// TLI - Keep a pointer of a TargetLowering to consult for determining
4681   /// transformation profitability.
4682   const TargetLowering *const TLI;
4683
4684 public:
4685   static char ID; // Pass ID, replacement for typeid
4686   explicit LoopStrengthReduce(const TargetLowering *tli = 0);
4687
4688 private:
4689   bool runOnLoop(Loop *L, LPPassManager &LPM);
4690   void getAnalysisUsage(AnalysisUsage &AU) const;
4691 };
4692
4693 }
4694
4695 char LoopStrengthReduce::ID = 0;
4696 INITIALIZE_PASS_BEGIN(LoopStrengthReduce, "loop-reduce",
4697                 "Loop Strength Reduction", false, false)
4698 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
4699 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
4700 INITIALIZE_PASS_DEPENDENCY(IVUsers)
4701 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
4702 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
4703 INITIALIZE_PASS_END(LoopStrengthReduce, "loop-reduce",
4704                 "Loop Strength Reduction", false, false)
4705
4706
4707 Pass *llvm::createLoopStrengthReducePass(const TargetLowering *TLI) {
4708   return new LoopStrengthReduce(TLI);
4709 }
4710
4711 LoopStrengthReduce::LoopStrengthReduce(const TargetLowering *tli)
4712   : LoopPass(ID), TLI(tli) {
4713     initializeLoopStrengthReducePass(*PassRegistry::getPassRegistry());
4714   }
4715
4716 void LoopStrengthReduce::getAnalysisUsage(AnalysisUsage &AU) const {
4717   // We split critical edges, so we change the CFG.  However, we do update
4718   // many analyses if they are around.
4719   AU.addPreservedID(LoopSimplifyID);
4720
4721   AU.addRequired<LoopInfo>();
4722   AU.addPreserved<LoopInfo>();
4723   AU.addRequiredID(LoopSimplifyID);
4724   AU.addRequired<DominatorTree>();
4725   AU.addPreserved<DominatorTree>();
4726   AU.addRequired<ScalarEvolution>();
4727   AU.addPreserved<ScalarEvolution>();
4728   // Requiring LoopSimplify a second time here prevents IVUsers from running
4729   // twice, since LoopSimplify was invalidated by running ScalarEvolution.
4730   AU.addRequiredID(LoopSimplifyID);
4731   AU.addRequired<IVUsers>();
4732   AU.addPreserved<IVUsers>();
4733 }
4734
4735 bool LoopStrengthReduce::runOnLoop(Loop *L, LPPassManager & /*LPM*/) {
4736   bool Changed = false;
4737
4738   // Run the main LSR transformation.
4739   Changed |= LSRInstance(TLI, L, this).getChanged();
4740
4741   // Remove any extra phis created by processing inner loops.
4742   Changed |= DeleteDeadPHIs(L->getHeader());
4743   if (EnablePhiElim) {
4744     SmallVector<WeakVH, 16> DeadInsts;
4745     SCEVExpander Rewriter(getAnalysis<ScalarEvolution>(), "lsr");
4746 #ifndef NDEBUG
4747     Rewriter.setDebugType(DEBUG_TYPE);
4748 #endif
4749     unsigned numFolded = Rewriter.
4750       replaceCongruentIVs(L, &getAnalysis<DominatorTree>(), DeadInsts, TLI);
4751     if (numFolded) {
4752       Changed = true;
4753       DeleteTriviallyDeadInstructions(DeadInsts);
4754       DeleteDeadPHIs(L->getHeader());
4755     }
4756   }
4757   return Changed;
4758 }