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