diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 7f16b31..8be9677 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -101,101 +101,6 @@
   return false;
 }
 
-/// NontrivialOverlap - Check to see if the two live ranges specified by i and j
-/// overlap.  If so, check to see if they have value numbers that are not 
-/// iIdx/jIdx respectively.  If both conditions are true, return true.
-static inline bool NontrivialOverlap(const LiveRange &I, const LiveRange &J,
-                                     unsigned iIdx, unsigned jIdx) {
-  if (I.start == J.start) {
-    // If this is not the allowed value merge, we cannot join.
-    if (I.ValId != iIdx || J.ValId != jIdx)
-      return true;
-  } else if (I.start < J.start) {
-    if (I.end > J.start && (I.ValId != iIdx || J.ValId != jIdx)) {
-      return true;
-    }
-  } else {
-    if (J.end > I.start && (I.ValId != iIdx || J.ValId != jIdx))
-      return true;
-  }
-  
-  return false;
-}
-
-/// joinable - Two intervals are joinable if the either don't overlap at all
-/// or if the destination of the copy is a single assignment value, and it
-/// only overlaps with one value in the source interval.
-bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const {
-  const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1);
-  const LiveRange *DestLR = getLiveRangeContaining(CopyIdx);
-  assert(SourceLR && DestLR && "Not joining due to a copy?");
-  unsigned OtherValIdx = SourceLR->ValId;
-  unsigned ThisValIdx = DestLR->ValId;
-
-  Ranges::const_iterator i = ranges.begin();
-  Ranges::const_iterator ie = ranges.end();
-  Ranges::const_iterator j = other.ranges.begin();
-  Ranges::const_iterator je = other.ranges.end();
-
-  if (i->start < j->start) {
-    i = std::upper_bound(i, ie, j->start);
-    if (i != ranges.begin()) --i;
-  } else if (j->start < i->start) {
-    j = std::upper_bound(j, je, i->start);
-    if (j != other.ranges.begin()) --j;
-  }
-
-  while (i != ie && j != je) {
-    if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx))
-      return false;
-    
-    if (i->end < j->end)
-      ++i;
-    else
-      ++j;
-  }
-
-  return true;
-}
-
-/// getOverlapingRanges - Given another live interval which is defined as a
-/// copy from this one, return a list of all of the live ranges where the
-/// two overlap and have different value numbers.
-void LiveInterval::getOverlapingRanges(const LiveInterval &other, 
-                                       unsigned CopyIdx,
-                                       std::vector<LiveRange*> &Ranges) {
-  const LiveRange *SourceLR = getLiveRangeContaining(CopyIdx-1);
-  const LiveRange *DestLR = other.getLiveRangeContaining(CopyIdx);
-  assert(SourceLR && DestLR && "Not joining due to a copy?");
-  unsigned OtherValIdx = SourceLR->ValId;
-  unsigned ThisValIdx = DestLR->ValId;
-  
-  Ranges::iterator i = ranges.begin();
-  Ranges::iterator ie = ranges.end();
-  Ranges::const_iterator j = other.ranges.begin();
-  Ranges::const_iterator je = other.ranges.end();
-  
-  if (i->start < j->start) {
-    i = std::upper_bound(i, ie, j->start);
-    if (i != ranges.begin()) --i;
-  } else if (j->start < i->start) {
-    j = std::upper_bound(j, je, i->start);
-    if (j != other.ranges.begin()) --j;
-  }
-  
-  while (i != ie && j != je) {
-    if (NontrivialOverlap(*i, *j, ThisValIdx, OtherValIdx))
-      Ranges.push_back(&*i);
-    
-    if (i->end < j->end)
-      ++i;
-    else
-      ++j;
-  }
-}
-
-
-
 /// extendIntervalEndTo - This method is used when we want to extend the range
 /// specified by I to end at the specified endpoint.  To do this, we should
 /// merge and eliminate all ranges that this will overlap with.  The iterator is
@@ -361,7 +266,7 @@
 LiveInterval::iterator 
 LiveInterval::FindLiveRangeContaining(unsigned Idx) {
   iterator It = std::upper_bound(begin(), end(), Idx);
-  if (It != ranges.begin()) {
+  if (It != begin()) {
     --It;
     if (It->contains(Idx))
       return It;
@@ -370,10 +275,13 @@
   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
-/// index 'CopyIdx' that copies from 'Other' to 'this'.
-void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) {
+/// join - Join two live intervals (this, and other) together.  This applies
+/// mappings to the value numbers in the LHS/RHS intervals as specified.  If
+/// the intervals are not joinable, this aborts.
+void LiveInterval::join(LiveInterval &Other, int *LHSValNoAssignments,
+                        int *RHSValNoAssignments, 
+                        SmallVector<unsigned, 16> &NewInstDefiningValue) {
+  
   // Try to do the least amount of work possible.  In particular, if there are
   // more liverange chunks in the other set than there are in the 'this' set,
   // swap sets to merge the fewest chunks in possible.
@@ -385,39 +293,61 @@
       MRegisterInfo::isVirtualRegister(reg)) ||
       MRegisterInfo::isPhysicalRegister(Other.reg)) {
     swap(Other);
-    std::swap(ThisOffs, OtherOffs);
+    std::swap(LHSValNoAssignments, RHSValNoAssignments);
+  }
+
+  // Determine if any of our live range values are mapped.  This is uncommon, so
+  // we want to avoid the interval scan if not.
+  bool MustMapCurValNos = false;
+  for (unsigned i = 0, e = getNumValNums(); i != e; ++i) {
+    if (InstDefiningValue[i] == ~2U) continue;  // tombstone value #
+    if (i != (unsigned)LHSValNoAssignments[i]) {
+      MustMapCurValNos = true;
+      break;
+    }
   }
   
-  const LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-OtherOffs);
-  const LiveRange *DestLR = getLiveRangeContaining(CopyIdx-ThisOffs);
-  assert(SourceLR && DestLR && "Not joining due to a copy?");
-  unsigned MergedSrcValIdx = SourceLR->ValId;
-  unsigned MergedDstValIdx = DestLR->ValId;
-
-  // Join the ranges of other into the ranges of this interval.
-  std::map<unsigned, unsigned> Dst2SrcIdxMap;
+  // If we have to apply a mapping to our base interval assignment, rewrite it
+  // now.
+  if (MustMapCurValNos) {
+    // Map the first live range.
+    iterator OutIt = begin();
+    OutIt->ValId = LHSValNoAssignments[OutIt->ValId];
+    ++OutIt;
+    for (iterator I = OutIt, E = end(); I != E; ++I) {
+      OutIt->ValId = LHSValNoAssignments[I->ValId];
+      
+      // If this live range has the same value # as its immediate predecessor,
+      // and if they are neighbors, remove one LiveRange.  This happens when we
+      // have [0,3:0)[4,7:1) and map 0/1 onto the same value #.
+      if (OutIt->ValId == (OutIt-1)->ValId && (OutIt-1)->end == OutIt->start) {
+        (OutIt-1)->end = OutIt->end;
+      } else {
+        if (I != OutIt) {
+          OutIt->start = I->start;
+          OutIt->end = I->end;
+        }
+        
+        // Didn't merge, on to the next one.
+        ++OutIt;
+      }
+    }
+    
+    // If we merge some live ranges, chop off the end.
+    ranges.erase(OutIt, end());
+  }
+  
+  // Okay, now insert the RHS live ranges into the LHS.
   iterator InsertPos = begin();
   for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) {
     // Map the ValId in the other live range to the current live range.
-    if (I->ValId == MergedSrcValIdx)
-      I->ValId = MergedDstValIdx;
-    else {
-      unsigned &NV = Dst2SrcIdxMap[I->ValId];
-      if (NV == 0) NV = getNextValue(Other.getInstForValNum(I->ValId));
-      I->ValId = NV;
-    }
-
+    I->ValId = RHSValNoAssignments[I->ValId];
     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];
-  }
-  
+
+  InstDefiningValue.clear();
+  InstDefiningValue.append(NewInstDefiningValue.begin(), 
+                           NewInstDefiningValue.end());
   weight += Other.weight;
 }
 
@@ -511,10 +441,9 @@
   // Now that V1 is dead, remove it.  If it is the largest value number, just
   // nuke it (and any other deleted values neighboring it), otherwise mark it as
   // ~1U so it can be nuked later.
-  if (V1 == NumValues-1) {
+  if (V1 == getNumValNums()-1) {
     do {
       InstDefiningValue.pop_back();
-      --NumValues;
     } while (InstDefiningValue.back() == ~1U);
   } else {
     InstDefiningValue[V1] = ~1U;
@@ -548,9 +477,9 @@
   }
   
   // Print value number info.
-  if (NumValues) {
+  if (getNumValNums()) {
     OS << "  ";
-    for (unsigned i = 0; i != NumValues; ++i) {
+    for (unsigned i = 0; i != getNumValNums(); ++i) {
       if (i) OS << " ";
       OS << i << "@";
       if (InstDefiningValue[i] == ~0U) {
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 4f34881..a26feb3 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -629,8 +629,9 @@
 /// This returns true if an interval was modified.
 ///
 bool LiveIntervals::AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
-                                         MachineInstr *CopyMI,
-                                         unsigned CopyIdx) {
+                                         MachineInstr *CopyMI) {
+  unsigned CopyIdx = getDefIndex(getInstructionIndex(CopyMI));
+
   // 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);
@@ -768,34 +769,22 @@
         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.
+  // Okay, attempt to join these two intervals.  On failure, this returns false.
+  // Otherwise, if one of the intervals being joined is a physreg, this method
+  // always canonicalizes DestInt to be it.  The output "SrcInt" will not have
+  // been modified, so we can use this information below to update aliases.
+  if (!JoinIntervals(DestInt, SrcInt)) {
+    // Coallescing failed.
+    
+    // If we can eliminate the copy without merging the live ranges, do so now.
+    if (AdjustCopiesBackFrom(SrcInt, DestInt, CopyMI))
+      return true;
 
-  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 (!Joinable) {
+    // Otherwise, we are unable to join the intervals.
     DEBUG(std::cerr << "Interference!\n");
     return false;
   }
 
-  // Okay, we can join these two intervals.  If one of the intervals being
-  // joined is a physreg, this method always canonicalizes DestInt to be it.
-  // The output "SrcInt" will not have been modified.
-  DestInt.join(SrcInt, MIDefIdx);
-
   bool Swapped = SrcReg == DestInt.reg;
   if (Swapped)
     std::swap(SrcReg, DstReg);
@@ -823,6 +812,182 @@
   return true;
 }
 
+/// ComputeUltimateVN - Assuming we are going to join two live intervals,
+/// compute what the resultant value numbers for each value in the input two
+/// ranges will be.  This is complicated by copies between the two which can
+/// and will commonly cause multiple value numbers to be merged into one.
+///
+/// VN is the value number that we're trying to resolve.  InstDefiningValue
+/// keeps track of the new InstDefiningValue assignment for the result
+/// LiveInterval.  ThisFromOther/OtherFromThis are sets that keep track of
+/// whether a value in this or other is a copy from the opposite set.
+/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have
+/// already been assigned.
+///
+/// ThisFromOther[x] - If x is defined as a copy from the other interval, this
+/// contains the value number the copy is from.
+///
+static unsigned ComputeUltimateVN(unsigned VN,
+                                  SmallVector<unsigned, 16> &InstDefiningValue,
+                                  SmallVector<int, 16> &ThisFromOther,
+                                  SmallVector<int, 16> &OtherFromThis,
+                                  SmallVector<int, 16> &ThisValNoAssignments,
+                                  SmallVector<int, 16> &OtherValNoAssignments,
+                                  LiveInterval &ThisLI, LiveInterval &OtherLI) {
+  // If the VN has already been computed, just return it.
+  if (ThisValNoAssignments[VN] >= 0)
+    return ThisValNoAssignments[VN];
+  assert(ThisValNoAssignments[VN] != -2 && "FIXME: Cyclic case, handle it!");
+  
+  // If this val is not a copy from the other val, then it must be a new value
+  // number in the destination.
+  int OtherValNo = ThisFromOther[VN];
+  if (OtherValNo == -1) {
+    InstDefiningValue.push_back(ThisLI.getInstForValNum(VN));
+    return ThisValNoAssignments[VN] = InstDefiningValue.size()-1;
+  }
+
+  // Otherwise, this *is* a copy from the RHS.  Mark this value number as
+  // currently being computed, then ask what the ultimate value # of the other
+  // value is.
+  ThisValNoAssignments[VN] = -2;
+  unsigned UltimateVN =
+    ComputeUltimateVN(OtherValNo, InstDefiningValue,
+                      OtherFromThis, ThisFromOther,
+                      OtherValNoAssignments, ThisValNoAssignments,
+                      OtherLI, ThisLI);
+  return ThisValNoAssignments[VN] = UltimateVN;
+}
+
+
+/// JoinIntervals - Attempt to join these two intervals.  On failure, this
+/// returns false.  Otherwise, if one of the intervals being joined is a
+/// physreg, this method always canonicalizes LHS to be it.  The output
+/// "RHS" will not have been modified, so we can use this information
+/// below to update aliases.
+bool LiveIntervals::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS) {
+  // Loop over the value numbers of the LHS, seeing if any are defined from the
+  // RHS.
+  SmallVector<int, 16> LHSValsDefinedFromRHS;
+  LHSValsDefinedFromRHS.resize(LHS.getNumValNums(), -1);
+  for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
+    unsigned ValInst = LHS.getInstForValNum(VN);
+    if (ValInst == ~0U || ValInst == ~1U)
+      continue;
+    
+    // If the instruction defining the LHS's value is a copy.
+    MachineInstr *ValInstMI = getInstructionFromIndex(ValInst);
+    
+    // If the value number is not defined by a copy instruction, ignore it.
+    unsigned SrcReg, DstReg;
+    if (!tii_->isMoveInstr(*ValInstMI, SrcReg, DstReg))
+      continue;
+    
+    // DstReg is known to be a register in the LHS interval.  If the src is from
+    // the RHS interval, we can use its value #.
+    if (rep(SrcReg) != RHS.reg)
+      continue;
+    
+    // Figure out the value # from the RHS.
+    LHSValsDefinedFromRHS[VN] = RHS.getLiveRangeContaining(ValInst-1)->ValId;
+  }
+  
+  // Loop over the value numbers of the RHS, seeing if any are defined from the
+  // LHS.
+  SmallVector<int, 16> RHSValsDefinedFromLHS;
+  RHSValsDefinedFromLHS.resize(RHS.getNumValNums(), -1);
+  for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
+    unsigned ValInst = RHS.getInstForValNum(VN);
+    if (ValInst == ~0U || ValInst == ~1U)
+      continue;
+    
+    // If the instruction defining the RHS's value is a copy.
+    MachineInstr *ValInstMI = getInstructionFromIndex(ValInst);
+    
+    // If the value number is not defined by a copy instruction, ignore it.
+    unsigned SrcReg, DstReg;
+    if (!tii_->isMoveInstr(*ValInstMI, SrcReg, DstReg))
+      continue;
+    
+    // DstReg is known to be a register in the RHS interval.  If the src is from
+    // the LHS interval, we can use its value #.
+    if (rep(SrcReg) != LHS.reg)
+      continue;
+    
+    // Figure out the value # from the LHS.
+    RHSValsDefinedFromLHS[VN] = LHS.getLiveRangeContaining(ValInst-1)->ValId;
+  }
+  
+  // Now that we know the value mapping, compute the final value assignment,
+  // assuming that the live ranges can be coallesced.
+  SmallVector<int, 16> LHSValNoAssignments;
+  SmallVector<int, 16> RHSValNoAssignments;
+  SmallVector<unsigned, 16> InstDefiningValue;
+  LHSValNoAssignments.resize(LHS.getNumValNums(), -1);
+  RHSValNoAssignments.resize(RHS.getNumValNums(), -1);
+  
+  // Compute ultimate value numbers for the LHS and RHS values.
+  for (unsigned VN = 0, e = LHS.getNumValNums(); VN != e; ++VN) {
+    if (LHS.getInstForValNum(VN) == ~2U) continue;
+    ComputeUltimateVN(VN, InstDefiningValue,
+                      LHSValsDefinedFromRHS, RHSValsDefinedFromLHS,
+                      LHSValNoAssignments, RHSValNoAssignments, LHS, RHS);
+  }
+  for (unsigned VN = 0, e = RHS.getNumValNums(); VN != e; ++VN) {
+    if (RHS.getInstForValNum(VN) == ~2U) continue;
+    ComputeUltimateVN(VN, InstDefiningValue,
+                      RHSValsDefinedFromLHS, LHSValsDefinedFromRHS,
+                      RHSValNoAssignments, LHSValNoAssignments, RHS, LHS);
+  }
+  
+  // Armed with the mappings of LHS/RHS values to ultimate values, walk the
+  // interval lists to see if these intervals are coallescable.
+  LiveInterval::const_iterator I = LHS.begin();
+  LiveInterval::const_iterator IE = LHS.end();
+  LiveInterval::const_iterator J = RHS.begin();
+  LiveInterval::const_iterator JE = RHS.end();
+  
+  // Skip ahead until the first place of potential sharing.
+  if (I->start < J->start) {
+    I = std::upper_bound(I, IE, J->start);
+    if (I != LHS.begin()) --I;
+  } else if (J->start < I->start) {
+    J = std::upper_bound(J, JE, I->start);
+    if (J != RHS.begin()) --J;
+  }
+  
+  while (1) {
+    // Determine if these two live ranges overlap.
+    bool Overlaps;
+    if (I->start < J->start) {
+      Overlaps = I->end > J->start;
+    } else {
+      Overlaps = J->end > I->start;
+    }
+
+    // If so, check value # info to determine if they are really different.
+    if (Overlaps) {
+      // If the live range overlap will map to the same value number in the
+      // result liverange, we can still coallesce them.  If not, we can't.
+      if (LHSValNoAssignments[I->ValId] != RHSValNoAssignments[J->ValId])
+        return false;
+    }
+    
+    if (I->end < J->end) {
+      ++I;
+      if (I == IE) break;
+    } else {
+      ++J;
+      if (J == JE) break;
+    }
+  }
+
+  // If we get here, we know that we can coallesce the live ranges.  Ask the
+  // intervals to coallesce themselves now.
+  LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0],
+           InstDefiningValue);
+  return true;
+}
 
 
 namespace {