diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-03-12 01:50:35 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-03-12 01:50:35 +0000 |
commit | 55768d763d3d955c07d5819c3ef2e9d1ca6d2baf (patch) | |
tree | 9ba913d3af1620e2a8e39ca7efe300c51f19a677 /lib/CodeGen/LiveInterval.cpp | |
parent | 8b3000b08ee583bedfa8baebd4fcfd92e9a201c7 (diff) | |
download | llvm-55768d763d3d955c07d5819c3ef2e9d1ca6d2baf.tar.gz llvm-55768d763d3d955c07d5819c3ef2e9d1ca6d2baf.tar.bz2 llvm-55768d763d3d955c07d5819c3ef2e9d1ca6d2baf.tar.xz |
That's it, I am declaring this a failure of the C++03 STL.
There are too many compatibility problems with using mixed types in
std::upper_bound, and I don't want to spend 110 lines of boilerplate setting up
a call to a 10-line function. Binary search is not /that/ hard to implement
correctly.
I tried terminating the binary search with a linear search, but that actually
made the algorithm slower against my expectation. Most live intervals have less
than 4 segments. The early test against endIndex() does pay, and this version is
25% faster than plain std::upper_bound().
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127522 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/CodeGen/LiveInterval.cpp')
-rw-r--r-- | lib/CodeGen/LiveInterval.cpp | 134 |
1 files changed, 15 insertions, 119 deletions
diff --git a/lib/CodeGen/LiveInterval.cpp b/lib/CodeGen/LiveInterval.cpp index 1b446e69d3..18ec9d5667 100644 --- a/lib/CodeGen/LiveInterval.cpp +++ b/lib/CodeGen/LiveInterval.cpp @@ -30,126 +30,22 @@ #include <algorithm> using namespace llvm; -// SlotIndexIterator - adapt an iterator over LiveRanges to look -// like an iterator over SlotIndexes by accessing the .end member. -namespace { -struct SlotIndexIterator - : std::iterator<std::random_access_iterator_tag, SlotIndex> { - - SlotIndexIterator() { - } - - explicit SlotIndexIterator(LiveInterval::iterator it) - : it(it) { - } - - SlotIndexIterator(const SlotIndexIterator & that) - : it(that.it) { - } - - SlotIndexIterator & operator=(const SlotIndexIterator & that) { - it = that.it; - return *this; - } - - SlotIndexIterator & operator++() { - ++it; - return *this; - } - - SlotIndexIterator operator++(int) { - SlotIndexIterator that(*this); - ++*this; - return that; - } - - SlotIndexIterator & operator--() { - --it; - return *this; - } - - SlotIndexIterator operator--(int) { - SlotIndexIterator that(*this); - --*this; - return that; - } - - SlotIndexIterator & operator+=(std::ptrdiff_t n) { - it += n; - return *this; - } - - SlotIndexIterator & operator-=(std::ptrdiff_t n) { - it -= n; - return *this; - } - - friend bool operator==(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it == rhs.it; - } - - friend bool operator!=(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it != rhs.it; - } - - friend bool operator<(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it < rhs.it; - } - - friend bool operator<=(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it <= rhs.it; - } - - friend bool operator>(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it > rhs.it; - } - - friend bool operator>=(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it >= rhs.it; - } - - friend SlotIndexIterator operator+(SlotIndexIterator that, std::ptrdiff_t n) { - return SlotIndexIterator(that.it + n); - } - - friend SlotIndexIterator operator+(std::ptrdiff_t n, SlotIndexIterator that) { - return SlotIndexIterator(n + that.it); - } - - friend SlotIndexIterator operator-(SlotIndexIterator that, std::ptrdiff_t n) { - return SlotIndexIterator(that.it - n); - } - - friend std::ptrdiff_t operator-(SlotIndexIterator lhs, SlotIndexIterator rhs) { - return lhs.it - rhs.it; - } - - reference operator*() const { - return it->end; - } - - reference operator[](std::ptrdiff_t n) const { - return it[n].end; - } - - pointer operator->() const { - return &it->end; - } - - LiveInterval::iterator base() const { - return it; - } - -private: - LiveInterval::iterator it; -}; -} - LiveInterval::iterator LiveInterval::find(SlotIndex Pos) { - assert(Pos.isValid() && "Cannot search for an invalid index"); - return std::upper_bound( - SlotIndexIterator(begin()), - SlotIndexIterator(end()), Pos).base(); + // This algorithm is basically std::upper_bound. + // Unfortunately, std::upper_bound cannot be used with mixed types until we + // adopt C++0x. Many libraries can do it, but not all. + if (empty() || Pos >= endIndex()) + return end(); + iterator I = begin(); + size_t Len = ranges.size(); + do { + size_t Mid = Len >> 1; + if (Pos < I[Mid].end) + Len = Mid; + else + I += Mid + 1, Len -= Mid + 1; + } while (Len); + return I; } /// killedInRange - Return true if the interval has kills in [Start,End). |