OSDN Git Service

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