[BPF] fix a bug for BTF pointee type pruning

In BTF, pointee type pruning is used to reduce cluttering
too many unused types into prog BTF. For example,
   struct task_struct {
      ...
      struct mm_struct *mm;
      ...
   }
If bpf program does not access members of "struct mm_struct",
there is no need to bring types for "struct mm_struct" to BTF.

This patch fixed a bug where an incorrect pruning happened.
The test case like below:
    struct t;
    typedef struct t _t;
    struct s1 { _t *c; };
    int test1(struct s1 *arg) { ... }

    struct t { int a; int b; };
    struct s2 { _t c; }
    int test2(struct s2 *arg) { ... }

After processing test1(), among others, BPF backend generates BTF types for
    "struct s1", "_t" and a placeholder for "struct t".
Note that "struct t" is not really generated. If later a direct access
to "struct t" member happened, "struct t" BTF type will be generated
properly.

During processing test2(), when processing member type "_t c",
BPF backend sees type "_t" already generated, so returned.
This caused the problem that "struct t" BTF type is never generated and
eventually causing incorrect type definition for "struct s2".

To fix the issue, during DebugInfo type traversal, even if a
typedef/const/volatile/restrict derived type has been recorded in BTF,
if it is not a type pruning candidate, type traversal of its base type continues.

Differential Revision: https://reviews.llvm.org/D82041

(cherry picked from commit 89648eb16d01725457f958e634d16c534b64c42c)

3 files changed, 280 insertions, 0 deletions

diff --git a/llvm/lib/Target/BPF/BTFDebug.cpp b/llvm/lib/Target/BPF/BTFDebug.cpp
index a9fb04f20d1c..6daeb3b4b63b 100644
--- a/llvm/lib/Target/BPF/BTFDebug.cpp
+++ b/llvm/lib/Target/BPF/BTFDebug.cpp
@@ -600,6 +600,38 @@ 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;
+    //    struct s1 { _t *c; };
+    //    int test1(struct s1 *arg) { ... }
+    //
+    //    struct t { int a; int b; };
+    //    struct s2 { _t c; }
+    //    int test2(struct s2 *arg) { ... }
+    //
+    // During traversing test1() argument, "_t" is recorded
+    // in DIToIdMap and a forward declaration fixup is created
+    // for "struct t" to avoid pointee type traversal.
+    //
+    // During traversing test2() argument, even if we see "_t" is
+    // already defined, we should keep moving to eventually
+    // bring in types for "struct t". Otherwise, the "struct s2"
+    // definition won't be correct.
+    if (Ty && (!CheckPointer || !SeenPointer)) {
+      if (const auto *DTy = dyn_cast<DIDerivedType>(Ty)) {
+        unsigned Tag = DTy->getTag();
+        if (Tag == dwarf::DW_TAG_typedef || Tag == dwarf::DW_TAG_const_type ||
+            Tag == dwarf::DW_TAG_volatile_type ||
+            Tag == dwarf::DW_TAG_restrict_type) {
+          uint32_t TmpTypeId;
+          visitTypeEntry(DTy->getBaseType(), TmpTypeId, CheckPointer,
+                         SeenPointer);
+        }
+      }
+    }
+
     return;
   }
 
diff --git a/llvm/test/CodeGen/BPF/BTF/pruning-const.ll b/llvm/test/CodeGen/BPF/BTF/pruning-const.ll
new file mode 100644
index 000000000000..516aeb46b1ce
--- /dev/null
+++ b/llvm/test/CodeGen/BPF/BTF/pruning-const.ll
@@ -0,0 +1,120 @@
+; RUN: llc -march=bpfel -filetype=asm -o - %s | FileCheck -check-prefixes=CHECK %s
+; RUN: llc -march=bpfeb -filetype=asm -o - %s | FileCheck -check-prefixes=CHECK %s
+; Source:
+;   struct tt;
+;   struct s1 { const struct tt *mp; };
+;   int test1(struct s1 *arg)
+;   {
+;     return  0;
+;   }
+;
+;   struct tt { int m1; int m2; };
+;   struct s2 { const struct tt m3; };
+;   int test2(struct s2 *arg)
+;   {
+;     return arg->m3.m1;
+;   }
+; Compilation flags:
+;   clang -target bpf -O2 -g -S -emit-llvm t.c
+
+%struct.s1 = type { %struct.tt* }
+%struct.tt = type { i32, i32 }
+%struct.s2 = type { %struct.tt }
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @test1(%struct.s1* nocapture readnone %arg) local_unnamed_addr #0 !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata %struct.s1* %arg, metadata !22, metadata !DIExpression()), !dbg !23
+  ret i32 0, !dbg !24
+}
+
+; Function Attrs: norecurse nounwind readonly
+define dso_local i32 @test2(%struct.s2* nocapture readonly %arg) local_unnamed_addr #1 !dbg !25 {
+entry:
+  call void @llvm.dbg.value(metadata %struct.s2* %arg, metadata !33, metadata !DIExpression()), !dbg !34
+  %m1 = getelementptr inbounds %struct.s2, %struct.s2* %arg, i64 0, i32 0, i32 0, !dbg !35
+  %0 = load i32, i32* %m1, align 4, !dbg !35, !tbaa !36
+  ret i32 %0, !dbg !42
+}
+
+; CHECK:        .long   0                       # BTF_KIND_CONST(id = 4)
+; CHECK-NEXT:   .long   167772160               # 0xa000000
+; CHECK-NEXT:   .long   10
+
+; CHECK:        .long   60                      # BTF_KIND_STRUCT(id = 9)
+; CHECK-NEXT:   .long   67108865                # 0x4000001
+; CHECK-NEXT:   .long   8
+; CHECK-NEXT:   .long   63
+; CHECK-NEXT:   .long   4
+; CHECK-NEXT:   .long   0                       # 0x0
+
+; CHECK:        .long   66                      # BTF_KIND_STRUCT(id = 10)
+; CHECK-NEXT:   .long   67108866                # 0x4000002
+; CHECK-NEXT:   .long   8
+; CHECK-NEXT:   .long   69
+; CHECK-NEXT:   .long   6
+; CHECK-NEXT:   .long   0                       # 0x0
+; CHECK-NEXT:   .long   72
+; CHECK-NEXT:   .long   6
+; CHECK-NEXT:   .long   32                      # 0x20
+
+; CHECK:        .ascii  "s2"                    # string offset=60
+; CHECK:        .ascii  "m3"                    # string offset=63
+; CHECK:        .ascii  "tt"                    # string offset=66
+; CHECK:        .ascii  "m1"                    # string offset=69
+; CHECK:        .ascii  "m2"                    # string offset=72
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata) #2
+
+attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { norecurse nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind readnone speculatable willreturn }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 11.0.0 (https://github.com/llvm/llvm-project.git 7cfd267c518aba226b34b7fbfe8db70000b22053)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "t.c", directory: "/tmp/home/yhs/work/tests/btf")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 11.0.0 (https://github.com/llvm/llvm-project.git 7cfd267c518aba226b34b7fbfe8db70000b22053)"}
+!7 = distinct !DISubprogram(name: "test1", scope: !1, file: !1, line: 3, type: !8, scopeLine: 4, 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: "s1", file: !1, line: 2, size: 64, elements: !13)
+!13 = !{!14}
+!14 = !DIDerivedType(tag: DW_TAG_member, name: "mp", scope: !12, file: !1, line: 2, baseType: !15, size: 64)
+!15 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !16, size: 64)
+!16 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !17)
+!17 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "tt", file: !1, line: 8, size: 64, elements: !18)
+!18 = !{!19, !20}
+!19 = !DIDerivedType(tag: DW_TAG_member, name: "m1", scope: !17, file: !1, line: 8, baseType: !10, size: 32)
+!20 = !DIDerivedType(tag: DW_TAG_member, name: "m2", scope: !17, file: !1, line: 8, baseType: !10, size: 32, offset: 32)
+!21 = !{!22}
+!22 = !DILocalVariable(name: "arg", arg: 1, scope: !7, file: !1, line: 3, type: !11)
+!23 = !DILocation(line: 0, scope: !7)
+!24 = !DILocation(line: 5, column: 3, scope: !7)
+!25 = distinct !DISubprogram(name: "test2", scope: !1, file: !1, line: 10, type: !26, scopeLine: 11, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !32)
+!26 = !DISubroutineType(types: !27)
+!27 = !{!10, !28}
+!28 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !29, size: 64)
+!29 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "s2", file: !1, line: 9, size: 64, elements: !30)
+!30 = !{!31}
+!31 = !DIDerivedType(tag: DW_TAG_member, name: "m3", scope: !29, file: !1, line: 9, baseType: !16, size: 64)
+!32 = !{!33}
+!33 = !DILocalVariable(name: "arg", arg: 1, scope: !25, file: !1, line: 10, type: !28)
+!34 = !DILocation(line: 0, scope: !25)
+!35 = !DILocation(line: 12, column: 18, scope: !25)
+!36 = !{!37, !39, i64 0}
+!37 = !{!"s2", !38, i64 0}
+!38 = !{!"tt", !39, i64 0, !39, i64 4}
+!39 = !{!"int", !40, i64 0}
+!40 = !{!"omnipotent char", !41, i64 0}
+!41 = !{!"Simple C/C++ TBAA"}
+!42 = !DILocation(line: 12, column: 3, scope: !25)
diff --git a/llvm/test/CodeGen/BPF/BTF/pruning-typedef.ll b/llvm/test/CodeGen/BPF/BTF/pruning-typedef.ll
new file mode 100644
index 000000000000..4ac8994a5ce3
--- /dev/null
+++ b/llvm/test/CodeGen/BPF/BTF/pruning-typedef.ll
@@ -0,0 +1,128 @@
+; RUN: llc -march=bpfel -filetype=asm -o - %s | FileCheck -check-prefixes=CHECK %s
+; RUN: llc -march=bpfeb -filetype=asm -o - %s | FileCheck -check-prefixes=CHECK %s
+; Source:
+;   struct tt;
+;   typedef struct tt _tt;
+;   typedef _tt __tt;
+;   struct s1 { __tt *mp; };
+;   int test1(struct s1 *arg)
+;   {
+;     return  0;
+;   }
+;
+;   struct tt { int m1; int m2; };
+;   struct s2 { __tt m3; };
+;   int test2(struct s2 *arg)
+;   {
+;     return arg->m3.m1;
+;   }
+; Compilation flags:
+;   clang -target bpf -O2 -g -S -emit-llvm t.c
+
+%struct.s1 = type { %struct.tt* }
+%struct.tt = type { i32, i32 }
+%struct.s2 = type { %struct.tt }
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @test1(%struct.s1* nocapture readnone %arg) local_unnamed_addr #0 !dbg !7 {
+entry:
+  call void @llvm.dbg.value(metadata %struct.s1* %arg, metadata !23, metadata !DIExpression()), !dbg !24
+  ret i32 0, !dbg !25
+}
+
+; Function Attrs: norecurse nounwind readonly
+define dso_local i32 @test2(%struct.s2* nocapture readonly %arg) local_unnamed_addr #1 !dbg !26 {
+entry:
+  call void @llvm.dbg.value(metadata %struct.s2* %arg, metadata !34, metadata !DIExpression()), !dbg !35
+  %m1 = getelementptr inbounds %struct.s2, %struct.s2* %arg, i64 0, i32 0, i32 0, !dbg !36
+  %0 = load i32, i32* %m1, align 4, !dbg !36, !tbaa !37
+  ret i32 %0, !dbg !43
+}
+
+; CHECK:        .long   7                       # BTF_KIND_TYPEDEF(id = 4)
+; CHECK-NEXT:   .long   134217728               # 0x8000000
+; CHECK-NEXT:   .long   5
+; CHECK-NEXT:   .long   12                      # BTF_KIND_TYPEDEF(id = 5)
+; CHECK-NEXT:   .long   134217728               # 0x8000000
+; CHECK-NEXT:   .long   11
+
+; CHECK:        .long   69                      # BTF_KIND_STRUCT(id = 10)
+; CHECK-NEXT:   .long   67108865                # 0x4000001
+; CHECK-NEXT:   .long   8
+; CHECK-NEXT:   .long   72
+; CHECK-NEXT:   .long   4
+; CHECK-NEXT:   .long   0                       # 0x0
+
+; CHECK:        .long   75                      # BTF_KIND_STRUCT(id = 11)
+; CHECK-NEXT:   .long   67108866                # 0x4000002
+; CHECK-NEXT:   .long   8
+; CHECK-NEXT:   .long   78
+; CHECK-NEXT:   .long   7
+; CHECK-NEXT:   .long   0                       # 0x0
+; CHECK-NEXT:   .long   81
+; CHECK-NEXT:   .long   7
+; CHECK-NEXT:   .long   32                      # 0x20
+
+; CHECK:        .ascii  "__tt"                  # string offset=7
+; CHECK:        .ascii  "_tt"                   # string offset=12
+; CHECK:        .ascii  "s2"                    # string offset=69
+; CHECK:        .ascii  "m3"                    # string offset=72
+; CHECK:        .ascii  "tt"                    # string offset=75
+; CHECK:        .ascii  "m1"                    # string offset=78
+; CHECK:        .ascii  "m2"                    # string offset=81
+
+; Function Attrs: nounwind readnone speculatable willreturn
+declare void @llvm.dbg.value(metadata, metadata, metadata) #2
+
+attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { norecurse nounwind readonly "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind readnone speculatable willreturn }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5}
+!llvm.ident = !{!6}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 11.0.0 (https://github.com/llvm/llvm-project.git 7cfd267c518aba226b34b7fbfe8db70000b22053)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+!1 = !DIFile(filename: "t.c", directory: "/tmp/home/yhs/work/tests/btf")
+!2 = !{}
+!3 = !{i32 7, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{!"clang version 11.0.0 (https://github.com/llvm/llvm-project.git 7cfd267c518aba226b34b7fbfe8db70000b22053)"}
+!7 = distinct !DISubprogram(name: "test1", scope: !1, file: !1, line: 5, type: !8, scopeLine: 6, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !22)
+!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: "s1", file: !1, line: 4, size: 64, elements: !13)
+!13 = !{!14}
+!14 = !DIDerivedType(tag: DW_TAG_member, name: "mp", scope: !12, file: !1, line: 4, baseType: !15, size: 64)
+!15 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !16, size: 64)
+!16 = !DIDerivedType(tag: DW_TAG_typedef, name: "__tt", file: !1, line: 3, baseType: !17)
+!17 = !DIDerivedType(tag: DW_TAG_typedef, name: "_tt", file: !1, line: 2, baseType: !18)
+!18 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "tt", file: !1, line: 10, size: 64, elements: !19)
+!19 = !{!20, !21}
+!20 = !DIDerivedType(tag: DW_TAG_member, name: "m1", scope: !18, file: !1, line: 10, baseType: !10, size: 32)
+!21 = !DIDerivedType(tag: DW_TAG_member, name: "m2", scope: !18, file: !1, line: 10, baseType: !10, size: 32, offset: 32)
+!22 = !{!23}
+!23 = !DILocalVariable(name: "arg", arg: 1, scope: !7, file: !1, line: 5, type: !11)
+!24 = !DILocation(line: 0, scope: !7)
+!25 = !DILocation(line: 7, column: 3, scope: !7)
+!26 = distinct !DISubprogram(name: "test2", scope: !1, file: !1, line: 12, type: !27, scopeLine: 13, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !33)
+!27 = !DISubroutineType(types: !28)
+!28 = !{!10, !29}
+!29 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !30, size: 64)
+!30 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "s2", file: !1, line: 11, size: 64, elements: !31)
+!31 = !{!32}
+!32 = !DIDerivedType(tag: DW_TAG_member, name: "m3", scope: !30, file: !1, line: 11, baseType: !16, size: 64)
+!33 = !{!34}
+!34 = !DILocalVariable(name: "arg", arg: 1, scope: !26, file: !1, line: 12, type: !29)
+!35 = !DILocation(line: 0, scope: !26)
+!36 = !DILocation(line: 14, column: 18, scope: !26)
+!37 = !{!38, !40, i64 0}
+!38 = !{!"s2", !39, i64 0}
+!39 = !{!"tt", !40, i64 0, !40, i64 4}
+!40 = !{!"int", !41, i64 0}
+!41 = !{!"omnipotent char", !42, i64 0}
+!42 = !{!"Simple C/C++ TBAA"}
+!43 = !DILocation(line: 14, column: 3, scope: !26)