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 ↗

(On Diff #507386)

This section is indented further than the others

530 ↗

(On Diff #507386)

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 ↗

(On Diff #507386)

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 ↗

(On Diff #509833)

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

llvm/include/llvm/TableGen/Record.h

850

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.

2736–2739

The whole comment should be synced with the documentation.

2779

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

2782–2783

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 ↗

(On Diff #509833)

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

850

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.

2736–2739

Excuse me, I don't understand the point.

2779

Understood. I will also try finding error cases.

2782–2783

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 ↗

(On Diff #509833)

You can update the comment below.

llvm/include/llvm/TableGen/Record.h

850

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.

2736–2739

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.

2782–2783

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

850

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 ↗

(On Diff #510311)

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 ↗

(On Diff #510311)

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 ↗

(On Diff #507386)

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

llvm/lib/TableGen/Record.cpp

1205

demorgan the condition

[chapuni]

• Rewrite

[chapuni]

Style fixes in LISTELEM and LISTSLICE.

llvm/include/llvm/TableGen/Record.h

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 {
     SHL,
     SRA,
     SRL,
     LISTCONCAT,
     LISTSPLAT,
     LISTREMOVE,
     LISTELEM,
     LISTSLICE,
     RANGE,
     RANGEC,
     STRCONCAT,
     INTERLEAVE,
     CONCAT,
     EQ,
     NE,
     LE,
     LT,
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

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();
 }
 
case LISTSLICE: {
     if (!TheList || !SliceIdxs)
       break;
     SmallVector<Init *, 8> Args;
     Args.reserve(SliceIdxs->size());
     for (auto *I : *SliceIdxs) {
       auto *II = dyn_cast<IntInit>(I);
       if (!II)
         goto unresolved;
       auto i = II->getValue();
       if (i < 0 || i >= (ssize_t)TheList->size())
         goto unresolved;
       Args.push_back(TheList->getElement(i));
     }
     return ListInit::get(Args, TheList->getElementType());
   }
   case RANGE:
   case RANGEC: {
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(Record *D)
+    : TypedInit(IK_DefInit, D->getType()), Def(D) {}
 
 DefInit *DefInit::get(Record *R) {
   return R->getDefInit();
 }
 
 Init *DefInit::convertInitializerTo(RecTy *Ty) const {
   if (auto *RRT = dyn_cast<RecordRecTy>(Ty))
     if (getType()->typeIsConvertibleTo(RRT))

llvm/lib/TableGen/TGParser.cpp

case tgtok::minus: { // Deprecated
     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 *RHSi = IntInit::get(Records, -Lex.getCurIntVal());
-    if (RHSi->getValue() < 0) {
+    auto i = -Lex.getCurIntVal();
+    if (i < 0) {
       TokError("invalid range, cannot be negative");
       return nullptr;
     }
-    RHS = RHSi;
+    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;
   }

 ///
 /// 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> Elems;       // int
   SmallVector<TypedInit *, 2> Slices; // list<int>
 
   auto FlushElems = [&] {
     if (!Elems.empty()) {
       Slices.push_back(ListInit::get(Elems, IntRecTy::get(Records)));
       Elems.clear();
     }
   };
 
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 ::= '[' 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;
 
   // Parse the suffixes now if present.
   while (true) {
case tgtok::l_brace: {
         TokError("expected '}' at end of bit range list");
         return nullptr;
       }
       break;
     }
     case tgtok::l_square: {
       auto *LHS = dyn_cast<TypedInit>(Result);
       if (!LHS) {
         Error(LHSLoc, "Invalid value, list expected");
         return nullptr;
       }
 
       auto *LHSTy = dyn_cast<ListRecTy>(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);