OSDN Git Service

6ff161425fe76df7996c73971cd96e6d44b4541d
[pf3gnuchains/gcc-fork.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, 2004, 2005, 2006, 2007, 2008, 2010, 2011
4    Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along 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.  */
63 static bool first_pass;
64
65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg.  */
66 static 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.  */
70 static bool block_was_dirty;
71
72 static bool try_crossjump_to_edge (int, edge, edge, enum replace_direction);
73 static bool try_crossjump_bb (int, basic_block);
74 static bool outgoing_edges_match (int, basic_block, basic_block);
75 static enum replace_direction old_insns_match_p (int, rtx, rtx);
76
77 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
78 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
79 static bool try_optimize_cfg (int);
80 static bool try_simplify_condjump (basic_block);
81 static bool try_forward_edges (int, basic_block);
82 static edge thread_jump (edge, basic_block);
83 static bool mark_effect (rtx, bitmap);
84 static void notice_new_block (basic_block);
85 static void update_forwarder_flag (basic_block);
86 static int mentions_nonequal_regs (rtx *, void *);
87 static void merge_memattrs (rtx, rtx);
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->flags |= 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->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
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 (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
197 static bool
198 mark_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.  */
242 static int
243 mentions_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
267 static edge
268 thread_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
399 failed_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
408 static bool
409 try_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
655 static void
656 merge_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
699 static void
700 merge_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
760 static basic_block
761 merge_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
857 void
858 merge_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     }
925
926   fmt = GET_RTX_FORMAT (code);
927   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
928     {
929       switch (fmt[i])
930         {
931         case 'E':
932           /* Two vectors must have the same length.  */
933           if (XVECLEN (x, i) != XVECLEN (y, i))
934             return;
935
936           for (j = 0; j < XVECLEN (x, i); j++)
937             merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
938
939           break;
940
941         case 'e':
942           merge_memattrs (XEXP (x, i), XEXP (y, i));
943         }
944     }
945   return;
946 }
947
948
949  /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
950     different single sets S1 and S2.  */
951
952 static bool
953 equal_different_set_p (rtx p1, rtx s1, rtx p2, rtx s2)
954 {
955   int i;
956   rtx e1, e2;
957
958   if (p1 == s1 && p2 == s2)
959     return true;
960
961   if (GET_CODE (p1) != PARALLEL || GET_CODE (p2) != PARALLEL)
962     return false;
963
964   if (XVECLEN (p1, 0) != XVECLEN (p2, 0))
965     return false;
966
967   for (i = 0; i < XVECLEN (p1, 0); i++)
968     {
969       e1 = XVECEXP (p1, 0, i);
970       e2 = XVECEXP (p2, 0, i);
971       if (e1 == s1 && e2 == s2)
972         continue;
973       if (reload_completed
974           ? rtx_renumbered_equal_p (e1, e2) : rtx_equal_p (e1, e2))
975         continue;
976
977         return false;
978     }
979
980   return true;
981 }
982
983 /* Examine register notes on I1 and I2 and return:
984    - dir_forward if I1 can be replaced by I2, or
985    - dir_backward if I2 can be replaced by I1, or
986    - dir_both if both are the case.  */
987
988 static enum replace_direction
989 can_replace_by (rtx i1, rtx i2)
990 {
991   rtx s1, s2, d1, d2, src1, src2, note1, note2;
992   bool c1, c2;
993
994   /* Check for 2 sets.  */
995   s1 = single_set (i1);
996   s2 = single_set (i2);
997   if (s1 == NULL_RTX || s2 == NULL_RTX)
998     return dir_none;
999
1000   /* Check that the 2 sets set the same dest.  */
1001   d1 = SET_DEST (s1);
1002   d2 = SET_DEST (s2);
1003   if (!(reload_completed
1004         ? rtx_renumbered_equal_p (d1, d2) : rtx_equal_p (d1, d2)))
1005     return dir_none;
1006
1007   /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
1008      set dest to the same value.  */
1009   note1 = find_reg_equal_equiv_note (i1);
1010   note2 = find_reg_equal_equiv_note (i2);
1011   if (!note1 || !note2 || !rtx_equal_p (XEXP (note1, 0), XEXP (note2, 0))
1012       || !CONST_INT_P (XEXP (note1, 0)))
1013     return dir_none;
1014
1015   if (!equal_different_set_p (PATTERN (i1), s1, PATTERN (i2), s2))
1016     return dir_none;
1017
1018   /* Although the 2 sets set dest to the same value, we cannot replace
1019        (set (dest) (const_int))
1020      by
1021        (set (dest) (reg))
1022      because we don't know if the reg is live and has the same value at the
1023      location of replacement.  */
1024   src1 = SET_SRC (s1);
1025   src2 = SET_SRC (s2);
1026   c1 = CONST_INT_P (src1);
1027   c2 = CONST_INT_P (src2);
1028   if (c1 && c2)
1029     return dir_both;
1030   else if (c2)
1031     return dir_forward;
1032   else if (c1)
1033     return dir_backward;
1034
1035   return dir_none;
1036 }
1037
1038 /* Merges directions A and B.  */
1039
1040 static enum replace_direction
1041 merge_dir (enum replace_direction a, enum replace_direction b)
1042 {
1043   /* Implements the following table:
1044         |bo fw bw no
1045      ---+-----------
1046      bo |bo fw bw no
1047      fw |-- fw no no
1048      bw |-- -- bw no
1049      no |-- -- -- no.  */
1050
1051   if (a == b)
1052     return a;
1053
1054   if (a == dir_both)
1055     return b;
1056   if (b == dir_both)
1057     return a;
1058
1059   return dir_none;
1060 }
1061
1062 /* Examine I1 and I2 and return:
1063    - dir_forward if I1 can be replaced by I2, or
1064    - dir_backward if I2 can be replaced by I1, or
1065    - dir_both if both are the case.  */
1066
1067 static enum replace_direction
1068 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
1069 {
1070   rtx p1, p2;
1071
1072   /* Verify that I1 and I2 are equivalent.  */
1073   if (GET_CODE (i1) != GET_CODE (i2))
1074     return dir_none;
1075
1076   /* __builtin_unreachable() may lead to empty blocks (ending with
1077      NOTE_INSN_BASIC_BLOCK).  They may be crossjumped. */
1078   if (NOTE_INSN_BASIC_BLOCK_P (i1) && NOTE_INSN_BASIC_BLOCK_P (i2))
1079     return dir_both;
1080
1081   /* ??? Do not allow cross-jumping between different stack levels.  */
1082   p1 = find_reg_note (i1, REG_ARGS_SIZE, NULL);
1083   p2 = find_reg_note (i2, REG_ARGS_SIZE, NULL);
1084   if (p1 && p2)
1085     {
1086       p1 = XEXP (p1, 0);
1087       p2 = XEXP (p2, 0);
1088       if (!rtx_equal_p (p1, p2))
1089         return dir_none;
1090
1091       /* ??? Worse, this adjustment had better be constant lest we
1092          have differing incoming stack levels.  */
1093       if (!frame_pointer_needed
1094           && find_args_size_adjust (i1) == HOST_WIDE_INT_MIN)
1095         return dir_none;
1096     }
1097   else if (p1 || p2)
1098     return dir_none;
1099
1100   p1 = PATTERN (i1);
1101   p2 = PATTERN (i2);
1102
1103   if (GET_CODE (p1) != GET_CODE (p2))
1104     return dir_none;
1105
1106   /* If this is a CALL_INSN, compare register usage information.
1107      If we don't check this on stack register machines, the two
1108      CALL_INSNs might be merged leaving reg-stack.c with mismatching
1109      numbers of stack registers in the same basic block.
1110      If we don't check this on machines with delay slots, a delay slot may
1111      be filled that clobbers a parameter expected by the subroutine.
1112
1113      ??? We take the simple route for now and assume that if they're
1114      equal, they were constructed identically.
1115
1116      Also check for identical exception regions.  */
1117
1118   if (CALL_P (i1))
1119     {
1120       /* Ensure the same EH region.  */
1121       rtx n1 = find_reg_note (i1, REG_EH_REGION, 0);
1122       rtx n2 = find_reg_note (i2, REG_EH_REGION, 0);
1123
1124       if (!n1 && n2)
1125         return dir_none;
1126
1127       if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1128         return dir_none;
1129
1130       if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
1131                         CALL_INSN_FUNCTION_USAGE (i2))
1132           || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2))
1133         return dir_none;
1134     }
1135
1136 #ifdef STACK_REGS
1137   /* If cross_jump_death_matters is not 0, the insn's mode
1138      indicates whether or not the insn contains any stack-like
1139      regs.  */
1140
1141   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
1142     {
1143       /* If register stack conversion has already been done, then
1144          death notes must also be compared before it is certain that
1145          the two instruction streams match.  */
1146
1147       rtx note;
1148       HARD_REG_SET i1_regset, i2_regset;
1149
1150       CLEAR_HARD_REG_SET (i1_regset);
1151       CLEAR_HARD_REG_SET (i2_regset);
1152
1153       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
1154         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1155           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
1156
1157       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1158         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1159           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1160
1161       if (!hard_reg_set_equal_p (i1_regset, i2_regset))
1162         return dir_none;
1163     }
1164 #endif
1165
1166   if (reload_completed
1167       ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1168     return dir_both;
1169
1170   return can_replace_by (i1, i2);
1171 }
1172 \f
1173 /* When comparing insns I1 and I2 in flow_find_cross_jump or
1174    flow_find_head_matching_sequence, ensure the notes match.  */
1175
1176 static void
1177 merge_notes (rtx i1, rtx i2)
1178 {
1179   /* If the merged insns have different REG_EQUAL notes, then
1180      remove them.  */
1181   rtx equiv1 = find_reg_equal_equiv_note (i1);
1182   rtx equiv2 = find_reg_equal_equiv_note (i2);
1183
1184   if (equiv1 && !equiv2)
1185     remove_note (i1, equiv1);
1186   else if (!equiv1 && equiv2)
1187     remove_note (i2, equiv2);
1188   else if (equiv1 && equiv2
1189            && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1190     {
1191       remove_note (i1, equiv1);
1192       remove_note (i2, equiv2);
1193     }
1194 }
1195
1196  /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
1197     resulting insn in I1, and the corresponding bb in BB1.  At the head of a
1198     bb, if there is a predecessor bb that reaches this bb via fallthru, and
1199     FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
1200     DID_FALLTHRU.  Otherwise, stops at the head of the bb.  */
1201
1202 static void
1203 walk_to_nondebug_insn (rtx *i1, basic_block *bb1, bool follow_fallthru,
1204                        bool *did_fallthru)
1205 {
1206   edge fallthru;
1207
1208   *did_fallthru = false;
1209
1210   /* Ignore notes.  */
1211   while (!NONDEBUG_INSN_P (*i1))
1212     {
1213       if (*i1 != BB_HEAD (*bb1))
1214         {
1215           *i1 = PREV_INSN (*i1);
1216           continue;
1217         }
1218
1219       if (!follow_fallthru)
1220         return;
1221
1222       fallthru = find_fallthru_edge ((*bb1)->preds);
1223       if (!fallthru || fallthru->src == ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun)
1224           || !single_succ_p (fallthru->src))
1225         return;
1226
1227       *bb1 = fallthru->src;
1228       *i1 = BB_END (*bb1);
1229       *did_fallthru = true;
1230      }
1231 }
1232
1233 /* Look through the insns at the end of BB1 and BB2 and find the longest
1234    sequence that are either equivalent, or allow forward or backward
1235    replacement.  Store the first insns for that sequence in *F1 and *F2 and
1236    return the sequence length.
1237
1238    DIR_P indicates the allowed replacement direction on function entry, and
1239    the actual replacement direction on function exit.  If NULL, only equivalent
1240    sequences are allowed.
1241
1242    To simplify callers of this function, if the blocks match exactly,
1243    store the head of the blocks in *F1 and *F2.  */
1244
1245 int
1246 flow_find_cross_jump (basic_block bb1, basic_block bb2, rtx *f1, rtx *f2,
1247                       enum replace_direction *dir_p)
1248 {
1249   rtx i1, i2, last1, last2, afterlast1, afterlast2;
1250   int ninsns = 0;
1251   rtx p1;
1252   enum replace_direction dir, last_dir, afterlast_dir;
1253   bool follow_fallthru, did_fallthru;
1254
1255   if (dir_p)
1256     dir = *dir_p;
1257   else
1258     dir = dir_both;
1259   afterlast_dir = dir;
1260   last_dir = afterlast_dir;
1261
1262   /* Skip simple jumps at the end of the blocks.  Complex jumps still
1263      need to be compared for equivalence, which we'll do below.  */
1264
1265   i1 = BB_END (bb1);
1266   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1267   if (onlyjump_p (i1)
1268       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1269     {
1270       last1 = i1;
1271       i1 = PREV_INSN (i1);
1272     }
1273
1274   i2 = BB_END (bb2);
1275   if (onlyjump_p (i2)
1276       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1277     {
1278       last2 = i2;
1279       /* Count everything except for unconditional jump as insn.  */
1280       if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1281         ninsns++;
1282       i2 = PREV_INSN (i2);
1283     }
1284
1285   while (true)
1286     {
1287       /* In the following example, we can replace all jumps to C by jumps to A.
1288
1289          This removes 4 duplicate insns.
1290          [bb A] insn1            [bb C] insn1
1291                 insn2                   insn2
1292          [bb B] insn3                   insn3
1293                 insn4                   insn4
1294                 jump_insn               jump_insn
1295
1296          We could also replace all jumps to A by jumps to C, but that leaves B
1297          alive, and removes only 2 duplicate insns.  In a subsequent crossjump
1298          step, all jumps to B would be replaced with jumps to the middle of C,
1299          achieving the same result with more effort.
1300          So we allow only the first possibility, which means that we don't allow
1301          fallthru in the block that's being replaced.  */
1302
1303       follow_fallthru = dir_p && dir != dir_forward;
1304       walk_to_nondebug_insn (&i1, &bb1, follow_fallthru, &did_fallthru);
1305       if (did_fallthru)
1306         dir = dir_backward;
1307
1308       follow_fallthru = dir_p && dir != dir_backward;
1309       walk_to_nondebug_insn (&i2, &bb2, follow_fallthru, &did_fallthru);
1310       if (did_fallthru)
1311         dir = dir_forward;
1312
1313       if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1314         break;
1315
1316       dir = merge_dir (dir, old_insns_match_p (0, i1, i2));
1317       if (dir == dir_none || (!dir_p && dir != dir_both))
1318         break;
1319
1320       merge_memattrs (i1, i2);
1321
1322       /* Don't begin a cross-jump with a NOTE insn.  */
1323       if (INSN_P (i1))
1324         {
1325           merge_notes (i1, i2);
1326
1327           afterlast1 = last1, afterlast2 = last2;
1328           last1 = i1, last2 = i2;
1329           afterlast_dir = last_dir;
1330           last_dir = dir;
1331           p1 = PATTERN (i1);
1332           if (!(GET_CODE (p1) == USE || GET_CODE (p1) == CLOBBER))
1333             ninsns++;
1334         }
1335
1336       i1 = PREV_INSN (i1);
1337       i2 = PREV_INSN (i2);
1338     }
1339
1340 #ifdef HAVE_cc0
1341   /* Don't allow the insn after a compare to be shared by
1342      cross-jumping unless the compare is also shared.  */
1343   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1344     last1 = afterlast1, last2 = afterlast2, last_dir = afterlast_dir, ninsns--;
1345 #endif
1346
1347   /* Include preceding notes and labels in the cross-jump.  One,
1348      this may bring us to the head of the blocks as requested above.
1349      Two, it keeps line number notes as matched as may be.  */
1350   if (ninsns)
1351     {
1352       bb1 = BLOCK_FOR_INSN (last1);
1353       while (last1 != BB_HEAD (bb1) && !NONDEBUG_INSN_P (PREV_INSN (last1)))
1354         last1 = PREV_INSN (last1);
1355
1356       if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1357         last1 = PREV_INSN (last1);
1358
1359       bb2 = BLOCK_FOR_INSN (last2);
1360       while (last2 != BB_HEAD (bb2) && !NONDEBUG_INSN_P (PREV_INSN (last2)))
1361         last2 = PREV_INSN (last2);
1362
1363       if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1364         last2 = PREV_INSN (last2);
1365
1366       *f1 = last1;
1367       *f2 = last2;
1368     }
1369
1370   if (dir_p)
1371     *dir_p = last_dir;
1372   return ninsns;
1373 }
1374
1375 /* Like flow_find_cross_jump, except start looking for a matching sequence from
1376    the head of the two blocks.  Do not include jumps at the end.
1377    If STOP_AFTER is nonzero, stop after finding that many matching
1378    instructions.  */
1379
1380 int
1381 flow_find_head_matching_sequence (basic_block bb1, basic_block bb2, rtx *f1,
1382                                   rtx *f2, int stop_after)
1383 {
1384   rtx i1, i2, last1, last2, beforelast1, beforelast2;
1385   int ninsns = 0;
1386   edge e;
1387   edge_iterator ei;
1388   int nehedges1 = 0, nehedges2 = 0;
1389
1390   FOR_EACH_EDGE (e, ei, bb1->succs)
1391     if (e->flags & EDGE_EH)
1392       nehedges1++;
1393   FOR_EACH_EDGE (e, ei, bb2->succs)
1394     if (e->flags & EDGE_EH)
1395       nehedges2++;
1396
1397   i1 = BB_HEAD (bb1);
1398   i2 = BB_HEAD (bb2);
1399   last1 = beforelast1 = last2 = beforelast2 = NULL_RTX;
1400
1401   while (true)
1402     {
1403       /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG.  */
1404       while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
1405         {
1406           if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG)
1407             break;
1408           i1 = NEXT_INSN (i1);
1409         }
1410
1411       while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
1412         {
1413           if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG)
1414             break;
1415           i2 = NEXT_INSN (i2);
1416         }
1417
1418       if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
1419           || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
1420         break;
1421
1422       if (NOTE_P (i1) || NOTE_P (i2)
1423           || JUMP_P (i1) || JUMP_P (i2))
1424         break;
1425
1426       /* A sanity check to make sure we're not merging insns with different
1427          effects on EH.  If only one of them ends a basic block, it shouldn't
1428          have an EH edge; if both end a basic block, there should be the same
1429          number of EH edges.  */
1430       if ((i1 == BB_END (bb1) && i2 != BB_END (bb2)
1431            && nehedges1 > 0)
1432           || (i2 == BB_END (bb2) && i1 != BB_END (bb1)
1433               && nehedges2 > 0)
1434           || (i1 == BB_END (bb1) && i2 == BB_END (bb2)
1435               && nehedges1 != nehedges2))
1436         break;
1437
1438       if (old_insns_match_p (0, i1, i2) != dir_both)
1439         break;
1440
1441       merge_memattrs (i1, i2);
1442
1443       /* Don't begin a cross-jump with a NOTE insn.  */
1444       if (INSN_P (i1))
1445         {
1446           merge_notes (i1, i2);
1447
1448           beforelast1 = last1, beforelast2 = last2;
1449           last1 = i1, last2 = i2;
1450           ninsns++;
1451         }
1452
1453       if (i1 == BB_END (bb1) || i2 == BB_END (bb2)
1454           || (stop_after > 0 && ninsns == stop_after))
1455         break;
1456
1457       i1 = NEXT_INSN (i1);
1458       i2 = NEXT_INSN (i2);
1459     }
1460
1461 #ifdef HAVE_cc0
1462   /* Don't allow a compare to be shared by cross-jumping unless the insn
1463      after the compare is also shared.  */
1464   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && sets_cc0_p (last1))
1465     last1 = beforelast1, last2 = beforelast2, ninsns--;
1466 #endif
1467
1468   if (ninsns)
1469     {
1470       *f1 = last1;
1471       *f2 = last2;
1472     }
1473
1474   return ninsns;
1475 }
1476
1477 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1478    the branch instruction.  This means that if we commonize the control
1479    flow before end of the basic block, the semantic remains unchanged.
1480
1481    We may assume that there exists one edge with a common destination.  */
1482
1483 static bool
1484 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1485 {
1486   int nehedges1 = 0, nehedges2 = 0;
1487   edge fallthru1 = 0, fallthru2 = 0;
1488   edge e1, e2;
1489   edge_iterator ei;
1490   rtx last1, last2;
1491   bool nonfakeedges;
1492
1493   /* If we performed shrink-wrapping, edges to the EXIT_BLOCK_PTR can
1494      only be distinguished for JUMP_INSNs.  The two paths may differ in
1495      whether they went through the prologue.  Sibcalls are fine, we know
1496      that we either didn't need or inserted an epilogue before them.  */
1497   if (crtl->shrink_wrapped
1498       && single_succ_p (bb1) && single_succ (bb1) == EXIT_BLOCK_PTR
1499       && !JUMP_P (BB_END (bb1))
1500       && !(CALL_P (BB_END (bb1)) && SIBLING_CALL_P (BB_END (bb1))))
1501     return false;
1502   
1503   /* If BB1 has only one successor, we may be looking at either an
1504      unconditional jump, or a fake edge to exit.  */
1505   if (single_succ_p (bb1)
1506       && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1507       && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1508     return (single_succ_p (bb2)
1509             && (single_succ_edge (bb2)->flags
1510                 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1511             && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1512
1513   /* Match conditional jumps - this may get tricky when fallthru and branch
1514      edges are crossed.  */
1515   if (EDGE_COUNT (bb1->succs) == 2
1516       && any_condjump_p (BB_END (bb1))
1517       && onlyjump_p (BB_END (bb1)))
1518     {
1519       edge b1, f1, b2, f2;
1520       bool reverse, match;
1521       rtx set1, set2, cond1, cond2;
1522       enum rtx_code code1, code2;
1523
1524       if (EDGE_COUNT (bb2->succs) != 2
1525           || !any_condjump_p (BB_END (bb2))
1526           || !onlyjump_p (BB_END (bb2)))
1527         return false;
1528
1529       b1 = BRANCH_EDGE (bb1);
1530       b2 = BRANCH_EDGE (bb2);
1531       f1 = FALLTHRU_EDGE (bb1);
1532       f2 = FALLTHRU_EDGE (bb2);
1533
1534       /* Get around possible forwarders on fallthru edges.  Other cases
1535          should be optimized out already.  */
1536       if (FORWARDER_BLOCK_P (f1->dest))
1537         f1 = single_succ_edge (f1->dest);
1538
1539       if (FORWARDER_BLOCK_P (f2->dest))
1540         f2 = single_succ_edge (f2->dest);
1541
1542       /* To simplify use of this function, return false if there are
1543          unneeded forwarder blocks.  These will get eliminated later
1544          during cleanup_cfg.  */
1545       if (FORWARDER_BLOCK_P (f1->dest)
1546           || FORWARDER_BLOCK_P (f2->dest)
1547           || FORWARDER_BLOCK_P (b1->dest)
1548           || FORWARDER_BLOCK_P (b2->dest))
1549         return false;
1550
1551       if (f1->dest == f2->dest && b1->dest == b2->dest)
1552         reverse = false;
1553       else if (f1->dest == b2->dest && b1->dest == f2->dest)
1554         reverse = true;
1555       else
1556         return false;
1557
1558       set1 = pc_set (BB_END (bb1));
1559       set2 = pc_set (BB_END (bb2));
1560       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1561           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1562         reverse = !reverse;
1563
1564       cond1 = XEXP (SET_SRC (set1), 0);
1565       cond2 = XEXP (SET_SRC (set2), 0);
1566       code1 = GET_CODE (cond1);
1567       if (reverse)
1568         code2 = reversed_comparison_code (cond2, BB_END (bb2));
1569       else
1570         code2 = GET_CODE (cond2);
1571
1572       if (code2 == UNKNOWN)
1573         return false;
1574
1575       /* Verify codes and operands match.  */
1576       match = ((code1 == code2
1577                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1578                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1579                || (code1 == swap_condition (code2)
1580                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
1581                                               XEXP (cond2, 0))
1582                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
1583                                               XEXP (cond2, 1))));
1584
1585       /* If we return true, we will join the blocks.  Which means that
1586          we will only have one branch prediction bit to work with.  Thus
1587          we require the existing branches to have probabilities that are
1588          roughly similar.  */
1589       if (match
1590           && optimize_bb_for_speed_p (bb1)
1591           && optimize_bb_for_speed_p (bb2))
1592         {
1593           int prob2;
1594
1595           if (b1->dest == b2->dest)
1596             prob2 = b2->probability;
1597           else
1598             /* Do not use f2 probability as f2 may be forwarded.  */
1599             prob2 = REG_BR_PROB_BASE - b2->probability;
1600
1601           /* Fail if the difference in probabilities is greater than 50%.
1602              This rules out two well-predicted branches with opposite
1603              outcomes.  */
1604           if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1605             {
1606               if (dump_file)
1607                 fprintf (dump_file,
1608                          "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1609                          bb1->index, bb2->index, b1->probability, prob2);
1610
1611               return false;
1612             }
1613         }
1614
1615       if (dump_file && match)
1616         fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1617                  bb1->index, bb2->index);
1618
1619       return match;
1620     }
1621
1622   /* Generic case - we are seeing a computed jump, table jump or trapping
1623      instruction.  */
1624
1625   /* Check whether there are tablejumps in the end of BB1 and BB2.
1626      Return true if they are identical.  */
1627     {
1628       rtx label1, label2;
1629       rtx table1, table2;
1630
1631       if (tablejump_p (BB_END (bb1), &label1, &table1)
1632           && tablejump_p (BB_END (bb2), &label2, &table2)
1633           && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1634         {
1635           /* The labels should never be the same rtx.  If they really are same
1636              the jump tables are same too. So disable crossjumping of blocks BB1
1637              and BB2 because when deleting the common insns in the end of BB1
1638              by delete_basic_block () the jump table would be deleted too.  */
1639           /* If LABEL2 is referenced in BB1->END do not do anything
1640              because we would loose information when replacing
1641              LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END.  */
1642           if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1643             {
1644               /* Set IDENTICAL to true when the tables are identical.  */
1645               bool identical = false;
1646               rtx p1, p2;
1647
1648               p1 = PATTERN (table1);
1649               p2 = PATTERN (table2);
1650               if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1651                 {
1652                   identical = true;
1653                 }
1654               else if (GET_CODE (p1) == ADDR_DIFF_VEC
1655                        && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1656                        && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1657                        && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1658                 {
1659                   int i;
1660
1661                   identical = true;
1662                   for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1663                     if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1664                       identical = false;
1665                 }
1666
1667               if (identical)
1668                 {
1669                   replace_label_data rr;
1670                   bool match;
1671
1672                   /* Temporarily replace references to LABEL1 with LABEL2
1673                      in BB1->END so that we could compare the instructions.  */
1674                   rr.r1 = label1;
1675                   rr.r2 = label2;
1676                   rr.update_label_nuses = false;
1677                   for_each_rtx (&BB_END (bb1), replace_label, &rr);
1678
1679                   match = (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2))
1680                            == dir_both);
1681                   if (dump_file && match)
1682                     fprintf (dump_file,
1683                              "Tablejumps in bb %i and %i match.\n",
1684                              bb1->index, bb2->index);
1685
1686                   /* Set the original label in BB1->END because when deleting
1687                      a block whose end is a tablejump, the tablejump referenced
1688                      from the instruction is deleted too.  */
1689                   rr.r1 = label2;
1690                   rr.r2 = label1;
1691                   for_each_rtx (&BB_END (bb1), replace_label, &rr);
1692
1693                   return match;
1694                 }
1695             }
1696           return false;
1697         }
1698     }
1699
1700   last1 = BB_END (bb1);
1701   last2 = BB_END (bb2);
1702   if (DEBUG_INSN_P (last1))
1703     last1 = prev_nondebug_insn (last1);
1704   if (DEBUG_INSN_P (last2))
1705     last2 = prev_nondebug_insn (last2);
1706   /* First ensure that the instructions match.  There may be many outgoing
1707      edges so this test is generally cheaper.  */
1708   if (old_insns_match_p (mode, last1, last2) != dir_both)
1709     return false;
1710
1711   /* Search the outgoing edges, ensure that the counts do match, find possible
1712      fallthru and exception handling edges since these needs more
1713      validation.  */
1714   if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
1715     return false;
1716
1717   nonfakeedges = false;
1718   FOR_EACH_EDGE (e1, ei, bb1->succs)
1719     {
1720       e2 = EDGE_SUCC (bb2, ei.index);
1721
1722       if ((e1->flags & EDGE_FAKE) == 0)
1723         nonfakeedges = true;
1724
1725       if (e1->flags & EDGE_EH)
1726         nehedges1++;
1727
1728       if (e2->flags & EDGE_EH)
1729         nehedges2++;
1730
1731       if (e1->flags & EDGE_FALLTHRU)
1732         fallthru1 = e1;
1733       if (e2->flags & EDGE_FALLTHRU)
1734         fallthru2 = e2;
1735     }
1736
1737   /* If number of edges of various types does not match, fail.  */
1738   if (nehedges1 != nehedges2
1739       || (fallthru1 != 0) != (fallthru2 != 0))
1740     return false;
1741
1742   /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
1743      and the last real insn doesn't have REG_ARGS_SIZE note, don't
1744      attempt to optimize, as the two basic blocks might have different
1745      REG_ARGS_SIZE depths.  For noreturn calls and unconditional
1746      traps there should be REG_ARG_SIZE notes, they could be missing
1747      for __builtin_unreachable () uses though.  */
1748   if (!nonfakeedges
1749       && !ACCUMULATE_OUTGOING_ARGS
1750       && (!INSN_P (last1)
1751           || !find_reg_note (last1, REG_ARGS_SIZE, NULL)))
1752     return false;
1753
1754   /* fallthru edges must be forwarded to the same destination.  */
1755   if (fallthru1)
1756     {
1757       basic_block d1 = (forwarder_block_p (fallthru1->dest)
1758                         ? single_succ (fallthru1->dest): fallthru1->dest);
1759       basic_block d2 = (forwarder_block_p (fallthru2->dest)
1760                         ? single_succ (fallthru2->dest): fallthru2->dest);
1761
1762       if (d1 != d2)
1763         return false;
1764     }
1765
1766   /* Ensure the same EH region.  */
1767   {
1768     rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1769     rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1770
1771     if (!n1 && n2)
1772       return false;
1773
1774     if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1775       return false;
1776   }
1777
1778   /* The same checks as in try_crossjump_to_edge. It is required for RTL
1779      version of sequence abstraction.  */
1780   FOR_EACH_EDGE (e1, ei, bb2->succs)
1781     {
1782       edge e2;
1783       edge_iterator ei;
1784       basic_block d1 = e1->dest;
1785
1786       if (FORWARDER_BLOCK_P (d1))
1787         d1 = EDGE_SUCC (d1, 0)->dest;
1788
1789       FOR_EACH_EDGE (e2, ei, bb1->succs)
1790         {
1791           basic_block d2 = e2->dest;
1792           if (FORWARDER_BLOCK_P (d2))
1793             d2 = EDGE_SUCC (d2, 0)->dest;
1794           if (d1 == d2)
1795             break;
1796         }
1797
1798       if (!e2)
1799         return false;
1800     }
1801
1802   return true;
1803 }
1804
1805 /* Returns true if BB basic block has a preserve label.  */
1806
1807 static bool
1808 block_has_preserve_label (basic_block bb)
1809 {
1810   return (bb
1811           && block_label (bb)
1812           && LABEL_PRESERVE_P (block_label (bb)));
1813 }
1814
1815 /* E1 and E2 are edges with the same destination block.  Search their
1816    predecessors for common code.  If found, redirect control flow from
1817    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
1818    or the other way around (dir_backward).  DIR specifies the allowed
1819    replacement direction.  */
1820
1821 static bool
1822 try_crossjump_to_edge (int mode, edge e1, edge e2,
1823                        enum replace_direction dir)
1824 {
1825   int nmatch;
1826   basic_block src1 = e1->src, src2 = e2->src;
1827   basic_block redirect_to, redirect_from, to_remove;
1828   basic_block osrc1, osrc2, redirect_edges_to, tmp;
1829   rtx newpos1, newpos2;
1830   edge s;
1831   edge_iterator ei;
1832
1833   newpos1 = newpos2 = NULL_RTX;
1834
1835   /* If we have partitioned hot/cold basic blocks, it is a bad idea
1836      to try this optimization.
1837
1838      Basic block partitioning may result in some jumps that appear to
1839      be optimizable (or blocks that appear to be mergeable), but which really
1840      must be left untouched (they are required to make it safely across
1841      partition boundaries).  See the comments at the top of
1842      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
1843
1844   if (flag_reorder_blocks_and_partition && reload_completed)
1845     return false;
1846
1847   /* Search backward through forwarder blocks.  We don't need to worry
1848      about multiple entry or chained forwarders, as they will be optimized
1849      away.  We do this to look past the unconditional jump following a
1850      conditional jump that is required due to the current CFG shape.  */
1851   if (single_pred_p (src1)
1852       && FORWARDER_BLOCK_P (src1))
1853     e1 = single_pred_edge (src1), src1 = e1->src;
1854
1855   if (single_pred_p (src2)
1856       && FORWARDER_BLOCK_P (src2))
1857     e2 = single_pred_edge (src2), src2 = e2->src;
1858
1859   /* Nothing to do if we reach ENTRY, or a common source block.  */
1860   if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1861     return false;
1862   if (src1 == src2)
1863     return false;
1864
1865   /* Seeing more than 1 forwarder blocks would confuse us later...  */
1866   if (FORWARDER_BLOCK_P (e1->dest)
1867       && FORWARDER_BLOCK_P (single_succ (e1->dest)))
1868     return false;
1869
1870   if (FORWARDER_BLOCK_P (e2->dest)
1871       && FORWARDER_BLOCK_P (single_succ (e2->dest)))
1872     return false;
1873
1874   /* Likewise with dead code (possibly newly created by the other optimizations
1875      of cfg_cleanup).  */
1876   if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1877     return false;
1878
1879   /* Look for the common insn sequence, part the first ...  */
1880   if (!outgoing_edges_match (mode, src1, src2))
1881     return false;
1882
1883   /* ... and part the second.  */
1884   nmatch = flow_find_cross_jump (src1, src2, &newpos1, &newpos2, &dir);
1885
1886   osrc1 = src1;
1887   osrc2 = src2;
1888   if (newpos1 != NULL_RTX)
1889     src1 = BLOCK_FOR_INSN (newpos1);
1890   if (newpos2 != NULL_RTX)
1891     src2 = BLOCK_FOR_INSN (newpos2);
1892
1893   if (dir == dir_backward)
1894     {
1895 #define SWAP(T, X, Y) do { T tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
1896       SWAP (basic_block, osrc1, osrc2);
1897       SWAP (basic_block, src1, src2);
1898       SWAP (edge, e1, e2);
1899       SWAP (rtx, newpos1, newpos2);
1900 #undef SWAP
1901     }
1902
1903   /* Don't proceed with the crossjump unless we found a sufficient number
1904      of matching instructions or the 'from' block was totally matched
1905      (such that its predecessors will hopefully be redirected and the
1906      block removed).  */
1907   if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
1908       && (newpos1 != BB_HEAD (src1)))
1909     return false;
1910
1911   /* Avoid deleting preserve label when redirecting ABNORMAL edges.  */
1912   if (block_has_preserve_label (e1->dest)
1913       && (e1->flags & EDGE_ABNORMAL))
1914     return false;
1915
1916   /* Here we know that the insns in the end of SRC1 which are common with SRC2
1917      will be deleted.
1918      If we have tablejumps in the end of SRC1 and SRC2
1919      they have been already compared for equivalence in outgoing_edges_match ()
1920      so replace the references to TABLE1 by references to TABLE2.  */
1921     {
1922       rtx label1, label2;
1923       rtx table1, table2;
1924
1925       if (tablejump_p (BB_END (osrc1), &label1, &table1)
1926           && tablejump_p (BB_END (osrc2), &label2, &table2)
1927           && label1 != label2)
1928         {
1929           replace_label_data rr;
1930           rtx insn;
1931
1932           /* Replace references to LABEL1 with LABEL2.  */
1933           rr.r1 = label1;
1934           rr.r2 = label2;
1935           rr.update_label_nuses = true;
1936           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1937             {
1938               /* Do not replace the label in SRC1->END because when deleting
1939                  a block whose end is a tablejump, the tablejump referenced
1940                  from the instruction is deleted too.  */
1941               if (insn != BB_END (osrc1))
1942                 for_each_rtx (&insn, replace_label, &rr);
1943             }
1944         }
1945     }
1946
1947   /* Avoid splitting if possible.  We must always split when SRC2 has
1948      EH predecessor edges, or we may end up with basic blocks with both
1949      normal and EH predecessor edges.  */
1950   if (newpos2 == BB_HEAD (src2)
1951       && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
1952     redirect_to = src2;
1953   else
1954     {
1955       if (newpos2 == BB_HEAD (src2))
1956         {
1957           /* Skip possible basic block header.  */
1958           if (LABEL_P (newpos2))
1959             newpos2 = NEXT_INSN (newpos2);
1960           while (DEBUG_INSN_P (newpos2))
1961             newpos2 = NEXT_INSN (newpos2);
1962           if (NOTE_P (newpos2))
1963             newpos2 = NEXT_INSN (newpos2);
1964           while (DEBUG_INSN_P (newpos2))
1965             newpos2 = NEXT_INSN (newpos2);
1966         }
1967
1968       if (dump_file)
1969         fprintf (dump_file, "Splitting bb %i before %i insns\n",
1970                  src2->index, nmatch);
1971       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1972     }
1973
1974   if (dump_file)
1975     fprintf (dump_file,
1976              "Cross jumping from bb %i to bb %i; %i common insns\n",
1977              src1->index, src2->index, nmatch);
1978
1979   /* We may have some registers visible through the block.  */
1980   df_set_bb_dirty (redirect_to);
1981
1982   if (osrc2 == src2)
1983     redirect_edges_to = redirect_to;
1984   else
1985     redirect_edges_to = osrc2;
1986
1987   /* Recompute the frequencies and counts of outgoing edges.  */
1988   FOR_EACH_EDGE (s, ei, redirect_edges_to->succs)
1989     {
1990       edge s2;
1991       edge_iterator ei;
1992       basic_block d = s->dest;
1993
1994       if (FORWARDER_BLOCK_P (d))
1995         d = single_succ (d);
1996
1997       FOR_EACH_EDGE (s2, ei, src1->succs)
1998         {
1999           basic_block d2 = s2->dest;
2000           if (FORWARDER_BLOCK_P (d2))
2001             d2 = single_succ (d2);
2002           if (d == d2)
2003             break;
2004         }
2005
2006       s->count += s2->count;
2007
2008       /* Take care to update possible forwarder blocks.  We verified
2009          that there is no more than one in the chain, so we can't run
2010          into infinite loop.  */
2011       if (FORWARDER_BLOCK_P (s->dest))
2012         {
2013           single_succ_edge (s->dest)->count += s2->count;
2014           s->dest->count += s2->count;
2015           s->dest->frequency += EDGE_FREQUENCY (s);
2016         }
2017
2018       if (FORWARDER_BLOCK_P (s2->dest))
2019         {
2020           single_succ_edge (s2->dest)->count -= s2->count;
2021           if (single_succ_edge (s2->dest)->count < 0)
2022             single_succ_edge (s2->dest)->count = 0;
2023           s2->dest->count -= s2->count;
2024           s2->dest->frequency -= EDGE_FREQUENCY (s);
2025           if (s2->dest->frequency < 0)
2026             s2->dest->frequency = 0;
2027           if (s2->dest->count < 0)
2028             s2->dest->count = 0;
2029         }
2030
2031       if (!redirect_edges_to->frequency && !src1->frequency)
2032         s->probability = (s->probability + s2->probability) / 2;
2033       else
2034         s->probability
2035           = ((s->probability * redirect_edges_to->frequency +
2036               s2->probability * src1->frequency)
2037              / (redirect_edges_to->frequency + src1->frequency));
2038     }
2039
2040   /* Adjust count and frequency for the block.  An earlier jump
2041      threading pass may have left the profile in an inconsistent
2042      state (see update_bb_profile_for_threading) so we must be
2043      prepared for overflows.  */
2044   tmp = redirect_to;
2045   do
2046     {
2047       tmp->count += src1->count;
2048       tmp->frequency += src1->frequency;
2049       if (tmp->frequency > BB_FREQ_MAX)
2050         tmp->frequency = BB_FREQ_MAX;
2051       if (tmp == redirect_edges_to)
2052         break;
2053       tmp = find_fallthru_edge (tmp->succs)->dest;
2054     }
2055   while (true);
2056   update_br_prob_note (redirect_edges_to);
2057
2058   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
2059
2060   /* Skip possible basic block header.  */
2061   if (LABEL_P (newpos1))
2062     newpos1 = NEXT_INSN (newpos1);
2063
2064   while (DEBUG_INSN_P (newpos1))
2065     newpos1 = NEXT_INSN (newpos1);
2066
2067   if (NOTE_INSN_BASIC_BLOCK_P (newpos1))
2068     newpos1 = NEXT_INSN (newpos1);
2069
2070   while (DEBUG_INSN_P (newpos1))
2071     newpos1 = NEXT_INSN (newpos1);
2072
2073   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
2074   to_remove = single_succ (redirect_from);
2075
2076   redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
2077   delete_basic_block (to_remove);
2078
2079   update_forwarder_flag (redirect_from);
2080   if (redirect_to != src2)
2081     update_forwarder_flag (src2);
2082
2083   return true;
2084 }
2085
2086 /* Search the predecessors of BB for common insn sequences.  When found,
2087    share code between them by redirecting control flow.  Return true if
2088    any changes made.  */
2089
2090 static bool
2091 try_crossjump_bb (int mode, basic_block bb)
2092 {
2093   edge e, e2, fallthru;
2094   bool changed;
2095   unsigned max, ix, ix2;
2096
2097   /* Nothing to do if there is not at least two incoming edges.  */
2098   if (EDGE_COUNT (bb->preds) < 2)
2099     return false;
2100
2101   /* Don't crossjump if this block ends in a computed jump,
2102      unless we are optimizing for size.  */
2103   if (optimize_bb_for_size_p (bb)
2104       && bb != EXIT_BLOCK_PTR
2105       && computed_jump_p (BB_END (bb)))
2106     return false;
2107
2108   /* If we are partitioning hot/cold basic blocks, we don't want to
2109      mess up unconditional or indirect jumps that cross between hot
2110      and cold sections.
2111
2112      Basic block partitioning may result in some jumps that appear to
2113      be optimizable (or blocks that appear to be mergeable), but which really
2114      must be left untouched (they are required to make it safely across
2115      partition boundaries).  See the comments at the top of
2116      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
2117
2118   if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
2119                                         BB_PARTITION (EDGE_PRED (bb, 1)->src)
2120       || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
2121     return false;
2122
2123   /* It is always cheapest to redirect a block that ends in a branch to
2124      a block that falls through into BB, as that adds no branches to the
2125      program.  We'll try that combination first.  */
2126   fallthru = NULL;
2127   max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
2128
2129   if (EDGE_COUNT (bb->preds) > max)
2130     return false;
2131
2132   fallthru = find_fallthru_edge (bb->preds);
2133
2134   changed = false;
2135   for (ix = 0; ix < EDGE_COUNT (bb->preds);)
2136     {
2137       e = EDGE_PRED (bb, ix);
2138       ix++;
2139
2140       /* As noted above, first try with the fallthru predecessor (or, a
2141          fallthru predecessor if we are in cfglayout mode).  */
2142       if (fallthru)
2143         {
2144           /* Don't combine the fallthru edge into anything else.
2145              If there is a match, we'll do it the other way around.  */
2146           if (e == fallthru)
2147             continue;
2148           /* If nothing changed since the last attempt, there is nothing
2149              we can do.  */
2150           if (!first_pass
2151               && !((e->src->flags & BB_MODIFIED)
2152                    || (fallthru->src->flags & BB_MODIFIED)))
2153             continue;
2154
2155           if (try_crossjump_to_edge (mode, e, fallthru, dir_forward))
2156             {
2157               changed = true;
2158               ix = 0;
2159               continue;
2160             }
2161         }
2162
2163       /* Non-obvious work limiting check: Recognize that we're going
2164          to call try_crossjump_bb on every basic block.  So if we have
2165          two blocks with lots of outgoing edges (a switch) and they
2166          share lots of common destinations, then we would do the
2167          cross-jump check once for each common destination.
2168
2169          Now, if the blocks actually are cross-jump candidates, then
2170          all of their destinations will be shared.  Which means that
2171          we only need check them for cross-jump candidacy once.  We
2172          can eliminate redundant checks of crossjump(A,B) by arbitrarily
2173          choosing to do the check from the block for which the edge
2174          in question is the first successor of A.  */
2175       if (EDGE_SUCC (e->src, 0) != e)
2176         continue;
2177
2178       for (ix2 = 0; ix2 < EDGE_COUNT (bb->preds); ix2++)
2179         {
2180           e2 = EDGE_PRED (bb, ix2);
2181
2182           if (e2 == e)
2183             continue;
2184
2185           /* We've already checked the fallthru edge above.  */
2186           if (e2 == fallthru)
2187             continue;
2188
2189           /* The "first successor" check above only prevents multiple
2190              checks of crossjump(A,B).  In order to prevent redundant
2191              checks of crossjump(B,A), require that A be the block
2192              with the lowest index.  */
2193           if (e->src->index > e2->src->index)
2194             continue;
2195
2196           /* If nothing changed since the last attempt, there is nothing
2197              we can do.  */
2198           if (!first_pass
2199               && !((e->src->flags & BB_MODIFIED)
2200                    || (e2->src->flags & BB_MODIFIED)))
2201             continue;
2202
2203           /* Both e and e2 are not fallthru edges, so we can crossjump in either
2204              direction.  */
2205           if (try_crossjump_to_edge (mode, e, e2, dir_both))
2206             {
2207               changed = true;
2208               ix = 0;
2209               break;
2210             }
2211         }
2212     }
2213
2214   if (changed)
2215     crossjumps_occured = true;
2216
2217   return changed;
2218 }
2219
2220 /* Search the successors of BB for common insn sequences.  When found,
2221    share code between them by moving it across the basic block
2222    boundary.  Return true if any changes made.  */
2223
2224 static bool
2225 try_head_merge_bb (basic_block bb)
2226 {
2227   basic_block final_dest_bb = NULL;
2228   int max_match = INT_MAX;
2229   edge e0;
2230   rtx *headptr, *currptr, *nextptr;
2231   bool changed, moveall;
2232   unsigned ix;
2233   rtx e0_last_head, cond, move_before;
2234   unsigned nedges = EDGE_COUNT (bb->succs);
2235   rtx jump = BB_END (bb);
2236   regset live, live_union;
2237
2238   /* Nothing to do if there is not at least two outgoing edges.  */
2239   if (nedges < 2)
2240     return false;
2241
2242   /* Don't crossjump if this block ends in a computed jump,
2243      unless we are optimizing for size.  */
2244   if (optimize_bb_for_size_p (bb)
2245       && bb != EXIT_BLOCK_PTR
2246       && computed_jump_p (BB_END (bb)))
2247     return false;
2248
2249   cond = get_condition (jump, &move_before, true, false);
2250   if (cond == NULL_RTX)
2251     {
2252 #ifdef HAVE_cc0
2253       if (reg_mentioned_p (cc0_rtx, jump))
2254         move_before = prev_nonnote_nondebug_insn (jump);
2255       else
2256 #endif
2257         move_before = jump;
2258     }
2259
2260   for (ix = 0; ix < nedges; ix++)
2261     if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR)
2262       return false;
2263
2264   for (ix = 0; ix < nedges; ix++)
2265     {
2266       edge e = EDGE_SUCC (bb, ix);
2267       basic_block other_bb = e->dest;
2268
2269       if (df_get_bb_dirty (other_bb))
2270         {
2271           block_was_dirty = true;
2272           return false;
2273         }
2274
2275       if (e->flags & EDGE_ABNORMAL)
2276         return false;
2277
2278       /* Normally, all destination blocks must only be reachable from this
2279          block, i.e. they must have one incoming edge.
2280
2281          There is one special case we can handle, that of multiple consecutive
2282          jumps where the first jumps to one of the targets of the second jump.
2283          This happens frequently in switch statements for default labels.
2284          The structure is as follows:
2285          FINAL_DEST_BB
2286          ....
2287          if (cond) jump A;
2288          fall through
2289          BB
2290          jump with targets A, B, C, D...
2291          A
2292          has two incoming edges, from FINAL_DEST_BB and BB
2293
2294          In this case, we can try to move the insns through BB and into
2295          FINAL_DEST_BB.  */
2296       if (EDGE_COUNT (other_bb->preds) != 1)
2297         {
2298           edge incoming_edge, incoming_bb_other_edge;
2299           edge_iterator ei;
2300
2301           if (final_dest_bb != NULL
2302               || EDGE_COUNT (other_bb->preds) != 2)
2303             return false;
2304
2305           /* We must be able to move the insns across the whole block.  */
2306           move_before = BB_HEAD (bb);
2307           while (!NONDEBUG_INSN_P (move_before))
2308             move_before = NEXT_INSN (move_before);
2309
2310           if (EDGE_COUNT (bb->preds) != 1)
2311             return false;
2312           incoming_edge = EDGE_PRED (bb, 0);
2313           final_dest_bb = incoming_edge->src;
2314           if (EDGE_COUNT (final_dest_bb->succs) != 2)
2315             return false;
2316           FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
2317             if (incoming_bb_other_edge != incoming_edge)
2318               break;
2319           if (incoming_bb_other_edge->dest != other_bb)
2320             return false;
2321         }
2322     }
2323
2324   e0 = EDGE_SUCC (bb, 0);
2325   e0_last_head = NULL_RTX;
2326   changed = false;
2327
2328   for (ix = 1; ix < nedges; ix++)
2329     {
2330       edge e = EDGE_SUCC (bb, ix);
2331       rtx e0_last, e_last;
2332       int nmatch;
2333
2334       nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
2335                                                  &e0_last, &e_last, 0);
2336       if (nmatch == 0)
2337         return false;
2338
2339       if (nmatch < max_match)
2340         {
2341           max_match = nmatch;
2342           e0_last_head = e0_last;
2343         }
2344     }
2345
2346   /* If we matched an entire block, we probably have to avoid moving the
2347      last insn.  */
2348   if (max_match > 0
2349       && e0_last_head == BB_END (e0->dest)
2350       && (find_reg_note (e0_last_head, REG_EH_REGION, 0)
2351           || control_flow_insn_p (e0_last_head)))
2352     {
2353       max_match--;
2354       if (max_match == 0)
2355         return false;
2356       do
2357         e0_last_head = prev_real_insn (e0_last_head);
2358       while (DEBUG_INSN_P (e0_last_head));
2359     }
2360
2361   if (max_match == 0)
2362     return false;
2363
2364   /* We must find a union of the live registers at each of the end points.  */
2365   live = BITMAP_ALLOC (NULL);
2366   live_union = BITMAP_ALLOC (NULL);
2367
2368   currptr = XNEWVEC (rtx, nedges);
2369   headptr = XNEWVEC (rtx, nedges);
2370   nextptr = XNEWVEC (rtx, nedges);
2371
2372   for (ix = 0; ix < nedges; ix++)
2373     {
2374       int j;
2375       basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
2376       rtx head = BB_HEAD (merge_bb);
2377
2378       while (!NONDEBUG_INSN_P (head))
2379         head = NEXT_INSN (head);
2380       headptr[ix] = head;
2381       currptr[ix] = head;
2382
2383       /* Compute the end point and live information  */
2384       for (j = 1; j < max_match; j++)
2385         do
2386           head = NEXT_INSN (head);
2387         while (!NONDEBUG_INSN_P (head));
2388       simulate_backwards_to_point (merge_bb, live, head);
2389       IOR_REG_SET (live_union, live);
2390     }
2391
2392   /* If we're moving across two blocks, verify the validity of the
2393      first move, then adjust the target and let the loop below deal
2394      with the final move.  */
2395   if (final_dest_bb != NULL)
2396     {
2397       rtx move_upto;
2398
2399       moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
2400                                        jump, e0->dest, live_union,
2401                                        NULL, &move_upto);
2402       if (!moveall)
2403         {
2404           if (move_upto == NULL_RTX)
2405             goto out;
2406
2407           while (e0_last_head != move_upto)
2408             {
2409               df_simulate_one_insn_backwards (e0->dest, e0_last_head,
2410                                               live_union);
2411               e0_last_head = PREV_INSN (e0_last_head);
2412             }
2413         }
2414       if (e0_last_head == NULL_RTX)
2415         goto out;
2416
2417       jump = BB_END (final_dest_bb);
2418       cond = get_condition (jump, &move_before, true, false);
2419       if (cond == NULL_RTX)
2420         {
2421 #ifdef HAVE_cc0
2422           if (reg_mentioned_p (cc0_rtx, jump))
2423             move_before = prev_nonnote_nondebug_insn (jump);
2424           else
2425 #endif
2426             move_before = jump;
2427         }
2428     }
2429
2430   do
2431     {
2432       rtx move_upto;
2433       moveall = can_move_insns_across (currptr[0], e0_last_head,
2434                                        move_before, jump, e0->dest, live_union,
2435                                        NULL, &move_upto);
2436       if (!moveall && move_upto == NULL_RTX)
2437         {
2438           if (jump == move_before)
2439             break;
2440
2441           /* Try again, using a different insertion point.  */
2442           move_before = jump;
2443
2444 #ifdef HAVE_cc0
2445           /* Don't try moving before a cc0 user, as that may invalidate
2446              the cc0.  */
2447           if (reg_mentioned_p (cc0_rtx, jump))
2448             break;
2449 #endif
2450
2451           continue;
2452         }
2453
2454       if (final_dest_bb && !moveall)
2455         /* We haven't checked whether a partial move would be OK for the first
2456            move, so we have to fail this case.  */
2457         break;
2458
2459       changed = true;
2460       for (;;)
2461         {
2462           if (currptr[0] == move_upto)
2463             break;
2464           for (ix = 0; ix < nedges; ix++)
2465             {
2466               rtx curr = currptr[ix];
2467               do
2468                 curr = NEXT_INSN (curr);
2469               while (!NONDEBUG_INSN_P (curr));
2470               currptr[ix] = curr;
2471             }
2472         }
2473
2474       /* If we can't currently move all of the identical insns, remember
2475          each insn after the range that we'll merge.  */
2476       if (!moveall)
2477         for (ix = 0; ix < nedges; ix++)
2478           {
2479             rtx curr = currptr[ix];
2480             do
2481               curr = NEXT_INSN (curr);
2482             while (!NONDEBUG_INSN_P (curr));
2483             nextptr[ix] = curr;
2484           }
2485
2486       reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
2487       df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
2488       if (final_dest_bb != NULL)
2489         df_set_bb_dirty (final_dest_bb);
2490       df_set_bb_dirty (bb);
2491       for (ix = 1; ix < nedges; ix++)
2492         {
2493           df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
2494           delete_insn_chain (headptr[ix], currptr[ix], false);
2495         }
2496       if (!moveall)
2497         {
2498           if (jump == move_before)
2499             break;
2500
2501           /* For the unmerged insns, try a different insertion point.  */
2502           move_before = jump;
2503
2504 #ifdef HAVE_cc0
2505           /* Don't try moving before a cc0 user, as that may invalidate
2506              the cc0.  */
2507           if (reg_mentioned_p (cc0_rtx, jump))
2508             break;
2509 #endif
2510
2511           for (ix = 0; ix < nedges; ix++)
2512             currptr[ix] = headptr[ix] = nextptr[ix];
2513         }
2514     }
2515   while (!moveall);
2516
2517  out:
2518   free (currptr);
2519   free (headptr);
2520   free (nextptr);
2521
2522   crossjumps_occured |= changed;
2523
2524   return changed;
2525 }
2526
2527 /* Return true if BB contains just bb note, or bb note followed
2528    by only DEBUG_INSNs.  */
2529
2530 static bool
2531 trivially_empty_bb_p (basic_block bb)
2532 {
2533   rtx insn = BB_END (bb);
2534
2535   while (1)
2536     {
2537       if (insn == BB_HEAD (bb))
2538         return true;
2539       if (!DEBUG_INSN_P (insn))
2540         return false;
2541       insn = PREV_INSN (insn);
2542     }
2543 }
2544
2545 /* Do simple CFG optimizations - basic block merging, simplifying of jump
2546    instructions etc.  Return nonzero if changes were made.  */
2547
2548 static bool
2549 try_optimize_cfg (int mode)
2550 {
2551   bool changed_overall = false;
2552   bool changed;
2553   int iterations = 0;
2554   basic_block bb, b, next;
2555
2556   if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
2557     clear_bb_flags ();
2558
2559   crossjumps_occured = false;
2560
2561   FOR_EACH_BB (bb)
2562     update_forwarder_flag (bb);
2563
2564   if (! targetm.cannot_modify_jumps_p ())
2565     {
2566       first_pass = true;
2567       /* Attempt to merge blocks as made possible by edge removal.  If
2568          a block has only one successor, and the successor has only
2569          one predecessor, they may be combined.  */
2570       do
2571         {
2572           block_was_dirty = false;
2573           changed = false;
2574           iterations++;
2575
2576           if (dump_file)
2577             fprintf (dump_file,
2578                      "\n\ntry_optimize_cfg iteration %i\n\n",
2579                      iterations);
2580
2581           for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
2582             {
2583               basic_block c;
2584               edge s;
2585               bool changed_here = false;
2586
2587               /* Delete trivially dead basic blocks.  This is either
2588                  blocks with no predecessors, or empty blocks with no
2589                  successors.  However if the empty block with no
2590                  successors is the successor of the ENTRY_BLOCK, it is
2591                  kept.  This ensures that the ENTRY_BLOCK will have a
2592                  successor which is a precondition for many RTL
2593                  passes.  Empty blocks may result from expanding
2594                  __builtin_unreachable ().  */
2595               if (EDGE_COUNT (b->preds) == 0
2596                   || (EDGE_COUNT (b->succs) == 0
2597                       && trivially_empty_bb_p (b)
2598                       && single_succ_edge (ENTRY_BLOCK_PTR)->dest != b))
2599                 {
2600                   c = b->prev_bb;
2601                   if (EDGE_COUNT (b->preds) > 0)
2602                     {
2603                       edge e;
2604                       edge_iterator ei;
2605
2606                       if (current_ir_type () == IR_RTL_CFGLAYOUT)
2607                         {
2608                           if (b->il.rtl->footer
2609                               && BARRIER_P (b->il.rtl->footer))
2610                             FOR_EACH_EDGE (e, ei, b->preds)
2611                               if ((e->flags & EDGE_FALLTHRU)
2612                                   && e->src->il.rtl->footer == NULL)
2613                                 {
2614                                   if (b->il.rtl->footer)
2615                                     {
2616                                       e->src->il.rtl->footer = b->il.rtl->footer;
2617                                       b->il.rtl->footer = NULL;
2618                                     }
2619                                   else
2620                                     {
2621                                       start_sequence ();
2622                                       e->src->il.rtl->footer = emit_barrier ();
2623                                       end_sequence ();
2624                                     }
2625                                 }
2626                         }
2627                       else
2628                         {
2629                           rtx last = get_last_bb_insn (b);
2630                           if (last && BARRIER_P (last))
2631                             FOR_EACH_EDGE (e, ei, b->preds)
2632                               if ((e->flags & EDGE_FALLTHRU))
2633                                 emit_barrier_after (BB_END (e->src));
2634                         }
2635                     }
2636                   delete_basic_block (b);
2637                   changed = true;
2638                   /* Avoid trying to remove ENTRY_BLOCK_PTR.  */
2639                   b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
2640                   continue;
2641                 }
2642
2643               /* Remove code labels no longer used.  */
2644               if (single_pred_p (b)
2645                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2646                   && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
2647                   && LABEL_P (BB_HEAD (b))
2648                   /* If the previous block ends with a branch to this
2649                      block, we can't delete the label.  Normally this
2650                      is a condjump that is yet to be simplified, but
2651                      if CASE_DROPS_THRU, this can be a tablejump with
2652                      some element going to the same place as the
2653                      default (fallthru).  */
2654                   && (single_pred (b) == ENTRY_BLOCK_PTR
2655                       || !JUMP_P (BB_END (single_pred (b)))
2656                       || ! label_is_jump_target_p (BB_HEAD (b),
2657                                                    BB_END (single_pred (b)))))
2658                 {
2659                   rtx label = BB_HEAD (b);
2660
2661                   delete_insn_chain (label, label, false);
2662                   /* If the case label is undeletable, move it after the
2663                      BASIC_BLOCK note.  */
2664                   if (NOTE_KIND (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
2665                     {
2666                       rtx bb_note = NEXT_INSN (BB_HEAD (b));
2667
2668                       reorder_insns_nobb (label, label, bb_note);
2669                       BB_HEAD (b) = bb_note;
2670                       if (BB_END (b) == bb_note)
2671                         BB_END (b) = label;
2672                     }
2673                   if (dump_file)
2674                     fprintf (dump_file, "Deleted label in block %i.\n",
2675                              b->index);
2676                 }
2677
2678               /* If we fall through an empty block, we can remove it.  */
2679               if (!(mode & CLEANUP_CFGLAYOUT)
2680                   && single_pred_p (b)
2681                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2682                   && !LABEL_P (BB_HEAD (b))
2683                   && FORWARDER_BLOCK_P (b)
2684                   /* Note that forwarder_block_p true ensures that
2685                      there is a successor for this block.  */
2686                   && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
2687                   && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
2688                 {
2689                   if (dump_file)
2690                     fprintf (dump_file,
2691                              "Deleting fallthru block %i.\n",
2692                              b->index);
2693
2694                   c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
2695                   redirect_edge_succ_nodup (single_pred_edge (b),
2696                                             single_succ (b));
2697                   delete_basic_block (b);
2698                   changed = true;
2699                   b = c;
2700                   continue;
2701                 }
2702
2703               /* Merge B with its single successor, if any.  */
2704               if (single_succ_p (b)
2705                   && (s = single_succ_edge (b))
2706                   && !(s->flags & EDGE_COMPLEX)
2707                   && (c = s->dest) != EXIT_BLOCK_PTR
2708                   && single_pred_p (c)
2709                   && b != c)
2710                 {
2711                   /* When not in cfg_layout mode use code aware of reordering
2712                      INSN.  This code possibly creates new basic blocks so it
2713                      does not fit merge_blocks interface and is kept here in
2714                      hope that it will become useless once more of compiler
2715                      is transformed to use cfg_layout mode.  */
2716
2717                   if ((mode & CLEANUP_CFGLAYOUT)
2718                       && can_merge_blocks_p (b, c))
2719                     {
2720                       merge_blocks (b, c);
2721                       update_forwarder_flag (b);
2722                       changed_here = true;
2723                     }
2724                   else if (!(mode & CLEANUP_CFGLAYOUT)
2725                            /* If the jump insn has side effects,
2726                               we can't kill the edge.  */
2727                            && (!JUMP_P (BB_END (b))
2728                                || (reload_completed
2729                                    ? simplejump_p (BB_END (b))
2730                                    : (onlyjump_p (BB_END (b))
2731                                       && !tablejump_p (BB_END (b),
2732                                                        NULL, NULL))))
2733                            && (next = merge_blocks_move (s, b, c, mode)))
2734                       {
2735                         b = next;
2736                         changed_here = true;
2737                       }
2738                 }
2739
2740               /* Simplify branch over branch.  */
2741               if ((mode & CLEANUP_EXPENSIVE)
2742                    && !(mode & CLEANUP_CFGLAYOUT)
2743                    && try_simplify_condjump (b))
2744                 changed_here = true;
2745
2746               /* If B has a single outgoing edge, but uses a
2747                  non-trivial jump instruction without side-effects, we
2748                  can either delete the jump entirely, or replace it
2749                  with a simple unconditional jump.  */
2750               if (single_succ_p (b)
2751                   && single_succ (b) != EXIT_BLOCK_PTR
2752                   && onlyjump_p (BB_END (b))
2753                   && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
2754                   && try_redirect_by_replacing_jump (single_succ_edge (b),
2755                                                      single_succ (b),
2756                                                      (mode & CLEANUP_CFGLAYOUT) != 0))
2757                 {
2758                   update_forwarder_flag (b);
2759                   changed_here = true;
2760                 }
2761
2762               /* Simplify branch to branch.  */
2763               if (try_forward_edges (mode, b))
2764                 {
2765                   update_forwarder_flag (b);
2766                   changed_here = true;
2767                 }
2768
2769               /* Look for shared code between blocks.  */
2770               if ((mode & CLEANUP_CROSSJUMP)
2771                   && try_crossjump_bb (mode, b))
2772                 changed_here = true;
2773
2774               if ((mode & CLEANUP_CROSSJUMP)
2775                   /* This can lengthen register lifetimes.  Do it only after
2776                      reload.  */
2777                   && reload_completed
2778                   && try_head_merge_bb (b))
2779                 changed_here = true;
2780
2781               /* Don't get confused by the index shift caused by
2782                  deleting blocks.  */
2783               if (!changed_here)
2784                 b = b->next_bb;
2785               else
2786                 changed = true;
2787             }
2788
2789           if ((mode & CLEANUP_CROSSJUMP)
2790               && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
2791             changed = true;
2792
2793           if (block_was_dirty)
2794             {
2795               /* This should only be set by head-merging.  */
2796               gcc_assert (mode & CLEANUP_CROSSJUMP);
2797               df_analyze ();
2798             }
2799
2800 #ifdef ENABLE_CHECKING
2801           if (changed)
2802             verify_flow_info ();
2803 #endif
2804
2805           changed_overall |= changed;
2806           first_pass = false;
2807         }
2808       while (changed);
2809     }
2810
2811   FOR_ALL_BB (b)
2812     b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
2813
2814   return changed_overall;
2815 }
2816 \f
2817 /* Delete all unreachable basic blocks.  */
2818
2819 bool
2820 delete_unreachable_blocks (void)
2821 {
2822   bool changed = false;
2823   basic_block b, prev_bb;
2824
2825   find_unreachable_blocks ();
2826
2827   /* When we're in GIMPLE mode and there may be debug insns, we should
2828      delete blocks in reverse dominator order, so as to get a chance
2829      to substitute all released DEFs into debug stmts.  If we don't
2830      have dominators information, walking blocks backward gets us a
2831      better chance of retaining most debug information than
2832      otherwise.  */
2833   if (MAY_HAVE_DEBUG_STMTS && current_ir_type () == IR_GIMPLE
2834       && dom_info_available_p (CDI_DOMINATORS))
2835     {
2836       for (b = EXIT_BLOCK_PTR->prev_bb; b != ENTRY_BLOCK_PTR; b = prev_bb)
2837         {
2838           prev_bb = b->prev_bb;
2839
2840           if (!(b->flags & BB_REACHABLE))
2841             {
2842               /* Speed up the removal of blocks that don't dominate
2843                  others.  Walking backwards, this should be the common
2844                  case.  */
2845               if (!first_dom_son (CDI_DOMINATORS, b))
2846                 delete_basic_block (b);
2847               else
2848                 {
2849                   VEC (basic_block, heap) *h
2850                     = get_all_dominated_blocks (CDI_DOMINATORS, b);
2851
2852                   while (VEC_length (basic_block, h))
2853                     {
2854                       b = VEC_pop (basic_block, h);
2855
2856                       prev_bb = b->prev_bb;
2857
2858                       gcc_assert (!(b->flags & BB_REACHABLE));
2859
2860                       delete_basic_block (b);
2861                     }
2862
2863                   VEC_free (basic_block, heap, h);
2864                 }
2865
2866               changed = true;
2867             }
2868         }
2869     }
2870   else
2871     {
2872       for (b = EXIT_BLOCK_PTR->prev_bb; b != ENTRY_BLOCK_PTR; b = prev_bb)
2873         {
2874           prev_bb = b->prev_bb;
2875
2876           if (!(b->flags & BB_REACHABLE))
2877             {
2878               delete_basic_block (b);
2879               changed = true;
2880             }
2881         }
2882     }
2883
2884   if (changed)
2885     tidy_fallthru_edges ();
2886   return changed;
2887 }
2888
2889 /* Delete any jump tables never referenced.  We can't delete them at the
2890    time of removing tablejump insn as they are referenced by the preceding
2891    insns computing the destination, so we delay deleting and garbagecollect
2892    them once life information is computed.  */
2893 void
2894 delete_dead_jumptables (void)
2895 {
2896   basic_block bb;
2897
2898   /* A dead jump table does not belong to any basic block.  Scan insns
2899      between two adjacent basic blocks.  */
2900   FOR_EACH_BB (bb)
2901     {
2902       rtx insn, next;
2903
2904       for (insn = NEXT_INSN (BB_END (bb));
2905            insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
2906            insn = next)
2907         {
2908           next = NEXT_INSN (insn);
2909           if (LABEL_P (insn)
2910               && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
2911               && JUMP_TABLE_DATA_P (next))
2912             {
2913               rtx label = insn, jump = next;
2914
2915               if (dump_file)
2916                 fprintf (dump_file, "Dead jumptable %i removed\n",
2917                          INSN_UID (insn));
2918
2919               next = NEXT_INSN (next);
2920               delete_insn (jump);
2921               delete_insn (label);
2922             }
2923         }
2924     }
2925 }
2926
2927 \f
2928 /* Tidy the CFG by deleting unreachable code and whatnot.  */
2929
2930 bool
2931 cleanup_cfg (int mode)
2932 {
2933   bool changed = false;
2934
2935   /* Set the cfglayout mode flag here.  We could update all the callers
2936      but that is just inconvenient, especially given that we eventually
2937      want to have cfglayout mode as the default.  */
2938   if (current_ir_type () == IR_RTL_CFGLAYOUT)
2939     mode |= CLEANUP_CFGLAYOUT;
2940
2941   timevar_push (TV_CLEANUP_CFG);
2942   if (delete_unreachable_blocks ())
2943     {
2944       changed = true;
2945       /* We've possibly created trivially dead code.  Cleanup it right
2946          now to introduce more opportunities for try_optimize_cfg.  */
2947       if (!(mode & (CLEANUP_NO_INSN_DEL))
2948           && !reload_completed)
2949         delete_trivially_dead_insns (get_insns (), max_reg_num ());
2950     }
2951
2952   compact_blocks ();
2953
2954   /* To tail-merge blocks ending in the same noreturn function (e.g.
2955      a call to abort) we have to insert fake edges to exit.  Do this
2956      here once.  The fake edges do not interfere with any other CFG
2957      cleanups.  */
2958   if (mode & CLEANUP_CROSSJUMP)
2959     add_noreturn_fake_exit_edges ();
2960
2961   if (!dbg_cnt (cfg_cleanup))
2962     return changed;
2963
2964   while (try_optimize_cfg (mode))
2965     {
2966       delete_unreachable_blocks (), changed = true;
2967       if (!(mode & CLEANUP_NO_INSN_DEL))
2968         {
2969           /* Try to remove some trivially dead insns when doing an expensive
2970              cleanup.  But delete_trivially_dead_insns doesn't work after
2971              reload (it only handles pseudos) and run_fast_dce is too costly
2972              to run in every iteration.
2973
2974              For effective cross jumping, we really want to run a fast DCE to
2975              clean up any dead conditions, or they get in the way of performing
2976              useful tail merges.
2977
2978              Other transformations in cleanup_cfg are not so sensitive to dead
2979              code, so delete_trivially_dead_insns or even doing nothing at all
2980              is good enough.  */
2981           if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
2982               && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2983             break;
2984           if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occured)
2985             run_fast_dce ();
2986         }
2987       else
2988         break;
2989     }
2990
2991   if (mode & CLEANUP_CROSSJUMP)
2992     remove_fake_exit_edges ();
2993
2994   /* Don't call delete_dead_jumptables in cfglayout mode, because
2995      that function assumes that jump tables are in the insns stream.
2996      But we also don't _have_ to delete dead jumptables in cfglayout
2997      mode because we shouldn't even be looking at things that are
2998      not in a basic block.  Dead jumptables are cleaned up when
2999      going out of cfglayout mode.  */
3000   if (!(mode & CLEANUP_CFGLAYOUT))
3001     delete_dead_jumptables ();
3002
3003   timevar_pop (TV_CLEANUP_CFG);
3004
3005   return changed;
3006 }
3007 \f
3008 static unsigned int
3009 rest_of_handle_jump (void)
3010 {
3011   if (crtl->tail_call_emit)
3012     fixup_tail_calls ();
3013   return 0;
3014 }
3015
3016 struct rtl_opt_pass pass_jump =
3017 {
3018  {
3019   RTL_PASS,
3020   "sibling",                            /* name */
3021   NULL,                                 /* gate */
3022   rest_of_handle_jump,                  /* execute */
3023   NULL,                                 /* sub */
3024   NULL,                                 /* next */
3025   0,                                    /* static_pass_number */
3026   TV_JUMP,                              /* tv_id */
3027   0,                                    /* properties_required */
3028   0,                                    /* properties_provided */
3029   0,                                    /* properties_destroyed */
3030   TODO_ggc_collect,                     /* todo_flags_start */
3031   TODO_verify_flow,                     /* todo_flags_finish */
3032  }
3033 };
3034
3035
3036 static unsigned int
3037 rest_of_handle_jump2 (void)
3038 {
3039   delete_trivially_dead_insns (get_insns (), max_reg_num ());
3040   if (dump_file)
3041     dump_flow_info (dump_file, dump_flags);
3042   cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
3043                | (flag_thread_jumps ? CLEANUP_THREADING : 0));
3044   return 0;
3045 }
3046
3047
3048 struct rtl_opt_pass pass_jump2 =
3049 {
3050  {
3051   RTL_PASS,
3052   "jump",                               /* name */
3053   NULL,                                 /* gate */
3054   rest_of_handle_jump2,                 /* execute */
3055   NULL,                                 /* sub */
3056   NULL,                                 /* next */
3057   0,                                    /* static_pass_number */
3058   TV_JUMP,                              /* tv_id */
3059   0,                                    /* properties_required */
3060   0,                                    /* properties_provided */
3061   0,                                    /* properties_destroyed */
3062   TODO_ggc_collect,                     /* todo_flags_start */
3063   TODO_verify_rtl_sharing,              /* todo_flags_finish */
3064  }
3065 };