[TableGen] Add the !filter bang operator.

[Paul-C-Anagnostopoulos]

Summary

I added the !filter bang operator to simplify various !foldl expressions and to improve efficiency. It eliminates all the intermediate list concatenations required when using !foldl.

I updated the Programmer's Reference and wrote a test.

I used the new operator in various .td files.

[lattner]

Very nice Paul!

llvm/docs/TableGen/ProgRef.rst

 Bang operators
 --------------
 
 TableGen provides "bang operators" that have a wide variety of uses:
 
 .. productionlist::
    BangOperator: one of
                : !add        !and         !cast        !con         !dag 
-               : !empty      !eq          !foldl       !foreach     !ge
-               : !getdagop   !gt          !head        !if          !interleave
-               : !isa        !le          !listconcat  !listsplat   !lt
-               : !mul        !ne          !not         !or          !setdagop
-               : !shl        !size        !sra         !srl         !strconcat
-               : !sub        !subst       !tail        !xor
+               : !empty      !eq          !foldl       !foreach     !filter
+               : !ge         !getdagop    !gt          !head        !if
+               : !interleave !isa         !le          !listconcat  !listsplat
+               : !lt         !mul         !ne          !not         !or
+               : !setdagop   !shl         !size        !sra         !srl
+               : !strconcat  !sub         !subst       !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.
``!empty(``\ *a*\ ``)``
     This operator produces 1 if the string, list, or DAG *a* is empty; 0 otherwise.
     A dag is empty if it has no arguments; the operator does not count.
 
 ``!eq(`` *a*\ `,` *b*\ ``)``
     This operator produces 1 if *a* is equal to *b*; 0 otherwise.
     The arguments must be ``bit``, ``bits``, ``int``, or ``string`` values.
     Use ``!cast<string>`` to compare other types of objects.
 
+``!filter(``\ *var*\ ``,`` *list*\ ``,`` *predicate*\ ``)``
+
+    This operator creates a new ``list`` by filtering the elements in
+    *list*. To perform the filtering, TableGen binds the variable *var* to each
+    element and then evaluates the *predicate* expression, which presumably
+    refers to *var*. The predicate must
+    produce a boolean value (``bit``, ``bits``, or ``int``). The value is
+    interpreted as with ``!if``:
+    if the value is 0, the element is not included in the new list. If the value
+    is anything else, the element is included.
+
 ``!foldl(``\ *init*\ ``,`` *list*\ ``,`` *acc*\ ``,`` *var*\ ``,`` *expr*\ ``)``
     This operator performs a left-fold over the items in *list*. The
     variable *acc* acts as the accumulator and is initialized to *init*.
     The variable *var* is bound to each element in the *list*. The
     expression is evaluated for each element and presumably uses *acc* and
     *var* to calculate the accumulated value, which ``!foldl`` stores back in
     *acc*. The type of *acc* is the same as *init*; the type of *var* is the
     same as the elements of *list*; *expr* must have the same type as *init*.
 
     The following example computes the total of the ``Number`` field in the
     list of records in ``RecList``::
 
       int x = !foldl(0, RecList, total, rec, !add(total, rec.Number));
 
+    If your goal is to filter the list and produce a new list that includes only
+    some of the elements, see ``!filter``.
+
 ``!foreach(``\ *var*\ ``,`` *sequence*\ ``,`` *expr*\ ``)``
     This operator creates a new ``list``/``dag`` in which each element is a
     function of the corresponding element in the *sequence* ``list``/``dag``.
     To perform the function, TableGen binds the variable *var* to an element
     and then evaluates the expression. The expression presumably refers
     to the variable *var* and calculates the result value.
 
     If you simply want to create a list of a certain length containing

llvm/include/llvm/IR/IntrinsicsNVVM.td

list<WMMA_REGS> ldst_bit_ab_ops = MMA_LDST_OPS<
             ["m8n8k128"], ["a", "b"], ["b1"]>.ret;
   list<WMMA_REGS> ldst_subint_cd_ops = MMA_LDST_OPS<
             ["m8n8k32", "m8n8k128"],  ["c", "d"], ["s32"]>.ret;
   list<WMMA_REGS> all_ldst_ops = !listconcat(ldst_ab_ops, ldst_cd_ops,
                                              ldst_subint_ab_ops,
                                              ldst_bit_ab_ops,
                                              ldst_subint_cd_ops);
   // Separate A/B/C fragments (loads) from D (stores).
-  list<WMMA_REGS> all_ld_ops = !foldl([]<WMMA_REGS>, all_ldst_ops, a, b,
-                                      !listconcat(a, !if(!eq(b.frag,"d"), [],[b])));
-  list<WMMA_REGS> all_st_ops = !foldl([]<WMMA_REGS>, all_ldst_ops, a, b,
-                                      !listconcat(a, !if(!eq(b.frag,"d"), [b],[])));
+  list<WMMA_REGS> all_ld_ops = !filter(op, all_ldst_ops, !ne(op.frag, "d"));
+  list<WMMA_REGS> all_st_ops = !filter(op, all_ldst_ops, !eq(op.frag, "d"));
 }
 
 def NVVM_MMA_OPS : NVVM_MMA_OPS;
 
 // Returns [1] if this combination of layout/satf is supported, [] otherwise.
 // MMA ops must provide all parameters. Loads and stores -- only frags and layout_a.
 // The class is used to prevent generation of records for the unsupported variants.
 // E.g.

llvm/include/llvm/TableGen/Record.h

public:
   Init *resolveReferences(Resolver &R) const override;
 
   std::string getAsString() const override;
 };
 
 /// !op (X, Y, Z) - Combine two inits.
 class TernOpInit : public OpInit, public FoldingSetNode {
 public:
-  enum TernaryOp : uint8_t { SUBST, FOREACH, IF, DAG };
+  enum TernaryOp : uint8_t { SUBST, FOREACH, FILTER, IF, DAG };
 
 private:
   Init *LHS, *MHS, *RHS;
 
   TernOpInit(TernaryOp opc, Init *lhs, Init *mhs, Init *rhs,
              RecTy *Type) :
       OpInit(IK_TernOpInit, Type, opc), LHS(lhs), MHS(mhs), RHS(rhs) {}
 

llvm/lib/TableGen/Record.cpp

TernOpInit *TernOpInit::get(TernaryOp Opc, Init *LHS, Init *MHS, Init *RHS,
   ThePool.InsertNode(I, IP);
   return I;
 }
 
 void TernOpInit::Profile(FoldingSetNodeID &ID) const {
   ProfileTernOpInit(ID, getOpcode(), getLHS(), getMHS(), getRHS(), getType());
 }
 
-static Init *ForeachApply(Init *LHS, Init *MHSe, Init *RHS, Record *CurRec) {
+static Init *ItemApply(Init *LHS, Init *MHSe, Init *RHS, Record *CurRec) {
   MapResolver R(CurRec);
   R.set(LHS, MHSe);
   return RHS->resolveReferences(R);
 }
 
 static Init *ForeachDagApply(Init *LHS, DagInit *MHSd, Init *RHS,
                              Record *CurRec) {
   bool Change = false;
-  Init *Val = ForeachApply(LHS, MHSd->getOperator(), RHS, CurRec);
+  Init *Val = ItemApply(LHS, MHSd->getOperator(), RHS, CurRec);
   if (Val != MHSd->getOperator())
     Change = true;
 
   SmallVector<std::pair<Init *, StringInit *>, 8> NewArgs;
   for (unsigned int i = 0; i < MHSd->getNumArgs(); ++i) {
     Init *Arg = MHSd->getArg(i);
     Init *NewArg;
     StringInit *ArgName = MHSd->getArgName(i);
 
     if (DagInit *Argd = dyn_cast<DagInit>(Arg))
       NewArg = ForeachDagApply(LHS, Argd, RHS, CurRec);
     else
-      NewArg = ForeachApply(LHS, Arg, RHS, CurRec);
+      NewArg = ItemApply(LHS, Arg, RHS, CurRec);
 
     NewArgs.push_back(std::make_pair(NewArg, ArgName));
     if (Arg != NewArg)
       Change = true;
   }
 
   if (Change)
     return DagInit::get(Val, nullptr, NewArgs);
   return MHSd;
 }
 
 // Applies RHS to all elements of MHS, using LHS as a temp variable.
 static Init *ForeachHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
                            Record *CurRec) {
   if (DagInit *MHSd = dyn_cast<DagInit>(MHS))
     return ForeachDagApply(LHS, MHSd, RHS, CurRec);
 
   if (ListInit *MHSl = dyn_cast<ListInit>(MHS)) {
     SmallVector<Init *, 8> NewList(MHSl->begin(), MHSl->end());
 
     for (Init *&Item : NewList) {
-      Init *NewItem = ForeachApply(LHS, Item, RHS, CurRec);
+      Init *NewItem = ItemApply(LHS, Item, RHS, CurRec);
       if (NewItem != Item)
         Item = NewItem;
     }
     return ListInit::get(NewList, cast<ListRecTy>(Type)->getElementType());
   }
 
   return nullptr;
 }
 
+// Evaluates RHS for all elements of MHS, using LHS as a temp variable.
+// Creates a new list with the elements that evaluated to true.
+static Init *FilterHelper(Init *LHS, Init *MHS, Init *RHS, RecTy *Type,
+                          Record *CurRec) {
+  if (ListInit *MHSl = dyn_cast<ListInit>(MHS)) {
+    SmallVector<Init *, 8> NewList;
+
+    for (Init *Item : MHSl->getValues()) {
+      Init *Include = ItemApply(LHS, Item, RHS, CurRec);
+      if (!Include)
+        return nullptr;
+      if (IntInit *IncludeInt = dyn_cast_or_null<IntInit>(
+                                    Include->convertInitializerTo(IntRecTy::get()))) {
+        if (IncludeInt->getValue())          
+          NewList.push_back(Item);
+       } else {
+         return nullptr;
+       }
+    }
+    return ListInit::get(NewList, cast<ListRecTy>(Type)->getElementType());
+  }
+
+  return nullptr;
+}
+
 Init *TernOpInit::Fold(Record *CurRec) const {
   switch (getOpcode()) {
   case SUBST: {
     DefInit *LHSd = dyn_cast<DefInit>(LHS);
     VarInit *LHSv = dyn_cast<VarInit>(LHS);
     StringInit *LHSs = dyn_cast<StringInit>(LHS);
 
     DefInit *MHSd = dyn_cast<DefInit>(MHS);
Init *TernOpInit::Fold(Record *CurRec) const {
   }
 
   case FOREACH: {
     if (Init *Result = ForeachHelper(LHS, MHS, RHS, getType(), CurRec))
       return Result;
     break;
   }
 
+  case FILTER: {
+    if (Init *Result = FilterHelper(LHS, MHS, RHS, getType(), CurRec))
+      return Result;
+    break;
+  }
+
   case IF: {
     if (IntInit *LHSi = dyn_cast_or_null<IntInit>(
                             LHS->convertInitializerTo(IntRecTy::get()))) {
       if (LHSi->getValue())
         return MHS;
       return RHS;
     }
     break;
if (IntInit *Value = dyn_cast_or_null<IntInit>(
         return MHS->resolveReferences(R);
       return RHS->resolveReferences(R);
     }
   }
 
   Init *mhs = MHS->resolveReferences(R);
   Init *rhs;
 
-  if (getOpcode() == FOREACH) {
+  if (getOpcode() == FOREACH || getOpcode() == FILTER) {
     ShadowResolver SR(R);
     SR.addShadow(lhs);
     rhs = RHS->resolveReferences(SR);
   } else {
     rhs = RHS->resolveReferences(R);
   }
 
   if (LHS != lhs || MHS != mhs || RHS != rhs)
     return (TernOpInit::get(getOpcode(), lhs, mhs, rhs, getType()))
         ->Fold(R.getCurrentRecord());
   return const_cast<TernOpInit *>(this);
 }
 
 std::string TernOpInit::getAsString() const {
   std::string Result;
   bool UnquotedLHS = false;
   switch (getOpcode()) {
   case SUBST: Result = "!subst"; break;
   case FOREACH: Result = "!foreach"; UnquotedLHS = true; break;
+  case FILTER: Result = "!filter"; UnquotedLHS = true; break;
   case IF: Result = "!if"; break;
   case DAG: Result = "!dag"; break;
   }
   return (Result + "(" +
           (UnquotedLHS ? LHS->getAsUnquotedString() : LHS->getAsString()) +
           ", " + MHS->getAsString() + ", " + RHS->getAsString() + ")");
 }
 

llvm/lib/TableGen/TGLexer.h

 #include <vector>
 
 namespace llvm {
 template <typename T> class ArrayRef;
 class SourceMgr;
 class Twine;
 
 namespace tgtok {
   enum TokKind {
     // Markers
     Eof, Error,
 
     // Tokens with no info.
     minus, plus,        // - +
     l_square, r_square, // [ ]
     l_brace, r_brace,   // { }
     l_paren, r_paren,   // ( )
     less, greater,      // < >
     colon, semi,        // : ;
     comma, dot,         // , .
     equal, question,    // = ?
     paste,              // #
     dotdotdot,          // ...
 
     // Reserved keywords. ('ElseKW' is named to distinguish it from the
     // existing 'Else' that means the preprocessor #else.)
     Bit, Bits, Class, Code, Dag, Def, Defm, Defset, Defvar, ElseKW, FalseKW,
     Field, Foreach, If, In, Include, Int, Let, List, MultiClass,
     String, Then, TrueKW,
 
     // Bang operators.
     XConcat, XADD, XSUB, XMUL, XNOT, XAND, XOR, XXOR, XSRA, XSRL, XSHL,
     XListConcat, XListSplat, XStrConcat, XInterleave, XCast, XSubst, XForEach,
-    XFoldl, XHead, XTail, XSize, XEmpty, XIf, XCond, XEq, XIsA, XDag, XNe,
-    XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
+    XFilter, XFoldl, XHead, XTail, XSize, XEmpty, XIf, XCond, XEq, XIsA,
+    XDag, XNe, XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
 
     // Boolean literals.
     TrueVal, FalseVal,
 
     // Integer value.
     IntVal,
 
     // Binary constant.  Note that these are sized according to the number of

llvm/lib/TableGen/TGLexer.cpp

if (!isalpha(*CurPtr))
     return ReturnError(CurPtr - 1, "Invalid \"!operator\"");
 
   const char *Start = CurPtr++;
   while (isalpha(*CurPtr))
     ++CurPtr;
 
   // Check to see which operator this is.
   tgtok::TokKind Kind =
     StringSwitch<tgtok::TokKind>(StringRef(Start, CurPtr - Start))
     .Case("eq", tgtok::XEq)
     .Case("ne", tgtok::XNe)
     .Case("le", tgtok::XLe)
     .Case("lt", tgtok::XLt)
     .Case("ge", tgtok::XGe)
     .Case("gt", tgtok::XGt)
     .Case("if", tgtok::XIf)
     .Case("cond", tgtok::XCond)
tgtok::TokKind Kind =
     .Case("shl", tgtok::XSHL)
     .Case("sra", tgtok::XSRA)
     .Case("srl", tgtok::XSRL)
     .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("strconcat", tgtok::XStrConcat)
     .Case("interleave", tgtok::XInterleave)
     .Cases("setdagop", "setop", tgtok::XSetDagOp) // !setop is deprecated.
     .Cases("getdagop", "getop", tgtok::XGetDagOp) // !getop is deprecated.
     .Default(tgtok::Error);
 

llvm/lib/TableGen/TGParser.h

void ParseDagArgList(
       Record *CurRec);
   bool ParseOptionalRangeList(SmallVectorImpl<unsigned> &Ranges);
   bool ParseOptionalBitList(SmallVectorImpl<unsigned> &Ranges);
   void ParseRangeList(SmallVectorImpl<unsigned> &Result);
   bool ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
                        TypedInit *FirstItem = nullptr);
   RecTy *ParseType();
   Init *ParseOperation(Record *CurRec, RecTy *ItemType);
+  Init *ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationCond(Record *CurRec, RecTy *ItemType);
   RecTy *ParseOperatorType();
   Init *ParseObjectName(MultiClass *CurMultiClass);
   Record *ParseClassID();
   MultiClass *ParseMultiClassID();
   bool ApplyLetStack(Record *CurRec);
   bool ApplyLetStack(RecordsEntry &Entry);
 };
 
 } // end namespace llvm
 
 #endif

llvm/lib/TableGen/TGParser.cpp

case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     if (InitList.size() == 2)
       return (BinOpInit::get(Code, InitList[0], InitList[1], Type))
           ->Fold(CurRec);
 
     Error(OpLoc, "expected two operands to operator");
     return nullptr;
   }
 
-  case tgtok::XForEach: {
-    // Value ::= !foreach '(' Id ',' Value ',' Value ')'
-    SMLoc OpLoc = Lex.getLoc();
-    Lex.Lex(); // eat the operation
-    if (Lex.getCode() != tgtok::l_paren) {
-      TokError("expected '(' after !foreach");
-      return nullptr;
-    }
-
-    if (Lex.Lex() != tgtok::Id) { // eat the '('
-      TokError("first argument of !foreach must be an identifier");
-      return nullptr;
-    }
-
-    Init *LHS = StringInit::get(Lex.getCurStrVal());
-    Lex.Lex();
-
-    if (CurRec && CurRec->getValue(LHS)) {
-      TokError((Twine("iteration variable '") + LHS->getAsString() +
-                "' already defined")
-                   .str());
-      return nullptr;
-    }
-
-    if (!consume(tgtok::comma)) { // eat the id
-      TokError("expected ',' in ternary operator");
-      return nullptr;
-    }
-
-    Init *MHS = ParseValue(CurRec);
-    if (!MHS)
-      return nullptr;
-
-    if (!consume(tgtok::comma)) {
-      TokError("expected ',' in ternary operator");
-      return nullptr;
-    }
-
-    TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
-    if (!MHSt) {
-      TokError("could not get type of !foreach input");
-      return nullptr;
-    }
-
-    RecTy *InEltType = nullptr;
-    RecTy *OutEltType = nullptr;
-    bool IsDAG = false;
-
-    if (ListRecTy *InListTy = dyn_cast<ListRecTy>(MHSt->getType())) {
-      InEltType = InListTy->getElementType();
-      if (ItemType) {
-        if (ListRecTy *OutListTy = dyn_cast<ListRecTy>(ItemType)) {
-          OutEltType = OutListTy->getElementType();
-        } else {
-          Error(OpLoc,
-                "expected value of type '" + Twine(ItemType->getAsString()) +
-                "', but got !foreach of list type");
-          return nullptr;
-        }
-      }
-    } else if (DagRecTy *InDagTy = dyn_cast<DagRecTy>(MHSt->getType())) {
-      InEltType = InDagTy;
-      if (ItemType && !isa<DagRecTy>(ItemType)) {
-        Error(OpLoc,
-              "expected value of type '" + Twine(ItemType->getAsString()) +
-              "', but got !foreach of dag type");
-        return nullptr;
-      }
-      IsDAG = true;
-    } else {
-      TokError("!foreach must have list or dag input");
-      return nullptr;
-    }
-
-    // We need to create a temporary record to provide a scope for the
-    // iteration variable.
-    std::unique_ptr<Record> ParseRecTmp;
-    Record *ParseRec = CurRec;
-    if (!ParseRec) {
-      ParseRecTmp = std::make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
-      ParseRec = ParseRecTmp.get();
-    }
-
-    ParseRec->addValue(RecordVal(LHS, InEltType, false));
-    Init *RHS = ParseValue(ParseRec, OutEltType);
-    ParseRec->removeValue(LHS);
-    if (!RHS)
-      return nullptr;
-
-    if (!consume(tgtok::r_paren)) {
-      TokError("expected ')' in binary operator");
-      return nullptr;
-    }
-
-    RecTy *OutType;
-    if (IsDAG) {
-      OutType = InEltType;
-    } else {
-      TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
-      if (!RHSt) {
-        TokError("could not get type of !foreach result");
-        return nullptr;
-      }
-      OutType = RHSt->getType()->getListTy();
-    }
-
-    return (TernOpInit::get(TernOpInit::FOREACH, LHS, MHS, RHS, OutType))
-        ->Fold(CurRec);
+  case tgtok::XForEach:
+  case tgtok::XFilter: {
+    return ParseOperationForEachFilter(CurRec, ItemType);
   }
 
   case tgtok::XDag:
   case tgtok::XIf:
   case tgtok::XSubst: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     TernOpInit::TernaryOp Code;
     RecTy *Type = nullptr;
 
RecTy *TGParser::ParseOperatorType() {
   if (!consume(tgtok::greater)) {
     TokError("expected type name for operator");
     return nullptr;
   }
 
   return Type;
 }
 
+/// Parse the !foreach and !filter operations. Return null on error.
+///
+/// ForEach ::= !foreach(ID, list-or-dag, expr) => list<expr type>
+/// Filter  ::= !foreach(ID, list, predicate) ==> list<list type>
+Init *TGParser::ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType) { 
+  SMLoc OpLoc = Lex.getLoc();
+  tgtok::TokKind Operation = Lex.getCode();
+  Lex.Lex(); // eat the operation
+  if (Lex.getCode() != tgtok::l_paren) {
+    TokError("expected '(' after !foreach/!filter");
+    return nullptr;
+  }
+
+  if (Lex.Lex() != tgtok::Id) { // eat the '('
+    TokError("first argument of !foreach/!filter must be an identifier");
+    return nullptr;
+  }
+
+  Init *LHS = StringInit::get(Lex.getCurStrVal());
+  Lex.Lex(); // eat the ID.
+
+  if (CurRec && CurRec->getValue(LHS)) {
+    TokError((Twine("iteration variable '") + LHS->getAsString() +
+              "' is already defined")
+                 .str());
+    return nullptr;
+  }
+
+  if (!consume(tgtok::comma)) {
+    TokError("expected ',' in !foreach/!filter");
+    return nullptr;
+  }
+
+  Init *MHS = ParseValue(CurRec);
+  if (!MHS)
+    return nullptr;
+
+  if (!consume(tgtok::comma)) {
+    TokError("expected ',' in !foreach/!filter");
+    return nullptr;
+  }
+
+  TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
+  if (!MHSt) {
+    TokError("could not get type of !foreach/!filter list or dag");
+    return nullptr;
+  }
+
+  RecTy *InEltType = nullptr;
+  RecTy *ExprEltType = nullptr;
+  bool IsDAG = false;
+
+  if (ListRecTy *InListTy = dyn_cast<ListRecTy>(MHSt->getType())) {
+    InEltType = InListTy->getElementType();
+    if (ItemType) {
+      if (ListRecTy *OutListTy = dyn_cast<ListRecTy>(ItemType)) {
+        ExprEltType = (Operation == tgtok::XForEach)
+                          ? OutListTy->getElementType() : IntRecTy::get();
+      } else {
+        Error(OpLoc,
+              "expected value of type '" + Twine(ItemType->getAsString()) +
+              "', but got list type");
+        return nullptr;
+      }
+    }
+  } else if (DagRecTy *InDagTy = dyn_cast<DagRecTy>(MHSt->getType())) {
+    if (Operation == tgtok::XFilter) {
+      TokError("!filter must have a list argument");
+      return nullptr;
+    }
+    InEltType = InDagTy;
+    if (ItemType && !isa<DagRecTy>(ItemType)) {
+      Error(OpLoc,
+            "expected value of type '" + Twine(ItemType->getAsString()) +
+            "', but got dag type");
+      return nullptr;
+    }
+    IsDAG = true;
+  } else {
+    if (Operation == tgtok::XForEach)
+      TokError("!foreach must have a list or dag argument");
+    else
+      TokError("!filter must have a list argument");
+    return nullptr;
+  }
+
+  // We need to create a temporary record to provide a scope for the
+  // iteration variable.
+  std::unique_ptr<Record> ParseRecTmp;
+  Record *ParseRec = CurRec;
+  if (!ParseRec) {
+    ParseRecTmp = std::make_unique<Record>(".parse", ArrayRef<SMLoc>{}, Records);
+    ParseRec = ParseRecTmp.get();
+  }
+
+  ParseRec->addValue(RecordVal(LHS, InEltType, false));
+  Init *RHS = ParseValue(ParseRec, ExprEltType);
+  ParseRec->removeValue(LHS);
+  if (!RHS)
+    return nullptr;
+
+  if (!consume(tgtok::r_paren)) {
+    TokError("expected ')' in !foreach/!filter");
+    return nullptr;
+  }
+
+  RecTy *OutType = InEltType;
+  if (Operation == tgtok::XForEach && !IsDAG) {
+    TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
+    if (!RHSt) {
+      TokError("could not get type of !foreach result expression");
+      return nullptr;
+    }
+    OutType = RHSt->getType()->getListTy();
+  } else if (Operation == tgtok::XFilter) {
+    OutType = InEltType->getListTy();
+  }    
+
+  return (TernOpInit::get((Operation == tgtok::XForEach) ? TernOpInit::FOREACH
+                                                         : TernOpInit::FILTER,
+                          LHS, MHS, RHS, OutType))
+      ->Fold(CurRec);
+}
+
 Init *TGParser::ParseOperationCond(Record *CurRec, RecTy *ItemType) {
   Lex.Lex();  // eat the operation 'cond'
 
   if (!consume(tgtok::l_paren)) {
     TokError("expected '(' after !cond operator");
     return nullptr;
   }
 
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XListSplat:
   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:
   case tgtok::XSubst: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     return ParseOperation(CurRec, ItemType);
   }
   }
 
   return R;
 }
 

llvm/lib/Target/AMDGPU/AMDGPUInstructions.td

 def TruePredicate : Predicate<"">;
 
 // FIXME: Tablegen should specially supports this
 def FalsePredicate : Predicate<"false">;
 
 // Add a predicate to the list if does not already exist to deduplicate it.
 class PredConcat<list<Predicate> lst, Predicate pred> {
   list<Predicate> ret =
-    !foldl([pred], lst, acc, cur,
-           !listconcat(acc, !if(!eq(!cast<string>(cur),!cast<string>(pred)),
-                                [], [cur])));
+      !listconcat([pred], !filter(item, lst,
+                                  !ne(!cast<string>(item), !cast<string>(pred))));
 }
 
 class PredicateControl {
   Predicate SubtargetPredicate = TruePredicate;
   Predicate AssemblerPredicate = TruePredicate;
   Predicate WaveSizePredicate = TruePredicate;
   list<Predicate> OtherPredicates = [];
   list<Predicate> Predicates = PredConcat<

llvm/lib/Target/AMDGPU/MIMGInstructions.td

def MIMGInfoTable : GenericTable {
   let PrimaryKeyName = "getMIMGOpcodeHelper";
 }
 
 def getMIMGInfo : SearchIndex {
   let Table = MIMGInfoTable;
   let Key = ["Opcode"];
 }
 
-// This is a separate class so that TableGen memoizes the computations.
+// This class used to use !foldl to memoize the AddrAsmNames list.
+// It turned out that that was much slower than using !filter.
 class MIMGNSAHelper<int num_addrs> {
   list<string> AddrAsmNames =
-    !foldl([]<string>, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], lhs, i,
-           !if(!lt(i, num_addrs), !listconcat(lhs, ["vaddr"#!size(lhs)]), lhs));
+    !foreach(i, !filter(i, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
+                        !lt(i, num_addrs)), "vaddr" # i);
   dag AddrIns = !dag(ins, !foreach(arg, AddrAsmNames, VGPR_32), AddrAsmNames);
   string AddrAsm = "[$" # !interleave(AddrAsmNames, ", $") # "]";
 
   int NSA = !if(!le(num_addrs, 1), ?,
             !if(!le(num_addrs, 5), 1,
             !if(!le(num_addrs, 9), 2,
             !if(!le(num_addrs, 13), 3, ?))));
 }

llvm/lib/Target/AMDGPU/SIRegisterInfo.td

 
 class Indexes<int N> {
   list<int> all = [0,   1,  2,  3,  4,  5,  6 , 7,
                    8,   9, 10, 11, 12, 13, 14, 15,
                    16, 17, 18, 19, 20, 21, 22, 23,
                    24, 25, 26, 27, 28, 29, 30, 31];
 
   // Returns list of indexes [0..N)
-  list<int> slice =
-    !foldl([]<int>, all, acc, cur,
-           !listconcat(acc, !if(!lt(cur, N), [cur], [])));
+  list<int> slice = !filter(i, all, !lt(i, N));
 }
 
 let Namespace = "AMDGPU" in {
 
 def lo16 : SubRegIndex<16, 0>;
 def hi16 : SubRegIndex<16, 16>;
 
 foreach Index = 0...31 in {

llvm/test/TableGen/filter.td

+// RUN: llvm-tblgen %s | FileCheck %s
+// RUN: not llvm-tblgen -DERROR1 %s 2>&1 | FileCheck --check-prefix=ERROR1 %s
+
+defvar EmptyList = []<string>;
+defvar OneList = ["foo"];
+defvar WordList = ["foo", "bar", "zoo", "foo", "snork", "snork", "quux"];
+
+class Predicate;
+def pred1 : Predicate;
+def pred2 : Predicate;
+def pred3 : Predicate;
+def pred4 : Predicate;
+def pred5 : Predicate;
+
+class DeduplicatePredList<list<Predicate> predlist, Predicate pred> {
+  list<Predicate> ret =
+      !listconcat([pred], !filter(item, predlist,
+                                  !ne(!cast<string>(item), !cast<string>(pred))));
+}
+
+// CHECK: def rec1
+// CHECK:   list1 = [];
+// CHECK:   list2 = [];
+// CHECK:   list3 = ["foo"];
+// CHECK:   list4 = [];
+// CHECK:   list5 = ["foo", "bar", "zoo", "foo", "snork", "snork", "quux"];
+// CHECK:   list6 = [];
+
+def rec1 {
+  list<string> list1 = !filter(item, EmptyList, true);
+  list<string> list2 = !filter(item, EmptyList, false);
+  list<string> list3 = !filter(item, OneList, true);
+  list<string> list4 = !filter(item, OneList, false);
+  list<string> list5 = !filter(item, WordList, true);
+  list<string> list6 = !filter(item, WordList, false);
+}
+
+// CHECK: def rec2
+// CHECK:   list1 = ["foo", "foo"];
+// CHECK:   list2 = ["bar", "zoo", "snork", "snork", "quux"];
+// CHECK:   list3 = ["snork", "snork", "quux"];
+
+def rec2 {
+  list<string> list1 = !filter(item, WordList, !eq(item, "foo"));
+  list<string> list2 = !filter(item, WordList, !ne(item, "foo"));
+  list<string> list3 = !filter(item, WordList, !ge(!size(item), 4));
+}
+
+// CHECK: def rec3
+// CHECK:   list1 = [4, 5, 6, 7, 8, 9, 10];
+// CHECK:   list2 = [4, 5, 6, 7, 8];
+
+def rec3 {
+  list<int> list1 = !filter(num, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], !gt(num, 3));
+  list<int> list2 = !filter(num, list1, !lt(num, 9));
+}
+
+// CHECK: def rec4
+// CHECK:   duplist = [pred1, pred2, pred1, pred3, pred4, pred1, pred5];
+// CHECK:   deduplist = [pred1, pred2, pred3, pred4, pred5];
+
+def rec4 {
+  list<Predicate> duplist = [pred1, pred2, pred1, pred3, pred4, pred1, pred5];
+  list<Predicate> deduplist = DeduplicatePredList<duplist, pred1>.ret;  
+}
+
+#ifdef ERROR1
+
+// ERROR1: could not be fully resolved
+
+def rec9 {
+  list<string> list1 = !filter(item, WordList, !if(true, "oops!", "wrong!"));
+}
+
+#endif