OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[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   gcc_assert (!bb->tree_annotations);
298   bb->tree_annotations = ggc_alloc_cleared (sizeof (struct bb_ann_d));
299 }
300
301
302 /* Free the annotations for all the basic blocks.  */
303
304 static void free_blocks_annotations (void)
305 {
306   clear_blocks_annotations ();  
307 }
308
309
310 /* Clear the annotations for all the basic blocks.  */
311
312 static void
313 clear_blocks_annotations (void)
314 {
315   basic_block bb;
316
317   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
318     bb->tree_annotations = NULL;
319 }
320
321
322 /* Build a flowgraph for the statement_list STMT_LIST.  */
323
324 static void
325 make_blocks (tree stmt_list)
326 {
327   tree_stmt_iterator i = tsi_start (stmt_list);
328   tree stmt = NULL;
329   bool start_new_block = true;
330   bool first_stmt_of_list = true;
331   basic_block bb = ENTRY_BLOCK_PTR;
332
333   while (!tsi_end_p (i))
334     {
335       tree prev_stmt;
336
337       prev_stmt = stmt;
338       stmt = tsi_stmt (i);
339
340       /* If the statement starts a new basic block or if we have determined
341          in a previous pass that we need to create a new block for STMT, do
342          so now.  */
343       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
344         {
345           if (!first_stmt_of_list)
346             stmt_list = tsi_split_statement_list_before (&i);
347           bb = create_basic_block (stmt_list, NULL, bb);
348           start_new_block = false;
349         }
350
351       /* Now add STMT to BB and create the subgraphs for special statement
352          codes.  */
353       set_bb_for_stmt (stmt, bb);
354
355       if (computed_goto_p (stmt))
356         found_computed_goto = true;
357
358       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
359          next iteration.  */
360       if (stmt_ends_bb_p (stmt))
361         start_new_block = true;
362
363       tsi_next (&i);
364       first_stmt_of_list = false;
365     }
366 }
367
368
369 /* Create and return a new empty basic block after bb AFTER.  */
370
371 static basic_block
372 create_bb (void *h, void *e, basic_block after)
373 {
374   basic_block bb;
375
376   gcc_assert (!e);
377
378   /* Create and initialize a new basic block.  */
379   bb = alloc_block ();
380   memset (bb, 0, sizeof (*bb));
381
382   bb->index = last_basic_block;
383   bb->flags = BB_NEW;
384   bb->stmt_list = h ? h : alloc_stmt_list ();
385
386   /* Add the new block to the linked list of blocks.  */
387   link_block (bb, after);
388
389   /* Grow the basic block array if needed.  */
390   if ((size_t) last_basic_block == VARRAY_SIZE (basic_block_info))
391     {
392       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
393       VARRAY_GROW (basic_block_info, new_size);
394     }
395
396   /* Add the newly created block to the array.  */
397   BASIC_BLOCK (last_basic_block) = bb;
398
399   create_block_annotation (bb);
400
401   n_basic_blocks++;
402   last_basic_block++;
403
404   initialize_bb_rbi (bb);
405   return bb;
406 }
407
408
409 /*---------------------------------------------------------------------------
410                                  Edge creation
411 ---------------------------------------------------------------------------*/
412
413 /* Join all the blocks in the flowgraph.  */
414
415 static void
416 make_edges (void)
417 {
418   basic_block bb;
419
420   /* Create an edge from entry to the first block with executable
421      statements in it.  */
422   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
423
424   /* Traverse basic block array placing edges.  */
425   FOR_EACH_BB (bb)
426     {
427       tree first = first_stmt (bb);
428       tree last = last_stmt (bb);
429
430       if (first)
431         {
432           /* Edges for statements that always alter flow control.  */
433           if (is_ctrl_stmt (last))
434             make_ctrl_stmt_edges (bb);
435
436           /* Edges for statements that sometimes alter flow control.  */
437           if (is_ctrl_altering_stmt (last))
438             make_exit_edges (bb);
439         }
440
441       /* Finally, if no edges were created above, this is a regular
442          basic block that only needs a fallthru edge.  */
443       if (bb->succ == NULL)
444         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
445     }
446
447   /* We do not care about fake edges, so remove any that the CFG
448      builder inserted for completeness.  */
449   remove_fake_exit_edges ();
450
451   /* Clean up the graph and warn for unreachable code.  */
452   cleanup_tree_cfg ();
453 }
454
455
456 /* Create edges for control statement at basic block BB.  */
457
458 static void
459 make_ctrl_stmt_edges (basic_block bb)
460 {
461   tree last = last_stmt (bb);
462
463   gcc_assert (last);
464   switch (TREE_CODE (last))
465     {
466     case GOTO_EXPR:
467       make_goto_expr_edges (bb);
468       break;
469
470     case RETURN_EXPR:
471       make_edge (bb, EXIT_BLOCK_PTR, 0);
472       break;
473
474     case COND_EXPR:
475       make_cond_expr_edges (bb);
476       break;
477
478     case SWITCH_EXPR:
479       make_switch_expr_edges (bb);
480       break;
481
482     case RESX_EXPR:
483       make_eh_edges (last);
484       /* Yet another NORETURN hack.  */
485       if (bb->succ == NULL)
486         make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
487       break;
488
489     default:
490       gcc_unreachable ();
491     }
492 }
493
494
495 /* Create exit edges for statements in block BB that alter the flow of
496    control.  Statements that alter the control flow are 'goto', 'return'
497    and calls to non-returning functions.  */
498
499 static void
500 make_exit_edges (basic_block bb)
501 {
502   tree last = last_stmt (bb), op;
503
504   gcc_assert (last);
505   switch (TREE_CODE (last))
506     {
507     case CALL_EXPR:
508       /* If this function receives a nonlocal goto, then we need to
509          make edges from this call site to all the nonlocal goto
510          handlers.  */
511       if (TREE_SIDE_EFFECTS (last)
512           && current_function_has_nonlocal_label)
513         make_goto_expr_edges (bb);
514
515       /* If this statement has reachable exception handlers, then
516          create abnormal edges to them.  */
517       make_eh_edges (last);
518
519       /* Some calls are known not to return.  For such calls we create
520          a fake edge.
521
522          We really need to revamp how we build edges so that it's not
523          such a bloody pain to avoid creating edges for this case since
524          all we do is remove these edges when we're done building the
525          CFG.  */
526       if (call_expr_flags (last) & (ECF_NORETURN | ECF_LONGJMP))
527         {
528           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
529           return;
530         }
531
532       /* Don't forget the fall-thru edge.  */
533       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
534       break;
535
536     case MODIFY_EXPR:
537       /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
538          may have an abnormal edge.  Search the RHS for this case and
539          create any required edges.  */
540       op = get_call_expr_in (last);
541       if (op && TREE_SIDE_EFFECTS (op)
542           && current_function_has_nonlocal_label)
543         make_goto_expr_edges (bb);
544
545       make_eh_edges (last);
546       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
547       break;
548
549     default:
550       gcc_unreachable ();
551     }
552 }
553
554
555 /* Create the edges for a COND_EXPR starting at block BB.
556    At this point, both clauses must contain only simple gotos.  */
557
558 static void
559 make_cond_expr_edges (basic_block bb)
560 {
561   tree entry = last_stmt (bb);
562   basic_block then_bb, else_bb;
563   tree then_label, else_label;
564
565   gcc_assert (entry);
566   gcc_assert (TREE_CODE (entry) == COND_EXPR);
567
568   /* Entry basic blocks for each component.  */
569   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
570   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
571   then_bb = label_to_block (then_label);
572   else_bb = label_to_block (else_label);
573
574   make_edge (bb, then_bb, EDGE_TRUE_VALUE);
575   make_edge (bb, else_bb, EDGE_FALSE_VALUE);
576 }
577
578
579 /* Create the edges for a SWITCH_EXPR starting at block BB.
580    At this point, the switch body has been lowered and the
581    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
582
583 static void
584 make_switch_expr_edges (basic_block bb)
585 {
586   tree entry = last_stmt (bb);
587   size_t i, n;
588   tree vec;
589
590   vec = SWITCH_LABELS (entry);
591   n = TREE_VEC_LENGTH (vec);
592
593   for (i = 0; i < n; ++i)
594     {
595       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
596       basic_block label_bb = label_to_block (lab);
597       make_edge (bb, label_bb, 0);
598     }
599 }
600
601
602 /* Return the basic block holding label DEST.  */
603
604 basic_block
605 label_to_block (tree dest)
606 {
607   int uid = LABEL_DECL_UID (dest);
608
609   /* We would die hard when faced by undefined label.  Emit label to
610      very first basic block.  This will hopefully make even the dataflow
611      and undefined variable warnings quite right.  */
612   if ((errorcount || sorrycount) && uid < 0)
613     {
614       block_stmt_iterator bsi = bsi_start (BASIC_BLOCK (0));
615       tree stmt;
616
617       stmt = build1 (LABEL_EXPR, void_type_node, dest);
618       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
619       uid = LABEL_DECL_UID (dest);
620     }
621   return VARRAY_BB (label_to_block_map, uid);
622 }
623
624
625 /* Create edges for a goto statement at block BB.  */
626
627 static void
628 make_goto_expr_edges (basic_block bb)
629 {
630   tree goto_t, dest;
631   basic_block target_bb;
632   int for_call;
633   block_stmt_iterator last = bsi_last (bb);
634
635   goto_t = bsi_stmt (last);
636
637   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
638      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
639      from a nonlocal goto.  */
640   if (TREE_CODE (goto_t) != GOTO_EXPR)
641     {
642       dest = error_mark_node;
643       for_call = 1;
644     }
645   else
646     {
647       dest = GOTO_DESTINATION (goto_t);
648       for_call = 0;
649
650       /* A GOTO to a local label creates normal edges.  */
651       if (simple_goto_p (goto_t))
652         {
653           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
654 #ifdef USE_MAPPED_LOCATION
655           e->goto_locus = EXPR_LOCATION (goto_t);
656 #else
657           e->goto_locus = EXPR_LOCUS (goto_t);
658 #endif
659           bsi_remove (&last);
660           return;
661         }
662
663       /* Nothing more to do for nonlocal gotos.  */
664       if (TREE_CODE (dest) == LABEL_DECL)
665         return;
666
667       /* Computed gotos remain.  */
668     }
669
670   /* Look for the block starting with the destination label.  In the
671      case of a computed goto, make an edge to any label block we find
672      in the CFG.  */
673   FOR_EACH_BB (target_bb)
674     {
675       block_stmt_iterator bsi;
676
677       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
678         {
679           tree target = bsi_stmt (bsi);
680
681           if (TREE_CODE (target) != LABEL_EXPR)
682             break;
683
684           if (
685               /* Computed GOTOs.  Make an edge to every label block that has
686                  been marked as a potential target for a computed goto.  */
687               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && for_call == 0)
688               /* Nonlocal GOTO target.  Make an edge to every label block
689                  that has been marked as a potential target for a nonlocal
690                  goto.  */
691               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call == 1))
692             {
693               make_edge (bb, target_bb, EDGE_ABNORMAL);
694               break;
695             }
696         }
697     }
698
699   /* Degenerate case of computed goto with no labels.  */
700   if (!for_call && !bb->succ)
701     make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
702 }
703
704
705 /*---------------------------------------------------------------------------
706                                Flowgraph analysis
707 ---------------------------------------------------------------------------*/
708
709 /* Remove unreachable blocks and other miscellaneous clean up work.  */
710
711 bool
712 cleanup_tree_cfg (void)
713 {
714   bool something_changed = true;
715   bool retval = false;
716
717   timevar_push (TV_TREE_CLEANUP_CFG);
718
719   /* These three transformations can cascade, so we iterate on them until
720      nothing changes.  */
721   while (something_changed)
722     {
723       something_changed = cleanup_control_flow ();
724       something_changed |= delete_unreachable_blocks ();
725       something_changed |= thread_jumps ();
726       retval |= something_changed;
727     }
728
729   /* Merging the blocks creates no new opportunities for the other
730      optimizations, so do it here.  */
731   merge_seq_blocks ();
732
733   compact_blocks ();
734
735 #ifdef ENABLE_CHECKING
736   verify_flow_info ();
737 #endif
738   timevar_pop (TV_TREE_CLEANUP_CFG);
739   return retval;
740 }
741
742
743 /* Cleanup useless labels in basic blocks.  This is something we wish
744    to do early because it allows us to group case labels before creating
745    the edges for the CFG, and it speeds up block statement iterators in
746    all passes later on.
747    We only run this pass once, running it more than once is probably not
748    profitable.  */
749
750 /* A map from basic block index to the leading label of that block.  */
751 static tree *label_for_bb;
752
753 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
754 static void
755 update_eh_label (struct eh_region *region)
756 {
757   tree old_label = get_eh_region_tree_label (region);
758   if (old_label)
759     {
760       tree new_label;
761       basic_block bb = label_to_block (old_label);
762
763       /* ??? After optimizing, there may be EH regions with labels
764          that have already been removed from the function body, so
765          there is no basic block for them.  */
766       if (! bb)
767         return;
768
769       new_label = label_for_bb[bb->index];
770       set_eh_region_tree_label (region, new_label);
771     }
772 }
773
774 /* Given LABEL return the first label in the same basic block.  */
775 static tree
776 main_block_label (tree label)
777 {
778   basic_block bb = label_to_block (label);
779
780   /* label_to_block possibly inserted undefined label into the chain.  */
781   if (!label_for_bb[bb->index])
782     label_for_bb[bb->index] = label;
783   return label_for_bb[bb->index];
784 }
785
786 /* Cleanup redundant labels.  This is a three-steo process:
787      1) Find the leading label for each block.
788      2) Redirect all references to labels to the leading labels.
789      3) Cleanup all useless labels.  */
790
791 void
792 cleanup_dead_labels (void)
793 {
794   basic_block bb;
795   label_for_bb = xcalloc (last_basic_block, sizeof (tree));
796
797   /* Find a suitable label for each block.  We use the first user-defined
798      label is there is one, or otherwise just the first label we see.  */
799   FOR_EACH_BB (bb)
800     {
801       block_stmt_iterator i;
802
803       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
804         {
805           tree label, stmt = bsi_stmt (i);
806
807           if (TREE_CODE (stmt) != LABEL_EXPR)
808             break;
809
810           label = LABEL_EXPR_LABEL (stmt);
811
812           /* If we have not yet seen a label for the current block,
813              remember this one and see if there are more labels.  */
814           if (! label_for_bb[bb->index])
815             {
816               label_for_bb[bb->index] = label;
817               continue;
818             }
819
820           /* If we did see a label for the current block already, but it
821              is an artificially created label, replace it if the current
822              label is a user defined label.  */
823           if (! DECL_ARTIFICIAL (label)
824               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
825             {
826               label_for_bb[bb->index] = label;
827               break;
828             }
829         }
830     }
831
832   /* Now redirect all jumps/branches to the selected label.
833      First do so for each block ending in a control statement.  */
834   FOR_EACH_BB (bb)
835     {
836       tree stmt = last_stmt (bb);
837       if (!stmt)
838         continue;
839
840       switch (TREE_CODE (stmt))
841         {
842         case COND_EXPR:
843           {
844             tree true_branch, false_branch;
845
846             true_branch = COND_EXPR_THEN (stmt);
847             false_branch = COND_EXPR_ELSE (stmt);
848
849             GOTO_DESTINATION (true_branch)
850               = main_block_label (GOTO_DESTINATION (true_branch));
851             GOTO_DESTINATION (false_branch)
852               = main_block_label (GOTO_DESTINATION (false_branch));
853
854             break;
855           }
856   
857         case SWITCH_EXPR:
858           {
859             size_t i;
860             tree vec = SWITCH_LABELS (stmt);
861             size_t n = TREE_VEC_LENGTH (vec);
862   
863             /* Replace all destination labels.  */
864             for (i = 0; i < n; ++i)
865               CASE_LABEL (TREE_VEC_ELT (vec, i))
866                 = main_block_label (CASE_LABEL (TREE_VEC_ELT (vec, i)));
867   
868             break;
869           }
870
871         /* We have to handle GOTO_EXPRs until they're removed, and we don't
872            remove them until after we've created the CFG edges.  */
873         case GOTO_EXPR:
874           if (! computed_goto_p (stmt))
875             {
876               GOTO_DESTINATION (stmt)
877                 = main_block_label (GOTO_DESTINATION (stmt));
878               break;
879             }
880
881         default:
882           break;
883       }
884     }
885
886   for_each_eh_region (update_eh_label);
887
888   /* Finally, purge dead labels.  All user-defined labels and labels that
889      can be the target of non-local gotos are preserved.  */
890   FOR_EACH_BB (bb)
891     {
892       block_stmt_iterator i;
893       tree label_for_this_bb = label_for_bb[bb->index];
894
895       if (! label_for_this_bb)
896         continue;
897
898       for (i = bsi_start (bb); !bsi_end_p (i); )
899         {
900           tree label, stmt = bsi_stmt (i);
901
902           if (TREE_CODE (stmt) != LABEL_EXPR)
903             break;
904
905           label = LABEL_EXPR_LABEL (stmt);
906
907           if (label == label_for_this_bb
908               || ! DECL_ARTIFICIAL (label)
909               || DECL_NONLOCAL (label))
910             bsi_next (&i);
911           else
912             bsi_remove (&i);
913         }
914     }
915
916   free (label_for_bb);
917 }
918
919 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
920    and scan the sorted vector of cases.  Combine the ones jumping to the
921    same label.
922    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
923
924 void
925 group_case_labels (void)
926 {
927   basic_block bb;
928
929   FOR_EACH_BB (bb)
930     {
931       tree stmt = last_stmt (bb);
932       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
933         {
934           tree labels = SWITCH_LABELS (stmt);
935           int old_size = TREE_VEC_LENGTH (labels);
936           int i, j, new_size = old_size;
937           tree default_label = TREE_VEC_ELT (labels, old_size - 1);
938
939           /* Look for possible opportunities to merge cases.
940              Ignore the last element of the label vector because it
941              must be the default case.  */
942           i = 0;
943           while (i < old_size - 2)
944             {
945               tree base_case, base_label, base_high, type;
946               base_case = TREE_VEC_ELT (labels, i);
947
948               gcc_assert (base_case);
949               base_label = CASE_LABEL (base_case);
950
951               /* Discard cases that have the same destination as the
952                  default case.  */
953               if (base_label == default_label)
954                 {
955                   TREE_VEC_ELT (labels, i) = NULL_TREE;
956                   i++;
957                   continue;
958                 }
959
960               type = TREE_TYPE (CASE_LOW (base_case));
961               base_high = CASE_HIGH (base_case) ?
962                 CASE_HIGH (base_case) : CASE_LOW (base_case);
963
964               /* Try to merge case labels.  Break out when we reach the end
965                  of the label vector or when we cannot merge the next case
966                  label with the current one.  */
967               while (i < old_size - 2)
968                 {
969                   tree merge_case = TREE_VEC_ELT (labels, ++i);
970                   tree merge_label = CASE_LABEL (merge_case);
971                   tree t = int_const_binop (PLUS_EXPR, base_high,
972                                             integer_one_node, 1);
973
974                   /* Merge the cases if they jump to the same place,
975                      and their ranges are consecutive.  */
976                   if (merge_label == base_label
977                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
978                     {
979                       base_high = CASE_HIGH (merge_case) ?
980                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
981                       CASE_HIGH (base_case) = base_high;
982                       TREE_VEC_ELT (labels, i) = NULL_TREE;
983                       new_size--;
984                     }
985                   else
986                     break;
987                 }
988             }
989
990           /* Compress the case labels in the label vector, and adjust the
991              length of the vector.  */
992           for (i = 0, j = 0; i < new_size; i++)
993             {
994               while (! TREE_VEC_ELT (labels, j))
995                 j++;
996               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
997             }
998           TREE_VEC_LENGTH (labels) = new_size;
999         }
1000     }
1001 }
1002
1003 /* Checks whether we can merge block B into block A.  */
1004
1005 static bool
1006 tree_can_merge_blocks_p (basic_block a, basic_block b)
1007 {
1008   tree stmt;
1009   block_stmt_iterator bsi;
1010
1011   if (!a->succ
1012       || a->succ->succ_next)
1013     return false;
1014
1015   if (a->succ->flags & EDGE_ABNORMAL)
1016     return false;
1017
1018   if (a->succ->dest != b)
1019     return false;
1020
1021   if (b == EXIT_BLOCK_PTR)
1022     return false;
1023   
1024   if (b->pred->pred_next)
1025     return false;
1026
1027   /* If A ends by a statement causing exceptions or something similar, we
1028      cannot merge the blocks.  */
1029   stmt = last_stmt (a);
1030   if (stmt && stmt_ends_bb_p (stmt))
1031     return false;
1032
1033   /* Do not allow a block with only a non-local label to be merged.  */
1034   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1035       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1036     return false;
1037
1038   /* There may be no phi nodes at the start of b.  Most of these degenerate
1039      phi nodes should be cleaned up by kill_redundant_phi_nodes.  */
1040   if (phi_nodes (b))
1041     return false;
1042
1043   /* Do not remove user labels.  */
1044   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1045     {
1046       stmt = bsi_stmt (bsi);
1047       if (TREE_CODE (stmt) != LABEL_EXPR)
1048         break;
1049       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1050         return false;
1051     }
1052
1053   return true;
1054 }
1055
1056
1057 /* Merge block B into block A.  */
1058
1059 static void
1060 tree_merge_blocks (basic_block a, basic_block b)
1061 {
1062   block_stmt_iterator bsi;
1063   tree_stmt_iterator last;
1064
1065   if (dump_file)
1066     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1067
1068   /* Ensure that B follows A.  */
1069   move_block_after (b, a);
1070
1071   gcc_assert (a->succ->flags & EDGE_FALLTHRU);
1072   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1073
1074   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1075   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1076     {
1077       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1078         bsi_remove (&bsi);
1079       else
1080         {
1081           set_bb_for_stmt (bsi_stmt (bsi), a);
1082           bsi_next (&bsi);
1083         }
1084     }
1085
1086   /* Merge the chains.  */
1087   last = tsi_last (a->stmt_list);
1088   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1089   b->stmt_list = NULL;
1090 }
1091
1092
1093 /* Walk the function tree removing unnecessary statements.
1094
1095      * Empty statement nodes are removed
1096
1097      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1098
1099      * Unnecessary COND_EXPRs are removed
1100
1101      * Some unnecessary BIND_EXPRs are removed
1102
1103    Clearly more work could be done.  The trick is doing the analysis
1104    and removal fast enough to be a net improvement in compile times.
1105
1106    Note that when we remove a control structure such as a COND_EXPR
1107    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1108    to ensure we eliminate all the useless code.  */
1109
1110 struct rus_data
1111 {
1112   tree *last_goto;
1113   bool repeat;
1114   bool may_throw;
1115   bool may_branch;
1116   bool has_label;
1117 };
1118
1119 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1120
1121 static bool
1122 remove_useless_stmts_warn_notreached (tree stmt)
1123 {
1124   if (EXPR_HAS_LOCATION (stmt))
1125     {
1126       location_t loc = EXPR_LOCATION (stmt);
1127       warning ("%Hwill never be executed", &loc);
1128       return true;
1129     }
1130
1131   switch (TREE_CODE (stmt))
1132     {
1133     case STATEMENT_LIST:
1134       {
1135         tree_stmt_iterator i;
1136         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1137           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1138             return true;
1139       }
1140       break;
1141
1142     case COND_EXPR:
1143       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1144         return true;
1145       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1146         return true;
1147       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1148         return true;
1149       break;
1150
1151     case TRY_FINALLY_EXPR:
1152     case TRY_CATCH_EXPR:
1153       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1154         return true;
1155       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1156         return true;
1157       break;
1158
1159     case CATCH_EXPR:
1160       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1161     case EH_FILTER_EXPR:
1162       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1163     case BIND_EXPR:
1164       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1165
1166     default:
1167       /* Not a live container.  */
1168       break;
1169     }
1170
1171   return false;
1172 }
1173
1174 static void
1175 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1176 {
1177   tree then_clause, else_clause, cond;
1178   bool save_has_label, then_has_label, else_has_label;
1179
1180   save_has_label = data->has_label;
1181   data->has_label = false;
1182   data->last_goto = NULL;
1183
1184   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1185
1186   then_has_label = data->has_label;
1187   data->has_label = false;
1188   data->last_goto = NULL;
1189
1190   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1191
1192   else_has_label = data->has_label;
1193   data->has_label = save_has_label | then_has_label | else_has_label;
1194
1195   fold_stmt (stmt_p);
1196   then_clause = COND_EXPR_THEN (*stmt_p);
1197   else_clause = COND_EXPR_ELSE (*stmt_p);
1198   cond = COND_EXPR_COND (*stmt_p);
1199
1200   /* If neither arm does anything at all, we can remove the whole IF.  */
1201   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1202     {
1203       *stmt_p = build_empty_stmt ();
1204       data->repeat = true;
1205     }
1206
1207   /* If there are no reachable statements in an arm, then we can
1208      zap the entire conditional.  */
1209   else if (integer_nonzerop (cond) && !else_has_label)
1210     {
1211       if (warn_notreached)
1212         remove_useless_stmts_warn_notreached (else_clause);
1213       *stmt_p = then_clause;
1214       data->repeat = true;
1215     }
1216   else if (integer_zerop (cond) && !then_has_label)
1217     {
1218       if (warn_notreached)
1219         remove_useless_stmts_warn_notreached (then_clause);
1220       *stmt_p = else_clause;
1221       data->repeat = true;
1222     }
1223
1224   /* Check a couple of simple things on then/else with single stmts.  */
1225   else
1226     {
1227       tree then_stmt = expr_only (then_clause);
1228       tree else_stmt = expr_only (else_clause);
1229
1230       /* Notice branches to a common destination.  */
1231       if (then_stmt && else_stmt
1232           && TREE_CODE (then_stmt) == GOTO_EXPR
1233           && TREE_CODE (else_stmt) == GOTO_EXPR
1234           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1235         {
1236           *stmt_p = then_stmt;
1237           data->repeat = true;
1238         }
1239
1240       /* If the THEN/ELSE clause merely assigns a value to a variable or
1241          parameter which is already known to contain that value, then
1242          remove the useless THEN/ELSE clause.  */
1243       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1244         {
1245           if (else_stmt
1246               && TREE_CODE (else_stmt) == MODIFY_EXPR
1247               && TREE_OPERAND (else_stmt, 0) == cond
1248               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1249             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1250         }
1251       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1252                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1253                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1254                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1255         {
1256           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1257                        ? then_stmt : else_stmt);
1258           tree *location = (TREE_CODE (cond) == EQ_EXPR
1259                             ? &COND_EXPR_THEN (*stmt_p)
1260                             : &COND_EXPR_ELSE (*stmt_p));
1261
1262           if (stmt
1263               && TREE_CODE (stmt) == MODIFY_EXPR
1264               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1265               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1266             *location = alloc_stmt_list ();
1267         }
1268     }
1269
1270   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1271      would be re-introduced during lowering.  */
1272   data->last_goto = NULL;
1273 }
1274
1275
1276 static void
1277 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1278 {
1279   bool save_may_branch, save_may_throw;
1280   bool this_may_branch, this_may_throw;
1281
1282   /* Collect may_branch and may_throw information for the body only.  */
1283   save_may_branch = data->may_branch;
1284   save_may_throw = data->may_throw;
1285   data->may_branch = false;
1286   data->may_throw = false;
1287   data->last_goto = NULL;
1288
1289   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1290
1291   this_may_branch = data->may_branch;
1292   this_may_throw = data->may_throw;
1293   data->may_branch |= save_may_branch;
1294   data->may_throw |= save_may_throw;
1295   data->last_goto = NULL;
1296
1297   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1298
1299   /* If the body is empty, then we can emit the FINALLY block without
1300      the enclosing TRY_FINALLY_EXPR.  */
1301   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1302     {
1303       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1304       data->repeat = true;
1305     }
1306
1307   /* If the handler is empty, then we can emit the TRY block without
1308      the enclosing TRY_FINALLY_EXPR.  */
1309   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1310     {
1311       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1312       data->repeat = true;
1313     }
1314
1315   /* If the body neither throws, nor branches, then we can safely
1316      string the TRY and FINALLY blocks together.  */
1317   else if (!this_may_branch && !this_may_throw)
1318     {
1319       tree stmt = *stmt_p;
1320       *stmt_p = TREE_OPERAND (stmt, 0);
1321       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1322       data->repeat = true;
1323     }
1324 }
1325
1326
1327 static void
1328 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1329 {
1330   bool save_may_throw, this_may_throw;
1331   tree_stmt_iterator i;
1332   tree stmt;
1333
1334   /* Collect may_throw information for the body only.  */
1335   save_may_throw = data->may_throw;
1336   data->may_throw = false;
1337   data->last_goto = NULL;
1338
1339   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1340
1341   this_may_throw = data->may_throw;
1342   data->may_throw = save_may_throw;
1343
1344   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1345   if (!this_may_throw)
1346     {
1347       if (warn_notreached)
1348         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1349       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1350       data->repeat = true;
1351       return;
1352     }
1353
1354   /* Process the catch clause specially.  We may be able to tell that
1355      no exceptions propagate past this point.  */
1356
1357   this_may_throw = true;
1358   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1359   stmt = tsi_stmt (i);
1360   data->last_goto = NULL;
1361
1362   switch (TREE_CODE (stmt))
1363     {
1364     case CATCH_EXPR:
1365       for (; !tsi_end_p (i); tsi_next (&i))
1366         {
1367           stmt = tsi_stmt (i);
1368           /* If we catch all exceptions, then the body does not
1369              propagate exceptions past this point.  */
1370           if (CATCH_TYPES (stmt) == NULL)
1371             this_may_throw = false;
1372           data->last_goto = NULL;
1373           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1374         }
1375       break;
1376
1377     case EH_FILTER_EXPR:
1378       if (EH_FILTER_MUST_NOT_THROW (stmt))
1379         this_may_throw = false;
1380       else if (EH_FILTER_TYPES (stmt) == NULL)
1381         this_may_throw = false;
1382       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1383       break;
1384
1385     default:
1386       /* Otherwise this is a cleanup.  */
1387       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1388
1389       /* If the cleanup is empty, then we can emit the TRY block without
1390          the enclosing TRY_CATCH_EXPR.  */
1391       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1392         {
1393           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1394           data->repeat = true;
1395         }
1396       break;
1397     }
1398   data->may_throw |= this_may_throw;
1399 }
1400
1401
1402 static void
1403 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1404 {
1405   tree block;
1406
1407   /* First remove anything underneath the BIND_EXPR.  */
1408   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1409
1410   /* If the BIND_EXPR has no variables, then we can pull everything
1411      up one level and remove the BIND_EXPR, unless this is the toplevel
1412      BIND_EXPR for the current function or an inlined function.
1413
1414      When this situation occurs we will want to apply this
1415      optimization again.  */
1416   block = BIND_EXPR_BLOCK (*stmt_p);
1417   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1418       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1419       && (! block
1420           || ! BLOCK_ABSTRACT_ORIGIN (block)
1421           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1422               != FUNCTION_DECL)))
1423     {
1424       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1425       data->repeat = true;
1426     }
1427 }
1428
1429
1430 static void
1431 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1432 {
1433   tree dest = GOTO_DESTINATION (*stmt_p);
1434
1435   data->may_branch = true;
1436   data->last_goto = NULL;
1437
1438   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1439   if (TREE_CODE (dest) == LABEL_DECL)
1440     data->last_goto = stmt_p;
1441 }
1442
1443
1444 static void
1445 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1446 {
1447   tree label = LABEL_EXPR_LABEL (*stmt_p);
1448
1449   data->has_label = true;
1450
1451   /* We do want to jump across non-local label receiver code.  */
1452   if (DECL_NONLOCAL (label))
1453     data->last_goto = NULL;
1454
1455   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1456     {
1457       *data->last_goto = build_empty_stmt ();
1458       data->repeat = true;
1459     }
1460
1461   /* ??? Add something here to delete unused labels.  */
1462 }
1463
1464
1465 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1466    decl.  This allows us to eliminate redundant or useless
1467    calls to "const" functions. 
1468
1469    Gimplifier already does the same operation, but we may notice functions
1470    being const and pure once their calls has been gimplified, so we need
1471    to update the flag.  */
1472
1473 static void
1474 update_call_expr_flags (tree call)
1475 {
1476   tree decl = get_callee_fndecl (call);
1477   if (!decl)
1478     return;
1479   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1480     TREE_SIDE_EFFECTS (call) = 0;
1481   if (TREE_NOTHROW (decl))
1482     TREE_NOTHROW (call) = 1;
1483 }
1484
1485
1486 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1487
1488 void
1489 notice_special_calls (tree t)
1490 {
1491   int flags = call_expr_flags (t);
1492
1493   if (flags & ECF_MAY_BE_ALLOCA)
1494     current_function_calls_alloca = true;
1495   if (flags & ECF_RETURNS_TWICE)
1496     current_function_calls_setjmp = true;
1497 }
1498
1499
1500 /* Clear flags set by notice_special_calls.  Used by dead code removal
1501    to update the flags.  */
1502
1503 void
1504 clear_special_calls (void)
1505 {
1506   current_function_calls_alloca = false;
1507   current_function_calls_setjmp = false;
1508 }
1509
1510
1511 static void
1512 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1513 {
1514   tree t = *tp, op;
1515
1516   switch (TREE_CODE (t))
1517     {
1518     case COND_EXPR:
1519       remove_useless_stmts_cond (tp, data);
1520       break;
1521
1522     case TRY_FINALLY_EXPR:
1523       remove_useless_stmts_tf (tp, data);
1524       break;
1525
1526     case TRY_CATCH_EXPR:
1527       remove_useless_stmts_tc (tp, data);
1528       break;
1529
1530     case BIND_EXPR:
1531       remove_useless_stmts_bind (tp, data);
1532       break;
1533
1534     case GOTO_EXPR:
1535       remove_useless_stmts_goto (tp, data);
1536       break;
1537
1538     case LABEL_EXPR:
1539       remove_useless_stmts_label (tp, data);
1540       break;
1541
1542     case RETURN_EXPR:
1543       fold_stmt (tp);
1544       data->last_goto = NULL;
1545       data->may_branch = true;
1546       break;
1547
1548     case CALL_EXPR:
1549       fold_stmt (tp);
1550       data->last_goto = NULL;
1551       notice_special_calls (t);
1552       update_call_expr_flags (t);
1553       if (tree_could_throw_p (t))
1554         data->may_throw = true;
1555       break;
1556
1557     case MODIFY_EXPR:
1558       data->last_goto = NULL;
1559       fold_stmt (tp);
1560       op = get_call_expr_in (t);
1561       if (op)
1562         {
1563           update_call_expr_flags (op);
1564           notice_special_calls (op);
1565         }
1566       if (tree_could_throw_p (t))
1567         data->may_throw = true;
1568       break;
1569
1570     case STATEMENT_LIST:
1571       {
1572         tree_stmt_iterator i = tsi_start (t);
1573         while (!tsi_end_p (i))
1574           {
1575             t = tsi_stmt (i);
1576             if (IS_EMPTY_STMT (t))
1577               {
1578                 tsi_delink (&i);
1579                 continue;
1580               }
1581             
1582             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1583
1584             t = tsi_stmt (i);
1585             if (TREE_CODE (t) == STATEMENT_LIST)
1586               {
1587                 tsi_link_before (&i, t, TSI_SAME_STMT);
1588                 tsi_delink (&i);
1589               }
1590             else
1591               tsi_next (&i);
1592           }
1593       }
1594       break;
1595     case SWITCH_EXPR:
1596       fold_stmt (tp);
1597       data->last_goto = NULL;
1598       break;
1599
1600     default:
1601       data->last_goto = NULL;
1602       break;
1603     }
1604 }
1605
1606 static void
1607 remove_useless_stmts (void)
1608 {
1609   struct rus_data data;
1610
1611   clear_special_calls ();
1612
1613   do
1614     {
1615       memset (&data, 0, sizeof (data));
1616       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1617     }
1618   while (data.repeat);
1619 }
1620
1621
1622 struct tree_opt_pass pass_remove_useless_stmts = 
1623 {
1624   "useless",                            /* name */
1625   NULL,                                 /* gate */
1626   remove_useless_stmts,                 /* execute */
1627   NULL,                                 /* sub */
1628   NULL,                                 /* next */
1629   0,                                    /* static_pass_number */
1630   0,                                    /* tv_id */
1631   PROP_gimple_any,                      /* properties_required */
1632   0,                                    /* properties_provided */
1633   0,                                    /* properties_destroyed */
1634   0,                                    /* todo_flags_start */
1635   TODO_dump_func,                       /* todo_flags_finish */
1636   0                                     /* letter */
1637 };
1638
1639
1640 /* Remove obviously useless statements in basic block BB.  */
1641
1642 static void
1643 cfg_remove_useless_stmts_bb (basic_block bb)
1644 {
1645   block_stmt_iterator bsi;
1646   tree stmt = NULL_TREE;
1647   tree cond, var = NULL_TREE, val = NULL_TREE;
1648   struct var_ann_d *ann;
1649
1650   /* Check whether we come here from a condition, and if so, get the
1651      condition.  */
1652   if (!bb->pred
1653       || bb->pred->pred_next
1654       || !(bb->pred->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1655     return;
1656
1657   cond = COND_EXPR_COND (last_stmt (bb->pred->src));
1658
1659   if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1660     {
1661       var = cond;
1662       val = (bb->pred->flags & EDGE_FALSE_VALUE
1663              ? boolean_false_node : boolean_true_node);
1664     }
1665   else if (TREE_CODE (cond) == TRUTH_NOT_EXPR
1666            && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1667                || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL))
1668     {
1669       var = TREE_OPERAND (cond, 0);
1670       val = (bb->pred->flags & EDGE_FALSE_VALUE
1671              ? boolean_true_node : boolean_false_node);
1672     }
1673   else
1674     {
1675       if (bb->pred->flags & EDGE_FALSE_VALUE)
1676         cond = invert_truthvalue (cond);
1677       if (TREE_CODE (cond) == EQ_EXPR
1678           && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1679               || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1680           && (TREE_CODE (TREE_OPERAND (cond, 1)) == VAR_DECL
1681               || TREE_CODE (TREE_OPERAND (cond, 1)) == PARM_DECL
1682               || TREE_CONSTANT (TREE_OPERAND (cond, 1))))
1683         {
1684           var = TREE_OPERAND (cond, 0);
1685           val = TREE_OPERAND (cond, 1);
1686         }
1687       else
1688         return;
1689     }
1690
1691   /* Only work for normal local variables.  */
1692   ann = var_ann (var);
1693   if (!ann
1694       || ann->may_aliases
1695       || TREE_ADDRESSABLE (var))
1696     return;
1697
1698   if (! TREE_CONSTANT (val))
1699     {
1700       ann = var_ann (val);
1701       if (!ann
1702           || ann->may_aliases
1703           || TREE_ADDRESSABLE (val))
1704         return;
1705     }
1706
1707   /* Ignore floating point variables, since comparison behaves weird for
1708      them.  */
1709   if (FLOAT_TYPE_P (TREE_TYPE (var)))
1710     return;
1711
1712   for (bsi = bsi_start (bb); !bsi_end_p (bsi);)
1713     {
1714       stmt = bsi_stmt (bsi);
1715
1716       /* If the THEN/ELSE clause merely assigns a value to a variable/parameter
1717          which is already known to contain that value, then remove the useless
1718          THEN/ELSE clause.  */
1719       if (TREE_CODE (stmt) == MODIFY_EXPR
1720           && TREE_OPERAND (stmt, 0) == var
1721           && operand_equal_p (val, TREE_OPERAND (stmt, 1), 0))
1722         {
1723           bsi_remove (&bsi);
1724           continue;
1725         }
1726
1727       /* Invalidate the var if we encounter something that could modify it.
1728          Likewise for the value it was previously set to.  Note that we only
1729          consider values that are either a VAR_DECL or PARM_DECL so we
1730          can test for conflict very simply.  */
1731       if (TREE_CODE (stmt) == ASM_EXPR
1732           || (TREE_CODE (stmt) == MODIFY_EXPR
1733               && (TREE_OPERAND (stmt, 0) == var
1734                   || TREE_OPERAND (stmt, 0) == val)))
1735         return;
1736   
1737       bsi_next (&bsi);
1738     }
1739 }
1740
1741
1742 /* A CFG-aware version of remove_useless_stmts.  */
1743
1744 void
1745 cfg_remove_useless_stmts (void)
1746 {
1747   basic_block bb;
1748
1749 #ifdef ENABLE_CHECKING
1750   verify_flow_info ();
1751 #endif
1752
1753   FOR_EACH_BB (bb)
1754     {
1755       cfg_remove_useless_stmts_bb (bb);
1756     }
1757 }
1758
1759
1760 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1761
1762 static void
1763 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1764 {
1765   tree phi;
1766
1767   /* Since this block is no longer reachable, we can just delete all
1768      of its PHI nodes.  */
1769   phi = phi_nodes (bb);
1770   while (phi)
1771     {
1772       tree next = PHI_CHAIN (phi);
1773       remove_phi_node (phi, NULL_TREE, bb);
1774       phi = next;
1775     }
1776
1777   /* Remove edges to BB's successors.  */
1778   while (bb->succ != NULL)
1779     ssa_remove_edge (bb->succ);
1780 }
1781
1782
1783 /* Remove statements of basic block BB.  */
1784
1785 static void
1786 remove_bb (basic_block bb)
1787 {
1788   block_stmt_iterator i;
1789   source_locus loc = 0;
1790
1791   if (dump_file)
1792     {
1793       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1794       if (dump_flags & TDF_DETAILS)
1795         {
1796           dump_bb (bb, dump_file, 0);
1797           fprintf (dump_file, "\n");
1798         }
1799     }
1800
1801   /* Remove all the instructions in the block.  */
1802   for (i = bsi_start (bb); !bsi_end_p (i); bsi_remove (&i))
1803     {
1804       tree stmt = bsi_stmt (i);
1805
1806       set_bb_for_stmt (stmt, NULL);
1807
1808       /* Don't warn for removed gotos.  Gotos are often removed due to
1809          jump threading, thus resulting in bogus warnings.  Not great,
1810          since this way we lose warnings for gotos in the original
1811          program that are indeed unreachable.  */
1812       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
1813 #ifdef USE_MAPPED_LOCATION
1814         loc = EXPR_LOCATION (stmt);
1815 #else
1816         loc = EXPR_LOCUS (stmt);
1817 #endif
1818     }
1819
1820   /* If requested, give a warning that the first statement in the
1821      block is unreachable.  We walk statements backwards in the
1822      loop above, so the last statement we process is the first statement
1823      in the block.  */
1824   if (warn_notreached && loc)
1825 #ifdef USE_MAPPED_LOCATION
1826     warning ("%Hwill never be executed", &loc);
1827 #else
1828     warning ("%Hwill never be executed", loc);
1829 #endif
1830
1831   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1832 }
1833
1834
1835 /* Examine BB to determine if it is a forwarding block (a block which only
1836    transfers control to a new destination).  If BB is a forwarding block,
1837    then return the edge leading to the ultimate destination.  */
1838
1839 edge
1840 tree_block_forwards_to (basic_block bb)
1841 {
1842   block_stmt_iterator bsi;
1843   bb_ann_t ann = bb_ann (bb);
1844   tree stmt;
1845
1846   /* If this block is not forwardable, then avoid useless work.  */
1847   if (! ann->forwardable)
1848     return NULL;
1849
1850   /* Set this block to not be forwardable.  This prevents infinite loops since
1851      any block currently under examination is considered non-forwardable.  */
1852   ann->forwardable = 0;
1853
1854   /* No forwarding is possible if this block is a special block (ENTRY/EXIT),
1855      this block has more than one successor, this block's single successor is
1856      reached via an abnormal edge, this block has phi nodes, or this block's
1857      single successor has phi nodes.  */
1858   if (bb == EXIT_BLOCK_PTR
1859       || bb == ENTRY_BLOCK_PTR
1860       || !bb->succ
1861       || bb->succ->succ_next
1862       || bb->succ->dest == EXIT_BLOCK_PTR
1863       || (bb->succ->flags & EDGE_ABNORMAL) != 0
1864       || phi_nodes (bb)
1865       || phi_nodes (bb->succ->dest))
1866     return NULL;
1867
1868   /* Walk past any labels at the start of this block.  */
1869   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1870     {
1871       stmt = bsi_stmt (bsi);
1872       if (TREE_CODE (stmt) != LABEL_EXPR)
1873         break;
1874     }
1875
1876   /* If we reached the end of this block we may be able to optimize this
1877      case.  */
1878   if (bsi_end_p (bsi))
1879     {
1880       edge dest;
1881
1882       /* Recursive call to pick up chains of forwarding blocks.  */
1883       dest = tree_block_forwards_to (bb->succ->dest);
1884
1885       /* If none found, we forward to bb->succ at minimum.  */
1886       if (!dest)
1887         dest = bb->succ;
1888
1889       ann->forwardable = 1;
1890       return dest;
1891     }
1892
1893   /* No forwarding possible.  */
1894   return NULL;
1895 }
1896
1897
1898 /* Try to remove superfluous control structures.  */
1899
1900 static bool
1901 cleanup_control_flow (void)
1902 {
1903   basic_block bb;
1904   block_stmt_iterator bsi;
1905   bool retval = false;
1906   tree stmt;
1907
1908   FOR_EACH_BB (bb)
1909     {
1910       bsi = bsi_last (bb);
1911
1912       if (bsi_end_p (bsi))
1913         continue;
1914       
1915       stmt = bsi_stmt (bsi);
1916       if (TREE_CODE (stmt) == COND_EXPR
1917           || TREE_CODE (stmt) == SWITCH_EXPR)
1918         retval |= cleanup_control_expr_graph (bb, bsi);
1919     }
1920   return retval;
1921 }
1922
1923
1924 /* Disconnect an unreachable block in the control expression starting
1925    at block BB.  */
1926
1927 static bool
1928 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
1929 {
1930   edge taken_edge;
1931   bool retval = false;
1932   tree expr = bsi_stmt (bsi), val;
1933
1934   if (bb->succ->succ_next)
1935     {
1936       edge e, next;
1937
1938       switch (TREE_CODE (expr))
1939         {
1940         case COND_EXPR:
1941           val = COND_EXPR_COND (expr);
1942           break;
1943
1944         case SWITCH_EXPR:
1945           val = SWITCH_COND (expr);
1946           if (TREE_CODE (val) != INTEGER_CST)
1947             return false;
1948           break;
1949
1950         default:
1951           gcc_unreachable ();
1952         }
1953
1954       taken_edge = find_taken_edge (bb, val);
1955       if (!taken_edge)
1956         return false;
1957
1958       /* Remove all the edges except the one that is always executed.  */
1959       for (e = bb->succ; e; e = next)
1960         {
1961           next = e->succ_next;
1962           if (e != taken_edge)
1963             {
1964               taken_edge->probability += e->probability;
1965               taken_edge->count += e->count;
1966               ssa_remove_edge (e);
1967               retval = true;
1968             }
1969         }
1970       if (taken_edge->probability > REG_BR_PROB_BASE)
1971         taken_edge->probability = REG_BR_PROB_BASE;
1972     }
1973   else
1974     taken_edge = bb->succ;
1975
1976   bsi_remove (&bsi);
1977   taken_edge->flags = EDGE_FALLTHRU;
1978
1979   /* We removed some paths from the cfg.  */
1980   if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
1981     dom_computed[CDI_DOMINATORS] = DOM_CONS_OK;
1982
1983   return retval;
1984 }
1985
1986
1987 /* Given a control block BB and a predicate VAL, return the edge that
1988    will be taken out of the block.  If VAL does not match a unique
1989    edge, NULL is returned.  */
1990
1991 edge
1992 find_taken_edge (basic_block bb, tree val)
1993 {
1994   tree stmt;
1995
1996   stmt = last_stmt (bb);
1997
1998   gcc_assert (stmt);
1999   gcc_assert (is_ctrl_stmt (stmt));
2000
2001   /* If VAL is a predicate of the form N RELOP N, where N is an
2002      SSA_NAME, we can always determine its truth value (except when
2003      doing floating point comparisons that may involve NaNs).  */
2004   if (val
2005       && TREE_CODE_CLASS (TREE_CODE (val)) == '<'
2006       && TREE_OPERAND (val, 0) == TREE_OPERAND (val, 1)
2007       && TREE_CODE (TREE_OPERAND (val, 0)) == SSA_NAME
2008       && (TREE_CODE (TREE_TYPE (TREE_OPERAND (val, 0))) != REAL_TYPE
2009           || !HONOR_NANS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (val, 0))))))
2010     {
2011       enum tree_code code = TREE_CODE (val);
2012
2013       if (code == EQ_EXPR || code == LE_EXPR || code == GE_EXPR)
2014         val = boolean_true_node;
2015       else if (code == LT_EXPR || code == GT_EXPR || code == NE_EXPR)
2016         val = boolean_false_node;
2017     }
2018
2019   /* If VAL is not a constant, we can't determine which edge might
2020      be taken.  */
2021   if (val == NULL || !really_constant_p (val))
2022     return NULL;
2023
2024   if (TREE_CODE (stmt) == COND_EXPR)
2025     return find_taken_edge_cond_expr (bb, val);
2026
2027   if (TREE_CODE (stmt) == SWITCH_EXPR)
2028     return find_taken_edge_switch_expr (bb, val);
2029
2030   return bb->succ;
2031 }
2032
2033
2034 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2035    statement, determine which of the two edges will be taken out of the
2036    block.  Return NULL if either edge may be taken.  */
2037
2038 static edge
2039 find_taken_edge_cond_expr (basic_block bb, tree val)
2040 {
2041   edge true_edge, false_edge;
2042
2043   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2044
2045   /* If both edges of the branch lead to the same basic block, it doesn't
2046      matter which edge is taken.  */
2047   if (true_edge->dest == false_edge->dest)
2048     return true_edge;
2049
2050   /* Otherwise, try to determine which branch of the if() will be taken.
2051      If VAL is a constant but it can't be reduced to a 0 or a 1, then
2052      we don't really know which edge will be taken at runtime.  This
2053      may happen when comparing addresses (e.g., if (&var1 == 4)).  */
2054   if (integer_nonzerop (val))
2055     return true_edge;
2056   else if (integer_zerop (val))
2057     return false_edge;
2058   else
2059     return NULL;
2060 }
2061
2062
2063 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
2064    statement, determine which edge will be taken out of the block.  Return
2065    NULL if any edge may be taken.  */
2066
2067 static edge
2068 find_taken_edge_switch_expr (basic_block bb, tree val)
2069 {
2070   tree switch_expr, taken_case;
2071   basic_block dest_bb;
2072   edge e;
2073
2074   if (TREE_CODE (val) != INTEGER_CST)
2075     return NULL;
2076
2077   switch_expr = last_stmt (bb);
2078   taken_case = find_case_label_for_value (switch_expr, val);
2079   dest_bb = label_to_block (CASE_LABEL (taken_case));
2080
2081   e = find_edge (bb, dest_bb);
2082   gcc_assert (e);
2083   return e;
2084 }
2085
2086
2087 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2088    We can make optimal use here of the fact that the case labels are
2089    sorted: We can do a binary search for a case matching VAL.  */
2090
2091 static tree
2092 find_case_label_for_value (tree switch_expr, tree val)
2093 {
2094   tree vec = SWITCH_LABELS (switch_expr);
2095   size_t low, high, n = TREE_VEC_LENGTH (vec);
2096   tree default_case = TREE_VEC_ELT (vec, n - 1);
2097
2098   for (low = -1, high = n - 1; high - low > 1; )
2099     {
2100       size_t i = (high + low) / 2;
2101       tree t = TREE_VEC_ELT (vec, i);
2102       int cmp;
2103
2104       /* Cache the result of comparing CASE_LOW and val.  */
2105       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2106
2107       if (cmp > 0)
2108         high = i;
2109       else
2110         low = i;
2111
2112       if (CASE_HIGH (t) == NULL)
2113         {
2114           /* A singe-valued case label.  */
2115           if (cmp == 0)
2116             return t;
2117         }
2118       else
2119         {
2120           /* A case range.  We can only handle integer ranges.  */
2121           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2122             return t;
2123         }
2124     }
2125
2126   return default_case;
2127 }
2128
2129
2130 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
2131    those alternatives are equal in each of the PHI nodes, then return
2132    true, else return false.  */
2133
2134 static bool
2135 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
2136 {
2137   tree phi, val1, val2;
2138   int n1, n2;
2139
2140   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
2141     {
2142       n1 = phi_arg_from_edge (phi, e1);
2143       n2 = phi_arg_from_edge (phi, e2);
2144
2145       gcc_assert (n1 >= 0);
2146       gcc_assert (n2 >= 0);
2147
2148       val1 = PHI_ARG_DEF (phi, n1);
2149       val2 = PHI_ARG_DEF (phi, n2);
2150
2151       if (!operand_equal_p (val1, val2, 0))
2152         return false;
2153     }
2154
2155   return true;
2156 }
2157
2158
2159 /*---------------------------------------------------------------------------
2160                               Debugging functions
2161 ---------------------------------------------------------------------------*/
2162
2163 /* Dump tree-specific information of block BB to file OUTF.  */
2164
2165 void
2166 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2167 {
2168   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2169 }
2170
2171
2172 /* Dump a basic block on stderr.  */
2173
2174 void
2175 debug_tree_bb (basic_block bb)
2176 {
2177   dump_bb (bb, stderr, 0);
2178 }
2179
2180
2181 /* Dump basic block with index N on stderr.  */
2182
2183 basic_block
2184 debug_tree_bb_n (int n)
2185 {
2186   debug_tree_bb (BASIC_BLOCK (n));
2187   return BASIC_BLOCK (n);
2188 }        
2189
2190
2191 /* Dump the CFG on stderr.
2192
2193    FLAGS are the same used by the tree dumping functions
2194    (see TDF_* in tree.h).  */
2195
2196 void
2197 debug_tree_cfg (int flags)
2198 {
2199   dump_tree_cfg (stderr, flags);
2200 }
2201
2202
2203 /* Dump the program showing basic block boundaries on the given FILE.
2204
2205    FLAGS are the same used by the tree dumping functions (see TDF_* in
2206    tree.h).  */
2207
2208 void
2209 dump_tree_cfg (FILE *file, int flags)
2210 {
2211   if (flags & TDF_DETAILS)
2212     {
2213       const char *funcname
2214         = lang_hooks.decl_printable_name (current_function_decl, 2);
2215
2216       fputc ('\n', file);
2217       fprintf (file, ";; Function %s\n\n", funcname);
2218       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2219                n_basic_blocks, n_edges, last_basic_block);
2220
2221       brief_dump_cfg (file);
2222       fprintf (file, "\n");
2223     }
2224
2225   if (flags & TDF_STATS)
2226     dump_cfg_stats (file);
2227
2228   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2229 }
2230
2231
2232 /* Dump CFG statistics on FILE.  */
2233
2234 void
2235 dump_cfg_stats (FILE *file)
2236 {
2237   static long max_num_merged_labels = 0;
2238   unsigned long size, total = 0;
2239   int n_edges;
2240   basic_block bb;
2241   const char * const fmt_str   = "%-30s%-13s%12s\n";
2242   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2243   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2244   const char *funcname
2245     = lang_hooks.decl_printable_name (current_function_decl, 2);
2246
2247
2248   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2249
2250   fprintf (file, "---------------------------------------------------------\n");
2251   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2252   fprintf (file, fmt_str, "", "  instances  ", "used ");
2253   fprintf (file, "---------------------------------------------------------\n");
2254
2255   size = n_basic_blocks * sizeof (struct basic_block_def);
2256   total += size;
2257   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2258            SCALE (size), LABEL (size));
2259
2260   n_edges = 0;
2261   FOR_EACH_BB (bb)
2262     {
2263       edge e;
2264       for (e = bb->succ; e; e = e->succ_next)
2265         n_edges++;
2266     }
2267   size = n_edges * sizeof (struct edge_def);
2268   total += size;
2269   fprintf (file, fmt_str_1, "Edges", n_edges, SCALE (size), LABEL (size));
2270
2271   size = n_basic_blocks * sizeof (struct bb_ann_d);
2272   total += size;
2273   fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
2274            SCALE (size), LABEL (size));
2275
2276   fprintf (file, "---------------------------------------------------------\n");
2277   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2278            LABEL (total));
2279   fprintf (file, "---------------------------------------------------------\n");
2280   fprintf (file, "\n");
2281
2282   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2283     max_num_merged_labels = cfg_stats.num_merged_labels;
2284
2285   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2286            cfg_stats.num_merged_labels, max_num_merged_labels);
2287
2288   fprintf (file, "\n");
2289 }
2290
2291
2292 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2293    linked in the final executable.  */
2294
2295 void
2296 debug_cfg_stats (void)
2297 {
2298   dump_cfg_stats (stderr);
2299 }
2300
2301
2302 /* Dump the flowgraph to a .vcg FILE.  */
2303
2304 static void
2305 tree_cfg2vcg (FILE *file)
2306 {
2307   edge e;
2308   basic_block bb;
2309   const char *funcname
2310     = lang_hooks.decl_printable_name (current_function_decl, 2);
2311
2312   /* Write the file header.  */
2313   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2314   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2315   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2316
2317   /* Write blocks and edges.  */
2318   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
2319     {
2320       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2321                e->dest->index);
2322
2323       if (e->flags & EDGE_FAKE)
2324         fprintf (file, " linestyle: dotted priority: 10");
2325       else
2326         fprintf (file, " linestyle: solid priority: 100");
2327
2328       fprintf (file, " }\n");
2329     }
2330   fputc ('\n', file);
2331
2332   FOR_EACH_BB (bb)
2333     {
2334       enum tree_code head_code, end_code;
2335       const char *head_name, *end_name;
2336       int head_line = 0;
2337       int end_line = 0;
2338       tree first = first_stmt (bb);
2339       tree last = last_stmt (bb);
2340
2341       if (first)
2342         {
2343           head_code = TREE_CODE (first);
2344           head_name = tree_code_name[head_code];
2345           head_line = get_lineno (first);
2346         }
2347       else
2348         head_name = "no-statement";
2349
2350       if (last)
2351         {
2352           end_code = TREE_CODE (last);
2353           end_name = tree_code_name[end_code];
2354           end_line = get_lineno (last);
2355         }
2356       else
2357         end_name = "no-statement";
2358
2359       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2360                bb->index, bb->index, head_name, head_line, end_name,
2361                end_line);
2362
2363       for (e = bb->succ; e; e = e->succ_next)
2364         {
2365           if (e->dest == EXIT_BLOCK_PTR)
2366             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2367           else
2368             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2369
2370           if (e->flags & EDGE_FAKE)
2371             fprintf (file, " priority: 10 linestyle: dotted");
2372           else
2373             fprintf (file, " priority: 100 linestyle: solid");
2374
2375           fprintf (file, " }\n");
2376         }
2377
2378       if (bb->next_bb != EXIT_BLOCK_PTR)
2379         fputc ('\n', file);
2380     }
2381
2382   fputs ("}\n\n", file);
2383 }
2384
2385
2386
2387 /*---------------------------------------------------------------------------
2388                              Miscellaneous helpers
2389 ---------------------------------------------------------------------------*/
2390
2391 /* Return true if T represents a stmt that always transfers control.  */
2392
2393 bool
2394 is_ctrl_stmt (tree t)
2395 {
2396   return (TREE_CODE (t) == COND_EXPR
2397           || TREE_CODE (t) == SWITCH_EXPR
2398           || TREE_CODE (t) == GOTO_EXPR
2399           || TREE_CODE (t) == RETURN_EXPR
2400           || TREE_CODE (t) == RESX_EXPR);
2401 }
2402
2403
2404 /* Return true if T is a statement that may alter the flow of control
2405    (e.g., a call to a non-returning function).  */
2406
2407 bool
2408 is_ctrl_altering_stmt (tree t)
2409 {
2410   tree call;
2411
2412   gcc_assert (t);
2413   call = get_call_expr_in (t);
2414   if (call)
2415     {
2416       /* A non-pure/const CALL_EXPR alters flow control if the current
2417          function has nonlocal labels.  */
2418       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2419         return true;
2420
2421       /* A CALL_EXPR also alters control flow if it does not return.  */
2422       if (call_expr_flags (call) & (ECF_NORETURN | ECF_LONGJMP))
2423         return true;
2424     }
2425
2426   /* If a statement can throw, it alters control flow.  */
2427   return tree_can_throw_internal (t);
2428 }
2429
2430
2431 /* Return true if T is a computed goto.  */
2432
2433 bool
2434 computed_goto_p (tree t)
2435 {
2436   return (TREE_CODE (t) == GOTO_EXPR
2437           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2438 }
2439
2440
2441 /* Checks whether EXPR is a simple local goto.  */
2442
2443 bool
2444 simple_goto_p (tree expr)
2445 {
2446   return (TREE_CODE (expr) == GOTO_EXPR
2447           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2448 }
2449
2450
2451 /* Return true if T should start a new basic block.  PREV_T is the
2452    statement preceding T.  It is used when T is a label or a case label.
2453    Labels should only start a new basic block if their previous statement
2454    wasn't a label.  Otherwise, sequence of labels would generate
2455    unnecessary basic blocks that only contain a single label.  */
2456
2457 static inline bool
2458 stmt_starts_bb_p (tree t, tree prev_t)
2459 {
2460   enum tree_code code;
2461
2462   if (t == NULL_TREE)
2463     return false;
2464
2465   /* LABEL_EXPRs start a new basic block only if the preceding
2466      statement wasn't a label of the same type.  This prevents the
2467      creation of consecutive blocks that have nothing but a single
2468      label.  */
2469   code = TREE_CODE (t);
2470   if (code == LABEL_EXPR)
2471     {
2472       /* Nonlocal and computed GOTO targets always start a new block.  */
2473       if (code == LABEL_EXPR
2474           && (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2475               || FORCED_LABEL (LABEL_EXPR_LABEL (t))))
2476         return true;
2477
2478       if (prev_t && TREE_CODE (prev_t) == code)
2479         {
2480           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2481             return true;
2482
2483           cfg_stats.num_merged_labels++;
2484           return false;
2485         }
2486       else
2487         return true;
2488     }
2489
2490   return false;
2491 }
2492
2493
2494 /* Return true if T should end a basic block.  */
2495
2496 bool
2497 stmt_ends_bb_p (tree t)
2498 {
2499   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2500 }
2501
2502
2503 /* Add gotos that used to be represented implicitly in the CFG.  */
2504
2505 void
2506 disband_implicit_edges (void)
2507 {
2508   basic_block bb;
2509   block_stmt_iterator last;
2510   edge e;
2511   tree stmt, label;
2512
2513   FOR_EACH_BB (bb)
2514     {
2515       last = bsi_last (bb);
2516       stmt = last_stmt (bb);
2517
2518       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2519         {
2520           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2521              from cfg_remove_useless_stmts here since it violates the
2522              invariants for tree--cfg correspondence and thus fits better
2523              here where we do it anyway.  */
2524           for (e = bb->succ; e; e = e->succ_next)
2525             {
2526               if (e->dest != bb->next_bb)
2527                 continue;
2528
2529               if (e->flags & EDGE_TRUE_VALUE)
2530                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2531               else if (e->flags & EDGE_FALSE_VALUE)
2532                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2533               else
2534                 gcc_unreachable ();
2535               e->flags |= EDGE_FALLTHRU;
2536             }
2537
2538           continue;
2539         }
2540
2541       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2542         {
2543           /* Remove the RETURN_EXPR if we may fall though to the exit
2544              instead.  */
2545           gcc_assert (bb->succ);
2546           gcc_assert (!bb->succ->succ_next);
2547           gcc_assert (bb->succ->dest == EXIT_BLOCK_PTR);
2548
2549           if (bb->next_bb == EXIT_BLOCK_PTR
2550               && !TREE_OPERAND (stmt, 0))
2551             {
2552               bsi_remove (&last);
2553               bb->succ->flags |= EDGE_FALLTHRU;
2554             }
2555           continue;
2556         }
2557
2558       /* There can be no fallthru edge if the last statement is a control
2559          one.  */
2560       if (stmt && is_ctrl_stmt (stmt))
2561         continue;
2562
2563       /* Find a fallthru edge and emit the goto if necessary.  */
2564       for (e = bb->succ; e; e = e->succ_next)
2565         if (e->flags & EDGE_FALLTHRU)
2566           break;
2567
2568       if (!e || e->dest == bb->next_bb)
2569         continue;
2570
2571       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2572       label = tree_block_label (e->dest);
2573
2574       stmt = build1 (GOTO_EXPR, void_type_node, label);
2575 #ifdef USE_MAPPED_LOCATION
2576       SET_EXPR_LOCATION (stmt, e->goto_locus);
2577 #else
2578       SET_EXPR_LOCUS (stmt, e->goto_locus);
2579 #endif
2580       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2581       e->flags &= ~EDGE_FALLTHRU;
2582     }
2583 }
2584
2585 /* Remove block annotations and other datastructures.  */
2586
2587 void
2588 delete_tree_cfg_annotations (void)
2589 {
2590   basic_block bb;
2591   if (n_basic_blocks > 0)
2592     free_blocks_annotations ();
2593
2594   label_to_block_map = NULL;
2595   free_rbi_pool ();
2596   FOR_EACH_BB (bb)
2597     bb->rbi = NULL;
2598 }
2599
2600
2601 /* Return the first statement in basic block BB.  */
2602
2603 tree
2604 first_stmt (basic_block bb)
2605 {
2606   block_stmt_iterator i = bsi_start (bb);
2607   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2608 }
2609
2610
2611 /* Return the last statement in basic block BB.  */
2612
2613 tree
2614 last_stmt (basic_block bb)
2615 {
2616   block_stmt_iterator b = bsi_last (bb);
2617   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2618 }
2619
2620
2621 /* Return a pointer to the last statement in block BB.  */
2622
2623 tree *
2624 last_stmt_ptr (basic_block bb)
2625 {
2626   block_stmt_iterator last = bsi_last (bb);
2627   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2628 }
2629
2630
2631 /* Return the last statement of an otherwise empty block.  Return NULL
2632    if the block is totally empty, or if it contains more than one
2633    statement.  */
2634
2635 tree
2636 last_and_only_stmt (basic_block bb)
2637 {
2638   block_stmt_iterator i = bsi_last (bb);
2639   tree last, prev;
2640
2641   if (bsi_end_p (i))
2642     return NULL_TREE;
2643
2644   last = bsi_stmt (i);
2645   bsi_prev (&i);
2646   if (bsi_end_p (i))
2647     return last;
2648
2649   /* Empty statements should no longer appear in the instruction stream.
2650      Everything that might have appeared before should be deleted by
2651      remove_useless_stmts, and the optimizers should just bsi_remove
2652      instead of smashing with build_empty_stmt.
2653
2654      Thus the only thing that should appear here in a block containing
2655      one executable statement is a label.  */
2656   prev = bsi_stmt (i);
2657   if (TREE_CODE (prev) == LABEL_EXPR)
2658     return last;
2659   else
2660     return NULL_TREE;
2661 }
2662
2663
2664 /* Mark BB as the basic block holding statement T.  */
2665
2666 void
2667 set_bb_for_stmt (tree t, basic_block bb)
2668 {
2669   if (TREE_CODE (t) == STATEMENT_LIST)
2670     {
2671       tree_stmt_iterator i;
2672       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2673         set_bb_for_stmt (tsi_stmt (i), bb);
2674     }
2675   else
2676     {
2677       stmt_ann_t ann = get_stmt_ann (t);
2678       ann->bb = bb;
2679
2680       /* If the statement is a label, add the label to block-to-labels map
2681          so that we can speed up edge creation for GOTO_EXPRs.  */
2682       if (TREE_CODE (t) == LABEL_EXPR)
2683         {
2684           int uid;
2685
2686           t = LABEL_EXPR_LABEL (t);
2687           uid = LABEL_DECL_UID (t);
2688           if (uid == -1)
2689             {
2690               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2691               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2692                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2693             }
2694           else
2695             /* We're moving an existing label.  Make sure that we've
2696                 removed it from the old block.  */
2697             gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
2698           VARRAY_BB (label_to_block_map, uid) = bb;
2699         }
2700     }
2701 }
2702
2703 /* Finds iterator for STMT.  */
2704
2705 extern block_stmt_iterator
2706 stmt_for_bsi (tree stmt)
2707 {
2708   block_stmt_iterator bsi;
2709
2710   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2711     if (bsi_stmt (bsi) == stmt)
2712       return bsi;
2713
2714   gcc_unreachable ();
2715 }
2716
2717 /* Insert statement (or statement list) T before the statement
2718    pointed-to by iterator I.  M specifies how to update iterator I
2719    after insertion (see enum bsi_iterator_update).  */
2720
2721 void
2722 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2723 {
2724   set_bb_for_stmt (t, i->bb);
2725   tsi_link_before (&i->tsi, t, m);
2726   modify_stmt (t);
2727 }
2728
2729
2730 /* Insert statement (or statement list) T after the statement
2731    pointed-to by iterator I.  M specifies how to update iterator I
2732    after insertion (see enum bsi_iterator_update).  */
2733
2734 void
2735 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2736 {
2737   set_bb_for_stmt (t, i->bb);
2738   tsi_link_after (&i->tsi, t, m);
2739   modify_stmt (t);
2740 }
2741
2742
2743 /* Remove the statement pointed to by iterator I.  The iterator is updated
2744    to the next statement.  */
2745
2746 void
2747 bsi_remove (block_stmt_iterator *i)
2748 {
2749   tree t = bsi_stmt (*i);
2750   set_bb_for_stmt (t, NULL);
2751   tsi_delink (&i->tsi);
2752 }
2753
2754
2755 /* Move the statement at FROM so it comes right after the statement at TO.  */
2756
2757 void 
2758 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2759 {
2760   tree stmt = bsi_stmt (*from);
2761   bsi_remove (from);
2762   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2763
2764
2765
2766 /* Move the statement at FROM so it comes right before the statement at TO.  */
2767
2768 void 
2769 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2770 {
2771   tree stmt = bsi_stmt (*from);
2772   bsi_remove (from);
2773   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2774 }
2775
2776
2777 /* Move the statement at FROM to the end of basic block BB.  */
2778
2779 void
2780 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2781 {
2782   block_stmt_iterator last = bsi_last (bb);
2783   
2784   /* Have to check bsi_end_p because it could be an empty block.  */
2785   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2786     bsi_move_before (from, &last);
2787   else
2788     bsi_move_after (from, &last);
2789 }
2790
2791
2792 /* Replace the contents of the statement pointed to by iterator BSI
2793    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
2794    information of the original statement is preserved.  */
2795
2796 void
2797 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
2798 {
2799   int eh_region;
2800   tree orig_stmt = bsi_stmt (*bsi);
2801
2802   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2803   set_bb_for_stmt (stmt, bsi->bb);
2804
2805   /* Preserve EH region information from the original statement, if
2806      requested by the caller.  */
2807   if (preserve_eh_info)
2808     {
2809       eh_region = lookup_stmt_eh_region (orig_stmt);
2810       if (eh_region >= 0)
2811         add_stmt_to_eh_region (stmt, eh_region);
2812     }
2813
2814   *bsi_stmt_ptr (*bsi) = stmt;
2815   modify_stmt (stmt);
2816 }
2817
2818
2819 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2820    is made to place the statement in an existing basic block, but
2821    sometimes that isn't possible.  When it isn't possible, the edge is
2822    split and the statement is added to the new block.
2823
2824    In all cases, the returned *BSI points to the correct location.  The
2825    return value is true if insertion should be done after the location,
2826    or false if it should be done before the location.  If new basic block
2827    has to be created, it is stored in *NEW_BB.  */
2828
2829 static bool
2830 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2831                            basic_block *new_bb)
2832 {
2833   basic_block dest, src;
2834   tree tmp;
2835
2836   dest = e->dest;
2837  restart:
2838
2839   /* If the destination has one predecessor which has no PHI nodes,
2840      insert there.  Except for the exit block. 
2841
2842      The requirement for no PHI nodes could be relaxed.  Basically we
2843      would have to examine the PHIs to prove that none of them used
2844      the value set by the statement we want to insert on E.   That
2845      hardly seems worth the effort.  */
2846   if (dest->pred->pred_next == NULL
2847       && ! phi_nodes (dest)
2848       && dest != EXIT_BLOCK_PTR)
2849     {
2850       *bsi = bsi_start (dest);
2851       if (bsi_end_p (*bsi))
2852         return true;
2853
2854       /* Make sure we insert after any leading labels.  */
2855       tmp = bsi_stmt (*bsi);
2856       while (TREE_CODE (tmp) == LABEL_EXPR)
2857         {
2858           bsi_next (bsi);
2859           if (bsi_end_p (*bsi))
2860             break;
2861           tmp = bsi_stmt (*bsi);
2862         }
2863
2864       if (bsi_end_p (*bsi))
2865         {
2866           *bsi = bsi_last (dest);
2867           return true;
2868         }
2869       else
2870         return false;
2871     }
2872
2873   /* If the source has one successor, the edge is not abnormal and
2874      the last statement does not end a basic block, insert there.
2875      Except for the entry block.  */
2876   src = e->src;
2877   if ((e->flags & EDGE_ABNORMAL) == 0
2878       && src->succ->succ_next == NULL
2879       && src != ENTRY_BLOCK_PTR)
2880     {
2881       *bsi = bsi_last (src);
2882       if (bsi_end_p (*bsi))
2883         return true;
2884
2885       tmp = bsi_stmt (*bsi);
2886       if (!stmt_ends_bb_p (tmp))
2887         return true;
2888
2889       /* Insert code just before returning the value.  We may need to decompose
2890          the return in the case it contains non-trivial operand.  */
2891       if (TREE_CODE (tmp) == RETURN_EXPR)
2892         {
2893           tree op = TREE_OPERAND (tmp, 0);
2894           if (!is_gimple_val (op))
2895             {
2896               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
2897               bsi_insert_before (bsi, op, BSI_NEW_STMT);
2898               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
2899             }
2900           bsi_prev (bsi);
2901           return true;
2902         }
2903     }
2904
2905   /* Otherwise, create a new basic block, and split this edge.  */
2906   dest = split_edge (e);
2907   if (new_bb)
2908     *new_bb = dest;
2909   e = dest->pred;
2910   goto restart;
2911 }
2912
2913
2914 /* This routine will commit all pending edge insertions, creating any new
2915    basic blocks which are necessary.
2916
2917    If specified, NEW_BLOCKS returns a count of the number of new basic
2918    blocks which were created.  */
2919
2920 void
2921 bsi_commit_edge_inserts (int *new_blocks)
2922 {
2923   basic_block bb;
2924   edge e;
2925   int blocks;
2926
2927   blocks = n_basic_blocks;
2928
2929   bsi_commit_edge_inserts_1 (ENTRY_BLOCK_PTR->succ);
2930
2931   FOR_EACH_BB (bb)
2932     for (e = bb->succ; e; e = e->succ_next)
2933       bsi_commit_edge_inserts_1 (e);
2934
2935   if (new_blocks)
2936     *new_blocks = n_basic_blocks - blocks;
2937 }
2938
2939
2940 /* Commit insertions pending at edge E.  */
2941
2942 static void
2943 bsi_commit_edge_inserts_1 (edge e)
2944 {
2945   if (PENDING_STMT (e))
2946     {
2947       block_stmt_iterator bsi;
2948       tree stmt = PENDING_STMT (e);
2949
2950       PENDING_STMT (e) = NULL_TREE;
2951
2952       if (tree_find_edge_insert_loc (e, &bsi, NULL))
2953         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2954       else
2955         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2956     }
2957 }
2958
2959
2960 /* Add STMT to the pending list of edge E.  No actual insertion is
2961    made until a call to bsi_commit_edge_inserts () is made.  */
2962
2963 void
2964 bsi_insert_on_edge (edge e, tree stmt)
2965 {
2966   append_to_statement_list (stmt, &PENDING_STMT (e));
2967 }
2968
2969 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If new block has to
2970    be created, it is returned.  */
2971
2972 basic_block
2973 bsi_insert_on_edge_immediate (edge e, tree stmt)
2974 {
2975   block_stmt_iterator bsi;
2976   basic_block new_bb = NULL;
2977
2978   gcc_assert (!PENDING_STMT (e));
2979
2980   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
2981     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2982   else
2983     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2984
2985   return new_bb;
2986 }
2987
2988 /*---------------------------------------------------------------------------
2989              Tree specific functions for CFG manipulation
2990 ---------------------------------------------------------------------------*/
2991
2992 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2993    Abort on abnormal edges.  */
2994
2995 static basic_block
2996 tree_split_edge (edge edge_in)
2997 {
2998   basic_block new_bb, after_bb, dest, src;
2999   edge new_edge, e;
3000   tree phi;
3001   int i, num_elem;
3002
3003   /* Abnormal edges cannot be split.  */
3004   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3005
3006   src = edge_in->src;
3007   dest = edge_in->dest;
3008
3009   /* Place the new block in the block list.  Try to keep the new block
3010      near its "logical" location.  This is of most help to humans looking
3011      at debugging dumps.  */
3012   for (e = dest->pred; e; e = e->pred_next)
3013     if (e->src->next_bb == dest)
3014       break;
3015   if (!e)
3016     after_bb = dest->prev_bb;
3017   else
3018     after_bb = edge_in->src;
3019
3020   new_bb = create_empty_bb (after_bb);
3021   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3022
3023   /* Find all the PHI arguments on the original edge, and change them to
3024      the new edge.  Do it before redirection, so that the argument does not
3025      get removed.  */
3026   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
3027     {
3028       num_elem = PHI_NUM_ARGS (phi);
3029       for (i = 0; i < num_elem; i++)
3030         if (PHI_ARG_EDGE (phi, i) == edge_in)
3031           {
3032             PHI_ARG_EDGE (phi, i) = new_edge;
3033             break;
3034           }
3035     }
3036
3037   e = redirect_edge_and_branch (edge_in, new_bb);
3038   gcc_assert (e);
3039   gcc_assert (!PENDING_STMT (edge_in));
3040
3041   return new_bb;
3042 }
3043
3044
3045 /* Return true when BB has label LABEL in it.  */
3046
3047 static bool
3048 has_label_p (basic_block bb, tree label)
3049 {
3050   block_stmt_iterator bsi;
3051
3052   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3053     {
3054       tree stmt = bsi_stmt (bsi);
3055
3056       if (TREE_CODE (stmt) != LABEL_EXPR)
3057         return false;
3058       if (LABEL_EXPR_LABEL (stmt) == label)
3059         return true;
3060     }
3061   return false;
3062 }
3063
3064
3065 /* Callback for walk_tree, check that all elements with address taken are
3066    properly noticed as such.  */
3067
3068 static tree
3069 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3070 {
3071   tree t = *tp, x;
3072
3073   if (TYPE_P (t))
3074     *walk_subtrees = 0;
3075   
3076   /* Check operand N for being valid GIMPLE and give error MSG if not. 
3077      We check for constants explicitly since they are not considered
3078      gimple invariants if they overflowed.  */
3079 #define CHECK_OP(N, MSG) \
3080   do { if (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, N))) != 'c'     \
3081          && !is_gimple_val (TREE_OPERAND (t, N)))                       \
3082        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3083
3084   switch (TREE_CODE (t))
3085     {
3086     case SSA_NAME:
3087       if (SSA_NAME_IN_FREE_LIST (t))
3088         {
3089           error ("SSA name in freelist but still referenced");
3090           return *tp;
3091         }
3092       break;
3093
3094     case MODIFY_EXPR:
3095       x = TREE_OPERAND (t, 0);
3096       if (TREE_CODE (x) == BIT_FIELD_REF
3097           && is_gimple_reg (TREE_OPERAND (x, 0)))
3098         {
3099           error ("GIMPLE register modified with BIT_FIELD_REF");
3100           return t;
3101         }
3102       break;
3103
3104     case ADDR_EXPR:
3105       /* Skip any references (they will be checked when we recurse down the
3106          tree) and ensure that any variable used as a prefix is marked
3107          addressable.  */
3108       for (x = TREE_OPERAND (t, 0);
3109            (handled_component_p (x)
3110             || TREE_CODE (x) == REALPART_EXPR
3111             || TREE_CODE (x) == IMAGPART_EXPR);
3112            x = TREE_OPERAND (x, 0))
3113         ;
3114
3115       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3116         return NULL;
3117       if (!TREE_ADDRESSABLE (x))
3118         {
3119           error ("address taken, but ADDRESSABLE bit not set");
3120           return x;
3121         }
3122       break;
3123
3124     case COND_EXPR:
3125       x = TREE_OPERAND (t, 0);
3126       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3127         {
3128           error ("non-boolean used in condition");
3129           return x;
3130         }
3131       break;
3132
3133     case NOP_EXPR:
3134     case CONVERT_EXPR:
3135     case FIX_TRUNC_EXPR:
3136     case FIX_CEIL_EXPR:
3137     case FIX_FLOOR_EXPR:
3138     case FIX_ROUND_EXPR:
3139     case FLOAT_EXPR:
3140     case NEGATE_EXPR:
3141     case ABS_EXPR:
3142     case BIT_NOT_EXPR:
3143     case NON_LVALUE_EXPR:
3144     case TRUTH_NOT_EXPR:
3145       CHECK_OP (0, "Invalid operand to unary operator");
3146       break;
3147
3148     case REALPART_EXPR:
3149     case IMAGPART_EXPR:
3150     case COMPONENT_REF:
3151     case ARRAY_REF:
3152     case ARRAY_RANGE_REF:
3153     case BIT_FIELD_REF:
3154     case VIEW_CONVERT_EXPR:
3155       /* We have a nest of references.  Verify that each of the operands
3156          that determine where to reference is either a constant or a variable,
3157          verify that the base is valid, and then show we've already checked
3158          the subtrees.  */
3159       while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
3160              || handled_component_p (t))
3161         {
3162           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3163             CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3164           else if (TREE_CODE (t) == ARRAY_REF
3165                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3166             {
3167               CHECK_OP (1, "Invalid array index.");
3168               if (TREE_OPERAND (t, 2))
3169                 CHECK_OP (2, "Invalid array lower bound.");
3170               if (TREE_OPERAND (t, 3))
3171                 CHECK_OP (3, "Invalid array stride.");
3172             }
3173           else if (TREE_CODE (t) == BIT_FIELD_REF)
3174             {
3175               CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3176               CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3177             }
3178
3179           t = TREE_OPERAND (t, 0);
3180         }
3181
3182       if (TREE_CODE_CLASS (TREE_CODE (t)) != 'c'
3183           && !is_gimple_lvalue (t))
3184         {
3185           error ("Invalid reference prefix.");
3186           return t;
3187         }
3188       *walk_subtrees = 0;
3189       break;
3190
3191     case LT_EXPR:
3192     case LE_EXPR:
3193     case GT_EXPR:
3194     case GE_EXPR:
3195     case EQ_EXPR:
3196     case NE_EXPR:
3197     case UNORDERED_EXPR:
3198     case ORDERED_EXPR:
3199     case UNLT_EXPR:
3200     case UNLE_EXPR:
3201     case UNGT_EXPR:
3202     case UNGE_EXPR:
3203     case UNEQ_EXPR:
3204     case LTGT_EXPR:
3205     case PLUS_EXPR:
3206     case MINUS_EXPR:
3207     case MULT_EXPR:
3208     case TRUNC_DIV_EXPR:
3209     case CEIL_DIV_EXPR:
3210     case FLOOR_DIV_EXPR:
3211     case ROUND_DIV_EXPR:
3212     case TRUNC_MOD_EXPR:
3213     case CEIL_MOD_EXPR:
3214     case FLOOR_MOD_EXPR:
3215     case ROUND_MOD_EXPR:
3216     case RDIV_EXPR:
3217     case EXACT_DIV_EXPR:
3218     case MIN_EXPR:
3219     case MAX_EXPR:
3220     case LSHIFT_EXPR:
3221     case RSHIFT_EXPR:
3222     case LROTATE_EXPR:
3223     case RROTATE_EXPR:
3224     case BIT_IOR_EXPR:
3225     case BIT_XOR_EXPR:
3226     case BIT_AND_EXPR:
3227       CHECK_OP (0, "Invalid operand to binary operator");
3228       CHECK_OP (1, "Invalid operand to binary operator");
3229       break;
3230
3231     default:
3232       break;
3233     }
3234   return NULL;
3235
3236 #undef CHECK_OP
3237 }
3238
3239
3240 /* Verify STMT, return true if STMT is not in GIMPLE form.
3241    TODO: Implement type checking.  */
3242
3243 static bool
3244 verify_stmt (tree stmt, bool last_in_block)
3245 {
3246   tree addr;
3247
3248   if (!is_gimple_stmt (stmt))
3249     {
3250       error ("Is not a valid GIMPLE statement.");
3251       goto fail;
3252     }
3253
3254   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3255   if (addr)
3256     {
3257       debug_generic_stmt (addr);
3258       return true;
3259     }
3260
3261   /* If the statement is marked as part of an EH region, then it is
3262      expected that the statement could throw.  Verify that when we
3263      have optimizations that simplify statements such that we prove
3264      that they cannot throw, that we update other data structures
3265      to match.  */
3266   if (lookup_stmt_eh_region (stmt) >= 0)
3267     {
3268       if (!tree_could_throw_p (stmt))
3269         {
3270           error ("Statement marked for throw, but doesn't.");
3271           goto fail;
3272         }
3273       if (!last_in_block && tree_can_throw_internal (stmt))
3274         {
3275           error ("Statement marked for throw in middle of block.");
3276           goto fail;
3277         }
3278     }
3279
3280   return false;
3281
3282  fail:
3283   debug_generic_stmt (stmt);
3284   return true;
3285 }
3286
3287
3288 /* Return true when the T can be shared.  */
3289
3290 static bool
3291 tree_node_can_be_shared (tree t)
3292 {
3293   if (TYPE_P (t) || DECL_P (t)
3294       /* We check for constants explicitly since they are not considered
3295          gimple invariants if they overflowed.  */
3296       || TREE_CODE_CLASS (TREE_CODE (t)) == 'c'
3297       || is_gimple_min_invariant (t)
3298       || TREE_CODE (t) == SSA_NAME)
3299     return true;
3300
3301   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3302           /* We check for constants explicitly since they are not considered
3303              gimple invariants if they overflowed.  */
3304           && (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 1))) == 'c'
3305               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3306          || (TREE_CODE (t) == COMPONENT_REF
3307              || TREE_CODE (t) == REALPART_EXPR
3308              || TREE_CODE (t) == IMAGPART_EXPR))
3309     t = TREE_OPERAND (t, 0);
3310
3311   if (DECL_P (t))
3312     return true;
3313
3314   return false;
3315 }
3316
3317
3318 /* Called via walk_trees.  Verify tree sharing.  */
3319
3320 static tree
3321 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3322 {
3323   htab_t htab = (htab_t) data;
3324   void **slot;
3325
3326   if (tree_node_can_be_shared (*tp))
3327     {
3328       *walk_subtrees = false;
3329       return NULL;
3330     }
3331
3332   slot = htab_find_slot (htab, *tp, INSERT);
3333   if (*slot)
3334     return *slot;
3335   *slot = *tp;
3336
3337   return NULL;
3338 }
3339
3340
3341 /* Verify the GIMPLE statement chain.  */
3342
3343 void
3344 verify_stmts (void)
3345 {
3346   basic_block bb;
3347   block_stmt_iterator bsi;
3348   bool err = false;
3349   htab_t htab;
3350   tree addr;
3351
3352   timevar_push (TV_TREE_STMT_VERIFY);
3353   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3354
3355   FOR_EACH_BB (bb)
3356     {
3357       tree phi;
3358       int i;
3359
3360       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3361         {
3362           int phi_num_args = PHI_NUM_ARGS (phi);
3363
3364           for (i = 0; i < phi_num_args; i++)
3365             {
3366               tree t = PHI_ARG_DEF (phi, i);
3367               tree addr;
3368
3369               /* Addressable variables do have SSA_NAMEs but they
3370                  are not considered gimple values.  */
3371               if (TREE_CODE (t) != SSA_NAME
3372                   && TREE_CODE (t) != FUNCTION_DECL
3373                   && !is_gimple_val (t))
3374                 {
3375                   error ("PHI def is not a GIMPLE value");
3376                   debug_generic_stmt (phi);
3377                   debug_generic_stmt (t);
3378                   err |= true;
3379                 }
3380
3381               addr = walk_tree (&t, verify_expr, NULL, NULL);
3382               if (addr)
3383                 {
3384                   debug_generic_stmt (addr);
3385                   err |= true;
3386                 }
3387
3388               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3389               if (addr)
3390                 {
3391                   error ("Incorrect sharing of tree nodes");
3392                   debug_generic_stmt (phi);
3393                   debug_generic_stmt (addr);
3394                   err |= true;
3395                 }
3396             }
3397         }
3398
3399       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3400         {
3401           tree stmt = bsi_stmt (bsi);
3402           bsi_next (&bsi);
3403           err |= verify_stmt (stmt, bsi_end_p (bsi));
3404           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3405           if (addr)
3406             {
3407               error ("Incorrect sharing of tree nodes");
3408               debug_generic_stmt (stmt);
3409               debug_generic_stmt (addr);
3410               err |= true;
3411             }
3412         }
3413     }
3414
3415   if (err)
3416     internal_error ("verify_stmts failed.");
3417
3418   htab_delete (htab);
3419   timevar_pop (TV_TREE_STMT_VERIFY);
3420 }
3421
3422
3423 /* Verifies that the flow information is OK.  */
3424
3425 static int
3426 tree_verify_flow_info (void)
3427 {
3428   int err = 0;
3429   basic_block bb;
3430   block_stmt_iterator bsi;
3431   tree stmt;
3432   edge e;
3433
3434   if (ENTRY_BLOCK_PTR->stmt_list)
3435     {
3436       error ("ENTRY_BLOCK has a statement list associated with it\n");
3437       err = 1;
3438     }
3439
3440   if (EXIT_BLOCK_PTR->stmt_list)
3441     {
3442       error ("EXIT_BLOCK has a statement list associated with it\n");
3443       err = 1;
3444     }
3445
3446   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
3447     if (e->flags & EDGE_FALLTHRU)
3448       {
3449         error ("Fallthru to exit from bb %d\n", e->src->index);
3450         err = 1;
3451       }
3452
3453   FOR_EACH_BB (bb)
3454     {
3455       bool found_ctrl_stmt = false;
3456
3457       /* Skip labels on the start of basic block.  */
3458       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3459         {
3460           if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
3461             break;
3462
3463           if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
3464             {
3465               error ("Label %s to block does not match in bb %d\n",
3466                      IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
3467                      bb->index);
3468               err = 1;
3469             }
3470
3471           if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
3472               != current_function_decl)
3473             {
3474               error ("Label %s has incorrect context in bb %d\n",
3475                      IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
3476                      bb->index);
3477               err = 1;
3478             }
3479         }
3480
3481       /* Verify that body of basic block BB is free of control flow.  */
3482       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3483         {
3484           tree stmt = bsi_stmt (bsi);
3485
3486           if (found_ctrl_stmt)
3487             {
3488               error ("Control flow in the middle of basic block %d\n",
3489                      bb->index);
3490               err = 1;
3491             }
3492
3493           if (stmt_ends_bb_p (stmt))
3494             found_ctrl_stmt = true;
3495
3496           if (TREE_CODE (stmt) == LABEL_EXPR)
3497             {
3498               error ("Label %s in the middle of basic block %d\n",
3499                      IDENTIFIER_POINTER (DECL_NAME (stmt)),
3500                      bb->index);
3501               err = 1;
3502             }
3503         }
3504       bsi = bsi_last (bb);
3505       if (bsi_end_p (bsi))
3506         continue;
3507
3508       stmt = bsi_stmt (bsi);
3509
3510       if (is_ctrl_stmt (stmt))
3511         {
3512           for (e = bb->succ; e; e = e->succ_next)
3513             if (e->flags & EDGE_FALLTHRU)
3514               {
3515                 error ("Fallthru edge after a control statement in bb %d \n",
3516                        bb->index);
3517                 err = 1;
3518               }
3519         }
3520
3521       switch (TREE_CODE (stmt))
3522         {
3523         case COND_EXPR:
3524           {
3525             edge true_edge;
3526             edge false_edge;
3527             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3528                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3529               {
3530                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3531                 err = 1;
3532               }
3533
3534             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3535
3536             if (!true_edge || !false_edge
3537                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3538                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3539                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3540                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3541                 || bb->succ->succ_next->succ_next)
3542               {
3543                 error ("Wrong outgoing edge flags at end of bb %d\n",
3544                        bb->index);
3545                 err = 1;
3546               }
3547
3548             if (!has_label_p (true_edge->dest,
3549                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3550               {
3551                 error ("`then' label does not match edge at end of bb %d\n",
3552                        bb->index);
3553                 err = 1;
3554               }
3555
3556             if (!has_label_p (false_edge->dest,
3557                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3558               {
3559                 error ("`else' label does not match edge at end of bb %d\n",
3560                        bb->index);
3561                 err = 1;
3562               }
3563           }
3564           break;
3565
3566         case GOTO_EXPR:
3567           if (simple_goto_p (stmt))
3568             {
3569               error ("Explicit goto at end of bb %d\n", bb->index);
3570               err = 1;
3571             }
3572           else
3573             {
3574               /* FIXME.  We should double check that the labels in the 
3575                  destination blocks have their address taken.  */
3576               for (e = bb->succ; e; e = e->succ_next)
3577                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3578                                  | EDGE_FALSE_VALUE))
3579                     || !(e->flags & EDGE_ABNORMAL))
3580                   {
3581                     error ("Wrong outgoing edge flags at end of bb %d\n",
3582                            bb->index);
3583                     err = 1;
3584                   }
3585             }
3586           break;
3587
3588         case RETURN_EXPR:
3589           if (!bb->succ || bb->succ->succ_next
3590               || (bb->succ->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3591                                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3592             {
3593               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3594               err = 1;
3595             }
3596           if (bb->succ->dest != EXIT_BLOCK_PTR)
3597             {
3598               error ("Return edge does not point to exit in bb %d\n",
3599                      bb->index);
3600               err = 1;
3601             }
3602           break;
3603
3604         case SWITCH_EXPR:
3605           {
3606             tree prev;
3607             edge e;
3608             size_t i, n;
3609             tree vec;
3610
3611             vec = SWITCH_LABELS (stmt);
3612             n = TREE_VEC_LENGTH (vec);
3613
3614             /* Mark all the destination basic blocks.  */
3615             for (i = 0; i < n; ++i)
3616               {
3617                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3618                 basic_block label_bb = label_to_block (lab);
3619
3620                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3621                 label_bb->aux = (void *)1;
3622               }
3623
3624             /* Verify that the case labels are sorted.  */
3625             prev = TREE_VEC_ELT (vec, 0);
3626             for (i = 1; i < n - 1; ++i)
3627               {
3628                 tree c = TREE_VEC_ELT (vec, i);
3629                 if (! CASE_LOW (c))
3630                   {
3631                     error ("Found default case not at end of case vector");
3632                     err = 1;
3633                     continue;
3634                   }
3635                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3636                   {
3637                     error ("Case labels not sorted:\n ");
3638                     print_generic_expr (stderr, prev, 0);
3639                     fprintf (stderr," is greater than ");
3640                     print_generic_expr (stderr, c, 0);
3641                     fprintf (stderr," but comes before it.\n");
3642                     err = 1;
3643                   }
3644                 prev = c;
3645               }
3646             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3647               {
3648                 error ("No default case found at end of case vector");
3649                 err = 1;
3650               }
3651
3652             for (e = bb->succ; e; e = e->succ_next)
3653               {
3654                 if (!e->dest->aux)
3655                   {
3656                     error ("Extra outgoing edge %d->%d\n",
3657                            bb->index, e->dest->index);
3658                     err = 1;
3659                   }
3660                 e->dest->aux = (void *)2;
3661                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3662                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3663                   {
3664                     error ("Wrong outgoing edge flags at end of bb %d\n",
3665                            bb->index);
3666                     err = 1;
3667                   }
3668               }
3669
3670             /* Check that we have all of them.  */
3671             for (i = 0; i < n; ++i)
3672               {
3673                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3674                 basic_block label_bb = label_to_block (lab);
3675