[TableGen] Add a !listremove() bang operator

[RKSimon]

Summary

This patch proposes to add a !listremove() bang operator to allow us to prune list entries by removing any entries from the first list arg that are also contained in the second list arg.

The particular use case I have in mind is for improved analysis of x86 scheduler models for which I'm hoping to start using the CodeGenProcModel 'Unsupported' features lists, which lists the ISA features a particular model DOESN'T support - with such a diverse and growing list of x86 ISAs, I don't want to have to update all these lists with every ISA change to every model - so I'm intending to keep a single central list of all x86 features, and then have the each model "remove" the features that it supports via a !listremove() - leaving just the unsupported ones.

[lebedev.ri]

Sounds reasonable to me.

[Paul-C-Anagnostopoulos]

I think you have everything covered.

[RKSimon]

Cheers - anybody willing to accept?

[lebedev.ri]

Missing llvm/trunk/utils/kate/llvm-tablegen.xml change.
Thanks.

[RKSimon]

In D139642#3984289, @lebedev.ri wrote:

Missing llvm/trunk/utils/kate/llvm-tablegen.xml change.
Thanks.

Nice catch! Cheers.

llvm/docs/TableGen/ProgRef.rst

 TableGen provides "bang operators" that have a wide variety of uses:
 
 .. productionlist::
    BangOperator: one of
                : !add        !and         !cast        !con         !dag
                : !div        !empty       !eq          !filter      !find
                : !foldl      !foreach     !ge          !getdagop    !gt
                : !head       !if          !interleave  !isa         !le
-               : !listconcat !listsplat   !logtwo      !lt          !mul
-               : !ne         !not         !or          !setdagop    !shl
-               : !size       !sra         !srl         !strconcat   !sub
-               : !subst      !substr      !tail        !xor
+               : !listconcat !listremove  !listsplat   !logtwo      !lt
+               : !mul        !ne          !not         !or          !setdagop
+               : !shl        !size        !sra         !srl         !strconcat
+               : !sub        !subst       !substr      !tail        !xor
 
 The ``!cond`` operator has a slightly different
 syntax compared to other bang operators, so it is defined separately:
 
 .. productionlist::
    CondOperator: !cond
 
 See `Appendix A: Bang Operators`_ for a description of each bang operator.

 ``!le(``\ *a*\ ``,`` *b*\ ``)``
     This operator produces 1 if *a* is less than or equal to *b*; 0 otherwise.
     The arguments must be ``bit``, ``bits``, ``int``, or ``string`` values.
 
 ``!listconcat(``\ *list1*\ ``,`` *list2*\ ``, ...)``
     This operator concatenates the list arguments *list1*, *list2*, etc., and
     produces the resulting list. The lists must have the same element type.
 
+``!listremove(``\ *list1*\ ``,`` *list2*\ ``)``
+    This operator returns a copy of *list1* removing all elements that also occur in
+    *list2*. The lists must have the same element type.
+
 ``!listsplat(``\ *value*\ ``,`` *count*\ ``)``
     This operator produces a list of length *count* whose elements are all
     equal to the *value*. For example, ``!listsplat(42, 3)`` results in
     ``[42, 42, 42]``.
 
 ``!logtwo(``\ *a*\ ``)``
     This operator produces the base 2 log of *a* and produces the integer
     result. The log of 0 or a negative number produces an error. This

llvm/include/llvm/TableGen/Record.h

enum BinaryOp : uint8_t {
     AND,
     OR,
     XOR,
     SHL,
     SRA,
     SRL,
     LISTCONCAT,
     LISTSPLAT,
+    LISTREMOVE,
     STRCONCAT,
     INTERLEAVE,
     CONCAT,
     EQ,
     NE,
     LE,
     LT,
     GE,
Init *getOperand(unsigned i) const override {
     case 1: return getRHS();
     }
   }
 
   BinaryOp getOpcode() const { return (BinaryOp)Opc; }
   Init *getLHS() const { return LHS; }
   Init *getRHS() const { return RHS; }
 
+  std::optional<bool> CompareInit(unsigned Opc, Init *LHS, Init *RHS) const;
+
   // Fold - If possible, fold this to a simpler init.  Return this if not
   // possible to fold.
   Init *Fold(Record *CurRec) const;
 
   Init *resolveReferences(Resolver &R) const override;
 
   std::string getAsString() const override;
 };

llvm/lib/TableGen/Record.cpp

Init *BinOpInit::getListConcat(TypedInit *LHS, Init *RHS) {
 
   // Shortcut for the common case of concatenating two lists.
    if (const ListInit *LHSList = dyn_cast<ListInit>(LHS))
      if (const ListInit *RHSList = dyn_cast<ListInit>(RHS))
        return ConcatListInits(LHSList, RHSList);
    return BinOpInit::get(BinOpInit::LISTCONCAT, LHS, RHS, LHS->getType());
 }
 
+std::optional<bool> BinOpInit::CompareInit(unsigned Opc, Init *LHS, Init *RHS) const {
+   // First see if we have two bit, bits, or int.
+   IntInit *LHSi = dyn_cast_or_null<IntInit>(
+       LHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
+   IntInit *RHSi = dyn_cast_or_null<IntInit>(
+       RHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
+
+   if (LHSi && RHSi) {
+     bool Result;
+     switch (Opc) {
+     case EQ:
+       Result = LHSi->getValue() == RHSi->getValue();
+       break;
+     case NE:
+       Result = LHSi->getValue() != RHSi->getValue();
+       break;
+     case LE:
+       Result = LHSi->getValue() <= RHSi->getValue();
+       break;
+     case LT:
+       Result = LHSi->getValue() < RHSi->getValue();
+       break;
+     case GE:
+       Result = LHSi->getValue() >= RHSi->getValue();
+       break;
+     case GT:
+       Result = LHSi->getValue() > RHSi->getValue();
+       break;
+     default:
+       llvm_unreachable("unhandled comparison");
+     }
+     return Result;
+   }
+
+   // Next try strings.
+   StringInit *LHSs = dyn_cast<StringInit>(LHS);
+   StringInit *RHSs = dyn_cast<StringInit>(RHS);
+
+   if (LHSs && RHSs) {
+     bool Result;
+     switch (Opc) {
+     case EQ:
+       Result = LHSs->getValue() == RHSs->getValue();
+       break;
+     case NE:
+       Result = LHSs->getValue() != RHSs->getValue();
+       break;
+     case LE:
+       Result = LHSs->getValue() <= RHSs->getValue();
+       break;
+     case LT:
+       Result = LHSs->getValue() < RHSs->getValue();
+       break;
+     case GE:
+       Result = LHSs->getValue() >= RHSs->getValue();
+       break;
+     case GT:
+       Result = LHSs->getValue() > RHSs->getValue();
+       break;
+     default:
+       llvm_unreachable("unhandled comparison");
+     }
+     return Result;
+   }
+
+   // Finally, !eq and !ne can be used with records.
+   if (Opc == EQ || Opc == NE) {
+     DefInit *LHSd = dyn_cast<DefInit>(LHS);
+     DefInit *RHSd = dyn_cast<DefInit>(RHS);
+     if (LHSd && RHSd)
+       return (Opc == EQ) ? LHSd == RHSd : LHSd != RHSd;
+   }
+
+   return std::nullopt;
+}
+
  Init *BinOpInit::Fold(Record *CurRec) const {
   switch (getOpcode()) {
   case CONCAT: {
     DagInit *LHSs = dyn_cast<DagInit>(LHS);
     DagInit *RHSs = dyn_cast<DagInit>(RHS);
     if (LHSs && RHSs) {
       DefInit *LOp = dyn_cast<DefInit>(LHSs->getOperator());
       DefInit *ROp = dyn_cast<DefInit>(RHSs->getOperator());
       if ((!LOp && !isa<UnsetInit>(LHSs->getOperator())) ||
case LISTSPLAT: {
     TypedInit *Value = dyn_cast<TypedInit>(LHS);
     IntInit *Size = dyn_cast<IntInit>(RHS);
     if (Value && Size) {
       SmallVector<Init *, 8> Args(Size->getValue(), Value);
       return ListInit::get(Args, Value->getType());
     }
     break;
   }
+  case LISTREMOVE: {
+    ListInit *LHSs = dyn_cast<ListInit>(LHS);
+    ListInit *RHSs = dyn_cast<ListInit>(RHS);
+    if (LHSs && RHSs) {
+      SmallVector<Init *, 8> Args;
+      for (Init *EltLHS : *LHSs) {
+        bool Found = false;
+        for (Init *EltRHS : *RHSs) {
+          if (std::optional<bool> Result = CompareInit(EQ, EltLHS, EltRHS)) {
+            if (*Result) {
+              Found = true;
+              break;
+            }
+          }
+        }
+        if (!Found)
+          Args.push_back(EltLHS);
+      }
+      return ListInit::get(Args, LHSs->getElementType());
+    }
+    break;
+  }
   case STRCONCAT: {
     StringInit *LHSs = dyn_cast<StringInit>(LHS);
     StringInit *RHSs = dyn_cast<StringInit>(RHS);
     if (LHSs && RHSs)
       return ConcatStringInits(LHSs, RHSs);
     break;
   }
   case INTERLEAVE: {
case INTERLEAVE: {
     break;
   }
   case EQ:
   case NE:
   case LE:
   case LT:
   case GE:
   case GT: {
-    // First see if we have two bit, bits, or int.
-    IntInit *LHSi = dyn_cast_or_null<IntInit>(
-        LHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
-    IntInit *RHSi = dyn_cast_or_null<IntInit>(
-        RHS->convertInitializerTo(IntRecTy::get(getRecordKeeper())));
-
-    if (LHSi && RHSi) {
-      bool Result;
-      switch (getOpcode()) {
-      case EQ: Result = LHSi->getValue() == RHSi->getValue(); break;
-      case NE: Result = LHSi->getValue() != RHSi->getValue(); break;
-      case LE: Result = LHSi->getValue() <= RHSi->getValue(); break;
-      case LT: Result = LHSi->getValue() <  RHSi->getValue(); break;
-      case GE: Result = LHSi->getValue() >= RHSi->getValue(); break;
-      case GT: Result = LHSi->getValue() >  RHSi->getValue(); break;
-      default: llvm_unreachable("unhandled comparison");
-      }
-      return BitInit::get(getRecordKeeper(), Result);
-    }
-
-    // Next try strings.
-    StringInit *LHSs = dyn_cast<StringInit>(LHS);
-    StringInit *RHSs = dyn_cast<StringInit>(RHS);
-
-    if (LHSs && RHSs) {
-      bool Result;
-      switch (getOpcode()) {
-      case EQ: Result = LHSs->getValue() == RHSs->getValue(); break;
-      case NE: Result = LHSs->getValue() != RHSs->getValue(); break;
-      case LE: Result = LHSs->getValue() <= RHSs->getValue(); break;
-      case LT: Result = LHSs->getValue() <  RHSs->getValue(); break;
-      case GE: Result = LHSs->getValue() >= RHSs->getValue(); break;
-      case GT: Result = LHSs->getValue() >  RHSs->getValue(); break;
-      default: llvm_unreachable("unhandled comparison");
-      }
-      return BitInit::get(getRecordKeeper(), Result);
-    }
-
-    // Finally, !eq and !ne can be used with records.
-    if (getOpcode() == EQ || getOpcode() == NE) {
-      DefInit *LHSd = dyn_cast<DefInit>(LHS);
-      DefInit *RHSd = dyn_cast<DefInit>(RHS);
-      if (LHSd && RHSd)
-        return BitInit::get(getRecordKeeper(),
-                            (getOpcode() == EQ) ? LHSd == RHSd : LHSd != RHSd);
-    }
-
+    if (std::optional<bool> Result = CompareInit(getOpcode(), LHS, RHS))
+      return BitInit::get(getRecordKeeper(), *Result);
     break;
   }
   case SETDAGOP: {
     DagInit *Dag = dyn_cast<DagInit>(LHS);
     DefInit *Op = dyn_cast<DefInit>(RHS);
     if (Dag && Op) {
       SmallVector<Init*, 8> Args;
       SmallVector<StringInit*, 8> ArgNames;
std::string BinOpInit::getAsString() const {
   case EQ: Result = "!eq"; break;
   case NE: Result = "!ne"; break;
   case LE: Result = "!le"; break;
   case LT: Result = "!lt"; break;
   case GE: Result = "!ge"; break;
   case GT: Result = "!gt"; break;
   case LISTCONCAT: Result = "!listconcat"; break;
   case LISTSPLAT: Result = "!listsplat"; break;
+  case LISTREMOVE: Result = "!listremove"; break;
   case STRCONCAT: Result = "!strconcat"; break;
   case INTERLEAVE: Result = "!interleave"; break;
   case SETDAGOP: Result = "!setdagop"; break;
   }
   return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
 }
 
 static void

llvm/lib/TableGen/TGLexer.h

enum TokKind {
     FalseKW, Field, Foreach, If, In, Include, Int, Let, List, MultiClass,
     String, Then, TrueKW,
 
     // Bang operators.
     XConcat, XADD, XSUB, XMUL, XDIV, XNOT, XLOG2, XAND, XOR, XXOR, XSRA, XSRL,
     XSHL, XListConcat, XListSplat, XStrConcat, XInterleave, XSubstr, XFind,
     XCast, XSubst, XForEach, XFilter, XFoldl, XHead, XTail, XSize, XEmpty, XIf,
     XCond, XEq, XIsA, XDag, XNe, XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
-    XExists,
+    XExists, XListRemove,
 
     // Boolean literals.
     TrueVal, FalseVal,
 
     // Integer value.
     IntVal,
 
     // Binary constant.  Note that these are sized according to the number of

llvm/lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("cast", tgtok::XCast)
     .Case("empty", tgtok::XEmpty)
     .Case("subst", tgtok::XSubst)
     .Case("foldl", tgtok::XFoldl)
     .Case("foreach", tgtok::XForEach)
     .Case("filter", tgtok::XFilter)
     .Case("listconcat", tgtok::XListConcat)
     .Case("listsplat", tgtok::XListSplat)
+    .Case("listremove", tgtok::XListRemove)
     .Case("strconcat", tgtok::XStrConcat)
     .Case("interleave", tgtok::XInterleave)
     .Case("substr", tgtok::XSubstr)
     .Case("find", tgtok::XFind)
     .Cases("setdagop", "setop", tgtok::XSetDagOp) // !setop is deprecated.
     .Cases("getdagop", "getop", tgtok::XGetDagOp) // !getop is deprecated.
     .Case("exists", tgtok::XExists)
     .Default(tgtok::Error);

llvm/lib/TableGen/TGParser.cpp

Init *TGParser::ParseOperation(Record *CurRec, RecTy *ItemType) {
   case tgtok::XEq:
   case tgtok::XNe:
   case tgtok::XLe:
   case tgtok::XLt:
   case tgtok::XGe:
   case tgtok::XGt:
   case tgtok::XListConcat:
   case tgtok::XListSplat:
+  case tgtok::XListRemove:
   case tgtok::XStrConcat:
   case tgtok::XInterleave:
   case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     tgtok::TokKind OpTok = Lex.getCode();
     SMLoc OpLoc = Lex.getLoc();
     Lex.Lex();  // eat the operation
 
     BinOpInit::BinaryOp Code;
case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     case tgtok::XEq:     Code = BinOpInit::EQ; break;
     case tgtok::XNe:     Code = BinOpInit::NE; break;
     case tgtok::XLe:     Code = BinOpInit::LE; break;
     case tgtok::XLt:     Code = BinOpInit::LT; break;
     case tgtok::XGe:     Code = BinOpInit::GE; break;
     case tgtok::XGt:     Code = BinOpInit::GT; break;
     case tgtok::XListConcat: Code = BinOpInit::LISTCONCAT; break;
     case tgtok::XListSplat:  Code = BinOpInit::LISTSPLAT; break;
+    case tgtok::XListRemove: Code = BinOpInit::LISTREMOVE; break;
     case tgtok::XStrConcat:  Code = BinOpInit::STRCONCAT; break;
     case tgtok::XInterleave: Code = BinOpInit::INTERLEAVE; break;
     case tgtok::XSetDagOp:   Code = BinOpInit::SETDAGOP; break;
     }
 
     RecTy *Type = nullptr;
     RecTy *ArgType = nullptr;
     switch (OpTok) {
case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     case tgtok::XLe:
     case tgtok::XLt:
     case tgtok::XGe:
     case tgtok::XGt:
       Type = BitRecTy::get(Records);
       // ArgType for the comparison operators is not yet known.
       break;
     case tgtok::XListConcat:
-      // We don't know the list type until we parse the first argument
+      // We don't know the list type until we parse the first argument.
       ArgType = ItemType;
       break;
     case tgtok::XListSplat:
       // Can't do any typechecking until we parse the first argument.
       break;
+    case tgtok::XListRemove:
+      // We don't know the list type until we parse the first argument.
+      ArgType = ItemType;
+      break;
     case tgtok::XStrConcat:
       Type = StringRecTy::get(Records);
       ArgType = StringRecTy::get(Records);
       break;
     case tgtok::XInterleave:
       Type = StringRecTy::get(Records);
       // The first argument type is not yet known.
     }
for (;;) {
           if (InitList.size() == 2 && !isa<IntRecTy>(ArgType)) {
             Error(InitLoc, Twine("expected second parameter to be an int, got "
                                  "value of type '") +
                                ArgType->getAsString() + "'");
             return nullptr;
           }
           ArgType = nullptr; // Broken invariant: types not identical.
           break;
+        case BinOpInit::LISTREMOVE:
+          if (!isa<ListRecTy>(ArgType)) {
+            Error(InitLoc, Twine("expected a list, got value of type '") +
+                               ArgType->getAsString() + "'");
+            return nullptr;
+          }
+          break;
         case BinOpInit::EQ:
         case BinOpInit::NE:
           if (!ArgType->typeIsConvertibleTo(IntRecTy::get(Records)) &&
               !ArgType->typeIsConvertibleTo(StringRecTy::get(Records)) &&
               !ArgType->typeIsConvertibleTo(RecordRecTy::get(Records, {}))) {
             Error(InitLoc, Twine("expected bit, bits, int, string, or record; "
                                  "got value of type '") + ArgType->getAsString() + 
                                  "'");
case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     }
 
     // listconcat returns a list with type of the argument.
     if (Code == BinOpInit::LISTCONCAT)
       Type = ArgType;
     // listsplat returns a list of type of the *first* argument.
     if (Code == BinOpInit::LISTSPLAT)
       Type = cast<TypedInit>(InitList.front())->getType()->getListTy();
+    // listremove returns a list with type of the argument.
+    if (Code == BinOpInit::LISTREMOVE)
+      Type = ArgType;
 
     // We allow multiple operands to associative operators like !strconcat as
     // shorthand for nesting them.
     if (Code == BinOpInit::STRCONCAT || Code == BinOpInit::LISTCONCAT ||
         Code == BinOpInit::CONCAT || Code == BinOpInit::ADD ||
         Code == BinOpInit::AND || Code == BinOpInit::OR ||
         Code == BinOpInit::XOR || Code == BinOpInit::MUL) {
       while (InitList.size() > 2) {

 ///   SimpleValue ::= ADDTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= DIVTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SUBTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= LISTCONCATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= LISTSPLATTOK '(' Value ',' Value ')'
+///   SimpleValue ::= LISTREMOVETOK '(' Value ',' Value ')'
 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= COND '(' [Value ':' Value,]+ ')'
 ///
 Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
                                  IDParseMode Mode) {
   Init *R = nullptr;
   switch (Lex.getCode()) {
   default: TokError("Unknown or reserved token when parsing a value"); break;
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XEq:
   case tgtok::XNe:
   case tgtok::XLe:
   case tgtok::XLt:
   case tgtok::XGe:
   case tgtok::XGt:
   case tgtok::XListConcat:
   case tgtok::XListSplat:
+  case tgtok::XListRemove:
   case tgtok::XStrConcat:
   case tgtok::XInterleave:
   case tgtok::XSetDagOp: // Value ::= !binop '(' Value ',' Value ')'
   case tgtok::XIf:
   case tgtok::XCond:
   case tgtok::XFoldl:
   case tgtok::XForEach:
   case tgtok::XFilter:

llvm/test/TableGen/listremove.td

+// RUN: llvm-tblgen %s | FileCheck %s
+
+// CHECK: class X {
+// CHECK:   list<string> T0 = ["foo", "bar"];
+// CHECK:   list<string> T1 = ["foo", "bar"];
+// CHECK:   list<string> T2 = ["bar"];
+// CHECK:   list<string> T3 = ["foo"];
+// CHECK:   list<string> T4 = [];
+// CHECK: }
+
+class X {
+  list<string> T0 = !listremove(["foo", "bar"], []);
+  list<string> T1 = !listremove(["foo", "bar"], ["baz"]);
+  list<string> T2 = !listremove(["foo", "bar"], ["foo"]);
+  list<string> T3 = !listremove(["foo", "bar"], ["bar", "bar"]);
+  list<string> T4 = !listremove(["foo", "bar"], ["bar", "foo"]);
+}

llvm/utils/kate/llvm-tablegen.xml

<list name="bang-operators">
       <item> !and </item>
       <item> !or </item>
       <item> !empty </item>
       <item> !subst </item>
       <item> !foreach </item>
       <item> !strconcat </item>
       <item> !cast </item>
       <item> !listconcat </item>
+      <item> !listreplace </item>
       <item> !listsplat </item>
       <item> !size </item>
       <item> !foldl </item>
       <item> !isa </item>
       <item> !dag </item>
       <item> !le </item>
       <item> !lt </item>
       <item> !ge </item>