OSDN Git Service

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