From 0115643a5be1128254b906e312579a24cb4b0b6c Mon Sep 17 00:00:00 2001
From: David Majnemer <david.majnemer@gmail.com>
Date: Fri, 18 Sep 2015 08:18:07 +0000
Subject: [PATCH] [WinEH] Moved funclet pads should be in relative order

We shifted the MachineBasicBlocks to the end of the MachineFunction in
DFS order.  This will not ensure that MachineBasicBlocks which fell
through to one another will remain contiguous.  Instead, implement
a stable sort algorithm for iplist.

This partially reverts commit r214150.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@247978 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/ilist.h               | 47 ++++++++++++++++++++++++++
 include/llvm/CodeGen/MachineFunction.h |  5 +++
 lib/CodeGen/FuncletLayout.cpp          | 14 +++-----
 3 files changed, 57 insertions(+), 9 deletions(-)

diff --git a/include/llvm/ADT/ilist.h b/include/llvm/ADT/ilist.h
index a7b9306b3a7..ede3a9ced36 100644
--- a/include/llvm/ADT/ilist.h
+++ b/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/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h
index 9a253226a1c..1a102c05000 100644
--- a/include/llvm/CodeGen/MachineFunction.h
+++ b/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/lib/CodeGen/FuncletLayout.cpp b/lib/CodeGen/FuncletLayout.cpp
index 9b40a1a7558..0cda11f53db 100644
--- a/lib/CodeGen/FuncletLayout.cpp
+++ b/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;
-- 
2.34.1