Take advantage of the recent improvements to the liveintervals set (tracking

instructions which define each value#) to simplify and improve the coallescer.
In particular, this patch:

1. Implements iterative coallescing.
2. Reverts an unsafe hack from handlePhysRegDef, superceeding it with a
   better solution.
3. Implements PR865, "coallescing" away the second copy in code like:

   A = B
   ...
   B = A

This also includes changes to symbolically print registers in intervals
when possible.


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

3 files changed, 330 insertions, 221 deletions

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 0a2483e..a8c01da 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -346,18 +346,29 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) {
 
 /// getLiveRangeContaining - Return the live range that contains the
 /// specified index, or null if there is none.
-const LiveRange *LiveInterval::getLiveRangeContaining(unsigned Idx) const {
-  Ranges::const_iterator It = std::upper_bound(ranges.begin(),ranges.end(),Idx);
+LiveInterval::const_iterator 
+LiveInterval::FindLiveRangeContaining(unsigned Idx) const {
+  const_iterator It = std::upper_bound(begin(), end(), Idx);
   if (It != ranges.begin()) {
-    const LiveRange &LR = *prior(It);
-    if (LR.contains(Idx))
-      return &LR;
+    --It;
+    if (It->contains(Idx))
+      return It;
   }
 
-  return 0;
+  return end();
 }
 
-
+LiveInterval::iterator 
+LiveInterval::FindLiveRangeContaining(unsigned Idx) {
+  iterator It = std::upper_bound(begin(), end(), Idx);
+  if (It != ranges.begin()) {
+    --It;
+    if (It->contains(Idx))
+      return It;
+  }
+  
+  return end();
+}
 
 /// join - Join two live intervals (this, and other) together.  This operation
 /// is the result of a copy instruction in the source program, that occurs at
@@ -376,6 +387,7 @@ void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) {
     std::swap(MergedSrcValIdx, MergedDstValIdx);
     std::swap(ranges, Other.ranges);
     std::swap(NumValues, Other.NumValues);
+    std::swap(InstDefiningValue, Other.InstDefiningValue);
   }
 
   // Join the ranges of other into the ranges of this interval.
@@ -394,10 +406,73 @@ void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) {
 
     InsertPos = addRangeFrom(*I, InsertPos);
   }
-
+  
+  // Update the value number information for the value number defined by the
+  // copy.  The copy is about to be removed, so ensure that the value is defined
+  // by whatever the other value is defined by.
+  if (InstDefiningValue[MergedDstValIdx] == CopyIdx) {
+    InstDefiningValue[MergedDstValIdx] =
+      Other.InstDefiningValue[MergedSrcValIdx];
+  }
+  
   weight += Other.weight;
 }
 
+/// 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
+/// cause merging of V1/V2 values numbers and compaction of the value space.
+void LiveInterval::MergeValueNumberInto(unsigned V1, unsigned V2) {
+  assert(V1 != V2 && "Identical value#'s are always equivalent!");
+
+  // This code actually merges the (numerically) larger value number into the
+  // smaller value number, which is likely to allow us to compactify the value
+  // space.  The only thing we have to be careful of is to preserve the
+  // instruction that defines the result value.
+
+  // Make sure V2 is smaller than V1.
+  if (V1 < V2) {
+    setInstDefiningValNum(V1, getInstForValNum(V2));
+    std::swap(V1, V2);
+  }
+
+  // Merge V1 live ranges into V2.
+  for (iterator I = begin(); I != end(); ) {
+    iterator LR = I++;
+    if (LR->ValId != V1) continue;  // Not a V1 LiveRange.
+    
+    // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
+    // range, extend it.
+    if (LR != begin()) {
+      iterator Prev = LR-1;
+      if (Prev->ValId == V2 && Prev->end == LR->start) {
+        Prev->end = LR->end;
+
+        // Erase this live-range.
+        ranges.erase(LR);
+        I = Prev+1;
+        LR = Prev;
+      }
+    }
+    
+    // Okay, now we have a V1 or V2 live range that is maximally merged forward.
+    // Ensure that it is a V2 live-range.
+    LR->ValId = V2;
+    
+    // If we can merge it into later V2 live ranges, do so now.  We ignore any
+    // following V1 live ranges, as they will be merged in subsequent iterations
+    // of the loop.
+    if (I != end()) {
+      if (I->start == LR->end && I->ValId == V2) {
+        LR->end = I->end;
+        ranges.erase(I);
+        I = LR+1;
+      }
+    }
+  }
+}
+
+
 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
   return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")";
 }
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index e9bdaa1..5a7587f 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -61,8 +61,7 @@ namespace {
                 cl::init(true));
 }
 
-void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
-{
+void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LiveVariables>();
   AU.addPreservedID(PHIEliminationID);
   AU.addRequiredID(PHIEliminationID);
@@ -71,8 +70,7 @@ void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
-void LiveIntervals::releaseMemory()
-{
+void LiveIntervals::releaseMemory() {
   mi2iMap_.clear();
   i2miMap_.clear();
   r2iMap_.clear();
@@ -140,10 +138,10 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
     for (MachineFunction::livein_iterator I = fn.livein_begin(),
            E = fn.livein_end(); I != E; ++I) {
       handlePhysicalRegisterDef(Entry, Entry->begin(),
-                                getOrCreateInterval(I->first), 0, 0, true);
+                                getOrCreateInterval(I->first), true);
       for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS)
         handlePhysicalRegisterDef(Entry, Entry->begin(),
-                                  getOrCreateInterval(*AS), 0, 0, true);
+                                  getOrCreateInterval(*AS), true);
     }
   }
 
@@ -179,13 +177,7 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
           (RegRep = rep(srcReg)) == rep(dstReg)) {
         // remove from def list
         LiveInterval &interval = getOrCreateInterval(RegRep);
-        // remove index -> MachineInstr and
-        // MachineInstr -> index mappings
-        Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii);
-        if (mi2i != mi2iMap_.end()) {
-          i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
-          mi2iMap_.erase(mi2i);
-        }
+        RemoveMachineInstrFromMaps(mii);
         mii = mbbi->erase(mii);
         ++numPeep;
       }
@@ -252,8 +244,8 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
   assert(li.weight != HUGE_VAL &&
          "attempt to spill already spilled interval!");
 
-  DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: "
-        << li << '\n');
+  DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: ";
+        li.print(std::cerr, mri_); std::cerr << '\n');
 
   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg);
 
@@ -341,7 +333,8 @@ addIntervalsForSpills(const LiveInterval &li, VirtRegMap &vrm, int slot) {
             // a def, we can't do this.
             if (!mop.isUse()) NewRegLiveIn = 0;
             
-            DEBUG(std::cerr << "\t\t\t\tadded new interval: " << nI << '\n');
+            DEBUG(std::cerr << "\t\t\t\tadded new interval: ";
+                  nI.print(std::cerr, mri_); std::cerr << '\n');
           }
         }
       }
@@ -478,7 +471,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
       if (lv_->RegisterDefIsDead(mi, interval.reg))
         interval.addRange(LiveRange(RedefIndex, RedefIndex+1, 0));
 
-      DEBUG(std::cerr << "RESULT: " << interval);
+      DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_));
 
     } else {
       // Otherwise, this must be because of phi elimination.  If this is the
@@ -492,17 +485,17 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
         MachineInstr *Killer = vi.Kills[0];
         unsigned Start = getInstructionIndex(Killer->getParent()->begin());
         unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
-        DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: "
-              << interval << "\n");
+        DEBUG(std::cerr << "Removing [" << Start << "," << End << "] from: ";
+              interval.print(std::cerr, mri_); std::cerr << "\n");
         interval.removeRange(Start, End);
-        DEBUG(std::cerr << "RESULT: " << interval);
+        DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_));
 
         // Replace the interval with one of a NEW value number.  Note that this
         // value number isn't actually defined by an instruction, weird huh? :)
         LiveRange LR(Start, End, interval.getNextValue(~0U));
         DEBUG(std::cerr << " replace range with " << LR);
         interval.addRange(LR);
-        DEBUG(std::cerr << "RESULT: " << interval);
+        DEBUG(std::cerr << "RESULT: "; interval.print(std::cerr, mri_));
       }
 
       // In the case of PHI elimination, each variable definition is only
@@ -523,7 +516,6 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
                                               MachineBasicBlock::iterator mi,
                                               LiveInterval& interval,
-                                              unsigned SrcReg, unsigned DestReg,
                                               bool isLiveIn) {
   // A physical register cannot be live across basic block, so its
   // lifetime must end somewhere in its defining basic block.
@@ -564,44 +556,7 @@ void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
 exit:
   assert(start < end && "did not find end of interval?");
 
-  // Finally, if this is defining a new range for the physical register, and if
-  // that physreg is just a copy from a vreg, and if THAT vreg was a copy from
-  // the physreg, then the new fragment has the same value as the one copied
-  // into the vreg.
-  if (interval.reg == DestReg && !interval.empty() &&
-      MRegisterInfo::isVirtualRegister(SrcReg)) {
-
-    // Get the live interval for the vreg, see if it is defined by a copy.
-    LiveInterval &SrcInterval = getOrCreateInterval(SrcReg);
-
-    if (SrcInterval.containsOneValue()) {
-      assert(!SrcInterval.empty() && "Can't contain a value and be empty!");
-
-      // Get the first index of the first range.  Though the interval may have
-      // multiple liveranges in it, we only check the first.
-      unsigned StartIdx = SrcInterval.begin()->start;
-      MachineInstr *SrcDefMI = getInstructionFromIndex(StartIdx);
-
-      // Check to see if the vreg was defined by a copy instruction, and that
-      // the source was this physreg.
-      unsigned VRegSrcSrc, VRegSrcDest;
-      if (tii_->isMoveInstr(*SrcDefMI, VRegSrcSrc, VRegSrcDest) &&
-          SrcReg == VRegSrcDest && VRegSrcSrc == DestReg) {
-        // Okay, now we know that the vreg was defined by a copy from this
-        // physreg.  Find the value number being copied and use it as the value
-        // for this range.
-        const LiveRange *DefRange = interval.getLiveRangeContaining(StartIdx-1);
-        if (DefRange) {
-          LiveRange LR(start, end, DefRange->ValId);
-          interval.addRange(LR);
-          DEBUG(std::cerr << " +" << LR << '\n');
-          return;
-        }
-      }
-    }
-  }
-
-  LiveRange LR(start, end, interval.getNextValue(start));
+  LiveRange LR(start, end, interval.getNextValue(isLiveIn ? ~0U : start));
   interval.addRange(LR);
   DEBUG(std::cerr << " +" << LR << '\n');
 }
@@ -612,15 +567,9 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
   if (MRegisterInfo::isVirtualRegister(reg))
     handleVirtualRegisterDef(MBB, MI, getOrCreateInterval(reg));
   else if (allocatableRegs_[reg]) {
-    unsigned SrcReg = 0, DestReg = 0;
-    if (!tii_->isMoveInstr(*MI, SrcReg, DestReg))
-      SrcReg = DestReg = 0;
-
-    handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg),
-                              SrcReg, DestReg);
+    handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(reg));
     for (const unsigned* AS = mri_->getAliasSet(reg); *AS; ++AS)
-      handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS),
-                                SrcReg, DestReg);
+      handlePhysicalRegisterDef(MBB, MI, getOrCreateInterval(*AS));
   }
 }
 
@@ -628,8 +577,7 @@ void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
 /// registers. for some ordering of the machine instructions [1,N] a
 /// live interval is an interval [i, j) where 1 <= i <= j < N for
 /// which a variable is live
-void LiveIntervals::computeIntervals()
-{
+void LiveIntervals::computeIntervals() {
   DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n");
   DEBUG(std::cerr << "********** Function: "
         << ((Value*)mf_->getFunction())->getName() << '\n');
@@ -664,131 +612,200 @@ void LiveIntervals::computeIntervals()
   }
 }
 
-/// IntA is defined as a copy from IntB and we know it only has one value
-/// number.  If all of the places that IntA and IntB overlap are defined by
-/// copies from IntA to IntB, we know that these two ranges can really be
-/// merged if we adjust the value numbers.  If it is safe, adjust the value
-/// numbers and return true, allowing coalescing to occur.
-bool LiveIntervals::
-AdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA,
-                                          LiveInterval &IntB,
-                                          unsigned CopyIdx) {
-  std::vector<LiveRange*> Ranges;
-  IntA.getOverlapingRanges(IntB, CopyIdx, Ranges);
+/// AdjustCopiesBackFrom - We found a non-trivially-coallescable copy with IntA
+/// being the source and IntB being the dest, thus this defines a value number
+/// in IntB.  If the source value number (in IntA) is defined by a copy from B,
+/// see if we can merge these two pieces of B into a single value number,
+/// eliminating a copy.  For example:
+///
+///  A3 = B0
+///    ...
+///  B1 = A3      <- this copy
+///
+/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
+/// value number to be replaced with B0 (which simplifies the B liveinterval).
+///
+/// This returns true if an interval was modified.
+///
+bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
+                                         MachineInstr *CopyMI,
+                                         unsigned CopyIdx) {
+  // BValNo is a value number in B that is defined by a copy from A.  'B3' in
+  // the example above.
+  LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
+  unsigned BValNo = BLR->ValId;
+  
+  // Get the location that B is defined at.  Two options: either this value has
+  // an unknown definition point or it is defined at CopyIdx.  If unknown, we 
+  // can't process it.
+  unsigned BValNoDefIdx = IntB.getInstForValNum(BValNo);
+  if (BValNoDefIdx == ~0U) return false;
+  assert(BValNoDefIdx == CopyIdx &&
+         "Copy doesn't define the value?");
+  
+  // AValNo is the value number in A that defines the copy, A0 in the example.
+  LiveInterval::iterator AValLR = IntA.FindLiveRangeContaining(CopyIdx-1);
+  unsigned AValNo = AValLR->ValId;
   
-  assert(!Ranges.empty() && "Why didn't we do a simple join of this?");
+  // If AValNo is defined as a copy from IntB, we can potentially process this.
   
-  unsigned IntBRep = rep(IntB.reg);
+  // Get the instruction that defines this value number.
+  unsigned AValNoInstIdx = IntA.getInstForValNum(AValNo);
   
-  // Check to see if all of the overlaps (entries in Ranges) are defined by a
-  // copy from IntA.  If not, exit.
-  for (unsigned i = 0, e = Ranges.size(); i != e; ++i) {
-    unsigned Idx = Ranges[i]->start;
-    MachineInstr *MI = getInstructionFromIndex(Idx);
-    unsigned SrcReg, DestReg;
-    if (!tii_->isMoveInstr(*MI, SrcReg, DestReg)) return false;
+  // If it's unknown, ignore it.
+  if (AValNoInstIdx == ~0U || AValNoInstIdx == ~1U) return false;
+  // Otherwise, get the instruction for it.
+  MachineInstr *AValNoInstMI = getInstructionFromIndex(AValNoInstIdx);
     
-    // If this copy isn't actually defining this range, it must be a live
-    // range spanning basic blocks or something.
-    if (rep(DestReg) != rep(IntA.reg)) return false;
+  // If the value number is not defined by a copy instruction, ignore it.
+  unsigned SrcReg, DstReg;
+  if (!tii_->isMoveInstr(*AValNoInstMI, SrcReg, DstReg))
+    return false;
     
-    // Check to see if this is coming from IntB.  If not, bail out.
-    if (rep(SrcReg) != IntBRep) return false;
-  }
-
-  // Okay, we can change this one.  Get the IntB value number that IntA is
-  // copied from.
-  unsigned ActualValNo = IntA.getLiveRangeContaining(CopyIdx-1)->ValId;
+  // If the source register comes from an interval other than IntB, we can't
+  // handle this.
+  assert(rep(DstReg) == IntA.reg && "Not defining a reg in IntA?");
+  if (rep(SrcReg) != IntB.reg) return false;
+    
+  // Get the LiveRange in IntB that this value number starts with.
+  LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNoInstIdx-1);
   
-  // Change all of the value numbers to the same as what we IntA is copied from.
-  for (unsigned i = 0, e = Ranges.size(); i != e; ++i)
-    Ranges[i]->ValId = ActualValNo;
+  // Make sure that the end of the live range is inside the same block as
+  // CopyMI.
+  MachineInstr *ValLREndInst = getInstructionFromIndex(ValLR->end-1);
+  if (ValLREndInst->getParent() != CopyMI->getParent()) return false;
+
+  // Okay, we now know that ValLR ends in the same block that the CopyMI
+  // live-range starts.  If there are no intervening live ranges between them in
+  // IntB, we can merge them.
+  if (ValLR+1 != BLR) return false;
   
+  DEBUG(std::cerr << "\nExtending: "; IntB.print(std::cerr, mri_));
+    
+  // Okay, we can merge them.  We need to insert a new liverange:
+  // [ValLR.end, BLR.begin) of either value number, then we merge the
+  // two value numbers.
+  IntB.addRange(LiveRange(ValLR->end, BLR->start, BValNo));
+
+  // Okay, merge "B1" into the same value number as "B0".
+  if (BValNo != ValLR->ValId)
+    IntB.MergeValueNumberInto(BValNo, ValLR->ValId);
+  DEBUG(std::cerr << "   result = "; IntB.print(std::cerr, mri_);
+        std::cerr << "\n");
+  
+  // Finally, delete the copy instruction.
+  RemoveMachineInstrFromMaps(CopyMI);
+  CopyMI->eraseFromParent();
+  ++numPeep;
   return true;
 }
 
-void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) {
-  DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
 
-  for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end();
-       mi != mie; ++mi) {
-    DEBUG(std::cerr << getInstructionIndex(mi) << '\t' << *mi);
-
-    // we only join virtual registers with allocatable
-    // physical registers since we do not have liveness information
-    // on not allocatable physical registers
-    unsigned SrcReg, DestReg;
-    if (tii_->isMoveInstr(*mi, SrcReg, DestReg) &&
-        (MRegisterInfo::isVirtualRegister(SrcReg) || allocatableRegs_[SrcReg])&&
-        (MRegisterInfo::isVirtualRegister(DestReg)||allocatableRegs_[DestReg])){
-
-      // Get representative registers.
-      SrcReg = rep(SrcReg);
-      DestReg = rep(DestReg);
-
-      // If they are already joined we continue.
-      if (SrcReg == DestReg)
-        continue;
-
-      // If they are both physical registers, we cannot join them.
-      if (MRegisterInfo::isPhysicalRegister(SrcReg) &&
-          MRegisterInfo::isPhysicalRegister(DestReg))
-        continue;
-
-      // If they are not of the same register class, we cannot join them.
-      if (differingRegisterClasses(SrcReg, DestReg))
-        continue;
-
-      LiveInterval &SrcInt = getInterval(SrcReg);
-      LiveInterval &DestInt = getInterval(DestReg);
-      assert(SrcInt.reg == SrcReg && DestInt.reg == DestReg &&
-             "Register mapping is horribly broken!");
-
-      DEBUG(std::cerr << "\t\tInspecting "; SrcInt.print(std::cerr, mri_);
-            std::cerr << " and "; DestInt.print(std::cerr, mri_);
-            std::cerr << ": ");
-
-      // If two intervals contain a single value and are joined by a copy, it
-      // does not matter if the intervals overlap, they can always be joined.
-      bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue();
-
-      unsigned MIDefIdx = getDefIndex(getInstructionIndex(mi));
-      
-      // If the intervals think that this is joinable, do so now.
-      if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx))
-        Joinable = true;
-
-      // If DestInt is actually a copy from SrcInt (which we know) that is used
-      // to define another value of SrcInt, we can change the other range of
-      // SrcInt to be the value of the range that defines DestInt, allowing a
-      // coalesce.
-      if (!Joinable && DestInt.containsOneValue() &&
-          AdjustIfAllOverlappingRangesAreCopiesFrom(SrcInt, DestInt, MIDefIdx))
-        Joinable = true;
-      
-      if (!Joinable || overlapsAliases(&SrcInt, &DestInt)) {
-        DEBUG(std::cerr << "Interference!\n");
-      } else {
-        DestInt.join(SrcInt, MIDefIdx);
-        DEBUG(std::cerr << "Joined.  Result = " << DestInt << "\n");
-
-        if (!MRegisterInfo::isPhysicalRegister(SrcReg)) {
-          r2iMap_.erase(SrcReg);
-          r2rMap_[SrcReg] = DestReg;
-        } else {
-          // Otherwise merge the data structures the other way so we don't lose
-          // the physreg information.
-          r2rMap_[DestReg] = SrcReg;
-          DestInt.reg = SrcReg;
-          SrcInt.swap(DestInt);
-          r2iMap_.erase(DestReg);
-        }
-        ++numJoins;
-      }
-    }
+/// 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 coallesced away, or if it is never possible
+/// to coallesce these this copy, due to register constraints.  It returns
+/// false if it is not currently possible to coallesce this interval, but
+/// it may be possible if other things get coallesced.
+bool LiveIntervals::JoinCopy(MachineInstr *CopyMI,
+                             unsigned SrcReg, unsigned DstReg) {
+  
+  
+  DEBUG(std::cerr << getInstructionIndex(CopyMI) << '\t' << *CopyMI);
+  
+  // Get representative registers.
+  SrcReg = rep(SrcReg);
+  DstReg = rep(DstReg);
+  
+  // If they are already joined we continue.
+  if (SrcReg == DstReg) {
+    DEBUG(std::cerr << "\tCopy already coallesced.\n");
+    return true;  // Not coallescable.
+  }
+  
+  // If they are both physical registers, we cannot join them.
+  if (MRegisterInfo::isPhysicalRegister(SrcReg) &&
+      MRegisterInfo::isPhysicalRegister(DstReg)) {
+    DEBUG(std::cerr << "\tCan not coallesce physregs.\n");
+    return true;  // Not coallescable.
   }
+  
+  // We only join virtual registers with allocatable physical registers.
+  if (MRegisterInfo::isPhysicalRegister(SrcReg) && !allocatableRegs_[SrcReg]){
+    DEBUG(std::cerr << "\tSrc reg is unallocatable physreg.\n");
+    return true;  // Not coallescable.
+  }
+  if (MRegisterInfo::isPhysicalRegister(DstReg) && !allocatableRegs_[DstReg]){
+    DEBUG(std::cerr << "\tDst reg is unallocatable physreg.\n");
+    return true;  // Not coallescable.
+  }
+  
+  // If they are not of the same register class, we cannot join them.
+  if (differingRegisterClasses(SrcReg, DstReg)) {
+    DEBUG(std::cerr << "\tSrc/Dest are different register classes.\n");
+    return true;  // Not coallescable.
+  }
+  
+  LiveInterval &SrcInt = getInterval(SrcReg);
+  LiveInterval &DestInt = getInterval(DstReg);
+  assert(SrcInt.reg == SrcReg && DestInt.reg == DstReg &&
+         "Register mapping is horribly broken!");
+  
+  DEBUG(std::cerr << "\t\tInspecting "; SrcInt.print(std::cerr, mri_);
+        std::cerr << " and "; DestInt.print(std::cerr, mri_);
+        std::cerr << ": ");
+    
+  // If two intervals contain a single value and are joined by a copy, it
+  // does not matter if the intervals overlap, they can always be joined.
+
+  bool Joinable = SrcInt.containsOneValue() && DestInt.containsOneValue();
+  
+  unsigned MIDefIdx = getDefIndex(getInstructionIndex(CopyMI));
+  
+  // If the intervals think that this is joinable, do so now.
+  if (!Joinable && DestInt.joinable(SrcInt, MIDefIdx))
+    Joinable = true;
+  
+  // If DestInt is actually a copy from SrcInt (which we know) that is used
+  // to define another value of SrcInt, we can change the other range of
+  // SrcInt to be the value of the range that defines DestInt, simplying the
+  // interval an promoting coallescing.
+  if (!Joinable && AdjustCopiesBackFrom(SrcInt, DestInt, CopyMI, MIDefIdx))
+    return true;
+  
+  // If this looks joinable, do the final, expensive last check, checking to see
+  // if aliases overlap.  If they do, we can never join these.
+  if (Joinable && overlapsAliases(&SrcInt, &DestInt)) {
+    DEBUG(std::cerr << "Alias Overlap Interference!\n");
+    return true;   // Can never join these.
+  }
+  
+  if (!Joinable) {
+    DEBUG(std::cerr << "Interference!\n");
+    return false;
+  }
+
+  DestInt.join(SrcInt, MIDefIdx);
+  DEBUG(std::cerr << "\n\t\tJoined.  Result = "; DestInt.print(std::cerr, mri_);
+        std::cerr << "\n");
+    
+  if (!MRegisterInfo::isPhysicalRegister(SrcReg)) {
+    r2iMap_.erase(SrcReg);
+    r2rMap_[SrcReg] = DstReg;
+  } else {
+    // Otherwise merge the data structures the other way so we don't lose
+    // the physreg information.
+    r2rMap_[DstReg] = SrcReg;
+    DestInt.reg = SrcReg;
+    SrcInt.swap(DestInt);
+    r2iMap_.erase(DstReg);
+  }
+  ++numJoins;
+  return true;
 }
 
+
+
 namespace {
   // DepthMBBCompare - Comparison predicate that sort first based on the loop
   // depth of the basic block (the unsigned), and then on the MBB number.
@@ -802,15 +819,36 @@ namespace {
   };
 }
 
+
+void LiveIntervals::CopyCoallesceInMBB(MachineBasicBlock *MBB,
+                                       std::vector<CopyRec> &TryAgain) {
+  DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n");
+  
+  for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
+       MII != E;) {
+    MachineInstr *Inst = MII++;
+    
+    // If this isn't a copy, we can't join intervals.
+    unsigned SrcReg, DstReg;
+    if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg)) continue;
+    
+    if (!JoinCopy(Inst, SrcReg, DstReg))
+      TryAgain.push_back(getCopyRec(Inst, SrcReg, DstReg));
+  }
+}
+
+
 void LiveIntervals::joinIntervals() {
   DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n");
 
+  std::vector<CopyRec> TryAgainList;
+  
   const LoopInfo &LI = getAnalysis<LoopInfo>();
   if (LI.begin() == LI.end()) {
     // If there are no loops in the function, join intervals in function order.
     for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();
          I != E; ++I)
-      joinIntervalsInMachineBB(I);
+      CopyCoallesceInMBB(I, TryAgainList);
   } else {
     // Otherwise, join intervals in inner loops before other intervals.
     // Unfortunately we can't just iterate over loop hierarchy here because
@@ -825,9 +863,25 @@ void LiveIntervals::joinIntervals() {
 
     // Finally, join intervals in loop nest order.
     for (unsigned i = 0, e = MBBs.size(); i != e; ++i)
-      joinIntervalsInMachineBB(MBBs[i].second);
+      CopyCoallesceInMBB(MBBs[i].second, TryAgainList);
   }
 
+  // Joining intervals can allow other intervals to be joined.  Iteratively join
+  // until we make no progress.
+  bool ProgressMade = true;
+  while (ProgressMade) {
+    ProgressMade = false;
+    
+    for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) {
+      CopyRec &TheCopy = TryAgainList[i];
+      if (TheCopy.MI &&
+          JoinCopy(TheCopy.MI, TheCopy.SrcReg, TheCopy.DstReg)) {
+        TheCopy.MI = 0;   // Mark this one as done.
+        ProgressMade = true;
+      }
+    }
+  }
+  
   DEBUG(std::cerr << "*** Register mapping ***\n");
   DEBUG(for (int i = 0, e = r2rMap_.size(); i != e; ++i)
           if (r2rMap_[i]) {
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index 7e6d09b..bc56945 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -521,7 +521,6 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
     // Process all of the spilled uses and all non spilled reg references.
     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
       MachineOperand &MO = MI.getOperand(i);
-
       if (!MO.isRegister() || MO.getReg() == 0)
         continue;   // Ignore non-register operands.
       
@@ -791,37 +790,16 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
           }
 
           if (!OpTakenCareOf) {
+            // Check to see if this is a noop copy.  If so, eliminate the
+            // instruction before considering the dest reg to be changed.
             unsigned Src, Dst;
-            if (TII->isMoveInstr(MI, Src, Dst)) {
-              if (Src == Dst) {
-                // Check to see if this is a noop copy.  If so, eliminate
-                // the instruction before considering the dest reg to be
-                // changed.
-                ++NumDCE;
-                DEBUG(std::cerr << "Removing now-noop copy: " << MI);
-                MBB.erase(&MI);
-                VRM.RemoveFromFoldedVirtMap(&MI);
-                goto ProcessNextInst;
-              } else if (MII != MBB.begin()) {
-                // Check to see if this is a sequence of the form:
-                //    mov R0, R1
-                //    mov R1, R0
-                // Eliminate the second move if so.
-                MachineBasicBlock::iterator PrevMII = MII; --PrevMII;
-                MachineInstr& PrevMI = *PrevMII;
-                unsigned PrevSrc, PrevDst;
-
-                if (TII->isMoveInstr(PrevMI, PrevSrc, PrevDst))
-                  if (PrevSrc == Dst && PrevDst == Src) {
-                    ++NumDCE;
-                    DEBUG(std::cerr << "Removing now-noop copy: " << MI);
-                    MBB.erase(&MI);
-                    VRM.RemoveFromFoldedVirtMap(&MI);
-                    goto ProcessNextInst;
-                  }
-              }
+            if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
+              ++NumDCE;
+              DEBUG(std::cerr << "Removing now-noop copy: " << MI);
+              MBB.erase(&MI);
+              VRM.RemoveFromFoldedVirtMap(&MI);
+              goto ProcessNextInst;
             }
-
             Spills.ClobberPhysReg(VirtReg);
             continue;
           }
@@ -883,6 +861,8 @@ void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
   }
 }
 
+
+
 llvm::Spiller* llvm::createSpiller() {
   switch (SpillerOpt) {
   default: assert(0 && "Unreachable!");