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