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       gcc_unreachable ();
  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       gcc_unreachable ();
 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   gcc_assert (LABEL_P (label));
 187
 188   /* If the label was never emitted, this insn is junk, but avoid a
 189      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
 190      as a result of a syntax error and a diagnostic has already been
 191      printed.  */
 192
 193   if (INSN_UID (label) == 0)
 194     return;
 195
 196   cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
 197 }
 198
 199 /* Create the edges generated by INSN in REGION.  */
 200
 201 void
 202 rtl_make_eh_edge (sbitmap *edge_cache, basic_block src, rtx insn)
 203 {
 204   int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0;
 205   rtx handlers, i;
 206
 207   handlers = reachable_handlers (insn);
 208
 209   for (i = handlers; i; i = XEXP (i, 1))
 210     make_label_edge (edge_cache, src, XEXP (i, 0),
 211                      EDGE_ABNORMAL | EDGE_EH | is_call);
 212
 213   free_INSN_LIST_list (&handlers);
 214 }
 215
 216 /* Identify the edges between basic blocks MIN to MAX.
 217
 218    NONLOCAL_LABEL_LIST is a list of non-local labels in the function.  Blocks
 219    that are otherwise unreachable may be reachable with a non-local goto.
 220
 221    BB_EH_END is an array indexed by basic block number in which we record
 222    the list of exception regions active at the end of the basic block.  */
 223
 224 static void
 225 make_edges (basic_block min, basic_block max, int update_p)
 226 {
 227   basic_block bb;
 228   sbitmap *edge_cache = NULL;
 229
 230   /* Assume no computed jump; revise as we create edges.  */
 231   current_function_has_computed_jump = 0;
 232
 233   /* If we are partitioning hot and cold basic blocks into separate
 234      sections, we cannot assume there is no computed jump (partitioning
 235      sometimes requires the use of indirect jumps; see comments about
 236      partitioning at the top of bb-reorder.c:partition_hot_cold_basic_blocks
 237      for complete details).  */
 238
 239   if (flag_reorder_blocks_and_partition)
 240     current_function_has_computed_jump = 1;
 241
 242   /* Heavy use of computed goto in machine-generated code can lead to
 243      nearly fully-connected CFGs.  In that case we spend a significant
 244      amount of time searching the edge lists for duplicates.  */
 245   if (forced_labels || cfun->max_jumptable_ents > 100)
 246     {
 247       edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 248       sbitmap_vector_zero (edge_cache, last_basic_block);
 249
 250       if (update_p)
 251         FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 252           {
 253             edge e;
 254             edge_iterator ei;
 255
 256             FOR_EACH_EDGE (e, ei, bb->succs)
 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       edge_iterator ei;
 275
 276       if (LABEL_P (BB_HEAD (bb))
 277           && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
 278         cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
 279
 280       /* Examine the last instruction of the block, and discover the
 281          ways we can leave the block.  */
 282
 283       insn = BB_END (bb);
 284       code = GET_CODE (insn);
 285
 286       /* A branch.  */
 287       if (code == JUMP_INSN)
 288         {
 289           rtx tmp;
 290
 291           /* Recognize exception handling placeholders.  */
 292           if (GET_CODE (PATTERN (insn)) == RESX)
 293             rtl_make_eh_edge (edge_cache, bb, insn);
 294
 295           /* Recognize a non-local goto as a branch outside the
 296              current function.  */
 297           else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
 298             ;
 299
 300           /* Recognize a tablejump and do the right thing.  */
 301           else if (tablejump_p (insn, NULL, &tmp))
 302             {
 303               rtvec vec;
 304               int j;
 305
 306               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
 307                 vec = XVEC (PATTERN (tmp), 0);
 308               else
 309                 vec = XVEC (PATTERN (tmp), 1);
 310
 311               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
 312                 make_label_edge (edge_cache, bb,
 313                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
 314
 315               /* Some targets (eg, ARM) emit a conditional jump that also
 316                  contains the out-of-range target.  Scan for these and
 317                  add an edge if necessary.  */
 318               if ((tmp = single_set (insn)) != NULL
 319                   && SET_DEST (tmp) == pc_rtx
 320                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
 321                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 322                 make_label_edge (edge_cache, bb,
 323                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
 324
 325 #ifdef CASE_DROPS_THROUGH
 326               /* Silly VAXen.  The ADDR_VEC is going to be in the way of
 327                  us naturally detecting fallthru into the next block.  */
 328               force_fallthru = 1;
 329 #endif
 330             }
 331
 332           /* If this is a computed jump, then mark it as reaching
 333              everything on the forced_labels list.  */
 334           else if (computed_jump_p (insn))
 335             {
 336               current_function_has_computed_jump = 1;
 337
 338               for (x = forced_labels; x; x = XEXP (x, 1))
 339                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
 340             }
 341
 342           /* Returns create an exit out.  */
 343           else if (returnjump_p (insn))
 344             cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
 345
 346           /* Otherwise, we have a plain conditional or unconditional jump.  */
 347           else
 348             {
 349               gcc_assert (JUMP_LABEL (insn));
 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_EACH_EDGE (e, ei, bb->succs)
 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           gcc_unreachable ();
 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   gcc_assert (last_basic_block == n_basic_blocks);
 503
 504   clear_aux_for_blocks ();
 505 }
 506
 507
 508 /* Find basic blocks of the current function.
 509    F is the first insn of the function and NREGS the number of register
 510    numbers in use.  */
 511
 512 void
 513 find_basic_blocks (rtx f, int nregs ATTRIBUTE_UNUSED,
 514                    FILE *file ATTRIBUTE_UNUSED)
 515 {
 516   basic_block bb;
 517
 518   timevar_push (TV_CFG);
 519
 520   /* Flush out existing data.  */
 521   if (basic_block_info != NULL)
 522     {
 523       clear_edges ();
 524
 525       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 526          tag for reuse during create_basic_block, just in case some pass
 527          copies around basic block notes improperly.  */
 528       FOR_EACH_BB (bb)
 529         bb->aux = NULL;
 530
 531       basic_block_info = NULL;
 532     }
 533
 534   n_basic_blocks = count_basic_blocks (f);
 535   last_basic_block = 0;
 536   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 537   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 538
 539   /* Size the basic block table.  The actual structures will be allocated
 540      by find_basic_blocks_1, since we want to keep the structure pointers
 541      stable across calls to find_basic_blocks.  */
 542   /* ??? This whole issue would be much simpler if we called find_basic_blocks
 543      exactly once, and thereafter we don't have a single long chain of
 544      instructions at all until close to the end of compilation when we
 545      actually lay them out.  */
 546
 547   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 548
 549   find_basic_blocks_1 (f);
 550
 551   profile_status = PROFILE_ABSENT;
 552
 553   /* Discover the edges of our cfg.  */
 554   make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
 555
 556   /* Do very simple cleanup now, for the benefit of code that runs between
 557      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 558   tidy_fallthru_edges ();
 559
 560 #ifdef ENABLE_CHECKING
 561   verify_flow_info ();
 562 #endif
 563   timevar_pop (TV_CFG);
 564 }
 565 \f
 566 /* State of basic block as seen by find_sub_basic_blocks.  */
 567 enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
 568
 569 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 570 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 571
 572 /* Scan basic block BB for possible BB boundaries inside the block
 573    and create new basic blocks in the progress.  */
 574
 575 static void
 576 find_bb_boundaries (basic_block bb)
 577 {
 578   rtx insn = BB_HEAD (bb);
 579   rtx end = BB_END (bb);
 580   rtx flow_transfer_insn = NULL_RTX;
 581   edge fallthru = NULL;
 582
 583   if (insn == BB_END (bb))
 584     return;
 585
 586   if (LABEL_P (insn))
 587     insn = NEXT_INSN (insn);
 588
 589   /* Scan insn chain and try to find new basic block boundaries.  */
 590   while (1)
 591     {
 592       enum rtx_code code = GET_CODE (insn);
 593
 594       /* On code label, split current basic block.  */
 595       if (code == CODE_LABEL)
 596         {
 597           fallthru = split_block (bb, PREV_INSN (insn));
 598           if (flow_transfer_insn)
 599             BB_END (bb) = flow_transfer_insn;
 600
 601           bb = fallthru->dest;
 602           remove_edge (fallthru);
 603           flow_transfer_insn = NULL_RTX;
 604           if (LABEL_ALT_ENTRY_P (insn))
 605             make_edge (ENTRY_BLOCK_PTR, bb, 0);
 606         }
 607
 608       /* In case we've previously seen an insn that effects a control
 609          flow transfer, split the block.  */
 610       if (flow_transfer_insn && inside_basic_block_p (insn))
 611         {
 612           fallthru = split_block (bb, PREV_INSN (insn));
 613           BB_END (bb) = flow_transfer_insn;
 614           bb = fallthru->dest;
 615           remove_edge (fallthru);
 616           flow_transfer_insn = NULL_RTX;
 617         }
 618
 619       if (control_flow_insn_p (insn))
 620         flow_transfer_insn = insn;
 621       if (insn == end)
 622         break;
 623       insn = NEXT_INSN (insn);
 624     }
 625
 626   /* In case expander replaced normal insn by sequence terminating by
 627      return and barrier, or possibly other sequence not behaving like
 628      ordinary jump, we need to take care and move basic block boundary.  */
 629   if (flow_transfer_insn)
 630     BB_END (bb) = flow_transfer_insn;
 631
 632   /* We've possibly replaced the conditional jump by conditional jump
 633      followed by cleanup at fallthru edge, so the outgoing edges may
 634      be dead.  */
 635   purge_dead_edges (bb);
 636 }
 637
 638 /*  Assume that frequency of basic block B is known.  Compute frequencies
 639     and probabilities of outgoing edges.  */
 640
 641 static void
 642 compute_outgoing_frequencies (basic_block b)
 643 {
 644   edge e, f;
 645   edge_iterator ei;
 646
 647   if (EDGE_COUNT (b->succs) == 2)
 648     {
 649       rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
 650       int probability;
 651
 652       if (note)
 653         {
 654           probability = INTVAL (XEXP (note, 0));
 655           e = BRANCH_EDGE (b);
 656           e->probability = probability;
 657           e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 658                       / REG_BR_PROB_BASE);
 659           f = FALLTHRU_EDGE (b);
 660           f->probability = REG_BR_PROB_BASE - probability;
 661           f->count = b->count - e->count;
 662           return;
 663         }
 664     }
 665
 666   if (EDGE_COUNT (b->succs) == 1)
 667     {
 668       e = EDGE_SUCC (b, 0);
 669       e->probability = REG_BR_PROB_BASE;
 670       e->count = b->count;
 671       return;
 672     }
 673   guess_outgoing_edge_probabilities (b);
 674   if (b->count)
 675     FOR_EACH_EDGE (e, ei, b->succs)
 676       e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
 677                   / REG_BR_PROB_BASE);
 678 }
 679
 680 /* Assume that someone emitted code with control flow instructions to the
 681    basic block.  Update the data structure.  */
 682
 683 void
 684 find_many_sub_basic_blocks (sbitmap blocks)
 685 {
 686   basic_block bb, min, max;
 687
 688   FOR_EACH_BB (bb)
 689     SET_STATE (bb,
 690                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 691
 692   FOR_EACH_BB (bb)
 693     if (STATE (bb) == BLOCK_TO_SPLIT)
 694       find_bb_boundaries (bb);
 695
 696   FOR_EACH_BB (bb)
 697     if (STATE (bb) != BLOCK_ORIGINAL)
 698       break;
 699
 700   min = max = bb;
 701   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 702     if (STATE (bb) != BLOCK_ORIGINAL)
 703       max = bb;
 704
 705   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 706      jumps at the end of each new basic blocks.  */
 707   make_edges (min, max, 1);
 708
 709   /* Update branch probabilities.  Expect only (un)conditional jumps
 710      to be created with only the forward edges.  */
 711   if (profile_status != PROFILE_ABSENT)
 712     FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 713       {
 714         edge e;
 715         edge_iterator ei;
 716
 717         if (STATE (bb) == BLOCK_ORIGINAL)
 718           continue;
 719         if (STATE (bb) == BLOCK_NEW)
 720           {
 721             bb->count = 0;
 722             bb->frequency = 0;
 723             FOR_EACH_EDGE (e, ei, bb->preds)
 724               {
 725                 bb->count += e->count;
 726                 bb->frequency += EDGE_FREQUENCY (e);
 727               }
 728           }
 729
 730         compute_outgoing_frequencies (bb);
 731       }
 732
 733   FOR_EACH_BB (bb)
 734     SET_STATE (bb, 0);
 735 }
 736
 737 /* Like above but for single basic block only.  */
 738
 739 void
 740 find_sub_basic_blocks (basic_block bb)
 741 {
 742   basic_block min, max, b;
 743   basic_block next = bb->next_bb;
 744
 745   min = bb;
 746   find_bb_boundaries (bb);
 747   max = next->prev_bb;
 748
 749   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 750      jumps at the end of each new basic blocks.  */
 751   make_edges (min, max, 1);
 752
 753   /* Update branch probabilities.  Expect only (un)conditional jumps
 754      to be created with only the forward edges.  */
 755   FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
 756     {
 757       edge e;
 758       edge_iterator ei;
 759
 760       if (b != min)
 761         {
 762           b->count = 0;
 763           b->frequency = 0;
 764           FOR_EACH_EDGE (e, ei, b->preds)
 765             {
 766               b->count += e->count;
 767               b->frequency += EDGE_FREQUENCY (e);
 768             }
 769         }
 770
 771       compute_outgoing_frequencies (b);
 772     }
 773 }