lib/Transforms/Scalar/IndVarSimplify.cpp

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