Home | History | Annotate | Download | only in nir 
      1 /*
      2  * Copyright  2014 Intel Corporation
      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 (including the next
     12  * paragraph) shall be included in all copies or substantial portions of the
     13  * Software.
     14  *
     15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
     18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
     20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
     21  * IN THE SOFTWARE.
     22  *
     23  * Authors:
     24  *    Jason Ekstrand (jason (at) jlekstrand.net)
     25  *
     26  */
     27 
     28 #include "nir_worklist.h"
     29 
     30 void
     31 nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
     32                         void *mem_ctx)
     33 {
     34    w->size = num_blocks;
     35    w->count = 0;
     36    w->start = 0;
     37 
     38    w->blocks_present = rzalloc_array(mem_ctx, BITSET_WORD,
     39                                      BITSET_WORDS(num_blocks));
     40    w->blocks = rzalloc_array(mem_ctx, nir_block *, num_blocks);
     41 }
     42 
     43 void
     44 nir_block_worklist_fini(nir_block_worklist *w)
     45 {
     46    ralloc_free(w->blocks_present);
     47    ralloc_free(w->blocks);
     48 }
     49 
     50 void
     51 nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl)
     52 {
     53    nir_foreach_block(block, impl) {
     54       nir_block_worklist_push_tail(w, block);
     55    }
     56 }
     57 
     58 void
     59 nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block)
     60 {
     61    /* Pushing a block we already have is a no-op */
     62    if (BITSET_TEST(w->blocks_present, block->index))
     63       return;
     64 
     65    assert(w->count < w->size);
     66 
     67    if (w->start == 0)
     68       w->start = w->size - 1;
     69    else
     70       w->start--;
     71 
     72    w->count++;
     73 
     74    w->blocks[w->start] = block;
     75    BITSET_SET(w->blocks_present, block->index);
     76 }
     77 
     78 nir_block *
     79 nir_block_worklist_peek_head(const nir_block_worklist *w)
     80 {
     81    assert(w->count > 0);
     82 
     83    return w->blocks[w->start];
     84 }
     85 
     86 nir_block *
     87 nir_block_worklist_pop_head(nir_block_worklist *w)
     88 {
     89    assert(w->count > 0);
     90 
     91    unsigned head = w->start;
     92 
     93    w->start = (w->start + 1) % w->size;
     94    w->count--;
     95 
     96    BITSET_CLEAR(w->blocks_present, w->blocks[head]->index);
     97    return w->blocks[head];
     98 }
     99 
    100 void
    101 nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block)
    102 {
    103    /* Pushing a block we already have is a no-op */
    104    if (BITSET_TEST(w->blocks_present, block->index))
    105       return;
    106 
    107    assert(w->count < w->size);
    108 
    109    w->count++;
    110 
    111    unsigned tail = (w->start + w->count - 1) % w->size;
    112 
    113    w->blocks[tail] = block;
    114    BITSET_SET(w->blocks_present, block->index);
    115 }
    116 
    117 nir_block *
    118 nir_block_worklist_peek_tail(const nir_block_worklist *w)
    119 {
    120    assert(w->count > 0);
    121 
    122    unsigned tail = (w->start + w->count - 1) % w->size;
    123 
    124    return w->blocks[tail];
    125 }
    126 
    127 nir_block *
    128 nir_block_worklist_pop_tail(nir_block_worklist *w)
    129 {
    130    assert(w->count > 0);
    131 
    132    unsigned tail = (w->start + w->count - 1) % w->size;
    133 
    134    w->count--;
    135 
    136    BITSET_CLEAR(w->blocks_present, w->blocks[tail]->index);
    137    return w->blocks[tail];
    138 }
    139