7 using Id = std::string;
10 Word64(Id low, Id high)
21 Shifted(Word64 shifted, Id lost)
22 : value(std::
move(shifted))
23 , sticky(std::
move(lost))
33 [[nodiscard]] SoftDoubleModule finish(
const SoftDoubleUse& use)
55 out.declarations = declarations();
56 out.functions = std::move(m_text);
60 [[nodiscard]] std::string fft(
const ShaderSpec& spec)
62 const uint32_t points = spec.points;
63 const uint32_t local = spec.workgroup_size[0];
65 while ((1U << stages) < points) {
70 const uint32_t descriptors = spec.descriptors;
71 const std::string& values = spec.bindings[0].name;
72 const std::string& twiddle = spec.bindings[1].name;
73 const std::string& window = spec.bindings[2].name;
74 const std::string& result = spec.bindings[3].name;
75 const std::string weights = projection ? spec.bindings[4].name : std::string {};
81 const auto load_global = [
this](
const std::string& binding,
const Id& index) {
82 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
83 return ins(
"%v2u32",
"OpLoad", { pointer });
85 const auto store_global = [
this](
const std::string& binding,
const Id& index,
const Id& value) {
86 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
87 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
89 const auto load_shared = [
this](std::string_view array,
const Id& index) {
90 const Id pointer = ins(
"%fft_p_sh",
"OpAccessChain", { array, index });
91 return ins(
"%v2u32",
"OpLoad", { pointer });
93 const auto store_shared = [
this](std::string_view array,
const Id& index,
const Id& value) {
94 const Id pointer = ins(
"%fft_p_sh",
"OpAccessChain", { array, index });
95 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
97 const auto mulf = [
this](
const Id& a,
const Id& b) {
100 const auto addf = [
this](
const Id& a,
const Id& b) {
103 const auto negf = [
this](
const Id& a) {
104 const Word64 w = unpack(a);
105 return pair(w.lo, bxor(w.hi, k(2147483648)));
107 const auto selv = [
this](
const Id& condition,
const Id& a,
const Id& b) {
108 const Word64 wa = unpack(a);
109 const Word64 wb = unpack(b);
110 return pair(sel(condition, wa.lo, wb.lo), sel(condition, wa.hi, wb.hi));
112 const auto barrier = [
this] {
113 m_text +=
"OpControlBarrier " + k(2) +
" " + k(2) +
" " + k(264) +
"\n";
115 const auto push_constant = [
this](uint32_t member) {
116 const Id pointer = ins(
"%ppc_u32",
"OpAccessChain", {
"%pc", k(member) });
117 return ins(
"%u32",
"OpLoad", { pointer });
119 const auto bit_reverse = [
this, stages](
const Id& index) {
121 for (uint32_t bit = 0; bit < stages; ++bit) {
122 reversed = bor(reversed, shl(band(shr(index, k(bit)), k(1)), k(stages - 1 - bit)));
127 m_text +=
"%main = OpFunction %void None %voidfn\n";
128 m_text +=
"%entry = OpLabel\n";
130 m_text +=
"%fft_acc = OpVariable %fft_pf_v2 Function\n";
131 m_text +=
"%fft_kidx = OpVariable %fft_pf_u32 Function\n";
134 const Id local_id = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%lid_var" }),
"0" });
135 const Id window_id = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%wgid_var" }),
"0" });
136 const Id length = push_constant(0);
137 const Id stride = push_constant(1);
138 const Id offset = push_constant(2);
139 const Id
scale = pair(push_constant(3), push_constant(4));
140 const Id base = word(
"OpIAdd", offset, word(
"OpIMul", window_id, stride));
141 const Id zero = pair(k(0), k(0));
143 for (uint32_t round = 0; round < points / local; ++round) {
144 const Id index = add(local_id, k(round * local));
145 const Id valid = ult(index, length);
146 const Id element = word(
"OpIMul", add(base, index), k(2));
147 const Id re_index = sel(valid, element, k(0));
148 const Id im_index = sel(valid, add(element, k(1)), k(1));
149 const Id coefficient = load_global(window, index);
150 const Id re = selv(valid, mulf(load_global(values, re_index), coefficient), zero);
151 const Id im = selv(valid, mulf(load_global(values, im_index), coefficient), zero);
152 const Id destination = bit_reverse(index);
153 store_shared(
"%fft_re", destination, re);
154 store_shared(
"%fft_im", destination, im);
158 for (uint32_t stage = 1; stage <= stages; ++stage) {
159 const uint32_t half = 1U << (stage - 1);
160 for (uint32_t round = 0; round < (points / 2) / local; ++round) {
161 const Id pair_index = add(local_id, k(round * local));
162 const Id within = band(pair_index, k(half - 1));
163 const Id first = add(shl(shr(pair_index, k(stage - 1)), k(stage)), within);
164 const Id second = add(first, k(half));
165 const Id twiddle_element = shl(shl(within, k(stages - stage)), k(1));
166 const Id wr = load_global(twiddle, twiddle_element);
167 const Id wi = load_global(twiddle, add(twiddle_element, k(1)));
169 const Id x0r = load_shared(
"%fft_re", first);
170 const Id x0i = load_shared(
"%fft_im", first);
171 const Id x1r = load_shared(
"%fft_re", second);
172 const Id x1i = load_shared(
"%fft_im", second);
174 const Id tr = addf(mulf(wr, x1r), negf(mulf(wi, x1i)));
175 const Id ti = addf(mulf(wr, x1i), mulf(wi, x1r));
177 store_shared(
"%fft_re", first, addf(x0r, tr));
178 store_shared(
"%fft_im", first, addf(x0i, ti));
179 store_shared(
"%fft_re", second, addf(x0r, negf(tr)));
180 store_shared(
"%fft_im", second, addf(x0i, negf(ti)));
186 const uint32_t bins = points / 2 + 1;
187 const uint32_t power_rounds = (bins + local - 1) / local;
188 for (uint32_t round = 0; round < power_rounds; ++round) {
189 const std::string tag = std::to_string(round);
190 const Id bin = add(local_id, k(round * local));
191 const Id inside = ult(bin, k(bins));
192 m_text +=
"OpSelectionMerge %fft_pm" + tag +
" None\n";
193 m_text +=
"OpBranchConditional " + inside +
" %fft_pw" + tag +
" %fft_pm" + tag +
"\n";
194 m_text +=
"%fft_pw" + tag +
" = OpLabel\n";
195 const Id re = mulf(load_shared(
"%fft_re", bin), scale);
196 const Id im = mulf(load_shared(
"%fft_im", bin), scale);
197 store_shared(
"%fft_re", bin, addf(mulf(re, re), mulf(im, im)));
198 m_text +=
"OpBranch %fft_pm" + tag +
"\n";
199 m_text +=
"%fft_pm" + tag +
" = OpLabel\n";
203 const uint32_t rows_rounds = (descriptors + local - 1) / local;
204 const Id result_base = word(
"OpIMul", window_id, k(descriptors));
205 for (uint32_t round = 0; round < rows_rounds; ++round) {
206 const std::string tag = std::to_string(round);
207 const Id row = add(local_id, k(round * local));
208 const Id inside = ult(row, k(descriptors));
209 m_text +=
"OpSelectionMerge %fft_dm" + tag +
" None\n";
210 m_text +=
"OpBranchConditional " + inside +
" %fft_dw" + tag +
" %fft_dm" + tag +
"\n";
211 m_text +=
"%fft_dw" + tag +
" = OpLabel\n";
212 m_text +=
"OpStore %fft_acc " + zero +
"\n";
213 m_text +=
"OpStore %fft_kidx " + k(0) +
"\n";
214 m_text +=
"OpBranch %fft_lh" + tag +
"\n";
215 m_text +=
"%fft_lh" + tag +
" = OpLabel\n";
216 m_text +=
"OpLoopMerge %fft_lm" + tag +
" %fft_lc" + tag +
" None\n";
217 m_text +=
"OpBranch %fft_lt" + tag +
"\n";
218 m_text +=
"%fft_lt" + tag +
" = OpLabel\n";
219 const Id bin_now = ins(
"%u32",
"OpLoad", {
"%fft_kidx" });
220 const Id more = ult(bin_now, k(bins));
221 m_text +=
"OpBranchConditional " + more +
" %fft_lb" + tag +
" %fft_lm" + tag +
"\n";
222 m_text +=
"%fft_lb" + tag +
" = OpLabel\n";
223 const Id weight = load_global(weights, add(word(
"OpIMul", row, k(bins)), bin_now));
224 const Id power_now = load_shared(
"%fft_re", bin_now);
225 const Id running = ins(
"%v2u32",
"OpLoad", {
"%fft_acc" });
226 m_text +=
"OpStore %fft_acc " + addf(running, mulf(weight, power_now)) +
"\n";
227 m_text +=
"OpBranch %fft_lc" + tag +
"\n";
228 m_text +=
"%fft_lc" + tag +
" = OpLabel\n";
229 const Id next = add(ins(
"%u32",
"OpLoad", {
"%fft_kidx" }), k(1));
230 m_text +=
"OpStore %fft_kidx " + next +
"\n";
231 m_text +=
"OpBranch %fft_lh" + tag +
"\n";
232 m_text +=
"%fft_lm" + tag +
" = OpLabel\n";
233 store_global(result, add(result_base, row), ins(
"%v2u32",
"OpLoad", {
"%fft_acc" }));
234 m_text +=
"OpBranch %fft_dm" + tag +
"\n";
235 m_text +=
"%fft_dm" + tag +
" = OpLabel\n";
238 const Id out_base = word(
"OpIMul", window_id, k(points * 2));
239 for (uint32_t round = 0; round < points / local; ++round) {
240 const Id bin = add(local_id, k(round * local));
241 const Id re = mulf(load_shared(
"%fft_re", bin), scale);
242 const Id im = mulf(load_shared(
"%fft_im", bin), scale);
243 const Id element = add(out_base, shl(bin, k(1)));
244 store_global(result, element, re);
245 store_global(result, add(element, k(1)), im);
248 const uint32_t bins = points / 2 + 1;
249 const uint32_t rounds = (bins + local - 1) / local;
250 const Id out_base = word(
"OpIMul", window_id, k(bins));
251 for (uint32_t round = 0; round < rounds; ++round) {
252 const std::string tag = std::to_string(round);
253 const Id bin = add(local_id, k(round * local));
254 const Id inside = ult(bin, k(bins));
255 m_text +=
"OpSelectionMerge %fft_pm" + tag +
" None\n";
256 m_text +=
"OpBranchConditional " + inside +
" %fft_pw" + tag +
" %fft_pm" + tag +
"\n";
257 m_text +=
"%fft_pw" + tag +
" = OpLabel\n";
258 const Id re = mulf(load_shared(
"%fft_re", bin), scale);
259 const Id im = mulf(load_shared(
"%fft_im", bin), scale);
260 store_global(result, add(out_base, bin), addf(mulf(re, re), mulf(im, im)));
261 m_text +=
"OpBranch %fft_pm" + tag +
"\n";
262 m_text +=
"%fft_pm" + tag +
" = OpLabel\n";
266 m_text +=
"OpReturn\n";
267 m_text +=
"OpFunctionEnd\n";
270 globals +=
"%lid_var = OpVariable %ptr_in_v3u32 Input\n";
271 globals +=
"%wgid_var = OpVariable %ptr_in_v3u32 Input\n";
272 globals +=
"%fft_arr_t = OpTypeArray %v2u32 %sd_k" + std::to_string(points) +
"\n";
273 globals +=
"%fft_p_arr = OpTypePointer Workgroup %fft_arr_t\n";
274 globals +=
"%fft_re = OpVariable %fft_p_arr Workgroup\n";
275 globals +=
"%fft_im = OpVariable %fft_p_arr Workgroup\n";
276 globals +=
"%fft_p_sh = OpTypePointer Workgroup %v2u32\n";
278 globals +=
"%fft_pf_v2 = OpTypePointer Function %v2u32\n";
279 globals +=
"%fft_pf_u32 = OpTypePointer Function %u32\n";
282 return declarations() + globals + m_text;
285 [[nodiscard]] std::string lagged_pair(
const ShaderSpec& spec)
287 const uint32_t local = spec.workgroup_size[0];
288 const bool centred = spec.centred;
290 const std::string& values = spec.bindings[0].name;
291 const std::string& result = spec.bindings[1].name;
302 const auto load_global = [
this](
const std::string& binding,
const Id& index) {
303 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
304 return ins(
"%v2u32",
"OpLoad", { pointer });
306 const auto store_global = [
this](
const std::string& binding,
const Id& index,
const Id& value) {
307 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
308 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
310 const auto load_shared = [
this](
const Id& index) {
311 const Id pointer = ins(
"%lp_p_sh",
"OpAccessChain", {
"%lp_shared", index });
312 return ins(
"%v2u32",
"OpLoad", { pointer });
314 const auto store_shared = [
this](
const Id& index,
const Id& value) {
315 const Id pointer = ins(
"%lp_p_sh",
"OpAccessChain", {
"%lp_shared", index });
316 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
318 const auto mulf = [
this](
const Id& a,
const Id& b) {
321 const auto addf = [
this](
const Id& a,
const Id& b) {
324 const auto divf = [
this](
const Id& a,
const Id& b) {
327 const auto negf = [
this](
const Id& a) {
328 const Word64 w = unpack(a);
329 return pair(w.lo, bxor(w.hi, k(2147483648)));
331 const auto barrier = [
this] {
332 m_text +=
"OpControlBarrier " + k(2) +
" " + k(2) +
" " + k(264) +
"\n";
334 const auto push_constant = [
this](uint32_t member) {
335 const Id pointer = ins(
"%ppc_u32",
"OpAccessChain", {
"%pc", k(member) });
336 return ins(
"%u32",
"OpLoad", { pointer });
338 const auto non_negative = [
this](
const Id& value) {
339 const Word64 w = unpack(value);
340 const Id all_ones = eq(band(shr(w.hi, k(20)), k(2047)), k(2047));
341 const Id nan = land(all_ones, ne(bor(band(w.hi, k(1048575)), w.lo), k(0)));
342 const Id sign_clear = eq(band(w.hi, k(2147483648)), k(0));
343 const Id zero_value = eq(bor(shl(w.hi, k(1)), w.lo), k(0));
344 return lor(zero_value, land(sign_clear, ins(
"%bool",
"OpLogicalNot", { nan })));
347 m_text +=
"%main = OpFunction %void None %voidfn\n";
348 m_text +=
"%entry = OpLabel\n";
349 m_text +=
"%lp_acc = OpVariable %lp_pf_v2 Function\n";
350 m_text +=
"%lp_k = OpVariable %lp_pf_u32 Function\n";
352 const Id local_id = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%lid_var" }),
"0" });
353 const Id group = ins(
"%v3u32",
"OpLoad", {
"%wgid_var" });
354 const Id lag_slot = ins(
"%u32",
"OpCompositeExtract", { group,
"0" });
355 const Id window_id = ins(
"%u32",
"OpCompositeExtract", { group,
"1" });
356 const Id length = push_constant(0);
357 const Id stride = push_constant(1);
358 const Id offset = push_constant(2);
359 const Id first_lag = push_constant(3);
360 const Id lag_count = push_constant(4);
361 const Id length_value = pair(push_constant(5), push_constant(6));
362 const Id lag = add(first_lag, lag_slot);
363 const Id base = add(offset, word(
"OpIMul", window_id, stride));
364 const Id terms = sel(ult(lag, length), sub(length, lag), k(0));
365 const Id zero = pair(k(0), k(0));
367 uint32_t counter = 0;
368 const auto accumulate = [&](
const Id& bound,
const auto& element) {
369 const std::string tag = std::to_string(counter++);
370 m_text +=
"OpStore %lp_acc " + zero +
"\n";
371 m_text +=
"OpStore %lp_k " + local_id +
"\n";
372 m_text +=
"OpBranch %lp_h" + tag +
"\n";
373 m_text +=
"%lp_h" + tag +
" = OpLabel\n";
374 m_text +=
"OpLoopMerge %lp_m" + tag +
" %lp_c" + tag +
" None\n";
375 m_text +=
"OpBranch %lp_t" + tag +
"\n";
376 m_text +=
"%lp_t" + tag +
" = OpLabel\n";
377 const Id index = ins(
"%u32",
"OpLoad", {
"%lp_k" });
378 m_text +=
"OpBranchConditional " + ult(index, bound) +
" %lp_b" + tag +
" %lp_m" + tag +
"\n";
379 m_text +=
"%lp_b" + tag +
" = OpLabel\n";
380 const Id term = element(index);
381 const Id running = ins(
"%v2u32",
"OpLoad", {
"%lp_acc" });
382 m_text +=
"OpStore %lp_acc " + addf(running, term) +
"\n";
383 m_text +=
"OpBranch %lp_c" + tag +
"\n";
384 m_text +=
"%lp_c" + tag +
" = OpLabel\n";
385 const Id next = add(ins(
"%u32",
"OpLoad", {
"%lp_k" }), k(local));
386 m_text +=
"OpStore %lp_k " + next +
"\n";
387 m_text +=
"OpBranch %lp_h" + tag +
"\n";
388 m_text +=
"%lp_m" + tag +
" = OpLabel\n";
392 store_shared(local_id, ins(
"%v2u32",
"OpLoad", {
"%lp_acc" }));
394 for (uint32_t span = local / 2; span >= 1; span /= 2) {
395 const std::string tag = std::to_string(counter++);
396 const Id active = ult(local_id, k(span));
397 m_text +=
"OpSelectionMerge %lp_sm" + tag +
" None\n";
398 m_text +=
"OpBranchConditional " + active +
" %lp_sw" + tag +
" %lp_sm" + tag +
"\n";
399 m_text +=
"%lp_sw" + tag +
" = OpLabel\n";
400 const Id own = load_shared(local_id);
401 const Id partner = load_shared(add(local_id, k(span)));
402 store_shared(local_id, addf(own, partner));
403 m_text +=
"OpBranch %lp_sm" + tag +
"\n";
404 m_text +=
"%lp_sm" + tag +
" = OpLabel\n";
409 Id negative_mean = zero;
411 accumulate(length, [&](
const Id& index) {
return load_global(values, add(base, index)); });
413 negative_mean = negf(divf(load_shared(k(0)), length_value));
417 accumulate(terms, [&](
const Id& index) {
418 const Id first_index = add(base, index);
419 Id a = load_global(values, first_index);
420 Id b = load_global(values, add(first_index, lag));
422 a = addf(a, negative_mean);
423 b = addf(b, negative_mean);
427 const Id differs = test(
"OpLogicalNotEqual", non_negative(a), non_negative(b));
428 return pair(k(0), sel(differs, k(1072693248), k(0)));
431 const Word64 d = unpack(addf(a, negf(b)));
432 return pair(d.lo, band(d.hi, k(2147483647)));
441 const Id first_invocation = eq(local_id, k(0));
442 m_text +=
"OpSelectionMerge %lp_wm None\n";
443 m_text +=
"OpBranchConditional " + first_invocation +
" %lp_ww %lp_wm\n";
444 m_text +=
"%lp_ww = OpLabel\n";
445 store_global(result, add(word(
"OpIMul", window_id, lag_count), lag_slot), load_shared(k(0)));
446 m_text +=
"OpBranch %lp_wm\n";
447 m_text +=
"%lp_wm = OpLabel\n";
448 m_text +=
"OpReturn\n";
449 m_text +=
"OpFunctionEnd\n";
452 globals +=
"%lid_var = OpVariable %ptr_in_v3u32 Input\n";
453 globals +=
"%wgid_var = OpVariable %ptr_in_v3u32 Input\n";
454 globals +=
"%lp_arr_t = OpTypeArray %v2u32 %sd_k" + std::to_string(local) +
"\n";
455 globals +=
"%lp_p_arr = OpTypePointer Workgroup %lp_arr_t\n";
456 globals +=
"%lp_shared = OpVariable %lp_p_arr Workgroup\n";
457 globals +=
"%lp_p_sh = OpTypePointer Workgroup %v2u32\n";
458 globals +=
"%lp_pf_v2 = OpTypePointer Function %v2u32\n";
459 globals +=
"%lp_pf_u32 = OpTypePointer Function %u32\n";
461 return declarations() + globals + m_text;
464 [[nodiscard]] std::string word_pair_map(
const ShaderSpec& spec)
466 const uint32_t local = spec.workgroup_size[0];
469 const std::string& first = spec.bindings[0].name;
470 const std::string& second = unary ? first : spec.bindings[1].name;
471 const std::string& result = spec.bindings.back().name;
497 const auto load_global = [
this](
const std::string& binding,
const Id& index) {
498 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
499 return ins(
"%v2u32",
"OpLoad", { pointer });
502 m_text +=
"%main = OpFunction %void None %voidfn\n";
503 m_text +=
"%entry = OpLabel\n";
504 const Id local_id = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%lid_var" }),
"0" });
505 const Id group = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%wgid_var" }),
"0" });
506 const Id
count = ins(
"%u32",
"OpLoad", { ins(
"%ppc_u32",
"OpAccessChain", {
"%pc", k(0) }) });
507 const Id index = add(word(
"OpIMul", group, k(local)), local_id);
509 const Id inside = ult(index, count);
510 m_text +=
"OpSelectionMerge %wm_end None\n";
511 m_text +=
"OpBranchConditional " + inside +
" %wm_body %wm_end\n";
512 m_text +=
"%wm_body = OpLabel\n";
513 const Id a = load_global(first, index);
514 const Id b = unary ? a : load_global(second, index);
516 ? ins(
"%f32",
"OpBitcast", { ins(
"%u32",
"OpFunctionCall", { function, a, b }) })
517 : ins(
"%v2u32",
"OpFunctionCall", { function, a, b });
518 const Id pointer = ins(
"%pelem_" + result,
"OpAccessChain", {
"%buf_" + result,
"%c0u", index });
519 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
520 m_text +=
"OpBranch %wm_end\n";
521 m_text +=
"%wm_end = OpLabel\n";
522 m_text +=
"OpReturn\n";
523 m_text +=
"OpFunctionEnd\n";
526 globals +=
"%lid_var = OpVariable %ptr_in_v3u32 Input\n";
527 globals +=
"%wgid_var = OpVariable %ptr_in_v3u32 Input\n\n";
528 return declarations() + globals + m_text;
531 [[nodiscard]] std::string segmented_argmax(
const ShaderSpec& spec)
533 const uint32_t local = spec.workgroup_size[0];
534 const std::string& values = spec.bindings[0].name;
535 const std::string& result = spec.bindings[1].name;
539 const auto load_global = [
this](
const std::string& binding,
const Id& index) {
540 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
541 return ins(
"%v2u32",
"OpLoad", { pointer });
543 const auto store_global = [
this](
const std::string& binding,
const Id& index,
const Id& value) {
544 const Id pointer = ins(
"%pelem_" + binding,
"OpAccessChain", {
"%buf_" + binding,
"%c0u", index });
545 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
547 const auto load_value = [
this](
const Id& index) {
548 const Id pointer = ins(
"%am_p_sh_v2",
"OpAccessChain", {
"%am_shared_v", index });
549 return ins(
"%v2u32",
"OpLoad", { pointer });
551 const auto store_value = [
this](
const Id& index,
const Id& value) {
552 const Id pointer = ins(
"%am_p_sh_v2",
"OpAccessChain", {
"%am_shared_v", index });
553 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
555 const auto load_at = [
this](
const Id& index) {
556 const Id pointer = ins(
"%am_p_sh_u32",
"OpAccessChain", {
"%am_shared_i", index });
557 return ins(
"%u32",
"OpLoad", { pointer });
559 const auto store_at = [
this](
const Id& index,
const Id& value) {
560 const Id pointer = ins(
"%am_p_sh_u32",
"OpAccessChain", {
"%am_shared_i", index });
561 m_text +=
"OpStore " + pointer +
" " + value +
"\n";
563 const auto push_constant = [
this](uint32_t member) {
564 const Id pointer = ins(
"%ppc_u32",
"OpAccessChain", {
"%pc", k(member) });
565 return ins(
"%u32",
"OpLoad", { pointer });
567 const auto barrier = [
this] {
568 m_text +=
"OpControlBarrier " + k(2) +
" " + k(2) +
" " + k(264) +
"\n";
570 const auto choose = [
this](
const Id& condition,
const Id& a,
const Id& b) {
571 const Word64 wa = unpack(a);
572 const Word64 wb = unpack(b);
573 return pair(sel(condition, wa.lo, wb.lo), sel(condition, wa.hi, wb.hi));
576 m_text +=
"%main = OpFunction %void None %voidfn\n";
577 m_text +=
"%entry = OpLabel\n";
578 m_text +=
"%am_best = OpVariable %am_pf_v2 Function\n";
579 m_text +=
"%am_at = OpVariable %am_pf_u32 Function\n";
580 m_text +=
"%am_k = OpVariable %am_pf_u32 Function\n";
582 const Id local_id = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%lid_var" }),
"0" });
583 const Id segment = ins(
"%u32",
"OpCompositeExtract", { ins(
"%v3u32",
"OpLoad", {
"%wgid_var" }),
"0" });
584 const Id length = push_constant(0);
585 const Id stride = push_constant(1);
586 const Id offset = push_constant(2);
587 const Id base = add(offset, word(
"OpIMul", segment, stride));
589 m_text +=
"OpStore %am_best " + pair(k(0), k(2146959360)) +
"\n";
590 m_text +=
"OpStore %am_at " + k(4294967295) +
"\n";
591 m_text +=
"OpStore %am_k " + local_id +
"\n";
592 m_text +=
"OpBranch %am_h\n";
593 m_text +=
"%am_h = OpLabel\n";
594 m_text +=
"OpLoopMerge %am_m %am_c None\n";
595 m_text +=
"OpBranch %am_t\n";
596 m_text +=
"%am_t = OpLabel\n";
597 const Id index = ins(
"%u32",
"OpLoad", {
"%am_k" });
598 const Id more = ult(index, length);
599 m_text +=
"OpBranchConditional " + more +
" %am_b %am_m\n";
600 m_text +=
"%am_b = OpLabel\n";
601 const Id element = load_global(values, add(base, index));
602 const Id current = ins(
"%v2u32",
"OpLoad", {
"%am_best" });
603 const Id take = ult64(argmax_key(unpack(current)), argmax_key(unpack(element)));
604 m_text +=
"OpStore %am_best " + choose(take, element, current) +
"\n";
605 m_text +=
"OpStore %am_at " + sel(take, index, ins(
"%u32",
"OpLoad", {
"%am_at" })) +
"\n";
606 m_text +=
"OpBranch %am_c\n";
607 m_text +=
"%am_c = OpLabel\n";
608 const Id next = add(ins(
"%u32",
"OpLoad", {
"%am_k" }), k(local));
609 m_text +=
"OpStore %am_k " + next +
"\n";
610 m_text +=
"OpBranch %am_h\n";
611 m_text +=
"%am_m = OpLabel\n";
613 store_value(local_id, ins(
"%v2u32",
"OpLoad", {
"%am_best" }));
614 store_at(local_id, ins(
"%u32",
"OpLoad", {
"%am_at" }));
617 uint32_t counter = 0;
618 for (uint32_t span = local / 2; span >= 1; span /= 2) {
619 const std::string tag = std::to_string(counter++);
620 const Id active = ult(local_id, k(span));
621 m_text +=
"OpSelectionMerge %am_sm" + tag +
" None\n";
622 m_text +=
"OpBranchConditional " + active +
" %am_sw" + tag +
" %am_sm" + tag +
"\n";
623 m_text +=
"%am_sw" + tag +
" = OpLabel\n";
624 const Id partner_slot = add(local_id, k(span));
625 const Id own = load_value(local_id);
626 const Id other = load_value(partner_slot);
627 const Id own_at = load_at(local_id);
628 const Id other_at = load_at(partner_slot);
629 const Word64 own_key = argmax_key(unpack(own));
630 const Word64 other_key = argmax_key(unpack(other));
631 const Id tied = land(eq(own_key.hi, other_key.hi), eq(own_key.lo, other_key.lo));
632 const Id replace = lor(ult64(own_key, other_key), land(tied, ult(other_at, own_at)));
633 store_value(local_id, choose(replace, other, own));
634 store_at(local_id, sel(replace, other_at, own_at));
635 m_text +=
"OpBranch %am_sm" + tag +
"\n";
636 m_text +=
"%am_sm" + tag +
" = OpLabel\n";
640 const Id first = eq(local_id, k(0));
641 m_text +=
"OpSelectionMerge %am_wm None\n";
642 m_text +=
"OpBranchConditional " + first +
" %am_ww %am_wm\n";
643 m_text +=
"%am_ww = OpLabel\n";
644 const Id slot = shl(segment, k(1));
645 store_global(result, slot, load_value(k(0)));
646 store_global(result, add(slot, k(1)), pair(load_at(k(0)), k(0)));
647 m_text +=
"OpBranch %am_wm\n";
648 m_text +=
"%am_wm = OpLabel\n";
649 m_text +=
"OpReturn\n";
650 m_text +=
"OpFunctionEnd\n";
653 globals +=
"%lid_var = OpVariable %ptr_in_v3u32 Input\n";
654 globals +=
"%wgid_var = OpVariable %ptr_in_v3u32 Input\n";
655 globals +=
"%am_arr_v = OpTypeArray %v2u32 %sd_k" + std::to_string(local) +
"\n";
656 globals +=
"%am_arr_i = OpTypeArray %u32 %sd_k" + std::to_string(local) +
"\n";
657 globals +=
"%am_p_arr_v = OpTypePointer Workgroup %am_arr_v\n";
658 globals +=
"%am_p_arr_i = OpTypePointer Workgroup %am_arr_i\n";
659 globals +=
"%am_shared_v = OpVariable %am_p_arr_v Workgroup\n";
660 globals +=
"%am_shared_i = OpVariable %am_p_arr_i Workgroup\n";
661 globals +=
"%am_p_sh_v2 = OpTypePointer Workgroup %v2u32\n";
662 globals +=
"%am_p_sh_u32 = OpTypePointer Workgroup %u32\n";
663 globals +=
"%am_pf_v2 = OpTypePointer Function %v2u32\n";
664 globals +=
"%am_pf_u32 = OpTypePointer Function %u32\n";
666 return declarations() + globals + m_text;
671 std::set<uint32_t> m_constants;
672 uint32_t m_next { 0 };
674 [[nodiscard]] std::string declarations()
const
677 out +=
"%sd_pair = OpTypeStruct %u32 %u32\n";
678 out +=
"%sd_fn_bin = OpTypeFunction %v2u32 %v2u32 %v2u32\n";
679 out +=
"%sd_fn_less = OpTypeFunction %bool %v2u32 %v2u32\n";
680 out +=
"%sd_fn_tof32 = OpTypeFunction %u32 %v2u32 %v2u32\n";
681 for (
const uint32_t value : m_constants) {
682 out +=
"%sd_k" + std::to_string(value) +
" = OpConstant %u32 " + std::to_string(value) +
"\n";
689 m_constants.insert(value);
690 return "%sd_k" + std::to_string(value);
693 Id ins(std::string_view type, std::string_view opcode, std::initializer_list<std::string_view> args)
695 Id
id =
"%sd" + std::to_string(m_next++);
696 m_text +=
id +
" = " + std::string(opcode) +
" " + std::string(type);
697 for (
const auto& arg : args) {
705 Id word(std::string_view opcode,
const Id& a,
const Id& b) {
return ins(
"%u32", opcode, { a, b }); }
706 Id test(std::string_view opcode,
const Id& a,
const Id& b) {
return ins(
"%bool", opcode, { a, b }); }
708 Id add(
const Id& a,
const Id& b) {
return word(
"OpIAdd", a, b); }
709 Id sub(
const Id& a,
const Id& b) {
return word(
"OpISub", a, b); }
710 Id band(
const Id& a,
const Id& b) {
return word(
"OpBitwiseAnd", a, b); }
711 Id bor(
const Id& a,
const Id& b) {
return word(
"OpBitwiseOr", a, b); }
712 Id bxor(
const Id& a,
const Id& b) {
return word(
"OpBitwiseXor", a, b); }
713 Id bnot(
const Id& a) {
return ins(
"%u32",
"OpNot", { a }); }
714 Id shl(
const Id& a,
const Id& n) {
return word(
"OpShiftLeftLogical", a, n); }
715 Id shr(
const Id& a,
const Id& n) {
return word(
"OpShiftRightLogical", a, n); }
716 Id umin(
const Id& a,
const Id& b) {
return ins(
"%u32",
"OpExtInst", {
"%glsl",
"UMin", a, b }); }
717 Id umax(
const Id& a,
const Id& b) {
return ins(
"%u32",
"OpExtInst", {
"%glsl",
"UMax", a, b }); }
718 Id msb(
const Id& a) {
return ins(
"%u32",
"OpExtInst", {
"%glsl",
"FindUMsb", a }); }
720 Id eq(
const Id& a,
const Id& b) {
return test(
"OpIEqual", a, b); }
721 Id ne(
const Id& a,
const Id& b) {
return test(
"OpINotEqual", a, b); }
722 Id ult(
const Id& a,
const Id& b) {
return test(
"OpULessThan", a, b); }
723 Id uge(
const Id& a,
const Id& b) {
return test(
"OpUGreaterThanEqual", a, b); }
724 Id sle(
const Id& a,
const Id& b) {
return test(
"OpSLessThanEqual", a, b); }
725 Id sge(
const Id& a,
const Id& b) {
return test(
"OpSGreaterThanEqual", a, b); }
726 Id land(
const Id& a,
const Id& b) {
return test(
"OpLogicalAnd", a, b); }
727 Id lor(
const Id& a,
const Id& b) {
return test(
"OpLogicalOr", a, b); }
729 Id sel(
const Id& c,
const Id& a,
const Id& b) {
return ins(
"%u32",
"OpSelect", { c, a, b }); }
730 Id bsel(
const Id& c,
const Id& a,
const Id& b) {
return ins(
"%bool",
"OpSelect", { c, a, b }); }
732 Id pair(
const Id& lo,
const Id& hi) {
return ins(
"%v2u32",
"OpCompositeConstruct", { lo, hi }); }
734 Word64 unpack(
const Id& v)
736 return { ins(
"%u32",
"OpCompositeExtract", { v,
"0" }), ins(
"%u32",
"OpCompositeExtract", { v,
"1" }) };
739 Word64 select64(
const Id& c,
const Word64& a,
const Word64& b)
741 return { sel(c, a.lo, b.lo), sel(c, a.hi, b.hi) };
744 Id shl_safe(
const Id& a,
const Id& n)
746 return sel(ult(n, k(32)), shl(a, umin(n, k(31))), k(0));
749 Id shr_safe(
const Id& a,
const Id& n)
751 return sel(ult(n, k(32)), shr(a, umin(n, k(31))), k(0));
754 Word64 shl64(
const Word64& w,
const Id& n)
756 const Id narrow_hi = bor(shl_safe(w.hi, n), shr_safe(w.lo, sub(k(32), n)));
757 const Id narrow_lo = shl_safe(w.lo, n);
758 const Id wide_hi = shl_safe(w.lo, sub(n, k(32)));
759 const Id wide = uge(n, k(32));
760 return { sel(wide, k(0), narrow_lo), sel(wide, wide_hi, narrow_hi) };
763 Word64 shr64(
const Word64& w,
const Id& n)
765 const Id narrow_lo = bor(shr_safe(w.lo, n), shl_safe(w.hi, sub(k(32), n)));
766 const Id narrow_hi = shr_safe(w.hi, n);
767 const Id wide_lo = shr_safe(w.hi, sub(n, k(32)));
768 const Id wide = uge(n, k(32));
769 return { sel(wide, wide_lo, narrow_lo), sel(wide, k(0), narrow_hi) };
772 Shifted shr64_sticky(
const Word64& w,
const Id& n)
774 Word64 value = shr64(w, n);
775 const Word64 lost = shl64(w, sub(k(64), umin(n, k(64))));
776 return { std::move(value), lor(ne(lost.lo, k(0)), ne(lost.hi, k(0))) };
779 Word64 add64(
const Word64& a,
const Word64& b)
781 const Id lo = add(a.lo, b.lo);
782 const Id carry = sel(ult(lo, a.lo), k(1), k(0));
783 return { lo, add(add(a.hi, b.hi), carry) };
786 Word64 sub64(
const Word64& a,
const Word64& b)
788 const Id lo = sub(a.lo, b.lo);
789 const Id borrow = sel(ult(a.lo, b.lo), k(1), k(0));
790 return { lo, sub(sub(a.hi, b.hi), borrow) };
793 Id ult64(
const Word64& a,
const Word64& b)
795 return lor(ult(a.hi, b.hi), land(eq(a.hi, b.hi), ult(a.lo, b.lo)));
798 Id lnot(
const Id& a) {
return ins(
"%bool",
"OpLogicalNot", { a }); }
800 Word64 shl1(
const Word64& w)
802 return { shl(w.lo, k(1)), bor(shl(w.hi, k(1)), shr(w.lo, k(31))) };
805 Id nonzero64(
const Word64& w) {
return lor(ne(w.lo, k(0)), ne(w.hi, k(0))); }
807 Id msb64(
const Word64& w)
809 return sel(ne(w.hi, k(0)), add(k(32), msb(w.hi)), msb(w.lo));
812 Word64 mul32(
const Id& a,
const Id& b)
814 const Id product = ins(
"%sd_pair",
"OpUMulExtended", { a, b });
815 return { ins(
"%u32",
"OpCompositeExtract", { product,
"0" }), ins(
"%u32",
"OpCompositeExtract", { product,
"1" }) };
818 void begin(std::string_view name, std::string_view result, std::string_view function_type)
820 const std::string base =
"%sd_f64_" + std::string(name);
821 m_text += base +
" = OpFunction " + std::string(result) +
" None " + std::string(function_type) +
"\n";
822 m_text += base +
"_a = OpFunctionParameter %v2u32\n";
823 m_text += base +
"_b = OpFunctionParameter %v2u32\n";
824 m_text += base +
"_entry = OpLabel\n";
827 void end(
const Id& value)
829 m_text +=
"OpReturnValue " + value +
"\n";
830 m_text +=
"OpFunctionEnd\n\n";
833 Id round_pack(
const Id& sign,
const Id& e,
const Word64& m,
const Id& sticky)
835 const Id subnormal = sle(e, k(0));
836 const Shifted down = shr64_sticky(m, sub(k(1), e));
837 const Word64 m1 = select64(subnormal, down.value, m);
838 const Id st1 = bsel(subnormal, lor(sticky, down.sticky), sticky);
839 const Id e1 = sel(subnormal, k(1), e);
841 const Id half = ne(band(m1.lo, k(512)), k(0));
842 const Id below = lor(ne(band(m1.lo, k(511)), k(0)), st1);
843 const Id odd = ne(band(m1.lo, k(1024)), k(0));
844 const Id up = land(half, lor(below, odd));
845 const Word64 m2 = add64(m1, Word64 { sel(up, k(1024), k(0)), k(0) });
847 const Id mant_lo = bor(shr(m2.lo, k(10)), shl(m2.hi, k(22)));
848 const Id mant_hi = shr(m2.hi, k(10));
849 const Id grew = ne(band(mant_hi, k(2097152)), k(0));
850 const Id lo2 = sel(grew, bor(shr(mant_lo, k(1)), shl(mant_hi, k(31))), mant_lo);
851 const Id hi2 = sel(grew, shr(mant_hi, k(1)), mant_hi);
852 const Id e2 = sel(grew, add(e1, k(1)), e1);
854 const Id hidden = ne(band(hi2, k(1048576)), k(0));
855 const Id field = sel(hidden, e2, k(0));
856 const Id overflow = sge(e2, k(2047));
857 const Id hi_norm = bor(bor(sign, shl(field, k(20))), band(hi2, k(1048575)));
858 const Id hi_out = sel(overflow, bor(sign, k(2146435072)), hi_norm);
859 const Id lo_out = sel(overflow, k(0), lo2);
860 return pair(lo_out, hi_out);
865 begin(
"add",
"%v2u32",
"%sd_fn_bin");
866 const Word64 wa = unpack(
"%sd_f64_add_a");
867 const Word64 wb = unpack(
"%sd_f64_add_b");
869 const Id ea_raw = band(shr(wa.hi, k(20)), k(2047));
870 const Id eb_raw = band(shr(wb.hi, k(20)), k(2047));
871 const Id fa = bor(band(wa.hi, k(1048575)), wa.lo);
872 const Id fb = bor(band(wb.hi, k(1048575)), wb.lo);
873 const Id a_max = eq(ea_raw, k(2047));
874 const Id b_max = eq(eb_raw, k(2047));
875 const Id a_nan = land(a_max, ne(fa, k(0)));
876 const Id b_nan = land(b_max, ne(fb, k(0)));
877 const Id a_inf = land(a_max, eq(fa, k(0)));
878 const Id b_inf = land(b_max, eq(fb, k(0)));
879 const Id sa = band(wa.hi, k(2147483648));
880 const Id sb = band(wb.hi, k(2147483648));
881 const Id invalid = lor(lor(a_nan, b_nan), land(land(a_inf, b_inf), ne(sa, sb)));
882 const Id special = lor(a_max, b_max);
883 const Id inf_lo = sel(a_inf, wa.lo, wb.lo);
884 const Id inf_hi = sel(a_inf, wa.hi, wb.hi);
885 const Id special_lo = sel(invalid, k(0), inf_lo);
886 const Id special_hi = sel(invalid, k(2146959360), inf_hi);
888 const Word64 mag_a { wa.lo, band(wa.hi, k(2147483647)) };
889 const Word64 mag_b { wb.lo, band(wb.hi, k(2147483647)) };
890 const Id a_smaller = ult64(mag_a, mag_b);
891 const Word64 x { sel(a_smaller, wb.lo, wa.lo), sel(a_smaller, wb.hi, wa.hi) };
892 const Word64 y { sel(a_smaller, wa.lo, wb.lo), sel(a_smaller, wa.hi, wb.hi) };
893 const Id sx = band(x.hi, k(2147483648));
894 const Id sy = band(y.hi, k(2147483648));
895 const Id ex_raw = band(shr(x.hi, k(20)), k(2047));
896 const Id ey_raw = band(shr(y.hi, k(20)), k(2047));
897 const Id ex = umax(ex_raw, k(1));
898 const Id ey = umax(ey_raw, k(1));
899 const Word64 mx_raw { x.lo, bor(band(x.hi, k(1048575)), sel(ne(ex_raw, k(0)), k(1048576), k(0))) };
900 const Word64 my_raw { y.lo, bor(band(y.hi, k(1048575)), sel(ne(ey_raw, k(0)), k(1048576), k(0))) };
901 const Word64 mx = shl64(mx_raw, k(10));
902 const Word64 my_full = shl64(my_raw, k(10));
903 const Shifted aligned = shr64_sticky(my_full, sub(ex, ey));
905 const Id same = eq(sx, sy);
906 const Word64
sum = add64(mx, aligned.value);
907 const Word64 diff = sub64(sub64(mx, aligned.value), Word64 { sel(aligned.sticky, k(1), k(0)), k(0) });
908 const Word64 m = select64(same, sum, diff);
909 const Id is_zero = land(eq(m.lo, k(0)), eq(m.hi, k(0)));
910 const Id zero_sign = sel(same, sx, k(0));
912 const Id p = msb64(m);
913 const Id carried = eq(p, k(63));
914 const Shifted halved = shr64_sticky(m, k(1));
915 const Id left = sel(ult(p, k(62)), umin(sub(k(62), p), sub(ex, k(1))), k(0));
916 const Word64 lifted = shl64(m, left);
917 const Word64 norm = select64(carried, halved.value, lifted);
918 const Id e = sel(carried, add(ex, k(1)), sub(ex, left));
919 const Id sticky = bsel(carried, lor(aligned.sticky, halved.sticky), aligned.sticky);
920 const Word64 packed = unpack(round_pack(sx, e, norm, sticky));
922 const Id finite_lo = sel(is_zero, k(0), packed.lo);
923 const Id finite_hi = sel(is_zero, zero_sign, packed.hi);
924 end(pair(sel(special, special_lo, finite_lo), sel(special, special_hi, finite_hi)));
935 Unpacked unpack_normalised(
const Word64& w)
937 const Id e_raw = band(shr(w.hi, k(20)), k(2047));
938 const Id frac = bor(band(w.hi, k(1048575)), w.lo);
939 const Id max_exp = eq(e_raw, k(2047));
940 const Word64 mant { w.lo, bor(band(w.hi, k(1048575)), sel(ne(e_raw, k(0)), k(1048576), k(0))) };
941 const Id lead = sub(k(52), msb64(mant));
942 Word64 normalised = shl64(mant, lead);
943 Id exponent = sub(umax(e_raw, k(1)), lead);
944 Id zero = land(eq(e_raw, k(0)), eq(frac, k(0)));
945 Id inf = land(max_exp, eq(frac, k(0)));
946 Id nan = land(max_exp, ne(frac, k(0)));
948 .mant = std::move(normalised),
949 .exp = std::move(exponent),
950 .is_zero = std::move(zero),
951 .is_inf = std::move(inf),
952 .is_nan = std::move(nan)
958 begin(
"mul",
"%v2u32",
"%sd_fn_bin");
959 const Word64 wa = unpack(
"%sd_f64_mul_a");
960 const Word64 wb = unpack(
"%sd_f64_mul_b");
961 const Unpacked a = unpack_normalised(wa);
962 const Unpacked b = unpack_normalised(wb);
964 const Id sign = band(bxor(wa.hi, wb.hi), k(2147483648));
965 const Id invalid = lor(lor(a.is_nan, b.is_nan), lor(land(a.is_inf, b.is_zero), land(b.is_inf, a.is_zero)));
966 const Id inf = lor(a.is_inf, b.is_inf);
967 const Id zero = lor(a.is_zero, b.is_zero);
969 const Word64 p0 = mul32(a.mant.lo, b.mant.lo);
970 const Word64 p1 = mul32(a.mant.hi, b.mant.lo);
971 const Word64 p2 = mul32(a.mant.lo, b.mant.hi);
972 const Word64 p3 = mul32(a.mant.hi, b.mant.hi);
973 const Word64 cross = add64(p1, p2);
974 const Word64 middle = add64(Word64 { p0.hi, k(0) }, Word64 { cross.lo, k(0) });
975 const Word64 upper = add64(add64(p3, Word64 { cross.hi, k(0) }), Word64 { middle.hi, k(0) });
977 const Id r1 = middle.lo;
978 const Id r2 = upper.lo;
979 const Id r3 = upper.hi;
981 const Id big = ne(band(shr(r3, k(9)), k(1)), k(0));
982 const Word64 m42 { bor(shr(r1, k(10)), shl(r2, k(22))), bor(shr(r2, k(10)), shl(r3, k(22))) };
983 const Word64 m43 { bor(shr(r1, k(11)), shl(r2, k(21))), bor(shr(r2, k(11)), shl(r3, k(21))) };
984 const Id st42 = lor(ne(r0, k(0)), ne(band(r1, k(1023)), k(0)));
985 const Id st43 = lor(ne(r0, k(0)), ne(band(r1, k(2047)), k(0)));
986 const Word64 m = select64(big, m43, m42);
987 const Id sticky = bsel(big, st43, st42);
988 const Id e = add(sub(add(a.exp, b.exp), k(1023)), sel(big, k(1), k(0)));
989 const Word64 packed = unpack(round_pack(sign, e, m, sticky));
991 const Id inf_hi = bor(sign, k(2146435072));
992 const Id lo = sel(lor(invalid, lor(inf, zero)), k(0), packed.lo);
993 const Id hi = sel(invalid, k(2146959360), sel(inf, inf_hi, sel(zero, sign, packed.hi)));
999 begin(
"div",
"%v2u32",
"%sd_fn_bin");
1000 const Word64 wa = unpack(
"%sd_f64_div_a");
1001 const Word64 wb = unpack(
"%sd_f64_div_b");
1002 const Unpacked a = unpack_normalised(wa);
1003 const Unpacked b = unpack_normalised(wb);
1005 const Id sign = band(bxor(wa.hi, wb.hi), k(2147483648));
1006 const Id invalid = lor(lor(a.is_nan, b.is_nan), lor(land(a.is_zero, b.is_zero), land(a.is_inf, b.is_inf)));
1007 const Id inf = lor(a.is_inf, b.is_zero);
1008 const Id zero = lor(a.is_zero, b.is_inf);
1010 Word64 remainder = a.mant;
1011 Word64 quotient { k(0), k(0) };
1012 for (uint32_t step = 0; step < 63; ++step) {
1013 const Id fits = lnot(ult64(remainder, b.mant));
1014 const Word64 reduced = select64(fits, sub64(remainder, b.mant), remainder);
1015 const Word64 shifted = shl1(quotient);
1016 quotient = Word64 { bor(shifted.lo, sel(fits, k(1), k(0))), shifted.hi };
1017 remainder = shl1(reduced);
1020 const Id whole = ne(band(quotient.hi, k(1073741824)), k(0));
1021 const Word64 m = select64(whole, quotient, shl1(quotient));
1022 const Id base = sub(add(a.exp, k(1023)), b.exp);
1023 const Id e = sel(whole, base, sub(base, k(1)));
1024 const Word64 packed = unpack(round_pack(sign, e, m, nonzero64(remainder)));
1026 const Id inf_hi = bor(sign, k(2146435072));
1027 const Id lo = sel(lor(invalid, lor(inf, zero)), k(0), packed.lo);
1028 const Id hi = sel(invalid, k(2146959360), sel(inf, inf_hi, sel(zero, sign, packed.hi)));
1032 Id pair_bits(
const Word64& w, uint32_t position)
1034 if (position >= 32) {
1035 return band(shr(w.hi, k(position - 32)), k(3));
1037 return band(shr(w.lo, k(position)), k(3));
1042 begin(
"sqrt",
"%v2u32",
"%sd_fn_bin");
1043 const Word64 wa = unpack(
"%sd_f64_sqrt_a");
1044 const Unpacked a = unpack_normalised(wa);
1046 const Id negative = ne(band(wa.hi, k(2147483648)), k(0));
1047 const Id invalid = lor(a.is_nan, land(negative, lnot(a.is_zero)));
1048 const Id passes = lor(a.is_zero, a.is_inf);
1050 const Id odd_exponent = eq(band(a.exp, k(1)), k(0));
1051 const Word64 radicand = select64(odd_exponent, shl1(a.mant), a.mant);
1053 Word64 root { k(0), k(0) };
1054 Word64 remainder { k(0), k(0) };
1055 for (uint32_t step = 0; step < 56; ++step) {
1056 const Id incoming = step < 27 ? pair_bits(radicand, 52 - 2 * step) : k(0);
1057 const Word64 widened = shl1(shl1(remainder));
1058 const Word64 brought { bor(widened.lo, incoming), widened.hi };
1059 const Word64 doubled = shl1(shl1(root));
1060 const Word64 trial { bor(doubled.lo, k(1)), doubled.hi };
1061 const Id fits = lnot(ult64(brought, trial));
1062 remainder = select64(fits, sub64(brought, trial), brought);
1063 const Word64 grown = shl1(root);
1064 root = Word64 { bor(grown.lo, sel(fits, k(1), k(0))), grown.hi };
1068 for (uint32_t i = 0; i < 7; ++i) {
1071 const Id parity = sel(odd_exponent, k(1), k(0));
1072 const Id e = shr(sub(add(a.exp, k(1023)), parity), k(1));
1073 const Word64 packed = unpack(round_pack(k(0), e, m, nonzero64(remainder)));
1075 const Id lo = sel(invalid, k(0), sel(passes, wa.lo, packed.lo));
1076 const Id hi = sel(invalid, k(2146959360), sel(passes, wa.hi, packed.hi));
1080 void emit_to_float32()
1082 begin(
"to_f32",
"%u32",
"%sd_fn_tof32");
1083 const Word64 w = unpack(
"%sd_f64_to_f32_a");
1085 const Id sign = band(w.hi, k(2147483648));
1086 const Id e = band(shr(w.hi, k(20)), k(2047));
1087 const Id fraction_hi = band(w.hi, k(1048575));
1088 const Id max_exp = eq(e, k(2047));
1089 const Id is_nan = land(max_exp, ne(bor(fraction_hi, w.lo), k(0)));
1090 const Id tiny = eq(e, k(0));
1092 const Word64 full { w.lo, bor(fraction_hi, k(1048576)) };
1093 const Id normal = uge(e, k(897));
1094 const Id drop = sel(normal, k(29), sub(k(926), e));
1095 const Shifted shifted = shr64_sticky(full, umin(sub(drop, k(1)), k(60)));
1096 const Id guard = band(shifted.value.lo, k(1));
1097 const Id quotient = shr(shifted.value.lo, k(1));
1098 const Id up = land(ne(guard, k(0)), lor(shifted.sticky, ne(band(quotient, k(1)), k(0))));
1099 const Id rounded = add(quotient, sel(up, k(1), k(0)));
1100 const Id base = sel(normal, shl(sub(e, k(897)), k(23)), k(0));
1101 const Id bits = add(base, rounded);
1103 const Id overflow = lor(uge(e, k(1151)), uge(bits, k(2139095040)));
1104 const Id finite = sel(tiny, k(0), sel(overflow, k(2139095040), bits));
1105 const Id special = sel(is_nan, k(2143289344), k(2139095040));
1106 end(bor(sign, sel(max_exp, special, finite)));
1111 const Id max_exp = eq(band(shr(w.hi, k(20)), k(2047)), k(2047));
1112 const Id is_nan = land(max_exp, ne(bor(band(w.hi, k(1048575)), w.lo), k(0)));
1113 const Id is_zero = eq(bor(shl(w.hi, k(1)), w.lo), k(0));
1114 const Id hi = sel(is_zero, k(0), w.hi);
1115 const Id lo = sel(is_zero, k(0), w.lo);
1116 const Id negative = ne(band(hi, k(2147483648)), k(0));
1117 const Id key_lo = sel(negative, bnot(lo), lo);
1118 const Id key_hi = sel(negative, bnot(hi), bor(hi, k(2147483648)));
1119 return { sel(is_nan, k(4294967295), key_lo), sel(is_nan, k(4294967295), key_hi) };
1122 Word64 argmax_key(
const Word64& w)
1124 const Id max_exp = eq(band(shr(w.hi, k(20)), k(2047)), k(2047));
1125 const Id is_nan = land(max_exp, ne(bor(band(w.hi, k(1048575)), w.lo), k(0)));
1127 return { sel(is_nan, k(0), key.lo), sel(is_nan, k(0), key.hi) };
1132 begin(
"less",
"%bool",
"%sd_fn_less");
1133 const Word64 ka =
order_key(unpack(
"%sd_f64_less_a"));
1134 const Word64 kb =
order_key(unpack(
"%sd_f64_less_b"));
1144 return builder.finish(use);
1149 const uint32_t points = spec.
points;
1152 const bool shaped = spec.
bindings.size() == (projecting ? 5U : 4U) && spec.
pc_fields.size() == 5
1155 return b.format == Kakshya::GpuDataFormat::VEC2_U32;
1158 return f.format == Kakshya::GpuDataFormat::UINT32;
1160 const bool sized = points >= 2 && points <= 2048 && (points & (points - 1)) == 0
1161 && local >= 1 && local <= points / 2 && (local & (local - 1)) == 0;
1162 if (!shaped || !sized) {
1167 return builder.fft(spec);
1175 return b.format == Kakshya::GpuDataFormat::VEC2_U32;
1178 return f.format == Kakshya::GpuDataFormat::UINT32;
1180 const bool sized = local >= 2 && local <= 1024 && (local & (local - 1)) == 0;
1181 if (!shaped || !sized) {
1186 return builder.lagged_pair(spec);
1194 return b.format == Kakshya::GpuDataFormat::VEC2_U32;
1197 return f.format == Kakshya::GpuDataFormat::UINT32;
1199 const bool sized = local >= 2 && local <= 1024 && (local & (local - 1)) == 0;
1200 if (!shaped || !sized) {
1205 return builder.segmented_argmax(spec);
1213 const auto expected = [&](
size_t index) {
1216 bool formats = spec.
bindings.size() == bindings;
1217 for (
size_t i = 0; formats && i < spec.
bindings.size(); ++i) {
1218 formats = spec.
bindings[i].format == expected(i);
1220 const bool shaped = formats && spec.
pc_fields.size() == 1
1222 const bool sized = local >= 1 && local <= 1024;
1223 if (!shaped || !sized) {
1228 return builder.word_pair_map(spec);
@ VEC2_U32
glm::uvec2: a 64-bit value as low word (x) and high word (y), not a sampled image format
@ FLOAT32
32-bit float (standard GPU)
std::vector< double > sum(std::span< const double > data, size_t n_windows, uint32_t hop_size, uint32_t window_size)
Sum per window.
constexpr uint64_t order_key(double value) noexcept
The order key of a value.
std::vector< double > power(std::span< const double > data, size_t n_windows, uint32_t hop_size, uint32_t window_size)
Power (sum of squares) per window.
std::vector< double > count(std::span< const double > data, size_t n_windows, uint32_t hop_size, uint32_t window_size)
Sample count per window (as double for pipeline uniformity).
constexpr T map(T x, T in_lo, T in_hi, T out_lo, T out_hi) noexcept
Map x from [in_lo, in_hi] to [out_lo, out_hi], unclamped.
Tendency< D, float > scale(const Tendency< D, float > &t, float factor)
Uniform scaling of a scalar-output tendency.
Tendency< D, R > combine(const Tendency< D, R > &a, const Tendency< D, R > &b, BinaryOp op)
Combine two tendencies with a binary operation on their outputs.
std::string emit_word_pair_map(const ShaderSpec &spec)
Emit the globals, soft-double function and entry point of the WordPairMap template.
std::string emit_segmented_argmax(const ShaderSpec &spec)
Emit the globals and entry point of the SegmentedArgMax template.
SoftDoubleModule emit_soft_double(const SoftDoubleUse &use)
Emit the requested soft-double functions.
constexpr std::string_view soft_double_sqrt
Function taking the square root of the first double, held as uvec2.
constexpr std::string_view soft_double_div
Function dividing the first double by the second, held as uvec2.
std::string emit_lagged_pair(const ShaderSpec &spec)
Emit the globals, soft-double functions and entry point of the LaggedPair template.
constexpr std::string_view soft_double_to_float32
Function converting a double held as uvec2 to the bits of a float32, as a u32.
std::string emit_fft(const ShaderSpec &spec)
Emit the globals, soft-double functions and entry point of the FFT template.
constexpr std::string_view soft_double_add
Function adding two doubles held as uvec2.
constexpr std::string_view soft_double_mul
Function multiplying two doubles held as uvec2.
@ Projection
descriptors values per window: row r of a weights binding, one weight per power bin,...
@ Power
points / 2 + 1 bins of re * re + im * im, after scaling
PairMap
Map of two elements, x[i] and x[i + lag], summed by a LaggedPair kernel.
@ SignChange
1 when exactly one of a, b is non-negative, else 0; NaN counts as negative
WordPairOp
Operation applied by a WordPairMap kernel.
@ ToFloat32
float32(a) rounded to nearest even, with IEEE results for zeros, infinities, NaN, overflow and float ...
@ Sqrt
sqrt(a). Unary: no b binding.
void move(EditableText &s, int n)
Move the cursor by n codepoints.
Declaration of one SSBO or image binding in a generated shader.
One field in the generated push constant block.
uint32_t points
FFT only. Points per window.
std::vector< PushConstantField > pc_fields
std::vector< BindingSlot > bindings
WordPairOp word_op
WordPairMap only.
uint32_t descriptors
FFT with SpectrumOutput::Projection only. Rows of weights.
std::array< uint32_t, 3 > workgroup_size
SpectrumOutput spectrum
FFT only.
Complete declarative description of a generated compute shader.
Assembly text for the requested soft-double functions.
Which soft-double functions a generated module needs.