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