Index: include/llvm/Analysis/RegionInfo.h
===================================================================
--- include/llvm/Analysis/RegionInfo.h
+++ include/llvm/Analysis/RegionInfo.h
@@ -39,6 +39,7 @@
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
@@ -678,7 +679,7 @@
   friend class MachineRegionInfo;
   typedef DenseMap<BlockT *, BlockT *> BBtoBBMap;
   typedef DenseMap<BlockT *, RegionT *> BBtoRegionMap;
-  typedef SmallPtrSet<RegionT *, 4> RegionSet;
+  typedef SmallSetVector<RegionT *, 4> RegionSet;
 
   RegionInfoBase();
   virtual ~RegionInfoBase();
Index: lib/CodeGen/LocalStackSlotAllocation.cpp
===================================================================
--- lib/CodeGen/LocalStackSlotAllocation.cpp
+++ lib/CodeGen/LocalStackSlotAllocation.cpp
@@ -264,6 +264,10 @@
   return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
 }
 
+static bool compareFrameRefs(const FrameRef &LHS, const FrameRef &RHS) {
+  return LHS.getLocalOffset() < RHS.getLocalOffset();
+}
+
 bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
   // Scan the function's instructions looking for frame index references.
   // For each, ask the target if it wants a virtual base register for it
@@ -318,8 +322,11 @@
     }
   }
 
-  // Sort the frame references by local offset
-  array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());
+  // Sort the frame references by local offset.
+  // Note: We need to use a stable sort here as qsort does not guarantee
+  // relative order of MIs having the same local offset.
+  std::stable_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end(),
+                   compareFrameRefs);
 
   MachineBasicBlock *Entry = &Fn.front();
 
Index: lib/CodeGen/MachineScheduler.cpp
===================================================================
--- lib/CodeGen/MachineScheduler.cpp
+++ lib/CodeGen/MachineScheduler.cpp
@@ -1421,7 +1421,7 @@
   if (MemOpRecords.size() < 2)
     return;
 
-  std::sort(MemOpRecords.begin(), MemOpRecords.end());
+  std::stable_sort(MemOpRecords.begin(), MemOpRecords.end());
   unsigned ClusterLength = 1;
   for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
     if (MemOpRecords[Idx].BaseReg != MemOpRecords[Idx+1].BaseReg) {