Analyze blocks with uses separately from live-through blocks without uses.

About 90% of the relevant blocks are live-through without uses, and the only
information required about them is their number. This saves memory and enables
later optimizations that need to look at only the use-blocks.

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

3 files changed, 120 insertions, 89 deletions

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 45ed70737e..689e5c9066 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -414,20 +414,19 @@ unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
 /// this split, assuming that all preferences in SplitConstraints are met.
 float RAGreedy::calcSplitConstraints(unsigned PhysReg) {
   InterferenceCache::Cursor Intf(IntfCache, PhysReg);
+  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
 
   // Reset interference dependent info.
-  SplitConstraints.resize(SA->LiveBlocks.size());
+  SplitConstraints.resize(UseBlocks.size());
   float StaticCost = 0;
-  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
-    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
+  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
+    const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
     SpillPlacement::BlockConstraint &BC = SplitConstraints[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;
+    BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
+    BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
 
     if (!Intf.hasInterference())
       continue;
@@ -438,9 +437,7 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) {
     // Interference for the live-in value.
     if (BI.LiveIn) {
       if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
-        BC.Entry = SpillPlacement::MustSpill, Ins += BI.Uses;
-      else if (!BI.Uses)
-        BC.Entry = SpillPlacement::PrefSpill;
+        BC.Entry = SpillPlacement::MustSpill, ++Ins;
       else if (Intf.first() < BI.FirstUse)
         BC.Entry = SpillPlacement::PrefSpill, ++Ins;
       else if (Intf.first() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
@@ -450,9 +447,7 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) {
     // Interference for the live-out value.
     if (BI.LiveOut) {
       if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
-        BC.Exit = SpillPlacement::MustSpill, Ins += BI.Uses;
-      else if (!BI.Uses)
-        BC.Exit = SpillPlacement::PrefSpill;
+        BC.Exit = SpillPlacement::MustSpill, ++Ins;
       else if (Intf.last() > BI.LastUse)
         BC.Exit = SpillPlacement::PrefSpill, ++Ins;
       else if (Intf.last() > (BI.LiveThrough ? BI.FirstUse : BI.Def))
@@ -463,6 +458,33 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) {
     if (Ins)
       StaticCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
   }
+
+  // Now handle the live-through blocks without uses.
+  ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks();
+  SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size());
+  for (unsigned i = 0; i != ThroughBlocks.size(); ++i) {
+    SpillPlacement::BlockConstraint BC = SplitConstraints[UseBlocks.size() + i];
+    BC.Number = ThroughBlocks[i];
+    BC.Entry = SpillPlacement::DontCare;
+    BC.Exit = SpillPlacement::DontCare;
+
+    Intf.moveToBlock(BC.Number);
+    if (!Intf.hasInterference())
+      continue;
+
+    // Interference for the live-in value.
+    if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
+      BC.Entry = SpillPlacement::MustSpill;
+    else
+      BC.Entry = SpillPlacement::PrefSpill;
+
+    // Interference for the live-out value.
+    if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
+      BC.Exit = SpillPlacement::MustSpill;
+    else
+      BC.Exit = SpillPlacement::PrefSpill;
+  }
+
   return StaticCost;
 }
 
@@ -473,24 +495,31 @@ float RAGreedy::calcSplitConstraints(unsigned PhysReg) {
 ///
 float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
   float GlobalCost = 0;
-  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
-    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
+  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
+  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
+    const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
     bool RegIn  = LiveBundles[Bundles->getBundle(BC.Number, 0)];
     bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
     unsigned Ins = 0;
 
-    if (!BI.Uses)
-      Ins += RegIn != RegOut;
-    else {
-      if (BI.LiveIn)
-        Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
-      if (BI.LiveOut)
-        Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
-    }
+    if (BI.LiveIn)
+      Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
+    if (BI.LiveOut)
+      Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
     if (Ins)
       GlobalCost += Ins * SpillPlacer->getBlockFrequency(BC.Number);
   }
+
+  ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks();
+  SplitConstraints.resize(UseBlocks.size() + ThroughBlocks.size());
+  for (unsigned i = 0; i != ThroughBlocks.size(); ++i) {
+    unsigned Number = ThroughBlocks[i];
+    bool RegIn  = LiveBundles[Bundles->getBundle(Number, 0)];
+    bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
+    if (RegIn != RegOut)
+      GlobalCost += SpillPlacer->getBlockFrequency(Number);
+  }
   return GlobalCost;
 }
 
@@ -520,8 +549,9 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
   SE->openIntv();
 
   // First add all defs that are live out of a block.
-  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
-    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
+  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
+  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
+    const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 
@@ -548,15 +578,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     if (!Intf.hasInterference()) {
       // Block is interference-free.
       DEBUG(dbgs() << ", no interference");
-      if (!BI.Uses) {
-        assert(BI.LiveThrough && "No uses, but not live through block?");
-        // Block is live-through without interference.
-        DEBUG(dbgs() << ", no uses"
-                     << (RegIn ? ", live-through.\n" : ", stack in.\n"));
-        if (!RegIn)
-          SE->enterIntvAtEnd(*BI.MBB);
-        continue;
-      }
       if (!BI.LiveThrough) {
         DEBUG(dbgs() << ", not live-through.\n");
         SE->useIntv(SE->enterIntvBefore(BI.Def), Stop);
@@ -583,15 +604,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       continue;
     }
 
-
-    if (!BI.Uses) {
-      // 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 >= Intf.last() && "Couldn't avoid interference");
-      continue;
-    }
-
     SlotIndex LastSplitPoint = SA->getLastSplitPoint(BI.MBB->getNumber());
     if (Intf.last().getBoundaryIndex() < BI.LastUse) {
       // There are interference-free uses at the end of the block.
@@ -620,8 +632,8 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
   }
 
   // Now all defs leading to live bundles are handled, do everything else.
-  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
-    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
+  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
+    const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
     bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
     bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
 
@@ -642,18 +654,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     if (!Intf.hasInterference()) {
       // Block is interference-free.
       DEBUG(dbgs() << ", no interference");
-      if (!BI.Uses) {
-        assert(BI.LiveThrough && "No uses, but not live through block?");
-        // Block is live-through without interference.
-        if (RegOut) {
-          DEBUG(dbgs() << ", no uses, live-through.\n");
-          SE->useIntv(Start, Stop);
-        } else {
-          DEBUG(dbgs() << ", no uses, stack-out.\n");
-          SE->leaveIntvAtTop(*BI.MBB);
-        }
-        continue;
-      }
       if (!BI.LiveThrough) {
         DEBUG(dbgs() << ", killed in block.\n");
         SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill));
@@ -696,13 +696,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       continue;
     }
 
-    if (!BI.Uses) {
-      // 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 <= Intf.first() && "Couldn't avoid interference");
-      continue;
-    }
     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.
@@ -724,6 +717,28 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     assert(SegEnd <= Intf.first() && "Couldn't avoid interference");
   }
 
+  // Handle live-through blocks.
+  ArrayRef<unsigned> ThroughBlocks = SA->getThroughBlocks();
+  for (unsigned i = 0; i != ThroughBlocks.size(); ++i) {
+    unsigned Number = ThroughBlocks[i];
+    bool RegIn  = LiveBundles[Bundles->getBundle(Number, 0)];
+    bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
+    DEBUG(dbgs() << "Live through BB#" << Number << '\n');
+    if (RegIn && RegOut) {
+      Intf.moveToBlock(Number);
+      if (!Intf.hasInterference()) {
+        SE->useIntv(Indexes->getMBBStartIdx(Number),
+                    Indexes->getMBBEndIdx(Number));
+        continue;
+      }
+    }
+    MachineBasicBlock *MBB = MF->getBlockNumbered(Number);
+    if (RegIn)
+      SE->leaveIntvAtTop(*MBB);
+    if (RegOut)
+      SE->enterIntvAtEnd(*MBB);
+  }
+
   SE->closeIntv();
 
   // FIXME: Should we be more aggressive about splitting the stack region into
@@ -797,8 +812,8 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 ///
 void RAGreedy::calcGapWeights(unsigned PhysReg,
                               SmallVectorImpl<float> &GapWeight) {
-  assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
-  const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
+  assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
+  const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
   const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
   const unsigned NumGaps = Uses.size()-1;
 
@@ -889,8 +904,8 @@ unsigned RAGreedy::nextSplitPoint(unsigned i) {
 ///
 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
-  assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
-  const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
+  assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
+  const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
 
   // Note that it is possible to have an interval that is live-in or live-out
   // while only covering a single block - A phi-def can use undef values from
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index 238b5668ef..201e9b16cb 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -48,7 +48,8 @@ SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
 
 void SplitAnalysis::clear() {
   UseSlots.clear();
-  LiveBlocks.clear();
+  UseBlocks.clear();
+  ThroughBlocks.clear();
   CurLI = 0;
 }
 
@@ -121,15 +122,17 @@ void SplitAnalysis::analyzeUses() {
     DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
     const_cast<LiveIntervals&>(LIS)
       .shrinkToUses(const_cast<LiveInterval*>(CurLI));
-    LiveBlocks.clear();
+    UseBlocks.clear();
+    ThroughBlocks.clear();
     bool fixed = calcLiveBlockInfo();
     (void)fixed;
     assert(fixed && "Couldn't fix broken live interval");
   }
 
   DEBUG(dbgs() << "Analyze counted "
-               << UseSlots.size() << " instrs, "
-               << LiveBlocks.size() << " spanned.\n");
+               << UseSlots.size() << " instrs in "
+               << UseBlocks.size() << " blocks, through "
+               << ThroughBlocks.size() << " blocks.\n");
 }
 
 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
@@ -159,8 +162,8 @@ bool SplitAnalysis::calcLiveBlockInfo() {
       BI.Def = LVI->start;
 
     // Find the first and last uses in the block.
-    BI.Uses = UseI != UseE && *UseI < Stop;
-    if (BI.Uses) {
+    bool Uses = UseI != UseE && *UseI < Stop;
+    if (Uses) {
       BI.FirstUse = *UseI;
       assert(BI.FirstUse >= Start);
       do ++UseI;
@@ -188,11 +191,14 @@ bool SplitAnalysis::calcLiveBlockInfo() {
 
     // Don't set LiveThrough when the block has a gap.
     BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
-    LiveBlocks.push_back(BI);
+    if (Uses)
+      UseBlocks.push_back(BI);
+    else
+      ThroughBlocks.push_back(BI.MBB->getNumber());
 
     // FIXME: This should never happen. The live range stops or starts without a
     // corresponding use. An earlier pass did something wrong.
-    if (!BI.LiveThrough && !BI.Uses)
+    if (!BI.LiveThrough && !Uses)
       return false;
 
     // LVI is now at LVE or LVI->end >= Stop.
@@ -907,12 +913,12 @@ void SplitEditor::finish() {
 /// may be an advantage to split CurLI for the duration of the block.
 bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
   // If CurLI is local to one block, there is no point to splitting it.
-  if (LiveBlocks.size() <= 1)
+  if (UseBlocks.size() <= 1)
     return false;
   // Add blocks with multiple uses.
-  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
-    const BlockInfo &BI = LiveBlocks[i];
-    if (!BI.Uses || BI.FirstUse == BI.LastUse)
+  for (unsigned i = 0, e = UseBlocks.size(); i != e; ++i) {
+    const BlockInfo &BI = UseBlocks[i];
+    if (BI.FirstUse == BI.LastUse)
       continue;
     Blocks.insert(BI.MBB);
   }
@@ -923,10 +929,10 @@ bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
 /// basic block in Blocks.
 void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
   DEBUG(dbgs() << "  splitSingleBlocks for " << Blocks.size() << " blocks.\n");
-
-  for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
-    const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
-    if (!BI.Uses || !Blocks.count(BI.MBB))
+  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA.getUseBlocks();
+  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
+    const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
+    if (!Blocks.count(BI.MBB))
       continue;
 
     openIntv();
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 793989f7e3..20ac8a1fdc 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -12,6 +12,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/IndexedMap.h"
@@ -69,16 +70,11 @@ public:
     SlotIndex LastUse;    ///< Last instr using current reg.
     SlotIndex Kill;       ///< Interval end point inside block.
     SlotIndex Def;        ///< Interval start point inside block.
-    bool Uses;            ///< Current reg has uses or defs in block.
     bool LiveThrough;     ///< Live in whole block (Templ 5. or 6. above).
     bool LiveIn;          ///< Current reg is live in.
     bool LiveOut;         ///< Current reg is live out.
   };
 
-  /// Basic blocks where var is live. This array is parallel to
-  /// SpillConstraints.
-  SmallVector<BlockInfo, 8> LiveBlocks;
-
 private:
   // Current live interval.
   const LiveInterval *CurLI;
@@ -89,6 +85,12 @@ private:
   /// successor.
   SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint;
 
+  /// UseBlocks - Blocks where CurLI has uses.
+  SmallVector<BlockInfo, 8> UseBlocks;
+
+  /// ThroughBlocks - Block numbers where CurLI is live through without uses.
+  SmallVector<unsigned, 8> ThroughBlocks;
+
   SlotIndex computeLastSplitPoint(unsigned Num);
 
   // Sumarize statistics by counting instructions using CurLI.
@@ -129,6 +131,14 @@ public:
   /// splitting.
   bool isOriginalEndpoint(SlotIndex Idx) const;
 
+  /// getUseBlocks - Return an array of BlockInfo objects for the basic blocks
+  /// where CurLI has uses.
+  ArrayRef<BlockInfo> getUseBlocks() { return UseBlocks; }
+
+  /// getThroughBlocks - Return an array of block numbers where CurLI is live
+  /// through without uses.
+  ArrayRef<unsigned> getThroughBlocks() { return ThroughBlocks; }
+
   typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
 
   /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from