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