post-commit patch review for r265547

[wmi]

Summary

The patch contains three commits. I put them together here for easier review.

http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160404/345226.html
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160404/345430.html
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160404/345502.html

[qcolombet]

lib/CodeGen/InlineSpiller.cpp

1276

Since we make sure not to create an entry for Child, I believe it is safe to SpillsInSubTreeMap[*RIt] in a local variable.
That should make the code a but more readable.

[wmi]

lib/CodeGen/InlineSpiller.cpp

1276

Will fix it in the next commit.

[Eugene.Zelenko]

Settled in r266162.

lib/CodeGen/InlineSpiller.cpp

 //===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // The inline spiller modifies the machine function directly instead of
 // inserting spills and restores in VirtRegMap.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Spiller.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
class HoistSpillHelper {
   const TargetRegisterInfo &TRI;
   const MachineBlockFrequencyInfo &MBFI;
 
   // Map from StackSlot to its original register.
   DenseMap<int, unsigned> StackSlotToReg;
   // 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;
 
   /// This is the map from original register to a set containing all its
   /// siblings. To hoist a spill to another BB, we need to find out a live
   /// sibling there and use it as the source of the new spill.
   DenseMap<unsigned, SmallSetVector<unsigned, 16>> Virt2SiblingsMap;
 
HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
         MDT(pass.getAnalysis<MachineDominatorTree>()),
         Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
         MFI(*mf.getFrameInfo()), MRI(mf.getRegInfo()),
         TII(*mf.getSubtarget().getInstrInfo()),
         TRI(*mf.getSubtarget().getRegisterInfo()),
         MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()) {}
 
   void addToMergeableSpills(MachineInstr *Spill, int StackSlot,
                             unsigned Original);
   bool rmFromMergeableSpills(MachineInstr *Spill, int StackSlot);
   void hoistAllSpills(LiveRangeEdit &Edit);
 };
 
 class InlineSpiller : public Spiller {
   MachineFunction &MF;
   LiveIntervals &LIS;
   LiveStacks &LSS;
void InlineSpiller::postOptimization() {
   HSpiller.hoistAllSpills(LRE);
   assert(NewVRegs.size() == 0 &&
          "No new vregs should be generated in hoistAllSpills");
 }
 
 /// When a spill is inserted, add the spill to MergeableSpills map.
 ///
 void HoistSpillHelper::addToMergeableSpills(MachineInstr *Spill, int StackSlot,
                                             unsigned Original) {
   StackSlotToReg[StackSlot] = Original;
   SlotIndex Idx = LIS.getInstructionIndex(*Spill);
   VNInfo *OrigVNI = LIS.getInterval(Original).getVNInfoAt(Idx.getRegSlot());
   std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
   MergeableSpills[MIdx].insert(Spill);
 }
 
 /// When a spill is removed, remove the spill from MergeableSpills map.
void HoistSpillHelper::runHoistSpills(
   DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill;
 
   rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
 
   MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
   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.
   typedef std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>
       NodesCostPair;
   DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap;
   // Iterate Orders set in reverse order, which will be a bottom-up order
   // in the dominator tree. Once we visit a dom tree node, we know its
   // children have already been visited and the spill locations in the
   // subtrees of all the children have been determined.
   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.
     unsigned LiveReg = 0;
     if (!isSpillCandBB(OrigReg, OrigVNI, *Block, LiveReg))
       continue;
 
     // 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() &&
             !SpillsToKeep[SpillBB]) {
           MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
           SpillsToRm.push_back(SpillToRm);
         }
         // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
         SpillsToKeep.erase(SpillBB);
       }
       // Current Block is the BB containing the new hoisted spill. Add it to
       // SpillsToKeep. LiveReg is the source of the new spill.
       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),
   // save them to SpillsToIns.
   for (const auto Ent : SpillsToKeep) {
     if (Ent.second)
       SpillsToIns[Ent.first->getBlock()] = Ent.second;
   }