| /* |
| * Copyright © 2019 Valve Corporation |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the next |
| * paragraph) shall be included in all copies or substantial portions of the |
| * Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
| * IN THE SOFTWARE. |
| * |
| */ |
| |
| #include <map> |
| #include "aco_ir.h" |
| #include "aco_builder.h" |
| |
| /* |
| * Implements an algorithm to lower to Concentional SSA Form (CSSA). |
| * After "Revisiting Out-of-SSA Translation for Correctness, CodeQuality, and Efficiency" |
| * by B. Boissinot, A. Darte, F. Rastello, B. Dupont de Dinechin, C. Guillon, |
| * |
| * By lowering the IR to CSSA, the insertion of parallelcopies is separated from |
| * the register coalescing problem. Additionally, correctness is ensured w.r.t. spilling. |
| * The algorithm tries to find beneficial insertion points by checking if a basic block |
| * is empty and if the variable already has a new definition in a dominating block. |
| */ |
| |
| |
| namespace aco { |
| namespace { |
| |
| typedef std::map<uint32_t, std::vector<std::pair<Definition, Operand>>> phi_info; |
| |
| struct cssa_ctx { |
| Program* program; |
| live& live_vars; |
| phi_info logical_phi_info; |
| phi_info linear_phi_info; |
| |
| cssa_ctx(Program* program, live& live_vars) : program(program), live_vars(live_vars) {} |
| }; |
| |
| bool collect_phi_info(cssa_ctx& ctx) |
| { |
| bool progress = false; |
| for (Block& block : ctx.program->blocks) { |
| for (aco_ptr<Instruction>& phi : block.instructions) { |
| bool is_logical; |
| if (phi->opcode == aco_opcode::p_phi) |
| is_logical = true; |
| else if (phi->opcode == aco_opcode::p_linear_phi) |
| is_logical = false; |
| else |
| break; |
| |
| /* no CSSA for the exec mask as we don't spill it anyway */ |
| if (phi->definitions[0].isFixed() && phi->definitions[0].physReg() == exec) |
| continue; |
| std::vector<unsigned>& preds = is_logical ? block.logical_preds : block.linear_preds; |
| |
| /* collect definition's block per Operand */ |
| std::vector<unsigned> def_points(phi->operands.size()); |
| for (unsigned i = 0; i < phi->operands.size(); i++) { |
| Operand& op = phi->operands[i]; |
| if (op.isUndefined()) { |
| def_points[i] = preds[i]; |
| } else if (op.isConstant()) { |
| /* in theory, we could insert the definition there... */ |
| def_points[i] = 0; |
| } else { |
| assert(op.isTemp()); |
| unsigned pred = preds[i]; |
| do { |
| def_points[i] = pred; |
| pred = is_logical ? |
| ctx.program->blocks[pred].logical_idom : |
| ctx.program->blocks[pred].linear_idom; |
| } while (def_points[i] != pred && |
| ctx.live_vars.live_out[pred].find(op.getTemp()) != ctx.live_vars.live_out[pred].end()); |
| } |
| } |
| |
| /* check live-range intersections */ |
| for (unsigned i = 0; i < phi->operands.size(); i++) { |
| Operand op = phi->operands[i]; |
| if (op.isUndefined()) |
| continue; |
| /* check if the operand comes from the exec mask of a predecessor */ |
| if (op.isTemp() && op.getTemp() == ctx.program->blocks[preds[i]].live_out_exec) |
| op.setFixed(exec); |
| |
| bool interferes = false; |
| unsigned idom = is_logical ? |
| ctx.program->blocks[def_points[i]].logical_idom : |
| ctx.program->blocks[def_points[i]].linear_idom; |
| /* live-through operands definitely interfere */ |
| if (op.isTemp() && !op.isKill()) { |
| interferes = true; |
| /* create copies for constants to ease spilling */ |
| } else if (op.isConstant()) { |
| interferes = true; |
| /* create copies for SGPR -> VGPR moves */ |
| } else if (op.regClass() != phi->definitions[0].regClass()) { |
| interferes = true; |
| /* operand might interfere with any phi-def*/ |
| } else if (def_points[i] == block.index) { |
| interferes = true; |
| /* operand might interfere with phi-def */ |
| } else if (ctx.live_vars.live_out[idom].count(phi->definitions[0].getTemp())) { |
| interferes = true; |
| /* else check for interferences with other operands */ |
| } else { |
| for (unsigned j = 0; !interferes && j < phi->operands.size(); j++) { |
| /* don't care about other register classes */ |
| if (!phi->operands[j].isTemp() || phi->operands[j].regClass() != phi->definitions[0].regClass()) |
| continue; |
| /* same operands cannot interfere */ |
| if (op.getTemp() == phi->operands[j].getTemp()) |
| continue; |
| /* if def_points[i] dominates any other def_point, assume they interfere. |
| * As live-through operands are checked above, only test up the current block. */ |
| unsigned other_def_point = def_points[j]; |
| while (def_points[i] < other_def_point && other_def_point != block.index) |
| other_def_point = is_logical ? |
| ctx.program->blocks[other_def_point].logical_idom : |
| ctx.program->blocks[other_def_point].linear_idom; |
| interferes = def_points[i] == other_def_point; |
| } |
| } |
| |
| if (!interferes) |
| continue; |
| |
| progress = true; |
| |
| /* create new temporary and rename operands */ |
| Temp new_tmp = Temp{ctx.program->allocateId(), phi->definitions[0].regClass()}; |
| if (is_logical) |
| ctx.logical_phi_info[preds[i]].emplace_back(Definition(new_tmp), op); |
| else |
| ctx.linear_phi_info[preds[i]].emplace_back(Definition(new_tmp), op); |
| phi->operands[i] = Operand(new_tmp); |
| phi->operands[i].setKill(true); |
| def_points[i] = preds[i]; |
| } |
| } |
| } |
| return progress; |
| } |
| |
| void insert_parallelcopies(cssa_ctx& ctx) |
| { |
| /* insert the parallelcopies from logical phis before p_logical_end */ |
| for (auto&& entry : ctx.logical_phi_info) { |
| Block& block = ctx.program->blocks[entry.first]; |
| unsigned idx = block.instructions.size() - 1; |
| while (block.instructions[idx]->opcode != aco_opcode::p_logical_end) { |
| assert(idx > 0); |
| idx--; |
| } |
| |
| Builder bld(ctx.program); |
| bld.reset(&block.instructions, std::next(block.instructions.begin(), idx)); |
| for (std::pair<Definition, Operand>& pair : entry.second) |
| bld.pseudo(aco_opcode::p_parallelcopy, pair.first, pair.second); |
| } |
| |
| /* insert parallelcopies for the linear phis at the end of blocks just before the branch */ |
| for (auto&& entry : ctx.linear_phi_info) { |
| Block& block = ctx.program->blocks[entry.first]; |
| std::vector<aco_ptr<Instruction>>::iterator it = block.instructions.end(); |
| --it; |
| assert((*it)->format == Format::PSEUDO_BRANCH); |
| |
| Builder bld(ctx.program); |
| bld.reset(&block.instructions, it); |
| for (std::pair<Definition, Operand>& pair : entry.second) |
| bld.pseudo(aco_opcode::p_parallelcopy, pair.first, pair.second); |
| } |
| } |
| |
| } /* end namespace */ |
| |
| |
| void lower_to_cssa(Program* program, live& live_vars, const struct radv_nir_compiler_options *options) |
| { |
| cssa_ctx ctx = {program, live_vars}; |
| /* collect information about all interfering phi operands */ |
| bool progress = collect_phi_info(ctx); |
| |
| if (!progress) |
| return; |
| |
| insert_parallelcopies(ctx); |
| |
| /* update live variable information */ |
| live_vars = live_var_analysis(program, options); |
| } |
| } |
| |
