[globalisel] Decouple src pattern operands from dst pattern operands.

Summary:
This isn't testable for AArch64 by itself so this patch also adds
support for constant immediates in the pattern and physical
register uses in the result.

The new IntOperandMatcher matches the constant in patterns such as
'(set $rd:GPR32, (G_XOR $rs:GPR32, -1))'. It's always safe to fold
immediates into an instruction so this is the first rule that will match
across multiple BB's.

The Renderer hierarchy is responsible for adding operands to the result
instruction. Renderers can copy operands (CopyRenderer) or add physical
registers (in particular %wzr and %xzr) to the result instruction
in any order (OperandMatchers now import the operand names from
SelectionDAG to allow renderers to access any operand). This allows us to
emit the result instruction for:
  %1 = G_XOR %0, -1 --> %1 = ORNWrr %wzr, %0
  %1 = G_XOR -1, %0 --> %1 = ORNWrr %wzr, %0
although the latter is untested since the matcher/importer has not been
taught about commutativity yet.

Added BuildMIAction which can build new instructions and mutate them where
possible. W.r.t the mutation aspect, MatchActions are now told the name of
an instruction they can recycle and BuildMIAction will emit mutation code
when the renderers are appropriate. They are appropriate when all operands
are rendered using CopyRenderer and the indices are the same as the matcher.
This currently assumes that all operands have at least one matcher.

Finally, this change also fixes a crash in
AArch64InstructionSelector::select() caused by an immediate operand
passing isImm() rather than isCImm(). This was uncovered by the other
changes and was detected by existing tests.

Depends on D29711

Reviewers: t.p.northover, ab, qcolombet, rovka, aditya_nandakumar, javed.absar

Reviewed By: rovka

Subscribers: aemerson, dberris, kristof.beyls, llvm-commits

Differential Revision: https://reviews.llvm.org/D29712

llvm-svn: 296131

1 files changed, 282 insertions, 53 deletions

diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index 37fa5738fdd..409511b7265 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -56,8 +56,6 @@ static cl::opt<bool> WarnOnSkippedPatterns(
              "in the GlobalISel selector"),
     cl::init(false));
 
-namespace {
-
 //===- Helper functions ---------------------------------------------------===//
 
 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
@@ -135,8 +133,11 @@ public:
   /// the predicate when generating the matcher code. Kinds with higher priority
   /// must be tested first.
   ///
-  /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter.
+  /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
+  /// but OPM_Int must have priority over OPM_RegBank since constant integers
+  /// are represented by a virtual register defined by a G_CONSTANT instruction.
   enum PredicateKind {
+    OPM_Int,
     OPM_LLT,
     OPM_RegBank,
     OPM_MBB,
@@ -158,8 +159,8 @@ public:
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
-  virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) {
-    return false;
+  virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
+    return Kind < B.Kind;
   };
 };
 
@@ -218,22 +219,53 @@ public:
   }
 };
 
+/// Generates code to check that an operand is a particular int.
+class IntOperandMatcher : public OperandPredicateMatcher {
+protected:
+  int64_t Value;
+
+public:
+  IntOperandMatcher(int64_t Value)
+      : OperandPredicateMatcher(OPM_Int), Value(Value) {}
+
+  static bool classof(const OperandPredicateMatcher *P) {
+    return P->getKind() == OPM_Int;
+  }
+
+  void emitCxxPredicateExpr(raw_ostream &OS,
+                            const StringRef OperandExpr) const override {
+    OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)";
+  }
+};
+
 /// Generates code to check that a set of predicates match for a particular
 /// operand.
 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 protected:
   unsigned OpIdx;
+  std::string SymbolicName;
 
 public:
-  OperandMatcher(unsigned OpIdx) : OpIdx(OpIdx) {}
-  std::string getOperandExpr(StringRef InsnVarName) const {
+  OperandMatcher(unsigned OpIdx, const std::string &SymbolicName)
+      : OpIdx(OpIdx), SymbolicName(SymbolicName) {}
+
+  bool hasSymbolicName() const { return !SymbolicName.empty(); }
+  const StringRef getSymbolicName() const { return SymbolicName; }
+  unsigned getOperandIndex() const { return OpIdx; }
+
+  std::string getOperandExpr(const StringRef InsnVarName) const {
     return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
   }
 
   /// Emit a C++ expression that tests whether the instruction named in
   /// InsnVarName matches all the predicate and all the operands.
-  void emitCxxPredicateExpr(raw_ostream &OS, StringRef InsnVarName) const {
-    OS << "(/* Operand " << OpIdx << " */ ";
+  void emitCxxPredicateExpr(raw_ostream &OS, const StringRef InsnVarName) const {
+    OS << "(/* ";
+    if (SymbolicName.empty())
+      OS << "Operand " << OpIdx;
+    else
+      OS << SymbolicName;
+    OS << " */ ";
     emitCxxPredicateListExpr(OS, getOperandExpr(InsnVarName));
     OS << ")";
   }
@@ -290,7 +322,7 @@ public:
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
-  bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
+  virtual bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
     return Kind < B.Kind;
   };
 };
@@ -316,8 +348,8 @@ public:
 
   /// Compare the priority of this object and B.
   ///
-  /// Returns true if  is more important than B.
-  bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
+  /// Returns true if this object is more important than B.
+  bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
       return true;
     if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this))
@@ -343,15 +375,41 @@ public:
 class InstructionMatcher
     : public PredicateListMatcher<InstructionPredicateMatcher> {
 protected:
-  std::vector<OperandMatcher> Operands;
+  typedef std::vector<OperandMatcher> OperandVec;
+
+  /// The operands to match. All rendered operands must be present even if the
+  /// condition is always true.
+  OperandVec Operands;
 
 public:
   /// Add an operand to the matcher.
-  OperandMatcher &addOperand(unsigned OpIdx) {
-    Operands.emplace_back(OpIdx);
+  OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName) {
+    Operands.emplace_back(OpIdx, SymbolicName);
     return Operands.back();
   }
 
+  const OperandMatcher &getOperand(const 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;
+    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();
+  }
+  iterator_range<OperandVec::const_iterator> operands() const {
+    return make_range(operands_begin(), operands_end());
+  }
+
   /// Emit a C++ expression that tests whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
   void emitCxxPredicateExpr(raw_ostream &OS, StringRef InsnVarName) const {
@@ -393,6 +451,75 @@ public:
 
 //===- Actions ------------------------------------------------------------===//
 
+namespace {
+class OperandRenderer {
+public:
+  enum RendererKind { OR_Copy, OR_Register };
+
+protected:
+  RendererKind Kind;
+
+public:
+  OperandRenderer(RendererKind Kind) : Kind(Kind) {}
+  virtual ~OperandRenderer() {}
+
+  RendererKind getKind() const { return Kind; }
+
+  virtual void emitCxxRenderStmts(raw_ostream &OS) const = 0;
+};
+
+/// A CopyRenderer emits code to copy a single operand from an existing
+/// instruction to the one being built.
+class CopyRenderer : public OperandRenderer {
+protected:
+  /// The matcher for the instruction that this operand is copied from.
+  /// This provides the facility for looking up an a operand by it's name so
+  /// that it can be used as a source for the instruction being built.
+  const InstructionMatcher &Matched;
+  /// The name of the instruction to copy from.
+  const StringRef InsnVarName;
+  /// The name of the operand.
+  const StringRef SymbolicName;
+
+public:
+  CopyRenderer(const InstructionMatcher &Matched, const StringRef InsnVarName,
+               const StringRef SymbolicName)
+      : OperandRenderer(OR_Copy), Matched(Matched), InsnVarName(InsnVarName),
+        SymbolicName(SymbolicName) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_Copy;
+  }
+
+  const StringRef getSymbolicName() const { return SymbolicName; }
+
+  void emitCxxRenderStmts(raw_ostream &OS) const override {
+    std::string OperandExpr =
+        Matched.getOperand(SymbolicName).getOperandExpr(InsnVarName);
+    OS << "    MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n";
+  }
+};
+
+/// Adds a specific physical register to the instruction being built.
+/// This is typically useful for WZR/XZR on AArch64.
+class AddRegisterRenderer : public OperandRenderer {
+protected:
+  const Record *RegisterDef;
+
+public:
+  AddRegisterRenderer(const Record *RegisterDef)
+      : OperandRenderer(OR_Register), RegisterDef(RegisterDef) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_Register;
+  }
+
+  void emitCxxRenderStmts(raw_ostream &OS) const override {
+    OS << "    MIB.addReg(" << RegisterDef->getValueAsString("Namespace")
+       << "::" << RegisterDef->getName() << ");\n";
+  }
+};
+
 /// An action taken when all Matcher predicates succeeded for a parent rule.
 ///
 /// Typical actions include:
@@ -401,7 +528,14 @@ public:
 class MatchAction {
 public:
   virtual ~MatchAction() {}
-  virtual void emitCxxActionStmts(raw_ostream &OS) const = 0;
+
+  /// Emit the C++ statements to implement the action.
+  ///
+  /// \param InsnVarName If given, it's an instruction to recycle. The
+  ///                    requirements on the instruction vary from action to
+  ///                    action.
+  virtual void emitCxxActionStmts(raw_ostream &OS,
+                                  const StringRef InsnVarName) const = 0;
 };
 
 /// Generates a comment describing the matched rule being acted upon.
@@ -412,23 +546,65 @@ private:
 public:
   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 
-  virtual void emitCxxActionStmts(raw_ostream &OS) const {
+  void emitCxxActionStmts(raw_ostream &OS,
+                          const StringRef InsnVarName) const override {
     OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern();
   }
 };
 
-/// Generates code to set the opcode (really, the MCInstrDesc) of a matched
-/// instruction to a given Instruction.
-class MutateOpcodeAction : public MatchAction {
+/// Generates code to build an instruction or mutate an existing instruction
+/// into the desired instruction when this is possible.
+class BuildMIAction : public MatchAction {
 private:
   const CodeGenInstruction *I;
+  const InstructionMatcher &Matched;
+  std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
+
+  /// True if the instruction can be built solely by mutating the opcode.
+  bool canMutate() const {
+    for (const auto &Renderer : enumerate(OperandRenderers)) {
+      if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.Value)) {
+        if (Matched.getOperand(Copy->getSymbolicName()).getOperandIndex() !=
+            Renderer.Index)
+          return false;
+      } else
+        return false;
+    }
+
+    return true;
+  }
 
 public:
-  MutateOpcodeAction(const CodeGenInstruction *I) : I(I) {}
+  BuildMIAction(const CodeGenInstruction *I, const InstructionMatcher &Matched)
+      : I(I), Matched(Matched) {}
+
+  template <class Kind, class... Args>
+  Kind &addRenderer(Args&&... args) {
+    OperandRenderers.emplace_back(
+        llvm::make_unique<Kind>(std::forward<Args>(args)...));
+    return *static_cast<Kind *>(OperandRenderers.back().get());
+  }
+
+  virtual void emitCxxActionStmts(raw_ostream &OS,
+                                  const StringRef InsnVarName) const {
+    if (canMutate()) {
+      OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
+         << "));\n";
+      OS << "    MachineInstr &NewI = I;\n";
+      return;
+    }
 
-  virtual void emitCxxActionStmts(raw_ostream &OS) const {
-    OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
-       << "));";
+    // TODO: Simple permutation looks like it could be almost as common as
+    //       mutation due to commutative operations.
+
+    OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
+          "I.getDebugLoc(), TII.get("
+       << I->Namespace << "::" << I->TheDef->getName() << "));\n";
+    for (const auto &Renderer : OperandRenderers)
+      Renderer->emitCxxRenderStmts(OS);
+    OS << "    MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());\n";
+    OS << "    " << InsnVarName << ".eraseFromParent();\n";
+    OS << "    MachineInstr &NewI = *MIB;\n";
   }
 };
 
@@ -478,11 +654,11 @@ public:
 
     for (const auto &MA : Actions) {
       OS << "    ";
-      MA->emitCxxActionStmts(OS);
+      MA->emitCxxActionStmts(OS, "I");
       OS << "\n";
     }
 
-    OS << "    constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n";
+    OS << "    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n";
     OS << "    return true;\n";
     OS << "  }\n\n";
   }
@@ -591,7 +767,7 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   // The operators look good: match the opcode and mutate it to the new one.
   InstructionMatcher &InsnMatcher = M.addInstructionMatcher();
   InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
-  M.addAction<MutateOpcodeAction>(&DstI);
+  auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
 
   // Next, analyze the children, only accepting patterns that don't require
   // any change to operands.
@@ -605,7 +781,8 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
     return failedImport("Src pattern results and dst MI defs are different");
 
   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
-    Record *DstIOpRec = DstI.Operands[OpIdx].Rec;
+    const auto &DstIOperand = DstI.Operands[OpIdx];
+    Record *DstIOpRec = DstIOperand.Rec;
     if (!DstIOpRec->isSubClassOf("RegisterClass"))
       return failedImport("Dst MI def isn't a register class");
 
@@ -613,48 +790,35 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
     if (!OpTyOrNone)
       return failedImport("Dst operand has an unsupported type");
 
-    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx);
+    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, DstIOperand.Name);
     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
     OM.addPredicate<RegisterBankOperandMatcher>(
         Target.getRegisterClass(DstIOpRec));
+    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I", DstIOperand.Name);
     ++OpIdx;
   }
 
   // Finally match the used operands (i.e., the children of the root operator).
   for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
     auto *SrcChild = Src->getChild(i);
-    auto *DstChild = Dst->getChild(i);
 
-    // Patterns can reorder operands.  Ignore those for now.
-    if (SrcChild->getName() != DstChild->getName())
-      return failedImport("Src/dst pattern children not in same order");
+    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, SrcChild->getName());
 
     // 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 (DstChild->isLeaf() ||
-          SrcChild->getOperator() != DstChild->getOperator())
-        return failedImport("Src/dst pattern child operator mismatch");
-
       if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
         auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
         if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-          InsnMatcher.addOperand(OpIdx++).addPredicate<MBBOperandMatcher>();
+          OM.addPredicate<MBBOperandMatcher>();
           continue;
         }
       }
-      return failedImport("Src pattern child isn't a leaf node");
+      return failedImport("Src pattern child isn't a leaf node or an MBB");
     }
 
-    if (SrcChild->getLeafValue() != DstChild->getLeafValue())
-      return failedImport("Src/dst pattern child leaf mismatch");
-
-    // Otherwise, we're looking for a bog-standard RegisterClass operand.
     if (SrcChild->hasAnyPredicate())
       return failedImport("Src pattern child has predicate");
-    auto *ChildRec = cast<DefInit>(SrcChild->getLeafValue())->getDef();
-    if (!ChildRec->isSubClassOf("RegisterClass"))
-      return failedImport("Src pattern child isn't a RegisterClass");
 
     ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
     if (ChildTypes.size() != 1)
@@ -663,12 +827,77 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
     auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
     if (!OpTyOrNone)
       return failedImport("Src operand has an unsupported type");
-
-    OperandMatcher &OM = InsnMatcher.addOperand(OpIdx);
     OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
-    OM.addPredicate<RegisterBankOperandMatcher>(
-        Target.getRegisterClass(ChildRec));
-    ++OpIdx;
+
+    if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
+      OM.addPredicate<IntOperandMatcher>(ChildInt->getValue());
+      continue;
+    }
+
+    if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) {
+      auto *ChildRec = ChildDefInit->getDef();
+
+      // Otherwise, we're looking for a bog-standard RegisterClass operand.
+      if (!ChildRec->isSubClassOf("RegisterClass"))
+        return failedImport("Src pattern child isn't a RegisterClass");
+
+      OM.addPredicate<RegisterBankOperandMatcher>(
+          Target.getRegisterClass(ChildRec));
+      continue;
+    }
+
+    return failedImport("Src pattern child is an unsupported kind");
+  }
+
+  // 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, "I",
+                                                 DstChild->getName());
+          continue;
+        }
+      }
+      return failedImport("Dst pattern child isn't a leaf node or an MBB");
+    }
+
+    // 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;
+      }
+
+      if (ChildRec->isSubClassOf("RegisterClass")) {
+        DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, "I",
+                                               DstChild->getName());
+        continue;
+      }
+
+      return failedImport(
+          "Dst pattern child def is an unsupported tablegen class");
+    }
+
+    return failedImport("Src pattern child is an unsupported kind");
   }
 
   // We're done with this pattern!  It's eligible for GISel emission; return it.
@@ -709,8 +938,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
     Rules.push_back(std::move(MatcherOrErr.get()));
   }
 
-  std::sort(Rules.begin(), Rules.end(),
-            [](const RuleMatcher &A, const RuleMatcher &B) {
+  std::stable_sort(Rules.begin(), Rules.end(),
+            [&](const RuleMatcher &A, const RuleMatcher &B) {
               if (A.isHigherPriorityThan(B)) {
                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
                                                      "and less important at "