src/compiler/nir/nir_lower_int64.c

   1 /*
   2  * Copyright © 2016 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
  27 static nir_ssa_def *
  28 lower_imul64(nir_builder *b, nir_ssa_def *x, nir_ssa_def *y)
  29 {
  30    nir_ssa_def *x_lo = nir_unpack_64_2x32_split_x(b, x);
  31    nir_ssa_def *x_hi = nir_unpack_64_2x32_split_y(b, x);
  32    nir_ssa_def *y_lo = nir_unpack_64_2x32_split_x(b, y);
  33    nir_ssa_def *y_hi = nir_unpack_64_2x32_split_y(b, y);
  34
  35    nir_ssa_def *res_lo = nir_imul(b, x_lo, y_lo);
  36    nir_ssa_def *res_hi = nir_iadd(b, nir_umul_high(b, x_lo, y_lo),
  37                          nir_iadd(b, nir_imul(b, x_lo, y_hi),
  38                                      nir_imul(b, x_hi, y_lo)));
  39
  40    return nir_pack_64_2x32_split(b, res_lo, res_hi);
  41 }
  42
  43 static nir_ssa_def *
  44 lower_isign64(nir_builder *b, nir_ssa_def *x)
  45 {
  46    nir_ssa_def *x_lo = nir_unpack_64_2x32_split_x(b, x);
  47    nir_ssa_def *x_hi = nir_unpack_64_2x32_split_y(b, x);
  48
  49    nir_ssa_def *is_non_zero = nir_i2b(b, nir_ior(b, x_lo, x_hi));
  50    nir_ssa_def *res_hi = nir_ishr(b, x_hi, nir_imm_int(b, 31));
  51    nir_ssa_def *res_lo = nir_ior(b, res_hi, nir_b2i(b, is_non_zero));
  52
  53    return nir_pack_64_2x32_split(b, res_lo, res_hi);
  54 }
  55
  56 static void
  57 lower_udiv64_mod64(nir_builder *b, nir_ssa_def *n, nir_ssa_def *d,
  58                    nir_ssa_def **q, nir_ssa_def **r)
  59 {
  60    /* TODO: We should specially handle the case where the denominator is a
  61     * constant.  In that case, we should be able to reduce it to a multiply by
  62     * a constant, some shifts, and an add.
  63     */
  64    nir_ssa_def *n_lo = nir_unpack_64_2x32_split_x(b, n);
  65    nir_ssa_def *n_hi = nir_unpack_64_2x32_split_y(b, n);
  66    nir_ssa_def *d_lo = nir_unpack_64_2x32_split_x(b, d);
  67    nir_ssa_def *d_hi = nir_unpack_64_2x32_split_y(b, d);
  68
  69    nir_const_value v = { .u32 = { 0, 0, 0, 0 } };
  70    nir_ssa_def *q_lo = nir_build_imm(b, n->num_components, 32, v);
  71    nir_ssa_def *q_hi = nir_build_imm(b, n->num_components, 32, v);
  72
  73    nir_ssa_def *n_hi_before_if = n_hi;
  74    nir_ssa_def *q_hi_before_if = q_hi;
  75
  76    /* If the upper 32 bits of denom are non-zero, it is impossible for shifts
  77     * greater than 32 bits to occur.  If the upper 32 bits of the numerator
  78     * are zero, it is impossible for (denom << [63, 32]) <= numer unless
  79     * denom == 0.
  80     */
  81    nir_ssa_def *need_high_div =
  82       nir_iand(b, nir_ieq(b, d_hi, nir_imm_int(b, 0)), nir_uge(b, n_hi, d_lo));
  83    nir_push_if(b, nir_bany(b, need_high_div));
  84    {
  85       /* If we only have one component, then the bany above goes away and
  86        * this is always true within the if statement.
  87        */
  88       if (n->num_components == 1)
  89          need_high_div = nir_imm_int(b, NIR_TRUE);
  90
  91       nir_ssa_def *log2_d_lo = nir_ufind_msb(b, d_lo);
  92
  93       for (int i = 31; i >= 0; i--) {
  94          /* if ((d.x << i) <= n.y) {
  95           *    n.y -= d.x << i;
  96           *    quot.y |= 1U << i;
  97           * }
  98           */
  99          nir_ssa_def *d_shift = nir_ishl(b, d_lo, nir_imm_int(b, i));
 100          nir_ssa_def *new_n_hi = nir_isub(b, n_hi, d_shift);
 101          nir_ssa_def *new_q_hi = nir_ior(b, q_hi, nir_imm_int(b, 1u << i));
 102          nir_ssa_def *cond = nir_iand(b, need_high_div,
 103                                          nir_uge(b, n_hi, d_shift));
 104          if (i != 0) {
 105             /* log2_d_lo is always <= 31, so we don't need to bother with it
 106              * in the last iteration.
 107              */
 108             cond = nir_iand(b, cond,
 109                                nir_ige(b, nir_imm_int(b, 31 - i), log2_d_lo));
 110          }
 111          n_hi = nir_bcsel(b, cond, new_n_hi, n_hi);
 112          q_hi = nir_bcsel(b, cond, new_q_hi, q_hi);
 113       }
 114    }
 115    nir_pop_if(b, NULL);
 116    n_hi = nir_if_phi(b, n_hi, n_hi_before_if);
 117    q_hi = nir_if_phi(b, q_hi, q_hi_before_if);
 118
 119    nir_ssa_def *log2_denom = nir_ufind_msb(b, d_hi);
 120
 121    n = nir_pack_64_2x32_split(b, n_lo, n_hi);
 122    d = nir_pack_64_2x32_split(b, d_lo, d_hi);
 123    for (int i = 31; i >= 0; i--) {
 124       /* if ((d64 << i) <= n64) {
 125        *    n64 -= d64 << i;
 126        *    quot.x |= 1U << i;
 127        * }
 128        */
 129       nir_ssa_def *d_shift = nir_ishl(b, d, nir_imm_int(b, i));
 130       nir_ssa_def *new_n = nir_isub(b, n, d_shift);
 131       nir_ssa_def *new_q_lo = nir_ior(b, q_lo, nir_imm_int(b, 1u << i));
 132       nir_ssa_def *cond = nir_uge(b, n, d_shift);
 133       if (i != 0) {
 134          /* log2_denom is always <= 31, so we don't need to bother with it
 135           * in the last iteration.
 136           */
 137          cond = nir_iand(b, cond,
 138                             nir_ige(b, nir_imm_int(b, 31 - i), log2_denom));
 139       }
 140       n = nir_bcsel(b, cond, new_n, n);
 141       q_lo = nir_bcsel(b, cond, new_q_lo, q_lo);
 142    }
 143
 144    *q = nir_pack_64_2x32_split(b, q_lo, q_hi);
 145    *r = n;
 146 }
 147
 148 static nir_ssa_def *
 149 lower_udiv64(nir_builder *b, nir_ssa_def *n, nir_ssa_def *d)
 150 {
 151    nir_ssa_def *q, *r;
 152    lower_udiv64_mod64(b, n, d, &q, &r);
 153    return q;
 154 }
 155
 156 static nir_ssa_def *
 157 lower_idiv64(nir_builder *b, nir_ssa_def *n, nir_ssa_def *d)
 158 {
 159    nir_ssa_def *n_hi = nir_unpack_64_2x32_split_y(b, n);
 160    nir_ssa_def *d_hi = nir_unpack_64_2x32_split_y(b, d);
 161
 162    nir_ssa_def *negate = nir_ine(b, nir_ilt(b, n_hi, nir_imm_int(b, 0)),
 163                                     nir_ilt(b, d_hi, nir_imm_int(b, 0)));
 164    nir_ssa_def *q, *r;
 165    lower_udiv64_mod64(b, nir_iabs(b, n), nir_iabs(b, d), &q, &r);
 166    return nir_bcsel(b, negate, nir_ineg(b, q), q);
 167 }
 168
 169 static nir_ssa_def *
 170 lower_umod64(nir_builder *b, nir_ssa_def *n, nir_ssa_def *d)
 171 {
 172    nir_ssa_def *q, *r;
 173    lower_udiv64_mod64(b, n, d, &q, &r);
 174    return r;
 175 }
 176
 177 static nir_ssa_def *
 178 lower_imod64(nir_builder *b, nir_ssa_def *n, nir_ssa_def *d)
 179 {
 180    nir_ssa_def *n_hi = nir_unpack_64_2x32_split_y(b, n);
 181    nir_ssa_def *d_hi = nir_unpack_64_2x32_split_y(b, d);
 182    nir_ssa_def *n_is_neg = nir_ilt(b, n_hi, nir_imm_int(b, 0));
 183    nir_ssa_def *d_is_neg = nir_ilt(b, d_hi, nir_imm_int(b, 0));
 184
 185    nir_ssa_def *q, *r;
 186    lower_udiv64_mod64(b, nir_iabs(b, n), nir_iabs(b, d), &q, &r);
 187
 188    nir_ssa_def *rem = nir_bcsel(b, n_is_neg, nir_ineg(b, r), r);
 189
 190    return nir_bcsel(b, nir_ieq(b, r, nir_imm_int64(b, 0)), nir_imm_int64(b, 0),
 191           nir_bcsel(b, nir_ieq(b, n_is_neg, d_is_neg), rem,
 192                        nir_iadd(b, rem, d)));
 193 }
 194
 195 static nir_ssa_def *
 196 lower_irem64(nir_builder *b, nir_ssa_def *n, nir_ssa_def *d)
 197 {
 198    nir_ssa_def *n_hi = nir_unpack_64_2x32_split_y(b, n);
 199    nir_ssa_def *n_is_neg = nir_ilt(b, n_hi, nir_imm_int(b, 0));
 200
 201    nir_ssa_def *q, *r;
 202    lower_udiv64_mod64(b, nir_iabs(b, n), nir_iabs(b, d), &q, &r);
 203    return nir_bcsel(b, n_is_neg, nir_ineg(b, r), r);
 204 }
 205
 206 static nir_lower_int64_options
 207 opcode_to_options_mask(nir_op opcode)
 208 {
 209    switch (opcode) {
 210    case nir_op_imul:
 211       return nir_lower_imul64;
 212    case nir_op_isign:
 213       return nir_lower_isign64;
 214    case nir_op_udiv:
 215    case nir_op_idiv:
 216    case nir_op_umod:
 217    case nir_op_imod:
 218    case nir_op_irem:
 219       return nir_lower_divmod64;
 220    default:
 221       return 0;
 222    }
 223 }
 224
 225 static nir_ssa_def *
 226 lower_int64_alu_instr(nir_builder *b, nir_alu_instr *alu)
 227 {
 228    nir_ssa_def *src[4];
 229    for (unsigned i = 0; i < nir_op_infos[alu->op].num_inputs; i++)
 230       src[i] = nir_ssa_for_alu_src(b, alu, i);
 231
 232    switch (alu->op) {
 233    case nir_op_imul:
 234       return lower_imul64(b, src[0], src[1]);
 235    case nir_op_isign:
 236       return lower_isign64(b, src[0]);
 237    case nir_op_udiv:
 238       return lower_udiv64(b, src[0], src[1]);
 239    case nir_op_idiv:
 240       return lower_idiv64(b, src[0], src[1]);
 241    case nir_op_umod:
 242       return lower_umod64(b, src[0], src[1]);
 243    case nir_op_imod:
 244       return lower_imod64(b, src[0], src[1]);
 245    case nir_op_irem:
 246       return lower_irem64(b, src[0], src[1]);
 247    default:
 248       unreachable("Invalid ALU opcode to lower");
 249    }
 250 }
 251
 252 static bool
 253 lower_int64_impl(nir_function_impl *impl, nir_lower_int64_options options)
 254 {
 255    nir_builder b;
 256    nir_builder_init(&b, impl);
 257
 258    bool progress = false;
 259    nir_foreach_block(block, impl) {
 260       nir_foreach_instr_safe(instr, block) {
 261          if (instr->type != nir_instr_type_alu)
 262             continue;
 263
 264          nir_alu_instr *alu = nir_instr_as_alu(instr);
 265          assert(alu->dest.dest.is_ssa);
 266          if (alu->dest.dest.ssa.bit_size != 64)
 267             continue;
 268
 269          if (!(options & opcode_to_options_mask(alu->op)))
 270             continue;
 271
 272          b.cursor = nir_before_instr(instr);
 273
 274          nir_ssa_def *lowered = lower_int64_alu_instr(&b, alu);
 275          nir_ssa_def_rewrite_uses(&alu->dest.dest.ssa,
 276                                   nir_src_for_ssa(lowered));
 277          nir_instr_remove(&alu->instr);
 278          progress = true;
 279       }
 280    }
 281
 282    if (progress)
 283       nir_metadata_preserve(impl, nir_metadata_none);
 284
 285    return progress;
 286 }
 287
 288 bool
 289 nir_lower_int64(nir_shader *shader, nir_lower_int64_options options)
 290 {
 291    bool progress = false;
 292
 293    nir_foreach_function(function, shader) {
 294       if (function->impl)
 295          progress |= lower_int64_impl(function->impl, options);
 296    }
 297
 298    return progress;
 299 }