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 @@ -334,13 +334,18 @@ 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`(negative) .. warning:: The peculiar last form of :token:`RangePiece` is due to the fact that the @@ -504,17 +509,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 tyep 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 @@ -316,7 +316,6 @@ IK_AnonymousNameInit, IK_StringInit, IK_VarInit, - IK_VarListElementInit, IK_VarBitInit, IK_VarDefInit, IK_LastTypedInit, @@ -386,14 +385,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. @@ -445,7 +436,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 @@ -726,8 +716,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 @@ -859,6 +847,9 @@ LISTCONCAT, LISTSPLAT, LISTREMOVE, + LISTELEM, + LISTSLICE, + RANGEC, STRCONCAT, INTERLEAVE, CONCAT, @@ -1240,39 +1231,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; @@ -676,23 +674,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)); @@ -1206,6 +1187,59 @@ } break; } + 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 RANGEC: { + auto *LHSi = dyn_cast(LHS); + auto *RHSi = dyn_cast(RHS); + if (LHSi && RHSi) { + auto Start = LHSi->getValue(); + auto End = RHSi->getValue(); + SmallVector Args; + // 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)); + } + return ListInit::get(Args, LHSi->getType()); + } + break; + } case STRCONCAT: { StringInit *LHSs = dyn_cast(LHS); StringInit *RHSs = dyn_cast(RHS); @@ -1311,6 +1345,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; @@ -1894,22 +1933,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); @@ -1960,37 +1983,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,7 @@ Record *CurRec); bool ParseOptionalRangeList(SmallVectorImpl &Ranges); bool ParseOptionalBitList(SmallVectorImpl &Ranges); + 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,128 @@ return Result; } +/// ParseSliceElements - Parse subscripts in square brackets. +/// +/// SliceElements ::= ( SliceElement ',' )* SliceElement ','? +/// SliceElement ::= Value> +/// SliceElement ::= Value +/// SliceElement ::= Value '...' Value +/// SliceElement ::= Value '-' Value (deprecated) +/// SliceElement ::= Value INTVAL(Negative; deprecated) +/// +/// 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 = nullptr; + SmallVector LoV; // int + SmallVector LoL; // list + auto *IntTy = IntRecTy::get(Records); + + auto FlushLoV = [&] { + if (!LoV.empty()) { + LoL.push_back(ListInit::get(LoV, IntTy)); + LoV.clear(); + } + Single = false; + }; + + do { + if (CurVal) + LoV.push_back(CurVal); + + auto LHSLoc = Lex.getLoc(); + auto *LHS = ParseValue(CurRec); + if (!LHS) + return nullptr; + CurVal = dyn_cast(LHS); + assert(CurVal); + + TypedInit *RHS = nullptr; + switch (Lex.getCode()) { + case tgtok::dotdotdot: + case tgtok::minus: { // Deprecated + Lex.Lex(); // eat + auto RHSLoc = Lex.getLoc(); + RHS = dyn_cast(ParseValue(CurRec)); + if (!isa(RHS->getType())) { + Error(RHSLoc, "range should be int...int"); + return nullptr; + } + break; + } + case tgtok::IntVal: { // Deprecated "-num" + RHS = IntInit::get(Records, -Lex.getCurIntVal()); + if (dyn_cast(RHS)->getValue() < 0) { + TokError("invalid range, cannot be negative"); + return nullptr; + } + Lex.Lex(); // eat IntVal + break; + } + default: + break; + } + + if (RHS) { + // Closed-interval range ... + if (!isa(CurVal->getType())) { + Error(LHSLoc, "range should be int...int"); + return nullptr; + } + + FlushLoV(); + LoL.push_back(dyn_cast( + BinOpInit::get(BinOpInit::RANGEC, CurVal, RHS, IntTy->getListTy()) + ->Fold(CurRec))); + CurVal = nullptr; + } else { + // Single value (not a range) + if (auto *LHSTy = dyn_cast(CurVal->getType())) { + if (!isa(LHSTy->getElementType())) { + Error(LHSLoc, "should be list"); + return nullptr; + } + // list + FlushLoV(); + LoL.push_back(CurVal); + CurVal = nullptr; + } else if (isa(CurVal->getType())) { + // int -- `CurVal` will be added lazily. + } else { + Error(LHSLoc, "unhandled type in range"); + return nullptr; + } + } + + if (Lex.getCode() != tgtok::comma) + break; + + Lex.Lex(); // eat comma + Single = false; + } while (Lex.getCode() != tgtok::r_square); + + if (CurVal) { + if (Single) + return CurVal; + + LoV.push_back(CurVal); + } + + FlushLoV(); + + TypedInit *Result = nullptr; + for (auto *LE : LoL) { + Result = (Result ? dyn_cast(BinOpInit::getListConcat(Result, LE)) + : LE); + assert(Result); + } + + return Result; +} + /// ParseRangePiece - Parse a bit/value range. /// RangePiece ::= INTVAL /// RangePiece ::= INTVAL '...' INTVAL @@ -2532,7 +2654,7 @@ /// /// Value ::= SimpleValue ValueSuffix* /// ValueSuffix ::= '{' BitList '}' -/// ValueSuffix ::= '[' BitList ']' +/// ValueSuffix ::= '[' SliceElements ']' /// ValueSuffix ::= '.' ID /// Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType, IDParseMode Mode) { @@ -2571,12 +2693,30 @@ } case tgtok::l_square: { SMLoc SquareLoc = Lex.getLoc(); + + auto *LHS = dyn_cast(Result); + assert(LHS); + auto *LHSTy = dyn_cast(LHS->getType()); + if (!LHSTy) { + Error(SquareLoc, "Type '" + Twine(LHS->getType()->getAsString()) + + "' is invalid for list subscript"); + return nullptr; + } + Lex.Lex(); // eat the '[' - SmallVector Ranges; - ParseRangeList(Ranges); - if (Ranges.empty()) return nullptr; + 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); + } - Result = Result->convertInitListSlice(Ranges); if (!Result) { Error(SquareLoc, "Invalid range for list slice"); return nullptr; diff --git a/llvm/test/TableGen/ListSlices-fail.td b/llvm/test/TableGen/ListSlices-fail.td new file mode 100644 --- /dev/null +++ b/llvm/test/TableGen/ListSlices-fail.td @@ -0,0 +1,53 @@ +// Each RUN line is scattered. + +defvar list_int = [0, 1, 2, 3, 4, 5]; +defvar list_str = ["foo", "bar"]; +defvar str = "hoge"; + +#ifdef ERR0 +// RUN: not llvm-tblgen %s -DERR0 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR0 +// ERR0: [[FILE]]:[[@LINE+1]]:24: error: Unknown or reserved token when parsing a value +defvar errs = list_str[]; +#endif + +#ifdef ERR1 +// RUN: not llvm-tblgen %s -DERR1 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR1 +// ERR1: [[FILE]]:[[@LINE+1]]:24: error: Unknown or reserved token when parsing a value +defvar errs = list_str[,]; +#endif + +#ifdef ERR2 +// RUN: not llvm-tblgen %s -DERR2 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR2 +// ERR2: [[FILE]]:[[@LINE+1]]:24: error: should be 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]]:24: error: range should be int...int +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]]:28: error: range should be int...int +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]]:24: error: unhandled type 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]]:26: 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]]:18: error: Type 'string' is invalid for list subscript +defvar errs = str[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)]); +}