src/amd/compiler/aco_opt_value_numbering.cpp

   1 /*
   2  * Copyright © 2018 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 <map>
  26 #include <unordered_set>
  27
  28 #include "aco_ir.h"
  29
  30 /*
  31  * Implements the algorithm for dominator-tree value numbering
  32  * from "Value Numbering" by Briggs, Cooper, and Simpson.
  33  */
  34
  35 namespace aco {
  36 namespace {
  37
  38 struct InstrHash {
  39    std::size_t operator()(Instruction* instr) const
  40    {
  41       uint64_t hash = (uint64_t) instr->opcode + (uint64_t) instr->format;
  42       for (unsigned i = 0; i < instr->operands.size(); i++) {
  43          Operand op = instr->operands[i];
  44          uint64_t val = op.isTemp() ? op.tempId() : op.isFixed() ? op.physReg() : op.constantValue();
  45          hash |= val << (i+1) * 8;
  46       }
  47       if (instr->isVOP3()) {
  48          VOP3A_instruction* vop3 = static_cast<VOP3A_instruction*>(instr);
  49          for (unsigned i = 0; i < 3; i++) {
  50             hash ^= vop3->abs[i] << (i*3 + 0);
  51             hash ^= vop3->opsel[i] << (i*3 + 1);
  52             hash ^= vop3->neg[i] << (i*3 + 2);
  53          }
  54          hash ^= (vop3->clamp << 28) * 13;
  55          hash += vop3->omod << 19;
  56       }
  57       switch (instr->format) {
  58       case Format::SMEM:
  59          break;
  60       case Format::VINTRP: {
  61          Interp_instruction* interp = static_cast<Interp_instruction*>(instr);
  62          hash ^= interp->attribute << 13;
  63          hash ^= interp->component << 27;
  64          break;
  65       }
  66       case Format::DS:
  67          break;
  68       default:
  69          break;
  70       }
  71
  72       return hash;
  73    }
  74 };
  75
  76 struct InstrPred {
  77    bool operator()(Instruction* a, Instruction* b) const
  78    {
  79       if (a->format != b->format)
  80          return false;
  81       if (a->opcode != b->opcode)
  82          return false;
  83       if (a->operands.size() != b->operands.size() || a->definitions.size() != b->definitions.size())
  84          return false; /* possible with pseudo-instructions */
  85       /* We can't value number v_readlane_b32 across control flow or discards
  86        * because of the possibility of live-range splits.
  87        * We can't value number permutes for the same reason as
  88        * v_readlane_b32 and because discards affect the result */
  89       if (a->opcode == aco_opcode::v_readfirstlane_b32 || a->opcode == aco_opcode::v_readlane_b32 ||
  90           a->opcode == aco_opcode::ds_bpermute_b32 || a->opcode == aco_opcode::ds_permute_b32 ||
  91           a->opcode == aco_opcode::ds_swizzle_b32 || a->format == Format::PSEUDO_REDUCTION) {
  92          if (a->pass_flags != b->pass_flags)
  93             return false;
  94       }
  95       for (unsigned i = 0; i < a->operands.size(); i++) {
  96          if (a->operands[i].isConstant()) {
  97             if (!b->operands[i].isConstant())
  98                return false;
  99             if (a->operands[i].constantValue() != b->operands[i].constantValue())
 100                return false;
 101          }
 102          else if (a->operands[i].isTemp()) {
 103             if (!b->operands[i].isTemp())
 104                return false;
 105             if (a->operands[i].tempId() != b->operands[i].tempId())
 106                return false;
 107          }
 108          else if (a->operands[i].isUndefined() ^ b->operands[i].isUndefined())
 109             return false;
 110          if (a->operands[i].isFixed()) {
 111             if (a->operands[i].physReg() == exec)
 112                return false;
 113             if (!b->operands[i].isFixed())
 114                return false;
 115             if (!(a->operands[i].physReg() == b->operands[i].physReg()))
 116                return false;
 117          }
 118       }
 119       for (unsigned i = 0; i < a->definitions.size(); i++) {
 120          if (a->definitions[i].isTemp()) {
 121             if (!b->definitions[i].isTemp())
 122                return false;
 123             if (a->definitions[i].regClass() != b->definitions[i].regClass())
 124                return false;
 125          }
 126          if (a->definitions[i].isFixed()) {
 127             if (!b->definitions[i].isFixed())
 128                return false;
 129             if (!(a->definitions[i].physReg() == b->definitions[i].physReg()))
 130                return false;
 131          }
 132       }
 133       if (a->format == Format::PSEUDO_BRANCH)
 134          return false;
 135       if (a->isVOP3()) {
 136          VOP3A_instruction* a3 = static_cast<VOP3A_instruction*>(a);
 137          VOP3A_instruction* b3 = static_cast<VOP3A_instruction*>(b);
 138          for (unsigned i = 0; i < 3; i++) {
 139             if (a3->abs[i] != b3->abs[i] ||
 140                 a3->opsel[i] != b3->opsel[i] ||
 141                 a3->neg[i] != b3->neg[i])
 142                return false;
 143          }
 144          return a3->clamp == b3->clamp &&
 145                 a3->omod == b3->omod;
 146       }
 147       if (a->isDPP()) {
 148          DPP_instruction* aDPP = static_cast<DPP_instruction*>(a);
 149          DPP_instruction* bDPP = static_cast<DPP_instruction*>(b);
 150          return aDPP->dpp_ctrl == bDPP->dpp_ctrl &&
 151                 aDPP->bank_mask == bDPP->bank_mask &&
 152                 aDPP->row_mask == bDPP->row_mask &&
 153                 aDPP->bound_ctrl == bDPP->bound_ctrl &&
 154                 aDPP->abs[0] == bDPP->abs[0] &&
 155                 aDPP->abs[1] == bDPP->abs[1] &&
 156                 aDPP->neg[0] == bDPP->neg[0] &&
 157                 aDPP->neg[1] == bDPP->neg[1];
 158       }
 159       switch (a->format) {
 160          case Format::VOPC: {
 161             /* Since the results depend on the exec mask, these shouldn't
 162              * be value numbered (this is especially useful for subgroupBallot()). */
 163             return false;
 164          }
 165          case Format::SOPK: {
 166             SOPK_instruction* aK = static_cast<SOPK_instruction*>(a);
 167             SOPK_instruction* bK = static_cast<SOPK_instruction*>(b);
 168             return aK->imm == bK->imm;
 169          }
 170          case Format::SMEM: {
 171             SMEM_instruction* aS = static_cast<SMEM_instruction*>(a);
 172             SMEM_instruction* bS = static_cast<SMEM_instruction*>(b);
 173             return aS->can_reorder && bS->can_reorder &&
 174                    aS->glc == bS->glc && aS->nv == bS->nv;
 175          }
 176          case Format::VINTRP: {
 177             Interp_instruction* aI = static_cast<Interp_instruction*>(a);
 178             Interp_instruction* bI = static_cast<Interp_instruction*>(b);
 179             if (aI->attribute != bI->attribute)
 180                return false;
 181             if (aI->component != bI->component)
 182                return false;
 183             return true;
 184          }
 185          case Format::PSEUDO_REDUCTION: {
 186             Pseudo_reduction_instruction *aR = static_cast<Pseudo_reduction_instruction*>(a);
 187             Pseudo_reduction_instruction *bR = static_cast<Pseudo_reduction_instruction*>(b);
 188             return aR->reduce_op == bR->reduce_op && aR->cluster_size == bR->cluster_size;
 189          }
 190          case Format::MTBUF: {
 191             /* this is fine since they are only used for vertex input fetches */
 192             MTBUF_instruction* aM = static_cast<MTBUF_instruction *>(a);
 193             MTBUF_instruction* bM = static_cast<MTBUF_instruction *>(b);
 194             return aM->dfmt == bM->dfmt &&
 195                    aM->nfmt == bM->nfmt &&
 196                    aM->offset == bM->offset &&
 197                    aM->offen == bM->offen &&
 198                    aM->idxen == bM->idxen &&
 199                    aM->glc == bM->glc &&
 200                    aM->slc == bM->slc &&
 201                    aM->tfe == bM->tfe &&
 202                    aM->disable_wqm == bM->disable_wqm;
 203          }
 204          /* we want to optimize these in NIR and don't hassle with load-store dependencies */
 205          case Format::MUBUF:
 206          case Format::FLAT:
 207          case Format::GLOBAL:
 208          case Format::SCRATCH:
 209             return false;
 210          case Format::DS: {
 211             /* we already handle potential issue with permute/swizzle above */
 212             DS_instruction* aD = static_cast<DS_instruction *>(a);
 213             DS_instruction* bD = static_cast<DS_instruction *>(b);
 214             if (a->opcode != aco_opcode::ds_bpermute_b32 &&
 215                 a->opcode != aco_opcode::ds_permute_b32 &&
 216                 a->opcode != aco_opcode::ds_swizzle_b32)
 217                return false;
 218             return aD->gds == bD->gds && aD->offset0 == bD->offset0 && aD->offset1 == bD->offset1;
 219          }
 220          case Format::MIMG: {
 221             MIMG_instruction* aM = static_cast<MIMG_instruction*>(a);
 222             MIMG_instruction* bM = static_cast<MIMG_instruction*>(b);
 223             return aM->can_reorder && bM->can_reorder &&
 224                    aM->dmask == bM->dmask &&
 225                    aM->unrm == bM->unrm &&
 226                    aM->glc == bM->glc &&
 227                    aM->slc == bM->slc &&
 228                    aM->tfe == bM->tfe &&
 229                    aM->da == bM->da &&
 230                    aM->lwe == bM->lwe &&
 231                    aM->r128 == bM->r128 &&
 232                    aM->a16 == bM->a16 &&
 233                    aM->d16 == bM->d16 &&
 234                    aM->disable_wqm == bM->disable_wqm;
 235          }
 236          default:
 237             return true;
 238       }
 239    }
 240 };
 241
 242
 243 typedef std::unordered_set<Instruction*, InstrHash, InstrPred> expr_set;
 244
 245 void process_block(Block& block,
 246                    expr_set& expr_values,
 247                    std::map<uint32_t, Temp>& renames,
 248                    uint32_t *exec_id)
 249 {
 250    bool run = false;
 251    std::vector<aco_ptr<Instruction>>::iterator it = block.instructions.begin();
 252    std::vector<aco_ptr<Instruction>> new_instructions;
 253    new_instructions.reserve(block.instructions.size());
 254    expr_set phi_values;
 255
 256    while (it != block.instructions.end()) {
 257       aco_ptr<Instruction>& instr = *it;
 258       /* first, rename operands */
 259       for (Operand& op : instr->operands) {
 260          if (!op.isTemp())
 261             continue;
 262          auto it = renames.find(op.tempId());
 263          if (it != renames.end())
 264             op.setTemp(it->second);
 265       }
 266
 267       if (instr->definitions.empty() || !run) {
 268          if (instr->opcode == aco_opcode::p_logical_start)
 269             run = true;
 270          else if (instr->opcode == aco_opcode::p_logical_end)
 271             run = false;
 272          else if (instr->opcode == aco_opcode::p_phi || instr->opcode == aco_opcode::p_linear_phi) {
 273             std::pair<expr_set::iterator, bool> res = phi_values.emplace(instr.get());
 274             if (!res.second) {
 275                Instruction* orig_phi = *(res.first);
 276                renames.emplace(instr->definitions[0].tempId(), orig_phi->definitions[0].getTemp()).second;
 277                ++it;
 278                continue;
 279             }
 280          }
 281          new_instructions.emplace_back(std::move(instr));
 282          ++it;
 283          continue;
 284       }
 285
 286       /* simple copy-propagation through renaming */
 287       if ((instr->opcode == aco_opcode::s_mov_b32 || instr->opcode == aco_opcode::s_mov_b64 || instr->opcode == aco_opcode::v_mov_b32) &&
 288           !instr->definitions[0].isFixed() && instr->operands[0].isTemp() && instr->operands[0].regClass() == instr->definitions[0].regClass() &&
 289           !instr->isDPP() && !((int)instr->format & (int)Format::SDWA)) {
 290          renames[instr->definitions[0].tempId()] = instr->operands[0].getTemp();
 291       }
 292
 293       if (instr->opcode == aco_opcode::p_discard_if ||
 294           instr->opcode == aco_opcode::p_demote_to_helper)
 295          (*exec_id)++;
 296
 297       instr->pass_flags = *exec_id;
 298
 299       std::pair<expr_set::iterator, bool> res = expr_values.emplace(instr.get());
 300
 301       /* if there was already an expression with the same value number */
 302       if (!res.second) {
 303          Instruction* orig_instr = *(res.first);
 304          assert(instr->definitions.size() == orig_instr->definitions.size());
 305          for (unsigned i = 0; i < instr->definitions.size(); i++) {
 306             assert(instr->definitions[i].regClass() == orig_instr->definitions[i].regClass());
 307             renames.emplace(instr->definitions[i].tempId(), orig_instr->definitions[i].getTemp()).second;
 308          }
 309       } else {
 310          new_instructions.emplace_back(std::move(instr));
 311       }
 312       ++it;
 313    }
 314
 315    block.instructions.swap(new_instructions);
 316 }
 317
 318 void rename_phi_operands(Block& block, std::map<uint32_t, Temp>& renames)
 319 {
 320    for (aco_ptr<Instruction>& phi : block.instructions) {
 321       if (phi->opcode != aco_opcode::p_phi && phi->opcode != aco_opcode::p_linear_phi)
 322          break;
 323
 324       for (Operand& op : phi->operands) {
 325          if (!op.isTemp())
 326             continue;
 327          auto it = renames.find(op.tempId());
 328          if (it != renames.end())
 329             op.setTemp(it->second);
 330       }
 331    }
 332 }
 333 } /* end namespace */
 334
 335
 336 void value_numbering(Program* program)
 337 {
 338    std::vector<expr_set> expr_values(program->blocks.size());
 339    std::map<uint32_t, Temp> renames;
 340    uint32_t exec_id = 0;
 341
 342    for (Block& block : program->blocks) {
 343       if (block.logical_idom != -1) {
 344          /* initialize expr_values from idom */
 345          expr_values[block.index] = expr_values[block.logical_idom];
 346          process_block(block, expr_values[block.index], renames, &exec_id);
 347       } else {
 348          expr_set empty;
 349          process_block(block, empty, renames, &exec_id);
 350       }
 351       exec_id++;
 352    }
 353
 354    for (Block& block : program->blocks)
 355       rename_phi_operands(block, renames);
 356 }
 357
 358 }