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 (last_basic_block++, 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 (last_basic_block++, 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 (last_basic_block++, 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   int max_uid;
 616   basic_block bb;
 617
 618   timevar_push (TV_CFG);
 619
 620   /* Flush out existing data.  */
 621   if (basic_block_info != NULL)
 622     {
 623       clear_edges ();
 624
 625       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 626          tag for reuse during create_basic_block, just in case some pass
 627          copies around basic block notes improperly.  */
 628       FOR_EACH_BB (bb)
 629         bb->aux = NULL;
 630
 631       VARRAY_FREE (basic_block_info);
 632     }
 633
 634   n_basic_blocks = count_basic_blocks (f);
 635   last_basic_block = 0;
 636   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 637   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 638
 639   /* Size the basic block table.  The actual structures will be allocated
 640      by find_basic_blocks_1, since we want to keep the structure pointers
 641      stable across calls to find_basic_blocks.  */
 642   /* ??? This whole issue would be much simpler if we called find_basic_blocks
 643      exactly once, and thereafter we don't have a single long chain of
 644      instructions at all until close to the end of compilation when we
 645      actually lay them out.  */
 646
 647   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 648
 649   find_basic_blocks_1 (f);
 650
 651   /* Record the block to which an insn belongs.  */
 652   /* ??? This should be done another way, by which (perhaps) a label is
 653      tagged directly with the basic block that it starts.  It is used for
 654      more than that currently, but IMO that is the only valid use.  */
 655
 656   max_uid = get_max_uid ();
 657 #ifdef AUTO_INC_DEC
 658   /* Leave space for insns life_analysis makes in some cases for auto-inc.
 659      These cases are rare, so we don't need too much space.  */
 660   max_uid += max_uid / 10;
 661 #endif
 662
 663   compute_bb_for_insn (max_uid);
 664
 665   /* Discover the edges of our cfg.  */
 666   make_edges (label_value_list, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
 667
 668   /* Do very simple cleanup now, for the benefit of code that runs between
 669      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 670   tidy_fallthru_edges ();
 671
 672 #ifdef ENABLE_CHECKING
 673   verify_flow_info ();
 674 #endif
 675   timevar_pop (TV_CFG);
 676 }
 677 \f
 678 /* State of basic block as seen by find_sub_basic_blocks.  */
 679 enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
 680
 681 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 682 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 683
 684 /* Scan basic block BB for possible BB boundaries inside the block
 685    and create new basic blocks in the progress.  */
 686
 687 static void
 688 find_bb_boundaries (bb)
 689      basic_block bb;
 690 {
 691   rtx insn = bb->head;
 692   rtx end = bb->end;
 693   rtx flow_transfer_insn = NULL_RTX;
 694   edge fallthru = NULL;
 695
 696   if (insn == bb->end)
 697     return;
 698
 699   if (GET_CODE (insn) == CODE_LABEL)
 700     insn = NEXT_INSN (insn);
 701
 702   /* Scan insn chain and try to find new basic block boundaries.  */
 703   while (1)
 704     {
 705       enum rtx_code code = GET_CODE (insn);
 706
 707       /* On code label, split current basic block.  */
 708       if (code == CODE_LABEL)
 709         {
 710           fallthru = split_block (bb, PREV_INSN (insn));
 711           if (flow_transfer_insn)
 712             bb->end = flow_transfer_insn;
 713
 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         }
 720
 721       /* In case we've previously seen an insn that effects a control
 722          flow transfer, split the block.  */
 723       if (flow_transfer_insn && inside_basic_block_p (insn))
 724         {
 725           fallthru = split_block (bb, PREV_INSN (insn));
 726           bb->end = flow_transfer_insn;
 727           bb = fallthru->dest;
 728           remove_edge (fallthru);
 729           flow_transfer_insn = NULL_RTX;
 730         }
 731
 732       if (control_flow_insn_p (insn))
 733         flow_transfer_insn = insn;
 734       if (insn == end)
 735         break;
 736       insn = NEXT_INSN (insn);
 737     }
 738
 739   /* In case expander replaced normal insn by sequence terminating by
 740      return and barrier, or possibly other sequence not behaving like
 741      ordinary jump, we need to take care and move basic block boundary.  */
 742   if (flow_transfer_insn)
 743     bb->end = flow_transfer_insn;
 744
 745   /* We've possibly replaced the conditional jump by conditional jump
 746      followed by cleanup at fallthru edge, so the outgoing edges may
 747      be dead.  */
 748   purge_dead_edges (bb);
 749 }
 750
 751 /*  Assume that frequency of basic block B is known.  Compute frequencies
 752     and probabilities of outgoing edges.  */
 753
 754 static void
 755 compute_outgoing_frequencies (b)
 756      basic_block b;
 757 {
 758   edge e, f;
 759
 760   if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
 761     {
 762       rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
 763       int probability;
 764
 765       if (!note)
 766         return;
 767
 768       probability = INTVAL (XEXP (find_reg_note (b->end,
 769                                                  REG_BR_PROB, NULL),
 770                                   0));
 771       e = BRANCH_EDGE (b);
 772       e->probability = probability;
 773       e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 774                   / REG_BR_PROB_BASE);
 775       f = FALLTHRU_EDGE (b);
 776       f->probability = REG_BR_PROB_BASE - probability;
 777       f->count = b->count - e->count;
 778     }
 779
 780   if (b->succ && !b->succ->succ_next)
 781     {
 782       e = b->succ;
 783       e->probability = REG_BR_PROB_BASE;
 784       e->count = b->count;
 785     }
 786 }
 787
 788 /* Assume that someone emitted code with control flow instructions to the
 789    basic block.  Update the data structure.  */
 790
 791 void
 792 find_many_sub_basic_blocks (blocks)
 793      sbitmap blocks;
 794 {
 795   basic_block bb, min, max;
 796
 797   FOR_EACH_BB (bb)
 798     SET_STATE (bb,
 799                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 800
 801   FOR_EACH_BB (bb)
 802     if (STATE (bb) == BLOCK_TO_SPLIT)
 803       find_bb_boundaries (bb);
 804
 805   FOR_EACH_BB (bb)
 806     if (STATE (bb) != BLOCK_ORIGINAL)
 807       break;
 808
 809   min = max = bb;
 810   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 811     if (STATE (bb) != BLOCK_ORIGINAL)
 812       max = bb;
 813
 814   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 815      jumps at the end of each new basic blocks.  */
 816   make_edges (NULL, min, max, 1);
 817
 818   /* Update branch probabilities.  Expect only (un)conditional jumps
 819      to be created with only the forward edges.  */
 820   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 821     {
 822       edge e;
 823
 824       if (STATE (bb) == BLOCK_ORIGINAL)
 825         continue;
 826       if (STATE (bb) == BLOCK_NEW)
 827         {
 828           bb->count = 0;
 829           bb->frequency = 0;
 830           for (e = bb->pred; e; e=e->pred_next)
 831             {
 832               bb->count += e->count;
 833               bb->frequency += EDGE_FREQUENCY (e);
 834             }
 835         }
 836
 837       compute_outgoing_frequencies (bb);
 838     }
 839
 840   FOR_EACH_BB (bb)
 841     SET_STATE (bb, 0);
 842 }
 843
 844 /* Like above but for single basic block only.  */
 845
 846 void
 847 find_sub_basic_blocks (bb)
 848      basic_block bb;
 849 {
 850   basic_block min, max, b;
 851   basic_block next = bb->next_bb;
 852
 853   min = bb;
 854   find_bb_boundaries (bb);
 855   max = next->prev_bb;
 856
 857   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 858      jumps at the end of each new basic blocks.  */
 859   make_edges (NULL, min, max, 1);
 860
 861   /* Update branch probabilities.  Expect only (un)conditional jumps
 862      to be created with only the forward edges.  */
 863   FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
 864     {
 865       edge e;
 866
 867       if (b != min)
 868         {
 869           b->count = 0;
 870           b->frequency = 0;
 871           for (e = b->pred; e; e=e->pred_next)
 872             {
 873               b->count += e->count;
 874               b->frequency += EDGE_FREQUENCY (e);
 875             }
 876         }
 877
 878       compute_outgoing_frequencies (b);
 879     }
 880 }