nv50_ir_util.h revision 4a44f94caf8887f6dfc66c4193e95c6430c9de57
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
340   void clear()
341   {
342      FREE(data);
343      data = NULL;
344      size = 0;
345   }
346
347private:
348   Item *data;
349   unsigned int size;
350};
351
352class ArrayList
353{
354public:
355   ArrayList() : size(0) { }
356
357   void insert(void *item, int& id)
358   {
359      id = ids.getSize() ? ids.pop().u.i : size++;
360      data[id].p = item;
361   }
362
363   void remove(int& id)
364   {
365      const unsigned int uid = id;
366      assert(uid < size && data[id].p);
367      ids.push(uid);
368      data[uid].p = NULL;
369      id = -1;
370   }
371
372   inline int getSize() const { return size; }
373
374   inline void *get(unsigned int id) { assert(id < size); return data[id].p; }
375
376   class Iterator : public nv50_ir::Iterator
377   {
378   public:
379      Iterator(const ArrayList *array) : pos(0), data(array->data)
380      {
381         size = array->getSize();
382         if (size)
383            nextValid();
384      }
385
386      void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }
387
388      void next() { if (pos < size) { ++pos; nextValid(); } }
389      void *get() const { assert(pos < size); return data[pos].p; }
390      bool end() const { return pos >= size; }
391
392   private:
393      unsigned int pos;
394      unsigned int size;
395      const DynArray& data;
396
397      friend class ArrayList;
398   };
399
400   Iterator iterator() const { return Iterator(this); }
401
402   void clear()
403   {
404      data.clear();
405      ids.clear(true);
406      size = 0;
407   }
408
409private:
410   DynArray data;
411   Stack ids;
412   unsigned int size;
413};
414
415class Interval
416{
417public:
418   Interval() : head(0), tail(0) { }
419   ~Interval();
420
421   bool extend(int, int);
422   void unify(Interval&); // clears source interval
423   void clear();
424
425   inline int begin() { return head ? head->bgn : -1; }
426   inline int end() { checkTail(); return tail ? tail->end : -1; }
427   inline bool isEmpty() const { return !head; }
428   bool overlaps(const Interval&) const;
429   bool contains(int pos);
430
431   void print() const;
432
433   inline void checkTail() const;
434
435private:
436   class Range
437   {
438   public:
439      Range(int a, int b) : next(0), bgn(a), end(b) { }
440
441      Range *next;
442      int bgn;
443      int end;
444
445      void coalesce(Range **ptail)
446      {
447         Range *rnn;
448
449         while (next && end >= next->bgn) {
450            assert(bgn <= next->bgn);
451            rnn = next->next;
452            end = MAX2(end, next->end);
453            delete next;
454            next = rnn;
455         }
456         if (!next)
457            *ptail = this;
458      }
459   };
460
461   Range *head;
462   Range *tail;
463};
464
465class BitSet
466{
467public:
468   BitSet() : marker(false), data(0), size(0) { }
469   BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)
470   {
471      allocate(nBits, zero);
472   }
473   ~BitSet()
474   {
475      if (data)
476         FREE(data);
477   }
478
479   bool allocate(unsigned int nBits, bool zero);
480
481   inline unsigned int getSize() const { return size; }
482
483   void fill(uint32_t val);
484
485   void setOr(BitSet *, BitSet *); // second BitSet may be NULL
486
487   inline void set(unsigned int i)
488   {
489      assert(i < size);
490      data[i / 32] |= 1 << (i % 32);
491   }
492
493   inline void clr(unsigned int i)
494   {
495      assert(i < size);
496      data[i / 32] &= ~(1 << (i % 32));
497   }
498
499   inline bool test(unsigned int i) const
500   {
501      assert(i < size);
502      return data[i / 32] & (1 << (i % 32));
503   }
504
505   BitSet& operator|=(const BitSet&);
506
507   BitSet& operator=(const BitSet& set)
508   {
509      assert(data && set.data);
510      assert(size == set.size);
511      memcpy(data, set.data, (set.size + 7) / 8);
512      return *this;
513   }
514
515   void andNot(const BitSet&);
516
517   unsigned int popCount() const;
518
519   void print() const;
520
521public:
522   bool marker; // for user
523
524private:
525   uint32_t *data;
526   unsigned int size;
527};
528
529void Interval::checkTail() const
530{
531#if NV50_DEBUG & NV50_DEBUG_PROG_RA
532   Range *r = head;
533   while (r->next)
534      r = r->next;
535   assert(tail == r);
536#endif
537}
538
539class MemoryPool
540{
541private:
542   inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)
543   {
544      const unsigned int size = sizeof(uint8_t *) * id;
545      const unsigned int incr = sizeof(uint8_t *) * nr;
546
547      uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);
548      if (!alloc)
549         return false;
550      allocArray = alloc;
551      return true;
552   }
553
554   inline bool enlargeCapacity()
555   {
556      const unsigned int id = count >> objStepLog2;
557
558      uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);
559      if (!mem)
560         return false;
561
562      if (!(id % 32)) {
563         if (!enlargeAllocationsArray(id, 32)) {
564            FREE(mem);
565            return false;
566         }
567      }
568      allocArray[id] = mem;
569      return true;
570   }
571
572public:
573   MemoryPool(unsigned int size, unsigned int incr) : objSize(size),
574                                                      objStepLog2(incr)
575   {
576      allocArray = NULL;
577      released = NULL;
578      count = 0;
579   }
580
581   ~MemoryPool()
582   {
583      unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;
584      for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)
585         FREE(allocArray[i]);
586      if (allocArray)
587         FREE(allocArray);
588   }
589
590   void *allocate()
591   {
592      void *ret;
593      const unsigned int mask = (1 << objStepLog2) - 1;
594
595      if (released) {
596         ret = released;
597         released = *(void **)released;
598         return ret;
599      }
600
601      if (!(count & mask))
602         if (!enlargeCapacity())
603            return NULL;
604
605      ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;
606      ++count;
607      return ret;
608   }
609
610   void release(void *ptr)
611   {
612      *(void **)ptr = released;
613      released = ptr;
614   }
615
616private:
617   uint8_t **allocArray; // array (list) of MALLOC allocations
618
619   void *released; // list of released objects
620
621   unsigned int count; // highest allocated object
622
623   const unsigned int objSize;
624   const unsigned int objStepLog2;
625};
626
627/**
628 *  Composite object cloning policy.
629 *
630 *  Encapsulates how sub-objects are to be handled (if at all) when a
631 *  composite object is being cloned.
632 */
633template<typename C>
634class ClonePolicy
635{
636protected:
637   C *c;
638
639public:
640   ClonePolicy(C *c) : c(c) {}
641
642   C *context() { return c; }
643
644   template<typename T> T *get(T *obj)
645   {
646      void *clone = lookup(obj);
647      if (!clone)
648         clone = obj->clone(*this);
649      return reinterpret_cast<T *>(clone);
650   }
651
652   template<typename T> void set(const T *obj, T *clone)
653   {
654      insert(obj, clone);
655   }
656
657protected:
658   virtual void *lookup(void *obj) = 0;
659   virtual void insert(const void *obj, void *clone) = 0;
660};
661
662/**
663 *  Shallow non-recursive cloning policy.
664 *
665 *  Objects cloned with the "shallow" policy don't clone their
666 *  children recursively, instead, the new copy shares its children
667 *  with the original object.
668 */
669template<typename C>
670class ShallowClonePolicy : public ClonePolicy<C>
671{
672public:
673   ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {}
674
675protected:
676   virtual void *lookup(void *obj)
677   {
678      return obj;
679   }
680
681   virtual void insert(const void *obj, void *clone)
682   {
683   }
684};
685
686template<typename C, typename T>
687inline T *cloneShallow(C *c, T *obj)
688{
689   ShallowClonePolicy<C> pol(c);
690   return obj->clone(pol);
691}
692
693/**
694 *  Recursive cloning policy.
695 *
696 *  Objects cloned with the "deep" policy clone their children
697 *  recursively, keeping track of what has already been cloned to
698 *  avoid making several new copies of the same object.
699 */
700template<typename C>
701class DeepClonePolicy : public ClonePolicy<C>
702{
703public:
704   DeepClonePolicy(C *c) : ClonePolicy<C>(c) {}
705
706private:
707   std::map<const void *, void *> map;
708
709protected:
710   virtual void *lookup(void *obj)
711   {
712      return map[obj];
713   }
714
715   virtual void insert(const void *obj, void *clone)
716   {
717      map[obj] = clone;
718   }
719};
720
721template<typename S, typename T>
722struct bimap
723{
724   std::map<S, T> forth;
725   std::map<T, S> back;
726
727public:
728   bimap() : l(back), r(forth) { }
729   bimap(const bimap<S, T> &m)
730      : forth(m.forth), back(m.back), l(back), r(forth) { }
731
732   void insert(const S &s, const T &t)
733   {
734      forth.insert(std::make_pair(s, t));
735      back.insert(std::make_pair(t, s));
736   }
737
738   typedef typename std::map<T, S>::const_iterator l_iterator;
739   const std::map<T, S> &l;
740   typedef typename std::map<S, T>::const_iterator r_iterator;
741   const std::map<S, T> &r;
742};
743
744} // namespace nv50_ir
745
746#endif // __NV50_IR_UTIL_H__
747