OSDN Git Service

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