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) \
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 typedef std::auto_ptr
<Iterator
> IteratorRef
;
99 class ManipIterator
: public Iterator
102 virtual bool insert(void *) = 0; // insert after current position
103 virtual void erase() = 0;
106 // WARNING: do not use a->prev/next for __item or __list
108 #define DLLIST_DEL(__item) \
110 (__item)->prev->next = (__item)->next; \
111 (__item)->next->prev = (__item)->prev; \
112 (__item)->next = (__item); \
113 (__item)->prev = (__item); \
116 #define DLLIST_ADDTAIL(__list, __item) \
118 (__item)->next = (__list); \
119 (__item)->prev = (__list)->prev; \
120 (__list)->prev->next = (__item); \
121 (__list)->prev = (__item); \
124 #define DLLIST_ADDHEAD(__list, __item) \
126 (__item)->prev = (__list); \
127 (__item)->next = (__list)->next; \
128 (__list)->next->prev = (__item); \
129 (__list)->next = (__item); \
132 #define DLLIST_MERGE(__listA, __listB, ty) \
134 ty prevB = (__listB)->prev; \
135 (__listA)->prev->next = (__listB); \
136 (__listB)->prev->next = (__listA); \
137 (__listB)->prev = (__listA)->prev; \
138 (__listA)->prev = prevB; \
141 #define DLLIST_EMPTY(__list) ((__list)->next == (__list))
143 #define DLLIST_FOR_EACH(list, it) \
144 for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())
152 Item(void *priv
) : next(this), prev(this), data(priv
) { }
160 DLList() : head(0) { }
161 ~DLList() { clear(); }
163 inline void insertHead(void *data
)
165 Item
*item
= new Item(data
);
170 item
->next
= head
.next
;
171 head
.next
->prev
= item
;
175 inline void insertTail(void *data
)
177 Item
*item
= new Item(data
);
181 DLLIST_ADDTAIL(&head
, item
);
184 inline void insert(void *data
) { insertTail(data
); }
188 class Iterator
: public ManipIterator
191 Iterator(Item
*head
, bool r
) : rev(r
), pos(r
? head
->prev
: head
->next
),
194 virtual void next() { if (!end()) pos
= rev
? pos
->prev
: pos
->next
; }
195 virtual void *get() const { return pos
->data
; }
196 virtual bool end() const { return pos
== term
; }
198 // caution: if you're at end-2 and erase it, then do next, you're at end
199 virtual void erase();
200 virtual bool insert(void *data
);
202 // move item to a another list, no consistency with its iterators though
203 void moveToList(DLList
&);
213 inline void erase(Iterator
& pos
)
220 return Iterator(&head
, false);
223 Iterator
revIterator()
225 return Iterator(&head
, true);
245 Item() { memset(&u
, 0, sizeof(u
)); }
248 Stack() : size(0), limit(0), array(0) { }
249 ~Stack() { if (array
) FREE(array
); }
251 inline void push(int i
) { Item data
; data
.u
.i
= i
; push(data
); }
252 inline void push(unsigned int u
) { Item data
; data
.u
.u
= u
; push(data
); }
253 inline void push(void *p
) { Item data
; data
.u
.p
= p
; push(data
); }
254 inline void push(float f
) { Item data
; data
.u
.f
= f
; push(data
); }
256 inline void push(Item data
)
260 array
[size
++] = data
;
270 return array
[--size
];
273 inline unsigned int getSize() { return size
; }
275 inline Item
& peek() { assert(size
); return array
[size
- 1]; }
277 void clear(bool releaseStorage
= false)
279 if (releaseStorage
&& array
)
284 void moveTo(Stack
&); // move all items to target (not like push(pop()))
289 unsigned int sizeOld
, sizeNew
;
291 sizeOld
= limit
* sizeof(Item
);
292 limit
= MAX2(4, limit
+ limit
);
293 sizeNew
= limit
* sizeof(Item
);
295 array
= (Item
*)REALLOC(array
, sizeOld
, sizeNew
);
315 DynArray() : data(NULL
), size(0) { }
317 ~DynArray() { if (data
) FREE(data
); }
319 inline Item
& operator[](unsigned int i
)
326 inline const Item
operator[](unsigned int i
) const
331 void resize(unsigned int index
)
333 const unsigned int oldSize
= size
* sizeof(Item
);
337 while (size
<= index
)
340 data
= (Item
*)REALLOC(data
, oldSize
, size
* sizeof(Item
));
358 ArrayList() : size(0) { }
360 void insert(void *item
, int& id
)
362 id
= ids
.getSize() ? ids
.pop().u
.i
: size
++;
368 const unsigned int uid
= id
;
369 assert(uid
< size
&& data
[id
].p
);
375 inline int getSize() const { return size
; }
377 inline void *get(unsigned int id
) { assert(id
< size
); return data
[id
].p
; }
379 class Iterator
: public nv50_ir::Iterator
382 Iterator(const ArrayList
*array
) : pos(0), data(array
->data
)
384 size
= array
->getSize();
389 void nextValid() { while ((pos
< size
) && !data
[pos
].p
) ++pos
; }
391 void next() { if (pos
< size
) { ++pos
; nextValid(); } }
392 void *get() const { assert(pos
< size
); return data
[pos
].p
; }
393 bool end() const { return pos
>= size
; }
398 const DynArray
& data
;
400 friend class ArrayList
;
403 Iterator
iterator() const { return Iterator(this); }
421 Interval() : head(0), tail(0) { }
422 Interval(const Interval
&);
425 bool extend(int, int);
426 void insert(const Interval
&);
427 void unify(Interval
&); // clears source interval
430 inline int begin() const { return head
? head
->bgn
: -1; }
431 inline int end() const { checkTail(); return tail
? tail
->end
: -1; }
432 inline bool isEmpty() const { return !head
; }
433 bool overlaps(const Interval
&) const;
434 bool contains(int pos
) const;
436 inline int extent() const { return end() - begin(); }
441 inline void checkTail() const;
447 Range(int a
, int b
) : next(0), bgn(a
), end(b
) { }
453 void coalesce(Range
**ptail
)
457 while (next
&& end
>= next
->bgn
) {
458 assert(bgn
<= next
->bgn
);
460 end
= MAX2(end
, next
->end
);
476 BitSet() : marker(false), data(0), size(0) { }
477 BitSet(unsigned int nBits
, bool zero
) : marker(false), data(0), size(0)
479 allocate(nBits
, zero
);
487 // allocate will keep old data iff size is unchanged
488 bool allocate(unsigned int nBits
, bool zero
);
489 bool resize(unsigned int nBits
); // keep old data, zero additional bits
491 inline unsigned int getSize() const { return size
; }
493 void fill(uint32_t val
);
495 void setOr(BitSet
*, BitSet
*); // second BitSet may be NULL
497 inline void set(unsigned int i
)
500 data
[i
/ 32] |= 1 << (i
% 32);
502 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
503 inline void setRange(unsigned int i
, unsigned int n
)
505 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
506 data
[i
/ 32] |= ((1 << n
) - 1) << (i
% 32);
508 inline void setMask(unsigned int i
, uint32_t m
)
514 inline void clr(unsigned int i
)
517 data
[i
/ 32] &= ~(1 << (i
% 32));
519 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
520 inline void clrRange(unsigned int i
, unsigned int n
)
522 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
523 data
[i
/ 32] &= ~(((1 << n
) - 1) << (i
% 32));
526 inline bool test(unsigned int i
) const
529 return data
[i
/ 32] & (1 << (i
% 32));
531 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
532 inline bool testRange(unsigned int i
, unsigned int n
) const
534 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
535 return data
[i
/ 32] & (((1 << n
) - 1) << (i
% 32));
538 // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size).
539 int findFreeRange(unsigned int size
) const;
541 BitSet
& operator|=(const BitSet
&);
543 BitSet
& operator=(const BitSet
& set
)
545 assert(data
&& set
.data
);
546 assert(size
== set
.size
);
547 memcpy(data
, set
.data
, (set
.size
+ 7) / 8);
551 void andNot(const BitSet
&);
553 // bits = (bits | setMask) & ~clrMask
554 inline void periodicMask32(uint32_t setMask
, uint32_t clrMask
)
556 for (unsigned int i
= 0; i
< (size
+ 31) / 32; ++i
)
557 data
[i
] = (data
[i
] | setMask
) & ~clrMask
;
560 unsigned int popCount() const;
565 bool marker
; // for user
572 void Interval::checkTail() const
574 #if NV50_DEBUG & NV50_DEBUG_PROG_RA
585 inline bool enlargeAllocationsArray(const unsigned int id
, unsigned int nr
)
587 const unsigned int size
= sizeof(uint8_t *) * id
;
588 const unsigned int incr
= sizeof(uint8_t *) * nr
;
590 uint8_t **alloc
= (uint8_t **)REALLOC(allocArray
, size
, size
+ incr
);
597 inline bool enlargeCapacity()
599 const unsigned int id
= count
>> objStepLog2
;
601 uint8_t *const mem
= (uint8_t *)MALLOC(objSize
<< objStepLog2
);
606 if (!enlargeAllocationsArray(id
, 32)) {
611 allocArray
[id
] = mem
;
616 MemoryPool(unsigned int size
, unsigned int incr
) : objSize(size
),
626 unsigned int allocCount
= (count
+ (1 << objStepLog2
) - 1) >> objStepLog2
;
627 for (unsigned int i
= 0; i
< allocCount
&& allocArray
[i
]; ++i
)
636 const unsigned int mask
= (1 << objStepLog2
) - 1;
640 released
= *(void **)released
;
645 if (!enlargeCapacity())
648 ret
= allocArray
[count
>> objStepLog2
] + (count
& mask
) * objSize
;
653 void release(void *ptr
)
655 *(void **)ptr
= released
;
660 uint8_t **allocArray
; // array (list) of MALLOC allocations
662 void *released
; // list of released objects
664 unsigned int count
; // highest allocated object
666 const unsigned int objSize
;
667 const unsigned int objStepLog2
;
671 * Composite object cloning policy.
673 * Encapsulates how sub-objects are to be handled (if at all) when a
674 * composite object is being cloned.
683 ClonePolicy(C
*c
) : c(c
) {}
685 C
*context() { return c
; }
687 template<typename T
> T
*get(T
*obj
)
689 void *clone
= lookup(obj
);
691 clone
= obj
->clone(*this);
692 return reinterpret_cast<T
*>(clone
);
695 template<typename T
> void set(const T
*obj
, T
*clone
)
701 virtual void *lookup(void *obj
) = 0;
702 virtual void insert(const void *obj
, void *clone
) = 0;
706 * Shallow non-recursive cloning policy.
708 * Objects cloned with the "shallow" policy don't clone their
709 * children recursively, instead, the new copy shares its children
710 * with the original object.
713 class ShallowClonePolicy
: public ClonePolicy
<C
>
716 ShallowClonePolicy(C
*c
) : ClonePolicy
<C
>(c
) {}
719 virtual void *lookup(void *obj
)
724 virtual void insert(const void *obj
, void *clone
)
729 template<typename C
, typename T
>
730 inline T
*cloneShallow(C
*c
, T
*obj
)
732 ShallowClonePolicy
<C
> pol(c
);
733 return obj
->clone(pol
);
737 * Recursive cloning policy.
739 * Objects cloned with the "deep" policy clone their children
740 * recursively, keeping track of what has already been cloned to
741 * avoid making several new copies of the same object.
744 class DeepClonePolicy
: public ClonePolicy
<C
>
747 DeepClonePolicy(C
*c
) : ClonePolicy
<C
>(c
) {}
750 std::map
<const void *, void *> map
;
753 virtual void *lookup(void *obj
)
758 virtual void insert(const void *obj
, void *clone
)
764 template<typename S
, typename T
>
767 std::map
<S
, T
> forth
;
771 bimap() : l(back
), r(forth
) { }
772 bimap(const bimap
<S
, T
> &m
)
773 : forth(m
.forth
), back(m
.back
), l(back
), r(forth
) { }
775 void insert(const S
&s
, const T
&t
)
777 forth
.insert(std::make_pair(s
, t
));
778 back
.insert(std::make_pair(t
, s
));
781 typedef typename
std::map
<T
, S
>::const_iterator l_iterator
;
782 const std::map
<T
, S
> &l
;
783 typedef typename
std::map
<S
, T
>::const_iterator r_iterator
;
784 const std::map
<S
, T
> &r
;
787 } // namespace nv50_ir
789 #endif // __NV50_IR_UTIL_H__