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