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