src/gallium/drivers/nv50/codegen/nv50_ir_util.h

   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
  30 #include "util/u_inlines.h"
  31 #include "util/u_memory.h"
  32
  33 #define ERROR(args...) debug_printf("ERROR: " args)
  34 #define WARN(args...) debug_printf("WARNING: " args)
  35 #define INFO(args...) debug_printf(args)
  36
  37 #define INFO_DBG(m, f, args...)          \
  38    do {                                  \
  39       if (m & NV50_IR_DEBUG_##f)         \
  40          debug_printf(args);             \
  41    } while(0)
  42
  43 #define FATAL(args...)          \
  44    do {                         \
  45       fprintf(stderr, args);    \
  46       abort();                  \
  47    } while(0)
  48
  49
  50 #define NV50_IR_FUNC_ALLOC_OBJ_DEF(obj, f, args...)               \
  51    new ((f)->getProgram()->mem_##obj.allocate()) obj(f, args)
  52
  53 #define new_Instruction(f, args...)                      \
  54    NV50_IR_FUNC_ALLOC_OBJ_DEF(Instruction, f, args)
  55 #define new_CmpInstruction(f, args...)                   \
  56    NV50_IR_FUNC_ALLOC_OBJ_DEF(CmpInstruction, f, args)
  57 #define new_TexInstruction(f, args...)                   \
  58    NV50_IR_FUNC_ALLOC_OBJ_DEF(TexInstruction, f, args)
  59 #define new_FlowInstruction(f, args...)                  \
  60    NV50_IR_FUNC_ALLOC_OBJ_DEF(FlowInstruction, f, args)
  61
  62 #define new_LValue(f, args...)                  \
  63    NV50_IR_FUNC_ALLOC_OBJ_DEF(LValue, f, args)
  64
  65
  66 #define NV50_IR_PROG_ALLOC_OBJ_DEF(obj, p, args...)   \
  67    new ((p)->mem_##obj.allocate()) obj(p, args)
  68
  69 #define new_Symbol(p, args...)                           \
  70    NV50_IR_PROG_ALLOC_OBJ_DEF(Symbol, p, args)
  71 #define new_ImmediateValue(p, args...)                   \
  72    NV50_IR_PROG_ALLOC_OBJ_DEF(ImmediateValue, p, args)
  73
  74
  75 #define delete_Instruction(p, insn) (p)->releaseInstruction(insn)
  76 #define delete_Value(p, val) (p)->releaseValue(val)
  77
  78
  79 namespace nv50_ir {
  80
  81 class Iterator
  82 {
  83 public:
  84    virtual void next() = 0;
  85    virtual void *get() const = 0;
  86    virtual bool end() const = 0; // if true, get will return 0
  87 };
  88
  89 class ManipIterator : public Iterator
  90 {
  91 public:
  92    virtual bool insert(void *) = 0; // insert after current position
  93    virtual void erase() = 0;
  94 };
  95
  96 // WARNING: do not use a->prev/next for __item or __list
  97
  98 #define DLLIST_DEL(__item)                      \
  99    do {                                         \
 100       (__item)->prev->next = (__item)->next;    \
 101       (__item)->next->prev = (__item)->prev;    \
 102       (__item)->next = (__item);                \
 103       (__item)->prev = (__item);                \
 104    } while(0)
 105
 106 #define DLLIST_ADDTAIL(__list, __item)          \
 107    do {                                         \
 108       (__item)->next = (__list);                \
 109       (__item)->prev = (__list)->prev;          \
 110       (__list)->prev->next = (__item);          \
 111       (__list)->prev = (__item);                \
 112    } while(0)
 113
 114 #define DLLIST_ADDHEAD(__list, __item)          \
 115    do {                                         \
 116       (__item)->prev = (__list);                \
 117       (__item)->next = (__list)->next;          \
 118       (__list)->next->prev = (__item);          \
 119       (__list)->next = (__item);                \
 120    } while(0)
 121
 122 #define DLLIST_MERGE(__listA, __listB, ty)      \
 123    do {                                         \
 124       ty prevB = (__listB)->prev;               \
 125       (__listA)->prev->next = (__listB);        \
 126       (__listB)->prev->next = (__listA);        \
 127       (__listB)->prev = (__listA)->prev;        \
 128       (__listA)->prev = prevB;                  \
 129    } while(0)
 130
 131 #define DLLIST_FOR_EACH(list, it) \
 132    for (DLList::Iterator (it) = (list)->iterator(); !(it).end(); (it).next())
 133
 134 class DLList
 135 {
 136 public:
 137    class Item
 138    {
 139    public:
 140       Item(void *priv) : next(this), prev(this), data(priv) { }
 141
 142    public:
 143       Item *next;
 144       Item *prev;
 145       void *data;
 146    };
 147
 148    DLList() : head(0) { }
 149    ~DLList() { clear(); }
 150
 151    inline void insertHead(void *data)
 152    {
 153       Item *item = new Item(data);
 154
 155       assert(data);
 156
 157       item->prev = &head;
 158       item->next = head.next;
 159       head.next->prev = item;
 160       head.next = item;
 161    }
 162
 163    inline void insertTail(void *data)
 164    {
 165       Item *item = new Item(data);
 166
 167       assert(data);
 168
 169       DLLIST_ADDTAIL(&head, item);
 170    }
 171
 172    inline void insert(void *data) { insertTail(data); }
 173
 174    void clear();
 175
 176    class Iterator : public ManipIterator
 177    {
 178    public:
 179       Iterator(Item *head, bool r) : rev(r), pos(r ? head->prev : head->next),
 180                                      term(head) { }
 181
 182       virtual void next() { if (!end()) pos = rev ? pos->prev : pos->next; }
 183       virtual void *get() const { return pos->data; }
 184       virtual bool end() const { return pos == term; }
 185
 186       // caution: if you're at end-2 and erase it, then do next, you're at end
 187       virtual void erase();
 188       virtual bool insert(void *data);
 189
 190       // move item to a another list, no consistency with its iterators though
 191       void moveToList(DLList&);
 192
 193    private:
 194       const bool rev;
 195       Item *pos;
 196       Item *term;
 197
 198       friend class DLList;
 199    };
 200
 201    inline void erase(Iterator& pos)
 202    {
 203       pos.erase();
 204    }
 205
 206    Iterator iterator()
 207    {
 208       return Iterator(&head, false);
 209    }
 210
 211    Iterator revIterator()
 212    {
 213       return Iterator(&head, true);
 214    }
 215
 216 private:
 217    Item head;
 218 };
 219
 220 class Stack
 221 {
 222 public:
 223    class Item {
 224    public:
 225       union {
 226          void *p;
 227          int i;
 228          unsigned int u;
 229          float f;
 230          double d;
 231       } u;
 232
 233       Item() { memset(&u, 0, sizeof(u)); }
 234    };
 235
 236    Stack() : size(0), limit(0), array(0) { }
 237    ~Stack() { if (array) FREE(array); }
 238
 239    inline void push(int i)          { Item data; data.u.i = i; push(data); }
 240    inline void push(unsigned int u) { Item data; data.u.u = u; push(data); }
 241    inline void push(void *p)        { Item data; data.u.p = p; push(data); }
 242    inline void push(float f)        { Item data; data.u.f = f; push(data); }
 243
 244    inline void push(Item data)
 245    {
 246       if (size == limit)
 247          resize();
 248       array[size++] = data;
 249    }
 250
 251    inline Item pop()
 252    {
 253       if (!size) {
 254          Item data;
 255          assert(0);
 256          return data;
 257       }
 258       return array[--size];
 259    }
 260
 261    inline unsigned int getSize() { return size; }
 262
 263    inline Item& peek() { assert(size); return array[size - 1]; }
 264
 265    void clear(bool releaseStorage = false)
 266    {
 267       if (releaseStorage && array)
 268          FREE(array);
 269       size = limit = 0;
 270    }
 271
 272    void moveTo(Stack&); // move all items to target (not like push(pop()))
 273
 274 private:
 275    void resize()
 276    {
 277          unsigned int sizeOld, sizeNew;
 278
 279          sizeOld = limit * sizeof(Item);
 280          limit = MAX2(4, limit + limit);
 281          sizeNew = limit * sizeof(Item);
 282
 283          array = (Item *)REALLOC(array, sizeOld, sizeNew);
 284    }
 285
 286    unsigned int size;
 287    unsigned int limit;
 288    Item *array;
 289 };
 290
 291 class DynArray
 292 {
 293 public:
 294    class Item
 295    {
 296    public:
 297       union {
 298          uint32_t u32;
 299          void *p;
 300       };
 301    };
 302
 303    DynArray() : data(NULL), size(0) { }
 304
 305    ~DynArray() { if (data) FREE(data); }
 306
 307    inline Item& operator[](unsigned int i)
 308    {
 309       if (i >= size)
 310          resize(i);
 311       return data[i];
 312    }
 313
 314    inline const Item operator[](unsigned int i) const
 315    {
 316       return data[i];
 317    }
 318
 319    void resize(unsigned int index)
 320    {
 321       const unsigned int oldSize = size * sizeof(Item);
 322
 323       if (!size)
 324          size = 8;
 325       while (size <= index)
 326          size <<= 1;
 327
 328       data = (Item *)REALLOC(data, oldSize, size * sizeof(Item));
 329    }
 330
 331 private:
 332    Item *data;
 333    unsigned int size;
 334 };
 335
 336 class ArrayList
 337 {
 338 public:
 339    ArrayList() : size(0) { }
 340
 341    void insert(void *item, int& id)
 342    {
 343       id = ids.getSize() ? ids.pop().u.i : size++;
 344       data[id].p = item;
 345    }
 346
 347    void remove(int& id)
 348    {
 349       const unsigned int uid = id;
 350       assert(uid < size && data[id].p);
 351       ids.push(uid);
 352       data[uid].p = NULL;
 353       id = -1;
 354    }
 355
 356    inline int getSize() const { return size; }
 357
 358    inline void *get(unsigned int id) { assert(id < size); return data[id].p; }
 359
 360    class Iterator : public nv50_ir::Iterator
 361    {
 362    public:
 363       Iterator(const ArrayList *array) : pos(0), data(array->data)
 364       {
 365          size = array->getSize();
 366          if (size)
 367             nextValid();
 368       }
 369
 370       void nextValid() { while ((pos < size) && !data[pos].p) ++pos; }
 371
 372       void next() { if (pos < size) { ++pos; nextValid(); } }
 373       void *get() const { assert(pos < size); return data[pos].p; }
 374       bool end() const { return pos >= size; }
 375
 376    private:
 377       unsigned int pos;
 378       unsigned int size;
 379       const DynArray& data;
 380
 381       friend class ArrayList;
 382    };
 383
 384    Iterator iterator() const { return Iterator(this); }
 385
 386 private:
 387    DynArray data;
 388    Stack ids;
 389    unsigned int size;
 390 };
 391
 392 class Interval
 393 {
 394 public:
 395    Interval() : head(0), tail(0) { }
 396    ~Interval();
 397
 398    bool extend(int, int);
 399    void unify(Interval&); // clears source interval
 400    void clear();
 401
 402    inline int begin() { return head ? head->bgn : -1; }
 403    inline int end() { checkTail(); return tail ? tail->end : -1; }
 404    inline bool isEmpty() const { return !head; }
 405    bool overlaps(const Interval&) const;
 406    bool contains(int pos);
 407
 408    void print() const;
 409
 410    inline void checkTail() const;
 411
 412 private:
 413    class Range
 414    {
 415    public:
 416       Range(int a, int b) : next(0), bgn(a), end(b) { }
 417
 418       Range *next;
 419       int bgn;
 420       int end;
 421
 422       void coalesce(Range **ptail)
 423       {
 424          Range *rnn;
 425
 426          while (next && end >= next->bgn) {
 427             assert(bgn <= next->bgn);
 428             rnn = next->next;
 429             end = MAX2(end, next->end);
 430             delete next;
 431             next = rnn;
 432          }
 433          if (!next)
 434             *ptail = this;
 435       }
 436    };
 437
 438    Range *head;
 439    Range *tail;
 440 };
 441
 442 class BitSet
 443 {
 444 public:
 445    BitSet() : marker(false), data(0), size(0) { }
 446    BitSet(unsigned int nBits, bool zero) : marker(false), data(0), size(0)
 447    {
 448       allocate(nBits, zero);
 449    }
 450    ~BitSet()
 451    {
 452       if (data)
 453          FREE(data);
 454    }
 455
 456    bool allocate(unsigned int nBits, bool zero);
 457
 458    inline unsigned int getSize() const { return size; }
 459
 460    void fill(uint32_t val);
 461
 462    void setOr(BitSet *, BitSet *); // second BitSet may be NULL
 463
 464    inline void set(unsigned int i)
 465    {
 466       assert(i < size);
 467       data[i / 32] |= 1 << (i % 32);
 468    }
 469
 470    inline void clr(unsigned int i)
 471    {
 472       assert(i < size);
 473       data[i / 32] &= ~(1 << (i % 32));
 474    }
 475
 476    inline bool test(unsigned int i) const
 477    {
 478       assert(i < size);
 479       return data[i / 32] & (1 << (i % 32));
 480    }
 481
 482    BitSet& operator|=(const BitSet&);
 483
 484    BitSet& operator=(const BitSet& set)
 485    {
 486       assert(data && set.data);
 487       assert(size == set.size);
 488       memcpy(data, set.data, (set.size + 7) / 8);
 489       return *this;
 490    }
 491
 492    void andNot(const BitSet&);
 493
 494    unsigned int popCount() const;
 495
 496    void print() const;
 497
 498 public:
 499    bool marker; // for user
 500
 501 private:
 502    uint32_t *data;
 503    unsigned int size;
 504 };
 505
 506 void Interval::checkTail() const
 507 {
 508 #if NV50_DEBUG & NV50_DEBUG_PROG_RA
 509    Range *r = head;
 510    while (r->next)
 511       r = r->next;
 512    assert(tail == r);
 513 #endif
 514 }
 515
 516 class MemoryPool
 517 {
 518 private:
 519    inline bool enlargeAllocationsArray(const unsigned int id, unsigned int nr)
 520    {
 521       const unsigned int size = sizeof(uint8_t *) * id;
 522       const unsigned int incr = sizeof(uint8_t *) * nr;
 523
 524       uint8_t **alloc = (uint8_t **)REALLOC(allocArray, size, size + incr);
 525       if (!alloc)
 526          return false;
 527       allocArray = alloc;
 528       return true;
 529    }
 530
 531    inline bool enlargeCapacity()
 532    {
 533       const unsigned int id = count >> objStepLog2;
 534
 535       uint8_t *const mem = (uint8_t *)MALLOC(objSize << objStepLog2);
 536       if (!mem)
 537          return false;
 538
 539       if (!(id % 32)) {
 540          if (!enlargeAllocationsArray(id, 32)) {
 541             FREE(mem);
 542             return false;
 543          }
 544       }
 545       allocArray[id] = mem;
 546       return true;
 547    }
 548
 549 public:
 550    MemoryPool(unsigned int size, unsigned int incr) : objSize(size),
 551                                                       objStepLog2(incr)
 552    {
 553       allocArray = NULL;
 554       released = NULL;
 555       count = 0;
 556    }
 557
 558    ~MemoryPool()
 559    {
 560       unsigned int allocCount = (count + (1 << objStepLog2) - 1) >> objStepLog2;
 561       for (unsigned int i = 0; i < allocCount && allocArray[i]; ++i)
 562          FREE(allocArray[i]);
 563       if (allocArray)
 564          FREE(allocArray);
 565    }
 566
 567    void *allocate()
 568    {
 569       void *ret;
 570       const unsigned int mask = (1 << objStepLog2) - 1;
 571
 572       if (released) {
 573          ret = released;
 574          released = *(void **)released;
 575          return ret;
 576       }
 577
 578       if (!(count & mask))
 579          if (!enlargeCapacity())
 580             return NULL;
 581
 582       ret = allocArray[count >> objStepLog2] + (count & mask) * objSize;
 583       ++count;
 584       return ret;
 585    }
 586
 587    void release(void *ptr)
 588    {
 589       *(void **)ptr = released;
 590       released = ptr;
 591    }
 592
 593 private:
 594    uint8_t **allocArray; // array (list) of MALLOC allocations
 595
 596    void *released; // list of released objects
 597
 598    unsigned int count; // highest allocated object
 599
 600    const unsigned int objSize;
 601    const unsigned int objStepLog2;
 602 };
 603
 604 } // namespace nv50_ir
 605
 606 #endif // __NV50_IR_UTIL_H__