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_ssa_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_ssa_def * def)175 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
176 nir_block *block, nir_ssa_def *def)
177 {
178 _mesa_hash_table_insert(&val->ht, INDEX_TO_KEY(block->index), def);
179 }
180
181 nir_ssa_def *
nir_phi_builder_value_get_block_def(struct nir_phi_builder_value * val,nir_block * block)182 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
183 nir_block *block)
184 {
185 /* Crawl up the dominance tree and find the closest dominator for which we
186 * have a valid ssa_def, if any.
187 */
188 nir_block *dom = block;
189 struct hash_entry *he = NULL;
190
191 while (dom != NULL) {
192 he = _mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index));
193 if (he != NULL)
194 break;
195
196 dom = dom->imm_dom;
197 }
198
199 /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
200 assert((he != NULL) != (dom == NULL));
201
202 nir_ssa_def *def;
203 if (dom == NULL) {
204 /* No dominator means either that we crawled to the top without ever
205 * finding a definition or that this block is unreachable. In either
206 * case, the value is undefined so we need an SSA undef.
207 */
208 nir_ssa_undef_instr *undef =
209 nir_ssa_undef_instr_create(val->builder->shader,
210 val->num_components,
211 val->bit_size);
212 nir_instr_insert(nir_before_cf_list(&val->builder->impl->body),
213 &undef->instr);
214 def = &undef->def;
215 } else if (he->data == NEEDS_PHI) {
216 /* The magic value NEEDS_PHI indicates that the block needs a phi node
217 * but none has been created. We need to create one now so we can
218 * return it to the caller.
219 *
220 * Because a phi node may use SSA defs that it does not dominate (this
221 * happens in loops), we do not yet have enough information to fully
222 * fill out the phi node. Instead, the phi nodes we create here will be
223 * empty (have no sources) and won't actually be placed in the block's
224 * instruction list yet. Later, in nir_phi_builder_finish(), we walk
225 * over all of the phi instructions, fill out the sources lists, and
226 * place them at the top of their respective block's instruction list.
227 *
228 * Creating phi nodes on-demand allows us to avoid creating dead phi
229 * nodes that will just get deleted later. While this probably isn't a
230 * big win for a full into-SSA pass, other users may use the phi builder
231 * to make small SSA form repairs where most of the phi nodes will never
232 * be used.
233 */
234 nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
235 nir_ssa_dest_init(&phi->instr, &phi->dest, val->num_components,
236 val->bit_size, NULL);
237 phi->instr.block = dom;
238 exec_list_push_tail(&val->phis, &phi->instr.node);
239 def = &phi->dest.ssa;
240 he->data = def;
241 } else {
242 /* In this case, we have an actual SSA def. It's either the result of a
243 * phi node created by the case above or one passed to us through
244 * nir_phi_builder_value_set_block_def().
245 */
246 def = (struct nir_ssa_def *) he->data;
247 }
248
249 /* Walk the chain and stash the def in all of the applicable blocks. We do
250 * this for two reasons:
251 *
252 * 1) To speed up lookup next time even if the next time is called from a
253 * block that is not dominated by this one.
254 * 2) To avoid unneeded recreation of phi nodes and undefs.
255 */
256 for (dom = block; dom != NULL; dom = dom->imm_dom) {
257 if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)) != NULL)
258 break;
259
260 nir_phi_builder_value_set_block_def(val, dom, def);
261 }
262
263 return def;
264 }
265
266 void
nir_phi_builder_finish(struct nir_phi_builder * pb)267 nir_phi_builder_finish(struct nir_phi_builder *pb)
268 {
269 foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) {
270 /* We treat the linked list of phi nodes like a worklist. The list is
271 * pre-populated by calls to nir_phi_builder_value_get_block_def() that
272 * create phi nodes. As we fill in the sources of phi nodes, more may
273 * be created and are added to the end of the list.
274 *
275 * Because we are adding and removing phi nodes from the list as we go,
276 * we can't iterate over it normally. Instead, we just iterate until
277 * the list is empty.
278 */
279 while (!exec_list_is_empty(&val->phis)) {
280 struct exec_node *head = exec_list_get_head(&val->phis);
281 nir_phi_instr *phi = exec_node_data(nir_phi_instr, head, instr.node);
282 assert(phi->instr.type == nir_instr_type_phi);
283
284 exec_node_remove(&phi->instr.node);
285
286 /* XXX: Constructing the array this many times seems expensive. */
287 nir_block **preds = nir_block_get_predecessors_sorted(phi->instr.block, pb);
288
289 for (unsigned i = 0; i < phi->instr.block->predecessors->entries; i++) {
290 nir_phi_instr_add_src(phi, preds[i],
291 nir_src_for_ssa(nir_phi_builder_value_get_block_def(val, preds[i])));
292 }
293
294 ralloc_free(preds);
295
296 nir_instr_insert(nir_before_block(phi->instr.block), &phi->instr);
297 }
298 }
299
300 ralloc_free(pb);
301 }
302