src/gallium/drivers/nv50/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 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 #include "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()
  92 {
  93    clear();
  94 }
  95
  96 void
  97 Interval::clear()
  98 {
  99    for (Range *next, *r = head; r; r = next) {
 100       next = r->next;
 101       delete r;
 102    }
 103    head = tail = NULL;
 104 }
 105
 106 bool
 107 Interval::extend(int a, int b)
 108 {
 109    Range *r, **nextp = &head;
 110
 111    // NOTE: we need empty intervals for fixed registers
 112    // if (a == b)
 113    //   return false;
 114    assert(a <= b);
 115
 116    for (r = head; r; r = r->next) {
 117       if (b < r->bgn)
 118          break; // insert before
 119       if (a > r->end) {
 120          // insert after
 121          nextp = &r->next;
 122          continue;
 123       }
 124
 125       // overlap
 126       if (a < r->bgn) {
 127          r->bgn = a;
 128          if (b > r->end)
 129             r->end = b;
 130          r->coalesce(&tail);
 131          return true;
 132       }
 133       if (b > r->end) {
 134          r->end = b;
 135          r->coalesce(&tail);
 136          return true;
 137       }
 138       assert(a >= r->bgn);
 139       assert(b <= r->end);
 140       return true;
 141    }
 142
 143    (*nextp) = new Range(a, b);
 144    (*nextp)->next = r;
 145
 146    for (r = (*nextp); r->next; r = r->next);
 147    tail = r;
 148    return true;
 149 }
 150
 151 bool Interval::contains(int pos)
 152 {
 153    for (Range *r = head; r && r->bgn <= pos; r = r->next)
 154       if (r->end > pos)
 155          return true;
 156    return false;
 157 }
 158
 159 bool Interval::overlaps(const Interval &iv) const
 160 {
 161    for (Range *rA = this->head; rA; rA = rA->next)
 162       for (Range *rB = iv.head; rB; rB = rB->next)
 163          if (rB->bgn < rA->end &&
 164              rB->end > rA->bgn)
 165             return true;
 166    return false;
 167 }
 168
 169 void Interval::unify(Interval &that)
 170 {
 171    assert(this != &that);
 172    for (Range *next, *r = that.head; r; r = next) {
 173       next = r->next;
 174       this->extend(r->bgn, r->end);
 175       delete r;
 176    }
 177    that.head = NULL;
 178 }
 179
 180 void Interval::print() const
 181 {
 182    if (!head)
 183       return;
 184    INFO("[%i %i)", head->bgn, head->end);
 185    for (const Range *r = head->next; r; r = r->next)
 186       INFO(" [%i %i)", r->bgn, r->end);
 187    INFO("\n");
 188 }
 189
 190 void
 191 BitSet::andNot(const BitSet &set)
 192 {
 193    assert(data && set.data);
 194    assert(size >= set.size);
 195    for (unsigned int i = 0; i < (set.size + 31) / 32; ++i)
 196       data[i] &= ~set.data[i];
 197 }
 198
 199 BitSet& BitSet::operator|=(const BitSet &set)
 200 {
 201    assert(data && set.data);
 202    assert(size >= set.size);
 203    for (unsigned int i = 0; i < (set.size + 31) / 32; ++i)
 204       data[i] |= set.data[i];
 205    return *this;
 206 }
 207
 208 bool BitSet::allocate(unsigned int nBits, bool zero)
 209 {
 210    if (data && size < nBits) {
 211       FREE(data);
 212       data = NULL;
 213    }
 214    size = nBits;
 215
 216    if (!data)
 217       data = reinterpret_cast<uint32_t *>(CALLOC((size + 31) / 32, 4));
 218
 219    if (zero)
 220       memset(data, 0, (size + 7) / 8);
 221    else
 222    if (nBits)
 223       data[(size + 31) / 32 - 1] = 0; // clear unused bits (e.g. for popCount)
 224
 225    return data;
 226 }
 227
 228 unsigned int BitSet::popCount() const
 229 {
 230    unsigned int count = 0;
 231
 232    for (unsigned int i = 0; i < (size + 31) / 32; ++i)
 233       if (data[i])
 234          count += util_bitcount(data[i]);
 235    return count;
 236 }
 237
 238 void BitSet::fill(uint32_t val)
 239 {
 240    unsigned int i;
 241    for (i = 0; i < (size + 31) / 32; ++i)
 242       data[i] = val;
 243    if (val)
 244       data[i] &= ~(0xffffffff << (size % 32)); // BE ?
 245 }
 246
 247 void BitSet::setOr(BitSet *pA, BitSet *pB)
 248 {
 249    if (!pB) {
 250       *this = *pA;
 251    } else {
 252       for (unsigned int i = 0; i < (size + 31) / 32; ++i)
 253          data[i] = pA->data[i] | pB->data[i];
 254    }
 255 }
 256
 257 void BitSet::print() const
 258 {
 259    unsigned int n = 0;
 260    INFO("BitSet of size %u:\n", size);
 261    for (unsigned int i = 0; i < (size + 31) / 32; ++i) {
 262       uint32_t bits = data[i];
 263       while (bits) {
 264          int pos = ffs(bits) - 1;
 265          bits &= ~(1 << pos);
 266          INFO(" %i", i * 32 + pos);
 267          ++n;
 268          if ((n % 16) == 0)
 269             INFO("\n");
 270       }
 271    }
 272    if (n % 16)
 273       INFO("\n");
 274 }
 275
 276 } // namespace nv50_ir