1 /* 2 * Flow - walk the linearized flowgraph, simplifying it as we 3 * go along. 4 * 5 * Copyright (C) 2004 Linus Torvalds 6 */ 7 8 #include <string.h> 9 #include <stdarg.h> 10 #include <stdlib.h> 11 #include <stdio.h> 12 #include <stddef.h> 13 #include <assert.h> 14 15 #include "parse.h" 16 #include "expression.h" 17 #include "linearize.h" 18 #include "flow.h" 19 #include "target.h" 20 21 unsigned long bb_generation; 22 23 /* 24 * Dammit, if we have a phi-node followed by a conditional 25 * branch on that phi-node, we should damn well be able to 26 * do something about the source. Maybe. 27 */ 28 static int rewrite_branch(struct basic_block *bb, 29 struct basic_block **ptr, 30 struct basic_block *old, 31 struct basic_block *new) 32 { 33 if (*ptr != old || new == old || !bb->ep) 34 return 0; 35 36 /* We might find new if-conversions or non-dominating CSEs */ 37 /* we may also create new dead cycles */ 38 repeat_phase |= REPEAT_CSE | REPEAT_CFG_CLEANUP; 39 *ptr = new; 40 replace_bb_in_list(&bb->children, old, new, 1); 41 remove_bb_from_list(&old->parents, bb, 1); 42 add_bb(&new->parents, bb); 43 return 1; 44 } 45 46 /* 47 * Return the known truth value of a pseudo, or -1 if 48 * it's not known. 49 */ 50 static int pseudo_truth_value(pseudo_t pseudo) 51 { 52 switch (pseudo->type) { 53 case PSEUDO_VAL: 54 return !!pseudo->value; 55 56 case PSEUDO_REG: { 57 struct instruction *insn = pseudo->def; 58 59 /* A symbol address is always considered true.. */ 60 if (insn->opcode == OP_SYMADDR && insn->target == pseudo) 61 return 1; 62 } 63 /* Fall through */ 64 default: 65 return -1; 66 } 67 } 68 69 /* 70 * Does a basic block depend on the pseudos that "src" defines? 71 */ 72 static int bb_depends_on(struct basic_block *target, struct basic_block *src) 73 { 74 pseudo_t pseudo; 75 76 FOR_EACH_PTR(src->defines, pseudo) { 77 if (pseudo_in_list(target->needs, pseudo)) 78 return 1; 79 } END_FOR_EACH_PTR(pseudo); 80 return 0; 81 } 82 83 /* 84 * This really should be handled by bb_depends_on() 85 * which efficiently check the dependence using the 86 * defines - needs liveness info. Problem is that 87 * there is no liveness done on OP_PHI & OP_PHISRC. 88 * 89 * This function add the missing dependency checks. 90 */ 91 static int bb_depends_on_phi(struct basic_block *target, struct basic_block *src) 92 { 93 struct instruction *insn; 94 FOR_EACH_PTR(src->insns, insn) { 95 if (!insn->bb) 96 continue; 97 if (insn->opcode != OP_PHI) 98 continue; 99 if (pseudo_in_list(target->needs, insn->target)) 100 return 1; 101 } END_FOR_EACH_PTR(insn); 102 return 0; 103 } 104 105 /* 106 * When we reach here, we have: 107 * - a basic block that ends in a conditional branch and 108 * that has no side effects apart from the pseudos it 109 * may change. 110 * - the phi-node that the conditional branch depends on 111 * - full pseudo liveness information 112 * 113 * We need to check if any of the _sources_ of the phi-node 114 * may be constant, and not actually need this block at all. 115 */ 116 static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, struct instruction *second) 117 { 118 int changed = 0; 119 pseudo_t phi; 120 int bogus; 121 122 /* 123 * This a due to improper dominance tracking during 124 * simplify_symbol_usage()/conversion to SSA form. 125 * No sane simplification can be done when we have this. 126 */ 127 bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list); 128 129 FOR_EACH_PTR(first->phi_list, phi) { 130 struct instruction *def = phi->def; 131 struct basic_block *source, *target; 132 pseudo_t pseudo; 133 struct instruction *br; 134 int true; 135 136 if (!def) 137 continue; 138 source = def->bb; 139 pseudo = def->src1; 140 if (!pseudo || !source) 141 continue; 142 br = last_instruction(source->insns); 143 if (!br) 144 continue; 145 if (br->opcode != OP_CBR && br->opcode != OP_BR) 146 continue; 147 true = pseudo_truth_value(pseudo); 148 if (true < 0) 149 continue; 150 target = true ? second->bb_true : second->bb_false; 151 if (bb_depends_on(target, bb)) 152 continue; 153 if (bb_depends_on_phi(target, bb)) 154 continue; 155 changed |= rewrite_branch(source, &br->bb_true, bb, target); 156 changed |= rewrite_branch(source, &br->bb_false, bb, target); 157 if (changed && !bogus) 158 kill_use(THIS_ADDRESS(phi)); 159 } END_FOR_EACH_PTR(phi); 160 return changed; 161 } 162 163 static int bb_has_side_effects(struct basic_block *bb) 164 { 165 struct instruction *insn; 166 FOR_EACH_PTR(bb->insns, insn) { 167 switch (insn->opcode) { 168 case OP_CALL: 169 /* FIXME! This should take "const" etc into account */ 170 return 1; 171 172 case OP_STORE: 173 case OP_CONTEXT: 174 return 1; 175 176 case OP_ASM: 177 /* FIXME! This should take "volatile" etc into account */ 178 return 1; 179 180 default: 181 continue; 182 } 183 } END_FOR_EACH_PTR(insn); 184 return 0; 185 } 186 187 static int simplify_phi_branch(struct basic_block *bb, struct instruction *br) 188 { 189 pseudo_t cond = br->cond; 190 struct instruction *def; 191 192 if (cond->type != PSEUDO_REG) 193 return 0; 194 def = cond->def; 195 if (def->bb != bb || def->opcode != OP_PHI) 196 return 0; 197 if (bb_has_side_effects(bb)) 198 return 0; 199 return try_to_simplify_bb(bb, def, br); 200 } 201 202 static int simplify_branch_branch(struct basic_block *bb, struct instruction *br, 203 struct basic_block **target_p, int true) 204 { 205 struct basic_block *target = *target_p, *final; 206 struct instruction *insn; 207 int retval; 208 209 if (target == bb) 210 return 0; 211 insn = last_instruction(target->insns); 212 if (!insn || insn->opcode != OP_CBR || insn->cond != br->cond) 213 return 0; 214 /* 215 * Ahhah! We've found a branch to a branch on the same conditional! 216 * Now we just need to see if we can rewrite the branch.. 217 */ 218 retval = 0; 219 final = true ? insn->bb_true : insn->bb_false; 220 if (bb_has_side_effects(target)) 221 goto try_to_rewrite_target; 222 if (bb_depends_on(final, target)) 223 goto try_to_rewrite_target; 224 if (bb_depends_on_phi(final, target)) 225 return 0; 226 return rewrite_branch(bb, target_p, target, final); 227 228 try_to_rewrite_target: 229 /* 230 * If we're the only parent, at least we can rewrite the 231 * now-known second branch. 232 */ 233 if (bb_list_size(target->parents) != 1) 234 return retval; 235 insert_branch(target, insn, final); 236 return 1; 237 } 238 239 static int simplify_one_branch(struct basic_block *bb, struct instruction *br) 240 { 241 if (simplify_phi_branch(bb, br)) 242 return 1; 243 return simplify_branch_branch(bb, br, &br->bb_true, 1) | 244 simplify_branch_branch(bb, br, &br->bb_false, 0); 245 } 246 247 static int simplify_branch_nodes(struct entrypoint *ep) 248 { 249 int changed = 0; 250 struct basic_block *bb; 251 252 FOR_EACH_PTR(ep->bbs, bb) { 253 struct instruction *br = last_instruction(bb->insns); 254 255 if (!br || br->opcode != OP_CBR) 256 continue; 257 changed |= simplify_one_branch(bb, br); 258 } END_FOR_EACH_PTR(bb); 259 return changed; 260 } 261 262 /* 263 * This is called late - when we have intra-bb liveness information.. 264 */ 265 int simplify_flow(struct entrypoint *ep) 266 { 267 return simplify_branch_nodes(ep); 268 } 269 270 static inline void concat_user_list(struct pseudo_user_list *src, struct pseudo_user_list **dst) 271 { 272 concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst); 273 } 274 275 void convert_instruction_target(struct instruction *insn, pseudo_t src) 276 { 277 pseudo_t target; 278 struct pseudo_user *pu; 279 /* 280 * Go through the "insn->users" list and replace them all.. 281 */ 282 target = insn->target; 283 if (target == src) 284 return; 285 FOR_EACH_PTR(target->users, pu) { 286 if (*pu->userp != VOID) { 287 assert(*pu->userp == target); 288 *pu->userp = src; 289 } 290 } END_FOR_EACH_PTR(pu); 291 if (has_use_list(src)) 292 concat_user_list(target->users, &src->users); 293 target->users = NULL; 294 } 295 296 void convert_load_instruction(struct instruction *insn, pseudo_t src) 297 { 298 convert_instruction_target(insn, src); 299 /* Turn the load into a no-op */ 300 insn->opcode = OP_LNOP; 301 insn->bb = NULL; 302 } 303 304 static int overlapping_memop(struct instruction *a, struct instruction *b) 305 { 306 unsigned int a_start = bytes_to_bits(a->offset); 307 unsigned int b_start = bytes_to_bits(b->offset); 308 unsigned int a_size = a->size; 309 unsigned int b_size = b->size; 310 311 if (a_size + a_start <= b_start) 312 return 0; 313 if (b_size + b_start <= a_start) 314 return 0; 315 return 1; 316 } 317 318 static inline int same_memop(struct instruction *a, struct instruction *b) 319 { 320 return a->offset == b->offset && a->size == b->size; 321 } 322 323 static inline int distinct_symbols(pseudo_t a, pseudo_t b) 324 { 325 if (a->type != PSEUDO_SYM) 326 return 0; 327 if (b->type != PSEUDO_SYM) 328 return 0; 329 return a->sym != b->sym; 330 } 331 332 /* 333 * Return 1 if "dom" dominates the access to "pseudo" 334 * in "insn". 335 * 336 * Return 0 if it doesn't, and -1 if you don't know. 337 */ 338 int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom, int local) 339 { 340 int opcode = dom->opcode; 341 342 if (opcode == OP_CALL || opcode == OP_ENTRY) 343 return local ? 0 : -1; 344 if (opcode != OP_LOAD && opcode != OP_STORE) 345 return 0; 346 if (dom->src != pseudo) { 347 if (local) 348 return 0; 349 /* We don't think two explicitly different symbols ever alias */ 350 if (distinct_symbols(insn->src, dom->src)) 351 return 0; 352 /* We could try to do some alias analysis here */ 353 return -1; 354 } 355 if (!same_memop(insn, dom)) { 356 if (dom->opcode == OP_LOAD) 357 return 0; 358 if (!overlapping_memop(insn, dom)) 359 return 0; 360 return -1; 361 } 362 return 1; 363 } 364 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 /* 426 * We should probably sort the phi list just to make it easier to compare 427 * later for equality. 428 */ 429 void rewrite_load_instruction(struct instruction *insn, struct pseudo_list *dominators) 430 { 431 pseudo_t new, phi; 432 433 /* 434 * Check for somewhat common case of duplicate 435 * phi nodes. 436 */ 437 new = first_pseudo(dominators)->def->src1; 438 FOR_EACH_PTR(dominators, phi) { 439 if (new != phi->def->src1) 440 goto complex_phi; 441 new->ident = new->ident ? : phi->ident; 442 } END_FOR_EACH_PTR(phi); 443 444 /* 445 * All the same pseudo - mark the phi-nodes unused 446 * and convert the load into a LNOP and replace the 447 * pseudo. 448 */ 449 FOR_EACH_PTR(dominators, phi) { 450 kill_instruction(phi->def); 451 } END_FOR_EACH_PTR(phi); 452 convert_load_instruction(insn, new); 453 return; 454 455 complex_phi: 456 /* We leave symbol pseudos with a bogus usage list here */ 457 if (insn->src->type != PSEUDO_SYM) 458 kill_use(&insn->src); 459 insn->opcode = OP_PHI; 460 insn->phi_list = dominators; 461 } 462 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; 532 } 533 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 /* 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) 545 { 546 struct instruction *insn; 547 struct basic_block *parent; 548 549 if (bb->generation == generation) 550 return; 551 bb->generation = generation; 552 FOR_EACH_PTR_REVERSE(bb->insns, insn) { 553 int opcode = insn->opcode; 554 555 if (opcode != OP_LOAD && opcode != OP_STORE) { 556 if (local) 557 continue; 558 if (opcode == OP_CALL) 559 return; 560 continue; 561 } 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) 571 return; 572 } END_FOR_EACH_PTR_REVERSE(insn); 573 574 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; 608 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); 632 } END_FOR_EACH_PTR(parent); 633 } 634 635 void check_access(struct instruction *insn) 636 { 637 pseudo_t pseudo = insn->src; 638 639 if (insn->bb && pseudo->type == PSEUDO_SYM) { 640 int offset = insn->offset, bit = bytes_to_bits(offset) + insn->size; 641 struct symbol *sym = pseudo->sym; 642 643 if (sym->bit_size > 0 && (offset < 0 || bit > sym->bit_size)) 644 warning(insn->pos, "invalid access %s '%s' (%d %d)", 645 offset < 0 ? "below" : "past the end of", 646 show_ident(sym->ident), offset, 647 bits_to_bytes(sym->bit_size)); 648 } 649 } 650 651 static void simplify_one_symbol(struct entrypoint *ep, struct symbol *sym) 652 { 653 pseudo_t pseudo; 654 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: 690 continue; 691 default: 692 warning(sym->pos, "symbol '%s' pseudo used in unexpected way", show_ident(sym->ident)); 693 } 694 } END_FOR_EACH_PTR(pu); 695 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); 703 704 /* If we converted all the loads, remove the stores. They are dead */ 705 if (all && !mod) { 706 FOR_EACH_PTR(pseudo->users, pu) { 707 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); 728 } 729 } 730 731 return; 732 } 733 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); 741 } 742 743 static void mark_bb_reachable(struct basic_block *bb, unsigned long generation) 744 { 745 struct basic_block *child; 746 747 if (bb->generation == generation) 748 return; 749 bb->generation = generation; 750 FOR_EACH_PTR(bb->children, child) { 751 mark_bb_reachable(child, generation); 752 } END_FOR_EACH_PTR(child); 753 } 754 755 static void kill_defs(struct instruction *insn) 756 { 757 pseudo_t target = insn->target; 758 759 if (!has_use_list(target)) 760 return; 761 if (target->def != insn) 762 return; 763 764 convert_instruction_target(insn, VOID); 765 } 766 767 void kill_bb(struct basic_block *bb) 768 { 769 struct instruction *insn; 770 struct basic_block *child, *parent; 771 772 FOR_EACH_PTR(bb->insns, insn) { 773 kill_instruction_force(insn); 774 kill_defs(insn); 775 /* 776 * We kill unreachable instructions even if they 777 * otherwise aren't "killable" (e.g. volatile loads) 778 */ 779 } END_FOR_EACH_PTR(insn); 780 bb->insns = NULL; 781 782 FOR_EACH_PTR(bb->children, child) { 783 remove_bb_from_list(&child->parents, bb, 0); 784 } END_FOR_EACH_PTR(child); 785 bb->children = NULL; 786 787 FOR_EACH_PTR(bb->parents, parent) { 788 remove_bb_from_list(&parent->children, bb, 0); 789 } END_FOR_EACH_PTR(parent); 790 bb->parents = NULL; 791 } 792 793 void kill_unreachable_bbs(struct entrypoint *ep) 794 { 795 struct basic_block *bb; 796 unsigned long generation = ++bb_generation; 797 798 mark_bb_reachable(ep->entry->bb, generation); 799 FOR_EACH_PTR(ep->bbs, bb) { 800 if (bb->generation == generation) 801 continue; 802 /* Mark it as being dead */ 803 kill_bb(bb); 804 bb->ep = NULL; 805 DELETE_CURRENT_PTR(bb); 806 } END_FOR_EACH_PTR(bb); 807 PACK_PTR_LIST(&ep->bbs); 808 } 809 810 static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new) 811 { 812 int changed = 0; 813 struct instruction *insn = last_instruction(bb->insns); 814 815 if (!insn) 816 return 0; 817 818 /* Infinite loops: let's not "optimize" them.. */ 819 if (old == new) 820 return 0; 821 822 switch (insn->opcode) { 823 case OP_CBR: 824 changed |= rewrite_branch(bb, &insn->bb_false, old, new); 825 /* fall through */ 826 case OP_BR: 827 changed |= rewrite_branch(bb, &insn->bb_true, old, new); 828 assert(changed); 829 return changed; 830 case OP_SWITCH: { 831 struct multijmp *jmp; 832 FOR_EACH_PTR(insn->multijmp_list, jmp) { 833 changed |= rewrite_branch(bb, &jmp->target, old, new); 834 } END_FOR_EACH_PTR(jmp); 835 assert(changed); 836 return changed; 837 } 838 default: 839 return 0; 840 } 841 } 842 843 static struct basic_block * rewrite_branch_bb(struct basic_block *bb, struct instruction *br) 844 { 845 struct basic_block *parent; 846 struct basic_block *target = br->bb_true; 847 struct basic_block *false = br->bb_false; 848 849 if (br->opcode == OP_CBR) { 850 pseudo_t cond = br->cond; 851 if (cond->type != PSEUDO_VAL) 852 return NULL; 853 target = cond->value ? target : false; 854 } 855 856 /* 857 * We can't do FOR_EACH_PTR() here, because the parent list 858 * may change when we rewrite the parent. 859 */ 860 while ((parent = first_basic_block(bb->parents)) != NULL) { 861 if (!rewrite_parent_branch(parent, bb, target)) 862 return NULL; 863 } 864 return target; 865 } 866 867 static void vrfy_bb_in_list(struct basic_block *bb, struct basic_block_list *list) 868 { 869 if (bb) { 870 struct basic_block *tmp; 871 int no_bb_in_list = 0; 872 873 FOR_EACH_PTR(list, tmp) { 874 if (bb == tmp) 875 return; 876 } END_FOR_EACH_PTR(tmp); 877 assert(no_bb_in_list); 878 } 879 } 880 881 static void vrfy_parents(struct basic_block *bb) 882 { 883 struct basic_block *tmp; 884 FOR_EACH_PTR(bb->parents, tmp) { 885 vrfy_bb_in_list(bb, tmp->children); 886 } END_FOR_EACH_PTR(tmp); 887 } 888 889 static void vrfy_children(struct basic_block *bb) 890 { 891 struct basic_block *tmp; 892 struct instruction *br = last_instruction(bb->insns); 893 894 if (!br) { 895 assert(!bb->children); 896 return; 897 } 898 switch (br->opcode) { 899 struct multijmp *jmp; 900 case OP_CBR: 901 vrfy_bb_in_list(br->bb_false, bb->children); 902 /* fall through */ 903 case OP_BR: 904 vrfy_bb_in_list(br->bb_true, bb->children); 905 break; 906 case OP_SWITCH: 907 case OP_COMPUTEDGOTO: 908 FOR_EACH_PTR(br->multijmp_list, jmp) { 909 vrfy_bb_in_list(jmp->target, bb->children); 910 } END_FOR_EACH_PTR(jmp); 911 break; 912 default: 913 break; 914 } 915 916 FOR_EACH_PTR(bb->children, tmp) { 917 vrfy_bb_in_list(bb, tmp->parents); 918 } END_FOR_EACH_PTR(tmp); 919 } 920 921 static void vrfy_bb_flow(struct basic_block *bb) 922 { 923 vrfy_children(bb); 924 vrfy_parents(bb); 925 } 926 927 void vrfy_flow(struct entrypoint *ep) 928 { 929 struct basic_block *bb; 930 struct basic_block *entry = ep->entry->bb; 931 932 FOR_EACH_PTR(ep->bbs, bb) { 933 if (bb == entry) 934 entry = NULL; 935 vrfy_bb_flow(bb); 936 } END_FOR_EACH_PTR(bb); 937 assert(!entry); 938 } 939 940 void pack_basic_blocks(struct entrypoint *ep) 941 { 942 struct basic_block *bb; 943 944 /* See if we can merge a bb into another one.. */ 945 FOR_EACH_PTR(ep->bbs, bb) { 946 struct instruction *first, *insn; 947 struct basic_block *parent, *child, *last; 948 949 if (!bb_reachable(bb)) 950 continue; 951 952 /* 953 * Just a branch? 954 */ 955 FOR_EACH_PTR(bb->insns, first) { 956 if (!first->bb) 957 continue; 958 switch (first->opcode) { 959 case OP_NOP: case OP_LNOP: case OP_SNOP: 960 continue; 961 case OP_CBR: 962 case OP_BR: { 963 struct basic_block *replace; 964 replace = rewrite_branch_bb(bb, first); 965 if (replace) { 966 kill_bb(bb); 967 goto no_merge; 968 } 969 } 970 /* fallthrough */ 971 default: 972 goto out; 973 } 974 } END_FOR_EACH_PTR(first); 975 976 out: 977 /* 978 * See if we only have one parent.. 979 */ 980 last = NULL; 981 FOR_EACH_PTR(bb->parents, parent) { 982 if (last) { 983 if (last != parent) 984 goto no_merge; 985 continue; 986 } 987 last = parent; 988 } END_FOR_EACH_PTR(parent); 989 990 parent = last; 991 if (!parent || parent == bb) 992 continue; 993 994 /* 995 * Goodie. See if the parent can merge.. 996 */ 997 FOR_EACH_PTR(parent->children, child) { 998 if (child != bb) 999 goto no_merge; 1000 } END_FOR_EACH_PTR(child); 1001 1002 /* 1003 * Merge the two. 1004 */ 1005 repeat_phase |= REPEAT_CSE; 1006 1007 parent->children = bb->children; 1008 bb->children = NULL; 1009 bb->parents = NULL; 1010 1011 FOR_EACH_PTR(parent->children, child) { 1012 replace_bb_in_list(&child->parents, bb, parent, 0); 1013 } END_FOR_EACH_PTR(child); 1014 1015 kill_instruction(delete_last_instruction(&parent->insns)); 1016 FOR_EACH_PTR(bb->insns, insn) { 1017 if (insn->bb) { 1018 assert(insn->bb == bb); 1019 insn->bb = parent; 1020 } 1021 add_instruction(&parent->insns, insn); 1022 } END_FOR_EACH_PTR(insn); 1023 bb->insns = NULL; 1024 1025 no_merge: 1026 /* nothing to do */; 1027 } END_FOR_EACH_PTR(bb); 1028 } 1029 1030 1031