summaryrefslogtreecommitdiff
path: root/Source/Core
diff options
context:
space:
mode:
Diffstat (limited to 'Source/Core')
-rw-r--r--Source/Core/Common/CMakeLists.txt2
-rw-r--r--Source/Core/Common/RangeSet.h423
-rw-r--r--Source/Core/Common/RangeSizeSet.h586
-rw-r--r--Source/Core/Core/CMakeLists.txt1
-rw-r--r--Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h5
-rw-r--r--Source/Core/Core/PowerPC/Jit64/Jit.h7
-rw-r--r--Source/Core/Core/PowerPC/JitArm64/Jit.h11
-rw-r--r--Source/Core/Core/PowerPC/JitCommon/JitCache.cpp31
-rw-r--r--Source/Core/Core/PowerPC/JitCommon/JitCache.h7
-rw-r--r--Source/Core/Core/PowerPC/PPCAnalyst.cpp3
-rw-r--r--Source/Core/Core/PowerPC/PPCAnalyst.h4
-rw-r--r--Source/Core/DolphinLib.props2
-rw-r--r--Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp7
13 files changed, 1057 insertions, 32 deletions
diff --git a/Source/Core/Common/CMakeLists.txt b/Source/Core/Common/CMakeLists.txt
index fac5900f76..e134acabd3 100644
--- a/Source/Core/Common/CMakeLists.txt
+++ b/Source/Core/Common/CMakeLists.txt
@@ -127,6 +127,8 @@ add_library(common
QoSSession.h
Random.cpp
Random.h
+ RangeSet.h
+ RangeSizeSet.h
ScopeGuard.h
SDCardUtil.cpp
SDCardUtil.h
diff --git a/Source/Core/Common/RangeSet.h b/Source/Core/Common/RangeSet.h
new file mode 100644
index 0000000000..05229c8704
--- /dev/null
+++ b/Source/Core/Common/RangeSet.h
@@ -0,0 +1,423 @@
+// Copyright 2020 Dolphin Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <cassert>
+#include <cstddef>
+#include <map>
+#include <utility>
+
+namespace Common
+{
+template <typename T>
+class RangeSet
+{
+private:
+ using MapT = std::map<T, T>;
+
+public:
+ struct const_iterator
+ {
+ public:
+ const T& from() const { return It->first; }
+
+ const T& to() const { return It->second; }
+
+ std::pair<T, T> operator*() { return {from(), to()}; }
+
+ const_iterator& operator++()
+ {
+ ++It;
+ return *this;
+ }
+
+ const_iterator operator++(int)
+ {
+ const_iterator old = *this;
+ ++It;
+ return old;
+ }
+
+ const_iterator& operator--()
+ {
+ --It;
+ return *this;
+ }
+
+ const_iterator operator--(int)
+ {
+ const_iterator old = *this;
+ --It;
+ return old;
+ }
+
+ bool operator==(const const_iterator& rhs) const { return this->It == rhs.It; }
+
+ bool operator!=(const const_iterator& rhs) const { return !operator==(rhs); }
+
+ private:
+ typename MapT::const_iterator It;
+ const_iterator(typename MapT::const_iterator it) : It(it) {}
+ friend class RangeSet;
+ };
+
+ void insert(T from, T to)
+ {
+ if (from >= to)
+ return;
+
+ // Start by finding the closest range.
+ // upper_bound() returns the closest range whose starting position
+ // is greater than 'from'.
+ auto bound = Map.upper_bound(from);
+ if (bound == Map.end())
+ {
+ // There is no range that starts greater than the given one.
+ // This means we have three options:
+ // - 1. No range exists yet, this is the first range.
+ if (Map.empty())
+ {
+ insert_range(from, to);
+ return;
+ }
+
+ // - 2. The given range does not overlap the last range.
+ --bound;
+ if (from > get_to(bound))
+ {
+ insert_range(from, to);
+ return;
+ }
+
+ // - 3. The given range does overlap the last range.
+ maybe_expand_to(bound, to);
+ return;
+ }
+
+ if (bound == Map.begin())
+ {
+ // The given range starts before any of the existing ones.
+ // We must insert this as a new range even if we potentially overlap
+ // an existing one as we can't modify a key in a std::map.
+ auto inserted = insert_range(from, to);
+ merge_from_iterator_to_value(inserted, bound, to);
+ return;
+ }
+
+ auto abound = bound--;
+
+ // 'bound' now points at the first range in the map that
+ // could possibly be affected.
+
+ // If 'bound' overlaps with given range, update bounds object.
+ if (get_to(bound) >= from)
+ {
+ maybe_expand_to(bound, to);
+ auto inserted = bound;
+ ++bound;
+ merge_from_iterator_to_value(inserted, bound, to);
+ return;
+ }
+
+ // 'bound' *doesn't* overlap with given range, check next range.
+
+ // If this range overlaps with given range,
+ if (get_from(abound) <= to)
+ {
+ // insert new range
+ auto inserted = insert_range(from, to >= get_to(abound) ? to : get_to(abound));
+ // and delete overlaps
+ abound = erase_range(abound);
+ merge_from_iterator_to_value(inserted, abound, to);
+ return;
+ }
+
+ // Otherwise, if we come here, then this new range overlaps nothing
+ // and must be inserted as a new range.
+ insert_range(from, to);
+ }
+
+ void erase(T from, T to)
+ {
+ if (from >= to)
+ return;
+
+ // Like insert(), we use upper_bound to find the closest range.
+ auto bound = Map.upper_bound(from);
+ if (bound == Map.end())
+ {
+ // There is no range that starts greater than the given one.
+ if (Map.empty())
+ {
+ // nothing to do
+ return;
+ }
+ --bound;
+ // 'bound' now points at the last range.
+ if (from >= get_to(bound))
+ {
+ // Given range is larger than any range that exists, nothing to do.
+ return;
+ }
+
+ if (to >= get_to(bound))
+ {
+ if (from == get_from(bound))
+ {
+ // Given range fully overlaps last range, erase it.
+ erase_range(bound);
+ return;
+ }
+ else
+ {
+ // Given range overlaps end of last range, reduce it.
+ reduce_to(bound, from);
+ return;
+ }
+ }
+
+ if (from == get_from(bound))
+ {
+ // Given range overlaps begin of last range, reduce it.
+ reduce_from(bound, to);
+ return;
+ }
+ else
+ {
+ // Given range overlaps middle of last range, bisect it.
+ bisect_range(bound, from, to);
+ return;
+ }
+ }
+
+ if (bound == Map.begin())
+ {
+ // If we found the first range that means 'from' is before any stored range.
+ // This means we can just erase from start until 'to' and be done with it.
+ erase_from_iterator_to_value(bound, to);
+ return;
+ }
+
+ // check previous range
+ auto abound = bound--;
+
+ if (from == get_from(bound))
+ {
+ // Similarly, if the previous range starts with the given one, just erase until 'to'.
+ erase_from_iterator_to_value(bound, to);
+ return;
+ }
+
+ // If we come here, the given range may or may not overlap part of the current 'bound'
+ // (but never the full range), which means we may need to update the end position of it,
+ // or possibly even split it into two.
+ if (from < get_to(bound))
+ {
+ if (to < get_to(bound))
+ {
+ // need to split in two
+ bisect_range(bound, from, to);
+ return;
+ }
+ else
+ {
+ // just update end
+ reduce_to(bound, from);
+ }
+ }
+
+ // and then just erase until 'to'
+ erase_from_iterator_to_value(abound, to);
+ return;
+ }
+
+ const_iterator erase(const_iterator it) { return const_iterator(erase_range(it.It)); }
+
+ void clear() { Map.clear(); }
+
+ bool contains(T value) const
+ {
+ auto it = Map.upper_bound(value);
+ if (it == Map.begin())
+ return false;
+ --it;
+ return get_from(it) <= value && value < get_to(it);
+ }
+
+ bool overlaps(T from, T to) const
+ {
+ if (from >= to)
+ return false;
+
+ auto it = Map.lower_bound(to);
+ if (it == Map.begin())
+ return false;
+ --it;
+ return get_from(it) < to && from < get_to(it);
+ }
+
+ std::size_t size() const { return Map.size(); }
+
+ bool empty() const { return Map.empty(); }
+
+ void swap(RangeSet<T>& other) { Map.swap(other.Map); }
+
+ const_iterator begin() const { return const_iterator(Map.begin()); }
+
+ const_iterator end() const { return const_iterator(Map.end()); }
+
+ const_iterator cbegin() const { return const_iterator(Map.cbegin()); }
+
+ const_iterator cend() const { return const_iterator(Map.cend()); }
+
+ bool operator==(const RangeSet<T>& other) const { return this->Map == other.Map; }
+
+ bool operator!=(const RangeSet<T>& other) const { return !(*this == other); }
+
+ // Get free size and fragmentation ratio
+ std::pair<std::size_t, double> get_stats() const
+ {
+ std::size_t free_total = 0;
+ if (begin() == end())
+ return {free_total, 1.0};
+ std::size_t largest_size = 0;
+ for (auto iter = begin(); iter != end(); ++iter)
+ {
+ const std::size_t size = calc_size(iter.from(), iter.to());
+ if (size > largest_size)
+ largest_size = size;
+ free_total += size;
+ }
+ return {free_total, static_cast<double>(free_total - largest_size) / free_total};
+ }
+
+private:
+ static std::size_t calc_size(T from, T to)
+ {
+ if constexpr (std::is_pointer_v<T>)
+ {
+ // For pointers we don't want pointer arithmetic here, else void* breaks.
+ return reinterpret_cast<std::size_t>(to) - reinterpret_cast<std::size_t>(from);
+ }
+ else
+ {
+ return static_cast<std::size_t>(to - from);
+ }
+ }
+
+ // Assumptions that can be made about the data:
+ // - Range are stored in the form [from, to[
+ // That is, the starting value is inclusive, and the end value is exclusive.
+ // - 'from' is the map key, 'to' is the map value
+ // - 'from' is always smaller than 'to'
+ // - Stored ranges never touch.
+ // - Stored ranges never overlap.
+ MapT Map;
+
+ T get_from(typename MapT::iterator it) const { return it->first; }
+
+ T get_to(typename MapT::iterator it) const { return it->second; }
+
+ T get_from(typename MapT::const_iterator it) const { return it->first; }
+
+ T get_to(typename MapT::const_iterator it) const { return it->second; }
+
+ typename MapT::iterator insert_range(T from, T to) { return Map.emplace(from, to).first; }
+
+ typename MapT::iterator erase_range(typename MapT::iterator it) { return Map.erase(it); }
+
+ typename MapT::const_iterator erase_range(typename MapT::const_iterator it)
+ {
+ return Map.erase(it);
+ }
+
+ void bisect_range(typename MapT::iterator it, T from, T to)
+ {
+ assert(get_from(it) < from);
+ assert(get_from(it) < to);
+ assert(get_to(it) > from);
+ assert(get_to(it) > to);
+ assert(from < to);
+ T itto = get_to(it);
+ reduce_to(it, from);
+ insert_range(to, itto);
+ }
+
+ typename MapT::iterator reduce_from(typename MapT::iterator it, T from)
+ {
+ assert(get_from(it) < from);
+ T itto = get_to(it);
+ erase_range(it);
+ return insert_range(from, itto);
+ }
+
+ void maybe_expand_to(typename MapT::iterator it, T to)
+ {
+ if (to <= get_to(it))
+ return;
+
+ expand_to(it, to);
+ }
+
+ void expand_to(typename MapT::iterator it, T to)
+ {
+ assert(get_to(it) < to);
+ it->second = to;
+ }
+
+ void reduce_to(typename MapT::iterator it, T to)
+ {
+ assert(get_to(it) > to);
+ it->second = to;
+ }
+
+ void merge_from_iterator_to_value(typename MapT::iterator inserted, typename MapT::iterator bound,
+ T to)
+ {
+ // Erase all ranges that overlap the inserted while updating the upper end.
+ while (bound != Map.end() && get_from(bound) <= to)
+ {
+ maybe_expand_to(inserted, get_to(bound));
+ bound = erase_range(bound);
+ }
+ }
+
+ void erase_from_iterator_to_value(typename MapT::iterator bound, T to)
+ {
+ // Assumption: Given bound starts at or after the 'from' value of the range to erase.
+ while (true)
+ {
+ // Given range starts before stored range.
+ if (to <= get_from(bound))
+ {
+ // Range ends before this range too, nothing to do.
+ return;
+ }
+
+ if (to < get_to(bound))
+ {
+ // Range ends in the middle of current range, reduce current.
+ reduce_from(bound, to);
+ return;
+ }
+
+ if (to == get_to(bound))
+ {
+ // Range ends exactly with current range, erase current.
+ erase_range(bound);
+ return;
+ }
+
+ // Range ends later than current range.
+ // First erase current, then loop to check the range(s) after this one too.
+ bound = erase_range(bound);
+ if (bound == Map.end())
+ {
+ // Unless that was the last range, in which case there's nothing else to do.
+ return;
+ }
+ }
+ }
+};
+} // namespace Common
diff --git a/Source/Core/Common/RangeSizeSet.h b/Source/Core/Common/RangeSizeSet.h
new file mode 100644
index 0000000000..72ec740523
--- /dev/null
+++ b/Source/Core/Common/RangeSizeSet.h
@@ -0,0 +1,586 @@
+// Copyright 2020 Dolphin Emulator Project
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+#pragma once
+
+#include <cassert>
+#include <cstddef>
+#include <map>
+#include <type_traits>
+#include <utility>
+
+namespace Common
+{
+// Like RangeSet, but additionally stores a map of the ranges sorted by their size, for quickly
+// finding the largest or smallest range.
+template <typename T>
+class RangeSizeSet
+{
+private:
+ // Key type used in the by-size multimap. Should be a type big enough to hold all possible
+ // distances between possible 'from' and 'to'.
+ // I'd actually love to just do
+ // using SizeT = typename std::conditional<std::is_pointer_v<T>,
+ // std::size_t, typename std::make_unsigned<T>::type>::type;
+ // but that's apparently not possible due to the std::make_unsigned<T>::type not existing for
+ // pointer types so we'll work around this...
+ template <typename U, bool IsPointer>
+ struct GetSizeType
+ {
+ using S = typename std::make_unsigned<U>::type;
+ };
+ template <typename U>
+ struct GetSizeType<U, true>
+ {
+ using S = std::size_t;
+ };
+
+public:
+ using SizeT = typename GetSizeType<T, std::is_pointer_v<T>>::S;
+
+private:
+ // Value type stored in the regular range map.
+ struct Value
+ {
+ // End point of the range.
+ T To;
+
+ // Pointer to the same range in the by-size multimap.
+ typename std::multimap<SizeT, typename std::map<T, Value>::iterator,
+ std::greater<SizeT>>::iterator SizeIt;
+
+ Value(T to) : To(to) {}
+
+ bool operator==(const Value& other) const { return this->To == other.To; }
+
+ bool operator!=(const Value& other) const { return !operator==(other); }
+ };
+
+ using MapT = std::map<T, Value>;
+ using SizeMapT = std::multimap<SizeT, typename MapT::iterator, std::greater<SizeT>>;
+
+public:
+ struct by_size_const_iterator;
+
+ struct const_iterator
+ {
+ public:
+ const T& from() const { return It->first; }
+
+ const T& to() const { return It->second.To; }
+
+ std::pair<T, T> operator*() { return {from(), to()}; }
+
+ const_iterator& operator++()
+ {
+ ++It;
+ return *this;
+ }
+
+ const_iterator operator++(int)
+ {
+ const_iterator old = *this;
+ ++It;
+ return old;
+ }
+
+ const_iterator& operator--()
+ {
+ --It;
+ return *this;
+ }
+
+ const_iterator operator--(int)
+ {
+ const_iterator old = *this;
+ --It;
+ return old;
+ }
+
+ bool operator==(const const_iterator& rhs) const { return this->It == rhs.It; }
+
+ bool operator!=(const const_iterator& rhs) const { return !operator==(rhs); }
+
+ by_size_const_iterator to_size_iterator() { return by_size_const_iterator(It->second.SizeIt); }
+
+ private:
+ typename MapT::const_iterator It;
+ const_iterator(typename MapT::const_iterator it) : It(it) {}
+ friend class RangeSizeSet;
+ };
+
+ struct by_size_const_iterator
+ {
+ public:
+ const T& from() const { return It->second->first; }
+
+ const T& to() const { return It->second->second.To; }
+
+ by_size_const_iterator& operator++()
+ {
+ ++It;
+ return *this;
+ }
+
+ by_size_const_iterator operator++(int)
+ {
+ by_size_const_iterator old = *this;
+ ++It;
+ return old;
+ }
+
+ by_size_const_iterator& operator--()
+ {
+ --It;
+ return *this;
+ }
+
+ by_size_const_iterator operator--(int)
+ {
+ by_size_const_iterator old = *this;
+ --It;
+ return old;
+ }
+
+ bool operator==(const by_size_const_iterator& rhs) const { return this->It == rhs.It; }
+
+ bool operator!=(const by_size_const_iterator& rhs) const { return !operator==(rhs); }
+
+ const_iterator to_range_iterator() { return const_iterator(It->second); }
+
+ private:
+ typename SizeMapT::const_iterator It;
+ by_size_const_iterator(typename SizeMapT::const_iterator it) : It(it) {}
+ friend class RangeSizeSet;
+ };
+
+ // We store iterators internally, so disallow copying.
+ RangeSizeSet() = default;
+ RangeSizeSet(const RangeSizeSet<T>&) = delete;
+ RangeSizeSet(RangeSizeSet<T>&&) = default;
+ RangeSizeSet<T>& operator=(const RangeSizeSet<T>&) = delete;
+ RangeSizeSet<T>& operator=(RangeSizeSet<T>&&) = default;
+
+ void insert(T from, T to)
+ {
+ if (from >= to)
+ return;
+
+ // Start by finding the closest range.
+ // upper_bound() returns the closest range whose starting position
+ // is greater than 'from'.
+ auto bound = Map.upper_bound(from);
+ if (bound == Map.end())
+ {
+ // There is no range that starts greater than the given one.
+ // This means we have three options:
+ // - 1. No range exists yet, this is the first range.
+ if (Map.empty())
+ {
+ insert_range(from, to);
+ return;
+ }
+
+ // - 2. The given range does not overlap the last range.
+ --bound;
+ if (from > get_to(bound))
+ {
+ insert_range(from, to);
+ return;
+ }
+
+ // - 3. The given range does overlap the last range.
+ maybe_expand_to(bound, to);
+ return;
+ }
+
+ if (bound == Map.begin())
+ {
+ // The given range starts before any of the existing ones.
+ // We must insert this as a new range even if we potentially overlap
+ // an existing one as we can't modify a key in a std::map.
+ auto inserted = insert_range(from, to);
+ merge_from_iterator_to_value(inserted, bound, to);
+ return;
+ }
+
+ auto abound = bound--;
+
+ // 'bound' now points at the first range in the map that
+ // could possibly be affected.
+
+ // If 'bound' overlaps with given range, update bounds object.
+ if (get_to(bound) >= from)
+ {
+ maybe_expand_to(bound, to);
+ auto inserted = bound;
+ ++bound;
+ merge_from_iterator_to_value(inserted, bound, to);
+ return;
+ }
+
+ // 'bound' *doesn't* overlap with given range, check next range.
+
+ // If this range overlaps with given range,
+ if (get_from(abound) <= to)
+ {
+ // insert new range
+ auto inserted = insert_range(from, to >= get_to(abound) ? to : get_to(abound));
+ // and delete overlaps
+ abound = erase_range(abound);
+ merge_from_iterator_to_value(inserted, abound, to);
+ return;
+ }
+
+ // Otherwise, if we come here, then this new range overlaps nothing
+ // and must be inserted as a new range.
+ insert_range(from, to);
+ }
+
+ void erase(T from, T to)
+ {
+ if (from >= to)
+ return;
+
+ // Like insert(), we use upper_bound to find the closest range.
+ auto bound = Map.upper_bound(from);
+ if (bound == Map.end())
+ {
+ // There is no range that starts greater than the given one.
+ if (Map.empty())
+ {
+ // nothing to do
+ return;
+ }
+ --bound;
+ // 'bound' now points at the last range.
+ if (from >= get_to(bound))
+ {
+ // Given range is larger than any range that exists, nothing to do.
+ return;
+ }
+
+ if (to >= get_to(bound))
+ {
+ if (from == get_from(bound))
+ {
+ // Given range fully overlaps last range, erase it.
+ erase_range(bound);
+ return;
+ }
+ else
+ {
+ // Given range overlaps end of last range, reduce it.
+ reduce_to(bound, from);
+ return;
+ }
+ }
+
+ if (from == get_from(bound))
+ {
+ // Given range overlaps begin of last range, reduce it.
+ reduce_from(bound, to);
+ return;
+ }
+ else
+ {
+ // Given range overlaps middle of last range, bisect it.
+ bisect_range(bound, from, to);
+ return;
+ }
+ }
+
+ if (bound == Map.begin())
+ {
+ // If we found the first range that means 'from' is before any stored range.
+ // This means we can just erase from start until 'to' and be done with it.
+ erase_from_iterator_to_value(bound, to);
+ return;
+ }
+
+ // check previous range
+ auto abound = bound--;
+
+ if (from == get_from(bound))
+ {
+ // Similarly, if the previous range starts with the given one, just erase until 'to'.
+ erase_from_iterator_to_value(bound, to);
+ return;
+ }
+
+ // If we come here, the given range may or may not overlap part of the current 'bound'
+ // (but never the full range), which means we may need to update the end position of it,
+ // or possibly even split it into two.
+ if (from < get_to(bound))
+ {
+ if (to < get_to(bound))
+ {
+ // need to split in two
+ bisect_range(bound, from, to);
+ return;
+ }
+ else
+ {
+ // just update end
+ reduce_to(bound, from);
+ }
+ }
+
+ // and then just erase until 'to'
+ erase_from_iterator_to_value(abound, to);
+ return;
+ }
+
+ const_iterator erase(const_iterator it) { return const_iterator(erase_range(it.It)); }
+
+ by_size_const_iterator erase(by_size_const_iterator it)
+ {
+ return by_size_const_iterator(erase_range_by_size(it.It));
+ }
+
+ void clear()
+ {
+ Map.clear();
+ Sizes.clear();
+ }
+
+ bool contains(T value) const
+ {
+ auto it = Map.upper_bound(value);
+ if (it == Map.begin())
+ return false;
+ --it;
+ return get_from(it) <= value && value < get_to(it);
+ }
+
+ bool overlaps(T from, T to) const
+ {
+ if (from >= to)
+ return false;
+
+ auto it = Map.lower_bound(to);
+ if (it == Map.begin())
+ return false;
+ --it;
+ return get_from(it) < to && from < get_to(it);
+ }
+
+ std::size_t size() const { return Map.size(); }
+
+ bool empty() const { return Map.empty(); }
+
+ std::size_t by_size_count(const SizeT& key) const { return Sizes.count(key); }
+
+ by_size_const_iterator by_size_find(const SizeT& key) const { return Sizes.find(key); }
+
+ std::pair<by_size_const_iterator, by_size_const_iterator>
+ by_size_equal_range(const SizeT& key) const
+ {
+ auto p = Sizes.equal_range(key);
+ return std::pair<by_size_const_iterator, by_size_const_iterator>(
+ by_size_const_iterator(p.first), by_size_const_iterator(p.second));
+ }
+
+ by_size_const_iterator by_size_lower_bound(const SizeT& key) const
+ {
+ return Sizes.lower_bound(key);
+ }
+
+ by_size_const_iterator by_size_upper_bound(const SizeT& key) const
+ {
+ return Sizes.upper_bound(key);
+ }
+
+ void swap(RangeSizeSet<T>& other)
+ {
+ Map.swap(other.Map);
+ Sizes.swap(other.Sizes);
+ }
+
+ const_iterator begin() const { return const_iterator(Map.begin()); }
+
+ const_iterator end() const { return const_iterator(Map.end()); }
+
+ const_iterator cbegin() const { return const_iterator(Map.cbegin()); }
+
+ const_iterator cend() const { return const_iterator(Map.cend()); }
+
+ by_size_const_iterator by_size_begin() const { return by_size_const_iterator(Sizes.begin()); }
+
+ by_size_const_iterator by_size_end() const { return by_size_const_iterator(Sizes.end()); }
+
+ by_size_const_iterator by_size_cbegin() const { return by_size_const_iterator(Sizes.cbegin()); }
+
+ by_size_const_iterator by_size_cend() const { return by_size_const_iterator(Sizes.cend()); }
+
+ bool operator==(const RangeSizeSet<T>& other) const { return this->Map == other.Map; }
+
+ bool operator!=(const RangeSizeSet<T>& other) const { return !(*this == other); }
+
+ // Get free size and fragmentation ratio
+ std::pair<std::size_t, double> get_stats() const
+ {
+ std::size_t free_total = 0;
+ if (begin() == end())
+ return {free_total, 1.0};
+ for (auto iter = begin(); iter != end(); ++iter)
+ free_total += calc_size(iter.from(), iter.to());
+ return {free_total, static_cast<double>(free_total - Sizes.begin()->first) / free_total};
+ }
+
+private:
+ static SizeT calc_size(T from, T to)
+ {
+ if constexpr (std::is_pointer_v<T>)
+ {
+ // For pointers we don't want pointer arithmetic here, else void* breaks.
+ static_assert(sizeof(T) <= sizeof(SizeT));
+ return reinterpret_cast<SizeT>(to) - reinterpret_cast<SizeT>(from);
+ }
+ else
+ {
+ return static_cast<SizeT>(to - from);
+ }
+ }
+
+ // Assumptions that can be made about the data:
+ // - Range are stored in the form [from, to[
+ // That is, the starting value is inclusive, and the end value is exclusive.
+ // - 'from' is the map key, 'to' is the map value
+ // - 'from' is always smaller than 'to'
+ // - Stored ranges never touch.
+ // - Stored ranges never overlap.
+ MapT Map;
+
+ // The by-size multimap.
+ // Key is the size of the range.
+ // Value is a pointer to the range in the regular range map.
+ // We use std::greater so that Sizes.begin() gives us the largest range.
+ SizeMapT Sizes;
+
+ T get_from(typename MapT::iterator it) const { return it->first; }
+
+ T get_to(typename MapT::iterator it) const { return it->second.To; }
+
+ T get_from(typename MapT::const_iterator it) const { return it->first; }
+
+ T get_to(typename MapT::const_iterator it) const { return it->second.To; }
+
+ typename MapT::iterator insert_range(T from, T to)
+ {
+ auto m = Map.emplace(from, to).first;
+ m->second.SizeIt = Sizes.emplace(calc_size(from, to), m);
+ return m;
+ }
+
+ typename MapT::iterator erase_range(typename MapT::iterator it)
+ {
+ Sizes.erase(it->second.SizeIt);
+ return Map.erase(it);
+ }
+
+ typename MapT::const_iterator erase_range(typename MapT::const_iterator it)
+ {
+ Sizes.erase(it->second.SizeIt);
+ return Map.erase(it);
+ }
+
+ typename SizeMapT::const_iterator erase_range_by_size(typename SizeMapT::const_iterator it)
+ {
+ Map.erase(it->second);
+ return Sizes.erase(it);
+ }
+
+ void bisect_range(typename MapT::iterator it, T from, T to)
+ {
+ assert(get_from(it) < from);
+ assert(get_from(it) < to);
+ assert(get_to(it) > from);
+ assert(get_to(it) > to);
+ assert(from < to);
+ T itto = get_to(it);
+ reduce_to(it, from);
+ insert_range(to, itto);
+ }
+
+ typename MapT::iterator reduce_from(typename MapT::iterator it, T from)
+ {
+ assert(get_from(it) < from);
+ T itto = get_to(it);
+ erase_range(it);
+ return insert_range(from, itto);
+ }
+
+ void maybe_expand_to(typename MapT::iterator it, T to)
+ {
+ if (to <= get_to(it))
+ return;
+
+ expand_to(it, to);
+ }
+
+ void expand_to(typename MapT::iterator it, T to)
+ {
+ assert(get_to(it) < to);
+ it->second.To = to;
+ Sizes.erase(it->second.SizeIt);
+ it->second.SizeIt = Sizes.emplace(calc_size(get_from(it), to), it);
+ }
+
+ void reduce_to(typename MapT::iterator it, T to)
+ {
+ assert(get_to(it) > to);
+ it->second.To = to;
+ Sizes.erase(it->second.SizeIt);
+ it->second.SizeIt = Sizes.emplace(calc_size(get_from(it), to), it);
+ }
+
+ void merge_from_iterator_to_value(typename MapT::iterator inserted, typename MapT::iterator bound,
+ T to)
+ {
+ // Erase all ranges that overlap the inserted while updating the upper end.
+ while (bound != Map.end() && get_from(bound) <= to)
+ {
+ maybe_expand_to(inserted, get_to(bound));
+ bound = erase_range(bound);
+ }
+ }
+
+ void erase_from_iterator_to_value(typename MapT::iterator bound, T to)
+ {
+ // Assumption: Given bound starts at or after the 'from' value of the range to erase.
+ while (true)
+ {
+ // Given range starts before stored range.
+ if (to <= get_from(bound))
+ {
+ // Range ends before this range too, nothing to do.
+ return;
+ }
+
+ if (to < get_to(bound))
+ {
+ // Range ends in the middle of current range, reduce current.
+ reduce_from(bound, to);
+ return;
+ }
+
+ if (to == get_to(bound))
+ {
+ // Range ends exactly with current range, erase current.
+ erase_range(bound);
+ return;
+ }
+
+ // Range ends later than current range.
+ // First erase current, then loop to check the range(s) after this one too.
+ bound = erase_range(bound);
+ if (bound == Map.end())
+ {
+ // Unless that was the last range, in which case there's nothing else to do.
+ return;
+ }
+ }
+ }
+};
+} // namespace Common
diff --git a/Source/Core/Core/CMakeLists.txt b/Source/Core/Core/CMakeLists.txt
index e2ae3e9919..b81558e274 100644
--- a/Source/Core/Core/CMakeLists.txt
+++ b/Source/Core/Core/CMakeLists.txt
@@ -660,7 +660,6 @@ PUBLIC
inputcommon
MbedTLS::mbedtls
pugixml
- RangeSet::RangeSet
sfml-network
videonull
videoogl
diff --git a/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h b/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h
index 12e9c17c50..dd940e89a2 100644
--- a/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h
+++ b/Source/Core/Core/PowerPC/CachedInterpreter/CachedInterpreter.h
@@ -5,9 +5,8 @@
#include <cstddef>
-#include <rangeset/rangesizeset.h>
-
#include "Common/CommonTypes.h"
+#include "Common/RangeSizeSet.h"
#include "Core/PowerPC/CachedInterpreter/CachedInterpreterBlockCache.h"
#include "Core/PowerPC/CachedInterpreter/CachedInterpreterEmitter.h"
#include "Core/PowerPC/JitCommon/JitBase.h"
@@ -112,7 +111,7 @@ private:
static s32 CheckIdle(PowerPC::PowerPCState& ppc_state, const CheckIdleOperands& operands);
static s32 CheckIdle(std::ostream& stream, const CheckIdleOperands& operands);
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges;
+ Common::RangeSizeSet<u8*> m_free_ranges;
CachedInterpreterBlockCache m_block_cache;
};
diff --git a/Source/Core/Core/PowerPC/Jit64/Jit.h b/Source/Core/Core/PowerPC/Jit64/Jit.h
index 2d8ef2be55..da1be2db04 100644
--- a/Source/Core/Core/PowerPC/Jit64/Jit.h
+++ b/Source/Core/Core/PowerPC/Jit64/Jit.h
@@ -19,9 +19,8 @@
#include <optional>
-#include <rangeset/rangesizeset.h>
-
#include "Common/CommonTypes.h"
+#include "Common/RangeSizeSet.h"
#include "Common/x64Emitter.h"
#include "Core/PowerPC/Jit64/JitAsm.h"
#include "Core/PowerPC/Jit64/RegCache/FPURegCache.h"
@@ -295,8 +294,8 @@ private:
Jit64AsmRoutineManager asm_routines{*this};
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges_near;
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges_far;
+ Common::RangeSizeSet<u8*> m_free_ranges_near;
+ Common::RangeSizeSet<u8*> m_free_ranges_far;
const bool m_im_here_debug = false;
const bool m_im_here_log = false;
diff --git a/Source/Core/Core/PowerPC/JitArm64/Jit.h b/Source/Core/Core/PowerPC/JitArm64/Jit.h
index 5b42dff3dd..9c23112e1c 100644
--- a/Source/Core/Core/PowerPC/JitArm64/Jit.h
+++ b/Source/Core/Core/PowerPC/JitArm64/Jit.h
@@ -7,9 +7,8 @@
#include <map>
#include <optional>
-#include <rangeset/rangesizeset.h>
-
#include "Common/Arm64Emitter.h"
+#include "Common/RangeSizeSet.h"
#include "Core/PowerPC/JitArm64/JitArm64Cache.h"
#include "Core/PowerPC/JitArm64/JitArm64_RegCache.h"
@@ -431,10 +430,10 @@ protected:
u8* m_near_code_end = nullptr;
bool m_near_code_write_failed = false;
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges_near_0;
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges_near_1;
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges_far_0;
- HyoutaUtilities::RangeSizeSet<u8*> m_free_ranges_far_1;
+ Common::RangeSizeSet<u8*> m_free_ranges_near_0;
+ Common::RangeSizeSet<u8*> m_free_ranges_near_1;
+ Common::RangeSizeSet<u8*> m_free_ranges_far_0;
+ Common::RangeSizeSet<u8*> m_free_ranges_far_1;
std::unique_ptr<HostDisassembler> m_disassembler;
};
diff --git a/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp b/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp
index c9050be730..a7226b2ae9 100644
--- a/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp
+++ b/Source/Core/Core/PowerPC/JitCommon/JitCache.cpp
@@ -31,8 +31,7 @@ using namespace Gen;
bool JitBlock::OverlapsPhysicalRange(u32 address, u32 length) const
{
- return physical_addresses.lower_bound(address) !=
- physical_addresses.lower_bound(address + length);
+ return physical_addresses.overlaps(address, address + length);
}
void JitBlock::ProfileData::BeginProfiling(ProfileData* data)
@@ -171,10 +170,13 @@ void JitBaseBlockCache::FinalizeBlock(JitBlock& block, bool block_link,
original_buffer_transform_view.end());
}
- for (u32 addr : block.physical_addresses)
+ for (auto [range_start, range_end] : block.physical_addresses)
{
- valid_block.Set(addr / 32);
- block_range_map[addr & BLOCK_RANGE_MAP_MASK].insert(&block);
+ for (u32 i = range_start & ~31; i < range_end; i += 32)
+ valid_block.Set(i / 32);
+
+ for (u32 i = range_start & BLOCK_RANGE_MAP_MASK; i < range_end; i += BLOCK_RANGE_SIZE)
+ block_range_map[i].insert(&block);
}
if (block_link)
@@ -362,9 +364,15 @@ void JitBaseBlockCache::ErasePhysicalRange(u32 address, u32 length)
{
// If the block overlaps, also remove all other occupied slots in the other macro blocks.
// This will leak empty macro blocks, but they may be reused or cleared later on.
- for (u32 addr : block->physical_addresses)
- if ((addr & BLOCK_RANGE_MAP_MASK) != start->first)
- block_range_map[addr & BLOCK_RANGE_MAP_MASK].erase(block);
+ for (auto [range_start, range_end] : block->physical_addresses)
+ {
+ DEBUG_ASSERT(range_start != range_end);
+ for (u32 i = range_start & BLOCK_RANGE_MAP_MASK; i < range_end; i += BLOCK_RANGE_SIZE)
+ {
+ if (i != start->first)
+ block_range_map[i].erase(block);
+ }
+ }
// And remove the block.
DestroyBlock(*block);
@@ -404,8 +412,11 @@ void JitBaseBlockCache::EraseSingleBlock(const JitBlock& block)
JitBlock& mutable_block = block_map_iter->second;
- for (const u32 addr : mutable_block.physical_addresses)
- block_range_map[addr & BLOCK_RANGE_MAP_MASK].erase(&mutable_block);
+ for (auto [range_start, range_end] : mutable_block.physical_addresses)
+ {
+ for (u32 i = range_start & BLOCK_RANGE_MAP_MASK; i < range_end; i += BLOCK_RANGE_SIZE)
+ block_range_map[i].erase(&mutable_block);
+ }
DestroyBlock(mutable_block);
block_map.erase(block_map_iter); // The original JitBlock reference is now dangling.
diff --git a/Source/Core/Core/PowerPC/JitCommon/JitCache.h b/Source/Core/Core/PowerPC/JitCommon/JitCache.h
index 9d227d62b0..703fb4069e 100644
--- a/Source/Core/Core/PowerPC/JitCommon/JitCache.h
+++ b/Source/Core/Core/PowerPC/JitCommon/JitCache.h
@@ -10,13 +10,13 @@
#include <functional>
#include <map>
#include <memory>
-#include <set>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "Common/CommonTypes.h"
+#include "Common/RangeSet.h"
#include "Core/HW/Memmap.h"
#include "Core/PowerPC/Gekko.h"
#include "Core/PowerPC/PPCAnalyst.h"
@@ -101,7 +101,7 @@ struct JitBlock : public JitBlockData
std::vector<LinkData> linkData;
// This set stores all physical addresses of all occupied instructions.
- std::set<u32> physical_addresses;
+ Common::RangeSet<u32> physical_addresses;
// This is only available when debugging is enabled. It is a trimmed-down copy of the
// PPCAnalyst::CodeBuffer used to recompile this block, including repeat instructions.
@@ -218,7 +218,8 @@ private:
// Range of overlapping code indexed by a masked physical address.
// This is used for invalidation of memory regions. The range is grouped
// in macro blocks of each 0x100 bytes.
- static constexpr u32 BLOCK_RANGE_MAP_MASK = ~(0x100 - 1);
+ static constexpr u32 BLOCK_RANGE_SIZE = 0x100;
+ static constexpr u32 BLOCK_RANGE_MAP_MASK = ~(BLOCK_RANGE_SIZE - 1);
std::map<u32, std::unordered_set<JitBlock*>> block_range_map;
// This bitsets shows which cachelines overlap with any blocks.
diff --git a/Source/Core/Core/PowerPC/PPCAnalyst.cpp b/Source/Core/Core/PowerPC/PPCAnalyst.cpp
index 8c35ad4923..40b974b0d8 100644
--- a/Source/Core/Core/PowerPC/PPCAnalyst.cpp
+++ b/Source/Core/Core/PowerPC/PPCAnalyst.cpp
@@ -849,7 +849,8 @@ u32 PPCAnalyzer::Analyze(u32 address, CodeBlock* block, CodeBuffer* buffer,
code[i].inst = inst;
code[i].skip = false;
block->m_stats->numCycles += opinfo->num_cycles;
- block->m_physical_addresses.insert(result.physical_address);
+ block->m_physical_addresses.insert(result.physical_address,
+ result.physical_address + sizeof(UGeckoInstruction));
SetInstructionStats(block, &code[i], opinfo);
diff --git a/Source/Core/Core/PowerPC/PPCAnalyst.h b/Source/Core/Core/PowerPC/PPCAnalyst.h
index ed0242498b..879bd06111 100644
--- a/Source/Core/Core/PowerPC/PPCAnalyst.h
+++ b/Source/Core/Core/PowerPC/PPCAnalyst.h
@@ -5,11 +5,11 @@
#include <algorithm>
#include <cstddef>
-#include <set>
#include <vector>
#include "Common/BitSet.h"
#include "Common/CommonTypes.h"
+#include "Common/RangeSet.h"
#include "Core/PowerPC/PPCTables.h"
class PPCSymbolDB;
@@ -129,7 +129,7 @@ struct CodeBlock
BitSet32 m_gpr_inputs;
// Which memory locations are occupied by this block.
- std::set<u32> m_physical_addresses;
+ Common::RangeSet<u32> m_physical_addresses;
};
class PPCAnalyzer
diff --git a/Source/Core/DolphinLib.props b/Source/Core/DolphinLib.props
index 34e4b83f13..c6c9c485dd 100644
--- a/Source/Core/DolphinLib.props
+++ b/Source/Core/DolphinLib.props
@@ -154,6 +154,8 @@
<ClInclude Include="Common\Projection.h" />
<ClInclude Include="Common\QoSSession.h" />
<ClInclude Include="Common\Random.h" />
+ <ClInclude Include="Common\RangeSet.h" />
+ <ClInclude Include="Common\RangeSizeSet.h" />
<ClInclude Include="Common\scmrev.h" />
<ClInclude Include="Common\ScopeGuard.h" />
<ClInclude Include="Common\SDCardUtil.h" />
diff --git a/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp b/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp
index 25701d26f4..61f5851380 100644
--- a/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp
+++ b/Source/Core/DolphinQt/Debugger/JitBlockTableModel.cpp
@@ -236,7 +236,8 @@ QVariant JitBlockTableModel::DisplayRoleData(const QModelIndex& index) const
case Column::CodeBufferSize:
return QString::number(jit_block.originalSize * sizeof(UGeckoInstruction));
case Column::RepeatInstructions:
- return QString::number(jit_block.originalSize - jit_block.physical_addresses.size());
+ return QString::number(jit_block.originalSize - jit_block.physical_addresses.get_stats().first /
+ sizeof(UGeckoInstruction));
case Column::HostNearCodeSize:
return QString::number(jit_block.near_end - jit_block.near_begin);
case Column::HostFarCodeSize:
@@ -329,7 +330,9 @@ QVariant JitBlockTableModel::SortRoleData(const QModelIndex& index) const
case Column::CodeBufferSize:
return static_cast<qulonglong>(jit_block.originalSize);
case Column::RepeatInstructions:
- return static_cast<qulonglong>(jit_block.originalSize - jit_block.physical_addresses.size());
+ return static_cast<qulonglong>(jit_block.originalSize -
+ jit_block.physical_addresses.get_stats().first /
+ sizeof(UGeckoInstruction));
case Column::HostNearCodeSize:
return static_cast<qulonglong>(jit_block.near_end - jit_block.near_begin);
case Column::HostFarCodeSize:
generated by cgit v1.2.3 (git 2.25.1) at 2026-08-03 07:49:31 +0000