X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.cpp;h=942d8d95cf993bf740c57efa96adf4bfa20a420c;hb=ef4cfc749a61d0d0252196c957697436ba7ec068;hp=09b610c21dbcafef5c7292b9d57cbf316985a2f9;hpb=e08eb9ca1dc832e0c8b460459fe218622f231898;p=oota-llvm.git

diff --git a/lib/CodeGen/SimpleRegisterCoalescing.cpp b/lib/CodeGen/SimpleRegisterCoalescing.cpp
index 09b610c21db..942d8d95cf9 100644
--- a/lib/CodeGen/SimpleRegisterCoalescing.cpp
+++ b/lib/CodeGen/SimpleRegisterCoalescing.cpp
@@ -36,12 +36,13 @@
 using namespace llvm;
 
 STATISTIC(numJoins    , "Number of interval joins performed");
-STATISTIC(numSubJoins , "Number of subclass joins performed");
+STATISTIC(numCrossRCs , "Number of cross class joins performed");
 STATISTIC(numCommutes , "Number of instruction commuting performed");
 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>
@@ -55,8 +56,8 @@ NewHeuristic("new-coalescer-heuristic",
              cl::init(false), cl::Hidden);
 
 static cl::opt<bool>
-CrossClassJoin("join-subclass-copies",
-               cl::desc("Coalesce copies to sub- register class"),
+CrossClassJoin("join-cross-class-copies",
+               cl::desc("Coalesce cross register class copies"),
                cl::init(false), cl::Hidden);
 
 static RegisterPass<SimpleRegisterCoalescing> 
@@ -386,8 +387,8 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
       else
         BKills.push_back(li_->getUseIndex(UseIdx)+1);
     }
-    unsigned SrcReg, DstReg;
-    if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg))
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
       continue;
     if (DstReg == IntB.reg) {
       // This copy will become a noop. If it's defining a new val#,
@@ -450,6 +451,98 @@ bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
   return true;
 }
 
+/// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
+/// fallthoughs to SuccMBB.
+static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
+                                  MachineBasicBlock *SuccMBB,
+                                  const TargetInstrInfo *tii_) {
+  if (MBB == SuccMBB)
+    return true;
+  MachineBasicBlock *TBB = 0, *FBB = 0;
+  SmallVector<MachineOperand, 4> Cond;
+  return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
+    MBB->isSuccessor(SuccMBB);
+}
+
+/// 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;
+      }
+    }
+  }
+}
+
+/// TrimLiveIntervalToLastUse - If there is a last use in the same basic block
+/// as the copy instruction, trim the live interval to the last use and return
+/// true.
+bool
+SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(unsigned CopyIdx,
+                                                    MachineBasicBlock *CopyMBB,
+                                                    LiveInterval &li,
+                                                    const LiveRange *LR) {
+  unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
+  unsigned LastUseIdx;
+  MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg,
+                                            LastUseIdx);
+  if (LastUse) {
+    MachineInstr *LastUseMI = LastUse->getParent();
+    if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
+      // r1024 = op
+      // ...
+      // BB1:
+      //       = r1024
+      //
+      // BB2:
+      // r1025<dead> = r1024<kill>
+      if (MBBStart < LR->end)
+        removeRange(li, MBBStart, LR->end, li_, tri_);
+      return true;
+    }
+
+    // There are uses before the copy, just shorten the live range to the end
+    // of last use.
+    LastUse->setIsKill();
+    removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
+    li.addKill(LR->valno, LastUseIdx+1);
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
+        DstReg == li.reg) {
+      // Last use is itself an identity code.
+      int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_);
+      LastUseMI->getOperand(DeadIdx).setIsDead();
+    }
+    return true;
+  }
+
+  // Is it livein?
+  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);
+    }
+    // FIXME: Shorten intervals in BBs that reaches this BB.
+  }
+
+  return false;
+}
+
 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
 /// computation, replace the copy by rematerialize the definition.
 bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
@@ -467,6 +560,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;
@@ -485,7 +581,12 @@ bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
     }
   }
 
+  // If copy kills the source register, find the last use and propagate
+  // kill.
   MachineBasicBlock *MBB = CopyMI->getParent();
+  if (CopyMI->killsRegister(SrcInt.reg))
+    TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR);
+
   MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI));
   CopyMI->removeFromParent();
   tii_->reMaterialize(*MBB, MII, DstReg, DefMI);
@@ -563,8 +664,9 @@ SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
       if (OldSubIdx)
           UseDstReg = tri_->getSubReg(DstReg, OldSubIdx);
 
-      unsigned CopySrcReg, CopyDstReg;
-      if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
+      unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
+      if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
+                            CopySrcSubIdx, CopyDstSubIdx) &&
           CopySrcReg != CopyDstReg &&
           CopySrcReg == SrcReg && CopyDstReg != UseDstReg) {
         // If the use is a copy and it won't be coalesced away, and its source
@@ -595,9 +697,10 @@ SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
     // After updating the operand, check if the machine instruction has
     // become a copy. If so, update its val# information.
     const TargetInstrDesc &TID = UseMI->getDesc();
-    unsigned CopySrcReg, CopyDstReg;
+    unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx;
     if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 &&
-        tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
+        tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg,
+                          CopySrcSubIdx, CopyDstSubIdx) &&
         CopySrcReg != CopyDstReg &&
         (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
          allocatableRegs_[CopyDstReg])) {
@@ -658,30 +761,6 @@ void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg,
   }
 }
 
-/// 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. Return true if live interval is removed.
@@ -750,19 +829,6 @@ static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
   }
 }
 
-/// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
-/// fallthoughs to SuccMBB.
-static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
-                                  MachineBasicBlock *SuccMBB,
-                                  const TargetInstrInfo *tii_) {
-  if (MBB == SuccMBB)
-    return true;
-  MachineBasicBlock *TBB = 0, *FBB = 0;
-  SmallVector<MachineOperand, 4> Cond;
-  return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
-    MBB->isSuccessor(SuccMBB);
-}
-
 /// ShortenDeadCopySrcLiveRange - 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
@@ -794,55 +860,31 @@ SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
     // More uses past this copy? Nothing to do.
     return false;
 
+  // If there is a last use in the same bb, we can't remove the live range.
+  // Shorten the live interval and return.
   MachineBasicBlock *CopyMBB = CopyMI->getParent();
-  unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
-  unsigned LastUseIdx;
-  MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg,
-                                            LastUseIdx);
-  if (LastUse) {
-    MachineInstr *LastUseMI = LastUse->getParent();
-    if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
-      // r1024 = op
-      // ...
-      // BB1:
-      //       = r1024
-      //
-      // BB2:
-      // r1025<dead> = r1024<kill>
-      if (MBBStart < LR->end)
-        removeRange(li, MBBStart, LR->end, li_, tri_);
-      return false;
-    }
-
-    // There are uses before the copy, just shorten the live range to the end
-    // of last use.
-    LastUse->setIsKill();
-    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();
-    }
+  if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR))
     return false;
-  }
 
-  // Is it livein?
-  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);
+  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;
     }
-    // FIXME: Shorten intervals in BBs that reaches this BB.
+    if (li.isKill(LR->valno, RemoveEnd))
+      li.removeKill(LR->valno, RemoveEnd);
   }
 
-  if (LR->valno->def == RemoveStart)
-    // If the def MI defines the val#, propagate the dead marker.
-    PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);
-
-  removeRange(li, RemoveStart, LR->end, li_, tri_);
+  removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
   return removeIntervalIfEmpty(li, li_, tri_);
 }
 
@@ -873,8 +915,8 @@ bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI,
     if (ULR == li.end() || ULR->valno != LR->valno)
       continue;
     // If the use is not a use, then it's not safe to coalesce the move.
-    unsigned SrcReg, DstReg;
-    if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg)) {
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
       if (UseMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG &&
           UseMI->getOperand(1).getReg() == li.reg)
         continue;
@@ -911,8 +953,9 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li,
     if (ULR == li.end() || ULR->valno != VNI)
       continue;
     // If the use is a copy, turn it into an identity copy.
-    unsigned SrcReg, DstReg;
-    if (tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == li.reg) {
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
+        SrcReg == li.reg) {
       // Each use MI may have multiple uses of this register. Change them all.
       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
         MachineOperand &MO = MI->getOperand(i);
@@ -925,9 +968,10 @@ void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li,
       LastUse = MO;
     }
   }
-  if (LastUse)
+  if (LastUse) {
     LastUse->setIsKill();
-  else {
+    li.addKill(VNI, LastUseIdx+1);
+  } else {
     // Remove dead implicit_def's.
     while (!ImpDefs.empty()) {
       MachineInstr *ImpDef = ImpDefs.back();
@@ -950,38 +994,24 @@ static unsigned getMatchingSuperReg(unsigned Reg, unsigned SubIdx,
   return 0;
 }
 
-/// isProfitableToCoalesceToSubRC - Given that register class of DstReg is
-/// a subset of the register class of SrcReg, return true if it's profitable
-/// to coalesce the two registers.
+/// isWinToJoinCrossClass - Return true if it's profitable to coalesce
+/// two virtual registers from different register classes.
 bool
-SimpleRegisterCoalescing::isProfitableToCoalesceToSubRC(unsigned SrcReg,
-                                                        unsigned DstReg,
-                                                        MachineBasicBlock *MBB){
-  if (!CrossClassJoin)
-    return false;
-
-  // First let's make sure all uses are in the same MBB.
-  for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(SrcReg),
-         RE = mri_->reg_end(); RI != RE; ++RI) {
-    MachineInstr &MI = *RI;
-    if (MI.getParent() != MBB)
-      return false;
-  }
-  for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(DstReg),
-         RE = mri_->reg_end(); RI != RE; ++RI) {
-    MachineInstr &MI = *RI;
-    if (MI.getParent() != MBB)
-      return false;
-  }
-
+SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned LargeReg,
+                                                unsigned SmallReg,
+                                                unsigned Threshold) {
   // Then make sure the intervals are *short*.
-  LiveInterval &SrcInt = li_->getInterval(SrcReg);
-  LiveInterval &DstInt = li_->getInterval(DstReg);
-  unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt);
-  unsigned DstSize = li_->getApproximateInstructionCount(DstInt);
-  const TargetRegisterClass *RC = mri_->getRegClass(DstReg);
-  unsigned Threshold = allocatableRCRegs_[RC].count() * 2;
-  return (SrcSize + DstSize) <= Threshold;
+  LiveInterval &LargeInt = li_->getInterval(LargeReg);
+  LiveInterval &SmallInt = li_->getInterval(SmallReg);
+  unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt);
+  unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt);
+  if (SmallSize > Threshold || LargeSize > Threshold)
+    if ((float)std::distance(mri_->use_begin(SmallReg),
+                             mri_->use_end()) / SmallSize <
+        (float)std::distance(mri_->use_begin(LargeReg),
+                             mri_->use_end()) / LargeSize)
+      return false;
+  return true;
 }
 
 /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual
@@ -1044,15 +1074,9 @@ SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI,
 /// an extract_subreg where dst is a physical register, e.g.
 /// cl = EXTRACT_SUBREG reg1024, 1
 bool
-SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(MachineInstr *CopyMI,
-                                        unsigned DstReg, unsigned SrcReg,
-                                        unsigned SubIdx, unsigned &RealDstReg) {
-  if (CopyMI->getOperand(1).getSubReg()) {
-    DOUT << "\tSrc of extract_subreg already coalesced with reg"
-         << " of a super-class.\n";
-    return false; // Not coalescable.
-  }
-
+SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(unsigned DstReg,
+                                               unsigned SrcReg, unsigned SubIdx,
+                                               unsigned &RealDstReg) {
   const TargetRegisterClass *RC = mri_->getRegClass(SrcReg);
   RealDstReg = getMatchingSuperReg(DstReg, SubIdx, RC, tri_);
   assert(RealDstReg && "Invalid extract_subreg instruction!");
@@ -1080,14 +1104,9 @@ SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(MachineInstr *CopyMI,
 /// an insert_subreg where src is a physical register, e.g.
 /// reg1024 = INSERT_SUBREG reg1024, c1, 0
 bool
-SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(MachineInstr *CopyMI,
-                                        unsigned DstReg, unsigned SrcReg,
-                                        unsigned SubIdx, unsigned &RealSrcReg) {
-  if (CopyMI->getOperand(1).getSubReg()) {
-    DOUT << "\tSrc of insert_subreg already coalesced with reg"
-         << " of a super-class.\n";
-    return false; // Not coalescable.
-  }
+SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(unsigned DstReg,
+                                               unsigned SrcReg, unsigned SubIdx,
+                                               unsigned &RealSrcReg) {
   const TargetRegisterClass *RC = mri_->getRegClass(DstReg);
   RealSrcReg = getMatchingSuperReg(SrcReg, SubIdx, RC, tri_);
   assert(RealSrcReg && "Invalid extract_subreg instruction!");
@@ -1108,7 +1127,6 @@ SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(MachineInstr *CopyMI,
   return true;
 }
 
-
 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
 /// which are the src/dst of the copy instruction CopyMI.  This returns true
 /// if the copy was successfully coalesced away. If it is not currently
@@ -1123,8 +1141,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
 
   DOUT << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI;
 
-  unsigned SrcReg;
-  unsigned DstReg;
+  unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
   bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG;
   bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG;
   unsigned SubIdx = 0;
@@ -1139,7 +1156,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
     }
     DstReg = CopyMI->getOperand(0).getReg();
     SrcReg = CopyMI->getOperand(2).getReg();
-  } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
+  } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)){
     assert(0 && "Unrecognized copy instruction!");
     return false;
   }
@@ -1170,7 +1187,8 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
   }
 
   // Should be non-null only when coalescing to a sub-register class.
-  const TargetRegisterClass *SubRC = NULL;
+  bool CrossRC = false;
+  const TargetRegisterClass *NewRC = NULL;
   MachineBasicBlock *CopyMBB = CopyMI->getParent();
   unsigned RealDstReg = 0;
   unsigned RealSrcReg = 0;
@@ -1204,13 +1222,17 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
         DstReg = tri_->getSubReg(DstReg, SubIdx);
       SubIdx = 0;
     } else if ((DstIsPhys && isExtSubReg) || (SrcIsPhys && isInsSubReg)) {
+      if (CopyMI->getOperand(1).getSubReg()) {
+        DOUT << "\tSrc of extract_subreg already coalesced with reg"
+             << " of a super-class.\n";
+        return false; // Not coalescable.
+      }
+
       if (isExtSubReg) {
-        if (!CanJoinExtractSubRegToPhysReg(CopyMI, DstReg, SrcReg, SubIdx,
-                                           RealDstReg))
+        if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg))
           return false; // Not coalescable
       } else {
-        if (!CanJoinInsertSubRegToPhysReg(CopyMI, DstReg, SrcReg, SubIdx,
-                                          RealSrcReg))
+        if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg))
           return false; // Not coalescable
       }
       SubIdx = 0;
@@ -1218,8 +1240,7 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
       unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg()
         : CopyMI->getOperand(2).getSubReg();
       if (OldSubIdx) {
-        if (OldSubIdx == SubIdx &&
-            !differingRegisterClasses(SrcReg, DstReg, SubRC))
+        if (OldSubIdx == SubIdx && !differingRegisterClasses(SrcReg, DstReg))
           // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been
           // coalesced to a larger register so the subreg indices cancel out.
           // Also check if the other larger register is of the same register
@@ -1233,41 +1254,95 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
       if (SubIdx) {
         unsigned LargeReg = isExtSubReg ? SrcReg : DstReg;
         unsigned SmallReg = isExtSubReg ? DstReg : SrcReg;
-        unsigned LargeRegSize = 
-          li_->getApproximateInstructionCount(li_->getInterval(LargeReg));
-        unsigned SmallRegSize = 
-          li_->getApproximateInstructionCount(li_->getInterval(SmallReg));
-        const TargetRegisterClass *RC = mri_->getRegClass(SmallReg);
-        unsigned Threshold = allocatableRCRegs_[RC].count();
-        // Be conservative. If both sides are virtual registers, do not coalesce
-        // if this will cause a high use density interval to target a smaller
-        // set of registers.
-        if (SmallRegSize > Threshold || LargeRegSize > Threshold) {
-          if ((float)std::distance(mri_->use_begin(SmallReg),
-                                   mri_->use_end()) / SmallRegSize <
-              (float)std::distance(mri_->use_begin(LargeReg),
-                                   mri_->use_end()) / LargeRegSize) {
-            Again = true;  // May be possible to coalesce later.
-            return false;
-          }
+        unsigned Limit= allocatableRCRegs_[mri_->getRegClass(SmallReg)].count();
+        if (!isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) {
+          Again = true;  // May be possible to coalesce later.
+          return false;
         }
       }
     }
-  } else if (differingRegisterClasses(SrcReg, DstReg, SubRC)) {
-    // FIXME: What if the resul of a EXTRACT_SUBREG is then coalesced
+  } else if (differingRegisterClasses(SrcReg, DstReg)) {
+    if (!CrossClassJoin)
+      return false;
+    CrossRC = true;
+
+    // FIXME: What if the result of a EXTRACT_SUBREG is then coalesced
     // with another? If it's the resulting destination register, then
     // the subidx must be propagated to uses (but only those defined
     // by the EXTRACT_SUBREG). If it's being coalesced into another
     // register, it should be safe because register is assumed to have
     // the register class of the super-register.
 
-    if (!SubRC || !isProfitableToCoalesceToSubRC(SrcReg, DstReg, CopyMBB)) {
-      // If they are not of the same register class, we cannot join them.
+    // Process moves where one of the registers have a sub-register index.
+    MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg);
+    if (DstMO->getSubReg())
+      // FIXME: Can we handle this?
+      return false;
+    MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg);
+    SubIdx = SrcMO->getSubReg();
+    if (SubIdx) {
+      // This is not a extract_subreg but it looks like one.
+      // e.g. %cl = MOV16rr %reg1024:2
+      isExtSubReg = true;
+      if (DstIsPhys) {
+        if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg))
+          return false; // Not coalescable
+        SubIdx = 0;
+      }
+    }
+
+    const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg);
+    const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg);
+    unsigned LargeReg = SrcReg;
+    unsigned SmallReg = DstReg;
+    unsigned Limit = 0;
+
+    // Now determine the register class of the joined register.
+    if (isExtSubReg) {
+      if (SubIdx && DstRC && DstRC->isASubClass()) {
+        // This is a move to a sub-register class. However, the source is a
+        // sub-register of a larger register class. We don't know what should
+        // the register class be. FIXME.
+        Again = true;
+        return false;
+      }
+      Limit = allocatableRCRegs_[DstRC].count();
+    } else if (!SrcIsPhys && !SrcIsPhys) {
+      unsigned SrcSize = SrcRC->getSize();
+      unsigned DstSize = DstRC->getSize();
+      if (SrcSize < DstSize)
+        // For example X86::MOVSD2PDrr copies from FR64 to VR128.
+        NewRC = DstRC;
+      else if (DstSize > SrcSize) {
+        NewRC = SrcRC;
+        std::swap(LargeReg, SmallReg);
+      } else {
+        unsigned SrcNumRegs = SrcRC->getNumRegs();
+        unsigned DstNumRegs = DstRC->getNumRegs();
+        if (DstNumRegs < SrcNumRegs)
+          // Sub-register class?
+          NewRC = DstRC;
+        else if (SrcNumRegs < DstNumRegs) {
+          NewRC = SrcRC;
+          std::swap(LargeReg, SmallReg);
+        } else
+          // No idea what's the right register class to use.
+          return false;
+      }
+    }
+
+    // If we are joining two virtual registers and the resulting register
+    // class is more restrictive (fewer register, smaller size). Check if it's
+    // worth doing the merge.
+    if (!SrcIsPhys && !DstIsPhys &&
+        (isExtSubReg || DstRC->isASubClass()) &&
+        !isWinToJoinCrossClass(LargeReg, SmallReg,
+                               allocatableRCRegs_[NewRC].count())) {
       DOUT << "\tSrc/Dest are different register classes.\n";
       // Allow the coalescer to try again in case either side gets coalesced to
       // a physical register that's compatible with the other side. e.g.
       // r1024 = MOV32to32_ r1025
-      // but later r1024 is assigned EAX then r1025 may be coalesced with EAX.
+      // But later r1024 is assigned EAX then r1025 may be coalesced with EAX.
       Again = true;  // May be possible to coalesce later.
       return false;
     }
@@ -1288,6 +1363,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);
@@ -1379,21 +1463,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;
     }
 
@@ -1415,9 +1495,10 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
 
   // Coalescing to a virtual register that is of a sub-register class of the
   // other. Make sure the resulting register is set to the right register class.
-  if (SubRC) {
-    mri_->setRegClass(DstReg, SubRC);
-    ++numSubJoins;
+  if (CrossRC) {
+      ++numCrossRCs;
+    if (NewRC)
+      mri_->setRegClass(DstReg, NewRC);
   }
 
   if (NewHeuristic) {
@@ -1428,10 +1509,11 @@ bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) {
       if (!vni->def || vni->def == ~1U || vni->def == ~0U)
         continue;
       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
-      unsigned NewSrcReg, NewDstReg;
+      unsigned NewSrcReg, NewDstReg, NewSrcSubIdx, NewDstSubIdx;
       if (CopyMI &&
           JoinedCopies.count(CopyMI) == 0 &&
-          tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg)) {
+          tii_->isMoveInstr(*CopyMI, NewSrcReg, NewDstReg,
+                            NewSrcSubIdx, NewDstSubIdx)) {
         unsigned LoopDepth = loopInfo->getLoopDepth(CopyMBB);
         JoinQueue->push(CopyRec(CopyMI, LoopDepth,
                                 isBackEdgeCopy(CopyMI, DstReg)));
@@ -1461,6 +1543,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
@@ -1570,8 +1658,9 @@ bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li,
     // It's a sub-register live interval, we may not have precise information.
     // Re-compute it.
     MachineInstr *DefMI = li_->getInstructionFromIndex(LR->start);
-    unsigned SrcReg, DstReg;
-    if (DefMI && tii_->isMoveInstr(*DefMI, SrcReg, DstReg) &&
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (DefMI &&
+        tii_->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
         DstReg == li.reg && SrcReg == Reg) {
       // Cache computed info.
       LR->valno->def  = LR->start;
@@ -2070,14 +2159,14 @@ void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB,
     MachineInstr *Inst = MII++;
     
     // If this isn't a copy nor a extract_subreg, we can't join intervals.
-    unsigned SrcReg, DstReg;
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
     if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) {
       DstReg = Inst->getOperand(0).getReg();
       SrcReg = Inst->getOperand(1).getReg();
     } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
       DstReg = Inst->getOperand(0).getReg();
       SrcReg = Inst->getOperand(2).getReg();
-    } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg))
+    } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx))
       continue;
 
     bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg);
@@ -2204,14 +2293,10 @@ void SimpleRegisterCoalescing::joinIntervals() {
 }
 
 /// Return true if the two specified registers belong to different register
-/// classes.  The registers may be either phys or virt regs. In the
-/// case where both registers are virtual registers, it would also returns
-/// true by reference the RegB register class in SubRC if it is a subset of
-/// RegA's register class.
+/// classes.  The registers may be either phys or virt regs.
 bool
-SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB,
-                                      const TargetRegisterClass *&SubRC) const {
-
+SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA,
+                                                   unsigned RegB) const {
   // Get the register classes for the first reg.
   if (TargetRegisterInfo::isPhysicalRegister(RegA)) {
     assert(TargetRegisterInfo::isVirtualRegister(RegB) &&
@@ -2223,10 +2308,7 @@ SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, unsigned RegB,
   const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA);
   if (TargetRegisterInfo::isVirtualRegister(RegB)) {
     const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB);
-    if (RegClassA == RegClassB)
-      return false;
-    SubRC = (RegClassA->hasSubClass(RegClassB)) ? RegClassB : NULL;
-    return true;
+    return RegClassA != RegClassB;
   }
   return !RegClassA->contains(RegB);
 }
@@ -2243,14 +2325,15 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
            E = mri_->use_end(); I != E; ++I) {
       MachineOperand &Use = I.getOperand();
       MachineInstr *UseMI = Use.getParent();
-      unsigned SrcReg, DstReg;
-      if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg) && SrcReg == DstReg)
+      unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+      if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
+          SrcReg == DstReg)
         // Ignore identity copies.
         continue;
       unsigned Idx = li_->getInstructionIndex(UseMI);
       if (Idx >= Start && Idx < End && Idx >= UseIdx) {
         LastUse = &Use;
-        UseIdx = Idx;
+        UseIdx = li_->getUseIndex(Idx);
       }
     }
     return LastUse;
@@ -2269,13 +2352,14 @@ SimpleRegisterCoalescing::lastRegisterUse(unsigned Start, unsigned End,
       return NULL;
 
     // Ignore identity copies.
-    unsigned SrcReg, DstReg;
-    if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg))
+    unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
+    if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) &&
+          SrcReg == DstReg))
       for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) {
         MachineOperand &Use = MI->getOperand(i);
         if (Use.isReg() && Use.isUse() && Use.getReg() &&
             tri_->regsOverlap(Use.getReg(), Reg)) {
-          UseIdx = e;
+          UseIdx = li_->getUseIndex(e);
           return &Use;
         }
       }
@@ -2389,10 +2473,10 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
     for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
          mii != mie; ) {
       MachineInstr *MI = mii;
-      unsigned SrcReg, DstReg;
+      unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
       if (JoinedCopies.count(MI)) {
         // Delete all coalesced copies.
-        if (!tii_->isMoveInstr(*MI, SrcReg, DstReg)) {
+        if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) {
           assert((MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
                   MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) &&
                  "Unrecognized copy instruction");
@@ -2417,6 +2501,8 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
           if (!MO.isReg())
             continue;
           unsigned Reg = MO.getReg();
+          if (!Reg)
+            continue;
           if (TargetRegisterInfo::isVirtualRegister(Reg))
             DeadDefs.push_back(Reg);
           if (MO.isDead())
@@ -2441,7 +2527,7 @@ bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) {
       }
 
       // If the move will be an identity move delete it
-      bool isMove = tii_->isMoveInstr(*MI, SrcReg, DstReg);
+      bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
       if (isMove && SrcReg == DstReg) {
         if (li_->hasInterval(SrcReg)) {
           LiveInterval &RegInt = li_->getInterval(SrcReg);