LLVM API Documentation

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

LoopStrengthReduce.cpp

Go to the documentation of this file.
00001 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Nate Begeman and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass performs a strength reduction on array references inside loops that
00011 // have as one or more of their components the loop induction variable.  This is
00012 // accomplished by creating a new Value to hold the initial value of the array
00013 // access for the first iteration, and then creating a new GEP instruction in
00014 // the loop to increment the value by the appropriate amount.
00015 //
00016 // There are currently several deficiencies in the implementation, marked with
00017 // FIXME in the code.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #include "llvm/Transforms/Scalar.h"
00022 #include "llvm/Constants.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/Type.h"
00025 #include "llvm/Analysis/Dominators.h"
00026 #include "llvm/Analysis/LoopInfo.h"
00027 #include "llvm/Support/CFG.h"
00028 #include "llvm/Transforms/Utils/Local.h"
00029 #include "llvm/ADT/Statistic.h"
00030 #include <set>
00031 using namespace llvm;
00032 
00033 namespace {
00034   Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced");
00035 
00036   class LoopStrengthReduce : public FunctionPass {
00037     LoopInfo *LI;
00038     DominatorSet *DS;
00039     bool Changed;
00040   public:
00041     virtual bool runOnFunction(Function &) {
00042       LI = &getAnalysis<LoopInfo>();
00043       DS = &getAnalysis<DominatorSet>();
00044       Changed = false;
00045 
00046       for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
00047         runOnLoop(*I);
00048       return Changed;
00049     }
00050 
00051     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00052       AU.setPreservesCFG();
00053       AU.addRequired<LoopInfo>();
00054       AU.addRequired<DominatorSet>();
00055     }
00056   private:
00057     void runOnLoop(Loop *L);
00058     void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
00059                            Instruction *InsertBefore,
00060                            std::set<Instruction*> &DeadInsts);
00061     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
00062   };
00063   RegisterOpt<LoopStrengthReduce> X("loop-reduce", 
00064                                     "Strength Reduce GEP Uses of Ind. Vars");
00065 }
00066 
00067 FunctionPass *llvm::createLoopStrengthReducePass() {
00068   return new LoopStrengthReduce();
00069 }
00070 
00071 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
00072 /// specified set are trivially dead, delete them and see if this makes any of
00073 /// their operands subsequently dead.
00074 void LoopStrengthReduce::
00075 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
00076   while (!Insts.empty()) {
00077     Instruction *I = *Insts.begin();
00078     Insts.erase(Insts.begin());
00079     if (isInstructionTriviallyDead(I)) {
00080       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
00081         if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
00082           Insts.insert(U);
00083       I->getParent()->getInstList().erase(I);
00084       Changed = true;
00085     }
00086   }
00087 }
00088 
00089 void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
00090                                            Instruction *InsertBefore,
00091                                            std::set<Instruction*> &DeadInsts) {
00092   // We will strength reduce the GEP by splitting it into two parts.  The first
00093   // is a GEP to hold the initial value of the non-strength-reduced GEP upon
00094   // entering the loop, which we will insert at the end of the loop preheader.
00095   // The second is a GEP to hold the incremented value of the initial GEP.
00096   // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so
00097   // we will replace the indvar with a constant zero value to create the first
00098   // GEP.
00099   //
00100   // We currently only handle GEP instructions that consist of zero or more
00101   // constants and one instance of the canonical induction variable.
00102   bool foundIndvar = false;
00103   bool indvarLast = false;
00104   std::vector<Value *> pre_op_vector;
00105   std::vector<Value *> inc_op_vector;
00106   Value *CanonicalIndVar = L->getCanonicalInductionVariable();
00107   for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) {
00108     Value *operand = GEPI->getOperand(op);
00109     if (operand == CanonicalIndVar) {
00110       // FIXME: We currently only support strength reducing GEP instructions
00111       // with one instance of the canonical induction variable.  This means that 
00112       // we can't deal with statements of the form A[i][i].
00113       if (foundIndvar == true)
00114         return;
00115         
00116       // FIXME: use getCanonicalInductionVariableIncrement to choose between
00117       // one and neg one maybe?  We need to support int *foo = GEP base, -1
00118       const Type *Ty = CanonicalIndVar->getType();
00119       pre_op_vector.push_back(Constant::getNullValue(Ty));
00120       inc_op_vector.push_back(ConstantInt::get(Ty, 1));
00121       foundIndvar = true;
00122       indvarLast = true;
00123     } else if (isa<Constant>(operand)) {
00124       pre_op_vector.push_back(operand);
00125       if (indvarLast == true) indvarLast = false;
00126     } else
00127       return;
00128   }
00129   // FIXME: handle GEPs where the indvar is not the last element of the index
00130   // array.
00131   if (indvarLast == false)
00132     return;
00133   assert(true == foundIndvar && "Indvar used by GEP not found in operand list");
00134   
00135   // FIXME: Being able to hoist the definition of the initial pointer value
00136   // would allow us to strength reduce more loops.  For example, %tmp.32 in the
00137   // following loop:
00138   // entry:
00139   //   br label %no_exit.0
00140   // no_exit.0:   ; preds = %entry, %no_exit.0
00141   //   %init.1.0 = phi uint [ 0, %entry ], [ %indvar.next, %no_exit.0 ]
00142   //   %tmp.32 = load uint** %CROSSING
00143   //   %tmp.35 = getelementptr uint* %tmp.32, uint %init.1.0
00144   //   br label %no_exit.0
00145   BasicBlock *Header = L->getHeader();
00146   if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0)))
00147     if (!DS->dominates(GepPtrOp, Header->begin()))
00148       return;
00149   
00150   // If all operands of the GEP we are going to insert into the preheader
00151   // are constants, generate a GEP ConstantExpr instead. 
00152   //
00153   // If there is only one operand after the initial non-constant one, we know
00154   // that it was the induction variable, and has been replaced by a constant
00155   // null value.  In this case, replace the GEP with a use of pointer directly.
00156   //
00157   // 
00158   BasicBlock *Preheader = L->getLoopPreheader();
00159   Value *PreGEP;
00160   if (isa<Constant>(GEPI->getOperand(0))) {
00161     Constant *C = dyn_cast<Constant>(GEPI->getOperand(0));
00162     PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector);
00163   } else if (pre_op_vector.size() == 1) {
00164     PreGEP = GEPI->getOperand(0);
00165   } else {
00166     PreGEP = new GetElementPtrInst(GEPI->getOperand(0),
00167                                    pre_op_vector, GEPI->getName(), 
00168                                    Preheader->getTerminator());
00169   }
00170 
00171   // The next step of the strength reduction is to create a PHI that will choose
00172   // between the initial GEP we created and inserted into the preheader, and 
00173   // the incremented GEP that we will create below and insert into the loop body
00174   PHINode *NewPHI = new PHINode(PreGEP->getType(), 
00175                                 GEPI->getName()+".str", InsertBefore);
00176   NewPHI->addIncoming(PreGEP, Preheader);
00177   
00178   // Now, create the GEP instruction to increment the value selected by the PHI
00179   // instruction we just created above by one, and add it as the second incoming
00180   // Value and BasicBlock pair to the PHINode.
00181   Instruction *IncrInst = 
00182     const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement());
00183   GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector,
00184                                                     GEPI->getName()+".inc",
00185                                                     IncrInst);
00186   NewPHI->addIncoming(StrGEP, IncrInst->getParent());
00187   
00188   // Replace all uses of the old GEP instructions with the new PHI
00189   GEPI->replaceAllUsesWith(NewPHI);
00190   
00191   // The old GEP is now dead.
00192   DeadInsts.insert(GEPI);
00193   ++NumReduced;
00194 }
00195 
00196 void LoopStrengthReduce::runOnLoop(Loop *L) {
00197   // First step, transform all loops nesting inside of this loop.
00198   for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
00199     runOnLoop(*I);
00200 
00201   // Next, get the first PHINode since it is guaranteed to be the canonical
00202   // induction variable for the loop by the preceding IndVarSimplify pass.
00203   PHINode *PN = L->getCanonicalInductionVariable();
00204   if (0 == PN)
00205     return;
00206 
00207   // Insert secondary PHI nodes after the canonical induction variable's PHI
00208   // for the strength reduced pointers that we will be creating.
00209   Instruction *InsertBefore = PN->getNext();
00210 
00211   // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars
00212   // pass creates code like this, which we can't currently detect:
00213   //  %tmp.1 = sub uint 2000, %indvar
00214   //  %tmp.8 = getelementptr int* %y, uint %tmp.1
00215   
00216   // Strength reduce all GEPs in the Loop
00217   std::set<Instruction*> DeadInsts;
00218   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
00219        UI != UE; ++UI)
00220     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
00221       strengthReduceGEP(GEPI, L, InsertBefore, DeadInsts);
00222 
00223   // Clean up after ourselves
00224   if (!DeadInsts.empty()) {
00225     DeleteTriviallyDeadInstructions(DeadInsts);
00226 
00227     // At this point, we know that we have killed one or more GEP instructions.
00228     // It is worth checking to see if the cann indvar is also dead, so that we
00229     // can remove it as well.  The requirements for the cann indvar to be
00230     // considered dead are:
00231     // 1. the cann indvar has one use
00232     // 2. the use is an add instruction
00233     // 3. the add has one use
00234     // 4. the add is used by the cann indvar
00235     // If all four cases above are true, then we can remove both the add and
00236     // the cann indvar.
00237     if (PN->hasOneUse()) {
00238       BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
00239       if (BO && BO->getOpcode() == Instruction::Add)
00240         if (BO->hasOneUse()) {
00241           PHINode *PotentialIndvar = dyn_cast<PHINode>(*(BO->use_begin()));
00242           if (PotentialIndvar && PN == PotentialIndvar) {
00243             PN->dropAllReferences();
00244             DeadInsts.insert(BO);
00245             DeadInsts.insert(PN);
00246             DeleteTriviallyDeadInstructions(DeadInsts);
00247           }
00248         }
00249     }
00250   }
00251 }