2 * Copyright © 2016 Intel Corporation
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:
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
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
24 #include "nir_phi_builder.h"
25 #include "nir/nir_vla.h"
27 struct nir_phi_builder
{
29 nir_function_impl
*impl
;
31 /* Copied from the impl for easy access */
34 /* Array of all blocks indexed by block->index. */
37 /* Hold on to the values so we can easily iterate over them. */
38 struct exec_list values
;
40 /* Worklist for phi adding */
46 #define NEEDS_PHI ((nir_ssa_def *)(intptr_t)-1)
48 struct nir_phi_builder_value
{
49 struct exec_node node
;
51 struct nir_phi_builder
*builder
;
53 /* Needed so we can create phis and undefs */
54 unsigned num_components
;
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
63 struct exec_list phis
;
65 /* Array of SSA defs, indexed by block. For each block, this array has has
66 * one of three types of values:
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.
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
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().
82 * Convert a block index into a value that can be used as a key for a hash table
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.
88 #define INDEX_TO_KEY(x) ((void *)(uintptr_t) ((x << 2) + 1))
90 struct nir_phi_builder
*
91 nir_phi_builder_create(nir_function_impl
*impl
)
93 struct nir_phi_builder
*pb
= rzalloc(NULL
, struct nir_phi_builder
);
95 pb
->shader
= impl
->function
->shader
;
98 assert(impl
->valid_metadata
& (nir_metadata_block_index
|
99 nir_metadata_dominance
));
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
;
107 exec_list_make_empty(&pb
->values
);
110 pb
->work
= rzalloc_array(pb
, unsigned, pb
->num_blocks
);
111 pb
->W
= ralloc_array(pb
, nir_block
*, pb
->num_blocks
);
116 struct nir_phi_builder_value
*
117 nir_phi_builder_add_value(struct nir_phi_builder
*pb
, unsigned num_components
,
118 unsigned bit_size
, const BITSET_WORD
*defs
)
120 struct nir_phi_builder_value
*val
;
121 unsigned i
, w_start
= 0, w_end
= 0;
123 val
= rzalloc_size(pb
, sizeof(*val
));
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
);
130 _mesa_hash_table_init(&val
->ht
, pb
, _mesa_hash_pointer
,
131 _mesa_key_pointer_equal
);
136 BITSET_FOREACH_SET(i
, tmp
, defs
, pb
->num_blocks
) {
137 if (pb
->work
[i
] < pb
->iter_count
)
138 pb
->W
[w_end
++] = pb
->blocks
[i
];
139 pb
->work
[i
] = pb
->iter_count
;
142 while (w_start
!= w_end
) {
143 nir_block
*cur
= pb
->W
[w_start
++];
144 set_foreach(cur
->dom_frontier
, dom_entry
) {
145 nir_block
*next
= (nir_block
*) dom_entry
->key
;
147 /* If there's more than one return statement, then the end block
148 * can be a join point for some definitions. However, there are
149 * no instructions in the end block, so nothing would use those
150 * phi nodes. Of course, we couldn't place those phi nodes
151 * anyways due to the restriction of having no instructions in the
154 if (next
== pb
->impl
->end_block
)
157 if (_mesa_hash_table_search(&val
->ht
, INDEX_TO_KEY(next
->index
)) == NULL
) {
158 /* Instead of creating a phi node immediately, we simply set the
159 * value to the magic value NEEDS_PHI. Later, we create phi nodes
160 * on demand in nir_phi_builder_value_get_block_def().
162 nir_phi_builder_value_set_block_def(val
, next
, NEEDS_PHI
);
164 if (pb
->work
[next
->index
] < pb
->iter_count
) {
165 pb
->work
[next
->index
] = pb
->iter_count
;
166 pb
->W
[w_end
++] = next
;
176 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value
*val
,
177 nir_block
*block
, nir_ssa_def
*def
)
179 _mesa_hash_table_insert(&val
->ht
, INDEX_TO_KEY(block
->index
), def
);
183 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value
*val
,
186 /* Crawl up the dominance tree and find the closest dominator for which we
187 * have a valid ssa_def, if any.
189 nir_block
*dom
= block
;
190 struct hash_entry
*he
= NULL
;
192 while (dom
!= NULL
) {
193 he
= _mesa_hash_table_search(&val
->ht
, INDEX_TO_KEY(dom
->index
));
200 /* Exactly one of (he != NULL) and (dom == NULL) must be true. */
201 assert((he
!= NULL
) != (dom
== NULL
));
205 /* No dominator means either that we crawled to the top without ever
206 * finding a definition or that this block is unreachable. In either
207 * case, the value is undefined so we need an SSA undef.
209 nir_ssa_undef_instr
*undef
=
210 nir_ssa_undef_instr_create(val
->builder
->shader
,
213 nir_instr_insert(nir_before_cf_list(&val
->builder
->impl
->body
),
216 } else if (he
->data
== NEEDS_PHI
) {
217 /* The magic value NEEDS_PHI indicates that the block needs a phi node
218 * but none has been created. We need to create one now so we can
219 * return it to the caller.
221 * Because a phi node may use SSA defs that it does not dominate (this
222 * happens in loops), we do not yet have enough information to fully
223 * fill out the phi node. Instead, the phi nodes we create here will be
224 * empty (have no sources) and won't actually be placed in the block's
225 * instruction list yet. Later, in nir_phi_builder_finish(), we walk
226 * over all of the phi instructions, fill out the sources lists, and
227 * place them at the top of their respective block's instruction list.
229 * Creating phi nodes on-demand allows us to avoid creating dead phi
230 * nodes that will just get deleted later. While this probably isn't a
231 * big win for a full into-SSA pass, other users may use the phi builder
232 * to make small SSA form repairs where most of the phi nodes will never
235 nir_phi_instr
*phi
= nir_phi_instr_create(val
->builder
->shader
);
236 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
, val
->num_components
,
237 val
->bit_size
, NULL
);
238 phi
->instr
.block
= dom
;
239 exec_list_push_tail(&val
->phis
, &phi
->instr
.node
);
240 def
= &phi
->dest
.ssa
;
243 /* In this case, we have an actual SSA def. It's either the result of a
244 * phi node created by the case above or one passed to us through
245 * nir_phi_builder_value_set_block_def().
247 def
= (struct nir_ssa_def
*) he
->data
;
250 /* Walk the chain and stash the def in all of the applicable blocks. We do
251 * this for two reasons:
253 * 1) To speed up lookup next time even if the next time is called from a
254 * block that is not dominated by this one.
255 * 2) To avoid unneeded recreation of phi nodes and undefs.
257 for (dom
= block
; dom
!= NULL
; dom
= dom
->imm_dom
) {
258 if (_mesa_hash_table_search(&val
->ht
, INDEX_TO_KEY(dom
->index
)) != NULL
)
261 nir_phi_builder_value_set_block_def(val
, dom
, def
);
268 compare_blocks(const void *_a
, const void *_b
)
270 const nir_block
* const * a
= _a
;
271 const nir_block
* const * b
= _b
;
273 return (*a
)->index
- (*b
)->index
;
277 nir_phi_builder_finish(struct nir_phi_builder
*pb
)
279 const unsigned num_blocks
= pb
->num_blocks
;
280 NIR_VLA(nir_block
*, preds
, num_blocks
);
282 foreach_list_typed(struct nir_phi_builder_value
, val
, node
, &pb
->values
) {
283 /* We treat the linked list of phi nodes like a worklist. The list is
284 * pre-populated by calls to nir_phi_builder_value_get_block_def() that
285 * create phi nodes. As we fill in the sources of phi nodes, more may
286 * be created and are added to the end of the list.
288 * Because we are adding and removing phi nodes from the list as we go,
289 * we can't iterate over it normally. Instead, we just iterate until
292 while (!exec_list_is_empty(&val
->phis
)) {
293 struct exec_node
*head
= exec_list_get_head(&val
->phis
);
294 nir_phi_instr
*phi
= exec_node_data(nir_phi_instr
, head
, instr
.node
);
295 assert(phi
->instr
.type
== nir_instr_type_phi
);
297 exec_node_remove(&phi
->instr
.node
);
299 /* Construct an array of predecessors. We sort it to ensure
300 * determinism in the phi insertion algorithm.
302 * XXX: Calling qsort this many times seems expensive.
305 set_foreach(phi
->instr
.block
->predecessors
, entry
)
306 preds
[num_preds
++] = (nir_block
*)entry
->key
;
307 qsort(preds
, num_preds
, sizeof(*preds
), compare_blocks
);
309 for (unsigned i
= 0; i
< num_preds
; i
++) {
310 nir_phi_src
*src
= ralloc(phi
, nir_phi_src
);
311 src
->pred
= preds
[i
];
312 src
->src
= nir_src_for_ssa(
313 nir_phi_builder_value_get_block_def(val
, preds
[i
]));
314 exec_list_push_tail(&phi
->srcs
, &src
->node
);
317 nir_instr_insert(nir_before_block(phi
->instr
.block
), &phi
->instr
);