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#include "nir_worklist.h"
29
30void
31nir_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
43void
44nir_block_worklist_fini(nir_block_worklist *w)
45{
46   ralloc_free(w->blocks_present);
47   ralloc_free(w->blocks);
48}
49
50void
51nir_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
58void
59nir_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
78nir_block *
79nir_block_worklist_peek_head(const nir_block_worklist *w)
80{
81   assert(w->count > 0);
82
83   return w->blocks[w->start];
84}
85
86nir_block *
87nir_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
100void
101nir_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
117nir_block *
118nir_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
127nir_block *
128nir_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