src/amd/compiler/aco_repair_ssa.cpp - platform/external/mesa3d - Git at Google

 /*
  * Copyright © 2024 Valve Corporation
  *
  * SPDX-License-Identifier: MIT
  */

 #include "aco_ir.h"

 #include <functional>

 namespace aco {

 namespace {

 /**
  * This is a limited SSA repair pass which inserts the phis necessary for the definition of a
  * linear temporary to dominate it's uses in the linear CFG. The definition must still dominate it's
  * uses in the logical CFG. If a path in which the temporary is defined is not taken, the value used
  * is undefined.
  *
  * aco::lower_phis() must be run after to lower the logical phis created by this pass.
  */

 struct repair_state {
    Program* program;
    Block* block;

    std::vector<bool> block_needs_repair; /* uses in this block might need repair */
    std::vector<bool> dom_needs_repair;   /* whether a block dominates a block which needs repair */

    std::vector<bool> has_def_block;
    std::unique_ptr<uint32_t[]> def_blocks;
    std::unordered_map<uint64_t, Temp> renames;

    std::vector<aco_ptr<Instruction>> new_phis;

    std::vector<bool> visit_block;
    std::vector<Temp> temps;

    bool is_temp_defined_at_pred(uint32_t block_idx, uint32_t def_block) const
    {
       return block_idx >= def_block && visit_block[block_idx] && temps[block_idx].id();
    }
 };

 Temp
 create_phis(repair_state* state, Temp tmp, uint32_t use_block, uint32_t def_block)
 {
    Program* program = state->program;

    assert(program->blocks[def_block].logical_idom != -1);
    assert(program->blocks[use_block].logical_idom != -1);
    assert(use_block > def_block);

    std::fill(state->visit_block.begin() + def_block, state->visit_block.begin() + use_block + 1,
              false);

    for (int32_t i = use_block; i >= (int)def_block; i--) {
       bool block_needs_tmp = (uint32_t)i == use_block;
       for (uint32_t succ : program->blocks[i].logical_succs)
          block_needs_tmp |= succ > (uint32_t)i && state->visit_block[succ];
       state->visit_block[i] = block_needs_tmp;

       if (block_needs_tmp && (uint32_t)i != def_block) {
          uint64_t k = i | ((uint64_t)tmp.id() << 32);
          auto it = state->renames.find(k);
          if (it != state->renames.end())
             state->temps[i] = it->second;
          else
             state->temps[i] = Temp(0, tmp.regClass());
       }
    }

    state->temps[def_block] = tmp;
    for (uint32_t i = def_block + 1; i <= use_block; i++) {
       if (!state->visit_block[i] || state->temps[i].id())
          continue;

       Block& block = program->blocks[i];

       bool undef = true;
       for (unsigned pred : block.logical_preds)
          undef &= pred < i && !state->is_temp_defined_at_pred(pred, def_block);
       if (undef) {
          state->temps[i] = Temp(0, tmp.regClass());
          continue;
       }

       /* If a logical dominator has a temporary, we don't need to create a phi and can just use
        * that temporary instead. For linear temporaries, we also need to check if it dominates in
        * the linear CFG, because logical dominators do not necessarily dominate a block in the
        * linear CFG (for example, because of continue_or_break or empty exec skips). */
       uint32_t dom = block.index;
       bool skip_phis = false;
       do {
          dom = program->blocks[dom].logical_idom;
          if (state->is_temp_defined_at_pred(dom, def_block) &&
              dominates_linear(program->blocks[dom], block)) {
             skip_phis = true;
             break;
          }
       } while (dom != def_block);
       if (skip_phis) {
          state->temps[i] = state->temps[dom];
          continue;
       }

       /* This pass doesn't support creating loop header phis */
       assert(!(block.kind & block_kind_loop_header));

       Temp def = program->allocateTmp(tmp.regClass());
       aco_ptr<Instruction> phi{
          create_instruction(aco_opcode::p_phi, Format::PSEUDO, block.logical_preds.size(), 1)};
       for (unsigned j = 0; j < block.logical_preds.size(); j++) {
          uint32_t pred = block.logical_preds[j];
          assert(state->is_temp_defined_at_pred(pred, def_block));
          phi->operands[j] = Operand(state->temps[pred]);
       }
       phi->definitions[0] = Definition(def);

       if (&block == state->block)
          state->new_phis.emplace_back(std::move(phi));
       else
          block.instructions.emplace(block.instructions.begin(), std::move(phi));

       uint64_t k = i | ((uint64_t)tmp.id() << 32);
       state->renames.emplace(k, def);
       state->temps[i] = def;
    }

    return state->temps[use_block];
 }

 template <bool LoopHeader>
 bool
 repair_block(repair_state* state, Block& block)
 {
    bool needs_repair = state->block_needs_repair[block.index];
    bool dom_needs_repair = state->dom_needs_repair[block.index];
    bool progress = false;

    state->block = &block;
    for (aco_ptr<Instruction>& instr : block.instructions) {
       if (dom_needs_repair) {
          for (Definition def : instr->definitions) {
             if (def.isTemp()) {
                state->def_blocks[def.tempId()] = block.index;
                state->has_def_block[def.tempId()] = true;
             }
          }
       }

       bool phi = is_phi(instr) || instr->opcode == aco_opcode::p_boolean_phi;

       /* Skip the section below if we don't need to repair. If we don't need to update def_blocks
        * either, then we can just break. We always need to process phis because their actual uses
        * are in the predecessors, which might need repair. */
       if (!phi && !needs_repair) {
          if (!dom_needs_repair)
             break;
          continue;
       }

       unsigned start = 0;
       unsigned num_operands = instr->operands.size();
       if (phi && (block.kind & block_kind_loop_header)) {
          if (LoopHeader)
             start++;
          else
             num_operands = 1;
       } else if (LoopHeader) {
          break;
       }

       for (unsigned i = start; i < num_operands; i++) {
          Operand& op = instr->operands[i];
          if (!op.isTemp() || !op.getTemp().is_linear() || !state->has_def_block[op.tempId()])
             continue;

          uint32_t def_block = state->def_blocks[op.tempId()];
          uint32_t use_block = block.index;
          if (instr->opcode == aco_opcode::p_boolean_phi || instr->opcode == aco_opcode::p_phi) {
             use_block = block.logical_preds[i];
             if (!state->block_needs_repair[use_block])
                continue;
          } else if (instr->opcode == aco_opcode::p_linear_phi) {
             use_block = block.linear_preds[i];
             if (!state->block_needs_repair[use_block])
                continue;
          }

          if (!dominates_linear(state->program->blocks[def_block],
                                state->program->blocks[use_block])) {
             assert(dominates_logical(state->program->blocks[def_block],
                                      state->program->blocks[use_block]));
             op.setTemp(create_phis(state, op.getTemp(), use_block, def_block));
             progress = true;
          }
       }
    }

    /* These are inserted later to not invalidate any iterators. */
    block.instructions.insert(block.instructions.begin(),
                              std::move_iterator(state->new_phis.begin()),
                              std::move_iterator(state->new_phis.end()));
    state->new_phis.clear();

    return progress;
 }

 } /* end namespace */

 bool
 repair_ssa(Program* program)
 {
    repair_state state;
    state.program = program;

    state.block_needs_repair.resize(program->blocks.size());
    state.dom_needs_repair.resize(program->blocks.size());

    state.has_def_block.resize(program->peekAllocationId());
    state.def_blocks.reset(new uint32_t[program->peekAllocationId()]);

    state.visit_block.resize(program->blocks.size());
    state.temps.resize(program->blocks.size());

    for (Block& block : program->blocks) {
       if (block.logical_idom == -1)
          continue;

       if (state.block_needs_repair[block.logical_idom] ||
           !dominates_linear(program->blocks[block.logical_idom], block)) {
          state.block_needs_repair[block.index] = true;

          /* Set dom_needs_repair=true for logical dominators. */
          uint32_t parent = block.logical_idom;
          while (!state.dom_needs_repair[parent]) {
             state.dom_needs_repair[parent] = true;
             parent = program->blocks[parent].logical_idom;
          }
       }
    }

    std::vector<unsigned> loop_header_indices;

    bool progress = false;
    for (Block& block : program->blocks) {
       if (block.kind & block_kind_loop_header)
          loop_header_indices.push_back(block.index);

       progress |= repair_block<false>(&state, block);

       if (block.kind & block_kind_loop_exit) {
          unsigned header = loop_header_indices.back();
          loop_header_indices.pop_back();

          progress |= repair_block<true>(&state, program->blocks[header]);
       }
    }

    return progress;
 }

 } // namespace aco
	/*
	* Copyright © 2024 Valve Corporation
	*
	* SPDX-License-Identifier: MIT
	*/

	#include "aco_ir.h"

	#include <functional>

	namespace aco {

	namespace {

	/**
	* This is a limited SSA repair pass which inserts the phis necessary for the definition of a
	* linear temporary to dominate it's uses in the linear CFG. The definition must still dominate it's
	* uses in the logical CFG. If a path in which the temporary is defined is not taken, the value used
	* is undefined.
	*
	* aco::lower_phis() must be run after to lower the logical phis created by this pass.
	*/

	struct repair_state {
	Program* program;
	Block* block;

	std::vector<bool> block_needs_repair; /* uses in this block might need repair */
	std::vector<bool> dom_needs_repair; /* whether a block dominates a block which needs repair */

	std::vector<bool> has_def_block;
	std::unique_ptr<uint32_t[]> def_blocks;
	std::unordered_map<uint64_t, Temp> renames;

	std::vector<aco_ptr<Instruction>> new_phis;

	std::vector<bool> visit_block;
	std::vector<Temp> temps;

	bool is_temp_defined_at_pred(uint32_t block_idx, uint32_t def_block) const
	{
	return block_idx >= def_block && visit_block[block_idx] && temps[block_idx].id();
	}
	};

	Temp
	create_phis(repair_state* state, Temp tmp, uint32_t use_block, uint32_t def_block)
	{
	Program* program = state->program;

	assert(program->blocks[def_block].logical_idom != -1);
	assert(program->blocks[use_block].logical_idom != -1);
	assert(use_block > def_block);

	std::fill(state->visit_block.begin() + def_block, state->visit_block.begin() + use_block + 1,
	false);

	for (int32_t i = use_block; i >= (int)def_block; i--) {
	bool block_needs_tmp = (uint32_t)i == use_block;
	for (uint32_t succ : program->blocks[i].logical_succs)
	block_needs_tmp \|= succ > (uint32_t)i && state->visit_block[succ];
	state->visit_block[i] = block_needs_tmp;

	if (block_needs_tmp && (uint32_t)i != def_block) {
	uint64_t k = i \| ((uint64_t)tmp.id() << 32);
	auto it = state->renames.find(k);
	if (it != state->renames.end())
	state->temps[i] = it->second;
	else
	state->temps[i] = Temp(0, tmp.regClass());
	}
	}

	state->temps[def_block] = tmp;
	for (uint32_t i = def_block + 1; i <= use_block; i++) {
	if (!state->visit_block[i] \|\| state->temps[i].id())
	continue;

	Block& block = program->blocks[i];

	bool undef = true;
	for (unsigned pred : block.logical_preds)
	undef &= pred < i && !state->is_temp_defined_at_pred(pred, def_block);
	if (undef) {
	state->temps[i] = Temp(0, tmp.regClass());
	continue;
	}

	/* If a logical dominator has a temporary, we don't need to create a phi and can just use
	* that temporary instead. For linear temporaries, we also need to check if it dominates in
	* the linear CFG, because logical dominators do not necessarily dominate a block in the
	* linear CFG (for example, because of continue_or_break or empty exec skips). */
	uint32_t dom = block.index;
	bool skip_phis = false;
	do {
	dom = program->blocks[dom].logical_idom;
	if (state->is_temp_defined_at_pred(dom, def_block) &&
	dominates_linear(program->blocks[dom], block)) {
	skip_phis = true;
	break;
	}
	} while (dom != def_block);
	if (skip_phis) {
	state->temps[i] = state->temps[dom];
	continue;
	}

	/* This pass doesn't support creating loop header phis */
	assert(!(block.kind & block_kind_loop_header));

	Temp def = program->allocateTmp(tmp.regClass());
	aco_ptr<Instruction> phi{
	create_instruction(aco_opcode::p_phi, Format::PSEUDO, block.logical_preds.size(), 1)};
	for (unsigned j = 0; j < block.logical_preds.size(); j++) {
	uint32_t pred = block.logical_preds[j];
	assert(state->is_temp_defined_at_pred(pred, def_block));
	phi->operands[j] = Operand(state->temps[pred]);
	}
	phi->definitions[0] = Definition(def);

	if (&block == state->block)
	state->new_phis.emplace_back(std::move(phi));
	else
	block.instructions.emplace(block.instructions.begin(), std::move(phi));

	uint64_t k = i \| ((uint64_t)tmp.id() << 32);
	state->renames.emplace(k, def);
	state->temps[i] = def;
	}

	return state->temps[use_block];
	}

	template <bool LoopHeader>
	bool
	repair_block(repair_state* state, Block& block)
	{
	bool needs_repair = state->block_needs_repair[block.index];
	bool dom_needs_repair = state->dom_needs_repair[block.index];
	bool progress = false;

	state->block = &block;
	for (aco_ptr<Instruction>& instr : block.instructions) {
	if (dom_needs_repair) {
	for (Definition def : instr->definitions) {
	if (def.isTemp()) {
	state->def_blocks[def.tempId()] = block.index;
	state->has_def_block[def.tempId()] = true;
	}
	}
	}

	bool phi = is_phi(instr) \|\| instr->opcode == aco_opcode::p_boolean_phi;

	/* Skip the section below if we don't need to repair. If we don't need to update def_blocks
	* either, then we can just break. We always need to process phis because their actual uses
	* are in the predecessors, which might need repair. */
	if (!phi && !needs_repair) {
	if (!dom_needs_repair)
	break;
	continue;
	}

	unsigned start = 0;
	unsigned num_operands = instr->operands.size();
	if (phi && (block.kind & block_kind_loop_header)) {
	if (LoopHeader)
	start++;
	else
	num_operands = 1;
	} else if (LoopHeader) {
	break;
	}

	for (unsigned i = start; i < num_operands; i++) {
	Operand& op = instr->operands[i];
	if (!op.isTemp() \|\| !op.getTemp().is_linear() \|\| !state->has_def_block[op.tempId()])
	continue;

	uint32_t def_block = state->def_blocks[op.tempId()];
	uint32_t use_block = block.index;
	if (instr->opcode == aco_opcode::p_boolean_phi \|\| instr->opcode == aco_opcode::p_phi) {
	use_block = block.logical_preds[i];
	if (!state->block_needs_repair[use_block])
	continue;
	} else if (instr->opcode == aco_opcode::p_linear_phi) {
	use_block = block.linear_preds[i];
	if (!state->block_needs_repair[use_block])
	continue;
	}

	if (!dominates_linear(state->program->blocks[def_block],
	state->program->blocks[use_block])) {
	assert(dominates_logical(state->program->blocks[def_block],
	state->program->blocks[use_block]));
	op.setTemp(create_phis(state, op.getTemp(), use_block, def_block));
	progress = true;
	}
	}
	}

	/* These are inserted later to not invalidate any iterators. */
	block.instructions.insert(block.instructions.begin(),
	std::move_iterator(state->new_phis.begin()),
	std::move_iterator(state->new_phis.end()));
	state->new_phis.clear();

	return progress;
	}

	} /* end namespace */

	bool
	repair_ssa(Program* program)
	{
	repair_state state;
	state.program = program;

	state.block_needs_repair.resize(program->blocks.size());
	state.dom_needs_repair.resize(program->blocks.size());

	state.has_def_block.resize(program->peekAllocationId());
	state.def_blocks.reset(new uint32_t[program->peekAllocationId()]);

	state.visit_block.resize(program->blocks.size());
	state.temps.resize(program->blocks.size());

	for (Block& block : program->blocks) {
	if (block.logical_idom == -1)
	continue;

	if (state.block_needs_repair[block.logical_idom] \|\|
	!dominates_linear(program->blocks[block.logical_idom], block)) {
	state.block_needs_repair[block.index] = true;

	/* Set dom_needs_repair=true for logical dominators. */
	uint32_t parent = block.logical_idom;
	while (!state.dom_needs_repair[parent]) {
	state.dom_needs_repair[parent] = true;
	parent = program->blocks[parent].logical_idom;
	}
	}
	}

	std::vector<unsigned> loop_header_indices;

	bool progress = false;
	for (Block& block : program->blocks) {
	if (block.kind & block_kind_loop_header)
	loop_header_indices.push_back(block.index);

	progress \|= repair_block<false>(&state, block);

	if (block.kind & block_kind_loop_exit) {
	unsigned header = loop_header_indices.back();
	loop_header_indices.pop_back();

	progress \|= repair_block<true>(&state, program->blocks[header]);
	}
	}

	return progress;
	}

	} // namespace aco