Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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
  393.