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