X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FGVN.cpp;h=18a9661684f35c72d7e27c2938979d4c3bc2a80e;hb=c45996bf7464d4b5bc038abeff362f47fea401d9;hp=7ea3ed89c376305142458d246c35512280150932;hpb=2960ed4b85d49fbdb3270605a1bfdbfbdcb97d62;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 7ea3ed89c37..18a9661684f 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -25,21 +25,25 @@ #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" 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 EnablePRE("enable-pre", + cl::init(false), cl::Hidden); //===----------------------------------------------------------------------===// // ValueTable Class @@ -162,6 +166,7 @@ namespace { void setAliasAnalysis(AliasAnalysis* A) { AA = A; } void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } void setDomTree(DominatorTree* D) { DT = D; } + uint32_t getNextUnusedValueNumber() { return nextValueNumber; } }; } @@ -414,6 +419,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) { @@ -675,7 +685,7 @@ 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 unsigned getHashValue(const uint32_t& Val) { return Val * 37; } static bool isPod() { return true; } static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) { return LHS == RHS; @@ -683,8 +693,14 @@ namespace llvm { }; } -typedef ScopedHashTable ValueNumberMap; -typedef ScopedHashTableScope ValueNumberScope; +namespace { + struct VISIBILITY_HIDDEN ValueNumberScope { + ValueNumberScope* parent; + DenseMap table; + + ValueNumberScope(ValueNumberScope* p) : parent(p) { } + }; +} namespace { @@ -696,9 +712,7 @@ namespace { private: ValueTable VN; - - DenseMap availableOut; - ValueNumberMap BaseMap; + DenseMap localAvail; typedef DenseMap > PhiMapType; PhiMapType phiMap; @@ -706,10 +720,11 @@ 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(); } @@ -728,10 +743,12 @@ 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); }; char GVN::ID = 0; @@ -743,13 +760,11 @@ 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"); @@ -794,6 +809,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 (!getAnalysis().isReachableFromEntry(BB)) + return Phis[BB] = UndefValue::get(orig->getType()); + BasicBlock* singlePred = BB->getSinglePredecessor(); if (singlePred) { Value *ret = GetValueForBlock(singlePred, orig, Phis); @@ -1005,20 +1025,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,11 +1081,18 @@ 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); @@ -1045,8 +1101,8 @@ bool GVN::processInstruction(Instruction *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; @@ -1074,12 +1130,17 @@ bool GVN::runOnFunction(Function& F) { 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); @@ -1108,21 +1169,182 @@ 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; } +/// 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; + 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; ) { + if (isa(BI) || isa(BI) || + isa(BI) || BI->mayReadFromMemory() || + BI->mayWriteToMemory()) { + BI++; + continue; + } + + uint32_t valno = VN.lookup(BI); + + // 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; + DenseMap 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, 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 == BI) { + 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) { + BI++; + 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 + // that weren't original present will have been instantiated earlier + // in this loop. + Instruction* PREInstr = BI->clone(); + bool success = true; + for (unsigned i = 0; i < BI->getNumOperands(); ++i) { + Value* op = BI->getOperand(i); + if (isa(op) || isa(op) || isa(op)) + PREInstr->setOperand(i, op); + else { + Value* V = lookupNumber(PREPred, VN.lookup(op)); + if (!V) { + success = false; + break; + } else + PREInstr->setOperand(i, V); + } + } + + // 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; + BI++; + continue; + } + + 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]->table.insert(std::make_pair(valno, PREInstr)); + + // Create a PHI to make the value available in this block. + PHINode* Phi = PHINode::Create(BI->getType(), + BI->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; + + BI->replaceAllUsesWith(Phi); + VN.erase(BI); + + Instruction* erase = BI; + BI++; + erase->eraseFromParent(); + + changed = true; + } + } + + for (SmallVector, 4>::iterator + I = toSplit.begin(), E = toSplit.end(); I != E; ++I) + SplitCriticalEdge(I->first, I->second, this); + + 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(); + for (DenseMap::iterator + I = localAvail.begin(), E = localAvail.end(); I != E; ++I) + delete I->second; + localAvail.clear(); + DominatorTree &DT = getAnalysis(); // Top-down walk of the dominator tree - return processBlock(DT.getRootNode()); + bool changed = false; + for (df_iterator DI = df_begin(DT.getRootNode()), + DE = df_end(DT.getRootNode()); DI != DE; ++DI) + changed |= processBlock(*DI); + + if (EnablePRE) + changed |= performPRE(F); + + return changed; }