TableGen: Generalize record types to fix typeIsConvertibleTo et al.

[nhaehnle]

Summary

Allow RecordRecTy to represent the type "subtype of N superclasses",
where N may be zero. Furthermore, generate RecordRecTy instances only
with actual classes in the list.

Keeping track of multiple superclasses is required to resolve the type
of a list correctly in some cases. The old code relied on the incorrect
behavior of typeIsConvertibleTo, and an earlier version of this change
relied on a modified ordering of superclasses (it was committed in
r325884 and then reverted because unfortunately some of clang-tblgen's
backends depend on the ordering).

Previously, the DefInit for each Record would have a RecordRecTy of
that Record as its type. Now, all defs with the same superclasses will
share the same type.

This allows us to be more consistent with standard expectations about
type checks involving records:

• typeIsConvertibleTo actually requires the LHS to be a subtype of the RHS

• resolveTypes will return the least supertype of given record types in all cases

• different record types in the two branches of an !if are handled correctly

Add a test that used to be accepted without flagging the obvious type
error.

Change-Id: Ib366db1a4e6a079f1a0851e469b402cddae76714

[tra]

My brain is fried by now. I'll get back to this patch on Monday.

lib/TableGen/Record.cpp

191–195 ↗

(On Diff #135643)

return llvm::any_of(...) ?

206–210 ↗

(On Diff #135643)

return llvm::all_of(...) ?

[nhaehnle]

No worries :) I very much appreciate the time you're taking to go over these changes!

lib/TableGen/Record.cpp

191–195 ↗

(On Diff #135643)

Good idea, done. Also changed some variable names, hope that helps.

206–210 ↗

(On Diff #135643)

Done.

[nhaehnle]

Use any_of/all_of.

[tra]

lib/TableGen/Record.cpp

136 ↗

(On Diff #135828)

TableGen is a library. Having static cache of RecordRecTy will be a problem if the same library is used to process more than one independent tablegen input. Perhaps it should live somewhere in the RecordKeeper?

210 ↗

(On Diff #135828)

This could use a brief description of what this function does (or, perhaps a more descriptive name). It's hard to tell that resolveRecordTypes returns a record type built from common ancestors of both types.

228 ↗

(On Diff #135828)

This could use an explanation.

If I understand it correctly, we assume that getSuperClasses() returns the list of superclasses as a forest, flattened in preorder. When we drop 1 + SC->getSuperClasses().size() we remove SC and all its superclasses and we'll descend further when we eventually pop SC off the Stack. It's a neat arrangement, but this is rather fragile as it seems to depend on the details of the implementation. At least I don't see anywhere in the TableGen headers that getSuperClasses guarantees any particular order. At the very least there should be some comments explaining what's going on.

1410–1415 ↗

(On Diff #135828)

Perhaps it's worth extracting this into a getDirectSuperClasses() function? It would make resolveRecordTypes() easier to understand.

[nhaehnle]

Extract getDirectSuperClasses, move RecordRecTy pool to RecordKeeper.

[nhaehnle]

lib/TableGen/Record.cpp

136 ↗

(On Diff #135828)

I've moved the pool to the RecordKeeper. Keep in mind that the whole of the TableGen frontend leaks objects in those pools, but at least with this change we can no longer run into the situation where a RecordRecTy is re-used after the underlying Record(s) have been freed and then a new Record was allocated with the same pointer.

210 ↗

(On Diff #135828)

Added a comment.

1410–1415 ↗

(On Diff #135828)

Good idea, done.

[tra]

lib/TableGen/Record.cpp

1633–1641 ↗

(On Diff #136982)

This could still benefit from a few comments regarding expected layout of classes in the array. Function tells us *what* this function is expected top produce, but it's still relatively hard to tell why it does things the way it does.

[nhaehnle]

lib/TableGen/Record.cpp

1633–1641 ↗

(On Diff #136982)

I thought the comment on the SuperClasses member variable is enough, but I suppose it doesn't hurt, so I added another small comment.

llvm/trunk/include/llvm/TableGen/Record.h

static bool classof(const RecTy *RT) {
     return RT->getRecTyKind() == DagRecTyKind;
   }
 
   static DagRecTy *get() { return &Shared; }
 
   std::string getAsString() const override;
 };
 
-/// '[classname]' - Represent an instance of a class, such as:
-/// (R32 X = EAX).
-class RecordRecTy : public RecTy {
+/// '[classname]' - Type of record values that have zero or more superclasses.
+///
+/// The list of superclasses is non-redundant, i.e. only contains classes that
+/// are not the superclass of some other listed class.
+class RecordRecTy final : public RecTy, public FoldingSetNode,
+                          public TrailingObjects<RecordRecTy, Record *> {
   friend class Record;
 
-  Record *Rec;
+  unsigned NumClasses;
 
-  explicit RecordRecTy(Record *R) : RecTy(RecordRecTyKind), Rec(R) {}
+  explicit RecordRecTy(unsigned Num)
+      : RecTy(RecordRecTyKind), NumClasses(Num) {}
 
 public:
+  RecordRecTy(const RecordRecTy &) = delete;
+  RecordRecTy &operator=(const RecordRecTy &) = delete;
+
+  // Do not use sized deallocation due to trailing objects.
+  void operator delete(void *p) { ::operator delete(p); }
+
   static bool classof(const RecTy *RT) {
     return RT->getRecTyKind() == RecordRecTyKind;
   }
 
-  static RecordRecTy *get(Record *R);
+  /// Get the record type with the given non-redundant list of superclasses.
+  static RecordRecTy *get(ArrayRef<Record *> Classes);
+
+  void Profile(FoldingSetNodeID &ID) const;
+
+  ArrayRef<Record *> getClasses() const {
+    return makeArrayRef(getTrailingObjects<Record *>(), NumClasses);
+  }
+
+  using const_record_iterator = Record * const *;
 
-  Record *getRecord() const { return Rec; }
+  const_record_iterator classes_begin() const { return getClasses().begin(); }
+  const_record_iterator classes_end() const { return getClasses().end(); }
 
   std::string getAsString() const override;
 
+  bool isSubClassOf(Record *Class) const;
   bool typeIsConvertibleTo(const RecTy *RHS) const override;
 };
 
 /// Find a common type that T1 and T2 convert to.
 /// Return 0 if no such type exists.
 RecTy *resolveTypes(RecTy *T1, RecTy *T2);
 
 //===----------------------------------------------------------------------===//

 };
 
 /// AL - Represent a reference to a 'def' in the description
 class DefInit : public TypedInit {
   friend class Record;
 
   Record *Def;
 
-  DefInit(Record *D, RecordRecTy *T) : TypedInit(IK_DefInit, T), Def(D) {}
+  explicit DefInit(Record *D);
 
 public:
   DefInit(const DefInit &) = delete;
   DefInit &operator=(const DefInit &) = delete;
 
   static bool classof(const Init *I) {
     return I->getKind() == IK_DefInit;
   }
class Record {
   static unsigned LastID;
 
   Init *Name;
   // Location where record was instantiated, followed by the location of
   // multiclass prototypes used.
   SmallVector<SMLoc, 4> Locs;
   SmallVector<Init *, 0> TemplateArgs;
   SmallVector<RecordVal, 0> Values;
+
+  // All superclasses in the inheritance forest in reverse preorder (yes, it
+  // must be a forest; diamond-shaped inheritance is not allowed).
   SmallVector<std::pair<Record *, SMRange>, 0> SuperClasses;
 
   // Tracks Record instances. Not owned by Record.
   RecordKeeper &TrackedRecords;
 
   DefInit *TheInit = nullptr;
 
   // Unique record ID.
public:
   }
 
   ArrayRef<RecordVal> getValues() const { return Values; }
 
   ArrayRef<std::pair<Record *, SMRange>>  getSuperClasses() const {
     return SuperClasses;
   }
 
+  /// Append the direct super classes of this record to Classes.
+  void getDirectSuperClasses(SmallVectorImpl<Record *> &Classes) const;
+
   bool isTemplateArg(Init *Name) const {
     for (Init *TA : TemplateArgs)
       if (TA == Name) return true;
     return false;
   }
 
   const RecordVal *getValue(const Init *Name) const {
     for (const RecordVal &Val : Values)
struct MultiClass {
 
   void dump() const;
 
   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;
 
 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();

llvm/trunk/lib/TableGen/Record.cpp

if (const auto *ListTy = dyn_cast<ListRecTy>(RHS))
     return Ty->typeIsConvertibleTo(ListTy->getElementType());
   return false;
 }
 
 std::string DagRecTy::getAsString() const {
   return "dag";
 }
 
-RecordRecTy *RecordRecTy::get(Record *R) {
-  return dyn_cast<RecordRecTy>(R->getDefInit()->getType());
+static void ProfileRecordRecTy(FoldingSetNodeID &ID,
+                               ArrayRef<Record *> Classes) {
+  ID.AddInteger(Classes.size());
+  for (Record *R : Classes)
+    ID.AddPointer(R);
+}
+
+RecordRecTy *RecordRecTy::get(ArrayRef<Record *> UnsortedClasses) {
+  if (UnsortedClasses.empty()) {
+    static RecordRecTy AnyRecord(0);
+    return &AnyRecord;
+  }
+
+  FoldingSet<RecordRecTy> &ThePool =
+      UnsortedClasses[0]->getRecords().RecordTypePool;
+
+  SmallVector<Record *, 4> Classes(UnsortedClasses.begin(),
+                                   UnsortedClasses.end());
+  std::sort(Classes.begin(), Classes.end(),
+            [](Record *LHS, Record *RHS) {
+              return LHS->getNameInitAsString() < RHS->getNameInitAsString();
+            });
+
+  FoldingSetNodeID ID;
+  ProfileRecordRecTy(ID, Classes);
+
+  void *IP = nullptr;
+  if (RecordRecTy *Ty = ThePool.FindNodeOrInsertPos(ID, IP))
+    return Ty;
+
+#ifndef NDEBUG
+  // Check for redundancy.
+  for (unsigned i = 0; i < Classes.size(); ++i) {
+    for (unsigned j = 0; j < Classes.size(); ++j) {
+      assert(i == j || !Classes[i]->isSubClassOf(Classes[j]));
+    }
+    assert(&Classes[0]->getRecords() == &Classes[i]->getRecords());
+  }
+#endif
+
+  void *Mem = Allocator.Allocate(totalSizeToAlloc<Record *>(Classes.size()),
+                                 alignof(RecordRecTy));
+  RecordRecTy *Ty = new(Mem) RecordRecTy(Classes.size());
+  std::uninitialized_copy(Classes.begin(), Classes.end(),
+                          Ty->getTrailingObjects<Record *>());
+  ThePool.InsertNode(Ty, IP);
+  return Ty;
+}
+
+void RecordRecTy::Profile(FoldingSetNodeID &ID) const {
+  ProfileRecordRecTy(ID, getClasses());
 }
 
 std::string RecordRecTy::getAsString() const {
-  return Rec->getName();
+  if (NumClasses == 1)
+    return getClasses()[0]->getName();
+
+  std::string Str = "{";
+  bool First = true;
+  for (Record *R : getClasses()) {
+    if (!First)
+      Str += ", ";
+    First = false;
+    Str += R->getName();
+  }
+  Str += "}";
+  return Str;
+}
+
+bool RecordRecTy::isSubClassOf(Record *Class) const {
+  return llvm::any_of(getClasses(), [Class](Record *MySuperClass) {
+                                      return MySuperClass == Class ||
+                                             MySuperClass->isSubClassOf(Class);
+                                    });
 }
 
 bool RecordRecTy::typeIsConvertibleTo(const RecTy *RHS) const {
+  if (this == RHS)
+    return true;
+
   const RecordRecTy *RTy = dyn_cast<RecordRecTy>(RHS);
   if (!RTy)
     return false;
 
-  if (RTy->getRecord() == Rec || Rec->isSubClassOf(RTy->getRecord()))
-    return true;
+  return llvm::all_of(RTy->getClasses(), [this](Record *TargetClass) {
+                                           return isSubClassOf(TargetClass);
+                                         });
+}
 
-  for (const auto &SCPair : RTy->getRecord()->getSuperClasses())
-    if (Rec->isSubClassOf(SCPair.first))
-      return true;
+static RecordRecTy *resolveRecordTypes(RecordRecTy *T1, RecordRecTy *T2) {
+  SmallVector<Record *, 4> CommonSuperClasses;
+  SmallVector<Record *, 4> Stack;
 
-  return false;
+  Stack.insert(Stack.end(), T1->classes_begin(), T1->classes_end());
+
+  while (!Stack.empty()) {
+    Record *R = Stack.back();
+    Stack.pop_back();
+
+    if (T2->isSubClassOf(R)) {
+      CommonSuperClasses.push_back(R);
+    } else {
+      R->getDirectSuperClasses(Stack);
+    }
+  }
+
+  return RecordRecTy::get(CommonSuperClasses);
 }
 
 RecTy *llvm::resolveTypes(RecTy *T1, RecTy *T2) {
+  if (T1 == T2)
+    return T1;
+
+  if (RecordRecTy *RecTy1 = dyn_cast<RecordRecTy>(T1)) {
+    if (RecordRecTy *RecTy2 = dyn_cast<RecordRecTy>(T2))
+      return resolveRecordTypes(RecTy1, RecTy2);
+  }
+
   if (T1->typeIsConvertibleTo(T2))
     return T2;
   if (T2->typeIsConvertibleTo(T1))
     return T1;
 
-  // If one is a Record type, check superclasses
-  if (RecordRecTy *RecTy1 = dyn_cast<RecordRecTy>(T1)) {
-    // See if T2 inherits from a type T1 also inherits from
-    for (const auto &SuperPair1 : RecTy1->getRecord()->getSuperClasses()) {
-      RecordRecTy *SuperRecTy1 = RecordRecTy::get(SuperPair1.first);
-      RecTy *NewType1 = resolveTypes(SuperRecTy1, T2);
-      if (NewType1)
-        return NewType1;
-    }
-  }
-  if (RecordRecTy *RecTy2 = dyn_cast<RecordRecTy>(T2)) {
-    // See if T1 inherits from a type T2 also inherits from
-    for (const auto &SuperPair2 : RecTy2->getRecord()->getSuperClasses()) {
-      RecordRecTy *SuperRecTy2 = RecordRecTy::get(SuperPair2.first);
-      RecTy *NewType2 = resolveTypes(T1, SuperRecTy2);
-      if (NewType2)
-        return NewType2;
+  if (ListRecTy *ListTy1 = dyn_cast<ListRecTy>(T1)) {
+    if (ListRecTy *ListTy2 = dyn_cast<ListRecTy>(T2)) {
+      RecTy* NewType = resolveTypes(ListTy1->getElementType(),
+                                    ListTy2->getElementType());
+      if (NewType)
+        return NewType->getListTy();
     }
   }
+
   return nullptr;
 }
 
 //===----------------------------------------------------------------------===//
 //    Initializer implementations
 //===----------------------------------------------------------------------===//
 
 void Init::anchor() {}
std::string TernOpInit::getAsString() const {
   case FOREACH: Result = "!foreach"; break;
   case IF: Result = "!if"; break;
   }
   return Result + "(" + LHS->getAsString() + ", " + MHS->getAsString() + ", " +
          RHS->getAsString() + ")";
 }
 
 RecTy *TypedInit::getFieldType(StringInit *FieldName) const {
-  if (RecordRecTy *RecordType = dyn_cast<RecordRecTy>(getType()))
-    if (RecordVal *Field = RecordType->getRecord()->getValue(FieldName))
+  if (RecordRecTy *RecordType = dyn_cast<RecordRecTy>(getType())) {
+    for (Record *Rec : RecordType->getClasses()) {
+      if (RecordVal *Field = Rec->getValue(FieldName))
         return Field->getType();
+    }
+  }
   return nullptr;
 }
 
 Init *
 TypedInit::convertInitializerTo(RecTy *Ty) const {
   if (isa<IntRecTy>(Ty)) {
     if (getType()->typeIsConvertibleTo(Ty))
       return const_cast<TypedInit *>(this);
TypedInit::convertInitializerTo(RecTy *Ty) const {
 
   if (auto *DRT = dyn_cast<DagRecTy>(Ty)) {
     if (getType()->typeIsConvertibleTo(DRT))
       return const_cast<TypedInit *>(this);
     return nullptr;
   }
 
   if (auto *SRRT = dyn_cast<RecordRecTy>(Ty)) {
-    // Ensure that this is compatible with Rec.
-    if (RecordRecTy *DRRT = dyn_cast<RecordRecTy>(getType()))
-      if (DRRT->getRecord()->isSubClassOf(SRRT->getRecord()) ||
-          DRRT->getRecord() == SRRT->getRecord())
-        return const_cast<TypedInit *>(this);
+    if (getType()->typeIsConvertibleTo(SRRT))
     return nullptr;
   }
 
   return nullptr;
 }
 
 Init *TypedInit::convertInitializerBitRange(ArrayRef<unsigned> Bits) const {
   BitsRecTy *T = dyn_cast<BitsRecTy>(getType());

 }
 
 Init *VarListElementInit::getBit(unsigned Bit) const {
   if (getType() == BitRecTy::get())
     return const_cast<VarListElementInit*>(this);
   return VarBitInit::get(const_cast<VarListElementInit*>(this), Bit);
 }
 
+static RecordRecTy *makeDefInitType(Record *Rec) {
+  SmallVector<Record *, 4> SuperClasses;
+  Rec->getDirectSuperClasses(SuperClasses);
+  return RecordRecTy::get(SuperClasses);
+}
+
+DefInit::DefInit(Record *D)
+    : TypedInit(IK_DefInit, makeDefInitType(D)), Def(D) {}
+
 DefInit *DefInit::get(Record *R) {
   return R->getDefInit();
 }
 
 Init *DefInit::convertInitializerTo(RecTy *Ty) const {
   if (auto *RRT = dyn_cast<RecordRecTy>(Ty))
-    if (getDef()->isSubClassOf(RRT->getRecord()))
+    if (getType()->typeIsConvertibleTo(RRT))
       return const_cast<DefInit *>(this);
   return nullptr;
 }
 
 RecTy *DefInit::getFieldType(StringInit *FieldName) const {
   if (const RecordVal *RV = Def->getValue(FieldName))
     return RV->getType();
   return nullptr;
void Record::checkName() {
   // Ensure the record name has string type.
   const TypedInit *TypedName = cast<const TypedInit>(Name);
   if (!isa<StringRecTy>(TypedName->getType()))
     PrintFatalError(getLoc(), "Record name is not a string!");
 }
 
 DefInit *Record::getDefInit() {
   if (!TheInit)
-    TheInit = new(Allocator) DefInit(this, new(Allocator) RecordRecTy(this));
+    TheInit = new(Allocator) DefInit(this);
   return TheInit;
 }
 
 void Record::setName(Init *NewName) {
   Name = NewName;
   checkName();
   // DO NOT resolve record values to the name at this point because
   // there might be default values for arguments of this def.  Those
   // arguments might not have been resolved yet so we don't want to
   // prematurely assume values for those arguments were not passed to
   // this def.
   //
   // Nonetheless, it may be that some of this Record's values
   // reference the record name.  Indeed, the reason for having the
   // record name be an Init is to provide this flexibility.  The extra
   // resolve steps after completely instantiating defs takes care of
   // this.  See TGParser::ParseDef and TGParser::ParseDefm.
 }
 
+void Record::getDirectSuperClasses(SmallVectorImpl<Record *> &Classes) const {
+  ArrayRef<std::pair<Record *, SMRange>> SCs = getSuperClasses();
+  while (!SCs.empty()) {
+    // Superclasses are in reverse preorder, so 'back' is a direct superclass,
+    // and its transitive superclasses are directly preceding it.
+    Record *SC = SCs.back().first;
+    SCs = SCs.drop_back(1 + SC->getSuperClasses().size());
+    Classes.push_back(SC);
+  }
+}
+
 void Record::resolveReferences(Resolver &R, const RecordVal *SkipVal) {
   for (RecordVal &Value : Values) {
     if (SkipVal == &Value) // Skip resolve the same field as the given one
       continue;
     if (Init *V = Value.getValue()) {
       Init *VR = V->resolveReferences(R);
       if (Value.setValue(VR))
         PrintFatalError(getLoc(), "Invalid value is found when setting '" +

llvm/trunk/lib/TableGen/TGParser.cpp

case tgtok::XIf: {
       if (isa<UnsetInit>(RHS))
         RHSTy = MHSTy;
 
       if (!MHSTy || !RHSTy) {
         TokError("could not get type for !if");
         return nullptr;
       }
 
-      if (MHSTy->typeIsConvertibleTo(RHSTy)) {
-        Type = RHSTy;
-      } else if (RHSTy->typeIsConvertibleTo(MHSTy)) {
-        Type = MHSTy;
-      } else {
-        TokError("inconsistent types for !if");
+      Type = resolveTypes(MHSTy, RHSTy);
+      if (!Type) {
+        TokError(Twine("inconsistent types '") + MHSTy->getAsString() +
+                 "' and '" + RHSTy->getAsString() + "' for !if");
         return nullptr;
       }
       break;
     }
     case tgtok::XSubst: {
       TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
       if (!RHSt) {
         TokError("could not get type for !subst");
if (!CurMultiClass) {
       assert(MCNameRV && "multiclass record must have a NAME");
 
       return UnOpInit::get(UnOpInit::CAST,
                            BinOpInit::get(BinOpInit::STRCONCAT,
                                           VarInit::get(MCNameRV->getName(),
                                                        MCNameRV->getType()),
                                           NewRec->getNameInit(),
                                           StringRecTy::get()),
-                           Class->getDefInit()->getType());
+                           NewRec->getDefInit()->getType());
     }
 
     // The result of the expression is a reference to the new record.
     return DefInit::get(NewRec);
   }
   case tgtok::l_brace: {           // Value ::= '{' ValueList '}'
     SMLoc BraceLoc = Lex.getLoc();
     Lex.Lex(); // eat the '{'

llvm/trunk/test/TableGen/if-type.td

+// RUN: not llvm-tblgen %s 2>&1 | FileCheck %s
+// XFAIL: vg_leak
+
+class A<int dummy> {}
+class B<int dummy> : A<dummy> {}
+class C<int dummy> : A<dummy> {}
+
+// CHECK: Value 'x' of type 'C' is incompatible with initializer '{{.*}}' of type 'A'
+class X<int cc, B b, C c> {
+  C x = !if(cc, b, c);
+}

llvm/trunk/test/TableGen/if.td

 // CHECK: def DI1 {     // I1
 // CHECK-NEXT: int i = 0;
 def DI1: I1<1>;
 
 // CHECK: def DI2 {     // I1 I2
 // CHECK-NEXT: int i = 0;
 def DI2: I2<1>;
 
+// Check that !if with operands of different subtypes can initialize a
+// supertype variable.
+//
+// CHECK: def EXd1 {
+// CHECK:   E x = E1d;
+// CHECK: }
+//
+// CHECK: def EXd2 {
+// CHECK:   E x = E2d;
+// CHECK: }
+class E<int dummy> {}
+class E1<int dummy> : E<dummy> {}
+class E2<int dummy> : E<dummy> {}
+
+class EX<int cc, E1 b, E2 c> {
+  E x = !if(cc, b, c);
+}
+
+def E1d : E1<0>;
+def E2d : E2<0>;
+
+def EXd1 : EX<1, E1d, E2d>;
+def EXd2 : EX<0, E1d, E2d>;
+
 // CHECK:      def One
 // CHECK-NEXT: list<int> first = [1, 2, 3];
 // CHECK-NEXT: list<int> rest = [1, 2, 3];
 
 // CHECK:      def OneB
 // CHECK-NEXT: list<int> vals = [1, 2, 3];
 
 // CHECK:      def Two