1ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland/* 2ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * Copyright © 2015 Thomas Helland 3ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * 4ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * Permission is hereby granted, free of charge, to any person obtaining a 5ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * copy of this software and associated documentation files (the "Software"), 6ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * to deal in the Software without restriction, including without limitation 7ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * and/or sell copies of the Software, and to permit persons to whom the 9ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * Software is furnished to do so, subject to the following conditions: 10ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * 11ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * The above copyright notice and this permission notice (including the next 12ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * paragraph) shall be included in all copies or substantial portions of the 13ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * Software. 14ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * 15ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * IN THE SOFTWARE. 22ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland */ 23ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 24ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland/* 25ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * This pass converts the ssa-graph into "Loop Closed SSA form". This is 26ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * done by placing phi nodes at the exits of the loop for all values 27ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * that are used outside the loop. The result is it transforms: 28ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * 29ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * loop { -> loop { 30ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * ssa2 = .... -> ssa2 = ... 31ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * if (cond) -> if (cond) 32ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * break; -> break; 33ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4 34ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * } -> } 35ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2) 36ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * ssa6 = ssa5 + 4 37ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland */ 38ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 39ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland#include "nir.h" 40ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 41ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandtypedef struct { 42ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland /* The nir_shader we are transforming */ 43ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_shader *shader; 44ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 45ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland /* The loop we store information for */ 46ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_loop *loop; 47ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 48ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland} lcssa_state; 49ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 50ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandstatic bool 51ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandis_if_use_inside_loop(nir_src *use, nir_loop* loop) 52ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland{ 53ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_block *block_before_loop = 54ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 55ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_block *block_after_loop = 56ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 57ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 58ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_block *prev_block = 59ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_cf_node_as_block(nir_cf_node_prev(&use->parent_if->cf_node)); 60ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (prev_block->index <= block_before_loop->index || 61ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland prev_block->index >= block_after_loop->index) { 62ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return false; 63ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 64ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 65ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return true; 66ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland} 67ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 68ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandstatic bool 69ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandis_use_inside_loop(nir_src *use, nir_loop* loop) 70ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland{ 71ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_block *block_before_loop = 72ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 73ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_block *block_after_loop = 74ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 75ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 76ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (use->parent_instr->block->index <= block_before_loop->index || 77ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland use->parent_instr->block->index >= block_after_loop->index) { 78ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return false; 79ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 80ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 81ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return true; 82ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland} 83ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 84ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandstatic bool 85ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandconvert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state) 86ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland{ 87ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland lcssa_state *state = void_state; 88ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland bool all_uses_inside_loop = true; 89ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 90ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_block *block_after_loop = 91ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node)); 92ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 93ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_foreach_use(use, def) { 94ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (use->parent_instr->type == nir_instr_type_phi && 95ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland use->parent_instr->block == block_after_loop) { 96ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland continue; 97ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 98ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 99ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (!is_use_inside_loop(use, state->loop)) { 100ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland all_uses_inside_loop = false; 101ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 102ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 103ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 104ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_foreach_if_use(use, def) { 105ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (!is_if_use_inside_loop(use, state->loop)) { 106ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland all_uses_inside_loop = false; 107ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 108ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 109ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 110ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland /* There where no sources that had defs outside the loop */ 111ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (all_uses_inside_loop) 112ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return true; 113ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 114ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland /* Initialize a phi-instruction */ 115ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_phi_instr *phi = nir_phi_instr_create(state->shader); 116ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_ssa_dest_init(&phi->instr, &phi->dest, 117ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland def->num_components, def->bit_size, "LCSSA-phi"); 118ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 119ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland /* Create a phi node with as many sources pointing to the same ssa_def as 120ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * the block has predecessors. 121ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland */ 122ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland struct set_entry *entry; 123ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland set_foreach(block_after_loop->predecessors, entry) { 124ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_phi_src *phi_src = ralloc(phi, nir_phi_src); 125ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland phi_src->src = nir_src_for_ssa(def); 126ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland phi_src->pred = (nir_block *) entry->key; 127ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 128ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland exec_list_push_tail(&phi->srcs, &phi_src->node); 129ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 130ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 131ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_instr_insert_before_block(block_after_loop, &phi->instr); 132ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 133ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland /* Run through all uses and rewrite those outside the loop to point to 134ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland * the phi instead of pointing to the ssa-def. 135ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland */ 136ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_foreach_use_safe(use, def) { 137ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (use->parent_instr->type == nir_instr_type_phi && 138ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland block_after_loop == use->parent_instr->block) { 139ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland continue; 140ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 141ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 142ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (!is_use_inside_loop(use, state->loop)) { 143ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_instr_rewrite_src(use->parent_instr, use, 144ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_src_for_ssa(&phi->dest.ssa)); 145ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 146ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 147ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 148ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_foreach_if_use_safe(use, def) { 149ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland if (!is_if_use_inside_loop(use, state->loop)) { 150ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_if_rewrite_condition(use->parent_if, 151ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_src_for_ssa(&phi->dest.ssa)); 152ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 153ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 154ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 155ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return true; 156ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland} 157ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 158ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandstatic void 159ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandconvert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state) 160ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland{ 161ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland switch (cf_node->type) { 162ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland case nir_cf_node_block: 163ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_foreach_instr(instr, nir_cf_node_as_block(cf_node)) 164ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state); 165ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return; 166ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland case nir_cf_node_if: { 167ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_if *if_stmt = nir_cf_node_as_if(cf_node); 168ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list) 169ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland convert_to_lcssa(nested_node, state); 170ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list) 171ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland convert_to_lcssa(nested_node, state); 172ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return; 173ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 174ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland case nir_cf_node_loop: { 175ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_loop *parent_loop = state->loop; 176ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland state->loop = nir_cf_node_as_loop(cf_node); 177ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 178ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body) 179ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland convert_to_lcssa(nested_node, state); 180ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 181ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland state->loop = parent_loop; 182ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland return; 183ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 184ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland default: 185ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland unreachable("unknown cf node type"); 186ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland } 187ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland} 188ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 189ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandvoid 190ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Hellandnir_convert_loop_to_lcssa(nir_loop *loop) { 191ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node); 192ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 193ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland nir_metadata_require(impl, nir_metadata_block_index); 194ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 195ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland lcssa_state *state = rzalloc(NULL, lcssa_state); 196ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland state->loop = loop; 197ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland state->shader = impl->function->shader; 198ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 199ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland foreach_list_typed(nir_cf_node, node, node, &state->loop->body) 200ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland convert_to_lcssa(node, state); 201ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland 202ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland ralloc_free(state); 203ec8423a4b174450575152dfb3f9c80ba1b8729afThomas Helland} 204