namespace llvm {
template <> struct DenseMapKeyInfo<Expression> {
- 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;
(unsigned)((uintptr_t)e.type >> 9) +
hash * 37;
- for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end();
- I != E; ++I)
+ for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
+ E = e.varargs.end(); I != E; ++I)
hash = *I + hash * 37;
return hash;
DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
+ typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
+ PhiMapType phiMap;
+
+
// This transformation requires dominator postdominator info
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
ValueNumberedSet& currAvail,
DenseMap<Value*, LoadInst*>& lastSeenLoad,
SmallVector<Instruction*, 4>& toErase);
- bool processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase);
+ bool processNonLocalLoad(LoadInst* L,
+ SmallVector<Instruction*, 4>& toErase);
Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
- DenseMap<BasicBlock*, Value*> &Phis);
+ DenseMap<BasicBlock*, Value*> &Phis,
+ bool top_level = false);
void dump(DenseMap<BasicBlock*, Value*>& 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<BasicBlock*, Value*> &Phis) {
+ DenseMap<BasicBlock*, Value*> &Phis,
+ bool top_level) {
// If we have already computed this value, return the previously computed val.
- Value *&V = Phis[BB];
- if (V) return V;
+ DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
+ if (V != Phis.end() && !top_level) return V->second;
BasicBlock* singlePred = BB->getSinglePredecessor();
- if (singlePred)
- return V = GetValueForBlock(singlePred, orig, Phis);
-
+ 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)));
- V = PN;
+
+ if (Phis.count(BB) == 0)
+ Phis.insert(std::make_pair(BB, PN));
bool all_same = true;
Value* first = 0;
return first;
}
+ phiMap[orig->getPointerOperand()].insert(PN);
return PN;
}
-bool GVN::processNonLocalLoad(LoadInst* L, SmallVector<Instruction*, 4>& toErase) {
+bool GVN::processNonLocalLoad(LoadInst* L,
+ SmallVector<Instruction*, 4>& toErase) {
MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
DenseMap<BasicBlock*, Value*> deps;
MD.getNonLocalDependency(L, deps);
DenseMap<BasicBlock*, Value*> repl;
+
for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
I != E; ++I)
if (I->second == MemoryDependenceAnalysis::None) {
continue;
}else if (StoreInst* S = dyn_cast<StoreInst>(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<LoadInst>(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<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
+ for (SmallPtrSet<Instruction*, 4>::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<BasicBlock*, 4> 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;
}
// Clean out global sets from any previous functions
VN.clear();
availableOut.clear();
+ phiMap.clear();
bool changed_function = false;
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();