Gracefully handle invalid live ranges. Fix PR9831.

Register coalescing can sometimes create live ranges that end in the middle of a
basic block without any killing instruction. When SplitKit detects this, it will
repair the live range by shrinking it to its uses.

Live range splitting also needs to know about this. When the range shrinks so
much that it becomes allocatable, live range splitting fails because it can't
find a good split point. It is paranoid about making progress, so an allocatable
range is considered an error.

The coalescer should really not be creating these bad live ranges. They appear
when coalescing dead copies.

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

diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 7c461d8ea7874783da3d72359c5548dcb2544c1b..6feb45455d69f9b865e641a07050fdeb03eef275 100644 (file)
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -1315,6 +1315,19 @@ unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
 
   SA->analyze(&VirtReg);
 
+  // FIXME: SplitAnalysis may repair broken live ranges coming from the
+  // coalescer. That may cause the range to become allocatable which means that
+  // tryRegionSplit won't be making progress. This check should be replaced with
+  // an assertion when the coalescer is fixed.
+  if (SA->didRepairRange()) {
+    // VirtReg has changed, so all cached queries are invalid.
+    Order.rewind();
+    while (unsigned PhysReg = Order.next())
+      query(VirtReg, PhysReg).clear();
+    if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
+      return PhysReg;
+  }
+
   // First try to split around a region spanning multiple blocks.
   unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
   if (PhysReg || !NewVRegs.empty())

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index ac9d72bf62c9362875d4ffa166e8b5bf916b447b..feb3d3481b4f75ba20be728bcb765f2e089d78d6 100644 (file)
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -51,6 +51,7 @@ void SplitAnalysis::clear() {
   UseBlocks.clear();
   ThroughBlocks.clear();
   CurLI = 0;
+  DidRepairRange = false;
 }
 
 SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
@@ -119,6 +120,7 @@ void SplitAnalysis::analyzeUses() {
   if (!calcLiveBlockInfo()) {
     // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
     // I am looking at you, SimpleRegisterCoalescing!
+    DidRepairRange = true;
     DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
     const_cast<LiveIntervals&>(LIS)
       .shrinkToUses(const_cast<LiveInterval*>(CurLI));

diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 2ae760a58da5250f3e8668948358c17bae42b0b7..6305d0cc23502bfdda271843520c82165ea478cf 100644 (file)
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -97,6 +97,9 @@ private:
   /// NumThroughBlocks - Number of live-through blocks.
   unsigned NumThroughBlocks;
 
+  /// DidRepairRange - analyze was forced to shrinkToUses().
+  bool DidRepairRange;
+
   SlotIndex computeLastSplitPoint(unsigned Num);
 
   // Sumarize statistics by counting instructions using CurLI.
@@ -113,6 +116,11 @@ public:
   /// split.
   void analyze(const LiveInterval *li);
 
+  /// didRepairRange() - Returns true if CurLI was invalid and has been repaired
+  /// by analyze(). This really shouldn't happen, but sometimes the coalescer
+  /// can create live ranges that end in mid-air.
+  bool didRepairRange() const { return DidRepairRange; }
+
   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
   /// new interval.
   void clear();