[Mesa-dev] [PATCH 11/16] i965/fs: Add local value numbering optimization pass.
Matt Turner
mattst88 at gmail.com
Thu Dec 19 13:40:25 PST 2013
total instructions in shared programs: 1520829 -> 1511991 (-0.58%)
instructions in affected programs: 559725 -> 550887 (-1.58%)
GAINED: 6
LOST: 9
---
src/mesa/drivers/dri/i965/Makefile.sources | 1 +
src/mesa/drivers/dri/i965/brw_fs.cpp | 37 +-
src/mesa/drivers/dri/i965/brw_fs.h | 1 +
.../drivers/dri/i965/brw_fs_value_numbering.cpp | 398 +++++++++++++++++++++
4 files changed, 435 insertions(+), 2 deletions(-)
create mode 100644 src/mesa/drivers/dri/i965/brw_fs_value_numbering.cpp
diff --git a/src/mesa/drivers/dri/i965/Makefile.sources b/src/mesa/drivers/dri/i965/Makefile.sources
index 43f152e..36d8261 100644
--- a/src/mesa/drivers/dri/i965/Makefile.sources
+++ b/src/mesa/drivers/dri/i965/Makefile.sources
@@ -63,6 +63,7 @@ i965_FILES = \
brw_fs_peephole_predicated_break.cpp \
brw_fs_reg_allocate.cpp \
brw_fs_sel_peephole.cpp \
+ brw_fs_value_numbering.cpp \
brw_fs_vector_splitting.cpp \
brw_fs_visitor.cpp \
brw_gs.c \
diff --git a/src/mesa/drivers/dri/i965/brw_fs.cpp b/src/mesa/drivers/dri/i965/brw_fs.cpp
index e4a4737..08837da 100644
--- a/src/mesa/drivers/dri/i965/brw_fs.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs.cpp
@@ -3285,9 +3285,11 @@ fs_visitor::run()
remove_dead_constants();
setup_pull_constants();
- bool progress;
+ bool progress, cp_progress, vn_progress;
do {
progress = false;
+ cp_progress = false;
+ vn_progress = false;
compact_virtual_grfs();
@@ -3295,16 +3297,47 @@ fs_visitor::run()
progress = opt_algebraic() || progress;
progress = opt_cse() || progress;
- progress = opt_copy_propagate() || progress;
progress = opt_peephole_predicated_break() || progress;
+ cp_progress = opt_copy_propagate();
progress = dead_code_eliminate() || progress;
progress = dead_code_eliminate_local() || progress;
progress = opt_peephole_sel() || progress;
progress = dead_control_flow_eliminate(this) || progress;
+ vn_progress = opt_value_numbering();
progress = register_coalesce() || progress;
progress = compute_to_mrf() || progress;
+
+ /* Value numbering rewrites
+ *
+ * MOV g5, 1.0F
+ * MOV g6, 1.0F
+ *
+ * into
+ *
+ * MOV g5, 1.0F
+ * MOV g6, g5
+ *
+ * but constant propagation undoes this. If these were the only two
+ * passes to make progress, they're just fighting.
+ */
+ if (!progress && (cp_progress != vn_progress)) {
+ progress = true;
+ }
} while (progress);
+ /* Copy propagation and value numbering were fighting, which means that
+ * the last changes made by value numbering weren't useful, so rerun
+ * copy propagation and the rest of the optimizations after it, modulo
+ * value numbering.
+ */
+ if (cp_progress && vn_progress) {
+ opt_copy_propagate();
+ dead_code_eliminate();
+ dead_code_eliminate_local();
+ register_coalesce();
+ compute_to_mrf();
+ }
+
lower_uniform_pull_constant_loads();
assign_curb_setup();
diff --git a/src/mesa/drivers/dri/i965/brw_fs.h b/src/mesa/drivers/dri/i965/brw_fs.h
index 853cf3c..75de18e 100644
--- a/src/mesa/drivers/dri/i965/brw_fs.h
+++ b/src/mesa/drivers/dri/i965/brw_fs.h
@@ -312,6 +312,7 @@ public:
bool opt_algebraic();
bool opt_cse();
bool opt_cse_local(bblock_t *block, exec_list *aeb);
+ bool opt_value_numbering();
bool opt_copy_propagate();
bool try_copy_propagate(fs_inst *inst, int arg, acp_entry *entry);
bool try_constant_propagate(fs_inst *inst, acp_entry *entry);
diff --git a/src/mesa/drivers/dri/i965/brw_fs_value_numbering.cpp b/src/mesa/drivers/dri/i965/brw_fs_value_numbering.cpp
new file mode 100644
index 0000000..fc7299c
--- /dev/null
+++ b/src/mesa/drivers/dri/i965/brw_fs_value_numbering.cpp
@@ -0,0 +1,398 @@
+/*
+ * 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.
+ */
+
+#include "brw_fs.h"
+#include "brw_cfg.h"
+#include "main/hash_table.h"
+
+/** @file brw_fs_value_numbering.cpp
+ *
+ * Support for local value numbering.
+ *
+ * See Cooper and Torczon's Engineering a Compiler [first edition], section
+ * 8.3.2 (p398).
+ */
+
+static bool debug = false;
+
+struct value_numbering_hash_key {
+ /* For variables and constants, <opcode> is 0. For an expression, it is the
+ * opcode of the instruction.
+ */
+ enum opcode opcode;
+
+ /* For expressions, value_number[] contains the value numbers of the
+ * sources. If a source is NULL, a value number of 0 is used.
+ */
+ int value_number[3];
+
+ /* Otherwise a copy of a variable or constant is stored in <src>. <src> and
+ * <value_number> cannot be in a union, because C++ does not allow non-POD
+ * types to be a union.
+ */
+ fs_reg src;
+
+ /* Value number for the flag register. */
+ int flag_value_number;
+
+ bool predicate;
+ bool predicate_inverse;
+};
+
+struct value_numbering_hash_data {
+ /* Pointer to the key of the instruction that generated this value number,
+ * or NULL if the value number was assigned to a source value.
+ *
+ * Used to find and remove the instruction that previously wrote to this
+ * destination when its entry is no longer valid.
+ *
+ * We must store a pointer to the key, rather than the hash or a pointer to
+ * the entry itself, since these may not be valid after calls to
+ * _mesa_hash_table_insert().
+ */
+ struct value_numbering_hash_key *inst_key;
+
+ /* Pointer to instruction that generated the value numbered by the
+ * <value_number> field.
+ */
+ fs_inst *inst;
+ int value_number;
+};
+
+static bool
+value_numbering_hash_compare(const void *a, const void *b)
+{
+ return memcmp(a, b, sizeof(struct value_numbering_hash_key)) == 0;
+}
+
+/* Returns a pointer to the value_numbering_hash_data corresponding to the
+ * <key> in the hash table <ht>. If a key:value pair does not already exist,
+ * a new one will be allocated.
+ */
+static struct value_numbering_hash_data *
+value_numbering_hash_get_data(struct hash_table *ht,
+ struct value_numbering_hash_key *key)
+{
+ uint32_t hash = _mesa_hash_data(key,
+ sizeof(struct value_numbering_hash_key));
+ struct hash_entry *entry = _mesa_hash_table_search(ht, hash, key);
+ struct value_numbering_hash_data *data;
+
+ if (entry) {
+ data = (struct value_numbering_hash_data *)entry->data;
+ } else {
+ data = rzalloc(ht, struct value_numbering_hash_data);
+
+ _mesa_hash_table_insert(ht, hash, key, data);
+ }
+
+ return data;
+}
+
+/* Sorts the value numbers of the source arguments of commutative operations
+ * so that for instance
+ *
+ * add ... g10 g11
+ * add ... g11 g10
+ *
+ * will be recognized as identical expressions.
+ */
+static void
+sort_src_value_numbers(struct value_numbering_hash_key *key)
+{
+ int min, max;
+
+ switch (key->opcode) {
+ case BRW_OPCODE_AND:
+ case BRW_OPCODE_OR:
+ case BRW_OPCODE_XOR:
+ case BRW_OPCODE_ADD:
+ case BRW_OPCODE_MUL:
+ min = MIN2(key->value_number[0], key->value_number[1]);
+ max = MAX2(key->value_number[0], key->value_number[1]);
+ key->value_number[0] = min;
+ key->value_number[1] = max;
+ break;
+ case BRW_OPCODE_MAD:
+ min = MIN2(key->value_number[1], key->value_number[2]);
+ max = MAX2(key->value_number[1], key->value_number[2]);
+ key->value_number[1] = min;
+ key->value_number[2] = max;
+ break;
+ default:
+ break;
+ }
+}
+
+/* Performs local value numbering. */
+static bool
+opt_value_numbering_local(fs_visitor *v, bblock_t *block)
+{
+ bool progress = false;
+ void *mem_ctx = ralloc_context(v->mem_ctx);
+
+ /* The hash table that will hold the value numbers for expressions,
+ * constants, and variables in the current basic block.
+ */
+ struct hash_table *ht =
+ _mesa_hash_table_create(mem_ctx, value_numbering_hash_compare);
+ int value_number = 1;
+
+ for (fs_inst *inst = (fs_inst *)block->start;
+ inst != block->end->next;
+ inst = (fs_inst *) inst->next) {
+ if (inst->mlen > 0)
+ continue;
+ switch (inst->opcode) {
+ case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD:
+ case FS_OPCODE_UNIFORM_PULL_CONSTANT_LOAD_GEN7:
+ case FS_OPCODE_VARYING_PULL_CONSTANT_LOAD:
+ case FS_OPCODE_VARYING_PULL_CONSTANT_LOAD_GEN7:
+ continue;
+ case BRW_OPCODE_MOV:
+ if (v->virtual_grf_sizes[inst->dst.reg] != 1)
+ continue;
+ default:
+ break;
+ }
+
+ struct value_numbering_hash_key *key =
+ rzalloc(ht, struct value_numbering_hash_key);
+ key->opcode = inst->opcode;
+
+ bool skip = false;
+
+ /* Look up or assign value numbers of the operands and store them in
+ * key->value_number[].
+ */
+ for (int i = 0; i < 3; i++) {
+ /* Make sure NULL arguments get the same value number (zero). */
+ if (inst->src[i].file == BAD_FILE) {
+ key->value_number[i] = 0;
+ continue;
+
+ /* I don't want to have to think about implicit writes to the
+ * accumulator.
+ */
+ } else if (inst->src[i].file == HW_REG) {
+ skip = true;
+ break;
+ }
+
+ struct value_numbering_hash_key *operand_key =
+ rzalloc(ht, struct value_numbering_hash_key);
+ operand_key->src = inst->src[i];
+
+ struct value_numbering_hash_data *data =
+ value_numbering_hash_get_data(ht, operand_key);
+
+ /* A value number of 0 means that <data> was just rzalloc'd. Assign
+ * the operand a new value number.
+ */
+ if (data->value_number == 0) {
+ data->inst = NULL;
+ data->value_number = value_number;
+
+ value_number++;
+ }
+ key->value_number[i] = data->value_number;
+ }
+
+ if (skip) {
+ ralloc_free(key);
+ continue;
+ }
+
+ sort_src_value_numbers(key);
+
+ /* If the instruction is predicated, look up or assign a value number
+ * for the flag register and store it in key->flag_value_number.
+ */
+ if (inst->reads_flag()) {
+ struct value_numbering_hash_key *flag_key =
+ rzalloc(ht, struct value_numbering_hash_key);
+
+ /* inst->reads_flag() === (inst->predicate == true) */
+ flag_key->predicate = true;
+ flag_key->predicate_inverse = inst->predicate_inverse;
+
+ struct value_numbering_hash_data *data =
+ value_numbering_hash_get_data(ht, flag_key);
+
+ /* A value number of 0 means that <data> was just rzalloc'd. Assign
+ * the flag a new value number.
+ */
+ if (data->value_number == 0) {
+ data->inst = NULL;
+ data->value_number = value_number;
+
+ value_number++;
+ }
+ key->flag_value_number = data->value_number;
+ }
+
+ /* Calculate hash value for
+ * <VN(flag), opcode, VN(op1), VN(op2), VN(op3)>.
+ */
+ uint32_t expr_hash =
+ _mesa_hash_data(key, sizeof(struct value_numbering_hash_key));
+
+ struct hash_entry *entry = _mesa_hash_table_search(ht, expr_hash, key);
+
+ /* If the hash is already in the table, replace the expression with
+ * a MOV from the destination of the instruction that generated the
+ * value.
+ */
+ if (entry) {
+ progress = true;
+
+ struct value_numbering_hash_data *data =
+ (struct value_numbering_hash_data *)entry->data;
+
+ fs_inst *copy = v->MOV(inst->dst, data->inst->dst);
+
+ /* Copy the new MOV's predicate & predicate inverse flags unless we
+ * are copying from a SEL instruction where the predicate has another
+ * meaning.
+ *
+ * Otherwise we could incorrectly convert
+ * (-f0.0) sel g3 g2 0.0f
+ * (-f0.0) sel g4 g2 0.0f
+ * into
+ * (-f0.0) sel g3 g2 0.0f
+ * (-f0.0) mov g4 g3
+ */
+ if (inst->opcode != BRW_OPCODE_SEL) {
+ copy->predicate = inst->predicate;
+ copy->predicate_inverse = inst->predicate_inverse;
+ }
+ copy->force_writemask_all = inst->force_writemask_all;
+ inst->insert_before(copy);
+ inst->remove();
+
+ /* Appending an instruction may have changed our bblock end. */
+ if (inst == block->end) {
+ block->end = copy;
+ }
+
+ /* Continue iteration with copy->next */
+ inst = copy;
+
+ /* If not, update the value numbers of the expression's outputs. */
+ } else {
+ /* If the destination is something we can read back (i.e., GRF)
+ * store the value number.
+ */
+ if (inst->dst.file == GRF) {
+ struct value_numbering_hash_data *expr_data =
+ rzalloc(ht, struct value_numbering_hash_data);
+
+ expr_data->inst = inst;
+ expr_data->value_number = value_number;
+
+ _mesa_hash_table_insert(ht, expr_hash, key, expr_data);
+
+ /* Also assign the new value number to the destination if the
+ * destination is not null.
+ */
+ struct value_numbering_hash_key *destination_key =
+ rzalloc(ht, struct value_numbering_hash_key);
+ destination_key->src = inst->dst;
+
+ struct value_numbering_hash_data *destination =
+ value_numbering_hash_get_data(ht, destination_key);
+
+ /* Find and delete from the hash table the instruction that
+ * previously wrote to the destination, since its entry is now no
+ * longer valid.
+ */
+ if (destination->value_number != 0 && destination->inst_key) {
+ uint32_t inst_hash =
+ _mesa_hash_data(destination->inst_key,
+ sizeof(struct value_numbering_hash_key));
+
+ struct hash_entry *inst_entry =
+ _mesa_hash_table_search(ht, inst_hash,
+ destination->inst_key);
+
+ if (debug) {
+ struct value_numbering_hash_data *prev_inst_data =
+ (struct value_numbering_hash_data *)inst_entry->data;
+
+ printf("Deleting:\n\t");
+ if (prev_inst_data->inst)
+ v->dump_instruction(prev_inst_data->inst);
+ printf("in favor of:\n\t");
+ v->dump_instruction(inst);
+ }
+
+ _mesa_hash_table_remove(ht, inst_entry);
+ }
+
+ destination->inst = NULL;
+ destination->value_number = value_number;
+ destination->inst_key = key;
+
+ value_number++;
+ }
+
+ /* If the instruction writes the flag register, assign it a new
+ * value number.
+ */
+ if (inst->writes_flag()) {
+ struct value_numbering_hash_key *flag_key =
+ rzalloc(ht, struct value_numbering_hash_key);
+ flag_key->predicate = true;
+
+ struct value_numbering_hash_data *data =
+ value_numbering_hash_get_data(ht, flag_key);
+
+ data->inst = NULL;
+ data->value_number = value_number;
+
+ value_number++;
+ }
+ }
+ }
+
+ _mesa_hash_table_destroy(ht, NULL);
+
+ return progress;
+}
+
+bool
+fs_visitor::opt_value_numbering()
+{
+ bool progress = false;
+
+ cfg_t cfg(&instructions);
+
+ for (int b = 0; b < cfg.num_blocks; b++) {
+ progress = opt_value_numbering_local(this, cfg.blocks[b]) || progress;
+ }
+
+ if (progress)
+ invalidate_live_intervals();
+
+ return progress;
+}
--
1.8.3.2
More information about the mesa-dev
mailing list