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 #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_ */
     92