OSDN Git Service

ce0be966592ec4d7cb78a0408b2007025076a91d
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfg.c
1 /* Control flow functions for trees.
2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License 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
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "output.h"
32 #include "errors.h"
33 #include "flags.h"
34 #include "function.h"
35 #include "expr.h"
36 #include "ggc.h"
37 #include "langhooks.h"
38 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "timevar.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
43 #include "toplev.h"
44 #include "except.h"
45 #include "cfgloop.h"
46
47 /* This file contains functions for building the Control Flow Graph (CFG)
48    for a function tree.  */
49
50 /* Local declarations.  */
51
52 /* Initial capacity for the basic block array.  */
53 static const int initial_cfg_capacity = 20;
54
55 /* Mapping of labels to their associated blocks.  This can greatly speed up
56    building of the CFG in code with lots of gotos.  */
57 static GTY(()) varray_type label_to_block_map;
58
59 /* CFG statistics.  */
60 struct cfg_stats_d
61 {
62   long num_merged_labels;
63 };
64
65 static struct cfg_stats_d cfg_stats;
66
67 /* Nonzero if we found a computed goto while building basic blocks.  */
68 static bool found_computed_goto;
69
70 /* Basic blocks and flowgraphs.  */
71 static basic_block create_bb (void *, void *, basic_block);
72 static void create_block_annotation (basic_block);
73 static void free_blocks_annotations (void);
74 static void clear_blocks_annotations (void);
75 static void make_blocks (tree);
76 static void factor_computed_gotos (void);
77
78 /* Edges.  */
79 static void make_edges (void);
80 static void make_ctrl_stmt_edges (basic_block);
81 static void make_exit_edges (basic_block);
82 static void make_cond_expr_edges (basic_block);
83 static void make_switch_expr_edges (basic_block);
84 static void make_goto_expr_edges (basic_block);
85 static edge tree_redirect_edge_and_branch (edge, basic_block);
86 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
87 static void split_critical_edges (void);
88
89 /* Various helpers.  */
90 static inline bool stmt_starts_bb_p (tree, tree);
91 static int tree_verify_flow_info (void);
92 static void tree_make_forwarder_block (edge);
93 static bool thread_jumps (void);
94 static bool tree_forwarder_block_p (basic_block);
95 static void bsi_commit_edge_inserts_1 (edge e);
96 static void tree_cfg2vcg (FILE *);
97
98 /* Flowgraph optimization and cleanup.  */
99 static void tree_merge_blocks (basic_block, basic_block);
100 static bool tree_can_merge_blocks_p (basic_block, basic_block);
101 static void remove_bb (basic_block);
102 static bool cleanup_control_flow (void);
103 static bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
104 static edge find_taken_edge_cond_expr (basic_block, tree);
105 static edge find_taken_edge_switch_expr (basic_block, tree);
106 static tree find_case_label_for_value (tree, tree);
107 static bool phi_alternatives_equal (basic_block, edge, edge);
108
109
110 /*---------------------------------------------------------------------------
111                               Create basic blocks
112 ---------------------------------------------------------------------------*/
113
114 /* Entry point to the CFG builder for trees.  TP points to the list of
115    statements to be added to the flowgraph.  */
116
117 static void
118 build_tree_cfg (tree *tp)
119 {
120   /* Register specific tree functions.  */
121   tree_register_cfg_hooks ();
122
123   /* Initialize rbi_pool.  */
124   alloc_rbi_pool ();
125
126   /* Initialize the basic block array.  */
127   init_flow ();
128   profile_status = PROFILE_ABSENT;
129   n_basic_blocks = 0;
130   last_basic_block = 0;
131   VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
132   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
133
134   /* Build a mapping of labels to their associated blocks.  */
135   VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
136                   "label to block map");
137
138   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
139   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
140
141   found_computed_goto = 0;
142   make_blocks (*tp);
143
144   /* Computed gotos are hell to deal with, especially if there are
145      lots of them with a large number of destinations.  So we factor
146      them to a common computed goto location before we build the
147      edge list.  After we convert back to normal form, we will un-factor
148      the computed gotos since factoring introduces an unwanted jump.  */
149   if (found_computed_goto)
150     factor_computed_gotos ();
151
152   /* Make sure there is always at least one block, even if its empty.  */
153   if (n_basic_blocks == 0)
154     create_empty_bb (ENTRY_BLOCK_PTR);
155
156   create_block_annotation (ENTRY_BLOCK_PTR);
157   create_block_annotation (EXIT_BLOCK_PTR);
158   
159   /* Adjust the size of the array.  */
160   VARRAY_GROW (basic_block_info, n_basic_blocks);
161
162   /* To speed up statement iterator walks, we first purge dead labels.  */
163   cleanup_dead_labels ();
164
165   /* Group case nodes to reduce the number of edges.
166      We do this after cleaning up dead labels because otherwise we miss
167      a lot of obvious case merging opportunities.  */
168   group_case_labels ();
169
170   /* Create the edges of the flowgraph.  */
171   make_edges ();
172
173   /* Debugging dumps.  */
174
175   /* Write the flowgraph to a VCG file.  */
176   {
177     int local_dump_flags;
178     FILE *dump_file = dump_begin (TDI_vcg, &local_dump_flags);
179     if (dump_file)
180       {
181         tree_cfg2vcg (dump_file);
182         dump_end (TDI_vcg, dump_file);
183       }
184   }
185
186   /* Dump a textual representation of the flowgraph.  */
187   if (dump_file)
188     dump_tree_cfg (dump_file, dump_flags);
189 }
190
191 static void
192 execute_build_cfg (void)
193 {
194   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
195 }
196
197 struct tree_opt_pass pass_build_cfg =
198 {
199   "cfg",                                /* name */
200   NULL,                                 /* gate */
201   execute_build_cfg,                    /* execute */
202   NULL,                                 /* sub */
203   NULL,                                 /* next */
204   0,                                    /* static_pass_number */
205   TV_TREE_CFG,                          /* tv_id */
206   PROP_gimple_leh,                      /* properties_required */
207   PROP_cfg,                             /* properties_provided */
208   0,                                    /* properties_destroyed */
209   0,                                    /* todo_flags_start */
210   TODO_verify_stmts,                    /* todo_flags_finish */
211   0                                     /* letter */
212 };
213
214 /* Search the CFG for any computed gotos.  If found, factor them to a 
215    common computed goto site.  Also record the location of that site so
216    that we can un-factor the gotos after we have converted back to 
217    normal form.  */
218
219 static void
220 factor_computed_gotos (void)
221 {
222   basic_block bb;
223   tree factored_label_decl = NULL;
224   tree var = NULL;
225   tree factored_computed_goto_label = NULL;
226   tree factored_computed_goto = NULL;
227
228   /* We know there are one or more computed gotos in this function.
229      Examine the last statement in each basic block to see if the block
230      ends with a computed goto.  */
231         
232   FOR_EACH_BB (bb)
233     {
234       block_stmt_iterator bsi = bsi_last (bb);
235       tree last;
236
237       if (bsi_end_p (bsi))
238         continue;
239       last = bsi_stmt (bsi);
240
241       /* Ignore the computed goto we create when we factor the original
242          computed gotos.  */
243       if (last == factored_computed_goto)
244         continue;
245
246       /* If the last statement is a computed goto, factor it.  */
247       if (computed_goto_p (last))
248         {
249           tree assignment;
250
251           /* The first time we find a computed goto we need to create
252              the factored goto block and the variable each original
253              computed goto will use for their goto destination.  */
254           if (! factored_computed_goto)
255             {
256               basic_block new_bb = create_empty_bb (bb);
257               block_stmt_iterator new_bsi = bsi_start (new_bb);
258
259               /* Create the destination of the factored goto.  Each original
260                  computed goto will put its desired destination into this
261                  variable and jump to the label we create immediately
262                  below.  */
263               var = create_tmp_var (ptr_type_node, "gotovar");
264
265               /* Build a label for the new block which will contain the
266                  factored computed goto.  */
267               factored_label_decl = create_artificial_label ();
268               factored_computed_goto_label
269                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
270               bsi_insert_after (&new_bsi, factored_computed_goto_label,
271                                 BSI_NEW_STMT);
272
273               /* Build our new computed goto.  */
274               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
275               bsi_insert_after (&new_bsi, factored_computed_goto,
276                                 BSI_NEW_STMT);
277             }
278
279           /* Copy the original computed goto's destination into VAR.  */
280           assignment = build (MODIFY_EXPR, ptr_type_node,
281                               var, GOTO_DESTINATION (last));
282           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
283
284           /* And re-vector the computed goto to the new destination.  */
285           GOTO_DESTINATION (last) = factored_label_decl;
286         }
287     }
288 }
289
290
291 /* Create annotations for a single basic block.  */
292
293 static void
294 create_block_annotation (basic_block bb)
295 {
296   /* Verify that the tree_annotations field is clear.  */
297   if (bb->tree_annotations)
298     abort ();
299   bb->tree_annotations = ggc_alloc_cleared (sizeof (struct bb_ann_d));
300 }
301
302
303 /* Free the annotations for all the basic blocks.  */
304
305 static void free_blocks_annotations (void)
306 {
307   clear_blocks_annotations ();  
308 }
309
310
311 /* Clear the annotations for all the basic blocks.  */
312
313 static void
314 clear_blocks_annotations (void)
315 {
316   basic_block bb;
317
318   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
319     bb->tree_annotations = NULL;
320 }
321
322
323 /* Build a flowgraph for the statement_list STMT_LIST.  */
324
325 static void
326 make_blocks (tree stmt_list)
327 {
328   tree_stmt_iterator i = tsi_start (stmt_list);
329   tree stmt = NULL;
330   bool start_new_block = true;
331   bool first_stmt_of_list = true;
332   basic_block bb = ENTRY_BLOCK_PTR;
333
334   while (!tsi_end_p (i))
335     {
336       tree prev_stmt;
337
338       prev_stmt = stmt;
339       stmt = tsi_stmt (i);
340
341       /* If the statement starts a new basic block or if we have determined
342          in a previous pass that we need to create a new block for STMT, do
343          so now.  */
344       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
345         {
346           if (!first_stmt_of_list)
347             stmt_list = tsi_split_statement_list_before (&i);
348           bb = create_basic_block (stmt_list, NULL, bb);
349           start_new_block = false;
350         }
351
352       /* Now add STMT to BB and create the subgraphs for special statement
353          codes.  */
354       set_bb_for_stmt (stmt, bb);
355
356       if (computed_goto_p (stmt))
357         found_computed_goto = true;
358
359       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
360          next iteration.  */
361       if (stmt_ends_bb_p (stmt))
362         start_new_block = true;
363
364       tsi_next (&i);
365       first_stmt_of_list = false;
366     }
367 }
368
369
370 /* Create and return a new empty basic block after bb AFTER.  */
371
372 static basic_block
373 create_bb (void *h, void *e, basic_block after)
374 {
375   basic_block bb;
376
377   if (e)
378     abort ();
379
380   /* Create and initialize a new basic block.  */
381   bb = alloc_block ();
382   memset (bb, 0, sizeof (*bb));
383
384   bb->index = last_basic_block;
385   bb->flags = BB_NEW;
386   bb->stmt_list = h ? h : alloc_stmt_list ();
387
388   /* Add the new block to the linked list of blocks.  */
389   link_block (bb, after);
390
391   /* Grow the basic block array if needed.  */
392   if ((size_t) last_basic_block == VARRAY_SIZE (basic_block_info))
393     {
394       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
395       VARRAY_GROW (basic_block_info, new_size);
396     }
397
398   /* Add the newly created block to the array.  */
399   BASIC_BLOCK (last_basic_block) = bb;
400
401   create_block_annotation (bb);
402
403   n_basic_blocks++;
404   last_basic_block++;
405
406   initialize_bb_rbi (bb);
407   return bb;
408 }
409
410
411 /*---------------------------------------------------------------------------
412                                  Edge creation
413 ---------------------------------------------------------------------------*/
414
415 /* Join all the blocks in the flowgraph.  */
416
417 static void
418 make_edges (void)
419 {
420   basic_block bb;
421
422   /* Create an edge from entry to the first block with executable
423      statements in it.  */
424   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
425
426   /* Traverse basic block array placing edges.  */
427   FOR_EACH_BB (bb)
428     {
429       tree first = first_stmt (bb);
430       tree last = last_stmt (bb);
431
432       if (first)
433         {
434           /* Edges for statements that always alter flow control.  */
435           if (is_ctrl_stmt (last))
436             make_ctrl_stmt_edges (bb);
437
438           /* Edges for statements that sometimes alter flow control.  */
439           if (is_ctrl_altering_stmt (last))
440             make_exit_edges (bb);
441         }
442
443       /* Finally, if no edges were created above, this is a regular
444          basic block that only needs a fallthru edge.  */
445       if (bb->succ == NULL)
446         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
447     }
448
449   /* We do not care about fake edges, so remove any that the CFG
450      builder inserted for completeness.  */
451   remove_fake_exit_edges ();
452
453   /* Clean up the graph and warn for unreachable code.  */
454   cleanup_tree_cfg ();
455 }
456
457
458 /* Create edges for control statement at basic block BB.  */
459
460 static void
461 make_ctrl_stmt_edges (basic_block bb)
462 {
463   tree last = last_stmt (bb);
464
465 #if defined ENABLE_CHECKING
466   if (last == NULL_TREE)
467     abort();
468 #endif
469
470   switch (TREE_CODE (last))
471     {
472     case GOTO_EXPR:
473       make_goto_expr_edges (bb);
474       break;
475
476     case RETURN_EXPR:
477       make_edge (bb, EXIT_BLOCK_PTR, 0);
478       break;
479
480     case COND_EXPR:
481       make_cond_expr_edges (bb);
482       break;
483
484     case SWITCH_EXPR:
485       make_switch_expr_edges (bb);
486       break;
487
488     case RESX_EXPR:
489       make_eh_edges (last);
490       /* Yet another NORETURN hack.  */
491       if (bb->succ == NULL)
492         make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
493       break;
494
495     default:
496       abort ();
497     }
498 }
499
500
501 /* Create exit edges for statements in block BB that alter the flow of
502    control.  Statements that alter the control flow are 'goto', 'return'
503    and calls to non-returning functions.  */
504
505 static void
506 make_exit_edges (basic_block bb)
507 {
508   tree last = last_stmt (bb), op;
509
510   if (last == NULL_TREE)
511     abort ();
512
513   switch (TREE_CODE (last))
514     {
515     case CALL_EXPR:
516       /* If this function receives a nonlocal goto, then we need to
517          make edges from this call site to all the nonlocal goto
518          handlers.  */
519       if (TREE_SIDE_EFFECTS (last)
520           && current_function_has_nonlocal_label)
521         make_goto_expr_edges (bb);
522
523       /* If this statement has reachable exception handlers, then
524          create abnormal edges to them.  */
525       make_eh_edges (last);
526
527       /* Some calls are known not to return.  For such calls we create
528          a fake edge.
529
530          We really need to revamp how we build edges so that it's not
531          such a bloody pain to avoid creating edges for this case since
532          all we do is remove these edges when we're done building the
533          CFG.  */
534       if (call_expr_flags (last) & (ECF_NORETURN | ECF_LONGJMP))
535         {
536           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
537           return;
538         }
539
540       /* Don't forget the fall-thru edge.  */
541       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
542       break;
543
544     case MODIFY_EXPR:
545       /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
546          may have an abnormal edge.  Search the RHS for this case and
547          create any required edges.  */
548       op = get_call_expr_in (last);
549       if (op && TREE_SIDE_EFFECTS (op)
550           && current_function_has_nonlocal_label)
551         make_goto_expr_edges (bb);
552
553       make_eh_edges (last);
554       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
555       break;
556
557     default:
558       abort ();
559     }
560 }
561
562
563 /* Create the edges for a COND_EXPR starting at block BB.
564    At this point, both clauses must contain only simple gotos.  */
565
566 static void
567 make_cond_expr_edges (basic_block bb)
568 {
569   tree entry = last_stmt (bb);
570   basic_block then_bb, else_bb;
571   tree then_label, else_label;
572
573 #if defined ENABLE_CHECKING
574   if (entry == NULL_TREE || TREE_CODE (entry) != COND_EXPR)
575     abort ();
576 #endif
577
578   /* Entry basic blocks for each component.  */
579   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
580   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
581   then_bb = label_to_block (then_label);
582   else_bb = label_to_block (else_label);
583
584   make_edge (bb, then_bb, EDGE_TRUE_VALUE);
585   make_edge (bb, else_bb, EDGE_FALSE_VALUE);
586 }
587
588
589 /* Create the edges for a SWITCH_EXPR starting at block BB.
590    At this point, the switch body has been lowered and the
591    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
592
593 static void
594 make_switch_expr_edges (basic_block bb)
595 {
596   tree entry = last_stmt (bb);
597   size_t i, n;
598   tree vec;
599
600   vec = SWITCH_LABELS (entry);
601   n = TREE_VEC_LENGTH (vec);
602
603   for (i = 0; i < n; ++i)
604     {
605       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
606       basic_block label_bb = label_to_block (lab);
607       make_edge (bb, label_bb, 0);
608     }
609 }
610
611
612 /* Return the basic block holding label DEST.  */
613
614 basic_block
615 label_to_block (tree dest)
616 {
617   int uid = LABEL_DECL_UID (dest);
618
619   /* We would die hard when faced by undefined label.  Emit label to
620      very first basic block.  This will hopefully make even the dataflow
621      and undefined variable warnings quite right.  */
622   if ((errorcount || sorrycount) && uid < 0)
623     {
624       block_stmt_iterator bsi = bsi_start (BASIC_BLOCK (0));
625       tree stmt;
626
627       stmt = build1 (LABEL_EXPR, void_type_node, dest);
628       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
629       uid = LABEL_DECL_UID (dest);
630     }
631   return VARRAY_BB (label_to_block_map, uid);
632 }
633
634
635 /* Create edges for a goto statement at block BB.  */
636
637 static void
638 make_goto_expr_edges (basic_block bb)
639 {
640   tree goto_t, dest;
641   basic_block target_bb;
642   int for_call;
643   block_stmt_iterator last = bsi_last (bb);
644
645   goto_t = bsi_stmt (last);
646
647   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
648      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
649      from a nonlocal goto.  */
650   if (TREE_CODE (goto_t) != GOTO_EXPR)
651     {
652       dest = error_mark_node;
653       for_call = 1;
654     }
655   else
656     {
657       dest = GOTO_DESTINATION (goto_t);
658       for_call = 0;
659
660       /* A GOTO to a local label creates normal edges.  */
661       if (simple_goto_p (goto_t))
662         {
663           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
664 #ifdef USE_MAPPED_LOCATION
665           e->goto_locus = EXPR_LOCATION (goto_t);
666 #else
667           e->goto_locus = EXPR_LOCUS (goto_t);
668 #endif
669           bsi_remove (&last);
670           return;
671         }
672
673       /* Nothing more to do for nonlocal gotos.  */
674       if (TREE_CODE (dest) == LABEL_DECL)
675         return;
676
677       /* Computed gotos remain.  */
678     }
679
680   /* Look for the block starting with the destination label.  In the
681      case of a computed goto, make an edge to any label block we find
682      in the CFG.  */
683   FOR_EACH_BB (target_bb)
684     {
685       block_stmt_iterator bsi;
686
687       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
688         {
689           tree target = bsi_stmt (bsi);
690
691           if (TREE_CODE (target) != LABEL_EXPR)
692             break;
693
694           if (
695               /* Computed GOTOs.  Make an edge to every label block that has
696                  been marked as a potential target for a computed goto.  */
697               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && for_call == 0)
698               /* Nonlocal GOTO target.  Make an edge to every label block
699                  that has been marked as a potential target for a nonlocal
700                  goto.  */
701               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call == 1))
702             {
703               make_edge (bb, target_bb, EDGE_ABNORMAL);
704               break;
705             }
706         }
707     }
708
709   /* Degenerate case of computed goto with no labels.  */
710   if (!for_call && !bb->succ)
711     make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
712 }
713
714
715 /*---------------------------------------------------------------------------
716                                Flowgraph analysis
717 ---------------------------------------------------------------------------*/
718
719 /* Remove unreachable blocks and other miscellaneous clean up work.  */
720
721 bool
722 cleanup_tree_cfg (void)
723 {
724   bool something_changed = true;
725   bool retval = false;
726
727   timevar_push (TV_TREE_CLEANUP_CFG);
728
729   /* These three transformations can cascade, so we iterate on them until
730      nothing changes.  */
731   while (something_changed)
732     {
733       something_changed = cleanup_control_flow ();
734       something_changed |= delete_unreachable_blocks ();
735       something_changed |= thread_jumps ();
736       retval |= something_changed;
737     }
738
739   /* Merging the blocks creates no new opportunities for the other
740      optimizations, so do it here.  */
741   merge_seq_blocks ();
742
743   compact_blocks ();
744
745 #ifdef ENABLE_CHECKING
746   verify_flow_info ();
747 #endif
748   timevar_pop (TV_TREE_CLEANUP_CFG);
749   return retval;
750 }
751
752
753 /* Cleanup useless labels in basic blocks.  This is something we wish
754    to do early because it allows us to group case labels before creating
755    the edges for the CFG, and it speeds up block statement iterators in
756    all passes later on.
757    We only run this pass once, running it more than once is probably not
758    profitable.  */
759
760 /* A map from basic block index to the leading label of that block.  */
761 static tree *label_for_bb;
762
763 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
764 static void
765 update_eh_label (struct eh_region *region)
766 {
767   tree old_label = get_eh_region_tree_label (region);
768   if (old_label)
769     {
770       tree new_label;
771       basic_block bb = label_to_block (old_label);
772
773       /* ??? After optimizing, there may be EH regions with labels
774          that have already been removed from the function body, so
775          there is no basic block for them.  */
776       if (! bb)
777         return;
778
779       new_label = label_for_bb[bb->index];
780       set_eh_region_tree_label (region, new_label);
781     }
782 }
783
784 /* Given LABEL return the first label in the same basic block.  */
785 static tree
786 main_block_label (tree label)
787 {
788   basic_block bb = label_to_block (label);
789
790   /* label_to_block possibly inserted undefined label into the chain.  */
791   if (!label_for_bb[bb->index])
792     label_for_bb[bb->index] = label;
793   return label_for_bb[bb->index];
794 }
795
796 /* Cleanup redundant labels.  This is a three-steo process:
797      1) Find the leading label for each block.
798      2) Redirect all references to labels to the leading labels.
799      3) Cleanup all useless labels.  */
800
801 void
802 cleanup_dead_labels (void)
803 {
804   basic_block bb;
805   label_for_bb = xcalloc (last_basic_block, sizeof (tree));
806
807   /* Find a suitable label for each block.  We use the first user-defined
808      label is there is one, or otherwise just the first label we see.  */
809   FOR_EACH_BB (bb)
810     {
811       block_stmt_iterator i;
812
813       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
814         {
815           tree label, stmt = bsi_stmt (i);
816
817           if (TREE_CODE (stmt) != LABEL_EXPR)
818             break;
819
820           label = LABEL_EXPR_LABEL (stmt);
821
822           /* If we have not yet seen a label for the current block,
823              remember this one and see if there are more labels.  */
824           if (! label_for_bb[bb->index])
825             {
826               label_for_bb[bb->index] = label;
827               continue;
828             }
829
830           /* If we did see a label for the current block already, but it
831              is an artificially created label, replace it if the current
832              label is a user defined label.  */
833           if (! DECL_ARTIFICIAL (label)
834               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
835             {
836               label_for_bb[bb->index] = label;
837               break;
838             }
839         }
840     }
841
842   /* Now redirect all jumps/branches to the selected label.
843      First do so for each block ending in a control statement.  */
844   FOR_EACH_BB (bb)
845     {
846       tree stmt = last_stmt (bb);
847       if (!stmt)
848         continue;
849
850       switch (TREE_CODE (stmt))
851         {
852         case COND_EXPR:
853           {
854             tree true_branch, false_branch;
855
856             true_branch = COND_EXPR_THEN (stmt);
857             false_branch = COND_EXPR_ELSE (stmt);
858
859             GOTO_DESTINATION (true_branch)
860               = main_block_label (GOTO_DESTINATION (true_branch));
861             GOTO_DESTINATION (false_branch)
862               = main_block_label (GOTO_DESTINATION (false_branch));
863
864             break;
865           }
866   
867         case SWITCH_EXPR:
868           {
869             size_t i;
870             tree vec = SWITCH_LABELS (stmt);
871             size_t n = TREE_VEC_LENGTH (vec);
872   
873             /* Replace all destination labels.  */
874             for (i = 0; i < n; ++i)
875               CASE_LABEL (TREE_VEC_ELT (vec, i))
876                 = main_block_label (CASE_LABEL (TREE_VEC_ELT (vec, i)));
877   
878             break;
879           }
880
881         /* We have to handle GOTO_EXPRs until they're removed, and we don't
882            remove them until after we've created the CFG edges.  */
883         case GOTO_EXPR:
884           if (! computed_goto_p (stmt))
885             {
886               GOTO_DESTINATION (stmt)
887                 = main_block_label (GOTO_DESTINATION (stmt));
888               break;
889             }
890
891         default:
892           break;
893       }
894     }
895
896   for_each_eh_region (update_eh_label);
897
898   /* Finally, purge dead labels.  All user-defined labels and labels that
899      can be the target of non-local gotos are preserved.  */
900   FOR_EACH_BB (bb)
901     {
902       block_stmt_iterator i;
903       tree label_for_this_bb = label_for_bb[bb->index];
904
905       if (! label_for_this_bb)
906         continue;
907
908       for (i = bsi_start (bb); !bsi_end_p (i); )
909         {
910           tree label, stmt = bsi_stmt (i);
911
912           if (TREE_CODE (stmt) != LABEL_EXPR)
913             break;
914
915           label = LABEL_EXPR_LABEL (stmt);
916
917           if (label == label_for_this_bb
918               || ! DECL_ARTIFICIAL (label)
919               || DECL_NONLOCAL (label))
920             bsi_next (&i);
921           else
922             bsi_remove (&i);
923         }
924     }
925
926   free (label_for_bb);
927 }
928
929 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
930    and scan the sorted vector of cases.  Combine the ones jumping to the
931    same label.
932    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
933
934 void
935 group_case_labels (void)
936 {
937   basic_block bb;
938
939   FOR_EACH_BB (bb)
940     {
941       tree stmt = last_stmt (bb);
942       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
943         {
944           tree labels = SWITCH_LABELS (stmt);
945           int old_size = TREE_VEC_LENGTH (labels);
946           int i, j, new_size = old_size;
947           tree default_label = TREE_VEC_ELT (labels, old_size - 1);
948
949           /* Look for possible opportunities to merge cases.
950              Ignore the last element of the label vector because it
951              must be the default case.  */
952           i = 0;
953           while (i < old_size - 2)
954             {
955               tree base_case, base_label, base_high, type;
956               base_case = TREE_VEC_ELT (labels, i);
957
958               if (! base_case)
959                 abort ();
960
961               base_label = CASE_LABEL (base_case);
962
963               /* Discard cases that have the same destination as the
964                  default case.  */
965               if (base_label == default_label)
966                 {
967                   TREE_VEC_ELT (labels, i) = NULL_TREE;
968                   i++;
969                   continue;
970                 }
971
972               type = TREE_TYPE (CASE_LOW (base_case));
973               base_high = CASE_HIGH (base_case) ?
974                 CASE_HIGH (base_case) : CASE_LOW (base_case);
975
976               /* Try to merge case labels.  Break out when we reach the end
977                  of the label vector or when we cannot merge the next case
978                  label with the current one.  */
979               while (i < old_size - 2)
980                 {
981                   tree merge_case = TREE_VEC_ELT (labels, ++i);
982                   tree merge_label = CASE_LABEL (merge_case);
983                   tree t = int_const_binop (PLUS_EXPR, base_high,
984                                             integer_one_node, 1);
985
986                   /* Merge the cases if they jump to the same place,
987                      and their ranges are consecutive.  */
988                   if (merge_label == base_label
989                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
990                     {
991                       base_high = CASE_HIGH (merge_case) ?
992                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
993                       CASE_HIGH (base_case) = base_high;
994                       TREE_VEC_ELT (labels, i) = NULL_TREE;
995                       new_size--;
996                     }
997                   else
998                     break;
999                 }
1000             }
1001
1002           /* Compress the case labels in the label vector, and adjust the
1003              length of the vector.  */
1004           for (i = 0, j = 0; i < new_size; i++)
1005             {
1006               while (! TREE_VEC_ELT (labels, j))
1007                 j++;
1008               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1009             }
1010           TREE_VEC_LENGTH (labels) = new_size;
1011         }
1012     }
1013 }
1014
1015 /* Checks whether we can merge block B into block A.  */
1016
1017 static bool
1018 tree_can_merge_blocks_p (basic_block a, basic_block b)
1019 {
1020   tree stmt;
1021   block_stmt_iterator bsi;
1022
1023   if (!a->succ
1024       || a->succ->succ_next)
1025     return false;
1026
1027   if (a->succ->flags & EDGE_ABNORMAL)
1028     return false;
1029
1030   if (a->succ->dest != b)
1031     return false;
1032
1033   if (b == EXIT_BLOCK_PTR)
1034     return false;
1035   
1036   if (b->pred->pred_next)
1037     return false;
1038
1039   /* If A ends by a statement causing exceptions or something similar, we
1040      cannot merge the blocks.  */
1041   stmt = last_stmt (a);
1042   if (stmt && stmt_ends_bb_p (stmt))
1043     return false;
1044
1045   /* Do not allow a block with only a non-local label to be merged.  */
1046   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1047       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1048     return false;
1049
1050   /* There may be no phi nodes at the start of b.  Most of these degenerate
1051      phi nodes should be cleaned up by kill_redundant_phi_nodes.  */
1052   if (phi_nodes (b))
1053     return false;
1054
1055   /* Do not remove user labels.  */
1056   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1057     {
1058       stmt = bsi_stmt (bsi);
1059       if (TREE_CODE (stmt) != LABEL_EXPR)
1060         break;
1061       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1062         return false;
1063     }
1064
1065   return true;
1066 }
1067
1068
1069 /* Merge block B into block A.  */
1070
1071 static void
1072 tree_merge_blocks (basic_block a, basic_block b)
1073 {
1074   block_stmt_iterator bsi;
1075   tree_stmt_iterator last;
1076
1077   if (dump_file)
1078     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1079
1080   /* Ensure that B follows A.  */
1081   move_block_after (b, a);
1082
1083   if (!(a->succ->flags & EDGE_FALLTHRU))
1084     abort ();
1085
1086   if (last_stmt (a)
1087       && stmt_ends_bb_p (last_stmt (a)))
1088     abort ();
1089
1090   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1091   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1092     {
1093       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1094         bsi_remove (&bsi);
1095       else
1096         {
1097           set_bb_for_stmt (bsi_stmt (bsi), a);
1098           bsi_next (&bsi);
1099         }
1100     }
1101
1102   /* Merge the chains.  */
1103   last = tsi_last (a->stmt_list);
1104   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1105   b->stmt_list = NULL;
1106 }
1107
1108
1109 /* Walk the function tree removing unnecessary statements.
1110
1111      * Empty statement nodes are removed
1112
1113      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1114
1115      * Unnecessary COND_EXPRs are removed
1116
1117      * Some unnecessary BIND_EXPRs are removed
1118
1119    Clearly more work could be done.  The trick is doing the analysis
1120    and removal fast enough to be a net improvement in compile times.
1121
1122    Note that when we remove a control structure such as a COND_EXPR
1123    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1124    to ensure we eliminate all the useless code.  */
1125
1126 struct rus_data
1127 {
1128   tree *last_goto;
1129   bool repeat;
1130   bool may_throw;
1131   bool may_branch;
1132   bool has_label;
1133 };
1134
1135 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1136
1137 static bool
1138 remove_useless_stmts_warn_notreached (tree stmt)
1139 {
1140   if (EXPR_HAS_LOCATION (stmt))
1141     {
1142       location_t loc = EXPR_LOCATION (stmt);
1143       warning ("%Hwill never be executed", &loc);
1144       return true;
1145     }
1146
1147   switch (TREE_CODE (stmt))
1148     {
1149     case STATEMENT_LIST:
1150       {
1151         tree_stmt_iterator i;
1152         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1153           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1154             return true;
1155       }
1156       break;
1157
1158     case COND_EXPR:
1159       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1160         return true;
1161       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1162         return true;
1163       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1164         return true;
1165       break;
1166
1167     case TRY_FINALLY_EXPR:
1168     case TRY_CATCH_EXPR:
1169       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1170         return true;
1171       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1172         return true;
1173       break;
1174
1175     case CATCH_EXPR:
1176       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1177     case EH_FILTER_EXPR:
1178       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1179     case BIND_EXPR:
1180       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1181
1182     default:
1183       /* Not a live container.  */
1184       break;
1185     }
1186
1187   return false;
1188 }
1189
1190 static void
1191 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1192 {
1193   tree then_clause, else_clause, cond;
1194   bool save_has_label, then_has_label, else_has_label;
1195
1196   save_has_label = data->has_label;
1197   data->has_label = false;
1198   data->last_goto = NULL;
1199
1200   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1201
1202   then_has_label = data->has_label;
1203   data->has_label = false;
1204   data->last_goto = NULL;
1205
1206   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1207
1208   else_has_label = data->has_label;
1209   data->has_label = save_has_label | then_has_label | else_has_label;
1210
1211   fold_stmt (stmt_p);
1212   then_clause = COND_EXPR_THEN (*stmt_p);
1213   else_clause = COND_EXPR_ELSE (*stmt_p);
1214   cond = COND_EXPR_COND (*stmt_p);
1215
1216   /* If neither arm does anything at all, we can remove the whole IF.  */
1217   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1218     {
1219       *stmt_p = build_empty_stmt ();
1220       data->repeat = true;
1221     }
1222
1223   /* If there are no reachable statements in an arm, then we can
1224      zap the entire conditional.  */
1225   else if (integer_nonzerop (cond) && !else_has_label)
1226     {
1227       if (warn_notreached)
1228         remove_useless_stmts_warn_notreached (else_clause);
1229       *stmt_p = then_clause;
1230       data->repeat = true;
1231     }
1232   else if (integer_zerop (cond) && !then_has_label)
1233     {
1234       if (warn_notreached)
1235         remove_useless_stmts_warn_notreached (then_clause);
1236       *stmt_p = else_clause;
1237       data->repeat = true;
1238     }
1239
1240   /* Check a couple of simple things on then/else with single stmts.  */
1241   else
1242     {
1243       tree then_stmt = expr_only (then_clause);
1244       tree else_stmt = expr_only (else_clause);
1245
1246       /* Notice branches to a common destination.  */
1247       if (then_stmt && else_stmt
1248           && TREE_CODE (then_stmt) == GOTO_EXPR
1249           && TREE_CODE (else_stmt) == GOTO_EXPR
1250           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1251         {
1252           *stmt_p = then_stmt;
1253           data->repeat = true;
1254         }
1255
1256       /* If the THEN/ELSE clause merely assigns a value to a variable or
1257          parameter which is already known to contain that value, then
1258          remove the useless THEN/ELSE clause.  */
1259       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1260         {
1261           if (else_stmt
1262               && TREE_CODE (else_stmt) == MODIFY_EXPR
1263               && TREE_OPERAND (else_stmt, 0) == cond
1264               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1265             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1266         }
1267       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1268                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1269                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1270                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1271         {
1272           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1273                        ? then_stmt : else_stmt);
1274           tree *location = (TREE_CODE (cond) == EQ_EXPR
1275                             ? &COND_EXPR_THEN (*stmt_p)
1276                             : &COND_EXPR_ELSE (*stmt_p));
1277
1278           if (stmt
1279               && TREE_CODE (stmt) == MODIFY_EXPR
1280               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1281               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1282             *location = alloc_stmt_list ();
1283         }
1284     }
1285
1286   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1287      would be re-introduced during lowering.  */
1288   data->last_goto = NULL;
1289 }
1290
1291
1292 static void
1293 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1294 {
1295   bool save_may_branch, save_may_throw;
1296   bool this_may_branch, this_may_throw;
1297
1298   /* Collect may_branch and may_throw information for the body only.  */
1299   save_may_branch = data->may_branch;
1300   save_may_throw = data->may_throw;
1301   data->may_branch = false;
1302   data->may_throw = false;
1303   data->last_goto = NULL;
1304
1305   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1306
1307   this_may_branch = data->may_branch;
1308   this_may_throw = data->may_throw;
1309   data->may_branch |= save_may_branch;
1310   data->may_throw |= save_may_throw;
1311   data->last_goto = NULL;
1312
1313   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1314
1315   /* If the body is empty, then we can emit the FINALLY block without
1316      the enclosing TRY_FINALLY_EXPR.  */
1317   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1318     {
1319       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1320       data->repeat = true;
1321     }
1322
1323   /* If the handler is empty, then we can emit the TRY block without
1324      the enclosing TRY_FINALLY_EXPR.  */
1325   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1326     {
1327       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1328       data->repeat = true;
1329     }
1330
1331   /* If the body neither throws, nor branches, then we can safely
1332      string the TRY and FINALLY blocks together.  */
1333   else if (!this_may_branch && !this_may_throw)
1334     {
1335       tree stmt = *stmt_p;
1336       *stmt_p = TREE_OPERAND (stmt, 0);
1337       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1338       data->repeat = true;
1339     }
1340 }
1341
1342
1343 static void
1344 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1345 {
1346   bool save_may_throw, this_may_throw;
1347   tree_stmt_iterator i;
1348   tree stmt;
1349
1350   /* Collect may_throw information for the body only.  */
1351   save_may_throw = data->may_throw;
1352   data->may_throw = false;
1353   data->last_goto = NULL;
1354
1355   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1356
1357   this_may_throw = data->may_throw;
1358   data->may_throw = save_may_throw;
1359
1360   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1361   if (!this_may_throw)
1362     {
1363       if (warn_notreached)
1364         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1365       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1366       data->repeat = true;
1367       return;
1368     }
1369
1370   /* Process the catch clause specially.  We may be able to tell that
1371      no exceptions propagate past this point.  */
1372
1373   this_may_throw = true;
1374   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1375   stmt = tsi_stmt (i);
1376   data->last_goto = NULL;
1377
1378   switch (TREE_CODE (stmt))
1379     {
1380     case CATCH_EXPR:
1381       for (; !tsi_end_p (i); tsi_next (&i))
1382         {
1383           stmt = tsi_stmt (i);
1384           /* If we catch all exceptions, then the body does not
1385              propagate exceptions past this point.  */
1386           if (CATCH_TYPES (stmt) == NULL)
1387             this_may_throw = false;
1388           data->last_goto = NULL;
1389           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1390         }
1391       break;
1392
1393     case EH_FILTER_EXPR:
1394       if (EH_FILTER_MUST_NOT_THROW (stmt))
1395         this_may_throw = false;
1396       else if (EH_FILTER_TYPES (stmt) == NULL)
1397         this_may_throw = false;
1398       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1399       break;
1400
1401     default:
1402       /* Otherwise this is a cleanup.  */
1403       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1404
1405       /* If the cleanup is empty, then we can emit the TRY block without
1406          the enclosing TRY_CATCH_EXPR.  */
1407       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1408         {
1409           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1410           data->repeat = true;
1411         }
1412       break;
1413     }
1414   data->may_throw |= this_may_throw;
1415 }
1416
1417
1418 static void
1419 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1420 {
1421   tree block;
1422
1423   /* First remove anything underneath the BIND_EXPR.  */
1424   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1425
1426   /* If the BIND_EXPR has no variables, then we can pull everything
1427      up one level and remove the BIND_EXPR, unless this is the toplevel
1428      BIND_EXPR for the current function or an inlined function.
1429
1430      When this situation occurs we will want to apply this
1431      optimization again.  */
1432   block = BIND_EXPR_BLOCK (*stmt_p);
1433   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1434       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1435       && (! block
1436           || ! BLOCK_ABSTRACT_ORIGIN (block)
1437           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1438               != FUNCTION_DECL)))
1439     {
1440       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1441       data->repeat = true;
1442     }
1443 }
1444
1445
1446 static void
1447 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1448 {
1449   tree dest = GOTO_DESTINATION (*stmt_p);
1450
1451   data->may_branch = true;
1452   data->last_goto = NULL;
1453
1454   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1455   if (TREE_CODE (dest) == LABEL_DECL)
1456     data->last_goto = stmt_p;
1457 }
1458
1459
1460 static void
1461 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1462 {
1463   tree label = LABEL_EXPR_LABEL (*stmt_p);
1464
1465   data->has_label = true;
1466
1467   /* We do want to jump across non-local label receiver code.  */
1468   if (DECL_NONLOCAL (label))
1469     data->last_goto = NULL;
1470
1471   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1472     {
1473       *data->last_goto = build_empty_stmt ();
1474       data->repeat = true;
1475     }
1476
1477   /* ??? Add something here to delete unused labels.  */
1478 }
1479
1480
1481 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1482    decl.  This allows us to eliminate redundant or useless
1483    calls to "const" functions. 
1484
1485    Gimplifier already does the same operation, but we may notice functions
1486    being const and pure once their calls has been gimplified, so we need
1487    to update the flag.  */
1488
1489 static void
1490 update_call_expr_flags (tree call)
1491 {
1492   tree decl = get_callee_fndecl (call);
1493   if (!decl)
1494     return;
1495   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1496     TREE_SIDE_EFFECTS (call) = 0;
1497   if (TREE_NOTHROW (decl))
1498     TREE_NOTHROW (call) = 1;
1499 }
1500
1501
1502 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1503
1504 void
1505 notice_special_calls (tree t)
1506 {
1507   int flags = call_expr_flags (t);
1508
1509   if (flags & ECF_MAY_BE_ALLOCA)
1510     current_function_calls_alloca = true;
1511   if (flags & ECF_RETURNS_TWICE)
1512     current_function_calls_setjmp = true;
1513 }
1514
1515
1516 /* Clear flags set by notice_special_calls.  Used by dead code removal
1517    to update the flags.  */
1518
1519 void
1520 clear_special_calls (void)
1521 {
1522   current_function_calls_alloca = false;
1523   current_function_calls_setjmp = false;
1524 }
1525
1526
1527 static void
1528 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1529 {
1530   tree t = *tp, op;
1531
1532   switch (TREE_CODE (t))
1533     {
1534     case COND_EXPR:
1535       remove_useless_stmts_cond (tp, data);
1536       break;
1537
1538     case TRY_FINALLY_EXPR:
1539       remove_useless_stmts_tf (tp, data);
1540       break;
1541
1542     case TRY_CATCH_EXPR:
1543       remove_useless_stmts_tc (tp, data);
1544       break;
1545
1546     case BIND_EXPR:
1547       remove_useless_stmts_bind (tp, data);
1548       break;
1549
1550     case GOTO_EXPR:
1551       remove_useless_stmts_goto (tp, data);
1552       break;
1553
1554     case LABEL_EXPR:
1555       remove_useless_stmts_label (tp, data);
1556       break;
1557
1558     case RETURN_EXPR:
1559       fold_stmt (tp);
1560       data->last_goto = NULL;
1561       data->may_branch = true;
1562       break;
1563
1564     case CALL_EXPR:
1565       fold_stmt (tp);
1566       data->last_goto = NULL;
1567       notice_special_calls (t);
1568       update_call_expr_flags (t);
1569       if (tree_could_throw_p (t))
1570         data->may_throw = true;
1571       break;
1572
1573     case MODIFY_EXPR:
1574       data->last_goto = NULL;
1575       fold_stmt (tp);
1576       op = get_call_expr_in (t);
1577       if (op)
1578         {
1579           update_call_expr_flags (op);
1580           notice_special_calls (op);
1581         }
1582       if (tree_could_throw_p (t))
1583         data->may_throw = true;
1584       break;
1585
1586     case STATEMENT_LIST:
1587       {
1588         tree_stmt_iterator i = tsi_start (t);
1589         while (!tsi_end_p (i))
1590           {
1591             t = tsi_stmt (i);
1592             if (IS_EMPTY_STMT (t))
1593               {
1594                 tsi_delink (&i);
1595                 continue;
1596               }
1597             
1598             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1599
1600             t = tsi_stmt (i);
1601             if (TREE_CODE (t) == STATEMENT_LIST)
1602               {
1603                 tsi_link_before (&i, t, TSI_SAME_STMT);
1604                 tsi_delink (&i);
1605               }
1606             else
1607               tsi_next (&i);
1608           }
1609       }
1610       break;
1611     case SWITCH_EXPR:
1612       fold_stmt (tp);
1613       data->last_goto = NULL;
1614       break;
1615
1616     default:
1617       data->last_goto = NULL;
1618       break;
1619     }
1620 }
1621
1622 static void
1623 remove_useless_stmts (void)
1624 {
1625   struct rus_data data;
1626
1627   clear_special_calls ();
1628
1629   do
1630     {
1631       memset (&data, 0, sizeof (data));
1632       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1633     }
1634   while (data.repeat);
1635 }
1636
1637
1638 struct tree_opt_pass pass_remove_useless_stmts = 
1639 {
1640   "useless",                            /* name */
1641   NULL,                                 /* gate */
1642   remove_useless_stmts,                 /* execute */
1643   NULL,                                 /* sub */
1644   NULL,                                 /* next */
1645   0,                                    /* static_pass_number */
1646   0,                                    /* tv_id */
1647   PROP_gimple_any,                      /* properties_required */
1648   0,                                    /* properties_provided */
1649   0,                                    /* properties_destroyed */
1650   0,                                    /* todo_flags_start */
1651   TODO_dump_func,                       /* todo_flags_finish */
1652   0                                     /* letter */
1653 };
1654
1655
1656 /* Remove obviously useless statements in basic block BB.  */
1657
1658 static void
1659 cfg_remove_useless_stmts_bb (basic_block bb)
1660 {
1661   block_stmt_iterator bsi;
1662   tree stmt = NULL_TREE;
1663   tree cond, var = NULL_TREE, val = NULL_TREE;
1664   struct var_ann_d *ann;
1665
1666   /* Check whether we come here from a condition, and if so, get the
1667      condition.  */
1668   if (!bb->pred
1669       || bb->pred->pred_next
1670       || !(bb->pred->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1671     return;
1672
1673   cond = COND_EXPR_COND (last_stmt (bb->pred->src));
1674
1675   if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1676     {
1677       var = cond;
1678       val = (bb->pred->flags & EDGE_FALSE_VALUE
1679              ? boolean_false_node : boolean_true_node);
1680     }
1681   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
1682            && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1683                || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL))
1684     {
1685       var = TREE_OPERAND (cond, 0);
1686       val = (bb->pred->flags & EDGE_FALSE_VALUE
1687              ? boolean_true_node : boolean_false_node);
1688     }
1689   else
1690     {
1691       if (bb->pred->flags & EDGE_FALSE_VALUE)
1692         cond = invert_truthvalue (cond);
1693       if (TREE_CODE (cond) == EQ_EXPR
1694           && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1695               || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1696           && (TREE_CODE (TREE_OPERAND (cond, 1)) == VAR_DECL
1697               || TREE_CODE (TREE_OPERAND (cond, 1)) == PARM_DECL
1698               || TREE_CONSTANT (TREE_OPERAND (cond, 1))))
1699         {
1700           var = TREE_OPERAND (cond, 0);
1701           val = TREE_OPERAND (cond, 1);
1702         }
1703       else
1704         return;
1705     }
1706
1707   /* Only work for normal local variables.  */
1708   ann = var_ann (var);
1709   if (!ann
1710       || ann->may_aliases
1711       || TREE_ADDRESSABLE (var))
1712     return;
1713
1714   if (! TREE_CONSTANT (val))
1715     {
1716       ann = var_ann (val);
1717       if (!ann
1718           || ann->may_aliases
1719           || TREE_ADDRESSABLE (val))
1720         return;
1721     }
1722
1723   /* Ignore floating point variables, since comparison behaves weird for
1724      them.  */
1725   if (FLOAT_TYPE_P (TREE_TYPE (var)))
1726     return;
1727
1728   for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
1729     {
1730       stmt = bsi_stmt (bsi);
1731
1732       /* If the THEN/ELSE clause merely assigns a value to a variable/parameter
1733          which is already known to contain that value, then remove the useless
1734          THEN/ELSE clause.  */
1735       if (TREE_CODE (stmt) == MODIFY_EXPR
1736           && TREE_OPERAND (stmt, 0) == var
1737           && operand_equal_p (val, TREE_OPERAND (stmt, 1), 0))
1738         {
1739           bsi_remove (&bsi);
1740           continue;
1741         }
1742
1743       /* Invalidate the var if we encounter something that could modify it.
1744          Likewise for the value it was previously set to.  Note that we only
1745          consider values that are either a VAR_DECL or PARM_DECL so we
1746          can test for conflict very simply.  */
1747       if (TREE_CODE (stmt) == ASM_EXPR
1748           || (TREE_CODE (stmt) == MODIFY_EXPR
1749               && (TREE_OPERAND (stmt, 0) == var
1750                   || TREE_OPERAND (stmt, 0) == val)))
1751         return;
1752   
1753       bsi_next (&bsi);
1754     }
1755 }
1756
1757
1758 /* A CFG-aware version of remove_useless_stmts.  */
1759
1760 void
1761 cfg_remove_useless_stmts (void)
1762 {
1763   basic_block bb;
1764
1765 #ifdef ENABLE_CHECKING
1766   verify_flow_info ();
1767 #endif
1768
1769   FOR_EACH_BB (bb)
1770     {
1771       cfg_remove_useless_stmts_bb (bb);
1772     }
1773 }
1774
1775
1776 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1777
1778 static void
1779 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1780 {
1781   tree phi;
1782
1783   /* Since this block is no longer reachable, we can just delete all
1784      of its PHI nodes.  */
1785   phi = phi_nodes (bb);
1786   while (phi)
1787     {
1788       tree next = PHI_CHAIN (phi);
1789       remove_phi_node (phi, NULL_TREE, bb);
1790       phi = next;
1791     }
1792
1793   /* Remove edges to BB's successors.  */
1794   while (bb->succ != NULL)
1795     ssa_remove_edge (bb->succ);
1796 }
1797
1798
1799 /* Remove statements of basic block BB.  */
1800
1801 static void
1802 remove_bb (basic_block bb)
1803 {
1804   block_stmt_iterator i;
1805   source_locus loc = 0;
1806
1807   if (dump_file)
1808     {
1809       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1810       if (dump_flags & TDF_DETAILS)
1811         {
1812           dump_bb (bb, dump_file, 0);
1813           fprintf (dump_file, "\n");
1814         }
1815     }
1816
1817   /* Remove all the instructions in the block.  */
1818   for (i = bsi_start (bb); !bsi_end_p (i); bsi_remove (&i))
1819     {
1820       tree stmt = bsi_stmt (i);
1821
1822       set_bb_for_stmt (stmt, NULL);
1823
1824       /* Don't warn for removed gotos.  Gotos are often removed due to
1825          jump threading, thus resulting in bogus warnings.  Not great,
1826          since this way we lose warnings for gotos in the original
1827          program that are indeed unreachable.  */
1828       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
1829 #ifdef USE_MAPPED_LOCATION
1830         loc = EXPR_LOCATION (stmt);
1831 #else
1832         loc = EXPR_LOCUS (stmt);
1833 #endif
1834     }
1835
1836   /* If requested, give a warning that the first statement in the
1837      block is unreachable.  We walk statements backwards in the
1838      loop above, so the last statement we process is the first statement
1839      in the block.  */
1840   if (warn_notreached && loc)
1841 #ifdef USE_MAPPED_LOCATION
1842     warning ("%Hwill never be executed", &loc);
1843 #else
1844     warning ("%Hwill never be executed", loc);
1845 #endif
1846
1847   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1848 }
1849
1850
1851 /* Examine BB to determine if it is a forwarding block (a block which only
1852    transfers control to a new destination).  If BB is a forwarding block,
1853    then return the edge leading to the ultimate destination.  */
1854
1855 edge
1856 tree_block_forwards_to (basic_block bb)
1857 {
1858   block_stmt_iterator bsi;
1859   bb_ann_t ann = bb_ann (bb);
1860   tree stmt;
1861
1862   /* If this block is not forwardable, then avoid useless work.  */
1863   if (! ann->forwardable)
1864     return NULL;
1865
1866   /* Set this block to not be forwardable.  This prevents infinite loops since
1867      any block currently under examination is considered non-forwardable.  */
1868   ann->forwardable = 0;
1869
1870   /* No forwarding is possible if this block is a special block (ENTRY/EXIT),
1871      this block has more than one successor, this block's single successor is
1872      reached via an abnormal edge, this block has phi nodes, or this block's
1873      single successor has phi nodes.  */
1874   if (bb == EXIT_BLOCK_PTR
1875       || bb == ENTRY_BLOCK_PTR
1876       || !bb->succ
1877       || bb->succ->succ_next
1878       || bb->succ->dest == EXIT_BLOCK_PTR
1879       || (bb->succ->flags & EDGE_ABNORMAL) != 0
1880       || phi_nodes (bb)
1881       || phi_nodes (bb->succ->dest))
1882     return NULL;
1883
1884   /* Walk past any labels at the start of this block.  */
1885   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1886     {
1887       stmt = bsi_stmt (bsi);
1888       if (TREE_CODE (stmt) != LABEL_EXPR)
1889         break;
1890     }
1891
1892   /* If we reached the end of this block we may be able to optimize this
1893      case.  */
1894   if (bsi_end_p (bsi))
1895     {
1896       edge dest;
1897
1898       /* Recursive call to pick up chains of forwarding blocks.  */
1899       dest = tree_block_forwards_to (bb->succ->dest);
1900
1901       /* If none found, we forward to bb->succ at minimum.  */
1902       if (!dest)
1903         dest = bb->succ;
1904
1905       ann->forwardable = 1;
1906       return dest;
1907     }
1908
1909   /* No forwarding possible.  */
1910   return NULL;
1911 }
1912
1913
1914 /* Try to remove superfluous control structures.  */
1915
1916 static bool
1917 cleanup_control_flow (void)
1918 {
1919   basic_block bb;
1920   block_stmt_iterator bsi;
1921   bool retval = false;
1922   tree stmt;
1923
1924   FOR_EACH_BB (bb)
1925     {
1926       bsi = bsi_last (bb);
1927
1928       if (bsi_end_p (bsi))
1929         continue;
1930       
1931       stmt = bsi_stmt (bsi);
1932       if (TREE_CODE (stmt) == COND_EXPR
1933           || TREE_CODE (stmt) == SWITCH_EXPR)
1934         retval |= cleanup_control_expr_graph (bb, bsi);
1935     }
1936   return retval;
1937 }
1938
1939
1940 /* Disconnect an unreachable block in the control expression starting
1941    at block BB.  */
1942
1943 static bool
1944 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
1945 {
1946   edge taken_edge;
1947   bool retval = false;
1948   tree expr = bsi_stmt (bsi), val;
1949
1950   if (bb->succ->succ_next)
1951     {
1952       edge e, next;
1953
1954       switch (TREE_CODE (expr))
1955         {
1956         case COND_EXPR:
1957           val = COND_EXPR_COND (expr);
1958           break;
1959
1960         case SWITCH_EXPR:
1961           val = SWITCH_COND (expr);
1962           if (TREE_CODE (val) != INTEGER_CST)
1963             return false;
1964           break;
1965
1966         default:
1967           abort ();
1968         }
1969
1970       taken_edge = find_taken_edge (bb, val);
1971       if (!taken_edge)
1972         return false;
1973
1974       /* Remove all the edges except the one that is always executed.  */
1975       for (e = bb->succ; e; e = next)
1976         {
1977           next = e->succ_next;
1978           if (e != taken_edge)
1979             {
1980               taken_edge->probability += e->probability;
1981               taken_edge->count += e->count;
1982               ssa_remove_edge (e);
1983               retval = true;
1984             }
1985         }
1986       if (taken_edge->probability > REG_BR_PROB_BASE)
1987         taken_edge->probability = REG_BR_PROB_BASE;
1988     }
1989   else
1990     taken_edge = bb->succ;
1991
1992   bsi_remove (&bsi);
1993   taken_edge->flags = EDGE_FALLTHRU;
1994
1995   /* We removed some paths from the cfg.  */
1996   if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
1997     dom_computed[CDI_DOMINATORS] = DOM_CONS_OK;
1998
1999   return retval;
2000 }
2001
2002
2003 /* Given a control block BB and a predicate VAL, return the edge that
2004    will be taken out of the block.  If VAL does not match a unique
2005    edge, NULL is returned.  */
2006
2007 edge
2008 find_taken_edge (basic_block bb, tree val)
2009 {
2010   tree stmt;
2011
2012   stmt = last_stmt (bb);
2013
2014 #if defined ENABLE_CHECKING
2015   if (stmt == NULL_TREE || !is_ctrl_stmt (stmt))
2016     abort ();
2017 #endif
2018
2019   /* If VAL is a predicate of the form N RELOP N, where N is an
2020      SSA_NAME, we can always determine its truth value (except when
2021      doing floating point comparisons that may involve NaNs).  */
2022   if (val
2023       && TREE_CODE_CLASS (TREE_CODE (val)) == '<'
2024       && TREE_OPERAND (val, 0) == TREE_OPERAND (val, 1)
2025       && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME
2026       && (TREE_CODE (TREE_TYPE (TREE_OPERAND (val, 0))) != REAL_TYPE
2027           || !HONOR_NANS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (val, 0))))))
2028     {
2029       enum tree_code code = TREE_CODE (val);
2030
2031       if (code == EQ_EXPR || code == LE_EXPR || code == GE_EXPR)
2032         val = boolean_true_node;
2033       else if (code == LT_EXPR || code == GT_EXPR || code == NE_EXPR)
2034         val = boolean_false_node;
2035     }
2036
2037   /* If VAL is not a constant, we can't determine which edge might
2038      be taken.  */
2039   if (val == NULL || !really_constant_p (val))
2040     return NULL;
2041
2042   if (TREE_CODE (stmt) == COND_EXPR)
2043     return find_taken_edge_cond_expr (bb, val);
2044
2045   if (TREE_CODE (stmt) == SWITCH_EXPR)
2046     return find_taken_edge_switch_expr (bb, val);
2047
2048   return bb->succ;
2049 }
2050
2051
2052 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2053    statement, determine which of the two edges will be taken out of the
2054    block.  Return NULL if either edge may be taken.  */
2055
2056 static edge
2057 find_taken_edge_cond_expr (basic_block bb, tree val)
2058 {
2059   edge true_edge, false_edge;
2060
2061   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2062
2063   /* If both edges of the branch lead to the same basic block, it doesn't
2064      matter which edge is taken.  */
2065   if (true_edge->dest == false_edge->dest)
2066     return true_edge;
2067
2068   /* Otherwise, try to determine which branch of the if() will be taken.
2069      If VAL is a constant but it can't be reduced to a 0 or a 1, then
2070      we don't really know which edge will be taken at runtime.  This
2071      may happen when comparing addresses (e.g., if (&var1 == 4)).  */
2072   if (integer_nonzerop (val))
2073     return true_edge;
2074   else if (integer_zerop (val))
2075     return false_edge;
2076   else
2077     return NULL;
2078 }
2079
2080
2081 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
2082    statement, determine which edge will be taken out of the block.  Return
2083    NULL if any edge may be taken.  */
2084
2085 static edge
2086 find_taken_edge_switch_expr (basic_block bb, tree val)
2087 {
2088   tree switch_expr, taken_case;
2089   basic_block dest_bb;
2090   edge e;
2091
2092   if (TREE_CODE (val) != INTEGER_CST)
2093     return NULL;
2094
2095   switch_expr = last_stmt (bb);
2096   taken_case = find_case_label_for_value (switch_expr, val);
2097   dest_bb = label_to_block (CASE_LABEL (taken_case));
2098
2099   e = find_edge (bb, dest_bb);
2100   if (!e)
2101     abort ();
2102   return e;
2103 }
2104
2105
2106 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2107    We can make optimal use here of the fact that the case labels are
2108    sorted: We can do a binary search for a case matching VAL.  */
2109
2110 static tree
2111 find_case_label_for_value (tree switch_expr, tree val)
2112 {
2113   tree vec = SWITCH_LABELS (switch_expr);
2114   size_t low, high, n = TREE_VEC_LENGTH (vec);
2115   tree default_case = TREE_VEC_ELT (vec, n - 1);
2116
2117   for (low = -1, high = n - 1; high - low > 1; )
2118     {
2119       size_t i = (high + low) / 2;
2120       tree t = TREE_VEC_ELT (vec, i);
2121       int cmp;
2122
2123       /* Cache the result of comparing CASE_LOW and val.  */
2124       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2125
2126       if (cmp > 0)
2127         high = i;
2128       else
2129         low = i;
2130
2131       if (CASE_HIGH (t) == NULL)
2132         {
2133           /* A singe-valued case label.  */
2134           if (cmp == 0)
2135             return t;
2136         }
2137       else
2138         {
2139           /* A case range.  We can only handle integer ranges.  */
2140           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2141             return t;
2142         }
2143     }
2144
2145   return default_case;
2146 }
2147
2148
2149 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
2150    those alternatives are equal in each of the PHI nodes, then return
2151    true, else return false.  */
2152
2153 static bool
2154 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
2155 {
2156   tree phi, val1, val2;
2157   int n1, n2;
2158
2159   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
2160     {
2161       n1 = phi_arg_from_edge (phi, e1);
2162       n2 = phi_arg_from_edge (phi, e2);
2163
2164 #ifdef ENABLE_CHECKING
2165       if (n1 < 0 || n2 < 0)
2166         abort ();
2167 #endif
2168
2169       val1 = PHI_ARG_DEF (phi, n1);
2170       val2 = PHI_ARG_DEF (phi, n2);
2171
2172       if (!operand_equal_p (val1, val2, 0))
2173         return false;
2174     }
2175
2176   return true;
2177 }
2178
2179
2180 /*---------------------------------------------------------------------------
2181                               Debugging functions
2182 ---------------------------------------------------------------------------*/
2183
2184 /* Dump tree-specific information of block BB to file OUTF.  */
2185
2186 void
2187 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2188 {
2189   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2190 }
2191
2192
2193 /* Dump a basic block on stderr.  */
2194
2195 void
2196 debug_tree_bb (basic_block bb)
2197 {
2198   dump_bb (bb, stderr, 0);
2199 }
2200
2201
2202 /* Dump basic block with index N on stderr.  */
2203
2204 basic_block
2205 debug_tree_bb_n (int n)
2206 {
2207   debug_tree_bb (BASIC_BLOCK (n));
2208   return BASIC_BLOCK (n);
2209 }        
2210
2211
2212 /* Dump the CFG on stderr.
2213
2214    FLAGS are the same used by the tree dumping functions
2215    (see TDF_* in tree.h).  */
2216
2217 void
2218 debug_tree_cfg (int flags)
2219 {
2220   dump_tree_cfg (stderr, flags);
2221 }
2222
2223
2224 /* Dump the program showing basic block boundaries on the given FILE.
2225
2226    FLAGS are the same used by the tree dumping functions (see TDF_* in
2227    tree.h).  */
2228
2229 void
2230 dump_tree_cfg (FILE *file, int flags)
2231 {
2232   if (flags & TDF_DETAILS)
2233     {
2234       const char *funcname
2235         = lang_hooks.decl_printable_name (current_function_decl, 2);
2236
2237       fputc ('\n', file);
2238       fprintf (file, ";; Function %s\n\n", funcname);
2239       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2240                n_basic_blocks, n_edges, last_basic_block);
2241
2242       brief_dump_cfg (file);
2243       fprintf (file, "\n");
2244     }
2245
2246   if (flags & TDF_STATS)
2247     dump_cfg_stats (file);
2248
2249   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2250 }
2251
2252
2253 /* Dump CFG statistics on FILE.  */
2254
2255 void
2256 dump_cfg_stats (FILE *file)
2257 {
2258   static long max_num_merged_labels = 0;
2259   unsigned long size, total = 0;
2260   int n_edges;
2261   basic_block bb;
2262   const char * const fmt_str   = "%-30s%-13s%12s\n";
2263   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2264   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2265   const char *funcname
2266     = lang_hooks.decl_printable_name (current_function_decl, 2);
2267
2268
2269   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2270
2271   fprintf (file, "---------------------------------------------------------\n");
2272   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2273   fprintf (file, fmt_str, "", "  instances  ", "used ");
2274   fprintf (file, "---------------------------------------------------------\n");
2275
2276   size = n_basic_blocks * sizeof (struct basic_block_def);
2277   total += size;
2278   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2279            SCALE (size), LABEL (size));
2280
2281   n_edges = 0;
2282   FOR_EACH_BB (bb)
2283     {
2284       edge e;
2285       for (e = bb->succ; e; e = e->succ_next)
2286         n_edges++;
2287     }
2288   size = n_edges * sizeof (struct edge_def);
2289   total += size;
2290   fprintf (file, fmt_str_1, "Edges", n_edges, SCALE (size), LABEL (size));
2291
2292   size = n_basic_blocks * sizeof (struct bb_ann_d);
2293   total += size;
2294   fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
2295            SCALE (size), LABEL (size));
2296
2297   fprintf (file, "---------------------------------------------------------\n");
2298   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2299            LABEL (total));
2300   fprintf (file, "---------------------------------------------------------\n");
2301   fprintf (file, "\n");
2302
2303   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2304     max_num_merged_labels = cfg_stats.num_merged_labels;
2305
2306   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2307            cfg_stats.num_merged_labels, max_num_merged_labels);
2308
2309   fprintf (file, "\n");
2310 }
2311
2312
2313 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2314    linked in the final executable.  */
2315
2316 void
2317 debug_cfg_stats (void)
2318 {
2319   dump_cfg_stats (stderr);
2320 }
2321
2322
2323 /* Dump the flowgraph to a .vcg FILE.  */
2324
2325 static void
2326 tree_cfg2vcg (FILE *file)
2327 {
2328   edge e;
2329   basic_block bb;
2330   const char *funcname
2331     = lang_hooks.decl_printable_name (current_function_decl, 2);
2332
2333   /* Write the file header.  */
2334   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2335   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2336   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2337
2338   /* Write blocks and edges.  */
2339   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
2340     {
2341       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2342                e->dest->index);
2343
2344       if (e->flags & EDGE_FAKE)
2345         fprintf (file, " linestyle: dotted priority: 10");
2346       else
2347         fprintf (file, " linestyle: solid priority: 100");
2348
2349       fprintf (file, " }\n");
2350     }
2351   fputc ('\n', file);
2352
2353   FOR_EACH_BB (bb)
2354     {
2355       enum tree_code head_code, end_code;
2356       const char *head_name, *end_name;
2357       int head_line = 0;
2358       int end_line = 0;
2359       tree first = first_stmt (bb);
2360       tree last = last_stmt (bb);
2361
2362       if (first)
2363         {
2364           head_code = TREE_CODE (first);
2365           head_name = tree_code_name[head_code];
2366           head_line = get_lineno (first);
2367         }
2368       else
2369         head_name = "no-statement";
2370
2371       if (last)
2372         {
2373           end_code = TREE_CODE (last);
2374           end_name = tree_code_name[end_code];
2375           end_line = get_lineno (last);
2376         }
2377       else
2378         end_name = "no-statement";
2379
2380       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2381                bb->index, bb->index, head_name, head_line, end_name,
2382                end_line);
2383
2384       for (e = bb->succ; e; e = e->succ_next)
2385         {
2386           if (e->dest == EXIT_BLOCK_PTR)
2387             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2388           else
2389             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2390
2391           if (e->flags & EDGE_FAKE)
2392             fprintf (file, " priority: 10 linestyle: dotted");
2393           else
2394             fprintf (file, " priority: 100 linestyle: solid");
2395
2396           fprintf (file, " }\n");
2397         }
2398
2399       if (bb->next_bb != EXIT_BLOCK_PTR)
2400         fputc ('\n', file);
2401     }
2402
2403   fputs ("}\n\n", file);
2404 }
2405
2406
2407
2408 /*---------------------------------------------------------------------------
2409                              Miscellaneous helpers
2410 ---------------------------------------------------------------------------*/
2411
2412 /* Return true if T represents a stmt that always transfers control.  */
2413
2414 bool
2415 is_ctrl_stmt (tree t)
2416 {
2417   return (TREE_CODE (t) == COND_EXPR
2418           || TREE_CODE (t) == SWITCH_EXPR
2419           || TREE_CODE (t) == GOTO_EXPR
2420           || TREE_CODE (t) == RETURN_EXPR
2421           || TREE_CODE (t) == RESX_EXPR);
2422 }
2423
2424
2425 /* Return true if T is a statement that may alter the flow of control
2426    (e.g., a call to a non-returning function).  */
2427
2428 bool
2429 is_ctrl_altering_stmt (tree t)
2430 {
2431   tree call;
2432
2433 #if defined ENABLE_CHECKING
2434   if (t == NULL)
2435     abort ();
2436 #endif
2437
2438   call = get_call_expr_in (t);
2439   if (call)
2440     {
2441       /* A non-pure/const CALL_EXPR alters flow control if the current
2442          function has nonlocal labels.  */
2443       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2444         return true;
2445
2446       /* A CALL_EXPR also alters control flow if it does not return.  */
2447       if (call_expr_flags (call) & (ECF_NORETURN | ECF_LONGJMP))
2448         return true;
2449     }
2450
2451   /* If a statement can throw, it alters control flow.  */
2452   return tree_can_throw_internal (t);
2453 }
2454
2455
2456 /* Return true if T is a computed goto.  */
2457
2458 bool
2459 computed_goto_p (tree t)
2460 {
2461   return (TREE_CODE (t) == GOTO_EXPR
2462           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2463 }
2464
2465
2466 /* Checks whether EXPR is a simple local goto.  */
2467
2468 bool
2469 simple_goto_p (tree expr)
2470 {
2471   return (TREE_CODE (expr) == GOTO_EXPR
2472           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2473 }
2474
2475
2476 /* Return true if T should start a new basic block.  PREV_T is the
2477    statement preceding T.  It is used when T is a label or a case label.
2478    Labels should only start a new basic block if their previous statement
2479    wasn't a label.  Otherwise, sequence of labels would generate
2480    unnecessary basic blocks that only contain a single label.  */
2481
2482 static inline bool
2483 stmt_starts_bb_p (tree t, tree prev_t)
2484 {
2485   enum tree_code code;
2486
2487   if (t == NULL_TREE)
2488     return false;
2489
2490   /* LABEL_EXPRs start a new basic block only if the preceding
2491      statement wasn't a label of the same type.  This prevents the
2492      creation of consecutive blocks that have nothing but a single
2493      label.  */
2494   code = TREE_CODE (t);
2495   if (code == LABEL_EXPR)
2496     {
2497       /* Nonlocal and computed GOTO targets always start a new block.  */
2498       if (code == LABEL_EXPR
2499           && (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2500               || FORCED_LABEL (LABEL_EXPR_LABEL (t))))
2501         return true;
2502
2503       if (prev_t && TREE_CODE (prev_t) == code)
2504         {
2505           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2506             return true;
2507
2508           cfg_stats.num_merged_labels++;
2509           return false;
2510         }
2511       else
2512         return true;
2513     }
2514
2515   return false;
2516 }
2517
2518
2519 /* Return true if T should end a basic block.  */
2520
2521 bool
2522 stmt_ends_bb_p (tree t)
2523 {
2524   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2525 }
2526
2527
2528 /* Add gotos that used to be represented implicitly in the CFG.  */
2529
2530 void
2531 disband_implicit_edges (void)
2532 {
2533   basic_block bb;
2534   block_stmt_iterator last;
2535   edge e;
2536   tree stmt, label;
2537
2538   FOR_EACH_BB (bb)
2539     {
2540       last = bsi_last (bb);
2541       stmt = last_stmt (bb);
2542
2543       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2544         {
2545           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2546              from cfg_remove_useless_stmts here since it violates the
2547              invariants for tree--cfg correspondence and thus fits better
2548              here where we do it anyway.  */
2549           for (e = bb->succ; e; e = e->succ_next)
2550             {
2551               if (e->dest != bb->next_bb)
2552                 continue;
2553
2554               if (e->flags & EDGE_TRUE_VALUE)
2555                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2556               else if (e->flags & EDGE_FALSE_VALUE)
2557                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2558               else
2559                 abort ();
2560               e->flags |= EDGE_FALLTHRU;
2561             }
2562
2563           continue;
2564         }
2565
2566       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2567         {
2568           /* Remove the RETURN_EXPR if we may fall though to the exit
2569              instead.  */
2570           if (!bb->succ
2571               || bb->succ->succ_next
2572               || bb->succ->dest != EXIT_BLOCK_PTR)
2573             abort ();
2574
2575           if (bb->next_bb == EXIT_BLOCK_PTR
2576               && !TREE_OPERAND (stmt, 0))
2577             {
2578               bsi_remove (&last);
2579               bb->succ->flags |= EDGE_FALLTHRU;
2580             }
2581           continue;
2582         }
2583
2584       /* There can be no fallthru edge if the last statement is a control
2585          one.  */
2586       if (stmt && is_ctrl_stmt (stmt))
2587         continue;
2588
2589       /* Find a fallthru edge and emit the goto if necessary.  */
2590       for (e = bb->succ; e; e = e->succ_next)
2591         if (e->flags & EDGE_FALLTHRU)
2592           break;
2593
2594       if (!e || e->dest == bb->next_bb)
2595         continue;
2596
2597       if (e->dest == EXIT_BLOCK_PTR)
2598         abort ();
2599
2600       label = tree_block_label (e->dest);
2601
2602       stmt = build1 (GOTO_EXPR, void_type_node, label);
2603 #ifdef USE_MAPPED_LOCATION
2604       SET_EXPR_LOCATION (stmt, e->goto_locus);
2605 #else
2606       SET_EXPR_LOCUS (stmt, e->goto_locus);
2607 #endif
2608       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2609       e->flags &= ~EDGE_FALLTHRU;
2610     }
2611 }
2612
2613 /* Remove block annotations and other datastructures.  */
2614
2615 void
2616 delete_tree_cfg_annotations (void)
2617 {
2618   basic_block bb;
2619   if (n_basic_blocks > 0)
2620     free_blocks_annotations ();
2621
2622   label_to_block_map = NULL;
2623   free_rbi_pool ();
2624   FOR_EACH_BB (bb)
2625     bb->rbi = NULL;
2626 }
2627
2628
2629 /* Return the first statement in basic block BB.  */
2630
2631 tree
2632 first_stmt (basic_block bb)
2633 {
2634   block_stmt_iterator i = bsi_start (bb);
2635   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2636 }
2637
2638
2639 /* Return the last statement in basic block BB.  */
2640
2641 tree
2642 last_stmt (basic_block bb)
2643 {
2644   block_stmt_iterator b = bsi_last (bb);
2645   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2646 }
2647
2648
2649 /* Return a pointer to the last statement in block BB.  */
2650
2651 tree *
2652 last_stmt_ptr (basic_block bb)
2653 {
2654   block_stmt_iterator last = bsi_last (bb);
2655   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2656 }
2657
2658
2659 /* Return the last statement of an otherwise empty block.  Return NULL
2660    if the block is totally empty, or if it contains more than one
2661    statement.  */
2662
2663 tree
2664 last_and_only_stmt (basic_block bb)
2665 {
2666   block_stmt_iterator i = bsi_last (bb);
2667   tree last, prev;
2668
2669   if (bsi_end_p (i))
2670     return NULL_TREE;
2671
2672   last = bsi_stmt (i);
2673   bsi_prev (&i);
2674   if (bsi_end_p (i))
2675     return last;
2676
2677   /* Empty statements should no longer appear in the instruction stream.
2678      Everything that might have appeared before should be deleted by
2679      remove_useless_stmts, and the optimizers should just bsi_remove
2680      instead of smashing with build_empty_stmt.
2681
2682      Thus the only thing that should appear here in a block containing
2683      one executable statement is a label.  */
2684   prev = bsi_stmt (i);
2685   if (TREE_CODE (prev) == LABEL_EXPR)
2686     return last;
2687   else
2688     return NULL_TREE;
2689 }
2690
2691
2692 /* Mark BB as the basic block holding statement T.  */
2693
2694 void
2695 set_bb_for_stmt (tree t, basic_block bb)
2696 {
2697   if (TREE_CODE (t) == STATEMENT_LIST)
2698     {
2699       tree_stmt_iterator i;
2700       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2701         set_bb_for_stmt (tsi_stmt (i), bb);
2702     }
2703   else
2704     {
2705       stmt_ann_t ann = get_stmt_ann (t);
2706       ann->bb = bb;
2707
2708       /* If the statement is a label, add the label to block-to-labels map
2709          so that we can speed up edge creation for GOTO_EXPRs.  */
2710       if (TREE_CODE (t) == LABEL_EXPR)
2711         {
2712           int uid;
2713
2714           t = LABEL_EXPR_LABEL (t);
2715           uid = LABEL_DECL_UID (t);
2716           if (uid == -1)
2717             {
2718               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2719               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2720                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2721             }
2722           else
2723             {
2724 #ifdef ENABLE_CHECKING
2725               /* We're moving an existing label.  Make sure that we've
2726                  removed it from the old block.  */
2727               if (bb && VARRAY_BB (label_to_block_map, uid))
2728                 abort ();
2729 #endif
2730             }
2731           VARRAY_BB (label_to_block_map, uid) = bb;
2732         }
2733     }
2734 }
2735
2736 /* Finds iterator for STMT.  */
2737
2738 extern block_stmt_iterator
2739 stmt_for_bsi (tree stmt)
2740 {
2741   block_stmt_iterator bsi;
2742
2743   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2744     if (bsi_stmt (bsi) == stmt)
2745       return bsi;
2746
2747   abort ();
2748 }
2749
2750 /* Insert statement (or statement list) T before the statement
2751    pointed-to by iterator I.  M specifies how to update iterator I
2752    after insertion (see enum bsi_iterator_update).  */
2753
2754 void
2755 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2756 {
2757   set_bb_for_stmt (t, i->bb);
2758   tsi_link_before (&i->tsi, t, m);
2759   modify_stmt (t);
2760 }
2761
2762
2763 /* Insert statement (or statement list) T after the statement
2764    pointed-to by iterator I.  M specifies how to update iterator I
2765    after insertion (see enum bsi_iterator_update).  */
2766
2767 void
2768 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2769 {
2770   set_bb_for_stmt (t, i->bb);
2771   tsi_link_after (&i->tsi, t, m);
2772   modify_stmt (t);
2773 }
2774
2775
2776 /* Remove the statement pointed to by iterator I.  The iterator is updated
2777    to the next statement.  */
2778
2779 void
2780 bsi_remove (block_stmt_iterator *i)
2781 {
2782   tree t = bsi_stmt (*i);
2783   set_bb_for_stmt (t, NULL);
2784   tsi_delink (&i->tsi);
2785 }
2786
2787
2788 /* Move the statement at FROM so it comes right after the statement at TO.  */
2789
2790 void 
2791 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2792 {
2793   tree stmt = bsi_stmt (*from);
2794   bsi_remove (from);
2795   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2796
2797
2798
2799 /* Move the statement at FROM so it comes right before the statement at TO.  */
2800
2801 void 
2802 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2803 {
2804   tree stmt = bsi_stmt (*from);
2805   bsi_remove (from);
2806   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2807 }
2808
2809
2810 /* Move the statement at FROM to the end of basic block BB.  */
2811
2812 void
2813 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2814 {
2815   block_stmt_iterator last = bsi_last (bb);
2816   
2817   /* Have to check bsi_end_p because it could be an empty block.  */
2818   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2819     bsi_move_before (from, &last);
2820   else
2821     bsi_move_after (from, &last);
2822 }
2823
2824
2825 /* Replace the contents of the statement pointed to by iterator BSI
2826    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
2827    information of the original statement is preserved.  */
2828
2829 void
2830 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
2831 {
2832   int eh_region;
2833   tree orig_stmt = bsi_stmt (*bsi);
2834
2835   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2836   set_bb_for_stmt (stmt, bsi->bb);
2837
2838   /* Preserve EH region information from the original statement, if
2839      requested by the caller.  */
2840   if (preserve_eh_info)
2841     {
2842       eh_region = lookup_stmt_eh_region (orig_stmt);
2843       if (eh_region >= 0)
2844         add_stmt_to_eh_region (stmt, eh_region);
2845     }
2846
2847   *bsi_stmt_ptr (*bsi) = stmt;
2848   modify_stmt (stmt);
2849 }
2850
2851
2852 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2853    is made to place the statement in an existing basic block, but
2854    sometimes that isn't possible.  When it isn't possible, the edge is
2855    split and the statement is added to the new block.
2856
2857    In all cases, the returned *BSI points to the correct location.  The
2858    return value is true if insertion should be done after the location,
2859    or false if it should be done before the location.  If new basic block
2860    has to be created, it is stored in *NEW_BB.  */
2861
2862 static bool
2863 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2864                            basic_block *new_bb)
2865 {
2866   basic_block dest, src;
2867   tree tmp;
2868
2869   dest = e->dest;
2870  restart:
2871
2872   /* If the destination has one predecessor which has no PHI nodes,
2873      insert there.  Except for the exit block. 
2874
2875      The requirement for no PHI nodes could be relaxed.  Basically we
2876      would have to examine the PHIs to prove that none of them used
2877      the value set by the statement we want to insert on E.   That
2878      hardly seems worth the effort.  */
2879   if (dest->pred->pred_next == NULL
2880       && ! phi_nodes (dest)
2881       && dest != EXIT_BLOCK_PTR)
2882     {
2883       *bsi = bsi_start (dest);
2884       if (bsi_end_p (*bsi))
2885         return true;
2886
2887       /* Make sure we insert after any leading labels.  */
2888       tmp = bsi_stmt (*bsi);
2889       while (TREE_CODE (tmp) == LABEL_EXPR)
2890         {
2891           bsi_next (bsi);
2892           if (bsi_end_p (*bsi))
2893             break;
2894           tmp = bsi_stmt (*bsi);
2895         }
2896
2897       if (bsi_end_p (*bsi))
2898         {
2899           *bsi = bsi_last (dest);
2900           return true;
2901         }
2902       else
2903         return false;
2904     }
2905
2906   /* If the source has one successor, the edge is not abnormal and
2907      the last statement does not end a basic block, insert there.
2908      Except for the entry block.  */
2909   src = e->src;
2910   if ((e->flags & EDGE_ABNORMAL) == 0
2911       && src->succ->succ_next == NULL
2912       && src != ENTRY_BLOCK_PTR)
2913     {
2914       *bsi = bsi_last (src);
2915       if (bsi_end_p (*bsi))
2916         return true;
2917
2918       tmp = bsi_stmt (*bsi);
2919       if (!stmt_ends_bb_p (tmp))
2920         return true;
2921
2922       /* Insert code just before returning the value.  We may need to decompose
2923          the return in the case it contains non-trivial operand.  */
2924       if (TREE_CODE (tmp) == RETURN_EXPR)
2925         {
2926           tree op = TREE_OPERAND (tmp, 0);
2927           if (!is_gimple_val (op))
2928             {
2929               if (TREE_CODE (op) != MODIFY_EXPR)
2930                 abort ();
2931               bsi_insert_before (bsi, op, BSI_NEW_STMT);
2932               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
2933             }
2934           bsi_prev (bsi);
2935           return true;
2936         }
2937     }
2938
2939   /* Otherwise, create a new basic block, and split this edge.  */
2940   dest = split_edge (e);
2941   if (new_bb)
2942     *new_bb = dest;
2943   e = dest->pred;
2944   goto restart;
2945 }
2946
2947
2948 /* This routine will commit all pending edge insertions, creating any new
2949    basic blocks which are necessary.
2950
2951    If specified, NEW_BLOCKS returns a count of the number of new basic
2952    blocks which were created.  */
2953
2954 void
2955 bsi_commit_edge_inserts (int *new_blocks)
2956 {
2957   basic_block bb;
2958   edge e;
2959   int blocks;
2960
2961   blocks = n_basic_blocks;
2962
2963   bsi_commit_edge_inserts_1 (ENTRY_BLOCK_PTR->succ);
2964
2965   FOR_EACH_BB (bb)
2966     for (e = bb->succ; e; e = e->succ_next)
2967       bsi_commit_edge_inserts_1 (e);
2968
2969   if (new_blocks)
2970     *new_blocks = n_basic_blocks - blocks;
2971 }
2972
2973
2974 /* Commit insertions pending at edge E.  */
2975
2976 static void
2977 bsi_commit_edge_inserts_1 (edge e)
2978 {
2979   if (PENDING_STMT (e))
2980     {
2981       block_stmt_iterator bsi;
2982       tree stmt = PENDING_STMT (e);
2983
2984       PENDING_STMT (e) = NULL_TREE;
2985
2986       if (tree_find_edge_insert_loc (e, &bsi, NULL))
2987         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2988       else
2989         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2990     }
2991 }
2992
2993
2994 /* Add STMT to the pending list of edge E.  No actual insertion is
2995    made until a call to bsi_commit_edge_inserts () is made.  */
2996
2997 void
2998 bsi_insert_on_edge (edge e, tree stmt)
2999 {
3000   append_to_statement_list (stmt, &PENDING_STMT (e));
3001 }
3002
3003 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If new block has to
3004    be created, it is returned.  */
3005
3006 basic_block
3007 bsi_insert_on_edge_immediate (edge e, tree stmt)
3008 {
3009   block_stmt_iterator bsi;
3010   basic_block new_bb = NULL;
3011
3012   if (PENDING_STMT (e))
3013     abort ();
3014
3015   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3016     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3017   else
3018     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3019
3020   return new_bb;
3021 }
3022
3023 /*---------------------------------------------------------------------------
3024              Tree specific functions for CFG manipulation
3025 ---------------------------------------------------------------------------*/
3026
3027 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3028    Abort on abnormal edges.  */
3029
3030 static basic_block
3031 tree_split_edge (edge edge_in)
3032 {
3033   basic_block new_bb, after_bb, dest, src;
3034   edge new_edge, e;
3035   tree phi;
3036   int i, num_elem;
3037
3038   /* Abnormal edges cannot be split.  */
3039   if (edge_in->flags & EDGE_ABNORMAL)
3040     abort ();
3041
3042   src = edge_in->src;
3043   dest = edge_in->dest;
3044
3045   /* Place the new block in the block list.  Try to keep the new block
3046      near its "logical" location.  This is of most help to humans looking
3047      at debugging dumps.  */
3048   for (e = dest->pred; e; e = e->pred_next)
3049     if (e->src->next_bb == dest)
3050       break;
3051   if (!e)
3052     after_bb = dest->prev_bb;
3053   else
3054     after_bb = edge_in->src;
3055
3056   new_bb = create_empty_bb (after_bb);
3057   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3058
3059   /* Find all the PHI arguments on the original edge, and change them to
3060      the new edge.  Do it before redirection, so that the argument does not
3061      get removed.  */
3062   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
3063     {
3064       num_elem = PHI_NUM_ARGS (phi);
3065       for (i = 0; i < num_elem; i++)
3066         if (PHI_ARG_EDGE (phi, i) == edge_in)
3067           {
3068             PHI_ARG_EDGE (phi, i) = new_edge;
3069             break;
3070           }
3071     }
3072
3073   if (!redirect_edge_and_branch (edge_in, new_bb))
3074     abort ();
3075
3076   if (PENDING_STMT (edge_in))
3077     abort ();
3078
3079   return new_bb;
3080 }
3081
3082
3083 /* Return true when BB has label LABEL in it.  */
3084
3085 static bool
3086 has_label_p (basic_block bb, tree label)
3087 {
3088   block_stmt_iterator bsi;
3089
3090   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3091     {
3092       tree stmt = bsi_stmt (bsi);
3093
3094       if (TREE_CODE (stmt) != LABEL_EXPR)
3095         return false;
3096       if (LABEL_EXPR_LABEL (stmt) == label)
3097         return true;
3098     }
3099   return false;
3100 }
3101
3102
3103 /* Callback for walk_tree, check that all elements with address taken are
3104    properly noticed as such.  */
3105
3106 static tree
3107 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3108 {
3109   tree t = *tp, x;
3110
3111   if (TYPE_P (t))
3112     *walk_subtrees = 0;
3113   
3114   /* Check operand N for being valid GIMPLE and give error MSG if not. 
3115      We check for constants explicitly since they are not considered
3116      gimple invariants if they overflowed.  */
3117 #define CHECK_OP(N, MSG) \
3118   do { if (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, N))) != 'c'     \
3119          && !is_gimple_val (TREE_OPERAND (t, N)))                       \
3120        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3121
3122   switch (TREE_CODE (t))
3123     {
3124     case SSA_NAME:
3125       if (SSA_NAME_IN_FREE_LIST (t))
3126         {
3127           error ("SSA name in freelist but still referenced");
3128           return *tp;
3129         }
3130       break;
3131
3132     case MODIFY_EXPR:
3133       x = TREE_OPERAND (t, 0);
3134       if (TREE_CODE (x) == BIT_FIELD_REF
3135           && is_gimple_reg (TREE_OPERAND (x, 0)))
3136         {
3137           error ("GIMPLE register modified with BIT_FIELD_REF");
3138           return t;
3139         }
3140       break;
3141
3142     case ADDR_EXPR:
3143       /* Skip any references (they will be checked when we recurse down the
3144          tree) and ensure that any variable used as a prefix is marked
3145          addressable.  */
3146       for (x = TREE_OPERAND (t, 0);
3147            (handled_component_p (x)
3148             || TREE_CODE (x) == REALPART_EXPR
3149             || TREE_CODE (x) == IMAGPART_EXPR);
3150            x = TREE_OPERAND (x, 0))
3151         ;
3152
3153       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3154         return NULL;
3155       if (!TREE_ADDRESSABLE (x))
3156         {
3157           error ("address taken, but ADDRESSABLE bit not set");
3158           return x;
3159         }
3160       break;
3161
3162     case COND_EXPR:
3163       x = TREE_OPERAND (t, 0);
3164       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3165         {
3166           error ("non-boolean used in condition");
3167           return x;
3168         }
3169       break;
3170
3171     case NOP_EXPR:
3172     case CONVERT_EXPR:
3173     case FIX_TRUNC_EXPR:
3174     case FIX_CEIL_EXPR:
3175     case FIX_FLOOR_EXPR:
3176     case FIX_ROUND_EXPR:
3177     case FLOAT_EXPR:
3178     case NEGATE_EXPR:
3179     case ABS_EXPR:
3180     case BIT_NOT_EXPR:
3181     case NON_LVALUE_EXPR:
3182     case TRUTH_NOT_EXPR:
3183       CHECK_OP (0, "Invalid operand to unary operator");
3184       break;
3185
3186     case REALPART_EXPR:
3187     case IMAGPART_EXPR:
3188     case COMPONENT_REF:
3189     case ARRAY_REF:
3190     case ARRAY_RANGE_REF:
3191     case BIT_FIELD_REF:
3192     case VIEW_CONVERT_EXPR:
3193       /* We have a nest of references.  Verify that each of the operands
3194          that determine where to reference is either a constant or a variable,
3195          verify that the base is valid, and then show we've already checked
3196          the subtrees.  */
3197       while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
3198              || handled_component_p (t))
3199         {
3200           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3201             CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3202           else if (TREE_CODE (t) == ARRAY_REF
3203                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3204             {
3205               CHECK_OP (1, "Invalid array index.");
3206               if (TREE_OPERAND (t, 2))
3207                 CHECK_OP (2, "Invalid array lower bound.");
3208               if (TREE_OPERAND (t, 3))
3209                 CHECK_OP (3, "Invalid array stride.");
3210             }
3211           else if (TREE_CODE (t) == BIT_FIELD_REF)
3212             {
3213               CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3214               CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3215             }
3216
3217           t = TREE_OPERAND (t, 0);
3218         }
3219
3220       if (TREE_CODE_CLASS (TREE_CODE (t)) != 'c'
3221           && !is_gimple_lvalue (t))
3222         {
3223           error ("Invalid reference prefix.");
3224           return t;
3225         }
3226       *walk_subtrees = 0;
3227       break;
3228
3229     case LT_EXPR:
3230     case LE_EXPR:
3231     case GT_EXPR:
3232     case GE_EXPR:
3233     case EQ_EXPR:
3234     case NE_EXPR:
3235     case UNORDERED_EXPR:
3236     case ORDERED_EXPR:
3237     case UNLT_EXPR:
3238     case UNLE_EXPR:
3239     case UNGT_EXPR:
3240     case UNGE_EXPR:
3241     case UNEQ_EXPR:
3242     case LTGT_EXPR:
3243     case PLUS_EXPR:
3244     case MINUS_EXPR:
3245     case MULT_EXPR:
3246     case TRUNC_DIV_EXPR:
3247     case CEIL_DIV_EXPR:
3248     case FLOOR_DIV_EXPR:
3249     case ROUND_DIV_EXPR:
3250     case TRUNC_MOD_EXPR:
3251     case CEIL_MOD_EXPR:
3252     case FLOOR_MOD_EXPR:
3253     case ROUND_MOD_EXPR:
3254     case RDIV_EXPR:
3255     case EXACT_DIV_EXPR:
3256     case MIN_EXPR:
3257     case MAX_EXPR:
3258     case LSHIFT_EXPR:
3259     case RSHIFT_EXPR:
3260     case LROTATE_EXPR:
3261     case RROTATE_EXPR:
3262     case BIT_IOR_EXPR:
3263     case BIT_XOR_EXPR:
3264     case BIT_AND_EXPR:
3265       CHECK_OP (0, "Invalid operand to binary operator");
3266       CHECK_OP (1, "Invalid operand to binary operator");
3267       break;
3268
3269     default:
3270       break;
3271     }
3272   return NULL;
3273
3274 #undef CHECK_OP
3275 }
3276
3277
3278 /* Verify STMT, return true if STMT is not in GIMPLE form.
3279    TODO: Implement type checking.  */
3280
3281 static bool
3282 verify_stmt (tree stmt, bool last_in_block)
3283 {
3284   tree addr;
3285
3286   if (!is_gimple_stmt (stmt))
3287     {
3288       error ("Is not a valid GIMPLE statement.");
3289       goto fail;
3290     }
3291
3292   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3293   if (addr)
3294     {
3295       debug_generic_stmt (addr);
3296       return true;
3297     }
3298
3299   /* If the statement is marked as part of an EH region, then it is
3300      expected that the statement could throw.  Verify that when we
3301      have optimizations that simplify statements such that we prove
3302      that they cannot throw, that we update other data structures
3303      to match.  */
3304   if (lookup_stmt_eh_region (stmt) >= 0)
3305     {
3306       if (!tree_could_throw_p (stmt))
3307         {
3308           error ("Statement marked for throw, but doesn't.");
3309           goto fail;
3310         }
3311       if (!last_in_block && tree_can_throw_internal (stmt))
3312         {
3313           error ("Statement marked for throw in middle of block.");
3314           goto fail;
3315         }
3316     }
3317
3318   return false;
3319
3320  fail:
3321   debug_generic_stmt (stmt);
3322   return true;
3323 }
3324
3325
3326 /* Return true when the T can be shared.  */
3327
3328 static bool
3329 tree_node_can_be_shared (tree t)
3330 {
3331   if (TYPE_P (t) || DECL_P (t)
3332       /* We check for constants explicitly since they are not considered
3333          gimple invariants if they overflowed.  */
3334       || TREE_CODE_CLASS (TREE_CODE (t)) == 'c'
3335       || is_gimple_min_invariant (t)
3336       || TREE_CODE (t) == SSA_NAME)
3337     return true;
3338
3339   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3340           /* We check for constants explicitly since they are not considered
3341              gimple invariants if they overflowed.  */
3342           && (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 1))) == 'c'
3343               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3344          || (TREE_CODE (t) == COMPONENT_REF
3345              || TREE_CODE (t) == REALPART_EXPR
3346              || TREE_CODE (t) == IMAGPART_EXPR))
3347     t = TREE_OPERAND (t, 0);
3348
3349   if (DECL_P (t))
3350     return true;
3351
3352   return false;
3353 }
3354
3355
3356 /* Called via walk_trees.  Verify tree sharing.  */
3357
3358 static tree
3359 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3360 {
3361   htab_t htab = (htab_t) data;
3362   void **slot;
3363
3364   if (tree_node_can_be_shared (*tp))
3365     {
3366       *walk_subtrees = false;
3367       return NULL;
3368     }
3369
3370   slot = htab_find_slot (htab, *tp, INSERT);
3371   if (*slot)
3372     return *slot;
3373   *slot = *tp;
3374
3375   return NULL;
3376 }
3377
3378
3379 /* Verify the GIMPLE statement chain.  */
3380
3381 void
3382 verify_stmts (void)
3383 {
3384   basic_block bb;
3385   block_stmt_iterator bsi;
3386   bool err = false;
3387   htab_t htab;
3388   tree addr;
3389
3390   timevar_push (TV_TREE_STMT_VERIFY);
3391   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3392
3393   FOR_EACH_BB (bb)
3394     {
3395       tree phi;
3396       int i;
3397
3398       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3399         {
3400           int phi_num_args = PHI_NUM_ARGS (phi);
3401
3402           for (i = 0; i < phi_num_args; i++)
3403             {
3404               tree t = PHI_ARG_DEF (phi, i);
3405               tree addr;
3406
3407               /* Addressable variables do have SSA_NAMEs but they
3408                  are not considered gimple values.  */
3409               if (TREE_CODE (t) != SSA_NAME
3410                   && TREE_CODE (t) != FUNCTION_DECL
3411                   && !is_gimple_val (t))
3412                 {
3413                   error ("PHI def is not a GIMPLE value");
3414                   debug_generic_stmt (phi);
3415                   debug_generic_stmt (t);
3416                   err |= true;
3417                 }
3418
3419               addr = walk_tree (&t, verify_expr, NULL, NULL);
3420               if (addr)
3421                 {
3422                   debug_generic_stmt (addr);
3423                   err |= true;
3424                 }
3425
3426               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3427               if (addr)
3428                 {
3429                   error ("Incorrect sharing of tree nodes");
3430                   debug_generic_stmt (phi);
3431                   debug_generic_stmt (addr);
3432                   err |= true;
3433                 }
3434             }
3435         }
3436
3437       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3438         {
3439           tree stmt = bsi_stmt (bsi);
3440           bsi_next (&bsi);
3441           err |= verify_stmt (stmt, bsi_end_p (bsi));
3442           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3443           if (addr)
3444             {
3445               error ("Incorrect sharing of tree nodes");
3446               debug_generic_stmt (stmt);
3447               debug_generic_stmt (addr);
3448               err |= true;
3449             }
3450         }
3451     }
3452
3453   if (err)
3454     internal_error ("verify_stmts failed.");
3455
3456   htab_delete (htab);
3457   timevar_pop (TV_TREE_STMT_VERIFY);
3458 }
3459
3460
3461 /* Verifies that the flow information is OK.  */
3462
3463 static int
3464 tree_verify_flow_info (void)
3465 {
3466   int err = 0;
3467   basic_block bb;
3468   block_stmt_iterator bsi;
3469   tree stmt;
3470   edge e;
3471
3472   if (ENTRY_BLOCK_PTR->stmt_list)
3473     {
3474       error ("ENTRY_BLOCK has a statement list associated with it\n");
3475       err = 1;
3476     }
3477
3478   if (EXIT_BLOCK_PTR->stmt_list)
3479     {
3480       error ("EXIT_BLOCK has a statement list associated with it\n");
3481       err = 1;
3482     }
3483
3484   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
3485     if (e->flags & EDGE_FALLTHRU)
3486       {
3487         error ("Fallthru to exit from bb %d\n", e->src->index);
3488         err = 1;
3489       }
3490
3491   FOR_EACH_BB (bb)
3492     {
3493       bool found_ctrl_stmt = false;
3494
3495       /* Skip labels on the start of basic block.  */
3496       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3497         {
3498           if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
3499             break;
3500
3501           if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
3502             {
3503               error ("Label %s to block does not match in bb %d\n",
3504                      IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
3505                      bb->index);
3506               err = 1;
3507             }
3508
3509           if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
3510               != current_function_decl)
3511             {
3512               error ("Label %s has incorrect context in bb %d\n",
3513                      IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
3514                      bb->index);
3515               err = 1;
3516             }
3517         }
3518
3519       /* Verify that body of basic block BB is free of control flow.  */
3520       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3521         {
3522           tree stmt = bsi_stmt (bsi);
3523
3524           if (found_ctrl_stmt)
3525             {
3526               error ("Control flow in the middle of basic block %d\n",
3527                      bb->index);
3528               err = 1;
3529             }
3530
3531           if (stmt_ends_bb_p (stmt))
3532             found_ctrl_stmt = true;
3533
3534           if (TREE_CODE (stmt) == LABEL_EXPR)
3535             {
3536               error ("Label %s in the middle of basic block %d\n",
3537                      IDENTIFIER_POINTER (DECL_NAME (stmt)),
3538                      bb->index);
3539               err = 1;
3540             }
3541         }
3542       bsi = bsi_last (bb);
3543       if (bsi_end_p (bsi))
3544         continue;
3545
3546       stmt = bsi_stmt (bsi);
3547
3548       if (is_ctrl_stmt (stmt))
3549         {
3550           for (e = bb->succ; e; e = e->succ_next)
3551             if (e->flags & EDGE_FALLTHRU)
3552               {
3553                 error ("Fallthru edge after a control statement in bb %d \n",
3554                        bb->index);
3555                 err = 1;
3556               }
3557         }
3558
3559       switch (TREE_CODE (stmt))
3560         {
3561         case COND_EXPR:
3562           {
3563             edge true_edge;
3564             edge false_edge;
3565             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3566                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3567               {
3568                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3569                 err = 1;
3570               }
3571
3572             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3573
3574             if (!true_edge || !false_edge
3575                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3576                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3577                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3578                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3579                 || bb->succ->succ_next->succ_next)
3580               {
3581                 error ("Wrong outgoing edge flags at end of bb %d\n",
3582                        bb->index);
3583                 err = 1;
3584               }
3585
3586             if (!has_label_p (true_edge->dest,
3587                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3588               {
3589                 error ("`then' label does not match edge at end of bb %d\n",
3590                        bb->index);
3591                 err = 1;
3592               }
3593
3594             if (!has_label_p (false_edge->dest,
3595                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3596               {
3597                 error ("`else' label does not match edge at end of bb %d\n",
3598                        bb->index);
3599                 err = 1;
3600               }
3601           }
3602           break;
3603
3604         case GOTO_EXPR:
3605           if (simple_goto_p (stmt))
3606             {
3607               error ("Explicit goto at end of bb %d\n", bb->index);
3608               err = 1;
3609             }
3610           else
3611             {
3612               /* FIXME.  We should double check that the labels in the 
3613                  destination blocks have their address taken.  */
3614               for (e = bb->succ; e; e = e->succ_next)
3615                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3616                                  | EDGE_FALSE_VALUE))
3617                     || !(e->flags & EDGE_ABNORMAL))
3618                   {
3619                     error ("Wrong outgoing edge flags at end of bb %d\n",
3620                            bb->index);
3621                     err = 1;
3622                   }
3623             }
3624           break;
3625
3626         case RETURN_EXPR:
3627           if (!bb->succ || bb->succ->succ_next
3628               || (bb->succ->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3629                                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3630             {
3631               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3632               err = 1;
3633             }
3634           if (bb->succ->dest != EXIT_BLOCK_PTR)
3635             {
3636               error ("Return edge does not point to exit in bb %d\n",
3637                      bb->index);
3638               err = 1;
3639             }
3640           break;
3641
3642         case SWITCH_EXPR:
3643           {
3644             tree prev;
3645             edge e;
3646             size_t i, n;
3647             tree vec;
3648
3649             vec = SWITCH_LABELS (stmt);
3650             n = TREE_VEC_LENGTH (vec);
3651
3652             /* Mark all the destination basic blocks.  */
3653             for (i = 0; i < n; ++i)
3654               {
3655                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3656                 basic_block label_bb = label_to_block (lab);
3657
3658                 if (label_bb->aux && label_bb->aux != (void *)1)
3659                   abort ();
3660                 label_bb->aux = (void *)1;
3661               }
3662
3663             /* Verify that the case labels are sorted.  */
3664             prev = TREE_VEC_ELT (vec, 0);
3665             for (i = 1; i < n - 1; ++i)
3666               {
3667                 tree c = TREE_VEC_ELT (vec, i);
3668                 if (! CASE_LOW (c))
3669                   {
3670                     error ("Found default case not at end of case vector");
3671                     err = 1;
3672                     continue;
3673                   }
3674                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3675                   {
3676                     error ("Case labels not sorted:\n ");
3677                     print_generic_expr (stderr, prev, 0);
3678                     fprintf (stderr," is greater than ");
3679                     print_generic_expr (stderr, c, 0);
3680                     fprintf (stderr," but comes before it.\n");
3681                     err = 1;
3682                   }
3683                 prev = c;
3684               }
3685             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3686               {
3687                 error ("No default case found at end of case vector");
3688                 err = 1;
3689               }
3690
3691             for (e = bb->succ; e; e = e->succ_next)
3692               {
3693                 if (!e->dest->aux)
3694                   {
3695                     error ("Extra outgoing edge %d->%d\n",
3696                            bb->index, e->dest->index);
3697                     err = 1;
3698                   }
3699                 e->dest->aux = (void *)2;
3700                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3701                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3702                   {
3703                     error ("Wrong outgoing edge flags at end of bb %d\n",
3704                            bb->index);
3705                     err = 1;
3706                   }
3707               }
3708
3709             /* Check that we have all of them.  */
3710             for (i = 0; i < n; ++i)
3711               {
3712                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3713                 basic_block label_bb = label_to_block (lab);
3714
3715                 if (label_bb->aux != (void *)2)
3716                   {
3717                     error ("Missing edge %i->%i\n",
3718                            bb->index, label_bb->index);
3719                     err = 1;
3720                   }
3721               }
3722
3723             for (e = bb->succ; e; e = e->succ_next)
3724               e->dest->aux = (void *)0;
3725           }
3726
3727         default: ;
3728         }
3729     }
3730
3731   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3732     verify_dominators (CDI_DOMINATORS);
3733
3734   return err;
3735 }
3736
3737
3738 /* Updates phi nodes after creating forwarder block joined
3739    by edge FALLTHRU.  */
3740
3741 static void
3742 tree_make_forwarder_block (edge fallthru)
3743 {
3744   edge e;
3745   basic_block dummy, bb;
3746   tree phi, new_phi, var, prev, next;
3747
3748   dummy = fallthru->src;
3749   bb = fallthru->dest;
3750
3751   if (!bb->pred->pred_next)
3752     return;
3753
3754   /* If we redirected a branch we must create new phi nodes at the
3755      start of BB.  */
3756   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3757     {
3758       var = PHI_RESULT (phi);
3759       new_phi = create_phi_node (var, bb);
3760       SSA_NAME_DEF_STMT (var) = new_phi;
3761       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3762       add_phi_arg (&new_phi, PHI_RESULT (phi), fallthru);
3763     }
3764
3765   /* Ensure that the PHI node chain is in the same order.  */
3766   prev = NULL;
3767   for (phi = phi_nodes (bb); phi; phi = next)
3768     {
3769       next = PHI_CHAIN (phi);
3770       PHI_CHAIN (phi) = prev;
3771       prev = phi;
3772     }
3773   set_phi_nodes (bb, prev);
3774
3775   /* Add the arguments we have stored on edges.  */
3776   for (e = bb->pred; e; e = e->pred_next)
3777     {
3778       if (e == fallthru)
3779         continue;
3780
3781       for (phi = phi_nodes (bb), var = PENDING_STMT (e);
3782            phi;
3783            phi = PHI_CHAIN (phi), var = TREE_CHAIN (var))
3784         add_phi_arg (&phi, TREE_VALUE (var), e);
3785
3786       PENDING_STMT (e) = NULL;
3787     }
3788 }
3789
3790
3791 /* Return true if basic block BB does nothing except pass control
3792    flow to another block and that we can safely insert a label at
3793    the start of the successor block.  */
3794
3795 static bool
3796 tree_forwarder_block_p (basic_block bb)
3797 {
3798   block_stmt_iterator bsi;
3799   edge e;
3800
3801   /* If we have already determined that this block is not forwardable,
3802      then no further checks are necessary.  */
3803   if (! bb_ann (bb)->forwardable)
3804     return false;
3805
3806   /* BB must have a single outgoing normal edge.  Otherwise it can not be
3807      a forwarder block.  */
3808   if (!bb->succ
3809       || bb->succ->succ_next
3810       || bb->succ->dest == EXIT_BLOCK_PTR
3811       || (bb->succ->flags & EDGE_ABNORMAL)
3812       || bb == ENTRY_BLOCK_PTR)
3813     {
3814       bb_ann (bb)->forwardable = 0;
3815       return false; 
3816     }
3817
3818   /* Successors of the entry block are not forwarders.  */
3819   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
3820     if (e->dest == bb)
3821       {
3822         bb_ann (bb)->forwardable = 0;
3823         return false;
3824       }
3825
3826   /* BB can not have any PHI nodes.  This could potentially be relaxed
3827      early in compilation if we re-rewrote the variables appearing in
3828      any PHI nodes in forwarder blocks.  */
3829   if (phi_nodes (bb))
3830     {
3831       bb_ann (bb)->forwardable = 0;
3832       return false; 
3833     }
3834
3835   /* Now walk through the statements.  We can ignore labels, anything else
3836      means this is not a forwarder block.  */
3837   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3838     {
3839       tree stmt = bsi_stmt (bsi);
3840  
3841       switch (TREE_CODE (stmt))
3842         {
3843         case LABEL_EXPR:
3844           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3845             return false;
3846           break;
3847
3848         default:
3849           bb_ann (bb)->forwardable = 0;
3850           return false;
3851         }
3852     }
3853
3854   return true;
3855 }
3856
3857
3858 /* Thread jumps over empty statements.
3859
3860    This code should _not_ thread over obviously equivalent conditions
3861    as that requires nontrivial updates to the SSA graph.  */
3862    
3863 static bool
3864 thread_jumps (void)
3865 {
3866   edge e, next, last, old;
3867   basic_block bb, dest, tmp, old_dest, dom;
3868   tree phi;
3869   int arg;
3870   bool retval = false;
3871
3872   FOR_EACH_BB (bb)
3873     bb_ann (bb)->forwardable = 1;
3874
3875   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3876     {
3877       /* Don't waste time on unreachable blocks.  */
3878       if (!bb->pred)
3879         continue;
3880
3881       /* Nor on forwarders.  */
3882       if (tree_forwarder_block_p (bb))
3883         continue;
3884       
3885       /* This block is now part of a forwarding path, mark it as not
3886          forwardable so that we can detect loops.  This bit will be
3887          reset below.  */
3888       bb_ann (bb)->forwardable = 0;
3889
3890       /* Examine each of our block's successors to see if it is
3891          forwardable.  */
3892       for (e = bb->succ; e; e = next)
3893         {
3894           next = e->succ_next;
3895
3896           /* If the edge is abnormal or its destination is not
3897              forwardable, then there's nothing to do.  */
3898           if ((e->flags & EDGE_ABNORMAL)
3899               || !tree_forwarder_block_p (e->dest))
3900             continue;
3901
3902           /* Now walk through as many forwarder block as possible to
3903              find the ultimate destination we want to thread our jump
3904              to.  */
3905           last = e->dest->succ;
3906           bb_ann (e->dest)->forwardable = 0;
3907           for (dest = e->dest->succ->dest;
3908                tree_forwarder_block_p (dest);
3909                last = dest->succ,
3910                dest = dest->succ->dest)
3911             {
3912               /* An infinite loop detected.  We redirect the edge anyway, so
3913                  that the loop is shrunk into single basic block.  */
3914               if (!bb_ann (dest)->forwardable)
3915                 break;
3916
3917               if (dest->succ->dest == EXIT_BLOCK_PTR)
3918                 break;
3919
3920               bb_ann (dest)->forwardable = 0;
3921             }
3922
3923           /* Reset the forwardable marks to 1.  */
3924           for (tmp = e->dest;
3925                tmp != dest;
3926                tmp = tmp->succ->dest)
3927             bb_ann (tmp)->forwardable = 1;
3928
3929           if (dest == e->dest)
3930             continue;
3931               
3932           old = find_edge (bb, dest);
3933           if (old)
3934             {
3935               /* If there already is an edge, check whether the values
3936                  in phi nodes differ.  */
3937               if (!phi_alternatives_equal (dest, last, old))
3938                 {
3939                   /* The previous block is forwarder.  Redirect our jump
3940                      to that target instead since we know it has no PHI
3941                      nodes that will need updating.  */
3942                   dest = last->src;
3943           
3944                   /* That might mean that no forwarding at all is possible.  */
3945                   if (dest == e->dest)
3946                     continue;
3947
3948                   old = find_edge (bb, dest);
3949                 }
3950             }
3951
3952           /* Perform the redirection.  */
3953           retval = true;
3954           old_dest = e->dest;
3955           e = redirect_edge_and_branch (e, dest);
3956
3957           if (!old)
3958             {
3959               /* Update PHI nodes.   We know that the new argument should
3960                  have the same value as the argument associated with LAST.
3961                  Otherwise we would have changed our target block above.  */
3962               for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
3963                 {
3964                   arg = phi_arg_from_edge (phi, last);
3965                   if (arg < 0)
3966                     abort ();
3967                   add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
3968                 }
3969             }
3970
3971           /* Update the dominators.  */
3972           if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
3973             {
3974               /* Remove the unreachable blocks (observe that if all blocks
3975                  were reachable before, only those in the path we threaded
3976                  over and did not have any predecessor outside of the path
3977                  become unreachable).  */
3978               for (; old_dest != dest; old_dest = tmp)
3979                 {
3980                   tmp = old_dest->succ->dest;
3981
3982                   if (old_dest->pred)
3983                     break;
3984
3985                   delete_basic_block (old_dest);
3986                 }
3987               /* If the dominator of the destination was in the path, set its
3988                  dominator to the start of the redirected edge.  */
3989               if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
3990                 set_immediate_dominator (CDI_DOMINATORS, old_dest, bb);
3991
3992               /* Now proceed like if we forwarded just over one edge at a time.
3993                  Algorithm for forwarding over edge A --> B then is
3994
3995                  if (idom (B) == A)
3996                    idom (B) = idom (A);
3997                  recount_idom (A);  */
3998
3999               for (; old_dest != dest; old_dest = tmp)
4000                 {
4001                   tmp = old_dest->succ->dest;
4002
4003                   if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest)
4004                     {
4005                       dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
4006                       set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
4007                     }
4008
4009                   dom = recount_dominator (CDI_DOMINATORS, old_dest);
4010                   set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
4011                 }
4012             }
4013         }
4014
4015       /* Reset the forwardable bit on our block since it's no longer in
4016          a forwarding chain path.  */
4017       bb_ann (bb)->forwardable = 1;
4018     }
4019
4020   return retval;
4021 }
4022
4023
4024 /* Return a non-special label in the head of basic block BLOCK.
4025    Create one if it doesn't exist.  */
4026
4027 tree
4028 tree_block_label (basic_block bb)
4029 {
4030   block_stmt_iterator i, s = bsi_start (bb);
4031   bool first = true;
4032   tree label, stmt;
4033
4034   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4035     {
4036       stmt = bsi_stmt (i);
4037       if (TREE_CODE (stmt) != LABEL_EXPR)
4038         break;
4039       label = LABEL_EXPR_LABEL (stmt);
4040       if (!DECL_NONLOCAL (label))
4041         {
4042           if (!first)
4043             bsi_move_before (&i, &s);
4044           return label;
4045         }
4046     }
4047
4048   label = create_artificial_label ();
4049   stmt = build1 (LABEL_EXPR, void_type_node, label);
4050   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4051   return label;
4052 }
4053
4054
4055 /* Attempt to perform edge redirection by replacing a possibly complex
4056    jump instruction by a goto or by removing the jump completely.
4057    This can apply only if all edges now point to the same block.  The
4058    parameters and return values are equivalent to
4059    redirect_edge_and_branch.  */
4060
4061 static edge
4062 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4063 {
4064   basic_block src = e->src;
4065   edge tmp;
4066   block_stmt_iterator b;
4067   tree stmt;
4068
4069   /* Verify that all targets will be TARGET.  */
4070   for (tmp = src->succ; tmp; tmp = tmp->succ_next)
4071     if (tmp->dest != target && tmp != e)
4072       break;
4073
4074   if (tmp)
4075     return NULL;
4076
4077   b = bsi_last (src);
4078   if (bsi_end_p (b))
4079     return NULL;
4080   stmt = bsi_stmt (b);
4081
4082   if (TREE_CODE (stmt) == COND_EXPR
4083       || TREE_CODE (stmt) == SWITCH_EXPR)
4084     {
4085       bsi_remove (&b);
4086       e = ssa_redirect_edge (e, target);
4087       e->flags = EDGE_FALLTHRU;
4088       return e;
4089     }
4090
4091   return NULL;
4092 }
4093
4094
4095 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4096    edge representing the redirected branch.  */
4097
4098 static edge
4099 tree_redirect_edge_and_branch (edge e, basic_block dest)
4100 {
4101   basic_block bb = e->src;
4102   block_stmt_iterator bsi;
4103   edge ret;
4104   tree label, stmt;
4105
4106   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4107     return NULL;
4108
4109   if (e->src != ENTRY_BLOCK_PTR 
4110       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4111     return ret;
4112
4113   if (e->dest == dest)
4114     return NULL;
4115
4116   label = tree_block_label (dest);
4117
4118   bsi = bsi_last (bb);
4119   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4120
4121   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4122     {
4123     case COND_EXPR:
4124       stmt = (e->flags & EDGE_TRUE_VALUE
4125               ? COND_EXPR_THEN (stmt)
4126               : COND_EXPR_ELSE (stmt));
4127       GOTO_DESTINATION (stmt) = label;
4128       break;
4129
4130     case GOTO_EXPR:
4131       /* No non-abnormal edges should lead from a non-simple goto, and
4132          simple ones should be represented implicitly.  */
4133       abort ();
4134
4135     case SWITCH_EXPR:
4136       {
4137         tree vec = SWITCH_LABELS (stmt);
4138         size_t i, n = TREE_VEC_LENGTH (vec);
4139
4140         for (i = 0; i < n; ++i)
4141           {
4142             tree elt = TREE_VEC_ELT (vec, i);
4143             if (label_to_block (CASE_LABEL (elt)) == e->dest)
4144               CASE_LABEL (elt) = label;
4145           }
4146       }
4147       break;
4148
4149     case RETURN_EXPR:
4150       bsi_remove (&bsi);
4151       e->flags |= EDGE_FALLTHRU;
4152       break;
4153
4154     default:
4155       /* Otherwise it must be a fallthru edge, and we don't need to
4156          do anything besides redirecting it.  */
4157       if (!(e->flags & EDGE_FALLTHRU))
4158         abort ();
4159       break;
4160     }
4161
4162   /* Update/insert PHI nodes as necessary.  */
4163
4164   /* Now update the edges in the CFG.  */
4165   e = ssa_redirect_edge (e, dest);
4166
4167   return e;
4168 }
4169
4170
4171 /* Simple wrapper, as we can always redirect fallthru edges.  */
4172
4173 static basic_block
4174 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4175 {
4176   e = tree_redirect_edge_and_branch (e, dest);
4177   if (!e)
4178     abort ();
4179
4180   return NULL;
4181 }
4182
4183
4184 /* Splits basic block BB after statement STMT (but at least after the
4185    labels).  If STMT is NULL, BB is split just after the labels.  */
4186
4187 static basic_block
4188 tree_split_block (basic_block bb, void *stmt)
4189 {
4190   block_stmt_iterator bsi, bsi_tgt;
4191   tree act;
4192   basic_block new_bb;
4193   edge e;
4194
4195   new_bb = create_empty_bb (bb);
4196
4197   /* Redirect the outgoing edges.  */
4198   new_bb->succ = bb->succ;
4199   bb->succ = NULL;
4200   for (e = new_bb->succ; e; e = e->succ_next)
4201     e->src = new_bb;
4202
4203   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4204     stmt = NULL;
4205
4206   /* Move everything from BSI to the new basic block.  */
4207   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4208     {
4209       act = bsi_stmt (bsi);
4210       if (TREE_CODE (act) == LABEL_EXPR)
4211         continue;
4212
4213       if (!stmt)
4214         break;
4215
4216       if (stmt == act)
4217         {
4218           bsi_next (&bsi);
4219           break;
4220         }
4221     }
4222
4223   bsi_tgt = bsi_start (new_bb);
4224   while (!bsi_end_p (bsi))
4225     {
4226       act = bsi_stmt (bsi);
4227       bsi_remove (&bsi);
4228       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4229     }
4230
4231   return new_bb;
4232 }
4233
4234
4235 /* Moves basic block BB after block AFTER.  */
4236
4237 static bool
4238 tree_move_block_after (basic_block bb, basic_block after)
4239 {
4240   if (bb->prev_bb == after)
4241     return true;
4242
4243   unlink_block (bb);
4244   link_block (bb, after);
4245
4246   return true;
4247 }
4248
4249
4250 /* Return true if basic_block can be duplicated.  */
4251
4252 static bool
4253 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4254 {
4255   return true;
4256 }
4257
4258
4259 /* Create a duplicate of the basic block BB.  NOTE: This does not
4260    preserve SSA form.  */
4261
4262 static basic_block
4263 tree_duplicate_bb (basic_block bb)
4264 {
4265   basic_block new_bb;
4266   block_stmt_iterator bsi, bsi_tgt;
4267   tree phi, val;
4268   ssa_op_iter op_iter;
4269
4270   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4271
4272   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
4273     {
4274       mark_for_rewrite (PHI_RESULT (phi));
4275     }
4276
4277   bsi_tgt = bsi_start (new_bb);
4278   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4279     {
4280       tree stmt = bsi_stmt (bsi);
4281       tree copy;
4282
4283       if (TREE_CODE (stmt) == LABEL_EXPR)
4284         continue;
4285
4286       /* Record the definitions.  */
4287       get_stmt_operands (stmt);
4288
4289       FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
4290         mark_for_rewrite (val);
4291
4292       copy = unshare_expr (stmt);
4293
4294       /* Copy also the virtual operands.  */
4295       get_stmt_ann (copy);
4296       copy_virtual_operands (copy, stmt);
4297       
4298       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4299     }
4300
4301   return new_bb;
4302 }
4303
4304
4305 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4306
4307 void
4308 dump_function_to_file (tree fn, FILE *file, int flags)
4309 {
4310   tree arg, vars, var;
4311   bool ignore_topmost_bind = false, any_var = false;
4312   basic_block bb;
4313   tree chain;
4314
4315   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4316
4317   arg = DECL_ARGUMENTS (fn);
4318   while (arg)
4319     {
4320       print_generic_expr (file, arg, dump_flags);
4321       if (TREE_CHAIN (arg))
4322         fprintf (file, ", ");
4323       arg = TREE_CHAIN (arg);
4324     }
4325   fprintf (file, ")\n");
4326
4327   if (flags & TDF_RAW)
4328     {
4329       dump_node (fn, TDF_SLIM | flags, file);
4330       return;
4331     }
4332
4333   /* When GIMPLE is lowered, the variables are no longer available in
4334      BIND_EXPRs, so display them separately.  */
4335   if (cfun && cfun->unexpanded_var_list)
4336     {
4337       ignore_topmost_bind = true;
4338
4339       fprintf (file, "{\n");
4340       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4341         {
4342           var = TREE_VALUE (vars);
4343
4344           print_generic_decl (file, var, flags);
4345           fprintf (file, "\n");
4346
4347           any_var = true;
4348         }
4349     }
4350
4351   if (basic_block_info)
4352     {
4353       /* Make a CFG based dump.  */
4354       check_bb_profile (ENTRY_BLOCK_PTR, file);
4355       if (!ignore_topmost_bind)
4356         fprintf (file, "{\n");
4357
4358       if (any_var && n_basic_blocks)