1 /* 2 * Copyright 2014 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 * Authors: 24 * Jason Ekstrand (jason (at) jlekstrand.net) 25 */ 26 27 #include "nir.h" 28 #include "nir_worklist.h" 29 #include "nir_vla.h" 30 31 /* 32 * Basic liveness analysis. This works only in SSA form. 33 * 34 * This liveness pass treats phi nodes as being melded to the space between 35 * blocks so that the destinations of a phi are in the livein of the block 36 * in which it resides and the sources are in the liveout of the 37 * corresponding block. By formulating the liveness information in this 38 * way, we ensure that the definition of any variable dominates its entire 39 * live range. This is true because the only way that the definition of an 40 * SSA value may not dominate a use is if the use is in a phi node and the 41 * uses in phi no are in the live-out of the corresponding predecessor 42 * block but not in the live-in of the block containing the phi node. 43 */ 44 45 struct live_ssa_defs_state { 46 unsigned num_ssa_defs; 47 unsigned bitset_words; 48 49 nir_block_worklist worklist; 50 }; 51 52 static bool 53 index_ssa_def(nir_ssa_def *def, void *void_state) 54 { 55 struct live_ssa_defs_state *state = void_state; 56 57 if (def->parent_instr->type == nir_instr_type_ssa_undef) 58 def->live_index = 0; 59 else 60 def->live_index = state->num_ssa_defs++; 61 62 return true; 63 } 64 65 /* Initialize the liveness data to zero and add the given block to the 66 * worklist. 67 */ 68 static bool 69 init_liveness_block(nir_block *block, 70 struct live_ssa_defs_state *state) 71 { 72 block->live_in = reralloc(block, block->live_in, BITSET_WORD, 73 state->bitset_words); 74 memset(block->live_in, 0, state->bitset_words * sizeof(BITSET_WORD)); 75 76 block->live_out = reralloc(block, block->live_out, BITSET_WORD, 77 state->bitset_words); 78 memset(block->live_out, 0, state->bitset_words * sizeof(BITSET_WORD)); 79 80 nir_block_worklist_push_head(&state->worklist, block); 81 82 return true; 83 } 84 85 static bool 86 set_src_live(nir_src *src, void *void_live) 87 { 88 BITSET_WORD *live = void_live; 89 90 if (!src->is_ssa) 91 return true; 92 93 if (src->ssa->live_index == 0) 94 return true; /* undefined variables are never live */ 95 96 BITSET_SET(live, src->ssa->live_index); 97 98 return true; 99 } 100 101 static bool 102 set_ssa_def_dead(nir_ssa_def *def, void *void_live) 103 { 104 BITSET_WORD *live = void_live; 105 106 BITSET_CLEAR(live, def->live_index); 107 108 return true; 109 } 110 111 /** Propagates the live in of succ across the edge to the live out of pred 112 * 113 * Phi nodes exist "between" blocks and all the phi nodes at the start of a 114 * block act "in parallel". When we propagate from the live_in of one 115 * block to the live out of the other, we have to kill any writes from phis 116 * and make live any sources. 117 * 118 * Returns true if updating live out of pred added anything 119 */ 120 static bool 121 propagate_across_edge(nir_block *pred, nir_block *succ, 122 struct live_ssa_defs_state *state) 123 { 124 NIR_VLA(BITSET_WORD, live, state->bitset_words); 125 memcpy(live, succ->live_in, state->bitset_words * sizeof *live); 126 127 nir_foreach_instr(instr, succ) { 128 if (instr->type != nir_instr_type_phi) 129 break; 130 nir_phi_instr *phi = nir_instr_as_phi(instr); 131 132 assert(phi->dest.is_ssa); 133 set_ssa_def_dead(&phi->dest.ssa, live); 134 } 135 136 nir_foreach_instr(instr, succ) { 137 if (instr->type != nir_instr_type_phi) 138 break; 139 nir_phi_instr *phi = nir_instr_as_phi(instr); 140 141 nir_foreach_phi_src(src, phi) { 142 if (src->pred == pred) { 143 set_src_live(&src->src, live); 144 break; 145 } 146 } 147 } 148 149 BITSET_WORD progress = 0; 150 for (unsigned i = 0; i < state->bitset_words; ++i) { 151 progress |= live[i] & ~pred->live_out[i]; 152 pred->live_out[i] |= live[i]; 153 } 154 return progress != 0; 155 } 156 157 void 158 nir_live_ssa_defs_impl(nir_function_impl *impl) 159 { 160 struct live_ssa_defs_state state; 161 162 /* We start at 1 because we reserve the index value of 0 for ssa_undef 163 * instructions. Those are never live, so their liveness information 164 * can be compacted into a single bit. 165 */ 166 state.num_ssa_defs = 1; 167 nir_foreach_block(block, impl) { 168 nir_foreach_instr(instr, block) 169 nir_foreach_ssa_def(instr, index_ssa_def, &state); 170 } 171 172 nir_block_worklist_init(&state.worklist, impl->num_blocks, NULL); 173 174 /* We now know how many unique ssa definitions we have and we can go 175 * ahead and allocate live_in and live_out sets and add all of the 176 * blocks to the worklist. 177 */ 178 state.bitset_words = BITSET_WORDS(state.num_ssa_defs); 179 nir_foreach_block(block, impl) { 180 init_liveness_block(block, &state); 181 } 182 183 184 /* We're now ready to work through the worklist and update the liveness 185 * sets of each of the blocks. By the time we get to this point, every 186 * block in the function implementation has been pushed onto the 187 * worklist in reverse order. As long as we keep the worklist 188 * up-to-date as we go, everything will get covered. 189 */ 190 while (!nir_block_worklist_is_empty(&state.worklist)) { 191 /* We pop them off in the reverse order we pushed them on. This way 192 * the first walk of the instructions is backwards so we only walk 193 * once in the case of no control flow. 194 */ 195 nir_block *block = nir_block_worklist_pop_head(&state.worklist); 196 197 memcpy(block->live_in, block->live_out, 198 state.bitset_words * sizeof(BITSET_WORD)); 199 200 nir_if *following_if = nir_block_get_following_if(block); 201 if (following_if) 202 set_src_live(&following_if->condition, block->live_in); 203 204 nir_foreach_instr_reverse(instr, block) { 205 /* Phi nodes are handled seperately so we want to skip them. Since 206 * we are going backwards and they are at the beginning, we can just 207 * break as soon as we see one. 208 */ 209 if (instr->type == nir_instr_type_phi) 210 break; 211 212 nir_foreach_ssa_def(instr, set_ssa_def_dead, block->live_in); 213 nir_foreach_src(instr, set_src_live, block->live_in); 214 } 215 216 /* Walk over all of the predecessors of the current block updating 217 * their live in with the live out of this one. If anything has 218 * changed, add the predecessor to the work list so that we ensure 219 * that the new information is used. 220 */ 221 struct set_entry *entry; 222 set_foreach(block->predecessors, entry) { 223 nir_block *pred = (nir_block *)entry->key; 224 if (propagate_across_edge(pred, block, &state)) 225 nir_block_worklist_push_tail(&state.worklist, pred); 226 } 227 } 228 229 nir_block_worklist_fini(&state.worklist); 230 } 231 232 static bool 233 src_does_not_use_def(nir_src *src, void *def) 234 { 235 return !src->is_ssa || src->ssa != (nir_ssa_def *)def; 236 } 237 238 static bool 239 search_for_use_after_instr(nir_instr *start, nir_ssa_def *def) 240 { 241 /* Only look for a use strictly after the given instruction */ 242 struct exec_node *node = start->node.next; 243 while (!exec_node_is_tail_sentinel(node)) { 244 nir_instr *instr = exec_node_data(nir_instr, node, node); 245 if (!nir_foreach_src(instr, src_does_not_use_def, def)) 246 return true; 247 node = node->next; 248 } 249 return false; 250 } 251 252 /* Returns true if def is live at instr assuming that def comes before 253 * instr in a pre DFS search of the dominance tree. 254 */ 255 static bool 256 nir_ssa_def_is_live_at(nir_ssa_def *def, nir_instr *instr) 257 { 258 if (BITSET_TEST(instr->block->live_out, def->live_index)) { 259 /* Since def dominates instr, if def is in the liveout of the block, 260 * it's live at instr 261 */ 262 return true; 263 } else { 264 if (BITSET_TEST(instr->block->live_in, def->live_index) || 265 def->parent_instr->block == instr->block) { 266 /* In this case it is either live coming into instr's block or it 267 * is defined in the same block. In this case, we simply need to 268 * see if it is used after instr. 269 */ 270 return search_for_use_after_instr(instr, def); 271 } else { 272 return false; 273 } 274 } 275 } 276 277 bool 278 nir_ssa_defs_interfere(nir_ssa_def *a, nir_ssa_def *b) 279 { 280 if (a->parent_instr == b->parent_instr) { 281 /* Two variables defined at the same time interfere assuming at 282 * least one isn't dead. 283 */ 284 return true; 285 } else if (a->live_index == 0 || b->live_index == 0) { 286 /* If either variable is an ssa_undef, then there's no interference */ 287 return false; 288 } else if (a->live_index < b->live_index) { 289 return nir_ssa_def_is_live_at(a, b->parent_instr); 290 } else { 291 return nir_ssa_def_is_live_at(b, a->parent_instr); 292 } 293 } 294
