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 #ifndef __NV50_IR_UTIL_H__
24 #define __NV50_IR_UTIL_H__
25
26 #include <new>
27 #include <assert.h>
28 #include <stdio.h>
29 #include <memory>
30 #include <map>
31
32 #ifndef NDEBUG
33 # include <typeinfo>
34 #endif
35
36 #include "util/u_inlines.h"
37 #include "util/u_memory.h"
38
39 #define ERROR(args...) _debug_printf("ERROR: " args)
40 #define WARN(args...) _debug_printf("WARNING: " args)
41 #define INFO(args...) _debug_printf(args)
42
43 #define INFO_DBG(m, f, args...) \
44 do { \
45 if (m & NV50_IR_DEBUG_##f) \
46 _debug_printf(args); \
47 } while(0)
48
49 #define FATAL(args...) \
50 do { \
51 fprintf(stderr, args); \
52 abort(); \
53 } while(0)
54
55
56 #define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...) \
57 new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
58
59 #define new_Instruction(f, args...) \
60 NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)
61 #define new_CmpInstruction(f, args...) \
62 NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)
63 #define new_TexInstruction(f, args...) \
64 NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)
65 #define new_FlowInstruction(f, args...) \
66 NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)
67
68 #define new_LValue(f, args...) \
69 NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
70
71
72 #define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...) \
73 new ((p)->mem_##obj.allocate()) obj(p, args)
74
75 #define new_Symbol(p, args...) \
76 NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)
77 #define new_ImmediateValue(p, args...) \
78 NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)
79
80
81 #define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
82 #define delete_Value(p, val) (p)->releaseValue(val)
83
84
85 namespace nv50_ir {
86
87 class Iterator
88 {
89 public:
~Iterator()90 virtual ~Iterator() { };
91 virtual void next() = 0;
92 virtual void *get() const = 0;
93 virtual bool end() const = 0; // if true, get will return 0
reset()94 virtual void reset() { assert(0); } // only for graph iterators
95 };
96
97 typedef std::unique_ptr<Iterator> IteratorRef;
98
99 class ManipIterator : public Iterator
100 {
101 public:
102 virtual bool insert(void *) = 0; // insert after current position
103 virtual void erase() = 0;
104 };
105
106 // WARNING: do not use a->prev/next for __item or __list
107
108 #define DLLIST_DEL(__item) \
109 do { \
110 (__item)->prev->next = (__item)->next; \
111 (__item)->next->prev = (__item)->prev; \
112 (__item)->next = (__item); \
113 (__item)->prev = (__item); \
114 } while(0)
115
116 #define DLLIST_ADDTAIL(__list, __item) \
117 do { \
118 (__item)->next = (__list); \
119 (__item)->prev = (__list)->prev; \
120 (__list)->prev->next = (__item); \
121 (__list)->prev = (__item); \
122 } while(0)
123
124 #define DLLIST_ADDHEAD(__list, __item) \
125 do { \
126 (__item)->prev = (__list); \
127 (__item)->next = (__list)->next; \
128 (__list)->next->prev = (__item); \
129 (__list)->next = (__item); \
130 } while(0)
131
132 #define DLLIST_MERGE(__listA, __listB, ty) \
133 do { \
134 ty prevB = (__listB)->prev; \
135 (__listA)->prev->next = (__listB); \
136 (__listB)->prev->next = (__listA); \
137 (__listB)->prev = (__listA)->prev; \
138 (__listA)->prev = prevB; \
139 } while(0)
140
141 #define DLLIST_EMPTY(__list) ((__list)->next == (__list))
142
143 #define DLLIST_FOR_EACH(list, it) \
144 for (DLList::Iterator it = (list)->iterator(); !(it).end(); (it).next())
145
146 class DLList
147 {
148 public:
149 class Item
150 {
151 public:
Item(void * priv)152 Item(void *priv) : next(this), prev(this), data(priv) { }
153
154 public:
155 Item *next;
156 Item *prev;
157 void *data;
158 };
159
DLList()160 DLList() : head(0) { }
~DLList()161 ~DLList() { clear(); }
162
163 DLList(const DLList&) = delete;
164 DLList& operator=(const DLList&) = delete;
165
insertHead(void * data)166 inline void insertHead(void *data)
167 {
168 Item *item = new Item(data);
169
170 assert(data);
171
172 item->prev = &head;
173 item->next = head.next;
174 head.next->prev = item;
175 head.next = item;
176 }
177
insertTail(void * data)178 inline void insertTail(void *data)
179 {
180 Item *item = new Item(data);
181
182 assert(data);
183
184 DLLIST_ADDTAIL(&head, item);
185 }
186
insert(void * data)187 inline void insert(void *data) { insertTail(data); }
188
189 void clear();
190
191 class Iterator : public ManipIterator
192 {
193 public:
Iterator(Item * head,bool r)194 Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next),
195 term(head) { }
196
next()197 virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; }
get()198 virtual void *get() const { return pos->data; }
end()199 virtual bool end() const { return pos == term; }
200
201 // caution: if you're at end-2 and erase it, then do next, you're at end
202 virtual void erase();
203 virtual bool insert(void *data);
204
205 // move item to another list, no consistency with its iterators though
206 void moveToList(DLList&);
207
208 private:
209 const bool rev;
210 Item *pos;
211 Item *term;
212
213 friend class DLList;
214 };
215
erase(Iterator & pos)216 inline void erase(Iterator& pos)
217 {
218 pos.erase();
219 }
220
iterator()221 Iterator iterator()
222 {
223 return Iterator(&head, false);
224 }
225
revIterator()226 Iterator revIterator()
227 {
228 return Iterator(&head, true);
229 }
230
231 private:
232 Item head;
233 };
234
235 class Stack
236 {
237 public:
238 class Item {
239 public:
240 union {
241 void *p;
242 int i;
243 unsigned int u;
244 float f;
245 double d;
246 } u;
247
Item()248 Item() { memset(&u, 0, sizeof(u)); }
249 };
250
Stack()251 Stack() : size(0), limit(0), array(0) { }
~Stack()252 ~Stack() { if (array) FREE(array); }
253
254 Stack(const Stack&) = delete;
255 Stack& operator=(const Stack&) = delete;
256
push(int i)257 inline void push(int i) { Item data; data.u.i = i; push(data); }
push(unsigned int u)258 inline void push(unsigned int u) { Item data; data.u.u = u; push(data); }
push(void * p)259 inline void push(void *p) { Item data; data.u.p = p; push(data); }
push(float f)260 inline void push(float f) { Item data; data.u.f = f; push(data); }
261
push(Item data)262 inline void push(Item data)
263 {
264 if (size == limit)
265 resize();
266 array[size++] = data;
267 }
268
pop()269 inline Item pop()
270 {
271 if (!size) {
272 Item data;
273 assert(0);
274 return data;
275 }
276 return array[--size];
277 }
278
getSize()279 inline unsigned int getSize() { return size; }
280
peek()281 inline Item& peek() { assert(size); return array[size - 1]; }
282
283 void clear(bool releaseStorage = false)
284 {
285 if (releaseStorage && array)
286 FREE(array);
287 size = limit = 0;
288 }
289
290 void moveTo(Stack&); // move all items to target (not like push(pop()))
291
292 private:
resize()293 void resize()
294 {
295 unsigned int sizeOld, sizeNew;
296
297 sizeOld = limit * sizeof(Item);
298 limit = MAX2(4, limit + limit);
299 sizeNew = limit * sizeof(Item);
300
301 array = (Item *)REALLOC(array, sizeOld, sizeNew);
302 }
303
304 unsigned int size;
305 unsigned int limit;
306 Item *array;
307 };
308
309 class DynArray
310 {
311 public:
312 class Item
313 {
314 public:
315 union {
316 uint32_t u32;
317 void *p;
318 };
319 };
320
DynArray()321 DynArray() : data(NULL), size(0) { }
322
~DynArray()323 ~DynArray() { if (data) FREE(data); }
324
325 DynArray(const DynArray&) = delete;
326 DynArray& operator=(const DynArray&) = delete;
327
328 inline Item& operator[](unsigned int i)
329 {
330 if (i >= size)
331 resize(i);
332 return data[i];
333 }
334
335 inline const Item operator[](unsigned int i) const
336 {
337 return data[i];
338 }
339
resize(unsigned int index)340 void resize(unsigned int index)
341 {
342 const unsigned int oldSize = size * sizeof(Item);
343
344 if (!size)
345 size = 8;
346 while (size <= index)
347 size <<= 1;
348
349 data = (Item *)REALLOC(data, oldSize, size * sizeof(Item));
350 }
351
clear()352 void clear()
353 {
354 FREE(data);
355 data = NULL;
356 size = 0;
357 }
358
359 private:
360 Item *data;
361 unsigned int size;
362 };
363
364 class ArrayList
365 {
366 public:
ArrayList()367 ArrayList() : size(0) { }
368
insert(void * item,int & id)369 void insert(void *item, int& id)
370 {
371 id = ids.getSize() ? ids.pop().u.i : size++;
372 data[id].p = item;
373 }
374
remove(int & id)375 void remove(int& id)
376 {
377 const unsigned int uid = id;
378 assert(uid < size && data[id].p);
379 ids.push(uid);
380 data[uid].p = NULL;
381 id = -1;
382 }
383
getSize()384 inline unsigned int getSize() const { return size; }
385
get(unsigned int id)386 inline void *get(unsigned int id) { assert(id < size); return data[id].p; }
387
388 class Iterator : public nv50_ir::Iterator
389 {
390 public:
Iterator(const ArrayList * array)391 Iterator(const ArrayList *array) : pos(0), data(array->data)
392 {
393 size = array->getSize();
394 if (size)
395 nextValid();
396 }
397
nextValid()398 void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }
399
next()400 void next() { if (pos < size) { ++pos; nextValid(); } }
get()401 void *get() const { assert(pos < size); return data[pos].p; }
end()402 bool end() const { return pos >= size; }
403
404 private:
405 unsigned int pos;
406 unsigned int size;
407 const DynArray& data;
408
409 friend class ArrayList;
410 };
411
iterator()412 Iterator iterator() const { return Iterator(this); }
413
clear()414 void clear()
415 {
416 data.clear();
417 ids.clear(true);
418 size = 0;
419 }
420
421 private:
422 DynArray data;
423 Stack ids;
424 unsigned int size;
425 };
426
427 class Interval
428 {
429 public:
Interval()430 Interval() : head(0), tail(0) { }
431 Interval(const Interval&);
432 ~Interval();
433
434 Interval& operator=(const Interval&) = delete;
435
436 bool extend(int, int);
437 void insert(const Interval&);
438 void unify(Interval&); // clears source interval
439 void clear();
440
begin()441 inline int begin() const { return head ? head->bgn : -1; }
end()442 inline int end() const { checkTail(); return tail ? tail->end : -1; }
isEmpty()443 inline bool isEmpty() const { return !head; }
444 bool overlaps(const Interval&) const;
445 bool contains(int pos) const;
446
extent()447 inline int extent() const { return end() - begin(); }
448 int length() const;
449
450 void print() const;
451
452 inline void checkTail() const;
453
454 private:
455 class Range
456 {
457 public:
Range(int a,int b)458 Range(int a, int b) : next(0), bgn(a), end(b) { }
459
460 Range *next;
461 int bgn;
462 int end;
463
coalesce(Range ** ptail)464 void coalesce(Range **ptail)
465 {
466 Range *rnn;
467
468 while (next && end >= next->bgn) {
469 assert(bgn <= next->bgn);
470 rnn = next->next;
471 end = MAX2(end, next->end);
472 delete next;
473 next = rnn;
474 }
475 if (!next)
476 *ptail = this;
477 }
478 };
479
480 Range *head;
481 Range *tail;
482 };
483
484 class BitSet
485 {
486 public:
BitSet()487 BitSet() : marker(false), data(0), size(0) { }
BitSet(unsigned int nBits,bool zero)488 BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)
489 {
490 allocate(nBits, zero);
491 }
~BitSet()492 ~BitSet()
493 {
494 if (data)
495 FREE(data);
496 }
497
498 BitSet(const BitSet&) = delete;
499
500 // allocate will keep old data iff size is unchanged
501 bool allocate(unsigned int nBits, bool zero);
502 bool resize(unsigned int nBits); // keep old data, zero additional bits
503
getSize()504 inline unsigned int getSize() const { return size; }
505
506 void fill(uint32_t val);
507
508 void setOr(BitSet *, BitSet *); // second BitSet may be NULL
509
set(unsigned int i)510 inline void set(unsigned int i)
511 {
512 assert(i < size);
513 data[i / 32] |= 1 << (i % 32);
514 }
515 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
setRange(unsigned int i,unsigned int n)516 inline void setRange(unsigned int i, unsigned int n)
517 {
518 assert((i + n) <= size && (((i % 32) + n) <= 32));
519 data[i / 32] |= ((1 << n) - 1) << (i % 32);
520 }
setMask(unsigned int i,uint32_t m)521 inline void setMask(unsigned int i, uint32_t m)
522 {
523 assert(i < size);
524 data[i / 32] |= m;
525 }
526
clr(unsigned int i)527 inline void clr(unsigned int i)
528 {
529 assert(i < size);
530 data[i / 32] &= ~(1 << (i % 32));
531 }
532 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
clrRange(unsigned int i,unsigned int n)533 inline void clrRange(unsigned int i, unsigned int n)
534 {
535 assert((i + n) <= size && (((i % 32) + n) <= 32));
536 data[i / 32] &= ~(((1 << n) - 1) << (i % 32));
537 }
538
test(unsigned int i)539 inline bool test(unsigned int i) const
540 {
541 assert(i < size);
542 return data[i / 32] & (1 << (i % 32));
543 }
544 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
testRange(unsigned int i,unsigned int n)545 inline bool testRange(unsigned int i, unsigned int n) const
546 {
547 assert((i + n) <= size && (((i % 32) + n) <= 32));
548 return data[i / 32] & (((1 << n) - 1) << (i % 32));
549 }
550
551 // Find a range of count (<= 32) clear bits aligned to roundup_pow2(count).
552 int findFreeRange(unsigned int count, unsigned int max) const;
findFreeRange(unsigned int count)553 inline int findFreeRange(unsigned int count) const {
554 return findFreeRange(count, size);
555 }
556
557 BitSet& operator|=(const BitSet&);
558
559 BitSet& operator=(const BitSet& set)
560 {
561 assert(data && set.data);
562 assert(size == set.size);
563 memcpy(data, set.data, (set.size + 7) / 8);
564 return *this;
565 }
566
567 void andNot(const BitSet&);
568
569 unsigned int popCount() const;
570
571 void print() const;
572
573 public:
574 bool marker; // for user
575
576 private:
577 uint32_t *data;
578 unsigned int size;
579 };
580
checkTail()581 void Interval::checkTail() const
582 {
583 #if NV50_DEBUG & NV50_DEBUG_PROG_RA
584 Range *r = head;
585 while (r->next)
586 r = r->next;
587 assert(tail == r);
588 #endif
589 }
590
591 class MemoryPool
592 {
593 private:
enlargeAllocationsArray(const unsigned int id,unsigned int nr)594 inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)
595 {
596 const unsigned int size = sizeof(uint8_t *) * id;
597 const unsigned int incr = sizeof(uint8_t *) * nr;
598
599 uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);
600 if (!alloc)
601 return false;
602 allocArray = alloc;
603 return true;
604 }
605
enlargeCapacity()606 inline bool enlargeCapacity()
607 {
608 const unsigned int id = count >> objStepLog2;
609
610 uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);
611 if (!mem)
612 return false;
613
614 if (!(id % 32)) {
615 if (!enlargeAllocationsArray(id, 32)) {
616 FREE(mem);
617 return false;
618 }
619 }
620 allocArray[id] = mem;
621 return true;
622 }
623
624 public:
MemoryPool(unsigned int size,unsigned int incr)625 MemoryPool(unsigned int size, unsigned int incr) : objSize(size),
626 objStepLog2(incr)
627 {
628 allocArray = NULL;
629 released = NULL;
630 count = 0;
631 }
632
~MemoryPool()633 ~MemoryPool()
634 {
635 unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;
636 for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)
637 FREE(allocArray[i]);
638 if (allocArray)
639 FREE(allocArray);
640 }
641
642 MemoryPool(const MemoryPool&) = delete;
643 MemoryPool& operator=(const MemoryPool&) = delete;
644
allocate()645 void *allocate()
646 {
647 void *ret;
648 const unsigned int mask = (1 << objStepLog2) - 1;
649
650 if (released) {
651 ret = released;
652 released = *(void **)released;
653 return ret;
654 }
655
656 if (!(count & mask))
657 if (!enlargeCapacity())
658 return NULL;
659
660 ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;
661 ++count;
662 return ret;
663 }
664
release(void * ptr)665 void release(void *ptr)
666 {
667 *(void **)ptr = released;
668 released = ptr;
669 }
670
671 private:
672 uint8_t **allocArray; // array (list) of MALLOC allocations
673
674 void *released; // list of released objects
675
676 unsigned int count; // highest allocated object
677
678 const unsigned int objSize;
679 const unsigned int objStepLog2;
680 };
681
682 /**
683 * Composite object cloning policy.
684 *
685 * Encapsulates how sub-objects are to be handled (if at all) when a
686 * composite object is being cloned.
687 */
688 template<typename C>
689 class ClonePolicy
690 {
691 protected:
692 C *c;
693
694 public:
ClonePolicy(C * c)695 ClonePolicy(C *c) : c(c) {}
696
context()697 C *context() { return c; }
698
get(T * obj)699 template<typename T> T *get(T *obj)
700 {
701 void *clone = lookup(obj);
702 if (!clone)
703 clone = obj->clone(*this);
704 return reinterpret_cast<T *>(clone);
705 }
706
set(const T * obj,T * clone)707 template<typename T> void set(const T *obj, T *clone)
708 {
709 insert(obj, clone);
710 }
711
712 protected:
713 virtual void *lookup(void *obj) = 0;
714 virtual void insert(const void *obj, void *clone) = 0;
715 };
716
717 /**
718 * Shallow non-recursive cloning policy.
719 *
720 * Objects cloned with the "shallow" policy don't clone their
721 * children recursively, instead, the new copy shares its children
722 * with the original object.
723 */
724 template<typename C>
725 class ShallowClonePolicy : public ClonePolicy<C>
726 {
727 public:
ShallowClonePolicy(C * c)728 ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {}
729
730 protected:
lookup(void * obj)731 virtual void *lookup(void *obj)
732 {
733 return obj;
734 }
735
insert(const void * obj,void * clone)736 virtual void insert(const void *obj, void *clone)
737 {
738 }
739 };
740
741 template<typename C, typename T>
cloneShallow(C * c,T * obj)742 inline T *cloneShallow(C *c, T *obj)
743 {
744 ShallowClonePolicy<C> pol(c);
745 return obj->clone(pol);
746 }
747
748 /**
749 * Recursive cloning policy.
750 *
751 * Objects cloned with the "deep" policy clone their children
752 * recursively, keeping track of what has already been cloned to
753 * avoid making several new copies of the same object.
754 */
755 template<typename C>
756 class DeepClonePolicy : public ClonePolicy<C>
757 {
758 public:
DeepClonePolicy(C * c)759 DeepClonePolicy(C *c) : ClonePolicy<C>(c) {}
760
761 private:
762 std::map<const void *, void *> map;
763
764 protected:
lookup(void * obj)765 virtual void *lookup(void *obj)
766 {
767 return map[obj];
768 }
769
insert(const void * obj,void * clone)770 virtual void insert(const void *obj, void *clone)
771 {
772 map[obj] = clone;
773 }
774 };
775
776 } // namespace nv50_ir
777
778 #endif // __NV50_IR_UTIL_H__
779