LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

IndVarSimplify.cpp

Go to the documentation of this file.
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 }