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 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-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 \f
  35 #include "config.h"
  36 #include "system.h"
  37 #include "coretypes.h"
  38 #include "tm.h"
  39 #include "tree.h"
  40 #include "rtl.h"
  41 #include "hard-reg-set.h"
  42 #include "basic-block.h"
  43 #include "regs.h"
  44 #include "flags.h"
  45 #include "output.h"
  46 #include "function.h"
  47 #include "except.h"
  48 #include "toplev.h"
  49 #include "timevar.h"
  50
  51 static int count_basic_blocks (rtx);
  52 static void find_basic_blocks_1 (rtx);
  53 static void make_edges (basic_block, basic_block, int);
  54 static void make_label_edge (sbitmap *, basic_block, rtx, int);
  55 static void find_bb_boundaries (basic_block);
  56 static void compute_outgoing_frequencies (basic_block);
  57 \f
  58 /* Return true if insn is something that should be contained inside basic
  59    block.  */
  60
  61 bool
  62 inside_basic_block_p (rtx insn)
  63 {
  64   switch (GET_CODE (insn))
  65     {
  66     case CODE_LABEL:
  67       /* Avoid creating of basic block for jumptables.  */
  68       return (NEXT_INSN (insn) == 0
  69               || !JUMP_P (NEXT_INSN (insn))
  70               || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC
  71                   && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC));
  72
  73     case JUMP_INSN:
  74       return (GET_CODE (PATTERN (insn)) != ADDR_VEC
  75               && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
  76
  77     case CALL_INSN:
  78     case INSN:
  79       return true;
  80
  81     case BARRIER:
  82     case NOTE:
  83       return false;
  84
  85     default:
  86       abort ();
  87     }
  88 }
  89
  90 /* Return true if INSN may cause control flow transfer, so it should be last in
  91    the basic block.  */
  92
  93 bool
  94 control_flow_insn_p (rtx insn)
  95 {
  96   rtx note;
  97
  98   switch (GET_CODE (insn))
  99     {
 100     case NOTE:
 101     case CODE_LABEL:
 102       return false;
 103
 104     case JUMP_INSN:
 105       /* Jump insn always causes control transfer except for tablejumps.  */
 106       return (GET_CODE (PATTERN (insn)) != ADDR_VEC
 107               && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
 108
 109     case CALL_INSN:
 110       /* Noreturn and sibling call instructions terminate the basic blocks
 111          (but only if they happen unconditionally).  */
 112       if ((SIBLING_CALL_P (insn)
 113            || find_reg_note (insn, REG_NORETURN, 0))
 114           && GET_CODE (PATTERN (insn)) != COND_EXEC)
 115         return true;
 116       /* Call insn may return to the nonlocal goto handler.  */
 117       return ((nonlocal_goto_handler_labels
 118                && (0 == (note = find_reg_note (insn, REG_EH_REGION,
 119                                                NULL_RTX))
 120                    || INTVAL (XEXP (note, 0)) >= 0))
 121               /* Or may trap.  */
 122               || can_throw_internal (insn));
 123
 124     case INSN:
 125       return (flag_non_call_exceptions && can_throw_internal (insn));
 126
 127     case BARRIER:
 128       /* It is nonsense to reach barrier when looking for the
 129          end of basic block, but before dead code is eliminated
 130          this may happen.  */
 131       return false;
 132
 133     default:
 134       abort ();
 135     }
 136 }
 137
 138 /* Count the basic blocks of the function.  */
 139
 140 static int
 141 count_basic_blocks (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 current basic block to be
 150          terminated at previous real insn.  */
 151       if ((LABEL_P (insn) || BARRIER_P (insn))
 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 \f
 178 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
 179    about the edge that is accumulated between calls.  */
 180
 181 /* Create an edge from a basic block to a label.  */
 182
 183 static void
 184 make_label_edge (sbitmap *edge_cache, basic_block src, rtx label, int flags)
 185 {
 186   if (!LABEL_P (label))
 187     abort ();
 188
 189   /* If the label was never emitted, this insn is junk, but avoid a
 190      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
 191      as a result of a syntax error and a diagnostic has already been
 192      printed.  */
 193
 194   if (INSN_UID (label) == 0)
 195     return;
 196
 197   cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
 198 }
 199
 200 /* Create the edges generated by INSN in REGION.  */
 201
 202 void
 203 rtl_make_eh_edge (sbitmap *edge_cache, basic_block src, rtx insn)
 204 {
 205   int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0;
 206   rtx handlers, i;
 207
 208   handlers = reachable_handlers (insn);
 209
 210   for (i = handlers; i; i = XEXP (i, 1))
 211     make_label_edge (edge_cache, src, XEXP (i, 0),
 212                      EDGE_ABNORMAL | EDGE_EH | is_call);
 213
 214   free_INSN_LIST_list (&handlers);
 215 }
 216
 217 /* Identify the edges between basic blocks MIN to MAX.
 218
 219    NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
 220    that are otherwise unreachable may be reachable with a non-local goto.
 221
 222    BB_EH_END is an array indexed by basic block number in which we record
 223    the list of exception regions active at the end of the basic block.  */
 224
 225 static void
 226 make_edges (basic_block min, basic_block max, int update_p)
 227 {
 228   basic_block bb;
 229   sbitmap *edge_cache = NULL;
 230
 231   /* Assume no computed jump; revise as we create edges.  */
 232   current_function_has_computed_jump = 0;
 233
 234   /* If we are partitioning hot and cold basic blocks into separate
 235      sections, we cannot assume there is no computed jump (partitioning
 236      sometimes requires the use of indirect jumps; see comments about
 237      partitioning at the top of bb-reorder.c:partition_hot_cold_basic_blocks
 238      for complete details).  */
 239
 240   if (flag_reorder_blocks_and_partition)
 241     current_function_has_computed_jump = 1;
 242
 243   /* Heavy use of computed goto in machine-generated code can lead to
 244      nearly fully-connected CFGs.  In that case we spend a significant
 245      amount of time searching the edge lists for duplicates.  */
 246   if (forced_labels || cfun->max_jumptable_ents > 100)
 247     {
 248       edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 249       sbitmap_vector_zero (edge_cache, last_basic_block);
 250
 251       if (update_p)
 252         FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 253           {
 254             edge e;
 255
 256             for (e = bb->succ; e ; e = e->succ_next)
 257               if (e->dest != EXIT_BLOCK_PTR)
 258                 SET_BIT (edge_cache[bb->index], e->dest->index);
 259           }
 260     }
 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     cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, min,
 266                       EDGE_FALLTHRU);
 267
 268   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 269     {
 270       rtx insn, x;
 271       enum rtx_code code;
 272       int force_fallthru = 0;
 273       edge e;
 274
 275       if (LABEL_P (BB_HEAD (bb))
 276           && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
 277         cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
 278
 279       /* Examine the last instruction of the block, and discover the
 280          ways we can leave the block.  */
 281
 282       insn = BB_END (bb);
 283       code = GET_CODE (insn);
 284
 285       /* A branch.  */
 286       if (code == JUMP_INSN)
 287         {
 288           rtx tmp;
 289
 290           /* Recognize exception handling placeholders.  */
 291           if (GET_CODE (PATTERN (insn)) == RESX)
 292             rtl_make_eh_edge (edge_cache, bb, insn);
 293
 294           /* Recognize a non-local goto as a branch outside the
 295              current function.  */
 296           else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
 297             ;
 298
 299           /* Recognize a tablejump and do the right thing.  */
 300           else if (tablejump_p (insn, NULL, &tmp))
 301             {
 302               rtvec vec;
 303               int j;
 304
 305               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
 306                 vec = XVEC (PATTERN (tmp), 0);
 307               else
 308                 vec = XVEC (PATTERN (tmp), 1);
 309
 310               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
 311                 make_label_edge (edge_cache, bb,
 312                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
 313
 314               /* Some targets (eg, ARM) emit a conditional jump that also
 315                  contains the out-of-range target.  Scan for these and
 316                  add an edge if necessary.  */
 317               if ((tmp = single_set (insn)) != NULL
 318                   && SET_DEST (tmp) == pc_rtx
 319                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
 320                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 321                 make_label_edge (edge_cache, bb,
 322                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
 323
 324 #ifdef CASE_DROPS_THROUGH
 325               /* Silly VAXen.  The ADDR_VEC is going to be in the way of
 326                  us naturally detecting fallthru into the next block.  */
 327               force_fallthru = 1;
 328 #endif
 329             }
 330
 331           /* If this is a computed jump, then mark it as reaching
 332              everything on the forced_labels list.  */
 333           else if (computed_jump_p (insn))
 334             {
 335               current_function_has_computed_jump = 1;
 336
 337               for (x = forced_labels; x; x = XEXP (x, 1))
 338                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
 339             }
 340
 341           /* Returns create an exit out.  */
 342           else if (returnjump_p (insn))
 343             cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
 344
 345           /* Otherwise, we have a plain conditional or unconditional jump.  */
 346           else
 347             {
 348               if (! JUMP_LABEL (insn))
 349                 abort ();
 350               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
 351             }
 352         }
 353
 354       /* If this is a sibling call insn, then this is in effect a combined call
 355          and return, and so we need an edge to the exit block.  No need to
 356          worry about EH edges, since we wouldn't have created the sibling call
 357          in the first place.  */
 358       if (code == CALL_INSN && SIBLING_CALL_P (insn))
 359         cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
 360                           EDGE_SIBCALL | EDGE_ABNORMAL);
 361
 362       /* If this is a CALL_INSN, then mark it as reaching the active EH
 363          handler for this CALL_INSN.  If we're handling non-call
 364          exceptions then any insn can reach any of the active handlers.
 365          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
 366       else if (code == CALL_INSN || flag_non_call_exceptions)
 367         {
 368           /* Add any appropriate EH edges.  */
 369           rtl_make_eh_edge (edge_cache, bb, insn);
 370
 371           if (code == CALL_INSN && nonlocal_goto_handler_labels)
 372             {
 373               /* ??? This could be made smarter: in some cases it's possible
 374                  to tell that certain calls will not do a nonlocal goto.
 375                  For example, if the nested functions that do the nonlocal
 376                  gotos do not have their addresses taken, then only calls to
 377                  those functions or to other nested functions that use them
 378                  could possibly do nonlocal gotos.  */
 379
 380               /* We do know that a REG_EH_REGION note with a value less
 381                  than 0 is guaranteed not to perform a non-local goto.  */
 382               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
 383
 384               if (!note || INTVAL (XEXP (note, 0)) >=  0)
 385                 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
 386                   make_label_edge (edge_cache, bb, XEXP (x, 0),
 387                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
 388             }
 389         }
 390
 391       /* Find out if we can drop through to the next block.  */
 392       insn = NEXT_INSN (insn);
 393       for (e = bb->succ; e; e = e->succ_next)
 394         if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_FALLTHRU)
 395           {
 396             insn = 0;
 397             break;
 398           }
 399       while (insn
 400              && NOTE_P (insn)
 401              && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
 402         insn = NEXT_INSN (insn);
 403
 404       if (!insn || (bb->next_bb == EXIT_BLOCK_PTR && force_fallthru))
 405         cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 406       else if (bb->next_bb != EXIT_BLOCK_PTR)
 407         {
 408           if (force_fallthru || insn == BB_HEAD (bb->next_bb))
 409             cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
 410         }
 411     }
 412
 413   if (edge_cache)
 414     sbitmap_vector_free (edge_cache);
 415 }
 416 \f
 417 /* Find all basic blocks of the function whose first insn is F.
 418
 419    Collect and return a list of labels whose addresses are taken.  This
 420    will be used in make_edges for use with computed gotos.  */
 421
 422 static void
 423 find_basic_blocks_1 (rtx f)
 424 {
 425   rtx insn, next;
 426   rtx bb_note = NULL_RTX;
 427   rtx head = NULL_RTX;
 428   rtx end = NULL_RTX;
 429   basic_block prev = ENTRY_BLOCK_PTR;
 430
 431   /* We process the instructions in a slightly different way than we did
 432      previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
 433      closed out the previous block, so that it gets attached at the proper
 434      place.  Since this form should be equivalent to the previous,
 435      count_basic_blocks continues to use the old form as a check.  */
 436
 437   for (insn = f; insn; insn = next)
 438     {
 439       enum rtx_code code = GET_CODE (insn);
 440
 441       next = NEXT_INSN (insn);
 442
 443       if ((LABEL_P (insn) || BARRIER_P (insn))
 444           && head)
 445         {
 446           prev = create_basic_block_structure (head, end, bb_note, prev);
 447           head = end = NULL_RTX;
 448           bb_note = NULL_RTX;
 449         }
 450
 451       if (inside_basic_block_p (insn))
 452         {
 453           if (head == NULL_RTX)
 454             head = insn;
 455           end = insn;
 456         }
 457
 458       if (head && control_flow_insn_p (insn))
 459         {
 460           prev = create_basic_block_structure (head, end, bb_note, prev);
 461           head = end = NULL_RTX;
 462           bb_note = NULL_RTX;
 463         }
 464
 465       switch (code)
 466         {
 467         case NOTE:
 468           {
 469             int kind = NOTE_LINE_NUMBER (insn);
 470
 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 (kind == NOTE_INSN_BASIC_BLOCK)
 476               {
 477                 if (bb_note == NULL_RTX)
 478                   bb_note = insn;
 479                 else
 480                   next = delete_insn (insn);
 481               }
 482             break;
 483           }
 484
 485         case CODE_LABEL:
 486         case JUMP_INSN:
 487         case CALL_INSN:
 488         case INSN:
 489         case BARRIER:
 490           break;
 491
 492         default:
 493           abort ();
 494         }
 495     }
 496
 497   if (head != NULL_RTX)
 498     create_basic_block_structure (head, end, bb_note, prev);
 499   else if (bb_note)
 500     delete_insn (bb_note);
 501
 502   if (last_basic_block != n_basic_blocks)
 503     abort ();
 504
 505   clear_aux_for_blocks ();
 506 }
 507
 508
 509 /* Find basic blocks of the current function.
 510    F is the first insn of the function and NREGS the number of register
 511    numbers in use.  */
 512
 513 void
 514 find_basic_blocks (rtx f, int nregs ATTRIBUTE_UNUSED,
 515                    FILE *file ATTRIBUTE_UNUSED)
 516 {
 517   basic_block bb;
 518
 519   timevar_push (TV_CFG);
 520
 521   /* Flush out existing data.  */
 522   if (basic_block_info != NULL)
 523     {
 524       clear_edges ();
 525
 526       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 527          tag for reuse during create_basic_block, just in case some pass
 528          copies around basic block notes improperly.  */
 529       FOR_EACH_BB (bb)
 530         bb->aux = NULL;
 531
 532       basic_block_info = NULL;
 533     }
 534
 535   n_basic_blocks = count_basic_blocks (f);
 536   last_basic_block = 0;
 537   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 538   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 539
 540   /* Size the basic block table.  The actual structures will be allocated
 541      by find_basic_blocks_1, since we want to keep the structure pointers
 542      stable across calls to find_basic_blocks.  */
 543   /* ??? This whole issue would be much simpler if we called find_basic_blocks
 544      exactly once, and thereafter we don't have a single long chain of
 545      instructions at all until close to the end of compilation when we
 546      actually lay them out.  */
 547
 548   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 549
 550   find_basic_blocks_1 (f);
 551
 552   profile_status = PROFILE_ABSENT;
 553
 554   /* Discover the edges of our cfg.  */
 555   make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
 556
 557   /* Do very simple cleanup now, for the benefit of code that runs between
 558      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 559   tidy_fallthru_edges ();
 560
 561 #ifdef ENABLE_CHECKING
 562   verify_flow_info ();
 563 #endif
 564   timevar_pop (TV_CFG);
 565 }
 566 \f
 567 /* State of basic block as seen by find_sub_basic_blocks.  */
 568 enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
 569
 570 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 571 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 572
 573 /* Scan basic block BB for possible BB boundaries inside the block
 574    and create new basic blocks in the progress.  */
 575
 576 static void
 577 find_bb_boundaries (basic_block bb)
 578 {
 579   rtx insn = BB_HEAD (bb);
 580   rtx end = BB_END (bb);
 581   rtx flow_transfer_insn = NULL_RTX;
 582   edge fallthru = NULL;
 583
 584   if (insn == BB_END (bb))
 585     return;
 586
 587   if (LABEL_P (insn))
 588     insn = NEXT_INSN (insn);
 589
 590   /* Scan insn chain and try to find new basic block boundaries.  */
 591   while (1)
 592     {
 593       enum rtx_code code = GET_CODE (insn);
 594
 595       /* On code label, split current basic block.  */
 596       if (code == CODE_LABEL)
 597         {
 598           fallthru = split_block (bb, PREV_INSN (insn));
 599           if (flow_transfer_insn)
 600             BB_END (bb) = flow_transfer_insn;
 601
 602           bb = fallthru->dest;
 603           remove_edge (fallthru);
 604           flow_transfer_insn = NULL_RTX;
 605           if (LABEL_ALT_ENTRY_P (insn))
 606             make_edge (ENTRY_BLOCK_PTR, bb, 0);
 607         }
 608
 609       /* In case we've previously seen an insn that effects a control
 610          flow transfer, split the block.  */
 611       if (flow_transfer_insn && inside_basic_block_p (insn))
 612         {
 613           fallthru = split_block (bb, PREV_INSN (insn));
 614           BB_END (bb) = flow_transfer_insn;
 615           bb = fallthru->dest;
 616           remove_edge (fallthru);
 617           flow_transfer_insn = NULL_RTX;
 618         }
 619
 620       if (control_flow_insn_p (insn))
 621         flow_transfer_insn = insn;
 622       if (insn == end)
 623         break;
 624       insn = NEXT_INSN (insn);
 625     }
 626
 627   /* In case expander replaced normal insn by sequence terminating by
 628      return and barrier, or possibly other sequence not behaving like
 629      ordinary jump, we need to take care and move basic block boundary.  */
 630   if (flow_transfer_insn)
 631     BB_END (bb) = flow_transfer_insn;
 632
 633   /* We've possibly replaced the conditional jump by conditional jump
 634      followed by cleanup at fallthru edge, so the outgoing edges may
 635      be dead.  */
 636   purge_dead_edges (bb);
 637 }
 638
 639 /*  Assume that frequency of basic block B is known.  Compute frequencies
 640     and probabilities of outgoing edges.  */
 641
 642 static void
 643 compute_outgoing_frequencies (basic_block b)
 644 {
 645   edge e, f;
 646
 647   if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
 648     {
 649       rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
 650       int probability;
 651
 652       if (!note)
 653         return;
 654
 655       probability = INTVAL (XEXP (note, 0));
 656       e = BRANCH_EDGE (b);
 657       e->probability = probability;
 658       e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 659                   / REG_BR_PROB_BASE);
 660       f = FALLTHRU_EDGE (b);
 661       f->probability = REG_BR_PROB_BASE - probability;
 662       f->count = b->count - e->count;
 663     }
 664
 665   if (b->succ && !b->succ->succ_next)
 666     {
 667       e = b->succ;
 668       e->probability = REG_BR_PROB_BASE;
 669       e->count = b->count;
 670     }
 671 }
 672
 673 /* Assume that someone emitted code with control flow instructions to the
 674    basic block.  Update the data structure.  */
 675
 676 void
 677 find_many_sub_basic_blocks (sbitmap blocks)
 678 {
 679   basic_block bb, min, max;
 680
 681   FOR_EACH_BB (bb)
 682     SET_STATE (bb,
 683                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 684
 685   FOR_EACH_BB (bb)
 686     if (STATE (bb) == BLOCK_TO_SPLIT)
 687       find_bb_boundaries (bb);
 688
 689   FOR_EACH_BB (bb)
 690     if (STATE (bb) != BLOCK_ORIGINAL)
 691       break;
 692
 693   min = max = bb;
 694   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 695     if (STATE (bb) != BLOCK_ORIGINAL)
 696       max = bb;
 697
 698   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 699      jumps at the end of each new basic blocks.  */
 700   make_edges (min, max, 1);
 701
 702   /* Update branch probabilities.  Expect only (un)conditional jumps
 703      to be created with only the forward edges.  */
 704   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 705     {
 706       edge e;
 707
 708       if (STATE (bb) == BLOCK_ORIGINAL)
 709         continue;
 710       if (STATE (bb) == BLOCK_NEW)
 711         {
 712           bb->count = 0;
 713           bb->frequency = 0;
 714           for (e = bb->pred; e; e = e->pred_next)
 715             {
 716               bb->count += e->count;
 717               bb->frequency += EDGE_FREQUENCY (e);
 718             }
 719         }
 720
 721       compute_outgoing_frequencies (bb);
 722     }
 723
 724   FOR_EACH_BB (bb)
 725     SET_STATE (bb, 0);
 726 }
 727
 728 /* Like above but for single basic block only.  */
 729
 730 void
 731 find_sub_basic_blocks (basic_block bb)
 732 {
 733   basic_block min, max, b;
 734   basic_block next = bb->next_bb;
 735
 736   min = bb;
 737   find_bb_boundaries (bb);
 738   max = next->prev_bb;
 739
 740   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 741      jumps at the end of each new basic blocks.  */
 742   make_edges (min, max, 1);
 743
 744   /* Update branch probabilities.  Expect only (un)conditional jumps
 745      to be created with only the forward edges.  */
 746   FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
 747     {
 748       edge e;
 749
 750       if (b != min)
 751         {
 752           b->count = 0;
 753           b->frequency = 0;
 754           for (e = b->pred; e; e = e->pred_next)
 755             {
 756               b->count += e->count;
 757               b->frequency += EDGE_FREQUENCY (e);
 758             }
 759         }
 760
 761       compute_outgoing_frequencies (b);
 762     }
 763 }