1/*
2 * Copyright © 2021 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 */
24
25#include "aco_builder.h"
26#include "aco_ir.h"
27
28#include <algorithm>
29#include <array>
30#include <bitset>
31#include <vector>
32
33namespace aco {
34namespace {
35
36constexpr const size_t max_reg_cnt = 512;
37constexpr const size_t max_sgpr_cnt = 128;
38constexpr const size_t min_vgpr = 256;
39constexpr const size_t max_vgpr_cnt = 256;
40
41struct Idx {
42   bool operator==(const Idx& other) const { return block == other.block && instr == other.instr; }
43   bool operator!=(const Idx& other) const { return !operator==(other); }
44
45   bool found() const { return block != UINT32_MAX; }
46
47   uint32_t block;
48   uint32_t instr;
49};
50
51Idx not_written_in_block{UINT32_MAX, 0};
52Idx clobbered{UINT32_MAX, 1};
53Idx const_or_undef{UINT32_MAX, 2};
54Idx written_by_multiple_instrs{UINT32_MAX, 3};
55
56struct pr_opt_ctx {
57   Program* program;
58   Block* current_block;
59   uint32_t current_instr_idx;
60   std::vector<uint16_t> uses;
61   std::vector<std::array<Idx, max_reg_cnt>> instr_idx_by_regs;
62
63   void reset_block(Block* block)
64   {
65      current_block = block;
66      current_instr_idx = 0;
67
68      if ((block->kind & block_kind_loop_header) || block->linear_preds.empty()) {
69         std::fill(instr_idx_by_regs[block->index].begin(), instr_idx_by_regs[block->index].end(),
70                   not_written_in_block);
71      } else {
72         const uint32_t first_linear_pred = block->linear_preds[0];
73         const std::vector<uint32_t>& linear_preds = block->linear_preds;
74
75         for (unsigned i = 0; i < max_sgpr_cnt; i++) {
76            const bool all_same = std::all_of(
77               std::next(linear_preds.begin()), linear_preds.end(),
78               [=](unsigned pred)
79               { return instr_idx_by_regs[pred][i] == instr_idx_by_regs[first_linear_pred][i]; });
80
81            if (all_same)
82               instr_idx_by_regs[block->index][i] = instr_idx_by_regs[first_linear_pred][i];
83            else
84               instr_idx_by_regs[block->index][i] = written_by_multiple_instrs;
85         }
86
87         if (!block->logical_preds.empty()) {
88            /* We assume that VGPRs are only read by blocks which have a logical predecessor,
89             * ie. any block that reads any VGPR has at least 1 logical predecessor.
90             */
91            const unsigned first_logical_pred = block->logical_preds[0];
92            const std::vector<uint32_t>& logical_preds = block->logical_preds;
93
94            for (unsigned i = min_vgpr; i < (min_vgpr + max_vgpr_cnt); i++) {
95               const bool all_same = std::all_of(
96                  std::next(logical_preds.begin()), logical_preds.end(),
97                  [=](unsigned pred) {
98                     return instr_idx_by_regs[pred][i] == instr_idx_by_regs[first_logical_pred][i];
99                  });
100
101               if (all_same)
102                  instr_idx_by_regs[block->index][i] = instr_idx_by_regs[first_logical_pred][i];
103               else
104                  instr_idx_by_regs[block->index][i] = written_by_multiple_instrs;
105            }
106         } else {
107            /* If a block has no logical predecessors, it is not part of the
108             * logical CFG and therefore it also won't have any logical successors.
109             * Such a block does not write any VGPRs ever.
110             */
111            assert(block->logical_succs.empty());
112         }
113      }
114   }
115
116   Instruction* get(Idx idx) { return program->blocks[idx.block].instructions[idx.instr].get(); }
117};
118
119void
120save_reg_writes(pr_opt_ctx& ctx, aco_ptr<Instruction>& instr)
121{
122   for (const Definition& def : instr->definitions) {
123      assert(def.regClass().type() != RegType::sgpr || def.physReg().reg() <= 255);
124      assert(def.regClass().type() != RegType::vgpr || def.physReg().reg() >= 256);
125
126      unsigned dw_size = DIV_ROUND_UP(def.bytes(), 4u);
127      unsigned r = def.physReg().reg();
128      Idx idx{ctx.current_block->index, ctx.current_instr_idx};
129
130      if (def.regClass().is_subdword())
131         idx = clobbered;
132
133      assert((r + dw_size) <= max_reg_cnt);
134      assert(def.size() == dw_size || def.regClass().is_subdword());
135      std::fill(ctx.instr_idx_by_regs[ctx.current_block->index].begin() + r,
136                ctx.instr_idx_by_regs[ctx.current_block->index].begin() + r + dw_size, idx);
137   }
138}
139
140Idx
141last_writer_idx(pr_opt_ctx& ctx, PhysReg physReg, RegClass rc)
142{
143   /* Verify that all of the operand's registers are written by the same instruction. */
144   assert(physReg.reg() < max_reg_cnt);
145   Idx instr_idx = ctx.instr_idx_by_regs[ctx.current_block->index][physReg.reg()];
146   unsigned dw_size = DIV_ROUND_UP(rc.bytes(), 4u);
147   unsigned r = physReg.reg();
148   bool all_same =
149      std::all_of(ctx.instr_idx_by_regs[ctx.current_block->index].begin() + r,
150                  ctx.instr_idx_by_regs[ctx.current_block->index].begin() + r + dw_size,
151                  [instr_idx](Idx i) { return i == instr_idx; });
152
153   return all_same ? instr_idx : written_by_multiple_instrs;
154}
155
156Idx
157last_writer_idx(pr_opt_ctx& ctx, const Operand& op)
158{
159   if (op.isConstant() || op.isUndefined())
160      return const_or_undef;
161
162   return last_writer_idx(ctx, op.physReg(), op.regClass());
163}
164
165bool
166is_clobbered_since(pr_opt_ctx& ctx, PhysReg reg, RegClass rc, const Idx& idx)
167{
168   /* If we didn't find an instruction, assume that the register is clobbered. */
169   if (!idx.found())
170      return true;
171
172   /* TODO: We currently can't keep track of subdword registers. */
173   if (rc.is_subdword())
174      return true;
175
176   unsigned begin_reg = reg.reg();
177   unsigned end_reg = begin_reg + rc.size();
178   unsigned current_block_idx = ctx.current_block->index;
179
180   for (unsigned r = begin_reg; r < end_reg; ++r) {
181      Idx& i = ctx.instr_idx_by_regs[current_block_idx][r];
182      if (i == clobbered || i == written_by_multiple_instrs)
183         return true;
184      else if (i == not_written_in_block)
185         continue;
186
187      assert(i.found());
188
189      if (i.block > idx.block || (i.block == idx.block && i.instr > idx.instr))
190         return true;
191   }
192
193   return false;
194}
195
196template <typename T>
197bool
198is_clobbered_since(pr_opt_ctx& ctx, const T& t, const Idx& idx)
199{
200   return is_clobbered_since(ctx, t.physReg(), t.regClass(), idx);
201}
202
203void
204try_apply_branch_vcc(pr_opt_ctx& ctx, aco_ptr<Instruction>& instr)
205{
206   /* We are looking for the following pattern:
207    *
208    * vcc = ...                      ; last_vcc_wr
209    * sX, scc = s_and_bXX vcc, exec  ; op0_instr
210    * (...vcc and exec must not be clobbered inbetween...)
211    * s_cbranch_XX scc               ; instr
212    *
213    * If possible, the above is optimized into:
214    *
215    * vcc = ...                      ; last_vcc_wr
216    * s_cbranch_XX vcc               ; instr modified to use vcc
217    */
218
219   /* Don't try to optimize this on GFX6-7 because SMEM may corrupt the vccz bit. */
220   if (ctx.program->gfx_level < GFX8)
221      return;
222
223   if (instr->format != Format::PSEUDO_BRANCH || instr->operands.size() == 0 ||
224       instr->operands[0].physReg() != scc)
225      return;
226
227   Idx op0_instr_idx = last_writer_idx(ctx, instr->operands[0]);
228   Idx last_vcc_wr_idx = last_writer_idx(ctx, vcc, ctx.program->lane_mask);
229
230   /* We need to make sure:
231    * - the instructions that wrote the operand register and VCC are both found
232    * - the operand register used by the branch, and VCC were both written in the current block
233    * - EXEC hasn't been clobbered since the last VCC write
234    * - VCC hasn't been clobbered since the operand register was written
235    *   (ie. the last VCC writer precedes the op0 writer)
236    */
237   if (!op0_instr_idx.found() || !last_vcc_wr_idx.found() ||
238       op0_instr_idx.block != ctx.current_block->index ||
239       last_vcc_wr_idx.block != ctx.current_block->index ||
240       is_clobbered_since(ctx, exec, ctx.program->lane_mask, last_vcc_wr_idx) ||
241       is_clobbered_since(ctx, vcc, ctx.program->lane_mask, op0_instr_idx))
242      return;
243
244   Instruction* op0_instr = ctx.get(op0_instr_idx);
245   Instruction* last_vcc_wr = ctx.get(last_vcc_wr_idx);
246
247   if ((op0_instr->opcode != aco_opcode::s_and_b64 /* wave64 */ &&
248        op0_instr->opcode != aco_opcode::s_and_b32 /* wave32 */) ||
249       op0_instr->operands[0].physReg() != vcc || op0_instr->operands[1].physReg() != exec ||
250       !last_vcc_wr->isVOPC())
251      return;
252
253   assert(last_vcc_wr->definitions[0].tempId() == op0_instr->operands[0].tempId());
254
255   /* Reduce the uses of the SCC def */
256   ctx.uses[instr->operands[0].tempId()]--;
257   /* Use VCC instead of SCC in the branch */
258   instr->operands[0] = op0_instr->operands[0];
259}
260
261void
262try_optimize_scc_nocompare(pr_opt_ctx& ctx, aco_ptr<Instruction>& instr)
263{
264   /* We are looking for the following pattern:
265    *
266    * s_bfe_u32 s0, s3, 0x40018  ; outputs SGPR and SCC if the SGPR != 0
267    * s_cmp_eq_i32 s0, 0         ; comparison between the SGPR and 0
268    * s_cbranch_scc0 BB3         ; use the result of the comparison, eg. branch or cselect
269    *
270    * If possible, the above is optimized into:
271    *
272    * s_bfe_u32 s0, s3, 0x40018  ; original instruction
273    * s_cbranch_scc1 BB3         ; modified to use SCC directly rather than the SGPR with comparison
274    *
275    */
276
277   if (!instr->isSALU() && !instr->isBranch())
278      return;
279
280   if (instr->isSOPC() &&
281       (instr->opcode == aco_opcode::s_cmp_eq_u32 || instr->opcode == aco_opcode::s_cmp_eq_i32 ||
282        instr->opcode == aco_opcode::s_cmp_lg_u32 || instr->opcode == aco_opcode::s_cmp_lg_i32 ||
283        instr->opcode == aco_opcode::s_cmp_eq_u64 || instr->opcode == aco_opcode::s_cmp_lg_u64) &&
284       (instr->operands[0].constantEquals(0) || instr->operands[1].constantEquals(0)) &&
285       (instr->operands[0].isTemp() || instr->operands[1].isTemp())) {
286      /* Make sure the constant is always in operand 1 */
287      if (instr->operands[0].isConstant())
288         std::swap(instr->operands[0], instr->operands[1]);
289
290      if (ctx.uses[instr->operands[0].tempId()] > 1)
291         return;
292
293      /* Make sure both SCC and Operand 0 are written by the same instruction. */
294      Idx wr_idx = last_writer_idx(ctx, instr->operands[0]);
295      Idx sccwr_idx = last_writer_idx(ctx, scc, s1);
296      if (!wr_idx.found() || wr_idx != sccwr_idx)
297         return;
298
299      Instruction* wr_instr = ctx.get(wr_idx);
300      if (!wr_instr->isSALU() || wr_instr->definitions.size() < 2 ||
301          wr_instr->definitions[1].physReg() != scc)
302         return;
303
304      /* Look for instructions which set SCC := (D != 0) */
305      switch (wr_instr->opcode) {
306      case aco_opcode::s_bfe_i32:
307      case aco_opcode::s_bfe_i64:
308      case aco_opcode::s_bfe_u32:
309      case aco_opcode::s_bfe_u64:
310      case aco_opcode::s_and_b32:
311      case aco_opcode::s_and_b64:
312      case aco_opcode::s_andn2_b32:
313      case aco_opcode::s_andn2_b64:
314      case aco_opcode::s_or_b32:
315      case aco_opcode::s_or_b64:
316      case aco_opcode::s_orn2_b32:
317      case aco_opcode::s_orn2_b64:
318      case aco_opcode::s_xor_b32:
319      case aco_opcode::s_xor_b64:
320      case aco_opcode::s_not_b32:
321      case aco_opcode::s_not_b64:
322      case aco_opcode::s_nor_b32:
323      case aco_opcode::s_nor_b64:
324      case aco_opcode::s_xnor_b32:
325      case aco_opcode::s_xnor_b64:
326      case aco_opcode::s_nand_b32:
327      case aco_opcode::s_nand_b64:
328      case aco_opcode::s_lshl_b32:
329      case aco_opcode::s_lshl_b64:
330      case aco_opcode::s_lshr_b32:
331      case aco_opcode::s_lshr_b64:
332      case aco_opcode::s_ashr_i32:
333      case aco_opcode::s_ashr_i64:
334      case aco_opcode::s_abs_i32:
335      case aco_opcode::s_absdiff_i32: break;
336      default: return;
337      }
338
339      /* Use the SCC def from wr_instr */
340      ctx.uses[instr->operands[0].tempId()]--;
341      instr->operands[0] = Operand(wr_instr->definitions[1].getTemp(), scc);
342      ctx.uses[instr->operands[0].tempId()]++;
343
344      /* Set the opcode and operand to 32-bit */
345      instr->operands[1] = Operand::zero();
346      instr->opcode =
347         (instr->opcode == aco_opcode::s_cmp_eq_u32 || instr->opcode == aco_opcode::s_cmp_eq_i32 ||
348          instr->opcode == aco_opcode::s_cmp_eq_u64)
349            ? aco_opcode::s_cmp_eq_u32
350            : aco_opcode::s_cmp_lg_u32;
351   } else if ((instr->format == Format::PSEUDO_BRANCH && instr->operands.size() == 1 &&
352               instr->operands[0].physReg() == scc) ||
353              instr->opcode == aco_opcode::s_cselect_b32) {
354
355      /* For cselect, operand 2 is the SCC condition */
356      unsigned scc_op_idx = 0;
357      if (instr->opcode == aco_opcode::s_cselect_b32) {
358         scc_op_idx = 2;
359      }
360
361      Idx wr_idx = last_writer_idx(ctx, instr->operands[scc_op_idx]);
362      if (!wr_idx.found())
363         return;
364
365      Instruction* wr_instr = ctx.get(wr_idx);
366
367      /* Check if we found the pattern above. */
368      if (wr_instr->opcode != aco_opcode::s_cmp_eq_u32 &&
369          wr_instr->opcode != aco_opcode::s_cmp_lg_u32)
370         return;
371      if (wr_instr->operands[0].physReg() != scc)
372         return;
373      if (!wr_instr->operands[1].constantEquals(0))
374         return;
375
376      /* The optimization can be unsafe when there are other users. */
377      if (ctx.uses[instr->operands[scc_op_idx].tempId()] > 1)
378         return;
379
380      if (wr_instr->opcode == aco_opcode::s_cmp_eq_u32) {
381         /* Flip the meaning of the instruction to correctly use the SCC. */
382         if (instr->format == Format::PSEUDO_BRANCH)
383            instr->opcode = instr->opcode == aco_opcode::p_cbranch_z ? aco_opcode::p_cbranch_nz
384                                                                     : aco_opcode::p_cbranch_z;
385         else if (instr->opcode == aco_opcode::s_cselect_b32)
386            std::swap(instr->operands[0], instr->operands[1]);
387         else
388            unreachable(
389               "scc_nocompare optimization is only implemented for p_cbranch and s_cselect");
390      }
391
392      /* Use the SCC def from the original instruction, not the comparison */
393      ctx.uses[instr->operands[scc_op_idx].tempId()]--;
394      instr->operands[scc_op_idx] = wr_instr->operands[0];
395   }
396}
397
398void
399try_combine_dpp(pr_opt_ctx& ctx, aco_ptr<Instruction>& instr)
400{
401   /* We are looking for the following pattern:
402    *
403    * v_mov_dpp vA, vB, ...      ; move instruction with DPP
404    * v_xxx vC, vA, ...          ; current instr that uses the result from the move
405    *
406    * If possible, the above is optimized into:
407    *
408    * v_xxx_dpp vC, vB, ...      ; current instr modified to use DPP directly
409    *
410    */
411
412   if (!instr->isVALU() || instr->isDPP())
413      return;
414
415   for (unsigned i = 0; i < MIN2(2, instr->operands.size()); i++) {
416      Idx op_instr_idx = last_writer_idx(ctx, instr->operands[i]);
417      if (!op_instr_idx.found())
418         continue;
419
420      const Instruction* mov = ctx.get(op_instr_idx);
421      if (mov->opcode != aco_opcode::v_mov_b32 || !mov->isDPP())
422         continue;
423      bool dpp8 = mov->isDPP8();
424      if (!can_use_DPP(instr, false, dpp8))
425         return;
426
427      /* If we aren't going to remove the v_mov_b32, we have to ensure that it doesn't overwrite
428       * it's own operand before we use it.
429       */
430      if (mov->definitions[0].physReg() == mov->operands[0].physReg() &&
431          (!mov->definitions[0].tempId() || ctx.uses[mov->definitions[0].tempId()] > 1))
432         continue;
433
434      /* Don't propagate DPP if the source register is overwritten since the move. */
435      if (is_clobbered_since(ctx, mov->operands[0], op_instr_idx))
436         continue;
437
438      if (i && !can_swap_operands(instr, &instr->opcode))
439         continue;
440
441      if (!dpp8) /* anything else doesn't make sense in SSA */
442         assert(mov->dpp16().row_mask == 0xf && mov->dpp16().bank_mask == 0xf);
443
444      if (--ctx.uses[mov->definitions[0].tempId()])
445         ctx.uses[mov->operands[0].tempId()]++;
446
447      convert_to_DPP(instr, dpp8);
448
449      if (dpp8) {
450         DPP8_instruction* dpp = &instr->dpp8();
451         if (i) {
452            std::swap(dpp->operands[0], dpp->operands[1]);
453         }
454         dpp->operands[0] = mov->operands[0];
455         memcpy(dpp->lane_sel, mov->dpp8().lane_sel, sizeof(dpp->lane_sel));
456      } else {
457         DPP16_instruction* dpp = &instr->dpp16();
458         if (i) {
459            std::swap(dpp->operands[0], dpp->operands[1]);
460            std::swap(dpp->neg[0], dpp->neg[1]);
461            std::swap(dpp->abs[0], dpp->abs[1]);
462         }
463         dpp->operands[0] = mov->operands[0];
464         dpp->dpp_ctrl = mov->dpp16().dpp_ctrl;
465         dpp->bound_ctrl = true;
466         dpp->neg[0] ^= mov->dpp16().neg[0] && !dpp->abs[0];
467         dpp->abs[0] |= mov->dpp16().abs[0];
468      }
469      return;
470   }
471}
472
473void
474process_instruction(pr_opt_ctx& ctx, aco_ptr<Instruction>& instr)
475{
476   try_apply_branch_vcc(ctx, instr);
477
478   try_optimize_scc_nocompare(ctx, instr);
479
480   try_combine_dpp(ctx, instr);
481
482   if (instr)
483      save_reg_writes(ctx, instr);
484
485   ctx.current_instr_idx++;
486}
487
488} // namespace
489
490void
491optimize_postRA(Program* program)
492{
493   pr_opt_ctx ctx;
494   ctx.program = program;
495   ctx.uses = dead_code_analysis(program);
496   ctx.instr_idx_by_regs.resize(program->blocks.size());
497
498   /* Forward pass
499    * Goes through each instruction exactly once, and can transform
500    * instructions or adjust the use counts of temps.
501    */
502   for (auto& block : program->blocks) {
503      ctx.reset_block(&block);
504
505      for (aco_ptr<Instruction>& instr : block.instructions)
506         process_instruction(ctx, instr);
507   }
508
509   /* Cleanup pass
510    * Gets rid of instructions which are manually deleted or
511    * no longer have any uses.
512    */
513   for (auto& block : program->blocks) {
514      auto new_end = std::remove_if(block.instructions.begin(), block.instructions.end(),
515                                    [&ctx](const aco_ptr<Instruction>& instr)
516                                    { return !instr || is_dead(ctx.uses, instr.get()); });
517      block.instructions.resize(new_end - block.instructions.begin());
518   }
519}
520
521} // namespace aco
522