Index: lib/CodeGen/InlineSpiller.cpp
===================================================================
--- lib/CodeGen/InlineSpiller.cpp
+++ lib/CodeGen/InlineSpiller.cpp
@@ -13,6 +13,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "Spiller.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
@@ -71,7 +72,7 @@
   // Map from pair of (StackSlot and Original VNI) to a set of spills which
   // have the same stackslot and have equal values defined by Original VNI.
   // These spills are mergeable and are hoist candiates.
-  typedef DenseMap<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>
+  typedef MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>
       MergeableSpillsMap;
   MergeableSpillsMap MergeableSpills;
 
@@ -114,7 +115,7 @@
         MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
 
   void addToMergeableSpills(MachineInstr *Spill, int StackSlot,
-                           unsigned Original);
+                            unsigned Original);
   bool rmFromMergeableSpills(MachineInstr *Spill, int StackSlot);
   void hoistAllSpills(LiveRangeEdit &Edit);
 };
@@ -1049,7 +1050,7 @@
 /// When a spill is inserted, add the spill to MergeableSpills map.
 ///
 void HoistSpillHelper::addToMergeableSpills(MachineInstr *Spill, int StackSlot,
-                                           unsigned Original) {
+                                            unsigned Original) {
   StackSlotToReg[StackSlot] = Original;
   SlotIndex Idx = LIS.getInstructionIndex(*Spill);
   VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot());
@@ -1242,7 +1243,7 @@
   getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
                  SpillBBToSpill);
 
-  // SpillsInSubTree keeps the map from a dom tree node to a pair of
+  // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
   // nodes set and the cost of all the spills inside those nodes.
   // The nodes set are the locations where spills are to be inserted
   // in the subtree of current node.
@@ -1256,32 +1257,37 @@
   SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
   for (; RIt != Orders.rend(); RIt++) {
     MachineBasicBlock *Block = (*RIt)->getBlock();
-    SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
-        SpillsInSubTreeMap[*RIt].first;
-    // Total spill costs inside the sub tree.
-    BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
 
     // If Block contains an original spill, simply continue.
     if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
-      SpillsInSubTree.insert(*RIt);
-      SubTreeCost = MBFI.getBlockFreq(Block);
+      SpillsInSubTreeMap[*RIt].first.insert(*RIt);
+      // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
+      SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
       continue;
     }
 
     // Collect spills in subtree of current node (*RIt) to
-    // SpillsInSubTree.
+    // SpillsInSubTreeMap[*RIt].first.
     const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren();
     unsigned NumChildren = Children.size();
     for (unsigned i = 0; i != NumChildren; ++i) {
       MachineDomTreeNode *Child = Children[i];
-      SpillsInSubTree.insert(SpillsInSubTreeMap[Child].first.begin(),
-                             SpillsInSubTreeMap[Child].first.end());
-      SubTreeCost += SpillsInSubTreeMap[Child].second;
+      if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end())
+        continue;
+      // SpillsInSubTreeMap[*RIt].second += SpillsInSubTreeMap[Child].second
+      // should be placed before getting the begin and end iterators of
+      // SpillsInSubTreeMap[Child].first, or else the iterators may be
+      // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
+      // and the map grows and then the original buckets in the map are moved.
+      SpillsInSubTreeMap[*RIt].second += SpillsInSubTreeMap[Child].second;
+      auto BI = SpillsInSubTreeMap[Child].first.begin();
+      auto EI = SpillsInSubTreeMap[Child].first.end();
+      SpillsInSubTreeMap[*RIt].first.insert(BI, EI);
       SpillsInSubTreeMap.erase(Child);
     }
 
     // No spills in subtree, simply continue.
-    if (SpillsInSubTree.empty())
+    if (SpillsInSubTreeMap[*RIt].first.empty())
       continue;
 
     // Check whether Block is a possible candidate to insert spill.
@@ -1291,12 +1297,13 @@
 
     // If there are multiple spills that could be merged, bias a little
     // to hoist the spill.
-    BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
+    BranchProbability MarginProb = (SpillsInSubTreeMap[*RIt].first.size() > 1)
                                        ? BranchProbability(9, 10)
                                        : BranchProbability(1, 1);
-    if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
+    if (SpillsInSubTreeMap[*RIt].second >
+        MBFI.getBlockFreq(Block) * MarginProb) {
       // Hoist: Move spills to current Block.
-      for (const auto SpillBB : SpillsInSubTree) {
+      for (const auto SpillBB : SpillsInSubTreeMap[*RIt].first) {
         // When SpillBB is a BB contains original spill, insert the spill
         // to SpillsToRm.
         if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() &&
@@ -1312,14 +1319,14 @@
       SpillsToKeep[*RIt] = LiveReg;
       DEBUG({
         dbgs() << "spills in BB: ";
-        for (const auto Rspill : SpillsInSubTree)
+        for (const auto Rspill : SpillsInSubTreeMap[*RIt].first)
           dbgs() << Rspill->getBlock()->getNumber() << " ";
         dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()
                << "\n";
       });
-      SpillsInSubTree.clear();
-      SpillsInSubTree.insert(*RIt);
-      SubTreeCost = MBFI.getBlockFreq(Block);
+      SpillsInSubTreeMap[*RIt].first.clear();
+      SpillsInSubTreeMap[*RIt].first.insert(*RIt);
+      SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
     }
   }
   // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),