Defer SplitKit value mapping until all defs are available.

The greedy register allocator revealed some problems with the value mapping in
SplitKit. We would sometimes start mapping values before all defs were known,
and that could change a value from a simple 1-1 mapping to a multi-def mapping
that requires ssa update.

The new approach collects all defs and register assignments first without
filling in any live intervals. Only when finish() is called, do we compute
liveness and mapped values. At this time we know with certainty which values map
to multiple values in a split range.

This also has the advantage that we can compute live ranges based on the
remaining uses after rematerializing at split points.

The current implementation has many opportunities for compile time optimization.

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

1 files changed, 3 insertions, 12 deletions

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 2b30c316f1..d970c7d16a 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -645,9 +645,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
   LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
   SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
 
-  // Ranges to add to the register interval after all defs are in place.
-  SmallVector<IndexPair, 8> UseRanges;
-
   // Create the main cross-block interval.
   SE.openIntv();
 
@@ -684,7 +681,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       if (!BI.LiveThrough) {
         DEBUG(dbgs() << ", not live-through.\n");
         SE.enterIntvBefore(BI.Def);
-        UseRanges.push_back(IndexPair(BI.Def, Stop));
+        SE.useIntv(BI.Def, Stop);
         continue;
       }
       if (!RegIn) {
@@ -692,7 +689,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
         // Reload just before the first use.
         DEBUG(dbgs() << ", not live-in, enter before first use.\n");
         SE.enterIntvBefore(BI.FirstUse);
-        UseRanges.push_back(IndexPair(BI.FirstUse, Stop));
+        SE.useIntv(BI.FirstUse, Stop);
         continue;
       }
       DEBUG(dbgs() << ", live-through.\n");
@@ -717,7 +714,7 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
       DEBUG(dbgs() << ", free use at " << Use << ".\n");
       assert(Use <= BI.LastUse && "Couldn't find last use");
       SE.enterIntvBefore(Use);
-      UseRanges.push_back(IndexPair(Use, Stop));
+      SE.useIntv(Use, Stop);
       continue;
     }
 
@@ -726,12 +723,6 @@ void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
     SE.enterIntvAtEnd(*BI.MBB);
   }
 
-  // Add the live-out ranges following the defs.
-  // We must wait until all defs have been inserted, otherwise SplitKit gets
-  // confused about the value mapping.
-  for (unsigned i = 0, e = UseRanges.size(); i != e; ++i)
-    SE.useIntv(UseRanges[i].first, UseRanges[i].second);
-
   // Now all defs leading to live bundles are handled, do everything else.
   for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
     BlockInfo &BI = LiveBlocks[i];