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