| /* |
| * Copyright (C) 2021 Valve Corporation |
| * |
| * 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, sublicense, |
| * 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 NONINFRINGEMENT. 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. |
| */ |
| |
| #include "ir3_ra.h" |
| #include "ir3_shader.h" |
| #include "ralloc.h" |
| |
| /* A note on how phi node uses are handled: |
| * |
| * - Phi node sources are considered to happen after the end of the |
| * predecessor block, so the live_out for that block contains phi sources. |
| * - On the other hand, phi destinations are considered to happen at the start |
| * of the block, so that live_in does *not* contain phi destinations. This |
| * is mainly because phi destinations and live-through values have to be |
| * treated very differently by RA at the beginning of a block. |
| */ |
| |
| static bool |
| compute_block_liveness(struct ir3_liveness *live, struct ir3_block *block, |
| BITSET_WORD *tmp_live, unsigned bitset_words) |
| { |
| memcpy(tmp_live, live->live_out[block->index], |
| bitset_words * sizeof(BITSET_WORD)); |
| |
| /* Process instructions */ |
| foreach_instr_rev (instr, &block->instr_list) { |
| ra_foreach_dst (dst, instr) { |
| if (BITSET_TEST(tmp_live, dst->name)) |
| dst->flags &= ~IR3_REG_UNUSED; |
| else |
| dst->flags |= IR3_REG_UNUSED; |
| BITSET_CLEAR(tmp_live, dst->name); |
| } |
| |
| /* Phi node uses occur after the predecessor block */ |
| if (instr->opc != OPC_META_PHI) { |
| ra_foreach_src (src, instr) { |
| if (BITSET_TEST(tmp_live, src->def->name)) |
| src->flags &= ~IR3_REG_KILL; |
| else |
| src->flags |= IR3_REG_KILL; |
| } |
| |
| ra_foreach_src (src, instr) { |
| if (BITSET_TEST(tmp_live, src->def->name)) |
| src->flags &= ~IR3_REG_FIRST_KILL; |
| else |
| src->flags |= IR3_REG_FIRST_KILL; |
| BITSET_SET(tmp_live, src->def->name); |
| } |
| } |
| } |
| |
| memcpy(live->live_in[block->index], tmp_live, |
| bitset_words * sizeof(BITSET_WORD)); |
| |
| bool progress = false; |
| for (unsigned i = 0; i < block->predecessors_count; i++) { |
| const struct ir3_block *pred = block->predecessors[i]; |
| for (unsigned j = 0; j < bitset_words; j++) { |
| if (tmp_live[j] & ~live->live_out[pred->index][j]) |
| progress = true; |
| live->live_out[pred->index][j] |= tmp_live[j]; |
| } |
| |
| /* Process phi sources. */ |
| foreach_instr (phi, &block->instr_list) { |
| if (phi->opc != OPC_META_PHI) |
| break; |
| if (!phi->srcs[i]->def) |
| continue; |
| unsigned name = phi->srcs[i]->def->name; |
| if (!BITSET_TEST(live->live_out[pred->index], name)) { |
| progress = true; |
| BITSET_SET(live->live_out[pred->index], name); |
| } |
| } |
| } |
| |
| for (unsigned i = 0; i < block->physical_predecessors_count; i++) { |
| const struct ir3_block *pred = block->physical_predecessors[i]; |
| unsigned name; |
| BITSET_FOREACH_SET (name, tmp_live, live->definitions_count) { |
| struct ir3_register *reg = live->definitions[name]; |
| if (!(reg->flags & IR3_REG_SHARED)) |
| continue; |
| if (!BITSET_TEST(live->live_out[pred->index], name)) { |
| progress = true; |
| BITSET_SET(live->live_out[pred->index], name); |
| } |
| } |
| } |
| |
| return progress; |
| } |
| |
| struct ir3_liveness * |
| ir3_calc_liveness(void *mem_ctx, struct ir3 *ir) |
| { |
| struct ir3_liveness *live = rzalloc(mem_ctx, struct ir3_liveness); |
| |
| /* Reserve name 0 to mean "doesn't have a name yet" to make the debug |
| * output nicer. |
| */ |
| array_insert(live, live->definitions, NULL); |
| |
| /* Build definition <-> name mapping */ |
| unsigned block_count = 0; |
| foreach_block (block, &ir->block_list) { |
| block->index = block_count++; |
| foreach_instr (instr, &block->instr_list) { |
| ra_foreach_dst (dst, instr) { |
| dst->name = live->definitions_count; |
| array_insert(live, live->definitions, dst); |
| } |
| } |
| } |
| |
| live->block_count = block_count; |
| |
| unsigned bitset_words = BITSET_WORDS(live->definitions_count); |
| BITSET_WORD *tmp_live = ralloc_array(live, BITSET_WORD, bitset_words); |
| live->live_in = ralloc_array(live, BITSET_WORD *, block_count); |
| live->live_out = ralloc_array(live, BITSET_WORD *, block_count); |
| unsigned i = 0; |
| foreach_block (block, &ir->block_list) { |
| block->index = i++; |
| live->live_in[block->index] = |
| rzalloc_array(live, BITSET_WORD, bitset_words); |
| live->live_out[block->index] = |
| rzalloc_array(live, BITSET_WORD, bitset_words); |
| } |
| |
| bool progress = true; |
| while (progress) { |
| progress = false; |
| foreach_block_rev (block, &ir->block_list) { |
| progress |= |
| compute_block_liveness(live, block, tmp_live, bitset_words); |
| } |
| } |
| |
| return live; |
| } |
| |
| /* Return true if "def" is live after "instr". It's assumed that "def" |
| * dominates "instr". |
| */ |
| bool |
| ir3_def_live_after(struct ir3_liveness *live, struct ir3_register *def, |
| struct ir3_instruction *instr) |
| { |
| /* If it's live out then it's definitely live at the instruction. */ |
| if (BITSET_TEST(live->live_out[instr->block->index], def->name)) |
| return true; |
| |
| /* If it's not live in and not defined in the same block then the live |
| * range can't extend to the instruction. |
| */ |
| if (def->instr->block != instr->block && |
| !BITSET_TEST(live->live_in[instr->block->index], def->name)) |
| return false; |
| |
| /* Ok, now comes the tricky case, where "def" is killed somewhere in |
| * "instr"'s block and we have to check if it's before or after. |
| */ |
| foreach_instr_rev (test_instr, &instr->block->instr_list) { |
| if (test_instr == instr) |
| break; |
| |
| for (unsigned i = 0; i < test_instr->srcs_count; i++) { |
| if (test_instr->srcs[i]->def == def) |
| return true; |
| } |
| } |
| |
| return false; |
| } |
