02aced6b45c454b6cfd71ed1da7f0c316e0c7580
[mesa.git] / src / compiler / nir / nir_opt_gcm.c
1 /*
2 * Copyright © 2014 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 * Authors:
24 * Jason Ekstrand (jason@jlekstrand.net)
25 *
26 */
27
28 #include "nir.h"
29 #include "nir_instr_set.h"
30
31 /*
32 * Implements Global Code Motion. A description of GCM can be found in
33 * "Global Code Motion; Global Value Numbering" by Cliff Click.
34 * Unfortunately, the algorithm presented in the paper is broken in a
35 * number of ways. The algorithm used here differs substantially from the
36 * one in the paper but it is, in my opinion, much easier to read and
37 * verify correcness.
38 */
39
40 struct gcm_block_info {
41 /* Number of loops this block is inside */
42 unsigned loop_depth;
43
44 /* The last instruction inserted into this block. This is used as we
45 * traverse the instructions and insert them back into the program to
46 * put them in the right order.
47 */
48 nir_instr *last_instr;
49 };
50
51 struct gcm_instr_info {
52 nir_block *early_block;
53 };
54
55 /* Flags used in the instr->pass_flags field for various instruction states */
56 enum {
57 GCM_INSTR_PINNED = (1 << 0),
58 GCM_INSTR_SCHEDULE_EARLIER_ONLY = (1 << 1),
59 GCM_INSTR_SCHEDULED_EARLY = (1 << 2),
60 GCM_INSTR_SCHEDULED_LATE = (1 << 3),
61 GCM_INSTR_PLACED = (1 << 4),
62 };
63
64 struct gcm_state {
65 nir_function_impl *impl;
66 nir_instr *instr;
67
68 bool progress;
69
70 /* The list of non-pinned instructions. As we do the late scheduling,
71 * we pull non-pinned instructions out of their blocks and place them in
72 * this list. This saves us from having linked-list problems when we go
73 * to put instructions back in their blocks.
74 */
75 struct exec_list instrs;
76
77 struct gcm_block_info *blocks;
78
79 unsigned num_instrs;
80 struct gcm_instr_info *instr_infos;
81 };
82
83 /* Recursively walks the CFG and builds the block_info structure */
84 static void
85 gcm_build_block_info(struct exec_list *cf_list, struct gcm_state *state,
86 unsigned loop_depth)
87 {
88 foreach_list_typed(nir_cf_node, node, node, cf_list) {
89 switch (node->type) {
90 case nir_cf_node_block: {
91 nir_block *block = nir_cf_node_as_block(node);
92 state->blocks[block->index].loop_depth = loop_depth;
93 break;
94 }
95 case nir_cf_node_if: {
96 nir_if *if_stmt = nir_cf_node_as_if(node);
97 gcm_build_block_info(&if_stmt->then_list, state, loop_depth);
98 gcm_build_block_info(&if_stmt->else_list, state, loop_depth);
99 break;
100 }
101 case nir_cf_node_loop: {
102 nir_loop *loop = nir_cf_node_as_loop(node);
103 gcm_build_block_info(&loop->body, state, loop_depth + 1);
104 break;
105 }
106 default:
107 unreachable("Invalid CF node type");
108 }
109 }
110 }
111
112 static bool
113 is_src_scalarizable(nir_src *src)
114 {
115 assert(src->is_ssa);
116
117 nir_instr *src_instr = src->ssa->parent_instr;
118 switch (src_instr->type) {
119 case nir_instr_type_alu: {
120 nir_alu_instr *src_alu = nir_instr_as_alu(src_instr);
121
122 /* ALU operations with output_size == 0 should be scalarized. We
123 * will also see a bunch of vecN operations from scalarizing ALU
124 * operations and, since they can easily be copy-propagated, they
125 * are ok too.
126 */
127 return nir_op_infos[src_alu->op].output_size == 0 ||
128 src_alu->op == nir_op_vec2 ||
129 src_alu->op == nir_op_vec3 ||
130 src_alu->op == nir_op_vec4;
131 }
132
133 case nir_instr_type_load_const:
134 /* These are trivially scalarizable */
135 return true;
136
137 case nir_instr_type_ssa_undef:
138 return true;
139
140 case nir_instr_type_intrinsic: {
141 nir_intrinsic_instr *src_intrin = nir_instr_as_intrinsic(src_instr);
142
143 switch (src_intrin->intrinsic) {
144 case nir_intrinsic_load_deref: {
145 nir_deref_instr *deref = nir_src_as_deref(src_intrin->src[0]);
146 return deref->mode == nir_var_shader_in ||
147 deref->mode == nir_var_uniform ||
148 deref->mode == nir_var_mem_ubo ||
149 deref->mode == nir_var_mem_ssbo ||
150 deref->mode == nir_var_mem_global;
151 }
152
153 case nir_intrinsic_interp_deref_at_centroid:
154 case nir_intrinsic_interp_deref_at_sample:
155 case nir_intrinsic_interp_deref_at_offset:
156 case nir_intrinsic_load_uniform:
157 case nir_intrinsic_load_ubo:
158 case nir_intrinsic_load_ssbo:
159 case nir_intrinsic_load_global:
160 case nir_intrinsic_load_input:
161 return true;
162 default:
163 break;
164 }
165
166 return false;
167 }
168
169 default:
170 /* We can't scalarize this type of instruction */
171 return false;
172 }
173 }
174
175 /* Walks the instruction list and marks immovable instructions as pinned
176 *
177 * This function also serves to initialize the instr->pass_flags field.
178 * After this is completed, all instructions' pass_flags fields will be set
179 * to either GCM_INSTR_PINNED or 0.
180 */
181 static void
182 gcm_pin_instructions(nir_function_impl *impl, struct gcm_state *state)
183 {
184 state->num_instrs = 0;
185
186 nir_foreach_block(block, impl) {
187 nir_foreach_instr_safe(instr, block) {
188 /* Index the instructions for use in gcm_state::instrs */
189 instr->index = state->num_instrs++;
190
191 switch (instr->type) {
192 case nir_instr_type_alu:
193 switch (nir_instr_as_alu(instr)->op) {
194 case nir_op_fddx:
195 case nir_op_fddy:
196 case nir_op_fddx_fine:
197 case nir_op_fddy_fine:
198 case nir_op_fddx_coarse:
199 case nir_op_fddy_coarse:
200 /* These can only go in uniform control flow */
201 instr->pass_flags = GCM_INSTR_SCHEDULE_EARLIER_ONLY;
202 break;
203
204 case nir_op_mov:
205 if (!is_src_scalarizable(&(nir_instr_as_alu(instr)->src[0].src))) {
206 instr->pass_flags = GCM_INSTR_PINNED;
207 break;
208 }
209 /* fallthrough */
210
211 default:
212 instr->pass_flags = 0;
213 break;
214 }
215 break;
216
217 case nir_instr_type_tex:
218 if (nir_tex_instr_has_implicit_derivative(nir_instr_as_tex(instr)))
219 instr->pass_flags = GCM_INSTR_SCHEDULE_EARLIER_ONLY;
220 break;
221
222 case nir_instr_type_deref:
223 case nir_instr_type_load_const:
224 instr->pass_flags = 0;
225 break;
226
227 case nir_instr_type_intrinsic: {
228 if (nir_intrinsic_can_reorder(nir_instr_as_intrinsic(instr))) {
229 instr->pass_flags = 0;
230 } else {
231 instr->pass_flags = GCM_INSTR_PINNED;
232 }
233 break;
234 }
235
236 case nir_instr_type_jump:
237 case nir_instr_type_ssa_undef:
238 case nir_instr_type_phi:
239 instr->pass_flags = GCM_INSTR_PINNED;
240 break;
241
242 default:
243 unreachable("Invalid instruction type in GCM");
244 }
245
246 if (!(instr->pass_flags & GCM_INSTR_PINNED)) {
247 /* If this is an unpinned instruction, go ahead and pull it out of
248 * the program and put it on the instrs list. This has a couple
249 * of benifits. First, it makes the scheduling algorithm more
250 * efficient because we can avoid walking over basic blocks and
251 * pinned instructions. Second, it keeps us from causing linked
252 * list confusion when we're trying to put everything in its
253 * proper place at the end of the pass.
254 *
255 * Note that we don't use nir_instr_remove here because that also
256 * cleans up uses and defs and we want to keep that information.
257 */
258 exec_node_remove(&instr->node);
259 exec_list_push_tail(&state->instrs, &instr->node);
260 }
261 }
262 }
263 }
264
265 static void
266 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state);
267
268 /** Update an instructions schedule for the given source
269 *
270 * This function is called iteratively as we walk the sources of an
271 * instruction. It ensures that the given source instruction has been
272 * scheduled and then update this instruction's block if the source
273 * instruction is lower down the tree.
274 */
275 static bool
276 gcm_schedule_early_src(nir_src *src, void *void_state)
277 {
278 struct gcm_state *state = void_state;
279 nir_instr *instr = state->instr;
280
281 assert(src->is_ssa);
282
283 gcm_schedule_early_instr(src->ssa->parent_instr, void_state);
284
285 /* While the index isn't a proper dominance depth, it does have the
286 * property that if A dominates B then A->index <= B->index. Since we
287 * know that this instruction must have been dominated by all of its
288 * sources at some point (even if it's gone through value-numbering),
289 * all of the sources must lie on the same branch of the dominance tree.
290 * Therefore, we can just go ahead and just compare indices.
291 */
292 struct gcm_instr_info *src_info =
293 &state->instr_infos[src->ssa->parent_instr->index];
294 struct gcm_instr_info *info = &state->instr_infos[instr->index];
295 if (info->early_block->index < src_info->early_block->index)
296 info->early_block = src_info->early_block;
297
298 /* We need to restore the state instruction because it may have been
299 * changed through the gcm_schedule_early_instr call above. Since we
300 * may still be iterating through sources and future calls to
301 * gcm_schedule_early_src for the same instruction will still need it.
302 */
303 state->instr = instr;
304
305 return true;
306 }
307
308 /** Schedules an instruction early
309 *
310 * This function performs a recursive depth-first search starting at the
311 * given instruction and proceeding through the sources to schedule
312 * instructions as early as they can possibly go in the dominance tree.
313 * The instructions are "scheduled" by updating the early_block field of
314 * the corresponding gcm_instr_state entry.
315 */
316 static void
317 gcm_schedule_early_instr(nir_instr *instr, struct gcm_state *state)
318 {
319 if (instr->pass_flags & GCM_INSTR_SCHEDULED_EARLY)
320 return;
321
322 instr->pass_flags |= GCM_INSTR_SCHEDULED_EARLY;
323
324 /* Pinned instructions always get scheduled in their original block so we
325 * don't need to do anything. Also, bailing here keeps us from ever
326 * following the sources of phi nodes which can be back-edges.
327 */
328 if (instr->pass_flags & GCM_INSTR_PINNED) {
329 state->instr_infos[instr->index].early_block = instr->block;
330 return;
331 }
332
333 /* Start with the instruction at the top. As we iterate over the
334 * sources, it will get moved down as needed.
335 */
336 state->instr_infos[instr->index].early_block = nir_start_block(state->impl);
337 state->instr = instr;
338
339 nir_foreach_src(instr, gcm_schedule_early_src, state);
340 }
341
342 static nir_block *
343 gcm_choose_block_for_instr(nir_instr *instr, nir_block *early_block,
344 nir_block *late_block, struct gcm_state *state)
345 {
346 assert(nir_block_dominates(early_block, late_block));
347
348 nir_block *best = late_block;
349 for (nir_block *block = late_block; block != NULL; block = block->imm_dom) {
350 /* Being too aggressive with how we pull instructions out of loops can
351 * result in extra register pressure and spilling. For example its fairly
352 * common for loops in compute shaders to calculate SSBO offsets using
353 * the workgroup id, subgroup id and subgroup invocation, pulling all
354 * these calculations outside the loop causes register pressure.
355 *
356 * To work around these issues for now we only allow constant and texture
357 * instructions to be moved outside their original loops.
358 *
359 * TODO: figure out some heuristics to allow more to be moved out of loops.
360 */
361 if (state->blocks[block->index].loop_depth <
362 state->blocks[best->index].loop_depth &&
363 (nir_block_dominates(instr->block, block) ||
364 instr->type == nir_instr_type_load_const ||
365 instr->type == nir_instr_type_tex))
366 best = block;
367 else if (block == instr->block)
368 best = block;
369
370 if (block == early_block)
371 break;
372 }
373
374 return best;
375 }
376
377 static void
378 gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state);
379
380 /** Schedules the instruction associated with the given SSA def late
381 *
382 * This function works by first walking all of the uses of the given SSA
383 * definition, ensuring that they are scheduled, and then computing the LCA
384 * (least common ancestor) of its uses. It then schedules this instruction
385 * as close to the LCA as possible while trying to stay out of loops.
386 */
387 static bool
388 gcm_schedule_late_def(nir_ssa_def *def, void *void_state)
389 {
390 struct gcm_state *state = void_state;
391
392 nir_block *lca = NULL;
393
394 nir_foreach_use(use_src, def) {
395 nir_instr *use_instr = use_src->parent_instr;
396
397 gcm_schedule_late_instr(use_instr, state);
398
399 /* Phi instructions are a bit special. SSA definitions don't have to
400 * dominate the sources of the phi nodes that use them; instead, they
401 * have to dominate the predecessor block corresponding to the phi
402 * source. We handle this by looking through the sources, finding
403 * any that are usingg this SSA def, and using those blocks instead
404 * of the one the phi lives in.
405 */
406 if (use_instr->type == nir_instr_type_phi) {
407 nir_phi_instr *phi = nir_instr_as_phi(use_instr);
408
409 nir_foreach_phi_src(phi_src, phi) {
410 if (phi_src->src.ssa == def)
411 lca = nir_dominance_lca(lca, phi_src->pred);
412 }
413 } else {
414 lca = nir_dominance_lca(lca, use_instr->block);
415 }
416 }
417
418 nir_foreach_if_use(use_src, def) {
419 nir_if *if_stmt = use_src->parent_if;
420
421 /* For if statements, we consider the block to be the one immediately
422 * preceding the if CF node.
423 */
424 nir_block *pred_block =
425 nir_cf_node_as_block(nir_cf_node_prev(&if_stmt->cf_node));
426
427 lca = nir_dominance_lca(lca, pred_block);
428 }
429
430 nir_block *early_block =
431 state->instr_infos[def->parent_instr->index].early_block;
432
433 /* Some instructions may never be used. Flag them and the instruction
434 * placement code will get rid of them for us.
435 */
436 if (lca == NULL) {
437 def->parent_instr->block = NULL;
438 return true;
439 }
440
441 if (def->parent_instr->pass_flags & GCM_INSTR_SCHEDULE_EARLIER_ONLY &&
442 lca != def->parent_instr->block &&
443 nir_block_dominates(def->parent_instr->block, lca)) {
444 lca = def->parent_instr->block;
445 }
446
447 /* We now have the LCA of all of the uses. If our invariants hold,
448 * this is dominated by the block that we chose when scheduling early.
449 * We now walk up the dominance tree and pick the lowest block that is
450 * as far outside loops as we can get.
451 */
452 nir_block *best_block =
453 gcm_choose_block_for_instr(def->parent_instr, early_block, lca, state);
454
455 if (def->parent_instr->block != best_block)
456 state->progress = true;
457
458 def->parent_instr->block = best_block;
459
460 return true;
461 }
462
463 /** Schedules an instruction late
464 *
465 * This function performs a depth-first search starting at the given
466 * instruction and proceeding through its uses to schedule instructions as
467 * late as they can reasonably go in the dominance tree. The instructions
468 * are "scheduled" by updating their instr->block field.
469 *
470 * The name of this function is actually a bit of a misnomer as it doesn't
471 * schedule them "as late as possible" as the paper implies. Instead, it
472 * first finds the lates possible place it can schedule the instruction and
473 * then possibly schedules it earlier than that. The actual location is as
474 * far down the tree as we can go while trying to stay out of loops.
475 */
476 static void
477 gcm_schedule_late_instr(nir_instr *instr, struct gcm_state *state)
478 {
479 if (instr->pass_flags & GCM_INSTR_SCHEDULED_LATE)
480 return;
481
482 instr->pass_flags |= GCM_INSTR_SCHEDULED_LATE;
483
484 /* Pinned instructions are already scheduled so we don't need to do
485 * anything. Also, bailing here keeps us from ever following phi nodes
486 * which can be back-edges.
487 */
488 if (instr->pass_flags & GCM_INSTR_PINNED)
489 return;
490
491 nir_foreach_ssa_def(instr, gcm_schedule_late_def, state);
492 }
493
494 static void
495 gcm_place_instr(nir_instr *instr, struct gcm_state *state);
496
497 static bool
498 gcm_place_instr_def(nir_ssa_def *def, void *state)
499 {
500 nir_foreach_use(use_src, def)
501 gcm_place_instr(use_src->parent_instr, state);
502
503 return false;
504 }
505
506 static bool
507 gcm_replace_def_with_undef(nir_ssa_def *def, void *void_state)
508 {
509 struct gcm_state *state = void_state;
510
511 if (list_is_empty(&def->uses) && list_is_empty(&def->if_uses))
512 return true;
513
514 nir_ssa_undef_instr *undef =
515 nir_ssa_undef_instr_create(state->impl->function->shader,
516 def->num_components, def->bit_size);
517 nir_instr_insert(nir_before_cf_list(&state->impl->body), &undef->instr);
518 nir_ssa_def_rewrite_uses(def, nir_src_for_ssa(&undef->def));
519
520 return true;
521 }
522
523 /** Places an instrution back into the program
524 *
525 * The earlier passes of GCM simply choose blocks for each instruction and
526 * otherwise leave them alone. This pass actually places the instructions
527 * into their chosen blocks.
528 *
529 * To do so, we use a standard post-order depth-first search linearization
530 * algorithm. We walk over the uses of the given instruction and ensure
531 * that they are placed and then place this instruction. Because we are
532 * working on multiple blocks at a time, we keep track of the last inserted
533 * instruction per-block in the state structure's block_info array. When
534 * we insert an instruction in a block we insert it before the last
535 * instruction inserted in that block rather than the last instruction
536 * inserted globally.
537 */
538 static void
539 gcm_place_instr(nir_instr *instr, struct gcm_state *state)
540 {
541 if (instr->pass_flags & GCM_INSTR_PLACED)
542 return;
543
544 instr->pass_flags |= GCM_INSTR_PLACED;
545
546 if (instr->block == NULL) {
547 nir_foreach_ssa_def(instr, gcm_replace_def_with_undef, state);
548 nir_instr_remove(instr);
549 return;
550 }
551
552 /* Phi nodes are our once source of back-edges. Since right now we are
553 * only doing scheduling within blocks, we don't need to worry about
554 * them since they are always at the top. Just skip them completely.
555 */
556 if (instr->type == nir_instr_type_phi) {
557 assert(instr->pass_flags & GCM_INSTR_PINNED);
558 return;
559 }
560
561 nir_foreach_ssa_def(instr, gcm_place_instr_def, state);
562
563 if (instr->pass_flags & GCM_INSTR_PINNED) {
564 /* Pinned instructions have an implicit dependence on the pinned
565 * instructions that come after them in the block. Since the pinned
566 * instructions will naturally "chain" together, we only need to
567 * explicitly visit one of them.
568 */
569 for (nir_instr *after = nir_instr_next(instr);
570 after;
571 after = nir_instr_next(after)) {
572 if (after->pass_flags & GCM_INSTR_PINNED) {
573 gcm_place_instr(after, state);
574 break;
575 }
576 }
577 }
578
579 struct gcm_block_info *block_info = &state->blocks[instr->block->index];
580 if (!(instr->pass_flags & GCM_INSTR_PINNED)) {
581 exec_node_remove(&instr->node);
582
583 if (block_info->last_instr) {
584 exec_node_insert_node_before(&block_info->last_instr->node,
585 &instr->node);
586 } else {
587 /* Schedule it at the end of the block */
588 nir_instr *jump_instr = nir_block_last_instr(instr->block);
589 if (jump_instr && jump_instr->type == nir_instr_type_jump) {
590 exec_node_insert_node_before(&jump_instr->node, &instr->node);
591 } else {
592 exec_list_push_tail(&instr->block->instr_list, &instr->node);
593 }
594 }
595 }
596
597 block_info->last_instr = instr;
598 }
599
600 static bool
601 opt_gcm_impl(nir_function_impl *impl, bool value_number)
602 {
603 nir_metadata_require(impl, nir_metadata_block_index |
604 nir_metadata_dominance);
605
606 struct gcm_state state;
607
608 state.impl = impl;
609 state.instr = NULL;
610 state.progress = false;
611 exec_list_make_empty(&state.instrs);
612 state.blocks = rzalloc_array(NULL, struct gcm_block_info, impl->num_blocks);
613
614 gcm_build_block_info(&impl->body, &state, 0);
615
616 gcm_pin_instructions(impl, &state);
617
618 state.instr_infos =
619 rzalloc_array(NULL, struct gcm_instr_info, state.num_instrs);
620
621 if (value_number) {
622 struct set *gvn_set = nir_instr_set_create(NULL);
623 foreach_list_typed_safe(nir_instr, instr, node, &state.instrs) {
624 if (nir_instr_set_add_or_rewrite(gvn_set, instr)) {
625 nir_instr_remove(instr);
626 state.progress = true;
627 }
628 }
629 nir_instr_set_destroy(gvn_set);
630 }
631
632 foreach_list_typed(nir_instr, instr, node, &state.instrs)
633 gcm_schedule_early_instr(instr, &state);
634
635 foreach_list_typed(nir_instr, instr, node, &state.instrs)
636 gcm_schedule_late_instr(instr, &state);
637
638 while (!exec_list_is_empty(&state.instrs)) {
639 nir_instr *instr = exec_node_data(nir_instr,
640 state.instrs.tail_sentinel.prev, node);
641 gcm_place_instr(instr, &state);
642 }
643
644 ralloc_free(state.blocks);
645 ralloc_free(state.instr_infos);
646
647 nir_metadata_preserve(impl, nir_metadata_block_index |
648 nir_metadata_dominance);
649
650 return state.progress;
651 }
652
653 bool
654 nir_opt_gcm(nir_shader *shader, bool value_number)
655 {
656 bool progress = false;
657
658 nir_foreach_function(function, shader) {
659 if (function->impl)
660 progress |= opt_gcm_impl(function->impl, value_number);
661 }
662
663 return progress;
664 }