IndVarSimplify.cpp revision ca703bd56ba1f717b3735c6889334c319ca005b1
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 RewriteNonIntegerIVs(Loop *L); 101 102 ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 103 Value *IndVar, 104 BasicBlock *ExitingBlock, 105 BranchInst *BI, 106 SCEVExpander &Rewriter); 107 void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 108 109 void RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter); 110 111 void SinkUnusedInvariants(Loop *L); 112 113 void HandleFloatingPointIV(Loop *L, PHINode *PH); 114 }; 115} 116 117char IndVarSimplify::ID = 0; 118static RegisterPass<IndVarSimplify> 119X("indvars", "Canonicalize Induction Variables"); 120 121Pass *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. 130ICmpInst *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. 173 assert(RHS->isLoopInvariant(L) && 174 "Computed iteration count is not loop invariant!"); 175 Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); 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 DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 185 << " LHS:" << *CmpIndVar << '\n' 186 << " op:\t" 187 << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 188 << " RHS:\t" << *RHS << "\n"); 189 190 ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond"); 191 192 Value *OrigCond = 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. 216void IndVarSimplify::RewriteLoopExitValues(Loop *L, 217 SCEVExpander &Rewriter) { 218 // Verify the input to the pass in already in LCSSA form. 219 assert(L->isLCSSAForm(*DT)); 220 221 SmallVector<BasicBlock*, 8> ExitBlocks; 222 L->getUniqueExitBlocks(ExitBlocks); 223 224 // Find all values that are computed inside the loop, but used outside of it. 225 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 226 // the exit blocks of the loop to find them. 227 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 228 BasicBlock *ExitBB = ExitBlocks[i]; 229 230 // If there are no PHI nodes in this exit block, then no values defined 231 // inside the loop are used on this path, skip it. 232 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 233 if (!PN) continue; 234 235 unsigned NumPreds = PN->getNumIncomingValues(); 236 237 // Iterate over all of the PHI nodes. 238 BasicBlock::iterator BBI = ExitBB->begin(); 239 while ((PN = dyn_cast<PHINode>(BBI++))) { 240 if (PN->use_empty()) 241 continue; // dead use, don't replace it 242 243 // SCEV only supports integer expressions for now. 244 if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 245 continue; 246 247 // It's necessary to tell ScalarEvolution about this explicitly so that 248 // it can walk the def-use list and forget all SCEVs, as it may not be 249 // watching the PHI itself. Once the new exit value is in place, there 250 // may not be a def-use connection between the loop and every instruction 251 // which got a SCEVAddRecExpr for that loop. 252 SE->forgetValue(PN); 253 254 // Iterate over all of the values in all the PHI nodes. 255 for (unsigned i = 0; i != NumPreds; ++i) { 256 // If the value being merged in is not integer or is not defined 257 // in the loop, skip it. 258 Value *InVal = PN->getIncomingValue(i); 259 if (!isa<Instruction>(InVal)) 260 continue; 261 262 // If this pred is for a subloop, not L itself, skip it. 263 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 264 continue; // The Block is in a subloop, skip it. 265 266 // Check that InVal is defined in the loop. 267 Instruction *Inst = cast<Instruction>(InVal); 268 if (!L->contains(Inst)) 269 continue; 270 271 // Okay, this instruction has a user outside of the current loop 272 // and varies predictably *inside* the loop. Evaluate the value it 273 // contains when the loop exits, if possible. 274 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 275 if (!ExitValue->isLoopInvariant(L)) 276 continue; 277 278 Changed = true; 279 ++NumReplaced; 280 281 Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 282 283 DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 284 << " LoopVal = " << *Inst << "\n"); 285 286 PN->setIncomingValue(i, ExitVal); 287 288 // If this instruction is dead now, delete it. 289 RecursivelyDeleteTriviallyDeadInstructions(Inst); 290 291 if (NumPreds == 1) { 292 // Completely replace a single-pred PHI. This is safe, because the 293 // NewVal won't be variant in the loop, so we don't need an LCSSA phi 294 // node anymore. 295 PN->replaceAllUsesWith(ExitVal); 296 RecursivelyDeleteTriviallyDeadInstructions(PN); 297 } 298 } 299 if (NumPreds != 1) { 300 // Clone the PHI and delete the original one. This lets IVUsers and 301 // any other maps purge the original user from their records. 302 PHINode *NewPN = cast<PHINode>(PN->clone()); 303 NewPN->takeName(PN); 304 NewPN->insertBefore(PN); 305 PN->replaceAllUsesWith(NewPN); 306 PN->eraseFromParent(); 307 } 308 } 309 } 310 311 // The insertion point instruction may have been deleted; clear it out 312 // so that the rewriter doesn't trip over it later. 313 Rewriter.clearInsertPoint(); 314} 315 316void 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->forgetLoop(L); 337} 338 339bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 340 IU = &getAnalysis<IVUsers>(); 341 LI = &getAnalysis<LoopInfo>(); 342 SE = &getAnalysis<ScalarEvolution>(); 343 DT = &getAnalysis<DominatorTree>(); 344 Changed = false; 345 346 // If there are any floating-point recurrences, attempt to 347 // transform them to use integer recurrences. 348 RewriteNonIntegerIVs(L); 349 350 BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 351 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 352 353 // Create a rewriter object which we'll use to transform the code with. 354 SCEVExpander Rewriter(*SE); 355 356 // Check to see if this loop has a computable loop-invariant execution count. 357 // If so, this means that we can compute the final value of any expressions 358 // that are recurrent in the loop, and substitute the exit values from the 359 // loop into any instructions outside of the loop that use the final values of 360 // the current expressions. 361 // 362 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 363 RewriteLoopExitValues(L, Rewriter); 364 365 // Compute the type of the largest recurrence expression, and decide whether 366 // a canonical induction variable should be inserted. 367 const Type *LargestType = 0; 368 bool NeedCannIV = false; 369 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 370 LargestType = BackedgeTakenCount->getType(); 371 LargestType = SE->getEffectiveSCEVType(LargestType); 372 // If we have a known trip count and a single exit block, we'll be 373 // rewriting the loop exit test condition below, which requires a 374 // canonical induction variable. 375 if (ExitingBlock) 376 NeedCannIV = true; 377 } 378 for (IVUsers::const_iterator I = IU->begin(), E = IU->end(); I != E; ++I) { 379 const Type *Ty = 380 SE->getEffectiveSCEVType(I->getOperandValToReplace()->getType()); 381 if (!LargestType || 382 SE->getTypeSizeInBits(Ty) > 383 SE->getTypeSizeInBits(LargestType)) 384 LargestType = Ty; 385 NeedCannIV = true; 386 } 387 388 // Now that we know the largest of the induction variable expressions 389 // in this loop, insert a canonical induction variable of the largest size. 390 Value *IndVar = 0; 391 if (NeedCannIV) { 392 // Check to see if the loop already has any canonical-looking induction 393 // variables. If any are present and wider than the planned canonical 394 // induction variable, temporarily remove them, so that the Rewriter 395 // doesn't attempt to reuse them. 396 SmallVector<PHINode *, 2> OldCannIVs; 397 while (PHINode *OldCannIV = L->getCanonicalInductionVariable()) { 398 if (SE->getTypeSizeInBits(OldCannIV->getType()) > 399 SE->getTypeSizeInBits(LargestType)) 400 OldCannIV->removeFromParent(); 401 else 402 break; 403 OldCannIVs.push_back(OldCannIV); 404 } 405 406 IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 407 408 ++NumInserted; 409 Changed = true; 410 DEBUG(dbgs() << "INDVARS: New CanIV: " << *IndVar << '\n'); 411 412 // Now that the official induction variable is established, reinsert 413 // any old canonical-looking variables after it so that the IR remains 414 // consistent. They will be deleted as part of the dead-PHI deletion at 415 // the end of the pass. 416 while (!OldCannIVs.empty()) { 417 PHINode *OldCannIV = OldCannIVs.pop_back_val(); 418 OldCannIV->insertBefore(L->getHeader()->getFirstNonPHI()); 419 } 420 } 421 422 // If we have a trip count expression, rewrite the loop's exit condition 423 // using it. We can currently only handle loops with a single exit. 424 ICmpInst *NewICmp = 0; 425 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && 426 !BackedgeTakenCount->isZero() && 427 ExitingBlock) { 428 assert(NeedCannIV && 429 "LinearFunctionTestReplace requires a canonical induction variable"); 430 // Can't rewrite non-branch yet. 431 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 432 NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 433 ExitingBlock, BI, Rewriter); 434 } 435 436 // Rewrite IV-derived expressions. Clears the rewriter cache. 437 RewriteIVExpressions(L, Rewriter); 438 439 // The Rewriter may not be used from this point on. 440 441 // Loop-invariant instructions in the preheader that aren't used in the 442 // loop may be sunk below the loop to reduce register pressure. 443 SinkUnusedInvariants(L); 444 445 // For completeness, inform IVUsers of the IV use in the newly-created 446 // loop exit test instruction. 447 if (NewICmp) 448 IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 449 450 // Clean up dead instructions. 451 Changed |= DeleteDeadPHIs(L->getHeader()); 452 // Check a post-condition. 453 assert(L->isLCSSAForm(*DT) && "Indvars did not leave the loop in lcssa form!"); 454 return Changed; 455} 456 457void IndVarSimplify::RewriteIVExpressions(Loop *L, SCEVExpander &Rewriter) { 458 SmallVector<WeakVH, 16> DeadInsts; 459 460 // Rewrite all induction variable expressions in terms of the canonical 461 // induction variable. 462 // 463 // If there were induction variables of other sizes or offsets, manually 464 // add the offsets to the primary induction variable and cast, avoiding 465 // the need for the code evaluation methods to insert induction variables 466 // of different sizes. 467 for (IVUsers::iterator UI = IU->begin(), E = IU->end(); UI != E; ++UI) { 468 const SCEV *Stride = UI->getStride(); 469 Value *Op = UI->getOperandValToReplace(); 470 const Type *UseTy = Op->getType(); 471 Instruction *User = UI->getUser(); 472 473 // Compute the final addrec to expand into code. 474 const SCEV *AR = IU->getReplacementExpr(*UI); 475 476 // Evaluate the expression out of the loop, if possible. 477 if (!L->contains(UI->getUser())) { 478 const SCEV *ExitVal = SE->getSCEVAtScope(AR, L->getParentLoop()); 479 if (ExitVal->isLoopInvariant(L)) 480 AR = ExitVal; 481 } 482 483 // FIXME: It is an extremely bad idea to indvar substitute anything more 484 // complex than affine induction variables. Doing so will put expensive 485 // polynomial evaluations inside of the loop, and the str reduction pass 486 // currently can only reduce affine polynomials. For now just disable 487 // indvar subst on anything more complex than an affine addrec, unless 488 // it can be expanded to a trivial value. 489 if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L)) 490 continue; 491 492 // Determine the insertion point for this user. By default, insert 493 // immediately before the user. The SCEVExpander class will automatically 494 // hoist loop invariants out of the loop. For PHI nodes, there may be 495 // multiple uses, so compute the nearest common dominator for the 496 // incoming blocks. 497 Instruction *InsertPt = User; 498 if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 499 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 500 if (PHI->getIncomingValue(i) == Op) { 501 if (InsertPt == User) 502 InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 503 else 504 InsertPt = 505 DT->findNearestCommonDominator(InsertPt->getParent(), 506 PHI->getIncomingBlock(i)) 507 ->getTerminator(); 508 } 509 510 // Now expand it into actual Instructions and patch it into place. 511 Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 512 513 // Inform ScalarEvolution that this value is changing. The change doesn't 514 // affect its value, but it does potentially affect which use lists the 515 // value will be on after the replacement, which affects ScalarEvolution's 516 // ability to walk use lists and drop dangling pointers when a value is 517 // deleted. 518 SE->forgetValue(User); 519 520 // Patch the new value into place. 521 if (Op->hasName()) 522 NewVal->takeName(Op); 523 User->replaceUsesOfWith(Op, NewVal); 524 UI->setOperandValToReplace(NewVal); 525 DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 526 << " into = " << *NewVal << "\n"); 527 ++NumRemoved; 528 Changed = true; 529 530 // The old value may be dead now. 531 DeadInsts.push_back(Op); 532 } 533 534 // Clear the rewriter cache, because values that are in the rewriter's cache 535 // can be deleted in the loop below, causing the AssertingVH in the cache to 536 // trigger. 537 Rewriter.clear(); 538 // Now that we're done iterating through lists, clean up any instructions 539 // which are now dead. 540 while (!DeadInsts.empty()) 541 if (Instruction *Inst = 542 dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val())) 543 RecursivelyDeleteTriviallyDeadInstructions(Inst); 544} 545 546/// If there's a single exit block, sink any loop-invariant values that 547/// were defined in the preheader but not used inside the loop into the 548/// exit block to reduce register pressure in the loop. 549void IndVarSimplify::SinkUnusedInvariants(Loop *L) { 550 BasicBlock *ExitBlock = L->getExitBlock(); 551 if (!ExitBlock) return; 552 553 BasicBlock *Preheader = L->getLoopPreheader(); 554 if (!Preheader) return; 555 556 Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 557 BasicBlock::iterator I = Preheader->getTerminator(); 558 while (I != Preheader->begin()) { 559 --I; 560 // New instructions were inserted at the end of the preheader. 561 if (isa<PHINode>(I)) 562 break; 563 564 // Don't move instructions which might have side effects, since the side 565 // effects need to complete before instructions inside the loop. Also don't 566 // move instructions which might read memory, since the loop may modify 567 // memory. Note that it's okay if the instruction might have undefined 568 // behavior: LoopSimplify guarantees that the preheader dominates the exit 569 // block. 570 if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 571 continue; 572 573 // Skip debug info intrinsics. 574 if (isa<DbgInfoIntrinsic>(I)) 575 continue; 576 577 // Don't sink static AllocaInsts out of the entry block, which would 578 // turn them into dynamic allocas! 579 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 580 if (AI->isStaticAlloca()) 581 continue; 582 583 // Determine if there is a use in or before the loop (direct or 584 // otherwise). 585 bool UsedInLoop = false; 586 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 587 UI != UE; ++UI) { 588 BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 589 if (PHINode *P = dyn_cast<PHINode>(UI)) { 590 unsigned i = 591 PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 592 UseBB = P->getIncomingBlock(i); 593 } 594 if (UseBB == Preheader || L->contains(UseBB)) { 595 UsedInLoop = true; 596 break; 597 } 598 } 599 600 // If there is, the def must remain in the preheader. 601 if (UsedInLoop) 602 continue; 603 604 // Otherwise, sink it to the exit block. 605 Instruction *ToMove = I; 606 bool Done = false; 607 608 if (I != Preheader->begin()) { 609 // Skip debug info intrinsics. 610 do { 611 --I; 612 } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 613 614 if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 615 Done = true; 616 } else { 617 Done = true; 618 } 619 620 ToMove->moveBefore(InsertPt); 621 if (Done) break; 622 InsertPt = ToMove; 623 } 624} 625 626/// Return true if it is OK to use SIToFPInst for an induction variable 627/// with given initial and exit values. 628static bool CanUseSIToFP(ConstantFP *InitV, ConstantFP *ExitV, 629 uint64_t intIV, uint64_t intEV) { 630 631 if (InitV->getValueAPF().isNegative() || ExitV->getValueAPF().isNegative()) 632 return true; 633 634 // If the iteration range can be handled by SIToFPInst then use it. 635 APInt Max = APInt::getSignedMaxValue(32); 636 if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 637 return true; 638 639 return false; 640} 641 642/// convertToInt - Convert APF to an integer, if possible. 643static bool convertToInt(const APFloat &APF, uint64_t &intVal) { 644 bool isExact = false; 645 if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 646 return false; 647 if (APF.convertToInteger(&intVal, 32, APF.isNegative(), 648 APFloat::rmTowardZero, &isExact) != APFloat::opOK) 649 return false; 650 if (!isExact) 651 return false; 652 return true; 653} 654 655/// HandleFloatingPointIV - If the loop has floating induction variable 656/// then insert corresponding integer induction variable if possible. 657/// For example, 658/// for(double i = 0; i < 10000; ++i) 659/// bar(i) 660/// is converted into 661/// for(int i = 0; i < 10000; ++i) 662/// bar((double)i); 663/// 664void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 665 unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 666 unsigned BackEdge = IncomingEdge^1; 667 668 // Check incoming value. 669 ConstantFP *InitValueVal = 670 dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 671 if (!InitValueVal) return; 672 673 uint64_t InitValue; 674 if (!convertToInt(InitValueVal->getValueAPF(), InitValue)) 675 return; 676 677 // Check IV increment. Reject this PH if increment operation is not 678 // an add or increment value can not be represented by an integer. 679 BinaryOperator *Incr = 680 dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 681 if (Incr == 0 || Incr->getOpcode() != Instruction::FAdd) return; 682 683 // If this is not an add of the PHI with a constantfp, or if the constant fp 684 // is not an integer, bail out. 685 ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 686 uint64_t IntValue; 687 if (IncValueVal == 0 || Incr->getOperand(0) != PH || 688 !convertToInt(IncValueVal->getValueAPF(), IntValue)) 689 return; 690 691 // Check Incr uses. One user is PH and the other user is an exit condition 692 // used by the conditional terminator. 693 Value::use_iterator IncrUse = Incr->use_begin(); 694 Instruction *U1 = cast<Instruction>(IncrUse++); 695 if (IncrUse == Incr->use_end()) return; 696 Instruction *U2 = cast<Instruction>(IncrUse++); 697 if (IncrUse != Incr->use_end()) return; 698 699 // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 700 // only used by a branch, we can't transform it. 701 FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 702 if (!Compare) 703 Compare = dyn_cast<FCmpInst>(U2); 704 if (Compare == 0 || !Compare->hasOneUse() || 705 !isa<BranchInst>(Compare->use_back())) 706 return; 707 708 BranchInst *TheBr = cast<BranchInst>(Compare->use_back()); 709 710 // If it isn't a comparison with an integer-as-fp (the exit value), we can't 711 // transform it. 712 ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 713 uint64_t ExitValue; 714 if (ExitValueVal == 0 || !convertToInt(ExitValueVal->getValueAPF(),ExitValue)) 715 return; 716 717 // Find new predicate for integer comparison. 718 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 719 switch (Compare->getPredicate()) { 720 default: return; // Unknown comparison. 721 case CmpInst::FCMP_OEQ: 722 case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 723 case CmpInst::FCMP_OGT: 724 case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_UGT; break; 725 case CmpInst::FCMP_OGE: 726 case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_UGE; break; 727 case CmpInst::FCMP_OLT: 728 case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_ULT; break; 729 case CmpInst::FCMP_OLE: 730 case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_ULE; break; 731 } 732 733 const IntegerType *Int32Ty = Type::getInt32Ty(PH->getContext()); 734 735 // Insert new i32 integer induction variable. 736 PHINode *NewPHI = PHINode::Create(Int32Ty, PH->getName()+".int", PH); 737 NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 738 PH->getIncomingBlock(IncomingEdge)); 739 740 Value *NewAdd = 741 BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IntValue), 742 Incr->getName()+".int", Incr); 743 NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 744 745 ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 746 ConstantInt::get(Int32Ty, ExitValue), 747 Compare->getName()); 748 749 // In the following deletions, PH may become dead and may be deleted. 750 // Use a WeakVH to observe whether this happens. 751 WeakVH WeakPH = PH; 752 753 // Delete the old floating point exit comparison. The branch starts using the 754 // new comparison. 755 NewCompare->takeName(Compare); 756 Compare->replaceAllUsesWith(NewCompare); 757 RecursivelyDeleteTriviallyDeadInstructions(Compare); 758 759 // Delete the old floating point increment. 760 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 761 RecursivelyDeleteTriviallyDeadInstructions(Incr); 762 763 // Replace floating induction variable, if it isn't already deleted. 764 // Give SIToFPInst preference over UIToFPInst because it is faster on 765 // platforms that are widely used. 766 if (WeakPH && !PH->use_empty()) { 767 if (CanUseSIToFP(InitValueVal, ExitValueVal, InitValue, ExitValue)) { 768 SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 769 PH->getParent()->getFirstNonPHI()); 770 PH->replaceAllUsesWith(Conv); 771 } else { 772 UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 773 PH->getParent()->getFirstNonPHI()); 774 PH->replaceAllUsesWith(Conv); 775 } 776 RecursivelyDeleteTriviallyDeadInstructions(PH); 777 } 778 779 // Add a new IVUsers entry for the newly-created integer PHI. 780 IU->AddUsersIfInteresting(NewPHI); 781} 782