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 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 \f
  33 #include "config.h"
  34 #include "system.h"
  35 #include "coretypes.h"
  36 #include "tm.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
  49 static int count_basic_blocks (rtx);
  50 static void find_basic_blocks_1 (rtx);
  51 static void make_edges (basic_block, basic_block, int);
  52 static void make_label_edge (sbitmap, basic_block, rtx, int);
  53 static void find_bb_boundaries (basic_block);
  54 static void compute_outgoing_frequencies (basic_block);
  55 \f
  56 /* Return true if insn is something that should be contained inside basic
  57    block.  */
  58
  59 bool
  60 inside_basic_block_p (rtx insn)
  61 {
  62   switch (GET_CODE (insn))
  63     {
  64     case CODE_LABEL:
  65       /* Avoid creating of basic block for jumptables.  */
  66       return (NEXT_INSN (insn) == 0
  67               || !JUMP_P (NEXT_INSN (insn))
  68               || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC
  69                   && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC));
  70
  71     case JUMP_INSN:
  72       return (GET_CODE (PATTERN (insn)) != ADDR_VEC
  73               && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
  74
  75     case CALL_INSN:
  76     case INSN:
  77       return true;
  78
  79     case BARRIER:
  80     case NOTE:
  81       return false;
  82
  83     default:
  84       gcc_unreachable ();
  85     }
  86 }
  87
  88 /* Return true if INSN may cause control flow transfer, so it should be last in
  89    the basic block.  */
  90
  91 bool
  92 control_flow_insn_p (rtx insn)
  93 {
  94   rtx note;
  95
  96   switch (GET_CODE (insn))
  97     {
  98     case NOTE:
  99     case CODE_LABEL:
 100       return false;
 101
 102     case JUMP_INSN:
 103       /* Jump insn always causes control transfer except for tablejumps.  */
 104       return (GET_CODE (PATTERN (insn)) != ADDR_VEC
 105               && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
 106
 107     case CALL_INSN:
 108       /* Noreturn and sibling call instructions terminate the basic blocks
 109          (but only if they happen unconditionally).  */
 110       if ((SIBLING_CALL_P (insn)
 111            || find_reg_note (insn, REG_NORETURN, 0))
 112           && GET_CODE (PATTERN (insn)) != COND_EXEC)
 113         return true;
 114       /* Call insn may return to the nonlocal goto handler.  */
 115       return ((nonlocal_goto_handler_labels
 116                && (0 == (note = find_reg_note (insn, REG_EH_REGION,
 117                                                NULL_RTX))
 118                    || INTVAL (XEXP (note, 0)) >= 0))
 119               /* Or may trap.  */
 120               || can_throw_internal (insn));
 121
 122     case INSN:
 123       return (flag_non_call_exceptions && can_throw_internal (insn));
 124
 125     case BARRIER:
 126       /* It is nonsense to reach barrier when looking for the
 127          end of basic block, but before dead code is eliminated
 128          this may happen.  */
 129       return false;
 130
 131     default:
 132       gcc_unreachable ();
 133     }
 134 }
 135
 136 /* Count the basic blocks of the function.  */
 137
 138 static int
 139 count_basic_blocks (rtx f)
 140 {
 141   int count = 0;
 142   bool saw_insn = false;
 143   rtx insn;
 144
 145   for (insn = f; insn; insn = NEXT_INSN (insn))
 146     {
 147       /* Code labels and barriers causes current basic block to be
 148          terminated at previous real insn.  */
 149       if ((LABEL_P (insn) || BARRIER_P (insn))
 150           && saw_insn)
 151         count++, saw_insn = false;
 152
 153       /* Start basic block if needed.  */
 154       if (!saw_insn && inside_basic_block_p (insn))
 155         saw_insn = true;
 156
 157       /* Control flow insn causes current basic block to be terminated.  */
 158       if (saw_insn && control_flow_insn_p (insn))
 159         count++, saw_insn = false;
 160     }
 161
 162   if (saw_insn)
 163     count++;
 164
 165   /* The rest of the compiler works a bit smoother when we don't have to
 166      check for the edge case of do-nothing functions with no basic blocks.  */
 167   if (count == 0)
 168     {
 169       emit_insn (gen_rtx_USE (VOIDmode, const0_rtx));
 170       count = 1;
 171     }
 172
 173   return count;
 174 }
 175 \f
 176 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
 177    about the edge that is accumulated between calls.  */
 178
 179 /* Create an edge from a basic block to a label.  */
 180
 181 static void
 182 make_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags)
 183 {
 184   gcc_assert (LABEL_P (label));
 185
 186   /* If the label was never emitted, this insn is junk, but avoid a
 187      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
 188      as a result of a syntax error and a diagnostic has already been
 189      printed.  */
 190
 191   if (INSN_UID (label) == 0)
 192     return;
 193
 194   cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
 195 }
 196
 197 /* Create the edges generated by INSN in REGION.  */
 198
 199 void
 200 rtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx insn)
 201 {
 202   int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0;
 203   rtx handlers, i;
 204
 205   handlers = reachable_handlers (insn);
 206
 207   for (i = handlers; i; i = XEXP (i, 1))
 208     make_label_edge (edge_cache, src, XEXP (i, 0),
 209                      EDGE_ABNORMAL | EDGE_EH | is_call);
 210
 211   free_INSN_LIST_list (&handlers);
 212 }
 213
 214 /* States of basic block as seen by find_many_sub_basic_blocks.  */
 215 enum state {
 216   /* Basic blocks created via split_block belong to this state.
 217      make_edges will examine these basic blocks to see if we need to
 218      create edges going out of them.  */
 219   BLOCK_NEW = 0,
 220
 221   /* Basic blocks that do not need examining belong to this state.
 222      These blocks will be left intact.  In particular, make_edges will
 223      not create edges going out of these basic blocks.  */
 224   BLOCK_ORIGINAL,
 225
 226   /* Basic blocks that may need splitting (due to a label appearing in
 227      the middle, etc) belong to this state.  After splitting them,
 228      make_edges will create create edges going out of them as
 229      needed.  */
 230   BLOCK_TO_SPLIT
 231 };
 232
 233 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 234 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 235
 236 /* Used internally by purge_dead_tablejump_edges, ORed into state.  */
 237 #define BLOCK_USED_BY_TABLEJUMP         32
 238 #define FULL_STATE(BB) ((size_t) (BB)->aux)
 239
 240 /* Identify the edges going out of basic blocks between MIN and MAX,
 241    inclusive, that have their states set to BLOCK_NEW or
 242    BLOCK_TO_SPLIT.
 243
 244    UPDATE_P should be nonzero if we are updating CFG and zero if we
 245    are building CFG from scratch.  */
 246
 247 static void
 248 make_edges (basic_block min, basic_block max, int update_p)
 249 {
 250   basic_block bb;
 251   sbitmap edge_cache = NULL;
 252
 253   /* Heavy use of computed goto in machine-generated code can lead to
 254      nearly fully-connected CFGs.  In that case we spend a significant
 255      amount of time searching the edge lists for duplicates.  */
 256   if (forced_labels || cfun->max_jumptable_ents > 100)
 257     edge_cache = sbitmap_alloc (last_basic_block);
 258
 259   /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
 260      is always the entry.  */
 261   if (min == ENTRY_BLOCK_PTR->next_bb)
 262     make_edge (ENTRY_BLOCK_PTR, min, EDGE_FALLTHRU);
 263
 264   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 265     {
 266       rtx insn, x;
 267       enum rtx_code code;
 268       edge e;
 269       edge_iterator ei;
 270
 271       if (STATE (bb) == BLOCK_ORIGINAL)
 272         continue;
 273
 274       /* If we have an edge cache, cache edges going out of BB.  */
 275       if (edge_cache)
 276         {
 277           sbitmap_zero (edge_cache);
 278           if (update_p)
 279             {
 280               FOR_EACH_EDGE (e, ei, bb->succs)
 281                 if (e->dest != EXIT_BLOCK_PTR)
 282                   SET_BIT (edge_cache, e->dest->index);
 283             }
 284         }
 285
 286       if (LABEL_P (BB_HEAD (bb))
 287           && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
 288         cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
 289
 290       /* Examine the last instruction of the block, and discover the
 291          ways we can leave the block.  */
 292
 293       insn = BB_END (bb);
 294       code = GET_CODE (insn);
 295
 296       /* A branch.  */
 297       if (code == JUMP_INSN)
 298         {
 299           rtx tmp;
 300
 301           /* Recognize exception handling placeholders.  */
 302           if (GET_CODE (PATTERN (insn)) == RESX)
 303             rtl_make_eh_edge (edge_cache, bb, insn);
 304
 305           /* Recognize a non-local goto as a branch outside the
 306              current function.  */
 307           else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
 308             ;
 309
 310           /* Recognize a tablejump and do the right thing.  */
 311           else if (tablejump_p (insn, NULL, &tmp))
 312             {
 313               rtvec vec;
 314               int j;
 315
 316               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
 317                 vec = XVEC (PATTERN (tmp), 0);
 318               else
 319                 vec = XVEC (PATTERN (tmp), 1);
 320
 321               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
 322                 make_label_edge (edge_cache, bb,
 323                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
 324
 325               /* Some targets (eg, ARM) emit a conditional jump that also
 326                  contains the out-of-range target.  Scan for these and
 327                  add an edge if necessary.  */
 328               if ((tmp = single_set (insn)) != NULL
 329                   && SET_DEST (tmp) == pc_rtx
 330                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
 331                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 332                 make_label_edge (edge_cache, bb,
 333                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
 334             }
 335
 336           /* If this is a computed jump, then mark it as reaching
 337              everything on the forced_labels list.  */
 338           else if (computed_jump_p (insn))
 339             {
 340               for (x = forced_labels; x; x = XEXP (x, 1))
 341                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
 342             }
 343
 344           /* Returns create an exit out.  */
 345           else if (returnjump_p (insn))
 346             cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
 347
 348           /* Otherwise, we have a plain conditional or unconditional jump.  */
 349           else
 350             {
 351               gcc_assert (JUMP_LABEL (insn));
 352               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
 353             }
 354         }
 355
 356       /* If this is a sibling call insn, then this is in effect a combined call
 357          and return, and so we need an edge to the exit block.  No need to
 358          worry about EH edges, since we wouldn't have created the sibling call
 359          in the first place.  */
 360       if (code == CALL_INSN && SIBLING_CALL_P (insn))
 361         cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
 362                           EDGE_SIBCALL | EDGE_ABNORMAL);
 363
 364       /* If this is a CALL_INSN, then mark it as reaching the active EH
 365          handler for this CALL_INSN.  If we're handling non-call
 366          exceptions then any insn can reach any of the active handlers.
 367          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
 368       else if (code == CALL_INSN || flag_non_call_exceptions)
 369         {
 370           /* Add any appropriate EH edges.  */
 371           rtl_make_eh_edge (edge_cache, bb, insn);
 372
 373           if (code == CALL_INSN && nonlocal_goto_handler_labels)
 374             {
 375               /* ??? This could be made smarter: in some cases it's possible
 376                  to tell that certain calls will not do a nonlocal goto.
 377                  For example, if the nested functions that do the nonlocal
 378                  gotos do not have their addresses taken, then only calls to
 379                  those functions or to other nested functions that use them
 380                  could possibly do nonlocal gotos.  */
 381
 382               /* We do know that a REG_EH_REGION note with a value less
 383                  than 0 is guaranteed not to perform a non-local goto.  */
 384               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
 385
 386               if (!note || INTVAL (XEXP (note, 0)) >=  0)
 387                 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
 388                   make_label_edge (edge_cache, bb, XEXP (x, 0),
 389                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
 390             }
 391         }
 392
 393       /* Find out if we can drop through to the next block.  */
 394       insn = NEXT_INSN (insn);
 395       e = find_edge (bb, EXIT_BLOCK_PTR);
 396       if (e && e->flags & EDGE_FALLTHRU)
 397         insn = NULL;
 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)
 405         cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 406       else if (bb->next_bb != EXIT_BLOCK_PTR)
 407         {
 408           if (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.  */
 510
 511 void
 512 find_basic_blocks (rtx f)
 513 {
 514   basic_block bb;
 515
 516   timevar_push (TV_CFG);
 517
 518   /* Flush out existing data.  */
 519   if (basic_block_info != NULL)
 520     {
 521       clear_edges ();
 522
 523       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 524          tag for reuse during create_basic_block, just in case some pass
 525          copies around basic block notes improperly.  */
 526       FOR_EACH_BB (bb)
 527         bb->aux = NULL;
 528
 529       basic_block_info = NULL;
 530     }
 531
 532   n_basic_blocks = count_basic_blocks (f);
 533   last_basic_block = 0;
 534   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 535   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 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   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 546
 547   find_basic_blocks_1 (f);
 548
 549   profile_status = PROFILE_ABSENT;
 550
 551   /* Tell make_edges to examine every block for out-going edges.  */
 552   FOR_EACH_BB (bb)
 553     SET_STATE (bb, BLOCK_NEW);
 554
 555   /* Discover the edges of our cfg.  */
 556   make_edges (ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
 557
 558   /* Do very simple cleanup now, for the benefit of code that runs between
 559      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 560   tidy_fallthru_edges ();
 561
 562 #ifdef ENABLE_CHECKING
 563   verify_flow_info ();
 564 #endif
 565   timevar_pop (TV_CFG);
 566 }
 567 \f
 568 static void
 569 mark_tablejump_edge (rtx label)
 570 {
 571   basic_block bb;
 572
 573   gcc_assert (LABEL_P (label));
 574   /* See comment in make_label_edge.  */
 575   if (INSN_UID (label) == 0)
 576     return;
 577   bb = BLOCK_FOR_INSN (label);
 578   SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
 579 }
 580
 581 static void
 582 purge_dead_tablejump_edges (basic_block bb, rtx table)
 583 {
 584   rtx insn = BB_END (bb), tmp;
 585   rtvec vec;
 586   int j;
 587   edge_iterator ei;
 588   edge e;
 589
 590   if (GET_CODE (PATTERN (table)) == ADDR_VEC)
 591     vec = XVEC (PATTERN (table), 0);
 592   else
 593     vec = XVEC (PATTERN (table), 1);
 594
 595   for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
 596     mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0));
 597
 598   /* Some targets (eg, ARM) emit a conditional jump that also
 599      contains the out-of-range target.  Scan for these and
 600      add an edge if necessary.  */
 601   if ((tmp = single_set (insn)) != NULL
 602        && SET_DEST (tmp) == pc_rtx
 603        && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
 604        && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 605     mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0));
 606
 607   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 608     {
 609       if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
 610         SET_STATE (e->dest, FULL_STATE (e->dest)
 611                             & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
 612       else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 613         {
 614           remove_edge (e);
 615           continue;
 616         }
 617       ei_next (&ei);
 618     }
 619 }
 620
 621 /* Scan basic block BB for possible BB boundaries inside the block
 622    and create new basic blocks in the progress.  */
 623
 624 static void
 625 find_bb_boundaries (basic_block bb)
 626 {
 627   basic_block orig_bb = bb;
 628   rtx insn = BB_HEAD (bb);
 629   rtx end = BB_END (bb);
 630   rtx table;
 631   rtx flow_transfer_insn = NULL_RTX;
 632   edge fallthru = NULL;
 633
 634   if (insn == BB_END (bb))
 635     return;
 636
 637   if (LABEL_P (insn))
 638     insn = NEXT_INSN (insn);
 639
 640   /* Scan insn chain and try to find new basic block boundaries.  */
 641   while (1)
 642     {
 643       enum rtx_code code = GET_CODE (insn);
 644
 645       /* On code label, split current basic block.  */
 646       if (code == CODE_LABEL)
 647         {
 648           fallthru = split_block (bb, PREV_INSN (insn));
 649           if (flow_transfer_insn)
 650             BB_END (bb) = flow_transfer_insn;
 651
 652           bb = fallthru->dest;
 653           remove_edge (fallthru);
 654           flow_transfer_insn = NULL_RTX;
 655           if (LABEL_ALT_ENTRY_P (insn))
 656             make_edge (ENTRY_BLOCK_PTR, bb, 0);
 657         }
 658
 659       /* In case we've previously seen an insn that effects a control
 660          flow transfer, split the block.  */
 661       if (flow_transfer_insn && inside_basic_block_p (insn))
 662         {
 663           fallthru = split_block (bb, PREV_INSN (insn));
 664           BB_END (bb) = flow_transfer_insn;
 665           bb = fallthru->dest;
 666           remove_edge (fallthru);
 667           flow_transfer_insn = NULL_RTX;
 668         }
 669
 670       if (control_flow_insn_p (insn))
 671         flow_transfer_insn = insn;
 672       if (insn == end)
 673         break;
 674       insn = NEXT_INSN (insn);
 675     }
 676
 677   /* In case expander replaced normal insn by sequence terminating by
 678      return and barrier, or possibly other sequence not behaving like
 679      ordinary jump, we need to take care and move basic block boundary.  */
 680   if (flow_transfer_insn)
 681     BB_END (bb) = flow_transfer_insn;
 682
 683   /* We've possibly replaced the conditional jump by conditional jump
 684      followed by cleanup at fallthru edge, so the outgoing edges may
 685      be dead.  */
 686   purge_dead_edges (bb);
 687
 688   /* purge_dead_edges doesn't handle tablejump's, but if we have split the
 689      basic block, we might need to kill some edges.  */
 690   if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
 691     purge_dead_tablejump_edges (bb, table);
 692 }
 693
 694 /*  Assume that frequency of basic block B is known.  Compute frequencies
 695     and probabilities of outgoing edges.  */
 696
 697 static void
 698 compute_outgoing_frequencies (basic_block b)
 699 {
 700   edge e, f;
 701   edge_iterator ei;
 702
 703   if (EDGE_COUNT (b->succs) == 2)
 704     {
 705       rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
 706       int probability;
 707
 708       if (note)
 709         {
 710           probability = INTVAL (XEXP (note, 0));
 711           e = BRANCH_EDGE (b);
 712           e->probability = probability;
 713           e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 714                       / REG_BR_PROB_BASE);
 715           f = FALLTHRU_EDGE (b);
 716           f->probability = REG_BR_PROB_BASE - probability;
 717           f->count = b->count - e->count;
 718           return;
 719         }
 720     }
 721
 722   if (single_succ_p (b))
 723     {
 724       e = single_succ_edge (b);
 725       e->probability = REG_BR_PROB_BASE;
 726       e->count = b->count;
 727       return;
 728     }
 729   guess_outgoing_edge_probabilities (b);
 730   if (b->count)
 731     FOR_EACH_EDGE (e, ei, b->succs)
 732       e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
 733                   / REG_BR_PROB_BASE);
 734 }
 735
 736 /* Assume that some pass has inserted labels or control flow
 737    instructions within a basic block.  Split basic blocks as needed
 738    and create edges.  */
 739
 740 void
 741 find_many_sub_basic_blocks (sbitmap blocks)
 742 {
 743   basic_block bb, min, max;
 744
 745   FOR_EACH_BB (bb)
 746     SET_STATE (bb,
 747                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 748
 749   FOR_EACH_BB (bb)
 750     if (STATE (bb) == BLOCK_TO_SPLIT)
 751       find_bb_boundaries (bb);
 752
 753   FOR_EACH_BB (bb)
 754     if (STATE (bb) != BLOCK_ORIGINAL)
 755       break;
 756
 757   min = max = bb;
 758   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 759     if (STATE (bb) != BLOCK_ORIGINAL)
 760       max = bb;
 761
 762   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 763      jumps at the end of each new basic blocks.  */
 764   make_edges (min, max, 1);
 765
 766   /* Update branch probabilities.  Expect only (un)conditional jumps
 767      to be created with only the forward edges.  */
 768   if (profile_status != PROFILE_ABSENT)
 769     FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 770       {
 771         edge e;
 772         edge_iterator ei;
 773
 774         if (STATE (bb) == BLOCK_ORIGINAL)
 775           continue;
 776         if (STATE (bb) == BLOCK_NEW)
 777           {
 778             bb->count = 0;
 779             bb->frequency = 0;
 780             FOR_EACH_EDGE (e, ei, bb->preds)
 781               {
 782                 bb->count += e->count;
 783                 bb->frequency += EDGE_FREQUENCY (e);
 784               }
 785           }
 786
 787         compute_outgoing_frequencies (bb);
 788       }
 789
 790   FOR_EACH_BB (bb)
 791     SET_STATE (bb, 0);
 792 }