1/* Basic block reordering routines for the GNU compiler. 2 Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 1902110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "tree.h" 26#include "rtl.h" 27#include "hard-reg-set.h" 28#include "obstack.h" 29#include "basic-block.h" 30#include "insn-config.h" 31#include "output.h" 32#include "function.h" 33#include "cfglayout.h" 34#include "cfgloop.h" 35#include "target.h" 36#include "ggc.h" 37#include "alloc-pool.h" 38#include "flags.h" 39#include "tree-pass.h" 40#include "vecprim.h" 41 42/* Holds the interesting trailing notes for the function. */ 43rtx cfg_layout_function_footer, cfg_layout_function_header; 44 45static rtx skip_insns_after_block (basic_block); 46static void record_effective_endpoints (void); 47static rtx label_for_bb (basic_block); 48static void fixup_reorder_chain (void); 49 50static void set_block_levels (tree, int); 51static void change_scope (rtx, tree, tree); 52 53void verify_insn_chain (void); 54static void fixup_fallthru_exit_predecessor (void); 55static tree insn_scope (rtx); 56 57rtx 58unlink_insn_chain (rtx first, rtx last) 59{ 60 rtx prevfirst = PREV_INSN (first); 61 rtx nextlast = NEXT_INSN (last); 62 63 PREV_INSN (first) = NULL; 64 NEXT_INSN (last) = NULL; 65 if (prevfirst) 66 NEXT_INSN (prevfirst) = nextlast; 67 if (nextlast) 68 PREV_INSN (nextlast) = prevfirst; 69 else 70 set_last_insn (prevfirst); 71 if (!prevfirst) 72 set_first_insn (nextlast); 73 return first; 74} 75 76/* Skip over inter-block insns occurring after BB which are typically 77 associated with BB (e.g., barriers). If there are any such insns, 78 we return the last one. Otherwise, we return the end of BB. */ 79 80static rtx 81skip_insns_after_block (basic_block bb) 82{ 83 rtx insn, last_insn, next_head, prev; 84 85 next_head = NULL_RTX; 86 if (bb->next_bb != EXIT_BLOCK_PTR) 87 next_head = BB_HEAD (bb->next_bb); 88 89 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; ) 90 { 91 if (insn == next_head) 92 break; 93 94 switch (GET_CODE (insn)) 95 { 96 case BARRIER: 97 last_insn = insn; 98 continue; 99 100 case NOTE: 101 switch (NOTE_LINE_NUMBER (insn)) 102 { 103 case NOTE_INSN_BLOCK_END: 104 last_insn = insn; 105 continue; 106 case NOTE_INSN_DELETED: 107 case NOTE_INSN_DELETED_LABEL: 108 continue; 109 110 default: 111 continue; 112 break; 113 } 114 break; 115 116 case CODE_LABEL: 117 if (NEXT_INSN (insn) 118 && JUMP_P (NEXT_INSN (insn)) 119 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC 120 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC)) 121 { 122 insn = NEXT_INSN (insn); 123 last_insn = insn; 124 continue; 125 } 126 break; 127 128 default: 129 break; 130 } 131 132 break; 133 } 134 135 /* It is possible to hit contradictory sequence. For instance: 136 137 jump_insn 138 NOTE_INSN_BLOCK_BEG 139 barrier 140 141 Where barrier belongs to jump_insn, but the note does not. This can be 142 created by removing the basic block originally following 143 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */ 144 145 for (insn = last_insn; insn != BB_END (bb); insn = prev) 146 { 147 prev = PREV_INSN (insn); 148 if (NOTE_P (insn)) 149 switch (NOTE_LINE_NUMBER (insn)) 150 { 151 case NOTE_INSN_BLOCK_END: 152 case NOTE_INSN_DELETED: 153 case NOTE_INSN_DELETED_LABEL: 154 continue; 155 default: 156 reorder_insns (insn, insn, last_insn); 157 } 158 } 159 160 return last_insn; 161} 162 163/* Locate or create a label for a given basic block. */ 164 165static rtx 166label_for_bb (basic_block bb) 167{ 168 rtx label = BB_HEAD (bb); 169 170 if (!LABEL_P (label)) 171 { 172 if (dump_file) 173 fprintf (dump_file, "Emitting label for block %d\n", bb->index); 174 175 label = block_label (bb); 176 } 177 178 return label; 179} 180 181/* Locate the effective beginning and end of the insn chain for each 182 block, as defined by skip_insns_after_block above. */ 183 184static void 185record_effective_endpoints (void) 186{ 187 rtx next_insn; 188 basic_block bb; 189 rtx insn; 190 191 for (insn = get_insns (); 192 insn 193 && NOTE_P (insn) 194 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK; 195 insn = NEXT_INSN (insn)) 196 continue; 197 /* No basic blocks at all? */ 198 gcc_assert (insn); 199 200 if (PREV_INSN (insn)) 201 cfg_layout_function_header = 202 unlink_insn_chain (get_insns (), PREV_INSN (insn)); 203 else 204 cfg_layout_function_header = NULL_RTX; 205 206 next_insn = get_insns (); 207 FOR_EACH_BB (bb) 208 { 209 rtx end; 210 211 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb)) 212 bb->il.rtl->header = unlink_insn_chain (next_insn, 213 PREV_INSN (BB_HEAD (bb))); 214 end = skip_insns_after_block (bb); 215 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end) 216 bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end); 217 next_insn = NEXT_INSN (BB_END (bb)); 218 } 219 220 cfg_layout_function_footer = next_insn; 221 if (cfg_layout_function_footer) 222 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ()); 223} 224 225/* Data structures representing mapping of INSN_LOCATOR into scope blocks, line 226 numbers and files. In order to be GGC friendly we need to use separate 227 varrays. This also slightly improve the memory locality in binary search. 228 The _locs array contains locators where the given property change. The 229 block_locators_blocks contains the scope block that is used for all insn 230 locator greater than corresponding block_locators_locs value and smaller 231 than the following one. Similarly for the other properties. */ 232static VEC(int,heap) *block_locators_locs; 233static GTY(()) VEC(tree,gc) *block_locators_blocks; 234static VEC(int,heap) *line_locators_locs; 235static VEC(int,heap) *line_locators_lines; 236static VEC(int,heap) *file_locators_locs; 237static GTY(()) varray_type file_locators_files; 238int prologue_locator; 239int epilogue_locator; 240 241/* During the RTL expansion the lexical blocks and line numbers are 242 represented via INSN_NOTEs. Replace them by representation using 243 INSN_LOCATORs. */ 244 245unsigned int 246insn_locators_initialize (void) 247{ 248 tree block = NULL; 249 tree last_block = NULL; 250 rtx insn, next; 251 int loc = 0; 252 int line_number = 0, last_line_number = 0; 253 const char *file_name = NULL, *last_file_name = NULL; 254 255 prologue_locator = epilogue_locator = 0; 256 257 block_locators_locs = VEC_alloc (int, heap, 32); 258 block_locators_blocks = VEC_alloc (tree, gc, 32); 259 line_locators_locs = VEC_alloc (int, heap, 32); 260 line_locators_lines = VEC_alloc (int, heap, 32); 261 file_locators_locs = VEC_alloc (int, heap, 32); 262 VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files"); 263 264 for (insn = get_insns (); insn; insn = next) 265 { 266 int active = 0; 267 268 next = NEXT_INSN (insn); 269 270 if (NOTE_P (insn)) 271 { 272 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_BEG 273 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END); 274 if (NOTE_LINE_NUMBER (insn) > 0) 275 { 276 expanded_location xloc; 277 NOTE_EXPANDED_LOCATION (xloc, insn); 278 line_number = xloc.line; 279 file_name = xloc.file; 280 } 281 } 282 else 283 active = (active_insn_p (insn) 284 && GET_CODE (PATTERN (insn)) != ADDR_VEC 285 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); 286 287 check_block_change (insn, &block); 288 289 if (active 290 || !next 291 || (!prologue_locator && file_name)) 292 { 293 if (last_block != block) 294 { 295 loc++; 296 VEC_safe_push (int, heap, block_locators_locs, loc); 297 VEC_safe_push (tree, gc, block_locators_blocks, block); 298 last_block = block; 299 } 300 if (last_line_number != line_number) 301 { 302 loc++; 303 VEC_safe_push (int, heap, line_locators_locs, loc); 304 VEC_safe_push (int, heap, line_locators_lines, line_number); 305 last_line_number = line_number; 306 } 307 if (last_file_name != file_name) 308 { 309 loc++; 310 VEC_safe_push (int, heap, file_locators_locs, loc); 311 VARRAY_PUSH_CHAR_PTR (file_locators_files, (char *) file_name); 312 last_file_name = file_name; 313 } 314 if (!prologue_locator && file_name) 315 prologue_locator = loc; 316 if (!next) 317 epilogue_locator = loc; 318 if (active) 319 INSN_LOCATOR (insn) = loc; 320 } 321 } 322 323 /* Tag the blocks with a depth number so that change_scope can find 324 the common parent easily. */ 325 set_block_levels (DECL_INITIAL (cfun->decl), 0); 326 327 free_block_changes (); 328 return 0; 329} 330 331struct tree_opt_pass pass_insn_locators_initialize = 332{ 333 "locators", /* name */ 334 NULL, /* gate */ 335 insn_locators_initialize, /* execute */ 336 NULL, /* sub */ 337 NULL, /* next */ 338 0, /* static_pass_number */ 339 0, /* tv_id */ 340 0, /* properties_required */ 341 0, /* properties_provided */ 342 0, /* properties_destroyed */ 343 0, /* todo_flags_start */ 344 TODO_dump_func, /* todo_flags_finish */ 345 0 /* letter */ 346}; 347 348 349/* For each lexical block, set BLOCK_NUMBER to the depth at which it is 350 found in the block tree. */ 351 352static void 353set_block_levels (tree block, int level) 354{ 355 while (block) 356 { 357 BLOCK_NUMBER (block) = level; 358 set_block_levels (BLOCK_SUBBLOCKS (block), level + 1); 359 block = BLOCK_CHAIN (block); 360 } 361} 362 363/* Return sope resulting from combination of S1 and S2. */ 364static tree 365choose_inner_scope (tree s1, tree s2) 366{ 367 if (!s1) 368 return s2; 369 if (!s2) 370 return s1; 371 if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2)) 372 return s1; 373 return s2; 374} 375 376/* Emit lexical block notes needed to change scope from S1 to S2. */ 377 378static void 379change_scope (rtx orig_insn, tree s1, tree s2) 380{ 381 rtx insn = orig_insn; 382 tree com = NULL_TREE; 383 tree ts1 = s1, ts2 = s2; 384 tree s; 385 386 while (ts1 != ts2) 387 { 388 gcc_assert (ts1 && ts2); 389 if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2)) 390 ts1 = BLOCK_SUPERCONTEXT (ts1); 391 else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2)) 392 ts2 = BLOCK_SUPERCONTEXT (ts2); 393 else 394 { 395 ts1 = BLOCK_SUPERCONTEXT (ts1); 396 ts2 = BLOCK_SUPERCONTEXT (ts2); 397 } 398 } 399 com = ts1; 400 401 /* Close scopes. */ 402 s = s1; 403 while (s != com) 404 { 405 rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn); 406 NOTE_BLOCK (note) = s; 407 s = BLOCK_SUPERCONTEXT (s); 408 } 409 410 /* Open scopes. */ 411 s = s2; 412 while (s != com) 413 { 414 insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn); 415 NOTE_BLOCK (insn) = s; 416 s = BLOCK_SUPERCONTEXT (s); 417 } 418} 419 420/* Return lexical scope block insn belong to. */ 421static tree 422insn_scope (rtx insn) 423{ 424 int max = VEC_length (int, block_locators_locs); 425 int min = 0; 426 int loc = INSN_LOCATOR (insn); 427 428 /* When block_locators_locs was initialized, the pro- and epilogue 429 insns didn't exist yet and can therefore not be found this way. 430 But we know that they belong to the outer most block of the 431 current function. 432 Without this test, the prologue would be put inside the block of 433 the first valid instruction in the function and when that first 434 insn is part of an inlined function then the low_pc of that 435 inlined function is messed up. Likewise for the epilogue and 436 the last valid instruction. */ 437 if (loc == prologue_locator || loc == epilogue_locator) 438 return DECL_INITIAL (cfun->decl); 439 440 if (!max || !loc) 441 return NULL; 442 while (1) 443 { 444 int pos = (min + max) / 2; 445 int tmp = VEC_index (int, block_locators_locs, pos); 446 447 if (tmp <= loc && min != pos) 448 min = pos; 449 else if (tmp > loc && max != pos) 450 max = pos; 451 else 452 { 453 min = pos; 454 break; 455 } 456 } 457 return VEC_index (tree, block_locators_blocks, min); 458} 459 460/* Return line number of the statement specified by the locator. */ 461int 462locator_line (int loc) 463{ 464 int max = VEC_length (int, line_locators_locs); 465 int min = 0; 466 467 if (!max || !loc) 468 return 0; 469 while (1) 470 { 471 int pos = (min + max) / 2; 472 int tmp = VEC_index (int, line_locators_locs, pos); 473 474 if (tmp <= loc && min != pos) 475 min = pos; 476 else if (tmp > loc && max != pos) 477 max = pos; 478 else 479 { 480 min = pos; 481 break; 482 } 483 } 484 return VEC_index (int, line_locators_lines, min); 485} 486 487/* Return line number of the statement that produced this insn. */ 488int 489insn_line (rtx insn) 490{ 491 return locator_line (INSN_LOCATOR (insn)); 492} 493 494/* Return source file of the statement specified by LOC. */ 495const char * 496locator_file (int loc) 497{ 498 int max = VEC_length (int, file_locators_locs); 499 int min = 0; 500 501 if (!max || !loc) 502 return NULL; 503 while (1) 504 { 505 int pos = (min + max) / 2; 506 int tmp = VEC_index (int, file_locators_locs, pos); 507 508 if (tmp <= loc && min != pos) 509 min = pos; 510 else if (tmp > loc && max != pos) 511 max = pos; 512 else 513 { 514 min = pos; 515 break; 516 } 517 } 518 return VARRAY_CHAR_PTR (file_locators_files, min); 519} 520 521/* Return source file of the statement that produced this insn. */ 522const char * 523insn_file (rtx insn) 524{ 525 return locator_file (INSN_LOCATOR (insn)); 526} 527 528/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based 529 on the scope tree and the newly reordered instructions. */ 530 531void 532reemit_insn_block_notes (void) 533{ 534 tree cur_block = DECL_INITIAL (cfun->decl); 535 rtx insn, note; 536 537 insn = get_insns (); 538 if (!active_insn_p (insn)) 539 insn = next_active_insn (insn); 540 for (; insn; insn = next_active_insn (insn)) 541 { 542 tree this_block; 543 544 /* Avoid putting scope notes between jump table and its label. */ 545 if (JUMP_P (insn) 546 && (GET_CODE (PATTERN (insn)) == ADDR_VEC 547 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)) 548 continue; 549 550 this_block = insn_scope (insn); 551 /* For sequences compute scope resulting from merging all scopes 552 of instructions nested inside. */ 553 if (GET_CODE (PATTERN (insn)) == SEQUENCE) 554 { 555 int i; 556 rtx body = PATTERN (insn); 557 558 this_block = NULL; 559 for (i = 0; i < XVECLEN (body, 0); i++) 560 this_block = choose_inner_scope (this_block, 561 insn_scope (XVECEXP (body, 0, i))); 562 } 563 if (! this_block) 564 continue; 565 566 if (this_block != cur_block) 567 { 568 change_scope (insn, cur_block, this_block); 569 cur_block = this_block; 570 } 571 } 572 573 /* change_scope emits before the insn, not after. */ 574 note = emit_note (NOTE_INSN_DELETED); 575 change_scope (note, cur_block, DECL_INITIAL (cfun->decl)); 576 delete_insn (note); 577 578 reorder_blocks (); 579} 580 581/* Given a reorder chain, rearrange the code to match. */ 582 583static void 584fixup_reorder_chain (void) 585{ 586 basic_block bb, prev_bb; 587 int index; 588 rtx insn = NULL; 589 590 if (cfg_layout_function_header) 591 { 592 set_first_insn (cfg_layout_function_header); 593 insn = cfg_layout_function_header; 594 while (NEXT_INSN (insn)) 595 insn = NEXT_INSN (insn); 596 } 597 598 /* First do the bulk reordering -- rechain the blocks without regard to 599 the needed changes to jumps and labels. */ 600 601 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS; 602 bb != 0; 603 bb = bb->aux, index++) 604 { 605 if (bb->il.rtl->header) 606 { 607 if (insn) 608 NEXT_INSN (insn) = bb->il.rtl->header; 609 else 610 set_first_insn (bb->il.rtl->header); 611 PREV_INSN (bb->il.rtl->header) = insn; 612 insn = bb->il.rtl->header; 613 while (NEXT_INSN (insn)) 614 insn = NEXT_INSN (insn); 615 } 616 if (insn) 617 NEXT_INSN (insn) = BB_HEAD (bb); 618 else 619 set_first_insn (BB_HEAD (bb)); 620 PREV_INSN (BB_HEAD (bb)) = insn; 621 insn = BB_END (bb); 622 if (bb->il.rtl->footer) 623 { 624 NEXT_INSN (insn) = bb->il.rtl->footer; 625 PREV_INSN (bb->il.rtl->footer) = insn; 626 while (NEXT_INSN (insn)) 627 insn = NEXT_INSN (insn); 628 } 629 } 630 631 gcc_assert (index == n_basic_blocks); 632 633 NEXT_INSN (insn) = cfg_layout_function_footer; 634 if (cfg_layout_function_footer) 635 PREV_INSN (cfg_layout_function_footer) = insn; 636 637 while (NEXT_INSN (insn)) 638 insn = NEXT_INSN (insn); 639 640 set_last_insn (insn); 641#ifdef ENABLE_CHECKING 642 verify_insn_chain (); 643#endif 644 delete_dead_jumptables (); 645 646 /* Now add jumps and labels as needed to match the blocks new 647 outgoing edges. */ 648 649 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux) 650 { 651 edge e_fall, e_taken, e; 652 rtx bb_end_insn; 653 basic_block nb; 654 edge_iterator ei; 655 656 if (EDGE_COUNT (bb->succs) == 0) 657 continue; 658 659 /* Find the old fallthru edge, and another non-EH edge for 660 a taken jump. */ 661 e_taken = e_fall = NULL; 662 663 FOR_EACH_EDGE (e, ei, bb->succs) 664 if (e->flags & EDGE_FALLTHRU) 665 e_fall = e; 666 else if (! (e->flags & EDGE_EH)) 667 e_taken = e; 668 669 bb_end_insn = BB_END (bb); 670 if (JUMP_P (bb_end_insn)) 671 { 672 if (any_condjump_p (bb_end_insn)) 673 { 674 /* If the old fallthru is still next, nothing to do. */ 675 if (bb->aux == e_fall->dest 676 || e_fall->dest == EXIT_BLOCK_PTR) 677 continue; 678 679 /* The degenerated case of conditional jump jumping to the next 680 instruction can happen for jumps with side effects. We need 681 to construct a forwarder block and this will be done just 682 fine by force_nonfallthru below. */ 683 if (!e_taken) 684 ; 685 686 /* There is another special case: if *neither* block is next, 687 such as happens at the very end of a function, then we'll 688 need to add a new unconditional jump. Choose the taken 689 edge based on known or assumed probability. */ 690 else if (bb->aux != e_taken->dest) 691 { 692 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0); 693 694 if (note 695 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2 696 && invert_jump (bb_end_insn, 697 (e_fall->dest == EXIT_BLOCK_PTR 698 ? NULL_RTX 699 : label_for_bb (e_fall->dest)), 0)) 700 { 701 e_fall->flags &= ~EDGE_FALLTHRU; 702#ifdef ENABLE_CHECKING 703 gcc_assert (could_fall_through 704 (e_taken->src, e_taken->dest)); 705#endif 706 e_taken->flags |= EDGE_FALLTHRU; 707 update_br_prob_note (bb); 708 e = e_fall, e_fall = e_taken, e_taken = e; 709 } 710 } 711 712 /* If the "jumping" edge is a crossing edge, and the fall 713 through edge is non-crossing, leave things as they are. */ 714 else if ((e_taken->flags & EDGE_CROSSING) 715 && !(e_fall->flags & EDGE_CROSSING)) 716 continue; 717 718 /* Otherwise we can try to invert the jump. This will 719 basically never fail, however, keep up the pretense. */ 720 else if (invert_jump (bb_end_insn, 721 (e_fall->dest == EXIT_BLOCK_PTR 722 ? NULL_RTX 723 : label_for_bb (e_fall->dest)), 0)) 724 { 725 e_fall->flags &= ~EDGE_FALLTHRU; 726#ifdef ENABLE_CHECKING 727 gcc_assert (could_fall_through 728 (e_taken->src, e_taken->dest)); 729#endif 730 e_taken->flags |= EDGE_FALLTHRU; 731 update_br_prob_note (bb); 732 continue; 733 } 734 } 735 else 736 { 737 /* Otherwise we have some return, switch or computed 738 jump. In the 99% case, there should not have been a 739 fallthru edge. */ 740 gcc_assert (returnjump_p (bb_end_insn) || !e_fall); 741 continue; 742 } 743 } 744 else 745 { 746 /* No fallthru implies a noreturn function with EH edges, or 747 something similarly bizarre. In any case, we don't need to 748 do anything. */ 749 if (! e_fall) 750 continue; 751 752 /* If the fallthru block is still next, nothing to do. */ 753 if (bb->aux == e_fall->dest) 754 continue; 755 756 /* A fallthru to exit block. */ 757 if (e_fall->dest == EXIT_BLOCK_PTR) 758 continue; 759 } 760 761 /* We got here if we need to add a new jump insn. */ 762 nb = force_nonfallthru (e_fall); 763 if (nb) 764 { 765 nb->il.rtl->visited = 1; 766 nb->aux = bb->aux; 767 bb->aux = nb; 768 /* Don't process this new block. */ 769 bb = nb; 770 771 /* Make sure new bb is tagged for correct section (same as 772 fall-thru source, since you cannot fall-throu across 773 section boundaries). */ 774 BB_COPY_PARTITION (e_fall->src, single_pred (bb)); 775 if (flag_reorder_blocks_and_partition 776 && targetm.have_named_sections 777 && JUMP_P (BB_END (bb)) 778 && !any_condjump_p (BB_END (bb)) 779 && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING)) 780 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST 781 (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb))); 782 } 783 } 784 785 /* Put basic_block_info in the new order. */ 786 787 if (dump_file) 788 { 789 fprintf (dump_file, "Reordered sequence:\n"); 790 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS; 791 bb; 792 bb = bb->aux, index++) 793 { 794 fprintf (dump_file, " %i ", index); 795 if (get_bb_original (bb)) 796 fprintf (dump_file, "duplicate of %i ", 797 get_bb_original (bb)->index); 798 else if (forwarder_block_p (bb) 799 && !LABEL_P (BB_HEAD (bb))) 800 fprintf (dump_file, "compensation "); 801 else 802 fprintf (dump_file, "bb %i ", bb->index); 803 fprintf (dump_file, " [%i]\n", bb->frequency); 804 } 805 } 806 807 prev_bb = ENTRY_BLOCK_PTR; 808 bb = ENTRY_BLOCK_PTR->next_bb; 809 index = NUM_FIXED_BLOCKS; 810 811 for (; bb; prev_bb = bb, bb = bb->aux, index ++) 812 { 813 bb->index = index; 814 SET_BASIC_BLOCK (index, bb); 815 816 bb->prev_bb = prev_bb; 817 prev_bb->next_bb = bb; 818 } 819 prev_bb->next_bb = EXIT_BLOCK_PTR; 820 EXIT_BLOCK_PTR->prev_bb = prev_bb; 821 822 /* Annoying special case - jump around dead jumptables left in the code. */ 823 FOR_EACH_BB (bb) 824 { 825 edge e; 826 edge_iterator ei; 827 828 FOR_EACH_EDGE (e, ei, bb->succs) 829 if (e->flags & EDGE_FALLTHRU) 830 break; 831 832 if (e && !can_fallthru (e->src, e->dest)) 833 force_nonfallthru (e); 834 } 835} 836 837/* Perform sanity checks on the insn chain. 838 1. Check that next/prev pointers are consistent in both the forward and 839 reverse direction. 840 2. Count insns in chain, going both directions, and check if equal. 841 3. Check that get_last_insn () returns the actual end of chain. */ 842 843void 844verify_insn_chain (void) 845{ 846 rtx x, prevx, nextx; 847 int insn_cnt1, insn_cnt2; 848 849 for (prevx = NULL, insn_cnt1 = 1, x = get_insns (); 850 x != 0; 851 prevx = x, insn_cnt1++, x = NEXT_INSN (x)) 852 gcc_assert (PREV_INSN (x) == prevx); 853 854 gcc_assert (prevx == get_last_insn ()); 855 856 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn (); 857 x != 0; 858 nextx = x, insn_cnt2++, x = PREV_INSN (x)) 859 gcc_assert (NEXT_INSN (x) == nextx); 860 861 gcc_assert (insn_cnt1 == insn_cnt2); 862} 863 864/* If we have assembler epilogues, the block falling through to exit must 865 be the last one in the reordered chain when we reach final. Ensure 866 that this condition is met. */ 867static void 868fixup_fallthru_exit_predecessor (void) 869{ 870 edge e; 871 edge_iterator ei; 872 basic_block bb = NULL; 873 874 /* This transformation is not valid before reload, because we might 875 separate a call from the instruction that copies the return 876 value. */ 877 gcc_assert (reload_completed); 878 879 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 880 if (e->flags & EDGE_FALLTHRU) 881 bb = e->src; 882 883 if (bb && bb->aux) 884 { 885 basic_block c = ENTRY_BLOCK_PTR->next_bb; 886 887 /* If the very first block is the one with the fall-through exit 888 edge, we have to split that block. */ 889 if (c == bb) 890 { 891 bb = split_block (bb, NULL)->dest; 892 bb->aux = c->aux; 893 c->aux = bb; 894 bb->il.rtl->footer = c->il.rtl->footer; 895 c->il.rtl->footer = NULL; 896 } 897 898 while (c->aux != bb) 899 c = c->aux; 900 901 c->aux = bb->aux; 902 while (c->aux) 903 c = c->aux; 904 905 c->aux = bb; 906 bb->aux = NULL; 907 } 908} 909 910/* Return true in case it is possible to duplicate the basic block BB. */ 911 912/* We do not want to declare the function in a header file, since it should 913 only be used through the cfghooks interface, and we do not want to move 914 it to cfgrtl.c since it would require also moving quite a lot of related 915 code. */ 916extern bool cfg_layout_can_duplicate_bb_p (basic_block); 917 918bool 919cfg_layout_can_duplicate_bb_p (basic_block bb) 920{ 921 /* Do not attempt to duplicate tablejumps, as we need to unshare 922 the dispatch table. This is difficult to do, as the instructions 923 computing jump destination may be hoisted outside the basic block. */ 924 if (tablejump_p (BB_END (bb), NULL, NULL)) 925 return false; 926 927 /* Do not duplicate blocks containing insns that can't be copied. */ 928 if (targetm.cannot_copy_insn_p) 929 { 930 rtx insn = BB_HEAD (bb); 931 while (1) 932 { 933 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn)) 934 return false; 935 if (insn == BB_END (bb)) 936 break; 937 insn = NEXT_INSN (insn); 938 } 939 } 940 941 return true; 942} 943 944rtx 945duplicate_insn_chain (rtx from, rtx to) 946{ 947 rtx insn, last; 948 949 /* Avoid updating of boundaries of previous basic block. The 950 note will get removed from insn stream in fixup. */ 951 last = emit_note (NOTE_INSN_DELETED); 952 953 /* Create copy at the end of INSN chain. The chain will 954 be reordered later. */ 955 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn)) 956 { 957 switch (GET_CODE (insn)) 958 { 959 case INSN: 960 case CALL_INSN: 961 case JUMP_INSN: 962 /* Avoid copying of dispatch tables. We never duplicate 963 tablejumps, so this can hit only in case the table got 964 moved far from original jump. */ 965 if (GET_CODE (PATTERN (insn)) == ADDR_VEC 966 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC) 967 break; 968 emit_copy_of_insn_after (insn, get_last_insn ()); 969 break; 970 971 case CODE_LABEL: 972 break; 973 974 case BARRIER: 975 emit_barrier (); 976 break; 977 978 case NOTE: 979 switch (NOTE_LINE_NUMBER (insn)) 980 { 981 /* In case prologue is empty and function contain label 982 in first BB, we may want to copy the block. */ 983 case NOTE_INSN_PROLOGUE_END: 984 985 case NOTE_INSN_DELETED: 986 case NOTE_INSN_DELETED_LABEL: 987 /* No problem to strip these. */ 988 case NOTE_INSN_EPILOGUE_BEG: 989 case NOTE_INSN_FUNCTION_END: 990 /* Debug code expect these notes to exist just once. 991 Keep them in the master copy. 992 ??? It probably makes more sense to duplicate them for each 993 epilogue copy. */ 994 case NOTE_INSN_FUNCTION_BEG: 995 /* There is always just single entry to function. */ 996 case NOTE_INSN_BASIC_BLOCK: 997 break; 998 999 case NOTE_INSN_REPEATED_LINE_NUMBER: 1000 case NOTE_INSN_SWITCH_TEXT_SECTIONS: 1001 emit_note_copy (insn); 1002 break; 1003 1004 default: 1005 /* All other notes should have already been eliminated. 1006 */ 1007 gcc_assert (NOTE_LINE_NUMBER (insn) >= 0); 1008 1009 /* It is possible that no_line_number is set and the note 1010 won't be emitted. */ 1011 emit_note_copy (insn); 1012 } 1013 break; 1014 default: 1015 gcc_unreachable (); 1016 } 1017 } 1018 insn = NEXT_INSN (last); 1019 delete_insn (last); 1020 return insn; 1021} 1022/* Create a duplicate of the basic block BB. */ 1023 1024/* We do not want to declare the function in a header file, since it should 1025 only be used through the cfghooks interface, and we do not want to move 1026 it to cfgrtl.c since it would require also moving quite a lot of related 1027 code. */ 1028extern basic_block cfg_layout_duplicate_bb (basic_block); 1029 1030basic_block 1031cfg_layout_duplicate_bb (basic_block bb) 1032{ 1033 rtx insn; 1034 basic_block new_bb; 1035 1036 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb)); 1037 new_bb = create_basic_block (insn, 1038 insn ? get_last_insn () : NULL, 1039 EXIT_BLOCK_PTR->prev_bb); 1040 1041 BB_COPY_PARTITION (new_bb, bb); 1042 if (bb->il.rtl->header) 1043 { 1044 insn = bb->il.rtl->header; 1045 while (NEXT_INSN (insn)) 1046 insn = NEXT_INSN (insn); 1047 insn = duplicate_insn_chain (bb->il.rtl->header, insn); 1048 if (insn) 1049 new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ()); 1050 } 1051 1052 if (bb->il.rtl->footer) 1053 { 1054 insn = bb->il.rtl->footer; 1055 while (NEXT_INSN (insn)) 1056 insn = NEXT_INSN (insn); 1057 insn = duplicate_insn_chain (bb->il.rtl->footer, insn); 1058 if (insn) 1059 new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ()); 1060 } 1061 1062 if (bb->il.rtl->global_live_at_start) 1063 { 1064 new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1065 new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1066 COPY_REG_SET (new_bb->il.rtl->global_live_at_start, 1067 bb->il.rtl->global_live_at_start); 1068 COPY_REG_SET (new_bb->il.rtl->global_live_at_end, 1069 bb->il.rtl->global_live_at_end); 1070 } 1071 1072 return new_bb; 1073} 1074 1075/* Main entry point to this module - initialize the datastructures for 1076 CFG layout changes. It keeps LOOPS up-to-date if not null. 1077 1078 FLAGS is a set of additional flags to pass to cleanup_cfg(). It should 1079 include CLEANUP_UPDATE_LIFE if liveness information must be kept up 1080 to date. */ 1081 1082void 1083cfg_layout_initialize (unsigned int flags) 1084{ 1085 initialize_original_copy_tables (); 1086 1087 cfg_layout_rtl_register_cfg_hooks (); 1088 1089 record_effective_endpoints (); 1090 1091 cleanup_cfg (CLEANUP_CFGLAYOUT | flags); 1092} 1093 1094/* Splits superblocks. */ 1095void 1096break_superblocks (void) 1097{ 1098 sbitmap superblocks; 1099 bool need = false; 1100 basic_block bb; 1101 1102 superblocks = sbitmap_alloc (last_basic_block); 1103 sbitmap_zero (superblocks); 1104 1105 FOR_EACH_BB (bb) 1106 if (bb->flags & BB_SUPERBLOCK) 1107 { 1108 bb->flags &= ~BB_SUPERBLOCK; 1109 SET_BIT (superblocks, bb->index); 1110 need = true; 1111 } 1112 1113 if (need) 1114 { 1115 rebuild_jump_labels (get_insns ()); 1116 find_many_sub_basic_blocks (superblocks); 1117 } 1118 1119 free (superblocks); 1120} 1121 1122/* Finalize the changes: reorder insn list according to the sequence specified 1123 by aux pointers, enter compensation code, rebuild scope forest. */ 1124 1125void 1126cfg_layout_finalize (void) 1127{ 1128 basic_block bb; 1129 1130#ifdef ENABLE_CHECKING 1131 verify_flow_info (); 1132#endif 1133 rtl_register_cfg_hooks (); 1134 if (reload_completed 1135#ifdef HAVE_epilogue 1136 && !HAVE_epilogue 1137#endif 1138 ) 1139 fixup_fallthru_exit_predecessor (); 1140 fixup_reorder_chain (); 1141 1142#ifdef ENABLE_CHECKING 1143 verify_insn_chain (); 1144#endif 1145 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 1146 { 1147 bb->il.rtl->header = bb->il.rtl->footer = NULL; 1148 bb->aux = NULL; 1149 bb->il.rtl->visited = 0; 1150 } 1151 1152 break_superblocks (); 1153 1154#ifdef ENABLE_CHECKING 1155 verify_flow_info (); 1156#endif 1157 1158 free_original_copy_tables (); 1159} 1160 1161/* Checks whether all N blocks in BBS array can be copied. */ 1162bool 1163can_copy_bbs_p (basic_block *bbs, unsigned n) 1164{ 1165 unsigned i; 1166 edge e; 1167 int ret = true; 1168 1169 for (i = 0; i < n; i++) 1170 bbs[i]->flags |= BB_DUPLICATED; 1171 1172 for (i = 0; i < n; i++) 1173 { 1174 /* In case we should redirect abnormal edge during duplication, fail. */ 1175 edge_iterator ei; 1176 FOR_EACH_EDGE (e, ei, bbs[i]->succs) 1177 if ((e->flags & EDGE_ABNORMAL) 1178 && (e->dest->flags & BB_DUPLICATED)) 1179 { 1180 ret = false; 1181 goto end; 1182 } 1183 1184 if (!can_duplicate_block_p (bbs[i])) 1185 { 1186 ret = false; 1187 break; 1188 } 1189 } 1190 1191end: 1192 for (i = 0; i < n; i++) 1193 bbs[i]->flags &= ~BB_DUPLICATED; 1194 1195 return ret; 1196} 1197 1198/* Duplicates N basic blocks stored in array BBS. Newly created basic blocks 1199 are placed into array NEW_BBS in the same order. Edges from basic blocks 1200 in BBS are also duplicated and copies of those of them 1201 that lead into BBS are redirected to appropriate newly created block. The 1202 function assigns bbs into loops (copy of basic block bb is assigned to 1203 bb->loop_father->copy loop, so this must be set up correctly in advance) 1204 and updates dominators locally (LOOPS structure that contains the information 1205 about dominators is passed to enable this). 1206 1207 BASE is the superloop to that basic block belongs; if its header or latch 1208 is copied, we do not set the new blocks as header or latch. 1209 1210 Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES, 1211 also in the same order. 1212 1213 Newly created basic blocks are put after the basic block AFTER in the 1214 instruction stream, and the order of the blocks in BBS array is preserved. */ 1215 1216void 1217copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs, 1218 edge *edges, unsigned num_edges, edge *new_edges, 1219 struct loop *base, basic_block after) 1220{ 1221 unsigned i, j; 1222 basic_block bb, new_bb, dom_bb; 1223 edge e; 1224 1225 /* Duplicate bbs, update dominators, assign bbs to loops. */ 1226 for (i = 0; i < n; i++) 1227 { 1228 /* Duplicate. */ 1229 bb = bbs[i]; 1230 new_bb = new_bbs[i] = duplicate_block (bb, NULL, after); 1231 after = new_bb; 1232 bb->flags |= BB_DUPLICATED; 1233 /* Add to loop. */ 1234 add_bb_to_loop (new_bb, bb->loop_father->copy); 1235 /* Possibly set header. */ 1236 if (bb->loop_father->header == bb && bb->loop_father != base) 1237 new_bb->loop_father->header = new_bb; 1238 /* Or latch. */ 1239 if (bb->loop_father->latch == bb && bb->loop_father != base) 1240 new_bb->loop_father->latch = new_bb; 1241 } 1242 1243 /* Set dominators. */ 1244 for (i = 0; i < n; i++) 1245 { 1246 bb = bbs[i]; 1247 new_bb = new_bbs[i]; 1248 1249 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb); 1250 if (dom_bb->flags & BB_DUPLICATED) 1251 { 1252 dom_bb = get_bb_copy (dom_bb); 1253 set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb); 1254 } 1255 } 1256 1257 /* Redirect edges. */ 1258 for (j = 0; j < num_edges; j++) 1259 new_edges[j] = NULL; 1260 for (i = 0; i < n; i++) 1261 { 1262 edge_iterator ei; 1263 new_bb = new_bbs[i]; 1264 bb = bbs[i]; 1265 1266 FOR_EACH_EDGE (e, ei, new_bb->succs) 1267 { 1268 for (j = 0; j < num_edges; j++) 1269 if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest) 1270 new_edges[j] = e; 1271 1272 if (!(e->dest->flags & BB_DUPLICATED)) 1273 continue; 1274 redirect_edge_and_branch_force (e, get_bb_copy (e->dest)); 1275 } 1276 } 1277 1278 /* Clear information about duplicates. */ 1279 for (i = 0; i < n; i++) 1280 bbs[i]->flags &= ~BB_DUPLICATED; 1281} 1282 1283#include "gt-cfglayout.h" 1284