summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/CodeGen/LiveInterval.h40
-rw-r--r--lib/CodeGen/LiveInterval.cpp76
2 files changed, 41 insertions, 75 deletions
diff --git a/include/llvm/CodeGen/LiveInterval.h b/include/llvm/CodeGen/LiveInterval.h
index 33d3d12feb..aec21f8522 100644
--- a/include/llvm/CodeGen/LiveInterval.h
+++ b/include/llvm/CodeGen/LiveInterval.h
@@ -271,6 +271,19 @@ namespace llvm {
return I;
}
+ /// find - Return an iterator pointing to the first range that ends after
+ /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster
+ /// when searching large intervals.
+ ///
+ /// If Pos is contained in a LiveRange, that range is returned.
+ /// If Pos is in a hole, the following LiveRange is returned.
+ /// If Pos is beyond endIndex, end() is returned.
+ iterator find(SlotIndex Pos);
+
+ const_iterator find(SlotIndex Pos) const {
+ return const_cast<LiveInterval*>(this)->find(Pos);
+ }
+
void clear() {
valnos.clear();
ranges.clear();
@@ -386,12 +399,18 @@ namespace llvm {
return index >= endIndex();
}
- bool liveAt(SlotIndex index) const;
+ bool liveAt(SlotIndex index) const {
+ const_iterator r = find(index);
+ return r != end() && r->start <= index;
+ }
/// 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 killedAt(SlotIndex index) const;
+ bool killedAt(SlotIndex index) const {
+ const_iterator r = find(index.getUseIndex());
+ return r != end() && r->end == index;
+ }
/// killedInRange - Return true if the interval has kills in [Start,End).
/// Note that the kill point is considered the end of a live range, so it is
@@ -421,11 +440,15 @@ namespace llvm {
/// FindLiveRangeContaining - Return an iterator to the live range that
/// contains the specified index, or end() if there is none.
- const_iterator FindLiveRangeContaining(SlotIndex Idx) const;
+ iterator FindLiveRangeContaining(SlotIndex Idx) {
+ iterator I = find(Idx);
+ return I != end() && I->start <= Idx ? I : end();
+ }
- /// FindLiveRangeContaining - Return an iterator to the live range that
- /// contains the specified index, or end() if there is none.
- iterator FindLiveRangeContaining(SlotIndex Idx);
+ const_iterator FindLiveRangeContaining(SlotIndex Idx) const {
+ const_iterator I = find(Idx);
+ return I != end() && I->start <= Idx ? I : end();
+ }
/// findDefinedVNInfo - Find the by the specified
/// index (register interval) or defined
@@ -467,7 +490,10 @@ namespace llvm {
/// isInOneLiveRange - Return true if the range specified is entirely in the
/// a single LiveRange of the live interval.
- bool isInOneLiveRange(SlotIndex Start, SlotIndex End);
+ bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const {
+ const_iterator r = find(Start);
+ return r != end() && r->containsRange(Start, End);
+ }
/// removeRange - Remove the specified range from this interval. Note that
/// the range must be a single LiveRange in its entirety.
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp
index 513a6c0835..6a6ecf78f6 100644
--- a/lib/CodeGen/LiveInterval.cpp
+++ b/lib/CodeGen/LiveInterval.cpp
@@ -30,37 +30,14 @@
#include <algorithm>
using namespace llvm;
-// An example for liveAt():
-//
-// this = [1,4), liveAt(0) will return false. The instruction defining this
-// spans slots [0,3]. The interval belongs to an spilled definition of the
-// variable it represents. This is because slot 1 is used (def slot) and spans
-// up to slot 3 (store slot).
-//
-bool LiveInterval::liveAt(SlotIndex I) const {
- Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
-
- if (r == ranges.begin())
- return false;
-
- --r;
- return r->contains(I);
+// compEnd - Compare LiveRange end to Pos.
+// This argument ordering works for upper_bound.
+static inline bool compEnd(SlotIndex Pos, const LiveRange &LR) {
+ return Pos < LR.end;
}
-/// 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;
+LiveInterval::iterator LiveInterval::find(SlotIndex Pos) {
+ return std::upper_bound(begin(), end(), Pos, compEnd);
}
/// killedInRange - Return true if the interval has kills in [Start,End).
@@ -309,25 +286,14 @@ LiveInterval::addRangeFrom(LiveRange LR, iterator From) {
return ranges.insert(it, LR);
}
-/// isInOneLiveRange - Return true if the range specified is entirely in
-/// a single LiveRange of the live interval.
-bool LiveInterval::isInOneLiveRange(SlotIndex Start, SlotIndex End) {
- Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
- if (I == ranges.begin())
- return false;
- --I;
- return I->containsRange(Start, End);
-}
-
/// removeRange - Remove the specified range from this interval. Note that
/// the range must be in a single LiveRange in its entirety.
void LiveInterval::removeRange(SlotIndex Start, SlotIndex 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!");
- --I;
+ Ranges::iterator I = find(Start);
+ assert(I != ranges.end() && "Range is not in interval!");
assert(I->containsRange(Start, End) && "Range is not entirely in interval!");
// If the span we are removing is at the start of the LiveRange, adjust it.
@@ -384,32 +350,6 @@ void LiveInterval::removeValNo(VNInfo *ValNo) {
markValNoForDeletion(ValNo);
}
-/// getLiveRangeContaining - Return the live range that contains the
-/// specified index, or null if there is none.
-LiveInterval::const_iterator
-LiveInterval::FindLiveRangeContaining(SlotIndex Idx) const {
- const_iterator It = std::upper_bound(begin(), end(), Idx);
- if (It != ranges.begin()) {
- --It;
- if (It->contains(Idx))
- return It;
- }
-
- return end();
-}
-
-LiveInterval::iterator
-LiveInterval::FindLiveRangeContaining(SlotIndex Idx) {
- iterator It = std::upper_bound(begin(), end(), Idx);
- if (It != begin()) {
- --It;
- if (It->contains(Idx))
- return It;
- }
-
- return end();
-}
-
/// findDefinedVNInfo - Find the VNInfo defined by the specified
/// index (register interval).
VNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const {
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-25 09:19:09 +0000