1 /*
2 * Copyright (c) 2019 Lima Project
3 *
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:
10 *
11 * The above copyright notice and this permission notice (including the
12 * next paragraph) shall be included in all copies or substantial portions
13 * of the Software.
14 *
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.
22 *
23 */
24
25 #include "ppir.h"
26
27 /* Propagates liveness from a liveness set to another by performing the
28 * union between sets. */
29 static void
ppir_liveness_propagate(ppir_compiler * comp,struct ppir_liveness * dest,struct ppir_liveness * src,struct set * dest_set,struct set * src_set)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)
33 {
34 set_foreach(src_set, entry_src) {
35 const struct ppir_liveness *s = entry_src->key;
36 assert(s);
37
38 unsigned int regalloc_index = s->reg->regalloc_index;
39
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]);
43 }
44 }
45
46 /* Clone a liveness set (without propagation) */
47 static void
ppir_liveness_set_clone(ppir_compiler * comp,struct ppir_liveness * dest,struct ppir_liveness * src,struct set * dest_set,struct set * src_set)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)
51 {
52 _mesa_set_clear(dest_set, NULL);
53 memset(dest, 0, list_length(&comp->reg_list) * sizeof(struct ppir_liveness));
54 memcpy(dest, src,
55 list_length(&comp->reg_list) * sizeof(struct ppir_liveness));
56
57 set_foreach(src_set, entry_src) {
58 const struct ppir_liveness *s = entry_src->key;
59 assert(s);
60
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]);
65 }
66 }
67
68 /* Check whether two liveness sets are equal. */
69 static bool
ppir_liveness_set_equal(ppir_compiler * comp,struct ppir_liveness * l1,struct ppir_liveness * l2,struct set * set1,struct set * set2)70 ppir_liveness_set_equal(ppir_compiler *comp,
71 struct ppir_liveness *l1, struct ppir_liveness *l2,
72 struct set *set1, struct set *set2)
73 {
74 set_foreach(set1, entry1) {
75 const struct ppir_liveness *k1 = entry1->key;
76 unsigned int regalloc_index = k1->reg->regalloc_index;
77
78 struct set_entry *entry2 = _mesa_set_search(set2, &l2[regalloc_index]);
79 if (!entry2)
80 return false;
81
82 const struct ppir_liveness *k2 = entry2->key;
83
84 if (k1->mask != k2->mask)
85 return false;
86 }
87 set_foreach(set2, entry2) {
88 const struct ppir_liveness *k2 = entry2->key;
89 unsigned int regalloc_index = k2->reg->regalloc_index;
90
91 struct set_entry *entry1 = _mesa_set_search(set1, &l1[regalloc_index]);
92 if (!entry1)
93 return false;
94
95 const struct ppir_liveness *k1 = entry1->key;
96
97 if (k2->mask != k1->mask)
98 return false;
99 }
100 return true;
101 }
102
103 /* Update the liveness information of the instruction by adding its srcs
104 * as live registers to the live_in set. */
105 static void
ppir_liveness_instr_srcs(ppir_compiler * comp,ppir_instr * instr)106 ppir_liveness_instr_srcs(ppir_compiler *comp, ppir_instr *instr)
107 {
108 for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
109 ppir_node *node = instr->slots[i];
110 if (!node)
111 continue;
112
113 switch(node->op) {
114 case ppir_op_const:
115 case ppir_op_undef:
116 continue;
117 default:
118 break;
119 }
120
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)
124 continue;
125
126 ppir_reg *reg = ppir_src_get_reg(src);
127 if (!reg || reg->undef)
128 continue;
129
130 /* if some other op on this same instruction is writing,
131 * we just need to reserve a register for this particular
132 * instruction. */
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]);
136 continue;
137 }
138
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 */
143 if (live)
144 continue;
145
146 instr->live_in[reg->regalloc_index].reg = reg;
147 _mesa_set_add(instr->live_in_set, &instr->live_in[reg->regalloc_index]);
148 }
149 else {
150 unsigned int mask = ppir_src_get_mask(src);
151
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)))
156 continue;
157
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]);
162 }
163 }
164 }
165 }
166
167
168 /* Update the liveness information of the instruction by removing its
169 * dests from the live_in set. */
170 static void
ppir_liveness_instr_dest(ppir_compiler * comp,ppir_instr * instr)171 ppir_liveness_instr_dest(ppir_compiler *comp, ppir_instr *instr)
172 {
173 for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
174 ppir_node *node = instr->slots[i];
175 if (!node)
176 continue;
177
178 switch(node->op) {
179 case ppir_op_const:
180 case ppir_op_undef:
181 continue;
182 default:
183 break;
184 }
185
186 ppir_dest *dest = ppir_node_get_dest(node);
187 if (!dest || dest->type == ppir_target_pipeline)
188 continue;
189 ppir_reg *reg = ppir_dest_get_reg(dest);
190 if (!reg || reg->undef)
191 continue;
192
193 struct set_entry *live = _mesa_set_search(instr->live_in_set,
194 &instr->live_in[reg->regalloc_index]);
195
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. */
199 if (!live) {
200 instr->live_internal[reg->regalloc_index].reg = reg;
201 _mesa_set_add(instr->live_internal_set, &instr->live_internal[reg->regalloc_index]);
202 continue;
203 }
204
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]);
208 }
209 else {
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))
215 continue;
216
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]);
221 }
222 }
223 }
224 }
225
226 /* Main loop, iterate blocks/instructions/ops backwards, propagate
227 * livenss and update liveness of each instruction. */
228 static bool
ppir_liveness_compute_live_sets(ppir_compiler * comp)229 ppir_liveness_compute_live_sets(ppir_compiler *comp)
230 {
231 bool cont = false;
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);
235
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];
239 if (!succ)
240 continue;
241
242 ppir_liveness_propagate(comp, block->live_out, succ->live_in,
243 block->live_out_set, succ->live_in_set);
244 }
245
246 list_for_each_entry_rev(ppir_instr, instr, &block->instr_list, list) {
247 /* inherit (or-) live variables from next instr or block */
248 if (instr == last) {
249 ppir_liveness_set_clone(comp,
250 instr->live_out, block->live_out,
251 instr->live_out_set, block->live_out_set);
252 }
253 else {
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);
258 }
259 /* initial copy to check for changes */
260 struct set *temp_live_in_set = _mesa_set_create(comp,
261 _mesa_hash_pointer,
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);
267
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);
271
272 ppir_liveness_instr_dest(comp, instr);
273 ppir_liveness_instr_srcs(comp, instr);
274
275 cont |= !ppir_liveness_set_equal(comp, temp_live_in, instr->live_in,
276 temp_live_in_set, instr->live_in_set);
277 }
278
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);
284 else
285 ppir_liveness_set_clone(comp, block->live_in, block->live_out,
286 block->live_in_set, block->live_out_set);
287 }
288
289 return cont;
290 }
291
292 /*
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.
299 *
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
304 * block itself).
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
326 * current run.
327 */
328 void
ppir_liveness_analysis(ppir_compiler * comp)329 ppir_liveness_analysis(ppir_compiler *comp)
330 {
331 while (ppir_liveness_compute_live_sets(comp))
332 ;
333 }
334