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.addRequiredID(LoopSimplifyID);
  54       AU.addRequired<LoopInfo>();
  55       AU.addRequired<DominatorSet>();
  56     }
  57   private:
  58     void runOnLoop(Loop *L);
  59     void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
  60                            Instruction *InsertBefore,
  61                            std::set<Instruction*> &DeadInsts);
  62     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
  63   };
  64   RegisterOpt<LoopStrengthReduce> X("loop-reduce",
  65                                     "Strength Reduce GEP Uses of Ind. Vars");
  66 }
  67
  68 FunctionPass *llvm::createLoopStrengthReducePass() {
  69   return new LoopStrengthReduce();
  70 }
  71
  72 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
  73 /// specified set are trivially dead, delete them and see if this makes any of
  74 /// their operands subsequently dead.
  75 void LoopStrengthReduce::
  76 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
  77   while (!Insts.empty()) {
  78     Instruction *I = *Insts.begin();
  79     Insts.erase(Insts.begin());
  80     if (isInstructionTriviallyDead(I)) {
  81       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
  82         // Note: the PHI nodes had dropAllReferences() called on it, so its
  83         // operands will all be NULL.
  84         Value *V = I->getOperand(i);
  85         if (V)
  86           if (Instruction *U = dyn_cast<Instruction>(V))
  87             Insts.insert(U);
  88       }
  89       I->getParent()->getInstList().erase(I);
  90       Changed = true;
  91     }
  92   }
  93 }
  94
  95 void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
  96                                            Instruction *InsertBefore,
  97                                            std::set<Instruction*> &DeadInsts) {
  98   // We will strength reduce the GEP by splitting it into two parts.  The first
  99   // is a GEP to hold the initial value of the non-strength-reduced GEP upon
 100   // entering the loop, which we will insert at the end of the loop preheader.
 101   // The second is a GEP to hold the incremented value of the initial GEP.
 102   // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so
 103   // we will replace the indvar with a constant zero value to create the first
 104   // GEP.
 105   //
 106   // We currently only handle GEP instructions that consist of zero or more
 107   // constants or loop invariable expressions prior to an instance of the
 108   // canonical induction variable.
 109   unsigned indvar = 0;
 110   std::vector<Value *> pre_op_vector;
 111   std::vector<Value *> inc_op_vector;
 112   Value *CanonicalIndVar = L->getCanonicalInductionVariable();
 113   BasicBlock *Header = L->getHeader();
 114
 115   for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) {
 116     Value *operand = GEPI->getOperand(op);
 117     if (operand == CanonicalIndVar) {
 118       // FIXME: use getCanonicalInductionVariableIncrement to choose between
 119       // one and neg one maybe?  We need to support int *foo = GEP base, -1
 120       const Type *Ty = CanonicalIndVar->getType();
 121       pre_op_vector.push_back(Constant::getNullValue(Ty));
 122       inc_op_vector.push_back(ConstantInt::get(Ty, 1));
 123       indvar = op;
 124       break;
 125     } else if (isa<Constant>(operand)) {
 126       pre_op_vector.push_back(operand);
 127     } else if (Instruction *inst = dyn_cast<Instruction>(operand)) {
 128       if (!DS->dominates(inst, Header->begin()))
 129         return;
 130       pre_op_vector.push_back(operand);
 131     } else
 132       return;
 133   }
 134   assert(indvar > 0 && "Indvar used by GEP not found in operand list");
 135
 136   // Ensure the pointer base is loop invariant.  While strength reduction
 137   // makes sense even if the pointer changed on every iteration, there is no
 138   // realistic way of handling it unless GEPs were completely decomposed into
 139   // their constituent operations so we have explicit multiplications to work
 140   // with.
 141   if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0)))
 142     if (!DS->dominates(GepPtrOp, Header->begin()))
 143       return;
 144
 145   // If all operands of the GEP we are going to insert into the preheader
 146   // are constants, generate a GEP ConstantExpr instead.
 147   //
 148   // If there is only one operand after the initial non-constant one, we know
 149   // that it was the induction variable, and has been replaced by a constant
 150   // null value.  In this case, replace the GEP with a use of pointer directly.
 151   BasicBlock *Preheader = L->getLoopPreheader();
 152   Value *PreGEP;
 153   if (isa<Constant>(GEPI->getOperand(0))) {
 154     Constant *C = dyn_cast<Constant>(GEPI->getOperand(0));
 155     PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector);
 156   } else if (pre_op_vector.size() == 1) {
 157     PreGEP = GEPI->getOperand(0);
 158   } else {
 159     PreGEP = new GetElementPtrInst(GEPI->getOperand(0),
 160                                    pre_op_vector, GEPI->getName()+".pre",
 161                                    Preheader->getTerminator());
 162   }
 163
 164   // The next step of the strength reduction is to create a PHI that will choose
 165   // between the initial GEP we created and inserted into the preheader, and
 166   // the incremented GEP that we will create below and insert into the loop body
 167   PHINode *NewPHI = new PHINode(PreGEP->getType(),
 168                                 GEPI->getName()+".str", InsertBefore);
 169   NewPHI->addIncoming(PreGEP, Preheader);
 170
 171   // Now, create the GEP instruction to increment by one the value selected by
 172   // the PHI instruction we just created above, and add it as the second
 173   // incoming Value/BasicBlock pair to the PHINode.  It is inserted before the
 174   // increment of the canonical induction variable.
 175   Instruction *IncrInst =
 176     const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement());
 177   GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector,
 178                                                     GEPI->getName()+".inc",
 179                                                     IncrInst);
 180   NewPHI->addIncoming(StrGEP, IncrInst->getParent());
 181
 182   if (GEPI->getNumOperands() - 1 == indvar) {
 183     // If there were no operands following the induction variable, replace all
 184     // uses of the old GEP instruction with the new PHI.
 185     GEPI->replaceAllUsesWith(NewPHI);
 186   } else {
 187     // Create a new GEP instruction using the new PHI as the base.  The
 188     // operands of the original GEP past the induction variable become
 189     // operands of this new GEP.
 190     std::vector<Value *> op_vector;
 191     const Type *Ty = CanonicalIndVar->getType();
 192     op_vector.push_back(Constant::getNullValue(Ty));
 193     for (unsigned op = indvar + 1; op < GEPI->getNumOperands(); op++)
 194       op_vector.push_back(GEPI->getOperand(op));
 195     GetElementPtrInst *newGEP = new GetElementPtrInst(NewPHI, op_vector,
 196                                                       GEPI->getName() + ".lsr",
 197                                                       GEPI);
 198     GEPI->replaceAllUsesWith(newGEP);
 199 }
 200
 201   // The old GEP is now dead.
 202   DeadInsts.insert(GEPI);
 203   ++NumReduced;
 204 }
 205
 206 void LoopStrengthReduce::runOnLoop(Loop *L) {
 207   // First step, transform all loops nesting inside of this loop.
 208   for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
 209     runOnLoop(*I);
 210
 211   // Next, get the first PHINode since it is guaranteed to be the canonical
 212   // induction variable for the loop by the preceding IndVarSimplify pass.
 213   PHINode *PN = L->getCanonicalInductionVariable();
 214   if (0 == PN)
 215     return;
 216
 217   // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars
 218   // pass creates code like this, which we can't currently detect:
 219   //  %tmp.1 = sub uint 2000, %indvar
 220   //  %tmp.8 = getelementptr int* %y, uint %tmp.1
 221
 222   // Strength reduce all GEPs in the Loop.  Insert secondary PHI nodes for the
 223   // strength reduced pointers we'll be creating after the canonical induction
 224   // variable's PHI.
 225   std::set<Instruction*> DeadInsts;
 226   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
 227        UI != UE; ++UI)
 228     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
 229       strengthReduceGEP(GEPI, L, PN->getNext(), DeadInsts);
 230
 231   // Clean up after ourselves
 232   if (!DeadInsts.empty()) {
 233     DeleteTriviallyDeadInstructions(DeadInsts);
 234
 235     // At this point, we know that we have killed one or more GEP instructions.
 236     // It is worth checking to see if the cann indvar is also dead, so that we
 237     // can remove it as well.  The requirements for the cann indvar to be
 238     // considered dead are:
 239     // 1. the cann indvar has one use
 240     // 2. the use is an add instruction
 241     // 3. the add has one use
 242     // 4. the add is used by the cann indvar
 243     // If all four cases above are true, then we can remove both the add and
 244     // the cann indvar.
 245 #if 0
 246     // FIXME: it's not clear this code is correct.  An induction variable with
 247     // but one use, an increment, implies an infinite loop.  Not illegal, but
 248     // of questionable utility.  It also does not update the loop info with the
 249     // new induction variable.
 250     if (PN->hasOneUse()) {
 251       BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
 252       if (BO && BO->getOpcode() == Instruction::Add)
 253         if (BO->hasOneUse()) {
 254           PHINode *PotentialIndvar = dyn_cast<PHINode>(*(BO->use_begin()));
 255           if (PotentialIndvar && PN == PotentialIndvar) {
 256             PN->dropAllReferences();
 257             DeadInsts.insert(BO);
 258             DeadInsts.insert(PN);
 259             DeleteTriviallyDeadInstructions(DeadInsts);
 260           }
 261         }
 262     }
 263 #endif
 264   }
 265 }