OSDN Git Service

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