//===----------------------------------------------------------------------===//
#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"
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;
nextValueNumber = 1;
}
+/// erase - Remove a value from the value numbering
+void ValueTable::erase(Value* V) {
+ valueNumbering.erase(V);
+}
+
//===----------------------------------------------------------------------===//
// ValueNumberedSet Class
//===----------------------------------------------------------------------===//
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);
- Value *performPHIConstruction(BasicBlock *BB, LoadInst* orig,
- DenseMap<BasicBlock*, Value*> &Phis,
- SmallPtrSet<BasicBlock*, 4>& visited);
+ bool processNonLocalLoad(LoadInst* L,
+ SmallVector<Instruction*, 4>& toErase);
+ Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
+ DenseMap<BasicBlock*, Value*> &Phis,
+ bool top_level = false);
void dump(DenseMap<BasicBlock*, Value*>& d);
+ bool iterateOnFunction(Function &F);
};
char GVN::ID = 0;
}
-Value *GVN::performPHIConstruction(BasicBlock *BB, LoadInst* orig,
- DenseMap<BasicBlock*, Value*> &Phis,
- SmallPtrSet<BasicBlock*, 4>& visited) {
- DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB);
- if (DI != Phis.end())
- return DI->second;
+/// 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;
- unsigned numPreds = std::distance(pred_begin(BB), pred_end(BB));
+ 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 (numPreds == 1) {
- DenseMap<BasicBlock*, Value*>::iterator DI = Phis.find(BB);
- if (DI != Phis.end()) {
- Phis.insert(std::make_pair(BB, DI->second));
- return DI->second;
- } else {
- visited.insert(BB);
- Value* domV = performPHIConstruction(*pred_begin(BB), orig, Phis, visited);
- visited.erase(BB);
-
- Phis.insert(std::make_pair(BB, domV));
- return domV;
- }
- } else {
- PHINode *PN = new PHINode(orig->getType(), orig->getName()+".rle", BB->begin());
- PN->reserveOperandSpace(numPreds);
-
- visited.insert(BB);
- // Fill in the incoming values for the block.
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
- if (!visited.count(*PI))
- PN->addIncoming(performPHIConstruction(*PI, orig, Phis, visited), *PI);
- else
- PN->addIncoming(PN, *PI);
- visited.erase(BB);
-
- 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 (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);
- if (all_same) {
- PN->eraseFromParent();
- return first;
+ PN->addIncoming(val, *PI);
+ }
+
+ Value* v = PN->hasConstantValue();
+ if (v) {
+ if (Instruction* inst = dyn_cast<Instruction>(v)) {
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ if (DT.dominates(inst, PN)) {
+ MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+ MD.removeInstruction(PN);
+ PN->replaceAllUsesWith(inst);
+
+ SmallVector<BasicBlock*, 4> toRemove;
+ for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+ E = Phis.end(); I != E; ++I)
+ if (I->second == PN)
+ toRemove.push_back(I->first);
+ for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
+ E= toRemove.end(); I != E; ++I)
+ Phis[*I] = inst;
+
+ PN->eraseFromParent();
+
+ Phis[BB] = inst;
+
+ return inst;
+ }
} else {
- return PN;
+ MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+
+ MD.removeInstruction(PN);
+ PN->replaceAllUsesWith(v);
+
+ SmallVector<BasicBlock*, 4> toRemove;
+ for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
+ E = Phis.end(); I != E; ++I)
+ if (I->second == PN)
+ toRemove.push_back(I->first);
+ for (SmallVector<BasicBlock*, 4>::iterator I = toRemove.begin(),
+ E= toRemove.end(); I != E; ++I)
+ Phis[*I] = v;
+
+ PN->eraseFromParent();
+
+ Phis[BB] = v;
+
+ return v;
}
}
+
+ 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;
- bool ret = MD.getNonLocalDependency(L, deps);
- if (!ret)
- return false;
+ 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) {
return false;
- } else if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
+ } else if (I->second == MemoryDependenceAnalysis::NonLocal) {
+ 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 = performPHIConstruction(L->getParent(), L, repl, visited);
+ Value* v = GetValueForBlock(L->getParent(), L, repl, true);
MD.removeInstruction(L);
L->replaceAllUsesWith(v);
toErase.push_back(L);
+ NumGVNLoad++;
return true;
}
// ... to a pointer that has been loaded from before...
MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
+ bool removedNonLocal = false;
Instruction* dep = MD.getDependency(L);
if (dep == MemoryDependenceAnalysis::NonLocal &&
- L->getParent() != &L->getParent()->getParent()->getEntryBlock())
- processNonLocalLoad(L, toErase);
+ L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
+ removedNonLocal = processNonLocalLoad(L, toErase);
+
+ if (!removedNonLocal)
+ last = L;
+
+ return removedNonLocal;
+ }
+
+
bool deletedLoad = false;
while (dep != MemoryDependenceAnalysis::None &&
return deletedLoad;
}
-/// buildsets_availout - When calculating availability, handle an instruction
+/// processInstruction - When calculating availability, handle an instruction
/// by inserting it into the appropriate sets
bool GVN::processInstruction(Instruction* I,
ValueNumberedSet& currAvail,
unsigned num = VN.lookup_or_add(I);
- if (currAvail.test(num)) {
+ if (PHINode* p = dyn_cast<PHINode>(I)) {
+ Value* constVal = p->hasConstantValue();
+
+ if (constVal) {
+ if (Instruction* inst = dyn_cast<Instruction>(constVal)) {
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ if (DT.dominates(inst, p)) {
+ for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
+ PI != PE; ++PI)
+ if (PI->second.count(p))
+ PI->second.erase(p);
+
+ p->replaceAllUsesWith(inst);
+ toErase.push_back(p);
+ }
+ } else {
+ p->replaceAllUsesWith(constVal);
+ toErase.push_back(p);
+ }
+ }
+ } else if (currAvail.test(num)) {
Value* repl = find_leader(currAvail, num);
+ VN.erase(I);
I->replaceAllUsesWith(repl);
toErase.push_back(I);
return true;
// GVN::runOnFunction - This is the main transformation entry point for a
// function.
//
-bool GVN::runOnFunction(Function &F) {
+bool GVN::runOnFunction(Function& F) {
+ bool changed = false;
+ bool shouldContinue = true;
+
+ while (shouldContinue) {
+ shouldContinue = iterateOnFunction(F);
+ changed |= shouldContinue;
+ }
+
+ return changed;
+}
+
+
+// GVN::iterateOnFunction - Executes one iteration of GVN
+bool GVN::iterateOnFunction(Function &F) {
// Clean out global sets from any previous functions
VN.clear();
availableOut.clear();
+ phiMap.clear();
bool changed_function = false;
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<Instruction*, 4>::iterator I = toErase.begin(),
E = toErase.end(); I != E; ++I)
(*I)->eraseFromParent();
projects / oota-llvm.git / blobdiff