1 /*
2 * Register - track pseudo usage, maybe eventually try to do register
3 * allocation.
4 *
5 * Copyright (C) 2004 Linus Torvalds
6 */
7
8 #include <assert.h>
9
10 #include "liveness.h"
11 #include "parse.h"
12 #include "expression.h"
13 #include "linearize.h"
14 #include "flow.h"
15
phi_defines(struct instruction * phi_node,pseudo_t target,void (* defines)(struct basic_block *,pseudo_t))16 static void phi_defines(struct instruction * phi_node, pseudo_t target,
17 void (*defines)(struct basic_block *, pseudo_t))
18 {
19 pseudo_t phi;
20 FOR_EACH_PTR(phi_node->phi_list, phi) {
21 struct instruction *def;
22 if (phi == VOID)
23 continue;
24 def = phi->def;
25 if (!def || !def->bb)
26 continue;
27 defines(def->bb, target);
28 } END_FOR_EACH_PTR(phi);
29 }
30
asm_liveness(struct basic_block * bb,struct instruction * insn,void (* def)(struct basic_block *,pseudo_t),void (* use)(struct basic_block *,pseudo_t))31 static void asm_liveness(struct basic_block *bb, struct instruction *insn,
32 void (*def)(struct basic_block *, pseudo_t),
33 void (*use)(struct basic_block *, pseudo_t))
34 {
35 struct asm_constraint *entry;
36
37 FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
38 use(bb, entry->pseudo);
39 } END_FOR_EACH_PTR(entry);
40
41 FOR_EACH_PTR(insn->asm_rules->outputs, entry) {
42 if (entry->is_memory)
43 use(bb, entry->pseudo);
44 else
45 def(bb, entry->pseudo);
46 } END_FOR_EACH_PTR(entry);
47 }
48
track_instruction_usage(struct basic_block * bb,struct instruction * insn,void (* def)(struct basic_block *,pseudo_t),void (* use)(struct basic_block *,pseudo_t))49 static void track_instruction_usage(struct basic_block *bb, struct instruction *insn,
50 void (*def)(struct basic_block *, pseudo_t),
51 void (*use)(struct basic_block *, pseudo_t))
52 {
53 pseudo_t pseudo;
54
55 #define USES(x) use(bb, insn->x)
56 #define DEFINES(x) def(bb, insn->x)
57
58 switch (insn->opcode) {
59 case OP_RET:
60 case OP_COMPUTEDGOTO:
61 USES(src);
62 break;
63
64 case OP_CBR:
65 case OP_SWITCH:
66 USES(cond);
67 break;
68
69 /* Binary */
70 case OP_BINARY ... OP_BINARY_END:
71 case OP_FPCMP ... OP_FPCMP_END:
72 case OP_BINCMP ... OP_BINCMP_END:
73 USES(src1); USES(src2); DEFINES(target);
74 break;
75
76 /* Uni */
77 case OP_UNOP ... OP_UNOP_END:
78 case OP_SYMADDR:
79 case OP_SLICE:
80 USES(src); DEFINES(target);
81 break;
82
83 case OP_SEL:
84 USES(src1); USES(src2); USES(src3); DEFINES(target);
85 break;
86
87 /* Memory */
88 case OP_LOAD:
89 USES(src); DEFINES(target);
90 break;
91
92 case OP_STORE:
93 USES(src); USES(target);
94 break;
95
96 case OP_LABEL:
97 case OP_SETVAL:
98 case OP_SETFVAL:
99 DEFINES(target);
100 break;
101
102 /* Other */
103 case OP_PHI:
104 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
105 phi_defines(insn, insn->target, def);
106 break;
107
108 case OP_PHISOURCE:
109 /*
110 * We don't care about the phi-source define, they get set
111 * up and expanded by the OP_PHI
112 */
113 USES(phi_src);
114 break;
115
116 case OP_CALL:
117 USES(func);
118 if (insn->target != VOID)
119 DEFINES(target);
120 FOR_EACH_PTR(insn->arguments, pseudo) {
121 use(bb, pseudo);
122 } END_FOR_EACH_PTR(pseudo);
123 break;
124
125 case OP_ASM:
126 asm_liveness(bb, insn, def, use);
127 break;
128
129 case OP_RANGE:
130 USES(src1); USES(src2); USES(src3);
131 break;
132
133 case OP_BADOP:
134 case OP_NOP:
135 case OP_CONTEXT:
136 break;
137 }
138 }
139
140
141 static int liveness_changed;
142
add_pseudo_exclusive(struct pseudo_list ** list,pseudo_t pseudo)143 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
144 {
145 if (!pseudo_in_list(*list, pseudo)) {
146 liveness_changed = 1;
147 add_pseudo(list, pseudo);
148 }
149 }
150
trackable_pseudo(pseudo_t pseudo)151 static inline int trackable_pseudo(pseudo_t pseudo)
152 {
153 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
154 }
155
insn_uses(struct basic_block * bb,pseudo_t pseudo)156 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
157 {
158 if (trackable_pseudo(pseudo)) {
159 struct instruction *def = pseudo->def;
160 if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI)
161 add_pseudo_exclusive(&bb->needs, pseudo);
162 }
163 }
164
insn_defines(struct basic_block * bb,pseudo_t pseudo)165 static void insn_defines(struct basic_block *bb, pseudo_t pseudo)
166 {
167 assert(trackable_pseudo(pseudo));
168 add_pseudo(&bb->defines, pseudo);
169 }
170
track_bb_liveness(struct basic_block * bb)171 static void track_bb_liveness(struct basic_block *bb)
172 {
173 pseudo_t needs;
174
175 FOR_EACH_PTR(bb->needs, needs) {
176 struct basic_block *parent;
177 FOR_EACH_PTR(bb->parents, parent) {
178 if (!pseudo_in_list(parent->defines, needs)) {
179 add_pseudo_exclusive(&parent->needs, needs);
180 }
181 } END_FOR_EACH_PTR(parent);
182 } END_FOR_EACH_PTR(needs);
183 }
184
185 /*
186 * We need to clear the liveness information if we
187 * are going to re-run it.
188 */
clear_liveness(struct entrypoint * ep)189 void clear_liveness(struct entrypoint *ep)
190 {
191 struct basic_block *bb;
192
193 FOR_EACH_PTR(ep->bbs, bb) {
194 free_ptr_list(&bb->needs);
195 free_ptr_list(&bb->defines);
196 } END_FOR_EACH_PTR(bb);
197 }
198
199 /*
200 * Track inter-bb pseudo liveness. The intra-bb case
201 * is purely local information.
202 */
track_pseudo_liveness(struct entrypoint * ep)203 void track_pseudo_liveness(struct entrypoint *ep)
204 {
205 struct basic_block *bb;
206
207 /* Add all the bb pseudo usage */
208 FOR_EACH_PTR(ep->bbs, bb) {
209 struct instruction *insn;
210 FOR_EACH_PTR(bb->insns, insn) {
211 if (!insn->bb)
212 continue;
213 assert(insn->bb == bb);
214 track_instruction_usage(bb, insn, insn_defines, insn_uses);
215 } END_FOR_EACH_PTR(insn);
216 } END_FOR_EACH_PTR(bb);
217
218 /* Calculate liveness.. */
219 do {
220 liveness_changed = 0;
221 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
222 track_bb_liveness(bb);
223 } END_FOR_EACH_PTR_REVERSE(bb);
224 } while (liveness_changed);
225
226 /* Remove the pseudos from the "defines" list that are used internally */
227 FOR_EACH_PTR(ep->bbs, bb) {
228 pseudo_t def;
229 FOR_EACH_PTR(bb->defines, def) {
230 struct basic_block *child;
231 FOR_EACH_PTR(bb->children, child) {
232 if (pseudo_in_list(child->needs, def))
233 goto is_used;
234 } END_FOR_EACH_PTR(child);
235 DELETE_CURRENT_PTR(def);
236 is_used:
237 ;
238 } END_FOR_EACH_PTR(def);
239 PACK_PTR_LIST(&bb->defines);
240 } END_FOR_EACH_PTR(bb);
241 }
242
merge_pseudo_list(struct pseudo_list * src,struct pseudo_list ** dest)243 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
244 {
245 pseudo_t pseudo;
246 FOR_EACH_PTR(src, pseudo) {
247 add_pseudo_exclusive(dest, pseudo);
248 } END_FOR_EACH_PTR(pseudo);
249 }
250
track_phi_uses(struct instruction * insn)251 static void track_phi_uses(struct instruction *insn)
252 {
253 pseudo_t phi;
254 FOR_EACH_PTR(insn->phi_list, phi) {
255 struct instruction *def;
256 if (phi == VOID || !phi->def)
257 continue;
258 def = phi->def;
259 assert(def->opcode == OP_PHISOURCE);
260 } END_FOR_EACH_PTR(phi);
261 }
262
track_bb_phi_uses(struct basic_block * bb)263 static void track_bb_phi_uses(struct basic_block *bb)
264 {
265 struct instruction *insn;
266 FOR_EACH_PTR(bb->insns, insn) {
267 if (insn->bb && insn->opcode == OP_PHI)
268 track_phi_uses(insn);
269 } END_FOR_EACH_PTR(insn);
270 }
271
272 static struct pseudo_list **live_list;
273 static struct pseudo_list *dead_list;
274
death_def(struct basic_block * bb,pseudo_t pseudo)275 static void death_def(struct basic_block *bb, pseudo_t pseudo)
276 {
277 }
278
death_use(struct basic_block * bb,pseudo_t pseudo)279 static void death_use(struct basic_block *bb, pseudo_t pseudo)
280 {
281 if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
282 add_pseudo(&dead_list, pseudo);
283 add_pseudo(live_list, pseudo);
284 }
285 }
286
track_pseudo_death_bb(struct basic_block * bb)287 static void track_pseudo_death_bb(struct basic_block *bb)
288 {
289 struct pseudo_list *live = NULL;
290 struct basic_block *child;
291 struct instruction *insn;
292
293 FOR_EACH_PTR(bb->children, child) {
294 merge_pseudo_list(child->needs, &live);
295 } END_FOR_EACH_PTR(child);
296
297 live_list = &live;
298 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
299 if (!insn->bb)
300 continue;
301
302 dead_list = NULL;
303 track_instruction_usage(bb, insn, death_def, death_use);
304 if (dead_list) {
305 pseudo_t dead;
306 FOR_EACH_PTR(dead_list, dead) {
307 struct instruction *deathnote = __alloc_instruction(0);
308 deathnote->bb = bb;
309 deathnote->opcode = OP_DEATHNOTE;
310 deathnote->target = dead;
311 INSERT_CURRENT(deathnote, insn);
312 } END_FOR_EACH_PTR(dead);
313 free_ptr_list(&dead_list);
314 }
315 } END_FOR_EACH_PTR_REVERSE(insn);
316 free_ptr_list(&live);
317 }
318
track_pseudo_death(struct entrypoint * ep)319 void track_pseudo_death(struct entrypoint *ep)
320 {
321 struct basic_block *bb;
322
323 FOR_EACH_PTR(ep->bbs, bb) {
324 track_bb_phi_uses(bb);
325 } END_FOR_EACH_PTR(bb);
326
327 FOR_EACH_PTR(ep->bbs, bb) {
328 track_pseudo_death_bb(bb);
329 } END_FOR_EACH_PTR(bb);
330 }
331