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, 2004, 2005, 2007, 2008
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 \f
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "regs.h"
  32 #include "flags.h"
  33 #include "output.h"
  34 #include "function.h"
  35 #include "except.h"
  36 #include "toplev.h"
  37 #include "timevar.h"
  38
  39 static void make_edges (basic_block, basic_block, int);
  40 static void make_label_edge (sbitmap, basic_block, rtx, int);
  41 static void find_bb_boundaries (basic_block);
  42 static void compute_outgoing_frequencies (basic_block);
  43 \f
  44 /* Return true if insn is something that should be contained inside basic
  45    block.  */
  46
  47 bool
  48 inside_basic_block_p (const_rtx insn)
  49 {
  50   switch (GET_CODE (insn))
  51     {
  52     case CODE_LABEL:
  53       /* Avoid creating of basic block for jumptables.  */
  54       return (NEXT_INSN (insn) == 0
  55               || !JUMP_P (NEXT_INSN (insn))
  56               || (GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_VEC
  57                   && GET_CODE (PATTERN (NEXT_INSN (insn))) != ADDR_DIFF_VEC));
  58
  59     case JUMP_INSN:
  60       return (GET_CODE (PATTERN (insn)) != ADDR_VEC
  61               && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
  62
  63     case CALL_INSN:
  64     case INSN:
  65       return true;
  66
  67     case BARRIER:
  68     case NOTE:
  69       return false;
  70
  71     default:
  72       gcc_unreachable ();
  73     }
  74 }
  75
  76 /* Return true if INSN may cause control flow transfer, so it should be last in
  77    the basic block.  */
  78
  79 bool
  80 control_flow_insn_p (const_rtx insn)
  81 {
  82   rtx note;
  83
  84   switch (GET_CODE (insn))
  85     {
  86     case NOTE:
  87     case CODE_LABEL:
  88       return false;
  89
  90     case JUMP_INSN:
  91       /* Jump insn always causes control transfer except for tablejumps.  */
  92       return (GET_CODE (PATTERN (insn)) != ADDR_VEC
  93               && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
  94
  95     case CALL_INSN:
  96       /* Noreturn and sibling call instructions terminate the basic blocks
  97          (but only if they happen unconditionally).  */
  98       if ((SIBLING_CALL_P (insn)
  99            || find_reg_note (insn, REG_NORETURN, 0))
 100           && GET_CODE (PATTERN (insn)) != COND_EXEC)
 101         return true;
 102       /* Call insn may return to the nonlocal goto handler.  */
 103       return ((nonlocal_goto_handler_labels
 104                && (0 == (note = find_reg_note (insn, REG_EH_REGION,
 105                                                NULL_RTX))
 106                    || INTVAL (XEXP (note, 0)) >= 0))
 107               /* Or may trap.  */
 108               || can_throw_internal (insn));
 109
 110     case INSN:
 111       /* Treat trap instructions like noreturn calls (same provision).  */
 112       if (GET_CODE (PATTERN (insn)) == TRAP_IF
 113           && XEXP (PATTERN (insn), 0) == const1_rtx)
 114         return true;
 115
 116       return (flag_non_call_exceptions && can_throw_internal (insn));
 117
 118     case BARRIER:
 119       /* It is nonsense to reach barrier when looking for the
 120          end of basic block, but before dead code is eliminated
 121          this may happen.  */
 122       return false;
 123
 124     default:
 125       gcc_unreachable ();
 126     }
 127 }
 128
 129 \f
 130 /* Create an edge between two basic blocks.  FLAGS are auxiliary information
 131    about the edge that is accumulated between calls.  */
 132
 133 /* Create an edge from a basic block to a label.  */
 134
 135 static void
 136 make_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags)
 137 {
 138   gcc_assert (LABEL_P (label));
 139
 140   /* If the label was never emitted, this insn is junk, but avoid a
 141      crash trying to refer to BLOCK_FOR_INSN (label).  This can happen
 142      as a result of a syntax error and a diagnostic has already been
 143      printed.  */
 144
 145   if (INSN_UID (label) == 0)
 146     return;
 147
 148   cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
 149 }
 150
 151 /* Create the edges generated by INSN in REGION.  */
 152
 153 void
 154 rtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx insn)
 155 {
 156   int is_call = CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0;
 157   rtx handlers, i;
 158
 159   handlers = reachable_handlers (insn);
 160
 161   for (i = handlers; i; i = XEXP (i, 1))
 162     make_label_edge (edge_cache, src, XEXP (i, 0),
 163                      EDGE_ABNORMAL | EDGE_EH | is_call);
 164
 165   free_INSN_LIST_list (&handlers);
 166 }
 167
 168 /* States of basic block as seen by find_many_sub_basic_blocks.  */
 169 enum state {
 170   /* Basic blocks created via split_block belong to this state.
 171      make_edges will examine these basic blocks to see if we need to
 172      create edges going out of them.  */
 173   BLOCK_NEW = 0,
 174
 175   /* Basic blocks that do not need examining belong to this state.
 176      These blocks will be left intact.  In particular, make_edges will
 177      not create edges going out of these basic blocks.  */
 178   BLOCK_ORIGINAL,
 179
 180   /* Basic blocks that may need splitting (due to a label appearing in
 181      the middle, etc) belong to this state.  After splitting them,
 182      make_edges will create edges going out of them as needed.  */
 183   BLOCK_TO_SPLIT
 184 };
 185
 186 #define STATE(BB) (enum state) ((size_t) (BB)->aux)
 187 #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
 188
 189 /* Used internally by purge_dead_tablejump_edges, ORed into state.  */
 190 #define BLOCK_USED_BY_TABLEJUMP         32
 191 #define FULL_STATE(BB) ((size_t) (BB)->aux)
 192
 193 /* Identify the edges going out of basic blocks between MIN and MAX,
 194    inclusive, that have their states set to BLOCK_NEW or
 195    BLOCK_TO_SPLIT.
 196
 197    UPDATE_P should be nonzero if we are updating CFG and zero if we
 198    are building CFG from scratch.  */
 199
 200 static void
 201 make_edges (basic_block min, basic_block max, int update_p)
 202 {
 203   basic_block bb;
 204   sbitmap edge_cache = NULL;
 205
 206   /* Heavy use of computed goto in machine-generated code can lead to
 207      nearly fully-connected CFGs.  In that case we spend a significant
 208      amount of time searching the edge lists for duplicates.  */
 209   if (forced_labels || cfun->cfg->max_jumptable_ents > 100)
 210     edge_cache = sbitmap_alloc (last_basic_block);
 211
 212   /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
 213      is always the entry.  */
 214   if (min == ENTRY_BLOCK_PTR->next_bb)
 215     make_edge (ENTRY_BLOCK_PTR, min, EDGE_FALLTHRU);
 216
 217   FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 218     {
 219       rtx insn, x;
 220       enum rtx_code code;
 221       edge e;
 222       edge_iterator ei;
 223
 224       if (STATE (bb) == BLOCK_ORIGINAL)
 225         continue;
 226
 227       /* If we have an edge cache, cache edges going out of BB.  */
 228       if (edge_cache)
 229         {
 230           sbitmap_zero (edge_cache);
 231           if (update_p)
 232             {
 233               FOR_EACH_EDGE (e, ei, bb->succs)
 234                 if (e->dest != EXIT_BLOCK_PTR)
 235                   SET_BIT (edge_cache, e->dest->index);
 236             }
 237         }
 238
 239       if (LABEL_P (BB_HEAD (bb))
 240           && LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
 241         cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
 242
 243       /* Examine the last instruction of the block, and discover the
 244          ways we can leave the block.  */
 245
 246       insn = BB_END (bb);
 247       code = GET_CODE (insn);
 248
 249       /* A branch.  */
 250       if (code == JUMP_INSN)
 251         {
 252           rtx tmp;
 253
 254           /* Recognize exception handling placeholders.  */
 255           if (GET_CODE (PATTERN (insn)) == RESX)
 256             rtl_make_eh_edge (edge_cache, bb, insn);
 257
 258           /* Recognize a non-local goto as a branch outside the
 259              current function.  */
 260           else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
 261             ;
 262
 263           /* Recognize a tablejump and do the right thing.  */
 264           else if (tablejump_p (insn, NULL, &tmp))
 265             {
 266               rtvec vec;
 267               int j;
 268
 269               if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
 270                 vec = XVEC (PATTERN (tmp), 0);
 271               else
 272                 vec = XVEC (PATTERN (tmp), 1);
 273
 274               for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
 275                 make_label_edge (edge_cache, bb,
 276                                  XEXP (RTVEC_ELT (vec, j), 0), 0);
 277
 278               /* Some targets (eg, ARM) emit a conditional jump that also
 279                  contains the out-of-range target.  Scan for these and
 280                  add an edge if necessary.  */
 281               if ((tmp = single_set (insn)) != NULL
 282                   && SET_DEST (tmp) == pc_rtx
 283                   && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
 284                   && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 285                 make_label_edge (edge_cache, bb,
 286                                  XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
 287             }
 288
 289           /* If this is a computed jump, then mark it as reaching
 290              everything on the forced_labels list.  */
 291           else if (computed_jump_p (insn))
 292             {
 293               for (x = forced_labels; x; x = XEXP (x, 1))
 294                 make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
 295             }
 296
 297           /* Returns create an exit out.  */
 298           else if (returnjump_p (insn))
 299             cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
 300
 301           /* Otherwise, we have a plain conditional or unconditional jump.  */
 302           else
 303             {
 304               gcc_assert (JUMP_LABEL (insn));
 305               make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
 306             }
 307         }
 308
 309       /* If this is a sibling call insn, then this is in effect a combined call
 310          and return, and so we need an edge to the exit block.  No need to
 311          worry about EH edges, since we wouldn't have created the sibling call
 312          in the first place.  */
 313       if (code == CALL_INSN && SIBLING_CALL_P (insn))
 314         cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
 315                           EDGE_SIBCALL | EDGE_ABNORMAL);
 316
 317       /* If this is a CALL_INSN, then mark it as reaching the active EH
 318          handler for this CALL_INSN.  If we're handling non-call
 319          exceptions then any insn can reach any of the active handlers.
 320          Also mark the CALL_INSN as reaching any nonlocal goto handler.  */
 321       else if (code == CALL_INSN || flag_non_call_exceptions)
 322         {
 323           /* Add any appropriate EH edges.  */
 324           rtl_make_eh_edge (edge_cache, bb, insn);
 325
 326           if (code == CALL_INSN && nonlocal_goto_handler_labels)
 327             {
 328               /* ??? This could be made smarter: in some cases it's possible
 329                  to tell that certain calls will not do a nonlocal goto.
 330                  For example, if the nested functions that do the nonlocal
 331                  gotos do not have their addresses taken, then only calls to
 332                  those functions or to other nested functions that use them
 333                  could possibly do nonlocal gotos.  */
 334
 335               /* We do know that a REG_EH_REGION note with a value less
 336                  than 0 is guaranteed not to perform a non-local goto.  */
 337               rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
 338
 339               if (!note || INTVAL (XEXP (note, 0)) >=  0)
 340                 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
 341                   make_label_edge (edge_cache, bb, XEXP (x, 0),
 342                                    EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
 343             }
 344         }
 345
 346       /* Find out if we can drop through to the next block.  */
 347       insn = NEXT_INSN (insn);
 348       e = find_edge (bb, EXIT_BLOCK_PTR);
 349       if (e && e->flags & EDGE_FALLTHRU)
 350         insn = NULL;
 351
 352       while (insn
 353              && NOTE_P (insn)
 354              && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
 355         insn = NEXT_INSN (insn);
 356
 357       if (!insn)
 358         cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
 359       else if (bb->next_bb != EXIT_BLOCK_PTR)
 360         {
 361           if (insn == BB_HEAD (bb->next_bb))
 362             cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
 363         }
 364     }
 365
 366   if (edge_cache)
 367     sbitmap_vector_free (edge_cache);
 368 }
 369 \f
 370 static void
 371 mark_tablejump_edge (rtx label)
 372 {
 373   basic_block bb;
 374
 375   gcc_assert (LABEL_P (label));
 376   /* See comment in make_label_edge.  */
 377   if (INSN_UID (label) == 0)
 378     return;
 379   bb = BLOCK_FOR_INSN (label);
 380   SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
 381 }
 382
 383 static void
 384 purge_dead_tablejump_edges (basic_block bb, rtx table)
 385 {
 386   rtx insn = BB_END (bb), tmp;
 387   rtvec vec;
 388   int j;
 389   edge_iterator ei;
 390   edge e;
 391
 392   if (GET_CODE (PATTERN (table)) == ADDR_VEC)
 393     vec = XVEC (PATTERN (table), 0);
 394   else
 395     vec = XVEC (PATTERN (table), 1);
 396
 397   for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
 398     mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0));
 399
 400   /* Some targets (eg, ARM) emit a conditional jump that also
 401      contains the out-of-range target.  Scan for these and
 402      add an edge if necessary.  */
 403   if ((tmp = single_set (insn)) != NULL
 404        && SET_DEST (tmp) == pc_rtx
 405        && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
 406        && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
 407     mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0));
 408
 409   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 410     {
 411       if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
 412         SET_STATE (e->dest, FULL_STATE (e->dest)
 413                             & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
 414       else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
 415         {
 416           remove_edge (e);
 417           continue;
 418         }
 419       ei_next (&ei);
 420     }
 421 }
 422
 423 /* Scan basic block BB for possible BB boundaries inside the block
 424    and create new basic blocks in the progress.  */
 425
 426 static void
 427 find_bb_boundaries (basic_block bb)
 428 {
 429   basic_block orig_bb = bb;
 430   rtx insn = BB_HEAD (bb);
 431   rtx end = BB_END (bb), x;
 432   rtx table;
 433   rtx flow_transfer_insn = NULL_RTX;
 434   edge fallthru = NULL;
 435
 436   if (insn == BB_END (bb))
 437     return;
 438
 439   if (LABEL_P (insn))
 440     insn = NEXT_INSN (insn);
 441
 442   /* Scan insn chain and try to find new basic block boundaries.  */
 443   while (1)
 444     {
 445       enum rtx_code code = GET_CODE (insn);
 446
 447       /* On code label, split current basic block.  */
 448       if (code == CODE_LABEL)
 449         {
 450           fallthru = split_block (bb, PREV_INSN (insn));
 451           if (flow_transfer_insn)
 452             {
 453               BB_END (bb) = flow_transfer_insn;
 454
 455               /* Clean up the bb field for the insns between the blocks.  */
 456               for (x = NEXT_INSN (flow_transfer_insn);
 457                    x != BB_HEAD (fallthru->dest);
 458                    x = NEXT_INSN (x))
 459                 if (!BARRIER_P (x))
 460                   set_block_for_insn (x, NULL);
 461             }
 462
 463           bb = fallthru->dest;
 464           remove_edge (fallthru);
 465           flow_transfer_insn = NULL_RTX;
 466           if (LABEL_ALT_ENTRY_P (insn))
 467             make_edge (ENTRY_BLOCK_PTR, bb, 0);
 468         }
 469
 470       /* In case we've previously seen an insn that effects a control
 471          flow transfer, split the block.  */
 472       if (flow_transfer_insn && inside_basic_block_p (insn))
 473         {
 474           fallthru = split_block (bb, PREV_INSN (insn));
 475           BB_END (bb) = flow_transfer_insn;
 476
 477           /* Clean up the bb field for the insns between the blocks.  */
 478           for (x = NEXT_INSN (flow_transfer_insn);
 479                x != BB_HEAD (fallthru->dest);
 480                x = NEXT_INSN (x))
 481             if (!BARRIER_P (x))
 482               set_block_for_insn (x, NULL);
 483
 484           bb = fallthru->dest;
 485           remove_edge (fallthru);
 486           flow_transfer_insn = NULL_RTX;
 487         }
 488
 489       if (control_flow_insn_p (insn))
 490         flow_transfer_insn = insn;
 491       if (insn == end)
 492         break;
 493       insn = NEXT_INSN (insn);
 494     }
 495
 496   /* In case expander replaced normal insn by sequence terminating by
 497      return and barrier, or possibly other sequence not behaving like
 498      ordinary jump, we need to take care and move basic block boundary.  */
 499   if (flow_transfer_insn)
 500     {
 501       BB_END (bb) = flow_transfer_insn;
 502
 503       /* Clean up the bb field for the insns that do not belong to BB.  */
 504       x = flow_transfer_insn;
 505       while (x != end)
 506         {
 507           x = NEXT_INSN (x);
 508           if (!BARRIER_P (x))
 509             set_block_for_insn (x, NULL);
 510         }
 511     }
 512
 513   /* We've possibly replaced the conditional jump by conditional jump
 514      followed by cleanup at fallthru edge, so the outgoing edges may
 515      be dead.  */
 516   purge_dead_edges (bb);
 517
 518   /* purge_dead_edges doesn't handle tablejump's, but if we have split the
 519      basic block, we might need to kill some edges.  */
 520   if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
 521     purge_dead_tablejump_edges (bb, table);
 522 }
 523
 524 /*  Assume that frequency of basic block B is known.  Compute frequencies
 525     and probabilities of outgoing edges.  */
 526
 527 static void
 528 compute_outgoing_frequencies (basic_block b)
 529 {
 530   edge e, f;
 531   edge_iterator ei;
 532
 533   if (EDGE_COUNT (b->succs) == 2)
 534     {
 535       rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
 536       int probability;
 537
 538       if (note)
 539         {
 540           probability = INTVAL (XEXP (note, 0));
 541           e = BRANCH_EDGE (b);
 542           e->probability = probability;
 543           e->count = ((b->count * probability + REG_BR_PROB_BASE / 2)
 544                       / REG_BR_PROB_BASE);
 545           f = FALLTHRU_EDGE (b);
 546           f->probability = REG_BR_PROB_BASE - probability;
 547           f->count = b->count - e->count;
 548           return;
 549         }
 550     }
 551
 552   if (single_succ_p (b))
 553     {
 554       e = single_succ_edge (b);
 555       e->probability = REG_BR_PROB_BASE;
 556       e->count = b->count;
 557       return;
 558     }
 559   guess_outgoing_edge_probabilities (b);
 560   if (b->count)
 561     FOR_EACH_EDGE (e, ei, b->succs)
 562       e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2)
 563                   / REG_BR_PROB_BASE);
 564 }
 565
 566 /* Assume that some pass has inserted labels or control flow
 567    instructions within a basic block.  Split basic blocks as needed
 568    and create edges.  */
 569
 570 void
 571 find_many_sub_basic_blocks (sbitmap blocks)
 572 {
 573   basic_block bb, min, max;
 574
 575   FOR_EACH_BB (bb)
 576     SET_STATE (bb,
 577                TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
 578
 579   FOR_EACH_BB (bb)
 580     if (STATE (bb) == BLOCK_TO_SPLIT)
 581       find_bb_boundaries (bb);
 582
 583   FOR_EACH_BB (bb)
 584     if (STATE (bb) != BLOCK_ORIGINAL)
 585       break;
 586
 587   min = max = bb;
 588   for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
 589     if (STATE (bb) != BLOCK_ORIGINAL)
 590       max = bb;
 591
 592   /* Now re-scan and wire in all edges.  This expect simple (conditional)
 593      jumps at the end of each new basic blocks.  */
 594   make_edges (min, max, 1);
 595
 596   /* Update branch probabilities.  Expect only (un)conditional jumps
 597      to be created with only the forward edges.  */
 598   if (profile_status != PROFILE_ABSENT)
 599     FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
 600       {
 601         edge e;
 602         edge_iterator ei;
 603
 604         if (STATE (bb) == BLOCK_ORIGINAL)
 605           continue;
 606         if (STATE (bb) == BLOCK_NEW)
 607           {
 608             bb->count = 0;
 609             bb->frequency = 0;
 610             FOR_EACH_EDGE (e, ei, bb->preds)
 611               {
 612                 bb->count += e->count;
 613                 bb->frequency += EDGE_FREQUENCY (e);
 614               }
 615           }
 616
 617         compute_outgoing_frequencies (bb);
 618       }
 619
 620   FOR_EACH_BB (bb)
 621     SET_STATE (bb, 0);
 622 }