[GlobalISel][SelectionDAG] Implement the HasNoUse builtin predicate

[abinavpp]

Summary

This change introduces the HasNoUse builtin predicate in PatFrags that
checks for the absence of use of the first result operand.
GlobalISelEmitter will allow source PatFrags with this predicate to be
matched with destination instructions with empty outs. This predicate is
required for selecting the no-return variant of atomic instructions in
AMDGPU.

[foad]

Would it be helpful if the generated matcher actually checked (or maybe asserted) that the discarded defs are unused?

[abinavpp]

In D125212#3500157, @foad wrote:

Would it be helpful if the generated matcher actually checked (or maybe asserted) that the discarded defs are unused?

This makes sense if the we don't have predicates that check for the use of the defs; Like in PowerPC:

def int_ppc_trechkpt : GCCBuiltin<"__builtin_trechkpt">,
      Intrinsic<[llvm_i32_ty], [], []>;

def TRECHKPT : XForm_base_r3xo <31, 1006,
                                (outs), (ins), "trechkpt." ...

def : Pat<(int_ppc_trechkpt),
          (TRECHKPT)>;

I don't think it would be useful for D125213.

[arsenm]

I do think there should be a builtin hasOneUse pattern predicate the emitter could use to verify

[abinavpp]

In D125212#3500234, @arsenm wrote:

I do think there should be a builtin hasOneUse pattern predicate the emitter could use to verify

If we have a bit HasNoUse builtin predicate in PatFrags we can get the matcher
table to check the empty usage of the result without the generic C++ predicates.
The problem I'm seeing here is that the default behaviour should be to not check
for the use count since most of the selection doesn't care about it. Having a
ternary HasNoUse builtin is fine since we could set it to false for selection
that needs at least 1 use (e.g.: AMDGPU's return atomic ops), true for selection
that needs no use (e.g.: AMDGPU's no return atomic ops), "don't care" for the
majority of the other selections. I don't think we can rely on the '?'
(uninitialized) value since TreePredicateFn::isPredefinedPredicateEqualTo()
return false for uninitialized fields.

How should we do this?

[arsenm]

In D125212#3510705, @abinavpp wrote:

In D125212#3500234, @arsenm wrote:

I do think there should be a builtin hasOneUse pattern predicate the emitter could use to verify

If we have a bit HasNoUse builtin predicate in PatFrags we can get the matcher
table to check the empty usage of the result without the generic C++ predicates.
The problem I'm seeing here is that the default behaviour should be to not check
for the use count since most of the selection doesn't care about it. Having a
ternary HasNoUse builtin is fine since we could set it to false for selection
that needs at least 1 use (e.g.: AMDGPU's return atomic ops), true for selection
that needs no use (e.g.: AMDGPU's no return atomic ops), "don't care" for the
majority of the other selections. I don't think we can rely on the '?'
(uninitialized) value since TreePredicateFn::isPredefinedPredicateEqualTo()
return false for uninitialized fields.

How should we do this?

Having a false/unset builtin HasOneUse predicate doesn't imply applying the negated predicate. It would just be nothing. If we wanted a hasOneOrMultiple predicate, it would be a separate PatFrag bit

[abinavpp]

In D125212#3517386, @arsenm wrote:

In D125212#3510705, @abinavpp wrote:

In D125212#3500234, @arsenm wrote:

I do think there should be a builtin hasOneUse pattern predicate the emitter could use to verify

If we have a bit HasNoUse builtin predicate in PatFrags we can get the matcher
table to check the empty usage of the result without the generic C++ predicates.
The problem I'm seeing here is that the default behaviour should be to not check
for the use count since most of the selection doesn't care about it. Having a
ternary HasNoUse builtin is fine since we could set it to false for selection
that needs at least 1 use (e.g.: AMDGPU's return atomic ops), true for selection
that needs no use (e.g.: AMDGPU's no return atomic ops), "don't care" for the
majority of the other selections. I don't think we can rely on the '?'
(uninitialized) value since TreePredicateFn::isPredefinedPredicateEqualTo()
return false for uninitialized fields.

How should we do this?

Having a false/unset builtin HasOneUse predicate doesn't imply applying the negated predicate. It would just be nothing. If we wanted a hasOneOrMultiple predicate, it would be a separate PatFrag bit

I'm assuming you mean has(No)Use, I don't see the relevance of checking for one
use here.

I agree with you on omitting the predicates if the field is set to
false/uninitialized. In that case, how about we add the following to
PatFrags:

// If set to true, a predicate is added that checks for at least one use of
// the return value; Otherwise no predicate is added.
bit HasUse = ?;
// If set to true, a predicate is added that checks for no use of the return
// value; Otherwise no predicate is added.
//
// The TableGen backend asserts that both HasUse and HasNoUse is not set to
// true.
bit HasNoUse = ?;

[arsenm]

In D125212#3518566, @abinavpp wrote:

I agree with you on omitting the predicates if the field is set to
false/uninitialized. In that case, how about we add the following to
PatFrags:

// If set to true, a predicate is added that checks for at least one use of
// the return value; Otherwise no predicate is added.
bit HasUse = ?;
// If set to true, a predicate is added that checks for no use of the return
// value; Otherwise no predicate is added.
//
// The TableGen backend asserts that both HasUse and HasNoUse is not set to
// true.
bit HasNoUse = ?;

Yes. The way the PatFrags are structured this is two different predicates the emitter needs to enforce are mutually exclusive. This only really makes sense if you look at how this is implemented

[abinavpp]

Change the SDNPHasChain approach to the Has{No}Use predicates approach

[foad]

llvm/test/TableGen/GlobalISelEmitter-HasUse.td

45 ↗

(On Diff #430971)

A philosophical question: do we really need HasUse? After all the atomic_load_add_ret pattern will still work in both cases (use & nouse), so shouldn't we use priorities instead to prefer the atomic_load_add_no_ret pattern when both are applicable?

llvm/utils/TableGen/GlobalISelEmitter.cpp

5268–5269

Use min() ?

5270–5271

This looks odd. Does the call to getExtType have side effects?

[arsenm]

llvm/test/TableGen/GlobalISelEmitter-HasUse.td

45 ↗

(On Diff #430971)

Yes, having one predicate and priorities would be more consistent

llvm/utils/TableGen/GlobalISelEmitter.cpp

4030–4035

It's very not obvious but the code is structured in such a way that assumes each level of PatFrag you define only defines one predicate. We need verification (like the DAG path has) that this is the case

5258

The naming here is potentially confusing, since it looks like it's checking for a use of the predicate itself.

[abinavpp]

Address review comments

[abinavpp]

llvm/test/TableGen/GlobalISelEmitter-HasUse.td

45 ↗

(On Diff #430971)

D128241

[abinavpp]

llvm/utils/TableGen/GlobalISelEmitter.cpp

4030–4035

I'm interested in reworking this, but probably in a different patch.

[foad]

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

199

Should document that it applies to the first result operand - if that's what you intended to implement.

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

390

Don't need == nullptr.

llvm/include/llvm/Target/TargetSelectionDAG.td

805

"... the first result"?

[abinavpp]

Address review comments

[abinavpp]

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

390

Don't we need to make sure that State.MIs[InsnID] is not a nullptr here?

[foad]

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

390

I just meant you could write it as assert(MI && "Used insn before defined") - you don't need the != nullptr part. (And I mistyped == instead of !=.)

[abinavpp]

Address review comment

[arsenm]

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

392

Ideally this would be for a specific operand index, but it would be a bit hard to test since we still can't write patterns with other defs

llvm/include/llvm/Target/TargetSelectionDAG.td

803

Not sure how you can avoid supporting it here?

[abinavpp]

llvm/include/llvm/Target/TargetSelectionDAG.td

803

I assume we're good with the changes for GlobalISel (including D128241 and D125213). Should I add the SelectionDAG support in this patch?

[arsenm]

llvm/include/llvm/Target/TargetSelectionDAG.td

803

Yes. I think not having the predicate work in both would be confusingly divergent. I think the DAG path is easier to handle since it's just dumb C++ emission

[abinavpp]

• Rebase
• Add the SelectionDAG implementation; Had to add this in the TreePredicateFn::hasPredCode() since the predicate was not added for intrinsics without it (due to the absence of IsAtomic?).

[arsenm]

In D125212#3627989, @abinavpp wrote:

• Rebase
• Add the SelectionDAG implementation; Had to add this in the TreePredicateFn::hasPredCode() since the predicate was not added for intrinsics without it (due to the absence of IsAtomic?).

This shouldn't depend on the memory properties. This should work for any node

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

enum {
   GIM_CheckIsBuildVectorAllOnes,
   GIM_CheckIsBuildVectorAllZeros,
 
   /// Check a generic C++ instruction predicate
   /// - InsnID - Instruction ID
   /// - PredicateID - The ID of the predicate function to call
   GIM_CheckCxxInsnPredicate,
 
+  /// Check if there's no use of the first result.
+  /// - InsnID - Instruction ID
+  GIM_CheckHasNoUse,
+
   /// Check the type for the specified operand
   /// - InsnID - Instruction ID
   /// - OpIdx - Operand index
   /// - Expected type
   GIM_CheckType,
   /// Check the type of a pointer to any address space.
   /// - InsnID - Instruction ID
   /// - OpIdx - Operand index

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

case GIM_CheckCxxInsnPredicate: {
       assert(Predicate > GIPFP_MI_Invalid && "Expected a valid predicate");
 
       if (!testMIPredicate_MI(Predicate, *State.MIs[InsnID],
                               State.RecordedOperands))
         if (handleReject() == RejectAndGiveUp)
           return false;
       break;
     }
+    case GIM_CheckHasNoUse: {
+      int64_t InsnID = MatchTable[CurrentIdx++];
+
+      DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
+                      dbgs() << CurrentIdx << ": GIM_CheckHasNoUse(MIs["
+                             << InsnID << "]\n");
+
+      const MachineInstr *MI = State.MIs[InsnID];
+      assert(MI && "Used insn before defined");
+      assert(MI->getNumDefs() > 0 && "No defs");
+      const Register Res = MI->getOperand(0).getReg();
+
+      if (!MRI.use_nodbg_empty(Res)) {
+        if (handleReject() == RejectAndGiveUp)
+          return false;
+      }
+
+      break;
+    }
     case GIM_CheckAtomicOrdering: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       AtomicOrdering Ordering = (AtomicOrdering)MatchTable[CurrentIdx++];
       DEBUG_WITH_TYPE(TgtInstructionSelector::getName(),
                       dbgs() << CurrentIdx << ": GIM_CheckAtomicOrdering(MIs["
                              << InsnID << "], " << (uint64_t)Ordering << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       if (!State.MIs[InsnID]->hasOneMemOperand())

llvm/include/llvm/Target/TargetSelectionDAG.td

class PatFrags<dag ops, list<dag> frags, code pred = [{}],
   // vector which contains the captured nodes of the DAG, in the order listed
   // by the Operands field above.
   //
   // This is useful when Fragments involves associative / commutative
   // operators: a single piece of code can easily refer to all operands even
   // when re-associated / commuted variants of the fragment are matched.
   bit PredicateCodeUsesOperands = false;
 
+  // TODO: Support this in SelectionDAG.
+  // If set to true, a predicate is added that checks for the absence of use of
+  // the first result.
+  bit HasNoUse = ?;
+
   // Define a few pre-packaged predicates. This helps GlobalISel import
   // existing rules from SelectionDAG for many common cases.
   // They will be tested prior to the code in pred and must not be used in
   // ImmLeaf and its subclasses.
 
   // Is the desired pre-packaged predicate for a load?
   bit IsLoad = ?;
   // Is the desired pre-packaged predicate for a store?

llvm/test/TableGen/GlobalISelEmitter-HasNoUse.td

+// RUN: llvm-tblgen -gen-global-isel -warn-on-skipped-patterns -I %p/../../include -I %p/Common %s -o - < %s | FileCheck -check-prefix=GISEL %s
+
+include "llvm/Target/Target.td"
+include "GlobalISelEmitterCommon.td"
+
+// Test the HasNoUse predicate
+
+def NO_RET_ATOMIC_ADD : I<(outs), (ins GPR32Op:$src0, GPR32Op:$src1), []>;
+
+// GISEL: GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ATOMICRMW_ADD,
+// GISEL-NEXT: GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// GISEL-NEXT: GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// GISEL-NEXT: GIM_CheckMemorySizeEqualTo, /*MI*/0, /*MMO*/0, /*Size*/4,
+// GISEL-NEXT: GIM_CheckHasNoUse, /*MI*/0,
+// GISEL-NEXT: // MIs[0] src0
+// GISEL-NEXT: GIM_CheckPointerToAny, /*MI*/0, /*Op*/1, /*SizeInBits*/0,
+// GISEL-NEXT: // (atomic_load_add:{ *:[i32] } iPTR:{ *:[iPTR] }:$src0, i32:{ *:[i32] }:$src1)<<P:Predicate_atomic_load_add_no_ret_32>>  =>  (NO_RET_ATOMIC_ADD GPR32:{ *:[i32] }:$src0, GPR32:{ *:[i32] }:$src1)
+// GISEL-NEXT: GIR_BuildMI, /*InsnID*/0, /*Opcode*/MyTarget::NO_RET_ATOMIC_ADD,
+// GISEL-NEXT: GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/1, // src0
+// GISEL-NEXT: GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/2, // src1
+// GISEL-NEXT: GIR_MergeMemOperands, /*InsnID*/0, /*MergeInsnID's*/0, GIU_MergeMemOperands_EndOfList,
+// GISEL-NEXT: GIR_EraseFromParent, /*InsnID*/0,
+// GISEL-NEXT: GIR_ConstrainSelectedInstOperands, /*InsnID*/0,
+let HasNoUse = true in
+defm atomic_load_add_no_ret : binary_atomic_op<atomic_load_add>;
+
+def : Pat <
+  (atomic_load_add_no_ret_32 iPTR:$src0, i32:$src1),
+  (NO_RET_ATOMIC_ADD GPR32:$src0, GPR32:$src1)
+>;

llvm/utils/TableGen/CodeGenDAGPatterns.h

public:
 
   /// Get a string that describes the type returned by getImmType() but is
   /// usable as part of an identifier.
   StringRef getImmTypeIdentifier() const;
 
   // Predicate code uses the PatFrag's captured operands.
   bool usesOperands() const;
 
+  // Check if the HasNoUse predicate is set.
+  bool hasNoUse() const;
+
   // Is the desired predefined predicate for a load?
   bool isLoad() const;
   // Is the desired predefined predicate for a store?
   bool isStore() const;
   // Is the desired predefined predicate for an atomic?
   bool isAtomic() const;
 
   /// Is this predicate the predefined unindexed load predicate?

llvm/utils/TableGen/CodeGenDAGPatterns.cpp

bool Result =
       getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset(Field, Unset);
   if (Unset)
     return false;
   return Result == Value;
 }
 bool TreePredicateFn::usesOperands() const {
   return isPredefinedPredicateEqualTo("PredicateCodeUsesOperands", true);
 }
+bool TreePredicateFn::hasNoUse() const {
+  return isPredefinedPredicateEqualTo("HasNoUse", true);
+}
 bool TreePredicateFn::isLoad() const {
   return isPredefinedPredicateEqualTo("IsLoad", true);
 }
 bool TreePredicateFn::isStore() const {
   return isPredefinedPredicateEqualTo("IsStore", true);
 }
 bool TreePredicateFn::isAtomic() const {
   return isPredefinedPredicateEqualTo("IsAtomic", true);

llvm/utils/TableGen/GlobalISelEmitter.cpp

for (const TreePredicateCall &Call : N->getPredicateCalls()) {
     const TreePredicateFn &Predicate = Call.Fn;
 
     if (Predicate.isAlwaysTrue())
       continue;
 
     if (Predicate.isImmediatePattern())
       continue;
 
+    if (Predicate.hasNoUse())
+      continue;
+
     if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() ||
         Predicate.isSignExtLoad() || Predicate.isZeroExtLoad())
       continue;
 
     if (Predicate.isNonTruncStore() || Predicate.isTruncStore())
       continue;
 
     if (Predicate.isLoad() && Predicate.getMemoryVT())
enum PredicateKind {
     IPM_ImmPredicate,
     IPM_Imm,
     IPM_AtomicOrderingMMO,
     IPM_MemoryLLTSize,
     IPM_MemoryVsLLTSize,
     IPM_MemoryAddressSpace,
     IPM_MemoryAlignment,
     IPM_VectorSplatImm,
+    IPM_NoUse,
     IPM_GenericPredicate,
     OPM_SameOperand,
     OPM_ComplexPattern,
     OPM_IntrinsicID,
     OPM_CmpPredicate,
     OPM_Instruction,
     OPM_Int,
     OPM_LiteralInt,
void emitPredicateOpcodes(MatchTable &Table,
     Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("FnId")
           << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
           << MatchTable::LineBreak;
   }
 };
 
+/// Generates code to check for the absence of use of the result.
+// TODO? Generalize this to support checking for one use.
+class NoUsePredicateMatcher : public InstructionPredicateMatcher {
+public:
+  NoUsePredicateMatcher(unsigned InsnVarID)
+      : InstructionPredicateMatcher(IPM_NoUse, InsnVarID) {}
+
+  static bool classof(const PredicateMatcher *P) {
+    return P->getKind() == IPM_NoUse;
+  }
+
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return InstructionPredicateMatcher::isIdentical(B);
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckHasNoUse")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::LineBreak;
+  }
+};
+
 /// Generates code to check that a set of predicates and operands match for a
 /// particular instruction.
 ///
 /// Typical predicates include:
 /// * Has a specific opcode.
 /// * Has an nsw/nuw flag or doesn't.
 class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
 protected:
if (Predicate.isImmediatePattern()) {
       continue;
     }
 
     auto InsnMatcherOrError = addBuiltinPredicates(
         SrcGIEquivOrNull, Predicate, InsnMatcher, HasAddedBuiltinMatcher);
     if (auto Error = InsnMatcherOrError.takeError())
       return std::move(Error);
 
+    // FIXME: This should be part of addBuiltinPredicates(). If we add this at
+    // the start of addBuiltinPredicates() without returning, then there might
+    // be cases where we hit the last return before which the
+    // HasAddedBuiltinMatcher will be set to false. The predicate could be
+    // missed if we add it in the middle or at the end due to return statements
+    // after the addPredicate<>() calls.
+    if (Predicate.hasNoUse()) {
+      InsnMatcher.addPredicate<NoUsePredicateMatcher>();
+      HasAddedBuiltinMatcher = true;
+    }
+
     if (Predicate.hasGISelPredicateCode()) {
       if (Predicate.usesOperands()) {
         assert(WaitingForNamedOperands == 0 &&
                "previous predicate didn't find all operands or "
                "nested predicate that uses operands");
         TreePattern *TP = Predicate.getOrigPatFragRecord();
         WaitingForNamedOperands = TP->getNumArgs();
         for (unsigned i = 0; i < WaitingForNamedOperands; ++i)
Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   // Start with the defined operands (i.e., the results of the root operator).
   Record *DstOp = Dst->getOperator();
   if (!DstOp->isSubClassOf("Instruction"))
     return failedImport("Pattern operator isn't an instruction");
 
   auto &DstI = Target.getInstruction(DstOp);
   StringRef DstIName = DstI.TheDef->getName();
 
-  if (DstI.Operands.NumDefs < Src->getExtTypes().size())
+  unsigned DstNumDefs = DstI.Operands.NumDefs,
+           SrcNumDefs = Src->getExtTypes().size();
+  if (DstNumDefs < SrcNumDefs) {
+    if (DstNumDefs != 0)
       return failedImport("Src pattern result has more defs than dst MI (" +
-                        to_string(Src->getExtTypes().size()) + " def(s) vs " +
-                        to_string(DstI.Operands.NumDefs) + " def(s))");
+                          to_string(SrcNumDefs) + " def(s) vs " +
+                          to_string(DstNumDefs) + " def(s))");
+
+    bool FoundNoUsePred = false;
+    for (const auto &Pred : InsnMatcher.predicates()) {
+      if ((FoundNoUsePred = isa<NoUsePredicateMatcher>(Pred.get())))
+        break;
+    }
+    if (!FoundNoUsePred)
+      return failedImport("Src pattern result has " + to_string(SrcNumDefs) +
+                          " def(s) without the HasNoUse predicate set to true "
+                          "but Dst MI has no def");
+  }
 
   // The root of the match also has constraints on the register bank so that it
   // matches the result instruction.
   unsigned OpIdx = 0;
-  for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
-    (void)VTy;
+  unsigned N = std::min(DstNumDefs, SrcNumDefs);
+  for (unsigned I = 0; I < N; ++I) {
+    const TypeSetByHwMode &VTy = Src->getExtType(I);
 
     const auto &DstIOperand = DstI.Operands[OpIdx];
     Record *DstIOpRec = DstIOperand.Rec;
     if (DstIName == "COPY_TO_REGCLASS") {
       DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue());
 
       if (DstIOpRec == nullptr)
         return failedImport(