TableGen/GlobalISel: Partially fix nontrivial, custom predicates

[arsenm]

Summary

Currently custom code predicates can only really be used for
contextless checks tied to a single instruction (e.g. check the def
for hasOneUse). If you do want to inspect the input instructions in
the source pattern, you cannot without re-verifying the opcode and
type checks implied by the patterns, since this check was emitted
before any operand constraints. Really, these are pattern level
predicates that implicitly depend on the instruction and operand
checks.

Introduce a filtering function so the custom predicate is emitted
last. I'm not sure this is the most elegant solution. It seems like
this is really a different thing from the InstructionMatcher/IPM_
predicate kinds. I initially tried keeping this in a separate
predicate list, but that also seemed awkward.

This only half fixes the problem I'm trying to solve. The AMDGPU
pattern I'm attempting to port also uses the PredicateCodeUsesOperands
feature to allow checks on the source operands when the input pattern
is commuted. Really the emitter should reject the pattern since it
doesn't handle this case, but at this point it would be more
productive to just implement this.

[arsenm]

Drop leftover change

[paquette]

I can't think of any better way to do this off the top of my head.

Maybe @dsanders has some opinions here?

llvm/utils/TableGen/GlobalISelEmitter.cpp

1048

I think it's worth documenting what the filter functions are for in a comment here.

1050–1052

Probably worth documenting in a comment too.

[arsenm]

Add comments

[arsenm]

ping

[arsenm]

ping

[paquette]

I think this is fine. LGTM

[dsanders]

Yeah, there isn't really a better way to do it as there's no dependency tracking in the importer. GIMatchDAG can track exactly what needs to be available for the predicate to be testable (making it just an issue of how to represent that in the source) but we aren't using that in the importer.

[arsenm]

1254f6d5312cd4952e413cc11dd7c78a87d050b9

llvm/test/TableGen/GlobalISelEmitter.td

 //
 // R21C-NEXT:  GIM_Try, /*On fail goto*//*Label [[PREV_NUM:[0-9]+]]*/ [[PREV:[0-9]+]], // Rule ID 19 //
 // R21C-NOT:     GIR_Done,
 // R21C:         // GIR_Coverage, 19,
 // R21C-NEXT:    GIR_Done,
 // R21C-NEXT:  // Label [[PREV_NUM]]: @[[PREV]]
 // R21C-NEXT:  GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]], // Rule ID 21 //
 //
-// R21O-NEXT:    GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_frag,
 // R21O-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // R21O-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // R21N-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/4,
 // R21N-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
-// R21N-NEXT:    GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_frag,
 // R21N-NEXT:    // MIs[0] dst
 // R21N-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // R21N-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // R21N-NEXT:    // MIs[0] src1
 // R21N-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
 // R21N-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
 // R21N-NEXT:    // MIs[0] src2
 // R21N-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
 //
+// R21O-NEXT:    GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_frag,
 // R21C-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/2, /*Renderer*/0, GICP_gi_complex,
 // R21N-NEXT:    // MIs[0] src3
 // R21N-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/3, /*Type*/GILLT_s32,
 // R21C-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/3, /*Renderer*/1, GICP_gi_complex,
+// R21N-NEXT:    GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_frag,
 // R21C-NEXT:    // (select:{ *:[i32] } GPR32:{ *:[i32] }:$src1, complex:{ *:[i32] }:$src2, complex:{ *:[i32] }:$src3)<<P:Predicate_frag>> => (INSN2:{ *:[i32] } GPR32:{ *:[i32] }:$src1, complex:{ *:[i32] }:$src3, complex:{ *:[i32] }:$src2)
 
 // R21C-NEXT:    GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::INSN2,
 // R21C-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
 // R21C-NEXT:    GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src1
 // R21C-NEXT:    GIR_ComplexRenderer, /*InsnID*/0, /*RendererID*/1,
 // R21C-NEXT:    GIR_ComplexRenderer, /*InsnID*/0, /*RendererID*/0,
 // R21C-NEXT:    GIR_MergeMemOperands, /*InsnID*/0, /*MergeInsnID's*/0, GIU_MergeMemOperands_EndOfList,

llvm/test/TableGen/GlobalISelEmitterCustomPredicate.td

+// RUN: llvm-tblgen %s -gen-global-isel -optimize-match-table=false -I %p/../../include -I %p/Common -o - | FileCheck %s
+
+include "llvm/Target/Target.td"
+include "GlobalISelEmitterCommon.td"
+
+// Boilerplate code for setting up some registers with subregs.
+class MyReg<string n, list<Register> subregs = []>
+  : Register<n> {
+  let SubRegs = subregs;
+}
+
+class MyClass<int size, list<ValueType> types, dag registers>
+  : RegisterClass<"Test", types, size, registers> {
+  let Size = size;
+}
+
+def sub0 : SubRegIndex<16>;
+def sub1 : SubRegIndex<16, 16>;
+def S0 : MyReg<"s0">;
+def S1 : MyReg<"s1">;
+def SRegs : MyClass<16, [i16], (sequence "S%u", 0, 1)>;
+
+let SubRegIndices = [sub0, sub1] in {
+def D0 : MyReg<"d0", [S0, S1]>;
+}
+
+def DRegs : MyClass<32, [i32], (sequence "D%u", 0, 0)>;
+def DOP : RegisterOperand<DRegs>;
+def AND_OR : I<(outs DRegs:$dst), (ins DOP:$src0, DOP:$src1, DOP:$src2), []>;
+
+
+def or_oneuse : PatFrag<
+  (ops node:$x, node:$y),
+  (or node:$x, node:$y), [{ return foo(); }]> {
+  let GISelPredicateCode = [{
+    return MRI.hasOneNonDBGUse(MI.getOperand(0).getReg());
+  }];
+}
+
+
+// FIXME: GISelPredicateCode ignored if DAG predicate not set.
+def and_or_pat : PatFrag<
+  (ops node:$x, node:$y, node:$z),
+  (and (or node:$x, node:$y), node:$z), [{ return foo(); }]> {
+  let GISelPredicateCode = [{
+    return doesComplexCheck(MI);
+  }];
+}
+
+// CHECK: GIM_Try, /*On fail goto*//*Label 0*/ {{[0-9]+}}, // Rule ID 1 //
+// CHECK-NEXT: GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT: GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_AND,
+// CHECK-NEXT: // MIs[0] dst
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[0] Operand 1
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT: GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT: GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_OR,
+// CHECK-NEXT: // MIs[1] Operand 0
+// CHECK-NEXT:GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT: // MIs[1] src0
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/1, /*Op*/1, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[1] src1
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[0] src2
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_and_or_pat,
+// CHECK-NEXT: GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT: // (and:{ *:[i32] } (or:{ *:[i32] } DOP:{ *:[i32] }:$src0, DOP:{ *:[i32] }:$src1), DOP:{ *:[i32] }:$src2)<<P:Predicate_and_or_pat>>  =>  (AND_OR:{ *:[i32] } DOP:{ *:[i32] }:$src0, DOP:{ *:[i32] }:$src1, DOP:{ *:[i32] }:$src2)
+// CHECK-NEXT: GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::AND_OR,
+
+
+// CHECK: GIM_Try, /*On fail goto*//*Label 1*/ {{[0-9]+}}, // Rule ID 2 //
+// CHECK-NEXT: GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT: GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_AND,
+// CHECK-NEXT: // MIs[0] dst
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[0] src2
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[0] Operand 2
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/2, // MIs[1]
+// CHECK-NEXT: GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT: GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_OR,
+// CHECK-NEXT: // MIs[1] Operand 0
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT: // MIs[1] src0
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/1, /*Op*/1, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[1] src1
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_and_or_pat,
+// CHECK-NEXT: GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT: // (and:{ *:[i32] } DOP:{ *:[i32] }:$src2, (or:{ *:[i32] } DOP:{ *:[i32] }:$src0, DOP:{ *:[i32] }:$src1))<<P:Predicate_and_or_pat>>  =>  (AND_OR:{ *:[i32] } DOP:{ *:[i32] }:$src0, DOP:{ *:[i32] }:$src1, DOP:{ *:[i32] }:$src2)
+// CHECK-NEXT: GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::AND_OR,
+
+// Test commutative, standalone pattern.
+def : Pat<
+  (i32 (and_or_pat DOP:$src0, DOP:$src1, DOP:$src2)),
+  (AND_OR DOP:$src0, DOP:$src1, DOP:$src2)
+>;
+
+
+def sub3_pat : PatFrag<
+  (ops node:$x, node:$y, node:$z),
+  (sub (sub node:$x, node:$y), node:$z), [{ return foo(); }]> {
+  let GISelPredicateCode = [{
+    return doesComplexCheck(MI);
+  }];
+}
+
+// CHECK: GIM_Try, /*On fail goto*//*Label 2*/ {{[0-9]+}}, // Rule ID 0 //
+// CHECK-NEXT: GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT: GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// CHECK-NEXT: // MIs[0] dst
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/Test::DRegsRegClassID,
+// CHECK-NEXT: // MIs[0] Operand 1
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT: GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT: GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_SUB,
+// CHECK-NEXT: // MIs[1] Operand 0
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT: // MIs[1] src0
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT: // MIs[1] src1
+// CHECK-NEXT: GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT: // MIs[0] src2
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT: GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_sub3_pat,
+// CHECK-NEXT: GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT: // (sub:{ *:[i32] } (sub:{ *:[i32] } i32:{ *:[i32] }:$src0, i32:{ *:[i32] }:$src1), i32:{ *:[i32] }:$src2)<<P:Predicate_sub3_pat>>  =>  (SUB3:{ *:[i32] } i32:{ *:[i32] }:$src0, i32:{ *:[i32] }:$src1, i32:{ *:[i32] }:$src2)
+// CHECK-NEXT: GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::SUB3,
+
+// Test a non-commutative pattern.
+def SUB3 : I<(outs DRegs:$dst),
+  (ins DOP:$src0, DOP:$src1, DOP:$src2),
+  [(set DRegs:$dst, (sub3_pat i32:$src0, i32:$src1, i32:$src2))]
+>;

llvm/test/TableGen/GlobalISelEmitterOverloadedPtr.td

 // RUN: llvm-tblgen -gen-global-isel -I %p/../../include -I %p/Common %s -o - | FileCheck %s
 
 // Boilerplate code.
 include "llvm/Target/Target.td"
 include "GlobalISelEmitterCommon.td"
 
 let TargetPrefix = "mytarget" in {
     def int_mytarget_anyptr : Intrinsic<[llvm_i32_ty], [llvm_anyptr_ty]>;
 }
 
 // Ensure that llvm_anyptr_ty on an intrinsic results in a
 // GIM_CheckPointerToAny rather than a GIM_CheckType.
 //
-// CHECK: GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_frag_anyptr,
+// CHECK: GIM_CheckIntrinsicID, /*MI*/0, /*Op*/1, Intrinsic::mytarget_anyptr,
+// CHECK-NEXT: GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
 // CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
 // CHECK-NEXT: // MIs[0] src
 // CHECK-NEXT: GIM_CheckPointerToAny, /*MI*/0, /*Op*/2, /*SizeInBits*/32,
 // CHECK-NEXT: GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT: GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GIPFP_MI_Predicate_frag_anyptr,
 // CHECK-NEXT: // (intrinsic_w_chain:{ *:[i32] } {{[0-9]+}}:{ *:[iPTR] }, GPR32:{ *:[i32] }:$src)<<P:Predicate_frag_anyptr>>  =>  (ANYLOAD:{ *:[i32] } GPR32:{ *:[i32] }:$src)
 // CHECK-NEXT: GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::ANYLOAD,
 let hasSideEffects = 1 in {
   def ANYLOAD : I<(outs GPR32:$dst), (ins GPR32:$src1),
             [(set GPR32:$dst, (load GPR32:$src1))]>;
 }
 
 def frag_anyptr : PatFrag<(ops node:$src),
                    (int_mytarget_anyptr node:$src),
                    [{ return true; // C++ code }]> {
   let GISelPredicateCode = [{ return true; // C++ code }];
 }
 
 def : Pat<(frag_anyptr GPR32:$src),
           (p0 (ANYLOAD GPR32:$src))>;

llvm/utils/TableGen/GlobalISelEmitter.cpp

if (Predicates.empty() && !Optimized) {
       Table << MatchTable::Comment(getNoPredicateComment())
             << MatchTable::LineBreak;
       return;
     }
 
     for (const auto &Predicate : predicates())
       Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
   }
+
+  /// Provide a function to avoid emitting certain predicates. This is used to
+  /// defer some predicate checks until after others
+  using PredicateFilterFunc = std::function<bool(const PredicateTy&)>;
+
+  /// Emit MatchTable opcodes for predicates which satisfy \p
+  /// ShouldEmitPredicate. This should be called multiple times to ensure all
+  /// predicates are eventually added to the match table.
+  template <class... Args>
+  void emitFilteredPredicateListOpcodes(PredicateFilterFunc ShouldEmitPredicate,
+                                        MatchTable &Table, Args &&... args) {
+    if (Predicates.empty() && !Optimized) {
+      Table << MatchTable::Comment(getNoPredicateComment())
+            << MatchTable::LineBreak;
+      return;
+    }
+
+    for (const auto &Predicate : predicates()) {
+      if (ShouldEmitPredicate(*Predicate))
+        Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
+    }
+  }
 };
 
 class PredicateMatcher {
 public:
   /// This enum is used for RTTI and also defines the priority that is given to
   /// the predicate when generating the matcher code. Kinds with higher priority
   /// must be tested first.
   ///
public:
 
   virtual ~PredicateMatcher() = default;
   /// Emit MatchTable opcodes that check the predicate for the given operand.
   virtual void emitPredicateOpcodes(MatchTable &Table,
                                     RuleMatcher &Rule) const = 0;
 
   PredicateKind getKind() const { return Kind; }
 
+  bool dependsOnOperands() const {
+    // Custom predicates really depend on the context pattern of the
+    // instruction, not just the individual instruction. This therefore
+    // implicitly depends on all other pattern constraints.
+    return Kind == IPM_GenericPredicate;
+  }
+
   virtual bool isIdentical(const PredicateMatcher &B) const {
     return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
            OpIdx == B.OpIdx;
   }
 
   virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
     return hasValue() && PredicateMatcher::isIdentical(B);
   }
public:
 
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
   void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
     if (NumOperandsCheck)
       InstructionNumOperandsMatcher(InsnVarID, getNumOperands())
           .emitPredicateOpcodes(Table, Rule);
 
-    emitPredicateListOpcodes(Table, Rule);
+    // First emit all instruction level predicates need to be verified before we
+    // can verify operands.
+    emitFilteredPredicateListOpcodes(
+      [](const PredicateMatcher &P) {
+        return !P.dependsOnOperands();
+      }, Table, Rule);
 
+    // Emit all operand constraints.
     for (const auto &Operand : Operands)
       Operand->emitPredicateOpcodes(Table, Rule);
+
+    // All of the tablegen defined predicates should now be matched. Now emit
+    // any custom predicates that rely on all generated checks.
+    emitFilteredPredicateListOpcodes(
+      [](const PredicateMatcher &P) {
+        return P.dependsOnOperands();
+      }, Table, Rule);
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(InstructionMatcher &B) {
     // Instruction matchers involving more operands have higher priority.
     if (Operands.size() > B.Operands.size())