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