switch from my nice hashtable based merging solution to a
gross little neighbor merging implementation. This one has
the benefit of not violating the ordering of patterns, so it
generates code that passes tests again.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97218 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp
index d4796e9..5aaa51f 100644
--- a/utils/TableGen/DAGISelMatcherOpt.cpp
+++ b/utils/TableGen/DAGISelMatcherOpt.cpp
@@ -75,97 +75,53 @@
// 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;
for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
// Factor the subexpression.
OwningPtr<Matcher> Child(Scope->takeChild(i));
FactorNodes(Child);
- if (Matcher *N = Child.take()) {
+ if (Matcher *N = Child.take())
OptionsToMatch.push_back(N);
- MatchersByHash[N->getHash()].push_back(N);
- }
}
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) {
+ // Loop over options to match, merging neighboring patterns with identical
+ // starting nodes into a shared matcher.
+ for (unsigned i = 0, e = OptionsToMatch.size(); i != e;) {
// 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()) {
- delete Optn;
- 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()) {
- delete Optn;
- 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) {
+ Matcher *Optn = OptionsToMatch[i++];
+
+ // See if the next option starts with the same matcher, if not, no sharing.
+ if (i == e || !OptionsToMatch[i]->isEqual(Optn)) {
+ // TODO: Skip over mutually exclusive patterns.
NewOptionsToMatch.push_back(Optn);
continue;
}
+ // If the two neighbors *do* start with the same matcher, we can factor the
+ // matcher out of at least these two patterns. See what the maximal set we
+ // can merge together is.
+ SmallVector<Matcher*, 8> EqualMatchers;
+ EqualMatchers.push_back(Optn);
+ EqualMatchers.push_back(OptionsToMatch[i++]);
+
+ while (i != e && OptionsToMatch[i]->isEqual(Optn))
+ EqualMatchers.push_back(OptionsToMatch[i++]);
+
// Factor these checks by pulling the first node off each entry and
// discarding it. Take the first one off the first entry to reuse.
Matcher *Shared = Optn;
Optn = Optn->takeNext();
EqualMatchers[0] = Optn;
- // Skip the first node. Leave the first node around though, we'll delete it
- // on subsequent iterations over OptionsToMatch.
- for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i)
- EqualMatchers[i] = EqualMatchers[i]->takeNext();
+ // Remove and delete the first node from the other matchers we're factoring.
+ for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {
+ Matcher *Tmp = EqualMatchers[i]->takeNext();
+ delete EqualMatchers[i];
+ EqualMatchers[i] = Tmp;
+ }
Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));