nv50_ir_util.h revision d2d19ea51fa3575a8d014a69a9b835c335728817 
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
30#include "util/u_inlines.h"
31#include "util/u_memory.h"
32
33#define ERROR(args...) debug_printf("ERROR: " args)
34#define WARN(args...) debug_printf("WARNING: " args)
35#define INFO(args...) debug_printf(args)
36
37#define INFO_DBG(m, f, args...)          \
38   do {                                  \
39      if (m & NV50_IR_DEBUG_##f)         \
40         debug_printf(args);             \
41   } while(0)
42
43#define FATAL(args...)          \
44   do {                         \
45      fprintf(stderr, args);    \
46      abort();                  \
47   } while(0)
48
49
50#define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...)               \
51   new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
52
53#define new_Instruction(f, args...)                      \
54   NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)
55#define new_CmpInstruction(f, args...)                   \
56   NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)
57#define new_TexInstruction(f, args...)                   \
58   NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)
59#define new_FlowInstruction(f, args...)                  \
60   NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)
61
62#define new_LValue(f, args...)                  \
63   NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
64
65
66#define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...)   \
67   new ((p)->mem_##obj.allocate()) obj(p, args)
68
69#define new_Symbol(p, args...)                           \
70   NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)
71#define new_ImmediateValue(p, args...)                   \
72   NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)
73
74
75#define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
76#define delete_Value(p, val) (p)->releaseValue(val)
77
78
79namespace nv50_ir {
80
81class Iterator
82{
83public:
84   virtual void next() = 0;
85   virtual void *get() const = 0;
86   virtual bool end() const = 0; // if true, get will return 0
87};
88
89class ManipIterator : public Iterator
90{
91public:
92   virtual bool insert(void *) = 0; // insert after current position
93   virtual void erase() = 0;
94};
95
96// WARNING: do not use a->prev/next for __item or __list
97
98#define DLLIST_DEL(__item)                      \
99   do {                                         \
100      (__item)->prev->next = (__item)->next;    \
101      (__item)->next->prev = (__item)->prev;    \
102      (__item)->next = (__item);                \
103      (__item)->prev = (__item);                \
104   } while(0)
105
106#define DLLIST_ADDTAIL(__list, __item)          \
107   do {                                         \
108      (__item)->next = (__list);                \
109      (__item)->prev = (__list)->prev;          \
110      (__list)->prev->next = (__item);          \
111      (__list)->prev = (__item);                \
112   } while(0)
113
114#define DLLIST_ADDHEAD(__list, __item)          \
115   do {                                         \
116      (__item)->prev = (__list);                \
117      (__item)->next = (__list)->next;          \
118      (__list)->next->prev = (__item);          \
119      (__list)->next = (__item);                \
120   } while(0)
121
122#define DLLIST_MERGE(__listA, __listB, ty)      \
123   do {                                         \
124      ty prevB = (__listB)->prev;               \
125      (__listA)->prev->next = (__listB);        \
126      (__listB)->prev->next = (__listA);        \
127      (__listB)->prev = (__listA)->prev;        \
128      (__listA)->prev = prevB;                  \
129   } while(0)
130
131#define DLLIST_FOR_EACH(list, it) \
132   for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())
133
134class DLList
135{
136public:
137   class Item
138   {
139   public:
140      Item(void *priv) : next(this), prev(this), data(priv) { }
141
142   public:
143      Item *next;
144      Item *prev;
145      void *data;
146   };
147
148   DLList() : head(0) { }
149   ~DLList() { clear(); }
150
151   inline void insertHead(void *data)
152   {
153      Item *item = new Item(data);
154
155      assert(data);
156
157      item->prev = &head;
158      item->next = head.next;
159      head.next->prev = item;
160      head.next = item;
161   }
162
163   inline void insertTail(void *data)
164   {
165      Item *item = new Item(data);
166
167      assert(data);
168
169      DLLIST_ADDTAIL(&head, item);
170   }
171
172   inline void insert(void *data) { insertTail(data); }
173
174   void clear();
175
176   class Iterator : public ManipIterator
177   {
178   public:
179      Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next),
180                                     term(head) { }
181
182      virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; }
183      virtual void *get() const { return pos->data; }
184      virtual bool end() const { return pos == term; }
185
186      // caution: if you're at end-2 and erase it, then do next, you're at end
187      virtual void erase();
188      virtual bool insert(void *data);
189
190      // move item to a another list, no consistency with its iterators though
191      void moveToList(DLList&);
192
193   private:
194      const bool rev;
195      Item *pos;
196      Item *term;
197
198      friend class DLList;
199   };
200
201   inline void erase(Iterator& pos)
202   {
203      pos.erase();
204   }
205
206   Iterator iterator()
207   {
208      return Iterator(&head, false);
209   }
210
211   Iterator revIterator()
212   {
213      return Iterator(&head, true);
214   }
215
216private:
217   Item head;
218};
219
220class Stack
221{
222public:
223   class Item {
224   public:
225      union {
226         void *p;
227         int i;
228         unsigned int u;
229         float f;
230         double d;
231      } u;
232
233      Item() { memset(&u, 0, sizeof(u)); }
234   };
235
236   Stack() : size(0), limit(0), array(0) { }
237   ~Stack() { if (array) FREE(array); }
238
239   inline void push(int i)          { Item data; data.u.i = i; push(data); }
240   inline void push(unsigned int u) { Item data; data.u.u = u; push(data); }
241   inline void push(void *p)        { Item data; data.u.p = p; push(data); }
242   inline void push(float f)        { Item data; data.u.f = f; push(data); }
243
244   inline void push(Item data)
245   {
246      if (size == limit)
247         resize();
248      array[size++] = data;
249   }
250
251   inline Item pop()
252   {
253      if (!size) {
254         Item data;
255         assert(0);
256         return data;
257      }
258      return array[--size];
259   }
260
261   inline unsigned int getSize() { return size; }
262
263   inline Item& peek() { assert(size); return array[size - 1]; }
264
265   void clear(bool releaseStorage = false)
266   {
267      if (releaseStorage && array)
268         FREE(array);
269      size = limit = 0;
270   }
271
272   void moveTo(Stack&); // move all items to target (not like push(pop()))
273
274private:
275   void resize()
276   {
277         unsigned int sizeOld, sizeNew;
278
279         sizeOld = limit * sizeof(Item);
280         limit = MAX2(4, limit + limit);
281         sizeNew = limit * sizeof(Item);
282
283         array = (Item *)REALLOC(array, sizeOld, sizeNew);
284   }
285
286   unsigned int size;
287   unsigned int limit;
288   Item *array;
289};
290
291class DynArray
292{
293public:
294   class Item
295   {
296   public:
297      union {
298         uint32_t u32;
299         void *p;
300      };
301   };
302
303   DynArray() : data(NULL), size(0) { }
304
305   ~DynArray() { if (data) FREE(data); }
306
307   inline Item& operator[](unsigned int i)
308   {
309      if (i >= size)
310         resize(i);
311      return data[i];
312   }
313
314   inline const Item operator[](unsigned int i) const
315   {
316      return data[i];
317   }
318
319   void resize(unsigned int index)
320   {
321      const unsigned int oldSize = size * sizeof(Item);
322
323      if (!size)
324         size = 8;
325      while (size <= index)
326         size <<= 1;
327
328      data = (Item *)REALLOC(data, oldSize, size * sizeof(Item));
329   }
330
331private:
332   Item *data;
333   unsigned int size;
334};
335
336class ArrayList
337{
338public:
339   ArrayList() : size(0) { }
340
341   void insert(void *item, int& id)
342   {
343      id = ids.getSize() ? ids.pop().u.i : size++;
344      data[id].p = item;
345   }
346
347   void remove(int& id)
348   {
349      const unsigned int uid = id;
350      assert(uid < size && data[id].p);
351      ids.push(uid);
352      data[uid].p = NULL;
353      id = -1;
354   }
355
356   inline int getSize() const { return size; }
357
358   inline void *get(unsigned int id) { assert(id < size); return data[id].p; }
359
360   class Iterator : public nv50_ir::Iterator
361   {
362   public:
363      Iterator(const ArrayList *array) : pos(0), data(array->data)
364      {
365         size = array->getSize();
366         if (size)
367            nextValid();
368      }
369
370      void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }
371
372      void next() { if (pos < size) { ++pos; nextValid(); } }
373      void *get() const { assert(pos < size); return data[pos].p; }
374      bool end() const { return pos >= size; }
375
376   private:
377      unsigned int pos;
378      unsigned int size;
379      const DynArray& data;
380
381      friend class ArrayList;
382   };
383
384   Iterator iterator() const { return Iterator(this); }
385
386private:
387   DynArray data;
388   Stack ids;
389   unsigned int size;
390};
391
392class Interval
393{
394public:
395   Interval() : head(0), tail(0) { }
396   ~Interval();
397
398   bool extend(int, int);
399   void unify(Interval&); // clears source interval
400   void clear();
401
402   inline int begin() { return head ? head->bgn : -1; }
403   inline int end() { checkTail(); return tail ? tail->end : -1; }
404   inline bool isEmpty() const { return !head; }
405   bool overlaps(const Interval&) const;
406   bool contains(int pos);
407
408   void print() const;
409
410   inline void checkTail() const;
411
412private:
413   class Range
414   {
415   public:
416      Range(int a, int b) : next(0), bgn(a), end(b) { }
417
418      Range *next;
419      int bgn;
420      int end;
421
422      void coalesce(Range **ptail)
423      {
424         Range *rnn;
425
426         while (next && end >= next->bgn) {
427            assert(bgn <= next->bgn);
428            rnn = next->next;
429            end = MAX2(end, next->end);
430            delete next;
431            next = rnn;
432         }
433         if (!next)
434            *ptail = this;
435      }
436   };
437
438   Range *head;
439   Range *tail;
440};
441
442class BitSet
443{
444public:
445   BitSet() : marker(false), data(0), size(0) { }
446   BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)
447   {
448      allocate(nBits, zero);
449   }
450   ~BitSet()
451   {
452      if (data)
453         FREE(data);
454   }
455
456   bool allocate(unsigned int nBits, bool zero);
457
458   inline unsigned int getSize() const { return size; }
459
460   void fill(uint32_t val);
461
462   void setOr(BitSet *, BitSet *); // second BitSet may be NULL
463
464   inline void set(unsigned int i)
465   {
466      assert(i < size);
467      data[i / 32] |= 1 << (i % 32);
468   }
469
470   inline void clr(unsigned int i)
471   {
472      assert(i < size);
473      data[i / 32] &= ~(1 << (i % 32));
474   }
475
476   inline bool test(unsigned int i) const
477   {
478      assert(i < size);
479      return data[i / 32] & (1 << (i % 32));
480   }
481
482   BitSet& operator|=(const BitSet&);
483
484   BitSet& operator=(const BitSet& set)
485   {
486      assert(data && set.data);
487      assert(size == set.size);
488      memcpy(data, set.data, (set.size + 7) / 8);
489      return *this;
490   }
491
492   void andNot(const BitSet&);
493
494   unsigned int popCount() const;
495
496   void print() const;
497
498public:
499   bool marker; // for user
500
501private:
502   uint32_t *data;
503   unsigned int size;
504};
505
506void Interval::checkTail() const
507{
508#if NV50_DEBUG & NV50_DEBUG_PROG_RA
509   Range *r = head;
510   while (r->next)
511      r = r->next;
512   assert(tail == r);
513#endif
514}
515
516class MemoryPool
517{
518private:
519   inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)
520   {
521      const unsigned int size = sizeof(uint8_t *) * id;
522      const unsigned int incr = sizeof(uint8_t *) * nr;
523
524      uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);
525      if (!alloc)
526         return false;
527      allocArray = alloc;
528      return true;
529   }
530
531   inline bool enlargeCapacity()
532   {
533      const unsigned int id = count >> objStepLog2;
534
535      uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);
536      if (!mem)
537         return false;
538
539      if (!(id % 32)) {
540         if (!enlargeAllocationsArray(id, 32)) {
541            FREE(mem);
542            return false;
543         }
544      }
545      allocArray[id] = mem;
546      return true;
547   }
548
549public:
550   MemoryPool(unsigned int size, unsigned int incr) : objSize(size),
551                                                      objStepLog2(incr)
552   {
553      allocArray = NULL;
554      released = NULL;
555      count = 0;
556   }
557
558   ~MemoryPool()
559   {
560      unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;
561      for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)
562         FREE(allocArray[i]);
563      if (allocArray)
564         FREE(allocArray);
565   }
566
567   void *allocate()
568   {
569      void *ret;
570      const unsigned int mask = (1 << objStepLog2) - 1;
571
572      if (released) {
573         ret = released;
574         released = *(void **)released;
575         return ret;
576      }
577
578      if (!(count & mask))
579         if (!enlargeCapacity())
580            return NULL;
581
582      ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;
583      ++count;
584      return ret;
585   }
586
587   void release(void *ptr)
588   {
589      *(void **)ptr = released;
590      released = ptr;
591   }
592
593private:
594   uint8_t **allocArray; // array (list) of MALLOC allocations
595
596   void *released; // list of released objects
597
598   unsigned int count; // highest allocated object
599
600   const unsigned int objSize;
601   const unsigned int objStepLog2;
602};
603
604} // namespace nv50_ir
605
606#endif // __NV50_IR_UTIL_H__
607