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 #ifndef __NV50_IR_UTIL_H__
24 #define __NV50_IR_UTIL_H__
30 #include "util/u_inlines.h"
31 #include "util/u_memory.h"
33 #define ERROR(args...) debug_printf("ERROR: " args)
34 #define WARN(args...) debug_printf("WARNING: " args)
35 #define INFO(args...) debug_printf(args)
37 #define INFO_DBG(m, f, args...) \
39 if (m & NV50_IR_DEBUG_##f) \
43 #define FATAL(args...) \
45 fprintf(stderr, args); \
50 #define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...) \
51 new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
53 #define new_Instruction(f, args...) \
54 NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)
55 #define new_CmpInstruction(f, args...) \
56 NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)
57 #define new_TexInstruction(f, args...) \
58 NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)
59 #define new_FlowInstruction(f, args...) \
60 NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)
62 #define new_LValue(f, args...) \
63 NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
66 #define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...) \
67 new ((p)->mem_##obj.allocate()) obj(p, args)
69 #define new_Symbol(p, args...) \
70 NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)
71 #define new_ImmediateValue(p, args...) \
72 NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)
75 #define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
76 #define delete_Value(p, val) (p)->releaseValue(val)
84 virtual void next() = 0;
85 virtual void *get() const = 0;
86 virtual bool end() const = 0; // if true, get will return 0
89 class ManipIterator
: public Iterator
92 virtual bool insert(void *) = 0; // insert after current position
93 virtual void erase() = 0;
96 // WARNING: do not use a->prev/next for __item or __list
98 #define DLLIST_DEL(__item) \
100 (__item)->prev->next = (__item)->next; \
101 (__item)->next->prev = (__item)->prev; \
102 (__item)->next = (__item); \
103 (__item)->prev = (__item); \
106 #define DLLIST_ADDTAIL(__list, __item) \
108 (__item)->next = (__list); \
109 (__item)->prev = (__list)->prev; \
110 (__list)->prev->next = (__item); \
111 (__list)->prev = (__item); \
114 #define DLLIST_ADDHEAD(__list, __item) \
116 (__item)->prev = (__list); \
117 (__item)->next = (__list)->next; \
118 (__list)->next->prev = (__item); \
119 (__list)->next = (__item); \
122 #define DLLIST_MERGE(__listA, __listB, ty) \
124 ty prevB = (__listB)->prev; \
125 (__listA)->prev->next = (__listB); \
126 (__listB)->prev->next = (__listA); \
127 (__listB)->prev = (__listA)->prev; \
128 (__listA)->prev = prevB; \
131 #define DLLIST_FOR_EACH(list, it) \
132 for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())
140 Item(void *priv
) : next(this), prev(this), data(priv
) { }
148 DLList() : head(0) { }
149 ~DLList() { clear(); }
151 inline void insertHead(void *data
)
153 Item
*item
= new Item(data
);
158 item
->next
= head
.next
;
159 head
.next
->prev
= item
;
163 inline void insertTail(void *data
)
165 Item
*item
= new Item(data
);
169 DLLIST_ADDTAIL(&head
, item
);
172 inline void insert(void *data
) { insertTail(data
); }
176 class Iterator
: public ManipIterator
179 Iterator(Item
*head
, bool r
) : rev(r
), pos(r
? head
->prev
: head
->next
),
182 virtual void next() { if (!end()) pos
= rev
? pos
->prev
: pos
->next
; }
183 virtual void *get() const { return pos
->data
; }
184 virtual bool end() const { return pos
== term
; }
186 // caution: if you're at end-2 and erase it, then do next, you're at end
187 virtual void erase();
188 virtual bool insert(void *data
);
190 // move item to a another list, no consistency with its iterators though
191 void moveToList(DLList
&);
201 inline void erase(Iterator
& pos
)
208 return Iterator(&head
, false);
211 Iterator
revIterator()
213 return Iterator(&head
, true);
233 Item() { memset(&u
, 0, sizeof(u
)); }
236 Stack() : size(0), limit(0), array(0) { }
237 ~Stack() { if (array
) FREE(array
); }
239 inline void push(int i
) { Item data
; data
.u
.i
= i
; push(data
); }
240 inline void push(unsigned int u
) { Item data
; data
.u
.u
= u
; push(data
); }
241 inline void push(void *p
) { Item data
; data
.u
.p
= p
; push(data
); }
242 inline void push(float f
) { Item data
; data
.u
.f
= f
; push(data
); }
244 inline void push(Item data
)
248 array
[size
++] = data
;
258 return array
[--size
];
261 inline unsigned int getSize() { return size
; }
263 inline Item
& peek() { assert(size
); return array
[size
- 1]; }
265 void clear(bool releaseStorage
= false)
267 if (releaseStorage
&& array
)
272 void moveTo(Stack
&); // move all items to target (not like push(pop()))
277 unsigned int sizeOld
, sizeNew
;
279 sizeOld
= limit
* sizeof(Item
);
280 limit
= MAX2(4, limit
+ limit
);
281 sizeNew
= limit
* sizeof(Item
);
283 array
= (Item
*)REALLOC(array
, sizeOld
, sizeNew
);
303 DynArray() : data(NULL
), size(0) { }
305 ~DynArray() { if (data
) FREE(data
); }
307 inline Item
& operator[](unsigned int i
)
314 inline const Item
operator[](unsigned int i
) const
319 void resize(unsigned int index
)
321 const unsigned int oldSize
= size
* sizeof(Item
);
325 while (size
<= index
)
328 data
= (Item
*)REALLOC(data
, oldSize
, size
* sizeof(Item
));
339 ArrayList() : size(0) { }
341 void insert(void *item
, int& id
)
343 id
= ids
.getSize() ? ids
.pop().u
.i
: size
++;
349 const unsigned int uid
= id
;
350 assert(uid
< size
&& data
[id
].p
);
356 inline int getSize() const { return size
; }
358 inline void *get(unsigned int id
) { assert(id
< size
); return data
[id
].p
; }
360 class Iterator
: public nv50_ir::Iterator
363 Iterator(const ArrayList
*array
) : pos(0), data(array
->data
)
365 size
= array
->getSize();
370 void nextValid() { while ((pos
< size
) && !data
[pos
].p
) ++pos
; }
372 void next() { if (pos
< size
) { ++pos
; nextValid(); } }
373 void *get() const { assert(pos
< size
); return data
[pos
].p
; }
374 bool end() const { return pos
>= size
; }
379 const DynArray
& data
;
381 friend class ArrayList
;
384 Iterator
iterator() const { return Iterator(this); }
395 Interval() : head(0), tail(0) { }
398 bool extend(int, int);
399 void unify(Interval
&); // clears source interval
402 inline int begin() { return head
? head
->bgn
: -1; }
403 inline int end() { checkTail(); return tail
? tail
->end
: -1; }
404 inline bool isEmpty() const { return !head
; }
405 bool overlaps(const Interval
&) const;
406 bool contains(int pos
);
410 inline void checkTail() const;
416 Range(int a
, int b
) : next(0), bgn(a
), end(b
) { }
422 void coalesce(Range
**ptail
)
426 while (next
&& end
>= next
->bgn
) {
427 assert(bgn
<= next
->bgn
);
429 end
= MAX2(end
, next
->end
);
445 BitSet() : marker(false), data(0), size(0) { }
446 BitSet(unsigned int nBits
, bool zero
) : marker(false), data(0), size(0)
448 allocate(nBits
, zero
);
456 bool allocate(unsigned int nBits
, bool zero
);
458 inline unsigned int getSize() const { return size
; }
460 void fill(uint32_t val
);
462 void setOr(BitSet
*, BitSet
*); // second BitSet may be NULL
464 inline void set(unsigned int i
)
467 data
[i
/ 32] |= 1 << (i
% 32);
470 inline void clr(unsigned int i
)
473 data
[i
/ 32] &= ~(1 << (i
% 32));
476 inline bool test(unsigned int i
) const
479 return data
[i
/ 32] & (1 << (i
% 32));
482 BitSet
& operator|=(const BitSet
&);
484 BitSet
& operator=(const BitSet
& set
)
486 assert(data
&& set
.data
);
487 assert(size
== set
.size
);
488 memcpy(data
, set
.data
, (set
.size
+ 7) / 8);
492 void andNot(const BitSet
&);
494 unsigned int popCount() const;
499 bool marker
; // for user
506 void Interval::checkTail() const
508 #if NV50_DEBUG & NV50_DEBUG_PROG_RA
519 inline bool enlargeAllocationsArray(const unsigned int id
, unsigned int nr
)
521 const unsigned int size
= sizeof(uint8_t *) * id
;
522 const unsigned int incr
= sizeof(uint8_t *) * nr
;
524 uint8_t **alloc
= (uint8_t **)REALLOC(allocArray
, size
, size
+ incr
);
531 inline bool enlargeCapacity()
533 const unsigned int id
= count
>> objStepLog2
;
535 uint8_t *const mem
= (uint8_t *)MALLOC(objSize
<< objStepLog2
);
540 if (!enlargeAllocationsArray(id
, 32)) {
545 allocArray
[id
] = mem
;
550 MemoryPool(unsigned int size
, unsigned int incr
) : objSize(size
),
560 unsigned int allocCount
= (count
+ (1 << objStepLog2
) - 1) >> objStepLog2
;
561 for (unsigned int i
= 0; i
< allocCount
&& allocArray
[i
]; ++i
)
570 const unsigned int mask
= (1 << objStepLog2
) - 1;
574 released
= *(void **)released
;
579 if (!enlargeCapacity())
582 ret
= allocArray
[count
>> objStepLog2
] + (count
& mask
) * objSize
;
587 void release(void *ptr
)
589 *(void **)ptr
= released
;
594 uint8_t **allocArray
; // array (list) of MALLOC allocations
596 void *released
; // list of released objects
598 unsigned int count
; // highest allocated object
600 const unsigned int objSize
;
601 const unsigned int objStepLog2
;
604 } // namespace nv50_ir
606 #endif // __NV50_IR_UTIL_H__