1d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller/* 2d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Copyright 2011 Christoph Bumiller 3d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 4d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Permission is hereby granted, free of charge, to any person obtaining a 5d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * copy of this software and associated documentation files (the "Software"), 6d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * to deal in the Software without restriction, including without limitation 7d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * and/or sell copies of the Software, and to permit persons to whom the 9d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Software is furnished to do so, subject to the following conditions: 10d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 11d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * The above copyright notice and this permission notice shall be included in 12d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * all copies or substantial portions of the Software. 13d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * 14d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * SOFTWARE. 21d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller */ 2257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "nv50_ir_util.h" 2457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillernamespace nv50_ir { 2657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 2757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid DLList::clear() 2857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 2957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Item *next, *item = head.next; item != &head; item = next) { 3057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = item->next; 3157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete item; 3257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 3357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller head.next = head.prev = &head; 3457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 3557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 3757594065c30feec9376be9b2132659f7d87362eeChristoph BumillerDLList::Iterator::erase() 3857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 3957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *rem = pos; 4057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (rem == term) 4257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 4357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos = pos->next; 4457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLLIST_DEL(rem); 4657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete rem; 4757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 4857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid DLList::Iterator::moveToList(DLList& dest) 5057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 5157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *item = pos; 5257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(term != &dest.head); 5457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(pos != term); 5557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos = pos->next; 5757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 5857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLLIST_DEL(item); 5957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLLIST_ADDHEAD(&dest.head, item); 6057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 6157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 6257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 6357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerDLList::Iterator::insert(void *data) 6457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 6557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *ins = new Item(data); 6657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 6757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ins->next = pos->next; 6857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ins->prev = pos; 6957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos->next->prev = ins; 7057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos->next = ins; 7157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (pos == term) 7357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller term = ins; 7457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 7657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 7757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 7857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 7957594065c30feec9376be9b2132659f7d87362eeChristoph BumillerStack::moveTo(Stack& that) 8057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 8157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int newSize = this->size + that.size; 8257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (newSize > that.limit) 8457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller that.resize(); 8557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller memcpy(&that.array[that.size], &array[0], this->size * sizeof(Item)); 8657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 8757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller that.size = newSize; 8857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller this->size = 0; 8957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 9057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 91e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph BumillerInterval::Interval(const Interval& that) : head(NULL), tail(NULL) 92e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 93e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller this->insert(that); 94e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 95e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 9657594065c30feec9376be9b2132659f7d87362eeChristoph BumillerInterval::~Interval() 9757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 9857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller clear(); 9957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 10057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 10257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerInterval::clear() 10357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 10457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Range *next, *r = head; r; r = next) { 10557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = r->next; 10657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete r; 10757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 108f0a7ec9a2fad56eeb70c76202c21c97a33915d0bFrancisco Jerez head = tail = NULL; 10957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 11057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool 11257594065c30feec9376be9b2132659f7d87362eeChristoph BumillerInterval::extend(int a, int b) 11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *r, **nextp = &head; 11557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // NOTE: we need empty intervals for fixed registers 11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // if (a == b) 11857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // return false; 11957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(a <= b); 12057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (r = head; r; r = r->next) { 12257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b < r->bgn) 12357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller break; // insert before 12457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (a > r->end) { 12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // insert after 12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nextp = &r->next; 12757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller continue; 12857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 13057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // overlap 13157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (a < r->bgn) { 13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r->bgn = a; 13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b > r->end) 13457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r->end = b; 13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r->coalesce(&tail); 13657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (b > r->end) { 13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r->end = b; 14057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r->coalesce(&tail); 14157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(a >= r->bgn); 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(b <= r->end); 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (*nextp) = new Range(a, b); 14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (*nextp)->next = r; 15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (r = (*nextp); r->next; r = r->next); 15257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller tail = r; 15357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 156e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool Interval::contains(int pos) const 15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 15857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Range *r = head; r && r->bgn <= pos; r = r->next) 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (r->end > pos) 16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 164e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool Interval::overlaps(const Interval &that) const 16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 166e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#if 1 167e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Range *a = this->head; 168e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Range *b = that.head; 169e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 170e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller while (a && b) { 171e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (b->bgn < a->end && 172e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller b->end > a->bgn) 173e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return true; 174e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (a->end <= b->bgn) 175e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller a = a->next; 176e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller else 177e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller b = b->next; 178e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 179e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#else 18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Range *rA = this->head; rA; rA = rA->next) 18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Range *rB = iv.head; rB; rB = rB->next) 18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (rB->bgn < rA->end && 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller rB->end > rA->bgn) 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 185e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#endif 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 189e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillervoid Interval::insert(const Interval &that) 190e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 191e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Range *r = that.head; r; r = r->next) 192e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller this->extend(r->bgn, r->end); 193e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 194e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Interval::unify(Interval &that) 19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(this != &that); 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (Range *next, *r = that.head; r; r = next) { 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = r->next; 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller this->extend(r->bgn, r->end); 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete r; 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller that.head = NULL; 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 206e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerint Interval::length() const 207e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 208e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int len = 0; 209e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (Range *r = head; r; r = r->next) 210e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller len += r->bgn - r->end; 211e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return len; 212e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 213e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Interval::print() const 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!head) 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return; 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("[%i %i)", head->bgn, head->end); 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (const Range *r = head->next; r; r = r->next) 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO(" [%i %i)", r->bgn, r->end); 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("\n"); 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid 22557594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBitSet::andNot(const BitSet &set) 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data && set.data); 22857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(size >= set.size); 22957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < (set.size + 31) / 32; ++i) 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i] &= ~set.data[i]; 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23357594065c30feec9376be9b2132659f7d87362eeChristoph BumillerBitSet& BitSet::operator|=(const BitSet &set) 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 23557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data && set.data); 23657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(size >= set.size); 23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < (set.size + 31) / 32; ++i) 23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i] |= set.data[i]; 23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return *this; 24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 242e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerbool BitSet::resize(unsigned int nBits) 243e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 244e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!data || !nBits) 245e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return allocate(nBits, true); 246e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const unsigned int p = (size + 31) / 32; 247e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const unsigned int n = (nBits + 31) / 32; 248e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (n == p) 249e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return true; 250e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 251e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller data = (uint32_t *)REALLOC(data, 4 * p, 4 * n); 252e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!data) { 253e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller size = 0; 254e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return false; 255e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 256e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (n > p) 257e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller memset(&data[4 * p + 4], 0, (n - p) * 4); 258e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 259e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller size = nBits; 260e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return true; 261e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 262e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerbool BitSet::allocate(unsigned int nBits, bool zero) 26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 26557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (data && size < nBits) { 26657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(data); 26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data = NULL; 26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = nBits; 27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!data) 27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4)); 27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (zero) 27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller memset(data, 0, (size + 7) / 8); 27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller else 277349cb60ed58e42341351c5f0ebd186acb8f12005Francisco Jerez if (nBits) 27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[(size + 31) / 32 - 1] = 0; // clear unused bits (e.g. for popCount) 27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data; 28157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerunsigned int BitSet::popCount() const 28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int count = 0; 28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < (size + 31) / 32; ++i) 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (data[i]) 28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller count += util_bitcount(data[i]); 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return count; 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid BitSet::fill(uint32_t val) 29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int i; 29657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (i = 0; i < (size + 31) / 32; ++i) 29757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i] = val; 29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (val) 29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i] &= ~(0xffffffff << (size % 32)); // BE ? 30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid BitSet::setOr(BitSet *pA, BitSet *pB) 30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!pB) { 30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller *this = *pA; 30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } else { 30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < (size + 31) / 32; ++i) 30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i] = pA->data[i] | pB->data[i]; 30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 312e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumillerint BitSet::findFreeRange(unsigned int count) const 313e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller{ 314e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const uint32_t m = (1 << count) - 1; 315e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int pos = size; 316e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller unsigned int i; 317e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller const unsigned int end = (size + 31) / 32; 318e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 319e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (count == 1) { 320e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (i = 0; i < end; ++i) { 321e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pos = ffs(~data[i]) - 1; 322e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pos >= 0) 323e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 324e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 325e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 326e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (count == 2) { 327e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (i = 0; i < end; ++i) { 328e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (data[i] != 0xffffffff) { 329e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint32_t b = data[i] | (data[i] >> 1) | 0xaaaaaaaa; 330e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pos = ffs(~b) - 1; 331e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pos >= 0) 332e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 333e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 334e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 335e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else 336e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (count == 4 || count == 3) { 337e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (i = 0; i < end; ++i) { 338e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (data[i] != 0xffffffff) { 339e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller uint32_t b = 340e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller (data[i] >> 0) | (data[i] >> 1) | 341e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller (data[i] >> 2) | (data[i] >> 3) | 0xeeeeeeee; 342e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pos = ffs(~b) - 1; 343e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pos >= 0) 344e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 345e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 346e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 347e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } else { 348e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (count <= 8) 349e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller count = 8; 350e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller else 351e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (count <= 16) 352e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller count = 16; 353e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller else 354e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller count = 32; 355e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 356e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (i = 0; i < end; ++i) { 357e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (data[i] != 0xffffffff) { 358e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (pos = 0; pos < 32; pos += count) 359e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (!(data[i] & (m << pos))) 360e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 361e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller if (pos < 32) 362e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller break; 363e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 364e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 365e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 366e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller pos += i * 32; 367e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 368e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return ((pos + count) <= size) ? pos : -1; 369e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller} 370e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid BitSet::print() const 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int n = 0; 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("BitSet of size %u:\n", size); 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < (size + 31) / 32; ++i) { 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t bits = data[i]; 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (bits) { 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int pos = ffs(bits) - 1; 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bits &= ~(1 << pos); 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO(" %i", i * 32 + pos); 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++n; 38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if ((n % 16) == 0) 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("\n"); 38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (n % 16) 38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller INFO("\n"); 38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 391