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.h"
25 #include "nir_phi_builder.h"
26
27 struct repair_ssa_state {
28 nir_function_impl *impl;
29
30 BITSET_WORD *def_set;
31 struct nir_phi_builder *phi_builder;
32
33 bool progress;
34 };
35
36 /* Get ready to build a phi and return the builder */
37 static struct nir_phi_builder *
prep_build_phi(struct repair_ssa_state * state)38 prep_build_phi(struct repair_ssa_state *state)
39 {
40 const unsigned num_words = BITSET_WORDS(state->impl->num_blocks);
41
42 /* We create the phi builder on-demand. */
43 if (state->phi_builder == NULL) {
44 state->phi_builder = nir_phi_builder_create(state->impl);
45 state->def_set = ralloc_array(NULL, BITSET_WORD, num_words);
46 }
47
48 /* We're going to build a phi. That's progress. */
49 state->progress = true;
50
51 /* Set the defs set to empty */
52 memset(state->def_set, 0, num_words * sizeof(*state->def_set));
53
54 return state->phi_builder;
55 }
56
57 static nir_block *
get_src_block(nir_src * src)58 get_src_block(nir_src *src)
59 {
60 if (src->parent_instr->type == nir_instr_type_phi) {
61 return exec_node_data(nir_phi_src, src, src)->pred;
62 } else {
63 return src->parent_instr->block;
64 }
65 }
66
67 static bool
repair_ssa_def(nir_ssa_def * def,void * void_state)68 repair_ssa_def(nir_ssa_def *def, void *void_state)
69 {
70 struct repair_ssa_state *state = void_state;
71
72 bool is_valid = true;
73 nir_foreach_use(src, def) {
74 if (!nir_block_dominates(def->parent_instr->block, get_src_block(src))) {
75 is_valid = false;
76 break;
77 }
78 }
79
80 if (is_valid)
81 return true;
82
83 struct nir_phi_builder *pb = prep_build_phi(state);
84
85 BITSET_SET(state->def_set, def->parent_instr->block->index);
86
87 struct nir_phi_builder_value *val =
88 nir_phi_builder_add_value(pb, def->num_components, def->bit_size,
89 state->def_set);
90
91 nir_phi_builder_value_set_block_def(val, def->parent_instr->block, def);
92
93 nir_foreach_use_safe(src, def) {
94 nir_block *src_block = get_src_block(src);
95 if (!nir_block_dominates(def->parent_instr->block, src_block)) {
96 nir_instr_rewrite_src(src->parent_instr, src, nir_src_for_ssa(
97 nir_phi_builder_value_get_block_def(val, src_block)));
98 }
99 }
100
101 return true;
102 }
103
104 bool
nir_repair_ssa_impl(nir_function_impl * impl)105 nir_repair_ssa_impl(nir_function_impl *impl)
106 {
107 struct repair_ssa_state state;
108
109 state.impl = impl;
110 state.phi_builder = NULL;
111 state.progress = false;
112
113 nir_metadata_require(impl, nir_metadata_block_index |
114 nir_metadata_dominance);
115
116 nir_foreach_block(block, impl) {
117 nir_foreach_instr_safe(instr, block) {
118 nir_foreach_ssa_def(instr, repair_ssa_def, &state);
119 }
120 }
121
122 if (state.progress)
123 nir_metadata_preserve(impl, nir_metadata_block_index |
124 nir_metadata_dominance);
125
126 if (state.phi_builder) {
127 nir_phi_builder_finish(state.phi_builder);
128 ralloc_free(state.def_set);
129 }
130
131 return state.progress;
132 }
133
134 /** This pass can be used to repair SSA form in a shader.
135 *
136 * Sometimes a transformation (such as return lowering) will have to make
137 * changes to a shader which, while still correct, break some of NIR's SSA
138 * invariants. This pass will insert ssa_undefs and phi nodes as needed to
139 * get the shader back into SSA that the validator will like.
140 */
141 bool
nir_repair_ssa(nir_shader * shader)142 nir_repair_ssa(nir_shader *shader)
143 {
144 bool progress = false;
145
146 nir_foreach_function(function, shader) {
147 if (function->impl)
148 progress = nir_repair_ssa_impl(function->impl) || progress;
149 }
150
151 return progress;
152 }
153