1 /* Control flow optimization code for GNU compiler. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011 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 /* This file contains optimizer of the control flow. The main entry point is 23 cleanup_cfg. Following optimizations are performed: 24 25 - Unreachable blocks removal 26 - Edge forwarding (edge to the forwarder block is forwarded to its 27 successor. Simplification of the branch instruction is performed by 28 underlying infrastructure so branch can be converted to simplejump or 29 eliminated). 30 - Cross jumping (tail merging) 31 - Conditional jump-around-simplejump simplification 32 - Basic block merging. */ 33 34 #include "config.h" 35 #include "system.h" 36 #include "coretypes.h" 37 #include "tm.h" 38 #include "rtl.h" 39 #include "hard-reg-set.h" 40 #include "regs.h" 41 #include "timevar.h" 42 #include "output.h" 43 #include "insn-config.h" 44 #include "flags.h" 45 #include "recog.h" 46 #include "diagnostic-core.h" 47 #include "cselib.h" 48 #include "params.h" 49 #include "tm_p.h" 50 #include "target.h" 51 #include "cfglayout.h" 52 #include "emit-rtl.h" 53 #include "tree-pass.h" 54 #include "cfgloop.h" 55 #include "expr.h" 56 #include "df.h" 57 #include "dce.h" 58 #include "dbgcnt.h" 59 60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK) 61 62 /* Set to true when we are running first pass of try_optimize_cfg loop. */ 63 static bool first_pass; 64 65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg. */ 66 static bool crossjumps_occured; 67 68 /* Set to true if we couldn't run an optimization due to stale liveness 69 information; we should run df_analyze to enable more opportunities. */ 70 static bool block_was_dirty; 71 72 static bool try_crossjump_to_edge (int, edge, edge, enum replace_direction); 73 static bool try_crossjump_bb (int, basic_block); 74 static bool outgoing_edges_match (int, basic_block, basic_block); 75 static enum replace_direction old_insns_match_p (int, rtx, rtx); 76 77 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block); 78 static void merge_blocks_move_successor_nojumps (basic_block, basic_block); 79 static bool try_optimize_cfg (int); 80 static bool try_simplify_condjump (basic_block); 81 static bool try_forward_edges (int, basic_block); 82 static edge thread_jump (edge, basic_block); 83 static bool mark_effect (rtx, bitmap); 84 static void notice_new_block (basic_block); 85 static void update_forwarder_flag (basic_block); 86 static int mentions_nonequal_regs (rtx *, void *); 87 static void merge_memattrs (rtx, rtx); 88 89 /* Set flags for newly created block. */ 90 91 static void 92 notice_new_block (basic_block bb) 93 { 94 if (!bb) 95 return; 96 97 if (forwarder_block_p (bb)) 98 bb->flags |= BB_FORWARDER_BLOCK; 99 } 100 101 /* Recompute forwarder flag after block has been modified. */ 102 103 static void 104 update_forwarder_flag (basic_block bb) 105 { 106 if (forwarder_block_p (bb)) 107 bb->flags |= BB_FORWARDER_BLOCK; 108 else 109 bb->flags &= ~BB_FORWARDER_BLOCK; 110 } 111 112 /* Simplify a conditional jump around an unconditional jump. 113 Return true if something changed. */ 114 115 static bool 116 try_simplify_condjump (basic_block cbranch_block) 117 { 118 basic_block jump_block, jump_dest_block, cbranch_dest_block; 119 edge cbranch_jump_edge, cbranch_fallthru_edge; 120 rtx cbranch_insn; 121 122 /* Verify that there are exactly two successors. */ 123 if (EDGE_COUNT (cbranch_block->succs) != 2) 124 return false; 125 126 /* Verify that we've got a normal conditional branch at the end 127 of the block. */ 128 cbranch_insn = BB_END (cbranch_block); 129 if (!any_condjump_p (cbranch_insn)) 130 return false; 131 132 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block); 133 cbranch_jump_edge = BRANCH_EDGE (cbranch_block); 134 135 /* The next block must not have multiple predecessors, must not 136 be the last block in the function, and must contain just the 137 unconditional jump. */ 138 jump_block = cbranch_fallthru_edge->dest; 139 if (!single_pred_p (jump_block) 140 || jump_block->next_bb == EXIT_BLOCK_PTR 141 || !FORWARDER_BLOCK_P (jump_block)) 142 return false; 143 jump_dest_block = single_succ (jump_block); 144 145 /* If we are partitioning hot/cold basic blocks, we don't want to 146 mess up unconditional or indirect jumps that cross between hot 147 and cold sections. 148 149 Basic block partitioning may result in some jumps that appear to 150 be optimizable (or blocks that appear to be mergeable), but which really 151 must be left untouched (they are required to make it safely across 152 partition boundaries). See the comments at the top of 153 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 154 155 if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block) 156 || (cbranch_jump_edge->flags & EDGE_CROSSING)) 157 return false; 158 159 /* The conditional branch must target the block after the 160 unconditional branch. */ 161 cbranch_dest_block = cbranch_jump_edge->dest; 162 163 if (cbranch_dest_block == EXIT_BLOCK_PTR 164 || !can_fallthru (jump_block, cbranch_dest_block)) 165 return false; 166 167 /* Invert the conditional branch. */ 168 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0)) 169 return false; 170 171 if (dump_file) 172 fprintf (dump_file, "Simplifying condjump %i around jump %i\n", 173 INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block))); 174 175 /* Success. Update the CFG to match. Note that after this point 176 the edge variable names appear backwards; the redirection is done 177 this way to preserve edge profile data. */ 178 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge, 179 cbranch_dest_block); 180 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge, 181 jump_dest_block); 182 cbranch_jump_edge->flags |= EDGE_FALLTHRU; 183 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU; 184 update_br_prob_note (cbranch_block); 185 186 /* Delete the block with the unconditional jump, and clean up the mess. */ 187 delete_basic_block (jump_block); 188 tidy_fallthru_edge (cbranch_jump_edge); 189 update_forwarder_flag (cbranch_block); 190 191 return true; 192 } 193 194 /* Attempt to prove that operation is NOOP using CSElib or mark the effect 195 on register. Used by jump threading. */ 196 197 static bool 198 mark_effect (rtx exp, regset nonequal) 199 { 200 int regno; 201 rtx dest; 202 switch (GET_CODE (exp)) 203 { 204 /* In case we do clobber the register, mark it as equal, as we know the 205 value is dead so it don't have to match. */ 206 case CLOBBER: 207 if (REG_P (XEXP (exp, 0))) 208 { 209 dest = XEXP (exp, 0); 210 regno = REGNO (dest); 211 if (HARD_REGISTER_NUM_P (regno)) 212 bitmap_clear_range (nonequal, regno, 213 hard_regno_nregs[regno][GET_MODE (dest)]); 214 else 215 bitmap_clear_bit (nonequal, regno); 216 } 217 return false; 218 219 case SET: 220 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp))) 221 return false; 222 dest = SET_DEST (exp); 223 if (dest == pc_rtx) 224 return false; 225 if (!REG_P (dest)) 226 return true; 227 regno = REGNO (dest); 228 if (HARD_REGISTER_NUM_P (regno)) 229 bitmap_set_range (nonequal, regno, 230 hard_regno_nregs[regno][GET_MODE (dest)]); 231 else 232 bitmap_set_bit (nonequal, regno); 233 return false; 234 235 default: 236 return false; 237 } 238 } 239 240 /* Return nonzero if X is a register set in regset DATA. 241 Called via for_each_rtx. */ 242 static int 243 mentions_nonequal_regs (rtx *x, void *data) 244 { 245 regset nonequal = (regset) data; 246 if (REG_P (*x)) 247 { 248 int regno; 249 250 regno = REGNO (*x); 251 if (REGNO_REG_SET_P (nonequal, regno)) 252 return 1; 253 if (regno < FIRST_PSEUDO_REGISTER) 254 { 255 int n = hard_regno_nregs[regno][GET_MODE (*x)]; 256 while (--n > 0) 257 if (REGNO_REG_SET_P (nonequal, regno + n)) 258 return 1; 259 } 260 } 261 return 0; 262 } 263 /* Attempt to prove that the basic block B will have no side effects and 264 always continues in the same edge if reached via E. Return the edge 265 if exist, NULL otherwise. */ 266 267 static edge 268 thread_jump (edge e, basic_block b) 269 { 270 rtx set1, set2, cond1, cond2, insn; 271 enum rtx_code code1, code2, reversed_code2; 272 bool reverse1 = false; 273 unsigned i; 274 regset nonequal; 275 bool failed = false; 276 reg_set_iterator rsi; 277 278 if (b->flags & BB_NONTHREADABLE_BLOCK) 279 return NULL; 280 281 /* At the moment, we do handle only conditional jumps, but later we may 282 want to extend this code to tablejumps and others. */ 283 if (EDGE_COUNT (e->src->succs) != 2) 284 return NULL; 285 if (EDGE_COUNT (b->succs) != 2) 286 { 287 b->flags |= BB_NONTHREADABLE_BLOCK; 288 return NULL; 289 } 290 291 /* Second branch must end with onlyjump, as we will eliminate the jump. */ 292 if (!any_condjump_p (BB_END (e->src))) 293 return NULL; 294 295 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b))) 296 { 297 b->flags |= BB_NONTHREADABLE_BLOCK; 298 return NULL; 299 } 300 301 set1 = pc_set (BB_END (e->src)); 302 set2 = pc_set (BB_END (b)); 303 if (((e->flags & EDGE_FALLTHRU) != 0) 304 != (XEXP (SET_SRC (set1), 1) == pc_rtx)) 305 reverse1 = true; 306 307 cond1 = XEXP (SET_SRC (set1), 0); 308 cond2 = XEXP (SET_SRC (set2), 0); 309 if (reverse1) 310 code1 = reversed_comparison_code (cond1, BB_END (e->src)); 311 else 312 code1 = GET_CODE (cond1); 313 314 code2 = GET_CODE (cond2); 315 reversed_code2 = reversed_comparison_code (cond2, BB_END (b)); 316 317 if (!comparison_dominates_p (code1, code2) 318 && !comparison_dominates_p (code1, reversed_code2)) 319 return NULL; 320 321 /* Ensure that the comparison operators are equivalent. 322 ??? This is far too pessimistic. We should allow swapped operands, 323 different CCmodes, or for example comparisons for interval, that 324 dominate even when operands are not equivalent. */ 325 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0)) 326 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1))) 327 return NULL; 328 329 /* Short circuit cases where block B contains some side effects, as we can't 330 safely bypass it. */ 331 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b)); 332 insn = NEXT_INSN (insn)) 333 if (INSN_P (insn) && side_effects_p (PATTERN (insn))) 334 { 335 b->flags |= BB_NONTHREADABLE_BLOCK; 336 return NULL; 337 } 338 339 cselib_init (0); 340 341 /* First process all values computed in the source basic block. */ 342 for (insn = NEXT_INSN (BB_HEAD (e->src)); 343 insn != NEXT_INSN (BB_END (e->src)); 344 insn = NEXT_INSN (insn)) 345 if (INSN_P (insn)) 346 cselib_process_insn (insn); 347 348 nonequal = BITMAP_ALLOC (NULL); 349 CLEAR_REG_SET (nonequal); 350 351 /* Now assume that we've continued by the edge E to B and continue 352 processing as if it were same basic block. 353 Our goal is to prove that whole block is an NOOP. */ 354 355 for (insn = NEXT_INSN (BB_HEAD (b)); 356 insn != NEXT_INSN (BB_END (b)) && !failed; 357 insn = NEXT_INSN (insn)) 358 { 359 if (INSN_P (insn)) 360 { 361 rtx pat = PATTERN (insn); 362 363 if (GET_CODE (pat) == PARALLEL) 364 { 365 for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++) 366 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal); 367 } 368 else 369 failed |= mark_effect (pat, nonequal); 370 } 371 372 cselib_process_insn (insn); 373 } 374 375 /* Later we should clear nonequal of dead registers. So far we don't 376 have life information in cfg_cleanup. */ 377 if (failed) 378 { 379 b->flags |= BB_NONTHREADABLE_BLOCK; 380 goto failed_exit; 381 } 382 383 /* cond2 must not mention any register that is not equal to the 384 former block. */ 385 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal)) 386 goto failed_exit; 387 388 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, rsi) 389 goto failed_exit; 390 391 BITMAP_FREE (nonequal); 392 cselib_finish (); 393 if ((comparison_dominates_p (code1, code2) != 0) 394 != (XEXP (SET_SRC (set2), 1) == pc_rtx)) 395 return BRANCH_EDGE (b); 396 else 397 return FALLTHRU_EDGE (b); 398 399 failed_exit: 400 BITMAP_FREE (nonequal); 401 cselib_finish (); 402 return NULL; 403 } 404 405 /* Attempt to forward edges leaving basic block B. 406 Return true if successful. */ 407 408 static bool 409 try_forward_edges (int mode, basic_block b) 410 { 411 bool changed = false; 412 edge_iterator ei; 413 edge e, *threaded_edges = NULL; 414 415 /* If we are partitioning hot/cold basic blocks, we don't want to 416 mess up unconditional or indirect jumps that cross between hot 417 and cold sections. 418 419 Basic block partitioning may result in some jumps that appear to 420 be optimizable (or blocks that appear to be mergeable), but which really 421 must be left untouched (they are required to make it safely across 422 partition boundaries). See the comments at the top of 423 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 424 425 if (find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)) 426 return false; 427 428 for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); ) 429 { 430 basic_block target, first; 431 int counter, goto_locus; 432 bool threaded = false; 433 int nthreaded_edges = 0; 434 bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0; 435 436 /* Skip complex edges because we don't know how to update them. 437 438 Still handle fallthru edges, as we can succeed to forward fallthru 439 edge to the same place as the branch edge of conditional branch 440 and turn conditional branch to an unconditional branch. */ 441 if (e->flags & EDGE_COMPLEX) 442 { 443 ei_next (&ei); 444 continue; 445 } 446 447 target = first = e->dest; 448 counter = NUM_FIXED_BLOCKS; 449 goto_locus = e->goto_locus; 450 451 /* If we are partitioning hot/cold basic_blocks, we don't want to mess 452 up jumps that cross between hot/cold sections. 453 454 Basic block partitioning may result in some jumps that appear 455 to be optimizable (or blocks that appear to be mergeable), but which 456 really must be left untouched (they are required to make it safely 457 across partition boundaries). See the comments at the top of 458 bb-reorder.c:partition_hot_cold_basic_blocks for complete 459 details. */ 460 461 if (first != EXIT_BLOCK_PTR 462 && find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX)) 463 return false; 464 465 while (counter < n_basic_blocks) 466 { 467 basic_block new_target = NULL; 468 bool new_target_threaded = false; 469 may_thread |= (target->flags & BB_MODIFIED) != 0; 470 471 if (FORWARDER_BLOCK_P (target) 472 && !(single_succ_edge (target)->flags & EDGE_CROSSING) 473 && single_succ (target) != EXIT_BLOCK_PTR) 474 { 475 /* Bypass trivial infinite loops. */ 476 new_target = single_succ (target); 477 if (target == new_target) 478 counter = n_basic_blocks; 479 else if (!optimize) 480 { 481 /* When not optimizing, ensure that edges or forwarder 482 blocks with different locus are not optimized out. */ 483 int new_locus = single_succ_edge (target)->goto_locus; 484 int locus = goto_locus; 485 486 if (new_locus && locus && !locator_eq (new_locus, locus)) 487 new_target = NULL; 488 else 489 { 490 rtx last; 491 492 if (new_locus) 493 locus = new_locus; 494 495 last = BB_END (target); 496 if (DEBUG_INSN_P (last)) 497 last = prev_nondebug_insn (last); 498 499 new_locus = last && INSN_P (last) 500 ? INSN_LOCATOR (last) : 0; 501 502 if (new_locus && locus && !locator_eq (new_locus, locus)) 503 new_target = NULL; 504 else 505 { 506 if (new_locus) 507 locus = new_locus; 508 509 goto_locus = locus; 510 } 511 } 512 } 513 } 514 515 /* Allow to thread only over one edge at time to simplify updating 516 of probabilities. */ 517 else if ((mode & CLEANUP_THREADING) && may_thread) 518 { 519 edge t = thread_jump (e, target); 520 if (t) 521 { 522 if (!threaded_edges) 523 threaded_edges = XNEWVEC (edge, n_basic_blocks); 524 else 525 { 526 int i; 527 528 /* Detect an infinite loop across blocks not 529 including the start block. */ 530 for (i = 0; i < nthreaded_edges; ++i) 531 if (threaded_edges[i] == t) 532 break; 533 if (i < nthreaded_edges) 534 { 535 counter = n_basic_blocks; 536 break; 537 } 538 } 539 540 /* Detect an infinite loop across the start block. */ 541 if (t->dest == b) 542 break; 543 544 gcc_assert (nthreaded_edges < n_basic_blocks - NUM_FIXED_BLOCKS); 545 threaded_edges[nthreaded_edges++] = t; 546 547 new_target = t->dest; 548 new_target_threaded = true; 549 } 550 } 551 552 if (!new_target) 553 break; 554 555 counter++; 556 target = new_target; 557 threaded |= new_target_threaded; 558 } 559 560 if (counter >= n_basic_blocks) 561 { 562 if (dump_file) 563 fprintf (dump_file, "Infinite loop in BB %i.\n", 564 target->index); 565 } 566 else if (target == first) 567 ; /* We didn't do anything. */ 568 else 569 { 570 /* Save the values now, as the edge may get removed. */ 571 gcov_type edge_count = e->count; 572 int edge_probability = e->probability; 573 int edge_frequency; 574 int n = 0; 575 576 e->goto_locus = goto_locus; 577 578 /* Don't force if target is exit block. */ 579 if (threaded && target != EXIT_BLOCK_PTR) 580 { 581 notice_new_block (redirect_edge_and_branch_force (e, target)); 582 if (dump_file) 583 fprintf (dump_file, "Conditionals threaded.\n"); 584 } 585 else if (!redirect_edge_and_branch (e, target)) 586 { 587 if (dump_file) 588 fprintf (dump_file, 589 "Forwarding edge %i->%i to %i failed.\n", 590 b->index, e->dest->index, target->index); 591 ei_next (&ei); 592 continue; 593 } 594 595 /* We successfully forwarded the edge. Now update profile 596 data: for each edge we traversed in the chain, remove 597 the original edge's execution count. */ 598 edge_frequency = ((edge_probability * b->frequency 599 + REG_BR_PROB_BASE / 2) 600 / REG_BR_PROB_BASE); 601 602 do 603 { 604 edge t; 605 606 if (!single_succ_p (first)) 607 { 608 gcc_assert (n < nthreaded_edges); 609 t = threaded_edges [n++]; 610 gcc_assert (t->src == first); 611 update_bb_profile_for_threading (first, edge_frequency, 612 edge_count, t); 613 update_br_prob_note (first); 614 } 615 else 616 { 617 first->count -= edge_count; 618 if (first->count < 0) 619 first->count = 0; 620 first->frequency -= edge_frequency; 621 if (first->frequency < 0) 622 first->frequency = 0; 623 /* It is possible that as the result of 624 threading we've removed edge as it is 625 threaded to the fallthru edge. Avoid 626 getting out of sync. */ 627 if (n < nthreaded_edges 628 && first == threaded_edges [n]->src) 629 n++; 630 t = single_succ_edge (first); 631 } 632 633 t->count -= edge_count; 634 if (t->count < 0) 635 t->count = 0; 636 first = t->dest; 637 } 638 while (first != target); 639 640 changed = true; 641 continue; 642 } 643 ei_next (&ei); 644 } 645 646 free (threaded_edges); 647 return changed; 648 } 649 650 651 /* Blocks A and B are to be merged into a single block. A has no incoming 652 fallthru edge, so it can be moved before B without adding or modifying 653 any jumps (aside from the jump from A to B). */ 654 655 static void 656 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b) 657 { 658 rtx barrier; 659 660 /* If we are partitioning hot/cold basic blocks, we don't want to 661 mess up unconditional or indirect jumps that cross between hot 662 and cold sections. 663 664 Basic block partitioning may result in some jumps that appear to 665 be optimizable (or blocks that appear to be mergeable), but which really 666 must be left untouched (they are required to make it safely across 667 partition boundaries). See the comments at the top of 668 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 669 670 if (BB_PARTITION (a) != BB_PARTITION (b)) 671 return; 672 673 barrier = next_nonnote_insn (BB_END (a)); 674 gcc_assert (BARRIER_P (barrier)); 675 delete_insn (barrier); 676 677 /* Scramble the insn chain. */ 678 if (BB_END (a) != PREV_INSN (BB_HEAD (b))) 679 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b))); 680 df_set_bb_dirty (a); 681 682 if (dump_file) 683 fprintf (dump_file, "Moved block %d before %d and merged.\n", 684 a->index, b->index); 685 686 /* Swap the records for the two blocks around. */ 687 688 unlink_block (a); 689 link_block (a, b->prev_bb); 690 691 /* Now blocks A and B are contiguous. Merge them. */ 692 merge_blocks (a, b); 693 } 694 695 /* Blocks A and B are to be merged into a single block. B has no outgoing 696 fallthru edge, so it can be moved after A without adding or modifying 697 any jumps (aside from the jump from A to B). */ 698 699 static void 700 merge_blocks_move_successor_nojumps (basic_block a, basic_block b) 701 { 702 rtx barrier, real_b_end; 703 rtx label, table; 704 705 /* If we are partitioning hot/cold basic blocks, we don't want to 706 mess up unconditional or indirect jumps that cross between hot 707 and cold sections. 708 709 Basic block partitioning may result in some jumps that appear to 710 be optimizable (or blocks that appear to be mergeable), but which really 711 must be left untouched (they are required to make it safely across 712 partition boundaries). See the comments at the top of 713 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 714 715 if (BB_PARTITION (a) != BB_PARTITION (b)) 716 return; 717 718 real_b_end = BB_END (b); 719 720 /* If there is a jump table following block B temporarily add the jump table 721 to block B so that it will also be moved to the correct location. */ 722 if (tablejump_p (BB_END (b), &label, &table) 723 && prev_active_insn (label) == BB_END (b)) 724 { 725 BB_END (b) = table; 726 } 727 728 /* There had better have been a barrier there. Delete it. */ 729 barrier = NEXT_INSN (BB_END (b)); 730 if (barrier && BARRIER_P (barrier)) 731 delete_insn (barrier); 732 733 734 /* Scramble the insn chain. */ 735 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a)); 736 737 /* Restore the real end of b. */ 738 BB_END (b) = real_b_end; 739 740 if (dump_file) 741 fprintf (dump_file, "Moved block %d after %d and merged.\n", 742 b->index, a->index); 743 744 /* Now blocks A and B are contiguous. Merge them. */ 745 merge_blocks (a, b); 746 } 747 748 /* Attempt to merge basic blocks that are potentially non-adjacent. 749 Return NULL iff the attempt failed, otherwise return basic block 750 where cleanup_cfg should continue. Because the merging commonly 751 moves basic block away or introduces another optimization 752 possibility, return basic block just before B so cleanup_cfg don't 753 need to iterate. 754 755 It may be good idea to return basic block before C in the case 756 C has been moved after B and originally appeared earlier in the 757 insn sequence, but we have no information available about the 758 relative ordering of these two. Hopefully it is not too common. */ 759 760 static basic_block 761 merge_blocks_move (edge e, basic_block b, basic_block c, int mode) 762 { 763 basic_block next; 764 765 /* If we are partitioning hot/cold basic blocks, we don't want to 766 mess up unconditional or indirect jumps that cross between hot 767 and cold sections. 768 769 Basic block partitioning may result in some jumps that appear to 770 be optimizable (or blocks that appear to be mergeable), but which really 771 must be left untouched (they are required to make it safely across 772 partition boundaries). See the comments at the top of 773 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 774 775 if (BB_PARTITION (b) != BB_PARTITION (c)) 776 return NULL; 777 778 /* If B has a fallthru edge to C, no need to move anything. */ 779 if (e->flags & EDGE_FALLTHRU) 780 { 781 int b_index = b->index, c_index = c->index; 782 merge_blocks (b, c); 783 update_forwarder_flag (b); 784 785 if (dump_file) 786 fprintf (dump_file, "Merged %d and %d without moving.\n", 787 b_index, c_index); 788 789 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb; 790 } 791 792 /* Otherwise we will need to move code around. Do that only if expensive 793 transformations are allowed. */ 794 else if (mode & CLEANUP_EXPENSIVE) 795 { 796 edge tmp_edge, b_fallthru_edge; 797 bool c_has_outgoing_fallthru; 798 bool b_has_incoming_fallthru; 799 800 /* Avoid overactive code motion, as the forwarder blocks should be 801 eliminated by edge redirection instead. One exception might have 802 been if B is a forwarder block and C has no fallthru edge, but 803 that should be cleaned up by bb-reorder instead. */ 804 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c)) 805 return NULL; 806 807 /* We must make sure to not munge nesting of lexical blocks, 808 and loop notes. This is done by squeezing out all the notes 809 and leaving them there to lie. Not ideal, but functional. */ 810 811 tmp_edge = find_fallthru_edge (c->succs); 812 c_has_outgoing_fallthru = (tmp_edge != NULL); 813 814 tmp_edge = find_fallthru_edge (b->preds); 815 b_has_incoming_fallthru = (tmp_edge != NULL); 816 b_fallthru_edge = tmp_edge; 817 next = b->prev_bb; 818 if (next == c) 819 next = next->prev_bb; 820 821 /* Otherwise, we're going to try to move C after B. If C does 822 not have an outgoing fallthru, then it can be moved 823 immediately after B without introducing or modifying jumps. */ 824 if (! c_has_outgoing_fallthru) 825 { 826 merge_blocks_move_successor_nojumps (b, c); 827 return next == ENTRY_BLOCK_PTR ? next->next_bb : next; 828 } 829 830 /* If B does not have an incoming fallthru, then it can be moved 831 immediately before C without introducing or modifying jumps. 832 C cannot be the first block, so we do not have to worry about 833 accessing a non-existent block. */ 834 835 if (b_has_incoming_fallthru) 836 { 837 basic_block bb; 838 839 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR) 840 return NULL; 841 bb = force_nonfallthru (b_fallthru_edge); 842 if (bb) 843 notice_new_block (bb); 844 } 845 846 merge_blocks_move_predecessor_nojumps (b, c); 847 return next == ENTRY_BLOCK_PTR ? next->next_bb : next; 848 } 849 850 return NULL; 851 } 852 853 854 /* Removes the memory attributes of MEM expression 855 if they are not equal. */ 856 857 void 858 merge_memattrs (rtx x, rtx y) 859 { 860 int i; 861 int j; 862 enum rtx_code code; 863 const char *fmt; 864 865 if (x == y) 866 return; 867 if (x == 0 || y == 0) 868 return; 869 870 code = GET_CODE (x); 871 872 if (code != GET_CODE (y)) 873 return; 874 875 if (GET_MODE (x) != GET_MODE (y)) 876 return; 877 878 if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y)) 879 { 880 if (! MEM_ATTRS (x)) 881 MEM_ATTRS (y) = 0; 882 else if (! MEM_ATTRS (y)) 883 MEM_ATTRS (x) = 0; 884 else 885 { 886 HOST_WIDE_INT mem_size; 887 888 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y)) 889 { 890 set_mem_alias_set (x, 0); 891 set_mem_alias_set (y, 0); 892 } 893 894 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y))) 895 { 896 set_mem_expr (x, 0); 897 set_mem_expr (y, 0); 898 clear_mem_offset (x); 899 clear_mem_offset (y); 900 } 901 else if (MEM_OFFSET_KNOWN_P (x) != MEM_OFFSET_KNOWN_P (y) 902 || (MEM_OFFSET_KNOWN_P (x) 903 && MEM_OFFSET (x) != MEM_OFFSET (y))) 904 { 905 clear_mem_offset (x); 906 clear_mem_offset (y); 907 } 908 909 if (MEM_SIZE_KNOWN_P (x) && MEM_SIZE_KNOWN_P (y)) 910 { 911 mem_size = MAX (MEM_SIZE (x), MEM_SIZE (y)); 912 set_mem_size (x, mem_size); 913 set_mem_size (y, mem_size); 914 } 915 else 916 { 917 clear_mem_size (x); 918 clear_mem_size (y); 919 } 920 921 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y))); 922 set_mem_align (y, MEM_ALIGN (x)); 923 } 924 } 925 if (code == MEM) 926 { 927 if (MEM_READONLY_P (x) != MEM_READONLY_P (y)) 928 { 929 MEM_READONLY_P (x) = 0; 930 MEM_READONLY_P (y) = 0; 931 } 932 if (MEM_NOTRAP_P (x) != MEM_NOTRAP_P (y)) 933 { 934 MEM_NOTRAP_P (x) = 0; 935 MEM_NOTRAP_P (y) = 0; 936 } 937 if (MEM_VOLATILE_P (x) != MEM_VOLATILE_P (y)) 938 { 939 MEM_VOLATILE_P (x) = 1; 940 MEM_VOLATILE_P (y) = 1; 941 } 942 } 943 944 fmt = GET_RTX_FORMAT (code); 945 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 946 { 947 switch (fmt[i]) 948 { 949 case 'E': 950 /* Two vectors must have the same length. */ 951 if (XVECLEN (x, i) != XVECLEN (y, i)) 952 return; 953 954 for (j = 0; j < XVECLEN (x, i); j++) 955 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j)); 956 957 break; 958 959 case 'e': 960 merge_memattrs (XEXP (x, i), XEXP (y, i)); 961 } 962 } 963 return; 964 } 965 966 967 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly 968 different single sets S1 and S2. */ 969 970 static bool 971 equal_different_set_p (rtx p1, rtx s1, rtx p2, rtx s2) 972 { 973 int i; 974 rtx e1, e2; 975 976 if (p1 == s1 && p2 == s2) 977 return true; 978 979 if (GET_CODE (p1) != PARALLEL || GET_CODE (p2) != PARALLEL) 980 return false; 981 982 if (XVECLEN (p1, 0) != XVECLEN (p2, 0)) 983 return false; 984 985 for (i = 0; i < XVECLEN (p1, 0); i++) 986 { 987 e1 = XVECEXP (p1, 0, i); 988 e2 = XVECEXP (p2, 0, i); 989 if (e1 == s1 && e2 == s2) 990 continue; 991 if (reload_completed 992 ? rtx_renumbered_equal_p (e1, e2) : rtx_equal_p (e1, e2)) 993 continue; 994 995 return false; 996 } 997 998 return true; 999 } 1000 1001 /* Examine register notes on I1 and I2 and return: 1002 - dir_forward if I1 can be replaced by I2, or 1003 - dir_backward if I2 can be replaced by I1, or 1004 - dir_both if both are the case. */ 1005 1006 static enum replace_direction 1007 can_replace_by (rtx i1, rtx i2) 1008 { 1009 rtx s1, s2, d1, d2, src1, src2, note1, note2; 1010 bool c1, c2; 1011 1012 /* Check for 2 sets. */ 1013 s1 = single_set (i1); 1014 s2 = single_set (i2); 1015 if (s1 == NULL_RTX || s2 == NULL_RTX) 1016 return dir_none; 1017 1018 /* Check that the 2 sets set the same dest. */ 1019 d1 = SET_DEST (s1); 1020 d2 = SET_DEST (s2); 1021 if (!(reload_completed 1022 ? rtx_renumbered_equal_p (d1, d2) : rtx_equal_p (d1, d2))) 1023 return dir_none; 1024 1025 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets 1026 set dest to the same value. */ 1027 note1 = find_reg_equal_equiv_note (i1); 1028 note2 = find_reg_equal_equiv_note (i2); 1029 if (!note1 || !note2 || !rtx_equal_p (XEXP (note1, 0), XEXP (note2, 0)) 1030 || !CONST_INT_P (XEXP (note1, 0))) 1031 return dir_none; 1032 1033 if (!equal_different_set_p (PATTERN (i1), s1, PATTERN (i2), s2)) 1034 return dir_none; 1035 1036 /* Although the 2 sets set dest to the same value, we cannot replace 1037 (set (dest) (const_int)) 1038 by 1039 (set (dest) (reg)) 1040 because we don't know if the reg is live and has the same value at the 1041 location of replacement. */ 1042 src1 = SET_SRC (s1); 1043 src2 = SET_SRC (s2); 1044 c1 = CONST_INT_P (src1); 1045 c2 = CONST_INT_P (src2); 1046 if (c1 && c2) 1047 return dir_both; 1048 else if (c2) 1049 return dir_forward; 1050 else if (c1) 1051 return dir_backward; 1052 1053 return dir_none; 1054 } 1055 1056 /* Merges directions A and B. */ 1057 1058 static enum replace_direction 1059 merge_dir (enum replace_direction a, enum replace_direction b) 1060 { 1061 /* Implements the following table: 1062 |bo fw bw no 1063 ---+----------- 1064 bo |bo fw bw no 1065 fw |-- fw no no 1066 bw |-- -- bw no 1067 no |-- -- -- no. */ 1068 1069 if (a == b) 1070 return a; 1071 1072 if (a == dir_both) 1073 return b; 1074 if (b == dir_both) 1075 return a; 1076 1077 return dir_none; 1078 } 1079 1080 /* Examine I1 and I2 and return: 1081 - dir_forward if I1 can be replaced by I2, or 1082 - dir_backward if I2 can be replaced by I1, or 1083 - dir_both if both are the case. */ 1084 1085 static enum replace_direction 1086 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2) 1087 { 1088 rtx p1, p2; 1089 1090 /* Verify that I1 and I2 are equivalent. */ 1091 if (GET_CODE (i1) != GET_CODE (i2)) 1092 return dir_none; 1093 1094 /* __builtin_unreachable() may lead to empty blocks (ending with 1095 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */ 1096 if (NOTE_INSN_BASIC_BLOCK_P (i1) && NOTE_INSN_BASIC_BLOCK_P (i2)) 1097 return dir_both; 1098 1099 /* ??? Do not allow cross-jumping between different stack levels. */ 1100 p1 = find_reg_note (i1, REG_ARGS_SIZE, NULL); 1101 p2 = find_reg_note (i2, REG_ARGS_SIZE, NULL); 1102 if (p1 && p2) 1103 { 1104 p1 = XEXP (p1, 0); 1105 p2 = XEXP (p2, 0); 1106 if (!rtx_equal_p (p1, p2)) 1107 return dir_none; 1108 1109 /* ??? Worse, this adjustment had better be constant lest we 1110 have differing incoming stack levels. */ 1111 if (!frame_pointer_needed 1112 && find_args_size_adjust (i1) == HOST_WIDE_INT_MIN) 1113 return dir_none; 1114 } 1115 else if (p1 || p2) 1116 return dir_none; 1117 1118 p1 = PATTERN (i1); 1119 p2 = PATTERN (i2); 1120 1121 if (GET_CODE (p1) != GET_CODE (p2)) 1122 return dir_none; 1123 1124 /* If this is a CALL_INSN, compare register usage information. 1125 If we don't check this on stack register machines, the two 1126 CALL_INSNs might be merged leaving reg-stack.c with mismatching 1127 numbers of stack registers in the same basic block. 1128 If we don't check this on machines with delay slots, a delay slot may 1129 be filled that clobbers a parameter expected by the subroutine. 1130 1131 ??? We take the simple route for now and assume that if they're 1132 equal, they were constructed identically. 1133 1134 Also check for identical exception regions. */ 1135 1136 if (CALL_P (i1)) 1137 { 1138 /* Ensure the same EH region. */ 1139 rtx n1 = find_reg_note (i1, REG_EH_REGION, 0); 1140 rtx n2 = find_reg_note (i2, REG_EH_REGION, 0); 1141 1142 if (!n1 && n2) 1143 return dir_none; 1144 1145 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0))) 1146 return dir_none; 1147 1148 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1), 1149 CALL_INSN_FUNCTION_USAGE (i2)) 1150 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)) 1151 return dir_none; 1152 } 1153 1154 #ifdef STACK_REGS 1155 /* If cross_jump_death_matters is not 0, the insn's mode 1156 indicates whether or not the insn contains any stack-like 1157 regs. */ 1158 1159 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1)) 1160 { 1161 /* If register stack conversion has already been done, then 1162 death notes must also be compared before it is certain that 1163 the two instruction streams match. */ 1164 1165 rtx note; 1166 HARD_REG_SET i1_regset, i2_regset; 1167 1168 CLEAR_HARD_REG_SET (i1_regset); 1169 CLEAR_HARD_REG_SET (i2_regset); 1170 1171 for (note = REG_NOTES (i1); note; note = XEXP (note, 1)) 1172 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0))) 1173 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0))); 1174 1175 for (note = REG_NOTES (i2); note; note = XEXP (note, 1)) 1176 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0))) 1177 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0))); 1178 1179 if (!hard_reg_set_equal_p (i1_regset, i2_regset)) 1180 return dir_none; 1181 } 1182 #endif 1183 1184 if (reload_completed 1185 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2)) 1186 return dir_both; 1187 1188 return can_replace_by (i1, i2); 1189 } 1190 1191 /* When comparing insns I1 and I2 in flow_find_cross_jump or 1192 flow_find_head_matching_sequence, ensure the notes match. */ 1193 1194 static void 1195 merge_notes (rtx i1, rtx i2) 1196 { 1197 /* If the merged insns have different REG_EQUAL notes, then 1198 remove them. */ 1199 rtx equiv1 = find_reg_equal_equiv_note (i1); 1200 rtx equiv2 = find_reg_equal_equiv_note (i2); 1201 1202 if (equiv1 && !equiv2) 1203 remove_note (i1, equiv1); 1204 else if (!equiv1 && equiv2) 1205 remove_note (i2, equiv2); 1206 else if (equiv1 && equiv2 1207 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0))) 1208 { 1209 remove_note (i1, equiv1); 1210 remove_note (i2, equiv2); 1211 } 1212 } 1213 1214 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the 1215 resulting insn in I1, and the corresponding bb in BB1. At the head of a 1216 bb, if there is a predecessor bb that reaches this bb via fallthru, and 1217 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in 1218 DID_FALLTHRU. Otherwise, stops at the head of the bb. */ 1219 1220 static void 1221 walk_to_nondebug_insn (rtx *i1, basic_block *bb1, bool follow_fallthru, 1222 bool *did_fallthru) 1223 { 1224 edge fallthru; 1225 1226 *did_fallthru = false; 1227 1228 /* Ignore notes. */ 1229 while (!NONDEBUG_INSN_P (*i1)) 1230 { 1231 if (*i1 != BB_HEAD (*bb1)) 1232 { 1233 *i1 = PREV_INSN (*i1); 1234 continue; 1235 } 1236 1237 if (!follow_fallthru) 1238 return; 1239 1240 fallthru = find_fallthru_edge ((*bb1)->preds); 1241 if (!fallthru || fallthru->src == ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun) 1242 || !single_succ_p (fallthru->src)) 1243 return; 1244 1245 *bb1 = fallthru->src; 1246 *i1 = BB_END (*bb1); 1247 *did_fallthru = true; 1248 } 1249 } 1250 1251 /* Look through the insns at the end of BB1 and BB2 and find the longest 1252 sequence that are either equivalent, or allow forward or backward 1253 replacement. Store the first insns for that sequence in *F1 and *F2 and 1254 return the sequence length. 1255 1256 DIR_P indicates the allowed replacement direction on function entry, and 1257 the actual replacement direction on function exit. If NULL, only equivalent 1258 sequences are allowed. 1259 1260 To simplify callers of this function, if the blocks match exactly, 1261 store the head of the blocks in *F1 and *F2. */ 1262 1263 int 1264 flow_find_cross_jump (basic_block bb1, basic_block bb2, rtx *f1, rtx *f2, 1265 enum replace_direction *dir_p) 1266 { 1267 rtx i1, i2, last1, last2, afterlast1, afterlast2; 1268 int ninsns = 0; 1269 rtx p1; 1270 enum replace_direction dir, last_dir, afterlast_dir; 1271 bool follow_fallthru, did_fallthru; 1272 1273 if (dir_p) 1274 dir = *dir_p; 1275 else 1276 dir = dir_both; 1277 afterlast_dir = dir; 1278 last_dir = afterlast_dir; 1279 1280 /* Skip simple jumps at the end of the blocks. Complex jumps still 1281 need to be compared for equivalence, which we'll do below. */ 1282 1283 i1 = BB_END (bb1); 1284 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX; 1285 if (onlyjump_p (i1) 1286 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1)))) 1287 { 1288 last1 = i1; 1289 i1 = PREV_INSN (i1); 1290 } 1291 1292 i2 = BB_END (bb2); 1293 if (onlyjump_p (i2) 1294 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2)))) 1295 { 1296 last2 = i2; 1297 /* Count everything except for unconditional jump as insn. */ 1298 if (!simplejump_p (i2) && !returnjump_p (i2) && last1) 1299 ninsns++; 1300 i2 = PREV_INSN (i2); 1301 } 1302 1303 while (true) 1304 { 1305 /* In the following example, we can replace all jumps to C by jumps to A. 1306 1307 This removes 4 duplicate insns. 1308 [bb A] insn1 [bb C] insn1 1309 insn2 insn2 1310 [bb B] insn3 insn3 1311 insn4 insn4 1312 jump_insn jump_insn 1313 1314 We could also replace all jumps to A by jumps to C, but that leaves B 1315 alive, and removes only 2 duplicate insns. In a subsequent crossjump 1316 step, all jumps to B would be replaced with jumps to the middle of C, 1317 achieving the same result with more effort. 1318 So we allow only the first possibility, which means that we don't allow 1319 fallthru in the block that's being replaced. */ 1320 1321 follow_fallthru = dir_p && dir != dir_forward; 1322 walk_to_nondebug_insn (&i1, &bb1, follow_fallthru, &did_fallthru); 1323 if (did_fallthru) 1324 dir = dir_backward; 1325 1326 follow_fallthru = dir_p && dir != dir_backward; 1327 walk_to_nondebug_insn (&i2, &bb2, follow_fallthru, &did_fallthru); 1328 if (did_fallthru) 1329 dir = dir_forward; 1330 1331 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2)) 1332 break; 1333 1334 dir = merge_dir (dir, old_insns_match_p (0, i1, i2)); 1335 if (dir == dir_none || (!dir_p && dir != dir_both)) 1336 break; 1337 1338 merge_memattrs (i1, i2); 1339 1340 /* Don't begin a cross-jump with a NOTE insn. */ 1341 if (INSN_P (i1)) 1342 { 1343 merge_notes (i1, i2); 1344 1345 afterlast1 = last1, afterlast2 = last2; 1346 last1 = i1, last2 = i2; 1347 afterlast_dir = last_dir; 1348 last_dir = dir; 1349 p1 = PATTERN (i1); 1350 if (!(GET_CODE (p1) == USE || GET_CODE (p1) == CLOBBER)) 1351 ninsns++; 1352 } 1353 1354 i1 = PREV_INSN (i1); 1355 i2 = PREV_INSN (i2); 1356 } 1357 1358 #ifdef HAVE_cc0 1359 /* Don't allow the insn after a compare to be shared by 1360 cross-jumping unless the compare is also shared. */ 1361 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1)) 1362 last1 = afterlast1, last2 = afterlast2, last_dir = afterlast_dir, ninsns--; 1363 #endif 1364 1365 /* Include preceding notes and labels in the cross-jump. One, 1366 this may bring us to the head of the blocks as requested above. 1367 Two, it keeps line number notes as matched as may be. */ 1368 if (ninsns) 1369 { 1370 bb1 = BLOCK_FOR_INSN (last1); 1371 while (last1 != BB_HEAD (bb1) && !NONDEBUG_INSN_P (PREV_INSN (last1))) 1372 last1 = PREV_INSN (last1); 1373 1374 if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1))) 1375 last1 = PREV_INSN (last1); 1376 1377 bb2 = BLOCK_FOR_INSN (last2); 1378 while (last2 != BB_HEAD (bb2) && !NONDEBUG_INSN_P (PREV_INSN (last2))) 1379 last2 = PREV_INSN (last2); 1380 1381 if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2))) 1382 last2 = PREV_INSN (last2); 1383 1384 *f1 = last1; 1385 *f2 = last2; 1386 } 1387 1388 if (dir_p) 1389 *dir_p = last_dir; 1390 return ninsns; 1391 } 1392 1393 /* Like flow_find_cross_jump, except start looking for a matching sequence from 1394 the head of the two blocks. Do not include jumps at the end. 1395 If STOP_AFTER is nonzero, stop after finding that many matching 1396 instructions. */ 1397 1398 int 1399 flow_find_head_matching_sequence (basic_block bb1, basic_block bb2, rtx *f1, 1400 rtx *f2, int stop_after) 1401 { 1402 rtx i1, i2, last1, last2, beforelast1, beforelast2; 1403 int ninsns = 0; 1404 edge e; 1405 edge_iterator ei; 1406 int nehedges1 = 0, nehedges2 = 0; 1407 1408 FOR_EACH_EDGE (e, ei, bb1->succs) 1409 if (e->flags & EDGE_EH) 1410 nehedges1++; 1411 FOR_EACH_EDGE (e, ei, bb2->succs) 1412 if (e->flags & EDGE_EH) 1413 nehedges2++; 1414 1415 i1 = BB_HEAD (bb1); 1416 i2 = BB_HEAD (bb2); 1417 last1 = beforelast1 = last2 = beforelast2 = NULL_RTX; 1418 1419 while (true) 1420 { 1421 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */ 1422 while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1)) 1423 { 1424 if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG) 1425 break; 1426 i1 = NEXT_INSN (i1); 1427 } 1428 1429 while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2)) 1430 { 1431 if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG) 1432 break; 1433 i2 = NEXT_INSN (i2); 1434 } 1435 1436 if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1)) 1437 || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2))) 1438 break; 1439 1440 if (NOTE_P (i1) || NOTE_P (i2) 1441 || JUMP_P (i1) || JUMP_P (i2)) 1442 break; 1443 1444 /* A sanity check to make sure we're not merging insns with different 1445 effects on EH. If only one of them ends a basic block, it shouldn't 1446 have an EH edge; if both end a basic block, there should be the same 1447 number of EH edges. */ 1448 if ((i1 == BB_END (bb1) && i2 != BB_END (bb2) 1449 && nehedges1 > 0) 1450 || (i2 == BB_END (bb2) && i1 != BB_END (bb1) 1451 && nehedges2 > 0) 1452 || (i1 == BB_END (bb1) && i2 == BB_END (bb2) 1453 && nehedges1 != nehedges2)) 1454 break; 1455 1456 if (old_insns_match_p (0, i1, i2) != dir_both) 1457 break; 1458 1459 merge_memattrs (i1, i2); 1460 1461 /* Don't begin a cross-jump with a NOTE insn. */ 1462 if (INSN_P (i1)) 1463 { 1464 merge_notes (i1, i2); 1465 1466 beforelast1 = last1, beforelast2 = last2; 1467 last1 = i1, last2 = i2; 1468 ninsns++; 1469 } 1470 1471 if (i1 == BB_END (bb1) || i2 == BB_END (bb2) 1472 || (stop_after > 0 && ninsns == stop_after)) 1473 break; 1474 1475 i1 = NEXT_INSN (i1); 1476 i2 = NEXT_INSN (i2); 1477 } 1478 1479 #ifdef HAVE_cc0 1480 /* Don't allow a compare to be shared by cross-jumping unless the insn 1481 after the compare is also shared. */ 1482 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && sets_cc0_p (last1)) 1483 last1 = beforelast1, last2 = beforelast2, ninsns--; 1484 #endif 1485 1486 if (ninsns) 1487 { 1488 *f1 = last1; 1489 *f2 = last2; 1490 } 1491 1492 return ninsns; 1493 } 1494 1495 /* Return true iff outgoing edges of BB1 and BB2 match, together with 1496 the branch instruction. This means that if we commonize the control 1497 flow before end of the basic block, the semantic remains unchanged. 1498 1499 We may assume that there exists one edge with a common destination. */ 1500 1501 static bool 1502 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2) 1503 { 1504 int nehedges1 = 0, nehedges2 = 0; 1505 edge fallthru1 = 0, fallthru2 = 0; 1506 edge e1, e2; 1507 edge_iterator ei; 1508 rtx last1, last2; 1509 bool nonfakeedges; 1510 1511 /* If we performed shrink-wrapping, edges to the EXIT_BLOCK_PTR can 1512 only be distinguished for JUMP_INSNs. The two paths may differ in 1513 whether they went through the prologue. Sibcalls are fine, we know 1514 that we either didn't need or inserted an epilogue before them. */ 1515 if (crtl->shrink_wrapped 1516 && single_succ_p (bb1) && single_succ (bb1) == EXIT_BLOCK_PTR 1517 && !JUMP_P (BB_END (bb1)) 1518 && !(CALL_P (BB_END (bb1)) && SIBLING_CALL_P (BB_END (bb1)))) 1519 return false; 1520 1521 /* If BB1 has only one successor, we may be looking at either an 1522 unconditional jump, or a fake edge to exit. */ 1523 if (single_succ_p (bb1) 1524 && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0 1525 && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1)))) 1526 return (single_succ_p (bb2) 1527 && (single_succ_edge (bb2)->flags 1528 & (EDGE_COMPLEX | EDGE_FAKE)) == 0 1529 && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2)))); 1530 1531 /* Match conditional jumps - this may get tricky when fallthru and branch 1532 edges are crossed. */ 1533 if (EDGE_COUNT (bb1->succs) == 2 1534 && any_condjump_p (BB_END (bb1)) 1535 && onlyjump_p (BB_END (bb1))) 1536 { 1537 edge b1, f1, b2, f2; 1538 bool reverse, match; 1539 rtx set1, set2, cond1, cond2; 1540 enum rtx_code code1, code2; 1541 1542 if (EDGE_COUNT (bb2->succs) != 2 1543 || !any_condjump_p (BB_END (bb2)) 1544 || !onlyjump_p (BB_END (bb2))) 1545 return false; 1546 1547 b1 = BRANCH_EDGE (bb1); 1548 b2 = BRANCH_EDGE (bb2); 1549 f1 = FALLTHRU_EDGE (bb1); 1550 f2 = FALLTHRU_EDGE (bb2); 1551 1552 /* Get around possible forwarders on fallthru edges. Other cases 1553 should be optimized out already. */ 1554 if (FORWARDER_BLOCK_P (f1->dest)) 1555 f1 = single_succ_edge (f1->dest); 1556 1557 if (FORWARDER_BLOCK_P (f2->dest)) 1558 f2 = single_succ_edge (f2->dest); 1559 1560 /* To simplify use of this function, return false if there are 1561 unneeded forwarder blocks. These will get eliminated later 1562 during cleanup_cfg. */ 1563 if (FORWARDER_BLOCK_P (f1->dest) 1564 || FORWARDER_BLOCK_P (f2->dest) 1565 || FORWARDER_BLOCK_P (b1->dest) 1566 || FORWARDER_BLOCK_P (b2->dest)) 1567 return false; 1568 1569 if (f1->dest == f2->dest && b1->dest == b2->dest) 1570 reverse = false; 1571 else if (f1->dest == b2->dest && b1->dest == f2->dest) 1572 reverse = true; 1573 else 1574 return false; 1575 1576 set1 = pc_set (BB_END (bb1)); 1577 set2 = pc_set (BB_END (bb2)); 1578 if ((XEXP (SET_SRC (set1), 1) == pc_rtx) 1579 != (XEXP (SET_SRC (set2), 1) == pc_rtx)) 1580 reverse = !reverse; 1581 1582 cond1 = XEXP (SET_SRC (set1), 0); 1583 cond2 = XEXP (SET_SRC (set2), 0); 1584 code1 = GET_CODE (cond1); 1585 if (reverse) 1586 code2 = reversed_comparison_code (cond2, BB_END (bb2)); 1587 else 1588 code2 = GET_CODE (cond2); 1589 1590 if (code2 == UNKNOWN) 1591 return false; 1592 1593 /* Verify codes and operands match. */ 1594 match = ((code1 == code2 1595 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0)) 1596 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1))) 1597 || (code1 == swap_condition (code2) 1598 && rtx_renumbered_equal_p (XEXP (cond1, 1), 1599 XEXP (cond2, 0)) 1600 && rtx_renumbered_equal_p (XEXP (cond1, 0), 1601 XEXP (cond2, 1)))); 1602 1603 /* If we return true, we will join the blocks. Which means that 1604 we will only have one branch prediction bit to work with. Thus 1605 we require the existing branches to have probabilities that are 1606 roughly similar. */ 1607 if (match 1608 && optimize_bb_for_speed_p (bb1) 1609 && optimize_bb_for_speed_p (bb2)) 1610 { 1611 int prob2; 1612 1613 if (b1->dest == b2->dest) 1614 prob2 = b2->probability; 1615 else 1616 /* Do not use f2 probability as f2 may be forwarded. */ 1617 prob2 = REG_BR_PROB_BASE - b2->probability; 1618 1619 /* Fail if the difference in probabilities is greater than 50%. 1620 This rules out two well-predicted branches with opposite 1621 outcomes. */ 1622 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2) 1623 { 1624 if (dump_file) 1625 fprintf (dump_file, 1626 "Outcomes of branch in bb %i and %i differ too much (%i %i)\n", 1627 bb1->index, bb2->index, b1->probability, prob2); 1628 1629 return false; 1630 } 1631 } 1632 1633 if (dump_file && match) 1634 fprintf (dump_file, "Conditionals in bb %i and %i match.\n", 1635 bb1->index, bb2->index); 1636 1637 return match; 1638 } 1639 1640 /* Generic case - we are seeing a computed jump, table jump or trapping 1641 instruction. */ 1642 1643 /* Check whether there are tablejumps in the end of BB1 and BB2. 1644 Return true if they are identical. */ 1645 { 1646 rtx label1, label2; 1647 rtx table1, table2; 1648 1649 if (tablejump_p (BB_END (bb1), &label1, &table1) 1650 && tablejump_p (BB_END (bb2), &label2, &table2) 1651 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2))) 1652 { 1653 /* The labels should never be the same rtx. If they really are same 1654 the jump tables are same too. So disable crossjumping of blocks BB1 1655 and BB2 because when deleting the common insns in the end of BB1 1656 by delete_basic_block () the jump table would be deleted too. */ 1657 /* If LABEL2 is referenced in BB1->END do not do anything 1658 because we would loose information when replacing 1659 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */ 1660 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1))) 1661 { 1662 /* Set IDENTICAL to true when the tables are identical. */ 1663 bool identical = false; 1664 rtx p1, p2; 1665 1666 p1 = PATTERN (table1); 1667 p2 = PATTERN (table2); 1668 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2)) 1669 { 1670 identical = true; 1671 } 1672 else if (GET_CODE (p1) == ADDR_DIFF_VEC 1673 && (XVECLEN (p1, 1) == XVECLEN (p2, 1)) 1674 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2)) 1675 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3))) 1676 { 1677 int i; 1678 1679 identical = true; 1680 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--) 1681 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i))) 1682 identical = false; 1683 } 1684 1685 if (identical) 1686 { 1687 replace_label_data rr; 1688 bool match; 1689 1690 /* Temporarily replace references to LABEL1 with LABEL2 1691 in BB1->END so that we could compare the instructions. */ 1692 rr.r1 = label1; 1693 rr.r2 = label2; 1694 rr.update_label_nuses = false; 1695 for_each_rtx (&BB_END (bb1), replace_label, &rr); 1696 1697 match = (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)) 1698 == dir_both); 1699 if (dump_file && match) 1700 fprintf (dump_file, 1701 "Tablejumps in bb %i and %i match.\n", 1702 bb1->index, bb2->index); 1703 1704 /* Set the original label in BB1->END because when deleting 1705 a block whose end is a tablejump, the tablejump referenced 1706 from the instruction is deleted too. */ 1707 rr.r1 = label2; 1708 rr.r2 = label1; 1709 for_each_rtx (&BB_END (bb1), replace_label, &rr); 1710 1711 return match; 1712 } 1713 } 1714 return false; 1715 } 1716 } 1717 1718 last1 = BB_END (bb1); 1719 last2 = BB_END (bb2); 1720 if (DEBUG_INSN_P (last1)) 1721 last1 = prev_nondebug_insn (last1); 1722 if (DEBUG_INSN_P (last2)) 1723 last2 = prev_nondebug_insn (last2); 1724 /* First ensure that the instructions match. There may be many outgoing 1725 edges so this test is generally cheaper. */ 1726 if (old_insns_match_p (mode, last1, last2) != dir_both) 1727 return false; 1728 1729 /* Search the outgoing edges, ensure that the counts do match, find possible 1730 fallthru and exception handling edges since these needs more 1731 validation. */ 1732 if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs)) 1733 return false; 1734 1735 nonfakeedges = false; 1736 FOR_EACH_EDGE (e1, ei, bb1->succs) 1737 { 1738 e2 = EDGE_SUCC (bb2, ei.index); 1739 1740 if ((e1->flags & EDGE_FAKE) == 0) 1741 nonfakeedges = true; 1742 1743 if (e1->flags & EDGE_EH) 1744 nehedges1++; 1745 1746 if (e2->flags & EDGE_EH) 1747 nehedges2++; 1748 1749 if (e1->flags & EDGE_FALLTHRU) 1750 fallthru1 = e1; 1751 if (e2->flags & EDGE_FALLTHRU) 1752 fallthru2 = e2; 1753 } 1754 1755 /* If number of edges of various types does not match, fail. */ 1756 if (nehedges1 != nehedges2 1757 || (fallthru1 != 0) != (fallthru2 != 0)) 1758 return false; 1759 1760 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors 1761 and the last real insn doesn't have REG_ARGS_SIZE note, don't 1762 attempt to optimize, as the two basic blocks might have different 1763 REG_ARGS_SIZE depths. For noreturn calls and unconditional 1764 traps there should be REG_ARG_SIZE notes, they could be missing 1765 for __builtin_unreachable () uses though. */ 1766 if (!nonfakeedges 1767 && !ACCUMULATE_OUTGOING_ARGS 1768 && (!INSN_P (last1) 1769 || !find_reg_note (last1, REG_ARGS_SIZE, NULL))) 1770 return false; 1771 1772 /* fallthru edges must be forwarded to the same destination. */ 1773 if (fallthru1) 1774 { 1775 basic_block d1 = (forwarder_block_p (fallthru1->dest) 1776 ? single_succ (fallthru1->dest): fallthru1->dest); 1777 basic_block d2 = (forwarder_block_p (fallthru2->dest) 1778 ? single_succ (fallthru2->dest): fallthru2->dest); 1779 1780 if (d1 != d2) 1781 return false; 1782 } 1783 1784 /* Ensure the same EH region. */ 1785 { 1786 rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0); 1787 rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0); 1788 1789 if (!n1 && n2) 1790 return false; 1791 1792 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0))) 1793 return false; 1794 } 1795 1796 /* The same checks as in try_crossjump_to_edge. It is required for RTL 1797 version of sequence abstraction. */ 1798 FOR_EACH_EDGE (e1, ei, bb2->succs) 1799 { 1800 edge e2; 1801 edge_iterator ei; 1802 basic_block d1 = e1->dest; 1803 1804 if (FORWARDER_BLOCK_P (d1)) 1805 d1 = EDGE_SUCC (d1, 0)->dest; 1806 1807 FOR_EACH_EDGE (e2, ei, bb1->succs) 1808 { 1809 basic_block d2 = e2->dest; 1810 if (FORWARDER_BLOCK_P (d2)) 1811 d2 = EDGE_SUCC (d2, 0)->dest; 1812 if (d1 == d2) 1813 break; 1814 } 1815 1816 if (!e2) 1817 return false; 1818 } 1819 1820 return true; 1821 } 1822 1823 /* Returns true if BB basic block has a preserve label. */ 1824 1825 static bool 1826 block_has_preserve_label (basic_block bb) 1827 { 1828 return (bb 1829 && block_label (bb) 1830 && LABEL_PRESERVE_P (block_label (bb))); 1831 } 1832 1833 /* E1 and E2 are edges with the same destination block. Search their 1834 predecessors for common code. If found, redirect control flow from 1835 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward), 1836 or the other way around (dir_backward). DIR specifies the allowed 1837 replacement direction. */ 1838 1839 static bool 1840 try_crossjump_to_edge (int mode, edge e1, edge e2, 1841 enum replace_direction dir) 1842 { 1843 int nmatch; 1844 basic_block src1 = e1->src, src2 = e2->src; 1845 basic_block redirect_to, redirect_from, to_remove; 1846 basic_block osrc1, osrc2, redirect_edges_to, tmp; 1847 rtx newpos1, newpos2; 1848 edge s; 1849 edge_iterator ei; 1850 1851 newpos1 = newpos2 = NULL_RTX; 1852 1853 /* If we have partitioned hot/cold basic blocks, it is a bad idea 1854 to try this optimization. 1855 1856 Basic block partitioning may result in some jumps that appear to 1857 be optimizable (or blocks that appear to be mergeable), but which really 1858 must be left untouched (they are required to make it safely across 1859 partition boundaries). See the comments at the top of 1860 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 1861 1862 if (flag_reorder_blocks_and_partition && reload_completed) 1863 return false; 1864 1865 /* Search backward through forwarder blocks. We don't need to worry 1866 about multiple entry or chained forwarders, as they will be optimized 1867 away. We do this to look past the unconditional jump following a 1868 conditional jump that is required due to the current CFG shape. */ 1869 if (single_pred_p (src1) 1870 && FORWARDER_BLOCK_P (src1)) 1871 e1 = single_pred_edge (src1), src1 = e1->src; 1872 1873 if (single_pred_p (src2) 1874 && FORWARDER_BLOCK_P (src2)) 1875 e2 = single_pred_edge (src2), src2 = e2->src; 1876 1877 /* Nothing to do if we reach ENTRY, or a common source block. */ 1878 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR) 1879 return false; 1880 if (src1 == src2) 1881 return false; 1882 1883 /* Seeing more than 1 forwarder blocks would confuse us later... */ 1884 if (FORWARDER_BLOCK_P (e1->dest) 1885 && FORWARDER_BLOCK_P (single_succ (e1->dest))) 1886 return false; 1887 1888 if (FORWARDER_BLOCK_P (e2->dest) 1889 && FORWARDER_BLOCK_P (single_succ (e2->dest))) 1890 return false; 1891 1892 /* Likewise with dead code (possibly newly created by the other optimizations 1893 of cfg_cleanup). */ 1894 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0) 1895 return false; 1896 1897 /* Look for the common insn sequence, part the first ... */ 1898 if (!outgoing_edges_match (mode, src1, src2)) 1899 return false; 1900 1901 /* ... and part the second. */ 1902 nmatch = flow_find_cross_jump (src1, src2, &newpos1, &newpos2, &dir); 1903 1904 osrc1 = src1; 1905 osrc2 = src2; 1906 if (newpos1 != NULL_RTX) 1907 src1 = BLOCK_FOR_INSN (newpos1); 1908 if (newpos2 != NULL_RTX) 1909 src2 = BLOCK_FOR_INSN (newpos2); 1910 1911 if (dir == dir_backward) 1912 { 1913 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0) 1914 SWAP (basic_block, osrc1, osrc2); 1915 SWAP (basic_block, src1, src2); 1916 SWAP (edge, e1, e2); 1917 SWAP (rtx, newpos1, newpos2); 1918 #undef SWAP 1919 } 1920 1921 /* Don't proceed with the crossjump unless we found a sufficient number 1922 of matching instructions or the 'from' block was totally matched 1923 (such that its predecessors will hopefully be redirected and the 1924 block removed). */ 1925 if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS)) 1926 && (newpos1 != BB_HEAD (src1))) 1927 return false; 1928 1929 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */ 1930 if (block_has_preserve_label (e1->dest) 1931 && (e1->flags & EDGE_ABNORMAL)) 1932 return false; 1933 1934 /* Here we know that the insns in the end of SRC1 which are common with SRC2 1935 will be deleted. 1936 If we have tablejumps in the end of SRC1 and SRC2 1937 they have been already compared for equivalence in outgoing_edges_match () 1938 so replace the references to TABLE1 by references to TABLE2. */ 1939 { 1940 rtx label1, label2; 1941 rtx table1, table2; 1942 1943 if (tablejump_p (BB_END (osrc1), &label1, &table1) 1944 && tablejump_p (BB_END (osrc2), &label2, &table2) 1945 && label1 != label2) 1946 { 1947 replace_label_data rr; 1948 rtx insn; 1949 1950 /* Replace references to LABEL1 with LABEL2. */ 1951 rr.r1 = label1; 1952 rr.r2 = label2; 1953 rr.update_label_nuses = true; 1954 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 1955 { 1956 /* Do not replace the label in SRC1->END because when deleting 1957 a block whose end is a tablejump, the tablejump referenced 1958 from the instruction is deleted too. */ 1959 if (insn != BB_END (osrc1)) 1960 for_each_rtx (&insn, replace_label, &rr); 1961 } 1962 } 1963 } 1964 1965 /* Avoid splitting if possible. We must always split when SRC2 has 1966 EH predecessor edges, or we may end up with basic blocks with both 1967 normal and EH predecessor edges. */ 1968 if (newpos2 == BB_HEAD (src2) 1969 && !(EDGE_PRED (src2, 0)->flags & EDGE_EH)) 1970 redirect_to = src2; 1971 else 1972 { 1973 if (newpos2 == BB_HEAD (src2)) 1974 { 1975 /* Skip possible basic block header. */ 1976 if (LABEL_P (newpos2)) 1977 newpos2 = NEXT_INSN (newpos2); 1978 while (DEBUG_INSN_P (newpos2)) 1979 newpos2 = NEXT_INSN (newpos2); 1980 if (NOTE_P (newpos2)) 1981 newpos2 = NEXT_INSN (newpos2); 1982 while (DEBUG_INSN_P (newpos2)) 1983 newpos2 = NEXT_INSN (newpos2); 1984 } 1985 1986 if (dump_file) 1987 fprintf (dump_file, "Splitting bb %i before %i insns\n", 1988 src2->index, nmatch); 1989 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest; 1990 } 1991 1992 if (dump_file) 1993 fprintf (dump_file, 1994 "Cross jumping from bb %i to bb %i; %i common insns\n", 1995 src1->index, src2->index, nmatch); 1996 1997 /* We may have some registers visible through the block. */ 1998 df_set_bb_dirty (redirect_to); 1999 2000 if (osrc2 == src2) 2001 redirect_edges_to = redirect_to; 2002 else 2003 redirect_edges_to = osrc2; 2004 2005 /* Recompute the frequencies and counts of outgoing edges. */ 2006 FOR_EACH_EDGE (s, ei, redirect_edges_to->succs) 2007 { 2008 edge s2; 2009 edge_iterator ei; 2010 basic_block d = s->dest; 2011 2012 if (FORWARDER_BLOCK_P (d)) 2013 d = single_succ (d); 2014 2015 FOR_EACH_EDGE (s2, ei, src1->succs) 2016 { 2017 basic_block d2 = s2->dest; 2018 if (FORWARDER_BLOCK_P (d2)) 2019 d2 = single_succ (d2); 2020 if (d == d2) 2021 break; 2022 } 2023 2024 s->count += s2->count; 2025 2026 /* Take care to update possible forwarder blocks. We verified 2027 that there is no more than one in the chain, so we can't run 2028 into infinite loop. */ 2029 if (FORWARDER_BLOCK_P (s->dest)) 2030 { 2031 single_succ_edge (s->dest)->count += s2->count; 2032 s->dest->count += s2->count; 2033 s->dest->frequency += EDGE_FREQUENCY (s); 2034 } 2035 2036 if (FORWARDER_BLOCK_P (s2->dest)) 2037 { 2038 single_succ_edge (s2->dest)->count -= s2->count; 2039 if (single_succ_edge (s2->dest)->count < 0) 2040 single_succ_edge (s2->dest)->count = 0; 2041 s2->dest->count -= s2->count; 2042 s2->dest->frequency -= EDGE_FREQUENCY (s); 2043 if (s2->dest->frequency < 0) 2044 s2->dest->frequency = 0; 2045 if (s2->dest->count < 0) 2046 s2->dest->count = 0; 2047 } 2048 2049 if (!redirect_edges_to->frequency && !src1->frequency) 2050 s->probability = (s->probability + s2->probability) / 2; 2051 else 2052 s->probability 2053 = ((s->probability * redirect_edges_to->frequency + 2054 s2->probability * src1->frequency) 2055 / (redirect_edges_to->frequency + src1->frequency)); 2056 } 2057 2058 /* Adjust count and frequency for the block. An earlier jump 2059 threading pass may have left the profile in an inconsistent 2060 state (see update_bb_profile_for_threading) so we must be 2061 prepared for overflows. */ 2062 tmp = redirect_to; 2063 do 2064 { 2065 tmp->count += src1->count; 2066 tmp->frequency += src1->frequency; 2067 if (tmp->frequency > BB_FREQ_MAX) 2068 tmp->frequency = BB_FREQ_MAX; 2069 if (tmp == redirect_edges_to) 2070 break; 2071 tmp = find_fallthru_edge (tmp->succs)->dest; 2072 } 2073 while (true); 2074 update_br_prob_note (redirect_edges_to); 2075 2076 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */ 2077 2078 /* Skip possible basic block header. */ 2079 if (LABEL_P (newpos1)) 2080 newpos1 = NEXT_INSN (newpos1); 2081 2082 while (DEBUG_INSN_P (newpos1)) 2083 newpos1 = NEXT_INSN (newpos1); 2084 2085 if (NOTE_INSN_BASIC_BLOCK_P (newpos1)) 2086 newpos1 = NEXT_INSN (newpos1); 2087 2088 while (DEBUG_INSN_P (newpos1)) 2089 newpos1 = NEXT_INSN (newpos1); 2090 2091 redirect_from = split_block (src1, PREV_INSN (newpos1))->src; 2092 to_remove = single_succ (redirect_from); 2093 2094 redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to); 2095 delete_basic_block (to_remove); 2096 2097 update_forwarder_flag (redirect_from); 2098 if (redirect_to != src2) 2099 update_forwarder_flag (src2); 2100 2101 return true; 2102 } 2103 2104 /* Search the predecessors of BB for common insn sequences. When found, 2105 share code between them by redirecting control flow. Return true if 2106 any changes made. */ 2107 2108 static bool 2109 try_crossjump_bb (int mode, basic_block bb) 2110 { 2111 edge e, e2, fallthru; 2112 bool changed; 2113 unsigned max, ix, ix2; 2114 2115 /* Nothing to do if there is not at least two incoming edges. */ 2116 if (EDGE_COUNT (bb->preds) < 2) 2117 return false; 2118 2119 /* Don't crossjump if this block ends in a computed jump, 2120 unless we are optimizing for size. */ 2121 if (optimize_bb_for_size_p (bb) 2122 && bb != EXIT_BLOCK_PTR 2123 && computed_jump_p (BB_END (bb))) 2124 return false; 2125 2126 /* If we are partitioning hot/cold basic blocks, we don't want to 2127 mess up unconditional or indirect jumps that cross between hot 2128 and cold sections. 2129 2130 Basic block partitioning may result in some jumps that appear to 2131 be optimizable (or blocks that appear to be mergeable), but which really 2132 must be left untouched (they are required to make it safely across 2133 partition boundaries). See the comments at the top of 2134 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 2135 2136 if (BB_PARTITION (EDGE_PRED (bb, 0)->src) != 2137 BB_PARTITION (EDGE_PRED (bb, 1)->src) 2138 || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING)) 2139 return false; 2140 2141 /* It is always cheapest to redirect a block that ends in a branch to 2142 a block that falls through into BB, as that adds no branches to the 2143 program. We'll try that combination first. */ 2144 fallthru = NULL; 2145 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES); 2146 2147 if (EDGE_COUNT (bb->preds) > max) 2148 return false; 2149 2150 fallthru = find_fallthru_edge (bb->preds); 2151 2152 changed = false; 2153 for (ix = 0; ix < EDGE_COUNT (bb->preds);) 2154 { 2155 e = EDGE_PRED (bb, ix); 2156 ix++; 2157 2158 /* As noted above, first try with the fallthru predecessor (or, a 2159 fallthru predecessor if we are in cfglayout mode). */ 2160 if (fallthru) 2161 { 2162 /* Don't combine the fallthru edge into anything else. 2163 If there is a match, we'll do it the other way around. */ 2164 if (e == fallthru) 2165 continue; 2166 /* If nothing changed since the last attempt, there is nothing 2167 we can do. */ 2168 if (!first_pass 2169 && !((e->src->flags & BB_MODIFIED) 2170 || (fallthru->src->flags & BB_MODIFIED))) 2171 continue; 2172 2173 if (try_crossjump_to_edge (mode, e, fallthru, dir_forward)) 2174 { 2175 changed = true; 2176 ix = 0; 2177 continue; 2178 } 2179 } 2180 2181 /* Non-obvious work limiting check: Recognize that we're going 2182 to call try_crossjump_bb on every basic block. So if we have 2183 two blocks with lots of outgoing edges (a switch) and they 2184 share lots of common destinations, then we would do the 2185 cross-jump check once for each common destination. 2186 2187 Now, if the blocks actually are cross-jump candidates, then 2188 all of their destinations will be shared. Which means that 2189 we only need check them for cross-jump candidacy once. We 2190 can eliminate redundant checks of crossjump(A,B) by arbitrarily 2191 choosing to do the check from the block for which the edge 2192 in question is the first successor of A. */ 2193 if (EDGE_SUCC (e->src, 0) != e) 2194 continue; 2195 2196 for (ix2 = 0; ix2 < EDGE_COUNT (bb->preds); ix2++) 2197 { 2198 e2 = EDGE_PRED (bb, ix2); 2199 2200 if (e2 == e) 2201 continue; 2202 2203 /* We've already checked the fallthru edge above. */ 2204 if (e2 == fallthru) 2205 continue; 2206 2207 /* The "first successor" check above only prevents multiple 2208 checks of crossjump(A,B). In order to prevent redundant 2209 checks of crossjump(B,A), require that A be the block 2210 with the lowest index. */ 2211 if (e->src->index > e2->src->index) 2212 continue; 2213 2214 /* If nothing changed since the last attempt, there is nothing 2215 we can do. */ 2216 if (!first_pass 2217 && !((e->src->flags & BB_MODIFIED) 2218 || (e2->src->flags & BB_MODIFIED))) 2219 continue; 2220 2221 /* Both e and e2 are not fallthru edges, so we can crossjump in either 2222 direction. */ 2223 if (try_crossjump_to_edge (mode, e, e2, dir_both)) 2224 { 2225 changed = true; 2226 ix = 0; 2227 break; 2228 } 2229 } 2230 } 2231 2232 if (changed) 2233 crossjumps_occured = true; 2234 2235 return changed; 2236 } 2237 2238 /* Search the successors of BB for common insn sequences. When found, 2239 share code between them by moving it across the basic block 2240 boundary. Return true if any changes made. */ 2241 2242 static bool 2243 try_head_merge_bb (basic_block bb) 2244 { 2245 basic_block final_dest_bb = NULL; 2246 int max_match = INT_MAX; 2247 edge e0; 2248 rtx *headptr, *currptr, *nextptr; 2249 bool changed, moveall; 2250 unsigned ix; 2251 rtx e0_last_head, cond, move_before; 2252 unsigned nedges = EDGE_COUNT (bb->succs); 2253 rtx jump = BB_END (bb); 2254 regset live, live_union; 2255 2256 /* Nothing to do if there is not at least two outgoing edges. */ 2257 if (nedges < 2) 2258 return false; 2259 2260 /* Don't crossjump if this block ends in a computed jump, 2261 unless we are optimizing for size. */ 2262 if (optimize_bb_for_size_p (bb) 2263 && bb != EXIT_BLOCK_PTR 2264 && computed_jump_p (BB_END (bb))) 2265 return false; 2266 2267 cond = get_condition (jump, &move_before, true, false); 2268 if (cond == NULL_RTX) 2269 { 2270 #ifdef HAVE_cc0 2271 if (reg_mentioned_p (cc0_rtx, jump)) 2272 move_before = prev_nonnote_nondebug_insn (jump); 2273 else 2274 #endif 2275 move_before = jump; 2276 } 2277 2278 for (ix = 0; ix < nedges; ix++) 2279 if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR) 2280 return false; 2281 2282 for (ix = 0; ix < nedges; ix++) 2283 { 2284 edge e = EDGE_SUCC (bb, ix); 2285 basic_block other_bb = e->dest; 2286 2287 if (df_get_bb_dirty (other_bb)) 2288 { 2289 block_was_dirty = true; 2290 return false; 2291 } 2292 2293 if (e->flags & EDGE_ABNORMAL) 2294 return false; 2295 2296 /* Normally, all destination blocks must only be reachable from this 2297 block, i.e. they must have one incoming edge. 2298 2299 There is one special case we can handle, that of multiple consecutive 2300 jumps where the first jumps to one of the targets of the second jump. 2301 This happens frequently in switch statements for default labels. 2302 The structure is as follows: 2303 FINAL_DEST_BB 2304 .... 2305 if (cond) jump A; 2306 fall through 2307 BB 2308 jump with targets A, B, C, D... 2309 A 2310 has two incoming edges, from FINAL_DEST_BB and BB 2311 2312 In this case, we can try to move the insns through BB and into 2313 FINAL_DEST_BB. */ 2314 if (EDGE_COUNT (other_bb->preds) != 1) 2315 { 2316 edge incoming_edge, incoming_bb_other_edge; 2317 edge_iterator ei; 2318 2319 if (final_dest_bb != NULL 2320 || EDGE_COUNT (other_bb->preds) != 2) 2321 return false; 2322 2323 /* We must be able to move the insns across the whole block. */ 2324 move_before = BB_HEAD (bb); 2325 while (!NONDEBUG_INSN_P (move_before)) 2326 move_before = NEXT_INSN (move_before); 2327 2328 if (EDGE_COUNT (bb->preds) != 1) 2329 return false; 2330 incoming_edge = EDGE_PRED (bb, 0); 2331 final_dest_bb = incoming_edge->src; 2332 if (EDGE_COUNT (final_dest_bb->succs) != 2) 2333 return false; 2334 FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs) 2335 if (incoming_bb_other_edge != incoming_edge) 2336 break; 2337 if (incoming_bb_other_edge->dest != other_bb) 2338 return false; 2339 } 2340 } 2341 2342 e0 = EDGE_SUCC (bb, 0); 2343 e0_last_head = NULL_RTX; 2344 changed = false; 2345 2346 for (ix = 1; ix < nedges; ix++) 2347 { 2348 edge e = EDGE_SUCC (bb, ix); 2349 rtx e0_last, e_last; 2350 int nmatch; 2351 2352 nmatch = flow_find_head_matching_sequence (e0->dest, e->dest, 2353 &e0_last, &e_last, 0); 2354 if (nmatch == 0) 2355 return false; 2356 2357 if (nmatch < max_match) 2358 { 2359 max_match = nmatch; 2360 e0_last_head = e0_last; 2361 } 2362 } 2363 2364 /* If we matched an entire block, we probably have to avoid moving the 2365 last insn. */ 2366 if (max_match > 0 2367 && e0_last_head == BB_END (e0->dest) 2368 && (find_reg_note (e0_last_head, REG_EH_REGION, 0) 2369 || control_flow_insn_p (e0_last_head))) 2370 { 2371 max_match--; 2372 if (max_match == 0) 2373 return false; 2374 do 2375 e0_last_head = prev_real_insn (e0_last_head); 2376 while (DEBUG_INSN_P (e0_last_head)); 2377 } 2378 2379 if (max_match == 0) 2380 return false; 2381 2382 /* We must find a union of the live registers at each of the end points. */ 2383 live = BITMAP_ALLOC (NULL); 2384 live_union = BITMAP_ALLOC (NULL); 2385 2386 currptr = XNEWVEC (rtx, nedges); 2387 headptr = XNEWVEC (rtx, nedges); 2388 nextptr = XNEWVEC (rtx, nedges); 2389 2390 for (ix = 0; ix < nedges; ix++) 2391 { 2392 int j; 2393 basic_block merge_bb = EDGE_SUCC (bb, ix)->dest; 2394 rtx head = BB_HEAD (merge_bb); 2395 2396 while (!NONDEBUG_INSN_P (head)) 2397 head = NEXT_INSN (head); 2398 headptr[ix] = head; 2399 currptr[ix] = head; 2400 2401 /* Compute the end point and live information */ 2402 for (j = 1; j < max_match; j++) 2403 do 2404 head = NEXT_INSN (head); 2405 while (!NONDEBUG_INSN_P (head)); 2406 simulate_backwards_to_point (merge_bb, live, head); 2407 IOR_REG_SET (live_union, live); 2408 } 2409 2410 /* If we're moving across two blocks, verify the validity of the 2411 first move, then adjust the target and let the loop below deal 2412 with the final move. */ 2413 if (final_dest_bb != NULL) 2414 { 2415 rtx move_upto; 2416 2417 moveall = can_move_insns_across (currptr[0], e0_last_head, move_before, 2418 jump, e0->dest, live_union, 2419 NULL, &move_upto); 2420 if (!moveall) 2421 { 2422 if (move_upto == NULL_RTX) 2423 goto out; 2424 2425 while (e0_last_head != move_upto) 2426 { 2427 df_simulate_one_insn_backwards (e0->dest, e0_last_head, 2428 live_union); 2429 e0_last_head = PREV_INSN (e0_last_head); 2430 } 2431 } 2432 if (e0_last_head == NULL_RTX) 2433 goto out; 2434 2435 jump = BB_END (final_dest_bb); 2436 cond = get_condition (jump, &move_before, true, false); 2437 if (cond == NULL_RTX) 2438 { 2439 #ifdef HAVE_cc0 2440 if (reg_mentioned_p (cc0_rtx, jump)) 2441 move_before = prev_nonnote_nondebug_insn (jump); 2442 else 2443 #endif 2444 move_before = jump; 2445 } 2446 } 2447 2448 do 2449 { 2450 rtx move_upto; 2451 moveall = can_move_insns_across (currptr[0], e0_last_head, 2452 move_before, jump, e0->dest, live_union, 2453 NULL, &move_upto); 2454 if (!moveall && move_upto == NULL_RTX) 2455 { 2456 if (jump == move_before) 2457 break; 2458 2459 /* Try again, using a different insertion point. */ 2460 move_before = jump; 2461 2462 #ifdef HAVE_cc0 2463 /* Don't try moving before a cc0 user, as that may invalidate 2464 the cc0. */ 2465 if (reg_mentioned_p (cc0_rtx, jump)) 2466 break; 2467 #endif 2468 2469 continue; 2470 } 2471 2472 if (final_dest_bb && !moveall) 2473 /* We haven't checked whether a partial move would be OK for the first 2474 move, so we have to fail this case. */ 2475 break; 2476 2477 changed = true; 2478 for (;;) 2479 { 2480 if (currptr[0] == move_upto) 2481 break; 2482 for (ix = 0; ix < nedges; ix++) 2483 { 2484 rtx curr = currptr[ix]; 2485 do 2486 curr = NEXT_INSN (curr); 2487 while (!NONDEBUG_INSN_P (curr)); 2488 currptr[ix] = curr; 2489 } 2490 } 2491 2492 /* If we can't currently move all of the identical insns, remember 2493 each insn after the range that we'll merge. */ 2494 if (!moveall) 2495 for (ix = 0; ix < nedges; ix++) 2496 { 2497 rtx curr = currptr[ix]; 2498 do 2499 curr = NEXT_INSN (curr); 2500 while (!NONDEBUG_INSN_P (curr)); 2501 nextptr[ix] = curr; 2502 } 2503 2504 reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before)); 2505 df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest); 2506 if (final_dest_bb != NULL) 2507 df_set_bb_dirty (final_dest_bb); 2508 df_set_bb_dirty (bb); 2509 for (ix = 1; ix < nedges; ix++) 2510 { 2511 df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest); 2512 delete_insn_chain (headptr[ix], currptr[ix], false); 2513 } 2514 if (!moveall) 2515 { 2516 if (jump == move_before) 2517 break; 2518 2519 /* For the unmerged insns, try a different insertion point. */ 2520 move_before = jump; 2521 2522 #ifdef HAVE_cc0 2523 /* Don't try moving before a cc0 user, as that may invalidate 2524 the cc0. */ 2525 if (reg_mentioned_p (cc0_rtx, jump)) 2526 break; 2527 #endif 2528 2529 for (ix = 0; ix < nedges; ix++) 2530 currptr[ix] = headptr[ix] = nextptr[ix]; 2531 } 2532 } 2533 while (!moveall); 2534 2535 out: 2536 free (currptr); 2537 free (headptr); 2538 free (nextptr); 2539 2540 crossjumps_occured |= changed; 2541 2542 return changed; 2543 } 2544 2545 /* Return true if BB contains just bb note, or bb note followed 2546 by only DEBUG_INSNs. */ 2547 2548 static bool 2549 trivially_empty_bb_p (basic_block bb) 2550 { 2551 rtx insn = BB_END (bb); 2552 2553 while (1) 2554 { 2555 if (insn == BB_HEAD (bb)) 2556 return true; 2557 if (!DEBUG_INSN_P (insn)) 2558 return false; 2559 insn = PREV_INSN (insn); 2560 } 2561 } 2562 2563 /* Do simple CFG optimizations - basic block merging, simplifying of jump 2564 instructions etc. Return nonzero if changes were made. */ 2565 2566 static bool 2567 try_optimize_cfg (int mode) 2568 { 2569 bool changed_overall = false; 2570 bool changed; 2571 int iterations = 0; 2572 basic_block bb, b, next; 2573 2574 if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING)) 2575 clear_bb_flags (); 2576 2577 crossjumps_occured = false; 2578 2579 FOR_EACH_BB (bb) 2580 update_forwarder_flag (bb); 2581 2582 if (! targetm.cannot_modify_jumps_p ()) 2583 { 2584 first_pass = true; 2585 /* Attempt to merge blocks as made possible by edge removal. If 2586 a block has only one successor, and the successor has only 2587 one predecessor, they may be combined. */ 2588 do 2589 { 2590 block_was_dirty = false; 2591 changed = false; 2592 iterations++; 2593 2594 if (dump_file) 2595 fprintf (dump_file, 2596 "\n\ntry_optimize_cfg iteration %i\n\n", 2597 iterations); 2598 2599 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;) 2600 { 2601 basic_block c; 2602 edge s; 2603 bool changed_here = false; 2604 2605 /* Delete trivially dead basic blocks. This is either 2606 blocks with no predecessors, or empty blocks with no 2607 successors. However if the empty block with no 2608 successors is the successor of the ENTRY_BLOCK, it is 2609 kept. This ensures that the ENTRY_BLOCK will have a 2610 successor which is a precondition for many RTL 2611 passes. Empty blocks may result from expanding 2612 __builtin_unreachable (). */ 2613 if (EDGE_COUNT (b->preds) == 0 2614 || (EDGE_COUNT (b->succs) == 0 2615 && trivially_empty_bb_p (b) 2616 && single_succ_edge (ENTRY_BLOCK_PTR)->dest != b)) 2617 { 2618 c = b->prev_bb; 2619 if (EDGE_COUNT (b->preds) > 0) 2620 { 2621 edge e; 2622 edge_iterator ei; 2623 2624 if (current_ir_type () == IR_RTL_CFGLAYOUT) 2625 { 2626 if (b->il.rtl->footer 2627 && BARRIER_P (b->il.rtl->footer)) 2628 FOR_EACH_EDGE (e, ei, b->preds) 2629 if ((e->flags & EDGE_FALLTHRU) 2630 && e->src->il.rtl->footer == NULL) 2631 { 2632 if (b->il.rtl->footer) 2633 { 2634 e->src->il.rtl->footer = b->il.rtl->footer; 2635 b->il.rtl->footer = NULL; 2636 } 2637 else 2638 { 2639 start_sequence (); 2640 e->src->il.rtl->footer = emit_barrier (); 2641 end_sequence (); 2642 } 2643 } 2644 } 2645 else 2646 { 2647 rtx last = get_last_bb_insn (b); 2648 if (last && BARRIER_P (last)) 2649 FOR_EACH_EDGE (e, ei, b->preds) 2650 if ((e->flags & EDGE_FALLTHRU)) 2651 emit_barrier_after (BB_END (e->src)); 2652 } 2653 } 2654 delete_basic_block (b); 2655 changed = true; 2656 /* Avoid trying to remove ENTRY_BLOCK_PTR. */ 2657 b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c); 2658 continue; 2659 } 2660 2661 /* Remove code labels no longer used. */ 2662 if (single_pred_p (b) 2663 && (single_pred_edge (b)->flags & EDGE_FALLTHRU) 2664 && !(single_pred_edge (b)->flags & EDGE_COMPLEX) 2665 && LABEL_P (BB_HEAD (b)) 2666 /* If the previous block ends with a branch to this 2667 block, we can't delete the label. Normally this 2668 is a condjump that is yet to be simplified, but 2669 if CASE_DROPS_THRU, this can be a tablejump with 2670 some element going to the same place as the 2671 default (fallthru). */ 2672 && (single_pred (b) == ENTRY_BLOCK_PTR 2673 || !JUMP_P (BB_END (single_pred (b))) 2674 || ! label_is_jump_target_p (BB_HEAD (b), 2675 BB_END (single_pred (b))))) 2676 { 2677 rtx label = BB_HEAD (b); 2678 2679 delete_insn_chain (label, label, false); 2680 /* If the case label is undeletable, move it after the 2681 BASIC_BLOCK note. */ 2682 if (NOTE_KIND (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL) 2683 { 2684 rtx bb_note = NEXT_INSN (BB_HEAD (b)); 2685 2686 reorder_insns_nobb (label, label, bb_note); 2687 BB_HEAD (b) = bb_note; 2688 if (BB_END (b) == bb_note) 2689 BB_END (b) = label; 2690 } 2691 if (dump_file) 2692 fprintf (dump_file, "Deleted label in block %i.\n", 2693 b->index); 2694 } 2695 2696 /* If we fall through an empty block, we can remove it. */ 2697 if (!(mode & CLEANUP_CFGLAYOUT) 2698 && single_pred_p (b) 2699 && (single_pred_edge (b)->flags & EDGE_FALLTHRU) 2700 && !LABEL_P (BB_HEAD (b)) 2701 && FORWARDER_BLOCK_P (b) 2702 /* Note that forwarder_block_p true ensures that 2703 there is a successor for this block. */ 2704 && (single_succ_edge (b)->flags & EDGE_FALLTHRU) 2705 && n_basic_blocks > NUM_FIXED_BLOCKS + 1) 2706 { 2707 if (dump_file) 2708 fprintf (dump_file, 2709 "Deleting fallthru block %i.\n", 2710 b->index); 2711 2712 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb; 2713 redirect_edge_succ_nodup (single_pred_edge (b), 2714 single_succ (b)); 2715 delete_basic_block (b); 2716 changed = true; 2717 b = c; 2718 continue; 2719 } 2720 2721 /* Merge B with its single successor, if any. */ 2722 if (single_succ_p (b) 2723 && (s = single_succ_edge (b)) 2724 && !(s->flags & EDGE_COMPLEX) 2725 && (c = s->dest) != EXIT_BLOCK_PTR 2726 && single_pred_p (c) 2727 && b != c) 2728 { 2729 /* When not in cfg_layout mode use code aware of reordering 2730 INSN. This code possibly creates new basic blocks so it 2731 does not fit merge_blocks interface and is kept here in 2732 hope that it will become useless once more of compiler 2733 is transformed to use cfg_layout mode. */ 2734 2735 if ((mode & CLEANUP_CFGLAYOUT) 2736 && can_merge_blocks_p (b, c)) 2737 { 2738 merge_blocks (b, c); 2739 update_forwarder_flag (b); 2740 changed_here = true; 2741 } 2742 else if (!(mode & CLEANUP_CFGLAYOUT) 2743 /* If the jump insn has side effects, 2744 we can't kill the edge. */ 2745 && (!JUMP_P (BB_END (b)) 2746 || (reload_completed 2747 ? simplejump_p (BB_END (b)) 2748 : (onlyjump_p (BB_END (b)) 2749 && !tablejump_p (BB_END (b), 2750 NULL, NULL)))) 2751 && (next = merge_blocks_move (s, b, c, mode))) 2752 { 2753 b = next; 2754 changed_here = true; 2755 } 2756 } 2757 2758 /* Simplify branch over branch. */ 2759 if ((mode & CLEANUP_EXPENSIVE) 2760 && !(mode & CLEANUP_CFGLAYOUT) 2761 && try_simplify_condjump (b)) 2762 changed_here = true; 2763 2764 /* If B has a single outgoing edge, but uses a 2765 non-trivial jump instruction without side-effects, we 2766 can either delete the jump entirely, or replace it 2767 with a simple unconditional jump. */ 2768 if (single_succ_p (b) 2769 && single_succ (b) != EXIT_BLOCK_PTR 2770 && onlyjump_p (BB_END (b)) 2771 && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX) 2772 && try_redirect_by_replacing_jump (single_succ_edge (b), 2773 single_succ (b), 2774 (mode & CLEANUP_CFGLAYOUT) != 0)) 2775 { 2776 update_forwarder_flag (b); 2777 changed_here = true; 2778 } 2779 2780 /* Simplify branch to branch. */ 2781 if (try_forward_edges (mode, b)) 2782 { 2783 update_forwarder_flag (b); 2784 changed_here = true; 2785 } 2786 2787 /* Look for shared code between blocks. */ 2788 if ((mode & CLEANUP_CROSSJUMP) 2789 && try_crossjump_bb (mode, b)) 2790 changed_here = true; 2791 2792 if ((mode & CLEANUP_CROSSJUMP) 2793 /* This can lengthen register lifetimes. Do it only after 2794 reload. */ 2795 && reload_completed 2796 && try_head_merge_bb (b)) 2797 changed_here = true; 2798 2799 /* Don't get confused by the index shift caused by 2800 deleting blocks. */ 2801 if (!changed_here) 2802 b = b->next_bb; 2803 else 2804 changed = true; 2805 } 2806 2807 if ((mode & CLEANUP_CROSSJUMP) 2808 && try_crossjump_bb (mode, EXIT_BLOCK_PTR)) 2809 changed = true; 2810 2811 if (block_was_dirty) 2812 { 2813 /* This should only be set by head-merging. */ 2814 gcc_assert (mode & CLEANUP_CROSSJUMP); 2815 df_analyze (); 2816 } 2817 2818 #ifdef ENABLE_CHECKING 2819 if (changed) 2820 verify_flow_info (); 2821 #endif 2822 2823 changed_overall |= changed; 2824 first_pass = false; 2825 } 2826 while (changed); 2827 } 2828 2829 FOR_ALL_BB (b) 2830 b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK); 2831 2832 return changed_overall; 2833 } 2834 2835 /* Delete all unreachable basic blocks. */ 2836 2837 bool 2838 delete_unreachable_blocks (void) 2839 { 2840 bool changed = false; 2841 basic_block b, prev_bb; 2842 2843 find_unreachable_blocks (); 2844 2845 /* When we're in GIMPLE mode and there may be debug insns, we should 2846 delete blocks in reverse dominator order, so as to get a chance 2847 to substitute all released DEFs into debug stmts. If we don't 2848 have dominators information, walking blocks backward gets us a 2849 better chance of retaining most debug information than 2850 otherwise. */ 2851 if (MAY_HAVE_DEBUG_STMTS && current_ir_type () == IR_GIMPLE 2852 && dom_info_available_p (CDI_DOMINATORS)) 2853 { 2854 for (b = EXIT_BLOCK_PTR->prev_bb; b != ENTRY_BLOCK_PTR; b = prev_bb) 2855 { 2856 prev_bb = b->prev_bb; 2857 2858 if (!(b->flags & BB_REACHABLE)) 2859 { 2860 /* Speed up the removal of blocks that don't dominate 2861 others. Walking backwards, this should be the common 2862 case. */ 2863 if (!first_dom_son (CDI_DOMINATORS, b)) 2864 delete_basic_block (b); 2865 else 2866 { 2867 VEC (basic_block, heap) *h 2868 = get_all_dominated_blocks (CDI_DOMINATORS, b); 2869 2870 while (VEC_length (basic_block, h)) 2871 { 2872 b = VEC_pop (basic_block, h); 2873 2874 prev_bb = b->prev_bb; 2875 2876 gcc_assert (!(b->flags & BB_REACHABLE)); 2877 2878 delete_basic_block (b); 2879 } 2880 2881 VEC_free (basic_block, heap, h); 2882 } 2883 2884 changed = true; 2885 } 2886 } 2887 } 2888 else 2889 { 2890 for (b = EXIT_BLOCK_PTR->prev_bb; b != ENTRY_BLOCK_PTR; b = prev_bb) 2891 { 2892 prev_bb = b->prev_bb; 2893 2894 if (!(b->flags & BB_REACHABLE)) 2895 { 2896 delete_basic_block (b); 2897 changed = true; 2898 } 2899 } 2900 } 2901 2902 if (changed) 2903 tidy_fallthru_edges (); 2904 return changed; 2905 } 2906 2907 /* Delete any jump tables never referenced. We can't delete them at the 2908 time of removing tablejump insn as they are referenced by the preceding 2909 insns computing the destination, so we delay deleting and garbagecollect 2910 them once life information is computed. */ 2911 void 2912 delete_dead_jumptables (void) 2913 { 2914 basic_block bb; 2915 2916 /* A dead jump table does not belong to any basic block. Scan insns 2917 between two adjacent basic blocks. */ 2918 FOR_EACH_BB (bb) 2919 { 2920 rtx insn, next; 2921 2922 for (insn = NEXT_INSN (BB_END (bb)); 2923 insn && !NOTE_INSN_BASIC_BLOCK_P (insn); 2924 insn = next) 2925 { 2926 next = NEXT_INSN (insn); 2927 if (LABEL_P (insn) 2928 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn) 2929 && JUMP_TABLE_DATA_P (next)) 2930 { 2931 rtx label = insn, jump = next; 2932 2933 if (dump_file) 2934 fprintf (dump_file, "Dead jumptable %i removed\n", 2935 INSN_UID (insn)); 2936 2937 next = NEXT_INSN (next); 2938 delete_insn (jump); 2939 delete_insn (label); 2940 } 2941 } 2942 } 2943 } 2944 2945 2946 /* Tidy the CFG by deleting unreachable code and whatnot. */ 2947 2948 bool 2949 cleanup_cfg (int mode) 2950 { 2951 bool changed = false; 2952 2953 /* Set the cfglayout mode flag here. We could update all the callers 2954 but that is just inconvenient, especially given that we eventually 2955 want to have cfglayout mode as the default. */ 2956 if (current_ir_type () == IR_RTL_CFGLAYOUT) 2957 mode |= CLEANUP_CFGLAYOUT; 2958 2959 timevar_push (TV_CLEANUP_CFG); 2960 if (delete_unreachable_blocks ()) 2961 { 2962 changed = true; 2963 /* We've possibly created trivially dead code. Cleanup it right 2964 now to introduce more opportunities for try_optimize_cfg. */ 2965 if (!(mode & (CLEANUP_NO_INSN_DEL)) 2966 && !reload_completed) 2967 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 2968 } 2969 2970 compact_blocks (); 2971 2972 /* To tail-merge blocks ending in the same noreturn function (e.g. 2973 a call to abort) we have to insert fake edges to exit. Do this 2974 here once. The fake edges do not interfere with any other CFG 2975 cleanups. */ 2976 if (mode & CLEANUP_CROSSJUMP) 2977 add_noreturn_fake_exit_edges (); 2978 2979 if (!dbg_cnt (cfg_cleanup)) 2980 return changed; 2981 2982 while (try_optimize_cfg (mode)) 2983 { 2984 delete_unreachable_blocks (), changed = true; 2985 if (!(mode & CLEANUP_NO_INSN_DEL)) 2986 { 2987 /* Try to remove some trivially dead insns when doing an expensive 2988 cleanup. But delete_trivially_dead_insns doesn't work after 2989 reload (it only handles pseudos) and run_fast_dce is too costly 2990 to run in every iteration. 2991 2992 For effective cross jumping, we really want to run a fast DCE to 2993 clean up any dead conditions, or they get in the way of performing 2994 useful tail merges. 2995 2996 Other transformations in cleanup_cfg are not so sensitive to dead 2997 code, so delete_trivially_dead_insns or even doing nothing at all 2998 is good enough. */ 2999 if ((mode & CLEANUP_EXPENSIVE) && !reload_completed 3000 && !delete_trivially_dead_insns (get_insns (), max_reg_num ())) 3001 break; 3002 if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occured) 3003 run_fast_dce (); 3004 } 3005 else 3006 break; 3007 } 3008 3009 if (mode & CLEANUP_CROSSJUMP) 3010 remove_fake_exit_edges (); 3011 3012 /* Don't call delete_dead_jumptables in cfglayout mode, because 3013 that function assumes that jump tables are in the insns stream. 3014 But we also don't _have_ to delete dead jumptables in cfglayout 3015 mode because we shouldn't even be looking at things that are 3016 not in a basic block. Dead jumptables are cleaned up when 3017 going out of cfglayout mode. */ 3018 if (!(mode & CLEANUP_CFGLAYOUT)) 3019 delete_dead_jumptables (); 3020 3021 timevar_pop (TV_CLEANUP_CFG); 3022 3023 return changed; 3024 } 3025 3026 static unsigned int 3027 rest_of_handle_jump (void) 3028 { 3029 if (crtl->tail_call_emit) 3030 fixup_tail_calls (); 3031 return 0; 3032 } 3033 3034 struct rtl_opt_pass pass_jump = 3035 { 3036 { 3037 RTL_PASS, 3038 "sibling", /* name */ 3039 NULL, /* gate */ 3040 rest_of_handle_jump, /* execute */ 3041 NULL, /* sub */ 3042 NULL, /* next */ 3043 0, /* static_pass_number */ 3044 TV_JUMP, /* tv_id */ 3045 0, /* properties_required */ 3046 0, /* properties_provided */ 3047 0, /* properties_destroyed */ 3048 TODO_ggc_collect, /* todo_flags_start */ 3049 TODO_verify_flow, /* todo_flags_finish */ 3050 } 3051 }; 3052 3053 3054 static unsigned int 3055 rest_of_handle_jump2 (void) 3056 { 3057 delete_trivially_dead_insns (get_insns (), max_reg_num ()); 3058 if (dump_file) 3059 dump_flow_info (dump_file, dump_flags); 3060 cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0) 3061 | (flag_thread_jumps ? CLEANUP_THREADING : 0)); 3062 return 0; 3063 } 3064 3065 3066 struct rtl_opt_pass pass_jump2 = 3067 { 3068 { 3069 RTL_PASS, 3070 "jump", /* name */ 3071 NULL, /* gate */ 3072 rest_of_handle_jump2, /* execute */ 3073 NULL, /* sub */ 3074 NULL, /* next */ 3075 0, /* static_pass_number */ 3076 TV_JUMP, /* tv_id */ 3077 0, /* properties_required */ 3078 0, /* properties_provided */ 3079 0, /* properties_destroyed */ 3080 TODO_ggc_collect, /* todo_flags_start */ 3081 TODO_verify_rtl_sharing, /* todo_flags_finish */ 3082 } 3083 }; 3084