2 * Copyright © 2018 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"
26 #include "util/fast_idiv_by_const.h"
27 #include "util/u_math.h"
30 build_udiv(nir_builder
*b
, nir_ssa_def
*n
, uint64_t d
)
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(b
, n
, nir_imm_int(b
, util_logbase2_64(d
)));
37 struct util_fast_udiv_info m
=
38 util_compute_fast_udiv_info(d
, n
->bit_size
, n
->bit_size
);
41 n
= nir_ushr(b
, n
, nir_imm_int(b
, m
.pre_shift
));
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
));
46 n
= nir_ushr(b
, n
, nir_imm_int(b
, m
.post_shift
));
53 build_umod(nir_builder
*b
, nir_ssa_def
*n
, uint64_t d
)
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
));
60 return nir_isub(b
, n
, nir_imul(b
, build_udiv(b
, n
, d
),
61 nir_imm_intN_t(b
, d
, n
->bit_size
)));
66 build_idiv(nir_builder
*b
, nir_ssa_def
*n
, int64_t d
)
68 uint64_t abs_d
= d
< 0 ? -d
: d
;
71 return nir_imm_intN_t(b
, 0, n
->bit_size
);
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(b
, nir_iabs(b
, n
),
78 nir_imm_int(b
, util_logbase2_64(abs_d
)));
79 nir_ssa_def
*n_neg
= nir_ilt(b
, n
, nir_imm_intN_t(b
, 0, n
->bit_size
));
80 nir_ssa_def
*neg
= d
< 0 ? nir_inot(b
, n_neg
) : n_neg
;
81 return nir_bcsel(b
, neg
, nir_ineg(b
, uq
), uq
);
83 struct util_fast_sdiv_info m
=
84 util_compute_fast_sdiv_info(d
, n
->bit_size
);
87 nir_imul_high(b
, n
, nir_imm_intN_t(b
, m
.multiplier
, n
->bit_size
));
88 if (d
> 0 && m
.multiplier
< 0)
89 res
= nir_iadd(b
, res
, n
);
90 if (d
< 0 && m
.multiplier
> 0)
91 res
= nir_isub(b
, res
, n
);
93 res
= nir_ishr(b
, res
, nir_imm_int(b
, m
.shift
));
94 res
= nir_iadd(b
, res
, nir_ushr(b
, res
, nir_imm_int(b
, n
->bit_size
- 1)));
101 nir_opt_idiv_const_instr(nir_builder
*b
, nir_alu_instr
*alu
)
103 assert(alu
->dest
.dest
.is_ssa
);
104 assert(alu
->src
[0].src
.is_ssa
&& alu
->src
[1].src
.is_ssa
);
106 nir_const_value
*const_denom
= nir_src_as_const_value(alu
->src
[1].src
);
110 unsigned bit_size
= alu
->src
[1].src
.ssa
->bit_size
;
112 b
->cursor
= nir_before_instr(&alu
->instr
);
115 for (unsigned comp
= 0; comp
< alu
->dest
.dest
.ssa
.num_components
; comp
++) {
116 /* Get the numerator for the channel */
117 nir_ssa_def
*n
= nir_channel(b
, alu
->src
[0].src
.ssa
,
118 alu
->src
[0].swizzle
[comp
]);
120 /* Get the denominator for the channel */
124 d
= const_denom
[alu
->src
[1].swizzle
[comp
]].i8
;
127 d
= const_denom
[alu
->src
[1].swizzle
[comp
]].i16
;
130 d
= const_denom
[alu
->src
[1].swizzle
[comp
]].i32
;
133 d
= const_denom
[alu
->src
[1].swizzle
[comp
]].i64
;
136 unreachable("Invalid bit size");
139 nir_alu_type d_type
= nir_op_infos
[alu
->op
].input_types
[1];
140 if (nir_alu_type_get_base_type(d_type
) == nir_type_uint
) {
141 /* The code above sign-extended. If we're lowering an unsigned op,
142 * we need to mask it off to the correct number of bits so that a
143 * cast to uint64_t will do the right thing.
146 d
&= (1ull << bit_size
) - 1;
151 q
[comp
] = build_udiv(b
, n
, d
);
154 q
[comp
] = build_idiv(b
, n
, d
);
157 q
[comp
] = build_umod(b
, n
, d
);
160 unreachable("Unknown integer division op");
164 nir_ssa_def
*qvec
= nir_vec(b
, q
, alu
->dest
.dest
.ssa
.num_components
);
165 nir_ssa_def_rewrite_uses(&alu
->dest
.dest
.ssa
, nir_src_for_ssa(qvec
));
166 nir_instr_remove(&alu
->instr
);
172 nir_opt_idiv_const_impl(nir_function_impl
*impl
, unsigned min_bit_size
)
174 bool progress
= false;
177 nir_builder_init(&b
, impl
);
179 nir_foreach_block(block
, impl
) {
180 nir_foreach_instr_safe(instr
, block
) {
181 if (instr
->type
!= nir_instr_type_alu
)
184 nir_alu_instr
*alu
= nir_instr_as_alu(instr
);
185 if (alu
->op
!= nir_op_udiv
&&
186 alu
->op
!= nir_op_idiv
&&
187 alu
->op
!= nir_op_umod
)
190 assert(alu
->dest
.dest
.is_ssa
);
191 if (alu
->dest
.dest
.ssa
.bit_size
< min_bit_size
)
194 progress
|= nir_opt_idiv_const_instr(&b
, alu
);
199 nir_metadata_preserve(impl
, nir_metadata_block_index
|
200 nir_metadata_dominance
);
207 nir_opt_idiv_const(nir_shader
*shader
, unsigned min_bit_size
)
209 bool progress
= false;
211 nir_foreach_function(function
, shader
) {
213 progress
|= nir_opt_idiv_const_impl(function
->impl
, min_bit_size
);