diff options
author | Rahman Lavaee <rahmanl@google.com> | 2024-02-01 17:50:46 -0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-02-01 17:50:46 -0800 |
commit | acec6419e811a46050b0603dfa72fc6a169aa0f7 (patch) | |
tree | 337780cb5ca46c7706367fab736bb56f9fdf6a3c /llvm/tools | |
parent | 70eab122bceb94b15218c86db7045ff2448ea979 (diff) | |
download | llvm-acec6419e811a46050b0603dfa72fc6a169aa0f7.zip llvm-acec6419e811a46050b0603dfa72fc6a169aa0f7.tar.gz llvm-acec6419e811a46050b0603dfa72fc6a169aa0f7.tar.bz2 |
[SHT_LLVM_BB_ADDR_MAP] Allow basic-block-sections and labels be used together by decoupling the handling of the two features. (#74128)
Today `-split-machine-functions` and `-fbasic-block-sections={all,list}`
cannot be combined with `-basic-block-sections=labels` (the labels
option will be ignored).
The inconsistency comes from the way basic block address map -- the
underlying mechanism for basic block labels -- encodes basic block
addresses
(https://lists.llvm.org/pipermail/llvm-dev/2020-July/143512.html).
Specifically, basic block offsets are computed relative to the function
begin symbol. This relies on functions being contiguous which is not the
case for MFS and basic block section binaries. This means Propeller
cannot use binary profiles collected from these binaries, which limits
the applicability of Propeller for iterative optimization.
To make the `SHT_LLVM_BB_ADDR_MAP` feature work with basic block section
binaries, we propose modifying the encoding of this section as follows.
First let us review the current encoding which emits the address of each
function and its number of basic blocks, followed by basic block entries
for each basic block.
| | |
|--|--|
| Address of the function | Function Address |
| Number of basic blocks in this function | NumBlocks |
| BB entry 1
| BB entry 2
| ...
| BB entry #NumBlocks
To make this work for basic block sections, we treat each basic block
section similar to a function, except that basic block sections of the
same function must be encapsulated in the same structure so we can map
all of them to their single function.
We modify the encoding to first emit the number of basic block sections
(BB ranges) in the function. Then we emit the address map of each basic
block section section as before: the base address of the section, its
number of blocks, and BB entries for its basic block. The first section
in the BB address map is always the function entry section.
| | |
|--|--|
| Number of sections for this function | NumBBRanges |
| Section 1 begin address | BaseAddress[1] |
| Number of basic blocks in section 1 | NumBlocks[1] |
| BB entries for Section 1
|..................|
| Section #NumBBRanges begin address | BaseAddress[NumBBRanges] |
| Number of basic blocks in section #NumBBRanges |
NumBlocks[NumBBRanges] |
| BB entries for Section #NumBBRanges
The encoding of basic block entries remains as before with the minor
change that each basic block offset is now computed relative to the
begin symbol of its containing BB section.
This patch adds a new boolean codegen option `-basic-block-address-map`.
Correspondingly, the front-end flag `-fbasic-block-address-map` and LLD
flag `--lto-basic-block-address-map` are introduced.
Analogously, we add a new TargetOption field `BBAddrMap`. This means BB
address maps are either generated for all functions in the compiling
unit, or for none (depending on `TargetOptions::BBAddrMap`).
This patch keeps the functionality of the old
`-fbasic-block-sections=labels` option but does not remove it. A
subsequent patch will remove the obsolete option.
We refactor the `BasicBlockSections` pass by separating the BB address
map and BB sections handing to their own functions (named
`handleBBAddrMap` and `handleBBSections`). `handleBBSections` renumbers
basic blocks and places them in their assigned sections.
`handleBBAddrMap` is invoked after `handleBBSections` (if requested) and
only renumbers the blocks.
- New tests added:
- Two tests basic-block-address-map-with-basic-block-sections.ll and
basic-block-address-map-with-mfs.ll to exercise the combination of
`-basic-block-address-map` with `-basic-block-sections=list` and
'-split-machine-functions`.
- A driver sanity test for the `-fbasic-block-address-map` option
(basic-block-address-map.c).
- An LLD test for testing the `--lto-basic-block-address-map` option.
This reuses the LLVM IR from `lld/test/ELF/lto/basic-block-sections.ll`.
- Renamed and modified the two existing codegen tests for basic block
address map (`basic-block-sections-labels-functions-sections.ll` and
`basic-block-sections-labels.ll`)
- Removed `SHT_LLVM_BB_ADDR_MAP_V0` tests. Full deprecation of
`SHT_LLVM_BB_ADDR_MAP_V0` and `SHT_LLVM_BB_ADDR_MAP` version less than 2
will happen in a separate PR in a few months.
Diffstat (limited to 'llvm/tools')
-rw-r--r-- | llvm/tools/llvm-objdump/llvm-objdump.cpp | 206 | ||||
-rw-r--r-- | llvm/tools/llvm-readobj/ELFDumper.cpp | 43 | ||||
-rw-r--r-- | llvm/tools/obj2yaml/elf2yaml.cpp | 46 |
3 files changed, 190 insertions, 105 deletions
diff --git a/llvm/tools/llvm-objdump/llvm-objdump.cpp b/llvm/tools/llvm-objdump/llvm-objdump.cpp index 7f57713..b4467ec 100644 --- a/llvm/tools/llvm-objdump/llvm-objdump.cpp +++ b/llvm/tools/llvm-objdump/llvm-objdump.cpp @@ -172,6 +172,110 @@ public: "Mach-O object file displaying tool") {} }; +struct BBAddrMapLabel { + std::string BlockLabel; + std::string PGOAnalysis; +}; + +// This class represents the BBAddrMap and PGOMap associated with a single +// function. +class BBAddrMapFunctionEntry { +public: + BBAddrMapFunctionEntry(BBAddrMap AddrMap, PGOAnalysisMap PGOMap) + : AddrMap(std::move(AddrMap)), PGOMap(std::move(PGOMap)) {} + + const BBAddrMap &getAddrMap() const { return AddrMap; } + + // Returns the PGO string associated with the entry of index `PGOBBEntryIndex` + // in `PGOMap`. + std::string constructPGOLabelString(size_t PGOBBEntryIndex) const { + if (!PGOMap.FeatEnable.hasPGOAnalysis()) + return ""; + std::string PGOString; + raw_string_ostream PGOSS(PGOString); + + PGOSS << " ("; + if (PGOMap.FeatEnable.FuncEntryCount && PGOBBEntryIndex == 0) { + PGOSS << "Entry count: " << Twine(PGOMap.FuncEntryCount); + if (PGOMap.FeatEnable.hasPGOAnalysisBBData()) { + PGOSS << ", "; + } + } + + if (PGOMap.FeatEnable.hasPGOAnalysisBBData()) { + + assert(PGOBBEntryIndex < PGOMap.BBEntries.size() && + "Expected PGOAnalysisMap and BBAddrMap to have the same entries"); + const PGOAnalysisMap::PGOBBEntry &PGOBBEntry = + PGOMap.BBEntries[PGOBBEntryIndex]; + + if (PGOMap.FeatEnable.BBFreq) { + PGOSS << "Frequency: " << Twine(PGOBBEntry.BlockFreq.getFrequency()); + if (PGOMap.FeatEnable.BrProb && PGOBBEntry.Successors.size() > 0) { + PGOSS << ", "; + } + } + if (PGOMap.FeatEnable.BrProb && PGOBBEntry.Successors.size() > 0) { + PGOSS << "Successors: "; + interleaveComma( + PGOBBEntry.Successors, PGOSS, + [&PGOSS](const PGOAnalysisMap::PGOBBEntry::SuccessorEntry &SE) { + PGOSS << "BB" << SE.ID << ":"; + PGOSS.write_hex(SE.Prob.getNumerator()); + }); + } + } + PGOSS << ")"; + + return PGOString; + } + +private: + const BBAddrMap AddrMap; + const PGOAnalysisMap PGOMap; +}; + +// This class represents the BBAddrMap and PGOMap of potentially multiple +// functions in a section. +class BBAddrMapInfo { +public: + void clear() { + FunctionAddrToMap.clear(); + RangeBaseAddrToFunctionAddr.clear(); + } + + bool empty() const { return FunctionAddrToMap.empty(); } + + void AddFunctionEntry(BBAddrMap AddrMap, PGOAnalysisMap PGOMap) { + uint64_t FunctionAddr = AddrMap.getFunctionAddress(); + for (size_t I = 1; I < AddrMap.BBRanges.size(); ++I) + RangeBaseAddrToFunctionAddr.emplace(AddrMap.BBRanges[I].BaseAddress, + FunctionAddr); + [[maybe_unused]] auto R = FunctionAddrToMap.try_emplace( + FunctionAddr, std::move(AddrMap), std::move(PGOMap)); + assert(R.second && "duplicate function address"); + } + + // Returns the BBAddrMap entry for the function associated with `BaseAddress`. + // `BaseAddress` could be the function address or the address of a range + // associated with that function. Returns `nullptr` if `BaseAddress` is not + // mapped to any entry. + const BBAddrMapFunctionEntry *getEntryForAddress(uint64_t BaseAddress) const { + uint64_t FunctionAddr = BaseAddress; + auto S = RangeBaseAddrToFunctionAddr.find(BaseAddress); + if (S != RangeBaseAddrToFunctionAddr.end()) + FunctionAddr = S->second; + auto R = FunctionAddrToMap.find(FunctionAddr); + if (R == FunctionAddrToMap.end()) + return nullptr; + return &R->second; + } + +private: + std::unordered_map<uint64_t, BBAddrMapFunctionEntry> FunctionAddrToMap; + std::unordered_map<uint64_t, uint64_t> RangeBaseAddrToFunctionAddr; +}; + } // namespace #define DEBUG_TYPE "objdump" @@ -1266,80 +1370,38 @@ static SymbolInfoTy createDummySymbolInfo(const ObjectFile &Obj, return SymbolInfoTy(Addr, Name, Type); } -struct BBAddrMapLabel { - std::string BlockLabel; - std::string PGOAnalysis; -}; - -static std::string constructPGOLabelString(const PGOAnalysisMap &PGOMap, - size_t BBEntryIndex) { - std::string PGOString; - raw_string_ostream PGOSS(PGOString); - - PGOSS << " ("; - if (PGOMap.FeatEnable.FuncEntryCount && BBEntryIndex == 0) { - PGOSS << "Entry count: " << Twine(PGOMap.FuncEntryCount); - if (PGOMap.FeatEnable.BBFreq || PGOMap.FeatEnable.BrProb) { - PGOSS << ", "; - } - } - - if (PGOMap.FeatEnable.BBFreq || PGOMap.FeatEnable.BrProb) { - assert(BBEntryIndex < PGOMap.BBEntries.size() && - "Expected PGOAnalysisMap and BBAddrMap to have the same entires"); - const PGOAnalysisMap::PGOBBEntry &PGOBBEntry = - PGOMap.BBEntries[BBEntryIndex]; - - if (PGOMap.FeatEnable.BBFreq) { - PGOSS << "Frequency: " << Twine(PGOBBEntry.BlockFreq.getFrequency()); - if (PGOMap.FeatEnable.BrProb && PGOBBEntry.Successors.size() > 0) { - PGOSS << ", "; - } - } - if (PGOMap.FeatEnable.BrProb && PGOBBEntry.Successors.size() > 0) { - PGOSS << "Successors: "; - interleaveComma( - PGOBBEntry.Successors, PGOSS, - [&PGOSS](const PGOAnalysisMap::PGOBBEntry::SuccessorEntry &SE) { - PGOSS << "BB" << SE.ID << ":"; - PGOSS.write_hex(SE.Prob.getNumerator()); - }); - } - } - PGOSS << ")"; - - return PGOString; -} - static void collectBBAddrMapLabels( - const std::unordered_map<uint64_t, BBAddrMap> &AddrToBBAddrMap, - const std::unordered_map<uint64_t, PGOAnalysisMap> &AddrToPGOAnalysisMap, - uint64_t SectionAddr, uint64_t Start, uint64_t End, - std::unordered_map<uint64_t, std::vector<BBAddrMapLabel>> &Labels, - const StringRef FileName) { - if (AddrToBBAddrMap.empty()) + const BBAddrMapInfo &FullAddrMap, uint64_t SectionAddr, uint64_t Start, + uint64_t End, + std::unordered_map<uint64_t, std::vector<BBAddrMapLabel>> &Labels) { + if (FullAddrMap.empty()) return; Labels.clear(); uint64_t StartAddress = SectionAddr + Start; uint64_t EndAddress = SectionAddr + End; - auto Iter = AddrToBBAddrMap.find(StartAddress); - if (Iter == AddrToBBAddrMap.end()) + const BBAddrMapFunctionEntry *FunctionMap = + FullAddrMap.getEntryForAddress(StartAddress); + if (!FunctionMap) return; - auto PGOIter = AddrToPGOAnalysisMap.find(StartAddress); - - for (size_t I = 0; I < Iter->second.getBBEntries().size(); ++I) { - const BBAddrMap::BBEntry &BBEntry = Iter->second.getBBEntries()[I]; - uint64_t BBAddress = BBEntry.Offset + Iter->second.getFunctionAddress(); + std::optional<size_t> BBRangeIndex = + FunctionMap->getAddrMap().getBBRangeIndexForBaseAddress(StartAddress); + if (!BBRangeIndex) + return; + size_t NumBBEntriesBeforeRange = 0; + for (size_t I = 0; I < *BBRangeIndex; ++I) + NumBBEntriesBeforeRange += + FunctionMap->getAddrMap().BBRanges[I].BBEntries.size(); + const auto &BBRange = FunctionMap->getAddrMap().BBRanges[*BBRangeIndex]; + for (size_t I = 0; I < BBRange.BBEntries.size(); ++I) { + const BBAddrMap::BBEntry &BBEntry = BBRange.BBEntries[I]; + uint64_t BBAddress = BBEntry.Offset + BBRange.BaseAddress; if (BBAddress >= EndAddress) continue; std::string LabelString = ("BB" + Twine(BBEntry.ID)).str(); - std::string PGOString; - - if (PGOIter != AddrToPGOAnalysisMap.end()) - PGOString = constructPGOLabelString(PGOIter->second, I); - - Labels[BBAddress].push_back({LabelString, PGOString}); + Labels[BBAddress].push_back( + {LabelString, + FunctionMap->constructPGOLabelString(NumBBEntriesBeforeRange + I)}); } } @@ -1696,11 +1758,10 @@ disassembleObject(ObjectFile &Obj, const ObjectFile &DbgObj, LLVM_DEBUG(LVP.dump()); - std::unordered_map<uint64_t, BBAddrMap> AddrToBBAddrMap; - std::unordered_map<uint64_t, PGOAnalysisMap> AddrToPGOAnalysisMap; + BBAddrMapInfo FullAddrMap; auto ReadBBAddrMap = [&](std::optional<unsigned> SectionIndex = std::nullopt) { - AddrToBBAddrMap.clear(); + FullAddrMap.clear(); if (const auto *Elf = dyn_cast<ELFObjectFileBase>(&Obj)) { std::vector<PGOAnalysisMap> PGOAnalyses; auto BBAddrMapsOrErr = Elf->readBBAddrMap(SectionIndex, &PGOAnalyses); @@ -1710,10 +1771,8 @@ disassembleObject(ObjectFile &Obj, const ObjectFile &DbgObj, } for (auto &&[FunctionBBAddrMap, FunctionPGOAnalysis] : zip_equal(*std::move(BBAddrMapsOrErr), std::move(PGOAnalyses))) { - uint64_t Addr = FunctionBBAddrMap.Addr; - AddrToBBAddrMap.emplace(Addr, std::move(FunctionBBAddrMap)); - if (FunctionPGOAnalysis.FeatEnable.anyEnabled()) - AddrToPGOAnalysisMap.emplace(Addr, std::move(FunctionPGOAnalysis)); + FullAddrMap.AddFunctionEntry(std::move(FunctionBBAddrMap), + std::move(FunctionPGOAnalysis)); } } }; @@ -2049,9 +2108,8 @@ disassembleObject(ObjectFile &Obj, const ObjectFile &DbgObj, DT->DisAsm.get(), DT->InstPrinter.get(), PrimaryTarget.SubtargetInfo.get(), SectionAddr, Index, End, AllLabels); - collectBBAddrMapLabels(AddrToBBAddrMap, AddrToPGOAnalysisMap, - SectionAddr, Index, End, BBAddrMapLabels, - FileName); + collectBBAddrMapLabels(FullAddrMap, SectionAddr, Index, End, + BBAddrMapLabels); } if (DT->InstrAnalysis) diff --git a/llvm/tools/llvm-readobj/ELFDumper.cpp b/llvm/tools/llvm-readobj/ELFDumper.cpp index 4bf4640..ce33b15 100644 --- a/llvm/tools/llvm-readobj/ELFDumper.cpp +++ b/llvm/tools/llvm-readobj/ELFDumper.cpp @@ -7545,8 +7545,7 @@ template <class ELFT> void LLVMELFDumper<ELFT>::printBBAddrMaps() { bool IsRelocatable = this->Obj.getHeader().e_type == ELF::ET_REL; using Elf_Shdr = typename ELFT::Shdr; auto IsMatch = [](const Elf_Shdr &Sec) -> bool { - return Sec.sh_type == ELF::SHT_LLVM_BB_ADDR_MAP || - Sec.sh_type == ELF::SHT_LLVM_BB_ADDR_MAP_V0; + return Sec.sh_type == ELF::SHT_LLVM_BB_ADDR_MAP; }; Expected<MapVector<const Elf_Shdr *, const Elf_Shdr *>> SecRelocMapOrErr = this->Obj.getSectionAndRelocations(IsMatch); @@ -7577,40 +7576,46 @@ template <class ELFT> void LLVMELFDumper<ELFT>::printBBAddrMaps() { } for (const auto &[AM, PAM] : zip_equal(*BBAddrMapOrErr, PGOAnalyses)) { DictScope D(W, "Function"); - W.printHex("At", AM.Addr); + W.printHex("At", AM.getFunctionAddress()); SmallVector<uint32_t> FuncSymIndex = - this->getSymbolIndexesForFunctionAddress(AM.Addr, FunctionSec); + this->getSymbolIndexesForFunctionAddress(AM.getFunctionAddress(), + FunctionSec); std::string FuncName = "<?>"; if (FuncSymIndex.empty()) this->reportUniqueWarning( "could not identify function symbol for address (0x" + - Twine::utohexstr(AM.Addr) + ") in " + this->describe(*Sec)); + Twine::utohexstr(AM.getFunctionAddress()) + ") in " + + this->describe(*Sec)); else FuncName = this->getStaticSymbolName(FuncSymIndex.front()); W.printString("Name", FuncName); - { - ListScope L(W, "BB entries"); - for (const BBAddrMap::BBEntry &BBE : AM.BBEntries) { - DictScope L(W); - W.printNumber("ID", BBE.ID); - 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()); - W.printBoolean("CanFallThrough", BBE.canFallThrough()); - W.printBoolean("HasIndirectBranch", BBE.hasIndirectBranch()); + ListScope BBRL(W, "BB Ranges"); + for (const BBAddrMap::BBRangeEntry &BBR : AM.BBRanges) { + DictScope BBRD(W); + W.printHex("Base Address", BBR.BaseAddress); + ListScope BBEL(W, "BB Entries"); + for (const BBAddrMap::BBEntry &BBE : BBR.BBEntries) { + DictScope BBED(W); + W.printNumber("ID", BBE.ID); + 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()); + W.printBoolean("CanFallThrough", BBE.canFallThrough()); + W.printBoolean("HasIndirectBranch", BBE.hasIndirectBranch()); + } } } - if (PAM.FeatEnable.anyEnabled()) { + if (PAM.FeatEnable.hasPGOAnalysis()) { DictScope PD(W, "PGO analyses"); if (PAM.FeatEnable.FuncEntryCount) W.printNumber("FuncEntryCount", PAM.FuncEntryCount); - if (PAM.FeatEnable.BBFreq || PAM.FeatEnable.BrProb) { + if (PAM.FeatEnable.hasPGOAnalysisBBData()) { ListScope L(W, "PGO BB entries"); for (const PGOAnalysisMap::PGOBBEntry &PBBE : PAM.BBEntries) { DictScope L(W); diff --git a/llvm/tools/obj2yaml/elf2yaml.cpp b/llvm/tools/obj2yaml/elf2yaml.cpp index 86bd138..38a69f7 100644 --- a/llvm/tools/obj2yaml/elf2yaml.cpp +++ b/llvm/tools/obj2yaml/elf2yaml.cpp @@ -626,7 +626,6 @@ ELFDumper<ELFT>::dumpSections() { case ELF::SHT_LLVM_CALL_GRAPH_PROFILE: return [this](const Elf_Shdr *S) { return dumpCallGraphProfileSection(S); }; - case ELF::SHT_LLVM_BB_ADDR_MAP_V0: case ELF::SHT_LLVM_BB_ADDR_MAP: return [this](const Elf_Shdr *S) { return dumpBBAddrMapSection(S); }; case ELF::SHT_STRTAB: @@ -893,6 +892,7 @@ ELFDumper<ELFT>::dumpBBAddrMapSection(const Elf_Shdr *Shdr) { DataExtractor::Cursor Cur(0); uint8_t Version = 0; uint8_t Feature = 0; + uint64_t Address = 0; while (Cur && Cur.tell() < Content.size()) { if (Shdr->sh_type == ELF::SHT_LLVM_BB_ADDR_MAP) { Version = Data.getU8(Cur); @@ -903,19 +903,41 @@ ELFDumper<ELFT>::dumpBBAddrMapSection(const Elf_Shdr *Shdr) { Twine(static_cast<int>(Version))); Feature = Data.getU8(Cur); } - uint64_t Address = Data.getAddress(Cur); - uint64_t NumBlocks = Data.getULEB128(Cur); - std::vector<ELFYAML::BBAddrMapEntry::BBEntry> BBEntries; - // Read the specified number of BB entries, or until decoding fails. - for (uint64_t BlockIndex = 0; Cur && BlockIndex < NumBlocks; ++BlockIndex) { - uint32_t ID = Version >= 2 ? Data.getULEB128(Cur) : BlockIndex; - uint64_t Offset = Data.getULEB128(Cur); - uint64_t Size = Data.getULEB128(Cur); - uint64_t Metadata = Data.getULEB128(Cur); - BBEntries.push_back({ID, Offset, Size, Metadata}); + uint64_t NumBBRanges = 1; + uint64_t NumBlocks = 0; + auto FeatureOrErr = llvm::object::BBAddrMap::Features::decode(Feature); + if (!FeatureOrErr) + return FeatureOrErr.takeError(); + if (FeatureOrErr->MultiBBRange) { + NumBBRanges = Data.getULEB128(Cur); + } else { + Address = Data.getAddress(Cur); + NumBlocks = Data.getULEB128(Cur); + } + std::vector<ELFYAML::BBAddrMapEntry::BBRangeEntry> BBRanges; + uint64_t BaseAddress = 0; + for (uint64_t BBRangeN = 0; Cur && BBRangeN != NumBBRanges; ++BBRangeN) { + if (FeatureOrErr->MultiBBRange) { + BaseAddress = Data.getAddress(Cur); + NumBlocks = Data.getULEB128(Cur); + } else { + BaseAddress = Address; + } + + std::vector<ELFYAML::BBAddrMapEntry::BBEntry> BBEntries; + // Read the specified number of BB entries, or until decoding fails. + for (uint64_t BlockIndex = 0; Cur && BlockIndex < NumBlocks; + ++BlockIndex) { + uint32_t ID = Version >= 2 ? Data.getULEB128(Cur) : BlockIndex; + uint64_t Offset = Data.getULEB128(Cur); + uint64_t Size = Data.getULEB128(Cur); + uint64_t Metadata = Data.getULEB128(Cur); + BBEntries.push_back({ID, Offset, Size, Metadata}); + } + BBRanges.push_back({BaseAddress, /*NumBlocks=*/{}, BBEntries}); } Entries.push_back( - {Version, Feature, Address, /*NumBlocks=*/{}, std::move(BBEntries)}); + {Version, Feature, /*NumBBRanges=*/{}, std::move(BBRanges)}); } if (!Cur) { |