i965: Do dead-code elimination in a single pass.

The first pass marked dead instructions as opcode = NOP, and a second
pass deleted those instructions so that the live ranges used in the
first pass wouldn't change.

But since we're walking the instructions in reverse order, we can just
do everything in one pass. The only thing we have to do is walk the
blocks in reverse as well.

Reviewed-by: Francisco Jerez <[email protected]>

3 files changed, 16 insertions, 29 deletions

diff --git a/src/mesa/drivers/dri/i965/brw_cfg.h b/src/mesa/drivers/dri/i965/brw_cfg.h
index 69e39e8964d..405020b77e5 100644
--- a/src/mesa/drivers/dri/i965/brw_cfg.h
+++ b/src/mesa/drivers/dri/i965/brw_cfg.h
@@ -314,6 +314,9 @@ struct cfg_t {
 #define foreach_block_safe(__block, __cfg)                     \
    foreach_list_typed_safe (bblock_t, __block, link, &(__cfg)->block_list)
 
+#define foreach_block_reverse_safe(__block, __cfg)             \
+   foreach_list_typed_reverse_safe (bblock_t, __block, link, &(__cfg)->block_list)
+
 #define foreach_inst_in_block(__type, __inst, __block)         \
    foreach_in_list(__type, __inst, &(__block)->instructions)
 
diff --git a/src/mesa/drivers/dri/i965/brw_fs_dead_code_eliminate.cpp b/src/mesa/drivers/dri/i965/brw_fs_dead_code_eliminate.cpp
index 6b4b60224b7..bd57e09fe0c 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_dead_code_eliminate.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_dead_code_eliminate.cpp
@@ -45,13 +45,13 @@ fs_visitor::dead_code_eliminate()
    BITSET_WORD *live = ralloc_array(NULL, BITSET_WORD, BITSET_WORDS(num_vars));
    BITSET_WORD *flag_live = ralloc_array(NULL, BITSET_WORD, 1);
 
-   foreach_block (block, cfg) {
+   foreach_block_reverse_safe(block, cfg) {
       memcpy(live, live_intervals->block_data[block->num].liveout,
              sizeof(BITSET_WORD) * BITSET_WORDS(num_vars));
       memcpy(flag_live, live_intervals->block_data[block->num].flag_liveout,
              sizeof(BITSET_WORD));
 
-      foreach_inst_in_block_reverse(fs_inst, inst, block) {
+      foreach_inst_in_block_reverse_safe(fs_inst, inst, block) {
          if (inst->dst.file == VGRF && !inst->has_side_effects()) {
             bool result_live = false;
 
@@ -72,7 +72,6 @@ fs_visitor::dead_code_eliminate()
                   inst->dst = fs_reg(retype(brw_null_reg(), inst->dst.type));
                } else {
                   inst->opcode = BRW_OPCODE_NOP;
-                  continue;
                }
             }
          }
@@ -81,7 +80,6 @@ fs_visitor::dead_code_eliminate()
             if (!BITSET_TEST(flag_live, inst->flag_subreg)) {
                inst->opcode = BRW_OPCODE_NOP;
                progress = true;
-               continue;
             }
          }
 
@@ -93,7 +91,6 @@ fs_visitor::dead_code_eliminate()
              !inst->writes_accumulator) {
             inst->opcode = BRW_OPCODE_NOP;
             progress = true;
-            continue;
          }
 
          if (inst->dst.file == VGRF) {
@@ -109,9 +106,10 @@ fs_visitor::dead_code_eliminate()
             BITSET_CLEAR(flag_live, inst->flag_subreg);
          }
 
-         /* Don't mark dead instructions' sources as live */
-         if (inst->opcode == BRW_OPCODE_NOP)
+         if (inst->opcode == BRW_OPCODE_NOP) {
+            inst->remove(block);
             continue;
+         }
 
          for (int i = 0; i < inst->sources; i++) {
             if (inst->src[i].file == VGRF) {
@@ -132,15 +130,8 @@ fs_visitor::dead_code_eliminate()
    ralloc_free(live);
    ralloc_free(flag_live);
 
-   if (progress) {
-      foreach_block_and_inst_safe (block, backend_instruction, inst, cfg) {
-         if (inst->opcode == BRW_OPCODE_NOP) {
-            inst->remove(block);
-         }
-      }
-
+   if (progress)
       invalidate_live_intervals();
-   }
 
    return progress;
 }
diff --git a/src/mesa/drivers/dri/i965/brw_vec4_dead_code_eliminate.cpp b/src/mesa/drivers/dri/i965/brw_vec4_dead_code_eliminate.cpp
index 369941bb71e..2d0722aa1eb 100644
--- a/src/mesa/drivers/dri/i965/brw_vec4_dead_code_eliminate.cpp
+++ b/src/mesa/drivers/dri/i965/brw_vec4_dead_code_eliminate.cpp
@@ -71,13 +71,13 @@ vec4_visitor::dead_code_eliminate()
    BITSET_WORD *live = ralloc_array(NULL, BITSET_WORD, BITSET_WORDS(num_vars));
    BITSET_WORD *flag_live = ralloc_array(NULL, BITSET_WORD, 1);
 
-   foreach_block(block, cfg) {
+   foreach_block_reverse_safe(block, cfg) {
       memcpy(live, live_intervals->block_data[block->num].liveout,
              sizeof(BITSET_WORD) * BITSET_WORDS(num_vars));
       memcpy(flag_live, live_intervals->block_data[block->num].flag_liveout,
              sizeof(BITSET_WORD));
 
-      foreach_inst_in_block_reverse(vec4_instruction, inst, block) {
+      foreach_inst_in_block_reverse_safe(vec4_instruction, inst, block) {
          if ((inst->dst.file == VGRF && !inst->has_side_effects()) ||
              (inst->dst.is_null() && inst->writes_flag())){
             bool result_live[4] = { false };
@@ -115,7 +115,7 @@ vec4_visitor::dead_code_eliminate()
                         inst->dst = dst_reg(retype(brw_null_reg(), inst->dst.type));
                      } else {
                         inst->opcode = BRW_OPCODE_NOP;
-                        continue;
+                        break;
                      }
                   }
                }
@@ -130,7 +130,6 @@ vec4_visitor::dead_code_eliminate()
             if (!combined_live) {
                inst->opcode = BRW_OPCODE_NOP;
                progress = true;
-               continue;
             }
          }
 
@@ -150,9 +149,10 @@ vec4_visitor::dead_code_eliminate()
                BITSET_CLEAR(flag_live, c);
          }
 
-         /* Don't mark dead instructions' sources as live */
-         if (inst->opcode == BRW_OPCODE_NOP)
+         if (inst->opcode == BRW_OPCODE_NOP) {
+            inst->remove(block);
             continue;
+         }
 
          for (int i = 0; i < 3; i++) {
             if (inst->src[i].file == VGRF) {
@@ -176,15 +176,8 @@ vec4_visitor::dead_code_eliminate()
    ralloc_free(live);
    ralloc_free(flag_live);
 
-   if (progress) {
-      foreach_block_and_inst_safe(block, backend_instruction, inst, cfg) {
-         if (inst->opcode == BRW_OPCODE_NOP) {
-            inst->remove(block);
-         }
-      }
-
+   if (progress)
       invalidate_live_intervals();
-   }
 
    return progress;
 }