smatch.h: introduce sm_pedantic()
[smatch.git] / liveness.c
blob30a9a5b6b16966cb06404c25cfe63ce6fc51c8ac
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 "liveness.h"
11 #include "parse.h"
12 #include "expression.h"
13 #include "linearize.h"
14 #include "flow.h"
16 static void phi_defines(struct instruction * phi_node, pseudo_t target,
17 void (*defines)(struct basic_block *, pseudo_t))
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);
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))
35 struct asm_constraint *entry;
37 FOR_EACH_PTR(insn->asm_rules->inputs, entry) {
38 use(bb, entry->pseudo);
39 } END_FOR_EACH_PTR(entry);
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);
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))
53 pseudo_t pseudo;
55 #define USES(x) use(bb, insn->x)
56 #define DEFINES(x) def(bb, insn->x)
58 switch (insn->opcode) {
59 case OP_RET:
60 case OP_COMPUTEDGOTO:
61 USES(src);
62 break;
64 case OP_CBR:
65 case OP_SWITCH:
66 USES(cond);
67 break;
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;
76 /* Uni */
77 case OP_UNOP ... OP_UNOP_END:
78 case OP_SYMADDR:
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_LABEL:
96 case OP_SETVAL:
97 case OP_SETFVAL:
98 DEFINES(target);
99 break;
101 /* Other */
102 case OP_PHI:
103 /* Phi-nodes are "backwards" nodes. Their def doesn't matter */
104 phi_defines(insn, insn->target, def);
105 break;
107 case OP_PHISOURCE:
109 * We don't care about the phi-source define, they get set
110 * up and expanded by the OP_PHI
112 USES(phi_src);
113 break;
115 case OP_CALL:
116 USES(func);
117 if (insn->target != VOID)
118 DEFINES(target);
119 FOR_EACH_PTR(insn->arguments, pseudo) {
120 use(bb, pseudo);
121 } END_FOR_EACH_PTR(pseudo);
122 break;
124 case OP_SLICE:
125 USES(base); DEFINES(target);
126 break;
128 case OP_ASM:
129 asm_liveness(bb, insn, def, use);
130 break;
132 case OP_RANGE:
133 USES(src1); USES(src2); USES(src3);
134 break;
136 case OP_BADOP:
137 case OP_NOP:
138 case OP_CONTEXT:
139 break;
144 static int liveness_changed;
146 static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
148 if (!pseudo_in_list(*list, pseudo)) {
149 liveness_changed = 1;
150 add_pseudo(list, pseudo);
154 static inline int trackable_pseudo(pseudo_t pseudo)
156 return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
159 static void insn_uses(struct basic_block *bb, pseudo_t pseudo)
161 if (trackable_pseudo(pseudo)) {
162 struct instruction *def = pseudo->def;
163 if (pseudo->type != PSEUDO_REG || def->bb != bb || def->opcode == OP_PHI)
164 add_pseudo_exclusive(&bb->needs, pseudo);
168 static void insn_defines(struct basic_block *bb, pseudo_t pseudo)
170 assert(trackable_pseudo(pseudo));
171 add_pseudo(&bb->defines, pseudo);
174 static void track_bb_liveness(struct basic_block *bb)
176 pseudo_t needs;
178 FOR_EACH_PTR(bb->needs, needs) {
179 struct basic_block *parent;
180 FOR_EACH_PTR(bb->parents, parent) {
181 if (!pseudo_in_list(parent->defines, needs)) {
182 add_pseudo_exclusive(&parent->needs, needs);
184 } END_FOR_EACH_PTR(parent);
185 } END_FOR_EACH_PTR(needs);
189 * We need to clear the liveness information if we
190 * are going to re-run it.
192 void clear_liveness(struct entrypoint *ep)
194 struct basic_block *bb;
196 FOR_EACH_PTR(ep->bbs, bb) {
197 free_ptr_list(&bb->needs);
198 free_ptr_list(&bb->defines);
199 } END_FOR_EACH_PTR(bb);
203 * Track inter-bb pseudo liveness. The intra-bb case
204 * is purely local information.
206 void track_pseudo_liveness(struct entrypoint *ep)
208 struct basic_block *bb;
210 /* Add all the bb pseudo usage */
211 FOR_EACH_PTR(ep->bbs, bb) {
212 struct instruction *insn;
213 FOR_EACH_PTR(bb->insns, insn) {
214 if (!insn->bb)
215 continue;
216 assert(insn->bb == bb);
217 track_instruction_usage(bb, insn, insn_defines, insn_uses);
218 } END_FOR_EACH_PTR(insn);
219 } END_FOR_EACH_PTR(bb);
221 /* Calculate liveness.. */
222 do {
223 liveness_changed = 0;
224 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
225 track_bb_liveness(bb);
226 } END_FOR_EACH_PTR_REVERSE(bb);
227 } while (liveness_changed);
229 /* Remove the pseudos from the "defines" list that are used internally */
230 FOR_EACH_PTR(ep->bbs, bb) {
231 pseudo_t def;
232 FOR_EACH_PTR(bb->defines, def) {
233 struct basic_block *child;
234 FOR_EACH_PTR(bb->children, child) {
235 if (pseudo_in_list(child->needs, def))
236 goto is_used;
237 } END_FOR_EACH_PTR(child);
238 DELETE_CURRENT_PTR(def);
239 is_used:
241 } END_FOR_EACH_PTR(def);
242 PACK_PTR_LIST(&bb->defines);
243 } END_FOR_EACH_PTR(bb);
246 static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
248 pseudo_t pseudo;
249 FOR_EACH_PTR(src, pseudo) {
250 add_pseudo_exclusive(dest, pseudo);
251 } END_FOR_EACH_PTR(pseudo);
254 static void track_phi_uses(struct instruction *insn)
256 pseudo_t phi;
257 FOR_EACH_PTR(insn->phi_list, phi) {
258 struct instruction *def;
259 if (phi == VOID || !phi->def)
260 continue;
261 def = phi->def;
262 assert(def->opcode == OP_PHISOURCE);
263 add_ptr_list(&def->phi_users, insn);
264 } END_FOR_EACH_PTR(phi);
267 static void track_bb_phi_uses(struct basic_block *bb)
269 struct instruction *insn;
270 FOR_EACH_PTR(bb->insns, insn) {
271 if (insn->bb && insn->opcode == OP_PHI)
272 track_phi_uses(insn);
273 } END_FOR_EACH_PTR(insn);
276 static struct pseudo_list **live_list;
277 static struct pseudo_list *dead_list;
279 static void death_def(struct basic_block *bb, pseudo_t pseudo)
283 static void death_use(struct basic_block *bb, pseudo_t pseudo)
285 if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
286 add_pseudo(&dead_list, pseudo);
287 add_pseudo(live_list, pseudo);
291 static void track_pseudo_death_bb(struct basic_block *bb)
293 struct pseudo_list *live = NULL;
294 struct basic_block *child;
295 struct instruction *insn;
297 FOR_EACH_PTR(bb->children, child) {
298 merge_pseudo_list(child->needs, &live);
299 } END_FOR_EACH_PTR(child);
301 live_list = &live;
302 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
303 if (!insn->bb)
304 continue;
306 dead_list = NULL;
307 track_instruction_usage(bb, insn, death_def, death_use);
308 if (dead_list) {
309 pseudo_t dead;
310 FOR_EACH_PTR(dead_list, dead) {
311 struct instruction *deathnote = __alloc_instruction(0);
312 deathnote->bb = bb;
313 deathnote->opcode = OP_DEATHNOTE;
314 deathnote->target = dead;
315 INSERT_CURRENT(deathnote, insn);
316 } END_FOR_EACH_PTR(dead);
317 free_ptr_list(&dead_list);
319 } END_FOR_EACH_PTR_REVERSE(insn);
320 free_ptr_list(&live);
323 void track_pseudo_death(struct entrypoint *ep)
325 struct basic_block *bb;
327 FOR_EACH_PTR(ep->bbs, bb) {
328 track_bb_phi_uses(bb);
329 } END_FOR_EACH_PTR(bb);
331 FOR_EACH_PTR(ep->bbs, bb) {
332 track_pseudo_death_bb(bb);
333 } END_FOR_EACH_PTR(bb);