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