1d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller/*
2d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Copyright 2011 Christoph Bumiller
3d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller *
4d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Permission is hereby granted, free of charge, to any person obtaining a
5d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * copy of this software and associated documentation files (the "Software"),
6d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * to deal in the Software without restriction, including without limitation
7d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * and/or sell copies of the Software, and to permit persons to whom the
9d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * Software is furnished to do so, subject to the following conditions:
10d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller *
11d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * The above copyright notice and this permission notice shall be included in
12d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * all copies or substantial portions of the Software.
13d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller *
14d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
17d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
18d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
19d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller * SOFTWARE.
21d2d19ea51fa3575a8d014a69a9b835c335728817Christoph Bumiller */
2257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
2357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#ifndef __NV50_IR_UTIL_H__
2457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define __NV50_IR_UTIL_H__
2557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
2657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include <new>
2757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include <assert.h>
2857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include <stdio.h>
2978de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez#include <memory>
3056d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez#include <map>
31a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
32a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez#ifndef NDEBUG
33a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez# include <typeinfo>
34a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez#endif
3557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
3657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "util/u_inlines.h"
3757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#include "util/u_memory.h"
3857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
3957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define ERROR(args...) debug_printf("ERROR: " args)
4057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define WARN(args...) debug_printf("WARNING: " args)
4157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define INFO(args...) debug_printf(args)
4257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
4357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define INFO_DBG(m, f, args...)          \
4457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   do {                                  \
4557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (m & NV50_IR_DEBUG_##f)         \
4657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         debug_printf(args);             \
4757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   } while(0)
4857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
4957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define FATAL(args...)          \
5057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   do {                         \
5157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      fprintf(stderr, args);    \
5257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      abort();                  \
5357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   } while(0)
5457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
5557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
5657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...)               \
5757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
5857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
5957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_Instruction(f, args...)                      \
6057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)
6157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_CmpInstruction(f, args...)                   \
6257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)
6357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_TexInstruction(f, args...)                   \
6457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)
6557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_FlowInstruction(f, args...)                  \
6657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)
6757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
6857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_LValue(f, args...)                  \
6957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
7057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
7157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
7257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...)   \
7357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   new ((p)->mem_##obj.allocate()) obj(p, args)
7457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
7557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_Symbol(p, args...)                           \
7657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)
7757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define new_ImmediateValue(p, args...)                   \
7857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)
7957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
8057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
8157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
8257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define delete_Value(p, val) (p)->releaseValue(val)
8357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
8457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
8557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillernamespace nv50_ir {
8657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
8757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Iterator
8857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
8957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
9078de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez   virtual ~Iterator() { };
9157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   virtual void next() = 0;
9257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   virtual void *get() const = 0;
9357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   virtual bool end() const = 0; // if true, get will return 0
9400fe442253744c4c4e7e68da44d6983da053968bChristoph Bumiller   virtual void reset() { assert(0); } // only for graph iterators
9557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
9657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
9778de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jereztypedef std::auto_ptr<Iterator> IteratorRef;
9878de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez
9957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass ManipIterator : public Iterator
10057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
10157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
10257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   virtual bool insert(void *) = 0; // insert after current position
10357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   virtual void erase() = 0;
10457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
10557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
10657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// WARNING: do not use a->prev/next for __item or __list
10757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
10857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_DEL(__item)                      \
10957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   do {                                         \
11057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->prev->next = (__item)->next;    \
11157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->next->prev = (__item)->prev;    \
11257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->next = (__item);                \
11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->prev = (__item);                \
11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   } while(0)
11557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_ADDTAIL(__list, __item)          \
11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   do {                                         \
11857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->next = (__list);                \
11957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->prev = (__list)->prev;          \
12057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__list)->prev->next = (__item);          \
12157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__list)->prev = (__item);                \
12257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   } while(0)
12357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
12457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_ADDHEAD(__list, __item)          \
12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   do {                                         \
12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->prev = (__list);                \
12757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__item)->next = (__list)->next;          \
12857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__list)->next->prev = (__item);          \
12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__list)->next = (__item);                \
13057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   } while(0)
13157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_MERGE(__listA, __listB, ty)      \
13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   do {                                         \
13457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      ty prevB = (__listB)->prev;               \
13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__listA)->prev->next = (__listB);        \
13657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__listB)->prev->next = (__listA);        \
13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__listB)->prev = (__listA)->prev;        \
13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      (__listA)->prev = prevB;                  \
13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   } while(0)
14057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
141e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#define DLLIST_EMPTY(__list) ((__list)->next == (__list))
142e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller
14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_FOR_EACH(list, it) \
14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())
14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass DLList
14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   class Item
15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
15157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
15257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item(void *priv) : next(this), prev(this), data(priv) { }
15357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item *next;
15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item *prev;
15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void *data;
15857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   };
15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   DLList() : head(0) { }
16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ~DLList() { clear(); }
16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void insertHead(void *data)
16457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item *item = new Item(data);
16657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
16757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(data);
16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
16957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      item->prev = &head;
17057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      item->next = head.next;
17157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      head.next->prev = item;
17257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      head.next = item;
17357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
17457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
17557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void insertTail(void *data)
17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
17757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item *item = new Item(data);
17857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
17957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(data);
18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      DLLIST_ADDTAIL(&head, item);
18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void insert(void *data) { insertTail(data); }
18557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void clear();
18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   class Iterator : public ManipIterator
18957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next),
19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller                                     term(head) { }
19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; }
19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      virtual void *get() const { return pos->data; }
19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      virtual bool end() const { return pos == term; }
19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      // caution: if you're at end-2 and erase it, then do next, you're at end
19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      virtual void erase();
20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      virtual bool insert(void *data);
20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      // move item to a another list, no consistency with its iterators though
20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void moveToList(DLList&);
20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   private:
20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const bool rev;
20757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item *pos;
20857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item *term;
20957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
21057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      friend class DLList;
21157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   };
21257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void erase(Iterator& pos)
21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      pos.erase();
21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Iterator iterator()
21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return Iterator(&head, false);
22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Iterator revIterator()
22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return Iterator(&head, true);
22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
22857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
22957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Item head;
23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Stack
23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
23557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   class Item {
23657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      union {
23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         void *p;
23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         int i;
24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         unsigned int u;
24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         float f;
24257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         double d;
24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      } u;
24457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Item() { memset(&u, 0, sizeof(u)); }
24657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   };
24757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
24857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Stack() : size(0), limit(0), array(0) { }
24957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ~Stack() { if (array) FREE(array); }
25057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
25157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void push(int i)          { Item data; data.u.i = i; push(data); }
25257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void push(unsigned int u) { Item data; data.u.u = u; push(data); }
25357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void push(void *p)        { Item data; data.u.p = p; push(data); }
25457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void push(float f)        { Item data; data.u.f = f; push(data); }
25557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void push(Item data)
25757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
25857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (size == limit)
25957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         resize();
26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      array[size++] = data;
26157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
26257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline Item pop()
26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
26557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (!size) {
26657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         Item data;
26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         assert(0);
26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         return data;
26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      }
27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return array[--size];
27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline unsigned int getSize() { return size; }
27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline Item& peek() { assert(size); return array[size - 1]; }
27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
27757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void clear(bool releaseStorage = false)
27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (releaseStorage && array)
28057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         FREE(array);
28157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      size = limit = 0;
28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void moveTo(Stack&); // move all items to target (not like push(pop()))
28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void resize()
28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         unsigned int sizeOld, sizeNew;
29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         sizeOld = limit * sizeof(Item);
29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         limit = MAX2(4, limit + limit);
29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         sizeNew = limit * sizeof(Item);
29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         array = (Item *)REALLOC(array, sizeOld, sizeNew);
29657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
29757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int size;
29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int limit;
30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Item *array;
30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass DynArray
30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   class Item
30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      union {
31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         uint32_t u32;
31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         void *p;
31257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      };
31357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   };
31457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
31557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   DynArray() : data(NULL), size(0) { }
31657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
31757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ~DynArray() { if (data) FREE(data); }
31857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
31957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline Item& operator[](unsigned int i)
32057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
32157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (i >= size)
32257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         resize(i);
32357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return data[i];
32457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
32557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
32657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline const Item operator[](unsigned int i) const
32757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
32857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return data[i];
32957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
33057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
33157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void resize(unsigned int index)
33257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
33357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const unsigned int oldSize = size * sizeof(Item);
33457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
33557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (!size)
33657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         size = 8;
33757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      while (size <= index)
33857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         size <<= 1;
33957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
34057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      data = (Item *)REALLOC(data, oldSize, size * sizeof(Item));
34157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
34257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
3434a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez   void clear()
3444a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez   {
3454a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez      FREE(data);
3464a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez      data = NULL;
3474a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez      size = 0;
3484a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez   }
3494a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez
35057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
35157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Item *data;
35257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int size;
35357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
35457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
35557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass ArrayList
35657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
35757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
35857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ArrayList() : size(0) { }
35957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void insert(void *item, int& id)
36157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
36257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      id = ids.getSize() ? ids.pop().u.i : size++;
36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      data[id].p = item;
36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void remove(int& id)
36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const unsigned int uid = id;
36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(uid < size && data[id].p);
37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      ids.push(uid);
37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      data[uid].p = NULL;
37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      id = -1;
37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline int getSize() const { return size; }
37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void *get(unsigned int id) { assert(id < size); return data[id].p; }
37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   class Iterator : public nv50_ir::Iterator
38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Iterator(const ArrayList *array) : pos(0), data(array->data)
38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      {
38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         size = array->getSize();
38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         if (size)
38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            nextValid();
38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      }
38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }
39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
39157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void next() { if (pos < size) { ++pos; nextValid(); } }
39257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void *get() const { assert(pos < size); return data[pos].p; }
39357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      bool end() const { return pos >= size; }
39457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
39557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   private:
39657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      unsigned int pos;
39757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      unsigned int size;
39857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const DynArray& data;
39957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
40057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      friend class ArrayList;
40157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   };
40257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
40357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Iterator iterator() const { return Iterator(this); }
40457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
4054a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez   void clear()
4064a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez   {
4074a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez      data.clear();
4084a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez      ids.clear(true);
4094a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez      size = 0;
4104a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez   }
4114a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez
41257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
41357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   DynArray data;
41457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Stack ids;
41557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int size;
41657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
41757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
41857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Interval
41957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
42057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
42157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Interval() : head(0), tail(0) { }
422e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   Interval(const Interval&);
42357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ~Interval();
42457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
42557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   bool extend(int, int);
426e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   void insert(const Interval&);
42757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void unify(Interval&); // clears source interval
42857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void clear();
42957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
430e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline int begin() const { return head ? head->bgn : -1; }
431e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline int end() const { checkTail(); return tail ? tail->end : -1; }
43257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline bool isEmpty() const { return !head; }
43357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   bool overlaps(const Interval&) const;
434e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   bool contains(int pos) const;
435e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller
436e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline int extent() const { return end() - begin(); }
437e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   int length() const;
43857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
43957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void print() const;
44057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
44157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void checkTail() const;
44257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
44357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
44457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   class Range
44557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
44657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   public:
44757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Range(int a, int b) : next(0), bgn(a), end(b) { }
44857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
44957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      Range *next;
45057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      int bgn;
45157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      int end;
45257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
45357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void coalesce(Range **ptail)
45457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      {
45557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         Range *rnn;
45657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
45757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         while (next && end >= next->bgn) {
45857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            assert(bgn <= next->bgn);
45957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            rnn = next->next;
46057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            end = MAX2(end, next->end);
46157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            delete next;
46257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            next = rnn;
46357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         }
46457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         if (!next)
46557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            *ptail = this;
46657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      }
46757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   };
46857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
46957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Range *head;
47057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Range *tail;
47157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
47257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
47357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass BitSet
47457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
47557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
47657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   BitSet() : marker(false), data(0), size(0) { }
47757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)
47857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
47957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      allocate(nBits, zero);
48057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
48157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ~BitSet()
48257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
48357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (data)
48457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         FREE(data);
48557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
48657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
48757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   bool allocate(unsigned int nBits, bool zero);
488e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   bool resize(unsigned int nBits); // keep old data, zero additional bits
48957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
49057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline unsigned int getSize() const { return size; }
49157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
49257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void fill(uint32_t val);
49357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
49457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void setOr(BitSet *, BitSet *); // second BitSet may be NULL
49557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
49657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void set(unsigned int i)
49757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
49857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(i < size);
49957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      data[i / 32] |= 1 << (i % 32);
50057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
501e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   // NOTE: range may not cross 32 bit boundary (implies n <= 32)
502e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline void setRange(unsigned int i, unsigned int n)
503e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   {
504e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      assert((i + n) <= size && (((i % 32) + n) <= 32));
505e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      data[i / 32] |= ((1 << n) - 1) << (i % 32);
506e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   }
507e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline void setMask(unsigned int i, uint32_t m)
508e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   {
509e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      assert(i < size);
510e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      data[i / 32] |= m;
511e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   }
51257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
51357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline void clr(unsigned int i)
51457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
51557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(i < size);
51657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      data[i / 32] &= ~(1 << (i % 32));
51757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
518e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   // NOTE: range may not cross 32 bit boundary (implies n <= 32)
519e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline void clrRange(unsigned int i, unsigned int n)
520e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   {
521e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      assert((i + n) <= size && (((i % 32) + n) <= 32));
522e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      data[i / 32] &= ~(((1 << n) - 1) << (i % 32));
523e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   }
52457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
52557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline bool test(unsigned int i) const
52657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
52757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(i < size);
52857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return data[i / 32] & (1 << (i % 32));
52957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
530e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   // NOTE: range may not cross 32 bit boundary (implies n <= 32)
531e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline bool testRange(unsigned int i, unsigned int n)
532e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   {
533e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      assert((i + n) <= size && (((i % 32) + n) <= 32));
534e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      return data[i / 32] & (((1 << n) - 1) << (i % 32));
535e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   }
536e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller
537e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size).
538e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   int findFreeRange(unsigned int size) const;
53957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
54057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   BitSet& operator|=(const BitSet&);
54157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
54257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   BitSet& operator=(const BitSet& set)
54357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
54457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(data && set.data);
54557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      assert(size == set.size);
54657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      memcpy(data, set.data, (set.size + 7) / 8);
54757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return *this;
54857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
54957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
55057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void andNot(const BitSet&);
55157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
552e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   // bits = (bits | setMask) & ~clrMask
553e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   inline void periodicMask32(uint32_t setMask, uint32_t clrMask)
554e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   {
555e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller      for (unsigned int i = 0; i < (size + 31) / 32; ++i)
556e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller         data[i] = (data[i] | setMask) & ~clrMask;
557e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller   }
558e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller
55957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int popCount() const;
56057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
56157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void print() const;
56257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
56357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
56457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   bool marker; // for user
56557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
56657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
56757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   uint32_t *data;
56857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int size;
56957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
57057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
57157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Interval::checkTail() const
57257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
57357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#if NV50_DEBUG & NV50_DEBUG_PROG_RA
57457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   Range *r = head;
57557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   while (r->next)
57657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      r = r->next;
57757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   assert(tail == r);
57857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif
57957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}
58057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
58157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass MemoryPool
58257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{
58357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
58457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)
58557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
58657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const unsigned int size = sizeof(uint8_t *) * id;
58757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const unsigned int incr = sizeof(uint8_t *) * nr;
58857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
58957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);
59057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (!alloc)
59157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         return false;
59257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      allocArray = alloc;
59357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return true;
59457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
59557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
59657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   inline bool enlargeCapacity()
59757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
59857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const unsigned int id = count >> objStepLog2;
59957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
60057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);
60157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (!mem)
60257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         return false;
60357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
60457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (!(id % 32)) {
60557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         if (!enlargeAllocationsArray(id, 32)) {
60657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            FREE(mem);
60757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            return false;
60857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         }
60957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      }
61057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      allocArray[id] = mem;
61157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return true;
61257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
61357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
61457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic:
61557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   MemoryPool(unsigned int size, unsigned int incr) : objSize(size),
61657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller                                                      objStepLog2(incr)
61757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
61857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      allocArray = NULL;
61957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      released = NULL;
62057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      count = 0;
62157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
62257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
62357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   ~MemoryPool()
62457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
62557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;
62657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)
62757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         FREE(allocArray[i]);
62857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (allocArray)
62957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         FREE(allocArray);
63057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
63157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
63257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void *allocate()
63357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
63457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      void *ret;
63557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      const unsigned int mask = (1 << objStepLog2) - 1;
63657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
63757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (released) {
63857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         ret = released;
63957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         released = *(void **)released;
64057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         return ret;
64157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      }
64257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
64357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      if (!(count & mask))
64457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller         if (!enlargeCapacity())
64557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller            return NULL;
64657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
64757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;
64857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      ++count;
64957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      return ret;
65057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
65157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
65257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void release(void *ptr)
65357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   {
65457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      *(void **)ptr = released;
65557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller      released = ptr;
65657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   }
65757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
65857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate:
65957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   uint8_t **allocArray; // array (list) of MALLOC allocations
66057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
66157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   void *released; // list of released objects
66257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
66357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   unsigned int count; // highest allocated object
66457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
66557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   const unsigned int objSize;
66657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller   const unsigned int objStepLog2;
66757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller};
66857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
669a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/**
670a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  Composite object cloning policy.
671a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *
672a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  Encapsulates how sub-objects are to be handled (if at all) when a
673a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  composite object is being cloned.
674a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */
675a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C>
676a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass ClonePolicy
677a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{
678a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected:
679a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   C *c;
680a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
681a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic:
682a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   ClonePolicy(C *c) : c(c) {}
683a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
684a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   C *context() { return c; }
685a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
686a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   template<typename T> T *get(T *obj)
687a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   {
688a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      void *clone = lookup(obj);
689a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      if (!clone)
690a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez         clone = obj->clone(*this);
691a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      return reinterpret_cast<T *>(clone);
692a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   }
693a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
694a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   template<typename T> void set(const T *obj, T *clone)
695a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   {
696a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      insert(obj, clone);
697a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   }
698a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
699a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected:
700a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   virtual void *lookup(void *obj) = 0;
701a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   virtual void insert(const void *obj, void *clone) = 0;
702a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez};
703a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
704a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/**
705a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  Shallow non-recursive cloning policy.
706a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *
707a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  Objects cloned with the "shallow" policy don't clone their
708a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  children recursively, instead, the new copy shares its children
709a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  with the original object.
710a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */
711a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C>
712a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass ShallowClonePolicy : public ClonePolicy<C>
713a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{
714a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic:
715a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {}
716a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
717a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected:
718a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   virtual void *lookup(void *obj)
719a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   {
720a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      return obj;
721a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   }
722a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
723a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   virtual void insert(const void *obj, void *clone)
724a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   {
725a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   }
726a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez};
727a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
728a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C, typename T>
729a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezinline T *cloneShallow(C *c, T *obj)
730a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{
731a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   ShallowClonePolicy<C> pol(c);
732a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   return obj->clone(pol);
733a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}
734a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
735a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/**
736a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  Recursive cloning policy.
737a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *
738a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  Objects cloned with the "deep" policy clone their children
739a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  recursively, keeping track of what has already been cloned to
740a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez *  avoid making several new copies of the same object.
741a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */
742a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C>
743a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass DeepClonePolicy : public ClonePolicy<C>
744a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{
745a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic:
746a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   DeepClonePolicy(C *c) : ClonePolicy<C>(c) {}
747a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
748a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprivate:
749a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   std::map<const void *, void *> map;
750a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
751a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected:
752a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   virtual void *lookup(void *obj)
753a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   {
754a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      return map[obj];
755a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   }
756a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
757a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   virtual void insert(const void *obj, void *clone)
758a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   {
759a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez      map[obj] = clone;
760a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez   }
761a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez};
762a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez
76356d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jereztemplate<typename S, typename T>
76456d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerezstruct bimap
76556d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez{
76656d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   std::map<S, T> forth;
76756d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   std::map<T, S> back;
76856d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez
76956d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerezpublic:
77056d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   bimap() : l(back), r(forth) { }
77156d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   bimap(const bimap<S, T> &m)
77256d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez      : forth(m.forth), back(m.back), l(back), r(forth) { }
77356d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez
77456d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   void insert(const S &s, const T &t)
77556d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   {
77656d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez      forth.insert(std::make_pair(s, t));
77756d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez      back.insert(std::make_pair(t, s));
77856d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   }
77956d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez
78056d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   typedef typename std::map<T, S>::const_iterator l_iterator;
78156d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   const std::map<T, S> &l;
78256d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   typedef typename std::map<S, T>::const_iterator r_iterator;
78356d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez   const std::map<S, T> &r;
78456d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez};
78556d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez
78657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir
78757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller
78857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif // __NV50_IR_UTIL_H__
789