diff --git a/llvm/include/llvm/Support/ScopedPrinter.h b/llvm/include/llvm/Support/ScopedPrinter.h --- a/llvm/include/llvm/Support/ScopedPrinter.h +++ b/llvm/include/llvm/Support/ScopedPrinter.h @@ -230,6 +230,11 @@ startLine() << Label << ": " << int(Value) << "\n"; } + virtual void printNumber(StringRef Label, float Value) { + startLine() << Label << ": " << format("%5.1f", Value) << "\n"; + } + + virtual void printNumber(StringRef Label, const APSInt &Value) { startLine() << Label << ": " << Value << "\n"; } diff --git a/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test b/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test --- a/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test +++ b/llvm/test/tools/llvm-readobj/ELF/hash-histogram.test @@ -12,6 +12,10 @@ # RUN: yaml2obj --docnum=1 -D BITS=64 %s -o %t1-64.o # RUN: llvm-readelf --elf-hash-histogram %t1-64.o | FileCheck %s --check-prefix=HIST +## Check that LLVM output has the expected format +# RUN: llvm-readobj --elf-hash-histogram %t1-32.o | FileCheck %s --check-prefix=LLVM-HIST +# RUN: llvm-readobj --elf-hash-histogram %t1-64.o | FileCheck %s --check-prefix=LLVM-HIST + # HIST: Histogram for bucket list length (total of 3 buckets) # HIST-NEXT: Length Number % of total Coverage # HIST-NEXT: 0 2 ( 66.7%) 0.0% @@ -26,6 +30,65 @@ # HIST-NEXT: 3 1 ( 33.3%) 100.0% # HIST-NOT: {{.}} +# LLVM-HIST: HashHistogram { +# LLVM-HIST-NEXT: TotalBuckets: 3 +# LLVM-HIST-NEXT: Chains [ +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 0 +# LLVM-HIST-NEXT: Count: 2 +# LLVM-HIST-NEXT: Percentage: 66.7 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 1 +# LLVM-HIST-NEXT: Count: 0 +# LLVM-HIST-NEXT: Percentage: 0.0 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 2 +# LLVM-HIST-NEXT: Count: 0 +# LLVM-HIST-NEXT: Percentage: 0.0 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Chain { +# LLVM-HIST-NEXT: Length: 3 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 100.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: ] +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: GnuHashHistogram { +# LLVM-HIST-NEXT: TotalBuckets: 3 +# LLVM-HIST-NEXT: Buckets [ +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 0 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 0.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 1 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 25.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 2 +# LLVM-HIST-NEXT: Count: 0 +# LLVM-HIST-NEXT: Percentage: 0.0 +# LLVM-HIST-NEXT: Coverage: 25.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: Bucket { +# LLVM-HIST-NEXT: Length: 3 +# LLVM-HIST-NEXT: Count: 1 +# LLVM-HIST-NEXT: Percentage: 33.3 +# LLVM-HIST-NEXT: Coverage: 100.0 +# LLVM-HIST-NEXT: } +# LLVM-HIST-NEXT: ] +# LLVM-HIST-NEXT: } + --- !ELF FileHeader: Class: ELFCLASS[[BITS]] 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 @@ -222,6 +222,13 @@ void printArchSpecificInfo() override; void printStackMap() const override; + // Hash histogram shows statistics of how efficient the hash was for the + // dynamic symbol table. The table shows the number of hash buckets for + // different lengths of chains as an absolute number and percentage of the + // total buckets, and the cumulative coverage of symbols for each set of + // buckets. + void printHashHistograms() override; + const object::ELFObjectFile &getElfObject() const { return ObjF; }; std::string describe(const Elf_Shdr &Sec) const; @@ -300,6 +307,15 @@ virtual void printMipsGOT(const MipsGOTParser &Parser) = 0; virtual void printMipsPLT(const MipsGOTParser &Parser) = 0; + virtual void printHashHistogram(const Elf_Hash &HashTable) const; + virtual void printGnuHashHistogram(const Elf_GnuHash &GnuHashTable) const; + virtual void printHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, + const ArrayRef Count) const = 0; + virtual void printGnuHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, + const ArrayRef Count) const = 0; + Expected> getVersionTable(const Elf_Shdr &Sec, ArrayRef *SymTab, StringRef *StrTab, const Elf_Shdr **SymTabSec) const; @@ -575,17 +591,20 @@ void printVersionSymbolSection(const Elf_Shdr *Sec) override; void printVersionDefinitionSection(const Elf_Shdr *Sec) override; void printVersionDependencySection(const Elf_Shdr *Sec) override; - void printHashHistograms() override; void printCGProfile() override; void printBBAddrMaps() override; void printAddrsig() override; void printNotes() override; void printELFLinkerOptions() override; void printStackSizes() override; + void printHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, + const ArrayRef Count) const override; + void printGnuHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, + const ArrayRef Count) const override; private: - void printHashHistogram(const Elf_Hash &HashTable); - void printGnuHashHistogram(const Elf_GnuHash &GnuHashTable); void printHashTableSymbols(const Elf_Hash &HashTable); void printGnuHashTableSymbols(const Elf_GnuHash &GnuHashTable); @@ -679,7 +698,6 @@ void printVersionSymbolSection(const Elf_Shdr *Sec) override; void printVersionDefinitionSection(const Elf_Shdr *Sec) override; void printVersionDependencySection(const Elf_Shdr *Sec) override; - void printHashHistograms() override; void printCGProfile() override; void printBBAddrMaps() override; void printAddrsig() override; @@ -688,6 +706,13 @@ void printStackSizes() override; void printSymbolSection(const Elf_Sym &Symbol, unsigned SymIndex, DataRegion ShndxTable) const; + void printHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, + const ArrayRef Count) const override; + void printGnuHashHistogramStats(size_t NBucket, size_t MaxChain, + size_t TotalSyms, + const ArrayRef Count) const override; + private: void printRelrReloc(const Elf_Relr &R) override; @@ -2654,6 +2679,116 @@ W.printHexList("Values", *Chains); } +template void ELFDumper::printHashHistograms() { + // Print histogram for the .hash section. + if (this->HashTable) { + if (Error E = checkHashTable(*this, this->HashTable)) + this->reportUniqueWarning(std::move(E)); + else + printHashHistogram(*this->HashTable); + } + + // Print histogram for the .gnu.hash section. + if (this->GnuHashTable) { + if (Error E = checkGNUHashTable(this->Obj, this->GnuHashTable)) + this->reportUniqueWarning(std::move(E)); + else + printGnuHashHistogram(*this->GnuHashTable); + } +} + +template +void ELFDumper::printHashHistogram(const Elf_Hash &HashTable) const { + size_t NBucket = HashTable.nbucket; + size_t NChain = HashTable.nchain; + ArrayRef Buckets = HashTable.buckets(); + ArrayRef Chains = HashTable.chains(); + size_t TotalSyms = 0; + // If hash table is correct, we have at least chains with 0 length + size_t MaxChain = 1; + + if (NChain == 0 || NBucket == 0) + return; + + std::vector ChainLen(NBucket, 0); + // Go over all buckets and and note chain lengths of each bucket (total + // unique chain lengths). + for (size_t B = 0; B < NBucket; B++) { + BitVector Visited(NChain); + for (size_t C = Buckets[B]; C < NChain; C = Chains[C]) { + if (C == ELF::STN_UNDEF) + break; + if (Visited[C]) { + this->reportUniqueWarning(".hash section is invalid: bucket " + + Twine(C) + + ": a cycle was detected in the linked chain"); + break; + } + Visited[C] = true; + if (MaxChain <= ++ChainLen[B]) + MaxChain++; + } + TotalSyms += ChainLen[B]; + } + + if (!TotalSyms) + return; + + std::vector Count(MaxChain, 0); + // Count how long is the chain for each bucket + for (size_t B = 0; B < NBucket; B++) + ++Count[ChainLen[B]]; + // Print Number of buckets with each chain lengths and their cumulative + // coverage of the symbols + printHashHistogramStats(NBucket, MaxChain, TotalSyms, Count); +} + +template +void ELFDumper::printGnuHashHistogram( + const Elf_GnuHash &GnuHashTable) const { + Expected> ChainsOrErr = + getGnuHashTableChains(this->DynSymRegion, &GnuHashTable); + if (!ChainsOrErr) { + this->reportUniqueWarning("unable to print the GNU hash table histogram: " + + toString(ChainsOrErr.takeError())); + return; + } + + ArrayRef Chains = *ChainsOrErr; + size_t Symndx = GnuHashTable.symndx; + size_t TotalSyms = 0; + size_t MaxChain = 1; + + size_t NBucket = GnuHashTable.nbuckets; + if (Chains.empty() || NBucket == 0) + return; + + ArrayRef Buckets = GnuHashTable.buckets(); + std::vector ChainLen(NBucket, 0); + for (size_t B = 0; B < NBucket; B++) { + if (!Buckets[B]) + continue; + size_t Len = 1; + for (size_t C = Buckets[B] - Symndx; + C < Chains.size() && (Chains[C] & 1) == 0; C++) + if (MaxChain < ++Len) + MaxChain++; + ChainLen[B] = Len; + TotalSyms += Len; + } + MaxChain++; + + if (!TotalSyms) + return; + + std::vector Count(MaxChain, 0); + for (size_t B = 0; B < NBucket; B++) + ++Count[ChainLen[B]]; + // Print Number of buckets with each chain lengths and their cumulative + // coverage of the symbols + printGnuHashHistogramStats(NBucket, MaxChain, TotalSyms, Count); +} + template void ELFDumper::printLoadName() { StringRef SOName = ""; if (SONameOffset) @@ -4801,49 +4936,10 @@ } template -void GNUELFDumper::printHashHistogram(const Elf_Hash &HashTable) { - size_t NBucket = HashTable.nbucket; - size_t NChain = HashTable.nchain; - ArrayRef Buckets = HashTable.buckets(); - ArrayRef Chains = HashTable.chains(); - size_t TotalSyms = 0; - // If hash table is correct, we have at least chains with 0 length - size_t MaxChain = 1; +void GNUELFDumper::printHashHistogramStats( + size_t NBucket, size_t MaxChain, size_t TotalSyms, + const ArrayRef Count) const { size_t CumulativeNonZero = 0; - - if (NChain == 0 || NBucket == 0) - return; - - std::vector ChainLen(NBucket, 0); - // Go over all buckets and and note chain lengths of each bucket (total - // unique chain lengths). - for (size_t B = 0; B < NBucket; B++) { - BitVector Visited(NChain); - for (size_t C = Buckets[B]; C < NChain; C = Chains[C]) { - if (C == ELF::STN_UNDEF) - break; - if (Visited[C]) { - this->reportUniqueWarning(".hash section is invalid: bucket " + - Twine(C) + - ": a cycle was detected in the linked chain"); - break; - } - Visited[C] = true; - if (MaxChain <= ++ChainLen[B]) - MaxChain++; - } - TotalSyms += ChainLen[B]; - } - - if (!TotalSyms) - return; - - std::vector Count(MaxChain, 0); - // Count how long is the chain for each bucket - for (size_t B = 0; B < NBucket; B++) - ++Count[ChainLen[B]]; - // Print Number of buckets with each chain lengths and their cumulative - // coverage of the symbols OS << "Histogram for bucket list length (total of " << NBucket << " buckets)\n" << " Length Number % of total Coverage\n"; @@ -4856,49 +4952,10 @@ } template -void GNUELFDumper::printGnuHashHistogram( - const Elf_GnuHash &GnuHashTable) { - Expected> ChainsOrErr = - getGnuHashTableChains(this->DynSymRegion, &GnuHashTable); - if (!ChainsOrErr) { - this->reportUniqueWarning("unable to print the GNU hash table histogram: " + - toString(ChainsOrErr.takeError())); - return; - } - - ArrayRef Chains = *ChainsOrErr; - size_t Symndx = GnuHashTable.symndx; - size_t TotalSyms = 0; - size_t MaxChain = 1; +void GNUELFDumper::printGnuHashHistogramStats( + size_t NBucket, size_t MaxChain, size_t TotalSyms, + const ArrayRef Count) const { size_t CumulativeNonZero = 0; - - size_t NBucket = GnuHashTable.nbuckets; - if (Chains.empty() || NBucket == 0) - return; - - ArrayRef Buckets = GnuHashTable.buckets(); - std::vector ChainLen(NBucket, 0); - for (size_t B = 0; B < NBucket; B++) { - if (!Buckets[B]) - continue; - size_t Len = 1; - for (size_t C = Buckets[B] - Symndx; - C < Chains.size() && (Chains[C] & 1) == 0; C++) - if (MaxChain < ++Len) - MaxChain++; - ChainLen[B] = Len; - TotalSyms += Len; - } - MaxChain++; - - if (!TotalSyms) - return; - - std::vector Count(MaxChain, 0); - for (size_t B = 0; B < NBucket; B++) - ++Count[ChainLen[B]]; - // Print Number of buckets with each chain lengths and their cumulative - // coverage of the symbols OS << "Histogram for `.gnu.hash' bucket list length (total of " << NBucket << " buckets)\n" << " Length Number % of total Coverage\n"; @@ -4910,27 +4967,6 @@ } } -// Hash histogram shows statistics of how efficient the hash was for the -// dynamic symbol table. The table shows the number of hash buckets for -// different lengths of chains as an absolute number and percentage of the total -// buckets, and the cumulative coverage of symbols for each set of buckets. -template void GNUELFDumper::printHashHistograms() { - // Print histogram for the .hash section. - if (this->HashTable) { - if (Error E = checkHashTable(*this, this->HashTable)) - this->reportUniqueWarning(std::move(E)); - else - printHashHistogram(*this->HashTable); - } - - // Print histogram for the .gnu.hash section. - if (this->GnuHashTable) { - if (Error E = checkGNUHashTable(this->Obj, this->GnuHashTable)) - this->reportUniqueWarning(std::move(E)); - else - printGnuHashHistogram(*this->GnuHashTable); - } -} template void GNUELFDumper::printCGProfile() { OS << "GNUStyle::printCGProfile not implemented\n"; @@ -7088,8 +7124,40 @@ } } -template void LLVMELFDumper::printHashHistograms() { - W.startLine() << "Hash Histogram not implemented!\n"; +template +void LLVMELFDumper::printHashHistogramStats( + size_t NBucket, size_t MaxChain, size_t TotalSyms, + const ArrayRef Count) const { + DictScope Outer(W, "HashHistogram"); + W.printNumber("TotalBuckets", NBucket); + ListScope Buckets(W, "Chains"); + size_t CumulativeNonZero = 0; + for (size_t I = 0; I < MaxChain; I++) { + CumulativeNonZero += Count[I] * I; + DictScope Bucket(W, "Chain"); + W.printNumber("Length", I); + W.printNumber("Count", Count[I]); + W.printNumber("Percentage", (float)(Count[I] * 100.0) / NBucket); + W.printNumber("Coverage", (float)(CumulativeNonZero * 100.0) / TotalSyms); + } +} + +template +void LLVMELFDumper::printGnuHashHistogramStats( + size_t NBucket, size_t MaxChain, size_t TotalSyms, + const ArrayRef Count) const { + DictScope Outer(W, "GnuHashHistogram"); + W.printNumber("TotalBuckets", NBucket); + ListScope Buckets(W, "Buckets"); + size_t CumulativeNonZero = 0; + for (size_t I = 0; I < MaxChain; I++) { + CumulativeNonZero += Count[I] * I; + DictScope Bucket(W, "Bucket"); + W.printNumber("Length", I); + W.printNumber("Count", Count[I]); + W.printNumber("Percentage", (float)(Count[I] * 100.0) / NBucket); + W.printNumber("Coverage", (float)(CumulativeNonZero * 100.0) / TotalSyms); + } } // Returns true if rel/rela section exists, and populates SymbolIndices.