IndVarSimplify.cpp revision 87a10f5b2fc26e418a7bde45136843aac4c7a7e6
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 // Patch the new value into place. 514 if (Op->hasName()) 515 NewVal->takeName(Op); 516 User->replaceUsesOfWith(Op, NewVal); 517 UI->setOperandValToReplace(NewVal); 518 DEBUG(dbgs() << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 519 << " into = " << *NewVal << "\n"); 520 ++NumRemoved; 521 Changed = true; 522 523 // The old value may be dead now. 524 DeadInsts.push_back(Op); 525 } 526 527 // Clear the rewriter cache, because values that are in the rewriter's cache 528 // can be deleted in the loop below, causing the AssertingVH in the cache to 529 // trigger. 530 Rewriter.clear(); 531 // Now that we're done iterating through lists, clean up any instructions 532 // which are now dead. 533 while (!DeadInsts.empty()) 534 if (Instruction *Inst = 535 dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val())) 536 RecursivelyDeleteTriviallyDeadInstructions(Inst); 537} 538 539/// If there's a single exit block, sink any loop-invariant values that 540/// were defined in the preheader but not used inside the loop into the 541/// exit block to reduce register pressure in the loop. 542void IndVarSimplify::SinkUnusedInvariants(Loop *L) { 543 BasicBlock *ExitBlock = L->getExitBlock(); 544 if (!ExitBlock) return; 545 546 BasicBlock *Preheader = L->getLoopPreheader(); 547 if (!Preheader) return; 548 549 Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 550 BasicBlock::iterator I = Preheader->getTerminator(); 551 while (I != Preheader->begin()) { 552 --I; 553 // New instructions were inserted at the end of the preheader. 554 if (isa<PHINode>(I)) 555 break; 556 557 // Don't move instructions which might have side effects, since the side 558 // effects need to complete before instructions inside the loop. Also don't 559 // move instructions which might read memory, since the loop may modify 560 // memory. Note that it's okay if the instruction might have undefined 561 // behavior: LoopSimplify guarantees that the preheader dominates the exit 562 // block. 563 if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 564 continue; 565 566 // Skip debug info intrinsics. 567 if (isa<DbgInfoIntrinsic>(I)) 568 continue; 569 570 // Don't sink static AllocaInsts out of the entry block, which would 571 // turn them into dynamic allocas! 572 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 573 if (AI->isStaticAlloca()) 574 continue; 575 576 // Determine if there is a use in or before the loop (direct or 577 // otherwise). 578 bool UsedInLoop = false; 579 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 580 UI != UE; ++UI) { 581 BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 582 if (PHINode *P = dyn_cast<PHINode>(UI)) { 583 unsigned i = 584 PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 585 UseBB = P->getIncomingBlock(i); 586 } 587 if (UseBB == Preheader || L->contains(UseBB)) { 588 UsedInLoop = true; 589 break; 590 } 591 } 592 593 // If there is, the def must remain in the preheader. 594 if (UsedInLoop) 595 continue; 596 597 // Otherwise, sink it to the exit block. 598 Instruction *ToMove = I; 599 bool Done = false; 600 601 if (I != Preheader->begin()) { 602 // Skip debug info intrinsics. 603 do { 604 --I; 605 } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 606 607 if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 608 Done = true; 609 } else { 610 Done = true; 611 } 612 613 ToMove->moveBefore(InsertPt); 614 if (Done) break; 615 InsertPt = ToMove; 616 } 617} 618 619/// Return true if it is OK to use SIToFPInst for an induction variable 620/// with given initial and exit values. 621static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 622 uint64_t intIV, uint64_t intEV) { 623 624 if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 625 return true; 626 627 // If the iteration range can be handled by SIToFPInst then use it. 628 APInt Max = APInt::getSignedMaxValue(32); 629 if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 630 return true; 631 632 return false; 633} 634 635/// convertToInt - Convert APF to an integer, if possible. 636static bool convertToInt(const APFloat &APF, uint64_t *intVal) { 637 638 bool isExact = false; 639 if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 640 return false; 641 if (APF.convertToInteger(intVal, 32, APF.isNegative(), 642 APFloat::rmTowardZero, &isExact) 643 != APFloat::opOK) 644 return false; 645 if (!isExact) 646 return false; 647 return true; 648 649} 650 651/// HandleFloatingPointIV - If the loop has floating induction variable 652/// then insert corresponding integer induction variable if possible. 653/// For example, 654/// for(double i = 0; i < 10000; ++i) 655/// bar(i) 656/// is converted into 657/// for(int i = 0; i < 10000; ++i) 658/// bar((double)i); 659/// 660void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 661 662 unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 663 unsigned BackEdge = IncomingEdge^1; 664 665 // Check incoming value. 666 ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 667 if (!InitValue) return; 668 uint64_t newInitValue = 669 Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 670 if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 671 return; 672 673 // Check IV increment. Reject this PH if increment operation is not 674 // an add or increment value can not be represented by an integer. 675 BinaryOperator *Incr = 676 dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 677 if (!Incr) return; 678 if (Incr->getOpcode() != Instruction::FAdd) return; 679 ConstantFP *IncrValue = NULL; 680 unsigned IncrVIndex = 1; 681 if (Incr->getOperand(1) == PH) 682 IncrVIndex = 0; 683 IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 684 if (!IncrValue) return; 685 uint64_t newIncrValue = 686 Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 687 if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 688 return; 689 690 // Check Incr uses. One user is PH and the other users is exit condition used 691 // by the conditional terminator. 692 Value::use_iterator IncrUse = Incr->use_begin(); 693 Instruction *U1 = cast<Instruction>(IncrUse++); 694 if (IncrUse == Incr->use_end()) return; 695 Instruction *U2 = cast<Instruction>(IncrUse++); 696 if (IncrUse != Incr->use_end()) return; 697 698 // Find exit condition. 699 FCmpInst *EC = dyn_cast<FCmpInst>(U1); 700 if (!EC) 701 EC = dyn_cast<FCmpInst>(U2); 702 if (!EC) return; 703 704 if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 705 if (!BI->isConditional()) return; 706 if (BI->getCondition() != EC) return; 707 } 708 709 // Find exit value. If exit value can not be represented as an integer then 710 // do not handle this floating point PH. 711 ConstantFP *EV = NULL; 712 unsigned EVIndex = 1; 713 if (EC->getOperand(1) == Incr) 714 EVIndex = 0; 715 EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 716 if (!EV) return; 717 uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 718 if (!convertToInt(EV->getValueAPF(), &intEV)) 719 return; 720 721 // Find new predicate for integer comparison. 722 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 723 switch (EC->getPredicate()) { 724 case CmpInst::FCMP_OEQ: 725 case CmpInst::FCMP_UEQ: 726 NewPred = CmpInst::ICMP_EQ; 727 break; 728 case CmpInst::FCMP_OGT: 729 case CmpInst::FCMP_UGT: 730 NewPred = CmpInst::ICMP_UGT; 731 break; 732 case CmpInst::FCMP_OGE: 733 case CmpInst::FCMP_UGE: 734 NewPred = CmpInst::ICMP_UGE; 735 break; 736 case CmpInst::FCMP_OLT: 737 case CmpInst::FCMP_ULT: 738 NewPred = CmpInst::ICMP_ULT; 739 break; 740 case CmpInst::FCMP_OLE: 741 case CmpInst::FCMP_ULE: 742 NewPred = CmpInst::ICMP_ULE; 743 break; 744 default: 745 break; 746 } 747 if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 748 749 // Insert new integer induction variable. 750 PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()), 751 PH->getName()+".int", PH); 752 NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()), 753 newInitValue), 754 PH->getIncomingBlock(IncomingEdge)); 755 756 Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 757 ConstantInt::get(Type::getInt32Ty(PH->getContext()), 758 newIncrValue), 759 Incr->getName()+".int", Incr); 760 NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 761 762 // The back edge is edge 1 of newPHI, whatever it may have been in the 763 // original PHI. 764 ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()), 765 intEV); 766 Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV); 767 Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1)); 768 ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(), 769 NewPred, LHS, RHS, EC->getName()); 770 771 // In the following deletions, PH may become dead and may be deleted. 772 // Use a WeakVH to observe whether this happens. 773 WeakVH WeakPH = PH; 774 775 // Delete old, floating point, exit comparison instruction. 776 NewEC->takeName(EC); 777 EC->replaceAllUsesWith(NewEC); 778 RecursivelyDeleteTriviallyDeadInstructions(EC); 779 780 // Delete old, floating point, increment instruction. 781 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 782 RecursivelyDeleteTriviallyDeadInstructions(Incr); 783 784 // Replace floating induction variable, if it isn't already deleted. 785 // Give SIToFPInst preference over UIToFPInst because it is faster on 786 // platforms that are widely used. 787 if (WeakPH && !PH->use_empty()) { 788 if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 789 SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 790 PH->getParent()->getFirstNonPHI()); 791 PH->replaceAllUsesWith(Conv); 792 } else { 793 UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 794 PH->getParent()->getFirstNonPHI()); 795 PH->replaceAllUsesWith(Conv); 796 } 797 RecursivelyDeleteTriviallyDeadInstructions(PH); 798 } 799 800 // Add a new IVUsers entry for the newly-created integer PHI. 801 IU->AddUsersIfInteresting(NewPHI); 802} 803