diff options
| -rw-r--r-- | include/llvm/Transforms/Scalar.h | 7 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/LoopStrengthReduce.cpp | 251 |
2 files changed, 257 insertions, 1 deletions
diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 34e87dc..5515c6a 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -141,6 +141,12 @@ FunctionPass *createInstructionCombiningPass(); // FunctionPass *createLICMPass(); +//===----------------------------------------------------------------------===// +// +// LoopStrengthReduce - This pass is strength reduces GEP instructions that use +// a loop's canonical induction variable as one of their indices. +// +FunctionPass *createLoopStrengthReducePass(); //===----------------------------------------------------------------------===// // @@ -155,7 +161,6 @@ FunctionPass *createLoopUnswitchPass(); // FunctionPass *createLoopUnrollPass(); - //===----------------------------------------------------------------------===// // // This pass is used to promote memory references to be register references. A diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp new file mode 100644 index 0000000..db57ce6 --- /dev/null +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -0,0 +1,251 @@ +//===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Nate Begeman and is distributed under the +// University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass performs a strength reduction on array references inside loops that +// have as one or more of their components the loop induction variable. This is +// accomplished by creating a new Value to hold the initial value of the array +// access for the first iteration, and then creating a new GEP instruction in +// the loop to increment the value by the appropriate amount. +// +// There are currently several deficiencies in the implementation, marked with +// FIXME in the code. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar.h" +#include "llvm/Constants.h" +#include "llvm/Instructions.h" +#include "llvm/Type.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Support/CFG.h" +#include "llvm/Transforms/Utils/Local.h" +#include "llvm/ADT/Statistic.h" +#include <set> +using namespace llvm; + +namespace { + Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced"); + + class LoopStrengthReduce : public FunctionPass { + LoopInfo *LI; + DominatorSet *DS; + bool Changed; + public: + virtual bool runOnFunction(Function &) { + LI = &getAnalysis<LoopInfo>(); + DS = &getAnalysis<DominatorSet>(); + Changed = false; + + for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + runOnLoop(*I); + return Changed; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired<LoopInfo>(); + AU.addRequired<DominatorSet>(); + } + private: + void runOnLoop(Loop *L); + void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, + Instruction *InsertBefore, + std::set<Instruction*> &DeadInsts); + void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts); + }; + RegisterOpt<LoopStrengthReduce> X("loop-reduce", + "Strength Reduce GEP Uses of Ind. Vars"); +} + +FunctionPass *llvm::createLoopStrengthReducePass() { + return new LoopStrengthReduce(); +} + +/// DeleteTriviallyDeadInstructions - If any of the instructions is the +/// specified set are trivially dead, delete them and see if this makes any of +/// their operands subsequently dead. +void LoopStrengthReduce:: +DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) { + while (!Insts.empty()) { + Instruction *I = *Insts.begin(); + Insts.erase(Insts.begin()); + if (isInstructionTriviallyDead(I)) { + for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) + if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) + Insts.insert(U); + I->getParent()->getInstList().erase(I); + Changed = true; + } + } +} + +void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, + Instruction *InsertBefore, + std::set<Instruction*> &DeadInsts) { + // We will strength reduce the GEP by splitting it into two parts. The first + // is a GEP to hold the initial value of the non-strength-reduced GEP upon + // entering the loop, which we will insert at the end of the loop preheader. + // The second is a GEP to hold the incremented value of the initial GEP. + // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so + // we will replace the indvar with a constant zero value to create the first + // GEP. + // + // We currently only handle GEP instructions that consist of zero or more + // constants and one instance of the canonical induction variable. + bool foundIndvar = false; + bool indvarLast = false; + std::vector<Value *> pre_op_vector; + std::vector<Value *> inc_op_vector; + Value *CanonicalIndVar = L->getCanonicalInductionVariable(); + for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) { + Value *operand = GEPI->getOperand(op); + if (operand == CanonicalIndVar) { + // FIXME: We currently only support strength reducing GEP instructions + // with one instance of the canonical induction variable. This means that + // we can't deal with statements of the form A[i][i]. + if (foundIndvar == true) + return; + + // FIXME: use getCanonicalInductionVariableIncrement to choose between + // one and neg one maybe? We need to support int *foo = GEP base, -1 + const Type *Ty = CanonicalIndVar->getType(); + pre_op_vector.push_back(Constant::getNullValue(Ty)); + inc_op_vector.push_back(ConstantInt::get(Ty, 1)); + foundIndvar = true; + indvarLast = true; + } else if (isa<Constant>(operand)) { + pre_op_vector.push_back(operand); + if (indvarLast == true) indvarLast = false; + } else + return; + } + // FIXME: handle GEPs where the indvar is not the last element of the index + // array. + if (indvarLast == false) + return; + assert(true == foundIndvar && "Indvar used by GEP not found in operand list"); + + // FIXME: Being able to hoist the definition of the initial pointer value + // would allow us to strength reduce more loops. For example, %tmp.32 in the + // following loop: + // entry: + // br label %no_exit.0 + // no_exit.0: ; preds = %entry, %no_exit.0 + // %init.1.0 = phi uint [ 0, %entry ], [ %indvar.next, %no_exit.0 ] + // %tmp.32 = load uint** %CROSSING + // %tmp.35 = getelementptr uint* %tmp.32, uint %init.1.0 + // br label %no_exit.0 + BasicBlock *Header = L->getHeader(); + if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0))) + if (!DS->dominates(GepPtrOp, Header->begin())) + return; + + // If all operands of the GEP we are going to insert into the preheader + // are constants, generate a GEP ConstantExpr instead. + // + // If there is only one operand after the initial non-constant one, we know + // that it was the induction variable, and has been replaced by a constant + // null value. In this case, replace the GEP with a use of pointer directly. + // + // + BasicBlock *Preheader = L->getLoopPreheader(); + Value *PreGEP; + if (isa<Constant>(GEPI->getOperand(0))) { + Constant *C = dyn_cast<Constant>(GEPI->getOperand(0)); + PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector); + } else if (pre_op_vector.size() == 1) { + PreGEP = GEPI->getOperand(0); + } else { + PreGEP = new GetElementPtrInst(GEPI->getOperand(0), + pre_op_vector, GEPI->getName(), + Preheader->getTerminator()); + } + + // The next step of the strength reduction is to create a PHI that will choose + // between the initial GEP we created and inserted into the preheader, and + // the incremented GEP that we will create below and insert into the loop body + PHINode *NewPHI = new PHINode(PreGEP->getType(), + GEPI->getName()+".str", InsertBefore); + NewPHI->addIncoming(PreGEP, Preheader); + + // Now, create the GEP instruction to increment the value selected by the PHI + // instruction we just created above by one, and add it as the second incoming + // Value and BasicBlock pair to the PHINode. + Instruction *IncrInst = + const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement()); + GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector, + GEPI->getName()+".inc", + IncrInst); + NewPHI->addIncoming(StrGEP, IncrInst->getParent()); + + // Replace all uses of the old GEP instructions with the new PHI + GEPI->replaceAllUsesWith(NewPHI); + + // The old GEP is now dead. + DeadInsts.insert(GEPI); + ++NumReduced; +} + +void LoopStrengthReduce::runOnLoop(Loop *L) { + // First step, transform all loops nesting inside of this loop. + for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I) + runOnLoop(*I); + + // Next, get the first PHINode since it is guaranteed to be the canonical + // induction variable for the loop by the preceding IndVarSimplify pass. + PHINode *PN = L->getCanonicalInductionVariable(); + if (0 == PN) + return; + + // Insert secondary PHI nodes after the canonical induction variable's PHI + // for the strength reduced pointers that we will be creating. + Instruction *InsertBefore = PN->getNext(); + + // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars + // pass creates code like this, which we can't currently detect: + // %tmp.1 = sub uint 2000, %indvar + // %tmp.8 = getelementptr int* %y, uint %tmp.1 + + // Strength reduce all GEPs in the Loop + std::set<Instruction*> DeadInsts; + for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); + UI != UE; ++UI) + if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) + strengthReduceGEP(GEPI, L, InsertBefore, DeadInsts); + + // Clean up after ourselves + if (!DeadInsts.empty()) { + DeleteTriviallyDeadInstructions(DeadInsts); + + // At this point, we know that we have killed one or more GEP instructions. + // It is worth checking to see if the cann indvar is also dead, so that we + // can remove it as well. The requirements for the cann indvar to be + // considered dead are: + // 1. the cann indvar has one use + // 2. the use is an add instruction + // 3. the add has one use + // 4. the add is used by the cann indvar + // If all four cases above are true, then we can remove both the add and + // the cann indvar. + if (PN->hasOneUse()) { + BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin())); + if (BO && BO->getOpcode() == Instruction::Add) + if (BO->hasOneUse()) { + PHINode *PotentialIndvar = dyn_cast<PHINode>(*(BO->use_begin())); + if (PotentialIndvar && PN == PotentialIndvar) { + PN->dropAllReferences(); + DeadInsts.insert(BO); + DeadInsts.insert(PN); + DeleteTriviallyDeadInstructions(DeadInsts); + } + } + } + } +} |