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