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