From c1b7a40893e4b8f4601a5d8d449dd08ec59c0b2b Mon Sep 17 00:00:00 2001 From: Nikos Nikoleris Date: Sun, 26 May 2019 23:33:48 +0100 Subject: base: Extend AddrRange to support more flexible addressing Previously an AddrRange could express interleaving using a number of consecutive bits and in additional optionally a second number of consecutive bits. The two sets of consecutive bits would be xored and matched against a value to determine if an address is in the AddrRange. For example: sel[0] = a[8] ^ a[12] sel[1] = a[9] ^ a[13] where sel == intlvMatch This change extends AddrRange to allow more flexible interleavings with an abritary number of set of bits which do not need be consecutive. For example: sel[0] = a[8] ^ a[11] ^ a[13] sel[1] = a[15] ^ a[17] ^ a[19] where sel == intlvMatch Change-Id: I42220a6d5011a31f0560535762a25bfc823c3ebb Signed-off-by: Nikos Nikoleris Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/19130 Maintainer: Jason Lowe-Power Tested-by: kokoro Reviewed-by: Daniel Carvalho --- src/base/addr_range.hh | 278 +++++++++++++++++++++++++++----------------- src/python/pybind11/core.cc | 1 - 2 files changed, 174 insertions(+), 105 deletions(-) diff --git a/src/base/addr_range.hh b/src/base/addr_range.hh index 842f01ad9..1d2dc731f 100644 --- a/src/base/addr_range.hh +++ b/src/base/addr_range.hh @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012, 2014, 2017-2018 ARM Limited + * Copyright (c) 2012, 2014, 2017-2019 ARM Limited * All rights reserved * * The license below extends only to copyright in the software and shall @@ -63,9 +63,8 @@ * allowing a number of bits of the address, at an arbitrary bit * position, to be used as interleaving bits with an associated * matching value. In addition, to prevent uniformly strided address - * patterns from a very biased interleaving, we also allow basic - * XOR-based hashing by specifying an additional set of bits to XOR - * with before matching. + * patterns from a very biased interleaving, we also allow XOR-based + * hashing by specifying a set of bits to XOR with before matching. * * The AddrRange is also able to coalesce a number of interleaved * ranges to a contiguous range. @@ -80,59 +79,124 @@ class AddrRange Addr _start; Addr _end; - /// The high bit of the slice that is used for interleaving - uint8_t intlvHighBit; - - /// The high bit of the slice used to XOR hash the value we match - /// against, set to 0 to disable. - uint8_t xorHighBit; - - /// The number of bits used for interleaving, set to 0 to disable - uint8_t intlvBits; + /** + * Each mask determines the bits we need to xor to get one bit of + * sel. The first (0) mask is used to get the LSB and the last for + * the MSB of sel. + */ + std::vector masks; - /// The value to compare the slice addr[high:(high - bits + 1)] - /// with. + /** The value to compare sel with. */ uint8_t intlvMatch; public: AddrRange() - : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), - intlvMatch(0) + : _start(1), _end(0), intlvMatch(0) {} + /** + * Construct an address range + * + * If the user provides a non empty vector of masks then the + * address range is interleaved. Each mask determines a set of + * bits that are xored to determine one bit of the sel value, + * starting from the least significant bit (i.e., masks[0] + * determines the least significant bit of sel, ...). If sel + * matches the provided _intlv_match then the address a is in the + * range. + * + * For example if the input mask is + * _masks = { 1 << 8 | 1 << 11 | 1 << 13, + * 1 << 15 | 1 << 17 | 1 << 19} + * + * Then a belongs to the address range if + * _start <= a < _end + * and + * sel == _intlv_match + * where + * sel[0] = a[8] ^ a[11] ^ a[13] + * sel[1] = a[15] ^ a[17] ^ a[19] + * + * @param _start The start address of this range + * @param _end The end address of this range (not included in the range) + * @param _masks The input vector of masks + * @param intlv_math The matching value of the xor operations + */ + AddrRange(Addr _start, Addr _end, const std::vector &_masks, + uint8_t _intlv_match) + : _start(_start), _end(_end), masks(_masks), + intlvMatch(_intlv_match) + { + // sanity checks + fatal_if(!masks.empty() && _intlv_match >= ULL(1) << masks.size(), + "Match value %d does not fit in %d interleaving bits\n", + _intlv_match, masks.size()); + } + + /** + * Legacy constructor of AddrRange + * + * If the user provides a non-zero value in _intlv_high_bit the + * address range is interleaved. + * + * An address a belongs to the address range if + * _start <= a < _end + * and + * sel == _intlv_match + * where + * sel = sel1 ^ sel2 + * sel1 = a[_intlv_low_bit:_intlv_high_bit] + * sel2 = a[_xor_low_bit:_xor_high_bit] + * _intlv_low_bit = _intlv_high_bit - intv_bits + * _xor_low_bit = _xor_high_bit - intv_bits + * + * @param _start The start address of this range + * @param _end The end address of this range (not included in the range) + * @param _intlv_high_bit The MSB of the intlv bits (disabled if 0) + * @param _xor_high_bit The MSB of the xor bit (disabled if 0) + * @param intlv_math The matching value of the xor operations + */ AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, uint8_t _xor_high_bit, uint8_t _intlv_bits, uint8_t _intlv_match) - : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), - xorHighBit(_xor_high_bit), intlvBits(_intlv_bits), + : _start(_start), _end(_end), masks(_intlv_bits), intlvMatch(_intlv_match) { // sanity checks - fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits, + fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits, "Match value %d does not fit in %d interleaving bits\n", - intlvMatch, intlvBits); + _intlv_match, _intlv_bits); // ignore the XOR bits if not interleaving - if (intlvBits && xorHighBit) { - if (xorHighBit == intlvHighBit) { + if (_intlv_bits && _xor_high_bit) { + if (_xor_high_bit == _intlv_high_bit) { fatal("XOR and interleave high bit must be different\n"); - } else if (xorHighBit > intlvHighBit) { - if ((xorHighBit - intlvHighBit) < intlvBits) + } else if (_xor_high_bit > _intlv_high_bit) { + if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits) fatal("XOR and interleave high bit must be at least " - "%d bits apart\n", intlvBits); + "%d bits apart\n", _intlv_bits); } else { - if ((intlvHighBit - xorHighBit) < intlvBits) { + if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) { fatal("Interleave and XOR high bit must be at least " - "%d bits apart\n", intlvBits); + "%d bits apart\n", _intlv_bits); } } } + + for (auto i = 0; i < _intlv_bits; i++) { + uint8_t bit1 = _intlv_high_bit - i; + Addr mask = (1ULL << bit1); + if (_xor_high_bit) { + uint8_t bit2 = _xor_high_bit - i; + mask |= (1ULL << bit2); + } + masks[_intlv_bits - i - 1] = mask; + } } AddrRange(Addr _start, Addr _end) - : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0), - intlvBits(0), intlvMatch(0) + : _start(_start), _end(_end), intlvMatch(0) {} /** @@ -142,38 +206,31 @@ class AddrRange * @param ranges Interleaved ranges to be merged */ AddrRange(const std::vector& ranges) - : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), - intlvMatch(0) + : _start(1), _end(0), intlvMatch(0) { if (!ranges.empty()) { // get the values from the first one and check the others _start = ranges.front()._start; _end = ranges.front()._end; - intlvHighBit = ranges.front().intlvHighBit; - xorHighBit = ranges.front().xorHighBit; - intlvBits = ranges.front().intlvBits; + masks = ranges.front().masks; - if (ranges.size() != (ULL(1) << intlvBits)) + if (ranges.size() != (ULL(1) << masks.size())) fatal("Got %d ranges spanning %d interleaving bits\n", - ranges.size(), intlvBits); + ranges.size(), masks.size()); uint8_t match = 0; for (const auto& r : ranges) { if (!mergesWith(r)) fatal("Can only merge ranges with the same start, end " - "and interleaving bits\n"); + "and interleaving bits, %s %s\n", to_string(), + r.to_string()); if (r.intlvMatch != match) fatal("Expected interleave match %d but got %d when " "merging\n", match, r.intlvMatch); ++match; } - - // our range is complete and we can turn this into a - // non-interleaved range - intlvHighBit = 0; - xorHighBit = 0; - intlvBits = 0; + masks.clear(); } } @@ -182,12 +239,7 @@ class AddrRange * * @return true if interleaved */ - bool interleaved() const { return intlvBits != 0; } - - /** - * Determine if the range interleaving is hashed or not. - */ - bool hashed() const { return interleaved() && xorHighBit != 0; } + bool interleaved() const { return masks.size() > 0; } /** * Determing the interleaving granularity of the range. @@ -197,13 +249,12 @@ class AddrRange uint64_t granularity() const { if (interleaved()) { - const uint8_t intlv_low_bit = intlvHighBit - intlvBits + 1; - if (hashed()) { - const uint8_t xor_low_bit = xorHighBit - intlvBits + 1; - return ULL(1) << std::min(intlv_low_bit, xor_low_bit); - } else { - return ULL(1) << intlv_low_bit; + auto combined_mask = 0; + for (auto mask: masks) { + combined_mask |= mask; } + const uint8_t lowest_bit = ctz64(combined_mask); + return ULL(1) << lowest_bit; } else { return size(); } @@ -215,7 +266,7 @@ class AddrRange * * @return The number of stripes spanned by the interleaving bits */ - uint32_t stripes() const { return ULL(1) << intlvBits; } + uint32_t stripes() const { return ULL(1) << masks.size(); } /** * Get the size of the address range. For a case where @@ -224,7 +275,7 @@ class AddrRange */ Addr size() const { - return (_end - _start + 1) >> intlvBits; + return (_end - _start + 1) >> masks.size(); } /** @@ -250,20 +301,20 @@ class AddrRange std::string to_string() const { if (interleaved()) { - if (hashed()) { - return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d", - _start, _end, - intlvHighBit, intlvHighBit - intlvBits + 1, - xorHighBit, xorHighBit - intlvBits + 1, - intlvMatch); - } else { - return csprintf("[%#llx : %#llx], [%d : %d] = %d", - _start, _end, - intlvHighBit, intlvHighBit - intlvBits + 1, - intlvMatch); + std::string str; + for (int i = 0; i < masks.size(); i++) { + str += " "; + Addr mask = masks[i]; + while (mask) { + auto bit = ctz64(mask); + mask &= ~(1ULL << bit); + str += csprintf("a[%d]^", bit); + } + str += csprintf("\b=%d", bits(intlvMatch, i)); } + return csprintf("[%#llx:%#llx]%s", _start, _end, str); } else { - return csprintf("[%#llx : %#llx]", _start, _end); + return csprintf("[%#llx:%#llx]", _start, _end); } } @@ -278,9 +329,7 @@ class AddrRange bool mergesWith(const AddrRange& r) const { return r._start == _start && r._end == _end && - r.intlvHighBit == intlvHighBit && - r.xorHighBit == xorHighBit && - r.intlvBits == intlvBits; + r.masks == masks; } /** @@ -352,17 +401,17 @@ class AddrRange // no interleaving, or with interleaving also if the selected // bits from the address match the interleaving value bool in_range = a >= _start && a <= _end; - if (!interleaved()) { - return in_range; - } else if (in_range) { - if (!hashed()) { - return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == - intlvMatch; - } else { - return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^ - bits(a, xorHighBit, xorHighBit - intlvBits + 1)) == - intlvMatch; + if (in_range) { + auto sel = 0; + for (int i = 0; i < masks.size(); i++) { + Addr masked = a & masks[i]; + // The result of an xor operation is 1 if the number + // of bits set is odd or 0 othersize, thefore it + // suffices to count the number of bits set to + // determine the i-th bit of sel. + sel |= (popCount(masked) % 2) << i; } + return sel == intlvMatch; } return false; } @@ -370,26 +419,49 @@ class AddrRange /** * Remove the interleaving bits from an input address. * - * This function returns a new address that doesn't have the bits - * that are use to determine which of the interleaved ranges it - * belongs to. + * This function returns a new address in a continous range [ + * start, start + size / intlv_bits). We can achieve this by + * discarding the LSB in each mask. + * + * e.g., if the input address is of the form: + * ------------------------------------ + * | a_high | x1 | a_mid | x0 | a_low | + * ------------------------------------ + * where x0 is the LSB set in masks[0] + * and x1 is the LSB set in masks[1] * - * e.g., if the input address is: - * ------------------------------- - * | prefix | intlvBits | suffix | - * ------------------------------- * this function will return: - * ------------------------------- - * | 0 | prefix | suffix | - * ------------------------------- + * --------------------------------- + * | 0 | a_high | a_mid | a_low | + * --------------------------------- * * @param the input address - * @return the address without the interleaved bits + * @return the new address */ - inline Addr removeIntlvBits(const Addr &a) const + inline Addr removeIntlvBits(Addr a) const { - const auto intlv_low_bit = intlvHighBit - intlvBits + 1; - return insertBits(a >> intlvBits, intlv_low_bit - 1, 0, a); + // Get the LSB set from each mask + int masks_lsb[masks.size()]; + for (int i = 0; i < masks.size(); i++) { + masks_lsb[i] = ctz64(masks[i]); + } + + // we need to sort the list of bits we will discard as we + // discard them one by one starting. + std::sort(masks_lsb, masks_lsb + masks.size()); + + for (int i = 0; i < masks.size(); i++) { + const int intlv_bit = masks_lsb[i]; + if (intlv_bit > 0) { + // on every iteration we remove one bit from the input + // address, and therefore the lowest invtl_bit has + // also shifted to the right by i positions. + a = insertBits(a >> 1, intlv_bit - i - 1, 0, a); + } else { + a >>= 1; + } + } + return a; } /** @@ -435,13 +507,11 @@ class AddrRange bool operator==(const AddrRange& r) const { - if (_start != r._start) return false; - if (_end != r._end) return false; - if (intlvBits != r.intlvBits) return false; - if (intlvBits != 0) { - if (intlvHighBit != r.intlvHighBit) return false; - if (intlvMatch != r.intlvMatch) return false; - } + if (_start != r._start) return false; + if (_end != r._end) return false; + if (masks != r.masks) return false; + if (intlvMatch != r.intlvMatch) return false; + return true; } diff --git a/src/python/pybind11/core.cc b/src/python/pybind11/core.cc index 57fcb94cb..fad7a7daa 100644 --- a/src/python/pybind11/core.cc +++ b/src/python/pybind11/core.cc @@ -154,7 +154,6 @@ init_range(py::module &m_native) .def("__str__", &AddrRange::to_string) .def("interleaved", &AddrRange::interleaved) - .def("hashed", &AddrRange::hashed) .def("granularity", &AddrRange::granularity) .def("stripes", &AddrRange::stripes) .def("size", &AddrRange::size) -- cgit v1.2.3