[GlobalISel] Generate selector with predicates; use it for FP binops.

[ab]

Summary

This emits (rule-level) checks for pattern predicates. That mostly includes
subtarget feature checks. This lets us emit a selector for basic FP binops.

Using all predicates as-is in the selector emitter is not going to be
trivial in general: predicates can be arbitrary code (running in
a <Target>DAGToDAGISel member), so, over time, we've grown some pretty
interesting uses.

In the long run, we'll want to either:

• add first-class support for the different families of predicates
• add some mappings from DAGToDAGISel code to the GISel equivalent

Or a combination of both.

I originally tried to express each Predicate as a RuleMatcher
predicate child, but, without the extra checking and grouping of
predicate families, that just looked like noisy boilerplate.

In the meantime, use the aggregate raw predicate check code string.

[kristof.beyls]

utils/TableGen/GlobalISelEmitter.cpp

366–368

I've gotten the feedback that most developers don't really understand how the auto-generated "magic" works for DAGISel.
So far, I think the current design is pretty easy to understand in comparison. I've tried being picky in this area before about things like naming to keep the code as-easy-to-understand as possible.
Maybe the 3 variables here could use a short comment in that respect?
Maybe something like

/// optional code string that indicates when this rule is legal
Optional<std::string> Predicate;
/// list of matchers that all need to evaluate true for the current IR node to match pattern P.
std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
/// re-writing actions that need to be taken when the current IR node matches pattern P and Predicate is true.
std::vector<std::unique_ptr<MatchAction>> Actions;

Please note that I haven't tried hard to make the comment fully factual correct - I'm hoping Daniel or Ahmed will be able to quickly make those comments factually correct.

392–408

I think it's slightly easier to read if the assert would go before any of the code-emitting code.
It makes it slightly easier to read what code gets generated.

[dsanders]

This needs a testcase.

utils/TableGen/GlobalISelEmitter.cpp

366

I'd prefer it if we did these predicates the same way as for Instructions and Operands (i.e. with PredicateListMatcher<RulePredicateMatcher>). This is because I'm trying to push the SelectionDAG dependency out of the *Matcher classes so we can eventually import pure-GlobalISel rules in addition to the imported SelectionDAG rules. I also expect we'll eventually have GlobalISel-specific predicates that control when rules are applied (e.g. ISel, Pseudo-expansion, etc.)

Reaching that point isn't a near term goal though so I don't have any strong objections to importing the whole predicate expression for now and making it more precise later

366–368

These comments are accurate. I'd add a FIXME saying that Matchers is only allowed to be 1-element long for now until we have a way to match multiple independent instructions.

[ab]

WIP: only recognize predicates that map to Subtarget features (the unfortunately named AssemblerPredicate). Those should always be supported.

I grabbed the feature flags off of the subtarget. We should do something similar to the asm matcher and cache the combined feature flags. I'll look into deduplicating the various computeAvailableFeatures instances; we could also generate that code in the selector itself. Either way, that gives us support for flag logic for free (e.g., "FeatureFoo,!FeatureBar").

In the meantime, what do you folks think?

[ab]

In D29478#665821, @dsanders wrote:

This needs a testcase.

Right! I've been wanting to write tablegen tests forever but never remember. I guess it just doesn't come naturally in these parts ;) Done in r294075.

utils/TableGen/GlobalISelEmitter.cpp

366

Yeah, that's what I originally did, but it felt quite boilerplate-y, so I figured we keep it simple in the meantime. Either works though.

366–368

Done with a few tweaks in r294077, let me know if you spot anything else!

392–408

Fair enough; done.

[dsanders]

In D29478#666554, @ab wrote:

In D29478#665821, @dsanders wrote:

This needs a testcase.

Right! I've been wanting to write tablegen tests forever but never remember. I guess it just doesn't come naturally in these parts ;) Done in r294075.

Sorry for being ambiguous here. I meant a test case that checks the output for G_FADD and the other newly-added FPU operations but having just checked test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir it seems we're re-using some existing tests from when they were added to the C++ implementation.

Thanks for adding tablegen tests. I'll make sure my patches update them too.

WIP: only recognize predicates that map to Subtarget features (the unfortunately named AssemblerPredicate). Those should always be supported.

I grabbed the feature flags off of the subtarget. We should do something similar to the asm matcher and cache the combined feature flags.
I'll look into deduplicating the various computeAvailableFeatures instances; we could also generate that code in the selector itself. Either way,
that gives us support for flag logic for free (e.g., "FeatureFoo,!FeatureBar").

In the meantime, what do you folks think?

IIRC, SelectionDAG only uses the Predicate class and the MC layer only uses AssemblerPredicate. It's probably safest to stick to that but there's some advantages to the AssemblerPredicate way so it makes sense to make use that approach in GlobalISel where possible. The main one I see is that it's possible to test multiple predicates simultaneously. If we do use AssemblerPredicates in GlobalISel, we shouldn't continue to call it AssemblerPredicate though.

I should mention that AArch64 has a few Predicates (e.g. IsLE) that don't have an AssemblerPredicate. We'll need to fix that. Also, Mips has an AssemblerPredicate that lacks a Predicate because it only makes sense to the assembly (UseTCCInDiv).

[ab]

In D29478#667093, @dsanders wrote:

In D29478#666554, @ab wrote:

In the meantime, what do you folks think?

IIRC, SelectionDAG only uses the Predicate class and the MC layer only uses AssemblerPredicate. It's probably safest to stick to that but there's some advantages to the AssemblerPredicate way so it makes sense to make use that approach in GlobalISel where possible. The main one I see is that it's possible to test multiple predicates simultaneously. If we do use AssemblerPredicates in GlobalISel, we shouldn't continue to call it AssemblerPredicate though.

You're right on all points. I was thinking we could split AssemblerPredicate into something like SubtargetFeaturePredicate and AssemblerPredicate: what's interesting to us is that AssemblerPredicates only need an MCSubtargetInfo. SDAG Predicates have arbitrarily weird code that we will never be able to support in the general case.

I should mention that AArch64 has a few Predicates (e.g. IsLE) that don't have an AssemblerPredicate. We'll need to fix that. Also, Mips has an AssemblerPredicate that lacks a Predicate because it only makes sense to the assembly (UseTCCInDiv).

These Predicates should probably also have a way of defining GISel equivalence.

include/llvm/Target/GlobalISel/SelectionDAGCompat.td

 def : GINodeEquiv<G_LSHR, srl>;
 def : GINodeEquiv<G_ASHR, sra>;
 
 def : GINodeEquiv<G_SDIV, sdiv>;
 def : GINodeEquiv<G_UDIV, udiv>;
 def : GINodeEquiv<G_SREM, srem>;
 def : GINodeEquiv<G_UREM, urem>;
 
+def : GINodeEquiv<G_FADD, fadd>;
+def : GINodeEquiv<G_FSUB, fsub>;
+def : GINodeEquiv<G_FMUL, fmul>;
+def : GINodeEquiv<G_FDIV, fdiv>;
+def : GINodeEquiv<G_FREM, frem>;
+
 def : GINodeEquiv<G_BR, br>;

lib/Target/AArch64/AArch64InstructionSelector.cpp

if (OpSize == 32) {
       case TargetOpcode::G_ASHR:
         return AArch64::ASRVXr;
       default:
         return GenericOpc;
       }
     }
   case AArch64::FPRRegBankID:
     switch (OpSize) {
-    case 32:
-      switch (GenericOpc) {
-      case TargetOpcode::G_FADD:
-        return AArch64::FADDSrr;
-      case TargetOpcode::G_FSUB:
-        return AArch64::FSUBSrr;
-      case TargetOpcode::G_FMUL:
-        return AArch64::FMULSrr;
-      case TargetOpcode::G_FDIV:
-        return AArch64::FDIVSrr;
-      default:
-        return GenericOpc;
-      }
     case 64:
       switch (GenericOpc) {
-      case TargetOpcode::G_FADD:
-        return AArch64::FADDDrr;
-      case TargetOpcode::G_FSUB:
-        return AArch64::FSUBDrr;
-      case TargetOpcode::G_FMUL:
-        return AArch64::FMULDrr;
-      case TargetOpcode::G_FDIV:
-        return AArch64::FDIVDrr;
       case TargetOpcode::G_OR:
         return AArch64::ORRv8i8;
       default:
         return GenericOpc;
       }
     }
   };
   return GenericOpc;
case TargetOpcode::G_MUL: {
 
     I.addOperand(MachineOperand::CreateReg(ZeroReg, /*isDef=*/false));
 
     // Now that we selected an opcode, we need to constrain the register
     // operands to use appropriate classes.
     return constrainSelectedInstRegOperands(I, TII, TRI, RBI);
   }
 
-  case TargetOpcode::G_FADD:
-  case TargetOpcode::G_FSUB:
-  case TargetOpcode::G_FMUL:
-  case TargetOpcode::G_FDIV:
-
   case TargetOpcode::G_OR:
   case TargetOpcode::G_SHL:
   case TargetOpcode::G_LSHR:
   case TargetOpcode::G_ASHR:
   case TargetOpcode::G_GEP: {
     // Reject the various things we don't support yet.
     if (unsupportedBinOp(I, RBI, MRI, TRI))
       return false;

test/TableGen/GlobalISelEmitter.td

 //===- Test the function definition boilerplate. --------------------------===//
 
 // CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I) const {
 // CHECK: const MachineRegisterInfo &MRI = I.getParent()->getParent()->getRegInfo();
 
 
 //===- Test a simple pattern with regclass operands. ----------------------===//
 
-// CHECK: if ((I.getOpcode() == TargetOpcode::G_ADD) &&
+// CHECK: if (true &&
+// CHECK-NEXT: (I.getOpcode() == TargetOpcode::G_ADD) &&
 // CHECK-NEXT: (((MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) &&
 // CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) &&
 // CHECK-NEXT: (((MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) &&
 // CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) &&
 // CHECK-NEXT: (((MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) &&
 // CHECK-NEXT:  ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(2).getReg(), MRI, TRI)))))) {
 
 // CHECK-NEXT:   // (add:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (ADD:i32 GPR32:i32:$src1, GPR32:i32:$src2)
 // CHECK-NEXT:   I.setDesc(TII.get(MyTarget::ADD));
 // CHECK-NEXT:   constrainSelectedInstRegOperands(I, TII, TRI, RBI);
 // CHECK-NEXT:   return true;
 // CHECK-NEXT: }
 
 def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2),
             [(set GPR32:$dst, (add GPR32:$src1, GPR32:$src2))]>;
 
 //===- Test a pattern with an MBB operand. --------------------------------===//
 
-// CHECK: if ((I.getOpcode() == TargetOpcode::G_BR) &&
+// CHECK: if (true &&
+// CHECK-NEXT: (I.getOpcode() == TargetOpcode::G_BR) &&
 // CHECK-NEXT: (((I.getOperand(0).isMBB())))) {
 
 // CHECK-NEXT:   // (br (bb:Other):$target) => (BR (bb:Other):$target)
 // CHECK-NEXT:   I.setDesc(TII.get(MyTarget::BR));
 // CHECK-NEXT:   constrainSelectedInstRegOperands(I, TII, TRI, RBI);
 // CHECK-NEXT:   return true;
 // CHECK-NEXT: }
 
 def BR : I<(outs), (ins unknown:$target),
             [(br bb:$target)]>;
+
+//===- Test a pattern with a predicate. -----------------------------------===//
+
+// CHECK: if ((STI.getFeatureBits()[MyTarget::FeatureFancyBR_A]) &&
+// CHECK-NEXT: (STI.getFeatureBits()[MyTarget::FeatureFancyBR_A]) &&
+// CHECK-NEXT: (I.getOpcode() == TargetOpcode::G_BR) &&
+// CHECK-NEXT: (((I.getOperand(0).isMBB())))) {
+
+// CHECK-NEXT:   // (br (bb:Other):$target) => (FancyBR (bb:Other):$target)
+// CHECK-NEXT:   I.setDesc(TII.get(MyTarget::FancyBR));
+// CHECK-NEXT:   constrainSelectedInstRegOperands(I, TII, TRI, RBI);
+// CHECK-NEXT:   return true;
+// CHECK-NEXT: }
+
+def HasFancyBR_A : Predicate<"HasFancyBR_A">,
+                   AssemblerPredicate<"FeatureFancyBR_A", "fancy-br-a">;
+def HasFancyBR_B : Predicate<"HasFancyBR_B">,
+                   AssemblerPredicate<"FeatureFancyBR_A", "fancy-br-a">;
+
+def FancyBR : I<(outs), (ins unknown:$target),
+                [(br bb:$target)]>,
+              Requires<[HasFancyBR_A, HasFancyBR_B]>;

utils/TableGen/GlobalISelEmitter.cpp

void emitCxxPredicateExpr(raw_ostream &OS, const StringRef InsnVarName) const {
     for (const auto &Operand : Operands) {
       OS << " &&\n(";
       Operand.emitCxxPredicateExpr(OS, InsnVarName);
       OS << ")";
     }
   }
 };
 
+/// Generates code to check a predicate on a rule.
+///
+/// Typical predicates include:
+/// * The subtarget has some feature flag.
+/// * The function has a certain attribute (e.g., minsize).
+class RulePredicateMatcher {
+public:
+  virtual ~RulePredicateMatcher() {}
+
+  /// Emit a C++ expression that tests whether the rule matches the
+  /// (context-insensitive) predicate.
+  virtual void emitCxxPredicateExpr(raw_ostream &OS) const = 0;
+};
+
+/// Generates code to check a subtarget feature.
+class SubtargetFeatureRuleMatcher : public RulePredicateMatcher {
+protected:
+  std::string Feature;
+
+public:
+  SubtargetFeatureRuleMatcher(std::string Feature) : Feature(Feature) {}
+
+  void emitCxxPredicateExpr(raw_ostream &OS) const override {
+    OS << "STI.getFeatureBits()[" << Feature << "]";
+  }
+};
+
 //===- Actions ------------------------------------------------------------===//
 
 /// An action taken when all Matcher predicates succeeded for a parent rule.
 ///
 /// Typical actions include:
 /// * Changing the opcode of an instruction.
 /// * Adding an operand to an instruction.
 class MatchAction {
public:
   MutateOpcodeAction(const CodeGenInstruction *I) : I(I) {}
 
   virtual void emitCxxActionStmts(raw_ostream &OS) const {
     OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
        << "));";
   }
 };
 
-/// Generates code to check that a match rule matches.
-class RuleMatcher {
+/// Generates code to check that a match rule matches, and that a set of
+/// rule-level predicates match.
+///
+/// Typical predicates include:
+/// * The subtarget has some feature flag.
+/// * The function has a certain attribute (e.g., minsize).
+///
+/// This currently supports a single match position but could be extended to
+/// support multiple positions to support div/rem fusion or load-multiple
+/// instructions.
+class RuleMatcher : public PredicateListMatcher<RulePredicateMatcher> {
   /// A list of matchers that all need to succeed for the current rule to match.
   /// FIXME: This currently supports a single match position but could be
   /// extended to support multiple positions to support div/rem fusion or
   /// load-multiple instructions.
   std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
 
   /// A list of actions that need to be taken when all predicates in this rule
   /// have succeeded.
   std::vector<std::unique_ptr<MatchAction>> Actions;
 
 public:
   RuleMatcher() {}
 
   InstructionMatcher &addInstructionMatcher() {
     Matchers.emplace_back(new InstructionMatcher());
     return *Matchers.back();
   }
 
   template <class Kind, class... Args>
   Kind &addAction(Args&&... args) {
     Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
     return *static_cast<Kind *>(Actions.back().get());
   }
 
   void emit(raw_ostream &OS) {
     if (Matchers.empty())
       llvm_unreachable("Unexpected empty matcher!");
 
     // The representation supports rules that require multiple roots such as:
     //    %ptr(p0) = ...
     //    %elt0(s32) = G_LOAD %ptr
     //    %1(p0) = G_ADD %ptr, 4
     //    %elt1(s32) = G_LOAD p0 %1
     // which could be usefully folded into:
     //    %ptr(p0) = ...
     //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
     // on some targets but we don't need to make use of that yet.
     assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
+
     OS << "  if (";
+    emitCxxPredicateListExpr(OS);
+    OS << " &&\n";
     Matchers.front()->emitCxxPredicateExpr(OS, "I");
     OS << ") {\n";
 
     for (const auto &MA : Actions) {
       OS << "    ";
       MA->emitCxxActionStmts(OS);
       OS << "\n";
     }
 
     OS << "    constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n";

 Optional<GlobalISelEmitter::SkipReason>
 GlobalISelEmitter::runOnPattern(const PatternToMatch &P, raw_ostream &OS) {
 
   // Keep track of the matchers and actions to emit.
   RuleMatcher M;
   M.addAction<DebugCommentAction>(P);
 
   // First, analyze the whole pattern.
-  // If the entire pattern has a predicate (e.g., target features), ignore it.
-  if (!P.getPredicates()->getValues().empty())
-    return SkipReason{"Pattern has a predicate"};
+
+  // If the pattern has predicates (e.g., target features), check them.
+  for (Init *PredInit : P.getPredicates()->getValues()) {
+    DefInit *PredDef = dyn_cast<DefInit>(PredInit);
+    if (!PredDef)
+      return SkipReason{"Malformed pattern predicate"};
+    Record *PredRec = PredDef->getDef();
+    if (!PredRec->isSubClassOf("Predicate"))
+      return SkipReason{"Unrecognized pattern predicate"};
+
+    std::string CondString =
+        PredRec->getValueAsString("AssemblerCondString");
+    StringRef Cond = CondString;
+    if (Cond.contains(',') || Cond.contains('!'))
+      return SkipReason{"Pattern predicate is too complicated"};
+
+    M.addPredicate<SubtargetFeatureRuleMatcher>(
+        (Target.getName() + "::" + Cond).str());
+  }
 
   // Physreg imp-defs require additional logic.  Ignore the pattern.
   if (!P.getDstRegs().empty())
     return SkipReason{"Pattern defines a physical register"};
 
   // Next, analyze the pattern operators.
   TreePatternNode *Src = P.getSrcPattern();
   TreePatternNode *Dst = P.getDstPattern();