1 /*
2 * Copyright © 2018 Valve Corporation
3 *
4 * SPDX-License-Identifier: MIT
5 */
6
7 #include "aco_ir.h"
8
9 #include <vector>
10
11 namespace aco {
12 namespace {
13
14 struct phi_info_item {
15 Definition def;
16 Operand op;
17 };
18
19 struct ssa_elimination_ctx {
20 /* The outer vectors should be indexed by block index. The inner vectors store phi information
21 * for each block. */
22 std::vector<std::vector<phi_info_item>> logical_phi_info;
23 std::vector<std::vector<phi_info_item>> linear_phi_info;
24 Program* program;
25
ssa_elimination_ctxaco::__anon0f1630770111::ssa_elimination_ctx26 ssa_elimination_ctx(Program* program_)
27 : logical_phi_info(program_->blocks.size()), linear_phi_info(program_->blocks.size()),
28 program(program_)
29 {}
30 };
31
32 void
collect_phi_info(ssa_elimination_ctx & ctx)33 collect_phi_info(ssa_elimination_ctx& ctx)
34 {
35 for (Block& block : ctx.program->blocks) {
36 for (aco_ptr<Instruction>& phi : block.instructions) {
37 if (phi->opcode != aco_opcode::p_phi && phi->opcode != aco_opcode::p_linear_phi)
38 break;
39
40 for (unsigned i = 0; i < phi->operands.size(); i++) {
41 if (phi->operands[i].isUndefined())
42 continue;
43 if (phi->operands[i].physReg() == phi->definitions[0].physReg())
44 continue;
45
46 assert(phi->definitions[0].size() == phi->operands[i].size());
47
48 Block::edge_vec& preds =
49 phi->opcode == aco_opcode::p_phi ? block.logical_preds : block.linear_preds;
50 uint32_t pred_idx = preds[i];
51 auto& info_vec = phi->opcode == aco_opcode::p_phi ? ctx.logical_phi_info[pred_idx]
52 : ctx.linear_phi_info[pred_idx];
53 info_vec.push_back({phi->definitions[0], phi->operands[i]});
54 }
55 }
56 }
57 }
58
59 void
insert_parallelcopies(ssa_elimination_ctx & ctx)60 insert_parallelcopies(ssa_elimination_ctx& ctx)
61 {
62 /* insert the parallelcopies from logical phis before p_logical_end */
63 for (unsigned block_idx = 0; block_idx < ctx.program->blocks.size(); ++block_idx) {
64 auto& logical_phi_info = ctx.logical_phi_info[block_idx];
65 if (logical_phi_info.empty())
66 continue;
67
68 Block& block = ctx.program->blocks[block_idx];
69 unsigned idx = block.instructions.size() - 1;
70 while (block.instructions[idx]->opcode != aco_opcode::p_logical_end) {
71 assert(idx > 0);
72 idx--;
73 }
74
75 std::vector<aco_ptr<Instruction>>::iterator it = std::next(block.instructions.begin(), idx);
76 aco_ptr<Instruction> pc{create_instruction(aco_opcode::p_parallelcopy, Format::PSEUDO,
77 logical_phi_info.size(), logical_phi_info.size())};
78 unsigned i = 0;
79 for (auto& phi_info : logical_phi_info) {
80 pc->definitions[i] = phi_info.def;
81 pc->operands[i] = phi_info.op;
82 i++;
83 }
84 pc->pseudo().needs_scratch_reg = false;
85 block.instructions.insert(it, std::move(pc));
86 }
87
88 /* insert parallelcopies for the linear phis at the end of blocks just before the branch */
89 for (unsigned block_idx = 0; block_idx < ctx.program->blocks.size(); ++block_idx) {
90 auto& linear_phi_info = ctx.linear_phi_info[block_idx];
91 if (linear_phi_info.empty())
92 continue;
93
94 Block& block = ctx.program->blocks[block_idx];
95 Block& succ = ctx.program->blocks[block.linear_succs[0]];
96 aco_ptr<Instruction> pc{create_instruction(aco_opcode::p_parallelcopy, Format::PSEUDO,
97 linear_phi_info.size(), linear_phi_info.size())};
98 unsigned i = 0;
99 for (auto& phi_info : linear_phi_info) {
100 pc->definitions[i] = phi_info.def;
101 pc->operands[i] = phi_info.op;
102 i++;
103 }
104 pc->pseudo().scratch_sgpr = succ.instructions[0]->pseudo().scratch_sgpr;
105 pc->pseudo().needs_scratch_reg = succ.instructions[0]->pseudo().needs_scratch_reg;
106 auto it = std::prev(block.instructions.end());
107 block.instructions.insert(it, std::move(pc));
108 }
109 }
110
111 } /* end namespace */
112
113 void
ssa_elimination(Program * program)114 ssa_elimination(Program* program)
115 {
116 ssa_elimination_ctx ctx(program);
117
118 /* Collect information about every phi-instruction */
119 collect_phi_info(ctx);
120
121 /* insert parallelcopies from SSA elimination */
122 insert_parallelcopies(ctx);
123 }
124 } // namespace aco
125