2 * Copyright © 2015 Intel Corporation
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
24 #include "vtn_private.h"
25 #include "nir/nir_vla.h"
27 static struct vtn_block
*
28 vtn_block(struct vtn_builder
*b
, uint32_t value_id
)
30 return vtn_value(b
, value_id
, vtn_value_type_block
)->block
;
33 static struct vtn_pointer
*
34 vtn_load_param_pointer(struct vtn_builder
*b
,
35 struct vtn_type
*param_type
,
38 struct vtn_type
*ptr_type
= param_type
;
39 if (param_type
->base_type
!= vtn_base_type_pointer
) {
40 assert(param_type
->base_type
== vtn_base_type_image
||
41 param_type
->base_type
== vtn_base_type_sampler
);
42 ptr_type
= rzalloc(b
, struct vtn_type
);
43 ptr_type
->base_type
= vtn_base_type_pointer
;
44 ptr_type
->deref
= param_type
;
45 ptr_type
->storage_class
= SpvStorageClassUniformConstant
;
48 return vtn_pointer_from_ssa(b
, nir_load_param(&b
->nb
, param_idx
), ptr_type
);
52 vtn_type_count_function_params(struct vtn_type
*type
)
54 switch (type
->base_type
) {
55 case vtn_base_type_array
:
56 case vtn_base_type_matrix
:
57 return type
->length
* vtn_type_count_function_params(type
->array_element
);
59 case vtn_base_type_struct
: {
61 for (unsigned i
= 0; i
< type
->length
; i
++)
62 count
+= vtn_type_count_function_params(type
->members
[i
]);
66 case vtn_base_type_sampled_image
:
75 vtn_type_add_to_function_params(struct vtn_type
*type
,
79 static const nir_parameter nir_deref_param
= {
84 switch (type
->base_type
) {
85 case vtn_base_type_array
:
86 case vtn_base_type_matrix
:
87 for (unsigned i
= 0; i
< type
->length
; i
++)
88 vtn_type_add_to_function_params(type
->array_element
, func
, param_idx
);
91 case vtn_base_type_struct
:
92 for (unsigned i
= 0; i
< type
->length
; i
++)
93 vtn_type_add_to_function_params(type
->members
[i
], func
, param_idx
);
96 case vtn_base_type_sampled_image
:
97 func
->params
[(*param_idx
)++] = nir_deref_param
;
98 func
->params
[(*param_idx
)++] = nir_deref_param
;
101 case vtn_base_type_image
:
102 case vtn_base_type_sampler
:
103 func
->params
[(*param_idx
)++] = nir_deref_param
;
106 case vtn_base_type_pointer
:
108 func
->params
[(*param_idx
)++] = (nir_parameter
) {
109 .num_components
= glsl_get_vector_elements(type
->type
),
110 .bit_size
= glsl_get_bit_size(type
->type
),
113 func
->params
[(*param_idx
)++] = nir_deref_param
;
118 func
->params
[(*param_idx
)++] = (nir_parameter
) {
119 .num_components
= glsl_get_vector_elements(type
->type
),
120 .bit_size
= glsl_get_bit_size(type
->type
),
126 vtn_ssa_value_add_to_call_params(struct vtn_builder
*b
,
127 struct vtn_ssa_value
*value
,
128 struct vtn_type
*type
,
129 nir_call_instr
*call
,
132 switch (type
->base_type
) {
133 case vtn_base_type_array
:
134 case vtn_base_type_matrix
:
135 for (unsigned i
= 0; i
< type
->length
; i
++) {
136 vtn_ssa_value_add_to_call_params(b
, value
->elems
[i
],
142 case vtn_base_type_struct
:
143 for (unsigned i
= 0; i
< type
->length
; i
++) {
144 vtn_ssa_value_add_to_call_params(b
, value
->elems
[i
],
151 call
->params
[(*param_idx
)++] = nir_src_for_ssa(value
->def
);
157 vtn_ssa_value_load_function_param(struct vtn_builder
*b
,
158 struct vtn_ssa_value
*value
,
159 struct vtn_type
*type
,
162 switch (type
->base_type
) {
163 case vtn_base_type_array
:
164 case vtn_base_type_matrix
:
165 for (unsigned i
= 0; i
< type
->length
; i
++) {
166 vtn_ssa_value_load_function_param(b
, value
->elems
[i
],
167 type
->array_element
, param_idx
);
171 case vtn_base_type_struct
:
172 for (unsigned i
= 0; i
< type
->length
; i
++) {
173 vtn_ssa_value_load_function_param(b
, value
->elems
[i
],
174 type
->members
[i
], param_idx
);
179 value
->def
= nir_load_param(&b
->nb
, (*param_idx
)++);
185 vtn_handle_function_call(struct vtn_builder
*b
, SpvOp opcode
,
186 const uint32_t *w
, unsigned count
)
188 struct vtn_type
*res_type
= vtn_get_type(b
, w
[1]);
189 struct vtn_function
*vtn_callee
=
190 vtn_value(b
, w
[3], vtn_value_type_function
)->func
;
191 struct nir_function
*callee
= vtn_callee
->impl
->function
;
193 vtn_callee
->referenced
= true;
195 nir_call_instr
*call
= nir_call_instr_create(b
->nb
.shader
, callee
);
197 unsigned param_idx
= 0;
199 nir_deref_instr
*ret_deref
= NULL
;
200 struct vtn_type
*ret_type
= vtn_callee
->type
->return_type
;
201 if (ret_type
->base_type
!= vtn_base_type_void
) {
202 nir_variable
*ret_tmp
=
203 nir_local_variable_create(b
->nb
.impl
,
204 glsl_get_bare_type(ret_type
->type
),
206 ret_deref
= nir_build_deref_var(&b
->nb
, ret_tmp
);
207 call
->params
[param_idx
++] = nir_src_for_ssa(&ret_deref
->dest
.ssa
);
210 for (unsigned i
= 0; i
< vtn_callee
->type
->length
; i
++) {
211 struct vtn_type
*arg_type
= vtn_callee
->type
->params
[i
];
212 unsigned arg_id
= w
[4 + i
];
214 if (arg_type
->base_type
== vtn_base_type_sampled_image
) {
215 struct vtn_sampled_image
*sampled_image
=
216 vtn_value(b
, arg_id
, vtn_value_type_sampled_image
)->sampled_image
;
218 call
->params
[param_idx
++] =
219 nir_src_for_ssa(vtn_pointer_to_ssa(b
, sampled_image
->image
));
220 call
->params
[param_idx
++] =
221 nir_src_for_ssa(vtn_pointer_to_ssa(b
, sampled_image
->sampler
));
222 } else if (arg_type
->base_type
== vtn_base_type_pointer
||
223 arg_type
->base_type
== vtn_base_type_image
||
224 arg_type
->base_type
== vtn_base_type_sampler
) {
225 struct vtn_pointer
*pointer
=
226 vtn_value(b
, arg_id
, vtn_value_type_pointer
)->pointer
;
227 call
->params
[param_idx
++] =
228 nir_src_for_ssa(vtn_pointer_to_ssa(b
, pointer
));
230 vtn_ssa_value_add_to_call_params(b
, vtn_ssa_value(b
, arg_id
),
231 arg_type
, call
, ¶m_idx
);
234 assert(param_idx
== call
->num_params
);
236 nir_builder_instr_insert(&b
->nb
, &call
->instr
);
238 if (ret_type
->base_type
== vtn_base_type_void
) {
239 vtn_push_value(b
, w
[2], vtn_value_type_undef
);
241 vtn_push_ssa(b
, w
[2], res_type
, vtn_local_load(b
, ret_deref
, 0));
246 vtn_cfg_handle_prepass_instruction(struct vtn_builder
*b
, SpvOp opcode
,
247 const uint32_t *w
, unsigned count
)
250 case SpvOpFunction
: {
251 vtn_assert(b
->func
== NULL
);
252 b
->func
= rzalloc(b
, struct vtn_function
);
254 b
->func
->node
.type
= vtn_cf_node_type_function
;
255 b
->func
->node
.parent
= NULL
;
256 list_inithead(&b
->func
->body
);
257 b
->func
->control
= w
[3];
259 UNUSED
const struct glsl_type
*result_type
= vtn_get_type(b
, w
[1])->type
;
260 struct vtn_value
*val
= vtn_push_value(b
, w
[2], vtn_value_type_function
);
263 b
->func
->type
= vtn_get_type(b
, w
[4]);
264 const struct vtn_type
*func_type
= b
->func
->type
;
266 vtn_assert(func_type
->return_type
->type
== result_type
);
269 nir_function_create(b
->shader
, ralloc_strdup(b
->shader
, val
->name
));
271 unsigned num_params
= 0;
272 for (unsigned i
= 0; i
< func_type
->length
; i
++)
273 num_params
+= vtn_type_count_function_params(func_type
->params
[i
]);
275 /* Add one parameter for the function return value */
276 if (func_type
->return_type
->base_type
!= vtn_base_type_void
)
279 func
->num_params
= num_params
;
280 func
->params
= ralloc_array(b
->shader
, nir_parameter
, num_params
);
283 if (func_type
->return_type
->base_type
!= vtn_base_type_void
) {
284 nir_address_format addr_format
=
285 vtn_mode_to_address_format(b
, vtn_variable_mode_function
);
286 /* The return value is a regular pointer */
287 func
->params
[idx
++] = (nir_parameter
) {
288 .num_components
= nir_address_format_num_components(addr_format
),
289 .bit_size
= nir_address_format_bit_size(addr_format
),
293 for (unsigned i
= 0; i
< func_type
->length
; i
++)
294 vtn_type_add_to_function_params(func_type
->params
[i
], func
, &idx
);
295 assert(idx
== num_params
);
297 b
->func
->impl
= nir_function_impl_create(func
);
298 nir_builder_init(&b
->nb
, func
->impl
);
299 b
->nb
.cursor
= nir_before_cf_list(&b
->func
->impl
->body
);
300 b
->nb
.exact
= b
->exact
;
302 b
->func_param_idx
= 0;
304 /* The return value is the first parameter */
305 if (func_type
->return_type
->base_type
!= vtn_base_type_void
)
310 case SpvOpFunctionEnd
:
315 case SpvOpFunctionParameter
: {
316 struct vtn_type
*type
= vtn_get_type(b
, w
[1]);
318 vtn_assert(b
->func_param_idx
< b
->func
->impl
->function
->num_params
);
320 if (type
->base_type
== vtn_base_type_sampled_image
) {
321 /* Sampled images are actually two parameters. The first is the
322 * image and the second is the sampler.
324 struct vtn_value
*val
=
325 vtn_push_value(b
, w
[2], vtn_value_type_sampled_image
);
327 val
->sampled_image
= ralloc(b
, struct vtn_sampled_image
);
329 struct vtn_type
*image_type
= rzalloc(b
, struct vtn_type
);
330 image_type
->base_type
= vtn_base_type_image
;
331 image_type
->type
= type
->type
;
333 struct vtn_type
*sampler_type
= rzalloc(b
, struct vtn_type
);
334 sampler_type
->base_type
= vtn_base_type_sampler
;
335 sampler_type
->type
= glsl_bare_sampler_type();
337 val
->sampled_image
->image
=
338 vtn_load_param_pointer(b
, image_type
, b
->func_param_idx
++);
339 val
->sampled_image
->sampler
=
340 vtn_load_param_pointer(b
, sampler_type
, b
->func_param_idx
++);
341 } else if (type
->base_type
== vtn_base_type_pointer
&&
342 type
->type
!= NULL
) {
343 /* This is a pointer with an actual storage type */
344 nir_ssa_def
*ssa_ptr
= nir_load_param(&b
->nb
, b
->func_param_idx
++);
345 vtn_push_pointer(b
, w
[2], vtn_pointer_from_ssa(b
, ssa_ptr
, type
));
346 } else if (type
->base_type
== vtn_base_type_pointer
||
347 type
->base_type
== vtn_base_type_image
||
348 type
->base_type
== vtn_base_type_sampler
) {
349 vtn_push_pointer(b
, w
[2], vtn_load_param_pointer(b
, type
, b
->func_param_idx
++));
351 /* We're a regular SSA value. */
352 struct vtn_ssa_value
*value
= vtn_create_ssa_value(b
, type
->type
);
353 vtn_ssa_value_load_function_param(b
, value
, type
, &b
->func_param_idx
);
354 vtn_push_ssa(b
, w
[2], type
, value
);
360 vtn_assert(b
->block
== NULL
);
361 b
->block
= rzalloc(b
, struct vtn_block
);
362 b
->block
->node
.type
= vtn_cf_node_type_block
;
364 vtn_push_value(b
, w
[1], vtn_value_type_block
)->block
= b
->block
;
366 if (b
->func
->start_block
== NULL
) {
367 /* This is the first block encountered for this function. In this
368 * case, we set the start block and add it to the list of
369 * implemented functions that we'll walk later.
371 b
->func
->start_block
= b
->block
;
372 list_addtail(&b
->func
->node
.link
, &b
->functions
);
377 case SpvOpSelectionMerge
:
379 vtn_assert(b
->block
&& b
->block
->merge
== NULL
);
384 case SpvOpBranchConditional
:
388 case SpvOpReturnValue
:
389 case SpvOpUnreachable
:
390 vtn_assert(b
->block
&& b
->block
->branch
== NULL
);
391 b
->block
->branch
= w
;
396 /* Continue on as per normal */
403 /* This function performs a depth-first search of the cases and puts them
404 * in fall-through order.
407 vtn_order_case(struct vtn_switch
*swtch
, struct vtn_case
*cse
)
414 list_del(&cse
->node
.link
);
416 if (cse
->fallthrough
) {
417 vtn_order_case(swtch
, cse
->fallthrough
);
419 /* If we have a fall-through, place this case right before the case it
420 * falls through to. This ensures that fallthroughs come one after
421 * the other. These two can never get separated because that would
422 * imply something else falling through to the same case. Also, this
423 * can't break ordering because the DFS ensures that this case is
424 * visited before anything that falls through to it.
426 list_addtail(&cse
->node
.link
, &cse
->fallthrough
->node
.link
);
428 list_add(&cse
->node
.link
, &swtch
->cases
);
433 vtn_switch_order_cases(struct vtn_switch
*swtch
)
435 struct list_head cases
;
436 list_replace(&swtch
->cases
, &cases
);
437 list_inithead(&swtch
->cases
);
438 while (!list_is_empty(&cases
)) {
439 struct vtn_case
*cse
=
440 list_first_entry(&cases
, struct vtn_case
, node
.link
);
441 vtn_order_case(swtch
, cse
);
446 vtn_block_set_merge_cf_node(struct vtn_builder
*b
, struct vtn_block
*block
,
447 struct vtn_cf_node
*cf_node
)
449 vtn_fail_if(block
->merge_cf_node
!= NULL
,
450 "The merge block declared by a header block cannot be a "
451 "merge block declared by any other header block.");
453 block
->merge_cf_node
= cf_node
;
456 #define VTN_DECL_CF_NODE_FIND(_type) \
457 static inline struct vtn_##_type * \
458 vtn_cf_node_find_##_type(struct vtn_cf_node *node) \
460 while (node && node->type != vtn_cf_node_type_##_type) \
461 node = node->parent; \
462 return (struct vtn_##_type *)node; \
465 VTN_DECL_CF_NODE_FIND(if)
466 VTN_DECL_CF_NODE_FIND(loop
)
467 VTN_DECL_CF_NODE_FIND(case)
468 VTN_DECL_CF_NODE_FIND(switch)
469 VTN_DECL_CF_NODE_FIND(function
)
471 static enum vtn_branch_type
472 vtn_handle_branch(struct vtn_builder
*b
,
473 struct vtn_cf_node
*cf_parent
,
474 struct vtn_block
*target_block
)
476 struct vtn_loop
*loop
= vtn_cf_node_find_loop(cf_parent
);
478 /* Detect a loop back-edge first. That way none of the code below
479 * accidentally operates on a loop back-edge.
481 if (loop
&& target_block
== loop
->header_block
)
482 return vtn_branch_type_loop_back_edge
;
484 /* Try to detect fall-through */
485 if (target_block
->switch_case
) {
486 /* When it comes to handling switch cases, we can break calls to
487 * vtn_handle_branch into two cases: calls from within a case construct
488 * and calls for the jump to each case construct. In the second case,
489 * cf_parent is the vtn_switch itself and vtn_cf_node_find_case() will
490 * return the outer switch case in which this switch is contained. It's
491 * fine if the target block is a switch case from an outer switch as
492 * long as it is also the switch break for this switch.
494 struct vtn_case
*switch_case
= vtn_cf_node_find_case(cf_parent
);
496 /* This doesn't get called for the OpSwitch */
497 vtn_fail_if(switch_case
== NULL
,
498 "A switch case can only be entered through an OpSwitch or "
499 "falling through from another switch case.");
501 /* Because block->switch_case is only set on the entry block for a given
502 * switch case, we only ever get here if we're jumping to the start of a
503 * switch case. It's possible, however, that a switch case could jump
504 * to itself via a back-edge. That *should* get caught by the loop
505 * handling case above but if we have a back edge without a loop merge,
506 * we could en up here.
508 vtn_fail_if(target_block
->switch_case
== switch_case
,
509 "A switch cannot fall-through to itself. Likely, there is "
510 "a back-edge which is not to a loop header.");
512 vtn_fail_if(target_block
->switch_case
->node
.parent
!=
513 switch_case
->node
.parent
,
514 "A switch case fall-through must come from the same "
515 "OpSwitch construct");
517 vtn_fail_if(switch_case
->fallthrough
!= NULL
&&
518 switch_case
->fallthrough
!= target_block
->switch_case
,
519 "Each case construct can have at most one branch to "
520 "another case construct");
522 switch_case
->fallthrough
= target_block
->switch_case
;
524 /* We don't immediately return vtn_branch_type_switch_fallthrough
525 * because it may also be a loop or switch break for an inner loop or
526 * switch and that takes precedence.
530 if (loop
&& target_block
== loop
->cont_block
)
531 return vtn_branch_type_loop_continue
;
533 /* We walk blocks as a breadth-first search on the control-flow construct
534 * tree where, when we find a construct, we add the vtn_cf_node for that
535 * construct and continue iterating at the merge target block (if any).
536 * Therefore, we want merges whose with parent == cf_parent to be treated
537 * as regular branches. We only want to consider merges if they break out
538 * of the current CF construct.
540 if (target_block
->merge_cf_node
!= NULL
&&
541 target_block
->merge_cf_node
->parent
!= cf_parent
) {
542 switch (target_block
->merge_cf_node
->type
) {
543 case vtn_cf_node_type_if
:
544 for (struct vtn_cf_node
*node
= cf_parent
;
545 node
!= target_block
->merge_cf_node
; node
= node
->parent
) {
546 vtn_fail_if(node
== NULL
|| node
->type
!= vtn_cf_node_type_if
,
547 "Branching to the merge block of a selection "
548 "construct can only be used to break out of a "
549 "selection construct");
551 struct vtn_if
*if_stmt
= vtn_cf_node_as_if(node
);
553 /* This should be guaranteed by our iteration */
554 assert(if_stmt
->merge_block
!= target_block
);
556 vtn_fail_if(if_stmt
->merge_block
!= NULL
,
557 "Branching to the merge block of a selection "
558 "construct can only be used to break out of the "
559 "inner most nested selection level");
561 return vtn_branch_type_if_merge
;
563 case vtn_cf_node_type_loop
:
564 vtn_fail_if(target_block
->merge_cf_node
!= &loop
->node
,
565 "Loop breaks can only break out of the inner most "
566 "nested loop level");
567 return vtn_branch_type_loop_break
;
569 case vtn_cf_node_type_switch
: {
570 struct vtn_switch
*swtch
= vtn_cf_node_find_switch(cf_parent
);
571 vtn_fail_if(target_block
->merge_cf_node
!= &swtch
->node
,
572 "Switch breaks can only break out of the inner most "
573 "nested switch level");
574 return vtn_branch_type_switch_break
;
578 unreachable("Invalid CF node type for a merge");
582 if (target_block
->switch_case
)
583 return vtn_branch_type_switch_fallthrough
;
585 return vtn_branch_type_none
;
588 struct vtn_cfg_work_item
{
589 struct list_head link
;
591 struct vtn_cf_node
*cf_parent
;
592 struct list_head
*cf_list
;
593 struct vtn_block
*start_block
;
597 vtn_add_cfg_work_item(struct vtn_builder
*b
,
598 struct list_head
*work_list
,
599 struct vtn_cf_node
*cf_parent
,
600 struct list_head
*cf_list
,
601 struct vtn_block
*start_block
)
603 struct vtn_cfg_work_item
*work
= ralloc(b
, struct vtn_cfg_work_item
);
604 work
->cf_parent
= cf_parent
;
605 work
->cf_list
= cf_list
;
606 work
->start_block
= start_block
;
607 list_addtail(&work
->link
, work_list
);
610 /* Processes a block and returns the next block to process or NULL if we've
611 * reached the end of the construct.
613 static struct vtn_block
*
614 vtn_process_block(struct vtn_builder
*b
,
615 struct list_head
*work_list
,
616 struct vtn_cf_node
*cf_parent
,
617 struct list_head
*cf_list
,
618 struct vtn_block
*block
)
620 if (!list_is_empty(cf_list
)) {
621 /* vtn_process_block() acts like an iterator: it processes the given
622 * block and then returns the next block to process. For a given
623 * control-flow construct, vtn_build_cfg() calls vtn_process_block()
624 * repeatedly until it finally returns NULL. Therefore, we know that
625 * the only blocks on which vtn_process_block() can be called are either
626 * the first block in a construct or a block that vtn_process_block()
627 * returned for the current construct. If cf_list is empty then we know
628 * that we're processing the first block in the construct and we have to
629 * add it to the list.
631 * If cf_list is not empty, then it must be the block returned by the
632 * previous call to vtn_process_block(). We know a priori that
633 * vtn_process_block only returns either normal branches
634 * (vtn_branch_type_none) or merge target blocks.
636 switch (vtn_handle_branch(b
, cf_parent
, block
)) {
637 case vtn_branch_type_none
:
638 /* For normal branches, we want to process them and add them to the
639 * current construct. Merge target blocks also look like normal
640 * branches from the perspective of this construct. See also
641 * vtn_handle_branch().
645 case vtn_branch_type_loop_continue
:
646 case vtn_branch_type_switch_fallthrough
:
647 /* The two cases where we can get early exits from a construct that
648 * are not to that construct's merge target are loop continues and
649 * switch fall-throughs. In these cases, we need to break out of the
650 * current construct by returning NULL.
655 /* The only way we can get here is if something was used as two kinds
656 * of merges at the same time and that's illegal.
658 vtn_fail("A block was used as a merge target from two or more "
659 "structured control-flow constructs");
663 /* Once a block has been processed, it is placed into and the list link
664 * will point to something non-null. If we see a node we've already
665 * processed here, it either exists in multiple functions or it's an
668 if (block
->node
.parent
!= NULL
) {
669 vtn_fail_if(vtn_cf_node_find_function(&block
->node
) !=
670 vtn_cf_node_find_function(cf_parent
),
671 "A block cannot exist in two functions at the "
674 vtn_fail("Invalid back or cross-edge in the CFG");
677 if (block
->merge
&& (*block
->merge
& SpvOpCodeMask
) == SpvOpLoopMerge
&&
678 block
->loop
== NULL
) {
679 vtn_fail_if((*block
->branch
& SpvOpCodeMask
) != SpvOpBranch
&&
680 (*block
->branch
& SpvOpCodeMask
) != SpvOpBranchConditional
,
681 "An OpLoopMerge instruction must immediately precede "
682 "either an OpBranch or OpBranchConditional instruction.");
684 struct vtn_loop
*loop
= rzalloc(b
, struct vtn_loop
);
686 loop
->node
.type
= vtn_cf_node_type_loop
;
687 loop
->node
.parent
= cf_parent
;
688 list_inithead(&loop
->body
);
689 list_inithead(&loop
->cont_body
);
690 loop
->header_block
= block
;
691 loop
->break_block
= vtn_block(b
, block
->merge
[1]);
692 loop
->cont_block
= vtn_block(b
, block
->merge
[2]);
693 loop
->control
= block
->merge
[3];
695 list_addtail(&loop
->node
.link
, cf_list
);
698 /* Note: The work item for the main loop body will start with the
699 * current block as its start block. If we weren't careful, we would
700 * get here again and end up in an infinite loop. This is why we set
701 * block->loop above and check for it before creating one. This way,
702 * we only create the loop once and the second iteration that tries to
703 * handle this loop goes to the cases below and gets handled as a
706 vtn_add_cfg_work_item(b
, work_list
, &loop
->node
,
707 &loop
->body
, loop
->header_block
);
709 /* For continue targets, SPIR-V guarantees the following:
711 * - the Continue Target must dominate the back-edge block
712 * - the back-edge block must post dominate the Continue Target
714 * If the header block is the same as the continue target, this
715 * condition is trivially satisfied and there is no real continue
718 if (loop
->cont_block
!= loop
->header_block
) {
719 vtn_add_cfg_work_item(b
, work_list
, &loop
->node
,
720 &loop
->cont_body
, loop
->cont_block
);
723 vtn_block_set_merge_cf_node(b
, loop
->break_block
, &loop
->node
);
725 return loop
->break_block
;
728 /* Add the block to the CF list */
729 block
->node
.parent
= cf_parent
;
730 list_addtail(&block
->node
.link
, cf_list
);
732 switch (*block
->branch
& SpvOpCodeMask
) {
734 struct vtn_block
*branch_block
= vtn_block(b
, block
->branch
[1]);
736 block
->branch_type
= vtn_handle_branch(b
, cf_parent
, branch_block
);
738 if (block
->branch_type
== vtn_branch_type_none
)
745 case SpvOpReturnValue
:
746 block
->branch_type
= vtn_branch_type_return
;
750 block
->branch_type
= vtn_branch_type_discard
;
753 case SpvOpBranchConditional
: {
754 struct vtn_value
*cond_val
= vtn_untyped_value(b
, block
->branch
[1]);
755 vtn_fail_if(!cond_val
->type
||
756 cond_val
->type
->base_type
!= vtn_base_type_scalar
||
757 cond_val
->type
->type
!= glsl_bool_type(),
758 "Condition must be a Boolean type scalar");
760 struct vtn_block
*then_block
= vtn_block(b
, block
->branch
[2]);
761 struct vtn_block
*else_block
= vtn_block(b
, block
->branch
[3]);
763 if (then_block
== else_block
) {
764 /* This is uncommon but it can happen. We treat this the same way as
765 * an unconditional branch.
767 block
->branch_type
= vtn_handle_branch(b
, cf_parent
, then_block
);
769 if (block
->branch_type
== vtn_branch_type_none
)
775 struct vtn_if
*if_stmt
= rzalloc(b
, struct vtn_if
);
777 if_stmt
->node
.type
= vtn_cf_node_type_if
;
778 if_stmt
->node
.parent
= cf_parent
;
779 if_stmt
->condition
= block
->branch
[1];
780 list_inithead(&if_stmt
->then_body
);
781 list_inithead(&if_stmt
->else_body
);
783 list_addtail(&if_stmt
->node
.link
, cf_list
);
786 (*block
->merge
& SpvOpCodeMask
) == SpvOpSelectionMerge
) {
787 /* We may not always have a merge block and that merge doesn't
788 * technically have to be an OpSelectionMerge. We could have a block
789 * with an OpLoopMerge which ends in an OpBranchConditional.
791 if_stmt
->merge_block
= vtn_block(b
, block
->merge
[1]);
792 vtn_block_set_merge_cf_node(b
, if_stmt
->merge_block
, &if_stmt
->node
);
794 if_stmt
->control
= block
->merge
[2];
797 if_stmt
->then_type
= vtn_handle_branch(b
, &if_stmt
->node
, then_block
);
798 if (if_stmt
->then_type
== vtn_branch_type_none
) {
799 vtn_add_cfg_work_item(b
, work_list
, &if_stmt
->node
,
800 &if_stmt
->then_body
, then_block
);
803 if_stmt
->else_type
= vtn_handle_branch(b
, &if_stmt
->node
, else_block
);
804 if (if_stmt
->else_type
== vtn_branch_type_none
) {
805 vtn_add_cfg_work_item(b
, work_list
, &if_stmt
->node
,
806 &if_stmt
->else_body
, else_block
);
809 return if_stmt
->merge_block
;
813 struct vtn_value
*sel_val
= vtn_untyped_value(b
, block
->branch
[1]);
814 vtn_fail_if(!sel_val
->type
||
815 sel_val
->type
->base_type
!= vtn_base_type_scalar
,
816 "Selector of OpSwitch must have a type of OpTypeInt");
818 nir_alu_type sel_type
=
819 nir_get_nir_type_for_glsl_type(sel_val
->type
->type
);
820 vtn_fail_if(nir_alu_type_get_base_type(sel_type
) != nir_type_int
&&
821 nir_alu_type_get_base_type(sel_type
) != nir_type_uint
,
822 "Selector of OpSwitch must have a type of OpTypeInt");
824 struct vtn_switch
*swtch
= rzalloc(b
, struct vtn_switch
);
826 swtch
->node
.type
= vtn_cf_node_type_switch
;
827 swtch
->node
.parent
= cf_parent
;
828 swtch
->selector
= block
->branch
[1];
829 list_inithead(&swtch
->cases
);
831 list_addtail(&swtch
->node
.link
, cf_list
);
833 /* We may not always have a merge block */
835 vtn_fail_if((*block
->merge
& SpvOpCodeMask
) != SpvOpSelectionMerge
,
836 "An OpLoopMerge instruction must immediately precede "
837 "either an OpBranch or OpBranchConditional "
839 swtch
->break_block
= vtn_block(b
, block
->merge
[1]);
840 vtn_block_set_merge_cf_node(b
, swtch
->break_block
, &swtch
->node
);
843 /* First, we go through and record all of the cases. */
844 const uint32_t *branch_end
=
845 block
->branch
+ (block
->branch
[0] >> SpvWordCountShift
);
847 struct hash_table
*block_to_case
= _mesa_pointer_hash_table_create(b
);
849 bool is_default
= true;
850 const unsigned bitsize
= nir_alu_type_get_type_size(sel_type
);
851 for (const uint32_t *w
= block
->branch
+ 2; w
< branch_end
;) {
852 uint64_t literal
= 0;
857 assert(bitsize
== 64);
858 literal
= vtn_u64_literal(w
);
862 struct vtn_block
*case_block
= vtn_block(b
, *(w
++));
864 struct hash_entry
*case_entry
=
865 _mesa_hash_table_search(block_to_case
, case_block
);
867 struct vtn_case
*cse
;
869 cse
= case_entry
->data
;
871 cse
= rzalloc(b
, struct vtn_case
);
873 cse
->node
.type
= vtn_cf_node_type_case
;
874 cse
->node
.parent
= &swtch
->node
;
875 list_inithead(&cse
->body
);
876 util_dynarray_init(&cse
->values
, b
);
878 cse
->type
= vtn_handle_branch(b
, &swtch
->node
, case_block
);
880 case vtn_branch_type_none
:
881 /* This is a "real" cases which has stuff in it */
882 vtn_fail_if(case_block
->switch_case
!= NULL
,
883 "OpSwitch has a case which is also in another "
884 "OpSwitch construct");
885 case_block
->switch_case
= cse
;
886 vtn_add_cfg_work_item(b
, work_list
, &cse
->node
,
887 &cse
->body
, case_block
);
890 case vtn_branch_type_switch_break
:
891 case vtn_branch_type_loop_break
:
892 case vtn_branch_type_loop_continue
:
893 /* Switch breaks as well as loop breaks and continues can be
894 * used to break out of a switch construct or as direct targets
900 vtn_fail("Target of OpSwitch is not a valid structured exit "
901 "from the switch construct.");
904 list_addtail(&cse
->node
.link
, &swtch
->cases
);
906 _mesa_hash_table_insert(block_to_case
, case_block
, cse
);
910 cse
->is_default
= true;
912 util_dynarray_append(&cse
->values
, uint64_t, literal
);
918 _mesa_hash_table_destroy(block_to_case
, NULL
);
920 return swtch
->break_block
;
923 case SpvOpUnreachable
:
927 vtn_fail("Block did not end with a valid branch instruction");
932 vtn_build_cfg(struct vtn_builder
*b
, const uint32_t *words
, const uint32_t *end
)
934 vtn_foreach_instruction(b
, words
, end
,
935 vtn_cfg_handle_prepass_instruction
);
937 vtn_foreach_cf_node(func_node
, &b
->functions
) {
938 struct vtn_function
*func
= vtn_cf_node_as_function(func_node
);
940 /* We build the CFG for each function by doing a breadth-first search on
941 * the control-flow graph. We keep track of our state using a worklist.
942 * Doing a BFS ensures that we visit each structured control-flow
943 * construct and its merge node before we visit the stuff inside the
946 struct list_head work_list
;
947 list_inithead(&work_list
);
948 vtn_add_cfg_work_item(b
, &work_list
, &func
->node
, &func
->body
,
951 while (!list_is_empty(&work_list
)) {
952 struct vtn_cfg_work_item
*work
=
953 list_first_entry(&work_list
, struct vtn_cfg_work_item
, link
);
954 list_del(&work
->link
);
956 for (struct vtn_block
*block
= work
->start_block
; block
; ) {
957 block
= vtn_process_block(b
, &work_list
, work
->cf_parent
,
958 work
->cf_list
, block
);
965 vtn_handle_phis_first_pass(struct vtn_builder
*b
, SpvOp opcode
,
966 const uint32_t *w
, unsigned count
)
968 if (opcode
== SpvOpLabel
)
969 return true; /* Nothing to do */
971 /* If this isn't a phi node, stop. */
972 if (opcode
!= SpvOpPhi
)
975 /* For handling phi nodes, we do a poor-man's out-of-ssa on the spot.
976 * For each phi, we create a variable with the appropreate type and
977 * do a load from that variable. Then, in a second pass, we add
978 * stores to that variable to each of the predecessor blocks.
980 * We could do something more intelligent here. However, in order to
981 * handle loops and things properly, we really need dominance
982 * information. It would end up basically being the into-SSA
983 * algorithm all over again. It's easier if we just let
984 * lower_vars_to_ssa do that for us instead of repeating it here.
986 struct vtn_type
*type
= vtn_get_type(b
, w
[1]);
987 nir_variable
*phi_var
=
988 nir_local_variable_create(b
->nb
.impl
, type
->type
, "phi");
989 _mesa_hash_table_insert(b
->phi_table
, w
, phi_var
);
991 vtn_push_ssa(b
, w
[2], type
,
992 vtn_local_load(b
, nir_build_deref_var(&b
->nb
, phi_var
), 0));
998 vtn_handle_phi_second_pass(struct vtn_builder
*b
, SpvOp opcode
,
999 const uint32_t *w
, unsigned count
)
1001 if (opcode
!= SpvOpPhi
)
1004 struct hash_entry
*phi_entry
= _mesa_hash_table_search(b
->phi_table
, w
);
1006 /* It's possible that this phi is in an unreachable block in which case it
1007 * may never have been emitted and therefore may not be in the hash table.
1008 * In this case, there's no var for it and it's safe to just bail.
1010 if (phi_entry
== NULL
)
1013 nir_variable
*phi_var
= phi_entry
->data
;
1015 for (unsigned i
= 3; i
< count
; i
+= 2) {
1016 struct vtn_block
*pred
= vtn_block(b
, w
[i
+ 1]);
1018 /* If block does not have end_nop, that is because it is an unreacheable
1019 * block, and hence it is not worth to handle it */
1023 b
->nb
.cursor
= nir_after_instr(&pred
->end_nop
->instr
);
1025 struct vtn_ssa_value
*src
= vtn_ssa_value(b
, w
[i
]);
1027 vtn_local_store(b
, src
, nir_build_deref_var(&b
->nb
, phi_var
), 0);
1034 vtn_emit_branch(struct vtn_builder
*b
, enum vtn_branch_type branch_type
,
1035 nir_variable
*switch_fall_var
, bool *has_switch_break
)
1037 switch (branch_type
) {
1038 case vtn_branch_type_if_merge
:
1039 break; /* Nothing to do */
1040 case vtn_branch_type_switch_break
:
1041 nir_store_var(&b
->nb
, switch_fall_var
, nir_imm_false(&b
->nb
), 1);
1042 *has_switch_break
= true;
1044 case vtn_branch_type_switch_fallthrough
:
1045 break; /* Nothing to do */
1046 case vtn_branch_type_loop_break
:
1047 nir_jump(&b
->nb
, nir_jump_break
);
1049 case vtn_branch_type_loop_continue
:
1050 nir_jump(&b
->nb
, nir_jump_continue
);
1052 case vtn_branch_type_loop_back_edge
:
1054 case vtn_branch_type_return
:
1055 nir_jump(&b
->nb
, nir_jump_return
);
1057 case vtn_branch_type_discard
: {
1058 nir_intrinsic_instr
*discard
=
1059 nir_intrinsic_instr_create(b
->nb
.shader
, nir_intrinsic_discard
);
1060 nir_builder_instr_insert(&b
->nb
, &discard
->instr
);
1064 vtn_fail("Invalid branch type");
1068 static nir_ssa_def
*
1069 vtn_switch_case_condition(struct vtn_builder
*b
, struct vtn_switch
*swtch
,
1070 nir_ssa_def
*sel
, struct vtn_case
*cse
)
1072 if (cse
->is_default
) {
1073 nir_ssa_def
*any
= nir_imm_false(&b
->nb
);
1074 vtn_foreach_cf_node(other_node
, &swtch
->cases
) {
1075 struct vtn_case
*other
= vtn_cf_node_as_case(other_node
);
1076 if (other
->is_default
)
1079 any
= nir_ior(&b
->nb
, any
,
1080 vtn_switch_case_condition(b
, swtch
, sel
, other
));
1082 return nir_inot(&b
->nb
, any
);
1084 nir_ssa_def
*cond
= nir_imm_false(&b
->nb
);
1085 util_dynarray_foreach(&cse
->values
, uint64_t, val
) {
1086 nir_ssa_def
*imm
= nir_imm_intN_t(&b
->nb
, *val
, sel
->bit_size
);
1087 cond
= nir_ior(&b
->nb
, cond
, nir_ieq(&b
->nb
, sel
, imm
));
1093 static nir_loop_control
1094 vtn_loop_control(struct vtn_builder
*b
, struct vtn_loop
*vtn_loop
)
1096 if (vtn_loop
->control
== SpvLoopControlMaskNone
)
1097 return nir_loop_control_none
;
1098 else if (vtn_loop
->control
& SpvLoopControlDontUnrollMask
)
1099 return nir_loop_control_dont_unroll
;
1100 else if (vtn_loop
->control
& SpvLoopControlUnrollMask
)
1101 return nir_loop_control_unroll
;
1102 else if (vtn_loop
->control
& SpvLoopControlDependencyInfiniteMask
||
1103 vtn_loop
->control
& SpvLoopControlDependencyLengthMask
||
1104 vtn_loop
->control
& SpvLoopControlMinIterationsMask
||
1105 vtn_loop
->control
& SpvLoopControlMaxIterationsMask
||
1106 vtn_loop
->control
& SpvLoopControlIterationMultipleMask
||
1107 vtn_loop
->control
& SpvLoopControlPeelCountMask
||
1108 vtn_loop
->control
& SpvLoopControlPartialCountMask
) {
1109 /* We do not do anything special with these yet. */
1110 return nir_loop_control_none
;
1112 vtn_fail("Invalid loop control");
1116 static nir_selection_control
1117 vtn_selection_control(struct vtn_builder
*b
, struct vtn_if
*vtn_if
)
1119 if (vtn_if
->control
== SpvSelectionControlMaskNone
)
1120 return nir_selection_control_none
;
1121 else if (vtn_if
->control
& SpvSelectionControlDontFlattenMask
)
1122 return nir_selection_control_dont_flatten
;
1123 else if (vtn_if
->control
& SpvSelectionControlFlattenMask
)
1124 return nir_selection_control_flatten
;
1126 vtn_fail("Invalid selection control");
1130 vtn_emit_cf_list(struct vtn_builder
*b
, struct list_head
*cf_list
,
1131 nir_variable
*switch_fall_var
, bool *has_switch_break
,
1132 vtn_instruction_handler handler
)
1134 vtn_foreach_cf_node(node
, cf_list
) {
1135 switch (node
->type
) {
1136 case vtn_cf_node_type_block
: {
1137 struct vtn_block
*block
= vtn_cf_node_as_block(node
);
1139 const uint32_t *block_start
= block
->label
;
1140 const uint32_t *block_end
= block
->merge
? block
->merge
:
1143 block_start
= vtn_foreach_instruction(b
, block_start
, block_end
,
1144 vtn_handle_phis_first_pass
);
1146 vtn_foreach_instruction(b
, block_start
, block_end
, handler
);
1148 block
->end_nop
= nir_intrinsic_instr_create(b
->nb
.shader
,
1150 nir_builder_instr_insert(&b
->nb
, &block
->end_nop
->instr
);
1152 if ((*block
->branch
& SpvOpCodeMask
) == SpvOpReturnValue
) {
1153 vtn_fail_if(b
->func
->type
->return_type
->base_type
==
1155 "Return with a value from a function returning void");
1156 struct vtn_ssa_value
*src
= vtn_ssa_value(b
, block
->branch
[1]);
1157 const struct glsl_type
*ret_type
=
1158 glsl_get_bare_type(b
->func
->type
->return_type
->type
);
1159 nir_deref_instr
*ret_deref
=
1160 nir_build_deref_cast(&b
->nb
, nir_load_param(&b
->nb
, 0),
1161 nir_var_function_temp
, ret_type
, 0);
1162 vtn_local_store(b
, src
, ret_deref
, 0);
1165 if (block
->branch_type
!= vtn_branch_type_none
) {
1166 vtn_emit_branch(b
, block
->branch_type
,
1167 switch_fall_var
, has_switch_break
);
1174 case vtn_cf_node_type_if
: {
1175 struct vtn_if
*vtn_if
= vtn_cf_node_as_if(node
);
1176 bool sw_break
= false;
1179 nir_push_if(&b
->nb
, vtn_get_nir_ssa(b
, vtn_if
->condition
));
1181 nif
->control
= vtn_selection_control(b
, vtn_if
);
1183 if (vtn_if
->then_type
== vtn_branch_type_none
) {
1184 vtn_emit_cf_list(b
, &vtn_if
->then_body
,
1185 switch_fall_var
, &sw_break
, handler
);
1187 vtn_emit_branch(b
, vtn_if
->then_type
, switch_fall_var
, &sw_break
);
1190 nir_push_else(&b
->nb
, nif
);
1191 if (vtn_if
->else_type
== vtn_branch_type_none
) {
1192 vtn_emit_cf_list(b
, &vtn_if
->else_body
,
1193 switch_fall_var
, &sw_break
, handler
);
1195 vtn_emit_branch(b
, vtn_if
->else_type
, switch_fall_var
, &sw_break
);
1198 nir_pop_if(&b
->nb
, nif
);
1200 /* If we encountered a switch break somewhere inside of the if,
1201 * then it would have been handled correctly by calling
1202 * emit_cf_list or emit_branch for the interrior. However, we
1203 * need to predicate everything following on wether or not we're
1207 *has_switch_break
= true;
1208 nir_push_if(&b
->nb
, nir_load_var(&b
->nb
, switch_fall_var
));
1213 case vtn_cf_node_type_loop
: {
1214 struct vtn_loop
*vtn_loop
= vtn_cf_node_as_loop(node
);
1216 nir_loop
*loop
= nir_push_loop(&b
->nb
);
1217 loop
->control
= vtn_loop_control(b
, vtn_loop
);
1219 vtn_emit_cf_list(b
, &vtn_loop
->body
, NULL
, NULL
, handler
);
1221 if (!list_is_empty(&vtn_loop
->cont_body
)) {
1222 /* If we have a non-trivial continue body then we need to put
1223 * it at the beginning of the loop with a flag to ensure that
1224 * it doesn't get executed in the first iteration.
1226 nir_variable
*do_cont
=
1227 nir_local_variable_create(b
->nb
.impl
, glsl_bool_type(), "cont");
1229 b
->nb
.cursor
= nir_before_cf_node(&loop
->cf_node
);
1230 nir_store_var(&b
->nb
, do_cont
, nir_imm_false(&b
->nb
), 1);
1232 b
->nb
.cursor
= nir_before_cf_list(&loop
->body
);
1235 nir_push_if(&b
->nb
, nir_load_var(&b
->nb
, do_cont
));
1237 vtn_emit_cf_list(b
, &vtn_loop
->cont_body
, NULL
, NULL
, handler
);
1239 nir_pop_if(&b
->nb
, cont_if
);
1241 nir_store_var(&b
->nb
, do_cont
, nir_imm_true(&b
->nb
), 1);
1243 b
->has_loop_continue
= true;
1246 nir_pop_loop(&b
->nb
, loop
);
1250 case vtn_cf_node_type_switch
: {
1251 struct vtn_switch
*vtn_switch
= vtn_cf_node_as_switch(node
);
1253 /* Before we can emit anything, we need to sort the list of cases in
1254 * fall-through order.
1256 vtn_switch_order_cases(vtn_switch
);
1258 /* First, we create a variable to keep track of whether or not the
1259 * switch is still going at any given point. Any switch breaks
1260 * will set this variable to false.
1262 nir_variable
*fall_var
=
1263 nir_local_variable_create(b
->nb
.impl
, glsl_bool_type(), "fall");
1264 nir_store_var(&b
->nb
, fall_var
, nir_imm_false(&b
->nb
), 1);
1266 nir_ssa_def
*sel
= vtn_get_nir_ssa(b
, vtn_switch
->selector
);
1268 /* Now we can walk the list of cases and actually emit code */
1269 vtn_foreach_cf_node(case_node
, &vtn_switch
->cases
) {
1270 struct vtn_case
*cse
= vtn_cf_node_as_case(case_node
);
1272 /* Figure out the condition */
1274 vtn_switch_case_condition(b
, vtn_switch
, sel
, cse
);
1275 /* Take fallthrough into account */
1276 cond
= nir_ior(&b
->nb
, cond
, nir_load_var(&b
->nb
, fall_var
));
1278 nir_if
*case_if
= nir_push_if(&b
->nb
, cond
);
1280 bool has_break
= false;
1281 nir_store_var(&b
->nb
, fall_var
, nir_imm_true(&b
->nb
), 1);
1282 vtn_emit_cf_list(b
, &cse
->body
, fall_var
, &has_break
, handler
);
1283 (void)has_break
; /* We don't care */
1285 nir_pop_if(&b
->nb
, case_if
);
1292 vtn_fail("Invalid CF node type");
1298 vtn_function_emit(struct vtn_builder
*b
, struct vtn_function
*func
,
1299 vtn_instruction_handler instruction_handler
)
1301 nir_builder_init(&b
->nb
, func
->impl
);
1303 b
->nb
.cursor
= nir_after_cf_list(&func
->impl
->body
);
1304 b
->nb
.exact
= b
->exact
;
1305 b
->has_loop_continue
= false;
1306 b
->phi_table
= _mesa_pointer_hash_table_create(b
);
1308 vtn_emit_cf_list(b
, &func
->body
, NULL
, NULL
, instruction_handler
);
1310 vtn_foreach_instruction(b
, func
->start_block
->label
, func
->end
,
1311 vtn_handle_phi_second_pass
);
1313 nir_rematerialize_derefs_in_use_blocks_impl(func
->impl
);
1315 /* Continue blocks for loops get inserted before the body of the loop
1316 * but instructions in the continue may use SSA defs in the loop body.
1317 * Therefore, we need to repair SSA to insert the needed phi nodes.
1319 if (b
->has_loop_continue
)
1320 nir_repair_ssa_impl(func
->impl
);
1322 func
->emitted
= true;