2 * Copyright 2011 Christoph Bumiller
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:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
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
23 #include "nv50_ir_util.h"
29 for (Item *next, *item = head.next; item != &head; item = next) {
33 head.next = head.prev = &head;
37 DLList::Iterator::erase()
49 void DLList::Iterator::moveToList(DLList& dest)
53 assert(term != &dest.head);
59 DLLIST_ADDHEAD(&dest.head, item);
63 DLList::Iterator::insert(void *data)
65 Item *ins = new Item(data);
67 ins->next = pos->next;
69 pos->next->prev = ins;
79 Stack::moveTo(Stack& that)
81 unsigned int newSize = this->size + that.size;
83 while (newSize > that.limit)
85 memcpy(&that.array[that.size], &array[0], this->size * sizeof(Item));
99 for (Range *next, *r = head; r; r = next) {
106 Interval::extend(int a, int b)
108 Range *r, **nextp = &head;
110 // NOTE: we need empty intervals for fixed registers
115 for (r = head; r; r = r->next) {
117 break; // insert before
142 (*nextp) = new Range(a, b);
145 for (r = (*nextp); r->next; r = r->next);
150 bool Interval::contains(int pos)
152 for (Range *r = head; r && r->bgn <= pos; r = r->next)
158 bool Interval::overlaps(const Interval &iv) const
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 &&
168 void Interval::unify(Interval &that)
170 assert(this != &that);
171 for (Range *next, *r = that.head; r; r = next) {
173 this->extend(r->bgn, r->end);
179 void Interval::print() const
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);
190 BitSet::andNot(const BitSet &set)
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];
198 BitSet& BitSet::operator|=(const BitSet &set)
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];
207 bool BitSet::allocate(unsigned int nBits, bool zero)
209 if (data && size < nBits) {
216 data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4));
219 memset(data, 0, (size + 7) / 8);
221 data[(size + 31) / 32 - 1] = 0; // clear unused bits (e.g. for popCount)
226 unsigned int BitSet::popCount() const
228 unsigned int count = 0;
230 for (unsigned int i = 0; i < (size + 31) / 32; ++i)
232 count += util_bitcount(data[i]);
236 void BitSet::fill(uint32_t val)
239 for (i = 0; i < (size + 31) / 32; ++i)
242 data[i] &= ~(0xffffffff << (size % 32)); // BE ?
245 void BitSet::setOr(BitSet *pA, BitSet *pB)
250 for (unsigned int i = 0; i < (size + 31) / 32; ++i)
251 data[i] = pA->data[i] | pB->data[i];
255 void BitSet::print() const
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];
262 int pos = ffs(bits) - 1;
264 INFO(" %i", i * 32 + pos);
274 } // namespace nv50_ir