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