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)
30 * Basic liveness analysis. This works only in SSA form.
32 * This liveness pass treats phi nodes as being melded to the space between
33 * blocks so that the destinations of a phi are in the livein of the block
34 * in which it resides and the sources are in the liveout of the
35 * corresponding block. By formulating the liveness information in this
36 * way, we ensure that the definition of any variable dominates its entire
37 * live range. This is true because the only way that the definition of an
38 * SSA value may not dominate a use is if the use is in a phi node and the
39 * uses in phi no are in the live-out of the corresponding predecessor
40 * block but not in the live-in of the block containing the phi node.
43 struct live_variables_state
{
44 unsigned num_ssa_defs
;
45 unsigned bitset_words
;
50 index_ssa_def(nir_ssa_def
*def
, void *void_state
)
52 struct live_variables_state
*state
= void_state
;
54 if (def
->parent_instr
->type
== nir_instr_type_ssa_undef
)
57 def
->live_index
= state
->num_ssa_defs
++;
63 index_ssa_definitions_block(nir_block
*block
, void *state
)
65 nir_foreach_instr(block
, instr
)
66 nir_foreach_ssa_def(instr
, index_ssa_def
, state
);
72 init_liveness_block(nir_block
*block
, void *void_state
)
74 struct live_variables_state
*state
= void_state
;
76 block
->live_in
= reralloc(block
, block
->live_in
, BITSET_WORD
,
78 memset(block
->live_in
, 0, state
->bitset_words
* sizeof(BITSET_WORD
));
80 block
->live_out
= reralloc(block
, block
->live_out
, BITSET_WORD
,
82 memset(block
->live_out
, 0, state
->bitset_words
* sizeof(BITSET_WORD
));
88 set_src_live(nir_src
*src
, void *void_live
)
90 BITSET_WORD
*live
= void_live
;
95 if (src
->ssa
->live_index
== 0)
96 return true; /* undefined variables are never live */
98 BITSET_SET(live
, src
->ssa
->live_index
);
104 set_ssa_def_dead(nir_ssa_def
*def
, void *void_live
)
106 BITSET_WORD
*live
= void_live
;
108 BITSET_CLEAR(live
, def
->live_index
);
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.
119 propagate_across_edge(nir_block
*pred
, nir_block
*succ
,
120 struct live_variables_state
*state
)
122 BITSET_WORD live
[state
->bitset_words
];
123 memcpy(live
, succ
->live_in
, sizeof live
);
125 nir_foreach_instr(succ
, instr
) {
126 if (instr
->type
!= nir_instr_type_phi
)
128 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
130 assert(phi
->dest
.is_ssa
);
131 set_ssa_def_dead(&phi
->dest
.ssa
, live
);
134 nir_foreach_instr(succ
, instr
) {
135 if (instr
->type
!= nir_instr_type_phi
)
137 nir_phi_instr
*phi
= nir_instr_as_phi(instr
);
139 foreach_list_typed(nir_phi_src
, src
, node
, &phi
->srcs
) {
140 if (src
->pred
== pred
) {
141 set_src_live(&src
->src
, live
);
147 for (unsigned i
= 0; i
< state
->bitset_words
; ++i
) {
148 state
->progress
= state
->progress
|| (live
[i
] & ~pred
->live_out
[i
]) != 0;
149 pred
->live_out
[i
] |= live
[i
];
154 walk_instructions_block(nir_block
*block
, void *void_state
)
156 struct live_variables_state
*state
= void_state
;
158 /* The live out is the union (modulo phi nodes) of the live ins of its
160 if (block
->successors
[0])
161 propagate_across_edge(block
, block
->successors
[0], state
);
162 if (block
->successors
[1])
163 propagate_across_edge(block
, block
->successors
[1], state
);
165 memcpy(block
->live_in
, block
->live_out
,
166 state
->bitset_words
* sizeof(BITSET_WORD
));
168 nir_if
*following_if
= nir_block_get_following_if(block
);
170 set_src_live(&following_if
->condition
, block
->live_in
);
172 nir_foreach_instr_reverse(block
, instr
) {
173 /* Phi nodes are handled seperately so we want to skip them. Since
174 * we are going backwards and they are at the beginning, we can just
175 * break as soon as we see one.
177 if (instr
->type
== nir_instr_type_phi
)
180 nir_foreach_ssa_def(instr
, set_ssa_def_dead
, block
->live_in
);
181 nir_foreach_src(instr
, set_src_live
, block
->live_in
);
188 src_does_not_use_def(nir_src
*src
, void *def
)
190 return !src
->is_ssa
|| src
->ssa
!= (nir_ssa_def
*)def
;
194 search_for_use_after_instr(nir_instr
*start
, nir_ssa_def
*def
)
196 /* Only look for a use strictly after the given instruction */
197 struct exec_node
*node
= start
->node
.next
;
198 while (!exec_node_is_tail_sentinel(node
)) {
199 nir_instr
*instr
= exec_node_data(nir_instr
, node
, node
);
200 if (!nir_foreach_src(instr
, src_does_not_use_def
, def
))
207 /* Returns true if def is live at instr assuming that def comes before
208 * instr in a pre DFS search of the dominance tree.
211 nir_ssa_def_is_live_at(nir_ssa_def
*def
, nir_instr
*instr
)
213 if (BITSET_TEST(instr
->block
->live_out
, def
->live_index
)) {
214 /* Since def dominates instr, if def is in the liveout of the block,
219 if (BITSET_TEST(instr
->block
->live_in
, def
->live_index
) ||
220 def
->parent_instr
->block
== instr
->block
) {
221 /* In this case it is either live coming into instr's block or it
222 * is defined in the same block. In this case, we simply need to
223 * see if it is used after instr.
225 return search_for_use_after_instr(instr
, def
);
233 nir_ssa_defs_interfere(nir_ssa_def
*a
, nir_ssa_def
*b
)
235 if (a
->parent_instr
== b
->parent_instr
) {
236 /* Two variables defined at the same time interfere assuming at
237 * least one isn't dead.
240 } else if (a
->live_index
== 0 || b
->live_index
== 0) {
241 /* If either variable is an ssa_undef, then there's no interference */
243 } else if (a
->live_index
< b
->live_index
) {
244 return nir_ssa_def_is_live_at(a
, b
->parent_instr
);
246 return nir_ssa_def_is_live_at(b
, a
->parent_instr
);
251 nir_live_variables_impl(nir_function_impl
*impl
)
253 struct live_variables_state state
;
255 /* We start at 1 because we reserve the index value of 0 for ssa_undef
256 * instructions. Those are never live, so their liveness information
257 * can be compacted into a single bit.
259 state
.num_ssa_defs
= 1;
260 nir_foreach_block(impl
, index_ssa_definitions_block
, &state
);
262 /* We now know how many unique ssa definitions we have and we can go
263 * ahead and allocate live_in and live_out sets
265 state
.bitset_words
= BITSET_WORDS(state
.num_ssa_defs
);
266 nir_foreach_block(impl
, init_liveness_block
, &state
);
268 /* We need to propagate the liveness back through the CFG. Thanks to
269 * the wonders of SSA, this will run no more times than the depth of the
273 state
.progress
= false;
274 nir_foreach_block_reverse(impl
, walk_instructions_block
, &state
);
275 } while (state
.progress
);