src/compiler/nir/nir_opt_idiv_const.c

   1 /*
   2  * Copyright © 2018 Intel 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 #include "nir.h"
  25 #include "nir_builder.h"
  26 #include "util/fast_idiv_by_const.h"
  27 #include "util/u_math.h"
  28
  29 static nir_ssa_def *
  30 build_udiv(nir_builder *b, nir_ssa_def *n, uint64_t d)
  31 {
  32    if (d == 0) {
  33       return nir_imm_intN_t(b, 0, n->bit_size);
  34    } else if (util_is_power_of_two_or_zero64(d)) {
  35       return nir_ushr_imm(b, n, util_logbase2_64(d));
  36    } else {
  37       struct util_fast_udiv_info m =
  38          util_compute_fast_udiv_info(d, n->bit_size, n->bit_size);
  39
  40       if (m.pre_shift)
  41          n = nir_ushr_imm(b, n, m.pre_shift);
  42       if (m.increment)
  43          n = nir_uadd_sat(b, n, nir_imm_intN_t(b, m.increment, n->bit_size));
  44       n = nir_umul_high(b, n, nir_imm_intN_t(b, m.multiplier, n->bit_size));
  45       if (m.post_shift)
  46          n = nir_ushr_imm(b, n, m.post_shift);
  47
  48       return n;
  49    }
  50 }
  51
  52 static nir_ssa_def *
  53 build_umod(nir_builder *b, nir_ssa_def *n, uint64_t d)
  54 {
  55    if (d == 0) {
  56       return nir_imm_intN_t(b, 0, n->bit_size);
  57    } else if (util_is_power_of_two_or_zero64(d)) {
  58       return nir_iand(b, n, nir_imm_intN_t(b, d - 1, n->bit_size));
  59    } else {
  60       return nir_isub(b, n, nir_imul(b, build_udiv(b, n, d),
  61                                         nir_imm_intN_t(b, d, n->bit_size)));
  62    }
  63 }
  64
  65 static nir_ssa_def *
  66 build_idiv(nir_builder *b, nir_ssa_def *n, int64_t d)
  67 {
  68    uint64_t abs_d = d < 0 ? -d : d;
  69
  70    if (d == 0) {
  71       return nir_imm_intN_t(b, 0, n->bit_size);
  72    } else if (d == 1) {
  73       return n;
  74    } else if (d == -1) {
  75       return nir_ineg(b, n);
  76    } else if (util_is_power_of_two_or_zero64(abs_d)) {
  77       nir_ssa_def *uq = nir_ushr_imm(b, nir_iabs(b, n), util_logbase2_64(abs_d));
  78       nir_ssa_def *n_neg = nir_ilt(b, n, nir_imm_intN_t(b, 0, n->bit_size));
  79       nir_ssa_def *neg = d < 0 ? nir_inot(b, n_neg) : n_neg;
  80       return nir_bcsel(b, neg, nir_ineg(b, uq), uq);
  81    } else {
  82       struct util_fast_sdiv_info m =
  83          util_compute_fast_sdiv_info(d, n->bit_size);
  84
  85       nir_ssa_def *res =
  86          nir_imul_high(b, n, nir_imm_intN_t(b, m.multiplier, n->bit_size));
  87       if (d > 0 && m.multiplier < 0)
  88          res = nir_iadd(b, res, n);
  89       if (d < 0 && m.multiplier > 0)
  90          res = nir_isub(b, res, n);
  91       if (m.shift)
  92          res = nir_ishr_imm(b, res, m.shift);
  93       res = nir_iadd(b, res, nir_ushr_imm(b, res, n->bit_size - 1));
  94
  95       return res;
  96    }
  97 }
  98
  99 static bool
 100 nir_opt_idiv_const_instr(nir_builder *b, nir_alu_instr *alu)
 101 {
 102    assert(alu->dest.dest.is_ssa);
 103    assert(alu->src[0].src.is_ssa && alu->src[1].src.is_ssa);
 104
 105    nir_const_value *const_denom = nir_src_as_const_value(alu->src[1].src);
 106    if (!const_denom)
 107       return false;
 108
 109    unsigned bit_size = alu->src[1].src.ssa->bit_size;
 110
 111    b->cursor = nir_before_instr(&alu->instr);
 112
 113    nir_ssa_def *q[4];
 114    for (unsigned comp = 0; comp < alu->dest.dest.ssa.num_components; comp++) {
 115       /* Get the numerator for the channel */
 116       nir_ssa_def *n = nir_channel(b, alu->src[0].src.ssa,
 117                                    alu->src[0].swizzle[comp]);
 118
 119       /* Get the denominator for the channel */
 120       int64_t d;
 121       switch (bit_size) {
 122       case 8:
 123          d = const_denom[alu->src[1].swizzle[comp]].i8;
 124          break;
 125       case 16:
 126          d = const_denom[alu->src[1].swizzle[comp]].i16;
 127          break;
 128       case 32:
 129          d = const_denom[alu->src[1].swizzle[comp]].i32;
 130          break;
 131       case 64:
 132          d = const_denom[alu->src[1].swizzle[comp]].i64;
 133          break;
 134       default:
 135          unreachable("Invalid bit size");
 136       }
 137
 138       nir_alu_type d_type = nir_op_infos[alu->op].input_types[1];
 139       if (nir_alu_type_get_base_type(d_type) == nir_type_uint) {
 140          /* The code above sign-extended.  If we're lowering an unsigned op,
 141           * we need to mask it off to the correct number of bits so that a
 142           * cast to uint64_t will do the right thing.
 143           */
 144          if (bit_size < 64)
 145             d &= (1ull << bit_size) - 1;
 146       }
 147
 148       switch (alu->op) {
 149       case nir_op_udiv:
 150          q[comp] = build_udiv(b, n, d);
 151          break;
 152       case nir_op_idiv:
 153          q[comp] = build_idiv(b, n, d);
 154          break;
 155       case nir_op_umod:
 156          q[comp] = build_umod(b, n, d);
 157          break;
 158       default:
 159          unreachable("Unknown integer division op");
 160       }
 161    }
 162
 163    nir_ssa_def *qvec = nir_vec(b, q, alu->dest.dest.ssa.num_components);
 164    nir_ssa_def_rewrite_uses(&alu->dest.dest.ssa, nir_src_for_ssa(qvec));
 165    nir_instr_remove(&alu->instr);
 166
 167    return true;
 168 }
 169
 170 static bool
 171 nir_opt_idiv_const_impl(nir_function_impl *impl, unsigned min_bit_size)
 172 {
 173    bool progress = false;
 174
 175    nir_builder b;
 176    nir_builder_init(&b, impl);
 177
 178    nir_foreach_block(block, impl) {
 179       nir_foreach_instr_safe(instr, block) {
 180          if (instr->type != nir_instr_type_alu)
 181             continue;
 182
 183          nir_alu_instr *alu = nir_instr_as_alu(instr);
 184          if (alu->op != nir_op_udiv &&
 185              alu->op != nir_op_idiv &&
 186              alu->op != nir_op_umod)
 187             continue;
 188
 189          assert(alu->dest.dest.is_ssa);
 190          if (alu->dest.dest.ssa.bit_size < min_bit_size)
 191             continue;
 192
 193          progress |= nir_opt_idiv_const_instr(&b, alu);
 194       }
 195    }
 196
 197    if (progress) {
 198       nir_metadata_preserve(impl, nir_metadata_block_index |
 199                                   nir_metadata_dominance);
 200    } else {
 201       nir_metadata_preserve(impl, nir_metadata_all);
 202    }
 203
 204    return progress;
 205 }
 206
 207 bool
 208 nir_opt_idiv_const(nir_shader *shader, unsigned min_bit_size)
 209 {
 210    bool progress = false;
 211
 212    nir_foreach_function(function, shader) {
 213       if (function->impl)
 214          progress |= nir_opt_idiv_const_impl(function->impl, min_bit_size);
 215    }
 216
 217    return progress;
 218 }