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 (n_basic_blocks, n_basic_blocks);
 299       sbitmap_vector_zero (edge_cache, n_basic_blocks);
 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   int i = 0;
 475   rtx bb_note = NULL_RTX;
 476   rtx lvl = NULL_RTX;
 477   rtx trll = NULL_RTX;
 478   rtx head = NULL_RTX;
 479   rtx end = NULL_RTX;
 480   basic_block prev = ENTRY_BLOCK_PTR;
 481
 482   /* We process the instructions in a slightly different way than we did
 483      previously.  This is so that we see a NOTE_BASIC_BLOCK after we have
 484      closed out the previous block, so that it gets attached at the proper
 485      place.  Since this form should be equivalent to the previous,
 486      count_basic_blocks continues to use the old form as a check.  */
 487
 488   for (insn = f; insn; insn = next)
 489     {
 490       enum rtx_code code = GET_CODE (insn);
 491
 492       next = NEXT_INSN (insn);
 493
 494       if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
 495           && head)
 496         {
 497           prev = create_basic_block_structure (i++, head, end, bb_note, prev);
 498           head = end = NULL_RTX;
 499           bb_note = NULL_RTX;
 500         }
 501
 502       if (inside_basic_block_p (insn))
 503         {
 504           if (head == NULL_RTX)
 505             head = insn;
 506           end = insn;
 507         }
 508
 509       if (head && control_flow_insn_p (insn))
 510         {
 511           prev = create_basic_block_structure (i++, head, end, bb_note, prev);
 512           head = end = NULL_RTX;
 513           bb_note = NULL_RTX;
 514         }
 515
 516       switch (code)
 517         {
 518         case NOTE:
 519           {
 520             int kind = NOTE_LINE_NUMBER (insn);
 521
 522             /* Look for basic block notes with which to keep the
 523                basic_block_info pointers stable.  Unthread the note now;
 524                we'll put it back at the right place in create_basic_block.
 525                Or not at all if we've already found a note in this block.  */
 526             if (kind == NOTE_INSN_BASIC_BLOCK)
 527               {
 528                 if (bb_note == NULL_RTX)
 529                   bb_note = insn;
 530                 else
 531                   next = delete_insn (insn);
 532               }
 533             break;
 534           }
 535
 536         case CODE_LABEL:
 537         case JUMP_INSN:
 538         case INSN:
 539         case BARRIER:
 540           break;
 541
 542         case CALL_INSN:
 543           if (GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
 544             {
 545               /* Scan each of the alternatives for label refs.  */
 546               lvl = find_label_refs (XEXP (PATTERN (insn), 0), lvl);
 547               lvl = find_label_refs (XEXP (PATTERN (insn), 1), lvl);
 548               lvl = find_label_refs (XEXP (PATTERN (insn), 2), lvl);
 549               /* Record its tail recursion label, if any.  */
 550               if (XEXP (PATTERN (insn), 3) != NULL_RTX)
 551                 trll = alloc_EXPR_LIST (0, XEXP (PATTERN (insn), 3), trll);
 552             }
 553           break;
 554
 555         default:
 556           abort ();
 557         }
 558
 559       if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
 560         {
 561           rtx note;
 562
 563           /* Make a list of all labels referred to other than by jumps.
 564
 565              Make a special exception for labels followed by an ADDR*VEC,
 566              as this would be a part of the tablejump setup code.
 567
 568              Make a special exception to registers loaded with label
 569              values just before jump insns that use them.  */
 570
 571           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
 572             if (REG_NOTE_KIND (note) == REG_LABEL)
 573               {
 574                 rtx lab = XEXP (note, 0), next;
 575
 576                 if ((next = next_nonnote_insn (lab)) != NULL
 577                          && GET_CODE (next) == JUMP_INSN
 578                          && (GET_CODE (PATTERN (next)) == ADDR_VEC
 579                              || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
 580                   ;
 581                 else if (GET_CODE (lab) == NOTE)
 582                   ;
 583                 else if (GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
 584                          && find_reg_note (NEXT_INSN (insn), REG_LABEL, lab))
 585                   ;
 586                 else
 587                   lvl = alloc_EXPR_LIST (0, XEXP (note, 0), lvl);
 588               }
 589         }
 590     }
 591
 592   if (head != NULL_RTX)
 593     create_basic_block_structure (i++, head, end, bb_note, prev);
 594   else if (bb_note)
 595     delete_insn (bb_note);
 596
 597   if (i != n_basic_blocks)
 598     abort ();
 599
 600   label_value_list = lvl;
 601   tail_recursion_label_list = trll;
 602   clear_aux_for_blocks ();
 603 }
 604
 605
 606 /* Find basic blocks of the current function.
 607    F is the first insn of the function and NREGS the number of register
 608    numbers in use.  */
 609
 610 void
 611 find_basic_blocks (f, nregs, file)
 612      rtx f;
 613      int nregs ATTRIBUTE_UNUSED;
 614      FILE *file ATTRIBUTE_UNUSED;
 615 {
 616   int max_uid;
 617   basic_block bb;
 618
 619   timevar_push (TV_CFG);
 620
 621   basic_block_for_insn = 0;
 622
 623   /* Flush out existing data.  */
 624   if (basic_block_info != NULL)
 625     {
 626       clear_edges ();
 627
 628       /* Clear bb->aux on all extant basic blocks.  We'll use this as a
 629          tag for reuse during create_basic_block, just in case some pass
 630          copies around basic block notes improperly.  */
 631       FOR_EACH_BB (bb)
 632         bb->aux = NULL;
 633
 634       VARRAY_FREE (basic_block_info);
 635     }
 636
 637   n_basic_blocks = count_basic_blocks (f);
 638   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 639   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 640
 641   /* Size the basic block table.  The actual structures will be allocated
 642      by find_basic_blocks_1, since we want to keep the structure pointers
 643      stable across calls to find_basic_blocks.  */
 644   /* ??? This whole issue would be much simpler if we called find_basic_blocks
 645      exactly once, and thereafter we don't have a single long chain of
 646      instructions at all until close to the end of compilation when we
 647      actually lay them out.  */
 648
 649   VARRAY_BB_INIT (basic_block_info, n_basic_blocks, "basic_block_info");
 650
 651   find_basic_blocks_1 (f);
 652
 653   /* Record the block to which an insn belongs.  */
 654   /* ??? This should be done another way, by which (perhaps) a label is
 655      tagged directly with the basic block that it starts.  It is used for
 656      more than that currently, but IMO that is the only valid use.  */
 657
 658   max_uid = get_max_uid ();
 659 #ifdef AUTO_INC_DEC
 660   /* Leave space for insns life_analysis makes in some cases for auto-inc.
 661      These cases are rare, so we don't need too much space.  */
 662   max_uid += max_uid / 10;
 663 #endif
 664
 665   compute_bb_for_insn (max_uid);
 666
 667   /* Discover the edges of our cfg.  */
 668   make_edges (label_value_list, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
 669
 670   /* Do very simple cleanup now, for the benefit of code that runs between
 671      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 672   tidy_fallthru_edges ();
 673
 674 #ifdef ENABLE_CHECKING
 675   verify_flow_info ();
 676 #endif
 677   timevar_pop (TV_CFG);
 678 }
 679 \f
 680 /* State of basic block as seen by find_sub_basic_blocks.  */
 681 enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
 682
 683 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 684 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 685
 686 /* Scan basic block BB for possible BB boundaries inside the block
 687    and create new basic blocks in the progress.  */
 688
 689 static void
 690 find_bb_boundaries (bb)
 691      basic_block bb;
 692 {
 693   rtx insn = bb->head;
 694   rtx end = bb->end;
 695   rtx flow_transfer_insn = NULL_RTX;
 696   edge fallthru = NULL;
 697
 698   if (insn == bb->end)
 699     return;
 700
 701   if (GET_CODE (insn) == CODE_LABEL)
 702     insn = NEXT_INSN (insn);
 703
 704   /* Scan insn chain and try to find new basic block boundaries.  */
 705   while (1)
 706     {
 707       enum rtx_code code = GET_CODE (insn);
 708
 709       /* On code label, split current basic block.  */
 710       if (code == CODE_LABEL)
 711         {
 712           fallthru = split_block (bb, PREV_INSN (insn));
 713           if (flow_transfer_insn)
 714             bb->end = flow_transfer_insn;
 715
 716           bb = fallthru->dest;
 717           remove_edge (fallthru);
 718           flow_transfer_insn = NULL_RTX;
 719           if (LABEL_ALTERNATE_NAME (insn))
 720             make_edge (ENTRY_BLOCK_PTR, bb, 0);
 721         }
 722
 723       /* In case we've previously seen an insn that effects a control
 724          flow transfer, split the block.  */
 725       if (flow_transfer_insn && inside_basic_block_p (insn))
 726         {
 727           fallthru = split_block (bb, PREV_INSN (insn));
 728           bb->end = flow_transfer_insn;
 729           bb = fallthru->dest;
 730           remove_edge (fallthru);
 731           flow_transfer_insn = NULL_RTX;
 732         }
 733
 734       if (control_flow_insn_p (insn))
 735         flow_transfer_insn = insn;
 736       if (insn == end)
 737         break;
 738       insn = NEXT_INSN (insn);
 739     }
 740
 741   /* In case expander replaced normal insn by sequence terminating by
 742      return and barrier, or possibly other sequence not behaving like
 743      ordinary jump, we need to take care and move basic block boundary.  */
 744   if (flow_transfer_insn)
 745     bb->end = flow_transfer_insn;
 746
 747   /* We've possibly replaced the conditional jump by conditional jump
 748      followed by cleanup at fallthru edge, so the outgoing edges may
 749      be dead.  */
 750   purge_dead_edges (bb);
 751 }
 752
 753 /*  Assume that frequency of basic block B is known.  Compute frequencies
 754     and probabilities of outgoing edges.  */
 755
 756 static void
 757 compute_outgoing_frequencies (b)
 758      basic_block b;
 759 {
 760   edge e, f;
 761
 762   if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
 763     {
 764       rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
 765       int probability;
 766
 767       if (!note)
 768         return;
 769
 770       probability = INTVAL (XEXP (find_reg_note (b->end,
 771                                                  REG_BR_PROB, NULL),
 772                                   0));
 773       e = BRANCH_EDGE (b);
 774       e->probability = probability;
 775       e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 776                   / REG_BR_PROB_BASE);
 777       f = FALLTHRU_EDGE (b);
 778       f->probability = REG_BR_PROB_BASE - probability;
 779       f->count = b->count - e->count;
 780     }
 781
 782   if (b->succ && !b->succ->succ_next)
 783     {
 784       e = b->succ;
 785       e->probability = REG_BR_PROB_BASE;
 786       e->count = b->count;
 787     }
 788 }
 789
 790 /* Assume that someone emitted code with control flow instructions to the
 791    basic block.  Update the data structure.  */
 792
 793 void
 794 find_many_sub_basic_blocks (blocks)
 795      sbitmap blocks;
 796 {
 797   basic_block bb, min, max;
 798
 799   FOR_EACH_BB (bb)
 800     SET_STATE (bb,
 801                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 802
 803   FOR_EACH_BB (bb)
 804     if (STATE (bb) == BLOCK_TO_SPLIT)
 805       find_bb_boundaries (bb);
 806
 807   FOR_EACH_BB (bb)
 808     if (STATE (bb) != BLOCK_ORIGINAL)
 809       break;
 810
 811   min = max = bb;
 812   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 813     if (STATE (bb) != BLOCK_ORIGINAL)
 814       max = bb;
 815
 816   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 817      jumps at the end of each new basic blocks.  */
 818   make_edges (NULL, min, max, 1);
 819
 820   /* Update branch probabilities.  Expect only (un)conditional jumps
 821      to be created with only the forward edges.  */
 822   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 823     {
 824       edge e;
 825
 826       if (STATE (bb) == BLOCK_ORIGINAL)
 827         continue;
 828       if (STATE (bb) == BLOCK_NEW)
 829         {
 830           bb->count = 0;
 831           bb->frequency = 0;
 832           for (e = bb->pred; e; e=e->pred_next)
 833             {
 834               bb->count += e->count;
 835               bb->frequency += EDGE_FREQUENCY (e);
 836             }
 837         }
 838
 839       compute_outgoing_frequencies (bb);
 840     }
 841
 842   FOR_EACH_BB (bb)
 843     SET_STATE (bb, 0);
 844 }
 845
 846 /* Like above but for single basic block only.  */
 847
 848 void
 849 find_sub_basic_blocks (bb)
 850      basic_block bb;
 851 {
 852   basic_block min, max, b;
 853   basic_block next = bb->next_bb;
 854
 855   min = bb;
 856   find_bb_boundaries (bb);
 857   max = next->prev_bb;
 858
 859   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 860      jumps at the end of each new basic blocks.  */
 861   make_edges (NULL, min, max, 1);
 862
 863   /* Update branch probabilities.  Expect only (un)conditional jumps
 864      to be created with only the forward edges.  */
 865   FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
 866     {
 867       edge e;
 868
 869       if (b != min)
 870         {
 871           b->count = 0;
 872           b->frequency = 0;
 873           for (e = b->pred; e; e=e->pred_next)
 874             {
 875               b->count += e->count;
 876               b->frequency += EDGE_FREQUENCY (e);
 877             }
 878         }
 879
 880       compute_outgoing_frequencies (b);
 881     }
 882 }