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