[TableGen] Add new operator !exists

[• pcwang-thead]

Summary

We can cast a string to a record via !cast, but we have no mechanism
to check if it is valid and TableGen will raise an error if failed to
cast. Besides, we have no semantic null in TableGen (we have ? but
different backends handle uninitialized value differently), so operator
like dyn_cast<> is hard to implement.

In this patch, we add a new operator !exists<T>(s) to check whether
a record with type T and name s exists. Self-references are allowed
just like !cast.

By doing these, we can write code like:

class dyn_cast_to_record<string name> {
  R value = !if(!exists<R>(name), !cast<R>(name), default_value);
}
defvar v = dyn_cast_to_record<"R0">.value; // R0 or default_value.

[• pcwang-thead]

Fix test errors.

[nhaehnle]

I think this change makes sense and it looks good to me, except for one thing: if I were to see an !instanceof without context, I would expect that it is also able to take a record/def as operand. That kind of use is likely to come up eventually, and people shouldn't have to artificial convert the record/def to its name first. So I'm in favor of this change, except I'd ask you to change the implementation (and tests) to support both kinds of use.

[nhaehnle]

Hmm, I now saw the earlier discussion and @tra's very good points in it. If !instanceof accepts defs, then it becomes somewhat redundant with !isa, which I hadn't considered. Can you improve the error checking so that if a record is provided as an argument, the message advises that !isa should be used instead?

FWIW, I'm not 100% happy about the name "instanceof", but I can't think of anything better right now that isn't super verbose. And I don't want to bikeshed this change to death either :)

[• pcwang-thead]

• Guide users to use !isa when argument is a record.
• Make position of error reporting correct.

[nhaehnle]

Thank you. One more thought after sleeping on it: What do you think about !exists? I think !exists<T>("foo") reads nicely as "does there exist a record of type T with name 'foo'?". It's not perfect, but I like that there's less confusion with "instanceof" or "isinstance" operators that some programming languages have.

[tra]

In D127948#3600082, @nhaehnle wrote:

Thank you. One more thought after sleeping on it: What do you think about !exists? I think !exists<T>("foo") reads nicely as "does there exist a record of type T with name 'foo'?". It's not perfect, but I like that there's less confusion with "instanceof" or "isinstance" operators that some programming languages have.

I like it. !instanceof sounded like something that assumes that its input is an object, while we're actually giving it an object's name.
!exists seems to be a better match.

[tra]

llvm/test/TableGen/instanceof.td

4–10 ↗

(On Diff #438363)

This test is rather hard to read as checks are placed all over the place, usually away from where the respective records are defined.
Alas, we don't have CHECK-DAG-NEXT we could use to do sequential matches in out of order chunks.

I guess the best we could do here is to have the tablegen source at the top of the file, and all the checks below, in order they are emitted by the tablegen, possibly with the comments referring to the relevant source code, if it's not obvious what exactly, and why, particular check statement tests for.
E.g. right now it's not obvious why the value of B1 is 0 and B0 is 1. See the other suggestion which may make the checks self-explanatory.

19–20 ↗

(On Diff #438363)

These could use more descriptive names, possibly reflecting expected result.
E.g.

def A0 : A;

class A_check<string name>{
  int exists = !instanceof<A>(name);
}

def A0_exists : A_check<"A0">;
def A1_missing : A_check<"A1">;

[• pcwang-thead]

• Change operator name to !exists.
• Make tests more self-explanatory.

[nhaehnle]

Awesome, LGTM

llvm/lib/TableGen/TGParser.cpp

2407

Why did you move the comment?

[tra]

Very nice. LGTM.

[• pcwang-thead]

Do not touch comment in ParseSimpleValue.

[• pcwang-thead]

llvm/lib/TableGen/TGParser.cpp

2407

Hmm, that's because I tried to extend UnOpInit before and found it not suitable, but I forgot to move the case. Fixed.

llvm/docs/TableGen/ProgRef.rst

``!interleave(``\ *list*\ ``,`` *delim*\ ``)``
     *delim* string between each pair, and produces the resulting string.
     The list can be a list of string, int, bits, or bit. An empty list
     results in an empty string. The delimiter can be the empty string.
 
 ``!isa<``\ *type*\ ``>(``\ *a*\ ``)``
     This operator produces 1 if the type of *a* is a subtype of the given *type*; 0
     otherwise.
 
+``!exists<``\ *type*\ ``>(``\ *name*\ ``)``
+    This operator produces 1 if a record of the given *type* whose name is *name*
+    exists; 0 otherwise. *name* should be of type *string*.
+
 ``!le(``\ *a*\ ``,`` *b*\ ``)``
     This operator produces 1 if *a* is less than or equal to *b*; 0 otherwise.
     The arguments must be ``bit``, ``bits``, ``int``, or ``string`` values.
 
 ``!listconcat(``\ *list1*\ ``,`` *list2*\ ``, ...)``
     This operator concatenates the list arguments *list1*, *list2*, etc., and
     produces the resulting list. The lists must have the same element type.
 

llvm/include/llvm/TableGen/Record.h

enum InitKind : uint8_t {
     IK_FirstOpInit,
     IK_BinOpInit,
     IK_TernOpInit,
     IK_UnOpInit,
     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
public:
 
   Init *resolveReferences(Resolver &R) const override;
 
   Init *getBit(unsigned Bit) const override;
 
   std::string getAsString() const override;
 };
 
+/// !exists<type>(expr) - Dynamically determine if a record of `type` named
+/// `expr` exists.
+class ExistsOpInit : public TypedInit, public FoldingSetNode {
+private:
+  RecTy *CheckType;
+  Init *Expr;
+
+  ExistsOpInit(RecTy *CheckType, Init *Expr)
+      : TypedInit(IK_ExistsOpInit, IntRecTy::get(CheckType->getRecordKeeper())),
+        CheckType(CheckType), Expr(Expr) {}
+
+public:
+  ExistsOpInit(const ExistsOpInit &) = delete;
+  ExistsOpInit &operator=(const ExistsOpInit &) = delete;
+
+  static bool classof(const Init *I) { return I->getKind() == IK_ExistsOpInit; }
+
+  static ExistsOpInit *get(RecTy *CheckType, Init *Expr);
+
+  void Profile(FoldingSetNodeID &ID) const;
+
+  // Fold - If possible, fold this to a simpler init.  Return this if not
+  // possible to fold.
+  Init *Fold(Record *CurRec, bool IsFinal = false) const;
+
+  bool isComplete() const override { return false; }
+
+  Init *resolveReferences(Resolver &R) const override;
+
+  Init *getBit(unsigned Bit) const override;
+
+  std::string getAsString() const override;
+};
+
 /// 'Opcode' - Represent a reference to an entire variable object.
 class VarInit : public TypedInit {
   Init *VarName;
 
   explicit VarInit(Init *VN, RecTy *T)
       : TypedInit(IK_VarInit, T), VarName(VN) {}
 
 public:

llvm/lib/TableGen/Record.cpp

struct RecordKeeperImpl {
   StringMap<StringInit *, BumpPtrAllocator &> StringInitStringPool;
   StringMap<StringInit *, BumpPtrAllocator &> StringInitCodePool;
   FoldingSet<ListInit> TheListInitPool;
   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;

 }
 
 std::string IsAOpInit::getAsString() const {
   return (Twine("!isa<") + CheckType->getAsString() + ">(" +
           Expr->getAsString() + ")")
       .str();
 }
 
+static void ProfileExistsOpInit(FoldingSetNodeID &ID, RecTy *CheckType,
+                                Init *Expr) {
+  ID.AddPointer(CheckType);
+  ID.AddPointer(Expr);
+}
+
+ExistsOpInit *ExistsOpInit::get(RecTy *CheckType, Init *Expr) {
+  FoldingSetNodeID ID;
+  ProfileExistsOpInit(ID, CheckType, Expr);
+
+  detail::RecordKeeperImpl &RK = Expr->getRecordKeeper().getImpl();
+  void *IP = nullptr;
+  if (ExistsOpInit *I = RK.TheExistsOpInitPool.FindNodeOrInsertPos(ID, IP))
+    return I;
+
+  ExistsOpInit *I = new (RK.Allocator) ExistsOpInit(CheckType, Expr);
+  RK.TheExistsOpInitPool.InsertNode(I, IP);
+  return I;
+}
+
+void ExistsOpInit::Profile(FoldingSetNodeID &ID) const {
+  ProfileExistsOpInit(ID, CheckType, Expr);
+}
+
+Init *ExistsOpInit::Fold(Record *CurRec, bool IsFinal) const {
+  if (StringInit *Name = dyn_cast<StringInit>(Expr)) {
+    if (!CurRec && !IsFinal)
+      return const_cast<ExistsOpInit *>(this);
+
+    // Self-references are allowed, but their resolution is delayed until
+    // the final resolve to ensure that we get the correct type for them.
+    auto *Anonymous = dyn_cast<AnonymousNameInit>(CurRec->getNameInit());
+    if (Name == CurRec->getNameInit() ||
+        (Anonymous && Name == Anonymous->getNameInit())) {
+      if (!IsFinal)
+        return const_cast<ExistsOpInit *>(this);
+
+      // No doubt that there exists a record, so we should check if types are
+      // compatiable.
+      return IntInit::get(getRecordKeeper(),
+                          CurRec->getType()->typeIsA(CheckType));
+    }
+
+    // Look up all defined records to see if we can find one.
+    Record *D = CheckType->getRecordKeeper().getDef(Name->getValue());
+    if (!D) {
+      if (IsFinal)
+        return IntInit::get(getRecordKeeper(), 0);
+      return const_cast<ExistsOpInit *>(this);
+    }
+
+    // Check if types are compatiable.
+    return IntInit::get(getRecordKeeper(),
+                        DefInit::get(D)->getType()->typeIsA(CheckType));
+  }
+  return const_cast<ExistsOpInit *>(this);
+}
+
+Init *ExistsOpInit::resolveReferences(Resolver &R) const {
+  Init *NewExpr = Expr->resolveReferences(R);
+  if (Expr != NewExpr || R.isFinal())
+    return get(CheckType, NewExpr)->Fold(R.getCurrentRecord(), R.isFinal());
+  return const_cast<ExistsOpInit *>(this);
+}
+
+Init *ExistsOpInit::getBit(unsigned Bit) const {
+  return VarBitInit::get(const_cast<ExistsOpInit *>(this), Bit);
+}
+
+std::string ExistsOpInit::getAsString() const {
+  return (Twine("!exists<") + CheckType->getAsString() + ">(" +
+          Expr->getAsString() + ")")
+      .str();
+}
+
 RecTy *TypedInit::getFieldType(StringInit *FieldName) const {
   if (RecordRecTy *RecordType = dyn_cast<RecordRecTy>(getType())) {
     for (Record *Rec : RecordType->getClasses()) {
       if (RecordVal *Field = Rec->getValue(FieldName))
         return Field->getType();
     }
   }
   return nullptr;

llvm/lib/TableGen/TGLexer.h

enum TokKind {
     FalseKW, Field, Foreach, If, In, Include, Int, Let, List, MultiClass,
     String, Then, TrueKW,
 
     // Bang operators.
     XConcat, XADD, XSUB, XMUL, XNOT, 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,
 
     // Boolean literals.
     TrueVal, FalseVal,
 
     // Integer value.
     IntVal,
 
     // Binary constant.  Note that these are sized according to the number of

llvm/lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("listconcat", tgtok::XListConcat)
     .Case("listsplat", tgtok::XListSplat)
     .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)
     .Default(tgtok::Error);
 
   return Kind != tgtok::Error ? Kind : ReturnError(Start-1, "Unknown operator");
 }
 
 bool TGLexer::prepExitInclude(bool IncludeStackMustBeEmpty) {
   // Report an error, if preprocessor control stack for the current
   // file is not empty.

llvm/lib/TableGen/TGParser.cpp

case tgtok::XIsA: {
     if (!consume(tgtok::r_paren)) {
       TokError("expected ')' in !isa");
       return nullptr;
     }
 
     return (IsAOpInit::get(Type, LHS))->Fold();
   }
 
+  case tgtok::XExists: {
+    // Value ::= !exists '<' Type '>' '(' Value ')'
+    Lex.Lex(); // eat the operation
+
+    RecTy *Type = ParseOperatorType();
+    if (!Type)
+      return nullptr;
+
+    if (!consume(tgtok::l_paren)) {
+      TokError("expected '(' after type of !exists");
+      return nullptr;
+    }
+
+    SMLoc ExprLoc = Lex.getLoc();
+    Init *Expr = ParseValue(CurRec);
+    if (!Expr)
+      return nullptr;
+
+    TypedInit *ExprType = dyn_cast<TypedInit>(Expr);
+    if (!ExprType) {
+      Error(ExprLoc, "expected string type argument in !exists operator");
+      return nullptr;
+    }
+
+    RecordRecTy *RecType = dyn_cast<RecordRecTy>(ExprType->getType());
+    if (RecType) {
+      Error(ExprLoc,
+            "expected string type argument in !exists operator, please "
+            "use !isa instead");
+      return nullptr;
+    }
+
+    StringRecTy *SType = dyn_cast<StringRecTy>(ExprType->getType());
+    if (!SType) {
+      Error(ExprLoc, "expected string type argument in !exists operator");
+      return nullptr;
+    }
+
+    if (!consume(tgtok::r_paren)) {
+      TokError("expected ')' in !exists");
+      return nullptr;
+    }
+
+    return (ExistsOpInit::get(Type, Expr))->Fold(CurRec);
+  }
+
   case tgtok::XConcat:
   case tgtok::XADD:
   case tgtok::XSUB:
   case tgtok::XMUL:
   case tgtok::XAND:
   case tgtok::XOR:
   case tgtok::XXOR:
   case tgtok::XSRA:
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   }
 
   case tgtok::XHead:
   case tgtok::XTail:
   case tgtok::XSize:
   case tgtok::XEmpty:
   case tgtok::XCast:
   case tgtok::XGetDagOp: // Value ::= !unop '(' Value ')'
+  case tgtok::XExists:
   case tgtok::XIsA:
   case tgtok::XConcat:
   case tgtok::XDag:
   case tgtok::XADD:
   case tgtok::XSUB:
   case tgtok::XMUL:
   case tgtok::XNOT:
   case tgtok::XAND:

llvm/test/TableGen/exists-error-non-string.td

+// RUN: not llvm-tblgen --no-warn-on-unused-template-args %s 2>&1 | FileCheck %s
+// XFAIL: vg_leak
+
+//CHECK: expected string type argument in !exists operator
+
+class A;
+
+defvar value = !exists<A>(123);

llvm/test/TableGen/exists-error-record.td

+// RUN: not llvm-tblgen --no-warn-on-unused-template-args %s 2>&1 | FileCheck %s
+// XFAIL: vg_leak
+
+//CHECK: expected string type argument in !exists operator, please use !isa instead
+
+class A;
+def a : A;
+defvar value = !exists<A>(a);

llvm/test/TableGen/exists-error-uninitialized.td

+// RUN: not llvm-tblgen --no-warn-on-unused-template-args %s 2>&1 | FileCheck %s
+// XFAIL: vg_leak
+
+//CHECK: expected string type argument in !exists operator
+
+class A;
+
+defvar value = !exists<A>(?);

llvm/test/TableGen/exists.td

+// RUN: llvm-tblgen --no-warn-on-unused-template-args %s | FileCheck %s
+// XFAIL: vg_leak
+
+class A;
+def a0 : A;
+
+class A_check<string name>{
+  int exists = !exists<A>(name);
+}
+
+def a0_exists : A_check<"a0">;
+def a1_missing : A_check<"a1">;
+
+
+// Subclasses are allowed.
+
+class B;
+class SubOfB : B;
+class B_check<string name> {
+  int exists = !exists<B>(name);
+}
+
+def sub : SubOfB;
+
+def sub_exists : B_check<"sub">;
+def a0_is_not_sub_of_B : B_check<"a0">;
+
+
+// Self-references are allowed.
+
+class Self_check<string name> {
+  int exists = !exists<Self_check>(name);
+}
+
+def self_reference : Self_check<"self_reference">; // Self-reference
+// There is no record called `current` in current context though we will define it below.
+def current_missing : Self_check<"current">;
+def current : Self_check<"current">;
+
+// CHECK: def a0_exists {
+// CHECK:   int exists = 1;
+// CHECK: }
+
+// CHECK: def a0_is_not_sub_of_B {
+// CHECK:   int exists = 0;
+// CHECK: }
+
+// CHECK: def a1_missing {
+// CHECK:   int exists = 0;
+// CHECK: }
+
+// CHECK: def current {
+// CHECK:   int exists = 1;
+// CHECK: }
+
+// `current` doesn't exist because we define it below `current_missing`.
+// CHECK: def current_missing {
+// CHECK:   int exists = 0;
+// CHECK: }
+
+// CHECK: def self_reference {
+// CHECK:   int exists = 1;
+// CHECK: }
+
+// CHECK: def sub_exists {
+// CHECK:   int exists = 1;
+// CHECK: }