2c2
< * Copyright (c) 2012, 2014, 2017-2018 ARM Limited
---
> * Copyright (c) 2012, 2014, 2017-2019 ARM Limited
66,68c66,67
< * 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.
83,84c82,87
< /// 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;
86,94c89
< /// 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. */
100,101c95
< : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
< intlvMatch(0)
---
> : _start(1), _end(0), intlvMatch(0)
103a98,159
> /**
> * 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<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());
> }
>
> /**
> * 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
> */
107,108c163
< : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
< xorHighBit(_xor_high_bit), intlvBits(_intlv_bits),
---
> : _start(_start), _end(_end), masks(_intlv_bits),
112c167
< fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits,
---
> fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits,
114c169
< intlvMatch, intlvBits);
---
> _intlv_match, _intlv_bits);
117,118c172,173
< if (intlvBits && xorHighBit) {
< if (xorHighBit == intlvHighBit) {
---
> if (_intlv_bits && _xor_high_bit) {
> if (_xor_high_bit == _intlv_high_bit) {
120,121c175,176
< } 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)
123c178
< "%d bits apart\n", intlvBits);
---
> "%d bits apart\n", _intlv_bits);
125c180
< if ((intlvHighBit - xorHighBit) < intlvBits) {
---
> if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) {
127c182
< "%d bits apart\n", intlvBits);
---
> "%d bits apart\n", _intlv_bits);
130a186,195
>
> 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;
> }
134,135c199
< : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0),
< intlvBits(0), intlvMatch(0)
---
> : _start(_start), _end(_end), intlvMatch(0)
145,146c209
< : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
< intlvMatch(0)
---
> : _start(1), _end(0), intlvMatch(0)
152,154c215
< intlvHighBit = ranges.front().intlvHighBit;
< xorHighBit = ranges.front().xorHighBit;
< intlvBits = ranges.front().intlvBits;
---
> masks = ranges.front().masks;
156c217
< if (ranges.size() != (ULL(1) << intlvBits))
---
> if (ranges.size() != (ULL(1) << masks.size()))
158c219
< ranges.size(), intlvBits);
---
> ranges.size(), masks.size());
164c225,226
< "and interleaving bits\n");
---
> "and interleaving bits, %s %s\n", to_string(),
> r.to_string());
171,176c233
<
< // our range is complete and we can turn this into a
< // non-interleaved range
< intlvHighBit = 0;
< xorHighBit = 0;
< intlvBits = 0;
---
> masks.clear();
185c242
< bool interleaved() const { return intlvBits != 0; }
---
> bool interleaved() const { return masks.size() > 0; }
188,192d244
< * Determine if the range interleaving is hashed or not.
< */
< bool hashed() const { return interleaved() && xorHighBit != 0; }
<
< /**
200,205c252,254
< 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;
206a256,257
> const uint8_t lowest_bit = ctz64(combined_mask);
> return ULL(1) << lowest_bit;
218c269
< uint32_t stripes() const { return ULL(1) << intlvBits; }
---
> uint32_t stripes() const { return ULL(1) << masks.size(); }
227c278
< return (_end - _start + 1) >> intlvBits;
---
> return (_end - _start + 1) >> masks.size();
253,263c304,313
< 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));
264a315
> return csprintf("[%#llx:%#llx]%s", _start, _end, str);
266c317
< return csprintf("[%#llx : %#llx]", _start, _end);
---
> return csprintf("[%#llx:%#llx]", _start, _end);
281,283c332
< r.intlvHighBit == intlvHighBit &&
< r.xorHighBit == xorHighBit &&
< r.intlvBits == intlvBits;
---
> r.masks == masks;
355,364c404,412
< 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;
365a414
> return sel == intlvMatch;
373,375c422,424
< * 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.
377,380c426,432
< * e.g., if the input address is:
< * -------------------------------
< * | prefix | intlvBits | suffix |
< * -------------------------------
---
> * 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]
> *
382,384c434,436
< * -------------------------------
< * | 0 | prefix | suffix |
< * -------------------------------
---
> * ---------------------------------
> * | 0 | a_high | a_mid | a_low |
> * ---------------------------------
387c439
< * @return the address without the interleaved bits
---
> * @return the new address
389c441
< inline Addr removeIntlvBits(const Addr &a) const
---
> inline Addr removeIntlvBits(Addr a) const
391,392c443,464
< 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;
438,444c510,514
< 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;
>
< * Copyright (c) 2012, 2014, 2017-2018 ARM Limited
---
> * Copyright (c) 2012, 2014, 2017-2019 ARM Limited
66,68c66,67
< * 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.
83,84c82,87
< /// 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;
86,94c89
< /// 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. */
100,101c95
< : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
< intlvMatch(0)
---
> : _start(1), _end(0), intlvMatch(0)
103a98,159
> /**
> * 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<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());
> }
>
> /**
> * 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
> */
107,108c163
< : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
< xorHighBit(_xor_high_bit), intlvBits(_intlv_bits),
---
> : _start(_start), _end(_end), masks(_intlv_bits),
112c167
< fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits,
---
> fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits,
114c169
< intlvMatch, intlvBits);
---
> _intlv_match, _intlv_bits);
117,118c172,173
< if (intlvBits && xorHighBit) {
< if (xorHighBit == intlvHighBit) {
---
> if (_intlv_bits && _xor_high_bit) {
> if (_xor_high_bit == _intlv_high_bit) {
120,121c175,176
< } 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)
123c178
< "%d bits apart\n", intlvBits);
---
> "%d bits apart\n", _intlv_bits);
125c180
< if ((intlvHighBit - xorHighBit) < intlvBits) {
---
> if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) {
127c182
< "%d bits apart\n", intlvBits);
---
> "%d bits apart\n", _intlv_bits);
130a186,195
>
> 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;
> }
134,135c199
< : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0),
< intlvBits(0), intlvMatch(0)
---
> : _start(_start), _end(_end), intlvMatch(0)
145,146c209
< : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0),
< intlvMatch(0)
---
> : _start(1), _end(0), intlvMatch(0)
152,154c215
< intlvHighBit = ranges.front().intlvHighBit;
< xorHighBit = ranges.front().xorHighBit;
< intlvBits = ranges.front().intlvBits;
---
> masks = ranges.front().masks;
156c217
< if (ranges.size() != (ULL(1) << intlvBits))
---
> if (ranges.size() != (ULL(1) << masks.size()))
158c219
< ranges.size(), intlvBits);
---
> ranges.size(), masks.size());
164c225,226
< "and interleaving bits\n");
---
> "and interleaving bits, %s %s\n", to_string(),
> r.to_string());
171,176c233
<
< // our range is complete and we can turn this into a
< // non-interleaved range
< intlvHighBit = 0;
< xorHighBit = 0;
< intlvBits = 0;
---
> masks.clear();
185c242
< bool interleaved() const { return intlvBits != 0; }
---
> bool interleaved() const { return masks.size() > 0; }
188,192d244
< * Determine if the range interleaving is hashed or not.
< */
< bool hashed() const { return interleaved() && xorHighBit != 0; }
<
< /**
200,205c252,254
< 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;
206a256,257
> const uint8_t lowest_bit = ctz64(combined_mask);
> return ULL(1) << lowest_bit;
218c269
< uint32_t stripes() const { return ULL(1) << intlvBits; }
---
> uint32_t stripes() const { return ULL(1) << masks.size(); }
227c278
< return (_end - _start + 1) >> intlvBits;
---
> return (_end - _start + 1) >> masks.size();
253,263c304,313
< 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));
264a315
> return csprintf("[%#llx:%#llx]%s", _start, _end, str);
266c317
< return csprintf("[%#llx : %#llx]", _start, _end);
---
> return csprintf("[%#llx:%#llx]", _start, _end);
281,283c332
< r.intlvHighBit == intlvHighBit &&
< r.xorHighBit == xorHighBit &&
< r.intlvBits == intlvBits;
---
> r.masks == masks;
355,364c404,412
< 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;
365a414
> return sel == intlvMatch;
373,375c422,424
< * 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.
377,380c426,432
< * e.g., if the input address is:
< * -------------------------------
< * | prefix | intlvBits | suffix |
< * -------------------------------
---
> * 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]
> *
382,384c434,436
< * -------------------------------
< * | 0 | prefix | suffix |
< * -------------------------------
---
> * ---------------------------------
> * | 0 | a_high | a_mid | a_low |
> * ---------------------------------
387c439
< * @return the address without the interleaved bits
---
> * @return the new address
389c441
< inline Addr removeIntlvBits(const Addr &a) const
---
> inline Addr removeIntlvBits(Addr a) const
391,392c443,464
< 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;
438,444c510,514
< 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;
>