[GISel] Teach TableGen to check predicates of immediate operands in patterns

[gargaroff]

I haven't worked that much with TableGen, so if this is already supported or if there is a better way to do this, please let me know.

[gargaroff]

Ping

[Paul-C-Anagnostopoulos]

I'm no expert on GlobalISelEmiitter, but it doesn't appear to perform this check now. Your new code looks good to my untrained eye.

Someone else should look at it, too.

[arsenm]

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

787

Should probably group with case GIM_CheckI64ImmPredicate: {

The name similarity is a bit confusing too

[gargaroff]

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

787

Do you have a suggestion for a better name? I'm struggling to come up with a different one. The only other idea I have is TImmPredicate, which is just as similar.

[foad]

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

787

"CheckI64ImmOperandPredicate"? Though there are plenty of other checks that check specific operands, that don't have "Operand" in their names.

[gargaroff]

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

787

I'd be fine with that. @arsenm ?

[arsenm]

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

787

MachineOperand calls these "isImm" and "isCImm", so these names should probably mirror that. I'm not sure about including "I64"

[gargaroff]

Rebase. Group with GIM_CheckI64ImmPredicate. Change naming to GIM_CheckImmOperandPredicate.

@arsenm I went with @foad's suggestion in the end because it had less impact than trying to make the naming work with CImm and Imm. Also MachineOperand seems to use them in aslightly different meaning, unless I'm misunderstanding. Hope that's fine for you.

[dsanders]

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

278–281

This assert probably ought to be re-worked a bit as at first glance it appears to be always true. I think it still mostly works but does so indirectly because G_CONSTANT always has an isCImm() (to have type information) and never an isImm().

However, an immediate operand can be isImm() or isCImm() which may give you a false assert for the immediate operands case.

787

I think the main thing is including 'Operand' in the name but I do think the comments need to make the distinction clear. In GlobalISel very few immediates are operands. Normally, the operand is a vreg that's def'd by a G_CONSTANT instruction.

IIRC, the I64 comes from IntImmLeaf isAPInt==0. There was a lot of code that only dealt with <=64-bit and used constants so those convert to int64_t before running the custom C++ predicate. A few needed full APInt's though. I'd be inclined to keep the I64 as sharing code with GIM_CheckI64ImmPredicate means the custom C++ predicate shares the same interface.

MachineOperand calls these "isImm" and "isCImm", so these names should probably mirror that. I'm not sure about including "I64"

isImm() vs isCImm() isn't related to imm/timm. It's about the size of the immediate

/// isImm - Tests if this is a MO_Immediate operand.
/// isCImm - Test if this is a MO_CImmediate operand.

MO_Immediate,         ///< Immediate operand
MO_CImmediate,        ///< Immediate >64bit operand

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

Ah ok, I see why timm is special, it's been special-cased and isn't handled with the other immediates. I'm a little surprised to see this here as this block of code is supposed to be handling MBB's. We should probably revise the comment on 4180 if this is correct. FWIW, I'd generally prefer that we didn't special case by name but I don't really have an alternative to suggest in this case.

What was the reason timm's needed to be handled here rather than with the imm and the other ImmLeaf's? I'd hazard a guess that it's down to the distinction between having an MCOperand with isImm() == true and the normal G_CONSTANT but even if that's the reason, timm vs imm doesn't really correspond to that distinction (timm is just an imm that can't be folded/simplified/lowered) which suggests there's something else not quite right.

[gargaroff]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

Do you have some suggestion what could be done? Even if we remove the special handling here, at one point we will have to do at least some special handling because in one case we have to check for a G_CONSTANT while in the other we have to check for an immediate operand.

I guess the checker in match-table could technically do both dynamically: check one condition first and if that doesn't apply, check the other one. However I'm not sure what changes this would need in this emitter, as the predicate matcher for G_CONSTANT is an InstructionMatcher while for timm we need an OperandMatcher. I'm not too familiar with the internals of TableGen, so the only way to differentiate between the two known to me, is to check by name unfortunately.

[gargaroff]

At the moment I still cannot find time to work on this, unfortunately. Unless someone has a suggestion for a simple way forward, I'm going to abandon this next week.

[dsanders]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

For the checking by name bit, I was just saying that I don't really like using the name but there's not really a reasonable alternative in this case. We can leave it distinguishing them by name

For the imm/timm not corresponding to G_CONSTANT/isImm() bit, I was mostly acknowledging that something doesn't quite fit with the mapping from DAGISel to GlobalISel in general not really w.r.t this patch. The problem is that the distinction between Constant/TargetConstant is rather artificial, they're both constants that can match and be rendered as isImm() immediates and they can both be materialized in a register. The only distinction is what optimizations DAGISel is allowed to apply to them. I think the closest we can get in GlobalISel is that both imm and timm are allowed to match G_CONSTANT's, but timm is also allowed to match isImm() immediates as well. The one bit that still doesn't quite match up with DAGISel there is if you have an isImm() style immediate but no timm rules that match it, you'll get cannot-select whereas DAGISel would have materialized it.

Does that cover what you need?

[arsenm]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

The problem is that the distinction between Constant/TargetConstant is rather artificial, they're both constants that can match and be rendered as isImm() immediates and they can both be materialized in a register

No, this is the real and significant distinction. Constant is materialized in a register, TargetConstant must not be. Transforming a constant from a materialized one into an isImm operand is a function of the output operand transform

[dsanders]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

There's nothing I've seen in the definition of timm/TargetConstant that forbids materialization in a register. Implementation-wise they're both ConstantSDNode's and are only distinguishable by the opcode being either Constant or TargetConstant. This keeps them apart in the rules as DAGISel rules which check the opcode rather than isa<ConstantSDNode> but aside from having a different enum value in ISD enum they're functionally the same in DAGISel's implementation.

If it's true that timm never materializes for a given target then it's only by a lack of a (set $dst, $src:timm) pattern rather than by anything in the nature of timm itself. Maybe that's common enough that we can get away with enforcing it in the importer but it's not enforced in DAGISel as far as I've seen.

[dsanders]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

If it's true that timm never materializes for a given target then it's only by a lack of a (set $dst, $src:timm) pattern rather than by anything in the nature of timm itself. Maybe that's common enough that we can get away with enforcing it in the importer but it's not enforced in DAGISel as far as I've seen.

Just to clarify the last bit of that, if is true via the lack of a materialization pattern for all targets then I'll be ok with the importer only accepting isImm() immediates for when timm is used. I think we should probably verify the materialization pattern for timm doesn't exist and error if we find it though.

[gargaroff]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

I tried to pick up this patch again but quickly realized that I'm still confused about what actually needs to be done now. Should the code handling timms be moved to some other place where it makes more sense? Should the cases for immediates in the instruction selector be merged? Or should the whole immediate handling be changed in some way?

I have never worked with DAG ISel and I don't know what the difference between imm and timm is supposed to be in the end. In my understanding it was just the distinction that imm maps to G_CONSTANT operand, while timm maps to an immediate operand, nothing more. From your discussion it seems like there is something more to this that would actually require a much bigger rework in this patch. Is that correct?

[dsanders]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

In my understanding it was just the distinction that imm maps to G_CONSTANT operand, while timm maps to an immediate operand, nothing more.

Where I landed on this was while this is technically wrong w.r.t the definition of imm/timm, it's right w.r.t practice. We just need to add a check along the lines of this pseudocode:

for (Pattern : Patterns) {
    if (Pattern.getSrcPattern() is not (set $d, timm))
        report_fatal_error("Materialization of timm cannot work in GISel");
}

to ensure we don't get bitten by the difference between what the definition allowed and what we implemented.

[arsenm]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

Not materializing in a register is the whole point, otherwise we would not have the distinction. I did make the SelectionDAG patterns stricter in this area not too long ago, so I don't think a verifier check would show too many violations

[dsanders]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

Not materializing in a register is the whole point, otherwise we would not have the distinction.

It may be the overall point but there's nothing in the definitions (implementation or documentation) that expresses this limitation. I've come around to the opinion that the limitation is pretty much there in practice but without any docs/implementation I'm nervous about _relying_ on that without some guard against being wrong.

I did make the SelectionDAG patterns stricter in this area not too long ago, so I don't think a verifier check would show too many violations

I'm hoping it will be zero. The reason I'd like the check is that a rule that violates this new limitation won't be considered a bug in GISel's importer, it will be on the target author to change their rules.

[gargaroff]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

So I implemented this check now and tried to write a test for it like this:

def Foo : I<(outs GPR32:$dst), (ins i32imm:$src),
  [(set GPR32:$dst, tuimm9:$src)]
>;

However this pattern is already getting rejected during the import:

llvm/test/TableGen/immarg-predicated.td:24:1: warning: Skipped pattern: Pattern operator lacks an equivalent Instruction (ISD::TargetConstant)
def Foo : I<(outs GPR32:$dst), (ins i32imm:$src),
^

Is there something wrong with my test pattern here or is this already handled then, indirectly?

[arsenm]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

The TargetConstant handling shouldn't have reached this point. The predicate code should have special cased the target constants

[dsanders]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4188

However this pattern is already getting rejected during the import:

llvm/test/TableGen/immarg-predicated.td:24:1: warning: Skipped pattern: Pattern operator lacks an equivalent Instruction (ISD::TargetConstant)
def Foo : I<(outs GPR32:$dst), (ins i32imm:$src),
^
Is there something wrong with my test pattern here or is this already handled then, indirectly?

Ah ok, I didn't realize we didn't have it mapped at all. In that case let's just put a comment next to:

def : GINodeEquiv<G_CONSTANT, imm>;

in SelectionDAGCompat.td saying that timm is intentionally not mapped so the materialization rule can't violate the expected distinction between imm and timm.

[gargaroff]

Add comment to SelectionDAGCompat.td

[gargaroff]

Remove unintended change. Rework assertion in InstructionSelectorImpl.h

[gargaroff]

Ping

[gargaroff]

Ping

[gargaroff]

Ping

[dsanders]

LGTM. Sorry for the long wait

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelector.h

enum {
   /// Check an immediate predicate on the specified instruction via an APInt.
   /// - InsnID - Instruction ID
   /// - The predicate to test
   GIM_CheckAPIntImmPredicate,
   /// Check a floating point immediate predicate on the specified instruction.
   /// - InsnID - Instruction ID
   /// - The predicate to test
   GIM_CheckAPFloatImmPredicate,
+  /// Check an immediate predicate on the specified instruction
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  /// - The predicate to test
+  GIM_CheckImmOperandPredicate,
   /// Check a memory operation has the specified atomic ordering.
   /// - InsnID - Instruction ID
   /// - Ordering - The AtomicOrdering value
   GIM_CheckAtomicOrdering,
   GIM_CheckAtomicOrderingOrStrongerThan,
   GIM_CheckAtomicOrderingWeakerThan,
   /// Check the size of the memory access for the given machine memory operand.
   /// - InsnID - Instruction ID
enum {
   /// - OldInsnID - Instruction ID to get the matched operand from
   /// - RendererFnID - Custom renderer function to call
   GIR_CustomRenderer,
 
   /// Render operands to the specified instruction using a custom function,
   /// reading from a specific operand.
   /// - InsnID - Instruction ID to modify
   /// - OldInsnID - Instruction ID to get the matched operand from
   /// - OpIdx - Operand index in OldInsnID the render function should read from..
   /// - RendererFnID - Custom renderer function to call
   GIR_CustomOperandRenderer,
 
   /// Render a G_CONSTANT operator as a sign-extended immediate.
   /// - NewInsnID - Instruction ID to modify
   /// - OldInsnID - Instruction ID to copy from
   /// The operand index is implicitly 1.
   GIR_CopyConstantAsSImm,

llvm/include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

case GIM_CheckNumOperands: {
                              << InsnID << "], Expected=" << Expected << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       if (State.MIs[InsnID]->getNumOperands() != Expected) {
         if (handleReject() == RejectAndGiveUp)
           return false;
       }
       break;
     }
-    case GIM_CheckI64ImmPredicate: {
+    case GIM_CheckI64ImmPredicate:
+    case GIM_CheckImmOperandPredicate: {
       int64_t InsnID = MatchTable[CurrentIdx++];
+      int64_t OpIdx = MatcherOpcode == GIM_CheckImmOperandPredicate
+                          ? MatchTable[CurrentIdx++]
+                          : 1;
       int64_t Predicate = MatchTable[CurrentIdx++];
       DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
-                      dbgs()
-                          << CurrentIdx << ": GIM_CheckI64ImmPredicate(MIs["
-                          << InsnID << "], Predicate=" << Predicate << ")\n");
+                      dbgs() << CurrentIdx << ": GIM_CheckImmPredicate(MIs["
+                             << InsnID << "]->getOperand(" << OpIdx
+                             << "), Predicate=" << Predicate << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
-      assert(State.MIs[InsnID]->getOpcode() == TargetOpcode::G_CONSTANT &&
-             "Expected G_CONSTANT");
+      assert((State.MIs[InsnID]->getOperand(OpIdx).isImm() ||
+              State.MIs[InsnID]->getOperand(OpIdx).isCImm()) &&
+             "Expected immediate operand");
       assert(Predicate > GIPFP_I64_Invalid && "Expected a valid predicate");
       int64_t Value = 0;
-      if (State.MIs[InsnID]->getOperand(1).isCImm())
-        Value = State.MIs[InsnID]->getOperand(1).getCImm()->getSExtValue();
-      else if (State.MIs[InsnID]->getOperand(1).isImm())
-        Value = State.MIs[InsnID]->getOperand(1).getImm();
+      if (State.MIs[InsnID]->getOperand(OpIdx).isCImm())
+        Value = State.MIs[InsnID]->getOperand(OpIdx).getCImm()->getSExtValue();
+      else if (State.MIs[InsnID]->getOperand(OpIdx).isImm())
+        Value = State.MIs[InsnID]->getOperand(OpIdx).getImm();
       else
         llvm_unreachable("Expected Imm or CImm operand");
 
       if (!testImmPredicate_I64(Predicate, Value))
         if (handleReject() == RejectAndGiveUp)
           return false;
       break;
     }
case GIM_CheckIsImm: {
                              << "]->getOperand(" << OpIdx << "))\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       if (!State.MIs[InsnID]->getOperand(OpIdx).isImm()) {
         if (handleReject() == RejectAndGiveUp)
           return false;
       }
       break;
     }
     case GIM_CheckIsSafeToFold: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
                       dbgs() << CurrentIdx << ": GIM_CheckIsSafeToFold(MIs["
                              << InsnID << "])\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       if (!isObviouslySafeToFold(*State.MIs[InsnID], *State.MIs[0])) {
         if (handleReject() == RejectAndGiveUp)
           return false;

llvm/include/llvm/Target/GlobalISel/SelectionDAGCompat.td

 def : GINodeEquiv<G_ANYEXT, anyext>;
 def : GINodeEquiv<G_SEXT, sext>;
 def : GINodeEquiv<G_ZEXT, zext>;
 def : GINodeEquiv<G_TRUNC, trunc>;
 def : GINodeEquiv<G_BITCAST, bitconvert>;
 // G_INTTOPTR - SelectionDAG has no equivalent.
 // G_PTRTOINT - SelectionDAG has no equivalent.
 def : GINodeEquiv<G_CONSTANT, imm>;
+// timm must not be materialized and therefore has no GlobalISel equivalent
 def : GINodeEquiv<G_FCONSTANT, fpimm>;
 def : GINodeEquiv<G_IMPLICIT_DEF, undef>;
 def : GINodeEquiv<G_FRAME_INDEX, frameindex>;
 def : GINodeEquiv<G_BLOCK_ADDR, blockaddress>;
 def : GINodeEquiv<G_ADD, add>;
 def : GINodeEquiv<G_SUB, sub>;
 def : GINodeEquiv<G_MUL, mul>;
 def : GINodeEquiv<G_UMULH, mulhu>;

llvm/test/TableGen/immarg-predicated.td

+// RUN: llvm-tblgen -gen-global-isel -optimize-match-table=false -I %p/Common -I %p/../../include %s -o - < %s | FileCheck -check-prefix=GISEL %s
+
+include "llvm/Target/Target.td"
+include "GlobalISelEmitterCommon.td"
+
+let TargetPrefix = "mytarget" in {
+def int_mytarget_sleep0 : Intrinsic<[], [llvm_i32_ty], [ImmArg<ArgIndex<0>>]>;
+}
+
+// GISEL: GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS,
+// GISEL-NEXT: // MIs[0] Operand 0
+// GISEL-NEXT: GIM_CheckIntrinsicID, /*MI*/0, /*Op*/0, Intrinsic::mytarget_sleep0,
+// GISEL-NEXT: // MIs[0] src
+// GISEL-NEXT: GIM_CheckIsImm, /*MI*/0, /*Op*/1,
+// GISEL-NEXT: GIM_CheckImmOperandPredicate, /*MI*/0, /*MO*/1, /*Predicate*/GIPFP_I64_Predicate_tuimm9,
+// GISEL-NEXT: // (intrinsic_void {{[0-9]+}}:{ *:[iPTR] }, (timm:{ *:[i32] })<<P:Predicate_tuimm9>>:$src) => (SLEEP0 (timm:{ *:[i32] }):$src)
+// GISEL-NEXT: GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::SLEEP0,
+// GISEL-NEXT: GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src
+def tuimm9 : TImmLeaf<i32, [{ return isUInt<9>(Imm); }]>;
+def SLEEP0 : I<(outs), (ins i32imm:$src),
+  [(int_mytarget_sleep0 tuimm9:$src)]
+>;

llvm/utils/TableGen/GlobalISelEmitter.cpp

 std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
   if (Predicate.hasGISelPredicateCode())
     return "GIPFP_MI_" + Predicate.getFnName();
   return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
          Predicate.getFnName();
 }
 
 /// Get the opcode used to check this predicate.
-std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
+std::string getMatchOpcodeForImmPredicate(const TreePredicateFn &Predicate) {
   return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
 }
 
 /// This class stands in for LLT wherever we want to tablegen-erate an
 /// equivalent at compiler run-time.
 class LLTCodeGen {
 private:
   LLT Ty;
void emitPredicateOpcodes(MatchTable &Table,
     Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
           << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
           << MatchTable::LineBreak;
   }
 };
 
+/// Generates code to check that this operand is an immediate whose value meets
+/// an immediate predicate.
+class OperandImmPredicateMatcher : public OperandPredicateMatcher {
+protected:
+  TreePredicateFn Predicate;
+
+public:
+  OperandImmPredicateMatcher(unsigned InsnVarID, unsigned OpIdx,
+                             const TreePredicateFn &Predicate)
+      : OperandPredicateMatcher(IPM_ImmPredicate, InsnVarID, OpIdx),
+        Predicate(Predicate) {}
+
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Predicate.getOrigPatFragRecord() ==
+               cast<OperandImmPredicateMatcher>(&B)
+                   ->Predicate.getOrigPatFragRecord();
+  }
+
+  static bool classof(const PredicateMatcher *P) {
+    return P->getKind() == IPM_ImmPredicate;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckImmOperandPredicate")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("MO") << MatchTable::IntValue(OpIdx)
+          << MatchTable::Comment("Predicate")
+          << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
+          << MatchTable::LineBreak;
+  }
+};
+
 /// Generates code to check that a set of predicates match for a particular
 /// operand.
 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 protected:
   InstructionMatcher &Insn;
   unsigned OpIdx;
   std::string SymbolicName;
 
public:
   }
 
   static bool classof(const PredicateMatcher *P) {
     return P->getKind() == IPM_ImmPredicate;
   }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override {
-    Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
+    Table << MatchTable::Opcode(getMatchOpcodeForImmPredicate(Predicate))
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Predicate")
           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
           << MatchTable::LineBreak;
   }
 };
 
 /// Generates code to check that a memory instruction has a atomic ordering
Error GlobalISelEmitter::importChildMatcher(
   // Check MBB's before the type check since they are not a known type.
   if (!SrcChild->isLeaf()) {
     if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
       auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
         OM.addPredicate<MBBOperandMatcher>();
         return Error::success();
       }
       if (SrcChild->getOperator()->getName() == "timm") {
         OM.addPredicate<ImmOperandMatcher>();
+
+        // Add predicates, if any
+        for (const TreePredicateCall &Call : SrcChild->getPredicateCalls()) {
+          const TreePredicateFn &Predicate = Call.Fn;
+
+          // Only handle immediate patterns for now
+          if (Predicate.isImmediatePattern()) {
+            OM.addPredicate<OperandImmPredicateMatcher>(Predicate);
+          }
+        }
+
         return Error::success();
       }
     }
   }
 
   // Immediate arguments have no meaningful type to check as they don't have
   // registers.
   if (!OperandIsImmArg) {