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