Supporting tbaa.struct metadata generation for bitfields

[strimo378]

Summary

Hi all,

this is my first contribution to the LLVM project.

The patch adds support for generating the tbaa.struct metadata for structs containing bitfields. The current implementation does not support bitfields and even generates wrong tbaa.struct metadata ... see https://github.com/llvm/llvm-project/issues/59328 .

The patch is not yet finished. I need some help to create an appropriate test case. My first test case looks like that

struct a {
  int : 8;
  int b1 : 4;
  int b2 : 8;
};
a i1,i2;
void c() { i1 = i2; }

and should generate the following metadata

  call void @llvm.memcpy.p0i8.p0i8.i64(i8* align 4 bitcast (%struct.a* @i1 to i8*), i8* align 4 bitcast (%struct.a* @i2 to i8*), i64 4, i1 false), !tbaa.struct !3
...
  !3 = !{i64 1, i64 2, !4}

Furthermore, I am unsure what Type should be used for adding bitfields to tbaa.struct. The original type or char? The current implementation uses the original type (if not alias).

[lebedev.ri]

Certainly needs tests.
I'm not sure if anyone actually knows this area of LLVM, though.

[strimo378]

• Updated a test case
• Supporting correct output for -new-struct-path-tbaa
• Added a paragraph to LangRef.rst (see https://discourse.llvm.org/t/rfc-clearify-tbaa-struct-requirements-within-language-reference/70835 )

[strimo378]

Ping

[strimo378]

Ping

clang/lib/CodeGen/CodeGenTBAA.h

class CodeGenTBAA {
   /// getRoot - This is the mdnode for the root of the metadata type graph
   /// for this translation unit.
   llvm::MDNode *getRoot();
 
   /// getChar - This is the mdnode for "char", which is special, and any types
   /// considered to be equivalent to it.
   llvm::MDNode *getChar();
 
+  /// AddCollectedField - Add one collected field to Fields vector
+  void
+  AddCollectedField(SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &Fields,
+                    uint64_t Offset, uint64_t Size, QualType QTy, bool MayAlias,
+                    bool FuseOverlapping);
+
   /// CollectFields - Collect information about the fields of a type for
   /// !tbaa.struct metadata formation. Return false for an unsupported type.
   bool CollectFields(uint64_t BaseOffset,
                      QualType Ty,
                      SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &Fields,
                      bool MayAlias);
 
   /// createScalarTypeNode - A wrapper function to create a metadata node

clang/lib/CodeGen/CodeGenTBAA.cpp

 
 TBAAAccessInfo CodeGenTBAA::getVTablePtrAccessInfo(llvm::Type *VTablePtrType) {
   llvm::DataLayout DL(&Module);
   unsigned Size = DL.getPointerTypeSize(VTablePtrType);
   return TBAAAccessInfo(createScalarTypeNode("vtable pointer", getRoot(), Size),
                         Size);
 }
 
+void CodeGenTBAA::AddCollectedField(
+    SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &Fields, uint64_t Offset,
+    uint64_t Size, QualType QTy, bool MayAlias, bool FuseOverlapping) {
+
+  // Fuse fields that overlap in their byte position (e.g. caused by bitfields)
+  if (FuseOverlapping && !Fields.empty() && Fields.back().Offset <= Offset &&
+      Offset < Fields.back().Offset + Fields.back().Size) {
+    Fields.back().Size = (Offset + Size) - Fields.back().Offset;
+    return;
+  }
+
+  llvm::MDNode *TBAAType = MayAlias ? getChar() : getTypeInfo(QTy);
+  llvm::MDNode *TBAATag = getAccessTagInfo(TBAAAccessInfo(TBAAType, Size));
+  Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
+}
+
+// Calculate the number of bytes a bitfield affects.
+// E.g. a 6-bit field starting a bit 0 affects 1 byte,
+// a 6-bit field starting at bit 4 affects 2 bytes.
+static uint64_t getBitFieldByteSize(ASTContext &Context,
+                                    uint64_t FieldBitOffset,
+                                    const FieldDecl *Field) {
+  assert(Field->isBitField());
+
+  uint64_t LastBitOffset =
+      FieldBitOffset + Field->getBitWidthValue(Context) - 1;
+  uint64_t LastByteOffset = LastBitOffset / Context.getCharWidth();
+  uint64_t FirstByteOffset = FieldBitOffset / Context.getCharWidth();
+  return LastByteOffset - FirstByteOffset + 1;
+}
+
 bool
 CodeGenTBAA::CollectFields(uint64_t BaseOffset,
                            QualType QTy,
                            SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &
                              Fields,
                            bool MayAlias) {
-  /* Things not handled yet include: C++ base classes, bitfields, */
+  /* Things not handled yet include: C++ base classes */
 
   if (const RecordType *TTy = QTy->getAs<RecordType>()) {
     const RecordDecl *RD = TTy->getDecl()->getDefinition();
     if (RD->hasFlexibleArrayMember())
       return false;
 
     // TODO: Handle C++ base classes.
     if (const CXXRecordDecl *Decl = dyn_cast<CXXRecordDecl>(RD))
       if (Decl->bases_begin() != Decl->bases_end())
         return false;
 
     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 
     unsigned idx = 0;
     for (RecordDecl::field_iterator i = RD->field_begin(),
          e = RD->field_end(); i != e; ++i, ++idx) {
       if ((*i)->isZeroSize(Context) || (*i)->isUnnamedBitfield())
         continue;
       uint64_t Offset = BaseOffset +
                         Layout.getFieldOffset(idx) / Context.getCharWidth();
       QualType FieldQTy = i->getType();
-      if (!CollectFields(Offset, FieldQTy, Fields,
-                         MayAlias || TypeHasMayAlias(FieldQTy)))
+      bool FieldMayAlias = MayAlias || TypeHasMayAlias(FieldQTy);
+      if ((*i)->isBitField()) {
+        uint64_t Size =
+            getBitFieldByteSize(Context, Layout.getFieldOffset(idx), *i);
+
+        AddCollectedField(Fields, Offset, Size, FieldQTy, FieldMayAlias, true);
+      } else {
+        if (!CollectFields(Offset, FieldQTy, Fields, FieldMayAlias))
           return false;
       }
+    }
     return true;
   }
 
   /* Otherwise, treat whatever it is as a field. */
-  uint64_t Offset = BaseOffset;
   uint64_t Size = Context.getTypeSizeInChars(QTy).getQuantity();
-  llvm::MDNode *TBAAType = MayAlias ? getChar() : getTypeInfo(QTy);
-  llvm::MDNode *TBAATag = getAccessTagInfo(TBAAAccessInfo(TBAAType, Size));
-  Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size, TBAATag));
+  AddCollectedField(Fields, BaseOffset, Size, QTy, MayAlias, false);
   return true;
 }
 
 llvm::MDNode *
 CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
   const Type *Ty = Context.getCanonicalType(QTy).getTypePtr();
 
   if (llvm::MDNode *N = StructMetadataCache[Ty])
for (FieldDecl *Field : RD->fields()) {
       QualType FieldQTy = Field->getType();
       llvm::MDNode *TypeNode = isValidBaseType(FieldQTy) ?
           getBaseTypeInfo(FieldQTy) : getTypeInfo(FieldQTy);
       if (!TypeNode)
         return BaseTypeMetadataCache[Ty] = nullptr;
 
       uint64_t BitOffset = Layout.getFieldOffset(Field->getFieldIndex());
       uint64_t Offset = Context.toCharUnitsFromBits(BitOffset).getQuantity();
-      uint64_t Size = Context.getTypeSizeInChars(FieldQTy).getQuantity();
+      uint64_t Size = Field->isBitField()
+                          ? getBitFieldByteSize(Context, BitOffset, Field)
+                          : Context.getTypeSizeInChars(FieldQTy).getQuantity();
+
       Fields.push_back(llvm::MDBuilder::TBAAStructField(Offset, Size,
                                                         TypeNode));
     }
 
     SmallString<256> OutName;
     if (Features.CPlusPlus) {
       // Don't use the mangler for C code.
       llvm::raw_svector_ostream Out(OutName);

clang/test/CodeGen/tbaa-struct.cpp

 void copy7(A *a1, AA *a2) {
 // CHECK-LABEL: _Z5copy7P1AS0_
 // CHECK: call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 4 dereferenceable(16) %{{.*}}, ptr noundef nonnull align 4 dereferenceable(16) %{{.*}}, i64 16, i1 false)
 // CHECK-OLD-SAME: !tbaa.struct [[TS]]
 // CHECK-NEW-SAME: !tbaa [[TAG_char]]
   *a1 = *a2;
 }
 
+struct E {
+  int : 8;
+  int a1 : 8;
+  int : 8;
+  int a2 : 8;
+  
+  int b1 : 9;
+  int : (32-9-9);
+  int b2 : 9;
+
+  int c1 : 15;
+  int c2 : 1;
+  int c3 : 1;
+  int : (32-15-1-1);
+  
+  char dummy[4];
+};
+
+void copy8(E *e1, E *e2) {
+// CHECK-LABEL: _Z5copy8P1ES0_
+// CHECK: call void @llvm.memcpy.p0.p0.i64(ptr noundef nonnull align 4 dereferenceable(16) %{{.*}}, ptr noundef nonnull align 4 dereferenceable(16) %{{.*}}, i64 16, i1 false)
+// CHECK-OLD-SAME: !tbaa.struct [[TS6:!.*]]
+// CHECK-NEW-SAME: !tbaa [[TAG_E:![0-9]*]]
+  *e1 = *e2;
+}
+
 // CHECK-OLD: [[TS]] = !{i64 0, i64 2, !{{.*}}, i64 4, i64 4, !{{.*}}, i64 8, i64 1, !{{.*}}, i64 12, i64 4, !{{.*}}}
 // CHECK-OLD: [[CHAR:!.*]] = !{!"omnipotent char", !{{.*}}}
 // CHECK-OLD: [[TAG_INT:!.*]] = !{[[INT:!.*]], [[INT]], i64 0}
 // CHECK-OLD: [[INT]] = !{!"int", [[CHAR]]
 // CHECK-OLD: [[TAG_CHAR:!.*]] = !{[[CHAR]], [[CHAR]], i64 0}
 // (offset, size) = (0,1) char; (4,2) short; (8,4) int; (12,1) char; (16,4) int; (20,4) int
 // CHECK-OLD: [[TS2]] = !{i64 0, i64 1, !{{.*}}, i64 4, i64 2, !{{.*}}, i64 8, i64 4, !{{.*}}, i64 12, i64 1, !{{.*}}, i64 16, i64 4, {{.*}}, i64 20, i64 4, {{.*}}}
 // (offset, size) = (0,8) char; (0,2) char; (4,8) char
 // CHECK-OLD: [[TS3]] = !{i64 0, i64 8, !{{.*}}, i64 0, i64 2, !{{.*}}, i64 4, i64 8, !{{.*}}}
 // CHECK-OLD: [[TS4]] = !{i64 0, i64 1, [[TAG_CHAR]], i64 1, i64 1, [[TAG_CHAR]], i64 2, i64 1, [[TAG_CHAR]]}
 // CHECK-OLD: [[TS5]] = !{i64 0, i64 1, [[TAG_CHAR]], i64 4, i64 1, [[TAG_CHAR]], i64 5, i64 1, [[TAG_CHAR]]}
+// CHECK-OLD: [[TS6]] = !{i64 1, i64 1, [[TAG_INT]], i64 3, i64 1, [[TAG_INT]], i64 4, i64 2, [[TAG_INT]], i64 6, i64 2, [[TAG_INT]], i64 8, i64 2, [[TAG_INT]], i64 10, i64 1, [[TAG_INT]], i64 12, i64 4, [[TAG_CHAR]]}
 
 // CHECK-NEW-DAG: [[TYPE_char:!.*]] = !{{{.*}}, i64 1, !"omnipotent char"}
 // CHECK-NEW-DAG: [[TAG_char]] = !{[[TYPE_char]], [[TYPE_char]], i64 0, i64 0}
 // CHECK-NEW-DAG: [[TYPE_short:!.*]] = !{[[TYPE_char]], i64 2, !"short"}
 // CHECK-NEW-DAG: [[TYPE_int:!.*]] = !{[[TYPE_char]], i64 4, !"int"}
 // CHECK-NEW-DAG: [[TYPE_A:!.*]] = !{[[TYPE_char]], i64 16, !"_ZTS1A", [[TYPE_short]], i64 0, i64 2, [[TYPE_int]], i64 4, i64 4, [[TYPE_char]], i64 8, i64 1, [[TYPE_int]], i64 12, i64 4}
 // CHECK-NEW-DAG: [[TAG_A]] = !{[[TYPE_A]], [[TYPE_A]], i64 0, i64 16}
 // CHECK-NEW-DAG: [[TYPE_B:!.*]] = !{[[TYPE_char]], i64 24, !"_ZTS1B", [[TYPE_char]], i64 0, i64 1, [[TYPE_A]], i64 4, i64 16, [[TYPE_int]], i64 20, i64 4}
 // CHECK-NEW-DAG: [[TAG_B]] = !{[[TYPE_B]], [[TYPE_B]], i64 0, i64 24}
 // CHECK-NEW-DAG: [[TAG_U]] = !{[[TYPE_char]], [[TYPE_char]], i64 0, i64 12}
 // CHECK-NEW-DAG: [[TYPE_C:!.*]] = !{[[TYPE_char]], i64 3, !"_ZTS1C", [[TYPE_char]], i64 0, i64 1, [[TYPE_char]], i64 1, i64 1, [[TYPE_char]], i64 2, i64 1}
 // CHECK-NEW-DAG: [[TAG_C]] = !{[[TYPE_C]], [[TYPE_C]], i64 0, i64 3}
 // CHECK-NEW-DAG: [[TYPE_D:!.*]] = !{[[TYPE_char]], i64 6, !"_ZTS1D", [[TYPE_char]], i64 0, i64 1, [[TYPE_char]], i64 4, i64 1, [[TYPE_char]], i64 5, i64 1}
 // CHECK-NEW-DAG: [[TAG_D]] = !{[[TYPE_D]], [[TYPE_D]], i64 0, i64 6}
+// CHECK-NEW-DAG: [[TYPE_E:!.*]] = !{[[TYPE_char]], i64 16, !"_ZTS1E", [[TYPE_int]], i64 1, i64 1, [[TYPE_int]], i64 3, i64 1, [[TYPE_int]], i64 4, i64 2, [[TYPE_int]], i64 6, i64 2, [[TYPE_int]], i64 8, i64 2, [[TYPE_int]], i64 9, i64 1, [[TYPE_int]], i64 10, i64 1, [[TYPE_char]], i64 12, i64 4}
+// CHECK-NEW-DAG: [[TAG_E]] = !{[[TYPE_E]], [[TYPE_E]], i64 0, i64 16}

llvm/docs/LangRef.rst

 This describes a struct with two fields. The first is at offset 0 bytes
 with size 4 bytes, and has tbaa tag !1. The second is at offset 8 bytes
 and has size 4 bytes and has tbaa tag !2.
 
 Note that the fields need not be contiguous. In this example, there is a
 4 byte gap between the two fields. This gap represents padding which
 does not carry useful data and need not be preserved.
 
+The order of the fields is unspecified. The byte range
+[offset, offset + size) of two fields must not overlap. The size
+of one field might be greater than the size of its TBAA tag (e.g. in
+case of arrays) or might be smaller (e.g. in case of bitfields).
+
 '``noalias``' and '``alias.scope``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 ``noalias`` and ``alias.scope`` metadata provide the ability to specify generic
 noalias memory-access sets. This means that some collection of memory access
 instructions (loads, stores, memory-accessing calls, etc.) that carry
 ``noalias`` metadata can specifically be specified not to alias with some other
 collection of memory access instructions that carry ``alias.scope`` metadata.