X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=edd11e8e493b0dff793a18e7c4c49f80e1799925;hb=a37226af81bf10ba9f23ef065d8efc58877d3dc3;hp=3b8adef4aa79ffb1b8fdf11518f594cde4a7d2b6;hpb=0cd320362e91852c8f7f2c8c4841498aab7f92fa;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 3b8adef4aa7..edd11e8e493 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -13,12 +13,14 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "gvn" -#include "llvm/Value.h" + #include "llvm/Transforms/Scalar.h" #include "llvm/BasicBlock.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" +#include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/Function.h" +#include "llvm/Instructions.h" +#include "llvm/Value.h" #include "llvm/Analysis/Dominators.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" @@ -144,8 +146,13 @@ namespace { namespace llvm { template <> struct DenseMapKeyInfo { - static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } - static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); } + static inline Expression getEmptyKey() { + return Expression(Expression::EMPTY); + } + + static inline Expression getTombstoneKey() { + return Expression(Expression::TOMBSTONE); + } static unsigned getHashValue(const Expression e) { unsigned hash = e.opcode; @@ -158,8 +165,8 @@ template <> struct DenseMapKeyInfo { (unsigned)((uintptr_t)e.type >> 9) + hash * 37; - for (SmallVector::const_iterator I = e.varargs.begin(), E = e.varargs.end(); - I != E; ++I) + for (SmallVector::const_iterator I = e.varargs.begin(), + E = e.varargs.end(); I != E; ++I) hash = *I + hash * 37; return hash; @@ -556,6 +563,11 @@ void ValueTable::clear() { nextValueNumber = 1; } +/// erase - Remove a value from the value numbering +void ValueTable::erase(Value* V) { + valueNumbering.erase(V); +} + //===----------------------------------------------------------------------===// // ValueNumberedSet Class //===----------------------------------------------------------------------===// @@ -630,6 +642,10 @@ namespace { DenseMap availableOut; + typedef DenseMap > PhiMapType; + PhiMapType phiMap; + + // This transformation requires dominator postdominator info virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); @@ -649,9 +665,11 @@ namespace { ValueNumberedSet& currAvail, DenseMap& lastSeenLoad, SmallVector& toErase); - bool processNonLocalLoad(LoadInst* L, SmallVector& toErase); - Value *performPHIConstruction(BasicBlock *BB, LoadInst* orig, - DenseMap &Phis); + bool processNonLocalLoad(LoadInst* L, + SmallVector& toErase); + Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, + DenseMap &Phis, + bool top_level = false); void dump(DenseMap& d); }; @@ -705,71 +723,122 @@ void GVN::dump(DenseMap& d) { } -Value *GVN::performPHIConstruction(BasicBlock *BB, LoadInst* orig, - DenseMap &Phis) { - DenseMap::iterator DI = Phis.find(BB); - if (DI != Phis.end()) - return DI->second; - - unsigned numPreds = std::distance(pred_begin(BB), pred_end(BB)); - - if (numPreds == 1) { - Phis[BB] = Phis[*pred_begin(BB)]; - return Phis[BB]; - } else { - PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", BB->begin()); - PN->reserveOperandSpace(numPreds); +/// GetValueForBlock - Get the value to use within the specified basic block. +/// available values are in Phis. +Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, + DenseMap &Phis, + bool top_level) { - // Fill in the incoming values for the block. - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - PN->addIncoming(performPHIConstruction(*PI, orig, Phis), *PI); - - bool all_same = PN->getNumIncomingValues() != 1; - Value* first = PN->getIncomingValue(0); - for (unsigned i = 1; i < PN->getNumIncomingValues(); ++i) - all_same &= (PN->getIncomingValue(i) == first); - - if (all_same) { - PN->eraseFromParent(); - return first; - } else { - return PN; - } + // If we have already computed this value, return the previously computed val. + DenseMap::iterator V = Phis.find(BB); + if (V != Phis.end() && !top_level) return V->second; + + BasicBlock* singlePred = BB->getSinglePredecessor(); + if (singlePred) { + Value *ret = GetValueForBlock(singlePred, orig, Phis); + Phis[BB] = ret; + return ret; + } + // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so + // now, then get values to fill in the incoming values for the PHI. + PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", + BB->begin()); + PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); + + if (Phis.count(BB) == 0) + Phis.insert(std::make_pair(BB, PN)); + + bool all_same = true; + Value* first = 0; + + // Fill in the incoming values for the block. + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + Value* val = GetValueForBlock(*PI, orig, Phis); + if (first == 0) + first = val; + else if (all_same && first != val) + all_same = false; + + PN->addIncoming(val, *PI); } + + if (all_same) { + MemoryDependenceAnalysis& MD = getAnalysis(); + + MD.removeInstruction(PN); + PN->replaceAllUsesWith(first); + + SmallVector toRemove; + for (DenseMap::iterator I = Phis.begin(), + E = Phis.end(); I != E; ++I) + if (I->second == PN) + toRemove.push_back(I->first); + for (SmallVector::iterator I = toRemove.begin(), + E= toRemove.end(); I != E; ++I) + Phis[*I] = first; + + PN->eraseFromParent(); + + Phis[BB] = first; + + return first; + } + + phiMap[orig->getPointerOperand()].insert(PN); + return PN; } -bool GVN::processNonLocalLoad(LoadInst* L, SmallVector& toErase) { +bool GVN::processNonLocalLoad(LoadInst* L, + SmallVector& toErase) { MemoryDependenceAnalysis& MD = getAnalysis(); DenseMap deps; - bool ret = MD.getNonLocalDependency(L, deps); - if (!ret) - return false; + MD.getNonLocalDependency(L, deps); DenseMap repl; + for (DenseMap::iterator I = deps.begin(), E = deps.end(); I != E; ++I) if (I->second == MemoryDependenceAnalysis::None) { return false; - } else if (StoreInst* S = dyn_cast(I->second)) { + } else if (I->second == MemoryDependenceAnalysis::NonLocal) { + continue; + }else if (StoreInst* S = dyn_cast(I->second)) { if (S->getPointerOperand() == L->getPointerOperand()) - repl.insert(std::make_pair(I->first, S->getOperand(0))); + repl[I->first] = S->getOperand(0); else return false; } else if (LoadInst* LD = dyn_cast(I->second)) { if (LD->getPointerOperand() == L->getPointerOperand()) - repl.insert(std::make_pair(I->first, LD)); + repl[I->first] = LD; else return false; } else { return false; } - Value* v = performPHIConstruction(L->getParent(), L, repl); + SmallPtrSet& p = phiMap[L->getPointerOperand()]; + for (SmallPtrSet::iterator I = p.begin(), E = p.end(); + I != E; ++I) { + if ((*I)->getParent() == L->getParent()) { + MD.removeInstruction(L); + L->replaceAllUsesWith(*I); + toErase.push_back(L); + NumGVNLoad++; + + return true; + } else { + repl.insert(std::make_pair((*I)->getParent(), *I)); + } + } + + SmallPtrSet visited; + Value* v = GetValueForBlock(L->getParent(), L, repl, true); MD.removeInstruction(L); L->replaceAllUsesWith(v); toErase.push_back(L); + NumGVNLoad++; return true; } @@ -851,6 +920,7 @@ bool GVN::processInstruction(Instruction* I, if (currAvail.test(num)) { Value* repl = find_leader(currAvail, num); + VN.erase(I); I->replaceAllUsesWith(repl); toErase.push_back(I); return true; @@ -869,6 +939,7 @@ bool GVN::runOnFunction(Function &F) { // Clean out global sets from any previous functions VN.clear(); availableOut.clear(); + phiMap.clear(); bool changed_function = false; @@ -891,11 +962,15 @@ bool GVN::runOnFunction(Function &F) { currAvail = availableOut[DI->getIDom()->getBlock()]; for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); - BI != BE; ++BI) { - changed_function |= processInstruction(BI, currAvail, lastSeenLoad, toErase); + BI != BE; ) { + changed_function |= processInstruction(BI, currAvail, + lastSeenLoad, toErase); NumGVNInstr += toErase.size(); + // Avoid iterator invalidation + ++BI; + for (SmallVector::iterator I = toErase.begin(), E = toErase.end(); I != E; ++I) (*I)->eraseFromParent();