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 fill_block_array(nir_block
*block
, void *void_data
)
84 nir_block
**blocks
= void_data
;
85 blocks
[block
->index
] = block
;
89 struct nir_phi_builder
*
90 nir_phi_builder_create(nir_function_impl
*impl
)
92 struct nir_phi_builder
*pb
= ralloc(NULL
, struct nir_phi_builder
);
94 pb
->shader
= impl
->function
->shader
;
97 assert(impl
->valid_metadata
& (nir_metadata_block_index
|
98 nir_metadata_dominance
));
100 pb
->num_blocks
= impl
->num_blocks
;
101 pb
->blocks
= ralloc_array(pb
, nir_block
*, pb
->num_blocks
);
102 nir_foreach_block(impl
, fill_block_array
, pb
->blocks
);
104 exec_list_make_empty(&pb
->values
);
107 pb
->work
= rzalloc_array(pb
, unsigned, pb
->num_blocks
);
108 pb
->W
= ralloc_array(pb
, nir_block
*, pb
->num_blocks
);
113 struct nir_phi_builder_value
*
114 nir_phi_builder_add_value(struct nir_phi_builder
*pb
, unsigned num_components
,
115 unsigned bit_size
, const BITSET_WORD
*defs
)
117 struct nir_phi_builder_value
*val
;
118 unsigned i
, w_start
= 0, w_end
= 0;
120 val
= rzalloc_size(pb
, sizeof(*val
) + sizeof(val
->defs
[0]) * pb
->num_blocks
);
122 val
->num_components
= num_components
;
123 val
->bit_size
= bit_size
;
124 exec_list_make_empty(&val
->phis
);
125 exec_list_push_tail(&pb
->values
, &val
->node
);
130 BITSET_FOREACH_SET(i
, tmp
, defs
, pb
->num_blocks
) {
131 if (pb
->work
[i
] < pb
->iter_count
)
132 pb
->W
[w_end
++] = pb
->blocks
[i
];
133 pb
->work
[i
] = pb
->iter_count
;
136 while (w_start
!= w_end
) {
137 nir_block
*cur
= pb
->W
[w_start
++];
138 struct set_entry
*dom_entry
;
139 set_foreach(cur
->dom_frontier
, dom_entry
) {
140 nir_block
*next
= (nir_block
*) dom_entry
->key
;
142 /* If there's more than one return statement, then the end block
143 * can be a join point for some definitions. However, there are
144 * no instructions in the end block, so nothing would use those
145 * phi nodes. Of course, we couldn't place those phi nodes
146 * anyways due to the restriction of having no instructions in the
149 if (next
== pb
->impl
->end_block
)
152 if (val
->defs
[next
->index
] == NULL
) {
153 /* Instead of creating a phi node immediately, we simply set the
154 * value to the magic value NEEDS_PHI. Later, we create phi nodes
155 * on demand in nir_phi_builder_value_get_block_def().
157 val
->defs
[next
->index
] = NEEDS_PHI
;
159 if (pb
->work
[next
->index
] < pb
->iter_count
) {
160 pb
->work
[next
->index
] = pb
->iter_count
;
161 pb
->W
[w_end
++] = next
;
171 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value
*val
,
172 nir_block
*block
, nir_ssa_def
*def
)
174 val
->defs
[block
->index
] = def
;
178 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value
*val
,
181 /* For each block, we have one of three types of values */
182 if (val
->defs
[block
->index
] == NULL
) {
183 /* NULL indicates that we have no SSA def for this block. */
184 if (block
->imm_dom
) {
185 /* Grab it from our immediate dominator. We'll stash it here for
188 val
->defs
[block
->index
] =
189 nir_phi_builder_value_get_block_def(val
, block
->imm_dom
);
190 return val
->defs
[block
->index
];
192 /* No immediate dominator means that this block is either the
193 * start block or unreachable. In either case, the value is
194 * undefined so we need an SSA undef.
196 nir_ssa_undef_instr
*undef
=
197 nir_ssa_undef_instr_create(val
->builder
->shader
,
198 val
->num_components
);
199 nir_instr_insert(nir_before_cf_list(&val
->builder
->impl
->body
),
201 val
->defs
[block
->index
] = &undef
->def
;
204 } else if (val
->defs
[block
->index
] == NEEDS_PHI
) {
205 /* The magic value NEEDS_PHI indicates that the block needs a phi node
206 * but none has been created. We need to create one now so we can
207 * return it to the caller.
209 * Because a phi node may use SSA defs that it does not dominate (this
210 * happens in loops), we do not yet have enough information to fully
211 * fill out the phi node. Instead, the phi nodes we create here will be
212 * empty (have no sources) and won't actually be placed in the block's
213 * instruction list yet. Later, in nir_phi_builder_finish(), we walk
214 * over all of the phi instructions, fill out the sources lists, and
215 * place them at the top of their respective block's instruction list.
217 * Creating phi nodes on-demand allows us to avoid creating dead phi
218 * nodes that will just get deleted later. While this probably isn't a
219 * big win for a full into-SSA pass, other users may use the phi builder
220 * to make small SSA form repairs where most of the phi nodes will never
223 nir_phi_instr
*phi
= nir_phi_instr_create(val
->builder
->shader
);
224 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
, val
->num_components
,
225 val
->bit_size
, NULL
);
226 phi
->instr
.block
= block
;
227 exec_list_push_tail(&val
->phis
, &phi
->instr
.node
);
228 val
->defs
[block
->index
] = &phi
->dest
.ssa
;
229 return &phi
->dest
.ssa
;
231 /* In this case, we have an actual SSA def. It's either the result of a
232 * phi node created by the case above or one passed to us through
233 * nir_phi_builder_value_set_block_def().
235 return val
->defs
[block
->index
];
240 compare_blocks(const void *_a
, const void *_b
)
242 nir_block
* const * a
= _a
;
243 nir_block
* const * b
= _b
;
245 return (*a
)->index
- (*b
)->index
;
249 nir_phi_builder_finish(struct nir_phi_builder
*pb
)
251 const unsigned num_blocks
= pb
->num_blocks
;
252 NIR_VLA(nir_block
*, preds
, num_blocks
);
254 foreach_list_typed(struct nir_phi_builder_value
, val
, node
, &pb
->values
) {
255 /* We treat the linked list of phi nodes like a worklist. The list is
256 * pre-populated by calls to nir_phi_builder_value_get_block_def() that
257 * create phi nodes. As we fill in the sources of phi nodes, more may
258 * be created and are added to the end of the list.
260 * Because we are adding and removing phi nodes from the list as we go,
261 * we can't iterate over it normally. Instead, we just iterate until
264 while (!exec_list_is_empty(&val
->phis
)) {
265 struct exec_node
*head
= exec_list_get_head(&val
->phis
);
266 nir_phi_instr
*phi
= exec_node_data(nir_phi_instr
, head
, instr
.node
);
267 assert(phi
->instr
.type
== nir_instr_type_phi
);
269 exec_node_remove(&phi
->instr
.node
);
271 /* Construct an array of predecessors. We sort it to ensure
272 * determinism in the phi insertion algorithm.
274 * XXX: Calling qsort this many times seems expensive.
277 struct set_entry
*entry
;
278 set_foreach(phi
->instr
.block
->predecessors
, entry
)
279 preds
[num_preds
++] = (nir_block
*)entry
->key
;
280 qsort(preds
, num_preds
, sizeof(*preds
), compare_blocks
);
282 for (unsigned i
= 0; i
< num_preds
; i
++) {
283 nir_phi_src
*src
= ralloc(phi
, nir_phi_src
);
284 src
->pred
= preds
[i
];
285 src
->src
= nir_src_for_ssa(
286 nir_phi_builder_value_get_block_def(val
, preds
[i
]));
287 exec_list_push_tail(&phi
->srcs
, &src
->node
);
290 nir_instr_insert(nir_before_block(phi
->instr
.block
), &phi
->instr
);