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