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