OSDN Git Service

PR rtl-optimization/31391
[pf3gnuchains/gcc-fork.git] / gcc / cfgcleanup.c
1 /* Control flow optimization code for GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
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 2, 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 COPYING.  If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA.  */
22
23 /* This file contains optimizer of the control flow.  The main entry point is
24    cleanup_cfg.  Following optimizations are performed:
25
26    - Unreachable blocks removal
27    - Edge forwarding (edge to the forwarder block is forwarded to its
28      successor.  Simplification of the branch instruction is performed by
29      underlying infrastructure so branch can be converted to simplejump or
30      eliminated).
31    - Cross jumping (tail merging)
32    - Conditional jump-around-simplejump simplification
33    - Basic block merging.  */
34
35 #include "config.h"
36 #include "system.h"
37 #include "coretypes.h"
38 #include "tm.h"
39 #include "rtl.h"
40 #include "hard-reg-set.h"
41 #include "regs.h"
42 #include "timevar.h"
43 #include "output.h"
44 #include "insn-config.h"
45 #include "flags.h"
46 #include "recog.h"
47 #include "toplev.h"
48 #include "cselib.h"
49 #include "params.h"
50 #include "tm_p.h"
51 #include "target.h"
52 #include "cfglayout.h"
53 #include "emit-rtl.h"
54 #include "tree-pass.h"
55 #include "cfgloop.h"
56 #include "expr.h"
57
58 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
59
60 /* Set to true when we are running first pass of try_optimize_cfg loop.  */
61 static bool first_pass;
62 static bool try_crossjump_to_edge (int, edge, edge);
63 static bool try_crossjump_bb (int, basic_block);
64 static bool outgoing_edges_match (int, basic_block, basic_block);
65 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
66 static bool old_insns_match_p (int, rtx, rtx);
67
68 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
69 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
70 static bool try_optimize_cfg (int);
71 static bool try_simplify_condjump (basic_block);
72 static bool try_forward_edges (int, basic_block);
73 static edge thread_jump (int, edge, basic_block);
74 static bool mark_effect (rtx, bitmap);
75 static void notice_new_block (basic_block);
76 static void update_forwarder_flag (basic_block);
77 static int mentions_nonequal_regs (rtx *, void *);
78 static void merge_memattrs (rtx, rtx);
79 \f
80 /* Set flags for newly created block.  */
81
82 static void
83 notice_new_block (basic_block bb)
84 {
85   if (!bb)
86     return;
87
88   if (forwarder_block_p (bb))
89     bb->flags |= BB_FORWARDER_BLOCK;
90 }
91
92 /* Recompute forwarder flag after block has been modified.  */
93
94 static void
95 update_forwarder_flag (basic_block bb)
96 {
97   if (forwarder_block_p (bb))
98     bb->flags |= BB_FORWARDER_BLOCK;
99   else
100     bb->flags &= ~BB_FORWARDER_BLOCK;
101 }
102 \f
103 /* Simplify a conditional jump around an unconditional jump.
104    Return true if something changed.  */
105
106 static bool
107 try_simplify_condjump (basic_block cbranch_block)
108 {
109   basic_block jump_block, jump_dest_block, cbranch_dest_block;
110   edge cbranch_jump_edge, cbranch_fallthru_edge;
111   rtx cbranch_insn;
112
113   /* Verify that there are exactly two successors.  */
114   if (EDGE_COUNT (cbranch_block->succs) != 2)
115     return false;
116
117   /* Verify that we've got a normal conditional branch at the end
118      of the block.  */
119   cbranch_insn = BB_END (cbranch_block);
120   if (!any_condjump_p (cbranch_insn))
121     return false;
122
123   cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
124   cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
125
126   /* The next block must not have multiple predecessors, must not
127      be the last block in the function, and must contain just the
128      unconditional jump.  */
129   jump_block = cbranch_fallthru_edge->dest;
130   if (!single_pred_p (jump_block)
131       || jump_block->next_bb == EXIT_BLOCK_PTR
132       || !FORWARDER_BLOCK_P (jump_block))
133     return false;
134   jump_dest_block = single_succ (jump_block);
135
136   /* If we are partitioning hot/cold basic blocks, we don't want to
137      mess up unconditional or indirect jumps that cross between hot
138      and cold sections.
139
140      Basic block partitioning may result in some jumps that appear to
141      be optimizable (or blocks that appear to be mergeable), but which really
142      must be left untouched (they are required to make it safely across
143      partition boundaries).  See the comments at the top of
144      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
145
146   if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
147       || (cbranch_jump_edge->flags & EDGE_CROSSING))
148     return false;
149
150   /* The conditional branch must target the block after the
151      unconditional branch.  */
152   cbranch_dest_block = cbranch_jump_edge->dest;
153
154   if (cbranch_dest_block == EXIT_BLOCK_PTR
155       || !can_fallthru (jump_block, cbranch_dest_block))
156     return false;
157
158   /* Invert the conditional branch.  */
159   if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
160     return false;
161
162   if (dump_file)
163     fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
164              INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
165
166   /* Success.  Update the CFG to match.  Note that after this point
167      the edge variable names appear backwards; the redirection is done
168      this way to preserve edge profile data.  */
169   cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
170                                                 cbranch_dest_block);
171   cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
172                                                     jump_dest_block);
173   cbranch_jump_edge->flags |= EDGE_FALLTHRU;
174   cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
175   update_br_prob_note (cbranch_block);
176
177   /* Delete the block with the unconditional jump, and clean up the mess.  */
178   delete_basic_block (jump_block);
179   tidy_fallthru_edge (cbranch_jump_edge);
180   update_forwarder_flag (cbranch_block);
181
182   return true;
183 }
184 \f
185 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
186    on register.  Used by jump threading.  */
187
188 static bool
189 mark_effect (rtx exp, regset nonequal)
190 {
191   int regno;
192   rtx dest;
193   switch (GET_CODE (exp))
194     {
195       /* In case we do clobber the register, mark it as equal, as we know the
196          value is dead so it don't have to match.  */
197     case CLOBBER:
198       if (REG_P (XEXP (exp, 0)))
199         {
200           dest = XEXP (exp, 0);
201           regno = REGNO (dest);
202           CLEAR_REGNO_REG_SET (nonequal, regno);
203           if (regno < FIRST_PSEUDO_REGISTER)
204             {
205               int n = hard_regno_nregs[regno][GET_MODE (dest)];
206               while (--n > 0)
207                 CLEAR_REGNO_REG_SET (nonequal, regno + n);
208             }
209         }
210       return false;
211
212     case SET:
213       if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
214         return false;
215       dest = SET_DEST (exp);
216       if (dest == pc_rtx)
217         return false;
218       if (!REG_P (dest))
219         return true;
220       regno = REGNO (dest);
221       SET_REGNO_REG_SET (nonequal, regno);
222       if (regno < FIRST_PSEUDO_REGISTER)
223         {
224           int n = hard_regno_nregs[regno][GET_MODE (dest)];
225           while (--n > 0)
226             SET_REGNO_REG_SET (nonequal, regno + n);
227         }
228       return false;
229
230     default:
231       return false;
232     }
233 }
234
235 /* Return nonzero if X is a register set in regset DATA.
236    Called via for_each_rtx.  */
237 static int
238 mentions_nonequal_regs (rtx *x, void *data)
239 {
240   regset nonequal = (regset) data;
241   if (REG_P (*x))
242     {
243       int regno;
244
245       regno = REGNO (*x);
246       if (REGNO_REG_SET_P (nonequal, regno))
247         return 1;
248       if (regno < FIRST_PSEUDO_REGISTER)
249         {
250           int n = hard_regno_nregs[regno][GET_MODE (*x)];
251           while (--n > 0)
252             if (REGNO_REG_SET_P (nonequal, regno + n))
253               return 1;
254         }
255     }
256   return 0;
257 }
258 /* Attempt to prove that the basic block B will have no side effects and
259    always continues in the same edge if reached via E.  Return the edge
260    if exist, NULL otherwise.  */
261
262 static edge
263 thread_jump (int mode, edge e, basic_block b)
264 {
265   rtx set1, set2, cond1, cond2, insn;
266   enum rtx_code code1, code2, reversed_code2;
267   bool reverse1 = false;
268   unsigned i;
269   regset nonequal;
270   bool failed = false;
271   reg_set_iterator rsi;
272
273   if (b->flags & BB_NONTHREADABLE_BLOCK)
274     return NULL;
275
276   /* At the moment, we do handle only conditional jumps, but later we may
277      want to extend this code to tablejumps and others.  */
278   if (EDGE_COUNT (e->src->succs) != 2)
279     return NULL;
280   if (EDGE_COUNT (b->succs) != 2)
281     {
282       b->flags |= BB_NONTHREADABLE_BLOCK;
283       return NULL;
284     }
285
286   /* Second branch must end with onlyjump, as we will eliminate the jump.  */
287   if (!any_condjump_p (BB_END (e->src)))
288     return NULL;
289
290   if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
291     {
292       b->flags |= BB_NONTHREADABLE_BLOCK;
293       return NULL;
294     }
295
296   set1 = pc_set (BB_END (e->src));
297   set2 = pc_set (BB_END (b));
298   if (((e->flags & EDGE_FALLTHRU) != 0)
299       != (XEXP (SET_SRC (set1), 1) == pc_rtx))
300     reverse1 = true;
301
302   cond1 = XEXP (SET_SRC (set1), 0);
303   cond2 = XEXP (SET_SRC (set2), 0);
304   if (reverse1)
305     code1 = reversed_comparison_code (cond1, BB_END (e->src));
306   else
307     code1 = GET_CODE (cond1);
308
309   code2 = GET_CODE (cond2);
310   reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
311
312   if (!comparison_dominates_p (code1, code2)
313       && !comparison_dominates_p (code1, reversed_code2))
314     return NULL;
315
316   /* Ensure that the comparison operators are equivalent.
317      ??? This is far too pessimistic.  We should allow swapped operands,
318      different CCmodes, or for example comparisons for interval, that
319      dominate even when operands are not equivalent.  */
320   if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
321       || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
322     return NULL;
323
324   /* Short circuit cases where block B contains some side effects, as we can't
325      safely bypass it.  */
326   for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
327        insn = NEXT_INSN (insn))
328     if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
329       {
330         b->flags |= BB_NONTHREADABLE_BLOCK;
331         return NULL;
332       }
333
334   cselib_init (false);
335
336   /* First process all values computed in the source basic block.  */
337   for (insn = NEXT_INSN (BB_HEAD (e->src));
338        insn != NEXT_INSN (BB_END (e->src));
339        insn = NEXT_INSN (insn))
340     if (INSN_P (insn))
341       cselib_process_insn (insn);
342
343   nonequal = BITMAP_ALLOC (NULL);
344   CLEAR_REG_SET (nonequal);
345
346   /* Now assume that we've continued by the edge E to B and continue
347      processing as if it were same basic block.
348      Our goal is to prove that whole block is an NOOP.  */
349
350   for (insn = NEXT_INSN (BB_HEAD (b));
351        insn != NEXT_INSN (BB_END (b)) && !failed;
352        insn = NEXT_INSN (insn))
353     {
354       if (INSN_P (insn))
355         {
356           rtx pat = PATTERN (insn);
357
358           if (GET_CODE (pat) == PARALLEL)
359             {
360               for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
361                 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
362             }
363           else
364             failed |= mark_effect (pat, nonequal);
365         }
366
367       cselib_process_insn (insn);
368     }
369
370   /* Later we should clear nonequal of dead registers.  So far we don't
371      have life information in cfg_cleanup.  */
372   if (failed)
373     {
374       b->flags |= BB_NONTHREADABLE_BLOCK;
375       goto failed_exit;
376     }
377
378   /* cond2 must not mention any register that is not equal to the
379      former block.  */
380   if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
381     goto failed_exit;
382
383   /* In case liveness information is available, we need to prove equivalence
384      only of the live values.  */
385   if (mode & CLEANUP_UPDATE_LIFE)
386     AND_REG_SET (nonequal, b->il.rtl->global_live_at_end);
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 m
421      ust 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;
432       bool threaded = false;
433       int nthreaded_edges = 0;
434       bool may_thread = first_pass | (b->flags & BB_DIRTY);
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
450       /* If we are partitioning hot/cold basic_blocks, we don't want to mess
451          up jumps that cross between hot/cold sections.
452
453          Basic block partitioning may result in some jumps that appear
454          to be optimizable (or blocks that appear to be mergeable), but which
455          really must be left untouched (they are required to make it safely
456          across partition boundaries).  See the comments at the top of
457          bb-reorder.c:partition_hot_cold_basic_blocks for complete
458          details.  */
459
460       if (first != EXIT_BLOCK_PTR
461           && find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX))
462         return false;
463
464       while (counter < n_basic_blocks)
465         {
466           basic_block new_target = NULL;
467           bool new_target_threaded = false;
468           may_thread |= target->flags & BB_DIRTY;
469
470           if (FORWARDER_BLOCK_P (target)
471               && !(single_succ_edge (target)->flags & EDGE_CROSSING)
472               && single_succ (target) != EXIT_BLOCK_PTR)
473             {
474               /* Bypass trivial infinite loops.  */
475               new_target = single_succ (target);
476               if (target == new_target)
477                 counter = n_basic_blocks;
478             }
479
480           /* Allow to thread only over one edge at time to simplify updating
481              of probabilities.  */
482           else if ((mode & CLEANUP_THREADING) && may_thread)
483             {
484               edge t = thread_jump (mode, e, target);
485               if (t)
486                 {
487                   if (!threaded_edges)
488                     threaded_edges = XNEWVEC (edge, n_basic_blocks);
489                   else
490                     {
491                       int i;
492
493                       /* Detect an infinite loop across blocks not
494                          including the start block.  */
495                       for (i = 0; i < nthreaded_edges; ++i)
496                         if (threaded_edges[i] == t)
497                           break;
498                       if (i < nthreaded_edges)
499                         {
500                           counter = n_basic_blocks;
501                           break;
502                         }
503                     }
504
505                   /* Detect an infinite loop across the start block.  */
506                   if (t->dest == b)
507                     break;
508
509                   gcc_assert (nthreaded_edges < n_basic_blocks - NUM_FIXED_BLOCKS);
510                   threaded_edges[nthreaded_edges++] = t;
511
512                   new_target = t->dest;
513                   new_target_threaded = true;
514                 }
515             }
516
517           if (!new_target)
518             break;
519
520           counter++;
521           target = new_target;
522           threaded |= new_target_threaded;
523         }
524
525       if (counter >= n_basic_blocks)
526         {
527           if (dump_file)
528             fprintf (dump_file, "Infinite loop in BB %i.\n",
529                      target->index);
530         }
531       else if (target == first)
532         ; /* We didn't do anything.  */
533       else
534         {
535           /* Save the values now, as the edge may get removed.  */
536           gcov_type edge_count = e->count;
537           int edge_probability = e->probability;
538           int edge_frequency;
539           int n = 0;
540
541           /* Don't force if target is exit block.  */
542           if (threaded && target != EXIT_BLOCK_PTR)
543             {
544               notice_new_block (redirect_edge_and_branch_force (e, target));
545               if (dump_file)
546                 fprintf (dump_file, "Conditionals threaded.\n");
547             }
548           else if (!redirect_edge_and_branch (e, target))
549             {
550               if (dump_file)
551                 fprintf (dump_file,
552                          "Forwarding edge %i->%i to %i failed.\n",
553                          b->index, e->dest->index, target->index);
554               ei_next (&ei);
555               continue;
556             }
557
558           /* We successfully forwarded the edge.  Now update profile
559              data: for each edge we traversed in the chain, remove
560              the original edge's execution count.  */
561           edge_frequency = ((edge_probability * b->frequency
562                              + REG_BR_PROB_BASE / 2)
563                             / REG_BR_PROB_BASE);
564
565           if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
566             b->flags |= BB_FORWARDER_BLOCK;
567
568           do
569             {
570               edge t;
571
572               if (!single_succ_p (first))
573                 {
574                   gcc_assert (n < nthreaded_edges);
575                   t = threaded_edges [n++];
576                   gcc_assert (t->src == first);
577                   update_bb_profile_for_threading (first, edge_frequency,
578                                                    edge_count, t);
579                   update_br_prob_note (first);
580                 }
581               else
582                 {
583                   first->count -= edge_count;
584                   if (first->count < 0)
585                     first->count = 0;
586                   first->frequency -= edge_frequency;
587                   if (first->frequency < 0)
588                     first->frequency = 0;
589                   /* It is possible that as the result of
590                      threading we've removed edge as it is
591                      threaded to the fallthru edge.  Avoid
592                      getting out of sync.  */
593                   if (n < nthreaded_edges
594                       && first == threaded_edges [n]->src)
595                     n++;
596                   t = single_succ_edge (first);
597                 }
598
599               t->count -= edge_count;
600               if (t->count < 0)
601                 t->count = 0;
602               first = t->dest;
603             }
604           while (first != target);
605
606           changed = true;
607           continue;
608         }
609       ei_next (&ei);
610     }
611
612   if (threaded_edges)
613     free (threaded_edges);
614   return changed;
615 }
616 \f
617
618 /* Blocks A and B are to be merged into a single block.  A has no incoming
619    fallthru edge, so it can be moved before B without adding or modifying
620    any jumps (aside from the jump from A to B).  */
621
622 static void
623 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
624 {
625   rtx barrier;
626   bool only_notes;
627
628   /* If we are partitioning hot/cold basic blocks, we don't want to
629      mess up unconditional or indirect jumps that cross between hot
630      and cold sections.
631
632      Basic block partitioning may result in some jumps that appear to
633      be optimizable (or blocks that appear to be mergeable), but which really
634      must be left untouched (they are required to make it safely across
635      partition boundaries).  See the comments at the top of
636      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
637
638   if (BB_PARTITION (a) != BB_PARTITION (b))
639     return;
640
641   barrier = next_nonnote_insn (BB_END (a));
642   gcc_assert (BARRIER_P (barrier));
643   delete_insn (barrier);
644
645   /* Move block and loop notes out of the chain so that we do not
646      disturb their order.
647
648      ??? A better solution would be to squeeze out all the non-nested notes
649      and adjust the block trees appropriately.   Even better would be to have
650      a tighter connection between block trees and rtl so that this is not
651      necessary.  */
652   only_notes = squeeze_notes (&BB_HEAD (a), &BB_END (a));
653   gcc_assert (!only_notes);
654
655   /* Scramble the insn chain.  */
656   if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
657     reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
658   a->flags |= BB_DIRTY;
659
660   if (dump_file)
661     fprintf (dump_file, "Moved block %d before %d and merged.\n",
662              a->index, b->index);
663
664   /* Swap the records for the two blocks around.  */
665
666   unlink_block (a);
667   link_block (a, b->prev_bb);
668
669   /* Now blocks A and B are contiguous.  Merge them.  */
670   merge_blocks (a, b);
671 }
672
673 /* Blocks A and B are to be merged into a single block.  B has no outgoing
674    fallthru edge, so it can be moved after A without adding or modifying
675    any jumps (aside from the jump from A to B).  */
676
677 static void
678 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
679 {
680   rtx barrier, real_b_end;
681   rtx label, table;
682   bool only_notes;
683
684   /* If we are partitioning hot/cold basic blocks, we don't want to
685      mess up unconditional or indirect jumps that cross between hot
686      and cold sections.
687
688      Basic block partitioning may result in some jumps that appear to
689      be optimizable (or blocks that appear to be mergeable), but which really
690      must be left untouched (they are required to make it safely across
691      partition boundaries).  See the comments at the top of
692      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
693
694   if (BB_PARTITION (a) != BB_PARTITION (b))
695     return;
696
697   real_b_end = BB_END (b);
698
699   /* If there is a jump table following block B temporarily add the jump table
700      to block B so that it will also be moved to the correct location.  */
701   if (tablejump_p (BB_END (b), &label, &table)
702       && prev_active_insn (label) == BB_END (b))
703     {
704       BB_END (b) = table;
705     }
706
707   /* There had better have been a barrier there.  Delete it.  */
708   barrier = NEXT_INSN (BB_END (b));
709   if (barrier && BARRIER_P (barrier))
710     delete_insn (barrier);
711
712   /* Move block and loop notes out of the chain so that we do not
713      disturb their order.
714
715      ??? A better solution would be to squeeze out all the non-nested notes
716      and adjust the block trees appropriately.   Even better would be to have
717      a tighter connection between block trees and rtl so that this is not
718      necessary.  */
719   only_notes = squeeze_notes (&BB_HEAD (b), &BB_END (b));
720   gcc_assert (!only_notes);
721
722
723   /* Scramble the insn chain.  */
724   reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
725
726   /* Restore the real end of b.  */
727   BB_END (b) = real_b_end;
728
729   if (dump_file)
730     fprintf (dump_file, "Moved block %d after %d and merged.\n",
731              b->index, a->index);
732
733   /* Now blocks A and B are contiguous.  Merge them.  */
734   merge_blocks (a, b);
735 }
736
737 /* Attempt to merge basic blocks that are potentially non-adjacent.
738    Return NULL iff the attempt failed, otherwise return basic block
739    where cleanup_cfg should continue.  Because the merging commonly
740    moves basic block away or introduces another optimization
741    possibility, return basic block just before B so cleanup_cfg don't
742    need to iterate.
743
744    It may be good idea to return basic block before C in the case
745    C has been moved after B and originally appeared earlier in the
746    insn sequence, but we have no information available about the
747    relative ordering of these two.  Hopefully it is not too common.  */
748
749 static basic_block
750 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
751 {
752   basic_block next;
753
754   /* If we are partitioning hot/cold basic blocks, we don't want to
755      mess up unconditional or indirect jumps that cross between hot
756      and cold sections.
757
758      Basic block partitioning may result in some jumps that appear to
759      be optimizable (or blocks that appear to be mergeable), but which really
760      must be left untouched (they are required to make it safely across
761      partition boundaries).  See the comments at the top of
762      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
763
764   if (BB_PARTITION (b) != BB_PARTITION (c))
765     return NULL;
766
767   /* If B has a fallthru edge to C, no need to move anything.  */
768   if (e->flags & EDGE_FALLTHRU)
769     {
770       int b_index = b->index, c_index = c->index;
771       merge_blocks (b, c);
772       update_forwarder_flag (b);
773
774       if (dump_file)
775         fprintf (dump_file, "Merged %d and %d without moving.\n",
776                  b_index, c_index);
777
778       return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
779     }
780
781   /* Otherwise we will need to move code around.  Do that only if expensive
782      transformations are allowed.  */
783   else if (mode & CLEANUP_EXPENSIVE)
784     {
785       edge tmp_edge, b_fallthru_edge;
786       bool c_has_outgoing_fallthru;
787       bool b_has_incoming_fallthru;
788       edge_iterator ei;
789
790       /* Avoid overactive code motion, as the forwarder blocks should be
791          eliminated by edge redirection instead.  One exception might have
792          been if B is a forwarder block and C has no fallthru edge, but
793          that should be cleaned up by bb-reorder instead.  */
794       if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
795         return NULL;
796
797       /* We must make sure to not munge nesting of lexical blocks,
798          and loop notes.  This is done by squeezing out all the notes
799          and leaving them there to lie.  Not ideal, but functional.  */
800
801       FOR_EACH_EDGE (tmp_edge, ei, c->succs)
802         if (tmp_edge->flags & EDGE_FALLTHRU)
803           break;
804
805       c_has_outgoing_fallthru = (tmp_edge != NULL);
806
807       FOR_EACH_EDGE (tmp_edge, ei, b->preds)
808         if (tmp_edge->flags & EDGE_FALLTHRU)
809           break;
810
811       b_has_incoming_fallthru = (tmp_edge != NULL);
812       b_fallthru_edge = tmp_edge;
813       next = b->prev_bb;
814       if (next == c)
815         next = next->prev_bb;
816
817       /* Otherwise, we're going to try to move C after B.  If C does
818          not have an outgoing fallthru, then it can be moved
819          immediately after B without introducing or modifying jumps.  */
820       if (! c_has_outgoing_fallthru)
821         {
822           merge_blocks_move_successor_nojumps (b, c);
823           return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
824         }
825
826       /* If B does not have an incoming fallthru, then it can be moved
827          immediately before C without introducing or modifying jumps.
828          C cannot be the first block, so we do not have to worry about
829          accessing a non-existent block.  */
830
831       if (b_has_incoming_fallthru)
832         {
833           basic_block bb;
834
835           if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
836             return NULL;
837           bb = force_nonfallthru (b_fallthru_edge);
838           if (bb)
839             notice_new_block (bb);
840         }
841
842       merge_blocks_move_predecessor_nojumps (b, c);
843       return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
844     }
845
846   return NULL;
847 }
848 \f
849
850 /* Removes the memory attributes of MEM expression
851    if they are not equal.  */
852
853 void
854 merge_memattrs (rtx x, rtx y)
855 {
856   int i;
857   int j;
858   enum rtx_code code;
859   const char *fmt;
860
861   if (x == y)
862     return;
863   if (x == 0 || y == 0)
864     return;
865
866   code = GET_CODE (x);
867
868   if (code != GET_CODE (y))
869     return;
870
871   if (GET_MODE (x) != GET_MODE (y))
872     return;
873
874   if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
875     {
876       if (! MEM_ATTRS (x))
877         MEM_ATTRS (y) = 0;
878       else if (! MEM_ATTRS (y))
879         MEM_ATTRS (x) = 0;
880       else
881         {
882           rtx mem_size;
883
884           if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
885             {
886               set_mem_alias_set (x, 0);
887               set_mem_alias_set (y, 0);
888             }
889
890           if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
891             {
892               set_mem_expr (x, 0);
893               set_mem_expr (y, 0);
894               set_mem_offset (x, 0);
895               set_mem_offset (y, 0);
896             }
897           else if (MEM_OFFSET (x) != MEM_OFFSET (y))
898             {
899               set_mem_offset (x, 0);
900               set_mem_offset (y, 0);
901             }
902
903           if (!MEM_SIZE (x))
904             mem_size = NULL_RTX;
905           else if (!MEM_SIZE (y))
906             mem_size = NULL_RTX;
907           else
908             mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
909                                      INTVAL (MEM_SIZE (y))));
910           set_mem_size (x, mem_size);
911           set_mem_size (y, mem_size);
912
913           set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
914           set_mem_align (y, MEM_ALIGN (x));
915         }
916     }
917
918   fmt = GET_RTX_FORMAT (code);
919   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
920     {
921       switch (fmt[i])
922         {
923         case 'E':
924           /* Two vectors must have the same length.  */
925           if (XVECLEN (x, i) != XVECLEN (y, i))
926             return;
927
928           for (j = 0; j < XVECLEN (x, i); j++)
929             merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
930
931           break;
932
933         case 'e':
934           merge_memattrs (XEXP (x, i), XEXP (y, i));
935         }
936     }
937   return;
938 }
939
940
941 /* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
942
943 static bool
944 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
945 {
946   rtx p1, p2;
947
948   /* Verify that I1 and I2 are equivalent.  */
949   if (GET_CODE (i1) != GET_CODE (i2))
950     return false;
951
952   p1 = PATTERN (i1);
953   p2 = PATTERN (i2);
954
955   if (GET_CODE (p1) != GET_CODE (p2))
956     return false;
957
958   /* If this is a CALL_INSN, compare register usage information.
959      If we don't check this on stack register machines, the two
960      CALL_INSNs might be merged leaving reg-stack.c with mismatching
961      numbers of stack registers in the same basic block.
962      If we don't check this on machines with delay slots, a delay slot may
963      be filled that clobbers a parameter expected by the subroutine.
964
965      ??? We take the simple route for now and assume that if they're
966      equal, they were constructed identically.  */
967
968   if (CALL_P (i1)
969       && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
970                         CALL_INSN_FUNCTION_USAGE (i2))
971           || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
972     return false;
973
974 #ifdef STACK_REGS
975   /* If cross_jump_death_matters is not 0, the insn's mode
976      indicates whether or not the insn contains any stack-like
977      regs.  */
978
979   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
980     {
981       /* If register stack conversion has already been done, then
982          death notes must also be compared before it is certain that
983          the two instruction streams match.  */
984
985       rtx note;
986       HARD_REG_SET i1_regset, i2_regset;
987
988       CLEAR_HARD_REG_SET (i1_regset);
989       CLEAR_HARD_REG_SET (i2_regset);
990
991       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
992         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
993           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
994
995       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
996         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
997           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
998
999       GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
1000
1001       return false;
1002
1003     done:
1004       ;
1005     }
1006 #endif
1007
1008   if (reload_completed
1009       ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1010     return true;
1011
1012   /* Do not do EQUIV substitution after reload.  First, we're undoing the
1013      work of reload_cse.  Second, we may be undoing the work of the post-
1014      reload splitting pass.  */
1015   /* ??? Possibly add a new phase switch variable that can be used by
1016      targets to disallow the troublesome insns after splitting.  */
1017   if (!reload_completed)
1018     {
1019       /* The following code helps take care of G++ cleanups.  */
1020       rtx equiv1 = find_reg_equal_equiv_note (i1);
1021       rtx equiv2 = find_reg_equal_equiv_note (i2);
1022
1023       if (equiv1 && equiv2
1024           /* If the equivalences are not to a constant, they may
1025              reference pseudos that no longer exist, so we can't
1026              use them.  */
1027           && (! reload_completed
1028               || (CONSTANT_P (XEXP (equiv1, 0))
1029                   && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
1030         {
1031           rtx s1 = single_set (i1);
1032           rtx s2 = single_set (i2);
1033           if (s1 != 0 && s2 != 0
1034               && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
1035             {
1036               validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
1037               validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
1038               if (! rtx_renumbered_equal_p (p1, p2))
1039                 cancel_changes (0);
1040               else if (apply_change_group ())
1041                 return true;
1042             }
1043         }
1044     }
1045
1046   return false;
1047 }
1048 \f
1049 /* Look through the insns at the end of BB1 and BB2 and find the longest
1050    sequence that are equivalent.  Store the first insns for that sequence
1051    in *F1 and *F2 and return the sequence length.
1052
1053    To simplify callers of this function, if the blocks match exactly,
1054    store the head of the blocks in *F1 and *F2.  */
1055
1056 static int
1057 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
1058                       basic_block bb2, rtx *f1, rtx *f2)
1059 {
1060   rtx i1, i2, last1, last2, afterlast1, afterlast2;
1061   int ninsns = 0;
1062
1063   /* Skip simple jumps at the end of the blocks.  Complex jumps still
1064      need to be compared for equivalence, which we'll do below.  */
1065
1066   i1 = BB_END (bb1);
1067   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1068   if (onlyjump_p (i1)
1069       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1070     {
1071       last1 = i1;
1072       i1 = PREV_INSN (i1);
1073     }
1074
1075   i2 = BB_END (bb2);
1076   if (onlyjump_p (i2)
1077       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1078     {
1079       last2 = i2;
1080       /* Count everything except for unconditional jump as insn.  */
1081       if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1082         ninsns++;
1083       i2 = PREV_INSN (i2);
1084     }
1085
1086   while (true)
1087     {
1088       /* Ignore notes.  */
1089       while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
1090         i1 = PREV_INSN (i1);
1091
1092       while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
1093         i2 = PREV_INSN (i2);
1094
1095       if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1096         break;
1097
1098       if (!old_insns_match_p (mode, i1, i2))
1099         break;
1100
1101       merge_memattrs (i1, i2);
1102
1103       /* Don't begin a cross-jump with a NOTE insn.  */
1104       if (INSN_P (i1))
1105         {
1106           /* If the merged insns have different REG_EQUAL notes, then
1107              remove them.  */
1108           rtx equiv1 = find_reg_equal_equiv_note (i1);
1109           rtx equiv2 = find_reg_equal_equiv_note (i2);
1110
1111           if (equiv1 && !equiv2)
1112             remove_note (i1, equiv1);
1113           else if (!equiv1 && equiv2)
1114             remove_note (i2, equiv2);
1115           else if (equiv1 && equiv2
1116                    && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1117             {
1118               remove_note (i1, equiv1);
1119               remove_note (i2, equiv2);
1120             }
1121
1122           afterlast1 = last1, afterlast2 = last2;
1123           last1 = i1, last2 = i2;
1124           ninsns++;
1125         }
1126
1127       i1 = PREV_INSN (i1);
1128       i2 = PREV_INSN (i2);
1129     }
1130
1131 #ifdef HAVE_cc0
1132   /* Don't allow the insn after a compare to be shared by
1133      cross-jumping unless the compare is also shared.  */
1134   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1135     last1 = afterlast1, last2 = afterlast2, ninsns--;
1136 #endif
1137
1138   /* Include preceding notes and labels in the cross-jump.  One,
1139      this may bring us to the head of the blocks as requested above.
1140      Two, it keeps line number notes as matched as may be.  */
1141   if (ninsns)
1142     {
1143       while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
1144         last1 = PREV_INSN (last1);
1145
1146       if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1147         last1 = PREV_INSN (last1);
1148
1149       while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
1150         last2 = PREV_INSN (last2);
1151
1152       if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1153         last2 = PREV_INSN (last2);
1154
1155       *f1 = last1;
1156       *f2 = last2;
1157     }
1158
1159   return ninsns;
1160 }
1161
1162 /* Return true iff the condbranches at the end of BB1 and BB2 match.  */
1163 bool
1164 condjump_equiv_p (struct equiv_info *info, bool call_init)
1165 {
1166   basic_block bb1 = info->x_block;
1167   basic_block bb2 = info->y_block;
1168   edge b1 = BRANCH_EDGE (bb1);
1169   edge b2 = BRANCH_EDGE (bb2);
1170   edge f1 = FALLTHRU_EDGE (bb1);
1171   edge f2 = FALLTHRU_EDGE (bb2);
1172   bool reverse, match;
1173   rtx set1, set2, cond1, cond2;
1174   rtx src1, src2;
1175   enum rtx_code code1, code2;
1176
1177   /* Get around possible forwarders on fallthru edges.  Other cases
1178      should be optimized out already.  */
1179   if (FORWARDER_BLOCK_P (f1->dest))
1180     f1 = single_succ_edge (f1->dest);
1181
1182   if (FORWARDER_BLOCK_P (f2->dest))
1183     f2 = single_succ_edge (f2->dest);
1184
1185   /* To simplify use of this function, return false if there are
1186      unneeded forwarder blocks.  These will get eliminated later
1187      during cleanup_cfg.  */
1188   if (FORWARDER_BLOCK_P (f1->dest)
1189       || FORWARDER_BLOCK_P (f2->dest)
1190       || FORWARDER_BLOCK_P (b1->dest)
1191       || FORWARDER_BLOCK_P (b2->dest))
1192     return false;
1193
1194   if (f1->dest == f2->dest && b1->dest == b2->dest)
1195     reverse = false;
1196   else if (f1->dest == b2->dest && b1->dest == f2->dest)
1197     reverse = true;
1198   else
1199     return false;
1200
1201   set1 = pc_set (BB_END (bb1));
1202   set2 = pc_set (BB_END (bb2));
1203   if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1204       != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1205     reverse = !reverse;
1206
1207   src1 = SET_SRC (set1);
1208   src2 = SET_SRC (set2);
1209   cond1 = XEXP (src1, 0);
1210   cond2 = XEXP (src2, 0);
1211   code1 = GET_CODE (cond1);
1212   if (reverse)
1213     code2 = reversed_comparison_code (cond2, BB_END (bb2));
1214   else
1215     code2 = GET_CODE (cond2);
1216
1217   if (code2 == UNKNOWN)
1218     return false;
1219
1220   if (call_init && !struct_equiv_init (STRUCT_EQUIV_START | info->mode, info))
1221     gcc_unreachable ();
1222   /* Make the sources of the pc sets unreadable so that when we call
1223      insns_match_p it won't process them.
1224      The death_notes_match_p from insns_match_p won't see the local registers
1225      used for the pc set, but that could only cause missed optimizations when
1226      there are actually condjumps that use stack registers.  */
1227   SET_SRC (set1) = pc_rtx;
1228   SET_SRC (set2) = pc_rtx;
1229   /* Verify codes and operands match.  */
1230   if (code1 == code2)
1231     {
1232       match = (insns_match_p (BB_END (bb1), BB_END (bb2), info)
1233                && rtx_equiv_p (&XEXP (cond1, 0), XEXP (cond2, 0), 1, info)
1234                && rtx_equiv_p (&XEXP (cond1, 1), XEXP (cond2, 1), 1, info));
1235
1236     }
1237   else if (code1 == swap_condition (code2))
1238     {
1239       match = (insns_match_p (BB_END (bb1), BB_END (bb2), info)
1240                && rtx_equiv_p (&XEXP (cond1, 1), XEXP (cond2, 0), 1, info)
1241                && rtx_equiv_p (&XEXP (cond1, 0), XEXP (cond2, 1), 1, info));
1242
1243     }
1244   else
1245     match = false;
1246   SET_SRC (set1) = src1;
1247   SET_SRC (set2) = src2;
1248   match &= verify_changes (0);
1249
1250   /* If we return true, we will join the blocks.  Which means that
1251      we will only have one branch prediction bit to work with.  Thus
1252      we require the existing branches to have probabilities that are
1253      roughly similar.  */
1254   if (match
1255       && !optimize_size
1256       && maybe_hot_bb_p (bb1)
1257       && maybe_hot_bb_p (bb2))
1258     {
1259       int prob2;
1260
1261       if (b1->dest == b2->dest)
1262         prob2 = b2->probability;
1263       else
1264         /* Do not use f2 probability as f2 may be forwarded.  */
1265         prob2 = REG_BR_PROB_BASE - b2->probability;
1266
1267       /* Fail if the difference in probabilities is greater than 50%.
1268          This rules out two well-predicted branches with opposite
1269          outcomes.  */
1270       if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1271         {
1272           if (dump_file)
1273             fprintf (dump_file,
1274                      "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1275                      bb1->index, bb2->index, b1->probability, prob2);
1276
1277           match = false;
1278         }
1279     }
1280
1281   if (dump_file && match)
1282     fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1283              bb1->index, bb2->index);
1284
1285   if (!match)
1286     cancel_changes (0);
1287   return match;
1288 }
1289
1290 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1291    the branch instruction.  This means that if we commonize the control
1292    flow before end of the basic block, the semantic remains unchanged.
1293
1294    We may assume that there exists one edge with a common destination.  */
1295
1296 static bool
1297 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1298 {
1299   int nehedges1 = 0, nehedges2 = 0;
1300   edge fallthru1 = 0, fallthru2 = 0;
1301   edge e1, e2;
1302   edge_iterator ei;
1303
1304   /* If BB1 has only one successor, we may be looking at either an
1305      unconditional jump, or a fake edge to exit.  */
1306   if (single_succ_p (bb1)
1307       && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1308       && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1309     return (single_succ_p (bb2)
1310             && (single_succ_edge (bb2)->flags
1311                 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1312             && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1313
1314   /* Match conditional jumps - this may get tricky when fallthru and branch
1315      edges are crossed.  */
1316   if (EDGE_COUNT (bb1->succs) == 2
1317       && any_condjump_p (BB_END (bb1))
1318       && onlyjump_p (BB_END (bb1)))
1319     {
1320       edge b1, f1, b2, f2;
1321       bool reverse, match;
1322       rtx set1, set2, cond1, cond2;
1323       enum rtx_code code1, code2;
1324
1325       if (EDGE_COUNT (bb2->succs) != 2
1326           || !any_condjump_p (BB_END (bb2))
1327           || !onlyjump_p (BB_END (bb2)))
1328         return false;
1329
1330       b1 = BRANCH_EDGE (bb1);
1331       b2 = BRANCH_EDGE (bb2);
1332       f1 = FALLTHRU_EDGE (bb1);
1333       f2 = FALLTHRU_EDGE (bb2);
1334
1335       /* Get around possible forwarders on fallthru edges.  Other cases
1336          should be optimized out already.  */
1337       if (FORWARDER_BLOCK_P (f1->dest))
1338         f1 = single_succ_edge (f1->dest);
1339
1340       if (FORWARDER_BLOCK_P (f2->dest))
1341         f2 = single_succ_edge (f2->dest);
1342
1343       /* To simplify use of this function, return false if there are
1344          unneeded forwarder blocks.  These will get eliminated later
1345          during cleanup_cfg.  */
1346       if (FORWARDER_BLOCK_P (f1->dest)
1347           || FORWARDER_BLOCK_P (f2->dest)
1348           || FORWARDER_BLOCK_P (b1->dest)
1349           || FORWARDER_BLOCK_P (b2->dest))
1350         return false;
1351
1352       if (f1->dest == f2->dest && b1->dest == b2->dest)
1353         reverse = false;
1354       else if (f1->dest == b2->dest && b1->dest == f2->dest)
1355         reverse = true;
1356       else
1357         return false;
1358
1359       set1 = pc_set (BB_END (bb1));
1360       set2 = pc_set (BB_END (bb2));
1361       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1362           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1363         reverse = !reverse;
1364
1365       cond1 = XEXP (SET_SRC (set1), 0);
1366       cond2 = XEXP (SET_SRC (set2), 0);
1367       code1 = GET_CODE (cond1);
1368       if (reverse)
1369         code2 = reversed_comparison_code (cond2, BB_END (bb2));
1370       else
1371         code2 = GET_CODE (cond2);
1372
1373       if (code2 == UNKNOWN)
1374         return false;
1375
1376       /* Verify codes and operands match.  */
1377       match = ((code1 == code2
1378                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1379                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1380                || (code1 == swap_condition (code2)
1381                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
1382                                               XEXP (cond2, 0))
1383                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
1384                                               XEXP (cond2, 1))));
1385
1386       /* If we return true, we will join the blocks.  Which means that
1387          we will only have one branch prediction bit to work with.  Thus
1388          we require the existing branches to have probabilities that are
1389          roughly similar.  */
1390       if (match
1391           && !optimize_size
1392           && maybe_hot_bb_p (bb1)
1393           && maybe_hot_bb_p (bb2))
1394         {
1395           int prob2;
1396
1397           if (b1->dest == b2->dest)
1398             prob2 = b2->probability;
1399           else
1400             /* Do not use f2 probability as f2 may be forwarded.  */
1401             prob2 = REG_BR_PROB_BASE - b2->probability;
1402
1403           /* Fail if the difference in probabilities is greater than 50%.
1404              This rules out two well-predicted branches with opposite
1405              outcomes.  */
1406           if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1407             {
1408               if (dump_file)
1409                 fprintf (dump_file,
1410                          "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1411                          bb1->index, bb2->index, b1->probability, prob2);
1412
1413               return false;
1414             }
1415         }
1416
1417       if (dump_file && match)
1418         fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1419                  bb1->index, bb2->index);
1420
1421       return match;
1422     }
1423
1424   /* Generic case - we are seeing a computed jump, table jump or trapping
1425      instruction.  */
1426
1427   /* Check whether there are tablejumps in the end of BB1 and BB2.
1428      Return true if they are identical.  */
1429     {
1430       rtx label1, label2;
1431       rtx table1, table2;
1432
1433       if (tablejump_p (BB_END (bb1), &label1, &table1)
1434           && tablejump_p (BB_END (bb2), &label2, &table2)
1435           && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1436         {
1437           /* The labels should never be the same rtx.  If they really are same
1438              the jump tables are same too. So disable crossjumping of blocks BB1
1439              and BB2 because when deleting the common insns in the end of BB1
1440              by delete_basic_block () the jump table would be deleted too.  */
1441           /* If LABEL2 is referenced in BB1->END do not do anything
1442              because we would loose information when replacing
1443              LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END.  */
1444           if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1445             {
1446               /* Set IDENTICAL to true when the tables are identical.  */
1447               bool identical = false;
1448               rtx p1, p2;
1449
1450               p1 = PATTERN (table1);
1451               p2 = PATTERN (table2);
1452               if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1453                 {
1454                   identical = true;
1455                 }
1456               else if (GET_CODE (p1) == ADDR_DIFF_VEC
1457                        && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1458                        && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1459                        && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1460                 {
1461                   int i;
1462
1463                   identical = true;
1464                   for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1465                     if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1466                       identical = false;
1467                 }
1468
1469               if (identical)
1470                 {
1471                   replace_label_data rr;
1472                   bool match;
1473
1474                   /* Temporarily replace references to LABEL1 with LABEL2
1475                      in BB1->END so that we could compare the instructions.  */
1476                   rr.r1 = label1;
1477                   rr.r2 = label2;
1478                   rr.update_label_nuses = false;
1479                   for_each_rtx (&BB_END (bb1), replace_label, &rr);
1480
1481                   match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
1482                   if (dump_file && match)
1483                     fprintf (dump_file,
1484                              "Tablejumps in bb %i and %i match.\n",
1485                              bb1->index, bb2->index);
1486
1487                   /* Set the original label in BB1->END because when deleting
1488                      a block whose end is a tablejump, the tablejump referenced
1489                      from the instruction is deleted too.  */
1490                   rr.r1 = label2;
1491                   rr.r2 = label1;
1492                   for_each_rtx (&BB_END (bb1), replace_label, &rr);
1493
1494                   return match;
1495                 }
1496             }
1497           return false;
1498         }
1499     }
1500
1501   /* First ensure that the instructions match.  There may be many outgoing
1502      edges so this test is generally cheaper.  */
1503   if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
1504     return false;
1505
1506   /* Search the outgoing edges, ensure that the counts do match, find possible
1507      fallthru and exception handling edges since these needs more
1508      validation.  */
1509   if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
1510     return false;
1511
1512   FOR_EACH_EDGE (e1, ei, bb1->succs)
1513     {
1514       e2 = EDGE_SUCC (bb2, ei.index);
1515
1516       if (e1->flags & EDGE_EH)
1517         nehedges1++;
1518
1519       if (e2->flags & EDGE_EH)
1520         nehedges2++;
1521
1522       if (e1->flags & EDGE_FALLTHRU)
1523         fallthru1 = e1;
1524       if (e2->flags & EDGE_FALLTHRU)
1525         fallthru2 = e2;
1526     }
1527
1528   /* If number of edges of various types does not match, fail.  */
1529   if (nehedges1 != nehedges2
1530       || (fallthru1 != 0) != (fallthru2 != 0))
1531     return false;
1532
1533   /* fallthru edges must be forwarded to the same destination.  */
1534   if (fallthru1)
1535     {
1536       basic_block d1 = (forwarder_block_p (fallthru1->dest)
1537                         ? single_succ (fallthru1->dest): fallthru1->dest);
1538       basic_block d2 = (forwarder_block_p (fallthru2->dest)
1539                         ? single_succ (fallthru2->dest): fallthru2->dest);
1540
1541       if (d1 != d2)
1542         return false;
1543     }
1544
1545   /* Ensure the same EH region.  */
1546   {
1547     rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1548     rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1549
1550     if (!n1 && n2)
1551       return false;
1552
1553     if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1554       return false;
1555   }
1556
1557   /* The same checks as in try_crossjump_to_edge. It is required for RTL
1558      version of sequence abstraction.  */
1559   FOR_EACH_EDGE (e1, ei, bb2->succs)
1560     {
1561       edge e2;
1562       edge_iterator ei;
1563       basic_block d1 = e1->dest;
1564
1565       if (FORWARDER_BLOCK_P (d1))
1566         d1 = EDGE_SUCC (d1, 0)->dest;
1567
1568       FOR_EACH_EDGE (e2, ei, bb1->succs)
1569         {
1570           basic_block d2 = e2->dest;
1571           if (FORWARDER_BLOCK_P (d2))
1572             d2 = EDGE_SUCC (d2, 0)->dest;
1573           if (d1 == d2)
1574             break;
1575         }
1576
1577       if (!e2)
1578         return false;
1579     }
1580
1581   return true;
1582 }
1583
1584 /* Returns true if BB basic block has a preserve label.  */
1585
1586 static bool
1587 block_has_preserve_label (basic_block bb)
1588 {
1589   return (bb
1590           && block_label (bb)
1591           && LABEL_PRESERVE_P (block_label (bb)));
1592 }
1593
1594 /* E1 and E2 are edges with the same destination block.  Search their
1595    predecessors for common code.  If found, redirect control flow from
1596    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC.  */
1597
1598 static bool
1599 try_crossjump_to_edge (int mode, edge e1, edge e2)
1600 {
1601   int nmatch;
1602   basic_block src1 = e1->src, src2 = e2->src;
1603   basic_block redirect_to, redirect_from, to_remove;
1604   rtx newpos1, newpos2;
1605   edge s;
1606   edge_iterator ei;
1607
1608   newpos1 = newpos2 = NULL_RTX;
1609
1610   /* If we have partitioned hot/cold basic blocks, it is a bad idea
1611      to try this optimization.
1612
1613      Basic block partitioning may result in some jumps that appear to
1614      be optimizable (or blocks that appear to be mergeable), but which really
1615      must be left untouched (they are required to make it safely across
1616      partition boundaries).  See the comments at the top of
1617      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
1618
1619   if (flag_reorder_blocks_and_partition && no_new_pseudos)
1620     return false;
1621
1622   /* Search backward through forwarder blocks.  We don't need to worry
1623      about multiple entry or chained forwarders, as they will be optimized
1624      away.  We do this to look past the unconditional jump following a
1625      conditional jump that is required due to the current CFG shape.  */
1626   if (single_pred_p (src1)
1627       && FORWARDER_BLOCK_P (src1))
1628     e1 = single_pred_edge (src1), src1 = e1->src;
1629
1630   if (single_pred_p (src2)
1631       && FORWARDER_BLOCK_P (src2))
1632     e2 = single_pred_edge (src2), src2 = e2->src;
1633
1634   /* Nothing to do if we reach ENTRY, or a common source block.  */
1635   if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1636     return false;
1637   if (src1 == src2)
1638     return false;
1639
1640   /* Seeing more than 1 forwarder blocks would confuse us later...  */
1641   if (FORWARDER_BLOCK_P (e1->dest)
1642       && FORWARDER_BLOCK_P (single_succ (e1->dest)))
1643     return false;
1644
1645   if (FORWARDER_BLOCK_P (e2->dest)
1646       && FORWARDER_BLOCK_P (single_succ (e2->dest)))
1647     return false;
1648
1649   /* Likewise with dead code (possibly newly created by the other optimizations
1650      of cfg_cleanup).  */
1651   if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1652     return false;
1653
1654   /* Look for the common insn sequence, part the first ...  */
1655   if (!outgoing_edges_match (mode, src1, src2))
1656     return false;
1657
1658   /* ... and part the second.  */
1659   nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1660
1661   /* Don't proceed with the crossjump unless we found a sufficient number
1662      of matching instructions or the 'from' block was totally matched
1663      (such that its predecessors will hopefully be redirected and the
1664      block removed).  */
1665   if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
1666       && (newpos1 != BB_HEAD (src1)))
1667     return false;
1668
1669   /* Avoid deleting preserve label when redirecting ABNORMAL edges.  */
1670   if (block_has_preserve_label (e1->dest)
1671       && (e1->flags & EDGE_ABNORMAL))
1672     return false;
1673
1674   /* Here we know that the insns in the end of SRC1 which are common with SRC2
1675      will be deleted.
1676      If we have tablejumps in the end of SRC1 and SRC2
1677      they have been already compared for equivalence in outgoing_edges_match ()
1678      so replace the references to TABLE1 by references to TABLE2.  */
1679     {
1680       rtx label1, label2;
1681       rtx table1, table2;
1682
1683       if (tablejump_p (BB_END (src1), &label1, &table1)
1684           && tablejump_p (BB_END (src2), &label2, &table2)
1685           && label1 != label2)
1686         {
1687           replace_label_data rr;
1688           rtx insn;
1689
1690           /* Replace references to LABEL1 with LABEL2.  */
1691           rr.r1 = label1;
1692           rr.r2 = label2;
1693           rr.update_label_nuses = true;
1694           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1695             {
1696               /* Do not replace the label in SRC1->END because when deleting
1697                  a block whose end is a tablejump, the tablejump referenced
1698                  from the instruction is deleted too.  */
1699               if (insn != BB_END (src1))
1700                 for_each_rtx (&insn, replace_label, &rr);
1701             }
1702         }
1703     }
1704
1705   /* Avoid splitting if possible.  We must always split when SRC2 has
1706      EH predecessor edges, or we may end up with basic blocks with both
1707      normal and EH predecessor edges.  */
1708   if (newpos2 == BB_HEAD (src2)
1709       && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
1710     redirect_to = src2;
1711   else
1712     {
1713       if (newpos2 == BB_HEAD (src2))
1714         {
1715           /* Skip possible basic block header.  */
1716           if (LABEL_P (newpos2))
1717             newpos2 = NEXT_INSN (newpos2);
1718           if (NOTE_P (newpos2))
1719             newpos2 = NEXT_INSN (newpos2);
1720         }
1721
1722       if (dump_file)
1723         fprintf (dump_file, "Splitting bb %i before %i insns\n",
1724                  src2->index, nmatch);
1725       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1726     }
1727
1728   if (dump_file)
1729     fprintf (dump_file,
1730              "Cross jumping from bb %i to bb %i; %i common insns\n",
1731              src1->index, src2->index, nmatch);
1732
1733   redirect_to->count += src1->count;
1734   redirect_to->frequency += src1->frequency;
1735   /* We may have some registers visible through the block.  */
1736   redirect_to->flags |= BB_DIRTY;
1737
1738   /* Recompute the frequencies and counts of outgoing edges.  */
1739   FOR_EACH_EDGE (s, ei, redirect_to->succs)
1740     {
1741       edge s2;
1742       edge_iterator ei;
1743       basic_block d = s->dest;
1744
1745       if (FORWARDER_BLOCK_P (d))
1746         d = single_succ (d);
1747
1748       FOR_EACH_EDGE (s2, ei, src1->succs)
1749         {
1750           basic_block d2 = s2->dest;
1751           if (FORWARDER_BLOCK_P (d2))
1752             d2 = single_succ (d2);
1753           if (d == d2)
1754             break;
1755         }
1756
1757       s->count += s2->count;
1758
1759       /* Take care to update possible forwarder blocks.  We verified
1760          that there is no more than one in the chain, so we can't run
1761          into infinite loop.  */
1762       if (FORWARDER_BLOCK_P (s->dest))
1763         {
1764           single_succ_edge (s->dest)->count += s2->count;
1765           s->dest->count += s2->count;
1766           s->dest->frequency += EDGE_FREQUENCY (s);
1767         }
1768
1769       if (FORWARDER_BLOCK_P (s2->dest))
1770         {
1771           single_succ_edge (s2->dest)->count -= s2->count;
1772           if (single_succ_edge (s2->dest)->count < 0)
1773             single_succ_edge (s2->dest)->count = 0;
1774           s2->dest->count -= s2->count;
1775           s2->dest->frequency -= EDGE_FREQUENCY (s);
1776           if (s2->dest->frequency < 0)
1777             s2->dest->frequency = 0;
1778           if (s2->dest->count < 0)
1779             s2->dest->count = 0;
1780         }
1781
1782       if (!redirect_to->frequency && !src1->frequency)
1783         s->probability = (s->probability + s2->probability) / 2;
1784       else
1785         s->probability
1786           = ((s->probability * redirect_to->frequency +
1787               s2->probability * src1->frequency)
1788              / (redirect_to->frequency + src1->frequency));
1789     }
1790
1791   update_br_prob_note (redirect_to);
1792
1793   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
1794
1795   /* Skip possible basic block header.  */
1796   if (LABEL_P (newpos1))
1797     newpos1 = NEXT_INSN (newpos1);
1798
1799   if (NOTE_P (newpos1))
1800     newpos1 = NEXT_INSN (newpos1);
1801
1802   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1803   to_remove = single_succ (redirect_from);
1804
1805   redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
1806   delete_basic_block (to_remove);
1807
1808   update_forwarder_flag (redirect_from);
1809   if (redirect_to != src2)
1810     update_forwarder_flag (src2);
1811
1812   return true;
1813 }
1814
1815 /* Search the predecessors of BB for common insn sequences.  When found,
1816    share code between them by redirecting control flow.  Return true if
1817    any changes made.  */
1818
1819 static bool
1820 try_crossjump_bb (int mode, basic_block bb)
1821 {
1822   edge e, e2, fallthru;
1823   bool changed;
1824   unsigned max, ix, ix2;
1825   basic_block ev, ev2;
1826   edge_iterator ei;
1827
1828   /* Nothing to do if there is not at least two incoming edges.  */
1829   if (EDGE_COUNT (bb->preds) < 2)
1830     return false;
1831
1832   /* Don't crossjump if this block ends in a computed jump,
1833      unless we are optimizing for size.  */
1834   if (!optimize_size
1835       && bb != EXIT_BLOCK_PTR
1836       && computed_jump_p (BB_END (bb)))
1837     return false;
1838
1839   /* If we are partitioning hot/cold basic blocks, we don't want to
1840      mess up unconditional or indirect jumps that cross between hot
1841      and cold sections.
1842
1843      Basic block partitioning may result in some jumps that appear to
1844      be optimizable (or blocks that appear to be mergeable), but which really
1845      must be left untouched (they are required to make it safely across
1846      partition boundaries).  See the comments at the top of
1847      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
1848
1849   if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
1850                                         BB_PARTITION (EDGE_PRED (bb, 1)->src)
1851       || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
1852     return false;
1853
1854   /* It is always cheapest to redirect a block that ends in a branch to
1855      a block that falls through into BB, as that adds no branches to the
1856      program.  We'll try that combination first.  */
1857   fallthru = NULL;
1858   max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1859
1860   if (EDGE_COUNT (bb->preds) > max)
1861     return false;
1862
1863   FOR_EACH_EDGE (e, ei, bb->preds)
1864     {
1865       if (e->flags & EDGE_FALLTHRU)
1866         fallthru = e;
1867     }
1868
1869   changed = false;
1870   for (ix = 0, ev = bb; ix < EDGE_COUNT (ev->preds); )
1871     {
1872       e = EDGE_PRED (ev, ix);
1873       ix++;
1874
1875       /* As noted above, first try with the fallthru predecessor.  */
1876       if (fallthru)
1877         {
1878           /* Don't combine the fallthru edge into anything else.
1879              If there is a match, we'll do it the other way around.  */
1880           if (e == fallthru)
1881             continue;
1882           /* If nothing changed since the last attempt, there is nothing
1883              we can do.  */
1884           if (!first_pass
1885               && (!(e->src->flags & BB_DIRTY)
1886                   && !(fallthru->src->flags & BB_DIRTY)))
1887             continue;
1888
1889           if (try_crossjump_to_edge (mode, e, fallthru))
1890             {
1891               changed = true;
1892               ix = 0;
1893               ev = bb;
1894               continue;
1895             }
1896         }
1897
1898       /* Non-obvious work limiting check: Recognize that we're going
1899          to call try_crossjump_bb on every basic block.  So if we have
1900          two blocks with lots of outgoing edges (a switch) and they
1901          share lots of common destinations, then we would do the
1902          cross-jump check once for each common destination.
1903
1904          Now, if the blocks actually are cross-jump candidates, then
1905          all of their destinations will be shared.  Which means that
1906          we only need check them for cross-jump candidacy once.  We
1907          can eliminate redundant checks of crossjump(A,B) by arbitrarily
1908          choosing to do the check from the block for which the edge
1909          in question is the first successor of A.  */
1910       if (EDGE_SUCC (e->src, 0) != e)
1911         continue;
1912
1913       for (ix2 = 0, ev2 = bb; ix2 < EDGE_COUNT (ev2->preds); )
1914         {
1915           e2 = EDGE_PRED (ev2, ix2);
1916           ix2++;
1917
1918           if (e2 == e)
1919             continue;
1920
1921           /* We've already checked the fallthru edge above.  */
1922           if (e2 == fallthru)
1923             continue;
1924
1925           /* The "first successor" check above only prevents multiple
1926              checks of crossjump(A,B).  In order to prevent redundant
1927              checks of crossjump(B,A), require that A be the block
1928              with the lowest index.  */
1929           if (e->src->index > e2->src->index)
1930             continue;
1931
1932           /* If nothing changed since the last attempt, there is nothing
1933              we can do.  */
1934           if (!first_pass
1935               && (!(e->src->flags & BB_DIRTY)
1936                   && !(e2->src->flags & BB_DIRTY)))
1937             continue;
1938
1939           if (try_crossjump_to_edge (mode, e, e2))
1940             {
1941               changed = true;
1942               ev2 = bb;
1943               ix = 0;
1944               break;
1945             }
1946         }
1947     }
1948
1949   return changed;
1950 }
1951
1952 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1953    instructions etc.  Return nonzero if changes were made.  */
1954
1955 static bool
1956 try_optimize_cfg (int mode)
1957 {
1958   bool changed_overall = false;
1959   bool changed;
1960   int iterations = 0;
1961   basic_block bb, b, next;
1962
1963   if (mode & CLEANUP_CROSSJUMP)
1964     add_noreturn_fake_exit_edges ();
1965
1966   if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
1967     clear_bb_flags ();
1968
1969   FOR_EACH_BB (bb)
1970     update_forwarder_flag (bb);
1971
1972   if (! targetm.cannot_modify_jumps_p ())
1973     {
1974       first_pass = true;
1975       /* Attempt to merge blocks as made possible by edge removal.  If
1976          a block has only one successor, and the successor has only
1977          one predecessor, they may be combined.  */
1978       do
1979         {
1980           changed = false;
1981           iterations++;
1982
1983           if (dump_file)
1984             fprintf (dump_file,
1985                      "\n\ntry_optimize_cfg iteration %i\n\n",
1986                      iterations);
1987
1988           for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1989             {
1990               basic_block c;
1991               edge s;
1992               bool changed_here = false;
1993
1994               /* Delete trivially dead basic blocks.  */
1995               if (EDGE_COUNT (b->preds) == 0)
1996                 {
1997                   c = b->prev_bb;
1998                   if (dump_file)
1999                     fprintf (dump_file, "Deleting block %i.\n",
2000                              b->index);
2001
2002                   delete_basic_block (b);
2003                   if (!(mode & CLEANUP_CFGLAYOUT))
2004                     changed = true;
2005                   /* Avoid trying to remove ENTRY_BLOCK_PTR.  */
2006                   b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
2007                   continue;
2008                 }
2009
2010               /* Remove code labels no longer used.  */
2011               if (single_pred_p (b)
2012                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2013                   && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
2014                   && LABEL_P (BB_HEAD (b))
2015                   /* If the previous block ends with a branch to this
2016                      block, we can't delete the label.  Normally this
2017                      is a condjump that is yet to be simplified, but
2018                      if CASE_DROPS_THRU, this can be a tablejump with
2019                      some element going to the same place as the
2020                      default (fallthru).  */
2021                   && (single_pred (b) == ENTRY_BLOCK_PTR
2022                       || !JUMP_P (BB_END (single_pred (b)))
2023                       || ! label_is_jump_target_p (BB_HEAD (b),
2024                                                    BB_END (single_pred (b)))))
2025                 {
2026                   rtx label = BB_HEAD (b);
2027
2028                   delete_insn_chain (label, label);
2029                   /* In the case label is undeletable, move it after the
2030                      BASIC_BLOCK note.  */
2031                   if (NOTE_LINE_NUMBER (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
2032                     {
2033                       rtx bb_note = NEXT_INSN (BB_HEAD (b));
2034
2035                       reorder_insns_nobb (label, label, bb_note);
2036                       BB_HEAD (b) = bb_note;
2037                       if (BB_END (b) == bb_note)
2038                         BB_END (b) = label;
2039                     }
2040                   if (dump_file)
2041                     fprintf (dump_file, "Deleted label in block %i.\n",
2042                              b->index);
2043                 }
2044
2045               /* If we fall through an empty block, we can remove it.  */
2046               if (!(mode & CLEANUP_CFGLAYOUT)
2047                   && single_pred_p (b)
2048                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
2049                   && !LABEL_P (BB_HEAD (b))
2050                   && FORWARDER_BLOCK_P (b)
2051                   /* Note that forwarder_block_p true ensures that
2052                      there is a successor for this block.  */
2053                   && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
2054                   && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
2055                 {
2056                   if (dump_file)
2057                     fprintf (dump_file,
2058                              "Deleting fallthru block %i.\n",
2059                              b->index);
2060
2061                   c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
2062                   redirect_edge_succ_nodup (single_pred_edge (b),
2063                                             single_succ (b));
2064                   delete_basic_block (b);
2065                   changed = true;
2066                   b = c;
2067                 }
2068
2069               if (single_succ_p (b)
2070                   && (s = single_succ_edge (b))
2071                   && !(s->flags & EDGE_COMPLEX)
2072                   && (c = s->dest) != EXIT_BLOCK_PTR
2073                   && single_pred_p (c)
2074                   && b != c)
2075                 {
2076                   /* When not in cfg_layout mode use code aware of reordering
2077                      INSN.  This code possibly creates new basic blocks so it
2078                      does not fit merge_blocks interface and is kept here in
2079                      hope that it will become useless once more of compiler
2080                      is transformed to use cfg_layout mode.  */
2081
2082                   if ((mode & CLEANUP_CFGLAYOUT)
2083                       && can_merge_blocks_p (b, c))
2084                     {
2085                       merge_blocks (b, c);
2086                       update_forwarder_flag (b);
2087                       changed_here = true;
2088                     }
2089                   else if (!(mode & CLEANUP_CFGLAYOUT)
2090                            /* If the jump insn has side effects,
2091                               we can't kill the edge.  */
2092                            && (!JUMP_P (BB_END (b))
2093                                || (reload_completed
2094                                    ? simplejump_p (BB_END (b))
2095                                    : (onlyjump_p (BB_END (b))
2096                                       && !tablejump_p (BB_END (b),
2097                                                        NULL, NULL))))
2098                            && (next = merge_blocks_move (s, b, c, mode)))
2099                       {
2100                         b = next;
2101                         changed_here = true;
2102                       }
2103                 }
2104
2105               /* Simplify branch over branch.  */
2106               if ((mode & CLEANUP_EXPENSIVE)
2107                    && !(mode & CLEANUP_CFGLAYOUT)
2108                    && try_simplify_condjump (b))
2109                 changed_here = true;
2110
2111               /* If B has a single outgoing edge, but uses a
2112                  non-trivial jump instruction without side-effects, we
2113                  can either delete the jump entirely, or replace it
2114                  with a simple unconditional jump.  */
2115               if (single_succ_p (b)
2116                   && single_succ (b) != EXIT_BLOCK_PTR
2117                   && onlyjump_p (BB_END (b))
2118                   && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
2119                   && try_redirect_by_replacing_jump (single_succ_edge (b),
2120                                                      single_succ (b),
2121                                                      (mode & CLEANUP_CFGLAYOUT) != 0))
2122                 {
2123                   update_forwarder_flag (b);
2124                   changed_here = true;
2125                 }
2126
2127               /* Simplify branch to branch.  */
2128               if (try_forward_edges (mode, b))
2129                 changed_here = true;
2130
2131               /* Look for shared code between blocks.  */
2132               if ((mode & CLEANUP_CROSSJUMP)
2133                   && try_crossjump_bb (mode, b))
2134                 changed_here = true;
2135
2136               /* Don't get confused by the index shift caused by
2137                  deleting blocks.  */
2138               if (!changed_here)
2139                 b = b->next_bb;
2140               else
2141                 changed = true;
2142             }
2143
2144           if ((mode & CLEANUP_CROSSJUMP)
2145               && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
2146             changed = true;
2147
2148 #ifdef ENABLE_CHECKING
2149           if (changed)
2150             verify_flow_info ();
2151 #endif
2152
2153           changed_overall |= changed;
2154           first_pass = false;
2155         }
2156       while (changed);
2157     }
2158
2159   if (mode & CLEANUP_CROSSJUMP)
2160     remove_fake_exit_edges ();
2161
2162   FOR_ALL_BB (b)
2163     b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
2164
2165   return changed_overall;
2166 }
2167 \f
2168 /* Delete all unreachable basic blocks.  */
2169
2170 bool
2171 delete_unreachable_blocks (void)
2172 {
2173   bool changed = false;
2174   basic_block b, next_bb;
2175
2176   find_unreachable_blocks ();
2177
2178   /* Delete all unreachable basic blocks.  */
2179
2180   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
2181     {
2182       next_bb = b->next_bb;
2183
2184       if (!(b->flags & BB_REACHABLE))
2185         {
2186           delete_basic_block (b);
2187           changed = true;
2188         }
2189     }
2190
2191   if (changed)
2192     tidy_fallthru_edges ();
2193   return changed;
2194 }
2195
2196 /* Merges sequential blocks if possible.  */
2197
2198 bool
2199 merge_seq_blocks (void)
2200 {
2201   basic_block bb;
2202   bool changed = false;
2203
2204   for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; )
2205     {
2206       if (single_succ_p (bb)
2207           && can_merge_blocks_p (bb, single_succ (bb)))
2208         {
2209           /* Merge the blocks and retry.  */
2210           merge_blocks (bb, single_succ (bb));
2211           changed = true;
2212           continue;
2213         }
2214
2215       bb = bb->next_bb;
2216     }
2217
2218   return changed;
2219 }
2220 \f
2221 /* Tidy the CFG by deleting unreachable code and whatnot.  */
2222
2223 bool
2224 cleanup_cfg (int mode)
2225 {
2226   bool changed = false;
2227
2228   /* Set the cfglayout mode flag here.  We could update all the callers
2229      but that is just inconvenient, especially given that we eventually
2230      want to have cfglayout mode as the default.  */
2231   if (current_ir_type () == IR_RTL_CFGLAYOUT)
2232     mode |= CLEANUP_CFGLAYOUT;
2233
2234   timevar_push (TV_CLEANUP_CFG);
2235   if (delete_unreachable_blocks ())
2236     {
2237       changed = true;
2238       /* We've possibly created trivially dead code.  Cleanup it right
2239          now to introduce more opportunities for try_optimize_cfg.  */
2240       if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_UPDATE_LIFE))
2241           && !reload_completed)
2242         delete_trivially_dead_insns (get_insns (), max_reg_num ());
2243     }
2244
2245   compact_blocks ();
2246
2247   while (try_optimize_cfg (mode))
2248     {
2249       delete_unreachable_blocks (), changed = true;
2250       if (mode & CLEANUP_UPDATE_LIFE)
2251         {
2252           /* Cleaning up CFG introduces more opportunities for dead code
2253              removal that in turn may introduce more opportunities for
2254              cleaning up the CFG.  */
2255           if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
2256                                                  PROP_DEATH_NOTES
2257                                                  | PROP_SCAN_DEAD_CODE
2258                                                  | PROP_KILL_DEAD_CODE
2259                                                  | ((mode & CLEANUP_LOG_LINKS)
2260                                                     ? PROP_LOG_LINKS : 0)))
2261             break;
2262         }
2263       else if (!(mode & CLEANUP_NO_INSN_DEL)
2264                && (mode & CLEANUP_EXPENSIVE)
2265                && !reload_completed)
2266         {
2267           if (!delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2268             break;
2269         }
2270       else
2271         break;
2272
2273       /* Don't call delete_dead_jumptables in cfglayout mode, because
2274          that function assumes that jump tables are in the insns stream.
2275          But we also don't _have_ to delete dead jumptables in cfglayout
2276          mode because we shouldn't even be looking at things that are
2277          not in a basic block.  Dead jumptables are cleaned up when
2278          going out of cfglayout mode.  */
2279       if (!(mode & CLEANUP_CFGLAYOUT))
2280         delete_dead_jumptables ();
2281     }
2282
2283   timevar_pop (TV_CLEANUP_CFG);
2284
2285   return changed;
2286 }
2287 \f
2288 static unsigned int
2289 rest_of_handle_jump (void)
2290 {
2291   delete_unreachable_blocks ();
2292
2293   if (cfun->tail_call_emit)
2294     fixup_tail_calls ();
2295   return 0;
2296 }
2297
2298 struct tree_opt_pass pass_jump =
2299 {
2300   "sibling",                            /* name */
2301   NULL,                                 /* gate */
2302   rest_of_handle_jump,                  /* execute */
2303   NULL,                                 /* sub */
2304   NULL,                                 /* next */
2305   0,                                    /* static_pass_number */
2306   TV_JUMP,                              /* tv_id */
2307   0,                                    /* properties_required */
2308   0,                                    /* properties_provided */
2309   0,                                    /* properties_destroyed */
2310   TODO_ggc_collect,                     /* todo_flags_start */
2311   TODO_dump_func |
2312   TODO_verify_flow,                     /* todo_flags_finish */
2313   'i'                                   /* letter */
2314 };
2315
2316
2317 static unsigned int
2318 rest_of_handle_jump2 (void)
2319 {
2320   delete_trivially_dead_insns (get_insns (), max_reg_num ());
2321   reg_scan (get_insns (), max_reg_num ());
2322   if (dump_file)
2323     dump_flow_info (dump_file, dump_flags);
2324   cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
2325                | (flag_thread_jumps ? CLEANUP_THREADING : 0));
2326   return 0;
2327 }
2328
2329
2330 struct tree_opt_pass pass_jump2 =
2331 {
2332   "jump",                               /* name */
2333   NULL,                                 /* gate */
2334   rest_of_handle_jump2,                 /* execute */
2335   NULL,                                 /* sub */
2336   NULL,                                 /* next */
2337   0,                                    /* static_pass_number */
2338   TV_JUMP,                              /* tv_id */
2339   0,                                    /* properties_required */
2340   0,                                    /* properties_provided */
2341   0,                                    /* properties_destroyed */
2342   TODO_ggc_collect,                     /* todo_flags_start */
2343   TODO_dump_func,                       /* todo_flags_finish */
2344   'j'                                   /* letter */
2345 };
2346
2347