* SOFTWARE.
*/
-/* mir_is_live_after performs liveness analysis on the MIR, used primarily
- * as part of register allocation. TODO: Algorithmic improvements for
- * compiler performance (this is the worst algorithm possible -- see
- * backlog with Connor on IRC) */
-
#include "compiler.h"
-static bool
-midgard_is_live_in_instr(midgard_instruction *ins, int src)
+void
+mir_liveness_ins_update(uint16_t *live, midgard_instruction *ins, unsigned max)
{
- if (ins->compact_branch)
- return false;
+ /* live_in[s] = GEN[s] + (live_out[s] - KILL[s]) */
- if (ins->ssa_args.src0 == src)
- return true;
+ pan_liveness_kill(live, ins->dest, max, mir_bytemask(ins));
- if (!ins->ssa_args.inline_constant && ins->ssa_args.src1 == src)
- return true;
+ mir_foreach_src(ins, src) {
+ unsigned node = ins->src[src];
+ unsigned bytemask = mir_bytemask_of_read_components(ins, node);
- return false;
+ pan_liveness_gen(live, node, max, bytemask);
+ }
}
-/* Determine if a variable is live in the successors of a block */
-static bool
-is_live_after_successors(compiler_context *ctx, midgard_block *bl, int src)
+static void
+mir_liveness_ins_update_wrap(uint16_t *live, void *ins, unsigned max)
{
- for (unsigned i = 0; i < bl->nr_successors; ++i) {
- midgard_block *succ = bl->successors[i];
-
- /* If we already visited, the value we're seeking
- * isn't down this path (or we would have short
- * circuited */
-
- if (succ->visited) continue;
-
- /* Otherwise (it's visited *now*), check the block */
-
- succ->visited = true;
-
- /* Within this block, check if it's overwritten first */
- bool block_done = false;
+ mir_liveness_ins_update(live, (midgard_instruction *) ins, max);
+}
- mir_foreach_instr_in_block(succ, ins) {
- if (midgard_is_live_in_instr(ins, src))
- return true;
+void
+mir_compute_liveness(compiler_context *ctx)
+{
+ /* If we already have fresh liveness, nothing to do */
+ if (ctx->metadata & MIDGARD_METADATA_LIVENESS)
+ return;
- /* If written-before-use, we're gone */
+ mir_compute_temp_count(ctx);
+ pan_compute_liveness(&ctx->blocks, ctx->temp_count, mir_liveness_ins_update_wrap);
- if (ins->ssa_args.dest == src && ins->type == TAG_LOAD_STORE_4 && ins->load_store.op == midgard_op_ld_int4 && ins->load_store.unknown == 0x1EEA) {
- block_done = true;
- break;
- }
- }
+ /* Liveness is now valid */
+ ctx->metadata |= MIDGARD_METADATA_LIVENESS;
+}
- if (block_done)
- continue;
+/* Once liveness data is no longer valid, call this */
- /* ...and also, check *its* successors */
- if (is_live_after_successors(ctx, succ, src))
- return true;
-
- }
+void
+mir_invalidate_liveness(compiler_context *ctx)
+{
+ /* If we didn't already compute liveness, there's nothing to do */
+ if (!(ctx->metadata & MIDGARD_METADATA_LIVENESS))
+ return;
- /* Welp. We're really not live. */
+ pan_free_liveness(&ctx->blocks);
- return false;
+ /* It's now invalid regardless */
+ ctx->metadata &= ~MIDGARD_METADATA_LIVENESS;
}
bool
mir_is_live_after(compiler_context *ctx, midgard_block *block, midgard_instruction *start, int src)
{
- /* Check the rest of the block for liveness */
-
- mir_foreach_instr_in_block_from(block, ins, mir_next_op(start)) {
- if (midgard_is_live_in_instr(ins, src))
- return true;
- }
+ mir_compute_liveness(ctx);
- /* Check the rest of the blocks for liveness recursively */
+ /* Check whether we're live in the successors */
- bool succ = is_live_after_successors(ctx, block, src);
-
- mir_foreach_block(ctx, block) {
- block->visited = false;
- }
-
- return succ;
-}
-
-/* Just a quick check -- is it written more than once? (I.e. are we definitely
- * not SSA?) */
+ if (pan_liveness_get(block->base.live_out, src, ctx->temp_count))
+ return true;
-bool
-mir_has_multiple_writes(compiler_context *ctx, int dest)
-{
- unsigned write_count = 0;
+ /* Check the rest of the block for liveness */
- mir_foreach_instr_global(ctx, ins) {
- if (ins->ssa_args.dest == dest)
- write_count++;
+ mir_foreach_instr_in_block_from(block, ins, mir_next_op(start)) {
+ if (mir_has_arg(ins, src))
+ return true;
}
- return write_count > 1;
+ return false;
}