TableGen: Let expressions available to list subscripts and list slices

[chapuni]

Summary

This enables indexing in !foreach and permutation with list[permlist].

Enhancements in syntax:

• list<int> is applicable as a slice element.
• list[int,] is evaluated as not ElemType but list<ElemType> with a single element.

FIXME: I didn't apply new semantics to BitSlice.

TableGen: Prune convertInitListSlice and VarListElementInit

They were dedicated to constant version of list slice.

Depends on D147401

[chapuni]

• Fixup

[chapuni]

• - Add a testcase str[0]

[chapuni]

• Style fixes

[chapuni]

• Improve error messages
• Use cast<ty> as possible

[chapuni]

• Split out ParseSliceElement()
• Update a test

[chapuni]

• Rewrite tgtok::IntVal

[arsenm]

llvm/docs/TableGen/ProgRef.rst

527

This section is indented further than the others

530

Typo 'tyep'

llvm/lib/TableGen/TGParser.cpp

760

This assert seems redundant with the cast<> above

[chapuni]

• s/tyep/type/

[chapuni]

llvm/docs/TableGen/ProgRef.rst

527

It is intentional that this is the subitem as supplement, since I wanted to avoid rewriting whole this item.
Could I rewrote this flat? Or I am happy if you could suggest an alternative sentense.

llvm/lib/TableGen/TGParser.cpp

760

I intend this as catching RHS = nullptr by default.
Assignments are done in L738 and L752, and I would like to catch the assumption after cases in the switch (in the future).

[barannikov88]

llvm/docs/TableGen/ProgRef.rst

348

IIUC this is supposed to be normative and (negative) is not normative.

llvm/include/llvm/TableGen/Record.h

852

What is C in RANGEC? Please give a descriptive name.

llvm/lib/TableGen/TGParser.cpp

746

I don't get it how IntVal implies -. Could you explain?

788–789

Please give entities descriptive / canonical names.

2675–2678

The whole comment should be synced with the documentation.

2718

ParseSimpleValue is not guaranteed to return TypedInit, this should be an error.

2721–2722

It should point to the element, not the opening bracket.

[chapuni]

Thanks for reviews! I will fix them later.

llvm/docs/TableGen/ProgRef.rst

348

I could drop (negative) if you mention the notation.
I know this is less strict but I wanted to explain semantic here.

llvm/include/llvm/TableGen/Record.h

852

It is a retronym "RANGE (close interval)" to D145871 (RANGE as half-open interval).
Could I revise both names?

llvm/lib/TableGen/TGParser.cpp

746

See L754 in TGParser::ParseRangePiece().
Could I update this as // Expects "-num" (deprecated) ?

788–789

Will fix. How about Elems and Lists? I don't prefer longer names.

2675–2678

Excuse me, I don't understand the point.

2718

Understood. I will also try finding error cases.

2721–2722

Since I was convinced to look into another user of SquareLoc, I followed it.
Wouldn't it make sense to point SquareLoc as "error in whole range expression"?

[barannikov88]

I like the idea, but the implementation looks more like a PoC than a complete solution.
There is clearly an overlap between RangeList and SliceElements and I don't see why they should be distinct.
I am not a TableGen expert so take my words with a grain of salt. I won't be able to review it well.
Maybe @nhaehnle could take a look?

llvm/docs/TableGen/ProgRef.rst

348

You can update the comment below.

llvm/include/llvm/TableGen/Record.h

852

RANGE is fine in D145871 because it directly corresponds to a bang operator.
There is no operator in the language that corresponds to any of LISTELEM/LISTSLICE/RANGEC.

I wish I new TableGen better to suggest a way of properly handling this...
It feels like it would be better to update the deleted code instead of deleting it.

llvm/lib/TableGen/TGParser.cpp

746

I think it is because 1 - -2 parses the same as 1 2 because --2 == 2.

788–789

How about Elems and Lists?

Elems and Lists would be better if it is what they are.

2675–2678

The [old] doc says:

Value: `SimpleValue` `ValueSuffix`*
     :| `Value` "#" [`Value`]
ValueSuffix: "{" `RangeList` "}"
           :| "[" `RangeList` "]"
           :| "." `TokIdentifier`

The [old] comment should have been the same or (in different style):

Value: `SimpleValue` `ValueSuffix`*
Value: `Value` "#" [`Value`]
ValueSuffix: "{" `RangeList` "}"
ValueSuffix: "[" `RangeList` "]"
ValueSuffix: "." `TokIdentifier`

I.e. the current comment misses the paste operator (#) and refers to BitList, which seems to have been changed to RangeList as some point.

Since you are updating the comment it would be nice if it represents the current state of things.

2721–2722

Wouldn't it make sense to point SquareLoc as "error in whole range expression"?

The error message specifically says that LHS has invalid type. Pointing to opening '[' is misleading.
It may make sense (the error message should be changed then), but if you can give a better error location why don't do it?
You don't need to follow old code, it is not always guaranteed to be perfect.

[chapuni]

• TGParser::ParseValue(): Prune one error reporter, since Fold() doesn't return nullptr.
• llvm/test/TableGen/ListSlices-fail.td: Insert whitespaces in tokens
• Revise symbols in TGParser::ParseSliceElements()
• TGParser::ParseSimpleValue(): Report LHS position for LHS error.
• TGParser::ParseValue(): Detect untyped LHS in the list slice
• ProgRef.rst: Revise to mention also SliceElement.

[chapuni]

In D145872#4235592, @barannikov88 wrote:

I like the idea, but the implementation looks more like a PoC than a complete solution.
There is clearly an overlap between RangeList and SliceElements and I don't see why they should be distinct.

In fact I started this as PoC at first but I don't suppose this is still PoC..
When I dropped VarListElementInit, I thought I achieved a step of migrations.
I understand you feel this as PoC, though.

I think the new semantics could be applied also to list initializer.
I haven't done since it didn't prevent my other changes, for list manipulations.
OTOH, I didn't change BitSlice, because I thought it is satisfied with fixed length array.

I am still dubious I could reuse existing codes. They assume each value could be resolved in-place.

I propose this for the series of D145937. I supposed this was essential to them at first,
but I have noticed list indexing could be hacked with !listconcat !foldl, etc.
I could detach this out of D145937, if this would be supposed not ready for landing.

llvm/include/llvm/TableGen/Record.h

852

I have taken BinOpInit for them rather than a new TypedInit derivative, since they can be treated as operators with two values except that they are not bang operators.
I suppose it would make sense if OpInit tree might be handled as the expr tree (like other languages).

I could rewrite them as derivatives of TypeInit if OpInit should be bang operator as principle. Then I can guess they would be code duplication. I think it would not be smart.

@Paul-C-Anagnostopoulos @nhaehnle Thoughts? Could we expand OpInit for non-bang-ops?

llvm/lib/TableGen/TGParser.cpp

746

I suppose it to interpret 0-7. Tokenized as 0 and -7.
See also;
https://llvm.org/docs/TableGen/ProgRef.html#id10
https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/ARM/ARMScheduleA9.td#L2109

1 - -2 is tokenized as num:1 minus num:-2.
--2 as minus num:-2.

[chapuni]

• Detach D147401 as a pre-commit testcase

[chapuni]

• Update error messages

[nhaehnle]

I haven't looked at the implementation, but the overall idea seems quite reasonable.

llvm/docs/TableGen/ProgRef.rst

347–348

Should the "a-b" syntax be supported here at all? It may be time to get serious about deprecating it. Excising all the uses of "a-b" for bit slices would be tough, but I'd think that with lists we're in a better position?

[chapuni]

FYI, list[m-n] is used in 77 lines;
list[m - n] is not used!

clang/include/clang/Basic/riscv_vector.td |   4
llvm/lib/Target/ARM/ARMScheduleA57.td     | 118
llvm/lib/Target/ARM/ARMScheduleA9.td      |  32
3 files changed, 77 insertions(+), 77 deletions(-)

We could revise them, though, I think we don't need to do.

Bitslices are used in many (hundreds? thousands?) places, as you know, and fixing them would be ugly due to replacing one character - to three characters ....

llvm/docs/TableGen/ProgRef.rst

347–348

We could deprecate them here, though, I think we may leave old syntax,
if TGParser::ParseSliceElement() would be applied also to bitslice.

Deprecating would not gain the big win, I guess.

[chapuni]

• Use early break

[chapuni]

• Rebase onto D145871

[chapuni]

Is this ready for commit soon?
Or I would commit D146915 with not this but hacky ListAt<list,idx> and detach this from the series.

Let me know whatever I have to do. Thank you.

[arsenm]

llvm/docs/TableGen/ProgRef.rst

527

I'm not sure, I have a hard time judging what the rendered output of this will look like

llvm/lib/TableGen/Record.cpp

1210

demorgan the condition

[chapuni]

• Rewrite

[chapuni]

Style fixes in LISTELEM and LISTSLICE.

llvm/docs/TableGen/ProgRef.rst

 Note that all of the values have rules for converting them from one type to
 another. For example, these rules allow you to assign a value like ``7``
 to an entity of type ``bits<4>``.
 
 .. productionlist::
    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
   "``-``" 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

 
 *value*\ ``{17}``
     The final value is bit 17 of the integer *value* (note the braces).
 
 *value*\ ``{8...15}``
     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<int>`.
+
 *value*\ ``.``\ *field*
     The final value is the value of the specified *field* in the specified
     record *value*.
 
 The paste operator
 ------------------
 
 The paste operator (``#``) is the only infix operator available in TableGen

llvm/include/llvm/TableGen/Record.h

 //===- llvm/TableGen/Record.h - Classes for Table Records -------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
enum InitKind : uint8_t {
     IK_LastOpInit,
     IK_CondOpInit,
     IK_FoldOpInit,
     IK_IsAOpInit,
     IK_ExistsOpInit,
     IK_AnonymousNameInit,
     IK_StringInit,
     IK_VarInit,
-    IK_VarListElementInit,
     IK_VarBitInit,
     IK_VarDefInit,
     IK_LastTypedInit,
     IK_UnsetInit
   };
 
 private:
   const InitKind Kind;
public:
   /// This function is used to implement the bit range
   /// selection operator. Given a value, it selects the specified bits,
   /// returning them as a new \p Init of type \p bits. If it is not legal
   /// to use the bit selection operator on this value, null is returned.
   virtual Init *convertInitializerBitRange(ArrayRef<unsigned> Bits) const {
     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<unsigned> 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.
   virtual RecTy *getFieldType(StringInit *FieldName) const {
     return nullptr;
   }
 
   /// This function is used by classes that refer to other
public:
 
   /// Get the record keeper that initialized this Init.
   RecordKeeper &getRecordKeeper() const { return ValueTy->getRecordKeeper(); }
 
   Init *getCastTo(RecTy *Ty) const override;
   Init *convertInitializerTo(RecTy *Ty) const override;
 
   Init *convertInitializerBitRange(ArrayRef<unsigned> Bits) const override;
-  Init *convertInitListSlice(ArrayRef<unsigned> 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
   /// they are of type record.
   RecTy *getFieldType(StringInit *FieldName) const override;
 };
 
 /// '?' - Represents an uninitialized value.
Init *getElement(unsigned i) const {
     return getTrailingObjects<Init *>()[i];
   }
   RecTy *getElementType() const {
     return cast<ListRecTy>(getType())->getElementType();
   }
 
   Record *getElementAsRecord(unsigned i) const;
 
-  Init *convertInitListSlice(ArrayRef<unsigned> Elements) const override;
-
   Init *convertInitializerTo(RecTy *Ty) const override;
 
   /// This method is used by classes that refer to other
   /// variables which may not be defined at the time they expression is formed.
   /// If a value is set for the variable later, this method will be called on
   /// users of the value to allow the value to propagate out.
   ///
   Init *resolveReferences(Resolver &R) const override;
enum BinaryOp : uint8_t {
     OR,
     XOR,
     SHL,
     SRA,
     SRL,
     LISTCONCAT,
     LISTSPLAT,
     LISTREMOVE,
+    LISTELEM,
+    LISTSLICE,
+    RANGEC,
     STRCONCAT,
     INTERLEAVE,
     CONCAT,
     EQ,
     NE,
     LE,
     LT,
     GE,
public:
   Init *resolveReferences(Resolver &R) const override;
 
   Init *getBit(unsigned B) const override {
     assert(B < 1 && "Bit index out of range!");
     return const_cast<VarBitInit*>(this);
   }
 };
 
-/// 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<ListRecTy>(T->getType())->getElementType()),
-        TI(T), Element(E) {
-    assert(T->getType() && isa<ListRecTy>(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;
 
   Record *Def;
 
   explicit DefInit(Record *D);
 

llvm/lib/TableGen/Record.cpp

 //===- Record.cpp - Record implementation ---------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
struct RecordKeeperImpl {
   FoldingSet<UnOpInit> TheUnOpInitPool;
   FoldingSet<BinOpInit> TheBinOpInitPool;
   FoldingSet<TernOpInit> TheTernOpInitPool;
   FoldingSet<FoldOpInit> TheFoldOpInitPool;
   FoldingSet<IsAOpInit> TheIsAOpInitPool;
   FoldingSet<ExistsOpInit> TheExistsOpInitPool;
   DenseMap<std::pair<RecTy *, Init *>, VarInit *> TheVarInitPool;
   DenseMap<std::pair<TypedInit *, unsigned>, VarBitInit *> TheVarBitInitPool;
-  DenseMap<std::pair<TypedInit *, unsigned>, VarListElementInit *>
-      TheVarListElementInitPool;
   FoldingSet<VarDefInit> TheVarDefInitPool;
   DenseMap<std::pair<Init *, StringInit *>, FieldInit *> TheFieldInitPool;
   FoldingSet<CondOpInit> TheCondOpInitPool;
   FoldingSet<DagInit> TheDagInitPool;
   FoldingSet<RecordRecTy> RecordTypePool;
 
   unsigned AnonCounter;
   unsigned LastRecordID;
if (auto *LRT = dyn_cast<ListRecTy>(Ty)) {
     if (!Changed)
       return const_cast<ListInit*>(this);
     return ListInit::get(Elements, ElementType);
   }
 
   return nullptr;
 }
 
-Init *ListInit::convertInitListSlice(ArrayRef<unsigned> Elements) const {
-  if (Elements.size() == 1) {
-    if (Elements[0] >= size())
-      return nullptr;
-    return getElement(Elements[0]);
-  }
-
-  SmallVector<Init*, 8> 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<DefInit>(getElement(i));
   if (!DI)
     PrintFatalError("Expected record in list!");
   return DI->getDef();
 }
 
if (LHSs && RHSs) {
         }
         if (!Found)
           Args.push_back(EltLHS);
       }
       return ListInit::get(Args, LHSs->getElementType());
     }
     break;
   }
+  case LISTELEM: {
+    auto *TheList = dyn_cast<ListInit>(LHS);
+    auto *Idx = dyn_cast<IntInit>(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<ListInit>(LHS);
+    auto *SliceIdxs = dyn_cast<ListInit>(RHS);
+    if (TheList && SliceIdxs) {
+      SmallVector<Init *, 8> Args;
+      Args.reserve(SliceIdxs->size());
+      for (auto *I : *SliceIdxs) {
+        auto *II = dyn_cast<IntInit>(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<IntInit>(LHS);
+    auto *RHSi = dyn_cast<IntInit>(RHS);
+    if (LHSi && RHSi) {
+      auto Start = LHSi->getValue();
+      auto End = RHSi->getValue();
+      SmallVector<Init *, 8> Args;
+      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<StringInit>(LHS);
     StringInit *RHSs = dyn_cast<StringInit>(RHS);
     if (LHSs && RHSs)
       return ConcatStringInits(LHSs, RHSs);
     break;
   }
   case INTERLEAVE: {
if (LHS != lhs || RHS != rhs)
     return (BinOpInit::get(getOpcode(), lhs, rhs, getType()))
         ->Fold(R.getCurrentRecord());
   return const_cast<BinOpInit *>(this);
 }
 
 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;
   case MUL: Result = "!mul"; break;
   case DIV: Result = "!div"; break;
   case AND: Result = "!and"; break;
   case OR: Result = "!or"; break;
   case XOR: Result = "!xor"; break;
Init *TypedInit::getCastTo(RecTy *Ty) const {
 
   if (!getType()->typeIsConvertibleTo(Ty))
     return nullptr;
 
   return UnOpInit::get(UnOpInit::CAST, const_cast<TypedInit *>(this), Ty)
       ->Fold(nullptr);
 }
 
-Init *TypedInit::convertInitListSlice(ArrayRef<unsigned> Elements) const {
-  ListRecTy *T = dyn_cast<ListRecTy>(getType());
-  if (!T) return nullptr;  // Cannot subscript a non-list variable.
-
-  if (Elements.size() == 1)
-    return VarListElementInit::get(const_cast<TypedInit *>(this), Elements[0]);
-
-  SmallVector<Init*, 8> ListInits;
-  ListInits.reserve(Elements.size());
-  for (unsigned Element : Elements)
-    ListInits.push_back(VarListElementInit::get(const_cast<TypedInit *>(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);
 }
 
 VarInit *VarInit::get(Init *VN, RecTy *T) {
   detail::RecordKeeperImpl &RK = T->getRecordKeeper().getImpl();
   VarInit *&I = RK.TheVarInitPool[std::make_pair(T, VN)];

 Init *VarBitInit::resolveReferences(Resolver &R) const {
   Init *I = TI->resolveReferences(R);
   if (TI != I)
     return I->getBit(getBitNum());
 
   return const_cast<VarBitInit*>(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<ListInit>(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<TypedInit>(NewTI))
-    return VarListElementInit::get(cast<TypedInit>(NewTI), getElementNum());
-  return const_cast<VarListElementInit *>(this);
-}
-
-Init *VarListElementInit::getBit(unsigned Bit) const {
-  if (getType() == BitRecTy::get(getRecordKeeper()))
-    return const_cast<VarListElementInit*>(this);
-  return VarBitInit::get(const_cast<VarListElementInit*>(this), Bit);
-}
-
 DefInit::DefInit(Record *D)
     : TypedInit(IK_DefInit, D->getType()), Def(D) {}
 
 DefInit *DefInit::get(Record *R) {
   return R->getDefInit();
 }
 
 Init *DefInit::convertInitializerTo(RecTy *Ty) const {

llvm/lib/TableGen/TGParser.h

 //===- TGParser.h - Parser for TableGen Files -------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
void ParseValueList(SmallVectorImpl<llvm::Init*> &Result,
                       Record *CurRec, RecTy *ItemType = nullptr);
   bool ParseTemplateArgValueList(SmallVectorImpl<llvm::Init *> &Result,
                                  Record *CurRec, Record *ArgsRec);
   void ParseDagArgList(
       SmallVectorImpl<std::pair<llvm::Init*, StringInit*>> &Result,
       Record *CurRec);
   bool ParseOptionalRangeList(SmallVectorImpl<unsigned> &Ranges);
   bool ParseOptionalBitList(SmallVectorImpl<unsigned> &Ranges);
+  TypedInit *ParseSliceElement(Record *CurRec);
+  TypedInit *ParseSliceElements(Record *CurRec, bool Single = false);
   void ParseRangeList(SmallVectorImpl<unsigned> &Result);
   bool ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
                        TypedInit *FirstItem = nullptr);
   RecTy *ParseType();
   Init *ParseOperation(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationSubstr(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationFind(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType);

llvm/lib/TableGen/TGParser.cpp

 //===- TGParser.cpp - Parser for TableGen Files ---------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (ParseTemplateArgValueList(Result.TemplateArgs, &CurMC->Rec,
     return Result;
   }
 
   Result.RefRange.End = Lex.getLoc();
 
   return Result;
 }
 
+/// ParseSliceElement - Parse subscript or range
+///
+///  SliceElement  ::= Value<list<int>>
+///  SliceElement  ::= Value<int>
+///  SliceElement  ::= Value<int> '...' Value<int>
+///  SliceElement  ::= Value<int> '-' Value<int> (deprecated)
+///  SliceElement  ::= Value<int> 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<TypedInit>(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<TypedInit>(CurVal);
+    if (!isa<IntRecTy>(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<IntRecTy>(RHS->getType()));
+
+  // Closed-interval range <LHS:IntRecTy>...<RHS:IntRecTy>
+  if (!isa<IntRecTy>(LHS->getType())) {
+    Error(LHSLoc,
+          "expected int...int, got " + Twine(LHS->getType()->getAsString()));
+    return nullptr;
+  }
+
+  return cast<TypedInit>(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<int> w/o trailing comma
+///
+TypedInit *TGParser::ParseSliceElements(Record *CurRec, bool Single) {
+  TypedInit *CurVal;
+  SmallVector<Init *, 2> LoV;      // int
+  SmallVector<TypedInit *, 2> LoL; // list<int>
+
+  auto FlushLoV = [&] {
+    if (!LoV.empty()) {
+      LoL.push_back(ListInit::get(LoV, IntRecTy::get(Records)));
+      LoV.clear();
+    }
+    Single = false;
+  };
+
+  do {
+    auto LHSLoc = Lex.getLoc();
+    CurVal = ParseSliceElement(CurRec);
+    if (!CurVal)
+      return nullptr;
+    auto *CurValTy = CurVal->getType();
+
+    if (auto *ListValTy = dyn_cast<ListRecTy>(CurValTy)) {
+      if (!isa<IntRecTy>(ListValTy->getElementType())) {
+        Error(LHSLoc,
+              "expected list<int>, got " + Twine(ListValTy->getAsString()));
+        return nullptr;
+      }
+
+      FlushLoV();
+      LoL.push_back(CurVal);
+      CurVal = nullptr;
+    } else if (!isa<IntRecTy>(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)
+      LoV.push_back(CurVal);
+    CurVal = nullptr;
+  } while (Lex.getCode() != tgtok::r_square);
+
+  if (CurVal) {
+    // LISTELEM
+    if (Single)
+      return CurVal;
+
+    LoV.push_back(CurVal);
+  }
+
+  FlushLoV();
+
+  // Concatenate lists in LoL
+  TypedInit *Result = nullptr;
+  for (auto *LE : LoL) {
+    Result =
+        (Result ? cast<TypedInit>(BinOpInit::getListConcat(Result, LE)) : LE);
+  }
+
+  return Result;
+}
+
 /// ParseRangePiece - Parse a bit/value range.
 ///   RangePiece ::= INTVAL
 ///   RangePiece ::= INTVAL '...' INTVAL
 ///   RangePiece ::= INTVAL '-' INTVAL
 ///   RangePiece ::= INTVAL INTVAL 
 // The last two forms are deprecated.
 bool TGParser::ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
                                TypedInit *FirstItem) {
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   }
   }
 
   return R;
 }
 
 /// ParseValue - Parse a TableGen value. This returns null on error.
 ///
 ///   Value       ::= SimpleValue ValueSuffix*
 ///   ValueSuffix ::= '{' BitList '}'
-///   ValueSuffix ::= '[' BitList ']'
+///   ValueSuffix ::= '[' SliceElements ']'
 ///   ValueSuffix ::= '.' ID
 ///
 Init *TGParser::ParseValue(Record *CurRec, RecTy *ItemType, IDParseMode Mode) {
   Init *Result = ParseSimpleValue(CurRec, ItemType, Mode);
   if (!Result) return nullptr;
 
   // Parse the suffixes now if present.
   while (true) {
     switch (Lex.getCode()) {
case tgtok::l_brace: {
       if (!consume(tgtok::r_brace)) {
         TokError("expected '}' at end of bit range list");
         return nullptr;
       }
       break;
     }
     case tgtok::l_square: {
       SMLoc SquareLoc = Lex.getLoc();
+
+      auto *LHS = dyn_cast<TypedInit>(Result);
+      assert(LHS);
+      auto *LHSTy = dyn_cast<ListRecTy>(LHS->getType());
+      if (!LHSTy) {
+        Error(SquareLoc, "Type '" + Twine(LHS->getType()->getAsString()) +
+                             "' is invalid for list subscript");
+        return nullptr;
+      }
+
       Lex.Lex(); // eat the '['
-      SmallVector<unsigned, 16> Ranges;
-      ParseRangeList(Ranges);
-      if (Ranges.empty()) return nullptr;
+      TypedInit *RHS = ParseSliceElements(CurRec, /*Single=*/true);
+      if (!RHS)
+        return nullptr;
+
+      if (isa<ListRecTy>(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;
       }
 
       // Eat the ']'.
       if (!consume(tgtok::r_square)) {
         TokError("expected ']' at end of list slice");

llvm/test/TableGen/ListSlices-fail.td

+// 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: expected list<int>, got list<string>
+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: expected int...int, got list<string>
+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: expected int...int, got list<string>
+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 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]]: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
+
+#ifdef ERR8
+// RUN: not llvm-tblgen %s -DERR8 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR8
+// ERR8: [[FILE]]:[[@LINE+1]]:24: error: Unknown or reserved token when parsing a value
+defvar errs = list_int[...];
+#endif
+
+#ifdef ERR9
+// RUN: not llvm-tblgen %s -DERR9 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR9
+// ERR9: [[FILE]]:[[@LINE+1]]:28: error: Unknown or reserved token when parsing a value
+defvar errs = list_int[0...];
+#endif

llvm/test/TableGen/ListSlices.td

 // CHECK-NEXT:   list<int> TwoFive = [2, 3, ?, 5];
 
 def Rec09 : Class1<[?, ?, 2, 3, ?, 5, ?]>;
 
 def Rec10 {
   int Zero = Class1<[?, ?, 2, 3, ?, 5, ?]>.Zero;
   list<int> TwoFive = Class1<[?, ?, 2, 3, ?, 5, ?]>.TwoFive;
 }
+
+// Test list[list] and list[int]
+// CHECK: def Rec11
+def Rec11 {
+  list<int> s5 = Var1[0...4];
+
+  // list[expr]
+  // CHECK:   list<int> rev = [4, 3, 2, 1, 0];
+  list<int> rev = !foreach(i, s5, Var1[!sub(4, i)]);
+
+  // Slice by list[foreach]
+  // CHECK:   list<int> revf = [4, 3, 2, 1, 0];
+  list<int> revf = Var1[!foreach(i, s5, !sub(4, i))];
+
+  // Simple slice
+  // CHECK:   list<int> rr = [0, 1, 2, 3, 4];
+  list<int> rr  = rev[rev];
+
+  // Trailing comma is acceptable
+  // CHECK:   list<int> rr_ = [0, 1, 2, 3, 4];
+  list<int> rr_ = rev[rev,];
+
+  // Concatenation in slice
+  // CHECK:   list<int> rrr = [1, 2, 4, 3, 2, 1, 0, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 8];
+  list<int> empty = [];
+  list<int> rrr = Var1[1, 2, rev, 3...6, 7, empty, rr, 8];
+
+  // Recognized as slice by the trailing comma
+  // CHECK:   list<list<int>> rl1 = {{\[}}[0], [1], [2], [3], [4]];
+  list<list<int>> rl1 = !foreach(i, rev, rev[i,]);
+
+  // Slice by pair<int,int>
+  // CHECK:   list<list<int>> rll = {{\[}}[0, 4], [1, 3], [2, 2], [3, 1], [4, 0]];
+  list<list<int>> rll = !foreach(i, rev, rev[i, !sub(4, i)]);
+
+  // Slice by dynamic range
+  // CHECK:   list<list<int>> rlr = {{\[}}[4, 3, 2, 1, 0], [3, 2, 1], [2], [1, 2, 3], [0, 1, 2, 3, 4]];
+  list<list<int>> rlr = !foreach(i, s5, rev[i...!sub(4, i)]);
+}