BPF: change btf_type_tag BTF output format

[yonghong-song]

Summary

For the declaration like below:

int __tag1 * __tag1 __tag2 *g

Commit 41860e602aaa ("BPF: Support btf_type_tag attribute")
implemented the following encoding:

VAR(g) -> __tag1 --> __tag2 -> pointer -> __tag1 -> pointer -> int

Some further experiments with linux btf_type_tag support, esp.
with generating attributes in vmlinux.h, and also some internal
discussion showed the following format is more desirable:

VAR(g) -> pointer -> __tag2 -> __tag1 -> pointer -> __tag1 -> int

The format makes it similar to other modifier like 'const', e.g.,

const int *g

which has encoding VAR(g) -> PTR -> CONST -> int

llvm/lib/Target/BPF/BTFDebug.h

public:
   virtual void emitType(MCStreamer &OS);
 };
 
 /// Handle several derived types include pointer, const,
 /// volatile, typedef and restrict.
 class BTFTypeDerived : public BTFTypeBase {
   const DIDerivedType *DTy;
   bool NeedsFixup;
+  StringRef Name;
 
 public:
   BTFTypeDerived(const DIDerivedType *Ty, unsigned Tag, bool NeedsFixup);
+  BTFTypeDerived(unsigned NextTypeId, unsigned Tag, StringRef Name);
   void completeType(BTFDebug &BDebug) override;
   void emitType(MCStreamer &OS) override;
   void setPointeeType(uint32_t PointeeType);
 };
 
 /// Handle struct or union forward declaration.
 class BTFTypeFwd : public BTFTypeBase {
   StringRef Name;

 public:
   BTFTypeDeclTag(uint32_t BaseTypeId, int ComponentId, StringRef Tag);
   uint32_t getSize() override { return BTFTypeBase::getSize() + 4; }
   void completeType(BTFDebug &BDebug) override;
   void emitType(MCStreamer &OS) override;
 };
 
 class BTFTypeTypeTag : public BTFTypeBase {
+  const DIDerivedType *DTy;
   StringRef Tag;
 
 public:
-  BTFTypeTypeTag(uint32_t BaseTypeId, StringRef Tag);
+  BTFTypeTypeTag(uint32_t NextTypeId, StringRef Tag);
+  BTFTypeTypeTag(const DIDerivedType *DTy, StringRef Tag);
   void completeType(BTFDebug &BDebug) override;
 };
 
 /// String table.
 class BTFStringTable {
   /// String table size in bytes.
   uint32_t Size;
   /// A mapping from string table offset to the index

llvm/lib/Target/BPF/BTFDebug.cpp

void BTFTypeBase::emitType(MCStreamer &OS) {
   OS.emitInt32(BTFType.NameOff);
   OS.AddComment("0x" + Twine::utohexstr(BTFType.Info));
   OS.emitInt32(BTFType.Info);
   OS.emitInt32(BTFType.Size);
 }
 
 BTFTypeDerived::BTFTypeDerived(const DIDerivedType *DTy, unsigned Tag,
                                bool NeedsFixup)
-    : DTy(DTy), NeedsFixup(NeedsFixup) {
+    : DTy(DTy), NeedsFixup(NeedsFixup), Name(DTy->getName()) {
   switch (Tag) {
   case dwarf::DW_TAG_pointer_type:
     Kind = BTF::BTF_KIND_PTR;
     break;
   case dwarf::DW_TAG_const_type:
     Kind = BTF::BTF_KIND_CONST;
     break;
   case dwarf::DW_TAG_volatile_type:
     Kind = BTF::BTF_KIND_VOLATILE;
     break;
   case dwarf::DW_TAG_typedef:
     Kind = BTF::BTF_KIND_TYPEDEF;
     break;
   case dwarf::DW_TAG_restrict_type:
     Kind = BTF::BTF_KIND_RESTRICT;
     break;
   default:
     llvm_unreachable("Unknown DIDerivedType Tag");
   }
   BTFType.Info = Kind << 24;
 }
 
+/// Used by DW_TAG_pointer_type only.
+BTFTypeDerived::BTFTypeDerived(unsigned NextTypeId, unsigned Tag,
+                               StringRef Name)
+    : DTy(nullptr), NeedsFixup(false), Name(Name) {
+  Kind = BTF::BTF_KIND_PTR;
+  BTFType.Info = Kind << 24;
+  BTFType.Type = NextTypeId;
+}
+
 void BTFTypeDerived::completeType(BTFDebug &BDebug) {
   if (IsCompleted)
     return;
   IsCompleted = true;
 
-  BTFType.NameOff = BDebug.addString(DTy->getName());
+  BTFType.NameOff = BDebug.addString(Name);
 
-  if (NeedsFixup)
+  if (NeedsFixup || !DTy)
     return;
 
   // The base type for PTR/CONST/VOLATILE could be void.
   const DIType *ResolvedType = DTy->getBaseType();
   if (!ResolvedType) {
     assert((Kind == BTF::BTF_KIND_PTR || Kind == BTF::BTF_KIND_CONST ||
             Kind == BTF::BTF_KIND_VOLATILE) &&
            "Invalid null basetype");
void BTFTypeDeclTag::completeType(BTFDebug &BDebug) {
   BTFType.NameOff = BDebug.addString(Tag);
 }
 
 void BTFTypeDeclTag::emitType(MCStreamer &OS) {
   BTFTypeBase::emitType(OS);
   OS.emitInt32(Info);
 }
 
-BTFTypeTypeTag::BTFTypeTypeTag(uint32_t BaseTypeId, StringRef Tag) : Tag(Tag) {
+BTFTypeTypeTag::BTFTypeTypeTag(uint32_t NextTypeId, StringRef Tag)
+    : DTy(nullptr), Tag(Tag) {
+  Kind = BTF::BTF_KIND_TYPE_TAG;
+  BTFType.Info = Kind << 24;
+  BTFType.Type = NextTypeId;
+}
+
+BTFTypeTypeTag::BTFTypeTypeTag(const DIDerivedType *DTy, StringRef Tag)
+    : DTy(DTy), Tag(Tag) {
   Kind = BTF::BTF_KIND_TYPE_TAG;
   BTFType.Info = Kind << 24;
-  BTFType.Type = BaseTypeId;
 }
 
 void BTFTypeTypeTag::completeType(BTFDebug &BDebug) {
   if (IsCompleted)
     return;
   IsCompleted = true;
   BTFType.NameOff = BDebug.addString(Tag);
+  if (DTy) {
+    const DIType *ResolvedType = DTy->getBaseType();
+    if (!ResolvedType)
+      BTFType.Type = 0;
+    else
+      BTFType.Type = BDebug.getTypeId(ResolvedType);
+  }
 }
 
 uint32_t BTFStringTable::addString(StringRef S) {
   // Check whether the string already exists.
   for (auto &OffsetM : OffsetToIdMap) {
     if (Table[OffsetM.second] == S)
       return OffsetM.first;
   }
if (Base) {
       }
     }
   }
 
   if (Tag == dwarf::DW_TAG_pointer_type) {
     SmallVector<const MDString *, 4> MDStrs;
     DINodeArray Annots = DTy->getAnnotations();
     if (Annots) {
+      // For type with "int __tag1 __tag2 *p", the MDStrs will have
+      // content: [__tag1, __tag2].
       for (const Metadata *Annotations : Annots->operands()) {
         const MDNode *MD = cast<MDNode>(Annotations);
         const MDString *Name = cast<MDString>(MD->getOperand(0));
         if (!Name->getString().equals("btf_type_tag"))
           continue;
         MDStrs.push_back(cast<MDString>(MD->getOperand(1)));
       }
     }
 
     if (MDStrs.size() > 0) {
-      auto TypeEntry = std::make_unique<BTFTypeDerived>(DTy, Tag, false);
-      unsigned TmpTypeId = addType(std::move(TypeEntry));
-      for (unsigned I = MDStrs.size(); I > 0; I--) {
-        const MDString *Value = MDStrs[I - 1];
-        if (I != 1) {
-          auto TypeEntry =
-              std::make_unique<BTFTypeTypeTag>(TmpTypeId, Value->getString());
-          TmpTypeId = addType(std::move(TypeEntry));
-        } else {
-          auto TypeEntry =
-              std::make_unique<BTFTypeTypeTag>(TmpTypeId, Value->getString());
-          TypeId = addType(std::move(TypeEntry), DTy);
-        }
+      // With MDStrs [__tag1, __tag2], the output type chain looks like
+      //   PTR -> __tag2 -> __tag1 -> BaseType
+      // In the below, we construct BTF types with the order of __tag1, __tag2
+      // and PTR.
+          std::make_unique<BTFTypeTypeTag>(DTy, MDStrs[0]->getString());
+      unsigned TmpTypeId = addType(std::move(TypeEntry));
+      for (unsigned I = 1; I < MDStrs.size(); I++) {
+        const MDString *Value = MDStrs[I];
+        TypeEntry =
       }
+      auto TypeDEntry =
+          std::make_unique<BTFTypeDerived>(TmpTypeId, Tag, DTy->getName());
+      TypeId = addType(std::move(TypeDEntry), DTy);
     } else {
       auto TypeEntry = std::make_unique<BTFTypeDerived>(DTy, Tag, false);
       TypeId = addType(std::move(TypeEntry), DTy);
     }
   } else if (Tag == dwarf::DW_TAG_typedef || Tag == dwarf::DW_TAG_const_type ||
              Tag == dwarf::DW_TAG_volatile_type ||
              Tag == dwarf::DW_TAG_restrict_type) {
     auto TypeEntry = std::make_unique<BTFTypeDerived>(DTy, Tag, false);

llvm/test/CodeGen/BPF/BTF/type-tag-var.ll

 !5 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !6, size: 64, annotations: !10)
 !6 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !7, size: 64, annotations: !8)
 !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 !8 = !{!9}
 !9 = !{!"btf_type_tag", !"tag1"}
 !10 = !{!9, !11}
 !11 = !{!"btf_type_tag", !"tag2"}
 
-; CHECK:             .long   0                               # BTF_KIND_PTR(id = 1)
-; CHECK-NEXT:        .long   33554432                        # 0x2000000
+; CHECK:             .long   1                               # BTF_KIND_TYPE_TAG(id = 1)
+; CHECK-NEXT:        .long   301989888                       # 0x12000000
 ; CHECK-NEXT:        .long   5
-; CHECK-NEXT:        .long   1                               # BTF_KIND_TYPE_TAG(id = 2)
+; CHECK-NEXT:        .long   6                               # BTF_KIND_TYPE_TAG(id = 2)
 ; CHECK-NEXT:        .long   301989888                       # 0x12000000
 ; CHECK-NEXT:        .long   1
-; CHECK-NEXT:        .long   6                               # BTF_KIND_TYPE_TAG(id = 3)
-; CHECK-NEXT:        .long   301989888                       # 0x12000000
-; CHECK-NEXT:        .long   2
-; CHECK-NEXT:        .long   0                               # BTF_KIND_PTR(id = 4)
+; CHECK-NEXT:        .long   0                               # BTF_KIND_PTR(id = 3)
 ; CHECK-NEXT:        .long   33554432                        # 0x2000000
-; CHECK-NEXT:        .long   6
-; CHECK-NEXT:        .long   6                               # BTF_KIND_TYPE_TAG(id = 5)
+; CHECK-NEXT:        .long   2
+; CHECK-NEXT:        .long   1                               # BTF_KIND_TYPE_TAG(id = 4)
 ; CHECK-NEXT:        .long   301989888                       # 0x12000000
+; CHECK-NEXT:        .long   6
+; CHECK-NEXT:        .long   0                               # BTF_KIND_PTR(id = 5)
+; CHECK-NEXT:        .long   33554432                        # 0x2000000
 ; CHECK-NEXT:        .long   4
 ; CHECK-NEXT:        .long   11                              # BTF_KIND_INT(id = 6)
 ; CHECK-NEXT:        .long   16777216                        # 0x1000000
 ; CHECK-NEXT:        .long   4
 ; CHECK-NEXT:        .long   16777248                        # 0x1000020
 ; CHECK-NEXT:        .long   15                              # BTF_KIND_VAR(id = 7)
 ; CHECK-NEXT:        .long   234881024                       # 0xe000000
 ; CHECK-NEXT:        .long   3
 ; CHECK-NEXT:        .long   1
 
-; CHECK:             .ascii  "tag2"                          # string offset=1
-; CHECK:             .ascii  "tag1"                          # string offset=6
+; CHECK:             .ascii  "tag1"                          # string offset=1
+; CHECK:             .ascii  "tag2"                          # string offset=6
 ; CHECK:             .ascii  "int"                           # string offset=11
 ; CHECK:             .byte   103                             # string offset=15
 
 !12 = !{i32 7, !"Dwarf Version", i32 4}
 !13 = !{i32 2, !"Debug Info Version", i32 3}
 !14 = !{i32 1, !"wchar_size", i32 4}
 !15 = !{i32 7, !"frame-pointer", i32 2}
 !16 = !{!"clang version 14.0.0 (https://github.com/llvm/llvm-project.git 077b2e0cf1e97c4d97ca5ceab3ec0192ed11c66e)"}