src/amd/compiler/aco_lower_phis.cpp

   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 phi_use {
  38    Block *block;
  39    unsigned phi_def;
  40
  41    bool operator<(const phi_use& other) const {
  42       return std::make_tuple(block, phi_def) <
  43              std::make_tuple(other.block, other.phi_def);
  44    }
  45 };
  46
  47 struct ssa_state {
  48    std::map<unsigned, unsigned> latest;
  49    std::map<unsigned, std::map<phi_use, uint64_t>> phis;
  50 };
  51
  52 Operand get_ssa(Program *program, unsigned block_idx, ssa_state *state)
  53 {
  54    while (true) {
  55       auto pos = state->latest.find(block_idx);
  56       if (pos != state->latest.end())
  57          return Operand(Temp(pos->second, program->lane_mask));
  58
  59       Block& block = program->blocks[block_idx];
  60       size_t pred = block.linear_preds.size();
  61       if (pred == 0) {
  62          return Operand(program->lane_mask);
  63       } else if (pred == 1) {
  64          block_idx = block.linear_preds[0];
  65          continue;
  66       } else {
  67          unsigned res = program->allocateId();
  68          state->latest[block_idx] = res;
  69
  70          aco_ptr<Pseudo_instruction> phi{create_instruction<Pseudo_instruction>(aco_opcode::p_linear_phi, Format::PSEUDO, pred, 1)};
  71          for (unsigned i = 0; i < pred; i++) {
  72             phi->operands[i] = get_ssa(program, block.linear_preds[i], state);
  73             if (phi->operands[i].isTemp()) {
  74                assert(i < 64);
  75                state->phis[phi->operands[i].tempId()][(phi_use){&block, res}] |= (uint64_t)1 << i;
  76             }
  77          }
  78          phi->definitions[0] = Definition(Temp{res, program->lane_mask});
  79          block.instructions.emplace(block.instructions.begin(), std::move(phi));
  80
  81          return Operand(Temp(res, program->lane_mask));
  82       }
  83    }
  84 }
  85
  86 void update_phi(Program *program, ssa_state *state, Block *block, unsigned phi_def, uint64_t operand_mask) {
  87    for (auto& phi : block->instructions) {
  88       if (phi->opcode != aco_opcode::p_phi && phi->opcode != aco_opcode::p_linear_phi)
  89          break;
  90       if (phi->opcode != aco_opcode::p_linear_phi)
  91          continue;
  92       if (phi->definitions[0].tempId() != phi_def)
  93          continue;
  94       assert(ffsll(operand_mask) <= phi->operands.size());
  95
  96       uint64_t operands = operand_mask;
  97       while (operands) {
  98          unsigned operand = u_bit_scan64(&operands);
  99          Operand new_operand = get_ssa(program, block->linear_preds[operand], state);
 100          phi->operands[operand] = new_operand;
 101          if (!new_operand.isUndefined())
 102             state->phis[new_operand.tempId()][(phi_use){block, phi_def}] |= (uint64_t)1 << operand;
 103       }
 104       return;
 105    }
 106    assert(false);
 107 }
 108
 109 Temp write_ssa(Program *program, Block *block, ssa_state *state, unsigned previous) {
 110    unsigned id = program->allocateId();
 111    state->latest[block->index] = id;
 112
 113    /* update phis */
 114    if (previous) {
 115       std::map<phi_use, uint64_t> phis;
 116       phis.swap(state->phis[previous]);
 117       for (auto& phi : phis)
 118          update_phi(program, state, phi.first.block, phi.first.phi_def, phi.second);
 119    }
 120
 121    return {id, program->lane_mask};
 122 }
 123
 124 void insert_before_logical_end(Block *block, aco_ptr<Instruction> instr)
 125 {
 126    auto IsLogicalEnd = [] (const aco_ptr<Instruction>& instr) -> bool {
 127       return instr->opcode == aco_opcode::p_logical_end;
 128    };
 129    auto it = std::find_if(block->instructions.crbegin(), block->instructions.crend(), IsLogicalEnd);
 130
 131    if (it == block->instructions.crend()) {
 132       assert(block->instructions.back()->format == Format::PSEUDO_BRANCH);
 133       block->instructions.insert(std::prev(block->instructions.end()), std::move(instr));
 134    }
 135    else
 136       block->instructions.insert(std::prev(it.base()), std::move(instr));
 137 }
 138
 139 void lower_divergent_bool_phi(Program *program, Block *block, aco_ptr<Instruction>& phi)
 140 {
 141    Builder bld(program);
 142
 143    ssa_state state;
 144    state.latest[block->index] = phi->definitions[0].tempId();
 145    for (unsigned i = 0; i < phi->operands.size(); i++) {
 146       Block *pred = &program->blocks[block->logical_preds[i]];
 147
 148       if (phi->operands[i].isUndefined())
 149          continue;
 150
 151       assert(phi->operands[i].isTemp());
 152       Temp phi_src = phi->operands[i].getTemp();
 153       assert(phi_src.regClass() == bld.lm);
 154
 155       Operand cur = get_ssa(program, pred->index, &state);
 156       assert(cur.regClass() == bld.lm);
 157       Temp new_cur = write_ssa(program, pred, &state, cur.isTemp() ? cur.tempId() : 0);
 158       assert(new_cur.regClass() == bld.lm);
 159
 160       if (cur.isUndefined()) {
 161          insert_before_logical_end(pred, bld.sop1(aco_opcode::s_mov_b64, Definition(new_cur), phi_src).get_ptr());
 162       } else {
 163          Temp tmp1 = bld.tmp(bld.lm), tmp2 = bld.tmp(bld.lm);
 164          insert_before_logical_end(pred,
 165             bld.sop2(Builder::s_andn2, Definition(tmp1), bld.def(s1, scc),
 166                      cur, Operand(exec, bld.lm)).get_ptr());
 167          insert_before_logical_end(pred,
 168             bld.sop2(Builder::s_and, Definition(tmp2), bld.def(s1, scc),
 169                      phi_src, Operand(exec, bld.lm)).get_ptr());
 170          insert_before_logical_end(pred,
 171             bld.sop2(Builder::s_or, Definition(new_cur), bld.def(s1, scc),
 172                      tmp1, tmp2).get_ptr());
 173       }
 174    }
 175
 176    unsigned num_preds = block->linear_preds.size();
 177    if (phi->operands.size() != num_preds) {
 178       Pseudo_instruction* new_phi{create_instruction<Pseudo_instruction>(aco_opcode::p_linear_phi, Format::PSEUDO, num_preds, 1)};
 179       new_phi->definitions[0] = phi->definitions[0];
 180       phi.reset(new_phi);
 181    } else {
 182       phi->opcode = aco_opcode::p_linear_phi;
 183    }
 184    assert(phi->operands.size() == num_preds);
 185
 186    for (unsigned i = 0; i < num_preds; i++)
 187       phi->operands[i] = get_ssa(program, block->linear_preds[i], &state);
 188
 189    return;
 190 }
 191
 192 void lower_subdword_phis(Program *program, Block *block, aco_ptr<Instruction>& phi)
 193 {
 194    Builder bld(program);
 195    for (unsigned i = 0; i < phi->operands.size(); i++) {
 196       if (phi->operands[i].isUndefined())
 197          continue;
 198       if (phi->operands[i].regClass() == phi->definitions[0].regClass())
 199          continue;
 200
 201       assert(phi->operands[i].isTemp());
 202       Block *pred = &program->blocks[block->logical_preds[i]];
 203       Temp phi_src = phi->operands[i].getTemp();
 204
 205       assert(phi_src.regClass().type() == RegType::sgpr);
 206       Temp tmp = bld.tmp(RegClass(RegType::vgpr, phi_src.size()));
 207       insert_before_logical_end(pred, bld.pseudo(aco_opcode::p_create_vector, Definition(tmp), phi_src).get_ptr());
 208       Temp new_phi_src = bld.tmp(phi->definitions[0].regClass());
 209       insert_before_logical_end(pred, bld.pseudo(aco_opcode::p_extract_vector, Definition(new_phi_src), tmp, Operand(0u)).get_ptr());
 210
 211       phi->operands[i].setTemp(new_phi_src);
 212    }
 213    return;
 214 }
 215
 216 void lower_phis(Program* program)
 217 {
 218    for (Block& block : program->blocks) {
 219       for (aco_ptr<Instruction>& phi : block.instructions) {
 220          if (phi->opcode == aco_opcode::p_phi) {
 221             assert(program->wave_size == 64 ? phi->definitions[0].regClass() != s1 : phi->definitions[0].regClass() != s2);
 222             if (phi->definitions[0].regClass() == program->lane_mask)
 223                lower_divergent_bool_phi(program, &block, phi);
 224             else if (phi->definitions[0].regClass().is_subdword())
 225                lower_subdword_phis(program, &block, phi);
 226          } else if (!is_phi(phi)) {
 227             break;
 228          }
 229       }
 230    }
 231 }
 232
 233 }