[CodeGen] Generate TBAA type descriptors in a more reliable manner

[kosarev]

Summary

This patch introduces a couple of helper functions that make it possible to handle the caching logic in a single place.

[rjmccall]

lib/CodeGen/CodeGenTBAA.cpp

267 ↗

(On Diff #122618)

The main danger with persisting this kind of reference is that DenseMap doesn't actually guarantee stability, so if there are recursive calls that can grow the data structure, the reference will become dangling. I think your patch is okay for the previous two functions, although I'd like you to check that, but in this function I'm confident that it's wrong, because you definitely recursively call getBaseTypeInfo below.

[kosarev]

Indeed, DenseMap invalidates iterators on insertion. But then even the "technically correct" part of these changes make things more fragile while my original concern was reliability and not performance. I particularly don't like the repeating cache assignments.

What if we add a set of helper functions whose only purpose is to produce new nodes so we can handle cache-related things in a single place? Something like this:

llvm::MDNode *CodeGenTBAA::getTypeInfoHelper(llvm::Type *Type) {
  ... Whatever we currently do in getTypeInfo(), except accesses to MetadataCache ...
}

llvm::MDNode *CodeGenTBAA::getTypeInfo(QualType QTy) {
  ...
  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
  if (llvm::MDNode *N = MetadataCache[Ty])
    return N;

  return MetadataCache[Ty] = getTypeInfoHelper(Ty);
}

If for any reasons it is undesirable, then I think I better abandon this diff. Maybe just add a comment explaining that we lookup twice for the same key intentionally.

[rjmccall]

I think having a primary function that handles the caching logic makes some sense. I think there might be some cases that intentionally don't cache their normal result, though, so it might be harder than you think. Up to you whether you want to continue.

[kosarev]

Reworked to use helper functions to separate producing metadata nodes from other code.

[kosarev]

In D39953#929144, @rjmccall wrote:

I think there might be some cases that intentionally don't cache their normal result, though, so it might be harder than you think.

My understanding is that conceptually every canonical type has a single corresponding type node; we shall never return different nodes for the same type. With the updated patch we cache nodes for all types, including different versions of char. This is supposed to be an improvement saving us some execution time.

[rjmccall]

Okay, looks good.

cfe/trunk/lib/CodeGen/CodeGenTBAA.h

bool CollectFields(uint64_t BaseOffset,
                      SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &Fields,
                      bool MayAlias);
 
   /// A wrapper function to create a scalar type. For struct-path aware TBAA,
   /// the scalar type has the same format as the struct type: name, offset,
   /// pointer to another node in the type DAG.
   llvm::MDNode *createTBAAScalarType(StringRef Name, llvm::MDNode *Parent);
 
+  /// getTypeInfoHelper - An internal helper function to generate metadata used
+  /// to describe accesses to objects of the given type.
+  llvm::MDNode *getTypeInfoHelper(const Type *Ty);
+
+  /// getBaseTypeInfoHelper - An internal helper function to generate metadata
+  /// used to describe accesses to objects of the given base type.
+  llvm::MDNode *getBaseTypeInfoHelper(const Type *Ty);
+
 public:
   CodeGenTBAA(ASTContext &Ctx, llvm::LLVMContext &VMContext,
               const CodeGenOptions &CGO,
               const LangOptions &Features,
               MangleContext &MContext);
   ~CodeGenTBAA();
 
   /// getTypeInfo - Get metadata used to describe accesses to objects of the

cfe/trunk/lib/CodeGen/CodeGenTBAA.cpp

if (const RecordType *TTy = QTy->getAs<RecordType>()) {
     // RD can be struct, union, class, interface or enum.
     // For now, we only handle struct and class.
     if (RD->isStruct() || RD->isClass())
       return true;
   }
   return false;
 }
 
-llvm::MDNode *CodeGenTBAA::getTypeInfo(QualType QTy) {
-  // At -O0 or relaxed aliasing, TBAA is not emitted for regular types.
-  if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing)
-    return nullptr;
-
-  // If the type has the may_alias attribute (even on a typedef), it is
-  // effectively in the general char alias class.
-  if (TypeHasMayAlias(QTy))
-    return getChar();
-
-  // We need this function to not fall back to returning the "omnipotent char"
-  // type node for aggregate and union types. Otherwise, any dereference of an
-  // aggregate will result into the may-alias access descriptor, meaning all
-  // subsequent accesses to direct and indirect members of that aggregate will
-  // be considered may-alias too.
-  // TODO: Combine getTypeInfo() and getBaseTypeInfo() into a single function.
-  if (isValidBaseType(QTy))
-    return getBaseTypeInfo(QTy);
-
-  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
-  if (llvm::MDNode *N = MetadataCache[Ty])
-    return N;
-
+llvm::MDNode *CodeGenTBAA::getTypeInfoHelper(const Type *Ty) {
   // Handle builtin types.
   if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
     switch (BTy->getKind()) {
     // Character types are special and can alias anything.
     // In C++, this technically only includes "char" and "unsigned char",
     // and not "signed char". In C, it includes all three. For now,
     // the risk of exploiting this detail in C++ seems likely to outweigh
     // the benefit.
case BuiltinType::ULongLong:
       return getTypeInfo(Context.LongLongTy);
     case BuiltinType::UInt128:
       return getTypeInfo(Context.Int128Ty);
 
     // Treat all other builtin types as distinct types. This includes
     // treating wchar_t, char16_t, and char32_t as distinct from their
     // "underlying types".
     default:
-      return MetadataCache[Ty] =
-        createTBAAScalarType(BTy->getName(Features), getChar());
+      return createTBAAScalarType(BTy->getName(Features), getChar());
     }
   }
 
   // C++1z [basic.lval]p10: "If a program attempts to access the stored value of
   // an object through a glvalue of other than one of the following types the
   // behavior is undefined: [...] a char, unsigned char, or std::byte type."
   if (Ty->isStdByteType())
-    return MetadataCache[Ty] = getChar();
+    return getChar();
 
   // Handle pointers and references.
   // TODO: Implement C++'s type "similarity" and consider dis-"similar"
   // pointers distinct.
   if (Ty->isPointerType() || Ty->isReferenceType())
-    return MetadataCache[Ty] = createTBAAScalarType("any pointer",
-                                                    getChar());
+    return createTBAAScalarType("any pointer", getChar());
 
   // Enum types are distinct types. In C++ they have "underlying types",
   // however they aren't related for TBAA.
   if (const EnumType *ETy = dyn_cast<EnumType>(Ty)) {
     // In C++ mode, types have linkage, so we can rely on the ODR and
     // on their mangled names, if they're external.
     // TODO: Is there a way to get a program-wide unique name for a
     // decl with local linkage or no linkage?
     if (!Features.CPlusPlus || !ETy->getDecl()->isExternallyVisible())
-      return MetadataCache[Ty] = getChar();
+      return getChar();
 
     SmallString<256> OutName;
     llvm::raw_svector_ostream Out(OutName);
     MContext.mangleTypeName(QualType(ETy, 0), Out);
-    return MetadataCache[Ty] = createTBAAScalarType(OutName, getChar());
+    return createTBAAScalarType(OutName, getChar());
   }
 
   // For now, handle any other kind of type conservatively.
-  return MetadataCache[Ty] = getChar();
+  return getChar();
+}
+
+llvm::MDNode *CodeGenTBAA::getTypeInfo(QualType QTy) {
+  // At -O0 or relaxed aliasing, TBAA is not emitted for regular types.
+  if (CodeGenOpts.OptimizationLevel == 0 || CodeGenOpts.RelaxedAliasing)
+    return nullptr;
+
+  // If the type has the may_alias attribute (even on a typedef), it is
+  // effectively in the general char alias class.
+  if (TypeHasMayAlias(QTy))
+    return getChar();
+
+  // We need this function to not fall back to returning the "omnipotent char"
+  // type node for aggregate and union types. Otherwise, any dereference of an
+  // aggregate will result into the may-alias access descriptor, meaning all
+  // subsequent accesses to direct and indirect members of that aggregate will
+  // be considered may-alias too.
+  // TODO: Combine getTypeInfo() and getBaseTypeInfo() into a single function.
+  if (isValidBaseType(QTy))
+    return getBaseTypeInfo(QTy);
+
+  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
+  if (llvm::MDNode *N = MetadataCache[Ty])
+    return N;
+
+  // Note that the following helper call is allowed to add new nodes to the
+  // cache, which invalidates all its previously obtained iterators. So we
+  // first generate the node for the type and then add that node to the cache.
+  llvm::MDNode *TypeNode = getTypeInfoHelper(Ty);
+  return MetadataCache[Ty] = TypeNode;
 }
 
 TBAAAccessInfo CodeGenTBAA::getVTablePtrAccessInfo() {
   return TBAAAccessInfo(createTBAAScalarType("vtable pointer", getRoot()));
 }
 
 bool
 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
   SmallVector<llvm::MDBuilder::TBAAStructField, 4> Fields;
   if (CollectFields(0, QTy, Fields, TypeHasMayAlias(QTy)))
     return MDHelper.createTBAAStructNode(Fields);
 
   // For now, handle any other kind of type conservatively.
   return StructMetadataCache[Ty] = nullptr;
 }
 
-llvm::MDNode *CodeGenTBAA::getBaseTypeInfo(QualType QTy) {
-  if (!isValidBaseType(QTy))
-    return nullptr;
-
-  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
-  if (llvm::MDNode *N = BaseTypeMetadataCache[Ty])
-    return N;
-
-  if (const RecordType *TTy = QTy->getAs<RecordType>()) {
+llvm::MDNode *CodeGenTBAA::getBaseTypeInfoHelper(const Type *Ty) {
+  if (auto *TTy = dyn_cast<RecordType>(Ty)) {
     const RecordDecl *RD = TTy->getDecl()->getDefinition();
 
     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
     SmallVector <std::pair<llvm::MDNode*, uint64_t>, 4> Fields;
     unsigned idx = 0;
     for (RecordDecl::field_iterator i = RD->field_begin(),
          e = RD->field_end(); i != e; ++i, ++idx) {
       QualType FieldQTy = i->getType();
if (auto *TTy = dyn_cast<RecordType>(Ty)) {
     if (Features.CPlusPlus) {
       // Don't use the mangler for C code.
       llvm::raw_svector_ostream Out(OutName);
       MContext.mangleTypeName(QualType(Ty, 0), Out);
     } else {
       OutName = RD->getName();
     }
     // Create the struct type node with a vector of pairs (offset, type).
-    return BaseTypeMetadataCache[Ty] =
-      MDHelper.createTBAAStructTypeNode(OutName, Fields);
+    return MDHelper.createTBAAStructTypeNode(OutName, Fields);
   }
 
-  return BaseTypeMetadataCache[Ty] = nullptr;
+  return nullptr;
+}
+
+llvm::MDNode *CodeGenTBAA::getBaseTypeInfo(QualType QTy) {
+  if (!isValidBaseType(QTy))
+    return nullptr;
+
+  const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
+  if (llvm::MDNode *N = BaseTypeMetadataCache[Ty])
+    return N;
+
+  // Note that the following helper call is allowed to add new nodes to the
+  // cache, which invalidates all its previously obtained iterators. So we
+  // first generate the node for the type and then add that node to the cache.
+  llvm::MDNode *TypeNode = getBaseTypeInfoHelper(Ty);
+  return BaseTypeMetadataCache[Ty] = TypeNode;
 }
 
 llvm::MDNode *CodeGenTBAA::getAccessTagInfo(TBAAAccessInfo Info) {
   if (Info.isMayAlias())
     Info = TBAAAccessInfo(getChar());
 
   if (!Info.AccessType)
     return nullptr;