[TableGen] Support combining AssemblerPredicates with ORs

[simoncook]

Summary

For context, the proposed RISC-V bit manipulation extension has a subset
of instructions which require one of two SubtargetFeatures to be
enabled, 'zbb' or 'zbp', and there is no defined feature which both of
these can imply to use as a constraint either (see comments in D65649).

AssemblerPredicates allow multiple SubtargetFeatures to be declared in
the "AssemblerCondString" field, separated by commas, and this means
that the two features must both be enabled. There is no equivalent to
say that _either_ feature X or feature Y must be enabled, short of
creating a dummy SubtargetFeature for this purpose and having features
X and Y imply the new feature.

To solve the case where X or Y is needed without adding a new feature,
and to better match a typical TableGen style, this replaces the existing
"AssemblerCondString" with a dag "AssemblerCondDag" which represents the
same information. Two operators are defined for use with AssemblerCondDag,
"all_of", which matches the current behaviour, and "any_of", which adds
the new proposed ORing features functionality.

Changes to all current backends are mechanical to support the replaced
functionality, and are NFCI.

At this stage, it is illegal to combine features with ands and ors in
a single AssemblerCondDag. I suspect this case is sufficiently rare
that adding more complex changes to support it are unnecessary.

[lewis-revill]

I can't see any issues with the logic of this implementation. It doesn't lend itself well to adapting it in the future if we want to be able to combine the operators, but I'd expect that would require a more disruptive rewrite so I'm not too concerned about that right now. See comments though.

llvm/include/llvm/MC/MCInstPrinter.h

135

Nitpick: Realign comments in this enum

llvm/lib/MC/MCInstPrinter.cpp

149

I don't know this code well enough to know if this is feasible but could this work by instead checking at this point if the pattern is an 'or' pattern, and selecting using 'any_of' if that's the case? We could then avoid adding the K_Or conditions.

[luismarques]

This seems reasonable. Looking forward to seeing this fleshed out with tests.
I see no problem with not supporting both AND and OR at the same time for now, as that could be added later if the need becomes clear.

llvm/include/llvm/Target/Target.td

664

Nitpick: this could benefit from a deeper edit to better reflect the new semantics, in a clear way. Be sure to clarify that , and | are currently mutually exclusive.

llvm/utils/TableGen/SubtargetFeatureInfo.cpp

128

Better to put something that indicates that this isn't currently implemented, but could be supported.

[simoncook]

Thanks for the feedback @luismarques and @lewis-revill.

I think regarding combining operators, it's still possible to do this by adding multiple Predicates on an Instruction definition, and these would still combine as an add (see my comment about GORCI), so the limitation is just about being in a single AsmPredicate definition. I agree that if we wanted to support this in a single AsmPredicate, then the change would be much more invasive, and since this appears to be the first instance that an or would be useful, combining ands and ors is probably sufficiently rare that refactoring it without a known use case may not be worth it; for now I'll document this limitation.

llvm/lib/MC/MCInstPrinter.cpp

149

It's not possible to do this in this case, since the tests here are made up of more than one predicate, you end up with a list of things which must all be true, but with some with this or case in the middle. As an example of the set of predicates that make it here (taken from RISCVGenAsmWriter.inc

// (GORCI GPR:$rd, GPR:$rs, { 1, 1, 1, 1, 0 }) - 327
{AliasPatternCond::K_RegClass, RISCV::GPRRegClassID},
{AliasPatternCond::K_RegClass, RISCV::GPRRegClassID},
{AliasPatternCond::K_Imm, uint32_t(30)},
{AliasPatternCond::K_OrFeature, RISCV::FeatureExtZbb},
{AliasPatternCond::K_OrFeature, RISCV::FeatureExtZbp},
{AliasPatternCond::K_EndOrFeatures, 0},
{AliasPatternCond::K_NegFeature, RISCV::Feature64Bit},

So in this case we only want to use this Asm string if the types match (the first three lines), and we have Zbb or Zbp in addition to not being 64-bit. Because of this I can't switch to using any_of because I'll match the wrong things. Adding the or features with the end of list marker meant I could keep this pattern and do a less invasive change. I suspect doing anything more complex might require a more in-depth change, I'm not sure if anyone who knows this part of the compiler might have other thoughts?

[simoncook]

Incorporate feedback, add test of disassembler and assembly matching test (asmwriter test is WIP)

[simoncook]

Add AsmWriter test

[simoncook]

Add test for RISCV Instruction Compression, so now all uses of AssemblerCondString are covered by this patch.

[evandro]

It's a logical addition to the semantics of features. Though at the moment RV is probably the only user of this addition, the eventual patch implementing it should not include the RV specific changes, which would be better in a separate patch.

[simoncook]

In D74338#1875026, @evandro wrote:

It's a logical addition to the semantics of features. Though at the moment RV is probably the only user of this addition, the eventual patch implementing it should not include the RV specific changes, which would be better in a separate patch.

That’s my plan, they’re just currently put together to demonstrate. I’ll separate them before submitting (the RV part will move to the bitmanip MC patch)

[ostannard]

We have a similar situation in the ARM backend, where there are a few move/load/store instructions operating on FP regs, which are available with either FeatureVFPv2_SP or HasIntegerMVEOps. We solved this by adding new target features for these common instructions, and adding dependencies from the other features to them, so that they get enabled whenever the "real" features are enabled. This works, but has the downside that clang now needs to disable these features when disabling the VFP/MVE features. This patch looks like a better solution to the problem, since clang doesn't need to know about the shared instructions.

[simoncook]

Following feedback from @nhaehnle (http://lists.llvm.org/pipermail/llvm-dev/2020-February/139186.html) I have re-designed this to look more TableGen like (i.e. using DAGs instead of strings to describe the predicate). I have declared two operators any_of and all_of which I think read better than and and or in these cases when just looking at the target files.

• I have removed the RISC-V bitmanip changes I want to support (I'll rebase D65649 on this to remove the circular dependency).
• Added tests for existing functionality and new or functionality.
• Changes to all backends are mechanical, no functional changes are intended, everything still passes with ninja check-llvm on my side.

I may need to improve some of the emitters I've touched, in particular RISCVCompressInstEmitter, but I think this is sufficient to carry on discussing the method of my proposed change.

[nhaehnle]

Thank you for doing this, much appreciated. LGTM.

[lenary]

llvm/include/llvm/Target/Target.td

661

This should document that you cannot do (any_of Pred1, (all_of Pred2, Pred3)), but you can do:

def Pred23 = AssemblerPredicate<(all_of Pred2, Pred3)>;
... = AssemblerPredicate<(any_of Pred1, Pred23)>;

[evandro]

It'd be nice if a single predicate wouldn't need all_of, but I don't feel strongly about it.

[simoncook]

In D74338#1915415, @evandro wrote:

It'd be nice if a single predicate wouldn't need all_of, but I don't feel strongly about it.

I was thinking about this when implementing the patch originally. I opted against that because it would be unlike other uses of dags in TableGen. I'm thinking in particular about RegisterClasses, where even for just a "stack pointer register class" we still do (add R2) in the definition.

llvm/include/llvm/MC/MCInstPrinter.h

struct AliasPattern {
   uint8_t NumOperands;
   uint8_t NumConds;
 };
 
 struct AliasPatternCond {
   enum CondKind : uint8_t {
     K_Feature,    // Match only if a feature is enabled.
     K_NegFeature, // Match only if a feature is disabled.
+    K_OrFeature,  // Match only if one of a set of features is enabled.
+    K_OrNegFeature,  // Match only if one of a set of features is disabled.
+    K_EndOrFeatures, // Note end of list of K_Or(Neg)?Features.
     K_Ignore,     // Match any operand.
     K_Reg,        // Match a specific register.
     K_TiedReg,    // Match another already matched register.
     K_Imm,        // Match a specific immediate.
     K_RegClass,   // Match registers in a class.
     K_Custom,     // Call custom matcher by index.
   };
 

llvm/include/llvm/Target/Target.td

class Predicate<string cond> {
   /// matcher, this is true.  Targets should set this by inheriting their
   /// feature from the AssemblerPredicate class in addition to Predicate.
   bit AssemblerMatcherPredicate = 0;
 
   /// AssemblerCondString - Name of the subtarget feature being tested used
   /// as alternative condition string used for assembler matcher.
   /// e.g. "ModeThumb" is translated to "(Bits & ModeThumb) != 0".
   ///      "!ModeThumb" is translated to "(Bits & ModeThumb) == 0".
-  /// It can also list multiple features separated by ",".
+  /// It can also list multiple features separated by "," or "|".
   /// e.g. "ModeThumb,FeatureThumb2" is translated to
   ///      "(Bits & ModeThumb) != 0 && (Bits & FeatureThumb2) != 0".
+  /// e.g. "ModeTumb|FeatureThumb2" is translated to
+  ///      "(Bits & ModeThumb) != 0 || (Bits & FeatureThumb2) != 0".
   string AssemblerCondString = "";
 
   /// PredicateName - User-level name to use for the predicate. Mainly for use
   /// in diagnostics such as missing feature errors in the asm matcher.
   string PredicateName = "";
 
   /// Setting this to '1' indicates that the predicate must be recomputed on
   /// every function change. Most predicates can leave this at '0'.

llvm/lib/MC/MCInstPrinter.cpp

if (!Annot.empty()) {
     } else
       OS << " " << MAI.getCommentString() << " " << Annot;
   }
 }
 
 static bool matchAliasCondition(const MCInst &MI, const MCSubtargetInfo *STI,
                                 const MCRegisterInfo &MRI, unsigned &OpIdx,
                                 const AliasMatchingData &M,
-                                const AliasPatternCond &C) {
+                                const AliasPatternCond &C,
+                                bool &OrPredicateResult) {
   // Feature tests are special, they don't consume operands.
   if (C.Kind == AliasPatternCond::K_Feature)
     return STI->getFeatureBits().test(C.Value);
   if (C.Kind == AliasPatternCond::K_NegFeature)
     return !STI->getFeatureBits().test(C.Value);
+  // For feature tests where just one feature is required in a list, set the
+  // predicate result bit to whether the expression will return true, and only
+  // return the real result at the end of list marker.
+  if (C.Kind == AliasPatternCond::K_OrFeature) {
+    OrPredicateResult |= STI->getFeatureBits().test(C.Value);
+    return true;
+  }
+  if (C.Kind == AliasPatternCond::K_OrNegFeature) {
+    OrPredicateResult |= !(STI->getFeatureBits().test(C.Value));
+    return true;
+  }
+  if (C.Kind == AliasPatternCond::K_EndOrFeatures) {
+    bool Res = OrPredicateResult;
+    OrPredicateResult = false;
+    return Res;
+  }
 
   // Get and consume an operand.
   const MCOperand &Opnd = MI.getOperand(OpIdx);
   ++OpIdx;
 
   // Check the specific condition for the operand.
   switch (C.Kind) {
   case AliasPatternCond::K_Imm:
static bool matchAliasCondition(const MCInst &MI, const MCSubtargetInfo *STI,
   case AliasPatternCond::K_Custom:
     // Operand must match some custom criteria.
     return M.ValidateMCOperand(Opnd, *STI, C.Value);
   case AliasPatternCond::K_Ignore:
     // Operand can be anything.
     return true;
   case AliasPatternCond::K_Feature:
   case AliasPatternCond::K_NegFeature:
+  case AliasPatternCond::K_OrFeature:
+  case AliasPatternCond::K_OrNegFeature:
+  case AliasPatternCond::K_EndOrFeatures:
     llvm_unreachable("handled earlier");
   }
   llvm_unreachable("invalid kind");
 }
 
 const char *MCInstPrinter::matchAliasPatterns(const MCInst *MI,
                                               const MCSubtargetInfo *STI,
                                               const AliasMatchingData &M) {
for (const AliasPattern &P : Patterns) {
     // Check operand count first.
     if (MI->getNumOperands() != P.NumOperands)
       return nullptr;
 
     // Test all conditions for this pattern.
     ArrayRef<AliasPatternCond> Conds =
         M.PatternConds.slice(P.AliasCondStart, P.NumConds);
     unsigned OpIdx = 0;
+    bool OrPredicateResult = false;
     if (llvm::all_of(Conds, [&](const AliasPatternCond &C) {
-          return matchAliasCondition(*MI, STI, MRI, OpIdx, M, C);
+          return matchAliasCondition(*MI, STI, MRI, OpIdx, M, C,
+                                     OrPredicateResult);
         })) {
       // If all conditions matched, use this asm string.
       AsmStrOffset = P.AsmStrOffset;
       break;
     }
   }
 
   // If no alias matched, don't print an alias.

llvm/lib/Target/RISCV/RISCV.td

def FeatureExtZbt
     : SubtargetFeature<"zbt", "HasStdExtZbt", "true",
                        "'Zbt' (Ternary Bit Manipulation Instructions)">;
 def HasStdExtZbt : Predicate<"Subtarget->hasStdExtZbt()">,
                            AssemblerPredicate<"FeatureExtZbt">;
 
 // For instructions that belong to both the basic and the permutation subextensions.
 // They should be added if any of the two subextension has been specified.
 def HasStdExtZbbOrZbp
-    : Predicate<"Subtarget->hasStdExtZbb() || Subtarget->hasStdExtZbp()">;
+    : Predicate<"Subtarget->hasStdExtZbb() || Subtarget->hasStdExtZbp()">,
+      AssemblerPredicate<"FeatureExtZbb|FeatureExtZbp">;
 
 def FeatureStdExtB
     : SubtargetFeature<"b", "HasStdExtB", "true",
                        "'B' (Bit Manipulation Instructions)",
                                 [FeatureExtZbb,
                                  FeatureExtZbc,
                                  FeatureExtZbe,
                                  FeatureExtZbf,

llvm/utils/TableGen/AsmWriterEmitter.cpp

for (auto &Alias : Aliases.second) {
           return R->getValueAsBit("AssemblerMatcherPredicate");
         });
       }
 
       for (auto I = ReqFeatures.cbegin(); I != ReqFeatures.cend(); I++) {
         Record *R = *I;
         StringRef AsmCondString = R->getValueAsString("AssemblerCondString");
 
-        // AsmCondString has syntax [!]F(,[!]F)*
+        // AsmCondString has syntax [!]F([,|][!]F)*
+        if (AsmCondString.find(',') != StringRef::npos &&
+            AsmCondString.find('|') != StringRef::npos)
+          PrintFatalError(R->getLoc(),
+                          "Cannot combine operators in AsmPredicate!");
+        bool IsOr = AsmCondString.find('|') != StringRef::npos;
         SmallVector<StringRef, 4> Ops;
-        SplitString(AsmCondString, Ops, ",");
+        SplitString(AsmCondString, Ops, ",|");
         assert(!Ops.empty() && "AssemblerCondString cannot be empty");
 
         for (StringRef Op : Ops) {
           assert(!Op.empty() && "Empty operator");
           bool IsNeg = Op[0] == '!';
           StringRef Feature = Op.drop_front(IsNeg ? 1 : 0);
           IAP.addCond(
-              std::string(formatv("AliasPatternCond::K_{0}Feature, {1}::{2}",
-                                  IsNeg ? "Neg" : "", Namespace, Feature)));
-        }
+              std::string(formatv("AliasPatternCond::K_{0}{1}Feature, {2}::{3}",
+                                  IsOr ? "Or" : "", IsNeg ? "Neg" : "",
+                                  Namespace, Feature)));
+        }
+        // If an AsmPredicate with ors is used, note end of list should these
+        // be combined.
+        if (IsOr)
+          IAP.addCond("AliasPatternCond::K_EndOrFeatures, 0");
       }
 
       IAPrinterMap[Aliases.first].push_back(std::move(IAP));
     }
   }
 
   //////////////////////////////
   // Write out the printAliasInstr function

llvm/utils/TableGen/FixedLenDecoderEmitter.cpp

for (unsigned i = 0; i < Predicates->size(); ++i) {
     StringRef P = Pred->getValueAsString("AssemblerCondString");
 
     if (P.empty())
       continue;
 
     if (!IsFirstEmission)
       o << " && ";
 
-    std::pair<StringRef, StringRef> pairs = P.split(',');
+    if (P.find(',') != StringRef::npos && P.find('|') != StringRef::npos)
+      PrintFatalError(Pred->getLoc(),
+                      "Cannot combine operators in AsmPredicate!");
+    bool SplitOr = P.find('|') != StringRef::npos;
+
+    if (SplitOr)
+      o << "(";
+    std::pair<StringRef, StringRef> pairs =
+      P.split(SplitOr ? '|' : ',');
     while (!pairs.second.empty()) {
       emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace);
+      if (SplitOr)
+        o << " || ";
+      else
         o << " && ";
-      pairs = pairs.second.split(',');
+      pairs = pairs.second.split(SplitOr ? '|' : ',');
     }
     emitSinglePredicateMatch(o, pairs.first, Emitter->PredicateNamespace);
+    if (SplitOr)
+      o << ")";
     IsFirstEmission = false;
   }
   return !Predicates->empty();
 }
 
 bool FilterChooser::doesOpcodeNeedPredicate(unsigned Opc) const {
   ListInit *Predicates =
       AllInstructions[Opc].EncodingDef->getValueAsListInit("Predicates");

llvm/utils/TableGen/SubtargetFeatureInfo.cpp

void SubtargetFeatureInfo::emitComputeAssemblerAvailableFeatures(
   OS << "  FeatureBitset Features;\n";
   for (const auto &SF : SubtargetFeatures) {
     const SubtargetFeatureInfo &SFI = SF.second;
 
     OS << "  if (";
     std::string CondStorage =
         std::string(SFI.TheDef->getValueAsString("AssemblerCondString"));
     StringRef Conds = CondStorage;
-    std::pair<StringRef, StringRef> Comma = Conds.split(',');
+    if (Conds.find(',') != StringRef::npos &&
+        Conds.find('|') != StringRef::npos)
+      PrintFatalError(SFI.TheDef->getLoc(),
+                      "Cannot combine operators in AsmPredicate!");
+    bool SplitOr = Conds.find('|') != StringRef::npos;
+    std::pair<StringRef, StringRef> Comma =
+        Conds.split(SplitOr ? '|' : ',');
     bool First = true;
     do {
-      if (!First)
+      if (!First) {
+        if (SplitOr)
+          OS << " || ";
+        else
           OS << " && ";
+      }
 
       bool Neg = false;
       StringRef Cond = Comma.first;
       if (Cond[0] == '!') {
         Neg = true;
         Cond = Cond.substr(1);
       }
 
       OS << "(";
       if (Neg)
         OS << "!";
       OS << "FB[" << TargetName << "::" << Cond << "])";
 
       if (Comma.second.empty())
         break;
 
       First = false;
-      Comma = Comma.second.split(',');
+      Comma = Comma.second.split(SplitOr ? '|' : ',');
     } while (true);
 
     OS << ")\n";
     OS << "    Features.set(" << SFI.getEnumBitName() << ");\n";
   }
   OS << "  return Features;\n";
   OS << "}\n\n";
 }