Subversion Repositories Kolibri OS

/*

 * Copyright 2011 Christoph Bumiller

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and associated documentation files (the "Software"),

 * to deal in the Software without restriction, including without limitation

 * the rights to use, copy, modify, merge, publish, distribute, sublicense,

 * and/or sell copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR

 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,

 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

 * OTHER DEALINGS IN THE SOFTWARE.

 */

#ifndef __NV50_IR_UTIL_H__

#define __NV50_IR_UTIL_H__

#include 

#include 

#include 

#include 

#include 

#ifndef NDEBUG

# include 

#endif

#include "util/u_inlines.h"

#include "util/u_memory.h"

#define ERROR(args...) debug_printf("ERROR: " args)

#define WARN(args...) debug_printf("WARNING: " args)

#define INFO(args...) debug_printf(args)

#define INFO_DBG(m, f, args...)          \

   do {                                  \

      if (m & NV50_IR_DEBUG_##f)         \

         debug_printf(args);             \

   } while(0)

#define FATAL(args...)          \

   do {                         \

      fprintf(stderr, args);    \

      abort();                  \

   } while(0)

#define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...)               \

   new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)

#define new_Instruction(f, args...)                      \

   NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)

#define new_CmpInstruction(f, args...)                   \

   NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)

#define new_TexInstruction(f, args...)                   \

   NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)

#define new_FlowInstruction(f, args...)                  \

   NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)

#define new_LValue(f, args...)                  \

   NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)

#define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...)   \

   new ((p)->mem_##obj.allocate()) obj(p, args)

#define new_Symbol(p, args...)                           \

   NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)

#define new_ImmediateValue(p, args...)                   \

   NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)

#define delete_Instruction(p, insn) (p)->releaseInstruction(insn)

#define delete_Value(p, val) (p)->releaseValue(val)

namespace nv50_ir {

class Iterator

{

public:

   virtual ~Iterator() { };

   virtual void next() = 0;

   virtual void *get() const = 0;

   virtual bool end() const = 0; // if true, get will return 0

   virtual void reset() { assert(0); } // only for graph iterators

};

typedef std::auto_ptr IteratorRef;

class ManipIterator : public Iterator

{

public:

   virtual bool insert(void *) = 0; // insert after current position

   virtual void erase() = 0;

};

// WARNING: do not use a->prev/next for __item or __list

#define DLLIST_DEL(__item)                      \

   do {                                         \

      (__item)->prev->next = (__item)->next;    \

      (__item)->next->prev = (__item)->prev;    \

      (__item)->next = (__item);                \

      (__item)->prev = (__item);                \

   } while(0)

#define DLLIST_ADDTAIL(__list, __item)          \

   do {                                         \

      (__item)->next = (__list);                \

      (__item)->prev = (__list)->prev;          \

      (__list)->prev->next = (__item);          \

      (__list)->prev = (__item);                \

   } while(0)

#define DLLIST_ADDHEAD(__list, __item)          \

   do {                                         \

      (__item)->prev = (__list);                \

      (__item)->next = (__list)->next;          \

      (__list)->next->prev = (__item);          \

      (__list)->next = (__item);                \

   } while(0)

#define DLLIST_MERGE(__listA, __listB, ty)      \

   do {                                         \

      ty prevB = (__listB)->prev;               \

      (__listA)->prev->next = (__listB);        \

      (__listB)->prev->next = (__listA);        \

      (__listB)->prev = (__listA)->prev;        \

      (__listA)->prev = prevB;                  \

   } while(0)

#define DLLIST_EMPTY(__list) ((__list)->next == (__list))

#define DLLIST_FOR_EACH(list, it) \

   for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())

class DLList

{

public:

   class Item

   {

   public:

      Item(void *priv) : next(this), prev(this), data(priv) { }

   public:

      Item *next;

      Item *prev;

      void *data;

   };

   DLList() : head(0) { }

   ~DLList() { clear(); }

   inline void insertHead(void *data)

   {

      Item *item = new Item(data);

      assert(data);

      item->prev = &head;

      item->next = head.next;

      head.next->prev = item;

      head.next = item;

   }

   inline void insertTail(void *data)

   {

      Item *item = new Item(data);

      assert(data);

      DLLIST_ADDTAIL(&head, item);

   }

   inline void insert(void *data) { insertTail(data); }

   void clear();

   class Iterator : public ManipIterator

   {

   public:

      Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next),

                                     term(head) { }

      virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; }

      virtual void *get() const { return pos->data; }

      virtual bool end() const { return pos == term; }

      // caution: if you're at end-2 and erase it, then do next, you're at end

      virtual void erase();

      virtual bool insert(void *data);

      // move item to a another list, no consistency with its iterators though

      void moveToList(DLList&);

   private:

      const bool rev;

      Item *pos;

      Item *term;

      friend class DLList;

   };

   inline void erase(Iterator& pos)

   {

      pos.erase();

   }

   Iterator iterator()

   {

      return Iterator(&head, false);

   }

   Iterator revIterator()

   {

      return Iterator(&head, true);

   }

private:

   Item head;

};

class Stack

{

public:

   class Item {

   public:

      union {

         void *p;

         int i;

         unsigned int u;

         float f;

         double d;

      } u;

      Item() { memset(&u, 0, sizeof(u)); }

   };

   Stack() : size(0), limit(0), array(0) { }

   ~Stack() { if (array) FREE(array); }

   inline void push(int i)          { Item data; data.u.i = i; push(data); }

   inline void push(unsigned int u) { Item data; data.u.u = u; push(data); }

   inline void push(void *p)        { Item data; data.u.p = p; push(data); }

   inline void push(float f)        { Item data; data.u.f = f; push(data); }

   inline void push(Item data)

   {

      if (size == limit)

         resize();

      array[size++] = data;

   }

   inline Item pop()

   {

      if (!size) {

         Item data;

         assert(0);

         return data;

      }

      return array[--size];

   }

   inline unsigned int getSize() { return size; }

   inline Item& peek() { assert(size); return array[size - 1]; }

   void clear(bool releaseStorage = false)

   {

      if (releaseStorage && array)

         FREE(array);

      size = limit = 0;

   }

   void moveTo(Stack&); // move all items to target (not like push(pop()))

private:

   void resize()

   {

         unsigned int sizeOld, sizeNew;

         sizeOld = limit * sizeof(Item);

         limit = MAX2(4, limit + limit);

         sizeNew = limit * sizeof(Item);

         array = (Item *)REALLOC(array, sizeOld, sizeNew);

   }

   unsigned int size;

   unsigned int limit;

   Item *array;

};

class DynArray

{

public:

   class Item

   {

   public:

      union {

         uint32_t u32;

         void *p;

      };

   };

   DynArray() : data(NULL), size(0) { }

   ~DynArray() { if (data) FREE(data); }

   inline Item& operator[](unsigned int i)

   {

      if (i >= size)

         resize(i);

      return data[i];

   }

   inline const Item operator[](unsigned int i) const

   {

      return data[i];

   }

   void resize(unsigned int index)

   {

      const unsigned int oldSize = size * sizeof(Item);

      if (!size)

         size = 8;

      while (size <= index)

         size <<= 1;

      data = (Item *)REALLOC(data, oldSize, size * sizeof(Item));

   }

   void clear()

   {

      FREE(data);

      data = NULL;

      size = 0;

   }

private:

   Item *data;

   unsigned int size;

};

class ArrayList

{

public:

   ArrayList() : size(0) { }

   void insert(void *item, int& id)

   {

      id = ids.getSize() ? ids.pop().u.i : size++;

      data[id].p = item;

   }

   void remove(int& id)

   {

      const unsigned int uid = id;

      assert(uid < size && data[id].p);

      ids.push(uid);

      data[uid].p = NULL;

      id = -1;

   }

   inline int getSize() const { return size; }

   inline void *get(unsigned int id) { assert(id < size); return data[id].p; }

   class Iterator : public nv50_ir::Iterator

   {

   public:

      Iterator(const ArrayList *array) : pos(0), data(array->data)

      {

         size = array->getSize();

         if (size)

            nextValid();

      }

      void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }

      void next() { if (pos < size) { ++pos; nextValid(); } }

      void *get() const { assert(pos < size); return data[pos].p; }

      bool end() const { return pos >= size; }

   private:

      unsigned int pos;

      unsigned int size;

      const DynArray& data;

      friend class ArrayList;

   };

   Iterator iterator() const { return Iterator(this); }

   void clear()

   {

      data.clear();

      ids.clear(true);

      size = 0;

   }

private:

   DynArray data;

   Stack ids;

   unsigned int size;

};

class Interval

{

public:

   Interval() : head(0), tail(0) { }

   Interval(const Interval&);

   ~Interval();

   bool extend(int, int);

   void insert(const Interval&);

   void unify(Interval&); // clears source interval

   void clear();

   inline int begin() const { return head ? head->bgn : -1; }

   inline int end() const { checkTail(); return tail ? tail->end : -1; }

   inline bool isEmpty() const { return !head; }

   bool overlaps(const Interval&) const;

   bool contains(int pos) const;

   inline int extent() const { return end() - begin(); }

   int length() const;

   void print() const;

   inline void checkTail() const;

private:

   class Range

   {

   public:

      Range(int a, int b) : next(0), bgn(a), end(b) { }

      Range *next;

      int bgn;

      int end;

      void coalesce(Range **ptail)

      {

         Range *rnn;

         while (next && end >= next->bgn) {

            assert(bgn <= next->bgn);

            rnn = next->next;

            end = MAX2(end, next->end);

            delete next;

            next = rnn;

         }

         if (!next)

            *ptail = this;

      }

   };

   Range *head;

   Range *tail;

};

class BitSet

{

public:

   BitSet() : marker(false), data(0), size(0) { }

   BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)

   {

      allocate(nBits, zero);

   }

   ~BitSet()

   {

      if (data)

         FREE(data);

   }

   bool allocate(unsigned int nBits, bool zero);

   bool resize(unsigned int nBits); // keep old data, zero additional bits

   inline unsigned int getSize() const { return size; }

   void fill(uint32_t val);

   void setOr(BitSet *, BitSet *); // second BitSet may be NULL

   inline void set(unsigned int i)

   {

      assert(i < size);

      data[i / 32] |= 1 << (i % 32);

   }

   // NOTE: range may not cross 32 bit boundary (implies n <= 32)

   inline void setRange(unsigned int i, unsigned int n)

   {

      assert((i + n) <= size && (((i % 32) + n) <= 32));

      data[i / 32] |= ((1 << n) - 1) << (i % 32);

   }

   inline void setMask(unsigned int i, uint32_t m)

   {

      assert(i < size);

      data[i / 32] |= m;

   }

   inline void clr(unsigned int i)

   {

      assert(i < size);

      data[i / 32] &= ~(1 << (i % 32));

   }

   // NOTE: range may not cross 32 bit boundary (implies n <= 32)

   inline void clrRange(unsigned int i, unsigned int n)

   {

      assert((i + n) <= size && (((i % 32) + n) <= 32));

      data[i / 32] &= ~(((1 << n) - 1) << (i % 32));

   }

   inline bool test(unsigned int i) const

   {

      assert(i < size);

      return data[i / 32] & (1 << (i % 32));

   }

   // NOTE: range may not cross 32 bit boundary (implies n <= 32)

   inline bool testRange(unsigned int i, unsigned int n) const

   {

      assert((i + n) <= size && (((i % 32) + n) <= 32));

      return data[i / 32] & (((1 << n) - 1) << (i % 32));

   }

   // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size).

   int findFreeRange(unsigned int size) const;

   BitSet& operator|=(const BitSet&);

   BitSet& operator=(const BitSet& set)

   {

      assert(data && set.data);

      assert(size == set.size);

      memcpy(data, set.data, (set.size + 7) / 8);

      return *this;

   }

   void andNot(const BitSet&);

   // bits = (bits | setMask) & ~clrMask

   inline void periodicMask32(uint32_t setMask, uint32_t clrMask)

   {

      for (unsigned int i = 0; i < (size + 31) / 32; ++i)

         data[i] = (data[i] | setMask) & ~clrMask;

   }

   unsigned int popCount() const;

   void print() const;

public:

   bool marker; // for user

private:

   uint32_t *data;

   unsigned int size;

};

void Interval::checkTail() const

{

#if NV50_DEBUG & NV50_DEBUG_PROG_RA

   Range *r = head;

   while (r->next)

      r = r->next;

   assert(tail == r);

#endif

}

class MemoryPool

{

private:

   inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)

   {

      const unsigned int size = sizeof(uint8_t *) * id;

      const unsigned int incr = sizeof(uint8_t *) * nr;

      uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);

      if (!alloc)

         return false;

      allocArray = alloc;

      return true;

   }

   inline bool enlargeCapacity()

   {

      const unsigned int id = count >> objStepLog2;

      uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);

      if (!mem)

         return false;

      if (!(id % 32)) {

         if (!enlargeAllocationsArray(id, 32)) {

            FREE(mem);

            return false;

         }

      }

      allocArray[id] = mem;

      return true;

   }

public:

   MemoryPool(unsigned int size, unsigned int incr) : objSize(size),

                                                      objStepLog2(incr)

   {

      allocArray = NULL;

      released = NULL;

      count = 0;

   }

   ~MemoryPool()

   {

      unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;

      for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)

         FREE(allocArray[i]);

      if (allocArray)

         FREE(allocArray);

   }

   void *allocate()

   {

      void *ret;

      const unsigned int mask = (1 << objStepLog2) - 1;

      if (released) {

         ret = released;

         released = *(void **)released;

         return ret;

      }

      if (!(count & mask))

         if (!enlargeCapacity())

            return NULL;

      ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;

      ++count;

      return ret;

   }

   void release(void *ptr)

   {

      *(void **)ptr = released;

      released = ptr;

   }

private:

   uint8_t **allocArray; // array (list) of MALLOC allocations

   void *released; // list of released objects

   unsigned int count; // highest allocated object

   const unsigned int objSize;

   const unsigned int objStepLog2;

};

/**

 *  Composite object cloning policy.

 *

 *  Encapsulates how sub-objects are to be handled (if at all) when a

 *  composite object is being cloned.

 */

template

class ClonePolicy

{

protected:

   C *c;

public:

   ClonePolicy(C *c) : c(c) {}

   C *context() { return c; }

   template T *get(T *obj)

   {

      void *clone = lookup(obj);

      if (!clone)

         clone = obj->clone(*this);

      return reinterpret_cast(clone);

   }

   template void set(const T *obj, T *clone)

   {

      insert(obj, clone);

   }

protected:

   virtual void *lookup(void *obj) = 0;

   virtual void insert(const void *obj, void *clone) = 0;

};

/**

 *  Shallow non-recursive cloning policy.

 *

 *  Objects cloned with the "shallow" policy don't clone their

 *  children recursively, instead, the new copy shares its children

 *  with the original object.

 */

template

class ShallowClonePolicy : public ClonePolicy

{

public:

   ShallowClonePolicy(C *c) : ClonePolicy(c) {}

protected:

   virtual void *lookup(void *obj)

   {

      return obj;

   }

   virtual void insert(const void *obj, void *clone)

   {

   }

};

template

inline T *cloneShallow(C *c, T *obj)

{

   ShallowClonePolicy pol(c);

   return obj->clone(pol);

}

/**

 *  Recursive cloning policy.

 *

 *  Objects cloned with the "deep" policy clone their children

 *  recursively, keeping track of what has already been cloned to

 *  avoid making several new copies of the same object.

 */

template

class DeepClonePolicy : public ClonePolicy

{

public:

   DeepClonePolicy(C *c) : ClonePolicy(c) {}

private:

   std::map map;

protected:

   virtual void *lookup(void *obj)

   {

      return map[obj];

   }

   virtual void insert(const void *obj, void *clone)

   {

      map[obj] = clone;

   }

};

template

struct bimap

{

   std::map forth;

   std::map back;

public:

   bimap() : l(back), r(forth) { }

   bimap(const bimap &m)

      : forth(m.forth), back(m.back), l(back), r(forth) { }

   void insert(const S &s, const T &t)

   {

      forth.insert(std::make_pair(s, t));

      back.insert(std::make_pair(t, s));

   }

   typedef typename std::map::const_iterator l_iterator;

   const std::map &l;

   typedef typename std::map::const_iterator r_iterator;

   const std::map &r;

};

} // namespace nv50_ir

#endif // __NV50_IR_UTIL_H__