Index: docs/TableGen/LangIntro.rst =================================================================== --- docs/TableGen/LangIntro.rst +++ docs/TableGen/LangIntro.rst @@ -217,6 +217,15 @@ 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.' Index: docs/TableGen/LangRef.rst =================================================================== --- docs/TableGen/LangRef.rst +++ docs/TableGen/LangRef.rst @@ -98,7 +98,7 @@ :!eq !if !head !tail !con :!add !shl !sra !srl !and :!or !empty !subst !foreach !strconcat - :!cast !listconcat !size + :!cast !listconcat !size !foldl Syntax Index: include/llvm/TableGen/Record.h =================================================================== --- include/llvm/TableGen/Record.h +++ include/llvm/TableGen/Record.h @@ -316,6 +316,7 @@ IK_TernOpInit, IK_UnOpInit, IK_LastOpInit, + IK_FoldOpInit, IK_StringInit, IK_VarInit, IK_VarListElementInit, @@ -913,6 +914,43 @@ 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; Index: lib/TableGen/Record.cpp =================================================================== --- lib/TableGen/Record.cpp +++ lib/TableGen/Record.cpp @@ -1160,6 +1160,77 @@ 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 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(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(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(this); + + return get(NewStart, NewList, A, B, NewExpr, getType()) + ->Fold(R.getCurrentRecord()); +} + +Init *FoldOpInit::getBit(unsigned Bit) const { + return VarBitInit::get(const_cast(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(getType())) { for (Record *Rec : RecordType->getClasses()) { Index: lib/TableGen/TGLexer.h =================================================================== --- lib/TableGen/TGLexer.h +++ lib/TableGen/TGLexer.h @@ -48,7 +48,7 @@ // !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, Index: lib/TableGen/TGLexer.cpp =================================================================== --- lib/TableGen/TGLexer.cpp +++ lib/TableGen/TGLexer.cpp @@ -480,6 +480,7 @@ .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) Index: lib/TableGen/TGParser.cpp =================================================================== --- lib/TableGen/TGParser.cpp +++ lib/TableGen/TGParser.cpp @@ -1232,6 +1232,121 @@ 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(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(ListUntyped); + if (!List) { + TokError("could not get type of !foldl list"); + return nullptr; + } + + ListRecTy *ListType = dyn_cast(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(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); + } } } @@ -1590,6 +1705,7 @@ 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); @@ -1697,7 +1813,7 @@ TypedInit *RHS = nullptr; Lex.Lex(); // Eat the '#'. - switch (Lex.getCode()) { + switch (Lex.getCode()) { case tgtok::colon: case tgtok::semi: case tgtok::l_brace: @@ -2579,7 +2695,7 @@ // 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; } Index: test/TableGen/foldl.td =================================================================== --- /dev/null +++ test/TableGen/foldl.td @@ -0,0 +1,71 @@ +// 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 ret = []; +// CHECK: } + +// CHECK: def B2 { +// CHECK: list ret = []; +// CHECK: } + +// CHECK: def B3 { +// CHECK: list ret = ["a"]; +// CHECK: } + +// CHECK: def B4 { +// CHECK: list ret = ["a", "b", "c", "d"]; +// CHECK: } + +// CHECK: def E0 { +// CHECK: list ret = [45, 45, 45, 45]; +// CHECK: } + +class Sum lst> { + int ret = !foldl(0, lst, a, b, !add(a, b)); +} + +class Flatten> lst> { + list ret = !foldl([], 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 lst> { + int ret = !foldl(0, lst, a, b, !add(a, b)); +} + +class D lst1, list lst2> { + list x = !foreach(a, lst1, C.ret); + list y = !foreach(b, lst1, C.ret); + list z = !listconcat(x, y); +} + +class E lst2> { + list ret = D<[0, 1], lst2>.z; +} + +def E0 : E<[10, 15, 20]>;