IndVarSimplify.cpp revision 9c159499675228990ffa5a169914ce30a455442f
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. Any pointer arithmetic recurrences are raised to use array subscripts. 21// 22// If the trip count of a loop is computable, this pass also makes the following 23// changes: 24// 1. The exit condition for the loop is canonicalized to compare the 25// induction value against the exit value. This turns loops like: 26// 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 27// 2. Any use outside of the loop of an expression derived from the indvar 28// is changed to compute the derived value outside of the loop, eliminating 29// the dependence on the exit value of the induction variable. If the only 30// purpose of the loop is to compute the exit value of some derived 31// expression, this transformation will make the loop dead. 32// 33// This transformation should be followed by strength reduction after all of the 34// desired loop transformations have been performed. Additionally, on targets 35// where it is profitable, the loop could be transformed to count down to zero 36// (the "do loop" optimization). 37// 38//===----------------------------------------------------------------------===// 39 40#define DEBUG_TYPE "indvars" 41#include "llvm/Transforms/Scalar.h" 42#include "llvm/BasicBlock.h" 43#include "llvm/Constants.h" 44#include "llvm/Instructions.h" 45#include "llvm/Type.h" 46#include "llvm/Analysis/ScalarEvolutionExpander.h" 47#include "llvm/Analysis/LoopInfo.h" 48#include "llvm/Analysis/LoopPass.h" 49#include "llvm/Support/CFG.h" 50#include "llvm/Support/Compiler.h" 51#include "llvm/Support/Debug.h" 52#include "llvm/Support/GetElementPtrTypeIterator.h" 53#include "llvm/Transforms/Utils/Local.h" 54#include "llvm/Support/CommandLine.h" 55#include "llvm/ADT/SmallVector.h" 56#include "llvm/ADT/SetVector.h" 57#include "llvm/ADT/SmallPtrSet.h" 58#include "llvm/ADT/Statistic.h" 59using namespace llvm; 60 61STATISTIC(NumRemoved , "Number of aux indvars removed"); 62STATISTIC(NumInserted, "Number of canonical indvars added"); 63STATISTIC(NumReplaced, "Number of exit values replaced"); 64STATISTIC(NumLFTR , "Number of loop exit tests replaced"); 65 66namespace { 67 class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { 68 LoopInfo *LI; 69 ScalarEvolution *SE; 70 bool Changed; 71 public: 72 73 static char ID; // Pass identification, replacement for typeid 74 IndVarSimplify() : LoopPass(&ID) {} 75 76 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 77 78 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 79 AU.addRequired<ScalarEvolution>(); 80 AU.addRequiredID(LCSSAID); 81 AU.addRequiredID(LoopSimplifyID); 82 AU.addRequired<LoopInfo>(); 83 AU.addPreserved<ScalarEvolution>(); 84 AU.addPreservedID(LoopSimplifyID); 85 AU.addPreservedID(LCSSAID); 86 AU.setPreservesCFG(); 87 } 88 89 private: 90 91 void RewriteNonIntegerIVs(Loop *L); 92 93 void LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount, 94 Value *IndVar, 95 BasicBlock *ExitingBlock, 96 BranchInst *BI, 97 SCEVExpander &Rewriter); 98 void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount); 99 100 void DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts); 101 102 void HandleFloatingPointIV(Loop *L, PHINode *PH, 103 SmallPtrSet<Instruction*, 16> &DeadInsts); 104 }; 105} 106 107char IndVarSimplify::ID = 0; 108static RegisterPass<IndVarSimplify> 109X("indvars", "Canonicalize Induction Variables"); 110 111Pass *llvm::createIndVarSimplifyPass() { 112 return new IndVarSimplify(); 113} 114 115/// DeleteTriviallyDeadInstructions - If any of the instructions is the 116/// specified set are trivially dead, delete them and see if this makes any of 117/// their operands subsequently dead. 118void IndVarSimplify:: 119DeleteTriviallyDeadInstructions(SmallPtrSet<Instruction*, 16> &Insts) { 120 while (!Insts.empty()) { 121 Instruction *I = *Insts.begin(); 122 Insts.erase(I); 123 if (isInstructionTriviallyDead(I)) { 124 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 125 if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 126 Insts.insert(U); 127 SE->deleteValueFromRecords(I); 128 DOUT << "INDVARS: Deleting: " << *I; 129 I->eraseFromParent(); 130 Changed = true; 131 } 132 } 133} 134 135/// LinearFunctionTestReplace - This method rewrites the exit condition of the 136/// loop to be a canonical != comparison against the incremented loop induction 137/// variable. This pass is able to rewrite the exit tests of any loop where the 138/// SCEV analysis can determine a loop-invariant trip count of the loop, which 139/// is actually a much broader range than just linear tests. 140void IndVarSimplify::LinearFunctionTestReplace(Loop *L, 141 SCEVHandle BackedgeTakenCount, 142 Value *IndVar, 143 BasicBlock *ExitingBlock, 144 BranchInst *BI, 145 SCEVExpander &Rewriter) { 146 // If the exiting block is not the same as the backedge block, we must compare 147 // against the preincremented value, otherwise we prefer to compare against 148 // the post-incremented value. 149 Value *CmpIndVar; 150 SCEVHandle RHS = BackedgeTakenCount; 151 if (ExitingBlock == L->getLoopLatch()) { 152 // Add one to the "backedge-taken" count to get the trip count. 153 // If this addition may overflow, we have to be more pessimistic and 154 // cast the induction variable before doing the add. 155 SCEVHandle Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 156 SCEVHandle N = 157 SE->getAddExpr(BackedgeTakenCount, 158 SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 159 if ((isa<SCEVConstant>(N) && !N->isZero()) || 160 SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 161 // No overflow. Cast the sum. 162 RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 163 } else { 164 // Potential overflow. Cast before doing the add. 165 RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 166 IndVar->getType()); 167 RHS = SE->getAddExpr(RHS, 168 SE->getIntegerSCEV(1, IndVar->getType())); 169 } 170 171 // The BackedgeTaken expression contains the number of times that the 172 // backedge branches to the loop header. This is one less than the 173 // number of times the loop executes, so use the incremented indvar. 174 CmpIndVar = L->getCanonicalInductionVariableIncrement(); 175 } else { 176 // We have to use the preincremented value... 177 RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 178 IndVar->getType()); 179 CmpIndVar = IndVar; 180 } 181 182 // Expand the code for the iteration count into the preheader of the loop. 183 BasicBlock *Preheader = L->getLoopPreheader(); 184 Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), 185 Preheader->getTerminator()); 186 187 // Insert a new icmp_ne or icmp_eq instruction before the branch. 188 ICmpInst::Predicate Opcode; 189 if (L->contains(BI->getSuccessor(0))) 190 Opcode = ICmpInst::ICMP_NE; 191 else 192 Opcode = ICmpInst::ICMP_EQ; 193 194 DOUT << "INDVARS: Rewriting loop exit condition to:\n" 195 << " LHS:" << *CmpIndVar // includes a newline 196 << " op:\t" 197 << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 198 << " RHS:\t" << *RHS << "\n"; 199 200 Value *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI); 201 BI->setCondition(Cond); 202 ++NumLFTR; 203 Changed = true; 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. 211void IndVarSimplify::RewriteLoopExitValues(Loop *L, 212 const SCEV *BackedgeTakenCount) { 213 BasicBlock *Preheader = L->getLoopPreheader(); 214 215 // Scan all of the instructions in the loop, looking at those that have 216 // extra-loop users and which are recurrences. 217 SCEVExpander Rewriter(*SE, *LI); 218 219 // We insert the code into the preheader of the loop if the loop contains 220 // multiple exit blocks, or in the exit block if there is exactly one. 221 BasicBlock *BlockToInsertInto; 222 SmallVector<BasicBlock*, 8> ExitBlocks; 223 L->getUniqueExitBlocks(ExitBlocks); 224 if (ExitBlocks.size() == 1) 225 BlockToInsertInto = ExitBlocks[0]; 226 else 227 BlockToInsertInto = Preheader; 228 BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI(); 229 230 bool HasConstantItCount = isa<SCEVConstant>(BackedgeTakenCount); 231 232 SmallPtrSet<Instruction*, 16> InstructionsToDelete; 233 std::map<Instruction*, Value*> ExitValues; 234 235 // Find all values that are computed inside the loop, but used outside of it. 236 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 237 // the exit blocks of the loop to find them. 238 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 239 BasicBlock *ExitBB = ExitBlocks[i]; 240 241 // If there are no PHI nodes in this exit block, then no values defined 242 // inside the loop are used on this path, skip it. 243 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 244 if (!PN) continue; 245 246 unsigned NumPreds = PN->getNumIncomingValues(); 247 248 // Iterate over all of the PHI nodes. 249 BasicBlock::iterator BBI = ExitBB->begin(); 250 while ((PN = dyn_cast<PHINode>(BBI++))) { 251 252 // Iterate over all of the values in all the PHI nodes. 253 for (unsigned i = 0; i != NumPreds; ++i) { 254 // If the value being merged in is not integer or is not defined 255 // in the loop, skip it. 256 Value *InVal = PN->getIncomingValue(i); 257 if (!isa<Instruction>(InVal) || 258 // SCEV only supports integer expressions for now. 259 (!isa<IntegerType>(InVal->getType()) && 260 !isa<PointerType>(InVal->getType()))) 261 continue; 262 263 // If this pred is for a subloop, not L itself, skip it. 264 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 265 continue; // The Block is in a subloop, skip it. 266 267 // Check that InVal is defined in the loop. 268 Instruction *Inst = cast<Instruction>(InVal); 269 if (!L->contains(Inst->getParent())) 270 continue; 271 272 // We require that this value either have a computable evolution or that 273 // the loop have a constant iteration count. In the case where the loop 274 // has a constant iteration count, we can sometimes force evaluation of 275 // the exit value through brute force. 276 SCEVHandle SH = SE->getSCEV(Inst); 277 if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount) 278 continue; // Cannot get exit evolution for the loop value. 279 280 // Okay, this instruction has a user outside of the current loop 281 // and varies predictably *inside* the loop. Evaluate the value it 282 // contains when the loop exits, if possible. 283 SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 284 if (isa<SCEVCouldNotCompute>(ExitValue) || 285 !ExitValue->isLoopInvariant(L)) 286 continue; 287 288 Changed = true; 289 ++NumReplaced; 290 291 // See if we already computed the exit value for the instruction, if so, 292 // just reuse it. 293 Value *&ExitVal = ExitValues[Inst]; 294 if (!ExitVal) 295 ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt); 296 297 DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal 298 << " LoopVal = " << *Inst << "\n"; 299 300 PN->setIncomingValue(i, ExitVal); 301 302 // If this instruction is dead now, schedule it to be removed. 303 if (Inst->use_empty()) 304 InstructionsToDelete.insert(Inst); 305 306 // See if this is a single-entry LCSSA PHI node. If so, we can (and 307 // have to) remove 308 // the PHI entirely. This is safe, because the NewVal won't be variant 309 // in the loop, so we don't need an LCSSA phi node anymore. 310 if (NumPreds == 1) { 311 SE->deleteValueFromRecords(PN); 312 PN->replaceAllUsesWith(ExitVal); 313 PN->eraseFromParent(); 314 break; 315 } 316 } 317 } 318 } 319 320 DeleteTriviallyDeadInstructions(InstructionsToDelete); 321} 322 323void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 324 // First step. Check to see if there are any floating-point recurrences. 325 // If there are, change them into integer recurrences, permitting analysis by 326 // the SCEV routines. 327 // 328 BasicBlock *Header = L->getHeader(); 329 330 SmallPtrSet<Instruction*, 16> DeadInsts; 331 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 332 PHINode *PN = cast<PHINode>(I); 333 HandleFloatingPointIV(L, PN, DeadInsts); 334 } 335 336 // If the loop previously had floating-point IV, ScalarEvolution 337 // may not have been able to compute a trip count. Now that we've done some 338 // re-writing, the trip count may be computable. 339 if (Changed) 340 SE->forgetLoopBackedgeTakenCount(L); 341 342 if (!DeadInsts.empty()) 343 DeleteTriviallyDeadInstructions(DeadInsts); 344} 345 346/// getEffectiveIndvarType - Determine the widest type that the 347/// induction-variable PHINode Phi is cast to. 348/// 349static const Type *getEffectiveIndvarType(const PHINode *Phi, 350 const ScalarEvolution *SE) { 351 const Type *Ty = Phi->getType(); 352 353 for (Value::use_const_iterator UI = Phi->use_begin(), UE = Phi->use_end(); 354 UI != UE; ++UI) { 355 const Type *CandidateType = NULL; 356 if (const ZExtInst *ZI = dyn_cast<ZExtInst>(UI)) 357 CandidateType = ZI->getDestTy(); 358 else if (const SExtInst *SI = dyn_cast<SExtInst>(UI)) 359 CandidateType = SI->getDestTy(); 360 else if (const IntToPtrInst *IP = dyn_cast<IntToPtrInst>(UI)) 361 CandidateType = IP->getDestTy(); 362 else if (const PtrToIntInst *PI = dyn_cast<PtrToIntInst>(UI)) 363 CandidateType = PI->getDestTy(); 364 if (CandidateType && 365 SE->isSCEVable(CandidateType) && 366 SE->getTypeSizeInBits(CandidateType) > SE->getTypeSizeInBits(Ty)) 367 Ty = CandidateType; 368 } 369 370 return Ty; 371} 372 373/// TestOrigIVForWrap - Analyze the original induction variable 374/// that controls the loop's iteration to determine whether it 375/// would ever undergo signed or unsigned overflow. Also, check 376/// whether an induction variable in the same type that starts 377/// at 0 would undergo signed overflow. 378/// 379/// In addition to setting the NoSignedWrap and NoUnsignedWrap 380/// variables to true when appropriate (they are not set to false here), 381/// return the PHI for this induction variable. Also record the initial 382/// and final values and the increment; these are not meaningful unless 383/// either NoSignedWrap or NoUnsignedWrap is true, and are always meaningful 384/// in that case, although the final value may be 0 indicating a nonconstant. 385/// 386/// TODO: This duplicates a fair amount of ScalarEvolution logic. 387/// Perhaps this can be merged with 388/// ScalarEvolution::getBackedgeTakenCount 389/// and/or ScalarEvolution::get{Sign,Zero}ExtendExpr. 390/// 391static const PHINode *TestOrigIVForWrap(const Loop *L, 392 const BranchInst *BI, 393 const Instruction *OrigCond, 394 const ScalarEvolution &SE, 395 bool &NoSignedWrap, 396 bool &NoUnsignedWrap, 397 const ConstantInt* &InitialVal, 398 const ConstantInt* &IncrVal, 399 const ConstantInt* &LimitVal) { 400 // Verify that the loop is sane and find the exit condition. 401 const ICmpInst *Cmp = dyn_cast<ICmpInst>(OrigCond); 402 if (!Cmp) return 0; 403 404 const Value *CmpLHS = Cmp->getOperand(0); 405 const Value *CmpRHS = Cmp->getOperand(1); 406 const BasicBlock *TrueBB = BI->getSuccessor(0); 407 const BasicBlock *FalseBB = BI->getSuccessor(1); 408 ICmpInst::Predicate Pred = Cmp->getPredicate(); 409 410 // Canonicalize a constant to the RHS. 411 if (isa<ConstantInt>(CmpLHS)) { 412 Pred = ICmpInst::getSwappedPredicate(Pred); 413 std::swap(CmpLHS, CmpRHS); 414 } 415 // Canonicalize SLE to SLT. 416 if (Pred == ICmpInst::ICMP_SLE) 417 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 418 if (!CI->getValue().isMaxSignedValue()) { 419 CmpRHS = ConstantInt::get(CI->getValue() + 1); 420 Pred = ICmpInst::ICMP_SLT; 421 } 422 // Canonicalize SGT to SGE. 423 if (Pred == ICmpInst::ICMP_SGT) 424 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 425 if (!CI->getValue().isMaxSignedValue()) { 426 CmpRHS = ConstantInt::get(CI->getValue() + 1); 427 Pred = ICmpInst::ICMP_SGE; 428 } 429 // Canonicalize SGE to SLT. 430 if (Pred == ICmpInst::ICMP_SGE) { 431 std::swap(TrueBB, FalseBB); 432 Pred = ICmpInst::ICMP_SLT; 433 } 434 // Canonicalize ULE to ULT. 435 if (Pred == ICmpInst::ICMP_ULE) 436 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 437 if (!CI->getValue().isMaxValue()) { 438 CmpRHS = ConstantInt::get(CI->getValue() + 1); 439 Pred = ICmpInst::ICMP_ULT; 440 } 441 // Canonicalize UGT to UGE. 442 if (Pred == ICmpInst::ICMP_UGT) 443 if (const ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) 444 if (!CI->getValue().isMaxValue()) { 445 CmpRHS = ConstantInt::get(CI->getValue() + 1); 446 Pred = ICmpInst::ICMP_UGE; 447 } 448 // Canonicalize UGE to ULT. 449 if (Pred == ICmpInst::ICMP_UGE) { 450 std::swap(TrueBB, FalseBB); 451 Pred = ICmpInst::ICMP_ULT; 452 } 453 // For now, analyze only LT loops for signed overflow. 454 if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_ULT) 455 return 0; 456 457 bool isSigned = Pred == ICmpInst::ICMP_SLT; 458 459 // Get the increment instruction. Look past casts if we will 460 // be able to prove that the original induction variable doesn't 461 // undergo signed or unsigned overflow, respectively. 462 const Value *IncrInst = CmpLHS; 463 if (isSigned) { 464 if (const SExtInst *SI = dyn_cast<SExtInst>(CmpLHS)) { 465 if (!isa<ConstantInt>(CmpRHS) || 466 !cast<ConstantInt>(CmpRHS)->getValue() 467 .isSignedIntN(SE.getTypeSizeInBits(IncrInst->getType()))) 468 return 0; 469 IncrInst = SI->getOperand(0); 470 } 471 } else { 472 if (const ZExtInst *ZI = dyn_cast<ZExtInst>(CmpLHS)) { 473 if (!isa<ConstantInt>(CmpRHS) || 474 !cast<ConstantInt>(CmpRHS)->getValue() 475 .isIntN(SE.getTypeSizeInBits(IncrInst->getType()))) 476 return 0; 477 IncrInst = ZI->getOperand(0); 478 } 479 } 480 481 // For now, only analyze induction variables that have simple increments. 482 const BinaryOperator *IncrOp = dyn_cast<BinaryOperator>(IncrInst); 483 if (!IncrOp || IncrOp->getOpcode() != Instruction::Add) 484 return 0; 485 IncrVal = dyn_cast<ConstantInt>(IncrOp->getOperand(1)); 486 if (!IncrVal) 487 return 0; 488 489 // Make sure the PHI looks like a normal IV. 490 const PHINode *PN = dyn_cast<PHINode>(IncrOp->getOperand(0)); 491 if (!PN || PN->getNumIncomingValues() != 2) 492 return 0; 493 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 494 unsigned BackEdge = !IncomingEdge; 495 if (!L->contains(PN->getIncomingBlock(BackEdge)) || 496 PN->getIncomingValue(BackEdge) != IncrOp) 497 return 0; 498 if (!L->contains(TrueBB)) 499 return 0; 500 501 // For now, only analyze loops with a constant start value, so that 502 // we can easily determine if the start value is not a maximum value 503 // which would wrap on the first iteration. 504 InitialVal = dyn_cast<ConstantInt>(PN->getIncomingValue(IncomingEdge)); 505 if (!InitialVal) 506 return 0; 507 508 // The upper limit need not be a constant; we'll check later. 509 LimitVal = dyn_cast<ConstantInt>(CmpRHS); 510 511 // We detect the impossibility of wrapping in two cases, both of 512 // which require starting with a non-max value: 513 // - The IV counts up by one, and the loop iterates only while it remains 514 // less than a limiting value (any) in the same type. 515 // - The IV counts up by a positive increment other than 1, and the 516 // constant limiting value + the increment is less than the max value 517 // (computed as max-increment to avoid overflow) 518 if (isSigned && !InitialVal->getValue().isMaxSignedValue()) { 519 if (IncrVal->equalsInt(1)) 520 NoSignedWrap = true; // LimitVal need not be constant 521 else if (LimitVal) { 522 uint64_t numBits = LimitVal->getValue().getBitWidth(); 523 if (IncrVal->getValue().sgt(APInt::getNullValue(numBits)) && 524 (APInt::getSignedMaxValue(numBits) - IncrVal->getValue()) 525 .sgt(LimitVal->getValue())) 526 NoSignedWrap = true; 527 } 528 } else if (!isSigned && !InitialVal->getValue().isMaxValue()) { 529 if (IncrVal->equalsInt(1)) 530 NoUnsignedWrap = true; // LimitVal need not be constant 531 else if (LimitVal) { 532 uint64_t numBits = LimitVal->getValue().getBitWidth(); 533 if (IncrVal->getValue().ugt(APInt::getNullValue(numBits)) && 534 (APInt::getMaxValue(numBits) - IncrVal->getValue()) 535 .ugt(LimitVal->getValue())) 536 NoUnsignedWrap = true; 537 } 538 } 539 return PN; 540} 541 542static Value *getSignExtendedTruncVar(const SCEVAddRecExpr *AR, 543 ScalarEvolution *SE, 544 const Type *LargestType, Loop *L, 545 const Type *myType, 546 SCEVExpander &Rewriter, 547 BasicBlock::iterator InsertPt) { 548 SCEVHandle ExtendedStart = 549 SE->getSignExtendExpr(AR->getStart(), LargestType); 550 SCEVHandle ExtendedStep = 551 SE->getSignExtendExpr(AR->getStepRecurrence(*SE), LargestType); 552 SCEVHandle ExtendedAddRec = 553 SE->getAddRecExpr(ExtendedStart, ExtendedStep, L); 554 if (LargestType != myType) 555 ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType); 556 return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt); 557} 558 559static Value *getZeroExtendedTruncVar(const SCEVAddRecExpr *AR, 560 ScalarEvolution *SE, 561 const Type *LargestType, Loop *L, 562 const Type *myType, 563 SCEVExpander &Rewriter, 564 BasicBlock::iterator InsertPt) { 565 SCEVHandle ExtendedStart = 566 SE->getZeroExtendExpr(AR->getStart(), LargestType); 567 SCEVHandle ExtendedStep = 568 SE->getZeroExtendExpr(AR->getStepRecurrence(*SE), LargestType); 569 SCEVHandle ExtendedAddRec = 570 SE->getAddRecExpr(ExtendedStart, ExtendedStep, L); 571 if (LargestType != myType) 572 ExtendedAddRec = SE->getTruncateExpr(ExtendedAddRec, myType); 573 return Rewriter.expandCodeFor(ExtendedAddRec, myType, InsertPt); 574} 575 576/// allUsesAreSameTyped - See whether all Uses of I are instructions 577/// with the same Opcode and the same type. 578static bool allUsesAreSameTyped(unsigned int Opcode, Instruction *I) { 579 const Type* firstType = NULL; 580 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 581 UI != UE; ++UI) { 582 Instruction *II = dyn_cast<Instruction>(*UI); 583 if (!II || II->getOpcode() != Opcode) 584 return false; 585 if (!firstType) 586 firstType = II->getType(); 587 else if (firstType != II->getType()) 588 return false; 589 } 590 return true; 591} 592 593bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 594 LI = &getAnalysis<LoopInfo>(); 595 SE = &getAnalysis<ScalarEvolution>(); 596 Changed = false; 597 598 // If there are any floating-point recurrences, attempt to 599 // transform them to use integer recurrences. 600 RewriteNonIntegerIVs(L); 601 602 BasicBlock *Header = L->getHeader(); 603 BasicBlock *ExitingBlock = L->getExitingBlock(); 604 SmallPtrSet<Instruction*, 16> DeadInsts; 605 606 // Verify the input to the pass in already in LCSSA form. 607 assert(L->isLCSSAForm()); 608 609 // Check to see if this loop has a computable loop-invariant execution count. 610 // If so, this means that we can compute the final value of any expressions 611 // that are recurrent in the loop, and substitute the exit values from the 612 // loop into any instructions outside of the loop that use the final values of 613 // the current expressions. 614 // 615 SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L); 616 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 617 RewriteLoopExitValues(L, BackedgeTakenCount); 618 619 // Next, analyze all of the induction variables in the loop, canonicalizing 620 // auxillary induction variables. 621 std::vector<std::pair<PHINode*, SCEVHandle> > IndVars; 622 623 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 624 PHINode *PN = cast<PHINode>(I); 625 if (SE->isSCEVable(PN->getType())) { 626 SCEVHandle SCEV = SE->getSCEV(PN); 627 // FIXME: It is an extremely bad idea to indvar substitute anything more 628 // complex than affine induction variables. Doing so will put expensive 629 // polynomial evaluations inside of the loop, and the str reduction pass 630 // currently can only reduce affine polynomials. For now just disable 631 // indvar subst on anything more complex than an affine addrec. 632 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV)) 633 if (AR->getLoop() == L && AR->isAffine()) 634 IndVars.push_back(std::make_pair(PN, SCEV)); 635 } 636 } 637 638 // Compute the type of the largest recurrence expression, and collect 639 // the set of the types of the other recurrence expressions. 640 const Type *LargestType = 0; 641 SmallSetVector<const Type *, 4> SizesToInsert; 642 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 643 LargestType = BackedgeTakenCount->getType(); 644 LargestType = SE->getEffectiveSCEVType(LargestType); 645 SizesToInsert.insert(LargestType); 646 } 647 for (unsigned i = 0, e = IndVars.size(); i != e; ++i) { 648 const PHINode *PN = IndVars[i].first; 649 const Type *PNTy = PN->getType(); 650 PNTy = SE->getEffectiveSCEVType(PNTy); 651 SizesToInsert.insert(PNTy); 652 const Type *EffTy = getEffectiveIndvarType(PN, SE); 653 EffTy = SE->getEffectiveSCEVType(EffTy); 654 SizesToInsert.insert(EffTy); 655 if (!LargestType || 656 SE->getTypeSizeInBits(EffTy) > 657 SE->getTypeSizeInBits(LargestType)) 658 LargestType = EffTy; 659 } 660 661 // Create a rewriter object which we'll use to transform the code with. 662 SCEVExpander Rewriter(*SE, *LI); 663 664 // Now that we know the largest of of the induction variables in this loop, 665 // insert a canonical induction variable of the largest size. 666 Value *IndVar = 0; 667 if (!SizesToInsert.empty()) { 668 IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); 669 ++NumInserted; 670 Changed = true; 671 DOUT << "INDVARS: New CanIV: " << *IndVar; 672 } 673 674 // If we have a trip count expression, rewrite the loop's exit condition 675 // using it. We can currently only handle loops with a single exit. 676 bool NoSignedWrap = false; 677 bool NoUnsignedWrap = false; 678 const ConstantInt* InitialVal, * IncrVal, * LimitVal; 679 const PHINode *OrigControllingPHI = 0; 680 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) 681 // Can't rewrite non-branch yet. 682 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) { 683 if (Instruction *OrigCond = dyn_cast<Instruction>(BI->getCondition())) { 684 // Determine if the OrigIV will ever undergo overflow. 685 OrigControllingPHI = 686 TestOrigIVForWrap(L, BI, OrigCond, *SE, 687 NoSignedWrap, NoUnsignedWrap, 688 InitialVal, IncrVal, LimitVal); 689 690 // We'll be replacing the original condition, so it'll be dead. 691 DeadInsts.insert(OrigCond); 692 } 693 694 LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 695 ExitingBlock, BI, Rewriter); 696 } 697 698 // Now that we have a canonical induction variable, we can rewrite any 699 // recurrences in terms of the induction variable. Start with the auxillary 700 // induction variables, and recursively rewrite any of their uses. 701 BasicBlock::iterator InsertPt = Header->getFirstNonPHI(); 702 703 // If there were induction variables of other sizes, cast the primary 704 // induction variable to the right size for them, avoiding the need for the 705 // code evaluation methods to insert induction variables of different sizes. 706 for (unsigned i = 0, e = SizesToInsert.size(); i != e; ++i) { 707 const Type *Ty = SizesToInsert[i]; 708 if (Ty != LargestType) { 709 Instruction *New = new TruncInst(IndVar, Ty, "indvar", InsertPt); 710 Rewriter.addInsertedValue(New, SE->getSCEV(New)); 711 DOUT << "INDVARS: Made trunc IV for type " << *Ty << ": " 712 << *New << "\n"; 713 } 714 } 715 716 // Rewrite all induction variables in terms of the canonical induction 717 // variable. 718 while (!IndVars.empty()) { 719 PHINode *PN = IndVars.back().first; 720 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(IndVars.back().second); 721 Value *NewVal = Rewriter.expandCodeFor(AR, PN->getType(), InsertPt); 722 DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *PN 723 << " into = " << *NewVal << "\n"; 724 NewVal->takeName(PN); 725 726 /// If the new canonical induction variable is wider than the original, 727 /// and the original has uses that are casts to wider types, see if the 728 /// truncate and extend can be omitted. 729 if (PN == OrigControllingPHI && PN->getType() != LargestType) 730 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); 731 UI != UE; ++UI) { 732 Instruction *UInst = dyn_cast<Instruction>(*UI); 733 if (UInst && isa<SExtInst>(UInst) && NoSignedWrap) { 734 Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, L, 735 UInst->getType(), Rewriter, InsertPt); 736 UInst->replaceAllUsesWith(TruncIndVar); 737 DeadInsts.insert(UInst); 738 } 739 // See if we can figure out sext(i+constant) doesn't wrap, so we can 740 // use a larger add. This is common in subscripting. 741 if (UInst && UInst->getOpcode()==Instruction::Add && 742 !UInst->use_empty() && 743 allUsesAreSameTyped(Instruction::SExt, UInst) && 744 isa<ConstantInt>(UInst->getOperand(1)) && 745 NoSignedWrap && LimitVal) { 746 uint64_t oldBitSize = LimitVal->getValue().getBitWidth(); 747 uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 748 ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 749 if (((APInt::getSignedMaxValue(oldBitSize) - IncrVal->getValue()) - 750 AddRHS->getValue()).sgt(LimitVal->getValue())) { 751 // We've determined this is (i+constant) and it won't overflow. 752 if (isa<SExtInst>(UInst->use_begin())) { 753 SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin()); 754 uint64_t truncSize = oldSext->getType()->getPrimitiveSizeInBits(); 755 Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 756 L, oldSext->getType(), Rewriter, 757 InsertPt); 758 APInt APnewAddRHS = APInt(AddRHS->getValue()).sext(newBitSize); 759 if (newBitSize > truncSize) 760 APnewAddRHS = APnewAddRHS.trunc(truncSize); 761 ConstantInt* newAddRHS =ConstantInt::get(APnewAddRHS); 762 Value *NewAdd = 763 BinaryOperator::CreateAdd(TruncIndVar, newAddRHS, 764 UInst->getName()+".nosex", UInst); 765 for (Value::use_iterator UI2 = UInst->use_begin(), 766 UE2 = UInst->use_end(); UI2 != UE2; ++UI2) { 767 Instruction *II = dyn_cast<Instruction>(UI2); 768 II->replaceAllUsesWith(NewAdd); 769 DeadInsts.insert(II); 770 } 771 DeadInsts.insert(UInst); 772 } 773 } 774 } 775 // Try for sext(i | constant). This is safe as long as the 776 // high bit of the constant is not set. 777 if (UInst && UInst->getOpcode()==Instruction::Or && 778 !UInst->use_empty() && 779 allUsesAreSameTyped(Instruction::SExt, UInst) && NoSignedWrap && 780 isa<ConstantInt>(UInst->getOperand(1))) { 781 ConstantInt* RHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 782 if (!RHS->getValue().isNegative()) { 783 uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 784 SExtInst* oldSext = dyn_cast<SExtInst>(UInst->use_begin()); 785 uint64_t truncSize = oldSext->getType()->getPrimitiveSizeInBits(); 786 Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 787 L, oldSext->getType(), Rewriter, 788 InsertPt); 789 APInt APnewOrRHS = APInt(RHS->getValue()).sext(newBitSize); 790 if (newBitSize > truncSize) 791 APnewOrRHS = APnewOrRHS.trunc(truncSize); 792 ConstantInt* newOrRHS =ConstantInt::get(APnewOrRHS); 793 Value *NewOr = 794 BinaryOperator::CreateOr(TruncIndVar, newOrRHS, 795 UInst->getName()+".nosex", UInst); 796 for (Value::use_iterator UI2 = UInst->use_begin(), 797 UE2 = UInst->use_end(); UI2 != UE2; ++UI2) { 798 Instruction *II = dyn_cast<Instruction>(UI2); 799 II->replaceAllUsesWith(NewOr); 800 DeadInsts.insert(II); 801 } 802 DeadInsts.insert(UInst); 803 } 804 } 805 // A zext of a signed variable known not to overflow is still safe. 806 if (UInst && isa<ZExtInst>(UInst) && (NoUnsignedWrap || NoSignedWrap)) { 807 Value *TruncIndVar = getZeroExtendedTruncVar(AR, SE, LargestType, L, 808 UInst->getType(), Rewriter, InsertPt); 809 UInst->replaceAllUsesWith(TruncIndVar); 810 DeadInsts.insert(UInst); 811 } 812 // If we have zext(i&constant), it's always safe to use the larger 813 // variable. This is not common but is a bottleneck in Openssl. 814 // (RHS doesn't have to be constant. There should be a better approach 815 // than bottom-up pattern matching for this...) 816 if (UInst && UInst->getOpcode()==Instruction::And && 817 !UInst->use_empty() && 818 allUsesAreSameTyped(Instruction::ZExt, UInst) && 819 isa<ConstantInt>(UInst->getOperand(1))) { 820 uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 821 ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 822 ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst->use_begin()); 823 uint64_t truncSize = oldZext->getType()->getPrimitiveSizeInBits(); 824 Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 825 L, oldZext->getType(), Rewriter, InsertPt); 826 APInt APnewAndRHS = APInt(AndRHS->getValue()).zext(newBitSize); 827 if (newBitSize > truncSize) 828 APnewAndRHS = APnewAndRHS.trunc(truncSize); 829 ConstantInt* newAndRHS = ConstantInt::get(APnewAndRHS); 830 Value *NewAnd = 831 BinaryOperator::CreateAnd(TruncIndVar, newAndRHS, 832 UInst->getName()+".nozex", UInst); 833 for (Value::use_iterator UI2 = UInst->use_begin(), 834 UE2 = UInst->use_end(); UI2 != UE2; ++UI2) { 835 Instruction *II = dyn_cast<Instruction>(UI2); 836 II->replaceAllUsesWith(NewAnd); 837 DeadInsts.insert(II); 838 } 839 DeadInsts.insert(UInst); 840 } 841 // If we have zext((i+constant)&constant), we can use the larger 842 // variable even if the add does overflow. This works whenever the 843 // constant being ANDed is the same size as i, which it presumably is. 844 // We don't need to restrict the expression being and'ed to i+const, 845 // but we have to promote everything in it, so it's convenient. 846 // zext((i | constant)&constant) is also valid and accepted here. 847 if (UInst && (UInst->getOpcode()==Instruction::Add || 848 UInst->getOpcode()==Instruction::Or) && 849 UInst->hasOneUse() && 850 isa<ConstantInt>(UInst->getOperand(1))) { 851 uint64_t newBitSize = LargestType->getPrimitiveSizeInBits(); 852 ConstantInt* AddRHS = dyn_cast<ConstantInt>(UInst->getOperand(1)); 853 Instruction *UInst2 = dyn_cast<Instruction>(UInst->use_begin()); 854 if (UInst2 && UInst2->getOpcode() == Instruction::And && 855 !UInst2->use_empty() && 856 allUsesAreSameTyped(Instruction::ZExt, UInst2) && 857 isa<ConstantInt>(UInst2->getOperand(1))) { 858 ZExtInst* oldZext = dyn_cast<ZExtInst>(UInst2->use_begin()); 859 uint64_t truncSize = oldZext->getType()->getPrimitiveSizeInBits(); 860 Value *TruncIndVar = getSignExtendedTruncVar(AR, SE, LargestType, 861 L, oldZext->getType(), Rewriter, InsertPt); 862 ConstantInt* AndRHS = dyn_cast<ConstantInt>(UInst2->getOperand(1)); 863 APInt APnewAddRHS = APInt(AddRHS->getValue()).zext(newBitSize); 864 if (newBitSize > truncSize) 865 APnewAddRHS = APnewAddRHS.trunc(truncSize); 866 ConstantInt* newAddRHS = ConstantInt::get(APnewAddRHS); 867 Value *NewAdd = ((UInst->getOpcode()==Instruction::Add) ? 868 BinaryOperator::CreateAdd(TruncIndVar, newAddRHS, 869 UInst->getName()+".nozex", UInst2) : 870 BinaryOperator::CreateOr(TruncIndVar, newAddRHS, 871 UInst->getName()+".nozex", UInst2)); 872 APInt APcopy2 = APInt(AndRHS->getValue()); 873 ConstantInt* newAndRHS = ConstantInt::get(APcopy2.zext(newBitSize)); 874 Value *NewAnd = 875 BinaryOperator::CreateAnd(NewAdd, newAndRHS, 876 UInst->getName()+".nozex", UInst2); 877 for (Value::use_iterator UI2 = UInst2->use_begin(), 878 UE2 = UInst2->use_end(); UI2 != UE2; ++UI2) { 879 Instruction *II = dyn_cast<Instruction>(UI2); 880 II->replaceAllUsesWith(NewAnd); 881 DeadInsts.insert(II); 882 } 883 DeadInsts.insert(UInst); 884 DeadInsts.insert(UInst2); 885 } 886 } 887 } 888 889 // Replace the old PHI Node with the inserted computation. 890 PN->replaceAllUsesWith(NewVal); 891 DeadInsts.insert(PN); 892 IndVars.pop_back(); 893 ++NumRemoved; 894 Changed = true; 895 } 896 897 DeleteTriviallyDeadInstructions(DeadInsts); 898 assert(L->isLCSSAForm()); 899 return Changed; 900} 901 902/// Return true if it is OK to use SIToFPInst for an inducation variable 903/// with given inital and exit values. 904static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 905 uint64_t intIV, uint64_t intEV) { 906 907 if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 908 return true; 909 910 // If the iteration range can be handled by SIToFPInst then use it. 911 APInt Max = APInt::getSignedMaxValue(32); 912 if (Max.getZExtValue() > static_cast<uint64_t>(abs(intEV - intIV))) 913 return true; 914 915 return false; 916} 917 918/// convertToInt - Convert APF to an integer, if possible. 919static bool convertToInt(const APFloat &APF, uint64_t *intVal) { 920 921 bool isExact = false; 922 if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 923 return false; 924 if (APF.convertToInteger(intVal, 32, APF.isNegative(), 925 APFloat::rmTowardZero, &isExact) 926 != APFloat::opOK) 927 return false; 928 if (!isExact) 929 return false; 930 return true; 931 932} 933 934/// HandleFloatingPointIV - If the loop has floating induction variable 935/// then insert corresponding integer induction variable if possible. 936/// For example, 937/// for(double i = 0; i < 10000; ++i) 938/// bar(i) 939/// is converted into 940/// for(int i = 0; i < 10000; ++i) 941/// bar((double)i); 942/// 943void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH, 944 SmallPtrSet<Instruction*, 16> &DeadInsts) { 945 946 unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 947 unsigned BackEdge = IncomingEdge^1; 948 949 // Check incoming value. 950 ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 951 if (!InitValue) return; 952 uint64_t newInitValue = Type::Int32Ty->getPrimitiveSizeInBits(); 953 if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 954 return; 955 956 // Check IV increment. Reject this PH if increement operation is not 957 // an add or increment value can not be represented by an integer. 958 BinaryOperator *Incr = 959 dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 960 if (!Incr) return; 961 if (Incr->getOpcode() != Instruction::Add) return; 962 ConstantFP *IncrValue = NULL; 963 unsigned IncrVIndex = 1; 964 if (Incr->getOperand(1) == PH) 965 IncrVIndex = 0; 966 IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 967 if (!IncrValue) return; 968 uint64_t newIncrValue = Type::Int32Ty->getPrimitiveSizeInBits(); 969 if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 970 return; 971 972 // Check Incr uses. One user is PH and the other users is exit condition used 973 // by the conditional terminator. 974 Value::use_iterator IncrUse = Incr->use_begin(); 975 Instruction *U1 = cast<Instruction>(IncrUse++); 976 if (IncrUse == Incr->use_end()) return; 977 Instruction *U2 = cast<Instruction>(IncrUse++); 978 if (IncrUse != Incr->use_end()) return; 979 980 // Find exit condition. 981 FCmpInst *EC = dyn_cast<FCmpInst>(U1); 982 if (!EC) 983 EC = dyn_cast<FCmpInst>(U2); 984 if (!EC) return; 985 986 if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 987 if (!BI->isConditional()) return; 988 if (BI->getCondition() != EC) return; 989 } 990 991 // Find exit value. If exit value can not be represented as an interger then 992 // do not handle this floating point PH. 993 ConstantFP *EV = NULL; 994 unsigned EVIndex = 1; 995 if (EC->getOperand(1) == Incr) 996 EVIndex = 0; 997 EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 998 if (!EV) return; 999 uint64_t intEV = Type::Int32Ty->getPrimitiveSizeInBits(); 1000 if (!convertToInt(EV->getValueAPF(), &intEV)) 1001 return; 1002 1003 // Find new predicate for integer comparison. 1004 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 1005 switch (EC->getPredicate()) { 1006 case CmpInst::FCMP_OEQ: 1007 case CmpInst::FCMP_UEQ: 1008 NewPred = CmpInst::ICMP_EQ; 1009 break; 1010 case CmpInst::FCMP_OGT: 1011 case CmpInst::FCMP_UGT: 1012 NewPred = CmpInst::ICMP_UGT; 1013 break; 1014 case CmpInst::FCMP_OGE: 1015 case CmpInst::FCMP_UGE: 1016 NewPred = CmpInst::ICMP_UGE; 1017 break; 1018 case CmpInst::FCMP_OLT: 1019 case CmpInst::FCMP_ULT: 1020 NewPred = CmpInst::ICMP_ULT; 1021 break; 1022 case CmpInst::FCMP_OLE: 1023 case CmpInst::FCMP_ULE: 1024 NewPred = CmpInst::ICMP_ULE; 1025 break; 1026 default: 1027 break; 1028 } 1029 if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 1030 1031 // Insert new integer induction variable. 1032 PHINode *NewPHI = PHINode::Create(Type::Int32Ty, 1033 PH->getName()+".int", PH); 1034 NewPHI->addIncoming(ConstantInt::get(Type::Int32Ty, newInitValue), 1035 PH->getIncomingBlock(IncomingEdge)); 1036 1037 Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 1038 ConstantInt::get(Type::Int32Ty, 1039 newIncrValue), 1040 Incr->getName()+".int", Incr); 1041 NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 1042 1043 ConstantInt *NewEV = ConstantInt::get(Type::Int32Ty, intEV); 1044 Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(BackEdge) : NewEV); 1045 Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(BackEdge)); 1046 ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(), 1047 EC->getParent()->getTerminator()); 1048 1049 // Delete old, floating point, exit comparision instruction. 1050 EC->replaceAllUsesWith(NewEC); 1051 DeadInsts.insert(EC); 1052 1053 // Delete old, floating point, increment instruction. 1054 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 1055 DeadInsts.insert(Incr); 1056 1057 // Replace floating induction variable. Give SIToFPInst preference over 1058 // UIToFPInst because it is faster on platforms that are widely used. 1059 if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 1060 SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 1061 PH->getParent()->getFirstNonPHI()); 1062 PH->replaceAllUsesWith(Conv); 1063 } else { 1064 UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 1065 PH->getParent()->getFirstNonPHI()); 1066 PH->replaceAllUsesWith(Conv); 1067 } 1068 DeadInsts.insert(PH); 1069} 1070 1071