+void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
+ printf("{\n");
+ for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(),
+ E = d.end(); I != E; ++I) {
+ if (I->second == MemoryDependenceAnalysis::None)
+ printf("None\n");
+ else
+ I->second->dump();
+ }
+ printf("}\n");
+}
+
+Value* GVN::CollapsePhi(PHINode* p) {
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ Value* constVal = p->hasConstantValue();
+
+ if (constVal) {
+ if (Instruction* inst = dyn_cast<Instruction>(constVal)) {
+ if (DT.dominates(inst, p))
+ if (isSafeReplacement(p, inst))
+ return inst;
+ } else {
+ return constVal;
+ }
+ }
+
+ return 0;
+}
+
+bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
+ if (!isa<PHINode>(inst))
+ return true;
+
+ for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
+ UI != E; ++UI)
+ if (PHINode* use_phi = dyn_cast<PHINode>(UI))
+ if (use_phi->getParent() == inst->getParent())
+ return false;
+
+ return true;
+}
+
+/// 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,
+ bool top_level) {
+
+ // If we have already computed this value, return the previously computed val.
+ DenseMap<BasicBlock*, Value*>::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));
+
+ // 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);
+
+ PN->addIncoming(val, *PI);
+ }
+
+ // Attempt to collapse PHI nodes that are trivially redundant
+ Value* v = CollapsePhi(PN);
+ if (v) {
+ MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+ MD.removeInstruction(PN);
+ PN->replaceAllUsesWith(v);
+
+ for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+ E = Phis.end(); I != E; ++I)
+ if (I->second == PN)
+ I->second = v;
+
+ PN->eraseFromParent();
+
+ Phis[BB] = v;
+
+ return v;
+ }
+
+ // Cache our phi construction results
+ phiMap[orig->getPointerOperand()].insert(PN);
+ return PN;
+}
+
+/// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
+/// non-local by performing PHI construction.
+bool GVN::processNonLocalLoad(LoadInst* L,
+ SmallVector<Instruction*, 4>& toErase) {
+ MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+ // Find the non-local dependencies of the load
+ DenseMap<BasicBlock*, Value*> deps;
+ MD.getNonLocalDependency(L, deps);
+
+ DenseMap<BasicBlock*, Value*> repl;
+
+ // Filter out useless results (non-locals, etc)
+ for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
+ I != E; ++I)
+ if (I->second == MemoryDependenceAnalysis::None) {
+ return false;
+ } else if (I->second == MemoryDependenceAnalysis::NonLocal) {
+ continue;
+ } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
+ if (S->getPointerOperand() == L->getPointerOperand())
+ repl[I->first] = S->getOperand(0);
+ else
+ return false;
+ } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
+ if (LD->getPointerOperand() == L->getPointerOperand())
+ repl[I->first] = LD;
+ else
+ return false;
+ } else {
+ return false;
+ }
+
+ // Use cached PHI construction information from previous runs
+ 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));
+ }
+ }
+
+ // Perform PHI construction
+ SmallPtrSet<BasicBlock*, 4> visited;
+ Value* v = GetValueForBlock(L->getParent(), L, repl, true);
+
+ MD.removeInstruction(L);
+ L->replaceAllUsesWith(v);
+ toErase.push_back(L);
+ NumGVNLoad++;
+
+ return true;
+}
+
+/// processLoad - Attempt to eliminate a load, first by eliminating it
+/// locally, and then attempting non-local elimination if that fails.