basic-block.h (create_basic_block, [...]): Kill.
[gcc.git] / gcc / cfgcleanup.c
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 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
21
22 /* This file contains optimizer of the control flow. The main entrypoint is
23 cleanup_cfg. Following optimizations are performed:
24
25 - Unreachable blocks removal
26 - Edge forwarding (edge to the forwarder block is forwarded to it's
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 "basic-block.h"
41 #include "timevar.h"
42 #include "output.h"
43 #include "insn-config.h"
44 #include "flags.h"
45 #include "recog.h"
46 #include "toplev.h"
47 #include "cselib.h"
48 #include "params.h"
49 #include "tm_p.h"
50 #include "target.h"
51
52 /* cleanup_cfg maintains following flags for each basic block. */
53
54 enum bb_flags
55 {
56 /* Set if BB is the forwarder block to avoid too many
57 forwarder_block_p calls. */
58 BB_FORWARDER_BLOCK = 1,
59 BB_NONTHREADABLE_BLOCK = 2
60 };
61
62 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
63 #define BB_SET_FLAG(BB, FLAG) \
64 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
65 #define BB_CLEAR_FLAG(BB, FLAG) \
66 (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
67
68 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
69
70 static bool try_crossjump_to_edge (int, edge, edge);
71 static bool try_crossjump_bb (int, basic_block);
72 static bool outgoing_edges_match (int, basic_block, basic_block);
73 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
74 static bool insns_match_p (int, rtx, rtx);
75
76 static bool label_is_jump_target_p (rtx, rtx);
77 static bool tail_recursion_label_p (rtx);
78 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
79 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
80 static bool try_optimize_cfg (int);
81 static bool try_simplify_condjump (basic_block);
82 static bool try_forward_edges (int, basic_block);
83 static edge thread_jump (int, edge, basic_block);
84 static bool mark_effect (rtx, bitmap);
85 static void notice_new_block (basic_block);
86 static void update_forwarder_flag (basic_block);
87 static int mentions_nonequal_regs (rtx *, void *);
88 \f
89 /* Set flags for newly created block. */
90
91 static void
92 notice_new_block (basic_block bb)
93 {
94 if (!bb)
95 return;
96
97 if (forwarder_block_p (bb))
98 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
99 }
100
101 /* Recompute forwarder flag after block has been modified. */
102
103 static void
104 update_forwarder_flag (basic_block bb)
105 {
106 if (forwarder_block_p (bb))
107 BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
108 else
109 BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
110 }
111 \f
112 /* Simplify a conditional jump around an unconditional jump.
113 Return true if something changed. */
114
115 static bool
116 try_simplify_condjump (basic_block cbranch_block)
117 {
118 basic_block jump_block, jump_dest_block, cbranch_dest_block;
119 edge cbranch_jump_edge, cbranch_fallthru_edge;
120 rtx cbranch_insn;
121
122 /* Verify that there are exactly two successors. */
123 if (!cbranch_block->succ
124 || !cbranch_block->succ->succ_next
125 || cbranch_block->succ->succ_next->succ_next)
126 return false;
127
128 /* Verify that we've got a normal conditional branch at the end
129 of the block. */
130 cbranch_insn = cbranch_block->end;
131 if (!any_condjump_p (cbranch_insn))
132 return false;
133
134 cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
135 cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
136
137 /* The next block must not have multiple predecessors, must not
138 be the last block in the function, and must contain just the
139 unconditional jump. */
140 jump_block = cbranch_fallthru_edge->dest;
141 if (jump_block->pred->pred_next
142 || jump_block->next_bb == EXIT_BLOCK_PTR
143 || !FORWARDER_BLOCK_P (jump_block))
144 return false;
145 jump_dest_block = jump_block->succ->dest;
146
147 /* The conditional branch must target the block after the
148 unconditional branch. */
149 cbranch_dest_block = cbranch_jump_edge->dest;
150
151 if (!can_fallthru (jump_block, cbranch_dest_block))
152 return false;
153
154 /* Invert the conditional branch. */
155 if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
156 return false;
157
158 if (rtl_dump_file)
159 fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
160 INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
161
162 /* Success. Update the CFG to match. Note that after this point
163 the edge variable names appear backwards; the redirection is done
164 this way to preserve edge profile data. */
165 cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
166 cbranch_dest_block);
167 cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
168 jump_dest_block);
169 cbranch_jump_edge->flags |= EDGE_FALLTHRU;
170 cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
171 update_br_prob_note (cbranch_block);
172
173 /* Delete the block with the unconditional jump, and clean up the mess. */
174 delete_block (jump_block);
175 tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
176
177 return true;
178 }
179 \f
180 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
181 on register. Used by jump threading. */
182
183 static bool
184 mark_effect (rtx exp, regset nonequal)
185 {
186 int regno;
187 rtx dest;
188 switch (GET_CODE (exp))
189 {
190 /* In case we do clobber the register, mark it as equal, as we know the
191 value is dead so it don't have to match. */
192 case CLOBBER:
193 if (REG_P (XEXP (exp, 0)))
194 {
195 dest = XEXP (exp, 0);
196 regno = REGNO (dest);
197 CLEAR_REGNO_REG_SET (nonequal, regno);
198 if (regno < FIRST_PSEUDO_REGISTER)
199 {
200 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
201 while (--n > 0)
202 CLEAR_REGNO_REG_SET (nonequal, regno + n);
203 }
204 }
205 return false;
206
207 case SET:
208 if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
209 return false;
210 dest = SET_DEST (exp);
211 if (dest == pc_rtx)
212 return false;
213 if (!REG_P (dest))
214 return true;
215 regno = REGNO (dest);
216 SET_REGNO_REG_SET (nonequal, regno);
217 if (regno < FIRST_PSEUDO_REGISTER)
218 {
219 int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
220 while (--n > 0)
221 SET_REGNO_REG_SET (nonequal, regno + n);
222 }
223 return false;
224
225 default:
226 return false;
227 }
228 }
229
230 /* Return nonzero if X is an register set in regset DATA.
231 Called via for_each_rtx. */
232 static int
233 mentions_nonequal_regs (rtx *x, void *data)
234 {
235 regset nonequal = (regset) data;
236 if (REG_P (*x))
237 {
238 int regno;
239
240 regno = REGNO (*x);
241 if (REGNO_REG_SET_P (nonequal, regno))
242 return 1;
243 if (regno < FIRST_PSEUDO_REGISTER)
244 {
245 int n = HARD_REGNO_NREGS (regno, GET_MODE (*x));
246 while (--n > 0)
247 if (REGNO_REG_SET_P (nonequal, regno + n))
248 return 1;
249 }
250 }
251 return 0;
252 }
253 /* Attempt to prove that the basic block B will have no side effects and
254 always continues in the same edge if reached via E. Return the edge
255 if exist, NULL otherwise. */
256
257 static edge
258 thread_jump (int mode, edge e, basic_block b)
259 {
260 rtx set1, set2, cond1, cond2, insn;
261 enum rtx_code code1, code2, reversed_code2;
262 bool reverse1 = false;
263 int i;
264 regset nonequal;
265 bool failed = false;
266
267 if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
268 return NULL;
269
270 /* At the moment, we do handle only conditional jumps, but later we may
271 want to extend this code to tablejumps and others. */
272 if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
273 return NULL;
274 if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
275 {
276 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
277 return NULL;
278 }
279
280 /* Second branch must end with onlyjump, as we will eliminate the jump. */
281 if (!any_condjump_p (e->src->end))
282 return NULL;
283
284 if (!any_condjump_p (b->end) || !onlyjump_p (b->end))
285 {
286 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
287 return NULL;
288 }
289
290 set1 = pc_set (e->src->end);
291 set2 = pc_set (b->end);
292 if (((e->flags & EDGE_FALLTHRU) != 0)
293 != (XEXP (SET_SRC (set1), 1) == pc_rtx))
294 reverse1 = true;
295
296 cond1 = XEXP (SET_SRC (set1), 0);
297 cond2 = XEXP (SET_SRC (set2), 0);
298 if (reverse1)
299 code1 = reversed_comparison_code (cond1, e->src->end);
300 else
301 code1 = GET_CODE (cond1);
302
303 code2 = GET_CODE (cond2);
304 reversed_code2 = reversed_comparison_code (cond2, b->end);
305
306 if (!comparison_dominates_p (code1, code2)
307 && !comparison_dominates_p (code1, reversed_code2))
308 return NULL;
309
310 /* Ensure that the comparison operators are equivalent.
311 ??? This is far too pessimistic. We should allow swapped operands,
312 different CCmodes, or for example comparisons for interval, that
313 dominate even when operands are not equivalent. */
314 if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
315 || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
316 return NULL;
317
318 /* Short circuit cases where block B contains some side effects, as we can't
319 safely bypass it. */
320 for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end);
321 insn = NEXT_INSN (insn))
322 if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
323 {
324 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
325 return NULL;
326 }
327
328 cselib_init ();
329
330 /* First process all values computed in the source basic block. */
331 for (insn = NEXT_INSN (e->src->head); insn != NEXT_INSN (e->src->end);
332 insn = NEXT_INSN (insn))
333 if (INSN_P (insn))
334 cselib_process_insn (insn);
335
336 nonequal = BITMAP_XMALLOC();
337 CLEAR_REG_SET (nonequal);
338
339 /* Now assume that we've continued by the edge E to B and continue
340 processing as if it were same basic block.
341 Our goal is to prove that whole block is an NOOP. */
342
343 for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end) && !failed;
344 insn = NEXT_INSN (insn))
345 {
346 if (INSN_P (insn))
347 {
348 rtx pat = PATTERN (insn);
349
350 if (GET_CODE (pat) == PARALLEL)
351 {
352 for (i = 0; i < XVECLEN (pat, 0); i++)
353 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
354 }
355 else
356 failed |= mark_effect (pat, nonequal);
357 }
358
359 cselib_process_insn (insn);
360 }
361
362 /* Later we should clear nonequal of dead registers. So far we don't
363 have life information in cfg_cleanup. */
364 if (failed)
365 {
366 BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
367 goto failed_exit;
368 }
369
370 /* cond2 must not mention any register that is not equal to the
371 former block. */
372 if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
373 goto failed_exit;
374
375 /* In case liveness information is available, we need to prove equivalence
376 only of the live values. */
377 if (mode & CLEANUP_UPDATE_LIFE)
378 AND_REG_SET (nonequal, b->global_live_at_end);
379
380 EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
381
382 BITMAP_XFREE (nonequal);
383 cselib_finish ();
384 if ((comparison_dominates_p (code1, code2) != 0)
385 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
386 return BRANCH_EDGE (b);
387 else
388 return FALLTHRU_EDGE (b);
389
390 failed_exit:
391 BITMAP_XFREE (nonequal);
392 cselib_finish ();
393 return NULL;
394 }
395 \f
396 /* Attempt to forward edges leaving basic block B.
397 Return true if successful. */
398
399 static bool
400 try_forward_edges (int mode, basic_block b)
401 {
402 bool changed = false;
403 edge e, next, *threaded_edges = NULL;
404
405 for (e = b->succ; e; e = next)
406 {
407 basic_block target, first;
408 int counter;
409 bool threaded = false;
410 int nthreaded_edges = 0;
411
412 next = e->succ_next;
413
414 /* Skip complex edges because we don't know how to update them.
415
416 Still handle fallthru edges, as we can succeed to forward fallthru
417 edge to the same place as the branch edge of conditional branch
418 and turn conditional branch to an unconditional branch. */
419 if (e->flags & EDGE_COMPLEX)
420 continue;
421
422 target = first = e->dest;
423 counter = 0;
424
425 while (counter < n_basic_blocks)
426 {
427 basic_block new_target = NULL;
428 bool new_target_threaded = false;
429
430 if (FORWARDER_BLOCK_P (target)
431 && target->succ->dest != EXIT_BLOCK_PTR)
432 {
433 /* Bypass trivial infinite loops. */
434 if (target == target->succ->dest)
435 counter = n_basic_blocks;
436 new_target = target->succ->dest;
437 }
438
439 /* Allow to thread only over one edge at time to simplify updating
440 of probabilities. */
441 else if (mode & CLEANUP_THREADING)
442 {
443 edge t = thread_jump (mode, e, target);
444 if (t)
445 {
446 if (!threaded_edges)
447 threaded_edges = xmalloc (sizeof (*threaded_edges)
448 * n_basic_blocks);
449 else
450 {
451 int i;
452
453 /* Detect an infinite loop across blocks not
454 including the start block. */
455 for (i = 0; i < nthreaded_edges; ++i)
456 if (threaded_edges[i] == t)
457 break;
458 if (i < nthreaded_edges)
459 {
460 counter = n_basic_blocks;
461 break;
462 }
463 }
464
465 /* Detect an infinite loop across the start block. */
466 if (t->dest == b)
467 break;
468
469 if (nthreaded_edges >= n_basic_blocks)
470 abort ();
471 threaded_edges[nthreaded_edges++] = t;
472
473 new_target = t->dest;
474 new_target_threaded = true;
475 }
476 }
477
478 if (!new_target)
479 break;
480
481 /* Avoid killing of loop pre-headers, as it is the place loop
482 optimizer wants to hoist code to.
483
484 For fallthru forwarders, the LOOP_BEG note must appear between
485 the header of block and CODE_LABEL of the loop, for non forwarders
486 it must appear before the JUMP_INSN. */
487 if ((mode & CLEANUP_PRE_LOOP) && optimize)
488 {
489 rtx insn = (target->succ->flags & EDGE_FALLTHRU
490 ? target->head : prev_nonnote_insn (target->end));
491
492 if (GET_CODE (insn) != NOTE)
493 insn = NEXT_INSN (insn);
494
495 for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
496 insn = NEXT_INSN (insn))
497 if (GET_CODE (insn) == NOTE
498 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
499 break;
500
501 if (GET_CODE (insn) == NOTE)
502 break;
503
504 /* Do not clean up branches to just past the end of a loop
505 at this time; it can mess up the loop optimizer's
506 recognition of some patterns. */
507
508 insn = PREV_INSN (target->head);
509 if (insn && GET_CODE (insn) == NOTE
510 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
511 break;
512 }
513
514 counter++;
515 target = new_target;
516 threaded |= new_target_threaded;
517 }
518
519 if (counter >= n_basic_blocks)
520 {
521 if (rtl_dump_file)
522 fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
523 target->index);
524 }
525 else if (target == first)
526 ; /* We didn't do anything. */
527 else
528 {
529 /* Save the values now, as the edge may get removed. */
530 gcov_type edge_count = e->count;
531 int edge_probability = e->probability;
532 int edge_frequency;
533 int n = 0;
534
535 /* Don't force if target is exit block. */
536 if (threaded && target != EXIT_BLOCK_PTR)
537 {
538 notice_new_block (redirect_edge_and_branch_force (e, target));
539 if (rtl_dump_file)
540 fprintf (rtl_dump_file, "Conditionals threaded.\n");
541 }
542 else if (!redirect_edge_and_branch (e, target))
543 {
544 if (rtl_dump_file)
545 fprintf (rtl_dump_file,
546 "Forwarding edge %i->%i to %i failed.\n",
547 b->index, e->dest->index, target->index);
548 continue;
549 }
550
551 /* We successfully forwarded the edge. Now update profile
552 data: for each edge we traversed in the chain, remove
553 the original edge's execution count. */
554 edge_frequency = ((edge_probability * b->frequency
555 + REG_BR_PROB_BASE / 2)
556 / REG_BR_PROB_BASE);
557
558 if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
559 BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
560
561 do
562 {
563 edge t;
564
565 first->count -= edge_count;
566 if (first->count < 0)
567 first->count = 0;
568 first->frequency -= edge_frequency;
569 if (first->frequency < 0)
570 first->frequency = 0;
571 if (first->succ->succ_next)
572 {
573 edge e;
574 int prob;
575 if (n >= nthreaded_edges)
576 abort ();
577 t = threaded_edges [n++];
578 if (t->src != first)
579 abort ();
580 if (first->frequency)
581 prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
582 else
583 prob = 0;
584 if (prob > t->probability)
585 prob = t->probability;
586 t->probability -= prob;
587 prob = REG_BR_PROB_BASE - prob;
588 if (prob <= 0)
589 {
590 first->succ->probability = REG_BR_PROB_BASE;
591 first->succ->succ_next->probability = 0;
592 }
593 else
594 for (e = first->succ; e; e = e->succ_next)
595 e->probability = ((e->probability * REG_BR_PROB_BASE)
596 / (double) prob);
597 update_br_prob_note (first);
598 }
599 else
600 {
601 /* It is possible that as the result of
602 threading we've removed edge as it is
603 threaded to the fallthru edge. Avoid
604 getting out of sync. */
605 if (n < nthreaded_edges
606 && first == threaded_edges [n]->src)
607 n++;
608 t = first->succ;
609 }
610
611 t->count -= edge_count;
612 if (t->count < 0)
613 t->count = 0;
614 first = t->dest;
615 }
616 while (first != target);
617
618 changed = true;
619 }
620 }
621
622 if (threaded_edges)
623 free (threaded_edges);
624 return changed;
625 }
626 \f
627 /* Return true if LABEL is a target of JUMP_INSN. This applies only
628 to non-complex jumps. That is, direct unconditional, conditional,
629 and tablejumps, but not computed jumps or returns. It also does
630 not apply to the fallthru case of a conditional jump. */
631
632 static bool
633 label_is_jump_target_p (rtx label, rtx jump_insn)
634 {
635 rtx tmp = JUMP_LABEL (jump_insn);
636
637 if (label == tmp)
638 return true;
639
640 if (tablejump_p (jump_insn, NULL, &tmp))
641 {
642 rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC);
643 int i, veclen = GET_NUM_ELEM (vec);
644
645 for (i = 0; i < veclen; ++i)
646 if (XEXP (RTVEC_ELT (vec, i), 0) == label)
647 return true;
648 }
649
650 return false;
651 }
652
653 /* Return true if LABEL is used for tail recursion. */
654
655 static bool
656 tail_recursion_label_p (rtx label)
657 {
658 rtx x;
659
660 for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
661 if (label == XEXP (x, 0))
662 return true;
663
664 return false;
665 }
666
667 /* Blocks A and B are to be merged into a single block. A has no incoming
668 fallthru edge, so it can be moved before B without adding or modifying
669 any jumps (aside from the jump from A to B). */
670
671 static void
672 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
673 {
674 rtx barrier;
675
676 barrier = next_nonnote_insn (a->end);
677 if (GET_CODE (barrier) != BARRIER)
678 abort ();
679 delete_insn (barrier);
680
681 /* Move block and loop notes out of the chain so that we do not
682 disturb their order.
683
684 ??? A better solution would be to squeeze out all the non-nested notes
685 and adjust the block trees appropriately. Even better would be to have
686 a tighter connection between block trees and rtl so that this is not
687 necessary. */
688 if (squeeze_notes (&a->head, &a->end))
689 abort ();
690
691 /* Scramble the insn chain. */
692 if (a->end != PREV_INSN (b->head))
693 reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
694 a->flags |= BB_DIRTY;
695
696 if (rtl_dump_file)
697 fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
698 a->index, b->index);
699
700 /* Swap the records for the two blocks around. */
701
702 unlink_block (a);
703 link_block (a, b->prev_bb);
704
705 /* Now blocks A and B are contiguous. Merge them. */
706 merge_blocks (a, b);
707 }
708
709 /* Blocks A and B are to be merged into a single block. B has no outgoing
710 fallthru edge, so it can be moved after A without adding or modifying
711 any jumps (aside from the jump from A to B). */
712
713 static void
714 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
715 {
716 rtx barrier, real_b_end;
717
718 real_b_end = b->end;
719 barrier = NEXT_INSN (b->end);
720
721 /* Recognize a jump table following block B. */
722 if (barrier
723 && GET_CODE (barrier) == CODE_LABEL
724 && NEXT_INSN (barrier)
725 && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
726 && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
727 || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
728 {
729 /* Temporarily add the table jump insn to b, so that it will also
730 be moved to the correct location. */
731 b->end = NEXT_INSN (barrier);
732 barrier = NEXT_INSN (b->end);
733 }
734
735 /* There had better have been a barrier there. Delete it. */
736 if (barrier && GET_CODE (barrier) == BARRIER)
737 delete_insn (barrier);
738
739 /* Move block and loop notes out of the chain so that we do not
740 disturb their order.
741
742 ??? A better solution would be to squeeze out all the non-nested notes
743 and adjust the block trees appropriately. Even better would be to have
744 a tighter connection between block trees and rtl so that this is not
745 necessary. */
746 if (squeeze_notes (&b->head, &b->end))
747 abort ();
748
749 /* Scramble the insn chain. */
750 reorder_insns_nobb (b->head, b->end, a->end);
751
752 /* Restore the real end of b. */
753 b->end = real_b_end;
754
755 if (rtl_dump_file)
756 fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
757 b->index, a->index);
758
759 /* Now blocks A and B are contiguous. Merge them. */
760 merge_blocks (a, b);
761 }
762
763 /* Attempt to merge basic blocks that are potentially non-adjacent.
764 Return NULL iff the attempt failed, otherwise return basic block
765 where cleanup_cfg should continue. Because the merging commonly
766 moves basic block away or introduces another optimization
767 possibility, return basic block just before B so cleanup_cfg don't
768 need to iterate.
769
770 It may be good idea to return basic block before C in the case
771 C has been moved after B and originally appeared earlier in the
772 insn seqeunce, but we have no infromation available about the
773 relative ordering of these two. Hopefully it is not too common. */
774
775 static basic_block
776 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
777 {
778 basic_block next;
779 /* If C has a tail recursion label, do not merge. There is no
780 edge recorded from the call_placeholder back to this label, as
781 that would make optimize_sibling_and_tail_recursive_calls more
782 complex for no gain. */
783 if ((mode & CLEANUP_PRE_SIBCALL)
784 && GET_CODE (c->head) == CODE_LABEL
785 && tail_recursion_label_p (c->head))
786 return NULL;
787
788 /* If B has a fallthru edge to C, no need to move anything. */
789 if (e->flags & EDGE_FALLTHRU)
790 {
791 int b_index = b->index, c_index = c->index;
792 merge_blocks (b, c);
793 update_forwarder_flag (b);
794
795 if (rtl_dump_file)
796 fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
797 b_index, c_index);
798
799 return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
800 }
801
802 /* Otherwise we will need to move code around. Do that only if expensive
803 transformations are allowed. */
804 else if (mode & CLEANUP_EXPENSIVE)
805 {
806 edge tmp_edge, b_fallthru_edge;
807 bool c_has_outgoing_fallthru;
808 bool b_has_incoming_fallthru;
809
810 /* Avoid overactive code motion, as the forwarder blocks should be
811 eliminated by edge redirection instead. One exception might have
812 been if B is a forwarder block and C has no fallthru edge, but
813 that should be cleaned up by bb-reorder instead. */
814 if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
815 return NULL;
816
817 /* We must make sure to not munge nesting of lexical blocks,
818 and loop notes. This is done by squeezing out all the notes
819 and leaving them there to lie. Not ideal, but functional. */
820
821 for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
822 if (tmp_edge->flags & EDGE_FALLTHRU)
823 break;
824
825 c_has_outgoing_fallthru = (tmp_edge != NULL);
826
827 for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
828 if (tmp_edge->flags & EDGE_FALLTHRU)
829 break;
830
831 b_has_incoming_fallthru = (tmp_edge != NULL);
832 b_fallthru_edge = tmp_edge;
833 next = b->prev_bb;
834 if (next == c)
835 next = next->prev_bb;
836
837 /* Otherwise, we're going to try to move C after B. If C does
838 not have an outgoing fallthru, then it can be moved
839 immediately after B without introducing or modifying jumps. */
840 if (! c_has_outgoing_fallthru)
841 {
842 merge_blocks_move_successor_nojumps (b, c);
843 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
844 }
845
846 /* If B does not have an incoming fallthru, then it can be moved
847 immediately before C without introducing or modifying jumps.
848 C cannot be the first block, so we do not have to worry about
849 accessing a non-existent block. */
850
851 if (b_has_incoming_fallthru)
852 {
853 basic_block bb;
854
855 if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
856 return NULL;
857 bb = force_nonfallthru (b_fallthru_edge);
858 if (bb)
859 notice_new_block (bb);
860 }
861
862 merge_blocks_move_predecessor_nojumps (b, c);
863 return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
864 }
865
866 return NULL;
867 }
868 \f
869
870 /* Return true if I1 and I2 are equivalent and thus can be crossjumped. */
871
872 static bool
873 insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
874 {
875 rtx p1, p2;
876
877 /* Verify that I1 and I2 are equivalent. */
878 if (GET_CODE (i1) != GET_CODE (i2))
879 return false;
880
881 p1 = PATTERN (i1);
882 p2 = PATTERN (i2);
883
884 if (GET_CODE (p1) != GET_CODE (p2))
885 return false;
886
887 /* If this is a CALL_INSN, compare register usage information.
888 If we don't check this on stack register machines, the two
889 CALL_INSNs might be merged leaving reg-stack.c with mismatching
890 numbers of stack registers in the same basic block.
891 If we don't check this on machines with delay slots, a delay slot may
892 be filled that clobbers a parameter expected by the subroutine.
893
894 ??? We take the simple route for now and assume that if they're
895 equal, they were constructed identically. */
896
897 if (GET_CODE (i1) == CALL_INSN
898 && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
899 CALL_INSN_FUNCTION_USAGE (i2))
900 || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
901 return false;
902
903 #ifdef STACK_REGS
904 /* If cross_jump_death_matters is not 0, the insn's mode
905 indicates whether or not the insn contains any stack-like
906 regs. */
907
908 if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
909 {
910 /* If register stack conversion has already been done, then
911 death notes must also be compared before it is certain that
912 the two instruction streams match. */
913
914 rtx note;
915 HARD_REG_SET i1_regset, i2_regset;
916
917 CLEAR_HARD_REG_SET (i1_regset);
918 CLEAR_HARD_REG_SET (i2_regset);
919
920 for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
921 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
922 SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
923
924 for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
925 if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
926 SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
927
928 GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
929
930 return false;
931
932 done:
933 ;
934 }
935 #endif
936
937 if (reload_completed
938 ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
939 return true;
940
941 /* Do not do EQUIV substitution after reload. First, we're undoing the
942 work of reload_cse. Second, we may be undoing the work of the post-
943 reload splitting pass. */
944 /* ??? Possibly add a new phase switch variable that can be used by
945 targets to disallow the troublesome insns after splitting. */
946 if (!reload_completed)
947 {
948 /* The following code helps take care of G++ cleanups. */
949 rtx equiv1 = find_reg_equal_equiv_note (i1);
950 rtx equiv2 = find_reg_equal_equiv_note (i2);
951
952 if (equiv1 && equiv2
953 /* If the equivalences are not to a constant, they may
954 reference pseudos that no longer exist, so we can't
955 use them. */
956 && (! reload_completed
957 || (CONSTANT_P (XEXP (equiv1, 0))
958 && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
959 {
960 rtx s1 = single_set (i1);
961 rtx s2 = single_set (i2);
962 if (s1 != 0 && s2 != 0
963 && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
964 {
965 validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
966 validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
967 if (! rtx_renumbered_equal_p (p1, p2))
968 cancel_changes (0);
969 else if (apply_change_group ())
970 return true;
971 }
972 }
973 }
974
975 return false;
976 }
977 \f
978 /* Look through the insns at the end of BB1 and BB2 and find the longest
979 sequence that are equivalent. Store the first insns for that sequence
980 in *F1 and *F2 and return the sequence length.
981
982 To simplify callers of this function, if the blocks match exactly,
983 store the head of the blocks in *F1 and *F2. */
984
985 static int
986 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
987 basic_block bb2, rtx *f1, rtx *f2)
988 {
989 rtx i1, i2, last1, last2, afterlast1, afterlast2;
990 int ninsns = 0;
991
992 /* Skip simple jumps at the end of the blocks. Complex jumps still
993 need to be compared for equivalence, which we'll do below. */
994
995 i1 = bb1->end;
996 last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
997 if (onlyjump_p (i1)
998 || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
999 {
1000 last1 = i1;
1001 i1 = PREV_INSN (i1);
1002 }
1003
1004 i2 = bb2->end;
1005 if (onlyjump_p (i2)
1006 || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1007 {
1008 last2 = i2;
1009 /* Count everything except for unconditional jump as insn. */
1010 if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1011 ninsns++;
1012 i2 = PREV_INSN (i2);
1013 }
1014
1015 while (true)
1016 {
1017 /* Ignore notes. */
1018 while (!INSN_P (i1) && i1 != bb1->head)
1019 i1 = PREV_INSN (i1);
1020
1021 while (!INSN_P (i2) && i2 != bb2->head)
1022 i2 = PREV_INSN (i2);
1023
1024 if (i1 == bb1->head || i2 == bb2->head)
1025 break;
1026
1027 if (!insns_match_p (mode, i1, i2))
1028 break;
1029
1030 /* Don't begin a cross-jump with a NOTE insn. */
1031 if (INSN_P (i1))
1032 {
1033 /* If the merged insns have different REG_EQUAL notes, then
1034 remove them. */
1035 rtx equiv1 = find_reg_equal_equiv_note (i1);
1036 rtx equiv2 = find_reg_equal_equiv_note (i2);
1037
1038 if (equiv1 && !equiv2)
1039 remove_note (i1, equiv1);
1040 else if (!equiv1 && equiv2)
1041 remove_note (i2, equiv2);
1042 else if (equiv1 && equiv2
1043 && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1044 {
1045 remove_note (i1, equiv1);
1046 remove_note (i2, equiv2);
1047 }
1048
1049 afterlast1 = last1, afterlast2 = last2;
1050 last1 = i1, last2 = i2;
1051 ninsns++;
1052 }
1053
1054 i1 = PREV_INSN (i1);
1055 i2 = PREV_INSN (i2);
1056 }
1057
1058 #ifdef HAVE_cc0
1059 /* Don't allow the insn after a compare to be shared by
1060 cross-jumping unless the compare is also shared. */
1061 if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1062 last1 = afterlast1, last2 = afterlast2, ninsns--;
1063 #endif
1064
1065 /* Include preceding notes and labels in the cross-jump. One,
1066 this may bring us to the head of the blocks as requested above.
1067 Two, it keeps line number notes as matched as may be. */
1068 if (ninsns)
1069 {
1070 while (last1 != bb1->head && !INSN_P (PREV_INSN (last1)))
1071 last1 = PREV_INSN (last1);
1072
1073 if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1074 last1 = PREV_INSN (last1);
1075
1076 while (last2 != bb2->head && !INSN_P (PREV_INSN (last2)))
1077 last2 = PREV_INSN (last2);
1078
1079 if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1080 last2 = PREV_INSN (last2);
1081
1082 *f1 = last1;
1083 *f2 = last2;
1084 }
1085
1086 return ninsns;
1087 }
1088
1089 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1090 the branch instruction. This means that if we commonize the control
1091 flow before end of the basic block, the semantic remains unchanged.
1092
1093 We may assume that there exists one edge with a common destination. */
1094
1095 static bool
1096 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1097 {
1098 int nehedges1 = 0, nehedges2 = 0;
1099 edge fallthru1 = 0, fallthru2 = 0;
1100 edge e1, e2;
1101
1102 /* If BB1 has only one successor, we may be looking at either an
1103 unconditional jump, or a fake edge to exit. */
1104 if (bb1->succ && !bb1->succ->succ_next
1105 && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1106 && (GET_CODE (bb1->end) != JUMP_INSN || simplejump_p (bb1->end)))
1107 return (bb2->succ && !bb2->succ->succ_next
1108 && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1109 && (GET_CODE (bb2->end) != JUMP_INSN || simplejump_p (bb2->end)));
1110
1111 /* Match conditional jumps - this may get tricky when fallthru and branch
1112 edges are crossed. */
1113 if (bb1->succ
1114 && bb1->succ->succ_next
1115 && !bb1->succ->succ_next->succ_next
1116 && any_condjump_p (bb1->end)
1117 && onlyjump_p (bb1->end))
1118 {
1119 edge b1, f1, b2, f2;
1120 bool reverse, match;
1121 rtx set1, set2, cond1, cond2;
1122 enum rtx_code code1, code2;
1123
1124 if (!bb2->succ
1125 || !bb2->succ->succ_next
1126 || bb2->succ->succ_next->succ_next
1127 || !any_condjump_p (bb2->end)
1128 || !onlyjump_p (bb2->end))
1129 return false;
1130
1131 b1 = BRANCH_EDGE (bb1);
1132 b2 = BRANCH_EDGE (bb2);
1133 f1 = FALLTHRU_EDGE (bb1);
1134 f2 = FALLTHRU_EDGE (bb2);
1135
1136 /* Get around possible forwarders on fallthru edges. Other cases
1137 should be optimized out already. */
1138 if (FORWARDER_BLOCK_P (f1->dest))
1139 f1 = f1->dest->succ;
1140
1141 if (FORWARDER_BLOCK_P (f2->dest))
1142 f2 = f2->dest->succ;
1143
1144 /* To simplify use of this function, return false if there are
1145 unneeded forwarder blocks. These will get eliminated later
1146 during cleanup_cfg. */
1147 if (FORWARDER_BLOCK_P (f1->dest)
1148 || FORWARDER_BLOCK_P (f2->dest)
1149 || FORWARDER_BLOCK_P (b1->dest)
1150 || FORWARDER_BLOCK_P (b2->dest))
1151 return false;
1152
1153 if (f1->dest == f2->dest && b1->dest == b2->dest)
1154 reverse = false;
1155 else if (f1->dest == b2->dest && b1->dest == f2->dest)
1156 reverse = true;
1157 else
1158 return false;
1159
1160 set1 = pc_set (bb1->end);
1161 set2 = pc_set (bb2->end);
1162 if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1163 != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1164 reverse = !reverse;
1165
1166 cond1 = XEXP (SET_SRC (set1), 0);
1167 cond2 = XEXP (SET_SRC (set2), 0);
1168 code1 = GET_CODE (cond1);
1169 if (reverse)
1170 code2 = reversed_comparison_code (cond2, bb2->end);
1171 else
1172 code2 = GET_CODE (cond2);
1173
1174 if (code2 == UNKNOWN)
1175 return false;
1176
1177 /* Verify codes and operands match. */
1178 match = ((code1 == code2
1179 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1180 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1181 || (code1 == swap_condition (code2)
1182 && rtx_renumbered_equal_p (XEXP (cond1, 1),
1183 XEXP (cond2, 0))
1184 && rtx_renumbered_equal_p (XEXP (cond1, 0),
1185 XEXP (cond2, 1))));
1186
1187 /* If we return true, we will join the blocks. Which means that
1188 we will only have one branch prediction bit to work with. Thus
1189 we require the existing branches to have probabilities that are
1190 roughly similar. */
1191 if (match
1192 && !optimize_size
1193 && maybe_hot_bb_p (bb1)
1194 && maybe_hot_bb_p (bb2))
1195 {
1196 int prob2;
1197
1198 if (b1->dest == b2->dest)
1199 prob2 = b2->probability;
1200 else
1201 /* Do not use f2 probability as f2 may be forwarded. */
1202 prob2 = REG_BR_PROB_BASE - b2->probability;
1203
1204 /* Fail if the difference in probabilities is greater than 50%.
1205 This rules out two well-predicted branches with opposite
1206 outcomes. */
1207 if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1208 {
1209 if (rtl_dump_file)
1210 fprintf (rtl_dump_file,
1211 "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1212 bb1->index, bb2->index, b1->probability, prob2);
1213
1214 return false;
1215 }
1216 }
1217
1218 if (rtl_dump_file && match)
1219 fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1220 bb1->index, bb2->index);
1221
1222 return match;
1223 }
1224
1225 /* Generic case - we are seeing a computed jump, table jump or trapping
1226 instruction. */
1227
1228 #ifndef CASE_DROPS_THROUGH
1229 /* Check whether there are tablejumps in the end of BB1 and BB2.
1230 Return true if they are identical. */
1231 {
1232 rtx label1, label2;
1233 rtx table1, table2;
1234
1235 if (tablejump_p (bb1->end, &label1, &table1)
1236 && tablejump_p (bb2->end, &label2, &table2)
1237 && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1238 {
1239 /* The labels should never be the same rtx. If they really are same
1240 the jump tables are same too. So disable crossjumping of blocks BB1
1241 and BB2 because when deleting the common insns in the end of BB1
1242 by delete_block () the jump table would be deleted too. */
1243 /* If LABEL2 is referenced in BB1->END do not do anything
1244 because we would loose information when replacing
1245 LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END. */
1246 if (label1 != label2 && !rtx_referenced_p (label2, bb1->end))
1247 {
1248 /* Set IDENTICAL to true when the tables are identical. */
1249 bool identical = false;
1250 rtx p1, p2;
1251
1252 p1 = PATTERN (table1);
1253 p2 = PATTERN (table2);
1254 if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1255 {
1256 identical = true;
1257 }
1258 else if (GET_CODE (p1) == ADDR_DIFF_VEC
1259 && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1260 && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1261 && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1262 {
1263 int i;
1264
1265 identical = true;
1266 for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1267 if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1268 identical = false;
1269 }
1270
1271 if (identical)
1272 {
1273 replace_label_data rr;
1274 bool match;
1275
1276 /* Temporarily replace references to LABEL1 with LABEL2
1277 in BB1->END so that we could compare the instructions. */
1278 rr.r1 = label1;
1279 rr.r2 = label2;
1280 rr.update_label_nuses = false;
1281 for_each_rtx (&bb1->end, replace_label, &rr);
1282
1283 match = insns_match_p (mode, bb1->end, bb2->end);
1284 if (rtl_dump_file && match)
1285 fprintf (rtl_dump_file,
1286 "Tablejumps in bb %i and %i match.\n",
1287 bb1->index, bb2->index);
1288
1289 /* Set the original label in BB1->END because when deleting
1290 a block whose end is a tablejump, the tablejump referenced
1291 from the instruction is deleted too. */
1292 rr.r1 = label2;
1293 rr.r2 = label1;
1294 for_each_rtx (&bb1->end, replace_label, &rr);
1295
1296 return match;
1297 }
1298 }
1299 return false;
1300 }
1301 }
1302 #endif
1303
1304 /* First ensure that the instructions match. There may be many outgoing
1305 edges so this test is generally cheaper. */
1306 if (!insns_match_p (mode, bb1->end, bb2->end))
1307 return false;
1308
1309 /* Search the outgoing edges, ensure that the counts do match, find possible
1310 fallthru and exception handling edges since these needs more
1311 validation. */
1312 for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1313 e1 = e1->succ_next, e2 = e2->succ_next)
1314 {
1315 if (e1->flags & EDGE_EH)
1316 nehedges1++;
1317
1318 if (e2->flags & EDGE_EH)
1319 nehedges2++;
1320
1321 if (e1->flags & EDGE_FALLTHRU)
1322 fallthru1 = e1;
1323 if (e2->flags & EDGE_FALLTHRU)
1324 fallthru2 = e2;
1325 }
1326
1327 /* If number of edges of various types does not match, fail. */
1328 if (e1 || e2
1329 || nehedges1 != nehedges2
1330 || (fallthru1 != 0) != (fallthru2 != 0))
1331 return false;
1332
1333 /* fallthru edges must be forwarded to the same destination. */
1334 if (fallthru1)
1335 {
1336 basic_block d1 = (forwarder_block_p (fallthru1->dest)
1337 ? fallthru1->dest->succ->dest: fallthru1->dest);
1338 basic_block d2 = (forwarder_block_p (fallthru2->dest)
1339 ? fallthru2->dest->succ->dest: fallthru2->dest);
1340
1341 if (d1 != d2)
1342 return false;
1343 }
1344
1345 /* In case we do have EH edges, ensure we are in the same region. */
1346 if (nehedges1)
1347 {
1348 rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0);
1349 rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0);
1350
1351 if (XEXP (n1, 0) != XEXP (n2, 0))
1352 return false;
1353 }
1354
1355 /* We don't need to match the rest of edges as above checks should be enough
1356 to ensure that they are equivalent. */
1357 return true;
1358 }
1359
1360 /* E1 and E2 are edges with the same destination block. Search their
1361 predecessors for common code. If found, redirect control flow from
1362 (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC. */
1363
1364 static bool
1365 try_crossjump_to_edge (int mode, edge e1, edge e2)
1366 {
1367 int nmatch;
1368 basic_block src1 = e1->src, src2 = e2->src;
1369 basic_block redirect_to, redirect_from, to_remove;
1370 rtx newpos1, newpos2;
1371 edge s;
1372
1373 /* Search backward through forwarder blocks. We don't need to worry
1374 about multiple entry or chained forwarders, as they will be optimized
1375 away. We do this to look past the unconditional jump following a
1376 conditional jump that is required due to the current CFG shape. */
1377 if (src1->pred
1378 && !src1->pred->pred_next
1379 && FORWARDER_BLOCK_P (src1))
1380 e1 = src1->pred, src1 = e1->src;
1381
1382 if (src2->pred
1383 && !src2->pred->pred_next
1384 && FORWARDER_BLOCK_P (src2))
1385 e2 = src2->pred, src2 = e2->src;
1386
1387 /* Nothing to do if we reach ENTRY, or a common source block. */
1388 if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1389 return false;
1390 if (src1 == src2)
1391 return false;
1392
1393 /* Seeing more than 1 forwarder blocks would confuse us later... */
1394 if (FORWARDER_BLOCK_P (e1->dest)
1395 && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1396 return false;
1397
1398 if (FORWARDER_BLOCK_P (e2->dest)
1399 && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1400 return false;
1401
1402 /* Likewise with dead code (possibly newly created by the other optimizations
1403 of cfg_cleanup). */
1404 if (!src1->pred || !src2->pred)
1405 return false;
1406
1407 /* Look for the common insn sequence, part the first ... */
1408 if (!outgoing_edges_match (mode, src1, src2))
1409 return false;
1410
1411 /* ... and part the second. */
1412 nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1413 if (!nmatch)
1414 return false;
1415
1416 #ifndef CASE_DROPS_THROUGH
1417 /* Here we know that the insns in the end of SRC1 which are common with SRC2
1418 will be deleted.
1419 If we have tablejumps in the end of SRC1 and SRC2
1420 they have been already compared for equivalence in outgoing_edges_match ()
1421 so replace the references to TABLE1 by references to TABLE2. */
1422 {
1423 rtx label1, label2;
1424 rtx table1, table2;
1425
1426 if (tablejump_p (src1->end, &label1, &table1)
1427 && tablejump_p (src2->end, &label2, &table2)
1428 && label1 != label2)
1429 {
1430 replace_label_data rr;
1431 rtx insn;
1432
1433 /* Replace references to LABEL1 with LABEL2. */
1434 rr.r1 = label1;
1435 rr.r2 = label2;
1436 rr.update_label_nuses = true;
1437 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1438 {
1439 /* Do not replace the label in SRC1->END because when deleting
1440 a block whose end is a tablejump, the tablejump referenced
1441 from the instruction is deleted too. */
1442 if (insn != src1->end)
1443 for_each_rtx (&insn, replace_label, &rr);
1444 }
1445 }
1446 }
1447 #endif
1448
1449 /* Avoid splitting if possible. */
1450 if (newpos2 == src2->head)
1451 redirect_to = src2;
1452 else
1453 {
1454 if (rtl_dump_file)
1455 fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1456 src2->index, nmatch);
1457 redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1458 }
1459
1460 if (rtl_dump_file)
1461 fprintf (rtl_dump_file,
1462 "Cross jumping from bb %i to bb %i; %i common insns\n",
1463 src1->index, src2->index, nmatch);
1464
1465 redirect_to->count += src1->count;
1466 redirect_to->frequency += src1->frequency;
1467 /* We may have some registers visible trought the block. */
1468 redirect_to->flags |= BB_DIRTY;
1469
1470 /* Recompute the frequencies and counts of outgoing edges. */
1471 for (s = redirect_to->succ; s; s = s->succ_next)
1472 {
1473 edge s2;
1474 basic_block d = s->dest;
1475
1476 if (FORWARDER_BLOCK_P (d))
1477 d = d->succ->dest;
1478
1479 for (s2 = src1->succ; ; s2 = s2->succ_next)
1480 {
1481 basic_block d2 = s2->dest;
1482 if (FORWARDER_BLOCK_P (d2))
1483 d2 = d2->succ->dest;
1484 if (d == d2)
1485 break;
1486 }
1487
1488 s->count += s2->count;
1489
1490 /* Take care to update possible forwarder blocks. We verified
1491 that there is no more than one in the chain, so we can't run
1492 into infinite loop. */
1493 if (FORWARDER_BLOCK_P (s->dest))
1494 {
1495 s->dest->succ->count += s2->count;
1496 s->dest->count += s2->count;
1497 s->dest->frequency += EDGE_FREQUENCY (s);
1498 }
1499
1500 if (FORWARDER_BLOCK_P (s2->dest))
1501 {
1502 s2->dest->succ->count -= s2->count;
1503 if (s2->dest->succ->count < 0)
1504 s2->dest->succ->count = 0;
1505 s2->dest->count -= s2->count;
1506 s2->dest->frequency -= EDGE_FREQUENCY (s);
1507 if (s2->dest->frequency < 0)
1508 s2->dest->frequency = 0;
1509 if (s2->dest->count < 0)
1510 s2->dest->count = 0;
1511 }
1512
1513 if (!redirect_to->frequency && !src1->frequency)
1514 s->probability = (s->probability + s2->probability) / 2;
1515 else
1516 s->probability
1517 = ((s->probability * redirect_to->frequency +
1518 s2->probability * src1->frequency)
1519 / (redirect_to->frequency + src1->frequency));
1520 }
1521
1522 update_br_prob_note (redirect_to);
1523
1524 /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
1525
1526 /* Skip possible basic block header. */
1527 if (GET_CODE (newpos1) == CODE_LABEL)
1528 newpos1 = NEXT_INSN (newpos1);
1529
1530 if (GET_CODE (newpos1) == NOTE)
1531 newpos1 = NEXT_INSN (newpos1);
1532
1533 redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1534 to_remove = redirect_from->succ->dest;
1535
1536 redirect_edge_and_branch_force (redirect_from->succ, redirect_to);
1537 delete_block (to_remove);
1538
1539 update_forwarder_flag (redirect_from);
1540
1541 return true;
1542 }
1543
1544 /* Search the predecessors of BB for common insn sequences. When found,
1545 share code between them by redirecting control flow. Return true if
1546 any changes made. */
1547
1548 static bool
1549 try_crossjump_bb (int mode, basic_block bb)
1550 {
1551 edge e, e2, nexte2, nexte, fallthru;
1552 bool changed;
1553 int n = 0, max;
1554
1555 /* Nothing to do if there is not at least two incoming edges. */
1556 if (!bb->pred || !bb->pred->pred_next)
1557 return false;
1558
1559 /* It is always cheapest to redirect a block that ends in a branch to
1560 a block that falls through into BB, as that adds no branches to the
1561 program. We'll try that combination first. */
1562 fallthru = NULL;
1563 max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1564 for (e = bb->pred; e ; e = e->pred_next, n++)
1565 {
1566 if (e->flags & EDGE_FALLTHRU)
1567 fallthru = e;
1568 if (n > max)
1569 return false;
1570 }
1571
1572 changed = false;
1573 for (e = bb->pred; e; e = nexte)
1574 {
1575 nexte = e->pred_next;
1576
1577 /* As noted above, first try with the fallthru predecessor. */
1578 if (fallthru)
1579 {
1580 /* Don't combine the fallthru edge into anything else.
1581 If there is a match, we'll do it the other way around. */
1582 if (e == fallthru)
1583 continue;
1584
1585 if (try_crossjump_to_edge (mode, e, fallthru))
1586 {
1587 changed = true;
1588 nexte = bb->pred;
1589 continue;
1590 }
1591 }
1592
1593 /* Non-obvious work limiting check: Recognize that we're going
1594 to call try_crossjump_bb on every basic block. So if we have
1595 two blocks with lots of outgoing edges (a switch) and they
1596 share lots of common destinations, then we would do the
1597 cross-jump check once for each common destination.
1598
1599 Now, if the blocks actually are cross-jump candidates, then
1600 all of their destinations will be shared. Which means that
1601 we only need check them for cross-jump candidacy once. We
1602 can eliminate redundant checks of crossjump(A,B) by arbitrarily
1603 choosing to do the check from the block for which the edge
1604 in question is the first successor of A. */
1605 if (e->src->succ != e)
1606 continue;
1607
1608 for (e2 = bb->pred; e2; e2 = nexte2)
1609 {
1610 nexte2 = e2->pred_next;
1611
1612 if (e2 == e)
1613 continue;
1614
1615 /* We've already checked the fallthru edge above. */
1616 if (e2 == fallthru)
1617 continue;
1618
1619 /* The "first successor" check above only prevents multiple
1620 checks of crossjump(A,B). In order to prevent redundant
1621 checks of crossjump(B,A), require that A be the block
1622 with the lowest index. */
1623 if (e->src->index > e2->src->index)
1624 continue;
1625
1626 if (try_crossjump_to_edge (mode, e, e2))
1627 {
1628 changed = true;
1629 nexte = bb->pred;
1630 break;
1631 }
1632 }
1633 }
1634
1635 return changed;
1636 }
1637
1638 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1639 instructions etc. Return nonzero if changes were made. */
1640
1641 static bool
1642 try_optimize_cfg (int mode)
1643 {
1644 bool changed_overall = false;
1645 bool changed;
1646 int iterations = 0;
1647 basic_block bb, b, next;
1648
1649 if (mode & CLEANUP_CROSSJUMP)
1650 add_noreturn_fake_exit_edges ();
1651
1652 FOR_EACH_BB (bb)
1653 update_forwarder_flag (bb);
1654
1655 if (mode & CLEANUP_UPDATE_LIFE)
1656 clear_bb_flags ();
1657
1658 if (! (* targetm.cannot_modify_jumps_p) ())
1659 {
1660 /* Attempt to merge blocks as made possible by edge removal. If
1661 a block has only one successor, and the successor has only
1662 one predecessor, they may be combined. */
1663 do
1664 {
1665 changed = false;
1666 iterations++;
1667
1668 if (rtl_dump_file)
1669 fprintf (rtl_dump_file,
1670 "\n\ntry_optimize_cfg iteration %i\n\n",
1671 iterations);
1672
1673 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1674 {
1675 basic_block c;
1676 edge s;
1677 bool changed_here = false;
1678
1679 /* Delete trivially dead basic blocks. */
1680 while (b->pred == NULL)
1681 {
1682 c = b->prev_bb;
1683 if (rtl_dump_file)
1684 fprintf (rtl_dump_file, "Deleting block %i.\n",
1685 b->index);
1686
1687 delete_block (b);
1688 if (!(mode & CLEANUP_CFGLAYOUT))
1689 changed = true;
1690 b = c;
1691 }
1692
1693 /* Remove code labels no longer used. Don't do this
1694 before CALL_PLACEHOLDER is removed, as some branches
1695 may be hidden within. */
1696 if (b->pred->pred_next == NULL
1697 && (b->pred->flags & EDGE_FALLTHRU)
1698 && !(b->pred->flags & EDGE_COMPLEX)
1699 && GET_CODE (b->head) == CODE_LABEL
1700 && (!(mode & CLEANUP_PRE_SIBCALL)
1701 || !tail_recursion_label_p (b->head))
1702 /* If the previous block ends with a branch to this
1703 block, we can't delete the label. Normally this
1704 is a condjump that is yet to be simplified, but
1705 if CASE_DROPS_THRU, this can be a tablejump with
1706 some element going to the same place as the
1707 default (fallthru). */
1708 && (b->pred->src == ENTRY_BLOCK_PTR
1709 || GET_CODE (b->pred->src->end) != JUMP_INSN
1710 || ! label_is_jump_target_p (b->head,
1711 b->pred->src->end)))
1712 {
1713 rtx label = b->head;
1714
1715 delete_insn_chain (label, label);
1716 /* In the case label is undeletable, move it after the
1717 BASIC_BLOCK note. */
1718 if (NOTE_LINE_NUMBER (b->head) == NOTE_INSN_DELETED_LABEL)
1719 {
1720 rtx bb_note = NEXT_INSN (b->head);
1721
1722 reorder_insns_nobb (label, label, bb_note);
1723 b->head = bb_note;
1724 }
1725 if (rtl_dump_file)
1726 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1727 b->index);
1728 }
1729
1730 /* If we fall through an empty block, we can remove it. */
1731 if (!(mode & CLEANUP_CFGLAYOUT)
1732 && b->pred->pred_next == NULL
1733 && (b->pred->flags & EDGE_FALLTHRU)
1734 && GET_CODE (b->head) != CODE_LABEL
1735 && FORWARDER_BLOCK_P (b)
1736 /* Note that forwarder_block_p true ensures that
1737 there is a successor for this block. */
1738 && (b->succ->flags & EDGE_FALLTHRU)
1739 && n_basic_blocks > 1)
1740 {
1741 if (rtl_dump_file)
1742 fprintf (rtl_dump_file,
1743 "Deleting fallthru block %i.\n",
1744 b->index);
1745
1746 c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1747 redirect_edge_succ_nodup (b->pred, b->succ->dest);
1748 delete_block (b);
1749 changed = true;
1750 b = c;
1751 }
1752
1753 if ((s = b->succ) != NULL
1754 && s->succ_next == NULL
1755 && !(s->flags & EDGE_COMPLEX)
1756 && (c = s->dest) != EXIT_BLOCK_PTR
1757 && c->pred->pred_next == NULL
1758 && b != c)
1759 {
1760 /* When not in cfg_layout mode use code aware of reordering
1761 INSN. This code possibly creates new basic blocks so it
1762 does not fit merge_blocks interface and is kept here in
1763 hope that it will become useless once more of compiler
1764 is transformed to use cfg_layout mode. */
1765
1766 if ((mode & CLEANUP_CFGLAYOUT)
1767 && can_merge_blocks_p (b, c))
1768 {
1769 merge_blocks (b, c);
1770 update_forwarder_flag (b);
1771 changed_here = true;
1772 }
1773 else if (!(mode & CLEANUP_CFGLAYOUT)
1774 /* If the jump insn has side effects,
1775 we can't kill the edge. */
1776 && (GET_CODE (b->end) != JUMP_INSN
1777 || (flow2_completed
1778 ? simplejump_p (b->end)
1779 : onlyjump_p (b->end)))
1780 && (next = merge_blocks_move (s, b, c, mode)))
1781 {
1782 b = next;
1783 changed_here = true;
1784 }
1785 }
1786
1787 /* Simplify branch over branch. */
1788 if ((mode & CLEANUP_EXPENSIVE)
1789 && !(mode & CLEANUP_CFGLAYOUT)
1790 && try_simplify_condjump (b))
1791 changed_here = true;
1792
1793 /* If B has a single outgoing edge, but uses a
1794 non-trivial jump instruction without side-effects, we
1795 can either delete the jump entirely, or replace it
1796 with a simple unconditional jump. Use
1797 redirect_edge_and_branch to do the dirty work. */
1798 if (b->succ
1799 && ! b->succ->succ_next
1800 && b->succ->dest != EXIT_BLOCK_PTR
1801 && onlyjump_p (b->end)
1802 && redirect_edge_and_branch (b->succ, b->succ->dest))
1803 {
1804 update_forwarder_flag (b);
1805 changed_here = true;
1806 }
1807
1808 /* Simplify branch to branch. */
1809 if (try_forward_edges (mode, b))
1810 changed_here = true;
1811
1812 /* Look for shared code between blocks. */
1813 if ((mode & CLEANUP_CROSSJUMP)
1814 && try_crossjump_bb (mode, b))
1815 changed_here = true;
1816
1817 /* Don't get confused by the index shift caused by
1818 deleting blocks. */
1819 if (!changed_here)
1820 b = b->next_bb;
1821 else
1822 changed = true;
1823 }
1824
1825 if ((mode & CLEANUP_CROSSJUMP)
1826 && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1827 changed = true;
1828
1829 #ifdef ENABLE_CHECKING
1830 if (changed)
1831 verify_flow_info ();
1832 #endif
1833
1834 changed_overall |= changed;
1835 }
1836 while (changed);
1837 }
1838
1839 if (mode & CLEANUP_CROSSJUMP)
1840 remove_fake_edges ();
1841
1842 clear_aux_for_blocks ();
1843
1844 return changed_overall;
1845 }
1846 \f
1847 /* Delete all unreachable basic blocks. */
1848
1849 bool
1850 delete_unreachable_blocks (void)
1851 {
1852 bool changed = false;
1853 basic_block b, next_bb;
1854
1855 find_unreachable_blocks ();
1856
1857 /* Delete all unreachable basic blocks. */
1858
1859 for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
1860 {
1861 next_bb = b->next_bb;
1862
1863 if (!(b->flags & BB_REACHABLE))
1864 {
1865 delete_block (b);
1866 changed = true;
1867 }
1868 }
1869
1870 if (changed)
1871 tidy_fallthru_edges ();
1872 return changed;
1873 }
1874 \f
1875 /* Tidy the CFG by deleting unreachable code and whatnot. */
1876
1877 bool
1878 cleanup_cfg (int mode)
1879 {
1880 bool changed = false;
1881
1882 timevar_push (TV_CLEANUP_CFG);
1883 if (delete_unreachable_blocks ())
1884 {
1885 changed = true;
1886 /* We've possibly created trivially dead code. Cleanup it right
1887 now to introduce more opportunities for try_optimize_cfg. */
1888 if (!(mode & (CLEANUP_NO_INSN_DEL
1889 | CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL))
1890 && !reload_completed)
1891 delete_trivially_dead_insns (get_insns(), max_reg_num ());
1892 }
1893
1894 compact_blocks ();
1895
1896 while (try_optimize_cfg (mode))
1897 {
1898 delete_unreachable_blocks (), changed = true;
1899 if (mode & CLEANUP_UPDATE_LIFE)
1900 {
1901 /* Cleaning up CFG introduces more opportunities for dead code
1902 removal that in turn may introduce more opportunities for
1903 cleaning up the CFG. */
1904 if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
1905 PROP_DEATH_NOTES
1906 | PROP_SCAN_DEAD_CODE
1907 | PROP_KILL_DEAD_CODE
1908 | PROP_LOG_LINKS))
1909 break;
1910 }
1911 else if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_PRE_SIBCALL))
1912 && (mode & CLEANUP_EXPENSIVE)
1913 && !reload_completed)
1914 {
1915 if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1916 break;
1917 }
1918 else
1919 break;
1920 delete_dead_jumptables ();
1921 }
1922
1923 /* Kill the data we won't maintain. */
1924 free_EXPR_LIST_list (&label_value_list);
1925 timevar_pop (TV_CLEANUP_CFG);
1926
1927 return changed;
1928 }