1 /*
2 * Copyright 2024 Valve Corporation
3 * SPDX-License-Identifier: MIT
4 */
5
6 #include "nir.h"
7
8 static bool
defined_before_loop(nir_src * src,void * state)9 defined_before_loop(nir_src *src, void *state)
10 {
11 unsigned *loop_preheader_idx = state;
12 return src->ssa->parent_instr->block->index <= *loop_preheader_idx;
13 }
14
15 static bool
is_instr_loop_invariant(nir_instr * instr,unsigned loop_preheader_idx)16 is_instr_loop_invariant(nir_instr *instr, unsigned loop_preheader_idx)
17 {
18 switch (instr->type) {
19 case nir_instr_type_load_const:
20 case nir_instr_type_undef:
21 return true;
22
23 case nir_instr_type_intrinsic:
24 if (!nir_intrinsic_can_reorder(nir_instr_as_intrinsic(instr)))
25 return false;
26 FALLTHROUGH;
27
28 case nir_instr_type_alu:
29 case nir_instr_type_tex:
30 case nir_instr_type_deref:
31 return nir_foreach_src(instr, defined_before_loop, &loop_preheader_idx);
32
33 case nir_instr_type_phi:
34 case nir_instr_type_call:
35 case nir_instr_type_jump:
36 default:
37 return false;
38 }
39 }
40
41 static bool
visit_block(nir_block * block,nir_block * preheader)42 visit_block(nir_block *block, nir_block *preheader)
43 {
44 bool progress = false;
45 nir_foreach_instr_safe(instr, block) {
46 if (is_instr_loop_invariant(instr, preheader->index)) {
47 nir_instr_remove(instr);
48 nir_instr_insert_after_block(preheader, instr);
49 progress = true;
50 }
51 }
52
53 return progress;
54 }
55
56 static bool
should_optimize_loop(nir_loop * loop)57 should_optimize_loop(nir_loop *loop)
58 {
59 /* Ignore loops without back-edge */
60 if (nir_loop_first_block(loop)->predecessors->entries == 1)
61 return false;
62
63 nir_foreach_block_in_cf_node(block, &loop->cf_node) {
64 /* Check for an early exit inside the loop. */
65 nir_foreach_instr(instr, block) {
66 if (instr->type == nir_instr_type_intrinsic) {
67 nir_intrinsic_instr *intrin = nir_instr_as_intrinsic(instr);
68 if (intrin->intrinsic == nir_intrinsic_terminate ||
69 intrin->intrinsic == nir_intrinsic_terminate_if)
70 return false;
71 }
72 }
73
74 /* The loop must not contains any return statement. */
75 if (nir_block_ends_in_return_or_halt(block))
76 return false;
77 }
78
79 return true;
80 }
81
82 static bool
visit_cf_list(struct exec_list * list,nir_block * preheader,nir_block * exit)83 visit_cf_list(struct exec_list *list, nir_block *preheader, nir_block *exit)
84 {
85 bool progress = false;
86
87 foreach_list_typed(nir_cf_node, node, node, list) {
88 switch (node->type) {
89 case nir_cf_node_block: {
90 /* By only visiting blocks which dominate the loop exit, we
91 * ensure that we don't speculatively hoist any instructions
92 * which otherwise might not be executed.
93 *
94 * Note, that the proper check would be whether this block
95 * postdominates the loop preheader.
96 */
97 nir_block *block = nir_cf_node_as_block(node);
98 if (exit && nir_block_dominates(block, exit))
99 progress |= visit_block(block, preheader);
100 break;
101 }
102 case nir_cf_node_if: {
103 nir_if *nif = nir_cf_node_as_if(node);
104 progress |= visit_cf_list(&nif->then_list, preheader, exit);
105 progress |= visit_cf_list(&nif->else_list, preheader, exit);
106 break;
107 }
108 case nir_cf_node_loop: {
109 nir_loop *loop = nir_cf_node_as_loop(node);
110 bool opt = should_optimize_loop(loop);
111 nir_block *inner_preheader = opt ? nir_cf_node_cf_tree_prev(node) : preheader;
112 nir_block *inner_exit = opt ? nir_cf_node_cf_tree_next(node) : exit;
113 progress |= visit_cf_list(&loop->body, inner_preheader, inner_exit);
114 progress |= visit_cf_list(&loop->continue_list, inner_preheader, inner_exit);
115 break;
116 }
117 case nir_cf_node_function:
118 unreachable("NIR LICM: Unsupported cf_node type.");
119 }
120 }
121
122 return progress;
123 }
124
125 bool
nir_opt_licm(nir_shader * shader)126 nir_opt_licm(nir_shader *shader)
127 {
128 bool progress = false;
129
130 nir_foreach_function_impl(impl, shader) {
131 nir_metadata_require(impl, nir_metadata_block_index |
132 nir_metadata_dominance);
133
134 if (visit_cf_list(&impl->body, NULL, NULL)) {
135 progress = true;
136 nir_metadata_preserve(impl, nir_metadata_block_index |
137 nir_metadata_dominance);
138 } else {
139 nir_metadata_preserve(impl, nir_metadata_all);
140 }
141 }
142
143 return progress;
144 }
145