Rewrite code that propagate isDead information after a dead copy is coalesced. This remove some ugly spaghetti code and fixed a number of subtle bugs.

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

3 files changed, 182 insertions, 78 deletions

diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 92a4ebe..3c9078e 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -479,28 +479,143 @@ void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg,
   }
 }
 
-/// ShortenDeadCopyLiveRange - Shorten a live range as it's artificially
-/// extended by a dead copy. Mark the last use (if any) of the val# as kill
-/// as ends the live range there. If there isn't another use, then this
-/// live range is dead.
+/// removeRange - Wrapper for LiveInterval::removeRange. This removes a range
+/// from a physical register live interval as well as from the live intervals
+/// of its sub-registers.
+static void removeRange(LiveInterval &li, unsigned Start, unsigned End,
+                        LiveIntervals *li_, const TargetRegisterInfo *tri_) {
+  li.removeRange(Start, End, true);
+  if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
+    for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
+      if (!li_->hasInterval(*SR))
+        continue;
+      LiveInterval &sli = li_->getInterval(*SR);
+      unsigned RemoveEnd = Start;
+      while (RemoveEnd != End) {
+        LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start);
+        if (LR == sli.end())
+          break;
+        RemoveEnd = (LR->end < End) ? LR->end : End;
+        sli.removeRange(Start, RemoveEnd, true);
+        Start = RemoveEnd;
+      }
+    }
+  }
+}
+
+/// removeIntervalIfEmpty - Check if the live interval of a physical register
+/// is empty, if so remove it and also remove the empty intervals of its
+/// sub-registers.
+static void removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
+                                  const TargetRegisterInfo *tri_) {
+  if (li.empty()) {
+    li_->removeInterval(li.reg);
+    if (TargetRegisterInfo::isPhysicalRegister(li.reg))
+      for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
+        if (!li_->hasInterval(*SR))
+          continue;
+        LiveInterval &sli = li_->getInterval(*SR);
+        if (sli.empty())
+          li_->removeInterval(*SR);
+      }
+  }
+}
+
+/// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
+///
 void SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
                                                         MachineInstr *CopyMI) {
   unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
   LiveInterval::iterator MLR =
     li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
+  if (MLR == li.end())
+    return;  // Already removed by ShortenDeadCopySrcLiveRange.
   unsigned RemoveStart = MLR->start;
   unsigned RemoveEnd = MLR->end;
+  // Remove the liverange that's defined by this.
+  if (RemoveEnd == li_->getDefIndex(CopyIdx)+1) {
+    removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
+    removeIntervalIfEmpty(li, li_, tri_);
+  }
+}
+
+/// ShortenDeadCopyLiveRange - Shorten a live range as it's artificially
+/// extended by a dead copy. Mark the last use (if any) of the val# as kill
+/// as ends the live range there. If there isn't another use, then this
+/// live range is dead.
+void
+SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
+                                                      MachineInstr *CopyMI) {
+  unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
+  if (CopyIdx == 0) {
+    // FIXME: special case: function live in. It can be a general case if the
+    // first instruction index starts at > 0 value.
+    assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
+    // Live-in to the function but dead. Remove it from entry live-in set.
+    mf_->begin()->removeLiveIn(li.reg);
+    LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx);
+    removeRange(li, LR->start, LR->end, li_, tri_);
+    removeIntervalIfEmpty(li, li_, tri_);
+    return;
+  }
+
+  LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx-1);
+  if (LR == li.end())
+    // Livein but defined by a phi.
+    return;
+
+  unsigned RemoveStart = LR->start;
+  unsigned RemoveEnd = li_->getDefIndex(CopyIdx)+1;
+  if (LR->end > RemoveEnd)
+    // More uses past this copy? Nothing to do.
+    return;
+
   unsigned LastUseIdx;
-  MachineOperand *LastUse = lastRegisterUse(RemoveStart, CopyIdx, li.reg,
-                                            LastUseIdx);
+  MachineOperand *LastUse =
+    lastRegisterUse(LR->start, CopyIdx-1, li.reg, LastUseIdx);
   if (LastUse) {
-    // Shorten the liveinterval to the end of last use.
+    // There are uses before the copy, just shorten the live range to the end
+    // of last use.
     LastUse->setIsKill();
-    RemoveStart = li_->getDefIndex(LastUseIdx);
+    MachineInstr *LastUseMI = LastUse->getParent();
+    removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
+    unsigned SrcReg, DstReg;
+    if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg) &&
+        DstReg == li.reg) {
+      // Last use is itself an identity code.
+      int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_);
+      LastUseMI->getOperand(DeadIdx).setIsDead();
+    }
+    return;
   }
-  li.removeRange(RemoveStart, RemoveEnd, true);
-  if (li.empty())
-    li_->removeInterval(li.reg);
+
+  // Is it livein?
+  MachineBasicBlock *CopyMBB = CopyMI->getParent();
+  unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
+  if (LR->start <= MBBStart && LR->end > MBBStart) {
+    if (LR->start == 0) {
+      assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
+      // Live-in to the function but dead. Remove it from entry live-in set.
+      mf_->begin()->removeLiveIn(li.reg);
+    }
+    removeRange(li, LR->start, LR->end, li_, tri_);
+    // FIXME: Shorten intervals in BBs that reaches this BB.
+  } else {
+    // Not livein into BB.
+    MachineInstr *DefMI =
+      li_->getInstructionFromIndex(li_->getDefIndex(RemoveStart));
+    if (DefMI && DefMI != CopyMI) {
+      int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false, tri_);
+      if (DeadIdx != -1) {
+        DefMI->getOperand(DeadIdx).setIsDead();
+        // A dead def should have a single cycle interval.
+        ++RemoveStart;
+      }
+    }
+    removeRange(li, RemoveStart, LR->end, li_, tri_);
+  }
+
+  removeIntervalIfEmpty(li, li_, tri_);
 }
 
 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
@@ -638,48 +753,15 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
   DOUT << " and "; DstInt.print(DOUT, tri_);
   DOUT << ": ";
 
-  // Check if it is necessary to propagate "isDead" property before intervals
-  // are joined.
+  // Check if it is necessary to propagate "isDead" property.
   MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false);
   bool isDead = mopd->isDead();
-  bool isShorten = false;
-  unsigned SrcStart = 0, RemoveStart = 0;
-  unsigned SrcEnd = 0, RemoveEnd = 0;
-  if (isDead) {
-    unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
-    LiveInterval::iterator SrcLR =
-      SrcInt.FindLiveRangeContaining(li_->getUseIndex(CopyIdx));
-    RemoveStart = SrcStart = SrcLR->start;
-    RemoveEnd   = SrcEnd   = SrcLR->end;
-    if (SrcEnd > li_->getDefIndex(CopyIdx)) {
-      // If there are other uses of SrcReg beyond the copy, there is nothing to do.
-      isDead = false;
-    } else {
-      unsigned LastUseIdx;
-      MachineOperand *LastUse =
-        lastRegisterUse(SrcStart, CopyIdx, SrcReg, LastUseIdx);
-      if (LastUse) {
-        // There are uses before the copy, just shorten the live range to the end
-        // of last use.
-        LastUse->setIsKill();
-        isDead = false;
-        isShorten = true;
-        RemoveStart = li_->getDefIndex(LastUseIdx);
-      } else {
-        // This live range is truly dead. Remove it.
-        MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart);
-        if (SrcMI && SrcMI->modifiesRegister(SrcReg, tri_))
-          // A dead def should have a single cycle interval.
-          ++RemoveStart;
-      }
-    }
-  }
 
   // We need to be careful about coalescing a source physical register with a
   // virtual register. Once the coalescing is done, it cannot be broken and
   // these are not spillable! If the destination interval uses are far away,
   // think twice about coalescing them!
-  if (!mopd->isDead() && (SrcIsPhys || DstIsPhys) && !isExtSubReg) {
+  if (!isDead && (SrcIsPhys || DstIsPhys) && !isExtSubReg) {
     LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt;
     unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg;
     unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg;
@@ -708,31 +790,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
   // been modified, so we can use this information below to update aliases.
   bool Swapped = false;
-  if (JoinIntervals(DstInt, SrcInt, Swapped)) {
-    if (isDead) {
-      // Result of the copy is dead. Propagate this property.
-      if (SrcStart == 0) {
-        assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
-               "Live-in must be a physical register!");
-        // Live-in to the function but dead. Remove it from entry live-in set.
-        // JoinIntervals may end up swapping the two intervals.
-        mf_->begin()->removeLiveIn(SrcReg);
-      } else {
-        MachineInstr *SrcMI = li_->getInstructionFromIndex(SrcStart);
-        if (SrcMI) {
-          int DeadIdx = SrcMI->findRegisterDefOperandIdx(SrcReg, false, tri_);
-          if (DeadIdx != -1)
-            SrcMI->getOperand(DeadIdx).setIsDead();
-        }
-      }
-    }
-
-    if (isShorten || isDead) {
-      // Shorten the destination live interval.
-      if (Swapped)
-        SrcInt.removeRange(RemoveStart, RemoveEnd, true);
-    }
-  } else {
+  if (!JoinIntervals(DstInt, SrcInt, Swapped)) {
     // Coalescing failed.
     
     // If we can eliminate the copy without merging the live ranges, do so now.
@@ -1566,6 +1624,14 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
     // Delete all coalesced copies.
     for (SmallPtrSet<MachineInstr*,32>::iterator I = JoinedCopies.begin(),
            E = JoinedCopies.end(); I != E; ++I) {
+      MachineInstr *CopyMI = *I;
+      unsigned SrcReg, DstReg;
+      tii_->isMoveInstr(*CopyMI, SrcReg, DstReg);
+      if (CopyMI->registerDefIsDead(DstReg)) {
+        LiveInterval &li = li_->getInterval(DstReg);
+        ShortenDeadCopySrcLiveRange(li, CopyMI);
+        ShortenDeadCopyLiveRange(li, CopyMI);
+      }
       li_->RemoveMachineInstrFromMaps(*I);
       (*I)->eraseFromParent();
       ++numPeep;
@@ -1584,12 +1650,15 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
       // if the move will be an identity move delete it
       unsigned srcReg, dstReg;
       if (tii_->isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) {
-        // remove from def list
-        LiveInterval &RegInt = li_->getOrCreateInterval(srcReg);
-        // If def of this move instruction is dead, remove its live range from
-        // the dstination register's live interval.
-        if (mii->registerDefIsDead(dstReg))
-          ShortenDeadCopyLiveRange(RegInt, mii);
+        if (li_->hasInterval(srcReg)) {
+          LiveInterval &RegInt = li_->getInterval(srcReg);
+          // If def of this move instruction is dead, remove its live range
+          // from the dstination register's live interval.
+          if (mii->registerDefIsDead(dstReg)) {
+            ShortenDeadCopySrcLiveRange(RegInt, mii);
+            ShortenDeadCopyLiveRange(RegInt, mii);
+          }
+        }
         li_->RemoveMachineInstrFromMaps(mii);
         mii = mbbi->erase(mii);
         ++numPeep;
diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h
index cf204a5..cfac126 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.h
+++ b/lib/CodeGen/SimpleRegisterCoalescing.h
@@ -205,11 +205,15 @@ namespace llvm {
     /// due to live range lengthening as the result of coalescing.
     void RemoveUnnecessaryKills(unsigned Reg, LiveInterval &LI);
 
+    /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
+    ///
+    void ShortenDeadCopyLiveRange(LiveInterval &li, MachineInstr *CopyMI);
+
     /// ShortenDeadCopyLiveRange - Shorten a live range as it's artificially
     /// extended by a dead copy. Mark the last use (if any) of the val# as kill
     /// as ends the live range there. If there isn't another use, then this
     /// live range is dead.
-    void ShortenDeadCopyLiveRange(LiveInterval &li, MachineInstr *CopyMI);
+    void ShortenDeadCopySrcLiveRange(LiveInterval &li, MachineInstr *CopyMI);
 
     /// lastRegisterUse - Returns the last use of the specific register between
     /// cycles Start and End or NULL if there are no uses.
diff --git a/test/CodeGen/PowerPC/2008-03-17-RegScavengerCrash.ll b/test/CodeGen/PowerPC/2008-03-17-RegScavengerCrash.ll
new file mode 100644
index 0000000..eaeccc5
--- /dev/null
+++ b/test/CodeGen/PowerPC/2008-03-17-RegScavengerCrash.ll
@@ -0,0 +1,31 @@
+; RUN: llvm-as < %s | llc -march=ppc32 -enable-ppc32-regscavenger
+
+	%struct._cpp_strbuf = type { i8*, i32, i32 }
+	%struct.cpp_string = type { i32, i8* }
+
+declare fastcc void @emit_numeric_escape(i32, i32, %struct._cpp_strbuf*, i32) nounwind 
+
+define i32 @cpp_interpret_string(i32 %pfile, %struct.cpp_string* %from, i32 %wide) nounwind  {
+entry:
+	%tmp61 = load i32* null, align 4		; <i32> [#uses=1]
+	%toBool = icmp eq i32 %wide, 0		; <i1> [#uses=2]
+	%iftmp.87.0 = select i1 %toBool, i32 %tmp61, i32 0		; <i32> [#uses=2]
+	%tmp69 = icmp ult i32 %iftmp.87.0, 33		; <i1> [#uses=1]
+	%min = select i1 %tmp69, i32 %iftmp.87.0, i32 32		; <i32> [#uses=1]
+	%tmp71 = icmp ugt i32 %min, 31		; <i1> [#uses=1]
+	br i1 %tmp71, label %bb79, label %bb75
+bb75:		; preds = %entry
+	ret i32 0
+bb79:		; preds = %entry
+	br i1 %toBool, label %bb103, label %bb94
+bb94:		; preds = %bb79
+	br i1 false, label %bb729, label %bb130.preheader
+bb103:		; preds = %bb79
+	ret i32 0
+bb130.preheader:		; preds = %bb94
+	%tmp134 = getelementptr %struct.cpp_string* %from, i32 0, i32 1		; <i8**> [#uses=0]
+	ret i32 0
+bb729:		; preds = %bb94
+	call fastcc void @emit_numeric_escape( i32 %pfile, i32 0, %struct._cpp_strbuf* null, i32 %wide ) nounwind 
+	ret i32 1
+}