cf67893c6c86c65268a43afa951a80bc89ea4ae6
[mesa.git] / src / compiler / spirv / vtn_cfg.c
1 /*
2 * Copyright © 2015 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 "vtn_private.h"
25 #include "nir/nir_vla.h"
26
27 static struct vtn_pointer *
28 vtn_load_param_pointer(struct vtn_builder *b,
29 struct vtn_type *param_type,
30 uint32_t param_idx)
31 {
32 struct vtn_type *ptr_type = param_type;
33 if (param_type->base_type != vtn_base_type_pointer) {
34 assert(param_type->base_type == vtn_base_type_image ||
35 param_type->base_type == vtn_base_type_sampler);
36 ptr_type = rzalloc(b, struct vtn_type);
37 ptr_type->base_type = vtn_base_type_pointer;
38 ptr_type->deref = param_type;
39 ptr_type->storage_class = SpvStorageClassUniformConstant;
40 }
41
42 return vtn_pointer_from_ssa(b, nir_load_param(&b->nb, param_idx), ptr_type);
43 }
44
45 static unsigned
46 vtn_type_count_function_params(struct vtn_type *type)
47 {
48 switch (type->base_type) {
49 case vtn_base_type_array:
50 case vtn_base_type_matrix:
51 return type->length * vtn_type_count_function_params(type->array_element);
52
53 case vtn_base_type_struct: {
54 unsigned count = 0;
55 for (unsigned i = 0; i < type->length; i++)
56 count += vtn_type_count_function_params(type->members[i]);
57 return count;
58 }
59
60 case vtn_base_type_sampled_image:
61 return 2;
62
63 default:
64 return 1;
65 }
66 }
67
68 static void
69 vtn_type_add_to_function_params(struct vtn_type *type,
70 nir_function *func,
71 unsigned *param_idx)
72 {
73 static const nir_parameter nir_deref_param = {
74 .num_components = 1,
75 .bit_size = 32,
76 };
77
78 switch (type->base_type) {
79 case vtn_base_type_array:
80 case vtn_base_type_matrix:
81 for (unsigned i = 0; i < type->length; i++)
82 vtn_type_add_to_function_params(type->array_element, func, param_idx);
83 break;
84
85 case vtn_base_type_struct:
86 for (unsigned i = 0; i < type->length; i++)
87 vtn_type_add_to_function_params(type->members[i], func, param_idx);
88 break;
89
90 case vtn_base_type_sampled_image:
91 func->params[(*param_idx)++] = nir_deref_param;
92 func->params[(*param_idx)++] = nir_deref_param;
93 break;
94
95 case vtn_base_type_image:
96 case vtn_base_type_sampler:
97 func->params[(*param_idx)++] = nir_deref_param;
98 break;
99
100 case vtn_base_type_pointer:
101 if (type->type) {
102 func->params[(*param_idx)++] = (nir_parameter) {
103 .num_components = glsl_get_vector_elements(type->type),
104 .bit_size = glsl_get_bit_size(type->type),
105 };
106 } else {
107 func->params[(*param_idx)++] = nir_deref_param;
108 }
109 break;
110
111 default:
112 func->params[(*param_idx)++] = (nir_parameter) {
113 .num_components = glsl_get_vector_elements(type->type),
114 .bit_size = glsl_get_bit_size(type->type),
115 };
116 }
117 }
118
119 static void
120 vtn_ssa_value_add_to_call_params(struct vtn_builder *b,
121 struct vtn_ssa_value *value,
122 struct vtn_type *type,
123 nir_call_instr *call,
124 unsigned *param_idx)
125 {
126 switch (type->base_type) {
127 case vtn_base_type_array:
128 case vtn_base_type_matrix:
129 for (unsigned i = 0; i < type->length; i++) {
130 vtn_ssa_value_add_to_call_params(b, value->elems[i],
131 type->array_element,
132 call, param_idx);
133 }
134 break;
135
136 case vtn_base_type_struct:
137 for (unsigned i = 0; i < type->length; i++) {
138 vtn_ssa_value_add_to_call_params(b, value->elems[i],
139 type->members[i],
140 call, param_idx);
141 }
142 break;
143
144 default:
145 call->params[(*param_idx)++] = nir_src_for_ssa(value->def);
146 break;
147 }
148 }
149
150 static void
151 vtn_ssa_value_load_function_param(struct vtn_builder *b,
152 struct vtn_ssa_value *value,
153 struct vtn_type *type,
154 unsigned *param_idx)
155 {
156 switch (type->base_type) {
157 case vtn_base_type_array:
158 case vtn_base_type_matrix:
159 for (unsigned i = 0; i < type->length; i++) {
160 vtn_ssa_value_load_function_param(b, value->elems[i],
161 type->array_element, param_idx);
162 }
163 break;
164
165 case vtn_base_type_struct:
166 for (unsigned i = 0; i < type->length; i++) {
167 vtn_ssa_value_load_function_param(b, value->elems[i],
168 type->members[i], param_idx);
169 }
170 break;
171
172 default:
173 value->def = nir_load_param(&b->nb, (*param_idx)++);
174 break;
175 }
176 }
177
178 void
179 vtn_handle_function_call(struct vtn_builder *b, SpvOp opcode,
180 const uint32_t *w, unsigned count)
181 {
182 struct vtn_type *res_type = vtn_value(b, w[1], vtn_value_type_type)->type;
183 struct vtn_function *vtn_callee =
184 vtn_value(b, w[3], vtn_value_type_function)->func;
185 struct nir_function *callee = vtn_callee->impl->function;
186
187 vtn_callee->referenced = true;
188
189 nir_call_instr *call = nir_call_instr_create(b->nb.shader, callee);
190
191 unsigned param_idx = 0;
192
193 nir_deref_instr *ret_deref = NULL;
194 struct vtn_type *ret_type = vtn_callee->type->return_type;
195 if (ret_type->base_type != vtn_base_type_void) {
196 nir_variable *ret_tmp =
197 nir_local_variable_create(b->nb.impl,
198 glsl_get_bare_type(ret_type->type),
199 "return_tmp");
200 ret_deref = nir_build_deref_var(&b->nb, ret_tmp);
201 call->params[param_idx++] = nir_src_for_ssa(&ret_deref->dest.ssa);
202 }
203
204 for (unsigned i = 0; i < vtn_callee->type->length; i++) {
205 struct vtn_type *arg_type = vtn_callee->type->params[i];
206 unsigned arg_id = w[4 + i];
207
208 if (arg_type->base_type == vtn_base_type_sampled_image) {
209 struct vtn_sampled_image *sampled_image =
210 vtn_value(b, arg_id, vtn_value_type_sampled_image)->sampled_image;
211
212 call->params[param_idx++] =
213 nir_src_for_ssa(&sampled_image->image->deref->dest.ssa);
214 call->params[param_idx++] =
215 nir_src_for_ssa(&sampled_image->sampler->deref->dest.ssa);
216 } else if (arg_type->base_type == vtn_base_type_pointer ||
217 arg_type->base_type == vtn_base_type_image ||
218 arg_type->base_type == vtn_base_type_sampler) {
219 struct vtn_pointer *pointer =
220 vtn_value(b, arg_id, vtn_value_type_pointer)->pointer;
221 call->params[param_idx++] =
222 nir_src_for_ssa(vtn_pointer_to_ssa(b, pointer));
223 } else {
224 vtn_ssa_value_add_to_call_params(b, vtn_ssa_value(b, arg_id),
225 arg_type, call, &param_idx);
226 }
227 }
228 assert(param_idx == call->num_params);
229
230 nir_builder_instr_insert(&b->nb, &call->instr);
231
232 if (ret_type->base_type == vtn_base_type_void) {
233 vtn_push_value(b, w[2], vtn_value_type_undef);
234 } else {
235 vtn_push_ssa(b, w[2], res_type, vtn_local_load(b, ret_deref, 0));
236 }
237 }
238
239 static bool
240 vtn_cfg_handle_prepass_instruction(struct vtn_builder *b, SpvOp opcode,
241 const uint32_t *w, unsigned count)
242 {
243 switch (opcode) {
244 case SpvOpFunction: {
245 vtn_assert(b->func == NULL);
246 b->func = rzalloc(b, struct vtn_function);
247
248 list_inithead(&b->func->body);
249 b->func->control = w[3];
250
251 UNUSED const struct glsl_type *result_type =
252 vtn_value(b, w[1], vtn_value_type_type)->type->type;
253 struct vtn_value *val = vtn_push_value(b, w[2], vtn_value_type_function);
254 val->func = b->func;
255
256 b->func->type = vtn_value(b, w[4], vtn_value_type_type)->type;
257 const struct vtn_type *func_type = b->func->type;
258
259 vtn_assert(func_type->return_type->type == result_type);
260
261 nir_function *func =
262 nir_function_create(b->shader, ralloc_strdup(b->shader, val->name));
263
264 unsigned num_params = 0;
265 for (unsigned i = 0; i < func_type->length; i++)
266 num_params += vtn_type_count_function_params(func_type->params[i]);
267
268 /* Add one parameter for the function return value */
269 if (func_type->return_type->base_type != vtn_base_type_void)
270 num_params++;
271
272 func->num_params = num_params;
273 func->params = ralloc_array(b->shader, nir_parameter, num_params);
274
275 unsigned idx = 0;
276 if (func_type->return_type->base_type != vtn_base_type_void) {
277 /* The return value is a regular pointer */
278 func->params[idx++] = (nir_parameter) {
279 .num_components = 1, .bit_size = 32,
280 };
281 }
282
283 for (unsigned i = 0; i < func_type->length; i++)
284 vtn_type_add_to_function_params(func_type->params[i], func, &idx);
285 assert(idx == num_params);
286
287 b->func->impl = nir_function_impl_create(func);
288 nir_builder_init(&b->nb, func->impl);
289 b->nb.cursor = nir_before_cf_list(&b->func->impl->body);
290 b->nb.exact = b->exact;
291
292 b->func_param_idx = 0;
293
294 /* The return value is the first parameter */
295 if (func_type->return_type->base_type != vtn_base_type_void)
296 b->func_param_idx++;
297 break;
298 }
299
300 case SpvOpFunctionEnd:
301 b->func->end = w;
302 b->func = NULL;
303 break;
304
305 case SpvOpFunctionParameter: {
306 struct vtn_type *type = vtn_value(b, w[1], vtn_value_type_type)->type;
307
308 vtn_assert(b->func_param_idx < b->func->impl->function->num_params);
309
310 if (type->base_type == vtn_base_type_sampled_image) {
311 /* Sampled images are actually two parameters. The first is the
312 * image and the second is the sampler.
313 */
314 struct vtn_value *val =
315 vtn_push_value(b, w[2], vtn_value_type_sampled_image);
316
317 val->sampled_image = ralloc(b, struct vtn_sampled_image);
318
319 struct vtn_type *sampler_type = rzalloc(b, struct vtn_type);
320 sampler_type->base_type = vtn_base_type_sampler;
321 sampler_type->type = glsl_bare_sampler_type();
322
323 val->sampled_image->image =
324 vtn_load_param_pointer(b, type, b->func_param_idx++);
325 val->sampled_image->sampler =
326 vtn_load_param_pointer(b, sampler_type, b->func_param_idx++);
327 } else if (type->base_type == vtn_base_type_pointer &&
328 type->type != NULL) {
329 /* This is a pointer with an actual storage type */
330 nir_ssa_def *ssa_ptr = nir_load_param(&b->nb, b->func_param_idx++);
331 vtn_push_value_pointer(b, w[2], vtn_pointer_from_ssa(b, ssa_ptr, type));
332 } else if (type->base_type == vtn_base_type_pointer ||
333 type->base_type == vtn_base_type_image ||
334 type->base_type == vtn_base_type_sampler) {
335 vtn_push_value_pointer(b, w[2], vtn_load_param_pointer(b, type, b->func_param_idx++));
336 } else {
337 /* We're a regular SSA value. */
338 struct vtn_ssa_value *value = vtn_create_ssa_value(b, type->type);
339 vtn_ssa_value_load_function_param(b, value, type, &b->func_param_idx);
340 vtn_push_ssa(b, w[2], type, value);
341 }
342 break;
343 }
344
345 case SpvOpLabel: {
346 vtn_assert(b->block == NULL);
347 b->block = rzalloc(b, struct vtn_block);
348 b->block->node.type = vtn_cf_node_type_block;
349 b->block->label = w;
350 vtn_push_value(b, w[1], vtn_value_type_block)->block = b->block;
351
352 if (b->func->start_block == NULL) {
353 /* This is the first block encountered for this function. In this
354 * case, we set the start block and add it to the list of
355 * implemented functions that we'll walk later.
356 */
357 b->func->start_block = b->block;
358 exec_list_push_tail(&b->functions, &b->func->node);
359 }
360 break;
361 }
362
363 case SpvOpSelectionMerge:
364 case SpvOpLoopMerge:
365 vtn_assert(b->block && b->block->merge == NULL);
366 b->block->merge = w;
367 break;
368
369 case SpvOpBranch:
370 case SpvOpBranchConditional:
371 case SpvOpSwitch:
372 case SpvOpKill:
373 case SpvOpReturn:
374 case SpvOpReturnValue:
375 case SpvOpUnreachable:
376 vtn_assert(b->block && b->block->branch == NULL);
377 b->block->branch = w;
378 b->block = NULL;
379 break;
380
381 default:
382 /* Continue on as per normal */
383 return true;
384 }
385
386 return true;
387 }
388
389 static void
390 vtn_add_case(struct vtn_builder *b, struct vtn_switch *swtch,
391 struct vtn_block *break_block,
392 uint32_t block_id, uint64_t val, bool is_default)
393 {
394 struct vtn_block *case_block =
395 vtn_value(b, block_id, vtn_value_type_block)->block;
396
397 /* Don't create dummy cases that just break */
398 if (case_block == break_block)
399 return;
400
401 if (case_block->switch_case == NULL) {
402 struct vtn_case *c = ralloc(b, struct vtn_case);
403
404 list_inithead(&c->body);
405 c->start_block = case_block;
406 c->fallthrough = NULL;
407 util_dynarray_init(&c->values, b);
408 c->is_default = false;
409 c->visited = false;
410
411 list_addtail(&c->link, &swtch->cases);
412
413 case_block->switch_case = c;
414 }
415
416 if (is_default) {
417 case_block->switch_case->is_default = true;
418 } else {
419 util_dynarray_append(&case_block->switch_case->values, uint64_t, val);
420 }
421 }
422
423 /* This function performs a depth-first search of the cases and puts them
424 * in fall-through order.
425 */
426 static void
427 vtn_order_case(struct vtn_switch *swtch, struct vtn_case *cse)
428 {
429 if (cse->visited)
430 return;
431
432 cse->visited = true;
433
434 list_del(&cse->link);
435
436 if (cse->fallthrough) {
437 vtn_order_case(swtch, cse->fallthrough);
438
439 /* If we have a fall-through, place this case right before the case it
440 * falls through to. This ensures that fallthroughs come one after
441 * the other. These two can never get separated because that would
442 * imply something else falling through to the same case. Also, this
443 * can't break ordering because the DFS ensures that this case is
444 * visited before anything that falls through to it.
445 */
446 list_addtail(&cse->link, &cse->fallthrough->link);
447 } else {
448 list_add(&cse->link, &swtch->cases);
449 }
450 }
451
452 static enum vtn_branch_type
453 vtn_get_branch_type(struct vtn_builder *b,
454 struct vtn_block *block,
455 struct vtn_case *swcase, struct vtn_block *switch_break,
456 struct vtn_block *loop_break, struct vtn_block *loop_cont)
457 {
458 if (block->switch_case) {
459 /* This branch is actually a fallthrough */
460 vtn_assert(swcase->fallthrough == NULL ||
461 swcase->fallthrough == block->switch_case);
462 swcase->fallthrough = block->switch_case;
463 return vtn_branch_type_switch_fallthrough;
464 } else if (block == loop_break) {
465 return vtn_branch_type_loop_break;
466 } else if (block == loop_cont) {
467 return vtn_branch_type_loop_continue;
468 } else if (block == switch_break) {
469 return vtn_branch_type_switch_break;
470 } else {
471 return vtn_branch_type_none;
472 }
473 }
474
475 static void
476 vtn_cfg_walk_blocks(struct vtn_builder *b, struct list_head *cf_list,
477 struct vtn_block *start, struct vtn_case *switch_case,
478 struct vtn_block *switch_break,
479 struct vtn_block *loop_break, struct vtn_block *loop_cont,
480 struct vtn_block *end)
481 {
482 struct vtn_block *block = start;
483 while (block != end) {
484 if (block->merge && (*block->merge & SpvOpCodeMask) == SpvOpLoopMerge &&
485 !block->loop) {
486 struct vtn_loop *loop = ralloc(b, struct vtn_loop);
487
488 loop->node.type = vtn_cf_node_type_loop;
489 list_inithead(&loop->body);
490 list_inithead(&loop->cont_body);
491 loop->control = block->merge[3];
492
493 list_addtail(&loop->node.link, cf_list);
494 block->loop = loop;
495
496 struct vtn_block *new_loop_break =
497 vtn_value(b, block->merge[1], vtn_value_type_block)->block;
498 struct vtn_block *new_loop_cont =
499 vtn_value(b, block->merge[2], vtn_value_type_block)->block;
500
501 /* Note: This recursive call will start with the current block as
502 * its start block. If we weren't careful, we would get here
503 * again and end up in infinite recursion. This is why we set
504 * block->loop above and check for it before creating one. This
505 * way, we only create the loop once and the second call that
506 * tries to handle this loop goes to the cases below and gets
507 * handled as a regular block.
508 *
509 * Note: When we make the recursive walk calls, we pass NULL for
510 * the switch break since you have to break out of the loop first.
511 * We do, however, still pass the current switch case because it's
512 * possible that the merge block for the loop is the start of
513 * another case.
514 */
515 vtn_cfg_walk_blocks(b, &loop->body, block, switch_case, NULL,
516 new_loop_break, new_loop_cont, NULL );
517 vtn_cfg_walk_blocks(b, &loop->cont_body, new_loop_cont, NULL, NULL,
518 new_loop_break, NULL, block);
519
520 enum vtn_branch_type branch_type =
521 vtn_get_branch_type(b, new_loop_break, switch_case, switch_break,
522 loop_break, loop_cont);
523
524 if (branch_type != vtn_branch_type_none) {
525 /* Stop walking through the CFG when this inner loop's break block
526 * ends up as the same block as the outer loop's continue block
527 * because we are already going to visit it.
528 */
529 vtn_assert(branch_type == vtn_branch_type_loop_continue);
530 return;
531 }
532
533 block = new_loop_break;
534 continue;
535 }
536
537 vtn_assert(block->node.link.next == NULL);
538 list_addtail(&block->node.link, cf_list);
539
540 switch (*block->branch & SpvOpCodeMask) {
541 case SpvOpBranch: {
542 struct vtn_block *branch_block =
543 vtn_value(b, block->branch[1], vtn_value_type_block)->block;
544
545 block->branch_type = vtn_get_branch_type(b, branch_block,
546 switch_case, switch_break,
547 loop_break, loop_cont);
548
549 if (block->branch_type != vtn_branch_type_none)
550 return;
551
552 block = branch_block;
553 continue;
554 }
555
556 case SpvOpReturn:
557 case SpvOpReturnValue:
558 block->branch_type = vtn_branch_type_return;
559 return;
560
561 case SpvOpKill:
562 block->branch_type = vtn_branch_type_discard;
563 return;
564
565 case SpvOpBranchConditional: {
566 struct vtn_block *then_block =
567 vtn_value(b, block->branch[2], vtn_value_type_block)->block;
568 struct vtn_block *else_block =
569 vtn_value(b, block->branch[3], vtn_value_type_block)->block;
570
571 struct vtn_if *if_stmt = ralloc(b, struct vtn_if);
572
573 if_stmt->node.type = vtn_cf_node_type_if;
574 if_stmt->condition = block->branch[1];
575 list_inithead(&if_stmt->then_body);
576 list_inithead(&if_stmt->else_body);
577
578 list_addtail(&if_stmt->node.link, cf_list);
579
580 if (block->merge &&
581 (*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge) {
582 if_stmt->control = block->merge[2];
583 } else {
584 if_stmt->control = SpvSelectionControlMaskNone;
585 }
586
587 if_stmt->then_type = vtn_get_branch_type(b, then_block,
588 switch_case, switch_break,
589 loop_break, loop_cont);
590 if_stmt->else_type = vtn_get_branch_type(b, else_block,
591 switch_case, switch_break,
592 loop_break, loop_cont);
593
594 if (then_block == else_block) {
595 block->branch_type = if_stmt->then_type;
596 if (block->branch_type == vtn_branch_type_none) {
597 block = then_block;
598 continue;
599 } else {
600 return;
601 }
602 } else if (if_stmt->then_type == vtn_branch_type_none &&
603 if_stmt->else_type == vtn_branch_type_none) {
604 /* Neither side of the if is something we can short-circuit. */
605 vtn_assert((*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge);
606 struct vtn_block *merge_block =
607 vtn_value(b, block->merge[1], vtn_value_type_block)->block;
608
609 vtn_cfg_walk_blocks(b, &if_stmt->then_body, then_block,
610 switch_case, switch_break,
611 loop_break, loop_cont, merge_block);
612 vtn_cfg_walk_blocks(b, &if_stmt->else_body, else_block,
613 switch_case, switch_break,
614 loop_break, loop_cont, merge_block);
615
616 enum vtn_branch_type merge_type =
617 vtn_get_branch_type(b, merge_block, switch_case, switch_break,
618 loop_break, loop_cont);
619 if (merge_type == vtn_branch_type_none) {
620 block = merge_block;
621 continue;
622 } else {
623 return;
624 }
625 } else if (if_stmt->then_type != vtn_branch_type_none &&
626 if_stmt->else_type != vtn_branch_type_none) {
627 /* Both sides were short-circuited. We're done here. */
628 return;
629 } else {
630 /* Exeactly one side of the branch could be short-circuited.
631 * We set the branch up as a predicated break/continue and we
632 * continue on with the other side as if it were what comes
633 * after the if.
634 */
635 if (if_stmt->then_type == vtn_branch_type_none) {
636 block = then_block;
637 } else {
638 block = else_block;
639 }
640 continue;
641 }
642 vtn_fail("Should have returned or continued");
643 }
644
645 case SpvOpSwitch: {
646 vtn_assert((*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge);
647 struct vtn_block *break_block =
648 vtn_value(b, block->merge[1], vtn_value_type_block)->block;
649
650 struct vtn_switch *swtch = ralloc(b, struct vtn_switch);
651
652 swtch->node.type = vtn_cf_node_type_switch;
653 swtch->selector = block->branch[1];
654 list_inithead(&swtch->cases);
655
656 list_addtail(&swtch->node.link, cf_list);
657
658 /* First, we go through and record all of the cases. */
659 const uint32_t *branch_end =
660 block->branch + (block->branch[0] >> SpvWordCountShift);
661
662 struct vtn_value *cond_val = vtn_untyped_value(b, block->branch[1]);
663 vtn_fail_if(!cond_val->type ||
664 cond_val->type->base_type != vtn_base_type_scalar,
665 "Selector of OpSelect must have a type of OpTypeInt");
666
667 nir_alu_type cond_type =
668 nir_get_nir_type_for_glsl_type(cond_val->type->type);
669 vtn_fail_if(nir_alu_type_get_base_type(cond_type) != nir_type_int &&
670 nir_alu_type_get_base_type(cond_type) != nir_type_uint,
671 "Selector of OpSelect must have a type of OpTypeInt");
672
673 bool is_default = true;
674 const unsigned bitsize = nir_alu_type_get_type_size(cond_type);
675 for (const uint32_t *w = block->branch + 2; w < branch_end;) {
676 uint64_t literal = 0;
677 if (!is_default) {
678 if (bitsize <= 32) {
679 literal = *(w++);
680 } else {
681 assert(bitsize == 64);
682 literal = vtn_u64_literal(w);
683 w += 2;
684 }
685 }
686
687 uint32_t block_id = *(w++);
688
689 vtn_add_case(b, swtch, break_block, block_id, literal, is_default);
690 is_default = false;
691 }
692
693 /* Now, we go through and walk the blocks. While we walk through
694 * the blocks, we also gather the much-needed fall-through
695 * information.
696 */
697 list_for_each_entry(struct vtn_case, cse, &swtch->cases, link) {
698 vtn_assert(cse->start_block != break_block);
699 vtn_cfg_walk_blocks(b, &cse->body, cse->start_block, cse,
700 break_block, loop_break, loop_cont, NULL);
701 }
702
703 /* Finally, we walk over all of the cases one more time and put
704 * them in fall-through order.
705 */
706 for (const uint32_t *w = block->branch + 2; w < branch_end;) {
707 struct vtn_block *case_block =
708 vtn_value(b, *w, vtn_value_type_block)->block;
709
710 if (bitsize <= 32) {
711 w += 2;
712 } else {
713 assert(bitsize == 64);
714 w += 3;
715 }
716
717 if (case_block == break_block)
718 continue;
719
720 vtn_assert(case_block->switch_case);
721
722 vtn_order_case(swtch, case_block->switch_case);
723 }
724
725 enum vtn_branch_type branch_type =
726 vtn_get_branch_type(b, break_block, switch_case, NULL,
727 loop_break, loop_cont);
728
729 if (branch_type != vtn_branch_type_none) {
730 /* It is possible that the break is actually the continue block
731 * for the containing loop. In this case, we need to bail and let
732 * the loop parsing code handle the continue properly.
733 */
734 vtn_assert(branch_type == vtn_branch_type_loop_continue);
735 return;
736 }
737
738 block = break_block;
739 continue;
740 }
741
742 case SpvOpUnreachable:
743 return;
744
745 default:
746 vtn_fail("Unhandled opcode");
747 }
748 }
749 }
750
751 void
752 vtn_build_cfg(struct vtn_builder *b, const uint32_t *words, const uint32_t *end)
753 {
754 vtn_foreach_instruction(b, words, end,
755 vtn_cfg_handle_prepass_instruction);
756
757 foreach_list_typed(struct vtn_function, func, node, &b->functions) {
758 vtn_cfg_walk_blocks(b, &func->body, func->start_block,
759 NULL, NULL, NULL, NULL, NULL);
760 }
761 }
762
763 static bool
764 vtn_handle_phis_first_pass(struct vtn_builder *b, SpvOp opcode,
765 const uint32_t *w, unsigned count)
766 {
767 if (opcode == SpvOpLabel)
768 return true; /* Nothing to do */
769
770 /* If this isn't a phi node, stop. */
771 if (opcode != SpvOpPhi)
772 return false;
773
774 /* For handling phi nodes, we do a poor-man's out-of-ssa on the spot.
775 * For each phi, we create a variable with the appropreate type and
776 * do a load from that variable. Then, in a second pass, we add
777 * stores to that variable to each of the predecessor blocks.
778 *
779 * We could do something more intelligent here. However, in order to
780 * handle loops and things properly, we really need dominance
781 * information. It would end up basically being the into-SSA
782 * algorithm all over again. It's easier if we just let
783 * lower_vars_to_ssa do that for us instead of repeating it here.
784 */
785 struct vtn_type *type = vtn_value(b, w[1], vtn_value_type_type)->type;
786 nir_variable *phi_var =
787 nir_local_variable_create(b->nb.impl, type->type, "phi");
788 _mesa_hash_table_insert(b->phi_table, w, phi_var);
789
790 vtn_push_ssa(b, w[2], type,
791 vtn_local_load(b, nir_build_deref_var(&b->nb, phi_var), 0));
792
793 return true;
794 }
795
796 static bool
797 vtn_handle_phi_second_pass(struct vtn_builder *b, SpvOp opcode,
798 const uint32_t *w, unsigned count)
799 {
800 if (opcode != SpvOpPhi)
801 return true;
802
803 struct hash_entry *phi_entry = _mesa_hash_table_search(b->phi_table, w);
804 vtn_assert(phi_entry);
805 nir_variable *phi_var = phi_entry->data;
806
807 for (unsigned i = 3; i < count; i += 2) {
808 struct vtn_block *pred =
809 vtn_value(b, w[i + 1], vtn_value_type_block)->block;
810
811 b->nb.cursor = nir_after_instr(&pred->end_nop->instr);
812
813 struct vtn_ssa_value *src = vtn_ssa_value(b, w[i]);
814
815 vtn_local_store(b, src, nir_build_deref_var(&b->nb, phi_var), 0);
816 }
817
818 return true;
819 }
820
821 static void
822 vtn_emit_branch(struct vtn_builder *b, enum vtn_branch_type branch_type,
823 nir_variable *switch_fall_var, bool *has_switch_break)
824 {
825 switch (branch_type) {
826 case vtn_branch_type_switch_break:
827 nir_store_var(&b->nb, switch_fall_var, nir_imm_false(&b->nb), 1);
828 *has_switch_break = true;
829 break;
830 case vtn_branch_type_switch_fallthrough:
831 break; /* Nothing to do */
832 case vtn_branch_type_loop_break:
833 nir_jump(&b->nb, nir_jump_break);
834 break;
835 case vtn_branch_type_loop_continue:
836 nir_jump(&b->nb, nir_jump_continue);
837 break;
838 case vtn_branch_type_return:
839 nir_jump(&b->nb, nir_jump_return);
840 break;
841 case vtn_branch_type_discard: {
842 nir_intrinsic_instr *discard =
843 nir_intrinsic_instr_create(b->nb.shader, nir_intrinsic_discard);
844 nir_builder_instr_insert(&b->nb, &discard->instr);
845 break;
846 }
847 default:
848 vtn_fail("Invalid branch type");
849 }
850 }
851
852 static nir_ssa_def *
853 vtn_switch_case_condition(struct vtn_builder *b, struct vtn_switch *swtch,
854 nir_ssa_def *sel, struct vtn_case *cse)
855 {
856 if (cse->is_default) {
857 nir_ssa_def *any = nir_imm_false(&b->nb);
858 list_for_each_entry(struct vtn_case, other, &swtch->cases, link) {
859 if (other->is_default)
860 continue;
861
862 any = nir_ior(&b->nb, any,
863 vtn_switch_case_condition(b, swtch, sel, other));
864 }
865 return nir_inot(&b->nb, any);
866 } else {
867 nir_ssa_def *cond = nir_imm_false(&b->nb);
868 util_dynarray_foreach(&cse->values, uint64_t, val) {
869 nir_ssa_def *imm = nir_imm_intN_t(&b->nb, *val, sel->bit_size);
870 cond = nir_ior(&b->nb, cond, nir_ieq(&b->nb, sel, imm));
871 }
872 return cond;
873 }
874 }
875
876 static nir_loop_control
877 vtn_loop_control(struct vtn_builder *b, struct vtn_loop *vtn_loop)
878 {
879 if (vtn_loop->control == SpvLoopControlMaskNone)
880 return nir_loop_control_none;
881 else if (vtn_loop->control & SpvLoopControlDontUnrollMask)
882 return nir_loop_control_dont_unroll;
883 else if (vtn_loop->control & SpvLoopControlUnrollMask)
884 return nir_loop_control_unroll;
885 else if (vtn_loop->control & SpvLoopControlDependencyInfiniteMask ||
886 vtn_loop->control & SpvLoopControlDependencyLengthMask ||
887 vtn_loop->control & SpvLoopControlMinIterationsMask ||
888 vtn_loop->control & SpvLoopControlMaxIterationsMask ||
889 vtn_loop->control & SpvLoopControlIterationMultipleMask ||
890 vtn_loop->control & SpvLoopControlPeelCountMask ||
891 vtn_loop->control & SpvLoopControlPartialCountMask) {
892 /* We do not do anything special with these yet. */
893 return nir_loop_control_none;
894 } else {
895 vtn_fail("Invalid loop control");
896 }
897 }
898
899 static nir_selection_control
900 vtn_selection_control(struct vtn_builder *b, struct vtn_if *vtn_if)
901 {
902 if (vtn_if->control == SpvSelectionControlMaskNone)
903 return nir_selection_control_none;
904 else if (vtn_if->control & SpvSelectionControlDontFlattenMask)
905 return nir_selection_control_dont_flatten;
906 else if (vtn_if->control & SpvSelectionControlFlattenMask)
907 return nir_selection_control_flatten;
908 else
909 vtn_fail("Invalid selection control");
910 }
911
912 static void
913 vtn_emit_cf_list(struct vtn_builder *b, struct list_head *cf_list,
914 nir_variable *switch_fall_var, bool *has_switch_break,
915 vtn_instruction_handler handler)
916 {
917 list_for_each_entry(struct vtn_cf_node, node, cf_list, link) {
918 switch (node->type) {
919 case vtn_cf_node_type_block: {
920 struct vtn_block *block = (struct vtn_block *)node;
921
922 const uint32_t *block_start = block->label;
923 const uint32_t *block_end = block->merge ? block->merge :
924 block->branch;
925
926 block_start = vtn_foreach_instruction(b, block_start, block_end,
927 vtn_handle_phis_first_pass);
928
929 vtn_foreach_instruction(b, block_start, block_end, handler);
930
931 block->end_nop = nir_intrinsic_instr_create(b->nb.shader,
932 nir_intrinsic_nop);
933 nir_builder_instr_insert(&b->nb, &block->end_nop->instr);
934
935 if ((*block->branch & SpvOpCodeMask) == SpvOpReturnValue) {
936 vtn_fail_if(b->func->type->return_type->base_type ==
937 vtn_base_type_void,
938 "Return with a value from a function returning void");
939 struct vtn_ssa_value *src = vtn_ssa_value(b, block->branch[1]);
940 const struct glsl_type *ret_type =
941 glsl_get_bare_type(b->func->type->return_type->type);
942 nir_deref_instr *ret_deref =
943 nir_build_deref_cast(&b->nb, nir_load_param(&b->nb, 0),
944 nir_var_function_temp, ret_type, 0);
945 vtn_local_store(b, src, ret_deref, 0);
946 }
947
948 if (block->branch_type != vtn_branch_type_none) {
949 vtn_emit_branch(b, block->branch_type,
950 switch_fall_var, has_switch_break);
951 return;
952 }
953
954 break;
955 }
956
957 case vtn_cf_node_type_if: {
958 struct vtn_if *vtn_if = (struct vtn_if *)node;
959 bool sw_break = false;
960
961 nir_if *nif =
962 nir_push_if(&b->nb, vtn_ssa_value(b, vtn_if->condition)->def);
963
964 nif->control = vtn_selection_control(b, vtn_if);
965
966 if (vtn_if->then_type == vtn_branch_type_none) {
967 vtn_emit_cf_list(b, &vtn_if->then_body,
968 switch_fall_var, &sw_break, handler);
969 } else {
970 vtn_emit_branch(b, vtn_if->then_type, switch_fall_var, &sw_break);
971 }
972
973 nir_push_else(&b->nb, nif);
974 if (vtn_if->else_type == vtn_branch_type_none) {
975 vtn_emit_cf_list(b, &vtn_if->else_body,
976 switch_fall_var, &sw_break, handler);
977 } else {
978 vtn_emit_branch(b, vtn_if->else_type, switch_fall_var, &sw_break);
979 }
980
981 nir_pop_if(&b->nb, nif);
982
983 /* If we encountered a switch break somewhere inside of the if,
984 * then it would have been handled correctly by calling
985 * emit_cf_list or emit_branch for the interrior. However, we
986 * need to predicate everything following on wether or not we're
987 * still going.
988 */
989 if (sw_break) {
990 *has_switch_break = true;
991 nir_push_if(&b->nb, nir_load_var(&b->nb, switch_fall_var));
992 }
993 break;
994 }
995
996 case vtn_cf_node_type_loop: {
997 struct vtn_loop *vtn_loop = (struct vtn_loop *)node;
998
999 nir_loop *loop = nir_push_loop(&b->nb);
1000 loop->control = vtn_loop_control(b, vtn_loop);
1001
1002 vtn_emit_cf_list(b, &vtn_loop->body, NULL, NULL, handler);
1003
1004 if (!list_is_empty(&vtn_loop->cont_body)) {
1005 /* If we have a non-trivial continue body then we need to put
1006 * it at the beginning of the loop with a flag to ensure that
1007 * it doesn't get executed in the first iteration.
1008 */
1009 nir_variable *do_cont =
1010 nir_local_variable_create(b->nb.impl, glsl_bool_type(), "cont");
1011
1012 b->nb.cursor = nir_before_cf_node(&loop->cf_node);
1013 nir_store_var(&b->nb, do_cont, nir_imm_false(&b->nb), 1);
1014
1015 b->nb.cursor = nir_before_cf_list(&loop->body);
1016
1017 nir_if *cont_if =
1018 nir_push_if(&b->nb, nir_load_var(&b->nb, do_cont));
1019
1020 vtn_emit_cf_list(b, &vtn_loop->cont_body, NULL, NULL, handler);
1021
1022 nir_pop_if(&b->nb, cont_if);
1023
1024 nir_store_var(&b->nb, do_cont, nir_imm_true(&b->nb), 1);
1025
1026 b->has_loop_continue = true;
1027 }
1028
1029 nir_pop_loop(&b->nb, loop);
1030 break;
1031 }
1032
1033 case vtn_cf_node_type_switch: {
1034 struct vtn_switch *vtn_switch = (struct vtn_switch *)node;
1035
1036 /* First, we create a variable to keep track of whether or not the
1037 * switch is still going at any given point. Any switch breaks
1038 * will set this variable to false.
1039 */
1040 nir_variable *fall_var =
1041 nir_local_variable_create(b->nb.impl, glsl_bool_type(), "fall");
1042 nir_store_var(&b->nb, fall_var, nir_imm_false(&b->nb), 1);
1043
1044 nir_ssa_def *sel = vtn_ssa_value(b, vtn_switch->selector)->def;
1045
1046 /* Now we can walk the list of cases and actually emit code */
1047 list_for_each_entry(struct vtn_case, cse, &vtn_switch->cases, link) {
1048 /* Figure out the condition */
1049 nir_ssa_def *cond =
1050 vtn_switch_case_condition(b, vtn_switch, sel, cse);
1051 /* Take fallthrough into account */
1052 cond = nir_ior(&b->nb, cond, nir_load_var(&b->nb, fall_var));
1053
1054 nir_if *case_if = nir_push_if(&b->nb, cond);
1055
1056 bool has_break = false;
1057 nir_store_var(&b->nb, fall_var, nir_imm_true(&b->nb), 1);
1058 vtn_emit_cf_list(b, &cse->body, fall_var, &has_break, handler);
1059 (void)has_break; /* We don't care */
1060
1061 nir_pop_if(&b->nb, case_if);
1062 }
1063
1064 break;
1065 }
1066
1067 default:
1068 vtn_fail("Invalid CF node type");
1069 }
1070 }
1071 }
1072
1073 void
1074 vtn_function_emit(struct vtn_builder *b, struct vtn_function *func,
1075 vtn_instruction_handler instruction_handler)
1076 {
1077 nir_builder_init(&b->nb, func->impl);
1078 b->func = func;
1079 b->nb.cursor = nir_after_cf_list(&func->impl->body);
1080 b->nb.exact = b->exact;
1081 b->has_loop_continue = false;
1082 b->phi_table = _mesa_pointer_hash_table_create(b);
1083
1084 vtn_emit_cf_list(b, &func->body, NULL, NULL, instruction_handler);
1085
1086 vtn_foreach_instruction(b, func->start_block->label, func->end,
1087 vtn_handle_phi_second_pass);
1088
1089 nir_rematerialize_derefs_in_use_blocks_impl(func->impl);
1090
1091 /* Continue blocks for loops get inserted before the body of the loop
1092 * but instructions in the continue may use SSA defs in the loop body.
1093 * Therefore, we need to repair SSA to insert the needed phi nodes.
1094 */
1095 if (b->has_loop_continue)
1096 nir_repair_ssa_impl(func->impl);
1097
1098 func->emitted = true;
1099 }