nv50_ir_util.h revision e43a3a66a9d8a99021d76ff4d07dec7b8cfd62ca
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 9457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 9557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 9678de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jereztypedef std::auto_ptr<Iterator> IteratorRef; 9778de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez 9857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass ManipIterator : public Iterator 9957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 10057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 10157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool insert(void *) = 0; // insert after current position 10257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void erase() = 0; 10357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 10457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller// WARNING: do not use a->prev/next for __item or __list 10657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 10757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_DEL(__item) \ 10857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller do { \ 10957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->prev->next = (__item)->next; \ 11057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->next->prev = (__item)->prev; \ 11157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->next = (__item); \ 11257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->prev = (__item); \ 11357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } while(0) 11457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 11557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_ADDTAIL(__list, __item) \ 11657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller do { \ 11757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->next = (__list); \ 11857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->prev = (__list)->prev; \ 11957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__list)->prev->next = (__item); \ 12057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__list)->prev = (__item); \ 12157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } while(0) 12257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 12357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_ADDHEAD(__list, __item) \ 12457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller do { \ 12557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->prev = (__list); \ 12657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__item)->next = (__list)->next; \ 12757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__list)->next->prev = (__item); \ 12857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__list)->next = (__item); \ 12957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } while(0) 13057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 13157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_MERGE(__listA, __listB, ty) \ 13257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller do { \ 13357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ty prevB = (__listB)->prev; \ 13457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__listA)->prev->next = (__listB); \ 13557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__listB)->prev->next = (__listA); \ 13657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__listB)->prev = (__listA)->prev; \ 13757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller (__listA)->prev = prevB; \ 13857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } while(0) 13957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 140e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller#define DLLIST_EMPTY(__list) ((__list)->next == (__list)) 141e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_FOR_EACH(list, it) \ 14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next()) 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass DLList 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Item 14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 15157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item(void *priv) : next(this), prev(this), data(priv) { } 15257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *next; 15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *prev; 15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *data; 15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 15857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLList() : head(0) { } 16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~DLList() { clear(); } 16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void insertHead(void *data) 16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 16457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *item = new Item(data); 16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data); 16757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller item->prev = &head; 16957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller item->next = head.next; 17057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller head.next->prev = item; 17157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller head.next = item; 17257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 17357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void insertTail(void *data) 17557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *item = new Item(data); 17757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data); 17957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLLIST_ADDTAIL(&head, item); 18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void insert(void *data) { insertTail(data); } 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void clear(); 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Iterator : public ManipIterator 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 18957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next), 19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller term(head) { } 19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; } 19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void *get() const { return pos->data; } 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool end() const { return pos == term; } 19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // caution: if you're at end-2 and erase it, then do next, you're at end 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void erase(); 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool insert(void *data); 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // move item to a another list, no consistency with its iterators though 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void moveToList(DLList&); 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const bool rev; 20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *pos; 20757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *term; 20857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller friend class DLList; 21057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 21157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void erase(Iterator& pos) 21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos.erase(); 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator iterator() 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return Iterator(&head, false); 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator revIterator() 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return Iterator(&head, true); 22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 22857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item head; 22957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Stack 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Item { 23557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 23657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller union { 23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *p; 23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int i; 23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int u; 24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller float f; 24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller double d; 24257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } u; 24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item() { memset(&u, 0, sizeof(u)); } 24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 24657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Stack() : size(0), limit(0), array(0) { } 24857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~Stack() { if (array) FREE(array); } 24957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(int i) { Item data; data.u.i = i; push(data); } 25157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(unsigned int u) { Item data; data.u.u = u; push(data); } 25257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(void *p) { Item data; data.u.p = p; push(data); } 25357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(float f) { Item data; data.u.f = f; push(data); } 25457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(Item data) 25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 25757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (size == limit) 25857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller resize(); 25957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller array[size++] = data; 26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 26157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Item pop() 26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!size) { 26557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item data; 26657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(0); 26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data; 26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return array[--size]; 27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline unsigned int getSize() { return size; } 27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Item& peek() { assert(size); return array[size - 1]; } 27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void clear(bool releaseStorage = false) 27757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (releaseStorage && array) 27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(array); 28057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = limit = 0; 28157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void moveTo(Stack&); // move all items to target (not like push(pop())) 28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void resize() 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int sizeOld, sizeNew; 28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sizeOld = limit * sizeof(Item); 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller limit = MAX2(4, limit + limit); 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sizeNew = limit * sizeof(Item); 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller array = (Item *)REALLOC(array, sizeOld, sizeNew); 29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 29657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int limit; 29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *array; 30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass DynArray 30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Item 30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller union { 30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t u32; 31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *p; 31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 31257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 31357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DynArray() : data(NULL), size(0) { } 31557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~DynArray() { if (data) FREE(data); } 31757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Item& operator[](unsigned int i) 31957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 32057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i >= size) 32157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller resize(i); 32257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data[i]; 32357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline const Item operator[](unsigned int i) const 32657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 32757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data[i]; 32857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void resize(unsigned int index) 33157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 33257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int oldSize = size * sizeof(Item); 33357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!size) 33557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = 8; 33657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (size <= index) 33757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size <<= 1; 33857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data = (Item *)REALLOC(data, oldSize, size * sizeof(Item)); 34057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 34157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 3424a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez void clear() 3434a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez { 3444a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez FREE(data); 3454a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez data = NULL; 3464a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez size = 0; 3474a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez } 3484a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez 34957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 35057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *data; 35157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 35257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 35357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass ArrayList 35557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 35657594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 35757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ArrayList() : size(0) { } 35857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void insert(void *item, int& id) 36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 36157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller id = ids.getSize() ? ids.pop().u.i : size++; 36257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[id].p = item; 36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void remove(int& id) 36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int uid = id; 36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(uid < size && data[id].p); 36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ids.push(uid); 37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[uid].p = NULL; 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller id = -1; 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline int getSize() const { return size; } 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void *get(unsigned int id) { assert(id < size); return data[id].p; } 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Iterator : public nv50_ir::Iterator 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator(const ArrayList *array) : pos(0), data(array->data) 38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = array->getSize(); 38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (size) 38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nextValid(); 38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void nextValid() { while ((pos < size) && !data[pos].p) ++pos; } 38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void next() { if (pos < size) { ++pos; nextValid(); } } 39157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *get() const { assert(pos < size); return data[pos].p; } 39257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool end() const { return pos >= size; } 39357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 39557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int pos; 39657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 39757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const DynArray& data; 39857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller friend class ArrayList; 40057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 40157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 40257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator iterator() const { return Iterator(this); } 40357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 4044a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez void clear() 4054a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez { 4064a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez data.clear(); 4074a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez ids.clear(true); 4084a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez size = 0; 4094a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez } 4104a44f94caf8887f6dfc66c4193e95c6430c9de57Francisco Jerez 41157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 41257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DynArray data; 41357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Stack ids; 41457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 41557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 41657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 41757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Interval 41857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 41957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 42057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Interval() : head(0), tail(0) { } 421e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller Interval(const Interval&); 42257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~Interval(); 42357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 42457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool extend(int, int); 425e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller void insert(const Interval&); 42657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void unify(Interval&); // clears source interval 42757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void clear(); 42857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 429e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int begin() const { return head ? head->bgn : -1; } 430e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int end() const { checkTail(); return tail ? tail->end : -1; } 43157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool isEmpty() const { return !head; } 43257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool overlaps(const Interval&) const; 433e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool contains(int pos) const; 434e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 435e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline int extent() const { return end() - begin(); } 436e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int length() const; 43757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 43857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void print() const; 43957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void checkTail() const; 44157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 44357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Range 44457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 44557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 44657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range(int a, int b) : next(0), bgn(a), end(b) { } 44757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *next; 44957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int bgn; 45057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int end; 45157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void coalesce(Range **ptail) 45357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 45457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *rnn; 45557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (next && end >= next->bgn) { 45757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bgn <= next->bgn); 45857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller rnn = next->next; 45957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller end = MAX2(end, next->end); 46057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete next; 46157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = rnn; 46257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 46357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!next) 46457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller *ptail = this; 46557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 46657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 46757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *head; 46957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *tail; 47057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 47157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass BitSet 47357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 47457594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 47557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet() : marker(false), data(0), size(0) { } 47657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0) 47757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 47857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocate(nBits, zero); 47957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 48057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~BitSet() 48157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 48257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (data) 48357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(data); 48457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 48557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool allocate(unsigned int nBits, bool zero); 487e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller bool resize(unsigned int nBits); // keep old data, zero additional bits 48857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline unsigned int getSize() const { return size; } 49057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 49157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void fill(uint32_t val); 49257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 49357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void setOr(BitSet *, BitSet *); // second BitSet may be NULL 49457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 49557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void set(unsigned int i) 49657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 49757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i < size); 49857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i / 32] |= 1 << (i % 32); 49957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 500e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // NOTE: range may not cross 32 bit boundary (implies n <= 32) 501e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void setRange(unsigned int i, unsigned int n) 502e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 503e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert((i + n) <= size && (((i % 32) + n) <= 32)); 504e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller data[i / 32] |= ((1 << n) - 1) << (i % 32); 505e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 506e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void setMask(unsigned int i, uint32_t m) 507e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 508e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert(i < size); 509e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller data[i / 32] |= m; 510e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 51157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void clr(unsigned int i) 51357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 51457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i < size); 51557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i / 32] &= ~(1 << (i % 32)); 51657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 517e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // NOTE: range may not cross 32 bit boundary (implies n <= 32) 518e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void clrRange(unsigned int i, unsigned int n) 519e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 520e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert((i + n) <= size && (((i % 32) + n) <= 32)); 521e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller data[i / 32] &= ~(((1 << n) - 1) << (i % 32)); 522e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 52357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 52457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool test(unsigned int i) const 52557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 52657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i < size); 52757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data[i / 32] & (1 << (i % 32)); 52857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 529e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // NOTE: range may not cross 32 bit boundary (implies n <= 32) 530e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline bool testRange(unsigned int i, unsigned int n) 531e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 532e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller assert((i + n) <= size && (((i % 32) + n) <= 32)); 533e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller return data[i / 32] & (((1 << n) - 1) << (i % 32)); 534e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 535e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 536e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // Find a range of size (<= 32) clear bits aligned to roundup_pow2(size). 537e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller int findFreeRange(unsigned int size) const; 53857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 53957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet& operator|=(const BitSet&); 54057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet& operator=(const BitSet& set) 54257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 54357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data && set.data); 54457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(size == set.size); 54557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller memcpy(data, set.data, (set.size + 7) / 8); 54657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return *this; 54757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 54857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void andNot(const BitSet&); 55057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 551e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller // bits = (bits | setMask) & ~clrMask 552e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller inline void periodicMask32(uint32_t setMask, uint32_t clrMask) 553e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller { 554e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller for (unsigned int i = 0; i < (size + 31) / 32; ++i) 555e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller data[i] = (data[i] | setMask) & ~clrMask; 556e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller } 557e43a3a66a9d8a99021d76ff4d07dec7b8cfd62caChristoph Bumiller 55857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int popCount() const; 55957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 56057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void print() const; 56157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 56257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 56357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool marker; // for user 56457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 56557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 56657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t *data; 56757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 56857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 56957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Interval::checkTail() const 57157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 57257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#if NV50_DEBUG & NV50_DEBUG_PROG_RA 57357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *r = head; 57457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (r->next) 57557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r = r->next; 57657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(tail == r); 57757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif 57857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 57957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass MemoryPool 58157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 58257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 58357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr) 58457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 58557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int size = sizeof(uint8_t *) * id; 58657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int incr = sizeof(uint8_t *) * nr; 58757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr); 58957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!alloc) 59057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 59157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocArray = alloc; 59257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 59357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 59457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 59557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool enlargeCapacity() 59657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 59757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int id = count >> objStepLog2; 59857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 59957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2); 60057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!mem) 60157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 60257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(id % 32)) { 60457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!enlargeAllocationsArray(id, 32)) { 60557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(mem); 60657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 60757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 60857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 60957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocArray[id] = mem; 61057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 61157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 61257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 61357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 61457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller MemoryPool(unsigned int size, unsigned int incr) : objSize(size), 61557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller objStepLog2(incr) 61657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 61757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocArray = NULL; 61857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller released = NULL; 61957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller count = 0; 62057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 62157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 62257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~MemoryPool() 62357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 62457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2; 62557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i) 62657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(allocArray[i]); 62757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (allocArray) 62857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(allocArray); 62957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 63057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 63157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *allocate() 63257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 63357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *ret; 63457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int mask = (1 << objStepLog2) - 1; 63557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 63657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (released) { 63757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = released; 63857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller released = *(void **)released; 63957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 64057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 64157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 64257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(count & mask)) 64357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!enlargeCapacity()) 64457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return NULL; 64557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 64657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = allocArray[count >> objStepLog2] + (count & mask) * objSize; 64757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++count; 64857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 64957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 65057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 65157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void release(void *ptr) 65257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 65357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller *(void **)ptr = released; 65457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller released = ptr; 65557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 65657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 65757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 65857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t **allocArray; // array (list) of MALLOC allocations 65957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 66057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *released; // list of released objects 66157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 66257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int count; // highest allocated object 66357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 66457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int objSize; 66557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int objStepLog2; 66657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 66757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 668a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/** 669a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Composite object cloning policy. 670a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * 671a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Encapsulates how sub-objects are to be handled (if at all) when a 672a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * composite object is being cloned. 673a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */ 674a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C> 675a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass ClonePolicy 676a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 677a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 678a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez C *c; 679a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 680a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic: 681a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez ClonePolicy(C *c) : c(c) {} 682a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 683a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez C *context() { return c; } 684a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 685a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez template<typename T> T *get(T *obj) 686a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 687a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez void *clone = lookup(obj); 688a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez if (!clone) 689a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez clone = obj->clone(*this); 690a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return reinterpret_cast<T *>(clone); 691a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 692a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 693a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez template<typename T> void set(const T *obj, T *clone) 694a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 695a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez insert(obj, clone); 696a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 697a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 698a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 699a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void *lookup(void *obj) = 0; 700a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void insert(const void *obj, void *clone) = 0; 701a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}; 702a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 703a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/** 704a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Shallow non-recursive cloning policy. 705a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * 706a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Objects cloned with the "shallow" policy don't clone their 707a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * children recursively, instead, the new copy shares its children 708a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * with the original object. 709a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */ 710a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C> 711a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass ShallowClonePolicy : public ClonePolicy<C> 712a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 713a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic: 714a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {} 715a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 716a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 717a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void *lookup(void *obj) 718a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 719a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return obj; 720a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 721a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 722a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void insert(const void *obj, void *clone) 723a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 724a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 725a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}; 726a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 727a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C, typename T> 728a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezinline T *cloneShallow(C *c, T *obj) 729a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 730a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez ShallowClonePolicy<C> pol(c); 731a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return obj->clone(pol); 732a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez} 733a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 734a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/** 735a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Recursive cloning policy. 736a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * 737a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Objects cloned with the "deep" policy clone their children 738a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * recursively, keeping track of what has already been cloned to 739a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * avoid making several new copies of the same object. 740a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */ 741a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C> 742a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass DeepClonePolicy : public ClonePolicy<C> 743a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 744a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic: 745a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez DeepClonePolicy(C *c) : ClonePolicy<C>(c) {} 746a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 747a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprivate: 748a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez std::map<const void *, void *> map; 749a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 750a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 751a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void *lookup(void *obj) 752a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 753a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return map[obj]; 754a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 755a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 756a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void insert(const void *obj, void *clone) 757a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 758a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez map[obj] = clone; 759a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 760a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}; 761a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 76256d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jereztemplate<typename S, typename T> 76356d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerezstruct bimap 76456d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez{ 76556d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez std::map<S, T> forth; 76656d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez std::map<T, S> back; 76756d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez 76856d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerezpublic: 76956d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez bimap() : l(back), r(forth) { } 77056d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez bimap(const bimap<S, T> &m) 77156d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez : forth(m.forth), back(m.back), l(back), r(forth) { } 77256d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez 77356d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez void insert(const S &s, const T &t) 77456d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez { 77556d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez forth.insert(std::make_pair(s, t)); 77656d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez back.insert(std::make_pair(t, s)); 77756d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez } 77856d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez 77956d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez typedef typename std::map<T, S>::const_iterator l_iterator; 78056d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez const std::map<T, S> &l; 78156d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez typedef typename std::map<S, T>::const_iterator r_iterator; 78256d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez const std::map<S, T> &r; 78356d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez}; 78456d40aa51b34b77791cc3a49d7e86473a7459b72Francisco Jerez 78557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 78657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 78757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif // __NV50_IR_UTIL_H__ 788