Debian Codegraph @

src/imagination/pco/pco_cf.c

raw
1 /*
2 * Copyright © 2025 Imagination Technologies Ltd.
3 *
4 * SPDX-License-Identifier: MIT
5 */
6
7 /**
8 * \file pco_cf.c
9 *
10 * \brief PCO control-flow passes.
11 */
12
13 #include "pco.h"
14 #include "pco_builder.h"
15 #include "util/bitscan.h"
16 #include "util/bitset.h"
17 #include "util/list.h"
18 #include "util/macros.h"
19 #include "util/ralloc.h"
20 #include "util/u_dynarray.h"
21
22 #include <assert.h>
23 #include <stdbool.h>
24
25 static pco_ref emc_ref(pco_func *func, pco_builder *b)
26 {
27 if (pco_ref_is_null(func->emc)) {
28 /* Allocate and initialize the emc. */
29 func->emc = pco_ref_new_vreg(func);
30
31 pco_cndst(b,
32 pco_ref_pred(PCO_PRED_PE),
33 func->emc,
34 pco_zero,
35 pco_ref_imm8(1),
36 .exec_cnd = PCO_EXEC_CND_EX_ZX,
37 .cnd = PCO_CND_ALWAYS);
38 }
39
40 return func->emc;
41 }
42
43 static inline pco_block *cf_section_create(pco_func *func,
44 pco_cf_node *parent_cf_node,
45 struct list_head *cf_node_list,
46 enum pco_cf_node_flag flag)
47 {
48 assert(flag == PCO_CF_NODE_FLAG_PROLOGUE ||
49 flag == PCO_CF_NODE_FLAG_INTERLOGUE ||
50 flag == PCO_CF_NODE_FLAG_EPILOGUE);
51
52 pco_block *block = pco_block_create(func);
53 block->cf_node.parent = parent_cf_node;
54 block->cf_node.flag = flag;
55 list_addtail(&block->cf_node.link, cf_node_list);
56
57 return block;
58 }
59
60 static inline bool body_has_non_preds(struct list_head *body)
61 {
62 if (list_is_empty(body))
63 return false;
64
65 pco_block *block = pco_cf_node_as_block(pco_cf_node_head(body));
66 pco_instr *last_instr = NULL;
67 pco_foreach_instr_in_block (instr, block) {
68 /* Make sure there are no instructions that read/write predicates. */
69 pco_foreach_instr_src (psrc, instr) {
70 if (pco_ref_is_pred(*psrc))
71 return true;
72 }
73
74 pco_foreach_instr_dest (pdest, instr) {
75 if (pco_ref_is_pred(*pdest))
76 return true;
77 }
78
79 if (!pco_instr_has_exec_cnd(instr))
80 return true;
81
82 if (!pco_instr_has_default_exec(instr))
83 return true;
84
85 last_instr = instr;
86 }
87
88 assert(last_instr);
89 return last_instr->op == PCO_OP_BR;
90 }
91
92 static inline bool can_pred_exec(pco_if *pif)
93 {
94 if (PCO_DEBUG(NO_PRED_CF))
95 return false;
96
97 /* Skip if there is any nesting. */
98 if (list_length(&pif->then_body) > 1 || list_length(&pif->else_body) > 1)
99 return false;
100
101 /* Skip if then/else blocks end with a branch, or contain non-predicatable
102 * instructions.
103 * Note: WDFs can't be predicated and won't be inserted until the scheduling
104 * pass which comes after this one, but we don't have to worry about it as if
105 * there are no outstanding data fences it'll simply NOP.
106 */
107 if (body_has_non_preds(&pif->then_body) ||
108 body_has_non_preds(&pif->else_body))
109 return false;
110
111 return true;
112 }
113
114 static inline void set_body_exec_cnd(struct list_head *body,
115 enum pco_exec_cnd exec_cnd)
116 {
117 assert(!list_is_empty(body));
118
119 pco_block *block = pco_cf_node_as_block(pco_cf_node_head(body));
120 pco_foreach_instr_in_block (instr, block) {
121 pco_instr_set_exec_cnd(instr, exec_cnd);
122 }
123 }
124
125 static inline void
126 lower_if_pred_exec(pco_if *pif, pco_func *func, bool has_else, bool invert_cond)
127 {
128 pco_block *prologue = cf_section_create(func,
129 &pif->cf_node,
130 &pif->prologue,
131 PCO_CF_NODE_FLAG_PROLOGUE);
132
133 /* Setup the prologue. */
134 pco_builder b = pco_builder_create(func, pco_cursor_after_block(prologue));
135
136 /* TODO: see if the cond producer can set p0 directly. */
137 pco_tstz(&b,
138 pco_ref_null(),
139 pco_ref_pred(PCO_PRED_P0),
140 pif->cond,
141 .tst_type_main = PCO_TST_TYPE_MAIN_U32);
142
143 set_body_exec_cnd(&pif->then_body,
144 invert_cond ? PCO_EXEC_CND_E1_Z1 : PCO_EXEC_CND_E1_Z0);
145
146 if (has_else) {
147 set_body_exec_cnd(&pif->else_body,
148 invert_cond ? PCO_EXEC_CND_E1_Z0 : PCO_EXEC_CND_E1_Z1);
149 }
150 }
151
152 static inline void
153 lower_if_cond_exec(pco_if *pif, pco_func *func, bool has_else, bool invert_cond)
154 {
155 pco_block *prologue = cf_section_create(func,
156 &pif->cf_node,
157 &pif->prologue,
158 PCO_CF_NODE_FLAG_PROLOGUE);
159
160 pco_block *interlogue = has_else
161 ? cf_section_create(func,
162 &pif->cf_node,
163 &pif->interlogue,
164 PCO_CF_NODE_FLAG_INTERLOGUE)
165 : NULL;
166
167 pco_block *epilogue = cf_section_create(func,
168 &pif->cf_node,
169 &pif->epilogue,
170 PCO_CF_NODE_FLAG_EPILOGUE);
171
172 /* Setup the prologue. */
173 pco_builder b = pco_builder_create(func, pco_cursor_after_block(prologue));
174 pco_ref emc = emc_ref(func, &b);
175
176 /* TODO: see if the cond producer can set p0 directly. */
177 pco_tstz(&b,
178 pco_ref_null(),
179 pco_ref_pred(PCO_PRED_P0),
180 pif->cond,
181 .tst_type_main = PCO_TST_TYPE_MAIN_U32);
182
183 pco_cndst(&b,
184 pco_ref_pred(PCO_PRED_PE),
185 emc,
186 emc,
187 pco_ref_imm8(1),
188 .exec_cnd = PCO_EXEC_CND_EX_ZX,
189 .cnd = invert_cond ? PCO_CND_P0_TRUE : PCO_CND_P0_FALSE);
190
191 pco_br(&b,
192 has_else ? &interlogue->cf_node : &epilogue->cf_node,
193 .branch_cnd = PCO_BRANCH_CND_ALLINST);
194
195 /* Setup the interlogue (if needed). */
196 if (has_else) {
197 b.cursor = pco_cursor_after_block(interlogue);
198
199 pco_cndef(&b,
200 pco_ref_pred(PCO_PRED_PE),
201 emc,
202 emc,
203 pco_ref_imm8(1),
204 .exec_cnd = PCO_EXEC_CND_EX_ZX,
205 .cnd = PCO_CND_ALWAYS);
206
207 pco_br(&b, &epilogue->cf_node, .branch_cnd = PCO_BRANCH_CND_ALLINST);
208 }
209
210 /* Setup the epilogue. */
211 b.cursor = pco_cursor_after_block(epilogue);
212
213 pco_cndend(&b,
214 pco_ref_pred(PCO_PRED_PE),
215 emc,
216 emc,
217 pco_ref_imm8(1),
218 .exec_cnd = PCO_EXEC_CND_EX_ZX);
219 }
220
221 static inline void lower_if(pco_if *pif, pco_func *func)
222 {
223 assert(!pco_ref_is_null(pif->cond));
224 assert(list_is_empty(&pif->prologue));
225 assert(list_is_empty(&pif->interlogue));
226 assert(list_is_empty(&pif->epilogue));
227
228 bool has_then = !list_is_empty(&pif->then_body);
229 bool has_else = !list_is_empty(&pif->else_body);
230 assert(has_then || has_else);
231
232 /* If we only have an else body, invert the condition and bodies. */
233 bool invert_cond = false;
234 if (!has_then && has_else) {
235 struct list_head temp;
236 memcpy(&temp, &pif->then_body, sizeof(pif->then_body));
237 memcpy(&pif->then_body, &pif->else_body, sizeof(pif->else_body));
238 memcpy(&pif->else_body, &pif->then_body, sizeof(pif->then_body));
239 invert_cond = true;
240
241 has_then = true;
242 has_else = false;
243 }
244
245 assert(has_then);
246
247 if (pif->pred_exec)
248 lower_if_pred_exec(pif, func, has_else, invert_cond);
249 else
250 lower_if_cond_exec(pif, func, has_else, invert_cond);
251
252 pif->cond = pco_ref_null();
253 }
254
255 static inline void lower_loop(pco_loop *loop, pco_func *func)
256 {
257 assert(list_is_empty(&loop->prologue));
258 assert(list_is_empty(&loop->interlogue));
259 assert(list_is_empty(&loop->epilogue));
260
261 pco_block *prologue = cf_section_create(func,
262 &loop->cf_node,
263 &loop->prologue,
264 PCO_CF_NODE_FLAG_PROLOGUE);
265
266 pco_block *interlogue = cf_section_create(func,
267 &loop->cf_node,
268 &loop->interlogue,
269 PCO_CF_NODE_FLAG_INTERLOGUE);
270
271 pco_block *epilogue = cf_section_create(func,
272 &loop->cf_node,
273 &loop->epilogue,
274 PCO_CF_NODE_FLAG_EPILOGUE);
275
276 /* Setup the prologue. */
277 pco_builder b = pco_builder_create(func, pco_cursor_after_block(prologue));
278 pco_ref emc = emc_ref(func, &b);
279
280 pco_cndst(&b,
281 pco_ref_pred(PCO_PRED_PE),
282 emc,
283 emc,
284 pco_ref_imm8(2), /* TODO: make this a define */
285 .exec_cnd = PCO_EXEC_CND_EX_ZX,
286 .cnd = PCO_CND_ALWAYS);
287
288 pco_br(&b, &epilogue->cf_node, .branch_cnd = PCO_BRANCH_CND_ALLINST);
289
290 /* Setup the interlogue. */
291 b.cursor = pco_cursor_after_block(interlogue);
292
293 pco_cndend(&b,
294 pco_ref_pred(PCO_PRED_PE),
295 emc,
296 emc,
297 pco_ref_imm8(1), /* TODO: make this a define */
298 .exec_cnd = PCO_EXEC_CND_EX_ZX);
299
300 pco_cndst(&b,
301 pco_ref_pred(PCO_PRED_PE),
302 emc,
303 emc,
304 pco_ref_imm8(1), /* TODO: make this a define */
305 .exec_cnd = PCO_EXEC_CND_EX_ZX,
306 .cnd = PCO_CND_ALWAYS);
307
308 /* Setup the epilogue. */
309 b.cursor = pco_cursor_after_block(epilogue);
310
311 pco_cndlt(&b,
312 pco_ref_pred(PCO_PRED_PE),
313 emc,
314 pco_ref_pred(PCO_PRED_P0),
315 emc,
316 pco_ref_imm8(2), /* TODO: make this a define */
317 .exec_cnd = PCO_EXEC_CND_EX_ZX,
318 .cnd = PCO_CND_ALWAYS);
319
320 pco_br(&b,
321 pco_cf_node_head(&loop->body),
322 .exec_cnd = PCO_EXEC_CND_E1_Z1,
323 .branch_cnd = PCO_BRANCH_CND_EXEC_COND);
324 }
325
326 static inline void lower_break_continue(pco_instr *instr,
327 pco_func *func,
328 pco_if *pif,
329 pco_loop *loop,
330 unsigned loop_nestings,
331 bool is_continue)
332 {
333 pco_builder b = pco_builder_create(func, pco_cursor_before_instr(instr));
334 pco_ref emc = emc_ref(func, &b);
335 enum pco_exec_cnd exec_cnd = pco_instr_get_exec_cnd(instr);
336
337 pco_ref val = pco_ref_new_ssa32(func);
338 pco_movi32(&b,
339 val,
340 pco_ref_imm32(loop_nestings + (is_continue ? 1 : 2)),
341 .exec_cnd = exec_cnd);
342
343 enum pco_cnd cnd;
344 switch (exec_cnd) {
345 case PCO_CC_E1_ZX:
346 assert(!pif || !pif->pred_exec);
347 cnd = PCO_CND_ALWAYS;
348 break;
349
350 case PCO_CC_E1_Z1:
351 assert(!pif || pif->pred_exec);
352 cnd = PCO_CND_P0_TRUE;
353 break;
354
355 case PCO_CC_E1_Z0:
356 assert(!pif || pif->pred_exec);
357 cnd = PCO_CND_P0_FALSE;
358 break;
359
360 default:
361 UNREACHABLE("");
362 }
363
364 pco_cndsm(&b,
365 pco_ref_pred(PCO_PRED_PE),
366 emc,
367 emc,
368 val,
369 .exec_cnd = PCO_EXEC_CND_EX_ZX,
370 .cnd = cnd);
371
372 pco_instr_delete(instr);
373 }
374
375 static inline bool pco_lower_cf(pco_func *func)
376 {
377 bool progress = false;
378
379 void *mem_ctx = ralloc_context(NULL);
380 unsigned loop_nestings = 0;
381 struct util_dynarray loop_nestings_stack;
382 struct util_dynarray pif_stack;
383 struct util_dynarray loop_stack;
384
385 util_dynarray_init(&loop_nestings_stack, mem_ctx);
386 util_dynarray_init(&pif_stack, mem_ctx);
387 util_dynarray_init(&loop_stack, mem_ctx);
388
389 pco_foreach_cf_node_in_func_structured (cf_node, cf_node_completed, func) {
390 /* Handle the end of an if/loop. */
391 if (cf_node_completed) {
392 switch (cf_node_completed->type) {
393 case PCO_CF_NODE_TYPE_IF: {
394 pco_if *pif = pco_cf_node_as_if(cf_node_completed);
395
396 ASSERTED pco_if *last_pif = util_dynarray_pop(&pif_stack, pco_if *);
397 assert(pif == last_pif);
398
399 if (!pif->pred_exec)
400 --loop_nestings;
401
402 break;
403 }
404
405 case PCO_CF_NODE_TYPE_LOOP: {
406 ASSERTED pco_loop *loop = pco_cf_node_as_loop(cf_node_completed);
407 ASSERTED pco_loop *last_loop =
408 util_dynarray_pop(&loop_stack, pco_loop *);
409 assert(loop == last_loop);
410
411 assert(loop_nestings == 0);
412 loop_nestings = util_dynarray_pop(&loop_nestings_stack, unsigned);
413 break;
414 }
415
416 default:
417 break;
418 }
419 }
420
421 /* Handle the start of an if/loop, or lower break/continue for blocks. */
422 switch (cf_node->type) {
423 case PCO_CF_NODE_TYPE_IF: {
424 pco_if *pif = pco_cf_node_as_if(cf_node);
425 pif->pred_exec = can_pred_exec(pif);
426 util_dynarray_append(&pif_stack, pif);
427
428 if (!pif->pred_exec)
429 ++loop_nestings;
430
431 lower_if(pif, func);
432 progress = true;
433
434 break;
435 }
436
437 case PCO_CF_NODE_TYPE_LOOP: {
438 util_dynarray_append(&loop_nestings_stack, loop_nestings);
439 loop_nestings = 0;
440
441 pco_loop *loop = pco_cf_node_as_loop(cf_node);
442 util_dynarray_append(&loop_stack, loop);
443
444 lower_loop(loop, func);
445 progress = true;
446
447 break;
448 }
449
450 case PCO_CF_NODE_TYPE_BLOCK: {
451 pco_block *block = pco_cf_node_as_block(cf_node);
452 pco_foreach_instr_in_block_safe (instr, block) {
453 if (instr->op != PCO_OP_BREAK && instr->op != PCO_OP_CONTINUE)
454 continue;
455
456 /* This has to be the last instruction in the block. */
457 assert(instr == pco_last_instr(block));
458
459 pco_if *current_pif = NULL;
460 if (instr->parent_block->cf_node.parent->type ==
461 PCO_CF_NODE_TYPE_IF) {
462 current_pif = util_dynarray_top(&pif_stack, pco_if *);
463 assert(current_pif ==
464 pco_cf_node_as_if(instr->parent_block->cf_node.parent));
465 }
466
467 pco_loop *current_loop = util_dynarray_top(&loop_stack, pco_loop *);
468
469 lower_break_continue(instr,
470 func,
471 current_pif,
472 current_loop,
473 loop_nestings,
474 instr->op == PCO_OP_CONTINUE);
475
476 progress = true;
477 }
478
479 break;
480 }
481
482 default:
483 break;
484 }
485 }
486
487 assert(!util_dynarray_num_elements(&loop_stack, pco_loop *));
488 assert(!util_dynarray_num_elements(&pif_stack, pco_if *));
489 assert(!util_dynarray_num_elements(&loop_nestings_stack, unsigned));
490 assert(loop_nestings == 0);
491
492 ralloc_free(mem_ctx);
493
494 return progress;
495 }
496
497 /**
498 * \brief Control-flow pass.
499 *
500 * \param[in,out] shader PCO shader.
501 * \return True if the pass made progress.
502 */
503 bool pco_cf(pco_shader *shader)
504 {
505 bool progress = false;
506
507 pco_foreach_func_in_shader (func, shader) {
508 progress |= pco_lower_cf(func);
509 }
510
511 return progress;
512 }