TableGen: Add !foldl operation

[nhaehnle]

Summary

Change-Id: I63d67bf6e0b315e2d3360e47e3b62c9517f38987

[tra]

LGTM. Few minor style questions.

docs/TableGen/LangRef.rst

98–101

Should we sort them?

lib/TableGen/TGParser.cpp

1251–1252

Would it make sense to print StartUntyped here, too? I often find TableGen failures baffling, specifically because tablegen will usually (sometimes?) tell you *where* tablegen ran into the problem, but it rarely tells you what exactly it saw after all the folding that made it unhappy. Better error reporting in general should probably be a patch, but I doubt there will be many voices against better error reporting in new code. :-)

1251–1258

You seem to mix fold and !foldl in the error messages throughout the function. Is that intentional? I'd use !foldl everywhere for consistency.

[nhaehnle]

r326790

docs/TableGen/LangRef.rst

98–101

Probably a good idea at some point, but I'd rather not do it in this commit to avoid conflicts with later changes.

lib/TableGen/TGParser.cpp

1251–1252

Yup, makes sense, I've added that, same with ListUntyped below.

1251–1258

You're right, I've changed all the messages to say !foldl consistently.

docs/TableGen/LangIntro.rst

``!subst(a, b, c)``
     If 'a' and 'b' are of string type or are symbol references, substitute 'b'
     for 'a' in 'c.'  This operation is analogous to $(subst) in GNU make.
 
 ``!foreach(a, b, c)``
     For each member of dag or list 'b' apply operator 'c'. 'a' is the name
     of a variable that will be substituted by members of 'b' in 'c'.
     This operation is analogous to $(foreach) in GNU make.
 
+``!foldl(start, lst, a, b, expr)``
+    Perform a left-fold over 'lst' with the given starting value. 'a' and 'b'
+    are variable names which will be substituted in 'expr'. If you think of
+    expr as a function f(a,b), the fold will compute
+    'f(...f(f(start, lst[0]), lst[1]), ...), lst[n-1])' for a list of length n.
+    As usual, 'a' will be of the type of 'start', and 'b' will be of the type
+    of elements of 'lst'. These types need not be the same, but 'expr' must be
+    of the same type as 'start'.
+
 ``!head(a)``
     The first element of list 'a.'
 
 ``!tail(a)``
     The 2nd-N elements of list 'a.'
 
 ``!empty(a)``
     An integer {0,1} indicating whether list 'a' is empty.

docs/TableGen/LangRef.rst

TableGen also has the following keywords::
    def   foreach   defm    field        in
    int   let       list    multiclass   string
 
 TableGen also has "bang operators" which have a
 wide variety of meanings:
 
 .. productionlist::
    BangOperator: one of
                :!eq     !if      !head    !tail      !con
                :!add    !shl     !sra     !srl       !and
                :!or     !empty   !subst   !foreach   !strconcat
-               :!cast   !listconcat       !size
+               :!cast   !listconcat       !size      !foldl
 
 
 Syntax
 ======
 
 TableGen has an ``include`` mechanism. It does not play a role in the
 syntax per se, since it is lexically replaced with the contents of the
 included file.

include/llvm/TableGen/Record.h

enum InitKind : uint8_t {
     IK_FieldInit,
     IK_IntInit,
     IK_ListInit,
     IK_FirstOpInit,
     IK_BinOpInit,
     IK_TernOpInit,
     IK_UnOpInit,
     IK_LastOpInit,
+    IK_FoldOpInit,
     IK_StringInit,
     IK_VarInit,
     IK_VarListElementInit,
     IK_VarBitInit,
     IK_VarDefInit,
     IK_LastTypedInit,
     IK_UnsetInit
   };
bool isComplete() const override {
     return LHS->isComplete() && MHS->isComplete() && RHS->isComplete();
   }
 
   Init *resolveReferences(Resolver &R) const override;
 
   std::string getAsString() const override;
 };
 
+/// !foldl (a, b, expr, start, lst) - Fold over a list.
+class FoldOpInit : public TypedInit, public FoldingSetNode {
+private:
+  Init *Start;
+  Init *List;
+  Init *A;
+  Init *B;
+  Init *Expr;
+
+  FoldOpInit(Init *Start, Init *List, Init *A, Init *B, Init *Expr, RecTy *Type)
+      : TypedInit(IK_FoldOpInit, Type), Start(Start), List(List), A(A), B(B),
+        Expr(Expr) {}
+
+public:
+  FoldOpInit(const FoldOpInit &) = delete;
+  FoldOpInit &operator=(const FoldOpInit &) = delete;
+
+  static bool classof(const Init *I) { return I->getKind() == IK_FoldOpInit; }
+
+  static FoldOpInit *get(Init *Start, Init *List, Init *A, Init *B, Init *Expr,
+                         RecTy *Type);
+
+  void Profile(FoldingSetNodeID &ID) const;
+
+  // Fold - If possible, fold this to a simpler init.  Return this if not
+  // possible to fold.
+  Init *Fold(Record *CurRec) const;
+
+  bool isComplete() const override { return false; }
+
+  Init *resolveReferences(Resolver &R) const override;
+
+  Init *getBit(unsigned Bit) const override;
+
+  std::string getAsString() const override;
+};
+
 /// 'Opcode' - Represent a reference to an entire variable object.
 class VarInit : public TypedInit {
   Init *VarName;
 
   explicit VarInit(Init *VN, RecTy *T)
       : TypedInit(IK_VarInit, T), VarName(VN) {}
 
 public:

lib/TableGen/Record.cpp

std::string TernOpInit::getAsString() const {
   case SUBST: Result = "!subst"; break;
   case FOREACH: Result = "!foreach"; break;
   case IF: Result = "!if"; break;
   }
   return Result + "(" + LHS->getAsString() + ", " + MHS->getAsString() + ", " +
          RHS->getAsString() + ")";
 }
 
+static void ProfileFoldOpInit(FoldingSetNodeID &ID, Init *A, Init *B,
+                              Init *Start, Init *List, Init *Expr,
+                              RecTy *Type) {
+  ID.AddPointer(Start);
+  ID.AddPointer(List);
+  ID.AddPointer(A);
+  ID.AddPointer(B);
+  ID.AddPointer(Expr);
+  ID.AddPointer(Type);
+}
+
+FoldOpInit *FoldOpInit::get(Init *Start, Init *List, Init *A, Init *B,
+                            Init *Expr, RecTy *Type) {
+  static FoldingSet<FoldOpInit> ThePool;
+
+  FoldingSetNodeID ID;
+  ProfileFoldOpInit(ID, Start, List, A, B, Expr, Type);
+
+  void *IP = nullptr;
+  if (FoldOpInit *I = ThePool.FindNodeOrInsertPos(ID, IP))
+    return I;
+
+  FoldOpInit *I = new (Allocator) FoldOpInit(Start, List, A, B, Expr, Type);
+  ThePool.InsertNode(I, IP);
+  return I;
+}
+
+void FoldOpInit::Profile(FoldingSetNodeID &ID) const {
+  ProfileFoldOpInit(ID, Start, List, A, B, Expr, getType());
+}
+
+Init *FoldOpInit::Fold(Record *CurRec) const {
+  if (ListInit *LI = dyn_cast<ListInit>(List)) {
+    Init *Accum = Start;
+    for (Init *Elt : *LI) {
+      MapResolver R(CurRec);
+      R.set(A, Accum);
+      R.set(B, Elt);
+      Accum = Expr->resolveReferences(R);
+    }
+    return Accum;
+  }
+  return const_cast<FoldOpInit *>(this);
+}
+
+Init *FoldOpInit::resolveReferences(Resolver &R) const {
+  Init *NewStart = Start->resolveReferences(R);
+  Init *NewList = List->resolveReferences(R);
+  ShadowResolver SR(R);
+  SR.addShadow(A);
+  SR.addShadow(B);
+  Init *NewExpr = Expr->resolveReferences(SR);
+
+  if (Start == NewStart && List == NewList && Expr == NewExpr)
+    return const_cast<FoldOpInit *>(this);
+
+  return get(NewStart, NewList, A, B, NewExpr, getType())
+      ->Fold(R.getCurrentRecord());
+}
+
+Init *FoldOpInit::getBit(unsigned Bit) const {
+  return VarBitInit::get(const_cast<FoldOpInit *>(this), Bit);
+}
+
+std::string FoldOpInit::getAsString() const {
+  return (Twine("!foldl(") + Start->getAsString() + ", " + List->getAsString() +
+          ", " + A->getAsUnquotedString() + ", " + B->getAsUnquotedString() +
+          ", " + Expr->getAsString() + ")")
+      .str();
+}
+
 RecTy *TypedInit::getFieldType(StringInit *FieldName) const {
   if (RecordRecTy *RecordType = dyn_cast<RecordRecTy>(getType())) {
     for (Record *Rec : RecordType->getClasses()) {
       if (RecordVal *Field = Rec->getValue(FieldName))
         return Field->getType();
     }
   }
   return nullptr;

lib/TableGen/TGLexer.h

enum TokKind {
     paste,              // #
 
     // Keywords.
     Bit, Bits, Class, Code, Dag, Def, Foreach, Defm, Field, In, Int, Let, List,
     MultiClass, String,
 
     // !keywords.
     XConcat, XADD, XAND, XOR, XSRA, XSRL, XSHL, XListConcat, XStrConcat, XCast,
-    XSubst, XForEach, XHead, XTail, XSize, XEmpty, XIf, XEq,
+    XSubst, XForEach, XFoldl, XHead, XTail, XSize, XEmpty, XIf, XEq,
 
     // Integer value.
     IntVal,
 
     // Binary constant.  Note that these are sized according to the number of
     // bits given.
     BinaryIntVal,
     

lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("and", tgtok::XAND)
     .Case("or", tgtok::XOR)
     .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("listconcat", tgtok::XListConcat)
     .Case("strconcat", tgtok::XStrConcat)
     .Default(tgtok::Error);
 
   return Kind != tgtok::Error ? Kind : ReturnError(Start-1, "Unknown operator");
 }

lib/TableGen/TGParser.cpp

case tgtok::XSubst: {
       }
       Type = RHSt->getType();
       break;
     }
     }
     return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec,
                                                              CurMultiClass);
   }
+
+  case tgtok::XFoldl: {
+    // Value ::= !foldl '(' Id ',' Id ',' Value ',' Value ',' Value ')'
+    Lex.Lex(); // eat the operation
+    if (Lex.getCode() != tgtok::l_paren) {
+      TokError("expected '(' after !foldl");
+      return nullptr;
+    }
+    Lex.Lex(); // eat the '('
+
+    Init *StartUntyped = ParseValue(CurRec);
+    if (!StartUntyped)
+      return nullptr;
+
+    TypedInit *Start = dyn_cast<TypedInit>(StartUntyped);
+    if (!Start) {
+      TokError("could not get type of !foldl start");
+      return nullptr;
+    }
+
+    if (Lex.getCode() != tgtok::comma) {
+      TokError("expected ',' in fold operator");
+      return nullptr;
+    }
+    Lex.Lex(); // eat the ','
+
+    Init *ListUntyped = ParseValue(CurRec);
+    if (!ListUntyped)
+      return nullptr;
+
+    TypedInit *List = dyn_cast<TypedInit>(ListUntyped);
+    if (!List) {
+      TokError("could not get type of !foldl list");
+      return nullptr;
+    }
+
+    ListRecTy *ListType = dyn_cast<ListRecTy>(List->getType());
+    if (!ListType) {
+      TokError(Twine("!foldl list must be a list, but is of type '") +
+               List->getType()->getAsString());
+      return nullptr;
+    }
+
+    if (Lex.getCode() != tgtok::comma) {
+      TokError("expected ',' in fold operator");
+      return nullptr;
+    }
+
+    if (Lex.Lex() != tgtok::Id) { // eat the ','
+      TokError("third argument of !foldl must be an identifier");
+      return nullptr;
+    }
+
+    Init *A = StringInit::get(Lex.getCurStrVal());
+    if (CurRec->getValue(A)) {
+      TokError((Twine("left fold variable '") + A->getAsString() +
+                "' already defined")
+                   .str());
+      return nullptr;
+    }
+
+    if (Lex.Lex() != tgtok::comma) { // eat the id
+      TokError("expected ',' in ternary operator");
+      return nullptr;
+    }
+
+    if (Lex.Lex() != tgtok::Id) { // eat the ','
+      TokError("fourth argument of !foldl must be an identifier");
+      return nullptr;
+    }
+
+    Init *B = StringInit::get(Lex.getCurStrVal());
+    if (CurRec->getValue(B)) {
+      TokError((Twine("right fold variable '") + B->getAsString() +
+                "' already defined")
+                   .str());
+      return nullptr;
+    }
+
+    if (Lex.Lex() != tgtok::comma) { // eat the id
+      TokError("expected ',' in fold operator");
+      return nullptr;
+    }
+    Lex.Lex(); // eat the ','
+
+    CurRec->addValue(RecordVal(A, Start->getType(), false));
+    CurRec->addValue(RecordVal(B, ListType->getElementType(), false));
+    Init *ExprUntyped = ParseValue(CurRec);
+    CurRec->removeValue(A);
+    CurRec->removeValue(B);
+    if (!ExprUntyped)
+      return nullptr;
+
+    TypedInit *Expr = dyn_cast<TypedInit>(ExprUntyped);
+    if (!Expr) {
+      TokError("could not get type of !foldl expression");
+      return nullptr;
+    }
+
+    if (Expr->getType() != Start->getType()) {
+      TokError(Twine("!foldl expression must be of same type as start (") +
+               Start->getType()->getAsString() + "), but is of type " +
+               Expr->getType()->getAsString());
+      return nullptr;
+    }
+
+    if (Lex.getCode() != tgtok::r_paren) {
+      TokError("expected ')' in fold operator");
+      return nullptr;
+    }
+    Lex.Lex(); // eat the ')'
+
+    return FoldOpInit::get(Start, List, A, B, Expr, Start->getType())
+        ->Fold(CurRec);
+  }
   }
 }
 
 /// ParseOperatorType - Parse a type for an operator.  This returns
 /// null on error.
 ///
 /// OperatorType ::= '<' Type '>'
 ///
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XOR:
   case tgtok::XSRA:
   case tgtok::XSRL:
   case tgtok::XSHL:
   case tgtok::XEq:
   case tgtok::XListConcat:
   case tgtok::XStrConcat:   // Value ::= !binop '(' Value ',' Value ')'
   case tgtok::XIf:
+  case tgtok::XFoldl:
   case tgtok::XForEach:
   case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     return ParseOperation(CurRec, ItemType);
   }
   }
 
   return R;
 }
case tgtok::paste:
 
       if (LHS->getType() != StringRecTy::get()) {
         LHS = UnOpInit::get(UnOpInit::CAST, LHS, StringRecTy::get());
       }
 
       TypedInit *RHS = nullptr;
 
       Lex.Lex();  // Eat the '#'.
-      switch (Lex.getCode()) { 
+      switch (Lex.getCode()) {
       case tgtok::colon:
       case tgtok::semi:
       case tgtok::l_brace:
         // These are all of the tokens that can begin an object body.
         // Some of these can also begin values but we disallow those cases
         // because they are unlikely to be useful.
 
         // Trailing paste, concat with an empty string.
if (!CurMultiClass) {
     // the top-level defm. Therefore, we don't add this to the
     // RecordKeeper at this point. If we did we could get duplicate
     // defs as more than one probably refers to NAME or some other
     // common internal placeholder.
 
     // Ensure redefinition doesn't happen.
     if (Records.getDef(CurRec->getNameInitAsString())) {
       Error(DefmPrefixRange.Start, "def '" + CurRec->getNameInitAsString() +
-            "' already defined, instantiating defm with subdef '" + 
+            "' already defined, instantiating defm with subdef '" +
             DefProto->getNameInitAsString() + "'");
       return nullptr;
     }
 
     Record *CurRecSave = CurRec.get(); // Keep a copy before we release.
     Records.addDef(std::move(CurRec));
     return CurRecSave;
   }

test/TableGen/foldl.td

+// RUN: llvm-tblgen %s | FileCheck %s
+// XFAIL: vg_leak
+
+// CHECK: --- Defs ---
+
+// CHECK: def A1 {
+// CHECK:   int ret = 0;
+// CHECK: }
+
+// CHECK: def A2 {
+// CHECK:   int ret = 5;
+// CHECK: }
+
+// CHECK: def A3 {
+// CHECK:   int ret = 10;
+// CHECK: }
+
+// CHECK: def B1 {
+// CHECK:   list<string> ret = [];
+// CHECK: }
+
+// CHECK: def B2 {
+// CHECK:   list<string> ret = [];
+// CHECK: }
+
+// CHECK: def B3 {
+// CHECK:   list<string> ret = ["a"];
+// CHECK: }
+
+// CHECK: def B4 {
+// CHECK:   list<string> ret = ["a", "b", "c", "d"];
+// CHECK: }
+
+// CHECK: def E0 {
+// CHECK:   list<int> ret = [45, 45, 45, 45];
+// CHECK: }
+
+class Sum<list<int> lst> {
+  int ret = !foldl(0, lst, a, b, !add(a, b));
+}
+
+class Flatten<list<list<string>> lst> {
+  list<string> ret = !foldl([]<string>, lst, a, b, !listconcat(a, b));
+}
+
+def A1 : Sum<[]>;
+def A2 : Sum<[5]>;
+def A3 : Sum<[1, 2, 3, 4]>;
+
+def B1 : Flatten<[]>;
+def B2 : Flatten<[[]]>;
+def B3 : Flatten<[["a"]]>;
+def B4 : Flatten<[["a", "b"], [], ["c"], ["d"]]>;
+
+// The variables a and b are declared both in the "inner" foldl and in the
+// other foreach. The test checks that they don't "leak".
+class C<list<int> lst> {
+  int ret = !foldl(0, lst, a, b, !add(a, b));
+}
+
+class D<list<int> lst1, list<int> lst2> {
+  list<int> x = !foreach(a, lst1, C<lst2>.ret);
+  list<int> y = !foreach(b, lst1, C<lst2>.ret);
+  list<int> z = !listconcat(x, y);
+}
+
+class E<list<int> lst2> {
+  list<int> ret = D<[0, 1], lst2>.z;
+}
+
+def E0 : E<[10, 15, 20]>;