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