From b21bf9a8d582a40142a322f508a2e8c2c2164893 Mon Sep 17 00:00:00 2001 From: Jeff Cohen Date: Sat, 5 Mar 2005 22:40:34 +0000 Subject: [PATCH] Reuse induction variables created for strength-reduced GEPs by other similar GEPs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20466 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopStrengthReduce.cpp | 93 +++++++++++++------- 1 file changed, 61 insertions(+), 32 deletions(-) diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp index 52b6b9887a7..b2b0064e112 100644 --- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp +++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp @@ -35,6 +35,22 @@ using namespace llvm; namespace { Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced"); + class GEPCache + { + public: + GEPCache() : CachedPHINode(0), Map() {} + + GEPCache* operator[](Value *v) { + std::map::iterator I = Map.find(v); + if (I == Map.end()) + I = Map.insert(std::pair(v, GEPCache())).first; + return &(I->second); + } + + PHINode *CachedPHINode; + std::map Map; + }; + class LoopStrengthReduce : public FunctionPass { LoopInfo *LI; DominatorSet *DS; @@ -65,6 +81,7 @@ namespace { private: void runOnLoop(Loop *L); void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, + GEPCache* GEPCache, Instruction *InsertBefore, std::set &DeadInsts); void DeleteTriviallyDeadInstructions(std::set &Insts); @@ -96,6 +113,7 @@ DeleteTriviallyDeadInstructions(std::set &Insts) { } void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, + GEPCache *Cache, Instruction *InsertBefore, std::set &DeadInsts) { // We will strength reduce the GEP by splitting it into two parts. The first @@ -117,6 +135,7 @@ void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, BasicBlock *Header = L->getHeader(); BasicBlock *Preheader = L->getLoopPreheader(); bool AllConstantOperands = true; + Cache = (*Cache)[GEPI->getOperand(0)]; for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) { Value *operand = GEPI->getOperand(op); @@ -145,6 +164,7 @@ void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, AllConstantOperands = false; } else return; + Cache = (*Cache)[operand]; } assert(indvar > 0 && "Indvar used by GEP not found in operand list"); @@ -157,7 +177,7 @@ void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, if (!DS->dominates(GepPtrOp, Preheader->getTerminator())) return; - // Don't reduced multiplies that the target can handle via addressing modes. + // Don't reduce multiplies that the target can handle via addressing modes. uint64_t sz = getAnalysis().getTypeSize(ty); for (unsigned i = 1; i <= MaxTargetAMSize; i *= 2) if (i == sz) @@ -169,38 +189,46 @@ void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, // 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. - Value *PreGEP; - if (AllConstantOperands && isa(GEPI->getOperand(0))) { - Constant *C = dyn_cast(GEPI->getOperand(0)); - PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector); - } else if (pre_op_vector.size() == 1) { - PreGEP = GEPI->getOperand(0); + PHINode *NewPHI; + if (1) { + Value *PreGEP; + if (AllConstantOperands && isa(GEPI->getOperand(0))) { + Constant *C = dyn_cast(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()+".pre", + 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 + NewPHI = new PHINode(PreGEP->getType(), + GEPI->getName()+".str", InsertBefore); + NewPHI->addIncoming(PreGEP, Preheader); + + // Now, create the GEP instruction to increment by one the value selected by + // the PHI instruction we just created above, and add it as the second + // incoming Value/BasicBlock pair to the PHINode. It is inserted before the + // increment of the canonical induction variable. + Instruction *IncrInst = + const_cast(L->getCanonicalInductionVariableIncrement()); + GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector, + GEPI->getName()+".inc", + IncrInst); + pred_iterator PI = pred_begin(Header); + if (*PI == Preheader) + ++PI; + NewPHI->addIncoming(StrGEP, *PI); + Cache->CachedPHINode = NewPHI; } else { - PreGEP = new GetElementPtrInst(GEPI->getOperand(0), - pre_op_vector, GEPI->getName()+".pre", - Preheader->getTerminator()); + // Reuse previously created pointer, as it is identical to the one we were + // about to create. + NewPHI = Cache->CachedPHINode; } - - // 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 by one the value selected by - // the PHI instruction we just created above, and add it as the second - // incoming Value/BasicBlock pair to the PHINode. It is inserted before the - // increment of the canonical induction variable. - Instruction *IncrInst = - const_cast(L->getCanonicalInductionVariableIncrement()); - GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector, - GEPI->getName()+".inc", - IncrInst); - pred_iterator PI = pred_begin(Header); - if (*PI == Preheader) - ++PI; - NewPHI->addIncoming(StrGEP, *PI); if (GEPI->getNumOperands() - 1 == indvar) { // If there were no operands following the induction variable, replace all @@ -246,10 +274,11 @@ void LoopStrengthReduce::runOnLoop(Loop *L) { // strength reduced pointers we'll be creating after the canonical induction // variable's PHI. std::set DeadInsts; + GEPCache Cache; for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); UI != UE; ++UI) if (GetElementPtrInst *GEPI = dyn_cast(*UI)) - strengthReduceGEP(GEPI, L, PN->getNext(), DeadInsts); + strengthReduceGEP(GEPI, L, &Cache, PN->getNext(), DeadInsts); // Clean up after ourselves if (!DeadInsts.empty()) { -- 2.34.1