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<Argument>(operand)) {
 158       pre_op_vector.push_back(operand);
 159       AllConstantOperands = false;
 160     } else if (isa<Constant>(operand)) {
 161       pre_op_vector.push_back(operand);
 162     } else if (Instruction *inst = dyn_cast<Instruction>(operand)) {
 163       if (!DS->dominates(inst, Preheader->getTerminator()))
 164         return;
 165       pre_op_vector.push_back(operand);
 166       AllConstantOperands = false;
 167     } else {
 168       return;  // Cannot handle this.
 169     }
 170     Cache = Cache->get(operand);
 171   }
 172   assert(indvar > 0 && "Indvar used by GEP not found in operand list");
 173
 174   // Ensure the pointer base is loop invariant.  While strength reduction
 175   // makes sense even if the pointer changed on every iteration, there is no
 176   // realistic way of handling it unless GEPs were completely decomposed into
 177   // their constituent operations so we have explicit multiplications to work
 178   // with.
 179   if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0)))
 180     if (!DS->dominates(GepPtrOp, Preheader->getTerminator()))
 181       return;
 182
 183   // Don't reduce multiplies that the target can handle via addressing modes.
 184   uint64_t sz = getAnalysis<TargetData>().getTypeSize(ty);
 185   if (sz && (sz & (sz-1)) == 0)   // Power of two?
 186     if (sz <= (1ULL << (MaxTargetAMSize-1)))
 187       return;
 188
 189   // If all operands of the GEP we are going to insert into the preheader
 190   // are constants, generate a GEP ConstantExpr instead.
 191   //
 192   // If there is only one operand after the initial non-constant one, we know
 193   // that it was the induction variable, and has been replaced by a constant
 194   // null value.  In this case, replace the GEP with a use of pointer directly.
 195   PHINode *NewPHI;
 196   if (Cache->CachedPHINode == 0) {
 197     Value *PreGEP;
 198     if (AllConstantOperands && isa<Constant>(GEPI->getOperand(0))) {
 199       Constant *C = dyn_cast<Constant>(GEPI->getOperand(0));
 200       PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector);
 201     } else if (pre_op_vector.size() == 1) {
 202       PreGEP = GEPI->getOperand(0);
 203     } else {
 204       PreGEP = new GetElementPtrInst(GEPI->getOperand(0),
 205                                     pre_op_vector, GEPI->getName()+".pre",
 206                                     Preheader->getTerminator());
 207     }
 208
 209     // The next step of the strength reduction is to create a PHI that will
 210     // choose between the initial GEP we created and inserted into the
 211     // preheader, and the incremented GEP that we will create below and insert
 212     // into the loop body.
 213     NewPHI = new PHINode(PreGEP->getType(),
 214                                   GEPI->getName()+".str", InsertBefore);
 215     NewPHI->addIncoming(PreGEP, Preheader);
 216
 217     // Now, create the GEP instruction to increment by one the value selected
 218     // by the PHI instruction we just created above, and add it as the second
 219     // incoming Value/BasicBlock pair to the PHINode.  It is inserted before
 220     // the increment of the canonical induction variable.
 221     Instruction *IncrInst =
 222       const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement());
 223     GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector,
 224                                                       GEPI->getName()+".inc",
 225                                                       IncrInst);
 226     pred_iterator PI = pred_begin(Header);
 227     if (*PI == Preheader)
 228       ++PI;
 229     NewPHI->addIncoming(StrGEP, *PI);
 230     Cache->CachedPHINode = NewPHI;
 231   } else {
 232     // Reuse previously created pointer, as it is identical to the one we were
 233     // about to create.
 234     NewPHI = Cache->CachedPHINode;
 235   }
 236
 237   if (GEPI->getNumOperands() - 1 == indvar) {
 238     // If there were no operands following the induction variable, replace all
 239     // uses of the old GEP instruction with the new PHI.
 240     GEPI->replaceAllUsesWith(NewPHI);
 241   } else {
 242     // Create a new GEP instruction using the new PHI as the base.  The
 243     // operands of the original GEP past the induction variable become
 244     // operands of this new GEP.
 245     std::vector<Value *> op_vector;
 246     const Type *Ty = CanonicalIndVar->getType();
 247     op_vector.push_back(Constant::getNullValue(Ty));
 248     for (unsigned op = indvar + 1; op < GEPI->getNumOperands(); op++)
 249       op_vector.push_back(GEPI->getOperand(op));
 250     GetElementPtrInst *newGEP = new GetElementPtrInst(NewPHI, op_vector,
 251                                                       GEPI->getName() + ".lsr",
 252                                                       GEPI);
 253     GEPI->replaceAllUsesWith(newGEP);
 254   }
 255
 256   // The old GEP is now dead.
 257   DeadInsts.insert(GEPI);
 258   ++NumReduced;
 259 }
 260
 261 void LoopStrengthReduce::runOnLoop(Loop *L) {
 262   // First step, transform all loops nesting inside of this loop.
 263   for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
 264     runOnLoop(*I);
 265
 266   // Next, get the first PHINode since it is guaranteed to be the canonical
 267   // induction variable for the loop by the preceding IndVarSimplify pass.
 268   PHINode *PN = L->getCanonicalInductionVariable();
 269   if (0 == PN)
 270     return;
 271
 272   // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars
 273   // pass creates code like this, which we can't currently detect:
 274   //  %tmp.1 = sub uint 2000, %indvar
 275   //  %tmp.8 = getelementptr int* %y, uint %tmp.1
 276
 277   // Strength reduce all GEPs in the Loop.  Insert secondary PHI nodes for the
 278   // strength reduced pointers we'll be creating after the canonical induction
 279   // variable's PHI.
 280   std::set<Instruction*> DeadInsts;
 281   GEPCache Cache;
 282   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
 283        UI != UE; ++UI)
 284     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
 285       strengthReduceGEP(GEPI, L, &Cache, PN->getNext(), DeadInsts);
 286
 287   // Clean up after ourselves
 288   if (!DeadInsts.empty()) {
 289     DeleteTriviallyDeadInstructions(DeadInsts);
 290
 291     // At this point, we know that we have killed one or more GEP instructions.
 292     // It is worth checking to see if the cann indvar is also dead, so that we
 293     // can remove it as well.  The requirements for the cann indvar to be
 294     // considered dead are:
 295     // 1. the cann indvar has one use
 296     // 2. the use is an add instruction
 297     // 3. the add has one use
 298     // 4. the add is used by the cann indvar
 299     // If all four cases above are true, then we can remove both the add and
 300     // the cann indvar.
 301     // FIXME: this needs to eliminate an induction variable even if it's being
 302     // compared against some value to decide loop termination.
 303     if (PN->hasOneUse()) {
 304       BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
 305       if (BO && BO->getOpcode() == Instruction::Add)
 306         if (BO->hasOneUse()) {
 307           if (PN == dyn_cast<PHINode>(*(BO->use_begin()))) {
 308             DeadInsts.insert(BO);
 309             // Break the cycle, then delete the PHI.
 310             PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 311             PN->eraseFromParent();
 312             DeleteTriviallyDeadInstructions(DeadInsts);
 313           }
 314         }
 315     }
 316   }
 317 }