[GlobalIsSel] Allow using PatFrags with multiple defs as the root of a combine rule

[Pierre-vh]

Summary

I had to tighten the restrictions on PatFrags a bit to make it consistent: instructions that
define the root of a PF can only have one def.

[Pierre-vh]

Document the new limitation

[foad]

llvm/include/llvm/Target/GlobalISel/Combine.td

163

This may be a silly question since I am not too familiar with PatFrags, and have no idea how they are implemented:

Why does a PatFrag like this have two defs, instead of one use and one def?

[Pierre-vh]

llvm/include/llvm/Target/GlobalISel/Combine.td

163

It's actually a design point I've been struggling with for a while, and the current iteration I've settled on (and that makes the most sense to me) is:

• out operands are defined by some instruction in all alternatives of the PatFrag, they can only be machine operands
• in operands are never defined by the patterns, they can be machine operands or immediates

Here the PatFrag defines $src so it's an out operand. If we wanted to also access $x that'd be an in operand because it's not defined by any instruction

Having $srrc as an out avoids having 2 defs that contradict each other, making the pattern impossible to match.

Another option could also be to always have a single def (the root) and just error when an inst is accidentally def'd twice with something like error: impossible pattern or something. Both have their pros and cons

[arsenm]

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td

266

It's somewhat confusing all the defs go to the right of the opcode name unlike in the actual mir

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

816

this could just return an ArrayRef?

[Pierre-vh]

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td

266

I agree, but not sure if we have an alternative unless we want to use something ugly like (pattern $foo, $z, G_UNMERGE_VALUES $y) everywhere because ($foo doesn't work I think?

I'm open to suggestions if you have a proposal with a better syntax, but IMO I think it's fine as-is. It's a small quirk of TableGen we have to deal with and unless we want to add some new TableGen syntax for infix/postfix operators, or parse MIR strings, we have to work with this

[Pierre-vh]

Use ArrayRef

llvm/docs/GlobalISel/MIRPatterns.rst

 Limitations
 -----------
 
 This a non-exhaustive list of known issues with MIR patterns at this time.
 
 * Matching intrinsics is not yet possible.
 * Using ``GICombinePatFrag`` within another ``GICombinePatFrag`` is not
   supported.
+* ``GICombinePatFrag`` can only have a single root.
+* Instructions with multiple defs cannot be the root of a ``GICombinePatFrag``.
 * Using ``GICombinePatFrag`` in the ``apply`` pattern of a ``GICombineRule``
   is not supported.
 * Deleting the matched pattern in a ``GICombineRule`` needs to be done using
   ``G_IMPLICIT_DEF`` or C++.
 * Replacing the root of a pattern with another instruction needs to be done
   using COPY.
 * We cannot rewrite a matched instruction other than the root.
 * Matching/creating a (CImm) immediate >64 bits is not supported

llvm/include/llvm/Target/GlobalISel/Combine.td

def copy_prop : GICombineRule<
   (match (COPY $d, $s):$mi,
          [{ return Helper.matchCombineCopy(*${mi}); }]),
   (apply [{ Helper.applyCombineCopy(*${mi}); }])>;
 
 // idempotent operations
 // Fold (freeze (freeze x)) -> (freeze x).
 // Fold (fabs (fabs x)) -> (fabs x).
 // Fold (fcanonicalize (fcanonicalize x)) -> (fcanonicalize x).
+def idempotent_prop_frags : GICombinePatFrag<
+  (outs root:$dst, $src), (ins),
+  !foreach(op, [G_FREEZE, G_FABS, G_FCANONICALIZE],
+           (pattern (op $dst, $src), (op $src, $x)))>;
+
 def idempotent_prop : GICombineRule<
-   (defs root:$mi),
-   (match (wip_match_opcode G_FREEZE, G_FABS, G_FCANONICALIZE):$mi,
-          [{ return MRI.getVRegDef(${mi}->getOperand(1).getReg())->getOpcode() ==
-                    ${mi}->getOpcode(); }]),
-   (apply [{ Helper.replaceSingleDefInstWithOperand(*${mi}, 1); }])>;
+   (defs root:$dst),
+   (match (idempotent_prop_frags $dst, $src)),
+   (apply (COPY $dst, $src))>;
 
 
 def extending_loads : GICombineRule<
   (defs root:$root, extending_load_matchdata:$matchinfo),
   (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD):$root,
          [{ return Helper.matchCombineExtendingLoads(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyCombineExtendingLoads(*${root}, ${matchinfo}); }])>;
 

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/patfrag-errors.td

 // CHECK: :[[@LINE+3]]:{{[0-9]+}}: warning: impossible type constraints: operand 1 of 'broken' has type 'i64', but 'TypedParams' constrains it to 'i32'
 // CHECK: :[[@LINE+2]]:{{[0-9]+}}: note: operand 1 of 'broken' is 'k'
 // CHECK: :[[@LINE+1]]:{{[0-9]+}}: note: argument 1 of 'TypedParams' is 'i'
 def inconsistent_arg_type : GICombineRule<
   (defs root:$dst),
   (match (TypedParams $dst, i64:$k):$broken),
   (apply (COPY $dst, (i32 0)))>;
 
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: all instructions that define root 'foo' in 'RootDefHasMultiDefs' can only have a single output operand
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Could not parse GICombinePatFrag 'RootDefHasMultiDefs'
+def RootDefHasMultiDefs: GICombinePatFrag<
+    (outs root:$foo),
+    (ins gi_imm:$cst),
+    [
+      (pattern (G_UNMERGE_VALUES $foo, $z, $y))
+    ]>;
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Failed to parse pattern: '(RootDefHasMultiDefs ?:$root, (i32 10))'
+def root_def_has_multi_defs : GICombineRule<
+  (defs root:$root),
+  (match (RootDefHasMultiDefs $root, (i32 10))),
+  (apply (COPY $root, (i32 0)))>;
+
 // CHECK: error: Failed to parse one or more rules
 
 def MyCombiner: GICombinerHelper<"GenMyCombiner", [
   too_many_perms,
   undef_livein,
   out_must_be_root,
   bad_out_type,
   unreachable_pat,
   wip_match_opcode_patfrag,
   nest_pat_frag,
   dup_params_in,
   dup_params_out,
   dup_params_inout,
   def_by_all_alts,
   multi_def_in_pat,
   expected_imm,
   expected_imm_namedimm,
   expected_mo,
   expected_mo_namedimm,
   patfrag_in_apply,
   patfrag_cannot_be_root,
-  inconsistent_arg_type
+  inconsistent_arg_type,
+  root_def_has_multi_defs
 ]>;

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-errors.td

def cannot_def_match_livein : GICombineRule<
   (apply (COPY $a, $b), (COPY $b, $b))>;
 
 // CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: invalid output operand 'x': operand is not a live-in of the match pattern, and it has no definition
 def undef_in_apply : GICombineRule<
   (defs root:$d),
   (match (COPY $a, $b):$d),
   (apply (COPY $a, $x))>;
 
-// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: def of pattern root 'a' is not redefined in the apply pattern!
-// CHECK: :[[@LINE+1]]:{{[0-9]+}}: note: match pattern root is 'foo'
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: 'a' must be redefined in the 'apply' pattern
 def no_redef_in_apply : GICombineRule<
   (defs root:$a),
   (match (COPY $a, $b):$foo),
   (apply (COPY $x, $b))>;
 
-// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error:  def of pattern root 'b' is not redefined in the apply pattern!
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: 'b' must be redefined in the 'apply' pattern
 def no_redef_in_apply_multidefroot : GICombineRule<
   (defs root:$a),
   (match (G_UNMERGE_VALUES $a, $b, $c)),
   (apply (COPY $a, $c))>;
 
 // CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: cannot use wip_match_opcode in combination with apply instruction patterns
 def instpat_with_wipmatch : GICombineRule<
   (defs root:$a),

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

public:
   }
 
   auto &operands() { return Operands; }
   const auto &operands() const { return Operands; }
   unsigned operands_size() const { return Operands.size(); }
   InstructionOperand &getOperand(unsigned K) { return Operands[K]; }
   const InstructionOperand &getOperand(unsigned K) const { return Operands[K]; }
 
+  /// When this InstructionPattern is used as the match root, returns the
+  /// operands that must be redefined in the 'apply' pattern for the rule to be
+  /// valid.
+  ///
+  /// For CodeGenInstructionPatterns, this just returns the defs of the CGI.
+  /// For PatFrag this only returns the root of the PF.
+  ///
+  /// Returns an empty array on error.
+  virtual ArrayRef<InstructionOperand> getApplyDefsNeeded() const = 0;
+
   auto named_operands() {
     return make_filter_range(Operands,
                              [&](auto &O) { return O.isNamedOperand(); });
   }
 
   auto named_operands() const {
     return make_filter_range(Operands,
                              [&](auto &O) { return O.isNamedOperand(); });
bool is(StringRef OpcodeName) const {
     return I.TheDef->getName() == OpcodeName;
   }
 
   bool hasVariadicDefs() const;
   bool isVariadic() const override { return I.Operands.isVariadic; }
   unsigned getNumInstDefs() const override;
   unsigned getNumInstOperands() const override;
 
+  ArrayRef<InstructionOperand> getApplyDefsNeeded() const override;
+
   const CodeGenInstruction &getInst() const { return I; }
   StringRef getInstName() const override { return I.TheDef->getName(); }
 
 private:
   const CodeGenInstruction &I;
 };
 
 bool CodeGenInstructionPattern::hasVariadicDefs() const {

 }
 
 unsigned CodeGenInstructionPattern::getNumInstOperands() const {
   unsigned NumCGIOps = I.Operands.size();
   return isVariadic() ? std::max<unsigned>(NumCGIOps, Operands.size())
                       : NumCGIOps;
 }
 
+ArrayRef<InstructionOperand>
+CodeGenInstructionPattern::getApplyDefsNeeded() const {
+  return {operands().begin(), getNumInstDefs()};
+}
+
 //===- OperandTypeChecker -------------------------------------------------===//
 
 /// This is a trivial type checker for all operands in a set of
 /// InstructionPatterns.
 ///
 /// It infers the type of each operand, check it's consistent with the known
 /// type of the operand, and then sets all of the types in all operands in
 /// setAllOperandTypes.
for (const auto &Op : out_params()) {
 
     if (SeenOps.count(Op.Name)) {
       PrintError("duplicate parameter '" + Op.Name + "'");
       return false;
     }
 
     // Check this operand is defined in all alternative's patterns.
     for (const auto &Alt : Alts) {
-      if (!Alt.OpTable.getDef(Op.Name)) {
+      const auto *OpDef = Alt.OpTable.getDef(Op.Name);
+      if (!OpDef) {
         PrintError("output parameter '" + Op.Name +
                    "' must be defined by all alternative patterns in '" +
                    Def.getName() + "'");
         return false;
       }
+
+      if (Op.Kind == PK_Root && OpDef->getNumInstDefs() != 1) {
+        // The instruction that defines the root must have a single def.
+        // Otherwise we'd need to support multiple roots and it gets messy.
+        //
+        // e.g. this is not supported:
+        //   (pattern (G_UNMERGE_VALUES $x, $root, $vec))
+        PrintError("all instructions that define root '" + Op.Name + "' in '" +
+                   Def.getName() + "' can only have a single output operand");
+        return false;
+      }
     }
 
     SeenOps.insert(Op.Name);
   }
 
   if (num_out_params() != 0 && num_roots() == 0) {
     PrintError(PatFragClassName + " must have one root in its 'out' operands");
     return false;
public:
   static bool classof(const Pattern *P) { return P->getKind() == K_PatFrag; }
 
   const PatFrag &getPatFrag() const { return PF; }
   StringRef getInstName() const override { return PF.getName(); }
 
   unsigned getNumInstDefs() const override { return PF.num_out_params(); }
   unsigned getNumInstOperands() const override { return PF.num_params(); }
 
+  ArrayRef<InstructionOperand> getApplyDefsNeeded() const override;
+
   bool checkSemantics(ArrayRef<SMLoc> DiagLoc) override;
 
   /// Before emitting the patterns inside the PatFrag, add all necessary code
   /// expansions to \p PatFragCEs imported from \p ParentCEs.
   ///
   /// For a MachineOperand PatFrag parameter, this will fetch the expansion for
   /// that operand from \p ParentCEs and add it to \p PatFragCEs. Errors can be
   /// emitted if the MachineOperand reference is unbound.
public:
   bool mapInputCodeExpansions(const CodeExpansions &ParentCEs,
                               CodeExpansions &PatFragCEs,
                               ArrayRef<SMLoc> DiagLoc) const;
 
 private:
   const PatFrag &PF;
 };
 
+ArrayRef<InstructionOperand> PatFragPattern::getApplyDefsNeeded() const {
+  assert(PF.num_roots() == 1);
+  // Only roots need to be redef.
+  for (auto [Idx, Param] : enumerate(PF.out_params())) {
+    if (Param.Kind == PatFrag::PK_Root)
+      return getOperand(Idx);
+  }
+  llvm_unreachable("root not found!");
+}
+
 bool PatFragPattern::checkSemantics(ArrayRef<SMLoc> DiagLoc) {
   if (!InstructionPattern::checkSemantics(DiagLoc))
     return false;
 
   for (const auto &[Idx, Op] : enumerate(Operands)) {
     switch (PF.getParam(Idx).Kind) {
     case PatFrag::PK_Imm:
       if (!Op.hasImmValue()) {
if (IPRoot->getNumInstDefs() == 0) {
       }
 
       ApplyRoots.insert(ApplyRoot);
       return true;
     }
 
     // Collect all redefinitions of the MatchRoot's defs and put them in
     // ApplyRoots.
-    for (unsigned K = 0; K < IPRoot->getNumInstDefs(); ++K) {
-      auto &O = IPRoot->getOperand(K);
-      assert(O.isDef() && O.isNamedOperand());
-      StringRef Name = O.getOperandName();
+    const auto DefsNeeded = IPRoot->getApplyDefsNeeded();
+    for (auto &Op : DefsNeeded) {
+      assert(Op.isDef() && Op.isNamedOperand());
+      StringRef Name = Op.getOperandName();
 
       auto *ApplyRedef = ApplyOpTable.getDef(Name);
       if (!ApplyRedef) {
-        PrintError("def of pattern root '" + Name +
-                   "' is not redefined in the apply pattern!");
-        PrintNote("match pattern root is '" + MatchRoot->getName() + "'");
+        PrintError("'" + Name + "' must be redefined in the 'apply' pattern");
         return false;
       }
 
       ApplyRoots.insert((InstructionPattern *)ApplyRedef);
     }
 
     if (auto It = ApplyPats.find(RootName); It != ApplyPats.end()) {
       if (find(ApplyRoots, It->second.get()) == ApplyRoots.end()) {