Index: /home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp
===================================================================
--- /home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp
+++ /home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp
@@ -37,6 +37,7 @@
   const CodeGenRegisterClass *RC;
   std::string SubRegNo;
   std::vector<std::string>* PhysRegs;
+  std::string PredicateCheck;
 };
 } // End anonymous namespace
 
@@ -365,7 +366,9 @@
 
 namespace {
 class FastISelMap {
-  typedef std::map<std::string, InstructionMemo> PredMap;
+  // A multimap is needed instead of a "plain" map because the key is 
+  // the instruction's complexity (an int) and they are not unique.
+  typedef std::multimap<int, InstructionMemo> PredMap;
   typedef std::map<MVT::SimpleValueType, PredMap> RetPredMap;
   typedef std::map<MVT::SimpleValueType, RetPredMap> TypeRetPredMap;
   typedef std::map<std::string, TypeRetPredMap> OpcodeTypeRetPredMap;
@@ -374,6 +377,16 @@
 
   OperandsOpcodeTypeRetPredMap SimplePatterns;
 
+  // This is used to check that there are no duplicate predicates            
+  typedef std::multimap<std::string, bool> PredCheckMap;
+  typedef std::map<MVT::SimpleValueType, PredCheckMap> RetPredCheckMap;
+  typedef std::map<MVT::SimpleValueType, RetPredCheckMap> TypeRetPredCheckMap;
+  typedef std::map<std::string, TypeRetPredCheckMap> OpcodeTypeRetPredCheckMap;
+  typedef std::map<OperandsSignature, OpcodeTypeRetPredCheckMap>
+            OperandsOpcodeTypeRetPredCheckMap;
+
+  OperandsOpcodeTypeRetPredCheckMap SimplePatternsCheck;
+
   std::map<OperandsSignature, std::vector<OperandsSignature> >
     SignaturesWithConstantForms;
 
@@ -561,14 +574,18 @@
       Pattern.getDstPattern()->getOperator()->getName(),
       DstRC,
       SubRegNo,
-      PhysRegInputs
+      PhysRegInputs,
+      PredicateCheck
     };
 
-    if (SimplePatterns[Operands][OpcodeName][VT][RetVT].count(PredicateCheck))
-      PrintFatalError(Pattern.getSrcRecord()->getLoc(),
-                    "Duplicate record in FastISel table!");
+    int complexity = Pattern.getPatternComplexity(CGP);
 
-    SimplePatterns[Operands][OpcodeName][VT][RetVT][PredicateCheck] = Memo;
+    if (SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].count(PredicateCheck)) {
+      PrintFatalError(Pattern.getSrcRecord()->getLoc(),
+                    "Duplicate predicate in FastISel table!");
+    }
+    SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].insert(std::make_pair(PredicateCheck, true));
+    SimplePatterns[Operands][OpcodeName][VT][RetVT].insert(std::make_pair(complexity, Memo));
 
     // If any of the operands were immediates with predicates on them, strip
     // them down to a signature that doesn't have predicates so that we can
@@ -620,7 +637,7 @@
                RI != RE; ++RI) {
             MVT::SimpleValueType RetVT = RI->first;
             const PredMap &PM = RI->second;
-            bool HasPred = false;
+            bool OneHadNoPredicate = false;
 
             OS << "unsigned fastEmit_"
                << getLegalCName(Opcode)
@@ -632,20 +649,26 @@
             OS << ") {\n";
 
             // Emit code for each possible instruction. There may be
-            // multiple if there are subtarget concerns.
-            for (PredMap::const_iterator PI = PM.begin(), PE = PM.end();
+            // multiple if there are subtarget concerns.  A reverse iterator
+            // is used to produce the ones with highest complexity first.
+            for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend();
                  PI != PE; ++PI) {
-              std::string PredicateCheck = PI->first;
               const InstructionMemo &Memo = PI->second;
+              std::string PredicateCheck = Memo.PredicateCheck;
 
               if (PredicateCheck.empty()) {
-                assert(!HasPred &&
-                       "Multiple instructions match, at least one has "
-                       "a predicate and at least one doesn't!");
+                assert(!OneHadNoPredicate &&
+                       "Multiple instructions match and more than one had "
+                       "no predicate!");
+                OneHadNoPredicate = true;
               } else {
+                if (OneHadNoPredicate) {
+                  PrintWarning("Multiple instructions match and one with no predicate "
+                               "came before one with a predicate!  name:" + Memo.Name +
+                               "  predicate: " + PredicateCheck);
+                }
                 OS << "  if (" + PredicateCheck + ") {\n";
                 OS << "  ";
-                HasPred = true;
               }
 
               for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) {
@@ -670,12 +693,13 @@
                 OS << ", Op0, Op0IsKill, " << Memo.SubRegNo << ");\n";
               }
 
-              if (HasPred)
+              if (!PredicateCheck.empty()) {
                 OS << "  }\n";
-
             }
-            // Return 0 if none of the predicates were satisfied.
-            if (HasPred)
+            }
+            // Return 0 if none of the predicates were satisfied and there
+            // was not one without a predicate.
+            if (!OneHadNoPredicate)
               OS << "  return 0;\n";
             OS << "}\n";
             OS << "\n";
@@ -720,23 +744,29 @@
              << ")\n    return 0;\n";
 
           const PredMap &PM = RM.begin()->second;
-          bool HasPred = false;
+          bool OneHadNoPredicate = false;
 
           // Emit code for each possible instruction. There may be
-          // multiple if there are subtarget concerns.
-          for (PredMap::const_iterator PI = PM.begin(), PE = PM.end(); PI != PE;
+          // multiple if there are subtarget concerns.  A reverse iterator
+          // is used to produce the ones with highest complexity first.
+          for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend(); PI != PE; 
                ++PI) {
-            std::string PredicateCheck = PI->first;
             const InstructionMemo &Memo = PI->second;
+            std::string PredicateCheck = Memo.PredicateCheck;
 
             if (PredicateCheck.empty()) {
-              assert(!HasPred &&
-                     "Multiple instructions match, at least one has "
-                     "a predicate and at least one doesn't!");
+                assert(!OneHadNoPredicate &&
+                       "Multiple instructions match and more than one had "
+                       "no predicate!");
+              OneHadNoPredicate = true;
             } else {
+                if (OneHadNoPredicate) {
+                  PrintWarning("Multiple instructions match and one with no predicate "
+                               "came before one with a predicate!  name:" + Memo.Name +
+                               "  predicate: " + PredicateCheck);
+                }
               OS << "  if (" + PredicateCheck + ") {\n";
               OS << "  ";
-              HasPred = true;
             }
 
             for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) {
@@ -763,12 +793,14 @@
               OS << ");\n";
             }
 
-             if (HasPred)
+            if (!PredicateCheck.empty()) {
                OS << "  }\n";
           }
+          }
 
-          // Return 0 if none of the predicates were satisfied.
-          if (HasPred)
+          // Return 0 if none of the predicates were satisfied and there
+          // was not one without a predicate.
+          if (!OneHadNoPredicate)
             OS << "  return 0;\n";
           OS << "}\n";
           OS << "\n";