Typo.

[oota-llvm.git] / lib / CodeGen / LiveInterval.cpp

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 4d38f0adcfa241abd7a17a8015e3dd07540a618c..5b855aa19383d499be09d71d0599ed5c2e9947b1 100644 (file)
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -19,6 +19,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/LiveInterval.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Streams.h"
 #include "llvm/Target/MRegisterInfo.h"
@@ -285,8 +286,8 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) {
 /// 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, 
+void LiveInterval::join(LiveInterval &Other, const int *LHSValNoAssignments,
+                        const int *RHSValNoAssignments, 
                         SmallVector<VNInfo*, 16> &NewVNInfo) {
   // Determine if any of our live range values are mapped.  This is uncommon, so
   // we want to avoid the interval scan if not. 
@@ -383,6 +384,75 @@ void LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS,
 }
 
 
+/// MergeValueInAsValue - Merge all of the live ranges of a specific val#
+/// in RHS into this live interval as the specified value number.
+/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the
+/// current interval, it will replace the value numbers of the overlaped
+/// live ranges with the specified value number.
+void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
+                                     const VNInfo *RHSValNo, VNInfo *LHSValNo) {
+  SmallVector<VNInfo*, 4> ReplacedValNos;
+  iterator IP = begin();
+  for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) {
+    if (I->valno != RHSValNo)
+      continue;
+    unsigned Start = I->start, End = I->end;
+    IP = std::upper_bound(IP, end(), Start);
+    // If the start of this range overlaps with an existing liverange, trim it.
+    if (IP != begin() && IP[-1].end > Start) {
+      if (IP->valno != LHSValNo) {
+        ReplacedValNos.push_back(IP->valno);
+        IP->valno = LHSValNo; // Update val#.
+      }
+      Start = IP[-1].end;
+      // Trimmed away the whole range?
+      if (Start >= End) continue;
+    }
+    // If the end of this range overlaps with an existing liverange, trim it.
+    if (IP != end() && End > IP->start) {
+      if (IP->valno != LHSValNo) {
+        ReplacedValNos.push_back(IP->valno);
+        IP->valno = LHSValNo;  // Update val#.
+      }
+      End = IP->start;
+      // If this trimmed away the whole range, ignore it.
+      if (Start == End) continue;
+    }
+    
+    // Map the valno in the other live range to the current live range.
+    IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP);
+  }
+
+
+  SmallSet<VNInfo*, 4> Seen;
+  for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) {
+    VNInfo *V1 = ReplacedValNos[i];
+    if (Seen.insert(V1)) {
+      bool isDead = true;
+      for (const_iterator I = begin(), E = end(); I != E; ++I)
+        if (I->valno == V1) {
+          isDead = false;
+          break;
+        }          
+      if (isDead) {
+        // 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->id == getNumValNums()-1) {
+          do {
+            VNInfo *VNI = valnos.back();
+            valnos.pop_back();
+            VNI->~VNInfo();
+          } while (valnos.back()->def == ~1U);
+        } else {
+          V1->def = ~1U;
+        }
+      }
+    }
+  }
+}
+
+
 /// MergeInClobberRanges - For any live ranges that are not defined in the
 /// current interval, but are defined in the Clobbers interval, mark them
 /// used with an unknown definition value.
@@ -476,13 +546,32 @@ void LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
   // ~1U so it can be nuked later.
   if (V1->id == getNumValNums()-1) {
     do {
+      VNInfo *VNI = valnos.back();
       valnos.pop_back();
+      VNI->~VNInfo();
     } while (valnos.back()->def == ~1U);
   } else {
     V1->def = ~1U;
   }
 }
 
+void LiveInterval::Copy(const LiveInterval &RHS,
+                        BumpPtrAllocator &VNInfoAllocator) {
+  ranges.clear();
+  valnos.clear();
+  preference = RHS.preference;
+  weight = RHS.weight;
+  for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) {
+    const VNInfo *VNI = RHS.getValNumInfo(i);
+    VNInfo *NewVNI = getNextValue(~0U, 0, VNInfoAllocator);
+    copyValNumInfo(NewVNI, VNI);
+  }
+  for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) {
+    const LiveRange &LR = RHS.ranges[i];
+    addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id)));
+  }
+}
+
 unsigned LiveInterval::getSize() const {
   unsigned Sum = 0;
   for (const_iterator I = begin(), E = end(); I != E; ++I)