[Mesa-dev] [PATCH 10/15] i965/fs: Add a pass to remove dead control flow.
Matt Turner
mattst88 at gmail.com
Mon Oct 28 19:31:34 CET 2013
Removes if/endif and if/else/endif.
total instructions in shared programs: 1293990 -> 1288172 (-0.45%)
instructions in affected programs: 95390 -> 89572 (-6.10%)
---
src/mesa/drivers/dri/i965/Makefile.sources | 1 +
src/mesa/drivers/dri/i965/brw_fs.cpp | 1 +
src/mesa/drivers/dri/i965/brw_fs.h | 1 +
.../drivers/dri/i965/brw_fs_dead_control_flow.cpp | 80 +++++++++++++++++++
src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp | 93 +++++++++++++++++-----
5 files changed, 154 insertions(+), 22 deletions(-)
create mode 100644 src/mesa/drivers/dri/i965/brw_fs_dead_control_flow.cpp
diff --git a/src/mesa/drivers/dri/i965/Makefile.sources b/src/mesa/drivers/dri/i965/Makefile.sources
index 5ddb421..37a8380 100644
--- a/src/mesa/drivers/dri/i965/Makefile.sources
+++ b/src/mesa/drivers/dri/i965/Makefile.sources
@@ -56,6 +56,7 @@ i965_FILES = \
brw_fs_channel_expressions.cpp \
brw_fs_copy_propagation.cpp \
brw_fs_cse.cpp \
+ brw_fs_dead_control_flow.cpp \
brw_fs_fp.cpp \
brw_fs_generator.cpp \
brw_fs_live_variables.cpp \
diff --git a/src/mesa/drivers/dri/i965/brw_fs.cpp b/src/mesa/drivers/dri/i965/brw_fs.cpp
index d3d2e44..2821170 100644
--- a/src/mesa/drivers/dri/i965/brw_fs.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs.cpp
@@ -3134,6 +3134,7 @@ fs_visitor::run()
progress = opt_peephole_sel() || progress;
progress = dead_code_eliminate() || progress;
progress = dead_code_eliminate_local() || progress;
+ progress = dead_control_flow_eliminate() || progress;
progress = register_coalesce() || progress;
progress = register_coalesce_2() || progress;
progress = compute_to_mrf() || progress;
diff --git a/src/mesa/drivers/dri/i965/brw_fs.h b/src/mesa/drivers/dri/i965/brw_fs.h
index a67ef86..208d3ab 100644
--- a/src/mesa/drivers/dri/i965/brw_fs.h
+++ b/src/mesa/drivers/dri/i965/brw_fs.h
@@ -318,6 +318,7 @@ public:
bool compute_to_mrf();
bool dead_code_eliminate();
bool dead_code_eliminate_local();
+ bool dead_control_flow_eliminate();
bool remove_dead_constants();
bool remove_duplicate_mrf_writes();
bool virtual_grf_interferes(int a, int b);
diff --git a/src/mesa/drivers/dri/i965/brw_fs_dead_control_flow.cpp b/src/mesa/drivers/dri/i965/brw_fs_dead_control_flow.cpp
new file mode 100644
index 0000000..4e8fdcd
--- /dev/null
+++ b/src/mesa/drivers/dri/i965/brw_fs_dead_control_flow.cpp
@@ -0,0 +1,80 @@
+/*
+ * Copyright © 2013 Intel 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.
+ */
+
+/** @file brw_fs_dead_control_flow.cpp
+ *
+ * This file implements the dead control flow elimination optimization pass.
+ */
+
+#include "brw_fs.h"
+#include "brw_cfg.h"
+
+/* Look for and eliminate dead control flow:
+ *
+ * - if/endif
+ * - if/else/endif
+ */
+bool
+fs_visitor::dead_control_flow_eliminate()
+{
+ bool progress = false;
+
+ cfg_t cfg(this);
+
+ for (int b = 0; b < cfg.num_blocks; b++) {
+ bblock_t *block = cfg.blocks[b];
+ bool found = false;
+
+ /* ENDIF instructions, by definition, can only be found at the ends of
+ * basic blocks.
+ */
+ fs_inst *endif_inst = (fs_inst *) block->end;
+ if (endif_inst->opcode != BRW_OPCODE_ENDIF)
+ continue;
+
+ fs_inst *if_inst = NULL, *else_inst = NULL;
+ fs_inst *prev_inst = (fs_inst *) endif_inst->prev;
+ if (prev_inst->opcode == BRW_OPCODE_IF) {
+ if_inst = prev_inst;
+ found = true;
+ } else if (prev_inst->opcode == BRW_OPCODE_ELSE) {
+ else_inst = prev_inst;
+
+ prev_inst = (fs_inst *) prev_inst->prev;
+ if (prev_inst->opcode == BRW_OPCODE_IF) {
+ if_inst = prev_inst;
+ found = true;
+ }
+ }
+
+ if (found) {
+ if_inst->remove();
+ if (else_inst)
+ else_inst->remove();
+ endif_inst->remove();
+ progress = true;
+ }
+ }
+
+ return progress;
+}
diff --git a/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp b/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
index 11c3677..8638f43 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_sel_peephole.cpp
@@ -34,32 +34,84 @@
#define MAX_MOVS 8 /**< The maximum number of MOVs to attempt to match. */
/**
+ * For a given control flow graph <cfg> and number <start_block> of the basic
+ * block ending with an ENDIF instruction, return pointers to the associated
+ * IF and ELSE instructions.
+ *
+ * If no ELSE instruction is found before the associated IF, return false.
+ * Otherwise return true.
+ */
+static bool
+find_if_else_from_endif(const cfg_t *cfg, int start_block,
+ fs_inst **if_inst, fs_inst **else_inst)
+{
+ assert(start_block > 0);
+ assert(if_inst);
+ assert(else_inst);
+
+ *if_inst = NULL;
+ *else_inst = NULL;
+
+ int depth = 0;
+ for (int b = start_block - 1; b >= 0; b--) {
+ bblock_t *block = cfg->blocks[b];
+
+ switch (block->end->opcode) {
+ case BRW_OPCODE_IF:
+ if (depth == 0) {
+ *if_inst = (fs_inst *) block->end;
+ return *else_inst != NULL;
+ }
+ depth--;
+ break;
+ case BRW_OPCODE_ELSE:
+ if (depth == 0) {
+ *else_inst = (fs_inst *) block->end;
+ }
+ /* No change in depth */
+ break;
+ case BRW_OPCODE_ENDIF:
+ case BRW_OPCODE_WHILE:
+ depth++;
+ break;
+ case BRW_OPCODE_DO:
+ depth--;
+ break;
+ default:
+ break;
+ }
+ }
+
+ return false;
+}
+
+/**
* Scans backwards from an ENDIF counting MOV instructions with common
* destinations inside the "then" and "else" blocks of the if statement.
*
- * A pointer to the fs_inst* for ENDIF is passed as the <match> argument. The
- * function stores pointers to the MOV instructions in the <then_mov> and
- * <else_mov> arrays. If the function is successful, the <match> points to the
- * fs_inst* pointing to the IF instruction at the beginning of the block.
+ * A pointer to the fs_inst* for ENDIF is passed as the <endif_inst> argument.
+ * The function stores pointers to the MOV instructions in the <then_mov> and
+ * <else_mov> arrays.
*
* \return the number of MOVs to a common destination found in the two branches
- * or zero if an error occurred.
*
* E.g.:
- * match = IF ...
+ * IF ...
+ * then_mov[2] = MOV g2, ...
* then_mov[1] = MOV g4, ...
* then_mov[0] = MOV g5, ...
* ELSE ...
+ * then_mov[2] = MOV g3, ...
* else_mov[1] = MOV g4, ...
* else_mov[0] = MOV g5, ...
* ENDIF
- * returns 2.
+ * returns 2 (since only the first two MOVs have a common destination)
*/
static int
match_movs_from_endif(fs_inst *then_mov[MAX_MOVS], fs_inst *else_mov[MAX_MOVS],
- fs_inst **match)
+ fs_inst *endif_inst, fs_inst *else_inst)
{
- fs_inst *m = *match;
+ fs_inst *m = endif_inst;
assert(m->opcode == BRW_OPCODE_ENDIF);
m = (fs_inst *) m->prev;
@@ -71,9 +123,7 @@ match_movs_from_endif(fs_inst *then_mov[MAX_MOVS], fs_inst *else_mov[MAX_MOVS],
else_movs++;
}
- if (m->opcode != BRW_OPCODE_ELSE)
- return 0;
- m = (fs_inst *) m->prev;
+ m = (fs_inst *) else_inst->prev;
int then_movs = 0;
while (then_movs < MAX_MOVS && m->opcode == BRW_OPCODE_MOV) {
@@ -82,10 +132,6 @@ match_movs_from_endif(fs_inst *then_mov[MAX_MOVS], fs_inst *else_mov[MAX_MOVS],
then_movs++;
}
- if (m->opcode != BRW_OPCODE_IF)
- return 0;
-
- *match = m;
return MIN2(then_movs, else_movs);
}
@@ -134,7 +180,7 @@ fs_visitor::opt_peephole_sel()
bblock_t *block = cfg.blocks[b];
int movs;
- fs_inst *if_inst, *endif_inst;
+ fs_inst *if_inst, *else_inst, *endif_inst;
fs_inst *start;
fs_inst *else_mov[MAX_MOVS] = { NULL };
fs_inst *then_mov[MAX_MOVS] = { NULL };
@@ -145,14 +191,17 @@ fs_visitor::opt_peephole_sel()
*/
start = (fs_inst *) block->end;
if (start->opcode == BRW_OPCODE_ENDIF) {
- fs_inst *match = endif_inst = start;
+ endif_inst = start;
+
+ /* Find the associated IF and ELSE instructions for our ENDIF. */
+ if (!find_if_else_from_endif(&cfg, b, &if_inst, &else_inst))
+ continue;
/* Find MOVs to a common destination. */
- movs = match_movs_from_endif(then_mov, else_mov, &match);
+ movs = match_movs_from_endif(then_mov, else_mov, start, else_inst);
+
if (movs == 0)
continue;
-
- if_inst = match;
} else {
continue;
}
@@ -171,7 +220,7 @@ fs_visitor::opt_peephole_sel()
if (!then_mov[i]->dst.equals(else_mov[i]->dst) ||
then_mov[i]->is_partial_write() ||
else_mov[i]->is_partial_write()) {
- bb_progress = false;
+ movs = i;
break;
}
--
1.8.3.2
More information about the mesa-dev
mailing list