#include "ppir.h"
+/* Propagates liveness from a liveness set to another by performing the
+ * union between sets. */
static void
-ppir_liveness_setup_def_use(ppir_compiler *comp)
+ppir_liveness_propagate(ppir_compiler *comp,
+ struct ppir_liveness *dest, struct ppir_liveness *src,
+ struct set *dest_set, struct set *src_set)
{
- list_for_each_entry(ppir_block, block, &comp->block_list, list) {
- list_for_each_entry(ppir_instr, instr, &block->instr_list, list) {
- for (int i = 0; i < PPIR_INSTR_SLOT_NUM; i++) {
- ppir_node *node = instr->slots[i];
- if (!node)
- continue;
- switch (node->op) {
- case ppir_op_const:
- continue;
- default:
- break;
- }
-
- for (int i = 0; i < ppir_node_get_src_num(node); i++) {
- ppir_src *src = ppir_node_get_src(node, i);
- if (!src)
- continue;
- ppir_reg *reg = ppir_src_get_reg(src);
- if (!reg)
- continue;
-
- reg->live_in = MIN2(reg->live_in, instr->seq);
- reg->live_out = MAX2(reg->live_out, instr->seq);
-
- if (BITSET_TEST(block->def, reg->regalloc_index))
- continue;
- BITSET_SET(block->use, reg->regalloc_index);
- }
-
- ppir_dest *dest = ppir_node_get_dest(node);
- if (!dest)
- continue;
- ppir_reg *reg = ppir_dest_get_reg(dest);
- if (!reg)
+ set_foreach(src_set, entry_src) {
+ const struct ppir_liveness *s = entry_src->key;
+ assert(s);
+
+ unsigned int regalloc_index = s->reg->regalloc_index;
+
+ dest[regalloc_index].reg = src[regalloc_index].reg;
+ dest[regalloc_index].mask |= src[regalloc_index].mask;
+ _mesa_set_add(dest_set, &dest[regalloc_index]);
+ }
+}
+
+/* Clone a liveness set (without propagation) */
+static void
+ppir_liveness_set_clone(ppir_compiler *comp,
+ struct ppir_liveness *dest, struct ppir_liveness *src,
+ struct set *dest_set, struct set *src_set)
+{
+ _mesa_set_clear(dest_set, NULL);
+ memset(dest, 0, list_length(&comp->reg_list) * sizeof(struct ppir_liveness));
+ memcpy(dest, src,
+ list_length(&comp->reg_list) * sizeof(struct ppir_liveness));
+
+ set_foreach(src_set, entry_src) {
+ const struct ppir_liveness *s = entry_src->key;
+ assert(s);
+
+ unsigned int regalloc_index = s->reg->regalloc_index;
+ dest[regalloc_index].reg = src[regalloc_index].reg;
+ dest[regalloc_index].mask = src[regalloc_index].mask;
+ _mesa_set_add(dest_set, &dest[regalloc_index]);
+ }
+}
+
+/* Check whether two liveness sets are equal. */
+static bool
+ppir_liveness_set_equal(ppir_compiler *comp,
+ struct ppir_liveness *l1, struct ppir_liveness *l2,
+ struct set *set1, struct set *set2)
+{
+ set_foreach(set1, entry1) {
+ const struct ppir_liveness *k1 = entry1->key;
+ unsigned int regalloc_index = k1->reg->regalloc_index;
+
+ struct set_entry *entry2 = _mesa_set_search(set2, &l2[regalloc_index]);
+ if (!entry2)
+ return false;
+
+ const struct ppir_liveness *k2 = entry2->key;
+
+ if (k1->mask != k2->mask)
+ return false;
+ }
+ set_foreach(set2, entry2) {
+ const struct ppir_liveness *k2 = entry2->key;
+ unsigned int regalloc_index = k2->reg->regalloc_index;
+
+ struct set_entry *entry1 = _mesa_set_search(set1, &l1[regalloc_index]);
+ if (!entry1)
+ return false;
+
+ const struct ppir_liveness *k1 = entry1->key;
+
+ if (k2->mask != k1->mask)
+ return false;
+ }
+ return true;
+}
+
+/* Update the liveness information of the instruction by adding its srcs
+ * as live registers to the live_in set. */
+static void
+ppir_liveness_instr_srcs(ppir_compiler *comp, ppir_instr *instr)
+{
+ for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
+ ppir_node *node = instr->slots[i];
+ if (!node)
+ continue;
+
+ switch(node->op) {
+ case ppir_op_const:
+ case ppir_op_undef:
+ continue;
+ default:
+ break;
+ }
+
+ for (int i = 0; i < ppir_node_get_src_num(node); i++) {
+ ppir_src *src = ppir_node_get_src(node, i);
+ if (!src || src->type == ppir_target_pipeline)
+ continue;
+
+ ppir_reg *reg = ppir_src_get_reg(src);
+ if (!reg || reg->undef)
+ continue;
+
+ /* if some other op on this same instruction is writing,
+ * we just need to reserve a register for this particular
+ * instruction. Add the register to live_out to make that
+ * interference happen without propagating its liveness. */
+ if (src->node && src->node->instr == instr) {
+ instr->live_out[reg->regalloc_index].reg = reg;
+ _mesa_set_add(instr->live_out_set, &instr->live_out[reg->regalloc_index]);
+ continue;
+ }
+
+ struct set_entry *live = _mesa_set_search(instr->live_in_set,
+ &instr->live_in[reg->regalloc_index]);
+ if (src->type == ppir_target_ssa) {
+ /* reg is read, needs to be live before instr */
+ if (live)
continue;
- reg->live_in = MIN2(reg->live_in, instr->seq);
- reg->live_out = MAX2(reg->live_out, instr->seq);
+ instr->live_in[reg->regalloc_index].reg = reg;
+ _mesa_set_add(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
+ }
+ else {
+ unsigned int mask = ppir_src_get_mask(node);
- if (BITSET_TEST(block->use, reg->regalloc_index))
+ /* read reg is type register, need to check if this sets
+ * any additional bits in the current mask */
+ if (live && (instr->live_in[reg->regalloc_index].mask ==
+ (instr->live_in[reg->regalloc_index].mask | mask)))
continue;
- BITSET_SET(block->def, reg->regalloc_index);
+
+ /* some new components */
+ instr->live_in[reg->regalloc_index].reg = reg;
+ instr->live_in[reg->regalloc_index].mask |= mask;
+ _mesa_set_add(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
}
}
}
}
-static bool
-ppir_liveness_setup_live_in_out(ppir_compiler *comp, int bitset_words)
+
+/* Update the liveness information of the instruction by removing its
+ * dests from the live_in set. */
+static void
+ppir_liveness_instr_dest(ppir_compiler *comp, ppir_instr *instr)
{
- bool cont = false;
- list_for_each_entry_rev(ppir_block, block, &comp->block_list, list) {
- /* Update live_out: Any successor using the variable
- * on entrance needs us to have the variable live on
- * exit.
- */
- for (int i = 0; i < 2; i++) {
- ppir_block *succ = block->successors[i];
- if (!succ)
+ for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
+ ppir_node *node = instr->slots[i];
+ if (!node)
+ continue;
+
+ switch(node->op) {
+ case ppir_op_const:
+ case ppir_op_undef:
+ case ppir_op_store_color: /* never clear dest if its store output */
continue;
- for (int i = 0; i < bitset_words; i++) {
- BITSET_WORD new_live_out = (succ->live_in[i] &
- ~block->live_out[i]);
- if (new_live_out) {
- block->live_out[i] |= new_live_out;
- cont = true;
- }
- }
+ default:
+ break;
}
- /* Update live_in */
- for (int i = 0; i < bitset_words; i++) {
- BITSET_WORD new_live_in = (block->use[i] |
- (block->live_out[i] &
- ~block->def[i]));
- if (new_live_in & ~block->live_in[i]) {
- block->live_in[i] |= new_live_in;
- cont = true;
+
+ ppir_dest *dest = ppir_node_get_dest(node);
+ if (!dest || dest->type == ppir_target_pipeline)
+ continue;
+ ppir_reg *reg = ppir_dest_get_reg(dest);
+ if (!reg || reg->undef)
+ continue;
+
+ struct set_entry *live = _mesa_set_search(instr->live_in_set,
+ &instr->live_in[reg->regalloc_index]);
+ if (dest->type == ppir_target_ssa) {
+ if (!live)
+ continue;
+ /* reg is written and ssa, is not live before instr */
+ _mesa_set_remove_key(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
+ }
+ else {
+ unsigned int mask = ppir_src_get_mask(node);
+ /* written reg is type register, need to check if this clears
+ * the remaining mask to remove it from the live set */
+ if (!live ||
+ instr->live_in[reg->regalloc_index].mask ==
+ (instr->live_in[reg->regalloc_index].mask & ~mask))
+ continue;
+
+ instr->live_in[reg->regalloc_index].mask &= ~mask;
+ /* unset reg if all remaining bits were cleared */
+ if (!instr->live_in[reg->regalloc_index].mask) {
+ _mesa_set_remove_key(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
}
}
}
-
- return cont;
}
-static void
-ppir_liveness_compute_start_end(ppir_compiler *comp)
+/* Main loop, iterate blocks/instructions/ops backwards, propagate
+ * livenss and update liveness of each instruction. */
+static bool
+ppir_liveness_compute_live_sets(ppir_compiler *comp)
{
- list_for_each_entry(ppir_block, block, &comp->block_list, list) {
- list_for_each_entry(ppir_reg, reg, &comp->reg_list, list) {
- if (!list_length(&block->instr_list))
+ bool cont = false;
+ list_for_each_entry_rev(ppir_block, block, &comp->block_list, list) {
+ ppir_instr *first = list_first_entry(&block->instr_list, ppir_instr, list);
+ ppir_instr *last = list_last_entry(&block->instr_list, ppir_instr, list);
+
+ /* inherit live_out from the other blocks live_in */
+ for (int i = 0; i < 2; i++) {
+ ppir_block *succ = block->successors[i];
+ if (!succ)
continue;
- if (BITSET_TEST(block->live_in, reg->regalloc_index)) {
- ppir_instr *first = list_first_entry(&block->instr_list,
- ppir_instr, list);
- reg->live_in = MIN2(reg->live_in, first->seq);
- reg->live_out = MAX2(reg->live_out, first->seq);
- }
+ ppir_liveness_propagate(comp, block->live_out, succ->live_in,
+ block->live_out_set, succ->live_in_set);
+ }
- if (BITSET_TEST(block->live_out, reg->regalloc_index)) {
- ppir_instr *last = list_last_entry(&block->instr_list,
- ppir_instr, list);
- reg->live_in = MIN2(reg->live_in, last->seq);
- reg->live_out = MAX2(reg->live_out, last->seq);
+ list_for_each_entry_rev(ppir_instr, instr, &block->instr_list, list) {
+ /* inherit (or-) live variables from next instr or block */
+ if (instr == last) {
+ ppir_liveness_set_clone(comp,
+ instr->live_out, block->live_out,
+ instr->live_out_set, block->live_out_set);
}
+ else {
+ ppir_instr *next_instr = LIST_ENTRY(ppir_instr, instr->list.next, list);
+ ppir_liveness_set_clone(comp,
+ instr->live_out, next_instr->live_in,
+ instr->live_out_set, next_instr->live_in_set);
+ }
+ /* initial copy to check for changes */
+ struct set *temp_live_in_set = _mesa_set_create(comp,
+ _mesa_hash_pointer,
+ _mesa_key_pointer_equal);
+ struct ppir_liveness temp_live_in[list_length(&comp->reg_list)];
+ ppir_liveness_set_clone(comp,
+ temp_live_in, instr->live_in,
+ temp_live_in_set, instr->live_in_set);
+
+ /* initialize live_in for potential changes */
+ ppir_liveness_propagate(comp, instr->live_in, instr->live_out,
+ instr->live_in_set, instr->live_out_set);
+
+ ppir_liveness_instr_dest(comp, instr);
+ ppir_liveness_instr_srcs(comp, instr);
+
+ cont |= !ppir_liveness_set_equal(comp, temp_live_in, instr->live_in,
+ temp_live_in_set, instr->live_in_set);
}
+
+ /* inherit live_in from the first instruction in the block,
+ * or live_out if it is empty */
+ if (!list_is_empty(&block->instr_list) && first && first->scheduled)
+ ppir_liveness_set_clone(comp, block->live_in, first->live_in,
+ block->live_in_set, first->live_in_set);
+ else
+ ppir_liveness_set_clone(comp, block->live_in, block->live_out,
+ block->live_in_set, block->live_out_set);
}
+
+ return cont;
}
-/* Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
- * 1) Compute def and use for each block. 'Def' is variables that are set
- * before they are read in block, 'set' is variables that are read before
- * they're set in the block. Initial live_in and live_out values are set
- * accordingly.
- * 2) Compute live_in and live_out of blocks:
- * live_in(block) = use(block) + (live_out(block) - set(block))
- * live_out(block) = live_in(successors[0]) + live_in(successors[1])
- * Loop walks blocks in reverse order and computes live_in/live_out of each
- * block, loop is terminated when no live_in or live_out is updated.
- * 3) Adjust live_in and live_out of variables to block boundaries if they
- * appear in live_in or live_out.
+/*
+ * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
+ * This implementation calculates liveness before/after each
+ * instruction. Aggregated block liveness information is stored
+ * before/after blocks for conveniency (handle e.g. empty blocks).
+ * Blocks/instructions/ops are iterated backwards so register reads are
+ * propagated up to the instruction that writes it.
+ *
+ * 1) Before computing liveness for each instruction, propagate live_out
+ * from the next instruction. If it is the last instruction in a
+ * block, propagate liveness from all possible next instructions
+ * (in this case, this information comes from the live_out of the
+ * block itself).
+ * 2) Calculate live_in for the each instruction. The initial live_in is
+ * a copy of its live_out so registers who aren't touched by this
+ * instruction are kept intact.
+ * - If a register is written by this instruction, it no longer needs
+ * to be live before the instruction, so it is removed from live_in.
+ * - If a register is read by this instruction, it needs to be live
+ * before its execution, so add it to live_in.
+ * - Non-ssa registers are a special case. For this, the algorithm
+ * keeps and updates the mask of live components following the same
+ * logic as above. The register is only removed from the live set
+ * when no live components are left.
+ * - If a non-ssa register is written and read in the same
+ * instruction, it stays in live_in.
+ * - Another special case is a ssa register that is written by an
+ * early op in the instruction, and read by a later op. In this case,
+ * the algorithm adds it to the live_out set so that the register
+ * allocator properly assigns an interference for it.
+ * 3) The algorithm must run over the entire program until it converges,
+ * i.e. a full run happens without changes. This is because blocks
+ * are updated sequentially and updates in a block may need to be
+ * propagated to parent blocks that were already calculated in the
+ * current run.
*/
void
ppir_liveness_analysis(ppir_compiler *comp)
{
- int bitset_words = BITSET_WORDS(list_length(&comp->reg_list));
-
- ppir_liveness_setup_def_use(comp);
-
- while (ppir_liveness_setup_live_in_out(comp, bitset_words))
+ while (ppir_liveness_compute_live_sets(comp))
;
-
- ppir_liveness_compute_start_end(comp);
}
projects / mesa.git / blobdiff