OSDN Git Service

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