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