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, 2009, 2010 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 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 "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 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 (!cfun->can_throw_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 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 || cfun->can_throw_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) 342 { 343 if (can_nonlocal_goto (insn)) 344 { 345 /* ??? This could be made smarter: in some cases it's 346 possible to tell that certain calls will not do a 347 nonlocal goto. For example, if the nested functions 348 that do the nonlocal gotos do not have their addresses 349 taken, then only calls to those functions or to other 350 nested functions that use them could possibly do 351 nonlocal gotos. */ 352 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1)) 353 make_label_edge (edge_cache, bb, XEXP (x, 0), 354 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); 355 } 356 357 if (flag_tm) 358 { 359 rtx note; 360 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 361 if (REG_NOTE_KIND (note) == REG_TM) 362 make_label_edge (edge_cache, bb, XEXP (note, 0), 363 EDGE_ABNORMAL | EDGE_ABNORMAL_CALL); 364 } 365 } 366 } 367 368 /* Find out if we can drop through to the next block. */ 369 insn = NEXT_INSN (insn); 370 e = find_edge (bb, EXIT_BLOCK_PTR); 371 if (e && e->flags & EDGE_FALLTHRU) 372 insn = NULL; 373 374 while (insn 375 && NOTE_P (insn) 376 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK) 377 insn = NEXT_INSN (insn); 378 379 if (!insn) 380 cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU); 381 else if (bb->next_bb != EXIT_BLOCK_PTR) 382 { 383 if (insn == BB_HEAD (bb->next_bb)) 384 cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU); 385 } 386 } 387 388 if (edge_cache) 389 sbitmap_vector_free (edge_cache); 390 } 391 392 static void 393 mark_tablejump_edge (rtx label) 394 { 395 basic_block bb; 396 397 gcc_assert (LABEL_P (label)); 398 /* See comment in make_label_edge. */ 399 if (INSN_UID (label) == 0) 400 return; 401 bb = BLOCK_FOR_INSN (label); 402 SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP); 403 } 404 405 static void 406 purge_dead_tablejump_edges (basic_block bb, rtx table) 407 { 408 rtx insn = BB_END (bb), tmp; 409 rtvec vec; 410 int j; 411 edge_iterator ei; 412 edge e; 413 414 if (GET_CODE (PATTERN (table)) == ADDR_VEC) 415 vec = XVEC (PATTERN (table), 0); 416 else 417 vec = XVEC (PATTERN (table), 1); 418 419 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j) 420 mark_tablejump_edge (XEXP (RTVEC_ELT (vec, j), 0)); 421 422 /* Some targets (eg, ARM) emit a conditional jump that also 423 contains the out-of-range target. Scan for these and 424 add an edge if necessary. */ 425 if ((tmp = single_set (insn)) != NULL 426 && SET_DEST (tmp) == pc_rtx 427 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE 428 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF) 429 mark_tablejump_edge (XEXP (XEXP (SET_SRC (tmp), 2), 0)); 430 431 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 432 { 433 if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP) 434 SET_STATE (e->dest, FULL_STATE (e->dest) 435 & ~(size_t) BLOCK_USED_BY_TABLEJUMP); 436 else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH))) 437 { 438 remove_edge (e); 439 continue; 440 } 441 ei_next (&ei); 442 } 443 } 444 445 /* Scan basic block BB for possible BB boundaries inside the block 446 and create new basic blocks in the progress. */ 447 448 static void 449 find_bb_boundaries (basic_block bb) 450 { 451 basic_block orig_bb = bb; 452 rtx insn = BB_HEAD (bb); 453 rtx end = BB_END (bb), x; 454 rtx table; 455 rtx flow_transfer_insn = NULL_RTX; 456 edge fallthru = NULL; 457 458 if (insn == BB_END (bb)) 459 return; 460 461 if (LABEL_P (insn)) 462 insn = NEXT_INSN (insn); 463 464 /* Scan insn chain and try to find new basic block boundaries. */ 465 while (1) 466 { 467 enum rtx_code code = GET_CODE (insn); 468 469 /* In case we've previously seen an insn that effects a control 470 flow transfer, split the block. */ 471 if ((flow_transfer_insn || code == CODE_LABEL) 472 && inside_basic_block_p (insn)) 473 { 474 fallthru = split_block (bb, PREV_INSN (insn)); 475 if (flow_transfer_insn) 476 { 477 BB_END (bb) = flow_transfer_insn; 478 479 /* Clean up the bb field for the insns between the blocks. */ 480 for (x = NEXT_INSN (flow_transfer_insn); 481 x != BB_HEAD (fallthru->dest); 482 x = NEXT_INSN (x)) 483 if (!BARRIER_P (x)) 484 set_block_for_insn (x, NULL); 485 } 486 487 bb = fallthru->dest; 488 remove_edge (fallthru); 489 flow_transfer_insn = NULL_RTX; 490 if (code == CODE_LABEL && LABEL_ALT_ENTRY_P (insn)) 491 make_edge (ENTRY_BLOCK_PTR, bb, 0); 492 } 493 else if (code == BARRIER) 494 { 495 /* __builtin_unreachable () may cause a barrier to be emitted in 496 the middle of a BB. We need to split it in the same manner as 497 if the barrier were preceded by a control_flow_insn_p insn. */ 498 if (!flow_transfer_insn) 499 flow_transfer_insn = prev_nonnote_insn_bb (insn); 500 } 501 502 if (control_flow_insn_p (insn)) 503 flow_transfer_insn = insn; 504 if (insn == end) 505 break; 506 insn = NEXT_INSN (insn); 507 } 508 509 /* In case expander replaced normal insn by sequence terminating by 510 return and barrier, or possibly other sequence not behaving like 511 ordinary jump, we need to take care and move basic block boundary. */ 512 if (flow_transfer_insn) 513 { 514 BB_END (bb) = flow_transfer_insn; 515 516 /* Clean up the bb field for the insns that do not belong to BB. */ 517 x = flow_transfer_insn; 518 while (x != end) 519 { 520 x = NEXT_INSN (x); 521 if (!BARRIER_P (x)) 522 set_block_for_insn (x, NULL); 523 } 524 } 525 526 /* We've possibly replaced the conditional jump by conditional jump 527 followed by cleanup at fallthru edge, so the outgoing edges may 528 be dead. */ 529 purge_dead_edges (bb); 530 531 /* purge_dead_edges doesn't handle tablejump's, but if we have split the 532 basic block, we might need to kill some edges. */ 533 if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table)) 534 purge_dead_tablejump_edges (bb, table); 535 } 536 537 /* Assume that frequency of basic block B is known. Compute frequencies 538 and probabilities of outgoing edges. */ 539 540 static void 541 compute_outgoing_frequencies (basic_block b) 542 { 543 edge e, f; 544 edge_iterator ei; 545 546 if (EDGE_COUNT (b->succs) == 2) 547 { 548 rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL); 549 int probability; 550 551 if (note) 552 { 553 probability = INTVAL (XEXP (note, 0)); 554 e = BRANCH_EDGE (b); 555 e->probability = probability; 556 e->count = ((b->count * probability + REG_BR_PROB_BASE / 2) 557 / REG_BR_PROB_BASE); 558 f = FALLTHRU_EDGE (b); 559 f->probability = REG_BR_PROB_BASE - probability; 560 f->count = b->count - e->count; 561 return; 562 } 563 } 564 565 if (single_succ_p (b)) 566 { 567 e = single_succ_edge (b); 568 e->probability = REG_BR_PROB_BASE; 569 e->count = b->count; 570 return; 571 } 572 guess_outgoing_edge_probabilities (b); 573 if (b->count) 574 FOR_EACH_EDGE (e, ei, b->succs) 575 e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) 576 / REG_BR_PROB_BASE); 577 } 578 579 /* Assume that some pass has inserted labels or control flow 580 instructions within a basic block. Split basic blocks as needed 581 and create edges. */ 582 583 void 584 find_many_sub_basic_blocks (sbitmap blocks) 585 { 586 basic_block bb, min, max; 587 588 FOR_EACH_BB (bb) 589 SET_STATE (bb, 590 TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL); 591 592 FOR_EACH_BB (bb) 593 if (STATE (bb) == BLOCK_TO_SPLIT) 594 find_bb_boundaries (bb); 595 596 FOR_EACH_BB (bb) 597 if (STATE (bb) != BLOCK_ORIGINAL) 598 break; 599 600 min = max = bb; 601 for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb) 602 if (STATE (bb) != BLOCK_ORIGINAL) 603 max = bb; 604 605 /* Now re-scan and wire in all edges. This expect simple (conditional) 606 jumps at the end of each new basic blocks. */ 607 make_edges (min, max, 1); 608 609 /* Update branch probabilities. Expect only (un)conditional jumps 610 to be created with only the forward edges. */ 611 if (profile_status != PROFILE_ABSENT) 612 FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb) 613 { 614 edge e; 615 edge_iterator ei; 616 617 if (STATE (bb) == BLOCK_ORIGINAL) 618 continue; 619 if (STATE (bb) == BLOCK_NEW) 620 { 621 bb->count = 0; 622 bb->frequency = 0; 623 FOR_EACH_EDGE (e, ei, bb->preds) 624 { 625 bb->count += e->count; 626 bb->frequency += EDGE_FREQUENCY (e); 627 } 628 } 629 630 compute_outgoing_frequencies (bb); 631 } 632 633 FOR_EACH_BB (bb) 634 SET_STATE (bb, 0); 635 } 636