nv50_ir_util.cpp revision d2d19ea51fa3575a8d014a69a9b835c335728817
1/* 2 * Copyright 2011 Christoph Bumiller 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included in 12 * all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 17 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 18 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 19 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 20 * SOFTWARE. 21 */ 22 23#include "nv50_ir_util.h" 24 25namespace nv50_ir { 26 27void DLList::clear() 28{ 29 for (Item *next, *item = head.next; item != &head; item = next) { 30 next = item->next; 31 delete item; 32 } 33 head.next = head.prev = &head; 34} 35 36void 37DLList::Iterator::erase() 38{ 39 Item *rem = pos; 40 41 if (rem == term) 42 return; 43 pos = pos->next; 44 45 DLLIST_DEL(rem); 46 delete rem; 47} 48 49void DLList::Iterator::moveToList(DLList& dest) 50{ 51 Item *item = pos; 52 53 assert(term != &dest.head); 54 assert(pos != term); 55 56 pos = pos->next; 57 58 DLLIST_DEL(item); 59 DLLIST_ADDHEAD(&dest.head, item); 60} 61 62bool 63DLList::Iterator::insert(void *data) 64{ 65 Item *ins = new Item(data); 66 67 ins->next = pos->next; 68 ins->prev = pos; 69 pos->next->prev = ins; 70 pos->next = ins; 71 72 if (pos == term) 73 term = ins; 74 75 return true; 76} 77 78void 79Stack::moveTo(Stack& that) 80{ 81 unsigned int newSize = this->size + that.size; 82 83 while (newSize > that.limit) 84 that.resize(); 85 memcpy(&that.array[that.size], &array[0], this->size * sizeof(Item)); 86 87 that.size = newSize; 88 this->size = 0; 89} 90 91Interval::~Interval() 92{ 93 clear(); 94} 95 96void 97Interval::clear() 98{ 99 for (Range *next, *r = head; r; r = next) { 100 next = r->next; 101 delete r; 102 } 103} 104 105bool 106Interval::extend(int a, int b) 107{ 108 Range *r, **nextp = &head; 109 110 // NOTE: we need empty intervals for fixed registers 111 // if (a == b) 112 // return false; 113 assert(a <= b); 114 115 for (r = head; r; r = r->next) { 116 if (b < r->bgn) 117 break; // insert before 118 if (a > r->end) { 119 // insert after 120 nextp = &r->next; 121 continue; 122 } 123 124 // overlap 125 if (a < r->bgn) { 126 r->bgn = a; 127 if (b > r->end) 128 r->end = b; 129 r->coalesce(&tail); 130 return true; 131 } 132 if (b > r->end) { 133 r->end = b; 134 r->coalesce(&tail); 135 return true; 136 } 137 assert(a >= r->bgn); 138 assert(b <= r->end); 139 return true; 140 } 141 142 (*nextp) = new Range(a, b); 143 (*nextp)->next = r; 144 145 for (r = (*nextp); r->next; r = r->next); 146 tail = r; 147 return true; 148} 149 150bool Interval::contains(int pos) 151{ 152 for (Range *r = head; r && r->bgn <= pos; r = r->next) 153 if (r->end > pos) 154 return true; 155 return false; 156} 157 158bool Interval::overlaps(const Interval &iv) const 159{ 160 for (Range *rA = this->head; rA; rA = rA->next) 161 for (Range *rB = iv.head; rB; rB = rB->next) 162 if (rB->bgn < rA->end && 163 rB->end > rA->bgn) 164 return true; 165 return false; 166} 167 168void Interval::unify(Interval &that) 169{ 170 assert(this != &that); 171 for (Range *next, *r = that.head; r; r = next) { 172 next = r->next; 173 this->extend(r->bgn, r->end); 174 delete r; 175 } 176 that.head = NULL; 177} 178 179void Interval::print() const 180{ 181 if (!head) 182 return; 183 INFO("[%i %i)", head->bgn, head->end); 184 for (const Range *r = head->next; r; r = r->next) 185 INFO(" [%i %i)", r->bgn, r->end); 186 INFO("\n"); 187} 188 189void 190BitSet::andNot(const BitSet &set) 191{ 192 assert(data && set.data); 193 assert(size >= set.size); 194 for (unsigned int i = 0; i < (set.size + 31) / 32; ++i) 195 data[i] &= ~set.data[i]; 196} 197 198BitSet& BitSet::operator|=(const BitSet &set) 199{ 200 assert(data && set.data); 201 assert(size >= set.size); 202 for (unsigned int i = 0; i < (set.size + 31) / 32; ++i) 203 data[i] |= set.data[i]; 204 return *this; 205} 206 207bool BitSet::allocate(unsigned int nBits, bool zero) 208{ 209 if (data && size < nBits) { 210 FREE(data); 211 data = NULL; 212 } 213 size = nBits; 214 215 if (!data) 216 data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4)); 217 218 if (zero) 219 memset(data, 0, (size + 7) / 8); 220 else 221 data[(size + 31) / 32 - 1] = 0; // clear unused bits (e.g. for popCount) 222 223 return data; 224} 225 226unsigned int BitSet::popCount() const 227{ 228 unsigned int count = 0; 229 230 for (unsigned int i = 0; i < (size + 31) / 32; ++i) 231 if (data[i]) 232 count += util_bitcount(data[i]); 233 return count; 234} 235 236void BitSet::fill(uint32_t val) 237{ 238 unsigned int i; 239 for (i = 0; i < (size + 31) / 32; ++i) 240 data[i] = val; 241 if (val) 242 data[i] &= ~(0xffffffff << (size % 32)); // BE ? 243} 244 245void BitSet::setOr(BitSet *pA, BitSet *pB) 246{ 247 if (!pB) { 248 *this = *pA; 249 } else { 250 for (unsigned int i = 0; i < (size + 31) / 32; ++i) 251 data[i] = pA->data[i] | pB->data[i]; 252 } 253} 254 255void BitSet::print() const 256{ 257 unsigned int n = 0; 258 INFO("BitSet of size %u:\n", size); 259 for (unsigned int i = 0; i < (size + 31) / 32; ++i) { 260 uint32_t bits = data[i]; 261 while (bits) { 262 int pos = ffs(bits) - 1; 263 bits &= ~(1 << pos); 264 INFO(" %i", i * 32 + pos); 265 ++n; 266 if ((n % 16) == 0) 267 INFO("\n"); 268 } 269 } 270 if (n % 16) 271 INFO("\n"); 272} 273 274} // namespace nv50_ir 275