1364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand/* 2364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * Copyright © 2016 Intel Corporation 3364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * 4364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * Permission is hereby granted, free of charge, to any person obtaining a 5364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * copy of this software and associated documentation files (the "Software"), 6364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * to deal in the Software without restriction, including without limitation 7364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * and/or sell copies of the Software, and to permit persons to whom the 9364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * Software is furnished to do so, subject to the following conditions: 10364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * 11364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * The above copyright notice and this permission notice (including the next 12364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * paragraph) shall be included in all copies or substantial portions of the 13364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * Software. 14364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * 15364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * IN THE SOFTWARE. 22364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand */ 23364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 24364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand#include "nir.h" 25364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand#include "nir_phi_builder.h" 26364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 27364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandstruct repair_ssa_state { 28364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_function_impl *impl; 29364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 30364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand BITSET_WORD *def_set; 31364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand struct nir_phi_builder *phi_builder; 32364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 33364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand bool progress; 34364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand}; 35364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 36364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand/* Get ready to build a phi and return the builder */ 37364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandstatic struct nir_phi_builder * 38364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandprep_build_phi(struct repair_ssa_state *state) 39364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand{ 40364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand const unsigned num_words = BITSET_WORDS(state->impl->num_blocks); 41364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 42364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand /* We create the phi builder on-demand. */ 43364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (state->phi_builder == NULL) { 44364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state->phi_builder = nir_phi_builder_create(state->impl); 45364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state->def_set = ralloc_array(NULL, BITSET_WORD, num_words); 46364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 47364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 48364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand /* We're going to build a phi. That's progress. */ 49364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state->progress = true; 50364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 51364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand /* Set the defs set to empty */ 52364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand memset(state->def_set, 0, num_words * sizeof(*state->def_set)); 53364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 54364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return state->phi_builder; 55364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand} 56364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 57364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandstatic nir_block * 58364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandget_src_block(nir_src *src) 59364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand{ 60364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (src->parent_instr->type == nir_instr_type_phi) { 61364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return exec_node_data(nir_phi_src, src, src)->pred; 62364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } else { 63364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return src->parent_instr->block; 64364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 65364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand} 66364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 67364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandstatic bool 68364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandrepair_ssa_def(nir_ssa_def *def, void *void_state) 69364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand{ 70364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand struct repair_ssa_state *state = void_state; 71364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 72364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand bool is_valid = true; 735015260a0598ada4865b2c6086fc669505f64749Jason Ekstrand nir_foreach_use(src, def) { 74364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (!nir_block_dominates(def->parent_instr->block, get_src_block(src))) { 75364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand is_valid = false; 76364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand break; 77364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 78364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 79364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 80364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (is_valid) 81364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return true; 82364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 83364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand struct nir_phi_builder *pb = prep_build_phi(state); 84364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 85364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand BITSET_SET(state->def_set, def->parent_instr->block->index); 86364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 87364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand struct nir_phi_builder_value *val = 88364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_phi_builder_add_value(pb, def->num_components, def->bit_size, 89364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state->def_set); 90364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 91364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_phi_builder_value_set_block_def(val, def->parent_instr->block, def); 92364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 935015260a0598ada4865b2c6086fc669505f64749Jason Ekstrand nir_foreach_use_safe(src, def) { 94364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_block *src_block = get_src_block(src); 95364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (!nir_block_dominates(def->parent_instr->block, src_block)) { 96364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_instr_rewrite_src(src->parent_instr, src, nir_src_for_ssa( 97364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_phi_builder_value_get_block_def(val, src_block))); 98364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 99364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 100364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 101364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return true; 102364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand} 103364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 104364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandbool 105364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandnir_repair_ssa_impl(nir_function_impl *impl) 106364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand{ 107364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand struct repair_ssa_state state; 108364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 109364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state.impl = impl; 110364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state.phi_builder = NULL; 111364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand state.progress = false; 112364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 113364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_metadata_require(impl, nir_metadata_block_index | 114364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_metadata_dominance); 115364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 1169d41a1ffebfb62ec3ab6e09ae926dcb04917eccdConnor Abbott nir_foreach_block(block, impl) { 117707e72f13bb78869ee95d3286980bf1709cba6cfJason Ekstrand nir_foreach_instr_safe(instr, block) { 1189d41a1ffebfb62ec3ab6e09ae926dcb04917eccdConnor Abbott nir_foreach_ssa_def(instr, repair_ssa_def, &state); 1199d41a1ffebfb62ec3ab6e09ae926dcb04917eccdConnor Abbott } 1209d41a1ffebfb62ec3ab6e09ae926dcb04917eccdConnor Abbott } 121364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 122364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (state.progress) 123364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_metadata_preserve(impl, nir_metadata_block_index | 124364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_metadata_dominance); 125364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 126364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (state.phi_builder) { 127364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand nir_phi_builder_finish(state.phi_builder); 128364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand ralloc_free(state.def_set); 129364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 130364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 131364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return state.progress; 132364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand} 133364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 134364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand/** This pass can be used to repair SSA form in a shader. 135364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * 136364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * Sometimes a transformation (such as return lowering) will have to make 137364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * changes to a shader which, while still correct, break some of NIR's SSA 138364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * invariants. This pass will insert ssa_undefs and phi nodes as needed to 139364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand * get the shader back into SSA that the validator will like. 140364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand */ 141364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandbool 142364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrandnir_repair_ssa(nir_shader *shader) 143364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand{ 144364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand bool progress = false; 145364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 1469464d8c49813aba77285e7465b96e92a91ed327cJason Ekstrand nir_foreach_function(function, shader) { 147364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand if (function->impl) 148364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand progress = nir_repair_ssa_impl(function->impl) || progress; 149364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand } 150364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand 151364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand return progress; 152364212f1ede4b2ecf4361e27e24e3d84e19aa54dJason Ekstrand} 153