[BOLT] Update labels for split landing pad

[nhuhuan]

Summary

Landing pad is the catch block in C++ exception handling and normally
resides in same function with callsite. As a result, it makes sense
to reuse or create a local label during parsing LSDA section.

However, for function-splitting enabled binaries, callsite and landing
pad could be in different sibling fragments. The split landing pad's
label needs to be registered as a secondary entry point to the target
fragment.

Also, unless LSDA section is updated, it is necessary to link callsite
fragment to landing pad fragment to guarantee that landing pad fragment
can be moved.

Test Plan:

ninja check-bolt

[Amir]

Thanks for working on it and adding a test with a stripped binary.

The approach looks good to me. I would appreciate if @maksfb or @rafaelauler take a look.
@nhuhuan: let's wait a day before proceeding.

[rafauler]

Excellent work Huan! I have a few design suggestions below. Let me know what do you think.

bolt/lib/Core/Exceptions.cpp

102

I'm not a fan of using boolean input variables (there are several texts written about this anti-pattern, this is just one of them: https://understandlegacycode.com/blog/what-is-wrong-with-boolean-parameters/ )

We have quite a few of these in our codebase already and it makes me uneasy. Here, it just makes code harder to read and understand. This is already a reasonably complex parser, and we should at least try to make it simpler to read. I would prefer if this function was refactored to reflect the fact that it now has two modes of operation.

If we look at parseLSDA as it is in this patch, it can be refactored using a pattern of parser logic separated from callback action. this is similar to semantic actions in a compiler parser, in which we completely separate parser from the component responsible for taking actions depending on what the parser reports as the rule being currently consumed.

put all of the current parser logic into parseLSDA, make parseLSDA receive a callback as an argument that is what is going to happen to each parsed element, and then implement checkonly=true and checkonly=false logic in the callback.

something along these lines (let me know if it is not feasible to implement this pattern or if it is too cumbersome):

BinaryFunction {
private:
  parseAndWalkOverLSDA(data, Callback)
public:
  consumeLSDAForFragmentRelationships();
  consumeLSDAForEHInfo()
}

parseAndWalkOverLSDA{
  parsing logic...
  for each iteration of loop {
    parsing logic
    callback()
  }
}

consumeLSDAForFragmentRelationships{
  auto Callback = [&] {
    establish fragment relationships logic...
  }

  parseAndWalkOverLSDA(Callback);
}

consumeLSDAForEHInfo {
  auto Callback = [&] {
    modify instructions to add all EH info stuff..
  }
  parseAndWalkOverLSDA(Callback);
}

520

fillLSDAAddressFor

[rafauler]

I'm also curious if this adds runtime overhead by parsing LSDA two times per function. Can we measure that using a large binary as input?

[nhuhuan]

In D130072#3673246, @rafauler wrote:

I'm also curious if this adds runtime overhead by parsing LSDA two times per function. Can we measure that using a large binary as input?

Regarding overhead, running twice should have (almost) no effect because size
of LSDA is proportional to only C++ exception handling. Very small amount of
code actually uses this feature.

I measured performance on a binary of size 741MB.

Run parseLSDA once - without checking for valid LSDA:
Testing Time: 431.06s
real 7m11.206s
user 8m43.858s
sys 13m35.488s

Run parseLSDA twice - with checking for valid LSDA:
Testing Time: 442.66s
real 7m22.803s
user 8m43.770s
sys 13m54.131s

Note that to quickly get results, I skipped the checks in "Run Once" version,
resulted in faster performance, but that is not significant.

If we keep the checks in place, running once or twice probably does not matter
much. I don't think performance is a problem.

[Amir]

Please update the summary to narrative form.

[nhuhuan]

bolt/lib/Core/Exceptions.cpp

102

Thanks for your suggestions, @rafaelauler.

I generally agree that using callbacks improves maintainability. However, a few things are holding me back.

(a) Callbacks may need too many arguments
I assume that we don't want to add parsing logic remained in parseAndWalkOverLSDA
If so, there are simply too many arguments for one general callback.

(b) Avoid printing duplicate debugging messages.
If printing message in callbacks, then many more arguments.
So parseAndWalkOverLSDA need to take another boolean AllowPrintingMessage.

[nhuhuan]

Split this diff into a few diffs.

[rafauler]

bolt/lib/Core/BinaryFunction.cpp

1887

.. if LPFunc has no CFG yet

1888

Solution: rerun recomputeLandingPads after buildCFG for all functions

bolt/lib/Core/Exceptions.cpp

203–205

I would suggest moving this before MCSymbol *LPLabel = nullptr; so the code that calculates LPLabel is closer together

209

I was thinking in maybe adding a comment "Skip creating a landing pad if LPOffset is zero" so it is clear that this is from the LSDA format

217

Treat split landing pad as the fragment's secondary entry point?

But maybe expand this comment, as it looks like this code section is handling _only_ that. Maybe:

Create/fetch landing pad label. If necessary, treat split landing pad as...

226

Is this correct for the case where LPOffset is an offset outside this function (LPLabel is set by Fragment->addEntryPointAtOffset(FragmentOffset)) ?

bolt/lib/Rewrite/RewriteInstance.cpp

2925–2926

I would reverse for clarity:

Process non-simple cases due to split jump table or split landing pad
Ignore all other non-simple cases

[nhuhuan]

Address feedbacks

bolt/lib/Core/Exceptions.cpp

209

I wrote an equivalent comment: "Assumption: landing pad cannot target current fragment entry"

226

You're correct. I explain this in the last paragraph in description.
Let me clarify a bit more here:

The link between callsite and landing pad fragment is Labels[LPOffset].
If LSDA is not updated, the LPOffset will be the same, while target function
may be moved. This link is to keep connection between two fragments.
I also see its benefit on merging split function task in future.

520

Addressed in another diff: D130663

[Amir]

We need to make sure that the support for split LP is sufficient/correct for also running the processed binary.
Can we turn the test into a runtime test, making sure that the EH works after BOLT?

bolt/lib/Core/BinaryFunction.cpp

for (BinaryBasicBlock *BB : BasicBlocks) {
     for (MCInst &Instr : *BB) {
       if (!BC.MIB->isInvoke(Instr))
         continue;
 
       const Optional<MCPlus::MCLandingPad> EHInfo = BC.MIB->getEHInfo(Instr);
       if (!EHInfo || !EHInfo->first)
         continue;
 
-      BinaryBasicBlock *LPBlock = getBasicBlockForLabel(EHInfo->first);
-      if (!BBLandingPads.count(LPBlock)) {
+      // For cross-fragment LPs, LPBlock = nullptr if LPFunc not yet buildCFG
+      // Solution: after buildCFG for all functions, rerun recomputeLandingPads
+      const MCSymbol *LPLabel = EHInfo->first;
+      BinaryFunction *LPFunc = BC.getFunctionForSymbol(LPLabel);
+      BinaryBasicBlock *LPBlock = LPFunc->getBasicBlockForLabel(LPLabel);
+      if (LPBlock != nullptr && !BBLandingPads.count(LPBlock)) {
         BBLandingPads.insert(LPBlock);
         BB->LandingPads.emplace_back(LPBlock);
         LPBlock->Throwers.emplace_back(BB);
       }
     }
   }
 }
 

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");
 
   if (!getLSDAAddress())
     return;
 
   DWARFDataExtractor Data(
       StringRef(reinterpret_cast<const char *>(LSDASectionData.data()),
                 LSDASectionData.size()),
while (CallSitePtr < CallSiteTableEnd) {
     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);
 
     // Verify if landing pad code is located outside current function
     // Support landing pad to builtin_unreachable
     if (LPAddress < Address || LPAddress > Address + getSize()) {
-      BinaryFunction *Fragment =
-          BC.getBinaryFunctionContainingAddress(LPAddress);
       assert(Fragment != nullptr &&
              "BOLT-ERROR: cannot find landing pad fragment");
       BC.addInterproceduralReference(this, Fragment->getAddress());
       BC.processInterproceduralReferences();
       auto isFragmentOf = [](BinaryFunction *Fragment,
                              BinaryFunction *Parent) -> bool {
         return (Fragment->isFragment() && Fragment->isParentFragment(Parent));
       };
       assert((isFragmentOf(this, Fragment) || isFragmentOf(Fragment, this)) &&
              "BOLT-ERROR: cannot have landing pads in different "
              "functions");
       setHasIndirectTargetToSplitFragment(true);
       BC.addFragmentsToSkip(this);
-      return;
-    }
-
-    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';
     }
 
     // Create a handler entry if necessary.
-    MCSymbol *LPSymbol = nullptr;
-    if (LPOffset) {
-      if (!getInstructionAtOffset(LPOffset)) {
+    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 " << *this
+                 << " not pointing to an instruction in function " << *Fragment
                  << " - ignoring.\n";
       } else {
-        auto Label = Labels.find(LPOffset);
-        if (Label != Labels.end()) {
-          LPSymbol = Label->second;
-        } else {
-          LPSymbol = BC.Ctx->createNamedTempSymbol("LP");
-          Labels[LPOffset] = LPSymbol;
-        }
-      }
+        // 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(LPSymbol, ActionEntry));
+                          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;
if (FDEI != FDEs.end() && FDEI->first == CurFDE->getInitialLocation()) {
         }
       }
     } else {
       FDEs.emplace_hint(FDEI, CurFDE->getInitialLocation(), CurFDE);
     }
   }
 }
 
 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;
   Optional<uint64_t> LSDA = CurFDE.getLSDAAddress();

bolt/lib/Passes/SplitFunctions.cpp

SplitFunctions::createEHTrampolines(BinaryFunction &BF) const {
   // function which will invalidate its iterators.
   std::vector<BinaryBasicBlock *> Blocks(BF.pbegin(), BF.pend());
   for (BinaryBasicBlock *BB : Blocks) {
     for (MCInst &Instr : *BB) {
       const Optional<MCPlus::MCLandingPad> EHInfo = MIB->getEHInfo(Instr);
       if (!EHInfo || !EHInfo->first)
         continue;
 
+      // In case of split landing pad, LPFunc != BF
       const MCSymbol *LPLabel = EHInfo->first;
-      BinaryBasicBlock *LPBlock = BF.getBasicBlockForLabel(LPLabel);
+      BinaryFunction *LPFunc =
+          BF.getBinaryContext().getFunctionForSymbol(LPLabel);
+      BinaryBasicBlock *LPBlock = LPFunc->getBasicBlockForLabel(LPLabel);
       if (BB->isCold() == LPBlock->isCold())
         continue;
 
       const MCSymbol *TrampolineLabel = nullptr;
       auto Iter = LPTrampolines.find(LPLabel);
       if (Iter != LPTrampolines.end()) {
         TrampolineLabel = Iter->second;
       } else {
         // Create a trampoline basic block in the same fragment as the thrower.
         // Note: there's no need to insert the jump instruction, it will be
         // added by fixBranches().
-        BinaryBasicBlock *TrampolineBB = BF.addBasicBlock();
+        BinaryBasicBlock *TrampolineBB = LPFunc->addBasicBlock();
         TrampolineBB->setIsCold(BB->isCold());
         TrampolineBB->setExecutionCount(LPBlock->getExecutionCount());
         TrampolineBB->addSuccessor(LPBlock, TrampolineBB->getExecutionCount());
         TrampolineBB->setCFIState(LPBlock->getCFIState());
         TrampolineLabel = TrampolineBB->getLabel();
         LPTrampolines.insert(std::make_pair(LPLabel, TrampolineLabel));
+        BF.getBinaryContext().setSymbolToFunctionMap(TrampolineLabel, LPFunc);
       }
 
       // Substitute the landing pad with the trampoline.
       MIB->updateEHInfo(Instr,
                         MCPlus::MCLandingPad(TrampolineLabel, EHInfo->second));
     }
   }
 

bolt/lib/Rewrite/RewriteInstance.cpp

void RewriteInstance::disassembleFunctions() {
   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.hasIndirectTargetToSplitFragment()) &&
+    // If non-simple due to split jump table or split landing pad, process
+    // Every other non-simple cases, ignore
+    if (!Function.isSimple() && !Function.hasIndirectTargetToSplitFragment()) {
+      assert((!BC->HasRelocations || Function.getSize() == 0) &&
              "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);
void RewriteInstance::buildFunctionsCFG() {
   };
 
   ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
       *BC, ParallelUtilities::SchedulingPolicy::SP_INST_LINEAR, WorkFun,
       SkipPredicate, "disassembleFunctions-buildCFG",
       /*ForceSequential*/ opts::SequentialDisassembly || opts::PrintAll);
 
   BC->postProcessSymbolTable();
+
+  // recomputeLandingPads is invoked during buildCFG for every function.
+  // For split landing pad, it is possible that the target function does
+  // not yet have CFG, so recomputeLandingPads would fail to capture
+  // cross-function targets.
+  //
+  // Solution:
+  // (a) Safely ignore split landing pad during buildCFG
+  // (b) Rerun recomputeLandingPads after all functions have CFG
+  for (BinaryFunction *Function : BC->getAllBinaryFunctions())
+    if (Function->getState() == BinaryFunction::State::CFG)
+      Function->recomputeLandingPads();
 }
 
 void RewriteInstance::postProcessFunctions() {
   // We mark fragments as non-simple here, not during disassembly,
   // So we can build their CFGs.
   BC->skipMarkedFragments();
   BC->clearFragmentsToSkip();
 

bolt/test/X86/split-landing-pad.s

 # .gcc_except_table specify the landing pads for try blocks
 #    LPStart = 255 (omit), which means LPStart = foo start
 # Landing pads .Ltmp2 and .Ltmp5 in call site record are offset to foo start.
 
 
 # REQUIRES: system-linux
 # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
 # RUN: %clang++ %cxxflags %t.o -o %t.exe -Wl,-q
-# RUN: llvm-bolt -v=3 %t.exe -o %t.out 2>&1 | FileCheck %s
+# RUN: llvm-bolt -v=3 %t.exe -o %t.out -print-exceptions 2>&1 | FileCheck %s
 
-# CHECK: BOLT-WARNING: Ignoring foo
-# CHECK: BOLT-WARNING: Ignoring foo.cold.1
+# CHECK: BOLT-INFO: marking [[FOO_COLD:.+]] as a fragment of [[FOO:.+]]
+# CHECK: landing pad label: [[TMP2:.+]]
+# CHECK: landing pad label: [[TMP5:.+]]
+# CHECK: BOLT-WARNING: Ignoring [[FOO]]
+# CHECK: BOLT-WARNING: Ignoring [[FOO_COLD]]
 # CHECK: BOLT-WARNING: skipped 2 functions due to cold fragments
 
   .text
   .globl  bar                             # -- Begin function bar
   .p2align  4, 0x90
   .type bar,@function
 bar:                                    # @bar
   .cfi_startproc