gcc/cfgbuild.c

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