OSDN Git Service

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