Add an interface for SplitKit complement spill modes.

SplitKit always computes a complement live range to cover the places
where the original live range was live, but no explicit region has been
allocated.

Currently, the complement live range is created to be as small as
possible - it never overlaps any of the regions.  This minimizes
register pressure, but if the complement is going to be spilled anyway,
that is not very important.  The spiller will eliminate redundant
spills, and hoist others by making the spill slot live range overlap
some of the regions created by splitting.  Stack slots are cheap.

This patch adds the interface to enable spill modes in SplitKit.  In
spill mode, SplitKit will assume that the complement is going to spill,
so it will allow it to overlap regions in order to avoid back-copies.
By doing some of the spiller's work early, the complement live range
becomes simpler.  In some cases, it can become much simpler because no
extra PHI-defs are required.  This will speed up both splitting and
spilling.

This is only the interface to enable spill modes, no implementation yet.

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

3 files changed, 49 insertions, 5 deletions

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 4275851..474594e 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -53,6 +53,15 @@ STATISTIC(NumEvicted,      "Number of interferences evicted");
 
 static cl::opt<bool> CompactRegions("compact-regions", cl::init(true));
 
+static cl::opt<SplitEditor::ComplementSpillMode>
+SplitSpillMode("split-spill-mode", cl::Hidden,
+  cl::desc("Spill mode for splitting live ranges"),
+  cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
+             clEnumValN(SplitEditor::SM_Size,  "size",  "Optimize for size"),
+             clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"),
+             clEnumValEnd),
+  cl::init(SplitEditor::SM_Partition));
+
 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
                                        createGreedyRegisterAllocator);
 
@@ -1166,7 +1175,7 @@ unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 
   // Prepare split editor.
   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
-  SE->reset(LREdit);
+  SE->reset(LREdit, SplitSpillMode);
 
   // Assign all edge bundles to the preferred candidate, or NoCand.
   BundleCand.assign(Bundles->getNumBundles(), NoCand);
@@ -1214,7 +1223,7 @@ unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
   unsigned Reg = VirtReg.reg;
   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
   LiveRangeEdit LREdit(VirtReg, NewVRegs, this);
-  SE->reset(LREdit);
+  SE->reset(LREdit, SplitSpillMode);
   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index fe17e93..67a722e 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -309,11 +309,13 @@ SplitEditor::SplitEditor(SplitAnalysis &sa,
     TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
     Edit(0),
     OpenIdx(0),
+    SpillMode(SM_Partition),
     RegAssign(Allocator)
 {}
 
-void SplitEditor::reset(LiveRangeEdit &lre) {
-  Edit = &lre;
+void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
+  Edit = &LRE;
+  SpillMode = SM;
   OpenIdx = 0;
   RegAssign.clear();
   Values.clear();
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index becd22c..7f74d3a 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -217,6 +217,36 @@ class SplitEditor {
   const TargetInstrInfo &TII;
   const TargetRegisterInfo &TRI;
 
+public:
+
+  /// ComplementSpillMode - Select how the complement live range should be
+  /// created.  SplitEditor automatically creates interval 0 to contain
+  /// anything that isn't added to another interval.  This complement interval
+  /// can get quite complicated, and it can sometimes be an advantage to allow
+  /// it to overlap the other intervals.  If it is going to spill anyway, no
+  /// registers are wasted by keeping a value in two places at the same time.
+  enum ComplementSpillMode {
+    /// SM_Partition(Default) - Try to create the complement interval so it
+    /// doesn't overlap any other intervals, and the original interval is
+    /// partitioned.  This may require a large number of back copies and extra
+    /// PHI-defs.  Only segments marked with overlapIntv will be overlapping.
+    SM_Partition,
+
+    /// SM_Size - Overlap intervals to minimize the number of inserted COPY
+    /// instructions.  Copies to the complement interval are hoisted to their
+    /// common dominator, so only one COPY is required per value in the
+    /// complement interval.  This also means that no extra PHI-defs need to be
+    /// inserted in the complement interval.
+    SM_Size,
+
+    /// SM_Speed - Overlap intervals to minimize the expected execution
+    /// frequency of the inserted copies.  This is very similar to SM_Size, but
+    /// the complement interval may get some extra PHI-defs.
+    SM_Speed
+  };
+
+private:
+
   /// Edit - The current parent register and new intervals created.
   LiveRangeEdit *Edit;
 
@@ -225,6 +255,9 @@ class SplitEditor {
   /// openIntv will be 1.
   unsigned OpenIdx;
 
+  /// The current spill mode, selected by reset().
+  ComplementSpillMode SpillMode;
+
   typedef IntervalMap<SlotIndex, unsigned> RegAssignMap;
 
   /// Allocator for the interval map. This will eventually be shared with
@@ -354,7 +387,7 @@ public:
               MachineDominatorTree&);
 
   /// reset - Prepare for a new split.
-  void reset(LiveRangeEdit&);
+  void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
 
   /// Create a new virtual register and live interval.
   /// Return the interval index, starting from 1. Interval index 0 is the