#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"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
- PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
+ PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY,
TOMBSTONE };
ExpressionOpcode opcode;
uint32_t secondVN;
uint32_t thirdVN;
SmallVector<uint32_t, 4> varargs;
+ Value* function;
Expression() { }
Expression(ExpressionOpcode o) : opcode(o) { }
return true;
else if (type != other.type)
return false;
+ else if (function != other.function)
+ return false;
else if (firstVN != other.firstVN)
return false;
else if (secondVN != other.secondVN)
return false;
else if (type != other.type)
return true;
+ else if (function != other.function)
+ return true;
else if (firstVN != other.firstVN)
return true;
else if (secondVN != other.secondVN)
private:
DenseMap<Value*, uint32_t> valueNumbering;
DenseMap<Expression, uint32_t> expressionNumbering;
+ AliasAnalysis* AA;
uint32_t nextValueNumber;
Expression create_expression(SelectInst* V);
Expression create_expression(CastInst* C);
Expression create_expression(GetElementPtrInst* G);
+ Expression create_expression(CallInst* C);
public:
- ValueTable() { nextValueNumber = 1; }
+ ValueTable() : nextValueNumber(1) { }
uint32_t lookup_or_add(Value* V);
uint32_t lookup(Value* V) const;
void add(Value* V, uint32_t num);
void clear();
void erase(Value* v);
unsigned size();
+ void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
};
}
namespace llvm {
-template <> struct DenseMapKeyInfo<Expression> {
+template <> struct DenseMapInfo<Expression> {
static inline Expression getEmptyKey() {
return Expression(Expression::EMPTY);
}
E = e.varargs.end(); I != E; ++I)
hash = *I + hash * 37;
+ hash = (unsigned)((uintptr_t)e.function >> 4) ^
+ (unsigned)((uintptr_t)e.function >> 9) +
+ hash * 37;
+
return hash;
}
+ static bool isEqual(const Expression &LHS, const Expression &RHS) {
+ return LHS == RHS;
+ }
static bool isPod() { return true; }
};
}
}
}
+Expression ValueTable::create_expression(CallInst* C) {
+ Expression e;
+
+ e.type = C->getType();
+ e.firstVN = 0;
+ e.secondVN = 0;
+ e.thirdVN = 0;
+ e.function = C->getCalledFunction();
+ e.opcode = Expression::CALL;
+
+ for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
+ I != E; ++I)
+ e.varargs.push_back(lookup_or_add(*I));
+
+ return e;
+}
+
Expression ValueTable::create_expression(BinaryOperator* BO) {
Expression e;
e.firstVN = lookup_or_add(BO->getOperand(0));
e.secondVN = lookup_or_add(BO->getOperand(1));
e.thirdVN = 0;
+ e.function = 0;
e.type = BO->getType();
e.opcode = getOpcode(BO);
e.firstVN = lookup_or_add(C->getOperand(0));
e.secondVN = lookup_or_add(C->getOperand(1));
e.thirdVN = 0;
+ e.function = 0;
e.type = C->getType();
e.opcode = getOpcode(C);
e.firstVN = lookup_or_add(C->getOperand(0));
e.secondVN = 0;
e.thirdVN = 0;
+ e.function = 0;
e.type = C->getType();
e.opcode = getOpcode(C);
e.firstVN = lookup_or_add(S->getOperand(0));
e.secondVN = lookup_or_add(S->getOperand(1));
e.thirdVN = lookup_or_add(S->getOperand(2));
+ e.function = 0;
e.type = S->getType();
e.opcode = Expression::SHUFFLE;
e.firstVN = lookup_or_add(E->getOperand(0));
e.secondVN = lookup_or_add(E->getOperand(1));
e.thirdVN = 0;
+ e.function = 0;
e.type = E->getType();
e.opcode = Expression::EXTRACT;
e.firstVN = lookup_or_add(I->getOperand(0));
e.secondVN = lookup_or_add(I->getOperand(1));
e.thirdVN = lookup_or_add(I->getOperand(2));
+ e.function = 0;
e.type = I->getType();
e.opcode = Expression::INSERT;
e.firstVN = lookup_or_add(I->getCondition());
e.secondVN = lookup_or_add(I->getTrueValue());
e.thirdVN = lookup_or_add(I->getFalseValue());
+ e.function = 0;
e.type = I->getType();
e.opcode = Expression::SELECT;
e.firstVN = lookup_or_add(G->getPointerOperand());
e.secondVN = 0;
e.thirdVN = 0;
+ e.function = 0;
e.type = G->getType();
e.opcode = Expression::GEP;
if (VI != valueNumbering.end())
return VI->second;
-
- if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
+ if (CallInst* C = dyn_cast<CallInst>(V)) {
+ if (C->getCalledFunction() &&
+ AA->doesNotAccessMemory(C->getCalledFunction())) {
+ Expression e = create_expression(C);
+
+ DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
+ if (EI != expressionNumbering.end()) {
+ valueNumbering.insert(std::make_pair(V, EI->second));
+ return EI->second;
+ } else {
+ expressionNumbering.insert(std::make_pair(e, nextValueNumber));
+ valueNumbering.insert(std::make_pair(V, nextValueNumber));
+
+ return nextValueNumber++;
+ }
+ } else {
+ valueNumbering.insert(std::make_pair(V, nextValueNumber));
+ return nextValueNumber++;
+ }
+ } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
Expression e = create_expression(BO);
DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
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();
AU.addRequired<DominatorTree>();
AU.addRequired<MemoryDependenceAnalysis>();
+ AU.addRequired<AliasAnalysis>();
+ AU.addPreserved<AliasAnalysis>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
DenseMap<BasicBlock*, Value*> &Phis,
bool top_level = false);
void dump(DenseMap<BasicBlock*, Value*>& d);
+ bool iterateOnFunction(Function &F);
+ Value* CollapsePhi(PHINode* p);
+ bool isSafeReplacement(PHINode* p, Instruction* inst);
};
char GVN::ID = 0;
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.
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) {
+ // Attempt to collapse PHI nodes that are trivially redundant
+ Value* v = CollapsePhi(PN);
+ if (v) {
MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
-
+
MD.removeInstruction(PN);
- PN->replaceAllUsesWith(first);
-
- SmallVector<BasicBlock*, 4> toRemove;
+ PN->replaceAllUsesWith(v);
+
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] = first;
-
+ I->second = v;
+
PN->eraseFromParent();
-
- Phis[BB] = first;
-
- return first;
+
+ 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)) {
+ } 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;
}
+ // 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.
bool GVN::processLoad(LoadInst* L,
DenseMap<Value*, LoadInst*>& lastLoad,
SmallVector<Instruction*, 4>& toErase) {
// ... 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;
+ // Walk up the dependency chain until we either find
+ // a dependency we can use, or we can't walk any further
while (dep != MemoryDependenceAnalysis::None &&
dep != MemoryDependenceAnalysis::NonLocal &&
(isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
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)) {
+ // Collapse PHI nodes
+ if (PHINode* p = dyn_cast<PHINode>(I)) {
+ Value* constVal = CollapsePhi(p);
+
+ if (constVal) {
+ for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
+ PI != PE; ++PI)
+ if (PI->second.count(p))
+ PI->second.erase(p);
+
+ p->replaceAllUsesWith(constVal);
+ toErase.push_back(p);
+ }
+ // Perform value-number based elimination
+ } else if (currAvail.test(num)) {
Value* repl = find_leader(currAvail, num);
VN.erase(I);
// GVN::runOnFunction - This is the main transformation entry point for a
// function.
//
-bool GVN::runOnFunction(Function &F) {
+bool GVN::runOnFunction(Function& F) {
+ VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
+
+ 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;
projects / oota-llvm.git / blobdiff