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/LLVMContext.h"
  47 #include "llvm/Type.h"
  48 #include "llvm/Analysis/Dominators.h"
  49 #include "llvm/Analysis/IVUsers.h"
  50 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  51 #include "llvm/Analysis/LoopInfo.h"
  52 #include "llvm/Analysis/LoopPass.h"
  53 #include "llvm/Support/CFG.h"
  54 #include "llvm/Support/CommandLine.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/ADT/SmallVector.h"
  60 #include "llvm/ADT/Statistic.h"
  61 #include "llvm/ADT/STLExtras.h"
  62 using namespace llvm;
  63
  64 STATISTIC(NumRemoved , "Number of aux indvars removed");
  65 STATISTIC(NumInserted, "Number of canonical indvars added");
  66 STATISTIC(NumReplaced, "Number of exit values replaced");
  67 STATISTIC(NumLFTR    , "Number of loop exit tests replaced");
  68
  69 namespace {
  70   class IndVarSimplify : public LoopPass {
  71     IVUsers         *IU;
  72     LoopInfo        *LI;
  73     ScalarEvolution *SE;
  74     DominatorTree   *DT;
  75     bool Changed;
  76   public:
  77
  78     static char ID; // Pass identification, replacement for typeid
  79     IndVarSimplify() : LoopPass(&ID) {}
  80
  81     virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
  82
  83     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  84       AU.addRequired<DominatorTree>();
  85       AU.addRequired<LoopInfo>();
  86       AU.addRequired<ScalarEvolution>();
  87       AU.addRequiredID(LoopSimplifyID);
  88       AU.addRequiredID(LCSSAID);
  89       AU.addRequired<IVUsers>();
  90       AU.addPreserved<ScalarEvolution>();
  91       AU.addPreservedID(LoopSimplifyID);
  92       AU.addPreservedID(LCSSAID);
  93       AU.addPreserved<IVUsers>();
  94       AU.setPreservesCFG();
  95     }
  96
  97   private:
  98
  99     void RewriteNonIntegerIVs(Loop *L);
 100
 101     ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
 102                                    Value *IndVar,
 103                                    BasicBlock *ExitingBlock,
 104                                    BranchInst *BI,
 105                                    SCEVExpander &Rewriter);
 106     void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount,
 107                                SCEVExpander &Rewriter);
 108
 109     void RewriteIVExpressions(Loop *L, const Type *LargestType,
 110                               SCEVExpander &Rewriter);
 111
 112     void SinkUnusedInvariants(Loop *L);
 113
 114     void HandleFloatingPointIV(Loop *L, PHINode *PH);
 115   };
 116 }
 117
 118 char IndVarSimplify::ID = 0;
 119 static RegisterPass<IndVarSimplify>
 120 X("indvars", "Canonicalize Induction Variables");
 121
 122 Pass *llvm::createIndVarSimplifyPass() {
 123   return new IndVarSimplify();
 124 }
 125
 126 /// LinearFunctionTestReplace - This method rewrites the exit condition of the
 127 /// loop to be a canonical != comparison against the incremented loop induction
 128 /// variable.  This pass is able to rewrite the exit tests of any loop where the
 129 /// SCEV analysis can determine a loop-invariant trip count of the loop, which
 130 /// is actually a much broader range than just linear tests.
 131 ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
 132                                    const SCEV *BackedgeTakenCount,
 133                                    Value *IndVar,
 134                                    BasicBlock *ExitingBlock,
 135                                    BranchInst *BI,
 136                                    SCEVExpander &Rewriter) {
 137   // If the exiting block is not the same as the backedge block, we must compare
 138   // against the preincremented value, otherwise we prefer to compare against
 139   // the post-incremented value.
 140   Value *CmpIndVar;
 141   const SCEV *RHS = BackedgeTakenCount;
 142   if (ExitingBlock == L->getLoopLatch()) {
 143     // Add one to the "backedge-taken" count to get the trip count.
 144     // If this addition may overflow, we have to be more pessimistic and
 145     // cast the induction variable before doing the add.
 146     const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
 147     const SCEV *N =
 148       SE->getAddExpr(BackedgeTakenCount,
 149                      SE->getIntegerSCEV(1, BackedgeTakenCount->getType()));
 150     if ((isa<SCEVConstant>(N) && !N->isZero()) ||
 151         SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) {
 152       // No overflow. Cast the sum.
 153       RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType());
 154     } else {
 155       // Potential overflow. Cast before doing the add.
 156       RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
 157                                         IndVar->getType());
 158       RHS = SE->getAddExpr(RHS,
 159                            SE->getIntegerSCEV(1, IndVar->getType()));
 160     }
 161
 162     // The BackedgeTaken expression contains the number of times that the
 163     // backedge branches to the loop header.  This is one less than the
 164     // number of times the loop executes, so use the incremented indvar.
 165     CmpIndVar = L->getCanonicalInductionVariableIncrement();
 166   } else {
 167     // We have to use the preincremented value...
 168     RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
 169                                       IndVar->getType());
 170     CmpIndVar = IndVar;
 171   }
 172
 173   // Expand the code for the iteration count.
 174   assert(RHS->isLoopInvariant(L) &&
 175          "Computed iteration count is not loop invariant!");
 176   Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI);
 177
 178   // Insert a new icmp_ne or icmp_eq instruction before the branch.
 179   ICmpInst::Predicate Opcode;
 180   if (L->contains(BI->getSuccessor(0)))
 181     Opcode = ICmpInst::ICMP_NE;
 182   else
 183     Opcode = ICmpInst::ICMP_EQ;
 184
 185   DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
 186                << "      LHS:" << *CmpIndVar << '\n'
 187                << "       op:\t"
 188                << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
 189                << "      RHS:\t" << *RHS << "\n");
 190
 191   ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond");
 192
 193   Instruction *OrigCond = cast<Instruction>(BI->getCondition());
 194   // It's tempting to use replaceAllUsesWith here to fully replace the old
 195   // comparison, but that's not immediately safe, since users of the old
 196   // comparison may not be dominated by the new comparison. Instead, just
 197   // update the branch to use the new comparison; in the common case this
 198   // will make old comparison dead.
 199   BI->setCondition(Cond);
 200   RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
 201
 202   ++NumLFTR;
 203   Changed = true;
 204   return Cond;
 205 }
 206
 207 /// RewriteLoopExitValues - Check to see if this loop has a computable
 208 /// loop-invariant execution count.  If so, this means that we can compute the
 209 /// final value of any expressions that are recurrent in the loop, and
 210 /// substitute the exit values from the loop into any instructions outside of
 211 /// the loop that use the final values of the current expressions.
 212 ///
 213 /// This is mostly redundant with the regular IndVarSimplify activities that
 214 /// happen later, except that it's more powerful in some cases, because it's
 215 /// able to brute-force evaluate arbitrary instructions as long as they have
 216 /// constant operands at the beginning of the loop.
 217 void IndVarSimplify::RewriteLoopExitValues(Loop *L,
 218                                            const SCEV *BackedgeTakenCount,
 219                                            SCEVExpander &Rewriter) {
 220   // Verify the input to the pass in already in LCSSA form.
 221   assert(L->isLCSSAForm());
 222
 223   SmallVector<BasicBlock*, 8> ExitBlocks;
 224   L->getUniqueExitBlocks(ExitBlocks);
 225
 226   // Find all values that are computed inside the loop, but used outside of it.
 227   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
 228   // the exit blocks of the loop to find them.
 229   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
 230     BasicBlock *ExitBB = ExitBlocks[i];
 231
 232     // If there are no PHI nodes in this exit block, then no values defined
 233     // inside the loop are used on this path, skip it.
 234     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
 235     if (!PN) continue;
 236
 237     unsigned NumPreds = PN->getNumIncomingValues();
 238
 239     // Iterate over all of the PHI nodes.
 240     BasicBlock::iterator BBI = ExitBB->begin();
 241     while ((PN = dyn_cast<PHINode>(BBI++))) {
 242       if (PN->use_empty())
 243         continue; // dead use, don't replace it
 244       // Iterate over all of the values in all the PHI nodes.
 245       for (unsigned i = 0; i != NumPreds; ++i) {
 246         // If the value being merged in is not integer or is not defined
 247         // in the loop, skip it.
 248         Value *InVal = PN->getIncomingValue(i);
 249         if (!isa<Instruction>(InVal) ||
 250             // SCEV only supports integer expressions for now.
 251             (!isa<IntegerType>(InVal->getType()) &&
 252              !isa<PointerType>(InVal->getType())))
 253           continue;
 254
 255         // If this pred is for a subloop, not L itself, skip it.
 256         if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
 257           continue; // The Block is in a subloop, skip it.
 258
 259         // Check that InVal is defined in the loop.
 260         Instruction *Inst = cast<Instruction>(InVal);
 261         if (!L->contains(Inst))
 262           continue;
 263
 264         // Okay, this instruction has a user outside of the current loop
 265         // and varies predictably *inside* the loop.  Evaluate the value it
 266         // contains when the loop exits, if possible.
 267         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
 268         if (!ExitValue->isLoopInvariant(L))
 269           continue;
 270
 271         Changed = true;
 272         ++NumReplaced;
 273
 274         Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst);
 275
 276         DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n'
 277                      << "  LoopVal = " << *Inst << "\n");
 278
 279         PN->setIncomingValue(i, ExitVal);
 280
 281         // If this instruction is dead now, delete it.
 282         RecursivelyDeleteTriviallyDeadInstructions(Inst);
 283
 284         if (NumPreds == 1) {
 285           // Completely replace a single-pred PHI. This is safe, because the
 286           // NewVal won't be variant in the loop, so we don't need an LCSSA phi
 287           // node anymore.
 288           PN->replaceAllUsesWith(ExitVal);
 289           RecursivelyDeleteTriviallyDeadInstructions(PN);
 290         }
 291       }
 292       if (NumPreds != 1) {
 293         // Clone the PHI and delete the original one. This lets IVUsers and
 294         // any other maps purge the original user from their records.
 295         PHINode *NewPN = cast<PHINode>(PN->clone());
 296         NewPN->takeName(PN);
 297         NewPN->insertBefore(PN);
 298         PN->replaceAllUsesWith(NewPN);
 299         PN->eraseFromParent();
 300       }
 301     }
 302   }
 303 }
 304
 305 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
 306   // First step.  Check to see if there are any floating-point recurrences.
 307   // If there are, change them into integer recurrences, permitting analysis by
 308   // the SCEV routines.
 309   //
 310   BasicBlock *Header    = L->getHeader();
 311
 312   SmallVector<WeakVH, 8> PHIs;
 313   for (BasicBlock::iterator I = Header->begin();
 314        PHINode *PN = dyn_cast<PHINode>(I); ++I)
 315     PHIs.push_back(PN);
 316
 317   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
 318     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
 319       HandleFloatingPointIV(L, PN);
 320
 321   // If the loop previously had floating-point IV, ScalarEvolution
 322   // may not have been able to compute a trip count. Now that we've done some
 323   // re-writing, the trip count may be computable.
 324   if (Changed)
 325     SE->forgetLoop(L);
 326 }
 327
 328 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
 329   IU = &getAnalysis<IVUsers>();
 330   LI = &getAnalysis<LoopInfo>();
 331   SE = &getAnalysis<ScalarEvolution>();
 332   DT = &getAnalysis<DominatorTree>();
 333   Changed = false;
 334
 335   // If there are any floating-point recurrences, attempt to
 336   // transform them to use integer recurrences.
 337   RewriteNonIntegerIVs(L);
 338
 339   BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
 340   const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
 341
 342   // Create a rewriter object which we'll use to transform the code with.
 343   SCEVExpander Rewriter(*SE);
 344
 345   // Check to see if this loop has a computable loop-invariant execution count.
 346   // If so, this means that we can compute the final value of any expressions
 347   // that are recurrent in the loop, and substitute the exit values from the
 348   // loop into any instructions outside of the loop that use the final values of
 349   // the current expressions.
 350   //
 351   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
 352     RewriteLoopExitValues(L, BackedgeTakenCount, Rewriter);
 353
 354   // Compute the type of the largest recurrence expression, and decide whether
 355   // a canonical induction variable should be inserted.
 356   const Type *LargestType = 0;
 357   bool NeedCannIV = false;
 358   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
 359     LargestType = BackedgeTakenCount->getType();
 360     LargestType = SE->getEffectiveSCEVType(LargestType);
 361     // If we have a known trip count and a single exit block, we'll be
 362     // rewriting the loop exit test condition below, which requires a
 363     // canonical induction variable.
 364     if (ExitingBlock)
 365       NeedCannIV = true;
 366   }
 367   for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
 368     const SCEV *Stride = IU->StrideOrder[i];
 369     const Type *Ty = SE->getEffectiveSCEVType(Stride->getType());
 370     if (!LargestType ||
 371         SE->getTypeSizeInBits(Ty) >
 372           SE->getTypeSizeInBits(LargestType))
 373       LargestType = Ty;
 374
 375     std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI =
 376       IU->IVUsesByStride.find(IU->StrideOrder[i]);
 377     assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
 378
 379     if (!SI->second->Users.empty())
 380       NeedCannIV = true;
 381   }
 382
 383   // Now that we know the largest of of the induction variable expressions
 384   // in this loop, insert a canonical induction variable of the largest size.
 385   Value *IndVar = 0;
 386   if (NeedCannIV) {
 387     // Check to see if the loop already has a canonical-looking induction
 388     // variable. If one is present and it's wider than the planned canonical
 389     // induction variable, temporarily remove it, so that the Rewriter
 390     // doesn't attempt to reuse it.
 391     PHINode *OldCannIV = L->getCanonicalInductionVariable();
 392     if (OldCannIV) {
 393       if (SE->getTypeSizeInBits(OldCannIV->getType()) >
 394           SE->getTypeSizeInBits(LargestType))
 395         OldCannIV->removeFromParent();
 396       else
 397         OldCannIV = 0;
 398     }
 399
 400     IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType);
 401
 402     ++NumInserted;
 403     Changed = true;
 404     DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n');
 405
 406     // Now that the official induction variable is established, reinsert
 407     // the old canonical-looking variable after it so that the IR remains
 408     // consistent. It will be deleted as part of the dead-PHI deletion at
 409     // the end of the pass.
 410     if (OldCannIV)
 411       OldCannIV->insertAfter(cast<Instruction>(IndVar));
 412   }
 413
 414   // If we have a trip count expression, rewrite the loop's exit condition
 415   // using it.  We can currently only handle loops with a single exit.
 416   ICmpInst *NewICmp = 0;
 417   if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) {
 418     assert(NeedCannIV &&
 419            "LinearFunctionTestReplace requires a canonical induction variable");
 420     // Can't rewrite non-branch yet.
 421     if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
 422       NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
 423                                           ExitingBlock, BI, Rewriter);
 424   }
 425
 426   // Rewrite IV-derived expressions. Clears the rewriter cache.
 427   RewriteIVExpressions(L, LargestType, Rewriter);
 428
 429   // The Rewriter may not be used from this point on.
 430
 431   // Loop-invariant instructions in the preheader that aren't used in the
 432   // loop may be sunk below the loop to reduce register pressure.
 433   SinkUnusedInvariants(L);
 434
 435   // For completeness, inform IVUsers of the IV use in the newly-created
 436   // loop exit test instruction.
 437   if (NewICmp)
 438     IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
 439
 440   // Clean up dead instructions.
 441   Changed |= DeleteDeadPHIs(L->getHeader());
 442   // Check a post-condition.
 443   assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
 444   return Changed;
 445 }
 446
 447 void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
 448                                           SCEVExpander &Rewriter) {
 449   SmallVector<WeakVH, 16> DeadInsts;
 450
 451   // Rewrite all induction variable expressions in terms of the canonical
 452   // induction variable.
 453   //
 454   // If there were induction variables of other sizes or offsets, manually
 455   // add the offsets to the primary induction variable and cast, avoiding
 456   // the need for the code evaluation methods to insert induction variables
 457   // of different sizes.
 458   for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
 459     const SCEV *Stride = IU->StrideOrder[i];
 460
 461     std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI =
 462       IU->IVUsesByStride.find(IU->StrideOrder[i]);
 463     assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
 464     ilist<IVStrideUse> &List = SI->second->Users;
 465     for (ilist<IVStrideUse>::iterator UI = List.begin(),
 466          E = List.end(); UI != E; ++UI) {
 467       Value *Op = UI->getOperandValToReplace();
 468       const Type *UseTy = Op->getType();
 469       Instruction *User = UI->getUser();
 470
 471       // Compute the final addrec to expand into code.
 472       const SCEV *AR = IU->getReplacementExpr(*UI);
 473
 474       // Evaluate the expression out of the loop, if possible.
 475       if (!L->contains(UI->getUser())) {
 476         const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop());
 477         if (ExitVal->isLoopInvariant(L))
 478           AR = ExitVal;
 479       }
 480
 481       // FIXME: It is an extremely bad idea to indvar substitute anything more
 482       // complex than affine induction variables.  Doing so will put expensive
 483       // polynomial evaluations inside of the loop, and the str reduction pass
 484       // currently can only reduce affine polynomials.  For now just disable
 485       // indvar subst on anything more complex than an affine addrec, unless
 486       // it can be expanded to a trivial value.
 487       if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L))
 488         continue;
 489
 490       // Determine the insertion point for this user. By default, insert
 491       // immediately before the user. The SCEVExpander class will automatically
 492       // hoist loop invariants out of the loop. For PHI nodes, there may be
 493       // multiple uses, so compute the nearest common dominator for the
 494       // incoming blocks.
 495       Instruction *InsertPt = User;
 496       if (PHINode *PHI = dyn_cast<PHINode>(InsertPt))
 497         for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i)
 498           if (PHI->getIncomingValue(i) == Op) {
 499             if (InsertPt == User)
 500               InsertPt = PHI->getIncomingBlock(i)->getTerminator();
 501             else
 502               InsertPt =
 503                 DT->findNearestCommonDominator(InsertPt->getParent(),
 504                                                PHI->getIncomingBlock(i))
 505                       ->getTerminator();
 506           }
 507
 508       // Now expand it into actual Instructions and patch it into place.
 509       Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt);
 510
 511       // Patch the new value into place.
 512       if (Op->hasName())
 513         NewVal->takeName(Op);
 514       User->replaceUsesOfWith(Op, NewVal);
 515       UI->setOperandValToReplace(NewVal);
 516       DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n'
 517                    << "   into = " << *NewVal << "\n");
 518       ++NumRemoved;
 519       Changed = true;
 520
 521       // The old value may be dead now.
 522       DeadInsts.push_back(Op);
 523     }
 524   }
 525
 526   // Clear the rewriter cache, because values that are in the rewriter's cache
 527   // can be deleted in the loop below, causing the AssertingVH in the cache to
 528   // trigger.
 529   Rewriter.clear();
 530   // Now that we're done iterating through lists, clean up any instructions
 531   // which are now dead.
 532   while (!DeadInsts.empty())
 533     if (Instruction *Inst =
 534           dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
 535       RecursivelyDeleteTriviallyDeadInstructions(Inst);
 536 }
 537
 538 /// If there's a single exit block, sink any loop-invariant values that
 539 /// were defined in the preheader but not used inside the loop into the
 540 /// exit block to reduce register pressure in the loop.
 541 void IndVarSimplify::SinkUnusedInvariants(Loop *L) {
 542   BasicBlock *ExitBlock = L->getExitBlock();
 543   if (!ExitBlock) return;
 544
 545   BasicBlock *Preheader = L->getLoopPreheader();
 546   if (!Preheader) return;
 547
 548   Instruction *InsertPt = ExitBlock->getFirstNonPHI();
 549   BasicBlock::iterator I = Preheader->getTerminator();
 550   while (I != Preheader->begin()) {
 551     --I;
 552     // New instructions were inserted at the end of the preheader.
 553     if (isa<PHINode>(I))
 554       break;
 555     // Don't move instructions which might have side effects, since the side
 556     // effects need to complete before instructions inside the loop.  Also
 557     // don't move instructions which might read memory, since the loop may
 558     // modify memory. Note that it's okay if the instruction might have
 559     // undefined behavior: LoopSimplify guarantees that the preheader
 560     // dominates the exit block.
 561     if (I->mayHaveSideEffects() || I->mayReadFromMemory())
 562       continue;
 563     // Don't sink static AllocaInsts out of the entry block, which would
 564     // turn them into dynamic allocas!
 565     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 566       if (AI->isStaticAlloca())
 567         continue;
 568     // Determine if there is a use in or before the loop (direct or
 569     // otherwise).
 570     bool UsedInLoop = false;
 571     for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 572          UI != UE; ++UI) {
 573       BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
 574       if (PHINode *P = dyn_cast<PHINode>(UI)) {
 575         unsigned i =
 576           PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
 577         UseBB = P->getIncomingBlock(i);
 578       }
 579       if (UseBB == Preheader || L->contains(UseBB)) {
 580         UsedInLoop = true;
 581         break;
 582       }
 583     }
 584     // If there is, the def must remain in the preheader.
 585     if (UsedInLoop)
 586       continue;
 587     // Otherwise, sink it to the exit block.
 588     Instruction *ToMove = I;
 589     bool Done = false;
 590     if (I != Preheader->begin())
 591       --I;
 592     else
 593       Done = true;
 594     ToMove->moveBefore(InsertPt);
 595     if (Done)
 596       break;
 597     InsertPt = ToMove;
 598   }
 599 }
 600
 601 /// Return true if it is OK to use SIToFPInst for an inducation variable
 602 /// with given inital and exit values.
 603 static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV,
 604                           uint64_t intIV, uint64_t intEV) {
 605
 606   if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative())
 607     return true;
 608
 609   // If the iteration range can be handled by SIToFPInst then use it.
 610   APInt Max = APInt::getSignedMaxValue(32);
 611   if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV)))
 612     return true;
 613
 614   return false;
 615 }
 616
 617 /// convertToInt - Convert APF to an integer, if possible.
 618 static bool convertToInt(const APFloat &APF, uint64_t *intVal) {
 619
 620   bool isExact = false;
 621   if (&APF.getSemantics() == &APFloat::PPCDoubleDouble)
 622     return false;
 623   if (APF.convertToInteger(intVal, 32, APF.isNegative(),
 624                            APFloat::rmTowardZero, &isExact)
 625       != APFloat::opOK)
 626     return false;
 627   if (!isExact)
 628     return false;
 629   return true;
 630
 631 }
 632
 633 /// HandleFloatingPointIV - If the loop has floating induction variable
 634 /// then insert corresponding integer induction variable if possible.
 635 /// For example,
 636 /// for(double i = 0; i < 10000; ++i)
 637 ///   bar(i)
 638 /// is converted into
 639 /// for(int i = 0; i < 10000; ++i)
 640 ///   bar((double)i);
 641 ///
 642 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
 643
 644   unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
 645   unsigned BackEdge     = IncomingEdge^1;
 646
 647   // Check incoming value.
 648   ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge));
 649   if (!InitValue) return;
 650   uint64_t newInitValue =
 651               Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
 652   if (!convertToInt(InitValue->getValueAPF(), &newInitValue))
 653     return;
 654
 655   // Check IV increment. Reject this PH if increement operation is not
 656   // an add or increment value can not be represented by an integer.
 657   BinaryOperator *Incr =
 658     dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge));
 659   if (!Incr) return;
 660   if (Incr->getOpcode() != Instruction::FAdd) return;
 661   ConstantFP *IncrValue = NULL;
 662   unsigned IncrVIndex = 1;
 663   if (Incr->getOperand(1) == PH)
 664     IncrVIndex = 0;
 665   IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex));
 666   if (!IncrValue) return;
 667   uint64_t newIncrValue =
 668               Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
 669   if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue))
 670     return;
 671
 672   // Check Incr uses. One user is PH and the other users is exit condition used
 673   // by the conditional terminator.
 674   Value::use_iterator IncrUse = Incr->use_begin();
 675   Instruction *U1 = cast<Instruction>(IncrUse++);
 676   if (IncrUse == Incr->use_end()) return;
 677   Instruction *U2 = cast<Instruction>(IncrUse++);
 678   if (IncrUse != Incr->use_end()) return;
 679
 680   // Find exit condition.
 681   FCmpInst *EC = dyn_cast<FCmpInst>(U1);
 682   if (!EC)
 683     EC = dyn_cast<FCmpInst>(U2);
 684   if (!EC) return;
 685
 686   if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) {
 687     if (!BI->isConditional()) return;
 688     if (BI->getCondition() != EC) return;
 689   }
 690
 691   // Find exit value. If exit value can not be represented as an interger then
 692   // do not handle this floating point PH.
 693   ConstantFP *EV = NULL;
 694   unsigned EVIndex = 1;
 695   if (EC->getOperand(1) == Incr)
 696     EVIndex = 0;
 697   EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex));
 698   if (!EV) return;
 699   uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits();
 700   if (!convertToInt(EV->getValueAPF(), &intEV))
 701     return;
 702
 703   // Find new predicate for integer comparison.
 704   CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
 705   switch (EC->getPredicate()) {
 706   case CmpInst::FCMP_OEQ:
 707   case CmpInst::FCMP_UEQ:
 708     NewPred = CmpInst::ICMP_EQ;
 709     break;
 710   case CmpInst::FCMP_OGT:
 711   case CmpInst::FCMP_UGT:
 712     NewPred = CmpInst::ICMP_UGT;
 713     break;
 714   case CmpInst::FCMP_OGE:
 715   case CmpInst::FCMP_UGE:
 716     NewPred = CmpInst::ICMP_UGE;
 717     break;
 718   case CmpInst::FCMP_OLT:
 719   case CmpInst::FCMP_ULT:
 720     NewPred = CmpInst::ICMP_ULT;
 721     break;
 722   case CmpInst::FCMP_OLE:
 723   case CmpInst::FCMP_ULE:
 724     NewPred = CmpInst::ICMP_ULE;
 725     break;
 726   default:
 727     break;
 728   }
 729   if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return;
 730
 731   // Insert new integer induction variable.
 732   PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()),
 733                                     PH->getName()+".int", PH);
 734   NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()),
 735                                        newInitValue),
 736                       PH->getIncomingBlock(IncomingEdge));
 737
 738   Value *NewAdd = BinaryOperator::CreateAdd(NewPHI,
 739                            ConstantInt::get(Type::getInt32Ty(PH->getContext()),
 740                                                              newIncrValue),
 741                                             Incr->getName()+".int", Incr);
 742   NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge));
 743
 744   // The back edge is edge 1 of newPHI, whatever it may have been in the
 745   // original PHI.
 746   ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()),
 747                                         intEV);
 748   Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV);
 749   Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1));
 750   ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(),
 751                                  NewPred, LHS, RHS, EC->getName());
 752
 753   // In the following deltions, PH may become dead and may be deleted.
 754   // Use a WeakVH to observe whether this happens.
 755   WeakVH WeakPH = PH;
 756
 757   // Delete old, floating point, exit comparision instruction.
 758   NewEC->takeName(EC);
 759   EC->replaceAllUsesWith(NewEC);
 760   RecursivelyDeleteTriviallyDeadInstructions(EC);
 761
 762   // Delete old, floating point, increment instruction.
 763   Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
 764   RecursivelyDeleteTriviallyDeadInstructions(Incr);
 765
 766   // Replace floating induction variable, if it isn't already deleted.
 767   // Give SIToFPInst preference over UIToFPInst because it is faster on
 768   // platforms that are widely used.
 769   if (WeakPH && !PH->use_empty()) {
 770     if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
 771       SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
 772                                         PH->getParent()->getFirstNonPHI());
 773       PH->replaceAllUsesWith(Conv);
 774     } else {
 775       UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
 776                                         PH->getParent()->getFirstNonPHI());
 777       PH->replaceAllUsesWith(Conv);
 778     }
 779     RecursivelyDeleteTriviallyDeadInstructions(PH);
 780   }
 781
 782   // Add a new IVUsers entry for the newly-created integer PHI.
 783   IU->AddUsersIfInteresting(NewPHI);
 784 }