X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Famd%2Fcompiler%2Faco_register_allocation.cpp;h=a59a9af7add64501e06bbd023a1c7888f080d674;hb=bf4b377b9b9fa7152431f1efd6bcd15018bbd8f8;hp=965fe15964a8bffd5aea62e540ce964bd3541034;hpb=08d510010b7586387e363460b98e6a45bbe97164;p=mesa.git diff --git a/src/amd/compiler/aco_register_allocation.cpp b/src/amd/compiler/aco_register_allocation.cpp index 965fe15964a..a59a9af7add 100644 --- a/src/amd/compiler/aco_register_allocation.cpp +++ b/src/amd/compiler/aco_register_allocation.cpp @@ -30,7 +30,6 @@ #include #include #include -#include #include "aco_ir.h" #include "sid.h" @@ -39,22 +38,219 @@ namespace aco { namespace { +unsigned get_subdword_operand_stride(chip_class chip, const aco_ptr& instr, unsigned idx, RegClass rc); +void add_subdword_operand(chip_class chip, aco_ptr& instr, unsigned idx, unsigned byte, RegClass rc); +std::pair get_subdword_definition_info(Program *program, const aco_ptr& instr, RegClass rc); +void add_subdword_definition(Program *program, aco_ptr& instr, unsigned idx, PhysReg reg, bool is_partial); + +struct assignment { + PhysReg reg; + RegClass rc; + uint8_t assigned = 0; + assignment() = default; + assignment(PhysReg reg, RegClass rc) : reg(reg), rc(rc), assigned(-1) {} +}; + +struct phi_info { + Instruction* phi; + unsigned block_idx; + std::set uses; +}; + struct ra_ctx { std::bitset<512> war_hint; Program* program; - std::unordered_map> assignments; - std::map orig_names; + std::vector assignments; + std::vector> renames; + std::vector> incomplete_phis; + std::vector filled; + std::vector sealed; + std::unordered_map orig_names; + std::unordered_map phi_map; + std::unordered_map affinities; + std::unordered_map vectors; + std::unordered_map split_vectors; + aco_ptr pseudo_dummy; unsigned max_used_sgpr = 0; unsigned max_used_vgpr = 0; std::bitset<64> defs_done; /* see MAX_ARGS in aco_instruction_selection_setup.cpp */ - ra_ctx(Program* program) : program(program) {} + ra_ctx(Program* program) : program(program), + assignments(program->peekAllocationId()), + renames(program->blocks.size()), + incomplete_phis(program->blocks.size()), + filled(program->blocks.size()), + sealed(program->blocks.size()) + { + pseudo_dummy.reset(create_instruction(aco_opcode::p_parallelcopy, Format::PSEUDO, 0, 0)); + } +}; + +struct DefInfo { + uint16_t lb; + uint16_t ub; + uint8_t size; + uint8_t stride; + RegClass rc; + + DefInfo(ra_ctx& ctx, aco_ptr& instr, RegClass rc_, int operand) : rc(rc_) { + size = rc.size(); + stride = 1; + + if (rc.type() == RegType::vgpr) { + lb = 256; + ub = 256 + ctx.program->max_reg_demand.vgpr; + } else { + lb = 0; + ub = ctx.program->max_reg_demand.sgpr; + if (size == 2) + stride = 2; + else if (size >= 4) + stride = 4; + } + + if (rc.is_subdword() && operand >= 0) { + /* stride in bytes */ + stride = get_subdword_operand_stride(ctx.program->chip_class, instr, operand, rc); + } else if (rc.is_subdword()) { + std::pair info = get_subdword_definition_info(ctx.program, instr, rc); + stride = info.first; + if (info.second > rc.bytes()) { + rc = RegClass::get(rc.type(), info.second); + size = rc.size(); + /* we might still be able to put the definition in the high half, + * but that's only useful for affinities and this information isn't + * used for them */ + stride = align(stride, info.second); + if (!rc.is_subdword()) + stride = DIV_ROUND_UP(stride, 4); + } + assert(stride > 0); + } + } +}; + +class RegisterFile { +public: + RegisterFile() {regs.fill(0);} + + std::array regs; + std::map> subdword_regs; + + const uint32_t& operator [] (unsigned index) const { + return regs[index]; + } + + uint32_t& operator [] (unsigned index) { + return regs[index]; + } + + unsigned count_zero(PhysReg start, unsigned size) { + unsigned res = 0; + for (unsigned i = 0; i < size; i++) + res += !regs[start + i]; + return res; + } + + bool test(PhysReg start, unsigned num_bytes) { + for (PhysReg i = start; i.reg_b < start.reg_b + num_bytes; i = PhysReg(i + 1)) { + if (regs[i] & 0x0FFFFFFF) + return true; + if (regs[i] == 0xF0000000) { + assert(subdword_regs.find(i) != subdword_regs.end()); + for (unsigned j = i.byte(); i * 4 + j < start.reg_b + num_bytes && j < 4; j++) { + if (subdword_regs[i][j]) + return true; + } + } + } + return false; + } + + void block(PhysReg start, RegClass rc) { + if (rc.is_subdword()) + fill_subdword(start, rc.bytes(), 0xFFFFFFFF); + else + fill(start, rc.size(), 0xFFFFFFFF); + } + + bool is_blocked(PhysReg start) { + if (regs[start] == 0xFFFFFFFF) + return true; + if (regs[start] == 0xF0000000) { + for (unsigned i = start.byte(); i < 4; i++) + if (subdword_regs[start][i] == 0xFFFFFFFF) + return true; + } + return false; + } + + bool is_empty_or_blocked(PhysReg start) { + if (regs[start] == 0xF0000000) { + return subdword_regs[start][start.byte()] + 1 <= 1; + } + return regs[start] + 1 <= 1; + } + + void clear(PhysReg start, RegClass rc) { + if (rc.is_subdword()) + fill_subdword(start, rc.bytes(), 0); + else + fill(start, rc.size(), 0); + } + + void fill(Operand op) { + if (op.regClass().is_subdword()) + fill_subdword(op.physReg(), op.bytes(), op.tempId()); + else + fill(op.physReg(), op.size(), op.tempId()); + } + + void clear(Operand op) { + clear(op.physReg(), op.regClass()); + } + + void fill(Definition def) { + if (def.regClass().is_subdword()) + fill_subdword(def.physReg(), def.bytes(), def.tempId()); + else + fill(def.physReg(), def.size(), def.tempId()); + } + + void clear(Definition def) { + clear(def.physReg(), def.regClass()); + } + + unsigned get_id(PhysReg reg) { + return regs[reg] == 0xF0000000 ? subdword_regs[reg][reg.byte()] : regs[reg]; + } + +private: + void fill(PhysReg start, unsigned size, uint32_t val) { + for (unsigned i = 0; i < size; i++) + regs[start + i] = val; + } + + void fill_subdword(PhysReg start, unsigned num_bytes, uint32_t val) { + fill(start, DIV_ROUND_UP(num_bytes, 4), 0xF0000000); + for (PhysReg i = start; i.reg_b < start.reg_b + num_bytes; i = PhysReg(i + 1)) { + /* emplace or get */ + std::array& sub = subdword_regs.emplace(i, std::array{0, 0, 0, 0}).first->second; + for (unsigned j = i.byte(); i * 4 + j < start.reg_b + num_bytes && j < 4; j++) + sub[j] = val; + + if (sub == std::array{0, 0, 0, 0}) { + subdword_regs.erase(i); + regs[i] = 0; + } + } + } }; /* helper function for debugging */ #if 0 -void print_regs(ra_ctx& ctx, bool vgprs, std::array& reg_file) +void print_regs(ra_ctx& ctx, bool vgprs, RegisterFile& reg_file) { unsigned max = vgprs ? ctx.program->max_reg_demand.vgpr : ctx.program->max_reg_demand.sgpr; unsigned lb = vgprs ? 256 : 0; @@ -120,6 +316,201 @@ void print_regs(ra_ctx& ctx, bool vgprs, std::array& reg_file) #endif +unsigned get_subdword_operand_stride(chip_class chip, const aco_ptr& instr, unsigned idx, RegClass rc) +{ + if (instr->format == Format::PSEUDO && chip >= GFX8) + return rc.bytes() % 2 == 0 ? 2 : 1; + + if (instr->opcode == aco_opcode::v_cvt_f32_ubyte0) { + return 1; + } else if (can_use_SDWA(chip, instr)) { + return rc.bytes() % 2 == 0 ? 2 : 1; + } else if (rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, idx, 1)) { + return 2; + } + + switch (instr->opcode) { + case aco_opcode::ds_write_b8: + case aco_opcode::ds_write_b16: + return chip >= GFX8 ? 2 : 4; + case aco_opcode::buffer_store_byte: + case aco_opcode::buffer_store_short: + case aco_opcode::flat_store_byte: + case aco_opcode::flat_store_short: + case aco_opcode::scratch_store_byte: + case aco_opcode::scratch_store_short: + case aco_opcode::global_store_byte: + case aco_opcode::global_store_short: + return chip >= GFX9 ? 2 : 4; + default: + break; + } + + return 4; +} + +void add_subdword_operand(chip_class chip, aco_ptr& instr, unsigned idx, unsigned byte, RegClass rc) +{ + if (instr->format == Format::PSEUDO || byte == 0) + return; + + assert(rc.bytes() <= 2); + + if (!instr->usesModifiers() && instr->opcode == aco_opcode::v_cvt_f32_ubyte0) { + switch (byte) { + case 0: + instr->opcode = aco_opcode::v_cvt_f32_ubyte0; + break; + case 1: + instr->opcode = aco_opcode::v_cvt_f32_ubyte1; + break; + case 2: + instr->opcode = aco_opcode::v_cvt_f32_ubyte2; + break; + case 3: + instr->opcode = aco_opcode::v_cvt_f32_ubyte3; + break; + } + return; + } else if (can_use_SDWA(chip, instr)) { + convert_to_SDWA(chip, instr); + return; + } else if (rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, idx, byte / 2)) { + VOP3A_instruction *vop3 = static_cast(instr.get()); + vop3->opsel |= (byte / 2) << idx; + return; + } + + if (chip >= GFX8 && instr->opcode == aco_opcode::ds_write_b8 && byte == 2) { + instr->opcode = aco_opcode::ds_write_b8_d16_hi; + return; + } + if (chip >= GFX8 && instr->opcode == aco_opcode::ds_write_b16 && byte == 2) { + instr->opcode = aco_opcode::ds_write_b16_d16_hi; + return; + } + + if (chip >= GFX9 && byte == 2) { + if (instr->opcode == aco_opcode::buffer_store_byte) + instr->opcode = aco_opcode::buffer_store_byte_d16_hi; + else if (instr->opcode == aco_opcode::buffer_store_short) + instr->opcode = aco_opcode::buffer_store_short_d16_hi; + else if (instr->opcode == aco_opcode::flat_store_byte) + instr->opcode = aco_opcode::flat_store_byte_d16_hi; + else if (instr->opcode == aco_opcode::flat_store_short) + instr->opcode = aco_opcode::flat_store_short_d16_hi; + else if (instr->opcode == aco_opcode::scratch_store_byte) + instr->opcode = aco_opcode::scratch_store_byte_d16_hi; + else if (instr->opcode == aco_opcode::scratch_store_short) + instr->opcode = aco_opcode::scratch_store_short_d16_hi; + else if (instr->opcode == aco_opcode::global_store_byte) + instr->opcode = aco_opcode::global_store_byte_d16_hi; + else if (instr->opcode == aco_opcode::global_store_short) + instr->opcode = aco_opcode::global_store_short_d16_hi; + else + unreachable("Something went wrong: Impossible register assignment."); + } +} + +/* minimum_stride, bytes_written */ +std::pair get_subdword_definition_info(Program *program, const aco_ptr& instr, RegClass rc) +{ + chip_class chip = program->chip_class; + + if (instr->format == Format::PSEUDO && chip >= GFX8) + return std::make_pair(rc.bytes() % 2 == 0 ? 2 : 1, rc.bytes()); + else if (instr->format == Format::PSEUDO) + return std::make_pair(4, rc.size() * 4u); + + unsigned bytes_written = chip >= GFX10 ? rc.bytes() : 4u; + switch (instr->opcode) { + case aco_opcode::v_mad_f16: + case aco_opcode::v_mad_u16: + case aco_opcode::v_mad_i16: + case aco_opcode::v_fma_f16: + case aco_opcode::v_div_fixup_f16: + case aco_opcode::v_interp_p2_f16: + bytes_written = chip >= GFX9 ? rc.bytes() : 4u; + break; + default: + break; + } + bytes_written = MAX2(bytes_written, instr_info.definition_size[(int)instr->opcode] / 8u); + + if (can_use_SDWA(chip, instr)) { + return std::make_pair(rc.bytes(), rc.bytes()); + } else if (rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, -1, 1)) { + return std::make_pair(2u, bytes_written); + } + + switch (instr->opcode) { + case aco_opcode::buffer_load_ubyte_d16: + case aco_opcode::buffer_load_short_d16: + case aco_opcode::flat_load_ubyte_d16: + case aco_opcode::flat_load_short_d16: + case aco_opcode::scratch_load_ubyte_d16: + case aco_opcode::scratch_load_short_d16: + case aco_opcode::global_load_ubyte_d16: + case aco_opcode::global_load_short_d16: + case aco_opcode::ds_read_u8_d16: + case aco_opcode::ds_read_u16_d16: + if (chip >= GFX9 && !program->sram_ecc_enabled) + return std::make_pair(2u, 2u); + else + return std::make_pair(2u, 4u); + default: + break; + } + + return std::make_pair(4u, bytes_written); +} + +void add_subdword_definition(Program *program, aco_ptr& instr, unsigned idx, PhysReg reg, bool is_partial) +{ + RegClass rc = instr->definitions[idx].regClass(); + chip_class chip = program->chip_class; + + instr->definitions[idx].setFixed(reg); + + if (instr->format == Format::PSEUDO) { + return; + } else if (can_use_SDWA(chip, instr)) { + if (reg.byte() || (is_partial && chip < GFX10)) + convert_to_SDWA(chip, instr); + return; + } else if (reg.byte() && rc.bytes() == 2 && can_use_opsel(chip, instr->opcode, -1, reg.byte() / 2)) { + VOP3A_instruction *vop3 = static_cast(instr.get()); + if (reg.byte() == 2) + vop3->opsel |= (1 << 3); /* dst in high half */ + return; + } + + if (reg.byte() == 2) { + if (instr->opcode == aco_opcode::buffer_load_ubyte_d16) + instr->opcode = aco_opcode::buffer_load_ubyte_d16_hi; + else if (instr->opcode == aco_opcode::buffer_load_short_d16) + instr->opcode = aco_opcode::buffer_load_short_d16_hi; + else if (instr->opcode == aco_opcode::flat_load_ubyte_d16) + instr->opcode = aco_opcode::flat_load_ubyte_d16_hi; + else if (instr->opcode == aco_opcode::flat_load_short_d16) + instr->opcode = aco_opcode::flat_load_short_d16_hi; + else if (instr->opcode == aco_opcode::scratch_load_ubyte_d16) + instr->opcode = aco_opcode::scratch_load_ubyte_d16_hi; + else if (instr->opcode == aco_opcode::scratch_load_short_d16) + instr->opcode = aco_opcode::scratch_load_short_d16_hi; + else if (instr->opcode == aco_opcode::global_load_ubyte_d16) + instr->opcode = aco_opcode::global_load_ubyte_d16_hi; + else if (instr->opcode == aco_opcode::global_load_short_d16) + instr->opcode = aco_opcode::global_load_short_d16_hi; + else if (instr->opcode == aco_opcode::ds_read_u8_d16) + instr->opcode = aco_opcode::ds_read_u8_d16_hi; + else if (instr->opcode == aco_opcode::ds_read_u16_d16) + instr->opcode = aco_opcode::ds_read_u16_d16_hi; + else + unreachable("Something went wrong: Impossible register assignment."); + } +} + void adjust_max_used_regs(ra_ctx& ctx, RegClass rc, unsigned reg) { unsigned max_addressible_sgpr = ctx.program->sgpr_limit; @@ -135,9 +526,9 @@ void adjust_max_used_regs(ra_ctx& ctx, RegClass rc, unsigned reg) } -void update_renames(ra_ctx& ctx, std::array& reg_file, +void update_renames(ra_ctx& ctx, RegisterFile& reg_file, std::vector>& parallelcopies, - aco_ptr& instr) + aco_ptr& instr, bool rename_not_killed_ops) { /* allocate id's and rename operands: this is done transparently here */ for (std::pair& copy : parallelcopies) { @@ -145,25 +536,43 @@ void update_renames(ra_ctx& ctx, std::array& reg_file, if (copy.second.isTemp()) continue; + /* check if we we moved another parallelcopy definition */ + for (std::pair& other : parallelcopies) { + if (!other.second.isTemp()) + continue; + if (copy.first.getTemp() == other.second.getTemp()) { + copy.first.setTemp(other.first.getTemp()); + copy.first.setFixed(other.first.physReg()); + } + } // FIXME: if a definition got moved, change the target location and remove the parallelcopy copy.second.setTemp(Temp(ctx.program->allocateId(), copy.second.regClass())); - ctx.assignments[copy.second.tempId()] = {copy.second.physReg(), copy.second.regClass()}; - for (unsigned i = copy.second.physReg().reg; i < copy.second.physReg() + copy.second.size(); i++) - reg_file[i] = copy.second.tempId(); + ctx.assignments.emplace_back(copy.second.physReg(), copy.second.regClass()); + assert(ctx.assignments.size() == ctx.program->peekAllocationId()); + reg_file.fill(copy.second); + /* check if we moved an operand */ - for (Operand& op : instr->operands) { + bool first = true; + for (unsigned i = 0; i < instr->operands.size(); i++) { + Operand& op = instr->operands[i]; if (!op.isTemp()) continue; if (op.tempId() == copy.first.tempId()) { - bool omit_renaming = instr->opcode == aco_opcode::p_create_vector && !op.isKill(); + bool omit_renaming = !rename_not_killed_ops && !op.isKillBeforeDef(); for (std::pair& pc : parallelcopies) { PhysReg def_reg = pc.second.physReg(); omit_renaming &= def_reg > copy.first.physReg() ? - (copy.first.physReg() + copy.first.size() <= def_reg.reg) : - (def_reg + pc.second.size() <= copy.first.physReg().reg); + (copy.first.physReg() + copy.first.size() <= def_reg.reg()) : + (def_reg + pc.second.size() <= copy.first.physReg().reg()); } - if (omit_renaming) + if (omit_renaming) { + if (first) + op.setFirstKill(true); + else + op.setKill(true); + first = false; continue; + } op.setTemp(copy.second.getTemp()); op.setFixed(copy.second.physReg()); } @@ -172,53 +581,81 @@ void update_renames(ra_ctx& ctx, std::array& reg_file, } std::pair get_reg_simple(ra_ctx& ctx, - std::array& reg_file, - uint32_t lb, uint32_t ub, - uint32_t size, uint32_t stride, - RegClass rc) + RegisterFile& reg_file, + DefInfo info) { - /* best fit algorithm: find the smallest gap to fit in the variable */ + uint32_t lb = info.lb; + uint32_t ub = info.ub; + uint32_t size = info.size; + uint32_t stride = info.rc.is_subdword() ? DIV_ROUND_UP(info.stride, 4) : info.stride; + RegClass rc = info.rc; + if (stride == 1) { + + for (unsigned stride = 8; stride > 1; stride /= 2) { + if (size % stride) + continue; + info.stride = stride; + std::pair res = get_reg_simple(ctx, reg_file, info); + if (res.second) + return res; + } + + /* best fit algorithm: find the smallest gap to fit in the variable */ unsigned best_pos = 0xFFFF; unsigned gap_size = 0xFFFF; - unsigned next_pos = 0xFFFF; + unsigned last_pos = 0xFFFF; for (unsigned current_reg = lb; current_reg < ub; current_reg++) { - if (reg_file[current_reg] != 0 || ctx.war_hint[current_reg]) { - if (next_pos == 0xFFFF) - continue; - /* check if the variable fits */ - if (next_pos + size > current_reg) { - next_pos = 0xFFFF; + if (reg_file[current_reg] == 0 && !ctx.war_hint[current_reg]) { + if (last_pos == 0xFFFF) + last_pos = current_reg; + + /* stop searching after max_used_gpr */ + if (current_reg == ctx.max_used_sgpr + 1 || current_reg == 256 + ctx.max_used_vgpr + 1) + break; + else continue; - } + } - /* check if the tested gap is smaller */ - if (current_reg - next_pos < gap_size) { - best_pos = next_pos; - gap_size = current_reg - next_pos; - } - next_pos = 0xFFFF; + if (last_pos == 0xFFFF) continue; + + /* early return on exact matches */ + if (last_pos + size == current_reg) { + adjust_max_used_regs(ctx, rc, last_pos); + return {PhysReg{last_pos}, true}; } - if (next_pos == 0xFFFF) - next_pos = current_reg; + /* check if it fits and the gap size is smaller */ + if (last_pos + size < current_reg && current_reg - last_pos < gap_size) { + best_pos = last_pos; + gap_size = current_reg - last_pos; + } + last_pos = 0xFFFF; } /* final check */ - if (next_pos != 0xFFFF && - next_pos + size <= ub && - ub - next_pos < gap_size) { - best_pos = next_pos; - gap_size = ub - next_pos; + if (last_pos + size <= ub && ub - last_pos < gap_size) { + best_pos = last_pos; + gap_size = ub - last_pos; } - if (best_pos != 0xFFFF) { - adjust_max_used_regs(ctx, rc, best_pos); - return {PhysReg{best_pos}, true}; + + if (best_pos == 0xFFFF) + return {{}, false}; + + /* find best position within gap by leaving a good stride for other variables*/ + unsigned buffer = gap_size - size; + if (buffer > 1) { + if (((best_pos + size) % 8 != 0 && (best_pos + buffer) % 8 == 0) || + ((best_pos + size) % 4 != 0 && (best_pos + buffer) % 4 == 0) || + ((best_pos + size) % 2 != 0 && (best_pos + buffer) % 2 == 0)) + best_pos = best_pos + buffer; } - return {{}, false}; + + adjust_max_used_regs(ctx, rc, best_pos); + return {PhysReg{best_pos}, true}; } bool found = false; @@ -243,13 +680,71 @@ std::pair get_reg_simple(ra_ctx& ctx, reg_lo += stride; } + /* do this late because using the upper bytes of a register can require + * larger instruction encodings or copies + * TODO: don't do this in situations where it doesn't benefit */ + if (rc.is_subdword()) { + for (std::pair> entry : reg_file.subdword_regs) { + assert(reg_file[entry.first] == 0xF0000000); + if (lb > entry.first || entry.first >= ub) + continue; + + for (unsigned i = 0; i < 4; i+= info.stride) { + if (entry.second[i] != 0) + continue; + + bool reg_found = true; + for (unsigned j = 1; reg_found && i + j < 4 && j < rc.bytes(); j++) + reg_found &= entry.second[i + j] == 0; + + /* check neighboring reg if needed */ + reg_found &= ((int)i <= 4 - (int)rc.bytes() || reg_file[entry.first + 1] == 0); + if (reg_found) { + PhysReg res{entry.first}; + res.reg_b += i; + adjust_max_used_regs(ctx, rc, entry.first); + return {res, true}; + } + } + } + } + return {{}, false}; } +/* collect variables from a register area and clear reg_file */ +std::set> collect_vars(ra_ctx& ctx, RegisterFile& reg_file, + PhysReg reg, unsigned size) +{ + std::set> vars; + for (unsigned j = reg; j < reg + size; j++) { + if (reg_file.is_blocked(PhysReg{j})) + continue; + if (reg_file[j] == 0xF0000000) { + for (unsigned k = 0; k < 4; k++) { + unsigned id = reg_file.subdword_regs[j][k]; + if (id) { + assignment& var = ctx.assignments[id]; + vars.emplace(var.rc.bytes(), id); + reg_file.clear(var.reg, var.rc); + if (!reg_file[j]) + break; + } + } + } else if (reg_file[j] != 0) { + unsigned id = reg_file[j]; + assignment& var = ctx.assignments[id]; + vars.emplace(var.rc.bytes(), id); + reg_file.clear(var.reg, var.rc); + } + } + return vars; +} + bool get_regs_for_copies(ra_ctx& ctx, - std::array& reg_file, + RegisterFile& reg_file, std::vector>& parallelcopies, - std::set> vars, + const std::set> &vars, uint32_t lb, uint32_t ub, aco_ptr& instr, uint32_t def_reg_lo, @@ -258,55 +753,61 @@ bool get_regs_for_copies(ra_ctx& ctx, /* variables are sorted from small sized to large */ /* NOTE: variables are also sorted by ID. this only affects a very small number of shaders slightly though. */ - for (std::set>::reverse_iterator it = vars.rbegin(); it != vars.rend(); ++it) { + for (std::set>::const_reverse_iterator it = vars.rbegin(); it != vars.rend(); ++it) { unsigned id = it->second; - std::pair var = ctx.assignments[id]; - uint32_t size = it->first; - uint32_t stride = 1; - if (var.second.type() == RegType::sgpr) { - if (size == 2) - stride = 2; - if (size > 3) - stride = 4; - } + assignment& var = ctx.assignments[id]; + DefInfo info = DefInfo(ctx, ctx.pseudo_dummy, var.rc, -1); + uint32_t size = info.size; - /* check if this is a dead operand, then we can re-use the space from the definition */ + /* check if this is a dead operand, then we can re-use the space from the definition + * also use the correct stride for sub-dword operands */ bool is_dead_operand = false; - for (unsigned i = 0; !is_phi(instr) && !is_dead_operand && i < instr->operands.size(); i++) { - if (instr->operands[i].isTemp() && instr->operands[i].isKill() && instr->operands[i].tempId() == id) - is_dead_operand = true; + for (unsigned i = 0; !is_phi(instr) && i < instr->operands.size(); i++) { + if (instr->operands[i].isTemp() && instr->operands[i].tempId() == id) { + if (instr->operands[i].isKillBeforeDef()) + is_dead_operand = true; + info = DefInfo(ctx, instr, var.rc, i); + break; + } } std::pair res; if (is_dead_operand) { if (instr->opcode == aco_opcode::p_create_vector) { - for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].size(), i++) { + PhysReg reg(def_reg_lo); + for (unsigned i = 0; i < instr->operands.size(); i++) { if (instr->operands[i].isTemp() && instr->operands[i].tempId() == id) { - for (unsigned j = 0; j < size; j++) - assert(reg_file[def_reg_lo + offset + j] == 0); - res = {PhysReg{def_reg_lo + offset}, true}; + res = {reg, (!var.rc.is_subdword() || (reg.byte() % info.stride == 0)) && !reg_file.test(reg, var.rc.bytes())}; break; } + reg.reg_b += instr->operands[i].bytes(); } + if (!res.second) + res = {var.reg, !reg_file.test(var.reg, var.rc.bytes())}; } else { - res = get_reg_simple(ctx, reg_file, def_reg_lo, def_reg_hi + 1, size, stride, var.second); + info.lb = def_reg_lo; + info.ub = def_reg_hi + 1; + res = get_reg_simple(ctx, reg_file, info); } } else { - res = get_reg_simple(ctx, reg_file, lb, def_reg_lo, size, stride, var.second); - if (!res.second) { - unsigned lb = (def_reg_hi + stride) & ~(stride - 1); - res = get_reg_simple(ctx, reg_file, lb, ub, size, stride, var.second); + info.lb = lb; + info.ub = MIN2(def_reg_lo, ub); + res = get_reg_simple(ctx, reg_file, info); + if (!res.second && def_reg_hi < ub) { + info.lb = (def_reg_hi + info.stride) & ~(info.stride - 1); + info.ub = ub; + res = get_reg_simple(ctx, reg_file, info); } } if (res.second) { /* mark the area as blocked */ - for (unsigned i = res.first.reg; i < res.first + size; i++) - reg_file[i] = 0xFFFFFFFF; + reg_file.block(res.first, var.rc); + /* create parallelcopy pair (without definition id) */ - Temp tmp = Temp(id, var.second); + Temp tmp = Temp(id, var.rc); Operand pc_op = Operand(tmp); - pc_op.setFixed(var.first); + pc_op.setFixed(var.reg); Definition pc_def = Definition(res.first, pc_op.regClass()); parallelcopies.emplace_back(pc_op, pc_def); continue; @@ -319,6 +820,7 @@ bool get_regs_for_copies(ra_ctx& ctx, /* we use a sliding window to find potential positions */ unsigned reg_lo = lb; unsigned reg_hi = lb + size - 1; + unsigned stride = var.rc.is_subdword() ? 1 : info.stride; for (reg_lo = lb, reg_hi = lb + size - 1; reg_hi < ub; reg_lo += stride, reg_hi += stride) { if (!is_dead_operand && ((reg_lo >= def_reg_lo && reg_lo <= def_reg_hi) || (reg_hi >= def_reg_lo && reg_hi <= def_reg_hi))) @@ -334,29 +836,33 @@ bool get_regs_for_copies(ra_ctx& ctx, if (reg_file[j] == 0 || reg_file[j] == last_var) continue; - /* 0xFFFF signals that this area is already blocked! */ - if (reg_file[j] == 0xFFFFFFFF || k > num_moves) { + if (reg_file.is_blocked(PhysReg{j}) || k > num_moves) { found = false; break; } + if (reg_file[j] == 0xF0000000) { + k += 1; + n++; + continue; + } /* we cannot split live ranges of linear vgprs */ - if (ctx.assignments[reg_file[j]].second & (1 << 6)) { + if (ctx.assignments[reg_file[j]].rc & (1 << 6)) { found = false; break; } bool is_kill = false; for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isKill() && op.tempId() == reg_file[j]) { + if (op.isTemp() && op.isKillBeforeDef() && op.tempId() == reg_file[j]) { is_kill = true; break; } } - if (!is_kill && ctx.assignments[reg_file[j]].second.size() >= size) { + if (!is_kill && ctx.assignments[reg_file[j]].rc.size() >= size) { found = false; break; } - k += ctx.assignments[reg_file[j]].second.size(); + k += ctx.assignments[reg_file[j]].rc.size(); last_var = reg_file[j]; n++; if (k > num_moves || (k == num_moves && n <= num_vars)) { @@ -380,30 +886,20 @@ bool get_regs_for_copies(ra_ctx& ctx, reg_hi = best_pos + size - 1; /* collect variables and block reg file */ - std::set> new_vars; - for (unsigned j = reg_lo; j <= reg_hi; j++) { - if (reg_file[j] != 0) { - unsigned size = ctx.assignments[reg_file[j]].second.size(); - unsigned id = reg_file[j]; - new_vars.emplace(size, id); - for (unsigned k = 0; k < size; k++) - reg_file[ctx.assignments[id].first + k] = 0; - } - } + std::set> new_vars = collect_vars(ctx, reg_file, PhysReg{reg_lo}, size); /* mark the area as blocked */ - for (unsigned i = reg_lo; i <= reg_hi; i++) - reg_file[i] = 0xFFFFFFFF; + reg_file.block(PhysReg{reg_lo}, var.rc); if (!get_regs_for_copies(ctx, reg_file, parallelcopies, new_vars, lb, ub, instr, def_reg_lo, def_reg_hi)) return false; - adjust_max_used_regs(ctx, var.second, reg_lo); + adjust_max_used_regs(ctx, var.rc, reg_lo); /* create parallelcopy pair (without definition id) */ - Temp tmp = Temp(id, var.second); + Temp tmp = Temp(id, var.rc); Operand pc_op = Operand(tmp); - pc_op.setFixed(var.first); + pc_op.setFixed(var.reg); Definition pc_def = Definition(PhysReg{reg_lo}, pc_op.regClass()); parallelcopies.emplace_back(pc_op, pc_def); } @@ -413,31 +909,30 @@ bool get_regs_for_copies(ra_ctx& ctx, std::pair get_reg_impl(ra_ctx& ctx, - std::array& reg_file, + RegisterFile& reg_file, std::vector>& parallelcopies, - uint32_t lb, uint32_t ub, - uint32_t size, uint32_t stride, - RegClass rc, + DefInfo info, aco_ptr& instr) { - unsigned regs_free = 0; + uint32_t lb = info.lb; + uint32_t ub = info.ub; + uint32_t size = info.size; + uint32_t stride = info.stride; + RegClass rc = info.rc; + /* check how many free regs we have */ - for (unsigned j = lb; j < ub; j++) { - if (reg_file[j] == 0) - regs_free++; - } + unsigned regs_free = reg_file.count_zero(PhysReg{lb}, ub-lb); /* mark and count killed operands */ unsigned killed_ops = 0; for (unsigned j = 0; !is_phi(instr) && j < instr->operands.size(); j++) { if (instr->operands[j].isTemp() && - instr->operands[j].isFirstKill() && + instr->operands[j].isFirstKillBeforeDef() && instr->operands[j].physReg() >= lb && - instr->operands[j].physReg() < ub) { + instr->operands[j].physReg() < ub && + !reg_file.test(instr->operands[j].physReg(), instr->operands[j].bytes())) { assert(instr->operands[j].isFixed()); - assert(reg_file[instr->operands[j].physReg().reg] == 0); - for (unsigned k = 0; k < instr->operands[j].size(); k++) - reg_file[instr->operands[j].physReg() + k] = 0xFFFFFFFF; + reg_file.block(instr->operands[j].physReg(), instr->operands[j].regClass()); killed_ops += instr->operands[j].getTemp().size(); } } @@ -459,9 +954,11 @@ std::pair get_reg_impl(ra_ctx& ctx, unsigned reg_hi = lb + size - 1; for (reg_lo = lb, reg_hi = lb + size - 1; reg_hi < ub; reg_lo += stride, reg_hi += stride) { /* first check the edges: this is what we have to fix to allow for num_moves > size */ - if (reg_lo > lb && reg_file[reg_lo] != 0 && reg_file[reg_lo] == reg_file[reg_lo - 1]) + if (reg_lo > lb && !reg_file.is_empty_or_blocked(PhysReg(reg_lo)) && + reg_file.get_id(PhysReg(reg_lo)) == reg_file.get_id(PhysReg(reg_lo).advance(-1))) continue; - if (reg_hi < ub - 1 && reg_file[reg_hi] != 0 && reg_file[reg_hi] == reg_file[reg_hi + 1]) + if (reg_hi < ub - 1 && !reg_file.is_empty_or_blocked(PhysReg(reg_hi).advance(3)) && + reg_file.get_id(PhysReg(reg_hi).advance(3)) == reg_file.get_id(PhysReg(reg_hi).advance(4))) continue; /* second, check that we have at most k=num_moves elements in the window @@ -477,25 +974,32 @@ std::pair get_reg_impl(ra_ctx& ctx, continue; /* dead operands effectively reduce the number of estimated moves */ - if (remaining_op_moves && reg_file[j] == 0xFFFFFFFF) { - k--; - remaining_op_moves--; + if (reg_file.is_blocked(PhysReg{j})) { + if (remaining_op_moves) { + k--; + remaining_op_moves--; + } + continue; + } + + if (reg_file[j] == 0xF0000000) { + k += 1; + n++; continue; } - if (ctx.assignments[reg_file[j]].second.size() >= size) { + if (ctx.assignments[reg_file[j]].rc.size() >= size) { found = false; break; } - /* we cannot split live ranges of linear vgprs */ - if (ctx.assignments[reg_file[j]].second & (1 << 6)) { + if (ctx.assignments[reg_file[j]].rc & (1 << 6)) { found = false; break; } - k += ctx.assignments[reg_file[j]].second.size(); + k += ctx.assignments[reg_file[j]].rc.size(); n++; last_var = reg_file[j]; } @@ -517,54 +1021,46 @@ std::pair get_reg_impl(ra_ctx& ctx, if (num_moves == 0xFF) { /* remove killed operands from reg_file once again */ for (unsigned i = 0; !is_phi(instr) && i < instr->operands.size(); i++) { - if (instr->operands[i].isTemp() && instr->operands[i].isFirstKill()) { - for (unsigned k = 0; k < instr->operands[i].getTemp().size(); k++) - reg_file[instr->operands[i].physReg() + k] = 0; - } + if (instr->operands[i].isTemp() && instr->operands[i].isFirstKillBeforeDef()) + reg_file.clear(instr->operands[i]); } for (unsigned i = 0; i < instr->definitions.size(); i++) { Definition def = instr->definitions[i]; - if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i)) { - for (unsigned k = 0; k < def.getTemp().size(); k++) - reg_file[def.physReg() + k] = def.tempId(); - } + if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i)) + reg_file.fill(def); } return {{}, false}; } - std::array register_file = reg_file; + RegisterFile register_file = reg_file; /* now, we figured the placement for our definition */ - std::set> vars; - for (unsigned j = best_pos; j < best_pos + size; j++) { - if (reg_file[j] != 0xFFFFFFFF && reg_file[j] != 0) - vars.emplace(ctx.assignments[reg_file[j]].second.size(), reg_file[j]); - reg_file[j] = 0; - } + std::set> vars = collect_vars(ctx, reg_file, PhysReg{best_pos}, size); if (instr->opcode == aco_opcode::p_create_vector) { - /* move killed operands which aren't yet at the correct position */ - for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].size(), i++) { - if (instr->operands[i].isTemp() && instr->operands[i].isFirstKill() && - instr->operands[i].getTemp().type() == rc.type()) { - - if (instr->operands[i].physReg() != best_pos + offset) { - vars.emplace(instr->operands[i].size(), instr->operands[i].tempId()); - for (unsigned j = 0; j < instr->operands[i].size(); j++) - reg_file[instr->operands[i].physReg() + j] = 0; + /* move killed operands which aren't yet at the correct position (GFX9+) + * or which are in the definition space */ + PhysReg reg = PhysReg{best_pos}; + for (Operand& op : instr->operands) { + if (op.isTemp() && op.isFirstKillBeforeDef() && + op.getTemp().type() == rc.type()) { + if (op.physReg() != reg && + (ctx.program->chip_class >= GFX9 || + (op.physReg().advance(op.bytes()) > PhysReg{best_pos} && + op.physReg() < PhysReg{best_pos + size}))) { + vars.emplace(op.bytes(), op.tempId()); + reg_file.clear(op); } else { - for (unsigned j = 0; j < instr->operands[i].size(); j++) - reg_file[instr->operands[i].physReg() + j] = instr->operands[i].tempId(); + reg_file.fill(op); } } + reg.reg_b += op.bytes(); } - } else { - /* re-enable the killed operands */ - for (unsigned j = 0; !is_phi(instr) && j < instr->operands.size(); j++) { - if (instr->operands[j].isTemp() && instr->operands[j].isFirstKill()) { - for (unsigned k = 0; k < instr->operands[j].getTemp().size(); k++) - reg_file[instr->operands[j].physReg() + k] = instr->operands[j].tempId(); - } + } else if (!is_phi(instr)) { + /* re-enable killed operands */ + for (Operand& op : instr->operands) { + if (op.isTemp() && op.isFirstKillBeforeDef()) + reg_file.fill(op); } } @@ -574,18 +1070,14 @@ std::pair get_reg_impl(ra_ctx& ctx, /* remove killed operands from reg_file once again */ if (!is_phi(instr)) { for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isFirstKill()) { - for (unsigned k = 0; k < op.getTemp().size(); k++) - reg_file[op.physReg() + k] = 0; - } + if (op.isTemp() && op.isFirstKillBeforeDef()) + reg_file.clear(op); } } for (unsigned i = 0; i < instr->definitions.size(); i++) { Definition& def = instr->definitions[i]; - if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i)) { - for (unsigned k = 0; k < def.getTemp().size(); k++) - reg_file[def.physReg() + k] = def.tempId(); - } + if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i)) + reg_file.fill(def); } return {{}, false}; } @@ -593,125 +1085,191 @@ std::pair get_reg_impl(ra_ctx& ctx, parallelcopies.insert(parallelcopies.end(), pc.begin(), pc.end()); /* we set the definition regs == 0. the actual caller is responsible for correct setting */ - for (unsigned i = 0; i < size; i++) - reg_file[best_pos + i] = 0; + reg_file.clear(PhysReg{best_pos}, rc); - update_renames(ctx, reg_file, parallelcopies, instr); + update_renames(ctx, reg_file, parallelcopies, instr, instr->opcode != aco_opcode::p_create_vector); /* remove killed operands from reg_file once again */ for (unsigned i = 0; !is_phi(instr) && i < instr->operands.size(); i++) { if (!instr->operands[i].isTemp() || !instr->operands[i].isFixed()) continue; assert(!instr->operands[i].isUndefined()); - if (instr->operands[i].isFirstKill()) { - for (unsigned j = 0; j < instr->operands[i].getTemp().size(); j++) - reg_file[instr->operands[i].physReg() + j] = 0; - } + if (instr->operands[i].isFirstKillBeforeDef()) + reg_file.clear(instr->operands[i]); } for (unsigned i = 0; i < instr->definitions.size(); i++) { Definition def = instr->definitions[i]; - if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i)) { - for (unsigned k = 0; k < def.getTemp().size(); k++) - reg_file[def.physReg() + k] = def.tempId(); - } + if (def.isTemp() && def.isFixed() && ctx.defs_done.test(i)) + reg_file.fill(def); } adjust_max_used_regs(ctx, rc, best_pos); return {PhysReg{best_pos}, true}; } -PhysReg get_reg(ra_ctx& ctx, - std::array& reg_file, - RegClass rc, - std::vector>& parallelcopies, - aco_ptr& instr) +bool get_reg_specified(ra_ctx& ctx, + RegisterFile& reg_file, + RegClass rc, + std::vector>& parallelcopies, + aco_ptr& instr, + PhysReg reg) { + std::pair sdw_def_info; + if (rc.is_subdword()) + sdw_def_info = get_subdword_definition_info(ctx.program, instr, rc); + + if (rc.is_subdword() && reg.byte() % sdw_def_info.first) + return false; + if (!rc.is_subdword() && reg.byte()) + return false; + uint32_t size = rc.size(); uint32_t stride = 1; uint32_t lb, ub; + if (rc.type() == RegType::vgpr) { lb = 256; ub = 256 + ctx.program->max_reg_demand.vgpr; } else { - lb = 0; - ub = ctx.program->max_reg_demand.sgpr; if (size == 2) stride = 2; else if (size >= 4) stride = 4; + if (reg % stride != 0) + return false; + lb = 0; + ub = ctx.program->max_reg_demand.sgpr; } - std::pair res = {{}, false}; + uint32_t reg_lo = reg.reg(); + uint32_t reg_hi = reg + (size - 1); + + if (reg_lo < lb || reg_hi >= ub || reg_lo > reg_hi) + return false; + + if (rc.is_subdword()) { + PhysReg test_reg; + test_reg.reg_b = reg.reg_b & ~(sdw_def_info.second - 1); + if (reg_file.test(test_reg, sdw_def_info.second)) + return false; + } else { + if (reg_file.test(reg, rc.bytes())) + return false; + } + + adjust_max_used_regs(ctx, rc, reg_lo); + return true; +} + +PhysReg get_reg(ra_ctx& ctx, + RegisterFile& reg_file, + Temp temp, + std::vector>& parallelcopies, + aco_ptr& instr, + int operand_index=-1) +{ + auto split_vec = ctx.split_vectors.find(temp.id()); + if (split_vec != ctx.split_vectors.end()) { + unsigned offset = 0; + for (Definition def : split_vec->second->definitions) { + auto affinity_it = ctx.affinities.find(def.tempId()); + if (affinity_it != ctx.affinities.end() && ctx.assignments[affinity_it->second].assigned) { + PhysReg reg = ctx.assignments[affinity_it->second].reg; + reg.reg_b -= offset; + if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg)) + return reg; + } + offset += def.bytes(); + } + } + + if (ctx.affinities.find(temp.id()) != ctx.affinities.end() && + ctx.assignments[ctx.affinities[temp.id()]].assigned) { + PhysReg reg = ctx.assignments[ctx.affinities[temp.id()]].reg; + if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg)) + return reg; + } + + if (ctx.vectors.find(temp.id()) != ctx.vectors.end()) { + Instruction* vec = ctx.vectors[temp.id()]; + unsigned byte_offset = 0; + for (const Operand& op : vec->operands) { + if (op.isTemp() && op.tempId() == temp.id()) + break; + else + byte_offset += op.bytes(); + } + unsigned k = 0; + for (const Operand& op : vec->operands) { + if (op.isTemp() && + op.tempId() != temp.id() && + op.getTemp().type() == temp.type() && + ctx.assignments[op.tempId()].assigned) { + PhysReg reg = ctx.assignments[op.tempId()].reg; + reg.reg_b += (byte_offset - k); + if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg)) + return reg; + } + k += op.bytes(); + } + + DefInfo info(ctx, ctx.pseudo_dummy, vec->definitions[0].regClass(), -1); + std::pair res = get_reg_simple(ctx, reg_file, info); + PhysReg reg = res.first; + if (res.second) { + reg.reg_b += byte_offset; + /* make sure to only use byte offset if the instruction supports it */ + if (get_reg_specified(ctx, reg_file, temp.regClass(), parallelcopies, instr, reg)) + return reg; + } + } + + DefInfo info(ctx, instr, temp.regClass(), operand_index); + /* try to find space without live-range splits */ - if (rc.type() == RegType::vgpr && (size == 4 || size == 8)) - res = get_reg_simple(ctx, reg_file, lb, ub, size, 4, rc); - if (!res.second) - res = get_reg_simple(ctx, reg_file, lb, ub, size, stride, rc); + std::pair res = get_reg_simple(ctx, reg_file, info); + if (res.second) return res.first; /* try to find space with live-range splits */ - res = get_reg_impl(ctx, reg_file, parallelcopies, lb, ub, size, stride, rc, instr); + res = get_reg_impl(ctx, reg_file, parallelcopies, info, instr); if (res.second) return res.first; - unsigned regs_free = 0; - for (unsigned i = lb; i < ub; i++) { - if (!reg_file[i]) - regs_free++; - } + /* try using more registers */ /* We should only fail here because keeping under the limit would require * too many moves. */ - assert(regs_free >= size); + assert(reg_file.count_zero(PhysReg{info.lb}, info.ub-info.lb) >= info.size); - /* try using more registers */ uint16_t max_addressible_sgpr = ctx.program->sgpr_limit; - if (rc.type() == RegType::vgpr && ctx.program->max_reg_demand.vgpr < 256) { + uint16_t max_addressible_vgpr = ctx.program->vgpr_limit; + if (info.rc.type() == RegType::vgpr && ctx.program->max_reg_demand.vgpr < max_addressible_vgpr) { update_vgpr_sgpr_demand(ctx.program, RegisterDemand(ctx.program->max_reg_demand.vgpr + 1, ctx.program->max_reg_demand.sgpr)); - return get_reg(ctx, reg_file, rc, parallelcopies, instr); - } else if (rc.type() == RegType::sgpr && ctx.program->max_reg_demand.sgpr < max_addressible_sgpr) { + return get_reg(ctx, reg_file, temp, parallelcopies, instr, operand_index); + } else if (info.rc.type() == RegType::sgpr && ctx.program->max_reg_demand.sgpr < max_addressible_sgpr) { update_vgpr_sgpr_demand(ctx.program, RegisterDemand(ctx.program->max_reg_demand.vgpr, ctx.program->max_reg_demand.sgpr + 1)); - return get_reg(ctx, reg_file, rc, parallelcopies, instr); + return get_reg(ctx, reg_file, temp, parallelcopies, instr, operand_index); } //FIXME: if nothing helps, shift-rotate the registers to make space - unreachable("did not find a register"); -} - - -std::pair get_reg_vec(ra_ctx& ctx, - std::array& reg_file, - RegClass rc) -{ - uint32_t size = rc.size(); - uint32_t stride = 1; - uint32_t lb, ub; - if (rc.type() == RegType::vgpr) { - lb = 256; - ub = 256 + ctx.program->max_reg_demand.vgpr; - } else { - lb = 0; - ub = ctx.program->max_reg_demand.sgpr; - if (size == 2) - stride = 2; - else if (size >= 4) - stride = 4; - } - return get_reg_simple(ctx, reg_file, lb, ub, size, stride, rc); + fprintf(stderr, "ACO: failed to allocate registers during shader compilation\n"); + abort(); } - PhysReg get_reg_create_vector(ra_ctx& ctx, - std::array& reg_file, - RegClass rc, + RegisterFile& reg_file, + Temp temp, std::vector>& parallelcopies, aco_ptr& instr) { + RegClass rc = temp.regClass(); /* create_vector instructions have different costs w.r.t. register coalescing */ uint32_t size = rc.size(); + uint32_t bytes = rc.bytes(); uint32_t stride = 1; uint32_t lb, ub; if (rc.type() == RegType::vgpr) { @@ -726,20 +1284,25 @@ PhysReg get_reg_create_vector(ra_ctx& ctx, stride = 4; } + //TODO: improve p_create_vector for sub-dword vectors + unsigned best_pos = -1; unsigned num_moves = 0xFF; bool best_war_hint = true; /* test for each operand which definition placement causes the least shuffle instructions */ - for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].size(), i++) { + for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].bytes(), i++) { // TODO: think about, if we can alias live operands on the same register - if (!instr->operands[i].isTemp() || !instr->operands[i].isKill() || instr->operands[i].getTemp().type() != rc.type()) + if (!instr->operands[i].isTemp() || !instr->operands[i].isKillBeforeDef() || instr->operands[i].getTemp().type() != rc.type()) continue; - if (offset > instr->operands[i].physReg()) + if (offset > instr->operands[i].physReg().reg_b) continue; - unsigned reg_lo = instr->operands[i].physReg() - offset; + unsigned reg_lo = instr->operands[i].physReg().reg_b - offset; + if (reg_lo % 4) + continue; + reg_lo /= 4; unsigned reg_hi = reg_lo + size - 1; unsigned k = 0; @@ -751,30 +1314,45 @@ PhysReg get_reg_create_vector(ra_ctx& ctx, // TODO: this can be improved */ if (reg_lo < lb || reg_hi >= ub || reg_lo % stride != 0) continue; - if (reg_lo > lb && reg_file[reg_lo] != 0 && reg_file[reg_lo] == reg_file[reg_lo - 1]) + if (reg_lo > lb && reg_file[reg_lo] != 0 && reg_file.get_id(PhysReg(reg_lo)) == reg_file.get_id(PhysReg(reg_lo).advance(-1))) continue; - if (reg_hi < ub - 1 && reg_file[reg_hi] != 0 && reg_file[reg_hi] == reg_file[reg_hi + 1]) + if (reg_hi < ub - 1 && reg_file[reg_hi] != 0 && reg_file.get_id(PhysReg(reg_hi).advance(3)) == reg_file.get_id(PhysReg(reg_hi).advance(4))) continue; /* count variables to be moved and check war_hint */ bool war_hint = false; - for (unsigned j = reg_lo; j <= reg_hi; j++) { - if (reg_file[j] != 0) - k++; + bool linear_vgpr = false; + for (unsigned j = reg_lo; j <= reg_hi && !linear_vgpr; j++) { + if (reg_file[j] != 0) { + if (reg_file[j] == 0xF0000000) { + PhysReg reg; + reg.reg_b = j * 4; + unsigned bytes_left = bytes - (j - reg_lo) * 4; + for (unsigned k = 0; k < MIN2(bytes_left, 4); k++, reg.reg_b++) + k += reg_file.test(reg, 1); + } else { + k += 4; + /* we cannot split live ranges of linear vgprs */ + if (ctx.assignments[reg_file[j]].rc & (1 << 6)) + linear_vgpr = true; + } + } war_hint |= ctx.war_hint[j]; } + if (linear_vgpr || (war_hint && !best_war_hint)) + continue; /* count operands in wrong positions */ - for (unsigned j = 0, offset = 0; j < instr->operands.size(); offset += instr->operands[j].size(), j++) { + for (unsigned j = 0, offset = 0; j < instr->operands.size(); offset += instr->operands[j].bytes(), j++) { if (j == i || !instr->operands[j].isTemp() || instr->operands[j].getTemp().type() != rc.type()) continue; - if (instr->operands[j].physReg() != reg_lo + offset) - k += instr->operands[j].size(); + if (instr->operands[j].physReg().reg_b != reg_lo * 4 + offset) + k += instr->operands[j].bytes(); } bool aligned = rc == RegClass::v4 && reg_lo % 4 == 0; - if (k > num_moves || (!aligned && k == num_moves) || (war_hint && !best_war_hint)) + if (k > num_moves || (!aligned && k == num_moves)) continue; best_pos = reg_lo; @@ -782,79 +1360,58 @@ PhysReg get_reg_create_vector(ra_ctx& ctx, best_war_hint = war_hint; } - if (num_moves >= size) - return get_reg(ctx, reg_file, rc, parallelcopies, instr); + if (num_moves >= bytes) + return get_reg(ctx, reg_file, temp, parallelcopies, instr); - /* collect variables to be moved */ - std::set> vars; - for (unsigned i = best_pos; i < best_pos + size; i++) { - if (reg_file[i] != 0) - vars.emplace(ctx.assignments[reg_file[i]].second.size(), reg_file[i]); - reg_file[i] = 0; + /* re-enable killed operands which are in the wrong position */ + for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].bytes(), i++) { + if (instr->operands[i].isTemp() && + instr->operands[i].isFirstKillBeforeDef() && + instr->operands[i].physReg().reg_b != best_pos * 4 + offset) + reg_file.fill(instr->operands[i]); } - /* move killed operands which aren't yet at the correct position */ - for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].size(), i++) { - if (instr->operands[i].isTemp() && instr->operands[i].isFirstKill() && instr->operands[i].getTemp().type() == rc.type()) { - if (instr->operands[i].physReg() != best_pos + offset) { - vars.emplace(instr->operands[i].size(), instr->operands[i].tempId()); - } else { - for (unsigned j = 0; j < instr->operands[i].size(); j++) - reg_file[instr->operands[i].physReg() + j] = instr->operands[i].tempId(); - } + /* collect variables to be moved */ + std::set> vars = collect_vars(ctx, reg_file, PhysReg{best_pos}, size); + + for (unsigned i = 0, offset = 0; i < instr->operands.size(); offset += instr->operands[i].bytes(), i++) { + if (!instr->operands[i].isTemp() || !instr->operands[i].isFirstKillBeforeDef() || + instr->operands[i].getTemp().type() != rc.type()) + continue; + bool correct_pos = instr->operands[i].physReg().reg_b == best_pos * 4 + offset; + /* GFX9+: move killed operands which aren't yet at the correct position + * Moving all killed operands generally leads to more register swaps. + * This is only done on GFX9+ because of the cheap v_swap instruction. + */ + if (ctx.program->chip_class >= GFX9 && !correct_pos) { + vars.emplace(instr->operands[i].bytes(), instr->operands[i].tempId()); + reg_file.clear(instr->operands[i]); + /* fill operands which are in the correct position to avoid overwriting */ + } else if (correct_pos) { + reg_file.fill(instr->operands[i]); } } - ASSERTED bool success = false; success = get_regs_for_copies(ctx, reg_file, parallelcopies, vars, lb, ub, instr, best_pos, best_pos + size - 1); assert(success); - update_renames(ctx, reg_file, parallelcopies, instr); + update_renames(ctx, reg_file, parallelcopies, instr, false); adjust_max_used_regs(ctx, rc, best_pos); - return PhysReg{best_pos}; -} - -bool get_reg_specified(ra_ctx& ctx, - std::array& reg_file, - RegClass rc, - std::vector>& parallelcopies, - aco_ptr& instr, - PhysReg reg) -{ - uint32_t size = rc.size(); - uint32_t stride = 1; - uint32_t lb, ub; - if (rc.type() == RegType::vgpr) { - lb = 256; - ub = 256 + ctx.program->max_reg_demand.vgpr; - } else { - if (size == 2) - stride = 2; - else if (size >= 4) - stride = 4; - if (reg % stride != 0) - return false; - lb = 0; - ub = ctx.program->max_reg_demand.sgpr; + /* remove killed operands from reg_file once again */ + for (unsigned i = 0; i < instr->operands.size(); i++) { + if (!instr->operands[i].isTemp() || !instr->operands[i].isFixed()) + continue; + assert(!instr->operands[i].isUndefined()); + if (instr->operands[i].isFirstKillBeforeDef()) + reg_file.clear(instr->operands[i]); } - uint32_t reg_lo = reg.reg; - uint32_t reg_hi = reg + (size - 1); - - if (reg_lo < lb || reg_hi >= ub || reg_lo > reg_hi) - return false; - - for (unsigned i = reg_lo; i <= reg_hi; i++) { - if (reg_file[i] != 0) - return false; - } - adjust_max_used_regs(ctx, rc, reg_lo); - return true; + return PhysReg{best_pos}; } void handle_pseudo(ra_ctx& ctx, - const std::array& reg_file, + const RegisterFile& reg_file, Instruction* instr) { if (instr->format != Format::PSEUDO) @@ -880,11 +1437,24 @@ void handle_pseudo(ra_ctx& ctx, break; } } - if (!writes_sgpr) + /* if all operands are constant, no need to care either */ + bool reads_sgpr = false; + bool reads_subdword = false; + for (Operand& op : instr->operands) { + if (op.isTemp() && op.getTemp().type() == RegType::sgpr) { + reads_sgpr = true; + break; + } + if (op.isTemp() && op.regClass().is_subdword()) + reads_subdword = true; + } + bool needs_scratch_reg = (writes_sgpr && reads_sgpr) || + (ctx.program->chip_class <= GFX7 && reads_subdword); + if (!needs_scratch_reg) return; Pseudo_instruction *pi = (Pseudo_instruction *)instr; - if (reg_file[scc.reg]) { + if (reg_file[scc.reg()]) { pi->tmp_in_scc = true; int reg = ctx.max_used_sgpr; @@ -894,7 +1464,10 @@ void handle_pseudo(ra_ctx& ctx, reg = ctx.max_used_sgpr + 1; for (; reg < ctx.program->max_reg_demand.sgpr && reg_file[reg]; reg++) ; - assert(reg < ctx.program->max_reg_demand.sgpr); + if (reg == ctx.program->max_reg_demand.sgpr) { + assert(reads_subdword && reg_file[m0] == 0); + reg = m0; + } } adjust_max_used_regs(ctx, s1, reg); @@ -904,8 +1477,17 @@ void handle_pseudo(ra_ctx& ctx, } } -bool operand_can_use_reg(aco_ptr& instr, unsigned idx, PhysReg reg) +bool operand_can_use_reg(chip_class chip, aco_ptr& instr, unsigned idx, PhysReg reg, RegClass rc) { + if (instr->operands[idx].isFixed()) + return instr->operands[idx].physReg() == reg; + + if (reg.byte()) { + unsigned stride = get_subdword_operand_stride(chip, instr, idx, rc); + if (reg.byte() % stride) + return false; + } + switch (instr->format) { case Format::SMEM: return reg != scc && @@ -918,196 +1500,211 @@ bool operand_can_use_reg(aco_ptr& instr, unsigned idx, PhysReg reg) } } -} /* end namespace */ +void get_reg_for_operand(ra_ctx& ctx, RegisterFile& register_file, + std::vector>& parallelcopy, + aco_ptr& instr, Operand& operand, unsigned operand_index) +{ + /* check if the operand is fixed */ + PhysReg dst; + if (operand.isFixed()) { + assert(operand.physReg() != ctx.assignments[operand.tempId()].reg); + + /* check if target reg is blocked, and move away the blocking var */ + if (register_file[operand.physReg().reg()]) { + assert(register_file[operand.physReg()] != 0xF0000000); + uint32_t blocking_id = register_file[operand.physReg().reg()]; + RegClass rc = ctx.assignments[blocking_id].rc; + Operand pc_op = Operand(Temp{blocking_id, rc}); + pc_op.setFixed(operand.physReg()); + + /* find free reg */ + PhysReg reg = get_reg(ctx, register_file, pc_op.getTemp(), parallelcopy, ctx.pseudo_dummy); + Definition pc_def = Definition(PhysReg{reg}, pc_op.regClass()); + register_file.clear(pc_op); + parallelcopy.emplace_back(pc_op, pc_def); + } + dst = operand.physReg(); + + } else { + dst = get_reg(ctx, register_file, operand.getTemp(), parallelcopy, instr, operand_index); + } + Operand pc_op = operand; + pc_op.setFixed(ctx.assignments[operand.tempId()].reg); + Definition pc_def = Definition(dst, pc_op.regClass()); + register_file.clear(pc_op); + parallelcopy.emplace_back(pc_op, pc_def); + update_renames(ctx, register_file, parallelcopy, instr, true); +} -void register_allocation(Program *program, std::vector> live_out_per_block) +Temp read_variable(ra_ctx& ctx, Temp val, unsigned block_idx) { - ra_ctx ctx(program); - - std::vector> renames(program->blocks.size()); - - struct phi_info { - Instruction* phi; - unsigned block_idx; - std::set uses; - }; - - bool filled[program->blocks.size()]; - bool sealed[program->blocks.size()]; - memset(filled, 0, sizeof filled); - memset(sealed, 0, sizeof sealed); - std::vector> incomplete_phis(program->blocks.size()); - std::map phi_map; - std::map affinities; - std::function read_variable; - std::function handle_live_in; - std::function::iterator)> try_remove_trivial_phi; - - read_variable = [&](Temp val, unsigned block_idx) -> Temp { - std::unordered_map::iterator it = renames[block_idx].find(val.id()); - assert(it != renames[block_idx].end()); + std::unordered_map::iterator it = ctx.renames[block_idx].find(val.id()); + if (it == ctx.renames[block_idx].end()) + return val; + else return it->second; - }; +} - handle_live_in = [&](Temp val, Block *block) -> Temp { - std::vector& preds = val.is_linear() ? block->linear_preds : block->logical_preds; - if (preds.size() == 0 && block->index != 0) { - renames[block->index][val.id()] = val; - return val; +Temp handle_live_in(ra_ctx& ctx, Temp val, Block* block) +{ + std::vector& preds = val.is_linear() ? block->linear_preds : block->logical_preds; + if (preds.size() == 0 || val.regClass() == val.regClass().as_linear()) + return val; + + assert(preds.size() > 0); + + Temp new_val; + if (!ctx.sealed[block->index]) { + /* consider rename from already processed predecessor */ + Temp tmp = read_variable(ctx, val, preds[0]); + + /* if the block is not sealed yet, we create an incomplete phi (which might later get removed again) */ + new_val = Temp{ctx.program->allocateId(), val.regClass()}; + ctx.assignments.emplace_back(); + aco_opcode opcode = val.is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi; + aco_ptr phi{create_instruction(opcode, Format::PSEUDO, preds.size(), 1)}; + phi->definitions[0] = Definition(new_val); + for (unsigned i = 0; i < preds.size(); i++) + phi->operands[i] = Operand(val); + if (tmp.regClass() == new_val.regClass()) + ctx.affinities[new_val.id()] = tmp.id(); + + ctx.phi_map.emplace(new_val.id(), phi_info{phi.get(), block->index}); + ctx.incomplete_phis[block->index].emplace_back(phi.get()); + block->instructions.insert(block->instructions.begin(), std::move(phi)); + + } else if (preds.size() == 1) { + /* if the block has only one predecessor, just look there for the name */ + new_val = read_variable(ctx, val, preds[0]); + } else { + /* there are multiple predecessors and the block is sealed */ + Temp ops[preds.size()]; + + /* get the rename from each predecessor and check if they are the same */ + bool needs_phi = false; + for (unsigned i = 0; i < preds.size(); i++) { + ops[i] = read_variable(ctx, val, preds[i]); + if (i == 0) + new_val = ops[i]; + else + needs_phi |= !(new_val == ops[i]); } - assert(preds.size() > 0); - Temp new_val; - if (!sealed[block->index]) { - /* consider rename from already processed predecessor */ - Temp tmp = read_variable(val, preds[0]); - - /* if the block is not sealed yet, we create an incomplete phi (which might later get removed again) */ - new_val = Temp{program->allocateId(), val.regClass()}; + if (needs_phi) { + /* the variable has been renamed differently in the predecessors: we need to insert a phi */ aco_opcode opcode = val.is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi; aco_ptr phi{create_instruction(opcode, Format::PSEUDO, preds.size(), 1)}; + new_val = Temp{ctx.program->allocateId(), val.regClass()}; phi->definitions[0] = Definition(new_val); - for (unsigned i = 0; i < preds.size(); i++) - phi->operands[i] = Operand(val); - if (tmp.regClass() == new_val.regClass()) - affinities[new_val.id()] = tmp.id(); - - phi_map.emplace(new_val.id(), phi_info{phi.get(), block->index}); - incomplete_phis[block->index].emplace_back(phi.get()); + for (unsigned i = 0; i < preds.size(); i++) { + phi->operands[i] = Operand(ops[i]); + phi->operands[i].setFixed(ctx.assignments[ops[i].id()].reg); + if (ops[i].regClass() == new_val.regClass()) + ctx.affinities[new_val.id()] = ops[i].id(); + } + ctx.assignments.emplace_back(); + assert(ctx.assignments.size() == ctx.program->peekAllocationId()); + ctx.phi_map.emplace(new_val.id(), phi_info{phi.get(), block->index}); block->instructions.insert(block->instructions.begin(), std::move(phi)); + } + } - } else if (preds.size() == 1) { - /* if the block has only one predecessor, just look there for the name */ - new_val = read_variable(val, preds[0]); - } else { - /* there are multiple predecessors and the block is sealed */ - Temp ops[preds.size()]; + if (new_val != val) { + ctx.renames[block->index][val.id()] = new_val; + ctx.orig_names[new_val.id()] = val; + } + return new_val; +} - /* we start assuming that the name is the same from all predecessors */ - renames[block->index][val.id()] = val; - bool needs_phi = false; +void try_remove_trivial_phi(ra_ctx& ctx, Temp temp) +{ + std::unordered_map::iterator info = ctx.phi_map.find(temp.id()); - /* get the rename from each predecessor and check if they are the same */ - for (unsigned i = 0; i < preds.size(); i++) { - ops[i] = read_variable(val, preds[i]); - if (i == 0) - new_val = ops[i]; - else - needs_phi |= !(new_val == ops[i]); - } + if (info == ctx.phi_map.end() || !ctx.sealed[info->second.block_idx]) + return; - if (needs_phi) { - /* the variable has been renamed differently in the predecessors: we need to insert a phi */ - aco_opcode opcode = val.is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi; - aco_ptr phi{create_instruction(opcode, Format::PSEUDO, preds.size(), 1)}; - new_val = Temp{program->allocateId(), val.regClass()}; - phi->definitions[0] = Definition(new_val); - for (unsigned i = 0; i < preds.size(); i++) { - phi->operands[i] = Operand(ops[i]); - phi->operands[i].setFixed(ctx.assignments[ops[i].id()].first); - if (ops[i].regClass() == new_val.regClass()) - affinities[new_val.id()] = ops[i].id(); - } - phi_map.emplace(new_val.id(), phi_info{phi.get(), block->index}); - block->instructions.insert(block->instructions.begin(), std::move(phi)); - } + assert(info->second.block_idx != 0); + Instruction* phi = info->second.phi; + Temp same = Temp(); + Definition def = phi->definitions[0]; + + /* a phi node is trivial if all operands are the same as the definition of the phi */ + for (const Operand& op : phi->operands) { + const Temp t = op.getTemp(); + if (t == same || t == def.getTemp()) { + assert(t == same || op.physReg() == def.physReg()); + continue; } + if (same != Temp()) + return; - renames[block->index][val.id()] = new_val; - renames[block->index][new_val.id()] = new_val; - ctx.orig_names[new_val.id()] = val; - return new_val; - }; - - try_remove_trivial_phi = [&] (std::map::iterator info) -> Temp { - assert(info->second.block_idx != 0); - Instruction* phi = info->second.phi; - Temp same = Temp(); - - Definition def = phi->definitions[0]; - /* a phi node is trivial if all operands are the same as the definition of the phi */ - for (const Operand& op : phi->operands) { - const Temp t = op.getTemp(); - if (t == same || t == def.getTemp()) + same = t; + } + assert(same != Temp() || same == def.getTemp()); + + /* reroute all uses to same and remove phi */ + std::vector phi_users; + std::unordered_map::iterator same_phi_info = ctx.phi_map.find(same.id()); + for (Instruction* instr : info->second.uses) { + assert(phi != instr); + /* recursively try to remove trivial phis */ + if (is_phi(instr)) { + /* ignore if the phi was already flagged trivial */ + if (instr->definitions.empty()) continue; - if (!(same == Temp()) || !(op.physReg() == def.physReg())) { - /* phi is not trivial */ - return def.getTemp(); - } - same = t; - } - assert(!(same == Temp() || same == def.getTemp())); - - /* reroute all uses to same and remove phi */ - std::vector::iterator> phi_users; - std::map::iterator same_phi_info = phi_map.find(same.id()); - for (Instruction* instr : info->second.uses) { - assert(phi != instr); - /* recursively try to remove trivial phis */ - if (is_phi(instr)) { - /* ignore if the phi was already flagged trivial */ - if (instr->definitions.empty()) - continue; - std::map::iterator it = phi_map.find(instr->definitions[0].tempId()); - if (it != phi_map.end() && it != info) - phi_users.emplace_back(it); - } - for (Operand& op : instr->operands) { - if (op.isTemp() && op.tempId() == def.tempId()) { - op.setTemp(same); - if (same_phi_info != phi_map.end()) - same_phi_info->second.uses.emplace(instr); - } + if (instr->definitions[0].getTemp() != temp) + phi_users.emplace_back(instr->definitions[0].getTemp()); + } + for (Operand& op : instr->operands) { + if (op.isTemp() && op.tempId() == def.tempId()) { + op.setTemp(same); + if (same_phi_info != ctx.phi_map.end()) + same_phi_info->second.uses.emplace(instr); } } + } - auto it = ctx.orig_names.find(same.id()); - unsigned orig_var = it != ctx.orig_names.end() ? it->second.id() : same.id(); - for (unsigned i = 0; i < program->blocks.size(); i++) { - auto it = renames[i].find(orig_var); - if (it != renames[i].end() && it->second == def.getTemp()) - renames[i][orig_var] = same; - } + auto it = ctx.orig_names.find(same.id()); + unsigned orig_var = it != ctx.orig_names.end() ? it->second.id() : same.id(); + for (unsigned i = 0; i < ctx.program->blocks.size(); i++) { + auto it = ctx.renames[i].find(orig_var); + if (it != ctx.renames[i].end() && it->second == def.getTemp()) + ctx.renames[i][orig_var] = same; + } - unsigned block_idx = info->second.block_idx; - phi->definitions.clear(); /* this indicates that the phi can be removed */ - phi_map.erase(info); - for (auto it : phi_users) { - if (sealed[it->second.block_idx]) - try_remove_trivial_phi(it); - } + phi->definitions.clear(); /* this indicates that the phi can be removed */ + ctx.phi_map.erase(info); + for (Temp t : phi_users) + try_remove_trivial_phi(ctx, t); + + return; +} + +} /* end namespace */ - /* due to the removal of other phis, the name might have changed once again! */ - return renames[block_idx][orig_var]; - }; - std::map vectors; +void register_allocation(Program *program, std::vector& live_out_per_block) +{ + ra_ctx ctx(program); std::vector> phi_ressources; - std::map temp_to_phi_ressources; + std::unordered_map temp_to_phi_ressources; for (std::vector::reverse_iterator it = program->blocks.rbegin(); it != program->blocks.rend(); it++) { Block& block = *it; /* first, compute the death points of all live vars within the block */ - std::set& live = live_out_per_block[block.index]; + TempSet& live = live_out_per_block[block.index]; std::vector>::reverse_iterator rit; for (rit = block.instructions.rbegin(); rit != block.instructions.rend(); ++rit) { aco_ptr& instr = *rit; - if (!is_phi(instr)) { - for (const Operand& op : instr->operands) { - if (op.isTemp()) - live.emplace(op.getTemp()); - } - if (instr->opcode == aco_opcode::p_create_vector) { - for (const Operand& op : instr->operands) { - if (op.isTemp() && op.getTemp().type() == instr->definitions[0].getTemp().type()) - vectors[op.tempId()] = instr.get(); - } + if (is_phi(instr)) { + if (instr->definitions[0].isKill() || instr->definitions[0].isFixed()) { + live.erase(instr->definitions[0].getTemp()); + continue; } - } else if (!instr->definitions[0].isKill() && !instr->definitions[0].isFixed()) { /* collect information about affinity-related temporaries */ std::vector affinity_related; /* affinity_related[0] is the last seen affinity-related temp */ @@ -1120,15 +1717,50 @@ void register_allocation(Program *program, std::vector> live_out_ } } phi_ressources.emplace_back(std::move(affinity_related)); + } else { + /* add vector affinities */ + if (instr->opcode == aco_opcode::p_create_vector) { + for (const Operand& op : instr->operands) { + if (op.isTemp() && op.isFirstKill() && op.getTemp().type() == instr->definitions[0].getTemp().type()) + ctx.vectors[op.tempId()] = instr.get(); + } + } + + if (instr->opcode == aco_opcode::p_split_vector && instr->operands[0].isFirstKillBeforeDef()) + ctx.split_vectors[instr->operands[0].tempId()] = instr.get(); + + /* add operands to live variables */ + for (const Operand& op : instr->operands) { + if (op.isTemp()) + live.emplace(op.getTemp()); + } } - /* erase from live */ - for (const Definition& def : instr->definitions) { - if (def.isTemp()) { - live.erase(def.getTemp()); - std::map::iterator it = temp_to_phi_ressources.find(def.tempId()); - if (it != temp_to_phi_ressources.end() && def.regClass() == phi_ressources[it->second][0].regClass()) - phi_ressources[it->second][0] = def.getTemp(); + /* erase definitions from live */ + for (unsigned i = 0; i < instr->definitions.size(); i++) { + const Definition& def = instr->definitions[i]; + if (!def.isTemp()) + continue; + live.erase(def.getTemp()); + /* mark last-seen phi operand */ + std::unordered_map::iterator it = temp_to_phi_ressources.find(def.tempId()); + if (it != temp_to_phi_ressources.end() && def.regClass() == phi_ressources[it->second][0].regClass()) { + phi_ressources[it->second][0] = def.getTemp(); + /* try to coalesce phi affinities with parallelcopies */ + Operand op = Operand(); + if (!def.isFixed() && instr->opcode == aco_opcode::p_parallelcopy) + op = instr->operands[i]; + else if ((instr->opcode == aco_opcode::v_mad_f32 || + (instr->opcode == aco_opcode::v_fma_f32 && program->chip_class >= GFX10) || + instr->opcode == aco_opcode::v_mad_f16 || + instr->opcode == aco_opcode::v_mad_legacy_f16 || + (instr->opcode == aco_opcode::v_fma_f16 && program->chip_class >= GFX10)) && !instr->usesModifiers()) + op = instr->operands[2]; + + if (op.isTemp() && op.isFirstKillBeforeDef() && def.regClass() == op.regClass()) { + phi_ressources[it->second].emplace_back(op.getTemp()); + temp_to_phi_ressources[op.tempId()] = it->second; + } } } } @@ -1138,25 +1770,25 @@ void register_allocation(Program *program, std::vector> live_out_ assert(vec.size() > 1); for (unsigned i = 1; i < vec.size(); i++) if (vec[i].id() != vec[0].id()) - affinities[vec[i].id()] = vec[0].id(); + ctx.affinities[vec[i].id()] = vec[0].id(); } /* state of register file after phis */ std::vector> sgpr_live_in(program->blocks.size()); for (Block& block : program->blocks) { - std::set& live = live_out_per_block[block.index]; + TempSet& live = live_out_per_block[block.index]; /* initialize register file */ assert(block.index != 0 || live.empty()); - std::array register_file = {0}; + RegisterFile register_file; ctx.war_hint.reset(); for (Temp t : live) { - Temp renamed = handle_live_in(t, &block); - if (ctx.assignments.find(renamed.id()) != ctx.assignments.end()) { - for (unsigned i = 0; i < t.size(); i++) - register_file[ctx.assignments[renamed.id()].first + i] = renamed.id(); - } + Temp renamed = handle_live_in(ctx, t, &block); + assignment& var = ctx.assignments[renamed.id()]; + /* due to live-range splits, the live-in might be a phi, now */ + if (var.assigned) + register_file.fill(Definition(renamed.id(), var.reg, var.rc)); } std::vector> instructions; @@ -1178,8 +1810,8 @@ void register_allocation(Program *program, std::vector> live_out_ if (definition.isKill()) { for (Operand& op : phi->operands) { assert(op.isTemp()); - if (ctx.assignments.find(op.tempId()) == ctx.assignments.end() || - ctx.assignments[op.tempId()].first != exec) { + if (!ctx.assignments[op.tempId()].assigned || + ctx.assignments[op.tempId()].reg != exec) { definition.setKill(false); break; } @@ -1190,10 +1822,8 @@ void register_allocation(Program *program, std::vector> live_out_ continue; assert(definition.physReg() == exec); - for (unsigned i = 0; i < definition.size(); i++) { - assert(register_file[definition.physReg() + i] == 0); - register_file[definition.physReg() + i] = definition.tempId(); - } + assert(!register_file.test(definition.physReg(), definition.bytes())); + register_file.fill(definition); ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()}; } @@ -1206,16 +1836,15 @@ void register_allocation(Program *program, std::vector> live_out_ if (definition.isKill() || definition.isFixed()) continue; - if (affinities.find(definition.tempId()) != affinities.end() && - ctx.assignments.find(affinities[definition.tempId()]) != ctx.assignments.end()) { - assert(ctx.assignments[affinities[definition.tempId()]].second == definition.regClass()); - PhysReg reg = ctx.assignments[affinities[definition.tempId()]].first; + if (ctx.affinities.find(definition.tempId()) != ctx.affinities.end() && + ctx.assignments[ctx.affinities[definition.tempId()]].assigned) { + assert(ctx.assignments[ctx.affinities[definition.tempId()]].rc == definition.regClass()); + PhysReg reg = ctx.assignments[ctx.affinities[definition.tempId()]].reg; bool try_use_special_reg = reg == scc || reg == exec; if (try_use_special_reg) { for (const Operand& op : phi->operands) { - if (!op.isTemp() || - ctx.assignments.find(op.tempId()) == ctx.assignments.end() || - !(ctx.assignments[op.tempId()].first == reg)) { + if (!(op.isTemp() && ctx.assignments[op.tempId()].assigned && + ctx.assignments[op.tempId()].reg == reg)) { try_use_special_reg = false; break; } @@ -1223,16 +1852,10 @@ void register_allocation(Program *program, std::vector> live_out_ if (!try_use_special_reg) continue; } - bool reg_free = true; - for (unsigned i = reg.reg; reg_free && i < reg + definition.size(); i++) { - if (register_file[i] != 0) - reg_free = false; - } /* only assign if register is still free */ - if (reg_free) { + if (!register_file.test(reg, definition.bytes())) { definition.setFixed(reg); - for (unsigned i = 0; i < definition.size(); i++) - register_file[definition.physReg() + i] = definition.tempId(); + register_file.fill(definition); ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()}; } } @@ -1248,16 +1871,13 @@ void register_allocation(Program *program, std::vector> live_out_ if (definition.isKill()) continue; - renames[block.index][definition.tempId()] = definition.getTemp(); - if (!definition.isFixed()) { std::vector> parallelcopy; /* try to find a register that is used by at least one operand */ for (const Operand& op : phi->operands) { - if (!op.isTemp() || - ctx.assignments.find(op.tempId()) == ctx.assignments.end()) + if (!(op.isTemp() && ctx.assignments[op.tempId()].assigned)) continue; - PhysReg reg = ctx.assignments[op.tempId()].first; + PhysReg reg = ctx.assignments[op.tempId()].reg; /* we tried this already on the previous loop */ if (reg == scc || reg == exec) continue; @@ -1267,34 +1887,42 @@ void register_allocation(Program *program, std::vector> live_out_ } } if (!definition.isFixed()) - definition.setFixed(get_reg(ctx, register_file, definition.regClass(), parallelcopy, phi)); + definition.setFixed(get_reg(ctx, register_file, definition.getTemp(), parallelcopy, phi)); /* process parallelcopy */ for (std::pair pc : parallelcopy) { - /* rename */ - std::map::iterator orig_it = ctx.orig_names.find(pc.first.tempId()); - Temp orig = pc.first.getTemp(); - if (orig_it != ctx.orig_names.end()) - orig = orig_it->second; - else - ctx.orig_names[pc.second.tempId()] = orig; - renames[block.index][orig.id()] = pc.second.getTemp(); - renames[block.index][pc.second.tempId()] = pc.second.getTemp(); - - /* see if it's a copy from a previous phi */ + /* see if it's a copy from a different phi */ //TODO: prefer moving some previous phis over live-ins //TODO: somehow prevent phis fixed before the RA from being updated (shouldn't be a problem in practice since they can only be fixed to exec) Instruction *prev_phi = NULL; - for (auto it2 = instructions.begin(); it2 != instructions.end(); ++it2) { - if ((*it2)->definitions[0].tempId() == pc.first.tempId()) - prev_phi = it2->get(); + std::vector>::iterator phi_it; + for (phi_it = instructions.begin(); phi_it != instructions.end(); ++phi_it) { + if ((*phi_it)->definitions[0].tempId() == pc.first.tempId()) + prev_phi = phi_it->get(); + } + phi_it = it; + while (!prev_phi && is_phi(*++phi_it)) { + if ((*phi_it)->definitions[0].tempId() == pc.first.tempId()) + prev_phi = phi_it->get(); } if (prev_phi) { - /* if so, just update that phi */ - prev_phi->definitions[0] = pc.second; + /* if so, just update that phi's register */ + register_file.clear(prev_phi->definitions[0]); + prev_phi->definitions[0].setFixed(pc.second.physReg()); + ctx.assignments[prev_phi->definitions[0].tempId()] = {pc.second.physReg(), pc.second.regClass()}; + register_file.fill(prev_phi->definitions[0]); continue; } + /* rename */ + std::unordered_map::iterator orig_it = ctx.orig_names.find(pc.first.tempId()); + Temp orig = pc.first.getTemp(); + if (orig_it != ctx.orig_names.end()) + orig = orig_it->second; + else + ctx.orig_names[pc.second.tempId()] = orig; + ctx.renames[block.index][orig.id()] = pc.second.getTemp(); + /* otherwise, this is a live-in and we need to create a new phi * to move it in this block's predecessors */ aco_opcode opcode = pc.first.getTemp().is_linear() ? aco_opcode::p_linear_phi : aco_opcode::p_phi; @@ -1306,8 +1934,7 @@ void register_allocation(Program *program, std::vector> live_out_ instructions.emplace_back(std::move(new_phi)); } - for (unsigned i = 0; i < definition.size(); i++) - register_file[definition.physReg() + i] = definition.tempId(); + register_file.fill(definition); ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()}; } live.emplace(definition.getTemp()); @@ -1315,16 +1942,16 @@ void register_allocation(Program *program, std::vector> live_out_ /* update phi affinities */ for (const Operand& op : phi->operands) { if (op.isTemp() && op.regClass() == phi->definitions[0].regClass()) - affinities[op.tempId()] = definition.tempId(); + ctx.affinities[op.tempId()] = definition.tempId(); } instructions.emplace_back(std::move(*it)); } /* fill in sgpr_live_in */ - for (unsigned i = 0; i < ctx.max_used_sgpr; i++) + for (unsigned i = 0; i <= ctx.max_used_sgpr; i++) sgpr_live_in[block.index][i] = register_file[i]; - sgpr_live_in[block.index][127] = register_file[scc.reg]; + sgpr_live_in[block.index][127] = register_file[scc.reg()]; /* Handle all other instructions of the block */ for (; it != block.instructions.end(); ++it) { @@ -1349,9 +1976,9 @@ void register_allocation(Program *program, std::vector> live_out_ if (phi->opcode == aco_opcode::p_phi) { if (phi->operands[idx].isTemp() && phi->operands[idx].getTemp().type() == RegType::sgpr && - phi->operands[idx].isFirstKill()) { - Temp phi_op = read_variable(phi->operands[idx].getTemp(), block.index); - PhysReg reg = ctx.assignments[phi_op.id()].first; + phi->operands[idx].isFirstKillBeforeDef()) { + Temp phi_op = read_variable(ctx, phi->operands[idx].getTemp(), block.index); + PhysReg reg = ctx.assignments[phi_op.id()].reg; assert(register_file[reg] == phi_op.id()); register_file[reg] = 0; } @@ -1374,126 +2001,94 @@ void register_allocation(Program *program, std::vector> live_out_ continue; /* rename operands */ - operand.setTemp(read_variable(operand.getTemp(), block.index)); - - /* check if the operand is fixed */ - if (operand.isFixed()) { - - if (operand.physReg() == ctx.assignments[operand.tempId()].first) { - /* we are fine: the operand is already assigned the correct reg */ - - } else { - /* check if target reg is blocked, and move away the blocking var */ - if (register_file[operand.physReg().reg]) { - uint32_t blocking_id = register_file[operand.physReg().reg]; - RegClass rc = ctx.assignments[blocking_id].second; - Operand pc_op = Operand(Temp{blocking_id, rc}); - pc_op.setFixed(operand.physReg()); - Definition pc_def = Definition(Temp{program->allocateId(), pc_op.regClass()}); - /* find free reg */ - PhysReg reg = get_reg(ctx, register_file, pc_op.regClass(), parallelcopy, instr); - pc_def.setFixed(reg); - ctx.assignments[pc_def.tempId()] = {reg, pc_def.regClass()}; - for (unsigned i = 0; i < operand.size(); i++) { - register_file[pc_op.physReg() + i] = 0; - register_file[pc_def.physReg() + i] = pc_def.tempId(); - } - parallelcopy.emplace_back(pc_op, pc_def); - - /* handle renames of previous operands */ - for (unsigned j = 0; j < i; j++) { - Operand& op = instr->operands[j]; - if (op.isTemp() && op.tempId() == blocking_id) { - op = Operand(pc_def.getTemp()); - op.setFixed(reg); - } - } - } - /* move operand to fixed reg and create parallelcopy pair */ - Operand pc_op = operand; - Temp tmp = Temp{program->allocateId(), operand.regClass()}; - Definition pc_def = Definition(tmp); - pc_def.setFixed(operand.physReg()); - pc_op.setFixed(ctx.assignments[operand.tempId()].first); - operand.setTemp(tmp); - ctx.assignments[tmp.id()] = {pc_def.physReg(), pc_def.regClass()}; - operand.setFixed(pc_def.physReg()); - for (unsigned i = 0; i < operand.size(); i++) { - register_file[pc_op.physReg() + i] = 0; - register_file[pc_def.physReg() + i] = tmp.id(); - } - parallelcopy.emplace_back(pc_op, pc_def); - } - } else { - assert(ctx.assignments.find(operand.tempId()) != ctx.assignments.end()); - PhysReg reg = ctx.assignments[operand.tempId()].first; + operand.setTemp(read_variable(ctx, operand.getTemp(), block.index)); + assert(ctx.assignments[operand.tempId()].assigned); - if (operand_can_use_reg(instr, i, reg)) { - operand.setFixed(ctx.assignments[operand.tempId()].first); - } else { - Operand pc_op = operand; - pc_op.setFixed(reg); - PhysReg new_reg = get_reg(ctx, register_file, operand.regClass(), parallelcopy, instr); - Definition pc_def = Definition(program->allocateId(), new_reg, pc_op.regClass()); - ctx.assignments[pc_def.tempId()] = {reg, pc_def.regClass()}; - for (unsigned i = 0; i < operand.size(); i++) { - register_file[pc_op.physReg() + i] = 0; - register_file[pc_def.physReg() + i] = pc_def.tempId(); - } - parallelcopy.emplace_back(pc_op, pc_def); - operand.setFixed(new_reg); - } + PhysReg reg = ctx.assignments[operand.tempId()].reg; + if (operand_can_use_reg(program->chip_class, instr, i, reg, operand.regClass())) + operand.setFixed(reg); + else + get_reg_for_operand(ctx, register_file, parallelcopy, instr, operand, i); - if (instr->format == Format::EXP || - (instr->isVMEM() && i == 3 && program->chip_class == GFX6) || - (instr->format == Format::DS && static_cast(instr.get())->gds)) { - for (unsigned j = 0; j < operand.size(); j++) - ctx.war_hint.set(operand.physReg().reg + j); - } + if (instr->format == Format::EXP || + (instr->isVMEM() && i == 3 && ctx.program->chip_class == GFX6) || + (instr->format == Format::DS && static_cast(instr.get())->gds)) { + for (unsigned j = 0; j < operand.size(); j++) + ctx.war_hint.set(operand.physReg().reg() + j); } - std::map::iterator phi = phi_map.find(operand.getTemp().id()); - if (phi != phi_map.end()) - phi->second.uses.emplace(instr.get()); + std::unordered_map::iterator phi = ctx.phi_map.find(operand.getTemp().id()); + if (phi != ctx.phi_map.end()) + phi->second.uses.emplace(instr.get()); } + /* remove dead vars from register file */ for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isFirstKill()) - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0; + if (op.isTemp() && op.isFirstKillBeforeDef()) + register_file.clear(op); } /* try to optimize v_mad_f32 -> v_mac_f32 */ - if (instr->opcode == aco_opcode::v_mad_f32 && + if ((instr->opcode == aco_opcode::v_mad_f32 || + (instr->opcode == aco_opcode::v_fma_f32 && program->chip_class >= GFX10) || + instr->opcode == aco_opcode::v_mad_f16 || + instr->opcode == aco_opcode::v_mad_legacy_f16 || + (instr->opcode == aco_opcode::v_fma_f16 && program->chip_class >= GFX10)) && instr->operands[2].isTemp() && - instr->operands[2].isKill() && + instr->operands[2].isKillBeforeDef() && instr->operands[2].getTemp().type() == RegType::vgpr && instr->operands[1].isTemp() && - instr->operands[1].getTemp().type() == RegType::vgpr) { /* TODO: swap src0 and src1 in this case */ - VOP3A_instruction* vop3 = static_cast(instr.get()); - bool can_use_mac = !(vop3->abs[0] || vop3->abs[1] || vop3->abs[2] || - vop3->opsel[0] || vop3->opsel[1] || vop3->opsel[2] || - vop3->neg[0] || vop3->neg[1] || vop3->neg[2] || - vop3->clamp || vop3->omod); - if (can_use_mac) { + instr->operands[1].getTemp().type() == RegType::vgpr && + !instr->usesModifiers() && + instr->operands[0].physReg().byte() == 0 && + instr->operands[1].physReg().byte() == 0 && + instr->operands[2].physReg().byte() == 0) { + unsigned def_id = instr->definitions[0].tempId(); + auto it = ctx.affinities.find(def_id); + if (it == ctx.affinities.end() || !ctx.assignments[it->second].assigned || + instr->operands[2].physReg() == ctx.assignments[it->second].reg || + register_file.test(ctx.assignments[it->second].reg, instr->operands[2].bytes())) { instr->format = Format::VOP2; - instr->opcode = aco_opcode::v_mac_f32; + switch (instr->opcode) { + case aco_opcode::v_mad_f32: + instr->opcode = aco_opcode::v_mac_f32; + break; + case aco_opcode::v_fma_f32: + instr->opcode = aco_opcode::v_fmac_f32; + break; + case aco_opcode::v_mad_f16: + case aco_opcode::v_mad_legacy_f16: + instr->opcode = aco_opcode::v_mac_f16; + break; + case aco_opcode::v_fma_f16: + instr->opcode = aco_opcode::v_fmac_f16; + break; + default: + break; + } } } /* handle definitions which must have the same register as an operand */ if (instr->opcode == aco_opcode::v_interp_p2_f32 || instr->opcode == aco_opcode::v_mac_f32 || - instr->opcode == aco_opcode::v_writelane_b32) { + instr->opcode == aco_opcode::v_fmac_f32 || + instr->opcode == aco_opcode::v_mac_f16 || + instr->opcode == aco_opcode::v_fmac_f16 || + instr->opcode == aco_opcode::v_writelane_b32 || + instr->opcode == aco_opcode::v_writelane_b32_e64) { instr->definitions[0].setFixed(instr->operands[2].physReg()); } else if (instr->opcode == aco_opcode::s_addk_i32 || instr->opcode == aco_opcode::s_mulk_i32) { instr->definitions[0].setFixed(instr->operands[0].physReg()); - } else if ((instr->format == Format::MUBUF || - instr->format == Format::MIMG) && - instr->definitions.size() == 1 && - instr->operands.size() == 4) { + } else if (instr->format == Format::MUBUF && + instr->definitions.size() == 1 && + instr->operands.size() == 4) { instr->definitions[0].setFixed(instr->operands[3].physReg()); + } else if (instr->format == Format::MIMG && + instr->definitions.size() == 1 && + instr->operands[1].regClass().type() == RegType::vgpr) { + instr->definitions[0].setFixed(instr->operands[1].physReg()); } ctx.defs_done.reset(); @@ -1506,45 +2101,34 @@ void register_allocation(Program *program, std::vector> live_out_ adjust_max_used_regs(ctx, definition.regClass(), definition.physReg()); /* check if the target register is blocked */ - if (register_file[definition.physReg().reg] != 0) { - /* create parallelcopy pair to move blocking var */ - Temp tmp = {register_file[definition.physReg()], ctx.assignments[register_file[definition.physReg()]].second}; - Operand pc_op = Operand(tmp); - pc_op.setFixed(ctx.assignments[register_file[definition.physReg().reg]].first); - RegClass rc = pc_op.regClass(); - tmp = Temp{program->allocateId(), rc}; - Definition pc_def = Definition(tmp); - - /* re-enable the killed operands, so that we don't move the blocking var there */ + if (register_file.test(definition.physReg(), definition.bytes())) { + /* create parallelcopy pair to move blocking vars */ + std::set> vars = collect_vars(ctx, register_file, definition.physReg(), definition.size()); + + /* re-enable the killed operands, so that we don't move the blocking vars there */ for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isFirstKill()) - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0xFFFF; + if (op.isTemp() && op.isFirstKillBeforeDef()) + register_file.fill(op); } - /* find a new register for the blocking variable */ - PhysReg reg = get_reg(ctx, register_file, rc, parallelcopy, instr); + ASSERTED bool success = false; + DefInfo info(ctx, instr, definition.regClass(), -1); + success = get_regs_for_copies(ctx, register_file, parallelcopy, + vars, info.lb, info.ub, instr, + definition.physReg(), + definition.physReg() + definition.size() - 1); + assert(success); + + update_renames(ctx, register_file, parallelcopy, instr, false); + /* once again, disable killed operands */ for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isFirstKill()) - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0; + if (op.isTemp() && op.isFirstKillBeforeDef()) + register_file.clear(op); } for (unsigned k = 0; k < i; k++) { if (instr->definitions[k].isTemp() && ctx.defs_done.test(k) && !instr->definitions[k].isKill()) - for (unsigned j = 0; j < instr->definitions[k].size(); j++) - register_file[instr->definitions[k].physReg() + j] = instr->definitions[k].tempId(); - } - pc_def.setFixed(reg); - - /* finish assignment of parallelcopy */ - ctx.assignments[pc_def.tempId()] = {reg, pc_def.regClass()}; - parallelcopy.emplace_back(pc_op, pc_def); - - /* add changes to reg_file */ - for (unsigned i = 0; i < pc_op.size(); i++) { - register_file[pc_op.physReg() + i] = 0x0; - register_file[pc_def.physReg() + i] = pc_def.tempId(); + register_file.fill(instr->definitions[k]); } } ctx.defs_done.set(i); @@ -1557,135 +2141,100 @@ void register_allocation(Program *program, std::vector> live_out_ live.emplace(definition.getTemp()); ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()}; - renames[block.index][definition.tempId()] = definition.getTemp(); - for (unsigned j = 0; j < definition.size(); j++) - register_file[definition.physReg() + j] = definition.tempId(); + register_file.fill(definition); } /* handle all other definitions */ for (unsigned i = 0; i < instr->definitions.size(); ++i) { - auto& definition = instr->definitions[i]; + Definition *definition = &instr->definitions[i]; - if (definition.isFixed() || !definition.isTemp()) + if (definition->isFixed() || !definition->isTemp()) continue; /* find free reg */ - if (definition.hasHint() && register_file[definition.physReg().reg] == 0) - definition.setFixed(definition.physReg()); + if (definition->hasHint() && register_file[definition->physReg().reg()] == 0) + definition->setFixed(definition->physReg()); else if (instr->opcode == aco_opcode::p_split_vector) { - PhysReg reg = PhysReg{instr->operands[0].physReg() + i * definition.size()}; - if (!get_reg_specified(ctx, register_file, definition.regClass(), parallelcopy, instr, reg)) - reg = get_reg(ctx, register_file, definition.regClass(), parallelcopy, instr); - definition.setFixed(reg); - } else if (instr->opcode == aco_opcode::p_wqm) { - PhysReg reg; - if (instr->operands[0].isKill() && instr->operands[0].getTemp().type() == definition.getTemp().type()) { - reg = instr->operands[0].physReg(); - assert(register_file[reg.reg] == 0); - } else { - reg = get_reg(ctx, register_file, definition.regClass(), parallelcopy, instr); - } - definition.setFixed(reg); + PhysReg reg = instr->operands[0].physReg(); + for (unsigned j = 0; j < i; j++) + reg.reg_b += instr->definitions[j].bytes(); + if (get_reg_specified(ctx, register_file, definition->regClass(), parallelcopy, instr, reg)) + definition->setFixed(reg); + } else if (instr->opcode == aco_opcode::p_wqm || instr->opcode == aco_opcode::p_parallelcopy) { + PhysReg reg = instr->operands[i].physReg(); + if (instr->operands[i].isTemp() && + instr->operands[i].getTemp().type() == definition->getTemp().type() && + !register_file.test(reg, definition->bytes())) + definition->setFixed(reg); } else if (instr->opcode == aco_opcode::p_extract_vector) { PhysReg reg; - if (instr->operands[0].isKill() && - instr->operands[0].getTemp().type() == definition.getTemp().type()) { + if (instr->operands[0].isKillBeforeDef() && + instr->operands[0].getTemp().type() == definition->getTemp().type()) { reg = instr->operands[0].physReg(); - reg.reg += definition.size() * instr->operands[1].constantValue(); - assert(register_file[reg.reg] == 0); - } else { - reg = get_reg(ctx, register_file, definition.regClass(), parallelcopy, instr); + reg.reg_b += definition->bytes() * instr->operands[1].constantValue(); + assert(!register_file.test(reg, definition->bytes())); + definition->setFixed(reg); } - definition.setFixed(reg); } else if (instr->opcode == aco_opcode::p_create_vector) { - PhysReg reg = get_reg_create_vector(ctx, register_file, definition.regClass(), + PhysReg reg = get_reg_create_vector(ctx, register_file, definition->getTemp(), parallelcopy, instr); - definition.setFixed(reg); - } else if (affinities.find(definition.tempId()) != affinities.end() && - ctx.assignments.find(affinities[definition.tempId()]) != ctx.assignments.end()) { - PhysReg reg = ctx.assignments[affinities[definition.tempId()]].first; - if (get_reg_specified(ctx, register_file, definition.regClass(), parallelcopy, instr, reg)) - definition.setFixed(reg); - else - definition.setFixed(get_reg(ctx, register_file, definition.regClass(), parallelcopy, instr)); + definition->setFixed(reg); + } - } else if (vectors.find(definition.tempId()) != vectors.end()) { - Instruction* vec = vectors[definition.tempId()]; - unsigned offset = 0; - for (const Operand& op : vec->operands) { - if (op.isTemp() && op.tempId() == definition.tempId()) - break; - else - offset += op.size(); - } - unsigned k = 0; - for (const Operand& op : vec->operands) { - if (op.isTemp() && - op.tempId() != definition.tempId() && - op.getTemp().type() == definition.getTemp().type() && - ctx.assignments.find(op.tempId()) != ctx.assignments.end()) { - PhysReg reg = ctx.assignments[op.tempId()].first; - reg.reg = reg - k + offset; - if (get_reg_specified(ctx, register_file, definition.regClass(), parallelcopy, instr, reg)) { - definition.setFixed(reg); - break; - } - } - k += op.size(); - } - if (!definition.isFixed()) { - std::pair res = get_reg_vec(ctx, register_file, vec->definitions[0].regClass()); - PhysReg reg = res.first; - if (res.second) { - reg.reg += offset; - } else { - reg = get_reg(ctx, register_file, definition.regClass(), parallelcopy, instr); - } - definition.setFixed(reg); + if (!definition->isFixed()) { + Temp tmp = definition->getTemp(); + if (definition->regClass().is_subdword() && definition->bytes() < 4) { + PhysReg reg = get_reg(ctx, register_file, tmp, parallelcopy, instr); + bool partial = !(tmp.bytes() <= 4 && reg.byte() == 0 && !register_file.test(reg, 4)); + add_subdword_definition(program, instr, i, reg, partial); + definition = &instr->definitions[i]; /* add_subdword_definition can invalidate the reference */ + } else { + definition->setFixed(get_reg(ctx, register_file, tmp, parallelcopy, instr)); } - } else - definition.setFixed(get_reg(ctx, register_file, definition.regClass(), parallelcopy, instr)); + } - assert(definition.isFixed() && ((definition.getTemp().type() == RegType::vgpr && definition.physReg() >= 256) || - (definition.getTemp().type() != RegType::vgpr && definition.physReg() < 256))); + assert(definition->isFixed() && ((definition->getTemp().type() == RegType::vgpr && definition->physReg() >= 256) || + (definition->getTemp().type() != RegType::vgpr && definition->physReg() < 256))); ctx.defs_done.set(i); /* set live if it has a kill point */ - if (!definition.isKill()) - live.emplace(definition.getTemp()); + if (!definition->isKill()) + live.emplace(definition->getTemp()); - ctx.assignments[definition.tempId()] = {definition.physReg(), definition.regClass()}; - renames[block.index][definition.tempId()] = definition.getTemp(); - for (unsigned j = 0; j < definition.size(); j++) - register_file[definition.physReg() + j] = definition.tempId(); + ctx.assignments[definition->tempId()] = {definition->physReg(), definition->regClass()}; + register_file.fill(*definition); } handle_pseudo(ctx, register_file, instr.get()); - /* kill definitions */ + /* kill definitions and late-kill operands and ensure that sub-dword operands can actually be read */ for (const Definition& def : instr->definitions) { - if (def.isTemp() && def.isKill()) { - for (unsigned j = 0; j < def.size(); j++) { - register_file[def.physReg() + j] = 0; - } - } + if (def.isTemp() && def.isKill()) + register_file.clear(def); + } + for (unsigned i = 0; i < instr->operands.size(); i++) { + const Operand& op = instr->operands[i]; + if (op.isTemp() && op.isFirstKill() && op.isLateKill()) + register_file.clear(op); + if (op.isTemp() && op.physReg().byte() != 0) + add_subdword_operand(program->chip_class, instr, i, op.physReg().byte(), op.regClass()); } /* emit parallelcopy */ if (!parallelcopy.empty()) { aco_ptr pc; pc.reset(create_instruction(aco_opcode::p_parallelcopy, Format::PSEUDO, parallelcopy.size(), parallelcopy.size())); - bool temp_in_scc = register_file[scc.reg]; + bool temp_in_scc = register_file[scc.reg()]; bool sgpr_operands_alias_defs = false; uint64_t sgpr_operands[4] = {0, 0, 0, 0}; for (unsigned i = 0; i < parallelcopy.size(); i++) { if (temp_in_scc && parallelcopy[i].first.isTemp() && parallelcopy[i].first.getTemp().type() == RegType::sgpr) { if (!sgpr_operands_alias_defs) { - unsigned reg = parallelcopy[i].first.physReg().reg; + unsigned reg = parallelcopy[i].first.physReg().reg(); unsigned size = parallelcopy[i].first.getTemp().size(); sgpr_operands[reg / 64u] |= ((1u << size) - 1) << (reg % 64u); - reg = parallelcopy[i].second.physReg().reg; + reg = parallelcopy[i].second.physReg().reg(); size = parallelcopy[i].second.getTemp().size(); if (sgpr_operands[reg / 64u] & ((1u << size) - 1) << (reg % 64u)) sgpr_operands_alias_defs = true; @@ -1694,36 +2243,28 @@ void register_allocation(Program *program, std::vector> live_out_ pc->operands[i] = parallelcopy[i].first; pc->definitions[i] = parallelcopy[i].second; + assert(pc->operands[i].size() == pc->definitions[i].size()); /* it might happen that the operand is already renamed. we have to restore the original name. */ - std::map::iterator it = ctx.orig_names.find(pc->operands[i].tempId()); - if (it != ctx.orig_names.end()) - pc->operands[i].setTemp(it->second); - unsigned orig_id = pc->operands[i].tempId(); - ctx.orig_names[pc->definitions[i].tempId()] = pc->operands[i].getTemp(); - - pc->operands[i].setTemp(read_variable(pc->operands[i].getTemp(), block.index)); - renames[block.index][orig_id] = pc->definitions[i].getTemp(); - renames[block.index][pc->definitions[i].tempId()] = pc->definitions[i].getTemp(); - std::map::iterator phi = phi_map.find(pc->operands[i].tempId()); - if (phi != phi_map.end()) + std::unordered_map::iterator it = ctx.orig_names.find(pc->operands[i].tempId()); + Temp orig = it != ctx.orig_names.end() ? it->second : pc->operands[i].getTemp(); + ctx.orig_names[pc->definitions[i].tempId()] = orig; + ctx.renames[block.index][orig.id()] = pc->definitions[i].getTemp(); + + std::unordered_map::iterator phi = ctx.phi_map.find(pc->operands[i].tempId()); + if (phi != ctx.phi_map.end()) phi->second.uses.emplace(pc.get()); } if (temp_in_scc && sgpr_operands_alias_defs) { /* disable definitions and re-enable operands */ for (const Definition& def : instr->definitions) { - if (def.isTemp() && !def.isKill()) { - for (unsigned j = 0; j < def.size(); j++) { - register_file[def.physReg() + j] = 0x0; - } - } + if (def.isTemp() && !def.isKill()) + register_file.clear(def); } for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isFirstKill()) { - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0xFFFF; - } + if (op.isTemp() && op.isFirstKill()) + register_file.block(op.physReg(), op.regClass()); } handle_pseudo(ctx, register_file, pc.get()); @@ -1731,15 +2272,11 @@ void register_allocation(Program *program, std::vector> live_out_ /* re-enable live vars */ for (const Operand& op : instr->operands) { if (op.isTemp() && op.isFirstKill()) - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0x0; + register_file.clear(op); } for (const Definition& def : instr->definitions) { - if (def.isTemp() && !def.isKill()) { - for (unsigned j = 0; j < def.size(); j++) { - register_file[def.physReg() + j] = def.tempId(); - } - } + if (def.isTemp() && !def.isKill()) + register_file.fill(def); } } else { pc->tmp_in_scc = false; @@ -1766,7 +2303,7 @@ void register_allocation(Program *program, std::vector> live_out_ if (instr_needs_vop3) { /* if the first operand is a literal, we have to move it to a reg */ - if (instr->operands.size() && instr->operands[0].isLiteral()) { + if (instr->operands.size() && instr->operands[0].isLiteral() && program->chip_class < GFX10) { bool can_sgpr = true; /* check, if we have to move to vgpr */ for (const Operand& op : instr->operands) { @@ -1775,42 +2312,37 @@ void register_allocation(Program *program, std::vector> live_out_ break; } } + /* disable definitions and re-enable operands */ + for (const Definition& def : instr->definitions) + register_file.clear(def); + for (const Operand& op : instr->operands) { + if (op.isTemp() && op.isFirstKill()) + register_file.block(op.physReg(), op.regClass()); + } + Temp tmp = {program->allocateId(), can_sgpr ? s1 : v1}; + ctx.assignments.emplace_back(); + PhysReg reg = get_reg(ctx, register_file, tmp, parallelcopy, instr); + aco_ptr mov; if (can_sgpr) mov.reset(create_instruction(aco_opcode::s_mov_b32, Format::SOP1, 1, 1)); else mov.reset(create_instruction(aco_opcode::v_mov_b32, Format::VOP1, 1, 1)); mov->operands[0] = instr->operands[0]; - Temp tmp = {program->allocateId(), can_sgpr ? s1 : v1}; mov->definitions[0] = Definition(tmp); - /* disable definitions and re-enable operands */ - for (const Definition& def : instr->definitions) { - for (unsigned j = 0; j < def.size(); j++) { - register_file[def.physReg() + j] = 0x0; - } - } - for (const Operand& op : instr->operands) { - if (op.isTemp() && op.isFirstKill()) { - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0xFFFF; - } - } - mov->definitions[0].setFixed(get_reg(ctx, register_file, tmp.regClass(), parallelcopy, mov)); + mov->definitions[0].setFixed(reg); + instr->operands[0] = Operand(tmp); - instr->operands[0].setFixed(mov->definitions[0].physReg()); + instr->operands[0].setFixed(reg); instructions.emplace_back(std::move(mov)); /* re-enable live vars */ for (const Operand& op : instr->operands) { if (op.isTemp() && op.isFirstKill()) - for (unsigned j = 0; j < op.size(); j++) - register_file[op.physReg() + j] = 0x0; + register_file.clear(op); } for (const Definition& def : instr->definitions) { - if (def.isTemp() && !def.isKill()) { - for (unsigned j = 0; j < def.size(); j++) { - register_file[def.physReg() + j] = def.tempId(); - } - } + if (def.isTemp() && !def.isKill()) + register_file.fill(def); } } @@ -1823,8 +2355,8 @@ void register_allocation(Program *program, std::vector> live_out_ instr->operands[i] = operand; /* keep phi_map up to date */ if (operand.isTemp()) { - std::map::iterator phi = phi_map.find(operand.tempId()); - if (phi != phi_map.end()) { + std::unordered_map::iterator phi = ctx.phi_map.find(operand.tempId()); + if (phi != ctx.phi_map.end()) { phi->second.uses.erase(tmp.get()); phi->second.uses.emplace(instr.get()); } @@ -1832,32 +2364,35 @@ void register_allocation(Program *program, std::vector> live_out_ } std::copy(tmp->definitions.begin(), tmp->definitions.end(), instr->definitions.begin()); } + instructions.emplace_back(std::move(*it)); } /* end for Instr */ block.instructions = std::move(instructions); - filled[block.index] = true; + ctx.filled[block.index] = true; for (unsigned succ_idx : block.linear_succs) { Block& succ = program->blocks[succ_idx]; /* seal block if all predecessors are filled */ bool all_filled = true; for (unsigned pred_idx : succ.linear_preds) { - if (!filled[pred_idx]) { + if (!ctx.filled[pred_idx]) { all_filled = false; break; } } if (all_filled) { + ctx.sealed[succ_idx] = true; + /* finish incomplete phis and check if they became trivial */ - for (Instruction* phi : incomplete_phis[succ_idx]) { + for (Instruction* phi : ctx.incomplete_phis[succ_idx]) { std::vector preds = phi->definitions[0].getTemp().is_linear() ? succ.linear_preds : succ.logical_preds; for (unsigned i = 0; i < phi->operands.size(); i++) { - phi->operands[i].setTemp(read_variable(phi->operands[i].getTemp(), preds[i])); - phi->operands[i].setFixed(ctx.assignments[phi->operands[i].tempId()].first); + phi->operands[i].setTemp(read_variable(ctx, phi->operands[i].getTemp(), preds[i])); + phi->operands[i].setFixed(ctx.assignments[phi->operands[i].tempId()].reg); } - try_remove_trivial_phi(phi_map.find(phi->definitions[0].tempId())); + try_remove_trivial_phi(ctx, phi->definitions[0].getTemp()); } /* complete the original phi nodes, but no need to check triviality */ for (aco_ptr& instr : succ.instructions) { @@ -1869,14 +2404,13 @@ void register_allocation(Program *program, std::vector> live_out_ auto& operand = instr->operands[i]; if (!operand.isTemp()) continue; - operand.setTemp(read_variable(operand.getTemp(), preds[i])); - operand.setFixed(ctx.assignments[operand.tempId()].first); - std::map::iterator phi = phi_map.find(operand.getTemp().id()); - if (phi != phi_map.end()) + operand.setTemp(read_variable(ctx, operand.getTemp(), preds[i])); + operand.setFixed(ctx.assignments[operand.tempId()].reg); + std::unordered_map::iterator phi = ctx.phi_map.find(operand.getTemp().id()); + if (phi != ctx.phi_map.end()) phi->second.uses.emplace(instr.get()); } } - sealed[succ_idx] = true; } } } /* end for BB */