[tablegen] Add !listconcat operator with the similar semantics as !strconcat

[dsanders]

Summary

It concatenates two or more lists. In addition to the !strconcat semantics
the lists must have the same element type.

My overall aim is to make it easy to append to Instruction.Predicates
rather than override it. This can be done by concatenating lists passed as
arguments, or by concatenating lists passed in additional fields.

[dsanders]

Unfortunately it's not possible to do something like:
let Predicates = !listconcat(Predicates, [Foo])
this is a general problem with let statements. Tablegen expands all references after overwriting the value so it expands to:
let Predicates = !listconcat(!listconcat(?, Predicates), [Foo])
which isn't very useful. I had follow-on patches that evaluated self-references before overwriting the old value (to give an overall bottom-up left-to-right evaluation order) but I've since found there are a number of nasty corner cases (mostly involving multiclasses) which seem unsolvable.

The code style I'm now aiming for is a compromise that works around this issue:
class PredicateControl {

		list<Predicate> ISAPredicates = [];
		list<Predicate> EncodingPredicates = [];
		list<Predicate> AdditionalPredicates = [];
		list<Predicate> Predicates = !listconcat(ISAPredicates, EncodingPredicates, AdditionalPredicates);

}

class InstSE<...> { let EncodingPredicates = [StandardEncoding]; }
class InstMicromips<...> { let EncodingPredicates = [MicromipsEncoding]; }

let AdditionalPredicates = [SomePredicate] in {

		def ADD<...> : InstSE<...> { let ISAPredicates = [Mips32]; }
		def DADD<...> : InstSE<...> { let ISAPredicates = [Mips64]; }
		def ADD_Micromips<...> : InstMicromips<...> { let ISAPredicates = [Mips32]; }

}

Each field corresponds to the mutually exclusive groups of predicates. Variable references are evaluated after all the let statements so the defs in this example expand to:
def ADD {

		list<Predicate> ISAPredicates = [Mips32];
		list<Predicate> EncodingPredicates = [StandardEncoding];
		list<Predicate> AdditionalPredicates = [SomePredicate];
		list<Predicate> Predicates = [Mips32, StandardEncoding, SomePredicate];

}
def DADD {

		list<Predicate> ISAPredicates = [Mips64];
		list<Predicate> EncodingPredicates = [StandardEncoding];
		list<Predicate> AdditionalPredicates = [SomePredicate];
		list<Predicate> Predicates = [Mips64, StandardEncoding, SomePredicate];

}
def ADD_Micromips {

		list<Predicate> ISAPredicates = [Mips32];
		list<Predicate> EncodingPredicates = [MicromipsEncoding];
		list<Predicate> AdditionalPredicates = [SomePredicate];
		list<Predicate> Predicates = [Mips32, MicromipsEncoding, SomePredicate];

}

-----Original Message-----
From: Owen Anderson [mailto:[e-mail]]
Sent: 25 April 2014 17:30
To: [e-mail]
Cc: Daniel Sanders; [e-mail]
Subject: Re: [PATCH] [tablegen] Add !listconcat operator with the similar
semantics as !strconcat

What are the evaluation order semantics of this? If I have several levels of
class/multiclass hierarchy, each doing a concatenation, what order do they
happen in?

-Owen

[dsanders]

ping...

[dsanders]

• !listconcat(a, b) -> !listconcat(a, b, ...) following a suggestion in the review of D3485 (!strconcat)

[dsanders]

I'm sorry to ping this patch again so soon but it's a bottleneck for a patch-series that adds assembler-only implementations of MIPS-I, MIPS-II, MIPS-III, and MIPS-V which has become quite important. It has become important because the it is itself a bottleneck for the minimal, functionally correct MIPS64r6 compiler we are urgently working on (we currently aim to get minimal MIPS64r6 support upstream by the end of the month). I could potentially re-work the dependent patch-series to override Instruction.Predicates instead of sublists that are concatenated to form the full predicates list but this is rather bug prone (while implementing MIPS-I to MIPS-V I found several cases of accidentally removing HasStdEnc with a 'let Predicates = ...' statement) and will require a significant amount of time.

Could someone review this patch which adds a !listconcat operator?

[hfinkel]

LGTM. Thanks!

docs/TableGen/LangIntro.rst

170

While you're here, can you also add a comment about what strconcat does with multiple arguments (a separate commit is fine).

[dsanders]

Thanks!

docs/TableGen/LangIntro.rst

170

Already done in r207865.

docs/TableGen/LangIntro.rst

 ``foreach <var> = {0-15,32-47} in ...``
     Loop over ranges of integers. The braces are required for multiple ranges.
 
 ``(DEF a, b)``
     a dag value.  The first element is required to be a record definition, the
     remaining elements in the list may be arbitrary other values, including
     nested ```dag``' values.
 
+``!listconcat(a, b, ...)``
+    A list value that is the result of concatenating the 'a' and 'b' lists.
+    The lists must have the same element type.
+    More than two arguments are accepted with the result being the concatenation
+    of all the lists given.
+
 ``!strconcat(a, b)``
     A string value that is the result of concatenating the 'a' and 'b' strings.
 
 ``str1#str2``
     "#" (paste) is a shorthand for !strconcat.  It may concatenate things that
     are not quoted strings, in which case an implicit !cast<string> is done on
     the operand of the paste.
 
 ``!cast<type>(a)``
     A symbol of type *type* obtained by looking up the string 'a' in the symbol

docs/TableGen/LangRef.rst

 
 TableGen also has "bang operators" which have a
 wide variety of meanings:
 
 .. productionlist::
    BangOperator: one of
                :!eq     !if      !head    !tail      !con
                :!add    !shl     !sra     !srl
-               :!cast   !empty   !subst   !foreach   !strconcat
+               :!cast   !empty   !subst   !foreach   !listconcat   !strconcat
 
 Syntax
 ======
 
 TableGen has an ``include`` mechanism. It does not play a role in the
 syntax per se, since it is lexically replaced with the contents of the
 included file.
 

include/llvm/TableGen/Record.h

public:
 
   std::string getAsString() const override;
 };
 
 /// BinOpInit - !op (X, Y) - Combine two inits.
 ///
 class BinOpInit : public OpInit {
 public:
-  enum BinaryOp { ADD, SHL, SRA, SRL, STRCONCAT, CONCAT, EQ };
+  enum BinaryOp { ADD, SHL, SRA, SRL, LISTCONCAT, STRCONCAT, CONCAT, EQ };
+
 private:
   BinaryOp Opc;
   Init *LHS, *RHS;
 
   BinOpInit(BinaryOp opc, Init *lhs, Init *rhs, RecTy *Type) :
       OpInit(IK_BinOpInit, Type), Opc(opc), LHS(lhs), RHS(rhs) {}
 
   BinOpInit(const BinOpInit &Other) LLVM_DELETED_FUNCTION;

lib/TableGen/Record.cpp

if (LHSs && RHSs) {
       for (unsigned i = 0, e = RHSs->getNumArgs(); i != e; ++i) {
         Args.push_back(RHSs->getArg(i));
         ArgNames.push_back(RHSs->getArgName(i));
       }
       return DagInit::get(LHSs->getOperator(), "", Args, ArgNames);
     }
     break;
   }
+  case LISTCONCAT: {
+    ListInit *LHSs = dyn_cast<ListInit>(LHS);
+    ListInit *RHSs = dyn_cast<ListInit>(RHS);
+    if (LHSs && RHSs) {
+      std::vector<Init *> Args;
+      Args.insert(Args.end(), LHSs->begin(), LHSs->end());
+      Args.insert(Args.end(), RHSs->begin(), RHSs->end());
+      return ListInit::get(
+          Args, static_cast<ListRecTy *>(LHSs->getType())->getElementType());
+    }
+    break;
+  }
   case STRCONCAT: {
     StringInit *LHSs = dyn_cast<StringInit>(LHS);
     StringInit *RHSs = dyn_cast<StringInit>(RHS);
     if (LHSs && RHSs)
       return StringInit::get(LHSs->getValue() + RHSs->getValue());
     break;
   }
   case EQ: {
std::string BinOpInit::getAsString() const {
   std::string Result;
   switch (Opc) {
   case CONCAT: Result = "!con"; break;
   case ADD: Result = "!add"; break;
   case SHL: Result = "!shl"; break;
   case SRA: Result = "!sra"; break;
   case SRL: Result = "!srl"; break;
   case EQ: Result = "!eq"; break;
+  case LISTCONCAT: Result = "!listconcat"; break;
   case STRCONCAT: Result = "!strconcat"; break;
   }
   return Result + "(" + LHS->getAsString() + ", " + RHS->getAsString() + ")";
 }
 
 TernOpInit *TernOpInit::get(TernaryOp opc, Init *lhs,
                                   Init *mhs, Init *rhs,
                                   RecTy *Type) {

lib/TableGen/TGLexer.h

enum TokKind {
     equal, question,    // = ?
     paste,              // #
 
     // Keywords.
     Bit, Bits, Class, Code, Dag, Def, Foreach, Defm, Field, In, Int, Let, List,
     MultiClass, String,
     
     // !keywords.
-    XConcat, XADD, XSRA, XSRL, XSHL, XStrConcat, XCast, XSubst,
+    XConcat, XADD, XSRA, XSRL, XSHL, XListConcat, XStrConcat, XCast, XSubst,
     XForEach, XHead, XTail, XEmpty, XIf, XEq,
 
     // Integer value.
     IntVal,
     
     // String valued tokens.
     Id, StrVal, VarName, CodeFragment
   };

lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("add", tgtok::XADD)
     .Case("shl", tgtok::XSHL)
     .Case("sra", tgtok::XSRA)
     .Case("srl", tgtok::XSRL)
     .Case("cast", tgtok::XCast)
     .Case("empty", tgtok::XEmpty)
     .Case("subst", tgtok::XSubst)
     .Case("foreach", tgtok::XForEach)
+    .Case("listconcat", tgtok::XListConcat)
     .Case("strconcat", tgtok::XStrConcat)
     .Default(tgtok::Error);
 
   return Kind != tgtok::Error ? Kind : ReturnError(Start-1, "Unknown operator");
 }
 

lib/TableGen/TGParser.cpp

Init *TGParser::ParseOperation(Record *CurRec) {
   }
 
   case tgtok::XConcat:
   case tgtok::XADD:
   case tgtok::XSRA:
   case tgtok::XSRL:
   case tgtok::XSHL:
   case tgtok::XEq:
+  case tgtok::XListConcat:
   case tgtok::XStrConcat: {  // Value ::= !binop '(' Value ',' Value ')'
     tgtok::TokKind OpTok = Lex.getCode();
     SMLoc OpLoc = Lex.getLoc();
     Lex.Lex();  // eat the operation
 
     BinOpInit::BinaryOp Code;
     RecTy *Type = nullptr;
 
     switch (OpTok) {
     default: llvm_unreachable("Unhandled code!");
     case tgtok::XConcat: Code = BinOpInit::CONCAT;Type = DagRecTy::get(); break;
     case tgtok::XADD:    Code = BinOpInit::ADD;   Type = IntRecTy::get(); break;
     case tgtok::XSRA:    Code = BinOpInit::SRA;   Type = IntRecTy::get(); break;
     case tgtok::XSRL:    Code = BinOpInit::SRL;   Type = IntRecTy::get(); break;
     case tgtok::XSHL:    Code = BinOpInit::SHL;   Type = IntRecTy::get(); break;
     case tgtok::XEq:     Code = BinOpInit::EQ;    Type = BitRecTy::get(); break;
+    case tgtok::XListConcat:
+      Code = BinOpInit::LISTCONCAT;
+      // We don't know the list type until we parse the first argument
+      break;
     case tgtok::XStrConcat:
       Code = BinOpInit::STRCONCAT;
       Type = StringRecTy::get();
       break;
     }
 
     if (Lex.getCode() != tgtok::l_paren) {
       TokError("expected '(' after binary operator");
case tgtok::XStrConcat: {  // Value ::= !binop '(' Value ',' Value ')'
     }
 
     if (Lex.getCode() != tgtok::r_paren) {
       TokError("expected ')' in operator");
       return nullptr;
     }
     Lex.Lex();  // eat the ')'
 
+    // If we are doing !listconcat, we should know the type by now
+    if (OpTok == tgtok::XListConcat) {
+      if (VarInit *Arg0 = dyn_cast<VarInit>(InitList[0]))
+        Type = Arg0->getType();
+      else if (ListInit *Arg0 = dyn_cast<ListInit>(InitList[0]))
+        Type = Arg0->getType();
+      else {
+        InitList[0]->dump();
+        Error(OpLoc, "expected a list");
+        return nullptr;
+      }
+    }
+
     // We allow multiple operands to associative operators like !strconcat as
     // shorthand for nesting them.
-    if (Code == BinOpInit::STRCONCAT) {
+    if (Code == BinOpInit::STRCONCAT || Code == BinOpInit::LISTCONCAT) {
       while (InitList.size() > 2) {
         Init *RHS = InitList.pop_back_val();
         RHS = (BinOpInit::get(Code, InitList.back(), RHS, Type))
                            ->Fold(CurRec, CurMultiClass);
         InitList.back() = RHS;
       }
     }
 

 ///   SimpleValue ::= ID '<' ValueListNE '>'
 ///   SimpleValue ::= '[' ValueList ']'
 ///   SimpleValue ::= '(' IDValue DagArgList ')'
 ///   SimpleValue ::= CONCATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= ADDTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SHLTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SRATOK '(' Value ',' Value ')'
 ///   SimpleValue ::= SRLTOK '(' Value ',' Value ')'
+///   SimpleValue ::= LISTCONCATTOK '(' Value ',' Value ')'
 ///   SimpleValue ::= STRCONCATTOK '(' Value ',' Value ')'
 ///
 Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
                                  IDParseMode Mode) {
   Init *R = nullptr;
   switch (Lex.getCode()) {
   default: TokError("Unknown token when parsing a value"); break;
   case tgtok::paste:
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XEmpty:
   case tgtok::XCast:  // Value ::= !unop '(' Value ')'
   case tgtok::XConcat:
   case tgtok::XADD:
   case tgtok::XSRA:
   case tgtok::XSRL:
   case tgtok::XSHL:
   case tgtok::XEq:
+  case tgtok::XListConcat:
   case tgtok::XStrConcat:   // Value ::= !binop '(' Value ',' Value ')'
   case tgtok::XIf:
   case tgtok::XForEach:
   case tgtok::XSubst: {  // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     return ParseOperation(CurRec);
   }
   }
 

test/TableGen/listconcat.td

+// RUN: llvm-tblgen %s | FileCheck %s
+
+// CHECK: class Y<list<string> Y:S = ?> {
+// CHECK:   list<string> T1 = !listconcat(Y:S, ["foo"]);
+// CHECK:   list<string> T2 = !listconcat(Y:S, !listconcat(["foo"], !listconcat(Y:S, ["bar", "baz"])));
+// CHECK: }
+
+// CHECK: def Z {
+// CHECK:   list<string> T1 = ["fu", "foo"];
+// CHECK:   list<string> T2 = ["fu", "foo", "fu", "bar", "baz"];
+// CHECK: }
+
+class Y<list<string> S> {
+  list<string> T1 = !listconcat(S, ["foo"]);
+  list<string> T2 = !listconcat(S, ["foo"], S, ["bar", "baz"]);
+}
+
+def Z : Y<["fu"]>;