v3d: Restrict live intervals to the blocks reachable from any def.

In the backend, we often have condition codes on writes to variables, such
that there's no screening def anywhere and the previous live ranges
algorithm would conclude that the start of the range extends to the start
of the program.  However, we do know that the live range can only extend
as early as you can reach from all blocks writing to the variable.

The motivation was that, while we have a couple of hacks to try to promote
conditional writes up to being a def within the block, the exec_mask one
was broken and needed a replacement.

Based on c3c1aa5aeb92 ("intel/fs: Restrict live intervals to the subset
possibly reachable from any definition.").

diff --git a/src/broadcom/compiler/v3d_compiler.h b/src/broadcom/compiler/v3d_compiler.h
index 5984d3ef5fe2a5d01f78a08fd01e27d1c3052421..75dff07404ef22f964bf04163e8be0026ce86cba 100644 (file)
--- a/src/broadcom/compiler/v3d_compiler.h
+++ b/src/broadcom/compiler/v3d_compiler.h
@@ -419,6 +419,8 @@ struct qblock {
 
         /** @{ used by v3d_vir_live_variables.c */
         BITSET_WORD *def;
+        BITSET_WORD *defin;
+        BITSET_WORD *defout;
         BITSET_WORD *use;
         BITSET_WORD *live_in;
         BITSET_WORD *live_out;

diff --git a/src/broadcom/compiler/vir_live_variables.c b/src/broadcom/compiler/vir_live_variables.c
index 2879e23b43c3f1210884495abff44df09a9f13df..cba4000fd1df2cf323452b51d01a14aa46424374 100644 (file)
--- a/src/broadcom/compiler/vir_live_variables.c
+++ b/src/broadcom/compiler/vir_live_variables.c
@@ -109,8 +109,11 @@ vir_setup_def(struct v3d_compile *c, struct qblock *block, int ip,
         c->temp_start[var] = MIN2(c->temp_start[var], ip);
         c->temp_end[var] = MAX2(c->temp_end[var], ip);
 
-        /* If we've already tracked this as a def, or already used it within
-         * the block, there's nothing to do.
+        /* Mark the block as having a (partial) def of the var. */
+        BITSET_SET(block->defout, var);
+
+        /* If we've already tracked this as a def that screens off previous
+         * uses, or already used it within the block, there's nothing to do.
          */
         if (BITSET_TEST(block->use, var) || BITSET_TEST(block->def, var))
                 return;
@@ -278,6 +281,33 @@ vir_live_variables_dataflow(struct v3d_compile *c, int bitset_words)
         return cont;
 }
 
+static bool
+vir_live_variables_defin_defout_dataflow(struct v3d_compile *c, int bitset_words)
+{
+        bool cont = false;
+
+        vir_for_each_block_rev(block, c) {
+                /* Propagate defin/defout down the successors to produce the
+                 * union of blocks with a reachable (partial) definition of
+                 * the var.
+                 *
+                 * This keeps a conditional first write to a reg from
+                 * extending its lifetime back to the start of the program.
+                 */
+                vir_for_each_successor(succ, block) {
+                        for (int i = 0; i < bitset_words; i++) {
+                                BITSET_WORD new_def = (block->defout[i] &
+                                                       ~succ->defin[i]);
+                                succ->defin[i] |= new_def;
+                                succ->defout[i] |= new_def;
+                                cont |= new_def;
+                        }
+                }
+        }
+
+        return cont;
+}
+
 /**
  * Extend the start/end ranges for each variable to account for the
  * new information calculated from control flow.
@@ -287,14 +317,16 @@ vir_compute_start_end(struct v3d_compile *c, int num_vars)
 {
         vir_for_each_block(block, c) {
                 for (int i = 0; i < num_vars; i++) {
-                        if (BITSET_TEST(block->live_in, i)) {
+                        if (BITSET_TEST(block->live_in, i) &&
+                            BITSET_TEST(block->defin, i)) {
                                 c->temp_start[i] = MIN2(c->temp_start[i],
                                                         block->start_ip);
                                 c->temp_end[i] = MAX2(c->temp_end[i],
                                                       block->start_ip);
                         }
 
-                        if (BITSET_TEST(block->live_out, i)) {
+                        if (BITSET_TEST(block->live_out, i) &&
+                            BITSET_TEST(block->defout, i)) {
                                 c->temp_start[i] = MIN2(c->temp_start[i],
                                                         block->end_ip);
                                 c->temp_end[i] = MAX2(c->temp_end[i],
@@ -334,6 +366,8 @@ vir_calculate_live_intervals(struct v3d_compile *c)
 
         vir_for_each_block(block, c) {
                 block->def = rzalloc_array(c, BITSET_WORD, bitset_words);
+                block->defin = rzalloc_array(c, BITSET_WORD, bitset_words);
+                block->defout = rzalloc_array(c, BITSET_WORD, bitset_words);
                 block->use = rzalloc_array(c, BITSET_WORD, bitset_words);
                 block->live_in = rzalloc_array(c, BITSET_WORD, bitset_words);
                 block->live_out = rzalloc_array(c, BITSET_WORD, bitset_words);
@@ -344,6 +378,9 @@ vir_calculate_live_intervals(struct v3d_compile *c)
         while (vir_live_variables_dataflow(c, bitset_words))
                 ;
 
+        while (vir_live_variables_defin_defout_dataflow(c, bitset_words))
+                ;
+
         vir_compute_start_end(c, c->num_temps);
 
         c->live_intervals_valid = true;