Implement PR3495: local spiller optimization. The local spiller can now keep availabi...

[oota-llvm.git] / lib / CodeGen / SimpleRegisterCoalescing.cpp

diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 75389a412a0f712dc931b388cd09a5ee0597baeb..e5286c21cebcbf6666fcc3373280a262a8d9034c 100644 (file)
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -489,7 +489,7 @@ static void removeRange(LiveInterval &li, unsigned Start, unsigned End,
 }
 
 /// TrimLiveIntervalToLastUse - If there is a last use in the same basic block
-/// as the copy instruction, trim the ive interval to the last use and return
+/// as the copy instruction, trim the live interval to the last use and return
 /// true.
 bool
 SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx,
@@ -861,20 +861,29 @@ SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
 
   // If there is a last use in the same bb, we can't remove the live range.
   // Shorten the live interval and return.
-  if (TrimLiveIntervalToLastUse(CopyIdx, CopyMI->getParent(), li, LR))
+  MachineBasicBlock *CopyMBB = CopyMI->getParent();
+  if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR))
     return false;
 
+  MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart);
+  if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_))
+    // If the live range starts in another mbb and the copy mbb is not a fall
+    // through mbb, then we can only cut the range from the beginning of the
+    // copy mbb.
+    RemoveStart = li_->getMBBStartIdx(CopyMBB) + 1;
+
   if (LR->valno->def == RemoveStart) {
     // If the def MI defines the val# and this copy is the only kill of the
     // val#, then propagate the dead marker.
-    if (li.isOnlyKill(LR->valno, RemoveEnd)) {
+    if (li.isOnlyLROfValNo(LR)) {
       PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
       ++numDeadValNo;
-    } else
+    }
+    if (li.isKill(LR->valno, RemoveEnd))
       li.removeKill(LR->valno, RemoveEnd);
   }
 
-  removeRange(li, RemoveStart, LR->end, li_, tri_);
+  removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
   return removeIntervalIfEmpty(li, li_, tri_);
 }
 
@@ -1352,6 +1361,15 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
   DOUT << " and "; DstInt.print(DOUT, tri_);
   DOUT << ": ";
 
+  // Save a copy of the virtual register live interval. We'll manually
+  // merge this into the "real" physical register live interval this is
+  // coalesced with.
+  LiveInterval *SavedLI = 0;
+  if (RealDstReg)
+    SavedLI = li_->dupInterval(&SrcInt);
+  else if (RealSrcReg)
+    SavedLI = li_->dupInterval(&DstInt);
+
   // Check if it is necessary to propagate "isDead" property.
   if (!isExtSubReg && !isInsSubReg) {
     MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false);
@@ -1443,21 +1461,17 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
     if (RealDstReg || RealSrcReg) {
       LiveInterval &RealInt =
         li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg);
-      SmallSet<const VNInfo*, 4> CopiedValNos;
-      for (LiveInterval::Ranges::const_iterator I = ResSrcInt->ranges.begin(),
-             E = ResSrcInt->ranges.end(); I != E; ++I) {
-        const LiveRange *DstLR = ResDstInt->getLiveRangeContaining(I->start);
-        assert(DstLR  && "Invalid joined interval!");
-        const VNInfo *DstValNo = DstLR->valno;
-        if (CopiedValNos.insert(DstValNo)) {
-          VNInfo *ValNo = RealInt.getNextValue(DstValNo->def, DstValNo->copy,
-                                               li_->getVNInfoAllocator());
-          ValNo->hasPHIKill = DstValNo->hasPHIKill;
-          RealInt.addKills(ValNo, DstValNo->kills);
-          RealInt.MergeValueInAsValue(*ResDstInt, DstValNo, ValNo);
-        }
+      for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(),
+             E = SavedLI->vni_end(); I != E; ++I) {
+        const VNInfo *ValNo = *I;
+        VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->copy,
+                                                li_->getVNInfoAllocator());
+        NewValNo->hasPHIKill = ValNo->hasPHIKill;
+        NewValNo->redefByEC = ValNo->redefByEC;
+        RealInt.addKills(NewValNo, ValNo->kills);
+        RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo);
       }
-      
+      RealInt.weight += SavedLI->weight;      
       DstReg = RealDstReg ? RealDstReg : RealSrcReg;
     }
 
@@ -1527,6 +1541,12 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
   // being merged.
   li_->removeInterval(SrcReg);
 
+  // Manually deleted the live interval copy.
+  if (SavedLI) {
+    SavedLI->clear();
+    delete SavedLI;
+  }
+
   if (isEmpty) {
     // Now the copy is being coalesced away, the val# previously defined
     // by the copy is being defined by an IMPLICIT_DEF which defines a zero