From 124084604d9ac0efc10cd9bea2aecf23807e8506 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Fri, 22 Jun 2007 03:14:03 +0000 Subject: [PATCH] Avoid excessive calls to find_leader when calculating AVAIL_OUT. This reduces the time to optimize 403.gcc from 23.5s to 21.9s. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37702 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/GVNPRE.cpp | 106 ++++++++++++++++++++++--------- 1 file changed, 76 insertions(+), 30 deletions(-) diff --git a/lib/Transforms/Scalar/GVNPRE.cpp b/lib/Transforms/Scalar/GVNPRE.cpp index 045ca5c4f82..f58ea47b41b 100644 --- a/lib/Transforms/Scalar/GVNPRE.cpp +++ b/lib/Transforms/Scalar/GVNPRE.cpp @@ -367,45 +367,47 @@ namespace { // Helper fuctions // FIXME: eliminate or document these better - void dump(const SmallPtrSet& s) const; - void clean(SmallPtrSet& set); + void dump(const SmallPtrSet& s) const __attribute__((noinline)); + void clean(SmallPtrSet& set) __attribute__((noinline)); Value* find_leader(SmallPtrSet& vals, - uint32_t v); - Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ); + uint32_t v) __attribute__((noinline)); + Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) __attribute__((noinline)); void phi_translate_set(SmallPtrSet& anticIn, BasicBlock* pred, - BasicBlock* succ, SmallPtrSet& out) ; + BasicBlock* succ, SmallPtrSet& out) __attribute__((noinline)); void topo_sort(SmallPtrSet& set, - std::vector& vec); + std::vector& vec) __attribute__((noinline)); - void cleanup(); - bool elimination(); + void cleanup() __attribute__((noinline)); + bool elimination() __attribute__((noinline)); - void val_insert(SmallPtrSet& s, Value* v); - void val_replace(SmallPtrSet& s, Value* v); - bool dependsOnInvoke(Value* V); + void val_insert(SmallPtrSet& s, Value* v) __attribute__((noinline)); + void val_replace(SmallPtrSet& s, Value* v) __attribute__((noinline)); + bool dependsOnInvoke(Value* V) __attribute__((noinline)); void buildsets_availout(BasicBlock::iterator I, SmallPtrSet& currAvail, SmallPtrSet& currPhis, SmallPtrSet& currExps, - SmallPtrSet& currTemps); + SmallPtrSet& currTemps, + BitVector& availNumbers, + BitVector& expNumbers) __attribute__((noinline)); bool buildsets_anticout(BasicBlock* BB, SmallPtrSet& anticOut, - std::set& visited); + std::set& visited) __attribute__((noinline)); unsigned buildsets_anticin(BasicBlock* BB, SmallPtrSet& anticOut, SmallPtrSet& currExps, SmallPtrSet& currTemps, - std::set& visited); - unsigned buildsets(Function& F); + std::set& visited) __attribute__((noinline)); + unsigned buildsets(Function& F) __attribute__((noinline)); void insertion_pre(Value* e, BasicBlock* BB, std::map& avail, - SmallPtrSet& new_set); + SmallPtrSet& new_set) __attribute__((noinline)); unsigned insertion_mergepoint(std::vector& workList, df_iterator& D, - SmallPtrSet& new_set); - bool insertion(Function& F); + SmallPtrSet& new_set) __attribute__((noinline)); + bool insertion(Function& F) __attribute__((noinline)); }; @@ -795,10 +797,15 @@ void GVNPRE::buildsets_availout(BasicBlock::iterator I, SmallPtrSet& currAvail, SmallPtrSet& currPhis, SmallPtrSet& currExps, - SmallPtrSet& currTemps) { + SmallPtrSet& currTemps, + BitVector& availNumbers, + BitVector& expNumbers) { // Handle PHI nodes... if (PHINode* p = dyn_cast(I)) { VN.lookup_or_add(p); + expNumbers.resize(VN.size()); + availNumbers.resize(VN.size()); + currPhis.insert(p); // Handle binary ops... @@ -806,13 +813,26 @@ void GVNPRE::buildsets_availout(BasicBlock::iterator I, Value* leftValue = BO->getOperand(0); Value* rightValue = BO->getOperand(1); - VN.lookup_or_add(BO); + unsigned num = VN.lookup_or_add(BO); + expNumbers.resize(VN.size()); + availNumbers.resize(VN.size()); if (isa(leftValue)) - val_insert(currExps, leftValue); + if (!expNumbers.test(VN.lookup(leftValue)-1)) { + currExps.insert(leftValue); + expNumbers.set(VN.lookup(leftValue)-1); + } + if (isa(rightValue)) - val_insert(currExps, rightValue); - val_insert(currExps, BO); + if (!expNumbers.test(VN.lookup(rightValue)-1)) { + currExps.insert(rightValue); + expNumbers.set(VN.lookup(rightValue)-1); + } + + if (!expNumbers.test(VN.lookup(BO)-1)) { + currExps.insert(BO); + expNumbers.set(num-1); + } // Handle cmp ops... } else if (CmpInst* C = dyn_cast(I)) { @@ -820,21 +840,41 @@ void GVNPRE::buildsets_availout(BasicBlock::iterator I, Value* rightValue = C->getOperand(1); VN.lookup_or_add(C); - + + unsigned num = VN.lookup_or_add(C); + expNumbers.resize(VN.size()); + availNumbers.resize(VN.size()); + if (isa(leftValue)) - val_insert(currExps, leftValue); + if (!expNumbers.test(VN.lookup(leftValue)-1)) { + currExps.insert(leftValue); + expNumbers.set(VN.lookup(leftValue)-1); + } if (isa(rightValue)) - val_insert(currExps, rightValue); - val_insert(currExps, C); - + if (!expNumbers.test(VN.lookup(rightValue)-1)) { + currExps.insert(rightValue); + expNumbers.set(VN.lookup(rightValue)-1); + } + + if (!expNumbers.test(VN.lookup(C)-1)) { + currExps.insert(C); + expNumbers.set(num-1); + } + // Handle unsupported ops } else if (!I->isTerminator()){ VN.lookup_or_add(I); + expNumbers.resize(VN.size()); + availNumbers.resize(VN.size()); + currTemps.insert(I); } if (!I->isTerminator()) - val_insert(currAvail, I); + if (!availNumbers.test(VN.lookup(I)-1)) { + currAvail.insert(I); + availNumbers.set(VN.lookup(I)-1); + } } /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT @@ -953,10 +993,16 @@ unsigned GVNPRE::buildsets(Function& F) { currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(), availableOut[DI->getIDom()->getBlock()].end()); + BitVector availNumbers(VN.size()); + for (SmallPtrSet::iterator I = currAvail.begin(), + E = currAvail.end(); I != E; ++I) + availNumbers.set(VN.lookup(*I)); + BitVector expNumbers(VN.size()); for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) - buildsets_availout(BI, currAvail, currPhis, currExps, currTemps); + buildsets_availout(BI, currAvail, currPhis, currExps, + currTemps, availNumbers, expNumbers); } -- 2.34.1