TableGen: Introduce `!range` operator for half-opened interval

[chapuni]

Summary

!range(a, b) generates a list [a,b). a is optional and 0 by default.

• !range(-1, 4) generates [-1, 0, 1, 2, 3]
• !range(4) generates [0, 1, 2, 3]
• !range(2, 2) generates []<list<int>>

!range(list) is equivalent to !range(0, !size(list)).

[chapuni]

• Fixup

[chapuni]

• Add a test case

[Paul-C-Anagnostopoulos]

I'm tempted to suggest that this bang operator should be called !rangelist. The name !range suggests a pair of integers or a sequence of integers not encapsulated in a list. Add a couple of other reviewers so we can get a second opinion.

Add some simpler initial tests to range-op.td, such as the examples you gave in the summary.

[chapuni]

Thanks for your comment.

!range(m, n) and !range(n) come from Python.
!range(list) is just a syntax sugar.

I will accept even if a minimal functionality (m, n) would be landed. Do you think I should drop other syntax sugars?

Add a couple of other reviewers so we can get a second opinion.

I will happy if you could nominate anyone, since you ask a second opinion.

Add some simpler initial tests to range-op.td, such as the examples you gave in the summary.

I didn't think I could add simpler examples to the test. I will do if it would be better.

[Paul-C-Anagnostopoulos]

I've added two reviewers. Could I get a second opinion on the name of this bang operator?

I think a few simpler tests first is a good idea. In particular, it helps a future developer understand what is going on.

[chapuni]

• Update a test more descriptive

[Paul-C-Anagnostopoulos]

Nice new tests. Thanks!

[nhaehnle]

!range makes sense to me because I also see the analogy to Python's range.

I have some minor notes inline, apart from that the code looks good to me.

llvm/lib/TableGen/TGParser.cpp

1508

You're relying here on the cast always being successful (which makes sense), so you should use cast instead of dyn_cast. (This has the benefit of raising an assertion if the cast fails.)

1509

Using a switch for this instead of an if/else chain is a bit unorthodox, but I suppose we can live with it.

1525

Also here: use cast instead of dyn_cast

[Paul-C-Anagnostopoulos]

I see the analogy to Python's range(), except that it returns a sequence of numbers, not a list. But I'm not really too worried about this.

[chapuni]

• Use cast<ty> rather than dyn_cast<ty> when <ty> is assumed.
• Add a testcase.
• Other cleanups

[chapuni]

llvm/lib/TableGen/TGParser.cpp

1508

I have misunderstood cast<ty> as it would crash with incompatible type.
Thanks for pointing out.

1509

I avoided duplicate usages of InitList.size(), even if they were optimized out.

[arsenm]

llvm/lib/TableGen/TGParser.cpp

1526

I still see separate isa and cast?

llvm/test/TableGen/range-op-fail.td

27

Test with mixed integer and not-integer

[chapuni]

• Make Arg1 consistent

[chapuni]

@arsenm Thanks for your reviews!

llvm/lib/TableGen/TGParser.cpp

1526

The inner cast was for TypedInit::getType(). Anyways, I have rewritten more consistent.

llvm/test/TableGen/range-op-fail.td

27

This detects that 1st arg is not integer.
OTOH, I suppose ERR1 would cover if 1st arg was integer.

[arsenm]

llvm/lib/TableGen/Record.cpp

1212

Can early break and reduce indentation

llvm/test/TableGen/range-op-fail.td

27

Right but you aren't testing the error is produced for each position individually

[chapuni]

• Use early break
• range-op-fail.td: Let unnumbered
• Add ERR_UNEXPECTED_TYPE(s)

[chapuni]

llvm/lib/TableGen/Record.cpp

1212

I followed old code style around. Updated.
(Frankly said, I started from copypaste)

llvm/test/TableGen/range-op-fail.td

27

Put string for each position.
(and rename cases as unnumbered)

[chapuni]

Ping. Any other issues?

[Paul-C-Anagnostopoulos]

I don't see the documentation for this new operator. Did it go in already?

[chapuni]

@Paul-C-Anagnostopoulos I suppose ProgRef.rst would satisfy. Would I miss anything?

[Paul-C-Anagnostopoulos]

Yes, that's the file. You need to add the name to the list in section 1.3.3 and the description to section 1.10.

[chapuni]

• Rebase
• ProgRef.rst: Update bang ops index

[chapuni]

@Paul-C-Anagnostopoulos Updated. Okay?

[Paul-C-Anagnostopoulos]

I can't figure out what is going on here. It doesn't look like you added a description of !range.

[chapuni]

llvm/docs/TableGen/ProgRef.rst

1785–1792

@Paul-C-Anagnostopoulos Is it insufficient or improper?

[Paul-C-Anagnostopoulos]

llvm/docs/TableGen/ProgRef.rst

1785–1792

Say: The result is ...
If *a* `>=` *b*, then the result is ...

[chapuni]

llvm/docs/TableGen/ProgRef.rst

1785–1792

How about them?

• Omit the sentence "Its result is...", since it is obvious.
• Revise the last sentence as your suggestion.

[Paul-C-Anagnostopoulos]

llvm/docs/TableGen/ProgRef.rst

1785–1792

I would keep both sentences about the results.

[chapuni]

• ProgRef.rst: Revise the description

[foad]

Late naming suggestion: !iota

But I am also fine with !range

llvm/docs/TableGen/ProgRef.rst

``!not(``\ *a*\ ``)``
     an integer. The argument 0 results in 1 (true); any other
     argument results in 0 (false).
 
 ``!or(``\ *a*\ ``,`` *b*\ ``, ...)``
     This operator does a bitwise OR on *a*, *b*, etc., and produces the
     result. A logical OR can be performed if all the arguments are either
     0 or 1.
 
+``!range([``\ *a*\ ``,``] *b*\ ``)``
+    This operator produces half-open range sequence ``[a : b)`` as ``list<int>``.
+    *a* is ``0`` by default. ``!range(4)`` is equivalent to ``!range(0, 4)``.
+    Its result is `[0, 1, 2, 3]`.
+    The result is `[]<list<int>>` if *a* ``>=`` *b*.
+
+``!range([``\ *list*\ ``)``
+    Equivalent to ``!range(0, !size(list))``.
+
 ``!setdagop(``\ *dag*\ ``,`` *op*\ ``)``
     This operator produces a DAG node with the same arguments as *dag*, but with its
     operator replaced with *op*.
 
     Example: ``!setdagop((foo 1, 2), bar)`` results in ``(bar 1, 2)``.
 
 ``!shl(``\ *a*\ ``,`` *count*\ ``)``
     This operator shifts *a* left logically by *count* bits and produces the resulting

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 BinaryOp : uint8_t {
     OR,
     XOR,
     SHL,
     SRA,
     SRL,
     LISTCONCAT,
     LISTSPLAT,
     LISTREMOVE,
+    RANGE,
     STRCONCAT,
     INTERLEAVE,
     CONCAT,
     EQ,
     NE,
     LE,
     LT,
     GE,

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
 //
 //===----------------------------------------------------------------------===//
 //
if (LHSs && RHSs) {
         }
         if (!Found)
           Args.push_back(EltLHS);
       }
       return ListInit::get(Args, LHSs->getElementType());
     }
     break;
   }
+  case RANGE: {
+    IntInit *LHSi = dyn_cast<IntInit>(LHS);
+    IntInit *RHSi = dyn_cast<IntInit>(RHS);
+    if (LHSi && RHSi) {
+      auto Start = LHSi->getValue();
+      auto End = RHSi->getValue();
+      SmallVector<Init *, 8> Args;
+      if (Start < End) {
+        Args.reserve(End - Start);
+        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: {
std::string BinOpInit::getAsString() const {
   case NE: Result = "!ne"; break;
   case LE: Result = "!le"; break;
   case LT: Result = "!lt"; break;
   case GE: Result = "!ge"; break;
   case GT: Result = "!gt"; break;
   case LISTCONCAT: Result = "!listconcat"; break;
   case LISTSPLAT: Result = "!listsplat"; break;
   case LISTREMOVE: Result = "!listremove"; break;
+  case RANGE: Result = "!range"; break;
   case STRCONCAT: Result = "!strconcat"; break;
   case INTERLEAVE: Result = "!interleave"; break;
   case SETDAGOP: Result = "!setdagop"; break;
   }
   return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
 }
 
 static void

llvm/lib/TableGen/TGLexer.h

 //===- TGLexer.h - Lexer 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
 //
 //===----------------------------------------------------------------------===//
 //
// existing 'Else' that means the preprocessor #else.)
     FalseKW, Field, Foreach, If, In, Include, Int, Let, List, MultiClass,
     String, Then, TrueKW,
 
   // Bang operators.
     XConcat, XADD, XSUB, XMUL, XDIV, XNOT, XLOG2, XAND, XOR, XXOR, XSRA, XSRL,
     XSHL, XListConcat, XListSplat, XStrConcat, XInterleave, XSubstr, XFind,
     XCast, XSubst, XForEach, XFilter, XFoldl, XHead, XTail, XSize, XEmpty, XIf,
     XCond, XEq, XIsA, XDag, XNe, XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
-    XExists, XListRemove,  XToLower, XToUpper,
+    XExists, XListRemove,  XToLower, XToUpper, XRange,
 
   // Boolean literals.
     TrueVal, FalseVal,
 
   // Integer value.
   IntVal,
 
   // Binary constant.  Note that these are sized according to the number of

llvm/lib/TableGen/TGLexer.cpp

 //===- TGLexer.cpp - Lexer for TableGen -----------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
tgtok::TokKind Kind =
           .Case("empty", tgtok::XEmpty)
           .Case("subst", tgtok::XSubst)
           .Case("foldl", tgtok::XFoldl)
           .Case("foreach", tgtok::XForEach)
           .Case("filter", tgtok::XFilter)
           .Case("listconcat", tgtok::XListConcat)
           .Case("listsplat", tgtok::XListSplat)
           .Case("listremove", tgtok::XListRemove)
+          .Case("range", tgtok::XRange)
           .Case("strconcat", tgtok::XStrConcat)
           .Case("interleave", tgtok::XInterleave)
           .Case("substr", tgtok::XSubstr)
           .Case("find", tgtok::XFind)
           .Cases("setdagop", "setop", tgtok::XSetDagOp) // !setop is deprecated.
           .Cases("getdagop", "getop", tgtok::XGetDagOp) // !getop is deprecated.
           .Case("exists", tgtok::XExists)
           .Case("tolower", tgtok::XToLower)

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
 //
 //===----------------------------------------------------------------------===//
 //
Init *TGParser::ParseOperation(Record *CurRec, RecTy *ItemType) {
   case tgtok::XNe:
   case tgtok::XLe:
   case tgtok::XLt:
   case tgtok::XGe:
   case tgtok::XGt:
   case tgtok::XListConcat:
   case tgtok::XListSplat:
   case tgtok::XListRemove:
+  case tgtok::XRange:
   case tgtok::XStrConcat:
   case tgtok::XInterleave:
   case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     tgtok::TokKind OpTok = Lex.getCode();
     SMLoc OpLoc = Lex.getLoc();
     Lex.Lex();  // eat the operation
 
     BinOpInit::BinaryOp Code;
case tgtok::XSetDagOp: { // Value ::= !binop '(' Value ',' Value ')'
     case tgtok::XNe:     Code = BinOpInit::NE; break;
     case tgtok::XLe:     Code = BinOpInit::LE; break;
     case tgtok::XLt:     Code = BinOpInit::LT; break;
     case tgtok::XGe:     Code = BinOpInit::GE; break;
     case tgtok::XGt:     Code = BinOpInit::GT; break;
     case tgtok::XListConcat: Code = BinOpInit::LISTCONCAT; break;
     case tgtok::XListSplat:  Code = BinOpInit::LISTSPLAT; break;
     case tgtok::XListRemove: Code = BinOpInit::LISTREMOVE; break;
+    case tgtok::XRange:      Code = BinOpInit::RANGE; break;
     case tgtok::XStrConcat:  Code = BinOpInit::STRCONCAT; break;
     case tgtok::XInterleave: Code = BinOpInit::INTERLEAVE; break;
     case tgtok::XSetDagOp:   Code = BinOpInit::SETDAGOP; break;
     }
 
     RecTy *Type = nullptr;
     RecTy *ArgType = nullptr;
     switch (OpTok) {
case tgtok::XListConcat:
       break;
     case tgtok::XListSplat:
       // Can't do any typechecking until we parse the first argument.
       break;
     case tgtok::XListRemove:
       // We don't know the list type until we parse the first argument.
       ArgType = ItemType;
       break;
+    case tgtok::XRange:
+      Type = IntRecTy::get(Records)->getListTy();
+      // ArgType may be either Int or List.
+      break;
     case tgtok::XStrConcat:
       Type = StringRecTy::get(Records);
       ArgType = StringRecTy::get(Records);
       break;
     case tgtok::XInterleave:
       Type = StringRecTy::get(Records);
       // The first argument type is not yet known.
     }
for (;;) {
           break;
         case BinOpInit::LISTREMOVE:
           if (!isa<ListRecTy>(ArgType)) {
             Error(InitLoc, Twine("expected a list, got value of type '") +
                                ArgType->getAsString() + "'");
             return nullptr;
           }
           break;
+        case BinOpInit::RANGE:
+          if (InitList.size() == 1) {
+            if (isa<ListRecTy>(ArgType)) {
+              ArgType = nullptr;
+              break;
+            } else if (!isa<IntRecTy>(ArgType)) {
+              Error(InitLoc,
+                    Twine("expected list or int, got value of type '") +
+                        ArgType->getAsString() + "'");
+              return nullptr;
+            }
+          } else {
+            if (isa<IntRecTy>(dyn_cast<TypedInit>(InitList[1])->getType())) {
+              Error(InitLoc,
+                    Twine("expected one list, got extra value of type '") +
+                        ArgType->getAsString() + "'");
+              return nullptr;
+            }
+          }
+          break;
         case BinOpInit::EQ:
         case BinOpInit::NE:
           if (!ArgType->typeIsConvertibleTo(IntRecTy::get(Records)) &&
               !ArgType->typeIsConvertibleTo(StringRecTy::get(Records)) &&
               !ArgType->typeIsConvertibleTo(RecordRecTy::get(Records, {}))) {
             Error(InitLoc, Twine("expected bit, bits, int, string, or record; "
                                  "got value of type '") + ArgType->getAsString() + 
                                  "'");
if (Code == BinOpInit::LISTCONCAT)
       Type = ArgType;
     // listsplat returns a list of type of the *first* argument.
     if (Code == BinOpInit::LISTSPLAT)
       Type = cast<TypedInit>(InitList.front())->getType()->getListTy();
     // listremove returns a list with type of the argument.
     if (Code == BinOpInit::LISTREMOVE)
       Type = ArgType;
 
+    if (Code == BinOpInit::RANGE) {
+      Init *LHS, *RHS;
+      TypedInit *Arg0 = dyn_cast<TypedInit>(InitList[0]);
+      switch (InitList.size()) {
+      case 1:
+        if (isa<ListRecTy>(Arg0->getType())) {
+          // (0, !size(arg))
+          LHS = IntInit::get(Records, 0);
+          RHS = UnOpInit::get(UnOpInit::SIZE, Arg0, IntRecTy::get(Records))
+                    ->Fold(CurRec);
+        } else {
+          assert(isa<IntRecTy>(Arg0->getType()));
+          // (0, arg)
+          LHS = IntInit::get(Records, 0);
+          RHS = Arg0;
+        }
+        break;
+      case 2:
+        assert(isa<IntRecTy>(Arg0->getType()));
+        assert(isa<IntRecTy>(dyn_cast<TypedInit>(InitList[1])->getType()));
+        LHS = Arg0;
+        RHS = InitList[1];
+        break;
+      default:
+        Error(OpLoc, "expected at most two integer");
+        return nullptr;
+      }
+      return BinOpInit::get(Code, LHS, RHS, Type)->Fold(CurRec);
+    }
+
     // We allow multiple operands to associative operators like !strconcat as
     // shorthand for nesting them.
     if (Code == BinOpInit::STRCONCAT || Code == BinOpInit::LISTCONCAT ||
         Code == BinOpInit::CONCAT || Code == BinOpInit::ADD ||
         Code == BinOpInit::AND || Code == BinOpInit::OR ||
         Code == BinOpInit::XOR || Code == BinOpInit::MUL) {
       while (InitList.size() > 2) {
         Init *RHS = InitList.pop_back_val();

 ///   SimpleValue ::= DIVTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SUBTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= LISTCONCATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= LISTSPLATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= LISTREMOVETOK '(' Value ',' Value ')'
+///   SimpleValue ::= RANGE '(' Value ')'
+///   SimpleValue ::= RANGE '(' Value ',' Value ')'
 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= COND '(' [Value ':' Value,]+ ')'
 ///
 Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
                                  IDParseMode Mode) {
   Init *R = nullptr;
   switch (Lex.getCode()) {
   default: TokError("Unknown or reserved token when parsing a value"); break;
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XNe:
   case tgtok::XLe:
   case tgtok::XLt:
   case tgtok::XGe:
   case tgtok::XGt:
   case tgtok::XListConcat:
   case tgtok::XListSplat:
   case tgtok::XListRemove:
+  case tgtok::XRange:
   case tgtok::XStrConcat:
   case tgtok::XInterleave:
   case tgtok::XSetDagOp: // Value ::= !binop '(' Value ',' Value ')'
   case tgtok::XIf:
   case tgtok::XCond:
   case tgtok::XFoldl:
   case tgtok::XForEach:
   case tgtok::XFilter:

llvm/test/TableGen/range-op-fail.td

+// Each RUN line is scattered.
+
+defvar list_int = !range(4);
+
+#ifdef ERR0
+// RUN: not llvm-tblgen %s -DERR0 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR0
+// ERR0: [[FILE]]:[[@LINE+1]]:32: error: expected one list, got extra value of type 'int'
+defvar err0 = !range(list_int, 42);
+#endif
+
+#ifdef ERR1
+// RUN: not llvm-tblgen %s -DERR1 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR1
+// ERR1: [[FILE]]:[[@LINE+1]]:25: error: expected value of type 'int', got 'list<int>'
+defvar err1 = !range(0, list_int);
+#endif
+
+#ifdef ERR2
+// RUN: not llvm-tblgen %s -DERR2 2>&1 | FileCheck -DFILE=%s %s --check-prefix=ERR2
+// ERR2: [[FILE]]:[[@LINE+1]]:15: error: expected at most two integer
+defvar err3 = !range(0, 42, 255);
+#endif

llvm/test/TableGen/range-op.td

+// RUN: llvm-tblgen %s | FileCheck %s
+// XFAIL: vg_leak
+
+defvar idxs = !range(8);
+
+// CHECK: def range_op_ranges {
+def range_op_ranges {
+  // CHECK: list<list<int>> r0 = {{\[}}[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5, 6]];
+  list<list<int>> r0 = !foreach(i, idxs, !range(i));
+
+  // CHECK: list<list<int>> rr = {{\[}}[0, 1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [2, 3, 4], [3], [], [], [], []];
+  list<list<int>> rr = !foreach(i, idxs, !range(i, !sub(7, i)));
+
+  // CHECK: list<int> i100 = [100, 101, 102, 103, 104, 105, 106, 107];
+  list<int> i100 = !foreach(i, !range(rr), !add(100, i));
+}