[llvm-readobj] Optimize printing stack sizes to linear time.

[rahmanl]

Summary

Currently, each function name lookup is a linear iteration over all symbols defined in the object file which makes the total running time quadratic.

This patch optimizes the function name lookup by populating an address to index map upon the first function name lookup which is used to lookup each function name in O(1).

impact: For the clang binary built with -fstack-size-section, this improves the running time of llvm-readobj --stack-size from 7 minutes to 0.25 seconds.

[jhenderson]

llvm/tools/llvm-readobj/ELFDumper.cpp

5750–5751

Nit: add a blank line before the start of the loop and remove the one inside the loop.

5753–5754

Based on the function name, can't this clause be moved inside the earlier loop, where it was before? That would avoid adding unnecessary symbols to the table.

6724–6731

Seems like this change is unrelated?

[rahmanl]

Address comments.

[rahmanl]

Rename map to AddressToIndexMap.

[jhenderson]

LGTM, with nit.

llvm/tools/llvm-readobj/ELFDumper.cpp

5723

You can delete this line now.

[rahmanl]

• Remove (void) line.

[rahmanl]

Thanks for the review @jhenderson

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:
   const Elf_Hash *HashTable = nullptr;
   const Elf_GnuHash *GnuHashTable = nullptr;
   const Elf_Shdr *DotSymtabSec = nullptr;
   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>>> SymbolValueToIndexMap;
 
   const Elf_Shdr *SymbolVersionSection = nullptr;   // .gnu.version
   const Elf_Shdr *SymbolVersionNeedSection = nullptr; // .gnu.version_r
   const Elf_Shdr *SymbolVersionDefSection = nullptr; // .gnu.version_d
 
   std::string getFullSymbolName(const Elf_Sym &Symbol, unsigned SymIndex,
                                 DataRegion<Elf_Word> ShndxTable,
                                 Optional<StringRef> StrTable,
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;
+          }
+
+          (*this->SymbolValueToIndexMap)[*SymAddrOrErr].push_back(Index);
+        }
+      } else {
+        reportUniqueWarning("unable to read the symbol table: " +
+                            toString(SymsOrError.takeError()));
+      }
+    }
 
-        // 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;
-          }
-        }
+  auto Symbols = this->SymbolValueToIndexMap->find(SymValue);
+  if (Symbols == this->SymbolValueToIndexMap->end())
+    return None;
+
+  for (uint32_t Index : Symbols->second) {
+      const Elf_Sym &Sym = *cantFail(Obj.getSymbol(this->DotSymtabSec, Index));
+        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() {
   for (const Elf_Shdr &Sec : cantFail(this->Obj.sections())) {
     if (Sec.sh_type != SHT_LLVM_BB_ADDR_MAP)
       continue;
     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);
       ListScope L(W, "BB entries");
       for (const typename Elf_BBAddrMap::BBEntry &BBE : AM.BBEntries) {