[globalisel] Separate the SelectionDAG importer from the emitter. NFC

[dsanders]

Summary

In the near future the rules will be sorted between these two steps to
ensure that more important rules are not prevented by less important ones.

[kristof.beyls]

utils/TableGen/GlobalISelEmitter.cpp

562

This comment has become incorrect in the new version of the code?
Probably best to just remove?

[ab]

utils/TableGen/GlobalISelEmitter.cpp

58–59

My original thought was to replace, when we get to this point, the Optional<SkipReason> with an Expected<something>. I gave that a shot in D29743, what do you think?

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

58–59

I'm in two minds about this at the moment. I originally started this writing this patch as a transformation to Expected<RuleMatcher> but I went with the std::vector<RuleMatcher> in the end due to a need to emit multiple rules for a single pattern. I was thinking about commutativity at the time and was planning to expand, for example, (G_XOR $rs, -1) as two separate rules but I tried to implement commutativity yesterday and it's looking like it will be easier to handle that in the InstructionMatcher. However, I think the multiple-rules requirement may also arise for other cases (e.g. ComplexPattern) so I'm not entirely convinced I don't need the vector anymore.

I suppose it's best to go with Expected<RuleMatcher> until we have a pressing need to expand patterns into multiple rules at which point we can re-assess how we do this.

562

I wouldn't go as far as saying it's incorrect but I agree it's not serving any real purpose anymore. I'll remove it if we go ahead with this patch rather than D29743

[ab]

utils/TableGen/GlobalISelEmitter.cpp

58–59

IIRC things like commutativity are handled as extra PatternToMatch entries, somewhere when we do the initial CodeGenDAGPatterns parse. If that's true, it does mean we'll get mostly-identical rules. So you're right, doing something in InstructionMatcher is probably the smart move.

But either way, can't we do Expected<std::vector<RuleMatcher>> ? It's a tad more expensive, but it seems like we could still move all the RuleMatchers.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

58–59

CodeGenDAGPatterns::AddPatternToMatch() is rejecting the commutative cases on the grounds that they can never match. This is because DAGCombiner::visitADD() canonicalizes ISD::ADD nodes such that the immediate is always on the right hand side.

[dsanders]

Rebased to trunk.

[ab]

utils/TableGen/GlobalISelEmitter.cpp

58–59

Interesting; I suppose immediates aren't a great example, as we should also (eventually) do the canonicalization.

What about things like (mul x, (add y, z)) ? Do we need to handle commutativity for those ourselves?

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

58–59

I think we do need to handle those cases. AddPatternToMatch() isn't rejecting those and both patterns show up separately in AArch64GenDAGISel.inc.

For example: AArch64 has these entries in MatcherTable:

// Src: (add:i64 (mul:i64 (sext:i64 GPR32:i32:$Rn), (imm:i64)<<P:Predicate_s64imm_32bit>>:$C), GPR64:i64:$Ra) - Complexity = 18
// Dst: (SMADDLrrr:i64 GPR32:i32:$Rn, (MOVi32imm:i32 (trunc_imm:i32 (imm:i64):$C)), GPR64:i64:$Ra)

// Src: (add:i64 GPR64:i64:$Ra, (mul:i64 (sext:i64 GPR32:i32:$Rn), (imm:i64)<<P:Predicate_s64imm_32bit>>:$C)) - Complexity = 18
// Dst: (SMADDLrrr:i64 GPR32:i32:$Rn, (MOVi32imm:i32 (trunc_imm:i32 (imm:i64):$C)), GPR64:i64:$Ra)

utils/TableGen/GlobalISelEmitter.cpp

 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 #include <string>
 using namespace llvm;
 
 #define DEBUG_TYPE "gisel-emitter"
 
 STATISTIC(NumPatternTotal, "Total number of patterns");
-STATISTIC(NumPatternSkipped, "Number of patterns skipped");
+STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
+STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
 
 static cl::opt<bool> WarnOnSkippedPatterns(
     "warn-on-skipped-patterns",
     cl::desc("Explain why a pattern was skipped for inclusion "
              "in the GlobalISel selector"),
     cl::init(false));
 
 namespace {
-class RuleMatcher;
 
 //===- Helper functions ---------------------------------------------------===//
 
 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
 static Optional<std::string> MVTToLLT(MVT::SimpleValueType SVT) {
   std::string TyStr;
   raw_string_ostream OS(TyStr);
   MVT VT(SVT);
public:
   }
 
   template <class Kind, class... Args>
   Kind &addAction(Args&&... args) {
     Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
     return *static_cast<Kind *>(Actions.back().get());
   }
 
-  void emit(raw_ostream &OS) {
+  void emit(raw_ostream &OS) const {
     if (Matchers.empty())
       llvm_unreachable("Unexpected empty matcher!");
 
     // The representation supports rules that require multiple roots such as:
     //    %ptr(p0) = ...
     //    %elt0(s32) = G_LOAD %ptr
     //    %1(p0) = G_ADD %ptr, 4
     //    %elt1(s32) = G_LOAD p0 %1
for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx);
     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
     OM.addPredicate<RegisterBankOperandMatcher>(
         Target.getRegisterClass(ChildRec));
     ++OpIdx;
   }
 
   // We're done with this pattern!  It's eligible for GISel emission; return it.
+  ++NumPatternImported;
   return std::move(M);
 }
 
 void GlobalISelEmitter::run(raw_ostream &OS) {
   // Track the GINodeEquiv definitions.
   gatherNodeEquivs();
 
   emitSourceFileHeader(("Global Instruction Selector for the " +
                        Target.getName() + " target").str(), OS);
   OS << "bool " << Target.getName()
      << "InstructionSelector::selectImpl"
         "(MachineInstr &I) const {\n  const MachineRegisterInfo &MRI = "
         "I.getParent()->getParent()->getRegInfo();\n\n";
 
+  std::vector<RuleMatcher> Rules;
   // Look through the SelectionDAG patterns we found, possibly emitting some.
   for (const PatternToMatch &Pat : CGP.ptms()) {
     ++NumPatternTotal;
     auto MatcherOrErr = runOnPattern(Pat);
 
     // The pattern analysis can fail, indicating an unsupported pattern.
     // Report that if we've been asked to do so.
     if (auto Err = MatcherOrErr.takeError()) {
       if (WarnOnSkippedPatterns) {
         PrintWarning(Pat.getSrcRecord()->getLoc(),
                      "Skipped pattern: " + toString(std::move(Err)));
       } else {
         consumeError(std::move(Err));
       }
-      ++NumPatternSkipped;
+      ++NumPatternImportsSkipped;
       continue;
     }
 
-    MatcherOrErr->emit(OS);
+    Rules.push_back(std::move(MatcherOrErr.get()));
+  }
+
+  for (const auto &Rule : Rules) {
+    Rule.emit(OS);
     ++NumPatternEmitted;
   }
 
   OS << "  return false;\n}\n";
 }
 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 
 namespace llvm {
 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
   GlobalISelEmitter(RK).run(OS);
 }
 } // End llvm namespace