LFTR improvement to avoid truncation.
[oota-llvm.git] / lib / Transforms / Scalar / IndVarSimplify.cpp
1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
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 simpler forms suitable for subsequent
12 // analysis and transformation.
13 //
14 // If the trip count of a loop is computable, this pass also makes the following
15 // changes:
16 //   1. The exit condition for the loop is canonicalized to compare the
17 //      induction value against the exit value.  This turns loops like:
18 //        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
19 //   2. Any use outside of the loop of an expression derived from the indvar
20 //      is changed to compute the derived value outside of the loop, eliminating
21 //      the dependence on the exit value of the induction variable.  If the only
22 //      purpose of the loop is to compute the exit value of some derived
23 //      expression, this transformation will make the loop dead.
24 //
25 //===----------------------------------------------------------------------===//
26
27 #define DEBUG_TYPE "indvars"
28 #include "llvm/Transforms/Scalar.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/Dominators.h"
33 #include "llvm/Analysis/LoopInfo.h"
34 #include "llvm/Analysis/LoopPass.h"
35 #include "llvm/Analysis/ScalarEvolutionExpander.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/Constants.h"
38 #include "llvm/IR/DataLayout.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/IntrinsicInst.h"
41 #include "llvm/IR/LLVMContext.h"
42 #include "llvm/IR/Type.h"
43 #include "llvm/Support/CFG.h"
44 #include "llvm/Support/CommandLine.h"
45 #include "llvm/Support/Debug.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include "llvm/Target/TargetLibraryInfo.h"
48 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
49 #include "llvm/Transforms/Utils/Local.h"
50 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
51 using namespace llvm;
52
53 STATISTIC(NumWidened     , "Number of indvars widened");
54 STATISTIC(NumReplaced    , "Number of exit values replaced");
55 STATISTIC(NumLFTR        , "Number of loop exit tests replaced");
56 STATISTIC(NumElimExt     , "Number of IV sign/zero extends eliminated");
57 STATISTIC(NumElimIV      , "Number of congruent IVs eliminated");
58
59 // Trip count verification can be enabled by default under NDEBUG if we
60 // implement a strong expression equivalence checker in SCEV. Until then, we
61 // use the verify-indvars flag, which may assert in some cases.
62 static cl::opt<bool> VerifyIndvars(
63   "verify-indvars", cl::Hidden,
64   cl::desc("Verify the ScalarEvolution result after running indvars"));
65
66 namespace {
67   class IndVarSimplify : public LoopPass {
68     LoopInfo        *LI;
69     ScalarEvolution *SE;
70     DominatorTree   *DT;
71     DataLayout      *TD;
72     TargetLibraryInfo *TLI;
73
74     SmallVector<WeakVH, 16> DeadInsts;
75     bool Changed;
76   public:
77
78     static char ID; // Pass identification, replacement for typeid
79     IndVarSimplify() : LoopPass(ID), LI(0), SE(0), DT(0), TD(0),
80                        Changed(false) {
81       initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry());
82     }
83
84     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
85
86     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
87       AU.addRequired<DominatorTree>();
88       AU.addRequired<LoopInfo>();
89       AU.addRequired<ScalarEvolution>();
90       AU.addRequiredID(LoopSimplifyID);
91       AU.addRequiredID(LCSSAID);
92       AU.addPreserved<ScalarEvolution>();
93       AU.addPreservedID(LoopSimplifyID);
94       AU.addPreservedID(LCSSAID);
95       AU.setPreservesCFG();
96     }
97
98   private:
99     virtual void releaseMemory() {
100       DeadInsts.clear();
101     }
102
103     bool isValidRewrite(Value *FromVal, Value *ToVal);
104
105     void HandleFloatingPointIV(Loop *L, PHINode *PH);
106     void RewriteNonIntegerIVs(Loop *L);
107
108     void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM);
109
110     void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
111
112     Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
113                                      PHINode *IndVar, SCEVExpander &Rewriter);
114
115     void SinkUnusedInvariants(Loop *L);
116   };
117 }
118
119 char IndVarSimplify::ID = 0;
120 INITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars",
121                 "Induction Variable Simplification", false, false)
122 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
123 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
124 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
125 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
126 INITIALIZE_PASS_DEPENDENCY(LCSSA)
127 INITIALIZE_PASS_END(IndVarSimplify, "indvars",
128                 "Induction Variable Simplification", false, false)
129
130 Pass *llvm::createIndVarSimplifyPass() {
131   return new IndVarSimplify();
132 }
133
134 /// isValidRewrite - Return true if the SCEV expansion generated by the
135 /// rewriter can replace the original value. SCEV guarantees that it
136 /// produces the same value, but the way it is produced may be illegal IR.
137 /// Ideally, this function will only be called for verification.
138 bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
139   // If an SCEV expression subsumed multiple pointers, its expansion could
140   // reassociate the GEP changing the base pointer. This is illegal because the
141   // final address produced by a GEP chain must be inbounds relative to its
142   // underlying object. Otherwise basic alias analysis, among other things,
143   // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
144   // producing an expression involving multiple pointers. Until then, we must
145   // bail out here.
146   //
147   // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
148   // because it understands lcssa phis while SCEV does not.
149   Value *FromPtr = FromVal;
150   Value *ToPtr = ToVal;
151   if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) {
152     FromPtr = GEP->getPointerOperand();
153   }
154   if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) {
155     ToPtr = GEP->getPointerOperand();
156   }
157   if (FromPtr != FromVal || ToPtr != ToVal) {
158     // Quickly check the common case
159     if (FromPtr == ToPtr)
160       return true;
161
162     // SCEV may have rewritten an expression that produces the GEP's pointer
163     // operand. That's ok as long as the pointer operand has the same base
164     // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
165     // base of a recurrence. This handles the case in which SCEV expansion
166     // converts a pointer type recurrence into a nonrecurrent pointer base
167     // indexed by an integer recurrence.
168
169     // If the GEP base pointer is a vector of pointers, abort.
170     if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
171       return false;
172
173     const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
174     const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
175     if (FromBase == ToBase)
176       return true;
177
178     DEBUG(dbgs() << "INDVARS: GEP rewrite bail out "
179           << *FromBase << " != " << *ToBase << "\n");
180
181     return false;
182   }
183   return true;
184 }
185
186 /// Determine the insertion point for this user. By default, insert immediately
187 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
188 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
189 /// common dominator for the incoming blocks.
190 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
191                                           DominatorTree *DT) {
192   PHINode *PHI = dyn_cast<PHINode>(User);
193   if (!PHI)
194     return User;
195
196   Instruction *InsertPt = 0;
197   for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
198     if (PHI->getIncomingValue(i) != Def)
199       continue;
200
201     BasicBlock *InsertBB = PHI->getIncomingBlock(i);
202     if (!InsertPt) {
203       InsertPt = InsertBB->getTerminator();
204       continue;
205     }
206     InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
207     InsertPt = InsertBB->getTerminator();
208   }
209   assert(InsertPt && "Missing phi operand");
210   assert((!isa<Instruction>(Def) ||
211           DT->dominates(cast<Instruction>(Def), InsertPt)) &&
212          "def does not dominate all uses");
213   return InsertPt;
214 }
215
216 //===----------------------------------------------------------------------===//
217 // RewriteNonIntegerIVs and helpers. Prefer integer IVs.
218 //===----------------------------------------------------------------------===//
219
220 /// ConvertToSInt - Convert APF to an integer, if possible.
221 static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
222   bool isExact = false;
223   // See if we can convert this to an int64_t
224   uint64_t UIntVal;
225   if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero,
226                            &isExact) != APFloat::opOK || !isExact)
227     return false;
228   IntVal = UIntVal;
229   return true;
230 }
231
232 /// HandleFloatingPointIV - If the loop has floating induction variable
233 /// then insert corresponding integer induction variable if possible.
234 /// For example,
235 /// for(double i = 0; i < 10000; ++i)
236 ///   bar(i)
237 /// is converted into
238 /// for(int i = 0; i < 10000; ++i)
239 ///   bar((double)i);
240 ///
241 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) {
242   unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
243   unsigned BackEdge     = IncomingEdge^1;
244
245   // Check incoming value.
246   ConstantFP *InitValueVal =
247     dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge));
248
249   int64_t InitValue;
250   if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
251     return;
252
253   // Check IV increment. Reject this PN if increment operation is not
254   // an add or increment value can not be represented by an integer.
255   BinaryOperator *Incr =
256     dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge));
257   if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return;
258
259   // If this is not an add of the PHI with a constantfp, or if the constant fp
260   // is not an integer, bail out.
261   ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
262   int64_t IncValue;
263   if (IncValueVal == 0 || Incr->getOperand(0) != PN ||
264       !ConvertToSInt(IncValueVal->getValueAPF(), IncValue))
265     return;
266
267   // Check Incr uses. One user is PN and the other user is an exit condition
268   // used by the conditional terminator.
269   Value::use_iterator IncrUse = Incr->use_begin();
270   Instruction *U1 = cast<Instruction>(*IncrUse++);
271   if (IncrUse == Incr->use_end()) return;
272   Instruction *U2 = cast<Instruction>(*IncrUse++);
273   if (IncrUse != Incr->use_end()) return;
274
275   // Find exit condition, which is an fcmp.  If it doesn't exist, or if it isn't
276   // only used by a branch, we can't transform it.
277   FCmpInst *Compare = dyn_cast<FCmpInst>(U1);
278   if (!Compare)
279     Compare = dyn_cast<FCmpInst>(U2);
280   if (Compare == 0 || !Compare->hasOneUse() ||
281       !isa<BranchInst>(Compare->use_back()))
282     return;
283
284   BranchInst *TheBr = cast<BranchInst>(Compare->use_back());
285
286   // We need to verify that the branch actually controls the iteration count
287   // of the loop.  If not, the new IV can overflow and no one will notice.
288   // The branch block must be in the loop and one of the successors must be out
289   // of the loop.
290   assert(TheBr->isConditional() && "Can't use fcmp if not conditional");
291   if (!L->contains(TheBr->getParent()) ||
292       (L->contains(TheBr->getSuccessor(0)) &&
293        L->contains(TheBr->getSuccessor(1))))
294     return;
295
296
297   // If it isn't a comparison with an integer-as-fp (the exit value), we can't
298   // transform it.
299   ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));
300   int64_t ExitValue;
301   if (ExitValueVal == 0 ||
302       !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue))
303     return;
304
305   // Find new predicate for integer comparison.
306   CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
307   switch (Compare->getPredicate()) {
308   default: return;  // Unknown comparison.
309   case CmpInst::FCMP_OEQ:
310   case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break;
311   case CmpInst::FCMP_ONE:
312   case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break;
313   case CmpInst::FCMP_OGT:
314   case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break;
315   case CmpInst::FCMP_OGE:
316   case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break;
317   case CmpInst::FCMP_OLT:
318   case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break;
319   case CmpInst::FCMP_OLE:
320   case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break;
321   }
322
323   // We convert the floating point induction variable to a signed i32 value if
324   // we can.  This is only safe if the comparison will not overflow in a way
325   // that won't be trapped by the integer equivalent operations.  Check for this
326   // now.
327   // TODO: We could use i64 if it is native and the range requires it.
328
329   // The start/stride/exit values must all fit in signed i32.
330   if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
331     return;
332
333   // If not actually striding (add x, 0.0), avoid touching the code.
334   if (IncValue == 0)
335     return;
336
337   // Positive and negative strides have different safety conditions.
338   if (IncValue > 0) {
339     // If we have a positive stride, we require the init to be less than the
340     // exit value.
341     if (InitValue >= ExitValue)
342       return;
343
344     uint32_t Range = uint32_t(ExitValue-InitValue);
345     // Check for infinite loop, either:
346     // while (i <= Exit) or until (i > Exit)
347     if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) {
348       if (++Range == 0) return;  // Range overflows.
349     }
350
351     unsigned Leftover = Range % uint32_t(IncValue);
352
353     // If this is an equality comparison, we require that the strided value
354     // exactly land on the exit value, otherwise the IV condition will wrap
355     // around and do things the fp IV wouldn't.
356     if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
357         Leftover != 0)
358       return;
359
360     // If the stride would wrap around the i32 before exiting, we can't
361     // transform the IV.
362     if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
363       return;
364
365   } else {
366     // If we have a negative stride, we require the init to be greater than the
367     // exit value.
368     if (InitValue <= ExitValue)
369       return;
370
371     uint32_t Range = uint32_t(InitValue-ExitValue);
372     // Check for infinite loop, either:
373     // while (i >= Exit) or until (i < Exit)
374     if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) {
375       if (++Range == 0) return;  // Range overflows.
376     }
377
378     unsigned Leftover = Range % uint32_t(-IncValue);
379
380     // If this is an equality comparison, we require that the strided value
381     // exactly land on the exit value, otherwise the IV condition will wrap
382     // around and do things the fp IV wouldn't.
383     if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
384         Leftover != 0)
385       return;
386
387     // If the stride would wrap around the i32 before exiting, we can't
388     // transform the IV.
389     if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
390       return;
391   }
392
393   IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext());
394
395   // Insert new integer induction variable.
396   PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN);
397   NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue),
398                       PN->getIncomingBlock(IncomingEdge));
399
400   Value *NewAdd =
401     BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue),
402                               Incr->getName()+".int", Incr);
403   NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge));
404
405   ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd,
406                                       ConstantInt::get(Int32Ty, ExitValue),
407                                       Compare->getName());
408
409   // In the following deletions, PN may become dead and may be deleted.
410   // Use a WeakVH to observe whether this happens.
411   WeakVH WeakPH = PN;
412
413   // Delete the old floating point exit comparison.  The branch starts using the
414   // new comparison.
415   NewCompare->takeName(Compare);
416   Compare->replaceAllUsesWith(NewCompare);
417   RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI);
418
419   // Delete the old floating point increment.
420   Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
421   RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI);
422
423   // If the FP induction variable still has uses, this is because something else
424   // in the loop uses its value.  In order to canonicalize the induction
425   // variable, we chose to eliminate the IV and rewrite it in terms of an
426   // int->fp cast.
427   //
428   // We give preference to sitofp over uitofp because it is faster on most
429   // platforms.
430   if (WeakPH) {
431     Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",
432                                  PN->getParent()->getFirstInsertionPt());
433     PN->replaceAllUsesWith(Conv);
434     RecursivelyDeleteTriviallyDeadInstructions(PN, TLI);
435   }
436   Changed = true;
437 }
438
439 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
440   // First step.  Check to see if there are any floating-point recurrences.
441   // If there are, change them into integer recurrences, permitting analysis by
442   // the SCEV routines.
443   //
444   BasicBlock *Header = L->getHeader();
445
446   SmallVector<WeakVH, 8> PHIs;
447   for (BasicBlock::iterator I = Header->begin();
448        PHINode *PN = dyn_cast<PHINode>(I); ++I)
449     PHIs.push_back(PN);
450
451   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
452     if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i]))
453       HandleFloatingPointIV(L, PN);
454
455   // If the loop previously had floating-point IV, ScalarEvolution
456   // may not have been able to compute a trip count. Now that we've done some
457   // re-writing, the trip count may be computable.
458   if (Changed)
459     SE->forgetLoop(L);
460 }
461
462 //===----------------------------------------------------------------------===//
463 // RewriteLoopExitValues - Optimize IV users outside the loop.
464 // As a side effect, reduces the amount of IV processing within the loop.
465 //===----------------------------------------------------------------------===//
466
467 /// RewriteLoopExitValues - Check to see if this loop has a computable
468 /// loop-invariant execution count.  If so, this means that we can compute the
469 /// final value of any expressions that are recurrent in the loop, and
470 /// substitute the exit values from the loop into any instructions outside of
471 /// the loop that use the final values of the current expressions.
472 ///
473 /// This is mostly redundant with the regular IndVarSimplify activities that
474 /// happen later, except that it's more powerful in some cases, because it's
475 /// able to brute-force evaluate arbitrary instructions as long as they have
476 /// constant operands at the beginning of the loop.
477 void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
478   // Verify the input to the pass in already in LCSSA form.
479   assert(L->isLCSSAForm(*DT));
480
481   SmallVector<BasicBlock*, 8> ExitBlocks;
482   L->getUniqueExitBlocks(ExitBlocks);
483
484   // Find all values that are computed inside the loop, but used outside of it.
485   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
486   // the exit blocks of the loop to find them.
487   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
488     BasicBlock *ExitBB = ExitBlocks[i];
489
490     // If there are no PHI nodes in this exit block, then no values defined
491     // inside the loop are used on this path, skip it.
492     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
493     if (!PN) continue;
494
495     unsigned NumPreds = PN->getNumIncomingValues();
496
497     // Iterate over all of the PHI nodes.
498     BasicBlock::iterator BBI = ExitBB->begin();
499     while ((PN = dyn_cast<PHINode>(BBI++))) {
500       if (PN->use_empty())
501         continue; // dead use, don't replace it
502
503       // SCEV only supports integer expressions for now.
504       if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy())
505         continue;
506
507       // It's necessary to tell ScalarEvolution about this explicitly so that
508       // it can walk the def-use list and forget all SCEVs, as it may not be
509       // watching the PHI itself. Once the new exit value is in place, there
510       // may not be a def-use connection between the loop and every instruction
511       // which got a SCEVAddRecExpr for that loop.
512       SE->forgetValue(PN);
513
514       // Iterate over all of the values in all the PHI nodes.
515       for (unsigned i = 0; i != NumPreds; ++i) {
516         // If the value being merged in is not integer or is not defined
517         // in the loop, skip it.
518         Value *InVal = PN->getIncomingValue(i);
519         if (!isa<Instruction>(InVal))
520           continue;
521
522         // If this pred is for a subloop, not L itself, skip it.
523         if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
524           continue; // The Block is in a subloop, skip it.
525
526         // Check that InVal is defined in the loop.
527         Instruction *Inst = cast<Instruction>(InVal);
528         if (!L->contains(Inst))
529           continue;
530
531         // Okay, this instruction has a user outside of the current loop
532         // and varies predictably *inside* the loop.  Evaluate the value it
533         // contains when the loop exits, if possible.
534         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
535         if (!SE->isLoopInvariant(ExitValue, L) || !isSafeToExpand(ExitValue))
536           continue;
537
538         // Computing the value outside of the loop brings no benefit if :
539         //  - it is definitely used inside the loop in a way which can not be
540         //    optimized away.
541         //  - no use outside of the loop can take advantage of hoisting the
542         //    computation out of the loop
543         if (ExitValue->getSCEVType()>=scMulExpr) {
544           unsigned NumHardInternalUses = 0;
545           unsigned NumSoftExternalUses = 0;
546           unsigned NumUses = 0;
547           for (Value::use_iterator IB=Inst->use_begin(), IE=Inst->use_end();
548                IB!=IE && NumUses<=6 ; ++IB) {
549             Instruction *UseInstr = cast<Instruction>(*IB);
550             unsigned Opc = UseInstr->getOpcode();
551             NumUses++;
552             if (L->contains(UseInstr)) {
553               if (Opc == Instruction::Call || Opc == Instruction::Ret)
554                 NumHardInternalUses++;
555             } else {
556               if (Opc == Instruction::PHI) {
557                 // Do not count the Phi as a use. LCSSA may have inserted
558                 // plenty of trivial ones.
559                 NumUses--;
560                 for (Value::use_iterator PB=UseInstr->use_begin(),
561                                          PE=UseInstr->use_end();
562                      PB!=PE && NumUses<=6 ; ++PB, ++NumUses) {
563                   unsigned PhiOpc = cast<Instruction>(*PB)->getOpcode();
564                   if (PhiOpc != Instruction::Call && PhiOpc != Instruction::Ret)
565                     NumSoftExternalUses++;
566                 }
567                 continue;
568               }
569               if (Opc != Instruction::Call && Opc != Instruction::Ret)
570                 NumSoftExternalUses++;
571             }
572           }
573           if (NumUses <= 6 && NumHardInternalUses && !NumSoftExternalUses)
574             continue;
575         }
576
577         Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
578
579         DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n'
580                      << "  LoopVal = " << *Inst << "\n");
581
582         if (!isValidRewrite(Inst, ExitVal)) {
583           DeadInsts.push_back(ExitVal);
584           continue;
585         }
586         Changed = true;
587         ++NumReplaced;
588
589         PN->setIncomingValue(i, ExitVal);
590
591         // If this instruction is dead now, delete it. Don't do it now to avoid
592         // invalidating iterators.
593         if (isInstructionTriviallyDead(Inst, TLI))
594           DeadInsts.push_back(Inst);
595
596         if (NumPreds == 1) {
597           // Completely replace a single-pred PHI. This is safe, because the
598           // NewVal won't be variant in the loop, so we don't need an LCSSA phi
599           // node anymore.
600           PN->replaceAllUsesWith(ExitVal);
601           PN->eraseFromParent();
602         }
603       }
604       if (NumPreds != 1) {
605         // Clone the PHI and delete the original one. This lets IVUsers and
606         // any other maps purge the original user from their records.
607         PHINode *NewPN = cast<PHINode>(PN->clone());
608         NewPN->takeName(PN);
609         NewPN->insertBefore(PN);
610         PN->replaceAllUsesWith(NewPN);
611         PN->eraseFromParent();
612       }
613     }
614   }
615
616   // The insertion point instruction may have been deleted; clear it out
617   // so that the rewriter doesn't trip over it later.
618   Rewriter.clearInsertPoint();
619 }
620
621 //===----------------------------------------------------------------------===//
622 //  IV Widening - Extend the width of an IV to cover its widest uses.
623 //===----------------------------------------------------------------------===//
624
625 namespace {
626   // Collect information about induction variables that are used by sign/zero
627   // extend operations. This information is recorded by CollectExtend and
628   // provides the input to WidenIV.
629   struct WideIVInfo {
630     PHINode *NarrowIV;
631     Type *WidestNativeType; // Widest integer type created [sz]ext
632     bool IsSigned;          // Was an sext user seen before a zext?
633
634     WideIVInfo() : NarrowIV(0), WidestNativeType(0), IsSigned(false) {}
635   };
636
637   class WideIVVisitor : public IVVisitor {
638     ScalarEvolution *SE;
639     const DataLayout *TD;
640
641   public:
642     WideIVInfo WI;
643
644     WideIVVisitor(PHINode *NarrowIV, ScalarEvolution *SCEV,
645                   const DataLayout *TData) :
646       SE(SCEV), TD(TData) { WI.NarrowIV = NarrowIV; }
647
648     // Implement the interface used by simplifyUsersOfIV.
649     virtual void visitCast(CastInst *Cast);
650   };
651 }
652
653 /// visitCast - Update information about the induction variable that is
654 /// extended by this sign or zero extend operation. This is used to determine
655 /// the final width of the IV before actually widening it.
656 void WideIVVisitor::visitCast(CastInst *Cast) {
657   bool IsSigned = Cast->getOpcode() == Instruction::SExt;
658   if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)
659     return;
660
661   Type *Ty = Cast->getType();
662   uint64_t Width = SE->getTypeSizeInBits(Ty);
663   if (TD && !TD->isLegalInteger(Width))
664     return;
665
666   if (!WI.WidestNativeType) {
667     WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
668     WI.IsSigned = IsSigned;
669     return;
670   }
671
672   // We extend the IV to satisfy the sign of its first user, arbitrarily.
673   if (WI.IsSigned != IsSigned)
674     return;
675
676   if (Width > SE->getTypeSizeInBits(WI.WidestNativeType))
677     WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
678 }
679
680 namespace {
681
682 /// NarrowIVDefUse - Record a link in the Narrow IV def-use chain along with the
683 /// WideIV that computes the same value as the Narrow IV def.  This avoids
684 /// caching Use* pointers.
685 struct NarrowIVDefUse {
686   Instruction *NarrowDef;
687   Instruction *NarrowUse;
688   Instruction *WideDef;
689
690   NarrowIVDefUse(): NarrowDef(0), NarrowUse(0), WideDef(0) {}
691
692   NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD):
693     NarrowDef(ND), NarrowUse(NU), WideDef(WD) {}
694 };
695
696 /// WidenIV - The goal of this transform is to remove sign and zero extends
697 /// without creating any new induction variables. To do this, it creates a new
698 /// phi of the wider type and redirects all users, either removing extends or
699 /// inserting truncs whenever we stop propagating the type.
700 ///
701 class WidenIV {
702   // Parameters
703   PHINode *OrigPhi;
704   Type *WideType;
705   bool IsSigned;
706
707   // Context
708   LoopInfo        *LI;
709   Loop            *L;
710   ScalarEvolution *SE;
711   DominatorTree   *DT;
712
713   // Result
714   PHINode *WidePhi;
715   Instruction *WideInc;
716   const SCEV *WideIncExpr;
717   SmallVectorImpl<WeakVH> &DeadInsts;
718
719   SmallPtrSet<Instruction*,16> Widened;
720   SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
721
722 public:
723   WidenIV(const WideIVInfo &WI, LoopInfo *LInfo,
724           ScalarEvolution *SEv, DominatorTree *DTree,
725           SmallVectorImpl<WeakVH> &DI) :
726     OrigPhi(WI.NarrowIV),
727     WideType(WI.WidestNativeType),
728     IsSigned(WI.IsSigned),
729     LI(LInfo),
730     L(LI->getLoopFor(OrigPhi->getParent())),
731     SE(SEv),
732     DT(DTree),
733     WidePhi(0),
734     WideInc(0),
735     WideIncExpr(0),
736     DeadInsts(DI) {
737     assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
738   }
739
740   PHINode *CreateWideIV(SCEVExpander &Rewriter);
741
742 protected:
743   Value *getExtend(Value *NarrowOper, Type *WideType, bool IsSigned,
744                    Instruction *Use);
745
746   Instruction *CloneIVUser(NarrowIVDefUse DU);
747
748   const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse);
749
750   const SCEVAddRecExpr* GetExtendedOperandRecurrence(NarrowIVDefUse DU);
751
752   Instruction *WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);
753
754   void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
755 };
756 } // anonymous namespace
757
758 /// isLoopInvariant - Perform a quick domtree based check for loop invariance
759 /// assuming that V is used within the loop. LoopInfo::isLoopInvariant() seems
760 /// gratuitous for this purpose.
761 static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) {
762   Instruction *Inst = dyn_cast<Instruction>(V);
763   if (!Inst)
764     return true;
765
766   return DT->properlyDominates(Inst->getParent(), L->getHeader());
767 }
768
769 Value *WidenIV::getExtend(Value *NarrowOper, Type *WideType, bool IsSigned,
770                           Instruction *Use) {
771   // Set the debug location and conservative insertion point.
772   IRBuilder<> Builder(Use);
773   // Hoist the insertion point into loop preheaders as far as possible.
774   for (const Loop *L = LI->getLoopFor(Use->getParent());
775        L && L->getLoopPreheader() && isLoopInvariant(NarrowOper, L, DT);
776        L = L->getParentLoop())
777     Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
778
779   return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
780                     Builder.CreateZExt(NarrowOper, WideType);
781 }
782
783 /// CloneIVUser - Instantiate a wide operation to replace a narrow
784 /// operation. This only needs to handle operations that can evaluation to
785 /// SCEVAddRec. It can safely return 0 for any operation we decide not to clone.
786 Instruction *WidenIV::CloneIVUser(NarrowIVDefUse DU) {
787   unsigned Opcode = DU.NarrowUse->getOpcode();
788   switch (Opcode) {
789   default:
790     return 0;
791   case Instruction::Add:
792   case Instruction::Mul:
793   case Instruction::UDiv:
794   case Instruction::Sub:
795   case Instruction::And:
796   case Instruction::Or:
797   case Instruction::Xor:
798   case Instruction::Shl:
799   case Instruction::LShr:
800   case Instruction::AShr:
801     DEBUG(dbgs() << "Cloning IVUser: " << *DU.NarrowUse << "\n");
802
803     // Replace NarrowDef operands with WideDef. Otherwise, we don't know
804     // anything about the narrow operand yet so must insert a [sz]ext. It is
805     // probably loop invariant and will be folded or hoisted. If it actually
806     // comes from a widened IV, it should be removed during a future call to
807     // WidenIVUse.
808     Value *LHS = (DU.NarrowUse->getOperand(0) == DU.NarrowDef) ? DU.WideDef :
809       getExtend(DU.NarrowUse->getOperand(0), WideType, IsSigned, DU.NarrowUse);
810     Value *RHS = (DU.NarrowUse->getOperand(1) == DU.NarrowDef) ? DU.WideDef :
811       getExtend(DU.NarrowUse->getOperand(1), WideType, IsSigned, DU.NarrowUse);
812
813     BinaryOperator *NarrowBO = cast<BinaryOperator>(DU.NarrowUse);
814     BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(),
815                                                     LHS, RHS,
816                                                     NarrowBO->getName());
817     IRBuilder<> Builder(DU.NarrowUse);
818     Builder.Insert(WideBO);
819     if (const OverflowingBinaryOperator *OBO =
820         dyn_cast<OverflowingBinaryOperator>(NarrowBO)) {
821       if (OBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap();
822       if (OBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap();
823     }
824     return WideBO;
825   }
826 }
827
828 /// No-wrap operations can transfer sign extension of their result to their
829 /// operands. Generate the SCEV value for the widened operation without
830 /// actually modifying the IR yet. If the expression after extending the
831 /// operands is an AddRec for this loop, return it.
832 const SCEVAddRecExpr* WidenIV::GetExtendedOperandRecurrence(NarrowIVDefUse DU) {
833   // Handle the common case of add<nsw/nuw>
834   if (DU.NarrowUse->getOpcode() != Instruction::Add)
835     return 0;
836
837   // One operand (NarrowDef) has already been extended to WideDef. Now determine
838   // if extending the other will lead to a recurrence.
839   unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
840   assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
841
842   const SCEV *ExtendOperExpr = 0;
843   const OverflowingBinaryOperator *OBO =
844     cast<OverflowingBinaryOperator>(DU.NarrowUse);
845   if (IsSigned && OBO->hasNoSignedWrap())
846     ExtendOperExpr = SE->getSignExtendExpr(
847       SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
848   else if(!IsSigned && OBO->hasNoUnsignedWrap())
849     ExtendOperExpr = SE->getZeroExtendExpr(
850       SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
851   else
852     return 0;
853
854   // When creating this AddExpr, don't apply the current operations NSW or NUW
855   // flags. This instruction may be guarded by control flow that the no-wrap
856   // behavior depends on. Non-control-equivalent instructions can be mapped to
857   // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
858   // semantics to those operations.
859   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(
860     SE->getAddExpr(SE->getSCEV(DU.WideDef), ExtendOperExpr));
861
862   if (!AddRec || AddRec->getLoop() != L)
863     return 0;
864   return AddRec;
865 }
866
867 /// GetWideRecurrence - Is this instruction potentially interesting from
868 /// IVUsers' perspective after widening it's type? In other words, can the
869 /// extend be safely hoisted out of the loop with SCEV reducing the value to a
870 /// recurrence on the same loop. If so, return the sign or zero extended
871 /// recurrence. Otherwise return NULL.
872 const SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) {
873   if (!SE->isSCEVable(NarrowUse->getType()))
874     return 0;
875
876   const SCEV *NarrowExpr = SE->getSCEV(NarrowUse);
877   if (SE->getTypeSizeInBits(NarrowExpr->getType())
878       >= SE->getTypeSizeInBits(WideType)) {
879     // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
880     // index. So don't follow this use.
881     return 0;
882   }
883
884   const SCEV *WideExpr = IsSigned ?
885     SE->getSignExtendExpr(NarrowExpr, WideType) :
886     SE->getZeroExtendExpr(NarrowExpr, WideType);
887   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
888   if (!AddRec || AddRec->getLoop() != L)
889     return 0;
890   return AddRec;
891 }
892
893 /// WidenIVUse - Determine whether an individual user of the narrow IV can be
894 /// widened. If so, return the wide clone of the user.
895 Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
896
897   // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
898   if (isa<PHINode>(DU.NarrowUse) &&
899       LI->getLoopFor(DU.NarrowUse->getParent()) != L)
900     return 0;
901
902   // Our raison d'etre! Eliminate sign and zero extension.
903   if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) {
904     Value *NewDef = DU.WideDef;
905     if (DU.NarrowUse->getType() != WideType) {
906       unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
907       unsigned IVWidth = SE->getTypeSizeInBits(WideType);
908       if (CastWidth < IVWidth) {
909         // The cast isn't as wide as the IV, so insert a Trunc.
910         IRBuilder<> Builder(DU.NarrowUse);
911         NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
912       }
913       else {
914         // A wider extend was hidden behind a narrower one. This may induce
915         // another round of IV widening in which the intermediate IV becomes
916         // dead. It should be very rare.
917         DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
918               << " not wide enough to subsume " << *DU.NarrowUse << "\n");
919         DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
920         NewDef = DU.NarrowUse;
921       }
922     }
923     if (NewDef != DU.NarrowUse) {
924       DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
925             << " replaced by " << *DU.WideDef << "\n");
926       ++NumElimExt;
927       DU.NarrowUse->replaceAllUsesWith(NewDef);
928       DeadInsts.push_back(DU.NarrowUse);
929     }
930     // Now that the extend is gone, we want to expose it's uses for potential
931     // further simplification. We don't need to directly inform SimplifyIVUsers
932     // of the new users, because their parent IV will be processed later as a
933     // new loop phi. If we preserved IVUsers analysis, we would also want to
934     // push the uses of WideDef here.
935
936     // No further widening is needed. The deceased [sz]ext had done it for us.
937     return 0;
938   }
939
940   // Does this user itself evaluate to a recurrence after widening?
941   const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(DU.NarrowUse);
942   if (!WideAddRec) {
943       WideAddRec = GetExtendedOperandRecurrence(DU);
944   }
945   if (!WideAddRec) {
946     // This user does not evaluate to a recurence after widening, so don't
947     // follow it. Instead insert a Trunc to kill off the original use,
948     // eventually isolating the original narrow IV so it can be removed.
949     IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT));
950     Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
951     DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
952     return 0;
953   }
954   // Assume block terminators cannot evaluate to a recurrence. We can't to
955   // insert a Trunc after a terminator if there happens to be a critical edge.
956   assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
957          "SCEV is not expected to evaluate a block terminator");
958
959   // Reuse the IV increment that SCEVExpander created as long as it dominates
960   // NarrowUse.
961   Instruction *WideUse = 0;
962   if (WideAddRec == WideIncExpr
963       && Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
964     WideUse = WideInc;
965   else {
966     WideUse = CloneIVUser(DU);
967     if (!WideUse)
968       return 0;
969   }
970   // Evaluation of WideAddRec ensured that the narrow expression could be
971   // extended outside the loop without overflow. This suggests that the wide use
972   // evaluates to the same expression as the extended narrow use, but doesn't
973   // absolutely guarantee it. Hence the following failsafe check. In rare cases
974   // where it fails, we simply throw away the newly created wide use.
975   if (WideAddRec != SE->getSCEV(WideUse)) {
976     DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse
977           << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n");
978     DeadInsts.push_back(WideUse);
979     return 0;
980   }
981
982   // Returning WideUse pushes it on the worklist.
983   return WideUse;
984 }
985
986 /// pushNarrowIVUsers - Add eligible users of NarrowDef to NarrowIVUsers.
987 ///
988 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
989   for (Value::use_iterator UI = NarrowDef->use_begin(),
990          UE = NarrowDef->use_end(); UI != UE; ++UI) {
991     Instruction *NarrowUse = cast<Instruction>(*UI);
992
993     // Handle data flow merges and bizarre phi cycles.
994     if (!Widened.insert(NarrowUse))
995       continue;
996
997     NarrowIVUsers.push_back(NarrowIVDefUse(NarrowDef, NarrowUse, WideDef));
998   }
999 }
1000
1001 /// CreateWideIV - Process a single induction variable. First use the
1002 /// SCEVExpander to create a wide induction variable that evaluates to the same
1003 /// recurrence as the original narrow IV. Then use a worklist to forward
1004 /// traverse the narrow IV's def-use chain. After WidenIVUse has processed all
1005 /// interesting IV users, the narrow IV will be isolated for removal by
1006 /// DeleteDeadPHIs.
1007 ///
1008 /// It would be simpler to delete uses as they are processed, but we must avoid
1009 /// invalidating SCEV expressions.
1010 ///
1011 PHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) {
1012   // Is this phi an induction variable?
1013   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1014   if (!AddRec)
1015     return NULL;
1016
1017   // Widen the induction variable expression.
1018   const SCEV *WideIVExpr = IsSigned ?
1019     SE->getSignExtendExpr(AddRec, WideType) :
1020     SE->getZeroExtendExpr(AddRec, WideType);
1021
1022   assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1023          "Expect the new IV expression to preserve its type");
1024
1025   // Can the IV be extended outside the loop without overflow?
1026   AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1027   if (!AddRec || AddRec->getLoop() != L)
1028     return NULL;
1029
1030   // An AddRec must have loop-invariant operands. Since this AddRec is
1031   // materialized by a loop header phi, the expression cannot have any post-loop
1032   // operands, so they must dominate the loop header.
1033   assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1034          SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader())
1035          && "Loop header phi recurrence inputs do not dominate the loop");
1036
1037   // The rewriter provides a value for the desired IV expression. This may
1038   // either find an existing phi or materialize a new one. Either way, we
1039   // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1040   // of the phi-SCC dominates the loop entry.
1041   Instruction *InsertPt = L->getHeader()->begin();
1042   WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));
1043
1044   // Remembering the WideIV increment generated by SCEVExpander allows
1045   // WidenIVUse to reuse it when widening the narrow IV's increment. We don't
1046   // employ a general reuse mechanism because the call above is the only call to
1047   // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1048   if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1049     WideInc =
1050       cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1051     WideIncExpr = SE->getSCEV(WideInc);
1052   }
1053
1054   DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1055   ++NumWidened;
1056
1057   // Traverse the def-use chain using a worklist starting at the original IV.
1058   assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1059
1060   Widened.insert(OrigPhi);
1061   pushNarrowIVUsers(OrigPhi, WidePhi);
1062
1063   while (!NarrowIVUsers.empty()) {
1064     NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1065
1066     // Process a def-use edge. This may replace the use, so don't hold a
1067     // use_iterator across it.
1068     Instruction *WideUse = WidenIVUse(DU, Rewriter);
1069
1070     // Follow all def-use edges from the previous narrow use.
1071     if (WideUse)
1072       pushNarrowIVUsers(DU.NarrowUse, WideUse);
1073
1074     // WidenIVUse may have removed the def-use edge.
1075     if (DU.NarrowDef->use_empty())
1076       DeadInsts.push_back(DU.NarrowDef);
1077   }
1078   return WidePhi;
1079 }
1080
1081 //===----------------------------------------------------------------------===//
1082 //  Simplification of IV users based on SCEV evaluation.
1083 //===----------------------------------------------------------------------===//
1084
1085
1086 /// SimplifyAndExtend - Iteratively perform simplification on a worklist of IV
1087 /// users. Each successive simplification may push more users which may
1088 /// themselves be candidates for simplification.
1089 ///
1090 /// Sign/Zero extend elimination is interleaved with IV simplification.
1091 ///
1092 void IndVarSimplify::SimplifyAndExtend(Loop *L,
1093                                        SCEVExpander &Rewriter,
1094                                        LPPassManager &LPM) {
1095   SmallVector<WideIVInfo, 8> WideIVs;
1096
1097   SmallVector<PHINode*, 8> LoopPhis;
1098   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
1099     LoopPhis.push_back(cast<PHINode>(I));
1100   }
1101   // Each round of simplification iterates through the SimplifyIVUsers worklist
1102   // for all current phis, then determines whether any IVs can be
1103   // widened. Widening adds new phis to LoopPhis, inducing another round of
1104   // simplification on the wide IVs.
1105   while (!LoopPhis.empty()) {
1106     // Evaluate as many IV expressions as possible before widening any IVs. This
1107     // forces SCEV to set no-wrap flags before evaluating sign/zero
1108     // extension. The first time SCEV attempts to normalize sign/zero extension,
1109     // the result becomes final. So for the most predictable results, we delay
1110     // evaluation of sign/zero extend evaluation until needed, and avoid running
1111     // other SCEV based analysis prior to SimplifyAndExtend.
1112     do {
1113       PHINode *CurrIV = LoopPhis.pop_back_val();
1114
1115       // Information about sign/zero extensions of CurrIV.
1116       WideIVVisitor WIV(CurrIV, SE, TD);
1117
1118       Changed |= simplifyUsersOfIV(CurrIV, SE, &LPM, DeadInsts, &WIV);
1119
1120       if (WIV.WI.WidestNativeType) {
1121         WideIVs.push_back(WIV.WI);
1122       }
1123     } while(!LoopPhis.empty());
1124
1125     for (; !WideIVs.empty(); WideIVs.pop_back()) {
1126       WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts);
1127       if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) {
1128         Changed = true;
1129         LoopPhis.push_back(WidePhi);
1130       }
1131     }
1132   }
1133 }
1134
1135 //===----------------------------------------------------------------------===//
1136 //  LinearFunctionTestReplace and its kin. Rewrite the loop exit condition.
1137 //===----------------------------------------------------------------------===//
1138
1139 /// Check for expressions that ScalarEvolution generates to compute
1140 /// BackedgeTakenInfo. If these expressions have not been reduced, then
1141 /// expanding them may incur additional cost (albeit in the loop preheader).
1142 static bool isHighCostExpansion(const SCEV *S, BranchInst *BI,
1143                                 SmallPtrSet<const SCEV*, 8> &Processed,
1144                                 ScalarEvolution *SE) {
1145   if (!Processed.insert(S))
1146     return false;
1147
1148   // If the backedge-taken count is a UDiv, it's very likely a UDiv that
1149   // ScalarEvolution's HowFarToZero or HowManyLessThans produced to compute a
1150   // precise expression, rather than a UDiv from the user's code. If we can't
1151   // find a UDiv in the code with some simple searching, assume the former and
1152   // forego rewriting the loop.
1153   if (isa<SCEVUDivExpr>(S)) {
1154     ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition());
1155     if (!OrigCond) return true;
1156     const SCEV *R = SE->getSCEV(OrigCond->getOperand(1));
1157     R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1));
1158     if (R != S) {
1159       const SCEV *L = SE->getSCEV(OrigCond->getOperand(0));
1160       L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1));
1161       if (L != S)
1162         return true;
1163     }
1164   }
1165
1166   // Recurse past add expressions, which commonly occur in the
1167   // BackedgeTakenCount. They may already exist in program code, and if not,
1168   // they are not too expensive rematerialize.
1169   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
1170     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
1171          I != E; ++I) {
1172       if (isHighCostExpansion(*I, BI, Processed, SE))
1173         return true;
1174     }
1175     return false;
1176   }
1177
1178   // HowManyLessThans uses a Max expression whenever the loop is not guarded by
1179   // the exit condition.
1180   if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S))
1181     return true;
1182
1183   // If we haven't recognized an expensive SCEV pattern, assume it's an
1184   // expression produced by program code.
1185   return false;
1186 }
1187
1188 /// canExpandBackedgeTakenCount - Return true if this loop's backedge taken
1189 /// count expression can be safely and cheaply expanded into an instruction
1190 /// sequence that can be used by LinearFunctionTestReplace.
1191 ///
1192 /// TODO: This fails for pointer-type loop counters with greater than one byte
1193 /// strides, consequently preventing LFTR from running. For the purpose of LFTR
1194 /// we could skip this check in the case that the LFTR loop counter (chosen by
1195 /// FindLoopCounter) is also pointer type. Instead, we could directly convert
1196 /// the loop test to an inequality test by checking the target data's alignment
1197 /// of element types (given that the initial pointer value originates from or is
1198 /// used by ABI constrained operation, as opposed to inttoptr/ptrtoint).
1199 /// However, we don't yet have a strong motivation for converting loop tests
1200 /// into inequality tests.
1201 static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) {
1202   const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1203   if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) ||
1204       BackedgeTakenCount->isZero())
1205     return false;
1206
1207   if (!L->getExitingBlock())
1208     return false;
1209
1210   // Can't rewrite non-branch yet.
1211   BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator());
1212   if (!BI)
1213     return false;
1214
1215   SmallPtrSet<const SCEV*, 8> Processed;
1216   if (isHighCostExpansion(BackedgeTakenCount, BI, Processed, SE))
1217     return false;
1218
1219   return true;
1220 }
1221
1222 /// getLoopPhiForCounter - Return the loop header phi IFF IncV adds a loop
1223 /// invariant value to the phi.
1224 static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) {
1225   Instruction *IncI = dyn_cast<Instruction>(IncV);
1226   if (!IncI)
1227     return 0;
1228
1229   switch (IncI->getOpcode()) {
1230   case Instruction::Add:
1231   case Instruction::Sub:
1232     break;
1233   case Instruction::GetElementPtr:
1234     // An IV counter must preserve its type.
1235     if (IncI->getNumOperands() == 2)
1236       break;
1237   default:
1238     return 0;
1239   }
1240
1241   PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0));
1242   if (Phi && Phi->getParent() == L->getHeader()) {
1243     if (isLoopInvariant(IncI->getOperand(1), L, DT))
1244       return Phi;
1245     return 0;
1246   }
1247   if (IncI->getOpcode() == Instruction::GetElementPtr)
1248     return 0;
1249
1250   // Allow add/sub to be commuted.
1251   Phi = dyn_cast<PHINode>(IncI->getOperand(1));
1252   if (Phi && Phi->getParent() == L->getHeader()) {
1253     if (isLoopInvariant(IncI->getOperand(0), L, DT))
1254       return Phi;
1255   }
1256   return 0;
1257 }
1258
1259 /// Return the compare guarding the loop latch, or NULL for unrecognized tests.
1260 static ICmpInst *getLoopTest(Loop *L) {
1261   assert(L->getExitingBlock() && "expected loop exit");
1262
1263   BasicBlock *LatchBlock = L->getLoopLatch();
1264   // Don't bother with LFTR if the loop is not properly simplified.
1265   if (!LatchBlock)
1266     return 0;
1267
1268   BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator());
1269   assert(BI && "expected exit branch");
1270
1271   return dyn_cast<ICmpInst>(BI->getCondition());
1272 }
1273
1274 /// needsLFTR - LinearFunctionTestReplace policy. Return true unless we can show
1275 /// that the current exit test is already sufficiently canonical.
1276 static bool needsLFTR(Loop *L, DominatorTree *DT) {
1277   // Do LFTR to simplify the exit condition to an ICMP.
1278   ICmpInst *Cond = getLoopTest(L);
1279   if (!Cond)
1280     return true;
1281
1282   // Do LFTR to simplify the exit ICMP to EQ/NE
1283   ICmpInst::Predicate Pred = Cond->getPredicate();
1284   if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
1285     return true;
1286
1287   // Look for a loop invariant RHS
1288   Value *LHS = Cond->getOperand(0);
1289   Value *RHS = Cond->getOperand(1);
1290   if (!isLoopInvariant(RHS, L, DT)) {
1291     if (!isLoopInvariant(LHS, L, DT))
1292       return true;
1293     std::swap(LHS, RHS);
1294   }
1295   // Look for a simple IV counter LHS
1296   PHINode *Phi = dyn_cast<PHINode>(LHS);
1297   if (!Phi)
1298     Phi = getLoopPhiForCounter(LHS, L, DT);
1299
1300   if (!Phi)
1301     return true;
1302
1303   // Do LFTR if PHI node is defined in the loop, but is *not* a counter.
1304   int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
1305   if (Idx < 0)
1306     return true;
1307
1308   // Do LFTR if the exit condition's IV is *not* a simple counter.
1309   Value *IncV = Phi->getIncomingValue(Idx);
1310   return Phi != getLoopPhiForCounter(IncV, L, DT);
1311 }
1312
1313 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
1314 /// down to checking that all operands are constant and listing instructions
1315 /// that may hide undef.
1316 static bool hasConcreteDefImpl(Value *V, SmallPtrSet<Value*, 8> &Visited,
1317                                unsigned Depth) {
1318   if (isa<Constant>(V))
1319     return !isa<UndefValue>(V);
1320
1321   if (Depth >= 6)
1322     return false;
1323
1324   // Conservatively handle non-constant non-instructions. For example, Arguments
1325   // may be undef.
1326   Instruction *I = dyn_cast<Instruction>(V);
1327   if (!I)
1328     return false;
1329
1330   // Load and return values may be undef.
1331   if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I))
1332     return false;
1333
1334   // Optimistically handle other instructions.
1335   for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) {
1336     if (!Visited.insert(*OI))
1337       continue;
1338     if (!hasConcreteDefImpl(*OI, Visited, Depth+1))
1339       return false;
1340   }
1341   return true;
1342 }
1343
1344 /// Return true if the given value is concrete. We must prove that undef can
1345 /// never reach it.
1346 ///
1347 /// TODO: If we decide that this is a good approach to checking for undef, we
1348 /// may factor it into a common location.
1349 static bool hasConcreteDef(Value *V) {
1350   SmallPtrSet<Value*, 8> Visited;
1351   Visited.insert(V);
1352   return hasConcreteDefImpl(V, Visited, 0);
1353 }
1354
1355 /// AlmostDeadIV - Return true if this IV has any uses other than the (soon to
1356 /// be rewritten) loop exit test.
1357 static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) {
1358   int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
1359   Value *IncV = Phi->getIncomingValue(LatchIdx);
1360
1361   for (Value::use_iterator UI = Phi->use_begin(), UE = Phi->use_end();
1362        UI != UE; ++UI) {
1363     if (*UI != Cond && *UI != IncV) return false;
1364   }
1365
1366   for (Value::use_iterator UI = IncV->use_begin(), UE = IncV->use_end();
1367        UI != UE; ++UI) {
1368     if (*UI != Cond && *UI != Phi) return false;
1369   }
1370   return true;
1371 }
1372
1373 /// FindLoopCounter - Find an affine IV in canonical form.
1374 ///
1375 /// BECount may be an i8* pointer type. The pointer difference is already
1376 /// valid count without scaling the address stride, so it remains a pointer
1377 /// expression as far as SCEV is concerned.
1378 ///
1379 /// Currently only valid for LFTR. See the comments on hasConcreteDef below.
1380 ///
1381 /// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount
1382 ///
1383 /// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride.
1384 /// This is difficult in general for SCEV because of potential overflow. But we
1385 /// could at least handle constant BECounts.
1386 static PHINode *
1387 FindLoopCounter(Loop *L, const SCEV *BECount,
1388                 ScalarEvolution *SE, DominatorTree *DT, const DataLayout *TD) {
1389   uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());
1390
1391   Value *Cond =
1392     cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition();
1393
1394   // Loop over all of the PHI nodes, looking for a simple counter.
1395   PHINode *BestPhi = 0;
1396   const SCEV *BestInit = 0;
1397   BasicBlock *LatchBlock = L->getLoopLatch();
1398   assert(LatchBlock && "needsLFTR should guarantee a loop latch");
1399
1400   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
1401     PHINode *Phi = cast<PHINode>(I);
1402     if (!SE->isSCEVable(Phi->getType()))
1403       continue;
1404
1405     // Avoid comparing an integer IV against a pointer Limit.
1406     if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy())
1407       continue;
1408
1409     const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
1410     if (!AR || AR->getLoop() != L || !AR->isAffine())
1411       continue;
1412
1413     // AR may be a pointer type, while BECount is an integer type.
1414     // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
1415     // AR may not be a narrower type, or we may never exit.
1416     uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());
1417     if (PhiWidth < BCWidth || (TD && !TD->isLegalInteger(PhiWidth)))
1418       continue;
1419
1420     const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
1421     if (!Step || !Step->isOne())
1422       continue;
1423
1424     int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
1425     Value *IncV = Phi->getIncomingValue(LatchIdx);
1426     if (getLoopPhiForCounter(IncV, L, DT) != Phi)
1427       continue;
1428
1429     // Avoid reusing a potentially undef value to compute other values that may
1430     // have originally had a concrete definition.
1431     if (!hasConcreteDef(Phi)) {
1432       // We explicitly allow unknown phis as long as they are already used by
1433       // the loop test. In this case we assume that performing LFTR could not
1434       // increase the number of undef users.
1435       if (ICmpInst *Cond = getLoopTest(L)) {
1436         if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L, DT)
1437             && Phi != getLoopPhiForCounter(Cond->getOperand(1), L, DT)) {
1438           continue;
1439         }
1440       }
1441     }
1442     const SCEV *Init = AR->getStart();
1443
1444     if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) {
1445       // Don't force a live loop counter if another IV can be used.
1446       if (AlmostDeadIV(Phi, LatchBlock, Cond))
1447         continue;
1448
1449       // Prefer to count-from-zero. This is a more "canonical" counter form. It
1450       // also prefers integer to pointer IVs.
1451       if (BestInit->isZero() != Init->isZero()) {
1452         if (BestInit->isZero())
1453           continue;
1454       }
1455       // If two IVs both count from zero or both count from nonzero then the
1456       // narrower is likely a dead phi that has been widened. Use the wider phi
1457       // to allow the other to be eliminated.
1458       else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))
1459         continue;
1460     }
1461     BestPhi = Phi;
1462     BestInit = Init;
1463   }
1464   return BestPhi;
1465 }
1466
1467 /// genLoopLimit - Help LinearFunctionTestReplace by generating a value that
1468 /// holds the RHS of the new loop test.
1469 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L,
1470                            SCEVExpander &Rewriter, ScalarEvolution *SE) {
1471   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
1472   assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter");
1473   const SCEV *IVInit = AR->getStart();
1474
1475   // IVInit may be a pointer while IVCount is an integer when FindLoopCounter
1476   // finds a valid pointer IV. Sign extend BECount in order to materialize a
1477   // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing
1478   // the existing GEPs whenever possible.
1479   if (IndVar->getType()->isPointerTy()
1480       && !IVCount->getType()->isPointerTy()) {
1481
1482     Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType());
1483     const SCEV *IVOffset = SE->getTruncateOrSignExtend(IVCount, OfsTy);
1484
1485     // Expand the code for the iteration count.
1486     assert(SE->isLoopInvariant(IVOffset, L) &&
1487            "Computed iteration count is not loop invariant!");
1488     BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
1489     Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI);
1490
1491     Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader());
1492     assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter");
1493     // We could handle pointer IVs other than i8*, but we need to compensate for
1494     // gep index scaling. See canExpandBackedgeTakenCount comments.
1495     assert(SE->getSizeOfExpr(
1496              cast<PointerType>(GEPBase->getType())->getElementType())->isOne()
1497            && "unit stride pointer IV must be i8*");
1498
1499     IRBuilder<> Builder(L->getLoopPreheader()->getTerminator());
1500     return Builder.CreateGEP(GEPBase, GEPOffset, "lftr.limit");
1501   }
1502   else {
1503     // In any other case, convert both IVInit and IVCount to integers before
1504     // comparing. This may result in SCEV expension of pointers, but in practice
1505     // SCEV will fold the pointer arithmetic away as such:
1506     // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc).
1507     //
1508     // Valid Cases: (1) both integers is most common; (2) both may be pointers
1509     // for simple memset-style loops; (3) IVInit is an integer and IVCount is a
1510     // pointer may occur when enable-iv-rewrite generates a canonical IV on top
1511     // of case #2.
1512
1513     const SCEV *IVLimit = 0;
1514     // For unit stride, IVCount = Start + BECount with 2's complement overflow.
1515     // For non-zero Start, compute IVCount here.
1516     if (AR->getStart()->isZero())
1517       IVLimit = IVCount;
1518     else {
1519       assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride");
1520       const SCEV *IVInit = AR->getStart();
1521
1522       // For integer IVs, truncate the IV before computing IVInit + BECount.
1523       if (SE->getTypeSizeInBits(IVInit->getType())
1524           > SE->getTypeSizeInBits(IVCount->getType()))
1525         IVInit = SE->getTruncateExpr(IVInit, IVCount->getType());
1526
1527       IVLimit = SE->getAddExpr(IVInit, IVCount);
1528     }
1529     // Expand the code for the iteration count.
1530     BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
1531     IRBuilder<> Builder(BI);
1532     assert(SE->isLoopInvariant(IVLimit, L) &&
1533            "Computed iteration count is not loop invariant!");
1534     // Ensure that we generate the same type as IndVar, or a smaller integer
1535     // type. In the presence of null pointer values, we have an integer type
1536     // SCEV expression (IVInit) for a pointer type IV value (IndVar).
1537     Type *LimitTy = IVCount->getType()->isPointerTy() ?
1538       IndVar->getType() : IVCount->getType();
1539     return Rewriter.expandCodeFor(IVLimit, LimitTy, BI);
1540   }
1541 }
1542
1543 /// LinearFunctionTestReplace - This method rewrites the exit condition of the
1544 /// loop to be a canonical != comparison against the incremented loop induction
1545 /// variable.  This pass is able to rewrite the exit tests of any loop where the
1546 /// SCEV analysis can determine a loop-invariant trip count of the loop, which
1547 /// is actually a much broader range than just linear tests.
1548 Value *IndVarSimplify::
1549 LinearFunctionTestReplace(Loop *L,
1550                           const SCEV *BackedgeTakenCount,
1551                           PHINode *IndVar,
1552                           SCEVExpander &Rewriter) {
1553   assert(canExpandBackedgeTakenCount(L, SE) && "precondition");
1554
1555   // Initialize CmpIndVar and IVCount to their preincremented values.
1556   Value *CmpIndVar = IndVar;
1557   const SCEV *IVCount = BackedgeTakenCount;
1558
1559   // If the exiting block is the same as the backedge block, we prefer to
1560   // compare against the post-incremented value, otherwise we must compare
1561   // against the preincremented value.
1562   if (L->getExitingBlock() == L->getLoopLatch()) {
1563     // Add one to the "backedge-taken" count to get the trip count.
1564     // This addition may overflow, which is valid as long as the comparison is
1565     // truncated to BackedgeTakenCount->getType().
1566     IVCount = SE->getAddExpr(BackedgeTakenCount,
1567                              SE->getConstant(BackedgeTakenCount->getType(), 1));
1568     // The BackedgeTaken expression contains the number of times that the
1569     // backedge branches to the loop header.  This is one less than the
1570     // number of times the loop executes, so use the incremented indvar.
1571     CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock());
1572   }
1573
1574   Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE);
1575   assert(ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy()
1576          && "genLoopLimit missed a cast");
1577
1578   // Insert a new icmp_ne or icmp_eq instruction before the branch.
1579   BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
1580   ICmpInst::Predicate P;
1581   if (L->contains(BI->getSuccessor(0)))
1582     P = ICmpInst::ICMP_NE;
1583   else
1584     P = ICmpInst::ICMP_EQ;
1585
1586   DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
1587                << "      LHS:" << *CmpIndVar << '\n'
1588                << "       op:\t"
1589                << (P == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
1590                << "      RHS:\t" << *ExitCnt << "\n"
1591                << "  IVCount:\t" << *IVCount << "\n");
1592
1593   IRBuilder<> Builder(BI);
1594
1595   // LFTR can ignore IV overflow and truncate to the width of
1596   // BECount. This avoids materializing the add(zext(add)) expression.
1597   unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType());
1598   unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType());
1599   if (CmpIndVarSize > ExitCntSize) {
1600     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
1601     const SCEV *ARStart = AR->getStart();
1602     const SCEV *ARStep = AR->getStepRecurrence(*SE);
1603     // For constant IVCount, avoid truncation.
1604     if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) {
1605       const APInt &Start = cast<SCEVConstant>(ARStart)->getValue()->getValue();
1606       APInt Count = cast<SCEVConstant>(IVCount)->getValue()->getValue();
1607       // Note that the post-inc value of BackedgeTakenCount may have overflowed
1608       // above such that IVCount is now zero.
1609       if (IVCount != BackedgeTakenCount && Count == 0) {
1610         Count = APInt::getMaxValue(Count.getBitWidth()).zext(CmpIndVarSize);
1611         ++Count;
1612       }
1613       else
1614         Count = Count.zext(CmpIndVarSize);
1615       APInt NewLimit;
1616       if (cast<SCEVConstant>(ARStep)->getValue()->isNegative())
1617         NewLimit = Start - Count;
1618       else
1619         NewLimit = Start + Count;
1620       ExitCnt = ConstantInt::get(CmpIndVar->getType(), NewLimit);
1621
1622       DEBUG(dbgs() << "  Widen RHS:\t" << *ExitCnt << "\n");
1623     } else {
1624       CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),
1625                                       "lftr.wideiv");
1626     }
1627   }
1628   Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");
1629   Value *OrigCond = BI->getCondition();
1630   // It's tempting to use replaceAllUsesWith here to fully replace the old
1631   // comparison, but that's not immediately safe, since users of the old
1632   // comparison may not be dominated by the new comparison. Instead, just
1633   // update the branch to use the new comparison; in the common case this
1634   // will make old comparison dead.
1635   BI->setCondition(Cond);
1636   DeadInsts.push_back(OrigCond);
1637
1638   ++NumLFTR;
1639   Changed = true;
1640   return Cond;
1641 }
1642
1643 //===----------------------------------------------------------------------===//
1644 //  SinkUnusedInvariants. A late subpass to cleanup loop preheaders.
1645 //===----------------------------------------------------------------------===//
1646
1647 /// If there's a single exit block, sink any loop-invariant values that
1648 /// were defined in the preheader but not used inside the loop into the
1649 /// exit block to reduce register pressure in the loop.
1650 void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
1651   BasicBlock *ExitBlock = L->getExitBlock();
1652   if (!ExitBlock) return;
1653
1654   BasicBlock *Preheader = L->getLoopPreheader();
1655   if (!Preheader) return;
1656
1657   Instruction *InsertPt = ExitBlock->getFirstInsertionPt();
1658   BasicBlock::iterator I = Preheader->getTerminator();
1659   while (I != Preheader->begin()) {
1660     --I;
1661     // New instructions were inserted at the end of the preheader.
1662     if (isa<PHINode>(I))
1663       break;
1664
1665     // Don't move instructions which might have side effects, since the side
1666     // effects need to complete before instructions inside the loop.  Also don't
1667     // move instructions which might read memory, since the loop may modify
1668     // memory. Note that it's okay if the instruction might have undefined
1669     // behavior: LoopSimplify guarantees that the preheader dominates the exit
1670     // block.
1671     if (I->mayHaveSideEffects() || I->mayReadFromMemory())
1672       continue;
1673
1674     // Skip debug info intrinsics.
1675     if (isa<DbgInfoIntrinsic>(I))
1676       continue;
1677
1678     // Skip landingpad instructions.
1679     if (isa<LandingPadInst>(I))
1680       continue;
1681
1682     // Don't sink alloca: we never want to sink static alloca's out of the
1683     // entry block, and correctly sinking dynamic alloca's requires
1684     // checks for stacksave/stackrestore intrinsics.
1685     // FIXME: Refactor this check somehow?
1686     if (isa<AllocaInst>(I))
1687       continue;
1688
1689     // Determine if there is a use in or before the loop (direct or
1690     // otherwise).
1691     bool UsedInLoop = false;
1692     for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
1693          UI != UE; ++UI) {
1694       User *U = *UI;
1695       BasicBlock *UseBB = cast<Instruction>(U)->getParent();
1696       if (PHINode *P = dyn_cast<PHINode>(U)) {
1697         unsigned i =
1698           PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
1699         UseBB = P->getIncomingBlock(i);
1700       }
1701       if (UseBB == Preheader || L->contains(UseBB)) {
1702         UsedInLoop = true;
1703         break;
1704       }
1705     }
1706
1707     // If there is, the def must remain in the preheader.
1708     if (UsedInLoop)
1709       continue;
1710
1711     // Otherwise, sink it to the exit block.
1712     Instruction *ToMove = I;
1713     bool Done = false;
1714
1715     if (I != Preheader->begin()) {
1716       // Skip debug info intrinsics.
1717       do {
1718         --I;
1719       } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
1720
1721       if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
1722         Done = true;
1723     } else {
1724       Done = true;
1725     }
1726
1727     ToMove->moveBefore(InsertPt);
1728     if (Done) break;
1729     InsertPt = ToMove;
1730   }
1731 }
1732
1733 //===----------------------------------------------------------------------===//
1734 //  IndVarSimplify driver. Manage several subpasses of IV simplification.
1735 //===----------------------------------------------------------------------===//
1736
1737 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
1738   // If LoopSimplify form is not available, stay out of trouble. Some notes:
1739   //  - LSR currently only supports LoopSimplify-form loops. Indvars'
1740   //    canonicalization can be a pessimization without LSR to "clean up"
1741   //    afterwards.
1742   //  - We depend on having a preheader; in particular,
1743   //    Loop::getCanonicalInductionVariable only supports loops with preheaders,
1744   //    and we're in trouble if we can't find the induction variable even when
1745   //    we've manually inserted one.
1746   if (!L->isLoopSimplifyForm())
1747     return false;
1748
1749   LI = &getAnalysis<LoopInfo>();
1750   SE = &getAnalysis<ScalarEvolution>();
1751   DT = &getAnalysis<DominatorTree>();
1752   TD = getAnalysisIfAvailable<DataLayout>();
1753   TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
1754
1755   DeadInsts.clear();
1756   Changed = false;
1757
1758   // If there are any floating-point recurrences, attempt to
1759   // transform them to use integer recurrences.
1760   RewriteNonIntegerIVs(L);
1761
1762   const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1763
1764   // Create a rewriter object which we'll use to transform the code with.
1765   SCEVExpander Rewriter(*SE, "indvars");
1766 #ifndef NDEBUG
1767   Rewriter.setDebugType(DEBUG_TYPE);
1768 #endif
1769
1770   // Eliminate redundant IV users.
1771   //
1772   // Simplification works best when run before other consumers of SCEV. We
1773   // attempt to avoid evaluating SCEVs for sign/zero extend operations until
1774   // other expressions involving loop IVs have been evaluated. This helps SCEV
1775   // set no-wrap flags before normalizing sign/zero extension.
1776   Rewriter.disableCanonicalMode();
1777   SimplifyAndExtend(L, Rewriter, LPM);
1778
1779   // Check to see if this loop has a computable loop-invariant execution count.
1780   // If so, this means that we can compute the final value of any expressions
1781   // that are recurrent in the loop, and substitute the exit values from the
1782   // loop into any instructions outside of the loop that use the final values of
1783   // the current expressions.
1784   //
1785   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
1786     RewriteLoopExitValues(L, Rewriter);
1787
1788   // Eliminate redundant IV cycles.
1789   NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
1790
1791   // If we have a trip count expression, rewrite the loop's exit condition
1792   // using it.  We can currently only handle loops with a single exit.
1793   if (canExpandBackedgeTakenCount(L, SE) && needsLFTR(L, DT)) {
1794     PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT, TD);
1795     if (IndVar) {
1796       // Check preconditions for proper SCEVExpander operation. SCEV does not
1797       // express SCEVExpander's dependencies, such as LoopSimplify. Instead any
1798       // pass that uses the SCEVExpander must do it. This does not work well for
1799       // loop passes because SCEVExpander makes assumptions about all loops, while
1800       // LoopPassManager only forces the current loop to be simplified.
1801       //
1802       // FIXME: SCEV expansion has no way to bail out, so the caller must
1803       // explicitly check any assumptions made by SCEV. Brittle.
1804       const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount);
1805       if (!AR || AR->getLoop()->getLoopPreheader())
1806         (void)LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
1807                                         Rewriter);
1808     }
1809   }
1810   // Clear the rewriter cache, because values that are in the rewriter's cache
1811   // can be deleted in the loop below, causing the AssertingVH in the cache to
1812   // trigger.
1813   Rewriter.clear();
1814
1815   // Now that we're done iterating through lists, clean up any instructions
1816   // which are now dead.
1817   while (!DeadInsts.empty())
1818     if (Instruction *Inst =
1819           dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
1820       RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
1821
1822   // The Rewriter may not be used from this point on.
1823
1824   // Loop-invariant instructions in the preheader that aren't used in the
1825   // loop may be sunk below the loop to reduce register pressure.
1826   SinkUnusedInvariants(L);
1827
1828   // Clean up dead instructions.
1829   Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
1830   // Check a post-condition.
1831   assert(L->isLCSSAForm(*DT) &&
1832          "Indvars did not leave the loop in lcssa form!");
1833
1834   // Verify that LFTR, and any other change have not interfered with SCEV's
1835   // ability to compute trip count.
1836 #ifndef NDEBUG
1837   if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
1838     SE->forgetLoop(L);
1839     const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
1840     if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
1841         SE->getTypeSizeInBits(NewBECount->getType()))
1842       NewBECount = SE->getTruncateOrNoop(NewBECount,
1843                                          BackedgeTakenCount->getType());
1844     else
1845       BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount,
1846                                                  NewBECount->getType());
1847     assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV");
1848   }
1849 #endif
1850
1851   return Changed;
1852 }