1 /*
2 * Copyright © 2016 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 #include "nir_phi_builder.h"
25 #include "nir/nir_vla.h"
26
27 struct nir_phi_builder {
28 nir_shader *shader;
29 nir_function_impl *impl;
30
31 /* Copied from the impl for easy access */
32 unsigned num_blocks;
33
34 /* Array of all blocks indexed by block->index. */
35 nir_block **blocks;
36
37 /* Hold on to the values so we can easily iterate over them. */
38 struct exec_list values;
39
40 /* Worklist for phi adding */
41 unsigned iter_count;
42 unsigned *work;
43 nir_block **W;
44 };
45
46 #define NEEDS_PHI ((nir_def *)(intptr_t)-1)
47
48 struct nir_phi_builder_value {
49 struct exec_node node;
50
51 struct nir_phi_builder *builder;
52
53 /* Needed so we can create phis and undefs */
54 unsigned num_components;
55 unsigned bit_size;
56
57 /* The list of phi nodes associated with this value. Phi nodes are not
58 * added directly. Instead, they are created, the instr->block pointer
59 * set, and then added to this list. Later, in phi_builder_finish, we
60 * set up their sources and add them to the top of their respective
61 * blocks.
62 */
63 struct exec_list phis;
64
65 /* Array of SSA defs, indexed by block. For each block, this array has has
66 * one of three types of values:
67 *
68 * - NULL. Indicates that there is no known definition in this block. If
69 * you need to find one, look at the block's immediate dominator.
70 *
71 * - NEEDS_PHI. Indicates that the block may need a phi node but none has
72 * been created yet. If a def is requested for a block, a phi will need
73 * to be created.
74 *
75 * - A regular SSA def. This will be either the result of a phi node or
76 * one of the defs provided by nir_phi_builder_value_set_blocK_def().
77 */
78 struct hash_table ht;
79 };
80
81 /**
82 * Convert a block index into a value that can be used as a key for a hash table
83 *
84 * The hash table functions want a pointer that is not \c NULL.
85 * _mesa_hash_pointer drops the two least significant bits, but that's where
86 * most of our data likely is. Shift by 2 and add 1 to make everything happy.
87 */
88 #define INDEX_TO_KEY(x) ((void *)(uintptr_t)((x << 2) + 1))
89
90 struct nir_phi_builder *
nir_phi_builder_create(nir_function_impl * impl)91 nir_phi_builder_create(nir_function_impl *impl)
92 {
93 struct nir_phi_builder *pb = rzalloc(NULL, struct nir_phi_builder);
94
95 pb->shader = impl->function->shader;
96 pb->impl = impl;
97
98 assert(impl->valid_metadata & (nir_metadata_block_index |
99 nir_metadata_dominance));
100
101 pb->num_blocks = impl->num_blocks;
102 pb->blocks = ralloc_array(pb, nir_block *, pb->num_blocks);
103 nir_foreach_block(block, impl) {
104 pb->blocks[block->index] = block;
105 }
106
107 exec_list_make_empty(&pb->values);
108
109 pb->iter_count = 0;
110 pb->work = rzalloc_array(pb, unsigned, pb->num_blocks);
111 pb->W = ralloc_array(pb, nir_block *, pb->num_blocks);
112
113 return pb;
114 }
115
116 struct nir_phi_builder_value *
nir_phi_builder_add_value(struct nir_phi_builder * pb,unsigned num_components,unsigned bit_size,const BITSET_WORD * defs)117 nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
118 unsigned bit_size, const BITSET_WORD *defs)
119 {
120 struct nir_phi_builder_value *val;
121 unsigned i, w_start = 0, w_end = 0;
122
123 val = rzalloc_size(pb, sizeof(*val));
124 val->builder = pb;
125 val->num_components = num_components;
126 val->bit_size = bit_size;
127 exec_list_make_empty(&val->phis);
128 exec_list_push_tail(&pb->values, &val->node);
129
130 _mesa_hash_table_init(&val->ht, pb, _mesa_hash_pointer,
131 _mesa_key_pointer_equal);
132
133 pb->iter_count++;
134
135 BITSET_FOREACH_SET(i, defs, pb->num_blocks) {
136 if (pb->work[i] < pb->iter_count)
137 pb->W[w_end++] = pb->blocks[i];
138 pb->work[i] = pb->iter_count;
139 }
140
141 while (w_start != w_end) {
142 nir_block *cur = pb->W[w_start++];
143 set_foreach(cur->dom_frontier, dom_entry) {
144 nir_block *next = (nir_block *)dom_entry->key;
145
146 /* If there's more than one return statement, then the end block
147 * can be a join point for some definitions. However, there are
148 * no instructions in the end block, so nothing would use those
149 * phi nodes. Of course, we couldn't place those phi nodes
150 * anyways due to the restriction of having no instructions in the
151 * end block...
152 */
153 if (next == pb->impl->end_block)
154 continue;
155
156 if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(next->index)) == NULL) {
157 /* Instead of creating a phi node immediately, we simply set the
158 * value to the magic value NEEDS_PHI. Later, we create phi nodes
159 * on demand in nir_phi_builder_value_get_block_def().
160 */
161 nir_phi_builder_value_set_block_def(val, next, NEEDS_PHI);
162
163 if (pb->work[next->index] < pb->iter_count) {
164 pb->work[next->index] = pb->iter_count;
165 pb->W[w_end++] = next;
166 }
167 }
168 }
169 }
170
171 return val;
172 }
173
174 void
nir_phi_builder_value_set_block_def(struct nir_phi_builder_value * val,nir_block * block,nir_def * def)175 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
176 nir_block *block, nir_def *def)
177 {
178 if (def != NEEDS_PHI) {
179 assert(def->bit_size == val->bit_size);
180 assert(def->num_components == val->num_components);
181 }
182 _mesa_hash_table_insert(&val->ht, INDEX_TO_KEY(block->index), def);
183 }
184
185 nir_def *
nir_phi_builder_value_get_block_def(struct nir_phi_builder_value * val,nir_block * block)186 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
187 nir_block *block)
188 {
189 /* Crawl up the dominance tree and find the closest dominator for which we
190 * have a valid ssa_def, if any.
191 */
192 nir_block *dom = block;
193 struct hash_entry *he = NULL;
194
195 while (dom != NULL) {
196 he = _mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index));
197 if (he != NULL)
198 break;
199
200 dom = dom->imm_dom;
201 }
202
203 /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
204 assert((he != NULL) != (dom == NULL));
205
206 nir_def *def;
207 if (dom == NULL) {
208 /* No dominator means either that we crawled to the top without ever
209 * finding a definition or that this block is unreachable. In either
210 * case, the value is undefined so we need an SSA undef.
211 */
212 nir_undef_instr *undef =
213 nir_undef_instr_create(val->builder->shader,
214 val->num_components,
215 val->bit_size);
216 nir_instr_insert(nir_before_impl(val->builder->impl),
217 &undef->instr);
218 def = &undef->def;
219 } else if (he->data == NEEDS_PHI) {
220 /* The magic value NEEDS_PHI indicates that the block needs a phi node
221 * but none has been created. We need to create one now so we can
222 * return it to the caller.
223 *
224 * Because a phi node may use SSA defs that it does not dominate (this
225 * happens in loops), we do not yet have enough information to fully
226 * fill out the phi node. Instead, the phi nodes we create here will be
227 * empty (have no sources) and won't actually be placed in the block's
228 * instruction list yet. Later, in nir_phi_builder_finish(), we walk
229 * over all of the phi instructions, fill out the sources lists, and
230 * place them at the top of their respective block's instruction list.
231 *
232 * Creating phi nodes on-demand allows us to avoid creating dead phi
233 * nodes that will just get deleted later. While this probably isn't a
234 * big win for a full into-SSA pass, other users may use the phi builder
235 * to make small SSA form repairs where most of the phi nodes will never
236 * be used.
237 */
238 nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
239 nir_def_init(&phi->instr, &phi->def, val->num_components,
240 val->bit_size);
241 phi->instr.block = dom;
242 exec_list_push_tail(&val->phis, &phi->instr.node);
243 def = &phi->def;
244 he->data = def;
245 } else {
246 /* In this case, we have an actual SSA def. It's either the result of a
247 * phi node created by the case above or one passed to us through
248 * nir_phi_builder_value_set_block_def().
249 */
250 def = (struct nir_def *)he->data;
251 }
252
253 /* Walk the chain and stash the def in all of the applicable blocks. We do
254 * this for two reasons:
255 *
256 * 1) To speed up lookup next time even if the next time is called from a
257 * block that is not dominated by this one.
258 * 2) To avoid unneeded recreation of phi nodes and undefs.
259 */
260 for (dom = block; dom != NULL; dom = dom->imm_dom) {
261 if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)) != NULL)
262 break;
263
264 nir_phi_builder_value_set_block_def(val, dom, def);
265 }
266
267 return def;
268 }
269
270 void
nir_phi_builder_finish(struct nir_phi_builder * pb)271 nir_phi_builder_finish(struct nir_phi_builder *pb)
272 {
273 foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) {
274 /* We treat the linked list of phi nodes like a worklist. The list is
275 * pre-populated by calls to nir_phi_builder_value_get_block_def() that
276 * create phi nodes. As we fill in the sources of phi nodes, more may
277 * be created and are added to the end of the list.
278 *
279 * Because we are adding and removing phi nodes from the list as we go,
280 * we can't iterate over it normally. Instead, we just iterate until
281 * the list is empty.
282 */
283 while (!exec_list_is_empty(&val->phis)) {
284 struct exec_node *head = exec_list_get_head(&val->phis);
285 nir_phi_instr *phi = exec_node_data(nir_phi_instr, head, instr.node);
286 assert(phi->instr.type == nir_instr_type_phi);
287
288 exec_node_remove(&phi->instr.node);
289
290 /* XXX: Constructing the array this many times seems expensive. */
291 nir_block **preds = nir_block_get_predecessors_sorted(phi->instr.block, pb);
292
293 for (unsigned i = 0; i < phi->instr.block->predecessors->entries; i++) {
294 nir_phi_instr_add_src(phi, preds[i],
295 nir_phi_builder_value_get_block_def(val, preds[i]));
296 }
297
298 ralloc_free(preds);
299
300 nir_instr_insert(nir_before_block(phi->instr.block), &phi->instr);
301 }
302 }
303
304 ralloc_free(pb);
305 }
306