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 #include "util/set.h"
34 #include "util/u_vector.h"
35 #include "util/u_worklist.h"
36
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40
41 typedef u_worklist nir_block_worklist;
42
43 #define nir_block_worklist_init(w, num_blocks, mem_ctx) \
44 u_worklist_init(w, num_blocks, mem_ctx)
45
46 #define nir_block_worklist_fini(w) u_worklist_fini(w)
47
48 #define nir_block_worklist_is_empty(w) u_worklist_is_empty(w)
49
50 #define nir_block_worklist_push_head(w, block) \
51 u_worklist_push_head(w, block, index)
52
53 #define nir_block_worklist_peek_head(w) \
54 u_worklist_peek_head(w, nir_block, index)
55
56 #define nir_block_worklist_pop_head(w) \
57 u_worklist_pop_head(w, nir_block, index)
58
59 #define nir_block_worklist_push_tail(w, block) \
60 u_worklist_push_tail(w, block, index)
61
62 #define nir_block_worklist_peek_tail(w) \
63 u_worklist_peek_tail(w, nir_block, index)
64
65 #define nir_block_worklist_pop_tail(w) \
66 u_worklist_pop_tail(w, nir_block, index)
67
68 void nir_block_worklist_add_all(nir_block_worklist *w, nir_function_impl *impl);
69
70 /*
71 * This worklist implementation, in contrast to the block worklist, does not
72 * have unique entries, meaning a nir_instr can be inserted more than once
73 * into the worklist. It uses u_vector to keep the overhead and memory
74 * footprint at a minimum.
75 *
76 * Making it unique by using a set was tested, but for the single usecase
77 * (nir_opt_dce) it did not improve speed. There we check the pass_flag bit
78 * and abort immediately if there's nothing to do, so the added overhead of
79 * the set was higher than just processing the few extra entries.
80 */
81
82 typedef struct {
83 struct u_vector instr_vec;
84 } nir_instr_worklist;
85
86 static inline nir_instr_worklist *
nir_instr_worklist_create()87 nir_instr_worklist_create() {
88 nir_instr_worklist *wl = malloc(sizeof(nir_instr_worklist));
89 if (!wl)
90 return NULL;
91
92 if (!u_vector_init_pow2(&wl->instr_vec, 8, sizeof(struct nir_instr *))) {
93 free(wl);
94 return NULL;
95 }
96
97 return wl;
98 }
99
100 static inline uint32_t
nir_instr_worklist_length(nir_instr_worklist * wl)101 nir_instr_worklist_length(nir_instr_worklist *wl)
102 {
103 return u_vector_length(&wl->instr_vec);
104 }
105
106 static inline bool
nir_instr_worklist_is_empty(nir_instr_worklist * wl)107 nir_instr_worklist_is_empty(nir_instr_worklist *wl)
108 {
109 return nir_instr_worklist_length(wl) == 0;
110 }
111
112 static inline void
nir_instr_worklist_destroy(nir_instr_worklist * wl)113 nir_instr_worklist_destroy(nir_instr_worklist *wl)
114 {
115 u_vector_finish(&wl->instr_vec);
116 free(wl);
117 }
118
119 static inline void
nir_instr_worklist_push_tail(nir_instr_worklist * wl,nir_instr * instr)120 nir_instr_worklist_push_tail(nir_instr_worklist *wl, nir_instr *instr)
121 {
122 struct nir_instr **vec_instr = u_vector_add(&wl->instr_vec);
123 *vec_instr = instr;
124 }
125
126 static inline nir_instr *
nir_instr_worklist_pop_head(nir_instr_worklist * wl)127 nir_instr_worklist_pop_head(nir_instr_worklist *wl)
128 {
129 struct nir_instr **vec_instr = u_vector_remove(&wl->instr_vec);
130
131 if (vec_instr == NULL)
132 return NULL;
133
134 return *vec_instr;
135 }
136
137 void
138 nir_instr_worklist_add_ssa_srcs(nir_instr_worklist *wl, nir_instr *instr);
139
140 #define nir_foreach_instr_in_worklist(instr, wl) \
141 for (nir_instr *instr; (instr = nir_instr_worklist_pop_head(wl));)
142
143 #ifdef __cplusplus
144 } /* extern "C" */
145 #endif
146
147 #endif /* _NIR_WORKLIST_ */
148