cfgbuild.c revision 110611
1/* Control flow graph building code for GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2003 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22/* find_basic_blocks divides the current function's rtl into basic 23 blocks and constructs the CFG. The blocks are recorded in the 24 basic_block_info array; the CFG exists in the edge structures 25 referenced by the blocks. 26 27 find_basic_blocks also finds any unreachable loops and deletes them. 28 29 Available functionality: 30 - CFG construction 31 find_basic_blocks 32 - Local CFG construction 33 find_sub_basic_blocks */ 34 35#include "config.h" 36#include "system.h" 37#include "tree.h" 38#include "rtl.h" 39#include "hard-reg-set.h" 40#include "basic-block.h" 41#include "regs.h" 42#include "flags.h" 43#include "output.h" 44#include "function.h" 45#include "except.h" 46#include "toplev.h" 47#include "timevar.h" 48#include "obstack.h" 49 50static int count_basic_blocks PARAMS ((rtx)); 51static void find_basic_blocks_1 PARAMS ((rtx)); 52static rtx find_label_refs PARAMS ((rtx, rtx)); 53static void make_edges PARAMS ((rtx, int, int, int)); 54static void make_label_edge PARAMS ((sbitmap *, basic_block, 55 rtx, int)); 56static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx)); 57static void find_bb_boundaries PARAMS ((basic_block)); 58static void compute_outgoing_frequencies PARAMS ((basic_block)); 59static bool inside_basic_block_p PARAMS ((rtx)); 60 61/* Return true if insn is something that should be contained inside basic 62 block. */ 63 64static bool 65inside_basic_block_p (insn) 66 rtx insn; 67{ 68 switch (GET_CODE (insn)) 69 { 70 case CODE_LABEL: 71 /* Avoid creating of basic block for jumptables. */ 72 return (NEXT_INSN (insn) == 0 73 || GET_CODE (NEXT_INSN (insn)) != JUMP_INSN 74 || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC 75 && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC)); 76 77 case JUMP_INSN: 78 return (GET_CODE (PATTERN (insn)) != ADDR_VEC 79 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); 80 81 case CALL_INSN: 82 case INSN: 83 return true; 84 85 case BARRIER: 86 case NOTE: 87 return false; 88 89 default: 90 abort (); 91 } 92} 93 94/* Return true if INSN may cause control flow transfer, so it should be last in 95 the basic block. */ 96 97bool 98control_flow_insn_p (insn) 99 rtx insn; 100{ 101 rtx note; 102 103 switch (GET_CODE (insn)) 104 { 105 case NOTE: 106 case CODE_LABEL: 107 return false; 108 109 case JUMP_INSN: 110 /* Jump insn always causes control transfer except for tablejumps. */ 111 return (GET_CODE (PATTERN (insn)) != ADDR_VEC 112 && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC); 113 114 case CALL_INSN: 115 /* Call insn may return to the nonlocal goto handler. */ 116 return ((nonlocal_goto_handler_labels 117 && (0 == (note = find_reg_note (insn, REG_EH_REGION, 118 NULL_RTX)) 119 || INTVAL (XEXP (note, 0)) >= 0)) 120 /* Or may trap. */ 121 || can_throw_internal (insn)); 122 123 case INSN: 124 return (flag_non_call_exceptions && can_throw_internal (insn)); 125 126 case BARRIER: 127 /* It is nonsence to reach barrier when looking for the 128 end of basic block, but before dead code is eliminated 129 this may happen. */ 130 return false; 131 132 default: 133 abort (); 134 } 135} 136 137/* Count the basic blocks of the function. */ 138 139static int 140count_basic_blocks (f) 141 rtx f; 142{ 143 int count = 0; 144 bool saw_insn = false; 145 rtx insn; 146 147 for (insn = f; insn; insn = NEXT_INSN (insn)) 148 { 149 /* Code labels and barriers causes curent basic block to be 150 terminated at previous real insn. */ 151 if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER) 152 && saw_insn) 153 count++, saw_insn = false; 154 155 /* Start basic block if needed. */ 156 if (!saw_insn && inside_basic_block_p (insn)) 157 saw_insn = true; 158 159 /* Control flow insn causes current basic block to be terminated. */ 160 if (saw_insn && control_flow_insn_p (insn)) 161 count++, saw_insn = false; 162 } 163 164 if (saw_insn) 165 count++; 166 167 /* The rest of the compiler works a bit smoother when we don't have to 168 check for the edge case of do-nothing functions with no basic blocks. */ 169 if (count == 0) 170 { 171 emit_insn (gen_rtx_USE (VOIDmode, const0_rtx)); 172 count = 1; 173 } 174 175 return count; 176} 177 178/* Scan a list of insns for labels referred to other than by jumps. 179 This is used to scan the alternatives of a call placeholder. */ 180 181static rtx 182find_label_refs (f, lvl) 183 rtx f; 184 rtx lvl; 185{ 186 rtx insn; 187 188 for (insn = f; insn; insn = NEXT_INSN (insn)) 189 if (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN) 190 { 191 rtx note; 192 193 /* Make a list of all labels referred to other than by jumps 194 (which just don't have the REG_LABEL notes). 195 196 Make a special exception for labels followed by an ADDR*VEC, 197 as this would be a part of the tablejump setup code. 198 199 Make a special exception to registers loaded with label 200 values just before jump insns that use them. */ 201 202 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 203 if (REG_NOTE_KIND (note) == REG_LABEL) 204 { 205 rtx lab = XEXP (note, 0), next; 206 207 if ((next = next_nonnote_insn (lab)) != NULL 208 && GET_CODE (next) == JUMP_INSN 209 && (GET_CODE (PATTERN (next)) == ADDR_VEC 210 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) 211 ; 212 else if (GET_CODE (lab) == NOTE) 213 ; 214 else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN 215 && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab)) 216 ; 217 else 218 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl); 219 } 220 } 221 222 return lvl; 223} 224 225/* Create an edge between two basic blocks. FLAGS are auxiliary information 226 about the edge that is accumulated between calls. */ 227 228/* Create an edge from a basic block to a label. */ 229 230static void 231make_label_edge (edge_cache, src, label, flags) 232 sbitmap *edge_cache; 233 basic_block src; 234 rtx label; 235 int flags; 236{ 237 if (GET_CODE (label) != CODE_LABEL) 238 abort (); 239 240 /* If the label was never emitted, this insn is junk, but avoid a 241 crash trying to refer to BLOCK_FOR_INSN (label). This can happen 242 as a result of a syntax error and a diagnostic has already been 243 printed. */ 244 245 if (INSN_UID (label) == 0) 246 return; 247 248 cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags); 249} 250 251/* Create the edges generated by INSN in REGION. */ 252 253static void 254make_eh_edge (edge_cache, src, insn) 255 sbitmap *edge_cache; 256 basic_block src; 257 rtx insn; 258{ 259 int is_call = GET_CODE (insn) == CALL_INSN ? EDGE_ABNORMAL_CALL : 0; 260 rtx handlers, i; 261 262 handlers = reachable_handlers (insn); 263 264 for (i = handlers; i; i = XEXP (i, 1)) 265 make_label_edge (edge_cache, src, XEXP (i, 0), 266 EDGE_ABNORMAL | EDGE_EH | is_call); 267 268 free_INSN_LIST_list (&handlers); 269} 270 271/* Identify the edges between basic blocks MIN to MAX. 272 273 NONLOCAL_LABEL_LIST is a list of non-local labels in the function. Blocks 274 that are otherwise unreachable may be reachable with a non-local goto. 275 276 BB_EH_END is an array indexed by basic block number in which we record 277 the list of exception regions active at the end of the basic block. */ 278 279static void 280make_edges (label_value_list, min, max, update_p) 281 rtx label_value_list; 282 int min, max, update_p; 283{ 284 int i; 285 sbitmap *edge_cache = NULL; 286 287 /* Assume no computed jump; revise as we create edges. */ 288 current_function_has_computed_jump = 0; 289 290 /* Heavy use of computed goto in machine-generated code can lead to 291 nearly fully-connected CFGs. In that case we spend a significant 292 amount of time searching the edge lists for duplicates. */ 293 if (forced_labels || label_value_list) 294 { 295 edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); 296 sbitmap_vector_zero (edge_cache, n_basic_blocks); 297 298 if (update_p) 299 for (i = min; i <= max; ++i) 300 { 301 edge e; 302 303 for (e = BASIC_BLOCK (i)->succ; e ; e = e->succ_next) 304 if (e->dest != EXIT_BLOCK_PTR) 305 SET_BIT (edge_cache[i], e->dest->index); 306 } 307 } 308 309 /* By nature of the way these get numbered, block 0 is always the entry. */ 310 if (min == 0) 311 cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), 312 EDGE_FALLTHRU); 313 314 for (i = min; i <= max; ++i) 315 { 316 basic_block bb = BASIC_BLOCK (i); 317 rtx insn, x; 318 enum rtx_code code; 319 int force_fallthru = 0; 320 321 if (GET_CODE (bb->head) == CODE_LABEL && LABEL_ALTERNATE_NAME (bb->head)) 322 cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0); 323 324 /* Examine the last instruction of the block, and discover the 325 ways we can leave the block. */ 326 327 insn = bb->end; 328 code = GET_CODE (insn); 329 330 /* A branch. */ 331 if (code == JUMP_INSN) 332 { 333 rtx tmp; 334 335 /* Recognize exception handling placeholders. */ 336 if (GET_CODE (PATTERN (insn)) == RESX) 337 make_eh_edge (edge_cache, bb, insn); 338 339 /* Recognize a non-local goto as a branch outside the 340 current function. */ 341 else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) 342 ; 343 344 /* ??? Recognize a tablejump and do the right thing. */ 345 else if ((tmp = JUMP_LABEL (insn)) != NULL_RTX 346 && (tmp = NEXT_INSN (tmp)) != NULL_RTX 347 && GET_CODE (tmp) == JUMP_INSN 348 && (GET_CODE (PATTERN (tmp)) == ADDR_VEC 349 || GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC)) 350 { 351 rtvec vec; 352 int j; 353 354 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC) 355 vec = XVEC (PATTERN (tmp), 0); 356 else 357 vec = XVEC (PATTERN (tmp), 1); 358 359 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 360 make_label_edge (edge_cache, bb, 361 XEXP (RTVEC_ELT (vec, j), 0), 0); 362 363 /* Some targets (eg, ARM) emit a conditional jump that also 364 contains the out-of-range target. Scan for these and 365 add an edge if necessary. */ 366 if ((tmp = single_set (insn)) != NULL 367 && SET_DEST (tmp) == pc_rtx 368 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 369 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) 370 make_label_edge (edge_cache, bb, 371 XEXP (XEXP (SET_SRC (tmp), 2), 0), 0); 372 373#ifdef CASE_DROPS_THROUGH 374 /* Silly VAXen. The ADDR_VEC is going to be in the way of 375 us naturally detecting fallthru into the next block. */ 376 force_fallthru = 1; 377#endif 378 } 379 380 /* If this is a computed jump, then mark it as reaching 381 everything on the label_value_list and forced_labels list. */ 382 else if (computed_jump_p (insn)) 383 { 384 current_function_has_computed_jump = 1; 385 386 for (x = label_value_list; x; x = XEXP (x, 1)) 387 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); 388 389 for (x = forced_labels; x; x = XEXP (x, 1)) 390 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL); 391 } 392 393 /* Returns create an exit out. */ 394 else if (returnjump_p (insn)) 395 cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0); 396 397 /* Otherwise, we have a plain conditional or unconditional jump. */ 398 else 399 { 400 if (! JUMP_LABEL (insn)) 401 abort (); 402 make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0); 403 } 404 } 405 406 /* If this is a sibling call insn, then this is in effect a combined call 407 and return, and so we need an edge to the exit block. No need to 408 worry about EH edges, since we wouldn't have created the sibling call 409 in the first place. */ 410 if (code == CALL_INSN && SIBLING_CALL_P (insn)) 411 cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 412 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); 413 414 /* If this is a CALL_INSN, then mark it as reaching the active EH 415 handler for this CALL_INSN. If we're handling non-call 416 exceptions then any insn can reach any of the active handlers. 417 Also mark the CALL_INSN as reaching any nonlocal goto handler. */ 418 else if (code == CALL_INSN || flag_non_call_exceptions) 419 { 420 /* Add any appropriate EH edges. */ 421 make_eh_edge (edge_cache, bb, insn); 422 423 if (code == CALL_INSN && nonlocal_goto_handler_labels) 424 { 425 /* ??? This could be made smarter: in some cases it's possible 426 to tell that certain calls will not do a nonlocal goto. 427 For example, if the nested functions that do the nonlocal 428 gotos do not have their addresses taken, then only calls to 429 those functions or to other nested functions that use them 430 could possibly do nonlocal gotos. */ 431 432 /* We do know that a REG_EH_REGION note with a value less 433 than 0 is guaranteed not to perform a non-local goto. */ 434 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX); 435 436 if (!note || INTVAL (XEXP (note, 0)) >= 0) 437 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1)) 438 make_label_edge (edge_cache, bb, XEXP (x, 0), 439 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); 440 } 441 } 442 443 /* Find out if we can drop through to the next block. */ 444 insn = next_nonnote_insn (insn); 445 if (!insn || (i + 1 == n_basic_blocks && force_fallthru)) 446 cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); 447 else if (i + 1 < n_basic_blocks) 448 { 449 rtx tmp = BLOCK_HEAD (i + 1); 450 if (GET_CODE (tmp) == NOTE) 451 tmp = next_nonnote_insn (tmp); 452 if (force_fallthru || insn == tmp) 453 cached_make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), 454 EDGE_FALLTHRU); 455 } 456 } 457 458 if (edge_cache) 459 sbitmap_vector_free (edge_cache); 460} 461 462/* Find all basic blocks of the function whose first insn is F. 463 464 Collect and return a list of labels whose addresses are taken. This 465 will be used in make_edges for use with computed gotos. */ 466 467static void 468find_basic_blocks_1 (f) 469 rtx f; 470{ 471 rtx insn, next; 472 int i = 0; 473 rtx bb_note = NULL_RTX; 474 rtx lvl = NULL_RTX; 475 rtx trll = NULL_RTX; 476 rtx head = NULL_RTX; 477 rtx end = NULL_RTX; 478 479 /* We process the instructions in a slightly different way than we did 480 previously. This is so that we see a NOTE_BASIC_BLOCK after we have 481 closed out the previous block, so that it gets attached at the proper 482 place. Since this form should be equivalent to the previous, 483 count_basic_blocks continues to use the old form as a check. */ 484 485 for (insn = f; insn; insn = next) 486 { 487 enum rtx_code code = GET_CODE (insn); 488 489 next = NEXT_INSN (insn); 490 491 if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER) 492 && head) 493 { 494 create_basic_block_structure (i++, head, end, bb_note); 495 head = end = NULL_RTX; 496 bb_note = NULL_RTX; 497 } 498 499 if (inside_basic_block_p (insn)) 500 { 501 if (head == NULL_RTX) 502 head = insn; 503 end = insn; 504 } 505 506 if (head && control_flow_insn_p (insn)) 507 { 508 create_basic_block_structure (i++, head, end, bb_note); 509 head = end = NULL_RTX; 510 bb_note = NULL_RTX; 511 } 512 513 switch (code) 514 { 515 case NOTE: 516 { 517 int kind = NOTE_LINE_NUMBER (insn); 518 519 /* Look for basic block notes with which to keep the 520 basic_block_info pointers stable. Unthread the note now; 521 we'll put it back at the right place in create_basic_block. 522 Or not at all if we've already found a note in this block. */ 523 if (kind == NOTE_INSN_BASIC_BLOCK) 524 { 525 if (bb_note == NULL_RTX) 526 bb_note = insn; 527 else 528 next = delete_insn (insn); 529 } 530 break; 531 } 532 533 case CODE_LABEL: 534 case JUMP_INSN: 535 case INSN: 536 case BARRIER: 537 break; 538 539 case CALL_INSN: 540 if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER) 541 { 542 /* Scan each of the alternatives for label refs. */ 543 lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl); 544 lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl); 545 lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl); 546 /* Record its tail recursion label, if any. */ 547 if (XEXP (PATTERN (insn), 3) != NULL_RTX) 548 trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll); 549 } 550 break; 551 552 default: 553 abort (); 554 } 555 556 if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN) 557 { 558 rtx note; 559 560 /* Make a list of all labels referred to other than by jumps. 561 562 Make a special exception for labels followed by an ADDR*VEC, 563 as this would be a part of the tablejump setup code. 564 565 Make a special exception to registers loaded with label 566 values just before jump insns that use them. */ 567 568 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 569 if (REG_NOTE_KIND (note) == REG_LABEL) 570 { 571 rtx lab = XEXP (note, 0), next; 572 573 if ((next = next_nonnote_insn (lab)) != NULL 574 && GET_CODE (next) == JUMP_INSN 575 && (GET_CODE (PATTERN (next)) == ADDR_VEC 576 || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)) 577 ; 578 else if (GET_CODE (lab) == NOTE) 579 ; 580 else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN 581 && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab)) 582 ; 583 else 584 lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl); 585 } 586 } 587 } 588 589 if (head != NULL_RTX) 590 create_basic_block_structure (i++, head, end, bb_note); 591 else if (bb_note) 592 delete_insn (bb_note); 593 594 if (i != n_basic_blocks) 595 abort (); 596 597 label_value_list = lvl; 598 tail_recursion_label_list = trll; 599} 600 601 602/* Find basic blocks of the current function. 603 F is the first insn of the function and NREGS the number of register 604 numbers in use. */ 605 606void 607find_basic_blocks (f, nregs, file) 608 rtx f; 609 int nregs ATTRIBUTE_UNUSED; 610 FILE *file ATTRIBUTE_UNUSED; 611{ 612 int max_uid; 613 timevar_push (TV_CFG); 614 615 basic_block_for_insn = 0; 616 617 /* Flush out existing data. */ 618 if (basic_block_info != NULL) 619 { 620 int i; 621 622 clear_edges (); 623 624 /* Clear bb->aux on all extant basic blocks. We'll use this as a 625 tag for reuse during create_basic_block, just in case some pass 626 copies around basic block notes improperly. */ 627 for (i = 0; i < n_basic_blocks; ++i) 628 BASIC_BLOCK (i)->aux = NULL; 629 630 VARRAY_FREE (basic_block_info); 631 } 632 633 n_basic_blocks = count_basic_blocks (f); 634 635 /* Size the basic block table. The actual structures will be allocated 636 by find_basic_blocks_1, since we want to keep the structure pointers 637 stable across calls to find_basic_blocks. */ 638 /* ??? This whole issue would be much simpler if we called find_basic_blocks 639 exactly once, and thereafter we don't have a single long chain of 640 instructions at all until close to the end of compilation when we 641 actually lay them out. */ 642 643 VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info"); 644 645 find_basic_blocks_1 (f); 646 647 /* Record the block to which an insn belongs. */ 648 /* ??? This should be done another way, by which (perhaps) a label is 649 tagged directly with the basic block that it starts. It is used for 650 more than that currently, but IMO that is the only valid use. */ 651 652 max_uid = get_max_uid (); 653#ifdef AUTO_INC_DEC 654 /* Leave space for insns life_analysis makes in some cases for auto-inc. 655 These cases are rare, so we don't need too much space. */ 656 max_uid += max_uid / 10; 657#endif 658 659 compute_bb_for_insn (max_uid); 660 661 /* Discover the edges of our cfg. */ 662 make_edges (label_value_list, 0, n_basic_blocks - 1, 0); 663 664 /* Do very simple cleanup now, for the benefit of code that runs between 665 here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */ 666 tidy_fallthru_edges (); 667 668#ifdef ENABLE_CHECKING 669 verify_flow_info (); 670#endif 671 timevar_pop (TV_CFG); 672} 673 674/* State of basic block as seen by find_sub_basic_blocks. */ 675enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT}; 676 677#define STATE(BB) (enum state) ((size_t) (BB)->aux) 678#define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE)) 679 680/* Scan basic block BB for possible BB boundaries inside the block 681 and create new basic blocks in the progress. */ 682 683static void 684find_bb_boundaries (bb) 685 basic_block bb; 686{ 687 rtx insn = bb->head; 688 rtx end = bb->end; 689 rtx flow_transfer_insn = NULL_RTX; 690 edge fallthru = NULL; 691 692 if (insn == bb->end) 693 return; 694 695 if (GET_CODE (insn) == CODE_LABEL) 696 insn = NEXT_INSN (insn); 697 698 /* Scan insn chain and try to find new basic block boundaries. */ 699 while (1) 700 { 701 enum rtx_code code = GET_CODE (insn); 702 703 /* On code label, split current basic block. */ 704 if (code == CODE_LABEL) 705 { 706 fallthru = split_block (bb, PREV_INSN (insn)); 707 if (flow_transfer_insn) 708 bb->end = flow_transfer_insn; 709 710 bb = fallthru->dest; 711 remove_edge (fallthru); 712 flow_transfer_insn = NULL_RTX; 713 if (LABEL_ALTERNATE_NAME (insn)) 714 make_edge (ENTRY_BLOCK_PTR, bb, 0); 715 } 716 717 /* In case we've previously seen an insn that effects a control 718 flow transfer, split the block. */ 719 if (flow_transfer_insn && inside_basic_block_p (insn)) 720 { 721 fallthru = split_block (bb, PREV_INSN (insn)); 722 bb->end = flow_transfer_insn; 723 bb = fallthru->dest; 724 remove_edge (fallthru); 725 flow_transfer_insn = NULL_RTX; 726 } 727 728 if (control_flow_insn_p (insn)) 729 flow_transfer_insn = insn; 730 if (insn == end) 731 break; 732 insn = NEXT_INSN (insn); 733 } 734 735 /* In case expander replaced normal insn by sequence terminating by 736 return and barrier, or possibly other sequence not behaving like 737 ordinary jump, we need to take care and move basic block boundary. */ 738 if (flow_transfer_insn) 739 bb->end = flow_transfer_insn; 740 741 /* We've possibly replaced the conditional jump by conditional jump 742 followed by cleanup at fallthru edge, so the outgoing edges may 743 be dead. */ 744 purge_dead_edges (bb); 745} 746 747/* Assume that frequency of basic block B is known. Compute frequencies 748 and probabilities of outgoing edges. */ 749 750static void 751compute_outgoing_frequencies (b) 752 basic_block b; 753{ 754 edge e, f; 755 756 if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next) 757 { 758 rtx note = find_reg_note (b->end, REG_BR_PROB, NULL); 759 int probability; 760 761 if (!note) 762 return; 763 764 probability = INTVAL (XEXP (find_reg_note (b->end, 765 REG_BR_PROB, NULL), 766 0)); 767 e = BRANCH_EDGE (b); 768 e->probability = probability; 769 e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) 770 / REG_BR_PROB_BASE); 771 f = FALLTHRU_EDGE (b); 772 f->probability = REG_BR_PROB_BASE - probability; 773 f->count = b->count - e->count; 774 } 775 776 if (b->succ && !b->succ->succ_next) 777 { 778 e = b->succ; 779 e->probability = REG_BR_PROB_BASE; 780 e->count = b->count; 781 } 782} 783 784/* Assume that someone emitted code with control flow instructions to the 785 basic block. Update the data structure. */ 786 787void 788find_many_sub_basic_blocks (blocks) 789 sbitmap blocks; 790{ 791 int i; 792 int min, max; 793 794 for (i = 0; i < n_basic_blocks; i++) 795 SET_STATE (BASIC_BLOCK (i), 796 TEST_BIT (blocks, i) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL); 797 798 for (i = 0; i < n_basic_blocks; i++) 799 if (STATE (BASIC_BLOCK (i)) == BLOCK_TO_SPLIT) 800 find_bb_boundaries (BASIC_BLOCK (i)); 801 802 for (i = 0; i < n_basic_blocks; i++) 803 if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL) 804 break; 805 806 min = max = i; 807 for (; i < n_basic_blocks; i++) 808 if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL) 809 max = i; 810 811 /* Now re-scan and wire in all edges. This expect simple (conditional) 812 jumps at the end of each new basic blocks. */ 813 make_edges (NULL, min, max, 1); 814 815 /* Update branch probabilities. Expect only (un)conditional jumps 816 to be created with only the forward edges. */ 817 for (i = min; i <= max; i++) 818 { 819 edge e; 820 basic_block b = BASIC_BLOCK (i); 821 822 if (STATE (b) == BLOCK_ORIGINAL) 823 continue; 824 if (STATE (b) == BLOCK_NEW) 825 { 826 b->count = 0; 827 b->frequency = 0; 828 for (e = b->pred; e; e=e->pred_next) 829 { 830 b->count += e->count; 831 b->frequency += EDGE_FREQUENCY (e); 832 } 833 } 834 835 compute_outgoing_frequencies (b); 836 } 837 838 for (i = 0; i < n_basic_blocks; i++) 839 SET_STATE (BASIC_BLOCK (i), 0); 840} 841 842/* Like above but for single basic block only. */ 843 844void 845find_sub_basic_blocks (bb) 846 basic_block bb; 847{ 848 int i; 849 int min, max; 850 basic_block next = (bb->index == n_basic_blocks - 1 851 ? NULL : BASIC_BLOCK (bb->index + 1)); 852 853 min = bb->index; 854 find_bb_boundaries (bb); 855 max = (next ? next->index : n_basic_blocks) - 1; 856 857 /* Now re-scan and wire in all edges. This expect simple (conditional) 858 jumps at the end of each new basic blocks. */ 859 make_edges (NULL, min, max, 1); 860 861 /* Update branch probabilities. Expect only (un)conditional jumps 862 to be created with only the forward edges. */ 863 for (i = min; i <= max; i++) 864 { 865 edge e; 866 basic_block b = BASIC_BLOCK (i); 867 868 if (i != min) 869 { 870 b->count = 0; 871 b->frequency = 0; 872 for (e = b->pred; e; e=e->pred_next) 873 { 874 b->count += e->count; 875 b->frequency += EDGE_FREQUENCY (e); 876 } 877 } 878 879 compute_outgoing_frequencies (b); 880 } 881} 882