1 /*
2 * Copyright © 2019 Valve Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 *
23 * Authors:
24 * Rhys Perry (pendingchaos02@gmail.com)
25 *
26 */
27
28 #include <map>
29
30 #include "aco_ir.h"
31 #include "aco_builder.h"
32 #include <algorithm>
33
34
35 namespace aco {
36
37 struct ssa_state {
38 bool checked_preds_for_uniform;
39 bool all_preds_uniform;
40
41 bool needs_init;
42 uint64_t cur_undef_operands;
43
44 unsigned phi_block_idx;
45 unsigned loop_nest_depth;
46 std::map<unsigned, unsigned> writes;
47 std::vector<Operand> latest;
48 std::vector<bool> visited;
49 };
50
get_ssa(Program * program,unsigned block_idx,ssa_state * state,bool before_write)51 Operand get_ssa(Program *program, unsigned block_idx, ssa_state *state, bool before_write)
52 {
53 if (!before_write) {
54 auto it = state->writes.find(block_idx);
55 if (it != state->writes.end())
56 return Operand(Temp(it->second, program->lane_mask));
57 if (state->visited[block_idx])
58 return state->latest[block_idx];
59 }
60
61 state->visited[block_idx] = true;
62
63 Block& block = program->blocks[block_idx];
64 size_t pred = block.linear_preds.size();
65 if (pred == 0 || block.loop_nest_depth < state->loop_nest_depth) {
66 return Operand(program->lane_mask);
67 } else if (block.loop_nest_depth > state->loop_nest_depth) {
68 Operand op = get_ssa(program, block_idx - 1, state, false);
69 state->latest[block_idx] = op;
70 return op;
71 } else if (pred == 1 || block.kind & block_kind_loop_exit) {
72 Operand op = get_ssa(program, block.linear_preds[0], state, false);
73 state->latest[block_idx] = op;
74 return op;
75 } else if (block.kind & block_kind_loop_header &&
76 !(program->blocks[state->phi_block_idx].kind & block_kind_loop_exit)) {
77 return Operand(program->lane_mask);
78 } else {
79 Temp res = Temp(program->allocateTmp(program->lane_mask));
80 state->latest[block_idx] = Operand(res);
81
82 Operand *const ops = (Operand *)alloca(pred * sizeof(Operand));
83 for (unsigned i = 0; i < pred; i++)
84 ops[i] = get_ssa(program, block.linear_preds[i], state, false);
85
86 bool all_undef = true;
87 for (unsigned i = 0; i < pred; i++)
88 all_undef = all_undef && ops[i].isUndefined();
89 if (all_undef) {
90 state->latest[block_idx] = ops[0];
91 return ops[0];
92 }
93
94 aco_ptr<Pseudo_instruction> phi{create_instruction<Pseudo_instruction>(aco_opcode::p_linear_phi, Format::PSEUDO, pred, 1)};
95 for (unsigned i = 0; i < pred; i++)
96 phi->operands[i] = ops[i];
97 phi->definitions[0] = Definition(res);
98 block.instructions.emplace(block.instructions.begin(), std::move(phi));
99
100 return Operand(res);
101 }
102 }
103
insert_before_logical_end(Block * block,aco_ptr<Instruction> instr)104 void insert_before_logical_end(Block *block, aco_ptr<Instruction> instr)
105 {
106 auto IsLogicalEnd = [] (const aco_ptr<Instruction>& instr) -> bool {
107 return instr->opcode == aco_opcode::p_logical_end;
108 };
109 auto it = std::find_if(block->instructions.crbegin(), block->instructions.crend(), IsLogicalEnd);
110
111 if (it == block->instructions.crend()) {
112 assert(block->instructions.back()->format == Format::PSEUDO_BRANCH);
113 block->instructions.insert(std::prev(block->instructions.end()), std::move(instr));
114 } else {
115 block->instructions.insert(std::prev(it.base()), std::move(instr));
116 }
117 }
118
build_merge_code(Program * program,Block * block,Definition dst,Operand prev,Operand cur)119 void build_merge_code(Program *program, Block *block, Definition dst, Operand prev, Operand cur)
120 {
121 Builder bld(program);
122
123 auto IsLogicalEnd = [] (const aco_ptr<Instruction>& instr) -> bool {
124 return instr->opcode == aco_opcode::p_logical_end;
125 };
126 auto it = std::find_if(block->instructions.rbegin(), block->instructions.rend(), IsLogicalEnd);
127 assert(it != block->instructions.rend());
128 bld.reset(&block->instructions, std::prev(it.base()));
129
130 if (prev.isUndefined()) {
131 bld.copy(dst, cur);
132 return;
133 }
134
135 bool prev_is_constant = prev.isConstant() && prev.constantValue64(true) + 1u < 2u;
136 bool cur_is_constant = cur.isConstant() && cur.constantValue64(true) + 1u < 2u;
137
138 if (!prev_is_constant) {
139 if (!cur_is_constant) {
140 Temp tmp1 = bld.tmp(bld.lm), tmp2 = bld.tmp(bld.lm);
141 bld.sop2(Builder::s_andn2, Definition(tmp1), bld.def(s1, scc), prev, Operand(exec, bld.lm));
142 bld.sop2(Builder::s_and, Definition(tmp2), bld.def(s1, scc), cur, Operand(exec, bld.lm));
143 bld.sop2(Builder::s_or, dst, bld.def(s1, scc), tmp1, tmp2);
144 } else if (cur.constantValue64(true)) {
145 bld.sop2(Builder::s_or, dst, bld.def(s1, scc), prev, Operand(exec, bld.lm));
146 } else {
147 bld.sop2(Builder::s_andn2, dst, bld.def(s1, scc), prev, Operand(exec, bld.lm));
148 }
149 } else if (prev.constantValue64(true)) {
150 if (!cur_is_constant)
151 bld.sop2(Builder::s_orn2, dst, bld.def(s1, scc), cur, Operand(exec, bld.lm));
152 else if (cur.constantValue64(true))
153 bld.copy(dst, Operand(UINT32_MAX, bld.lm == s2));
154 else
155 bld.sop1(Builder::s_not, dst, bld.def(s1, scc), Operand(exec, bld.lm));
156 } else {
157 if (!cur_is_constant)
158 bld.sop2(Builder::s_and, dst, bld.def(s1, scc), cur, Operand(exec, bld.lm));
159 else if (cur.constantValue64(true))
160 bld.copy(dst, Operand(exec, bld.lm));
161 else
162 bld.copy(dst, Operand(0u, bld.lm == s2));
163 }
164 }
165
lower_divergent_bool_phi(Program * program,ssa_state * state,Block * block,aco_ptr<Instruction> & phi)166 void lower_divergent_bool_phi(Program *program, ssa_state *state, Block *block, aco_ptr<Instruction>& phi)
167 {
168 Builder bld(program);
169
170 if (!state->checked_preds_for_uniform) {
171 state->all_preds_uniform = !(block->kind & block_kind_merge);
172 for (unsigned pred : block->logical_preds)
173 state->all_preds_uniform = state->all_preds_uniform && (program->blocks[pred].kind & block_kind_uniform);
174 state->checked_preds_for_uniform = true;
175 }
176
177 if (state->all_preds_uniform) {
178 assert(block->logical_preds.size() == block->linear_preds.size());
179 phi->opcode = aco_opcode::p_linear_phi;
180 return;
181 }
182
183 state->latest.resize(program->blocks.size());
184 state->visited.resize(program->blocks.size());
185
186 uint64_t undef_operands = 0;
187 for (unsigned i = 0; i < phi->operands.size(); i++)
188 undef_operands |= phi->operands[i].isUndefined() << i;
189
190 if (state->needs_init || undef_operands != state->cur_undef_operands ||
191 block->logical_preds.size() > 64) {
192 /* this only has to be done once per block unless the set of predecessors
193 * which are undefined changes */
194 state->cur_undef_operands = undef_operands;
195 state->phi_block_idx = block->index;
196 state->loop_nest_depth = block->loop_nest_depth;
197 if (block->kind & block_kind_loop_exit) {
198 state->loop_nest_depth += 1;
199 }
200 state->writes.clear();
201 state->needs_init = false;
202 }
203 std::fill(state->latest.begin(), state->latest.end(), Operand(program->lane_mask));
204 std::fill(state->visited.begin(), state->visited.end(), false);
205
206 for (unsigned i = 0; i < phi->operands.size(); i++) {
207 if (phi->operands[i].isUndefined())
208 continue;
209
210 state->writes[block->logical_preds[i]] = program->allocateId(program->lane_mask);
211 }
212
213 bool uniform_merge = block->kind & block_kind_loop_header;
214
215 for (unsigned i = 0; i < phi->operands.size(); i++) {
216 Block *pred = &program->blocks[block->logical_preds[i]];
217
218 bool need_get_ssa = !uniform_merge;
219 if (block->kind & block_kind_loop_header && !(pred->kind & block_kind_uniform))
220 uniform_merge = false;
221
222 if (phi->operands[i].isUndefined())
223 continue;
224
225 Operand cur(bld.lm);
226 if (need_get_ssa)
227 cur = get_ssa(program, pred->index, state, true);
228 assert(cur.regClass() == bld.lm);
229
230 Temp new_cur = {state->writes.at(pred->index), program->lane_mask};
231 assert(new_cur.regClass() == bld.lm);
232
233 if (i == 1 && (block->kind & block_kind_merge) && phi->operands[0].isConstant())
234 cur = phi->operands[0];
235 build_merge_code(program, pred, Definition(new_cur), cur, phi->operands[i]);
236 }
237
238 unsigned num_preds = block->linear_preds.size();
239 if (phi->operands.size() != num_preds) {
240 Pseudo_instruction* new_phi{create_instruction<Pseudo_instruction>(aco_opcode::p_linear_phi, Format::PSEUDO, num_preds, 1)};
241 new_phi->definitions[0] = phi->definitions[0];
242 phi.reset(new_phi);
243 } else {
244 phi->opcode = aco_opcode::p_linear_phi;
245 }
246 assert(phi->operands.size() == num_preds);
247
248 for (unsigned i = 0; i < num_preds; i++)
249 phi->operands[i] = get_ssa(program, block->linear_preds[i], state, false);
250
251 return;
252 }
253
lower_subdword_phis(Program * program,Block * block,aco_ptr<Instruction> & phi)254 void lower_subdword_phis(Program *program, Block *block, aco_ptr<Instruction>& phi)
255 {
256 Builder bld(program);
257 for (unsigned i = 0; i < phi->operands.size(); i++) {
258 if (phi->operands[i].isUndefined())
259 continue;
260 if (phi->operands[i].regClass() == phi->definitions[0].regClass())
261 continue;
262
263 assert(phi->operands[i].isTemp());
264 Block *pred = &program->blocks[block->logical_preds[i]];
265 Temp phi_src = phi->operands[i].getTemp();
266
267 assert(phi_src.regClass().type() == RegType::sgpr);
268 Temp tmp = bld.tmp(RegClass(RegType::vgpr, phi_src.size()));
269 insert_before_logical_end(pred, bld.copy(Definition(tmp), phi_src).get_ptr());
270 Temp new_phi_src = bld.tmp(phi->definitions[0].regClass());
271 insert_before_logical_end(pred, bld.pseudo(aco_opcode::p_extract_vector, Definition(new_phi_src), tmp, Operand(0u)).get_ptr());
272
273 phi->operands[i].setTemp(new_phi_src);
274 }
275 return;
276 }
277
lower_phis(Program * program)278 void lower_phis(Program* program)
279 {
280 ssa_state state;
281
282 for (Block& block : program->blocks) {
283 state.checked_preds_for_uniform = false;
284 state.needs_init = true;
285 for (aco_ptr<Instruction>& phi : block.instructions) {
286 if (phi->opcode == aco_opcode::p_phi) {
287 assert(program->wave_size == 64 ? phi->definitions[0].regClass() != s1 : phi->definitions[0].regClass() != s2);
288 if (phi->definitions[0].regClass() == program->lane_mask)
289 lower_divergent_bool_phi(program, &state, &block, phi);
290 else if (phi->definitions[0].regClass().is_subdword())
291 lower_subdword_phis(program, &block, phi);
292 } else if (!is_phi(phi)) {
293 break;
294 }
295 }
296 }
297 }
298
299 }
300