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