LLVM API Documentation
00001 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source 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 make 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. Any pointer arithmetic recurrences are raised to use array subscripts. 00021 // 00022 // If the trip count of a loop is computable, this pass also makes the following 00023 // changes: 00024 // 1. The exit condition for the loop is canonicalized to compare the 00025 // induction value against the exit value. This turns loops like: 00026 // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 00027 // 2. Any use outside of the loop of an expression derived from the indvar 00028 // is changed to compute the derived value outside of the loop, eliminating 00029 // the dependence on the exit value of the induction variable. If the only 00030 // purpose of the loop is to compute the exit value of some derived 00031 // expression, this transformation will make the loop dead. 00032 // 00033 // This transformation should be followed by strength reduction after all of the 00034 // desired loop transformations have been performed. Additionally, on targets 00035 // where it is profitable, the loop could be transformed to count down to zero 00036 // (the "do loop" optimization). 00037 // 00038 //===----------------------------------------------------------------------===// 00039 00040 #include "llvm/Transforms/Scalar.h" 00041 #include "llvm/BasicBlock.h" 00042 #include "llvm/Constants.h" 00043 #include "llvm/Instructions.h" 00044 #include "llvm/Type.h" 00045 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 00046 #include "llvm/Analysis/LoopInfo.h" 00047 #include "llvm/Support/CFG.h" 00048 #include "llvm/Support/GetElementPtrTypeIterator.h" 00049 #include "llvm/Transforms/Utils/Local.h" 00050 #include "llvm/Support/CommandLine.h" 00051 #include "llvm/ADT/Statistic.h" 00052 using namespace llvm; 00053 00054 namespace { 00055 /// SCEVExpander - This class uses information about analyze scalars to 00056 /// rewrite expressions in canonical form. 00057 /// 00058 /// Clients should create an instance of this class when rewriting is needed, 00059 /// and destroying it when finished to allow the release of the associated 00060 /// memory. 00061 struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { 00062 ScalarEvolution &SE; 00063 LoopInfo &LI; 00064 std::map<SCEVHandle, Value*> InsertedExpressions; 00065 std::set<Instruction*> InsertedInstructions; 00066 00067 Instruction *InsertPt; 00068 00069 friend struct SCEVVisitor<SCEVExpander, Value*>; 00070 public: 00071 SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {} 00072 00073 /// isInsertedInstruction - Return true if the specified instruction was 00074 /// inserted by the code rewriter. If so, the client should not modify the 00075 /// instruction. 00076 bool isInsertedInstruction(Instruction *I) const { 00077 return InsertedInstructions.count(I); 00078 } 00079 00080 /// getOrInsertCanonicalInductionVariable - This method returns the 00081 /// canonical induction variable of the specified type for the specified 00082 /// loop (inserting one if there is none). A canonical induction variable 00083 /// starts at zero and steps by one on each iteration. 00084 Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ 00085 assert((Ty->isInteger() || Ty->isFloatingPoint()) && 00086 "Can only insert integer or floating point induction variables!"); 00087 SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty), 00088 SCEVUnknown::getIntegerSCEV(1, Ty), L); 00089 return expand(H); 00090 } 00091 00092 /// addInsertedValue - Remember the specified instruction as being the 00093 /// canonical form for the specified SCEV. 00094 void addInsertedValue(Instruction *I, SCEV *S) { 00095 InsertedExpressions[S] = (Value*)I; 00096 InsertedInstructions.insert(I); 00097 } 00098 00099 /// expandCodeFor - Insert code to directly compute the specified SCEV 00100 /// expression into the program. The inserted code is inserted into the 00101 /// specified block. 00102 /// 00103 /// If a particular value sign is required, a type may be specified for the 00104 /// result. 00105 Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) { 00106 // Expand the code for this SCEV. 00107 this->InsertPt = IP; 00108 return expandInTy(SH, Ty); 00109 } 00110 00111 protected: 00112 Value *expand(SCEV *S) { 00113 // Check to see if we already expanded this. 00114 std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S); 00115 if (I != InsertedExpressions.end()) 00116 return I->second; 00117 00118 Value *V = visit(S); 00119 InsertedExpressions[S] = V; 00120 return V; 00121 } 00122 00123 Value *expandInTy(SCEV *S, const Type *Ty) { 00124 Value *V = expand(S); 00125 if (Ty && V->getType() != Ty) { 00126 // FIXME: keep track of the cast instruction. 00127 if (Constant *C = dyn_cast<Constant>(V)) 00128 return ConstantExpr::getCast(C, Ty); 00129 else if (Instruction *I = dyn_cast<Instruction>(V)) { 00130 // Check to see if there is already a cast. If there is, use it. 00131 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00132 UI != E; ++UI) { 00133 if ((*UI)->getType() == Ty) 00134 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) { 00135 BasicBlock::iterator It = I; ++It; 00136 while (isa<PHINode>(It)) ++It; 00137 if (It != BasicBlock::iterator(CI)) { 00138 // Splice the cast immediately after the operand in question. 00139 BasicBlock::InstListType &InstList = 00140 I->getParent()->getInstList(); 00141 InstList.splice(It, CI->getParent()->getInstList(), CI); 00142 } 00143 return CI; 00144 } 00145 } 00146 BasicBlock::iterator IP = I; ++IP; 00147 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 00148 IP = II->getNormalDest()->begin(); 00149 while (isa<PHINode>(IP)) ++IP; 00150 return new CastInst(V, Ty, V->getName(), IP); 00151 } else { 00152 // FIXME: check to see if there is already a cast! 00153 return new CastInst(V, Ty, V->getName(), InsertPt); 00154 } 00155 } 00156 return V; 00157 } 00158 00159 Value *visitConstant(SCEVConstant *S) { 00160 return S->getValue(); 00161 } 00162 00163 Value *visitTruncateExpr(SCEVTruncateExpr *S) { 00164 Value *V = expand(S->getOperand()); 00165 return new CastInst(V, S->getType(), "tmp.", InsertPt); 00166 } 00167 00168 Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) { 00169 Value *V = expandInTy(S->getOperand(),S->getType()->getUnsignedVersion()); 00170 return new CastInst(V, S->getType(), "tmp.", InsertPt); 00171 } 00172 00173 Value *visitAddExpr(SCEVAddExpr *S) { 00174 const Type *Ty = S->getType(); 00175 Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty); 00176 00177 // Emit a bunch of add instructions 00178 for (int i = S->getNumOperands()-2; i >= 0; --i) 00179 V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty), 00180 "tmp.", InsertPt); 00181 return V; 00182 } 00183 00184 Value *visitMulExpr(SCEVMulExpr *S); 00185 00186 Value *visitUDivExpr(SCEVUDivExpr *S) { 00187 const Type *Ty = S->getType(); 00188 Value *LHS = expandInTy(S->getLHS(), Ty); 00189 Value *RHS = expandInTy(S->getRHS(), Ty); 00190 return BinaryOperator::createDiv(LHS, RHS, "tmp.", InsertPt); 00191 } 00192 00193 Value *visitAddRecExpr(SCEVAddRecExpr *S); 00194 00195 Value *visitUnknown(SCEVUnknown *S) { 00196 return S->getValue(); 00197 } 00198 }; 00199 } 00200 00201 Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) { 00202 const Type *Ty = S->getType(); 00203 int FirstOp = 0; // Set if we should emit a subtract. 00204 if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 00205 if (SC->getValue()->isAllOnesValue()) 00206 FirstOp = 1; 00207 00208 int i = S->getNumOperands()-2; 00209 Value *V = expandInTy(S->getOperand(i+1), Ty); 00210 00211 // Emit a bunch of multiply instructions 00212 for (; i >= FirstOp; --i) 00213 V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty), 00214 "tmp.", InsertPt); 00215 // -1 * ... ---> 0 - ... 00216 if (FirstOp == 1) 00217 V = BinaryOperator::createNeg(V, "tmp.", InsertPt); 00218 return V; 00219 } 00220 00221 Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { 00222 const Type *Ty = S->getType(); 00223 const Loop *L = S->getLoop(); 00224 // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} 00225 assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!"); 00226 00227 // {X,+,F} --> X + {0,+,F} 00228 if (!isa<SCEVConstant>(S->getStart()) || 00229 !cast<SCEVConstant>(S->getStart())->getValue()->isNullValue()) { 00230 Value *Start = expandInTy(S->getStart(), Ty); 00231 std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end()); 00232 NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty); 00233 Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty); 00234 00235 // FIXME: look for an existing add to use. 00236 return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt); 00237 } 00238 00239 // {0,+,1} --> Insert a canonical induction variable into the loop! 00240 if (S->getNumOperands() == 2 && 00241 S->getOperand(1) == SCEVUnknown::getIntegerSCEV(1, Ty)) { 00242 // Create and insert the PHI node for the induction variable in the 00243 // specified loop. 00244 BasicBlock *Header = L->getHeader(); 00245 PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); 00246 PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 00247 00248 pred_iterator HPI = pred_begin(Header); 00249 assert(HPI != pred_end(Header) && "Loop with zero preds???"); 00250 if (!L->contains(*HPI)) ++HPI; 00251 assert(HPI != pred_end(Header) && L->contains(*HPI) && 00252 "No backedge in loop?"); 00253 00254 // Insert a unit add instruction right before the terminator corresponding 00255 // to the back-edge. 00256 Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0) 00257 : ConstantInt::get(Ty, 1); 00258 Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next", 00259 (*HPI)->getTerminator()); 00260 00261 pred_iterator PI = pred_begin(Header); 00262 if (*PI == L->getLoopPreheader()) 00263 ++PI; 00264 PN->addIncoming(Add, *PI); 00265 return PN; 00266 } 00267 00268 // Get the canonical induction variable I for this loop. 00269 Value *I = getOrInsertCanonicalInductionVariable(L, Ty); 00270 00271 if (S->getNumOperands() == 2) { // {0,+,F} --> i*F 00272 Value *F = expandInTy(S->getOperand(1), Ty); 00273 return BinaryOperator::createMul(I, F, "tmp.", InsertPt); 00274 } 00275 00276 // If this is a chain of recurrences, turn it into a closed form, using the 00277 // folders, then expandCodeFor the closed form. This allows the folders to 00278 // simplify the expression without having to build a bunch of special code 00279 // into this folder. 00280 SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. 00281 00282 SCEVHandle V = S->evaluateAtIteration(IH); 00283 //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 00284 00285 return expandInTy(V, Ty); 00286 } 00287 00288 00289 namespace { 00290 Statistic<> NumRemoved ("indvars", "Number of aux indvars removed"); 00291 Statistic<> NumPointer ("indvars", "Number of pointer indvars promoted"); 00292 Statistic<> NumInserted("indvars", "Number of canonical indvars added"); 00293 Statistic<> NumReplaced("indvars", "Number of exit values replaced"); 00294 Statistic<> NumLFTR ("indvars", "Number of loop exit tests replaced"); 00295 00296 class IndVarSimplify : public FunctionPass { 00297 LoopInfo *LI; 00298 ScalarEvolution *SE; 00299 bool Changed; 00300 public: 00301 virtual bool runOnFunction(Function &) { 00302 LI = &getAnalysis<LoopInfo>(); 00303 SE = &getAnalysis<ScalarEvolution>(); 00304 Changed = false; 00305 00306 // Induction Variables live in the header nodes of loops 00307 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 00308 runOnLoop(*I); 00309 return Changed; 00310 } 00311 00312 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00313 AU.addRequiredID(LoopSimplifyID); 00314 AU.addRequired<ScalarEvolution>(); 00315 AU.addRequired<LoopInfo>(); 00316 AU.addPreservedID(LoopSimplifyID); 00317 AU.setPreservesCFG(); 00318 } 00319 private: 00320 void runOnLoop(Loop *L); 00321 void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader, 00322 std::set<Instruction*> &DeadInsts); 00323 void LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, 00324 SCEVExpander &RW); 00325 void RewriteLoopExitValues(Loop *L); 00326 00327 void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts); 00328 }; 00329 RegisterOpt<IndVarSimplify> X("indvars", "Canonicalize Induction Variables"); 00330 } 00331 00332 FunctionPass *llvm::createIndVarSimplifyPass() { 00333 return new IndVarSimplify(); 00334 } 00335 00336 /// DeleteTriviallyDeadInstructions - If any of the instructions is the 00337 /// specified set are trivially dead, delete them and see if this makes any of 00338 /// their operands subsequently dead. 00339 void IndVarSimplify:: 00340 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) { 00341 while (!Insts.empty()) { 00342 Instruction *I = *Insts.begin(); 00343 Insts.erase(Insts.begin()); 00344 if (isInstructionTriviallyDead(I)) { 00345 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00346 if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 00347 Insts.insert(U); 00348 SE->deleteInstructionFromRecords(I); 00349 I->eraseFromParent(); 00350 Changed = true; 00351 } 00352 } 00353 } 00354 00355 00356 /// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer 00357 /// recurrence. If so, change it into an integer recurrence, permitting 00358 /// analysis by the SCEV routines. 00359 void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN, 00360 BasicBlock *Preheader, 00361 std::set<Instruction*> &DeadInsts) { 00362 assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!"); 00363 unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader); 00364 unsigned BackedgeIdx = PreheaderIdx^1; 00365 if (GetElementPtrInst *GEPI = 00366 dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx))) 00367 if (GEPI->getOperand(0) == PN) { 00368 assert(GEPI->getNumOperands() == 2 && "GEP types must mismatch!"); 00369 00370 // Okay, we found a pointer recurrence. Transform this pointer 00371 // recurrence into an integer recurrence. Compute the value that gets 00372 // added to the pointer at every iteration. 00373 Value *AddedVal = GEPI->getOperand(1); 00374 00375 // Insert a new integer PHI node into the top of the block. 00376 PHINode *NewPhi = new PHINode(AddedVal->getType(), 00377 PN->getName()+".rec", PN); 00378 NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader); 00379 00380 // Create the new add instruction. 00381 Value *NewAdd = BinaryOperator::createAdd(NewPhi, AddedVal, 00382 GEPI->getName()+".rec", GEPI); 00383 NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx)); 00384 00385 // Update the existing GEP to use the recurrence. 00386 GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx)); 00387 00388 // Update the GEP to use the new recurrence we just inserted. 00389 GEPI->setOperand(1, NewAdd); 00390 00391 // If the incoming value is a constant expr GEP, try peeling out the array 00392 // 0 index if possible to make things simpler. 00393 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0))) 00394 if (CE->getOpcode() == Instruction::GetElementPtr) { 00395 unsigned NumOps = CE->getNumOperands(); 00396 assert(NumOps > 1 && "CE folding didn't work!"); 00397 if (CE->getOperand(NumOps-1)->isNullValue()) { 00398 // Check to make sure the last index really is an array index. 00399 gep_type_iterator GTI = gep_type_begin(GEPI); 00400 for (unsigned i = 1, e = GEPI->getNumOperands()-1; 00401 i != e; ++i, ++GTI) 00402 /*empty*/; 00403 if (isa<SequentialType>(*GTI)) { 00404 // Pull the last index out of the constant expr GEP. 00405 std::vector<Value*> CEIdxs(CE->op_begin()+1, CE->op_end()-1); 00406 Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0), 00407 CEIdxs); 00408 GetElementPtrInst *NGEPI = 00409 new GetElementPtrInst(NCE, Constant::getNullValue(Type::IntTy), 00410 NewAdd, GEPI->getName(), GEPI); 00411 GEPI->replaceAllUsesWith(NGEPI); 00412 GEPI->eraseFromParent(); 00413 GEPI = NGEPI; 00414 } 00415 } 00416 } 00417 00418 00419 // Finally, if there are any other users of the PHI node, we must 00420 // insert a new GEP instruction that uses the pre-incremented version 00421 // of the induction amount. 00422 if (!PN->use_empty()) { 00423 BasicBlock::iterator InsertPos = PN; ++InsertPos; 00424 while (isa<PHINode>(InsertPos)) ++InsertPos; 00425 std::string Name = PN->getName(); PN->setName(""); 00426 Value *PreInc = 00427 new GetElementPtrInst(PN->getIncomingValue(PreheaderIdx), 00428 std::vector<Value*>(1, NewPhi), Name, 00429 InsertPos); 00430 PN->replaceAllUsesWith(PreInc); 00431 } 00432 00433 // Delete the old PHI for sure, and the GEP if its otherwise unused. 00434 DeadInsts.insert(PN); 00435 00436 ++NumPointer; 00437 Changed = true; 00438 } 00439 } 00440 00441 /// LinearFunctionTestReplace - This method rewrites the exit condition of the 00442 /// loop to be a canonical != comparison against the incremented loop induction 00443 /// variable. This pass is able to rewrite the exit tests of any loop where the 00444 /// SCEV analysis can determine a loop-invariant trip count of the loop, which 00445 /// is actually a much broader range than just linear tests. 00446 void IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEV *IterationCount, 00447 SCEVExpander &RW) { 00448 // Find the exit block for the loop. We can currently only handle loops with 00449 // a single exit. 00450 std::vector<BasicBlock*> ExitBlocks; 00451 L->getExitBlocks(ExitBlocks); 00452 if (ExitBlocks.size() != 1) return; 00453 BasicBlock *ExitBlock = ExitBlocks[0]; 00454 00455 // Make sure there is only one predecessor block in the loop. 00456 BasicBlock *ExitingBlock = 0; 00457 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 00458 PI != PE; ++PI) 00459 if (L->contains(*PI)) { 00460 if (ExitingBlock == 0) 00461 ExitingBlock = *PI; 00462 else 00463 return; // Multiple exits from loop to this block. 00464 } 00465 assert(ExitingBlock && "Loop info is broken"); 00466 00467 if (!isa<BranchInst>(ExitingBlock->getTerminator())) 00468 return; // Can't rewrite non-branch yet 00469 BranchInst *BI = cast<BranchInst>(ExitingBlock->getTerminator()); 00470 assert(BI->isConditional() && "Must be conditional to be part of loop!"); 00471 00472 std::set<Instruction*> InstructionsToDelete; 00473 if (Instruction *Cond = dyn_cast<Instruction>(BI->getCondition())) 00474 InstructionsToDelete.insert(Cond); 00475 00476 // If the exiting block is not the same as the backedge block, we must compare 00477 // against the preincremented value, otherwise we prefer to compare against 00478 // the post-incremented value. 00479 BasicBlock *Header = L->getHeader(); 00480 pred_iterator HPI = pred_begin(Header); 00481 assert(HPI != pred_end(Header) && "Loop with zero preds???"); 00482 if (!L->contains(*HPI)) ++HPI; 00483 assert(HPI != pred_end(Header) && L->contains(*HPI) && 00484 "No backedge in loop?"); 00485 00486 SCEVHandle TripCount = IterationCount; 00487 Value *IndVar; 00488 if (*HPI == ExitingBlock) { 00489 // The IterationCount expression contains the number of times that the 00490 // backedge actually branches to the loop header. This is one less than the 00491 // number of times the loop executes, so add one to it. 00492 Constant *OneC = ConstantInt::get(IterationCount->getType(), 1); 00493 TripCount = SCEVAddExpr::get(IterationCount, SCEVUnknown::get(OneC)); 00494 IndVar = L->getCanonicalInductionVariableIncrement(); 00495 } else { 00496 // We have to use the preincremented value... 00497 IndVar = L->getCanonicalInductionVariable(); 00498 } 00499 00500 // Expand the code for the iteration count into the preheader of the loop. 00501 BasicBlock *Preheader = L->getLoopPreheader(); 00502 Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator(), 00503 IndVar->getType()); 00504 00505 // Insert a new setne or seteq instruction before the branch. 00506 Instruction::BinaryOps Opcode; 00507 if (L->contains(BI->getSuccessor(0))) 00508 Opcode = Instruction::SetNE; 00509 else 00510 Opcode = Instruction::SetEQ; 00511 00512 Value *Cond = new SetCondInst(Opcode, IndVar, ExitCnt, "exitcond", BI); 00513 BI->setCondition(Cond); 00514 ++NumLFTR; 00515 Changed = true; 00516 00517 DeleteTriviallyDeadInstructions(InstructionsToDelete); 00518 } 00519 00520 00521 /// RewriteLoopExitValues - Check to see if this loop has a computable 00522 /// loop-invariant execution count. If so, this means that we can compute the 00523 /// final value of any expressions that are recurrent in the loop, and 00524 /// substitute the exit values from the loop into any instructions outside of 00525 /// the loop that use the final values of the current expressions. 00526 void IndVarSimplify::RewriteLoopExitValues(Loop *L) { 00527 BasicBlock *Preheader = L->getLoopPreheader(); 00528 00529 // Scan all of the instructions in the loop, looking at those that have 00530 // extra-loop users and which are recurrences. 00531 SCEVExpander Rewriter(*SE, *LI); 00532 00533 // We insert the code into the preheader of the loop if the loop contains 00534 // multiple exit blocks, or in the exit block if there is exactly one. 00535 BasicBlock *BlockToInsertInto; 00536 std::vector<BasicBlock*> ExitBlocks; 00537 L->getExitBlocks(ExitBlocks); 00538 if (ExitBlocks.size() == 1) 00539 BlockToInsertInto = ExitBlocks[0]; 00540 else 00541 BlockToInsertInto = Preheader; 00542 BasicBlock::iterator InsertPt = BlockToInsertInto->begin(); 00543 while (isa<PHINode>(InsertPt)) ++InsertPt; 00544 00545 bool HasConstantItCount = isa<SCEVConstant>(SE->getIterationCount(L)); 00546 00547 std::set<Instruction*> InstructionsToDelete; 00548 00549 for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 00550 if (LI->getLoopFor(L->getBlocks()[i]) == L) { // Not in a subloop... 00551 BasicBlock *BB = L->getBlocks()[i]; 00552 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00553 if (I->getType()->isInteger()) { // Is an integer instruction 00554 SCEVHandle SH = SE->getSCEV(I); 00555 if (SH->hasComputableLoopEvolution(L) || // Varies predictably 00556 HasConstantItCount) { 00557 // Find out if this predictably varying value is actually used 00558 // outside of the loop. "extra" as opposed to "intra". 00559 std::vector<User*> ExtraLoopUsers; 00560 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00561 UI != E; ++UI) 00562 if (!L->contains(cast<Instruction>(*UI)->getParent())) 00563 ExtraLoopUsers.push_back(*UI); 00564 if (!ExtraLoopUsers.empty()) { 00565 // Okay, this instruction has a user outside of the current loop 00566 // and varies predictably in this loop. Evaluate the value it 00567 // contains when the loop exits, and insert code for it. 00568 SCEVHandle ExitValue = SE->getSCEVAtScope(I, L->getParentLoop()); 00569 if (!isa<SCEVCouldNotCompute>(ExitValue)) { 00570 Changed = true; 00571 ++NumReplaced; 00572 Value *NewVal = Rewriter.expandCodeFor(ExitValue, InsertPt, 00573 I->getType()); 00574 00575 // Rewrite any users of the computed value outside of the loop 00576 // with the newly computed value. 00577 for (unsigned i = 0, e = ExtraLoopUsers.size(); i != e; ++i) 00578 ExtraLoopUsers[i]->replaceUsesOfWith(I, NewVal); 00579 00580 // If this instruction is dead now, schedule it to be removed. 00581 if (I->use_empty()) 00582 InstructionsToDelete.insert(I); 00583 } 00584 } 00585 } 00586 } 00587 } 00588 00589 DeleteTriviallyDeadInstructions(InstructionsToDelete); 00590 } 00591 00592 00593 void IndVarSimplify::runOnLoop(Loop *L) { 00594 // First step. Check to see if there are any trivial GEP pointer recurrences. 00595 // If there are, change them into integer recurrences, permitting analysis by 00596 // the SCEV routines. 00597 // 00598 BasicBlock *Header = L->getHeader(); 00599 BasicBlock *Preheader = L->getLoopPreheader(); 00600 00601 std::set<Instruction*> DeadInsts; 00602 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 00603 PHINode *PN = cast<PHINode>(I); 00604 if (isa<PointerType>(PN->getType())) 00605 EliminatePointerRecurrence(PN, Preheader, DeadInsts); 00606 } 00607 00608 if (!DeadInsts.empty()) 00609 DeleteTriviallyDeadInstructions(DeadInsts); 00610 00611 00612 // Next, transform all loops nesting inside of this loop. 00613 for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I) 00614 runOnLoop(*I); 00615 00616 // Check to see if this loop has a computable loop-invariant execution count. 00617 // If so, this means that we can compute the final value of any expressions 00618 // that are recurrent in the loop, and substitute the exit values from the 00619 // loop into any instructions outside of the loop that use the final values of 00620 // the current expressions. 00621 // 00622 SCEVHandle IterationCount = SE->getIterationCount(L); 00623 if (!isa<SCEVCouldNotCompute>(IterationCount)) 00624 RewriteLoopExitValues(L); 00625 00626 // Next, analyze all of the induction variables in the loop, canonicalizing 00627 // auxillary induction variables. 00628 std::vector<std::pair<PHINode*, SCEVHandle> > IndVars; 00629 00630 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 00631 PHINode *PN = cast<PHINode>(I); 00632 if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable! 00633 SCEVHandle SCEV = SE->getSCEV(PN); 00634 if (SCEV->hasComputableLoopEvolution(L)) 00635 // FIXME: Without a strength reduction pass, it is an extremely bad idea 00636 // to indvar substitute anything more complex than a linear induction 00637 // variable. Doing so will put expensive multiply instructions inside 00638 // of the loop. For now just disable indvar subst on anything more 00639 // complex than a linear addrec. 00640 if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV)) 00641 if (AR->getNumOperands() == 2 && isa<SCEVConstant>(AR->getOperand(1))) 00642 IndVars.push_back(std::make_pair(PN, SCEV)); 00643 } 00644 } 00645 00646 // If there are no induction variables in the loop, there is nothing more to 00647 // do. 00648 if (IndVars.empty()) { 00649 // Actually, if we know how many times the loop iterates, lets insert a 00650 // canonical induction variable to help subsequent passes. 00651 if (!isa<SCEVCouldNotCompute>(IterationCount)) { 00652 SCEVExpander Rewriter(*SE, *LI); 00653 Rewriter.getOrInsertCanonicalInductionVariable(L, 00654 IterationCount->getType()); 00655 LinearFunctionTestReplace(L, IterationCount, Rewriter); 00656 } 00657 return; 00658 } 00659 00660 // Compute the type of the largest recurrence expression. 00661 // 00662 const Type *LargestType = IndVars[0].first->getType(); 00663 bool DifferingSizes = false; 00664 for (unsigned i = 1, e = IndVars.size(); i != e; ++i) { 00665 const Type *Ty = IndVars[i].first->getType(); 00666 DifferingSizes |= Ty->getPrimitiveSize() != LargestType->getPrimitiveSize(); 00667 if (Ty->getPrimitiveSize() > LargestType->getPrimitiveSize()) 00668 LargestType = Ty; 00669 } 00670 00671 // Create a rewriter object which we'll use to transform the code with. 00672 SCEVExpander Rewriter(*SE, *LI); 00673 00674 // Now that we know the largest of of the induction variables in this loop, 00675 // insert a canonical induction variable of the largest size. 00676 LargestType = LargestType->getUnsignedVersion(); 00677 Value *IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType); 00678 ++NumInserted; 00679 Changed = true; 00680 00681 if (!isa<SCEVCouldNotCompute>(IterationCount)) 00682 LinearFunctionTestReplace(L, IterationCount, Rewriter); 00683 00684 // Now that we have a canonical induction variable, we can rewrite any 00685 // recurrences in terms of the induction variable. Start with the auxillary 00686 // induction variables, and recursively rewrite any of their uses. 00687 BasicBlock::iterator InsertPt = Header->begin(); 00688 while (isa<PHINode>(InsertPt)) ++InsertPt; 00689 00690 // If there were induction variables of other sizes, cast the primary 00691 // induction variable to the right size for them, avoiding the need for the 00692 // code evaluation methods to insert induction variables of different sizes. 00693 if (DifferingSizes) { 00694 bool InsertedSizes[17] = { false }; 00695 InsertedSizes[LargestType->getPrimitiveSize()] = true; 00696 for (unsigned i = 0, e = IndVars.size(); i != e; ++i) 00697 if (!InsertedSizes[IndVars[i].first->getType()->getPrimitiveSize()]) { 00698 PHINode *PN = IndVars[i].first; 00699 InsertedSizes[PN->getType()->getPrimitiveSize()] = true; 00700 Instruction *New = new CastInst(IndVar, 00701 PN->getType()->getUnsignedVersion(), 00702 "indvar", InsertPt); 00703 Rewriter.addInsertedValue(New, SE->getSCEV(New)); 00704 } 00705 } 00706 00707 // If there were induction variables of other sizes, cast the primary 00708 // induction variable to the right size for them, avoiding the need for the 00709 // code evaluation methods to insert induction variables of different sizes. 00710 std::map<unsigned, Value*> InsertedSizes; 00711 while (!IndVars.empty()) { 00712 PHINode *PN = IndVars.back().first; 00713 Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt, 00714 PN->getType()); 00715 std::string Name = PN->getName(); 00716 PN->setName(""); 00717 NewVal->setName(Name); 00718 00719 // Replace the old PHI Node with the inserted computation. 00720 PN->replaceAllUsesWith(NewVal); 00721 DeadInsts.insert(PN); 00722 IndVars.pop_back(); 00723 ++NumRemoved; 00724 Changed = true; 00725 } 00726 00727 #if 0 00728 // Now replace all derived expressions in the loop body with simpler 00729 // expressions. 00730 for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 00731 if (LI->getLoopFor(L->getBlocks()[i]) == L) { // Not in a subloop... 00732 BasicBlock *BB = L->getBlocks()[i]; 00733 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00734 if (I->getType()->isInteger() && // Is an integer instruction 00735 !I->use_empty() && 00736 !Rewriter.isInsertedInstruction(I)) { 00737 SCEVHandle SH = SE->getSCEV(I); 00738 Value *V = Rewriter.expandCodeFor(SH, I, I->getType()); 00739 if (V != I) { 00740 if (isa<Instruction>(V)) { 00741 std::string Name = I->getName(); 00742 I->setName(""); 00743 V->setName(Name); 00744 } 00745 I->replaceAllUsesWith(V); 00746 DeadInsts.insert(I); 00747 ++NumRemoved; 00748 Changed = true; 00749 } 00750 } 00751 } 00752 #endif 00753 00754 DeleteTriviallyDeadInstructions(DeadInsts); 00755 }