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