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
133 if (src
->node
&& src
->node
->instr
== instr
) {
134 instr
->live_internal
[reg
->regalloc_index
].reg
= reg
;
135 _mesa_set_add(instr
->live_internal_set
, &instr
->live_internal
[reg
->regalloc_index
]);
139 struct set_entry
*live
= _mesa_set_search(instr
->live_in_set
,
140 &instr
->live_in
[reg
->regalloc_index
]);
141 if (src
->type
== ppir_target_ssa
) {
142 /* reg is read, needs to be live before instr */
146 instr
->live_in
[reg
->regalloc_index
].reg
= reg
;
147 _mesa_set_add(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
150 unsigned int mask
= ppir_src_get_mask(src
);
152 /* read reg is type register, need to check if this sets
153 * any additional bits in the current mask */
154 if (live
&& (instr
->live_in
[reg
->regalloc_index
].mask
==
155 (instr
->live_in
[reg
->regalloc_index
].mask
| mask
)))
158 /* some new components */
159 instr
->live_in
[reg
->regalloc_index
].reg
= reg
;
160 instr
->live_in
[reg
->regalloc_index
].mask
|= mask
;
161 _mesa_set_add(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
168 /* Update the liveness information of the instruction by removing its
169 * dests from the live_in set. */
171 ppir_liveness_instr_dest(ppir_compiler
*comp
, ppir_instr
*instr
)
173 for (int i
= PPIR_INSTR_SLOT_NUM
-1; i
>= 0; i
--) {
174 ppir_node
*node
= instr
->slots
[i
];
181 case ppir_op_store_color
: /* never clear dest if its store output */
187 ppir_dest
*dest
= ppir_node_get_dest(node
);
188 if (!dest
|| dest
->type
== ppir_target_pipeline
)
190 ppir_reg
*reg
= ppir_dest_get_reg(dest
);
191 if (!reg
|| reg
->undef
)
194 struct set_entry
*live
= _mesa_set_search(instr
->live_in_set
,
195 &instr
->live_in
[reg
->regalloc_index
]);
197 /* If a register is written but wasn't read in a later instruction, it is
198 * either dead code or a bug. For now, assign an interference to it to
199 * ensure it doesn't get assigned a live register and overwrites it. */
201 instr
->live_internal
[reg
->regalloc_index
].reg
= reg
;
202 _mesa_set_add(instr
->live_internal_set
, &instr
->live_internal
[reg
->regalloc_index
]);
206 if (dest
->type
== ppir_target_ssa
) {
207 /* reg is written and ssa, is not live before instr */
208 _mesa_set_remove_key(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
211 unsigned int mask
= dest
->write_mask
;
212 /* written reg is type register, need to check if this clears
213 * the remaining mask to remove it from the live set */
214 if (instr
->live_in
[reg
->regalloc_index
].mask
==
215 (instr
->live_in
[reg
->regalloc_index
].mask
& ~mask
))
218 instr
->live_in
[reg
->regalloc_index
].mask
&= ~mask
;
219 /* unset reg if all remaining bits were cleared */
220 if (!instr
->live_in
[reg
->regalloc_index
].mask
) {
221 _mesa_set_remove_key(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
227 /* Main loop, iterate blocks/instructions/ops backwards, propagate
228 * livenss and update liveness of each instruction. */
230 ppir_liveness_compute_live_sets(ppir_compiler
*comp
)
233 list_for_each_entry_rev(ppir_block
, block
, &comp
->block_list
, list
) {
234 ppir_instr
*first
= list_first_entry(&block
->instr_list
, ppir_instr
, list
);
235 ppir_instr
*last
= list_last_entry(&block
->instr_list
, ppir_instr
, list
);
237 /* inherit live_out from the other blocks live_in */
238 for (int i
= 0; i
< 2; i
++) {
239 ppir_block
*succ
= block
->successors
[i
];
243 ppir_liveness_propagate(comp
, block
->live_out
, succ
->live_in
,
244 block
->live_out_set
, succ
->live_in_set
);
247 list_for_each_entry_rev(ppir_instr
, instr
, &block
->instr_list
, list
) {
248 /* inherit (or-) live variables from next instr or block */
250 ppir_liveness_set_clone(comp
,
251 instr
->live_out
, block
->live_out
,
252 instr
->live_out_set
, block
->live_out_set
);
255 ppir_instr
*next_instr
= LIST_ENTRY(ppir_instr
, instr
->list
.next
, list
);
256 ppir_liveness_set_clone(comp
,
257 instr
->live_out
, next_instr
->live_in
,
258 instr
->live_out_set
, next_instr
->live_in_set
);
260 /* initial copy to check for changes */
261 struct set
*temp_live_in_set
= _mesa_set_create(comp
,
263 _mesa_key_pointer_equal
);
264 struct ppir_liveness temp_live_in
[list_length(&comp
->reg_list
)];
265 ppir_liveness_set_clone(comp
,
266 temp_live_in
, instr
->live_in
,
267 temp_live_in_set
, instr
->live_in_set
);
269 /* initialize live_in for potential changes */
270 ppir_liveness_propagate(comp
, instr
->live_in
, instr
->live_out
,
271 instr
->live_in_set
, instr
->live_out_set
);
273 ppir_liveness_instr_dest(comp
, instr
);
274 ppir_liveness_instr_srcs(comp
, instr
);
276 cont
|= !ppir_liveness_set_equal(comp
, temp_live_in
, instr
->live_in
,
277 temp_live_in_set
, instr
->live_in_set
);
280 /* inherit live_in from the first instruction in the block,
281 * or live_out if it is empty */
282 if (!list_is_empty(&block
->instr_list
) && first
&& first
->scheduled
)
283 ppir_liveness_set_clone(comp
, block
->live_in
, first
->live_in
,
284 block
->live_in_set
, first
->live_in_set
);
286 ppir_liveness_set_clone(comp
, block
->live_in
, block
->live_out
,
287 block
->live_in_set
, block
->live_out_set
);
294 * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
295 * This implementation calculates liveness before/after each
296 * instruction. Aggregated block liveness information is stored
297 * before/after blocks for conveniency (handle e.g. empty blocks).
298 * Blocks/instructions/ops are iterated backwards so register reads are
299 * propagated up to the instruction that writes it.
301 * 1) Before computing liveness for each instruction, propagate live_out
302 * from the next instruction. If it is the last instruction in a
303 * block, propagate liveness from all possible next instructions
304 * (in this case, this information comes from the live_out of the
306 * 2) Calculate live_in for the each instruction. The initial live_in is
307 * a copy of its live_out so registers who aren't touched by this
308 * instruction are kept intact.
309 * - If a register is written by this instruction, it no longer needs
310 * to be live before the instruction, so it is removed from live_in.
311 * - If a register is read by this instruction, it needs to be live
312 * before its execution, so add it to live_in.
313 * - Non-ssa registers are a special case. For this, the algorithm
314 * keeps and updates the mask of live components following the same
315 * logic as above. The register is only removed from the live set
316 * when no live components are left.
317 * - If a non-ssa register is written and read in the same
318 * instruction, it stays in live_in.
319 * - Another special case is a ssa register that is written by an
320 * early op in the instruction, and read by a later op. In this case,
321 * the algorithm adds it to the live_out set so that the register
322 * allocator properly assigns an interference for it.
323 * 3) The algorithm must run over the entire program until it converges,
324 * i.e. a full run happens without changes. This is because blocks
325 * are updated sequentially and updates in a block may need to be
326 * propagated to parent blocks that were already calculated in the
330 ppir_liveness_analysis(ppir_compiler
*comp
)
332 while (ppir_liveness_compute_live_sets(comp
))