| /* |
| * Copyright (c) 2019 Zodiac Inflight Innovations |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sub license, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the |
| * next paragraph) shall be included in all copies or substantial portions |
| * of the Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| * DEALINGS IN THE SOFTWARE. |
| * |
| * Authors: |
| * Jonathan Marek <jonathan@marek.ca> |
| */ |
| |
| #include "etnaviv_compiler_nir.h" |
| #include "compiler/nir/nir_worklist.h" |
| |
| static void |
| range_include(struct live_def *def, unsigned index) |
| { |
| if (def->live_start > index) |
| def->live_start = index; |
| if (def->live_end < index) |
| def->live_end = index; |
| } |
| |
| struct live_defs_state { |
| unsigned num_defs; |
| unsigned bitset_words; |
| |
| nir_function_impl *impl; |
| nir_block *block; /* current block pointer */ |
| unsigned index; /* current live index */ |
| |
| struct live_def *defs; |
| unsigned *live_map; /* to map ssa/reg index into defs array */ |
| |
| nir_block_worklist worklist; |
| }; |
| |
| static bool |
| init_liveness_block(nir_block *block, |
| struct live_defs_state *state) |
| { |
| block->live_in = reralloc(block, block->live_in, BITSET_WORD, |
| state->bitset_words); |
| memset(block->live_in, 0, state->bitset_words * sizeof(BITSET_WORD)); |
| |
| block->live_out = reralloc(block, block->live_out, BITSET_WORD, |
| state->bitset_words); |
| memset(block->live_out, 0, state->bitset_words * sizeof(BITSET_WORD)); |
| |
| nir_block_worklist_push_head(&state->worklist, block); |
| |
| return true; |
| } |
| |
| static bool |
| set_src_live(nir_src *src, void *void_state) |
| { |
| struct live_defs_state *state = void_state; |
| |
| if (src->is_ssa) { |
| nir_instr *instr = src->ssa->parent_instr; |
| |
| if (is_sysval(instr) || instr->type == nir_instr_type_deref) |
| return true; |
| |
| switch (instr->type) { |
| case nir_instr_type_load_const: |
| case nir_instr_type_ssa_undef: |
| return true; |
| case nir_instr_type_alu: { |
| /* alu op bypass */ |
| nir_alu_instr *alu = nir_instr_as_alu(instr); |
| if (instr->pass_flags & BYPASS_SRC) { |
| for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++) |
| set_src_live(&alu->src[i].src, state); |
| return true; |
| } |
| } break; |
| default: |
| break; |
| } |
| } |
| |
| unsigned i = state->live_map[src_index(state->impl, src)]; |
| assert(i != ~0u); |
| |
| BITSET_SET(state->block->live_in, i); |
| range_include(&state->defs[i], state->index); |
| |
| return true; |
| } |
| |
| static bool |
| propagate_across_edge(nir_block *pred, nir_block *succ, |
| struct live_defs_state *state) |
| { |
| BITSET_WORD progress = 0; |
| for (unsigned i = 0; i < state->bitset_words; ++i) { |
| progress |= succ->live_in[i] & ~pred->live_out[i]; |
| pred->live_out[i] |= succ->live_in[i]; |
| } |
| return progress != 0; |
| } |
| |
| unsigned |
| etna_live_defs(nir_function_impl *impl, struct live_def *defs, unsigned *live_map) |
| { |
| struct live_defs_state state; |
| unsigned block_live_index[impl->num_blocks + 1]; |
| |
| state.impl = impl; |
| state.defs = defs; |
| state.live_map = live_map; |
| |
| state.num_defs = 0; |
| nir_foreach_block(block, impl) { |
| block_live_index[block->index] = state.num_defs; |
| nir_foreach_instr(instr, block) { |
| nir_dest *dest = dest_for_instr(instr); |
| if (!dest) |
| continue; |
| |
| unsigned idx = dest_index(impl, dest); |
| /* register is already in defs */ |
| if (live_map[idx] != ~0u) |
| continue; |
| |
| defs[state.num_defs] = (struct live_def) {instr, dest, state.num_defs, 0}; |
| |
| /* input live from the start */ |
| if (instr->type == nir_instr_type_intrinsic) { |
| nir_intrinsic_instr *intr = nir_instr_as_intrinsic(instr); |
| if (intr->intrinsic == nir_intrinsic_load_input || |
| intr->intrinsic == nir_intrinsic_load_instance_id) |
| defs[state.num_defs].live_start = 0; |
| } |
| |
| live_map[idx] = state.num_defs; |
| state.num_defs++; |
| } |
| } |
| block_live_index[impl->num_blocks] = state.num_defs; |
| |
| nir_block_worklist_init(&state.worklist, impl->num_blocks, NULL); |
| |
| /* We now know how many unique ssa definitions we have and we can go |
| * ahead and allocate live_in and live_out sets and add all of the |
| * blocks to the worklist. |
| */ |
| state.bitset_words = BITSET_WORDS(state.num_defs); |
| nir_foreach_block(block, impl) { |
| init_liveness_block(block, &state); |
| } |
| |
| /* We're now ready to work through the worklist and update the liveness |
| * sets of each of the blocks. By the time we get to this point, every |
| * block in the function implementation has been pushed onto the |
| * worklist in reverse order. As long as we keep the worklist |
| * up-to-date as we go, everything will get covered. |
| */ |
| while (!nir_block_worklist_is_empty(&state.worklist)) { |
| /* We pop them off in the reverse order we pushed them on. This way |
| * the first walk of the instructions is backwards so we only walk |
| * once in the case of no control flow. |
| */ |
| nir_block *block = nir_block_worklist_pop_head(&state.worklist); |
| state.block = block; |
| |
| memcpy(block->live_in, block->live_out, |
| state.bitset_words * sizeof(BITSET_WORD)); |
| |
| state.index = block_live_index[block->index + 1]; |
| |
| nir_if *following_if = nir_block_get_following_if(block); |
| if (following_if) |
| set_src_live(&following_if->condition, &state); |
| |
| nir_foreach_instr_reverse(instr, block) { |
| /* when we come across the next "live" instruction, decrement index */ |
| if (state.index && instr == defs[state.index - 1].instr) { |
| state.index--; |
| /* the only source of writes to registers is phis: |
| * we don't expect any partial write_mask alus |
| * so clearing live_in here is OK |
| */ |
| BITSET_CLEAR(block->live_in, state.index); |
| } |
| |
| /* don't set_src_live for not-emitted instructions */ |
| if (instr->pass_flags) |
| continue; |
| |
| unsigned index = state.index; |
| |
| /* output live till the end */ |
| if (instr->type == nir_instr_type_intrinsic) { |
| nir_intrinsic_instr *intr = nir_instr_as_intrinsic(instr); |
| if (intr->intrinsic == nir_intrinsic_store_deref) |
| state.index = ~0u; |
| } |
| |
| nir_foreach_src(instr, set_src_live, &state); |
| |
| state.index = index; |
| } |
| assert(state.index == block_live_index[block->index]); |
| |
| /* Walk over all of the predecessors of the current block updating |
| * their live in with the live out of this one. If anything has |
| * changed, add the predecessor to the work list so that we ensure |
| * that the new information is used. |
| */ |
| set_foreach(block->predecessors, entry) { |
| nir_block *pred = (nir_block *)entry->key; |
| if (propagate_across_edge(pred, block, &state)) |
| nir_block_worklist_push_tail(&state.worklist, pred); |
| } |
| } |
| |
| nir_block_worklist_fini(&state.worklist); |
| |
| /* apply live_in/live_out to ranges */ |
| |
| nir_foreach_block(block, impl) { |
| int i; |
| |
| BITSET_FOREACH_SET(i, block->live_in, state.num_defs) |
| range_include(&state.defs[i], block_live_index[block->index]); |
| |
| BITSET_FOREACH_SET(i, block->live_out, state.num_defs) |
| range_include(&state.defs[i], block_live_index[block->index + 1]); |
| } |
| |
| return state.num_defs; |
| } |