diff options
author | Chris Lattner <sabre@nondot.org> | 2010-02-25 07:45:24 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2010-02-25 07:45:24 +0000 |
commit | 04db82d2ba5d9d8e935de82a465b1de5ea7cdf69 (patch) | |
tree | 8b5565b609fdc60ab65dbf3db844ac2d950b83d2 /utils/TableGen/DAGISelMatcherOpt.cpp | |
parent | 85669637139089eaed8def1583ac04266c9654e2 (diff) | |
download | external_llvm-04db82d2ba5d9d8e935de82a465b1de5ea7cdf69.zip external_llvm-04db82d2ba5d9d8e935de82a465b1de5ea7cdf69.tar.gz external_llvm-04db82d2ba5d9d8e935de82a465b1de5ea7cdf69.tar.bz2 |
Implement the first half of redundancy factoring: efficiently
splitting all the patterns under scope nodes into equality sets
based on their first node. The second step is to rewrite the
graph info a form that exposes the sharing. Before I do this,
I want to redesign the Scope node.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97130 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'utils/TableGen/DAGISelMatcherOpt.cpp')
-rw-r--r-- | utils/TableGen/DAGISelMatcherOpt.cpp | 93 |
1 files changed, 89 insertions, 4 deletions
diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp index acde4b8..002637b 100644 --- a/utils/TableGen/DAGISelMatcherOpt.cpp +++ b/utils/TableGen/DAGISelMatcherOpt.cpp @@ -12,6 +12,8 @@ //===----------------------------------------------------------------------===// #include "DAGISelMatcher.h" +#include "llvm/ADT/DenseMap.h" +#include <vector> using namespace llvm; static void ContractNodes(OwningPtr<Matcher> &MatcherPtr) { @@ -63,15 +65,98 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { return FactorNodes(N->getNextPtr()); // Okay, pull together the series of linear push nodes into a vector so we can - // inspect it more easily. + // inspect it more easily. While we're at it, bucket them up by the hash + // code of their first predicate. SmallVector<Matcher*, 32> OptionsToMatch; + typedef DenseMap<unsigned, std::vector<Matcher*> > HashTableTy; + HashTableTy MatchersByHash; Matcher *CurNode = N; for (; ScopeMatcher *PMN = dyn_cast<ScopeMatcher>(CurNode); - CurNode = PMN->getNext()) - OptionsToMatch.push_back(PMN->getCheck()); - OptionsToMatch.push_back(CurNode); + CurNode = PMN->getNext()) { + // Factor the subexpression. + FactorNodes(PMN->getCheckPtr()); + if (Matcher *Check = PMN->getCheck()) { + OptionsToMatch.push_back(Check); + MatchersByHash[Check->getHash()].push_back(Check); + } + } + + if (CurNode) { + OptionsToMatch.push_back(CurNode); + MatchersByHash[CurNode->getHash()].push_back(CurNode); + } + + SmallVector<Matcher*, 32> NewOptionsToMatch; + + // Now that we have bucketed up things by hash code, iterate over sets of + // matchers that all start with the same node. We would like to iterate over + // the hash table, but it isn't in deterministic order, emulate this by going + // about this slightly backwards. After each set of nodes is processed, we + // remove them from MatchersByHash. + for (unsigned i = 0, e = OptionsToMatch.size(); + i != e && !MatchersByHash.empty(); ++i) { + // Find the set of matchers that start with this node. + Matcher *Optn = OptionsToMatch[i]; + + // Find all nodes that hash to the same value. If there is no entry in the + // hash table, then we must have previously processed a node equal to this + // one. + HashTableTy::iterator DMI = MatchersByHash.find(Optn->getHash()); + if (DMI == MatchersByHash.end()) continue; + + std::vector<Matcher*> &HashMembers = DMI->second; + assert(!HashMembers.empty() && "Should be removed if empty"); + + // Check to see if this node is in HashMembers, if not it was equal to a + // previous node and removed. + std::vector<Matcher*>::iterator MemberSlot = + std::find(HashMembers.begin(), HashMembers.end(), Optn); + if (MemberSlot == HashMembers.end()) continue; + + // If the node *does* exist in HashMembers, then we've confirmed that it + // hasn't been processed as equal to a previous node. Process it now, start + // by removing it from the list of hash-equal nodes. + HashMembers.erase(MemberSlot); + + // Scan all of the hash members looking for ones that are equal, removing + // them from HashMembers, adding them to EqualMatchers. + SmallVector<Matcher*, 8> EqualMatchers; + + // Scan the vector backwards so we're generally removing from the end to + // avoid pointless data copying. + for (unsigned i = HashMembers.size(); i != 0; --i) { + if (!HashMembers[i-1]->isEqual(Optn)) continue; + + EqualMatchers.push_back(HashMembers[i-1]); + HashMembers.erase(HashMembers.begin()+i-1); + } + EqualMatchers.push_back(Optn); + + // Reverse the vector so that we preserve the match ordering. + std::reverse(EqualMatchers.begin(), EqualMatchers.end()); + + // If HashMembers is empty at this point, then we've gotten all nodes with + // the same hash, nuke the entry in the hash table. + if (HashMembers.empty()) + MatchersByHash.erase(Optn->getHash()); + + // Okay, we have the list of all matchers that start with the same node as + // Optn. If there is more than one in the set, we want to factor them. + if (EqualMatchers.size() == 1) { + NewOptionsToMatch.push_back(Optn); + continue; + } + + // Factor these checks by pulling the first node off each entry and + // discarding it, replacing it with... + // something amazing?? + + // FIXME: Need to change the Scope model. + } + + // Reassemble a new Scope node. } |