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