LLVM API Documentation
00001 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This transformation analyzes and transforms the induction variables (and 00011 // computations derived from them) into simpler forms suitable for subsequent 00012 // analysis and transformation. 00013 // 00014 // This transformation makes the following changes to each loop with an 00015 // identifiable induction variable: 00016 // 1. All loops are transformed to have a SINGLE canonical induction variable 00017 // which starts at zero and steps by one. 00018 // 2. The canonical induction variable is guaranteed to be the first PHI node 00019 // in the loop header block. 00020 // 3. The canonical induction variable is guaranteed to be in a wide enough 00021 // type so that IV expressions need not be (directly) zero-extended or 00022 // sign-extended. 00023 // 4. Any pointer arithmetic recurrences are raised to use array subscripts. 00024 // 00025 // If the trip count of a loop is computable, this pass also makes the following 00026 // changes: 00027 // 1. The exit condition for the loop is canonicalized to compare the 00028 // induction value against the exit value. This turns loops like: 00029 // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 00030 // 2. Any use outside of the loop of an expression derived from the indvar 00031 // is changed to compute the derived value outside of the loop, eliminating 00032 // the dependence on the exit value of the induction variable. If the only 00033 // purpose of the loop is to compute the exit value of some derived 00034 // expression, this transformation will make the loop dead. 00035 // 00036 // This transformation should be followed by strength reduction after all of the 00037 // desired loop transformations have been performed. 00038 // 00039 //===----------------------------------------------------------------------===// 00040 00041 #define DEBUG_TYPE "indvars" 00042 #include "llvm/Transforms/Scalar.h" 00043 #include "llvm/BasicBlock.h" 00044 #include "llvm/Constants.h" 00045 #include "llvm/Instructions.h" 00046 #include "llvm/LLVMContext.h" 00047 #include "llvm/Type.h" 00048 #include "llvm/Analysis/Dominators.h" 00049 #include "llvm/Analysis/IVUsers.h" 00050 #include "llvm/Analysis/ScalarEvolutionExpander.h" 00051 #include "llvm/Analysis/LoopInfo.h" 00052 #include "llvm/Analysis/LoopPass.h" 00053 #include "llvm/Support/CFG.h" 00054 #include "llvm/Support/Compiler.h" 00055 #include "llvm/Support/Debug.h" 00056 #include "llvm/Transforms/Utils/Local.h" 00057 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00058 #include "llvm/Support/CommandLine.h" 00059 #include "llvm/ADT/SmallVector.h" 00060 #include "llvm/ADT/Statistic.h" 00061 #include "llvm/ADT/STLExtras.h" 00062 using namespace llvm; 00063 00064 STATISTIC(NumRemoved , "Number of aux indvars removed"); 00065 STATISTIC(NumInserted, "Number of canonical indvars added"); 00066 STATISTIC(NumReplaced, "Number of exit values replaced"); 00067 STATISTIC(NumLFTR , "Number of loop exit tests replaced"); 00068 00069 namespace { 00070 class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass { 00071 IVUsers *IU; 00072 LoopInfo *LI; 00073 ScalarEvolution *SE; 00074 DominatorTree *DT; 00075 bool Changed; 00076 public: 00077 00078 static char ID; // Pass identification, replacement for typeid 00079 IndVarSimplify() : LoopPass(&ID) {} 00080 00081 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 00082 00083 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00084 AU.addRequired<DominatorTree>(); 00085 AU.addRequired<LoopInfo>(); 00086 AU.addRequired<ScalarEvolution>(); 00087 AU.addRequiredID(LoopSimplifyID); 00088 AU.addRequiredID(LCSSAID); 00089 AU.addRequired<IVUsers>(); 00090 AU.addPreserved<ScalarEvolution>(); 00091 AU.addPreservedID(LoopSimplifyID); 00092 AU.addPreservedID(LCSSAID); 00093 AU.addPreserved<IVUsers>(); 00094 AU.setPreservesCFG(); 00095 } 00096 00097 private: 00098 00099 void RewriteNonIntegerIVs(Loop *L); 00100 00101 ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 00102 Value *IndVar, 00103 BasicBlock *ExitingBlock, 00104 BranchInst *BI, 00105 SCEVExpander &Rewriter); 00106 void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount, 00107 SCEVExpander &Rewriter); 00108 00109 void RewriteIVExpressions(Loop *L, const Type *LargestType, 00110 SCEVExpander &Rewriter); 00111 00112 void SinkUnusedInvariants(Loop *L); 00113 00114 void HandleFloatingPointIV(Loop *L, PHINode *PH); 00115 }; 00116 } 00117 00118 char IndVarSimplify::ID = 0; 00119 static RegisterPass<IndVarSimplify> 00120 X("indvars", "Canonicalize Induction Variables"); 00121 00122 Pass *llvm::createIndVarSimplifyPass() { 00123 return new IndVarSimplify(); 00124 } 00125 00126 /// LinearFunctionTestReplace - This method rewrites the exit condition of the 00127 /// loop to be a canonical != comparison against the incremented loop induction 00128 /// variable. This pass is able to rewrite the exit tests of any loop where the 00129 /// SCEV analysis can determine a loop-invariant trip count of the loop, which 00130 /// is actually a much broader range than just linear tests. 00131 ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L, 00132 const SCEV *BackedgeTakenCount, 00133 Value *IndVar, 00134 BasicBlock *ExitingBlock, 00135 BranchInst *BI, 00136 SCEVExpander &Rewriter) { 00137 // If the exiting block is not the same as the backedge block, we must compare 00138 // against the preincremented value, otherwise we prefer to compare against 00139 // the post-incremented value. 00140 Value *CmpIndVar; 00141 const SCEV *RHS = BackedgeTakenCount; 00142 if (ExitingBlock == L->getLoopLatch()) { 00143 // Add one to the "backedge-taken" count to get the trip count. 00144 // If this addition may overflow, we have to be more pessimistic and 00145 // cast the induction variable before doing the add. 00146 const SCEV *Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType()); 00147 const SCEV *N = 00148 SE->getAddExpr(BackedgeTakenCount, 00149 SE->getIntegerSCEV(1, BackedgeTakenCount->getType())); 00150 if ((isa<SCEVConstant>(N) && !N->isZero()) || 00151 SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) { 00152 // No overflow. Cast the sum. 00153 RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType()); 00154 } else { 00155 // Potential overflow. Cast before doing the add. 00156 RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 00157 IndVar->getType()); 00158 RHS = SE->getAddExpr(RHS, 00159 SE->getIntegerSCEV(1, IndVar->getType())); 00160 } 00161 00162 // The BackedgeTaken expression contains the number of times that the 00163 // backedge branches to the loop header. This is one less than the 00164 // number of times the loop executes, so use the incremented indvar. 00165 CmpIndVar = L->getCanonicalInductionVariableIncrement(); 00166 } else { 00167 // We have to use the preincremented value... 00168 RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount, 00169 IndVar->getType()); 00170 CmpIndVar = IndVar; 00171 } 00172 00173 // Expand the code for the iteration count. 00174 assert(RHS->isLoopInvariant(L) && 00175 "Computed iteration count is not loop invariant!"); 00176 Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(), BI); 00177 00178 // Insert a new icmp_ne or icmp_eq instruction before the branch. 00179 ICmpInst::Predicate Opcode; 00180 if (L->contains(BI->getSuccessor(0))) 00181 Opcode = ICmpInst::ICMP_NE; 00182 else 00183 Opcode = ICmpInst::ICMP_EQ; 00184 00185 DOUT << "INDVARS: Rewriting loop exit condition to:\n" 00186 << " LHS:" << *CmpIndVar << '\n' 00187 << " op:\t" 00188 << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 00189 << " RHS:\t" << *RHS << "\n"; 00190 00191 ICmpInst *Cond = new ICmpInst(BI, Opcode, CmpIndVar, ExitCnt, "exitcond"); 00192 00193 Instruction *OrigCond = cast<Instruction>(BI->getCondition()); 00194 // It's tempting to use replaceAllUsesWith here to fully replace the old 00195 // comparison, but that's not immediately safe, since users of the old 00196 // comparison may not be dominated by the new comparison. Instead, just 00197 // update the branch to use the new comparison; in the common case this 00198 // will make old comparison dead. 00199 BI->setCondition(Cond); 00200 RecursivelyDeleteTriviallyDeadInstructions(OrigCond); 00201 00202 ++NumLFTR; 00203 Changed = true; 00204 return Cond; 00205 } 00206 00207 /// RewriteLoopExitValues - Check to see if this loop has a computable 00208 /// loop-invariant execution count. If so, this means that we can compute the 00209 /// final value of any expressions that are recurrent in the loop, and 00210 /// substitute the exit values from the loop into any instructions outside of 00211 /// the loop that use the final values of the current expressions. 00212 /// 00213 /// This is mostly redundant with the regular IndVarSimplify activities that 00214 /// happen later, except that it's more powerful in some cases, because it's 00215 /// able to brute-force evaluate arbitrary instructions as long as they have 00216 /// constant operands at the beginning of the loop. 00217 void IndVarSimplify::RewriteLoopExitValues(Loop *L, 00218 const SCEV *BackedgeTakenCount, 00219 SCEVExpander &Rewriter) { 00220 // Verify the input to the pass in already in LCSSA form. 00221 assert(L->isLCSSAForm()); 00222 00223 SmallVector<BasicBlock*, 8> ExitBlocks; 00224 L->getUniqueExitBlocks(ExitBlocks); 00225 00226 // Find all values that are computed inside the loop, but used outside of it. 00227 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 00228 // the exit blocks of the loop to find them. 00229 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 00230 BasicBlock *ExitBB = ExitBlocks[i]; 00231 00232 // If there are no PHI nodes in this exit block, then no values defined 00233 // inside the loop are used on this path, skip it. 00234 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 00235 if (!PN) continue; 00236 00237 unsigned NumPreds = PN->getNumIncomingValues(); 00238 00239 // Iterate over all of the PHI nodes. 00240 BasicBlock::iterator BBI = ExitBB->begin(); 00241 while ((PN = dyn_cast<PHINode>(BBI++))) { 00242 if (PN->use_empty()) 00243 continue; // dead use, don't replace it 00244 // Iterate over all of the values in all the PHI nodes. 00245 for (unsigned i = 0; i != NumPreds; ++i) { 00246 // If the value being merged in is not integer or is not defined 00247 // in the loop, skip it. 00248 Value *InVal = PN->getIncomingValue(i); 00249 if (!isa<Instruction>(InVal) || 00250 // SCEV only supports integer expressions for now. 00251 (!isa<IntegerType>(InVal->getType()) && 00252 !isa<PointerType>(InVal->getType()))) 00253 continue; 00254 00255 // If this pred is for a subloop, not L itself, skip it. 00256 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 00257 continue; // The Block is in a subloop, skip it. 00258 00259 // Check that InVal is defined in the loop. 00260 Instruction *Inst = cast<Instruction>(InVal); 00261 if (!L->contains(Inst->getParent())) 00262 continue; 00263 00264 // Okay, this instruction has a user outside of the current loop 00265 // and varies predictably *inside* the loop. Evaluate the value it 00266 // contains when the loop exits, if possible. 00267 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 00268 if (!ExitValue->isLoopInvariant(L)) 00269 continue; 00270 00271 Changed = true; 00272 ++NumReplaced; 00273 00274 Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 00275 00276 DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 00277 << " LoopVal = " << *Inst << "\n"; 00278 00279 PN->setIncomingValue(i, ExitVal); 00280 00281 // If this instruction is dead now, delete it. 00282 RecursivelyDeleteTriviallyDeadInstructions(Inst); 00283 00284 if (NumPreds == 1) { 00285 // Completely replace a single-pred PHI. This is safe, because the 00286 // NewVal won't be variant in the loop, so we don't need an LCSSA phi 00287 // node anymore. 00288 PN->replaceAllUsesWith(ExitVal); 00289 RecursivelyDeleteTriviallyDeadInstructions(PN); 00290 } 00291 } 00292 if (NumPreds != 1) { 00293 // Clone the PHI and delete the original one. This lets IVUsers and 00294 // any other maps purge the original user from their records. 00295 PHINode *NewPN = PN->clone(PN->getContext()); 00296 NewPN->takeName(PN); 00297 NewPN->insertBefore(PN); 00298 PN->replaceAllUsesWith(NewPN); 00299 PN->eraseFromParent(); 00300 } 00301 } 00302 } 00303 } 00304 00305 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 00306 // First step. Check to see if there are any floating-point recurrences. 00307 // If there are, change them into integer recurrences, permitting analysis by 00308 // the SCEV routines. 00309 // 00310 BasicBlock *Header = L->getHeader(); 00311 00312 SmallVector<WeakVH, 8> PHIs; 00313 for (BasicBlock::iterator I = Header->begin(); 00314 PHINode *PN = dyn_cast<PHINode>(I); ++I) 00315 PHIs.push_back(PN); 00316 00317 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 00318 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i])) 00319 HandleFloatingPointIV(L, PN); 00320 00321 // If the loop previously had floating-point IV, ScalarEvolution 00322 // may not have been able to compute a trip count. Now that we've done some 00323 // re-writing, the trip count may be computable. 00324 if (Changed) 00325 SE->forgetLoopBackedgeTakenCount(L); 00326 } 00327 00328 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 00329 IU = &getAnalysis<IVUsers>(); 00330 LI = &getAnalysis<LoopInfo>(); 00331 SE = &getAnalysis<ScalarEvolution>(); 00332 DT = &getAnalysis<DominatorTree>(); 00333 Changed = false; 00334 00335 // If there are any floating-point recurrences, attempt to 00336 // transform them to use integer recurrences. 00337 RewriteNonIntegerIVs(L); 00338 00339 BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null 00340 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 00341 00342 // Create a rewriter object which we'll use to transform the code with. 00343 SCEVExpander Rewriter(*SE); 00344 00345 // Check to see if this loop has a computable loop-invariant execution count. 00346 // If so, this means that we can compute the final value of any expressions 00347 // that are recurrent in the loop, and substitute the exit values from the 00348 // loop into any instructions outside of the loop that use the final values of 00349 // the current expressions. 00350 // 00351 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 00352 RewriteLoopExitValues(L, BackedgeTakenCount, Rewriter); 00353 00354 // Compute the type of the largest recurrence expression, and decide whether 00355 // a canonical induction variable should be inserted. 00356 const Type *LargestType = 0; 00357 bool NeedCannIV = false; 00358 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 00359 LargestType = BackedgeTakenCount->getType(); 00360 LargestType = SE->getEffectiveSCEVType(LargestType); 00361 // If we have a known trip count and a single exit block, we'll be 00362 // rewriting the loop exit test condition below, which requires a 00363 // canonical induction variable. 00364 if (ExitingBlock) 00365 NeedCannIV = true; 00366 } 00367 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 00368 const SCEV *Stride = IU->StrideOrder[i]; 00369 const Type *Ty = SE->getEffectiveSCEVType(Stride->getType()); 00370 if (!LargestType || 00371 SE->getTypeSizeInBits(Ty) > 00372 SE->getTypeSizeInBits(LargestType)) 00373 LargestType = Ty; 00374 00375 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 00376 IU->IVUsesByStride.find(IU->StrideOrder[i]); 00377 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 00378 00379 if (!SI->second->Users.empty()) 00380 NeedCannIV = true; 00381 } 00382 00383 // Now that we know the largest of of the induction variable expressions 00384 // in this loop, insert a canonical induction variable of the largest size. 00385 Value *IndVar = 0; 00386 if (NeedCannIV) { 00387 // Check to see if the loop already has a canonical-looking induction 00388 // variable. If one is present and it's wider than the planned canonical 00389 // induction variable, temporarily remove it, so that the Rewriter 00390 // doesn't attempt to reuse it. 00391 PHINode *OldCannIV = L->getCanonicalInductionVariable(); 00392 if (OldCannIV) { 00393 if (SE->getTypeSizeInBits(OldCannIV->getType()) > 00394 SE->getTypeSizeInBits(LargestType)) 00395 OldCannIV->removeFromParent(); 00396 else 00397 OldCannIV = 0; 00398 } 00399 00400 IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L, LargestType); 00401 00402 ++NumInserted; 00403 Changed = true; 00404 DOUT << "INDVARS: New CanIV: " << *IndVar << '\n'; 00405 00406 // Now that the official induction variable is established, reinsert 00407 // the old canonical-looking variable after it so that the IR remains 00408 // consistent. It will be deleted as part of the dead-PHI deletion at 00409 // the end of the pass. 00410 if (OldCannIV) 00411 OldCannIV->insertAfter(cast<Instruction>(IndVar)); 00412 } 00413 00414 // If we have a trip count expression, rewrite the loop's exit condition 00415 // using it. We can currently only handle loops with a single exit. 00416 ICmpInst *NewICmp = 0; 00417 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) { 00418 assert(NeedCannIV && 00419 "LinearFunctionTestReplace requires a canonical induction variable"); 00420 // Can't rewrite non-branch yet. 00421 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) 00422 NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 00423 ExitingBlock, BI, Rewriter); 00424 } 00425 00426 // Rewrite IV-derived expressions. Clears the rewriter cache. 00427 RewriteIVExpressions(L, LargestType, Rewriter); 00428 00429 // The Rewriter may not be used from this point on. 00430 00431 // Loop-invariant instructions in the preheader that aren't used in the 00432 // loop may be sunk below the loop to reduce register pressure. 00433 SinkUnusedInvariants(L); 00434 00435 // For completeness, inform IVUsers of the IV use in the newly-created 00436 // loop exit test instruction. 00437 if (NewICmp) 00438 IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0))); 00439 00440 // Clean up dead instructions. 00441 DeleteDeadPHIs(L->getHeader()); 00442 // Check a post-condition. 00443 assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!"); 00444 return Changed; 00445 } 00446 00447 void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType, 00448 SCEVExpander &Rewriter) { 00449 SmallVector<WeakVH, 16> DeadInsts; 00450 00451 // Rewrite all induction variable expressions in terms of the canonical 00452 // induction variable. 00453 // 00454 // If there were induction variables of other sizes or offsets, manually 00455 // add the offsets to the primary induction variable and cast, avoiding 00456 // the need for the code evaluation methods to insert induction variables 00457 // of different sizes. 00458 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) { 00459 const SCEV *Stride = IU->StrideOrder[i]; 00460 00461 std::map<const SCEV *, IVUsersOfOneStride *>::iterator SI = 00462 IU->IVUsesByStride.find(IU->StrideOrder[i]); 00463 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!"); 00464 ilist<IVStrideUse> &List = SI->second->Users; 00465 for (ilist<IVStrideUse>::iterator UI = List.begin(), 00466 E = List.end(); UI != E; ++UI) { 00467 Value *Op = UI->getOperandValToReplace(); 00468 const Type *UseTy = Op->getType(); 00469 Instruction *User = UI->getUser(); 00470 00471 // Compute the final addrec to expand into code. 00472 const SCEV *AR = IU->getReplacementExpr(*UI); 00473 00474 // FIXME: It is an extremely bad idea to indvar substitute anything more 00475 // complex than affine induction variables. Doing so will put expensive 00476 // polynomial evaluations inside of the loop, and the str reduction pass 00477 // currently can only reduce affine polynomials. For now just disable 00478 // indvar subst on anything more complex than an affine addrec, unless 00479 // it can be expanded to a trivial value. 00480 if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L)) 00481 continue; 00482 00483 // Determine the insertion point for this user. By default, insert 00484 // immediately before the user. The SCEVExpander class will automatically 00485 // hoist loop invariants out of the loop. For PHI nodes, there may be 00486 // multiple uses, so compute the nearest common dominator for the 00487 // incoming blocks. 00488 Instruction *InsertPt = User; 00489 if (PHINode *PHI = dyn_cast<PHINode>(InsertPt)) 00490 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 00491 if (PHI->getIncomingValue(i) == Op) { 00492 if (InsertPt == User) 00493 InsertPt = PHI->getIncomingBlock(i)->getTerminator(); 00494 else 00495 InsertPt = 00496 DT->findNearestCommonDominator(InsertPt->getParent(), 00497 PHI->getIncomingBlock(i)) 00498 ->getTerminator(); 00499 } 00500 00501 // Now expand it into actual Instructions and patch it into place. 00502 Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt); 00503 00504 // Patch the new value into place. 00505 if (Op->hasName()) 00506 NewVal->takeName(Op); 00507 User->replaceUsesOfWith(Op, NewVal); 00508 UI->setOperandValToReplace(NewVal); 00509 DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op << '\n' 00510 << " into = " << *NewVal << "\n"; 00511 ++NumRemoved; 00512 Changed = true; 00513 00514 // The old value may be dead now. 00515 DeadInsts.push_back(Op); 00516 } 00517 } 00518 00519 // Clear the rewriter cache, because values that are in the rewriter's cache 00520 // can be deleted in the loop below, causing the AssertingVH in the cache to 00521 // trigger. 00522 Rewriter.clear(); 00523 // Now that we're done iterating through lists, clean up any instructions 00524 // which are now dead. 00525 while (!DeadInsts.empty()) { 00526 Instruction *Inst = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()); 00527 if (Inst) 00528 RecursivelyDeleteTriviallyDeadInstructions(Inst); 00529 } 00530 } 00531 00532 /// If there's a single exit block, sink any loop-invariant values that 00533 /// were defined in the preheader but not used inside the loop into the 00534 /// exit block to reduce register pressure in the loop. 00535 void IndVarSimplify::SinkUnusedInvariants(Loop *L) { 00536 BasicBlock *ExitBlock = L->getExitBlock(); 00537 if (!ExitBlock) return; 00538 00539 Instruction *InsertPt = ExitBlock->getFirstNonPHI(); 00540 BasicBlock *Preheader = L->getLoopPreheader(); 00541 BasicBlock::iterator I = Preheader->getTerminator(); 00542 while (I != Preheader->begin()) { 00543 --I; 00544 // New instructions were inserted at the end of the preheader. 00545 if (isa<PHINode>(I)) 00546 break; 00547 // Don't move instructions which might have side effects, since the side 00548 // effects need to complete before instructions inside the loop. Also 00549 // don't move instructions which might read memory, since the loop may 00550 // modify memory. Note that it's okay if the instruction might have 00551 // undefined behavior: LoopSimplify guarantees that the preheader 00552 // dominates the exit block. 00553 if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 00554 continue; 00555 // Don't sink static AllocaInsts out of the entry block, which would 00556 // turn them into dynamic allocas! 00557 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 00558 if (AI->isStaticAlloca()) 00559 continue; 00560 // Determine if there is a use in or before the loop (direct or 00561 // otherwise). 00562 bool UsedInLoop = false; 00563 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 00564 UI != UE; ++UI) { 00565 BasicBlock *UseBB = cast<Instruction>(UI)->getParent(); 00566 if (PHINode *P = dyn_cast<PHINode>(UI)) { 00567 unsigned i = 00568 PHINode::getIncomingValueNumForOperand(UI.getOperandNo()); 00569 UseBB = P->getIncomingBlock(i); 00570 } 00571 if (UseBB == Preheader || L->contains(UseBB)) { 00572 UsedInLoop = true; 00573 break; 00574 } 00575 } 00576 // If there is, the def must remain in the preheader. 00577 if (UsedInLoop) 00578 continue; 00579 // Otherwise, sink it to the exit block. 00580 Instruction *ToMove = I; 00581 bool Done = false; 00582 if (I != Preheader->begin()) 00583 --I; 00584 else 00585 Done = true; 00586 ToMove->moveBefore(InsertPt); 00587 if (Done) 00588 break; 00589 InsertPt = ToMove; 00590 } 00591 } 00592 00593 /// Return true if it is OK to use SIToFPInst for an inducation variable 00594 /// with given inital and exit values. 00595 static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV, 00596 uint64_t intIV, uint64_t intEV) { 00597 00598 if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative()) 00599 return true; 00600 00601 // If the iteration range can be handled by SIToFPInst then use it. 00602 APInt Max = APInt::getSignedMaxValue(32); 00603 if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV))) 00604 return true; 00605 00606 return false; 00607 } 00608 00609 /// convertToInt - Convert APF to an integer, if possible. 00610 static bool convertToInt(const APFloat &APF, uint64_t *intVal) { 00611 00612 bool isExact = false; 00613 if (&APF.getSemantics() == &APFloat::PPCDoubleDouble) 00614 return false; 00615 if (APF.convertToInteger(intVal, 32, APF.isNegative(), 00616 APFloat::rmTowardZero, &isExact) 00617 != APFloat::opOK) 00618 return false; 00619 if (!isExact) 00620 return false; 00621 return true; 00622 00623 } 00624 00625 /// HandleFloatingPointIV - If the loop has floating induction variable 00626 /// then insert corresponding integer induction variable if possible. 00627 /// For example, 00628 /// for(double i = 0; i < 10000; ++i) 00629 /// bar(i) 00630 /// is converted into 00631 /// for(int i = 0; i < 10000; ++i) 00632 /// bar((double)i); 00633 /// 00634 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) { 00635 00636 unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0)); 00637 unsigned BackEdge = IncomingEdge^1; 00638 00639 // Check incoming value. 00640 ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge)); 00641 if (!InitValue) return; 00642 uint64_t newInitValue = 00643 Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 00644 if (!convertToInt(InitValue->getValueAPF(), &newInitValue)) 00645 return; 00646 00647 // Check IV increment. Reject this PH if increement operation is not 00648 // an add or increment value can not be represented by an integer. 00649 BinaryOperator *Incr = 00650 dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge)); 00651 if (!Incr) return; 00652 if (Incr->getOpcode() != Instruction::FAdd) return; 00653 ConstantFP *IncrValue = NULL; 00654 unsigned IncrVIndex = 1; 00655 if (Incr->getOperand(1) == PH) 00656 IncrVIndex = 0; 00657 IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex)); 00658 if (!IncrValue) return; 00659 uint64_t newIncrValue = 00660 Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 00661 if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue)) 00662 return; 00663 00664 // Check Incr uses. One user is PH and the other users is exit condition used 00665 // by the conditional terminator. 00666 Value::use_iterator IncrUse = Incr->use_begin(); 00667 Instruction *U1 = cast<Instruction>(IncrUse++); 00668 if (IncrUse == Incr->use_end()) return; 00669 Instruction *U2 = cast<Instruction>(IncrUse++); 00670 if (IncrUse != Incr->use_end()) return; 00671 00672 // Find exit condition. 00673 FCmpInst *EC = dyn_cast<FCmpInst>(U1); 00674 if (!EC) 00675 EC = dyn_cast<FCmpInst>(U2); 00676 if (!EC) return; 00677 00678 if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) { 00679 if (!BI->isConditional()) return; 00680 if (BI->getCondition() != EC) return; 00681 } 00682 00683 // Find exit value. If exit value can not be represented as an interger then 00684 // do not handle this floating point PH. 00685 ConstantFP *EV = NULL; 00686 unsigned EVIndex = 1; 00687 if (EC->getOperand(1) == Incr) 00688 EVIndex = 0; 00689 EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex)); 00690 if (!EV) return; 00691 uint64_t intEV = Type::getInt32Ty(PH->getContext())->getPrimitiveSizeInBits(); 00692 if (!convertToInt(EV->getValueAPF(), &intEV)) 00693 return; 00694 00695 // Find new predicate for integer comparison. 00696 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 00697 switch (EC->getPredicate()) { 00698 case CmpInst::FCMP_OEQ: 00699 case CmpInst::FCMP_UEQ: 00700 NewPred = CmpInst::ICMP_EQ; 00701 break; 00702 case CmpInst::FCMP_OGT: 00703 case CmpInst::FCMP_UGT: 00704 NewPred = CmpInst::ICMP_UGT; 00705 break; 00706 case CmpInst::FCMP_OGE: 00707 case CmpInst::FCMP_UGE: 00708 NewPred = CmpInst::ICMP_UGE; 00709 break; 00710 case CmpInst::FCMP_OLT: 00711 case CmpInst::FCMP_ULT: 00712 NewPred = CmpInst::ICMP_ULT; 00713 break; 00714 case CmpInst::FCMP_OLE: 00715 case CmpInst::FCMP_ULE: 00716 NewPred = CmpInst::ICMP_ULE; 00717 break; 00718 default: 00719 break; 00720 } 00721 if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return; 00722 00723 // Insert new integer induction variable. 00724 PHINode *NewPHI = PHINode::Create(Type::getInt32Ty(PH->getContext()), 00725 PH->getName()+".int", PH); 00726 NewPHI->addIncoming(ConstantInt::get(Type::getInt32Ty(PH->getContext()), 00727 newInitValue), 00728 PH->getIncomingBlock(IncomingEdge)); 00729 00730 Value *NewAdd = BinaryOperator::CreateAdd(NewPHI, 00731 ConstantInt::get(Type::getInt32Ty(PH->getContext()), 00732 newIncrValue), 00733 Incr->getName()+".int", Incr); 00734 NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge)); 00735 00736 // The back edge is edge 1 of newPHI, whatever it may have been in the 00737 // original PHI. 00738 ConstantInt *NewEV = ConstantInt::get(Type::getInt32Ty(PH->getContext()), 00739 intEV); 00740 Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV); 00741 Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1)); 00742 ICmpInst *NewEC = new ICmpInst(EC->getParent()->getTerminator(), 00743 NewPred, LHS, RHS, EC->getName()); 00744 00745 // In the following deltions, PH may become dead and may be deleted. 00746 // Use a WeakVH to observe whether this happens. 00747 WeakVH WeakPH = PH; 00748 00749 // Delete old, floating point, exit comparision instruction. 00750 NewEC->takeName(EC); 00751 EC->replaceAllUsesWith(NewEC); 00752 RecursivelyDeleteTriviallyDeadInstructions(EC); 00753 00754 // Delete old, floating point, increment instruction. 00755 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 00756 RecursivelyDeleteTriviallyDeadInstructions(Incr); 00757 00758 // Replace floating induction variable, if it isn't already deleted. 00759 // Give SIToFPInst preference over UIToFPInst because it is faster on 00760 // platforms that are widely used. 00761 if (WeakPH && !PH->use_empty()) { 00762 if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) { 00763 SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv", 00764 PH->getParent()->getFirstNonPHI()); 00765 PH->replaceAllUsesWith(Conv); 00766 } else { 00767 UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv", 00768 PH->getParent()->getFirstNonPHI()); 00769 PH->replaceAllUsesWith(Conv); 00770 } 00771 RecursivelyDeleteTriviallyDeadInstructions(PH); 00772 } 00773 00774 // Add a new IVUsers entry for the newly-created integer PHI. 00775 IU->AddUsersIfInteresting(NewPHI); 00776 }