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 28d249235d136598e41f588721a1495e03d77823..e5286c21cebcbf6666fcc3373280a262a8d9034c 100644 (file)
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -42,6 +42,7 @@ STATISTIC(numExtends  , "Number of copies extended");
 STATISTIC(NumReMats   , "Number of instructions re-materialized");
 STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
 STATISTIC(numAborts   , "Number of times interval joining aborted");
+STATISTIC(numDeadValNo, "Number of valno def marked dead");
 
 char SimpleRegisterCoalescing::ID = 0;
 static cl::opt<bool>
@@ -488,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,
@@ -558,6 +559,9 @@ bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
   const TargetInstrDesc &TID = DefMI->getDesc();
   if (!TID.isAsCheapAsAMove())
     return false;
+  if (!DefMI->getDesc().isRematerializable() ||
+      !tii_->isTriviallyReMaterializable(DefMI))
+    return false;
   bool SawStore = false;
   if (!DefMI->isSafeToMove(tii_, SawStore))
     return false;
@@ -857,14 +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;
 
-  if (LR->valno->def == RemoveStart)
-    // If the def MI defines the val#, propagate the dead marker.
-    PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
+  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.isOnlyLROfValNo(LR)) {
+      PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
+      ++numDeadValNo;
+    }
+    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_);
 }
 
@@ -1342,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);
@@ -1433,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;
     }
 
@@ -1517,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