Use InterferenceCache in RegAllocGreedy.

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

1 files changed, 46 insertions, 94 deletions

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index e2cf71a650..e64deafc21 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -119,15 +119,15 @@ class RAGreedy : public MachineFunctionPass,
   std::auto_ptr<SplitAnalysis> SA;
   std::auto_ptr<SplitEditor> SE;
 
+  /// Cached per-block interference maps
+  InterferenceCache IntfCache;
+
   /// All basic blocks where the current register is live.
   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
 
-  typedef std::pair<SlotIndex, SlotIndex> IndexPair;
-
   /// Global live range splitting candidate info.
   struct GlobalSplitCandidate {
     unsigned PhysReg;
-    SmallVector<IndexPair, 8> Interference;
     BitVector LiveBundles;
   };
 
@@ -168,9 +168,7 @@ private:
   void LRE_WillShrinkVirtReg(unsigned);
   void LRE_DidCloneVirtReg(unsigned, unsigned);
 
-  void mapGlobalInterference(unsigned, SmallVectorImpl<IndexPair>&);
-  float calcSplitConstraints(const SmallVectorImpl<IndexPair>&);
-
+  float calcSplitConstraints(unsigned);
   float calcGlobalSplitCost(const BitVector&);
   void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
                          SmallVectorImpl<LiveInterval*>&);
@@ -407,96 +405,53 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
 //                              Region Splitting
 //===----------------------------------------------------------------------===//
 
-/// mapGlobalInterference - Compute a map of the interference from PhysReg and
-/// its aliases in each block in SA->LiveBlocks.
-/// If LiveBlocks[i] is live-in, Ranges[i].first is the first interference.
-/// If LiveBlocks[i] is live-out, Ranges[i].second is the last interference.
-void RAGreedy::mapGlobalInterference(unsigned PhysReg,
-                                     SmallVectorImpl<IndexPair> &Ranges) {
-  Ranges.assign(SA->LiveBlocks.size(), IndexPair());
-  LiveInterval &VirtReg = const_cast<LiveInterval&>(SA->getParent());
-  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
-    if (!query(VirtReg, *AI).checkInterference())
-      continue;
-    LiveIntervalUnion::SegmentIter IntI =
-      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
-    if (!IntI.valid())
-      continue;
-    for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
-      const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
-      IndexPair &IP = Ranges[i];
-
-      // Skip interference-free blocks.
-      if (IntI.start() >= BI.Stop)
-        continue;
-
-      // First interference in block.
-      if (BI.LiveIn) {
-        IntI.advanceTo(BI.Start);
-        if (!IntI.valid())
-          break;
-        if (IntI.start() >= BI.Stop)
-          continue;
-        if (!IP.first.isValid() || IntI.start() < IP.first)
-          IP.first = IntI.start();
-      }
-
-      // Last interference in block.
-      if (BI.LiveOut) {
-        IntI.advanceTo(BI.Stop);
-        if (!IntI.valid() || IntI.start() >= BI.Stop)
-          --IntI;
-        if (IntI.stop() <= BI.Start)
-          continue;
-        if (!IP.second.isValid() || IntI.stop() > IP.second)
-          IP.second = IntI.stop();
-      }
-    }
-  }
-}
-
 /// calcSplitConstraints - Fill out the SplitConstraints vector based on the
-/// interference pattern in Intf. Return the static cost of this split,
-/// assuming that all preferences in SplitConstraints are met.
-float RAGreedy::calcSplitConstraints(const SmallVectorImpl<IndexPair> &Intf) {
+/// interference pattern in Physreg and its aliases. Return the static cost of
+/// this split, assuming that all preferences in SplitConstraints are met.
+float RAGreedy::calcSplitConstraints(unsigned PhysReg) {
+  InterferenceCache::Cursor Intf(IntfCache, PhysReg);
+
   // Reset interference dependent info.
   SplitConstraints.resize(SA->LiveBlocks.size());
   float StaticCost = 0;
   for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
     SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
-    IndexPair IP = Intf[i];
 
     BC.Number = BI.MBB->getNumber();
+    Intf.moveToBlock(BC.Number);
     BC.Entry = (BI.Uses && BI.LiveIn) ?
       SpillPlacement::PrefReg : SpillPlacement::DontCare;
     BC.Exit = (BI.Uses && BI.LiveOut) ?
       SpillPlacement::PrefReg : SpillPlacement::DontCare;
 
+    if (!Intf.hasInterference())
+      continue;
+
     // Number of spill code instructions to insert.
     unsigned Ins = 0;
 
     // Interference for the live-in value.
-    if (IP.first.isValid()) {
-      if (IP.first <= BI.Start)
+    if (BI.LiveIn) {
+      if (Intf.first() <= BI.Start)
         BC.Entry = SpillPlacement::MustSpill, Ins += BI.Uses;
       else if (!BI.Uses)
         BC.Entry = SpillPlacement::PrefSpill;
-      else if (IP.first < BI.FirstUse)
+      else if (Intf.first() < BI.FirstUse)
         BC.Entry = SpillPlacement::PrefSpill, ++Ins;
-      else if (IP.first < (BI.LiveThrough ? BI.LastUse : BI.Kill))
+      else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
         ++Ins;
     }
 
     // Interference for the live-out value.
-    if (IP.second.isValid()) {
-      if (IP.second >= BI.LastSplitPoint)
+    if (BI.LiveOut) {
+      if (Intf.last() >= BI.LastSplitPoint)
         BC.Exit = SpillPlacement::MustSpill, Ins += BI.Uses;
       else if (!BI.Uses)
         BC.Exit = SpillPlacement::PrefSpill;
-      else if (IP.second > BI.LastUse)
+      else if (Intf.last() > BI.LastUse)
         BC.Exit = SpillPlacement::PrefSpill, ++Ins;
-      else if (IP.second > (BI.LiveThrough ? BI.FirstUse : BI.Def))
+      else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def))
         ++Ins;
     }
 
@@ -553,10 +508,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     dbgs() << ".\n";
   });
 
-  // First compute interference ranges in the live blocks.
-  SmallVector<IndexPair, 8> InterferenceRanges;
-  mapGlobalInterference(PhysReg, InterferenceRanges);
-
+  InterferenceCache::Cursor Intf(IntfCache, PhysReg);
   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
   SE->reset(LREdit);
 
@@ -573,20 +525,21 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     if (!BI.LiveOut || !RegOut)
       continue;
 
-    IndexPair &IP = InterferenceRanges[i];
+    Intf.moveToBlock(BI.MBB->getNumber());
     DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
                  << Bundles->getBundle(BI.MBB->getNumber(), 1)
                  << " [" << BI.Start << ';' << BI.LastSplitPoint << '-'
-                 << BI.Stop << ") intf [" << IP.first << ';' << IP.second
+                 << BI.Stop << ") intf [" << Intf.first() << ';' << Intf.last()
                  << ')');
 
     // The interference interval should either be invalid or overlap MBB.
-    assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference");
-    assert((!IP.second.isValid() || IP.second > BI.Start)
+    assert((!Intf.hasInterference() || Intf.first() < BI.Stop)
+           && "Bad interference");
+    assert((!Intf.hasInterference() || Intf.last() > BI.Start)
            && "Bad interference");
 
     // Check interference leaving the block.
-    if (!IP.second.isValid()) {
+    if (!Intf.hasInterference()) {
       // Block is interference-free.
       DEBUG(dbgs() << ", no interference");
       if (!BI.Uses) {
@@ -615,9 +568,9 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     }
 
     // Block has interference.
-    DEBUG(dbgs() << ", interference to " << IP.second);
+    DEBUG(dbgs() << ", interference to " << Intf.last());
 
-    if (!BI.LiveThrough && IP.second <= BI.Def) {
+    if (!BI.LiveThrough && Intf.last() <= BI.Def) {
       // The interference doesn't reach the outgoing segment.
       DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
       SE->useIntv(BI.Def, BI.Stop);
@@ -629,16 +582,16 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       // No uses in block, avoid interference by reloading as late as possible.
       DEBUG(dbgs() << ", no uses.\n");
       SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
-      assert(SegStart >= IP.second && "Couldn't avoid interference");
+      assert(SegStart >= Intf.last() && "Couldn't avoid interference");
       continue;
     }
 
-    if (IP.second.getBoundaryIndex() < BI.LastUse) {
+    if (Intf.last().getBoundaryIndex() < BI.LastUse) {
       // There are interference-free uses at the end of the block.
       // Find the first use that can get the live-out register.
       SmallVectorImpl<SlotIndex>::const_iterator UI =
         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
-                         IP.second.getBoundaryIndex());
+                         Intf.last().getBoundaryIndex());
       assert(UI != SA->UseSlots.end() && "Couldn't find last use");
       SlotIndex Use = *UI;
       assert(Use <= BI.LastUse && "Couldn't find last use");
@@ -646,7 +599,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       if (Use.getBaseIndex() <= BI.LastSplitPoint) {
         DEBUG(dbgs() << ", free use at " << Use << ".\n");
         SlotIndex SegStart = SE->enterIntvBefore(Use);
-        assert(SegStart >= IP.second && "Couldn't avoid interference");
+        assert(SegStart >= Intf.last() && "Couldn't avoid interference");
         assert(SegStart < BI.LastSplitPoint && "Impossible split point");
         SE->useIntv(SegStart, BI.Stop);
         continue;
@@ -656,7 +609,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     // Interference is after the last use.
     DEBUG(dbgs() << " after last use.\n");
     SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
-    assert(SegStart >= IP.second && "Couldn't avoid interference");
+    assert(SegStart >= Intf.last() && "Couldn't avoid interference");
   }
 
   // Now all defs leading to live bundles are handled, do everything else.
@@ -670,14 +623,13 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       continue;
 
     // We have an incoming register. Check for interference.
-    IndexPair &IP = InterferenceRanges[i];
-
+    Intf.moveToBlock(BI.MBB->getNumber());
     DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
                  << " -> BB#" << BI.MBB->getNumber() << " [" << BI.Start << ';'
                  << BI.LastSplitPoint << '-' << BI.Stop << ')');
 
     // Check interference entering the block.
-    if (!IP.first.isValid()) {
+    if (!Intf.hasInterference()) {
       // Block is interference-free.
       DEBUG(dbgs() << ", no interference");
       if (!BI.Uses) {
@@ -724,9 +676,9 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     }
 
     // Block has interference.
-    DEBUG(dbgs() << ", interference from " << IP.first);
+    DEBUG(dbgs() << ", interference from " << Intf.first());
 
-    if (!BI.LiveThrough && IP.first >= BI.Kill) {
+    if (!BI.LiveThrough && Intf.first() >= BI.Kill) {
       // The interference doesn't reach the outgoing segment.
       DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
       SE->useIntv(BI.Start, BI.Kill);
@@ -737,20 +689,20 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       // No uses in block, avoid interference by spilling as soon as possible.
       DEBUG(dbgs() << ", no uses.\n");
       SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
-      assert(SegEnd <= IP.first && "Couldn't avoid interference");
+      assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
       continue;
     }
-    if (IP.first.getBaseIndex() > BI.FirstUse) {
+    if (Intf.first().getBaseIndex() > BI.FirstUse) {
       // There are interference-free uses at the beginning of the block.
       // Find the last use that can get the register.
       SmallVectorImpl<SlotIndex>::const_iterator UI =
         std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
-                         IP.first.getBaseIndex());
+                         Intf.first().getBaseIndex());
       assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
       SlotIndex Use = (--UI)->getBoundaryIndex();
       DEBUG(dbgs() << ", free use at " << *UI << ".\n");
       SlotIndex SegEnd = SE->leaveIntvAfter(Use);
-      assert(SegEnd <= IP.first && "Couldn't avoid interference");
+      assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
       SE->useIntv(BI.Start, SegEnd);
       continue;
     }
@@ -758,7 +710,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     // Interference is before the first use.
     DEBUG(dbgs() << " before first use.\n");
     SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
-    assert(SegEnd <= IP.first && "Couldn't avoid interference");
+    assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
   }
 
   SE->closeIntv();
@@ -785,8 +737,7 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
       GlobalCand.resize(Cand+1);
     GlobalCand[Cand].PhysReg = PhysReg;
 
-    mapGlobalInterference(PhysReg, GlobalCand[Cand].Interference);
-    float Cost = calcSplitConstraints(GlobalCand[Cand].Interference);
+    float Cost = calcSplitConstraints(PhysReg);
     DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = " << Cost);
     if (BestReg && Cost >= BestCost) {
       DEBUG(dbgs() << " higher.\n");
@@ -1213,6 +1164,7 @@ bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
   SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
   LRStage.clear();
   LRStage.resize(MRI->getNumVirtRegs());
+  IntfCache.init(MF, &PhysReg2LiveUnion[0], Indexes, TRI);
 
   allocatePhysRegs();
   addMBBLiveIns(MF);