From 55d738e2e14725e71aa1c580cf1061c607fbd7ee Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Fri, 25 Jun 2010 22:53:05 +0000
Subject: Don't track kills in VNInfo. Use interval ends instead.

The VNInfo.kills vector was almost unused except for all the code keeping it
updated. The few places using it were easily rewritten to check for interval
ends instead.

The two new methods LiveInterval::killedAt and killedInRange are replacements.

This brings us down to 3 independent data structures tracking kills.

llvm-svn: 106905
---
 llvm/lib/CodeGen/LiveInterval.cpp | 60 +++++++++++++++++++++------------------
 1 file changed, 33 insertions(+), 27 deletions(-)

(limited to 'llvm/lib/CodeGen/LiveInterval.cpp')

diff --git a/llvm/lib/CodeGen/LiveInterval.cpp b/llvm/lib/CodeGen/LiveInterval.cpp
index bf0bdd183c8..34b58515b68 100644
--- a/llvm/lib/CodeGen/LiveInterval.cpp
+++ b/llvm/lib/CodeGen/LiveInterval.cpp
@@ -68,6 +68,37 @@ bool LiveInterval::liveBeforeAndAt(SlotIndex I) const {
   return r->end == I;
 }
 
+/// killedAt - Return true if a live range ends at index. Note that the kill
+/// point is not contained in the half-open live range. It is usually the
+/// getDefIndex() slot following its last use.
+bool LiveInterval::killedAt(SlotIndex I) const {
+  Ranges::const_iterator r = std::lower_bound(ranges.begin(), ranges.end(), I);
+
+  // Now r points to the first interval with start >= I, or ranges.end().
+  if (r == ranges.begin())
+    return false;
+
+  --r;
+  // Now r points to the last interval with end <= I.
+  // r->end is the kill point.
+  return r->end == I;
+}
+
+/// killedInRange - Return true if the interval has kills in [Start,End).
+bool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const {
+  Ranges::const_iterator r =
+    std::lower_bound(ranges.begin(), ranges.end(), End);
+
+  // Now r points to the first interval with start >= End, or ranges.end().
+  if (r == ranges.begin())
+    return false;
+
+  --r;
+  // Now r points to the last interval with end <= End.
+  // r->end is the kill point.
+  return r->end >= Start && r->end < End;
+}
+
 // overlaps - Return true if the intersection of the two live intervals is
 // not empty.
 //
@@ -163,9 +194,6 @@ void LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) {
   // Erase any dead ranges.
   ranges.erase(next(I), MergeTo);
 
-  // Update kill info.
-  ValNo->removeKills(OldEnd, I->end.getPrevSlot());
-
   // 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);
@@ -245,9 +273,6 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
         // endpoint as well.
         if (End > it->end)
           extendIntervalEndTo(it, End);
-        else if (End < it->end)
-          // Overlapping intervals, there might have been a kill here.
-          it->valno->removeKill(End);
         return it;
       }
     } else {
@@ -288,7 +313,6 @@ void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
   VNInfo *ValNo = I->valno;
   if (I->start == Start) {
     if (I->end == End) {
-      ValNo->removeKills(Start, End);
       if (RemoveDeadValNo) {
         // Check if val# is dead.
         bool isDead = true;
@@ -296,7 +320,7 @@ void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
           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),
@@ -320,7 +344,6 @@ void LiveInterval::removeRange(SlotIndex Start, SlotIndex End,
   // Otherwise if the span we are removing is at the end of the LiveRange,
   // adjust the other way.
   if (I->end == End) {
-    ValNo->removeKills(Start, End);
     I->end = Start;
     return;
   }
@@ -484,8 +507,6 @@ void LiveInterval::join(LiveInterval &Other,
     I->valno = NewVNInfo[OtherAssignments[RangeNo]];
     assert(I->valno && "Adding a dead range?");
     InsertPos = addRangeFrom(*I, InsertPos);
-    InsertPos->valno->removeKills(InsertPos->start,
-                                  InsertPos->end.getPrevSlot());
   }
 
   ComputeJoinedWeight(Other);
@@ -831,7 +852,7 @@ void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
       assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo");
     }
   }
-  
+
   // Print value number info.
   if (getNumValNums()) {
     OS << "  ";
@@ -848,21 +869,6 @@ void LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
           OS << "?";
         else
           OS << vni->def;
-        unsigned ee = vni->kills.size();
-        if (ee || vni->hasPHIKill()) {
-          OS << "-(";
-          for (unsigned j = 0; j != ee; ++j) {
-            OS << vni->kills[j];
-            if (j != ee-1)
-              OS << " ";
-          }
-          if (vni->hasPHIKill()) {
-            if (ee)
-              OS << " ";
-            OS << "phi";
-          }
-          OS << ")";
-        }
       }
     }
   }
-- 
cgit v1.2.3