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
) {
107 Interval::extend(int a
, int b
)
109 Range
*r
, **nextp
= &head
;
111 // NOTE: we need empty intervals for fixed registers
116 for (r
= head
; r
; r
= r
->next
) {
118 break; // insert before
143 (*nextp
) = new Range(a
, b
);
146 for (r
= (*nextp
); r
->next
; r
= r
->next
);
151 bool Interval::contains(int pos
)
153 for (Range
*r
= head
; r
&& r
->bgn
<= pos
; r
= r
->next
)
159 bool Interval::overlaps(const Interval
&iv
) const
161 for (Range
*rA
= this->head
; rA
; rA
= rA
->next
)
162 for (Range
*rB
= iv
.head
; rB
; rB
= rB
->next
)
163 if (rB
->bgn
< rA
->end
&&
169 void Interval::unify(Interval
&that
)
171 assert(this != &that
);
172 for (Range
*next
, *r
= that
.head
; r
; r
= next
) {
174 this->extend(r
->bgn
, r
->end
);
180 void Interval::print() const
184 INFO("[%i %i)", head
->bgn
, head
->end
);
185 for (const Range
*r
= head
->next
; r
; r
= r
->next
)
186 INFO(" [%i %i)", r
->bgn
, r
->end
);
191 BitSet::andNot(const BitSet
&set
)
193 assert(data
&& set
.data
);
194 assert(size
>= set
.size
);
195 for (unsigned int i
= 0; i
< (set
.size
+ 31) / 32; ++i
)
196 data
[i
] &= ~set
.data
[i
];
199 BitSet
& BitSet::operator|=(const BitSet
&set
)
201 assert(data
&& set
.data
);
202 assert(size
>= set
.size
);
203 for (unsigned int i
= 0; i
< (set
.size
+ 31) / 32; ++i
)
204 data
[i
] |= set
.data
[i
];
208 bool BitSet::allocate(unsigned int nBits
, bool zero
)
210 if (data
&& size
< nBits
) {
217 data
= reinterpret_cast<uint32_t *>(CALLOC((size
+ 31) / 32, 4));
220 memset(data
, 0, (size
+ 7) / 8);
223 data
[(size
+ 31) / 32 - 1] = 0; // clear unused bits (e.g. for popCount)
228 unsigned int BitSet::popCount() const
230 unsigned int count
= 0;
232 for (unsigned int i
= 0; i
< (size
+ 31) / 32; ++i
)
234 count
+= util_bitcount(data
[i
]);
238 void BitSet::fill(uint32_t val
)
241 for (i
= 0; i
< (size
+ 31) / 32; ++i
)
244 data
[i
] &= ~(0xffffffff << (size
% 32)); // BE ?
247 void BitSet::setOr(BitSet
*pA
, BitSet
*pB
)
252 for (unsigned int i
= 0; i
< (size
+ 31) / 32; ++i
)
253 data
[i
] = pA
->data
[i
] | pB
->data
[i
];
257 void BitSet::print() const
260 INFO("BitSet of size %u:\n", size
);
261 for (unsigned int i
= 0; i
< (size
+ 31) / 32; ++i
) {
262 uint32_t bits
= data
[i
];
264 int pos
= ffs(bits
) - 1;
266 INFO(" %i", i
* 32 + pos
);
276 } // namespace nv50_ir