diff --git a/llvm/include/llvm/Object/ELF.h b/llvm/include/llvm/Object/ELF.h
--- a/llvm/include/llvm/Object/ELF.h
+++ b/llvm/include/llvm/Object/ELF.h
@@ -14,6 +14,7 @@
 #define LLVM_OBJECT_ELF_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
@@ -391,9 +392,22 @@
   Expected<ArrayRef<T>> getSectionContentsAsArray(const Elf_Shdr &Sec) const;
   Expected<ArrayRef<uint8_t>> getSectionContents(const Elf_Shdr &Sec) const;
   Expected<ArrayRef<uint8_t>> getSegmentContents(const Elf_Phdr &Phdr) const;
-  Expected<std::vector<BBAddrMap>> decodeBBAddrMap(const Elf_Shdr &Sec) const;
+
+  Expected<std::vector<BBAddrMap>>
+  decodeBBAddrMap(const Elf_Shdr &Sec, std::optional<Elf_Shdr> RelaSec = {}) const;
+  Expected<llvm::MapVector<const Elf_Shdr *, const Elf_Shdr *>>
+  getBBAddrMapSections(std::optional<unsigned> TextSectionIndex = {}) const;
+  Expected<llvm::MapVector<const Elf_Shdr *, const Elf_Shdr *>>
+  getBBAddrMapAndRelaSections(
+      std::optional<unsigned> TextSectionIndex = {}) const;
 
   void createFakeSections();
+
+private:
+  Expected<bool>
+  shouldSkipBasedOnTextSection(std::optional<unsigned> TextSectionIndex,
+                               const typename ELFT::Shdr &CurrentSection) const;
+  Expected<llvm::DenseMap<uint64_t, uint64_t>> getBBAddrMapTranslations(const Elf_Shdr &RelaSec) const;
 };
 
 using ELF32LEFile = ELFFile<ELF32LE>;
diff --git a/llvm/lib/Object/ELF.cpp b/llvm/lib/Object/ELF.cpp
--- a/llvm/lib/Object/ELF.cpp
+++ b/llvm/lib/Object/ELF.cpp
@@ -639,8 +639,114 @@
 }
 
 template <class ELFT>
-Expected<std::vector<BBAddrMap>>
-ELFFile<ELFT>::decodeBBAddrMap(const Elf_Shdr &Sec) const {
+Expected<bool> ELFFile<ELFT>::shouldSkipBasedOnTextSection(
+    std::optional<unsigned> TextSectionIndex,
+    const typename ELFT::Shdr &CurrentSection) const {
+  if(!TextSectionIndex) {
+    return false;
+  }
+  const auto &Sections = cantFail(this->sections());
+  Expected<const Elf_Shdr *> TextSecOrErr =
+      this->getSection(CurrentSection.sh_link);
+  if (!TextSecOrErr)
+    return createError("unable to get the linked-to section for " +
+                       describe(*this, CurrentSection) + ": " +
+                       toString(TextSecOrErr.takeError()));
+  if (*TextSectionIndex != std::distance(Sections.begin(), *TextSecOrErr)) {
+    return true;
+  }
+  return false;
+}
+
+template <class ELFT>
+Expected<
+    llvm::MapVector<const typename ELFT::Shdr *, const typename ELFT::Shdr *>>
+ELFFile<ELFT>::getBBAddrMapSections(
+    std::optional<unsigned> TextSectionIndex) const {
+  using Elf_Shdr = typename ELFT::Shdr;
+  llvm::MapVector<const Elf_Shdr *, const Elf_Shdr *> BBAddrMapSections;
+  const auto &Sections = cantFail(this->sections());
+  for (const Elf_Shdr &Sec : Sections) {
+    if (Sec.sh_type != ELF::SHT_LLVM_BB_ADDR_MAP &&
+        Sec.sh_type != ELF::SHT_LLVM_BB_ADDR_MAP_V0)
+      continue;
+    auto TextSectionSkip = shouldSkipBasedOnTextSection(TextSectionIndex, Sec);
+    if(!TextSectionSkip) {
+      return TextSectionSkip.takeError();
+    }
+    if(*TextSectionSkip) {
+      continue;
+    }
+    BBAddrMapSections[&Sec] = (const Elf_Shdr *)nullptr;
+  }
+  return BBAddrMapSections;
+}
+
+template <class ELFT>
+Expected<
+    llvm::MapVector<const typename ELFT::Shdr *, const typename ELFT::Shdr *>>
+ELFFile<ELFT>::getBBAddrMapAndRelaSections(
+    std::optional<unsigned> TextSectionIndex) const {
+  using Elf_Shdr = typename ELFT::Shdr;
+  const auto &Sections = cantFail(sections());
+  llvm::MapVector<const Elf_Shdr *, const Elf_Shdr *> BBAddrMapSecsRelasMap;
+  for (const Elf_Shdr &Sec : Sections) {
+    if (Sec.sh_type != ELF::SHT_RELA) {
+      continue;
+    }
+    Expected<const Elf_Shdr *> BBAddrMapSectionOrErr = getSection(Sec.sh_info);
+    if (!BBAddrMapSectionOrErr) {
+      return createError(
+          "Failed to read section linked to from section sh_info");
+    }
+    const Elf_Shdr *PossibleBBAddrMapSection = *BBAddrMapSectionOrErr;
+    if (PossibleBBAddrMapSection->sh_type != ELF::SHT_LLVM_BB_ADDR_MAP &&
+        PossibleBBAddrMapSection->sh_type != ELF::SHT_LLVM_BB_ADDR_MAP_V0) {
+      continue;
+    }
+    // we know we have a BBAddrMapSection with the associated rela section
+    auto TextSectionSkip = shouldSkipBasedOnTextSection(TextSectionIndex, *PossibleBBAddrMapSection);
+    if(!TextSectionSkip) {
+      return TextSectionSkip.takeError();
+    }
+    if(*TextSectionSkip) {
+      continue;
+    }
+    BBAddrMapSecsRelasMap[PossibleBBAddrMapSection] = &Sec;
+  }
+  return BBAddrMapSecsRelasMap;
+}
+
+template <class ELFT>
+Expected<llvm::DenseMap<uint64_t, uint64_t>>
+ELFFile<ELFT>::getBBAddrMapTranslations(const Elf_Shdr &RelaSec) const {
+  llvm::DenseMap<uint64_t, uint64_t> AddrTranslationMap;
+  auto Relas = this->relas(RelaSec);
+  if (!Relas) {
+    return Relas.takeError();
+  }
+  for (auto Rela : *Relas) {
+    AddrTranslationMap[Rela.r_offset] = Rela.r_addend;
+  }
+  return AddrTranslationMap;
+}
+
+template <class ELFT>
+Expected<std::vector<BBAddrMap>> ELFFile<ELFT>::decodeBBAddrMap(
+    const Elf_Shdr &Sec, const std::optional<Elf_Shdr> RelaSec) const {
+  bool IsRelocatable = getHeader().e_type == ELF::ET_REL;
+  if (IsRelocatable && !RelaSec) {
+    return createError("decodeBBAddrMap called in a relocatable file with no "
+                       "relocation section");
+  }
+  llvm::DenseMap<uint64_t, uint64_t> BBAddrMapTranslations;
+  if(IsRelocatable) {
+    auto TranslationsOrErr = getBBAddrMapTranslations(*RelaSec);
+    if(!TranslationsOrErr) {
+      return TranslationsOrErr.takeError();
+    }
+    BBAddrMapTranslations = *TranslationsOrErr;
+  }
   Expected<ArrayRef<uint8_t>> ContentsOrErr = getSectionContents(Sec);
   if (!ContentsOrErr)
     return ContentsOrErr.takeError();
@@ -680,7 +786,13 @@
                            Twine(static_cast<int>(Version)));
       Data.getU8(Cur); // Feature byte
     }
-    uintX_t Address = static_cast<uintX_t>(Data.getAddress(Cur));
+    uintX_t Address;
+    if(IsRelocatable) {
+      Address = BBAddrMapTranslations[Cur.tell()];
+      Cur.seek(Cur.tell() + sizeof(uintX_t));
+    } else {
+      Address = static_cast<uintX_t>(Data.getAddress(Cur));
+    }
     uint32_t NumBlocks = ReadULEB128AsUInt32();
     std::vector<BBAddrMap::BBEntry> BBEntries;
     uint32_t PrevBBEndOffset = 0;
diff --git a/llvm/lib/Object/ELFObjectFile.cpp b/llvm/lib/Object/ELFObjectFile.cpp
--- a/llvm/lib/Object/ELFObjectFile.cpp
+++ b/llvm/lib/Object/ELFObjectFile.cpp
@@ -681,24 +681,30 @@
 Expected<std::vector<BBAddrMap>> static readBBAddrMapImpl(
     const ELFFile<ELFT> &EF, std::optional<unsigned> TextSectionIndex) {
   using Elf_Shdr = typename ELFT::Shdr;
+  bool IsRelocatable = EF.getHeader().e_type == ELF::ET_REL;
   std::vector<BBAddrMap> BBAddrMaps;
-  const auto &Sections = cantFail(EF.sections());
-  for (const Elf_Shdr &Sec : Sections) {
-    if (Sec.sh_type != ELF::SHT_LLVM_BB_ADDR_MAP &&
-        Sec.sh_type != ELF::SHT_LLVM_BB_ADDR_MAP_V0)
-      continue;
-    if (TextSectionIndex) {
-      Expected<const Elf_Shdr *> TextSecOrErr = EF.getSection(Sec.sh_link);
-      if (!TextSecOrErr)
-        return createError("unable to get the linked-to section for " +
-                           describe(EF, Sec) + ": " +
-                           toString(TextSecOrErr.takeError()));
-      if (*TextSectionIndex != std::distance(Sections.begin(), *TextSecOrErr))
-        continue;
+  llvm::MapVector<const Elf_Shdr*, const Elf_Shdr *> Sections;
+  if(IsRelocatable) {
+    auto SecsOrErr = EF.getBBAddrMapAndRelaSections(TextSectionIndex);
+    if(!SecsOrErr) {
+      return SecsOrErr.takeError();
+    }
+    Sections = *SecsOrErr;
+  } else {
+    auto SecsOrErr = EF.getBBAddrMapSections(TextSectionIndex);
+    if(!SecsOrErr) {
+      return SecsOrErr.takeError();
+    }
+    Sections = *SecsOrErr;
+  }
+  for (auto const& [Sec, RelocSec] : Sections) {
+    std::optional<Elf_Shdr> RelaSec = {};
+    if(IsRelocatable) {
+      RelaSec = *RelocSec;
     }
-    Expected<std::vector<BBAddrMap>> BBAddrMapOrErr = EF.decodeBBAddrMap(Sec);
+    Expected<std::vector<BBAddrMap>> BBAddrMapOrErr = EF.decodeBBAddrMap(*Sec, RelaSec);
     if (!BBAddrMapOrErr)
-      return createError("unable to read " + describe(EF, Sec) + ": " +
+      return createError("unable to read " + describe(EF, *Sec) + ": " +
                          toString(BBAddrMapOrErr.takeError()));
     std::move(BBAddrMapOrErr->begin(), BBAddrMapOrErr->end(),
               std::back_inserter(BBAddrMaps));
diff --git a/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml b/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml
--- a/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml
+++ b/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml
@@ -5,19 +5,12 @@
 # UNSUPPORTED: system-windows
 
 ## Executable object file.
-# RUN: yaml2obj --docnum=1 -DTYPE=ET_EXEC -DFOO_ADDR=0x4000 -DBAR_ADDR=0x5000 %s -o %t1
+# RUN: yaml2obj --docnum=1 -DFOO_ADDR=0x4000 -DBAR_ADDR=0x5000 %s -o %t1
 # RUN: llvm-objdump %t1 -d --symbolize-operands -M intel --no-show-raw-insn --no-leading-addr | \
 # RUN:   FileCheck %s -DSYM=symbol --match-full-lines --check-prefixes=INTEL
 # RUN: llvm-objdump %t1 -d --symbolize-operands -M att --no-show-raw-insn --no-leading-addr | \
 # RUN:   FileCheck %s -DSYM=symbol --match-full-lines --check-prefixes=ATT
 
-## Relocatable object file.
-# RUN: yaml2obj --docnum=1 -DTYPE=ET_REL -DFOO_ADDR=0x0 -DBAR_ADDR=0x0 %s -o %t2
-# RUN: llvm-objdump %t2 -d --symbolize-operands -M intel --no-show-raw-insn --no-leading-addr | \
-# RUN:   FileCheck %s -DSYM=foo+0x200c --match-full-lines --check-prefix=INTEL
-# RUN: llvm-objdump %t2 -d --symbolize-operands -M att --no-show-raw-insn --no-leading-addr | \
-# RUN:   FileCheck %s -DSYM=foo+0x200c --match-full-lines --check-prefix=ATT
-
 ## Executable object file with a single SHT_LLVM_BB_ADDR_MAP for multiple text sections.
 # RUN: yaml2obj --docnum=2 %s -o %t3
 # RUN: llvm-objdump %t3 -d --symbolize-operands -M intel --no-show-raw-insn --no-leading-addr | \
@@ -78,7 +71,7 @@
 FileHeader:
   Class:   ELFCLASS64
   Data:    ELFDATA2LSB
-  Type:    [[TYPE]]
+  Type:    ET_EXEC
   Machine: EM_X86_64
 Sections:
   - Name:    .text.foo
diff --git a/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-symbolize-relocatable.yaml b/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-symbolize-relocatable.yaml
new file mode 100644
--- /dev/null
+++ b/llvm/test/tools/llvm-objdump/X86/elf-bbaddrmap-symbolize-relocatable.yaml
@@ -0,0 +1,136 @@
+## Test that in the presence of SHT_LLVM_BB_ADDR_MAP sections,
+## --symbolize-operands can display <BB*> labels properly in a relocatable
+## object file.
+
+# UNSUPPORTED: system-windows
+
+## Relocatable Object file.
+# RUN: yaml2obj %s -o %t1
+# RUN: llvm-objdump %t1 -d --symbolize-operands -M intel --no-show-raw-insn --no-leading-addr | \
+# RUN:   FileCheck %s -DSYM=symbol --match-full-lines --check-prefixes=INTEL
+# RUN: llvm-objdump %t1 -d --symbolize-operands -M att --no-show-raw-insn --no-leading-addr | \
+# RUN:   FileCheck %s -DSYM=symbol --match-full-lines --check-prefixes=ATT
+
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_X86_64
+  SectionHeaderStringTable: .strtab
+Sections:
+  - Name:    .text
+    Type:    SHT_PROGBITS
+    Flags:   [ SHF_ALLOC, SHF_EXECINSTR ]
+    Content: 554889E5897DFC8B45FCC1E0015DC390554889E5897DF8837DF8050F8E0E0000008B45F883E8058945FCE9060000008B45F88945FC8B45FC5DC3
+  - Name:    .llvm_bb_addr_map
+    Type:    SHT_LLVM_BB_ADDR_MAP
+    Link:    .text
+    Entries:
+      - Version: 2
+        BBEntries:
+          - ID:              0
+            AddressOffset:   0x0
+            Size:            0xF
+            Metadata:        0x1
+      - Version: 2
+        BBEntries:
+          - ID:              0
+            AddressOffset:   0x0
+            Size:            0x11
+            Metadata:        0x8
+          - ID:              1
+            AddressOffset:   0x0
+            Size:            0xE
+            Metadata:        0x0
+          - ID:              2
+            AddressOffset:   0x0
+            Size:            0x6
+            Metadata:        0x8
+          - ID:              3
+            AddressOffset:   0x0
+            Size:            0x5
+            Metadata:        0x1
+  - Name:  .rela.llvm_bb_addr_map
+    Type:  SHT_RELA
+    Flags: [ SHF_INFO_LINK ]
+    Link:  .symtab
+    Info:  .llvm_bb_addr_map
+    Relocations:
+      - Offset: 0x2
+        Symbol: .text
+        Type:   R_X86_64_64
+      - Offset: 0x11
+        Symbol: .text
+        Type:   R_X86_64_64
+        Addend: 16
+Symbols:
+  - Name:    a
+    Section: .text
+    Value:   0x0
+  - Name:    c
+    Section: .text
+    Value:   0x10
+  - Name:    .text
+    Type:    STT_SECTION
+    Section: .text
+
+# ATT:      <a>:
+# ATT-NEXT: <BB0>:
+# ATT-NEXT:   pushq   %rbp
+# ATT-NEXT:   movq    %rsp, %rbp
+# ATT-NEXT:   movl    %edi, -0x4(%rbp)
+# ATT-NEXT:   movl    -0x4(%rbp), %eax
+# ATT-NEXT:   shll    $0x1, %eax
+# ATT-NEXT:   popq    %rbp
+# ATT-NEXT:   retq
+# ATT-NEXT:   nop
+# ATT:      <c>:
+# ATT-NEXT: <BB0>:
+# ATT-NEXT:   pushq   %rbp
+# ATT-NEXT:   movq    %rsp, %rbp
+# ATT-NEXT:   movl    %edi, -0x8(%rbp)
+# ATT-NEXT:   cmpl    $0x5, -0x8(%rbp)
+# ATT-NEXT:   jle      <BB2>
+# ATT-NEXT: <BB1>:
+# ATT-NEXT:   movl    -0x8(%rbp), %eax
+# ATT-NEXT:   subl    $0x5, %eax
+# ATT-NEXT:   movl    %eax, -0x4(%rbp)
+# ATT-NEXT:   jmp      <BB3>
+# ATT-NEXT: <BB2>:
+# ATT-NEXT:   movl    -0x8(%rbp), %eax
+# ATT-NEXT:   movl    %eax, -0x4(%rbp)
+# ATT-NEXT: <BB3>:
+# ATT-NEXT:   movl    -0x4(%rbp), %eax
+# ATT-NEXT:   popq    %rbp
+# ATT-NEXT:   retq
+
+# INTEL:      <a>:
+# INTEL-NEXT: <BB0>:
+# INTEL-NEXT:   push    rbp
+# INTEL-NEXT:   mov     rbp, rsp
+# INTEL-NEXT:   mov     dword ptr [rbp - 0x4], edi
+# INTEL-NEXT:   mov     eax, dword ptr [rbp - 0x4]
+# INTEL-NEXT:   shl     eax, 0x1
+# INTEL-NEXT:   pop     rbp
+# INTEL-NEXT:   ret
+# INTEL-NEXT:   nop
+# INTEL:      <c>:
+# INTEL-NEXT: <BB0>:
+# INTEL-NEXT:   push    rbp
+# INTEL-NEXT:   mov     rbp, rsp
+# INTEL-NEXT:   mov     dword ptr [rbp - 0x8], edi
+# INTEL-NEXT:   cmp     dword ptr [rbp - 0x8], 0x5
+# INTEL-NEXT:   jle      <BB2>
+# INTEL-NEXT: <BB1>:
+# INTEL-NEXT:   mov     eax, dword ptr [rbp - 0x8]
+# INTEL-NEXT:   sub     eax, 0x5
+# INTEL-NEXT:   mov     dword ptr [rbp - 0x4], eax
+# INTEL-NEXT:   jmp      <BB3>
+# INTEL-NEXT: <BB2>:
+# INTEL-NEXT:   mov     eax, dword ptr [rbp - 0x8]
+# INTEL-NEXT:   mov     dword ptr [rbp - 0x4], eax
+# INTEL-NEXT: <BB3>:
+# INTEL-NEXT:   mov     eax, dword ptr [rbp - 0x4]
+# INTEL-NEXT:   pop     rbp
+# INTEL-NEXT:   ret
diff --git a/llvm/test/tools/llvm-readobj/ELF/bb-addr-map-relocatable.test b/llvm/test/tools/llvm-readobj/ELF/bb-addr-map-relocatable.test
new file mode 100644
--- /dev/null
+++ b/llvm/test/tools/llvm-readobj/ELF/bb-addr-map-relocatable.test
@@ -0,0 +1,131 @@
+## This test checks how we handle the --bb-addr-map option on relocatable
+## object files.
+
+## UNSUPPORTED: system-windows
+
+# RUN: yaml2obj %s -o %t1.o
+# RUN: llvm-readobj %t1.o --bb-addr-map | FileCheck %s
+
+# CHECK:      BBAddrMap [
+# CHECK-NEXT:   Function {
+# CHECK-NEXT:     At: 0x0
+# CHECK-NEXT:     Name: <?>
+# CHECK-NEXT:     BB entries [
+# CHECK-NEXT:       {
+# CHECK-NEXT:         ID: 0
+# CHECK-NEXT:         Offset: 0x0
+# CHECK-NEXT:         Size: 0xF
+# CHECK-NEXT:         HasReturn: Yes
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: No
+# CHECK-NEXT:       }
+# CHECK-NEXT:     ]
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Function {
+# CHECK-NEXT:     At: 0x10
+# CHECK-NEXT:     Name: <?>
+# CHECK-NEXT:     BB entries [
+# CHECK-NEXT:       {
+# CHECK-NEXT:         ID: 0
+# CHECK-NEXT:         Offset: 0x0
+# CHECK-NEXT:         Size: 0x11
+# CHECK-NEXT:         HasReturn: No
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: Yes
+# CHECK-NEXT:       }
+# CHECK-NEXT:       {
+# CHECK-NEXT:         ID: 1
+# CHECK-NEXT:         Offset: 0x11
+# CHECK-NEXT:         Size: 0xE
+# CHECK-NEXT:         HasReturn: No
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: No
+# CHECK-NEXT:       }
+# CHECK-NEXT:       {
+# CHECK-NEXT:         ID: 2
+# CHECK-NEXT:         Offset: 0x1F
+# CHECK-NEXT:         Size: 0x6
+# CHECK-NEXT:         HasReturn: No
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: Yes
+# CHECK-NEXT:       }
+# CHECK-NEXT:       {
+# CHECK-NEXT:         ID: 3
+# CHECK-NEXT:         Offset: 0x25
+# CHECK-NEXT:         Size: 0x5
+# CHECK-NEXT:         HasReturn: Yes
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: No
+# CHECK-NEXT:       }
+# CHECK-NEXT:     ]
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_X86_64
+  SectionHeaderStringTable: .strtab
+Sections:
+  - Name:    .text
+    Type:    SHT_PROGBITS
+    Flags:   [ SHF_ALLOC, SHF_EXECINSTR ]
+    Content: 554889E5897DFC8B45FCC1E0015DC390554889E5897DF8837DF8050F8E0E0000008B45F883E8058945FCE9060000008B45F88945FC8B45FC5DC3
+  - Name:    .llvm_bb_addr_map
+    Type:    SHT_LLVM_BB_ADDR_MAP
+    Link:    .text
+    Entries:
+      - Version: 2
+        BBEntries:
+          - ID:              0
+            AddressOffset:   0x0
+            Size:            0xF
+            Metadata:        0x1
+      - Version: 2
+        BBEntries:
+          - ID:              0
+            AddressOffset:   0x0
+            Size:            0x11
+            Metadata:        0x8
+          - ID:              1
+            AddressOffset:   0x0
+            Size:            0xE
+            Metadata:        0x0
+          - ID:              2
+            AddressOffset:   0x0
+            Size:            0x6
+            Metadata:        0x8
+          - ID:              3
+            AddressOffset:   0x0
+            Size:            0x5
+            Metadata:        0x1
+  - Name:  .rela.llvm_bb_addr_map
+    Type:  SHT_RELA
+    Flags: [ SHF_INFO_LINK ]
+    Link:  .symtab
+    Info:  .llvm_bb_addr_map
+    Relocations:
+      - Offset: 0x2
+        Symbol: .text
+        Type:   R_X86_64_64
+      - Offset: 0x11
+        Symbol: .text
+        Type:   R_X86_64_64
+        Addend: 16
+Symbols:
+  - Name:    a
+    Section: .text
+    Value:   0x0
+  - Name:    c
+    Section: .text
+    Value:   0x10
+  - Name:    .text
+    Type:    STT_SECTION
+    Section: .text
diff --git a/llvm/tools/llvm-readobj/ELFDumper.cpp b/llvm/tools/llvm-readobj/ELFDumper.cpp
--- a/llvm/tools/llvm-readobj/ELFDumper.cpp
+++ b/llvm/tools/llvm-readobj/ELFDumper.cpp
@@ -7109,20 +7109,35 @@
 
 template <class ELFT> void LLVMELFDumper<ELFT>::printBBAddrMaps() {
   bool IsRelocatable = this->Obj.getHeader().e_type == ELF::ET_REL;
-  for (const Elf_Shdr &Sec : cantFail(this->Obj.sections())) {
-    if (Sec.sh_type != SHT_LLVM_BB_ADDR_MAP &&
-        Sec.sh_type != SHT_LLVM_BB_ADDR_MAP_V0) {
-      continue;
+  using Elf_Shdr = typename ELFT::Shdr;
+  llvm::MapVector<const Elf_Shdr*, const Elf_Shdr*> Sections;
+  if(IsRelocatable) {
+    auto SecsOrErr = this->Obj.getBBAddrMapAndRelaSections();
+    if(!SecsOrErr) {
+      this->reportUniqueWarning("Cannot get section");
+    }
+    Sections = *SecsOrErr;
+  } else {
+    auto SecsOrErr = this->Obj.getBBAddrMapSections();
+    if(!SecsOrErr) {
+      this->reportUniqueWarning("Cannot get section");
     }
+    Sections = *SecsOrErr;
+  }
+  for (auto const& [Sec, RelocSec] : Sections) {
     std::optional<const Elf_Shdr *> FunctionSec;
     if (IsRelocatable)
       FunctionSec =
-          unwrapOrError(this->FileName, this->Obj.getSection(Sec.sh_link));
+          unwrapOrError(this->FileName, this->Obj.getSection(Sec->sh_link));
     ListScope L(W, "BBAddrMap");
+    std::optional<Elf_Shdr> RelaSec = {};
+    if(IsRelocatable) {
+      RelaSec = *RelocSec;
+    }
     Expected<std::vector<BBAddrMap>> BBAddrMapOrErr =
-        this->Obj.decodeBBAddrMap(Sec);
+        this->Obj.decodeBBAddrMap(*Sec, RelaSec);
     if (!BBAddrMapOrErr) {
-      this->reportUniqueWarning("unable to dump " + this->describe(Sec) + ": " +
+      this->reportUniqueWarning("unable to dump " + this->describe(*Sec) + ": " +
                                 toString(BBAddrMapOrErr.takeError()));
       continue;
     }
@@ -7135,7 +7150,7 @@
       if (FuncSymIndex.empty())
         this->reportUniqueWarning(
             "could not identify function symbol for address (0x" +
-            Twine::utohexstr(AM.Addr) + ") in " + this->describe(Sec));
+            Twine::utohexstr(AM.Addr) + ") in " + this->describe(*Sec));
       else
         FuncName = this->getStaticSymbolName(FuncSymIndex.front());
       W.printString("Name", FuncName);