2 * Copyright (c) 2019 Lima Project
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, sub license,
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
12 * next paragraph) shall be included in all copies or substantial portions
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 NON-INFRINGEMENT. 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
21 * DEALINGS IN THE SOFTWARE.
27 /* Propagates liveness from a liveness set to another by performing the
28 * union between sets. */
30 ppir_liveness_propagate(ppir_compiler
*comp
,
31 struct ppir_liveness
*dest
, struct ppir_liveness
*src
,
32 struct set
*dest_set
, struct set
*src_set
)
34 set_foreach(src_set
, entry_src
) {
35 const struct ppir_liveness
*s
= entry_src
->key
;
38 unsigned int regalloc_index
= s
->reg
->regalloc_index
;
40 dest
[regalloc_index
].reg
= src
[regalloc_index
].reg
;
41 dest
[regalloc_index
].mask
|= src
[regalloc_index
].mask
;
42 _mesa_set_add(dest_set
, &dest
[regalloc_index
]);
46 /* Clone a liveness set (without propagation) */
48 ppir_liveness_set_clone(ppir_compiler
*comp
,
49 struct ppir_liveness
*dest
, struct ppir_liveness
*src
,
50 struct set
*dest_set
, struct set
*src_set
)
52 _mesa_set_clear(dest_set
, NULL
);
53 memset(dest
, 0, list_length(&comp
->reg_list
) * sizeof(struct ppir_liveness
));
55 list_length(&comp
->reg_list
) * sizeof(struct ppir_liveness
));
57 set_foreach(src_set
, entry_src
) {
58 const struct ppir_liveness
*s
= entry_src
->key
;
61 unsigned int regalloc_index
= s
->reg
->regalloc_index
;
62 dest
[regalloc_index
].reg
= src
[regalloc_index
].reg
;
63 dest
[regalloc_index
].mask
= src
[regalloc_index
].mask
;
64 _mesa_set_add(dest_set
, &dest
[regalloc_index
]);
68 /* Check whether two liveness sets are equal. */
70 ppir_liveness_set_equal(ppir_compiler
*comp
,
71 struct ppir_liveness
*l1
, struct ppir_liveness
*l2
,
72 struct set
*set1
, struct set
*set2
)
74 set_foreach(set1
, entry1
) {
75 const struct ppir_liveness
*k1
= entry1
->key
;
76 unsigned int regalloc_index
= k1
->reg
->regalloc_index
;
78 struct set_entry
*entry2
= _mesa_set_search(set2
, &l2
[regalloc_index
]);
82 const struct ppir_liveness
*k2
= entry2
->key
;
84 if (k1
->mask
!= k2
->mask
)
87 set_foreach(set2
, entry2
) {
88 const struct ppir_liveness
*k2
= entry2
->key
;
89 unsigned int regalloc_index
= k2
->reg
->regalloc_index
;
91 struct set_entry
*entry1
= _mesa_set_search(set1
, &l1
[regalloc_index
]);
95 const struct ppir_liveness
*k1
= entry1
->key
;
97 if (k2
->mask
!= k1
->mask
)
103 /* Update the liveness information of the instruction by adding its srcs
104 * as live registers to the live_in set. */
106 ppir_liveness_instr_srcs(ppir_compiler
*comp
, ppir_instr
*instr
)
108 for (int i
= PPIR_INSTR_SLOT_NUM
-1; i
>= 0; i
--) {
109 ppir_node
*node
= instr
->slots
[i
];
121 for (int i
= 0; i
< ppir_node_get_src_num(node
); i
++) {
122 ppir_src
*src
= ppir_node_get_src(node
, i
);
123 if (!src
|| src
->type
== ppir_target_pipeline
)
126 ppir_reg
*reg
= ppir_src_get_reg(src
);
127 if (!reg
|| reg
->undef
)
130 /* if some other op on this same instruction is writing,
131 * we just need to reserve a register for this particular
132 * instruction. Add the register to live_out to make that
133 * interference happen without propagating its liveness. */
134 if (src
->node
&& src
->node
->instr
== instr
) {
135 instr
->live_out
[reg
->regalloc_index
].reg
= reg
;
136 _mesa_set_add(instr
->live_out_set
, &instr
->live_out
[reg
->regalloc_index
]);
140 struct set_entry
*live
= _mesa_set_search(instr
->live_in_set
,
141 &instr
->live_in
[reg
->regalloc_index
]);
142 if (src
->type
== ppir_target_ssa
) {
143 /* reg is read, needs to be live before instr */
147 instr
->live_in
[reg
->regalloc_index
].reg
= reg
;
148 _mesa_set_add(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
151 unsigned int mask
= ppir_src_get_mask(node
);
153 /* read reg is type register, need to check if this sets
154 * any additional bits in the current mask */
155 if (live
&& (instr
->live_in
[reg
->regalloc_index
].mask
==
156 (instr
->live_in
[reg
->regalloc_index
].mask
| mask
)))
159 /* some new components */
160 instr
->live_in
[reg
->regalloc_index
].reg
= reg
;
161 instr
->live_in
[reg
->regalloc_index
].mask
|= mask
;
162 _mesa_set_add(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
169 /* Update the liveness information of the instruction by removing its
170 * dests from the live_in set. */
172 ppir_liveness_instr_dest(ppir_compiler
*comp
, ppir_instr
*instr
)
174 for (int i
= PPIR_INSTR_SLOT_NUM
-1; i
>= 0; i
--) {
175 ppir_node
*node
= instr
->slots
[i
];
182 case ppir_op_store_color
: /* never clear dest if its store output */
188 ppir_dest
*dest
= ppir_node_get_dest(node
);
189 if (!dest
|| dest
->type
== ppir_target_pipeline
)
191 ppir_reg
*reg
= ppir_dest_get_reg(dest
);
192 if (!reg
|| reg
->undef
)
195 struct set_entry
*live
= _mesa_set_search(instr
->live_in_set
,
196 &instr
->live_in
[reg
->regalloc_index
]);
197 if (dest
->type
== ppir_target_ssa
) {
200 /* reg is written and ssa, is not live before instr */
201 _mesa_set_remove_key(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
204 unsigned int mask
= ppir_src_get_mask(node
);
205 /* written reg is type register, need to check if this clears
206 * the remaining mask to remove it from the live set */
208 instr
->live_in
[reg
->regalloc_index
].mask
==
209 (instr
->live_in
[reg
->regalloc_index
].mask
& ~mask
))
212 instr
->live_in
[reg
->regalloc_index
].mask
&= ~mask
;
213 /* unset reg if all remaining bits were cleared */
214 if (!instr
->live_in
[reg
->regalloc_index
].mask
) {
215 _mesa_set_remove_key(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
221 /* Main loop, iterate blocks/instructions/ops backwards, propagate
222 * livenss and update liveness of each instruction. */
224 ppir_liveness_compute_live_sets(ppir_compiler
*comp
)
227 list_for_each_entry_rev(ppir_block
, block
, &comp
->block_list
, list
) {
228 ppir_instr
*first
= list_first_entry(&block
->instr_list
, ppir_instr
, list
);
229 ppir_instr
*last
= list_last_entry(&block
->instr_list
, ppir_instr
, list
);
231 /* inherit live_out from the other blocks live_in */
232 for (int i
= 0; i
< 2; i
++) {
233 ppir_block
*succ
= block
->successors
[i
];
237 ppir_liveness_propagate(comp
, block
->live_out
, succ
->live_in
,
238 block
->live_out_set
, succ
->live_in_set
);
241 list_for_each_entry_rev(ppir_instr
, instr
, &block
->instr_list
, list
) {
242 /* inherit (or-) live variables from next instr or block */
244 ppir_liveness_set_clone(comp
,
245 instr
->live_out
, block
->live_out
,
246 instr
->live_out_set
, block
->live_out_set
);
249 ppir_instr
*next_instr
= LIST_ENTRY(ppir_instr
, instr
->list
.next
, list
);
250 ppir_liveness_set_clone(comp
,
251 instr
->live_out
, next_instr
->live_in
,
252 instr
->live_out_set
, next_instr
->live_in_set
);
254 /* initial copy to check for changes */
255 struct set
*temp_live_in_set
= _mesa_set_create(comp
,
257 _mesa_key_pointer_equal
);
258 struct ppir_liveness temp_live_in
[list_length(&comp
->reg_list
)];
259 ppir_liveness_set_clone(comp
,
260 temp_live_in
, instr
->live_in
,
261 temp_live_in_set
, instr
->live_in_set
);
263 /* initialize live_in for potential changes */
264 ppir_liveness_propagate(comp
, instr
->live_in
, instr
->live_out
,
265 instr
->live_in_set
, instr
->live_out_set
);
267 ppir_liveness_instr_dest(comp
, instr
);
268 ppir_liveness_instr_srcs(comp
, instr
);
270 cont
|= !ppir_liveness_set_equal(comp
, temp_live_in
, instr
->live_in
,
271 temp_live_in_set
, instr
->live_in_set
);
274 /* inherit live_in from the first instruction in the block,
275 * or live_out if it is empty */
276 if (!list_is_empty(&block
->instr_list
) && first
&& first
->scheduled
)
277 ppir_liveness_set_clone(comp
, block
->live_in
, first
->live_in
,
278 block
->live_in_set
, first
->live_in_set
);
280 ppir_liveness_set_clone(comp
, block
->live_in
, block
->live_out
,
281 block
->live_in_set
, block
->live_out_set
);
288 * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
289 * This implementation calculates liveness before/after each
290 * instruction. Aggregated block liveness information is stored
291 * before/after blocks for conveniency (handle e.g. empty blocks).
292 * Blocks/instructions/ops are iterated backwards so register reads are
293 * propagated up to the instruction that writes it.
295 * 1) Before computing liveness for each instruction, propagate live_out
296 * from the next instruction. If it is the last instruction in a
297 * block, propagate liveness from all possible next instructions
298 * (in this case, this information comes from the live_out of the
300 * 2) Calculate live_in for the each instruction. The initial live_in is
301 * a copy of its live_out so registers who aren't touched by this
302 * instruction are kept intact.
303 * - If a register is written by this instruction, it no longer needs
304 * to be live before the instruction, so it is removed from live_in.
305 * - If a register is read by this instruction, it needs to be live
306 * before its execution, so add it to live_in.
307 * - Non-ssa registers are a special case. For this, the algorithm
308 * keeps and updates the mask of live components following the same
309 * logic as above. The register is only removed from the live set
310 * when no live components are left.
311 * - If a non-ssa register is written and read in the same
312 * instruction, it stays in live_in.
313 * - Another special case is a ssa register that is written by an
314 * early op in the instruction, and read by a later op. In this case,
315 * the algorithm adds it to the live_out set so that the register
316 * allocator properly assigns an interference for it.
317 * 3) The algorithm must run over the entire program until it converges,
318 * i.e. a full run happens without changes. This is because blocks
319 * are updated sequentially and updates in a block may need to be
320 * propagated to parent blocks that were already calculated in the
324 ppir_liveness_analysis(ppir_compiler
*comp
)
326 while (ppir_liveness_compute_live_sets(comp
))