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