1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright 2011 Christoph Bumiller 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice shall be included in 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * all copies or substantial portions of the Software. 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * SOFTWARE. 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "nv50_ir_util.h" 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace nv50_ir { 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DLList::clear() 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Item *next, *item = head.next; item != &head; item = next) { 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = item->next; 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete item; 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org head.next = head.prev = &head; 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgDLList::Iterator::erase() 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *rem = pos; 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (rem == term) 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = pos->next; 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLLIST_DEL(rem); 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete rem; 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid DLList::Iterator::moveToList(DLList& dest) 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *item = pos; 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(term != &dest.head); 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(pos != term); 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = pos->next; 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLLIST_DEL(item); 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DLLIST_ADDHEAD(&dest.head, item); 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgDLList::Iterator::insert(void *data) 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Item *ins = new Item(data); 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ins->next = pos->next; 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ins->prev = pos; 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos->next->prev = ins; 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos->next = ins; 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos == term) 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org term = ins; 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgStack::moveTo(Stack& that) 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int newSize = this->size + that.size; 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (newSize > that.limit) 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org that.resize(); 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org memcpy(&that.array[that.size], &array[0], this->size * sizeof(Item)); 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org that.size = newSize; 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->size = 0; 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgInterval::Interval(const Interval& that) : head(NULL), tail(NULL) 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->insert(that); 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgInterval::~Interval() 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org clear(); 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgInterval::clear() 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *next, *r = head; r; r = next) { 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = r->next; 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete r; 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org head = tail = NULL; 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgInterval::extend(int a, int b) 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *r, **nextp = &head; 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // NOTE: we need empty intervals for fixed registers 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // if (a == b) 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // return false; 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(a <= b); 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (r = head; r; r = r->next) { 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (b < r->bgn) 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; // insert before 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (a > r->end) { 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // insert after 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org nextp = &r->next; 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org continue; 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // overlap 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (a < r->bgn) { 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org r->bgn = a; 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (b > r->end) 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org r->end = b; 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org r->coalesce(&tail); 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (b > r->end) { 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org r->end = b; 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org r->coalesce(&tail); 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(a >= r->bgn); 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(b <= r->end); 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (*nextp) = new Range(a, b); 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (*nextp)->next = r; 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (r = (*nextp); r->next; r = r->next); 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org tail = r; 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool Interval::contains(int pos) const 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *r = head; r && r->bgn <= pos; r = r->next) 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (r->end > pos) 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool Interval::overlaps(const Interval &that) const 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#if 1 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *a = this->head; 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Range *b = that.head; 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (a && b) { 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (b->bgn < a->end && 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org b->end > a->bgn) 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (a->end <= b->bgn) 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org a = a->next; 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org b = b->next; 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#else 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *rA = this->head; rA; rA = rA->next) 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *rB = iv.head; rB; rB = rB->next) 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (rB->bgn < rA->end && 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org rB->end > rA->bgn) 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Interval::insert(const Interval &that) 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *r = that.head; r; r = r->next) 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->extend(r->bgn, r->end); 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Interval::unify(Interval &that) 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(this != &that); 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *next, *r = that.head; r; r = next) { 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org next = r->next; 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this->extend(r->bgn, r->end); 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org delete r; 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org that.head = NULL; 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgint Interval::length() const 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int len = 0; 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (Range *r = head; r; r = r->next) 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org len += r->bgn - r->end; 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return len; 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid Interval::print() const 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!head) 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("[%i %i)", head->bgn, head->end); 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (const Range *r = head->next; r; r = r->next) 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO(" [%i %i)", r->bgn, r->end); 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("\n"); 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBitSet::andNot(const BitSet &set) 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(data && set.data); 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(size >= set.size); 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < (set.size + 31) / 32; ++i) 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i] &= ~set.data[i]; 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgBitSet& BitSet::operator|=(const BitSet &set) 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(data && set.data); 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org assert(size >= set.size); 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < (set.size + 31) / 32; ++i) 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i] |= set.data[i]; 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return *this; 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool BitSet::resize(unsigned int nBits) 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!data || !nBits) 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return allocate(nBits, true); 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int p = (size + 31) / 32; 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int n = (nBits + 31) / 32; 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (n == p) 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data = (uint32_t *)REALLOC(data, 4 * p, 4 * n); 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!data) { 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = 0; 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (n > p) 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org memset(&data[4 * p + 4], 0, (n - p) * 4); 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = nBits; 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return true; 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgbool BitSet::allocate(unsigned int nBits, bool zero) 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (data && size < nBits) { 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FREE(data); 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data = NULL; 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org size = nBits; 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!data) 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4)); 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (zero) 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org memset(data, 0, (size + 7) / 8); 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (nBits) 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[(size + 31) / 32 - 1] = 0; // clear unused bits (e.g. for popCount) 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return data; 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgunsigned int BitSet::popCount() const 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int count = 0; 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < (size + 31) / 32; ++i) 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (data[i]) 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count += util_bitcount(data[i]); 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return count; 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid BitSet::fill(uint32_t val) 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int i; 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (i = 0; i < (size + 31) / 32; ++i) 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i] = val; 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (val) 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i] &= ~(0xffffffff << (size % 32)); // BE ? 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid BitSet::setOr(BitSet *pA, BitSet *pB) 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!pB) { 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org *this = *pA; 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < (size + 31) / 32; ++i) 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org data[i] = pA->data[i] | pB->data[i]; 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgint BitSet::findFreeRange(unsigned int count) const 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const uint32_t m = (1 << count) - 1; 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int pos = size; 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int i; 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const unsigned int end = (size + 31) / 32; 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (count == 1) { 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (i = 0; i < end; ++i) { 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = ffs(~data[i]) - 1; 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos >= 0) 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (count == 2) { 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (i = 0; i < end; ++i) { 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (data[i] != 0xffffffff) { 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint32_t b = data[i] | (data[i] >> 1) | 0xaaaaaaaa; 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = ffs(~b) - 1; 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos >= 0) 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (count == 4 || count == 3) { 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (i = 0; i < end; ++i) { 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (data[i] != 0xffffffff) { 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint32_t b = 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (data[i] >> 0) | (data[i] >> 1) | 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (data[i] >> 2) | (data[i] >> 3) | 0xeeeeeeee; 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos = ffs(~b) - 1; 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos >= 0) 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } else { 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (count <= 8) 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count = 8; 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (count <= 16) 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count = 16; 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org count = 32; 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (i = 0; i < end; ++i) { 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (data[i] != 0xffffffff) { 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (pos = 0; pos < 32; pos += count) 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (!(data[i] & (m << pos))) 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (pos < 32) 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org break; 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org pos += i * 32; 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ((pos + count) <= size) ? pos : -1; 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgvoid BitSet::print() const 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org unsigned int n = 0; 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("BitSet of size %u:\n", size); 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for (unsigned int i = 0; i < (size + 31) / 32; ++i) { 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org uint32_t bits = data[i]; 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while (bits) { 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int pos = ffs(bits) - 1; 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bits &= ~(1 << pos); 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO(" %i", i * 32 + pos); 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ++n; 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ((n % 16) == 0) 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("\n"); 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (n % 16) 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org INFO("\n"); 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} // namespace nv50_ir 391