mirror of OpenBSD xenocara tree
github.com/openbsd/xenocara
openbsd
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
27struct 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
48struct 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
90struct nir_phi_builder *
91nir_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_control_flow));
99
100 pb->num_blocks = impl->num_blocks;
101 pb->blocks = ralloc_array(pb, nir_block *, pb->num_blocks);
102 nir_foreach_block_unstructured(block, impl) {
103 pb->blocks[block->index] = block;
104 }
105
106 exec_list_make_empty(&pb->values);
107
108 pb->iter_count = 0;
109 pb->work = rzalloc_array(pb, unsigned, pb->num_blocks);
110 pb->W = ralloc_array(pb, nir_block *, pb->num_blocks);
111
112 return pb;
113}
114
115struct nir_phi_builder_value *
116nir_phi_builder_add_value(struct nir_phi_builder *pb, unsigned num_components,
117 unsigned bit_size, const BITSET_WORD *defs)
118{
119 struct nir_phi_builder_value *val;
120 unsigned i, w_start = 0, w_end = 0;
121
122 val = rzalloc_size(pb, sizeof(*val));
123 val->builder = pb;
124 val->num_components = num_components;
125 val->bit_size = bit_size;
126 exec_list_make_empty(&val->phis);
127 exec_list_push_tail(&pb->values, &val->node);
128
129 _mesa_hash_table_init(&val->ht, pb, _mesa_hash_pointer,
130 _mesa_key_pointer_equal);
131
132 pb->iter_count++;
133
134 BITSET_FOREACH_SET(i, defs, pb->num_blocks) {
135 if (pb->work[i] < pb->iter_count)
136 pb->W[w_end++] = pb->blocks[i];
137 pb->work[i] = pb->iter_count;
138 }
139
140 while (w_start != w_end) {
141 nir_block *cur = pb->W[w_start++];
142 set_foreach(cur->dom_frontier, dom_entry) {
143 nir_block *next = (nir_block *)dom_entry->key;
144
145 /* If there's more than one return statement, then the end block
146 * can be a join point for some definitions. However, there are
147 * no instructions in the end block, so nothing would use those
148 * phi nodes. Of course, we couldn't place those phi nodes
149 * anyways due to the restriction of having no instructions in the
150 * end block...
151 */
152 if (next == pb->impl->end_block)
153 continue;
154
155 if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(next->index)) == NULL) {
156 /* Instead of creating a phi node immediately, we simply set the
157 * value to the magic value NEEDS_PHI. Later, we create phi nodes
158 * on demand in nir_phi_builder_value_get_block_def().
159 */
160 nir_phi_builder_value_set_block_def(val, next, NEEDS_PHI);
161
162 if (pb->work[next->index] < pb->iter_count) {
163 pb->work[next->index] = pb->iter_count;
164 pb->W[w_end++] = next;
165 }
166 }
167 }
168 }
169
170 return val;
171}
172
173void
174nir_phi_builder_value_set_block_def(struct nir_phi_builder_value *val,
175 nir_block *block, nir_def *def)
176{
177 if (def != NEEDS_PHI) {
178 assert(def->bit_size == val->bit_size);
179 assert(def->num_components == val->num_components);
180 }
181 _mesa_hash_table_insert(&val->ht, INDEX_TO_KEY(block->index), def);
182}
183
184nir_def *
185nir_phi_builder_value_get_block_def(struct nir_phi_builder_value *val,
186 nir_block *block)
187{
188 /* Crawl up the dominance tree and find the closest dominator for which we
189 * have a valid ssa_def, if any.
190 */
191 nir_block *dom = block;
192 struct hash_entry *he = NULL;
193
194 while (dom != NULL) {
195 he = _mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index));
196 if (he != NULL)
197 break;
198
199 dom = dom->imm_dom;
200 }
201
202 /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
203 assert((he != NULL) != (dom == NULL));
204
205 nir_def *def;
206 if (dom == NULL) {
207 /* No dominator means either that we crawled to the top without ever
208 * finding a definition or that this block is unreachable. In either
209 * case, the value is undefined so we need an SSA undef.
210 */
211 nir_undef_instr *undef =
212 nir_undef_instr_create(val->builder->shader,
213 val->num_components,
214 val->bit_size);
215 nir_instr_insert(nir_before_impl(val->builder->impl),
216 &undef->instr);
217 def = &undef->def;
218 } else if (he->data == NEEDS_PHI) {
219 /* The magic value NEEDS_PHI indicates that the block needs a phi node
220 * but none has been created. We need to create one now so we can
221 * return it to the caller.
222 *
223 * Because a phi node may use SSA defs that it does not dominate (this
224 * happens in loops), we do not yet have enough information to fully
225 * fill out the phi node. Instead, the phi nodes we create here will be
226 * empty (have no sources) and won't actually be placed in the block's
227 * instruction list yet. Later, in nir_phi_builder_finish(), we walk
228 * over all of the phi instructions, fill out the sources lists, and
229 * place them at the top of their respective block's instruction list.
230 *
231 * Creating phi nodes on-demand allows us to avoid creating dead phi
232 * nodes that will just get deleted later. While this probably isn't a
233 * big win for a full into-SSA pass, other users may use the phi builder
234 * to make small SSA form repairs where most of the phi nodes will never
235 * be used.
236 */
237 nir_phi_instr *phi = nir_phi_instr_create(val->builder->shader);
238 nir_def_init(&phi->instr, &phi->def, val->num_components,
239 val->bit_size);
240 phi->instr.block = dom;
241 exec_list_push_tail(&val->phis, &phi->instr.node);
242 def = &phi->def;
243 he->data = def;
244 } else {
245 /* In this case, we have an actual SSA def. It's either the result of a
246 * phi node created by the case above or one passed to us through
247 * nir_phi_builder_value_set_block_def().
248 */
249 def = (struct nir_def *)he->data;
250 }
251
252 /* Walk the chain and stash the def in all of the applicable blocks. We do
253 * this for two reasons:
254 *
255 * 1) To speed up lookup next time even if the next time is called from a
256 * block that is not dominated by this one.
257 * 2) To avoid unneeded recreation of phi nodes and undefs.
258 */
259 for (dom = block; dom != NULL; dom = dom->imm_dom) {
260 if (_mesa_hash_table_search(&val->ht, INDEX_TO_KEY(dom->index)) != NULL)
261 break;
262
263 nir_phi_builder_value_set_block_def(val, dom, def);
264 }
265
266 return def;
267}
268
269void
270nir_phi_builder_finish(struct nir_phi_builder *pb)
271{
272 foreach_list_typed(struct nir_phi_builder_value, val, node, &pb->values) {
273 /* We treat the linked list of phi nodes like a worklist. The list is
274 * pre-populated by calls to nir_phi_builder_value_get_block_def() that
275 * create phi nodes. As we fill in the sources of phi nodes, more may
276 * be created and are added to the end of the list.
277 *
278 * Because we are adding and removing phi nodes from the list as we go,
279 * we can't iterate over it normally. Instead, we just iterate until
280 * the list is empty.
281 */
282 while (!exec_list_is_empty(&val->phis)) {
283 struct exec_node *head = exec_list_get_head(&val->phis);
284 nir_phi_instr *phi = exec_node_data(nir_phi_instr, head, instr.node);
285 assert(phi->instr.type == nir_instr_type_phi);
286
287 exec_node_remove(&phi->instr.node);
288
289 /* XXX: Constructing the array this many times seems expensive. */
290 nir_block **preds = nir_block_get_predecessors_sorted(phi->instr.block, pb);
291
292 for (unsigned i = 0; i < phi->instr.block->predecessors->entries; i++) {
293 nir_phi_instr_add_src(phi, preds[i],
294 nir_phi_builder_value_get_block_def(val, preds[i]));
295 }
296
297 ralloc_free(preds);
298
299 nir_instr_insert(nir_before_block(phi->instr.block), &phi->instr);
300 }
301 }
302
303 ralloc_free(pb);
304}