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/DerivedTypes.h"
  26 #include "llvm/Analysis/Dominators.h"
  27 #include "llvm/Analysis/LoopInfo.h"
  28 #include "llvm/Support/CFG.h"
  29 #include "llvm/Transforms/Utils/Local.h"
  30 #include "llvm/Target/TargetData.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include <set>
  33 using namespace llvm;
  34
  35 namespace {
  36   Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced");
  37
  38   class GEPCache {
  39   public:
  40     GEPCache() : CachedPHINode(0), Map() {}
  41
  42     GEPCache *get(Value *v) {
  43       std::map<Value *, GEPCache>::iterator I = Map.find(v);
  44       if (I == Map.end())
  45         I = Map.insert(std::pair<Value *, GEPCache>(v, GEPCache())).first;
  46       return &I->second;
  47     }
  48
  49     PHINode *CachedPHINode;
  50     std::map<Value *, GEPCache> Map;
  51   };
  52
  53   class LoopStrengthReduce : public FunctionPass {
  54     LoopInfo *LI;
  55     DominatorSet *DS;
  56     bool Changed;
  57     unsigned MaxTargetAMSize;
  58   public:
  59     LoopStrengthReduce(unsigned MTAMS = 1)
  60       : MaxTargetAMSize(MTAMS) {
  61     }
  62
  63     virtual bool runOnFunction(Function &) {
  64       LI = &getAnalysis<LoopInfo>();
  65       DS = &getAnalysis<DominatorSet>();
  66       Changed = false;
  67
  68       for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
  69         runOnLoop(*I);
  70       return Changed;
  71     }
  72
  73     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  74       AU.setPreservesCFG();
  75       AU.addRequiredID(LoopSimplifyID);
  76       AU.addRequired<LoopInfo>();
  77       AU.addRequired<DominatorSet>();
  78       AU.addRequired<TargetData>();
  79     }
  80   private:
  81     void runOnLoop(Loop *L);
  82     void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
  83                            GEPCache* GEPCache,
  84                            Instruction *InsertBefore,
  85                            std::set<Instruction*> &DeadInsts);
  86     void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
  87   };
  88   RegisterOpt<LoopStrengthReduce> X("loop-reduce",
  89                                     "Strength Reduce GEP Uses of Ind. Vars");
  90 }
  91
  92 FunctionPass *llvm::createLoopStrengthReducePass(unsigned MaxTargetAMSize) {
  93   return new LoopStrengthReduce(MaxTargetAMSize);
  94 }
  95
  96 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
  97 /// specified set are trivially dead, delete them and see if this makes any of
  98 /// their operands subsequently dead.
  99 void LoopStrengthReduce::
 100 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
 101   while (!Insts.empty()) {
 102     Instruction *I = *Insts.begin();
 103     Insts.erase(Insts.begin());
 104     if (isInstructionTriviallyDead(I)) {
 105       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
 106         if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
 107           Insts.insert(U);
 108       I->getParent()->getInstList().erase(I);
 109       Changed = true;
 110     }
 111   }
 112 }
 113
 114 void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
 115                                            GEPCache *Cache,
 116                                            Instruction *InsertBefore,
 117                                            std::set<Instruction*> &DeadInsts) {
 118   // We will strength reduce the GEP by splitting it into two parts.  The first
 119   // is a GEP to hold the initial value of the non-strength-reduced GEP upon
 120   // entering the loop, which we will insert at the end of the loop preheader.
 121   // The second is a GEP to hold the incremented value of the initial GEP.
 122   // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so
 123   // we will replace the indvar with a constant zero value to create the first
 124   // GEP.
 125   //
 126   // We currently only handle GEP instructions that consist of zero or more
 127   // constants or loop invariable expressions prior to an instance of the
 128   // canonical induction variable.
 129   unsigned indvar = 0;
 130   std::vector<Value *> pre_op_vector;
 131   std::vector<Value *> inc_op_vector;
 132   const Type *ty = GEPI->getOperand(0)->getType();
 133   Value *CanonicalIndVar = L->getCanonicalInductionVariable();
 134   BasicBlock *Header = L->getHeader();
 135   BasicBlock *Preheader = L->getLoopPreheader();
 136   bool AllConstantOperands = true;
 137   Cache = Cache->get(GEPI->getOperand(0));
 138
 139   for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) {
 140     Value *operand = GEPI->getOperand(op);
 141     if (ty->getTypeID() == Type::StructTyID) {
 142       assert(isa<ConstantUInt>(operand));
 143       ConstantUInt *c = dyn_cast<ConstantUInt>(operand);
 144       ty = ty->getContainedType(unsigned(c->getValue()));
 145     } else {
 146       ty = ty->getContainedType(0);
 147     }
 148
 149     if (operand == CanonicalIndVar) {
 150       // FIXME: use getCanonicalInductionVariableIncrement to choose between
 151       // one and neg one maybe?  We need to support int *foo = GEP base, -1
 152       const Type *Ty = CanonicalIndVar->getType();
 153       pre_op_vector.push_back(Constant::getNullValue(Ty));
 154       inc_op_vector.push_back(ConstantInt::get(Ty, 1));
 155       indvar = op;
 156       break;
 157     } else if (isa<Constant>(operand) || isa<Argument>(operand)) {
 158       pre_op_vector.push_back(operand);
 159     } else if (Instruction *inst = dyn_cast<Instruction>(operand)) {
 160       if (!DS->dominates(inst, Preheader->getTerminator()))
 161         return;
 162       pre_op_vector.push_back(operand);
 163       AllConstantOperands = false;
 164     } else
 165       return;
 166     Cache = Cache->get(operand);
 167   }
 168   assert(indvar > 0 && "Indvar used by GEP not found in operand list");
 169
 170   // Ensure the pointer base is loop invariant.  While strength reduction
 171   // makes sense even if the pointer changed on every iteration, there is no
 172   // realistic way of handling it unless GEPs were completely decomposed into
 173   // their constituent operations so we have explicit multiplications to work
 174   // with.
 175   if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0)))
 176     if (!DS->dominates(GepPtrOp, Preheader->getTerminator()))
 177       return;
 178
 179   // Don't reduce multiplies that the target can handle via addressing modes.
 180   uint64_t sz = getAnalysis<TargetData>().getTypeSize(ty);
 181   if (sz && (sz & (sz-1)) == 0)   // Power of two?
 182     if (sz <= (1ULL << (MaxTargetAMSize-1)))
 183       return;
 184
 185   // If all operands of the GEP we are going to insert into the preheader
 186   // are constants, generate a GEP ConstantExpr instead.
 187   //
 188   // If there is only one operand after the initial non-constant one, we know
 189   // that it was the induction variable, and has been replaced by a constant
 190   // null value.  In this case, replace the GEP with a use of pointer directly.
 191   PHINode *NewPHI;
 192   if (Cache->CachedPHINode == 0) {
 193     Value *PreGEP;
 194     if (AllConstantOperands && isa<Constant>(GEPI->getOperand(0))) {
 195       Constant *C = dyn_cast<Constant>(GEPI->getOperand(0));
 196       PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector);
 197     } else if (pre_op_vector.size() == 1) {
 198       PreGEP = GEPI->getOperand(0);
 199     } else {
 200       PreGEP = new GetElementPtrInst(GEPI->getOperand(0),
 201                                     pre_op_vector, GEPI->getName()+".pre",
 202                                     Preheader->getTerminator());
 203     }
 204
 205     // The next step of the strength reduction is to create a PHI that will
 206     // choose between the initial GEP we created and inserted into the
 207     // preheader, and the incremented GEP that we will create below and insert
 208     // into the loop body.
 209     NewPHI = new PHINode(PreGEP->getType(),
 210                                   GEPI->getName()+".str", InsertBefore);
 211     NewPHI->addIncoming(PreGEP, Preheader);
 212
 213     // Now, create the GEP instruction to increment by one the value selected
 214     // by the PHI instruction we just created above, and add it as the second
 215     // incoming Value/BasicBlock pair to the PHINode.  It is inserted before
 216     // the increment of the canonical induction variable.
 217     Instruction *IncrInst =
 218       const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement());
 219     GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector,
 220                                                       GEPI->getName()+".inc",
 221                                                       IncrInst);
 222     pred_iterator PI = pred_begin(Header);
 223     if (*PI == Preheader)
 224       ++PI;
 225     NewPHI->addIncoming(StrGEP, *PI);
 226     Cache->CachedPHINode = NewPHI;
 227   } else {
 228     // Reuse previously created pointer, as it is identical to the one we were
 229     // about to create.
 230     NewPHI = Cache->CachedPHINode;
 231   }
 232
 233   if (GEPI->getNumOperands() - 1 == indvar) {
 234     // If there were no operands following the induction variable, replace all
 235     // uses of the old GEP instruction with the new PHI.
 236     GEPI->replaceAllUsesWith(NewPHI);
 237   } else {
 238     // Create a new GEP instruction using the new PHI as the base.  The
 239     // operands of the original GEP past the induction variable become
 240     // operands of this new GEP.
 241     std::vector<Value *> op_vector;
 242     const Type *Ty = CanonicalIndVar->getType();
 243     op_vector.push_back(Constant::getNullValue(Ty));
 244     for (unsigned op = indvar + 1; op < GEPI->getNumOperands(); op++)
 245       op_vector.push_back(GEPI->getOperand(op));
 246     GetElementPtrInst *newGEP = new GetElementPtrInst(NewPHI, op_vector,
 247                                                       GEPI->getName() + ".lsr",
 248                                                       GEPI);
 249     GEPI->replaceAllUsesWith(newGEP);
 250   }
 251
 252   // The old GEP is now dead.
 253   DeadInsts.insert(GEPI);
 254   ++NumReduced;
 255 }
 256
 257 void LoopStrengthReduce::runOnLoop(Loop *L) {
 258   // First step, transform all loops nesting inside of this loop.
 259   for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
 260     runOnLoop(*I);
 261
 262   // Next, get the first PHINode since it is guaranteed to be the canonical
 263   // induction variable for the loop by the preceding IndVarSimplify pass.
 264   PHINode *PN = L->getCanonicalInductionVariable();
 265   if (0 == PN)
 266     return;
 267
 268   // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars
 269   // pass creates code like this, which we can't currently detect:
 270   //  %tmp.1 = sub uint 2000, %indvar
 271   //  %tmp.8 = getelementptr int* %y, uint %tmp.1
 272
 273   // Strength reduce all GEPs in the Loop.  Insert secondary PHI nodes for the
 274   // strength reduced pointers we'll be creating after the canonical induction
 275   // variable's PHI.
 276   std::set<Instruction*> DeadInsts;
 277   GEPCache Cache;
 278   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
 279        UI != UE; ++UI)
 280     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
 281       strengthReduceGEP(GEPI, L, &Cache, PN->getNext(), DeadInsts);
 282
 283   // Clean up after ourselves
 284   if (!DeadInsts.empty()) {
 285     DeleteTriviallyDeadInstructions(DeadInsts);
 286
 287     // At this point, we know that we have killed one or more GEP instructions.
 288     // It is worth checking to see if the cann indvar is also dead, so that we
 289     // can remove it as well.  The requirements for the cann indvar to be
 290     // considered dead are:
 291     // 1. the cann indvar has one use
 292     // 2. the use is an add instruction
 293     // 3. the add has one use
 294     // 4. the add is used by the cann indvar
 295     // If all four cases above are true, then we can remove both the add and
 296     // the cann indvar.
 297     // FIXME: this needs to eliminate an induction variable even if it's being
 298     // compared against some value to decide loop termination.
 299     if (PN->hasOneUse()) {
 300       BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
 301       if (BO && BO->getOpcode() == Instruction::Add)
 302         if (BO->hasOneUse()) {
 303           if (PN == dyn_cast<PHINode>(*(BO->use_begin()))) {
 304             DeadInsts.insert(BO);
 305             // Break the cycle, then delete the PHI.
 306             PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 307             PN->eraseFromParent();
 308             DeleteTriviallyDeadInstructions(DeadInsts);
 309           }
 310         }
 311     }
 312   }
 313 }