lib/Transforms/Scalar/IndVarSimplify.cpp

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