From 3a20ef4a3299fddc886f9d5908d8b3952dd63a54 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Daniel=20Sch=C3=BCrmann?= Date: Sat, 19 Oct 2019 16:11:13 +0200 Subject: [PATCH] aco: refactor value numbering Previously, we used one hashset per BB, so that we could always initialize the current hashset from the immediate dominator. This patch changes the behavior to a single hashmap using the block index per instruction to resolve dominance. Reviewed-by: Rhys Perry --- src/amd/compiler/aco_opt_value_numbering.cpp | 108 +++++++++---------- 1 file changed, 53 insertions(+), 55 deletions(-) diff --git a/src/amd/compiler/aco_opt_value_numbering.cpp b/src/amd/compiler/aco_opt_value_numbering.cpp index 856f7d7bf6c..e19f125e29f 100644 --- a/src/amd/compiler/aco_opt_value_numbering.cpp +++ b/src/amd/compiler/aco_opt_value_numbering.cpp @@ -23,8 +23,7 @@ */ #include -#include - +#include #include "aco_ir.h" /* @@ -88,7 +87,8 @@ struct InstrPred { * v_readlane_b32 and because discards affect the result */ if (a->opcode == aco_opcode::v_readfirstlane_b32 || a->opcode == aco_opcode::v_readlane_b32 || a->opcode == aco_opcode::ds_bpermute_b32 || a->opcode == aco_opcode::ds_permute_b32 || - a->opcode == aco_opcode::ds_swizzle_b32 || a->format == Format::PSEUDO_REDUCTION) { + a->opcode == aco_opcode::ds_swizzle_b32 || a->format == Format::PSEUDO_REDUCTION || + a->opcode == aco_opcode::p_phi || a->opcode == aco_opcode::p_linear_phi) { if (a->pass_flags != b->pass_flags) return false; } @@ -239,47 +239,42 @@ struct InstrPred { } }; +using expr_set = std::unordered_map; + +struct vn_ctx { + Program* program; + expr_set expr_values; + std::map renames; + uint32_t exec_id = 0; -typedef std::unordered_set expr_set; + vn_ctx(Program* program) : program(program) {} +}; -void process_block(Block& block, - expr_set& expr_values, - std::map& renames, - uint32_t *exec_id) +bool dominates(vn_ctx& ctx, uint32_t parent, uint32_t child) +{ + while (parent < child) + child = ctx.program->blocks[child].logical_idom; + + return parent == child; +} + +void process_block(vn_ctx& ctx, Block& block) { - bool run = false; - std::vector>::iterator it = block.instructions.begin(); std::vector> new_instructions; new_instructions.reserve(block.instructions.size()); - expr_set phi_values; - while (it != block.instructions.end()) { - aco_ptr& instr = *it; + for (aco_ptr& instr : block.instructions) { /* first, rename operands */ for (Operand& op : instr->operands) { if (!op.isTemp()) continue; - auto it = renames.find(op.tempId()); - if (it != renames.end()) + auto it = ctx.renames.find(op.tempId()); + if (it != ctx.renames.end()) op.setTemp(it->second); } - if (instr->definitions.empty() || !run) { - if (instr->opcode == aco_opcode::p_logical_start) - run = true; - else if (instr->opcode == aco_opcode::p_logical_end) - run = false; - else if (instr->opcode == aco_opcode::p_phi || instr->opcode == aco_opcode::p_linear_phi) { - std::pair res = phi_values.emplace(instr.get()); - if (!res.second) { - Instruction* orig_phi = *(res.first); - renames.emplace(instr->definitions[0].tempId(), orig_phi->definitions[0].getTemp()).second; - ++it; - continue; - } - } + if (instr->definitions.empty()) { new_instructions.emplace_back(std::move(instr)); - ++it; continue; } @@ -287,32 +282,37 @@ void process_block(Block& block, if ((instr->opcode == aco_opcode::s_mov_b32 || instr->opcode == aco_opcode::s_mov_b64 || instr->opcode == aco_opcode::v_mov_b32) && !instr->definitions[0].isFixed() && instr->operands[0].isTemp() && instr->operands[0].regClass() == instr->definitions[0].regClass() && !instr->isDPP() && !((int)instr->format & (int)Format::SDWA)) { - renames[instr->definitions[0].tempId()] = instr->operands[0].getTemp(); + ctx.renames[instr->definitions[0].tempId()] = instr->operands[0].getTemp(); } if (instr->opcode == aco_opcode::p_discard_if || instr->opcode == aco_opcode::p_demote_to_helper) - (*exec_id)++; - - instr->pass_flags = *exec_id; + ctx.exec_id++; - std::pair res = expr_values.emplace(instr.get()); + instr->pass_flags = ctx.exec_id; + std::pair res = ctx.expr_values.emplace(instr.get(), block.index); /* if there was already an expression with the same value number */ if (!res.second) { - Instruction* orig_instr = *(res.first); + Instruction* orig_instr = res.first->first; assert(instr->definitions.size() == orig_instr->definitions.size()); - for (unsigned i = 0; i < instr->definitions.size(); i++) { - assert(instr->definitions[i].regClass() == orig_instr->definitions[i].regClass()); - renames.emplace(instr->definitions[i].tempId(), orig_instr->definitions[i].getTemp()).second; + /* check if the original instruction dominates the current one */ + if (dominates(ctx, res.first->second, block.index)) { + for (unsigned i = 0; i < instr->definitions.size(); i++) { + assert(instr->definitions[i].regClass() == orig_instr->definitions[i].regClass()); + ctx.renames[instr->definitions[i].tempId()] = orig_instr->definitions[i].getTemp(); + } + } else { + ctx.expr_values.erase(res.first); + ctx.expr_values.emplace(instr.get(), block.index); + new_instructions.emplace_back(std::move(instr)); } } else { new_instructions.emplace_back(std::move(instr)); } - ++it; } - block.instructions.swap(new_instructions); + block.instructions = std::move(new_instructions); } void rename_phi_operands(Block& block, std::map& renames) @@ -335,24 +335,22 @@ void rename_phi_operands(Block& block, std::map& renames) void value_numbering(Program* program) { - std::vector expr_values(program->blocks.size()); - std::map renames; - uint32_t exec_id = 0; + vn_ctx ctx(program); for (Block& block : program->blocks) { - if (block.logical_idom != -1) { - /* initialize expr_values from idom */ - expr_values[block.index] = expr_values[block.logical_idom]; - process_block(block, expr_values[block.index], renames, &exec_id); - } else { - expr_set empty; - process_block(block, empty, renames, &exec_id); - } - exec_id++; + if (block.logical_idom != -1) + process_block(ctx, block); + else + rename_phi_operands(block, ctx.renames); + + ctx.exec_id++; } - for (Block& block : program->blocks) - rename_phi_operands(block, renames); + /* rename loop header phi operands */ + for (Block& block : program->blocks) { + if (block.kind & block_kind_loop_header) + rename_phi_operands(block, ctx.renames); + } } } -- 2.30.2