addr_range.hh revision 14047
12SN/A/* 214047Snikos.nikoleris@arm.com * Copyright (c) 2012, 2014, 2017-2019 ARM Limited 39235Sandreas.hansson@arm.com * All rights reserved 49235Sandreas.hansson@arm.com * 59235Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 69235Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 79235Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 89235Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 99235Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 109235Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 119235Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 129235Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 139235Sandreas.hansson@arm.com * 141762SN/A * Copyright (c) 2002-2005 The Regents of The University of Michigan 152SN/A * All rights reserved. 162SN/A * 172SN/A * Redistribution and use in source and binary forms, with or without 182SN/A * modification, are permitted provided that the following conditions are 192SN/A * met: redistributions of source code must retain the above copyright 202SN/A * notice, this list of conditions and the following disclaimer; 212SN/A * redistributions in binary form must reproduce the above copyright 222SN/A * notice, this list of conditions and the following disclaimer in the 232SN/A * documentation and/or other materials provided with the distribution; 242SN/A * neither the name of the copyright holders nor the names of its 252SN/A * contributors may be used to endorse or promote products derived from 262SN/A * this software without specific prior written permission. 272SN/A * 282SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392665SN/A * 402665SN/A * Authors: Nathan Binkert 412665SN/A * Steve Reinhardt 429235Sandreas.hansson@arm.com * Andreas Hansson 432SN/A */ 442SN/A 459235Sandreas.hansson@arm.com#ifndef __BASE_ADDR_RANGE_HH__ 469235Sandreas.hansson@arm.com#define __BASE_ADDR_RANGE_HH__ 472SN/A 4812977Snikos.nikoleris@arm.com#include <algorithm> 4910481Sandreas.hansson@arm.com#include <list> 509412Sandreas.hansson@arm.com#include <vector> 519412Sandreas.hansson@arm.com 529411Sandreas.hansson@arm.com#include "base/bitfield.hh" 539405Sandreas.hansson@arm.com#include "base/cprintf.hh" 5412334Sgabeblack@google.com#include "base/logging.hh" 559235Sandreas.hansson@arm.com#include "base/types.hh" 569235Sandreas.hansson@arm.com 5710676Sandreas.hansson@arm.com/** 5810676Sandreas.hansson@arm.com * The AddrRange class encapsulates an address range, and supports a 5910676Sandreas.hansson@arm.com * number of tests to check if two ranges intersect, if a range 6010676Sandreas.hansson@arm.com * contains a specific address etc. Besides a basic range, the 6110676Sandreas.hansson@arm.com * AddrRange also support interleaved ranges, to stripe across cache 6210676Sandreas.hansson@arm.com * banks, or memory controllers. The interleaving is implemented by 6310676Sandreas.hansson@arm.com * allowing a number of bits of the address, at an arbitrary bit 6410676Sandreas.hansson@arm.com * position, to be used as interleaving bits with an associated 6510676Sandreas.hansson@arm.com * matching value. In addition, to prevent uniformly strided address 6614047Snikos.nikoleris@arm.com * patterns from a very biased interleaving, we also allow XOR-based 6714047Snikos.nikoleris@arm.com * hashing by specifying a set of bits to XOR with before matching. 6810676Sandreas.hansson@arm.com * 6910676Sandreas.hansson@arm.com * The AddrRange is also able to coalesce a number of interleaved 7010676Sandreas.hansson@arm.com * ranges to a contiguous range. 7110676Sandreas.hansson@arm.com */ 729235Sandreas.hansson@arm.comclass AddrRange 732SN/A{ 742SN/A 759405Sandreas.hansson@arm.com private: 769405Sandreas.hansson@arm.com 779411Sandreas.hansson@arm.com /// Private fields for the start and end of the range 7810435Snilay@cs.wisc.edu /// Both _start and _end are part of the range. 799405Sandreas.hansson@arm.com Addr _start; 809405Sandreas.hansson@arm.com Addr _end; 819405Sandreas.hansson@arm.com 8214047Snikos.nikoleris@arm.com /** 8314047Snikos.nikoleris@arm.com * Each mask determines the bits we need to xor to get one bit of 8414047Snikos.nikoleris@arm.com * sel. The first (0) mask is used to get the LSB and the last for 8514047Snikos.nikoleris@arm.com * the MSB of sel. 8614047Snikos.nikoleris@arm.com */ 8714047Snikos.nikoleris@arm.com std::vector<Addr> masks; 889411Sandreas.hansson@arm.com 8914047Snikos.nikoleris@arm.com /** The value to compare sel with. */ 909411Sandreas.hansson@arm.com uint8_t intlvMatch; 919411Sandreas.hansson@arm.com 929235Sandreas.hansson@arm.com public: 932SN/A 949235Sandreas.hansson@arm.com AddrRange() 9514047Snikos.nikoleris@arm.com : _start(1), _end(0), intlvMatch(0) 969411Sandreas.hansson@arm.com {} 979411Sandreas.hansson@arm.com 9814047Snikos.nikoleris@arm.com /** 9914047Snikos.nikoleris@arm.com * Construct an address range 10014047Snikos.nikoleris@arm.com * 10114047Snikos.nikoleris@arm.com * If the user provides a non empty vector of masks then the 10214047Snikos.nikoleris@arm.com * address range is interleaved. Each mask determines a set of 10314047Snikos.nikoleris@arm.com * bits that are xored to determine one bit of the sel value, 10414047Snikos.nikoleris@arm.com * starting from the least significant bit (i.e., masks[0] 10514047Snikos.nikoleris@arm.com * determines the least significant bit of sel, ...). If sel 10614047Snikos.nikoleris@arm.com * matches the provided _intlv_match then the address a is in the 10714047Snikos.nikoleris@arm.com * range. 10814047Snikos.nikoleris@arm.com * 10914047Snikos.nikoleris@arm.com * For example if the input mask is 11014047Snikos.nikoleris@arm.com * _masks = { 1 << 8 | 1 << 11 | 1 << 13, 11114047Snikos.nikoleris@arm.com * 1 << 15 | 1 << 17 | 1 << 19} 11214047Snikos.nikoleris@arm.com * 11314047Snikos.nikoleris@arm.com * Then a belongs to the address range if 11414047Snikos.nikoleris@arm.com * _start <= a < _end 11514047Snikos.nikoleris@arm.com * and 11614047Snikos.nikoleris@arm.com * sel == _intlv_match 11714047Snikos.nikoleris@arm.com * where 11814047Snikos.nikoleris@arm.com * sel[0] = a[8] ^ a[11] ^ a[13] 11914047Snikos.nikoleris@arm.com * sel[1] = a[15] ^ a[17] ^ a[19] 12014047Snikos.nikoleris@arm.com * 12114047Snikos.nikoleris@arm.com * @param _start The start address of this range 12214047Snikos.nikoleris@arm.com * @param _end The end address of this range (not included in the range) 12314047Snikos.nikoleris@arm.com * @param _masks The input vector of masks 12414047Snikos.nikoleris@arm.com * @param intlv_math The matching value of the xor operations 12514047Snikos.nikoleris@arm.com */ 12614047Snikos.nikoleris@arm.com AddrRange(Addr _start, Addr _end, const std::vector<Addr> &_masks, 12714047Snikos.nikoleris@arm.com uint8_t _intlv_match) 12814047Snikos.nikoleris@arm.com : _start(_start), _end(_end), masks(_masks), 12914047Snikos.nikoleris@arm.com intlvMatch(_intlv_match) 13014047Snikos.nikoleris@arm.com { 13114047Snikos.nikoleris@arm.com // sanity checks 13214047Snikos.nikoleris@arm.com fatal_if(!masks.empty() && _intlv_match >= ULL(1) << masks.size(), 13314047Snikos.nikoleris@arm.com "Match value %d does not fit in %d interleaving bits\n", 13414047Snikos.nikoleris@arm.com _intlv_match, masks.size()); 13514047Snikos.nikoleris@arm.com } 13614047Snikos.nikoleris@arm.com 13714047Snikos.nikoleris@arm.com /** 13814047Snikos.nikoleris@arm.com * Legacy constructor of AddrRange 13914047Snikos.nikoleris@arm.com * 14014047Snikos.nikoleris@arm.com * If the user provides a non-zero value in _intlv_high_bit the 14114047Snikos.nikoleris@arm.com * address range is interleaved. 14214047Snikos.nikoleris@arm.com * 14314047Snikos.nikoleris@arm.com * An address a belongs to the address range if 14414047Snikos.nikoleris@arm.com * _start <= a < _end 14514047Snikos.nikoleris@arm.com * and 14614047Snikos.nikoleris@arm.com * sel == _intlv_match 14714047Snikos.nikoleris@arm.com * where 14814047Snikos.nikoleris@arm.com * sel = sel1 ^ sel2 14914047Snikos.nikoleris@arm.com * sel1 = a[_intlv_low_bit:_intlv_high_bit] 15014047Snikos.nikoleris@arm.com * sel2 = a[_xor_low_bit:_xor_high_bit] 15114047Snikos.nikoleris@arm.com * _intlv_low_bit = _intlv_high_bit - intv_bits 15214047Snikos.nikoleris@arm.com * _xor_low_bit = _xor_high_bit - intv_bits 15314047Snikos.nikoleris@arm.com * 15414047Snikos.nikoleris@arm.com * @param _start The start address of this range 15514047Snikos.nikoleris@arm.com * @param _end The end address of this range (not included in the range) 15614047Snikos.nikoleris@arm.com * @param _intlv_high_bit The MSB of the intlv bits (disabled if 0) 15714047Snikos.nikoleris@arm.com * @param _xor_high_bit The MSB of the xor bit (disabled if 0) 15814047Snikos.nikoleris@arm.com * @param intlv_math The matching value of the xor operations 15914047Snikos.nikoleris@arm.com */ 1609411Sandreas.hansson@arm.com AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, 16110676Sandreas.hansson@arm.com uint8_t _xor_high_bit, uint8_t _intlv_bits, 16210676Sandreas.hansson@arm.com uint8_t _intlv_match) 16314047Snikos.nikoleris@arm.com : _start(_start), _end(_end), masks(_intlv_bits), 16410676Sandreas.hansson@arm.com intlvMatch(_intlv_match) 16510676Sandreas.hansson@arm.com { 16610676Sandreas.hansson@arm.com // sanity checks 16714047Snikos.nikoleris@arm.com fatal_if(_intlv_bits && _intlv_match >= ULL(1) << _intlv_bits, 16810676Sandreas.hansson@arm.com "Match value %d does not fit in %d interleaving bits\n", 16914047Snikos.nikoleris@arm.com _intlv_match, _intlv_bits); 17010676Sandreas.hansson@arm.com 17110676Sandreas.hansson@arm.com // ignore the XOR bits if not interleaving 17214047Snikos.nikoleris@arm.com if (_intlv_bits && _xor_high_bit) { 17314047Snikos.nikoleris@arm.com if (_xor_high_bit == _intlv_high_bit) { 17410676Sandreas.hansson@arm.com fatal("XOR and interleave high bit must be different\n"); 17514047Snikos.nikoleris@arm.com } else if (_xor_high_bit > _intlv_high_bit) { 17614047Snikos.nikoleris@arm.com if ((_xor_high_bit - _intlv_high_bit) < _intlv_bits) 17710676Sandreas.hansson@arm.com fatal("XOR and interleave high bit must be at least " 17814047Snikos.nikoleris@arm.com "%d bits apart\n", _intlv_bits); 17910676Sandreas.hansson@arm.com } else { 18014047Snikos.nikoleris@arm.com if ((_intlv_high_bit - _xor_high_bit) < _intlv_bits) { 18110676Sandreas.hansson@arm.com fatal("Interleave and XOR high bit must be at least " 18214047Snikos.nikoleris@arm.com "%d bits apart\n", _intlv_bits); 18310676Sandreas.hansson@arm.com } 18410676Sandreas.hansson@arm.com } 18510676Sandreas.hansson@arm.com } 18614047Snikos.nikoleris@arm.com 18714047Snikos.nikoleris@arm.com for (auto i = 0; i < _intlv_bits; i++) { 18814047Snikos.nikoleris@arm.com uint8_t bit1 = _intlv_high_bit - i; 18914047Snikos.nikoleris@arm.com Addr mask = (1ULL << bit1); 19014047Snikos.nikoleris@arm.com if (_xor_high_bit) { 19114047Snikos.nikoleris@arm.com uint8_t bit2 = _xor_high_bit - i; 19214047Snikos.nikoleris@arm.com mask |= (1ULL << bit2); 19314047Snikos.nikoleris@arm.com } 19414047Snikos.nikoleris@arm.com masks[_intlv_bits - i - 1] = mask; 19514047Snikos.nikoleris@arm.com } 19610676Sandreas.hansson@arm.com } 1979235Sandreas.hansson@arm.com 1989235Sandreas.hansson@arm.com AddrRange(Addr _start, Addr _end) 19914047Snikos.nikoleris@arm.com : _start(_start), _end(_end), intlvMatch(0) 2009235Sandreas.hansson@arm.com {} 2019235Sandreas.hansson@arm.com 2029405Sandreas.hansson@arm.com /** 2039412Sandreas.hansson@arm.com * Create an address range by merging a collection of interleaved 2049412Sandreas.hansson@arm.com * ranges. 2059412Sandreas.hansson@arm.com * 2069412Sandreas.hansson@arm.com * @param ranges Interleaved ranges to be merged 2079412Sandreas.hansson@arm.com */ 2089412Sandreas.hansson@arm.com AddrRange(const std::vector<AddrRange>& ranges) 20914047Snikos.nikoleris@arm.com : _start(1), _end(0), intlvMatch(0) 2109412Sandreas.hansson@arm.com { 2119412Sandreas.hansson@arm.com if (!ranges.empty()) { 2129412Sandreas.hansson@arm.com // get the values from the first one and check the others 2139412Sandreas.hansson@arm.com _start = ranges.front()._start; 2149412Sandreas.hansson@arm.com _end = ranges.front()._end; 21514047Snikos.nikoleris@arm.com masks = ranges.front().masks; 2169412Sandreas.hansson@arm.com 21714047Snikos.nikoleris@arm.com if (ranges.size() != (ULL(1) << masks.size())) 2189412Sandreas.hansson@arm.com fatal("Got %d ranges spanning %d interleaving bits\n", 21914047Snikos.nikoleris@arm.com ranges.size(), masks.size()); 2209412Sandreas.hansson@arm.com 2219412Sandreas.hansson@arm.com uint8_t match = 0; 22210676Sandreas.hansson@arm.com for (const auto& r : ranges) { 22310676Sandreas.hansson@arm.com if (!mergesWith(r)) 2249412Sandreas.hansson@arm.com fatal("Can only merge ranges with the same start, end " 22514047Snikos.nikoleris@arm.com "and interleaving bits, %s %s\n", to_string(), 22614047Snikos.nikoleris@arm.com r.to_string()); 2279412Sandreas.hansson@arm.com 22810676Sandreas.hansson@arm.com if (r.intlvMatch != match) 2299412Sandreas.hansson@arm.com fatal("Expected interleave match %d but got %d when " 23010676Sandreas.hansson@arm.com "merging\n", match, r.intlvMatch); 2319412Sandreas.hansson@arm.com ++match; 2329412Sandreas.hansson@arm.com } 23314047Snikos.nikoleris@arm.com masks.clear(); 2349412Sandreas.hansson@arm.com } 2359412Sandreas.hansson@arm.com } 2369412Sandreas.hansson@arm.com 2379412Sandreas.hansson@arm.com /** 2389411Sandreas.hansson@arm.com * Determine if the range is interleaved or not. 2399411Sandreas.hansson@arm.com * 2409411Sandreas.hansson@arm.com * @return true if interleaved 2419411Sandreas.hansson@arm.com */ 24214047Snikos.nikoleris@arm.com bool interleaved() const { return masks.size() > 0; } 24310676Sandreas.hansson@arm.com 24410676Sandreas.hansson@arm.com /** 2459411Sandreas.hansson@arm.com * Determing the interleaving granularity of the range. 2469411Sandreas.hansson@arm.com * 2479411Sandreas.hansson@arm.com * @return The size of the regions created by the interleaving bits 2489411Sandreas.hansson@arm.com */ 2499581Sandreas.hansson@arm.com uint64_t granularity() const 2509581Sandreas.hansson@arm.com { 25112977Snikos.nikoleris@arm.com if (interleaved()) { 25214047Snikos.nikoleris@arm.com auto combined_mask = 0; 25314047Snikos.nikoleris@arm.com for (auto mask: masks) { 25414047Snikos.nikoleris@arm.com combined_mask |= mask; 25512977Snikos.nikoleris@arm.com } 25614047Snikos.nikoleris@arm.com const uint8_t lowest_bit = ctz64(combined_mask); 25714047Snikos.nikoleris@arm.com return ULL(1) << lowest_bit; 25812977Snikos.nikoleris@arm.com } else { 25912977Snikos.nikoleris@arm.com return size(); 26012977Snikos.nikoleris@arm.com } 2619581Sandreas.hansson@arm.com } 2629411Sandreas.hansson@arm.com 2639411Sandreas.hansson@arm.com /** 2649411Sandreas.hansson@arm.com * Determine the number of interleaved address stripes this range 2659411Sandreas.hansson@arm.com * is part of. 2669411Sandreas.hansson@arm.com * 2679411Sandreas.hansson@arm.com * @return The number of stripes spanned by the interleaving bits 2689411Sandreas.hansson@arm.com */ 26914047Snikos.nikoleris@arm.com uint32_t stripes() const { return ULL(1) << masks.size(); } 2709411Sandreas.hansson@arm.com 2719411Sandreas.hansson@arm.com /** 2729405Sandreas.hansson@arm.com * Get the size of the address range. For a case where 2739411Sandreas.hansson@arm.com * interleaving is used we make the simplifying assumption that 2749411Sandreas.hansson@arm.com * the size is a divisible by the size of the interleaving slice. 2759405Sandreas.hansson@arm.com */ 2769411Sandreas.hansson@arm.com Addr size() const 2779411Sandreas.hansson@arm.com { 27814047Snikos.nikoleris@arm.com return (_end - _start + 1) >> masks.size(); 2799411Sandreas.hansson@arm.com } 280532SN/A 2819405Sandreas.hansson@arm.com /** 2829405Sandreas.hansson@arm.com * Determine if the range is valid. 2839405Sandreas.hansson@arm.com */ 28410435Snilay@cs.wisc.edu bool valid() const { return _start <= _end; } 2859405Sandreas.hansson@arm.com 2869405Sandreas.hansson@arm.com /** 2879405Sandreas.hansson@arm.com * Get the start address of the range. 2889405Sandreas.hansson@arm.com */ 2899405Sandreas.hansson@arm.com Addr start() const { return _start; } 2909405Sandreas.hansson@arm.com 2919405Sandreas.hansson@arm.com /** 29210678SCurtis.Dunham@arm.com * Get the end address of the range. 29310678SCurtis.Dunham@arm.com */ 29410678SCurtis.Dunham@arm.com Addr end() const { return _end; } 29510678SCurtis.Dunham@arm.com 29610678SCurtis.Dunham@arm.com /** 2979405Sandreas.hansson@arm.com * Get a string representation of the range. This could 2989405Sandreas.hansson@arm.com * alternatively be implemented as a operator<<, but at the moment 2999405Sandreas.hansson@arm.com * that seems like overkill. 3009405Sandreas.hansson@arm.com */ 3019405Sandreas.hansson@arm.com std::string to_string() const 3029405Sandreas.hansson@arm.com { 30310676Sandreas.hansson@arm.com if (interleaved()) { 30414047Snikos.nikoleris@arm.com std::string str; 30514047Snikos.nikoleris@arm.com for (int i = 0; i < masks.size(); i++) { 30614047Snikos.nikoleris@arm.com str += " "; 30714047Snikos.nikoleris@arm.com Addr mask = masks[i]; 30814047Snikos.nikoleris@arm.com while (mask) { 30914047Snikos.nikoleris@arm.com auto bit = ctz64(mask); 31014047Snikos.nikoleris@arm.com mask &= ~(1ULL << bit); 31114047Snikos.nikoleris@arm.com str += csprintf("a[%d]^", bit); 31214047Snikos.nikoleris@arm.com } 31314047Snikos.nikoleris@arm.com str += csprintf("\b=%d", bits(intlvMatch, i)); 31410676Sandreas.hansson@arm.com } 31514047Snikos.nikoleris@arm.com return csprintf("[%#llx:%#llx]%s", _start, _end, str); 31610676Sandreas.hansson@arm.com } else { 31714047Snikos.nikoleris@arm.com return csprintf("[%#llx:%#llx]", _start, _end); 31810676Sandreas.hansson@arm.com } 3199411Sandreas.hansson@arm.com } 3209411Sandreas.hansson@arm.com 3219411Sandreas.hansson@arm.com /** 3229411Sandreas.hansson@arm.com * Determine if another range merges with the current one, i.e. if 3239411Sandreas.hansson@arm.com * they are part of the same contigous range and have the same 3249411Sandreas.hansson@arm.com * interleaving bits. 3259411Sandreas.hansson@arm.com * 3269411Sandreas.hansson@arm.com * @param r Range to evaluate merging with 3279411Sandreas.hansson@arm.com * @return true if the two ranges would merge 3289411Sandreas.hansson@arm.com */ 3299411Sandreas.hansson@arm.com bool mergesWith(const AddrRange& r) const 3309411Sandreas.hansson@arm.com { 3319411Sandreas.hansson@arm.com return r._start == _start && r._end == _end && 33214047Snikos.nikoleris@arm.com r.masks == masks; 3339405Sandreas.hansson@arm.com } 3349279Sandreas.hansson@arm.com 3359279Sandreas.hansson@arm.com /** 3369279Sandreas.hansson@arm.com * Determine if another range intersects this one, i.e. if there 3379279Sandreas.hansson@arm.com * is an address that is both in this range and the other 3389279Sandreas.hansson@arm.com * range. No check is made to ensure either range is valid. 3399279Sandreas.hansson@arm.com * 3409279Sandreas.hansson@arm.com * @param r Range to intersect with 3419279Sandreas.hansson@arm.com * @return true if the intersection of the two ranges is not empty 3429279Sandreas.hansson@arm.com */ 3439279Sandreas.hansson@arm.com bool intersects(const AddrRange& r) const 3449279Sandreas.hansson@arm.com { 34510853Sandreas.hansson@arm.com if (_start > r._end || _end < r._start) 34610853Sandreas.hansson@arm.com // start with the simple case of no overlap at all, 34710853Sandreas.hansson@arm.com // applicable even if we have interleaved ranges 34810853Sandreas.hansson@arm.com return false; 34910853Sandreas.hansson@arm.com else if (!interleaved() && !r.interleaved()) 35010853Sandreas.hansson@arm.com // if neither range is interleaved, we are done 35110853Sandreas.hansson@arm.com return true; 3529411Sandreas.hansson@arm.com 35310853Sandreas.hansson@arm.com // now it gets complicated, focus on the cases we care about 3549411Sandreas.hansson@arm.com if (r.size() == 1) 3559411Sandreas.hansson@arm.com // keep it simple and check if the address is within 3569411Sandreas.hansson@arm.com // this range 3579411Sandreas.hansson@arm.com return contains(r.start()); 3589411Sandreas.hansson@arm.com else if (mergesWith(r)) 3599411Sandreas.hansson@arm.com // restrict the check to ranges that belong to the 3609411Sandreas.hansson@arm.com // same chunk 3619411Sandreas.hansson@arm.com return intlvMatch == r.intlvMatch; 3629411Sandreas.hansson@arm.com else 36310853Sandreas.hansson@arm.com panic("Cannot test intersection of %s and %s\n", 36410853Sandreas.hansson@arm.com to_string(), r.to_string()); 3659279Sandreas.hansson@arm.com } 3669279Sandreas.hansson@arm.com 3679279Sandreas.hansson@arm.com /** 3689279Sandreas.hansson@arm.com * Determine if this range is a subset of another range, i.e. if 3699279Sandreas.hansson@arm.com * every address in this range is also in the other range. No 3709279Sandreas.hansson@arm.com * check is made to ensure either range is valid. 3719279Sandreas.hansson@arm.com * 3729279Sandreas.hansson@arm.com * @param r Range to compare with 3739279Sandreas.hansson@arm.com * @return true if the this range is a subset of the other one 3749279Sandreas.hansson@arm.com */ 3759279Sandreas.hansson@arm.com bool isSubset(const AddrRange& r) const 3769279Sandreas.hansson@arm.com { 3779411Sandreas.hansson@arm.com if (interleaved()) 3789411Sandreas.hansson@arm.com panic("Cannot test subset of interleaved range %s\n", to_string()); 37912977Snikos.nikoleris@arm.com 38012977Snikos.nikoleris@arm.com // This address range is not interleaved and therefore it 38112977Snikos.nikoleris@arm.com // suffices to check the upper bound, the lower bound and 38212977Snikos.nikoleris@arm.com // whether it would fit in a continuous segment of the input 38312977Snikos.nikoleris@arm.com // addr range. 38412977Snikos.nikoleris@arm.com if (r.interleaved()) { 38512977Snikos.nikoleris@arm.com return r.contains(_start) && r.contains(_end) && 38612977Snikos.nikoleris@arm.com size() <= r.granularity(); 38712977Snikos.nikoleris@arm.com } else { 38812977Snikos.nikoleris@arm.com return _start >= r._start && _end <= r._end; 38912977Snikos.nikoleris@arm.com } 3909279Sandreas.hansson@arm.com } 3919405Sandreas.hansson@arm.com 3929405Sandreas.hansson@arm.com /** 3939405Sandreas.hansson@arm.com * Determine if the range contains an address. 3949405Sandreas.hansson@arm.com * 3959405Sandreas.hansson@arm.com * @param a Address to compare with 3969405Sandreas.hansson@arm.com * @return true if the address is in the range 3979405Sandreas.hansson@arm.com */ 3989405Sandreas.hansson@arm.com bool contains(const Addr& a) const 3999405Sandreas.hansson@arm.com { 4009411Sandreas.hansson@arm.com // check if the address is in the range and if there is either 4019411Sandreas.hansson@arm.com // no interleaving, or with interleaving also if the selected 4029411Sandreas.hansson@arm.com // bits from the address match the interleaving value 40310676Sandreas.hansson@arm.com bool in_range = a >= _start && a <= _end; 40414047Snikos.nikoleris@arm.com if (in_range) { 40514047Snikos.nikoleris@arm.com auto sel = 0; 40614047Snikos.nikoleris@arm.com for (int i = 0; i < masks.size(); i++) { 40714047Snikos.nikoleris@arm.com Addr masked = a & masks[i]; 40814047Snikos.nikoleris@arm.com // The result of an xor operation is 1 if the number 40914047Snikos.nikoleris@arm.com // of bits set is odd or 0 othersize, thefore it 41014047Snikos.nikoleris@arm.com // suffices to count the number of bits set to 41114047Snikos.nikoleris@arm.com // determine the i-th bit of sel. 41214047Snikos.nikoleris@arm.com sel |= (popCount(masked) % 2) << i; 41310676Sandreas.hansson@arm.com } 41414047Snikos.nikoleris@arm.com return sel == intlvMatch; 41510676Sandreas.hansson@arm.com } 41610676Sandreas.hansson@arm.com return false; 4179405Sandreas.hansson@arm.com } 4182SN/A 4199405Sandreas.hansson@arm.com /** 42012065Snikos.nikoleris@arm.com * Remove the interleaving bits from an input address. 42112065Snikos.nikoleris@arm.com * 42214047Snikos.nikoleris@arm.com * This function returns a new address in a continous range [ 42314047Snikos.nikoleris@arm.com * start, start + size / intlv_bits). We can achieve this by 42414047Snikos.nikoleris@arm.com * discarding the LSB in each mask. 42512065Snikos.nikoleris@arm.com * 42614047Snikos.nikoleris@arm.com * e.g., if the input address is of the form: 42714047Snikos.nikoleris@arm.com * ------------------------------------ 42814047Snikos.nikoleris@arm.com * | a_high | x1 | a_mid | x0 | a_low | 42914047Snikos.nikoleris@arm.com * ------------------------------------ 43014047Snikos.nikoleris@arm.com * where x0 is the LSB set in masks[0] 43114047Snikos.nikoleris@arm.com * and x1 is the LSB set in masks[1] 43214047Snikos.nikoleris@arm.com * 43312065Snikos.nikoleris@arm.com * this function will return: 43414047Snikos.nikoleris@arm.com * --------------------------------- 43514047Snikos.nikoleris@arm.com * | 0 | a_high | a_mid | a_low | 43614047Snikos.nikoleris@arm.com * --------------------------------- 43712065Snikos.nikoleris@arm.com * 43812065Snikos.nikoleris@arm.com * @param the input address 43914047Snikos.nikoleris@arm.com * @return the new address 44012065Snikos.nikoleris@arm.com */ 44114047Snikos.nikoleris@arm.com inline Addr removeIntlvBits(Addr a) const 44212065Snikos.nikoleris@arm.com { 44314047Snikos.nikoleris@arm.com // Get the LSB set from each mask 44414047Snikos.nikoleris@arm.com int masks_lsb[masks.size()]; 44514047Snikos.nikoleris@arm.com for (int i = 0; i < masks.size(); i++) { 44614047Snikos.nikoleris@arm.com masks_lsb[i] = ctz64(masks[i]); 44714047Snikos.nikoleris@arm.com } 44814047Snikos.nikoleris@arm.com 44914047Snikos.nikoleris@arm.com // we need to sort the list of bits we will discard as we 45014047Snikos.nikoleris@arm.com // discard them one by one starting. 45114047Snikos.nikoleris@arm.com std::sort(masks_lsb, masks_lsb + masks.size()); 45214047Snikos.nikoleris@arm.com 45314047Snikos.nikoleris@arm.com for (int i = 0; i < masks.size(); i++) { 45414047Snikos.nikoleris@arm.com const int intlv_bit = masks_lsb[i]; 45514047Snikos.nikoleris@arm.com if (intlv_bit > 0) { 45614047Snikos.nikoleris@arm.com // on every iteration we remove one bit from the input 45714047Snikos.nikoleris@arm.com // address, and therefore the lowest invtl_bit has 45814047Snikos.nikoleris@arm.com // also shifted to the right by i positions. 45914047Snikos.nikoleris@arm.com a = insertBits(a >> 1, intlv_bit - i - 1, 0, a); 46014047Snikos.nikoleris@arm.com } else { 46114047Snikos.nikoleris@arm.com a >>= 1; 46214047Snikos.nikoleris@arm.com } 46314047Snikos.nikoleris@arm.com } 46414047Snikos.nikoleris@arm.com return a; 46512065Snikos.nikoleris@arm.com } 46612065Snikos.nikoleris@arm.com 46712065Snikos.nikoleris@arm.com /** 46812065Snikos.nikoleris@arm.com * Determine the offset of an address within the range. 46912065Snikos.nikoleris@arm.com * 47012065Snikos.nikoleris@arm.com * This function returns the offset of the given address from the 47112065Snikos.nikoleris@arm.com * starting address discarding any bits that are used for 47212065Snikos.nikoleris@arm.com * interleaving. This way we can convert the input address to a 47312065Snikos.nikoleris@arm.com * new unique address in a continuous range that starts from 0. 47412065Snikos.nikoleris@arm.com * 47512065Snikos.nikoleris@arm.com * @param the input address 47612065Snikos.nikoleris@arm.com * @return the flat offset in the address range 47712065Snikos.nikoleris@arm.com */ 47812065Snikos.nikoleris@arm.com Addr getOffset(const Addr& a) const 47912065Snikos.nikoleris@arm.com { 48012065Snikos.nikoleris@arm.com bool in_range = a >= _start && a <= _end; 48112065Snikos.nikoleris@arm.com if (!in_range) { 48212065Snikos.nikoleris@arm.com return MaxAddr; 48312065Snikos.nikoleris@arm.com } 48412065Snikos.nikoleris@arm.com if (interleaved()) { 48512065Snikos.nikoleris@arm.com return removeIntlvBits(a) - removeIntlvBits(_start); 48612065Snikos.nikoleris@arm.com } else { 48712065Snikos.nikoleris@arm.com return a - _start; 48812065Snikos.nikoleris@arm.com } 48912065Snikos.nikoleris@arm.com } 49012065Snikos.nikoleris@arm.com 49112065Snikos.nikoleris@arm.com /** 4929405Sandreas.hansson@arm.com * Less-than operator used to turn an STL map into a binary search 4939405Sandreas.hansson@arm.com * tree of non-overlapping address ranges. 4949405Sandreas.hansson@arm.com * 4959405Sandreas.hansson@arm.com * @param r Range to compare with 4969405Sandreas.hansson@arm.com * @return true if the start address is less than that of the other range 4979405Sandreas.hansson@arm.com */ 4989405Sandreas.hansson@arm.com bool operator<(const AddrRange& r) const 4999405Sandreas.hansson@arm.com { 5009411Sandreas.hansson@arm.com if (_start != r._start) 5019411Sandreas.hansson@arm.com return _start < r._start; 5029411Sandreas.hansson@arm.com else 5039411Sandreas.hansson@arm.com // for now assume that the end is also the same, and that 5049411Sandreas.hansson@arm.com // we are looking at the same interleaving bits 5059411Sandreas.hansson@arm.com return intlvMatch < r.intlvMatch; 5069405Sandreas.hansson@arm.com } 507531SN/A 50810678SCurtis.Dunham@arm.com bool operator==(const AddrRange& r) const 50910678SCurtis.Dunham@arm.com { 51014047Snikos.nikoleris@arm.com if (_start != r._start) return false; 51114047Snikos.nikoleris@arm.com if (_end != r._end) return false; 51214047Snikos.nikoleris@arm.com if (masks != r.masks) return false; 51314047Snikos.nikoleris@arm.com if (intlvMatch != r.intlvMatch) return false; 51414047Snikos.nikoleris@arm.com 51510678SCurtis.Dunham@arm.com return true; 51610678SCurtis.Dunham@arm.com } 51710678SCurtis.Dunham@arm.com 51810678SCurtis.Dunham@arm.com bool operator!=(const AddrRange& r) const 51910678SCurtis.Dunham@arm.com { 52010678SCurtis.Dunham@arm.com return !(*this == r); 52110678SCurtis.Dunham@arm.com } 5229405Sandreas.hansson@arm.com}; 5232SN/A 52410481Sandreas.hansson@arm.com/** 52510481Sandreas.hansson@arm.com * Convenience typedef for a collection of address ranges 52610481Sandreas.hansson@arm.com */ 52710481Sandreas.hansson@arm.comtypedef std::list<AddrRange> AddrRangeList; 52810481Sandreas.hansson@arm.com 5299235Sandreas.hansson@arm.cominline AddrRange 5309235Sandreas.hansson@arm.comRangeEx(Addr start, Addr end) 5319405Sandreas.hansson@arm.com{ return AddrRange(start, end - 1); } 5322SN/A 5339235Sandreas.hansson@arm.cominline AddrRange 5349235Sandreas.hansson@arm.comRangeIn(Addr start, Addr end) 5359405Sandreas.hansson@arm.com{ return AddrRange(start, end); } 5362SN/A 5379235Sandreas.hansson@arm.cominline AddrRange 5389235Sandreas.hansson@arm.comRangeSize(Addr start, Addr size) 5399405Sandreas.hansson@arm.com{ return AddrRange(start, start + size - 1); } 5402SN/A 5419235Sandreas.hansson@arm.com#endif // __BASE_ADDR_RANGE_HH__ 542