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_is_unreachable(get_src_block(src)) ||
75           !nir_block_dominates(def->parent_instr->block, get_src_block(src))) {
76          is_valid = false;
77          break;
78       }
79    }
80 
81    nir_foreach_if_use(src, def) {
82       nir_block *block_before_if =
83          nir_cf_node_as_block(nir_cf_node_prev(&src->parent_if->cf_node));
84       if (nir_block_is_unreachable(block_before_if) ||
85           !nir_block_dominates(def->parent_instr->block, block_before_if)) {
86          is_valid = false;
87          break;
88       }
89    }
90 
91    if (is_valid)
92       return true;
93 
94    struct nir_phi_builder *pb = prep_build_phi(state);
95 
96    BITSET_SET(state->def_set, def->parent_instr->block->index);
97 
98    struct nir_phi_builder_value *val =
99       nir_phi_builder_add_value(pb, def->num_components, def->bit_size,
100                                 state->def_set);
101 
102    nir_phi_builder_value_set_block_def(val, def->parent_instr->block, def);
103 
104    nir_foreach_use_safe(src, def) {
105       nir_block *src_block = get_src_block(src);
106       if (src_block == def->parent_instr->block) {
107          assert(nir_phi_builder_value_get_block_def(val, src_block) == def);
108          continue;
109       }
110 
111       nir_ssa_def *block_def =
112          nir_phi_builder_value_get_block_def(val, src_block);
113       if (block_def == def)
114          continue;
115 
116       /* If def was a deref and the use we're looking at is a deref that
117        * isn't a cast, we need to wrap it in a cast so we don't loose any
118        * deref information.
119        */
120       if (def->parent_instr->type == nir_instr_type_deref &&
121           src->parent_instr->type == nir_instr_type_deref &&
122           nir_instr_as_deref(src->parent_instr)->deref_type != nir_deref_type_cast) {
123          nir_deref_instr *cast =
124             nir_deref_instr_create(state->impl->function->shader,
125                                    nir_deref_type_cast);
126 
127          nir_deref_instr *deref = nir_instr_as_deref(def->parent_instr);
128          cast->modes = deref->modes;
129          cast->type = deref->type;
130          cast->parent = nir_src_for_ssa(block_def);
131          cast->cast.ptr_stride = nir_deref_instr_array_stride(deref);
132 
133          nir_ssa_dest_init(&cast->instr, &cast->dest,
134                            def->num_components, def->bit_size, NULL);
135          nir_instr_insert(nir_before_instr(src->parent_instr),
136                           &cast->instr);
137          block_def = &cast->dest.ssa;
138       }
139 
140       nir_instr_rewrite_src(src->parent_instr, src, nir_src_for_ssa(block_def));
141    }
142 
143    nir_foreach_if_use_safe(src, def) {
144       nir_block *block_before_if =
145          nir_cf_node_as_block(nir_cf_node_prev(&src->parent_if->cf_node));
146       if (block_before_if == def->parent_instr->block) {
147          assert(nir_phi_builder_value_get_block_def(val, block_before_if) == def);
148          continue;
149       }
150 
151       nir_ssa_def *block_def =
152          nir_phi_builder_value_get_block_def(val, block_before_if);
153       if (block_def == def)
154          continue;
155 
156       nir_if_rewrite_condition(src->parent_if, nir_src_for_ssa(block_def));
157    }
158 
159    return true;
160 }
161 
162 bool
nir_repair_ssa_impl(nir_function_impl * impl)163 nir_repair_ssa_impl(nir_function_impl *impl)
164 {
165    struct repair_ssa_state state;
166 
167    state.impl = impl;
168    state.phi_builder = NULL;
169    state.progress = false;
170 
171    nir_metadata_require(impl, nir_metadata_block_index |
172                               nir_metadata_dominance);
173 
174    nir_foreach_block(block, impl) {
175       nir_foreach_instr_safe(instr, block) {
176          nir_foreach_ssa_def(instr, repair_ssa_def, &state);
177       }
178    }
179 
180    if (state.progress)
181       nir_metadata_preserve(impl, nir_metadata_block_index |
182                                   nir_metadata_dominance);
183 
184    if (state.phi_builder) {
185       nir_phi_builder_finish(state.phi_builder);
186       ralloc_free(state.def_set);
187    }
188 
189    return state.progress;
190 }
191 
192 /** This pass can be used to repair SSA form in a shader.
193  *
194  * Sometimes a transformation (such as return lowering) will have to make
195  * changes to a shader which, while still correct, break some of NIR's SSA
196  * invariants.  This pass will insert ssa_undefs and phi nodes as needed to
197  * get the shader back into SSA that the validator will like.
198  */
199 bool
nir_repair_ssa(nir_shader * shader)200 nir_repair_ssa(nir_shader *shader)
201 {
202    bool progress = false;
203 
204    nir_foreach_function(function, shader) {
205       if (function->impl)
206          progress = nir_repair_ssa_impl(function->impl) || progress;
207    }
208 
209    return progress;
210 }
211