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