[Mesa-dev] [PATCH 11/16] i965/fs: Add local value numbering optimization pass.
Jordan Justen
jljusten at gmail.com
Fri Jan 17 13:08:20 PST 2014
On Thu, Dec 19, 2013 at 1:40 PM, Matt Turner <mattst88 at gmail.com> wrote:
Could you add some commit message text?
Maybe with a small example.
> 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).
Maybe duplicate the commit message summary/example here?
> + */
> +
> +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.
> + */
How about:
"Let's not consider writes to the accumulator for now."
> + } 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);
> + }
Is this debug code likely to be useful going forward, or maybe it was
mostly helpful during initial development?
Aside from questions in this and my other email:
Reviewed-by: Jordan Justen <jordan.l.justen at intel.com>
> +
> + _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
>
> _______________________________________________
> mesa-dev mailing list
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list