diff --git a/llvm/docs/TableGen/ProgRef.rst b/llvm/docs/TableGen/ProgRef.rst --- a/llvm/docs/TableGen/ProgRef.rst +++ b/llvm/docs/TableGen/ProgRef.rst @@ -335,19 +335,25 @@ Value: `SimpleValue` `ValueSuffix`* :| `Value` "#" [`Value`] ValueSuffix: "{" `RangeList` "}" - :| "[" `RangeList` "]" + :| "[" `SliceElements` "]" :| "." `TokIdentifier` RangeList: `RangePiece` ("," `RangePiece`)* RangePiece: `TokInteger` :| `TokInteger` "..." `TokInteger` :| `TokInteger` "-" `TokInteger` :| `TokInteger` `TokInteger` + SliceElements: (`SliceElement` ",")* `SliceElement` ","? + SliceElement: `Value` + :| `Value` "..." `Value` + :| `Value` "-" `Value` + :| `Value` `TokInteger` .. warning:: - The peculiar last form of :token:`RangePiece` is due to the fact that the - "``-``" is included in the :token:`TokInteger`, hence ``1-5`` gets lexed as - two consecutive tokens, with values ``1`` and ``-5``, instead of "1", "-", - and "5". The use of hyphen as the range punctuation is deprecated. + The peculiar last form of :token:`RangePiece` and :token:`SliceElement` is + due to the fact that the "``-``" is included in the :token:`TokInteger`, + hence ``1-5`` gets lexed as two consecutive tokens, with values ``1`` and + ``-5``, instead of "1", "-", and "5". + The use of hyphen as the range punctuation is deprecated. Simple values ------------- @@ -505,17 +511,26 @@ The final value is bits 8--15 of the integer *value*. The order of the bits can be reversed by specifying ``{15...8}``. -*value*\ ``[4]`` - The final value is element 4 of the list *value* (note the brackets). +*value*\ ``[i]`` + The final value is element `i` of the list *value* (note the brackets). In other words, the brackets act as a subscripting operator on the list. This is the case only when a single element is specified. +*value*\ ``[i,]`` + The final value is a list that contains a single element `i` of the list. + In short, a list slice with a single element. + *value*\ ``[4...7,17,2...3,4]`` The final value is a new list that is a slice of the list *value*. The new list contains elements 4, 5, 6, 7, 17, 2, 3, and 4. Elements may be included multiple times and in any order. This is the result only when more than one element is specified. + *value*\ ``[i,m...n,j,ls]`` + Each element may be an expression (variables, bang operators). + The type of `m` and `n` should be `int`. + The type of `i`, `j`, and `ls` should be either `int` or `list`. + *value*\ ``.``\ *field* The final value is the value of the specified *field* in the specified record *value*. diff --git a/llvm/include/llvm/TableGen/Record.h b/llvm/include/llvm/TableGen/Record.h --- a/llvm/include/llvm/TableGen/Record.h +++ b/llvm/include/llvm/TableGen/Record.h @@ -314,7 +314,6 @@ IK_AnonymousNameInit, IK_StringInit, IK_VarInit, - IK_VarListElementInit, IK_VarBitInit, IK_VarDefInit, IK_LastTypedInit, @@ -384,14 +383,6 @@ return nullptr; } - /// This function is used to implement the list slice - /// selection operator. Given a value, it selects the specified list - /// elements, returning them as a new \p Init of type \p list. If it - /// is not legal to use the slice operator, null is returned. - virtual Init *convertInitListSlice(ArrayRef Elements) const { - return nullptr; - } - /// This function is used to implement the FieldInit class. /// Implementors of this method should return the type of the named /// field if they are of type record. @@ -443,7 +434,6 @@ Init *convertInitializerTo(RecTy *Ty) const override; Init *convertInitializerBitRange(ArrayRef Bits) const override; - Init *convertInitListSlice(ArrayRef Elements) const override; /// This method is used to implement the FieldInit class. /// Implementors of this method should return the type of the named field if @@ -724,8 +714,6 @@ Record *getElementAsRecord(unsigned i) const; - Init *convertInitListSlice(ArrayRef Elements) const override; - Init *convertInitializerTo(RecTy *Ty) const override; /// This method is used by classes that refer to other @@ -857,7 +845,10 @@ LISTCONCAT, LISTSPLAT, LISTREMOVE, + LISTELEM, + LISTSLICE, RANGE, + RANGEC, STRCONCAT, INTERLEAVE, CONCAT, @@ -1239,39 +1230,6 @@ } }; -/// List[4] - Represent access to one element of a var or -/// field. -class VarListElementInit : public TypedInit { - TypedInit *TI; - unsigned Element; - - VarListElementInit(TypedInit *T, unsigned E) - : TypedInit(IK_VarListElementInit, - cast(T->getType())->getElementType()), - TI(T), Element(E) { - assert(T->getType() && isa(T->getType()) && - "Illegal VarBitInit expression!"); - } - -public: - VarListElementInit(const VarListElementInit &) = delete; - VarListElementInit &operator=(const VarListElementInit &) = delete; - - static bool classof(const Init *I) { - return I->getKind() == IK_VarListElementInit; - } - - static VarListElementInit *get(TypedInit *T, unsigned E); - - TypedInit *getVariable() const { return TI; } - unsigned getElementNum() const { return Element; } - - std::string getAsString() const override; - Init *resolveReferences(Resolver &R) const override; - - Init *getBit(unsigned Bit) const override; -}; - /// AL - Represent a reference to a 'def' in the description class DefInit : public TypedInit { friend class Record; diff --git a/llvm/lib/TableGen/Record.cpp b/llvm/lib/TableGen/Record.cpp --- a/llvm/lib/TableGen/Record.cpp +++ b/llvm/lib/TableGen/Record.cpp @@ -83,8 +83,6 @@ FoldingSet TheExistsOpInitPool; DenseMap, VarInit *> TheVarInitPool; DenseMap, VarBitInit *> TheVarBitInitPool; - DenseMap, VarListElementInit *> - TheVarListElementInitPool; FoldingSet TheVarDefInitPool; DenseMap, FieldInit *> TheFieldInitPool; FoldingSet TheCondOpInitPool; @@ -670,23 +668,6 @@ return nullptr; } -Init *ListInit::convertInitListSlice(ArrayRef Elements) const { - if (Elements.size() == 1) { - if (Elements[0] >= size()) - return nullptr; - return getElement(Elements[0]); - } - - SmallVector Vals; - Vals.reserve(Elements.size()); - for (unsigned Element : Elements) { - if (Element >= size()) - return nullptr; - Vals.push_back(getElement(Element)); - } - return ListInit::get(Vals, getElementType()); -} - Record *ListInit::getElementAsRecord(unsigned i) const { assert(i < NumValues && "List element index out of range!"); DefInit *DI = dyn_cast(getElement(i)); @@ -1200,7 +1181,38 @@ } break; } - case RANGE: { + case LISTELEM: { + auto *TheList = dyn_cast(LHS); + auto *Idx = dyn_cast(RHS); + if (TheList && Idx) { + auto i = Idx->getValue(); + if (0 <= i && i < (ssize_t)TheList->size()) + return TheList->getElement(i); + } + break; + } + case LISTSLICE: { + auto *TheList = dyn_cast(LHS); + auto *SliceIdxs = dyn_cast(RHS); + if (TheList && SliceIdxs) { + SmallVector Args; + Args.reserve(SliceIdxs->size()); + for (auto *I : *SliceIdxs) { + auto *II = dyn_cast(I); + if (!II) + goto listslice_fail; + auto i = II->getValue(); + if (!(0 <= i && i < (ssize_t)TheList->size())) + goto listslice_fail; + Args.push_back(TheList->getElement(i)); + } + return ListInit::get(Args, TheList->getElementType()); + } + listslice_fail: + break; + } + case RANGE: + case RANGEC: { auto *LHSi = dyn_cast(LHS); auto *RHSi = dyn_cast(RHS); if (!LHSi || !RHSi) @@ -1209,7 +1221,20 @@ auto Start = LHSi->getValue(); auto End = RHSi->getValue(); SmallVector Args; - if (Start < End) { + if (getOpcode() == RANGEC) { + // Closed interval + if (Start <= End) { + // Ascending order + Args.reserve(End - Start + 1); + for (auto i = Start; i <= End; ++i) + Args.push_back(IntInit::get(getRecordKeeper(), i)); + } else { + // Descending order + Args.reserve(Start - End + 1); + for (auto i = Start; i >= End; --i) + Args.push_back(IntInit::get(getRecordKeeper(), i)); + } + } else if (Start < End) { // Half-open interval (excludes `End`) Args.reserve(End - Start); for (auto i = Start; i < End; ++i) @@ -1324,6 +1349,11 @@ std::string BinOpInit::getAsString() const { std::string Result; switch (getOpcode()) { + case LISTELEM: + case LISTSLICE: + return LHS->getAsString() + "[" + RHS->getAsString() + "]"; + case RANGEC: + return LHS->getAsString() + "..." + RHS->getAsString(); case CONCAT: Result = "!con"; break; case ADD: Result = "!add"; break; case SUB: Result = "!sub"; break; @@ -1908,22 +1938,6 @@ ->Fold(nullptr); } -Init *TypedInit::convertInitListSlice(ArrayRef Elements) const { - ListRecTy *T = dyn_cast(getType()); - if (!T) return nullptr; // Cannot subscript a non-list variable. - - if (Elements.size() == 1) - return VarListElementInit::get(const_cast(this), Elements[0]); - - SmallVector ListInits; - ListInits.reserve(Elements.size()); - for (unsigned Element : Elements) - ListInits.push_back(VarListElementInit::get(const_cast(this), - Element)); - return ListInit::get(ListInits, T->getElementType()); -} - - VarInit *VarInit::get(StringRef VN, RecTy *T) { Init *Value = StringInit::get(T->getRecordKeeper(), VN); return VarInit::get(Value, T); @@ -1974,37 +1988,6 @@ return const_cast(this); } -VarListElementInit *VarListElementInit::get(TypedInit *T, unsigned E) { - detail::RecordKeeperImpl &RK = T->getRecordKeeper().getImpl(); - VarListElementInit *&I = RK.TheVarListElementInitPool[std::make_pair(T, E)]; - if (!I) - I = new (RK.Allocator) VarListElementInit(T, E); - return I; -} - -std::string VarListElementInit::getAsString() const { - return TI->getAsString() + "[" + utostr(Element) + "]"; -} - -Init *VarListElementInit::resolveReferences(Resolver &R) const { - Init *NewTI = TI->resolveReferences(R); - if (ListInit *List = dyn_cast(NewTI)) { - // Leave out-of-bounds array references as-is. This can happen without - // being an error, e.g. in the untaken "branch" of an !if expression. - if (getElementNum() < List->size()) - return List->getElement(getElementNum()); - } - if (NewTI != TI && isa(NewTI)) - return VarListElementInit::get(cast(NewTI), getElementNum()); - return const_cast(this); -} - -Init *VarListElementInit::getBit(unsigned Bit) const { - if (getType() == BitRecTy::get(getRecordKeeper())) - return const_cast(this); - return VarBitInit::get(const_cast(this), Bit); -} - DefInit::DefInit(Record *D) : TypedInit(IK_DefInit, D->getType()), Def(D) {} diff --git a/llvm/lib/TableGen/TGParser.h b/llvm/lib/TableGen/TGParser.h --- a/llvm/lib/TableGen/TGParser.h +++ b/llvm/lib/TableGen/TGParser.h @@ -265,6 +265,8 @@ Record *CurRec); bool ParseOptionalRangeList(SmallVectorImpl &Ranges); bool ParseOptionalBitList(SmallVectorImpl &Ranges); + TypedInit *ParseSliceElement(Record *CurRec); + TypedInit *ParseSliceElements(Record *CurRec, bool Single = false); void ParseRangeList(SmallVectorImpl &Result); bool ParseRangePiece(SmallVectorImpl &Ranges, TypedInit *FirstItem = nullptr); diff --git a/llvm/lib/TableGen/TGParser.cpp b/llvm/lib/TableGen/TGParser.cpp --- a/llvm/lib/TableGen/TGParser.cpp +++ b/llvm/lib/TableGen/TGParser.cpp @@ -709,6 +709,148 @@ return Result; } +/// ParseSliceElement - Parse subscript or range +/// +/// SliceElement ::= Value> +/// SliceElement ::= Value +/// SliceElement ::= Value '...' Value +/// SliceElement ::= Value '-' Value (deprecated) +/// SliceElement ::= Value INTVAL(Negative; deprecated) +/// +/// SliceElement is either IntRecTy, ListRecTy, or nullptr +/// +TypedInit *TGParser::ParseSliceElement(Record *CurRec) { + auto LHSLoc = Lex.getLoc(); + auto *CurVal = ParseValue(CurRec); + if (!CurVal) + return nullptr; + auto *LHS = cast(CurVal); + + TypedInit *RHS = nullptr; + switch (Lex.getCode()) { + case tgtok::dotdotdot: + case tgtok::minus: { // Deprecated + Lex.Lex(); // eat + auto RHSLoc = Lex.getLoc(); + CurVal = ParseValue(CurRec); + if (!CurVal) + return nullptr; + RHS = cast(CurVal); + if (!isa(RHS->getType())) { + Error(RHSLoc, + "expected int...int, got " + Twine(RHS->getType()->getAsString())); + return nullptr; + } + break; + } + case tgtok::IntVal: { // Deprecated "-num" + auto i = -Lex.getCurIntVal(); + if (i < 0) { + TokError("invalid range, cannot be negative"); + return nullptr; + } + RHS = IntInit::get(Records, i); + Lex.Lex(); // eat IntVal + break; + } + default: // Single value (IntRecTy or ListRecTy) + return LHS; + } + + assert(RHS); + assert(isa(RHS->getType())); + + // Closed-interval range ... + if (!isa(LHS->getType())) { + Error(LHSLoc, + "expected int...int, got " + Twine(LHS->getType()->getAsString())); + return nullptr; + } + + return cast(BinOpInit::get(BinOpInit::RANGEC, LHS, RHS, + IntRecTy::get(Records)->getListTy()) + ->Fold(CurRec)); +} + +/// ParseSliceElements - Parse subscripts in square brackets. +/// +/// SliceElements ::= ( SliceElement ',' )* SliceElement ','? +/// +/// SliceElement is either IntRecTy, ListRecTy, or nullptr +/// +/// Returns ListRecTy by defaut. +/// Returns IntRecTy if; +/// - Single=true +/// - SliceElements is Value w/o trailing comma +/// +TypedInit *TGParser::ParseSliceElements(Record *CurRec, bool Single) { + TypedInit *CurVal; + SmallVector Elems; // int + SmallVector Slices; // list + + auto FlushElems = [&] { + if (!Elems.empty()) { + Slices.push_back(ListInit::get(Elems, IntRecTy::get(Records))); + Elems.clear(); + } + }; + + do { + auto LHSLoc = Lex.getLoc(); + CurVal = ParseSliceElement(CurRec); + if (!CurVal) + return nullptr; + auto *CurValTy = CurVal->getType(); + + if (auto *ListValTy = dyn_cast(CurValTy)) { + if (!isa(ListValTy->getElementType())) { + Error(LHSLoc, + "expected list, got " + Twine(ListValTy->getAsString())); + return nullptr; + } + + FlushElems(); + Slices.push_back(CurVal); + Single = false; + CurVal = nullptr; + } else if (!isa(CurValTy)) { + Error(LHSLoc, + "unhandled type " + Twine(CurValTy->getAsString()) + " in range"); + return nullptr; + } + + if (Lex.getCode() != tgtok::comma) + break; + + Lex.Lex(); // eat comma + + // `[i,]` is not LISTELEM but LISTSLICE + Single = false; + if (CurVal) + Elems.push_back(CurVal); + CurVal = nullptr; + } while (Lex.getCode() != tgtok::r_square); + + if (CurVal) { + // LISTELEM + if (Single) + return CurVal; + + Elems.push_back(CurVal); + } + + FlushElems(); + + // Concatenate lists in Slices + TypedInit *Result = nullptr; + for (auto *Slice : Slices) { + Result = (Result ? cast(BinOpInit::getListConcat(Result, Slice)) + : Slice); + } + + return Result; +} + /// ParseRangePiece - Parse a bit/value range. /// RangePiece ::= INTVAL /// RangePiece ::= INTVAL '...' INTVAL @@ -2593,10 +2735,11 @@ /// /// Value ::= SimpleValue ValueSuffix* /// ValueSuffix ::= '{' BitList '}' -/// ValueSuffix ::= '[' BitList ']' +/// ValueSuffix ::= '[' SliceElements ']' /// ValueSuffix ::= '.' ID /// Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType, IDParseMode Mode) { + SMLoc LHSLoc = Lex.getLoc(); Init *Result = ParseSimpleValue(CurRec, ItemType, Mode); if (!Result) return nullptr; @@ -2631,18 +2774,35 @@ break; } case tgtok::l_square: { - SMLoc SquareLoc = Lex.getLoc(); - Lex.Lex(); // eat the '[' - SmallVector Ranges; - ParseRangeList(Ranges); - if (Ranges.empty()) return nullptr; + auto *LHS = dyn_cast(Result); + if (!LHS) { + Error(LHSLoc, "Invalid value, list expected"); + return nullptr; + } - Result = Result->convertInitListSlice(Ranges); - if (!Result) { - Error(SquareLoc, "Invalid range for list slice"); + auto *LHSTy = dyn_cast(LHS->getType()); + if (!LHSTy) { + Error(LHSLoc, "Type '" + Twine(LHS->getType()->getAsString()) + + "' is invalid, list expected"); + return nullptr; + } + + Lex.Lex(); // eat the '[' + TypedInit *RHS = ParseSliceElements(CurRec, /*Single=*/true); + if (!RHS) return nullptr; + + if (isa(RHS->getType())) { + Result = + BinOpInit::get(BinOpInit::LISTSLICE, LHS, RHS, LHSTy)->Fold(CurRec); + } else { + Result = BinOpInit::get(BinOpInit::LISTELEM, LHS, RHS, + LHSTy->getElementType()) + ->Fold(CurRec); } + assert(Result); + // Eat the ']'. if (!consume(tgtok::r_square)) { TokError("expected ']' at end of list slice"); diff --git a/llvm/test/TableGen/ListSlices-fail.td b/llvm/test/TableGen/ListSlices-fail.td --- a/llvm/test/TableGen/ListSlices-fail.td +++ b/llvm/test/TableGen/ListSlices-fail.td @@ -19,37 +19,37 @@ #ifdef ERR2 // RUN: not llvm-tblgen %s -DERR2 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR2 -// ERR2: [[FILE]]:[[@LINE+1]]:35: error: expected integer or bitrange +// ERR2: [[FILE]]:[[@LINE+1]]:26: error: expected list, got list defvar errs = list_str [ list_str ] ; #endif #ifdef ERR3 // RUN: not llvm-tblgen %s -DERR3 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR3 -// ERR3: [[FILE]]:[[@LINE+1]]:35: error: expected integer or bitrange +// ERR3: [[FILE]]:[[@LINE+1]]:26: error: expected int...int, got list defvar errs = list_str [ list_str ... 42 ] ; #endif #ifdef ERR4 // RUN: not llvm-tblgen %s -DERR4 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR4 -// ERR4: [[FILE]]:[[@LINE+1]]:41: error: expected integer value as end of range +// ERR4: [[FILE]]:[[@LINE+1]]:32: error: expected int...int, got list defvar errs = list_str [ 0 ... list_str ] ; #endif #ifdef ERR5 // RUN: not llvm-tblgen %s -DERR5 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR5 -// ERR5: [[FILE]]:[[@LINE+1]]:30: error: expected integer or bitrange +// ERR5: [[FILE]]:[[@LINE+1]]:26: error: unhandled type string in range defvar errs = list_str [ str ] ; #endif #ifdef ERR6 // RUN: not llvm-tblgen %s -DERR6 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR6 -// ERR6: [[FILE]]:[[@LINE+1]]:30: error: invalid range, cannot be negative +// ERR6: [[FILE]]:[[@LINE+1]]:28: error: invalid range, cannot be negative defvar errs = list_str [ 5 1 ] ; #endif #ifdef ERR7 // RUN: not llvm-tblgen %s -DERR7 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR7 -// ERR7: [[FILE]]:[[@LINE+1]]:19: error: Invalid range for list slice +// ERR7: [[FILE]]:[[@LINE+1]]:15: error: Type 'string' is invalid, list expected defvar errs = str [ 0 ] ; #endif @@ -67,6 +67,6 @@ #ifdef ERRA // RUN: not llvm-tblgen %s -DERRA 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERRA -// ERRA: [[FILE]]:[[@LINE+1]]:19: error: Invalid range for list slice +// ERRA: [[FILE]]:[[@LINE+1]]:15: error: Invalid value, list expected defvar errs = und [ 0 ] ; #endif diff --git a/llvm/test/TableGen/ListSlices.td b/llvm/test/TableGen/ListSlices.td --- a/llvm/test/TableGen/ListSlices.td +++ b/llvm/test/TableGen/ListSlices.td @@ -123,3 +123,42 @@ int Zero = Class1<[?, ?, 2, 3, ?, 5, ?]>.Zero; list TwoFive = Class1<[?, ?, 2, 3, ?, 5, ?]>.TwoFive; } + +// Test list[list] and list[int] +// CHECK: def Rec11 +def Rec11 { + list s5 = Var1[0...4]; + + // list[expr] + // CHECK: list rev = [4, 3, 2, 1, 0]; + list rev = !foreach(i, s5, Var1[!sub(4, i)]); + + // Slice by list[foreach] + // CHECK: list revf = [4, 3, 2, 1, 0]; + list revf = Var1[!foreach(i, s5, !sub(4, i))]; + + // Simple slice + // CHECK: list rr = [0, 1, 2, 3, 4]; + list rr = rev[rev]; + + // Trailing comma is acceptable + // CHECK: list rr_ = [0, 1, 2, 3, 4]; + list rr_ = rev[rev,]; + + // Concatenation in slice + // CHECK: list rrr = [1, 2, 4, 3, 2, 1, 0, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 8]; + list empty = []; + list rrr = Var1[1, 2, rev, 3...6, 7, empty, rr, 8]; + + // Recognized as slice by the trailing comma + // CHECK: list> rl1 = {{\[}}[0], [1], [2], [3], [4]]; + list> rl1 = !foreach(i, rev, rev[i,]); + + // Slice by pair + // CHECK: list> rll = {{\[}}[0, 4], [1, 3], [2, 2], [3, 1], [4, 0]]; + list> rll = !foreach(i, rev, rev[i, !sub(4, i)]); + + // Slice by dynamic range + // CHECK: list> rlr = {{\[}}[4, 3, 2, 1, 0], [3, 2, 1], [2], [1, 2, 3], [0, 1, 2, 3, 4]]; + list> rlr = !foreach(i, s5, rev[i...!sub(4, i)]); +}