summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Schürmann <daniel@schuermann.dev>2019-10-19 16:11:13 +0200
committerDaniel Schürmann <daniel@schuermann.dev>2019-10-22 17:18:59 +0200
commit3a20ef4a3299fddc886f9d5908d8b3952dd63a54 (patch)
tree468bc388170d98658dbdf6773fe2a4688e3145d9
parent3a71e1d27b041853d5cb5c56c2f143a2e18d476f (diff)
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 <pendingchaos02@gmail.com>
-rw-r--r--src/amd/compiler/aco_opt_value_numbering.cpp108
1 files 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 <map>
-#include <unordered_set>
-
+#include <unordered_map>
#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<Instruction*, uint32_t, InstrHash, InstrPred>;
+
+struct vn_ctx {
+ Program* program;
+ expr_set expr_values;
+ std::map<uint32_t, Temp> renames;
+ uint32_t exec_id = 0;
-typedef std::unordered_set<Instruction*, InstrHash, InstrPred> expr_set;
+ vn_ctx(Program* program) : program(program) {}
+};
-void process_block(Block& block,
- expr_set& expr_values,
- std::map<uint32_t, Temp>& 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<aco_ptr<Instruction>>::iterator it = block.instructions.begin();
std::vector<aco_ptr<Instruction>> new_instructions;
new_instructions.reserve(block.instructions.size());
- expr_set phi_values;
- while (it != block.instructions.end()) {
- aco_ptr<Instruction>& instr = *it;
+ for (aco_ptr<Instruction>& 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<expr_set::iterator, bool> 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<expr_set::iterator, bool> res = expr_values.emplace(instr.get());
+ instr->pass_flags = ctx.exec_id;
+ std::pair<expr_set::iterator, bool> 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<uint32_t, Temp>& renames)
@@ -335,24 +335,22 @@ void rename_phi_operands(Block& block, std::map<uint32_t, Temp>& renames)
void value_numbering(Program* program)
{
- std::vector<expr_set> expr_values(program->blocks.size());
- std::map<uint32_t, Temp> 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);
+ }
}
}