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