X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=039d52029aac9d88da399ae802cbf48d6d2a00fd;hb=912c49d169479ea713dfdee6fd7a2909c1147dab;hp=563f6e61b34c993d1b9a0eb6336efc14fa77179a;hpb=af4240ac2d5582f3c1c86c46c8c413823e1fc0db;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 563f6e61b34..039d52029aa 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -25,21 +25,27 @@ #include "llvm/Value.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/ScopedHashTable.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/SparseBitVector.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/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include using namespace llvm; STATISTIC(NumGVNInstr, "Number of instructions deleted"); STATISTIC(NumGVNLoad, "Number of loads deleted"); +STATISTIC(NumGVNPRE, "Number of instructions PRE'd"); +STATISTIC(NumGVNBlocks, "Number of blocks merged"); + +static cl::opt EnablePRE("enable-pre", + cl::init(true), cl::Hidden); //===----------------------------------------------------------------------===// // ValueTable Class @@ -160,8 +166,10 @@ namespace { void erase(Value* v); unsigned size(); void setAliasAnalysis(AliasAnalysis* A) { AA = A; } + AliasAnalysis *getAliasAnalysis() const { return AA; } void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } void setDomTree(DominatorTree* D) { DT = D; } + uint32_t getNextUnusedValueNumber() { return nextValueNumber; } }; } @@ -414,6 +422,11 @@ Expression ValueTable::create_expression(GetElementPtrInst* G) { // ValueTable External Functions //===----------------------------------------------------------------------===// +/// add - Insert a value into the table with a specified value number. +void ValueTable::add(Value* V, uint32_t num) { + valueNumbering.insert(std::make_pair(V, num)); +} + /// lookup_or_add - Returns the value number for the specified value, assigning /// it a new number if it did not have one before. uint32_t ValueTable::lookup_or_add(Value* V) { @@ -444,66 +457,75 @@ uint32_t ValueTable::lookup_or_add(Value* V) { return nextValueNumber++; } - Instruction* local_dep = MD->getDependency(C); + MemDepResult local_dep = MD->getDependency(C); - if (local_dep == MemoryDependenceAnalysis::None) { + if (local_dep.isNone()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; - } else if (local_dep != MemoryDependenceAnalysis::NonLocal) { - if (!isa(local_dep)) { + } + + if (Instruction *LocalDepInst = local_dep.getInst()) { + if (!isa(LocalDepInst)) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; } - CallInst* local_cdep = cast(local_dep); + CallInst* local_cdep = cast(LocalDepInst); if (local_cdep->getCalledFunction() != C->getCalledFunction() || local_cdep->getNumOperands() != C->getNumOperands()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; - } else if (!C->getCalledFunction()) { + } + + if (!C->getCalledFunction()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; - } else { - for (unsigned i = 1; i < C->getNumOperands(); ++i) { - uint32_t c_vn = lookup_or_add(C->getOperand(i)); - uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); - if (c_vn != cd_vn) { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } - } + } - uint32_t v = lookup_or_add(local_cdep); - valueNumbering.insert(std::make_pair(V, v)); - return v; + for (unsigned i = 1; i < C->getNumOperands(); ++i) { + uint32_t c_vn = lookup_or_add(C->getOperand(i)); + uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i)); + if (c_vn != cd_vn) { + valueNumbering.insert(std::make_pair(V, nextValueNumber)); + return nextValueNumber++; + } } - } + uint32_t v = lookup_or_add(local_cdep); + valueNumbering.insert(std::make_pair(V, v)); + return v; + } - DenseMap deps; - MD->getNonLocalDependency(C, deps); + + const MemoryDependenceAnalysis::NonLocalDepInfo &deps = + MD->getNonLocalDependency(C); CallInst* cdep = 0; - for (DenseMap::iterator I = deps.begin(), - E = deps.end(); I != E; ++I) { - if (I->second == MemoryDependenceAnalysis::None) { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); + // Check to see if we have a single dominating call instruction that is + // identical to C. + for (unsigned i = 0, e = deps.size(); i != e; ++i) { + const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i]; + // Ignore non-local dependencies. + if (I->second.isNonLocal()) + continue; - return nextValueNumber++; - } else if (I->second != MemoryDependenceAnalysis::NonLocal) { - if (DT->dominates(I->first, C->getParent())) { - if (CallInst* CD = dyn_cast(I->second)) - cdep = CD; - else { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } - } else { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } + // We don't handle non-depedencies. If we already have a call, reject + // instruction dependencies. + if (I->second.isNone() || cdep != 0) { + cdep = 0; + break; + } + + CallInst *NonLocalDepCall = dyn_cast(I->second.getInst()); + // FIXME: All duplicated with non-local case. + if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){ + cdep = NonLocalDepCall; + continue; } + + cdep = 0; + break; } if (!cdep) { @@ -515,24 +537,24 @@ uint32_t ValueTable::lookup_or_add(Value* V) { cdep->getNumOperands() != C->getNumOperands()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; - } else if (!C->getCalledFunction()) { + } + if (!C->getCalledFunction()) { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; - } else { - for (unsigned i = 1; i < C->getNumOperands(); ++i) { - uint32_t c_vn = lookup_or_add(C->getOperand(i)); - uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); - if (c_vn != cd_vn) { - valueNumbering.insert(std::make_pair(V, nextValueNumber)); - return nextValueNumber++; - } + } + for (unsigned i = 1; i < C->getNumOperands(); ++i) { + uint32_t c_vn = lookup_or_add(C->getOperand(i)); + uint32_t cd_vn = lookup_or_add(cdep->getOperand(i)); + if (c_vn != cd_vn) { + valueNumbering.insert(std::make_pair(V, nextValueNumber)); + return nextValueNumber++; } - - uint32_t v = lookup_or_add(cdep); - valueNumbering.insert(std::make_pair(V, v)); - return v; } + uint32_t v = lookup_or_add(cdep); + valueNumbering.insert(std::make_pair(V, v)); + return v; + } else { valueNumbering.insert(std::make_pair(V, nextValueNumber)); return nextValueNumber++; @@ -671,34 +693,29 @@ void ValueTable::erase(Value* V) { // GVN Pass //===----------------------------------------------------------------------===// -namespace llvm { - template<> struct DenseMapInfo { - static inline uint32_t getEmptyKey() { return ~0; } - static inline uint32_t getTombstoneKey() { return ~0 - 1; } - static unsigned getHashValue(const uint32_t& Val) { return Val; } - static bool isPod() { return true; } - static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) { - return LHS == RHS; - } +namespace { + struct VISIBILITY_HIDDEN ValueNumberScope { + ValueNumberScope* parent; + DenseMap table; + + ValueNumberScope(ValueNumberScope* p) : parent(p) { } }; } -typedef ScopedHashTable ValueNumberMap; -typedef ScopedHashTableScope ValueNumberScope; - namespace { class VISIBILITY_HIDDEN GVN : public FunctionPass { bool runOnFunction(Function &F); public: static char ID; // Pass identification, replacement for typeid - GVN() : FunctionPass((intptr_t)&ID) { } + GVN() : FunctionPass(&ID) { } private: + MemoryDependenceAnalysis *MD; + DominatorTree *DT; + ValueTable VN; - - DenseMap availableOut; - ValueNumberMap BaseMap; + DenseMap localAvail; typedef DenseMap > PhiMapType; PhiMapType phiMap; @@ -706,12 +723,12 @@ namespace { // This transformation requires dominator postdominator info virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); AU.addRequired(); AU.addRequired(); AU.addRequired(); + + AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); } // Helper fuctions @@ -728,10 +745,14 @@ namespace { Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig, DenseMap &Phis, bool top_level = false); - void dump(DenseMap& d); + void dump(DenseMap& d); bool iterateOnFunction(Function &F); Value* CollapsePhi(PHINode* p); bool isSafeReplacement(PHINode* p, Instruction* inst); + bool performPRE(Function& F); + Value* lookupNumber(BasicBlock* BB, uint32_t num); + bool mergeBlockIntoPredecessor(BasicBlock* BB); + void cleanupGlobalSets(); }; char GVN::ID = 0; @@ -743,29 +764,25 @@ FunctionPass *llvm::createGVNPass() { return new GVN(); } static RegisterPass X("gvn", "Global Value Numbering"); -void GVN::dump(DenseMap& d) { +void GVN::dump(DenseMap& d) { printf("{\n"); - for (DenseMap::iterator I = d.begin(), + for (DenseMap::iterator I = d.begin(), E = d.end(); I != E; ++I) { - if (I->second == MemoryDependenceAnalysis::None) - printf("None\n"); - else + printf("%d\n", I->first); I->second->dump(); } printf("}\n"); } Value* GVN::CollapsePhi(PHINode* p) { - DominatorTree &DT = getAnalysis(); Value* constVal = p->hasConstantValue(); - if (!constVal) return 0; Instruction* inst = dyn_cast(constVal); if (!inst) return constVal; - if (DT.dominates(inst, p)) + if (DT->dominates(inst, p)) if (isSafeReplacement(p, inst)) return inst; return 0; @@ -794,6 +811,11 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, DenseMap::iterator V = Phis.find(BB); if (V != Phis.end() && !top_level) return V->second; + // If the block is unreachable, just return undef, since this path + // can't actually occur at runtime. + if (!DT->isReachableFromEntry(BB)) + return Phis[BB] = UndefValue::get(orig->getType()); + BasicBlock* singlePred = BB->getSinglePredecessor(); if (singlePred) { Value *ret = GetValueForBlock(singlePred, orig, Phis); @@ -816,8 +838,7 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, PN->addIncoming(val, *PI); } - AliasAnalysis& AA = getAnalysis(); - AA.copyValue(orig, PN); + VN.getAliasAnalysis()->copyValue(orig, PN); // Attempt to collapse PHI nodes that are trivially redundant Value* v = CollapsePhi(PN); @@ -827,9 +848,6 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, return PN; } - MemoryDependenceAnalysis& MD = getAnalysis(); - - MD.removeInstruction(PN); PN->replaceAllUsesWith(v); for (DenseMap::iterator I = Phis.begin(), @@ -837,6 +855,8 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, if (I->second == PN) I->second = v; + DEBUG(cerr << "GVN removed: " << *PN); + MD->removeInstruction(PN); PN->eraseFromParent(); Phis[BB] = v; @@ -847,31 +867,78 @@ Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig, /// non-local by performing PHI construction. bool GVN::processNonLocalLoad(LoadInst* L, SmallVectorImpl &toErase) { - MemoryDependenceAnalysis& MD = getAnalysis(); - // Find the non-local dependencies of the load - DenseMap deps; - MD.getNonLocalDependency(L, deps); + const MemoryDependenceAnalysis::NonLocalDepInfo &deps = + MD->getNonLocalDependency(L); + DEBUG(cerr << "INVESTIGATING NONLOCAL LOAD: " << deps.size() << *L); +#if 0 + DEBUG(for (unsigned i = 0, e = deps.size(); i != e; ++i) { + cerr << " " << deps[i].first->getName(); + if (Instruction *I = deps[i].second.getInst()) + cerr << *I; + else + cerr << "\n"; + }); +#endif + + // If we had to process more than one hundred blocks to find the + // dependencies, this load isn't worth worrying about. Optimizing + // it will be too expensive. + if (deps.size() > 100) + return false; + + BasicBlock *EntryBlock = &L->getParent()->getParent()->getEntryBlock(); DenseMap repl; // Filter out useless results (non-locals, etc) - for (DenseMap::iterator I = deps.begin(), E = deps.end(); - I != E; ++I) { - if (I->second == MemoryDependenceAnalysis::None) - return false; - - if (I->second == MemoryDependenceAnalysis::NonLocal) + for (unsigned i = 0, e = deps.size(); i != e; ++i) { + BasicBlock *DepBB = deps[i].first; + MemDepResult DepInfo = deps[i].second; + + if (DepInfo.isNonLocal()) { + // If this is a non-local dependency in the entry block, then we depend on + // the value live-in at the start of the function. We could insert a load + // in the entry block to get this, but for now we'll just bail out. + // + // FIXME: Consider emitting a load in the entry block to catch this case! + // Tricky part is to sink so that it doesn't execute in places where it + // isn't needed. + if (DepBB == EntryBlock) + return false; + continue; + } + + if (DepInfo.isNone()) { + repl[DepBB] = UndefValue::get(L->getType()); continue; + } - if (StoreInst* S = dyn_cast(I->second)) { - if (S->getPointerOperand() != L->getPointerOperand()) + if (StoreInst* S = dyn_cast(DepInfo.getInst())) { + // Reject loads and stores that are to the same address but are of + // different types. + // NOTE: 403.gcc does have this case (e.g. in readonly_fields_p) because + // of bitfield access, it would be interesting to optimize for it at some + // point. + if (S->getOperand(0)->getType() != L->getType()) return false; - repl[I->first] = S->getOperand(0); - } else if (LoadInst* LD = dyn_cast(I->second)) { - if (LD->getPointerOperand() != L->getPointerOperand()) + + if (S->getPointerOperand() != L->getPointerOperand() && + VN.getAliasAnalysis()->alias(S->getPointerOperand(), 1, + L->getPointerOperand(), 1) + != AliasAnalysis::MustAlias) return false; - repl[I->first] = LD; + repl[DepBB] = S->getOperand(0); + } else if (LoadInst* LD = dyn_cast(DepInfo.getInst())) { + if (LD->getType() != L->getType()) + return false; + + if (LD->getPointerOperand() != L->getPointerOperand() && + VN.getAliasAnalysis()->alias(LD->getPointerOperand(), 1, + L->getPointerOperand(), 1) + != AliasAnalysis::MustAlias) + return false; + repl[DepBB] = LD; } else { return false; } @@ -882,7 +949,6 @@ bool GVN::processNonLocalLoad(LoadInst* L, for (SmallPtrSet::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++; @@ -891,16 +957,15 @@ bool GVN::processNonLocalLoad(LoadInst* L, repl.insert(std::make_pair((*I)->getParent(), *I)); } - + + DEBUG(cerr << "GVN REMOVING NONLOCAL LOAD: " << *L); + // Perform PHI construction SmallPtrSet visited; Value* v = GetValueForBlock(L->getParent(), L, repl, true); - - MD.removeInstruction(L); L->replaceAllUsesWith(v); toErase.push_back(L); NumGVNLoad++; - return true; } @@ -917,10 +982,9 @@ bool GVN::processLoad(LoadInst *L, DenseMap &lastLoad, LoadInst*& last = lastLoad[pointer]; // ... to a pointer that has been loaded from before... - MemoryDependenceAnalysis& MD = getAnalysis(); bool removedNonLocal = false; - Instruction* dep = MD.getDependency(L); - if (dep == MemoryDependenceAnalysis::NonLocal && + MemDepResult dep = MD->getDependency(L); + if (dep.isNonLocal() && L->getParent() != &L->getParent()->getParent()->getEntryBlock()) { removedNonLocal = processNonLocalLoad(L, toErase); @@ -935,15 +999,11 @@ bool GVN::processLoad(LoadInst *L, DenseMap &lastLoad, // 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(dep) || isa(dep))) { + while (Instruction *DepInst = dep.getInst()) { // ... that depends on a store ... - if (StoreInst* S = dyn_cast(dep)) { + if (StoreInst* S = dyn_cast(DepInst)) { if (S->getPointerOperand() == pointer) { // Remove it! - MD.removeInstruction(L); - L->replaceAllUsesWith(S->getOperand(0)); toErase.push_back(L); deletedLoad = true; @@ -953,50 +1013,36 @@ bool GVN::processLoad(LoadInst *L, DenseMap &lastLoad, // Whether we removed it or not, we can't // go any further break; + } else if (!isa(DepInst)) { + // Only want to handle loads below. + break; } else if (!last) { // If we don't depend on a store, and we haven't // been loaded before, bail. break; - } else if (dep == last) { + } else if (DepInst == last) { // Remove it! - MD.removeInstruction(L); - L->replaceAllUsesWith(last); toErase.push_back(L); deletedLoad = true; NumGVNLoad++; - break; } else { - dep = MD.getDependency(L, dep); + dep = MD->getDependencyFrom(L, DepInst, DepInst->getParent()); } } - if (dep != MemoryDependenceAnalysis::None && - dep != MemoryDependenceAnalysis::NonLocal && - isa(dep)) { - // Check that this load is actually from the - // allocation we found - Value* v = L->getOperand(0); - while (true) { - if (BitCastInst *BC = dyn_cast(v)) - v = BC->getOperand(0); - else if (GetElementPtrInst *GEP = dyn_cast(v)) - v = GEP->getOperand(0); - else - break; - } - if (v == dep) { - // If this load depends directly on an allocation, there isn't - // anything stored there; therefore, we can optimize this load - // to undef. - MD.removeInstruction(L); - - L->replaceAllUsesWith(UndefValue::get(L->getType())); - toErase.push_back(L); - deletedLoad = true; - NumGVNLoad++; - } + // If this load really doesn't depend on anything, then we must be loading an + // undef value. This can happen when loading for a fresh allocation with no + // intervening stores, for example. + if (dep.isNone()) { + // If this load depends directly on an allocation, there isn't + // anything stored there; therefore, we can optimize this load + // to undef. + L->replaceAllUsesWith(UndefValue::get(L->getType())); + toErase.push_back(L); + deletedLoad = true; + NumGVNLoad++; } if (!deletedLoad) @@ -1005,20 +1051,49 @@ bool GVN::processLoad(LoadInst *L, DenseMap &lastLoad, return deletedLoad; } +Value* GVN::lookupNumber(BasicBlock* BB, uint32_t num) { + DenseMap::iterator I = localAvail.find(BB); + if (I == localAvail.end()) + return 0; + + ValueNumberScope* locals = I->second; + + while (locals) { + DenseMap::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, DenseMap &lastSeenLoad, SmallVectorImpl &toErase) { - if (LoadInst* L = dyn_cast(I)) - return processLoad(L, lastSeenLoad, toErase); + if (LoadInst* L = dyn_cast(I)) { + bool changed = processLoad(L, lastSeenLoad, toErase); + + if (!changed) { + unsigned num = VN.lookup_or_add(L); + localAvail[I->getParent()]->table.insert(std::make_pair(num, L)); + } + + return changed; + } + + uint32_t nextNum = VN.getNextUnusedValueNumber(); + unsigned num = VN.lookup_or_add(I); // Allocations are always uniquely numbered, so we can save time and memory // by fast failing them. - if (isa(I)) + if (isa(I) || isa(I)) { + localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); return false; - - unsigned num = VN.lookup_or_add(I); + } // Collapse PHI nodes if (PHINode* p = dyn_cast(I)) { @@ -1032,21 +1107,25 @@ bool GVN::processInstruction(Instruction *I, p->replaceAllUsesWith(constVal); toErase.push_back(p); + } else { + localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); } - // Perform value-number based elimination - } else if (BaseMap.begin(num) != BaseMap.end()) { - Value* repl = *BaseMap.begin(num); + + // If the number we were assigned was a brand new VN, then we don't + // need to do a lookup to see if the number already exists + // somewhere in the domtree: it can't! + } else if (num == nextNum) { + localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); + // Perform value-number based elimination + } else if (Value* repl = lookupNumber(I->getParent(), num)) { // Remove it! - MemoryDependenceAnalysis& MD = getAnalysis(); - MD.removeInstruction(I); - VN.erase(I); I->replaceAllUsesWith(repl); toErase.push_back(I); return true; - } else if (!I->isTerminator()) { - BaseMap.insert(num, I); + } else { + localAvail[I->getParent()]->table.insert(std::make_pair(num, I)); } return false; @@ -1056,30 +1135,57 @@ bool GVN::processInstruction(Instruction *I, // function. // bool GVN::runOnFunction(Function& F) { + MD = &getAnalysis(); + DT = &getAnalysis(); VN.setAliasAnalysis(&getAnalysis()); - VN.setMemDep(&getAnalysis()); - VN.setDomTree(&getAnalysis()); + VN.setMemDep(MD); + VN.setDomTree(DT); bool changed = false; bool shouldContinue = true; + // Merge unconditional branches, allowing PRE to catch more + // optimization opportunities. + for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { + BasicBlock* BB = FI; + ++FI; + bool removedBlock = MergeBlockIntoPredecessor(BB, this); + if (removedBlock) NumGVNBlocks++; + + changed |= removedBlock; + } + while (shouldContinue) { shouldContinue = iterateOnFunction(F); changed |= shouldContinue; } + if (EnablePRE) { + bool PREChanged = true; + while (PREChanged) { + PREChanged = performPRE(F); + changed |= PREChanged; + } + } + + cleanupGlobalSets(); + return changed; } bool GVN::processBlock(DomTreeNode* DTN) { BasicBlock* BB = DTN->getBlock(); - ValueNumberScope NewScope(BaseMap); - SmallVector toErase; DenseMap lastSeenLoad; bool changed_function = false; - + + if (DTN->getIDom()) + 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;) { changed_function |= processInstruction(BI, lastSeenLoad, toErase); @@ -1097,8 +1203,11 @@ bool GVN::processBlock(DomTreeNode* DTN) { --BI; for (SmallVector::iterator I = toErase.begin(), - E = toErase.end(); I != E; ++I) + E = toErase.end(); I != E; ++I) { + DEBUG(cerr << "GVN removed: " << **I); + MD->removeInstruction(*I); (*I)->eraseFromParent(); + } if (AtStart) BI = BB->begin(); @@ -1108,21 +1217,180 @@ bool GVN::processBlock(DomTreeNode* DTN) { toErase.clear(); } - for (DomTreeNode::iterator I = DTN->begin(), E = DTN->end(); I != E; ++I) - changed_function |= processBlock(*I); - return changed_function; } -// GVN::iterateOnFunction - Executes one iteration of GVN +/// performPRE - Perform a purely local form of PRE that looks for diamond +/// control flow patterns and attempts to perform simple PRE at the join point. +bool GVN::performPRE(Function& F) { + bool Changed = false; + SmallVector, 4> toSplit; + DenseMap predMap; + for (df_iterator DI = df_begin(&F.getEntryBlock()), + DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) { + BasicBlock* CurrentBlock = *DI; + + // Nothing to PRE in the entry block. + if (CurrentBlock == &F.getEntryBlock()) continue; + + for (BasicBlock::iterator BI = CurrentBlock->begin(), + BE = CurrentBlock->end(); BI != BE; ) { + Instruction *CurInst = BI++; + + if (isa(CurInst) || isa(CurInst) || + isa(CurInst) || CurInst->mayReadFromMemory() || + CurInst->mayWriteToMemory()) + continue; + + uint32_t valno = VN.lookup(CurInst); + + // Look for the predecessors for PRE opportunities. We're + // only trying to solve the basic diamond case, where + // a value is computed in the successor and one predecessor, + // but not the other. We also explicitly disallow cases + // where the successor is its own predecessor, because they're + // more complicated to get right. + unsigned numWith = 0; + unsigned numWithout = 0; + BasicBlock* PREPred = 0; + predMap.clear(); + + 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, on in blocks with predecessors + // that are not reachable. + if (*PI == CurrentBlock) { + numWithout = 2; + break; + } else if (!localAvail.count(*PI)) { + numWithout = 2; + break; + } + + DenseMap::iterator predV = + localAvail[*PI]->table.find(valno); + if (predV == localAvail[*PI]->table.end()) { + PREPred = *PI; + numWithout++; + } else if (predV->second == CurInst) { + numWithout = 2; + } else { + predMap[*PI] = predV->second; + numWith++; + } + } + + // Don't do PRE when it might increase code size, i.e. when + // we would need to insert instructions in more than one pred. + if (numWithout != 1 || numWith == 0) + 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) == CurrentBlock) { + succNum = i; + break; + } + + if (isCriticalEdge(PREPred->getTerminator(), succNum)) { + toSplit.push_back(std::make_pair(PREPred->getTerminator(), succNum)); + Changed = true; + 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 + // that weren't original present will have been instantiated earlier + // in this loop. + Instruction* PREInstr = CurInst->clone(); + bool success = true; + for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) { + Value *Op = PREInstr->getOperand(i); + if (isa(Op) || isa(Op) || isa(Op)) + continue; + + if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) { + PREInstr->setOperand(i, V); + } else { + success = false; + break; + } + } + + // Fail out if we encounter an operand that is not available in + // the PRE predecessor. This is typically because of loads which + // are not value numbered precisely. + if (!success) { + delete PREInstr; + continue; + } + + PREInstr->insertBefore(PREPred->getTerminator()); + PREInstr->setName(CurInst->getName() + ".pre"); + predMap[PREPred] = PREInstr; + VN.add(PREInstr, valno); + NumGVNPRE++; + + // Update the availability map to include the new instruction. + localAvail[PREPred]->table.insert(std::make_pair(valno, PREInstr)); + + // Create a PHI to make the value available in this block. + PHINode* Phi = PHINode::Create(CurInst->getType(), + CurInst->getName() + ".pre-phi", + CurrentBlock->begin()); + for (pred_iterator PI = pred_begin(CurrentBlock), + PE = pred_end(CurrentBlock); PI != PE; ++PI) + Phi->addIncoming(predMap[*PI], *PI); + + VN.add(Phi, valno); + localAvail[CurrentBlock]->table[valno] = Phi; + + CurInst->replaceAllUsesWith(Phi); + VN.erase(CurInst); + + DEBUG(cerr << "GVN PRE removed: " << *CurInst); + MD->removeInstruction(CurInst); + CurInst->eraseFromParent(); + Changed = true; + } + } + + for (SmallVector, 4>::iterator + I = toSplit.begin(), E = toSplit.end(); I != E; ++I) { + SplitCriticalEdge(I->first, I->second, this); + BasicBlock* NewBlock = I->first->getSuccessor(I->second); + localAvail[NewBlock] = + new ValueNumberScope(localAvail[I->first->getParent()]); + } + + return Changed; +} + +// iterateOnFunction - Executes one iteration of GVN bool GVN::iterateOnFunction(Function &F) { - // Clean out global sets from any previous functions + cleanupGlobalSets(); + + // Top-down walk of the dominator tree + bool changed = false; + for (df_iterator DI = df_begin(DT->getRootNode()), + DE = df_end(DT->getRootNode()); DI != DE; ++DI) + changed |= processBlock(*DI); + + return changed; +} + +void GVN::cleanupGlobalSets() { VN.clear(); - availableOut.clear(); phiMap.clear(); - - DominatorTree &DT = getAnalysis(); - // Top-down walk of the dominator tree - return processBlock(DT.getRootNode()); + for (DenseMap::iterator + I = localAvail.begin(), E = localAvail.end(); I != E; ++I) + delete I->second; + localAvail.clear(); }