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