[BPF] Improve pruning to avoid generate more types in BTF

[yonghong-song]

Summary

Commit 3671bdbcd214("[BPF] Fix a BTF type pruning bug") fixed a
pruning bug to allow generate more types. But the commit has a bug
which permits to generate more types than necessary. The following
is an example to illustrate the problem.

struct t1 {
  int a;
};  
struct t2 {
  struct t1 *p1;
  struct t1 *p2;
  int b;
};  
int foo(struct t2 *arg) {
  return arg->b;
}

The following is the part of BTF generation sequence:

(1). 'struct t2 *arg' -> 'struct t1 *p1'
     In this step, the type 'struct t1' will be generated as
     a forward decl and the ptr type (to 'struct t1') will
     be stored in the internal type table.
(2). now the second field 'struct t1 *p2' will be processed.
     Since the ptr type (to 'struct t1') already in the type
     table, the existing logic strips out ptr modifier and
     is able to generate BTF type for 'struct t1'.

In the above step (2), if CheckPointer is true (the type traversal
chain including a struct member), 'ptr' modifier should be checked
and the subsequent type generation should be skipped since
the same case has been processed in visitDerivedType().

The issue is exposed when I am trying to use llvm15 to compile
some internal bpf programs. The bpf skeleton put the whole
ELF section (after striping some sections like dwarf) as a string.
The large BTF section triggered the following error:

bpf_object_with_struct_ops_test_prog_bpf/BpfObjectWithStructOpsTestProg.skel.h:222:23:
error: string literal of length 140144 exceeds maximum length 65536 that C++ compilers
are required to support [-Werror,-Woverlength-strings]
      return (const void *)"\  
                           ^~
1 error generated.

Although adding -Wno-overlength-strings could workaround the issue,
improving llvm BTF generation sounds better esp. for users using vmlinux.h.

[eddyz87]

llvm/lib/Target/BPF/BTFDebug.cpp

904

Looks reasonable.

To be honest, I find the logic with CheckPointer / SeenPointer a bit confusing. As far as I understand the main thing is the following code:

void BTFDebug::visitDerivedType(...) {
  if (CheckPointer && !SeenPointer) {
    SeenPointer = Tag == dwarf::DW_TAG_pointer_type;
  }

  if (CheckPointer && SeenPointer) {
    // generate forward declaration
    return;
  }
  ...
  if (Tag == dwarf::DW_TAG_member)
    visitTypeEntry(DTy->getBaseType(), TempTypeId, true /* !! */, false);
  else
    ...
}

And setting CheckPointer to true means that visitor should generate forward declarations when possible. Adding a comment describing behavior of these parameters somewhere would be really helpful.

[yonghong-song]

add comments to explain CheckPointer and SeePointer.

[yonghong-song]

update the comment.

[yonghong-song]

Added some comments to explain the rationale behind CheckPointer and SeePointer. If it looks okay, could you accept the patch?

[eddyz87]

In D145816#4188022, @yonghong-song wrote:

Added some comments to explain the rationale behind CheckPointer and SeePointer. If it looks okay, could you accept the patch?

Sure, thank you!

llvm/lib/Target/BPF/BTFDebug.h

void visitStructType(const DICompositeType *STy, bool IsStruct,
                        uint32_t &TypeId);
   void visitArrayType(const DICompositeType *ATy, uint32_t &TypeId);
   void visitEnumType(const DICompositeType *ETy, uint32_t &TypeId);
   void visitDerivedType(const DIDerivedType *DTy, uint32_t &TypeId,
                         bool CheckPointer, bool SeenPointer);
   void visitMapDefType(const DIType *Ty, uint32_t &TypeId);
   /// @}
 
+  /// Check whether the type is a forward declaration candidate or not.
+  bool IsForwardDeclCandidate(const DIType *Base);
+
   /// Get the file content for the subprogram. Certain lines of the file
   /// later may be put into string table and referenced by line info.
   std::string populateFileContent(const DISubprogram *SP);
 
   /// Construct a line info.
   void constructLineInfo(const DISubprogram *SP, MCSymbol *Label, uint32_t Line,
                          uint32_t Column);
 

llvm/lib/Target/BPF/BTFDebug.cpp

if (Tag == dwarf::DW_TAG_structure_type || Tag == dwarf::DW_TAG_union_type) {
     else
       visitStructType(CTy, Tag == dwarf::DW_TAG_structure_type, TypeId);
   } else if (Tag == dwarf::DW_TAG_array_type)
     visitArrayType(CTy, TypeId);
   else if (Tag == dwarf::DW_TAG_enumeration_type)
     visitEnumType(CTy, TypeId);
 }
 
+bool BTFDebug::IsForwardDeclCandidate(const DIType *Base) {
+  if (const auto *CTy = dyn_cast<DICompositeType>(Base)) {
+    auto CTag = CTy->getTag();
+    if ((CTag == dwarf::DW_TAG_structure_type ||
+         CTag == dwarf::DW_TAG_union_type) &&
+        !CTy->getName().empty() && !CTy->isForwardDecl())
+      return true;
+  }
+  return false;
+}
+
 /// Handle pointer, typedef, const, volatile, restrict and member types.
 void BTFDebug::visitDerivedType(const DIDerivedType *DTy, uint32_t &TypeId,
                                 bool CheckPointer, bool SeenPointer) {
   unsigned Tag = DTy->getTag();
 
   /// Try to avoid chasing pointees, esp. structure pointees which may
   /// unnecessary bring in a lot of types.
   if (CheckPointer && !SeenPointer) {
     SeenPointer = Tag == dwarf::DW_TAG_pointer_type;
   }
 
   if (CheckPointer && SeenPointer) {
     const DIType *Base = DTy->getBaseType();
     if (Base) {
-      if (const auto *CTy = dyn_cast<DICompositeType>(Base)) {
-        auto CTag = CTy->getTag();
-        if ((CTag == dwarf::DW_TAG_structure_type ||
-             CTag == dwarf::DW_TAG_union_type) &&
-            !CTy->getName().empty() && !CTy->isForwardDecl()) {
-          /// Find a candidate, generate a fixup. Later on the struct/union
-          /// pointee type will be replaced with either a real type or
-          /// a forward declaration.
-          auto TypeEntry = std::make_unique<BTFTypeDerived>(DTy, Tag, true);
-          auto &Fixup = FixupDerivedTypes[CTy];
-          Fixup.push_back(std::make_pair(DTy, TypeEntry.get()));
-          TypeId = addType(std::move(TypeEntry), DTy);
-          return;
-        }
-      }
-    }
-  }
+      if (IsForwardDeclCandidate(Base)) {
+        auto &Fixup = FixupDerivedTypes[cast<DICompositeType>(Base)];
 
   if (Tag == dwarf::DW_TAG_pointer_type) {
     int TmpTypeId = genBTFTypeTags(DTy, -1);
     if (TmpTypeId >= 0) {
       auto TypeDEntry =
           std::make_unique<BTFTypeDerived>(TmpTypeId, Tag, DTy->getName());
       TypeId = addType(std::move(TypeDEntry), DTy);
     } else {
void BTFDebug::visitDerivedType(const DIDerivedType *DTy, uint32_t &TypeId,
   // struct/union member.
   uint32_t TempTypeId = 0;
   if (Tag == dwarf::DW_TAG_member)
     visitTypeEntry(DTy->getBaseType(), TempTypeId, true, false);
   else
     visitTypeEntry(DTy->getBaseType(), TempTypeId, CheckPointer, SeenPointer);
 }
 
+/// Visit a type entry. CheckPointer is true if the type has
+/// one of its predecessors as one struct/union member. SeenPointer
+/// is true if CheckPointer is true and one of its predecessors
+/// is a pointer. The goal of CheckPointer and SeenPointer is to
+/// do pruning for struct/union types so some of these types
+/// will not be emitted in BTF and rather forward declarations
+/// will be generated.
 void BTFDebug::visitTypeEntry(const DIType *Ty, uint32_t &TypeId,
                               bool CheckPointer, bool SeenPointer) {
   if (!Ty || DIToIdMap.find(Ty) != DIToIdMap.end()) {
     TypeId = DIToIdMap[Ty];
 
     // To handle the case like the following:
     //    struct t;
     //    typedef struct t _t;
if (Ty && (!CheckPointer || !SeenPointer)) {
         while (DTy) {
           const DIType *BaseTy = DTy->getBaseType();
           if (!BaseTy)
             break;
 
           if (DIToIdMap.find(BaseTy) != DIToIdMap.end()) {
             DTy = dyn_cast<DIDerivedType>(BaseTy);
           } else {
+            if (CheckPointer && DTy->getTag() == dwarf::DW_TAG_pointer_type) {
+              SeenPointer = true;
+              if (IsForwardDeclCandidate(BaseTy))
+                break;
+            }
             uint32_t TmpTypeId;
             visitTypeEntry(BaseTy, TmpTypeId, CheckPointer, SeenPointer);
             break;
           }
         }
       }
     }
 

llvm/test/CodeGen/BPF/BTF/pruning-dup-ptr-struct.ll

+; RUN: llc -march=bpfel -o - %s | FileCheck %s
+; RUN: llc -march=bpfeb -o - %s | FileCheck %s
+; Source:
+;   struct t1 {
+;     int a;
+;   };
+;   struct t2 {
+;     struct t1 *p1;
+;     struct t1 *p2;
+;     int b;
+;   };
+;   int foo(struct t2 *arg) {
+;     return arg->b;
+;   }
+; Compilation flags:
+;   clang -target bpf -O2 -g -S -emit-llvm t.c
+
+%struct.t2 = type { ptr, ptr, i32 }
+
+; Function Attrs: argmemonly mustprogress nofree norecurse nosync nounwind readonly willreturn
+define dso_local i32 @foo(ptr nocapture noundef readonly %arg) local_unnamed_addr #0 !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata ptr %arg, metadata !22, metadata !DIExpression()), !dbg !23
+  %b = getelementptr inbounds %struct.t2, ptr %arg, i64 0, i32 2, !dbg !24
+  %0 = load i32, ptr %b, align 8, !dbg !24, !tbaa !25
+  ret i32 %0, !dbg !31
+}
+
+; CHECK:             .long   0                               # BTF_KIND_PTR(id = 1)
+; CHECK-NEXT:        .long   33554432                        # 0x2000000
+; CHECK-NEXT:        .long   2
+; CHECK-NEXT:        .long   1                               # BTF_KIND_STRUCT(id = 2)
+; CHECK-NEXT:        .long   67108867                        # 0x4000003
+; CHECK-NEXT:        .long   24
+; CHECK-NEXT:        .long   4
+; CHECK-NEXT:        .long   3
+; CHECK-NEXT:        .long   0                               # 0x0
+; CHECK-NEXT:        .long   7
+; CHECK-NEXT:        .long   3
+; CHECK-NEXT:        .long   64                              # 0x40
+; CHECK-NEXT:        .long   10
+; CHECK-NEXT:        .long   4
+; CHECK-NEXT:        .long   128                             # 0x80
+; CHECK-NEXT:        .long   0                               # BTF_KIND_PTR(id = 3)
+; CHECK-NEXT:        .long   33554432                        # 0x2000000
+; CHECK-NEXT:        .long   7
+; CHECK-NEXT:        .long   12                              # BTF_KIND_INT(id = 4)
+; CHECK-NEXT:        .long   16777216                        # 0x1000000
+; CHECK-NEXT:        .long   4
+; CHECK-NEXT:        .long   16777248                        # 0x1000020
+; CHECK-NEXT:        .long   0                               # BTF_KIND_FUNC_PROTO(id = 5)
+; CHECK-NEXT:        .long   218103809                       # 0xd000001
+; CHECK-NEXT:        .long   4
+; CHECK-NEXT:        .long   16
+; CHECK-NEXT:        .long   1
+; CHECK-NEXT:        .long   20                              # BTF_KIND_FUNC(id = 6)
+; CHECK-NEXT:        .long   201326593                       # 0xc000001
+; CHECK-NEXT:        .long   5
+; CHECK-NEXT:        .long   60                              # BTF_KIND_FWD(id = 7)
+; CHECK-NEXT:        .long   117440512                       # 0x7000000
+; CHECK-NEXT:        .long   0
+
+; CHECK:             .ascii  "t2"                            # string offset=1
+; CHECK:             .ascii  "p1"                            # string offset=4
+; CHECK:             .ascii  "p2"                            # string offset=7
+; CHECK:             .byte   98                              # string offset=10
+; CHECK:             .ascii  "int"                           # string offset=12
+; CHECK:             .ascii  "arg"                           # string offset=16
+; CHECK:             .ascii  "foo"                           # string offset=20
+; CHECK:             .ascii  "t1"                            # string offset=60
+
+; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+attributes #0 = { argmemonly mustprogress nofree norecurse nosync nounwind readonly willreturn "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" }
+attributes #1 = { nocallback nofree nosync nounwind readnone speculatable willreturn }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!2, !3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 15.0.7 (https://github.com/llvm/llvm-project.git 8dfdcc7b7bf66834a761bd8de445840ef68e4d1a)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "t1.c", directory: "/tmp/home/yhs/tmp3/tests", checksumkind: CSK_MD5, checksum: "9a79ff24a6244249e556afd85288af94")
+!2 = !{i32 7, !"Dwarf Version", i32 5}
+!3 = !{i32 2, !"Debug Info Version", i32 3}
+!4 = !{i32 1, !"wchar_size", i32 4}
+!5 = !{i32 7, !"frame-pointer", i32 2}
+!6 = !{!"clang version 15.0.7 (https://github.com/llvm/llvm-project.git 8dfdcc7b7bf66834a761bd8de445840ef68e4d1a)"}
+!7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 9, type: !8, scopeLine: 9, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !21)
+!8 = !DISubroutineType(types: !9)
+!9 = !{!10, !11}
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64)
+!12 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "t2", file: !1, line: 4, size: 192, elements: !13)
+!13 = !{!14, !19, !20}
+!14 = !DIDerivedType(tag: DW_TAG_member, name: "p1", scope: !12, file: !1, line: 5, baseType: !15, size: 64)
+!15 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !16, size: 64)
+!16 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "t1", file: !1, line: 1, size: 32, elements: !17)
+!17 = !{!18}
+!18 = !DIDerivedType(tag: DW_TAG_member, name: "a", scope: !16, file: !1, line: 2, baseType: !10, size: 32)
+!19 = !DIDerivedType(tag: DW_TAG_member, name: "p2", scope: !12, file: !1, line: 6, baseType: !15, size: 64, offset: 64)
+!20 = !DIDerivedType(tag: DW_TAG_member, name: "b", scope: !12, file: !1, line: 7, baseType: !10, size: 32, offset: 128)
+!21 = !{!22}
+!22 = !DILocalVariable(name: "arg", arg: 1, scope: !7, file: !1, line: 9, type: !11)
+!23 = !DILocation(line: 0, scope: !7)
+!24 = !DILocation(line: 10, column: 15, scope: !7)
+!25 = !{!26, !30, i64 16}
+!26 = !{!"t2", !27, i64 0, !27, i64 8, !30, i64 16}
+!27 = !{!"any pointer", !28, i64 0}
+!28 = !{!"omnipotent char", !29, i64 0}
+!29 = !{!"Simple C/C++ TBAA"}
+!30 = !{!"int", !28, i64 0}
+!31 = !DILocation(line: 10, column: 3, scope: !7)