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.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@106905 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index bf0bdd1..34b5851 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -68,6 +68,37 @@
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 @@
// 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 @@
// 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 @@
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 @@
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 @@
// 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 @@
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 @@
assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo");
}
}
-
+
// Print value number info.
if (getNumValNums()) {
OS << " ";
@@ -848,21 +869,6 @@
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 << ")";
- }
}
}
}