X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=edd11e8e493b0dff793a18e7c4c49f80e1799925;hb=a37226af81bf10ba9f23ef065d8efc58877d3dc3;hp=42e9ee8900fcfa47abc51475647b79917bd2f87b;hpb=891eecb040b26426fdb31499939eb1916ce6bf8d;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 42e9ee8900f..edd11e8e493 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -146,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; @@ -160,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; @@ -558,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 //===----------------------------------------------------------------------===// @@ -632,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(); @@ -651,9 +665,11 @@ namespace { ValueNumberedSet& currAvail, DenseMap& lastSeenLoad, SmallVector& toErase); - bool processNonLocalLoad(LoadInst* L, SmallVector& toErase); + bool processNonLocalLoad(LoadInst* L, + SmallVector& toErase); Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, - DenseMap &Phis); + DenseMap &Phis, + bool top_level = false); void dump(DenseMap& d); }; @@ -710,44 +726,77 @@ void GVN::dump(DenseMap& d) { /// 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) { - DominatorTree &DT = getAnalysis(); + DenseMap &Phis, + bool top_level) { // If we have already computed this value, return the previously computed val. - Value *&V = Phis[BB]; - if (V) return V; - - DomTreeNode *IDom = DT.getNode(BB)->getIDom(); - - if (IDom && Phis.count(IDom->getBlock())) { - return V = GetValueForBlock(IDom->getBlock(), orig, Phis); + 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; } - - if (std::distance(pred_begin(BB), pred_end(BB)) == 1) - return V = GetValueForBlock(IDom->getBlock(), orig, Phis); - // 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))); - V = PN; + + 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) - PN->addIncoming(GetValueForBlock(*PI, orig, Phis), *PI); + 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) { @@ -756,24 +805,40 @@ bool GVN::processNonLocalLoad(LoadInst* L, SmallVector& toErase 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; } + 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); + Value* v = GetValueForBlock(L->getParent(), L, repl, true); MD.removeInstruction(L); L->replaceAllUsesWith(v); toErase.push_back(L); + NumGVNLoad++; return true; } @@ -855,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; @@ -873,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; @@ -896,7 +963,8 @@ bool GVN::runOnFunction(Function &F) { for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ) { - changed_function |= processInstruction(BI, currAvail, lastSeenLoad, toErase); + changed_function |= processInstruction(BI, currAvail, + lastSeenLoad, toErase); NumGVNInstr += toErase.size();