1 /*
2 * Copyright © 2016 Intel Corporation
3 * Copyright © 2019 Valve Corporation
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 */
24
25 #include "nir.h"
26
27 /**
28 * \file nir_opt_move.c
29 *
30 * This pass can move various operations just before their first use inside the
31 * same basic block. Usually this is to reduce register usage. It's probably
32 * not a good idea to use this in an optimization loop.
33 *
34 * Moving comparisons is useful because many GPUs generate condition codes
35 * for comparisons, and use predication for conditional selects and control
36 * flow. In a sequence such as:
37 *
38 * vec1 32 ssa_1 = flt a b
39 * <some other operations>
40 * vec1 32 ssa_2 = bcsel ssa_1 c d
41 *
42 * the backend would likely do the comparison, producing condition codes,
43 * then save those to a boolean value. The intervening operations might
44 * trash the condition codes. Then, in order to do the bcsel, it would
45 * need to re-populate the condition code register based on the boolean.
46 *
47 * By moving the comparison just before the bcsel, the condition codes could
48 * be used directly. This eliminates the need to reload them from the boolean
49 * (generally eliminating an instruction). It may also eliminate the need to
50 * create a boolean value altogether (unless it's used elsewhere), which could
51 * lower register pressure.
52 */
53
54 static bool
nir_opt_move_block(nir_block * block,nir_move_options options)55 nir_opt_move_block(nir_block *block, nir_move_options options)
56 {
57 bool progress = false;
58 nir_instr *last_instr = nir_block_ends_in_jump(block) ? nir_block_last_instr(block) : NULL;
59 const nir_if *iff = nir_block_get_following_if(block);
60 const nir_instr *if_cond_instr = iff ? iff->condition.ssa->parent_instr : NULL;
61
62 /* Walk the instructions backwards.
63 * The instructions get indexed while iterating.
64 * For each instruction which can be moved, find the earliest user
65 * and insert the instruction before it.
66 * If multiple instructions have the same user,
67 * the original order is kept.
68 */
69 unsigned index = 1;
70 nir_foreach_instr_reverse_safe(instr, block) {
71 instr->index = index++;
72
73 /* Check if this instruction can be moved downwards */
74 if (!nir_can_move_instr(instr, options))
75 continue;
76
77 /* Check all users in this block which is the first */
78 const nir_def *def = nir_instr_def(instr);
79 nir_instr *first_user = instr == if_cond_instr ? NULL : last_instr;
80 nir_foreach_use(use, def) {
81 nir_instr *parent = nir_src_parent_instr(use);
82 if (parent->type == nir_instr_type_phi || parent->block != block)
83 continue;
84 if (!first_user || parent->index > first_user->index)
85 first_user = parent;
86 }
87
88 if (first_user) {
89 /* Check predecessor instructions for the same index to keep the order */
90 while (nir_instr_prev(first_user)->index == first_user->index)
91 first_user = nir_instr_prev(first_user);
92
93 /* check if the user is already the immediate successor */
94 if (nir_instr_prev(first_user) == instr)
95 continue;
96
97 /* Insert the instruction before it's first user */
98 exec_node_remove(&instr->node);
99 instr->index = first_user->index;
100 exec_node_insert_node_before(&first_user->node, &instr->node);
101 progress = true;
102 continue;
103 }
104
105 /* No user was found in this block:
106 * This instruction will be moved to the end of the block.
107 */
108 assert(nir_block_last_instr(block)->type != nir_instr_type_jump);
109 if (instr == nir_block_last_instr(block))
110 continue;
111
112 exec_node_remove(&instr->node);
113 instr->index = 0;
114 exec_list_push_tail(&block->instr_list, &instr->node);
115
116 /* update last_instr */
117 last_instr = instr;
118
119 progress = true;
120 }
121
122 return progress;
123 }
124
125 bool
nir_opt_move(nir_shader * shader,nir_move_options options)126 nir_opt_move(nir_shader *shader, nir_move_options options)
127 {
128 bool progress = false;
129
130 nir_foreach_function_impl(impl, shader) {
131 bool impl_progress = false;
132 nir_foreach_block(block, impl) {
133 if (nir_opt_move_block(block, options))
134 impl_progress = true;
135 }
136
137 if (impl_progress) {
138 nir_metadata_preserve(impl, nir_metadata_control_flow |
139 nir_metadata_live_defs);
140 progress = true;
141 } else {
142 nir_metadata_preserve(impl, nir_metadata_all);
143 }
144 }
145
146 return progress;
147 }
148