[GlobalISel][Tablegen] Fix SameOperandMatcher's isIdentical check

[kschwarz]

Summary

During rule optimization, identical SameOperandMatchers are hoisted into a common group,
however previously only one operand index was considered.
Commutable patterns can introduce SameOperandMatcher checks where the second index is commuted,
resulting in a different check that cannot be hoisted.

[kschwarz]

Rebase & ping

[kschwarz]

llvm/test/TableGen/GlobalISelEmitterMatchTableOptimizerSameOperand-invalid.td

17

Even with the fix for the isSameOperand predicate, we can still have a situation where hoisting the check is not correct.

In this case, the optimizer finds that the operand checks are indeed identical, and hoists the check into a common block.
However, the check will unconditionally access operand index 2 of /*OtherMI*/2.
If the input GMIR does not have three operands in /*OtherMI*/2, this will crash.

The safest way would be to forbid hoisting SameOperandMatchers altogether.
Anyone have a better idea?

[qcolombet]

llvm/test/TableGen/GlobalISelEmitterMatchTableOptimizerSameOperand-invalid.td

17

Just to make sure I understand correctly: what you're saying is this patch fixes one problem but there are others that need to be fixed as well, but this is orthogonal to this patch.

Is that right?

[kschwarz]

llvm/test/TableGen/GlobalISelEmitterMatchTableOptimizerSameOperand-invalid.td

17

Exactly. This patch fixes the issue where two SameOperandMatchers are considered identical, although they are not.

The other issue that is not addressed yet is that the table optimizer will hoist identical checks, even though it might not always be safe to do so.
One such case is shown in this "invalid" test, where the GIM_CheckIsSameOperand at line 16 is hoisted and thus also executed on the path to the matcher at line 75 (Label 1), which can lead to a crash of the compiler.

I'll try to come up with a patch for that in a follow-up.

llvm/test/TableGen/GlobalISelEmitterMatchTableOptimizerSameOperand-invalid.td

+// RUN: llvm-tblgen %s -gen-global-isel -optimize-match-table=true -I %p/../../include -I %p/Common -o - | FileCheck %s
+
+include "llvm/Target/Target.td"
+include "GlobalISelEmitterCommon.td"
+
+def InstTwoOperands : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def InstThreeOperands : I<(outs GPR32:$dst), (ins GPR32:$cond, GPR32:$src,GPR32:$src2), []>;
+
+// CHECK:         GIM_Try, /*On fail goto*//*Label 0*/ 219,
+// CHECK-NEXT:      GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// CHECK-NEXT:      GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:      GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:      GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:      GIM_Try, /*On fail goto*//*Label 1*/ 189,
+// CHECK-NEXT:        GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:        GIM_CheckIsSameOperand, /*MI*/0, /*OpIdx*/3, /*OtherMI*/2, /*OtherOpIdx*/2,
+// CHECK-NEXT:        GIM_Try, /*On fail goto*//*Label 2*/ 108, // Rule ID 1 //
+// CHECK-NEXT:          GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT:          GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_ICMP,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/1, /*Op*/3, /*Type*/GILLT_s32,
+// CHECK-NEXT:          // MIs[1] Operand 1
+// CHECK-NEXT:          GIM_CheckCmpPredicate, /*MI*/1, /*Op*/1, /*Predicate*/CmpInst::ICMP_EQ,
+// CHECK-NEXT:          GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:          GIM_CheckConstantInt, /*MI*/1, /*Op*/3, 0,
+// CHECK-NEXT:          GIM_RecordInsn, /*DefineMI*/2, /*MI*/0, /*OpIdx*/2, // MIs[2]
+// CHECK-NEXT:          GIM_CheckOpcode, /*MI*/2, TargetOpcode::G_SUB,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/2, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/2, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:          GIM_CheckRegBankForClass, /*MI*/2, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:          GIM_CheckRegBankForClass, /*MI*/2, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:          GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT:          GIM_CheckIsSafeToFold, /*InsnID*/2,
+// CHECK-NEXT:          // (select:{ *:[i32] } (setcc:{ *:[i32] } GPR32:{ *:[i32] }:$cond, 0:{ *:[i32] }, SETEQ:{ *:[Other] }), (sub:{ *:[i32] } GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2), GPR32:{ *:[i32] }:$src2)  =>  (InstThreeOperands:{ *:[i32] } GPR32:{ *:[i32] }:$cond, GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2)
+// CHECK-NEXT:          GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::InstThreeOperands,
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/2, // cond
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/2, /*OpIdx*/1, // src1
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/2, /*OpIdx*/2, // src2
+// CHECK-NEXT:          GIR_EraseFromParent, /*InsnID*/0,
+// CHECK-NEXT:          GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
+// CHECK-NEXT:          // GIR_Coverage, 1,
+// CHECK-NEXT:          GIR_Done,
+// CHECK-NEXT:        // Label 2: @108
+// CHECK-NEXT:        GIM_Try, /*On fail goto*//*Label 3*/ 188, // Rule ID 2 //
+// CHECK-NEXT:          GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT:          GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_ICMP,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/1, /*Op*/3, /*Type*/GILLT_s32,
+// CHECK-NEXT:          // MIs[1] Operand 1
+// CHECK-NEXT:          GIM_CheckCmpPredicate, /*MI*/1, /*Op*/1, /*Predicate*/CmpInst::ICMP_NE,
+// CHECK-NEXT:          GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:          GIM_CheckConstantInt, /*MI*/1, /*Op*/3, 0,
+// CHECK-NEXT:          GIM_RecordInsn, /*DefineMI*/2, /*MI*/0, /*OpIdx*/2, // MIs[2]
+// CHECK-NEXT:          GIM_CheckOpcode, /*MI*/2, TargetOpcode::G_SUB,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/2, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:          GIM_CheckType, /*MI*/2, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:          GIM_CheckRegBankForClass, /*MI*/2, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:          GIM_CheckRegBankForClass, /*MI*/2, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:          GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT:          GIM_CheckIsSafeToFold, /*InsnID*/2,
+// CHECK-NEXT:          // (select:{ *:[i32] } (setcc:{ *:[i32] } GPR32:{ *:[i32] }:$cond, 0:{ *:[i32] }, SETNE:{ *:[Other] }), (sub:{ *:[i32] } GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2), GPR32:{ *:[i32] }:$src2)  =>  (InstThreeOperands:{ *:[i32] } GPR32:{ *:[i32] }:$cond, GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2)
+// CHECK-NEXT:          GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::InstThreeOperands,
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // dst
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/2, // cond
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/2, /*OpIdx*/1, // src1
+// CHECK-NEXT:          GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/2, /*OpIdx*/2, // src2
+// CHECK-NEXT:          GIR_EraseFromParent, /*InsnID*/0,
+// CHECK-NEXT:          GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
+// CHECK-NEXT:          // GIR_Coverage, 2,
+// CHECK-NEXT:          GIR_Done,
+// CHECK-NEXT:        // Label 3: @188
+// CHECK-NEXT:        GIM_Reject,
+// CHECK-NEXT:      // Label 1: @189
+// CHECK-NEXT:      GIM_Try, /*On fail goto*//*Label 4*/ 218, // Rule ID 0 //
+// CHECK-NEXT:        GIM_CheckType, /*MI*/0, /*Op*/3, /*Type*/GILLT_s32,
+// CHECK-NEXT:        GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:        GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:        GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:        GIM_CheckRegBankForClass, /*MI*/0, /*Op*/3, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:        // (select:{ *:[i32] } GPR32:{ *:[i32] }:$cond, GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2)  =>  (InstThreeOperands:{ *:[i32] } GPR32:{ *:[i32] }:$cond, GPR32:{ *:[i32] }:$src1, GPR32:{ *:[i32] }:$src2)
+// CHECK-NEXT:        GIR_MutateOpcode, /*InsnID*/0, /*RecycleInsnID*/0, /*Opcode*/MyTarget::InstThreeOperands,
+// CHECK-NEXT:        GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
+// CHECK-NEXT:        // GIR_Coverage, 0,
+// CHECK-NEXT:        GIR_Done,
+// CHECK-NEXT:      // Label 4: @218
+// CHECK-NEXT:      GIM_Reject,
+// CHECK-NEXT:    // Label 0: @219
+// CHECK-NEXT:    GIM_Reject,
+// CHECK-NEXT:    }
+def : Pat<(i32 (select GPR32:$cond, GPR32:$src1, GPR32:$src2)),
+          (InstThreeOperands GPR32:$cond, GPR32:$src1, GPR32:$src2)>;
+
+def : Pat<(i32 (select (i32 (setcc GPR32:$cond, (i32 0), (OtherVT SETEQ))),
+                       (i32 (sub GPR32:$src1, GPR32:$src2)),
+                       GPR32:$src2)),
+          (InstThreeOperands GPR32:$cond, GPR32:$src1, GPR32:$src2)>;
+
+def : Pat<(i32 (select (i32 (setcc GPR32:$cond, (i32 0), (OtherVT SETNE))),
+                       (i32 (sub GPR32:$src1, GPR32:$src2)),
+                       GPR32:$src2)),
+          (InstThreeOperands GPR32:$cond, GPR32:$src1, GPR32:$src2)>;

llvm/test/TableGen/GlobalISelEmitterMatchTableOptimizerSameOperand.td

+// RUN: llvm-tblgen %s -gen-global-isel -optimize-match-table=true -I %p/../../include -I %p/Common -o - | FileCheck %s
+
+include "llvm/Target/Target.td"
+include "GlobalISelEmitterCommon.td"
+
+def InstTwoOperands : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def InstThreeOperands : I<(outs GPR32:$dst), (ins GPR32:$cond, GPR32:$src,GPR32:$src2), []>;
+
+// Make sure the GIM_CheckIsSameOperand check is not hoisted into the common header group
+
+// CHECK:       GIM_Try, /*On fail goto*//*Label 1*/
+// CHECK-NEXT:  GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NOT:   GIM_CheckIsSameOperand
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 2*/
+// CHECK:       GIM_CheckIsSameOperand, /*MI*/0, /*OpIdx*/3, /*OtherMI*/2, /*OtherOpIdx*/1,
+// CHECK:       // Label 2
+// CHECK-NEXT:  GIM_Try, /*On fail goto*//*Label 3*/
+// CHECK:       GIM_CheckIsSameOperand, /*MI*/0, /*OpIdx*/3, /*OtherMI*/2, /*OtherOpIdx*/2,
+// CHECK:       // Label 1
+def : Pat<(i32 (select GPR32:$cond, GPR32:$src1, GPR32:$src2)),
+          (InstThreeOperands GPR32:$cond, GPR32:$src1, GPR32:$src2)>;
+
+def : Pat<(i32 (select (i32 (setcc GPR32:$cond, (i32 0), (OtherVT SETEQ))),
+                      (i32 (add GPR32:$src1, GPR32:$const)),
+                       GPR32:$src1)),
+          (InstThreeOperands GPR32:$cond, GPR32:$src1, GPR32:$const)>;

llvm/utils/TableGen/GlobalISelEmitter.cpp

 PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
   return "No operand predicates";
 }
 
 /// Generates code to check that a register operand is defined by the same exact
 /// one as another.
 class SameOperandMatcher : public OperandPredicateMatcher {
   std::string MatchingName;
+  unsigned OrigOpIdx;
 
 public:
-  SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName)
+  SameOperandMatcher(unsigned InsnVarID, unsigned OpIdx, StringRef MatchingName,
+                     unsigned OrigOpIdx)
       : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
-        MatchingName(MatchingName) {}
+        MatchingName(MatchingName), OrigOpIdx(OrigOpIdx) {}
 
   static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_SameOperand;
   }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override;
 
   bool isIdentical(const PredicateMatcher &B) const override {
     return OperandPredicateMatcher::isIdentical(B) &&
+           OrigOpIdx == cast<SameOperandMatcher>(&B)->OrigOpIdx &&
            MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
   }
 };
 
 /// Generates code to check that an operand is a particular LLT.
 class LLTOperandMatcher : public OperandPredicateMatcher {
 protected:
   LLTCodeGen Ty;

 void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
   if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
     DefinedOperands[SymbolicName] = &OM;
     return;
   }
 
   // If the operand is already defined, then we must ensure both references in
   // the matcher have the exact same node.
-  OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
+  OM.addPredicate<SameOperandMatcher>(
+      OM.getSymbolicName(), getOperandMatcher(OM.getSymbolicName()).getOpIdx());
 }
 
 void RuleMatcher::definePhysRegOperand(Record *Reg, OperandMatcher &OM) {
   if (PhysRegOperands.find(Reg) == PhysRegOperands.end()) {
     PhysRegOperands[Reg] = &OM;
     return;
   }
 }