X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveInterval.cpp;h=40f8cd4388d89bc65bc89358e06d8d74e4b481e0;hb=b0000c376cf13ed63306622ab9642cfae49f074a;hp=e1b8cf98019e8558c12717d1d9595b49785cbc64;hpb=294e6524916aecd874dddeede4cc074d31f5f59f;p=oota-llvm.git

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index e1b8cf98019..40f8cd4388d 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -22,7 +22,7 @@
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Streams.h"
-#include "llvm/Target/MRegisterInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
 #include <algorithm>
 #include <ostream>
 using namespace llvm;
@@ -44,6 +44,27 @@ bool LiveInterval::liveAt(unsigned I) const {
   return r->contains(I);
 }
 
+// liveBeforeAndAt - Check if the interval is live at the index and the index
+// just before it. If index is liveAt, check if it starts a new live range.
+// If it does, then check if the previous live range ends at index-1.
+bool LiveInterval::liveBeforeAndAt(unsigned I) const {
+  Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
+
+  if (r == ranges.begin())
+    return false;
+
+  --r;
+  if (!r->contains(I))
+    return false;
+  if (I != r->start)
+    return true;
+  // I is the start of a live range. Check if the previous live range ends
+  // at I-1.
+  if (r == ranges.begin())
+    return false;
+  return r->end == I;
+}
+
 // overlaps - Return true if the intersection of the two live intervals is
 // not empty.
 //
@@ -196,7 +217,7 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
 
   // Otherwise, if this range ends in the middle of, or right next to, another
   // interval, merge it into that interval.
-  if (it != ranges.end())
+  if (it != ranges.end()) {
     if (LR.valno == it->valno) {
       if (it->start <= End) {
         it = extendIntervalStartTo(it, Start);
@@ -216,16 +237,28 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
       assert(it->start >= End &&
              "Cannot overlap two LiveRanges with differing ValID's");
     }
+  }
 
   // Otherwise, this is just a new range that doesn't interact with anything.
   // Insert it.
   return ranges.insert(it, LR);
 }
 
+/// isInOneLiveRange - Return true if the range specified is entirely in the
+/// a single LiveRange of the live interval.
+bool LiveInterval::isInOneLiveRange(unsigned Start, unsigned End) {
+  Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
+  if (I == ranges.begin())
+    return false;
+  --I;
+  return I->contains(Start) && I->contains(End-1);
+}
+
 
 /// removeRange - Remove the specified range from this interval.  Note that
-/// the range must already be in this interval in its entirety.
-void LiveInterval::removeRange(unsigned Start, unsigned End) {
+/// the range must be in a single LiveRange in its entirety.
+void LiveInterval::removeRange(unsigned Start, unsigned End,
+                               bool RemoveDeadValNo) {
   // Find the LiveRange containing this span.
   Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
   assert(I != ranges.begin() && "Range is not in interval!");
@@ -234,9 +267,34 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) {
          "Range is not entirely in interval!");
 
   // If the span we are removing is at the start of the LiveRange, adjust it.
+  VNInfo *ValNo = I->valno;
   if (I->start == Start) {
     if (I->end == End) {
       removeKills(I->valno, Start, End);
+      if (RemoveDeadValNo) {
+        // Check if val# is dead.
+        bool isDead = true;
+        for (const_iterator II = begin(), EE = end(); II != EE; ++II)
+          if (II != I && II->valno == ValNo) {
+            isDead = false;
+            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 {
+              VNInfo *VNI = valnos.back();
+              valnos.pop_back();
+              VNI->~VNInfo();
+            } while (!valnos.empty() && valnos.back()->def == ~1U);
+          } else {
+            ValNo->def = ~1U;
+          }
+        }
+      }
+
       ranges.erase(I);  // Removed the whole LiveRange.
     } else
       I->start = End;
@@ -246,7 +304,7 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) {
   // Otherwise if the span we are removing is at the end of the LiveRange,
   // adjust the other way.
   if (I->end == End) {
-    removeKills(I->valno, Start, End);
+    removeKills(ValNo, Start, End);
     I->end = Start;
     return;
   }
@@ -256,9 +314,34 @@ void LiveInterval::removeRange(unsigned Start, unsigned End) {
   I->end = Start;   // Trim the old interval.
 
   // Insert the new one.
-  ranges.insert(next(I), LiveRange(End, OldEnd, I->valno));
+  ranges.insert(next(I), LiveRange(End, OldEnd, ValNo));
 }
 
+/// removeValNo - Remove all the ranges defined by the specified value#.
+/// Also remove the value# from value# list.
+void LiveInterval::removeValNo(VNInfo *ValNo) {
+  if (empty()) return;
+  Ranges::iterator I = ranges.end();
+  Ranges::iterator E = ranges.begin();
+  do {
+    --I;
+    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 {
+      VNInfo *VNI = valnos.back();
+      valnos.pop_back();
+      VNI->~VNInfo();
+    } while (!valnos.empty() && valnos.back()->def == ~1U);
+  } else {
+    ValNo->def = ~1U;
+  }
+}
+ 
 /// getLiveRangeContaining - Return the live range that contains the
 /// specified index, or null if there is none.
 LiveInterval::const_iterator 
@@ -285,6 +368,20 @@ LiveInterval::FindLiveRangeContaining(unsigned Idx) {
   return end();
 }
 
+/// findDefinedVNInfo - Find the VNInfo that's defined at the specified index
+/// (register interval) or defined by the specified register (stack inteval).
+VNInfo *LiveInterval::findDefinedVNInfo(unsigned DefIdxOrReg) const {
+  VNInfo *VNI = NULL;
+  for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end();
+       i != e; ++i)
+    if ((*i)->def == DefIdxOrReg) {
+      VNI = *i;
+      break;
+    }
+  return VNI;
+}
+
+
 /// 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.
@@ -445,7 +542,7 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
             VNInfo *VNI = valnos.back();
             valnos.pop_back();
             VNI->~VNInfo();
-          } while (valnos.back()->def == ~1U);
+          } while (!valnos.empty() && valnos.back()->def == ~1U);
         } else {
           V1->def = ~1U;
         }
@@ -460,7 +557,7 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
 /// used with an unknown definition value.
 void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
                                         BumpPtrAllocator &VNInfoAllocator) {
-  if (Clobbers.begin() == Clobbers.end()) return;
+  if (Clobbers.empty()) return;
   
   // Find a value # to use for the clobber ranges.  If there is already a value#
   // for unknown values, use it.
@@ -494,7 +591,7 @@ void LiveInterval::MergeInClobberRanges(const LiveInterval &Clobbers,
 /// 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(VNInfo *V1, VNInfo *V2) {
+VNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
   assert(V1 != V2 && "Identical value#'s are always equivalent!");
 
   // This code actually merges the (numerically) larger value number into the
@@ -555,6 +652,8 @@ void LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
   } else {
     V1->def = ~1U;
   }
+  
+  return V2;
 }
 
 void LiveInterval::Copy(const LiveInterval &RHS,
@@ -589,16 +688,19 @@ void LiveRange::dump() const {
   cerr << *this << "\n";
 }
 
-void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
-  if (MRI && MRegisterInfo::isPhysicalRegister(reg))
-    OS << MRI->getName(reg);
+void LiveInterval::print(std::ostream &OS,
+                         const TargetRegisterInfo *TRI) const {
+  if (isStackSlot())
+    OS << "SS#" << getStackSlotIndex();
+  else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg))
+    OS << TRI->getName(reg);
   else
     OS << "%reg" << reg;
 
   OS << ',' << weight;
 
   if (empty())
-    OS << "EMPTY";
+    OS << " EMPTY";
   else {
     OS << " = ";
     for (LiveInterval::Ranges::const_iterator I = ranges.begin(),
@@ -623,15 +725,18 @@ void LiveInterval::print(std::ostream &OS, const MRegisterInfo *MRI) const {
         else
           OS << vni->def;
         unsigned ee = vni->kills.size();
-        if (ee) {
+        if (ee || vni->hasPHIKill) {
           OS << "-(";
           for (unsigned j = 0; j != ee; ++j) {
             OS << vni->kills[j];
             if (j != ee-1)
               OS << " ";
           }
-          if (vni->hasPHIKill)
-            OS << " phi";
+          if (vni->hasPHIKill) {
+            if (ee)
+              OS << " ";
+            OS << "phi";
+          }
           OS << ")";
         }
       }