[BOLT] Split functions with exceptions in shared objects and PIEs

[maksfb]

Summary

Add functionality to allow splitting code with C++ exceptions in shared
libraries and PIEs. To overcome a limitation in exception ranges format,
for functions with fragments spanning multiple sections, add trampoline
landing pads in the same section as the corresponding throwing range.

[Amir]

Did you see these errors from the new test?

ld.lld: error: can't create dynamic relocation R_X86_64_32 against local symbol in readonly segment; recompile object files with -fPIC or pass '-Wl,-z,notext' to allow text relocations in the output
>>> defined in /tmp/lit-tmp-pe4hpdy9/exceptions_split-6209af.o
>>> referenced by exceptions_split.cpp
>>>               /tmp/lit-tmp-pe4hpdy9/exceptions_split-6209af.o:(main)

https://buildkite.com/llvm-project/premerge-checks/builds/98179#01816afe-daa6-4e44-a7c8-efb4b5b9f1f6/485-3642

[maksfb]

In D127936#3588002, @Amir wrote:

Did you see these errors from the new test?

ld.lld: error: can't create dynamic relocation R_X86_64_32 against local symbol in readonly segment; recompile object files with -fPIC or pass '-Wl,-z,notext' to allow text relocations in the output
>>> defined in /tmp/lit-tmp-pe4hpdy9/exceptions_split-6209af.o
>>> referenced by exceptions_split.cpp
>>>               /tmp/lit-tmp-pe4hpdy9/exceptions_split-6209af.o:(main)

https://buildkite.com/llvm-project/premerge-checks/builds/98179#01816afe-daa6-4e44-a7c8-efb4b5b9f1f6/485-3642

Not locally.

[maksfb]

Add -fPIC to the test.

[Amir]

LGTM

bolt/include/bolt/Core/MCPlusBuilder.h

public:
   virtual bool requiresAlignedAddress(const MCInst &Inst) const {
     llvm_unreachable("not implemented");
     return false;
   }
 
   /// Return handler and action info for invoke instruction if present.
   Optional<MCPlus::MCLandingPad> getEHInfo(const MCInst &Inst) const;
 
-  // Add handler and action info for call instruction.
+  /// Add handler and action info for call instruction.
   void addEHInfo(MCInst &Inst, const MCPlus::MCLandingPad &LP);
 
+  /// Update exception-handling info for the invoke instruction \p Inst.
+  /// Return true on success and false otherwise, e.g. if the instruction is
+  /// not an invoke.
+  bool updateEHInfo(MCInst &Inst, const MCPlus::MCLandingPad &LP);
+
   /// Return non-negative GNU_args_size associated with the instruction
   /// or -1 if there's no associated info.
   int64_t getGnuArgsSize(const MCInst &Inst) const;
 
   /// Add the value of GNU_args_size to Inst if it already has EH info.
   void addGnuArgsSize(MCInst &Inst, int64_t GnuArgsSize,
                       AllocatorIdTy AllocId = 0);
 

bolt/include/bolt/Passes/SplitFunctions.h

ST_LARGE,    /// In non-relocation mode, only split functions that
                  /// are too large to fit into the original space.
     ST_ALL,      /// Split all functions.
   };
 
 private:
   /// Split function body into fragments.
   void splitFunction(BinaryFunction &Function);
 
+  /// Create trampoline landing pads for exception handling code to guarantee
+  /// that every landing pad is placed in the same function fragment as the
+  /// corresponding thrower block. The trampoline landing pad, when created,
+  /// will redirect the execution to the real landing pad in a different
+  /// fragment.
+  void createEHTrampolines(BinaryFunction &Function) const;
+
   std::atomic<uint64_t> SplitBytesHot{0ull};
   std::atomic<uint64_t> SplitBytesCold{0ull};
 
 public:
   explicit SplitFunctions(const cl::opt<bool> &PrintPass)
       : BinaryFunctionPass(PrintPass) {}
 
   bool shouldOptimize(const BinaryFunction &BF) const override;

bolt/lib/Core/BinaryEmitter.cpp

void BinaryEmitter::emitLSDA(BinaryFunction &BF, bool EmitColdPart) {
   //
   // If the base address can change, we cannot use absolute addresses for
   // landing pads (at least not without runtime relocations). Hence, we fall
   // back to emitting landing pads relative to the FDE start.
   // As we are emitting label differences, we have to guarantee both labels are
   // defined in the same section and hence cannot place the landing pad into a
   // cold fragment when the corresponding call site is in the hot fragment.
   // Because of this issue and the previously described issue of possible
-  // zero-offset landing pad we disable splitting of exception-handling
-  // code for shared objects.
+  // zero-offset landing pad we have to place landing pads in the same section
+  // as the corresponding invokes for shared objects.
   std::function<void(const MCSymbol *)> emitLandingPad;
   if (BC.HasFixedLoadAddress) {
     Streamer.emitIntValue(dwarf::DW_EH_PE_udata4, 1); // LPStart format
     Streamer.emitIntValue(0, 4);                      // LPStart
     emitLandingPad = [&](const MCSymbol *LPSymbol) {
       if (!LPSymbol)
         Streamer.emitIntValue(0, 4);
       else
         Streamer.emitSymbolValue(LPSymbol, 4);
     };
   } else {
-    assert(!EmitColdPart &&
-           "cannot have exceptions in cold fragment for shared object");
     Streamer.emitIntValue(dwarf::DW_EH_PE_omit, 1); // LPStart format
     emitLandingPad = [&](const MCSymbol *LPSymbol) {
       if (!LPSymbol)
         Streamer.emitIntValue(0, 4);
       else
         Streamer.emitAbsoluteSymbolDiff(LPSymbol, StartSymbol, 4);
     };
   }

bolt/lib/Core/MCPlusBuilder.cpp

if (isCall(Inst)) {
     assert(!getEHInfo(Inst));
     setAnnotationOpValue(Inst, MCAnnotation::kEHLandingPad,
                          reinterpret_cast<int64_t>(LP.first));
     setAnnotationOpValue(Inst, MCAnnotation::kEHAction,
                          static_cast<int64_t>(LP.second));
   }
 }
 
+bool MCPlusBuilder::updateEHInfo(MCInst &Inst, const MCLandingPad &LP) {
+  if (!isInvoke(Inst))
+    return false;
+
+  setAnnotationOpValue(Inst, MCAnnotation::kEHLandingPad,
+                       reinterpret_cast<int64_t>(LP.first));
+  setAnnotationOpValue(Inst, MCAnnotation::kEHAction,
+                       static_cast<int64_t>(LP.second));
+  return true;
+}
+
 int64_t MCPlusBuilder::getGnuArgsSize(const MCInst &Inst) const {
   Optional<int64_t> Value =
       getAnnotationOpValue(Inst, MCAnnotation::kGnuArgsSize);
   if (!Value)
     return -1LL;
   return *Value;
 }
 

bolt/lib/Passes/SplitFunctions.cpp

void SplitFunctions::splitFunction(BinaryFunction &BF) {
   if (!BF.size())
     return;
 
   if (!BF.hasValidProfile())
     return;
 
   bool AllCold = true;
   for (BinaryBasicBlock *BB : BF.layout()) {
-    uint64_t ExecCount = BB->getExecutionCount();
+    const uint64_t ExecCount = BB->getExecutionCount();
     if (ExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
       return;
     if (ExecCount != 0)
       AllCold = false;
   }
 
   if (AllCold)
     return;
 
   BinaryFunction::BasicBlockOrderType PreSplitLayout = BF.getLayout();
 
   BinaryContext &BC = BF.getBinaryContext();
   size_t OriginalHotSize;
   size_t HotSize;
   size_t ColdSize;
   if (BC.isX86()) {
     std::tie(OriginalHotSize, ColdSize) = BC.calculateEmittedSize(BF);
     LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
                       << " pre-split is <0x"
                       << Twine::utohexstr(OriginalHotSize) << ", 0x"
                       << Twine::utohexstr(ColdSize) << ">\n");
-  }
-
-  if (opts::SplitFunctions == SplitFunctions::ST_LARGE && !BC.HasRelocations) {
+    if (opts::SplitFunctions == SplitFunctions::ST_LARGE &&
+        !BC.HasRelocations) {
       // Split only if the function wouldn't fit.
       if (OriginalHotSize <= BF.getMaxSize())
         return;
     }
+  }
 
   // Never outline the first basic block.
   BF.layout_front()->setCanOutline(false);
   for (BinaryBasicBlock *BB : BF.layout()) {
     if (!BB->canOutline())
       continue;
     if (BB->getExecutionCount() != 0) {
       BB->setCanOutline(false);
       continue;
     }
     // Do not split extra entry points in aarch64. They can be referred by
     // using ADRs and when this happens, these blocks cannot be placed far
     // away due to the limited range in ADR instruction.
     if (BC.isAArch64() && BB->isEntryPoint()) {
       BB->setCanOutline(false);
       continue;
     }
+
     if (BF.hasEHRanges() && !opts::SplitEH) {
-      // We cannot move landing pads (or rather entry points for landing
-      // pads).
+      // We cannot move landing pads (or rather entry points for landing pads).
       if (BB->isLandingPad()) {
         BB->setCanOutline(false);
         continue;
       }
       // We cannot move a block that can throw since exception-handling
       // runtime cannot deal with split functions. However, if we can guarantee
       // that the block never throws, it is safe to move the block to
       // decrease the size of the function.
       for (MCInst &Instr : *BB) {
-        if (BF.getBinaryContext().MIB->isInvoke(Instr)) {
+        if (BC.MIB->isInvoke(Instr)) {
           BB->setCanOutline(false);
           break;
         }
       }
     }
   }
 
   if (opts::AggressiveSplitting) {
void SplitFunctions::splitFunction(BinaryFunction &BF) {
   // Separate hot from cold starting from the bottom.
   for (auto I = BF.layout_rbegin(), E = BF.layout_rend(); I != E; ++I) {
     BinaryBasicBlock *BB = *I;
     if (!BB->canOutline())
       break;
     BB->setIsCold(true);
   }
 
+  // For shared objects, place invoke instructions and corresponding landing
+  // pads in the same fragment. To reduce hot code size, create trampoline
+  // landing pads that will redirect the execution to the real LP.
+  if (!BC.HasFixedLoadAddress && BF.hasEHRanges() && BF.isSplit())
+    createEHTrampolines(BF);
+
   // Check the new size to see if it's worth splitting the function.
   if (BC.isX86() && BF.isSplit()) {
     std::tie(HotSize, ColdSize) = BC.calculateEmittedSize(BF);
     LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
                       << " post-split is <0x" << Twine::utohexstr(HotSize)
                       << ", 0x" << Twine::utohexstr(ColdSize) << ">\n");
     if (alignTo(OriginalHotSize, opts::SplitAlignThreshold) <=
         alignTo(HotSize, opts::SplitAlignThreshold) + opts::SplitThreshold) {
       LLVM_DEBUG(dbgs() << "Reversing splitting of function " << BF << ":\n  0x"
                         << Twine::utohexstr(HotSize) << ", 0x"
                         << Twine::utohexstr(ColdSize) << " -> 0x"
                         << Twine::utohexstr(OriginalHotSize) << '\n');
 
       BF.updateBasicBlockLayout(PreSplitLayout);
       for (BinaryBasicBlock &BB : BF)
         BB.setIsCold(false);
     } else {
       SplitBytesHot += HotSize;
       SplitBytesCold += ColdSize;
     }
   }
 }
 
+void SplitFunctions::createEHTrampolines(BinaryFunction &BF) const {
+  const auto &MIB = BF.getBinaryContext().MIB;
+
+  // Map real landing pads to the corresponding trampolines.
+  std::unordered_map<const MCSymbol *, const MCSymbol *> LPTrampolines;
+
+  // Iterate over the copy of basic blocks since we are adding new blocks to the
+  // 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;
+
+      const MCSymbol *LPLabel = EHInfo->first;
+      BinaryBasicBlock *LPBlock = BF.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();
+        TrampolineBB->setIsCold(BB->isCold());
+        TrampolineBB->setExecutionCount(LPBlock->getExecutionCount());
+        TrampolineBB->addSuccessor(LPBlock, TrampolineBB->getExecutionCount());
+        TrampolineBB->setCFIState(LPBlock->getCFIState());
+        TrampolineLabel = TrampolineBB->getLabel();
+        LPTrampolines.emplace(std::make_pair(LPLabel, TrampolineLabel));
+      }
+
+      // Substitute the landing pad with the trampoline.
+      MIB->updateEHInfo(Instr,
+                        MCPlus::MCLandingPad(TrampolineLabel, EHInfo->second));
+    }
+  }
+
+  if (LPTrampolines.empty())
+    return;
+
+  // All trampoline blocks were added to the end of the function. Place them at
+  // the end of corresponding fragments.
+  std::stable_sort(BF.layout_begin(), BF.layout_end(),
+                   [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
+                     return A->isCold() < B->isCold();
+                   });
+
+  // Conservatively introduce branch instructions.
+  BF.fixBranches();
+
+  // Update exception-handling CFG for the function.
+  BF.recomputeLandingPads();
+}
+
 } // namespace bolt
 } // namespace llvm

bolt/lib/Rewrite/RewriteInstance.cpp

if (opts::AlignMacroOpFusion != MFT_NONE && !BC->HasRelocations) {
     opts::AlignMacroOpFusion = MFT_NONE;
   }
 
   if (opts::SplitEH && !BC->HasRelocations) {
     errs() << "BOLT-WARNING: disabling -split-eh in non-relocation mode\n";
     opts::SplitEH = false;
   }
 
-  if (opts::SplitEH && !BC->HasFixedLoadAddress) {
-    errs() << "BOLT-WARNING: disabling -split-eh for shared object\n";
-    opts::SplitEH = false;
-  }
-
   if (opts::StrictMode && !BC->HasRelocations) {
     errs() << "BOLT-WARNING: disabling strict mode (-strict) in non-relocation "
               "mode\n";
     opts::StrictMode = false;
   }
 
   if (BC->HasRelocations && opts::AggregateOnly &&
       !opts::StrictMode.getNumOccurrences()) {

bolt/test/runtime/X86/Inputs/exceptions_split.cpp

 void filter_only(){
   foo();
 }
 
 int main(int argc, char **argv)
 {
   unsigned r = 0;
 
-  uint64_t limit = (argc >= 2 ? 10 : 500000000);
+  uint64_t limit = (argc >= 2 ? 10 : 5000);
   for (uint64_t i = 0; i < limit; ++i) {
     i += foo();
     try  {
       bar(argc);
       try {
         if (argc >= 2)
           throw new int();
       } catch (...) {

bolt/test/runtime/X86/pie-exceptions-split.test

+## Check that BOLT successfully splits C++ exception-handling code for
+## PIEs or shared objects.
+
+REQUIRES: system-linux
+
+RUN: %clangxx %cxxflags -pie -fPIC %p/Inputs/exceptions_split.cpp -Wl,-q -o %t
+RUN: llvm-bolt %t -o %t.instr --instrument --instrumentation-file=%t.fdata
+
+## Record profile with invocation that does not throw exceptions.
+RUN: %t.instr
+
+RUN: llvm-bolt %t -o %t.bolt --data %t.fdata --reorder-blocks=ext-tsp \
+RUN:   --split-functions=1 --split-eh --print-after-lowering \
+RUN:   --print-only=main 2>&1 | FileCheck %s
+
+## All calls to printf() should be from exception handling code that was
+## recorded as cold during the profile collection run. Check that the calls
+## are placed after the split point.
+CHECK-NOT: callq printf
+CHECK: HOT-COLD SPLIT POINT
+CHECK:     callq printf
+
+## Verify the output still executes correctly when the exception path is being
+## taken.
+RUN: %t.bolt arg1 arg2 arg3 2>&1 | FileCheck --check-prefix=CHECK-BOLTED %s
+
+CHECK-BOLTED:      catch 2
+CHECK-BOLTED-NEXT: catch 1
+