[llvm-readobj] Print function names with `--bb-addr-map`.

[rahmanl]

Summary

This patch uses the getSymbolIndexForFunctionAddress helper function to print function names for BB address map entries.

[rahmanl]

Rename and refactoring.

[tmsriram]

The quadratic behavior leading to a 10 minute latency is too much. Binary search like you mentioned or just hash look up seems like it would drastically reduce the problem, could we bake it in the same change?

[rahmanl]

In D102900#2775213, @tmsriram wrote:

The quadratic behavior leading to a 10 minute latency is too much. Binary search like you mentioned or just hash look up seems like it would drastically reduce the problem, could we bake it in the same change?

Sure. I'll revise.

[snehasish]

Agree with tmsriram@ the quadratic behaviour needs to be addressed, though I think we should split it out as a separate change which can be committed first. That would make it easier for folks to review independently. Thanks!

[rahmanl]

• Reimplement symbol index lookup using a hash map. This reduces the 10 minute running time to only 3 seconds.

[rahmanl]

• Fix the map value type.

[rahmanl]

In D102900#2777530, @snehasish wrote:

Agree with tmsriram@ the quadratic behaviour needs to be addressed, though I think we should split it out as a separate change which can be committed first. That would make it easier for folks to review independently. Thanks!

Ah. Got it. You want to submit the optimization patch before the feature patch. Makes sense.

[rahmanl]

• Rebase after landing D103072.

[jhenderson]

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test

21

I think you need to check the warning in this case too?

llvm/tools/llvm-readobj/ELFDumper.cpp

6747

Elsewhere, we usually use <?> to indicate unknown names. Probably best to be consistent here.

[rahmanl]

Check the warning.

[rahmanl]

Remove unwanted duplicate variable definition.

[jhenderson]

LGTM, thanks!

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test

 ## This test checks how we handle the --bb-addr-map option.
 
-## Check 64-bit:
-# RUN: yaml2obj %s -DBITS=64 -DADDR=0xFFFFFFFF1 -o %t1.x64.o
-# RUN: llvm-readobj %t1.x64.o --bb-addr-map | FileCheck %s -DADDR=0xFFFFFFFF1 --check-prefix=LLVM
+# Check 64-bit:
+# RUN: yaml2obj %s -DBITS=64 -DADDR=0x999999999 -o %t1.x64.o
+# RUN: llvm-readobj %t1.x64.o --bb-addr-map 2>&1 | FileCheck %s -DADDR=0x999999999 -DFILE=%t1.x64.o --check-prefix=LLVM
+
 # RUN: llvm-readelf %t1.x64.o --bb-addr-map | FileCheck %s --check-prefix=GNU
 
 ## Check 32-bit:
 # RUN: yaml2obj %s -DBITS=32 -o %t1.x32.o
-# RUN: llvm-readobj %t1.x32.o --bb-addr-map | FileCheck -DADDR=0x11111 %s --check-prefix=LLVM
+# RUN: llvm-readobj %t1.x32.o --bb-addr-map 2>&1 | FileCheck -DADDR=0x11111 %s -DFILE=%t1.x32.o --check-prefix=LLVM
 # RUN: llvm-readelf %t1.x32.o --bb-addr-map | FileCheck %s --check-prefix=GNU
 
 ## Check that a malformed section can be handled.
 # RUN: yaml2obj %s -DBITS=32 -DSIZE=4 -o %t2.o
 # RUN: llvm-readobj %t2.o --bb-addr-map 2>&1 | FileCheck %s -DOFFSET=0x00000004 -DFILE=%t2.o --check-prefix=TRUNCATED
 
 # LLVM:      BBAddrMap [
 # LLVM-NEXT:   Function {
 # LLVM-NEXT:     At: [[ADDR]]
+# LLVM-NEXT: warning: '[[FILE]]': could not identify function symbol for address ([[ADDR]]) in SHT_LLVM_BB_ADDR_MAP section with index 3
+# LLVM-NEXT:     Name: <?>
 # LLVM-NEXT:     BB entries [
 # LLVM-NEXT:       {
 # LLVM-NEXT:         Offset: 0x0
 # LLVM-NEXT:         Size: 0x1
 # LLVM-NEXT:         HasReturn: No
 # LLVM-NEXT:         HasTailCall: Yes
 # LLVM-NEXT:         IsEHPad: No
 # LLVM-NEXT:         CanFallThrough: No
 # LLVM-NEXT:       }
 # LLVM-NEXT:       {
 # LLVM-NEXT:         Offset: 0x3
 # LLVM-NEXT:         Size: 0x4
 # LLVM-NEXT:         HasReturn: Yes
 # LLVM-NEXT:         HasTailCall: No
 # LLVM-NEXT:         IsEHPad: Yes
 # LLVM-NEXT:         CanFallThrough: No
 # LLVM-NEXT:       }
 # LLVM-NEXT:     ]
 # LLVM-NEXT:   }
 # LLVM-NEXT:   Function {
 # LLVM-NEXT:     At: 0x22222
+# LLVM-NEXT:     Name: foo
 # LLVM-NEXT:     BB entries [
 # LLVM-NEXT:       {
 # LLVM-NEXT:         Offset: 0x6
 # LLVM-NEXT:         Size: 0x7
 # LLVM-NEXT:         HasReturn: No
 # LLVM-NEXT:         HasTailCall: No
 # LLVM-NEXT:         IsEHPad: No
 # LLVM-NEXT:         CanFallThrough: Yes
 # LLVM-NEXT:       }
 # LLVM-NEXT:     ]
 # LLVM-NEXT:   }
 # LLVM-NEXT: ]
 # LLVM-NEXT: BBAddrMap [
 # LLVM-NEXT:   Function {
 # LLVM-NEXT:     At: 0x33333
+# LLVM-NEXT:     Name: bar
 # LLVM-NEXT:     BB entries [
 # LLVM-NEXT:       {
 # LLVM-NEXT:         Offset: 0x9
 # LLVM-NEXT:         Size: 0xA
 # LLVM-NEXT:         HasReturn: Yes
 # LLVM-NEXT:         HasTailCall: Yes
 # LLVM-NEXT:         IsEHPad: No
 # LLVM-NEXT:         CanFallThrough: Yes
 # LLVM-NEXT:       }
 # LLVM-NEXT:     ]
 # LLVM-NEXT:   }
 # LLVM-NEXT: ]
 
 # GNU: GNUStyle::printBBAddrMaps not implemented
 
 # TRUNCATED:      BBAddrMap [
-# TRUNCATED-NEXT:   warning: '[[FILE]]': unable to dump SHT_LLVM_BB_ADDR_MAP section with index 1: unable to decode LEB128 at offset [[OFFSET]]: malformed uleb128, extends past end
+# TRUNCATED-NEXT:   warning: '[[FILE]]': unable to dump SHT_LLVM_BB_ADDR_MAP section with index 3: unable to decode LEB128 at offset [[OFFSET]]: malformed uleb128, extends past end
 # TRUNCATED-NEXT: ]
 ## Check that the other valid section is properly dumped.
 # TRUNCATED-NEXT: BBAddrMap [
 # TRUNCATED-NEXT:   Function {
-# TRUNCATED-NEXT:          At: 0x33333
-# TRUNCATED-NEXT:          BB entries [
-# TRUNCATED-NEXT:            {
+# TRUNCATED-NEXT:     At: 0x33333
+# TRUNCATED-NEXT:     Name: bar
+# TRUNCATED-NEXT:     BB entries [
+# TRUNCATED-NEXT:       {
 # TRUNCATED-NEXT:         Offset: 0x9
 # TRUNCATED-NEXT:         Size: 0xA
 # TRUNCATED-NEXT:         HasReturn: Yes
 # TRUNCATED-NEXT:         HasTailCall: Yes
 # TRUNCATED-NEXT:         IsEHPad: No
 # TRUNCATED-NEXT:         CanFallThrough: Yes
 # TRUNCATED-NEXT:       }
 # TRUNCATED-NEXT:     ]
 # TRUNCATED-NEXT:   }
 # TRUNCATED-NEXT: ]
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS[[BITS]]
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
+  - Name:   .text
+    Type:   SHT_PROGBITS
+    Flags:  [SHF_ALLOC]
+  - Name:   .text.bar
+    Type:   SHT_PROGBITS
+    Flags:  [SHF_ALLOC]
   - Name:   bb_addr_map_1
     Type:   SHT_LLVM_BB_ADDR_MAP
     ShSize: [[SIZE=<none>]]
+    Link:   .text
     Entries:
       - Address: [[ADDR=0x11111]]
         BBEntries:
           - AddressOffset: 0x0
             Size:          0x1
             Metadata:      0xF0000002
           - AddressOffset: 0x3
             Size:          0x4
             Metadata:      0x5
       - Address: 0x22222
         BBEntries:
           - AddressOffset: 0x6
             Size:          0x7
             Metadata:      0x8
   - Name:   dummy_section
     Type:   SHT_PROGBITS
     Size:   16
   - Name:   bb_addr_map_2
     Type:   SHT_LLVM_BB_ADDR_MAP
+    Link:   .text.bar
     Entries:
       - Address: 0x33333
         BBEntries:
           - AddressOffset: 0x9
             Size:          0xa
             Metadata:      0xb
+Symbols:
+  - Name:    foo
+    Section: .text
+    Type:    STT_FUNC
+    Value:   0x22222
+  - Name:    bar
+    Section: .text.bar
+    Type:    STT_FUNC
+    Value:   0x33333

llvm/tools/llvm-readobj/ELFDumper.cpp

protected:
   DynRegionInfo DynPLTRelRegion;
   Optional<DynRegionInfo> DynSymRegion;
   DynRegionInfo DynSymTabShndxRegion;
   DynRegionInfo DynamicTable;
   StringRef DynamicStringTable;
   const Elf_Hash *HashTable = nullptr;
   const Elf_GnuHash *GnuHashTable = nullptr;
   const Elf_Shdr *DotSymtabSec = nullptr;
+  Optional<DenseMap<uint64_t, std::vector<uint32_t>>> SymbolValueToIndexMap;
   const Elf_Shdr *DotDynsymSec = nullptr;
   const Elf_Shdr *DotCGProfileSec = nullptr;
   const Elf_Shdr *DotAddrsigSec = nullptr;
   DenseMap<const Elf_Shdr *, ArrayRef<Elf_Word>> ShndxTables;
   Optional<uint64_t> SONameOffset;
   Optional<DenseMap<uint64_t, std::vector<uint32_t>>> AddressToIndexMap;
 
   const Elf_Shdr *SymbolVersionSection = nullptr;   // .gnu.version
W.printNumber("From", this->getStaticSymbolName(CGPE.cgp_from),
                   CGPE.cgp_from);
     W.printNumber("To", this->getStaticSymbolName(CGPE.cgp_to),
                   CGPE.cgp_to);
     W.printNumber("Weight", CGPE.cgp_weight);
   }
 }
 
 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)
       continue;
+    Optional<const Elf_Shdr *> FunctionSec = None;
+    if (IsRelocatable)
+      FunctionSec =
+          unwrapOrError(this->FileName, this->Obj.getSection(Sec.sh_link));
     ListScope L(W, "BBAddrMap");
     Expected<std::vector<Elf_BBAddrMap>> BBAddrMapOrErr =
         this->Obj.decodeBBAddrMap(Sec);
     if (!BBAddrMapOrErr) {
       this->reportUniqueWarning("unable to dump " + this->describe(Sec) + ": " +
                                 toString(BBAddrMapOrErr.takeError()));
       continue;
     }
     for (const Elf_BBAddrMap &AM : *BBAddrMapOrErr) {
       DictScope D(W, "Function");
       W.printHex("At", AM.Addr);
+      Optional<uint32_t> FuncSymIndex =
+          this->getSymbolIndexForFunctionAddress(AM.Addr, FunctionSec);
+      std::string FuncName = "<?>";
+      if (FuncSymIndex == None)
+        this->reportUniqueWarning(
+            "could not identify function symbol for address (0x" +
+            Twine::utohexstr(AM.Addr) + ") in " + this->describe(Sec));
+      else
+        FuncName = this->getStaticSymbolName(*FuncSymIndex);
+      W.printString("Name", FuncName);
+
       ListScope L(W, "BB entries");
       for (const typename Elf_BBAddrMap::BBEntry &BBE : AM.BBEntries) {
         DictScope L(W);
         W.printHex("Offset", BBE.Offset);
         W.printHex("Size", BBE.Size);
         W.printBoolean("HasReturn", BBE.HasReturn);
         W.printBoolean("HasTailCall", BBE.HasTailCall);
         W.printBoolean("IsEHPad", BBE.IsEHPad);