move OP_MUL simplification in a separate function
[smatch.git] / liveness.c
blob2e5139433185f4023d5b449ffebe9ea3e11de060
1 /*
2 * Register - track pseudo usage, maybe eventually try to do register
3 * allocation.
5 * Copyright (C) 2004 Linus Torvalds
6 */
8 #include <assert.h>
10 #include "parse.h"
11 #include "expression.h"
12 #include "linearize.h"
13 #include "flow.h"
15 static void phi_defines(struct instruction * phi_node, pseudo_t target,
16 void (*defines)(struct basic_block *, pseudo_t))
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);
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))
34 struct asm_constraint *entry;
36 FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
37 use(bb, entry->pseudo);
38 } END_FOR_EACH_PTR(entry);
40 FOR_EACH_PTR(insn->asm_rules->outputs, entry) {
41 def(bb, entry->pseudo);
42 } END_FOR_EACH_PTR(entry);
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))
49 pseudo_t pseudo;
51 #define USES(x) use(bb, insn->x)
52 #define DEFINES(x) def(bb, insn->x)
54 switch (insn->opcode) {
55 case OP_RET:
56 USES(src);
57 break;
59 case OP_BR: case OP_SWITCH:
60 USES(cond);
61 break;
63 case OP_COMPUTEDGOTO:
64 USES(target);
65 break;
67 /* Binary */
68 case OP_BINARY ... OP_BINARY_END:
69 case OP_BINCMP ... OP_BINCMP_END:
70 USES(src1); USES(src2); DEFINES(target);
71 break;
73 /* Uni */
74 case OP_NOT: case OP_NEG:
75 USES(src1); DEFINES(target);
76 break;
78 case OP_SEL:
79 USES(src1); USES(src2); USES(src3); DEFINES(target);
80 break;
82 /* Memory */
83 case OP_LOAD:
84 USES(src); DEFINES(target);
85 break;
87 case OP_STORE:
88 USES(src); USES(target);
89 break;
91 case OP_SETVAL:
92 DEFINES(target);
93 break;
95 case OP_SYMADDR:
96 USES(symbol); DEFINES(target);
97 break;
99 /* Other */
100 case OP_PHI:
101 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
102 phi_defines(insn, insn->target, def);
103 break;
105 case OP_PHISOURCE:
107 * We don't care about the phi-source define, they get set
108 * up and expanded by the OP_PHI
110 USES(phi_src);
111 break;
113 case OP_CAST:
114 case OP_SCAST:
115 case OP_FPCAST:
116 case OP_PTRCAST:
117 USES(src); DEFINES(target);
118 break;
120 case OP_CALL:
121 USES(func);
122 if (insn->target != VOID)
123 DEFINES(target);
124 FOR_EACH_PTR(insn->arguments, pseudo) {
125 use(bb, pseudo);
126 } END_FOR_EACH_PTR(pseudo);
127 break;
129 case OP_SLICE:
130 USES(base); DEFINES(target);
131 break;
133 case OP_ASM:
134 asm_liveness(bb, insn, def, use);
135 break;
137 case OP_RANGE:
138 USES(src1); USES(src2); USES(src3);
139 break;
141 case OP_BADOP:
142 case OP_INVOKE:
143 case OP_UNWIND:
144 case OP_MALLOC:
145 case OP_FREE:
146 case OP_ALLOCA:
147 case OP_GET_ELEMENT_PTR:
148 case OP_VANEXT:
149 case OP_VAARG:
150 case OP_SNOP:
151 case OP_LNOP:
152 case OP_NOP:
153 case OP_CONTEXT:
154 break;
158 int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
160 pseudo_t old;
161 FOR_EACH_PTR(list,old) {
162 if (old == pseudo)
163 return 1;
164 } END_FOR_EACH_PTR(old);
165 return 0;
168 static int liveness_changed;
170 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
172 if (!pseudo_in_list(*list, pseudo)) {
173 liveness_changed = 1;
174 add_pseudo(list, pseudo);
178 static inline int trackable_pseudo(pseudo_t pseudo)
180 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
183 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
185 if (trackable_pseudo(pseudo)) {
186 struct instruction *def = pseudo->def;
187 if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI)
188 add_pseudo_exclusive(&bb->needs, pseudo);
192 static void insn_defines(struct basic_block *bb, pseudo_t pseudo)
194 assert(trackable_pseudo(pseudo));
195 add_pseudo(&bb->defines, pseudo);
198 static void track_bb_liveness(struct basic_block *bb)
200 pseudo_t needs;
202 FOR_EACH_PTR(bb->needs, needs) {
203 struct basic_block *parent;
204 FOR_EACH_PTR(bb->parents, parent) {
205 if (!pseudo_in_list(parent->defines, needs)) {
206 add_pseudo_exclusive(&parent->needs, needs);
208 } END_FOR_EACH_PTR(parent);
209 } END_FOR_EACH_PTR(needs);
213 * We need to clear the liveness information if we
214 * are going to re-run it.
216 void clear_liveness(struct entrypoint *ep)
218 struct basic_block *bb;
220 FOR_EACH_PTR(ep->bbs, bb) {
221 free_ptr_list(&bb->needs);
222 free_ptr_list(&bb->defines);
223 } END_FOR_EACH_PTR(bb);
227 * Track inter-bb pseudo liveness. The intra-bb case
228 * is purely local information.
230 void track_pseudo_liveness(struct entrypoint *ep)
232 struct basic_block *bb;
234 /* Add all the bb pseudo usage */
235 FOR_EACH_PTR(ep->bbs, bb) {
236 struct instruction *insn;
237 FOR_EACH_PTR(bb->insns, insn) {
238 if (!insn->bb)
239 continue;
240 assert(insn->bb == bb);
241 track_instruction_usage(bb, insn, insn_defines, insn_uses);
242 } END_FOR_EACH_PTR(insn);
243 } END_FOR_EACH_PTR(bb);
245 /* Calculate liveness.. */
246 do {
247 liveness_changed = 0;
248 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
249 track_bb_liveness(bb);
250 } END_FOR_EACH_PTR_REVERSE(bb);
251 } while (liveness_changed);
253 /* Remove the pseudos from the "defines" list that are used internally */
254 FOR_EACH_PTR(ep->bbs, bb) {
255 pseudo_t def;
256 FOR_EACH_PTR(bb->defines, def) {
257 struct basic_block *child;
258 FOR_EACH_PTR(bb->children, child) {
259 if (pseudo_in_list(child->needs, def))
260 goto is_used;
261 } END_FOR_EACH_PTR(child);
262 DELETE_CURRENT_PTR(def);
263 is_used:
265 } END_FOR_EACH_PTR(def);
266 PACK_PTR_LIST(&bb->defines);
267 } END_FOR_EACH_PTR(bb);
270 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
272 pseudo_t pseudo;
273 FOR_EACH_PTR(src, pseudo) {
274 add_pseudo_exclusive(dest, pseudo);
275 } END_FOR_EACH_PTR(pseudo);
278 void track_phi_uses(struct instruction *insn)
280 pseudo_t phi;
281 FOR_EACH_PTR(insn->phi_list, phi) {
282 struct instruction *def;
283 if (phi == VOID || !phi->def)
284 continue;
285 def = phi->def;
286 assert(def->opcode == OP_PHISOURCE);
287 add_ptr_list(&def->phi_users, insn);
288 } END_FOR_EACH_PTR(phi);
291 static void track_bb_phi_uses(struct basic_block *bb)
293 struct instruction *insn;
294 FOR_EACH_PTR(bb->insns, insn) {
295 if (insn->bb && insn->opcode == OP_PHI)
296 track_phi_uses(insn);
297 } END_FOR_EACH_PTR(insn);
300 static struct pseudo_list **live_list;
301 static struct pseudo_list *dead_list;
303 static void death_def(struct basic_block *bb, pseudo_t pseudo)
307 static void death_use(struct basic_block *bb, pseudo_t pseudo)
309 if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
310 add_pseudo(&dead_list, pseudo);
311 add_pseudo(live_list, pseudo);
315 static void track_pseudo_death_bb(struct basic_block *bb)
317 struct pseudo_list *live = NULL;
318 struct basic_block *child;
319 struct instruction *insn;
321 FOR_EACH_PTR(bb->children, child) {
322 merge_pseudo_list(child->needs, &live);
323 } END_FOR_EACH_PTR(child);
325 live_list = &live;
326 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
327 if (!insn->bb)
328 continue;
330 dead_list = NULL;
331 track_instruction_usage(bb, insn, death_def, death_use);
332 if (dead_list) {
333 pseudo_t dead;
334 FOR_EACH_PTR(dead_list, dead) {
335 struct instruction *deathnote = __alloc_instruction(0);
336 deathnote->bb = bb;
337 deathnote->opcode = OP_DEATHNOTE;
338 deathnote->target = dead;
339 INSERT_CURRENT(deathnote, insn);
340 } END_FOR_EACH_PTR(dead);
341 free_ptr_list(&dead_list);
343 } END_FOR_EACH_PTR_REVERSE(insn);
344 free_ptr_list(&live);
347 void track_pseudo_death(struct entrypoint *ep)
349 struct basic_block *bb;
351 FOR_EACH_PTR(ep->bbs, bb) {
352 track_bb_phi_uses(bb);
353 } END_FOR_EACH_PTR(bb);
355 FOR_EACH_PTR(ep->bbs, bb) {
356 track_pseudo_death_bb(bb);
357 } END_FOR_EACH_PTR(bb);