db: pass the call expression to call_implies callbacks
[smatch.git] / liveness.c
blobeeff0f79dfd3c40edc5f779d1d57253760275b2b
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 *, struct instruction *, 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 if (def->opcode == OP_PHI) {
27 phi_defines(def, target, defines);
28 continue;
30 defines(def->bb, phi->def, target);
31 } END_FOR_EACH_PTR(phi);
34 static void asm_liveness(struct basic_block *bb, struct instruction *insn,
35 void (*def)(struct basic_block *, struct instruction *, pseudo_t),
36 void (*use)(struct basic_block *, struct instruction *, pseudo_t))
38 struct asm_constraint *entry;
40 FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
41 use(bb, insn, entry->pseudo);
42 } END_FOR_EACH_PTR(entry);
44 FOR_EACH_PTR(insn->asm_rules->outputs, entry) {
45 def(bb, insn, entry->pseudo);
46 } END_FOR_EACH_PTR(entry);
49 static void track_instruction_usage(struct basic_block *bb, struct instruction *insn,
50 void (*def)(struct basic_block *, struct instruction *, pseudo_t),
51 void (*use)(struct basic_block *, struct instruction *, pseudo_t))
53 pseudo_t pseudo;
55 #define USES(x) use(bb, insn, insn->x)
56 #define DEFINES(x) def(bb, insn, insn->x)
58 switch (insn->opcode) {
59 case OP_RET:
60 USES(src);
61 break;
63 case OP_BR: case OP_SWITCH:
64 USES(cond);
65 break;
67 case OP_COMPUTEDGOTO:
68 USES(target);
69 break;
71 /* Binary */
72 case OP_BINARY ... OP_BINARY_END:
73 case OP_BINCMP ... OP_BINCMP_END:
74 USES(src1); USES(src2); DEFINES(target);
75 break;
77 /* Uni */
78 case OP_NOT: case OP_NEG:
79 USES(src1); DEFINES(target);
80 break;
82 case OP_SEL:
83 USES(src1); USES(src2); USES(src3); DEFINES(target);
84 break;
86 /* Memory */
87 case OP_LOAD:
88 USES(src); DEFINES(target);
89 break;
91 case OP_STORE:
92 USES(src); USES(target);
93 break;
95 case OP_SETVAL:
96 DEFINES(target);
97 break;
99 case OP_SYMADDR:
100 USES(symbol); DEFINES(target);
101 break;
103 /* Other */
104 case OP_PHI:
105 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
106 phi_defines(insn, insn->target, def);
107 break;
109 case OP_PHISOURCE:
111 * We don't care about the phi-source define, they get set
112 * up and expanded by the OP_PHI
114 USES(phi_src);
115 break;
117 case OP_CAST:
118 case OP_SCAST:
119 case OP_FPCAST:
120 case OP_PTRCAST:
121 USES(src); DEFINES(target);
122 break;
124 case OP_CALL:
125 USES(func);
126 if (insn->target != VOID)
127 DEFINES(target);
128 FOR_EACH_PTR(insn->arguments, pseudo) {
129 use(bb, insn, pseudo);
130 } END_FOR_EACH_PTR(pseudo);
131 break;
133 case OP_SLICE:
134 USES(base); DEFINES(target);
135 break;
137 case OP_ASM:
138 asm_liveness(bb, insn, def, use);
139 break;
141 case OP_RANGE:
142 USES(src1); USES(src2); USES(src3);
143 break;
145 case OP_BADOP:
146 case OP_INVOKE:
147 case OP_UNWIND:
148 case OP_MALLOC:
149 case OP_FREE:
150 case OP_ALLOCA:
151 case OP_GET_ELEMENT_PTR:
152 case OP_VANEXT:
153 case OP_VAARG:
154 case OP_SNOP:
155 case OP_LNOP:
156 case OP_NOP:
157 case OP_CONTEXT:
158 break;
162 int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
164 pseudo_t old;
165 FOR_EACH_PTR(list,old) {
166 if (old == pseudo)
167 return 1;
168 } END_FOR_EACH_PTR(old);
169 return 0;
172 static int liveness_changed;
174 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
176 if (!pseudo_in_list(*list, pseudo)) {
177 liveness_changed = 1;
178 add_pseudo(list, pseudo);
182 static inline int trackable_pseudo(pseudo_t pseudo)
184 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
187 static void insn_uses(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
189 if (trackable_pseudo(pseudo)) {
190 struct instruction *def = pseudo->def;
191 if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI)
192 add_pseudo_exclusive(&bb->needs, pseudo);
196 static void insn_defines(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
198 assert(trackable_pseudo(pseudo));
199 add_pseudo(&bb->defines, pseudo);
202 static void track_bb_liveness(struct basic_block *bb)
204 pseudo_t needs;
206 FOR_EACH_PTR(bb->needs, needs) {
207 struct basic_block *parent;
208 FOR_EACH_PTR(bb->parents, parent) {
209 if (!pseudo_in_list(parent->defines, needs)) {
210 add_pseudo_exclusive(&parent->needs, needs);
212 } END_FOR_EACH_PTR(parent);
213 } END_FOR_EACH_PTR(needs);
217 * We need to clear the liveness information if we
218 * are going to re-run it.
220 void clear_liveness(struct entrypoint *ep)
222 struct basic_block *bb;
224 FOR_EACH_PTR(ep->bbs, bb) {
225 free_ptr_list(&bb->needs);
226 free_ptr_list(&bb->defines);
227 } END_FOR_EACH_PTR(bb);
231 * Track inter-bb pseudo liveness. The intra-bb case
232 * is purely local information.
234 void track_pseudo_liveness(struct entrypoint *ep)
236 struct basic_block *bb;
238 /* Add all the bb pseudo usage */
239 FOR_EACH_PTR(ep->bbs, bb) {
240 struct instruction *insn;
241 FOR_EACH_PTR(bb->insns, insn) {
242 if (!insn->bb)
243 continue;
244 assert(insn->bb == bb);
245 track_instruction_usage(bb, insn, insn_defines, insn_uses);
246 } END_FOR_EACH_PTR(insn);
247 } END_FOR_EACH_PTR(bb);
249 /* Calculate liveness.. */
250 do {
251 liveness_changed = 0;
252 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
253 track_bb_liveness(bb);
254 } END_FOR_EACH_PTR_REVERSE(bb);
255 } while (liveness_changed);
257 /* Remove the pseudos from the "defines" list that are used internally */
258 FOR_EACH_PTR(ep->bbs, bb) {
259 pseudo_t def;
260 FOR_EACH_PTR(bb->defines, def) {
261 struct basic_block *child;
262 FOR_EACH_PTR(bb->children, child) {
263 if (pseudo_in_list(child->needs, def))
264 goto is_used;
265 } END_FOR_EACH_PTR(child);
266 DELETE_CURRENT_PTR(def);
267 is_used:
269 } END_FOR_EACH_PTR(def);
270 PACK_PTR_LIST(&bb->defines);
271 } END_FOR_EACH_PTR(bb);
274 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
276 pseudo_t pseudo;
277 FOR_EACH_PTR(src, pseudo) {
278 add_pseudo_exclusive(dest, pseudo);
279 } END_FOR_EACH_PTR(pseudo);
282 void track_phi_uses(struct instruction *insn)
284 pseudo_t phi;
285 FOR_EACH_PTR(insn->phi_list, phi) {
286 struct instruction *def;
287 if (phi == VOID || !phi->def)
288 continue;
289 def = phi->def;
290 assert(def->opcode == OP_PHISOURCE);
291 add_ptr_list(&def->phi_users, insn);
292 } END_FOR_EACH_PTR(phi);
295 static void track_bb_phi_uses(struct basic_block *bb)
297 struct instruction *insn;
298 FOR_EACH_PTR(bb->insns, insn) {
299 if (insn->bb && insn->opcode == OP_PHI)
300 track_phi_uses(insn);
301 } END_FOR_EACH_PTR(insn);
304 static struct pseudo_list **live_list;
305 static struct pseudo_list *dead_list;
307 static void death_def(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
311 static void death_use(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
313 if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
314 add_pseudo(&dead_list, pseudo);
315 add_pseudo(live_list, pseudo);
319 static void track_pseudo_death_bb(struct basic_block *bb)
321 struct pseudo_list *live = NULL;
322 struct basic_block *child;
323 struct instruction *insn;
325 FOR_EACH_PTR(bb->children, child) {
326 merge_pseudo_list(child->needs, &live);
327 } END_FOR_EACH_PTR(child);
329 live_list = &live;
330 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
331 if (!insn->bb)
332 continue;
334 dead_list = NULL;
335 track_instruction_usage(bb, insn, death_def, death_use);
336 if (dead_list) {
337 pseudo_t dead;
338 FOR_EACH_PTR(dead_list, dead) {
339 struct instruction *deathnote = __alloc_instruction(0);
340 deathnote->bb = bb;
341 deathnote->opcode = OP_DEATHNOTE;
342 deathnote->target = dead;
343 INSERT_CURRENT(deathnote, insn);
344 } END_FOR_EACH_PTR(dead);
345 free_ptr_list(&dead_list);
347 } END_FOR_EACH_PTR_REVERSE(insn);
348 free_ptr_list(&live);
351 void track_pseudo_death(struct entrypoint *ep)
353 struct basic_block *bb;
355 FOR_EACH_PTR(ep->bbs, bb) {
356 track_bb_phi_uses(bb);
357 } END_FOR_EACH_PTR(bb);
359 FOR_EACH_PTR(ep->bbs, bb) {
360 track_pseudo_death_bb(bb);
361 } END_FOR_EACH_PTR(bb);