Teach the grouper some simple tricks about looking contradictory

predicates.  For example if we have:

Scope:
  CheckType i32
    ABC
  CheckType f32
    DEF
  CheckType i32
    GHI

Then we know that we can transform this into:
Scope:
  CheckType i32
    Scope
      ABC
      GHI
  CheckType f32
    DEF

This reorders the check for the 'GHI' predicate above
the check for the 'DEF' predidate.  However it is safe to do this
in this situation because we know that a node cannot have both an
i32 and f32 type.

We're now doing more factoring that the old isel did.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97312 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 55 insertions, 12 deletions

diff --git a/utils/TableGen/DAGISelMatcherOpt.cpp b/utils/TableGen/DAGISelMatcherOpt.cpp
index 55c2538933..045d5011e7 100644
--- a/utils/TableGen/DAGISelMatcherOpt.cpp
+++ b/utils/TableGen/DAGISelMatcherOpt.cpp
@@ -11,8 +11,11 @@
 //
 //===----------------------------------------------------------------------===//
 
+#define DEBUG_TYPE "isel-opt"
 #include "DAGISelMatcher.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
 #include <vector>
 using namespace llvm;
 
@@ -156,26 +159,66 @@ static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
 
   // 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;) {
+  for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) {
     // Find the set of matchers that start with this node.
-    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.
+    Matcher *Optn = OptionsToMatch[OptionIdx++];
+
+    if (OptionIdx == e) {
       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.
+    // See if the next option starts with the same matcher.  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 all of the known-equal matchers after this one into the same
+    // group.
+    while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn))
+      EqualMatchers.push_back(OptionsToMatch[OptionIdx++]);
+
+    // If we found a non-equal matcher, see if it is contradictory with the
+    // current node.  If so, we know that the ordering relation between the
+    // current sets of nodes and this node don't matter.  Look past it to see if
+    // we can merge anything else into this matching group.
+    unsigned Scan = OptionIdx;
+    while (1) {
+      while (Scan != e && Optn->isContradictory(OptionsToMatch[Scan]))
+        ++Scan;
+      
+      // Ok, we found something that isn't known to be contradictory.  If it is
+      // equal, we can merge it into the set of nodes to factor, if not, we have
+      // to cease factoring.
+      if (Scan == e || !Optn->isEqual(OptionsToMatch[Scan])) break;
+
+      // If is equal after all, add the option to EqualMatchers and remove it
+      // from OptionsToMatch.
+      EqualMatchers.push_back(OptionsToMatch[Scan]);
+      OptionsToMatch.erase(OptionsToMatch.begin()+Scan);
+      --e;
+    }
+      
+    if (Scan != e) {
+      DEBUG(errs() << "Couldn't merge this:\n  ";
+            Optn->printOne(errs());
+            errs() << "into this:\n  ";
+            OptionsToMatch[OptionIdx]->printOne(errs());
+            if (OptionIdx+1 != e)
+              OptionsToMatch[OptionIdx+1]->printOne(errs());
+            if (OptionIdx+2 < e)
+              OptionsToMatch[OptionIdx+2]->printOne(errs());
+            errs() << "\n");
+    }
+    
+    // If we only found one option starting with this matcher, no factoring is
+    // possible.
+    if (EqualMatchers.size() == 1) {
+      NewOptionsToMatch.push_back(EqualMatchers[0]);
+      continue;
+    }
     
     // Factor these checks by pulling the first node off each entry and
     // discarding it.  Take the first one off the first entry to reuse.