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