2 * Copyright © 2014 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 * Jason Ekstrand (jason@jlekstrand.net)
28 #include "nir_worklist.h"
32 * Basic liveness analysis. This works only in SSA form.
34 * This liveness pass treats phi nodes as being melded to the space between
35 * blocks so that the destinations of a phi are in the livein of the block
36 * in which it resides and the sources are in the liveout of the
37 * corresponding block. By formulating the liveness information in this
38 * way, we ensure that the definition of any variable dominates its entire
39 * live range. This is true because the only way that the definition of an
40 * SSA value may not dominate a use is if the use is in a phi node and the
41 * uses in phi no are in the live-out of the corresponding predecessor
42 * block but not in the live-in of the block containing the phi node.
45 struct live_ssa_defs_state
{
46 unsigned num_ssa_defs
;
47 unsigned bitset_words
;
49 nir_block_worklist worklist
;
53 index_ssa_def(nir_ssa_def
*def
, void *void_state
)
55 struct live_ssa_defs_state
*state
= void_state
;
57 if (def
->parent_instr
->type
== nir_instr_type_ssa_undef
)
60 def
->live_index
= state
->num_ssa_defs
++;
65 /* Initialize the liveness data to zero and add the given block to the
69 init_liveness_block(nir_block
*block
,
70 struct live_ssa_defs_state
*state
)
72 block
->live_in
= reralloc(block
, block
->live_in
, BITSET_WORD
,
74 memset(block
->live_in
, 0, state
->bitset_words
* sizeof(BITSET_WORD
));
76 block
->live_out
= reralloc(block
, block
->live_out
, BITSET_WORD
,
78 memset(block
->live_out
, 0, state
->bitset_words
* sizeof(BITSET_WORD
));
80 nir_block_worklist_push_head(&state
->worklist
, block
);
86 set_src_live(nir_src
*src
, void *void_live
)
88 BITSET_WORD
*live
= void_live
;
93 if (src
->ssa
->live_index
== 0)
94 return true; /* undefined variables are never live */
96 BITSET_SET(live
, src
->ssa
->live_index
);
102 set_ssa_def_dead(nir_ssa_def
*def
, void *void_live
)
104 BITSET_WORD
*live
= void_live
;
106 BITSET_CLEAR(live
, def
->live_index
);
111 /** Propagates the live in of succ across the edge to the live out of pred
113 * Phi nodes exist "between" blocks and all the phi nodes at the start of a
114 * block act "in parallel". When we propagate from the live_in of one
115 * block to the live out of the other, we have to kill any writes from phis
116 * and make live any sources.
118 * Returns true if updating live out of pred added anything
121 propagate_across_edge(nir_block
*pred
, nir_block
*succ
,
122 struct live_ssa_defs_state
*state
)
124 NIR_VLA(BITSET_WORD
, live
, state
->bitset_words
);
125 memcpy(live
, succ
->live_in
, state
->bitset_words
* sizeof *live
);
127 nir_foreach_instr(instr
, succ
) {
128 if (instr
->type
!= nir_instr_type_phi
)
130 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
132 assert(phi
->dest
.is_ssa
);
133 set_ssa_def_dead(&phi
->dest
.ssa
, live
);
136 nir_foreach_instr(instr
, succ
) {
137 if (instr
->type
!= nir_instr_type_phi
)
139 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
141 nir_foreach_phi_src(src
, phi
) {
142 if (src
->pred
== pred
) {
143 set_src_live(&src
->src
, live
);
149 BITSET_WORD progress
= 0;
150 for (unsigned i
= 0; i
< state
->bitset_words
; ++i
) {
151 progress
|= live
[i
] & ~pred
->live_out
[i
];
152 pred
->live_out
[i
] |= live
[i
];
154 return progress
!= 0;
158 nir_live_ssa_defs_impl(nir_function_impl
*impl
)
160 struct live_ssa_defs_state state
;
162 /* We start at 1 because we reserve the index value of 0 for ssa_undef
163 * instructions. Those are never live, so their liveness information
164 * can be compacted into a single bit.
166 state
.num_ssa_defs
= 1;
167 nir_foreach_block(block
, impl
) {
168 nir_foreach_instr(instr
, block
)
169 nir_foreach_ssa_def(instr
, index_ssa_def
, &state
);
172 nir_block_worklist_init(&state
.worklist
, impl
->num_blocks
, NULL
);
174 /* We now know how many unique ssa definitions we have and we can go
175 * ahead and allocate live_in and live_out sets and add all of the
176 * blocks to the worklist.
178 state
.bitset_words
= BITSET_WORDS(state
.num_ssa_defs
);
179 nir_foreach_block(block
, impl
) {
180 init_liveness_block(block
, &state
);
184 /* We're now ready to work through the worklist and update the liveness
185 * sets of each of the blocks. By the time we get to this point, every
186 * block in the function implementation has been pushed onto the
187 * worklist in reverse order. As long as we keep the worklist
188 * up-to-date as we go, everything will get covered.
190 while (!nir_block_worklist_is_empty(&state
.worklist
)) {
191 /* We pop them off in the reverse order we pushed them on. This way
192 * the first walk of the instructions is backwards so we only walk
193 * once in the case of no control flow.
195 nir_block
*block
= nir_block_worklist_pop_head(&state
.worklist
);
197 memcpy(block
->live_in
, block
->live_out
,
198 state
.bitset_words
* sizeof(BITSET_WORD
));
200 nir_if
*following_if
= nir_block_get_following_if(block
);
202 set_src_live(&following_if
->condition
, block
->live_in
);
204 nir_foreach_instr_reverse(instr
, block
) {
205 /* Phi nodes are handled seperately so we want to skip them. Since
206 * we are going backwards and they are at the beginning, we can just
207 * break as soon as we see one.
209 if (instr
->type
== nir_instr_type_phi
)
212 nir_foreach_ssa_def(instr
, set_ssa_def_dead
, block
->live_in
);
213 nir_foreach_src(instr
, set_src_live
, block
->live_in
);
216 /* Walk over all of the predecessors of the current block updating
217 * their live in with the live out of this one. If anything has
218 * changed, add the predecessor to the work list so that we ensure
219 * that the new information is used.
221 struct set_entry
*entry
;
222 set_foreach(block
->predecessors
, entry
) {
223 nir_block
*pred
= (nir_block
*)entry
->key
;
224 if (propagate_across_edge(pred
, block
, &state
))
225 nir_block_worklist_push_tail(&state
.worklist
, pred
);
229 nir_block_worklist_fini(&state
.worklist
);
233 src_does_not_use_def(nir_src
*src
, void *def
)
235 return !src
->is_ssa
|| src
->ssa
!= (nir_ssa_def
*)def
;
239 search_for_use_after_instr(nir_instr
*start
, nir_ssa_def
*def
)
241 /* Only look for a use strictly after the given instruction */
242 struct exec_node
*node
= start
->node
.next
;
243 while (!exec_node_is_tail_sentinel(node
)) {
244 nir_instr
*instr
= exec_node_data(nir_instr
, node
, node
);
245 if (!nir_foreach_src(instr
, src_does_not_use_def
, def
))
252 /* Returns true if def is live at instr assuming that def comes before
253 * instr in a pre DFS search of the dominance tree.
256 nir_ssa_def_is_live_at(nir_ssa_def
*def
, nir_instr
*instr
)
258 if (BITSET_TEST(instr
->block
->live_out
, def
->live_index
)) {
259 /* Since def dominates instr, if def is in the liveout of the block,
264 if (BITSET_TEST(instr
->block
->live_in
, def
->live_index
) ||
265 def
->parent_instr
->block
== instr
->block
) {
266 /* In this case it is either live coming into instr's block or it
267 * is defined in the same block. In this case, we simply need to
268 * see if it is used after instr.
270 return search_for_use_after_instr(instr
, def
);
278 nir_ssa_defs_interfere(nir_ssa_def
*a
, nir_ssa_def
*b
)
280 if (a
->parent_instr
== b
->parent_instr
) {
281 /* Two variables defined at the same time interfere assuming at
282 * least one isn't dead.
285 } else if (a
->live_index
== 0 || b
->live_index
== 0) {
286 /* If either variable is an ssa_undef, then there's no interference */
288 } else if (a
->live_index
< b
->live_index
) {
289 return nir_ssa_def_is_live_at(a
, b
->parent_instr
);
291 return nir_ssa_def_is_live_at(b
, a
->parent_instr
);