lib/Transforms/Scalar/LoopStrengthReduce.cpp

   1 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nate Begeman and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs a strength reduction on array references inside loops that
  11 // have as one or more of their components the loop induction variable.  This is
  12 // accomplished by creating a new Value to hold the initial value of the array
  13 // access for the first iteration, and then creating a new GEP instruction in
  14 // the loop to increment the value by the appropriate amount.
  15 //
  16 // There are currently several deficiencies in the implementation, marked with
  17 // FIXME in the code.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #include "llvm/Transforms/Scalar.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Instructions.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/Analysis/Dominators.h"
  26 #include "llvm/Analysis/LoopInfo.h"
  27 #include "llvm/Support/CFG.h"
  28 #include "llvm/Transforms/Utils/Local.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include <set>
  31 using namespace llvm;
  32
  33 namespace {
  34   Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced");
  35
  36   class LoopStrengthReduce : public FunctionPass {
  37     LoopInfo *LI;
  38     DominatorSet *DS;
  39     bool Changed;
  40   public:
  41     virtual bool runOnFunction(Function &) {
  42       LI = &getAnalysis<LoopInfo>();
  43       DS = &getAnalysis<DominatorSet>();
  44       Changed = false;
  45
  46       for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
  47         runOnLoop(*I);
  48       return Changed;
  49     }
  50
  51     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  52       AU.setPreservesCFG();
  53       AU.addRequired<LoopInfo>();
  54       AU.addRequired<DominatorSet>();
  55     }
  56   private:
  57     void runOnLoop(Loop *L);
  58     void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
  59                            Instruction *InsertBefore,
  60                            std::set<Instruction*> &DeadInsts);
  61     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
  62   };
  63   RegisterOpt<LoopStrengthReduce> X("loop-reduce",
  64                                     "Strength Reduce GEP Uses of Ind. Vars");
  65 }
  66
  67 FunctionPass *llvm::createLoopStrengthReducePass() {
  68   return new LoopStrengthReduce();
  69 }
  70
  71 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
  72 /// specified set are trivially dead, delete them and see if this makes any of
  73 /// their operands subsequently dead.
  74 void LoopStrengthReduce::
  75 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
  76   while (!Insts.empty()) {
  77     Instruction *I = *Insts.begin();
  78     Insts.erase(Insts.begin());
  79     if (isInstructionTriviallyDead(I)) {
  80       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
  81         if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
  82           Insts.insert(U);
  83       I->getParent()->getInstList().erase(I);
  84       Changed = true;
  85     }
  86   }
  87 }
  88
  89 void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
  90                                            Instruction *InsertBefore,
  91                                            std::set<Instruction*> &DeadInsts) {
  92   // We will strength reduce the GEP by splitting it into two parts.  The first
  93   // is a GEP to hold the initial value of the non-strength-reduced GEP upon
  94   // entering the loop, which we will insert at the end of the loop preheader.
  95   // The second is a GEP to hold the incremented value of the initial GEP.
  96   // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so
  97   // we will replace the indvar with a constant zero value to create the first
  98   // GEP.
  99   //
 100   // We currently only handle GEP instructions that consist of zero or more
 101   // constants and one instance of the canonical induction variable.
 102   bool foundIndvar = false;
 103   bool indvarLast = false;
 104   std::vector<Value *> pre_op_vector;
 105   std::vector<Value *> inc_op_vector;
 106   Value *CanonicalIndVar = L->getCanonicalInductionVariable();
 107   for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) {
 108     Value *operand = GEPI->getOperand(op);
 109     if (operand == CanonicalIndVar) {
 110       // FIXME: We currently only support strength reducing GEP instructions
 111       // with one instance of the canonical induction variable.  This means that
 112       // we can't deal with statements of the form A[i][i].
 113       if (foundIndvar == true)
 114         return;
 115
 116       // FIXME: use getCanonicalInductionVariableIncrement to choose between
 117       // one and neg one maybe?  We need to support int *foo = GEP base, -1
 118       const Type *Ty = CanonicalIndVar->getType();
 119       pre_op_vector.push_back(Constant::getNullValue(Ty));
 120       inc_op_vector.push_back(ConstantInt::get(Ty, 1));
 121       foundIndvar = true;
 122       indvarLast = true;
 123     } else if (isa<Constant>(operand)) {
 124       pre_op_vector.push_back(operand);
 125       if (indvarLast == true) indvarLast = false;
 126     } else
 127       return;
 128   }
 129   // FIXME: handle GEPs where the indvar is not the last element of the index
 130   // array.
 131   if (indvarLast == false)
 132     return;
 133   assert(true == foundIndvar && "Indvar used by GEP not found in operand list");
 134
 135   // FIXME: Being able to hoist the definition of the initial pointer value
 136   // would allow us to strength reduce more loops.  For example, %tmp.32 in the
 137   // following loop:
 138   // entry:
 139   //   br label %no_exit.0
 140   // no_exit.0:         ; preds = %entry, %no_exit.0
 141   //   %init.1.0 = phi uint [ 0, %entry ], [ %indvar.next, %no_exit.0 ]
 142   //   %tmp.32 = load uint** %CROSSING
 143   //   %tmp.35 = getelementptr uint* %tmp.32, uint %init.1.0
 144   //   br label %no_exit.0
 145   BasicBlock *Header = L->getHeader();
 146   if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0)))
 147     if (!DS->dominates(GepPtrOp, Header->begin()))
 148       return;
 149
 150   // If all operands of the GEP we are going to insert into the preheader
 151   // are constants, generate a GEP ConstantExpr instead.
 152   //
 153   // If there is only one operand after the initial non-constant one, we know
 154   // that it was the induction variable, and has been replaced by a constant
 155   // null value.  In this case, replace the GEP with a use of pointer directly.
 156   //
 157   //
 158   BasicBlock *Preheader = L->getLoopPreheader();
 159   Value *PreGEP;
 160   if (isa<Constant>(GEPI->getOperand(0))) {
 161     Constant *C = dyn_cast<Constant>(GEPI->getOperand(0));
 162     PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector);
 163   } else if (pre_op_vector.size() == 1) {
 164     PreGEP = GEPI->getOperand(0);
 165   } else {
 166     PreGEP = new GetElementPtrInst(GEPI->getOperand(0),
 167                                    pre_op_vector, GEPI->getName(),
 168                                    Preheader->getTerminator());
 169   }
 170
 171   // The next step of the strength reduction is to create a PHI that will choose
 172   // between the initial GEP we created and inserted into the preheader, and
 173   // the incremented GEP that we will create below and insert into the loop body
 174   PHINode *NewPHI = new PHINode(PreGEP->getType(),
 175                                 GEPI->getName()+".str", InsertBefore);
 176   NewPHI->addIncoming(PreGEP, Preheader);
 177
 178   // Now, create the GEP instruction to increment the value selected by the PHI
 179   // instruction we just created above by one, and add it as the second incoming
 180   // Value and BasicBlock pair to the PHINode.
 181   Instruction *IncrInst =
 182     const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement());
 183   GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector,
 184                                                     GEPI->getName()+".inc",
 185                                                     IncrInst);
 186   NewPHI->addIncoming(StrGEP, IncrInst->getParent());
 187
 188   // Replace all uses of the old GEP instructions with the new PHI
 189   GEPI->replaceAllUsesWith(NewPHI);
 190
 191   // The old GEP is now dead.
 192   DeadInsts.insert(GEPI);
 193   ++NumReduced;
 194 }
 195
 196 void LoopStrengthReduce::runOnLoop(Loop *L) {
 197   // First step, transform all loops nesting inside of this loop.
 198   for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
 199     runOnLoop(*I);
 200
 201   // Next, get the first PHINode since it is guaranteed to be the canonical
 202   // induction variable for the loop by the preceding IndVarSimplify pass.
 203   PHINode *PN = L->getCanonicalInductionVariable();
 204   if (0 == PN)
 205     return;
 206
 207   // Insert secondary PHI nodes after the canonical induction variable's PHI
 208   // for the strength reduced pointers that we will be creating.
 209   Instruction *InsertBefore = PN->getNext();
 210
 211   // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars
 212   // pass creates code like this, which we can't currently detect:
 213   //  %tmp.1 = sub uint 2000, %indvar
 214   //  %tmp.8 = getelementptr int* %y, uint %tmp.1
 215
 216   // Strength reduce all GEPs in the Loop
 217   std::set<Instruction*> DeadInsts;
 218   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
 219        UI != UE; ++UI)
 220     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
 221       strengthReduceGEP(GEPI, L, InsertBefore, DeadInsts);
 222
 223   // Clean up after ourselves
 224   if (!DeadInsts.empty()) {
 225     DeleteTriviallyDeadInstructions(DeadInsts);
 226
 227     // At this point, we know that we have killed one or more GEP instructions.
 228     // It is worth checking to see if the cann indvar is also dead, so that we
 229     // can remove it as well.  The requirements for the cann indvar to be
 230     // considered dead are:
 231     // 1. the cann indvar has one use
 232     // 2. the use is an add instruction
 233     // 3. the add has one use
 234     // 4. the add is used by the cann indvar
 235     // If all four cases above are true, then we can remove both the add and
 236     // the cann indvar.
 237     if (PN->hasOneUse()) {
 238       BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
 239       if (BO && BO->getOpcode() == Instruction::Add)
 240         if (BO->hasOneUse()) {
 241           PHINode *PotentialIndvar = dyn_cast<PHINode>(*(BO->use_begin()));
 242           if (PotentialIndvar && PN == PotentialIndvar) {
 243             PN->dropAllReferences();
 244             DeadInsts.insert(BO);
 245             DeadInsts.insert(PN);
 246             DeleteTriviallyDeadInstructions(DeadInsts);
 247           }
 248         }
 249     }
 250   }
 251 }