nv50_ir_util.h revision 78de8c8ab54c50c96bc3fae2fe0976054e0acd14
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> 29a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez#include <map> 3078de8c8ab54c50c96bc3fae2fe0976054e0acd14Francisco Jerez#include <memory> 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 14057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#define DLLIST_FOR_EACH(list, it) \ 14157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next()) 14257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 14357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass DLList 14457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 14557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 14657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Item 14757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 14857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 14957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item(void *priv) : next(this), prev(this), data(priv) { } 15057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 15257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *next; 15357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *prev; 15457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *data; 15557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 15657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 15757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLList() : head(0) { } 15857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~DLList() { clear(); } 15957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void insertHead(void *data) 16157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 16257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *item = new Item(data); 16357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data); 16557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 16657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller item->prev = &head; 16757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller item->next = head.next; 16857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller head.next->prev = item; 16957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller head.next = item; 17057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 17157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void insertTail(void *data) 17357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 17457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *item = new Item(data); 17557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data); 17757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 17857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DLLIST_ADDTAIL(&head, item); 17957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 18057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void insert(void *data) { insertTail(data); } 18257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void clear(); 18457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 18557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Iterator : public ManipIterator 18657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 18757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 18857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next), 18957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller term(head) { } 19057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; } 19257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void *get() const { return pos->data; } 19357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool end() const { return pos == term; } 19457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // caution: if you're at end-2 and erase it, then do next, you're at end 19657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual void erase(); 19757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller virtual bool insert(void *data); 19857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 19957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller // move item to a another list, no consistency with its iterators though 20057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void moveToList(DLList&); 20157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 20357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const bool rev; 20457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *pos; 20557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *term; 20657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 20757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller friend class DLList; 20857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 20957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void erase(Iterator& pos) 21157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 21257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller pos.erase(); 21357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 21457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 21557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator iterator() 21657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 21757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return Iterator(&head, false); 21857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 21957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator revIterator() 22157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 22257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return Iterator(&head, true); 22357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 22457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 22657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item head; 22757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 22857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 22957594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Stack 23057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 23157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 23257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Item { 23357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 23457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller union { 23557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *p; 23657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int i; 23757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int u; 23857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller float f; 23957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller double d; 24057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } u; 24157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item() { memset(&u, 0, sizeof(u)); } 24357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 24457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Stack() : size(0), limit(0), array(0) { } 24657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~Stack() { if (array) FREE(array); } 24757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 24857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(int i) { Item data; data.u.i = i; push(data); } 24957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(unsigned int u) { Item data; data.u.u = u; push(data); } 25057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(void *p) { Item data; data.u.p = p; push(data); } 25157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(float f) { Item data; data.u.f = f; push(data); } 25257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 25357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void push(Item data) 25457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 25557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (size == limit) 25657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller resize(); 25757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller array[size++] = data; 25857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 25957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 26057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Item pop() 26157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 26257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!size) { 26357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item data; 26457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(0); 26557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data; 26657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 26757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return array[--size]; 26857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 26957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline unsigned int getSize() { return size; } 27157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Item& peek() { assert(size); return array[size - 1]; } 27357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 27457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void clear(bool releaseStorage = false) 27557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 27657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (releaseStorage && array) 27757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(array); 27857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = limit = 0; 27957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 28057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void moveTo(Stack&); // move all items to target (not like push(pop())) 28257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 28457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void resize() 28557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 28657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int sizeOld, sizeNew; 28757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 28857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sizeOld = limit * sizeof(Item); 28957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller limit = MAX2(4, limit + limit); 29057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller sizeNew = limit * sizeof(Item); 29157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller array = (Item *)REALLOC(array, sizeOld, sizeNew); 29357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 29457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 29557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 29657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int limit; 29757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *array; 29857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 29957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 30057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass DynArray 30157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 30257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 30357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Item 30457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 30557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 30657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller union { 30757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t u32; 30857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *p; 30957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 31057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 31157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DynArray() : data(NULL), size(0) { } 31357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~DynArray() { if (data) FREE(data); } 31557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 31657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline Item& operator[](unsigned int i) 31757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 31857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (i >= size) 31957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller resize(i); 32057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data[i]; 32157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline const Item operator[](unsigned int i) const 32457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 32557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data[i]; 32657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 32757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 32857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void resize(unsigned int index) 32957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 33057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int oldSize = size * sizeof(Item); 33157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!size) 33357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = 8; 33457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (size <= index) 33557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size <<= 1; 33657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 33757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data = (Item *)REALLOC(data, oldSize, size * sizeof(Item)); 33857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 33957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 34057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 34157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Item *data; 34257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 34357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 34457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 34557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass ArrayList 34657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 34757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 34857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ArrayList() : size(0) { } 34957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void insert(void *item, int& id) 35157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 35257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller id = ids.getSize() ? ids.pop().u.i : size++; 35357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[id].p = item; 35457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 35557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 35657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void remove(int& id) 35757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 35857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int uid = id; 35957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(uid < size && data[id].p); 36057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ids.push(uid); 36157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[uid].p = NULL; 36257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller id = -1; 36357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 36457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline int getSize() const { return size; } 36657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void *get(unsigned int id) { assert(id < size); return data[id].p; } 36857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 36957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Iterator : public nv50_ir::Iterator 37057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 37157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 37257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator(const ArrayList *array) : pos(0), data(array->data) 37357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 37457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller size = array->getSize(); 37557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (size) 37657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller nextValid(); 37757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 37857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 37957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void nextValid() { while ((pos < size) && !data[pos].p) ++pos; } 38057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void next() { if (pos < size) { ++pos; nextValid(); } } 38257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *get() const { assert(pos < size); return data[pos].p; } 38357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool end() const { return pos >= size; } 38457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 38557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller private: 38657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int pos; 38757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 38857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const DynArray& data; 38957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller friend class ArrayList; 39157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 39257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Iterator iterator() const { return Iterator(this); } 39457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 39557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 39657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller DynArray data; 39757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Stack ids; 39857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 39957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 40057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 40157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass Interval 40257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 40357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 40457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Interval() : head(0), tail(0) { } 40557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~Interval(); 40657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 40757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool extend(int, int); 40857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void unify(Interval&); // clears source interval 40957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void clear(); 41057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 41157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline int begin() { return head ? head->bgn : -1; } 41257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline int end() { checkTail(); return tail ? tail->end : -1; } 41357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool isEmpty() const { return !head; } 41457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool overlaps(const Interval&) const; 41557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool contains(int pos); 41657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 41757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void print() const; 41857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 41957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void checkTail() const; 42057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 42157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 42257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller class Range 42357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 42457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller public: 42557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range(int a, int b) : next(0), bgn(a), end(b) { } 42657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 42757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *next; 42857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int bgn; 42957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller int end; 43057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 43157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void coalesce(Range **ptail) 43257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 43357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *rnn; 43457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 43557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (next && end >= next->bgn) { 43657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(bgn <= next->bgn); 43757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller rnn = next->next; 43857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller end = MAX2(end, next->end); 43957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller delete next; 44057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller next = rnn; 44157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 44257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!next) 44357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller *ptail = this; 44457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 44557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller }; 44657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 44757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *head; 44857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *tail; 44957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 45057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 45157594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass BitSet 45257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 45357594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 45457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet() : marker(false), data(0), size(0) { } 45557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0) 45657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 45757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocate(nBits, zero); 45857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 45957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~BitSet() 46057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 46157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (data) 46257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(data); 46357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 46457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool allocate(unsigned int nBits, bool zero); 46657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline unsigned int getSize() const { return size; } 46857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 46957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void fill(uint32_t val); 47057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void setOr(BitSet *, BitSet *); // second BitSet may be NULL 47257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void set(unsigned int i) 47457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 47557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i < size); 47657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i / 32] |= 1 << (i % 32); 47757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 47857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 47957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline void clr(unsigned int i) 48057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 48157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i < size); 48257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller data[i / 32] &= ~(1 << (i % 32)); 48357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 48457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 48557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool test(unsigned int i) const 48657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 48757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(i < size); 48857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return data[i / 32] & (1 << (i % 32)); 48957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 49057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 49157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet& operator|=(const BitSet&); 49257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 49357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller BitSet& operator=(const BitSet& set) 49457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 49557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(data && set.data); 49657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(size == set.size); 49757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller memcpy(data, set.data, (set.size + 7) / 8); 49857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return *this; 49957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 50057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void andNot(const BitSet&); 50257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int popCount() const; 50457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void print() const; 50657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 50757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 50857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller bool marker; // for user 50957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51057594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 51157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint32_t *data; 51257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int size; 51357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 51457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 51557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillervoid Interval::checkTail() const 51657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 51757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#if NV50_DEBUG & NV50_DEBUG_PROG_RA 51857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller Range *r = head; 51957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller while (r->next) 52057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller r = r->next; 52157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller assert(tail == r); 52257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif 52357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} 52457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 52557594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerclass MemoryPool 52657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller{ 52757594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 52857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr) 52957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 53057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int size = sizeof(uint8_t *) * id; 53157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int incr = sizeof(uint8_t *) * nr; 53257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 53357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr); 53457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!alloc) 53557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 53657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocArray = alloc; 53757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 53857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 53957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller inline bool enlargeCapacity() 54157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 54257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int id = count >> objStepLog2; 54357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2); 54557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!mem) 54657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 54757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 54857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(id % 32)) { 54957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!enlargeAllocationsArray(id, 32)) { 55057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(mem); 55157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return false; 55257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 55357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 55457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocArray[id] = mem; 55557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return true; 55657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 55757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 55857594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerpublic: 55957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller MemoryPool(unsigned int size, unsigned int incr) : objSize(size), 56057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller objStepLog2(incr) 56157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 56257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller allocArray = NULL; 56357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller released = NULL; 56457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller count = 0; 56557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 56657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 56757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ~MemoryPool() 56857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 56957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2; 57057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i) 57157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(allocArray[i]); 57257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (allocArray) 57357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller FREE(allocArray); 57457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 57557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 57657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *allocate() 57757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 57857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *ret; 57957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int mask = (1 << objStepLog2) - 1; 58057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (released) { 58257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = released; 58357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller released = *(void **)released; 58457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 58557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 58657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 58757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!(count & mask)) 58857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller if (!enlargeCapacity()) 58957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return NULL; 59057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 59157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ret = allocArray[count >> objStepLog2] + (count & mask) * objSize; 59257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller ++count; 59357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller return ret; 59457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 59557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 59657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void release(void *ptr) 59757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller { 59857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller *(void **)ptr = released; 59957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller released = ptr; 60057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller } 60157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60257594065c30feec9376be9b2132659f7d87362eeChristoph Bumillerprivate: 60357594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller uint8_t **allocArray; // array (list) of MALLOC allocations 60457594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60557594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller void *released; // list of released objects 60657594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller unsigned int count; // highest allocated object 60857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 60957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int objSize; 61057594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller const unsigned int objStepLog2; 61157594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller}; 61257594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 613a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/** 614a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Composite object cloning policy. 615a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * 616a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Encapsulates how sub-objects are to be handled (if at all) when a 617a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * composite object is being cloned. 618a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */ 619a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C> 620a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass ClonePolicy 621a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 622a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 623a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez C *c; 624a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 625a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic: 626a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez ClonePolicy(C *c) : c(c) {} 627a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 628a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez C *context() { return c; } 629a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 630a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez template<typename T> T *get(T *obj) 631a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 632a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez void *clone = lookup(obj); 633a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez if (!clone) 634a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez clone = obj->clone(*this); 635a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return reinterpret_cast<T *>(clone); 636a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 637a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 638a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez template<typename T> void set(const T *obj, T *clone) 639a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 640a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez insert(obj, clone); 641a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 642a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 643a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 644a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void *lookup(void *obj) = 0; 645a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void insert(const void *obj, void *clone) = 0; 646a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}; 647a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 648a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/** 649a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Shallow non-recursive cloning policy. 650a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * 651a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Objects cloned with the "shallow" policy don't clone their 652a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * children recursively, instead, the new copy shares its children 653a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * with the original object. 654a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */ 655a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C> 656a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass ShallowClonePolicy : public ClonePolicy<C> 657a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 658a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic: 659a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {} 660a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 661a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 662a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void *lookup(void *obj) 663a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 664a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return obj; 665a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 666a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 667a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void insert(const void *obj, void *clone) 668a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 669a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 670a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}; 671a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 672a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C, typename T> 673a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezinline T *cloneShallow(C *c, T *obj) 674a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 675a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez ShallowClonePolicy<C> pol(c); 676a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return obj->clone(pol); 677a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez} 678a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 679a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez/** 680a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Recursive cloning policy. 681a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * 682a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * Objects cloned with the "deep" policy clone their children 683a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * recursively, keeping track of what has already been cloned to 684a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez * avoid making several new copies of the same object. 685a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez */ 686a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jereztemplate<typename C> 687a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezclass DeepClonePolicy : public ClonePolicy<C> 688a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez{ 689a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezpublic: 690a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez DeepClonePolicy(C *c) : ClonePolicy<C>(c) {} 691a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 692a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprivate: 693a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez std::map<const void *, void *> map; 694a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 695a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerezprotected: 696a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void *lookup(void *obj) 697a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 698a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez return map[obj]; 699a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 700a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 701a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez virtual void insert(const void *obj, void *clone) 702a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez { 703a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez map[obj] = clone; 704a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez } 705a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez}; 706a05e6a3fa28168d58a13cfb07f7a664e84b925aeFrancisco Jerez 70757594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller} // namespace nv50_ir 70857594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller 70957594065c30feec9376be9b2132659f7d87362eeChristoph Bumiller#endif // __NV50_IR_UTIL_H__ 710