[tablegen][globalisel] Convert the SelectionDAG importer to a tree walking approach. NFC

[dsanders]

Summary

But don't actually inspect the tree any deeper than we already do. This
change is NFC but the next one will enable full traversal of the
source/destination patterns.

Depends on D30535

[dsanders]

ping

[dsanders]

Refresh and ping. This patch is the main bottleneck for a lot of the tablegen work.

[ab]

This generally seems sensible, but if feasible it might be a good idea to replace the 'Expected<bool>' with 'Error'.

utils/TableGen/GlobalISelEmitter.cpp

1281–1284

Here and elsewhere: is it possible to fold the call into the if? Something like:

if (auto Err = importRulePredicates(M, P.getPredicates()->getValues()).takeError())
  return Err;

That also lets you avoid the not-very-descriptive 'TrueOrError'.

More generally, an 'Expected<bool>' that's always true seems odd. If you don't have plans to add more information, maybe just return an Error? Then the whole takeError vs weird-name problem goes away.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

1281–1284

Here and elsewhere: is it possible to fold the call into the if? Something like:

if (auto Err = importRulePredicates(M, P.getPredicates()->getValues()).takeError())

return Err;

That also lets you avoid the not-very-descriptive 'TrueOrError'.

I'll make this change in the commit.

More generally, an 'Expected<bool>' that's always true seems odd.

The bool is only there because Expected<void> isn't allowed. Optional<Error> is a bit more accurate but it has a different API and you then have to remember which functions return Expected<X> and which return Optional<Error>. I decided it was best to lean towards consistency.

If you don't have plans to add more information, maybe just return an Error? Then the
whole takeError vs weird-name problem goes away.

If a function always returns an Error, what does it return on success? It would be strange to have an Error that is not an error.

[dsanders]

Fold away the TrueOrError variables.

[ab]

If a function always returns an Error, what does it return on success? It would be strange to have an Error that is not an error.

It returns Error::success(). The name is somewhat awkward, but think of it as a replacement for the old-style 'int' return values, or c++ std::error_code. There are a few examples in http://llvm.org/docs/ProgrammersManual.html#recoverable-errors.

[dsanders]

In D30536#713232, @ab wrote:

If a function always returns an Error, what does it return on success? It would be strange to have an Error that is not an error.

It returns Error::success(). The name is somewhat awkward, but think of it as a replacement for the old-style 'int' return values, or c++ std::error_code. There are a few examples in http://llvm.org/docs/ProgrammersManual.html#recoverable-errors.

Hmm, I'm not keen returning an Error that represents success or using multiple error handling strategies for one family of functions. That said, the former is an established idiom and I suppose I could deal with the latter by renaming to createAndImport*() for the ones that return an Expected<X> and keeping import*() for the ones that return Error.

I'll commit a follow-up tomorrow to make that change.

utils/TableGen/GlobalISelEmitter.cpp

 
 public:
   OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx,
                  const std::string &SymbolicName)
       : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName) {}
 
   bool hasSymbolicName() const { return !SymbolicName.empty(); }
   const StringRef getSymbolicName() const { return SymbolicName; }
+  void setSymbolicName(StringRef Name) {
+    assert(SymbolicName.empty() && "Operand already has a symbolic name");
+    SymbolicName = Name;
+  }
   unsigned getOperandIndex() const { return OpIdx; }
 
   std::string getOperandExpr(const StringRef InsnVarName) const {
     return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
   }
 
   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 

 
 public:
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName) {
     Operands.emplace_back(*this, OpIdx, SymbolicName);
     return Operands.back();
   }
 
+  OperandMatcher &getOperand(unsigned OpIdx) {
+    auto I = std::find_if(Operands.begin(), Operands.end(),
+                          [&OpIdx](const OperandMatcher &X) {
+                            return X.getOperandIndex() == OpIdx;
+                          });
+    if (I != Operands.end())
+      return *I;
+    llvm_unreachable("Failed to lookup operand");
+  }
+
   Optional<const OperandMatcher *> getOptionalOperand(StringRef SymbolicName) const {
     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
     const auto &I = std::find_if(Operands.begin(), Operands.end(),
                                  [&SymbolicName](const OperandMatcher &X) {
                                    return X.getSymbolicName() == SymbolicName;
                                  });
     if (I != Operands.end())
       return &*I;
     return None;
   }
 
   const OperandMatcher &getOperand(const StringRef SymbolicName) const {
     Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
     if (OM.hasValue())
       return *OM.getValue();
     llvm_unreachable("Failed to lookup operand");
   }
 
   unsigned getNumOperands() const { return Operands.size(); }
-  OperandVec::const_iterator operands_begin() const {
-    return Operands.begin();
-  }
-  OperandVec::const_iterator operands_end() const {
-    return Operands.end();
-  }
+  OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
+  OperandVec::const_iterator operands_end() const { return Operands.end(); }
   iterator_range<OperandVec::const_iterator> operands() const {
     return make_range(operands_begin(), operands_end());
   }
 
   /// Emit C++ statements to check the shape of the match and capture
   /// instructions into local variables.
   ///
   /// TODO: When nested instruction matching is implemented, this function will
private:
   /// Keep track of the equivalence between ComplexPattern's and
   /// GIComplexOperandMatcher. Map entries are specified by subclassing
   /// GIComplexPatternEquiv.
   DenseMap<const Record *, const Record *> ComplexPatternEquivs;
 
   void gatherNodeEquivs();
   const CodeGenInstruction *findNodeEquiv(Record *N) const;
 
+  Expected<bool> importRulePredicates(RuleMatcher &M,
+                                      ArrayRef<Init *> Predicates) const;
+  Expected<InstructionMatcher &>
+  importSelDAGMatcher(InstructionMatcher &InsnMatcher,
+                      const TreePatternNode *Src) const;
+  Expected<bool> importChildMatcher(InstructionMatcher &InsnMatcher,
+                                    TreePatternNode *SrcChild, unsigned OpIdx,
+                                    unsigned &TempOpIdx) const;
+  Expected<BuildMIAction &>
+  importInstructionRenderer(RuleMatcher &M, const TreePatternNode *Dst,
+                            const InstructionMatcher &InsnMatcher) const;
+  Expected<bool> importExplicitUseRenderer(
+      BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
+      const InstructionMatcher &InsnMatcher, unsigned &TempOpIdx) const;
+  Expected<bool>
+  importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
+                             const std::vector<Record *> &ImplicitDefs) const;
+
   /// Analyze pattern \p P, returning a matcher for it if possible.
   /// Otherwise, return an Error explaining why we don't support it.
   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
 };
 
 void GlobalISelEmitter::gatherNodeEquivs() {
   assert(NodeEquivs.empty());
   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))

 
 //===- Emitter ------------------------------------------------------------===//
 
 /// Helper function to let the emitter report skip reason error messages.
 static Error failedImport(const Twine &Reason) {
   return make_error<StringError>(Reason, inconvertibleErrorCode());
 }
 
-Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
-  unsigned TempOpIdx = 0;
-
-  // Keep track of the matchers and actions to emit.
-  RuleMatcher M;
-  M.addAction<DebugCommentAction>(P);
-
-  // First, analyze the whole pattern.
-  // If the entire pattern has a predicate (e.g., target features), ignore it.
-  if (!P.getPredicates()->getValues().empty())
+Expected<bool>
+GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
+                                        ArrayRef<Init *> Predicates) const {
+  if (!Predicates.empty())
     return failedImport("Pattern has a predicate");
+  return true;
+}
 
-  // Physreg imp-defs require additional logic.  Ignore the pattern.
-  if (!P.getDstRegs().empty())
-    return failedImport("Pattern defines a physical register");
-
-  // Next, analyze the pattern operators.
-  TreePatternNode *Src = P.getSrcPattern();
-  TreePatternNode *Dst = P.getDstPattern();
-
-  // If the root of either pattern isn't a simple operator, ignore it.
-  if (!isTrivialOperatorNode(Dst))
-    return failedImport("Dst pattern root isn't a trivial operator");
-  if (!isTrivialOperatorNode(Src))
-    return failedImport("Src pattern root isn't a trivial operator");
-
-  Record *DstOp = Dst->getOperator();
-  if (!DstOp->isSubClassOf("Instruction"))
-    return failedImport("Pattern operator isn't an instruction");
-
-  auto &DstI = Target.getInstruction(DstOp);
+Expected<InstructionMatcher &>
+GlobalISelEmitter::importSelDAGMatcher(InstructionMatcher &InsnMatcher,
+                                       const TreePatternNode *Src) const {
+  // Start with the defined operands (i.e., the results of the root operator).
+  if (Src->getExtTypes().size() > 1)
+    return failedImport("Src pattern has multiple results");
 
   auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
   if (!SrcGIOrNull)
     return failedImport("Pattern operator lacks an equivalent Instruction");
   auto &SrcGI = *SrcGIOrNull;
 
   // The operators look good: match the opcode and mutate it to the new one.
-  InstructionMatcher &InsnMatcher = M.addInstructionMatcher();
   InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
-  auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
-
-  // Next, analyze the children, only accepting patterns that don't require
-  // any change to operands.
-  if (Src->getNumChildren() != Dst->getNumChildren())
-    return failedImport("Src/dst patterns have a different # of children");
 
   unsigned OpIdx = 0;
-
-  // Start with the defined operands (i.e., the results of the root operator).
-  if (DstI.Operands.NumDefs != Src->getExtTypes().size())
-    return failedImport("Src pattern results and dst MI defs are different");
-
   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
-    const auto &DstIOperand = DstI.Operands[OpIdx];
-    Record *DstIOpRec = DstIOperand.Rec;
-    if (!DstIOpRec->isSubClassOf("RegisterClass"))
-      return failedImport("Dst MI def isn't a register class");
-
     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
+
     if (!OpTyOrNone)
-      return failedImport("Dst operand has an unsupported type");
+      return failedImport(
+          "Result of Src pattern operator has an unsupported type");
 
-    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, DstIOperand.Name);
+    // Results don't have a name unless they are the root node. The caller will
+    // set the name if appropriate.
+    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "");
     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
-    OM.addPredicate<RegisterBankOperandMatcher>(
-        Target.getRegisterClass(DstIOpRec));
-    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
-    ++OpIdx;
   }
 
-  // Finally match the used operands (i.e., the children of the root operator).
+  unsigned TempOpIdx = 0;
+  // Match the used operands (i.e. the children of the operator).
   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
-    auto *SrcChild = Src->getChild(i);
+    if (auto Error = importChildMatcher(InsnMatcher, Src->getChild(i), OpIdx++,
+                                        TempOpIdx)
+                         .takeError())
+      return std::move(Error);
+  }
 
-    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, SrcChild->getName());
+  return InsnMatcher;
+}
 
-    // The only non-leaf child we accept is 'bb': it's an operator because
-    // BasicBlockSDNode isn't inline, but in MI it's just another operand.
-    if (!SrcChild->isLeaf()) {
-      if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
-        auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
-        if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-          OM.addPredicate<MBBOperandMatcher>();
-          continue;
-        }
+Expected<bool>
+GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
+                                      TreePatternNode *SrcChild, unsigned OpIdx,
+                                      unsigned &TempOpIdx) const {
+  OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, SrcChild->getName());
+
+  if (SrcChild->hasAnyPredicate())
+    return failedImport("Src pattern child has predicate");
+
+  ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
+  if (ChildTypes.size() != 1)
+    return failedImport("Src pattern child has multiple results");
+
+  // Check MBB's before the type check since they are not a known type.
+        return true;
       }
-      return failedImport("Src pattern child isn't a leaf node or an MBB");
     }
 
-    if (SrcChild->hasAnyPredicate())
-      return failedImport("Src pattern child has predicate");
-
-    ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
-    if (ChildTypes.size() != 1)
-      return failedImport("Src pattern child has multiple results");
+    return failedImport("Src child operand is an unsupported type");
+  }
 
-    auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
-    if (!OpTyOrNone)
-      return failedImport("Src operand has an unsupported type");
-    OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
 
-    if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
-      OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
-      continue;
-    }
+  // Check for constant immediates.
+    return true;
 
-    if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
-      auto *ChildRec = ChildDefInit->getDef();
+  // Check for def's like register classes or ComplexPattern's.
 
-      if (ChildRec->isSubClassOf("RegisterClass")) {
-        OM.addPredicate<RegisterBankOperandMatcher>(
-            Target.getRegisterClass(ChildRec));
-        continue;
-      }
+    // Check for register classes.
+      return true;
 
-      if (ChildRec->isSubClassOf("ComplexPattern")) {
-        const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
-        if (ComplexPattern == ComplexPatternEquivs.end())
-          return failedImport(
-              "SelectionDAG ComplexPattern not mapped to GlobalISel");
+    // Check for ComplexPattern's.
 
-        const auto &Predicate = OM.addPredicate<ComplexPatternOperandMatcher>(
-            *ComplexPattern->second, TempOpIdx);
-        TempOpIdx += Predicate.countTemporaryOperands();
-        continue;
-      }
+      return true;
 
-      return failedImport(
-          "Src pattern child def is an unsupported tablegen class");
-    }
 
-    return failedImport("Src pattern child is an unsupported kind");
-  }
 
-  TempOpIdx = 0;
-  // Finally render the used operands (i.e., the children of the root operator).
-  for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) {
-    auto *DstChild = Dst->getChild(i);
-
-    // The only non-leaf child we accept is 'bb': it's an operator because
-    // BasicBlockSDNode isn't inline, but in MI it's just another operand.
-    if (!DstChild->isLeaf()) {
-      if (DstChild->getOperator()->isSubClassOf("SDNode")) {
-        auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
-        if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-          DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
-                                                 DstChild->getName());
-          continue;
-        }
-      }
-      return failedImport("Dst pattern child isn't a leaf node or an MBB");
-    }
+Expected<bool> GlobalISelEmitter::importExplicitUseRenderer(
+    BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
+    const InstructionMatcher &InsnMatcher, unsigned &TempOpIdx) const {
+        return true;
 
-    // Otherwise, we're looking for a bog-standard RegisterClass operand.
-    if (DstChild->hasAnyPredicate())
-      return failedImport("Dst pattern child has predicate");
 
-    if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
-      auto *ChildRec = ChildDefInit->getDef();
 
-      ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
-      if (ChildTypes.size() != 1)
-        return failedImport("Dst pattern child has multiple results");
 
-      auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
-      if (!OpTyOrNone)
-        return failedImport("Dst operand has an unsupported type");
 
-      if (ChildRec->isSubClassOf("Register")) {
-        DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
-        continue;
-      }
+      return true;
 
-      if (ChildRec->isSubClassOf("RegisterClass")) {
-        DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
-                                               DstChild->getName());
-        continue;
-      }
+      DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstChild->getName());
+      return true;
 
-      if (ChildRec->isSubClassOf("ComplexPattern")) {
-        const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
-        if (ComplexPattern == ComplexPatternEquivs.end())
-          return failedImport(
-              "SelectionDAG ComplexPattern not mapped to GlobalISel");
 
-        SmallVector<OperandPlaceholder, 2> RenderedOperands;
-        for (unsigned I = 0; I < InsnMatcher.getOperand(DstChild->getName())
-                                     .countTemporaryOperands();
-             ++I) {
-          RenderedOperands.push_back(OperandPlaceholder::CreateTemporary(I));
-          TempOpIdx++;
-        }
-        DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
-            *ComplexPattern->second,
-            RenderedOperands);
-        continue;
-      }
+      for (unsigned I = 0;
+           I <
+           InsnMatcher.getOperand(DstChild->getName()).countTemporaryOperands();
+          *ComplexPattern->second, RenderedOperands);
+      return true;
 
-      return failedImport(
-          "Dst pattern child def is an unsupported tablegen class");
-    }
 
-    return failedImport("Dst pattern child is an unsupported kind");
-  }
 
+Expected<BuildMIAction &> GlobalISelEmitter::importInstructionRenderer(
+    RuleMatcher &M, const TreePatternNode *Dst,
+    const InstructionMatcher &InsnMatcher) const {
+  Record *DstOp = Dst->getOperator();
+  if (!DstOp->isSubClassOf("Instruction"))
+    return failedImport("Pattern operator isn't an instruction");
+  auto &DstI = Target.getInstruction(DstOp);
+
+  auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
+
+  // Render the explicit defs.
+  for (unsigned I = 0; I < DstI.Operands.NumDefs; ++I) {
+    const auto &DstIOperand = DstI.Operands[I];
+    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
+  }
+
+  // Render the explicit uses.
+  unsigned TempOpIdx = 0;
+  for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) {
+    if (auto Error = importExplicitUseRenderer(DstMIBuilder, Dst->getChild(i),
+                                               InsnMatcher, TempOpIdx)
+                         .takeError())
+      return std::move(Error);
+  }
+
+  return DstMIBuilder;
+}
+
+Expected<bool> GlobalISelEmitter::importImplicitDefRenderers(
+    BuildMIAction &DstMIBuilder,
+    const std::vector<Record *> &ImplicitDefs) const {
+  if (!ImplicitDefs.empty())
+    return failedImport("Pattern defines a physical register");
+  return true;
+}
+
+Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
+  // Keep track of the matchers and actions to emit.
+  RuleMatcher M;
+  M.addAction<DebugCommentAction>(P);
+
+  if (auto Error =
+          importRulePredicates(M, P.getPredicates()->getValues()).takeError())
+    return std::move(Error);
+
+  // Next, analyze the pattern operators.
+  TreePatternNode *Src = P.getSrcPattern();
+  TreePatternNode *Dst = P.getDstPattern();
+
+  // If the root of either pattern isn't a simple operator, ignore it.
+  if (!isTrivialOperatorNode(Dst))
+    return failedImport("Dst pattern root isn't a trivial operator");
+  if (!isTrivialOperatorNode(Src))
+    return failedImport("Src pattern root isn't a trivial operator");
+
+  Record *DstOp = Dst->getOperator();
+  if (!DstOp->isSubClassOf("Instruction"))
+    return failedImport("Pattern operator isn't an instruction");
+
+  auto &DstI = Target.getInstruction(DstOp);
+  if (DstI.Operands.NumDefs != Src->getExtTypes().size())
+    return failedImport("Src pattern results and dst MI defs are different");
+
+  InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
+  auto InsnMatcherOrError = importSelDAGMatcher(InsnMatcherTemp, Src);
+  if (auto Error = InsnMatcherOrError.takeError())
+    return std::move(Error);
+  InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
+
+  // The root of the match also has constraints on the register bank so that it
+  // matches the result instruction.
+  unsigned OpIdx = 0;
+  for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
+    (void)Ty;
+
+    const auto &DstIOperand = DstI.Operands[OpIdx];
+    Record *DstIOpRec = DstIOperand.Rec;
+    if (!DstIOpRec->isSubClassOf("RegisterClass"))
+      return failedImport("Dst MI def isn't a register class");
+
+    OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
+    OM.setSymbolicName(DstIOperand.Name);
+    OM.addPredicate<RegisterBankOperandMatcher>(
+        Target.getRegisterClass(DstIOpRec));
+    ++OpIdx;
+  }
+
+  auto DstMIBuilderOrError = importInstructionRenderer(M, Dst, InsnMatcher);
+  if (auto Error = DstMIBuilderOrError.takeError())
+    return std::move(Error);
+  BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
+
+  // Render the implicit defs.
+  // These are only added to the root of the result.
+  if (auto Error =
+          importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()).takeError())
+    return std::move(Error);
+
   // 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();