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 OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 #include "codegen/nv50_ir_util.h"
24
25 namespace nv50_ir {
26
clear()27 void 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
36 void
erase()37 DLList::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
moveToList(DLList & dest)49 void 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
62 bool
insert(void * data)63 DLList::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
78 void
moveTo(Stack & that)79 Stack::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
Interval(const Interval & that)91 Interval::Interval(const Interval& that) : head(NULL), tail(NULL)
92 {
93 this->insert(that);
94 }
95
~Interval()96 Interval::~Interval()
97 {
98 clear();
99 }
100
101 void
clear()102 Interval::clear()
103 {
104 for (Range *next, *r = head; r; r = next) {
105 next = r->next;
106 delete r;
107 }
108 head = tail = NULL;
109 }
110
111 bool
extend(int a,int b)112 Interval::extend(int a, int b)
113 {
114 Range *r, **nextp = &head;
115
116 // NOTE: we need empty intervals for fixed registers
117 // if (a == b)
118 // return false;
119 assert(a <= b);
120
121 for (r = head; r; r = r->next) {
122 if (b < r->bgn)
123 break; // insert before
124 if (a > r->end) {
125 // insert after
126 nextp = &r->next;
127 continue;
128 }
129
130 // overlap
131 if (a < r->bgn) {
132 r->bgn = a;
133 if (b > r->end)
134 r->end = b;
135 r->coalesce(&tail);
136 return true;
137 }
138 if (b > r->end) {
139 r->end = b;
140 r->coalesce(&tail);
141 return true;
142 }
143 assert(a >= r->bgn);
144 assert(b <= r->end);
145 return true;
146 }
147
148 (*nextp) = new Range(a, b);
149 (*nextp)->next = r;
150
151 for (r = (*nextp); r->next; r = r->next);
152 tail = r;
153 return true;
154 }
155
contains(int pos) const156 bool Interval::contains(int pos) const
157 {
158 for (Range *r = head; r && r->bgn <= pos; r = r->next)
159 if (r->end > pos)
160 return true;
161 return false;
162 }
163
overlaps(const Interval & that) const164 bool Interval::overlaps(const Interval &that) const
165 {
166 #if 1
167 Range *a = this->head;
168 Range *b = that.head;
169
170 while (a && b) {
171 if (b->bgn < a->end &&
172 b->end > a->bgn)
173 return true;
174 if (a->end <= b->bgn)
175 a = a->next;
176 else
177 b = b->next;
178 }
179 #else
180 for (Range *rA = this->head; rA; rA = rA->next)
181 for (Range *rB = iv.head; rB; rB = rB->next)
182 if (rB->bgn < rA->end &&
183 rB->end > rA->bgn)
184 return true;
185 #endif
186 return false;
187 }
188
insert(const Interval & that)189 void Interval::insert(const Interval &that)
190 {
191 for (Range *r = that.head; r; r = r->next)
192 this->extend(r->bgn, r->end);
193 }
194
unify(Interval & that)195 void Interval::unify(Interval &that)
196 {
197 assert(this != &that);
198 for (Range *next, *r = that.head; r; r = next) {
199 next = r->next;
200 this->extend(r->bgn, r->end);
201 delete r;
202 }
203 that.head = NULL;
204 }
205
length() const206 int Interval::length() const
207 {
208 int len = 0;
209 for (Range *r = head; r; r = r->next)
210 len += r->bgn - r->end;
211 return len;
212 }
213
print() const214 void Interval::print() const
215 {
216 if (!head)
217 return;
218 INFO("[%i %i)", head->bgn, head->end);
219 for (const Range *r = head->next; r; r = r->next)
220 INFO(" [%i %i)", r->bgn, r->end);
221 INFO("\n");
222 }
223
224 void
andNot(const BitSet & set)225 BitSet::andNot(const BitSet &set)
226 {
227 assert(data && set.data);
228 assert(size >= set.size);
229 for (unsigned int i = 0; i < (set.size + 31) / 32; ++i)
230 data[i] &= ~set.data[i];
231 }
232
operator |=(const BitSet & set)233 BitSet& BitSet::operator|=(const BitSet &set)
234 {
235 assert(data && set.data);
236 assert(size >= set.size);
237 for (unsigned int i = 0; i < (set.size + 31) / 32; ++i)
238 data[i] |= set.data[i];
239 return *this;
240 }
241
resize(unsigned int nBits)242 bool BitSet::resize(unsigned int nBits)
243 {
244 if (!data || !nBits)
245 return allocate(nBits, true);
246 const unsigned int p = (size + 31) / 32;
247 const unsigned int n = (nBits + 31) / 32;
248 if (n == p)
249 return true;
250
251 data = (uint32_t *)REALLOC(data, 4 * p, 4 * n);
252 if (!data) {
253 size = 0;
254 return false;
255 }
256 if (n > p)
257 memset(&data[p], 0, (n - p) * 4);
258 if (nBits < size && (nBits % 32))
259 data[(nBits + 31) / 32 - 1] &= (1 << (nBits % 32)) - 1;
260
261 size = nBits;
262 return true;
263 }
264
allocate(unsigned int nBits,bool zero)265 bool BitSet::allocate(unsigned int nBits, bool zero)
266 {
267 if (data && size < nBits) {
268 FREE(data);
269 data = NULL;
270 }
271 size = nBits;
272
273 if (!data)
274 data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4));
275
276 if (zero)
277 memset(data, 0, (size + 7) / 8);
278 else
279 if (size % 32) // clear unused bits (e.g. for popCount)
280 data[(size + 31) / 32 - 1] &= (1 << (size % 32)) - 1;
281
282 return data;
283 }
284
popCount() const285 unsigned int BitSet::popCount() const
286 {
287 unsigned int count = 0;
288
289 for (unsigned int i = 0; i < (size + 31) / 32; ++i)
290 if (data[i])
291 count += util_bitcount(data[i]);
292 return count;
293 }
294
fill(uint32_t val)295 void BitSet::fill(uint32_t val)
296 {
297 unsigned int i;
298 for (i = 0; i < (size + 31) / 32; ++i)
299 data[i] = val;
300 if (val && i)
301 data[i - 1] &= (1 << (size % 32)) - 1;
302 }
303
setOr(BitSet * pA,BitSet * pB)304 void BitSet::setOr(BitSet *pA, BitSet *pB)
305 {
306 if (!pB) {
307 *this = *pA;
308 } else {
309 for (unsigned int i = 0; i < (size + 31) / 32; ++i)
310 data[i] = pA->data[i] | pB->data[i];
311 }
312 }
313
findFreeRange(unsigned int count,unsigned int max) const314 int BitSet::findFreeRange(unsigned int count, unsigned int max) const
315 {
316 const uint32_t m = (1 << count) - 1;
317 int pos = max;
318 unsigned int i;
319 const unsigned int end = (max + 31) / 32;
320
321 if (count == 1) {
322 for (i = 0; i < end; ++i) {
323 pos = ffs(~data[i]) - 1;
324 if (pos >= 0)
325 break;
326 }
327 } else
328 if (count == 2) {
329 for (i = 0; i < end; ++i) {
330 if (data[i] != 0xffffffff) {
331 uint32_t b = data[i] | (data[i] >> 1) | 0xaaaaaaaa;
332 pos = ffs(~b) - 1;
333 if (pos >= 0)
334 break;
335 }
336 }
337 } else
338 if (count == 4 || count == 3) {
339 for (i = 0; i < end; ++i) {
340 if (data[i] != 0xffffffff) {
341 uint32_t b =
342 (data[i] >> 0) | (data[i] >> 1) |
343 (data[i] >> 2) | (data[i] >> 3) | 0xeeeeeeee;
344 pos = ffs(~b) - 1;
345 if (pos >= 0)
346 break;
347 }
348 }
349 } else {
350 if (count <= 8)
351 count = 8;
352 else
353 if (count <= 16)
354 count = 16;
355 else
356 count = 32;
357
358 for (i = 0; i < end; ++i) {
359 if (data[i] != 0xffffffff) {
360 for (pos = 0; pos < 32; pos += count)
361 if (!(data[i] & (m << pos)))
362 break;
363 if (pos < 32)
364 break;
365 }
366 }
367 }
368
369 // If we couldn't find a position, we can have a left-over -1 in pos. Make
370 // sure to abort in such a case.
371 if (pos < 0)
372 return -1;
373
374 pos += i * 32;
375
376 return ((pos + count) <= max) ? pos : -1;
377 }
378
print() const379 void BitSet::print() const
380 {
381 unsigned int n = 0;
382 INFO("BitSet of size %u:\n", size);
383 for (unsigned int i = 0; i < (size + 31) / 32; ++i) {
384 uint32_t bits = data[i];
385 while (bits) {
386 int pos = ffs(bits) - 1;
387 bits &= ~(1 << pos);
388 INFO(" %i", i * 32 + pos);
389 ++n;
390 if ((n % 16) == 0)
391 INFO("\n");
392 }
393 }
394 if (n % 16)
395 INFO("\n");
396 }
397
398 } // namespace nv50_ir
399