[BOLT] Support jump table entry to sibling's builtin_unreachable

[nhuhuan]

Summary

Previously, only builtin_unreachable of functions accessing jump table
are handled. For split function where jump table could also target the
builtin_unreachable of other sibling fragments, this constraint will
thwart valid entries after such builtin_unreachable entry, and lead to
incorrect jump table analysis results.

This update extend support for builtin_unreachable in sibling fragment.

Test Plan:

ninja check-bolt

[nhuhuan]

Support builtin_unreachable when another function is placed
after the sibling fragment

bolt/include/bolt/Core/BinaryFunction.h

private:
   uint64_t ImageSize{0};
 
   /// Name for the section this function code should reside in.
   std::string CodeSectionName;
 
   /// Name for the corresponding cold code section.
   std::string ColdCodeSectionName;
 
-  /// Parent function fragment for split function fragments.
-  SmallPtrSet<BinaryFunction *, 1> ParentFragments;
-
   /// Indicate if the function body was folded into another function.
   /// Used by ICF optimization.
   BinaryFunction *FoldedIntoFunction{nullptr};
 
-  /// All fragments for a parent function.
-  SmallPtrSet<BinaryFunction *, 1> Fragments;
-
   /// The profile data for the number of times the function was executed.
   uint64_t ExecutionCount{COUNT_NO_PROFILE};
 
   /// Profile match ratio.
   float ProfileMatchRatio{0.0f};
 
   /// Raw branch count for this function in the profile
   uint64_t RawBranchCount{0};
public:
 
   inline iterator_range<cfi_iterator> cie() {
     return iterator_range<cfi_iterator>(cie_begin(), cie_end());
   }
   inline iterator_range<const_cfi_iterator> cie() const {
     return iterator_range<const_cfi_iterator>(cie_begin(), cie_end());
   }
 
+  /// Parent function fragment for split function fragments.
+  SmallPtrSet<BinaryFunction *, 1> ParentFragments;
+
+  /// All fragments for a parent function.
+  SmallPtrSet<BinaryFunction *, 1> Fragments;
+
   /// Iterate over all jump tables associated with this function.
   iterator_range<std::map<uint64_t, JumpTable *>::const_iterator>
   jumpTables() const {
     return make_range(JumpTables.begin(), JumpTables.end());
   }
 
   /// Return relocation associated with a given \p Offset in the function,
   /// or nullptr if no such relocation exists.

bolt/lib/Core/BinaryBasicBlock.cpp

for (BinaryBasicBlock *Succ : Successors) {
         errs() << "BOLT-WARNING: Jump table successor " << Succ->getName()
                << " not contained in the jump table.\n";
       }
     }
     // If there are any leftover entries in the jump table, they
     // must be one of the function end labels.
     if (Valid) {
       for (const MCSymbol *Sym : UniqueSyms) {
-        Valid &= (Sym == Function->getFunctionEndLabel() ||
-                  Sym == Function->getFunctionColdEndLabel());
+        std::unordered_set<BinaryFunction *> Siblings;
+        Siblings.insert(Function->ParentFragments.begin(),
+                        Function->ParentFragments.end());
+        Siblings.insert(Function->Fragments.begin(), Function->Fragments.end());
+        Siblings.insert(Function);
+
+        Valid = false;
+        for (BinaryFunction *BF : Siblings)
+          Valid |= (Sym == BF->getFunctionEndLabel() ||
+              Sym == BF->getFunctionColdEndLabel());
+
         if (!Valid) {
           errs() << "BOLT-WARNING: Jump table contains illegal entry: "
                  << Sym->getName() << "\n";
         }
       }
     }
   } else {
     // Unknown control flow.

bolt/lib/Core/BinaryContext.cpp

bool isPotentialFragmentByName(BinaryFunction &Fragment,
   return false;
 }
 
 bool BinaryContext::isValidJumpTableEntry(
     uint64_t Address, BinaryFunction &Function,
     BinaryFunction *&ValidExternalTargetBF) {
 
   BinaryFunction *TargetBF = getBinaryFunctionContainingAddress(Address);
+  BinaryFunction *PredBF = getBinaryFunctionContainingAddress(Address - 1);
+
+  // Property 0: Entry target builtin_unreachable of sibling fragments
+  if (!IsStripped && PredBF != nullptr && PredBF != TargetBF) {
+    // Assumption: sibling fragments cannot be placed next to each other
+    // Builtin unreachable of same function
+    if (PredBF == &Function)
+      return true;
+    // Builtin unreachable of sibling fragments
+    else if (Function.isFragment() && registerFragment(Function, *PredBF))
+      return true;
+    else if (PredBF->isFragment() && registerFragment(*PredBF, Function))
+      return true;
+  }
 
   // Property 1: Entry must target a valid function body
   if (!TargetBF) {
     LLVM_DEBUG(dbgs() << "Invalid jump table entry candidate: not point to any "
                       << "function\n";);
     return false;
   }
 
bool BinaryContext::isValidJumpTableEntry(
 
   return false;
 }
 
 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;
+  uint64_t NumEntries = 0;
   BinaryFunction *ValidExternalTargetBF = nullptr;
 
   auto addEntryAddress = [&](uint64_t EntryAddress) {
     if (EntriesAsAddress)
       EntriesAsAddress->emplace_back(EntryAddress);
   };
 
   ErrorOr<BinarySection &> Section = getSectionForAddress(Address);
if (HasRelocations) {
       }
     }
 
     const uint64_t Value =
         (Type == JumpTable::JTT_PIC)
             ? Address + *getSignedValueAtAddress(EntryAddress, EntrySize)
             : *getPointerAtAddress(EntryAddress);
 
-    // __builtin_unreachable() case.
-    if (Value == BF.getAddress() + BF.getSize()) {
-      addEntryAddress(Value);
-      HasUnreachable = true;
-      LLVM_DEBUG(dbgs() << "OK: __builtin_unreachable\n");
-      continue;
-    }
-
     BinaryFunction *TargetBF = getBinaryFunctionContainingAddress(Value);
 
     // Verify if Value is a valid jump table entry
     if (!isValidJumpTableEntry(Value, BF, ValidExternalTargetBF))
       break;
 
-    ++NumRealEntries;
+    ++NumEntries;
 
     if (TargetBF != nullptr && 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;
+  return NumEntries >= 2;
 }
 
 void BinaryContext::populateJumpTables() {
   LLVM_DEBUG(dbgs() << "DataPCRelocations: " << DataPCRelocations.size()
                     << '\n');
 
   // Collect jump tables that pass the analyzeJumpTable's first check,
   // but fail the analyzeJumpTable's second check

bolt/lib/Core/BinaryFunction.cpp

if (JT.Type == JumpTable::JTT_PIC && opts::JumpTables == JTS_BASIC) {
       outs() << "BOLT-INFO: forcing -jump-tables=move as PIC jump table was "
                 "detected in function "
              << *this << '\n';
     }
     if (JT.Entries.empty()) {
       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);
+        BinaryFunction *TargetBF =
+            BC.getBinaryFunctionContainingAddress(EntryAddress);
+        BinaryFunction *PredBF =
+            BC.getBinaryFunctionContainingAddress(EntryAddress - 1);
+
+        // Verify builtin_unreachable
+        if (!BC.IsStripped && PredBF != nullptr && PredBF != TargetBF) {
+          if (PredBF == JT.Parents[0] ||
+              JT.Parents[0]->isParentFragment(PredBF) ||
+              PredBF->isParentFragment(JT.Parents[0])) {
+            MCSymbol *Label = PredBF->getOrCreateLocalLabel(EntryAddress, true);
             JT.Entries.push_back(Label);
-            break;
+            continue;
           }
         }
 
-        if (IsBuiltIn)
-          continue;
+        assert(TargetBF && "jump table entry must belong to a function");
 
-        // Functions can be optionally skipped by users, or marked as ignored
-        // during branch target analysis. Since the target function is not
-        // processed, functions that access jump tables which point to these
-        // target functions also need to be marked as ignored
-        BinaryFunction *TargetBF =
-            BC.getBinaryFunctionContainingAddress(EntryAddress);
-        if (TargetBF->getState() != BinaryFunction::State::Disassembled ||
-            TargetBF->isIgnored()) {
-          setIgnored();
-          return;
-        }
         // Create local label for targets cannot be reached by other fragments
-        // Otherwise, register as a secondary entry point to target function
+        // Otherwise, secondary entry point to target function
         if (TargetBF->getAddress() != EntryAddress) {
           MCSymbol *Label =
               (HasOneParent && TargetBF == this)
                   ? getOrCreateLocalLabel(JT.EntriesAsAddress[I], true)
                   : TargetBF->addEntryPointAtOffset(EntryAddress -
                                                     TargetBF->getAddress());
           JT.Entries.push_back(Label);
         }