nv50_ir_util.h revision 4a44f94caf8887f6dfc66c4193e95c6430c9de57
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright 2011 Christoph Bumiller 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Permission is hereby granted, free of charge, to any person obtaining a 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * copy of this software and associated documentation files (the "Software"), 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * to deal in the Software without restriction, including without limitation 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * the rights to use, copy, modify, merge, publish, distribute, sublicense, 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * and/or sell copies of the Software, and to permit persons to whom the 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Software is furnished to do so, subject to the following conditions: 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * The above copyright notice and this permission notice shall be included in 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * all copies or substantial portions of the Software. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * SOFTWARE. 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef __NV50_IR_UTIL_H__ 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define __NV50_IR_UTIL_H__ 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <new> 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <assert.h> 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h> 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <memory> 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map> 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef NDEBUG 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# include <typeinfo> 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/u_inlines.h" 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/u_memory.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ERROR(args...) debug_printf("ERROR: " args) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define WARN(args...) debug_printf("WARNING: " args) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define INFO(args...) debug_printf(args) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define INFO_DBG(m, f, args...) \ 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { \ 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (m & NV50_IR_DEBUG_##f) \ 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) debug_printf(args); \ 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while(0) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define FATAL(args...) \ 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { \ 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(stderr, args); \ 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) abort(); \ 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while(0) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...) \ 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_Instruction(f, args...) \ 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_CmpInstruction(f, args...) \ 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_TexInstruction(f, args...) \ 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_FlowInstruction(f, args...) \ 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_LValue(f, args...) \ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...) \ 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new ((p)->mem_##obj.allocate()) obj(p, args) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_Symbol(p, args...) \ 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define new_ImmediateValue(p, args...) \ 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define delete_Instruction(p, insn) (p)->releaseInstruction(insn) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define delete_Value(p, val) (p)->releaseValue(val) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace nv50_ir { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Iterator 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~Iterator() { }; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void next() = 0; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void *get() const = 0; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool end() const = 0; // if true, get will return 0 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef std::auto_ptr<Iterator> IteratorRef; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class ManipIterator : public Iterator 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool insert(void *) = 0; // insert after current position 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void erase() = 0; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// WARNING: do not use a->prev/next for __item or __list 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DLLIST_DEL(__item) \ 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { \ 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->prev->next = (__item)->next; \ 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->next->prev = (__item)->prev; \ 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->next = (__item); \ 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->prev = (__item); \ 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while(0) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DLLIST_ADDTAIL(__list, __item) \ 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { \ 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->next = (__list); \ 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->prev = (__list)->prev; \ 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__list)->prev->next = (__item); \ 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__list)->prev = (__item); \ 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while(0) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DLLIST_ADDHEAD(__list, __item) \ 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { \ 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->prev = (__list); \ 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__item)->next = (__list)->next; \ 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__list)->next->prev = (__item); \ 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__list)->next = (__item); \ 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while(0) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DLLIST_MERGE(__listA, __listB, ty) \ 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) do { \ 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ty prevB = (__listB)->prev; \ 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__listA)->prev->next = (__listB); \ 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__listB)->prev->next = (__listA); \ 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__listB)->prev = (__listA)->prev; \ 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (__listA)->prev = prevB; \ 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } while(0) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DLLIST_FOR_EACH(list, it) \ 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next()) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class DLList 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class Item 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Item(void *priv) : next(this), prev(this), data(priv) { } 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Item *next; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Item *prev; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *data; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 157 DLList() : head(0) { } 158 ~DLList() { clear(); } 159 160 inline void insertHead(void *data) 161 { 162 Item *item = new Item(data); 163 164 assert(data); 165 166 item->prev = &head; 167 item->next = head.next; 168 head.next->prev = item; 169 head.next = item; 170 } 171 172 inline void insertTail(void *data) 173 { 174 Item *item = new Item(data); 175 176 assert(data); 177 178 DLLIST_ADDTAIL(&head, item); 179 } 180 181 inline void insert(void *data) { insertTail(data); } 182 183 void clear(); 184 185 class Iterator : public ManipIterator 186 { 187 public: 188 Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next), 189 term(head) { } 190 191 virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; } 192 virtual void *get() const { return pos->data; } 193 virtual bool end() const { return pos == term; } 194 195 // caution: if you're at end-2 and erase it, then do next, you're at end 196 virtual void erase(); 197 virtual bool insert(void *data); 198 199 // move item to a another list, no consistency with its iterators though 200 void moveToList(DLList&); 201 202 private: 203 const bool rev; 204 Item *pos; 205 Item *term; 206 207 friend class DLList; 208 }; 209 210 inline void erase(Iterator& pos) 211 { 212 pos.erase(); 213 } 214 215 Iterator iterator() 216 { 217 return Iterator(&head, false); 218 } 219 220 Iterator revIterator() 221 { 222 return Iterator(&head, true); 223 } 224 225private: 226 Item head; 227}; 228 229class Stack 230{ 231public: 232 class Item { 233 public: 234 union { 235 void *p; 236 int i; 237 unsigned int u; 238 float f; 239 double d; 240 } u; 241 242 Item() { memset(&u, 0, sizeof(u)); } 243 }; 244 245 Stack() : size(0), limit(0), array(0) { } 246 ~Stack() { if (array) FREE(array); } 247 248 inline void push(int i) { Item data; data.u.i = i; push(data); } 249 inline void push(unsigned int u) { Item data; data.u.u = u; push(data); } 250 inline void push(void *p) { Item data; data.u.p = p; push(data); } 251 inline void push(float f) { Item data; data.u.f = f; push(data); } 252 253 inline void push(Item data) 254 { 255 if (size == limit) 256 resize(); 257 array[size++] = data; 258 } 259 260 inline Item pop() 261 { 262 if (!size) { 263 Item data; 264 assert(0); 265 return data; 266 } 267 return array[--size]; 268 } 269 270 inline unsigned int getSize() { return size; } 271 272 inline Item& peek() { assert(size); return array[size - 1]; } 273 274 void clear(bool releaseStorage = false) 275 { 276 if (releaseStorage && array) 277 FREE(array); 278 size = limit = 0; 279 } 280 281 void moveTo(Stack&); // move all items to target (not like push(pop())) 282 283private: 284 void resize() 285 { 286 unsigned int sizeOld, sizeNew; 287 288 sizeOld = limit * sizeof(Item); 289 limit = MAX2(4, limit + limit); 290 sizeNew = limit * sizeof(Item); 291 292 array = (Item *)REALLOC(array, sizeOld, sizeNew); 293 } 294 295 unsigned int size; 296 unsigned int limit; 297 Item *array; 298}; 299 300class DynArray 301{ 302public: 303 class Item 304 { 305 public: 306 union { 307 uint32_t u32; 308 void *p; 309 }; 310 }; 311 312 DynArray() : data(NULL), size(0) { } 313 314 ~DynArray() { if (data) FREE(data); } 315 316 inline Item& operator[](unsigned int i) 317 { 318 if (i >= size) 319 resize(i); 320 return data[i]; 321 } 322 323 inline const Item operator[](unsigned int i) const 324 { 325 return data[i]; 326 } 327 328 void resize(unsigned int index) 329 { 330 const unsigned int oldSize = size * sizeof(Item); 331 332 if (!size) 333 size = 8; 334 while (size <= index) 335 size <<= 1; 336 337 data = (Item *)REALLOC(data, oldSize, size * sizeof(Item)); 338 } 339 340 void clear() 341 { 342 FREE(data); 343 data = NULL; 344 size = 0; 345 } 346 347private: 348 Item *data; 349 unsigned int size; 350}; 351 352class ArrayList 353{ 354public: 355 ArrayList() : size(0) { } 356 357 void insert(void *item, int& id) 358 { 359 id = ids.getSize() ? ids.pop().u.i : size++; 360 data[id].p = item; 361 } 362 363 void remove(int& id) 364 { 365 const unsigned int uid = id; 366 assert(uid < size && data[id].p); 367 ids.push(uid); 368 data[uid].p = NULL; 369 id = -1; 370 } 371 372 inline int getSize() const { return size; } 373 374 inline void *get(unsigned int id) { assert(id < size); return data[id].p; } 375 376 class Iterator : public nv50_ir::Iterator 377 { 378 public: 379 Iterator(const ArrayList *array) : pos(0), data(array->data) 380 { 381 size = array->getSize(); 382 if (size) 383 nextValid(); 384 } 385 386 void nextValid() { while ((pos < size) && !data[pos].p) ++pos; } 387 388 void next() { if (pos < size) { ++pos; nextValid(); } } 389 void *get() const { assert(pos < size); return data[pos].p; } 390 bool end() const { return pos >= size; } 391 392 private: 393 unsigned int pos; 394 unsigned int size; 395 const DynArray& data; 396 397 friend class ArrayList; 398 }; 399 400 Iterator iterator() const { return Iterator(this); } 401 402 void clear() 403 { 404 data.clear(); 405 ids.clear(true); 406 size = 0; 407 } 408 409private: 410 DynArray data; 411 Stack ids; 412 unsigned int size; 413}; 414 415class Interval 416{ 417public: 418 Interval() : head(0), tail(0) { } 419 ~Interval(); 420 421 bool extend(int, int); 422 void unify(Interval&); // clears source interval 423 void clear(); 424 425 inline int begin() { return head ? head->bgn : -1; } 426 inline int end() { checkTail(); return tail ? tail->end : -1; } 427 inline bool isEmpty() const { return !head; } 428 bool overlaps(const Interval&) const; 429 bool contains(int pos); 430 431 void print() const; 432 433 inline void checkTail() const; 434 435private: 436 class Range 437 { 438 public: 439 Range(int a, int b) : next(0), bgn(a), end(b) { } 440 441 Range *next; 442 int bgn; 443 int end; 444 445 void coalesce(Range **ptail) 446 { 447 Range *rnn; 448 449 while (next && end >= next->bgn) { 450 assert(bgn <= next->bgn); 451 rnn = next->next; 452 end = MAX2(end, next->end); 453 delete next; 454 next = rnn; 455 } 456 if (!next) 457 *ptail = this; 458 } 459 }; 460 461 Range *head; 462 Range *tail; 463}; 464 465class BitSet 466{ 467public: 468 BitSet() : marker(false), data(0), size(0) { } 469 BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0) 470 { 471 allocate(nBits, zero); 472 } 473 ~BitSet() 474 { 475 if (data) 476 FREE(data); 477 } 478 479 bool allocate(unsigned int nBits, bool zero); 480 481 inline unsigned int getSize() const { return size; } 482 483 void fill(uint32_t val); 484 485 void setOr(BitSet *, BitSet *); // second BitSet may be NULL 486 487 inline void set(unsigned int i) 488 { 489 assert(i < size); 490 data[i / 32] |= 1 << (i % 32); 491 } 492 493 inline void clr(unsigned int i) 494 { 495 assert(i < size); 496 data[i / 32] &= ~(1 << (i % 32)); 497 } 498 499 inline bool test(unsigned int i) const 500 { 501 assert(i < size); 502 return data[i / 32] & (1 << (i % 32)); 503 } 504 505 BitSet& operator|=(const BitSet&); 506 507 BitSet& operator=(const BitSet& set) 508 { 509 assert(data && set.data); 510 assert(size == set.size); 511 memcpy(data, set.data, (set.size + 7) / 8); 512 return *this; 513 } 514 515 void andNot(const BitSet&); 516 517 unsigned int popCount() const; 518 519 void print() const; 520 521public: 522 bool marker; // for user 523 524private: 525 uint32_t *data; 526 unsigned int size; 527}; 528 529void Interval::checkTail() const 530{ 531#if NV50_DEBUG & NV50_DEBUG_PROG_RA 532 Range *r = head; 533 while (r->next) 534 r = r->next; 535 assert(tail == r); 536#endif 537} 538 539class MemoryPool 540{ 541private: 542 inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr) 543 { 544 const unsigned int size = sizeof(uint8_t *) * id; 545 const unsigned int incr = sizeof(uint8_t *) * nr; 546 547 uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr); 548 if (!alloc) 549 return false; 550 allocArray = alloc; 551 return true; 552 } 553 554 inline bool enlargeCapacity() 555 { 556 const unsigned int id = count >> objStepLog2; 557 558 uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2); 559 if (!mem) 560 return false; 561 562 if (!(id % 32)) { 563 if (!enlargeAllocationsArray(id, 32)) { 564 FREE(mem); 565 return false; 566 } 567 } 568 allocArray[id] = mem; 569 return true; 570 } 571 572public: 573 MemoryPool(unsigned int size, unsigned int incr) : objSize(size), 574 objStepLog2(incr) 575 { 576 allocArray = NULL; 577 released = NULL; 578 count = 0; 579 } 580 581 ~MemoryPool() 582 { 583 unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2; 584 for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i) 585 FREE(allocArray[i]); 586 if (allocArray) 587 FREE(allocArray); 588 } 589 590 void *allocate() 591 { 592 void *ret; 593 const unsigned int mask = (1 << objStepLog2) - 1; 594 595 if (released) { 596 ret = released; 597 released = *(void **)released; 598 return ret; 599 } 600 601 if (!(count & mask)) 602 if (!enlargeCapacity()) 603 return NULL; 604 605 ret = allocArray[count >> objStepLog2] + (count & mask) * objSize; 606 ++count; 607 return ret; 608 } 609 610 void release(void *ptr) 611 { 612 *(void **)ptr = released; 613 released = ptr; 614 } 615 616private: 617 uint8_t **allocArray; // array (list) of MALLOC allocations 618 619 void *released; // list of released objects 620 621 unsigned int count; // highest allocated object 622 623 const unsigned int objSize; 624 const unsigned int objStepLog2; 625}; 626 627/** 628 * Composite object cloning policy. 629 * 630 * Encapsulates how sub-objects are to be handled (if at all) when a 631 * composite object is being cloned. 632 */ 633template<typename C> 634class ClonePolicy 635{ 636protected: 637 C *c; 638 639public: 640 ClonePolicy(C *c) : c(c) {} 641 642 C *context() { return c; } 643 644 template<typename T> T *get(T *obj) 645 { 646 void *clone = lookup(obj); 647 if (!clone) 648 clone = obj->clone(*this); 649 return reinterpret_cast<T *>(clone); 650 } 651 652 template<typename T> void set(const T *obj, T *clone) 653 { 654 insert(obj, clone); 655 } 656 657protected: 658 virtual void *lookup(void *obj) = 0; 659 virtual void insert(const void *obj, void *clone) = 0; 660}; 661 662/** 663 * Shallow non-recursive cloning policy. 664 * 665 * Objects cloned with the "shallow" policy don't clone their 666 * children recursively, instead, the new copy shares its children 667 * with the original object. 668 */ 669template<typename C> 670class ShallowClonePolicy : public ClonePolicy<C> 671{ 672public: 673 ShallowClonePolicy(C *c) : ClonePolicy<C>(c) {} 674 675protected: 676 virtual void *lookup(void *obj) 677 { 678 return obj; 679 } 680 681 virtual void insert(const void *obj, void *clone) 682 { 683 } 684}; 685 686template<typename C, typename T> 687inline T *cloneShallow(C *c, T *obj) 688{ 689 ShallowClonePolicy<C> pol(c); 690 return obj->clone(pol); 691} 692 693/** 694 * Recursive cloning policy. 695 * 696 * Objects cloned with the "deep" policy clone their children 697 * recursively, keeping track of what has already been cloned to 698 * avoid making several new copies of the same object. 699 */ 700template<typename C> 701class DeepClonePolicy : public ClonePolicy<C> 702{ 703public: 704 DeepClonePolicy(C *c) : ClonePolicy<C>(c) {} 705 706private: 707 std::map<const void *, void *> map; 708 709protected: 710 virtual void *lookup(void *obj) 711 { 712 return map[obj]; 713 } 714 715 virtual void insert(const void *obj, void *clone) 716 { 717 map[obj] = clone; 718 } 719}; 720 721template<typename S, typename T> 722struct bimap 723{ 724 std::map<S, T> forth; 725 std::map<T, S> back; 726 727public: 728 bimap() : l(back), r(forth) { } 729 bimap(const bimap<S, T> &m) 730 : forth(m.forth), back(m.back), l(back), r(forth) { } 731 732 void insert(const S &s, const T &t) 733 { 734 forth.insert(std::make_pair(s, t)); 735 back.insert(std::make_pair(t, s)); 736 } 737 738 typedef typename std::map<T, S>::const_iterator l_iterator; 739 const std::map<T, S> &l; 740 typedef typename std::map<S, T>::const_iterator r_iterator; 741 const std::map<S, T> &r; 742}; 743 744} // namespace nv50_ir 745 746#endif // __NV50_IR_UTIL_H__ 747