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
];
186 ppir_dest
*dest
= ppir_node_get_dest(node
);
187 if (!dest
|| dest
->type
== ppir_target_pipeline
)
189 ppir_reg
*reg
= ppir_dest_get_reg(dest
);
190 if (!reg
|| reg
->undef
)
193 struct set_entry
*live
= _mesa_set_search(instr
->live_in_set
,
194 &instr
->live_in
[reg
->regalloc_index
]);
196 /* If a register is written but wasn't read in a later instruction, it is
197 * either dead code or a bug. For now, assign an interference to it to
198 * ensure it doesn't get assigned a live register and overwrites it. */
200 instr
->live_internal
[reg
->regalloc_index
].reg
= reg
;
201 _mesa_set_add(instr
->live_internal_set
, &instr
->live_internal
[reg
->regalloc_index
]);
205 if (dest
->type
== ppir_target_ssa
) {
206 /* reg is written and ssa, is not live before instr */
207 _mesa_set_remove_key(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
210 unsigned int mask
= dest
->write_mask
;
211 /* written reg is type register, need to check if this clears
212 * the remaining mask to remove it from the live set */
213 if (instr
->live_in
[reg
->regalloc_index
].mask
==
214 (instr
->live_in
[reg
->regalloc_index
].mask
& ~mask
))
217 instr
->live_in
[reg
->regalloc_index
].mask
&= ~mask
;
218 /* unset reg if all remaining bits were cleared */
219 if (!instr
->live_in
[reg
->regalloc_index
].mask
) {
220 _mesa_set_remove_key(instr
->live_in_set
, &instr
->live_in
[reg
->regalloc_index
]);
226 /* Main loop, iterate blocks/instructions/ops backwards, propagate
227 * livenss and update liveness of each instruction. */
229 ppir_liveness_compute_live_sets(ppir_compiler
*comp
)
232 list_for_each_entry_rev(ppir_block
, block
, &comp
->block_list
, list
) {
233 ppir_instr
*first
= list_first_entry(&block
->instr_list
, ppir_instr
, list
);
234 ppir_instr
*last
= list_last_entry(&block
->instr_list
, ppir_instr
, list
);
236 /* inherit live_out from the other blocks live_in */
237 for (int i
= 0; i
< 2; i
++) {
238 ppir_block
*succ
= block
->successors
[i
];
242 ppir_liveness_propagate(comp
, block
->live_out
, succ
->live_in
,
243 block
->live_out_set
, succ
->live_in_set
);
246 list_for_each_entry_rev(ppir_instr
, instr
, &block
->instr_list
, list
) {
247 /* inherit (or-) live variables from next instr or block */
249 ppir_liveness_set_clone(comp
,
250 instr
->live_out
, block
->live_out
,
251 instr
->live_out_set
, block
->live_out_set
);
254 ppir_instr
*next_instr
= LIST_ENTRY(ppir_instr
, instr
->list
.next
, list
);
255 ppir_liveness_set_clone(comp
,
256 instr
->live_out
, next_instr
->live_in
,
257 instr
->live_out_set
, next_instr
->live_in_set
);
259 /* initial copy to check for changes */
260 struct set
*temp_live_in_set
= _mesa_set_create(comp
,
262 _mesa_key_pointer_equal
);
263 struct ppir_liveness temp_live_in
[list_length(&comp
->reg_list
)];
264 ppir_liveness_set_clone(comp
,
265 temp_live_in
, instr
->live_in
,
266 temp_live_in_set
, instr
->live_in_set
);
268 /* initialize live_in for potential changes */
269 ppir_liveness_propagate(comp
, instr
->live_in
, instr
->live_out
,
270 instr
->live_in_set
, instr
->live_out_set
);
272 ppir_liveness_instr_dest(comp
, instr
);
273 ppir_liveness_instr_srcs(comp
, instr
);
275 cont
|= !ppir_liveness_set_equal(comp
, temp_live_in
, instr
->live_in
,
276 temp_live_in_set
, instr
->live_in_set
);
279 /* inherit live_in from the first instruction in the block,
280 * or live_out if it is empty */
281 if (!list_is_empty(&block
->instr_list
) && first
&& first
->scheduled
)
282 ppir_liveness_set_clone(comp
, block
->live_in
, first
->live_in
,
283 block
->live_in_set
, first
->live_in_set
);
285 ppir_liveness_set_clone(comp
, block
->live_in
, block
->live_out
,
286 block
->live_in_set
, block
->live_out_set
);
293 * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
294 * This implementation calculates liveness before/after each
295 * instruction. Aggregated block liveness information is stored
296 * before/after blocks for conveniency (handle e.g. empty blocks).
297 * Blocks/instructions/ops are iterated backwards so register reads are
298 * propagated up to the instruction that writes it.
300 * 1) Before computing liveness for each instruction, propagate live_out
301 * from the next instruction. If it is the last instruction in a
302 * block, propagate liveness from all possible next instructions
303 * (in this case, this information comes from the live_out of the
305 * 2) Calculate live_in for the each instruction. The initial live_in is
306 * a copy of its live_out so registers who aren't touched by this
307 * instruction are kept intact.
308 * - If a register is written by this instruction, it no longer needs
309 * to be live before the instruction, so it is removed from live_in.
310 * - If a register is read by this instruction, it needs to be live
311 * before its execution, so add it to live_in.
312 * - Non-ssa registers are a special case. For this, the algorithm
313 * keeps and updates the mask of live components following the same
314 * logic as above. The register is only removed from the live set
315 * when no live components are left.
316 * - If a non-ssa register is written and read in the same
317 * instruction, it stays in live_in.
318 * - Another special case is a ssa register that is written by an
319 * early op in the instruction, and read by a later op. In this case,
320 * the algorithm adds it to the live_out set so that the register
321 * allocator properly assigns an interference for it.
322 * 3) The algorithm must run over the entire program until it converges,
323 * i.e. a full run happens without changes. This is because blocks
324 * are updated sequentially and updates in a block may need to be
325 * propagated to parent blocks that were already calculated in the
329 ppir_liveness_analysis(ppir_compiler
*comp
)
331 while (ppir_liveness_compute_live_sets(comp
))