#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
using namespace llvm;
STATISTIC(NumGVNInstr, "Number of instructions deleted");
STATISTIC(NumGVNLoad, "Number of loads deleted");
STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
+static cl::opt<bool> EnablePRE("enable-pre",
+ cl::init(true), cl::Hidden);
+
//===----------------------------------------------------------------------===//
// ValueTable Class
//===----------------------------------------------------------------------===//
SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
- EXTRACTVALUE, INSERTVALUE, EMPTY, TOMBSTONE };
+ EMPTY, TOMBSTONE };
ExpressionOpcode opcode;
const Type* type;
Expression create_expression(GetElementPtrInst* G);
Expression create_expression(CallInst* C);
Expression create_expression(Constant* C);
- Expression create_expression(InsertValueInst* I);
- Expression create_expression(ExtractValueInst* I);
public:
ValueTable() : nextValueNumber(1) { }
uint32_t lookup_or_add(Value* V);
}
}
-Expression ValueTable::create_expression(InsertValueInst* I) {
- Expression e;
-
- e.type = I->getType();
- e.firstVN = lookup_or_add(I->getOperand(0));
- e.secondVN = lookup_or_add(I->getOperand(1));
- e.thirdVN = 0;
- e.function = 0;
- e.opcode = Expression::INSERTVALUE;
-
- for (InsertValueInst::op_iterator OI = I->op_begin()+2,
- OE = I->op_end(); OI != OE; ++OI)
- e.varargs.push_back(lookup_or_add(I));
-
- return e;
-}
-
-Expression ValueTable::create_expression(ExtractValueInst* I) {
- Expression e;
-
- e.type = I->getType();
- e.firstVN = lookup_or_add(I->getOperand(0));
- e.secondVN = lookup_or_add(I->getOperand(1));
- e.thirdVN = 0;
- e.function = 0;
- e.opcode = Expression::EXTRACTVALUE;
-
- for (InsertValueInst::op_iterator OI = I->op_begin()+2,
- OE = I->op_end(); OI != OE; ++OI)
- e.varargs.push_back(lookup_or_add(I));
-
- return e;
-}
-
Expression ValueTable::create_expression(CallInst* C) {
Expression e;
} else {
valueNumbering.insert(std::make_pair(V, nextValueNumber));
- return nextValueNumber++;
- }
- } else if (InsertValueInst* II = dyn_cast<InsertValueInst>(V)) {
- Expression e = create_expression(II);
-
- 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 if (ExtractValueInst* E = dyn_cast<ExtractValueInst>(V)) {
- Expression e = create_expression(E);
-
- 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 if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
};
}
+namespace {
+ struct VISIBILITY_HIDDEN ValueNumberScope {
+ ValueNumberScope* parent;
+ DenseMap<uint32_t, Value*> table;
+
+ ValueNumberScope(ValueNumberScope* p) : parent(p) { }
+ };
+}
+
namespace {
class VISIBILITY_HIDDEN GVN : public FunctionPass {
private:
ValueTable VN;
- DenseMap<BasicBlock*, DenseMap<uint32_t, Value*> > localAvail;
+ DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
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<DominatorTree>();
AU.addPreserved<AliasAnalysis>();
AU.addPreserved<MemoryDependenceAnalysis>();
}
Value* CollapsePhi(PHINode* p);
bool isSafeReplacement(PHINode* p, Instruction* inst);
bool performPRE(Function& F);
+ Value* lookupNumber(BasicBlock* BB, uint32_t num);
};
char GVN::ID = 0;
return deletedLoad;
}
+Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) {
+ DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
+ if (I == localAvail.end())
+ return 0;
+
+ ValueNumberScope* locals = I->second;
+
+ while (locals) {
+ DenseMap<uint32_t, Value*>::iterator I = locals->table.find(num);
+ if (I != locals->table.end())
+ return I->second;
+ else
+ locals = locals->parent;
+ }
+
+ return 0;
+}
+
/// processInstruction - When calculating availability, handle an instruction
/// by inserting it into the appropriate sets
bool GVN::processInstruction(Instruction *I,
if (!changed) {
unsigned num = VN.lookup_or_add(L);
- localAvail[I->getParent()].insert(std::make_pair(num, L));
+ localAvail[I->getParent()]->table.insert(std::make_pair(num, L));
}
return changed;
// Allocations are always uniquely numbered, so we can save time and memory
// by fast failing them.
if (isa<AllocationInst>(I)) {
- localAvail[I->getParent()].insert(std::make_pair(num, I));
+ localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
return false;
}
p->replaceAllUsesWith(constVal);
toErase.push_back(p);
} else {
- localAvail[I->getParent()].insert(std::make_pair(num, I));
+ localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
}
// Perform value-number based elimination
- } else if (localAvail[I->getParent()].count(num)) {
- Value* repl = localAvail[I->getParent()][num];
-
+ } else if (Value* repl = lookupNumber(I->getParent(), num)) {
// Remove it!
MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
MD.removeInstruction(I);
toErase.push_back(I);
return true;
} else if (!I->isTerminator()) {
- localAvail[I->getParent()].insert(std::make_pair(num, I));
+ localAvail[I->getParent()]->table.insert(std::make_pair(num, I));
}
return false;
bool changed_function = false;
if (DTN->getIDom())
- localAvail.insert(std::make_pair(BB,
- localAvail[DTN->getIDom()->getBlock()]));
+ localAvail[BB] =
+ new ValueNumberScope(localAvail[DTN->getIDom()->getBlock()]);
+ else
+ localAvail[BB] = new ValueNumberScope(0);
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
BI != BE;) {
/// control flow patterns and attempts to perform simple PRE at the join point.
bool GVN::performPRE(Function& F) {
bool changed = false;
+ SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
BasicBlock* CurrentBlock = *DI;
for (BasicBlock::iterator BI = CurrentBlock->begin(),
BE = CurrentBlock->end(); BI != BE; ) {
- if (isa<AllocaInst>(BI) || isa<TerminatorInst>(BI) ||
- isa<LoadInst>(BI) || isa<StoreInst>(BI) ||
- isa<CallInst>(BI) || isa<PHINode>(BI)) {
+ if (isa<AllocationInst>(BI) || isa<TerminatorInst>(BI) ||
+ isa<PHINode>(BI) || BI->mayReadFromMemory() ||
+ BI->mayWriteToMemory()) {
BI++;
continue;
}
unsigned numWith = 0;
unsigned numWithout = 0;
BasicBlock* PREPred = 0;
+ DenseMap<BasicBlock*, Value*> predMap;
for (pred_iterator PI = pred_begin(CurrentBlock),
PE = pred_end(CurrentBlock); PI != PE; ++PI) {
// We're not interested in PRE where the block is its
- // own predecessor.
- if (*PI == CurrentBlock)
+ // own predecessor, on in blocks with predecessors
+ // that are not reachable.
+ if (*PI == CurrentBlock) {
numWithout = 2;
-
- if (!localAvail[*PI].count(valno)) {
+ break;
+ } else if (!localAvail.count(*PI)) {
+ numWithout = 2;
+ break;
+ }
+
+ DenseMap<uint32_t, Value*>::iterator predV =
+ localAvail[*PI]->table.find(valno);
+ if (predV == localAvail[*PI]->table.end()) {
PREPred = *PI;
numWithout++;
- } else if (localAvail[*PI][valno] == BI) {
+ } else if (predV->second == BI) {
numWithout = 2;
} else {
+ predMap[*PI] = predV->second;
numWith++;
}
}
continue;
}
+ // We can't do PRE safely on a critical edge, so instead we schedule
+ // the edge to be split and perform the PRE the next time we iterate
+ // on the function.
+ unsigned succNum = 0;
+ for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
+ i != e; ++i)
+ if (PREPred->getTerminator()->getSuccessor(i) == PREPred) {
+ succNum = i;
+ break;
+ }
+
+ if (isCriticalEdge(PREPred->getTerminator(), succNum)) {
+ toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum));
+ changed = true;
+ BI++;
+ continue;
+ }
+
// Instantiate the expression the in predecessor that lacked it.
// Because we are going top-down through the block, all value numbers
// will be available in the predecessor by the time we need them. Any
Value* op = BI->getOperand(i);
if (isa<Argument>(op) || isa<Constant>(op) || isa<GlobalValue>(op))
PREInstr->setOperand(i, op);
- else if (!localAvail[PREPred].count(VN.lookup(op))) {
+ else if (!lookupNumber(PREPred, VN.lookup(op))) {
success = false;
break;
} else
- PREInstr->setOperand(i, localAvail[PREPred][VN.lookup(op)]);
+ PREInstr->setOperand(i, lookupNumber(PREPred, VN.lookup(op)));
}
// Fail out if we encounter an operand that is not available in
PREInstr->insertBefore(PREPred->getTerminator());
PREInstr->setName(BI->getName() + ".pre");
+ predMap[PREPred] = PREInstr;
VN.add(PREInstr, valno);
NumGVNPRE++;
// Update the availability map to include the new instruction.
- localAvail[PREPred].insert(std::make_pair(valno, PREInstr));
+ localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr));
// Create a PHI to make the value available in this block.
PHINode* Phi = PHINode::Create(BI->getType(),
CurrentBlock->begin());
for (pred_iterator PI = pred_begin(CurrentBlock),
PE = pred_end(CurrentBlock); PI != PE; ++PI)
- Phi->addIncoming(localAvail[*PI][valno], *PI);
+ Phi->addIncoming(predMap[*PI], *PI);
VN.add(Phi, valno);
-
- // The newly created PHI completely replaces the old instruction,
- // so we need to update the maps to reflect this.
- for (DenseMap<BasicBlock*, DenseMap<uint32_t, Value*> >::iterator
- UI = localAvail.begin(), UE = localAvail.end(); UI != UE; ++UI)
- for (DenseMap<uint32_t, Value*>::iterator UUI = UI->second.begin(),
- UUE = UI->second.end(); UUI != UUE; ++UUI)
- if (UUI->second == BI)
- UUI->second = Phi;
+ localAvail[CurrentBlock]->table[valno] = Phi;
BI->replaceAllUsesWith(Phi);
+ VN.erase(BI);
Instruction* erase = BI;
BI++;
}
}
+ for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
+ I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
+ SplitCriticalEdge(I->first, I->second, this);
+
return changed;
}
bool GVN::iterateOnFunction(Function &F) {
// Clean out global sets from any previous functions
VN.clear();
- localAvail.clear();
phiMap.clear();
+ for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
+ I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
+ delete I->second;
+ localAvail.clear();
+
DominatorTree &DT = getAnalysis<DominatorTree>();
// Top-down walk of the dominator tree
for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
DE = df_end(DT.getRootNode()); DI != DE; ++DI)
changed |= processBlock(*DI);
-
- changed |= performPRE(F);
+
+ if (EnablePRE)
+ changed |= performPRE(F);
+
return changed;
}
projects / oota-llvm.git / blobdiff