X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveInterval.cpp;h=0f5de9257a71959db4bb67e3743a9d0638c28692;hb=05c397d52a145c8844790d6491c4c51d4bbfed7c;hp=b20a87ea0a8c2fd0c5d95e0866ed688413b91cd7;hpb=a6c3f80d970ea7a5c8597bca495495832a56a54b;p=oota-llvm.git

diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index b20a87ea0a8..0f5de9257a7 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,6 +237,7 @@ 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.
@@ -225,7 +247,8 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
 
 /// 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) {
+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 +257,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 +294,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 +304,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 +358,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.
@@ -402,9 +489,9 @@ void LiveInterval::MergeValueInAsValue(const LiveInterval &RHS,
     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#.
+      if (IP[-1].valno != LHSValNo) {
+        ReplacedValNos.push_back(IP[-1].valno);
+        IP[-1].valno = LHSValNo; // Update val#.
       }
       Start = IP[-1].end;
       // Trimmed away the whole range?
@@ -445,7 +532,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;
         }
@@ -589,16 +676,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 +713,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 << ")";
         }
       }