1 /* 2 * Copyright 2015 Thomas Helland 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 /* 25 * This pass converts the ssa-graph into "Loop Closed SSA form". This is 26 * done by placing phi nodes at the exits of the loop for all values 27 * that are used outside the loop. The result is it transforms: 28 * 29 * loop { -> loop { 30 * ssa2 = .... -> ssa2 = ... 31 * if (cond) -> if (cond) 32 * break; -> break; 33 * ssa3 = ssa2 * ssa4 -> ssa3 = ssa2 * ssa4 34 * } -> } 35 * ssa6 = ssa2 + 4 -> ssa5 = phi(ssa2) 36 * ssa6 = ssa5 + 4 37 */ 38 39 #include "nir.h" 40 41 typedef struct { 42 /* The nir_shader we are transforming */ 43 nir_shader *shader; 44 45 /* The loop we store information for */ 46 nir_loop *loop; 47 48 } lcssa_state; 49 50 static bool 51 is_if_use_inside_loop(nir_src *use, nir_loop* loop) 52 { 53 nir_block *block_before_loop = 54 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 55 nir_block *block_after_loop = 56 nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 57 58 nir_block *prev_block = 59 nir_cf_node_as_block(nir_cf_node_prev(&use->parent_if->cf_node)); 60 if (prev_block->index <= block_before_loop->index || 61 prev_block->index >= block_after_loop->index) { 62 return false; 63 } 64 65 return true; 66 } 67 68 static bool 69 is_use_inside_loop(nir_src *use, nir_loop* loop) 70 { 71 nir_block *block_before_loop = 72 nir_cf_node_as_block(nir_cf_node_prev(&loop->cf_node)); 73 nir_block *block_after_loop = 74 nir_cf_node_as_block(nir_cf_node_next(&loop->cf_node)); 75 76 if (use->parent_instr->block->index <= block_before_loop->index || 77 use->parent_instr->block->index >= block_after_loop->index) { 78 return false; 79 } 80 81 return true; 82 } 83 84 static bool 85 convert_loop_exit_for_ssa(nir_ssa_def *def, void *void_state) 86 { 87 lcssa_state *state = void_state; 88 bool all_uses_inside_loop = true; 89 90 nir_block *block_after_loop = 91 nir_cf_node_as_block(nir_cf_node_next(&state->loop->cf_node)); 92 93 nir_foreach_use(use, def) { 94 if (use->parent_instr->type == nir_instr_type_phi && 95 use->parent_instr->block == block_after_loop) { 96 continue; 97 } 98 99 if (!is_use_inside_loop(use, state->loop)) { 100 all_uses_inside_loop = false; 101 } 102 } 103 104 nir_foreach_if_use(use, def) { 105 if (!is_if_use_inside_loop(use, state->loop)) { 106 all_uses_inside_loop = false; 107 } 108 } 109 110 /* There where no sources that had defs outside the loop */ 111 if (all_uses_inside_loop) 112 return true; 113 114 /* Initialize a phi-instruction */ 115 nir_phi_instr *phi = nir_phi_instr_create(state->shader); 116 nir_ssa_dest_init(&phi->instr, &phi->dest, 117 def->num_components, def->bit_size, "LCSSA-phi"); 118 119 /* Create a phi node with as many sources pointing to the same ssa_def as 120 * the block has predecessors. 121 */ 122 struct set_entry *entry; 123 set_foreach(block_after_loop->predecessors, entry) { 124 nir_phi_src *phi_src = ralloc(phi, nir_phi_src); 125 phi_src->src = nir_src_for_ssa(def); 126 phi_src->pred = (nir_block *) entry->key; 127 128 exec_list_push_tail(&phi->srcs, &phi_src->node); 129 } 130 131 nir_instr_insert_before_block(block_after_loop, &phi->instr); 132 133 /* Run through all uses and rewrite those outside the loop to point to 134 * the phi instead of pointing to the ssa-def. 135 */ 136 nir_foreach_use_safe(use, def) { 137 if (use->parent_instr->type == nir_instr_type_phi && 138 block_after_loop == use->parent_instr->block) { 139 continue; 140 } 141 142 if (!is_use_inside_loop(use, state->loop)) { 143 nir_instr_rewrite_src(use->parent_instr, use, 144 nir_src_for_ssa(&phi->dest.ssa)); 145 } 146 } 147 148 nir_foreach_if_use_safe(use, def) { 149 if (!is_if_use_inside_loop(use, state->loop)) { 150 nir_if_rewrite_condition(use->parent_if, 151 nir_src_for_ssa(&phi->dest.ssa)); 152 } 153 } 154 155 return true; 156 } 157 158 static void 159 convert_to_lcssa(nir_cf_node *cf_node, lcssa_state *state) 160 { 161 switch (cf_node->type) { 162 case nir_cf_node_block: 163 nir_foreach_instr(instr, nir_cf_node_as_block(cf_node)) 164 nir_foreach_ssa_def(instr, convert_loop_exit_for_ssa, state); 165 return; 166 case nir_cf_node_if: { 167 nir_if *if_stmt = nir_cf_node_as_if(cf_node); 168 foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->then_list) 169 convert_to_lcssa(nested_node, state); 170 foreach_list_typed(nir_cf_node, nested_node, node, &if_stmt->else_list) 171 convert_to_lcssa(nested_node, state); 172 return; 173 } 174 case nir_cf_node_loop: { 175 nir_loop *parent_loop = state->loop; 176 state->loop = nir_cf_node_as_loop(cf_node); 177 178 foreach_list_typed(nir_cf_node, nested_node, node, &state->loop->body) 179 convert_to_lcssa(nested_node, state); 180 181 state->loop = parent_loop; 182 return; 183 } 184 default: 185 unreachable("unknown cf node type"); 186 } 187 } 188 189 void 190 nir_convert_loop_to_lcssa(nir_loop *loop) { 191 nir_function_impl *impl = nir_cf_node_get_function(&loop->cf_node); 192 193 nir_metadata_require(impl, nir_metadata_block_index); 194 195 lcssa_state *state = rzalloc(NULL, lcssa_state); 196 state->loop = loop; 197 state->shader = impl->function->shader; 198 199 foreach_list_typed(nir_cf_node, node, node, &state->loop->body) 200 convert_to_lcssa(node, state); 201 202 ralloc_free(state); 203 } 204