TableGen: Delay instantiating inline anonymous records

[nhaehnle]

Summary

Only instantiate anonymous records once all variable references in template
arguments have been resolved. This allows patterns like the new test case,
which in practice can appear in expressions like:

class IntrinsicTypeProfile<list<LLVMType> ty, int shift> {
  list<LLVMType> types =
    !listconcat(ty, [llvm_any_ty, LLVMMatchType<shift>]);
}

class FooIntrinsic<IntrinsicTypeProfile P, ...>
  : Intrinsic<..., P.types, ...>;

Without this change, the anonymous LLVMMatchType instantiation would
never get resolved.

Another consequence of this change is that anonymous inline
instantiations are uniqued via the folding set of the newly introduced
VarDefInit.

Change-Id: I7a7041a20e297cf98c9109b28d85e64e176c932a

[tra]

Yay! Another of my favorite complaints about tablegen will be gone! Thank you!
Looks good overall, except for that concern about static pool and using tablegen as a library.

include/llvm/TableGen/Record.h

1065

Nit. I'd move it down to args_begin/args_end so it's easy to see the details of const_iterator next to the functions that return it. It's fine either way.

lib/TableGen/Record.cpp

1369

Same concern as I've raised in D43680 regarding use of the pool values across multiple invocations of tablegen's main function.

lib/TableGen/TGParser.cpp

1360–1363

TArgs could use a better name. Something along the lines of ExpectedArgNum. Calling it TArgs makes the error message somewhat confusing. My first thought was "Hold on a sec. We've just checked that template args (TArgs) is *less* than the number of [expected] arguments (Args)... Oh! TArgs is not the template args, it is the expected args".

1370

Nit. Class->getValue(TArgs[i]) could be extracted into a variable at the beginning of the for above.

[nhaehnle]

Address style issues.

include/llvm/TableGen/Record.h

1065

Makes sense. I believe I was just following some existing pattern elsewhere in the code.

lib/TableGen/Record.cpp

1369

Hmm. I'm less inclined to change this here, since all the other *Init classes work the same way already. I don't see anything that makes VarDefInit qualitatively different from e.g. OpInit.

lib/TableGen/TGParser.cpp

1360–1363

Good point.

1370

Done.

[tra]

lib/TableGen/Record.cpp

1369

OK.

One of these days we'll need to clean these static pools up on exit from TableGenMain.

include/llvm/TableGen/Record.h

enum InitKind : uint8_t {
     IK_BinOpInit,
     IK_TernOpInit,
     IK_UnOpInit,
     IK_LastOpInit,
     IK_StringInit,
     IK_VarInit,
     IK_VarListElementInit,
     IK_VarBitInit,
+    IK_VarDefInit,
     IK_LastTypedInit,
     IK_UnsetInit
   };
 
 private:
   const InitKind Kind;
 
 protected:
public:
   bool isConcrete() const override { return true; }
   std::string getAsString() const override;
 
   Init *getBit(unsigned Bit) const override {
     llvm_unreachable("Illegal bit reference off def");
   }
 };
 
+/// classname<targs...> - Represent an uninstantiated anonymous class
+/// instantiation.
+class VarDefInit final : public TypedInit, public FoldingSetNode,
+                         public TrailingObjects<VarDefInit, Init *> {
+  Record *Class;
+  DefInit *Def = nullptr; // after instantiation
+  unsigned NumArgs;
+
+  explicit VarDefInit(Record *Class, unsigned N)
+    : TypedInit(IK_VarDefInit, RecordRecTy::get(Class)), Class(Class), NumArgs(N) {}
+
+  DefInit *instantiate();
+
+public:
+  VarDefInit(const VarDefInit &) = delete;
+  VarDefInit &operator=(const VarDefInit &) = delete;
+
+  // Do not use sized deallocation due to trailing objects.
+  void operator delete(void *p) { ::operator delete(p); }
+
+  static bool classof(const Init *I) {
+    return I->getKind() == IK_VarDefInit;
+  }
+  static VarDefInit *get(Record *Class, ArrayRef<Init *> Args);
+
+  void Profile(FoldingSetNodeID &ID) const;
+
+  Init *resolveReferences(Resolver &R) const override;
+  Init *Fold() const;
+
+  std::string getAsString() const override;
+
+  Init *getArg(unsigned i) const {
+    assert(i < NumArgs && "Argument index out of range!");
+    return getTrailingObjects<Init *>()[i];
+  }
+
+  using const_iterator = Init *const *;
+
+  const_iterator args_begin() const { return getTrailingObjects<Init *>(); }
+  const_iterator args_end  () const { return args_begin() + NumArgs; }
+
+  size_t         args_size () const { return NumArgs; }
+  bool           args_empty() const { return NumArgs == 0; }
+
+  ArrayRef<Init *> args() const { return makeArrayRef(args_begin(), NumArgs); }
+
+  Init *getBit(unsigned Bit) const override {
+    llvm_unreachable("Illegal bit reference off anonymous def");
+  }
+};
+
 /// X.Y - Represent a reference to a subfield of a variable
 class FieldInit : public TypedInit {
   Init *Rec;                // Record we are referring to
   StringInit *FieldName;    // Field we are accessing
 
   FieldInit(Init *R, StringInit *FN)
       : TypedInit(IK_FieldInit, R->getFieldType(FN)), Rec(R), FieldName(FN) {
     assert(getType() && "FieldInit with non-record type!");
public:
 
   Init *resolve(Init *VarName) override {
     if (Shadowed.count(VarName))
       return nullptr;
     return R.resolve(VarName);
   }
 };
 
+/// (Optionally) delegate resolving to a sub-resolver, and keep track whether
+/// there were unresolved references.
+class TrackUnresolvedResolver final : public Resolver {
+  Resolver *R;
+  bool FoundUnresolved = false;
+
+public:
+  explicit TrackUnresolvedResolver(Resolver *R = nullptr)
+      : Resolver(R ? R->getCurrentRecord() : nullptr), R(R) {}
+
+  bool foundUnresolved() const { return FoundUnresolved; }
+
+  Init *resolve(Init *VarName) override;
+};
+
 } // end namespace llvm
 
 #endif // LLVM_TABLEGEN_RECORD_H

lib/TableGen/Record.cpp

if (const RecordVal *RV = Def->getValue(FieldName))
     return RV->getType();
   return nullptr;
 }
 
 std::string DefInit::getAsString() const {
   return Def->getName();
 }
 
+static void ProfileVarDefInit(FoldingSetNodeID &ID,
+                              Record *Class,
+                              ArrayRef<Init *> Args) {
+  ID.AddInteger(Args.size());
+  ID.AddPointer(Class);
+
+  for (Init *I : Args)
+    ID.AddPointer(I);
+}
+
+VarDefInit *VarDefInit::get(Record *Class, ArrayRef<Init *> Args) {
+  static FoldingSet<VarDefInit> ThePool;
+
+  FoldingSetNodeID ID;
+  ProfileVarDefInit(ID, Class, Args);
+
+  void *IP = nullptr;
+  if (VarDefInit *I = ThePool.FindNodeOrInsertPos(ID, IP))
+    return I;
+
+  void *Mem = Allocator.Allocate(totalSizeToAlloc<Init *>(Args.size()),
+                                 alignof(VarDefInit));
+  VarDefInit *I = new(Mem) VarDefInit(Class, Args.size());
+  std::uninitialized_copy(Args.begin(), Args.end(),
+                          I->getTrailingObjects<Init *>());
+  ThePool.InsertNode(I, IP);
+  return I;
+}
+
+void VarDefInit::Profile(FoldingSetNodeID &ID) const {
+  ProfileVarDefInit(ID, Class, args());
+}
+
+DefInit *VarDefInit::instantiate() {
+  if (!Def) {
+    RecordKeeper &Records = Class->getRecords();
+    auto NewRecOwner = make_unique<Record>(Records.getNewAnonymousName(),
+                                           Class->getLoc(), Records,
+                                           /*IsAnonymous=*/true);
+    Record *NewRec = NewRecOwner.get();
+
+    // Copy values from class to instance
+    for (const RecordVal &Val : Class->getValues()) {
+      if (Val.getName() != "NAME")
+        NewRec->addValue(Val);
+    }
+
+    // Substitute and resolve template arguments
+    ArrayRef<Init *> TArgs = Class->getTemplateArgs();
+    MapResolver R(NewRec);
+
+    for (unsigned i = 0, e = TArgs.size(); i != e; ++i) {
+      if (i < args_size())
+        R.set(TArgs[i], getArg(i));
+      else
+        R.set(TArgs[i], NewRec->getValue(TArgs[i])->getValue());
+
+      NewRec->removeValue(TArgs[i]);
+    }
+
+    NewRec->resolveReferences(R);
+
+    // Add superclasses.
+    ArrayRef<std::pair<Record *, SMRange>> SCs = Class->getSuperClasses();
+    for (const auto &SCPair : SCs)
+      NewRec->addSuperClass(SCPair.first, SCPair.second);
+
+    NewRec->addSuperClass(Class,
+                          SMRange(Class->getLoc().back(),
+                                  Class->getLoc().back()));
+
+    // Resolve internal references and store in record keeper
+    NewRec->resolveReferences();
+    Records.addDef(std::move(NewRecOwner));
+
+    Def = DefInit::get(NewRec);
+  }
+
+  return Def;
+}
+
+Init *VarDefInit::resolveReferences(Resolver &R) const {
+  TrackUnresolvedResolver UR(&R);
+  bool Changed = false;
+  SmallVector<Init *, 8> NewArgs;
+  NewArgs.reserve(args_size());
+
+  for (Init *Arg : args()) {
+    Init *NewArg = Arg->resolveReferences(UR);
+    NewArgs.push_back(NewArg);
+    Changed |= NewArg != Arg;
+  }
+
+  if (Changed) {
+    auto New = VarDefInit::get(Class, NewArgs);
+    if (!UR.foundUnresolved())
+      return New->instantiate();
+    return New;
+  }
+  return const_cast<VarDefInit *>(this);
+}
+
+Init *VarDefInit::Fold() const {
+  if (Def)
+    return Def;
+
+  TrackUnresolvedResolver R;
+  for (Init *Arg : args())
+    Arg->resolveReferences(R);
+
+  if (!R.foundUnresolved())
+    return const_cast<VarDefInit *>(this)->instantiate();
+  return const_cast<VarDefInit *>(this);
+}
+
+std::string VarDefInit::getAsString() const {
+  std::string Result = Class->getNameInitAsString() + "<";
+  const char *sep = "";
+  for (Init *Arg : args()) {
+    Result += sep;
+    sep = ", ";
+    Result += Arg->getAsString();
+  }
+  return Result + ">";
+}
+
 FieldInit *FieldInit::get(Init *R, StringInit *FN) {
   using Key = std::pair<Init *, StringInit *>;
   static DenseMap<Key, FieldInit*> ThePool;
 
   Key TheKey(std::make_pair(R, FN));
 
   FieldInit *&I = ThePool[TheKey];
   if (!I) I = new(Allocator) FieldInit(R, FN);
if (!isa<UnsetInit>(RV->getValue())) {
       Val = Val->resolveReferences(*this);
       Stack.pop_back();
     }
   }
 
   Cache[VarName] = Val;
   return Val;
 }
+
+Init *TrackUnresolvedResolver::resolve(Init *VarName) {
+  Init *I = nullptr;
+
+  if (R) {
+    I = R->resolve(VarName);
+    if (I && !FoundUnresolved) {
+      // Do not recurse into the resolved initializer, as that would change
+      // the behavior of the resolver we're delegating, but do check to see
+      // if there are unresolved variables remaining.
+      TrackUnresolvedResolver Sub;
+      I->resolveReferences(Sub);
+      FoundUnresolved |= Sub.FoundUnresolved;
+    }
+  }
+
+  if (!I)
+    FoundUnresolved = true;
+  return I;
+}

lib/TableGen/TGParser.cpp

case tgtok::Id: {
     // a new anonymous definition, deriving from CLASS<initvalslist> with no
     // body.
     Record *Class = Records.getClass(Name->getValue());
     if (!Class) {
       Error(NameLoc, "Expected a class name, got '" + Name->getValue() + "'");
       return nullptr;
     }
 
-    SubClassReference SCRef;
-    ParseValueList(SCRef.TemplateArgs, CurRec, Class);
-    if (SCRef.TemplateArgs.empty()) return nullptr;
+    SmallVector<Init *, 8> Args;
+    ParseValueList(Args, CurRec, Class);
+    if (Args.empty()) return nullptr;
 
     if (Lex.getCode() != tgtok::greater) {
       TokError("expected '>' at end of value list");
       return nullptr;
     }
     Lex.Lex();  // eat the '>'
-    SMLoc EndLoc = Lex.getLoc();
 
-    // Create the new record, set it as CurRec temporarily.
-    auto NewRecOwner =
-        make_unique<Record>(Records.getNewAnonymousName(), NameLoc, Records,
-                            /*IsAnonymous=*/true);
-    Record *NewRec = NewRecOwner.get(); // Keep a copy since we may release.
-    SCRef.RefRange = SMRange(NameLoc, EndLoc);
-    SCRef.Rec = Class;
-    // Add info about the subclass to NewRec.
-    if (AddSubClass(NewRec, SCRef))
+    // Typecheck the template arguments list
+    ArrayRef<Init *> ExpectedArgs = Class->getTemplateArgs();
+    if (ExpectedArgs.size() < Args.size()) {
+      Error(NameLoc,
+            "More template args specified than expected");
       return nullptr;
-
-    if (!CurMultiClass) {
-      NewRec->resolveReferences();
-      Records.addDef(std::move(NewRecOwner));
-    } else {
-      // This needs to get resolved once the multiclass template arguments are
-      // known before any use.
-      NewRec->setResolveFirst(true);
-      // Otherwise, we're inside a multiclass, add it to the multiclass.
-      CurMultiClass->DefPrototypes.push_back(std::move(NewRecOwner));
-
-      // 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?");
-        NewRec->addValue(*RV);
-      }
 
-      // We can't return the prototype def here, instead return:
-      // !cast<ItemType>(!strconcat(NAME, AnonName)).
-      const RecordVal *MCNameRV = CurMultiClass->Rec.getValue("NAME");
-      assert(MCNameRV && "multiclass record must have a NAME");
+    for (unsigned i = 0, e = ExpectedArgs.size(); i != e; ++i) {
+      RecordVal *ExpectedArg = Class->getValue(ExpectedArgs[i]);
+      if (i < Args.size()) {
+        if (TypedInit *TI = dyn_cast<TypedInit>(Args[i])) {
+          RecTy *ExpectedType = ExpectedArg->getType();
+          if (!TI->getType()->typeIsConvertibleTo(ExpectedType)) {
+            Error(NameLoc,
+                  "Value specified for template argument #" + Twine(i) + " (" +
+                  ExpectedArg->getNameInitAsString() + ") is of type '" +
+                  TI->getType()->getAsString() + "', expected '" +
+                  ExpectedType->getAsString() + "': " + TI->getAsString());
+            return nullptr;
+          }
+          continue;
+        }
+      } else if (ExpectedArg->getValue()->isComplete())
+        continue;
 
-      return UnOpInit::get(UnOpInit::CAST,
-                           BinOpInit::get(BinOpInit::STRCONCAT,
-                                          VarInit::get(MCNameRV->getName(),
-                                                       MCNameRV->getType()),
-                                          NewRec->getNameInit(),
-                                          StringRecTy::get()),
-                           NewRec->getDefInit()->getType());
+      Error(NameLoc,
+            "Value not specified for template argument #" + Twine(i) + " (" +
+            ExpectedArgs[i]->getAsUnquotedString() + ")");
+      return nullptr;
     }
 
-    // The result of the expression is a reference to the new record.
-    return DefInit::get(NewRec);
+    return VarDefInit::get(Class, Args)->Fold();
   }
   case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
     SMLoc BraceLoc = Lex.getLoc();
     Lex.Lex(); // eat the '{'
     SmallVector<Init*, 16> Vals;
 
     if (Lex.getCode() != tgtok::r_brace) {
       ParseValueList(Vals, CurRec);

test/TableGen/AnonDefinitionOnDemand.td

-// RUN: llvm-tblgen < %s
+// RUN: llvm-tblgen %s | FileCheck %s
 // XFAIL: vg_leak
 
+// CHECK: --- Defs ---
+
+// CHECK: def X {
+// CHECK:   foo Y = anonymous_0;
+// CHECK: }
+
+// CHECK: def ZD {
+// CHECK:   foo Z = anonymous_1;
+// CHECK: }
+
+// CHECK: def anonymous_0 {
+// CHECK:   int THEVAL = 1;
+// CHECK: }
+
+// CHECK: def anonymous_1 {
+// CHECK:   int THEVAL = 42;
+// CHECK: }
+
 class foo<int X> { int THEVAL = X; }
 def foo_imp : foo<1>;
 
 def x {
   foo Y = foo_imp;    // This works.
 }
 
 def X {
   foo Y = foo<1>;     // This should work too, synthesizing a new foo<1>.
 }
+
+class Z<int X> {
+  foo Z = foo<X>;
+}
+
+def ZD : Z<42>;