src/compiler/nir/nir_worklist.h

   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@jlekstrand.net)
  25  *
  26  */
  27
  28
  29 #ifndef _NIR_WORKLIST_
  30 #define _NIR_WORKLIST_
  31
  32 #include "nir.h"
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38 /** Represents a double-ended queue of unique blocks
  39  *
  40  * The worklist datastructure guarantees that eacy block is in the queue at
  41  * most once.  Pushing a block onto either end of the queue is a no-op if
  42  * the block is already in the queue.  In order for this to work, the
  43  * caller must ensure that the blocks are properly indexed.
  44  */
  45 typedef struct {
  46    /* The total size of the worklist */
  47    unsigned size;
  48
  49    /* The number of blocks currently in the worklist */
  50    unsigned count;
  51
  52    /* The offset in the array of blocks at which the list starts */
  53    unsigned start;
  54
  55    /* A bitset of all of the blocks currently present in the worklist */
  56    BITSET_WORD *blocks_present;
  57
  58    /* The actual worklist */
  59    nir_block **blocks;
  60 } nir_block_worklist;
  61
  62 void nir_block_worklist_init(nir_block_worklist *w, unsigned num_blocks,
  63                              void *mem_ctx);
  64 void nir_block_worklist_fini(nir_block_worklist *w);
  65
  66 void nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl);
  67
  68 static inline bool
  69 nir_block_worklist_is_empty(const nir_block_worklist *w)
  70 {
  71    return w->count == 0;
  72 }
  73
  74 void nir_block_worklist_push_head(nir_block_worklist *w, nir_block *block);
  75
  76 nir_block *nir_block_worklist_peek_head(const nir_block_worklist *w);
  77
  78 nir_block *nir_block_worklist_pop_head(nir_block_worklist *w);
  79
  80 void nir_block_worklist_push_tail(nir_block_worklist *w, nir_block *block);
  81
  82 nir_block *nir_block_worklist_peek_tail(const nir_block_worklist *w);
  83
  84 nir_block *nir_block_worklist_pop_tail(nir_block_worklist *w);
  85
  86 #ifdef __cplusplus
  87 } /* extern "C" */
  88 #endif
  89
  90 #endif /* _NIR_WORKLIST_ */