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