2 * Copyright © 2016 Intel Corporation
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:
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
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
25 #include "nir_builder.h"
28 lower_imul64(nir_builder
*b
, nir_ssa_def
*x
, nir_ssa_def
*y
)
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
);
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
)));
40 return nir_pack_64_2x32_split(b
, res_lo
, res_hi
);
44 lower_isign64(nir_builder
*b
, nir_ssa_def
*x
)
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
);
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
));
53 return nir_pack_64_2x32_split(b
, res_lo
, res_hi
);
57 lower_udiv64_mod64(nir_builder
*b
, nir_ssa_def
*n
, nir_ssa_def
*d
,
58 nir_ssa_def
**q
, nir_ssa_def
**r
)
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.
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
);
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
);
73 nir_ssa_def
*n_hi_before_if
= n_hi
;
74 nir_ssa_def
*q_hi_before_if
= q_hi
;
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
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
));
85 /* If we only have one component, then the bany above goes away and
86 * this is always true within the if statement.
88 if (n
->num_components
== 1)
89 need_high_div
= nir_imm_int(b
, NIR_TRUE
);
91 nir_ssa_def
*log2_d_lo
= nir_ufind_msb(b
, d_lo
);
93 for (int i
= 31; i
>= 0; i
--) {
94 /* if ((d.x << i) <= n.y) {
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
));
105 /* log2_d_lo is always <= 31, so we don't need to bother with it
106 * in the last iteration.
108 cond
= nir_iand(b
, cond
,
109 nir_ige(b
, nir_imm_int(b
, 31 - i
), log2_d_lo
));
111 n_hi
= nir_bcsel(b
, cond
, new_n_hi
, n_hi
);
112 q_hi
= nir_bcsel(b
, cond
, new_q_hi
, q_hi
);
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
);
119 nir_ssa_def
*log2_denom
= nir_ufind_msb(b
, d_hi
);
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) {
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
);
134 /* log2_denom is always <= 31, so we don't need to bother with it
135 * in the last iteration.
137 cond
= nir_iand(b
, cond
,
138 nir_ige(b
, nir_imm_int(b
, 31 - i
), log2_denom
));
140 n
= nir_bcsel(b
, cond
, new_n
, n
);
141 q_lo
= nir_bcsel(b
, cond
, new_q_lo
, q_lo
);
144 *q
= nir_pack_64_2x32_split(b
, q_lo
, q_hi
);
149 lower_udiv64(nir_builder
*b
, nir_ssa_def
*n
, nir_ssa_def
*d
)
152 lower_udiv64_mod64(b
, n
, d
, &q
, &r
);
157 lower_idiv64(nir_builder
*b
, nir_ssa_def
*n
, nir_ssa_def
*d
)
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
);
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)));
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
);
170 lower_umod64(nir_builder
*b
, nir_ssa_def
*n
, nir_ssa_def
*d
)
173 lower_udiv64_mod64(b
, n
, d
, &q
, &r
);
178 lower_imod64(nir_builder
*b
, nir_ssa_def
*n
, nir_ssa_def
*d
)
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));
186 lower_udiv64_mod64(b
, nir_iabs(b
, n
), nir_iabs(b
, d
), &q
, &r
);
188 nir_ssa_def
*rem
= nir_bcsel(b
, n_is_neg
, nir_ineg(b
, r
), r
);
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
)));
196 lower_irem64(nir_builder
*b
, nir_ssa_def
*n
, nir_ssa_def
*d
)
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));
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
);
206 static nir_lower_int64_options
207 opcode_to_options_mask(nir_op opcode
)
211 return nir_lower_imul64
;
213 return nir_lower_isign64
;
219 return nir_lower_divmod64
;
226 lower_int64_alu_instr(nir_builder
*b
, nir_alu_instr
*alu
)
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
);
234 return lower_imul64(b
, src
[0], src
[1]);
236 return lower_isign64(b
, src
[0]);
238 return lower_udiv64(b
, src
[0], src
[1]);
240 return lower_idiv64(b
, src
[0], src
[1]);
242 return lower_umod64(b
, src
[0], src
[1]);
244 return lower_imod64(b
, src
[0], src
[1]);
246 return lower_irem64(b
, src
[0], src
[1]);
248 unreachable("Invalid ALU opcode to lower");
253 lower_int64_impl(nir_function_impl
*impl
, nir_lower_int64_options options
)
256 nir_builder_init(&b
, impl
);
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
)
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)
269 if (!(options
& opcode_to_options_mask(alu
->op
)))
272 b
.cursor
= nir_before_instr(instr
);
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
);
283 nir_metadata_preserve(impl
, nir_metadata_none
);
289 nir_lower_int64(nir_shader
*shader
, nir_lower_int64_options options
)
291 bool progress
= false;
293 nir_foreach_function(function
, shader
) {
295 progress
|= lower_int64_impl(function
->impl
, options
);