[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

20

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

llvm/tools/llvm-readobj/ELFDumper.cpp

6745

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

 
 ## 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:     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:
 
   Expected<ArrayRef<Elf_Versym>>
   getVersionTable(const Elf_Shdr &Sec, ArrayRef<Elf_Sym> *SymTab,
                   StringRef *StrTab, const Elf_Shdr **SymTabSec) const;
   StringRef getPrintableSectionName(const Elf_Shdr &Sec) const;
 
   std::vector<GroupSection> getGroups();
 
+  // Returns the function symbol index for the given address. Matches the
+  // symbol's section with FunctionSec when specified.
+  // Returns None if no function symbol can be found for the address or in case
+  // it is not defined in the specified section.
+  Optional<uint32_t>
+  getSymbolIndexForFunctionAddress(uint64_t SymValue,
+                                   Optional<const Elf_Shdr *> FunctionSec);
   bool printFunctionStackSize(uint64_t SymValue,
                               Optional<const Elf_Shdr *> FunctionSec,
                               const Elf_Shdr &StackSizeSec, DataExtractor Data,
                               uint64_t *Offset);
   void printStackSize(const Relocation<ELFT> &R, const Elf_Shdr &RelocSec,
                       unsigned Ndx, const Elf_Shdr *SymTab,
                       const Elf_Shdr *FunctionSec, const Elf_Shdr &StackSizeSec,
                       const RelocationResolver &Resolver, DataExtractor Data);
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<uint64_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;
 
   const Elf_Shdr *SymbolVersionSection = nullptr;   // .gnu.version
   const Elf_Shdr *SymbolVersionNeedSection = nullptr; // .gnu.version_r
template <class ELFT> void GNUELFDumper<ELFT>::printDependentLibs() {
   };
 
   this->printDependentLibsHelper(OnSectionStart, OnLibEntry);
   if (SectionStarted)
     PrintSection();
 }
 
 template <class ELFT>
-bool ELFDumper<ELFT>::printFunctionStackSize(
-    uint64_t SymValue, Optional<const Elf_Shdr *> FunctionSec,
-    const Elf_Shdr &StackSizeSec, DataExtractor Data, uint64_t *Offset) {
-  uint32_t FuncSymIndex = 0;
+Optional<uint32_t> ELFDumper<ELFT>::getSymbolIndexForFunctionAddress(
+    uint64_t SymValue, Optional<const Elf_Shdr *> FunctionSec) {
+  if (!this->SymbolValueToIndexMap.hasValue()) {
+    // Populate the address to index map upon the first invocation of this
+    // function.
+    this->SymbolValueToIndexMap.emplace();
     if (this->DotSymtabSec) {
-    if (Expected<Elf_Sym_Range> SymsOrError = Obj.symbols(this->DotSymtabSec)) {
+      if (Expected<Elf_Sym_Range> SymsOrError =
+              Obj.symbols(this->DotSymtabSec)) {
         uint32_t Index = (uint32_t)-1;
         for (const Elf_Sym &Sym : *SymsOrError) {
+          (void)Sym;
           ++Index;
 
-        if (Sym.st_shndx == ELF::SHN_UNDEF || Sym.getType() != ELF::STT_FUNC)
-          continue;
-
-        if (Expected<uint64_t> SymAddrOrErr =
-                ObjF.toSymbolRef(this->DotSymtabSec, Index).getAddress()) {
-          if (SymValue != *SymAddrOrErr)
-            continue;
-        } else {
+          Expected<uint64_t> SymAddrOrErr =
+              ObjF.toSymbolRef(this->DotSymtabSec, Index).getAddress();
+          if (!SymAddrOrErr) {
             std::string Name = this->getStaticSymbolName(Index);
             reportUniqueWarning("unable to get address of symbol '" + Name +
                                 "': " + toString(SymAddrOrErr.takeError()));
-          break;
+            return None;
           }
 
-        // Check if the symbol is in the right section. FunctionSec == None
-        // means "any section".
-        if (FunctionSec) {
-          if (Expected<const Elf_Shdr *> SecOrErr =
-                  Obj.getSection(Sym, this->DotSymtabSec,
-                                 this->getShndxTable(this->DotSymtabSec))) {
-            if (*FunctionSec != *SecOrErr)
-              continue;
-          } else {
-            std::string Name = this->getStaticSymbolName(Index);
-            // Note: it is impossible to trigger this error currently, it is
-            // untested.
-            reportUniqueWarning("unable to get section of symbol '" + Name +
-                                "': " + toString(SecOrErr.takeError()));
-            break;
-          }
-        }
+          (*this->SymbolValueToIndexMap)[*SymAddrOrErr].push_back(Index);
+        }
+      } else {
+        reportUniqueWarning("unable to read the symbol table: " +
+                            toString(SymsOrError.takeError()));
+      }
+    }
+  }
+
+  auto Symbols = this->SymbolValueToIndexMap->find(SymValue);
+  if (Symbols == this->SymbolValueToIndexMap->end())
+    return None;
+  for (auto Index : Symbols->second) {
+
+    const Elf_Sym &Sym = *cantFail(Obj.getSymbol(this->DotSymtabSec, Index));
+    if (Sym.st_shndx == ELF::SHN_UNDEF || Sym.getType() != ELF::STT_FUNC)
+      continue;
+
+        return None;
 
-        FuncSymIndex = Index;
-        break;
-      }
-    } else {
-      reportUniqueWarning("unable to read the symbol table: " +
-                          toString(SymsOrError.takeError()));
-    }
-  }
+    return Index;
+  return None;
 
+template <class ELFT>
+bool ELFDumper<ELFT>::printFunctionStackSize(
+    uint64_t SymValue, Optional<const Elf_Shdr *> FunctionSec,
+    const Elf_Shdr &StackSizeSec, DataExtractor Data, uint64_t *Offset) {
+  Optional<uint32_t> FuncSymIndex =
+      this->getSymbolIndexForFunctionAddress(SymValue, FunctionSec);
   std::string FuncName = "?";
   if (!FuncSymIndex)
     reportUniqueWarning(
         "could not identify function symbol for stack size entry in " +
         describe(StackSizeSec));
   else
-    FuncName = this->getStaticSymbolName(FuncSymIndex);
+    FuncName = this->getStaticSymbolName(*FuncSymIndex);
 
   // Extract the size. The expectation is that Offset is pointing to the right
   // place, i.e. past the function address.
   Error Err = Error::success();
   uint64_t StackSize = Data.getULEB128(Offset, &Err);
   if (Err) {
     reportUniqueWarning("could not extract a valid stack size from " +
                         describe(StackSizeSec) + ": " +
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);