Nikos Nikoleris has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/19130
Change subject: base: Extend AddrRange to support more flexible addressing
......................................................................
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 <[email protected]>
---
M src/base/addr_range.hh
1 file changed, 120 insertions(+), 96 deletions(-)
diff --git a/src/base/addr_range.hh b/src/base/addr_range.hh
index 842f01a..0ae464c 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,73 @@
Addr _start;
Addr _end;
- /// The high bit of the slice that is used for interleaving
- uint8_t intlvHighBit;
+ /**
+ * 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<Addr> masks;
- /// 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;
-
- /// 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)
{}
+ AddrRange(Addr _start, Addr _end, const std::vector<Addr> &_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());
+ }
+
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 +155,31 @@
* @param ranges Interleaved ranges to be merged
*/
AddrRange(const std::vector<AddrRange>& 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) << ranges.front().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 +188,22 @@
*
* @return true if interleaved
*/
- bool interleaved() const { return intlvBits != 0; }
+ bool interleaved() const { return masks.size() > 0; }
/**
* Determine if the range interleaving is hashed or not.
*/
- bool hashed() const { return interleaved() && xorHighBit != 0; }
+ bool hashed() const
+ {
+ if (interleaved()) {
+ for (Addr mask: masks) {
+ if (popCount(mask) > 1) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
/**
* Determing the interleaving granularity of the range.
@@ -197,13 +213,12 @@
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 +230,7 @@
*
* @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 +239,7 @@
*/
Addr size() const
{
- return (_end - _start + 1) >> intlvBits;
+ return (_end - _start + 1) >> masks.size();
}
/**
@@ -250,20 +265,20 @@
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 +293,7 @@
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 +365,13 @@
// 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];
+ sel |= (popCount(masked) % 2) << i;
}
+ return sel == intlvMatch;
}
return false;
}
@@ -374,22 +383,39 @@
* that are use to determine which of the interleaved ranges it
* belongs to.
*
- * e.g., if the input address is:
- * -------------------------------
- * | prefix | intlvBits | suffix |
- * -------------------------------
+ * e.g., if the input address is of the form:
+ * ------------------------------------
+ * | a_high | x0 | a_mid | x1 | a_low |
+ * ------------------------------------
* 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
*/
- 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);
+ int masks_lsb[masks.size()];
+ for (int i = 0; i < masks.size(); i++) {
+ masks_lsb[i] = ctz64(masks[i]);
+ }
+
+ 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 +461,11 @@
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;
}
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/19130
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I42220a6d5011a31f0560535762a25bfc823c3ebb
Gerrit-Change-Number: 19130
Gerrit-PatchSet: 1
Gerrit-Owner: Nikos Nikoleris <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
