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,BITSET_WORD * dest_set,BITSET_WORD * src_set,uint8_t * dest_mask,uint8_t * src_mask)30 ppir_liveness_propagate(ppir_compiler *comp,
31 BITSET_WORD *dest_set, BITSET_WORD *src_set,
32 uint8_t *dest_mask, uint8_t *src_mask)
33 {
34 for (int i = 0; i < BITSET_WORDS(comp->reg_num); i++)
35 dest_set[i] |= src_set[i];
36
37 for (int i = 0; i < reg_mask_size(comp->reg_num); i++)
38 dest_mask[i] |= src_mask[i];
39 }
40
41 /* Check whether two liveness sets are equal. */
42 static bool
ppir_liveness_set_equal(ppir_compiler * comp,BITSET_WORD * set1,BITSET_WORD * set2,uint8_t * mask1,uint8_t * mask2)43 ppir_liveness_set_equal(ppir_compiler *comp,
44 BITSET_WORD *set1, BITSET_WORD *set2,
45 uint8_t *mask1, uint8_t *mask2)
46 {
47 for (int i = 0; i < BITSET_WORDS(comp->reg_num); i++)
48 if (set1[i] != set2[i])
49 return false;
50
51 for (int i = 0; i < reg_mask_size(comp->reg_num); i++)
52 if (mask1[i] != mask2[i])
53 return false;
54
55 return true;
56 }
57
58 /* Update the liveness information of the instruction by adding its srcs
59 * as live registers to the live_in set. */
60 static void
ppir_liveness_instr_srcs(ppir_compiler * comp,ppir_instr * instr)61 ppir_liveness_instr_srcs(ppir_compiler *comp, ppir_instr *instr)
62 {
63 for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
64 ppir_node *node = instr->slots[i];
65 if (!node)
66 continue;
67
68 switch(node->op) {
69 case ppir_op_const:
70 case ppir_op_undef:
71 continue;
72 default:
73 break;
74 }
75
76 for (int i = 0; i < ppir_node_get_src_num(node); i++) {
77 ppir_src *src = ppir_node_get_src(node, i);
78 if (!src || src->type == ppir_target_pipeline)
79 continue;
80
81 ppir_reg *reg = ppir_src_get_reg(src);
82 if (!reg || reg->undef)
83 continue;
84
85 unsigned int index = reg->regalloc_index;
86
87 /* if some other op on this same instruction is writing,
88 * we just need to reserve a register for this particular
89 * instruction. */
90 if (src->node && src->node->instr == instr) {
91 BITSET_SET(instr->live_internal, index);
92 continue;
93 }
94
95 bool live = BITSET_TEST(instr->live_set, index);
96 if (src->type == ppir_target_ssa) {
97 /* reg is read, needs to be live before instr */
98 if (live)
99 continue;
100
101 BITSET_SET(instr->live_set, index);
102 }
103 else {
104 unsigned int mask = ppir_src_get_mask(src);
105 uint8_t live_mask = get_reg_mask(instr->live_mask, index);
106
107 /* read reg is type register, need to check if this sets
108 * any additional bits in the current mask */
109 if (live && (live_mask == (live_mask | mask)))
110 continue;
111
112 /* some new components */
113 set_reg_mask(instr->live_mask, index, (live_mask | mask));
114 BITSET_SET(instr->live_set, index);
115 }
116 }
117 }
118 }
119
120
121 /* Update the liveness information of the instruction by removing its
122 * dests from the live_in set. */
123 static void
ppir_liveness_instr_dest(ppir_compiler * comp,ppir_instr * instr,ppir_instr * last)124 ppir_liveness_instr_dest(ppir_compiler *comp, ppir_instr *instr, ppir_instr *last)
125 {
126 for (int i = PPIR_INSTR_SLOT_NUM-1; i >= 0; i--) {
127 ppir_node *node = instr->slots[i];
128 if (!node)
129 continue;
130
131 switch(node->op) {
132 case ppir_op_const:
133 case ppir_op_undef:
134 continue;
135 default:
136 break;
137 }
138
139 ppir_dest *dest = ppir_node_get_dest(node);
140 if (!dest || dest->type == ppir_target_pipeline)
141 continue;
142 ppir_reg *reg = ppir_dest_get_reg(dest);
143 if (!reg || reg->undef)
144 continue;
145
146 unsigned int index = reg->regalloc_index;
147 bool live = BITSET_TEST(instr->live_set, index);
148
149 /* If it's an out reg, it's alive till the end of the block, so add it
150 * to live_set of the last instruction */
151 if (!live && reg->out_reg && (instr != last)) {
152 BITSET_SET(last->live_set, index);
153 BITSET_CLEAR(instr->live_set, index);
154 continue;
155 }
156
157 /* If a register is written but wasn't read in a later instruction, it is
158 * either an output register in last instruction, dead code or a bug.
159 * For now, assign an interference to it to ensure it doesn't get assigned
160 * a live register and overwrites it. */
161 if (!live) {
162 BITSET_SET(instr->live_internal, index);
163 continue;
164 }
165
166 if (dest->type == ppir_target_ssa) {
167 /* reg is written and ssa, is not live before instr */
168 BITSET_CLEAR(instr->live_set, index);
169 }
170 else {
171 unsigned int mask = dest->write_mask;
172 uint8_t live_mask = get_reg_mask(instr->live_mask, index);
173 /* written reg is type register, need to check if this clears
174 * the remaining mask to remove it from the live set */
175 if (live_mask == (live_mask & ~mask))
176 continue;
177
178 set_reg_mask(instr->live_mask, index, (live_mask & ~mask));
179 /* unset reg if all remaining bits were cleared */
180 if ((live_mask & ~mask) == 0) {
181 BITSET_CLEAR(instr->live_set, index);
182 }
183 }
184 }
185 }
186
187 /* Main loop, iterate blocks/instructions/ops backwards, propagate
188 * livenss and update liveness of each instruction. */
189 static bool
ppir_liveness_compute_live_sets(ppir_compiler * comp)190 ppir_liveness_compute_live_sets(ppir_compiler *comp)
191 {
192 uint8_t temp_live_mask[reg_mask_size(comp->reg_num)];
193 BITSET_DECLARE(temp_live_set, comp->reg_num);
194 bool cont = false;
195 list_for_each_entry_rev(ppir_block, block, &comp->block_list, list) {
196 if (list_is_empty(&block->instr_list))
197 continue;
198
199 ppir_instr *last = list_last_entry(&block->instr_list, ppir_instr, list);
200 assert(last);
201
202 list_for_each_entry_rev(ppir_instr, instr, &block->instr_list, list) {
203 /* initial copy to check for changes */
204 memset(temp_live_mask, 0, sizeof(temp_live_mask));
205 memset(temp_live_set, 0, sizeof(temp_live_set));
206
207 ppir_liveness_propagate(comp,
208 temp_live_set, instr->live_set,
209 temp_live_mask, instr->live_mask);
210
211 /* inherit (or-) live variables from next instr or block */
212 if (instr == last) {
213 ppir_instr *next_instr;
214 /* inherit liveness from the first instruction in the next blocks */
215 for (int i = 0; i < 2; i++) {
216 ppir_block *succ = block->successors[i];
217 if (!succ)
218 continue;
219
220 /* if the block is empty, go for the next-next until a non-empty
221 * one is found */
222 while (list_is_empty(&succ->instr_list)) {
223 assert(succ->successors[0] && !succ->successors[1]);
224 succ = succ->successors[0];
225 }
226
227 next_instr = list_first_entry(&succ->instr_list, ppir_instr, list);
228 assert(next_instr);
229
230 ppir_liveness_propagate(comp,
231 instr->live_set, next_instr->live_set,
232 instr->live_mask, next_instr->live_mask);
233 }
234 }
235 else {
236 ppir_instr *next_instr = list_entry(instr->list.next, ppir_instr, list);
237 ppir_liveness_propagate(comp,
238 instr->live_set, next_instr->live_set,
239 instr->live_mask, next_instr->live_mask);
240 }
241
242 ppir_liveness_instr_dest(comp, instr, last);
243 ppir_liveness_instr_srcs(comp, instr);
244
245 cont |= !ppir_liveness_set_equal(comp,
246 temp_live_set, instr->live_set,
247 temp_live_mask, instr->live_mask);
248 }
249 }
250
251 return cont;
252 }
253
254 /*
255 * Liveness analysis is based on https://en.wikipedia.org/wiki/Live_variable_analysis
256 * This implementation calculates liveness for each instruction.
257 * The liveness set in this implementation is defined as the set of
258 * registers live before the instruction executes.
259 * Blocks/instructions/ops are iterated backwards so register reads are
260 * propagated up to the instruction that writes it.
261 *
262 * 1) Before computing liveness for an instruction, propagate liveness
263 * from the next instruction. If it is the last instruction in a
264 * block, propagate liveness from all possible next instructions in
265 * the successor blocks.
266 * 2) Calculate the live set for the instruction. The initial live set
267 * is a propagated set of the live set from the next instructions.
268 * - Registers which aren't touched by this instruction are kept
269 * intact.
270 * - If a register is written by this instruction, it no longer needs
271 * to be live before the instruction, so it is removed from the live
272 * set of that instruction.
273 * - If a register is read by this instruction, it needs to be live
274 * before its execution, so add it to its live set.
275 * - Non-ssa registers are a special case. For this, the algorithm
276 * keeps and updates the mask of live components following the same
277 * logic as above. The register is only removed from the live set of
278 * the instruction when no live components are left.
279 * - If a non-ssa register is written and read in the same
280 * instruction, it stays in the live set.
281 * - Another special case is when a register is only written and read
282 * within a single instruciton. In this case a register needs to be
283 * reserved but not propagated. The algorithm adds it to the
284 * live_internal set so that the register allocator properly assigns
285 * an interference for it.
286 * 3) The algorithm must run over the entire program until it converges,
287 * i.e. a full run happens without changes. This is because blocks
288 * are updated sequentially and updates in a block may need to be
289 * propagated to parent blocks that were already calculated in the
290 * current run.
291 */
292 void
ppir_liveness_analysis(ppir_compiler * comp)293 ppir_liveness_analysis(ppir_compiler *comp)
294 {
295 while (ppir_liveness_compute_live_sets(comp))
296 ;
297 }
298