c++: Prevent overwriting arguments when merging duplicates [PR112588]
[official-gcc.git] / gcc / cfgcleanup.cc
bloba3b2e93fa510dbcddb634fb3d6884f77762c0644
1 /* Control flow optimization code for GNU compiler.
2 Copyright (C) 1987-2024 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 /* This file contains optimizer of the control flow. The main entry point is
21 cleanup_cfg. Following optimizations are performed:
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. */
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"
58 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
60 /* Set to true when we are running first pass of try_optimize_cfg loop. */
61 static bool first_pass;
63 /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg. */
64 static bool crossjumps_occurred;
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;
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 *);
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);
86 /* Set flags for newly created block. */
88 static void
89 notice_new_block (basic_block bb)
91 if (!bb)
92 return;
94 if (forwarder_block_p (bb))
95 bb->flags |= BB_FORWARDER_BLOCK;
98 /* Recompute forwarder flag after block has been modified. */
100 static void
101 update_forwarder_flag (basic_block bb)
103 if (forwarder_block_p (bb))
104 bb->flags |= BB_FORWARDER_BLOCK;
105 else
106 bb->flags &= ~BB_FORWARDER_BLOCK;
109 /* Simplify a conditional jump around an unconditional jump.
110 Return true if something changed. */
112 static bool
113 try_simplify_condjump (basic_block cbranch_block)
115 basic_block jump_block, jump_dest_block, cbranch_dest_block;
116 edge cbranch_jump_edge, cbranch_fallthru_edge;
117 rtx_insn *cbranch_insn;
119 /* Verify that there are exactly two successors. */
120 if (EDGE_COUNT (cbranch_block->succs) != 2)
121 return false;
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;
129 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
130 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
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);
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.
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.cc:partition_hot_cold_basic_blocks for complete details. */
152 if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
153 || (cbranch_jump_edge->flags & EDGE_CROSSING))
154 return false;
156 /* The conditional branch must target the block after the
157 unconditional branch. */
158 cbranch_dest_block = cbranch_jump_edge->dest;
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;
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;
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)));
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);
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);
190 return true;
193 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
194 on register. Used by jump threading. */
196 static bool
197 mark_effect (rtx exp, regset nonequal)
199 rtx dest;
200 switch (GET_CODE (exp))
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;
210 case SET:
211 if (cselib_redundant_set_p (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;
221 default:
222 return false;
226 /* Return true if X contains a register in NONEQUAL. */
227 static bool
228 mentions_nonequal_regs (const_rtx x, regset nonequal)
230 subrtx_iterator::array_type array;
231 FOR_EACH_SUBRTX (iter, array, x, NONCONST)
233 const_rtx x = *iter;
234 if (REG_P (x))
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;
242 return false;
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. */
249 static edge
250 thread_jump (edge e, basic_block b)
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;
260 /* Jump threading may cause fixup_partitions to introduce new crossing edges,
261 which is not allowed after reload. */
262 gcc_checking_assert (!reload_completed || !crtl->has_bb_partition);
264 if (b->flags & BB_NONTHREADABLE_BLOCK)
265 return NULL;
267 /* At the moment, we do handle only conditional jumps, but later we may
268 want to extend this code to tablejumps and others. */
269 if (EDGE_COUNT (e->src->succs) != 2)
270 return NULL;
271 if (EDGE_COUNT (b->succs) != 2)
273 b->flags |= BB_NONTHREADABLE_BLOCK;
274 return NULL;
277 /* Second branch must end with onlyjump, as we will eliminate the jump. */
278 if (!any_condjump_p (BB_END (e->src)))
279 return NULL;
281 if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
283 b->flags |= BB_NONTHREADABLE_BLOCK;
284 return NULL;
287 set1 = pc_set (BB_END (e->src));
288 set2 = pc_set (BB_END (b));
289 if (((e->flags & EDGE_FALLTHRU) != 0)
290 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
291 reverse1 = true;
293 cond1 = XEXP (SET_SRC (set1), 0);
294 cond2 = XEXP (SET_SRC (set2), 0);
295 if (reverse1)
296 code1 = reversed_comparison_code (cond1, BB_END (e->src));
297 else
298 code1 = GET_CODE (cond1);
300 code2 = GET_CODE (cond2);
301 reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
303 if (!comparison_dominates_p (code1, code2)
304 && !comparison_dominates_p (code1, reversed_code2))
305 return NULL;
307 /* Ensure that the comparison operators are equivalent.
308 ??? This is far too pessimistic. We should allow swapped operands,
309 different CCmodes, or for example comparisons for interval, that
310 dominate even when operands are not equivalent. */
311 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
312 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
313 return NULL;
315 /* Punt if BB_END (e->src) is doloop-like conditional jump that modifies
316 the registers used in cond1. */
317 if (modified_in_p (cond1, BB_END (e->src)))
318 return NULL;
320 /* Short circuit cases where block B contains some side effects, as we can't
321 safely bypass it. */
322 for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
323 insn = NEXT_INSN (insn))
324 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
326 b->flags |= BB_NONTHREADABLE_BLOCK;
327 return NULL;
330 cselib_init (0);
332 /* First process all values computed in the source basic block. */
333 for (insn = NEXT_INSN (BB_HEAD (e->src));
334 insn != NEXT_INSN (BB_END (e->src));
335 insn = NEXT_INSN (insn))
336 if (INSN_P (insn))
337 cselib_process_insn (insn);
339 nonequal = BITMAP_ALLOC (NULL);
340 CLEAR_REG_SET (nonequal);
342 /* Now assume that we've continued by the edge E to B and continue
343 processing as if it were same basic block.
344 Our goal is to prove that whole block is an NOOP. */
346 for (insn = NEXT_INSN (BB_HEAD (b));
347 insn != NEXT_INSN (BB_END (b)) && !failed;
348 insn = NEXT_INSN (insn))
350 /* cond2 must not mention any register that is not equal to the
351 former block. Check this before processing that instruction,
352 as BB_END (b) could contain also clobbers. */
353 if (insn == BB_END (b)
354 && mentions_nonequal_regs (cond2, nonequal))
355 goto failed_exit;
357 if (INSN_P (insn))
359 rtx pat = PATTERN (insn);
361 if (GET_CODE (pat) == PARALLEL)
363 for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
364 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
366 else
367 failed |= mark_effect (pat, nonequal);
370 cselib_process_insn (insn);
373 /* Later we should clear nonequal of dead registers. So far we don't
374 have life information in cfg_cleanup. */
375 if (failed)
377 b->flags |= BB_NONTHREADABLE_BLOCK;
378 goto failed_exit;
381 if (!REG_SET_EMPTY_P (nonequal))
382 goto failed_exit;
384 BITMAP_FREE (nonequal);
385 cselib_finish ();
386 if ((comparison_dominates_p (code1, code2) != 0)
387 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
388 return BRANCH_EDGE (b);
389 else
390 return FALLTHRU_EDGE (b);
392 failed_exit:
393 BITMAP_FREE (nonequal);
394 cselib_finish ();
395 return NULL;
398 /* Attempt to forward edges leaving basic block B.
399 Return true if successful. */
401 static bool
402 try_forward_edges (int mode, basic_block b)
404 bool changed = false;
405 edge_iterator ei;
406 edge e, *threaded_edges = NULL;
408 for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
410 basic_block target, first;
411 location_t goto_locus;
412 int counter;
413 bool threaded = false;
414 int nthreaded_edges = 0;
415 bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0;
416 bool new_target_threaded = false;
418 /* Skip complex edges because we don't know how to update them.
420 Still handle fallthru edges, as we can succeed to forward fallthru
421 edge to the same place as the branch edge of conditional branch
422 and turn conditional branch to an unconditional branch. */
423 if (e->flags & EDGE_COMPLEX)
425 ei_next (&ei);
426 continue;
429 target = first = e->dest;
430 counter = NUM_FIXED_BLOCKS;
431 goto_locus = e->goto_locus;
433 while (counter < n_basic_blocks_for_fn (cfun))
435 basic_block new_target = NULL;
436 may_thread |= (target->flags & BB_MODIFIED) != 0;
438 if (FORWARDER_BLOCK_P (target)
439 && single_succ (target) != EXIT_BLOCK_PTR_FOR_FN (cfun))
441 /* Bypass trivial infinite loops. */
442 new_target = single_succ (target);
443 if (target == new_target)
444 counter = n_basic_blocks_for_fn (cfun);
445 else if (!optimize)
447 /* When not optimizing, ensure that edges or forwarder
448 blocks with different locus are not optimized out. */
449 location_t new_locus = single_succ_edge (target)->goto_locus;
450 location_t locus = goto_locus;
452 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION
453 && LOCATION_LOCUS (locus) != UNKNOWN_LOCATION
454 && new_locus != locus)
455 new_target = NULL;
456 else
458 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION)
459 locus = new_locus;
461 rtx_insn *last = BB_END (target);
462 if (DEBUG_INSN_P (last))
463 last = prev_nondebug_insn (last);
464 if (last && INSN_P (last))
465 new_locus = INSN_LOCATION (last);
466 else
467 new_locus = UNKNOWN_LOCATION;
469 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION
470 && LOCATION_LOCUS (locus) != UNKNOWN_LOCATION
471 && new_locus != locus)
472 new_target = NULL;
473 else
475 if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION)
476 locus = new_locus;
478 goto_locus = locus;
484 /* Allow to thread only over one edge at time to simplify updating
485 of probabilities. */
486 else if ((mode & CLEANUP_THREADING) && may_thread)
488 edge t = thread_jump (e, target);
489 if (t)
491 if (!threaded_edges)
492 threaded_edges = XNEWVEC (edge,
493 n_basic_blocks_for_fn (cfun));
494 else
496 int i;
498 /* Detect an infinite loop across blocks not
499 including the start block. */
500 for (i = 0; i < nthreaded_edges; ++i)
501 if (threaded_edges[i] == t)
502 break;
503 if (i < nthreaded_edges)
505 counter = n_basic_blocks_for_fn (cfun);
506 break;
510 /* Detect an infinite loop across the start block. */
511 if (t->dest == b)
512 break;
514 gcc_assert (nthreaded_edges
515 < (n_basic_blocks_for_fn (cfun)
516 - NUM_FIXED_BLOCKS));
517 threaded_edges[nthreaded_edges++] = t;
519 new_target = t->dest;
520 new_target_threaded = true;
524 if (!new_target)
525 break;
527 counter++;
528 /* Do not turn non-crossing jump to crossing. Depending on target
529 it may require different instruction pattern. */
530 if ((e->flags & EDGE_CROSSING)
531 || BB_PARTITION (first) == BB_PARTITION (new_target))
533 target = new_target;
534 threaded |= new_target_threaded;
538 if (counter >= n_basic_blocks_for_fn (cfun))
540 if (dump_file)
541 fprintf (dump_file, "Infinite loop in BB %i.\n",
542 target->index);
544 else if (target == first)
545 ; /* We didn't do anything. */
546 else
548 /* Save the values now, as the edge may get removed. */
549 profile_count edge_count = e->count ();
550 int n = 0;
552 e->goto_locus = goto_locus;
554 /* Don't force if target is exit block. */
555 if (threaded && target != EXIT_BLOCK_PTR_FOR_FN (cfun))
557 notice_new_block (redirect_edge_and_branch_force (e, target));
558 if (dump_file)
559 fprintf (dump_file, "Conditionals threaded.\n");
561 else if (!redirect_edge_and_branch (e, target))
563 if (dump_file)
564 fprintf (dump_file,
565 "Forwarding edge %i->%i to %i failed.\n",
566 b->index, e->dest->index, target->index);
567 ei_next (&ei);
568 continue;
571 /* We successfully forwarded the edge. Now update profile
572 data: for each edge we traversed in the chain, remove
573 the original edge's execution count. */
576 edge t;
578 if (!single_succ_p (first))
580 gcc_assert (n < nthreaded_edges);
581 t = threaded_edges [n++];
582 gcc_assert (t->src == first);
583 update_bb_profile_for_threading (first, edge_count, t);
584 update_br_prob_note (first);
586 else
588 first->count -= edge_count;
589 /* It is possible that as the result of
590 threading we've removed edge as it is
591 threaded to the fallthru edge. Avoid
592 getting out of sync. */
593 if (n < nthreaded_edges
594 && first == threaded_edges [n]->src)
595 n++;
596 t = single_succ_edge (first);
599 first = t->dest;
601 while (first != target);
603 changed = true;
604 continue;
606 ei_next (&ei);
609 free (threaded_edges);
610 return changed;
614 /* Blocks A and B are to be merged into a single block. A has no incoming
615 fallthru edge, so it can be moved before B without adding or modifying
616 any jumps (aside from the jump from A to B). */
618 static void
619 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
621 rtx_insn *barrier;
623 /* If we are partitioning hot/cold basic blocks, we don't want to
624 mess up unconditional or indirect jumps that cross between hot
625 and cold sections.
627 Basic block partitioning may result in some jumps that appear to
628 be optimizable (or blocks that appear to be mergeable), but which really
629 must be left untouched (they are required to make it safely across
630 partition boundaries). See the comments at the top of
631 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
633 if (BB_PARTITION (a) != BB_PARTITION (b))
634 return;
636 barrier = next_nonnote_insn (BB_END (a));
637 gcc_assert (BARRIER_P (barrier));
638 delete_insn (barrier);
640 /* Scramble the insn chain. */
641 if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
642 reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
643 df_set_bb_dirty (a);
645 if (dump_file)
646 fprintf (dump_file, "Moved block %d before %d and merged.\n",
647 a->index, b->index);
649 /* Swap the records for the two blocks around. */
651 unlink_block (a);
652 link_block (a, b->prev_bb);
654 /* Now blocks A and B are contiguous. Merge them. */
655 merge_blocks (a, b);
658 /* Blocks A and B are to be merged into a single block. B has no outgoing
659 fallthru edge, so it can be moved after A without adding or modifying
660 any jumps (aside from the jump from A to B). */
662 static void
663 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
665 rtx_insn *barrier, *real_b_end;
666 rtx_insn *label;
667 rtx_jump_table_data *table;
669 /* If we are partitioning hot/cold basic blocks, we don't want to
670 mess up unconditional or indirect jumps that cross between hot
671 and cold sections.
673 Basic block partitioning may result in some jumps that appear to
674 be optimizable (or blocks that appear to be mergeable), but which really
675 must be left untouched (they are required to make it safely across
676 partition boundaries). See the comments at the top of
677 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
679 if (BB_PARTITION (a) != BB_PARTITION (b))
680 return;
682 real_b_end = BB_END (b);
684 /* If there is a jump table following block B temporarily add the jump table
685 to block B so that it will also be moved to the correct location. */
686 if (tablejump_p (BB_END (b), &label, &table)
687 && prev_active_insn (label) == BB_END (b))
689 BB_END (b) = table;
692 /* There had better have been a barrier there. Delete it. */
693 barrier = NEXT_INSN (BB_END (b));
694 if (barrier && BARRIER_P (barrier))
695 delete_insn (barrier);
698 /* Scramble the insn chain. */
699 reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
701 /* Restore the real end of b. */
702 BB_END (b) = real_b_end;
704 if (dump_file)
705 fprintf (dump_file, "Moved block %d after %d and merged.\n",
706 b->index, a->index);
708 /* Now blocks A and B are contiguous. Merge them. */
709 merge_blocks (a, b);
712 /* Attempt to merge basic blocks that are potentially non-adjacent.
713 Return NULL iff the attempt failed, otherwise return basic block
714 where cleanup_cfg should continue. Because the merging commonly
715 moves basic block away or introduces another optimization
716 possibility, return basic block just before B so cleanup_cfg don't
717 need to iterate.
719 It may be good idea to return basic block before C in the case
720 C has been moved after B and originally appeared earlier in the
721 insn sequence, but we have no information available about the
722 relative ordering of these two. Hopefully it is not too common. */
724 static basic_block
725 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
727 basic_block next;
729 /* If we are partitioning hot/cold basic blocks, we don't want to
730 mess up unconditional or indirect jumps that cross between hot
731 and cold sections.
733 Basic block partitioning may result in some jumps that appear to
734 be optimizable (or blocks that appear to be mergeable), but which really
735 must be left untouched (they are required to make it safely across
736 partition boundaries). See the comments at the top of
737 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
739 if (BB_PARTITION (b) != BB_PARTITION (c))
740 return NULL;
742 /* If B has a fallthru edge to C, no need to move anything. */
743 if (e->flags & EDGE_FALLTHRU)
745 int b_index = b->index, c_index = c->index;
747 /* Protect the loop latches. */
748 if (current_loops && c->loop_father->latch == c)
749 return NULL;
751 merge_blocks (b, c);
752 update_forwarder_flag (b);
754 if (dump_file)
755 fprintf (dump_file, "Merged %d and %d without moving.\n",
756 b_index, c_index);
758 return b->prev_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? b : b->prev_bb;
761 /* Otherwise we will need to move code around. Do that only if expensive
762 transformations are allowed. */
763 else if (mode & CLEANUP_EXPENSIVE)
765 edge tmp_edge, b_fallthru_edge;
766 bool c_has_outgoing_fallthru;
767 bool b_has_incoming_fallthru;
769 /* Avoid overactive code motion, as the forwarder blocks should be
770 eliminated by edge redirection instead. One exception might have
771 been if B is a forwarder block and C has no fallthru edge, but
772 that should be cleaned up by bb-reorder instead. */
773 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
774 return NULL;
776 /* We must make sure to not munge nesting of lexical blocks,
777 and loop notes. This is done by squeezing out all the notes
778 and leaving them there to lie. Not ideal, but functional. */
780 tmp_edge = find_fallthru_edge (c->succs);
781 c_has_outgoing_fallthru = (tmp_edge != NULL);
783 tmp_edge = find_fallthru_edge (b->preds);
784 b_has_incoming_fallthru = (tmp_edge != NULL);
785 b_fallthru_edge = tmp_edge;
786 next = b->prev_bb;
787 if (next == c)
788 next = next->prev_bb;
790 /* Otherwise, we're going to try to move C after B. If C does
791 not have an outgoing fallthru, then it can be moved
792 immediately after B without introducing or modifying jumps. */
793 if (! c_has_outgoing_fallthru)
795 merge_blocks_move_successor_nojumps (b, c);
796 return next == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? next->next_bb : next;
799 /* If B does not have an incoming fallthru, then it can be moved
800 immediately before C without introducing or modifying jumps.
801 C cannot be the first block, so we do not have to worry about
802 accessing a non-existent block. */
804 if (b_has_incoming_fallthru)
806 basic_block bb;
808 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
809 return NULL;
810 bb = force_nonfallthru (b_fallthru_edge);
811 if (bb)
812 notice_new_block (bb);
815 merge_blocks_move_predecessor_nojumps (b, c);
816 return next == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? next->next_bb : next;
819 return NULL;
823 /* Removes the memory attributes of MEM expression
824 if they are not equal. */
826 static void
827 merge_memattrs (rtx x, rtx y)
829 int i;
830 int j;
831 enum rtx_code code;
832 const char *fmt;
834 if (x == y)
835 return;
836 if (x == 0 || y == 0)
837 return;
839 code = GET_CODE (x);
841 if (code != GET_CODE (y))
842 return;
844 if (GET_MODE (x) != GET_MODE (y))
845 return;
847 if (code == MEM && !mem_attrs_eq_p (MEM_ATTRS (x), MEM_ATTRS (y)))
849 if (! MEM_ATTRS (x))
850 MEM_ATTRS (y) = 0;
851 else if (! MEM_ATTRS (y))
852 MEM_ATTRS (x) = 0;
853 else
855 if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
857 set_mem_alias_set (x, 0);
858 set_mem_alias_set (y, 0);
861 if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
863 set_mem_expr (x, 0);
864 set_mem_expr (y, 0);
865 clear_mem_offset (x);
866 clear_mem_offset (y);
868 else if (MEM_OFFSET_KNOWN_P (x) != MEM_OFFSET_KNOWN_P (y)
869 || (MEM_OFFSET_KNOWN_P (x)
870 && maybe_ne (MEM_OFFSET (x), MEM_OFFSET (y))))
872 clear_mem_offset (x);
873 clear_mem_offset (y);
876 if (!MEM_SIZE_KNOWN_P (x))
877 clear_mem_size (y);
878 else if (!MEM_SIZE_KNOWN_P (y))
879 clear_mem_size (x);
880 else if (known_le (MEM_SIZE (x), MEM_SIZE (y)))
881 set_mem_size (x, MEM_SIZE (y));
882 else if (known_le (MEM_SIZE (y), MEM_SIZE (x)))
883 set_mem_size (y, MEM_SIZE (x));
884 else
886 /* The sizes aren't ordered, so we can't merge them. */
887 clear_mem_size (x);
888 clear_mem_size (y);
891 set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
892 set_mem_align (y, MEM_ALIGN (x));
895 if (code == MEM)
897 if (MEM_READONLY_P (x) != MEM_READONLY_P (y))
899 MEM_READONLY_P (x) = 0;
900 MEM_READONLY_P (y) = 0;
902 if (MEM_NOTRAP_P (x) != MEM_NOTRAP_P (y))
904 MEM_NOTRAP_P (x) = 0;
905 MEM_NOTRAP_P (y) = 0;
907 if (MEM_VOLATILE_P (x) != MEM_VOLATILE_P (y))
909 MEM_VOLATILE_P (x) = 1;
910 MEM_VOLATILE_P (y) = 1;
914 fmt = GET_RTX_FORMAT (code);
915 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
917 switch (fmt[i])
919 case 'E':
920 /* Two vectors must have the same length. */
921 if (XVECLEN (x, i) != XVECLEN (y, i))
922 return;
924 for (j = 0; j < XVECLEN (x, i); j++)
925 merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
927 break;
929 case 'e':
930 merge_memattrs (XEXP (x, i), XEXP (y, i));
933 return;
937 /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
938 different single sets S1 and S2. */
940 static bool
941 equal_different_set_p (rtx p1, rtx s1, rtx p2, rtx s2)
943 int i;
944 rtx e1, e2;
946 if (p1 == s1 && p2 == s2)
947 return true;
949 if (GET_CODE (p1) != PARALLEL || GET_CODE (p2) != PARALLEL)
950 return false;
952 if (XVECLEN (p1, 0) != XVECLEN (p2, 0))
953 return false;
955 for (i = 0; i < XVECLEN (p1, 0); i++)
957 e1 = XVECEXP (p1, 0, i);
958 e2 = XVECEXP (p2, 0, i);
959 if (e1 == s1 && e2 == s2)
960 continue;
961 if (reload_completed
962 ? rtx_renumbered_equal_p (e1, e2) : rtx_equal_p (e1, e2))
963 continue;
965 return false;
968 return true;
972 /* NOTE1 is the REG_EQUAL note, if any, attached to an insn
973 that is a single_set with a SET_SRC of SRC1. Similarly
974 for NOTE2/SRC2.
976 So effectively NOTE1/NOTE2 are an alternate form of
977 SRC1/SRC2 respectively.
979 Return nonzero if SRC1 or NOTE1 has the same constant
980 integer value as SRC2 or NOTE2. Else return zero. */
981 static int
982 values_equal_p (rtx note1, rtx note2, rtx src1, rtx src2)
984 if (note1
985 && note2
986 && CONST_INT_P (XEXP (note1, 0))
987 && rtx_equal_p (XEXP (note1, 0), XEXP (note2, 0)))
988 return 1;
990 if (!note1
991 && !note2
992 && CONST_INT_P (src1)
993 && CONST_INT_P (src2)
994 && rtx_equal_p (src1, src2))
995 return 1;
997 if (note1
998 && CONST_INT_P (src2)
999 && rtx_equal_p (XEXP (note1, 0), src2))
1000 return 1;
1002 if (note2
1003 && CONST_INT_P (src1)
1004 && rtx_equal_p (XEXP (note2, 0), src1))
1005 return 1;
1007 return 0;
1010 /* Examine register notes on I1 and I2 and return:
1011 - dir_forward if I1 can be replaced by I2, or
1012 - dir_backward if I2 can be replaced by I1, or
1013 - dir_both if both are the case. */
1015 static enum replace_direction
1016 can_replace_by (rtx_insn *i1, rtx_insn *i2)
1018 rtx s1, s2, d1, d2, src1, src2, note1, note2;
1019 bool c1, c2;
1021 /* Check for 2 sets. */
1022 s1 = single_set (i1);
1023 s2 = single_set (i2);
1024 if (s1 == NULL_RTX || s2 == NULL_RTX)
1025 return dir_none;
1027 /* Check that the 2 sets set the same dest. */
1028 d1 = SET_DEST (s1);
1029 d2 = SET_DEST (s2);
1030 if (!(reload_completed
1031 ? rtx_renumbered_equal_p (d1, d2) : rtx_equal_p (d1, d2)))
1032 return dir_none;
1034 /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1035 set dest to the same value. */
1036 note1 = find_reg_equal_equiv_note (i1);
1037 note2 = find_reg_equal_equiv_note (i2);
1039 src1 = SET_SRC (s1);
1040 src2 = SET_SRC (s2);
1042 if (!values_equal_p (note1, note2, src1, src2))
1043 return dir_none;
1045 if (!equal_different_set_p (PATTERN (i1), s1, PATTERN (i2), s2))
1046 return dir_none;
1048 /* Although the 2 sets set dest to the same value, we cannot replace
1049 (set (dest) (const_int))
1051 (set (dest) (reg))
1052 because we don't know if the reg is live and has the same value at the
1053 location of replacement. */
1054 c1 = CONST_INT_P (src1);
1055 c2 = CONST_INT_P (src2);
1056 if (c1 && c2)
1057 return dir_both;
1058 else if (c2)
1059 return dir_forward;
1060 else if (c1)
1061 return dir_backward;
1063 return dir_none;
1066 /* Merges directions A and B. */
1068 static enum replace_direction
1069 merge_dir (enum replace_direction a, enum replace_direction b)
1071 /* Implements the following table:
1072 |bo fw bw no
1073 ---+-----------
1074 bo |bo fw bw no
1075 fw |-- fw no no
1076 bw |-- -- bw no
1077 no |-- -- -- no. */
1079 if (a == b)
1080 return a;
1082 if (a == dir_both)
1083 return b;
1084 if (b == dir_both)
1085 return a;
1087 return dir_none;
1090 /* Array of flags indexed by reg note kind, true if the given
1091 reg note is CFA related. */
1092 static const bool reg_note_cfa_p[] = {
1093 #undef REG_CFA_NOTE
1094 #define DEF_REG_NOTE(NAME) false,
1095 #define REG_CFA_NOTE(NAME) true,
1096 #include "reg-notes.def"
1097 #undef REG_CFA_NOTE
1098 #undef DEF_REG_NOTE
1099 false
1102 /* Return true if I1 and I2 have identical CFA notes (the same order
1103 and equivalent content). */
1105 static bool
1106 insns_have_identical_cfa_notes (rtx_insn *i1, rtx_insn *i2)
1108 rtx n1, n2;
1109 for (n1 = REG_NOTES (i1), n2 = REG_NOTES (i2); ;
1110 n1 = XEXP (n1, 1), n2 = XEXP (n2, 1))
1112 /* Skip over reg notes not related to CFI information. */
1113 while (n1 && !reg_note_cfa_p[REG_NOTE_KIND (n1)])
1114 n1 = XEXP (n1, 1);
1115 while (n2 && !reg_note_cfa_p[REG_NOTE_KIND (n2)])
1116 n2 = XEXP (n2, 1);
1117 if (n1 == NULL_RTX && n2 == NULL_RTX)
1118 return true;
1119 if (n1 == NULL_RTX || n2 == NULL_RTX)
1120 return false;
1121 if (XEXP (n1, 0) == XEXP (n2, 0))
1123 else if (XEXP (n1, 0) == NULL_RTX || XEXP (n2, 0) == NULL_RTX)
1124 return false;
1125 else if (!(reload_completed
1126 ? rtx_renumbered_equal_p (XEXP (n1, 0), XEXP (n2, 0))
1127 : rtx_equal_p (XEXP (n1, 0), XEXP (n2, 0))))
1128 return false;
1132 /* Examine I1 and I2 and return:
1133 - dir_forward if I1 can be replaced by I2, or
1134 - dir_backward if I2 can be replaced by I1, or
1135 - dir_both if both are the case. */
1137 static enum replace_direction
1138 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx_insn *i1, rtx_insn *i2)
1140 rtx p1, p2;
1142 /* Verify that I1 and I2 are equivalent. */
1143 if (GET_CODE (i1) != GET_CODE (i2))
1144 return dir_none;
1146 /* __builtin_unreachable() may lead to empty blocks (ending with
1147 NOTE_INSN_BASIC_BLOCK). They may be crossjumped. */
1148 if (NOTE_INSN_BASIC_BLOCK_P (i1) && NOTE_INSN_BASIC_BLOCK_P (i2))
1149 return dir_both;
1151 /* ??? Do not allow cross-jumping between different stack levels. */
1152 p1 = find_reg_note (i1, REG_ARGS_SIZE, NULL);
1153 p2 = find_reg_note (i2, REG_ARGS_SIZE, NULL);
1154 if (p1 && p2)
1156 p1 = XEXP (p1, 0);
1157 p2 = XEXP (p2, 0);
1158 if (!rtx_equal_p (p1, p2))
1159 return dir_none;
1161 /* ??? Worse, this adjustment had better be constant lest we
1162 have differing incoming stack levels. */
1163 if (!frame_pointer_needed
1164 && known_eq (find_args_size_adjust (i1), HOST_WIDE_INT_MIN))
1165 return dir_none;
1167 else if (p1 || p2)
1168 return dir_none;
1170 /* Do not allow cross-jumping between frame related insns and other
1171 insns. */
1172 if (RTX_FRAME_RELATED_P (i1) != RTX_FRAME_RELATED_P (i2))
1173 return dir_none;
1175 p1 = PATTERN (i1);
1176 p2 = PATTERN (i2);
1178 if (GET_CODE (p1) != GET_CODE (p2))
1179 return dir_none;
1181 /* If this is a CALL_INSN, compare register usage information.
1182 If we don't check this on stack register machines, the two
1183 CALL_INSNs might be merged leaving reg-stack.cc with mismatching
1184 numbers of stack registers in the same basic block.
1185 If we don't check this on machines with delay slots, a delay slot may
1186 be filled that clobbers a parameter expected by the subroutine.
1188 ??? We take the simple route for now and assume that if they're
1189 equal, they were constructed identically.
1191 Also check for identical exception regions. */
1193 if (CALL_P (i1))
1195 /* Ensure the same EH region. */
1196 rtx n1 = find_reg_note (i1, REG_EH_REGION, 0);
1197 rtx n2 = find_reg_note (i2, REG_EH_REGION, 0);
1199 if (!n1 && n2)
1200 return dir_none;
1202 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1203 return dir_none;
1205 if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
1206 CALL_INSN_FUNCTION_USAGE (i2))
1207 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2))
1208 return dir_none;
1210 /* For address sanitizer, never crossjump __asan_report_* builtins,
1211 otherwise errors might be reported on incorrect lines. */
1212 if (flag_sanitize & SANITIZE_ADDRESS)
1214 rtx call = get_call_rtx_from (i1);
1215 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
1217 rtx symbol = XEXP (XEXP (call, 0), 0);
1218 if (SYMBOL_REF_DECL (symbol)
1219 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
1221 if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
1222 == BUILT_IN_NORMAL)
1223 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
1224 >= BUILT_IN_ASAN_REPORT_LOAD1
1225 && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
1226 <= BUILT_IN_ASAN_STOREN)
1227 return dir_none;
1232 if (insn_callee_abi (i1) != insn_callee_abi (i2))
1233 return dir_none;
1236 /* If both i1 and i2 are frame related, verify all the CFA notes
1237 in the same order and with the same content. */
1238 if (RTX_FRAME_RELATED_P (i1) && !insns_have_identical_cfa_notes (i1, i2))
1239 return dir_none;
1241 #ifdef STACK_REGS
1242 /* If cross_jump_death_matters is not 0, the insn's mode
1243 indicates whether or not the insn contains any stack-like
1244 regs. */
1246 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
1248 /* If register stack conversion has already been done, then
1249 death notes must also be compared before it is certain that
1250 the two instruction streams match. */
1252 rtx note;
1253 HARD_REG_SET i1_regset, i2_regset;
1255 CLEAR_HARD_REG_SET (i1_regset);
1256 CLEAR_HARD_REG_SET (i2_regset);
1258 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
1259 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1260 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
1262 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1263 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1264 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1266 if (i1_regset != i2_regset)
1267 return dir_none;
1269 #endif
1271 if (reload_completed
1272 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1273 return dir_both;
1275 return can_replace_by (i1, i2);
1278 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1279 flow_find_head_matching_sequence, ensure the notes match. */
1281 static void
1282 merge_notes (rtx_insn *i1, rtx_insn *i2)
1284 /* If the merged insns have different REG_EQUAL notes, then
1285 remove them. */
1286 rtx equiv1 = find_reg_equal_equiv_note (i1);
1287 rtx equiv2 = find_reg_equal_equiv_note (i2);
1289 if (equiv1 && !equiv2)
1290 remove_note (i1, equiv1);
1291 else if (!equiv1 && equiv2)
1292 remove_note (i2, equiv2);
1293 else if (equiv1 && equiv2
1294 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1296 remove_note (i1, equiv1);
1297 remove_note (i2, equiv2);
1301 /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1302 resulting insn in I1, and the corresponding bb in BB1. At the head of a
1303 bb, if there is a predecessor bb that reaches this bb via fallthru, and
1304 FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1305 DID_FALLTHRU. Otherwise, stops at the head of the bb. */
1307 static void
1308 walk_to_nondebug_insn (rtx_insn **i1, basic_block *bb1, bool follow_fallthru,
1309 bool *did_fallthru)
1311 edge fallthru;
1313 *did_fallthru = false;
1315 /* Ignore notes. */
1316 while (!NONDEBUG_INSN_P (*i1))
1318 if (*i1 != BB_HEAD (*bb1))
1320 *i1 = PREV_INSN (*i1);
1321 continue;
1324 if (!follow_fallthru)
1325 return;
1327 fallthru = find_fallthru_edge ((*bb1)->preds);
1328 if (!fallthru || fallthru->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
1329 || !single_succ_p (fallthru->src))
1330 return;
1332 *bb1 = fallthru->src;
1333 *i1 = BB_END (*bb1);
1334 *did_fallthru = true;
1338 /* Look through the insns at the end of BB1 and BB2 and find the longest
1339 sequence that are either equivalent, or allow forward or backward
1340 replacement. Store the first insns for that sequence in *F1 and *F2 and
1341 return the sequence length.
1343 DIR_P indicates the allowed replacement direction on function entry, and
1344 the actual replacement direction on function exit. If NULL, only equivalent
1345 sequences are allowed.
1347 To simplify callers of this function, if the blocks match exactly,
1348 store the head of the blocks in *F1 and *F2. */
1351 flow_find_cross_jump (basic_block bb1, basic_block bb2, rtx_insn **f1,
1352 rtx_insn **f2, enum replace_direction *dir_p)
1354 rtx_insn *i1, *i2, *last1, *last2, *afterlast1, *afterlast2;
1355 int ninsns = 0;
1356 enum replace_direction dir, last_dir, afterlast_dir;
1357 bool follow_fallthru, did_fallthru;
1359 if (dir_p)
1360 dir = *dir_p;
1361 else
1362 dir = dir_both;
1363 afterlast_dir = dir;
1364 last_dir = afterlast_dir;
1366 /* Skip simple jumps at the end of the blocks. Complex jumps still
1367 need to be compared for equivalence, which we'll do below. */
1369 i1 = BB_END (bb1);
1370 last1 = afterlast1 = last2 = afterlast2 = NULL;
1371 if (onlyjump_p (i1)
1372 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1374 last1 = i1;
1375 i1 = PREV_INSN (i1);
1378 i2 = BB_END (bb2);
1379 if (onlyjump_p (i2)
1380 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1382 last2 = i2;
1383 /* Count everything except for unconditional jump as insn.
1384 Don't count any jumps if dir_p is NULL. */
1385 if (!simplejump_p (i2) && !returnjump_p (i2) && last1 && dir_p)
1386 ninsns++;
1387 i2 = PREV_INSN (i2);
1390 while (true)
1392 /* In the following example, we can replace all jumps to C by jumps to A.
1394 This removes 4 duplicate insns.
1395 [bb A] insn1 [bb C] insn1
1396 insn2 insn2
1397 [bb B] insn3 insn3
1398 insn4 insn4
1399 jump_insn jump_insn
1401 We could also replace all jumps to A by jumps to C, but that leaves B
1402 alive, and removes only 2 duplicate insns. In a subsequent crossjump
1403 step, all jumps to B would be replaced with jumps to the middle of C,
1404 achieving the same result with more effort.
1405 So we allow only the first possibility, which means that we don't allow
1406 fallthru in the block that's being replaced. */
1408 follow_fallthru = dir_p && dir != dir_forward;
1409 walk_to_nondebug_insn (&i1, &bb1, follow_fallthru, &did_fallthru);
1410 if (did_fallthru)
1411 dir = dir_backward;
1413 follow_fallthru = dir_p && dir != dir_backward;
1414 walk_to_nondebug_insn (&i2, &bb2, follow_fallthru, &did_fallthru);
1415 if (did_fallthru)
1416 dir = dir_forward;
1418 if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1419 break;
1421 /* Do not turn corssing edge to non-crossing or vice versa after
1422 reload. */
1423 if (BB_PARTITION (BLOCK_FOR_INSN (i1))
1424 != BB_PARTITION (BLOCK_FOR_INSN (i2))
1425 && reload_completed)
1426 break;
1428 dir = merge_dir (dir, old_insns_match_p (0, i1, i2));
1429 if (dir == dir_none || (!dir_p && dir != dir_both))
1430 break;
1432 merge_memattrs (i1, i2);
1434 /* Don't begin a cross-jump with a NOTE insn. */
1435 if (INSN_P (i1))
1437 merge_notes (i1, i2);
1439 afterlast1 = last1, afterlast2 = last2;
1440 last1 = i1, last2 = i2;
1441 afterlast_dir = last_dir;
1442 last_dir = dir;
1443 if (active_insn_p (i1))
1444 ninsns++;
1447 i1 = PREV_INSN (i1);
1448 i2 = PREV_INSN (i2);
1451 /* Include preceding notes and labels in the cross-jump. One,
1452 this may bring us to the head of the blocks as requested above.
1453 Two, it keeps line number notes as matched as may be. */
1454 if (ninsns)
1456 bb1 = BLOCK_FOR_INSN (last1);
1457 while (last1 != BB_HEAD (bb1) && !NONDEBUG_INSN_P (PREV_INSN (last1)))
1458 last1 = PREV_INSN (last1);
1460 if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1461 last1 = PREV_INSN (last1);
1463 bb2 = BLOCK_FOR_INSN (last2);
1464 while (last2 != BB_HEAD (bb2) && !NONDEBUG_INSN_P (PREV_INSN (last2)))
1465 last2 = PREV_INSN (last2);
1467 if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1468 last2 = PREV_INSN (last2);
1470 *f1 = last1;
1471 *f2 = last2;
1474 if (dir_p)
1475 *dir_p = last_dir;
1476 return ninsns;
1479 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1480 the head of the two blocks. Do not include jumps at the end.
1481 If STOP_AFTER is nonzero, stop after finding that many matching
1482 instructions. If STOP_AFTER is zero, count all INSN_P insns, if it is
1483 non-zero, only count active insns. */
1486 flow_find_head_matching_sequence (basic_block bb1, basic_block bb2, rtx_insn **f1,
1487 rtx_insn **f2, int stop_after)
1489 rtx_insn *i1, *i2, *last1, *last2, *beforelast1, *beforelast2;
1490 int ninsns = 0;
1491 edge e;
1492 edge_iterator ei;
1493 int nehedges1 = 0, nehedges2 = 0;
1495 FOR_EACH_EDGE (e, ei, bb1->succs)
1496 if (e->flags & EDGE_EH)
1497 nehedges1++;
1498 FOR_EACH_EDGE (e, ei, bb2->succs)
1499 if (e->flags & EDGE_EH)
1500 nehedges2++;
1502 i1 = BB_HEAD (bb1);
1503 i2 = BB_HEAD (bb2);
1504 last1 = beforelast1 = last2 = beforelast2 = NULL;
1506 while (true)
1508 /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG. */
1509 while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
1511 if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG)
1512 break;
1513 i1 = NEXT_INSN (i1);
1516 while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
1518 if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG)
1519 break;
1520 i2 = NEXT_INSN (i2);
1523 if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
1524 || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
1525 break;
1527 if (NOTE_P (i1) || NOTE_P (i2)
1528 || JUMP_P (i1) || JUMP_P (i2))
1529 break;
1531 /* A sanity check to make sure we're not merging insns with different
1532 effects on EH. If only one of them ends a basic block, it shouldn't
1533 have an EH edge; if both end a basic block, there should be the same
1534 number of EH edges. */
1535 if ((i1 == BB_END (bb1) && i2 != BB_END (bb2)
1536 && nehedges1 > 0)
1537 || (i2 == BB_END (bb2) && i1 != BB_END (bb1)
1538 && nehedges2 > 0)
1539 || (i1 == BB_END (bb1) && i2 == BB_END (bb2)
1540 && nehedges1 != nehedges2))
1541 break;
1543 if (old_insns_match_p (0, i1, i2) != dir_both)
1544 break;
1546 merge_memattrs (i1, i2);
1548 /* Don't begin a cross-jump with a NOTE insn. */
1549 if (INSN_P (i1))
1551 merge_notes (i1, i2);
1553 beforelast1 = last1, beforelast2 = last2;
1554 last1 = i1, last2 = i2;
1555 if (!stop_after || active_insn_p (i1))
1556 ninsns++;
1559 if (i1 == BB_END (bb1) || i2 == BB_END (bb2)
1560 || (stop_after > 0 && ninsns == stop_after))
1561 break;
1563 i1 = NEXT_INSN (i1);
1564 i2 = NEXT_INSN (i2);
1567 if (ninsns)
1569 *f1 = last1;
1570 *f2 = last2;
1573 return ninsns;
1576 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1577 the branch instruction. This means that if we commonize the control
1578 flow before end of the basic block, the semantic remains unchanged.
1580 We may assume that there exists one edge with a common destination. */
1582 static bool
1583 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1585 int nehedges1 = 0, nehedges2 = 0;
1586 edge fallthru1 = 0, fallthru2 = 0;
1587 edge e1, e2;
1588 edge_iterator ei;
1590 /* If we performed shrink-wrapping, edges to the exit block can
1591 only be distinguished for JUMP_INSNs. The two paths may differ in
1592 whether they went through the prologue. Sibcalls are fine, we know
1593 that we either didn't need or inserted an epilogue before them. */
1594 if (crtl->shrink_wrapped
1595 && single_succ_p (bb1)
1596 && single_succ (bb1) == EXIT_BLOCK_PTR_FOR_FN (cfun)
1597 && (!JUMP_P (BB_END (bb1))
1598 /* Punt if the only successor is a fake edge to exit, the jump
1599 must be some weird one. */
1600 || (single_succ_edge (bb1)->flags & EDGE_FAKE) != 0)
1601 && !(CALL_P (BB_END (bb1)) && SIBLING_CALL_P (BB_END (bb1))))
1602 return false;
1604 /* If BB1 has only one successor, we may be looking at either an
1605 unconditional jump, or a fake edge to exit. */
1606 if (single_succ_p (bb1)
1607 && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1608 && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1609 return (single_succ_p (bb2)
1610 && (single_succ_edge (bb2)->flags
1611 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1612 && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1614 /* Match conditional jumps - this may get tricky when fallthru and branch
1615 edges are crossed. */
1616 if (EDGE_COUNT (bb1->succs) == 2
1617 && any_condjump_p (BB_END (bb1))
1618 && onlyjump_p (BB_END (bb1)))
1620 edge b1, f1, b2, f2;
1621 bool reverse, match;
1622 rtx set1, set2, cond1, cond2;
1623 enum rtx_code code1, code2;
1625 if (EDGE_COUNT (bb2->succs) != 2
1626 || !any_condjump_p (BB_END (bb2))
1627 || !onlyjump_p (BB_END (bb2)))
1628 return false;
1630 b1 = BRANCH_EDGE (bb1);
1631 b2 = BRANCH_EDGE (bb2);
1632 f1 = FALLTHRU_EDGE (bb1);
1633 f2 = FALLTHRU_EDGE (bb2);
1635 /* Get around possible forwarders on fallthru edges. Other cases
1636 should be optimized out already. */
1637 if (FORWARDER_BLOCK_P (f1->dest))
1638 f1 = single_succ_edge (f1->dest);
1640 if (FORWARDER_BLOCK_P (f2->dest))
1641 f2 = single_succ_edge (f2->dest);
1643 /* To simplify use of this function, return false if there are
1644 unneeded forwarder blocks. These will get eliminated later
1645 during cleanup_cfg. */
1646 if (FORWARDER_BLOCK_P (f1->dest)
1647 || FORWARDER_BLOCK_P (f2->dest)
1648 || FORWARDER_BLOCK_P (b1->dest)
1649 || FORWARDER_BLOCK_P (b2->dest))
1650 return false;
1652 if (f1->dest == f2->dest && b1->dest == b2->dest)
1653 reverse = false;
1654 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1655 reverse = true;
1656 else
1657 return false;
1659 set1 = pc_set (BB_END (bb1));
1660 set2 = pc_set (BB_END (bb2));
1661 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1662 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1663 reverse = !reverse;
1665 cond1 = XEXP (SET_SRC (set1), 0);
1666 cond2 = XEXP (SET_SRC (set2), 0);
1667 code1 = GET_CODE (cond1);
1668 if (reverse)
1669 code2 = reversed_comparison_code (cond2, BB_END (bb2));
1670 else
1671 code2 = GET_CODE (cond2);
1673 if (code2 == UNKNOWN)
1674 return false;
1676 /* Verify codes and operands match. */
1677 match = ((code1 == code2
1678 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1679 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1680 || (code1 == swap_condition (code2)
1681 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1682 XEXP (cond2, 0))
1683 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1684 XEXP (cond2, 1))));
1686 /* If we return true, we will join the blocks. Which means that
1687 we will only have one branch prediction bit to work with. Thus
1688 we require the existing branches to have probabilities that are
1689 roughly similar. */
1690 if (match
1691 && optimize_bb_for_speed_p (bb1)
1692 && optimize_bb_for_speed_p (bb2))
1694 profile_probability prob2;
1696 if (b1->dest == b2->dest)
1697 prob2 = b2->probability;
1698 else
1699 /* Do not use f2 probability as f2 may be forwarded. */
1700 prob2 = b2->probability.invert ();
1702 /* Fail if the difference in probabilities is greater than 50%.
1703 This rules out two well-predicted branches with opposite
1704 outcomes. */
1705 if (b1->probability.differs_lot_from_p (prob2))
1707 if (dump_file)
1709 fprintf (dump_file,
1710 "Outcomes of branch in bb %i and %i differ too"
1711 " much (", bb1->index, bb2->index);
1712 b1->probability.dump (dump_file);
1713 prob2.dump (dump_file);
1714 fprintf (dump_file, ")\n");
1716 return false;
1720 if (dump_file && match)
1721 fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1722 bb1->index, bb2->index);
1724 return match;
1727 /* Generic case - we are seeing a computed jump, table jump or trapping
1728 instruction. */
1730 /* Check whether there are tablejumps in the end of BB1 and BB2.
1731 Return true if they are identical. */
1733 rtx_insn *label1, *label2;
1734 rtx_jump_table_data *table1, *table2;
1736 if (tablejump_p (BB_END (bb1), &label1, &table1)
1737 && tablejump_p (BB_END (bb2), &label2, &table2)
1738 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1740 /* The labels should never be the same rtx. If they really are same
1741 the jump tables are same too. So disable crossjumping of blocks BB1
1742 and BB2 because when deleting the common insns in the end of BB1
1743 by delete_basic_block () the jump table would be deleted too. */
1744 /* If LABEL2 is referenced in BB1->END do not do anything
1745 because we would loose information when replacing
1746 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1747 if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1749 /* Set IDENTICAL to true when the tables are identical. */
1750 bool identical = false;
1751 rtx p1, p2;
1753 p1 = PATTERN (table1);
1754 p2 = PATTERN (table2);
1755 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1757 identical = true;
1759 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1760 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1761 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1762 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1764 int i;
1766 identical = true;
1767 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1768 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1769 identical = false;
1772 if (identical)
1774 bool match;
1776 /* Temporarily replace references to LABEL1 with LABEL2
1777 in BB1->END so that we could compare the instructions. */
1778 replace_label_in_insn (BB_END (bb1), label1, label2, false);
1780 match = (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2))
1781 == dir_both);
1782 if (dump_file && match)
1783 fprintf (dump_file,
1784 "Tablejumps in bb %i and %i match.\n",
1785 bb1->index, bb2->index);
1787 /* Set the original label in BB1->END because when deleting
1788 a block whose end is a tablejump, the tablejump referenced
1789 from the instruction is deleted too. */
1790 replace_label_in_insn (BB_END (bb1), label2, label1, false);
1792 return match;
1795 return false;
1799 /* Find the last non-debug non-note instruction in each bb, except
1800 stop when we see the NOTE_INSN_BASIC_BLOCK, as old_insns_match_p
1801 handles that case specially. old_insns_match_p does not handle
1802 other types of instruction notes. */
1803 rtx_insn *last1 = BB_END (bb1);
1804 rtx_insn *last2 = BB_END (bb2);
1805 while (!NOTE_INSN_BASIC_BLOCK_P (last1) &&
1806 (DEBUG_INSN_P (last1) || NOTE_P (last1)))
1807 last1 = PREV_INSN (last1);
1808 while (!NOTE_INSN_BASIC_BLOCK_P (last2) &&
1809 (DEBUG_INSN_P (last2) || NOTE_P (last2)))
1810 last2 = PREV_INSN (last2);
1811 gcc_assert (last1 && last2);
1813 /* First ensure that the instructions match. There may be many outgoing
1814 edges so this test is generally cheaper. */
1815 if (old_insns_match_p (mode, last1, last2) != dir_both)
1816 return false;
1818 /* Search the outgoing edges, ensure that the counts do match, find possible
1819 fallthru and exception handling edges since these needs more
1820 validation. */
1821 if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
1822 return false;
1824 bool nonfakeedges = false;
1825 FOR_EACH_EDGE (e1, ei, bb1->succs)
1827 e2 = EDGE_SUCC (bb2, ei.index);
1829 if ((e1->flags & EDGE_FAKE) == 0)
1830 nonfakeedges = true;
1832 if (e1->flags & EDGE_EH)
1833 nehedges1++;
1835 if (e2->flags & EDGE_EH)
1836 nehedges2++;
1838 if (e1->flags & EDGE_FALLTHRU)
1839 fallthru1 = e1;
1840 if (e2->flags & EDGE_FALLTHRU)
1841 fallthru2 = e2;
1844 /* If number of edges of various types does not match, fail. */
1845 if (nehedges1 != nehedges2
1846 || (fallthru1 != 0) != (fallthru2 != 0))
1847 return false;
1849 /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1850 and the last real insn doesn't have REG_ARGS_SIZE note, don't
1851 attempt to optimize, as the two basic blocks might have different
1852 REG_ARGS_SIZE depths. For noreturn calls and unconditional
1853 traps there should be REG_ARG_SIZE notes, they could be missing
1854 for __builtin_unreachable () uses though. */
1855 if (!nonfakeedges
1856 && !ACCUMULATE_OUTGOING_ARGS
1857 && (!INSN_P (last1)
1858 || !find_reg_note (last1, REG_ARGS_SIZE, NULL)))
1859 return false;
1861 /* fallthru edges must be forwarded to the same destination. */
1862 if (fallthru1)
1864 basic_block d1 = (FORWARDER_BLOCK_P (fallthru1->dest)
1865 ? single_succ (fallthru1->dest): fallthru1->dest);
1866 basic_block d2 = (FORWARDER_BLOCK_P (fallthru2->dest)
1867 ? single_succ (fallthru2->dest): fallthru2->dest);
1869 if (d1 != d2)
1870 return false;
1873 /* Ensure the same EH region. */
1875 rtx n1 = find_reg_note (last1, REG_EH_REGION, 0);
1876 rtx n2 = find_reg_note (last2, REG_EH_REGION, 0);
1878 if (!n1 && n2)
1879 return false;
1881 if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1882 return false;
1885 /* The same checks as in try_crossjump_to_edge. It is required for RTL
1886 version of sequence abstraction. */
1887 FOR_EACH_EDGE (e1, ei, bb2->succs)
1889 edge e2;
1890 edge_iterator ei;
1891 basic_block d1 = e1->dest;
1893 if (FORWARDER_BLOCK_P (d1))
1894 d1 = EDGE_SUCC (d1, 0)->dest;
1896 FOR_EACH_EDGE (e2, ei, bb1->succs)
1898 basic_block d2 = e2->dest;
1899 if (FORWARDER_BLOCK_P (d2))
1900 d2 = EDGE_SUCC (d2, 0)->dest;
1901 if (d1 == d2)
1902 break;
1905 if (!e2)
1906 return false;
1909 return true;
1912 /* Returns true if BB basic block has a preserve label. */
1914 static bool
1915 block_has_preserve_label (basic_block bb)
1917 return (bb
1918 && block_label (bb)
1919 && LABEL_PRESERVE_P (block_label (bb)));
1922 /* E1 and E2 are edges with the same destination block. Search their
1923 predecessors for common code. If found, redirect control flow from
1924 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1925 or the other way around (dir_backward). DIR specifies the allowed
1926 replacement direction. */
1928 static bool
1929 try_crossjump_to_edge (int mode, edge e1, edge e2,
1930 enum replace_direction dir)
1932 int nmatch;
1933 basic_block src1 = e1->src, src2 = e2->src;
1934 basic_block redirect_to, redirect_from, to_remove;
1935 basic_block osrc1, osrc2, redirect_edges_to, tmp;
1936 rtx_insn *newpos1, *newpos2;
1937 edge s;
1938 edge_iterator ei;
1940 newpos1 = newpos2 = NULL;
1942 /* Search backward through forwarder blocks. We don't need to worry
1943 about multiple entry or chained forwarders, as they will be optimized
1944 away. We do this to look past the unconditional jump following a
1945 conditional jump that is required due to the current CFG shape. */
1946 if (single_pred_p (src1)
1947 && FORWARDER_BLOCK_P (src1))
1948 e1 = single_pred_edge (src1), src1 = e1->src;
1950 if (single_pred_p (src2)
1951 && FORWARDER_BLOCK_P (src2))
1952 e2 = single_pred_edge (src2), src2 = e2->src;
1954 /* Nothing to do if we reach ENTRY, or a common source block. */
1955 if (src1 == ENTRY_BLOCK_PTR_FOR_FN (cfun) || src2
1956 == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1957 return false;
1958 if (src1 == src2)
1959 return false;
1961 /* Seeing more than 1 forwarder blocks would confuse us later... */
1962 if (FORWARDER_BLOCK_P (e1->dest)
1963 && FORWARDER_BLOCK_P (single_succ (e1->dest)))
1964 return false;
1966 if (FORWARDER_BLOCK_P (e2->dest)
1967 && FORWARDER_BLOCK_P (single_succ (e2->dest)))
1968 return false;
1970 /* Likewise with dead code (possibly newly created by the other optimizations
1971 of cfg_cleanup). */
1972 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1973 return false;
1975 /* Do not turn corssing edge to non-crossing or vice versa after reload. */
1976 if (BB_PARTITION (src1) != BB_PARTITION (src2)
1977 && reload_completed)
1978 return false;
1980 /* Look for the common insn sequence, part the first ... */
1981 if (!outgoing_edges_match (mode, src1, src2))
1982 return false;
1984 /* ... and part the second. */
1985 nmatch = flow_find_cross_jump (src1, src2, &newpos1, &newpos2, &dir);
1987 osrc1 = src1;
1988 osrc2 = src2;
1989 if (newpos1 != NULL_RTX)
1990 src1 = BLOCK_FOR_INSN (newpos1);
1991 if (newpos2 != NULL_RTX)
1992 src2 = BLOCK_FOR_INSN (newpos2);
1994 /* Check that SRC1 and SRC2 have preds again. They may have changed
1995 above due to the call to flow_find_cross_jump. */
1996 if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1997 return false;
1999 if (dir == dir_backward)
2001 std::swap (osrc1, osrc2);
2002 std::swap (src1, src2);
2003 std::swap (e1, e2);
2004 std::swap (newpos1, newpos2);
2007 /* Don't proceed with the crossjump unless we found a sufficient number
2008 of matching instructions or the 'from' block was totally matched
2009 (such that its predecessors will hopefully be redirected and the
2010 block removed). */
2011 if ((nmatch < param_min_crossjump_insns)
2012 && (newpos1 != BB_HEAD (src1)))
2013 return false;
2015 /* Avoid deleting preserve label when redirecting ABNORMAL edges. */
2016 if (block_has_preserve_label (e1->dest)
2017 && (e1->flags & EDGE_ABNORMAL))
2018 return false;
2020 /* Here we know that the insns in the end of SRC1 which are common with SRC2
2021 will be deleted.
2022 If we have tablejumps in the end of SRC1 and SRC2
2023 they have been already compared for equivalence in outgoing_edges_match ()
2024 so replace the references to TABLE1 by references to TABLE2. */
2026 rtx_insn *label1, *label2;
2027 rtx_jump_table_data *table1, *table2;
2029 if (tablejump_p (BB_END (osrc1), &label1, &table1)
2030 && tablejump_p (BB_END (osrc2), &label2, &table2)
2031 && label1 != label2)
2033 rtx_insn *insn;
2035 /* Replace references to LABEL1 with LABEL2. */
2036 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2038 /* Do not replace the label in SRC1->END because when deleting
2039 a block whose end is a tablejump, the tablejump referenced
2040 from the instruction is deleted too. */
2041 if (insn != BB_END (osrc1))
2042 replace_label_in_insn (insn, label1, label2, true);
2047 /* Avoid splitting if possible. We must always split when SRC2 has
2048 EH predecessor edges, or we may end up with basic blocks with both
2049 normal and EH predecessor edges. */
2050 if (newpos2 == BB_HEAD (src2)
2051 && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
2052 redirect_to = src2;
2053 else
2055 if (newpos2 == BB_HEAD (src2))
2057 /* Skip possible basic block header. */
2058 if (LABEL_P (newpos2))
2059 newpos2 = NEXT_INSN (newpos2);
2060 while (DEBUG_INSN_P (newpos2))
2061 newpos2 = NEXT_INSN (newpos2);
2062 if (NOTE_P (newpos2))
2063 newpos2 = NEXT_INSN (newpos2);
2064 while (DEBUG_INSN_P (newpos2))
2065 newpos2 = NEXT_INSN (newpos2);
2068 if (dump_file)
2069 fprintf (dump_file, "Splitting bb %i before %i insns\n",
2070 src2->index, nmatch);
2071 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
2074 if (dump_file)
2075 fprintf (dump_file,
2076 "Cross jumping from bb %i to bb %i; %i common insns\n",
2077 src1->index, src2->index, nmatch);
2079 /* We may have some registers visible through the block. */
2080 df_set_bb_dirty (redirect_to);
2082 if (osrc2 == src2)
2083 redirect_edges_to = redirect_to;
2084 else
2085 redirect_edges_to = osrc2;
2087 /* Recompute the counts of destinations of outgoing edges. */
2088 FOR_EACH_EDGE (s, ei, redirect_edges_to->succs)
2090 edge s2;
2091 edge_iterator ei;
2092 basic_block d = s->dest;
2094 if (FORWARDER_BLOCK_P (d))
2095 d = single_succ (d);
2097 FOR_EACH_EDGE (s2, ei, src1->succs)
2099 basic_block d2 = s2->dest;
2100 if (FORWARDER_BLOCK_P (d2))
2101 d2 = single_succ (d2);
2102 if (d == d2)
2103 break;
2106 /* Take care to update possible forwarder blocks. We verified
2107 that there is no more than one in the chain, so we can't run
2108 into infinite loop. */
2109 if (FORWARDER_BLOCK_P (s->dest))
2110 s->dest->count += s->count ();
2112 if (FORWARDER_BLOCK_P (s2->dest))
2113 s2->dest->count -= s->count ();
2115 s->probability = s->probability.combine_with_count
2116 (redirect_edges_to->count,
2117 s2->probability, src1->count);
2120 /* Adjust count for the block. An earlier jump
2121 threading pass may have left the profile in an inconsistent
2122 state (see update_bb_profile_for_threading) so we must be
2123 prepared for overflows. */
2124 tmp = redirect_to;
2127 tmp->count += src1->count;
2128 if (tmp == redirect_edges_to)
2129 break;
2130 tmp = find_fallthru_edge (tmp->succs)->dest;
2132 while (true);
2133 update_br_prob_note (redirect_edges_to);
2135 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
2137 /* Skip possible basic block header. */
2138 if (LABEL_P (newpos1))
2139 newpos1 = NEXT_INSN (newpos1);
2141 while (DEBUG_INSN_P (newpos1))
2142 newpos1 = NEXT_INSN (newpos1);
2144 if (NOTE_INSN_BASIC_BLOCK_P (newpos1))
2145 newpos1 = NEXT_INSN (newpos1);
2147 /* Skip also prologue and function markers. */
2148 while (DEBUG_INSN_P (newpos1)
2149 || (NOTE_P (newpos1)
2150 && (NOTE_KIND (newpos1) == NOTE_INSN_PROLOGUE_END
2151 || NOTE_KIND (newpos1) == NOTE_INSN_FUNCTION_BEG)))
2152 newpos1 = NEXT_INSN (newpos1);
2154 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
2155 to_remove = single_succ (redirect_from);
2157 redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
2158 delete_basic_block (to_remove);
2160 update_forwarder_flag (redirect_from);
2161 if (redirect_to != src2)
2162 update_forwarder_flag (src2);
2164 return true;
2167 /* Search the predecessors of BB for common insn sequences. When found,
2168 share code between them by redirecting control flow. Return true if
2169 any changes made. */
2171 static bool
2172 try_crossjump_bb (int mode, basic_block bb)
2174 edge e, e2, fallthru;
2175 bool changed;
2176 unsigned max, ix, ix2;
2178 /* Nothing to do if there is not at least two incoming edges. */
2179 if (EDGE_COUNT (bb->preds) < 2)
2180 return false;
2182 /* Don't crossjump if this block ends in a computed jump,
2183 unless we are optimizing for size. */
2184 if (optimize_bb_for_size_p (bb)
2185 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
2186 && computed_jump_p (BB_END (bb)))
2187 return false;
2189 /* If we are partitioning hot/cold basic blocks, we don't want to
2190 mess up unconditional or indirect jumps that cross between hot
2191 and cold sections.
2193 Basic block partitioning may result in some jumps that appear to
2194 be optimizable (or blocks that appear to be mergeable), but which really
2195 must be left untouched (they are required to make it safely across
2196 partition boundaries). See the comments at the top of
2197 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
2199 if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
2200 BB_PARTITION (EDGE_PRED (bb, 1)->src)
2201 || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
2202 return false;
2204 /* It is always cheapest to redirect a block that ends in a branch to
2205 a block that falls through into BB, as that adds no branches to the
2206 program. We'll try that combination first. */
2207 fallthru = NULL;
2208 max = param_max_crossjump_edges;
2210 if (EDGE_COUNT (bb->preds) > max)
2211 return false;
2213 fallthru = find_fallthru_edge (bb->preds);
2215 changed = false;
2216 for (ix = 0; ix < EDGE_COUNT (bb->preds);)
2218 e = EDGE_PRED (bb, ix);
2219 ix++;
2221 /* As noted above, first try with the fallthru predecessor (or, a
2222 fallthru predecessor if we are in cfglayout mode). */
2223 if (fallthru)
2225 /* Don't combine the fallthru edge into anything else.
2226 If there is a match, we'll do it the other way around. */
2227 if (e == fallthru)
2228 continue;
2229 /* If nothing changed since the last attempt, there is nothing
2230 we can do. */
2231 if (!first_pass
2232 && !((e->src->flags & BB_MODIFIED)
2233 || (fallthru->src->flags & BB_MODIFIED)))
2234 continue;
2236 if (try_crossjump_to_edge (mode, e, fallthru, dir_forward))
2238 changed = true;
2239 ix = 0;
2240 continue;
2244 /* Non-obvious work limiting check: Recognize that we're going
2245 to call try_crossjump_bb on every basic block. So if we have
2246 two blocks with lots of outgoing edges (a switch) and they
2247 share lots of common destinations, then we would do the
2248 cross-jump check once for each common destination.
2250 Now, if the blocks actually are cross-jump candidates, then
2251 all of their destinations will be shared. Which means that
2252 we only need check them for cross-jump candidacy once. We
2253 can eliminate redundant checks of crossjump(A,B) by arbitrarily
2254 choosing to do the check from the block for which the edge
2255 in question is the first successor of A. */
2256 if (EDGE_SUCC (e->src, 0) != e)
2257 continue;
2259 for (ix2 = 0; ix2 < EDGE_COUNT (bb->preds); ix2++)
2261 e2 = EDGE_PRED (bb, ix2);
2263 if (e2 == e)
2264 continue;
2266 /* We've already checked the fallthru edge above. */
2267 if (e2 == fallthru)
2268 continue;
2270 /* The "first successor" check above only prevents multiple
2271 checks of crossjump(A,B). In order to prevent redundant
2272 checks of crossjump(B,A), require that A be the block
2273 with the lowest index. */
2274 if (e->src->index > e2->src->index)
2275 continue;
2277 /* If nothing changed since the last attempt, there is nothing
2278 we can do. */
2279 if (!first_pass
2280 && !((e->src->flags & BB_MODIFIED)
2281 || (e2->src->flags & BB_MODIFIED)))
2282 continue;
2284 /* Both e and e2 are not fallthru edges, so we can crossjump in either
2285 direction. */
2286 if (try_crossjump_to_edge (mode, e, e2, dir_both))
2288 changed = true;
2289 ix = 0;
2290 break;
2295 if (changed)
2296 crossjumps_occurred = true;
2298 return changed;
2301 /* Search the successors of BB for common insn sequences. When found,
2302 share code between them by moving it across the basic block
2303 boundary. Return true if any changes made. */
2305 static bool
2306 try_head_merge_bb (basic_block bb)
2308 basic_block final_dest_bb = NULL;
2309 int max_match = INT_MAX;
2310 edge e0;
2311 rtx_insn **headptr, **currptr, **nextptr;
2312 bool changed, moveall;
2313 unsigned ix;
2314 rtx_insn *e0_last_head;
2315 rtx cond;
2316 rtx_insn *move_before;
2317 unsigned nedges = EDGE_COUNT (bb->succs);
2318 rtx_insn *jump = BB_END (bb);
2319 regset live, live_union;
2321 /* Nothing to do if there is not at least two outgoing edges. */
2322 if (nedges < 2)
2323 return false;
2325 /* Don't crossjump if this block ends in a computed jump,
2326 unless we are optimizing for size. */
2327 if (optimize_bb_for_size_p (bb)
2328 && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
2329 && computed_jump_p (BB_END (bb)))
2330 return false;
2332 cond = get_condition (jump, &move_before, true, false);
2333 if (cond == NULL_RTX)
2334 move_before = jump;
2336 for (ix = 0; ix < nedges; ix++)
2337 if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
2338 return false;
2340 for (ix = 0; ix < nedges; ix++)
2342 edge e = EDGE_SUCC (bb, ix);
2343 basic_block other_bb = e->dest;
2345 if (df_get_bb_dirty (other_bb))
2347 block_was_dirty = true;
2348 return false;
2351 if (e->flags & EDGE_ABNORMAL)
2352 return false;
2354 /* Normally, all destination blocks must only be reachable from this
2355 block, i.e. they must have one incoming edge.
2357 There is one special case we can handle, that of multiple consecutive
2358 jumps where the first jumps to one of the targets of the second jump.
2359 This happens frequently in switch statements for default labels.
2360 The structure is as follows:
2361 FINAL_DEST_BB
2362 ....
2363 if (cond) jump A;
2364 fall through
2366 jump with targets A, B, C, D...
2368 has two incoming edges, from FINAL_DEST_BB and BB
2370 In this case, we can try to move the insns through BB and into
2371 FINAL_DEST_BB. */
2372 if (EDGE_COUNT (other_bb->preds) != 1)
2374 edge incoming_edge, incoming_bb_other_edge;
2375 edge_iterator ei;
2377 if (final_dest_bb != NULL
2378 || EDGE_COUNT (other_bb->preds) != 2)
2379 return false;
2381 /* We must be able to move the insns across the whole block. */
2382 move_before = BB_HEAD (bb);
2383 while (!NONDEBUG_INSN_P (move_before))
2384 move_before = NEXT_INSN (move_before);
2386 if (EDGE_COUNT (bb->preds) != 1)
2387 return false;
2388 incoming_edge = EDGE_PRED (bb, 0);
2389 final_dest_bb = incoming_edge->src;
2390 if (EDGE_COUNT (final_dest_bb->succs) != 2)
2391 return false;
2392 FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
2393 if (incoming_bb_other_edge != incoming_edge)
2394 break;
2395 if (incoming_bb_other_edge->dest != other_bb)
2396 return false;
2400 e0 = EDGE_SUCC (bb, 0);
2401 e0_last_head = NULL;
2402 changed = false;
2404 for (ix = 1; ix < nedges; ix++)
2406 edge e = EDGE_SUCC (bb, ix);
2407 rtx_insn *e0_last, *e_last;
2408 int nmatch;
2410 nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
2411 &e0_last, &e_last, 0);
2412 if (nmatch == 0)
2413 return false;
2415 if (nmatch < max_match)
2417 max_match = nmatch;
2418 e0_last_head = e0_last;
2422 /* If we matched an entire block, we probably have to avoid moving the
2423 last insn. */
2424 if (max_match > 0
2425 && e0_last_head == BB_END (e0->dest)
2426 && (find_reg_note (e0_last_head, REG_EH_REGION, 0)
2427 || control_flow_insn_p (e0_last_head)))
2429 max_match--;
2430 if (max_match == 0)
2431 return false;
2432 e0_last_head = prev_real_nondebug_insn (e0_last_head);
2435 if (max_match == 0)
2436 return false;
2438 /* We must find a union of the live registers at each of the end points. */
2439 live = BITMAP_ALLOC (NULL);
2440 live_union = BITMAP_ALLOC (NULL);
2442 currptr = XNEWVEC (rtx_insn *, nedges);
2443 headptr = XNEWVEC (rtx_insn *, nedges);
2444 nextptr = XNEWVEC (rtx_insn *, nedges);
2446 for (ix = 0; ix < nedges; ix++)
2448 int j;
2449 basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
2450 rtx_insn *head = BB_HEAD (merge_bb);
2452 while (!NONDEBUG_INSN_P (head))
2453 head = NEXT_INSN (head);
2454 headptr[ix] = head;
2455 currptr[ix] = head;
2457 /* Compute the end point and live information */
2458 for (j = 1; j < max_match; j++)
2460 head = NEXT_INSN (head);
2461 while (!NONDEBUG_INSN_P (head));
2462 simulate_backwards_to_point (merge_bb, live, head);
2463 IOR_REG_SET (live_union, live);
2466 /* If we're moving across two blocks, verify the validity of the
2467 first move, then adjust the target and let the loop below deal
2468 with the final move. */
2469 if (final_dest_bb != NULL)
2471 rtx_insn *move_upto;
2473 moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
2474 jump, e0->dest, live_union,
2475 NULL, &move_upto);
2476 if (!moveall)
2478 if (move_upto == NULL_RTX)
2479 goto out;
2481 while (e0_last_head != move_upto)
2483 df_simulate_one_insn_backwards (e0->dest, e0_last_head,
2484 live_union);
2485 e0_last_head = PREV_INSN (e0_last_head);
2488 if (e0_last_head == NULL_RTX)
2489 goto out;
2491 jump = BB_END (final_dest_bb);
2492 cond = get_condition (jump, &move_before, true, false);
2493 if (cond == NULL_RTX)
2494 move_before = jump;
2499 rtx_insn *move_upto;
2500 moveall = can_move_insns_across (currptr[0], e0_last_head,
2501 move_before, jump, e0->dest, live_union,
2502 NULL, &move_upto);
2503 if (!moveall && move_upto == NULL_RTX)
2505 if (jump == move_before)
2506 break;
2508 /* Try again, using a different insertion point. */
2509 move_before = jump;
2511 continue;
2514 if (final_dest_bb && !moveall)
2515 /* We haven't checked whether a partial move would be OK for the first
2516 move, so we have to fail this case. */
2517 break;
2519 changed = true;
2520 for (;;)
2522 if (currptr[0] == move_upto)
2523 break;
2524 for (ix = 0; ix < nedges; ix++)
2526 rtx_insn *curr = currptr[ix];
2528 curr = NEXT_INSN (curr);
2529 while (!NONDEBUG_INSN_P (curr));
2530 currptr[ix] = curr;
2534 /* If we can't currently move all of the identical insns, remember
2535 each insn after the range that we'll merge. */
2536 if (!moveall)
2537 for (ix = 0; ix < nedges; ix++)
2539 rtx_insn *curr = currptr[ix];
2541 curr = NEXT_INSN (curr);
2542 while (!NONDEBUG_INSN_P (curr));
2543 nextptr[ix] = curr;
2546 reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
2547 df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
2548 if (final_dest_bb != NULL)
2549 df_set_bb_dirty (final_dest_bb);
2550 df_set_bb_dirty (bb);
2551 for (ix = 1; ix < nedges; ix++)
2553 df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
2554 delete_insn_chain (headptr[ix], currptr[ix], false);
2556 if (!moveall)
2558 if (jump == move_before)
2559 break;
2561 /* For the unmerged insns, try a different insertion point. */
2562 move_before = jump;
2564 for (ix = 0; ix < nedges; ix++)
2565 currptr[ix] = headptr[ix] = nextptr[ix];
2568 while (!moveall);
2570 out:
2571 free (currptr);
2572 free (headptr);
2573 free (nextptr);
2575 crossjumps_occurred |= changed;
2577 return changed;
2580 /* Return true if BB contains just bb note, or bb note followed
2581 by only DEBUG_INSNs. */
2583 static bool
2584 trivially_empty_bb_p (basic_block bb)
2586 rtx_insn *insn = BB_END (bb);
2588 while (1)
2590 if (insn == BB_HEAD (bb))
2591 return true;
2592 if (!DEBUG_INSN_P (insn))
2593 return false;
2594 insn = PREV_INSN (insn);
2598 /* Return true if BB contains just a return and possibly a USE of the
2599 return value. Fill in *RET and *USE with the return and use insns
2600 if any found, otherwise NULL. All CLOBBERs are ignored. */
2602 bool
2603 bb_is_just_return (basic_block bb, rtx_insn **ret, rtx_insn **use)
2605 *ret = *use = NULL;
2606 rtx_insn *insn;
2608 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
2609 return false;
2611 FOR_BB_INSNS_REVERSE (bb, insn)
2612 if (NONDEBUG_INSN_P (insn))
2614 rtx pat = PATTERN (insn);
2616 if (!*ret && ANY_RETURN_P (pat))
2617 *ret = insn;
2618 else if (*ret && !*use && GET_CODE (pat) == USE
2619 && REG_P (XEXP (pat, 0))
2620 && REG_FUNCTION_VALUE_P (XEXP (pat, 0)))
2621 *use = insn;
2622 else if (GET_CODE (pat) != CLOBBER)
2623 return false;
2626 return !!*ret;
2629 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2630 instructions etc. Return nonzero if changes were made. */
2632 static bool
2633 try_optimize_cfg (int mode)
2635 bool changed_overall = false;
2636 bool changed;
2637 int iterations = 0;
2638 basic_block bb, b, next;
2640 if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
2641 clear_bb_flags ();
2643 crossjumps_occurred = false;
2645 FOR_EACH_BB_FN (bb, cfun)
2646 update_forwarder_flag (bb);
2648 if (! targetm.cannot_modify_jumps_p ())
2650 first_pass = true;
2651 /* Attempt to merge blocks as made possible by edge removal. If
2652 a block has only one successor, and the successor has only
2653 one predecessor, they may be combined. */
2656 block_was_dirty = false;
2657 changed = false;
2658 iterations++;
2660 if (dump_file)
2661 fprintf (dump_file,
2662 "\n\ntry_optimize_cfg iteration %i\n\n",
2663 iterations);
2665 for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
2666 != EXIT_BLOCK_PTR_FOR_FN (cfun);)
2668 basic_block c;
2669 edge s;
2670 bool changed_here = false;
2672 /* Delete trivially dead basic blocks. This is either
2673 blocks with no predecessors, or empty blocks with no
2674 successors. However if the empty block with no
2675 successors is the successor of the ENTRY_BLOCK, it is
2676 kept. This ensures that the ENTRY_BLOCK will have a
2677 successor which is a precondition for many RTL
2678 passes. Empty blocks may result from expanding
2679 __builtin_unreachable (). */
2680 if (EDGE_COUNT (b->preds) == 0
2681 || (EDGE_COUNT (b->succs) == 0
2682 && trivially_empty_bb_p (b)
2683 && single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest
2684 != b))
2686 c = b->prev_bb;
2687 if (EDGE_COUNT (b->preds) > 0)
2689 edge e;
2690 edge_iterator ei;
2692 if (current_ir_type () == IR_RTL_CFGLAYOUT)
2694 rtx_insn *insn;
2695 for (insn = BB_FOOTER (b);
2696 insn; insn = NEXT_INSN (insn))
2697 if (BARRIER_P (insn))
2698 break;
2699 if (insn)
2700 FOR_EACH_EDGE (e, ei, b->preds)
2701 if ((e->flags & EDGE_FALLTHRU))
2703 if (BB_FOOTER (b)
2704 && BB_FOOTER (e->src) == NULL)
2706 BB_FOOTER (e->src) = BB_FOOTER (b);
2707 BB_FOOTER (b) = NULL;
2709 else
2710 emit_barrier_after_bb (e->src);
2713 else
2715 rtx_insn *last = get_last_bb_insn (b);
2716 if (last && BARRIER_P (last))
2717 FOR_EACH_EDGE (e, ei, b->preds)
2718 if ((e->flags & EDGE_FALLTHRU))
2719 emit_barrier_after (BB_END (e->src));
2722 delete_basic_block (b);
2723 changed = true;
2724 /* Avoid trying to remove the exit block. */
2725 b = (c == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? c->next_bb : c);
2726 continue;
2729 /* Remove code labels no longer used. */
2730 if (single_pred_p (b)
2731 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2732 && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
2733 && LABEL_P (BB_HEAD (b))
2734 && !LABEL_PRESERVE_P (BB_HEAD (b))
2735 /* If the previous block ends with a branch to this
2736 block, we can't delete the label. Normally this
2737 is a condjump that is yet to be simplified, but
2738 if CASE_DROPS_THRU, this can be a tablejump with
2739 some element going to the same place as the
2740 default (fallthru). */
2741 && (single_pred (b) == ENTRY_BLOCK_PTR_FOR_FN (cfun)
2742 || !JUMP_P (BB_END (single_pred (b)))
2743 || ! label_is_jump_target_p (BB_HEAD (b),
2744 BB_END (single_pred (b)))))
2746 delete_insn (BB_HEAD (b));
2747 if (dump_file)
2748 fprintf (dump_file, "Deleted label in block %i.\n",
2749 b->index);
2752 /* If we fall through an empty block, we can remove it. */
2753 if (!(mode & (CLEANUP_CFGLAYOUT | CLEANUP_NO_INSN_DEL))
2754 && single_pred_p (b)
2755 && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2756 && !LABEL_P (BB_HEAD (b))
2757 && FORWARDER_BLOCK_P (b)
2758 /* Note that forwarder_block_p true ensures that
2759 there is a successor for this block. */
2760 && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
2761 && n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS + 1)
2763 if (dump_file)
2764 fprintf (dump_file,
2765 "Deleting fallthru block %i.\n",
2766 b->index);
2768 c = ((b->prev_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2769 ? b->next_bb : b->prev_bb);
2770 redirect_edge_succ_nodup (single_pred_edge (b),
2771 single_succ (b));
2772 delete_basic_block (b);
2773 changed = true;
2774 b = c;
2775 continue;
2778 /* Merge B with its single successor, if any. */
2779 if (single_succ_p (b)
2780 && (s = single_succ_edge (b))
2781 && !(s->flags & EDGE_COMPLEX)
2782 && (c = s->dest) != EXIT_BLOCK_PTR_FOR_FN (cfun)
2783 && single_pred_p (c)
2784 && b != c)
2786 /* When not in cfg_layout mode use code aware of reordering
2787 INSN. This code possibly creates new basic blocks so it
2788 does not fit merge_blocks interface and is kept here in
2789 hope that it will become useless once more of compiler
2790 is transformed to use cfg_layout mode. */
2792 if ((mode & CLEANUP_CFGLAYOUT)
2793 && can_merge_blocks_p (b, c))
2795 merge_blocks (b, c);
2796 update_forwarder_flag (b);
2797 changed_here = true;
2799 else if (!(mode & CLEANUP_CFGLAYOUT)
2800 /* If the jump insn has side effects,
2801 we can't kill the edge. */
2802 && (!JUMP_P (BB_END (b))
2803 || (reload_completed
2804 ? simplejump_p (BB_END (b))
2805 : (onlyjump_p (BB_END (b))
2806 && !tablejump_p (BB_END (b),
2807 NULL, NULL))))
2808 && (next = merge_blocks_move (s, b, c, mode)))
2810 b = next;
2811 changed_here = true;
2815 /* Try to change a branch to a return to just that return. */
2816 rtx_insn *ret, *use;
2817 if (single_succ_p (b)
2818 && onlyjump_p (BB_END (b))
2819 && bb_is_just_return (single_succ (b), &ret, &use))
2821 if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2822 PATTERN (ret), 0))
2824 if (use)
2825 emit_insn_before (copy_insn (PATTERN (use)),
2826 BB_END (b));
2827 if (dump_file)
2828 fprintf (dump_file, "Changed jump %d->%d to return.\n",
2829 b->index, single_succ (b)->index);
2830 redirect_edge_succ (single_succ_edge (b),
2831 EXIT_BLOCK_PTR_FOR_FN (cfun));
2832 single_succ_edge (b)->flags &= ~EDGE_CROSSING;
2833 changed_here = true;
2837 /* Try to change a conditional branch to a return to the
2838 respective conditional return. */
2839 if (EDGE_COUNT (b->succs) == 2
2840 && any_condjump_p (BB_END (b))
2841 && bb_is_just_return (BRANCH_EDGE (b)->dest, &ret, &use))
2843 if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2844 PATTERN (ret), 0))
2846 if (use)
2847 emit_insn_before (copy_insn (PATTERN (use)),
2848 BB_END (b));
2849 if (dump_file)
2850 fprintf (dump_file, "Changed conditional jump %d->%d "
2851 "to conditional return.\n",
2852 b->index, BRANCH_EDGE (b)->dest->index);
2853 redirect_edge_succ (BRANCH_EDGE (b),
2854 EXIT_BLOCK_PTR_FOR_FN (cfun));
2855 BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
2856 changed_here = true;
2860 /* Try to flip a conditional branch that falls through to
2861 a return so that it becomes a conditional return and a
2862 new jump to the original branch target. */
2863 if (EDGE_COUNT (b->succs) == 2
2864 && BRANCH_EDGE (b)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2865 && any_condjump_p (BB_END (b))
2866 && bb_is_just_return (FALLTHRU_EDGE (b)->dest, &ret, &use))
2868 if (invert_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2869 JUMP_LABEL (BB_END (b)), 0))
2871 basic_block new_ft = BRANCH_EDGE (b)->dest;
2872 if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2873 PATTERN (ret), 0))
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 "
2880 "%d->%d to conditional return, adding "
2881 "fall-through jump.\n",
2882 b->index, BRANCH_EDGE (b)->dest->index);
2883 redirect_edge_succ (BRANCH_EDGE (b),
2884 EXIT_BLOCK_PTR_FOR_FN (cfun));
2885 BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
2886 std::swap (BRANCH_EDGE (b)->probability,
2887 FALLTHRU_EDGE (b)->probability);
2888 update_br_prob_note (b);
2889 basic_block jb = force_nonfallthru (FALLTHRU_EDGE (b));
2890 notice_new_block (jb);
2891 if (!redirect_jump (as_a <rtx_jump_insn *> (BB_END (jb)),
2892 block_label (new_ft), 0))
2893 gcc_unreachable ();
2894 redirect_edge_succ (single_succ_edge (jb), new_ft);
2895 changed_here = true;
2897 else
2899 /* Invert the jump back to what it was. This should
2900 never fail. */
2901 if (!invert_jump (as_a <rtx_jump_insn *> (BB_END (b)),
2902 JUMP_LABEL (BB_END (b)), 0))
2903 gcc_unreachable ();
2908 /* Simplify branch over branch. */
2909 if ((mode & CLEANUP_EXPENSIVE)
2910 && !(mode & CLEANUP_CFGLAYOUT)
2911 && try_simplify_condjump (b))
2912 changed_here = true;
2914 /* If B has a single outgoing edge, but uses a
2915 non-trivial jump instruction without side-effects, we
2916 can either delete the jump entirely, or replace it
2917 with a simple unconditional jump. */
2918 if (single_succ_p (b)
2919 && single_succ (b) != EXIT_BLOCK_PTR_FOR_FN (cfun)
2920 && onlyjump_p (BB_END (b))
2921 && !CROSSING_JUMP_P (BB_END (b))
2922 && try_redirect_by_replacing_jump (single_succ_edge (b),
2923 single_succ (b),
2924 (mode & CLEANUP_CFGLAYOUT) != 0))
2926 update_forwarder_flag (b);
2927 changed_here = true;
2930 /* Simplify branch to branch. */
2931 if (try_forward_edges (mode, b))
2933 update_forwarder_flag (b);
2934 changed_here = true;
2937 /* Look for shared code between blocks. */
2938 if ((mode & CLEANUP_CROSSJUMP)
2939 && try_crossjump_bb (mode, b))
2940 changed_here = true;
2942 if ((mode & CLEANUP_CROSSJUMP)
2943 /* This can lengthen register lifetimes. Do it only after
2944 reload. */
2945 && reload_completed
2946 && try_head_merge_bb (b))
2947 changed_here = true;
2949 /* Don't get confused by the index shift caused by
2950 deleting blocks. */
2951 if (!changed_here)
2952 b = b->next_bb;
2953 else
2954 changed = true;
2957 if ((mode & CLEANUP_CROSSJUMP)
2958 && try_crossjump_bb (mode, EXIT_BLOCK_PTR_FOR_FN (cfun)))
2959 changed = true;
2961 if (block_was_dirty)
2963 /* This should only be set by head-merging. */
2964 gcc_assert (mode & CLEANUP_CROSSJUMP);
2965 df_analyze ();
2968 if (changed)
2970 /* Edge forwarding in particular can cause hot blocks previously
2971 reached by both hot and cold blocks to become dominated only
2972 by cold blocks. This will cause the verification below to fail,
2973 and lead to now cold code in the hot section. This is not easy
2974 to detect and fix during edge forwarding, and in some cases
2975 is only visible after newly unreachable blocks are deleted,
2976 which will be done in fixup_partitions. */
2977 if ((mode & CLEANUP_NO_PARTITIONING) == 0)
2979 fixup_partitions ();
2980 checking_verify_flow_info ();
2984 changed_overall |= changed;
2985 first_pass = false;
2987 while (changed);
2990 FOR_ALL_BB_FN (b, cfun)
2991 b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
2993 return changed_overall;
2996 /* Delete all unreachable basic blocks. */
2998 bool
2999 delete_unreachable_blocks (void)
3001 bool changed = false;
3002 basic_block b, prev_bb;
3004 find_unreachable_blocks ();
3006 /* When we're in GIMPLE mode and there may be debug bind insns, we
3007 should delete blocks in reverse dominator order, so as to get a
3008 chance to substitute all released DEFs into debug bind stmts. If
3009 we don't have dominators information, walking blocks backward
3010 gets us a better chance of retaining most debug information than
3011 otherwise. */
3012 if (MAY_HAVE_DEBUG_BIND_INSNS && current_ir_type () == IR_GIMPLE
3013 && dom_info_available_p (CDI_DOMINATORS))
3015 for (b = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
3016 b != ENTRY_BLOCK_PTR_FOR_FN (cfun); b = prev_bb)
3018 prev_bb = b->prev_bb;
3020 if (!(b->flags & BB_REACHABLE))
3022 /* Speed up the removal of blocks that don't dominate
3023 others. Walking backwards, this should be the common
3024 case. */
3025 if (!first_dom_son (CDI_DOMINATORS, b))
3026 delete_basic_block (b);
3027 else
3029 auto_vec<basic_block> h
3030 = get_all_dominated_blocks (CDI_DOMINATORS, b);
3032 while (h.length ())
3034 b = h.pop ();
3036 prev_bb = b->prev_bb;
3038 gcc_assert (!(b->flags & BB_REACHABLE));
3040 delete_basic_block (b);
3044 changed = true;
3048 else
3050 for (b = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
3051 b != ENTRY_BLOCK_PTR_FOR_FN (cfun); b = prev_bb)
3053 prev_bb = b->prev_bb;
3055 if (!(b->flags & BB_REACHABLE))
3057 delete_basic_block (b);
3058 changed = true;
3063 if (changed)
3064 tidy_fallthru_edges ();
3065 return changed;
3068 /* Delete any jump tables never referenced. We can't delete them at the
3069 time of removing tablejump insn as they are referenced by the preceding
3070 insns computing the destination, so we delay deleting and garbagecollect
3071 them once life information is computed. */
3072 void
3073 delete_dead_jumptables (void)
3075 basic_block bb;
3077 /* A dead jump table does not belong to any basic block. Scan insns
3078 between two adjacent basic blocks. */
3079 FOR_EACH_BB_FN (bb, cfun)
3081 rtx_insn *insn, *next;
3083 for (insn = NEXT_INSN (BB_END (bb));
3084 insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
3085 insn = next)
3087 next = NEXT_INSN (insn);
3088 if (LABEL_P (insn)
3089 && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
3090 && JUMP_TABLE_DATA_P (next))
3092 rtx_insn *label = insn, *jump = next;
3094 if (dump_file)
3095 fprintf (dump_file, "Dead jumptable %i removed\n",
3096 INSN_UID (insn));
3098 next = NEXT_INSN (next);
3099 delete_insn (jump);
3100 delete_insn (label);
3107 /* Tidy the CFG by deleting unreachable code and whatnot. */
3109 bool
3110 cleanup_cfg (int mode)
3112 bool changed = false;
3114 /* Set the cfglayout mode flag here. We could update all the callers
3115 but that is just inconvenient, especially given that we eventually
3116 want to have cfglayout mode as the default. */
3117 if (current_ir_type () == IR_RTL_CFGLAYOUT)
3118 mode |= CLEANUP_CFGLAYOUT;
3120 timevar_push (TV_CLEANUP_CFG);
3121 if (delete_unreachable_blocks ())
3123 changed = true;
3124 /* We've possibly created trivially dead code. Cleanup it right
3125 now to introduce more opportunities for try_optimize_cfg. */
3126 if (!(mode & (CLEANUP_NO_INSN_DEL))
3127 && !reload_completed)
3128 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3131 compact_blocks ();
3133 /* To tail-merge blocks ending in the same noreturn function (e.g.
3134 a call to abort) we have to insert fake edges to exit. Do this
3135 here once. The fake edges do not interfere with any other CFG
3136 cleanups. */
3137 if (mode & CLEANUP_CROSSJUMP)
3138 add_noreturn_fake_exit_edges ();
3140 if (!dbg_cnt (cfg_cleanup))
3141 return changed;
3143 while (try_optimize_cfg (mode))
3145 delete_unreachable_blocks (), changed = true;
3146 if (!(mode & CLEANUP_NO_INSN_DEL))
3148 /* Try to remove some trivially dead insns when doing an expensive
3149 cleanup. But delete_trivially_dead_insns doesn't work after
3150 reload (it only handles pseudos) and run_fast_dce is too costly
3151 to run in every iteration.
3153 For effective cross jumping, we really want to run a fast DCE to
3154 clean up any dead conditions, or they get in the way of performing
3155 useful tail merges.
3157 Other transformations in cleanup_cfg are not so sensitive to dead
3158 code, so delete_trivially_dead_insns or even doing nothing at all
3159 is good enough. */
3160 if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
3161 && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
3162 break;
3163 if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occurred)
3165 run_fast_dce ();
3166 mode &= ~CLEANUP_FORCE_FAST_DCE;
3169 else
3170 break;
3173 if (mode & CLEANUP_CROSSJUMP)
3174 remove_fake_exit_edges ();
3176 if (mode & CLEANUP_FORCE_FAST_DCE)
3177 run_fast_dce ();
3179 /* Don't call delete_dead_jumptables in cfglayout mode, because
3180 that function assumes that jump tables are in the insns stream.
3181 But we also don't _have_ to delete dead jumptables in cfglayout
3182 mode because we shouldn't even be looking at things that are
3183 not in a basic block. Dead jumptables are cleaned up when
3184 going out of cfglayout mode. */
3185 if (!(mode & CLEANUP_CFGLAYOUT))
3186 delete_dead_jumptables ();
3188 /* ??? We probably do this way too often. */
3189 if (current_loops
3190 && (changed
3191 || (mode & CLEANUP_CFG_CHANGED)))
3193 timevar_push (TV_REPAIR_LOOPS);
3194 /* The above doesn't preserve dominance info if available. */
3195 gcc_assert (!dom_info_available_p (CDI_DOMINATORS));
3196 calculate_dominance_info (CDI_DOMINATORS);
3197 fix_loop_structure (NULL);
3198 free_dominance_info (CDI_DOMINATORS);
3199 timevar_pop (TV_REPAIR_LOOPS);
3202 timevar_pop (TV_CLEANUP_CFG);
3204 return changed;
3207 namespace {
3209 const pass_data pass_data_jump =
3211 RTL_PASS, /* type */
3212 "jump", /* name */
3213 OPTGROUP_NONE, /* optinfo_flags */
3214 TV_JUMP, /* tv_id */
3215 0, /* properties_required */
3216 0, /* properties_provided */
3217 0, /* properties_destroyed */
3218 0, /* todo_flags_start */
3219 0, /* todo_flags_finish */
3222 class pass_jump : public rtl_opt_pass
3224 public:
3225 pass_jump (gcc::context *ctxt)
3226 : rtl_opt_pass (pass_data_jump, ctxt)
3229 /* opt_pass methods: */
3230 unsigned int execute (function *) final override;
3232 }; // class pass_jump
3234 unsigned int
3235 pass_jump::execute (function *)
3237 delete_trivially_dead_insns (get_insns (), max_reg_num ());
3238 if (dump_file)
3239 dump_flow_info (dump_file, dump_flags);
3240 cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
3241 | (flag_thread_jumps && flag_expensive_optimizations
3242 ? CLEANUP_THREADING : 0));
3243 return 0;
3246 } // anon namespace
3248 rtl_opt_pass *
3249 make_pass_jump (gcc::context *ctxt)
3251 return new pass_jump (ctxt);
3254 namespace {
3256 const pass_data pass_data_jump_after_combine =
3258 RTL_PASS, /* type */
3259 "jump_after_combine", /* name */
3260 OPTGROUP_NONE, /* optinfo_flags */
3261 TV_JUMP, /* tv_id */
3262 0, /* properties_required */
3263 0, /* properties_provided */
3264 0, /* properties_destroyed */
3265 0, /* todo_flags_start */
3266 0, /* todo_flags_finish */
3269 class pass_jump_after_combine : public rtl_opt_pass
3271 public:
3272 pass_jump_after_combine (gcc::context *ctxt)
3273 : rtl_opt_pass (pass_data_jump_after_combine, ctxt)
3276 /* opt_pass methods: */
3277 bool gate (function *) final override
3279 return flag_thread_jumps && flag_expensive_optimizations;
3281 unsigned int execute (function *) final override;
3283 }; // class pass_jump_after_combine
3285 unsigned int
3286 pass_jump_after_combine::execute (function *)
3288 /* Jump threading does not keep dominators up-to-date. */
3289 free_dominance_info (CDI_DOMINATORS);
3290 cleanup_cfg (CLEANUP_THREADING);
3291 return 0;
3294 } // anon namespace
3296 rtl_opt_pass *
3297 make_pass_jump_after_combine (gcc::context *ctxt)
3299 return new pass_jump_after_combine (ctxt);
3302 namespace {
3304 const pass_data pass_data_jump2 =
3306 RTL_PASS, /* type */
3307 "jump2", /* name */
3308 OPTGROUP_NONE, /* optinfo_flags */
3309 TV_JUMP, /* tv_id */
3310 0, /* properties_required */
3311 0, /* properties_provided */
3312 0, /* properties_destroyed */
3313 0, /* todo_flags_start */
3314 0, /* todo_flags_finish */
3317 class pass_jump2 : public rtl_opt_pass
3319 public:
3320 pass_jump2 (gcc::context *ctxt)
3321 : rtl_opt_pass (pass_data_jump2, ctxt)
3324 /* opt_pass methods: */
3325 unsigned int execute (function *) final override
3327 cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
3328 return 0;
3331 }; // class pass_jump2
3333 } // anon namespace
3335 rtl_opt_pass *
3336 make_pass_jump2 (gcc::context *ctxt)
3338 return new pass_jump2 (ctxt);