3 files changed, 57 insertions, 9 deletions

diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h
index a7b9306b3a7..ede3a9ced36 100644
--- a/llvm/include/llvm/ADT/ilist.h
+++ b/llvm/include/llvm/ADT/ilist.h
@@ -579,6 +579,53 @@ public:
   void splice(iterator where, iplist &L2, iterator first, iterator last) {
     if (first != last) transfer(where, L2, first, last);
   }
+
+  template <class Compare>
+  void merge(iplist &Right, Compare comp) {
+    if (this == &Right)
+      return;
+    iterator First1 = begin(), Last1 = end();
+    iterator First2 = Right.begin(), Last2 = Right.end();
+    while (First1 != Last1 && First2 != Last2) {
+      if (comp(*First2, *First1)) {
+        iterator Next = First2;
+        transfer(First1, Right, First2, ++Next);
+        First2 = Next;
+      } else {
+        ++First1;
+      }
+    }
+    if (First2 != Last2)
+      transfer(Last1, Right, First2, Last2);
+  }
+  void merge(iplist &Right) { return merge(Right, op_less); }
+
+  template <class Compare>
+  void sort(Compare comp) {
+    // The list is empty, vacuously sorted.
+    if (empty())
+      return;
+    // The list has a single element, vacuously sorted.
+    if (std::next(begin()) == end())
+      return;
+    // Find the split point for the list.
+    iterator Center = begin(), End = begin();
+    while (End != end() && std::next(End) != end()) {
+      Center = std::next(Center);
+      End = std::next(std::next(End));
+    }
+    // Split the list into two.
+    iplist RightHalf;
+    RightHalf.splice(RightHalf.begin(), *this, Center, end());
+
+    // Sort the two sublists.
+    sort(comp);
+    RightHalf.sort(comp);
+
+    // Merge the two sublists back together.
+    merge(RightHalf, comp);
+  }
+  void sort() { sort(op_less); }
 };
 
 
diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h
index 9a253226a1c..1a102c05000 100644
--- a/llvm/include/llvm/CodeGen/MachineFunction.h
+++ b/llvm/include/llvm/CodeGen/MachineFunction.h
@@ -375,6 +375,11 @@ public:
     BasicBlocks.erase(MBBI);
   }
 
+  template <typename Comp>
+  void sort(Comp comp) {
+    BasicBlocks.sort(comp);
+  }
+
   //===--------------------------------------------------------------------===//
   // Internal functions used to automatically number MachineBasicBlocks
   //
diff --git a/llvm/lib/CodeGen/FuncletLayout.cpp b/llvm/lib/CodeGen/FuncletLayout.cpp
index 9b40a1a7558..0cda11f53db 100644
--- a/llvm/lib/CodeGen/FuncletLayout.cpp
+++ b/llvm/lib/CodeGen/FuncletLayout.cpp
@@ -12,7 +12,6 @@
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/Passes.h"
-#include "llvm/ADT/MapVector.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
@@ -34,7 +33,7 @@ public:
 }
 
 static void
-collectFuncletMembers(MapVector<MachineBasicBlock *, int> &FuncletMembership,
+collectFuncletMembers(DenseMap<MachineBasicBlock *, int> &FuncletMembership,
                       int Funclet, MachineBasicBlock *MBB) {
   // Don't revisit blocks.
   if (FuncletMembership.count(MBB) > 0)
@@ -81,16 +80,13 @@ bool FuncletLayout::runOnMachineFunction(MachineFunction &F) {
   if (FuncletBlocks.empty())
     return false;
 
-  MapVector<MachineBasicBlock *, int> FuncletMembership;
+  DenseMap<MachineBasicBlock *, int> FuncletMembership;
   for (MachineBasicBlock *MBB : FuncletBlocks)
     collectFuncletMembers(FuncletMembership, MBB->getNumber(), MBB);
 
-  for (std::pair<llvm::MachineBasicBlock *, int> &FuncletMember :
-       FuncletMembership) {
-    // Move this block to the end of the function.
-    MachineBasicBlock *MBB = FuncletMember.first;
-    MBB->moveAfter(--F.end());
-  }
+  F.sort([&](MachineBasicBlock &x, MachineBasicBlock &y) {
+    return FuncletMembership[&x] < FuncletMembership[&y];
+  });
 
   // Conservatively assume we changed something.
   return true;