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

1 files changed, 22 insertions, 66 deletions

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,86 +75,40 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
   // 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;
+    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 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.
+    // 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;
-    
-    // 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);
+    EqualMatchers.push_back(OptionsToMatch[i++]);
     
-    // 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;
-    }
+    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.
@@ -162,10 +116,12 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
     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()));