[BOLT] Update sibling relationship from LSDA Section

[nhuhuan]

Summary

LSDA Section is encoded in an unambiguous manner, allows accurate
reconstruction of landing pads. By definition, split landing pads
must target same function. If a function is splitted, split landing
pads indicate that the target function is a sibling fragment.

When processing stripped binaries, BOLT leverages this information
to support split jump table analysis. For that, sibling inference
needs to run before branch target analysis.

In this update, sibling validation/inference is decoupled from other
tasks, e.g., register labels for landing pads, and is placed before
branch target analysis. This also requires decoupled getting LSDA
Address from processing other CFI Info.

Test Plan:

ninja check-bolt

[rafauler]

Can we add more testing that exercises the new code paths being added here?

bolt/include/bolt/Core/BinaryFunction.h

   void setEmitted(bool KeepCFG = false) {
     CurrentState = State::EmittedCFG;
     if (!KeepCFG) {
       releaseCFG();
       CurrentState = State::Emitted;
     }
   }
 
-  /// Process LSDA information for the function.
-  void parseLSDA(ArrayRef<uint8_t> LSDAData, uint64_t LSDAAddress);
+  /// Process LSDA information for the function:
+  /// SiblingValidation:
+  ///    Must run before branch target analysis
+  ///    Process CallSiteTable to infer siblings for stripped binaries
+  ///    Process CallSiteTable to validate siblings for nonstripped binaries
+  /// !SiblingValidation:
+  ///    Must run after disassembly and branch target analysis
+  ///    Process CallSiteTable to register labels for landing pad
+  ///    Process ActionTable
+  ///    Process TypesTable
+  void parseLSDA(ArrayRef<uint8_t> LSDAData, uint64_t LSDAAddress,
+                 bool SiblingValidation);
 
   /// Update exception handling ranges for the function.
   void updateEHRanges();
 
   /// Traverse cold basic blocks and replace references to constants in islands
   /// with a proxy symbol for the duplicated constant island that is going to be
   /// emitted in the cold region.
   void duplicateConstantIslands();

bolt/include/bolt/Core/Exceptions.h

 class BinaryFunction;
 
 /// \brief Wraps up information to read all CFI instructions and feed them to a
 /// BinaryFunction, as well as rewriting CFI sections.
 class CFIReaderWriter {
 public:
   explicit CFIReaderWriter(const DWARFDebugFrame &EHFrame);
 
+  void fillLSDAAddressFor(BinaryFunction &Function) const;
   bool fillCFIInfoFor(BinaryFunction &Function) const;
 
   /// Generate .eh_frame_hdr from old and new .eh_frame sections.
   ///
   /// Take FDEs from the \p NewEHFrame unless their initial_pc is listed
   /// in \p FailedAddresses. All other entries are taken from the
   /// \p OldEHFrame.
   ///

bolt/lib/Core/Exceptions.cpp

 // may require relocation.
 //
 // Ideally we should be able to re-write LSDA in-place, without the need to
 // allocate a new space for it. Sadly there's no guarantee that the new call
 // site table will be the same size as GCC uses uleb encodings for PC offsets.
 //
 // Note: some functions have LSDA entries with 0 call site entries.
 void BinaryFunction::parseLSDA(ArrayRef<uint8_t> LSDASectionData,
-                               uint64_t LSDASectionAddress) {
-  assert(CurrentState == State::Disassembled && "unexpected function state");
+                               uint64_t LSDASectionAddress,
+                               bool SiblingValidation) {
+  // Sibling validation occurs before branch target analysis
+  // Otherwise, require branch target analysis done to proceed
+  assert((SiblingValidation || CurrentState == State::Disassembled) &&
+         "unexpected function state");
 
   if (!getLSDAAddress())
     return;
 
   DWARFDataExtractor Data(
       StringRef(reinterpret_cast<const char *>(LSDASectionData.data()),
                 LSDASectionData.size()),
       BC.DwCtx->getDWARFObj().isLittleEndian(), 8);
void BinaryFunction::parseLSDA(ArrayRef<uint8_t> LSDASectionData,
   const uint8_t TTypeEncoding = Data.getU8(&Offset);
   size_t TTypeEncodingSize = 0;
   uintptr_t TTypeEnd = 0;
   if (TTypeEncoding != DW_EH_PE_omit) {
     TTypeEnd = Data.getULEB128(&Offset);
     TTypeEncodingSize = BC.getDWARFEncodingSize(TTypeEncoding);
   }
 
-  if (opts::PrintExceptions) {
+  // Avoid printing information twice
+  if (opts::PrintExceptions && !SiblingValidation) {
     outs() << "[LSDA at 0x" << Twine::utohexstr(getLSDAAddress())
            << " for function " << *this << "]:\n";
     outs() << "LPStart Encoding = 0x" << Twine::utohexstr(LPStartEncoding)
            << '\n';
     outs() << "LPStart = 0x" << Twine::utohexstr(LPStart) << '\n';
     outs() << "TType Encoding = 0x" << Twine::utohexstr(TTypeEncoding) << '\n';
     outs() << "TType End = " << TTypeEnd << '\n';
   }
void BinaryFunction::parseLSDA(ArrayRef<uint8_t> LSDASectionData,
 
   uint8_t CallSiteEncoding = Data.getU8(&Offset);
   uint32_t CallSiteTableLength = Data.getULEB128(&Offset);
   uint64_t CallSiteTableStart = Offset;
   uint64_t CallSiteTableEnd = CallSiteTableStart + CallSiteTableLength;
   uint64_t CallSitePtr = CallSiteTableStart;
   uint64_t ActionTableStart = CallSiteTableEnd;
 
-  if (opts::PrintExceptions) {
+  // Avoid printing information twice
+  if (opts::PrintExceptions && !SiblingValidation) {
     outs() << "CallSite Encoding = " << (unsigned)CallSiteEncoding << '\n';
     outs() << "CallSite table length = " << CallSiteTableLength << '\n';
     outs() << '\n';
   }
 
   this->HasEHRanges = CallSitePtr < CallSiteTableEnd;
   const uint64_t RangeBase = getAddress();
   while (CallSitePtr < CallSiteTableEnd) {
     uint64_t Start = *Data.getEncodedPointer(&CallSitePtr, CallSiteEncoding,
                                              CallSitePtr + LSDASectionAddress);
     uint64_t Length = *Data.getEncodedPointer(&CallSitePtr, CallSiteEncoding,
                                               CallSitePtr + LSDASectionAddress);
     uint64_t LandingPad = *Data.getEncodedPointer(
         &CallSitePtr, CallSiteEncoding, CallSitePtr + LSDASectionAddress);
     uint64_t ActionEntry = Data.getULEB128(&CallSitePtr);
 
     uint64_t LPOffset = LPStart + LandingPad;
     uint64_t LPAddress = Address + LPOffset;
     BinaryFunction *Fragment = BC.getBinaryFunctionContainingAddress(LPAddress);
 
+    // Sibling inference for stripped binaries
+    // Sibling validation for nonstripped binaries
+    if (SiblingValidation) {
       // Verify if landing pad code is located outside current function
       // Skip case where landing pad targets builtin_unreachable
       if (LPAddress < Address || LPAddress > Address + getSize()) {
         // Assume landing pad not target another fragment's builtin_unreachable
         // If this assumption is violated, must run a global check first
         assert(Fragment != nullptr &&
                "BOLT-ERROR: cannot find landing pad fragment");
-
         // Update IsFragment:
-      // In stripped mode, always trust LSDA, consider the function that
-      // contains LP as a fragment
-      // In non-stripped mode, use pattern matching (adjustFunctionBoundaries)
+        // For stripped binaries, functions containing LP are marked as sibling
+        // For nonstripped binaries, validate using symbol name
         if (BC.IsStripped)
           Fragment->IsFragment = true;
-
-      // Update parent-fragment relation, add Fragment as secondary entry of
-      // the current function, not an independent function
+        // Register siblings
+        // FIXME: This method print false warnings if LP is at function entry
         BC.addInterproceduralReference(this, Fragment->getAddress());
         BC.processInterproceduralReferences();
-
-      // In stripped mode, parent-fragment is always established --> skip check
-      // In non-stripped mode, parent-fragment depends on symbol name --> check
+        // Validate sibling relationship for nonstripped binaries only
         if (!BC.IsStripped) {
           auto isFragmentOf = [](BinaryFunction *Fragment,
                                  BinaryFunction *Parent) -> bool {
-          return (Fragment->isFragment() && Fragment->isParentFragment(Parent));
+            return (Fragment->isFragment() &&
+                    Fragment->isParentFragment(Parent));
           };
-        assert((isFragmentOf(this, Fragment) || isFragmentOf(Fragment, this)) &&
-               "BOLT-ERROR: cannot have landing pads in different functions");
+          assert(
+              (isFragmentOf(this, Fragment) || isFragmentOf(Fragment, this)) &&
         }
-      // Mark that this fragment reaches LP in another fragment of same function
+        // Mark that this fragment reaches LP in another fragment of same
+        // function
         setHasIndirectTargetToSplitFragment(true);
         BC.addFragmentsToSkip(this);
       }
-
+    }
+    // Register label for split landing pad
+    // Update EHInfo for Call Site. This update can only run once!
+    else {
       // Create a handler entry if necessary.
       MCSymbol *LPLabel = nullptr;
 
       // Special case, consider builtin_unreachable as part of this function
       if (LPAddress == Address + getSize())
         Fragment = this;
 
       // Assumption: landing pad cannot target current fragment entry
       // Note: landing pad can target other fragment entry -> split landing pad
       if (LPAddress != Address) {
         uint64_t FragmentOffset = LPAddress - Fragment->getAddress();
         if (!Fragment->getInstructionAtOffset(FragmentOffset)) {
           if (opts::Verbosity >= 1)
             errs() << "BOLT-WARNING: landing pad " << Twine::utohexstr(LPOffset)
-                 << " not pointing to an instruction in function " << *Fragment
-                 << " - ignoring.\n";
+                   << " not pointing to an instruction in function "
+                   << *Fragment << " - ignoring.\n";
         } else {
           // Treat split landing pad as the fragment's secondary fragment
           auto Label = Fragment->Labels.find(FragmentOffset);
           LPLabel = (Label != Fragment->Labels.end())
                         ? Label->second
                         : ((Fragment != this)
                                ? Fragment->addEntryPointAtOffset(FragmentOffset)
                                : BC.Ctx->createNamedTempSymbol("LP"));
           // Support recomputeLandingPad to identify split landing pad
           BC.setSymbolToFunctionMap(LPLabel, Fragment);
           Labels[LPOffset] = LPLabel;
         }
       }
 
       if (opts::PrintExceptions) {
         outs() << "Call Site: [0x" << Twine::utohexstr(RangeBase + Start)
                << ", 0x" << Twine::utohexstr(RangeBase + Start + Length)
                << "); landing pad: 0x" << Twine::utohexstr(LPOffset)
                << "; action entry: 0x" << Twine::utohexstr(ActionEntry) << "\n";
         outs() << "  current offset is " << (CallSitePtr - CallSiteTableStart)
                << '\n';
         if (LPLabel != nullptr)
           outs() << "  landing pad label: " << LPLabel->getName() << "\n";
       }
 
       // Mark all call instructions in the range.
       auto II = Instructions.find(Start);
       auto IE = Instructions.end();
       assert(II != IE && "exception range not pointing to an instruction");
       do {
         MCInst &Instruction = II->second;
         if (BC.MIB->isCall(Instruction) &&
             !BC.MIB->getConditionalTailCall(Instruction)) {
           assert(!BC.MIB->isInvoke(Instruction) &&
                  "overlapping exception ranges detected");
           // Add extra operands to a call instruction making it an invoke from
           // now on.
           BC.MIB->addEHInfo(Instruction,
                             MCPlus::MCLandingPad(LPLabel, ActionEntry));
         }
         ++II;
       } while (II != IE && II->first < Start + Length);
+    }
 
     if (ActionEntry != 0) {
       auto printType = [&](int Index, raw_ostream &OS) {
         assert(Index > 0 && "only positive indices are valid");
         uint64_t TTEntry = TypeTableStart - Index * TTypeEncodingSize;
         const uint64_t TTEntryAddress = TTEntry + LSDASectionAddress;
         uint64_t TypeAddress =
             *Data.getEncodedPointer(&TTEntry, TTypeEncoding, TTEntryAddress);
if (FDEI != FDEs.end() && FDEI->first == CurFDE->getInitialLocation()) {
         }
       }
     } else {
       FDEs.emplace_hint(FDEI, CurFDE->getInitialLocation(), CurFDE);
     }
   }
 }
 
-bool CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) const {
+void CFIReaderWriter::fillLSDAAddressFor(BinaryFunction &Function) const {
   uint64_t Address = Function.getAddress();
   auto I = FDEs.find(Address);
   // Ignore zero-length FDE ranges.
   if (I == FDEs.end() || !I->second->getAddressRange())
-    return true;
+    return;
 
   const FDE &CurFDE = *I->second;
   Optional<uint64_t> LSDA = CurFDE.getLSDAAddress();
   Function.setLSDAAddress(LSDA ? *LSDA : 0);
+}
+
+bool CFIReaderWriter::fillCFIInfoFor(BinaryFunction &Function) const {
+  uint64_t Address = Function.getAddress();
+  auto I = FDEs.find(Address);
+  // Ignore zero-length FDE ranges.
+  if (I == FDEs.end() || !I->second->getAddressRange())
+    return true;
+
+  const FDE &CurFDE = *I->second;
 
   uint64_t Offset = Function.getFirstInstructionOffset();
   uint64_t CodeAlignment = CurFDE.getLinkedCIE()->getCodeAlignmentFactor();
   uint64_t DataAlignment = CurFDE.getLinkedCIE()->getDataAlignmentFactor();
   if (CurFDE.getLinkedCIE()->getPersonalityAddress()) {
     Function.setPersonalityFunction(
         *CurFDE.getLinkedCIE()->getPersonalityAddress());
     Function.setPersonalityEncoding(

bolt/lib/Rewrite/RewriteInstance.cpp

void RewriteInstance::processProfileData() {
 
   if (opts::AggregateOnly)
     exit(0);
 }
 
 void RewriteInstance::disassembleFunctions() {
   NamedRegionTimer T("disassembleFunctions", "disassemble functions",
                      TimerGroupName, TimerGroupDesc, opts::TimeRewrite);
+
+  // Sibling inference for stripped binaries
+  // Sibling validation for nonstripped binaries
+  for (auto &BFI : BC->getBinaryFunctions()) {
+    BinaryFunction &Function = BFI.second;
+    if (!shouldDisassemble(Function))
+      continue;
+    CFIRdWrt->fillLSDAAddressFor(Function);
+    if (Function.getLSDAAddress() != 0)
+      Function.parseLSDA(getLSDAData(), getLSDAAddress(), true);
+  }
+
+  // Disassembly and Branch Target Analysis
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     ErrorOr<ArrayRef<uint8_t>> FunctionData = Function.getData();
     if (!FunctionData) {
       errs() << "BOLT-ERROR: corresponding section is non-executable or "
              << "empty for function " << Function << '\n';
       exit(1);
if (!Function.disassemble()) {
       Function.setIgnored();
       continue;
     }
 
     if (opts::PrintAll || opts::PrintDisasm)
       Function.print(outs(), "after disassembly", true);
   }
 
+  // Post-disassembly
   BC->processInterproceduralReferences();
   BC->populateJumpTables();
 
   for (auto &BFI : BC->getBinaryFunctions()) {
     BinaryFunction &Function = BFI.second;
 
     if (!shouldDisassemble(Function))
       continue;
if (!Function.trapsOnEntry() && !CFIRdWrt->fillCFIInfoFor(Function)) {
         errs() << "BOLT-WARNING: unable to fill CFI for function " << Function
                << ". Skipping.\n";
         Function.setSimple(false);
         continue;
       }
     }
 
     // Parse LSDA.
-    if (Function.getLSDAAddress() != 0 &&
-        !BC->getFragmentsToSkip().count(&Function))
-      Function.parseLSDA(getLSDAData(), getLSDAAddress());
+    if (Function.getLSDAAddress() != 0)
+      Function.parseLSDA(getLSDAData(), getLSDAAddress(), false);
   }
 }
 
 void RewriteInstance::buildFunctionsCFG() {
   NamedRegionTimer T("buildCFG", "buildCFG", "buildfuncs",
                      "Build Binary Functions", opts::TimeBuild);
 
   // Create annotation indices to allow lock-free execution