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