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 bool allocate(unsigned int nBits
, bool zero
);
488 bool resize(unsigned int nBits
); // keep old data, zero additional bits
490 inline unsigned int getSize() const { return size
; }
492 void fill(uint32_t val
);
494 void setOr(BitSet
*, BitSet
*); // second BitSet may be NULL
496 inline void set(unsigned int i
)
499 data
[i
/ 32] |= 1 << (i
% 32);
501 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
502 inline void setRange(unsigned int i
, unsigned int n
)
504 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
505 data
[i
/ 32] |= ((1 << n
) - 1) << (i
% 32);
507 inline void setMask(unsigned int i
, uint32_t m
)
513 inline void clr(unsigned int i
)
516 data
[i
/ 32] &= ~(1 << (i
% 32));
518 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
519 inline void clrRange(unsigned int i
, unsigned int n
)
521 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
522 data
[i
/ 32] &= ~(((1 << n
) - 1) << (i
% 32));
525 inline bool test(unsigned int i
) const
528 return data
[i
/ 32] & (1 << (i
% 32));
530 // NOTE: range may not cross 32 bit boundary (implies n <= 32)
531 inline bool testRange(unsigned int i
, unsigned int n
) const
533 assert((i
+ n
) <= size
&& (((i
% 32) + n
) <= 32));
534 return data
[i
/ 32] & (((1 << n
) - 1) << (i
% 32));
537 // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size).
538 int findFreeRange(unsigned int size
) const;
540 BitSet
& operator|=(const BitSet
&);
542 BitSet
& operator=(const BitSet
& set
)
544 assert(data
&& set
.data
);
545 assert(size
== set
.size
);
546 memcpy(data
, set
.data
, (set
.size
+ 7) / 8);
550 void andNot(const BitSet
&);
552 // bits = (bits | setMask) & ~clrMask
553 inline void periodicMask32(uint32_t setMask
, uint32_t clrMask
)
555 for (unsigned int i
= 0; i
< (size
+ 31) / 32; ++i
)
556 data
[i
] = (data
[i
] | setMask
) & ~clrMask
;
559 unsigned int popCount() const;
564 bool marker
; // for user
571 void Interval::checkTail() const
573 #if NV50_DEBUG & NV50_DEBUG_PROG_RA
584 inline bool enlargeAllocationsArray(const unsigned int id
, unsigned int nr
)
586 const unsigned int size
= sizeof(uint8_t *) * id
;
587 const unsigned int incr
= sizeof(uint8_t *) * nr
;
589 uint8_t **alloc
= (uint8_t **)REALLOC(allocArray
, size
, size
+ incr
);
596 inline bool enlargeCapacity()
598 const unsigned int id
= count
>> objStepLog2
;
600 uint8_t *const mem
= (uint8_t *)MALLOC(objSize
<< objStepLog2
);
605 if (!enlargeAllocationsArray(id
, 32)) {
610 allocArray
[id
] = mem
;
615 MemoryPool(unsigned int size
, unsigned int incr
) : objSize(size
),
625 unsigned int allocCount
= (count
+ (1 << objStepLog2
) - 1) >> objStepLog2
;
626 for (unsigned int i
= 0; i
< allocCount
&& allocArray
[i
]; ++i
)
635 const unsigned int mask
= (1 << objStepLog2
) - 1;
639 released
= *(void **)released
;
644 if (!enlargeCapacity())
647 ret
= allocArray
[count
>> objStepLog2
] + (count
& mask
) * objSize
;
652 void release(void *ptr
)
654 *(void **)ptr
= released
;
659 uint8_t **allocArray
; // array (list) of MALLOC allocations
661 void *released
; // list of released objects
663 unsigned int count
; // highest allocated object
665 const unsigned int objSize
;
666 const unsigned int objStepLog2
;
670 * Composite object cloning policy.
672 * Encapsulates how sub-objects are to be handled (if at all) when a
673 * composite object is being cloned.
682 ClonePolicy(C
*c
) : c(c
) {}
684 C
*context() { return c
; }
686 template<typename T
> T
*get(T
*obj
)
688 void *clone
= lookup(obj
);
690 clone
= obj
->clone(*this);
691 return reinterpret_cast<T
*>(clone
);
694 template<typename T
> void set(const T
*obj
, T
*clone
)
700 virtual void *lookup(void *obj
) = 0;
701 virtual void insert(const void *obj
, void *clone
) = 0;
705 * Shallow non-recursive cloning policy.
707 * Objects cloned with the "shallow" policy don't clone their
708 * children recursively, instead, the new copy shares its children
709 * with the original object.
712 class ShallowClonePolicy
: public ClonePolicy
<C
>
715 ShallowClonePolicy(C
*c
) : ClonePolicy
<C
>(c
) {}
718 virtual void *lookup(void *obj
)
723 virtual void insert(const void *obj
, void *clone
)
728 template<typename C
, typename T
>
729 inline T
*cloneShallow(C
*c
, T
*obj
)
731 ShallowClonePolicy
<C
> pol(c
);
732 return obj
->clone(pol
);
736 * Recursive cloning policy.
738 * Objects cloned with the "deep" policy clone their children
739 * recursively, keeping track of what has already been cloned to
740 * avoid making several new copies of the same object.
743 class DeepClonePolicy
: public ClonePolicy
<C
>
746 DeepClonePolicy(C
*c
) : ClonePolicy
<C
>(c
) {}
749 std::map
<const void *, void *> map
;
752 virtual void *lookup(void *obj
)
757 virtual void insert(const void *obj
, void *clone
)
763 template<typename S
, typename T
>
766 std::map
<S
, T
> forth
;
770 bimap() : l(back
), r(forth
) { }
771 bimap(const bimap
<S
, T
> &m
)
772 : forth(m
.forth
), back(m
.back
), l(back
), r(forth
) { }
774 void insert(const S
&s
, const T
&t
)
776 forth
.insert(std::make_pair(s
, t
));
777 back
.insert(std::make_pair(t
, s
));
780 typedef typename
std::map
<T
, S
>::const_iterator l_iterator
;
781 const std::map
<T
, S
> &l
;
782 typedef typename
std::map
<S
, T
>::const_iterator r_iterator
;
783 const std::map
<S
, T
> &r
;
786 } // namespace nv50_ir
788 #endif // __NV50_IR_UTIL_H__