xref: /aosp_15_r20/external/mesa3d/src/amd/compiler/aco_lower_phis.cpp (revision 6104692788411f58d303aa86923a9ff6ecaded22)
1 /*
2  * Copyright © 2019 Valve Corporation
3  *
4  * SPDX-License-Identifier: MIT
5  */
6 
7 #include "aco_builder.h"
8 #include "aco_ir.h"
9 
10 #include "util/enum_operators.h"
11 
12 #include <algorithm>
13 #include <map>
14 #include <vector>
15 
16 namespace aco {
17 
18 namespace {
19 
20 enum class pred_defined : uint8_t {
21    undef = 0,
22    const_1 = 1,
23    const_0 = 2,
24    temp = 3,
25    zero = 4, /* all disabled lanes are zero'd out */
26 };
27 MESA_DEFINE_CPP_ENUM_BITFIELD_OPERATORS(pred_defined);
28 
29 struct ssa_state {
30    unsigned loop_nest_depth;
31    RegClass rc;
32 
33    std::vector<pred_defined> any_pred_defined;
34    std::vector<bool> visited;
35    std::vector<Operand> outputs; /* the output per block */
36 };
37 
38 Operand get_output(Program* program, unsigned block_idx, ssa_state* state);
39 
40 void
init_outputs(Program * program,ssa_state * state,unsigned start,unsigned end)41 init_outputs(Program* program, ssa_state* state, unsigned start, unsigned end)
42 {
43    for (unsigned i = start; i <= end; ++i) {
44       if (state->visited[i])
45          continue;
46       state->outputs[i] = get_output(program, i, state);
47       state->visited[i] = true;
48    }
49 }
50 
51 Operand
get_output(Program * program,unsigned block_idx,ssa_state * state)52 get_output(Program* program, unsigned block_idx, ssa_state* state)
53 {
54    Block& block = program->blocks[block_idx];
55 
56    if (state->any_pred_defined[block_idx] == pred_defined::undef)
57       return Operand(state->rc);
58 
59    if (block.loop_nest_depth < state->loop_nest_depth)
60       /* loop-carried value for loop exit phis */
61       return Operand::zero(state->rc.bytes());
62 
63    size_t num_preds = block.linear_preds.size();
64 
65    if (block.loop_nest_depth > state->loop_nest_depth || num_preds == 1 ||
66        block.kind & block_kind_loop_exit)
67       return state->outputs[block.linear_preds[0]];
68 
69    Operand output;
70 
71    /* Loop headers can contain back edges, in which case the predecessor
72     * outputs aren't yet determined because the predecessor is after the block.
73     * The predecessor outputs also depend on the output of the loop header,
74     * so allocate a temporary that will store this block's output and use that
75     * to calculate the predecessor block output. In this case, we always emit a phi
76     * to ensure the allocated temporary is defined. */
77    if (block.kind & block_kind_loop_header) {
78       unsigned start_idx = block_idx + 1;
79       unsigned end_idx = block.linear_preds.back();
80 
81       state->outputs[block_idx] = Operand(Temp(program->allocateTmp(state->rc)));
82       init_outputs(program, state, start_idx, end_idx);
83       output = state->outputs[block_idx];
84    } else if (std::all_of(block.linear_preds.begin() + 1, block.linear_preds.end(),
85                           [&](unsigned pred) {
86                              return state->outputs[pred] == state->outputs[block.linear_preds[0]];
87                           })) {
88       return state->outputs[block.linear_preds[0]];
89    } else {
90       output = Operand(Temp(program->allocateTmp(state->rc)));
91    }
92 
93    /* create phi */
94    aco_ptr<Instruction> phi{
95       create_instruction(aco_opcode::p_linear_phi, Format::PSEUDO, num_preds, 1)};
96    for (unsigned i = 0; i < num_preds; i++)
97       phi->operands[i] = state->outputs[block.linear_preds[i]];
98    phi->definitions[0] = Definition(output.getTemp());
99    block.instructions.emplace(block.instructions.begin(), std::move(phi));
100 
101    assert(output.size() == state->rc.size());
102 
103    return output;
104 }
105 
106 void
insert_before_logical_end(Block * block,aco_ptr<Instruction> instr)107 insert_before_logical_end(Block* block, aco_ptr<Instruction> instr)
108 {
109    auto IsLogicalEnd = [](const aco_ptr<Instruction>& inst) -> bool
110    { return inst->opcode == aco_opcode::p_logical_end; };
111    auto it = std::find_if(block->instructions.crbegin(), block->instructions.crend(), IsLogicalEnd);
112 
113    if (it == block->instructions.crend()) {
114       assert(block->instructions.back()->isBranch());
115       block->instructions.insert(std::prev(block->instructions.end()), std::move(instr));
116    } else {
117       block->instructions.insert(std::prev(it.base()), std::move(instr));
118    }
119 }
120 
121 void
build_merge_code(Program * program,ssa_state * state,Block * block,Operand cur)122 build_merge_code(Program* program, ssa_state* state, Block* block, Operand cur)
123 {
124    unsigned block_idx = block->index;
125    Definition dst = Definition(state->outputs[block_idx].getTemp());
126    Operand prev = get_output(program, block_idx, state);
127    if (cur.isUndefined())
128       return;
129 
130    Builder bld(program);
131    auto IsLogicalEnd = [](const aco_ptr<Instruction>& instr) -> bool
132    { return instr->opcode == aco_opcode::p_logical_end; };
133    auto it = std::find_if(block->instructions.rbegin(), block->instructions.rend(), IsLogicalEnd);
134    assert(it != block->instructions.rend());
135    bld.reset(&block->instructions, std::prev(it.base()));
136 
137    pred_defined defined = state->any_pred_defined[block_idx];
138    if (defined == pred_defined::undef) {
139       return;
140    } else if (defined == pred_defined::const_0) {
141       bld.sop2(Builder::s_and, dst, bld.def(s1, scc), cur, Operand(exec, bld.lm));
142       return;
143    } else if (defined == pred_defined::const_1) {
144       bld.sop2(Builder::s_orn2, dst, bld.def(s1, scc), cur, Operand(exec, bld.lm));
145       return;
146    }
147 
148    assert(prev.isTemp());
149    /* simpler sequence in case prev has only zeros in disabled lanes */
150    if ((defined & pred_defined::zero) == pred_defined::zero) {
151       if (cur.isConstant()) {
152          if (!cur.constantValue()) {
153             bld.copy(dst, prev);
154             return;
155          }
156          cur = Operand(exec, bld.lm);
157       } else {
158          cur =
159             bld.sop2(Builder::s_and, bld.def(bld.lm), bld.def(s1, scc), cur, Operand(exec, bld.lm));
160       }
161       bld.sop2(Builder::s_or, dst, bld.def(s1, scc), prev, cur);
162       return;
163    }
164 
165    if (cur.isConstant()) {
166       if (cur.constantValue())
167          bld.sop2(Builder::s_or, dst, bld.def(s1, scc), prev, Operand(exec, bld.lm));
168       else
169          bld.sop2(Builder::s_andn2, dst, bld.def(s1, scc), prev, Operand(exec, bld.lm));
170       return;
171    }
172    prev =
173       bld.sop2(Builder::s_andn2, bld.def(bld.lm), bld.def(s1, scc), prev, Operand(exec, bld.lm));
174    cur = bld.sop2(Builder::s_and, bld.def(bld.lm), bld.def(s1, scc), cur, Operand(exec, bld.lm));
175    bld.sop2(Builder::s_or, dst, bld.def(s1, scc), prev, cur);
176    return;
177 }
178 
179 void
build_const_else_merge_code(Program * program,Block & invert_block,aco_ptr<Instruction> & phi)180 build_const_else_merge_code(Program* program, Block& invert_block, aco_ptr<Instruction>& phi)
181 {
182    /* When the else-side operand of a binary merge phi is constant,
183     * we can use a simpler way to lower the phi by emitting some
184     * instructions to the invert block instead.
185     * This allows us to actually delete the else block when it's empty.
186     */
187    assert(invert_block.kind & block_kind_invert);
188    Builder bld(program);
189    Operand then = phi->operands[0];
190    const Operand els = phi->operands[1];
191 
192    /* Only -1 (all lanes true) and 0 (all lanes false) constants are supported here. */
193    assert(!then.isConstant() || then.constantEquals(0) || then.constantEquals(-1));
194    assert(els.constantEquals(0) || els.constantEquals(-1));
195 
196    if (!then.isConstant()) {
197       /* Left-hand operand is not constant, so we need to emit a phi to access it. */
198       bld.reset(&invert_block.instructions, invert_block.instructions.begin());
199       then = bld.pseudo(aco_opcode::p_linear_phi, bld.def(bld.lm), then, Operand(bld.lm));
200    }
201 
202    auto after_phis =
203       std::find_if(invert_block.instructions.begin(), invert_block.instructions.end(),
204                    [](const aco_ptr<Instruction>& instr) -> bool { return !is_phi(instr.get()); });
205    bld.reset(&invert_block.instructions, after_phis);
206 
207    Temp tmp;
208    if (then.constantEquals(-1) && els.constantEquals(0)) {
209       tmp = bld.copy(bld.def(bld.lm), Operand(exec, bld.lm));
210    } else {
211       Builder::WaveSpecificOpcode opc = els.constantEquals(0) ? Builder::s_and : Builder::s_orn2;
212       tmp = bld.sop2(opc, bld.def(bld.lm), bld.def(s1, scc), then, Operand(exec, bld.lm));
213    }
214 
215    /* We can't delete the original phi because that'd invalidate the iterator in lower_phis,
216     * so just make it a trivial phi instead.
217     */
218    phi->opcode = aco_opcode::p_linear_phi;
219    phi->operands[0] = Operand(tmp);
220    phi->operands[1] = Operand(tmp);
221 }
222 
223 void
init_state(Program * program,Block * block,ssa_state * state,aco_ptr<Instruction> & phi)224 init_state(Program* program, Block* block, ssa_state* state, aco_ptr<Instruction>& phi)
225 {
226    Builder bld(program);
227 
228    /* do this here to avoid resizing in case of no boolean phis */
229    state->rc = phi->definitions[0].regClass();
230    state->visited.resize(program->blocks.size());
231    state->outputs.resize(program->blocks.size());
232    state->any_pred_defined.resize(program->blocks.size());
233    state->loop_nest_depth = block->loop_nest_depth;
234    if (block->kind & block_kind_loop_exit)
235       state->loop_nest_depth += 1;
236    std::fill(state->visited.begin(), state->visited.end(), false);
237    std::fill(state->any_pred_defined.begin(), state->any_pred_defined.end(), pred_defined::undef);
238 
239    for (unsigned i = 0; i < block->logical_preds.size(); i++) {
240       if (phi->operands[i].isUndefined())
241          continue;
242       pred_defined defined = pred_defined::temp;
243       if (phi->operands[i].isConstant() && phi->opcode == aco_opcode::p_boolean_phi)
244          defined = phi->operands[i].constantValue() ? pred_defined::const_1 : pred_defined::const_0;
245       for (unsigned succ : program->blocks[block->logical_preds[i]].linear_succs)
246          state->any_pred_defined[succ] |= defined;
247    }
248 
249    unsigned start = block->logical_preds[0];
250    unsigned end = block->linear_preds.back();
251 
252    /* The value might not be loop-invariant if the loop has a divergent break and
253     *  - this is a boolean phi, which must be combined with logical exits from previous iterations
254     *  - or the loop also has an additional linear exit (continue_or_break), which might be taken in
255     *    a different iteration than the logical exit
256     */
257    bool continue_or_break = block->linear_preds.size() > block->logical_preds.size();
258    bool has_divergent_break = std::any_of(
259       block->logical_preds.begin(), block->logical_preds.end(),
260       [&](unsigned pred) { return !(program->blocks[pred].kind & block_kind_uniform); });
261    if (block->kind & block_kind_loop_exit && has_divergent_break &&
262        (phi->opcode == aco_opcode::p_boolean_phi || continue_or_break)) {
263       /* Start at the loop pre-header as we need the value from previous iterations. */
264       while (program->blocks[start].loop_nest_depth >= state->loop_nest_depth)
265          start--;
266       end = block->index - 1;
267       /* If the loop-header has a back-edge, we need to insert a phi.
268        * This will contain a defined value */
269       if (program->blocks[start + 1].linear_preds.size() > 1) {
270          if (phi->opcode == aco_opcode::p_boolean_phi) {
271             state->any_pred_defined[start + 1] = pred_defined::temp | pred_defined::zero;
272             /* add dominating zero: this allows to emit simpler merge sequences
273              * if we can ensure that all disabled lanes are always zero on incoming values
274              */
275             state->any_pred_defined[start] = pred_defined::const_0;
276          } else {
277             state->any_pred_defined[start + 1] = pred_defined::temp;
278          }
279       }
280    }
281 
282    /* For loop header phis, don't propagate the incoming value */
283    if (block->kind & block_kind_loop_header) {
284       state->any_pred_defined[block->index] = pred_defined::undef;
285    }
286 
287    for (unsigned j = start; j <= end; j++) {
288       if (state->any_pred_defined[j] == pred_defined::undef)
289          continue;
290       for (unsigned succ : program->blocks[j].linear_succs)
291          state->any_pred_defined[succ] |= state->any_pred_defined[j];
292    }
293 
294    state->any_pred_defined[block->index] = pred_defined::undef;
295 
296    for (unsigned i = 0; i < phi->operands.size(); i++) {
297       /* If the Operand is undefined, just propagate the previous value. */
298       if (phi->operands[i].isUndefined())
299          continue;
300 
301       unsigned pred = block->logical_preds[i];
302       if (phi->opcode == aco_opcode::p_boolean_phi &&
303           state->any_pred_defined[pred] != pred_defined::undef) {
304          /* Needs merge code sequence. */
305          state->outputs[pred] = Operand(bld.tmp(state->rc));
306       } else {
307          state->outputs[pred] = phi->operands[i];
308       }
309       assert(state->outputs[pred].size() == state->rc.size());
310       state->visited[pred] = true;
311    }
312 
313    init_outputs(program, state, start, end);
314 }
315 
316 void
lower_phi_to_linear(Program * program,ssa_state * state,Block * block,aco_ptr<Instruction> & phi)317 lower_phi_to_linear(Program* program, ssa_state* state, Block* block, aco_ptr<Instruction>& phi)
318 {
319    if (block->linear_preds == block->logical_preds) {
320       phi->opcode = aco_opcode::p_linear_phi;
321       return;
322    }
323 
324    if ((block->kind & block_kind_merge) && phi->opcode == aco_opcode::p_boolean_phi &&
325        phi->operands.size() == 2 && phi->operands[1].isConstant()) {
326       build_const_else_merge_code(program, program->blocks[block->linear_idom], phi);
327       return;
328    }
329 
330    init_state(program, block, state, phi);
331 
332    if (phi->opcode == aco_opcode::p_boolean_phi) {
333       /* Divergent boolean phis are lowered to logical arithmetic and linear phis. */
334       for (unsigned i = 0; i < phi->operands.size(); i++)
335          build_merge_code(program, state, &program->blocks[block->logical_preds[i]],
336                           phi->operands[i]);
337    }
338 
339    unsigned num_preds = block->linear_preds.size();
340    if (phi->operands.size() != num_preds) {
341       Instruction* new_phi{
342          create_instruction(aco_opcode::p_linear_phi, Format::PSEUDO, num_preds, 1)};
343       new_phi->definitions[0] = phi->definitions[0];
344       phi.reset(new_phi);
345    } else {
346       phi->opcode = aco_opcode::p_linear_phi;
347    }
348    assert(phi->operands.size() == num_preds);
349 
350    for (unsigned i = 0; i < num_preds; i++)
351       phi->operands[i] = state->outputs[block->linear_preds[i]];
352 
353    return;
354 }
355 
356 void
lower_subdword_phis(Program * program,Block * block,aco_ptr<Instruction> & phi)357 lower_subdword_phis(Program* program, Block* block, aco_ptr<Instruction>& phi)
358 {
359    Builder bld(program);
360    for (unsigned i = 0; i < phi->operands.size(); i++) {
361       if (phi->operands[i].isUndefined())
362          continue;
363       if (phi->operands[i].regClass() == phi->definitions[0].regClass())
364          continue;
365 
366       assert(phi->operands[i].isTemp());
367       Block* pred = &program->blocks[block->logical_preds[i]];
368       Temp phi_src = phi->operands[i].getTemp();
369 
370       assert(phi_src.regClass().type() == RegType::sgpr);
371       Temp tmp = bld.tmp(RegClass(RegType::vgpr, phi_src.size()));
372       insert_before_logical_end(pred, bld.copy(Definition(tmp), phi_src).get_ptr());
373       Temp new_phi_src = bld.tmp(phi->definitions[0].regClass());
374       insert_before_logical_end(pred, bld.pseudo(aco_opcode::p_extract_vector,
375                                                  Definition(new_phi_src), tmp, Operand::zero())
376                                          .get_ptr());
377 
378       phi->operands[i].setTemp(new_phi_src);
379    }
380    return;
381 }
382 
383 } /* end namespace */
384 
385 void
lower_phis(Program * program)386 lower_phis(Program* program)
387 {
388    ssa_state state;
389 
390    for (Block& block : program->blocks) {
391       for (aco_ptr<Instruction>& phi : block.instructions) {
392          if (phi->opcode == aco_opcode::p_boolean_phi) {
393             assert(program->wave_size == 64 ? phi->definitions[0].regClass() == s2
394                                             : phi->definitions[0].regClass() == s1);
395             lower_phi_to_linear(program, &state, &block, phi);
396          } else if (phi->opcode == aco_opcode::p_phi) {
397             if (phi->definitions[0].regClass().type() == RegType::sgpr)
398                lower_phi_to_linear(program, &state, &block, phi);
399             else if (phi->definitions[0].regClass().is_subdword())
400                lower_subdword_phis(program, &block, phi);
401          } else if (!is_phi(phi)) {
402             break;
403          }
404       }
405    }
406 }
407 
408 } // namespace aco
409