xref: /aosp_15_r20/external/mesa3d/src/nouveau/codegen/nv50_ir_util.h (revision 6104692788411f58d303aa86923a9ff6ecaded22)
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