1dd9c621cba4e0581b3703323ad5bf6980823a75
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_call(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
,
200 nir_instr_insert(nir_before_cf_list(&val
->builder
->impl
->body
),
202 val
->defs
[block
->index
] = &undef
->def
;
205 } else if (val
->defs
[block
->index
] == NEEDS_PHI
) {
206 /* The magic value NEEDS_PHI indicates that the block needs a phi node
207 * but none has been created. We need to create one now so we can
208 * return it to the caller.
210 * Because a phi node may use SSA defs that it does not dominate (this
211 * happens in loops), we do not yet have enough information to fully
212 * fill out the phi node. Instead, the phi nodes we create here will be
213 * empty (have no sources) and won't actually be placed in the block's
214 * instruction list yet. Later, in nir_phi_builder_finish(), we walk
215 * over all of the phi instructions, fill out the sources lists, and
216 * place them at the top of their respective block's instruction list.
218 * Creating phi nodes on-demand allows us to avoid creating dead phi
219 * nodes that will just get deleted later. While this probably isn't a
220 * big win for a full into-SSA pass, other users may use the phi builder
221 * to make small SSA form repairs where most of the phi nodes will never
224 nir_phi_instr
*phi
= nir_phi_instr_create(val
->builder
->shader
);
225 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
, val
->num_components
,
226 val
->bit_size
, NULL
);
227 phi
->instr
.block
= block
;
228 exec_list_push_tail(&val
->phis
, &phi
->instr
.node
);
229 val
->defs
[block
->index
] = &phi
->dest
.ssa
;
230 return &phi
->dest
.ssa
;
232 /* In this case, we have an actual SSA def. It's either the result of a
233 * phi node created by the case above or one passed to us through
234 * nir_phi_builder_value_set_block_def().
236 return val
->defs
[block
->index
];
241 compare_blocks(const void *_a
, const void *_b
)
243 nir_block
* const * a
= _a
;
244 nir_block
* const * b
= _b
;
246 return (*a
)->index
- (*b
)->index
;
250 nir_phi_builder_finish(struct nir_phi_builder
*pb
)
252 const unsigned num_blocks
= pb
->num_blocks
;
253 NIR_VLA(nir_block
*, preds
, num_blocks
);
255 foreach_list_typed(struct nir_phi_builder_value
, val
, node
, &pb
->values
) {
256 /* We treat the linked list of phi nodes like a worklist. The list is
257 * pre-populated by calls to nir_phi_builder_value_get_block_def() that
258 * create phi nodes. As we fill in the sources of phi nodes, more may
259 * be created and are added to the end of the list.
261 * Because we are adding and removing phi nodes from the list as we go,
262 * we can't iterate over it normally. Instead, we just iterate until
265 while (!exec_list_is_empty(&val
->phis
)) {
266 struct exec_node
*head
= exec_list_get_head(&val
->phis
);
267 nir_phi_instr
*phi
= exec_node_data(nir_phi_instr
, head
, instr
.node
);
268 assert(phi
->instr
.type
== nir_instr_type_phi
);
270 exec_node_remove(&phi
->instr
.node
);
272 /* Construct an array of predecessors. We sort it to ensure
273 * determinism in the phi insertion algorithm.
275 * XXX: Calling qsort this many times seems expensive.
278 struct set_entry
*entry
;
279 set_foreach(phi
->instr
.block
->predecessors
, entry
)
280 preds
[num_preds
++] = (nir_block
*)entry
->key
;
281 qsort(preds
, num_preds
, sizeof(*preds
), compare_blocks
);
283 for (unsigned i
= 0; i
< num_preds
; i
++) {
284 nir_phi_src
*src
= ralloc(phi
, nir_phi_src
);
285 src
->pred
= preds
[i
];
286 src
->src
= nir_src_for_ssa(
287 nir_phi_builder_value_get_block_def(val
, preds
[i
]));
288 exec_list_push_tail(&phi
->srcs
, &src
->node
);
291 nir_instr_insert(nir_before_block(phi
->instr
.block
), &phi
->instr
);