From 82575d8ab132d0a2c900952d64f8e54011bcb594 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Fri, 22 Jun 2007 00:20:30 +0000 Subject: [PATCH] Make a bunch of optimizations for compile time to GVNPRE, including smarter set unions, deferring blocks rather than computing maximal sets, and smarter use of sets. With these enhancements, the time to optimize 273.perlbmk goes from 5.3s to 2.7s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37698 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/GVNPRE.cpp | 58 ++++++++++++++++++++++---------- 1 file changed, 41 insertions(+), 17 deletions(-) diff --git a/lib/Transforms/Scalar/GVNPRE.cpp b/lib/Transforms/Scalar/GVNPRE.cpp index 9f7fc4d8e7c..078d8954847 100644 --- a/lib/Transforms/Scalar/GVNPRE.cpp +++ b/lib/Transforms/Scalar/GVNPRE.cpp @@ -25,6 +25,7 @@ #include "llvm/Function.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/PostDominators.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" @@ -106,6 +107,7 @@ namespace { } SmallPtrSet& getMaximalValues() { return maximalValues; } void erase(Value* v); + unsigned size(); }; } @@ -331,6 +333,12 @@ void ValueTable::erase(Value* V) { maximalExpressions.erase(create_expression(C)); } +/// size - Return the number of assigned value numbers +unsigned ValueTable::size() { + // NOTE: zero is never assigned + return nextValueNumber; +} + //===----------------------------------------------------------------------===// // GVNPRE Pass //===----------------------------------------------------------------------===// @@ -365,7 +373,7 @@ namespace { uint32_t v); Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ); void phi_translate_set(SmallPtrSet& anticIn, BasicBlock* pred, - BasicBlock* succ, SmallPtrSet& out); + BasicBlock* succ, SmallPtrSet& out) ; void topo_sort(SmallPtrSet& set, std::vector& vec); @@ -381,10 +389,10 @@ namespace { SmallPtrSet& currPhis, SmallPtrSet& currExps, SmallPtrSet& currTemps); - void buildsets_anticout(BasicBlock* BB, + bool buildsets_anticout(BasicBlock* BB, SmallPtrSet& anticOut, std::set& visited); - bool buildsets_anticin(BasicBlock* BB, + unsigned buildsets_anticin(BasicBlock* BB, SmallPtrSet& anticOut, SmallPtrSet& currExps, SmallPtrSet& currTemps, @@ -395,7 +403,7 @@ namespace { std::map& avail, SmallPtrSet& new_set); unsigned insertion_mergepoint(std::vector& workList, - df_iterator D, + df_iterator& D, SmallPtrSet& new_set); bool insertion(Function& F); @@ -830,13 +838,12 @@ void GVNPRE::buildsets_availout(BasicBlock::iterator I, /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT /// set as a function of the ANTIC_IN set of the block's predecessors -void GVNPRE::buildsets_anticout(BasicBlock* BB, +bool GVNPRE::buildsets_anticout(BasicBlock* BB, SmallPtrSet& anticOut, std::set& visited) { if (BB->getTerminator()->getNumSuccessors() == 1) { - if (visited.find(BB->getTerminator()->getSuccessor(0)) == visited.end()) - phi_translate_set(VN.getMaximalValues(), BB, - BB->getTerminator()->getSuccessor(0), anticOut); + if (visited.count(BB->getTerminator()->getSuccessor(0)) == 0) + return true; else phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)], BB, BB->getTerminator()->getSuccessor(0), anticOut); @@ -860,12 +867,14 @@ void GVNPRE::buildsets_anticout(BasicBlock* BB, anticOut.erase(*I); } } + + return false; } /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for /// each block. ANTIC_IN is then a function of ANTIC_OUT and the GEN /// sets populated in buildsets_availout -bool GVNPRE::buildsets_anticin(BasicBlock* BB, +unsigned GVNPRE::buildsets_anticin(BasicBlock* BB, SmallPtrSet& anticOut, SmallPtrSet& currExps, SmallPtrSet& currTemps, @@ -873,7 +882,9 @@ bool GVNPRE::buildsets_anticin(BasicBlock* BB, SmallPtrSet& anticIn = anticipatedIn[BB]; SmallPtrSet old (anticIn.begin(), anticIn.end()); - buildsets_anticout(BB, anticOut, visited); + bool defer = buildsets_anticout(BB, anticOut, visited); + if (defer) + return 0; SmallPtrSet S; for (SmallPtrSet::iterator I = anticOut.begin(), @@ -887,7 +898,11 @@ bool GVNPRE::buildsets_anticin(BasicBlock* BB, E = currExps.end(); I != E; ++I) if (currTemps.count(*I) == 0) anticIn.insert(*I); - + + BitVector numbers(VN.size()); + for (SmallPtrSet::iterator I = anticIn.begin(), + E = anticIn.end(); I != E; ++I) + numbers.set(VN.lookup(*I)-1); for (SmallPtrSet::iterator I = S.begin(), E = S.end(); I != E; ++I) { // For non-opaque values, we should already have a value numbering. @@ -896,16 +911,17 @@ bool GVNPRE::buildsets_anticin(BasicBlock* BB, // so now. if (!isa(*I) && !isa(*I)) VN.lookup_or_add(*I); - val_insert(anticIn, *I); + if (!numbers.test(VN.lookup(*I)-1)) + anticIn.insert(*I); } clean(anticIn); anticOut.clear(); if (old.size() != anticIn.size()) - return true; + return 2; else - return false; + return 1; } /// buildsets - Phase 1 of the main algorithm. Construct the AVAIL_OUT @@ -974,10 +990,18 @@ unsigned GVNPRE::buildsets(Function& F) { if (BB == 0) continue; - visited.insert(BB); - changed |= buildsets_anticin(BB, anticOut, generatedTemporaries[BB], + + unsigned ret = buildsets_anticin(BB, anticOut, generatedTemporaries[BB], generatedExpressions[BB], visited); + + if (ret == 0) { + changed = true; + break; + } else { + visited.insert(BB); + changed |= (ret == 2); + } } iterations++; @@ -1054,7 +1078,7 @@ void GVNPRE::insertion_pre(Value* e, BasicBlock* BB, /// insertion_mergepoint - When walking the dom tree, check at each merge /// block for the possibility of a partial redundancy. If present, eliminate it unsigned GVNPRE::insertion_mergepoint(std::vector& workList, - df_iterator D, + df_iterator& D, SmallPtrSet& new_set) { bool changed_function = false; bool new_stuff = false; -- 2.34.1