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, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, 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 - Basic CFG/RTL manipulation API documented in cfghooks.h 27 - CFG-aware instruction chain manipulation 28 delete_insn, delete_insn_chain 29 - Edge splitting and committing to edges 30 insert_insn_on_edge, commit_edge_insertions 31 - CFG updating after insn simplification 32 purge_dead_edges, purge_all_dead_edges 33 34 Functions not supposed for generic use: 35 - Infrastructure to determine quickly basic block for insn 36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn, 37 - Edge redirection with updating and optimizing of insn chain 38 block_label, tidy_fallthru_edge, force_nonfallthru */ 39 40#include "config.h" 41#include "system.h" 42#include "coretypes.h" 43#include "tm.h" 44#include "tree.h" 45#include "rtl.h" 46#include "hard-reg-set.h" 47#include "basic-block.h" 48#include "regs.h" 49#include "flags.h" 50#include "output.h" 51#include "function.h" 52#include "except.h" 53#include "toplev.h" 54#include "tm_p.h" 55#include "obstack.h" 56#include "insn-config.h" 57#include "cfglayout.h" 58#include "expr.h" 59#include "target.h" 60#include "cfgloop.h" 61#include "ggc.h" 62#include "tree-pass.h" 63 64static int can_delete_note_p (rtx); 65static int can_delete_label_p (rtx); 66static void commit_one_edge_insertion (edge, int); 67static rtx last_loop_beg_note (rtx); 68static bool back_edge_of_syntactic_loop_p (basic_block, basic_block); 69static basic_block rtl_split_edge (edge); 70static bool rtl_move_block_after (basic_block, basic_block); 71static int rtl_verify_flow_info (void); 72static basic_block cfg_layout_split_block (basic_block, void *); 73static edge cfg_layout_redirect_edge_and_branch (edge, basic_block); 74static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block); 75static void cfg_layout_delete_block (basic_block); 76static void rtl_delete_block (basic_block); 77static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block); 78static edge rtl_redirect_edge_and_branch (edge, basic_block); 79static basic_block rtl_split_block (basic_block, void *); 80static void rtl_dump_bb (basic_block, FILE *, int); 81static int rtl_verify_flow_info_1 (void); 82static void mark_killed_regs (rtx, rtx, void *); 83static void rtl_make_forwarder_block (edge); 84 85/* Return true if NOTE is not one of the ones that must be kept paired, 86 so that we may simply delete it. */ 87 88static int 89can_delete_note_p (rtx note) 90{ 91 return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED 92 || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK); 93} 94 95/* True if a given label can be deleted. */ 96 97static int 98can_delete_label_p (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} 105 106/* Delete INSN by patching it out. Return the next insn. */ 107 108rtx 109delete_insn (rtx insn) 110{ 111 rtx next = NEXT_INSN (insn); 112 rtx note; 113 bool really_delete = true; 114 115 if (LABEL_P (insn)) 116 { 117 /* Some labels can't be directly removed from the INSN chain, as they 118 might be references via variables, constant pool etc. 119 Convert them to the special NOTE_INSN_DELETED_LABEL note. */ 120 if (! can_delete_label_p (insn)) 121 { 122 const char *name = LABEL_NAME (insn); 123 124 really_delete = false; 125 PUT_CODE (insn, NOTE); 126 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL; 127 NOTE_DELETED_LABEL_NAME (insn) = name; 128 } 129 130 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels); 131 } 132 133 if (really_delete) 134 { 135 /* If this insn has already been deleted, something is very wrong. */ 136 gcc_assert (!INSN_DELETED_P (insn)); 137 remove_insn (insn); 138 INSN_DELETED_P (insn) = 1; 139 } 140 141 /* If deleting a jump, decrement the use count of the label. Deleting 142 the label itself should happen in the normal course of block merging. */ 143 if (JUMP_P (insn) 144 && JUMP_LABEL (insn) 145 && LABEL_P (JUMP_LABEL (insn))) 146 LABEL_NUSES (JUMP_LABEL (insn))--; 147 148 /* Also if deleting an insn that references a label. */ 149 else 150 { 151 while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX 152 && LABEL_P (XEXP (note, 0))) 153 { 154 LABEL_NUSES (XEXP (note, 0))--; 155 remove_note (insn, note); 156 } 157 } 158 159 if (JUMP_P (insn) 160 && (GET_CODE (PATTERN (insn)) == ADDR_VEC 161 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 162 { 163 rtx pat = PATTERN (insn); 164 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC; 165 int len = XVECLEN (pat, diff_vec_p); 166 int i; 167 168 for (i = 0; i < len; i++) 169 { 170 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0); 171 172 /* When deleting code in bulk (e.g. removing many unreachable 173 blocks) we can delete a label that's a target of the vector 174 before deleting the vector itself. */ 175 if (!NOTE_P (label)) 176 LABEL_NUSES (label)--; 177 } 178 } 179 180 return next; 181} 182 183/* Like delete_insn but also purge dead edges from BB. */ 184rtx 185delete_insn_and_edges (rtx insn) 186{ 187 rtx x; 188 bool purge = false; 189 190 if (INSN_P (insn) 191 && BLOCK_FOR_INSN (insn) 192 && BB_END (BLOCK_FOR_INSN (insn)) == insn) 193 purge = true; 194 x = delete_insn (insn); 195 if (purge) 196 purge_dead_edges (BLOCK_FOR_INSN (insn)); 197 return x; 198} 199 200/* Unlink a chain of insns between START and FINISH, leaving notes 201 that must be paired. */ 202 203void 204delete_insn_chain (rtx start, rtx finish) 205{ 206 rtx next; 207 208 /* Unchain the insns one by one. It would be quicker to delete all of these 209 with a single unchaining, rather than one at a time, but we need to keep 210 the NOTE's. */ 211 while (1) 212 { 213 next = NEXT_INSN (start); 214 if (NOTE_P (start) && !can_delete_note_p (start)) 215 ; 216 else 217 next = delete_insn (start); 218 219 if (start == finish) 220 break; 221 start = next; 222 } 223} 224 225/* Like delete_insn but also purge dead edges from BB. */ 226void 227delete_insn_chain_and_edges (rtx first, rtx last) 228{ 229 bool purge = false; 230 231 if (INSN_P (last) 232 && BLOCK_FOR_INSN (last) 233 && BB_END (BLOCK_FOR_INSN (last)) == last) 234 purge = true; 235 delete_insn_chain (first, last); 236 if (purge) 237 purge_dead_edges (BLOCK_FOR_INSN (last)); 238} 239 240/* Create a new basic block consisting of the instructions between HEAD and END 241 inclusive. This function is designed to allow fast BB construction - reuses 242 the note and basic block struct in BB_NOTE, if any and do not grow 243 BASIC_BLOCK chain and should be used directly only by CFG construction code. 244 END can be NULL in to create new empty basic block before HEAD. Both END 245 and HEAD can be NULL to create basic block at the end of INSN chain. 246 AFTER is the basic block we should be put after. */ 247 248basic_block 249create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after) 250{ 251 basic_block bb; 252 253 if (bb_note 254 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL 255 && bb->aux == NULL) 256 { 257 /* If we found an existing note, thread it back onto the chain. */ 258 259 rtx after; 260 261 if (LABEL_P (head)) 262 after = head; 263 else 264 { 265 after = PREV_INSN (head); 266 head = bb_note; 267 } 268 269 if (after != bb_note && NEXT_INSN (after) != bb_note) 270 reorder_insns_nobb (bb_note, bb_note, after); 271 } 272 else 273 { 274 /* Otherwise we must create a note and a basic block structure. */ 275 276 bb = alloc_block (); 277 278 init_rtl_bb_info (bb); 279 if (!head && !end) 280 head = end = bb_note 281 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ()); 282 else if (LABEL_P (head) && end) 283 { 284 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head); 285 if (head == end) 286 end = bb_note; 287 } 288 else 289 { 290 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head); 291 head = bb_note; 292 if (!end) 293 end = head; 294 } 295 296 NOTE_BASIC_BLOCK (bb_note) = bb; 297 } 298 299 /* Always include the bb note in the block. */ 300 if (NEXT_INSN (end) == bb_note) 301 end = bb_note; 302 303 BB_HEAD (bb) = head; 304 BB_END (bb) = end; 305 bb->index = last_basic_block++; 306 bb->flags = BB_NEW | BB_RTL; 307 link_block (bb, after); 308 BASIC_BLOCK (bb->index) = bb; 309 update_bb_for_insn (bb); 310 BB_SET_PARTITION (bb, BB_UNPARTITIONED); 311 312 /* Tag the block so that we know it has been used when considering 313 other basic block notes. */ 314 bb->aux = bb; 315 316 return bb; 317} 318 319/* Create new basic block consisting of instructions in between HEAD and END 320 and place it to the BB chain after block AFTER. END can be NULL in to 321 create new empty basic block before HEAD. Both END and HEAD can be NULL to 322 create basic block at the end of INSN chain. */ 323 324static basic_block 325rtl_create_basic_block (void *headp, void *endp, basic_block after) 326{ 327 rtx head = headp, end = endp; 328 basic_block bb; 329 330 /* Grow the basic block array if needed. */ 331 if ((size_t) last_basic_block >= VARRAY_SIZE (basic_block_info)) 332 { 333 size_t new_size = last_basic_block + (last_basic_block + 3) / 4; 334 VARRAY_GROW (basic_block_info, new_size); 335 } 336 337 n_basic_blocks++; 338 339 bb = create_basic_block_structure (head, end, NULL, after); 340 bb->aux = NULL; 341 return bb; 342} 343 344static basic_block 345cfg_layout_create_basic_block (void *head, void *end, basic_block after) 346{ 347 basic_block newbb = rtl_create_basic_block (head, end, after); 348 349 return newbb; 350} 351 352/* Delete the insns in a (non-live) block. We physically delete every 353 non-deleted-note insn, and update the flow graph appropriately. 354 355 Return nonzero if we deleted an exception handler. */ 356 357/* ??? Preserving all such notes strikes me as wrong. It would be nice 358 to post-process the stream to remove empty blocks, loops, ranges, etc. */ 359 360static void 361rtl_delete_block (basic_block b) 362{ 363 rtx insn, end, tmp; 364 365 /* If the head of this block is a CODE_LABEL, then it might be the 366 label for an exception handler which can't be reached. We need 367 to remove the label from the exception_handler_label list. */ 368 insn = BB_HEAD (b); 369 if (LABEL_P (insn)) 370 maybe_remove_eh_handler (insn); 371 372 /* Include any jump table following the basic block. */ 373 end = BB_END (b); 374 if (tablejump_p (end, NULL, &tmp)) 375 end = tmp; 376 377 /* Include any barriers that may follow the basic block. */ 378 tmp = next_nonnote_insn (end); 379 while (tmp && BARRIER_P (tmp)) 380 { 381 end = tmp; 382 tmp = next_nonnote_insn (end); 383 } 384 385 /* Selectively delete the entire chain. */ 386 BB_HEAD (b) = NULL; 387 delete_insn_chain (insn, end); 388} 389 390/* Records the basic block struct in BLOCK_FOR_INSN for every insn. */ 391 392void 393compute_bb_for_insn (void) 394{ 395 basic_block bb; 396 397 FOR_EACH_BB (bb) 398 { 399 rtx end = BB_END (bb); 400 rtx insn; 401 402 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 403 { 404 BLOCK_FOR_INSN (insn) = bb; 405 if (insn == end) 406 break; 407 } 408 } 409} 410 411/* Release the basic_block_for_insn array. */ 412 413void 414free_bb_for_insn (void) 415{ 416 rtx insn; 417 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 418 if (!BARRIER_P (insn)) 419 BLOCK_FOR_INSN (insn) = NULL; 420} 421 422struct tree_opt_pass pass_free_cfg = 423{ 424 NULL, /* name */ 425 NULL, /* gate */ 426 free_bb_for_insn, /* execute */ 427 NULL, /* sub */ 428 NULL, /* next */ 429 0, /* static_pass_number */ 430 0, /* tv_id */ 431 0, /* properties_required */ 432 0, /* properties_provided */ 433 PROP_cfg, /* properties_destroyed */ 434 0, /* todo_flags_start */ 435 0, /* todo_flags_finish */ 436 0 /* letter */ 437}; 438 439/* Return RTX to emit after when we want to emit code on the entry of function. */ 440rtx 441entry_of_function (void) 442{ 443 return (n_basic_blocks ? BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ()); 444} 445 446/* Update insns block within BB. */ 447 448void 449update_bb_for_insn (basic_block bb) 450{ 451 rtx insn; 452 453 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 454 { 455 if (!BARRIER_P (insn)) 456 set_block_for_insn (insn, bb); 457 if (insn == BB_END (bb)) 458 break; 459 } 460} 461 462/* Creates a new basic block just after basic block B by splitting 463 everything after specified instruction I. */ 464 465static basic_block 466rtl_split_block (basic_block bb, void *insnp) 467{ 468 basic_block new_bb; 469 rtx insn = insnp; 470 edge e; 471 edge_iterator ei; 472 473 if (!insn) 474 { 475 insn = first_insn_after_basic_block_note (bb); 476 477 if (insn) 478 insn = PREV_INSN (insn); 479 else 480 insn = get_last_insn (); 481 } 482 483 /* We probably should check type of the insn so that we do not create 484 inconsistent cfg. It is checked in verify_flow_info anyway, so do not 485 bother. */ 486 if (insn == BB_END (bb)) 487 emit_note_after (NOTE_INSN_DELETED, insn); 488 489 /* Create the new basic block. */ 490 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb); 491 BB_COPY_PARTITION (new_bb, bb); 492 BB_END (bb) = insn; 493 494 /* Redirect the outgoing edges. */ 495 new_bb->succs = bb->succs; 496 bb->succs = NULL; 497 FOR_EACH_EDGE (e, ei, new_bb->succs) 498 e->src = new_bb; 499 500 if (bb->il.rtl->global_live_at_start) 501 { 502 new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 503 new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 504 COPY_REG_SET (new_bb->il.rtl->global_live_at_end, bb->il.rtl->global_live_at_end); 505 506 /* We now have to calculate which registers are live at the end 507 of the split basic block and at the start of the new basic 508 block. Start with those registers that are known to be live 509 at the end of the original basic block and get 510 propagate_block to determine which registers are live. */ 511 COPY_REG_SET (new_bb->il.rtl->global_live_at_start, bb->il.rtl->global_live_at_end); 512 propagate_block (new_bb, new_bb->il.rtl->global_live_at_start, NULL, NULL, 0); 513 COPY_REG_SET (bb->il.rtl->global_live_at_end, 514 new_bb->il.rtl->global_live_at_start); 515#ifdef HAVE_conditional_execution 516 /* In the presence of conditional execution we are not able to update 517 liveness precisely. */ 518 if (reload_completed) 519 { 520 bb->flags |= BB_DIRTY; 521 new_bb->flags |= BB_DIRTY; 522 } 523#endif 524 } 525 526 return new_bb; 527} 528 529/* Blocks A and B are to be merged into a single block A. The insns 530 are already contiguous. */ 531 532static void 533rtl_merge_blocks (basic_block a, basic_block b) 534{ 535 rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a); 536 rtx del_first = NULL_RTX, del_last = NULL_RTX; 537 int b_empty = 0; 538 539 /* If there was a CODE_LABEL beginning B, delete it. */ 540 if (LABEL_P (b_head)) 541 { 542 /* This might have been an EH label that no longer has incoming 543 EH edges. Update data structures to match. */ 544 maybe_remove_eh_handler (b_head); 545 546 /* Detect basic blocks with nothing but a label. This can happen 547 in particular at the end of a function. */ 548 if (b_head == b_end) 549 b_empty = 1; 550 551 del_first = del_last = b_head; 552 b_head = NEXT_INSN (b_head); 553 } 554 555 /* Delete the basic block note and handle blocks containing just that 556 note. */ 557 if (NOTE_INSN_BASIC_BLOCK_P (b_head)) 558 { 559 if (b_head == b_end) 560 b_empty = 1; 561 if (! del_last) 562 del_first = b_head; 563 564 del_last = b_head; 565 b_head = NEXT_INSN (b_head); 566 } 567 568 /* If there was a jump out of A, delete it. */ 569 if (JUMP_P (a_end)) 570 { 571 rtx prev; 572 573 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev)) 574 if (!NOTE_P (prev) 575 || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK 576 || prev == BB_HEAD (a)) 577 break; 578 579 del_first = a_end; 580 581#ifdef HAVE_cc0 582 /* If this was a conditional jump, we need to also delete 583 the insn that set cc0. */ 584 if (only_sets_cc0_p (prev)) 585 { 586 rtx tmp = prev; 587 588 prev = prev_nonnote_insn (prev); 589 if (!prev) 590 prev = BB_HEAD (a); 591 del_first = tmp; 592 } 593#endif 594 595 a_end = PREV_INSN (del_first); 596 } 597 else if (BARRIER_P (NEXT_INSN (a_end))) 598 del_first = NEXT_INSN (a_end); 599 600 /* Delete everything marked above as well as crap that might be 601 hanging out between the two blocks. */ 602 BB_HEAD (b) = NULL; 603 delete_insn_chain (del_first, del_last); 604 605 /* Reassociate the insns of B with A. */ 606 if (!b_empty) 607 { 608 rtx x; 609 610 for (x = a_end; x != b_end; x = NEXT_INSN (x)) 611 set_block_for_insn (x, a); 612 613 set_block_for_insn (b_end, a); 614 615 a_end = b_end; 616 } 617 618 BB_END (a) = a_end; 619 a->il.rtl->global_live_at_end = b->il.rtl->global_live_at_end; 620} 621 622/* Return true when block A and B can be merged. */ 623static bool 624rtl_can_merge_blocks (basic_block a,basic_block b) 625{ 626 /* If we are partitioning hot/cold basic blocks, we don't want to 627 mess up unconditional or indirect jumps that cross between hot 628 and cold sections. 629 630 Basic block partitioning may result in some jumps that appear to 631 be optimizable (or blocks that appear to be mergeable), but which really 632 must be left untouched (they are required to make it safely across 633 partition boundaries). See the comments at the top of 634 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 635 636 if (BB_PARTITION (a) != BB_PARTITION (b)) 637 return false; 638 639 /* There must be exactly one edge in between the blocks. */ 640 return (single_succ_p (a) 641 && single_succ (a) == b 642 && single_pred_p (b) 643 && a != b 644 /* Must be simple edge. */ 645 && !(single_succ_edge (a)->flags & EDGE_COMPLEX) 646 && a->next_bb == b 647 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR 648 /* If the jump insn has side effects, 649 we can't kill the edge. */ 650 && (!JUMP_P (BB_END (a)) 651 || (reload_completed 652 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); 653} 654 655/* Return the label in the head of basic block BLOCK. Create one if it doesn't 656 exist. */ 657 658rtx 659block_label (basic_block block) 660{ 661 if (block == EXIT_BLOCK_PTR) 662 return NULL_RTX; 663 664 if (!LABEL_P (BB_HEAD (block))) 665 { 666 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block)); 667 } 668 669 return BB_HEAD (block); 670} 671 672/* Attempt to perform edge redirection by replacing possibly complex jump 673 instruction by unconditional jump or removing jump completely. This can 674 apply only if all edges now point to the same block. The parameters and 675 return values are equivalent to redirect_edge_and_branch. */ 676 677edge 678try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout) 679{ 680 basic_block src = e->src; 681 rtx insn = BB_END (src), kill_from; 682 rtx set; 683 int fallthru = 0; 684 685 /* If we are partitioning hot/cold basic blocks, we don't want to 686 mess up unconditional or indirect jumps that cross between hot 687 and cold sections. 688 689 Basic block partitioning may result in some jumps that appear to 690 be optimizable (or blocks that appear to be mergeable), but which really 691 must be left untouched (they are required to make it safely across 692 partition boundaries). See the comments at the top of 693 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 694 695 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX) 696 || BB_PARTITION (src) != BB_PARTITION (target)) 697 return NULL; 698 699 /* We can replace or remove a complex jump only when we have exactly 700 two edges. Also, if we have exactly one outgoing edge, we can 701 redirect that. */ 702 if (EDGE_COUNT (src->succs) >= 3 703 /* Verify that all targets will be TARGET. Specifically, the 704 edge that is not E must also go to TARGET. */ 705 || (EDGE_COUNT (src->succs) == 2 706 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)) 707 return NULL; 708 709 if (!onlyjump_p (insn)) 710 return NULL; 711 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL)) 712 return NULL; 713 714 /* Avoid removing branch with side effects. */ 715 set = single_set (insn); 716 if (!set || side_effects_p (set)) 717 return NULL; 718 719 /* In case we zap a conditional jump, we'll need to kill 720 the cc0 setter too. */ 721 kill_from = insn; 722#ifdef HAVE_cc0 723 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))) 724 kill_from = PREV_INSN (insn); 725#endif 726 727 /* See if we can create the fallthru edge. */ 728 if (in_cfglayout || can_fallthru (src, target)) 729 { 730 if (dump_file) 731 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn)); 732 fallthru = 1; 733 734 /* Selectively unlink whole insn chain. */ 735 if (in_cfglayout) 736 { 737 rtx insn = src->il.rtl->footer; 738 739 delete_insn_chain (kill_from, BB_END (src)); 740 741 /* Remove barriers but keep jumptables. */ 742 while (insn) 743 { 744 if (BARRIER_P (insn)) 745 { 746 if (PREV_INSN (insn)) 747 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); 748 else 749 src->il.rtl->footer = NEXT_INSN (insn); 750 if (NEXT_INSN (insn)) 751 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); 752 } 753 if (LABEL_P (insn)) 754 break; 755 insn = NEXT_INSN (insn); 756 } 757 } 758 else 759 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target))); 760 } 761 762 /* If this already is simplejump, redirect it. */ 763 else if (simplejump_p (insn)) 764 { 765 if (e->dest == target) 766 return NULL; 767 if (dump_file) 768 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n", 769 INSN_UID (insn), e->dest->index, target->index); 770 if (!redirect_jump (insn, block_label (target), 0)) 771 { 772 gcc_assert (target == EXIT_BLOCK_PTR); 773 return NULL; 774 } 775 } 776 777 /* Cannot do anything for target exit block. */ 778 else if (target == EXIT_BLOCK_PTR) 779 return NULL; 780 781 /* Or replace possibly complicated jump insn by simple jump insn. */ 782 else 783 { 784 rtx target_label = block_label (target); 785 rtx barrier, label, table; 786 787 emit_jump_insn_after_noloc (gen_jump (target_label), insn); 788 JUMP_LABEL (BB_END (src)) = target_label; 789 LABEL_NUSES (target_label)++; 790 if (dump_file) 791 fprintf (dump_file, "Replacing insn %i by jump %i\n", 792 INSN_UID (insn), INSN_UID (BB_END (src))); 793 794 795 delete_insn_chain (kill_from, insn); 796 797 /* Recognize a tablejump that we are converting to a 798 simple jump and remove its associated CODE_LABEL 799 and ADDR_VEC or ADDR_DIFF_VEC. */ 800 if (tablejump_p (insn, &label, &table)) 801 delete_insn_chain (label, table); 802 803 barrier = next_nonnote_insn (BB_END (src)); 804 if (!barrier || !BARRIER_P (barrier)) 805 emit_barrier_after (BB_END (src)); 806 else 807 { 808 if (barrier != NEXT_INSN (BB_END (src))) 809 { 810 /* Move the jump before barrier so that the notes 811 which originally were or were created before jump table are 812 inside the basic block. */ 813 rtx new_insn = BB_END (src); 814 rtx tmp; 815 816 for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier; 817 tmp = NEXT_INSN (tmp)) 818 set_block_for_insn (tmp, src); 819 820 NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn); 821 PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn); 822 823 NEXT_INSN (new_insn) = barrier; 824 NEXT_INSN (PREV_INSN (barrier)) = new_insn; 825 826 PREV_INSN (new_insn) = PREV_INSN (barrier); 827 PREV_INSN (barrier) = new_insn; 828 } 829 } 830 } 831 832 /* Keep only one edge out and set proper flags. */ 833 if (!single_succ_p (src)) 834 remove_edge (e); 835 gcc_assert (single_succ_p (src)); 836 837 e = single_succ_edge (src); 838 if (fallthru) 839 e->flags = EDGE_FALLTHRU; 840 else 841 e->flags = 0; 842 843 e->probability = REG_BR_PROB_BASE; 844 e->count = src->count; 845 846 /* We don't want a block to end on a line-number note since that has 847 the potential of changing the code between -g and not -g. */ 848 while (NOTE_P (BB_END (e->src)) 849 && NOTE_LINE_NUMBER (BB_END (e->src)) >= 0) 850 delete_insn (BB_END (e->src)); 851 852 if (e->dest != target) 853 redirect_edge_succ (e, target); 854 855 return e; 856} 857 858/* Return last loop_beg note appearing after INSN, before start of next 859 basic block. Return INSN if there are no such notes. 860 861 When emitting jump to redirect a fallthru edge, it should always appear 862 after the LOOP_BEG notes, as loop optimizer expect loop to either start by 863 fallthru edge or jump following the LOOP_BEG note jumping to the loop exit 864 test. */ 865 866static rtx 867last_loop_beg_note (rtx insn) 868{ 869 rtx last = insn; 870 871 for (insn = NEXT_INSN (insn); insn && NOTE_P (insn) 872 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; 873 insn = NEXT_INSN (insn)) 874 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 875 last = insn; 876 877 return last; 878} 879 880/* Redirect edge representing branch of (un)conditional jump or tablejump, 881 NULL on failure */ 882static edge 883redirect_branch_edge (edge e, basic_block target) 884{ 885 rtx tmp; 886 rtx old_label = BB_HEAD (e->dest); 887 basic_block src = e->src; 888 rtx insn = BB_END (src); 889 890 /* We can only redirect non-fallthru edges of jump insn. */ 891 if (e->flags & EDGE_FALLTHRU) 892 return NULL; 893 else if (!JUMP_P (insn)) 894 return NULL; 895 896 /* Recognize a tablejump and adjust all matching cases. */ 897 if (tablejump_p (insn, NULL, &tmp)) 898 { 899 rtvec vec; 900 int j; 901 rtx new_label = block_label (target); 902 903 if (target == EXIT_BLOCK_PTR) 904 return NULL; 905 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) 906 vec = XVEC (PATTERN (tmp), 0); 907 else 908 vec = XVEC (PATTERN (tmp), 1); 909 910 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 911 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label) 912 { 913 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label); 914 --LABEL_NUSES (old_label); 915 ++LABEL_NUSES (new_label); 916 } 917 918 /* Handle casesi dispatch insns. */ 919 if ((tmp = single_set (insn)) != NULL 920 && SET_DEST (tmp) == pc_rtx 921 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 922 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF 923 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label) 924 { 925 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode, 926 new_label); 927 --LABEL_NUSES (old_label); 928 ++LABEL_NUSES (new_label); 929 } 930 } 931 else 932 { 933 /* ?? We may play the games with moving the named labels from 934 one basic block to the other in case only one computed_jump is 935 available. */ 936 if (computed_jump_p (insn) 937 /* A return instruction can't be redirected. */ 938 || returnjump_p (insn)) 939 return NULL; 940 941 /* If the insn doesn't go where we think, we're confused. */ 942 gcc_assert (JUMP_LABEL (insn) == old_label); 943 944 /* If the substitution doesn't succeed, die. This can happen 945 if the back end emitted unrecognizable instructions or if 946 target is exit block on some arches. */ 947 if (!redirect_jump (insn, block_label (target), 0)) 948 { 949 gcc_assert (target == EXIT_BLOCK_PTR); 950 return NULL; 951 } 952 } 953 954 if (dump_file) 955 fprintf (dump_file, "Edge %i->%i redirected to %i\n", 956 e->src->index, e->dest->index, target->index); 957 958 if (e->dest != target) 959 e = redirect_edge_succ_nodup (e, target); 960 return e; 961} 962 963/* Attempt to change code to redirect edge E to TARGET. Don't do that on 964 expense of adding new instructions or reordering basic blocks. 965 966 Function can be also called with edge destination equivalent to the TARGET. 967 Then it should try the simplifications and do nothing if none is possible. 968 969 Return edge representing the branch if transformation succeeded. Return NULL 970 on failure. 971 We still return NULL in case E already destinated TARGET and we didn't 972 managed to simplify instruction stream. */ 973 974static edge 975rtl_redirect_edge_and_branch (edge e, basic_block target) 976{ 977 edge ret; 978 basic_block src = e->src; 979 980 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 981 return NULL; 982 983 if (e->dest == target) 984 return e; 985 986 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL) 987 { 988 src->flags |= BB_DIRTY; 989 return ret; 990 } 991 992 ret = redirect_branch_edge (e, target); 993 if (!ret) 994 return NULL; 995 996 src->flags |= BB_DIRTY; 997 return ret; 998} 999 1000/* Like force_nonfallthru below, but additionally performs redirection 1001 Used by redirect_edge_and_branch_force. */ 1002 1003static basic_block 1004force_nonfallthru_and_redirect (edge e, basic_block target) 1005{ 1006 basic_block jump_block, new_bb = NULL, src = e->src; 1007 rtx note; 1008 edge new_edge; 1009 int abnormal_edge_flags = 0; 1010 1011 /* In the case the last instruction is conditional jump to the next 1012 instruction, first redirect the jump itself and then continue 1013 by creating a basic block afterwards to redirect fallthru edge. */ 1014 if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR 1015 && any_condjump_p (BB_END (e->src)) 1016 /* When called from cfglayout, fallthru edges do not 1017 necessarily go to the next block. */ 1018 && e->src->next_bb == e->dest 1019 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest)) 1020 { 1021 rtx note; 1022 edge b = unchecked_make_edge (e->src, target, 0); 1023 bool redirected; 1024 1025 redirected = redirect_jump (BB_END (e->src), block_label (target), 0); 1026 gcc_assert (redirected); 1027 1028 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX); 1029 if (note) 1030 { 1031 int prob = INTVAL (XEXP (note, 0)); 1032 1033 b->probability = prob; 1034 b->count = e->count * prob / REG_BR_PROB_BASE; 1035 e->probability -= e->probability; 1036 e->count -= b->count; 1037 if (e->probability < 0) 1038 e->probability = 0; 1039 if (e->count < 0) 1040 e->count = 0; 1041 } 1042 } 1043 1044 if (e->flags & EDGE_ABNORMAL) 1045 { 1046 /* Irritating special case - fallthru edge to the same block as abnormal 1047 edge. 1048 We can't redirect abnormal edge, but we still can split the fallthru 1049 one and create separate abnormal edge to original destination. 1050 This allows bb-reorder to make such edge non-fallthru. */ 1051 gcc_assert (e->dest == target); 1052 abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU); 1053 e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU; 1054 } 1055 else 1056 { 1057 gcc_assert (e->flags & EDGE_FALLTHRU); 1058 if (e->src == ENTRY_BLOCK_PTR) 1059 { 1060 /* We can't redirect the entry block. Create an empty block 1061 at the start of the function which we use to add the new 1062 jump. */ 1063 edge tmp; 1064 edge_iterator ei; 1065 bool found = false; 1066 1067 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR); 1068 1069 /* Change the existing edge's source to be the new block, and add 1070 a new edge from the entry block to the new block. */ 1071 e->src = bb; 1072 for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); ) 1073 { 1074 if (tmp == e) 1075 { 1076 VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index); 1077 found = true; 1078 break; 1079 } 1080 else 1081 ei_next (&ei); 1082 } 1083 1084 gcc_assert (found); 1085 1086 VEC_safe_push (edge, gc, bb->succs, e); 1087 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU); 1088 } 1089 } 1090 1091 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags) 1092 { 1093 /* Create the new structures. */ 1094 1095 /* If the old block ended with a tablejump, skip its table 1096 by searching forward from there. Otherwise start searching 1097 forward from the last instruction of the old block. */ 1098 if (!tablejump_p (BB_END (e->src), NULL, ¬e)) 1099 note = BB_END (e->src); 1100 1101 /* Position the new block correctly relative to loop notes. */ 1102 note = last_loop_beg_note (note); 1103 note = NEXT_INSN (note); 1104 1105 jump_block = create_basic_block (note, NULL, e->src); 1106 jump_block->count = e->count; 1107 jump_block->frequency = EDGE_FREQUENCY (e); 1108 jump_block->loop_depth = target->loop_depth; 1109 1110 if (target->il.rtl->global_live_at_start) 1111 { 1112 jump_block->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1113 jump_block->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1114 COPY_REG_SET (jump_block->il.rtl->global_live_at_start, 1115 target->il.rtl->global_live_at_start); 1116 COPY_REG_SET (jump_block->il.rtl->global_live_at_end, 1117 target->il.rtl->global_live_at_start); 1118 } 1119 1120 /* Make sure new block ends up in correct hot/cold section. */ 1121 1122 BB_COPY_PARTITION (jump_block, e->src); 1123 if (flag_reorder_blocks_and_partition 1124 && targetm.have_named_sections 1125 && JUMP_P (BB_END (jump_block)) 1126 && !any_condjump_p (BB_END (jump_block)) 1127 && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING)) 1128 REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, 1129 NULL_RTX, 1130 REG_NOTES 1131 (BB_END 1132 (jump_block))); 1133 1134 /* Wire edge in. */ 1135 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU); 1136 new_edge->probability = e->probability; 1137 new_edge->count = e->count; 1138 1139 /* Redirect old edge. */ 1140 redirect_edge_pred (e, jump_block); 1141 e->probability = REG_BR_PROB_BASE; 1142 1143 new_bb = jump_block; 1144 } 1145 else 1146 jump_block = e->src; 1147 1148 e->flags &= ~EDGE_FALLTHRU; 1149 if (target == EXIT_BLOCK_PTR) 1150 { 1151#ifdef HAVE_return 1152 emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block)); 1153#else 1154 gcc_unreachable (); 1155#endif 1156 } 1157 else 1158 { 1159 rtx label = block_label (target); 1160 emit_jump_insn_after_noloc (gen_jump (label), BB_END (jump_block)); 1161 JUMP_LABEL (BB_END (jump_block)) = label; 1162 LABEL_NUSES (label)++; 1163 } 1164 1165 emit_barrier_after (BB_END (jump_block)); 1166 redirect_edge_succ_nodup (e, target); 1167 1168 if (abnormal_edge_flags) 1169 make_edge (src, target, abnormal_edge_flags); 1170 1171 return new_bb; 1172} 1173 1174/* Edge E is assumed to be fallthru edge. Emit needed jump instruction 1175 (and possibly create new basic block) to make edge non-fallthru. 1176 Return newly created BB or NULL if none. */ 1177 1178basic_block 1179force_nonfallthru (edge e) 1180{ 1181 return force_nonfallthru_and_redirect (e, e->dest); 1182} 1183 1184/* Redirect edge even at the expense of creating new jump insn or 1185 basic block. Return new basic block if created, NULL otherwise. 1186 Conversion must be possible. */ 1187 1188static basic_block 1189rtl_redirect_edge_and_branch_force (edge e, basic_block target) 1190{ 1191 if (redirect_edge_and_branch (e, target) 1192 || e->dest == target) 1193 return NULL; 1194 1195 /* In case the edge redirection failed, try to force it to be non-fallthru 1196 and redirect newly created simplejump. */ 1197 return force_nonfallthru_and_redirect (e, target); 1198} 1199 1200/* The given edge should potentially be a fallthru edge. If that is in 1201 fact true, delete the jump and barriers that are in the way. */ 1202 1203static void 1204rtl_tidy_fallthru_edge (edge e) 1205{ 1206 rtx q; 1207 basic_block b = e->src, c = b->next_bb; 1208 1209 /* ??? In a late-running flow pass, other folks may have deleted basic 1210 blocks by nopping out blocks, leaving multiple BARRIERs between here 1211 and the target label. They ought to be chastised and fixed. 1212 1213 We can also wind up with a sequence of undeletable labels between 1214 one block and the next. 1215 1216 So search through a sequence of barriers, labels, and notes for 1217 the head of block C and assert that we really do fall through. */ 1218 1219 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q)) 1220 if (INSN_P (q)) 1221 return; 1222 1223 /* Remove what will soon cease being the jump insn from the source block. 1224 If block B consisted only of this single jump, turn it into a deleted 1225 note. */ 1226 q = BB_END (b); 1227 if (JUMP_P (q) 1228 && onlyjump_p (q) 1229 && (any_uncondjump_p (q) 1230 || single_succ_p (b))) 1231 { 1232#ifdef HAVE_cc0 1233 /* If this was a conditional jump, we need to also delete 1234 the insn that set cc0. */ 1235 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q))) 1236 q = PREV_INSN (q); 1237#endif 1238 1239 q = PREV_INSN (q); 1240 1241 /* We don't want a block to end on a line-number note since that has 1242 the potential of changing the code between -g and not -g. */ 1243 while (NOTE_P (q) && NOTE_LINE_NUMBER (q) >= 0) 1244 q = PREV_INSN (q); 1245 } 1246 1247 /* Selectively unlink the sequence. */ 1248 if (q != PREV_INSN (BB_HEAD (c))) 1249 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c))); 1250 1251 e->flags |= EDGE_FALLTHRU; 1252} 1253 1254/* Helper function for split_edge. Return true in case edge BB2 to BB1 1255 is back edge of syntactic loop. */ 1256 1257static bool 1258back_edge_of_syntactic_loop_p (basic_block bb1, basic_block bb2) 1259{ 1260 rtx insn; 1261 int count = 0; 1262 basic_block bb; 1263 1264 if (bb1 == bb2) 1265 return true; 1266 1267 /* ??? Could we guarantee that bb indices are monotone, so that we could 1268 just compare them? */ 1269 for (bb = bb1; bb && bb != bb2; bb = bb->next_bb) 1270 continue; 1271 1272 if (!bb) 1273 return false; 1274 1275 for (insn = BB_END (bb1); insn != BB_HEAD (bb2) && count >= 0; 1276 insn = NEXT_INSN (insn)) 1277 if (NOTE_P (insn)) 1278 { 1279 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) 1280 count++; 1281 else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) 1282 count--; 1283 } 1284 1285 return count >= 0; 1286} 1287 1288/* Should move basic block BB after basic block AFTER. NIY. */ 1289 1290static bool 1291rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED, 1292 basic_block after ATTRIBUTE_UNUSED) 1293{ 1294 return false; 1295} 1296 1297/* Split a (typically critical) edge. Return the new block. 1298 The edge must not be abnormal. 1299 1300 ??? The code generally expects to be called on critical edges. 1301 The case of a block ending in an unconditional jump to a 1302 block with multiple predecessors is not handled optimally. */ 1303 1304static basic_block 1305rtl_split_edge (edge edge_in) 1306{ 1307 basic_block bb; 1308 rtx before; 1309 1310 /* Abnormal edges cannot be split. */ 1311 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL)); 1312 1313 /* We are going to place the new block in front of edge destination. 1314 Avoid existence of fallthru predecessors. */ 1315 if ((edge_in->flags & EDGE_FALLTHRU) == 0) 1316 { 1317 edge e; 1318 edge_iterator ei; 1319 1320 FOR_EACH_EDGE (e, ei, edge_in->dest->preds) 1321 if (e->flags & EDGE_FALLTHRU) 1322 break; 1323 1324 if (e) 1325 force_nonfallthru (e); 1326 } 1327 1328 /* Create the basic block note. 1329 1330 Where we place the note can have a noticeable impact on the generated 1331 code. Consider this cfg: 1332 1333 E 1334 | 1335 0 1336 / \ 1337 +->1-->2--->E 1338 | | 1339 +--+ 1340 1341 If we need to insert an insn on the edge from block 0 to block 1, 1342 we want to ensure the instructions we insert are outside of any 1343 loop notes that physically sit between block 0 and block 1. Otherwise 1344 we confuse the loop optimizer into thinking the loop is a phony. */ 1345 1346 if (edge_in->dest != EXIT_BLOCK_PTR 1347 && PREV_INSN (BB_HEAD (edge_in->dest)) 1348 && NOTE_P (PREV_INSN (BB_HEAD (edge_in->dest))) 1349 && (NOTE_LINE_NUMBER (PREV_INSN (BB_HEAD (edge_in->dest))) 1350 == NOTE_INSN_LOOP_BEG) 1351 && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src)) 1352 before = PREV_INSN (BB_HEAD (edge_in->dest)); 1353 else if (edge_in->dest != EXIT_BLOCK_PTR) 1354 before = BB_HEAD (edge_in->dest); 1355 else 1356 before = NULL_RTX; 1357 1358 /* If this is a fall through edge to the exit block, the blocks might be 1359 not adjacent, and the right place is the after the source. */ 1360 if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR) 1361 { 1362 before = NEXT_INSN (BB_END (edge_in->src)); 1363 if (before 1364 && NOTE_P (before) 1365 && NOTE_LINE_NUMBER (before) == NOTE_INSN_LOOP_END) 1366 before = NEXT_INSN (before); 1367 bb = create_basic_block (before, NULL, edge_in->src); 1368 BB_COPY_PARTITION (bb, edge_in->src); 1369 } 1370 else 1371 { 1372 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb); 1373 /* ??? Why not edge_in->dest->prev_bb here? */ 1374 BB_COPY_PARTITION (bb, edge_in->dest); 1375 } 1376 1377 /* ??? This info is likely going to be out of date very soon. */ 1378 if (edge_in->dest->il.rtl->global_live_at_start) 1379 { 1380 bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1381 bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1382 COPY_REG_SET (bb->il.rtl->global_live_at_start, 1383 edge_in->dest->il.rtl->global_live_at_start); 1384 COPY_REG_SET (bb->il.rtl->global_live_at_end, 1385 edge_in->dest->il.rtl->global_live_at_start); 1386 } 1387 1388 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU); 1389 1390 /* For non-fallthru edges, we must adjust the predecessor's 1391 jump instruction to target our new block. */ 1392 if ((edge_in->flags & EDGE_FALLTHRU) == 0) 1393 { 1394 edge redirected = redirect_edge_and_branch (edge_in, bb); 1395 gcc_assert (redirected); 1396 } 1397 else 1398 redirect_edge_succ (edge_in, bb); 1399 1400 return bb; 1401} 1402 1403/* Queue instructions for insertion on an edge between two basic blocks. 1404 The new instructions and basic blocks (if any) will not appear in the 1405 CFG until commit_edge_insertions is called. */ 1406 1407void 1408insert_insn_on_edge (rtx pattern, edge e) 1409{ 1410 /* We cannot insert instructions on an abnormal critical edge. 1411 It will be easier to find the culprit if we die now. */ 1412 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))); 1413 1414 if (e->insns.r == NULL_RTX) 1415 start_sequence (); 1416 else 1417 push_to_sequence (e->insns.r); 1418 1419 emit_insn (pattern); 1420 1421 e->insns.r = get_insns (); 1422 end_sequence (); 1423} 1424 1425/* Called from safe_insert_insn_on_edge through note_stores, marks live 1426 registers that are killed by the store. */ 1427static void 1428mark_killed_regs (rtx reg, rtx set ATTRIBUTE_UNUSED, void *data) 1429{ 1430 regset killed = data; 1431 int regno, i; 1432 1433 if (GET_CODE (reg) == SUBREG) 1434 reg = SUBREG_REG (reg); 1435 if (!REG_P (reg)) 1436 return; 1437 regno = REGNO (reg); 1438 if (regno >= FIRST_PSEUDO_REGISTER) 1439 SET_REGNO_REG_SET (killed, regno); 1440 else 1441 { 1442 for (i = 0; i < (int) hard_regno_nregs[regno][GET_MODE (reg)]; i++) 1443 SET_REGNO_REG_SET (killed, regno + i); 1444 } 1445} 1446 1447/* Similar to insert_insn_on_edge, tries to put INSN to edge E. Additionally 1448 it checks whether this will not clobber the registers that are live on the 1449 edge (i.e. it requires liveness information to be up-to-date) and if there 1450 are some, then it tries to save and restore them. Returns true if 1451 successful. */ 1452bool 1453safe_insert_insn_on_edge (rtx insn, edge e) 1454{ 1455 rtx x; 1456 regset killed; 1457 rtx save_regs = NULL_RTX; 1458 unsigned regno; 1459 enum machine_mode mode; 1460 reg_set_iterator rsi; 1461 1462 killed = ALLOC_REG_SET (®_obstack); 1463 1464 for (x = insn; x; x = NEXT_INSN (x)) 1465 if (INSN_P (x)) 1466 note_stores (PATTERN (x), mark_killed_regs, killed); 1467 1468 /* Mark all hard registers as killed. Register allocator/reload cannot 1469 cope with the situation when life range of hard register spans operation 1470 for that the appropriate register is needed, i.e. it would be unsafe to 1471 extend the life ranges of hard registers. */ 1472 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 1473 if (!fixed_regs[regno] 1474 && !REGNO_PTR_FRAME_P (regno)) 1475 SET_REGNO_REG_SET (killed, regno); 1476 1477 bitmap_and_into (killed, e->dest->il.rtl->global_live_at_start); 1478 1479 EXECUTE_IF_SET_IN_REG_SET (killed, 0, regno, rsi) 1480 { 1481 mode = regno < FIRST_PSEUDO_REGISTER 1482 ? reg_raw_mode[regno] 1483 : GET_MODE (regno_reg_rtx[regno]); 1484 if (mode == VOIDmode) 1485 return false; 1486 1487 /* Avoid copying in CCmode if we can't. */ 1488 if (!can_copy_p (mode)) 1489 return false; 1490 1491 save_regs = alloc_EXPR_LIST (0, 1492 alloc_EXPR_LIST (0, 1493 gen_reg_rtx (mode), 1494 gen_raw_REG (mode, regno)), 1495 save_regs); 1496 } 1497 1498 if (save_regs) 1499 { 1500 rtx from, to; 1501 1502 start_sequence (); 1503 for (x = save_regs; x; x = XEXP (x, 1)) 1504 { 1505 from = XEXP (XEXP (x, 0), 1); 1506 to = XEXP (XEXP (x, 0), 0); 1507 emit_move_insn (to, from); 1508 } 1509 emit_insn (insn); 1510 for (x = save_regs; x; x = XEXP (x, 1)) 1511 { 1512 from = XEXP (XEXP (x, 0), 0); 1513 to = XEXP (XEXP (x, 0), 1); 1514 emit_move_insn (to, from); 1515 } 1516 insn = get_insns (); 1517 end_sequence (); 1518 free_EXPR_LIST_list (&save_regs); 1519 } 1520 insert_insn_on_edge (insn, e); 1521 1522 FREE_REG_SET (killed); 1523 1524 return true; 1525} 1526 1527/* Update the CFG for the instructions queued on edge E. */ 1528 1529static void 1530commit_one_edge_insertion (edge e, int watch_calls) 1531{ 1532 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last; 1533 basic_block bb = NULL; 1534 1535 /* Pull the insns off the edge now since the edge might go away. */ 1536 insns = e->insns.r; 1537 e->insns.r = NULL_RTX; 1538 1539 /* Special case -- avoid inserting code between call and storing 1540 its return value. */ 1541 if (watch_calls && (e->flags & EDGE_FALLTHRU) 1542 && single_pred_p (e->dest) 1543 && e->src != ENTRY_BLOCK_PTR 1544 && CALL_P (BB_END (e->src))) 1545 { 1546 rtx next = next_nonnote_insn (BB_END (e->src)); 1547 1548 after = BB_HEAD (e->dest); 1549 /* The first insn after the call may be a stack pop, skip it. */ 1550 while (next 1551 && keep_with_call_p (next)) 1552 { 1553 after = next; 1554 next = next_nonnote_insn (next); 1555 } 1556 bb = e->dest; 1557 } 1558 if (!before && !after) 1559 { 1560 /* Figure out where to put these things. If the destination has 1561 one predecessor, insert there. Except for the exit block. */ 1562 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR) 1563 { 1564 bb = e->dest; 1565 1566 /* Get the location correct wrt a code label, and "nice" wrt 1567 a basic block note, and before everything else. */ 1568 tmp = BB_HEAD (bb); 1569 if (LABEL_P (tmp)) 1570 tmp = NEXT_INSN (tmp); 1571 if (NOTE_INSN_BASIC_BLOCK_P (tmp)) 1572 tmp = NEXT_INSN (tmp); 1573 if (tmp == BB_HEAD (bb)) 1574 before = tmp; 1575 else if (tmp) 1576 after = PREV_INSN (tmp); 1577 else 1578 after = get_last_insn (); 1579 } 1580 1581 /* If the source has one successor and the edge is not abnormal, 1582 insert there. Except for the entry block. */ 1583 else if ((e->flags & EDGE_ABNORMAL) == 0 1584 && single_succ_p (e->src) 1585 && e->src != ENTRY_BLOCK_PTR) 1586 { 1587 bb = e->src; 1588 1589 /* It is possible to have a non-simple jump here. Consider a target 1590 where some forms of unconditional jumps clobber a register. This 1591 happens on the fr30 for example. 1592 1593 We know this block has a single successor, so we can just emit 1594 the queued insns before the jump. */ 1595 if (JUMP_P (BB_END (bb))) 1596 for (before = BB_END (bb); 1597 NOTE_P (PREV_INSN (before)) 1598 && NOTE_LINE_NUMBER (PREV_INSN (before)) == 1599 NOTE_INSN_LOOP_BEG; before = PREV_INSN (before)) 1600 ; 1601 else 1602 { 1603 /* We'd better be fallthru, or we've lost track of 1604 what's what. */ 1605 gcc_assert (e->flags & EDGE_FALLTHRU); 1606 1607 after = BB_END (bb); 1608 } 1609 } 1610 /* Otherwise we must split the edge. */ 1611 else 1612 { 1613 bb = split_edge (e); 1614 after = BB_END (bb); 1615 1616 if (flag_reorder_blocks_and_partition 1617 && targetm.have_named_sections 1618 && e->src != ENTRY_BLOCK_PTR 1619 && BB_PARTITION (e->src) == BB_COLD_PARTITION 1620 && !(e->flags & EDGE_CROSSING)) 1621 { 1622 rtx bb_note, cur_insn; 1623 1624 bb_note = NULL_RTX; 1625 for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb)); 1626 cur_insn = NEXT_INSN (cur_insn)) 1627 if (NOTE_P (cur_insn) 1628 && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK) 1629 { 1630 bb_note = cur_insn; 1631 break; 1632 } 1633 1634 if (JUMP_P (BB_END (bb)) 1635 && !any_condjump_p (BB_END (bb)) 1636 && (single_succ_edge (bb)->flags & EDGE_CROSSING)) 1637 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST 1638 (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); 1639 } 1640 } 1641 } 1642 1643 /* Now that we've found the spot, do the insertion. */ 1644 1645 if (before) 1646 { 1647 emit_insn_before_noloc (insns, before); 1648 last = prev_nonnote_insn (before); 1649 } 1650 else 1651 last = emit_insn_after_noloc (insns, after); 1652 1653 if (returnjump_p (last)) 1654 { 1655 /* ??? Remove all outgoing edges from BB and add one for EXIT. 1656 This is not currently a problem because this only happens 1657 for the (single) epilogue, which already has a fallthru edge 1658 to EXIT. */ 1659 1660 e = single_succ_edge (bb); 1661 gcc_assert (e->dest == EXIT_BLOCK_PTR 1662 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU)); 1663 1664 e->flags &= ~EDGE_FALLTHRU; 1665 emit_barrier_after (last); 1666 1667 if (before) 1668 delete_insn (before); 1669 } 1670 else 1671 gcc_assert (!JUMP_P (last)); 1672 1673 /* Mark the basic block for find_many_sub_basic_blocks. */ 1674 bb->aux = &bb->aux; 1675} 1676 1677/* Update the CFG for all queued instructions. */ 1678 1679void 1680commit_edge_insertions (void) 1681{ 1682 basic_block bb; 1683 sbitmap blocks; 1684 bool changed = false; 1685 1686#ifdef ENABLE_CHECKING 1687 verify_flow_info (); 1688#endif 1689 1690 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 1691 { 1692 edge e; 1693 edge_iterator ei; 1694 1695 FOR_EACH_EDGE (e, ei, bb->succs) 1696 if (e->insns.r) 1697 { 1698 changed = true; 1699 commit_one_edge_insertion (e, false); 1700 } 1701 } 1702 1703 if (!changed) 1704 return; 1705 1706 blocks = sbitmap_alloc (last_basic_block); 1707 sbitmap_zero (blocks); 1708 FOR_EACH_BB (bb) 1709 if (bb->aux) 1710 { 1711 SET_BIT (blocks, bb->index); 1712 /* Check for forgotten bb->aux values before commit_edge_insertions 1713 call. */ 1714 gcc_assert (bb->aux == &bb->aux); 1715 bb->aux = NULL; 1716 } 1717 find_many_sub_basic_blocks (blocks); 1718 sbitmap_free (blocks); 1719} 1720 1721/* Update the CFG for all queued instructions, taking special care of inserting 1722 code on edges between call and storing its return value. */ 1723 1724void 1725commit_edge_insertions_watch_calls (void) 1726{ 1727 basic_block bb; 1728 sbitmap blocks; 1729 bool changed = false; 1730 1731#ifdef ENABLE_CHECKING 1732 verify_flow_info (); 1733#endif 1734 1735 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 1736 { 1737 edge e; 1738 edge_iterator ei; 1739 1740 FOR_EACH_EDGE (e, ei, bb->succs) 1741 if (e->insns.r) 1742 { 1743 changed = true; 1744 commit_one_edge_insertion (e, true); 1745 } 1746 } 1747 1748 if (!changed) 1749 return; 1750 1751 blocks = sbitmap_alloc (last_basic_block); 1752 sbitmap_zero (blocks); 1753 FOR_EACH_BB (bb) 1754 if (bb->aux) 1755 { 1756 SET_BIT (blocks, bb->index); 1757 /* Check for forgotten bb->aux values before commit_edge_insertions 1758 call. */ 1759 gcc_assert (bb->aux == &bb->aux); 1760 bb->aux = NULL; 1761 } 1762 find_many_sub_basic_blocks (blocks); 1763 sbitmap_free (blocks); 1764} 1765 1766/* Print out RTL-specific basic block information (live information 1767 at start and end). */ 1768 1769static void 1770rtl_dump_bb (basic_block bb, FILE *outf, int indent) 1771{ 1772 rtx insn; 1773 rtx last; 1774 char *s_indent; 1775 1776 s_indent = alloca ((size_t) indent + 1); 1777 memset (s_indent, ' ', (size_t) indent); 1778 s_indent[indent] = '\0'; 1779 1780 fprintf (outf, ";;%s Registers live at start: ", s_indent); 1781 dump_regset (bb->il.rtl->global_live_at_start, outf); 1782 putc ('\n', outf); 1783 1784 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last; 1785 insn = NEXT_INSN (insn)) 1786 print_rtl_single (outf, insn); 1787 1788 fprintf (outf, ";;%s Registers live at end: ", s_indent); 1789 dump_regset (bb->il.rtl->global_live_at_end, outf); 1790 putc ('\n', outf); 1791} 1792 1793/* Like print_rtl, but also print out live information for the start of each 1794 basic block. */ 1795 1796void 1797print_rtl_with_bb (FILE *outf, rtx rtx_first) 1798{ 1799 rtx tmp_rtx; 1800 1801 if (rtx_first == 0) 1802 fprintf (outf, "(nil)\n"); 1803 else 1804 { 1805 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB }; 1806 int max_uid = get_max_uid (); 1807 basic_block *start = xcalloc (max_uid, sizeof (basic_block)); 1808 basic_block *end = xcalloc (max_uid, sizeof (basic_block)); 1809 enum bb_state *in_bb_p = xcalloc (max_uid, sizeof (enum bb_state)); 1810 1811 basic_block bb; 1812 1813 FOR_EACH_BB_REVERSE (bb) 1814 { 1815 rtx x; 1816 1817 start[INSN_UID (BB_HEAD (bb))] = bb; 1818 end[INSN_UID (BB_END (bb))] = bb; 1819 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x)) 1820 { 1821 enum bb_state state = IN_MULTIPLE_BB; 1822 1823 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB) 1824 state = IN_ONE_BB; 1825 in_bb_p[INSN_UID (x)] = state; 1826 1827 if (x == BB_END (bb)) 1828 break; 1829 } 1830 } 1831 1832 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx)) 1833 { 1834 int did_output; 1835 1836 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL) 1837 { 1838 fprintf (outf, ";; Start of basic block %d, registers live:", 1839 bb->index); 1840 dump_regset (bb->il.rtl->global_live_at_start, outf); 1841 putc ('\n', outf); 1842 } 1843 1844 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB 1845 && !NOTE_P (tmp_rtx) 1846 && !BARRIER_P (tmp_rtx)) 1847 fprintf (outf, ";; Insn is not within a basic block\n"); 1848 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB) 1849 fprintf (outf, ";; Insn is in multiple basic blocks\n"); 1850 1851 did_output = print_rtl_single (outf, tmp_rtx); 1852 1853 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL) 1854 { 1855 fprintf (outf, ";; End of basic block %d, registers live:\n", 1856 bb->index); 1857 dump_regset (bb->il.rtl->global_live_at_end, outf); 1858 putc ('\n', outf); 1859 } 1860 1861 if (did_output) 1862 putc ('\n', outf); 1863 } 1864 1865 free (start); 1866 free (end); 1867 free (in_bb_p); 1868 } 1869 1870 if (current_function_epilogue_delay_list != 0) 1871 { 1872 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n"); 1873 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0; 1874 tmp_rtx = XEXP (tmp_rtx, 1)) 1875 print_rtl_single (outf, XEXP (tmp_rtx, 0)); 1876 } 1877} 1878 1879void 1880update_br_prob_note (basic_block bb) 1881{ 1882 rtx note; 1883 if (!JUMP_P (BB_END (bb))) 1884 return; 1885 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX); 1886 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability) 1887 return; 1888 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability); 1889} 1890 1891/* Verify the CFG and RTL consistency common for both underlying RTL and 1892 cfglayout RTL. 1893 1894 Currently it does following checks: 1895 1896 - test head/end pointers 1897 - overlapping of basic blocks 1898 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note) 1899 - tails of basic blocks (ensure that boundary is necessary) 1900 - scans body of the basic block for JUMP_INSN, CODE_LABEL 1901 and NOTE_INSN_BASIC_BLOCK 1902 - verify that no fall_thru edge crosses hot/cold partition boundaries 1903 1904 In future it can be extended check a lot of other stuff as well 1905 (reachability of basic blocks, life information, etc. etc.). */ 1906 1907static int 1908rtl_verify_flow_info_1 (void) 1909{ 1910 const int max_uid = get_max_uid (); 1911 rtx last_head = get_last_insn (); 1912 basic_block *bb_info; 1913 rtx x; 1914 int err = 0; 1915 basic_block bb; 1916 1917 bb_info = xcalloc (max_uid, sizeof (basic_block)); 1918 1919 FOR_EACH_BB_REVERSE (bb) 1920 { 1921 rtx head = BB_HEAD (bb); 1922 rtx end = BB_END (bb); 1923 1924 /* Verify the end of the basic block is in the INSN chain. */ 1925 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x)) 1926 if (x == end) 1927 break; 1928 1929 if (!(bb->flags & BB_RTL)) 1930 { 1931 error ("BB_RTL flag not set for block %d", bb->index); 1932 err = 1; 1933 } 1934 1935 if (!x) 1936 { 1937 error ("end insn %d for block %d not found in the insn stream", 1938 INSN_UID (end), bb->index); 1939 err = 1; 1940 } 1941 1942 /* Work backwards from the end to the head of the basic block 1943 to verify the head is in the RTL chain. */ 1944 for (; x != NULL_RTX; x = PREV_INSN (x)) 1945 { 1946 /* While walking over the insn chain, verify insns appear 1947 in only one basic block and initialize the BB_INFO array 1948 used by other passes. */ 1949 if (bb_info[INSN_UID (x)] != NULL) 1950 { 1951 error ("insn %d is in multiple basic blocks (%d and %d)", 1952 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index); 1953 err = 1; 1954 } 1955 1956 bb_info[INSN_UID (x)] = bb; 1957 1958 if (x == head) 1959 break; 1960 } 1961 if (!x) 1962 { 1963 error ("head insn %d for block %d not found in the insn stream", 1964 INSN_UID (head), bb->index); 1965 err = 1; 1966 } 1967 1968 last_head = x; 1969 } 1970 1971 /* Now check the basic blocks (boundaries etc.) */ 1972 FOR_EACH_BB_REVERSE (bb) 1973 { 1974 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0; 1975 edge e, fallthru = NULL; 1976 rtx note; 1977 edge_iterator ei; 1978 1979 if (JUMP_P (BB_END (bb)) 1980 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX)) 1981 && EDGE_COUNT (bb->succs) >= 2 1982 && any_condjump_p (BB_END (bb))) 1983 { 1984 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability 1985 && profile_status != PROFILE_ABSENT) 1986 { 1987 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i", 1988 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability); 1989 err = 1; 1990 } 1991 } 1992 FOR_EACH_EDGE (e, ei, bb->succs) 1993 { 1994 if (e->flags & EDGE_FALLTHRU) 1995 { 1996 n_fallthru++, fallthru = e; 1997 if ((e->flags & EDGE_CROSSING) 1998 || (BB_PARTITION (e->src) != BB_PARTITION (e->dest) 1999 && e->src != ENTRY_BLOCK_PTR 2000 && e->dest != EXIT_BLOCK_PTR)) 2001 { 2002 error ("fallthru edge crosses section boundary (bb %i)", 2003 e->src->index); 2004 err = 1; 2005 } 2006 } 2007 2008 if ((e->flags & ~(EDGE_DFS_BACK 2009 | EDGE_CAN_FALLTHRU 2010 | EDGE_IRREDUCIBLE_LOOP 2011 | EDGE_LOOP_EXIT 2012 | EDGE_CROSSING)) == 0) 2013 n_branch++; 2014 2015 if (e->flags & EDGE_ABNORMAL_CALL) 2016 n_call++; 2017 2018 if (e->flags & EDGE_EH) 2019 n_eh++; 2020 else if (e->flags & EDGE_ABNORMAL) 2021 n_abnormal++; 2022 } 2023 2024 if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX 2025 && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX)) 2026 { 2027 error ("missing REG_EH_REGION note in the end of bb %i", bb->index); 2028 err = 1; 2029 } 2030 if (n_branch 2031 && (!JUMP_P (BB_END (bb)) 2032 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb)) 2033 || any_condjump_p (BB_END (bb)))))) 2034 { 2035 error ("too many outgoing branch edges from bb %i", bb->index); 2036 err = 1; 2037 } 2038 if (n_fallthru && any_uncondjump_p (BB_END (bb))) 2039 { 2040 error ("fallthru edge after unconditional jump %i", bb->index); 2041 err = 1; 2042 } 2043 if (n_branch != 1 && any_uncondjump_p (BB_END (bb))) 2044 { 2045 error ("wrong amount of branch edges after unconditional jump %i", bb->index); 2046 err = 1; 2047 } 2048 if (n_branch != 1 && any_condjump_p (BB_END (bb)) 2049 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest)) 2050 { 2051 error ("wrong amount of branch edges after conditional jump %i", 2052 bb->index); 2053 err = 1; 2054 } 2055 if (n_call && !CALL_P (BB_END (bb))) 2056 { 2057 error ("call edges for non-call insn in bb %i", bb->index); 2058 err = 1; 2059 } 2060 if (n_abnormal 2061 && (!CALL_P (BB_END (bb)) && n_call != n_abnormal) 2062 && (!JUMP_P (BB_END (bb)) 2063 || any_condjump_p (BB_END (bb)) 2064 || any_uncondjump_p (BB_END (bb)))) 2065 { 2066 error ("abnormal edges for no purpose in bb %i", bb->index); 2067 err = 1; 2068 } 2069 2070 for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x)) 2071 /* We may have a barrier inside a basic block before dead code 2072 elimination. There is no BLOCK_FOR_INSN field in a barrier. */ 2073 if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb) 2074 { 2075 debug_rtx (x); 2076 if (! BLOCK_FOR_INSN (x)) 2077 error 2078 ("insn %d inside basic block %d but block_for_insn is NULL", 2079 INSN_UID (x), bb->index); 2080 else 2081 error 2082 ("insn %d inside basic block %d but block_for_insn is %i", 2083 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index); 2084 2085 err = 1; 2086 } 2087 2088 /* OK pointers are correct. Now check the header of basic 2089 block. It ought to contain optional CODE_LABEL followed 2090 by NOTE_BASIC_BLOCK. */ 2091 x = BB_HEAD (bb); 2092 if (LABEL_P (x)) 2093 { 2094 if (BB_END (bb) == x) 2095 { 2096 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 2097 bb->index); 2098 err = 1; 2099 } 2100 2101 x = NEXT_INSN (x); 2102 } 2103 2104 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb) 2105 { 2106 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d", 2107 bb->index); 2108 err = 1; 2109 } 2110 2111 if (BB_END (bb) == x) 2112 /* Do checks for empty blocks here. */ 2113 ; 2114 else 2115 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x)) 2116 { 2117 if (NOTE_INSN_BASIC_BLOCK_P (x)) 2118 { 2119 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d", 2120 INSN_UID (x), bb->index); 2121 err = 1; 2122 } 2123 2124 if (x == BB_END (bb)) 2125 break; 2126 2127 if (control_flow_insn_p (x)) 2128 { 2129 error ("in basic block %d:", bb->index); 2130 fatal_insn ("flow control insn inside a basic block", x); 2131 } 2132 } 2133 } 2134 2135 /* Clean up. */ 2136 free (bb_info); 2137 return err; 2138} 2139 2140/* Verify the CFG and RTL consistency common for both underlying RTL and 2141 cfglayout RTL. 2142 2143 Currently it does following checks: 2144 - all checks of rtl_verify_flow_info_1 2145 - check that all insns are in the basic blocks 2146 (except the switch handling code, barriers and notes) 2147 - check that all returns are followed by barriers 2148 - check that all fallthru edge points to the adjacent blocks. */ 2149static int 2150rtl_verify_flow_info (void) 2151{ 2152 basic_block bb; 2153 int err = rtl_verify_flow_info_1 (); 2154 rtx x; 2155 int num_bb_notes; 2156 const rtx rtx_first = get_insns (); 2157 basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL; 2158 2159 FOR_EACH_BB_REVERSE (bb) 2160 { 2161 edge e; 2162 edge_iterator ei; 2163 2164 if (bb->predictions) 2165 { 2166 error ("bb prediction set for block %i, but it is not used in RTL land", bb->index); 2167 err = 1; 2168 } 2169 2170 FOR_EACH_EDGE (e, ei, bb->succs) 2171 if (e->flags & EDGE_FALLTHRU) 2172 break; 2173 if (!e) 2174 { 2175 rtx insn; 2176 2177 /* Ensure existence of barrier in BB with no fallthru edges. */ 2178 for (insn = BB_END (bb); !insn || !BARRIER_P (insn); 2179 insn = NEXT_INSN (insn)) 2180 if (!insn 2181 || (NOTE_P (insn) 2182 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK)) 2183 { 2184 error ("missing barrier after block %i", bb->index); 2185 err = 1; 2186 break; 2187 } 2188 } 2189 else if (e->src != ENTRY_BLOCK_PTR 2190 && e->dest != EXIT_BLOCK_PTR) 2191 { 2192 rtx insn; 2193 2194 if (e->src->next_bb != e->dest) 2195 { 2196 error 2197 ("verify_flow_info: Incorrect blocks for fallthru %i->%i", 2198 e->src->index, e->dest->index); 2199 err = 1; 2200 } 2201 else 2202 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest); 2203 insn = NEXT_INSN (insn)) 2204 if (BARRIER_P (insn) || INSN_P (insn)) 2205 { 2206 error ("verify_flow_info: Incorrect fallthru %i->%i", 2207 e->src->index, e->dest->index); 2208 fatal_insn ("wrong insn in the fallthru edge", insn); 2209 err = 1; 2210 } 2211 } 2212 } 2213 2214 num_bb_notes = 0; 2215 last_bb_seen = ENTRY_BLOCK_PTR; 2216 2217 for (x = rtx_first; x; x = NEXT_INSN (x)) 2218 { 2219 if (NOTE_INSN_BASIC_BLOCK_P (x)) 2220 { 2221 bb = NOTE_BASIC_BLOCK (x); 2222 2223 num_bb_notes++; 2224 if (bb != last_bb_seen->next_bb) 2225 internal_error ("basic blocks not laid down consecutively"); 2226 2227 curr_bb = last_bb_seen = bb; 2228 } 2229 2230 if (!curr_bb) 2231 { 2232 switch (GET_CODE (x)) 2233 { 2234 case BARRIER: 2235 case NOTE: 2236 break; 2237 2238 case CODE_LABEL: 2239 /* An addr_vec is placed outside any basic block. */ 2240 if (NEXT_INSN (x) 2241 && JUMP_P (NEXT_INSN (x)) 2242 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC 2243 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC)) 2244 x = NEXT_INSN (x); 2245 2246 /* But in any case, non-deletable labels can appear anywhere. */ 2247 break; 2248 2249 default: 2250 fatal_insn ("insn outside basic block", x); 2251 } 2252 } 2253 2254 if (JUMP_P (x) 2255 && returnjump_p (x) && ! condjump_p (x) 2256 && ! (NEXT_INSN (x) && BARRIER_P (NEXT_INSN (x)))) 2257 fatal_insn ("return not followed by barrier", x); 2258 if (curr_bb && x == BB_END (curr_bb)) 2259 curr_bb = NULL; 2260 } 2261 2262 if (num_bb_notes != n_basic_blocks) 2263 internal_error 2264 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)", 2265 num_bb_notes, n_basic_blocks); 2266 2267 return err; 2268} 2269 2270/* Assume that the preceding pass has possibly eliminated jump instructions 2271 or converted the unconditional jumps. Eliminate the edges from CFG. 2272 Return true if any edges are eliminated. */ 2273 2274bool 2275purge_dead_edges (basic_block bb) 2276{ 2277 edge e; 2278 rtx insn = BB_END (bb), note; 2279 bool purged = false; 2280 bool found; 2281 edge_iterator ei; 2282 2283 /* If this instruction cannot trap, remove REG_EH_REGION notes. */ 2284 if (NONJUMP_INSN_P (insn) 2285 && (note = find_reg_note (insn, REG_EH_REGION, NULL))) 2286 { 2287 rtx eqnote; 2288 2289 if (! may_trap_p (PATTERN (insn)) 2290 || ((eqnote = find_reg_equal_equiv_note (insn)) 2291 && ! may_trap_p (XEXP (eqnote, 0)))) 2292 remove_note (insn, note); 2293 } 2294 2295 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */ 2296 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 2297 { 2298 /* There are three types of edges we need to handle correctly here: EH 2299 edges, abnormal call EH edges, and abnormal call non-EH edges. The 2300 latter can appear when nonlocal gotos are used. */ 2301 if (e->flags & EDGE_EH) 2302 { 2303 if (can_throw_internal (BB_END (bb)) 2304 /* If this is a call edge, verify that this is a call insn. */ 2305 && (! (e->flags & EDGE_ABNORMAL_CALL) 2306 || CALL_P (BB_END (bb)))) 2307 { 2308 ei_next (&ei); 2309 continue; 2310 } 2311 } 2312 else if (e->flags & EDGE_ABNORMAL_CALL) 2313 { 2314 if (CALL_P (BB_END (bb)) 2315 && (! (note = find_reg_note (insn, REG_EH_REGION, NULL)) 2316 || INTVAL (XEXP (note, 0)) >= 0)) 2317 { 2318 ei_next (&ei); 2319 continue; 2320 } 2321 } 2322 else 2323 { 2324 ei_next (&ei); 2325 continue; 2326 } 2327 2328 remove_edge (e); 2329 bb->flags |= BB_DIRTY; 2330 purged = true; 2331 } 2332 2333 if (JUMP_P (insn)) 2334 { 2335 rtx note; 2336 edge b,f; 2337 edge_iterator ei; 2338 2339 /* We do care only about conditional jumps and simplejumps. */ 2340 if (!any_condjump_p (insn) 2341 && !returnjump_p (insn) 2342 && !simplejump_p (insn)) 2343 return purged; 2344 2345 /* Branch probability/prediction notes are defined only for 2346 condjumps. We've possibly turned condjump into simplejump. */ 2347 if (simplejump_p (insn)) 2348 { 2349 note = find_reg_note (insn, REG_BR_PROB, NULL); 2350 if (note) 2351 remove_note (insn, note); 2352 while ((note = find_reg_note (insn, REG_BR_PRED, NULL))) 2353 remove_note (insn, note); 2354 } 2355 2356 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 2357 { 2358 /* Avoid abnormal flags to leak from computed jumps turned 2359 into simplejumps. */ 2360 2361 e->flags &= ~EDGE_ABNORMAL; 2362 2363 /* See if this edge is one we should keep. */ 2364 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn)) 2365 /* A conditional jump can fall through into the next 2366 block, so we should keep the edge. */ 2367 { 2368 ei_next (&ei); 2369 continue; 2370 } 2371 else if (e->dest != EXIT_BLOCK_PTR 2372 && BB_HEAD (e->dest) == JUMP_LABEL (insn)) 2373 /* If the destination block is the target of the jump, 2374 keep the edge. */ 2375 { 2376 ei_next (&ei); 2377 continue; 2378 } 2379 else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn)) 2380 /* If the destination block is the exit block, and this 2381 instruction is a return, then keep the edge. */ 2382 { 2383 ei_next (&ei); 2384 continue; 2385 } 2386 else if ((e->flags & EDGE_EH) && can_throw_internal (insn)) 2387 /* Keep the edges that correspond to exceptions thrown by 2388 this instruction and rematerialize the EDGE_ABNORMAL 2389 flag we just cleared above. */ 2390 { 2391 e->flags |= EDGE_ABNORMAL; 2392 ei_next (&ei); 2393 continue; 2394 } 2395 2396 /* We do not need this edge. */ 2397 bb->flags |= BB_DIRTY; 2398 purged = true; 2399 remove_edge (e); 2400 } 2401 2402 if (EDGE_COUNT (bb->succs) == 0 || !purged) 2403 return purged; 2404 2405 if (dump_file) 2406 fprintf (dump_file, "Purged edges from bb %i\n", bb->index); 2407 2408 if (!optimize) 2409 return purged; 2410 2411 /* Redistribute probabilities. */ 2412 if (single_succ_p (bb)) 2413 { 2414 single_succ_edge (bb)->probability = REG_BR_PROB_BASE; 2415 single_succ_edge (bb)->count = bb->count; 2416 } 2417 else 2418 { 2419 note = find_reg_note (insn, REG_BR_PROB, NULL); 2420 if (!note) 2421 return purged; 2422 2423 b = BRANCH_EDGE (bb); 2424 f = FALLTHRU_EDGE (bb); 2425 b->probability = INTVAL (XEXP (note, 0)); 2426 f->probability = REG_BR_PROB_BASE - b->probability; 2427 b->count = bb->count * b->probability / REG_BR_PROB_BASE; 2428 f->count = bb->count * f->probability / REG_BR_PROB_BASE; 2429 } 2430 2431 return purged; 2432 } 2433 else if (CALL_P (insn) && SIBLING_CALL_P (insn)) 2434 { 2435 /* First, there should not be any EH or ABCALL edges resulting 2436 from non-local gotos and the like. If there were, we shouldn't 2437 have created the sibcall in the first place. Second, there 2438 should of course never have been a fallthru edge. */ 2439 gcc_assert (single_succ_p (bb)); 2440 gcc_assert (single_succ_edge (bb)->flags 2441 == (EDGE_SIBCALL | EDGE_ABNORMAL)); 2442 2443 return 0; 2444 } 2445 2446 /* If we don't see a jump insn, we don't know exactly why the block would 2447 have been broken at this point. Look for a simple, non-fallthru edge, 2448 as these are only created by conditional branches. If we find such an 2449 edge we know that there used to be a jump here and can then safely 2450 remove all non-fallthru edges. */ 2451 found = false; 2452 FOR_EACH_EDGE (e, ei, bb->succs) 2453 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))) 2454 { 2455 found = true; 2456 break; 2457 } 2458 2459 if (!found) 2460 return purged; 2461 2462 /* Remove all but the fake and fallthru edges. The fake edge may be 2463 the only successor for this block in the case of noreturn 2464 calls. */ 2465 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 2466 { 2467 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE))) 2468 { 2469 bb->flags |= BB_DIRTY; 2470 remove_edge (e); 2471 purged = true; 2472 } 2473 else 2474 ei_next (&ei); 2475 } 2476 2477 gcc_assert (single_succ_p (bb)); 2478 2479 single_succ_edge (bb)->probability = REG_BR_PROB_BASE; 2480 single_succ_edge (bb)->count = bb->count; 2481 2482 if (dump_file) 2483 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n", 2484 bb->index); 2485 return purged; 2486} 2487 2488/* Search all basic blocks for potentially dead edges and purge them. Return 2489 true if some edge has been eliminated. */ 2490 2491bool 2492purge_all_dead_edges (void) 2493{ 2494 int purged = false; 2495 basic_block bb; 2496 2497 FOR_EACH_BB (bb) 2498 { 2499 bool purged_here = purge_dead_edges (bb); 2500 2501 purged |= purged_here; 2502 } 2503 2504 return purged; 2505} 2506 2507/* Same as split_block but update cfg_layout structures. */ 2508 2509static basic_block 2510cfg_layout_split_block (basic_block bb, void *insnp) 2511{ 2512 rtx insn = insnp; 2513 basic_block new_bb = rtl_split_block (bb, insn); 2514 2515 new_bb->il.rtl->footer = bb->il.rtl->footer; 2516 bb->il.rtl->footer = NULL; 2517 2518 return new_bb; 2519} 2520 2521 2522/* Redirect Edge to DEST. */ 2523static edge 2524cfg_layout_redirect_edge_and_branch (edge e, basic_block dest) 2525{ 2526 basic_block src = e->src; 2527 edge ret; 2528 2529 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 2530 return NULL; 2531 2532 if (e->dest == dest) 2533 return e; 2534 2535 if (e->src != ENTRY_BLOCK_PTR 2536 && (ret = try_redirect_by_replacing_jump (e, dest, true))) 2537 { 2538 src->flags |= BB_DIRTY; 2539 return ret; 2540 } 2541 2542 if (e->src == ENTRY_BLOCK_PTR 2543 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX)) 2544 { 2545 if (dump_file) 2546 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n", 2547 e->src->index, dest->index); 2548 2549 e->src->flags |= BB_DIRTY; 2550 redirect_edge_succ (e, dest); 2551 return e; 2552 } 2553 2554 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge 2555 in the case the basic block appears to be in sequence. Avoid this 2556 transformation. */ 2557 2558 if (e->flags & EDGE_FALLTHRU) 2559 { 2560 /* Redirect any branch edges unified with the fallthru one. */ 2561 if (JUMP_P (BB_END (src)) 2562 && label_is_jump_target_p (BB_HEAD (e->dest), 2563 BB_END (src))) 2564 { 2565 edge redirected; 2566 2567 if (dump_file) 2568 fprintf (dump_file, "Fallthru edge unified with branch " 2569 "%i->%i redirected to %i\n", 2570 e->src->index, e->dest->index, dest->index); 2571 e->flags &= ~EDGE_FALLTHRU; 2572 redirected = redirect_branch_edge (e, dest); 2573 gcc_assert (redirected); 2574 e->flags |= EDGE_FALLTHRU; 2575 e->src->flags |= BB_DIRTY; 2576 return e; 2577 } 2578 /* In case we are redirecting fallthru edge to the branch edge 2579 of conditional jump, remove it. */ 2580 if (EDGE_COUNT (src->succs) == 2) 2581 { 2582 /* Find the edge that is different from E. */ 2583 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e); 2584 2585 if (s->dest == dest 2586 && any_condjump_p (BB_END (src)) 2587 && onlyjump_p (BB_END (src))) 2588 delete_insn (BB_END (src)); 2589 } 2590 ret = redirect_edge_succ_nodup (e, dest); 2591 if (dump_file) 2592 fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n", 2593 e->src->index, e->dest->index, dest->index); 2594 } 2595 else 2596 ret = redirect_branch_edge (e, dest); 2597 2598 /* We don't want simplejumps in the insn stream during cfglayout. */ 2599 gcc_assert (!simplejump_p (BB_END (src))); 2600 2601 src->flags |= BB_DIRTY; 2602 return ret; 2603} 2604 2605/* Simple wrapper as we always can redirect fallthru edges. */ 2606static basic_block 2607cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest) 2608{ 2609 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest); 2610 2611 gcc_assert (redirected); 2612 return NULL; 2613} 2614 2615/* Same as delete_basic_block but update cfg_layout structures. */ 2616 2617static void 2618cfg_layout_delete_block (basic_block bb) 2619{ 2620 rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints; 2621 2622 if (bb->il.rtl->header) 2623 { 2624 next = BB_HEAD (bb); 2625 if (prev) 2626 NEXT_INSN (prev) = bb->il.rtl->header; 2627 else 2628 set_first_insn (bb->il.rtl->header); 2629 PREV_INSN (bb->il.rtl->header) = prev; 2630 insn = bb->il.rtl->header; 2631 while (NEXT_INSN (insn)) 2632 insn = NEXT_INSN (insn); 2633 NEXT_INSN (insn) = next; 2634 PREV_INSN (next) = insn; 2635 } 2636 next = NEXT_INSN (BB_END (bb)); 2637 if (bb->il.rtl->footer) 2638 { 2639 insn = bb->il.rtl->footer; 2640 while (insn) 2641 { 2642 if (BARRIER_P (insn)) 2643 { 2644 if (PREV_INSN (insn)) 2645 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn); 2646 else 2647 bb->il.rtl->footer = NEXT_INSN (insn); 2648 if (NEXT_INSN (insn)) 2649 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn); 2650 } 2651 if (LABEL_P (insn)) 2652 break; 2653 insn = NEXT_INSN (insn); 2654 } 2655 if (bb->il.rtl->footer) 2656 { 2657 insn = BB_END (bb); 2658 NEXT_INSN (insn) = bb->il.rtl->footer; 2659 PREV_INSN (bb->il.rtl->footer) = insn; 2660 while (NEXT_INSN (insn)) 2661 insn = NEXT_INSN (insn); 2662 NEXT_INSN (insn) = next; 2663 if (next) 2664 PREV_INSN (next) = insn; 2665 else 2666 set_last_insn (insn); 2667 } 2668 } 2669 if (bb->next_bb != EXIT_BLOCK_PTR) 2670 to = &bb->next_bb->il.rtl->header; 2671 else 2672 to = &cfg_layout_function_footer; 2673 2674 rtl_delete_block (bb); 2675 2676 if (prev) 2677 prev = NEXT_INSN (prev); 2678 else 2679 prev = get_insns (); 2680 if (next) 2681 next = PREV_INSN (next); 2682 else 2683 next = get_last_insn (); 2684 2685 if (next && NEXT_INSN (next) != prev) 2686 { 2687 remaints = unlink_insn_chain (prev, next); 2688 insn = remaints; 2689 while (NEXT_INSN (insn)) 2690 insn = NEXT_INSN (insn); 2691 NEXT_INSN (insn) = *to; 2692 if (*to) 2693 PREV_INSN (*to) = insn; 2694 *to = remaints; 2695 } 2696} 2697 2698/* Return true when blocks A and B can be safely merged. */ 2699static bool 2700cfg_layout_can_merge_blocks_p (basic_block a, basic_block b) 2701{ 2702 /* If we are partitioning hot/cold basic blocks, we don't want to 2703 mess up unconditional or indirect jumps that cross between hot 2704 and cold sections. 2705 2706 Basic block partitioning may result in some jumps that appear to 2707 be optimizable (or blocks that appear to be mergeable), but which really 2708 must be left untouched (they are required to make it safely across 2709 partition boundaries). See the comments at the top of 2710 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 2711 2712 if (BB_PARTITION (a) != BB_PARTITION (b)) 2713 return false; 2714 2715 /* There must be exactly one edge in between the blocks. */ 2716 return (single_succ_p (a) 2717 && single_succ (a) == b 2718 && single_pred_p (b) == 1 2719 && a != b 2720 /* Must be simple edge. */ 2721 && !(single_succ_edge (a)->flags & EDGE_COMPLEX) 2722 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR 2723 /* If the jump insn has side effects, 2724 we can't kill the edge. */ 2725 && (!JUMP_P (BB_END (a)) 2726 || (reload_completed 2727 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a))))); 2728} 2729 2730/* Merge block A and B. The blocks must be mergeable. */ 2731 2732static void 2733cfg_layout_merge_blocks (basic_block a, basic_block b) 2734{ 2735#ifdef ENABLE_CHECKING 2736 gcc_assert (cfg_layout_can_merge_blocks_p (a, b)); 2737#endif 2738 2739 /* If there was a CODE_LABEL beginning B, delete it. */ 2740 if (LABEL_P (BB_HEAD (b))) 2741 { 2742 /* This might have been an EH label that no longer has incoming 2743 EH edges. Update data structures to match. */ 2744 maybe_remove_eh_handler (BB_HEAD (b)); 2745 2746 delete_insn (BB_HEAD (b)); 2747 } 2748 2749 /* We should have fallthru edge in a, or we can do dummy redirection to get 2750 it cleaned up. */ 2751 if (JUMP_P (BB_END (a))) 2752 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true); 2753 gcc_assert (!JUMP_P (BB_END (a))); 2754 2755 /* Possible line number notes should appear in between. */ 2756 if (b->il.rtl->header) 2757 { 2758 rtx first = BB_END (a), last; 2759 2760 last = emit_insn_after_noloc (b->il.rtl->header, BB_END (a)); 2761 delete_insn_chain (NEXT_INSN (first), last); 2762 b->il.rtl->header = NULL; 2763 } 2764 2765 /* In the case basic blocks are not adjacent, move them around. */ 2766 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b)) 2767 { 2768 rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b)); 2769 2770 emit_insn_after_noloc (first, BB_END (a)); 2771 /* Skip possible DELETED_LABEL insn. */ 2772 if (!NOTE_INSN_BASIC_BLOCK_P (first)) 2773 first = NEXT_INSN (first); 2774 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first)); 2775 BB_HEAD (b) = NULL; 2776 delete_insn (first); 2777 } 2778 /* Otherwise just re-associate the instructions. */ 2779 else 2780 { 2781 rtx insn; 2782 2783 for (insn = BB_HEAD (b); 2784 insn != NEXT_INSN (BB_END (b)); 2785 insn = NEXT_INSN (insn)) 2786 set_block_for_insn (insn, a); 2787 insn = BB_HEAD (b); 2788 /* Skip possible DELETED_LABEL insn. */ 2789 if (!NOTE_INSN_BASIC_BLOCK_P (insn)) 2790 insn = NEXT_INSN (insn); 2791 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); 2792 BB_HEAD (b) = NULL; 2793 BB_END (a) = BB_END (b); 2794 delete_insn (insn); 2795 } 2796 2797 /* Possible tablejumps and barriers should appear after the block. */ 2798 if (b->il.rtl->footer) 2799 { 2800 if (!a->il.rtl->footer) 2801 a->il.rtl->footer = b->il.rtl->footer; 2802 else 2803 { 2804 rtx last = a->il.rtl->footer; 2805 2806 while (NEXT_INSN (last)) 2807 last = NEXT_INSN (last); 2808 NEXT_INSN (last) = b->il.rtl->footer; 2809 PREV_INSN (b->il.rtl->footer) = last; 2810 } 2811 b->il.rtl->footer = NULL; 2812 } 2813 a->il.rtl->global_live_at_end = b->il.rtl->global_live_at_end; 2814 2815 if (dump_file) 2816 fprintf (dump_file, "Merged blocks %d and %d.\n", 2817 a->index, b->index); 2818} 2819 2820/* Split edge E. */ 2821 2822static basic_block 2823cfg_layout_split_edge (edge e) 2824{ 2825 basic_block new_bb = 2826 create_basic_block (e->src != ENTRY_BLOCK_PTR 2827 ? NEXT_INSN (BB_END (e->src)) : get_insns (), 2828 NULL_RTX, e->src); 2829 2830 /* ??? This info is likely going to be out of date very soon, but we must 2831 create it to avoid getting an ICE later. */ 2832 if (e->dest->il.rtl->global_live_at_start) 2833 { 2834 new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 2835 new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 2836 COPY_REG_SET (new_bb->il.rtl->global_live_at_start, 2837 e->dest->il.rtl->global_live_at_start); 2838 COPY_REG_SET (new_bb->il.rtl->global_live_at_end, 2839 e->dest->il.rtl->global_live_at_start); 2840 } 2841 2842 make_edge (new_bb, e->dest, EDGE_FALLTHRU); 2843 redirect_edge_and_branch_force (e, new_bb); 2844 2845 return new_bb; 2846} 2847 2848/* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */ 2849 2850static void 2851rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED) 2852{ 2853} 2854 2855/* Return 1 if BB ends with a call, possibly followed by some 2856 instructions that must stay with the call, 0 otherwise. */ 2857 2858static bool 2859rtl_block_ends_with_call_p (basic_block bb) 2860{ 2861 rtx insn = BB_END (bb); 2862 2863 while (!CALL_P (insn) 2864 && insn != BB_HEAD (bb) 2865 && keep_with_call_p (insn)) 2866 insn = PREV_INSN (insn); 2867 return (CALL_P (insn)); 2868} 2869 2870/* Return 1 if BB ends with a conditional branch, 0 otherwise. */ 2871 2872static bool 2873rtl_block_ends_with_condjump_p (basic_block bb) 2874{ 2875 return any_condjump_p (BB_END (bb)); 2876} 2877 2878/* Return true if we need to add fake edge to exit. 2879 Helper function for rtl_flow_call_edges_add. */ 2880 2881static bool 2882need_fake_edge_p (rtx insn) 2883{ 2884 if (!INSN_P (insn)) 2885 return false; 2886 2887 if ((CALL_P (insn) 2888 && !SIBLING_CALL_P (insn) 2889 && !find_reg_note (insn, REG_NORETURN, NULL) 2890 && !CONST_OR_PURE_CALL_P (insn))) 2891 return true; 2892 2893 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS 2894 && MEM_VOLATILE_P (PATTERN (insn))) 2895 || (GET_CODE (PATTERN (insn)) == PARALLEL 2896 && asm_noperands (insn) != -1 2897 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) 2898 || GET_CODE (PATTERN (insn)) == ASM_INPUT); 2899} 2900 2901/* Add fake edges to the function exit for any non constant and non noreturn 2902 calls, volatile inline assembly in the bitmap of blocks specified by 2903 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 2904 that were split. 2905 2906 The goal is to expose cases in which entering a basic block does not imply 2907 that all subsequent instructions must be executed. */ 2908 2909static int 2910rtl_flow_call_edges_add (sbitmap blocks) 2911{ 2912 int i; 2913 int blocks_split = 0; 2914 int last_bb = last_basic_block; 2915 bool check_last_block = false; 2916 2917 if (n_basic_blocks == 0) 2918 return 0; 2919 2920 if (! blocks) 2921 check_last_block = true; 2922 else 2923 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index); 2924 2925 /* In the last basic block, before epilogue generation, there will be 2926 a fallthru edge to EXIT. Special care is required if the last insn 2927 of the last basic block is a call because make_edge folds duplicate 2928 edges, which would result in the fallthru edge also being marked 2929 fake, which would result in the fallthru edge being removed by 2930 remove_fake_edges, which would result in an invalid CFG. 2931 2932 Moreover, we can't elide the outgoing fake edge, since the block 2933 profiler needs to take this into account in order to solve the minimal 2934 spanning tree in the case that the call doesn't return. 2935 2936 Handle this by adding a dummy instruction in a new last basic block. */ 2937 if (check_last_block) 2938 { 2939 basic_block bb = EXIT_BLOCK_PTR->prev_bb; 2940 rtx insn = BB_END (bb); 2941 2942 /* Back up past insns that must be kept in the same block as a call. */ 2943 while (insn != BB_HEAD (bb) 2944 && keep_with_call_p (insn)) 2945 insn = PREV_INSN (insn); 2946 2947 if (need_fake_edge_p (insn)) 2948 { 2949 edge e; 2950 2951 e = find_edge (bb, EXIT_BLOCK_PTR); 2952 if (e) 2953 { 2954 insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e); 2955 commit_edge_insertions (); 2956 } 2957 } 2958 } 2959 2960 /* Now add fake edges to the function exit for any non constant 2961 calls since there is no way that we can determine if they will 2962 return or not... */ 2963 2964 for (i = 0; i < last_bb; i++) 2965 { 2966 basic_block bb = BASIC_BLOCK (i); 2967 rtx insn; 2968 rtx prev_insn; 2969 2970 if (!bb) 2971 continue; 2972 2973 if (blocks && !TEST_BIT (blocks, i)) 2974 continue; 2975 2976 for (insn = BB_END (bb); ; insn = prev_insn) 2977 { 2978 prev_insn = PREV_INSN (insn); 2979 if (need_fake_edge_p (insn)) 2980 { 2981 edge e; 2982 rtx split_at_insn = insn; 2983 2984 /* Don't split the block between a call and an insn that should 2985 remain in the same block as the call. */ 2986 if (CALL_P (insn)) 2987 while (split_at_insn != BB_END (bb) 2988 && keep_with_call_p (NEXT_INSN (split_at_insn))) 2989 split_at_insn = NEXT_INSN (split_at_insn); 2990 2991 /* The handling above of the final block before the epilogue 2992 should be enough to verify that there is no edge to the exit 2993 block in CFG already. Calling make_edge in such case would 2994 cause us to mark that edge as fake and remove it later. */ 2995 2996#ifdef ENABLE_CHECKING 2997 if (split_at_insn == BB_END (bb)) 2998 { 2999 e = find_edge (bb, EXIT_BLOCK_PTR); 3000 gcc_assert (e == NULL); 3001 } 3002#endif 3003 3004 /* Note that the following may create a new basic block 3005 and renumber the existing basic blocks. */ 3006 if (split_at_insn != BB_END (bb)) 3007 { 3008 e = split_block (bb, split_at_insn); 3009 if (e) 3010 blocks_split++; 3011 } 3012 3013 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 3014 } 3015 3016 if (insn == BB_HEAD (bb)) 3017 break; 3018 } 3019 } 3020 3021 if (blocks_split) 3022 verify_flow_info (); 3023 3024 return blocks_split; 3025} 3026 3027/* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is 3028 the conditional branch target, SECOND_HEAD should be the fall-thru 3029 there is no need to handle this here the loop versioning code handles 3030 this. the reason for SECON_HEAD is that it is needed for condition 3031 in trees, and this should be of the same type since it is a hook. */ 3032static void 3033rtl_lv_add_condition_to_bb (basic_block first_head , 3034 basic_block second_head ATTRIBUTE_UNUSED, 3035 basic_block cond_bb, void *comp_rtx) 3036{ 3037 rtx label, seq, jump; 3038 rtx op0 = XEXP ((rtx)comp_rtx, 0); 3039 rtx op1 = XEXP ((rtx)comp_rtx, 1); 3040 enum rtx_code comp = GET_CODE ((rtx)comp_rtx); 3041 enum machine_mode mode; 3042 3043 3044 label = block_label (first_head); 3045 mode = GET_MODE (op0); 3046 if (mode == VOIDmode) 3047 mode = GET_MODE (op1); 3048 3049 start_sequence (); 3050 op0 = force_operand (op0, NULL_RTX); 3051 op1 = force_operand (op1, NULL_RTX); 3052 do_compare_rtx_and_jump (op0, op1, comp, 0, 3053 mode, NULL_RTX, NULL_RTX, label); 3054 jump = get_last_insn (); 3055 JUMP_LABEL (jump) = label; 3056 LABEL_NUSES (label)++; 3057 seq = get_insns (); 3058 end_sequence (); 3059 3060 /* Add the new cond , in the new head. */ 3061 emit_insn_after(seq, BB_END(cond_bb)); 3062} 3063 3064 3065/* Given a block B with unconditional branch at its end, get the 3066 store the return the branch edge and the fall-thru edge in 3067 BRANCH_EDGE and FALLTHRU_EDGE respectively. */ 3068static void 3069rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge, 3070 edge *fallthru_edge) 3071{ 3072 edge e = EDGE_SUCC (b, 0); 3073 3074 if (e->flags & EDGE_FALLTHRU) 3075 { 3076 *fallthru_edge = e; 3077 *branch_edge = EDGE_SUCC (b, 1); 3078 } 3079 else 3080 { 3081 *branch_edge = e; 3082 *fallthru_edge = EDGE_SUCC (b, 1); 3083 } 3084} 3085 3086void 3087init_rtl_bb_info (basic_block bb) 3088{ 3089 gcc_assert (!bb->il.rtl); 3090 bb->il.rtl = ggc_alloc_cleared (sizeof (struct rtl_bb_info)); 3091} 3092 3093 3094/* Implementation of CFG manipulation for linearized RTL. */ 3095struct cfg_hooks rtl_cfg_hooks = { 3096 "rtl", 3097 rtl_verify_flow_info, 3098 rtl_dump_bb, 3099 rtl_create_basic_block, 3100 rtl_redirect_edge_and_branch, 3101 rtl_redirect_edge_and_branch_force, 3102 rtl_delete_block, 3103 rtl_split_block, 3104 rtl_move_block_after, 3105 rtl_can_merge_blocks, /* can_merge_blocks_p */ 3106 rtl_merge_blocks, 3107 rtl_predict_edge, 3108 rtl_predicted_by_p, 3109 NULL, /* can_duplicate_block_p */ 3110 NULL, /* duplicate_block */ 3111 rtl_split_edge, 3112 rtl_make_forwarder_block, 3113 rtl_tidy_fallthru_edge, 3114 rtl_block_ends_with_call_p, 3115 rtl_block_ends_with_condjump_p, 3116 rtl_flow_call_edges_add, 3117 NULL, /* execute_on_growing_pred */ 3118 NULL, /* execute_on_shrinking_pred */ 3119 NULL, /* duplicate loop for trees */ 3120 NULL, /* lv_add_condition_to_bb */ 3121 NULL, /* lv_adjust_loop_header_phi*/ 3122 NULL, /* extract_cond_bb_edges */ 3123 NULL /* flush_pending_stmts */ 3124}; 3125 3126/* Implementation of CFG manipulation for cfg layout RTL, where 3127 basic block connected via fallthru edges does not have to be adjacent. 3128 This representation will hopefully become the default one in future 3129 version of the compiler. */ 3130 3131/* We do not want to declare these functions in a header file, since they 3132 should only be used through the cfghooks interface, and we do not want to 3133 move them here since it would require also moving quite a lot of related 3134 code. */ 3135extern bool cfg_layout_can_duplicate_bb_p (basic_block); 3136extern basic_block cfg_layout_duplicate_bb (basic_block); 3137 3138struct cfg_hooks cfg_layout_rtl_cfg_hooks = { 3139 "cfglayout mode", 3140 rtl_verify_flow_info_1, 3141 rtl_dump_bb, 3142 cfg_layout_create_basic_block, 3143 cfg_layout_redirect_edge_and_branch, 3144 cfg_layout_redirect_edge_and_branch_force, 3145 cfg_layout_delete_block, 3146 cfg_layout_split_block, 3147 rtl_move_block_after, 3148 cfg_layout_can_merge_blocks_p, 3149 cfg_layout_merge_blocks, 3150 rtl_predict_edge, 3151 rtl_predicted_by_p, 3152 cfg_layout_can_duplicate_bb_p, 3153 cfg_layout_duplicate_bb, 3154 cfg_layout_split_edge, 3155 rtl_make_forwarder_block, 3156 NULL, 3157 rtl_block_ends_with_call_p, 3158 rtl_block_ends_with_condjump_p, 3159 rtl_flow_call_edges_add, 3160 NULL, /* execute_on_growing_pred */ 3161 NULL, /* execute_on_shrinking_pred */ 3162 duplicate_loop_to_header_edge, /* duplicate loop for trees */ 3163 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */ 3164 NULL, /* lv_adjust_loop_header_phi*/ 3165 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */ 3166 NULL /* flush_pending_stmts */ 3167}; 3168 3169