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_block *
vtn_block(struct vtn_builder * b,uint32_t value_id)28 vtn_block(struct vtn_builder *b, uint32_t value_id)
29 {
30 return vtn_value(b, value_id, vtn_value_type_block)->block;
31 }
32
33 static unsigned
glsl_type_count_function_params(const struct glsl_type * type)34 glsl_type_count_function_params(const struct glsl_type *type)
35 {
36 if (glsl_type_is_vector_or_scalar(type)) {
37 return 1;
38 } else if (glsl_type_is_array_or_matrix(type)) {
39 return glsl_get_length(type) *
40 glsl_type_count_function_params(glsl_get_array_element(type));
41 } else {
42 assert(glsl_type_is_struct_or_ifc(type));
43 unsigned count = 0;
44 unsigned elems = glsl_get_length(type);
45 for (unsigned i = 0; i < elems; i++) {
46 const struct glsl_type *elem_type = glsl_get_struct_field(type, i);
47 count += glsl_type_count_function_params(elem_type);
48 }
49 return count;
50 }
51 }
52
53 static void
glsl_type_add_to_function_params(const struct glsl_type * type,nir_function * func,unsigned * param_idx)54 glsl_type_add_to_function_params(const struct glsl_type *type,
55 nir_function *func,
56 unsigned *param_idx)
57 {
58 if (glsl_type_is_vector_or_scalar(type)) {
59 func->params[(*param_idx)++] = (nir_parameter) {
60 .num_components = glsl_get_vector_elements(type),
61 .bit_size = glsl_get_bit_size(type),
62 };
63 } else if (glsl_type_is_array_or_matrix(type)) {
64 unsigned elems = glsl_get_length(type);
65 const struct glsl_type *elem_type = glsl_get_array_element(type);
66 for (unsigned i = 0; i < elems; i++)
67 glsl_type_add_to_function_params(elem_type,func, param_idx);
68 } else {
69 assert(glsl_type_is_struct_or_ifc(type));
70 unsigned elems = glsl_get_length(type);
71 for (unsigned i = 0; i < elems; i++) {
72 const struct glsl_type *elem_type = glsl_get_struct_field(type, i);
73 glsl_type_add_to_function_params(elem_type, func, param_idx);
74 }
75 }
76 }
77
78 static void
vtn_ssa_value_add_to_call_params(struct vtn_builder * b,struct vtn_ssa_value * value,nir_call_instr * call,unsigned * param_idx)79 vtn_ssa_value_add_to_call_params(struct vtn_builder *b,
80 struct vtn_ssa_value *value,
81 nir_call_instr *call,
82 unsigned *param_idx)
83 {
84 if (glsl_type_is_vector_or_scalar(value->type)) {
85 call->params[(*param_idx)++] = nir_src_for_ssa(value->def);
86 } else {
87 unsigned elems = glsl_get_length(value->type);
88 for (unsigned i = 0; i < elems; i++) {
89 vtn_ssa_value_add_to_call_params(b, value->elems[i],
90 call, param_idx);
91 }
92 }
93 }
94
95 static void
vtn_ssa_value_load_function_param(struct vtn_builder * b,struct vtn_ssa_value * value,unsigned * param_idx)96 vtn_ssa_value_load_function_param(struct vtn_builder *b,
97 struct vtn_ssa_value *value,
98 unsigned *param_idx)
99 {
100 if (glsl_type_is_vector_or_scalar(value->type)) {
101 value->def = nir_load_param(&b->nb, (*param_idx)++);
102 } else {
103 unsigned elems = glsl_get_length(value->type);
104 for (unsigned i = 0; i < elems; i++)
105 vtn_ssa_value_load_function_param(b, value->elems[i], param_idx);
106 }
107 }
108
109 void
vtn_handle_function_call(struct vtn_builder * b,SpvOp opcode,const uint32_t * w,unsigned count)110 vtn_handle_function_call(struct vtn_builder *b, SpvOp opcode,
111 const uint32_t *w, unsigned count)
112 {
113 struct vtn_function *vtn_callee =
114 vtn_value(b, w[3], vtn_value_type_function)->func;
115 struct nir_function *callee = vtn_callee->impl->function;
116
117 vtn_callee->referenced = true;
118
119 nir_call_instr *call = nir_call_instr_create(b->nb.shader, callee);
120
121 unsigned param_idx = 0;
122
123 nir_deref_instr *ret_deref = NULL;
124 struct vtn_type *ret_type = vtn_callee->type->return_type;
125 if (ret_type->base_type != vtn_base_type_void) {
126 nir_variable *ret_tmp =
127 nir_local_variable_create(b->nb.impl,
128 glsl_get_bare_type(ret_type->type),
129 "return_tmp");
130 ret_deref = nir_build_deref_var(&b->nb, ret_tmp);
131 call->params[param_idx++] = nir_src_for_ssa(&ret_deref->dest.ssa);
132 }
133
134 for (unsigned i = 0; i < vtn_callee->type->length; i++) {
135 vtn_ssa_value_add_to_call_params(b, vtn_ssa_value(b, w[4 + i]),
136 call, ¶m_idx);
137 }
138 assert(param_idx == call->num_params);
139
140 nir_builder_instr_insert(&b->nb, &call->instr);
141
142 if (ret_type->base_type == vtn_base_type_void) {
143 vtn_push_value(b, w[2], vtn_value_type_undef);
144 } else {
145 vtn_push_ssa_value(b, w[2], vtn_local_load(b, ret_deref, 0));
146 }
147 }
148
149 static bool
vtn_cfg_handle_prepass_instruction(struct vtn_builder * b,SpvOp opcode,const uint32_t * w,unsigned count)150 vtn_cfg_handle_prepass_instruction(struct vtn_builder *b, SpvOp opcode,
151 const uint32_t *w, unsigned count)
152 {
153 switch (opcode) {
154 case SpvOpFunction: {
155 vtn_assert(b->func == NULL);
156 b->func = rzalloc(b, struct vtn_function);
157
158 b->func->node.type = vtn_cf_node_type_function;
159 b->func->node.parent = NULL;
160 list_inithead(&b->func->body);
161 b->func->control = w[3];
162
163 UNUSED const struct glsl_type *result_type = vtn_get_type(b, w[1])->type;
164 struct vtn_value *val = vtn_push_value(b, w[2], vtn_value_type_function);
165 val->func = b->func;
166
167 b->func->type = vtn_get_type(b, w[4]);
168 const struct vtn_type *func_type = b->func->type;
169
170 vtn_assert(func_type->return_type->type == result_type);
171
172 nir_function *func =
173 nir_function_create(b->shader, ralloc_strdup(b->shader, val->name));
174
175 unsigned num_params = 0;
176 for (unsigned i = 0; i < func_type->length; i++)
177 num_params += glsl_type_count_function_params(func_type->params[i]->type);
178
179 /* Add one parameter for the function return value */
180 if (func_type->return_type->base_type != vtn_base_type_void)
181 num_params++;
182
183 func->num_params = num_params;
184 func->params = ralloc_array(b->shader, nir_parameter, num_params);
185
186 unsigned idx = 0;
187 if (func_type->return_type->base_type != vtn_base_type_void) {
188 nir_address_format addr_format =
189 vtn_mode_to_address_format(b, vtn_variable_mode_function);
190 /* The return value is a regular pointer */
191 func->params[idx++] = (nir_parameter) {
192 .num_components = nir_address_format_num_components(addr_format),
193 .bit_size = nir_address_format_bit_size(addr_format),
194 };
195 }
196
197 for (unsigned i = 0; i < func_type->length; i++)
198 glsl_type_add_to_function_params(func_type->params[i]->type, func, &idx);
199 assert(idx == num_params);
200
201 b->func->impl = nir_function_impl_create(func);
202 nir_builder_init(&b->nb, func->impl);
203 b->nb.cursor = nir_before_cf_list(&b->func->impl->body);
204 b->nb.exact = b->exact;
205
206 b->func_param_idx = 0;
207
208 /* The return value is the first parameter */
209 if (func_type->return_type->base_type != vtn_base_type_void)
210 b->func_param_idx++;
211 break;
212 }
213
214 case SpvOpFunctionEnd:
215 b->func->end = w;
216 b->func = NULL;
217 break;
218
219 case SpvOpFunctionParameter: {
220 vtn_assert(b->func_param_idx < b->func->impl->function->num_params);
221 struct vtn_type *type = vtn_get_type(b, w[1]);
222 struct vtn_ssa_value *value = vtn_create_ssa_value(b, type->type);
223 vtn_ssa_value_load_function_param(b, value, &b->func_param_idx);
224 vtn_push_ssa_value(b, w[2], value);
225 break;
226 }
227
228 case SpvOpLabel: {
229 vtn_assert(b->block == NULL);
230 b->block = rzalloc(b, struct vtn_block);
231 b->block->node.type = vtn_cf_node_type_block;
232 b->block->label = w;
233 vtn_push_value(b, w[1], vtn_value_type_block)->block = b->block;
234
235 if (b->func->start_block == NULL) {
236 /* This is the first block encountered for this function. In this
237 * case, we set the start block and add it to the list of
238 * implemented functions that we'll walk later.
239 */
240 b->func->start_block = b->block;
241 list_addtail(&b->func->node.link, &b->functions);
242 }
243 break;
244 }
245
246 case SpvOpSelectionMerge:
247 case SpvOpLoopMerge:
248 vtn_assert(b->block && b->block->merge == NULL);
249 b->block->merge = w;
250 break;
251
252 case SpvOpBranch:
253 case SpvOpBranchConditional:
254 case SpvOpSwitch:
255 case SpvOpKill:
256 case SpvOpReturn:
257 case SpvOpReturnValue:
258 case SpvOpUnreachable:
259 vtn_assert(b->block && b->block->branch == NULL);
260 b->block->branch = w;
261 b->block = NULL;
262 break;
263
264 default:
265 /* Continue on as per normal */
266 return true;
267 }
268
269 return true;
270 }
271
272 /* This function performs a depth-first search of the cases and puts them
273 * in fall-through order.
274 */
275 static void
vtn_order_case(struct vtn_switch * swtch,struct vtn_case * cse)276 vtn_order_case(struct vtn_switch *swtch, struct vtn_case *cse)
277 {
278 if (cse->visited)
279 return;
280
281 cse->visited = true;
282
283 list_del(&cse->node.link);
284
285 if (cse->fallthrough) {
286 vtn_order_case(swtch, cse->fallthrough);
287
288 /* If we have a fall-through, place this case right before the case it
289 * falls through to. This ensures that fallthroughs come one after
290 * the other. These two can never get separated because that would
291 * imply something else falling through to the same case. Also, this
292 * can't break ordering because the DFS ensures that this case is
293 * visited before anything that falls through to it.
294 */
295 list_addtail(&cse->node.link, &cse->fallthrough->node.link);
296 } else {
297 list_add(&cse->node.link, &swtch->cases);
298 }
299 }
300
301 static void
vtn_switch_order_cases(struct vtn_switch * swtch)302 vtn_switch_order_cases(struct vtn_switch *swtch)
303 {
304 struct list_head cases;
305 list_replace(&swtch->cases, &cases);
306 list_inithead(&swtch->cases);
307 while (!list_is_empty(&cases)) {
308 struct vtn_case *cse =
309 list_first_entry(&cases, struct vtn_case, node.link);
310 vtn_order_case(swtch, cse);
311 }
312 }
313
314 static void
vtn_block_set_merge_cf_node(struct vtn_builder * b,struct vtn_block * block,struct vtn_cf_node * cf_node)315 vtn_block_set_merge_cf_node(struct vtn_builder *b, struct vtn_block *block,
316 struct vtn_cf_node *cf_node)
317 {
318 vtn_fail_if(block->merge_cf_node != NULL,
319 "The merge block declared by a header block cannot be a "
320 "merge block declared by any other header block.");
321
322 block->merge_cf_node = cf_node;
323 }
324
325 #define VTN_DECL_CF_NODE_FIND(_type) \
326 static inline struct vtn_##_type * \
327 vtn_cf_node_find_##_type(struct vtn_cf_node *node) \
328 { \
329 while (node && node->type != vtn_cf_node_type_##_type) \
330 node = node->parent; \
331 return (struct vtn_##_type *)node; \
332 }
333
334 VTN_DECL_CF_NODE_FIND(if)
VTN_DECL_CF_NODE_FIND(loop)335 VTN_DECL_CF_NODE_FIND(loop)
336 VTN_DECL_CF_NODE_FIND(case)
337 VTN_DECL_CF_NODE_FIND(switch)
338 VTN_DECL_CF_NODE_FIND(function)
339
340 static enum vtn_branch_type
341 vtn_handle_branch(struct vtn_builder *b,
342 struct vtn_cf_node *cf_parent,
343 struct vtn_block *target_block)
344 {
345 struct vtn_loop *loop = vtn_cf_node_find_loop(cf_parent);
346
347 /* Detect a loop back-edge first. That way none of the code below
348 * accidentally operates on a loop back-edge.
349 */
350 if (loop && target_block == loop->header_block)
351 return vtn_branch_type_loop_back_edge;
352
353 /* Try to detect fall-through */
354 if (target_block->switch_case) {
355 /* When it comes to handling switch cases, we can break calls to
356 * vtn_handle_branch into two cases: calls from within a case construct
357 * and calls for the jump to each case construct. In the second case,
358 * cf_parent is the vtn_switch itself and vtn_cf_node_find_case() will
359 * return the outer switch case in which this switch is contained. It's
360 * fine if the target block is a switch case from an outer switch as
361 * long as it is also the switch break for this switch.
362 */
363 struct vtn_case *switch_case = vtn_cf_node_find_case(cf_parent);
364
365 /* This doesn't get called for the OpSwitch */
366 vtn_fail_if(switch_case == NULL,
367 "A switch case can only be entered through an OpSwitch or "
368 "falling through from another switch case.");
369
370 /* Because block->switch_case is only set on the entry block for a given
371 * switch case, we only ever get here if we're jumping to the start of a
372 * switch case. It's possible, however, that a switch case could jump
373 * to itself via a back-edge. That *should* get caught by the loop
374 * handling case above but if we have a back edge without a loop merge,
375 * we could en up here.
376 */
377 vtn_fail_if(target_block->switch_case == switch_case,
378 "A switch cannot fall-through to itself. Likely, there is "
379 "a back-edge which is not to a loop header.");
380
381 vtn_fail_if(target_block->switch_case->node.parent !=
382 switch_case->node.parent,
383 "A switch case fall-through must come from the same "
384 "OpSwitch construct");
385
386 vtn_fail_if(switch_case->fallthrough != NULL &&
387 switch_case->fallthrough != target_block->switch_case,
388 "Each case construct can have at most one branch to "
389 "another case construct");
390
391 switch_case->fallthrough = target_block->switch_case;
392
393 /* We don't immediately return vtn_branch_type_switch_fallthrough
394 * because it may also be a loop or switch break for an inner loop or
395 * switch and that takes precedence.
396 */
397 }
398
399 if (loop && target_block == loop->cont_block)
400 return vtn_branch_type_loop_continue;
401
402 /* We walk blocks as a breadth-first search on the control-flow construct
403 * tree where, when we find a construct, we add the vtn_cf_node for that
404 * construct and continue iterating at the merge target block (if any).
405 * Therefore, we want merges whose with parent == cf_parent to be treated
406 * as regular branches. We only want to consider merges if they break out
407 * of the current CF construct.
408 */
409 if (target_block->merge_cf_node != NULL &&
410 target_block->merge_cf_node->parent != cf_parent) {
411 switch (target_block->merge_cf_node->type) {
412 case vtn_cf_node_type_if:
413 for (struct vtn_cf_node *node = cf_parent;
414 node != target_block->merge_cf_node; node = node->parent) {
415 vtn_fail_if(node == NULL || node->type != vtn_cf_node_type_if,
416 "Branching to the merge block of a selection "
417 "construct can only be used to break out of a "
418 "selection construct");
419
420 struct vtn_if *if_stmt = vtn_cf_node_as_if(node);
421
422 /* This should be guaranteed by our iteration */
423 assert(if_stmt->merge_block != target_block);
424
425 vtn_fail_if(if_stmt->merge_block != NULL,
426 "Branching to the merge block of a selection "
427 "construct can only be used to break out of the "
428 "inner most nested selection level");
429 }
430 return vtn_branch_type_if_merge;
431
432 case vtn_cf_node_type_loop:
433 vtn_fail_if(target_block->merge_cf_node != &loop->node,
434 "Loop breaks can only break out of the inner most "
435 "nested loop level");
436 return vtn_branch_type_loop_break;
437
438 case vtn_cf_node_type_switch: {
439 struct vtn_switch *swtch = vtn_cf_node_find_switch(cf_parent);
440 vtn_fail_if(target_block->merge_cf_node != &swtch->node,
441 "Switch breaks can only break out of the inner most "
442 "nested switch level");
443 return vtn_branch_type_switch_break;
444 }
445
446 default:
447 unreachable("Invalid CF node type for a merge");
448 }
449 }
450
451 if (target_block->switch_case)
452 return vtn_branch_type_switch_fallthrough;
453
454 return vtn_branch_type_none;
455 }
456
457 struct vtn_cfg_work_item {
458 struct list_head link;
459
460 struct vtn_cf_node *cf_parent;
461 struct list_head *cf_list;
462 struct vtn_block *start_block;
463 };
464
465 static void
vtn_add_cfg_work_item(struct vtn_builder * b,struct list_head * work_list,struct vtn_cf_node * cf_parent,struct list_head * cf_list,struct vtn_block * start_block)466 vtn_add_cfg_work_item(struct vtn_builder *b,
467 struct list_head *work_list,
468 struct vtn_cf_node *cf_parent,
469 struct list_head *cf_list,
470 struct vtn_block *start_block)
471 {
472 struct vtn_cfg_work_item *work = ralloc(b, struct vtn_cfg_work_item);
473 work->cf_parent = cf_parent;
474 work->cf_list = cf_list;
475 work->start_block = start_block;
476 list_addtail(&work->link, work_list);
477 }
478
479 /* returns the default block */
480 static void
vtn_parse_switch(struct vtn_builder * b,struct vtn_switch * swtch,const uint32_t * branch,struct list_head * case_list)481 vtn_parse_switch(struct vtn_builder *b,
482 struct vtn_switch *swtch,
483 const uint32_t *branch,
484 struct list_head *case_list)
485 {
486 const uint32_t *branch_end = branch + (branch[0] >> SpvWordCountShift);
487
488 struct vtn_value *sel_val = vtn_untyped_value(b, branch[1]);
489 vtn_fail_if(!sel_val->type ||
490 sel_val->type->base_type != vtn_base_type_scalar,
491 "Selector of OpSwitch must have a type of OpTypeInt");
492
493 nir_alu_type sel_type =
494 nir_get_nir_type_for_glsl_type(sel_val->type->type);
495 vtn_fail_if(nir_alu_type_get_base_type(sel_type) != nir_type_int &&
496 nir_alu_type_get_base_type(sel_type) != nir_type_uint,
497 "Selector of OpSwitch must have a type of OpTypeInt");
498
499 struct hash_table *block_to_case = _mesa_pointer_hash_table_create(b);
500
501 bool is_default = true;
502 const unsigned bitsize = nir_alu_type_get_type_size(sel_type);
503 for (const uint32_t *w = branch + 2; w < branch_end;) {
504 uint64_t literal = 0;
505 if (!is_default) {
506 if (bitsize <= 32) {
507 literal = *(w++);
508 } else {
509 assert(bitsize == 64);
510 literal = vtn_u64_literal(w);
511 w += 2;
512 }
513 }
514 struct vtn_block *case_block = vtn_block(b, *(w++));
515
516 struct hash_entry *case_entry =
517 _mesa_hash_table_search(block_to_case, case_block);
518
519 struct vtn_case *cse;
520 if (case_entry) {
521 cse = case_entry->data;
522 } else {
523 cse = rzalloc(b, struct vtn_case);
524
525 cse->node.type = vtn_cf_node_type_case;
526 cse->node.parent = swtch ? &swtch->node : NULL;
527 cse->block = case_block;
528 list_inithead(&cse->body);
529 util_dynarray_init(&cse->values, b);
530
531 list_addtail(&cse->node.link, case_list);
532 _mesa_hash_table_insert(block_to_case, case_block, cse);
533 }
534
535 if (is_default) {
536 cse->is_default = true;
537 } else {
538 util_dynarray_append(&cse->values, uint64_t, literal);
539 }
540
541 is_default = false;
542 }
543
544 _mesa_hash_table_destroy(block_to_case, NULL);
545 }
546
547 /* Processes a block and returns the next block to process or NULL if we've
548 * reached the end of the construct.
549 */
550 static struct vtn_block *
vtn_process_block(struct vtn_builder * b,struct list_head * work_list,struct vtn_cf_node * cf_parent,struct list_head * cf_list,struct vtn_block * block)551 vtn_process_block(struct vtn_builder *b,
552 struct list_head *work_list,
553 struct vtn_cf_node *cf_parent,
554 struct list_head *cf_list,
555 struct vtn_block *block)
556 {
557 if (!list_is_empty(cf_list)) {
558 /* vtn_process_block() acts like an iterator: it processes the given
559 * block and then returns the next block to process. For a given
560 * control-flow construct, vtn_build_cfg() calls vtn_process_block()
561 * repeatedly until it finally returns NULL. Therefore, we know that
562 * the only blocks on which vtn_process_block() can be called are either
563 * the first block in a construct or a block that vtn_process_block()
564 * returned for the current construct. If cf_list is empty then we know
565 * that we're processing the first block in the construct and we have to
566 * add it to the list.
567 *
568 * If cf_list is not empty, then it must be the block returned by the
569 * previous call to vtn_process_block(). We know a priori that
570 * vtn_process_block only returns either normal branches
571 * (vtn_branch_type_none) or merge target blocks.
572 */
573 switch (vtn_handle_branch(b, cf_parent, block)) {
574 case vtn_branch_type_none:
575 /* For normal branches, we want to process them and add them to the
576 * current construct. Merge target blocks also look like normal
577 * branches from the perspective of this construct. See also
578 * vtn_handle_branch().
579 */
580 break;
581
582 case vtn_branch_type_loop_continue:
583 case vtn_branch_type_switch_fallthrough:
584 /* The two cases where we can get early exits from a construct that
585 * are not to that construct's merge target are loop continues and
586 * switch fall-throughs. In these cases, we need to break out of the
587 * current construct by returning NULL.
588 */
589 return NULL;
590
591 default:
592 /* The only way we can get here is if something was used as two kinds
593 * of merges at the same time and that's illegal.
594 */
595 vtn_fail("A block was used as a merge target from two or more "
596 "structured control-flow constructs");
597 }
598 }
599
600 /* Once a block has been processed, it is placed into and the list link
601 * will point to something non-null. If we see a node we've already
602 * processed here, it either exists in multiple functions or it's an
603 * invalid back-edge.
604 */
605 if (block->node.parent != NULL) {
606 vtn_fail_if(vtn_cf_node_find_function(&block->node) !=
607 vtn_cf_node_find_function(cf_parent),
608 "A block cannot exist in two functions at the "
609 "same time");
610
611 vtn_fail("Invalid back or cross-edge in the CFG");
612 }
613
614 if (block->merge && (*block->merge & SpvOpCodeMask) == SpvOpLoopMerge &&
615 block->loop == NULL) {
616 vtn_fail_if((*block->branch & SpvOpCodeMask) != SpvOpBranch &&
617 (*block->branch & SpvOpCodeMask) != SpvOpBranchConditional,
618 "An OpLoopMerge instruction must immediately precede "
619 "either an OpBranch or OpBranchConditional instruction.");
620
621 struct vtn_loop *loop = rzalloc(b, struct vtn_loop);
622
623 loop->node.type = vtn_cf_node_type_loop;
624 loop->node.parent = cf_parent;
625 list_inithead(&loop->body);
626 list_inithead(&loop->cont_body);
627 loop->header_block = block;
628 loop->break_block = vtn_block(b, block->merge[1]);
629 loop->cont_block = vtn_block(b, block->merge[2]);
630 loop->control = block->merge[3];
631
632 list_addtail(&loop->node.link, cf_list);
633 block->loop = loop;
634
635 /* Note: The work item for the main loop body will start with the
636 * current block as its start block. If we weren't careful, we would
637 * get here again and end up in an infinite loop. This is why we set
638 * block->loop above and check for it before creating one. This way,
639 * we only create the loop once and the second iteration that tries to
640 * handle this loop goes to the cases below and gets handled as a
641 * regular block.
642 */
643 vtn_add_cfg_work_item(b, work_list, &loop->node,
644 &loop->body, loop->header_block);
645
646 /* For continue targets, SPIR-V guarantees the following:
647 *
648 * - the Continue Target must dominate the back-edge block
649 * - the back-edge block must post dominate the Continue Target
650 *
651 * If the header block is the same as the continue target, this
652 * condition is trivially satisfied and there is no real continue
653 * section.
654 */
655 if (loop->cont_block != loop->header_block) {
656 vtn_add_cfg_work_item(b, work_list, &loop->node,
657 &loop->cont_body, loop->cont_block);
658 }
659
660 vtn_block_set_merge_cf_node(b, loop->break_block, &loop->node);
661
662 return loop->break_block;
663 }
664
665 /* Add the block to the CF list */
666 block->node.parent = cf_parent;
667 list_addtail(&block->node.link, cf_list);
668
669 switch (*block->branch & SpvOpCodeMask) {
670 case SpvOpBranch: {
671 struct vtn_block *branch_block = vtn_block(b, block->branch[1]);
672
673 block->branch_type = vtn_handle_branch(b, cf_parent, branch_block);
674
675 if (block->branch_type == vtn_branch_type_none)
676 return branch_block;
677 else
678 return NULL;
679 }
680
681 case SpvOpReturn:
682 case SpvOpReturnValue:
683 block->branch_type = vtn_branch_type_return;
684 return NULL;
685
686 case SpvOpKill:
687 b->has_kill = true;
688 block->branch_type = vtn_branch_type_discard;
689 return NULL;
690
691 case SpvOpBranchConditional: {
692 struct vtn_value *cond_val = vtn_untyped_value(b, block->branch[1]);
693 vtn_fail_if(!cond_val->type ||
694 cond_val->type->base_type != vtn_base_type_scalar ||
695 cond_val->type->type != glsl_bool_type(),
696 "Condition must be a Boolean type scalar");
697
698 struct vtn_block *then_block = vtn_block(b, block->branch[2]);
699 struct vtn_block *else_block = vtn_block(b, block->branch[3]);
700
701 if (then_block == else_block) {
702 /* This is uncommon but it can happen. We treat this the same way as
703 * an unconditional branch.
704 */
705 block->branch_type = vtn_handle_branch(b, cf_parent, then_block);
706
707 if (block->branch_type == vtn_branch_type_none)
708 return then_block;
709 else
710 return NULL;
711 }
712
713 struct vtn_if *if_stmt = rzalloc(b, struct vtn_if);
714
715 if_stmt->node.type = vtn_cf_node_type_if;
716 if_stmt->node.parent = cf_parent;
717 if_stmt->condition = block->branch[1];
718 list_inithead(&if_stmt->then_body);
719 list_inithead(&if_stmt->else_body);
720
721 list_addtail(&if_stmt->node.link, cf_list);
722
723 if (block->merge &&
724 (*block->merge & SpvOpCodeMask) == SpvOpSelectionMerge) {
725 /* We may not always have a merge block and that merge doesn't
726 * technically have to be an OpSelectionMerge. We could have a block
727 * with an OpLoopMerge which ends in an OpBranchConditional.
728 */
729 if_stmt->merge_block = vtn_block(b, block->merge[1]);
730 vtn_block_set_merge_cf_node(b, if_stmt->merge_block, &if_stmt->node);
731
732 if_stmt->control = block->merge[2];
733 }
734
735 if_stmt->then_type = vtn_handle_branch(b, &if_stmt->node, then_block);
736 if (if_stmt->then_type == vtn_branch_type_none) {
737 vtn_add_cfg_work_item(b, work_list, &if_stmt->node,
738 &if_stmt->then_body, then_block);
739 }
740
741 if_stmt->else_type = vtn_handle_branch(b, &if_stmt->node, else_block);
742 if (if_stmt->else_type == vtn_branch_type_none) {
743 vtn_add_cfg_work_item(b, work_list, &if_stmt->node,
744 &if_stmt->else_body, else_block);
745 }
746
747 return if_stmt->merge_block;
748 }
749
750 case SpvOpSwitch: {
751 struct vtn_switch *swtch = rzalloc(b, struct vtn_switch);
752
753 swtch->node.type = vtn_cf_node_type_switch;
754 swtch->node.parent = cf_parent;
755 swtch->selector = block->branch[1];
756 list_inithead(&swtch->cases);
757
758 list_addtail(&swtch->node.link, cf_list);
759
760 /* We may not always have a merge block */
761 if (block->merge) {
762 vtn_fail_if((*block->merge & SpvOpCodeMask) != SpvOpSelectionMerge,
763 "An OpLoopMerge instruction must immediately precede "
764 "either an OpBranch or OpBranchConditional "
765 "instruction.");
766 swtch->break_block = vtn_block(b, block->merge[1]);
767 vtn_block_set_merge_cf_node(b, swtch->break_block, &swtch->node);
768 }
769
770 /* First, we go through and record all of the cases. */
771 vtn_parse_switch(b, swtch, block->branch, &swtch->cases);
772
773 /* Gather the branch types for the switch */
774 vtn_foreach_cf_node(case_node, &swtch->cases) {
775 struct vtn_case *cse = vtn_cf_node_as_case(case_node);
776
777 cse->type = vtn_handle_branch(b, &swtch->node, cse->block);
778 switch (cse->type) {
779 case vtn_branch_type_none:
780 /* This is a "real" cases which has stuff in it */
781 vtn_fail_if(cse->block->switch_case != NULL,
782 "OpSwitch has a case which is also in another "
783 "OpSwitch construct");
784 cse->block->switch_case = cse;
785 vtn_add_cfg_work_item(b, work_list, &cse->node,
786 &cse->body, cse->block);
787 break;
788
789 case vtn_branch_type_switch_break:
790 case vtn_branch_type_loop_break:
791 case vtn_branch_type_loop_continue:
792 /* Switch breaks as well as loop breaks and continues can be
793 * used to break out of a switch construct or as direct targets
794 * of the OpSwitch.
795 */
796 break;
797
798 default:
799 vtn_fail("Target of OpSwitch is not a valid structured exit "
800 "from the switch construct.");
801 }
802 }
803
804 return swtch->break_block;
805 }
806
807 case SpvOpUnreachable:
808 return NULL;
809
810 default:
811 vtn_fail("Block did not end with a valid branch instruction");
812 }
813 }
814
815 void
vtn_build_cfg(struct vtn_builder * b,const uint32_t * words,const uint32_t * end)816 vtn_build_cfg(struct vtn_builder *b, const uint32_t *words, const uint32_t *end)
817 {
818 vtn_foreach_instruction(b, words, end,
819 vtn_cfg_handle_prepass_instruction);
820
821 vtn_foreach_cf_node(func_node, &b->functions) {
822 struct vtn_function *func = vtn_cf_node_as_function(func_node);
823
824 /* We build the CFG for each function by doing a breadth-first search on
825 * the control-flow graph. We keep track of our state using a worklist.
826 * Doing a BFS ensures that we visit each structured control-flow
827 * construct and its merge node before we visit the stuff inside the
828 * construct.
829 */
830 struct list_head work_list;
831 list_inithead(&work_list);
832 vtn_add_cfg_work_item(b, &work_list, &func->node, &func->body,
833 func->start_block);
834
835 while (!list_is_empty(&work_list)) {
836 struct vtn_cfg_work_item *work =
837 list_first_entry(&work_list, struct vtn_cfg_work_item, link);
838 list_del(&work->link);
839
840 for (struct vtn_block *block = work->start_block; block; ) {
841 block = vtn_process_block(b, &work_list, work->cf_parent,
842 work->cf_list, block);
843 }
844 }
845 }
846 }
847
848 static bool
vtn_handle_phis_first_pass(struct vtn_builder * b,SpvOp opcode,const uint32_t * w,unsigned count)849 vtn_handle_phis_first_pass(struct vtn_builder *b, SpvOp opcode,
850 const uint32_t *w, unsigned count)
851 {
852 if (opcode == SpvOpLabel)
853 return true; /* Nothing to do */
854
855 /* If this isn't a phi node, stop. */
856 if (opcode != SpvOpPhi)
857 return false;
858
859 /* For handling phi nodes, we do a poor-man's out-of-ssa on the spot.
860 * For each phi, we create a variable with the appropreate type and
861 * do a load from that variable. Then, in a second pass, we add
862 * stores to that variable to each of the predecessor blocks.
863 *
864 * We could do something more intelligent here. However, in order to
865 * handle loops and things properly, we really need dominance
866 * information. It would end up basically being the into-SSA
867 * algorithm all over again. It's easier if we just let
868 * lower_vars_to_ssa do that for us instead of repeating it here.
869 */
870 struct vtn_type *type = vtn_get_type(b, w[1]);
871 nir_variable *phi_var =
872 nir_local_variable_create(b->nb.impl, type->type, "phi");
873 _mesa_hash_table_insert(b->phi_table, w, phi_var);
874
875 vtn_push_ssa_value(b, w[2],
876 vtn_local_load(b, nir_build_deref_var(&b->nb, phi_var), 0));
877
878 return true;
879 }
880
881 static bool
vtn_handle_phi_second_pass(struct vtn_builder * b,SpvOp opcode,const uint32_t * w,unsigned count)882 vtn_handle_phi_second_pass(struct vtn_builder *b, SpvOp opcode,
883 const uint32_t *w, unsigned count)
884 {
885 if (opcode != SpvOpPhi)
886 return true;
887
888 struct hash_entry *phi_entry = _mesa_hash_table_search(b->phi_table, w);
889
890 /* It's possible that this phi is in an unreachable block in which case it
891 * may never have been emitted and therefore may not be in the hash table.
892 * In this case, there's no var for it and it's safe to just bail.
893 */
894 if (phi_entry == NULL)
895 return true;
896
897 nir_variable *phi_var = phi_entry->data;
898
899 for (unsigned i = 3; i < count; i += 2) {
900 struct vtn_block *pred = vtn_block(b, w[i + 1]);
901
902 /* If block does not have end_nop, that is because it is an unreacheable
903 * block, and hence it is not worth to handle it */
904 if (!pred->end_nop)
905 continue;
906
907 b->nb.cursor = nir_after_instr(&pred->end_nop->instr);
908
909 struct vtn_ssa_value *src = vtn_ssa_value(b, w[i]);
910
911 vtn_local_store(b, src, nir_build_deref_var(&b->nb, phi_var), 0);
912 }
913
914 return true;
915 }
916
917 static void
vtn_emit_branch(struct vtn_builder * b,enum vtn_branch_type branch_type,nir_variable * switch_fall_var,bool * has_switch_break)918 vtn_emit_branch(struct vtn_builder *b, enum vtn_branch_type branch_type,
919 nir_variable *switch_fall_var, bool *has_switch_break)
920 {
921 switch (branch_type) {
922 case vtn_branch_type_if_merge:
923 break; /* Nothing to do */
924 case vtn_branch_type_switch_break:
925 nir_store_var(&b->nb, switch_fall_var, nir_imm_false(&b->nb), 1);
926 *has_switch_break = true;
927 break;
928 case vtn_branch_type_switch_fallthrough:
929 break; /* Nothing to do */
930 case vtn_branch_type_loop_break:
931 nir_jump(&b->nb, nir_jump_break);
932 break;
933 case vtn_branch_type_loop_continue:
934 nir_jump(&b->nb, nir_jump_continue);
935 break;
936 case vtn_branch_type_loop_back_edge:
937 break;
938 case vtn_branch_type_return:
939 nir_jump(&b->nb, nir_jump_return);
940 break;
941 case vtn_branch_type_discard: {
942 nir_intrinsic_op op =
943 b->convert_discard_to_demote ? nir_intrinsic_demote : nir_intrinsic_discard;
944 nir_intrinsic_instr *discard =
945 nir_intrinsic_instr_create(b->nb.shader, op);
946 nir_builder_instr_insert(&b->nb, &discard->instr);
947 break;
948 }
949 default:
950 vtn_fail("Invalid branch type");
951 }
952 }
953
954 static nir_ssa_def *
vtn_switch_case_condition(struct vtn_builder * b,struct vtn_switch * swtch,nir_ssa_def * sel,struct vtn_case * cse)955 vtn_switch_case_condition(struct vtn_builder *b, struct vtn_switch *swtch,
956 nir_ssa_def *sel, struct vtn_case *cse)
957 {
958 if (cse->is_default) {
959 nir_ssa_def *any = nir_imm_false(&b->nb);
960 vtn_foreach_cf_node(other_node, &swtch->cases) {
961 struct vtn_case *other = vtn_cf_node_as_case(other_node);
962 if (other->is_default)
963 continue;
964
965 any = nir_ior(&b->nb, any,
966 vtn_switch_case_condition(b, swtch, sel, other));
967 }
968 return nir_inot(&b->nb, any);
969 } else {
970 nir_ssa_def *cond = nir_imm_false(&b->nb);
971 util_dynarray_foreach(&cse->values, uint64_t, val) {
972 nir_ssa_def *imm = nir_imm_intN_t(&b->nb, *val, sel->bit_size);
973 cond = nir_ior(&b->nb, cond, nir_ieq(&b->nb, sel, imm));
974 }
975 return cond;
976 }
977 }
978
979 static nir_loop_control
vtn_loop_control(struct vtn_builder * b,struct vtn_loop * vtn_loop)980 vtn_loop_control(struct vtn_builder *b, struct vtn_loop *vtn_loop)
981 {
982 if (vtn_loop->control == SpvLoopControlMaskNone)
983 return nir_loop_control_none;
984 else if (vtn_loop->control & SpvLoopControlDontUnrollMask)
985 return nir_loop_control_dont_unroll;
986 else if (vtn_loop->control & SpvLoopControlUnrollMask)
987 return nir_loop_control_unroll;
988 else if (vtn_loop->control & SpvLoopControlDependencyInfiniteMask ||
989 vtn_loop->control & SpvLoopControlDependencyLengthMask ||
990 vtn_loop->control & SpvLoopControlMinIterationsMask ||
991 vtn_loop->control & SpvLoopControlMaxIterationsMask ||
992 vtn_loop->control & SpvLoopControlIterationMultipleMask ||
993 vtn_loop->control & SpvLoopControlPeelCountMask ||
994 vtn_loop->control & SpvLoopControlPartialCountMask) {
995 /* We do not do anything special with these yet. */
996 return nir_loop_control_none;
997 } else {
998 vtn_fail("Invalid loop control");
999 }
1000 }
1001
1002 static nir_selection_control
vtn_selection_control(struct vtn_builder * b,struct vtn_if * vtn_if)1003 vtn_selection_control(struct vtn_builder *b, struct vtn_if *vtn_if)
1004 {
1005 if (vtn_if->control == SpvSelectionControlMaskNone)
1006 return nir_selection_control_none;
1007 else if (vtn_if->control & SpvSelectionControlDontFlattenMask)
1008 return nir_selection_control_dont_flatten;
1009 else if (vtn_if->control & SpvSelectionControlFlattenMask)
1010 return nir_selection_control_flatten;
1011 else
1012 vtn_fail("Invalid selection control");
1013 }
1014
1015 static void
vtn_emit_cf_list(struct vtn_builder * b,struct list_head * cf_list,nir_variable * switch_fall_var,bool * has_switch_break,vtn_instruction_handler handler)1016 vtn_emit_cf_list(struct vtn_builder *b, struct list_head *cf_list,
1017 nir_variable *switch_fall_var, bool *has_switch_break,
1018 vtn_instruction_handler handler)
1019 {
1020 vtn_foreach_cf_node(node, cf_list) {
1021 switch (node->type) {
1022 case vtn_cf_node_type_block: {
1023 struct vtn_block *block = vtn_cf_node_as_block(node);
1024
1025 const uint32_t *block_start = block->label;
1026 const uint32_t *block_end = block->merge ? block->merge :
1027 block->branch;
1028
1029 block_start = vtn_foreach_instruction(b, block_start, block_end,
1030 vtn_handle_phis_first_pass);
1031
1032 vtn_foreach_instruction(b, block_start, block_end, handler);
1033
1034 block->end_nop = nir_intrinsic_instr_create(b->nb.shader,
1035 nir_intrinsic_nop);
1036 nir_builder_instr_insert(&b->nb, &block->end_nop->instr);
1037
1038 if ((*block->branch & SpvOpCodeMask) == SpvOpReturnValue) {
1039 vtn_fail_if(b->func->type->return_type->base_type ==
1040 vtn_base_type_void,
1041 "Return with a value from a function returning void");
1042 struct vtn_ssa_value *src = vtn_ssa_value(b, block->branch[1]);
1043 const struct glsl_type *ret_type =
1044 glsl_get_bare_type(b->func->type->return_type->type);
1045 nir_deref_instr *ret_deref =
1046 nir_build_deref_cast(&b->nb, nir_load_param(&b->nb, 0),
1047 nir_var_function_temp, ret_type, 0);
1048 vtn_local_store(b, src, ret_deref, 0);
1049 }
1050
1051 if (block->branch_type != vtn_branch_type_none) {
1052 vtn_emit_branch(b, block->branch_type,
1053 switch_fall_var, has_switch_break);
1054 return;
1055 }
1056
1057 break;
1058 }
1059
1060 case vtn_cf_node_type_if: {
1061 struct vtn_if *vtn_if = vtn_cf_node_as_if(node);
1062 bool sw_break = false;
1063
1064 nir_if *nif =
1065 nir_push_if(&b->nb, vtn_get_nir_ssa(b, vtn_if->condition));
1066
1067 nif->control = vtn_selection_control(b, vtn_if);
1068
1069 if (vtn_if->then_type == vtn_branch_type_none) {
1070 vtn_emit_cf_list(b, &vtn_if->then_body,
1071 switch_fall_var, &sw_break, handler);
1072 } else {
1073 vtn_emit_branch(b, vtn_if->then_type, switch_fall_var, &sw_break);
1074 }
1075
1076 nir_push_else(&b->nb, nif);
1077 if (vtn_if->else_type == vtn_branch_type_none) {
1078 vtn_emit_cf_list(b, &vtn_if->else_body,
1079 switch_fall_var, &sw_break, handler);
1080 } else {
1081 vtn_emit_branch(b, vtn_if->else_type, switch_fall_var, &sw_break);
1082 }
1083
1084 nir_pop_if(&b->nb, nif);
1085
1086 /* If we encountered a switch break somewhere inside of the if,
1087 * then it would have been handled correctly by calling
1088 * emit_cf_list or emit_branch for the interrior. However, we
1089 * need to predicate everything following on wether or not we're
1090 * still going.
1091 */
1092 if (sw_break) {
1093 *has_switch_break = true;
1094 nir_push_if(&b->nb, nir_load_var(&b->nb, switch_fall_var));
1095 }
1096 break;
1097 }
1098
1099 case vtn_cf_node_type_loop: {
1100 struct vtn_loop *vtn_loop = vtn_cf_node_as_loop(node);
1101
1102 nir_loop *loop = nir_push_loop(&b->nb);
1103 loop->control = vtn_loop_control(b, vtn_loop);
1104
1105 vtn_emit_cf_list(b, &vtn_loop->body, NULL, NULL, handler);
1106
1107 if (!list_is_empty(&vtn_loop->cont_body)) {
1108 /* If we have a non-trivial continue body then we need to put
1109 * it at the beginning of the loop with a flag to ensure that
1110 * it doesn't get executed in the first iteration.
1111 */
1112 nir_variable *do_cont =
1113 nir_local_variable_create(b->nb.impl, glsl_bool_type(), "cont");
1114
1115 b->nb.cursor = nir_before_cf_node(&loop->cf_node);
1116 nir_store_var(&b->nb, do_cont, nir_imm_false(&b->nb), 1);
1117
1118 b->nb.cursor = nir_before_cf_list(&loop->body);
1119
1120 nir_if *cont_if =
1121 nir_push_if(&b->nb, nir_load_var(&b->nb, do_cont));
1122
1123 vtn_emit_cf_list(b, &vtn_loop->cont_body, NULL, NULL, handler);
1124
1125 nir_pop_if(&b->nb, cont_if);
1126
1127 nir_store_var(&b->nb, do_cont, nir_imm_true(&b->nb), 1);
1128
1129 b->has_loop_continue = true;
1130 }
1131
1132 nir_pop_loop(&b->nb, loop);
1133 break;
1134 }
1135
1136 case vtn_cf_node_type_switch: {
1137 struct vtn_switch *vtn_switch = vtn_cf_node_as_switch(node);
1138
1139 /* Before we can emit anything, we need to sort the list of cases in
1140 * fall-through order.
1141 */
1142 vtn_switch_order_cases(vtn_switch);
1143
1144 /* First, we create a variable to keep track of whether or not the
1145 * switch is still going at any given point. Any switch breaks
1146 * will set this variable to false.
1147 */
1148 nir_variable *fall_var =
1149 nir_local_variable_create(b->nb.impl, glsl_bool_type(), "fall");
1150 nir_store_var(&b->nb, fall_var, nir_imm_false(&b->nb), 1);
1151
1152 nir_ssa_def *sel = vtn_get_nir_ssa(b, vtn_switch->selector);
1153
1154 /* Now we can walk the list of cases and actually emit code */
1155 vtn_foreach_cf_node(case_node, &vtn_switch->cases) {
1156 struct vtn_case *cse = vtn_cf_node_as_case(case_node);
1157
1158 /* If this case jumps directly to the break block, we don't have
1159 * to handle the case as the body is empty and doesn't fall
1160 * through.
1161 */
1162 if (cse->block == vtn_switch->break_block)
1163 continue;
1164
1165 /* Figure out the condition */
1166 nir_ssa_def *cond =
1167 vtn_switch_case_condition(b, vtn_switch, sel, cse);
1168 /* Take fallthrough into account */
1169 cond = nir_ior(&b->nb, cond, nir_load_var(&b->nb, fall_var));
1170
1171 nir_if *case_if = nir_push_if(&b->nb, cond);
1172
1173 bool has_break = false;
1174 nir_store_var(&b->nb, fall_var, nir_imm_true(&b->nb), 1);
1175 vtn_emit_cf_list(b, &cse->body, fall_var, &has_break, handler);
1176 (void)has_break; /* We don't care */
1177
1178 nir_pop_if(&b->nb, case_if);
1179 }
1180
1181 break;
1182 }
1183
1184 default:
1185 vtn_fail("Invalid CF node type");
1186 }
1187 }
1188 }
1189
1190 void
vtn_function_emit(struct vtn_builder * b,struct vtn_function * func,vtn_instruction_handler instruction_handler)1191 vtn_function_emit(struct vtn_builder *b, struct vtn_function *func,
1192 vtn_instruction_handler instruction_handler)
1193 {
1194 nir_builder_init(&b->nb, func->impl);
1195 b->func = func;
1196 b->nb.cursor = nir_after_cf_list(&func->impl->body);
1197 b->nb.exact = b->exact;
1198 b->has_loop_continue = false;
1199 b->phi_table = _mesa_pointer_hash_table_create(b);
1200
1201 vtn_emit_cf_list(b, &func->body, NULL, NULL, instruction_handler);
1202
1203 vtn_foreach_instruction(b, func->start_block->label, func->end,
1204 vtn_handle_phi_second_pass);
1205
1206 nir_rematerialize_derefs_in_use_blocks_impl(func->impl);
1207
1208 /* Continue blocks for loops get inserted before the body of the loop
1209 * but instructions in the continue may use SSA defs in the loop body.
1210 * Therefore, we need to repair SSA to insert the needed phi nodes.
1211 */
1212 if (b->has_loop_continue || b->has_kill)
1213 nir_repair_ssa_impl(func->impl);
1214
1215 func->emitted = true;
1216 }
1217