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