[tbaa] Handle base classes in struct tbaa

[brunodf]

Summary

This is a fix for the miscompilation reported in https://github.com/llvm/llvm-project/issues/55384

Not adding a new test case since existing test cases already cover base classes (including new-struct-path tbaa).

[brunodf]

Anyone?

[jeroen.dobbelaere]

lgtm

[fhahn]

It looks like this commit is breaking bootstrap builds of LLVM/Clang, e.g. https://lab.llvm.org/buildbot/#/builders/37/builds/14224

FAILED: lib/Bitcode/Reader/CMakeFiles/LLVMBitReader.dir/BitcodeReader.cpp.o 
/b/sanitizer-x86_64-linux-autoconf/build/tsan_debug_build/bin/clang++  -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib/Bitcode/Reader -I/b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Bitcode/Reader -Iinclude -I/b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/include -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wno-comment -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O2 -g -DNDEBUG    -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -MD -MT lib/Bitcode/Reader/CMakeFiles/LLVMBitReader.dir/BitcodeRea
 der.cpp.o -MF lib/Bitcode/Reader/CMakeFiles/LLVMBitReader.dir/BitcodeReader.cpp.o.d -o lib/Bitcode/Reader/CMakeFiles/LLVMBitReader.dir/BitcodeReader.cpp.o -c /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Bitcode/Reader/BitcodeReader.cpp
Offsets must be increasing!
  %45 = load ptr, ptr %Context.i1113, align 8, !dbg !137343, !tbaa !97945, !noalias !137026
!68773 = !{!"_ZTSN12_GLOBAL__N_113BitcodeReaderE", !68334, i64 8, !68774, i64 0, !61585, i64 432, !61585, i64 440, !61620, i64 448, !61620, i64 456, !62256, i64 464, !61620, i64 472, !68775, i64 480, !68775, i64 504, !68778, i64 528, !68781, i64 552, !68783, i64 584, !68785, i64 616, !68561, i64 648, !68787, i64 712, !68788, i64 728, !68791, i64 752, !68795, i64 784, !68800, i64 1312, !68803, i64 1336, !68806, i64 1360, !68809, i64 1384, !68812, i64 1408, !68817, i64 1456, !68820, i64 1480, !68823, i64 1504, !68823, i64 1536, !62256, i64 1568, !68825, i64 1576, !68827, i64 1608, !68830, i64 1632, !68832, i64 1664, !68820, i64 1744, !62256, i64 1768, !62256, i64 1769, !62256, i64 1770, !68836, i64 1776, !68775, i64 1848, !68841, i64 1872, !68847, i64 1904}
clang++: /b/sanitizer-x86_64-linux-autoconf/build/llvm-project/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp:10631: bool llvm::LoopVectorizePass::processLoop(llvm::Loop*): Assertion `!verifyFunction(*L->getHeader()->getParent(), &dbgs())' failed.

Please take a look and revert the patch if the fix isn't trivial.

[jeroen.dobbelaere]

In D126956#3604978, @fhahn wrote:

Please take a look and revert the patch if the fix isn't trivial.

the patch has already been reverted so Bruno can investigate.

[brunodf]

New version that fixes the problem with base classes not appearing in order of increasing offset.

This issue was discovered in the multistage build, but the test case has now been extended for this situation.

Also changed to obtain the the size of the base subobject with getDataSize() since other subobjects may be allocated in its tail padding.

[efriedma]

clang/lib/CodeGen/CodeGenTBAA.cpp

366

Maybe add a comment explaining why each TBAAStructField has a unique offset. (If the offsets aren't unique, you need to use stable_sort.)

[brunodf]

Adding comment regarding empty subobjects.

[jeroen.dobbelaere]

lgtm

clang/lib/CodeGen/CodeGenTBAA.cpp

CodeGenTBAA::getTBAAStructInfo(QualType QTy) {
   // For now, handle any other kind of type conservatively.
   return StructMetadataCache[Ty] = nullptr;
 }
 
 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<llvm::MDBuilder::TBAAStructField, 4> Fields;
+    using TBAAStructField = llvm::MDBuilder::TBAAStructField;
+    SmallVector<TBAAStructField, 4> Fields;
+    if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(RD)) {
+      // Handle C++ base classes. Non-virtual bases can treated a a kind of
+      // field. Virtual bases are more complex and omitted, but avoid an
+      // incomplete view for NewStructPathTBAA.
+      if (CodeGenOpts.NewStructPathTBAA && CXXRD->getNumVBases() != 0)
+        return BaseTypeMetadataCache[Ty] = nullptr;
+      for (const CXXBaseSpecifier &B : CXXRD->bases()) {
+        if (B.isVirtual())
+          continue;
+        QualType BaseQTy = B.getType();
+        const CXXRecordDecl *BaseRD = BaseQTy->getAsCXXRecordDecl();
+        if (BaseRD->isEmpty())
+          continue;
+        llvm::MDNode *TypeNode = isValidBaseType(BaseQTy)
+                                     ? getBaseTypeInfo(BaseQTy)
+                                     : getTypeInfo(BaseQTy);
+        if (!TypeNode)
+          return BaseTypeMetadataCache[Ty] = nullptr;
+        uint64_t Offset = Layout.getBaseClassOffset(BaseRD).getQuantity();
+        uint64_t Size =
+            Context.getASTRecordLayout(BaseRD).getDataSize().getQuantity();
+        Fields.push_back(
+            llvm::MDBuilder::TBAAStructField(Offset, Size, TypeNode));
+      }
+      // The order in which base class subobjects are allocated is unspecified,
+      // so may differ from declaration order. In particular, Itanium ABI will
+      // allocate a primary base first.
+      // Since we exclude empty subobjects, the objects are not overlapping and
+      // their offsets are unique.
+      llvm::sort(Fields,
+                 [](const TBAAStructField &A, const TBAAStructField &B) {
+                   return A.Offset < B.Offset;
+                 });
+    }
     for (FieldDecl *Field : RD->fields()) {
       if (Field->isZeroSize(Context) || Field->isUnnamedBitfield())
         continue;
       QualType FieldQTy = Field->getType();
       llvm::MDNode *TypeNode = isValidBaseType(FieldQTy) ?
           getBaseTypeInfo(FieldQTy) : getTypeInfo(FieldQTy);
       if (!TypeNode)
         return BaseTypeMetadataCache[Ty] = nullptr;

clang/test/CodeGen/tbaa-class.cpp

 };
 class StructS2 : public StructS
 {
 public:
    uint16_t f16_2;
    uint32_t f32_2;
 };
 
+class StructT {
+public:
+  uint32_t f32_2;
+  void foo();
+};
+class StructM1 : public StructS, public StructT {
+public:
+  uint16_t f16_2;
+};
+class StructDyn {
+public:
+  uint32_t f32_2;
+  virtual void foo();
+};
+class StructM2 : public StructS, public StructDyn {
+public:
+  uint16_t f16_2;
+};
+
 uint32_t g(uint32_t *s, StructA *A, uint64_t count) {
 // CHECK-LABEL: define{{.*}} i32 @_Z1g
 // CHECK: store i32 1, i32* %{{.*}}, align 4, !tbaa [[TAG_i32:!.*]]
 // CHECK: store i32 4, i32* %{{.*}}, align 4, !tbaa [[TAG_i32]]
 // PATH-LABEL: define{{.*}} i32 @_Z1g
 // PATH: store i32 1, i32* %{{.*}}, align 4, !tbaa [[TAG_i32:!.*]]
 // PATH: store i32 4, i32* %{{.*}}, align 4, !tbaa [[TAG_A_f32:!.*]]
   *s = 1;
// PATH: store i32 4, i32* %{{.*}}, align 4, !tbaa [[TAG_B_a_f32]]
   StructB *b1 = &(C->b);
   StructB *b2 = &(D->b);
   // b1, b2 have different context.
   b1->a.f32 = 1;
   b2->a.f32 = 4;
   return b1->a.f32;
 }
 
+uint32_t g13(StructM1 *M, StructS *S) {
+  // CHECK-LABEL: define{{.*}} i32 @_Z3g13
+  // CHECK: store i16 1, i16* %{{.*}}, align 4, !tbaa [[TAG_i16]]
+  // CHECK: store i16 4, i16* %{{.*}}, align 4, !tbaa [[TAG_i16]]
+  // PATH-LABEL: define{{.*}} i32 @_Z3g13
+  // PATH: store i16 1, i16* %{{.*}}, align 4, !tbaa [[TAG_S_f16]]
+  // PATH: store i16 4, i16* %{{.*}}, align 4, !tbaa [[TAG_M1_f16_2:!.*]]
+  S->f16 = 1;
+  M->f16_2 = 4;
+  return S->f16;
+}
+
+uint32_t g14(StructM2 *M, StructS *S) {
+  // CHECK-LABEL: define{{.*}} i32 @_Z3g14
+  // CHECK: store i16 1, i16* %{{.*}}, align 4, !tbaa [[TAG_i16]]
+  // CHECK: store i16 4, i16* %{{.*}}, align 4, !tbaa [[TAG_i16]]
+  // PATH-LABEL: define{{.*}} i32 @_Z3g14
+  // PATH: store i16 1, i16* %{{.*}}, align 4, !tbaa [[TAG_S_f16]]
+  // PATH: store i16 4, i16* %{{.*}}, align 4, !tbaa [[TAG_M2_f16_2:!.*]]
+  S->f16 = 1;
+  M->f16_2 = 4;
+  return S->f16;
+}
+
 // CHECK: [[TYPE_char:!.*]] = !{!"omnipotent char", [[TAG_cxx_tbaa:!.*]],
 // CHECK: [[TAG_cxx_tbaa]] = !{!"Simple C++ TBAA"}
 // CHECK: [[TAG_i32]] = !{[[TYPE_i32:!.*]], [[TYPE_i32]], i64 0}
 // CHECK: [[TYPE_i32]] = !{!"int", [[TYPE_char]],
 // CHECK: [[TAG_i16]] = !{[[TYPE_i16:!.*]], [[TYPE_i16]], i64 0}
 // CHECK: [[TYPE_i16]] = !{!"short", [[TYPE_char]],
 
 // OLD-PATH: [[TYPE_CHAR:!.*]] = !{!"omnipotent char", !
 // OLD-PATH: [[TAG_i32]] = !{[[TYPE_INT:!.*]], [[TYPE_INT]], i64 0}
 // OLD-PATH: [[TYPE_INT]] = !{!"int", [[TYPE_CHAR]]
 // OLD-PATH: [[TAG_A_f32]] = !{[[TYPE_A:!.*]], [[TYPE_INT]], i64 4}
 // OLD-PATH: [[TYPE_A]] = !{!"_ZTS7StructA", [[TYPE_SHORT:!.*]], i64 0, [[TYPE_INT]], i64 4, [[TYPE_SHORT]], i64 8, [[TYPE_INT]], i64 12}
 // OLD-PATH: [[TYPE_SHORT:!.*]] = !{!"short", [[TYPE_CHAR]]
 // OLD-PATH: [[TAG_A_f16]] = !{[[TYPE_A]], [[TYPE_SHORT]], i64 0}
 // OLD-PATH: [[TAG_B_a_f32]] = !{[[TYPE_B:!.*]], [[TYPE_INT]], i64 8}
 // OLD-PATH: [[TYPE_B]] = !{!"_ZTS7StructB", [[TYPE_SHORT]], i64 0, [[TYPE_A]], i64 4, [[TYPE_INT]], i64 20}
 // OLD-PATH: [[TAG_B_a_f16]] = !{[[TYPE_B]], [[TYPE_SHORT]], i64 4}
 // OLD-PATH: [[TAG_B_f32]] = !{[[TYPE_B]], [[TYPE_INT]], i64 20}
 // OLD-PATH: [[TAG_B_a_f32_2]] = !{[[TYPE_B]], [[TYPE_INT]], i64 16}
 // OLD-PATH: [[TAG_S_f32]] = !{[[TYPE_S:!.*]], [[TYPE_INT]], i64 4}
 // OLD-PATH: [[TYPE_S]] = !{!"_ZTS7StructS", [[TYPE_SHORT]], i64 0, [[TYPE_INT]], i64 4}
 // OLD-PATH: [[TAG_S_f16]] = !{[[TYPE_S]], [[TYPE_SHORT]], i64 0}
 // OLD-PATH: [[TAG_S2_f32_2]] = !{[[TYPE_S2:!.*]], [[TYPE_INT]], i64 12}
-// OLD-PATH: [[TYPE_S2]] = !{!"_ZTS8StructS2", [[TYPE_SHORT]], i64 8, [[TYPE_INT]], i64 12}
+// OLD-PATH: [[TYPE_S2]] = !{!"_ZTS8StructS2", [[TYPE_S]], i64 0, [[TYPE_SHORT]], i64 8, [[TYPE_INT]], i64 12}
 // OLD-PATH: [[TAG_C_b_a_f32]] = !{[[TYPE_C:!.*]], [[TYPE_INT]], i64 12}
 // OLD-PATH: [[TYPE_C]] = !{!"_ZTS7StructC", [[TYPE_SHORT]], i64 0, [[TYPE_B]], i64 4, [[TYPE_INT]], i64 28}
 // OLD-PATH: [[TAG_D_b_a_f32]] = !{[[TYPE_D:!.*]], [[TYPE_INT]], i64 12}
 // OLD-PATH: [[TYPE_D]] = !{!"_ZTS7StructD", [[TYPE_SHORT]], i64 0, [[TYPE_B]], i64 4, [[TYPE_INT]], i64 28, [[TYPE_CHAR]], i64 32}
+// OLD-PATH: [[TAG_M1_f16_2]] = !{[[TYPE_M1:!.*]], [[TYPE_SHORT]], i64 12}
+// OLD-PATH: [[TYPE_M1]] = !{!"_ZTS8StructM1", [[TYPE_S]], i64 0, [[TYPE_T:!.*]], i64 8, [[TYPE_SHORT]], i64 12}
+// OLD_PATH: [[TYPE_T]] = !{!"_ZTS7StructT", [[TYPE_INT]], i64 0}
+// OLD-PATH: [[TAG_M2_f16_2]] = !{[[TYPE_M2:!.*]], [[TYPE_SHORT]], i64 20}
+// OLD-PATH: [[TYPE_M2]] = !{!"_ZTS8StructM2", [[TYPE_DYN:!.*]], i64 0, [[TYPE_S]], i64 12, [[TYPE_SHORT]], i64 20}
+// OLD_PATH: [[TYPE_DYN]] = !{!"_ZTS9StructDyn", [[TYPE_INT]], i64 8}
 
 // NEW-PATH: [[TYPE_CHAR:!.*]] = !{!{{.*}}, i64 1, !"omnipotent char"}
 // NEW-PATH: [[TAG_i32]] = !{[[TYPE_INT:!.*]], [[TYPE_INT]], i64 0, i64 4}
 // NEW-PATH: [[TYPE_INT]] = !{[[TYPE_CHAR]], i64 4, !"int"}
 // NEW-PATH: [[TAG_A_f32]] = !{[[TYPE_A:!.*]], [[TYPE_INT]], i64 4, i64 4}
 // NEW-PATH: [[TYPE_A]] = !{[[TYPE_CHAR]], i64 16, !"_ZTS7StructA", [[TYPE_SHORT:!.*]], i64 0, i64 2, [[TYPE_INT]], i64 4, i64 4, [[TYPE_SHORT]], i64 8, i64 2, [[TYPE_INT]], i64 12, i64 4}
 // NEW-PATH: [[TYPE_SHORT:!.*]] = !{[[TYPE_CHAR]], i64 2, !"short"}
 // NEW-PATH: [[TAG_A_f16]] = !{[[TYPE_A]], [[TYPE_SHORT]], i64 0, i64 2}
 // NEW-PATH: [[TAG_B_a_f32]] = !{[[TYPE_B:!.*]], [[TYPE_INT]], i64 8, i64 4}
 // NEW-PATH: [[TYPE_B]] = !{[[TYPE_CHAR]], i64 24, !"_ZTS7StructB", [[TYPE_SHORT]], i64 0, i64 2, [[TYPE_A]], i64 4, i64 16, [[TYPE_INT]], i64 20, i64 4}
 // NEW-PATH: [[TAG_B_a_f16]] = !{[[TYPE_B]], [[TYPE_SHORT]], i64 4, i64 2}
 // NEW-PATH: [[TAG_B_f32]] = !{[[TYPE_B]], [[TYPE_INT]], i64 20, i64 4}
 // NEW-PATH: [[TAG_B_a_f32_2]] = !{[[TYPE_B]], [[TYPE_INT]], i64 16, i64 4}
 // NEW-PATH: [[TAG_S_f32]] = !{[[TYPE_S:!.*]], [[TYPE_INT]], i64 4, i64 4}
 // NEW-PATH: [[TYPE_S]] = !{[[TYPE_CHAR]], i64 8, !"_ZTS7StructS", [[TYPE_SHORT]], i64 0, i64 2, [[TYPE_INT]], i64 4, i64 4}
 // NEW-PATH: [[TAG_S_f16]] = !{[[TYPE_S]], [[TYPE_SHORT]], i64 0, i64 2}
 // NEW-PATH: [[TAG_S2_f32_2]] = !{[[TYPE_S2:!.*]], [[TYPE_INT]], i64 12, i64 4}
-// NEW-PATH: [[TYPE_S2]] = !{[[TYPE_CHAR]], i64 16, !"_ZTS8StructS2", [[TYPE_SHORT]], i64 8, i64 2, [[TYPE_INT]], i64 12, i64 4}
+// NEW-PATH: [[TYPE_S2]] = !{[[TYPE_CHAR]], i64 16, !"_ZTS8StructS2", [[TYPE_S]], i64 0, i64 8, [[TYPE_SHORT]], i64 8, i64 2, [[TYPE_INT]], i64 12, i64 4}
 // NEW-PATH: [[TAG_C_b_a_f32]] = !{[[TYPE_C:!.*]], [[TYPE_INT]], i64 12, i64 4}
 // NEW-PATH: [[TYPE_C]] = !{[[TYPE_CHAR]], i64 32, !"_ZTS7StructC", [[TYPE_SHORT]], i64 0, i64 2, [[TYPE_B]], i64 4, i64 24, [[TYPE_INT]], i64 28, i64 4}
 // NEW-PATH: [[TAG_D_b_a_f32]] = !{[[TYPE_D:!.*]], [[TYPE_INT]], i64 12, i64 4}
 // NEW-PATH: [[TYPE_D]] = !{[[TYPE_CHAR]], i64 36, !"_ZTS7StructD", [[TYPE_SHORT]], i64 0, i64 2, [[TYPE_B]], i64 4, i64 24, [[TYPE_INT]], i64 28, i64 4, [[TYPE_CHAR]], i64 32, i64 1}
+// NEW-PATH: [[TAG_M1_f16_2]] = !{[[TYPE_M1:!.*]], [[TYPE_SHORT]], i64 12, i64 2}
+// NEW-PATH: [[TYPE_M1]] = !{[[TYPE_CHAR]], i64 16, !"_ZTS8StructM1", [[TYPE_S]], i64 0, i64 8, [[TYPE_T:!.*]], i64 8, i64 4, [[TYPE_SHORT]], i64 12, i64 2}
+// NEW_PATH: [[TYPE_T]] = !{[[TYPE_CHAR]], i64 4, !"_ZTS7StructT", [[TYPE_INT]], i64 0, i64 4}
+// NEW-PATH: [[TAG_M2_f16_2]] = !{[[TYPE_M2:!.*]], [[TYPE_SHORT]], i64 20, i64 2}
+// NEW-PATH: [[TYPE_M2]] = !{[[TYPE_CHAR]], i64 24, !"_ZTS8StructM2", [[TYPE_DYN:!.*]], i64 0, i64 12, [[TYPE_S]], i64 12, i64 8, [[TYPE_SHORT]], i64 20, i64 2}
+// NEW_PATH: [[TYPE_DYN]] = !{[[TYPE_CHAR]], i64 12, !"_ZTS9StructDyn", [[TYPE_INT]], i64 8, i64 4}

clang/unittests/CodeGen/TBAAMetadataTest.cpp

TEST(TBAAMetadataTest, BaseClass) {
   auto ClassBase = MMTuple(
     MMString("_ZTS4Base"),
     MMTuple(
       MMString("int"),
       OmnipotentCharCXX,
       MConstInt(0)),
     MConstInt(0));
 
-  auto ClassDerived = MMTuple(
-    MMString("_ZTS7Derived"),
-    MMTuple(
-      MMString("short"),
-      OmnipotentCharCXX,
-      MConstInt(0)),
+  auto ClassDerived =
+      MMTuple(MMString("_ZTS7Derived"), ClassBase, MConstInt(0),
+              MMTuple(MMString("short"), OmnipotentCharCXX, MConstInt(0)),
               MConstInt(4));
 
   const Instruction *I = match(BB,
       MInstruction(Instruction::Store,
         MConstInt(14, 32),
         MMTuple(
           ClassBase,
           MMTuple(
             MMString("int"),
TEST(TBAAMetadataTest, PolymorphicClass) {
   auto ClassBase = MMTuple(
     MMString("_ZTS4Base"),
     MMTuple(
       MMString("int"),
       OmnipotentCharCXX,
       MConstInt(0)),
     MConstInt(Compiler.PtrSize));
 
-  auto ClassDerived = MMTuple(
-    MMString("_ZTS7Derived"),
-    MMTuple(
-      MMString("short"),
-      OmnipotentCharCXX,
-      MConstInt(0)),
+  auto ClassDerived =
+      MMTuple(MMString("_ZTS7Derived"), ClassBase, MConstInt(0),
+              MMTuple(MMString("short"), OmnipotentCharCXX, MConstInt(0)),
               MConstInt(Compiler.PtrSize + 4));
 
   const Instruction *I = match(BB,
       MInstruction(Instruction::Store,
         MConstInt(14, 32),
         MMTuple(
           ClassBase,
           MMTuple(
             MMString("int"),