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 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.
23 #ifndef __NV50_IR_UTIL_H__
24 #define __NV50_IR_UTIL_H__
36 #include "util/u_inlines.h"
37 #include "util/u_memory.h"
39 #define ERROR(args...) _debug_printf("ERROR: " args)
40 #define WARN(args...) _debug_printf("WARNING: " args)
41 #define INFO(args...) _debug_printf(args)
43 #define INFO_DBG(m, f, args...) \
45 if (m & NV50_IR_DEBUG_##f) \
46 _debug_printf(args); \
49 #define FATAL(args...) \
51 fprintf(stderr, args); \
56 #define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...) \
57 new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
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)
68 #define new_LValue(f, args...) \
69 NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
72 #define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...) \
73 new ((p)->mem_##obj.allocate()) obj(p, args)
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)
81 #define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
82 #define delete_Value(p, val) (p)->releaseValue(val)
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
94 virtual void reset() { assert(0); } // only for graph iterators
97 #if __cplusplus >= 201103L
98 typedef std::unique_ptr
<Iterator
> IteratorRef
;
100 typedef std::auto_ptr
<Iterator
> IteratorRef
;
103 class ManipIterator
: public Iterator
106 virtual bool insert(void *) = 0; // insert after current position
107 virtual void erase() = 0;
110 // WARNING: do not use a->prev/next for __item or __list
112 #define DLLIST_DEL(__item) \
114 (__item)->prev->next = (__item)->next; \
115 (__item)->next->prev = (__item)->prev; \
116 (__item)->next = (__item); \
117 (__item)->prev = (__item); \
120 #define DLLIST_ADDTAIL(__list, __item) \
122 (__item)->next = (__list); \
123 (__item)->prev = (__list)->prev; \
124 (__list)->prev->next = (__item); \
125 (__list)->prev = (__item); \
128 #define DLLIST_ADDHEAD(__list, __item) \
130 (__item)->prev = (__list); \
131 (__item)->next = (__list)->next; \
132 (__list)->next->prev = (__item); \
133 (__list)->next = (__item); \
136 #define DLLIST_MERGE(__listA, __listB, ty) \
138 ty prevB = (__listB)->prev; \
139 (__listA)->prev->next = (__listB); \
140 (__listB)->prev->next = (__listA); \
141 (__listB)->prev = (__listA)->prev; \
142 (__listA)->prev = prevB; \
145 #define DLLIST_EMPTY(__list) ((__list)->next == (__list))
147 #define DLLIST_FOR_EACH(list, it) \
148 for (DLList::Iterator it = (list)->iterator(); !(it).end(); (it).next())
156 Item(void *priv
) : next(this), prev(this), data(priv
) { }
164 DLList() : head(0) { }
165 ~DLList() { clear(); }
167 inline void insertHead(void *data
)
169 Item
*item
= new Item(data
);
174 item
->next
= head
.next
;
175 head
.next
->prev
= item
;
179 inline void insertTail(void *data
)
181 Item
*item
= new Item(data
);
185 DLLIST_ADDTAIL(&head
, item
);
188 inline void insert(void *data
) { insertTail(data
); }
192 class Iterator
: public ManipIterator
195 Iterator(Item
*head
, bool r
) : rev(r
), pos(r
? head
->prev
: head
->next
),
198 virtual void next() { if (!end()) pos
= rev
? pos
->prev
: pos
->next
; }
199 virtual void *get() const { return pos
->data
; }
200 virtual bool end() const { return pos
== term
; }
202 // caution: if you're at end-2 and erase it, then do next, you're at end
203 virtual void erase();
204 virtual bool insert(void *data
);
206 // move item to another list, no consistency with its iterators though
207 void moveToList(DLList
&);
217 inline void erase(Iterator
& pos
)
224 return Iterator(&head
, false);
227 Iterator
revIterator()
229 return Iterator(&head
, true);
249 Item() { memset(&u
, 0, sizeof(u
)); }
252 Stack() : size(0), limit(0), array(0) { }
253 ~Stack() { if (array
) FREE(array
); }
255 inline void push(int i
) { Item data
; data
.u
.i
= i
; push(data
); }
256 inline void push(unsigned int u
) { Item data
; data
.u
.u
= u
; push(data
); }
257 inline void push(void *p
) { Item data
; data
.u
.p
= p
; push(data
); }
258 inline void push(float f
) { Item data
; data
.u
.f
= f
; push(data
); }
260 inline void push(Item data
)
264 array
[size
++] = data
;
274 return array
[--size
];
277 inline unsigned int getSize() { return size
; }
279 inline Item
& peek() { assert(size
); return array
[size
- 1]; }
281 void clear(bool releaseStorage
= false)
283 if (releaseStorage
&& array
)
288 void moveTo(Stack
&); // move all items to target (not like push(pop()))
293 unsigned int sizeOld
, sizeNew
;
295 sizeOld
= limit
* sizeof(Item
);
296 limit
= MAX2(4, limit
+ limit
);
297 sizeNew
= limit
* sizeof(Item
);
299 array
= (Item
*)REALLOC(array
, sizeOld
, sizeNew
);
319 DynArray() : data(NULL
), size(0) { }
321 ~DynArray() { if (data
) FREE(data
); }
323 inline Item
& operator[](unsigned int i
)
330 inline const Item
operator[](unsigned int i
) const
335 void resize(unsigned int index
)
337 const unsigned int oldSize
= size
* sizeof(Item
);
341 while (size
<= index
)
344 data
= (Item
*)REALLOC(data
, oldSize
, size
* sizeof(Item
));
362 ArrayList() : size(0) { }
364 void insert(void *item
, int& id
)
366 id
= ids
.getSize() ? ids
.pop().u
.i
: size
++;
372 const unsigned int uid
= id
;
373 assert(uid
< size
&& data
[id
].p
);
379 inline int getSize() const { return size
; }
381 inline void *get(unsigned int id
) { assert(id
< size
); return data
[id
].p
; }
383 class Iterator
: public nv50_ir::Iterator
386 Iterator(const ArrayList
*array
) : pos(0), data(array
->data
)
388 size
= array
->getSize();
393 void nextValid() { while ((pos
< size
) && !data
[pos
].p
) ++pos
; }
395 void next() { if (pos
< size
) { ++pos
; nextValid(); } }
396 void *get() const { assert(pos
< size
); return data
[pos
].p
; }
397 bool end() const { return pos
>= size
; }
402 const DynArray
& data
;
404 friend class ArrayList
;
407 Iterator
iterator() const { return Iterator(this); }
425 Interval() : head(0), tail(0) { }
426 Interval(const Interval
&);
429 bool extend(int, int);
430 void insert(const Interval
&);
431 void unify(Interval
&); // clears source interval
434 inline int begin() const { return head
? head
->bgn
: -1; }
435 inline int end() const { checkTail(); return tail
? tail
->end
: -1; }
436 inline bool isEmpty() const { return !head
; }
437 bool overlaps(const Interval
&) const;
438 bool contains(int pos
) const;
440 inline int extent() const { return end() - begin(); }
445 inline void checkTail() const;
451 Range(int a
, int b
) : next(0), bgn(a
), end(b
) { }
457 void coalesce(Range
**ptail
)
461 while (next
&& end
>= next
->bgn
) {
462 assert(bgn
<= next
->bgn
);
464 end
= MAX2(end
, next
->end
);
480 BitSet() : marker(false), data(0), size(0) { }
481 BitSet(unsigned int nBits
, bool zero
) : marker(false), data(0), size(0)
483 allocate(nBits
, zero
);
491 // allocate will keep old data iff size is unchanged
492 bool allocate(unsigned int nBits
, bool zero
);
493 bool resize(unsigned int nBits
); // keep old data, zero additional bits
495 inline unsigned int getSize() const { return size
; }
497 void fill(uint32_t val
);
499 void setOr(BitSet
*, BitSet
*); // second BitSet may be NULL
501 inline void set(unsigned int i
)
504 data
[i
/ 32] |= 1 << (i
% 32);
506 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
507 inline void setRange(unsigned int i
, unsigned int n
)
509 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
510 data
[i
/ 32] |= ((1 << n
) - 1) << (i
% 32);
512 inline void setMask(unsigned int i
, uint32_t m
)
518 inline void clr(unsigned int i
)
521 data
[i
/ 32] &= ~(1 << (i
% 32));
523 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
524 inline void clrRange(unsigned int i
, unsigned int n
)
526 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
527 data
[i
/ 32] &= ~(((1 << n
) - 1) << (i
% 32));
530 inline bool test(unsigned int i
) const
533 return data
[i
/ 32] & (1 << (i
% 32));
535 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
536 inline bool testRange(unsigned int i
, unsigned int n
) const
538 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
539 return data
[i
/ 32] & (((1 << n
) - 1) << (i
% 32));
542 // Find a range of count (<= 32) clear bits aligned to roundup_pow2(count).
543 int findFreeRange(unsigned int count
, unsigned int max
) const;
544 inline int findFreeRange(unsigned int count
) const {
545 return findFreeRange(count
, size
);
548 BitSet
& operator|=(const BitSet
&);
550 BitSet
& operator=(const BitSet
& set
)
552 assert(data
&& set
.data
);
553 assert(size
== set
.size
);
554 memcpy(data
, set
.data
, (set
.size
+ 7) / 8);
558 void andNot(const BitSet
&);
560 // bits = (bits | setMask) & ~clrMask
561 inline void periodicMask32(uint32_t setMask
, uint32_t clrMask
)
563 for (unsigned int i
= 0; i
< (size
+ 31) / 32; ++i
)
564 data
[i
] = (data
[i
] | setMask
) & ~clrMask
;
567 unsigned int popCount() const;
572 bool marker
; // for user
579 void Interval::checkTail() const
581 #if NV50_DEBUG & NV50_DEBUG_PROG_RA
592 inline bool enlargeAllocationsArray(const unsigned int id
, unsigned int nr
)
594 const unsigned int size
= sizeof(uint8_t *) * id
;
595 const unsigned int incr
= sizeof(uint8_t *) * nr
;
597 uint8_t **alloc
= (uint8_t **)REALLOC(allocArray
, size
, size
+ incr
);
604 inline bool enlargeCapacity()
606 const unsigned int id
= count
>> objStepLog2
;
608 uint8_t *const mem
= (uint8_t *)MALLOC(objSize
<< objStepLog2
);
613 if (!enlargeAllocationsArray(id
, 32)) {
618 allocArray
[id
] = mem
;
623 MemoryPool(unsigned int size
, unsigned int incr
) : objSize(size
),
633 unsigned int allocCount
= (count
+ (1 << objStepLog2
) - 1) >> objStepLog2
;
634 for (unsigned int i
= 0; i
< allocCount
&& allocArray
[i
]; ++i
)
643 const unsigned int mask
= (1 << objStepLog2
) - 1;
647 released
= *(void **)released
;
652 if (!enlargeCapacity())
655 ret
= allocArray
[count
>> objStepLog2
] + (count
& mask
) * objSize
;
660 void release(void *ptr
)
662 *(void **)ptr
= released
;
667 uint8_t **allocArray
; // array (list) of MALLOC allocations
669 void *released
; // list of released objects
671 unsigned int count
; // highest allocated object
673 const unsigned int objSize
;
674 const unsigned int objStepLog2
;
678 * Composite object cloning policy.
680 * Encapsulates how sub-objects are to be handled (if at all) when a
681 * composite object is being cloned.
690 ClonePolicy(C
*c
) : c(c
) {}
692 C
*context() { return c
; }
694 template<typename T
> T
*get(T
*obj
)
696 void *clone
= lookup(obj
);
698 clone
= obj
->clone(*this);
699 return reinterpret_cast<T
*>(clone
);
702 template<typename T
> void set(const T
*obj
, T
*clone
)
708 virtual void *lookup(void *obj
) = 0;
709 virtual void insert(const void *obj
, void *clone
) = 0;
713 * Shallow non-recursive cloning policy.
715 * Objects cloned with the "shallow" policy don't clone their
716 * children recursively, instead, the new copy shares its children
717 * with the original object.
720 class ShallowClonePolicy
: public ClonePolicy
<C
>
723 ShallowClonePolicy(C
*c
) : ClonePolicy
<C
>(c
) {}
726 virtual void *lookup(void *obj
)
731 virtual void insert(const void *obj
, void *clone
)
736 template<typename C
, typename T
>
737 inline T
*cloneShallow(C
*c
, T
*obj
)
739 ShallowClonePolicy
<C
> pol(c
);
740 return obj
->clone(pol
);
744 * Recursive cloning policy.
746 * Objects cloned with the "deep" policy clone their children
747 * recursively, keeping track of what has already been cloned to
748 * avoid making several new copies of the same object.
751 class DeepClonePolicy
: public ClonePolicy
<C
>
754 DeepClonePolicy(C
*c
) : ClonePolicy
<C
>(c
) {}
757 std::map
<const void *, void *> map
;
760 virtual void *lookup(void *obj
)
765 virtual void insert(const void *obj
, void *clone
)
771 template<typename S
, typename T
>
774 std::map
<S
, T
> forth
;
778 bimap() : l(back
), r(forth
) { }
779 bimap(const bimap
<S
, T
> &m
)
780 : forth(m
.forth
), back(m
.back
), l(back
), r(forth
) { }
782 void insert(const S
&s
, const T
&t
)
784 forth
.insert(std::make_pair(s
, t
));
785 back
.insert(std::make_pair(t
, s
));
788 typedef typename
std::map
<T
, S
>::const_iterator l_iterator
;
789 const std::map
<T
, S
> &l
;
790 typedef typename
std::map
<S
, T
>::const_iterator r_iterator
;
791 const std::map
<S
, T
> &r
;
794 } // namespace nv50_ir
796 #endif // __NV50_IR_UTIL_H__