From 05523dc32d8ca81d9a92ff955194a9e80cf79dc0 Mon Sep 17 00:00:00 2001 From: Huan Nguyen Date: Wed, 13 Jul 2022 23:35:51 -0700 Subject: [PATCH] [BOLT] Support multiple parents for split jump table There are two assumptions regarding jump table: (a) It is accessed by only one fragment, say, Parent (b) All entries target instructions in Parent For (a), BOLT stores jump table entries as relative offset to Parent. For (b), BOLT treats jump table entries target somewhere out of Parent as INVALID_OFFSET, including fragment of same split function. In this update, we extend (a) and (b) to include fragment of same split functinon. For (a), we store jump table entries in absolute offset instead. In addition, jump table will store all fragments that access it. A fragment uses this information to only create label for jump table entries that target to that fragment. For (b), using absolute offset allows jump table entries to target fragments of same split function, i.e., extend support for split jump table. This can be done using relocation (fragment start/size) and fragment detection heuristics (e.g., using symbol name pattern for non-stripped binaries). For jump table targets that can only be reached by one fragment, we mark them as local label; otherwise, they would be the secondary function entry to the target fragment. Test Plan ``` ninja check-bolt ``` Reviewed By: Amir Differential Revision: https://reviews.llvm.org/D128474 --- bolt/include/bolt/Core/BinaryContext.h | 28 ++-- bolt/include/bolt/Core/BinaryFunction.h | 19 ++- bolt/include/bolt/Core/JumpTable.h | 13 +- bolt/lib/Core/BinaryContext.cpp | 151 ++++++++++++--------- bolt/lib/Core/BinaryFunction.cpp | 37 ++++- bolt/lib/Core/JumpTable.cpp | 18 ++- bolt/lib/Passes/AsmDump.cpp | 9 +- bolt/lib/Rewrite/RewriteInstance.cpp | 10 +- bolt/test/X86/jump-table-move.s | 34 +++++ .../split-func-jump-table-fragment-bidirection.s | 5 +- 10 files changed, 212 insertions(+), 112 deletions(-) create mode 100644 bolt/test/X86/jump-table-move.s diff --git a/bolt/include/bolt/Core/BinaryContext.h b/bolt/include/bolt/Core/BinaryContext.h index f2fb727..8d385e9 100644 --- a/bolt/include/bolt/Core/BinaryContext.h +++ b/bolt/include/bolt/Core/BinaryContext.h @@ -200,7 +200,7 @@ class BinaryContext { uint32_t DuplicatedJumpTables{0x10000000}; /// Function fragments to skip. - std::vector FragmentsToSkip; + std::unordered_set FragmentsToSkip; /// The runtime library. std::unique_ptr RtLibrary; @@ -236,6 +236,18 @@ public: MIB = std::move(TargetBuilder); } + /// Return function fragments to skip. + const std::unordered_set &getFragmentsToSkip() { + return FragmentsToSkip; + } + + /// Add function fragment to skip + void addFragmentsToSkip(BinaryFunction *Function) { + FragmentsToSkip.insert(Function); + } + + void clearFragmentsToSkip() { FragmentsToSkip.clear(); } + /// Given DWOId returns CU if it exists in DWOCUs. Optional getDWOCU(uint64_t DWOId); @@ -476,15 +488,15 @@ public: /// If \p NextJTAddress is different from zero, it is used as an upper /// bound for jump table memory layout. /// - /// Optionally, populate \p Offsets with jump table entries. The entries + /// Optionally, populate \p Address from jump table entries. The entries /// could be partially populated if the jump table detection fails. bool analyzeJumpTable(const uint64_t Address, const JumpTable::JumpTableType Type, BinaryFunction &BF, const uint64_t NextJTAddress = 0, - JumpTable::OffsetsType *Offsets = nullptr); + JumpTable::AddressesType *EntriesAsAddress = nullptr); /// After jump table locations are established, this function will populate - /// their OffsetEntries based on memory contents. + /// their EntriesAsAddress based on memory contents. void populateJumpTables(); /// Returns a jump table ID and label pointing to the duplicated jump table. @@ -499,12 +511,12 @@ public: /// to function \p BF. std::string generateJumpTableName(const BinaryFunction &BF, uint64_t Address); - /// Free memory used by jump table offsets - void clearJumpTableOffsets() { + /// Free memory used by JumpTable's EntriesAsAddress + void clearJumpTableTempData() { for (auto &JTI : JumpTables) { JumpTable &JT = *JTI.second; - JumpTable::OffsetsType Temp; - Temp.swap(JT.OffsetEntries); + JumpTable::AddressesType Temp; + Temp.swap(JT.EntriesAsAddress); } } /// Return true if the array of bytes represents a valid code padding. diff --git a/bolt/include/bolt/Core/BinaryFunction.h b/bolt/include/bolt/Core/BinaryFunction.h index 2bba810..43ae333 100644 --- a/bolt/include/bolt/Core/BinaryFunction.h +++ b/bolt/include/bolt/Core/BinaryFunction.h @@ -333,9 +333,9 @@ private: /// True if the original entry point was patched. bool IsPatched{false}; - /// True if the function contains jump table with entries pointing to - /// locations in fragments. - bool HasSplitJumpTable{false}; + /// True if the function contains explicit or implicit indirect branch to its + /// split fragments, e.g., split jump table, landing pad in split fragment + bool HasIndirectTargetToSplitFragment{false}; /// True if there are no control-flow edges with successors in other functions /// (i.e. if tail calls have edges to function-local basic blocks). @@ -1437,9 +1437,12 @@ public: /// otherwise processed. bool isPseudo() const { return IsPseudo; } - /// Return true if the function contains a jump table with entries pointing - /// to split fragments. - bool hasSplitJumpTable() const { return HasSplitJumpTable; } + /// Return true if the function contains explicit or implicit indirect branch + /// to its split fragments, e.g., split jump table, landing pad in split + /// fragment. + bool hasIndirectTargetToSplitFragment() const { + return HasIndirectTargetToSplitFragment; + } /// Return true if all CFG edges have local successors. bool hasCanonicalCFG() const { return HasCanonicalCFG; } @@ -1834,7 +1837,9 @@ public: void setIsPatched(bool V) { IsPatched = V; } - void setHasSplitJumpTable(bool V) { HasSplitJumpTable = V; } + void setHasIndirectTargetToSplitFragment(bool V) { + HasIndirectTargetToSplitFragment = V; + } void setHasCanonicalCFG(bool V) { HasCanonicalCFG = V; } diff --git a/bolt/include/bolt/Core/JumpTable.h b/bolt/include/bolt/Core/JumpTable.h index e5f031e..9615025 100644 --- a/bolt/include/bolt/Core/JumpTable.h +++ b/bolt/include/bolt/Core/JumpTable.h @@ -69,9 +69,9 @@ public: /// All the entries as labels. std::vector Entries; - /// All the entries as offsets into a function. Invalid after CFG is built. - using OffsetsType = std::vector; - OffsetsType OffsetEntries; + /// All the entries as absolute addresses. Invalid after disassembly is done. + using AddressesType = std::vector; + AddressesType EntriesAsAddress; /// Map ->