Print this page
11972 resync smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/flow.c
+++ new/usr/src/tools/smatch/src/flow.c
1 1 /*
2 2 * Flow - walk the linearized flowgraph, simplifying it as we
3 3 * go along.
4 4 *
5 5 * Copyright (C) 2004 Linus Torvalds
6 6 */
7 7
8 8 #include <string.h>
9 9 #include <stdarg.h>
10 10 #include <stdlib.h>
11 11 #include <stdio.h>
12 12 #include <stddef.h>
13 13 #include <assert.h>
14 14
15 15 #include "parse.h"
16 16 #include "expression.h"
17 17 #include "linearize.h"
18 18 #include "flow.h"
19 19 #include "target.h"
20 20
21 21 unsigned long bb_generation;
22 22
23 23 /*
24 24 * Dammit, if we have a phi-node followed by a conditional
25 25 * branch on that phi-node, we should damn well be able to
26 26 * do something about the source. Maybe.
27 27 */
28 28 static int rewrite_branch(struct basic_block *bb,
29 29 struct basic_block **ptr,
30 30 struct basic_block *old,
31 31 struct basic_block *new)
32 32 {
33 33 if (*ptr != old || new == old || !bb->ep)
34 34 return 0;
35 35
36 36 /* We might find new if-conversions or non-dominating CSEs */
37 37 /* we may also create new dead cycles */
38 38 repeat_phase |= REPEAT_CSE | REPEAT_CFG_CLEANUP;
39 39 *ptr = new;
40 40 replace_bb_in_list(&bb->children, old, new, 1);
41 41 remove_bb_from_list(&old->parents, bb, 1);
42 42 add_bb(&new->parents, bb);
43 43 return 1;
44 44 }
45 45
46 46 /*
47 47 * Return the known truth value of a pseudo, or -1 if
48 48 * it's not known.
49 49 */
50 50 static int pseudo_truth_value(pseudo_t pseudo)
51 51 {
52 52 switch (pseudo->type) {
53 53 case PSEUDO_VAL:
54 54 return !!pseudo->value;
55 55
56 56 case PSEUDO_REG: {
57 57 struct instruction *insn = pseudo->def;
58 58
59 59 /* A symbol address is always considered true.. */
60 60 if (insn->opcode == OP_SYMADDR && insn->target == pseudo)
61 61 return 1;
62 62 }
63 63 /* Fall through */
64 64 default:
65 65 return -1;
66 66 }
67 67 }
68 68
69 69 /*
70 70 * Does a basic block depend on the pseudos that "src" defines?
71 71 */
72 72 static int bb_depends_on(struct basic_block *target, struct basic_block *src)
73 73 {
74 74 pseudo_t pseudo;
75 75
76 76 FOR_EACH_PTR(src->defines, pseudo) {
77 77 if (pseudo_in_list(target->needs, pseudo))
78 78 return 1;
79 79 } END_FOR_EACH_PTR(pseudo);
80 80 return 0;
81 81 }
82 82
83 83 /*
84 84 * This really should be handled by bb_depends_on()
85 85 * which efficiently check the dependence using the
86 86 * defines - needs liveness info. Problem is that
87 87 * there is no liveness done on OP_PHI & OP_PHISRC.
88 88 *
89 89 * This function add the missing dependency checks.
90 90 */
91 91 static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src)
92 92 {
93 93 struct instruction *insn;
94 94 FOR_EACH_PTR(src->insns, insn) {
95 95 if (!insn->bb)
96 96 continue;
97 97 if (insn->opcode != OP_PHI)
98 98 continue;
99 99 if (pseudo_in_list(target->needs, insn->target))
100 100 return 1;
101 101 } END_FOR_EACH_PTR(insn);
102 102 return 0;
103 103 }
104 104
105 105 /*
106 106 * When we reach here, we have:
107 107 * - a basic block that ends in a conditional branch and
108 108 * that has no side effects apart from the pseudos it
109 109 * may change.
110 110 * - the phi-node that the conditional branch depends on
111 111 * - full pseudo liveness information
112 112 *
113 113 * We need to check if any of the _sources_ of the phi-node
114 114 * may be constant, and not actually need this block at all.
115 115 */
116 116 static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, struct instruction *second)
117 117 {
118 118 int changed = 0;
119 119 pseudo_t phi;
120 120 int bogus;
121 121
122 122 /*
123 123 * This a due to improper dominance tracking during
|
↓ open down ↓ |
123 lines elided |
↑ open up ↑ |
124 124 * simplify_symbol_usage()/conversion to SSA form.
125 125 * No sane simplification can be done when we have this.
126 126 */
127 127 bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list);
128 128
129 129 FOR_EACH_PTR(first->phi_list, phi) {
130 130 struct instruction *def = phi->def;
131 131 struct basic_block *source, *target;
132 132 pseudo_t pseudo;
133 133 struct instruction *br;
134 - int true;
134 + int cond;
135 135
136 136 if (!def)
137 137 continue;
138 138 source = def->bb;
139 139 pseudo = def->src1;
140 140 if (!pseudo || !source)
141 141 continue;
142 142 br = last_instruction(source->insns);
143 143 if (!br)
144 144 continue;
145 145 if (br->opcode != OP_CBR && br->opcode != OP_BR)
146 146 continue;
147 - true = pseudo_truth_value(pseudo);
148 - if (true < 0)
147 + cond = pseudo_truth_value(pseudo);
148 + if (cond < 0)
149 149 continue;
150 - target = true ? second->bb_true : second->bb_false;
150 + target = cond ? second->bb_true : second->bb_false;
151 151 if (bb_depends_on(target, bb))
152 152 continue;
153 153 if (bb_depends_on_phi(target, bb))
154 154 continue;
155 155 changed |= rewrite_branch(source, &br->bb_true, bb, target);
156 156 changed |= rewrite_branch(source, &br->bb_false, bb, target);
157 157 if (changed && !bogus)
158 158 kill_use(THIS_ADDRESS(phi));
159 159 } END_FOR_EACH_PTR(phi);
160 160 return changed;
161 161 }
162 162
163 163 static int bb_has_side_effects(struct basic_block *bb)
164 164 {
165 165 struct instruction *insn;
166 166 FOR_EACH_PTR(bb->insns, insn) {
167 + if (!insn->bb)
168 + continue;
167 169 switch (insn->opcode) {
168 170 case OP_CALL:
169 171 /* FIXME! This should take "const" etc into account */
170 172 return 1;
171 173
174 + case OP_LOAD:
175 + if (!insn->type)
176 + return 1;
177 + if (insn->is_volatile)
178 + return 1;
179 + continue;
180 +
172 181 case OP_STORE:
173 182 case OP_CONTEXT:
174 183 return 1;
175 184
176 185 case OP_ASM:
177 186 /* FIXME! This should take "volatile" etc into account */
178 187 return 1;
179 188
180 189 default:
181 190 continue;
182 191 }
183 192 } END_FOR_EACH_PTR(insn);
184 193 return 0;
185 194 }
186 195
187 196 static int simplify_phi_branch(struct basic_block *bb, struct instruction *br)
188 197 {
189 198 pseudo_t cond = br->cond;
190 199 struct instruction *def;
191 200
192 201 if (cond->type != PSEUDO_REG)
|
↓ open down ↓ |
11 lines elided |
↑ open up ↑ |
193 202 return 0;
194 203 def = cond->def;
195 204 if (def->bb != bb || def->opcode != OP_PHI)
196 205 return 0;
197 206 if (bb_has_side_effects(bb))
198 207 return 0;
199 208 return try_to_simplify_bb(bb, def, br);
200 209 }
201 210
202 211 static int simplify_branch_branch(struct basic_block *bb, struct instruction *br,
203 - struct basic_block **target_p, int true)
212 + struct basic_block **target_p, int bb_true)
204 213 {
205 214 struct basic_block *target = *target_p, *final;
206 215 struct instruction *insn;
207 216 int retval;
208 217
209 218 if (target == bb)
210 219 return 0;
211 220 insn = last_instruction(target->insns);
212 221 if (!insn || insn->opcode != OP_CBR || insn->cond != br->cond)
213 222 return 0;
214 223 /*
215 224 * Ahhah! We've found a branch to a branch on the same conditional!
216 225 * Now we just need to see if we can rewrite the branch..
217 226 */
218 227 retval = 0;
219 - final = true ? insn->bb_true : insn->bb_false;
228 + final = bb_true ? insn->bb_true : insn->bb_false;
220 229 if (bb_has_side_effects(target))
221 230 goto try_to_rewrite_target;
222 231 if (bb_depends_on(final, target))
223 232 goto try_to_rewrite_target;
224 233 if (bb_depends_on_phi(final, target))
225 234 return 0;
226 235 return rewrite_branch(bb, target_p, target, final);
227 236
228 237 try_to_rewrite_target:
229 238 /*
230 239 * If we're the only parent, at least we can rewrite the
231 240 * now-known second branch.
232 241 */
233 242 if (bb_list_size(target->parents) != 1)
234 243 return retval;
235 244 insert_branch(target, insn, final);
236 245 return 1;
237 246 }
238 247
239 248 static int simplify_one_branch(struct basic_block *bb, struct instruction *br)
240 249 {
241 250 if (simplify_phi_branch(bb, br))
242 251 return 1;
243 252 return simplify_branch_branch(bb, br, &br->bb_true, 1) |
244 253 simplify_branch_branch(bb, br, &br->bb_false, 0);
245 254 }
246 255
247 256 static int simplify_branch_nodes(struct entrypoint *ep)
248 257 {
249 258 int changed = 0;
250 259 struct basic_block *bb;
251 260
252 261 FOR_EACH_PTR(ep->bbs, bb) {
253 262 struct instruction *br = last_instruction(bb->insns);
254 263
255 264 if (!br || br->opcode != OP_CBR)
256 265 continue;
257 266 changed |= simplify_one_branch(bb, br);
258 267 } END_FOR_EACH_PTR(bb);
259 268 return changed;
260 269 }
261 270
|
↓ open down ↓ |
32 lines elided |
↑ open up ↑ |
262 271 /*
263 272 * This is called late - when we have intra-bb liveness information..
264 273 */
265 274 int simplify_flow(struct entrypoint *ep)
266 275 {
267 276 return simplify_branch_nodes(ep);
268 277 }
269 278
270 279 static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst)
271 280 {
272 - concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst);
281 + copy_ptr_list((struct ptr_list **)dst, (struct ptr_list *)src);
273 282 }
274 283
275 284 void convert_instruction_target(struct instruction *insn, pseudo_t src)
276 285 {
277 286 pseudo_t target;
278 287 struct pseudo_user *pu;
279 288 /*
280 289 * Go through the "insn->users" list and replace them all..
281 290 */
282 291 target = insn->target;
283 292 if (target == src)
284 293 return;
285 294 FOR_EACH_PTR(target->users, pu) {
286 295 if (*pu->userp != VOID) {
287 296 assert(*pu->userp == target);
288 297 *pu->userp = src;
|
↓ open down ↓ |
6 lines elided |
↑ open up ↑ |
289 298 }
290 299 } END_FOR_EACH_PTR(pu);
291 300 if (has_use_list(src))
292 301 concat_user_list(target->users, &src->users);
293 302 target->users = NULL;
294 303 }
295 304
296 305 void convert_load_instruction(struct instruction *insn, pseudo_t src)
297 306 {
298 307 convert_instruction_target(insn, src);
299 - /* Turn the load into a no-op */
300 - insn->opcode = OP_LNOP;
301 - insn->bb = NULL;
308 + kill_instruction(insn);
309 + repeat_phase |= REPEAT_SYMBOL_CLEANUP;
302 310 }
303 311
304 312 static int overlapping_memop(struct instruction *a, struct instruction *b)
305 313 {
306 314 unsigned int a_start = bytes_to_bits(a->offset);
307 315 unsigned int b_start = bytes_to_bits(b->offset);
308 316 unsigned int a_size = a->size;
309 317 unsigned int b_size = b->size;
310 318
311 319 if (a_size + a_start <= b_start)
312 320 return 0;
313 321 if (b_size + b_start <= a_start)
314 322 return 0;
315 323 return 1;
316 324 }
317 325
318 326 static inline int same_memop(struct instruction *a, struct instruction *b)
319 327 {
320 328 return a->offset == b->offset && a->size == b->size;
321 329 }
322 330
323 331 static inline int distinct_symbols(pseudo_t a, pseudo_t b)
324 332 {
325 333 if (a->type != PSEUDO_SYM)
326 334 return 0;
327 335 if (b->type != PSEUDO_SYM)
328 336 return 0;
329 337 return a->sym != b->sym;
330 338 }
331 339
332 340 /*
333 341 * Return 1 if "dom" dominates the access to "pseudo"
334 342 * in "insn".
335 343 *
336 344 * Return 0 if it doesn't, and -1 if you don't know.
337 345 */
338 346 int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local)
339 347 {
340 348 int opcode = dom->opcode;
341 349
342 350 if (opcode == OP_CALL || opcode == OP_ENTRY)
343 351 return local ? 0 : -1;
344 352 if (opcode != OP_LOAD && opcode != OP_STORE)
345 353 return 0;
346 354 if (dom->src != pseudo) {
347 355 if (local)
348 356 return 0;
349 357 /* We don't think two explicitly different symbols ever alias */
350 358 if (distinct_symbols(insn->src, dom->src))
351 359 return 0;
352 360 /* We could try to do some alias analysis here */
353 361 return -1;
354 362 }
|
↓ open down ↓ |
43 lines elided |
↑ open up ↑ |
355 363 if (!same_memop(insn, dom)) {
356 364 if (dom->opcode == OP_LOAD)
357 365 return 0;
358 366 if (!overlapping_memop(insn, dom))
359 367 return 0;
360 368 return -1;
361 369 }
362 370 return 1;
363 371 }
364 372
365 -static int phisrc_in_bb(struct pseudo_list *list, struct basic_block *bb)
366 -{
367 - pseudo_t p;
368 - FOR_EACH_PTR(list, p) {
369 - if (p->def->bb == bb)
370 - return 1;
371 - } END_FOR_EACH_PTR(p);
372 -
373 - return 0;
374 -}
375 -
376 -static int find_dominating_parents(pseudo_t pseudo, struct instruction *insn,
377 - struct basic_block *bb, unsigned long generation, struct pseudo_list **dominators,
378 - int local)
379 -{
380 - struct basic_block *parent;
381 -
382 - if (!bb->parents)
383 - return !!local;
384 -
385 - FOR_EACH_PTR(bb->parents, parent) {
386 - struct instruction *one;
387 - struct instruction *br;
388 - pseudo_t phi;
389 -
390 - FOR_EACH_PTR_REVERSE(parent->insns, one) {
391 - int dominance;
392 - if (one == insn)
393 - goto no_dominance;
394 - dominance = dominates(pseudo, insn, one, local);
395 - if (dominance < 0) {
396 - if (one->opcode == OP_LOAD)
397 - continue;
398 - return 0;
399 - }
400 - if (!dominance)
401 - continue;
402 - goto found_dominator;
403 - } END_FOR_EACH_PTR_REVERSE(one);
404 -no_dominance:
405 - if (parent->generation == generation)
406 - continue;
407 - parent->generation = generation;
408 -
409 - if (!find_dominating_parents(pseudo, insn, parent, generation, dominators, local))
410 - return 0;
411 - continue;
412 -
413 -found_dominator:
414 - if (dominators && phisrc_in_bb(*dominators, parent))
415 - continue;
416 - br = delete_last_instruction(&parent->insns);
417 - phi = alloc_phi(parent, one->target, one->size);
418 - phi->ident = phi->ident ? : pseudo->ident;
419 - add_instruction(&parent->insns, br);
420 - use_pseudo(insn, phi, add_pseudo(dominators, phi));
421 - } END_FOR_EACH_PTR(parent);
422 - return 1;
423 -}
424 -
425 373 /*
426 374 * We should probably sort the phi list just to make it easier to compare
427 375 * later for equality.
428 376 */
429 377 void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators)
430 378 {
431 379 pseudo_t new, phi;
432 380
433 381 /*
434 382 * Check for somewhat common case of duplicate
435 383 * phi nodes.
436 384 */
437 - new = first_pseudo(dominators)->def->src1;
385 + new = first_pseudo(dominators)->def->phi_src;
438 386 FOR_EACH_PTR(dominators, phi) {
439 - if (new != phi->def->src1)
387 + if (new != phi->def->phi_src)
440 388 goto complex_phi;
441 389 new->ident = new->ident ? : phi->ident;
442 390 } END_FOR_EACH_PTR(phi);
443 391
444 392 /*
445 393 * All the same pseudo - mark the phi-nodes unused
446 394 * and convert the load into a LNOP and replace the
447 395 * pseudo.
448 396 */
397 + convert_load_instruction(insn, new);
449 398 FOR_EACH_PTR(dominators, phi) {
450 399 kill_instruction(phi->def);
451 400 } END_FOR_EACH_PTR(phi);
452 - convert_load_instruction(insn, new);
453 - return;
401 + goto end;
454 402
455 403 complex_phi:
456 404 /* We leave symbol pseudos with a bogus usage list here */
457 405 if (insn->src->type != PSEUDO_SYM)
458 406 kill_use(&insn->src);
459 407 insn->opcode = OP_PHI;
460 408 insn->phi_list = dominators;
461 -}
462 409
463 -static int find_dominating_stores(pseudo_t pseudo, struct instruction *insn,
464 - unsigned long generation, int local)
465 -{
466 - struct basic_block *bb = insn->bb;
467 - struct instruction *one, *dom = NULL;
468 - struct pseudo_list *dominators;
469 - int partial;
470 -
471 - /* Unreachable load? Undo it */
472 - if (!bb) {
473 - insn->opcode = OP_LNOP;
474 - return 1;
475 - }
476 -
477 - partial = 0;
478 - FOR_EACH_PTR(bb->insns, one) {
479 - int dominance;
480 - if (one == insn)
481 - goto found;
482 - dominance = dominates(pseudo, insn, one, local);
483 - if (dominance < 0) {
484 - /* Ignore partial load dominators */
485 - if (one->opcode == OP_LOAD)
486 - continue;
487 - dom = NULL;
488 - partial = 1;
489 - continue;
490 - }
491 - if (!dominance)
492 - continue;
493 - dom = one;
494 - partial = 0;
495 - } END_FOR_EACH_PTR(one);
496 - /* Whaa? */
497 - warning(pseudo->sym->pos, "unable to find symbol read");
498 - return 0;
499 -found:
500 - if (partial)
501 - return 0;
502 -
503 - if (dom) {
504 - convert_load_instruction(insn, dom->target);
505 - return 1;
506 - }
507 -
508 - /* OK, go find the parents */
509 - bb->generation = generation;
510 -
511 - dominators = NULL;
512 - if (!find_dominating_parents(pseudo, insn, bb, generation, &dominators, local))
513 - return 0;
514 -
515 - /* This happens with initial assignments to structures etc.. */
516 - if (!dominators) {
517 - if (!local)
518 - return 0;
519 - check_access(insn);
520 - convert_load_instruction(insn, value_pseudo(insn->type, 0));
521 - return 1;
522 - }
523 -
524 - /*
525 - * If we find just one dominating instruction, we
526 - * can turn it into a direct thing. Otherwise we'll
527 - * have to turn the load into a phi-node of the
528 - * dominators.
529 - */
530 - rewrite_load_instruction(insn, dominators);
531 - return 1;
410 +end:
411 + repeat_phase |= REPEAT_SYMBOL_CLEANUP;
532 412 }
533 413
534 -static void kill_store(struct instruction *insn)
535 -{
536 - if (insn) {
537 - insn->bb = NULL;
538 - insn->opcode = OP_SNOP;
539 - kill_use(&insn->target);
540 - }
541 -}
542 -
543 414 /* Kill a pseudo that is dead on exit from the bb */
544 -static void kill_dead_stores(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
415 +// The context is:
416 +// * the variable is not global but may have its address used (local/non-local)
417 +// * the stores are only needed by others functions which would do some
418 +// loads via the escaped address
419 +// We start by the terminating BB (normal exit BB + no-return/unreachable)
420 +// We walkup the BB' intruction backward
421 +// * we're only concerned by loads, stores & calls
422 +// * if we reach a call -> we have to stop if var is non-local
423 +// * if we reach a load of our var -> we have to stop
424 +// * if we reach a store of our var -> we can kill it, it's dead
425 +// * we can ignore other stores & loads if the var is local
426 +// * if we reach another store or load done via non-symbol access
427 +// (so done via some address calculation) -> we have to stop
428 +// If we reach the top of the BB we can recurse into the parents BBs.
429 +static void kill_dead_stores_bb(pseudo_t pseudo, unsigned long generation, struct basic_block *bb, int local)
545 430 {
546 431 struct instruction *insn;
547 432 struct basic_block *parent;
548 433
549 434 if (bb->generation == generation)
550 435 return;
551 436 bb->generation = generation;
552 437 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
553 - int opcode = insn->opcode;
554 -
555 - if (opcode != OP_LOAD && opcode != OP_STORE) {
556 - if (local)
438 + if (!insn->bb)
439 + continue;
440 + switch (insn->opcode) {
441 + case OP_LOAD:
442 + if (insn->src == pseudo)
443 + return;
444 + break;
445 + case OP_STORE:
446 + if (insn->src == pseudo) {
447 + kill_instruction_force(insn);
557 448 continue;
558 - if (opcode == OP_CALL)
449 + }
450 + break;
451 + case OP_CALL:
452 + if (!local)
559 453 return;
454 + default:
560 455 continue;
561 456 }
562 - if (insn->src == pseudo) {
563 - if (opcode == OP_LOAD)
564 - return;
565 - kill_store(insn);
566 - continue;
567 - }
568 - if (local)
569 - continue;
570 - if (insn->src->type != PSEUDO_SYM)
457 + if (!local && insn->src->type != PSEUDO_SYM)
571 458 return;
572 459 } END_FOR_EACH_PTR_REVERSE(insn);
573 460
574 461 FOR_EACH_PTR(bb->parents, parent) {
575 - struct basic_block *child;
576 - FOR_EACH_PTR(parent->children, child) {
577 - if (child && child != bb)
578 - return;
579 - } END_FOR_EACH_PTR(child);
580 - kill_dead_stores(pseudo, generation, parent, local);
581 - } END_FOR_EACH_PTR(parent);
582 -}
583 -
584 -/*
585 - * This should see if the "insn" trivially dominates some previous store, and kill the
586 - * store if unnecessary.
587 - */
588 -static void kill_dominated_stores(pseudo_t pseudo, struct instruction *insn,
589 - unsigned long generation, struct basic_block *bb, int local, int found)
590 -{
591 - struct instruction *one;
592 - struct basic_block *parent;
593 -
594 - /* Unreachable store? Undo it */
595 - if (!bb) {
596 - kill_store(insn);
597 - return;
598 - }
599 - if (bb->generation == generation)
600 - return;
601 - bb->generation = generation;
602 - FOR_EACH_PTR_REVERSE(bb->insns, one) {
603 - int dominance;
604 - if (!found) {
605 - if (one != insn)
606 - continue;
607 - found = 1;
462 + if (bb_list_size(parent->children) > 1)
608 463 continue;
609 - }
610 - dominance = dominates(pseudo, insn, one, local);
611 - if (!dominance)
612 - continue;
613 - if (dominance < 0)
614 - return;
615 - if (one->opcode == OP_LOAD)
616 - return;
617 - kill_store(one);
618 - } END_FOR_EACH_PTR_REVERSE(one);
619 -
620 - if (!found) {
621 - warning(bb->pos, "Unable to find instruction");
622 - return;
623 - }
624 -
625 - FOR_EACH_PTR(bb->parents, parent) {
626 - struct basic_block *child;
627 - FOR_EACH_PTR(parent->children, child) {
628 - if (child && child != bb)
629 - return;
630 - } END_FOR_EACH_PTR(child);
631 - kill_dominated_stores(pseudo, insn, generation, parent, local, found);
464 + kill_dead_stores_bb(pseudo, generation, parent, local);
632 465 } END_FOR_EACH_PTR(parent);
633 466 }
634 467
635 468 void check_access(struct instruction *insn)
636 469 {
637 470 pseudo_t pseudo = insn->src;
638 471
639 472 if (insn->bb && pseudo->type == PSEUDO_SYM) {
640 473 int offset = insn->offset, bit = bytes_to_bits(offset) + insn->size;
641 474 struct symbol *sym = pseudo->sym;
642 475
643 - if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size))
476 + if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size)) {
477 + if (insn->tainted)
478 + return;
644 479 warning(insn->pos, "invalid access %s '%s' (%d %d)",
645 480 offset < 0 ? "below" : "past the end of",
646 481 show_ident(sym->ident), offset,
647 482 bits_to_bytes(sym->bit_size));
483 + insn->tainted = 1;
484 + }
648 485 }
649 486 }
650 487
651 -static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym)
488 +static struct pseudo_user *first_user(pseudo_t p)
652 489 {
653 - pseudo_t pseudo;
654 490 struct pseudo_user *pu;
655 - unsigned long mod;
656 - int all;
657 -
658 - /* Never used as a symbol? */
659 - pseudo = sym->pseudo;
660 - if (!pseudo)
661 - return;
662 -
663 - /* We don't do coverage analysis of volatiles.. */
664 - if (sym->ctype.modifiers & MOD_VOLATILE)
665 - return;
666 -
667 - /* ..and symbols with external visibility need more care */
668 - mod = sym->ctype.modifiers & (MOD_NONLOCAL | MOD_STATIC | MOD_ADDRESSABLE);
669 - if (mod)
670 - goto external_visibility;
671 -
672 - FOR_EACH_PTR(pseudo->users, pu) {
673 - /* We know that the symbol-pseudo use is the "src" in the instruction */
674 - struct instruction *insn = pu->insn;
675 -
676 - switch (insn->opcode) {
677 - case OP_STORE:
678 - break;
679 - case OP_LOAD:
680 - break;
681 - case OP_SYMADDR:
682 - if (!insn->bb)
683 - continue;
684 - mod |= MOD_ADDRESSABLE;
685 - goto external_visibility;
686 - case OP_NOP:
687 - case OP_SNOP:
688 - case OP_LNOP:
689 - case OP_PHI:
491 + FOR_EACH_PTR(p->users, pu) {
492 + if (!pu)
690 493 continue;
691 - default:
692 - warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident));
693 - }
494 + return pu;
694 495 } END_FOR_EACH_PTR(pu);
496 + return NULL;
497 +}
695 498
696 -external_visibility:
697 - all = 1;
698 - FOR_EACH_PTR_REVERSE(pseudo->users, pu) {
699 - struct instruction *insn = pu->insn;
700 - if (insn->opcode == OP_LOAD)
701 - all &= find_dominating_stores(pseudo, insn, ++bb_generation, !mod);
702 - } END_FOR_EACH_PTR_REVERSE(pu);
499 +void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local)
500 +{
501 + unsigned long generation;
502 + struct basic_block *bb;
703 503
704 - /* If we converted all the loads, remove the stores. They are dead */
705 - if (all && !mod) {
706 - FOR_EACH_PTR(pseudo->users, pu) {
504 + switch (pseudo_user_list_size(addr->users)) {
505 + case 0:
506 + return;
507 + case 1:
508 + if (local) {
509 + struct pseudo_user *pu = first_user(addr);
707 510 struct instruction *insn = pu->insn;
708 - if (insn->opcode == OP_STORE)
709 - kill_store(insn);
710 - } END_FOR_EACH_PTR(pu);
711 - } else {
712 - /*
713 - * If we couldn't take the shortcut, see if we can at least kill some
714 - * of them..
715 - */
716 - FOR_EACH_PTR(pseudo->users, pu) {
717 - struct instruction *insn = pu->insn;
718 - if (insn->opcode == OP_STORE)
719 - kill_dominated_stores(pseudo, insn, ++bb_generation, insn->bb, !mod, 0);
720 - } END_FOR_EACH_PTR(pu);
721 -
722 - if (!(mod & (MOD_NONLOCAL | MOD_STATIC))) {
723 - struct basic_block *bb;
724 - FOR_EACH_PTR(ep->bbs, bb) {
725 - if (!bb->children)
726 - kill_dead_stores(pseudo, ++bb_generation, bb, !mod);
727 - } END_FOR_EACH_PTR(bb);
511 + if (insn->opcode == OP_STORE) {
512 + kill_instruction_force(insn);
513 + return;
514 + }
728 515 }
516 + default:
517 + break;
729 518 }
730 -
731 - return;
732 -}
733 519
734 -void simplify_symbol_usage(struct entrypoint *ep)
735 -{
736 - pseudo_t pseudo;
737 -
738 - FOR_EACH_PTR(ep->accesses, pseudo) {
739 - simplify_one_symbol(ep, pseudo->sym);
740 - } END_FOR_EACH_PTR(pseudo);
520 + generation = ++bb_generation;
521 + FOR_EACH_PTR(ep->bbs, bb) {
522 + if (bb->children)
523 + continue;
524 + kill_dead_stores_bb(addr, generation, bb, local);
525 + } END_FOR_EACH_PTR(bb);
741 526 }
742 527
743 528 static void mark_bb_reachable(struct basic_block *bb, unsigned long generation)
744 529 {
745 530 struct basic_block *child;
746 531
747 532 if (bb->generation == generation)
748 533 return;
749 534 bb->generation = generation;
750 535 FOR_EACH_PTR(bb->children, child) {
751 536 mark_bb_reachable(child, generation);
752 537 } END_FOR_EACH_PTR(child);
753 538 }
754 539
755 540 static void kill_defs(struct instruction *insn)
756 541 {
757 542 pseudo_t target = insn->target;
758 543
759 544 if (!has_use_list(target))
760 545 return;
761 546 if (target->def != insn)
762 547 return;
|
↓ open down ↓ |
12 lines elided |
↑ open up ↑ |
763 548
764 549 convert_instruction_target(insn, VOID);
765 550 }
766 551
767 552 void kill_bb(struct basic_block *bb)
768 553 {
769 554 struct instruction *insn;
770 555 struct basic_block *child, *parent;
771 556
772 557 FOR_EACH_PTR(bb->insns, insn) {
558 + if (!insn->bb)
559 + continue;
773 560 kill_instruction_force(insn);
774 561 kill_defs(insn);
775 562 /*
776 563 * We kill unreachable instructions even if they
777 564 * otherwise aren't "killable" (e.g. volatile loads)
778 565 */
779 566 } END_FOR_EACH_PTR(insn);
780 567 bb->insns = NULL;
781 568
782 569 FOR_EACH_PTR(bb->children, child) {
783 570 remove_bb_from_list(&child->parents, bb, 0);
784 571 } END_FOR_EACH_PTR(child);
785 572 bb->children = NULL;
786 573
787 574 FOR_EACH_PTR(bb->parents, parent) {
788 575 remove_bb_from_list(&parent->children, bb, 0);
789 576 } END_FOR_EACH_PTR(parent);
790 577 bb->parents = NULL;
791 578 }
792 579
793 580 void kill_unreachable_bbs(struct entrypoint *ep)
794 581 {
795 582 struct basic_block *bb;
796 583 unsigned long generation = ++bb_generation;
797 584
798 585 mark_bb_reachable(ep->entry->bb, generation);
799 586 FOR_EACH_PTR(ep->bbs, bb) {
800 587 if (bb->generation == generation)
801 588 continue;
802 589 /* Mark it as being dead */
803 590 kill_bb(bb);
804 591 bb->ep = NULL;
805 592 DELETE_CURRENT_PTR(bb);
806 593 } END_FOR_EACH_PTR(bb);
807 594 PACK_PTR_LIST(&ep->bbs);
808 595 }
809 596
810 597 static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new)
811 598 {
812 599 int changed = 0;
813 600 struct instruction *insn = last_instruction(bb->insns);
814 601
815 602 if (!insn)
816 603 return 0;
817 604
818 605 /* Infinite loops: let's not "optimize" them.. */
819 606 if (old == new)
820 607 return 0;
821 608
822 609 switch (insn->opcode) {
823 610 case OP_CBR:
824 611 changed |= rewrite_branch(bb, &insn->bb_false, old, new);
825 612 /* fall through */
826 613 case OP_BR:
827 614 changed |= rewrite_branch(bb, &insn->bb_true, old, new);
828 615 assert(changed);
829 616 return changed;
830 617 case OP_SWITCH: {
831 618 struct multijmp *jmp;
832 619 FOR_EACH_PTR(insn->multijmp_list, jmp) {
833 620 changed |= rewrite_branch(bb, &jmp->target, old, new);
834 621 } END_FOR_EACH_PTR(jmp);
835 622 assert(changed);
836 623 return changed;
|
↓ open down ↓ |
54 lines elided |
↑ open up ↑ |
837 624 }
838 625 default:
839 626 return 0;
840 627 }
841 628 }
842 629
843 630 static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct instruction *br)
844 631 {
845 632 struct basic_block *parent;
846 633 struct basic_block *target = br->bb_true;
847 - struct basic_block *false = br->bb_false;
848 634
849 635 if (br->opcode == OP_CBR) {
850 636 pseudo_t cond = br->cond;
851 637 if (cond->type != PSEUDO_VAL)
852 638 return NULL;
853 - target = cond->value ? target : false;
639 + target = cond->value ? target : br->bb_false;
854 640 }
855 641
856 642 /*
857 643 * We can't do FOR_EACH_PTR() here, because the parent list
858 644 * may change when we rewrite the parent.
859 645 */
860 646 while ((parent = first_basic_block(bb->parents)) != NULL) {
861 647 if (!rewrite_parent_branch(parent, bb, target))
862 648 return NULL;
863 649 }
864 650 return target;
865 651 }
866 652
867 653 static void vrfy_bb_in_list(struct basic_block *bb, struct basic_block_list *list)
868 654 {
869 655 if (bb) {
870 656 struct basic_block *tmp;
871 657 int no_bb_in_list = 0;
872 658
873 659 FOR_EACH_PTR(list, tmp) {
874 660 if (bb == tmp)
875 661 return;
876 662 } END_FOR_EACH_PTR(tmp);
877 663 assert(no_bb_in_list);
878 664 }
879 665 }
880 666
881 667 static void vrfy_parents(struct basic_block *bb)
882 668 {
883 669 struct basic_block *tmp;
884 670 FOR_EACH_PTR(bb->parents, tmp) {
885 671 vrfy_bb_in_list(bb, tmp->children);
886 672 } END_FOR_EACH_PTR(tmp);
887 673 }
888 674
889 675 static void vrfy_children(struct basic_block *bb)
890 676 {
891 677 struct basic_block *tmp;
892 678 struct instruction *br = last_instruction(bb->insns);
893 679
894 680 if (!br) {
895 681 assert(!bb->children);
896 682 return;
897 683 }
898 684 switch (br->opcode) {
899 685 struct multijmp *jmp;
900 686 case OP_CBR:
901 687 vrfy_bb_in_list(br->bb_false, bb->children);
902 688 /* fall through */
903 689 case OP_BR:
904 690 vrfy_bb_in_list(br->bb_true, bb->children);
905 691 break;
906 692 case OP_SWITCH:
907 693 case OP_COMPUTEDGOTO:
908 694 FOR_EACH_PTR(br->multijmp_list, jmp) {
909 695 vrfy_bb_in_list(jmp->target, bb->children);
910 696 } END_FOR_EACH_PTR(jmp);
911 697 break;
912 698 default:
913 699 break;
914 700 }
915 701
916 702 FOR_EACH_PTR(bb->children, tmp) {
917 703 vrfy_bb_in_list(bb, tmp->parents);
918 704 } END_FOR_EACH_PTR(tmp);
919 705 }
920 706
921 707 static void vrfy_bb_flow(struct basic_block *bb)
922 708 {
923 709 vrfy_children(bb);
924 710 vrfy_parents(bb);
925 711 }
926 712
927 713 void vrfy_flow(struct entrypoint *ep)
928 714 {
929 715 struct basic_block *bb;
930 716 struct basic_block *entry = ep->entry->bb;
931 717
932 718 FOR_EACH_PTR(ep->bbs, bb) {
933 719 if (bb == entry)
934 720 entry = NULL;
935 721 vrfy_bb_flow(bb);
936 722 } END_FOR_EACH_PTR(bb);
937 723 assert(!entry);
938 724 }
939 725
940 726 void pack_basic_blocks(struct entrypoint *ep)
941 727 {
942 728 struct basic_block *bb;
943 729
944 730 /* See if we can merge a bb into another one.. */
945 731 FOR_EACH_PTR(ep->bbs, bb) {
946 732 struct instruction *first, *insn;
947 733 struct basic_block *parent, *child, *last;
948 734
|
↓ open down ↓ |
85 lines elided |
↑ open up ↑ |
949 735 if (!bb_reachable(bb))
950 736 continue;
951 737
952 738 /*
953 739 * Just a branch?
954 740 */
955 741 FOR_EACH_PTR(bb->insns, first) {
956 742 if (!first->bb)
957 743 continue;
958 744 switch (first->opcode) {
959 - case OP_NOP: case OP_LNOP: case OP_SNOP:
745 + case OP_NOP:
746 + case OP_INLINED_CALL:
960 747 continue;
961 748 case OP_CBR:
962 749 case OP_BR: {
963 750 struct basic_block *replace;
964 751 replace = rewrite_branch_bb(bb, first);
965 752 if (replace) {
966 753 kill_bb(bb);
967 754 goto no_merge;
968 755 }
969 756 }
970 757 /* fallthrough */
971 758 default:
972 759 goto out;
973 760 }
974 761 } END_FOR_EACH_PTR(first);
975 762
976 763 out:
977 764 /*
978 765 * See if we only have one parent..
979 766 */
980 767 last = NULL;
981 768 FOR_EACH_PTR(bb->parents, parent) {
982 769 if (last) {
983 770 if (last != parent)
984 771 goto no_merge;
985 772 continue;
986 773 }
987 774 last = parent;
988 775 } END_FOR_EACH_PTR(parent);
989 776
990 777 parent = last;
991 778 if (!parent || parent == bb)
992 779 continue;
993 780
994 781 /*
|
↓ open down ↓ |
25 lines elided |
↑ open up ↑ |
995 782 * Goodie. See if the parent can merge..
996 783 */
997 784 FOR_EACH_PTR(parent->children, child) {
998 785 if (child != bb)
999 786 goto no_merge;
1000 787 } END_FOR_EACH_PTR(child);
1001 788
1002 789 /*
1003 790 * Merge the two.
1004 791 */
1005 - repeat_phase |= REPEAT_CSE;
792 + repeat_phase |= REPEAT_CFG_CLEANUP;
1006 793
1007 794 parent->children = bb->children;
1008 795 bb->children = NULL;
1009 796 bb->parents = NULL;
1010 797
1011 798 FOR_EACH_PTR(parent->children, child) {
1012 799 replace_bb_in_list(&child->parents, bb, parent, 0);
1013 800 } END_FOR_EACH_PTR(child);
1014 801
1015 802 kill_instruction(delete_last_instruction(&parent->insns));
1016 803 FOR_EACH_PTR(bb->insns, insn) {
1017 - if (insn->bb) {
1018 - assert(insn->bb == bb);
1019 - insn->bb = parent;
1020 - }
804 + if (!insn->bb)
805 + continue;
806 + assert(insn->bb == bb);
807 + insn->bb = parent;
1021 808 add_instruction(&parent->insns, insn);
1022 809 } END_FOR_EACH_PTR(insn);
1023 810 bb->insns = NULL;
1024 811
1025 812 no_merge:
1026 813 /* nothing to do */;
1027 814 } END_FOR_EACH_PTR(bb);
1028 815 }
1029 816
1030 817
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX