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