Tidy some #includes and forward-declarations, and move the C binding code

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

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 34b58515b68ccd6c082e9582a6cf754c1f1c5a97..f4c06b203cbcba3bce67ff1d446afd0f740ab220 100644 (file)
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -119,6 +119,7 @@ bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const {
 //
 bool LiveInterval::overlapsFrom(const LiveInterval& other,
                                 const_iterator StartPos) const {
+  assert(!empty() && "empty interval");
   const_iterator i = begin();
   const_iterator ie = end();
   const_iterator j = StartPos;
@@ -161,16 +162,37 @@ bool LiveInterval::overlapsFrom(const LiveInterval& other,
 /// by [Start, End).
 bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
   assert(Start < End && "Invalid range");
-  const_iterator I  = begin();
-  const_iterator E  = end();
-  const_iterator si = std::upper_bound(I, E, Start);
-  const_iterator ei = std::upper_bound(I, E, End);
-  if (si != ei)
-    return true;
-  if (si == I)
-    return false;
-  --si;
-  return si->contains(Start);
+  const_iterator I = std::lower_bound(begin(), end(), End);
+  return I != begin() && (--I)->end > Start;
+}
+
+
+/// ValNo 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.
+void LiveInterval::markValNoForDeletion(VNInfo *ValNo) {
+  if (ValNo->id == getNumValNums()-1) {
+    do {
+      valnos.pop_back();
+    } while (!valnos.empty() && valnos.back()->isUnused());
+  } else {
+    ValNo->setIsUnused(true);
+  }
+}
+
+/// RenumberValues - Renumber all values in order of appearance and delete the
+/// remaining unused values.
+void LiveInterval::RenumberValues() {
+  SmallPtrSet<VNInfo*, 8> Seen;
+  valnos.clear();
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
+    VNInfo *VNI = I->valno;
+    if (!Seen.insert(VNI))
+      continue;
+    assert(!VNI->isUnused() && "Unused valno used by live range");
+    VNI->id = (unsigned)valnos.size();
+    valnos.push_back(VNI);
+  }
 }
 
 /// extendIntervalEndTo - This method is used when we want to extend the range
@@ -180,10 +202,9 @@ bool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const {
 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
   assert(I != ranges.end() && "Not a valid interval!");
   VNInfo *ValNo = I->valno;
-  SlotIndex OldEnd = I->end;
 
   // Search for the first interval that we can't merge with.
-  Ranges::iterator MergeTo = next(I);
+  Ranges::iterator MergeTo = llvm::next(I);
   for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
     assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
   }
@@ -192,11 +213,11 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
   I->end = std::max(NewEnd, prior(MergeTo)->end);
 
   // Erase any dead ranges.
-  ranges.erase(next(I), MergeTo);
+  ranges.erase(llvm::next(I), MergeTo);
 
   // If the newly formed range now touches the range after it and if they have
   // the same value number, merge the two ranges into one range.
-  Ranges::iterator Next = next(I);
+  Ranges::iterator Next = llvm::next(I);
   if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) {
     I->end = Next->end;
     ranges.erase(Next);
@@ -235,7 +256,7 @@ LiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) {
     MergeTo->end = I->end;
   }
 
-  ranges.erase(next(MergeTo), next(I));
+  ranges.erase(llvm::next(MergeTo), llvm::next(I));
   return MergeTo;
 }
 
@@ -322,16 +343,8 @@ void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
             break;
           }
         if (isDead) {
-          // Now that ValNo 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 (ValNo->id == getNumValNums()-1) {
-            do {
-              valnos.pop_back();
-            } while (!valnos.empty() && valnos.back()->isUnused());
-          } else {
-            ValNo->setIsUnused(true);
-          }
+          // Now that ValNo is dead, remove it.
+          markValNoForDeletion(ValNo);
         }
       }
 
@@ -353,7 +366,7 @@ void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
   I->end = Start;   // Trim the old interval.
 
   // Insert the new one.
-  ranges.insert(next(I), LiveRange(End, OldEnd, ValNo));
+  ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo));
 }
 
 /// removeValNo - Remove all the ranges defined by the specified value#.
@@ -367,16 +380,8 @@ void LiveInterval::removeValNo(VNInfo *ValNo) {
     if (I->valno == ValNo)
       ranges.erase(I);
   } while (I != E);
-  // Now that ValNo 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 (ValNo->id == getNumValNums()-1) {
-    do {
-      valnos.pop_back();
-    } while (!valnos.empty() && valnos.back()->isUnused());
-  } else {
-    ValNo->setIsUnused(true);
-  }
+  // Now that ValNo is dead, remove it.
+  markValNoForDeletion(ValNo);
 }
 
 /// getLiveRangeContaining - Return the live range that contains the
@@ -594,16 +599,8 @@ void LiveInterval::MergeValueInAsValue(
           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 {
-            valnos.pop_back();
-          } while (!valnos.empty() && valnos.back()->isUnused());
-        } else {
-          V1->setIsUnused(true);
-        }
+        // Now that V1 is dead, remove it.
+        markValNoForDeletion(V1);
       }
     }
   }
@@ -761,16 +758,8 @@ VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
     }
   }
   
-  // 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 {
-      valnos.pop_back();
-    } while (valnos.back()->isUnused());
-  } else {
-    V1->setIsUnused(true);
-  }
+  // Now that V1 is dead, remove it.
+  markValNoForDeletion(V1);
   
   return V2;
 }
@@ -869,6 +858,10 @@ void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
           OS << "?";
         else
           OS << vni->def;
+        if (vni->hasPHIKill())
+          OS << "-phikill";
+        if (vni->hasRedefByEC())
+          OS << "-ec";
       }
     }
   }