TableGen: Add a defset statement

[nhaehnle]

Summary

Allows capturing a list of concrete instantiated defs.

This can be combined with foreach to create parallel sets of def
instantiations with less repetition in the source. This purpose is
largely also served by multiclasses, but in some cases multiclasses
can't be used.

The motivating example for this change is having a large set of
intrinsics, which are generated from the IntrinsicsBackend.td file
included by Intrinsics.td, and a corresponding set of instruction
selection patterns, which are generated via the backend's .td files.

Multiclasses cannot be used to eliminate the redundancy in this case,
because a multiclass cannot span both LLVM's common .td files and
the backend .td files at the same time.

Change-Id: I879e35042dceea542a5e6776fad23c5e0e69e76b

[tra]

docs/TableGen/LangRef.rst

360–368

Does it mean that instantiating any record that is not of type A will be an error? That sounds rather limiting.
That would prevent use of anonymous records or non-anonymous records or different types we may want to instantiate within the same multiclass hierarchy without having to duplicate all of it.

Could we change the semantics to the list collects all instantiated records of type A and, maybe, allow more than one pair of type:list , so we can collect multiple record types?

Another approach would be to say -- give me all records of type A, created by this defm instance. I.e. instead of defset A foo = { records } you do something like defm FOO : M<...>; list<A> foo = !defset(FOO).

[nhaehnle]

Clarify the docs

docs/TableGen/LangRef.rst

360–368

Anonymous (or rather "inline"?) records are not an issue: they are created on a different path and never added to a defset, and I think they shouldn't be. I've clarified that.

I did make incompatible (non-anonymous) record types an error because one could accidentally make the type of list<A> too strict and then end up with records silently not being collected in surprising ways.

I see your point about allowing different types explicitly, but I'm not entirely convinced yet. In part the whole point of defset is that it helps avoid reducing duplication by using the resulting list in a foreach later. I'm also a bit hesitant about proliferation of defset, and I'd personally err on the side of starting with stricter semantics. It's always easier to go to looser semantics later if good use cases for it show up than the other way around.

[tra]

docs/TableGen/LangRef.rst

360–368

Fair enough. I don't have any specific use case for multiple types of records inside defset and if anonymous records are allowed, this leaves some flexibility for what could be done inside the defset.

I'm OK with this variant. It should indeed be reasonably easy to extend if/when we have specific use cases.

docs/TableGen/LangRef.rst

 
 .. productionlist::
    IncludeDirective: "include" `TokString`
 
 TableGen's top-level production consists of "objects".
 
 .. productionlist::
    TableGenFile: `Object`*
-   Object: `Class` | `Def` | `Defm` | `Let` | `MultiClass` | `Foreach`
+   Object: `Class` | `Def` | `Defm` | `Defset` | `Let` | `MultiClass` |
+           `Foreach`
 
 ``class``\es
 ------------
 
 .. productionlist::
    Class: "class" `TokIdentifier` [`TemplateArgList`] `ObjectBody`
 
 A ``class`` declaration creates a record which other records can inherit

 --------
 
 .. productionlist::
    Defm: "defm" `TokIdentifier` ":" `BaseClassListNE` ";"
 
 Note that in the :token:`BaseClassList`, all of the ``multiclass``'s must
 precede any ``class``'s that appear.
 
+``defset``
+----------
+.. productionlist::
+   Defset: "defset" `Type` `TokIdentifier` "=" "{" `Object`* "}"
+
+All records defined inside the braces via ``def`` and ``defm`` are collected
+in a globally accessible list of the given name (in addition to being added
+to the global collection of records as usual). Anonymous records created inside
+initializier expressions using the ``Class<args...>`` syntax are never collected
+in a defset.
+
+The given type must be ``list<A>``, where ``A`` is some class. It is an error
+to define a record (via ``def`` or ``defm``) inside the braces which doesn't
+derive from ``A``.
+
 ``foreach``
 -----------
 
 .. productionlist::
    Foreach: "foreach" `ForeachDeclaration` "in" "{" `Object`* "}"
           :| "foreach" `ForeachDeclaration` "in" `Object`
    ForeachDeclaration: ID "=" ( "{" `RangeList` "}" | `RangePiece` | `Value` )
 

include/llvm/TableGen/Record.h

MultiClass(StringRef Name, SMLoc Loc, RecordKeeper &Records) :
     Rec(Name, Loc, Records) {}
 };
 
 class RecordKeeper {
   friend class RecordRecTy;
   using RecordMap = std::map<std::string, std::unique_ptr<Record>>;
   RecordMap Classes, Defs;
   FoldingSet<RecordRecTy> RecordTypePool;
+  std::map<std::string, Init *> ExtraGlobals;
   unsigned AnonCounter = 0;
 
 public:
   const RecordMap &getClasses() const { return Classes; }
   const RecordMap &getDefs() const { return Defs; }
 
   Record *getClass(StringRef Name) const {
     auto I = Classes.find(Name);
     return I == Classes.end() ? nullptr : I->second.get();
   }
 
   Record *getDef(StringRef Name) const {
     auto I = Defs.find(Name);
     return I == Defs.end() ? nullptr : I->second.get();
   }
 
+  Init *getGlobal(StringRef Name) const {
+    if (Record *R = getDef(Name))
+      return R->getDefInit();
+    auto It = ExtraGlobals.find(Name);
+    return It == ExtraGlobals.end() ? nullptr : It->second;
+  }
+
   void addClass(std::unique_ptr<Record> R) {
     bool Ins = Classes.insert(std::make_pair(R->getName(),
                                              std::move(R))).second;
     (void)Ins;
     assert(Ins && "Class already exists");
   }
 
   void addDef(std::unique_ptr<Record> R) {
     bool Ins = Defs.insert(std::make_pair(R->getName(),
                                           std::move(R))).second;
     (void)Ins;
     assert(Ins && "Record already exists");
   }
 
+  void addExtraGlobal(StringRef Name, Init *I) {
+    bool Ins = ExtraGlobals.insert(std::make_pair(Name, I)).second;
+    (void)Ins;
+    assert(!getDef(Name));
+    assert(Ins && "Global already exists");
+  }
+
   Init *getNewAnonymousName();
 
   //===--------------------------------------------------------------------===//
   // High-level helper methods, useful for tablegen backends...
 
   /// This method returns all concrete definitions
   /// that derive from the specified class name.  A class with the specified
   /// name must exist.

lib/TableGen/TGLexer.h

enum TokKind {
     less, greater,      // < >
     colon, semi,        // : ;
     comma, period,      // , .
     equal, question,    // = ?
     paste,              // #
 
     // Keywords.
     Bit, Bits, Class, Code, Dag, Def, Foreach, Defm, Field, In, Int, Let, List,
-    MultiClass, String,
+    MultiClass, String, Defset,
 
     // !keywords.
     XConcat, XADD, XAND, XOR, XSRA, XSRL, XSHL, XListConcat, XStrConcat, XCast,
     XSubst, XForEach, XFoldl, XHead, XTail, XSize, XEmpty, XIf, XEq, XIsA,
 
     // Integer value.
     IntVal,
 

lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind = StringSwitch<tgtok::TokKind>(Str)
     .Case("string", tgtok::String)
     .Case("list", tgtok::List)
     .Case("code", tgtok::Code)
     .Case("dag", tgtok::Dag)
     .Case("class", tgtok::Class)
     .Case("def", tgtok::Def)
     .Case("foreach", tgtok::Foreach)
     .Case("defm", tgtok::Defm)
+    .Case("defset", tgtok::Defset)
     .Case("multiclass", tgtok::MultiClass)
     .Case("field", tgtok::Field)
     .Case("let", tgtok::Let)
     .Case("in", tgtok::In)
     .Default(tgtok::Id);
 
   if (Kind == tgtok::Id)
     CurStrVal.assign(Str.begin(), Str.end());

lib/TableGen/TGParser.h

namespace llvm {
   struct ForeachLoop {
     VarInit *IterVar;
     ListInit *ListValue;
 
     ForeachLoop(VarInit *IVar, ListInit *LValue)
       : IterVar(IVar), ListValue(LValue) {}
   };
 
+  struct DefsetRecord {
+    SMLoc Loc;
+    RecTy *EltTy;
+    SmallVector<Init *, 16> Elements;
+  };
+
 class TGParser {
   TGLexer Lex;
   std::vector<SmallVector<LetRecord, 4>> LetStack;
   std::map<std::string, std::unique_ptr<MultiClass>> MultiClasses;
 
   /// Loops - Keep track of any foreach loops we are within.
   ///
   typedef std::vector<ForeachLoop> LoopVector;
   LoopVector Loops;
 
+  SmallVector<DefsetRecord *, 2> Defsets;
+
   /// CurMultiClass - If we are parsing a 'multiclass' definition, this is the
   /// current value.
   MultiClass *CurMultiClass;
 
   // Record tracker
   RecordKeeper &Records;
 
   // A "named boolean" indicating how to parse identifiers.  Usually
private:  // Semantic analysis methods.
 
   // IterSet: The set of all iterator values at some point in the
   // iteration space.
   typedef std::vector<IterRecord> IterSet;
 
   bool ProcessForeachDefs(Record *CurRec, SMLoc Loc);
   bool ProcessForeachDefs(Record *CurRec, SMLoc Loc, IterSet &IterVals);
 
+  bool addToDefsets(Record &R);
+
 private:  // Parser methods.
   bool ParseObjectList(MultiClass *MC = nullptr);
   bool ParseObject(MultiClass *MC);
   bool ParseClass();
   bool ParseMultiClass();
   Record *InstantiateMulticlassDef(MultiClass &MC, Record *DefProto,
                                    Init *&DefmPrefix, SMRange DefmPrefixRange,
                                    ArrayRef<Init *> TArgs,
                                    ArrayRef<Init *> TemplateVals);
   bool ResolveMulticlassDefArgs(MultiClass &MC, Record *DefProto,
                                 SMLoc DefmPrefixLoc, SMLoc SubClassLoc,
                                 ArrayRef<Init *> TArgs,
                                 ArrayRef<Init *> TemplateVals, bool DeleteArgs);
   bool ResolveMulticlassDef(MultiClass &MC,
                             Record *CurRec,
                             Record *DefProto,
                             SMLoc DefmPrefixLoc);
   bool ParseDefm(MultiClass *CurMultiClass);
   bool ParseDef(MultiClass *CurMultiClass);
+  bool ParseDefset();
   bool ParseForeach(MultiClass *CurMultiClass);
   bool ParseTopLevelLet(MultiClass *CurMultiClass);
   void ParseLetList(SmallVectorImpl<LetRecord> &Result);
 
   bool ParseObjectBody(Record *CurRec);
   bool ParseBody(Record *CurRec);
   bool ParseBodyItem(Record *CurRec);
 

lib/TableGen/TGParser.cpp

if (Records.getDef(IterRec->getNameInitAsString())) {
 
     IterRec->setName(Records.getNewAnonymousName());
   }
 
   Record *IterRecSave = IterRec.get(); // Keep a copy before release.
   Records.addDef(std::move(IterRec));
   IterRecSave->resolveReferences();
   checkConcrete(*IterRecSave);
+  if (addToDefsets(*IterRecSave))
+    return true;
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // Parser Code
 //===----------------------------------------------------------------------===//
 
 /// isObjectStart - Return true if this is a valid first token for an Object.
 static bool isObjectStart(tgtok::TokKind K) {
-  return K == tgtok::Class || K == tgtok::Def ||
-         K == tgtok::Defm || K == tgtok::Let ||
-         K == tgtok::MultiClass || K == tgtok::Foreach;
+  return K == tgtok::Class || K == tgtok::Def || K == tgtok::Defm ||
+         K == tgtok::Let || K == tgtok::MultiClass || K == tgtok::Foreach ||
+         K == tgtok::Defset;
 }
 
 /// ParseObjectName - If an object name is specified, return it.  Otherwise,
 /// return 0.
 ///   ObjectName ::= Value [ '#' Value ]*
 ///   ObjectName ::= /*empty*/
 ///
 Init *TGParser::ParseObjectName(MultiClass *CurMultiClass) {
RecTy *TGParser::ParseType() {
   default: TokError("Unknown token when expecting a type"); return nullptr;
   case tgtok::String: Lex.Lex(); return StringRecTy::get();
   case tgtok::Code:   Lex.Lex(); return CodeRecTy::get();
   case tgtok::Bit:    Lex.Lex(); return BitRecTy::get();
   case tgtok::Int:    Lex.Lex(); return IntRecTy::get();
   case tgtok::Dag:    Lex.Lex(); return DagRecTy::get();
   case tgtok::Id:
     if (Record *R = ParseClassID()) return RecordRecTy::get(R);
+    TokError("unknown class name");
     return nullptr;
   case tgtok::Bits: {
     if (Lex.Lex() != tgtok::less) { // Eat 'bits'
       TokError("expected '<' after bits type");
       return nullptr;
     }
     if (Lex.Lex() != tgtok::IntVal) {  // Eat '<'
       TokError("expected integer in bits<n> type");
for (const auto &L : Loops) {
     VarInit *IterVar = dyn_cast<VarInit>(L.IterVar);
     if (IterVar && IterVar->getNameInit() == Name)
       return IterVar;
   }
 
   if (Mode == ParseNameMode)
     return Name;
 
-  if (Record *D = Records.getDef(Name->getValue()))
-    return DefInit::get(D);
+  if (Init *I = Records.getGlobal(Name->getValue()))
+    return I;
 
   if (Mode == ParseValueMode) {
     Error(NameLoc, "Variable not defined: '" + Name->getValue() + "'");
     return nullptr;
   }
 
   return Name;
 }
if (!CurMultiClass && Loops.empty()) {
     return true;
   }
 
   if (!CurMultiClass) { // Def's in multiclasses aren't really defs.
     // See Record::setName().  This resolve step will see any new name
     // for the def that might have been created when resolving
     // inheritance, values and arguments above.
     CurRec->resolveReferences();
-    if (Loops.empty())
+    if (Loops.empty()) {
       checkConcrete(*CurRec);
+      if (addToDefsets(*CurRec))
+        return true;
+    }
   }
 
   // If ObjectBody has template arguments, it's an error.
   assert(CurRec->getTemplateArgs().empty() && "How'd this get template args?");
 
   if (CurMultiClass) {
     // Copy the template arguments for the multiclass into the def.
     for (Init *TArg : CurMultiClass->Rec.getTemplateArgs()) {
       const RecordVal *RV = CurMultiClass->Rec.getValue(TArg);
       assert(RV && "Template arg doesn't exist?");
       CurRec->addValue(*RV);
     }
   }
 
   if (ProcessForeachDefs(CurRec, DefLoc))
     return Error(DefLoc, "Could not process loops for def" +
                  CurRec->getNameInitAsString());
 
   return false;
 }
 
+bool TGParser::addToDefsets(Record &R) {
+  for (DefsetRecord *Defset : Defsets) {
+    DefInit *I = R.getDefInit();
+    if (!I->getType()->typeIsA(Defset->EltTy)) {
+      PrintError(R.getLoc(),
+                 Twine("adding record of incompatible type '") +
+                 I->getType()->getAsString() + "' to defset");
+      PrintNote(Defset->Loc, "to this defset");
+      return true;
+    }
+    Defset->Elements.push_back(I);
+  }
+  return false;
+}
+
+/// ParseDefset - Parse a defset statement.
+///
+///   Defset ::= DEFSET Type Id '=' '{' ObjectList '}'
+///
+bool TGParser::ParseDefset() {
+  assert(Lex.getCode() == tgtok::Defset);
+  Lex.Lex(); // Eat the 'defset' token
+
+  DefsetRecord Defset;
+  Defset.Loc = Lex.getLoc();
+  RecTy *Type = ParseType();
+  if (!Type)
+    return true;
+  if (!isa<ListRecTy>(Type))
+    return Error(Defset.Loc, "expected list type");
+  Defset.EltTy = cast<ListRecTy>(Type)->getElementType();
+
+  if (Lex.getCode() != tgtok::Id)
+    return TokError("expected identifier");
+  StringInit *DeclName = StringInit::get(Lex.getCurStrVal());
+  if (Records.getGlobal(DeclName->getValue()))
+    return TokError("def or global variable of this name already exists");
+
+  if (Lex.Lex() != tgtok::equal) // Eat the identifier
+    return TokError("expected '='");
+  if (Lex.Lex() != tgtok::l_brace) // Eat the '='
+    return TokError("expected '{'");
+  SMLoc BraceLoc = Lex.getLoc();
+  Lex.Lex(); // Eat the '{'
+
+  Defsets.push_back(&Defset);
+  bool Err = ParseObjectList(nullptr);
+  Defsets.pop_back();
+  if (Err)
+    return true;
+
+  if (Lex.getCode() != tgtok::r_brace) {
+    TokError("expected '}' at end of defset");
+    return Error(BraceLoc, "to match this '{'");
+  }
+  Lex.Lex();  // Eat the '}'
+
+  Records.addExtraGlobal(DeclName->getValue(),
+                         ListInit::get(Defset.Elements, Defset.EltTy));
+  return false;
+}
+
 /// ParseForeach - Parse a for statement.  Return the record corresponding
 /// to it.  This returns true on error.
 ///
 ///   Foreach ::= FOREACH Declaration IN '{ ObjectList '}'
 ///   Foreach ::= FOREACH Declaration IN Object
 ///
 bool TGParser::ParseForeach(MultiClass *CurMultiClass) {
   assert(Lex.getCode() == tgtok::Foreach && "Unknown tok");
if (Lex.getCode() != tgtok::l_brace) {
     Lex.Lex();  // eat the ';'.
   } else {
     if (Lex.Lex() == tgtok::r_brace)  // eat the '{'.
       return TokError("multiclass must contain at least one def");
 
     while (Lex.getCode() != tgtok::r_brace) {
       switch (Lex.getCode()) {
       default:
-        return TokError("expected 'let', 'def' or 'defm' in multiclass body");
+        return TokError("expected 'let', 'def', 'defm' or 'foreach' in "
+                        "multiclass body");
       case tgtok::Let:
       case tgtok::Def:
       case tgtok::Defm:
       case tgtok::Foreach:
         if (ParseObject(CurMultiClass))
           return true;
         break;
       }
bool TGParser::ParseDefm(MultiClass *CurMultiClass) {
 
   if (!CurMultiClass) {
     for (Record *CurRec : NewRecDefs) {
       // See Record::setName().  This resolve step will see any new
       // name for the def that might have been created when resolving
       // inheritance, values and arguments above.
       CurRec->resolveReferences();
       checkConcrete(*CurRec);
+      if (addToDefsets(*CurRec))
+        return true;
     }
   }
 
   if (Lex.getCode() != tgtok::semi)
     return TokError("expected ';' at end of defm");
   Lex.Lex();
 
   return false;
 }
 
 /// ParseObject
 ///   Object ::= ClassInst
 ///   Object ::= DefInst
 ///   Object ::= MultiClassInst
 ///   Object ::= DefMInst
 ///   Object ::= LETCommand '{' ObjectList '}'
 ///   Object ::= LETCommand Object
 bool TGParser::ParseObject(MultiClass *MC) {
   switch (Lex.getCode()) {
   default:
-    return TokError("Expected class, def, defm, multiclass or let definition");
+    return TokError("Expected class, def, defm, defset, multiclass, let or "
+                    "foreach");
   case tgtok::Let:   return ParseTopLevelLet(MC);
   case tgtok::Def:   return ParseDef(MC);
   case tgtok::Foreach:   return ParseForeach(MC);
   case tgtok::Defm:  return ParseDefm(MC);
+  case tgtok::Defset:
+    if (MC)
+      return TokError("defset is not allowed inside multiclass");
+    return ParseDefset();
   case tgtok::Class: return ParseClass();
   case tgtok::MultiClass: return ParseMultiClass();
   }
 }
 
 /// ParseObjectList
 ///   ObjectList :== Object*
 bool TGParser::ParseObjectList(MultiClass *MC) {

test/TableGen/defset-typeerror.td

+// RUN: not llvm-tblgen %s 2>&1 | FileCheck %s
+// XFAIL: vg_leak
+
+// CHECK: error: adding record of incompatible type 'A' to defset
+
+class A<int a> {
+  int Num = a;
+}
+
+class B<int a> : A<a>;
+
+defset list<B> Bs = {
+  def A0 : A<1>;
+}

test/TableGen/defset.td

+// RUN: llvm-tblgen %s | FileCheck %s
+// XFAIL: vg_leak
+
+// CHECK: --- Defs ---
+
+// CHECK: def Sum {
+// CHECK:   int x = 712;
+// CHECK: }
+
+// CHECK: def yyy_A0
+// CHECK: def yyy_A1
+// CHECK: def yyy_A2
+// CHECK: def yyy_B0A0
+// CHECK: def yyy_B0A1
+// CHECK: def yyy_C0B0A0
+// CHECK: def yyy_C0B0A1
+// CHECK: def yyy_C0B1A0
+// CHECK: def yyy_C0B1A1
+// CHECK-NOT: def zzz_A0
+// CHECK: def zzz_B0A0
+// CHECK: def zzz_B0A1
+// CHECK: def zzz_C0B0A0
+// CHECK: def zzz_C0B0A1
+// CHECK: def zzz_C0B1A0
+// CHECK: def zzz_C0B1A1
+
+class A<int a> {
+  int Num = a;
+}
+
+multiclass B<int b> {
+  def A0 : A<!add(10, b)>;
+  def A1 : A<!add(20, b)>;
+}
+
+multiclass C<int c> {
+  defm B0 : B<!add(100, c)>;
+  defm B1 : B<!add(200, c)>;
+}
+
+defset list<A> As = {
+  def A0 : A<1>;
+  foreach i = 1-2 in {
+    def A#i : A<!add(i, 1)>;
+  }
+  defset list<A> SubAs = {
+    defm B0 : B<2>;
+    defm C0 : C<3>;
+  }
+}
+
+def Sum {
+  int x = !foldl(0, As, a, b, !add(a, b.Num));
+}
+
+foreach a = As in {
+  def yyy_ # !cast<string>(a);
+}
+
+foreach a = SubAs in {
+  def zzz_ # !cast<string>(a);
+}