cfgrtl.c revision 90075
1/* Control flow graph manipulation code for GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22/* This file contains low level functions to manipulate the CFG and analyze it 23 that are aware of the RTL intermediate language. 24 25 Available functionality: 26 - CFG-aware instruction chain manipulation 27 delete_insn, delete_insn_chain 28 - Basic block manipulation 29 create_basic_block, flow_delete_block, split_block, 30 merge_blocks_nomove 31 - Infrastructure to determine quickly basic block for insn 32 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn, 33 - Edge redirection with updating and optimizing of insn chain 34 block_label, redirect_edge_and_branch, 35 redirect_edge_and_branch_force, tidy_fallthru_edge, force_nonfallthru 36 - Edge splitting and commiting to edges 37 split_edge, insert_insn_on_edge, commit_edge_insertions 38 - Dumping and debugging 39 print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n 40 - Consistency checking 41 verify_flow_info 42 - CFG updating after constant propagation 43 purge_dead_edges, purge_all_dead_edges */ 44 45#include "config.h" 46#include "system.h" 47#include "tree.h" 48#include "rtl.h" 49#include "hard-reg-set.h" 50#include "basic-block.h" 51#include "regs.h" 52#include "flags.h" 53#include "output.h" 54#include "function.h" 55#include "except.h" 56#include "toplev.h" 57#include "tm_p.h" 58#include "obstack.h" 59 60/* Stubs in case we don't have a return insn. */ 61#ifndef HAVE_return 62#define HAVE_return 0 63#define gen_return() NULL_RTX 64#endif 65 66/* The basic block structure for every insn, indexed by uid. */ 67varray_type basic_block_for_insn; 68 69/* The labels mentioned in non-jump rtl. Valid during find_basic_blocks. */ 70/* ??? Should probably be using LABEL_NUSES instead. It would take a 71 bit of surgery to be able to use or co-opt the routines in jump. */ 72rtx label_value_list; 73rtx tail_recursion_label_list; 74 75static int can_delete_note_p PARAMS ((rtx)); 76static int can_delete_label_p PARAMS ((rtx)); 77static void commit_one_edge_insertion PARAMS ((edge)); 78static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block)); 79static rtx last_loop_beg_note PARAMS ((rtx)); 80static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block)); 81static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block)); 82 83/* Return true if NOTE is not one of the ones that must be kept paired, 84 so that we may simply delete it. */ 85 86static int 87can_delete_note_p (note) 88 rtx note; 89{ 90 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED 91 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK); 92} 93 94/* True if a given label can be deleted. */ 95 96static int 97can_delete_label_p (label) 98 rtx label; 99{ 100 return (!LABEL_PRESERVE_P (label) 101 /* User declared labels must be preserved. */ 102 && LABEL_NAME (label) == 0 103 && !in_expr_list_p (forced_labels, label) 104 && !in_expr_list_p (label_value_list, label) 105 && !in_expr_list_p (exception_handler_labels, label)); 106} 107 108/* Delete INSN by patching it out. Return the next insn. */ 109 110rtx 111delete_insn (insn) 112 rtx insn; 113{ 114 rtx next = NEXT_INSN (insn); 115 rtx note; 116 bool really_delete = true; 117 118 if (GET_CODE (insn) == CODE_LABEL) 119 { 120 /* Some labels can't be directly removed from the INSN chain, as they 121 might be references via variables, constant pool etc. 122 Convert them to the special NOTE_INSN_DELETED_LABEL note. */ 123 if (! can_delete_label_p (insn)) 124 { 125 const char *name = LABEL_NAME (insn); 126 127 really_delete = false; 128 PUT_CODE (insn, NOTE); 129 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL; 130 NOTE_SOURCE_FILE (insn) = name; 131 } 132 133 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels); 134 } 135 136 if (really_delete) 137 { 138 /* If this insn has already been deleted, something is very wrong. */ 139 if (INSN_DELETED_P (insn)) 140 abort (); 141 remove_insn (insn); 142 INSN_DELETED_P (insn) = 1; 143 } 144 145 /* If deleting a jump, decrement the use count of the label. Deleting 146 the label itself should happen in the normal course of block merging. */ 147 if (GET_CODE (insn) == JUMP_INSN 148 && JUMP_LABEL (insn) 149 && GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL) 150 LABEL_NUSES (JUMP_LABEL (insn))--; 151 152 /* Also if deleting an insn that references a label. */ 153 else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX 154 && GET_CODE (XEXP (note, 0)) == CODE_LABEL) 155 LABEL_NUSES (XEXP (note, 0))--; 156 157 if (GET_CODE (insn) == JUMP_INSN 158 && (GET_CODE (PATTERN (insn)) == ADDR_VEC 159 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 160 { 161 rtx pat = PATTERN (insn); 162 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC; 163 int len = XVECLEN (pat, diff_vec_p); 164 int i; 165 166 for (i = 0; i < len; i++) 167 { 168 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0); 169 170 /* When deleting code in bulk (e.g. removing many unreachable 171 blocks) we can delete a label that's a target of the vector 172 before deleting the vector itself. */ 173 if (GET_CODE (label) != NOTE) 174 LABEL_NUSES (label)--; 175 } 176 } 177 178 return next; 179} 180 181/* Unlink a chain of insns between START and FINISH, leaving notes 182 that must be paired. */ 183 184void 185delete_insn_chain (start, finish) 186 rtx start, finish; 187{ 188 rtx next; 189 190 /* Unchain the insns one by one. It would be quicker to delete all of these 191 with a single unchaining, rather than one at a time, but we need to keep 192 the NOTE's. */ 193 while (1) 194 { 195 next = NEXT_INSN (start); 196 if (GET_CODE (start) == NOTE && !can_delete_note_p (start)) 197 ; 198 else 199 next = delete_insn (start); 200 201 if (start == finish) 202 break; 203 start = next; 204 } 205} 206 207/* Create a new basic block consisting of the instructions between HEAD and END 208 inclusive. This function is designed to allow fast BB construction - reuses 209 the note and basic block struct in BB_NOTE, if any and do not grow 210 BASIC_BLOCK chain and should be used directly only by CFG construction code. 211 END can be NULL in to create new empty basic block before HEAD. Both END 212 and HEAD can be NULL to create basic block at the end of INSN chain. */ 213 214basic_block 215create_basic_block_structure (index, head, end, bb_note) 216 int index; 217 rtx head, end, bb_note; 218{ 219 basic_block bb; 220 221 if (bb_note 222 && ! RTX_INTEGRATED_P (bb_note) 223 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL 224 && bb->aux == NULL) 225 { 226 /* If we found an existing note, thread it back onto the chain. */ 227 228 rtx after; 229 230 if (GET_CODE (head) == CODE_LABEL) 231 after = head; 232 else 233 { 234 after = PREV_INSN (head); 235 head = bb_note; 236 } 237 238 if (after != bb_note && NEXT_INSN (after) != bb_note) 239 reorder_insns (bb_note, bb_note, after); 240 } 241 else 242 { 243 /* Otherwise we must create a note and a basic block structure. */ 244 245 bb = alloc_block (); 246 247 if (!head && !end) 248 head = end = bb_note 249 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); 250 else if (GET_CODE (head) == CODE_LABEL && end) 251 { 252 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); 253 if (head == end) 254 end = bb_note; 255 } 256 else 257 { 258 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head); 259 head = bb_note; 260 if (!end) 261 end = head; 262 } 263 264 NOTE_BASIC_BLOCK (bb_note) = bb; 265 } 266 267 /* Always include the bb note in the block. */ 268 if (NEXT_INSN (end) == bb_note) 269 end = bb_note; 270 271 bb->head = head; 272 bb->end = end; 273 bb->index = index; 274 BASIC_BLOCK (index) = bb; 275 if (basic_block_for_insn) 276 update_bb_for_insn (bb); 277 278 /* Tag the block so that we know it has been used when considering 279 other basic block notes. */ 280 bb->aux = bb; 281 282 return bb; 283} 284 285/* Create new basic block consisting of instructions in between HEAD and END 286 and place it to the BB chain at position INDEX. END can be NULL in to 287 create new empty basic block before HEAD. Both END and HEAD can be NULL to 288 create basic block at the end of INSN chain. */ 289 290basic_block 291create_basic_block (index, head, end) 292 int index; 293 rtx head, end; 294{ 295 basic_block bb; 296 int i; 297 298 /* Place the new block just after the block being split. */ 299 VARRAY_GROW (basic_block_info, ++n_basic_blocks); 300 301 /* Some parts of the compiler expect blocks to be number in 302 sequential order so insert the new block immediately after the 303 block being split.. */ 304 for (i = n_basic_blocks - 1; i > index; --i) 305 { 306 basic_block tmp = BASIC_BLOCK (i - 1); 307 308 BASIC_BLOCK (i) = tmp; 309 tmp->index = i; 310 } 311 312 bb = create_basic_block_structure (index, head, end, NULL); 313 bb->aux = NULL; 314 return bb; 315} 316 317/* Delete the insns in a (non-live) block. We physically delete every 318 non-deleted-note insn, and update the flow graph appropriately. 319 320 Return nonzero if we deleted an exception handler. */ 321 322/* ??? Preserving all such notes strikes me as wrong. It would be nice 323 to post-process the stream to remove empty blocks, loops, ranges, etc. */ 324 325int 326flow_delete_block (b) 327 basic_block b; 328{ 329 int deleted_handler = 0; 330 rtx insn, end, tmp; 331 332 /* If the head of this block is a CODE_LABEL, then it might be the 333 label for an exception handler which can't be reached. 334 335 We need to remove the label from the exception_handler_label list 336 and remove the associated NOTE_INSN_EH_REGION_BEG and 337 NOTE_INSN_EH_REGION_END notes. */ 338 339 insn = b->head; 340 341 never_reached_warning (insn); 342 343 if (GET_CODE (insn) == CODE_LABEL) 344 maybe_remove_eh_handler (insn); 345 346 /* Include any jump table following the basic block. */ 347 end = b->end; 348 if (GET_CODE (end) == JUMP_INSN 349 && (tmp = JUMP_LABEL (end)) != NULL_RTX 350 && (tmp = NEXT_INSN (tmp)) != NULL_RTX 351 && GET_CODE (tmp) == JUMP_INSN 352 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC 353 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) 354 end = tmp; 355 356 /* Include any barrier that may follow the basic block. */ 357 tmp = next_nonnote_insn (end); 358 if (tmp && GET_CODE (tmp) == BARRIER) 359 end = tmp; 360 361 /* Selectively delete the entire chain. */ 362 b->head = NULL; 363 delete_insn_chain (insn, end); 364 365 /* Remove the edges into and out of this block. Note that there may 366 indeed be edges in, if we are removing an unreachable loop. */ 367 while (b->pred != NULL) 368 remove_edge (b->pred); 369 while (b->succ != NULL) 370 remove_edge (b->succ); 371 372 b->pred = NULL; 373 b->succ = NULL; 374 375 /* Remove the basic block from the array, and compact behind it. */ 376 expunge_block (b); 377 378 return deleted_handler; 379} 380 381/* Records the basic block struct in BB_FOR_INSN, for every instruction 382 indexed by INSN_UID. MAX is the size of the array. */ 383 384void 385compute_bb_for_insn (max) 386 int max; 387{ 388 int i; 389 390 if (basic_block_for_insn) 391 VARRAY_FREE (basic_block_for_insn); 392 393 VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn"); 394 395 for (i = 0; i < n_basic_blocks; ++i) 396 { 397 basic_block bb = BASIC_BLOCK (i); 398 rtx end = bb->end; 399 rtx insn; 400 401 for (insn = bb->head; ; insn = NEXT_INSN (insn)) 402 { 403 if (INSN_UID (insn) < max) 404 VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb; 405 406 if (insn == end) 407 break; 408 } 409 } 410} 411 412/* Release the basic_block_for_insn array. */ 413 414void 415free_bb_for_insn () 416{ 417 if (basic_block_for_insn) 418 VARRAY_FREE (basic_block_for_insn); 419 420 basic_block_for_insn = 0; 421} 422 423/* Update insns block within BB. */ 424 425void 426update_bb_for_insn (bb) 427 basic_block bb; 428{ 429 rtx insn; 430 431 if (! basic_block_for_insn) 432 return; 433 434 for (insn = bb->head; ; insn = NEXT_INSN (insn)) 435 { 436 set_block_for_insn (insn, bb); 437 if (insn == bb->end) 438 break; 439 } 440} 441 442/* Record INSN's block as BB. */ 443 444void 445set_block_for_insn (insn, bb) 446 rtx insn; 447 basic_block bb; 448{ 449 size_t uid = INSN_UID (insn); 450 451 if (uid >= basic_block_for_insn->num_elements) 452 { 453 /* Add one-eighth the size so we don't keep calling xrealloc. */ 454 size_t new_size = uid + (uid + 7) / 8; 455 456 VARRAY_GROW (basic_block_for_insn, new_size); 457 } 458 459 VARRAY_BB (basic_block_for_insn, uid) = bb; 460} 461 462/* Split a block BB after insn INSN creating a new fallthru edge. 463 Return the new edge. Note that to keep other parts of the compiler happy, 464 this function renumbers all the basic blocks so that the new 465 one has a number one greater than the block split. */ 466 467edge 468split_block (bb, insn) 469 basic_block bb; 470 rtx insn; 471{ 472 basic_block new_bb; 473 edge new_edge; 474 edge e; 475 476 /* There is no point splitting the block after its end. */ 477 if (bb->end == insn) 478 return 0; 479 480 /* Create the new basic block. */ 481 new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end); 482 new_bb->count = bb->count; 483 new_bb->frequency = bb->frequency; 484 new_bb->loop_depth = bb->loop_depth; 485 bb->end = insn; 486 487 /* Redirect the outgoing edges. */ 488 new_bb->succ = bb->succ; 489 bb->succ = NULL; 490 for (e = new_bb->succ; e; e = e->succ_next) 491 e->src = new_bb; 492 493 new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU); 494 495 if (bb->global_live_at_start) 496 { 497 new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); 498 new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); 499 COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end); 500 501 /* We now have to calculate which registers are live at the end 502 of the split basic block and at the start of the new basic 503 block. Start with those registers that are known to be live 504 at the end of the original basic block and get 505 propagate_block to determine which registers are live. */ 506 COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end); 507 propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0); 508 COPY_REG_SET (bb->global_live_at_end, 509 new_bb->global_live_at_start); 510 } 511 512 return new_edge; 513} 514 515/* Blocks A and B are to be merged into a single block A. The insns 516 are already contiguous, hence `nomove'. */ 517 518void 519merge_blocks_nomove (a, b) 520 basic_block a, b; 521{ 522 rtx b_head = b->head, b_end = b->end, a_end = a->end; 523 rtx del_first = NULL_RTX, del_last = NULL_RTX; 524 int b_empty = 0; 525 edge e; 526 527 /* If there was a CODE_LABEL beginning B, delete it. */ 528 if (GET_CODE (b_head) == CODE_LABEL) 529 { 530 /* Detect basic blocks with nothing but a label. This can happen 531 in particular at the end of a function. */ 532 if (b_head == b_end) 533 b_empty = 1; 534 535 del_first = del_last = b_head; 536 b_head = NEXT_INSN (b_head); 537 } 538 539 /* Delete the basic block note and handle blocks containing just that 540 note. */ 541 if (NOTE_INSN_BASIC_BLOCK_P (b_head)) 542 { 543 if (b_head == b_end) 544 b_empty = 1; 545 if (! del_last) 546 del_first = b_head; 547 548 del_last = b_head; 549 b_head = NEXT_INSN (b_head); 550 } 551 552 /* If there was a jump out of A, delete it. */ 553 if (GET_CODE (a_end) == JUMP_INSN) 554 { 555 rtx prev; 556 557 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev)) 558 if (GET_CODE (prev) != NOTE 559 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK 560 || prev == a->head) 561 break; 562 563 del_first = a_end; 564 565#ifdef HAVE_cc0 566 /* If this was a conditional jump, we need to also delete 567 the insn that set cc0. */ 568 if (only_sets_cc0_p (prev)) 569 { 570 rtx tmp = prev; 571 572 prev = prev_nonnote_insn (prev); 573 if (!prev) 574 prev = a->head; 575 del_first = tmp; 576 } 577#endif 578 579 a_end = PREV_INSN (del_first); 580 } 581 else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER) 582 del_first = NEXT_INSN (a_end); 583 584 /* Normally there should only be one successor of A and that is B, but 585 partway though the merge of blocks for conditional_execution we'll 586 be merging a TEST block with THEN and ELSE successors. Free the 587 whole lot of them and hope the caller knows what they're doing. */ 588 while (a->succ) 589 remove_edge (a->succ); 590 591 /* Adjust the edges out of B for the new owner. */ 592 for (e = b->succ; e; e = e->succ_next) 593 e->src = a; 594 a->succ = b->succ; 595 596 /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */ 597 b->pred = b->succ = NULL; 598 a->global_live_at_end = b->global_live_at_end; 599 600 expunge_block (b); 601 602 /* Delete everything marked above as well as crap that might be 603 hanging out between the two blocks. */ 604 delete_insn_chain (del_first, del_last); 605 606 /* Reassociate the insns of B with A. */ 607 if (!b_empty) 608 { 609 if (basic_block_for_insn) 610 { 611 rtx x; 612 613 for (x = a_end; x != b_end; x = NEXT_INSN (x)) 614 BLOCK_FOR_INSN (x) = a; 615 616 BLOCK_FOR_INSN (b_end) = a; 617 } 618 619 a_end = b_end; 620 } 621 622 a->end = a_end; 623} 624 625/* Return the label in the head of basic block BLOCK. Create one if it doesn't 626 exist. */ 627 628rtx 629block_label (block) 630 basic_block block; 631{ 632 if (block == EXIT_BLOCK_PTR) 633 return NULL_RTX; 634 635 if (GET_CODE (block->head) != CODE_LABEL) 636 { 637 block->head = emit_label_before (gen_label_rtx (), block->head); 638 if (basic_block_for_insn) 639 set_block_for_insn (block->head, block); 640 } 641 642 return block->head; 643} 644 645/* Attempt to perform edge redirection by replacing possibly complex jump 646 instruction by unconditional jump or removing jump completely. This can 647 apply only if all edges now point to the same block. The parameters and 648 return values are equivalent to redirect_edge_and_branch. */ 649 650static bool 651try_redirect_by_replacing_jump (e, target) 652 edge e; 653 basic_block target; 654{ 655 basic_block src = e->src; 656 rtx insn = src->end, kill_from; 657 edge tmp; 658 rtx set; 659 int fallthru = 0; 660 661 /* Verify that all targets will be TARGET. */ 662 for (tmp = src->succ; tmp; tmp = tmp->succ_next) 663 if (tmp->dest != target && tmp != e) 664 break; 665 666 if (tmp || !onlyjump_p (insn)) 667 return false; 668 669 /* Avoid removing branch with side effects. */ 670 set = single_set (insn); 671 if (!set || side_effects_p (set)) 672 return false; 673 674 /* In case we zap a conditional jump, we'll need to kill 675 the cc0 setter too. */ 676 kill_from = insn; 677#ifdef HAVE_cc0 678 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))) 679 kill_from = PREV_INSN (insn); 680#endif 681 682 /* See if we can create the fallthru edge. */ 683 if (can_fallthru (src, target)) 684 { 685 if (rtl_dump_file) 686 fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn)); 687 fallthru = 1; 688 689 /* Selectively unlink whole insn chain. */ 690 delete_insn_chain (kill_from, PREV_INSN (target->head)); 691 } 692 693 /* If this already is simplejump, redirect it. */ 694 else if (simplejump_p (insn)) 695 { 696 if (e->dest == target) 697 return false; 698 if (rtl_dump_file) 699 fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n", 700 INSN_UID (insn), e->dest->index, target->index); 701 if (!redirect_jump (insn, block_label (target), 0)) 702 { 703 if (target == EXIT_BLOCK_PTR) 704 return false; 705 abort (); 706 } 707 } 708 709 /* Cannot do anything for target exit block. */ 710 else if (target == EXIT_BLOCK_PTR) 711 return false; 712 713 /* Or replace possibly complicated jump insn by simple jump insn. */ 714 else 715 { 716 rtx target_label = block_label (target); 717 rtx barrier; 718 719 emit_jump_insn_after (gen_jump (target_label), insn); 720 JUMP_LABEL (src->end) = target_label; 721 LABEL_NUSES (target_label)++; 722 if (rtl_dump_file) 723 fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n", 724 INSN_UID (insn), INSN_UID (src->end)); 725 726 delete_insn_chain (kill_from, insn); 727 728 barrier = next_nonnote_insn (src->end); 729 if (!barrier || GET_CODE (barrier) != BARRIER) 730 emit_barrier_after (src->end); 731 } 732 733 /* Keep only one edge out and set proper flags. */ 734 while (src->succ->succ_next) 735 remove_edge (src->succ); 736 e = src->succ; 737 if (fallthru) 738 e->flags = EDGE_FALLTHRU; 739 else 740 e->flags = 0; 741 742 e->probability = REG_BR_PROB_BASE; 743 e->count = src->count; 744 745 /* We don't want a block to end on a line-number note since that has 746 the potential of changing the code between -g and not -g. */ 747 while (GET_CODE (e->src->end) == NOTE 748 && NOTE_LINE_NUMBER (e->src->end) >= 0) 749 delete_insn (e->src->end); 750 751 if (e->dest != target) 752 redirect_edge_succ (e, target); 753 754 return true; 755} 756 757/* Return last loop_beg note appearing after INSN, before start of next 758 basic block. Return INSN if there are no such notes. 759 760 When emitting jump to redirect an fallthru edge, it should always appear 761 after the LOOP_BEG notes, as loop optimizer expect loop to either start by 762 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit 763 test. */ 764 765static rtx 766last_loop_beg_note (insn) 767 rtx insn; 768{ 769 rtx last = insn; 770 771 for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE 772 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; 773 insn = NEXT_INSN (insn)) 774 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 775 last = insn; 776 777 return last; 778} 779 780/* Attempt to change code to redirect edge E to TARGET. Don't do that on 781 expense of adding new instructions or reordering basic blocks. 782 783 Function can be also called with edge destination equivalent to the TARGET. 784 Then it should try the simplifications and do nothing if none is possible. 785 786 Return true if transformation succeeded. We still return false in case E 787 already destinated TARGET and we didn't managed to simplify instruction 788 stream. */ 789 790bool 791redirect_edge_and_branch (e, target) 792 edge e; 793 basic_block target; 794{ 795 rtx tmp; 796 rtx old_label = e->dest->head; 797 basic_block src = e->src; 798 rtx insn = src->end; 799 800 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 801 return false; 802 803 if (try_redirect_by_replacing_jump (e, target)) 804 return true; 805 806 /* Do this fast path late, as we want above code to simplify for cases 807 where called on single edge leaving basic block containing nontrivial 808 jump insn. */ 809 else if (e->dest == target) 810 return false; 811 812 /* We can only redirect non-fallthru edges of jump insn. */ 813 if (e->flags & EDGE_FALLTHRU) 814 return false; 815 else if (GET_CODE (insn) != JUMP_INSN) 816 return false; 817 818 /* Recognize a tablejump and adjust all matching cases. */ 819 if ((tmp = JUMP_LABEL (insn)) != NULL_RTX 820 && (tmp = NEXT_INSN (tmp)) != NULL_RTX 821 && GET_CODE (tmp) == JUMP_INSN 822 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC 823 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) 824 { 825 rtvec vec; 826 int j; 827 rtx new_label = block_label (target); 828 829 if (target == EXIT_BLOCK_PTR) 830 return false; 831 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) 832 vec = XVEC (PATTERN (tmp), 0); 833 else 834 vec = XVEC (PATTERN (tmp), 1); 835 836 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 837 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label) 838 { 839 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label); 840 --LABEL_NUSES (old_label); 841 ++LABEL_NUSES (new_label); 842 } 843 844 /* Handle casesi dispatch insns */ 845 if ((tmp = single_set (insn)) != NULL 846 && SET_DEST (tmp) == pc_rtx 847 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 848 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF 849 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label) 850 { 851 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode, 852 new_label); 853 --LABEL_NUSES (old_label); 854 ++LABEL_NUSES (new_label); 855 } 856 } 857 else 858 { 859 /* ?? We may play the games with moving the named labels from 860 one basic block to the other in case only one computed_jump is 861 available. */ 862 if (computed_jump_p (insn) 863 /* A return instruction can't be redirected. */ 864 || returnjump_p (insn)) 865 return false; 866 867 /* If the insn doesn't go where we think, we're confused. */ 868 if (JUMP_LABEL (insn) != old_label) 869 abort (); 870 871 /* If the substitution doesn't succeed, die. This can happen 872 if the back end emitted unrecognizable instructions or if 873 target is exit block on some arches. */ 874 if (!redirect_jump (insn, block_label (target), 0)) 875 { 876 if (target == EXIT_BLOCK_PTR) 877 return false; 878 abort (); 879 } 880 } 881 882 if (rtl_dump_file) 883 fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n", 884 e->src->index, e->dest->index, target->index); 885 886 if (e->dest != target) 887 redirect_edge_succ_nodup (e, target); 888 889 return true; 890} 891 892/* Like force_nonfallthru below, but additionally performs redirection 893 Used by redirect_edge_and_branch_force. */ 894 895static basic_block 896force_nonfallthru_and_redirect (e, target) 897 edge e; 898 basic_block target; 899{ 900 basic_block jump_block, new_bb = NULL; 901 rtx note; 902 edge new_edge; 903 904 if (e->flags & EDGE_ABNORMAL) 905 abort (); 906 else if (!(e->flags & EDGE_FALLTHRU)) 907 abort (); 908 else if (e->src->succ->succ_next) 909 { 910 /* Create the new structures. */ 911 note = last_loop_beg_note (e->src->end); 912 jump_block 913 = create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL); 914 jump_block->count = e->count; 915 jump_block->frequency = EDGE_FREQUENCY (e); 916 jump_block->loop_depth = target->loop_depth; 917 918 if (target->global_live_at_start) 919 { 920 jump_block->global_live_at_start 921 = OBSTACK_ALLOC_REG_SET (&flow_obstack); 922 jump_block->global_live_at_end 923 = OBSTACK_ALLOC_REG_SET (&flow_obstack); 924 COPY_REG_SET (jump_block->global_live_at_start, 925 target->global_live_at_start); 926 COPY_REG_SET (jump_block->global_live_at_end, 927 target->global_live_at_start); 928 } 929 930 /* Wire edge in. */ 931 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU); 932 new_edge->probability = e->probability; 933 new_edge->count = e->count; 934 935 /* Redirect old edge. */ 936 redirect_edge_pred (e, jump_block); 937 e->probability = REG_BR_PROB_BASE; 938 939 new_bb = jump_block; 940 } 941 else 942 jump_block = e->src; 943 944 e->flags &= ~EDGE_FALLTHRU; 945 if (target == EXIT_BLOCK_PTR) 946 { 947 if (HAVE_return) 948 emit_jump_insn_after (gen_return (), jump_block->end); 949 else 950 abort (); 951 } 952 else 953 { 954 rtx label = block_label (target); 955 emit_jump_insn_after (gen_jump (label), jump_block->end); 956 JUMP_LABEL (jump_block->end) = label; 957 LABEL_NUSES (label)++; 958 } 959 960 emit_barrier_after (jump_block->end); 961 redirect_edge_succ_nodup (e, target); 962 963 return new_bb; 964} 965 966/* Edge E is assumed to be fallthru edge. Emit needed jump instruction 967 (and possibly create new basic block) to make edge non-fallthru. 968 Return newly created BB or NULL if none. */ 969 970basic_block 971force_nonfallthru (e) 972 edge e; 973{ 974 return force_nonfallthru_and_redirect (e, e->dest); 975} 976 977/* Redirect edge even at the expense of creating new jump insn or 978 basic block. Return new basic block if created, NULL otherwise. 979 Abort if conversion is impossible. */ 980 981basic_block 982redirect_edge_and_branch_force (e, target) 983 edge e; 984 basic_block target; 985{ 986 if (redirect_edge_and_branch (e, target) 987 || e->dest == target) 988 return NULL; 989 990 /* In case the edge redirection failed, try to force it to be non-fallthru 991 and redirect newly created simplejump. */ 992 return force_nonfallthru_and_redirect (e, target); 993} 994 995/* The given edge should potentially be a fallthru edge. If that is in 996 fact true, delete the jump and barriers that are in the way. */ 997 998void 999tidy_fallthru_edge (e, b, c) 1000 edge e; 1001 basic_block b, c; 1002{ 1003 rtx q; 1004 1005 /* ??? In a late-running flow pass, other folks may have deleted basic 1006 blocks by nopping out blocks, leaving multiple BARRIERs between here 1007 and the target label. They ought to be chastized and fixed. 1008 1009 We can also wind up with a sequence of undeletable labels between 1010 one block and the next. 1011 1012 So search through a sequence of barriers, labels, and notes for 1013 the head of block C and assert that we really do fall through. */ 1014 1015 if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head))) 1016 return; 1017 1018 /* Remove what will soon cease being the jump insn from the source block. 1019 If block B consisted only of this single jump, turn it into a deleted 1020 note. */ 1021 q = b->end; 1022 if (GET_CODE (q) == JUMP_INSN 1023 && onlyjump_p (q) 1024 && (any_uncondjump_p (q) 1025 || (b->succ == e && e->succ_next == NULL))) 1026 { 1027#ifdef HAVE_cc0 1028 /* If this was a conditional jump, we need to also delete 1029 the insn that set cc0. */ 1030 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q))) 1031 q = PREV_INSN (q); 1032#endif 1033 1034 q = PREV_INSN (q); 1035 1036 /* We don't want a block to end on a line-number note since that has 1037 the potential of changing the code between -g and not -g. */ 1038 while (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0) 1039 q = PREV_INSN (q); 1040 } 1041 1042 /* Selectively unlink the sequence. */ 1043 if (q != PREV_INSN (c->head)) 1044 delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head)); 1045 1046 e->flags |= EDGE_FALLTHRU; 1047} 1048 1049/* Fix up edges that now fall through, or rather should now fall through 1050 but previously required a jump around now deleted blocks. Simplify 1051 the search by only examining blocks numerically adjacent, since this 1052 is how find_basic_blocks created them. */ 1053 1054void 1055tidy_fallthru_edges () 1056{ 1057 int i; 1058 1059 for (i = 1; i < n_basic_blocks; i++) 1060 { 1061 basic_block b = BASIC_BLOCK (i - 1); 1062 basic_block c = BASIC_BLOCK (i); 1063 edge s; 1064 1065 /* We care about simple conditional or unconditional jumps with 1066 a single successor. 1067 1068 If we had a conditional branch to the next instruction when 1069 find_basic_blocks was called, then there will only be one 1070 out edge for the block which ended with the conditional 1071 branch (since we do not create duplicate edges). 1072 1073 Furthermore, the edge will be marked as a fallthru because we 1074 merge the flags for the duplicate edges. So we do not want to 1075 check that the edge is not a FALLTHRU edge. */ 1076 1077 if ((s = b->succ) != NULL 1078 && ! (s->flags & EDGE_COMPLEX) 1079 && s->succ_next == NULL 1080 && s->dest == c 1081 /* If the jump insn has side effects, we can't tidy the edge. */ 1082 && (GET_CODE (b->end) != JUMP_INSN 1083 || onlyjump_p (b->end))) 1084 tidy_fallthru_edge (s, b, c); 1085 } 1086} 1087 1088/* Helper function for split_edge. Return true in case edge BB2 to BB1 1089 is back edge of syntactic loop. */ 1090 1091static bool 1092back_edge_of_syntactic_loop_p (bb1, bb2) 1093 basic_block bb1, bb2; 1094{ 1095 rtx insn; 1096 int count = 0; 1097 1098 if (bb1->index > bb2->index) 1099 return false; 1100 else if (bb1->index == bb2->index) 1101 return true; 1102 1103 for (insn = bb1->end; insn != bb2->head && count >= 0; 1104 insn = NEXT_INSN (insn)) 1105 if (GET_CODE (insn) == NOTE) 1106 { 1107 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 1108 count++; 1109 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 1110 count--; 1111 } 1112 1113 return count >= 0; 1114} 1115 1116/* Split a (typically critical) edge. Return the new block. 1117 Abort on abnormal edges. 1118 1119 ??? The code generally expects to be called on critical edges. 1120 The case of a block ending in an unconditional jump to a 1121 block with multiple predecessors is not handled optimally. */ 1122 1123basic_block 1124split_edge (edge_in) 1125 edge edge_in; 1126{ 1127 basic_block bb; 1128 edge edge_out; 1129 rtx before; 1130 1131 /* Abnormal edges cannot be split. */ 1132 if ((edge_in->flags & EDGE_ABNORMAL) != 0) 1133 abort (); 1134 1135 /* We are going to place the new block in front of edge destination. 1136 Avoid existence of fallthru predecessors. */ 1137 if ((edge_in->flags & EDGE_FALLTHRU) == 0) 1138 { 1139 edge e; 1140 1141 for (e = edge_in->dest->pred; e; e = e->pred_next) 1142 if (e->flags & EDGE_FALLTHRU) 1143 break; 1144 1145 if (e) 1146 force_nonfallthru (e); 1147 } 1148 1149 /* Create the basic block note. 1150 1151 Where we place the note can have a noticeable impact on the generated 1152 code. Consider this cfg: 1153 1154 E 1155 | 1156 0 1157 / \ 1158 +->1-->2--->E 1159 | | 1160 +--+ 1161 1162 If we need to insert an insn on the edge from block 0 to block 1, 1163 we want to ensure the instructions we insert are outside of any 1164 loop notes that physically sit between block 0 and block 1. Otherwise 1165 we confuse the loop optimizer into thinking the loop is a phony. */ 1166 1167 if (edge_in->dest != EXIT_BLOCK_PTR 1168 && PREV_INSN (edge_in->dest->head) 1169 && GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE 1170 && (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head)) 1171 == NOTE_INSN_LOOP_BEG) 1172 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src)) 1173 before = PREV_INSN (edge_in->dest->head); 1174 else if (edge_in->dest != EXIT_BLOCK_PTR) 1175 before = edge_in->dest->head; 1176 else 1177 before = NULL_RTX; 1178 1179 bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks 1180 : edge_in->dest->index, before, NULL); 1181 bb->count = edge_in->count; 1182 bb->frequency = EDGE_FREQUENCY (edge_in); 1183 1184 /* ??? This info is likely going to be out of date very soon. */ 1185 if (edge_in->dest->global_live_at_start) 1186 { 1187 bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1188 bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack); 1189 COPY_REG_SET (bb->global_live_at_start, 1190 edge_in->dest->global_live_at_start); 1191 COPY_REG_SET (bb->global_live_at_end, 1192 edge_in->dest->global_live_at_start); 1193 } 1194 1195 edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); 1196 1197 /* For non-fallthry edges, we must adjust the predecessor's 1198 jump instruction to target our new block. */ 1199 if ((edge_in->flags & EDGE_FALLTHRU) == 0) 1200 { 1201 if (!redirect_edge_and_branch (edge_in, bb)) 1202 abort (); 1203 } 1204 else 1205 redirect_edge_succ (edge_in, bb); 1206 1207 return bb; 1208} 1209 1210/* Queue instructions for insertion on an edge between two basic blocks. 1211 The new instructions and basic blocks (if any) will not appear in the 1212 CFG until commit_edge_insertions is called. */ 1213 1214void 1215insert_insn_on_edge (pattern, e) 1216 rtx pattern; 1217 edge e; 1218{ 1219 /* We cannot insert instructions on an abnormal critical edge. 1220 It will be easier to find the culprit if we die now. */ 1221 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) 1222 abort (); 1223 1224 if (e->insns == NULL_RTX) 1225 start_sequence (); 1226 else 1227 push_to_sequence (e->insns); 1228 1229 emit_insn (pattern); 1230 1231 e->insns = get_insns (); 1232 end_sequence (); 1233} 1234 1235/* Update the CFG for the instructions queued on edge E. */ 1236 1237static void 1238commit_one_edge_insertion (e) 1239 edge e; 1240{ 1241 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last; 1242 basic_block bb; 1243 1244 /* Pull the insns off the edge now since the edge might go away. */ 1245 insns = e->insns; 1246 e->insns = NULL_RTX; 1247 1248 /* Figure out where to put these things. If the destination has 1249 one predecessor, insert there. Except for the exit block. */ 1250 if (e->dest->pred->pred_next == NULL 1251 && e->dest != EXIT_BLOCK_PTR) 1252 { 1253 bb = e->dest; 1254 1255 /* Get the location correct wrt a code label, and "nice" wrt 1256 a basic block note, and before everything else. */ 1257 tmp = bb->head; 1258 if (GET_CODE (tmp) == CODE_LABEL) 1259 tmp = NEXT_INSN (tmp); 1260 if (NOTE_INSN_BASIC_BLOCK_P (tmp)) 1261 tmp = NEXT_INSN (tmp); 1262 if (tmp == bb->head) 1263 before = tmp; 1264 else 1265 after = PREV_INSN (tmp); 1266 } 1267 1268 /* If the source has one successor and the edge is not abnormal, 1269 insert there. Except for the entry block. */ 1270 else if ((e->flags & EDGE_ABNORMAL) == 0 1271 && e->src->succ->succ_next == NULL 1272 && e->src != ENTRY_BLOCK_PTR) 1273 { 1274 bb = e->src; 1275 1276 /* It is possible to have a non-simple jump here. Consider a target 1277 where some forms of unconditional jumps clobber a register. This 1278 happens on the fr30 for example. 1279 1280 We know this block has a single successor, so we can just emit 1281 the queued insns before the jump. */ 1282 if (GET_CODE (bb->end) == JUMP_INSN) 1283 for (before = bb->end; 1284 GET_CODE (PREV_INSN (before)) == NOTE 1285 && NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG; 1286 before = PREV_INSN (before)) 1287 ; 1288 else 1289 { 1290 /* We'd better be fallthru, or we've lost track of what's what. */ 1291 if ((e->flags & EDGE_FALLTHRU) == 0) 1292 abort (); 1293 1294 after = bb->end; 1295 } 1296 } 1297 1298 /* Otherwise we must split the edge. */ 1299 else 1300 { 1301 bb = split_edge (e); 1302 after = bb->end; 1303 } 1304 1305 /* Now that we've found the spot, do the insertion. */ 1306 1307 if (before) 1308 { 1309 emit_insns_before (insns, before); 1310 last = prev_nonnote_insn (before); 1311 } 1312 else 1313 last = emit_insns_after (insns, after); 1314 1315 if (returnjump_p (last)) 1316 { 1317 /* ??? Remove all outgoing edges from BB and add one for EXIT. 1318 This is not currently a problem because this only happens 1319 for the (single) epilogue, which already has a fallthru edge 1320 to EXIT. */ 1321 1322 e = bb->succ; 1323 if (e->dest != EXIT_BLOCK_PTR 1324 || e->succ_next != NULL 1325 || (e->flags & EDGE_FALLTHRU) == 0) 1326 abort (); 1327 1328 e->flags &= ~EDGE_FALLTHRU; 1329 emit_barrier_after (last); 1330 1331 if (before) 1332 delete_insn (before); 1333 } 1334 else if (GET_CODE (last) == JUMP_INSN) 1335 abort (); 1336 1337 find_sub_basic_blocks (bb); 1338} 1339 1340/* Update the CFG for all queued instructions. */ 1341 1342void 1343commit_edge_insertions () 1344{ 1345 int i; 1346 basic_block bb; 1347 1348#ifdef ENABLE_CHECKING 1349 verify_flow_info (); 1350#endif 1351 1352 i = -1; 1353 bb = ENTRY_BLOCK_PTR; 1354 while (1) 1355 { 1356 edge e, next; 1357 1358 for (e = bb->succ; e; e = next) 1359 { 1360 next = e->succ_next; 1361 if (e->insns) 1362 commit_one_edge_insertion (e); 1363 } 1364 1365 if (++i >= n_basic_blocks) 1366 break; 1367 bb = BASIC_BLOCK (i); 1368 } 1369} 1370 1371/* Print out one basic block with live information at start and end. */ 1372 1373void 1374dump_bb (bb, outf) 1375 basic_block bb; 1376 FILE *outf; 1377{ 1378 rtx insn; 1379 rtx last; 1380 edge e; 1381 1382 fprintf (outf, ";; Basic block %d, loop depth %d, count ", 1383 bb->index, bb->loop_depth); 1384 fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); 1385 putc ('\n', outf); 1386 1387 fputs (";; Predecessors: ", outf); 1388 for (e = bb->pred; e; e = e->pred_next) 1389 dump_edge_info (outf, e, 0); 1390 putc ('\n', outf); 1391 1392 fputs (";; Registers live at start:", outf); 1393 dump_regset (bb->global_live_at_start, outf); 1394 putc ('\n', outf); 1395 1396 for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last; 1397 insn = NEXT_INSN (insn)) 1398 print_rtl_single (outf, insn); 1399 1400 fputs (";; Registers live at end:", outf); 1401 dump_regset (bb->global_live_at_end, outf); 1402 putc ('\n', outf); 1403 1404 fputs (";; Successors: ", outf); 1405 for (e = bb->succ; e; e = e->succ_next) 1406 dump_edge_info (outf, e, 1); 1407 putc ('\n', outf); 1408} 1409 1410void 1411debug_bb (bb) 1412 basic_block bb; 1413{ 1414 dump_bb (bb, stderr); 1415} 1416 1417void 1418debug_bb_n (n) 1419 int n; 1420{ 1421 dump_bb (BASIC_BLOCK (n), stderr); 1422} 1423 1424/* Like print_rtl, but also print out live information for the start of each 1425 basic block. */ 1426 1427void 1428print_rtl_with_bb (outf, rtx_first) 1429 FILE *outf; 1430 rtx rtx_first; 1431{ 1432 rtx tmp_rtx; 1433 1434 if (rtx_first == 0) 1435 fprintf (outf, "(nil)\n"); 1436 else 1437 { 1438 int i; 1439 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; 1440 int max_uid = get_max_uid (); 1441 basic_block *start 1442 = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); 1443 basic_block *end 1444 = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); 1445 enum bb_state *in_bb_p 1446 = (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state)); 1447 1448 for (i = n_basic_blocks - 1; i >= 0; i--) 1449 { 1450 basic_block bb = BASIC_BLOCK (i); 1451 rtx x; 1452 1453 start[INSN_UID (bb->head)] = bb; 1454 end[INSN_UID (bb->end)] = bb; 1455 for (x = bb->head; x != NULL_RTX; x = NEXT_INSN (x)) 1456 { 1457 enum bb_state state = IN_MULTIPLE_BB; 1458 1459 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB) 1460 state = IN_ONE_BB; 1461 in_bb_p[INSN_UID (x)] = state; 1462 1463 if (x == bb->end) 1464 break; 1465 } 1466 } 1467 1468 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx)) 1469 { 1470 int did_output; 1471 basic_block bb; 1472 1473 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL) 1474 { 1475 fprintf (outf, ";; Start of basic block %d, registers live:", 1476 bb->index); 1477 dump_regset (bb->global_live_at_start, outf); 1478 putc ('\n', outf); 1479 } 1480 1481 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB 1482 && GET_CODE (tmp_rtx) != NOTE 1483 && GET_CODE (tmp_rtx) != BARRIER) 1484 fprintf (outf, ";; Insn is not within a basic block\n"); 1485 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB) 1486 fprintf (outf, ";; Insn is in multiple basic blocks\n"); 1487 1488 did_output = print_rtl_single (outf, tmp_rtx); 1489 1490 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL) 1491 { 1492 fprintf (outf, ";; End of basic block %d, registers live:\n", 1493 bb->index); 1494 dump_regset (bb->global_live_at_end, outf); 1495 putc ('\n', outf); 1496 } 1497 1498 if (did_output) 1499 putc ('\n', outf); 1500 } 1501 1502 free (start); 1503 free (end); 1504 free (in_bb_p); 1505 } 1506 1507 if (current_function_epilogue_delay_list != 0) 1508 { 1509 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n"); 1510 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0; 1511 tmp_rtx = XEXP (tmp_rtx, 1)) 1512 print_rtl_single (outf, XEXP (tmp_rtx, 0)); 1513 } 1514} 1515 1516void 1517update_br_prob_note (bb) 1518 basic_block bb; 1519{ 1520 rtx note; 1521 if (GET_CODE (bb->end) != JUMP_INSN) 1522 return; 1523 note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX); 1524 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability) 1525 return; 1526 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability); 1527} 1528 1529/* Verify the CFG consistency. This function check some CFG invariants and 1530 aborts when something is wrong. Hope that this function will help to 1531 convert many optimization passes to preserve CFG consistent. 1532 1533 Currently it does following checks: 1534 1535 - test head/end pointers 1536 - overlapping of basic blocks 1537 - edge list correctness 1538 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note) 1539 - tails of basic blocks (ensure that boundary is necessary) 1540 - scans body of the basic block for JUMP_INSN, CODE_LABEL 1541 and NOTE_INSN_BASIC_BLOCK 1542 - check that all insns are in the basic blocks 1543 (except the switch handling code, barriers and notes) 1544 - check that all returns are followed by barriers 1545 1546 In future it can be extended check a lot of other stuff as well 1547 (reachability of basic blocks, life information, etc. etc.). */ 1548 1549void 1550verify_flow_info () 1551{ 1552 const int max_uid = get_max_uid (); 1553 const rtx rtx_first = get_insns (); 1554 rtx last_head = get_last_insn (); 1555 basic_block *bb_info, *last_visited; 1556 size_t *edge_checksum; 1557 rtx x; 1558 int i, last_bb_num_seen, num_bb_notes, err = 0; 1559 1560 bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block)); 1561 last_visited = (basic_block *) xcalloc (n_basic_blocks + 2, 1562 sizeof (basic_block)); 1563 edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t)); 1564 1565 for (i = n_basic_blocks - 1; i >= 0; i--) 1566 { 1567 basic_block bb = BASIC_BLOCK (i); 1568 rtx head = bb->head; 1569 rtx end = bb->end; 1570 1571 /* Verify the end of the basic block is in the INSN chain. */ 1572 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) 1573 if (x == end) 1574 break; 1575 1576 if (!x) 1577 { 1578 error ("end insn %d for block %d not found in the insn stream", 1579 INSN_UID (end), bb->index); 1580 err = 1; 1581 } 1582 1583 /* Work backwards from the end to the head of the basic block 1584 to verify the head is in the RTL chain. */ 1585 for (; x != NULL_RTX; x = PREV_INSN (x)) 1586 { 1587 /* While walking over the insn chain, verify insns appear 1588 in only one basic block and initialize the BB_INFO array 1589 used by other passes. */ 1590 if (bb_info[INSN_UID (x)] != NULL) 1591 { 1592 error ("insn %d is in multiple basic blocks (%d and %d)", 1593 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index); 1594 err = 1; 1595 } 1596 1597 bb_info[INSN_UID (x)] = bb; 1598 1599 if (x == head) 1600 break; 1601 } 1602 if (!x) 1603 { 1604 error ("head insn %d for block %d not found in the insn stream", 1605 INSN_UID (head), bb->index); 1606 err = 1; 1607 } 1608 1609 last_head = x; 1610 } 1611 1612 /* Now check the basic blocks (boundaries etc.) */ 1613 for (i = n_basic_blocks - 1; i >= 0; i--) 1614 { 1615 basic_block bb = BASIC_BLOCK (i); 1616 int has_fallthru = 0; 1617 edge e; 1618 1619 for (e = bb->succ; e; e = e->succ_next) 1620 { 1621 if (last_visited [e->dest->index + 2] == bb) 1622 { 1623 error ("verify_flow_info: Duplicate edge %i->%i", 1624 e->src->index, e->dest->index); 1625 err = 1; 1626 } 1627 1628 last_visited [e->dest->index + 2] = bb; 1629 1630 if (e->flags & EDGE_FALLTHRU) 1631 has_fallthru = 1; 1632 1633 if ((e->flags & EDGE_FALLTHRU) 1634 && e->src != ENTRY_BLOCK_PTR 1635 && e->dest != EXIT_BLOCK_PTR) 1636 { 1637 rtx insn; 1638 1639 if (e->src->index + 1 != e->dest->index) 1640 { 1641 error 1642 ("verify_flow_info: Incorrect blocks for fallthru %i->%i", 1643 e->src->index, e->dest->index); 1644 err = 1; 1645 } 1646 else 1647 for (insn = NEXT_INSN (e->src->end); insn != e->dest->head; 1648 insn = NEXT_INSN (insn)) 1649 if (GET_CODE (insn) == BARRIER 1650#ifndef CASE_DROPS_THROUGH 1651 || INSN_P (insn) 1652#else 1653 || (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn)) 1654#endif 1655 ) 1656 { 1657 error ("verify_flow_info: Incorrect fallthru %i->%i", 1658 e->src->index, e->dest->index); 1659 fatal_insn ("wrong insn in the fallthru edge", insn); 1660 err = 1; 1661 } 1662 } 1663 1664 if (e->src != bb) 1665 { 1666 error ("verify_flow_info: Basic block %d succ edge is corrupted", 1667 bb->index); 1668 fprintf (stderr, "Predecessor: "); 1669 dump_edge_info (stderr, e, 0); 1670 fprintf (stderr, "\nSuccessor: "); 1671 dump_edge_info (stderr, e, 1); 1672 fprintf (stderr, "\n"); 1673 err = 1; 1674 } 1675 1676 edge_checksum[e->dest->index + 2] += (size_t) e; 1677 } 1678 1679 if (!has_fallthru) 1680 { 1681 rtx insn; 1682 1683 /* Ensure existence of barrier in BB with no fallthru edges. */ 1684 for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER; 1685 insn = NEXT_INSN (insn)) 1686 if (!insn 1687 || (GET_CODE (insn) == NOTE 1688 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK)) 1689 { 1690 error ("missing barrier after block %i", bb->index); 1691 err = 1; 1692 break; 1693 } 1694 } 1695 1696 for (e = bb->pred; e; e = e->pred_next) 1697 { 1698 if (e->dest != bb) 1699 { 1700 error ("basic block %d pred edge is corrupted", bb->index); 1701 fputs ("Predecessor: ", stderr); 1702 dump_edge_info (stderr, e, 0); 1703 fputs ("\nSuccessor: ", stderr); 1704 dump_edge_info (stderr, e, 1); 1705 fputc ('\n', stderr); 1706 err = 1; 1707 } 1708 edge_checksum[e->dest->index + 2] -= (size_t) e; 1709 } 1710 1711 for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x)) 1712 if (basic_block_for_insn && BLOCK_FOR_INSN (x) != bb) 1713 { 1714 debug_rtx (x); 1715 if (! BLOCK_FOR_INSN (x)) 1716 error 1717 ("insn %d inside basic block %d but block_for_insn is NULL", 1718 INSN_UID (x), bb->index); 1719 else 1720 error 1721 ("insn %d inside basic block %d but block_for_insn is %i", 1722 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index); 1723 1724 err = 1; 1725 } 1726 1727 /* OK pointers are correct. Now check the header of basic 1728 block. It ought to contain optional CODE_LABEL followed 1729 by NOTE_BASIC_BLOCK. */ 1730 x = bb->head; 1731 if (GET_CODE (x) == CODE_LABEL) 1732 { 1733 if (bb->end == x) 1734 { 1735 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 1736 bb->index); 1737 err = 1; 1738 } 1739 1740 x = NEXT_INSN (x); 1741 } 1742 1743 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb) 1744 { 1745 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 1746 bb->index); 1747 err = 1; 1748 } 1749 1750 if (bb->end == x) 1751 /* Do checks for empty blocks her. e */ 1752 ; 1753 else 1754 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x)) 1755 { 1756 if (NOTE_INSN_BASIC_BLOCK_P (x)) 1757 { 1758 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d", 1759 INSN_UID (x), bb->index); 1760 err = 1; 1761 } 1762 1763 if (x == bb->end) 1764 break; 1765 1766 if (GET_CODE (x) == JUMP_INSN 1767 || GET_CODE (x) == CODE_LABEL 1768 || GET_CODE (x) == BARRIER) 1769 { 1770 error ("in basic block %d:", bb->index); 1771 fatal_insn ("flow control insn inside a basic block", x); 1772 } 1773 } 1774 } 1775 1776 /* Complete edge checksumming for ENTRY and EXIT. */ 1777 { 1778 edge e; 1779 1780 for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next) 1781 edge_checksum[e->dest->index + 2] += (size_t) e; 1782 1783 for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next) 1784 edge_checksum[e->dest->index + 2] -= (size_t) e; 1785 } 1786 1787 for (i = -2; i < n_basic_blocks; ++i) 1788 if (edge_checksum[i + 2]) 1789 { 1790 error ("basic block %i edge lists are corrupted", i); 1791 err = 1; 1792 } 1793 1794 last_bb_num_seen = -1; 1795 num_bb_notes = 0; 1796 for (x = rtx_first; x; x = NEXT_INSN (x)) 1797 { 1798 if (NOTE_INSN_BASIC_BLOCK_P (x)) 1799 { 1800 basic_block bb = NOTE_BASIC_BLOCK (x); 1801 1802 num_bb_notes++; 1803 if (bb->index != last_bb_num_seen + 1) 1804 internal_error ("basic blocks not numbered consecutively"); 1805 1806 last_bb_num_seen = bb->index; 1807 } 1808 1809 if (!bb_info[INSN_UID (x)]) 1810 { 1811 switch (GET_CODE (x)) 1812 { 1813 case BARRIER: 1814 case NOTE: 1815 break; 1816 1817 case CODE_LABEL: 1818 /* An addr_vec is placed outside any block block. */ 1819 if (NEXT_INSN (x) 1820 && GET_CODE (NEXT_INSN (x)) == JUMP_INSN 1821 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC 1822 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC)) 1823 x = NEXT_INSN (x); 1824 1825 /* But in any case, non-deletable labels can appear anywhere. */ 1826 break; 1827 1828 default: 1829 fatal_insn ("insn outside basic block", x); 1830 } 1831 } 1832 1833 if (INSN_P (x) 1834 && GET_CODE (x) == JUMP_INSN 1835 && returnjump_p (x) && ! condjump_p (x) 1836 && ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER)) 1837 fatal_insn ("return not followed by barrier", x); 1838 } 1839 1840 if (num_bb_notes != n_basic_blocks) 1841 internal_error 1842 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)", 1843 num_bb_notes, n_basic_blocks); 1844 1845 if (err) 1846 internal_error ("verify_flow_info failed"); 1847 1848 /* Clean up. */ 1849 free (bb_info); 1850 free (last_visited); 1851 free (edge_checksum); 1852} 1853 1854/* Assume that the preceding pass has possibly eliminated jump instructions 1855 or converted the unconditional jumps. Eliminate the edges from CFG. 1856 Return true if any edges are eliminated. */ 1857 1858bool 1859purge_dead_edges (bb) 1860 basic_block bb; 1861{ 1862 edge e, next; 1863 rtx insn = bb->end, note; 1864 bool purged = false; 1865 1866 /* ??? This makes no sense since the later test includes more cases. */ 1867 if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn)) 1868 return false; 1869 1870 if (GET_CODE (insn) == JUMP_INSN) 1871 { 1872 rtx note; 1873 edge b,f; 1874 1875 /* We do care only about conditional jumps and simplejumps. */ 1876 if (!any_condjump_p (insn) 1877 && !returnjump_p (insn) 1878 && !simplejump_p (insn)) 1879 return false; 1880 1881 for (e = bb->succ; e; e = next) 1882 { 1883 next = e->succ_next; 1884 1885 /* Avoid abnormal flags to leak from computed jumps turned 1886 into simplejumps. */ 1887 1888 e->flags &= ~EDGE_ABNORMAL; 1889 1890 /* Check purposes we can have edge. */ 1891 if ((e->flags & EDGE_FALLTHRU) 1892 && any_condjump_p (insn)) 1893 continue; 1894 else if (e->dest != EXIT_BLOCK_PTR 1895 && e->dest->head == JUMP_LABEL (insn)) 1896 continue; 1897 else if (e->dest == EXIT_BLOCK_PTR 1898 && returnjump_p (insn)) 1899 continue; 1900 1901 purged = true; 1902 remove_edge (e); 1903 } 1904 1905 if (!bb->succ || !purged) 1906 return false; 1907 1908 if (rtl_dump_file) 1909 fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index); 1910 1911 if (!optimize) 1912 return purged; 1913 1914 /* Redistribute probabilities. */ 1915 if (!bb->succ->succ_next) 1916 { 1917 bb->succ->probability = REG_BR_PROB_BASE; 1918 bb->succ->count = bb->count; 1919 } 1920 else 1921 { 1922 note = find_reg_note (insn, REG_BR_PROB, NULL); 1923 if (!note) 1924 return purged; 1925 1926 b = BRANCH_EDGE (bb); 1927 f = FALLTHRU_EDGE (bb); 1928 b->probability = INTVAL (XEXP (note, 0)); 1929 f->probability = REG_BR_PROB_BASE - b->probability; 1930 b->count = bb->count * b->probability / REG_BR_PROB_BASE; 1931 f->count = bb->count * f->probability / REG_BR_PROB_BASE; 1932 } 1933 1934 return purged; 1935 } 1936 1937 /* If this instruction cannot trap, remove REG_EH_REGION notes. */ 1938 if (GET_CODE (insn) == INSN 1939 && (note = find_reg_note (insn, REG_EH_REGION, NULL))) 1940 { 1941 rtx eqnote; 1942 1943 if (! may_trap_p (PATTERN (insn)) 1944 || ((eqnote = find_reg_equal_equiv_note (insn)) 1945 && ! may_trap_p (XEXP (eqnote, 0)))) 1946 remove_note (insn, note); 1947 } 1948 1949 /* Cleanup abnormal edges caused by throwing insns that have been 1950 eliminated. */ 1951 if (! can_throw_internal (bb->end)) 1952 for (e = bb->succ; e; e = next) 1953 { 1954 next = e->succ_next; 1955 if (e->flags & EDGE_EH) 1956 { 1957 remove_edge (e); 1958 purged = true; 1959 } 1960 } 1961 1962 /* If we don't see a jump insn, we don't know exactly why the block would 1963 have been broken at this point. Look for a simple, non-fallthru edge, 1964 as these are only created by conditional branches. If we find such an 1965 edge we know that there used to be a jump here and can then safely 1966 remove all non-fallthru edges. */ 1967 for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)); 1968 e = e->succ_next) 1969 ; 1970 1971 if (!e) 1972 return purged; 1973 1974 for (e = bb->succ; e; e = next) 1975 { 1976 next = e->succ_next; 1977 if (!(e->flags & EDGE_FALLTHRU)) 1978 remove_edge (e), purged = true; 1979 } 1980 1981 if (!bb->succ || bb->succ->succ_next) 1982 abort (); 1983 1984 bb->succ->probability = REG_BR_PROB_BASE; 1985 bb->succ->count = bb->count; 1986 1987 if (rtl_dump_file) 1988 fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n", 1989 bb->index); 1990 return purged; 1991} 1992 1993/* Search all basic blocks for potentially dead edges and purge them. Return 1994 true if some edge has been eliminated. */ 1995 1996bool 1997purge_all_dead_edges (update_life_p) 1998 int update_life_p; 1999{ 2000 int i, purged = false; 2001 sbitmap blocks = 0; 2002 2003 if (update_life_p) 2004 { 2005 blocks = sbitmap_alloc (n_basic_blocks); 2006 sbitmap_zero (blocks); 2007 } 2008 2009 for (i = 0; i < n_basic_blocks; i++) 2010 { 2011 bool purged_here = purge_dead_edges (BASIC_BLOCK (i)); 2012 2013 purged |= purged_here; 2014 if (purged_here && update_life_p) 2015 SET_BIT (blocks, i); 2016 } 2017 2018 if (update_life_p && purged) 2019 update_life_info (blocks, UPDATE_LIFE_GLOBAL, 2020 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE 2021 | PROP_KILL_DEAD_CODE); 2022 2023 if (update_life_p) 2024 sbitmap_free (blocks); 2025 return purged; 2026} 2027