5429083e5c802eaea2f225402c09cd23da24d765
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
;
56 /* The list of phi nodes associated with this value. Phi nodes are not
57 * added directly. Instead, they are created, the instr->block pointer
58 * set, and then added to this list. Later, in phi_builder_finish, we
59 * set up their sources and add them to the top of their respective
62 struct exec_list phis
;
64 /* Array of SSA defs, indexed by block. If a phi needs to be inserted
65 * in a given block, it will have the magic value NEEDS_PHI.
71 fill_block_array(nir_block
*block
, void *void_data
)
73 nir_block
**blocks
= void_data
;
74 blocks
[block
->index
] = block
;
78 struct nir_phi_builder
*
79 nir_phi_builder_create(nir_function_impl
*impl
)
81 struct nir_phi_builder
*pb
= ralloc(NULL
, struct nir_phi_builder
);
83 pb
->shader
= impl
->function
->shader
;
86 assert(impl
->valid_metadata
& (nir_metadata_block_index
|
87 nir_metadata_dominance
));
89 pb
->num_blocks
= impl
->num_blocks
;
90 pb
->blocks
= ralloc_array(pb
, nir_block
*, pb
->num_blocks
);
91 nir_foreach_block(impl
, fill_block_array
, pb
->blocks
);
93 exec_list_make_empty(&pb
->values
);
96 pb
->work
= rzalloc_array(pb
, unsigned, pb
->num_blocks
);
97 pb
->W
= ralloc_array(pb
, nir_block
*, pb
->num_blocks
);
102 struct nir_phi_builder_value
*
103 nir_phi_builder_add_value(struct nir_phi_builder
*pb
, unsigned num_components
,
104 const BITSET_WORD
*defs
)
106 struct nir_phi_builder_value
*val
;
107 unsigned i
, w_start
= 0, w_end
= 0;
109 val
= rzalloc_size(pb
, sizeof(*val
) + sizeof(val
->defs
[0]) * pb
->num_blocks
);
111 val
->num_components
= num_components
;
112 exec_list_make_empty(&val
->phis
);
113 exec_list_push_tail(&pb
->values
, &val
->node
);
118 BITSET_FOREACH_SET(i
, tmp
, defs
, pb
->num_blocks
) {
119 if (pb
->work
[i
] < pb
->iter_count
)
120 pb
->W
[w_end
++] = pb
->blocks
[i
];
121 pb
->work
[i
] = pb
->iter_count
;
124 while (w_start
!= w_end
) {
125 nir_block
*cur
= pb
->W
[w_start
++];
126 struct set_entry
*dom_entry
;
127 set_foreach(cur
->dom_frontier
, dom_entry
) {
128 nir_block
*next
= (nir_block
*) dom_entry
->key
;
131 * If there's more than one return statement, then the end block
132 * can be a join point for some definitions. However, there are
133 * no instructions in the end block, so nothing would use those
134 * phi nodes. Of course, we couldn't place those phi nodes
135 * anyways due to the restriction of having no instructions in the
138 if (next
== pb
->impl
->end_block
)
141 if (val
->defs
[next
->index
] == NULL
) {
142 val
->defs
[next
->index
] = NEEDS_PHI
;
144 if (pb
->work
[next
->index
] < pb
->iter_count
) {
145 pb
->work
[next
->index
] = pb
->iter_count
;
146 pb
->W
[w_end
++] = next
;
156 nir_phi_builder_value_set_block_def(struct nir_phi_builder_value
*val
,
157 nir_block
*block
, nir_ssa_def
*def
)
159 val
->defs
[block
->index
] = def
;
163 nir_phi_builder_value_get_block_def(struct nir_phi_builder_value
*val
,
166 if (val
->defs
[block
->index
] == NULL
) {
167 if (block
->imm_dom
) {
168 /* Grab it from our immediate dominator. We'll stash it here for
171 val
->defs
[block
->index
] =
172 nir_phi_builder_value_get_block_def(val
, block
->imm_dom
);
173 return val
->defs
[block
->index
];
175 /* No immediate dominator means that this block is either the
176 * start block or unreachable. In either case, the value is
177 * undefined so we need an SSA undef.
179 nir_ssa_undef_instr
*undef
=
180 nir_ssa_undef_instr_create(val
->builder
->shader
,
181 val
->num_components
);
182 nir_instr_insert(nir_before_cf_list(&val
->builder
->impl
->body
),
184 val
->defs
[block
->index
] = &undef
->def
;
187 } else if (val
->defs
[block
->index
] == NEEDS_PHI
) {
188 /* If we need a phi instruction, go ahead and create one but don't
189 * add it to the program yet. Later, we'll go through and set up phi
190 * sources and add the instructions will be added at that time.
192 nir_phi_instr
*phi
= nir_phi_instr_create(val
->builder
->shader
);
193 nir_ssa_dest_init(&phi
->instr
, &phi
->dest
, val
->num_components
, NULL
);
194 phi
->instr
.block
= block
;
195 exec_list_push_tail(&val
->phis
, &phi
->instr
.node
);
196 val
->defs
[block
->index
] = &phi
->dest
.ssa
;
197 return &phi
->dest
.ssa
;
199 return val
->defs
[block
->index
];
204 compare_blocks(const void *_a
, const void *_b
)
206 nir_block
* const * a
= _a
;
207 nir_block
* const * b
= _b
;
209 return (*a
)->index
- (*b
)->index
;
213 nir_phi_builder_finish(struct nir_phi_builder
*pb
)
215 const unsigned num_blocks
= pb
->num_blocks
;
216 NIR_VLA(nir_block
*, preds
, num_blocks
);
218 foreach_list_typed(struct nir_phi_builder_value
, val
, node
, &pb
->values
) {
219 /* We can't iterate over the list of phis normally because we are
220 * removing them as we go and, in some cases, adding new phis as we
221 * build the source lists of others.
223 while (!exec_list_is_empty(&val
->phis
)) {
224 struct exec_node
*head
= exec_list_get_head(&val
->phis
);
225 nir_phi_instr
*phi
= exec_node_data(nir_phi_instr
, head
, instr
.node
);
226 assert(phi
->instr
.type
== nir_instr_type_phi
);
228 exec_node_remove(&phi
->instr
.node
);
230 /* Construct an array of predecessors. We sort it to ensure
231 * determinism in the phi insertion algorithm.
233 * XXX: Calling qsort this many times seems expensive.
236 struct set_entry
*entry
;
237 set_foreach(phi
->instr
.block
->predecessors
, entry
)
238 preds
[num_preds
++] = (nir_block
*)entry
->key
;
239 qsort(preds
, num_preds
, sizeof(*preds
), compare_blocks
);
241 for (unsigned i
= 0; i
< num_preds
; i
++) {
242 nir_phi_src
*src
= ralloc(phi
, nir_phi_src
);
243 src
->pred
= preds
[i
];
244 src
->src
= nir_src_for_ssa(
245 nir_phi_builder_value_get_block_def(val
, preds
[i
]));
246 exec_list_push_tail(&phi
->srcs
, &src
->node
);
249 nir_instr_insert(nir_before_block(phi
->instr
.block
), &phi
->instr
);