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