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