Two coalescer fixes in one.

1. Use the same value# to represent unknown values being merged into sub-registers.
2. When coalescer commute an instruction and the destination is a physical register, update its sub-registers by merging in the extended ranges.

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

diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 1e8202e5f4bfaed5c9c5f8ea08de64e27554b2c5..8e99ee7e29f2e822ae6bcf616cc5921337ba40e3 100644 (file)
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -212,6 +212,10 @@ namespace llvm {
       return VNI;
     }
 
+    /// getUnknownValNo - Find a value# for unknown values, if there isn't one
+    /// create a new one.
+    VNInfo *getUnknownValNo(BumpPtrAllocator &VNInfoAllocator);
+
     /// addKill - Add a kill instruction index to the specified value
     /// number.
     static void addKill(VNInfo *VNI, unsigned KillIdx) {
@@ -296,6 +300,11 @@ namespace llvm {
     void MergeInClobberRanges(const LiveInterval &Clobbers,
                               BumpPtrAllocator &VNInfoAllocator);
 
+    /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
+    /// single LiveRange only.
+    void MergeInClobberRange(unsigned Start, unsigned End,
+                             BumpPtrAllocator &VNInfoAllocator);
+
     /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
     /// in RHS into this live interval as the specified value number.
     /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 40f8cd4388d89bc65bc89358e06d8d74e4b481e0..75cd36dec2c43187ab67eee44ccfda6ff9f171ef 100644 (file)
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -551,6 +551,20 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
   }
 }
 
+VNInfo *LiveInterval::getUnknownValNo(BumpPtrAllocator &VNInfoAllocator) {
+  unsigned i = getNumValNums();
+  if (i) {
+    do {
+      --i;
+      VNInfo *VNI = getValNumInfo(i);
+      if (VNI->def == ~0U && !VNI->copy &&
+          !VNI->hasPHIKill && !VNI->redefByEC && VNI->kills.empty())
+        return VNI;
+    } while (i != 0);
+  }
+  return getNextValue(~0U, 0, VNInfoAllocator);
+}
+
 
 /// MergeInClobberRanges - For any live ranges that are not defined in the
 /// current interval, but are defined in the Clobbers interval, mark them
@@ -561,8 +575,7 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
   
   // Find a value # to use for the clobber ranges.  If there is already a value#
   // for unknown values, use it.
-  // FIXME: Use a single sentinal number for these!
-  VNInfo *ClobberValNo = getNextValue(~0U, 0, VNInfoAllocator);
+  VNInfo *ClobberValNo = getUnknownValNo(VNInfoAllocator);
   
   iterator IP = begin();
   for (const_iterator I = Clobbers.begin(), E = Clobbers.end(); I != E; ++I) {
@@ -587,6 +600,32 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
   }
 }
 
+void LiveInterval::MergeInClobberRange(unsigned Start, unsigned End,
+                                       BumpPtrAllocator &VNInfoAllocator) {
+  // Find a value # to use for the clobber ranges.  If there is already a value#
+  // for unknown values, use it.
+  VNInfo *ClobberValNo = getUnknownValNo(VNInfoAllocator);
+  
+  iterator IP = begin();
+  IP = std::upper_bound(IP, end(), Start);
+    
+  // If the start of this range overlaps with an existing liverange, trim it.
+  if (IP != begin() && IP[-1].end > Start) {
+    Start = IP[-1].end;
+    // Trimmed away the whole range?
+    if (Start >= End) return;
+  }
+  // If the end of this range overlaps with an existing liverange, trim it.
+  if (IP != end() && End > IP->start) {
+    End = IP->start;
+    // If this trimmed away the whole range, ignore it.
+    if (Start == End) return;
+  }
+    
+  // Insert the clobber interval.
+  addRangeFrom(LiveRange(Start, End, ClobberValNo), IP);
+}
+
 /// MergeValueNumberInto - This method is called when two value nubmers
 /// are found to be equivalent.  This eliminates V1, replacing all
 /// LiveRanges with the V1 value number with the V2 value number.  This can

diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 942d8d95cf993bf740c57efa96adf4bfa20a420c..c29ee62c83e36a3a12aca9c139b6c4ca348d3dc6 100644 (file)
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -193,13 +193,12 @@ bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
   IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));
 
   // If the IntB live range is assigned to a physical register, and if that
-  // physreg has aliases, 
+  // physreg has sub-registers, update their live intervals as well. 
   if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
-    // Update the liveintervals of sub-registers.
-    for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) {
-      LiveInterval &AliasLI = li_->getInterval(*AS);
-      AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
-              AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator())));
+    for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
+      LiveInterval &SRLI = li_->getInterval(*SR);
+      SRLI.addRange(LiveRange(FillerStart, FillerEnd,
+                 SRLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator())));
     }
   }
 
@@ -367,6 +366,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
     BExtend[ALR->end] = BLR->end;
 
   // Update uses of IntA of the specific Val# with IntB.
+  bool BHasSubRegs = false;
+  if (TargetRegisterInfo::isPhysicalRegister(IntB.reg))
+    BHasSubRegs = *tri_->getSubRegisters(IntB.reg);
   for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
          UE = mri_->use_end(); UI != UE;) {
     MachineOperand &UseMO = UI.getOperand();
@@ -398,6 +400,9 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
       const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
       BHasPHIKill |= DLR->valno->hasPHIKill;
       assert(DLR->valno->def == DefIdx);
+      if (BHasSubRegs)
+        // Don't know how to update sub-register live intervals.
+        return false;
       BDeadValNos.push_back(DLR->valno);
       BExtend[DLR->start] = DLR->end;
       JoinedCopies.insert(UseMI);
@@ -435,6 +440,15 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
     if (EI != BExtend.end())
       End = EI->second;
     IntB.addRange(LiveRange(AI->start, End, ValNo));
+
+    // If the IntB live range is assigned to a physical register, and if that
+    // physreg has sub-registers, update their live intervals as well. 
+    if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
+      for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) {
+        LiveInterval &SRLI = li_->getInterval(*SR);
+        SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator());
+      }
+    }
   }
   IntB.addKills(ValNo, BKills);
   ValNo->hasPHIKill = BHasPHIKill;

diff --git a/test/CodeGen/X86/2009-03-10-CoalescerBug.ll b/test/CodeGen/X86/2009-03-10-CoalescerBug.ll
new file mode 100644 (file)
index 0000000..3d979e9
--- /dev/null
+++ b/test/CodeGen/X86/2009-03-10-CoalescerBug.ll
@@ -0,0 +1,28 @@
+; RUN: llvm-as < %s | llc -mtriple=x86_64-apple-darwin
+; rdar://r6661945
+
+       %struct.WINDOW = type { i16, i16, i16, i16, i16, i16, i16, i32, i32, i8, i8, i8, i8, i8, i8, i8, i8, i8, i32, %struct.ldat*, i16, i16, i32, i32, %struct.WINDOW*, %struct.pdat, i16, %struct.cchar_t }
+       %struct.cchar_t = type { i32, [5 x i32] }
+       %struct.ldat = type { %struct.cchar_t*, i16, i16, i16 }
+       %struct.pdat = type { i16, i16, i16, i16, i16, i16 }
+
+define i32 @pnoutrefresh(%struct.WINDOW* %win, i32 %pminrow, i32 %pmincol, i32 %sminrow, i32 %smincol, i32 %smaxrow, i32 %smaxcol) nounwind optsize ssp {
+entry:
+       %0 = load i16* null, align 4            ; <i16> [#uses=2]
+       %1 = icmp sgt i16 0, %0         ; <i1> [#uses=1]
+       br i1 %1, label %bb12, label %bb13
+
+bb12:          ; preds = %entry
+       %2 = sext i16 %0 to i32         ; <i32> [#uses=1]
+       %3 = sub i32 %2, 0              ; <i32> [#uses=1]
+       %4 = add i32 %3, %smaxrow               ; <i32> [#uses=2]
+       %5 = trunc i32 %4 to i16                ; <i16> [#uses=1]
+       %6 = add i16 0, %5              ; <i16> [#uses=1]
+       br label %bb13
+
+bb13:          ; preds = %bb12, %entry
+       %pmaxrow.0 = phi i16 [ %6, %bb12 ], [ 0, %entry ]               ; <i16> [#uses=0]
+       %smaxrow_addr.0 = phi i32 [ %4, %bb12 ], [ %smaxrow, %entry ]           ; <i32> [#uses=1]
+       %7 = trunc i32 %smaxrow_addr.0 to i16           ; <i16> [#uses=0]
+       ret i32 0
+}