Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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 OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  18.  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  19.  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  20.  * OTHER DEALINGS IN THE SOFTWARE.
  21.  */
  22.  
  23. #ifndef __NV50_IR_UTIL_H__
  24. #define __NV50_IR_UTIL_H__
  25.  
  26. #include <new>
  27. #include <assert.h>
  28. #include <stdio.h>
  29. #include <memory>
  30. #include <map>
  31.  
  32. #ifndef NDEBUG
  33. # include <typeinfo>
  34. #endif
  35.  
  36. #include "util/u_inlines.h"
  37. #include "util/u_memory.h"
  38.  
  39. #define ERROR(args...) debug_printf("ERROR: " args)
  40. #define WARN(args...) debug_printf("WARNING: " args)
  41. #define INFO(args...) debug_printf(args)
  42.  
  43. #define INFO_DBG(m, f, args...)          \
  44.    do {                                  \
  45.       if (m & NV50_IR_DEBUG_##f)         \
  46.          debug_printf(args);             \
  47.    } while(0)
  48.  
  49. #define FATAL(args...)          \
  50.    do {                         \
  51.       fprintf(stderr, args);    \
  52.       abort();                  \
  53.    } while(0)
  54.  
  55.  
  56. #define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...)               \
  57.    new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
  58.  
  59. #define new_Instruction(f, args...)                      \
  60.    NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)
  61. #define new_CmpInstruction(f, args...)                   \
  62.    NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)
  63. #define new_TexInstruction(f, args...)                   \
  64.    NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)
  65. #define new_FlowInstruction(f, args...)                  \
  66.    NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)
  67.  
  68. #define new_LValue(f, args...)                  \
  69.    NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
  70.  
  71.  
  72. #define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...)   \
  73.    new ((p)->mem_##obj.allocate()) obj(p, args)
  74.  
  75. #define new_Symbol(p, args...)                           \
  76.    NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)
  77. #define new_ImmediateValue(p, args...)                   \
  78.    NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)
  79.  
  80.  
  81. #define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
  82. #define delete_Value(p, val) (p)->releaseValue(val)
  83.  
  84.  
  85. namespace nv50_ir {
  86.  
  87. class Iterator
  88. {
  89. public:
  90.    virtual ~Iterator() { };
  91.    virtual void next() = 0;
  92.    virtual void *get() const = 0;
  93.    virtual bool end() const = 0; // if true, get will return 0
  94.    virtual void reset() { assert(0); } // only for graph iterators
  95. };
  96.  
  97. typedef std::auto_ptr<Iterator> IteratorRef;
  98.  
  99. class ManipIterator : public Iterator
  100. {
  101. public:
  102.    virtual bool insert(void *) = 0; // insert after current position
  103.    virtual void erase() = 0;
  104. };
  105.  
  106. // WARNING: do not use a->prev/next for __item or __list
  107.  
  108. #define DLLIST_DEL(__item)                      \
  109.    do {                                         \
  110.       (__item)->prev->next = (__item)->next;    \
  111.       (__item)->next->prev = (__item)->prev;    \
  112.       (__item)->next = (__item);                \
  113.       (__item)->prev = (__item);                \
  114.    } while(0)
  115.  
  116. #define DLLIST_ADDTAIL(__list, __item)          \
  117.    do {                                         \
  118.       (__item)->next = (__list);                \
  119.       (__item)->prev = (__list)->prev;          \
  120.       (__list)->prev->next = (__item);          \
  121.       (__list)->prev = (__item);                \
  122.    } while(0)
  123.  
  124. #define DLLIST_ADDHEAD(__list, __item)          \
  125.    do {                                         \
  126.       (__item)->prev = (__list);                \
  127.       (__item)->next = (__list)->next;          \
  128.       (__list)->next->prev = (__item);          \
  129.       (__list)->next = (__item);                \
  130.    } while(0)
  131.  
  132. #define DLLIST_MERGE(__listA, __listB, ty)      \
  133.    do {                                         \
  134.       ty prevB = (__listB)->prev;               \
  135.       (__listA)->prev->next = (__listB);        \
  136.       (__listB)->prev->next = (__listA);        \
  137.       (__listB)->prev = (__listA)->prev;        \
  138.       (__listA)->prev = prevB;                  \
  139.    } while(0)
  140.  
  141. #define DLLIST_EMPTY(__list) ((__list)->next == (__list))
  142.  
  143. #define DLLIST_FOR_EACH(list, it) \
  144.    for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())
  145.  
  146. class DLList
  147. {
  148. public:
  149.    class Item
  150.    {
  151.    public:
  152.       Item(void *priv) : next(this), prev(this), data(priv) { }
  153.  
  154.    public:
  155.       Item *next;
  156.       Item *prev;
  157.       void *data;
  158.    };
  159.  
  160.    DLList() : head(0) { }
  161.    ~DLList() { clear(); }
  162.  
  163.    inline void insertHead(void *data)
  164.    {
  165.       Item *item = new Item(data);
  166.  
  167.       assert(data);
  168.  
  169.       item->prev = &head;
  170.       item->next = head.next;
  171.       head.next->prev = item;
  172.       head.next = item;
  173.    }
  174.  
  175.    inline void insertTail(void *data)
  176.    {
  177.       Item *item = new Item(data);
  178.  
  179.       assert(data);
  180.  
  181.       DLLIST_ADDTAIL(&head, item);
  182.    }
  183.  
  184.    inline void insert(void *data) { insertTail(data); }
  185.  
  186.    void clear();
  187.  
  188.    class Iterator : public ManipIterator
  189.    {
  190.    public:
  191.       Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next),
  192.                                      term(head) { }
  193.  
  194.       virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; }
  195.       virtual void *get() const { return pos->data; }
  196.       virtual bool end() const { return pos == term; }
  197.  
  198.       // caution: if you're at end-2 and erase it, then do next, you're at end
  199.       virtual void erase();
  200.       virtual bool insert(void *data);
  201.  
  202.       // move item to a another list, no consistency with its iterators though
  203.       void moveToList(DLList&);
  204.  
  205.    private:
  206.       const bool rev;
  207.       Item *pos;
  208.       Item *term;
  209.  
  210.       friend class DLList;
  211.    };
  212.  
  213.    inline void erase(Iterator& pos)
  214.    {
  215.       pos.erase();
  216.    }
  217.  
  218.    Iterator iterator()
  219.    {
  220.       return Iterator(&head, false);
  221.    }
  222.  
  223.    Iterator revIterator()
  224.    {
  225.       return Iterator(&head, true);
  226.    }
  227.  
  228. private:
  229.    Item head;
  230. };
  231.  
  232. class Stack
  233. {
  234. public:
  235.    class Item {
  236.    public:
  237.       union {
  238.          void *p;
  239.          int i;
  240.          unsigned int u;
  241.          float f;
  242.          double d;
  243.       } u;
  244.  
  245.       Item() { memset(&u, 0, sizeof(u)); }
  246.    };
  247.  
  248.    Stack() : size(0), limit(0), array(0) { }
  249.    ~Stack() { if (array) FREE(array); }
  250.  
  251.    inline void push(int i)          { Item data; data.u.i = i; push(data); }
  252.    inline void push(unsigned int u) { Item data; data.u.u = u; push(data); }
  253.    inline void push(void *p)        { Item data; data.u.p = p; push(data); }
  254.    inline void push(float f)        { Item data; data.u.f = f; push(data); }
  255.  
  256.    inline void push(Item data)
  257.    {
  258.       if (size == limit)
  259.          resize();
  260.       array[size++] = data;
  261.    }
  262.  
  263.    inline Item pop()
  264.    {
  265.       if (!size) {
  266.          Item data;
  267.          assert(0);
  268.          return data;
  269.       }
  270.       return array[--size];
  271.    }
  272.  
  273.    inline unsigned int getSize() { return size; }
  274.  
  275.    inline Item& peek() { assert(size); return array[size - 1]; }
  276.  
  277.    void clear(bool releaseStorage = false)
  278.    {
  279.       if (releaseStorage && array)
  280.          FREE(array);
  281.       size = limit = 0;
  282.    }
  283.  
  284.    void moveTo(Stack&); // move all items to target (not like push(pop()))
  285.  
  286. private:
  287.    void resize()
  288.    {
  289.          unsigned int sizeOld, sizeNew;
  290.  
  291.          sizeOld = limit * sizeof(Item);
  292.          limit = MAX2(4, limit + limit);
  293.          sizeNew = limit * sizeof(Item);
  294.  
  295.          array = (Item *)REALLOC(array, sizeOld, sizeNew);
  296.    }
  297.  
  298.    unsigned int size;
  299.    unsigned int limit;
  300.    Item *array;
  301. };
  302.  
  303. class DynArray
  304. {
  305. public:
  306.    class Item
  307.    {
  308.    public:
  309.       union {
  310.          uint32_t u32;
  311.          void *p;
  312.       };
  313.    };
  314.  
  315.    DynArray() : data(NULL), size(0) { }
  316.  
  317.    ~DynArray() { if (data) FREE(data); }
  318.  
  319.    inline Item& operator[](unsigned int i)
  320.    {
  321.       if (i >= size)
  322.          resize(i);
  323.       return data[i];
  324.    }
  325.  
  326.    inline const Item operator[](unsigned int i) const
  327.    {
  328.       return data[i];
  329.    }
  330.  
  331.    void resize(unsigned int index)
  332.    {
  333.       const unsigned int oldSize = size * sizeof(Item);
  334.  
  335.       if (!size)
  336.          size = 8;
  337.       while (size <= index)
  338.          size <<= 1;
  339.  
  340.       data = (Item *)REALLOC(data, oldSize, size * sizeof(Item));
  341.    }
  342.  
  343.    void clear()
  344.    {
  345.       FREE(data);
  346.       data = NULL;
  347.       size = 0;
  348.    }
  349.  
  350. private:
  351.    Item *data;
  352.    unsigned int size;
  353. };
  354.  
  355. class ArrayList
  356. {
  357. public:
  358.    ArrayList() : size(0) { }
  359.  
  360.    void insert(void *item, int& id)
  361.    {
  362.       id = ids.getSize() ? ids.pop().u.i : size++;
  363.       data[id].p = item;
  364.    }
  365.  
  366.    void remove(int& id)
  367.    {
  368.       const unsigned int uid = id;
  369.       assert(uid < size && data[id].p);
  370.       ids.push(uid);
  371.       data[uid].p = NULL;
  372.       id = -1;
  373.    }
  374.  
  375.    inline int getSize() const { return size; }
  376.  
  377.    inline void *get(unsigned int id) { assert(id < size); return data[id].p; }
  378.  
  379.    class Iterator : public nv50_ir::Iterator
  380.    {
  381.    public:
  382.       Iterator(const ArrayList *array) : pos(0), data(array->data)
  383.       {
  384.          size = array->getSize();
  385.          if (size)
  386.             nextValid();
  387.       }
  388.  
  389.       void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }
  390.  
  391.       void next() { if (pos < size) { ++pos; nextValid(); } }
  392.       void *get() const { assert(pos < size); return data[pos].p; }
  393.       bool end() const { return pos >= size; }
  394.  
  395.    private:
  396.       unsigned int pos;
  397.       unsigned int size;
  398.       const DynArray& data;
  399.  
  400.       friend class ArrayList;
  401.    };
  402.  
  403.    Iterator iterator() const { return Iterator(this); }
  404.  
  405.    void clear()
  406.    {
  407.       data.clear();
  408.       ids.clear(true);
  409.       size = 0;
  410.    }
  411.  
  412. private:
  413.    DynArray data;
  414.    Stack ids;
  415.    unsigned int size;
  416. };
  417.  
  418. class Interval
  419. {
  420. public:
  421.    Interval() : head(0), tail(0) { }
  422.    Interval(const Interval&);
  423.    ~Interval();
  424.  
  425.    bool extend(int, int);
  426.    void insert(const Interval&);
  427.    void unify(Interval&); // clears source interval
  428.    void clear();
  429.  
  430.    inline int begin() const { return head ? head->bgn : -1; }
  431.    inline int end() const { checkTail(); return tail ? tail->end : -1; }
  432.    inline bool isEmpty() const { return !head; }
  433.    bool overlaps(const Interval&) const;
  434.    bool contains(int pos) const;
  435.  
  436.    inline int extent() const { return end() - begin(); }
  437.    int length() const;
  438.  
  439.    void print() const;
  440.  
  441.    inline void checkTail() const;
  442.  
  443. private:
  444.    class Range
  445.    {
  446.    public:
  447.       Range(int a, int b) : next(0), bgn(a), end(b) { }
  448.  
  449.       Range *next;
  450.       int bgn;
  451.       int end;
  452.  
  453.       void coalesce(Range **ptail)
  454.       {
  455.          Range *rnn;
  456.  
  457.          while (next && end >= next->bgn) {
  458.             assert(bgn <= next->bgn);
  459.             rnn = next->next;
  460.             end = MAX2(end, next->end);
  461.             delete next;
  462.             next = rnn;
  463.          }
  464.          if (!next)
  465.             *ptail = this;
  466.       }
  467.    };
  468.  
  469.    Range *head;
  470.    Range *tail;
  471. };
  472.  
  473. class BitSet
  474. {
  475. public:
  476.    BitSet() : marker(false), data(0), size(0) { }
  477.    BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)
  478.    {
  479.       allocate(nBits, zero);
  480.    }
  481.    ~BitSet()
  482.    {
  483.       if (data)
  484.          FREE(data);
  485.    }
  486.  
  487.    // allocate will keep old data iff size is unchanged
  488.    bool allocate(unsigned int nBits, bool zero);
  489.    bool resize(unsigned int nBits); // keep old data, zero additional bits
  490.  
  491.    inline unsigned int getSize() const { return size; }
  492.  
  493.    void fill(uint32_t val);
  494.  
  495.    void setOr(BitSet *, BitSet *); // second BitSet may be NULL
  496.  
  497.    inline void set(unsigned int i)
  498.    {
  499.       assert(i < size);
  500.       data[i / 32] |= 1 << (i % 32);
  501.    }
  502.    // NOTE: range may not cross 32 bit boundary (implies n <= 32)
  503.    inline void setRange(unsigned int i, unsigned int n)
  504.    {
  505.       assert((i + n) <= size && (((i % 32) + n) <= 32));
  506.       data[i / 32] |= ((1 << n) - 1) << (i % 32);
  507.    }
  508.    inline void setMask(unsigned int i, uint32_t m)
  509.    {
  510.       assert(i < size);
  511.       data[i / 32] |= m;
  512.    }
  513.  
  514.    inline void clr(unsigned int i)
  515.    {
  516.       assert(i < size);
  517.       data[i / 32] &= ~(1 << (i % 32));
  518.    }
  519.    // NOTE: range may not cross 32 bit boundary (implies n <= 32)
  520.    inline void clrRange(unsigned int i, unsigned int n)
  521.    {
  522.       assert((i + n) <= size && (((i % 32) + n) <= 32));
  523.       data[i / 32] &= ~(((1 << n) - 1) << (i % 32));
  524.    }
  525.  
  526.    inline bool test(unsigned int i) const
  527.    {
  528.       assert(i < size);
  529.       return data[i / 32] & (1 << (i % 32));
  530.    }
  531.    // NOTE: range may not cross 32 bit boundary (implies n <= 32)
  532.    inline bool testRange(unsigned int i, unsigned int n) const
  533.    {
  534.       assert((i + n) <= size && (((i % 32) + n) <= 32));
  535.       return data[i / 32] & (((1 << n) - 1) << (i % 32));
  536.    }
  537.  
  538.    // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size).
  539.    int findFreeRange(unsigned int size) const;
  540.  
  541.    BitSet& operator|=(const BitSet&);
  542.  
  543.    BitSet& operator=(const BitSet& set)
  544.    {
  545.       assert(data && set.data);
  546.       assert(size == set.size);
  547.       memcpy(data, set.data, (set.size + 7) / 8);
  548.       return *this;
  549.    }
  550.  
  551.    void andNot(const BitSet&);
  552.  
  553.    // bits = (bits | setMask) & ~clrMask
  554.    inline void periodicMask32(uint32_t setMask, uint32_t clrMask)
  555.    {
  556.       for (unsigned int i = 0; i < (size + 31) / 32; ++i)
  557.          data[i] = (data[i] | setMask) & ~clrMask;
  558.    }
  559.  
  560.    unsigned int popCount() const;
  561.  
  562.    void print() const;
  563.  
  564. public:
  565.    bool marker; // for user
  566.  
  567. private:
  568.    uint32_t *data;
  569.    unsigned int size;
  570. };
  571.  
  572. void Interval::checkTail() const
  573. {
  574. #if NV50_DEBUG & NV50_DEBUG_PROG_RA
  575.    Range *r = head;
  576.    while (r->next)
  577.       r = r->next;
  578.    assert(tail == r);
  579. #endif
  580. }
  581.  
  582. class MemoryPool
  583. {
  584. private:
  585.    inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)
  586.    {
  587.       const unsigned int size = sizeof(uint8_t *) * id;
  588.       const unsigned int incr = sizeof(uint8_t *) * nr;
  589.  
  590.       uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);
  591.       if (!alloc)
  592.          return false;
  593.       allocArray = alloc;
  594.       return true;
  595.    }
  596.  
  597.    inline bool enlargeCapacity()
  598.    {
  599.       const unsigned int id = count >> objStepLog2;
  600.  
  601.       uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);
  602.       if (!mem)
  603.          return false;
  604.  
  605.       if (!(id % 32)) {
  606.          if (!enlargeAllocationsArray(id, 32)) {
  607.             FREE(mem);
  608.             return false;
  609.          }
  610.       }
  611.       allocArray[id] = mem;
  612.       return true;
  613.    }
  614.  
  615. public:
  616.    MemoryPool(unsigned int size, unsigned int incr) : objSize(size),
  617.                                                       objStepLog2(incr)
  618.    {
  619.       allocArray = NULL;
  620.       released = NULL;
  621.       count = 0;
  622.    }
  623.  
  624.    ~MemoryPool()
  625.    {
  626.       unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;
  627.       for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)
  628.          FREE(allocArray[i]);
  629.       if (allocArray)
  630.          FREE(allocArray);
  631.    }
  632.  
  633.    void *allocate()
  634.    {
  635.       void *ret;
  636.       const unsigned int mask = (1 << objStepLog2) - 1;
  637.  
  638.       if (released) {
  639.          ret = released;
  640.          released = *(void **)released;
  641.          return ret;
  642.       }
  643.  
  644.       if (!(count & mask))
  645.          if (!enlargeCapacity())
  646.             return NULL;
  647.  
  648.       ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;
  649.       ++count;
  650.       return ret;
  651.    }
  652.  
  653.    void release(void *ptr)
  654.    {
  655.       *(void **)ptr = released;
  656.       released = ptr;
  657.    }
  658.  
  659. private:
  660.    uint8_t **allocArray; // array (list) of MALLOC allocations
  661.  
  662.    void *released; // list of released objects
  663.  
  664.    unsigned int count; // highest allocated object
  665.  
  666.    const unsigned int objSize;
  667.    const unsigned int objStepLog2;
  668. };
  669.  
  670. /**
  671.  *  Composite object cloning policy.
  672.  *
  673.  *  Encapsulates how sub-objects are to be handled (if at all) when a
  674.  *  composite object is being cloned.
  675.  */
  676. template<typename C>
  677. class ClonePolicy
  678. {
  679. protected:
  680.    C *c;
  681.  
  682. public:
  683.    ClonePolicy(C *c) : c(c) {}
  684.  
  685.    C *context() { return c; }
  686.  
  687.    template<typename T> T *get(T *obj)
  688.    {
  689.       void *clone = lookup(obj);
  690.       if (!clone)
  691.          clone = obj->clone(*this);
  692.       return reinterpret_cast<T *>(clone);
  693.    }
  694.  
  695.    template<typename T> void set(const T *obj, T *clone)
  696.    {
  697.       insert(obj, clone);
  698.    }
  699.  
  700. protected:
  701.    virtual void *lookup(void *obj) = 0;
  702.    virtual void insert(const void *obj, void *clone) = 0;
  703. };
  704.  
  705. /**
  706.  *  Shallow non-recursive cloning policy.
  707.  *
  708.  *  Objects cloned with the "shallow" policy don't clone their
  709.  *  children recursively, instead, the new copy shares its children
  710.  *  with the original object.
  711.  */
  712. template<typename C>
  713. class ShallowClonePolicy : public ClonePolicy<C>
  714. {
  715. public:
  716.    ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {}
  717.  
  718. protected:
  719.    virtual void *lookup(void *obj)
  720.    {
  721.       return obj;
  722.    }
  723.  
  724.    virtual void insert(const void *obj, void *clone)
  725.    {
  726.    }
  727. };
  728.  
  729. template<typename C, typename T>
  730. inline T *cloneShallow(C *c, T *obj)
  731. {
  732.    ShallowClonePolicy<C> pol(c);
  733.    return obj->clone(pol);
  734. }
  735.  
  736. /**
  737.  *  Recursive cloning policy.
  738.  *
  739.  *  Objects cloned with the "deep" policy clone their children
  740.  *  recursively, keeping track of what has already been cloned to
  741.  *  avoid making several new copies of the same object.
  742.  */
  743. template<typename C>
  744. class DeepClonePolicy : public ClonePolicy<C>
  745. {
  746. public:
  747.    DeepClonePolicy(C *c) : ClonePolicy<C>(c) {}
  748.  
  749. private:
  750.    std::map<const void *, void *> map;
  751.  
  752. protected:
  753.    virtual void *lookup(void *obj)
  754.    {
  755.       return map[obj];
  756.    }
  757.  
  758.    virtual void insert(const void *obj, void *clone)
  759.    {
  760.       map[obj] = clone;
  761.    }
  762. };
  763.  
  764. template<typename S, typename T>
  765. struct bimap
  766. {
  767.    std::map<S, T> forth;
  768.    std::map<T, S> back;
  769.  
  770. public:
  771.    bimap() : l(back), r(forth) { }
  772.    bimap(const bimap<S, T> &m)
  773.       : forth(m.forth), back(m.back), l(back), r(forth) { }
  774.  
  775.    void insert(const S &s, const T &t)
  776.    {
  777.       forth.insert(std::make_pair(s, t));
  778.       back.insert(std::make_pair(t, s));
  779.    }
  780.  
  781.    typedef typename std::map<T, S>::const_iterator l_iterator;
  782.    const std::map<T, S> &l;
  783.    typedef typename std::map<S, T>::const_iterator r_iterator;
  784.    const std::map<S, T> &r;
  785. };
  786.  
  787. } // namespace nv50_ir
  788.  
  789. #endif // __NV50_IR_UTIL_H__
  790.