[BOLT] Support multiple parents for split jump table

[nhuhuan]

Summary

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

[rafauler]

bolt/lib/Core/BinaryContext.cpp

645–648

debug code should be guarded under the LLVM_DEBUG macro in the same way as line 625. This line was previously unguarded by mistake.

651–660

same

[rafauler]

Do you have a testcase?

bolt/lib/Core/BinaryContext.cpp

704–705

outdated coment

[Amir]

bolt/lib/Core/BinaryContext.cpp

629–632

I think checking if the first parent is non-simple is fine, but a future-proof solution would be to check if any of parents is non-simple.

667

Let's add curly braces in if and else bodies

[nhuhuan]

bolt/lib/Core/BinaryContext.cpp

629–632

I also thought the same. There are two reasons why I keep it this way:
(a) Not sure about why we need this check.

Possibly the assumption is non-simple fragments are not be optimized, thus we
don't have to make best effort on analyzing it. So it boils down to the meaning of
non-simple. Maksim argues non-simple functions should have complete references,
just that we cannot construct a complete CFG.

(b) The previous calls to analyzeJumpTable and getOrCreateJumpTable already mark

all parents as "HasIndirectTargetToSplitFragment = true". I mistakenly thought that
was the same with all parents being non-simple.

The bottom line is that I will update following your feedbacks.

[Amir]

bolt/lib/Core/BinaryContext.cpp

629–632

I agree with your reasoning. Let's stick to keeping the check for now as it's a safe option, and remove it later separately.

[nhuhuan]

bolt/lib/Core/BinaryContext.cpp

727

There are two main types for FragmentsToSkip: (a) split jump table targets, (b) split landing pad targets.
Note that with our current code, we would need to call skipMarkedFragments() twice for (a) and (b). This
removal is to prepare for the next update where we only invoke skipMarkedFragments() once. To do that
we need to retain all FragmentsToSkip of both types.

[nhuhuan]

bolt/lib/Core/BinaryFunction.cpp

1704

This is a side note. BOLT made two assumptions:
a. Jump table entries are always unsigned int.
b. Jump table entries are arranged moving forward from Jump table base.

It's very often in real-world binaries to use movsl/movsx instead of movzl/movzx,
which seem to suggests against (a). But it is rare to see cases violate (b) from my
experience.

Now keeping (a), it is messy when OffsetEntries point to another fragment whose
appear prior to current function. It will be integer overflow, and this is inconsistent.

[nhuhuan]

Address some feedbacks

[nhuhuan]

bolt/lib/Core/BinaryContext.cpp

704–705

Thanks. I removed UniqueFunctions because it is the same as FragmentsToSkip. Also updated the comment.

[nhuhuan]

Clang-formatted

[nhuhuan]

In D128474#3606727, @rafauler wrote:

Do you have a testcase?

I already created a test case for it: two parents access same jump table whose entries target both parents:
split-func-jump-table-fragment-bidirection.s

[nhuhuan]

Clang-formatted

[nhuhuan]

Update test case: print-cfg to show all parents of a jump table

[nhuhuan]

Fix the printing message to include all parents of a jump table

[nhuhuan]

Rebase

[Amir]

bolt/lib/Core/BinaryContext.cpp

643

Let's move the body under !Success into

LLVM_DEBUG({
  ...
});

block, except llvm_unreachable at the end

832–833

Please remove that print

bolt/test/X86/split-func-jump-table-fragment-bidirection.s

14

[Amir]

bolt/lib/Core/BinaryContext.cpp

629–632

idk how clang-format skipped this

[rafauler]

bolt/lib/Core/BinaryContext.cpp

787–788

Warnings are printed to errs() and not outs()

BOLT-INFO is output to outs(). If this information is just reporting something on the input binary, consider converting it to INFO instead of WARNING, specially if this is supported.

[rafauler]

Thanks Huan for all the work put in this diff. I have a few more comments below.

bolt/include/bolt/Core/BinaryContext.h

239–242

Remove dead code

bolt/lib/Core/BinaryContext.cpp

493–496

I think it's a bit weird to keep calling this "Offsets", and "OffsetEntries" in JumpTable if we are not using offsets anymore, right? We are now using the full address in each entry. Perhaps we should rename this in JumpTable class? Something like "EntriesAsAddresses" in JumpTables.h:73 - 74 (and update comments there)

571

Same renaming here (my motivation here is why are we calling this an offset if this is not an offset anymore)

[rafauler]

bolt/include/bolt/Core/BinaryContext.h

239–242

Now I see it is used in the follow-up diff

[nhuhuan]

bolt/lib/Core/BinaryContext.cpp

571

Offset is a general term.
For PIC, it is the offset to the program start. Definitely not "absolute address".
For NoPIC, it is the offset to process's memory start.

[nhuhuan]

bolt/include/bolt/Core/BinaryContext.h

239–242

Right. The follow-up diff depends on this diff.

[nhuhuan]

Address the feedbacks.

[Amir]

bolt/include/bolt/Core/BinaryContext.h

496

[nhuhuan]

bolt/lib/Core/BinaryFunction.cpp

1703

Using same variable name "EntryOffset" is completely wrong, and may potentially trigger memory over-use!

[nhuhuan]

Update how jump table entries are generated. Allow buildCFG to operate
on non-simple fragments. Address feedbacks.

[nhuhuan]

Clang-formatted.

[Amir]

Looks good, with a couple of final nits.

bolt/lib/Core/BinaryContext.cpp

827

Please keep the verbosity here

bolt/lib/Core/BinaryFunction.cpp

1649

The variables must be upper-cased according to LLVM Style Guide: https://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

1650–1654

[nhuhuan]

Address feedbacks.

[Amir]

LGTM

[nhuhuan]

Fix bugs:
(a) missing builtin_unreachable jump table targets
(b) incorrect jump table duplication

[nhuhuan]

Rebase

bolt/include/bolt/Core/BinaryContext.h

class BinaryContext {
   std::unordered_set<uint64_t> DataPCRelocations;
 
   /// Used in duplicateJumpTable() to uniquely identify a JT clone
   /// Start our IDs with a high number so getJumpTableContainingAddress checks
   /// with size won't overflow
   uint32_t DuplicatedJumpTables{0x10000000};
 
   /// Function fragments to skip.
-  std::vector<BinaryFunction *> FragmentsToSkip;
+  std::unordered_set<BinaryFunction *> FragmentsToSkip;
 
   /// The runtime library.
   std::unique_ptr<RuntimeLibrary> RtLibrary;
 
   /// DWP Context.
   std::shared_ptr<DWARFContext> DWPContext;
 
   /// A map of DWO Ids to CUs.
public:
   /// overwritten, but it is okay to re-generate debug info for them.
   std::set<const DWARFUnit *> ProcessedCUs;
 
   // Setup MCPlus target builder
   void initializeTarget(std::unique_ptr<MCPlusBuilder> TargetBuilder) {
     MIB = std::move(TargetBuilder);
   }
 
+  /// Return function fragments to skip.
+  const std::unordered_set<BinaryFunction *> &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<DWARFUnit *> getDWOCU(uint64_t DWOId);
 
   /// Returns DWOContext if it exists.
   DWARFContext *getDWOContext() const;
 
   /// Get Number of DWOCUs in a map.
   uint32_t getNumDWOCUs() { return DWOCUs.size(); }
public:
   /// Analyze a possible jump table of type \p Type at a given \p Address.
   /// \p BF is a function referencing the jump table.
   /// Return true if the jump table was detected at \p Address, and false
   /// otherwise.
   ///
   /// 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.
   /// Ordinarily, jump tables are identified by their address in the input
   /// binary. We return an ID with the high bit set to differentiate it from
   /// regular addresses, avoiding conflicts with standard jump tables.
   std::pair<uint64_t, const MCSymbol *>
   duplicateJumpTable(BinaryFunction &Function, JumpTable *JT,
                      const MCSymbol *OldLabel);
 
   /// Generate a unique name for jump table at a given \p Address belonging
   /// 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.
   bool hasValidCodePadding(const BinaryFunction &BF);
 
   /// Verify padding area between functions, and adjust max function size
   /// accordingly.
   void adjustCodePadding();

bolt/include/bolt/Core/BinaryFunction.h

private:
 
   /// Indicate that the function body has Pseudo Probe
   bool HasPseudoProbe{BC.getUniqueSectionByName(".pseudo_probe_desc") &&
                       BC.getUniqueSectionByName(".pseudo_probe")};
 
   /// 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).
   /// Set to false by SCTC. Dynostats can't be reliably computed for
   /// functions with non-canonical CFG.
   /// This attribute is only valid when hasCFG() == true.
   bool HasCanonicalCFG{true};
 
public:
 
   /// Return true if the function should be ignored for optimization purposes.
   bool isIgnored() const { return IsIgnored; }
 
   /// Return true if the function should not be disassembled, emitted, or
   /// 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; }
 
   /// Return true if the original function code has all necessary relocations
   /// to track addresses of functions emitted to new locations.
   bool hasExternalRefRelocations() const { return HasExternalRefRelocations; }
 
BinaryFunction &setHasProfileAvailable(bool V = true) {
     return *this;
   }
 
   /// Mark function that should not be emitted.
   void setIgnored();
 
   void setIsPatched(bool V) { IsPatched = V; }
 
-  void setHasSplitJumpTable(bool V) { HasSplitJumpTable = V; }
+  void setHasIndirectTargetToSplitFragment(bool V) {
+    HasIndirectTargetToSplitFragment = V;
+  }
 
   void setHasCanonicalCFG(bool V) { HasCanonicalCFG = V; }
 
   void setFolded(BinaryFunction *BF) { FoldedIntoFunction = BF; }
 
   BinaryFunction &setPersonalityFunction(uint64_t Addr) {
     assert(!PersonalityFunction && "can't set personality function twice");
     PersonalityFunction = BC.getOrCreateGlobalSymbol(Addr, "FUNCat");

bolt/include/bolt/Core/JumpTable.h

public:
   size_t OutputEntrySize;
 
   /// The type of this jump table.
   JumpTableType Type;
 
   /// All the entries as labels.
   std::vector<MCSymbol *> Entries;
 
-  /// All the entries as offsets into a function. Invalid after CFG is built.
-  using OffsetsType = std::vector<uint64_t>;
-  OffsetsType OffsetEntries;
+  /// All the entries as absolute addresses. Invalid after disassembly is done.
+  using AddressesType = std::vector<uint64_t>;
+  AddressesType EntriesAsAddress;
 
   /// Map <Offset> -> <Label> used for embedded jump tables. Label at 0 offset
   /// is the main label for the jump table.
   using LabelMapType = std::map<unsigned, MCSymbol *>;
   LabelMapType Labels;
 
   /// Dynamic number of times each entry in the table was referenced.
   /// Identical entries will have a shared count (identical for every
   /// entry in the set).
   std::vector<JumpInfo> Counts;
 
   /// Total number of times this jump table was used.
   uint64_t Count{0};
 
   /// BinaryFunction this jump tables belongs to.
-  BinaryFunction *Parent{nullptr};
+  SmallVector<BinaryFunction *, 1> Parents;
 
 private:
   /// Constructor should only be called by a BinaryContext.
   JumpTable(MCSymbol &Symbol, uint64_t Address, size_t EntrySize,
-            JumpTableType Type, LabelMapType &&Labels, BinaryFunction &BF,
-            BinarySection &Section);
+            JumpTableType Type, LabelMapType &&Labels, BinarySection &Section);
 
 public:
   /// Return the size of the jump table.
   uint64_t getSize() const {
-    return std::max(OffsetEntries.size(), Entries.size()) * EntrySize;
+    return std::max(EntriesAsAddress.size(), Entries.size()) * EntrySize;
   }
 
   const MCSymbol *getFirstLabel() const {
     assert(Labels.count(0) != 0 && "labels must have an entry at 0");
     return Labels.find(0)->second;
   }
 
   /// Get the indexes for symbol entries that correspond to the jump table

bolt/lib/Core/BinaryContext.cpp

for (StringRef Name : Parent.getNames()) {
     std::string NamePrefix = Regex::escape(NameResolver::restore(Name));
     std::string NameRegex = Twine(NamePrefix, "\\.cold(\\.[0-9]+)?").str();
     if (Fragment.hasRestoredNameRegex(NameRegex))
       return true;
   }
   return false;
 }
 
-bool BinaryContext::analyzeJumpTable(const uint64_t Address,
-                                     const JumpTable::JumpTableType Type,
-                                     BinaryFunction &BF,
-                                     const uint64_t NextJTAddress,
-                                     JumpTable::OffsetsType *Offsets) {
+bool BinaryContext::analyzeJumpTable(
+    const uint64_t Address, const JumpTable::JumpTableType Type,
+    BinaryFunction &BF, const uint64_t NextJTAddress,
+    JumpTable::AddressesType *EntriesAsAddress) {
   // Is one of the targets __builtin_unreachable?
   bool HasUnreachable = false;
 
   // Number of targets other than __builtin_unreachable.
   uint64_t NumRealEntries = 0;
 
-  constexpr uint64_t INVALID_OFFSET = std::numeric_limits<uint64_t>::max();
-  auto addOffset = [&](uint64_t Offset) {
-    if (Offsets)
-      Offsets->emplace_back(Offset);
+  auto addEntryAddress = [&](uint64_t EntryAddress) {
+    if (EntriesAsAddress)
+      EntriesAsAddress->emplace_back(EntryAddress);
   };
 
   auto doesBelongToFunction = [&](const uint64_t Addr,
                                   BinaryFunction *TargetBF) -> bool {
     if (BF.containsAddress(Addr))
       return true;
     // Nothing to do if we failed to identify the containing function.
     if (!TargetBF)
for (uint64_t EntryAddress = Address; EntryAddress <= UpperBound - EntrySize;
 
     const uint64_t Value =
         (Type == JumpTable::JTT_PIC)
             ? Address + *getSignedValueAtAddress(EntryAddress, EntrySize)
             : *getPointerAtAddress(EntryAddress);
 
     // __builtin_unreachable() case.
     if (Value == BF.getAddress() + BF.getSize()) {
-      addOffset(Value - BF.getAddress());
+      addEntryAddress(Value);
       HasUnreachable = true;
       LLVM_DEBUG(dbgs() << "OK: __builtin_unreachable\n");
       continue;
     }
 
     // Function or one of its fragments.
     BinaryFunction *TargetBF = getBinaryFunctionContainingAddress(Value);
 
for (uint64_t EntryAddress = Address; EntryAddress <= UpperBound - EntrySize;
     if (TargetBF->getState() == BinaryFunction::State::Disassembled &&
         !TargetBF->getInstructionAtOffset(Value - TargetBF->getAddress())) {
       LLVM_DEBUG(dbgs() << "FAIL: no instruction at this offset\n");
       break;
     }
 
     ++NumRealEntries;
 
-    if (TargetBF == &BF) {
-      // Address inside the function.
-      addOffset(Value - TargetBF->getAddress());
-      LLVM_DEBUG(dbgs() << "OK: real entry\n");
-    } else {
-      // Address in split fragment.
-      BF.setHasSplitJumpTable(true);
-      // Add invalid offset for proper identification of jump table size.
-      addOffset(INVALID_OFFSET);
-      LLVM_DEBUG(dbgs() << "OK: address in split fragment "
-                        << TargetBF->getPrintName() << '\n');
-    }
+    if (TargetBF != &BF)
+      BF.setHasIndirectTargetToSplitFragment(true);
+    addEntryAddress(Value);
   }
 
   // It's a jump table if the number of real entries is more than 1, or there's
   // one real entry and "unreachable" targets. If there are only multiple
   // "unreachable" targets, then it's not a jump table.
   return NumRealEntries + HasUnreachable >= 2;
 }
 
 void BinaryContext::populateJumpTables() {
   LLVM_DEBUG(dbgs() << "DataPCRelocations: " << DataPCRelocations.size()
                     << '\n');
   for (auto JTI = JumpTables.begin(), JTE = JumpTables.end(); JTI != JTE;
        ++JTI) {
     JumpTable *JT = JTI->second;
-    BinaryFunction &BF = *JT->Parent;
 
-    if (!BF.isSimple())
+    bool NonSimpleParent = false;
+    for (BinaryFunction *BF : JT->Parents)
+      NonSimpleParent |= !BF->isSimple();
+    if (NonSimpleParent)
       continue;
 
     uint64_t NextJTAddress = 0;
     auto NextJTI = std::next(JTI);
     if (NextJTI != JTE)
       NextJTAddress = NextJTI->second->getAddress();
 
-    const bool Success = analyzeJumpTable(JT->getAddress(), JT->Type, BF,
-                                          NextJTAddress, &JT->OffsetEntries);
+    const bool Success =
+        analyzeJumpTable(JT->getAddress(), JT->Type, *(JT->Parents[0]),
+                         NextJTAddress, &JT->EntriesAsAddress);
     if (!Success) {
-      dbgs() << "failed to analyze jump table in function " << BF << '\n';
+      LLVM_DEBUG(ListSeparator LS;
+                 dbgs() << "failed to analyze jump table in function ";
+                 for (BinaryFunction *Frag
+                      : JT->Parents) dbgs()
+                 << LS << *Frag;
+                 dbgs() << '\n';);
       JT->print(dbgs());
       if (NextJTI != JTE) {
+        LLVM_DEBUG(ListSeparator LS;
                    dbgs() << "next jump table at 0x"
                           << Twine::utohexstr(NextJTI->second->getAddress())
-               << " belongs to function " << *NextJTI->second->Parent << '\n';
+                          << " belongs to function ";
+                   for (BinaryFunction *Frag
+                        : NextJTI->second->Parents) dbgs()
+                   << LS << *Frag;
+                   dbgs() << "\n";);
         NextJTI->second->print(dbgs());
       }
       llvm_unreachable("jump table heuristic failure");
     }
-
-    for (uint64_t EntryOffset : JT->OffsetEntries) {
-      if (EntryOffset == BF.getSize())
-        BF.IgnoredBranches.emplace_back(EntryOffset, BF.getSize());
-      else
-        BF.registerReferencedOffset(EntryOffset);
+    for (BinaryFunction *Frag : JT->Parents) {
+      for (uint64_t EntryAddress : JT->EntriesAsAddress)
+        // if target is builtin_unreachable
+        if (EntryAddress == Frag->getAddress() + Frag->getSize()) {
+          Frag->IgnoredBranches.emplace_back(EntryAddress - Frag->getAddress(),
+                                             Frag->getSize());
+        } else if (EntryAddress >= Frag->getAddress() &&
+                   EntryAddress < Frag->getAddress() + Frag->getSize()) {
+          Frag->registerReferencedOffset(EntryAddress - Frag->getAddress());
+        }
     }
 
     // In strict mode, erase PC-relative relocation record. Later we check that
     // all such records are erased and thus have been accounted for.
     if (opts::StrictMode && JT->Type == JumpTable::JTT_PIC) {
       for (uint64_t Address = JT->getAddress();
            Address < JT->getAddress() + JT->getSize();
            Address += JT->EntrySize) {
         DataPCRelocations.erase(DataPCRelocations.find(Address));
       }
     }
 
     // Mark to skip the function and all its fragments.
-    if (BF.hasSplitJumpTable())
-      FragmentsToSkip.push_back(&BF);
+    for (BinaryFunction *Frag : JT->Parents)
+      if (Frag->hasIndirectTargetToSplitFragment())
+        addFragmentsToSkip(Frag);
   }
 
   if (opts::StrictMode && DataPCRelocations.size()) {
     LLVM_DEBUG({
       dbgs() << DataPCRelocations.size()
              << " unclaimed PC-relative relocations left in data:\n";
       for (uint64_t Reloc : DataPCRelocations)
         dbgs() << Twine::utohexstr(Reloc) << '\n';
     });
     assert(0 && "unclaimed PC-relative relocations left in data\n");
   }
   clearList(DataPCRelocations);
 }
 
 void BinaryContext::skipMarkedFragments() {
-  // Unique functions in the vector.
-  std::unordered_set<BinaryFunction *> UniqueFunctions(FragmentsToSkip.begin(),
-                                                       FragmentsToSkip.end());
-  // Copy the functions back to FragmentsToSkip.
-  FragmentsToSkip.assign(UniqueFunctions.begin(), UniqueFunctions.end());
+  std::vector<BinaryFunction *> FragmentQueue;
+  // Copy the functions to FragmentQueue.
+  FragmentQueue.assign(FragmentsToSkip.begin(), FragmentsToSkip.end());
   auto addToWorklist = [&](BinaryFunction *Function) -> void {
-    if (UniqueFunctions.count(Function))
+    if (FragmentsToSkip.count(Function))
       return;
-    FragmentsToSkip.push_back(Function);
-    UniqueFunctions.insert(Function);
+    FragmentQueue.push_back(Function);
+    addFragmentsToSkip(Function);
   };
   // Functions containing split jump tables need to be skipped with all
   // fragments (transitively).
-  for (size_t I = 0; I != FragmentsToSkip.size(); I++) {
-    BinaryFunction *BF = FragmentsToSkip[I];
-    assert(UniqueFunctions.count(BF) &&
+  for (size_t I = 0; I != FragmentQueue.size(); I++) {
+    BinaryFunction *BF = FragmentQueue[I];
+    assert(FragmentsToSkip.count(BF) &&
            "internal error in traversing function fragments");
     if (opts::Verbosity >= 1)
       errs() << "BOLT-WARNING: Ignoring " << BF->getPrintName() << '\n';
     BF->setSimple(false);
-    BF->setHasSplitJumpTable(true);
+    BF->setHasIndirectTargetToSplitFragment(true);
 
     llvm::for_each(BF->Fragments, addToWorklist);
     llvm::for_each(BF->ParentFragments, addToWorklist);
   }
   if (!FragmentsToSkip.empty())
     errs() << "BOLT-WARNING: skipped " << FragmentsToSkip.size() << " function"
            << (FragmentsToSkip.size() == 1 ? "" : "s")
            << " due to cold fragments\n";
-  FragmentsToSkip.clear();
 }
 
 MCSymbol *BinaryContext::getOrCreateGlobalSymbol(uint64_t Address, Twine Prefix,
                                                  uint64_t Size,
                                                  uint16_t Alignment,
                                                  unsigned Flags) {
   auto Itr = BinaryDataMap.find(Address);
   if (Itr != BinaryDataMap.end()) {

 
 const MCSymbol *
 BinaryContext::getOrCreateJumpTable(BinaryFunction &Function, uint64_t Address,
                                     JumpTable::JumpTableType Type) {
   auto isFragmentOf = [](BinaryFunction *Fragment, BinaryFunction *Parent) {
     return (Fragment->isFragment() && Fragment->isParentFragment(Parent));
   };
 
+  // Two fragments of same function access same jump table
   if (JumpTable *JT = getJumpTableContainingAddress(Address)) {
     assert(JT->Type == Type && "jump table types have to match");
-    bool HasMultipleParents = isFragmentOf(JT->Parent, &Function) ||
-                              isFragmentOf(&Function, JT->Parent);
-    assert((JT->Parent == &Function || HasMultipleParents) &&
-           "cannot re-use jump table of a different function");
     assert(Address == JT->getAddress() && "unexpected non-empty jump table");
 
-    // Flush OffsetEntries with INVALID_OFFSET if multiple parents
+    // Prevent associating a jump table to a specific fragment twice.
+    // This simple check arises from the assumption: no more than 2 fragments.
+    if (JT->Parents.size() == 1 && JT->Parents[0] != &Function) {
+      bool SameFunction = isFragmentOf(JT->Parents[0], &Function) ||
+                          isFragmentOf(&Function, JT->Parents[0]);
+      assert(SameFunction &&
+             "cannot re-use jump table of a different function");
       // Duplicate the entry for the parent function for easy access
-    if (HasMultipleParents) {
+      JT->Parents.push_back(&Function);
       if (opts::Verbosity > 2) {
-        outs() << "BOLT-WARNING: Multiple fragments access same jump table: "
-               << JT->Parent->getPrintName() << "; " << Function.getPrintName()
-               << "\n";
-      }
-      constexpr uint64_t INVALID_OFFSET = std::numeric_limits<uint64_t>::max();
-      for (unsigned I = 0; I < JT->OffsetEntries.size(); ++I)
-        JT->OffsetEntries[I] = INVALID_OFFSET;
+        outs() << "BOLT-INFO: Multiple fragments access same jump table: "
+               << JT->Parents[0]->getPrintName() << "; "
+               << Function.getPrintName() << "\n";
+        JT->print(outs());
+      }
       Function.JumpTables.emplace(Address, JT);
+      JT->Parents[0]->setHasIndirectTargetToSplitFragment(true);
+      JT->Parents[1]->setHasIndirectTargetToSplitFragment(true);
     }
+
+    bool IsJumpTableParent = false;
+    for (BinaryFunction *Frag : JT->Parents)
+      if (Frag == &Function)
+        IsJumpTableParent = true;
+    assert(IsJumpTableParent &&
+           "cannot re-use jump table of a different function");
     return JT->getFirstLabel();
   }
 
   // Re-use the existing symbol if possible.
   MCSymbol *JTLabel = nullptr;
   if (BinaryData *Object = getBinaryDataAtAddress(Address)) {
     if (!isInternalSymbolName(Object->getSymbol()->getName()))
       JTLabel = Object->getSymbol();
   }
 
   const uint64_t EntrySize = getJumpTableEntrySize(Type);
   if (!JTLabel) {
     const std::string JumpTableName = generateJumpTableName(Function, Address);
     JTLabel = registerNameAtAddress(JumpTableName, Address, 0, EntrySize);
   }
 
   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: creating jump table " << JTLabel->getName()
                     << " in function " << Function << '\n');
 
   JumpTable *JT = new JumpTable(*JTLabel, Address, EntrySize, Type,
-                                JumpTable::LabelMapType{{0, JTLabel}}, Function,
+                                JumpTable::LabelMapType{{0, JTLabel}},
                                 *getSectionForAddress(Address));
+  JT->Parents.push_back(&Function);
+  if (opts::Verbosity > 2)
+    JT->print(outs());
   JumpTables.emplace(Address, JT);
 
   // Duplicate the entry for the parent function for easy access.
   Function.JumpTables.emplace(Address, JT);
-
   return JTLabel;
 }
 
 std::pair<uint64_t, const MCSymbol *>
 BinaryContext::duplicateJumpTable(BinaryFunction &Function, JumpTable *JT,
                                   const MCSymbol *OldLabel) {
   auto L = scopeLock();
   unsigned Offset = 0;
   bool Found = false;
   for (std::pair<const unsigned, MCSymbol *> Elmt : JT->Labels) {
     if (Elmt.second != OldLabel)
       continue;
     Offset = Elmt.first;
     Found = true;
     break;
   }
   assert(Found && "Label not found");
   (void)Found;
   MCSymbol *NewLabel = Ctx->createNamedTempSymbol("duplicatedJT");
   JumpTable *NewJT =
       new JumpTable(*NewLabel, JT->getAddress(), JT->EntrySize, JT->Type,
-                    JumpTable::LabelMapType{{Offset, NewLabel}}, Function,
+                    JumpTable::LabelMapType{{Offset, NewLabel}},
                     *getSectionForAddress(JT->getAddress()));
+  NewJT->Parents = JT->Parents;
   NewJT->Entries = JT->Entries;
   NewJT->Counts = JT->Counts;
   uint64_t JumpTableID = ++DuplicatedJumpTables;
   // Invert it to differentiate from regular jump tables whose IDs are their
   // addresses in the input binary memory space
   JumpTableID = ~JumpTableID;
   JumpTables.emplace(JumpTableID, NewJT);
   Function.JumpTables.emplace(JumpTableID, NewJT);

bolt/lib/Core/BinaryFunction.cpp

for (auto &JTI : JumpTables) {
     JumpTable &JT = *JTI.second;
     if (JT.Type == JumpTable::JTT_PIC && opts::JumpTables == JTS_BASIC) {
       opts::JumpTables = JTS_MOVE;
       outs() << "BOLT-INFO: forcing -jump-tables=move as PIC jump table was "
                 "detected in function "
              << *this << '\n';
     }
     if (JT.Entries.empty()) {
-      for (unsigned I = 0; I < JT.OffsetEntries.size(); ++I) {
+      bool HasOneParent = (JT.Parents.size() == 1);
+      for (unsigned I = 0; I < JT.EntriesAsAddress.size(); ++I) {
+        uint64_t EntryAddress = JT.EntriesAsAddress[I];
+        // builtin_unreachable does not belong to any function
+        // Need to handle separately
+        bool IsBuiltIn = false;
+        for (BinaryFunction *Parent : JT.Parents) {
+          if (EntryAddress == Parent->getAddress() + Parent->getSize()) {
+            IsBuiltIn = true;
+            // Specify second parameter as true to accept builtin_unreachable
+            MCSymbol *Label = getOrCreateLocalLabel(EntryAddress, true);
+            JT.Entries.push_back(Label);
+            break;
+          }
+        }
+        if (IsBuiltIn)
+          continue;
+        // Create local label for targets cannot be reached by other fragments
+        // Otherwise, secondary entry point to target function
+        BinaryFunction *TargetBF =
+            BC.getBinaryFunctionContainingAddress(EntryAddress);
+        if (TargetBF->getAddress() != EntryAddress) {
           MCSymbol *Label =
-            getOrCreateLocalLabel(getAddress() + JT.OffsetEntries[I],
-                                  /*CreatePastEnd*/ true);
+              (HasOneParent && TargetBF == this)
+                  ? getOrCreateLocalLabel(JT.EntriesAsAddress[I], true)
+                  : TargetBF->addEntryPointAtOffset(EntryAddress -
+                                                    TargetBF->getAddress());
           JT.Entries.push_back(Label);
         }
       }
+    }
 
     const uint64_t BDSize =
         BC.getBinaryDataAtAddress(JT.getAddress())->getSize();
     if (!BDSize) {
       BC.setBinaryDataSize(JT.getAddress(), JT.getSize());
     } else {
       assert(BDSize >= JT.getSize() &&
              "jump table cannot be larger than the containing object");
     }
   }
 
   // Add TakenBranches from JumpTables.
   //
   // We want to do it after initial processing since we don't know jump tables'
   // boundaries until we process them all.
   for (auto &JTSite : JTSites) {
     const uint64_t JTSiteOffset = JTSite.first;
     const uint64_t JTAddress = JTSite.second;
     const JumpTable *JT = getJumpTableContainingAddress(JTAddress);
     assert(JT && "cannot find jump table for address");
 
     uint64_t EntryOffset = JTAddress - JT->getAddress();
     while (EntryOffset < JT->getSize()) {
-      uint64_t TargetOffset = JT->OffsetEntries[EntryOffset / JT->EntrySize];
+      uint64_t EntryAddress = JT->EntriesAsAddress[EntryOffset / JT->EntrySize];
+      uint64_t TargetOffset = EntryAddress - getAddress();
       if (TargetOffset < getSize()) {
         TakenBranches.emplace_back(JTSiteOffset, TargetOffset);
 
         if (opts::StrictMode)
           registerReferencedOffset(TargetOffset);
       }
 
       EntryOffset += JT->EntrySize;
 
       // A label at the next entry means the end of this jump table.
       if (JT->Labels.count(EntryOffset))
         break;

bolt/lib/Core/JumpTable.cpp

 
 namespace opts {
 extern cl::opt<JumpTableSupportLevel> JumpTables;
 extern cl::opt<unsigned> Verbosity;
 } // namespace opts
 
 bolt::JumpTable::JumpTable(MCSymbol &Symbol, uint64_t Address, size_t EntrySize,
                            JumpTableType Type, LabelMapType &&Labels,
-                           BinaryFunction &BF, BinarySection &Section)
+                           BinarySection &Section)
     : BinaryData(Symbol, Address, 0, EntrySize, Section), EntrySize(EntrySize),
-      OutputEntrySize(EntrySize), Type(Type), Labels(Labels), Parent(&BF) {}
+      OutputEntrySize(EntrySize), Type(Type), Labels(Labels) {}
 
 std::pair<size_t, size_t>
 bolt::JumpTable::getEntriesForAddress(const uint64_t Addr) const {
   // Check if this is not an address, but a cloned JT id
   if ((int64_t)Addr < 0ll)
     return std::make_pair(0, Entries.size());
 
   const uint64_t InstOffset = Addr - getAddress();
for (MCSymbol *Entry : Entries) {
     EntryOffset += EntrySize;
   }
 }
 
 void bolt::JumpTable::print(raw_ostream &OS) const {
   uint64_t Offset = 0;
   if (Type == JTT_PIC)
     OS << "PIC ";
-  OS << "Jump table " << getName() << " for function " << *Parent << " at 0x"
-     << Twine::utohexstr(getAddress()) << " with a total count of " << Count
-     << ":\n";
-  for (const uint64_t EntryOffset : OffsetEntries)
-    OS << "  0x" << Twine::utohexstr(EntryOffset) << '\n';
+  ListSeparator LS;
+
+  OS << "Jump table " << getName() << " for function ";
+  for (BinaryFunction *Frag : Parents)
+    OS << LS << *Frag;
+  OS << " at 0x" << Twine::utohexstr(getAddress()) << " with a total count of "
+     << Count << ":\n";
+  for (const uint64_t EntryAddress : EntriesAsAddress)
+    OS << "  absolute offset: 0x" << Twine::utohexstr(EntryAddress) << '\n';
   for (const MCSymbol *Entry : Entries) {
     auto LI = Labels.find(Offset);
     if (Offset && LI != Labels.end()) {
       OS << "Jump Table " << LI->second->getName() << " at 0x"
          << Twine::utohexstr(getAddress() + Offset)
          << " (possibly part of larger jump table):\n";
     }
     OS << format("  0x%04" PRIx64 " : ", Offset) << Entry->getName();

bolt/lib/Passes/AsmDump.cpp

default:
     MAP.emitCFIInstruction(*CFIInstr);
   }
 }
 
 void dumpJumpTableFdata(raw_ostream &OS, const BinaryFunction &BF,
                         const MCInst &Instr, const std::string &BranchLabel) {
   StringRef FunctionName = BF.getOneName();
   const JumpTable *JT = BF.getJumpTable(Instr);
-  for (const uint64_t EntryOffset : JT->OffsetEntries) {
-    auto LI = JT->Labels.find(EntryOffset);
-    StringRef TargetName = LI->second->getName();
-    const uint64_t Mispreds = JT->Counts[EntryOffset].Mispreds;
-    const uint64_t Count = JT->Counts[EntryOffset].Count;
+  for (uint32_t i = 0; i < JT->Entries.size(); ++i) {
+    StringRef TargetName = JT->Entries[i]->getName();
+    const uint64_t Mispreds = JT->Counts[i].Mispreds;
+    const uint64_t Count = JT->Counts[i].Count;
     OS << "# FDATA: 1 " << FunctionName << " #" << BranchLabel << "# "
        << "1 " << FunctionName << " #" << TargetName << "# " << Mispreds << " "
        << Count << '\n';
   }
 }
 
 void dumpTailCallFdata(raw_ostream &OS, const BinaryFunction &BF,
                        const MCInst &Instr, const std::string &BranchLabel) {

bolt/lib/Rewrite/RewriteInstance.cpp

if (!Function.disassemble()) {
       continue;
     }
 
     if (opts::PrintAll || opts::PrintDisasm)
       Function.print(outs(), "after disassembly", true);
   }
 
   BC->processInterproceduralReferences();
-  BC->clearJumpTableOffsets();
   BC->populateJumpTables();
-  BC->skipMarkedFragments();
 
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     if (!shouldDisassemble(Function))
       continue;
 
     Function.postProcessEntryPoints();
     Function.postProcessJumpTables();
   }
 
+  BC->clearJumpTableTempData();
   BC->adjustCodePadding();
 
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     if (!shouldDisassemble(Function))
       continue;
 
     if (!Function.isSimple()) {
       assert((!BC->HasRelocations || Function.getSize() == 0 ||
-              Function.hasSplitJumpTable()) &&
+              Function.hasIndirectTargetToSplitFragment()) &&
              "unexpected non-simple function in relocation mode");
       continue;
     }
 
     // Fill in CFI information for this function
     if (!Function.trapsOnEntry() && !CFIRdWrt->fillCFIInfoFor(Function)) {
       if (BC->HasRelocations) {
         BC->exitWithBugReport("unable to fill CFI.", Function);
ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
       *BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,
       SkipPredicate, "disassembleFunctions-buildCFG",
       /*ForceSequential*/ opts::SequentialDisassembly || opts::PrintAll);
 
   BC->postProcessSymbolTable();
 }
 
 void RewriteInstance::postProcessFunctions() {
+  // We mark fragments as non-simple here, not during disassembly,
+  // So we can build their CFGs.
+  BC->skipMarkedFragments();
+  BC->clearFragmentsToSkip();
+
   BC->TotalScore = 0;
   BC->SumExecutionCount = 0;
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     if (Function.empty())
       continue;
 

bolt/test/X86/jump-table-move.s

+# REQUIRES: system-linux
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
+# RUN: %clang %cflags -no-pie %t.o -o %t.exe -Wl,-q
+# RUN: llvm-bolt %t.exe -o %t.out --lite=0 -v=1 --jump-tables=move 2>&1 | FileCheck %s
+
+# CHECK-NOT: unclaimed PC-relative relocations left in data
+# CHECK: BOLT-INFO: marking main.cold.1 as a fragment of main
+# CHECK: BOLT-WARNING: Ignoring main.cold.1
+# CHECK: BOLT-WARNING: Ignoring main
+
+  .text
+  .globl main
+  .type main, %function
+  .p2align 2
+main:
+    cmpl  $0x67, %edi
+    jne main.cold.1
+LBB0:
+    retq
+.size main, .-main
+
+  .globl main.cold.1
+  .type main.cold.1, %function
+  .p2align 2
+main.cold.1:
+    jmpq  *JUMP_TABLE(,%rcx,8)
+.size main.cold.1, .-main.cold.1
+
+  .rodata
+  .globl JUMP_TABLE
+JUMP_TABLE:
+  .quad LBB0
+  .quad LBB0

bolt/test/X86/split-func-jump-table-fragment-bidirection.s

 # This reproduces an issue where two fragments of same function access same
 # jump table, which means at least one fragment visits the other, i.e., one
 # of them has split jump table. As a result, all of them will be marked as
 # non-simple function.
 
 # REQUIRES: system-linux
 
 # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
 # RUN: llvm-strip --strip-unneeded %t.o
 # RUN: %clang %cflags %t.o -o %t.exe -Wl,-q
-# RUN: llvm-bolt -v=3 %t.exe -o %t.out 2>&1 | FileCheck %s
+# RUN: llvm-bolt -print-cfg -v=3 %t.exe -o %t.out 2>&1 | FileCheck %s
 
-# CHECK: BOLT-WARNING: Multiple fragments access same jump table: main; main.cold.1
+# CHECK: BOLT-INFO: Multiple fragments access same jump table: main; main.cold.1
+# CHECK: PIC Jump table JUMP_TABLE1 for function main, main.cold.1 at {{.*}}  with a total count of 0:
 
   .text
   .globl main
   .type main, %function
   .p2align 2
 main:
 LBB0:
   andl $0xf, %ecx