Recover compile time regression.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44386 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 76 insertions, 89 deletions

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index e4582f7..c803fbd 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -292,7 +292,7 @@ namespace llvm {
         VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc,
         SmallVector<int, 4> &ReMatIds,
         unsigned &NewVReg, bool &HasDef, bool &HasUse, const LoopInfo *loopInfo,
-        std::vector<unsigned> &NewVRegs,
+        std::map<unsigned,unsigned> &NewVRegs,
         std::vector<LiveInterval*> &NewLIs);
     void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
         LiveInterval::Ranges::const_iterator &I,
@@ -301,8 +301,8 @@ namespace llvm {
         VirtRegMap &vrm, SSARegMap *RegMap, const TargetRegisterClass* rc,
         SmallVector<int, 4> &ReMatIds, const LoopInfo *loopInfo,
         BitVector &SpillMBBs,
-        std::vector<std::pair<int, unsigned> > &SpillIdxes,
-        std::vector<unsigned> &NewVRegs,
+        std::map<unsigned, std::pair<int, unsigned> > &SpillIdxes,
+        std::map<unsigned,unsigned> &NewVRegs,
         std::vector<LiveInterval*> &NewLIs);
 
     static LiveInterval createInterval(unsigned Reg);
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index d2e32ab..238d8aa 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -707,7 +707,8 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
                  const TargetRegisterClass* rc,
                  SmallVector<int, 4> &ReMatIds,
                  unsigned &NewVReg, bool &HasDef, bool &HasUse,
-                 const LoopInfo *loopInfo, std::vector<unsigned> &NewVRegs,
+                 const LoopInfo *loopInfo,
+                 std::map<unsigned,unsigned> &NewVRegs,
                  std::vector<LiveInterval*> &NewLIs) {
  RestartInstruction:
   for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
@@ -731,6 +732,7 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
       // all of its uses are rematerialized, simply delete it.
       if (MI == ReMatOrigDefMI && CanDelete) {
         RemoveMachineInstrFromMaps(MI);
+        vrm.RemoveMachineInstrFromMaps(MI);
         MI->eraseFromParent();
         break;
       }
@@ -823,7 +825,7 @@ rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
     LiveInterval &nI = getOrCreateInterval(NewVReg);
     if (CreatedNewVReg) {
       NewLIs.push_back(&nI);
-      NewVRegs[MI->getParent()->getNumber()] = NewVReg;
+      NewVRegs.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
       if (TrySplit)
         vrm.setIsSplitFromReg(NewVReg, li.reg);
     }
@@ -893,8 +895,8 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
                     SmallVector<int, 4> &ReMatIds,
                     const LoopInfo *loopInfo,
                     BitVector &SpillMBBs,
-                    std::vector<std::pair<int, unsigned> > &SpillIdxes,
-                    std::vector<unsigned> &NewVRegs,
+                    std::map<unsigned, std::pair<int, unsigned> > &SpillIdxes,
+                    std::map<unsigned,unsigned> &NewVRegs,
                     std::vector<LiveInterval*> &NewLIs) {
   unsigned NewVReg = 0;
   unsigned index = getBaseIndex(I->start);
@@ -908,7 +910,13 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
 
     MachineInstr *MI = getInstructionFromIndex(index);
     MachineBasicBlock *MBB = MI->getParent();
-    NewVReg = !TrySplitMI ? 0 : NewVRegs[MBB->getNumber()];
+    NewVReg = 0;
+    if (TrySplitMI) {
+      std::map<unsigned,unsigned>::const_iterator NVI =
+        NewVRegs.find(MBB->getNumber());
+      if (NVI != NewVRegs.end())
+        NewVReg = NVI->second;
+    }
     bool IsNew = NewVReg == 0;
     bool HasDef = false;
     bool HasUse = false;
@@ -936,9 +944,11 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
             : anyKillInMBBAfterIdx(li, MBB, getDefIndex(index), I->valno);
           if (!HasKill) {
             unsigned MBBId = MBB->getNumber();
-            if ((int)index > SpillIdxes[MBBId].first)
-              // High bit specify whether this spill ought to be folded if
-              // possible.
+            // High bit specify whether this spill ought to be folded if
+            // possible.
+            std::map<unsigned, std::pair<int,unsigned> >::iterator SII =
+              SpillIdxes.find(MBBId);
+            if (SII == SpillIdxes.end() || (int)index > SII->second.first)
               SpillIdxes[MBBId] = std::make_pair(index, NewVReg | (1 << 31));
             SpillMBBs.set(MBBId);
           }
@@ -955,8 +965,11 @@ rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
       } else if (HasUse) {
         // Use(s) following the last def, it's not safe to fold the spill.
         unsigned MBBId = MBB->getNumber();
-        if ((SpillIdxes[MBBId].second & ((1<<31)-1)) == NewVReg &&
-            (int)getUseIndex(index) > SpillIdxes[MBBId].first)
+        std::map<unsigned, std::pair<int,unsigned> >::iterator SII =
+          SpillIdxes.find(MBBId);
+        if (SII != SpillIdxes.end() &&
+            (SII->second.second & ((1<<31)-1)) == NewVReg &&
+            (int)getUseIndex(index) > SII->second.first)
           SpillIdxes[MBBId].second &= (1<<31)-1;
       }
 
@@ -985,9 +998,8 @@ addIntervalsForSpills(const LiveInterval &li,
 
   // Each bit specify whether it a spill is required in the MBB.
   BitVector SpillMBBs(mf_->getNumBlockIDs());
-  std::vector<std::pair<int, unsigned> > SpillIdxes(mf_->getNumBlockIDs(),
-                                                    std::make_pair(-1,0));
-  std::vector<unsigned> NewVRegs(mf_->getNumBlockIDs(), 0);
+  std::map<unsigned, std::pair<int, unsigned> > SpillIdxes;
+  std::map<unsigned,unsigned> NewVRegs;
   std::vector<LiveInterval*> NewLIs;
   SSARegMap *RegMap = mf_->getSSARegMap();
   const TargetRegisterClass* rc = RegMap->getRegClass(li.reg);
@@ -1015,7 +1027,6 @@ addIntervalsForSpills(const LiveInterval &li,
     bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
     bool isLoad = isLoadSS ||
       (DefIsReMat && (ReMatDefMI->getInstrDescriptor()->Flags & M_LOAD_FLAG));
-    vrm.removeAllSpillPtsForReg(li.reg);
     bool IsFirstRange = true;
     for (LiveInterval::Ranges::const_iterator
            I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
@@ -1087,7 +1098,6 @@ addIntervalsForSpills(const LiveInterval &li,
   if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
     Slot = vrm.assignVirt2StackSlot(li.reg);
 
-
   // Create new intervals and rewrite defs and uses.
   for (LiveInterval::Ranges::const_iterator
          I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index fe4f7b7..44faa3a 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -74,7 +74,6 @@ void VirtRegMap::grow() {
   Virt2StackSlotMap.grow(LastVirtReg);
   Virt2ReMatIdMap.grow(LastVirtReg);
   Virt2SplitMap.grow(LastVirtReg);
-  Virt2SpillPtsMap.grow(LastVirtReg);
   ReMatMap.grow(LastVirtReg);
 }
 
@@ -837,7 +836,7 @@ bool LocalSpiller::PrepForUnfoldOpti(MachineBasicBlock &MBB,
           VRM.assignVirt2Phys(UnfoldVR, UnfoldPR);
         VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
         MII = MBB.insert(MII, FoldedMI);
-        VRM.RemoveFromFoldedVirtMap(&MI);
+        VRM.RemoveMachineInstrFromMaps(&MI);
         MBB.erase(&MI);
         return true;
       }
@@ -886,7 +885,7 @@ void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB,
     if (CheckDef)
       --PrevMII;
     MBB.erase(LastStore);
-    VRM.RemoveFromFoldedVirtMap(LastStore);
+    VRM.RemoveMachineInstrFromMaps(LastStore);
     if (CheckDef) {
       // Look at defs of killed registers on the store. Mark the defs
       // as dead since the store has been deleted and they aren't
@@ -899,7 +898,7 @@ void LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB,
             // FIXME: This assumes a remat def does not have side
             // effects.
             MBB.erase(DeadDef);
-            VRM.RemoveFromFoldedVirtMap(DeadDef);
+            VRM.RemoveMachineInstrFromMaps(DeadDef);
             ++NumDRM;
           }
         }
@@ -965,15 +964,19 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
     const TargetInstrDescriptor *TID = MI.getInstrDescriptor();
 
     // Insert spills here if asked to.
-    std::vector<unsigned> SpillRegs = VRM.getSpillPtSpills(&MI);
-    for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) {
-      unsigned VirtReg = SpillRegs[i];
-      const TargetRegisterClass *RC = RegMap->getRegClass(VirtReg);
-      unsigned Phys = VRM.getPhys(VirtReg);
-      int StackSlot = VRM.getStackSlot(VirtReg);
-      MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
-      SpillRegToStackSlot(MBB, MII, i, Phys, StackSlot, RC,
-                          LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM);
+    if (VRM.isSpillPt(&MI)) {
+      std::vector<unsigned> &SpillRegs = VRM.getSpillPtSpills(&MI);
+      for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) {
+        unsigned VirtReg = SpillRegs[i];
+        if (!VRM.getPreSplitReg(VirtReg))
+          continue; // Split interval spilled again.
+        const TargetRegisterClass *RC = RegMap->getRegClass(VirtReg);
+        unsigned Phys = VRM.getPhys(VirtReg);
+        int StackSlot = VRM.getStackSlot(VirtReg);
+        MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
+        SpillRegToStackSlot(MBB, MII, i, Phys, StackSlot, RC,
+                            LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM);
+      }
     }
 
     /// ReusedOperands - Keep track of operand reuse in case we need to undo
@@ -1142,7 +1145,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
             if (DeadStore) {
               DOUT << "Removed dead store:\t" << *DeadStore;
               InvalidateKills(*DeadStore, RegKills, KillOps);
-              VRM.RemoveFromFoldedVirtMap(DeadStore);
+              VRM.RemoveMachineInstrFromMaps(DeadStore);
               MBB.erase(DeadStore);
               MaybeDeadStores[ReuseSlot] = NULL;
               ++NumDSE;
@@ -1295,7 +1298,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
             } else
               DOUT << "Removing now-noop copy: " << MI;
 
-            VRM.RemoveFromFoldedVirtMap(&MI);
+            VRM.RemoveMachineInstrFromMaps(&MI);
             MBB.erase(&MI);
             Erased = true;
             goto ProcessNextInst;
@@ -1306,7 +1309,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
           if (PhysReg &&
               MRI->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) {
             MBB.insert(MII, NewMIs[0]);
-            VRM.RemoveFromFoldedVirtMap(&MI);
+            VRM.RemoveMachineInstrFromMaps(&MI);
             MBB.erase(&MI);
             Erased = true;
             --NextMII;  // backtrack to the unfolded instruction.
@@ -1331,7 +1334,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
             MBB.insert(MII, NewMIs[0]);
             NewStore = NewMIs[1];
             MBB.insert(MII, NewStore);
-            VRM.RemoveFromFoldedVirtMap(&MI);
+            VRM.RemoveMachineInstrFromMaps(&MI);
             MBB.erase(&MI);
             Erased = true;
             --NextMII;
@@ -1345,7 +1348,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
           // If we get here, the store is dead, nuke it now.
           DOUT << "Removed dead store:\t" << *DeadStore;
           InvalidateKills(*DeadStore, RegKills, KillOps);
-          VRM.RemoveFromFoldedVirtMap(DeadStore);
+          VRM.RemoveMachineInstrFromMaps(DeadStore);
           MBB.erase(DeadStore);
           if (!NewStore)
             ++NumDSE;
@@ -1405,7 +1408,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
           DOUT << "Removing now-noop copy: " << MI;
           MBB.erase(&MI);
           Erased = true;
-          VRM.RemoveFromFoldedVirtMap(&MI);
+          VRM.RemoveMachineInstrFromMaps(&MI);
           Spills.disallowClobberPhysReg(VirtReg);
           goto ProcessNextInst;
         }
@@ -1480,7 +1483,7 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
             DOUT << "Removing now-noop copy: " << MI;
             MBB.erase(&MI);
             Erased = true;
-            VRM.RemoveFromFoldedVirtMap(&MI);
+            VRM.RemoveMachineInstrFromMaps(&MI);
             UpdateKills(*LastStore, RegKills, KillOps);
             goto ProcessNextInst;
           }
@@ -1495,7 +1498,6 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
   }
 }
 
-
 llvm::Spiller* llvm::createSpiller() {
   switch (SpillerOpt) {
   default: assert(0 && "Unreachable!");
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index dc2f1cd..f7e5c08 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -80,12 +80,7 @@ namespace llvm {
     /// SpillPt2VirtMap - This records the virtual registers which should
     /// be spilled right after the MachineInstr due to live interval
     /// splitting.
-    DenseMap<MachineInstr*, std::vector<unsigned> > SpillPt2VirtMap;
-
-    /// Virt2SplitMap - This records the MachineInstrs where a virtual
-    /// register should be spilled due to live interval splitting.
-    IndexedMap<std::vector<MachineInstr*>, VirtReg2IndexFunctor>
-    Virt2SpillPtsMap;
+    std::map<MachineInstr*, std::vector<unsigned> > SpillPt2VirtMap;
 
     /// ReMatId - Instead of assigning a stack slot to a to be rematerialized
     /// virtual register, an unique id is being assigned. This keeps track of
@@ -209,6 +204,11 @@ namespace llvm {
       ReMatMap[virtReg] = def;
     }
 
+    /// @brief returns true if the specified MachineInstr is a spill point.
+    bool isSpillPt(MachineInstr *Pt) const {
+      return SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end();
+    }
+
     /// @brief returns the virtual registers that should be spilled due to
     /// splitting right after the specified MachineInstr.
     std::vector<unsigned> &getSpillPtSpills(MachineInstr *Pt) {
@@ -217,52 +217,26 @@ namespace llvm {
 
     /// @brief records the specified MachineInstr as a spill point for virtReg.
     void addSpillPoint(unsigned virtReg, MachineInstr *Pt) {
-      SpillPt2VirtMap[Pt].push_back(virtReg);
-      Virt2SpillPtsMap[virtReg].push_back(Pt);
-    }
-
-    /// @brief remove the virtReg from the list of registers that should be
-    /// spilled (due to splitting) right after the specified MachineInstr.
-    void removeRegFromSpillPt(MachineInstr *Pt, unsigned virtReg) {
-      std::vector<unsigned> &Regs = SpillPt2VirtMap[Pt];
-      if (Regs.back() == virtReg) // Most common case.
-        Regs.pop_back();
-      for (unsigned i = 0, e = Regs.size(); i != e; ++i)
-        if (Regs[i] == virtReg) {
-          Regs.erase(Regs.begin()+i-1);
-          break;
-        }
-    }
-
-    /// @brief specify virtReg is no longer being spilled due to splitting.
-    void removeAllSpillPtsForReg(unsigned virtReg) {
-      std::vector<MachineInstr*> &SpillPts = Virt2SpillPtsMap[virtReg];
-      for (unsigned i = 0, e = SpillPts.size(); i != e; ++i)
-        removeRegFromSpillPt(SpillPts[i], virtReg);
-      Virt2SpillPtsMap[virtReg].clear();
-    }
-
-    /// @brief remove the specified MachineInstr as a spill point for the
-    /// specified register.
-    void removeRegSpillPt(unsigned virtReg, MachineInstr *Pt) {
-      std::vector<MachineInstr*> &SpillPts = Virt2SpillPtsMap[virtReg];
-      if (SpillPts.back() == Pt) // Most common case.
-        SpillPts.pop_back();
-      for (unsigned i = 0, e = SpillPts.size(); i != e; ++i)
-        if (SpillPts[i] == Pt) {
-          SpillPts.erase(SpillPts.begin()+i-1);
-          break;
-        }
+      if (SpillPt2VirtMap.find(Pt) != SpillPt2VirtMap.end())
+        SpillPt2VirtMap[Pt].push_back(virtReg);
+      else {
+        std::vector<unsigned> Virts;
+        Virts.push_back(virtReg);
+        SpillPt2VirtMap.insert(std::make_pair(Pt, Virts));
+      }
     }
 
     void transferSpillPts(MachineInstr *Old, MachineInstr *New) {
-      std::vector<unsigned> &OldRegs = SpillPt2VirtMap[Old];
-      while (!OldRegs.empty()) {
-        unsigned virtReg = OldRegs.back();
-        OldRegs.pop_back();
-        removeRegSpillPt(virtReg, Old);
+      std::map<MachineInstr*,std::vector<unsigned> >::iterator I =
+        SpillPt2VirtMap.find(Old);
+      if (I == SpillPt2VirtMap.end())
+        return;
+      while (!I->second.empty()) {
+        unsigned virtReg = I->second.back();
+        I->second.pop_back();
         addSpillPoint(virtReg, New);
       }
+      SpillPt2VirtMap.erase(I);
     }
 
     /// @brief Updates information about the specified virtual register's value
@@ -282,10 +256,11 @@ namespace llvm {
       return MI2VirtMap.equal_range(MI);
     }
     
-    /// RemoveFromFoldedVirtMap - If the specified machine instruction is in
-    /// the folded instruction map, remove its entry from the map.
-    void RemoveFromFoldedVirtMap(MachineInstr *MI) {
+    /// RemoveMachineInstrFromMaps - MI is being erased, remove it from the
+    /// the folded instruction map and spill point map.
+    void RemoveMachineInstrFromMaps(MachineInstr *MI) {
       MI2VirtMap.erase(MI);
+      SpillPt2VirtMap.erase(MI);
     }
 
     void print(std::ostream &OS) const;