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