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::__anon9befeff40111::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 branch */
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 aco_ptr<Instruction> pc{create_instruction(aco_opcode::p_parallelcopy, Format::PSEUDO,
70 logical_phi_info.size(), logical_phi_info.size())};
71 unsigned i = 0;
72 for (auto& phi_info : logical_phi_info) {
73 pc->definitions[i] = phi_info.def;
74 pc->operands[i] = phi_info.op;
75 i++;
76 }
77 pc->pseudo().needs_scratch_reg = false;
78 auto it = std::prev(block.instructions.end());
79 block.instructions.insert(it, std::move(pc));
80 }
81
82 /* insert parallelcopies for the linear phis at the end of blocks just before the branch */
83 for (unsigned block_idx = 0; block_idx < ctx.program->blocks.size(); ++block_idx) {
84 auto& linear_phi_info = ctx.linear_phi_info[block_idx];
85 if (linear_phi_info.empty())
86 continue;
87
88 Block& block = ctx.program->blocks[block_idx];
89 Block& succ = ctx.program->blocks[block.linear_succs[0]];
90 aco_ptr<Instruction> pc{create_instruction(aco_opcode::p_parallelcopy, Format::PSEUDO,
91 linear_phi_info.size(), linear_phi_info.size())};
92 unsigned i = 0;
93 for (auto& phi_info : linear_phi_info) {
94 pc->definitions[i] = phi_info.def;
95 pc->operands[i] = phi_info.op;
96 i++;
97 }
98 pc->pseudo().scratch_sgpr = succ.instructions[0]->pseudo().scratch_sgpr;
99 pc->pseudo().needs_scratch_reg = succ.instructions[0]->pseudo().needs_scratch_reg;
100 auto it = std::prev(block.instructions.end());
101 block.instructions.insert(it, std::move(pc));
102 }
103 }
104
105 } /* end namespace */
106
107 void
ssa_elimination(Program * program)108 ssa_elimination(Program* program)
109 {
110 ssa_elimination_ctx ctx(program);
111
112 /* Collect information about every phi-instruction */
113 collect_phi_info(ctx);
114
115 /* insert parallelcopies from SSA elimination */
116 insert_parallelcopies(ctx);
117 }
118 } // namespace aco
119