diff --git a/bolt/include/bolt/Core/FunctionLayout.h b/bolt/include/bolt/Core/FunctionLayout.h
--- a/bolt/include/bolt/Core/FunctionLayout.h
+++ b/bolt/include/bolt/Core/FunctionLayout.h
@@ -39,11 +39,24 @@
   constexpr FragmentNum() = default;
   constexpr explicit FragmentNum(unsigned Value) : Value(Value) {}
   constexpr unsigned get() const { return Value; }
+
   constexpr bool operator==(const FragmentNum Other) const {
     return Value == Other.Value;
   }
   constexpr bool operator!=(const FragmentNum Other) const {
-    return !(*this == Other);
+    return Value != Other.Value;
+  }
+  constexpr bool operator<(const FragmentNum Other) const {
+    return Value < Other.Value;
+  }
+  constexpr bool operator<=(const FragmentNum Other) const {
+    return Value <= Other.Value;
+  }
+  constexpr bool operator>=(const FragmentNum Other) const {
+    return Value >= Other.Value;
+  }
+  constexpr bool operator>(const FragmentNum Other) const {
+    return Value > Other.Value;
   }
 
   static constexpr FragmentNum main() { return FragmentNum(0); }
diff --git a/bolt/include/bolt/Passes/SplitFunctions.h b/bolt/include/bolt/Passes/SplitFunctions.h
--- a/bolt/include/bolt/Passes/SplitFunctions.h
+++ b/bolt/include/bolt/Passes/SplitFunctions.h
@@ -9,7 +9,9 @@
 #ifndef BOLT_PASSES_SPLIT_FUNCTIONS_H
 #define BOLT_PASSES_SPLIT_FUNCTIONS_H
 
+#include "bolt/Core/FunctionLayout.h"
 #include "bolt/Passes/BinaryPasses.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/Support/CommandLine.h"
 #include <atomic>
 
@@ -39,8 +41,29 @@
   template <typename Strategy>
   void splitFunction(BinaryFunction &Function, Strategy S = {});
 
+  struct TrampolineKey {
+    FragmentNum SourceFN = FragmentNum::main();
+    const MCSymbol *Target = nullptr;
+
+    TrampolineKey() = default;
+    TrampolineKey(const FragmentNum SourceFN, const MCSymbol *const Target)
+        : SourceFN(SourceFN), Target(Target) {}
+
+    static inline TrampolineKey getEmptyKey() { return TrampolineKey(); };
+    static inline TrampolineKey getTombstoneKey() {
+      return TrampolineKey(FragmentNum(UINT_MAX), nullptr);
+    };
+    static unsigned getHashValue(const TrampolineKey &Val) {
+      return llvm::hash_combine(Val.SourceFN.get(), Val.Target);
+    }
+    static bool isEqual(const TrampolineKey &LHS, const TrampolineKey &RHS) {
+      return LHS.SourceFN == RHS.SourceFN && LHS.Target == RHS.Target;
+    }
+  };
+
   /// Map basic block labels to their trampoline block labels.
-  using TrampolineSetType = DenseMap<const MCSymbol *, const MCSymbol *>;
+  using TrampolineSetType =
+      DenseMap<TrampolineKey, const MCSymbol *, TrampolineKey>;
 
   using BasicBlockOrderType = BinaryFunction::BasicBlockOrderType;
 
diff --git a/bolt/lib/Passes/SplitFunctions.cpp b/bolt/lib/Passes/SplitFunctions.cpp
--- a/bolt/lib/Passes/SplitFunctions.cpp
+++ b/bolt/lib/Passes/SplitFunctions.cpp
@@ -433,11 +433,12 @@
 
       const MCSymbol *LPLabel = EHInfo->first;
       BinaryBasicBlock *LPBlock = BF.getBasicBlockForLabel(LPLabel);
-      if (BB->isCold() == LPBlock->isCold())
+      if (BB->getFragmentNum() == LPBlock->getFragmentNum())
         continue;
 
       const MCSymbol *TrampolineLabel = nullptr;
-      auto Iter = LPTrampolines.find(LPLabel);
+      const TrampolineKey Key(BB->getFragmentNum(), LPLabel);
+      auto Iter = LPTrampolines.find(Key);
       if (Iter != LPTrampolines.end()) {
         TrampolineLabel = Iter->second;
       } else {
@@ -445,12 +446,12 @@
         // 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->setFragmentNum(BB->getFragmentNum());
         TrampolineBB->setExecutionCount(LPBlock->getExecutionCount());
         TrampolineBB->addSuccessor(LPBlock, TrampolineBB->getExecutionCount());
         TrampolineBB->setCFIState(LPBlock->getCFIState());
         TrampolineLabel = TrampolineBB->getLabel();
-        LPTrampolines.insert(std::make_pair(LPLabel, TrampolineLabel));
+        LPTrampolines.insert(std::make_pair(Key, TrampolineLabel));
       }
 
       // Substitute the landing pad with the trampoline.
@@ -467,7 +468,7 @@
   BinaryFunction::BasicBlockOrderType NewLayout(BF.getLayout().block_begin(),
                                                 BF.getLayout().block_end());
   stable_sort(NewLayout, [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
-    return A->isCold() < B->isCold();
+    return A->getFragmentNum() < B->getFragmentNum();
   });
   BF.getLayout().update(NewLayout);
 
@@ -483,13 +484,22 @@
 SplitFunctions::BasicBlockOrderType SplitFunctions::mergeEHTrampolines(
     BinaryFunction &BF, SplitFunctions::BasicBlockOrderType &Layout,
     const SplitFunctions::TrampolineSetType &Trampolines) const {
+  DenseMap<const MCSymbol *, SmallVector<const MCSymbol *, 0>>
+      IncomingTrampolines;
+  for (const auto &Entry : Trampolines) {
+    IncomingTrampolines[Entry.getFirst().Target].emplace_back(
+        Entry.getSecond());
+  }
+
   BasicBlockOrderType MergedLayout;
   for (BinaryBasicBlock *BB : Layout) {
-    auto Iter = Trampolines.find(BB->getLabel());
-    if (Iter != Trampolines.end()) {
-      BinaryBasicBlock *LPBlock = BF.getBasicBlockForLabel(Iter->second);
-      assert(LPBlock && "Could not find matching landing pad block.");
-      MergedLayout.push_back(LPBlock);
+    auto Iter = IncomingTrampolines.find(BB->getLabel());
+    if (Iter != IncomingTrampolines.end()) {
+      for (const MCSymbol *const Trampoline : Iter->getSecond()) {
+        BinaryBasicBlock *LPBlock = BF.getBasicBlockForLabel(Trampoline);
+        assert(LPBlock && "Could not find matching landing pad block.");
+        MergedLayout.push_back(LPBlock);
+      }
     }
     MergedLayout.push_back(BB);
   }