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 // This transformation makes the following changes to each loop with an
  15 // identifiable induction variable:
  16 //   1. All loops are transformed to have a SINGLE canonical induction variable
  17 //      which starts at zero and steps by one.
  18 //   2. The canonical induction variable is guaranteed to be the first PHI node
  19 //      in the loop header block.
  20 //   3. The canonical induction variable is guaranteed to be in a wide enough
  21 //      type so that IV expressions need not be (directly) zero-extended or
  22 //      sign-extended.
  23 //   4. Any pointer arithmetic recurrences are raised to use array subscripts.
  24 //
  25 // If the trip count of a loop is computable, this pass also makes the following
  26 // changes:
  27 //   1. The exit condition for the loop is canonicalized to compare the
  28 //      induction value against the exit value.  This turns loops like:
  29 //        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
  30 //   2. Any use outside of the loop of an expression derived from the indvar
  31 //      is changed to compute the derived value outside of the loop, eliminating
  32 //      the dependence on the exit value of the induction variable.  If the only
  33 //      purpose of the loop is to compute the exit value of some derived
  34 //      expression, this transformation will make the loop dead.
  35 //
  36 // This transformation should be followed by strength reduction after all of the
  37 // desired loop transformations have been performed.
  38 //
  39 //===----------------------------------------------------------------------===//
  40
  41 #define DEBUG_TYPE "indvars"
  42 #include "llvm/Transforms/Scalar.h"
  43 #include "llvm/BasicBlock.h"
  44 #include "llvm/Constants.h"
  45 #include "llvm/Instructions.h"
  46 #include "llvm/IntrinsicInst.h"
  47 #include "llvm/LLVMContext.h"
  48 #include "llvm/Type.h"
  49 #include "llvm/Analysis/Dominators.h"
  50 #include "llvm/Analysis/IVUsers.h"
  51 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  52 #include "llvm/Analysis/LoopInfo.h"
  53 #include "llvm/Analysis/LoopPass.h"
  54 #include "llvm/Analysis/ValueTracking.h"
  55 #include "llvm/Support/CFG.h"
  56 #include "llvm/Support/CommandLine.h"
  57 #include "llvm/Support/Debug.h"
  58 #include "llvm/Support/raw_ostream.h"
  59 #include "llvm/Transforms/Utils/Local.h"
  60 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  61 #include "llvm/Target/TargetData.h"
  62 #include "llvm/ADT/SmallVector.h"
  63 #include "llvm/ADT/Statistic.h"
  64 #include "llvm/ADT/STLExtras.h"
  65 using namespace llvm;
  66
  67 STATISTIC(NumRemoved , "Number of aux indvars removed");
  68 STATISTIC(NumInserted, "Number of canonical indvars added");
  69 STATISTIC(NumReplaced, "Number of exit values replaced");
  70 STATISTIC(NumLFTR    , "Number of loop exit tests replaced");
  71
  72 namespace {
  73   class IndVarSimplify : public LoopPass {
  74     IVUsers         *IU;
  75     LoopInfo        *LI;
  76     ScalarEvolution *SE;
  77     DominatorTree   *DT;
  78     const TargetData *TD;
  79     SmallVector<WeakVH, 16> DeadInsts;
  80     bool Changed;
  81   public:
  82
  83     static char ID; // Pass identification, replacement for typeid
  84     IndVarSimplify() : LoopPass(ID) {
  85       initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry());
  86     }
  87
  88     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
  89
  90     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  91       AU.addRequired<DominatorTree>();
  92       AU.addRequired<LoopInfo>();
  93       AU.addRequired<ScalarEvolution>();
  94       AU.addRequiredID(LoopSimplifyID);
  95       AU.addRequiredID(LCSSAID);
  96       AU.addRequired<IVUsers>();
  97       AU.addPreserved<ScalarEvolution>();
  98       AU.addPreservedID(LoopSimplifyID);
  99       AU.addPreservedID(LCSSAID);
 100       AU.addPreserved<IVUsers>();
 101       AU.setPreservesCFG();
 102     }
 103
 104   private:
 105     bool isValidRewrite(Value *FromVal, Value *ToVal);
 106
 107     void EliminateIVComparisons();
 108     void EliminateIVRemainders();
 109     void RewriteNonIntegerIVs(Loop *L);
 110
 111     ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
 112                                    PHINode *IndVar,
 113                                    BasicBlock *ExitingBlock,
 114                                    BranchInst *BI,
 115                                    SCEVExpander &Rewriter);
 116     void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
 117
 118     void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter);
 119
 120     void SinkUnusedInvariants(Loop *L);
 121
 122     void HandleFloatingPointIV(Loop *L, PHINode *PH);
 123   };
 124 }
 125
 126 char IndVarSimplify::ID = 0;
 127 INITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars",
 128                 "Canonicalize Induction Variables", false, false)
 129 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 130 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
 131 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 132 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 133 INITIALIZE_PASS_DEPENDENCY(LCSSA)
 134 INITIALIZE_PASS_DEPENDENCY(IVUsers)
 135 INITIALIZE_PASS_END(IndVarSimplify, "indvars",
 136                 "Canonicalize Induction Variables", false, false)
 137
 138 Pass *llvm::createIndVarSimplifyPass() {
 139   return new IndVarSimplify();
 140 }
 141
 142 /// isValidRewrite - Return true if the SCEV expansion generated by the
 143 /// rewriter can replace the original value. SCEV guarantees that it
 144 /// produces the same value, but the way it is produced may be illegal IR.
 145 /// Ideally, this function will only be called for verification.
 146 bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
 147   // If an SCEV expression subsumed multiple pointers, its expansion could
 148   // reassociate the GEP changing the base pointer. This is illegal because the
 149   // final address produced by a GEP chain must be inbounds relative to its
 150   // underlying object. Otherwise basic alias analysis, among other things,
 151   // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
 152   // producing an expression involving multiple pointers. Until then, we must
 153   // bail out here.
 154   //
 155   // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
 156   // because it understands lcssa phis while SCEV does not.
 157   Value *FromPtr = FromVal;
 158   Value *ToPtr = ToVal;
 159   if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) {
 160     FromPtr = GEP->getPointerOperand();
 161   }
 162   if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) {
 163     ToPtr = GEP->getPointerOperand();
 164   }
 165   if (FromPtr != FromVal || ToPtr != ToVal) {
 166     // Quickly check the common case
 167     if (FromPtr == ToPtr)
 168       return true;
 169
 170     // SCEV may have rewritten an expression that produces the GEP's pointer
 171     // operand. That's ok as long as the pointer operand has the same base
 172     // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
 173     // base of a recurrence. This handles the case in which SCEV expansion
 174     // converts a pointer type recurrence into a nonrecurrent pointer base
 175     // indexed by an integer recurrence.
 176     const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
 177     const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
 178     if (FromBase == ToBase)
 179       return true;
 180
 181     DEBUG(dbgs() << "INDVARS: GEP rewrite bail out "
 182           << *FromBase << " != " << *ToBase << "\n");
 183
 184     return false;
 185   }
 186   return true;
 187 }
 188
 189 /// LinearFunctionTestReplace - This method rewrites the exit condition of the
 190 /// loop to be a canonical != comparison against the incremented loop induction
 191 /// variable.  This pass is able to rewrite the exit tests of any loop where the
 192 /// SCEV analysis can determine a loop-invariant trip count of the loop, which
 193 /// is actually a much broader range than just linear tests.
 194 ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
 195                                    const SCEV *BackedgeTakenCount,
 196                                    PHINode *IndVar,
 197                                    BasicBlock *ExitingBlock,
 198                                    BranchInst *BI,
 199                                    SCEVExpander &Rewriter) {
 200   // Special case: If the backedge-taken count is a UDiv, it's very likely a
 201   // UDiv that ScalarEvolution produced in order to compute a precise
 202   // expression, rather than a UDiv from the user's code. If we can't find a
 203   // UDiv in the code with some simple searching, assume the former and forego
 204   // rewriting the loop.
 205   if (isa<SCEVUDivExpr>(BackedgeTakenCount)) {
 206     ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition());
 207     if (!OrigCond) return 0;
 208     const SCEV *R = SE->getSCEV(OrigCond->getOperand(1));
 209     R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1));
 210     if (R != BackedgeTakenCount) {
 211       const SCEV *L = SE->getSCEV(OrigCond->getOperand(0));
 212       L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1));
 213       if (L != BackedgeTakenCount)
 214         return 0;
 215     }
 216   }
 217
 218   // If the exiting block is not the same as the backedge block, we must compare
 219   // against the preincremented value, otherwise we prefer to compare against
 220   // the post-incremented value.
 221   Value *CmpIndVar;
 222   const SCEV *RHS = BackedgeTakenCount;
 223   if (ExitingBlock == L->getLoopLatch()) {
 224     // Add one to the "backedge-taken" count to get the trip count.
 225     // If this addition may overflow, we have to be more pessimistic and
 226     // cast the induction variable before doing the add.
 227     const SCEV *Zero = SE->getConstant(BackedgeTakenCount->getType(), 0);
 228     const SCEV *N =
 229       SE->getAddExpr(BackedgeTakenCount,
 230                      SE->getConstant(BackedgeTakenCount->getType(), 1));
 231     if ((isa<SCEVConstant>(N) && !N->isZero()) ||
 232         SE->isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) {
 233       // No overflow. Cast the sum.
 234       RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType());
 235     } else {
 236       // Potential overflow. Cast before doing the add.
 237       RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
 238                                         IndVar->getType());
 239       RHS = SE->getAddExpr(RHS,
 240                            SE->getConstant(IndVar->getType(), 1));
 241     }
 242
 243     // The BackedgeTaken expression contains the number of times that the
 244     // backedge branches to the loop header.  This is one less than the
 245     // number of times the loop executes, so use the incremented indvar.
 246     CmpIndVar = IndVar->getIncomingValueForBlock(ExitingBlock);
 247   } else {
 248     // We have to use the preincremented value...
 249     RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
 250                                       IndVar->getType());
 251     CmpIndVar = IndVar;
 252   }
 253
 254   // Expand the code for the iteration count.
 255   assert(SE->isLoopInvariant(RHS, L) &&
 256          "Computed iteration count is not loop invariant!");
 257   Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI);
 258
 259   // Insert a new icmp_ne or icmp_eq instruction before the branch.
 260   ICmpInst::Predicate Opcode;
 261   if (L->contains(BI->getSuccessor(0)))
 262     Opcode = ICmpInst::ICMP_NE;
 263   else
 264     Opcode = ICmpInst::ICMP_EQ;
 265
 266   DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 267                << "      LHS:" << *CmpIndVar << '\n'
 268                << "       op:\t"
 269                << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
 270                << "      RHS:\t" << *RHS << "\n");
 271
 272   ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond");
 273
 274   Value *OrigCond = BI->getCondition();
 275   // It's tempting to use replaceAllUsesWith here to fully replace the old
 276   // comparison, but that's not immediately safe, since users of the old
 277   // comparison may not be dominated by the new comparison. Instead, just
 278   // update the branch to use the new comparison; in the common case this
 279   // will make old comparison dead.
 280   BI->setCondition(Cond);
 281   RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
 282
 283   ++NumLFTR;
 284   Changed = true;
 285   return Cond;
 286 }
 287
 288 /// RewriteLoopExitValues - Check to see if this loop has a computable
 289 /// loop-invariant execution count.  If so, this means that we can compute the
 290 /// final value of any expressions that are recurrent in the loop, and
 291 /// substitute the exit values from the loop into any instructions outside of
 292 /// the loop that use the final values of the current expressions.
 293 ///
 294 /// This is mostly redundant with the regular IndVarSimplify activities that
 295 /// happen later, except that it's more powerful in some cases, because it's
 296 /// able to brute-force evaluate arbitrary instructions as long as they have
 297 /// constant operands at the beginning of the loop.
 298 void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
 299   // Verify the input to the pass in already in LCSSA form.
 300   assert(L->isLCSSAForm(*DT));
 301
 302   SmallVector<BasicBlock*, 8> ExitBlocks;
 303   L->getUniqueExitBlocks(ExitBlocks);
 304
 305   // Find all values that are computed inside the loop, but used outside of it.
 306   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
 307   // the exit blocks of the loop to find them.
 308   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 309     BasicBlock *ExitBB = ExitBlocks[i];
 310
 311     // If there are no PHI nodes in this exit block, then no values defined
 312     // inside the loop are used on this path, skip it.
 313     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
 314     if (!PN) continue;
 315
 316     unsigned NumPreds = PN->getNumIncomingValues();
 317
 318     // Iterate over all of the PHI nodes.
 319     BasicBlock::iterator BBI = ExitBB->begin();
 320     while ((PN = dyn_cast<PHINode>(BBI++))) {
 321       if (PN->use_empty())
 322         continue; // dead use, don't replace it
 323
 324       // SCEV only supports integer expressions for now.
 325       if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy())
 326         continue;
 327
 328       // It's necessary to tell ScalarEvolution about this explicitly so that
 329       // it can walk the def-use list and forget all SCEVs, as it may not be
 330       // watching the PHI itself. Once the new exit value is in place, there
 331       // may not be a def-use connection between the loop and every instruction
 332       // which got a SCEVAddRecExpr for that loop.
 333       SE->forgetValue(PN);
 334
 335       // Iterate over all of the values in all the PHI nodes.
 336       for (unsigned i = 0; i != NumPreds; ++i) {
 337         // If the value being merged in is not integer or is not defined
 338         // in the loop, skip it.
 339         Value *InVal = PN->getIncomingValue(i);
 340         if (!isa<Instruction>(InVal))
 341           continue;
 342
 343         // If this pred is for a subloop, not L itself, skip it.
 344         if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
 345           continue; // The Block is in a subloop, skip it.
 346
 347         // Check that InVal is defined in the loop.
 348         Instruction *Inst = cast<Instruction>(InVal);
 349         if (!L->contains(Inst))
 350           continue;
 351
 352         // Okay, this instruction has a user outside of the current loop
 353         // and varies predictably *inside* the loop.  Evaluate the value it
 354         // contains when the loop exits, if possible.
 355         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
 356         if (!SE->isLoopInvariant(ExitValue, L))
 357           continue;
 358
 359         Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
 360
 361         DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n'
 362                      << "  LoopVal = " << *Inst << "\n");
 363
 364         if (!isValidRewrite(Inst, ExitVal)) {
 365           DeadInsts.push_back(ExitVal);
 366           continue;
 367         }
 368         Changed = true;
 369         ++NumReplaced;
 370
 371         PN->setIncomingValue(i, ExitVal);
 372
 373         // If this instruction is dead now, delete it.
 374         RecursivelyDeleteTriviallyDeadInstructions(Inst);
 375
 376         if (NumPreds == 1) {
 377           // Completely replace a single-pred PHI. This is safe, because the
 378           // NewVal won't be variant in the loop, so we don't need an LCSSA phi
 379           // node anymore.
 380           PN->replaceAllUsesWith(ExitVal);
 381           RecursivelyDeleteTriviallyDeadInstructions(PN);
 382         }
 383       }
 384       if (NumPreds != 1) {
 385         // Clone the PHI and delete the original one. This lets IVUsers and
 386         // any other maps purge the original user from their records.
 387         PHINode *NewPN = cast<PHINode>(PN->clone());
 388         NewPN->takeName(PN);
 389         NewPN->insertBefore(PN);
 390         PN->replaceAllUsesWith(NewPN);
 391         PN->eraseFromParent();
 392       }
 393     }
 394   }
 395
 396   // The insertion point instruction may have been deleted; clear it out
 397   // so that the rewriter doesn't trip over it later.
 398   Rewriter.clearInsertPoint();
 399 }
 400
 401 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
 402   // First step.  Check to see if there are any floating-point recurrences.
 403   // If there are, change them into integer recurrences, permitting analysis by
 404   // the SCEV routines.
 405   //
 406   BasicBlock *Header = L->getHeader();
 407
 408   SmallVector<WeakVH, 8> PHIs;
 409   for (BasicBlock::iterator I = Header->begin();
 410        PHINode *PN = dyn_cast<PHINode>(I); ++I)
 411     PHIs.push_back(PN);
 412
 413   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
 414     if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i]))
 415       HandleFloatingPointIV(L, PN);
 416
 417   // If the loop previously had floating-point IV, ScalarEvolution
 418   // may not have been able to compute a trip count. Now that we've done some
 419   // re-writing, the trip count may be computable.
 420   if (Changed)
 421     SE->forgetLoop(L);
 422 }
 423
 424 void IndVarSimplify::EliminateIVComparisons() {
 425   // Look for ICmp users.
 426   for (IVUsers::iterator I = IU->begin(), E = IU->end(); I != E; ++I) {
 427     IVStrideUse &UI = *I;
 428     ICmpInst *ICmp = dyn_cast<ICmpInst>(UI.getUser());
 429     if (!ICmp) continue;
 430
 431     bool Swapped = UI.getOperandValToReplace() == ICmp->getOperand(1);
 432     ICmpInst::Predicate Pred = ICmp->getPredicate();
 433     if (Swapped) Pred = ICmpInst::getSwappedPredicate(Pred);
 434
 435     // Get the SCEVs for the ICmp operands.
 436     const SCEV *S = IU->getReplacementExpr(UI);
 437     const SCEV *X = SE->getSCEV(ICmp->getOperand(!Swapped));
 438
 439     // Simplify unnecessary loops away.
 440     const Loop *ICmpLoop = LI->getLoopFor(ICmp->getParent());
 441     S = SE->getSCEVAtScope(S, ICmpLoop);
 442     X = SE->getSCEVAtScope(X, ICmpLoop);
 443
 444     // If the condition is always true or always false, replace it with
 445     // a constant value.
 446     if (SE->isKnownPredicate(Pred, S, X))
 447       ICmp->replaceAllUsesWith(ConstantInt::getTrue(ICmp->getContext()));
 448     else if (SE->isKnownPredicate(ICmpInst::getInversePredicate(Pred), S, X))
 449       ICmp->replaceAllUsesWith(ConstantInt::getFalse(ICmp->getContext()));
 450     else
 451       continue;
 452
 453     DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp << '\n');
 454     DeadInsts.push_back(ICmp);
 455   }
 456 }
 457
 458 void IndVarSimplify::EliminateIVRemainders() {
 459   // Look for SRem and URem users.
 460   for (IVUsers::iterator I = IU->begin(), E = IU->end(); I != E; ++I) {
 461     IVStrideUse &UI = *I;
 462     BinaryOperator *Rem = dyn_cast<BinaryOperator>(UI.getUser());
 463     if (!Rem) continue;
 464
 465     bool isSigned = Rem->getOpcode() == Instruction::SRem;
 466     if (!isSigned && Rem->getOpcode() != Instruction::URem)
 467       continue;
 468
 469     // We're only interested in the case where we know something about
 470     // the numerator.
 471     if (UI.getOperandValToReplace() != Rem->getOperand(0))
 472       continue;
 473
 474     // Get the SCEVs for the ICmp operands.
 475     const SCEV *S = SE->getSCEV(Rem->getOperand(0));
 476     const SCEV *X = SE->getSCEV(Rem->getOperand(1));
 477
 478     // Simplify unnecessary loops away.
 479     const Loop *ICmpLoop = LI->getLoopFor(Rem->getParent());
 480     S = SE->getSCEVAtScope(S, ICmpLoop);
 481     X = SE->getSCEVAtScope(X, ICmpLoop);
 482
 483     // i % n  -->  i  if i is in [0,n).
 484     if ((!isSigned || SE->isKnownNonNegative(S)) &&
 485         SE->isKnownPredicate(isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 486                              S, X))
 487       Rem->replaceAllUsesWith(Rem->getOperand(0));
 488     else {
 489       // (i+1) % n  -->  (i+1)==n?0:(i+1)  if i is in [0,n).
 490       const SCEV *LessOne =
 491         SE->getMinusSCEV(S, SE->getConstant(S->getType(), 1));
 492       if ((!isSigned || SE->isKnownNonNegative(LessOne)) &&
 493           SE->isKnownPredicate(isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
 494                                LessOne, X)) {
 495         ICmpInst *ICmp = new ICmpInst(Rem, ICmpInst::ICMP_EQ,
 496                                       Rem->getOperand(0), Rem->getOperand(1),
 497                                       "tmp");
 498         SelectInst *Sel =
 499           SelectInst::Create(ICmp,
 500                              ConstantInt::get(Rem->getType(), 0),
 501                              Rem->getOperand(0), "tmp", Rem);
 502         Rem->replaceAllUsesWith(Sel);
 503       } else
 504         continue;
 505     }
 506
 507     // Inform IVUsers about the new users.
 508     if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0)))
 509       IU->AddUsersIfInteresting(I);
 510
 511     DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
 512     DeadInsts.push_back(Rem);
 513   }
 514 }
 515
 516 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
 517   // If LoopSimplify form is not available, stay out of trouble. Some notes:
 518   //  - LSR currently only supports LoopSimplify-form loops. Indvars'
 519   //    canonicalization can be a pessimization without LSR to "clean up"
 520   //    afterwards.
 521   //  - We depend on having a preheader; in particular,
 522   //    Loop::getCanonicalInductionVariable only supports loops with preheaders,
 523   //    and we're in trouble if we can't find the induction variable even when
 524   //    we've manually inserted one.
 525   if (!L->isLoopSimplifyForm())
 526     return false;
 527
 528   IU = &getAnalysis<IVUsers>();
 529   LI = &getAnalysis<LoopInfo>();
 530   SE = &getAnalysis<ScalarEvolution>();
 531   DT = &getAnalysis<DominatorTree>();
 532   TD = getAnalysisIfAvailable<TargetData>();
 533   DeadInsts.clear();
 534   Changed = false;
 535
 536   // If there are any floating-point recurrences, attempt to
 537   // transform them to use integer recurrences.
 538   RewriteNonIntegerIVs(L);
 539
 540   BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
 541   const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
 542
 543   // Create a rewriter object which we'll use to transform the code with.
 544   SCEVExpander Rewriter(*SE);
 545
 546   // Check to see if this loop has a computable loop-invariant execution count.
 547   // If so, this means that we can compute the final value of any expressions
 548   // that are recurrent in the loop, and substitute the exit values from the
 549   // loop into any instructions outside of the loop that use the final values of
 550   // the current expressions.
 551   //
 552   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
 553     RewriteLoopExitValues(L, Rewriter);
 554
 555   // Simplify ICmp IV users.
 556   EliminateIVComparisons();
 557
 558   // Simplify SRem and URem IV users.
 559   EliminateIVRemainders();
 560
 561   // Compute the type of the largest recurrence expression, and decide whether
 562   // a canonical induction variable should be inserted.
 563   const Type *LargestType = 0;
 564   bool NeedCannIV = false;
 565   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
 566     LargestType = BackedgeTakenCount->getType();
 567     LargestType = SE->getEffectiveSCEVType(LargestType);
 568     // If we have a known trip count and a single exit block, we'll be
 569     // rewriting the loop exit test condition below, which requires a
 570     // canonical induction variable.
 571     if (ExitingBlock)
 572       NeedCannIV = true;
 573   }
 574   for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) {
 575     const Type *Ty =
 576       SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType());
 577     if (!LargestType ||
 578         SE->getTypeSizeInBits(Ty) >
 579           SE->getTypeSizeInBits(LargestType))
 580       LargestType = Ty;
 581     NeedCannIV = true;
 582   }
 583
 584   // Now that we know the largest of the induction variable expressions
 585   // in this loop, insert a canonical induction variable of the largest size.
 586   PHINode *IndVar = 0;
 587   if (NeedCannIV) {
 588     // Check to see if the loop already has any canonical-looking induction
 589     // variables. If any are present and wider than the planned canonical
 590     // induction variable, temporarily remove them, so that the Rewriter
 591     // doesn't attempt to reuse them.
 592     SmallVector<PHINode *, 2> OldCannIVs;
 593     while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) {
 594       if (SE->getTypeSizeInBits(OldCannIV->getType()) >
 595           SE->getTypeSizeInBits(LargestType))
 596         OldCannIV->removeFromParent();
 597       else
 598         break;
 599       OldCannIVs.push_back(OldCannIV);
 600     }
 601
 602     IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType);
 603
 604     ++NumInserted;
 605     Changed = true;
 606     DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n');
 607
 608     // Now that the official induction variable is established, reinsert
 609     // any old canonical-looking variables after it so that the IR remains
 610     // consistent. They will be deleted as part of the dead-PHI deletion at
 611     // the end of the pass.
 612     while (!OldCannIVs.empty()) {
 613       PHINode *OldCannIV = OldCannIVs.pop_back_val();
 614       OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI());
 615     }
 616   }
 617
 618   // If we have a trip count expression, rewrite the loop's exit condition
 619   // using it.  We can currently only handle loops with a single exit.
 620   ICmpInst *NewICmp = 0;
 621   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
 622       !BackedgeTakenCount->isZero() &&
 623       ExitingBlock) {
 624     assert(NeedCannIV &&
 625            "LinearFunctionTestReplace requires a canonical induction variable");
 626     // Can't rewrite non-branch yet.
 627     if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
 628       NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
 629                                           ExitingBlock, BI, Rewriter);
 630   }
 631
 632   // Rewrite IV-derived expressions.
 633   RewriteIVExpressions(L, Rewriter);
 634
 635   // Clear the rewriter cache, because values that are in the rewriter's cache
 636   // can be deleted in the loop below, causing the AssertingVH in the cache to
 637   // trigger.
 638   Rewriter.clear();
 639
 640   // Now that we're done iterating through lists, clean up any instructions
 641   // which are now dead.
 642   while (!DeadInsts.empty())
 643     if (Instruction *Inst =
 644           dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val()))
 645       RecursivelyDeleteTriviallyDeadInstructions(Inst);
 646
 647   // The Rewriter may not be used from this point on.
 648
 649   // Loop-invariant instructions in the preheader that aren't used in the
 650   // loop may be sunk below the loop to reduce register pressure.
 651   SinkUnusedInvariants(L);
 652
 653   // For completeness, inform IVUsers of the IV use in the newly-created
 654   // loop exit test instruction.
 655   if (NewICmp)
 656     IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
 657
 658   // Clean up dead instructions.
 659   Changed |= DeleteDeadPHIs(L->getHeader());
 660   // Check a post-condition.
 661   assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!");
 662   return Changed;
 663 }
 664
 665 // FIXME: It is an extremely bad idea to indvar substitute anything more
 666 // complex than affine induction variables.  Doing so will put expensive
 667 // polynomial evaluations inside of the loop, and the str reduction pass
 668 // currently can only reduce affine polynomials.  For now just disable
 669 // indvar subst on anything more complex than an affine addrec, unless
 670 // it can be expanded to a trivial value.
 671 static bool isSafe(const SCEV *S, const Loop *L, ScalarEvolution *SE) {
 672   // Loop-invariant values are safe.
 673   if (SE->isLoopInvariant(S, L)) return true;
 674
 675   // Affine addrecs are safe. Non-affine are not, because LSR doesn't know how
 676   // to transform them into efficient code.
 677   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S))
 678     return AR->isAffine();
 679
 680   // An add is safe it all its operands are safe.
 681   if (const SCEVCommutativeExpr *Commutative = dyn_cast<SCEVCommutativeExpr>(S)) {
 682     for (SCEVCommutativeExpr::op_iterator I = Commutative->op_begin(),
 683          E = Commutative->op_end(); I != E; ++I)
 684       if (!isSafe(*I, L, SE)) return false;
 685     return true;
 686   }
 687
 688   // A cast is safe if its operand is.
 689   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(S))
 690     return isSafe(C->getOperand(), L, SE);
 691
 692   // A udiv is safe if its operands are.
 693   if (const SCEVUDivExpr *UD = dyn_cast<SCEVUDivExpr>(S))
 694     return isSafe(UD->getLHS(), L, SE) &&
 695            isSafe(UD->getRHS(), L, SE);
 696
 697   // SCEVUnknown is always safe.
 698   if (isa<SCEVUnknown>(S))
 699     return true;
 700
 701   // Nothing else is safe.
 702   return false;
 703 }
 704
 705 void IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) {
 706   // Rewrite all induction variable expressions in terms of the canonical
 707   // induction variable.
 708   //
 709   // If there were induction variables of other sizes or offsets, manually
 710   // add the offsets to the primary induction variable and cast, avoiding
 711   // the need for the code evaluation methods to insert induction variables
 712   // of different sizes.
 713   for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) {
 714     Value *Op = UI->getOperandValToReplace();
 715     const Type *UseTy = Op->getType();
 716     Instruction *User = UI->getUser();
 717
 718     // Compute the final addrec to expand into code.
 719     const SCEV *AR = IU->getReplacementExpr(*UI);
 720
 721     // Evaluate the expression out of the loop, if possible.
 722     if (!L->contains(UI->getUser())) {
 723       const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop());
 724       if (SE->isLoopInvariant(ExitVal, L))
 725         AR = ExitVal;
 726     }
 727
 728     // FIXME: It is an extremely bad idea to indvar substitute anything more
 729     // complex than affine induction variables.  Doing so will put expensive
 730     // polynomial evaluations inside of the loop, and the str reduction pass
 731     // currently can only reduce affine polynomials.  For now just disable
 732     // indvar subst on anything more complex than an affine addrec, unless
 733     // it can be expanded to a trivial value.
 734     if (!isSafe(AR, L, SE))
 735       continue;
 736
 737     // Determine the insertion point for this user. By default, insert
 738     // immediately before the user. The SCEVExpander class will automatically
 739     // hoist loop invariants out of the loop. For PHI nodes, there may be
 740     // multiple uses, so compute the nearest common dominator for the
 741     // incoming blocks.
 742     Instruction *InsertPt = User;
 743     if (PHINode *PHI = dyn_cast<PHINode>(InsertPt))
 744       for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
 745         if (PHI->getIncomingValue(i) == Op) {
 746           if (InsertPt == User)
 747             InsertPt = PHI->getIncomingBlock(i)->getTerminator();
 748           else
 749             InsertPt =
 750               DT->findNearestCommonDominator(InsertPt->getParent(),
 751                                              PHI->getIncomingBlock(i))
 752                     ->getTerminator();
 753         }
 754
 755     // Now expand it into actual Instructions and patch it into place.
 756     Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt);
 757
 758     DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n'
 759                  << "   into = " << *NewVal << "\n");
 760
 761     if (!isValidRewrite(Op, NewVal)) {
 762       DeadInsts.push_back(NewVal);
 763       continue;
 764     }
 765     // Inform ScalarEvolution that this value is changing. The change doesn't
 766     // affect its value, but it does potentially affect which use lists the
 767     // value will be on after the replacement, which affects ScalarEvolution's
 768     // ability to walk use lists and drop dangling pointers when a value is
 769     // deleted.
 770     SE->forgetValue(User);
 771
 772     // Patch the new value into place.
 773     if (Op->hasName())
 774       NewVal->takeName(Op);
 775     User->replaceUsesOfWith(Op, NewVal);
 776     UI->setOperandValToReplace(NewVal);
 777
 778     ++NumRemoved;
 779     Changed = true;
 780
 781     // The old value may be dead now.
 782     DeadInsts.push_back(Op);
 783   }
 784 }
 785
 786 /// If there's a single exit block, sink any loop-invariant values that
 787 /// were defined in the preheader but not used inside the loop into the
 788 /// exit block to reduce register pressure in the loop.
 789 void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
 790   BasicBlock *ExitBlock = L->getExitBlock();
 791   if (!ExitBlock) return;
 792
 793   BasicBlock *Preheader = L->getLoopPreheader();
 794   if (!Preheader) return;
 795
 796   Instruction *InsertPt = ExitBlock->getFirstNonPHI();
 797   BasicBlock::iterator I = Preheader->getTerminator();
 798   while (I != Preheader->begin()) {
 799     --I;
 800     // New instructions were inserted at the end of the preheader.
 801     if (isa<PHINode>(I))
 802       break;
 803
 804     // Don't move instructions which might have side effects, since the side
 805     // effects need to complete before instructions inside the loop.  Also don't
 806     // move instructions which might read memory, since the loop may modify
 807     // memory. Note that it's okay if the instruction might have undefined
 808     // behavior: LoopSimplify guarantees that the preheader dominates the exit
 809     // block.
 810     if (I->mayHaveSideEffects() || I->mayReadFromMemory())
 811       continue;
 812
 813     // Skip debug info intrinsics.
 814     if (isa<DbgInfoIntrinsic>(I))
 815       continue;
 816
 817     // Don't sink static AllocaInsts out of the entry block, which would
 818     // turn them into dynamic allocas!
 819     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 820       if (AI->isStaticAlloca())
 821         continue;
 822
 823     // Determine if there is a use in or before the loop (direct or
 824     // otherwise).
 825     bool UsedInLoop = false;
 826     for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 827          UI != UE; ++UI) {
 828       User *U = *UI;
 829       BasicBlock *UseBB = cast<Instruction>(U)->getParent();
 830       if (PHINode *P = dyn_cast<PHINode>(U)) {
 831         unsigned i =
 832           PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
 833         UseBB = P->getIncomingBlock(i);
 834       }
 835       if (UseBB == Preheader || L->contains(UseBB)) {
 836         UsedInLoop = true;
 837         break;
 838       }
 839     }
 840
 841     // If there is, the def must remain in the preheader.
 842     if (UsedInLoop)
 843       continue;
 844
 845     // Otherwise, sink it to the exit block.
 846     Instruction *ToMove = I;
 847     bool Done = false;
 848
 849     if (I != Preheader->begin()) {
 850       // Skip debug info intrinsics.
 851       do {
 852         --I;
 853       } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
 854
 855       if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
 856         Done = true;
 857     } else {
 858       Done = true;
 859     }
 860
 861     ToMove->moveBefore(InsertPt);
 862     if (Done) break;
 863     InsertPt = ToMove;
 864   }
 865 }
 866
 867 /// ConvertToSInt - Convert APF to an integer, if possible.
 868 static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
 869   bool isExact = false;
 870   if (&APF.getSemantics() == &APFloat::PPCDoubleDouble)
 871     return false;
 872   // See if we can convert this to an int64_t
 873   uint64_t UIntVal;
 874   if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero,
 875                            &isExact) != APFloat::opOK || !isExact)
 876     return false;
 877   IntVal = UIntVal;
 878   return true;
 879 }
 880
 881 /// HandleFloatingPointIV - If the loop has floating induction variable
 882 /// then insert corresponding integer induction variable if possible.
 883 /// For example,
 884 /// for(double i = 0; i < 10000; ++i)
 885 ///   bar(i)
 886 /// is converted into
 887 /// for(int i = 0; i < 10000; ++i)
 888 ///   bar((double)i);
 889 ///
 890 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) {
 891   unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
 892   unsigned BackEdge     = IncomingEdge^1;
 893
 894   // Check incoming value.
 895   ConstantFP *InitValueVal =
 896     dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge));
 897
 898   int64_t InitValue;
 899   if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
 900     return;
 901
 902   // Check IV increment. Reject this PN if increment operation is not
 903   // an add or increment value can not be represented by an integer.
 904   BinaryOperator *Incr =
 905     dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge));
 906   if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return;
 907
 908   // If this is not an add of the PHI with a constantfp, or if the constant fp
 909   // is not an integer, bail out.
 910   ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
 911   int64_t IncValue;
 912   if (IncValueVal == 0 || Incr->getOperand(0) != PN ||
 913       !ConvertToSInt(IncValueVal->getValueAPF(), IncValue))
 914     return;
 915
 916   // Check Incr uses. One user is PN and the other user is an exit condition
 917   // used by the conditional terminator.
 918   Value::use_iterator IncrUse = Incr->use_begin();
 919   Instruction *U1 = cast<Instruction>(*IncrUse++);
 920   if (IncrUse == Incr->use_end()) return;
 921   Instruction *U2 = cast<Instruction>(*IncrUse++);
 922   if (IncrUse != Incr->use_end()) return;
 923
 924   // Find exit condition, which is an fcmp.  If it doesn't exist, or if it isn't
 925   // only used by a branch, we can't transform it.
 926   FCmpInst *Compare = dyn_cast<FCmpInst>(U1);
 927   if (!Compare)
 928     Compare = dyn_cast<FCmpInst>(U2);
 929   if (Compare == 0 || !Compare->hasOneUse() ||
 930       !isa<BranchInst>(Compare->use_back()))
 931     return;
 932
 933   BranchInst *TheBr = cast<BranchInst>(Compare->use_back());
 934
 935   // We need to verify that the branch actually controls the iteration count
 936   // of the loop.  If not, the new IV can overflow and no one will notice.
 937   // The branch block must be in the loop and one of the successors must be out
 938   // of the loop.
 939   assert(TheBr->isConditional() && "Can't use fcmp if not conditional");
 940   if (!L->contains(TheBr->getParent()) ||
 941       (L->contains(TheBr->getSuccessor(0)) &&
 942        L->contains(TheBr->getSuccessor(1))))
 943     return;
 944
 945
 946   // If it isn't a comparison with an integer-as-fp (the exit value), we can't
 947   // transform it.
 948   ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));
 949   int64_t ExitValue;
 950   if (ExitValueVal == 0 ||
 951       !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue))
 952     return;
 953
 954   // Find new predicate for integer comparison.
 955   CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
 956   switch (Compare->getPredicate()) {
 957   default: return;  // Unknown comparison.
 958   case CmpInst::FCMP_OEQ:
 959   case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break;
 960   case CmpInst::FCMP_ONE:
 961   case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break;
 962   case CmpInst::FCMP_OGT:
 963   case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break;
 964   case CmpInst::FCMP_OGE:
 965   case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break;
 966   case CmpInst::FCMP_OLT:
 967   case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break;
 968   case CmpInst::FCMP_OLE:
 969   case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break;
 970   }
 971
 972   // We convert the floating point induction variable to a signed i32 value if
 973   // we can.  This is only safe if the comparison will not overflow in a way
 974   // that won't be trapped by the integer equivalent operations.  Check for this
 975   // now.
 976   // TODO: We could use i64 if it is native and the range requires it.
 977
 978   // The start/stride/exit values must all fit in signed i32.
 979   if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
 980     return;
 981
 982   // If not actually striding (add x, 0.0), avoid touching the code.
 983   if (IncValue == 0)
 984     return;
 985
 986   // Positive and negative strides have different safety conditions.
 987   if (IncValue > 0) {
 988     // If we have a positive stride, we require the init to be less than the
 989     // exit value and an equality or less than comparison.
 990     if (InitValue >= ExitValue ||
 991         NewPred == CmpInst::ICMP_SGT || NewPred == CmpInst::ICMP_SGE)
 992       return;
 993
 994     uint32_t Range = uint32_t(ExitValue-InitValue);
 995     if (NewPred == CmpInst::ICMP_SLE) {
 996       // Normalize SLE -> SLT, check for infinite loop.
 997       if (++Range == 0) return;  // Range overflows.
 998     }
 999
1000     unsigned Leftover = Range % uint32_t(IncValue);
1001
1002     // If this is an equality comparison, we require that the strided value
1003     // exactly land on the exit value, otherwise the IV condition will wrap
1004     // around and do things the fp IV wouldn't.
1005     if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
1006         Leftover != 0)
1007       return;
1008
1009     // If the stride would wrap around the i32 before exiting, we can't
1010     // transform the IV.
1011     if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
1012       return;
1013
1014   } else {
1015     // If we have a negative stride, we require the init to be greater than the
1016     // exit value and an equality or greater than comparison.
1017     if (InitValue >= ExitValue ||
1018         NewPred == CmpInst::ICMP_SLT || NewPred == CmpInst::ICMP_SLE)
1019       return;
1020
1021     uint32_t Range = uint32_t(InitValue-ExitValue);
1022     if (NewPred == CmpInst::ICMP_SGE) {
1023       // Normalize SGE -> SGT, check for infinite loop.
1024       if (++Range == 0) return;  // Range overflows.
1025     }
1026
1027     unsigned Leftover = Range % uint32_t(-IncValue);
1028
1029     // If this is an equality comparison, we require that the strided value
1030     // exactly land on the exit value, otherwise the IV condition will wrap
1031     // around and do things the fp IV wouldn't.
1032     if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
1033         Leftover != 0)
1034       return;
1035
1036     // If the stride would wrap around the i32 before exiting, we can't
1037     // transform the IV.
1038     if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
1039       return;
1040   }
1041
1042   const IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext());
1043
1044   // Insert new integer induction variable.
1045   PHINode *NewPHI = PHINode::Create(Int32Ty, PN->getName()+".int", PN);
1046   NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue),
1047                       PN->getIncomingBlock(IncomingEdge));
1048
1049   Value *NewAdd =
1050     BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue),
1051                               Incr->getName()+".int", Incr);
1052   NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge));
1053
1054   ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd,
1055                                       ConstantInt::get(Int32Ty, ExitValue),
1056                                       Compare->getName());
1057
1058   // In the following deletions, PN may become dead and may be deleted.
1059   // Use a WeakVH to observe whether this happens.
1060   WeakVH WeakPH = PN;
1061
1062   // Delete the old floating point exit comparison.  The branch starts using the
1063   // new comparison.
1064   NewCompare->takeName(Compare);
1065   Compare->replaceAllUsesWith(NewCompare);
1066   RecursivelyDeleteTriviallyDeadInstructions(Compare);
1067
1068   // Delete the old floating point increment.
1069   Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
1070   RecursivelyDeleteTriviallyDeadInstructions(Incr);
1071
1072   // If the FP induction variable still has uses, this is because something else
1073   // in the loop uses its value.  In order to canonicalize the induction
1074   // variable, we chose to eliminate the IV and rewrite it in terms of an
1075   // int->fp cast.
1076   //
1077   // We give preference to sitofp over uitofp because it is faster on most
1078   // platforms.
1079   if (WeakPH) {
1080     Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",
1081                                  PN->getParent()->getFirstNonPHI());
1082     PN->replaceAllUsesWith(Conv);
1083     RecursivelyDeleteTriviallyDeadInstructions(PN);
1084   }
1085
1086   // Add a new IVUsers entry for the newly-created integer PHI.
1087   IU->AddUsersIfInteresting(NewPHI);
1088 }