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