gcc/cfgbuild.c

   1 /* Control flow graph building code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* find_basic_blocks divides the current function's rtl into basic
  23    blocks and constructs the CFG.  The blocks are recorded in the
  24    basic_block_info array; the CFG exists in the edge structures
  25    referenced by the blocks.
  26
  27    find_basic_blocks also finds any unreachable loops and deletes them.
  28
  29    Available functionality:
  30      - CFG construction
  31          find_basic_blocks
  32      - Local CFG construction
  33          find_sub_basic_blocks           */
  34 \f
  35 #include "config.h"
  36 #include "system.h"
  37 #include "coretypes.h"
  38 #include "tm.h"
  39 #include "tree.h"
  40 #include "rtl.h"
  41 #include "hard-reg-set.h"
  42 #include "basic-block.h"
  43 #include "regs.h"
  44 #include "flags.h"
  45 #include "output.h"
  46 #include "function.h"
  47 #include "except.h"
  48 #include "toplev.h"
  49 #include "timevar.h"
  50
  51 static int count_basic_blocks           PARAMS ((rtx));
  52 static void find_basic_blocks_1         PARAMS ((rtx));
  53 static rtx find_label_refs              PARAMS ((rtx, rtx));
  54 static void make_edges                  PARAMS ((rtx, basic_block,
  55                                                  basic_block, int));
  56 static void make_label_edge             PARAMS ((sbitmap *, basic_block,
  57                                                  rtx, int));
  58 static void make_eh_edge                PARAMS ((sbitmap *, basic_block, rtx));
  59 static void find_bb_boundaries          PARAMS ((basic_block));
  60 static void compute_outgoing_frequencies PARAMS ((basic_block));
  61 static bool inside_basic_block_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 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 current 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 || cfun->max_jumptable_ents > 100)
 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_ALT_ENTRY_P (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   /* Discover the edges of our cfg.  */
 651   make_edges (label_value_list, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
 652
 653   /* Do very simple cleanup now, for the benefit of code that runs between
 654      here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns.  */
 655   tidy_fallthru_edges ();
 656
 657 #ifdef ENABLE_CHECKING
 658   verify_flow_info ();
 659 #endif
 660   timevar_pop (TV_CFG);
 661 }
 662 \f
 663 /* State of basic block as seen by find_sub_basic_blocks.  */
 664 enum state {BLOCK_NEW = 0, BLOCK_ORIGINAL, BLOCK_TO_SPLIT};
 665
 666 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 667 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 668
 669 /* Scan basic block BB for possible BB boundaries inside the block
 670    and create new basic blocks in the progress.  */
 671
 672 static void
 673 find_bb_boundaries (bb)
 674      basic_block bb;
 675 {
 676   rtx insn = bb->head;
 677   rtx end = bb->end;
 678   rtx flow_transfer_insn = NULL_RTX;
 679   edge fallthru = NULL;
 680
 681   if (insn == bb->end)
 682     return;
 683
 684   if (GET_CODE (insn) == CODE_LABEL)
 685     insn = NEXT_INSN (insn);
 686
 687   /* Scan insn chain and try to find new basic block boundaries.  */
 688   while (1)
 689     {
 690       enum rtx_code code = GET_CODE (insn);
 691
 692       /* On code label, split current basic block.  */
 693       if (code == CODE_LABEL)
 694         {
 695           fallthru = split_block (bb, PREV_INSN (insn));
 696           if (flow_transfer_insn)
 697             bb->end = flow_transfer_insn;
 698
 699           bb = fallthru->dest;
 700           remove_edge (fallthru);
 701           flow_transfer_insn = NULL_RTX;
 702           if (LABEL_ALT_ENTRY_P (insn))
 703             make_edge (ENTRY_BLOCK_PTR, bb, 0);
 704         }
 705
 706       /* In case we've previously seen an insn that effects a control
 707          flow transfer, split the block.  */
 708       if (flow_transfer_insn && inside_basic_block_p (insn))
 709         {
 710           fallthru = split_block (bb, PREV_INSN (insn));
 711           bb->end = flow_transfer_insn;
 712           bb = fallthru->dest;
 713           remove_edge (fallthru);
 714           flow_transfer_insn = NULL_RTX;
 715         }
 716
 717       if (control_flow_insn_p (insn))
 718         flow_transfer_insn = insn;
 719       if (insn == end)
 720         break;
 721       insn = NEXT_INSN (insn);
 722     }
 723
 724   /* In case expander replaced normal insn by sequence terminating by
 725      return and barrier, or possibly other sequence not behaving like
 726      ordinary jump, we need to take care and move basic block boundary.  */
 727   if (flow_transfer_insn)
 728     bb->end = flow_transfer_insn;
 729
 730   /* We've possibly replaced the conditional jump by conditional jump
 731      followed by cleanup at fallthru edge, so the outgoing edges may
 732      be dead.  */
 733   purge_dead_edges (bb);
 734 }
 735
 736 /*  Assume that frequency of basic block B is known.  Compute frequencies
 737     and probabilities of outgoing edges.  */
 738
 739 static void
 740 compute_outgoing_frequencies (b)
 741      basic_block b;
 742 {
 743   edge e, f;
 744
 745   if (b->succ && b->succ->succ_next && !b->succ->succ_next->succ_next)
 746     {
 747       rtx note = find_reg_note (b->end, REG_BR_PROB, NULL);
 748       int probability;
 749
 750       if (!note)
 751         return;
 752
 753       probability = INTVAL (XEXP (find_reg_note (b->end,
 754                                                  REG_BR_PROB, NULL),
 755                                   0));
 756       e = BRANCH_EDGE (b);
 757       e->probability = probability;
 758       e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 759                   / REG_BR_PROB_BASE);
 760       f = FALLTHRU_EDGE (b);
 761       f->probability = REG_BR_PROB_BASE - probability;
 762       f->count = b->count - e->count;
 763     }
 764
 765   if (b->succ && !b->succ->succ_next)
 766     {
 767       e = b->succ;
 768       e->probability = REG_BR_PROB_BASE;
 769       e->count = b->count;
 770     }
 771 }
 772
 773 /* Assume that someone emitted code with control flow instructions to the
 774    basic block.  Update the data structure.  */
 775
 776 void
 777 find_many_sub_basic_blocks (blocks)
 778      sbitmap blocks;
 779 {
 780   basic_block bb, min, max;
 781
 782   FOR_EACH_BB (bb)
 783     SET_STATE (bb,
 784                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 785
 786   FOR_EACH_BB (bb)
 787     if (STATE (bb) == BLOCK_TO_SPLIT)
 788       find_bb_boundaries (bb);
 789
 790   FOR_EACH_BB (bb)
 791     if (STATE (bb) != BLOCK_ORIGINAL)
 792       break;
 793
 794   min = max = bb;
 795   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 796     if (STATE (bb) != BLOCK_ORIGINAL)
 797       max = bb;
 798
 799   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 800      jumps at the end of each new basic blocks.  */
 801   make_edges (NULL, min, max, 1);
 802
 803   /* Update branch probabilities.  Expect only (un)conditional jumps
 804      to be created with only the forward edges.  */
 805   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 806     {
 807       edge e;
 808
 809       if (STATE (bb) == BLOCK_ORIGINAL)
 810         continue;
 811       if (STATE (bb) == BLOCK_NEW)
 812         {
 813           bb->count = 0;
 814           bb->frequency = 0;
 815           for (e = bb->pred; e; e=e->pred_next)
 816             {
 817               bb->count += e->count;
 818               bb->frequency += EDGE_FREQUENCY (e);
 819             }
 820         }
 821
 822       compute_outgoing_frequencies (bb);
 823     }
 824
 825   FOR_EACH_BB (bb)
 826     SET_STATE (bb, 0);
 827 }
 828
 829 /* Like above but for single basic block only.  */
 830
 831 void
 832 find_sub_basic_blocks (bb)
 833      basic_block bb;
 834 {
 835   basic_block min, max, b;
 836   basic_block next = bb->next_bb;
 837
 838   min = bb;
 839   find_bb_boundaries (bb);
 840   max = next->prev_bb;
 841
 842   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 843      jumps at the end of each new basic blocks.  */
 844   make_edges (NULL, min, max, 1);
 845
 846   /* Update branch probabilities.  Expect only (un)conditional jumps
 847      to be created with only the forward edges.  */
 848   FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
 849     {
 850       edge e;
 851
 852       if (b != min)
 853         {
 854           b->count = 0;
 855           b->frequency = 0;
 856           for (e = b->pred; e; e=e->pred_next)
 857             {
 858               b->count += e->count;
 859               b->frequency += EDGE_FREQUENCY (e);
 860             }
 861         }
 862
 863       compute_outgoing_frequencies (b);
 864     }
 865 }