[GlobalISel][TableGen] Fix handling of default operands

[rovka]

Summary

When looping through a destination pattern's operands to decide how many
default operands we need to introduce, we used to count the "expanded"
number of operands. So if one default operand would be rendered as 2
values, we'd count it as 2 operands, when in fact it needs to count as
only 1 operand regardless of how many values it expands to.

This turns out to be a problem only in some very specific cases, e.g.
when we have one operand with multiple default values followed by more
operands with default values (see the new test). In such a situation
we'd stop looping before looking at all the operands, and then error out
assuming that we don't have enough default operands to make up the
shortfall.

At the moment this only affects ARM.

The patch removes the loop counting default operands entirely and
assumes that we'll have to introduce values for any default operand that
we find (i.e. we're assuming it cannot be given as a child at all). It
also extracts the code for adding renderers for default operands into a
helper method.

[rovka]

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

Hi Daniel,

Did you have some case in mind when counting things this way? It seems that for ARM instructions the predicate operand (which expands to 2 values) should be counted as only 1 operand. I tried to concoct other complicated cases with default operands but my TableGen-fu isn't strong enough and I couldn't find anything relevant in the existing instruction descriptions for any target (but I may have been looking at it the wrong way).

I ran TableGen with/without this patch for a lot of targets (including some that don't support GlobalISel yet) and the only one where I see any difference in the generated code or in the -warn-on-skipped-patterns -debug-only=gisel-emitter is ARM.

Please let me know if I'm missing something.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

Hi Diana,

I didn't have a particular case in mind when doing it this way. My expectation was that we needed to determine whether the MachineInstr had a complete set of MachineOperands and fill in any that are missing from the default operands. Therefore we needed to count how many default MachineOperands we added to the MachineInstr.

Do you have a particular test case I could look at to see the difference in behaviour?

Looking at this code again, I'm also wondering if there might be a bug involving ComplexPatterns with multiple operands since that's a situation where Dst->getNumChildren() is not equal to the number of MachineOperands added to the instruction.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

Do you have a particular test case I could look at to see the difference in behaviour?

I mean from ARM. In the meantime, I'll look into the one in this patch.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

The bug originates from DstI.Operands.size() which doesn't have the value I'd expect on XORManyDefaults. I'd expected it to be 5 (1 def, 1 explicitly specified operands, 2 default operands from m1Z, and another from Z) but it comes out as 4 (1 def, 3 uses). As a result, the code is mis-counting the number of MO's to expect and the number that are supplied and therefore adds the wrong number of default operands.

I've also noticed that this patch unconditionally adds the default operands this will lead to duplicated operands if a pattern supplies them. I'm currently working on a patch to fix both cases.

[dsanders]

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

Hmm. I'm sure I encountered a case where an OperandWithOptionalOps shouldn't insert the DefaultOps because that's what caused me to write this code but I'm unable to find it now and my attempts at supplying the optional operands in a pattern have failed.

If you agree that OperandWithOptionalOps and friends are really operands that are never provided in a pattern then I think we should add them unconditionally as per this patch. We should also be able to remove this loop and check isSubClassOf("OperandWithDefaultOps") where we currently have DefaultOperands.count(I)

[rovka]

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

On ARM you can look at ADD / SUB.
I agree that DstI.Operands are a bit fishy, I'm not sure how they interact with ComplexPatterns. In any case, without a relevant test we should just go with the simplest code for now and do our best to detect funny situations. I'll have another stab at it without the loop.

[rovka]

Removed the first loop and extracted a helper for adding renderers for default ops. I think this makes the body of the loop easier to read.

I've kept pretty much the same error detection as before. I think there might still be pathological cases that could pass by undetected, but I can't produce any with my current TableGen skills.

Anyway, with this and some changes that I committed today we can remove the handwritten code for G_ADD and G_SUB in the ARMInstructionSelector.

[dsanders]

LGTM.

utils/TableGen/GlobalISelEmitter.cpp

1519 ↗

(On Diff #98408)

In any case, without a relevant test we should just go with the simplest code for now and do our best to detect funny situations.

Yep, I agree.

llvm/trunk/test/TableGen/GlobalISelEmitter.td

 // CHECK-NEXT:    }
 // CHECK-NEXT:    return false;
 // CHECK-NEXT:  }()) { return true; }
 
 // The -4 is just to distinguish it from the other 'not' cases.
 def XORlike : I<(outs GPR32:$dst), (ins m1Z:$src2, GPR32:$src1),
                 [(set GPR32:$dst, (xor GPR32:$src1, -4))]>;
 
+//===- Test a simple pattern with multiple operands with defaults. --------===//
+//
+
+// CHECK-LABEL: if ([&]() {
+// CHECK-NEXT:    MachineInstr &MI0 = I;
+// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_XOR) &&
+// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
+// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
+// CHECK-NEXT:        (isOperandImmEqual(MI0.getOperand(2), -5, MRI))))) {
+// CHECK-NEXT:      // (xor:i32 GPR32:i32:$src1, -5:i32) => (XORManyDefaults:i32 GPR32:i32:$src1)
+// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORManyDefaults));
+// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
+// CHECK-NEXT:      MIB.addImm(-1);
+// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
+// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
+// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:          MIB.addMemOperand(MMO);
+// CHECK-NEXT:      I.eraseFromParent();
+// CHECK-NEXT:      MachineInstr &NewI = *MIB;
+// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:      return true;
+// CHECK-NEXT:    }
+// CHECK-NEXT:    return false;
+// CHECK-NEXT:  }()) { return true; }
+
+// The -5 is just to distinguish it from the other cases.
+def XORManyDefaults : I<(outs GPR32:$dst), (ins m1Z:$src3, Z:$src2, GPR32:$src1),
+                        [(set GPR32:$dst, (xor GPR32:$src1, -5))]>;
+
 //===- Test a simple pattern with constant immediate operands. ------------===//
 //
 // This must precede the 3-register variants because constant immediates have
 // priority over register banks.
 
 // CHECK-LABEL: if ([&]() {
 // CHECK-NEXT:    MachineInstr &MI0 = I;
 // CHECK-NEXT:    if (MI0.getNumOperands() < 3)

llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp

Error importChildMatcher(InstructionMatcher &InsnMatcher,
                            TreePatternNode *SrcChild, unsigned OpIdx,
                            unsigned &TempOpIdx) const;
   Expected<BuildMIAction &> createAndImportInstructionRenderer(
       RuleMatcher &M, const TreePatternNode *Dst,
       const InstructionMatcher &InsnMatcher) const;
   Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
                                   TreePatternNode *DstChild,
                                   const InstructionMatcher &InsnMatcher) const;
+  Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
+                                      DagInit *DefaultOps) const;
   Error
   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
                              const std::vector<Record *> &ImplicitDefs) const;
 
   /// Analyze pattern \p P, returning a matcher for it if possible.
   /// Otherwise, return an Error explaining why we don't support it.
   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
 
Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
   auto &DstMIBuilder = M.addAction<BuildMIAction>(&DstI, InsnMatcher);
 
   // Render the explicit defs.
   for (unsigned I = 0; I < DstI.Operands.NumDefs; ++I) {
     const auto &DstIOperand = DstI.Operands[I];
     DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
   }
 
-  // Figure out which operands need defaults inserted. Operands that subclass
-  // OperandWithDefaultOps are considered from left to right until we have
-  // enough operands to render the instruction.
-  SmallSet<unsigned, 2> DefaultOperands;
+  // Render the explicit uses.
+  unsigned Child = 0;
   unsigned DstINumUses = DstI.Operands.size() - DstI.Operands.NumDefs;
-  unsigned NumDefaultOperands = 0;
-  for (unsigned I = 0; I < DstINumUses &&
-                       DstINumUses > Dst->getNumChildren() + NumDefaultOperands;
-       ++I) {
+  unsigned NumDefaultOps = 0;
+  for (unsigned I = 0; I != DstINumUses; ++I) {
     const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
+
+    // If the operand has default values, introduce them now.
+    // FIXME: Until we have a decent test case that dictates we should do
+    // otherwise, we're going to assume that operands with default values cannot
+    // be specified in the patterns. Therefore, adding them will not cause us to
+    // end up with too many rendered operands.
     if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
-      DefaultOperands.insert(I);
-      NumDefaultOperands +=
-          DstIOperand.Rec->getValueAsDag("DefaultOps")->getNumArgs();
+      DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
+      if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps))
+        return std::move(Error);
+      ++NumDefaultOps;
+      continue;
     }
+
+    if (auto Error = importExplicitUseRenderer(
+            DstMIBuilder, Dst->getChild(Child), InsnMatcher))
+      return std::move(Error);
+    ++Child;
   }
-  if (DstINumUses > Dst->getNumChildren() + DefaultOperands.size())
-    return failedImport("Insufficient operands supplied and default ops "
-                        "couldn't make up the shortfall");
-  if (DstINumUses < Dst->getNumChildren() + DefaultOperands.size())
-    return failedImport("Too many operands supplied");
 
-  // Render the explicit uses.
-  unsigned Child = 0;
-  for (unsigned I = 0; I != DstINumUses; ++I) {
-    // If we need to insert default ops here, then do so.
-    if (DefaultOperands.count(I)) {
-      const auto &DstIOperand = DstI.Operands[DstI.Operands.NumDefs + I];
+  if (NumDefaultOps + Dst->getNumChildren() != DstINumUses)
+    return failedImport("Expected " + std::to_string(DstINumUses) +
+                        " used operands but found " +
+                        std::to_string(Dst->getNumChildren()) +
+                        " explicit ones and " + std::to_string(NumDefaultOps) +
+                        " default ones");
 
-      DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
-      for (const auto *DefaultOp : DefaultOps->args()) {
-        // Look through ValueType operators.
-        if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) {
-          if (const DefInit *DefaultDagOperator =
-                  dyn_cast<DefInit>(DefaultDagOp->getOperator())) {
-            if (DefaultDagOperator->getDef()->isSubClassOf("ValueType"))
-              DefaultOp = DefaultDagOp->getArg(0);
-          }
-        }
+  return DstMIBuilder;
+}
+
+Error GlobalISelEmitter::importDefaultOperandRenderers(
+    BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const {
 
-        if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
-          DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
-          continue;
-        }
 
-        if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
-          DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
-          continue;
-        }
 
-        return failedImport("Could not add default op");
-      }
 
-      continue;
-    }
-
-    if (auto Error = importExplicitUseRenderer(
-            DstMIBuilder, Dst->getChild(Child), InsnMatcher))
-      return std::move(Error);
-    ++Child;
-  }
-
-  return DstMIBuilder;
+  return Error::success();
 }
 
 Error GlobalISelEmitter::importImplicitDefRenderers(
     BuildMIAction &DstMIBuilder,
     const std::vector<Record *> &ImplicitDefs) const {
   if (!ImplicitDefs.empty())
     return failedImport("Pattern defines a physical register");
   return Error::success();