src/gallium/drivers/nouveau/codegen/nv50_ir_util.cpp

   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 #include "codegen/nv50_ir_util.h"
  24
  25 namespace nv50_ir {
  26
  27 void DLList::clear()
  28 {
  29    for (Item *next, *item = head.next; item != &head; item = next) {
  30       next = item->next;
  31       delete item;
  32    }
  33    head.next = head.prev = &head;
  34 }
  35
  36 void
  37 DLList::Iterator::erase()
  38 {
  39    Item *rem = pos;
  40
  41    if (rem == term)
  42       return;
  43    pos = pos->next;
  44
  45    DLLIST_DEL(rem);
  46    delete rem;
  47 }
  48
  49 void DLList::Iterator::moveToList(DLList& dest)
  50 {
  51    Item *item = pos;
  52
  53    assert(term != &dest.head);
  54    assert(pos != term);
  55
  56    pos = pos->next;
  57
  58    DLLIST_DEL(item);
  59    DLLIST_ADDHEAD(&dest.head, item);
  60 }
  61
  62 bool
  63 DLList::Iterator::insert(void *data)
  64 {
  65    Item *ins = new Item(data);
  66
  67    ins->next = pos->next;
  68    ins->prev = pos;
  69    pos->next->prev = ins;
  70    pos->next = ins;
  71
  72    if (pos == term)
  73       term = ins;
  74
  75    return true;
  76 }
  77
  78 void
  79 Stack::moveTo(Stack& that)
  80 {
  81    unsigned int newSize = this->size + that.size;
  82
  83    while (newSize > that.limit)
  84       that.resize();
  85    memcpy(&that.array[that.size], &array[0], this->size * sizeof(Item));
  86
  87    that.size = newSize;
  88    this->size = 0;
  89 }
  90
  91 Interval::Interval(const Interval& that) : head(NULL), tail(NULL)
  92 {
  93    this->insert(that);
  94 }
  95
  96 Interval::~Interval()
  97 {
  98    clear();
  99 }
 100
 101 void
 102 Interval::clear()
 103 {
 104    for (Range *next, *r = head; r; r = next) {
 105       next = r->next;
 106       delete r;
 107    }
 108    head = tail = NULL;
 109 }
 110
 111 bool
 112 Interval::extend(int a, int b)
 113 {
 114    Range *r, **nextp = &head;
 115
 116    // NOTE: we need empty intervals for fixed registers
 117    // if (a == b)
 118    //   return false;
 119    assert(a <= b);
 120
 121    for (r = head; r; r = r->next) {
 122       if (b < r->bgn)
 123          break; // insert before
 124       if (a > r->end) {
 125          // insert after
 126          nextp = &r->next;
 127          continue;
 128       }
 129
 130       // overlap
 131       if (a < r->bgn) {
 132          r->bgn = a;
 133          if (b > r->end)
 134             r->end = b;
 135          r->coalesce(&tail);
 136          return true;
 137       }
 138       if (b > r->end) {
 139          r->end = b;
 140          r->coalesce(&tail);
 141          return true;
 142       }
 143       assert(a >= r->bgn);
 144       assert(b <= r->end);
 145       return true;
 146    }
 147
 148    (*nextp) = new Range(a, b);
 149    (*nextp)->next = r;
 150
 151    for (r = (*nextp); r->next; r = r->next);
 152    tail = r;
 153    return true;
 154 }
 155
 156 bool Interval::contains(int pos) const
 157 {
 158    for (Range *r = head; r && r->bgn <= pos; r = r->next)
 159       if (r->end > pos)
 160          return true;
 161    return false;
 162 }
 163
 164 bool Interval::overlaps(const Interval &that) const
 165 {
 166 #if 1
 167    Range *a = this->head;
 168    Range *b = that.head;
 169
 170    while (a && b) {
 171       if (b->bgn < a->end &&
 172           b->end > a->bgn)
 173          return true;
 174       if (a->end <= b->bgn)
 175          a = a->next;
 176       else
 177          b = b->next;
 178    }
 179 #else
 180    for (Range *rA = this->head; rA; rA = rA->next)
 181       for (Range *rB = iv.head; rB; rB = rB->next)
 182          if (rB->bgn < rA->end &&
 183              rB->end > rA->bgn)
 184             return true;
 185 #endif
 186    return false;
 187 }
 188
 189 void Interval::insert(const Interval &that)
 190 {
 191    for (Range *r = that.head; r; r = r->next)
 192       this->extend(r->bgn, r->end);
 193 }
 194
 195 void Interval::unify(Interval &that)
 196 {
 197    assert(this != &that);
 198    for (Range *next, *r = that.head; r; r = next) {
 199       next = r->next;
 200       this->extend(r->bgn, r->end);
 201       delete r;
 202    }
 203    that.head = NULL;
 204 }
 205
 206 int Interval::length() const
 207 {
 208    int len = 0;
 209    for (Range *r = head; r; r = r->next)
 210       len += r->bgn - r->end;
 211    return len;
 212 }
 213
 214 void Interval::print() const
 215 {
 216    if (!head)
 217       return;
 218    INFO("[%i %i)", head->bgn, head->end);
 219    for (const Range *r = head->next; r; r = r->next)
 220       INFO(" [%i %i)", r->bgn, r->end);
 221    INFO("\n");
 222 }
 223
 224 void
 225 BitSet::andNot(const BitSet &set)
 226 {
 227    assert(data && set.data);
 228    assert(size >= set.size);
 229    for (unsigned int i = 0; i < (set.size + 31) / 32; ++i)
 230       data[i] &= ~set.data[i];
 231 }
 232
 233 BitSet& BitSet::operator|=(const BitSet &set)
 234 {
 235    assert(data && set.data);
 236    assert(size >= set.size);
 237    for (unsigned int i = 0; i < (set.size + 31) / 32; ++i)
 238       data[i] |= set.data[i];
 239    return *this;
 240 }
 241
 242 bool BitSet::resize(unsigned int nBits)
 243 {
 244    if (!data || !nBits)
 245       return allocate(nBits, true);
 246    const unsigned int p = (size + 31) / 32;
 247    const unsigned int n = (nBits + 31) / 32;
 248    if (n == p)
 249       return true;
 250
 251    data = (uint32_t *)REALLOC(data, 4 * p, 4 * n);
 252    if (!data) {
 253       size = 0;
 254       return false;
 255    }
 256    if (n > p)
 257       memset(&data[p], 0, (n - p) * 4);
 258    if (nBits < size && (nBits % 32))
 259       data[(nBits + 31) / 32 - 1] &= (1 << (nBits % 32)) - 1;
 260
 261    size = nBits;
 262    return true;
 263 }
 264
 265 bool BitSet::allocate(unsigned int nBits, bool zero)
 266 {
 267    if (data && size < nBits) {
 268       FREE(data);
 269       data = NULL;
 270    }
 271    size = nBits;
 272
 273    if (!data)
 274       data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4));
 275
 276    if (zero)
 277       memset(data, 0, (size + 7) / 8);
 278    else
 279    if (size % 32) // clear unused bits (e.g. for popCount)
 280       data[(size + 31) / 32 - 1] &= (1 << (size % 32)) - 1;
 281
 282    return data;
 283 }
 284
 285 unsigned int BitSet::popCount() const
 286 {
 287    unsigned int count = 0;
 288
 289    for (unsigned int i = 0; i < (size + 31) / 32; ++i)
 290       if (data[i])
 291          count += util_bitcount(data[i]);
 292    return count;
 293 }
 294
 295 void BitSet::fill(uint32_t val)
 296 {
 297    unsigned int i;
 298    for (i = 0; i < (size + 31) / 32; ++i)
 299       data[i] = val;
 300    if (val)
 301       data[i] &= ~(0xffffffff << (size % 32)); // BE ?
 302 }
 303
 304 void BitSet::setOr(BitSet *pA, BitSet *pB)
 305 {
 306    if (!pB) {
 307       *this = *pA;
 308    } else {
 309       for (unsigned int i = 0; i < (size + 31) / 32; ++i)
 310          data[i] = pA->data[i] | pB->data[i];
 311    }
 312 }
 313
 314 int BitSet::findFreeRange(unsigned int count) const
 315 {
 316    const uint32_t m = (1 << count) - 1;
 317    int pos = size;
 318    unsigned int i;
 319    const unsigned int end = (size + 31) / 32;
 320
 321    if (count == 1) {
 322       for (i = 0; i < end; ++i) {
 323          pos = ffs(~data[i]) - 1;
 324          if (pos >= 0)
 325             break;
 326       }
 327    } else
 328    if (count == 2) {
 329       for (i = 0; i < end; ++i) {
 330          if (data[i] != 0xffffffff) {
 331             uint32_t b = data[i] | (data[i] >> 1) | 0xaaaaaaaa;
 332             pos = ffs(~b) - 1;
 333             if (pos >= 0)
 334                break;
 335          }
 336       }
 337    } else
 338    if (count == 4 || count == 3) {
 339       for (i = 0; i < end; ++i) {
 340          if (data[i] != 0xffffffff) {
 341             uint32_t b =
 342                (data[i] >> 0) | (data[i] >> 1) |
 343                (data[i] >> 2) | (data[i] >> 3) | 0xeeeeeeee;
 344             pos = ffs(~b) - 1;
 345             if (pos >= 0)
 346                break;
 347          }
 348       }
 349    } else {
 350       if (count <= 8)
 351          count = 8;
 352       else
 353       if (count <= 16)
 354          count = 16;
 355       else
 356          count = 32;
 357
 358       for (i = 0; i < end; ++i) {
 359          if (data[i] != 0xffffffff) {
 360             for (pos = 0; pos < 32; pos += count)
 361                if (!(data[i] & (m << pos)))
 362                   break;
 363             if (pos < 32)
 364                break;
 365          }
 366       }
 367    }
 368    pos += i * 32;
 369
 370    return ((pos + count) <= size) ? pos : -1;
 371 }
 372
 373 void BitSet::print() const
 374 {
 375    unsigned int n = 0;
 376    INFO("BitSet of size %u:\n", size);
 377    for (unsigned int i = 0; i < (size + 31) / 32; ++i) {
 378       uint32_t bits = data[i];
 379       while (bits) {
 380          int pos = ffs(bits) - 1;
 381          bits &= ~(1 << pos);
 382          INFO(" %i", i * 32 + pos);
 383          ++n;
 384          if ((n % 16) == 0)
 385             INFO("\n");
 386       }
 387    }
 388    if (n % 16)
 389       INFO("\n");
 390 }
 391
 392 } // namespace nv50_ir