Change order of tablegen generated fastisel instruction code to be based on instruction complexity

[seurer]

Summary

The order that tablegen fastisel instruction code is generated is currently based on the text of the predicate (using string lessthan). This patch changes this to instead use the instruction complexity. Because the complexities are not unique a C++ multimap is used instead of a map.

This fixes the problem where code with no predicate always comes out first (the empty string always compares as less than all other strings) thus making the code with predicates dead code. See the FMUL code in PPCFastISel.cpp for an example. It also more closely matches the normal codegen ordering. Some error checking in the tablegen fastisel code is fixed as well.

[wschmidt]

I like this approach. What did you do to verify the code that's produced for various targets? (You probably told me this but I've forgotten.)

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

767–768

You didn't introduce the problem, but there's a pretty large factoring opportunity between the code below and the sequence starting at 651. It would be nice to clean that up as long as you're in here.

[seurer]

In D6220#4, @wschmidt wrote:

I like this approach. What did you do to verify the code that's produced for various targets? (You probably told me this but I've forgotten.)

I went through some of the generated fastisel .inc files comparing them to a version generated without this change to see if anything stood out as broken. The ordering is different of course but I am not familiar with the other targets and so I don't know if they are OK or not. For Power it was all OK.

I tried to build the X86 target on my laptop to run tests there but I never got it to work.

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

767–768

Yeah, I noticed that those two sections of code were the same.

[seurer]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

730

Should this PrintWarning be an PrintError or an assert? The X86 target actually hits this at least once so perhaps there is some problem there.

[hfinkel]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

600

Make sure you're not adding lines > 80 cols.

[echristo]

In D6220#5, @seurer wrote:

In D6220#4, @wschmidt wrote:

I like this approach. What did you do to verify the code that's produced for various targets? (You probably told me this but I've forgotten.)

I went through some of the generated fastisel .inc files comparing them to a version generated without this change to see if anything stood out as broken. The ordering is different of course but I am not familiar with the other targets and so I don't know if they are OK or not. For Power it was all OK.

I tried to build the X86 target on my laptop to run tests there but I never got it to work.

What problems did you have here? (Though the tests in test/CodeGen/X86 should pass either way)

[seurer]

In D6220#8, @echristo wrote:

In D6220#5, @seurer wrote:

In D6220#4, @wschmidt wrote:

I like this approach. What did you do to verify the code that's produced for various targets? (You probably told me this but I've forgotten.)

I went through some of the generated fastisel .inc files comparing them to a version generated without this change to see if anything stood out as broken. The ordering is different of course but I am not familiar with the other targets and so I don't know if they are OK or not. For Power it was all OK.

I tried to build the X86 target on my laptop to run tests there but I never got it to work.

What problems did you have here? (Though the tests in test/CodeGen/X86 should pass either way)

The configure script complained about Python and I can't get it (Python) to build for some reason. I still plan on trying to get it to work.

[echristo]

Weird, what platform are you on? Anyhow, we can take that out of the code review. make check did pass on your ppc machine I gather?

[seurer]

In D6220#10, @echristo wrote:

Weird, what platform are you on? Anyhow, we can take that out of the code review. make check did pass on your ppc machine I gather?

make check works just fine.

[echristo]

In general looks good. Couple of inline comments and fixing the bit that Bill pointed out would be nice.

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

726

Too many negatives in this comment, could you reword please?

730

This would be nice to track down. What's running into it?

[seurer]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

730

llvm[3]: Building X86.td "fast" instruction selector implementation with tblgen
warning:Multiple instructions match and one with no predicate came before one with a predicate! name:VBROADCASTSSZr predicate: (Subtarget->hasAVX512())

.. unsigned fastEmit_X86ISD_VBROADCAST_MVT_v4f32_MVT_v16f32_r(unsigned Op0, bool Op0IsKill) {
.. return fastEmitInst_r(X86::VBROADCASTSSZr, &X86::VR512RegClass, Op0, Op0IsKill);
.. if ((Subtarget->hasAVX512())) {
.. return fastEmitInst_r(X86::VBROADCASTSSZr, &X86::VR512RegClass, Op0, Op0IsKill);
.. }
.. }

That function comes out the same way either or without these changes.

[echristo]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

730

That's... lovely.

Don't worry about it. I've looked at the .td files and it would need some work to fix it. It is a problem in the X86 backend, but until we can fix it we can't do anything about it.

Perhaps file a bug and leave a comment that this should be an error?

[seurer]

I updated the code with changes to address all the comments so far.

[echristo]

Couple of inline comments.

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

596–599

Is there a reason we either a) don't want this on by default, or b) would never want this on?

646

Can you file a bug for this and then link the PR?

[seurer]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

596–599

When I tried it generated over 150 warnings so it's probably just too noisy. I wasn't sure if multiple patterns having the same complexity could be a potential issue, though.

[echristo]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

596–599

Yeah, I don't think so. Go ahead and just delete the commented out code with a "Two patterns could have the same complexity and we just end up picking the first one" or something like that. (I think it's the first one at this point?)

[seurer]

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

596–599

They all will still be generated because the predicates are different. I believe the order will be the order in which they are encountered.

"When iterating over a std::multimap the elements are ordered by key, but the order of elements having the same key is not specified."

Hmmm, maybe not.

[hfinkel]

• Original Message -----

From: "Bill Seurer" <[e-mail]>
To: [e-mail], [e-mail], [e-mail], [e-mail]
Cc: [e-mail]
Sent: Thursday, November 13, 2014 4:57:55 PM
Subject: Re: [PATCH] Change order of tablegen generated fastisel instruction code to be based on instruction
complexity

Comment at:
/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp:595
@@ -570,2 +594,3 @@

• SimplePatterns[Operands][OpcodeName][VT][RetVT][PredicateCheck]

Memo;

+ This was used when testing
+ if
(SimplePatterns[Operands][OpcodeName][VT][RetVT].count(complexity))

{

echristo wrote:

seurer wrote:

echristo wrote:

Is there a reason we either a) don't want this on by default,
or b) would never want this on?

When I tried it generated over 150 warnings so it's probably just
too noisy. I wasn't sure if multiple patterns having the same
complexity could be a potential issue, though.

Yeah, I don't think so. Go ahead and just delete the commented out
code with a "Two patterns could have the same complexity and we
just end up picking the first one" or something like that. (I
think it's the first one at this point?)

They all will still be generated because the predicates are
different. I believe the order will be the order in which they are
encountered.

"When iterating over a std::multimap the elements are ordered by key,
but the order of elements having the same key is not specified."

Hmmm, maybe not.

It was unspecified in C++ before C++11, but since C++11, the order is specified to be stable. LLVM has other dependencies on this, IIRC.

http://stackoverflow.com/questions/2643473/does-stdmultiset-guarantee-insertion-order?rq=1

-Hal

http://reviews.llvm.org/D6220

[echristo]

Ah, thanks Hal.

LGTM then with the comment change.

-eric

[seurer]

Final (I hope) source updates with all comments taken into account.

[echristo]

One nit and LGTM.

Thanks for all the work here!

-eric

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

647

Canonical naming is "PR21575".

[seurer]

Corrected reference to PR21575

[echristo]

LGTM thanks.

[wschmidt]

I added the missing period! ;) Also, I committed the patch on Bill's behalf. r222038. Thanks for the work, Bill!

/home/seurer/llvm/llvm-oneoff/utils/TableGen/FastISelEmitter.cpp

 /// instruction needed to emit code for it.
 ///
 namespace {
 struct InstructionMemo {
   std::string Name;
   const CodeGenRegisterClass *RC;
   std::string SubRegNo;
   std::vector<std::string>* PhysRegs;
+  std::string PredicateCheck;
 };
 } // End anonymous namespace
 
 /// ImmPredicateSet - This uniques predicates (represented as a string) and
 /// gives them unique (small) integer ID's that start at 0.
 namespace {
 class ImmPredicateSet {
   DenseMap<TreePattern *, unsigned> ImmIDs;
void PrintManglingSuffix(raw_ostream &OS, ImmPredicateSet &ImmPredicates,
     for (unsigned i = 0, e = Operands.size(); i != e; ++i)
       Operands[i].printManglingSuffix(OS, ImmPredicates, StripImmCodes);
   }
 };
 } // End anonymous namespace
 
 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;
   typedef std::map<OperandsSignature, OpcodeTypeRetPredMap>
             OperandsOpcodeTypeRetPredMap;
 
   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;
 
   std::string InstNS;
   ImmPredicateSet ImmediatePredicates;
 public:
   explicit FastISelMap(std::string InstNS);
 
   void collectPatterns(CodeGenDAGPatterns &CGP);
   void printImmediatePredicates(raw_ostream &OS);
   void printFunctionDefinitions(raw_ostream &OS);
+private:  
+  void emitInstructionCode(raw_ostream &OS, 
+                           const OperandsSignature &Operands,
+                           const PredMap &PM, 
+                           const std::string &RetVTName);
 };
 } // End anonymous namespace
 
 static std::string getOpcodeName(Record *Op, CodeGenDAGPatterns &CGP) {
   return CGP.getSDNodeInfo(Op).getEnumName();
 }
 
 static std::string getLegalCName(std::string OpName) {
for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
     // Get the predicate that guards this pattern.
     std::string PredicateCheck = Pattern.getPredicateCheck();
 
     // Ok, we found a pattern that we can handle. Remember it.
     InstructionMemo Memo = {
       Pattern.getDstPattern()->getOperator()->getName(),
       DstRC,
       SubRegNo,
-      PhysRegInputs
+      PhysRegInputs,
+      PredicateCheck
     };
     
-    if (SimplePatterns[Operands][OpcodeName][VT][RetVT].count(PredicateCheck))
+    int complexity = Pattern.getPatternComplexity(CGP);
+
+    if (SimplePatternsCheck[Operands][OpcodeName][VT]
+         [RetVT].count(PredicateCheck)) {
       PrintFatalError(Pattern.getSrcRecord()->getLoc(),
-                    "Duplicate record in FastISel table!");
+                    "Duplicate predicate in FastISel table!");
+    }
+    SimplePatternsCheck[Operands][OpcodeName][VT][RetVT].insert(
+         std::make_pair(PredicateCheck, true));
 
-    SimplePatterns[Operands][OpcodeName][VT][RetVT][PredicateCheck] = Memo;
+     // Note: Instructions with the same complexity will appear in the order
+     // that they are encountered.
+    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
     // associate them with the stripped predicate version.
     if (Operands.hasAnyImmediateCodes()) {
       SignaturesWithConstantForms[Operands.getWithoutImmCodes()]
         .push_back(Operands);
     }
   }
 }
 
 void FastISelMap::printImmediatePredicates(raw_ostream &OS) {
   if (ImmediatePredicates.begin() == ImmediatePredicates.end())
     return;
 
   OS << "\n// FastEmit Immediate Predicate functions.\n";
   for (ImmPredicateSet::iterator I = ImmediatePredicates.begin(),
        E = ImmediatePredicates.end(); I != E; ++I) {
     OS << "static bool " << I->getFnName() << "(int64_t Imm) {\n";
     OS << I->getImmediatePredicateCode() << "\n}\n";
   }
 
   OS << "\n\n";
 }
 
+void FastISelMap::emitInstructionCode(raw_ostream &OS, 
+                                      const OperandsSignature &Operands,
+                                      const PredMap &PM, 
+                                      const std::string &RetVTName) {
+  // Emit code for each possible instruction. There may be
+  // multiple if there are subtarget concerns.  A reverse iterator
+  // is used to produce the ones with highest complexity first.
+
+  bool OneHadNoPredicate = false;
+  for (PredMap::const_reverse_iterator PI = PM.rbegin(), PE = PM.rend();
+       PI != PE; ++PI) {
+    const InstructionMemo &Memo = PI->second;
+    std::string PredicateCheck = Memo.PredicateCheck;
+
+    if (PredicateCheck.empty()) {
+      assert(!OneHadNoPredicate &&
+             "Multiple instructions match and more than one had "
+             "no predicate!");
+      OneHadNoPredicate = true;
+    } else {
+      if (OneHadNoPredicate) {
+        // FIXME: This should be a PrintError once the x86 target fixes PR21575
+        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 << "  ";
+    }
+
+    for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) {
+      if ((*Memo.PhysRegs)[i] != "")
+        OS << "  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, "
+           << "TII.get(TargetOpcode::COPY), "
+           << (*Memo.PhysRegs)[i] << ").addReg(Op" << i << ");\n";
+    }
+
+    OS << "  return fastEmitInst_";
+    if (Memo.SubRegNo.empty()) {
+      Operands.PrintManglingSuffix(OS, *Memo.PhysRegs,
+     ImmediatePredicates, true);
+      OS << "(" << InstNS << Memo.Name << ", ";
+      OS << "&" << InstNS << Memo.RC->getName() << "RegClass";
+      if (!Operands.empty())
+        OS << ", ";
+      Operands.PrintArguments(OS, *Memo.PhysRegs);
+      OS << ");\n";
+    } else {
+      OS << "extractsubreg(" << RetVTName
+         << ", Op0, Op0IsKill, " << Memo.SubRegNo << ");\n";
+    }
+
+    if (!PredicateCheck.empty()) {
+      OS << "  }\n";
+    }
+  }
+  // Return 0 if all of the possibilities had predicates but none
+  // were satisfied.
+  if (!OneHadNoPredicate)
+    OS << "  return 0;\n";
+  OS << "}\n";
+  OS << "\n";
+}
+
 
 void FastISelMap::printFunctionDefinitions(raw_ostream &OS) {
   // Now emit code for all the patterns that we collected.
   for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(),
        OE = SimplePatterns.end(); OI != OE; ++OI) {
     const OperandsSignature &Operands = OI->first;
     const OpcodeTypeRetPredMap &OTM = OI->second;
 
for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end();
            TI != TE; ++TI) {
         MVT::SimpleValueType VT = TI->first;
         const RetPredMap &RM = TI->second;
         if (RM.size() != 1) {
           for (RetPredMap::const_iterator RI = RM.begin(), RE = RM.end();
                RI != RE; ++RI) {
             MVT::SimpleValueType RetVT = RI->first;
             const PredMap &PM = RI->second;
-            bool HasPred = false;
 
             OS << "unsigned fastEmit_"
                << getLegalCName(Opcode)
                << "_" << getLegalCName(getName(VT))
                << "_" << getLegalCName(getName(RetVT)) << "_";
             Operands.PrintManglingSuffix(OS, ImmediatePredicates);
             OS << "(";
             Operands.PrintParameters(OS);
             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();
-                 PI != PE; ++PI) {
-              std::string PredicateCheck = PI->first;
-              const InstructionMemo &Memo = PI->second;
-
-              if (PredicateCheck.empty()) {
-                assert(!HasPred &&
-                       "Multiple instructions match, at least one has "
-                       "a predicate and at least one doesn't!");
-              } else {
-                OS << "  if (" + PredicateCheck + ") {\n";
-                OS << "  ";
-                HasPred = true;
-              }
-
-              for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) {
-                if ((*Memo.PhysRegs)[i] != "")
-                  OS << "  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, "
-                     << "TII.get(TargetOpcode::COPY), "
-                     << (*Memo.PhysRegs)[i] << ").addReg(Op" << i << ");\n";
-              }
-
-              OS << "  return fastEmitInst_";
-              if (Memo.SubRegNo.empty()) {
-                Operands.PrintManglingSuffix(OS, *Memo.PhysRegs,
-                                             ImmediatePredicates, true);
-                OS << "(" << InstNS << Memo.Name << ", ";
-                OS << "&" << InstNS << Memo.RC->getName() << "RegClass";
-                if (!Operands.empty())
-                  OS << ", ";
-                Operands.PrintArguments(OS, *Memo.PhysRegs);
-                OS << ");\n";
-              } else {
-                OS << "extractsubreg(" << getName(RetVT);
-                OS << ", Op0, Op0IsKill, " << Memo.SubRegNo << ");\n";
-              }
-
-              if (HasPred)
-                OS << "  }\n";
-
-            }
-            // Return 0 if none of the predicates were satisfied.
-            if (HasPred)
-              OS << "  return 0;\n";
-            OS << "}\n";
-            OS << "\n";
+            emitInstructionCode(OS, Operands, PM, getName(RetVT));
           }
 
           // Emit one function for the type that demultiplexes on return type.
           OS << "unsigned fastEmit_"
              << getLegalCName(Opcode) << "_"
              << getLegalCName(getName(VT)) << "_";
           Operands.PrintManglingSuffix(OS, ImmediatePredicates);
           OS << "(MVT RetVT";
           if (!Operands.empty())
             OS << ", ";
           Operands.PrintParameters(OS);
           OS << ") {\nswitch (RetVT.SimpleTy) {\n";
for (OpcodeTypeRetPredMap::const_iterator I = OTM.begin(), E = OTM.end();
           if (!Operands.empty())
             OS << ", ";
           Operands.PrintParameters(OS);
           OS << ") {\n";
 
           OS << "  if (RetVT.SimpleTy != " << getName(RM.begin()->first)
              << ")\n    return 0;\n";
 
           const PredMap &PM = RM.begin()->second;
-          bool HasPred = 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;
-               ++PI) {
-            std::string PredicateCheck = PI->first;
-            const InstructionMemo &Memo = PI->second;
-
-            if (PredicateCheck.empty()) {
-              assert(!HasPred &&
-                     "Multiple instructions match, at least one has "
-                     "a predicate and at least one doesn't!");
-            } else {
-              OS << "  if (" + PredicateCheck + ") {\n";
-              OS << "  ";
-              HasPred = true;
-            }
-
-            for (unsigned i = 0; i < Memo.PhysRegs->size(); ++i) {
-              if ((*Memo.PhysRegs)[i] != "")
-                OS << "  BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, "
-                   << "TII.get(TargetOpcode::COPY), "
-                   << (*Memo.PhysRegs)[i] << ").addReg(Op" << i << ");\n";
-            }
 
-            OS << "  return fastEmitInst_";
-
-            if (Memo.SubRegNo.empty()) {
-              Operands.PrintManglingSuffix(OS, *Memo.PhysRegs,
-                                           ImmediatePredicates, true);
-              OS << "(" << InstNS << Memo.Name << ", ";
-              OS << "&" << InstNS << Memo.RC->getName() << "RegClass";
-              if (!Operands.empty())
-                OS << ", ";
-              Operands.PrintArguments(OS, *Memo.PhysRegs);
-              OS << ");\n";
-            } else {
-              OS << "extractsubreg(RetVT, Op0, Op0IsKill, ";
-              OS << Memo.SubRegNo;
-              OS << ");\n";
-            }
-
-             if (HasPred)
-               OS << "  }\n";
-          }
-
-          // Return 0 if none of the predicates were satisfied.
-          if (HasPred)
-            OS << "  return 0;\n";
-          OS << "}\n";
-          OS << "\n";
+          emitInstructionCode(OS, Operands, PM, "RetVT");
         }
       }
 
       // Emit one function for the opcode that demultiplexes based on the type.
       OS << "unsigned fastEmit_"
          << getLegalCName(Opcode) << "_";
       Operands.PrintManglingSuffix(OS, ImmediatePredicates);
       OS << "(MVT VT, MVT RetVT";