Switch pattern sorting predicate from stable sort -> sort, it

doesn't need to be stable because the patterns are fully ordered.

Add a first level sort predicate that orders patterns in this
order:  1) scalar integer operations 2) scalar floating point
3) vector int 4) vector float.  This is a trivial sort on their
top level pattern type so it is nice and transitive.  The
benefit of doing this is that simple integer operations are
much more common than insane vector things and isel was trying
to match the big complex vector patterns before the simple
ones because the complexity of the vector operations was much
higher.  Since they can't both match, it is best (for compile
time) to try the simple integer ones first.

This cuts down the # failed match attempts on real code by
quite a bit, for example, this reduces backtracks on crafty
(as a random example) from 228285 -> 188369.

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

diff --git a/utils/TableGen/DAGISelEmitter.cpp b/utils/TableGen/DAGISelEmitter.cpp
index f4a287c6c65368732835acbe2a2a57707328ebc7..04c7710ac5034163fa5fa68d84a494c6707ecf90 100644 (file)
--- a/utils/TableGen/DAGISelEmitter.cpp
+++ b/utils/TableGen/DAGISelEmitter.cpp
@@ -102,7 +102,6 @@ void DAGISelEmitter::EmitPredicateFunctions(raw_ostream &OS) {
   OS << "\n\n";
 }
 
-
 namespace {
 // PatternSortingPredicate - return true if we prefer to match LHS before RHS.
 // In particular, we want to match maximal patterns first and lowest cost within
@@ -112,6 +111,19 @@ struct PatternSortingPredicate {
   CodeGenDAGPatterns &CGP;
   
   bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) {
+    const TreePatternNode *LHSSrc = LHS->getSrcPattern();
+    const TreePatternNode *RHSSrc = RHS->getSrcPattern();
+    
+    if (LHSSrc->getNumTypes() != 0 && RHSSrc->getNumTypes() != 0 &&
+        LHSSrc->getType(0) != RHSSrc->getType(0)) {
+      MVT::SimpleValueType V1 = LHSSrc->getType(0), V2 = RHSSrc->getType(0);
+      if (MVT(V1).isVector() != MVT(V2).isVector())
+        return MVT(V2).isVector();
+      
+      if (MVT(V1).isFloatingPoint() != MVT(V2).isFloatingPoint())
+        return MVT(V2).isFloatingPoint();
+    }
+    
     // Otherwise, if the patterns might both match, sort based on complexity,
     // which means that we prefer to match patterns that cover more nodes in the
     // input over nodes that cover fewer.
@@ -167,8 +179,7 @@ void DAGISelEmitter::run(raw_ostream &OS) {
 
   // We want to process the matches in order of minimal cost.  Sort the patterns
   // so the least cost one is at the start.
-  std::stable_sort(Patterns.begin(), Patterns.end(),
-                   PatternSortingPredicate(CGP));
+  std::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP));
   
   
   // Convert each variant of each pattern into a Matcher.