2 files changed, 40 insertions, 53 deletions

diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index bb0026cdc1..149def33bd 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -317,7 +317,6 @@ void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
   Edit = &LRE;
   SpillMode = SM;
   OpenIdx = 0;
-  OverlappedComplement.clear();
   RegAssign.clear();
   Values.clear();
 
@@ -355,7 +354,8 @@ VNInfo *SplitEditor::defValue(unsigned RegIdx,
 
   // Use insert for lookup, so we can add missing values with a second lookup.
   std::pair<ValueMap::iterator, bool> InsP =
-    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
+    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id),
+                                 ValueForcePair(VNI, false)));
 
   // This was the first time (RegIdx, ParentVNI) was mapped.
   // Keep it as a simple def without any liveness.
@@ -363,11 +363,11 @@ VNInfo *SplitEditor::defValue(unsigned RegIdx,
     return VNI;
 
   // If the previous value was a simple mapping, add liveness for it now.
-  if (VNInfo *OldVNI = InsP.first->second) {
+  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
     SlotIndex Def = OldVNI->def;
     LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
-    // No longer a simple mapping.
-    InsP.first->second = 0;
+    // No longer a simple mapping.  Switch to a complex, non-forced mapping.
+    InsP.first->second = ValueForcePair();
   }
 
   // This is a complex mapping, add liveness for VNI
@@ -377,29 +377,24 @@ VNInfo *SplitEditor::defValue(unsigned RegIdx,
   return VNI;
 }
 
-void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
+void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
   assert(ParentVNI && "Mapping  NULL value");
-  VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
+  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
+  VNInfo *VNI = VFP.getPointer();
 
-  // ParentVNI was either unmapped or already complex mapped. Either way.
-  if (!VNI)
+  // ParentVNI was either unmapped or already complex mapped. Either way, just
+  // set the force bit.
+  if (!VNI) {
+    VFP.setInt(true);
     return;
+  }
 
   // This was previously a single mapping. Make sure the old def is represented
   // by a trivial live range.
   SlotIndex Def = VNI->def;
   Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
-  VNI = 0;
-}
-
-void SplitEditor::markOverlappedComplement(const VNInfo *ParentVNI) {
-  if (OverlappedComplement.insert(ParentVNI))
-    markComplexMapped(0, ParentVNI);
-}
-
-bool SplitEditor::needsRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
-  return (RegIdx == 0 && OverlappedComplement.count(ParentVNI)) ||
-    Edit->didRematerialize(ParentVNI);
+  // Mark as complex mapped, forced.
+  VFP = ValueForcePair(0, true);
 }
 
 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
@@ -586,7 +581,7 @@ void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
 
   // The complement interval will be extended as needed by LRCalc.extend().
   if (ParentVNI)
-    markOverlappedComplement(ParentVNI);
+    forceRecompute(0, ParentVNI);
   DEBUG(dbgs() << "    overlapIntv [" << Start << ';' << End << "):");
   RegAssign.insert(Start, End, OpenIdx);
   DEBUG(dump());
@@ -631,7 +626,7 @@ void SplitEditor::removeBackCopies(SmallVectorImpl<VNInfo*> &Copies) {
     unsigned RegIdx = AssignI.value();
     if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) {
       DEBUG(dbgs() << "  cannot find simple kill of RegIdx " << RegIdx << '\n');
-      markComplexMapped(RegIdx, Edit->getParent().getVNInfoAt(Def));
+      forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def));
     } else {
       SlotIndex Kill = LIS.getInstructionIndex(MBBI).getDefIndex();
       DEBUG(dbgs() << "  move kill to " << Kill << '\t' << *MBBI);
@@ -676,7 +671,7 @@ void SplitEditor::hoistCopiesForSize() {
     }
     // Skip the singly mapped values.  There is nothing to gain from hoisting a
     // single back-copy.
-    if (Values.lookup(std::make_pair(0, ParentVNI->id))) {
+    if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) {
       DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n');
       continue;
     }
@@ -729,7 +724,7 @@ void SplitEditor::hoistCopiesForSize() {
     if (!Dom.first || Dom.second == VNI->def)
       continue;
     BackCopies.push_back(VNI);
-    markOverlappedComplement(ParentVNI);
+    forceRecompute(0, ParentVNI);
   }
   removeBackCopies(BackCopies);
 }
@@ -768,17 +763,17 @@ bool SplitEditor::transferValues() {
       LiveInterval *LI = Edit->get(RegIdx);
 
       // Check for a simply defined value that can be blitted directly.
-      if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) {
+      ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id));
+      if (VNInfo *VNI = VFP.getPointer()) {
         DEBUG(dbgs() << ':' << VNI->id);
         LI->addRange(LiveRange(Start, End, VNI));
         Start = End;
         continue;
       }
 
-      // Skip rematerialized values, we need to use LRCalc.extend() and
-      // extendPHIKillRanges() to completely recompute the live ranges.
-      if (needsRecompute(RegIdx, ParentVNI)) {
-        DEBUG(dbgs() << "(remat)");
+      // Skip values with forced recomputation.
+      if (VFP.getInt()) {
+        DEBUG(dbgs() << "(recalc)");
         Skipped = true;
         Start = End;
         continue;
@@ -967,11 +962,11 @@ void SplitEditor::finish(SmallVectorImpl<unsigned> *LRMap) {
     VNI->setIsPHIDef(ParentVNI->isPHIDef());
     VNI->setCopy(ParentVNI->getCopy());
 
-    // Mark rematted values as complex everywhere to force liveness computation.
+    // Force rematted values to be recomputed everywhere.
     // The new live ranges may be truncated.
     if (Edit->didRematerialize(ParentVNI))
       for (unsigned i = 0, e = Edit->size(); i != e; ++i)
-        markComplexMapped(i, ParentVNI);
+        forceRecompute(i, ParentVNI);
   }
 
   // Hoist back-copies to the complement interval when in spill mode.
diff --git a/lib/CodeGen/SplitKit.h b/lib/CodeGen/SplitKit.h
index 67e80faefa..5a294e5055 100644
--- a/lib/CodeGen/SplitKit.h
+++ b/lib/CodeGen/SplitKit.h
@@ -250,10 +250,6 @@ private:
   /// The current spill mode, selected by reset().
   ComplementSpillMode SpillMode;
 
-  /// Parent interval values where the complement interval may be overlapping
-  /// other intervals.
-  SmallPtrSet<const VNInfo*, 8> OverlappedComplement;
-
   typedef IntervalMap<SlotIndex, unsigned> RegAssignMap;
 
   /// Allocator for the interval map. This will eventually be shared with
@@ -265,15 +261,20 @@ private:
   /// Idx.
   RegAssignMap RegAssign;
 
-  typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap;
+  typedef PointerIntPair<VNInfo*, 1> ValueForcePair;
+  typedef DenseMap<std::pair<unsigned, unsigned>, ValueForcePair> ValueMap;
 
   /// Values - keep track of the mapping from parent values to values in the new
   /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains:
   ///
   /// 1. No entry - the value is not mapped to Edit.get(RegIdx).
-  /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx).
-  ///    Each value is represented by a minimal live range at its def.
-  /// 3. A non-null VNInfo - the value is mapped to a single new value.
+  /// 2. (Null, false) - the value is mapped to multiple values in
+  ///    Edit.get(RegIdx).  Each value is represented by a minimal live range at
+  ///    its def.  The full live range can be inferred exactly from the range
+  ///    of RegIdx in RegAssign.
+  /// 3. (Null, true).  As above, but the ranges in RegAssign are too large, and
+  ///    the live range must be recomputed using LiveRangeCalc::extend().
+  /// 4. (VNI, false) The value is mapped to a single new value.
   ///    The new value has no live ranges anywhere.
   ValueMap Values;
 
@@ -296,20 +297,11 @@ private:
   /// Return the new LI value.
   VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx);
 
-  /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless
-  /// of the number of defs.
-  void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI);
-
-  /// markOverlappedComplement - Mark ParentVNI as being overlapped in the
-  /// complement interval.  The complement interval may overlap other intervals
-  /// after overlapIntv has been called, or when in spill mode.
-  void markOverlappedComplement(const VNInfo *ParentVNI);
-
-  /// needsRecompute - Returns true if the live range of ParentVNI needs to be
-  /// recomputed in RegIdx using LiveRangeCalc::extend.  This is the case if
-  /// the value has been rematerialized, or when back-copies have been hoisted
-  /// in spill mode.
-  bool needsRecompute(unsigned RegIdx, const VNInfo *ParentVNI);
+  /// forceRecompute - Force the live range of ParentVNI in RegIdx to be
+  /// recomputed by LiveRangeCalc::extend regardless of the number of defs.
+  /// This is used for values whose live range doesn't match RegAssign exactly.
+  /// They could have rematerialized, or back-copies may have been moved.
+  void forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI);
 
   /// defFromParent - Define Reg from ParentVNI at UseIdx using either
   /// rematerialization or a COPY from parent. Return the new value.