[CGTypes] Remove recursion protection

[nikic]

Summary

With opaque pointers, it should no longer be necessary to protect against recursion when converting Clang types to LLVM types.

Dropping this entire code passes check-clang and llvm-test-suite, but I'm not entirely confident that there aren't remaining edge cases.

[efriedma]

LGTM

I skimmed the code, and I don't think there's any way you can end up recursively visiting in a bad way, given standard restrictions on recursive types. (For member pointers, we do query properties of the pointed-to type in some cases, but we don't actually try to convert it to an IR type, so that shouldn't be an issue.)

I remember spending a lot of time on making recursive types/globals work correctly... but I'm not sad to see the complexity go away.

clang/lib/CodeGen/CodeGenTypes.h

class CodeGenTypes {
   llvm::DenseMap<const Type*, std::unique_ptr<CGRecordLayout>> CGRecordLayouts;
 
   /// Contains the LLVM IR type for any converted RecordDecl.
   llvm::DenseMap<const Type*, llvm::StructType *> RecordDeclTypes;
 
   /// Hold memoized CGFunctionInfo results.
   llvm::FoldingSet<CGFunctionInfo> FunctionInfos{FunctionInfosLog2InitSize};
 
-  /// This set keeps track of records that we're currently converting
-  /// to an IR type.  For example, when converting:
-  /// struct A { struct B { int x; } } when processing 'x', the 'A' and 'B'
-  /// types will be in this set.
-  llvm::SmallPtrSet<const Type*, 4> RecordsBeingLaidOut;
-
   llvm::SmallPtrSet<const CGFunctionInfo*, 4> FunctionsBeingProcessed;
 
   /// True if we didn't layout a function due to a being inside
   /// a recursive struct conversion, set this to true.
   bool SkippedLayout;
 
-  SmallVector<const RecordDecl *, 8> DeferredRecords;
-
   /// This map keeps cache of llvm::Types and maps clang::Type to
   /// corresponding llvm::Type.
   llvm::DenseMap<const Type *, llvm::Type *> TypeCache;
 
   llvm::DenseMap<const Type *, llvm::Type *> RecordsWithOpaqueMemberPointers;
 
   static constexpr unsigned FunctionInfosLog2InitSize = 9;
   /// Helper for ConvertType.
public:  // These are internal details of CGT that shouldn't be used externally.
   /// with an LLVM zeroinitializer.
   bool isPointerZeroInitializable(QualType T);
 
   /// IsZeroInitializable - Return whether a record type can be
   /// zero-initialized (in the C++ sense) with an LLVM zeroinitializer.
   bool isZeroInitializable(const RecordDecl *RD);
 
   bool isRecordLayoutComplete(const Type *Ty) const;
-  bool noRecordsBeingLaidOut() const {
-    return RecordsBeingLaidOut.empty();
-  }
-  bool isRecordBeingLaidOut(const Type *Ty) const {
-    return RecordsBeingLaidOut.count(Ty);
-  }
   unsigned getTargetAddressSpace(QualType T) const;
 };
 
 }  // end namespace CodeGen
 }  // end namespace clang
 
 #endif

clang/lib/CodeGen/CodeGenTypes.cpp

 /// isRecordLayoutComplete - Return true if the specified type is already
 /// completely laid out.
 bool CodeGenTypes::isRecordLayoutComplete(const Type *Ty) const {
   llvm::DenseMap<const Type*, llvm::StructType *>::const_iterator I =
   RecordDeclTypes.find(Ty);
   return I != RecordDeclTypes.end() && !I->second->isOpaque();
 }
 
-static bool
-isSafeToConvert(QualType T, CodeGenTypes &CGT,
-                llvm::SmallPtrSet<const RecordDecl*, 16> &AlreadyChecked);
-
-
-/// isSafeToConvert - Return true if it is safe to convert the specified record
-/// decl to IR and lay it out, false if doing so would cause us to get into a
-/// recursive compilation mess.
-static bool
-isSafeToConvert(const RecordDecl *RD, CodeGenTypes &CGT,
-                llvm::SmallPtrSet<const RecordDecl*, 16> &AlreadyChecked) {
-  // If we have already checked this type (maybe the same type is used by-value
-  // multiple times in multiple structure fields, don't check again.
-  if (!AlreadyChecked.insert(RD).second)
-    return true;
-
-  const Type *Key = CGT.getContext().getTagDeclType(RD).getTypePtr();
-
-  // If this type is already laid out, converting it is a noop.
-  if (CGT.isRecordLayoutComplete(Key)) return true;
-
-  // If this type is currently being laid out, we can't recursively compile it.
-  if (CGT.isRecordBeingLaidOut(Key))
-    return false;
-
-  // If this type would require laying out bases that are currently being laid
-  // out, don't do it.  This includes virtual base classes which get laid out
-  // when a class is translated, even though they aren't embedded by-value into
-  // the class.
-  if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) {
-    for (const auto &I : CRD->bases())
-      if (!isSafeToConvert(I.getType()->castAs<RecordType>()->getDecl(), CGT,
-                           AlreadyChecked))
-        return false;
-  }
-
-  // If this type would require laying out members that are currently being laid
-  // out, don't do it.
-  for (const auto *I : RD->fields())
-    if (!isSafeToConvert(I->getType(), CGT, AlreadyChecked))
-      return false;
-
-  // If there are no problems, lets do it.
-  return true;
-}
-
-/// isSafeToConvert - Return true if it is safe to convert this field type,
-/// which requires the structure elements contained by-value to all be
-/// recursively safe to convert.
-static bool
-isSafeToConvert(QualType T, CodeGenTypes &CGT,
-                llvm::SmallPtrSet<const RecordDecl*, 16> &AlreadyChecked) {
-  // Strip off atomic type sugar.
-  if (const auto *AT = T->getAs<AtomicType>())
-    T = AT->getValueType();
-
-  // If this is a record, check it.
-  if (const auto *RT = T->getAs<RecordType>())
-    return isSafeToConvert(RT->getDecl(), CGT, AlreadyChecked);
-
-  // If this is an array, check the elements, which are embedded inline.
-  if (const auto *AT = CGT.getContext().getAsArrayType(T))
-    return isSafeToConvert(AT->getElementType(), CGT, AlreadyChecked);
-
-  // Otherwise, there is no concern about transforming this.  We only care about
-  // things that are contained by-value in a structure that can have another
-  // structure as a member.
-  return true;
-}
-
-
-/// isSafeToConvert - Return true if it is safe to convert the specified record
-/// decl to IR and lay it out, false if doing so would cause us to get into a
-/// recursive compilation mess.
-static bool isSafeToConvert(const RecordDecl *RD, CodeGenTypes &CGT) {
-  // If no structs are being laid out, we can certainly do this one.
-  if (CGT.noRecordsBeingLaidOut()) return true;
-
-  llvm::SmallPtrSet<const RecordDecl*, 16> AlreadyChecked;
-  return isSafeToConvert(RD, CGT, AlreadyChecked);
-}
-
 /// isFuncParamTypeConvertible - Return true if the specified type in a
 /// function parameter or result position can be converted to an IR type at this
-/// point.  This boils down to being whether it is complete, as well as whether
-/// we've temporarily deferred expanding the type because we're in a recursive
-/// context.
+/// point. This boils down to being whether it is complete.
 bool CodeGenTypes::isFuncParamTypeConvertible(QualType Ty) {
   // Some ABIs cannot have their member pointers represented in IR unless
   // certain circumstances have been reached.
   if (const auto *MPT = Ty->getAs<MemberPointerType>())
     return getCXXABI().isMemberPointerConvertible(MPT);
 
   // If this isn't a tagged type, we can convert it!
   const TagType *TT = Ty->getAs<TagType>();
   if (!TT) return true;
 
   // Incomplete types cannot be converted.
-  if (TT->isIncompleteType())
-    return false;
-
-  // If this is an enum, then it is always safe to convert.
-  const RecordType *RT = dyn_cast<RecordType>(TT);
-  if (!RT) return true;
-
-  // Otherwise, we have to be careful.  If it is a struct that we're in the
-  // process of expanding, then we can't convert the function type.  That's ok
-  // though because we must be in a pointer context under the struct, so we can
-  // just convert it to a dummy type.
-  //
-  // We decide this by checking whether ConvertRecordDeclType returns us an
-  // opaque type for a struct that we know is defined.
-  return isSafeToConvert(RT->getDecl(), *this);
+  return !TT->isIncompleteType();
 }
 
 
 /// Code to verify a given function type is complete, i.e. the return type
 /// and all of the parameter types are complete.  Also check to see if we are in
 /// a RS_StructPointer context, and if so whether any struct types have been
 /// pended.  If so, we don't want to ask the ABI lowering code to handle a type
 /// that cannot be converted to an IR type.
if (&format == &llvm::APFloat::PPCDoubleDouble())
     return llvm::Type::getPPC_FP128Ty(VMContext);
   if (&format == &llvm::APFloat::x87DoubleExtended())
     return llvm::Type::getX86_FP80Ty(VMContext);
   llvm_unreachable("Unknown float format!");
 }
 
 llvm::Type *CodeGenTypes::ConvertFunctionTypeInternal(QualType QFT) {
   assert(QFT.isCanonical());
-  const Type *Ty = QFT.getTypePtr();
   const FunctionType *FT = cast<FunctionType>(QFT.getTypePtr());
   // First, check whether we can build the full function type.  If the
   // function type depends on an incomplete type (e.g. a struct or enum), we
   // cannot lower the function type.
   if (!isFuncTypeConvertible(FT)) {
     // This function's type depends on an incomplete tag type.
 
     // Force conversion of all the relevant record types, to make sure
     // we re-convert the FunctionType when appropriate.
     if (const RecordType *RT = FT->getReturnType()->getAs<RecordType>())
       ConvertRecordDeclType(RT->getDecl());
     if (const FunctionProtoType *FPT = dyn_cast<FunctionProtoType>(FT))
       for (unsigned i = 0, e = FPT->getNumParams(); i != e; i++)
         if (const RecordType *RT = FPT->getParamType(i)->getAs<RecordType>())
           ConvertRecordDeclType(RT->getDecl());
 
     SkippedLayout = true;
 
     // Return a placeholder type.
     return llvm::StructType::get(getLLVMContext());
   }
 
-  // While we're converting the parameter types for a function, we don't want
-  // to recursively convert any pointed-to structs.  Converting directly-used
-  // structs is ok though.
-  if (!RecordsBeingLaidOut.insert(Ty).second) {
-    SkippedLayout = true;
-    return llvm::StructType::get(getLLVMContext());
-  }
-
   // The function type can be built; call the appropriate routines to
   // build it.
   const CGFunctionInfo *FI;
   if (const FunctionProtoType *FPT = dyn_cast<FunctionProtoType>(FT)) {
     FI = &arrangeFreeFunctionType(
         CanQual<FunctionProtoType>::CreateUnsafe(QualType(FPT, 0)));
   } else {
     const FunctionNoProtoType *FNPT = cast<FunctionNoProtoType>(FT);
if (FunctionsBeingProcessed.count(FI)) {
     ResultType = llvm::StructType::get(getLLVMContext());
     SkippedLayout = true;
   } else {
 
     // Otherwise, we're good to go, go ahead and convert it.
     ResultType = GetFunctionType(*FI);
   }
 
-  RecordsBeingLaidOut.erase(Ty);
-
-  if (RecordsBeingLaidOut.empty())
-    while (!DeferredRecords.empty())
-      ConvertRecordDeclType(DeferredRecords.pop_back_val());
   return ResultType;
 }
 
 /// ConvertType - Convert the specified type to its LLVM form.
 llvm::Type *CodeGenTypes::ConvertType(QualType T) {
   T = Context.getCanonicalType(T);
 
   const Type *Ty = T.getTypePtr();
if (T->isCUDADeviceBuiltinSurfaceType()) {
         return Ty;
     }
   }
 
   // RecordTypes are cached and processed specially.
   if (const RecordType *RT = dyn_cast<RecordType>(Ty))
     return ConvertRecordDeclType(RT->getDecl());
 
-  // The LLVM type we return for a given Clang type may not always be the same,
-  // most notably when dealing with recursive structs. We mark these potential
-  // cases with ShouldUseCache below. Builtin types cannot be recursive.
-  // TODO: when clang uses LLVM opaque pointers we won't be able to represent
-  // recursive types with LLVM types, making this logic much simpler.
   llvm::Type *CachedType = nullptr;
-  bool ShouldUseCache =
-      Ty->isBuiltinType() ||
-      (noRecordsBeingLaidOut() && FunctionsBeingProcessed.empty());
-  if (ShouldUseCache) {
-    llvm::DenseMap<const Type *, llvm::Type *>::iterator TCI =
-        TypeCache.find(Ty);
-    if (TCI != TypeCache.end())
-      CachedType = TCI->second;
-      // With expensive checks, check that the type we compute matches the
-      // cached type.
+  auto TCI = TypeCache.find(Ty);
 #ifndef EXPENSIVE_CHECKS
-    if (CachedType)
-      return CachedType;
 #endif
-  }
 
   // If we don't have it in the cache, convert it now.
   llvm::Type *ResultType = nullptr;
   switch (Ty->getTypeClass()) {
   case Type::Record: // Handled above.
 #define TYPE(Class, Base)
 #define ABSTRACT_TYPE(Class, Base)
 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
case Type::BitInt: {
     break;
   }
   }
 
   assert(ResultType && "Didn't convert a type?");
   assert((!CachedType || CachedType == ResultType) &&
          "Cached type doesn't match computed type");
 
-  if (ShouldUseCache)
-    TypeCache[Ty] = ResultType;
   return ResultType;
 }
 
 bool CodeGenModule::isPaddedAtomicType(QualType type) {
   return isPaddedAtomicType(type->castAs<AtomicType>());
 }
 
 bool CodeGenModule::isPaddedAtomicType(const AtomicType *type) {
llvm::StructType *CodeGenTypes::ConvertRecordDeclType(const RecordDecl *RD) {
   llvm::StructType *Ty = Entry;
 
   // If this is still a forward declaration, or the LLVM type is already
   // complete, there's nothing more to do.
   RD = RD->getDefinition();
   if (!RD || !RD->isCompleteDefinition() || !Ty->isOpaque())
     return Ty;
 
-  // If converting this type would cause us to infinitely loop, don't do it!
-  if (!isSafeToConvert(RD, *this)) {
-    DeferredRecords.push_back(RD);
-    return Ty;
-  }
-
-  // Okay, this is a definition of a type.  Compile the implementation now.
-  bool InsertResult = RecordsBeingLaidOut.insert(Key).second;
-  (void)InsertResult;
-  assert(InsertResult && "Recursively compiling a struct?");
-
   // Force conversion of non-virtual base classes recursively.
   if (const CXXRecordDecl *CRD = dyn_cast<CXXRecordDecl>(RD)) {
     for (const auto &I : CRD->bases()) {
       if (I.isVirtual()) continue;
       ConvertRecordDeclType(I.getType()->castAs<RecordType>()->getDecl());
     }
   }
 
   // Layout fields.
   std::unique_ptr<CGRecordLayout> Layout = ComputeRecordLayout(RD, Ty);
   CGRecordLayouts[Key] = std::move(Layout);
 
-  // We're done laying out this struct.
-  bool EraseResult = RecordsBeingLaidOut.erase(Key); (void)EraseResult;
-  assert(EraseResult && "struct not in RecordsBeingLaidOut set?");
-
   // If this struct blocked a FunctionType conversion, then recompute whatever
   // was derived from that.
   // FIXME: This is hugely overconservative.
   if (SkippedLayout)
     TypeCache.clear();
 
-  // If we're done converting the outer-most record, then convert any deferred
-  // structs as well.
-  if (RecordsBeingLaidOut.empty())
-    while (!DeferredRecords.empty())
-      ConvertRecordDeclType(DeferredRecords.pop_back_val());
-
   return Ty;
 }
 
 /// getCGRecordLayout - Return record layout info for the given record decl.
 const CGRecordLayout &
 CodeGenTypes::getCGRecordLayout(const RecordDecl *RD) {
   const Type *Key = Context.getTagDeclType(RD).getTypePtr();