Add a case to LiveIntervalAnalysis::HandleMove

Some target like R600 may want to swap LiveRange order for a same register.
Subregister writes are independant and can be reorder to improve scheduling.
This patch allows LiveIntervals to support moving intervals accross some others.

1 files changed, 65 insertions, 4 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 22b35d5271..f85a1b2770 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -787,6 +787,18 @@ private:
     LI.verify();
   }
 
+  /// Split the Range interval = [a, b) in two at SplitPos.
+  /// Range becomes [a, SplitPos) and its (overwritten) successor is
+  /// [SplitPos, b), the value of the later being DefVNI.
+  ///
+  void splitRange(LiveRange *Range, SlotIndex SplitPos, VNInfo *DefVNI) {
+    assert(Range->contains(SplitPos) && "SplitPos not inside Range");
+    SlotIndex RangeEnd = Range->end;
+    Range->end = SplitPos;
+    // Finally we insert a new range
+    *llvm::next(Range) = LiveRange(SplitPos, RangeEnd, DefVNI);
+  }
+
   /// Update LI to reflect an instruction has been moved downwards from OldIdx
   /// to NewIdx.
   ///
@@ -807,6 +819,11 @@ private:
   /// 5. Value read at OldIdx, killed before NewIdx:
   ///    Extend kill to NewIdx.
   ///
+  /// 6. Live def at OldIdx AND several other values between NewIdx and OldIdx
+  ///    Extend the range that precedes OldIdx one and split the range that
+  ///    contains NewIdx.
+  ///    (Happens when reordering independant partial write to a register)
+  ///
   void handleMoveDown(LiveInterval &LI) {
     // First look for a kill at OldIdx.
     LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
@@ -821,6 +838,12 @@ private:
       // If the live-in value already extends to NewIdx, there is nothing to do.
       if (!SlotIndex::isEarlierInstr(I->end, NewIdx))
         return;
+      // If value is used at OldIdx and is moved to another interval, it's a
+      // consequence of subreg write reordering, do not go further
+      if (llvm::next(I) != E &&
+          !SlotIndex::isSameInstr(OldIdx, llvm::next(I)->start) &&
+          SlotIndex::isEarlierInstr(llvm::next(I)->start, NewIdx))
+        return;
       // Aggressively remove all kill flags from the old kill point.
       // Kill flags shouldn't be used while live intervals exist, they will be
       // reinserted by VirtRegRewriter.
@@ -853,11 +876,26 @@ private:
     // The remaining possibilities are now:
     // 2. Live def at OldIdx, killed at NewIdx: isSameInstr(I->end, NewIdx).
     // 3. Dead def at OldIdx: I->end = OldIdx.getDeadSlot().
+    // 6. Live def at OldIdx moving accross several others values
     // In either case, it is possible that there is an existing def at NewIdx.
-    assert((I->end == OldIdx.getDeadSlot() ||
-            SlotIndex::isSameInstr(I->end, NewIdx)) &&
-            "Cannot move def below kill");
     LiveInterval::iterator NewI = LI.advanceTo(I, NewIdx.getRegSlot());
+    if (!SlotIndex::isSameInstr(I->start, I->end) &&
+        SlotIndex::isEarlierInstr(I->end, NewIdx)) {
+      // OldIdx is not a dead def, and NewIdx is inside a new interval.
+      // Case 6 above.
+      if (I != LI.begin() &&
+          !SlotIndex::isEarlierInstr(llvm::prior(I)->end, I->start)) {
+        // There is no gap between I and its predecessor, merge them
+        // (We may fix the extension of the predecessor made in the live in
+        // case)
+        llvm::prior(I)->end = I->end;
+      }
+      std::copy(llvm::next(I), llvm::next(NewI), I);
+      splitRange(llvm::prior(NewI), DefVNI->def, DefVNI);
+      return;
+    }
+
+
     if (NewI != E && SlotIndex::isSameInstr(NewI->start, NewIdx)) {
       // There is an existing def at NewIdx, case 4 above. The def at OldIdx is
       // coalesced into that value.
@@ -894,6 +932,11 @@ private:
   ///    Hoist kill to NewIdx, then scan for last kill between NewIdx and
   ///    OldIdx.
   ///
+  /// 6. Live def at OldIdx AND several other values between NewIdx and OldIdx
+  ///    Extend the range that precedes OldIdx one and split the range that
+  ///    contains NewIdx.
+  ///    (Happens when reordering independant partial write to a register)
+  ///
   void handleMoveUp(LiveInterval &LI) {
     // First look for a kill at OldIdx.
     LiveInterval::iterator I = LI.find(OldIdx.getBaseIndex());
@@ -909,7 +952,9 @@ private:
         return;
       // Adjust I->end to end at NewIdx. If we are hoisting a kill above
       // another use, we need to search for that use. Case 5 above.
-      I->end = NewIdx.getRegSlot(I->end.isEarlyClobber());
+      SlotIndex NewEnd = NewIdx.getRegSlot(I->end.isEarlyClobber());;
+      if (llvm::next(I) == E || SlotIndex::isEarlierInstr(NewEnd, llvm::next(I)->start))
+        I->end = NewEnd;
       ++I;
       // If OldIdx also defines a value, there couldn't have been another use.
       if (I == E || !SlotIndex::isSameInstr(I->start, OldIdx)) {
@@ -942,6 +987,22 @@ private:
       return;
     }
 
+    if (!SlotIndex::isSameInstr(I->start, I->end) && I != LI.begin() &&
+        SlotIndex::isEarlierInstr(NewIdx, llvm::prior(I)->start)) {
+        // Case 6:
+        // OldIdx is not a dead def and NewIdx is before predecessor start
+        // First we extand range prior to I
+      LiveInterval::iterator NewI = LI.find(NewIdx.getRegSlot(true));
+      llvm::prior(I)->end = I->end;
+      std::copy_backward(NewI, I, llvm::next(I));
+      if (SlotIndex::isEarlierInstr(NewI->start, NewIdx)) {
+        splitRange(NewI, DefVNI->def, DefVNI);
+      } else {
+        *NewI = LiveRange(DefVNI->def, llvm::next(NewI)->start, DefVNI);
+      }
+      return;
+    }
+
     // There is no existing def at NewIdx. Hoist DefVNI.
     if (!I->end.isDead()) {
       // Leave the end point of a live def.