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