OSDN Git Service

96377ec821ecfeef62ea2004b46a6ea3a5b77832
[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 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
58    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
59    via their TREE_CHAIN field, which we clear after we're done with the
60    hash table to prevent problems with duplication of SWITCH_EXPRs.
61
62    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
63    update the case vector in response to edge redirections.
64
65    Right now this table is set up and torn down at key points in the
66    compilation process.  It would be nice if we could make the table
67    more persistent.  The key is getting notification of changes to
68    the CFG (particularly edge removal, creation and redirection).  */
69
70 struct edge_to_cases_elt
71 {
72   /* The edge itself.  Necessary for hashing and equality tests.  */
73   edge e;
74
75   /* The case labels associated with this edge.  We link these up via
76      their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
77      when we destroy the hash table.  This prevents problems when copying
78      SWITCH_EXPRs.  */
79   tree case_labels;
80 };
81
82 static htab_t edge_to_cases;
83
84 /* CFG statistics.  */
85 struct cfg_stats_d
86 {
87   long num_merged_labels;
88 };
89
90 static struct cfg_stats_d cfg_stats;
91
92 /* Nonzero if we found a computed goto while building basic blocks.  */
93 static bool found_computed_goto;
94
95 /* Basic blocks and flowgraphs.  */
96 static basic_block create_bb (void *, void *, basic_block);
97 static void create_block_annotation (basic_block);
98 static void free_blocks_annotations (void);
99 static void clear_blocks_annotations (void);
100 static void make_blocks (tree);
101 static void factor_computed_gotos (void);
102
103 /* Edges.  */
104 static void make_edges (void);
105 static void make_ctrl_stmt_edges (basic_block);
106 static void make_exit_edges (basic_block);
107 static void make_cond_expr_edges (basic_block);
108 static void make_switch_expr_edges (basic_block);
109 static void make_goto_expr_edges (basic_block);
110 static edge tree_redirect_edge_and_branch (edge, basic_block);
111 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
112 static void split_critical_edges (void);
113 static bool remove_fallthru_edge (VEC(edge,gc) *);
114
115 /* Various helpers.  */
116 static inline bool stmt_starts_bb_p (tree, tree);
117 static int tree_verify_flow_info (void);
118 static void tree_make_forwarder_block (edge);
119 static bool tree_forwarder_block_p (basic_block, bool);
120 static void tree_cfg2vcg (FILE *);
121
122 /* Flowgraph optimization and cleanup.  */
123 static void tree_merge_blocks (basic_block, basic_block);
124 static bool tree_can_merge_blocks_p (basic_block, basic_block);
125 static void remove_bb (basic_block);
126 static bool cleanup_control_flow (void);
127 static bool cleanup_control_expr_graph (basic_block, block_stmt_iterator);
128 static edge find_taken_edge_computed_goto (basic_block, tree);
129 static edge find_taken_edge_cond_expr (basic_block, tree);
130 static edge find_taken_edge_switch_expr (basic_block, tree);
131 static tree find_case_label_for_value (tree, tree);
132 static bool phi_alternatives_equal (basic_block, edge, edge);
133 static bool cleanup_forwarder_blocks (void);
134
135 void
136 init_empty_tree_cfg (void)
137 {
138   /* Initialize the basic block array.  */
139   init_flow ();
140   profile_status = PROFILE_ABSENT;
141   n_basic_blocks = 0;
142   last_basic_block = 0;
143   VARRAY_BB_INIT (basic_block_info, initial_cfg_capacity, "basic_block_info");
144
145   /* Build a mapping of labels to their associated blocks.  */
146   VARRAY_BB_INIT (label_to_block_map, initial_cfg_capacity,
147                   "label to block map");
148
149   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
150   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
151
152   create_block_annotation (ENTRY_BLOCK_PTR);
153   create_block_annotation (EXIT_BLOCK_PTR);
154 }
155
156 /*---------------------------------------------------------------------------
157                               Create basic blocks
158 ---------------------------------------------------------------------------*/
159
160 /* Entry point to the CFG builder for trees.  TP points to the list of
161    statements to be added to the flowgraph.  */
162
163 static void
164 build_tree_cfg (tree *tp)
165 {
166   /* Register specific tree functions.  */
167   tree_register_cfg_hooks ();
168
169   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
170
171   init_empty_tree_cfg ();
172
173   found_computed_goto = 0;
174   make_blocks (*tp);
175
176   /* Computed gotos are hell to deal with, especially if there are
177      lots of them with a large number of destinations.  So we factor
178      them to a common computed goto location before we build the
179      edge list.  After we convert back to normal form, we will un-factor
180      the computed gotos since factoring introduces an unwanted jump.  */
181   if (found_computed_goto)
182     factor_computed_gotos ();
183
184   /* Make sure there is always at least one block, even if it's empty.  */
185   if (n_basic_blocks == 0)
186     create_empty_bb (ENTRY_BLOCK_PTR);
187
188   /* Adjust the size of the array.  */
189   VARRAY_GROW (basic_block_info, n_basic_blocks);
190
191   /* To speed up statement iterator walks, we first purge dead labels.  */
192   cleanup_dead_labels ();
193
194   /* Group case nodes to reduce the number of edges.
195      We do this after cleaning up dead labels because otherwise we miss
196      a lot of obvious case merging opportunities.  */
197   group_case_labels ();
198
199   /* Create the edges of the flowgraph.  */
200   make_edges ();
201
202   /* Debugging dumps.  */
203
204   /* Write the flowgraph to a VCG file.  */
205   {
206     int local_dump_flags;
207     FILE *dump_file = dump_begin (TDI_vcg, &local_dump_flags);
208     if (dump_file)
209       {
210         tree_cfg2vcg (dump_file);
211         dump_end (TDI_vcg, dump_file);
212       }
213   }
214
215 #ifdef ENABLE_CHECKING
216   verify_stmts ();
217 #endif
218
219   /* Dump a textual representation of the flowgraph.  */
220   if (dump_file)
221     dump_tree_cfg (dump_file, dump_flags);
222 }
223
224 static void
225 execute_build_cfg (void)
226 {
227   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
228 }
229
230 struct tree_opt_pass pass_build_cfg =
231 {
232   "cfg",                                /* name */
233   NULL,                                 /* gate */
234   execute_build_cfg,                    /* execute */
235   NULL,                                 /* sub */
236   NULL,                                 /* next */
237   0,                                    /* static_pass_number */
238   TV_TREE_CFG,                          /* tv_id */
239   PROP_gimple_leh,                      /* properties_required */
240   PROP_cfg,                             /* properties_provided */
241   0,                                    /* properties_destroyed */
242   0,                                    /* todo_flags_start */
243   TODO_verify_stmts,                    /* todo_flags_finish */
244   0                                     /* letter */
245 };
246
247 /* Search the CFG for any computed gotos.  If found, factor them to a 
248    common computed goto site.  Also record the location of that site so
249    that we can un-factor the gotos after we have converted back to 
250    normal form.  */
251
252 static void
253 factor_computed_gotos (void)
254 {
255   basic_block bb;
256   tree factored_label_decl = NULL;
257   tree var = NULL;
258   tree factored_computed_goto_label = NULL;
259   tree factored_computed_goto = NULL;
260
261   /* We know there are one or more computed gotos in this function.
262      Examine the last statement in each basic block to see if the block
263      ends with a computed goto.  */
264         
265   FOR_EACH_BB (bb)
266     {
267       block_stmt_iterator bsi = bsi_last (bb);
268       tree last;
269
270       if (bsi_end_p (bsi))
271         continue;
272       last = bsi_stmt (bsi);
273
274       /* Ignore the computed goto we create when we factor the original
275          computed gotos.  */
276       if (last == factored_computed_goto)
277         continue;
278
279       /* If the last statement is a computed goto, factor it.  */
280       if (computed_goto_p (last))
281         {
282           tree assignment;
283
284           /* The first time we find a computed goto we need to create
285              the factored goto block and the variable each original
286              computed goto will use for their goto destination.  */
287           if (! factored_computed_goto)
288             {
289               basic_block new_bb = create_empty_bb (bb);
290               block_stmt_iterator new_bsi = bsi_start (new_bb);
291
292               /* Create the destination of the factored goto.  Each original
293                  computed goto will put its desired destination into this
294                  variable and jump to the label we create immediately
295                  below.  */
296               var = create_tmp_var (ptr_type_node, "gotovar");
297
298               /* Build a label for the new block which will contain the
299                  factored computed goto.  */
300               factored_label_decl = create_artificial_label ();
301               factored_computed_goto_label
302                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
303               bsi_insert_after (&new_bsi, factored_computed_goto_label,
304                                 BSI_NEW_STMT);
305
306               /* Build our new computed goto.  */
307               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
308               bsi_insert_after (&new_bsi, factored_computed_goto,
309                                 BSI_NEW_STMT);
310             }
311
312           /* Copy the original computed goto's destination into VAR.  */
313           assignment = build (MODIFY_EXPR, ptr_type_node,
314                               var, GOTO_DESTINATION (last));
315           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
316
317           /* And re-vector the computed goto to the new destination.  */
318           GOTO_DESTINATION (last) = factored_label_decl;
319         }
320     }
321 }
322
323
324 /* Create annotations for a single basic block.  */
325
326 static void
327 create_block_annotation (basic_block bb)
328 {
329   /* Verify that the tree_annotations field is clear.  */
330   gcc_assert (!bb->tree_annotations);
331   bb->tree_annotations = ggc_alloc_cleared (sizeof (struct bb_ann_d));
332 }
333
334
335 /* Free the annotations for all the basic blocks.  */
336
337 static void free_blocks_annotations (void)
338 {
339   clear_blocks_annotations ();  
340 }
341
342
343 /* Clear the annotations for all the basic blocks.  */
344
345 static void
346 clear_blocks_annotations (void)
347 {
348   basic_block bb;
349
350   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
351     bb->tree_annotations = NULL;
352 }
353
354
355 /* Build a flowgraph for the statement_list STMT_LIST.  */
356
357 static void
358 make_blocks (tree stmt_list)
359 {
360   tree_stmt_iterator i = tsi_start (stmt_list);
361   tree stmt = NULL;
362   bool start_new_block = true;
363   bool first_stmt_of_list = true;
364   basic_block bb = ENTRY_BLOCK_PTR;
365
366   while (!tsi_end_p (i))
367     {
368       tree prev_stmt;
369
370       prev_stmt = stmt;
371       stmt = tsi_stmt (i);
372
373       /* If the statement starts a new basic block or if we have determined
374          in a previous pass that we need to create a new block for STMT, do
375          so now.  */
376       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
377         {
378           if (!first_stmt_of_list)
379             stmt_list = tsi_split_statement_list_before (&i);
380           bb = create_basic_block (stmt_list, NULL, bb);
381           start_new_block = false;
382         }
383
384       /* Now add STMT to BB and create the subgraphs for special statement
385          codes.  */
386       set_bb_for_stmt (stmt, bb);
387
388       if (computed_goto_p (stmt))
389         found_computed_goto = true;
390
391       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
392          next iteration.  */
393       if (stmt_ends_bb_p (stmt))
394         start_new_block = true;
395
396       tsi_next (&i);
397       first_stmt_of_list = false;
398     }
399 }
400
401
402 /* Create and return a new empty basic block after bb AFTER.  */
403
404 static basic_block
405 create_bb (void *h, void *e, basic_block after)
406 {
407   basic_block bb;
408
409   gcc_assert (!e);
410
411   /* Create and initialize a new basic block.  Since alloc_block uses
412      ggc_alloc_cleared to allocate a basic block, we do not have to
413      clear the newly allocated basic block here.  */
414   bb = alloc_block ();
415
416   bb->index = last_basic_block;
417   bb->flags = BB_NEW;
418   bb->stmt_list = h ? h : alloc_stmt_list ();
419
420   /* Add the new block to the linked list of blocks.  */
421   link_block (bb, after);
422
423   /* Grow the basic block array if needed.  */
424   if ((size_t) last_basic_block == VARRAY_SIZE (basic_block_info))
425     {
426       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
427       VARRAY_GROW (basic_block_info, new_size);
428     }
429
430   /* Add the newly created block to the array.  */
431   BASIC_BLOCK (last_basic_block) = bb;
432
433   create_block_annotation (bb);
434
435   n_basic_blocks++;
436   last_basic_block++;
437
438   initialize_bb_rbi (bb);
439   return bb;
440 }
441
442
443 /*---------------------------------------------------------------------------
444                                  Edge creation
445 ---------------------------------------------------------------------------*/
446
447 /* Fold COND_EXPR_COND of each COND_EXPR.  */
448
449 static void
450 fold_cond_expr_cond (void)
451 {
452   basic_block bb;
453
454   FOR_EACH_BB (bb)
455     {
456       tree stmt = last_stmt (bb);
457
458       if (stmt
459           && TREE_CODE (stmt) == COND_EXPR)
460         {
461           tree cond = fold (COND_EXPR_COND (stmt));
462           if (integer_zerop (cond))
463             COND_EXPR_COND (stmt) = boolean_false_node;
464           else if (integer_onep (cond))
465             COND_EXPR_COND (stmt) = boolean_true_node;
466         }
467     }
468 }
469
470 /* Join all the blocks in the flowgraph.  */
471
472 static void
473 make_edges (void)
474 {
475   basic_block bb;
476
477   /* Create an edge from entry to the first block with executable
478      statements in it.  */
479   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
480
481   /* Traverse the basic block array placing edges.  */
482   FOR_EACH_BB (bb)
483     {
484       tree first = first_stmt (bb);
485       tree last = last_stmt (bb);
486
487       if (first)
488         {
489           /* Edges for statements that always alter flow control.  */
490           if (is_ctrl_stmt (last))
491             make_ctrl_stmt_edges (bb);
492
493           /* Edges for statements that sometimes alter flow control.  */
494           if (is_ctrl_altering_stmt (last))
495             make_exit_edges (bb);
496         }
497
498       /* Finally, if no edges were created above, this is a regular
499          basic block that only needs a fallthru edge.  */
500       if (EDGE_COUNT (bb->succs) == 0)
501         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
502     }
503
504   /* We do not care about fake edges, so remove any that the CFG
505      builder inserted for completeness.  */
506   remove_fake_exit_edges ();
507
508   /* Fold COND_EXPR_COND of each COND_EXPR.  */
509   fold_cond_expr_cond ();
510
511   /* Clean up the graph and warn for unreachable code.  */
512   cleanup_tree_cfg ();
513 }
514
515
516 /* Create edges for control statement at basic block BB.  */
517
518 static void
519 make_ctrl_stmt_edges (basic_block bb)
520 {
521   tree last = last_stmt (bb);
522
523   gcc_assert (last);
524   switch (TREE_CODE (last))
525     {
526     case GOTO_EXPR:
527       make_goto_expr_edges (bb);
528       break;
529
530     case RETURN_EXPR:
531       make_edge (bb, EXIT_BLOCK_PTR, 0);
532       break;
533
534     case COND_EXPR:
535       make_cond_expr_edges (bb);
536       break;
537
538     case SWITCH_EXPR:
539       make_switch_expr_edges (bb);
540       break;
541
542     case RESX_EXPR:
543       make_eh_edges (last);
544       /* Yet another NORETURN hack.  */
545       if (EDGE_COUNT (bb->succs) == 0)
546         make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
547       break;
548
549     default:
550       gcc_unreachable ();
551     }
552 }
553
554
555 /* Create exit edges for statements in block BB that alter the flow of
556    control.  Statements that alter the control flow are 'goto', 'return'
557    and calls to non-returning functions.  */
558
559 static void
560 make_exit_edges (basic_block bb)
561 {
562   tree last = last_stmt (bb), op;
563
564   gcc_assert (last);
565   switch (TREE_CODE (last))
566     {
567     case RESX_EXPR:
568       break;
569     case CALL_EXPR:
570       /* If this function receives a nonlocal goto, then we need to
571          make edges from this call site to all the nonlocal goto
572          handlers.  */
573       if (TREE_SIDE_EFFECTS (last)
574           && current_function_has_nonlocal_label)
575         make_goto_expr_edges (bb);
576
577       /* If this statement has reachable exception handlers, then
578          create abnormal edges to them.  */
579       make_eh_edges (last);
580
581       /* Some calls are known not to return.  For such calls we create
582          a fake edge.
583
584          We really need to revamp how we build edges so that it's not
585          such a bloody pain to avoid creating edges for this case since
586          all we do is remove these edges when we're done building the
587          CFG.  */
588       if (call_expr_flags (last) & ECF_NORETURN)
589         {
590           make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
591           return;
592         }
593
594       /* Don't forget the fall-thru edge.  */
595       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
596       break;
597
598     case MODIFY_EXPR:
599       /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
600          may have an abnormal edge.  Search the RHS for this case and
601          create any required edges.  */
602       op = get_call_expr_in (last);
603       if (op && TREE_SIDE_EFFECTS (op)
604           && current_function_has_nonlocal_label)
605         make_goto_expr_edges (bb);
606
607       make_eh_edges (last);
608       make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
609       break;
610
611     default:
612       gcc_unreachable ();
613     }
614 }
615
616
617 /* Create the edges for a COND_EXPR starting at block BB.
618    At this point, both clauses must contain only simple gotos.  */
619
620 static void
621 make_cond_expr_edges (basic_block bb)
622 {
623   tree entry = last_stmt (bb);
624   basic_block then_bb, else_bb;
625   tree then_label, else_label;
626
627   gcc_assert (entry);
628   gcc_assert (TREE_CODE (entry) == COND_EXPR);
629
630   /* Entry basic blocks for each component.  */
631   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
632   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
633   then_bb = label_to_block (then_label);
634   else_bb = label_to_block (else_label);
635
636   make_edge (bb, then_bb, EDGE_TRUE_VALUE);
637   make_edge (bb, else_bb, EDGE_FALSE_VALUE);
638 }
639
640 /* Hashing routine for EDGE_TO_CASES.  */
641
642 static hashval_t
643 edge_to_cases_hash (const void *p)
644 {
645   edge e = ((struct edge_to_cases_elt *)p)->e;
646
647   /* Hash on the edge itself (which is a pointer).  */
648   return htab_hash_pointer (e);
649 }
650
651 /* Equality routine for EDGE_TO_CASES, edges are unique, so testing
652    for equality is just a pointer comparison.  */
653
654 static int
655 edge_to_cases_eq (const void *p1, const void *p2)
656 {
657   edge e1 = ((struct edge_to_cases_elt *)p1)->e;
658   edge e2 = ((struct edge_to_cases_elt *)p2)->e;
659
660   return e1 == e2;
661 }
662
663 /* Called for each element in the hash table (P) as we delete the
664    edge to cases hash table.
665
666    Clear all the TREE_CHAINs to prevent problems with copying of 
667    SWITCH_EXPRs and structure sharing rules, then free the hash table
668    element.  */
669
670 static void
671 edge_to_cases_cleanup (void *p)
672 {
673   struct edge_to_cases_elt *elt = p;
674   tree t, next;
675
676   for (t = elt->case_labels; t; t = next)
677     {
678       next = TREE_CHAIN (t);
679       TREE_CHAIN (t) = NULL;
680     }
681   free (p);
682 }
683
684 /* Start recording information mapping edges to case labels.  */
685
686 static void
687 start_recording_case_labels (void)
688 {
689   gcc_assert (edge_to_cases == NULL);
690
691   edge_to_cases = htab_create (37,
692                                edge_to_cases_hash,
693                                edge_to_cases_eq,
694                                edge_to_cases_cleanup);
695 }
696
697 /* Return nonzero if we are recording information for case labels.  */
698
699 static bool
700 recording_case_labels_p (void)
701 {
702   return (edge_to_cases != NULL);
703 }
704
705 /* Stop recording information mapping edges to case labels and
706    remove any information we have recorded.  */
707 static void
708 end_recording_case_labels (void)
709 {
710   htab_delete (edge_to_cases);
711   edge_to_cases = NULL;
712 }
713
714 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
715
716 static void
717 record_switch_edge (edge e, tree case_label)
718 {
719   struct edge_to_cases_elt *elt;
720   void **slot;
721
722   /* Build a hash table element so we can see if E is already
723      in the table.  */
724   elt = xmalloc (sizeof (struct edge_to_cases_elt));
725   elt->e = e;
726   elt->case_labels = case_label;
727
728   slot = htab_find_slot (edge_to_cases, elt, INSERT);
729
730   if (*slot == NULL)
731     {
732       /* E was not in the hash table.  Install E into the hash table.  */
733       *slot = (void *)elt;
734     }
735   else
736     {
737       /* E was already in the hash table.  Free ELT as we do not need it
738          anymore.  */
739       free (elt);
740
741       /* Get the entry stored in the hash table.  */
742       elt = (struct edge_to_cases_elt *) *slot;
743
744       /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
745       TREE_CHAIN (case_label) = elt->case_labels;
746       elt->case_labels = case_label;
747     }
748 }
749
750 /* If we are inside a {start,end}_recording_cases block, then return
751    a chain of CASE_LABEL_EXPRs from T which reference E.
752
753    Otherwise return NULL.  */
754
755 static tree
756 get_cases_for_edge (edge e, tree t)
757 {
758   struct edge_to_cases_elt elt, *elt_p;
759   void **slot;
760   size_t i, n;
761   tree vec;
762
763   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
764      chains available.  Return NULL so the caller can detect this case.  */
765   if (!recording_case_labels_p ())
766     return NULL;
767   
768 restart:
769   elt.e = e;
770   elt.case_labels = NULL;
771   slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
772
773   if (slot)
774     {
775       elt_p = (struct edge_to_cases_elt *)*slot;
776       return elt_p->case_labels;
777     }
778
779   /* If we did not find E in the hash table, then this must be the first
780      time we have been queried for information about E & T.  Add all the
781      elements from T to the hash table then perform the query again.  */
782
783   vec = SWITCH_LABELS (t);
784   n = TREE_VEC_LENGTH (vec);
785   for (i = 0; i < n; i++)
786     {
787       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
788       basic_block label_bb = label_to_block (lab);
789       record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
790     }
791   goto restart;
792 }
793
794 /* Create the edges for a SWITCH_EXPR starting at block BB.
795    At this point, the switch body has been lowered and the
796    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
797
798 static void
799 make_switch_expr_edges (basic_block bb)
800 {
801   tree entry = last_stmt (bb);
802   size_t i, n;
803   tree vec;
804
805   vec = SWITCH_LABELS (entry);
806   n = TREE_VEC_LENGTH (vec);
807
808   for (i = 0; i < n; ++i)
809     {
810       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
811       basic_block label_bb = label_to_block (lab);
812       make_edge (bb, label_bb, 0);
813     }
814 }
815
816
817 /* Return the basic block holding label DEST.  */
818
819 basic_block
820 label_to_block_fn (struct function *ifun, tree dest)
821 {
822   int uid = LABEL_DECL_UID (dest);
823
824   /* We would die hard when faced by an undefined label.  Emit a label to
825      the very first basic block.  This will hopefully make even the dataflow
826      and undefined variable warnings quite right.  */
827   if ((errorcount || sorrycount) && uid < 0)
828     {
829       block_stmt_iterator bsi = bsi_start (BASIC_BLOCK (0));
830       tree stmt;
831
832       stmt = build1 (LABEL_EXPR, void_type_node, dest);
833       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
834       uid = LABEL_DECL_UID (dest);
835     }
836   if (VARRAY_SIZE (ifun->cfg->x_label_to_block_map) <= (unsigned int)uid)
837     return NULL;
838   return VARRAY_BB (ifun->cfg->x_label_to_block_map, uid);
839 }
840
841 /* Create edges for a goto statement at block BB.  */
842
843 static void
844 make_goto_expr_edges (basic_block bb)
845 {
846   tree goto_t;
847   basic_block target_bb;
848   int for_call;
849   block_stmt_iterator last = bsi_last (bb);
850
851   goto_t = bsi_stmt (last);
852
853   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
854      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
855      from a nonlocal goto.  */
856   if (TREE_CODE (goto_t) != GOTO_EXPR)
857     for_call = 1;
858   else
859     {
860       tree dest = GOTO_DESTINATION (goto_t);
861       for_call = 0;
862
863       /* A GOTO to a local label creates normal edges.  */
864       if (simple_goto_p (goto_t))
865         {
866           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
867 #ifdef USE_MAPPED_LOCATION
868           e->goto_locus = EXPR_LOCATION (goto_t);
869 #else
870           e->goto_locus = EXPR_LOCUS (goto_t);
871 #endif
872           bsi_remove (&last);
873           return;
874         }
875
876       /* Nothing more to do for nonlocal gotos.  */
877       if (TREE_CODE (dest) == LABEL_DECL)
878         return;
879
880       /* Computed gotos remain.  */
881     }
882
883   /* Look for the block starting with the destination label.  In the
884      case of a computed goto, make an edge to any label block we find
885      in the CFG.  */
886   FOR_EACH_BB (target_bb)
887     {
888       block_stmt_iterator bsi;
889
890       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
891         {
892           tree target = bsi_stmt (bsi);
893
894           if (TREE_CODE (target) != LABEL_EXPR)
895             break;
896
897           if (
898               /* Computed GOTOs.  Make an edge to every label block that has
899                  been marked as a potential target for a computed goto.  */
900               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && for_call == 0)
901               /* Nonlocal GOTO target.  Make an edge to every label block
902                  that has been marked as a potential target for a nonlocal
903                  goto.  */
904               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call == 1))
905             {
906               make_edge (bb, target_bb, EDGE_ABNORMAL);
907               break;
908             }
909         }
910     }
911
912   /* Degenerate case of computed goto with no labels.  */
913   if (!for_call && EDGE_COUNT (bb->succs) == 0)
914     make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
915 }
916
917
918 /*---------------------------------------------------------------------------
919                                Flowgraph analysis
920 ---------------------------------------------------------------------------*/
921
922 /* Remove unreachable blocks and other miscellaneous clean up work.  */
923
924 bool
925 cleanup_tree_cfg (void)
926 {
927   bool retval = false;
928
929   timevar_push (TV_TREE_CLEANUP_CFG);
930
931   retval = cleanup_control_flow ();
932   retval |= delete_unreachable_blocks ();
933
934   /* cleanup_forwarder_blocks can redirect edges out of SWITCH_EXPRs,
935      which can get expensive.  So we want to enable recording of edge
936      to CASE_LABEL_EXPR mappings around the call to
937      cleanup_forwarder_blocks.  */
938   start_recording_case_labels ();
939   retval |= cleanup_forwarder_blocks ();
940   end_recording_case_labels ();
941
942 #ifdef ENABLE_CHECKING
943   if (retval)
944     {
945       gcc_assert (!cleanup_control_flow ());
946       gcc_assert (!delete_unreachable_blocks ());
947       gcc_assert (!cleanup_forwarder_blocks ());
948     }
949 #endif
950
951   /* Merging the blocks creates no new opportunities for the other
952      optimizations, so do it here.  */
953   retval |= merge_seq_blocks ();
954
955   compact_blocks ();
956
957 #ifdef ENABLE_CHECKING
958   verify_flow_info ();
959 #endif
960   timevar_pop (TV_TREE_CLEANUP_CFG);
961   return retval;
962 }
963
964
965 /* Cleanup cfg and repair loop structures.  */
966
967 void
968 cleanup_tree_cfg_loop (void)
969 {
970   bitmap changed_bbs = BITMAP_ALLOC (NULL);
971
972   cleanup_tree_cfg ();
973
974   fix_loop_structure (current_loops, changed_bbs);
975   calculate_dominance_info (CDI_DOMINATORS);
976
977   /* This usually does nothing.  But sometimes parts of cfg that originally
978      were inside a loop get out of it due to edge removal (since they
979      become unreachable by back edges from latch).  */
980   rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa);
981
982   BITMAP_FREE (changed_bbs);
983
984 #ifdef ENABLE_CHECKING
985   verify_loop_structure (current_loops);
986 #endif
987 }
988
989 /* Cleanup useless labels in basic blocks.  This is something we wish
990    to do early because it allows us to group case labels before creating
991    the edges for the CFG, and it speeds up block statement iterators in
992    all passes later on.
993    We only run this pass once, running it more than once is probably not
994    profitable.  */
995
996 /* A map from basic block index to the leading label of that block.  */
997 static tree *label_for_bb;
998
999 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
1000 static void
1001 update_eh_label (struct eh_region *region)
1002 {
1003   tree old_label = get_eh_region_tree_label (region);
1004   if (old_label)
1005     {
1006       tree new_label;
1007       basic_block bb = label_to_block (old_label);
1008
1009       /* ??? After optimizing, there may be EH regions with labels
1010          that have already been removed from the function body, so
1011          there is no basic block for them.  */
1012       if (! bb)
1013         return;
1014
1015       new_label = label_for_bb[bb->index];
1016       set_eh_region_tree_label (region, new_label);
1017     }
1018 }
1019
1020 /* Given LABEL return the first label in the same basic block.  */
1021 static tree
1022 main_block_label (tree label)
1023 {
1024   basic_block bb = label_to_block (label);
1025
1026   /* label_to_block possibly inserted undefined label into the chain.  */
1027   if (!label_for_bb[bb->index])
1028     label_for_bb[bb->index] = label;
1029   return label_for_bb[bb->index];
1030 }
1031
1032 /* Cleanup redundant labels.  This is a three-step process:
1033      1) Find the leading label for each block.
1034      2) Redirect all references to labels to the leading labels.
1035      3) Cleanup all useless labels.  */
1036
1037 void
1038 cleanup_dead_labels (void)
1039 {
1040   basic_block bb;
1041   label_for_bb = xcalloc (last_basic_block, sizeof (tree));
1042
1043   /* Find a suitable label for each block.  We use the first user-defined
1044      label if there is one, or otherwise just the first label we see.  */
1045   FOR_EACH_BB (bb)
1046     {
1047       block_stmt_iterator i;
1048
1049       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
1050         {
1051           tree label, stmt = bsi_stmt (i);
1052
1053           if (TREE_CODE (stmt) != LABEL_EXPR)
1054             break;
1055
1056           label = LABEL_EXPR_LABEL (stmt);
1057
1058           /* If we have not yet seen a label for the current block,
1059              remember this one and see if there are more labels.  */
1060           if (! label_for_bb[bb->index])
1061             {
1062               label_for_bb[bb->index] = label;
1063               continue;
1064             }
1065
1066           /* If we did see a label for the current block already, but it
1067              is an artificially created label, replace it if the current
1068              label is a user defined label.  */
1069           if (! DECL_ARTIFICIAL (label)
1070               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
1071             {
1072               label_for_bb[bb->index] = label;
1073               break;
1074             }
1075         }
1076     }
1077
1078   /* Now redirect all jumps/branches to the selected label.
1079      First do so for each block ending in a control statement.  */
1080   FOR_EACH_BB (bb)
1081     {
1082       tree stmt = last_stmt (bb);
1083       if (!stmt)
1084         continue;
1085
1086       switch (TREE_CODE (stmt))
1087         {
1088         case COND_EXPR:
1089           {
1090             tree true_branch, false_branch;
1091
1092             true_branch = COND_EXPR_THEN (stmt);
1093             false_branch = COND_EXPR_ELSE (stmt);
1094
1095             GOTO_DESTINATION (true_branch)
1096               = main_block_label (GOTO_DESTINATION (true_branch));
1097             GOTO_DESTINATION (false_branch)
1098               = main_block_label (GOTO_DESTINATION (false_branch));
1099
1100             break;
1101           }
1102   
1103         case SWITCH_EXPR:
1104           {
1105             size_t i;
1106             tree vec = SWITCH_LABELS (stmt);
1107             size_t n = TREE_VEC_LENGTH (vec);
1108   
1109             /* Replace all destination labels.  */
1110             for (i = 0; i < n; ++i)
1111               {
1112                 tree elt = TREE_VEC_ELT (vec, i);
1113                 tree label = main_block_label (CASE_LABEL (elt));
1114                 CASE_LABEL (elt) = label;
1115               }
1116             break;
1117           }
1118
1119         /* We have to handle GOTO_EXPRs until they're removed, and we don't
1120            remove them until after we've created the CFG edges.  */
1121         case GOTO_EXPR:
1122           if (! computed_goto_p (stmt))
1123             {
1124               GOTO_DESTINATION (stmt)
1125                 = main_block_label (GOTO_DESTINATION (stmt));
1126               break;
1127             }
1128
1129         default:
1130           break;
1131       }
1132     }
1133
1134   for_each_eh_region (update_eh_label);
1135
1136   /* Finally, purge dead labels.  All user-defined labels and labels that
1137      can be the target of non-local gotos are preserved.  */
1138   FOR_EACH_BB (bb)
1139     {
1140       block_stmt_iterator i;
1141       tree label_for_this_bb = label_for_bb[bb->index];
1142
1143       if (! label_for_this_bb)
1144         continue;
1145
1146       for (i = bsi_start (bb); !bsi_end_p (i); )
1147         {
1148           tree label, stmt = bsi_stmt (i);
1149
1150           if (TREE_CODE (stmt) != LABEL_EXPR)
1151             break;
1152
1153           label = LABEL_EXPR_LABEL (stmt);
1154
1155           if (label == label_for_this_bb
1156               || ! DECL_ARTIFICIAL (label)
1157               || DECL_NONLOCAL (label))
1158             bsi_next (&i);
1159           else
1160             bsi_remove (&i);
1161         }
1162     }
1163
1164   free (label_for_bb);
1165 }
1166
1167 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1168    and scan the sorted vector of cases.  Combine the ones jumping to the
1169    same label.
1170    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1171
1172 void
1173 group_case_labels (void)
1174 {
1175   basic_block bb;
1176
1177   FOR_EACH_BB (bb)
1178     {
1179       tree stmt = last_stmt (bb);
1180       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1181         {
1182           tree labels = SWITCH_LABELS (stmt);
1183           int old_size = TREE_VEC_LENGTH (labels);
1184           int i, j, new_size = old_size;
1185           tree default_case = TREE_VEC_ELT (labels, old_size - 1);
1186           tree default_label;
1187
1188           /* The default label is always the last case in a switch
1189              statement after gimplification.  */
1190           default_label = CASE_LABEL (default_case);
1191
1192           /* Look for possible opportunities to merge cases.
1193              Ignore the last element of the label vector because it
1194              must be the default case.  */
1195           i = 0;
1196           while (i < old_size - 1)
1197             {
1198               tree base_case, base_label, base_high;
1199               base_case = TREE_VEC_ELT (labels, i);
1200
1201               gcc_assert (base_case);
1202               base_label = CASE_LABEL (base_case);
1203
1204               /* Discard cases that have the same destination as the
1205                  default case.  */
1206               if (base_label == default_label)
1207                 {
1208                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1209                   i++;
1210                   new_size--;
1211                   continue;
1212                 }
1213
1214               base_high = CASE_HIGH (base_case) ?
1215                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1216               i++;
1217               /* Try to merge case labels.  Break out when we reach the end
1218                  of the label vector or when we cannot merge the next case
1219                  label with the current one.  */
1220               while (i < old_size - 1)
1221                 {
1222                   tree merge_case = TREE_VEC_ELT (labels, i);
1223                   tree merge_label = CASE_LABEL (merge_case);
1224                   tree t = int_const_binop (PLUS_EXPR, base_high,
1225                                             integer_one_node, 1);
1226
1227                   /* Merge the cases if they jump to the same place,
1228                      and their ranges are consecutive.  */
1229                   if (merge_label == base_label
1230                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1231                     {
1232                       base_high = CASE_HIGH (merge_case) ?
1233                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1234                       CASE_HIGH (base_case) = base_high;
1235                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1236                       new_size--;
1237                       i++;
1238                     }
1239                   else
1240                     break;
1241                 }
1242             }
1243
1244           /* Compress the case labels in the label vector, and adjust the
1245              length of the vector.  */
1246           for (i = 0, j = 0; i < new_size; i++)
1247             {
1248               while (! TREE_VEC_ELT (labels, j))
1249                 j++;
1250               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1251             }
1252           TREE_VEC_LENGTH (labels) = new_size;
1253         }
1254     }
1255 }
1256
1257 /* Checks whether we can merge block B into block A.  */
1258
1259 static bool
1260 tree_can_merge_blocks_p (basic_block a, basic_block b)
1261 {
1262   tree stmt;
1263   block_stmt_iterator bsi;
1264
1265   if (!single_succ_p (a))
1266     return false;
1267
1268   if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1269     return false;
1270
1271   if (single_succ (a) != b)
1272     return false;
1273
1274   if (!single_pred_p (b))
1275     return false;
1276
1277   if (b == EXIT_BLOCK_PTR)
1278     return false;
1279   
1280   /* If A ends by a statement causing exceptions or something similar, we
1281      cannot merge the blocks.  */
1282   stmt = last_stmt (a);
1283   if (stmt && stmt_ends_bb_p (stmt))
1284     return false;
1285
1286   /* Do not allow a block with only a non-local label to be merged.  */
1287   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1288       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1289     return false;
1290
1291   /* There may be no PHI nodes at the start of B.  */
1292   if (phi_nodes (b))
1293     return false;
1294
1295   /* Do not remove user labels.  */
1296   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1297     {
1298       stmt = bsi_stmt (bsi);
1299       if (TREE_CODE (stmt) != LABEL_EXPR)
1300         break;
1301       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1302         return false;
1303     }
1304
1305   /* Protect the loop latches.  */
1306   if (current_loops
1307       && b->loop_father->latch == b)
1308     return false;
1309
1310   return true;
1311 }
1312
1313
1314 /* Merge block B into block A.  */
1315
1316 static void
1317 tree_merge_blocks (basic_block a, basic_block b)
1318 {
1319   block_stmt_iterator bsi;
1320   tree_stmt_iterator last;
1321
1322   if (dump_file)
1323     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1324
1325   /* Ensure that B follows A.  */
1326   move_block_after (b, a);
1327
1328   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1329   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1330
1331   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1332   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1333     {
1334       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1335         {
1336           tree label = bsi_stmt (bsi);
1337
1338           bsi_remove (&bsi);
1339           /* Now that we can thread computed gotos, we might have
1340              a situation where we have a forced label in block B
1341              However, the label at the start of block B might still be
1342              used in other ways (think about the runtime checking for
1343              Fortran assigned gotos).  So we can not just delete the
1344              label.  Instead we move the label to the start of block A.  */
1345           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1346             {
1347               block_stmt_iterator dest_bsi = bsi_start (a);
1348               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1349             }
1350         }
1351       else
1352         {
1353           set_bb_for_stmt (bsi_stmt (bsi), a);
1354           bsi_next (&bsi);
1355         }
1356     }
1357
1358   /* Merge the chains.  */
1359   last = tsi_last (a->stmt_list);
1360   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1361   b->stmt_list = NULL;
1362 }
1363
1364
1365 /* Walk the function tree removing unnecessary statements.
1366
1367      * Empty statement nodes are removed
1368
1369      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1370
1371      * Unnecessary COND_EXPRs are removed
1372
1373      * Some unnecessary BIND_EXPRs are removed
1374
1375    Clearly more work could be done.  The trick is doing the analysis
1376    and removal fast enough to be a net improvement in compile times.
1377
1378    Note that when we remove a control structure such as a COND_EXPR
1379    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1380    to ensure we eliminate all the useless code.  */
1381
1382 struct rus_data
1383 {
1384   tree *last_goto;
1385   bool repeat;
1386   bool may_throw;
1387   bool may_branch;
1388   bool has_label;
1389 };
1390
1391 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1392
1393 static bool
1394 remove_useless_stmts_warn_notreached (tree stmt)
1395 {
1396   if (EXPR_HAS_LOCATION (stmt))
1397     {
1398       location_t loc = EXPR_LOCATION (stmt);
1399       if (LOCATION_LINE (loc) > 0)
1400         {
1401           warning (0, "%Hwill never be executed", &loc);
1402           return true;
1403         }
1404     }
1405
1406   switch (TREE_CODE (stmt))
1407     {
1408     case STATEMENT_LIST:
1409       {
1410         tree_stmt_iterator i;
1411         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1412           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1413             return true;
1414       }
1415       break;
1416
1417     case COND_EXPR:
1418       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1419         return true;
1420       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1421         return true;
1422       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1423         return true;
1424       break;
1425
1426     case TRY_FINALLY_EXPR:
1427     case TRY_CATCH_EXPR:
1428       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1429         return true;
1430       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1431         return true;
1432       break;
1433
1434     case CATCH_EXPR:
1435       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1436     case EH_FILTER_EXPR:
1437       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1438     case BIND_EXPR:
1439       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1440
1441     default:
1442       /* Not a live container.  */
1443       break;
1444     }
1445
1446   return false;
1447 }
1448
1449 static void
1450 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1451 {
1452   tree then_clause, else_clause, cond;
1453   bool save_has_label, then_has_label, else_has_label;
1454
1455   save_has_label = data->has_label;
1456   data->has_label = false;
1457   data->last_goto = NULL;
1458
1459   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1460
1461   then_has_label = data->has_label;
1462   data->has_label = false;
1463   data->last_goto = NULL;
1464
1465   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1466
1467   else_has_label = data->has_label;
1468   data->has_label = save_has_label | then_has_label | else_has_label;
1469
1470   then_clause = COND_EXPR_THEN (*stmt_p);
1471   else_clause = COND_EXPR_ELSE (*stmt_p);
1472   cond = fold (COND_EXPR_COND (*stmt_p));
1473
1474   /* If neither arm does anything at all, we can remove the whole IF.  */
1475   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1476     {
1477       *stmt_p = build_empty_stmt ();
1478       data->repeat = true;
1479     }
1480
1481   /* If there are no reachable statements in an arm, then we can
1482      zap the entire conditional.  */
1483   else if (integer_nonzerop (cond) && !else_has_label)
1484     {
1485       if (warn_notreached)
1486         remove_useless_stmts_warn_notreached (else_clause);
1487       *stmt_p = then_clause;
1488       data->repeat = true;
1489     }
1490   else if (integer_zerop (cond) && !then_has_label)
1491     {
1492       if (warn_notreached)
1493         remove_useless_stmts_warn_notreached (then_clause);
1494       *stmt_p = else_clause;
1495       data->repeat = true;
1496     }
1497
1498   /* Check a couple of simple things on then/else with single stmts.  */
1499   else
1500     {
1501       tree then_stmt = expr_only (then_clause);
1502       tree else_stmt = expr_only (else_clause);
1503
1504       /* Notice branches to a common destination.  */
1505       if (then_stmt && else_stmt
1506           && TREE_CODE (then_stmt) == GOTO_EXPR
1507           && TREE_CODE (else_stmt) == GOTO_EXPR
1508           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1509         {
1510           *stmt_p = then_stmt;
1511           data->repeat = true;
1512         }
1513
1514       /* If the THEN/ELSE clause merely assigns a value to a variable or
1515          parameter which is already known to contain that value, then
1516          remove the useless THEN/ELSE clause.  */
1517       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1518         {
1519           if (else_stmt
1520               && TREE_CODE (else_stmt) == MODIFY_EXPR
1521               && TREE_OPERAND (else_stmt, 0) == cond
1522               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1523             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1524         }
1525       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1526                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1527                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1528                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1529         {
1530           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1531                        ? then_stmt : else_stmt);
1532           tree *location = (TREE_CODE (cond) == EQ_EXPR
1533                             ? &COND_EXPR_THEN (*stmt_p)
1534                             : &COND_EXPR_ELSE (*stmt_p));
1535
1536           if (stmt
1537               && TREE_CODE (stmt) == MODIFY_EXPR
1538               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1539               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1540             *location = alloc_stmt_list ();
1541         }
1542     }
1543
1544   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1545      would be re-introduced during lowering.  */
1546   data->last_goto = NULL;
1547 }
1548
1549
1550 static void
1551 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1552 {
1553   bool save_may_branch, save_may_throw;
1554   bool this_may_branch, this_may_throw;
1555
1556   /* Collect may_branch and may_throw information for the body only.  */
1557   save_may_branch = data->may_branch;
1558   save_may_throw = data->may_throw;
1559   data->may_branch = false;
1560   data->may_throw = false;
1561   data->last_goto = NULL;
1562
1563   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1564
1565   this_may_branch = data->may_branch;
1566   this_may_throw = data->may_throw;
1567   data->may_branch |= save_may_branch;
1568   data->may_throw |= save_may_throw;
1569   data->last_goto = NULL;
1570
1571   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1572
1573   /* If the body is empty, then we can emit the FINALLY block without
1574      the enclosing TRY_FINALLY_EXPR.  */
1575   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1576     {
1577       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1578       data->repeat = true;
1579     }
1580
1581   /* If the handler is empty, then we can emit the TRY block without
1582      the enclosing TRY_FINALLY_EXPR.  */
1583   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1584     {
1585       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1586       data->repeat = true;
1587     }
1588
1589   /* If the body neither throws, nor branches, then we can safely
1590      string the TRY and FINALLY blocks together.  */
1591   else if (!this_may_branch && !this_may_throw)
1592     {
1593       tree stmt = *stmt_p;
1594       *stmt_p = TREE_OPERAND (stmt, 0);
1595       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1596       data->repeat = true;
1597     }
1598 }
1599
1600
1601 static void
1602 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1603 {
1604   bool save_may_throw, this_may_throw;
1605   tree_stmt_iterator i;
1606   tree stmt;
1607
1608   /* Collect may_throw information for the body only.  */
1609   save_may_throw = data->may_throw;
1610   data->may_throw = false;
1611   data->last_goto = NULL;
1612
1613   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1614
1615   this_may_throw = data->may_throw;
1616   data->may_throw = save_may_throw;
1617
1618   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1619   if (!this_may_throw)
1620     {
1621       if (warn_notreached)
1622         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1623       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1624       data->repeat = true;
1625       return;
1626     }
1627
1628   /* Process the catch clause specially.  We may be able to tell that
1629      no exceptions propagate past this point.  */
1630
1631   this_may_throw = true;
1632   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1633   stmt = tsi_stmt (i);
1634   data->last_goto = NULL;
1635
1636   switch (TREE_CODE (stmt))
1637     {
1638     case CATCH_EXPR:
1639       for (; !tsi_end_p (i); tsi_next (&i))
1640         {
1641           stmt = tsi_stmt (i);
1642           /* If we catch all exceptions, then the body does not
1643              propagate exceptions past this point.  */
1644           if (CATCH_TYPES (stmt) == NULL)
1645             this_may_throw = false;
1646           data->last_goto = NULL;
1647           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1648         }
1649       break;
1650
1651     case EH_FILTER_EXPR:
1652       if (EH_FILTER_MUST_NOT_THROW (stmt))
1653         this_may_throw = false;
1654       else if (EH_FILTER_TYPES (stmt) == NULL)
1655         this_may_throw = false;
1656       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1657       break;
1658
1659     default:
1660       /* Otherwise this is a cleanup.  */
1661       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1662
1663       /* If the cleanup is empty, then we can emit the TRY block without
1664          the enclosing TRY_CATCH_EXPR.  */
1665       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1666         {
1667           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1668           data->repeat = true;
1669         }
1670       break;
1671     }
1672   data->may_throw |= this_may_throw;
1673 }
1674
1675
1676 static void
1677 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1678 {
1679   tree block;
1680
1681   /* First remove anything underneath the BIND_EXPR.  */
1682   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1683
1684   /* If the BIND_EXPR has no variables, then we can pull everything
1685      up one level and remove the BIND_EXPR, unless this is the toplevel
1686      BIND_EXPR for the current function or an inlined function.
1687
1688      When this situation occurs we will want to apply this
1689      optimization again.  */
1690   block = BIND_EXPR_BLOCK (*stmt_p);
1691   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1692       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1693       && (! block
1694           || ! BLOCK_ABSTRACT_ORIGIN (block)
1695           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1696               != FUNCTION_DECL)))
1697     {
1698       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1699       data->repeat = true;
1700     }
1701 }
1702
1703
1704 static void
1705 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1706 {
1707   tree dest = GOTO_DESTINATION (*stmt_p);
1708
1709   data->may_branch = true;
1710   data->last_goto = NULL;
1711
1712   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1713   if (TREE_CODE (dest) == LABEL_DECL)
1714     data->last_goto = stmt_p;
1715 }
1716
1717
1718 static void
1719 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1720 {
1721   tree label = LABEL_EXPR_LABEL (*stmt_p);
1722
1723   data->has_label = true;
1724
1725   /* We do want to jump across non-local label receiver code.  */
1726   if (DECL_NONLOCAL (label))
1727     data->last_goto = NULL;
1728
1729   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1730     {
1731       *data->last_goto = build_empty_stmt ();
1732       data->repeat = true;
1733     }
1734
1735   /* ??? Add something here to delete unused labels.  */
1736 }
1737
1738
1739 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1740    decl.  This allows us to eliminate redundant or useless
1741    calls to "const" functions. 
1742
1743    Gimplifier already does the same operation, but we may notice functions
1744    being const and pure once their calls has been gimplified, so we need
1745    to update the flag.  */
1746
1747 static void
1748 update_call_expr_flags (tree call)
1749 {
1750   tree decl = get_callee_fndecl (call);
1751   if (!decl)
1752     return;
1753   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1754     TREE_SIDE_EFFECTS (call) = 0;
1755   if (TREE_NOTHROW (decl))
1756     TREE_NOTHROW (call) = 1;
1757 }
1758
1759
1760 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1761
1762 void
1763 notice_special_calls (tree t)
1764 {
1765   int flags = call_expr_flags (t);
1766
1767   if (flags & ECF_MAY_BE_ALLOCA)
1768     current_function_calls_alloca = true;
1769   if (flags & ECF_RETURNS_TWICE)
1770     current_function_calls_setjmp = true;
1771 }
1772
1773
1774 /* Clear flags set by notice_special_calls.  Used by dead code removal
1775    to update the flags.  */
1776
1777 void
1778 clear_special_calls (void)
1779 {
1780   current_function_calls_alloca = false;
1781   current_function_calls_setjmp = false;
1782 }
1783
1784
1785 static void
1786 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1787 {
1788   tree t = *tp, op;
1789
1790   switch (TREE_CODE (t))
1791     {
1792     case COND_EXPR:
1793       remove_useless_stmts_cond (tp, data);
1794       break;
1795
1796     case TRY_FINALLY_EXPR:
1797       remove_useless_stmts_tf (tp, data);
1798       break;
1799
1800     case TRY_CATCH_EXPR:
1801       remove_useless_stmts_tc (tp, data);
1802       break;
1803
1804     case BIND_EXPR:
1805       remove_useless_stmts_bind (tp, data);
1806       break;
1807
1808     case GOTO_EXPR:
1809       remove_useless_stmts_goto (tp, data);
1810       break;
1811
1812     case LABEL_EXPR:
1813       remove_useless_stmts_label (tp, data);
1814       break;
1815
1816     case RETURN_EXPR:
1817       fold_stmt (tp);
1818       data->last_goto = NULL;
1819       data->may_branch = true;
1820       break;
1821
1822     case CALL_EXPR:
1823       fold_stmt (tp);
1824       data->last_goto = NULL;
1825       notice_special_calls (t);
1826       update_call_expr_flags (t);
1827       if (tree_could_throw_p (t))
1828         data->may_throw = true;
1829       break;
1830
1831     case MODIFY_EXPR:
1832       data->last_goto = NULL;
1833       fold_stmt (tp);
1834       op = get_call_expr_in (t);
1835       if (op)
1836         {
1837           update_call_expr_flags (op);
1838           notice_special_calls (op);
1839         }
1840       if (tree_could_throw_p (t))
1841         data->may_throw = true;
1842       break;
1843
1844     case STATEMENT_LIST:
1845       {
1846         tree_stmt_iterator i = tsi_start (t);
1847         while (!tsi_end_p (i))
1848           {
1849             t = tsi_stmt (i);
1850             if (IS_EMPTY_STMT (t))
1851               {
1852                 tsi_delink (&i);
1853                 continue;
1854               }
1855             
1856             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1857
1858             t = tsi_stmt (i);
1859             if (TREE_CODE (t) == STATEMENT_LIST)
1860               {
1861                 tsi_link_before (&i, t, TSI_SAME_STMT);
1862                 tsi_delink (&i);
1863               }
1864             else
1865               tsi_next (&i);
1866           }
1867       }
1868       break;
1869     case ASM_EXPR:
1870       fold_stmt (tp);
1871       data->last_goto = NULL;
1872       break;
1873
1874     default:
1875       data->last_goto = NULL;
1876       break;
1877     }
1878 }
1879
1880 static void
1881 remove_useless_stmts (void)
1882 {
1883   struct rus_data data;
1884
1885   clear_special_calls ();
1886
1887   do
1888     {
1889       memset (&data, 0, sizeof (data));
1890       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1891     }
1892   while (data.repeat);
1893 }
1894
1895
1896 struct tree_opt_pass pass_remove_useless_stmts = 
1897 {
1898   "useless",                            /* name */
1899   NULL,                                 /* gate */
1900   remove_useless_stmts,                 /* execute */
1901   NULL,                                 /* sub */
1902   NULL,                                 /* next */
1903   0,                                    /* static_pass_number */
1904   0,                                    /* tv_id */
1905   PROP_gimple_any,                      /* properties_required */
1906   0,                                    /* properties_provided */
1907   0,                                    /* properties_destroyed */
1908   0,                                    /* todo_flags_start */
1909   TODO_dump_func,                       /* todo_flags_finish */
1910   0                                     /* letter */
1911 };
1912
1913 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1914
1915 static void
1916 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1917 {
1918   tree phi;
1919
1920   /* Since this block is no longer reachable, we can just delete all
1921      of its PHI nodes.  */
1922   phi = phi_nodes (bb);
1923   while (phi)
1924     {
1925       tree next = PHI_CHAIN (phi);
1926       remove_phi_node (phi, NULL_TREE);
1927       phi = next;
1928     }
1929
1930   /* Remove edges to BB's successors.  */
1931   while (EDGE_COUNT (bb->succs) > 0)
1932     remove_edge (EDGE_SUCC (bb, 0));
1933 }
1934
1935
1936 /* Remove statements of basic block BB.  */
1937
1938 static void
1939 remove_bb (basic_block bb)
1940 {
1941   block_stmt_iterator i;
1942 #ifdef USE_MAPPED_LOCATION
1943   source_location loc = UNKNOWN_LOCATION;
1944 #else
1945   source_locus loc = 0;
1946 #endif
1947
1948   if (dump_file)
1949     {
1950       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1951       if (dump_flags & TDF_DETAILS)
1952         {
1953           dump_bb (bb, dump_file, 0);
1954           fprintf (dump_file, "\n");
1955         }
1956     }
1957
1958   /* If we remove the header or the latch of a loop, mark the loop for
1959      removal by setting its header and latch to NULL.  */
1960   if (current_loops)
1961     {
1962       struct loop *loop = bb->loop_father;
1963
1964       if (loop->latch == bb
1965           || loop->header == bb)
1966         {
1967           loop->latch = NULL;
1968           loop->header = NULL;
1969         }
1970     }
1971
1972   /* Remove all the instructions in the block.  */
1973   for (i = bsi_start (bb); !bsi_end_p (i);)
1974     {
1975       tree stmt = bsi_stmt (i);
1976       if (TREE_CODE (stmt) == LABEL_EXPR
1977           && FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
1978         {
1979           basic_block new_bb = bb->prev_bb;
1980           block_stmt_iterator new_bsi = bsi_start (new_bb);
1981                   
1982           bsi_remove (&i);
1983           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
1984         }
1985       else
1986         {
1987           release_defs (stmt);
1988
1989           bsi_remove (&i);
1990         }
1991
1992       /* Don't warn for removed gotos.  Gotos are often removed due to
1993          jump threading, thus resulting in bogus warnings.  Not great,
1994          since this way we lose warnings for gotos in the original
1995          program that are indeed unreachable.  */
1996       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
1997         {
1998 #ifdef USE_MAPPED_LOCATION
1999           if (EXPR_HAS_LOCATION (stmt))
2000             loc = EXPR_LOCATION (stmt);
2001 #else
2002           source_locus t;
2003           t = EXPR_LOCUS (stmt);
2004           if (t && LOCATION_LINE (*t) > 0)
2005             loc = t;
2006 #endif
2007         }
2008     }
2009
2010   /* If requested, give a warning that the first statement in the
2011      block is unreachable.  We walk statements backwards in the
2012      loop above, so the last statement we process is the first statement
2013      in the block.  */
2014 #ifdef USE_MAPPED_LOCATION
2015   if (warn_notreached && loc > BUILTINS_LOCATION)
2016     warning (0, "%Hwill never be executed", &loc);
2017 #else
2018   if (warn_notreached && loc)
2019     warning (0, "%Hwill never be executed", loc);
2020 #endif
2021
2022   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2023 }
2024
2025 /* A list of all the noreturn calls passed to modify_stmt.
2026    cleanup_control_flow uses it to detect cases where a mid-block
2027    indirect call has been turned into a noreturn call.  When this
2028    happens, all the instructions after the call are no longer
2029    reachable and must be deleted as dead.  */
2030
2031 VEC(tree,gc) *modified_noreturn_calls;
2032
2033 /* Try to remove superfluous control structures.  */
2034
2035 static bool
2036 cleanup_control_flow (void)
2037 {
2038   basic_block bb;
2039   block_stmt_iterator bsi;
2040   bool retval = false;
2041   tree stmt;
2042
2043   /* Detect cases where a mid-block call is now known not to return.  */
2044   while (VEC_length (tree, modified_noreturn_calls))
2045     {
2046       stmt = VEC_pop (tree, modified_noreturn_calls);
2047       bb = bb_for_stmt (stmt);
2048       if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt))
2049         split_block (bb, stmt);
2050     }
2051
2052   FOR_EACH_BB (bb)
2053     {
2054       bsi = bsi_last (bb);
2055
2056       if (bsi_end_p (bsi))
2057         continue;
2058       
2059       stmt = bsi_stmt (bsi);
2060       if (TREE_CODE (stmt) == COND_EXPR
2061           || TREE_CODE (stmt) == SWITCH_EXPR)
2062         retval |= cleanup_control_expr_graph (bb, bsi);
2063
2064       /* If we had a computed goto which has a compile-time determinable
2065          destination, then we can eliminate the goto.  */
2066       if (TREE_CODE (stmt) == GOTO_EXPR
2067           && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR
2068           && TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0)) == LABEL_DECL)
2069         {
2070           edge e;
2071           tree label;
2072           edge_iterator ei;
2073           basic_block target_block;
2074           bool removed_edge = false;
2075
2076           /* First look at all the outgoing edges.  Delete any outgoing
2077              edges which do not go to the right block.  For the one
2078              edge which goes to the right block, fix up its flags.  */
2079           label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0);
2080           target_block = label_to_block (label);
2081           for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2082             {
2083               if (e->dest != target_block)
2084                 {
2085                   removed_edge = true;
2086                   remove_edge (e);
2087                 }
2088               else
2089                 {
2090                   /* Turn off the EDGE_ABNORMAL flag.  */
2091                   e->flags &= ~EDGE_ABNORMAL;
2092
2093                   /* And set EDGE_FALLTHRU.  */
2094                   e->flags |= EDGE_FALLTHRU;
2095                   ei_next (&ei);
2096                 }
2097             }
2098
2099           /* If we removed one or more edges, then we will need to fix the
2100              dominators.  It may be possible to incrementally update them.  */
2101           if (removed_edge)
2102             free_dominance_info (CDI_DOMINATORS);
2103
2104           /* Remove the GOTO_EXPR as it is not needed.  The CFG has all the
2105              relevant information we need.  */
2106           bsi_remove (&bsi);
2107           retval = true;
2108         }
2109
2110       /* Check for indirect calls that have been turned into
2111          noreturn calls.  */
2112       if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs))
2113         {
2114           free_dominance_info (CDI_DOMINATORS);
2115           retval = true;
2116         }
2117     }
2118   return retval;
2119 }
2120
2121
2122 /* Disconnect an unreachable block in the control expression starting
2123    at block BB.  */
2124
2125 static bool
2126 cleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi)
2127 {
2128   edge taken_edge;
2129   bool retval = false;
2130   tree expr = bsi_stmt (bsi), val;
2131
2132   if (!single_succ_p (bb))
2133     {
2134       edge e;
2135       edge_iterator ei;
2136
2137       switch (TREE_CODE (expr))
2138         {
2139         case COND_EXPR:
2140           val = COND_EXPR_COND (expr);
2141           break;
2142
2143         case SWITCH_EXPR:
2144           val = SWITCH_COND (expr);
2145           if (TREE_CODE (val) != INTEGER_CST)
2146             return false;
2147           break;
2148
2149         default:
2150           gcc_unreachable ();
2151         }
2152
2153       taken_edge = find_taken_edge (bb, val);
2154       if (!taken_edge)
2155         return false;
2156
2157       /* Remove all the edges except the one that is always executed.  */
2158       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2159         {
2160           if (e != taken_edge)
2161             {
2162               taken_edge->probability += e->probability;
2163               taken_edge->count += e->count;
2164               remove_edge (e);
2165               retval = true;
2166             }
2167           else
2168             ei_next (&ei);
2169         }
2170       if (taken_edge->probability > REG_BR_PROB_BASE)
2171         taken_edge->probability = REG_BR_PROB_BASE;
2172     }
2173   else
2174     taken_edge = single_succ_edge (bb);
2175
2176   bsi_remove (&bsi);
2177   taken_edge->flags = EDGE_FALLTHRU;
2178
2179   /* We removed some paths from the cfg.  */
2180   free_dominance_info (CDI_DOMINATORS);
2181
2182   return retval;
2183 }
2184
2185 /* Remove any fallthru edge from EV.  Return true if an edge was removed.  */
2186
2187 static bool
2188 remove_fallthru_edge (VEC(edge,gc) *ev)
2189 {
2190   edge_iterator ei;
2191   edge e;
2192
2193   FOR_EACH_EDGE (e, ei, ev)
2194     if ((e->flags & EDGE_FALLTHRU) != 0)
2195       {
2196         remove_edge (e);
2197         return true;
2198       }
2199   return false;
2200 }
2201
2202 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2203    predicate VAL, return the edge that will be taken out of the block.
2204    If VAL does not match a unique edge, NULL is returned.  */
2205
2206 edge
2207 find_taken_edge (basic_block bb, tree val)
2208 {
2209   tree stmt;
2210
2211   stmt = last_stmt (bb);
2212
2213   gcc_assert (stmt);
2214   gcc_assert (is_ctrl_stmt (stmt));
2215   gcc_assert (val);
2216
2217   if (! is_gimple_min_invariant (val))
2218     return NULL;
2219
2220   if (TREE_CODE (stmt) == COND_EXPR)
2221     return find_taken_edge_cond_expr (bb, val);
2222
2223   if (TREE_CODE (stmt) == SWITCH_EXPR)
2224     return find_taken_edge_switch_expr (bb, val);
2225
2226   if (computed_goto_p (stmt))
2227     return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
2228
2229   gcc_unreachable ();
2230 }
2231
2232 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2233    statement, determine which of the outgoing edges will be taken out of the
2234    block.  Return NULL if either edge may be taken.  */
2235
2236 static edge
2237 find_taken_edge_computed_goto (basic_block bb, tree val)
2238 {
2239   basic_block dest;
2240   edge e = NULL;
2241
2242   dest = label_to_block (val);
2243   if (dest)
2244     {
2245       e = find_edge (bb, dest);
2246       gcc_assert (e != NULL);
2247     }
2248
2249   return e;
2250 }
2251
2252 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2253    statement, determine which of the two edges will be taken out of the
2254    block.  Return NULL if either edge may be taken.  */
2255
2256 static edge
2257 find_taken_edge_cond_expr (basic_block bb, tree val)
2258 {
2259   edge true_edge, false_edge;
2260
2261   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2262   
2263   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2264   return (zero_p (val) ? false_edge : true_edge);
2265 }
2266
2267 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2268    statement, determine which edge will be taken out of the block.  Return
2269    NULL if any edge may be taken.  */
2270
2271 static edge
2272 find_taken_edge_switch_expr (basic_block bb, tree val)
2273 {
2274   tree switch_expr, taken_case;
2275   basic_block dest_bb;
2276   edge e;
2277
2278   switch_expr = last_stmt (bb);
2279   taken_case = find_case_label_for_value (switch_expr, val);
2280   dest_bb = label_to_block (CASE_LABEL (taken_case));
2281
2282   e = find_edge (bb, dest_bb);
2283   gcc_assert (e);
2284   return e;
2285 }
2286
2287
2288 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2289    We can make optimal use here of the fact that the case labels are
2290    sorted: We can do a binary search for a case matching VAL.  */
2291
2292 static tree
2293 find_case_label_for_value (tree switch_expr, tree val)
2294 {
2295   tree vec = SWITCH_LABELS (switch_expr);
2296   size_t low, high, n = TREE_VEC_LENGTH (vec);
2297   tree default_case = TREE_VEC_ELT (vec, n - 1);
2298
2299   for (low = -1, high = n - 1; high - low > 1; )
2300     {
2301       size_t i = (high + low) / 2;
2302       tree t = TREE_VEC_ELT (vec, i);
2303       int cmp;
2304
2305       /* Cache the result of comparing CASE_LOW and val.  */
2306       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2307
2308       if (cmp > 0)
2309         high = i;
2310       else
2311         low = i;
2312
2313       if (CASE_HIGH (t) == NULL)
2314         {
2315           /* A singe-valued case label.  */
2316           if (cmp == 0)
2317             return t;
2318         }
2319       else
2320         {
2321           /* A case range.  We can only handle integer ranges.  */
2322           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2323             return t;
2324         }
2325     }
2326
2327   return default_case;
2328 }
2329
2330
2331 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
2332    those alternatives are equal in each of the PHI nodes, then return
2333    true, else return false.  */
2334
2335 static bool
2336 phi_alternatives_equal (basic_block dest, edge e1, edge e2)
2337 {
2338   int n1 = e1->dest_idx;
2339   int n2 = e2->dest_idx;
2340   tree phi;
2341
2342   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
2343     {
2344       tree val1 = PHI_ARG_DEF (phi, n1);
2345       tree val2 = PHI_ARG_DEF (phi, n2);
2346
2347       gcc_assert (val1 != NULL_TREE);
2348       gcc_assert (val2 != NULL_TREE);
2349
2350       if (!operand_equal_for_phi_arg_p (val1, val2))
2351         return false;
2352     }
2353
2354   return true;
2355 }
2356
2357
2358 /*---------------------------------------------------------------------------
2359                               Debugging functions
2360 ---------------------------------------------------------------------------*/
2361
2362 /* Dump tree-specific information of block BB to file OUTF.  */
2363
2364 void
2365 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2366 {
2367   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2368 }
2369
2370
2371 /* Dump a basic block on stderr.  */
2372
2373 void
2374 debug_tree_bb (basic_block bb)
2375 {
2376   dump_bb (bb, stderr, 0);
2377 }
2378
2379
2380 /* Dump basic block with index N on stderr.  */
2381
2382 basic_block
2383 debug_tree_bb_n (int n)
2384 {
2385   debug_tree_bb (BASIC_BLOCK (n));
2386   return BASIC_BLOCK (n);
2387 }        
2388
2389
2390 /* Dump the CFG on stderr.
2391
2392    FLAGS are the same used by the tree dumping functions
2393    (see TDF_* in tree.h).  */
2394
2395 void
2396 debug_tree_cfg (int flags)
2397 {
2398   dump_tree_cfg (stderr, flags);
2399 }
2400
2401
2402 /* Dump the program showing basic block boundaries on the given FILE.
2403
2404    FLAGS are the same used by the tree dumping functions (see TDF_* in
2405    tree.h).  */
2406
2407 void
2408 dump_tree_cfg (FILE *file, int flags)
2409 {
2410   if (flags & TDF_DETAILS)
2411     {
2412       const char *funcname
2413         = lang_hooks.decl_printable_name (current_function_decl, 2);
2414
2415       fputc ('\n', file);
2416       fprintf (file, ";; Function %s\n\n", funcname);
2417       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2418                n_basic_blocks, n_edges, last_basic_block);
2419
2420       brief_dump_cfg (file);
2421       fprintf (file, "\n");
2422     }
2423
2424   if (flags & TDF_STATS)
2425     dump_cfg_stats (file);
2426
2427   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2428 }
2429
2430
2431 /* Dump CFG statistics on FILE.  */
2432
2433 void
2434 dump_cfg_stats (FILE *file)
2435 {
2436   static long max_num_merged_labels = 0;
2437   unsigned long size, total = 0;
2438   long num_edges;
2439   basic_block bb;
2440   const char * const fmt_str   = "%-30s%-13s%12s\n";
2441   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2442   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2443   const char *funcname
2444     = lang_hooks.decl_printable_name (current_function_decl, 2);
2445
2446
2447   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2448
2449   fprintf (file, "---------------------------------------------------------\n");
2450   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2451   fprintf (file, fmt_str, "", "  instances  ", "used ");
2452   fprintf (file, "---------------------------------------------------------\n");
2453
2454   size = n_basic_blocks * sizeof (struct basic_block_def);
2455   total += size;
2456   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2457            SCALE (size), LABEL (size));
2458
2459   num_edges = 0;
2460   FOR_EACH_BB (bb)
2461     num_edges += EDGE_COUNT (bb->succs);
2462   size = num_edges * sizeof (struct edge_def);
2463   total += size;
2464   fprintf (file, fmt_str_1, "Edges", num_edges, SCALE (size), LABEL (size));
2465
2466   size = n_basic_blocks * sizeof (struct bb_ann_d);
2467   total += size;
2468   fprintf (file, fmt_str_1, "Basic block annotations", n_basic_blocks,
2469            SCALE (size), LABEL (size));
2470
2471   fprintf (file, "---------------------------------------------------------\n");
2472   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2473            LABEL (total));
2474   fprintf (file, "---------------------------------------------------------\n");
2475   fprintf (file, "\n");
2476
2477   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2478     max_num_merged_labels = cfg_stats.num_merged_labels;
2479
2480   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2481            cfg_stats.num_merged_labels, max_num_merged_labels);
2482
2483   fprintf (file, "\n");
2484 }
2485
2486
2487 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2488    linked in the final executable.  */
2489
2490 void
2491 debug_cfg_stats (void)
2492 {
2493   dump_cfg_stats (stderr);
2494 }
2495
2496
2497 /* Dump the flowgraph to a .vcg FILE.  */
2498
2499 static void
2500 tree_cfg2vcg (FILE *file)
2501 {
2502   edge e;
2503   edge_iterator ei;
2504   basic_block bb;
2505   const char *funcname
2506     = lang_hooks.decl_printable_name (current_function_decl, 2);
2507
2508   /* Write the file header.  */
2509   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2510   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2511   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2512
2513   /* Write blocks and edges.  */
2514   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2515     {
2516       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2517                e->dest->index);
2518
2519       if (e->flags & EDGE_FAKE)
2520         fprintf (file, " linestyle: dotted priority: 10");
2521       else
2522         fprintf (file, " linestyle: solid priority: 100");
2523
2524       fprintf (file, " }\n");
2525     }
2526   fputc ('\n', file);
2527
2528   FOR_EACH_BB (bb)
2529     {
2530       enum tree_code head_code, end_code;
2531       const char *head_name, *end_name;
2532       int head_line = 0;
2533       int end_line = 0;
2534       tree first = first_stmt (bb);
2535       tree last = last_stmt (bb);
2536
2537       if (first)
2538         {
2539           head_code = TREE_CODE (first);
2540           head_name = tree_code_name[head_code];
2541           head_line = get_lineno (first);
2542         }
2543       else
2544         head_name = "no-statement";
2545
2546       if (last)
2547         {
2548           end_code = TREE_CODE (last);
2549           end_name = tree_code_name[end_code];
2550           end_line = get_lineno (last);
2551         }
2552       else
2553         end_name = "no-statement";
2554
2555       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2556                bb->index, bb->index, head_name, head_line, end_name,
2557                end_line);
2558
2559       FOR_EACH_EDGE (e, ei, bb->succs)
2560         {
2561           if (e->dest == EXIT_BLOCK_PTR)
2562             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2563           else
2564             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2565
2566           if (e->flags & EDGE_FAKE)
2567             fprintf (file, " priority: 10 linestyle: dotted");
2568           else
2569             fprintf (file, " priority: 100 linestyle: solid");
2570
2571           fprintf (file, " }\n");
2572         }
2573
2574       if (bb->next_bb != EXIT_BLOCK_PTR)
2575         fputc ('\n', file);
2576     }
2577
2578   fputs ("}\n\n", file);
2579 }
2580
2581
2582
2583 /*---------------------------------------------------------------------------
2584                              Miscellaneous helpers
2585 ---------------------------------------------------------------------------*/
2586
2587 /* Return true if T represents a stmt that always transfers control.  */
2588
2589 bool
2590 is_ctrl_stmt (tree t)
2591 {
2592   return (TREE_CODE (t) == COND_EXPR
2593           || TREE_CODE (t) == SWITCH_EXPR
2594           || TREE_CODE (t) == GOTO_EXPR
2595           || TREE_CODE (t) == RETURN_EXPR
2596           || TREE_CODE (t) == RESX_EXPR);
2597 }
2598
2599
2600 /* Return true if T is a statement that may alter the flow of control
2601    (e.g., a call to a non-returning function).  */
2602
2603 bool
2604 is_ctrl_altering_stmt (tree t)
2605 {
2606   tree call;
2607
2608   gcc_assert (t);
2609   call = get_call_expr_in (t);
2610   if (call)
2611     {
2612       /* A non-pure/const CALL_EXPR alters flow control if the current
2613          function has nonlocal labels.  */
2614       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2615         return true;
2616
2617       /* A CALL_EXPR also alters control flow if it does not return.  */
2618       if (call_expr_flags (call) & ECF_NORETURN)
2619         return true;
2620     }
2621
2622   /* If a statement can throw, it alters control flow.  */
2623   return tree_can_throw_internal (t);
2624 }
2625
2626
2627 /* Return true if T is a computed goto.  */
2628
2629 bool
2630 computed_goto_p (tree t)
2631 {
2632   return (TREE_CODE (t) == GOTO_EXPR
2633           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2634 }
2635
2636
2637 /* Checks whether EXPR is a simple local goto.  */
2638
2639 bool
2640 simple_goto_p (tree expr)
2641 {
2642   return (TREE_CODE (expr) == GOTO_EXPR
2643           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2644 }
2645
2646
2647 /* Return true if T should start a new basic block.  PREV_T is the
2648    statement preceding T.  It is used when T is a label or a case label.
2649    Labels should only start a new basic block if their previous statement
2650    wasn't a label.  Otherwise, sequence of labels would generate
2651    unnecessary basic blocks that only contain a single label.  */
2652
2653 static inline bool
2654 stmt_starts_bb_p (tree t, tree prev_t)
2655 {
2656   if (t == NULL_TREE)
2657     return false;
2658
2659   /* LABEL_EXPRs start a new basic block only if the preceding
2660      statement wasn't a label of the same type.  This prevents the
2661      creation of consecutive blocks that have nothing but a single
2662      label.  */
2663   if (TREE_CODE (t) == LABEL_EXPR)
2664     {
2665       /* Nonlocal and computed GOTO targets always start a new block.  */
2666       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2667           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2668         return true;
2669
2670       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2671         {
2672           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2673             return true;
2674
2675           cfg_stats.num_merged_labels++;
2676           return false;
2677         }
2678       else
2679         return true;
2680     }
2681
2682   return false;
2683 }
2684
2685
2686 /* Return true if T should end a basic block.  */
2687
2688 bool
2689 stmt_ends_bb_p (tree t)
2690 {
2691   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2692 }
2693
2694
2695 /* Add gotos that used to be represented implicitly in the CFG.  */
2696
2697 void
2698 disband_implicit_edges (void)
2699 {
2700   basic_block bb;
2701   block_stmt_iterator last;
2702   edge e;
2703   edge_iterator ei;
2704   tree stmt, label;
2705
2706   FOR_EACH_BB (bb)
2707     {
2708       last = bsi_last (bb);
2709       stmt = last_stmt (bb);
2710
2711       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2712         {
2713           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2714              from cfg_remove_useless_stmts here since it violates the
2715              invariants for tree--cfg correspondence and thus fits better
2716              here where we do it anyway.  */
2717           e = find_edge (bb, bb->next_bb);
2718           if (e)
2719             {
2720               if (e->flags & EDGE_TRUE_VALUE)
2721                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2722               else if (e->flags & EDGE_FALSE_VALUE)
2723                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2724               else
2725                 gcc_unreachable ();
2726               e->flags |= EDGE_FALLTHRU;
2727             }
2728
2729           continue;
2730         }
2731
2732       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2733         {
2734           /* Remove the RETURN_EXPR if we may fall though to the exit
2735              instead.  */
2736           gcc_assert (single_succ_p (bb));
2737           gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2738
2739           if (bb->next_bb == EXIT_BLOCK_PTR
2740               && !TREE_OPERAND (stmt, 0))
2741             {
2742               bsi_remove (&last);
2743               single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2744             }
2745           continue;
2746         }
2747
2748       /* There can be no fallthru edge if the last statement is a control
2749          one.  */
2750       if (stmt && is_ctrl_stmt (stmt))
2751         continue;
2752
2753       /* Find a fallthru edge and emit the goto if necessary.  */
2754       FOR_EACH_EDGE (e, ei, bb->succs)
2755         if (e->flags & EDGE_FALLTHRU)
2756           break;
2757
2758       if (!e || e->dest == bb->next_bb)
2759         continue;
2760
2761       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2762       label = tree_block_label (e->dest);
2763
2764       stmt = build1 (GOTO_EXPR, void_type_node, label);
2765 #ifdef USE_MAPPED_LOCATION
2766       SET_EXPR_LOCATION (stmt, e->goto_locus);
2767 #else
2768       SET_EXPR_LOCUS (stmt, e->goto_locus);
2769 #endif
2770       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2771       e->flags &= ~EDGE_FALLTHRU;
2772     }
2773 }
2774
2775 /* Remove block annotations and other datastructures.  */
2776
2777 void
2778 delete_tree_cfg_annotations (void)
2779 {
2780   basic_block bb;
2781   if (n_basic_blocks > 0)
2782     free_blocks_annotations ();
2783
2784   label_to_block_map = NULL;
2785   FOR_EACH_BB (bb)
2786     bb->rbi = NULL;
2787 }
2788
2789
2790 /* Return the first statement in basic block BB.  */
2791
2792 tree
2793 first_stmt (basic_block bb)
2794 {
2795   block_stmt_iterator i = bsi_start (bb);
2796   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2797 }
2798
2799
2800 /* Return the last statement in basic block BB.  */
2801
2802 tree
2803 last_stmt (basic_block bb)
2804 {
2805   block_stmt_iterator b = bsi_last (bb);
2806   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2807 }
2808
2809
2810 /* Return a pointer to the last statement in block BB.  */
2811
2812 tree *
2813 last_stmt_ptr (basic_block bb)
2814 {
2815   block_stmt_iterator last = bsi_last (bb);
2816   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2817 }
2818
2819
2820 /* Return the last statement of an otherwise empty block.  Return NULL
2821    if the block is totally empty, or if it contains more than one
2822    statement.  */
2823
2824 tree
2825 last_and_only_stmt (basic_block bb)
2826 {
2827   block_stmt_iterator i = bsi_last (bb);
2828   tree last, prev;
2829
2830   if (bsi_end_p (i))
2831     return NULL_TREE;
2832
2833   last = bsi_stmt (i);
2834   bsi_prev (&i);
2835   if (bsi_end_p (i))
2836     return last;
2837
2838   /* Empty statements should no longer appear in the instruction stream.
2839      Everything that might have appeared before should be deleted by
2840      remove_useless_stmts, and the optimizers should just bsi_remove
2841      instead of smashing with build_empty_stmt.
2842
2843      Thus the only thing that should appear here in a block containing
2844      one executable statement is a label.  */
2845   prev = bsi_stmt (i);
2846   if (TREE_CODE (prev) == LABEL_EXPR)
2847     return last;
2848   else
2849     return NULL_TREE;
2850 }
2851
2852
2853 /* Mark BB as the basic block holding statement T.  */
2854
2855 void
2856 set_bb_for_stmt (tree t, basic_block bb)
2857 {
2858   if (TREE_CODE (t) == PHI_NODE)
2859     PHI_BB (t) = bb;
2860   else if (TREE_CODE (t) == STATEMENT_LIST)
2861     {
2862       tree_stmt_iterator i;
2863       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2864         set_bb_for_stmt (tsi_stmt (i), bb);
2865     }
2866   else
2867     {
2868       stmt_ann_t ann = get_stmt_ann (t);
2869       ann->bb = bb;
2870
2871       /* If the statement is a label, add the label to block-to-labels map
2872          so that we can speed up edge creation for GOTO_EXPRs.  */
2873       if (TREE_CODE (t) == LABEL_EXPR)
2874         {
2875           int uid;
2876
2877           t = LABEL_EXPR_LABEL (t);
2878           uid = LABEL_DECL_UID (t);
2879           if (uid == -1)
2880             {
2881               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2882               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2883                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2884             }
2885           else
2886             /* We're moving an existing label.  Make sure that we've
2887                 removed it from the old block.  */
2888             gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
2889           VARRAY_BB (label_to_block_map, uid) = bb;
2890         }
2891     }
2892 }
2893
2894 /* Finds iterator for STMT.  */
2895
2896 extern block_stmt_iterator
2897 bsi_for_stmt (tree stmt)
2898 {
2899   block_stmt_iterator bsi;
2900
2901   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2902     if (bsi_stmt (bsi) == stmt)
2903       return bsi;
2904
2905   gcc_unreachable ();
2906 }
2907
2908 /* Mark statement T as modified, and update it.  */
2909 static inline void
2910 update_modified_stmts (tree t)
2911 {
2912   if (TREE_CODE (t) == STATEMENT_LIST)
2913     {
2914       tree_stmt_iterator i;
2915       tree stmt;
2916       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2917         {
2918           stmt = tsi_stmt (i);
2919           update_stmt_if_modified (stmt);
2920         }
2921     }
2922   else
2923     update_stmt_if_modified (t);
2924 }
2925
2926 /* Insert statement (or statement list) T before the statement
2927    pointed-to by iterator I.  M specifies how to update iterator I
2928    after insertion (see enum bsi_iterator_update).  */
2929
2930 void
2931 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2932 {
2933   set_bb_for_stmt (t, i->bb);
2934   update_modified_stmts (t);
2935   tsi_link_before (&i->tsi, t, m);
2936 }
2937
2938
2939 /* Insert statement (or statement list) T after the statement
2940    pointed-to by iterator I.  M specifies how to update iterator I
2941    after insertion (see enum bsi_iterator_update).  */
2942
2943 void
2944 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2945 {
2946   set_bb_for_stmt (t, i->bb);
2947   update_modified_stmts (t);
2948   tsi_link_after (&i->tsi, t, m);
2949 }
2950
2951
2952 /* Remove the statement pointed to by iterator I.  The iterator is updated
2953    to the next statement.  */
2954
2955 void
2956 bsi_remove (block_stmt_iterator *i)
2957 {
2958   tree t = bsi_stmt (*i);
2959   set_bb_for_stmt (t, NULL);
2960   delink_stmt_imm_use (t);
2961   tsi_delink (&i->tsi);
2962   mark_stmt_modified (t);
2963 }
2964
2965
2966 /* Move the statement at FROM so it comes right after the statement at TO.  */
2967
2968 void 
2969 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2970 {
2971   tree stmt = bsi_stmt (*from);
2972   bsi_remove (from);
2973   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2974
2975
2976
2977 /* Move the statement at FROM so it comes right before the statement at TO.  */
2978
2979 void 
2980 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2981 {
2982   tree stmt = bsi_stmt (*from);
2983   bsi_remove (from);
2984   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2985 }
2986
2987
2988 /* Move the statement at FROM to the end of basic block BB.  */
2989
2990 void
2991 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2992 {
2993   block_stmt_iterator last = bsi_last (bb);
2994   
2995   /* Have to check bsi_end_p because it could be an empty block.  */
2996   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2997     bsi_move_before (from, &last);
2998   else
2999     bsi_move_after (from, &last);
3000 }
3001
3002
3003 /* Replace the contents of the statement pointed to by iterator BSI
3004    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
3005    information of the original statement is preserved.  */
3006
3007 void
3008 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
3009 {
3010   int eh_region;
3011   tree orig_stmt = bsi_stmt (*bsi);
3012
3013   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
3014   set_bb_for_stmt (stmt, bsi->bb);
3015
3016   /* Preserve EH region information from the original statement, if
3017      requested by the caller.  */
3018   if (preserve_eh_info)
3019     {
3020       eh_region = lookup_stmt_eh_region (orig_stmt);
3021       if (eh_region >= 0)
3022         add_stmt_to_eh_region (stmt, eh_region);
3023     }
3024
3025   delink_stmt_imm_use (orig_stmt);
3026   *bsi_stmt_ptr (*bsi) = stmt;
3027   mark_stmt_modified (stmt);
3028   update_modified_stmts (stmt);
3029 }
3030
3031
3032 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
3033    is made to place the statement in an existing basic block, but
3034    sometimes that isn't possible.  When it isn't possible, the edge is
3035    split and the statement is added to the new block.
3036
3037    In all cases, the returned *BSI points to the correct location.  The
3038    return value is true if insertion should be done after the location,
3039    or false if it should be done before the location.  If new basic block
3040    has to be created, it is stored in *NEW_BB.  */
3041
3042 static bool
3043 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
3044                            basic_block *new_bb)
3045 {
3046   basic_block dest, src;
3047   tree tmp;
3048
3049   dest = e->dest;
3050  restart:
3051
3052   /* If the destination has one predecessor which has no PHI nodes,
3053      insert there.  Except for the exit block. 
3054
3055      The requirement for no PHI nodes could be relaxed.  Basically we
3056      would have to examine the PHIs to prove that none of them used
3057      the value set by the statement we want to insert on E.  That
3058      hardly seems worth the effort.  */
3059   if (single_pred_p (dest)
3060       && ! phi_nodes (dest)
3061       && dest != EXIT_BLOCK_PTR)
3062     {
3063       *bsi = bsi_start (dest);
3064       if (bsi_end_p (*bsi))
3065         return true;
3066
3067       /* Make sure we insert after any leading labels.  */
3068       tmp = bsi_stmt (*bsi);
3069       while (TREE_CODE (tmp) == LABEL_EXPR)
3070         {
3071           bsi_next (bsi);
3072           if (bsi_end_p (*bsi))
3073             break;
3074           tmp = bsi_stmt (*bsi);
3075         }
3076
3077       if (bsi_end_p (*bsi))
3078         {
3079           *bsi = bsi_last (dest);
3080           return true;
3081         }
3082       else
3083         return false;
3084     }
3085
3086   /* If the source has one successor, the edge is not abnormal and
3087      the last statement does not end a basic block, insert there.
3088      Except for the entry block.  */
3089   src = e->src;
3090   if ((e->flags & EDGE_ABNORMAL) == 0
3091       && single_succ_p (src)
3092       && src != ENTRY_BLOCK_PTR)
3093     {
3094       *bsi = bsi_last (src);
3095       if (bsi_end_p (*bsi))
3096         return true;
3097
3098       tmp = bsi_stmt (*bsi);
3099       if (!stmt_ends_bb_p (tmp))
3100         return true;
3101
3102       /* Insert code just before returning the value.  We may need to decompose
3103          the return in the case it contains non-trivial operand.  */
3104       if (TREE_CODE (tmp) == RETURN_EXPR)
3105         {
3106           tree op = TREE_OPERAND (tmp, 0);
3107           if (!is_gimple_val (op))
3108             {
3109               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
3110               bsi_insert_before (bsi, op, BSI_NEW_STMT);
3111               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
3112             }
3113           bsi_prev (bsi);
3114           return true;
3115         }
3116     }
3117
3118   /* Otherwise, create a new basic block, and split this edge.  */
3119   dest = split_edge (e);
3120   if (new_bb)
3121     *new_bb = dest;
3122   e = single_pred_edge (dest);
3123   goto restart;
3124 }
3125
3126
3127 /* This routine will commit all pending edge insertions, creating any new
3128    basic blocks which are necessary.  */
3129
3130 void
3131 bsi_commit_edge_inserts (void)
3132 {
3133   basic_block bb;
3134   edge e;
3135   edge_iterator ei;
3136
3137   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
3138
3139   FOR_EACH_BB (bb)
3140     FOR_EACH_EDGE (e, ei, bb->succs)
3141       bsi_commit_one_edge_insert (e, NULL);
3142 }
3143
3144
3145 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3146    to this block, otherwise set it to NULL.  */
3147
3148 void
3149 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3150 {
3151   if (new_bb)
3152     *new_bb = NULL;
3153   if (PENDING_STMT (e))
3154     {
3155       block_stmt_iterator bsi;
3156       tree stmt = PENDING_STMT (e);
3157
3158       PENDING_STMT (e) = NULL_TREE;
3159
3160       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3161         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3162       else
3163         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3164     }
3165 }
3166
3167
3168 /* Add STMT to the pending list of edge E.  No actual insertion is
3169    made until a call to bsi_commit_edge_inserts () is made.  */
3170
3171 void
3172 bsi_insert_on_edge (edge e, tree stmt)
3173 {
3174   append_to_statement_list (stmt, &PENDING_STMT (e));
3175 }
3176
3177 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
3178    block has to be created, it is returned.  */
3179
3180 basic_block
3181 bsi_insert_on_edge_immediate (edge e, tree stmt)
3182 {
3183   block_stmt_iterator bsi;
3184   basic_block new_bb = NULL;
3185
3186   gcc_assert (!PENDING_STMT (e));
3187
3188   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3189     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3190   else
3191     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3192
3193   return new_bb;
3194 }
3195
3196 /*---------------------------------------------------------------------------
3197              Tree specific functions for CFG manipulation
3198 ---------------------------------------------------------------------------*/
3199
3200 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3201
3202 static void
3203 reinstall_phi_args (edge new_edge, edge old_edge)
3204 {
3205   tree var, phi;
3206
3207   if (!PENDING_STMT (old_edge))
3208     return;
3209   
3210   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3211        var && phi;
3212        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3213     {
3214       tree result = TREE_PURPOSE (var);
3215       tree arg = TREE_VALUE (var);
3216
3217       gcc_assert (result == PHI_RESULT (phi));
3218
3219       add_phi_arg (phi, arg, new_edge);
3220     }
3221
3222   PENDING_STMT (old_edge) = NULL;
3223 }
3224
3225 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3226    Abort on abnormal edges.  */
3227
3228 static basic_block
3229 tree_split_edge (edge edge_in)
3230 {
3231   basic_block new_bb, after_bb, dest, src;
3232   edge new_edge, e;
3233
3234   /* Abnormal edges cannot be split.  */
3235   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3236
3237   src = edge_in->src;
3238   dest = edge_in->dest;
3239
3240   /* Place the new block in the block list.  Try to keep the new block
3241      near its "logical" location.  This is of most help to humans looking
3242      at debugging dumps.  */
3243   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3244     after_bb = edge_in->src;
3245   else
3246     after_bb = dest->prev_bb;
3247
3248   new_bb = create_empty_bb (after_bb);
3249   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3250   new_bb->count = edge_in->count;
3251   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3252   new_edge->probability = REG_BR_PROB_BASE;
3253   new_edge->count = edge_in->count;
3254
3255   e = redirect_edge_and_branch (edge_in, new_bb);
3256   gcc_assert (e);
3257   reinstall_phi_args (new_edge, e);
3258
3259   return new_bb;
3260 }
3261
3262
3263 /* Return true when BB has label LABEL in it.  */
3264
3265 static bool
3266 has_label_p (basic_block bb, tree label)
3267 {
3268   block_stmt_iterator bsi;
3269
3270   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3271     {
3272       tree stmt = bsi_stmt (bsi);
3273
3274       if (TREE_CODE (stmt) != LABEL_EXPR)
3275         return false;
3276       if (LABEL_EXPR_LABEL (stmt) == label)
3277         return true;
3278     }
3279   return false;
3280 }
3281
3282
3283 /* Callback for walk_tree, check that all elements with address taken are
3284    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3285    inside a PHI node.  */
3286
3287 static tree
3288 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3289 {
3290   tree t = *tp, x;
3291   bool in_phi = (data != NULL);
3292
3293   if (TYPE_P (t))
3294     *walk_subtrees = 0;
3295   
3296   /* Check operand N for being valid GIMPLE and give error MSG if not. 
3297      We check for constants explicitly since they are not considered
3298      gimple invariants if they overflowed.  */
3299 #define CHECK_OP(N, MSG) \
3300   do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N))              \
3301          && !is_gimple_val (TREE_OPERAND (t, N)))               \
3302        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3303
3304   switch (TREE_CODE (t))
3305     {
3306     case SSA_NAME:
3307       if (SSA_NAME_IN_FREE_LIST (t))
3308         {
3309           error ("SSA name in freelist but still referenced");
3310           return *tp;
3311         }
3312       break;
3313
3314     case ASSERT_EXPR:
3315       x = fold (ASSERT_EXPR_COND (t));
3316       if (x == boolean_false_node)
3317         {
3318           error ("ASSERT_EXPR with an always-false condition");
3319           return *tp;
3320         }
3321       break;
3322
3323     case MODIFY_EXPR:
3324       x = TREE_OPERAND (t, 0);
3325       if (TREE_CODE (x) == BIT_FIELD_REF
3326           && is_gimple_reg (TREE_OPERAND (x, 0)))
3327         {
3328           error ("GIMPLE register modified with BIT_FIELD_REF");
3329           return t;
3330         }
3331       break;
3332
3333     case ADDR_EXPR:
3334       /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
3335          dead PHIs that take the address of something.  But if the PHI
3336          result is dead, the fact that it takes the address of anything
3337          is irrelevant.  Because we can not tell from here if a PHI result
3338          is dead, we just skip this check for PHIs altogether.  This means
3339          we may be missing "valid" checks, but what can you do?
3340          This was PR19217.  */
3341       if (in_phi)
3342         break;
3343
3344       /* Skip any references (they will be checked when we recurse down the
3345          tree) and ensure that any variable used as a prefix is marked
3346          addressable.  */
3347       for (x = TREE_OPERAND (t, 0);
3348            handled_component_p (x);
3349            x = TREE_OPERAND (x, 0))
3350         ;
3351
3352       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3353         return NULL;
3354       if (!TREE_ADDRESSABLE (x))
3355         {
3356           error ("address taken, but ADDRESSABLE bit not set");
3357           return x;
3358         }
3359       break;
3360
3361     case COND_EXPR:
3362       x = COND_EXPR_COND (t);
3363       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3364         {
3365           error ("non-boolean used in condition");
3366           return x;
3367         }
3368       break;
3369
3370     case NOP_EXPR:
3371     case CONVERT_EXPR:
3372     case FIX_TRUNC_EXPR:
3373     case FIX_CEIL_EXPR:
3374     case FIX_FLOOR_EXPR:
3375     case FIX_ROUND_EXPR:
3376     case FLOAT_EXPR:
3377     case NEGATE_EXPR:
3378     case ABS_EXPR:
3379     case BIT_NOT_EXPR:
3380     case NON_LVALUE_EXPR:
3381     case TRUTH_NOT_EXPR:
3382       CHECK_OP (0, "Invalid operand to unary operator");
3383       break;
3384
3385     case REALPART_EXPR:
3386     case IMAGPART_EXPR:
3387     case COMPONENT_REF:
3388     case ARRAY_REF:
3389     case ARRAY_RANGE_REF:
3390     case BIT_FIELD_REF:
3391     case VIEW_CONVERT_EXPR:
3392       /* We have a nest of references.  Verify that each of the operands
3393          that determine where to reference is either a constant or a variable,
3394          verify that the base is valid, and then show we've already checked
3395          the subtrees.  */
3396       while (handled_component_p (t))
3397         {
3398           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3399             CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3400           else if (TREE_CODE (t) == ARRAY_REF
3401                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3402             {
3403               CHECK_OP (1, "Invalid array index.");
3404               if (TREE_OPERAND (t, 2))
3405                 CHECK_OP (2, "Invalid array lower bound.");
3406               if (TREE_OPERAND (t, 3))
3407                 CHECK_OP (3, "Invalid array stride.");
3408             }
3409           else if (TREE_CODE (t) == BIT_FIELD_REF)
3410             {
3411               CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3412               CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3413             }
3414
3415           t = TREE_OPERAND (t, 0);
3416         }
3417
3418       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3419         {
3420           error ("Invalid reference prefix.");
3421           return t;
3422         }
3423       *walk_subtrees = 0;
3424       break;
3425
3426     case LT_EXPR:
3427     case LE_EXPR:
3428     case GT_EXPR:
3429     case GE_EXPR:
3430     case EQ_EXPR:
3431     case NE_EXPR:
3432     case UNORDERED_EXPR:
3433     case ORDERED_EXPR:
3434     case UNLT_EXPR:
3435     case UNLE_EXPR:
3436     case UNGT_EXPR:
3437     case UNGE_EXPR:
3438     case UNEQ_EXPR:
3439     case LTGT_EXPR:
3440     case PLUS_EXPR:
3441     case MINUS_EXPR:
3442     case MULT_EXPR:
3443     case TRUNC_DIV_EXPR:
3444     case CEIL_DIV_EXPR:
3445     case FLOOR_DIV_EXPR:
3446     case ROUND_DIV_EXPR:
3447     case TRUNC_MOD_EXPR:
3448     case CEIL_MOD_EXPR:
3449     case FLOOR_MOD_EXPR:
3450     case ROUND_MOD_EXPR:
3451     case RDIV_EXPR:
3452     case EXACT_DIV_EXPR:
3453     case MIN_EXPR:
3454     case MAX_EXPR:
3455     case LSHIFT_EXPR:
3456     case RSHIFT_EXPR:
3457     case LROTATE_EXPR:
3458     case RROTATE_EXPR:
3459     case BIT_IOR_EXPR:
3460     case BIT_XOR_EXPR:
3461     case BIT_AND_EXPR:
3462       CHECK_OP (0, "Invalid operand to binary operator");
3463       CHECK_OP (1, "Invalid operand to binary operator");
3464       break;
3465
3466     default:
3467       break;
3468     }
3469   return NULL;
3470
3471 #undef CHECK_OP
3472 }
3473
3474
3475 /* Verify STMT, return true if STMT is not in GIMPLE form.
3476    TODO: Implement type checking.  */
3477
3478 static bool
3479 verify_stmt (tree stmt, bool last_in_block)
3480 {
3481   tree addr;
3482
3483   if (!is_gimple_stmt (stmt))
3484     {
3485       error ("Is not a valid GIMPLE statement.");
3486       goto fail;
3487     }
3488
3489   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3490   if (addr)
3491     {
3492       debug_generic_stmt (addr);
3493       return true;
3494     }
3495
3496   /* If the statement is marked as part of an EH region, then it is
3497      expected that the statement could throw.  Verify that when we
3498      have optimizations that simplify statements such that we prove
3499      that they cannot throw, that we update other data structures
3500      to match.  */
3501   if (lookup_stmt_eh_region (stmt) >= 0)
3502     {
3503       if (!tree_could_throw_p (stmt))
3504         {
3505           error ("Statement marked for throw, but doesn%'t.");
3506           goto fail;
3507         }
3508       if (!last_in_block && tree_can_throw_internal (stmt))
3509         {
3510           error ("Statement marked for throw in middle of block.");
3511           goto fail;
3512         }
3513     }
3514
3515   return false;
3516
3517  fail:
3518   debug_generic_stmt (stmt);
3519   return true;
3520 }
3521
3522
3523 /* Return true when the T can be shared.  */
3524
3525 static bool
3526 tree_node_can_be_shared (tree t)
3527 {
3528   if (IS_TYPE_OR_DECL_P (t)
3529       /* We check for constants explicitly since they are not considered
3530          gimple invariants if they overflowed.  */
3531       || CONSTANT_CLASS_P (t)
3532       || is_gimple_min_invariant (t)
3533       || TREE_CODE (t) == SSA_NAME
3534       || t == error_mark_node)
3535     return true;
3536
3537   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3538     return true;
3539
3540   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3541           /* We check for constants explicitly since they are not considered
3542              gimple invariants if they overflowed.  */
3543           && (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
3544               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3545          || (TREE_CODE (t) == COMPONENT_REF
3546              || TREE_CODE (t) == REALPART_EXPR
3547              || TREE_CODE (t) == IMAGPART_EXPR))
3548     t = TREE_OPERAND (t, 0);
3549
3550   if (DECL_P (t))
3551     return true;
3552
3553   return false;
3554 }
3555
3556
3557 /* Called via walk_trees.  Verify tree sharing.  */
3558
3559 static tree
3560 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3561 {
3562   htab_t htab = (htab_t) data;
3563   void **slot;
3564
3565   if (tree_node_can_be_shared (*tp))
3566     {
3567       *walk_subtrees = false;
3568       return NULL;
3569     }
3570
3571   slot = htab_find_slot (htab, *tp, INSERT);
3572   if (*slot)
3573     return *slot;
3574   *slot = *tp;
3575
3576   return NULL;
3577 }
3578
3579
3580 /* Verify the GIMPLE statement chain.  */
3581
3582 void
3583 verify_stmts (void)
3584 {
3585   basic_block bb;
3586   block_stmt_iterator bsi;
3587   bool err = false;
3588   htab_t htab;
3589   tree addr;
3590
3591   timevar_push (TV_TREE_STMT_VERIFY);
3592   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3593
3594   FOR_EACH_BB (bb)
3595     {
3596       tree phi;
3597       int i;
3598
3599       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3600         {
3601           int phi_num_args = PHI_NUM_ARGS (phi);
3602
3603           if (bb_for_stmt (phi) != bb)
3604             {
3605               error ("bb_for_stmt (phi) is set to a wrong basic block\n");
3606               err |= true;
3607             }
3608
3609           for (i = 0; i < phi_num_args; i++)
3610             {
3611               tree t = PHI_ARG_DEF (phi, i);
3612               tree addr;
3613
3614               /* Addressable variables do have SSA_NAMEs but they
3615                  are not considered gimple values.  */
3616               if (TREE_CODE (t) != SSA_NAME
3617                   && TREE_CODE (t) != FUNCTION_DECL
3618                   && !is_gimple_val (t))
3619                 {
3620                   error ("PHI def is not a GIMPLE value");
3621                   debug_generic_stmt (phi);
3622                   debug_generic_stmt (t);
3623                   err |= true;
3624                 }
3625
3626               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
3627               if (addr)
3628                 {
3629                   debug_generic_stmt (addr);
3630                   err |= true;
3631                 }
3632
3633               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3634               if (addr)
3635                 {
3636                   error ("Incorrect sharing of tree nodes");
3637                   debug_generic_stmt (phi);
3638                   debug_generic_stmt (addr);
3639                   err |= true;
3640                 }
3641             }
3642         }
3643
3644       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3645         {
3646           tree stmt = bsi_stmt (bsi);
3647
3648           if (bb_for_stmt (stmt) != bb)
3649             {
3650               error ("bb_for_stmt (stmt) is set to a wrong basic block\n");
3651               err |= true;
3652             }
3653
3654           bsi_next (&bsi);
3655           err |= verify_stmt (stmt, bsi_end_p (bsi));
3656           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3657           if (addr)
3658             {
3659               error ("Incorrect sharing of tree nodes");
3660               debug_generic_stmt (stmt);
3661               debug_generic_stmt (addr);
3662               err |= true;
3663             }
3664         }
3665     }
3666
3667   if (err)
3668     internal_error ("verify_stmts failed.");
3669
3670   htab_delete (htab);
3671   timevar_pop (TV_TREE_STMT_VERIFY);
3672 }
3673
3674
3675 /* Verifies that the flow information is OK.  */
3676
3677 static int
3678 tree_verify_flow_info (void)
3679 {
3680   int err = 0;
3681   basic_block bb;
3682   block_stmt_iterator bsi;
3683   tree stmt;
3684   edge e;
3685   edge_iterator ei;
3686
3687   if (ENTRY_BLOCK_PTR->stmt_list)
3688     {
3689       error ("ENTRY_BLOCK has a statement list associated with it\n");
3690       err = 1;
3691     }
3692
3693   if (EXIT_BLOCK_PTR->stmt_list)
3694     {
3695       error ("EXIT_BLOCK has a statement list associated with it\n");
3696       err = 1;
3697     }
3698
3699   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3700     if (e->flags & EDGE_FALLTHRU)
3701       {
3702         error ("Fallthru to exit from bb %d\n", e->src->index);
3703         err = 1;
3704       }
3705
3706   FOR_EACH_BB (bb)
3707     {
3708       bool found_ctrl_stmt = false;
3709
3710       stmt = NULL_TREE;
3711
3712       /* Skip labels on the start of basic block.  */
3713       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3714         {
3715           tree prev_stmt = stmt;
3716
3717           stmt = bsi_stmt (bsi);
3718
3719           if (TREE_CODE (stmt) != LABEL_EXPR)
3720             break;
3721
3722           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3723             {
3724               error ("Nonlocal label %s is not first "
3725                      "in a sequence of labels in bb %d",
3726                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3727                      bb->index);
3728               err = 1;
3729             }
3730
3731           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3732             {
3733               error ("Label %s to block does not match in bb %d\n",
3734                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3735                      bb->index);
3736               err = 1;
3737             }
3738
3739           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3740               != current_function_decl)
3741             {
3742               error ("Label %s has incorrect context in bb %d\n",
3743                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3744                      bb->index);
3745               err = 1;
3746             }
3747         }
3748
3749       /* Verify that body of basic block BB is free of control flow.  */
3750       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3751         {
3752           tree stmt = bsi_stmt (bsi);
3753
3754           if (found_ctrl_stmt)
3755             {
3756               error ("Control flow in the middle of basic block %d\n",
3757                      bb->index);
3758               err = 1;
3759             }
3760
3761           if (stmt_ends_bb_p (stmt))
3762             found_ctrl_stmt = true;
3763
3764           if (TREE_CODE (stmt) == LABEL_EXPR)
3765             {
3766               error ("Label %s in the middle of basic block %d\n",
3767                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3768                      bb->index);
3769               err = 1;
3770             }
3771         }
3772       bsi = bsi_last (bb);
3773       if (bsi_end_p (bsi))
3774         continue;
3775
3776       stmt = bsi_stmt (bsi);
3777
3778       err |= verify_eh_edges (stmt);
3779
3780       if (is_ctrl_stmt (stmt))
3781         {
3782           FOR_EACH_EDGE (e, ei, bb->succs)
3783             if (e->flags & EDGE_FALLTHRU)
3784               {
3785                 error ("Fallthru edge after a control statement in bb %d \n",
3786                        bb->index);
3787                 err = 1;
3788               }
3789         }
3790
3791       switch (TREE_CODE (stmt))
3792         {
3793         case COND_EXPR:
3794           {
3795             edge true_edge;
3796             edge false_edge;
3797             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3798                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3799               {
3800                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3801                 err = 1;
3802               }
3803
3804             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3805
3806             if (!true_edge || !false_edge
3807                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3808                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3809                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3810                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3811                 || EDGE_COUNT (bb->succs) >= 3)
3812               {
3813                 error ("Wrong outgoing edge flags at end of bb %d\n",
3814                        bb->index);
3815                 err = 1;
3816               }
3817
3818             if (!has_label_p (true_edge->dest,
3819                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3820               {
3821                 error ("%<then%> label does not match edge at end of bb %d\n",
3822                        bb->index);
3823                 err = 1;
3824               }
3825
3826             if (!has_label_p (false_edge->dest,
3827                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3828               {
3829                 error ("%<else%> label does not match edge at end of bb %d\n",
3830                        bb->index);
3831                 err = 1;
3832               }
3833           }
3834           break;
3835
3836         case GOTO_EXPR:
3837           if (simple_goto_p (stmt))
3838             {
3839               error ("Explicit goto at end of bb %d\n", bb->index);
3840               err = 1;
3841             }
3842           else
3843             {
3844               /* FIXME.  We should double check that the labels in the 
3845                  destination blocks have their address taken.  */
3846               FOR_EACH_EDGE (e, ei, bb->succs)
3847                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3848                                  | EDGE_FALSE_VALUE))
3849                     || !(e->flags & EDGE_ABNORMAL))
3850                   {
3851                     error ("Wrong outgoing edge flags at end of bb %d\n",
3852                            bb->index);
3853                     err = 1;
3854                   }
3855             }
3856           break;
3857
3858         case RETURN_EXPR:
3859           if (!single_succ_p (bb)
3860               || (single_succ_edge (bb)->flags
3861                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
3862                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3863             {
3864               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3865               err = 1;
3866             }
3867           if (single_succ (bb) != EXIT_BLOCK_PTR)
3868             {
3869               error ("Return edge does not point to exit in bb %d\n",
3870                      bb->index);
3871               err = 1;
3872             }
3873           break;
3874
3875         case SWITCH_EXPR:
3876           {
3877             tree prev;
3878             edge e;
3879             size_t i, n;
3880             tree vec;
3881
3882             vec = SWITCH_LABELS (stmt);
3883             n = TREE_VEC_LENGTH (vec);
3884
3885             /* Mark all the destination basic blocks.  */
3886             for (i = 0; i < n; ++i)
3887               {
3888                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3889                 basic_block label_bb = label_to_block (lab);
3890
3891                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3892                 label_bb->aux = (void *)1;
3893               }
3894
3895             /* Verify that the case labels are sorted.  */
3896             prev = TREE_VEC_ELT (vec, 0);
3897             for (i = 1; i < n - 1; ++i)
3898               {
3899                 tree c = TREE_VEC_ELT (vec, i);
3900                 if (! CASE_LOW (c))
3901                   {
3902                     error ("Found default case not at end of case vector");
3903                     err = 1;
3904                     continue;
3905                   }
3906                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3907                   {
3908                     error ("Case labels not sorted:\n ");
3909                     print_generic_expr (stderr, prev, 0);
3910                     fprintf (stderr," is greater than ");
3911                     print_generic_expr (stderr, c, 0);
3912                     fprintf (stderr," but comes before it.\n");
3913                     err = 1;
3914                   }
3915                 prev = c;
3916               }
3917             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3918               {
3919                 error ("No default case found at end of case vector");
3920                 err = 1;
3921               }
3922
3923             FOR_EACH_EDGE (e, ei, bb->succs)
3924               {
3925                 if (!e->dest->aux)
3926                   {
3927                     error ("Extra outgoing edge %d->%d\n",
3928                            bb->index, e->dest->index);
3929                     err = 1;
3930                   }
3931                 e->dest->aux = (void *)2;
3932                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3933                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3934                   {
3935                     error ("Wrong outgoing edge flags at end of bb %d\n",
3936                            bb->index);
3937                     err = 1;
3938                   }
3939               }
3940
3941             /* Check that we have all of them.  */
3942             for (i = 0; i < n; ++i)
3943               {
3944                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3945                 basic_block label_bb = label_to_block (lab);
3946
3947                 if (label_bb->aux != (void *)2)
3948                   {
3949                     error ("Missing edge %i->%i",
3950                            bb->index, label_bb->index);
3951                     err = 1;
3952                   }
3953               }
3954
3955             FOR_EACH_EDGE (e, ei, bb->succs)
3956               e->dest->aux = (void *)0;
3957           }
3958
3959         default: ;
3960         }
3961     }
3962
3963   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3964     verify_dominators (CDI_DOMINATORS);
3965
3966   return err;
3967 }
3968
3969
3970 /* Updates phi nodes after creating a forwarder block joined
3971    by edge FALLTHRU.  */
3972
3973 static void
3974 tree_make_forwarder_block (edge fallthru)
3975 {
3976   edge e;
3977   edge_iterator ei;
3978   basic_block dummy, bb;
3979   tree phi, new_phi, var;
3980
3981   dummy = fallthru->src;
3982   bb = fallthru->dest;
3983
3984   if (single_pred_p (bb))
3985     return;
3986
3987   /* If we redirected a branch we must create new phi nodes at the
3988      start of BB.  */
3989   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3990     {
3991       var = PHI_RESULT (phi);
3992       new_phi = create_phi_node (var, bb);
3993       SSA_NAME_DEF_STMT (var) = new_phi;
3994       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3995       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3996     }
3997
3998   /* Ensure that the PHI node chain is in the same order.  */
3999   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
4000
4001   /* Add the arguments we have stored on edges.  */
4002   FOR_EACH_EDGE (e, ei, bb->preds)
4003     {
4004       if (e == fallthru)
4005         continue;
4006
4007       flush_pending_stmts (e);
4008     }
4009 }
4010
4011
4012 /* Return true if basic block BB does nothing except pass control
4013    flow to another block and that we can safely insert a label at
4014    the start of the successor block.
4015
4016    As a precondition, we require that BB be not equal to
4017    ENTRY_BLOCK_PTR.  */
4018
4019 static bool
4020 tree_forwarder_block_p (basic_block bb, bool phi_wanted)
4021 {
4022   block_stmt_iterator bsi;
4023
4024   /* BB must have a single outgoing edge.  */
4025   if (single_succ_p (bb) != 1
4026       /* If PHI_WANTED is false, BB must not have any PHI nodes.
4027          Otherwise, BB must have PHI nodes.  */
4028       || (phi_nodes (bb) != NULL_TREE) != phi_wanted
4029       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
4030       || single_succ (bb) == EXIT_BLOCK_PTR
4031       /* Nor should this be an infinite loop.  */
4032       || single_succ (bb) == bb
4033       /* BB may not have an abnormal outgoing edge.  */
4034       || (single_succ_edge (bb)->flags & EDGE_ABNORMAL))
4035     return false; 
4036
4037 #if ENABLE_CHECKING
4038   gcc_assert (bb != ENTRY_BLOCK_PTR);
4039 #endif
4040
4041   /* Now walk through the statements backward.  We can ignore labels,
4042      anything else means this is not a forwarder block.  */
4043   for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
4044     {
4045       tree stmt = bsi_stmt (bsi);
4046  
4047       switch (TREE_CODE (stmt))
4048         {
4049         case LABEL_EXPR:
4050           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
4051             return false;
4052           break;
4053
4054         default:
4055           return false;
4056         }
4057     }
4058
4059   if (find_edge (ENTRY_BLOCK_PTR, bb))
4060     return false;
4061
4062   if (current_loops)
4063     { 
4064       basic_block dest;
4065       /* Protect loop latches, headers and preheaders.  */
4066       if (bb->loop_father->header == bb)
4067         return false;
4068       dest = EDGE_SUCC (bb, 0)->dest;
4069  
4070       if (dest->loop_father->header == dest)
4071         return false;
4072     }
4073
4074   return true;
4075 }
4076
4077 /* Return true if BB has at least one abnormal incoming edge.  */
4078
4079 static inline bool
4080 has_abnormal_incoming_edge_p (basic_block bb)
4081 {
4082   edge e;
4083   edge_iterator ei;
4084
4085   FOR_EACH_EDGE (e, ei, bb->preds)
4086     if (e->flags & EDGE_ABNORMAL)
4087       return true;
4088
4089   return false;
4090 }
4091
4092 /* Removes forwarder block BB.  Returns false if this failed.  If a new
4093    forwarder block is created due to redirection of edges, it is
4094    stored to worklist.  */
4095
4096 static bool
4097 remove_forwarder_block (basic_block bb, basic_block **worklist)
4098 {
4099   edge succ = single_succ_edge (bb), e, s;
4100   basic_block dest = succ->dest;
4101   tree label;
4102   tree phi;
4103   edge_iterator ei;
4104   block_stmt_iterator bsi, bsi_to;
4105   bool seen_abnormal_edge = false;
4106
4107   /* We check for infinite loops already in tree_forwarder_block_p.
4108      However it may happen that the infinite loop is created
4109      afterwards due to removal of forwarders.  */
4110   if (dest == bb)
4111     return false;
4112
4113   /* If the destination block consists of a nonlocal label, do not merge
4114      it.  */
4115   label = first_stmt (dest);
4116   if (label
4117       && TREE_CODE (label) == LABEL_EXPR
4118       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
4119     return false;
4120
4121   /* If there is an abnormal edge to basic block BB, but not into
4122      dest, problems might occur during removal of the phi node at out
4123      of ssa due to overlapping live ranges of registers.
4124
4125      If there is an abnormal edge in DEST, the problems would occur
4126      anyway since cleanup_dead_labels would then merge the labels for
4127      two different eh regions, and rest of exception handling code
4128      does not like it.
4129      
4130      So if there is an abnormal edge to BB, proceed only if there is
4131      no abnormal edge to DEST and there are no phi nodes in DEST.  */
4132   if (has_abnormal_incoming_edge_p (bb))
4133     {
4134       seen_abnormal_edge = true;
4135
4136       if (has_abnormal_incoming_edge_p (dest)
4137           || phi_nodes (dest) != NULL_TREE)
4138         return false;
4139     }
4140
4141   /* If there are phi nodes in DEST, and some of the blocks that are
4142      predecessors of BB are also predecessors of DEST, check that the
4143      phi node arguments match.  */
4144   if (phi_nodes (dest))
4145     {
4146       FOR_EACH_EDGE (e, ei, bb->preds)
4147         {
4148           s = find_edge (e->src, dest);
4149           if (!s)
4150             continue;
4151
4152           if (!phi_alternatives_equal (dest, succ, s))
4153             return false;
4154         }
4155     }
4156
4157   /* Redirect the edges.  */
4158   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
4159     {
4160       if (e->flags & EDGE_ABNORMAL)
4161         {
4162           /* If there is an abnormal edge, redirect it anyway, and
4163              move the labels to the new block to make it legal.  */
4164           s = redirect_edge_succ_nodup (e, dest);
4165         }
4166       else
4167         s = redirect_edge_and_branch (e, dest);
4168
4169       if (s == e)
4170         {
4171           /* Create arguments for the phi nodes, since the edge was not
4172              here before.  */
4173           for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
4174             add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s);
4175         }
4176       else
4177         {
4178           /* The source basic block might become a forwarder.  We know
4179              that it was not a forwarder before, since it used to have
4180              at least two outgoing edges, so we may just add it to
4181              worklist.  */
4182           if (tree_forwarder_block_p (s->src, false))
4183             *(*worklist)++ = s->src;
4184         }
4185     }
4186
4187   if (seen_abnormal_edge)
4188     {
4189       /* Move the labels to the new block, so that the redirection of
4190          the abnormal edges works.  */
4191
4192       bsi_to = bsi_start (dest);
4193       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
4194         {
4195           label = bsi_stmt (bsi);
4196           gcc_assert (TREE_CODE (label) == LABEL_EXPR);
4197           bsi_remove (&bsi);
4198           bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING);
4199         }
4200     }
4201
4202   /* Update the dominators.  */
4203   if (dom_info_available_p (CDI_DOMINATORS))
4204     {
4205       basic_block dom, dombb, domdest;
4206
4207       dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
4208       domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
4209       if (domdest == bb)
4210         {
4211           /* Shortcut to avoid calling (relatively expensive)
4212              nearest_common_dominator unless necessary.  */
4213           dom = dombb;
4214         }
4215       else
4216         dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
4217
4218       set_immediate_dominator (CDI_DOMINATORS, dest, dom);
4219     }
4220
4221   /* And kill the forwarder block.  */
4222   delete_basic_block (bb);
4223
4224   return true;
4225 }
4226
4227 /* Removes forwarder blocks.  */
4228
4229 static bool
4230 cleanup_forwarder_blocks (void)
4231 {
4232   basic_block bb;
4233   bool changed = false;
4234   basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
4235   basic_block *current = worklist;
4236
4237   FOR_EACH_BB (bb)
4238     {
4239       if (tree_forwarder_block_p (bb, false))
4240         *current++ = bb;
4241     }
4242
4243   while (current != worklist)
4244     {
4245       bb = *--current;
4246       changed |= remove_forwarder_block (bb, &current);
4247     }
4248
4249   free (worklist);
4250   return changed;
4251 }
4252
4253 /* Merge the PHI nodes at BB into those at BB's sole successor.  */
4254
4255 static void
4256 remove_forwarder_block_with_phi (basic_block bb)
4257 {
4258   edge succ = single_succ_edge (bb);
4259   basic_block dest = succ->dest;
4260   tree label;
4261   basic_block dombb, domdest, dom;
4262
4263   /* We check for infinite loops already in tree_forwarder_block_p.
4264      However it may happen that the infinite loop is created
4265      afterwards due to removal of forwarders.  */
4266   if (dest == bb)
4267     return;
4268
4269   /* If the destination block consists of a nonlocal label, do not
4270      merge it.  */
4271   label = first_stmt (dest);
4272   if (label
4273       && TREE_CODE (label) == LABEL_EXPR
4274       && DECL_NONLOCAL (LABEL_EXPR_LABEL (label)))
4275     return;
4276
4277   /* Redirect each incoming edge to BB to DEST.  */
4278   while (EDGE_COUNT (bb->preds) > 0)
4279     {
4280       edge e = EDGE_PRED (bb, 0), s;
4281       tree phi;
4282
4283       s = find_edge (e->src, dest);
4284       if (s)
4285         {
4286           /* We already have an edge S from E->src to DEST.  If S and
4287              E->dest's sole successor edge have the same PHI arguments
4288              at DEST, redirect S to DEST.  */
4289           if (phi_alternatives_equal (dest, s, succ))
4290             {
4291               e = redirect_edge_and_branch (e, dest);
4292               PENDING_STMT (e) = NULL_TREE;
4293               continue;
4294             }
4295
4296           /* PHI arguments are different.  Create a forwarder block by
4297              splitting E so that we can merge PHI arguments on E to
4298              DEST.  */
4299           e = single_succ_edge (split_edge (e));
4300         }
4301
4302       s = redirect_edge_and_branch (e, dest);
4303
4304       /* redirect_edge_and_branch must not create a new edge.  */
4305       gcc_assert (s == e);
4306
4307       /* Add to the PHI nodes at DEST each PHI argument removed at the
4308          destination of E.  */
4309       for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
4310         {
4311           tree def = PHI_ARG_DEF (phi, succ->dest_idx);
4312
4313           if (TREE_CODE (def) == SSA_NAME)
4314             {
4315               tree var;
4316
4317               /* If DEF is one of the results of PHI nodes removed during
4318                  redirection, replace it with the PHI argument that used
4319                  to be on E.  */
4320               for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
4321                 {
4322                   tree old_arg = TREE_PURPOSE (var);
4323                   tree new_arg = TREE_VALUE (var);
4324
4325                   if (def == old_arg)
4326                     {
4327                       def = new_arg;
4328                       break;
4329                     }
4330                 }
4331             }
4332
4333           add_phi_arg (phi, def, s);
4334         }
4335
4336       PENDING_STMT (e) = NULL;
4337     }
4338
4339   /* Update the dominators.  */
4340   dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
4341   domdest = get_immediate_dominator (CDI_DOMINATORS, dest);
4342   if (domdest == bb)
4343     {
4344       /* Shortcut to avoid calling (relatively expensive)
4345          nearest_common_dominator unless necessary.  */
4346       dom = dombb;
4347     }
4348   else
4349     dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb);
4350
4351   set_immediate_dominator (CDI_DOMINATORS, dest, dom);
4352   
4353   /* Remove BB since all of BB's incoming edges have been redirected
4354      to DEST.  */
4355   delete_basic_block (bb);
4356 }
4357
4358 /* This pass merges PHI nodes if one feeds into another.  For example,
4359    suppose we have the following:
4360
4361   goto <bb 9> (<L9>);
4362
4363 <L8>:;
4364   tem_17 = foo ();
4365
4366   # tem_6 = PHI <tem_17(8), tem_23(7)>;
4367 <L9>:;
4368
4369   # tem_3 = PHI <tem_6(9), tem_2(5)>;
4370 <L10>:;
4371
4372   Then we merge the first PHI node into the second one like so:
4373
4374   goto <bb 9> (<L10>);
4375
4376 <L8>:;
4377   tem_17 = foo ();
4378
4379   # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>;
4380 <L10>:;
4381 */
4382
4383 static void
4384 merge_phi_nodes (void)
4385 {
4386   basic_block *worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
4387   basic_block *current = worklist;
4388   basic_block bb;
4389
4390   calculate_dominance_info (CDI_DOMINATORS);
4391
4392   /* Find all PHI nodes that we may be able to merge.  */
4393   FOR_EACH_BB (bb)
4394     {
4395       basic_block dest;
4396
4397       /* Look for a forwarder block with PHI nodes.  */
4398       if (!tree_forwarder_block_p (bb, true))
4399         continue;
4400
4401       dest = single_succ (bb);
4402
4403       /* We have to feed into another basic block with PHI
4404          nodes.  */
4405       if (!phi_nodes (dest)
4406           /* We don't want to deal with a basic block with
4407              abnormal edges.  */
4408           || has_abnormal_incoming_edge_p (bb))
4409         continue;
4410
4411       if (!dominated_by_p (CDI_DOMINATORS, dest, bb))
4412         {
4413           /* If BB does not dominate DEST, then the PHI nodes at
4414              DEST must be the only users of the results of the PHI
4415              nodes at BB.  */
4416           *current++ = bb;
4417         }
4418     }
4419
4420   /* Now let's drain WORKLIST.  */
4421   while (current != worklist)
4422     {
4423       bb = *--current;
4424       remove_forwarder_block_with_phi (bb);
4425     }
4426
4427   free (worklist);
4428 }
4429
4430 static bool
4431 gate_merge_phi (void)
4432 {
4433   return 1;
4434 }
4435
4436 struct tree_opt_pass pass_merge_phi = {
4437   "mergephi",                   /* name */
4438   gate_merge_phi,               /* gate */
4439   merge_phi_nodes,              /* execute */
4440   NULL,                         /* sub */
4441   NULL,                         /* next */
4442   0,                            /* static_pass_number */
4443   TV_TREE_MERGE_PHI,            /* tv_id */
4444   PROP_cfg | PROP_ssa,          /* properties_required */
4445   0,                            /* properties_provided */
4446   0,                            /* properties_destroyed */
4447   0,                            /* todo_flags_start */
4448   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
4449   | TODO_verify_ssa,
4450   0                             /* letter */
4451 };
4452
4453 /* Return a non-special label in the head of basic block BLOCK.
4454    Create one if it doesn't exist.  */
4455
4456 tree
4457 tree_block_label (basic_block bb)
4458 {
4459   block_stmt_iterator i, s = bsi_start (bb);
4460   bool first = true;
4461   tree label, stmt;
4462
4463   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4464     {
4465       stmt = bsi_stmt (i);
4466       if (TREE_CODE (stmt) != LABEL_EXPR)
4467         break;
4468       label = LABEL_EXPR_LABEL (stmt);
4469       if (!DECL_NONLOCAL (label))
4470         {
4471           if (!first)
4472             bsi_move_before (&i, &s);
4473           return label;
4474         }
4475     }
4476
4477   label = create_artificial_label ();
4478   stmt = build1 (LABEL_EXPR, void_type_node, label);
4479   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4480   return label;
4481 }
4482
4483
4484 /* Attempt to perform edge redirection by replacing a possibly complex
4485    jump instruction by a goto or by removing the jump completely.
4486    This can apply only if all edges now point to the same block.  The
4487    parameters and return values are equivalent to
4488    redirect_edge_and_branch.  */
4489
4490 static edge
4491 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4492 {
4493   basic_block src = e->src;
4494   block_stmt_iterator b;
4495   tree stmt;
4496
4497   /* We can replace or remove a complex jump only when we have exactly
4498      two edges.  */
4499   if (EDGE_COUNT (src->succs) != 2
4500       /* Verify that all targets will be TARGET.  Specifically, the
4501          edge that is not E must also go to TARGET.  */
4502       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4503     return NULL;
4504
4505   b = bsi_last (src);
4506   if (bsi_end_p (b))
4507     return NULL;
4508   stmt = bsi_stmt (b);
4509
4510   if (TREE_CODE (stmt) == COND_EXPR
4511       || TREE_CODE (stmt) == SWITCH_EXPR)
4512     {
4513       bsi_remove (&b);
4514       e = ssa_redirect_edge (e, target);
4515       e->flags = EDGE_FALLTHRU;
4516       return e;
4517     }
4518
4519   return NULL;
4520 }
4521
4522
4523 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4524    edge representing the redirected branch.  */
4525
4526 static edge
4527 tree_redirect_edge_and_branch (edge e, basic_block dest)
4528 {
4529   basic_block bb = e->src;
4530   block_stmt_iterator bsi;
4531   edge ret;
4532   tree label, stmt;
4533
4534   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4535     return NULL;
4536
4537   if (e->src != ENTRY_BLOCK_PTR 
4538       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4539     return ret;
4540
4541   if (e->dest == dest)
4542     return NULL;
4543
4544   label = tree_block_label (dest);
4545
4546   bsi = bsi_last (bb);
4547   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4548
4549   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4550     {
4551     case COND_EXPR:
4552       stmt = (e->flags & EDGE_TRUE_VALUE
4553               ? COND_EXPR_THEN (stmt)
4554               : COND_EXPR_ELSE (stmt));
4555       GOTO_DESTINATION (stmt) = label;
4556       break;
4557
4558     case GOTO_EXPR:
4559       /* No non-abnormal edges should lead from a non-simple goto, and
4560          simple ones should be represented implicitly.  */
4561       gcc_unreachable ();
4562
4563     case SWITCH_EXPR:
4564       {
4565         tree cases = get_cases_for_edge (e, stmt);
4566
4567         /* If we have a list of cases associated with E, then use it
4568            as it's a lot faster than walking the entire case vector.  */
4569         if (cases)
4570           {
4571             edge e2 = find_edge (e->src, dest);
4572             tree last, first;
4573
4574             first = cases;
4575             while (cases)
4576               {
4577                 last = cases;
4578                 CASE_LABEL (cases) = label;
4579                 cases = TREE_CHAIN (cases);
4580               }
4581
4582             /* If there was already an edge in the CFG, then we need
4583                to move all the cases associated with E to E2.  */
4584             if (e2)
4585               {
4586                 tree cases2 = get_cases_for_edge (e2, stmt);
4587
4588                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4589                 TREE_CHAIN (cases2) = first;
4590               }
4591           }
4592         else
4593           {
4594             tree vec = SWITCH_LABELS (stmt);
4595             size_t i, n = TREE_VEC_LENGTH (vec);
4596
4597             for (i = 0; i < n; i++)
4598               {
4599                 tree elt = TREE_VEC_ELT (vec, i);
4600
4601                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4602                   CASE_LABEL (elt) = label;
4603               }
4604           }
4605
4606         break;
4607       }
4608
4609     case RETURN_EXPR:
4610       bsi_remove (&bsi);
4611       e->flags |= EDGE_FALLTHRU;
4612       break;
4613
4614     default:
4615       /* Otherwise it must be a fallthru edge, and we don't need to
4616          do anything besides redirecting it.  */
4617       gcc_assert (e->flags & EDGE_FALLTHRU);
4618       break;
4619     }
4620
4621   /* Update/insert PHI nodes as necessary.  */
4622
4623   /* Now update the edges in the CFG.  */
4624   e = ssa_redirect_edge (e, dest);
4625
4626   return e;
4627 }
4628
4629
4630 /* Simple wrapper, as we can always redirect fallthru edges.  */
4631
4632 static basic_block
4633 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4634 {
4635   e = tree_redirect_edge_and_branch (e, dest);
4636   gcc_assert (e);
4637
4638   return NULL;
4639 }
4640
4641
4642 /* Splits basic block BB after statement STMT (but at least after the
4643    labels).  If STMT is NULL, BB is split just after the labels.  */
4644
4645 static basic_block
4646 tree_split_block (basic_block bb, void *stmt)
4647 {
4648   block_stmt_iterator bsi, bsi_tgt;
4649   tree act;
4650   basic_block new_bb;
4651   edge e;
4652   edge_iterator ei;
4653
4654   new_bb = create_empty_bb (bb);
4655
4656   /* Redirect the outgoing edges.  */
4657   new_bb->succs = bb->succs;
4658   bb->succs = NULL;
4659   FOR_EACH_EDGE (e, ei, new_bb->succs)
4660     e->src = new_bb;
4661
4662   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4663     stmt = NULL;
4664
4665   /* Move everything from BSI to the new basic block.  */
4666   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4667     {
4668       act = bsi_stmt (bsi);
4669       if (TREE_CODE (act) == LABEL_EXPR)
4670         continue;
4671
4672       if (!stmt)
4673         break;
4674
4675       if (stmt == act)
4676         {
4677           bsi_next (&bsi);
4678           break;
4679         }
4680     }
4681
4682   bsi_tgt = bsi_start (new_bb);
4683   while (!bsi_end_p (bsi))
4684     {
4685       act = bsi_stmt (bsi);
4686       bsi_remove (&bsi);
4687       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4688     }
4689
4690   return new_bb;
4691 }
4692
4693
4694 /* Moves basic block BB after block AFTER.  */
4695
4696 static bool
4697 tree_move_block_after (basic_block bb, basic_block after)
4698 {
4699   if (bb->prev_bb == after)
4700     return true;
4701
4702   unlink_block (bb);
4703   link_block (bb, after);
4704
4705   return true;
4706 }
4707
4708
4709 /* Return true if basic_block can be duplicated.  */
4710
4711 static bool
4712 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4713 {
4714   return true;
4715 }
4716
4717
4718 /* Create a duplicate of the basic block BB.  NOTE: This does not
4719    preserve SSA form.  */
4720
4721 static basic_block
4722 tree_duplicate_bb (basic_block bb)
4723 {
4724   basic_block new_bb;
4725   block_stmt_iterator bsi, bsi_tgt;
4726   tree phi;
4727
4728   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4729
4730   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4731      the incoming edges have not been setup yet.  */
4732   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4733     {
4734       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4735       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4736     }
4737
4738   /* Keep the chain of PHI nodes in the same order so that they can be
4739      updated by ssa_redirect_edge.  */
4740   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4741
4742   bsi_tgt = bsi_start (new_bb);
4743   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4744     {
4745       def_operand_p def_p;
4746       ssa_op_iter op_iter;
4747       tree stmt, copy;
4748       int region;
4749
4750       stmt = bsi_stmt (bsi);
4751       if (TREE_CODE (stmt) == LABEL_EXPR)
4752         continue;
4753
4754       /* Create a new copy of STMT and duplicate STMT's virtual
4755          operands.  */
4756       copy = unshare_expr (stmt);
4757       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4758       copy_virtual_operands (copy, stmt);
4759       region = lookup_stmt_eh_region (stmt);
4760       if (region >= 0)
4761         add_stmt_to_eh_region (copy, region);
4762
4763       /* Create new names for all the definitions created by COPY and
4764          add replacement mappings for each new name.  */
4765       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4766         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4767     }
4768
4769   return new_bb;
4770 }
4771
4772
4773 /* Basic block BB_COPY was created by code duplication.  Add phi node
4774    arguments for edges going out of BB_COPY.  The blocks that were
4775    duplicated have rbi->duplicated set to one.  */
4776
4777 void
4778 add_phi_args_after_copy_bb (basic_block bb_copy)
4779 {
4780   basic_block bb, dest;
4781   edge e, e_copy;
4782   edge_iterator ei;
4783   tree phi, phi_copy, phi_next, def;
4784       
4785   bb = bb_copy->rbi->original;
4786
4787   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4788     {
4789       if (!phi_nodes (e_copy->dest))
4790         continue;
4791
4792       if (e_copy->dest->rbi->duplicated)
4793         dest = e_copy->dest->rbi->original;
4794       else
4795         dest = e_copy->dest;
4796
4797       e = find_edge (bb, dest);
4798       if (!e)
4799         {
4800           /* During loop unrolling the target of the latch edge is copied.
4801              In this case we are not looking for edge to dest, but to
4802              duplicated block whose original was dest.  */
4803           FOR_EACH_EDGE (e, ei, bb->succs)
4804             if (e->dest->rbi->duplicated
4805                 && e->dest->rbi->original == dest)
4806               break;
4807
4808           gcc_assert (e != NULL);
4809         }
4810
4811       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4812            phi;
4813            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4814         {
4815           phi_next = PHI_CHAIN (phi);
4816           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4817           add_phi_arg (phi_copy, def, e_copy);
4818         }
4819     }
4820 }
4821
4822 /* Blocks in REGION_COPY array of length N_REGION were created by
4823    duplication of basic blocks.  Add phi node arguments for edges
4824    going from these blocks.  */
4825
4826 void
4827 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4828 {
4829   unsigned i;
4830
4831   for (i = 0; i < n_region; i++)
4832     region_copy[i]->rbi->duplicated = 1;
4833
4834   for (i = 0; i < n_region; i++)
4835     add_phi_args_after_copy_bb (region_copy[i]);
4836
4837   for (i = 0; i < n_region; i++)
4838     region_copy[i]->rbi->duplicated = 0;
4839 }
4840
4841 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4842    important exit edge EXIT.  By important we mean that no SSA name defined
4843    inside region is live over the other exit edges of the region.  All entry
4844    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4845    to the duplicate of the region.  SSA form, dominance and loop information
4846    is updated.  The new basic blocks are stored to REGION_COPY in the same
4847    order as they had in REGION, provided that REGION_COPY is not NULL.
4848    The function returns false if it is unable to copy the region,
4849    true otherwise.  */
4850
4851 bool
4852 tree_duplicate_sese_region (edge entry, edge exit,
4853                             basic_block *region, unsigned n_region,
4854                             basic_block *region_copy)
4855 {
4856   unsigned i, n_doms;
4857   bool free_region_copy = false, copying_header = false;
4858   struct loop *loop = entry->dest->loop_father;
4859   edge exit_copy;
4860   basic_block *doms;
4861   edge redirected;
4862   int total_freq, entry_freq;
4863
4864   if (!can_copy_bbs_p (region, n_region))
4865     return false;
4866
4867   /* Some sanity checking.  Note that we do not check for all possible
4868      missuses of the functions.  I.e. if you ask to copy something weird,
4869      it will work, but the state of structures probably will not be
4870      correct.  */
4871   for (i = 0; i < n_region; i++)
4872     {
4873       /* We do not handle subloops, i.e. all the blocks must belong to the
4874          same loop.  */
4875       if (region[i]->loop_father != loop)
4876         return false;
4877
4878       if (region[i] != entry->dest
4879           && region[i] == loop->header)
4880         return false;
4881     }
4882
4883   loop->copy = loop;
4884
4885   /* In case the function is used for loop header copying (which is the primary
4886      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4887   if (loop->header == entry->dest)
4888     {
4889       copying_header = true;
4890       loop->copy = loop->outer;
4891
4892       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4893         return false;
4894
4895       for (i = 0; i < n_region; i++)
4896         if (region[i] != exit->src
4897             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4898           return false;
4899     }
4900
4901   if (!region_copy)
4902     {
4903       region_copy = xmalloc (sizeof (basic_block) * n_region);
4904       free_region_copy = true;
4905     }
4906
4907   gcc_assert (!need_ssa_update_p ());
4908
4909   /* Record blocks outside the region that are dominated by something
4910      inside.  */
4911   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
4912   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4913
4914   total_freq = entry->dest->frequency;
4915   entry_freq = EDGE_FREQUENCY (entry);
4916   /* Fix up corner cases, to avoid division by zero or creation of negative
4917      frequencies.  */
4918   if (total_freq == 0)
4919     total_freq = 1;
4920   else if (entry_freq > total_freq)
4921     entry_freq = total_freq;
4922
4923   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
4924   scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4925                              total_freq);
4926   scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4927
4928   if (copying_header)
4929     {
4930       loop->header = exit->dest;
4931       loop->latch = exit->src;
4932     }
4933
4934   /* Redirect the entry and add the phi node arguments.  */
4935   redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy);
4936   gcc_assert (redirected != NULL);
4937   flush_pending_stmts (entry);
4938
4939   /* Concerning updating of dominators:  We must recount dominators
4940      for entry block and its copy.  Anything that is outside of the
4941      region, but was dominated by something inside needs recounting as
4942      well.  */
4943   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4944   doms[n_doms++] = entry->dest->rbi->original;
4945   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4946   free (doms);
4947
4948   /* Add the other PHI node arguments.  */
4949   add_phi_args_after_copy (region_copy, n_region);
4950
4951   /* Update the SSA web.  */
4952   update_ssa (TODO_update_ssa);
4953
4954   if (free_region_copy)
4955     free (region_copy);
4956
4957   return true;
4958 }
4959
4960
4961 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4962
4963 void
4964 dump_function_to_file (tree fn, FILE *file, int flags)
4965 {
4966   tree arg, vars, var;
4967   bool ignore_topmost_bind = false, any_var = false;
4968   basic_block bb;
4969   tree chain;
4970
4971   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4972
4973   arg = DECL_ARGUMENTS (fn);
4974   while (arg)
4975     {
4976       print_generic_expr (file, arg, dump_flags);
4977       if (TREE_CHAIN (arg))
4978         fprintf (file, ", ");
4979       arg = TREE_CHAIN (arg);
4980     }
4981   fprintf (file, ")\n");
4982
4983   if (flags & TDF_DETAILS)
4984     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
4985   if (flags & TDF_RAW)
4986     {
4987       dump_node (fn, TDF_SLIM | flags, file);
4988       return;
4989     }
4990
4991   /* When GIMPLE is lowered, the variables are no longer available in
4992      BIND_EXPRs, so display them separately.  */
4993   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
4994     {
4995       ignore_topmost_bind = true;
4996
4997       fprintf (file, "{\n");
4998       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4999         {
5000           var = TREE_VALUE (vars);
5001
5002           print_generic_decl (file, var, flags);
5003           fprintf (file, "\n");
5004
5005           any_var = true;
5006         }
5007     }
5008
5009   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
5010     {
5011       /* Make a CFG based dump.  */
5012       check_bb_profile (ENTRY_BLOCK_PTR, file);
5013       if (!ignore_topmost_bind)
5014         fprintf (file, "{\n");
5015
5016       if (any_var && n_basic_blocks)
5017         fprintf (file, "\n");
5018
5019       FOR_EACH_BB (bb)
5020         dump_generic_bb (file, bb, 2, flags);
5021         
5022       fprintf (file, "}\n");
5023       check_bb_profile (EXIT_BLOCK_PTR, file);
5024     }
5025   else
5026     {
5027       int indent;
5028
5029       /* Make a tree based dump.  */
5030       chain = DECL_SAVED_TREE (fn);
5031
5032       if (TREE_CODE (chain) == BIND_EXPR)
5033         {
5034           if (ignore_topmost_bind)
5035             {
5036               chain = BIND_EXPR_BODY (chain);
5037               indent = 2;
5038             }
5039           else
5040             indent = 0;
5041         }
5042       else
5043         {
5044           if (!ignore_topmost_bind)
5045             fprintf (file, "{\n");
5046           indent = 2;
5047         }
5048
5049       if (any_var)
5050         fprintf (file, "\n");
5051
5052       print_generic_stmt_indented (file, chain, flags, indent);
5053       if (ignore_topmost_bind)
5054         fprintf (file, "}\n");
5055     }
5056
5057   fprintf (file, "\n\n");
5058 }
5059
5060
5061 /* Pretty print of the loops intermediate representation.  */
5062 static void print_loop (FILE *, struct loop *, int);
5063 static void print_pred_bbs (FILE *, basic_block bb);
5064 static void print_succ_bbs (FILE *, basic_block bb);
5065
5066
5067 /* Print the predecessors indexes of edge E on FILE.  */
5068
5069 static void
5070 print_pred_bbs (FILE *file, basic_block bb)
5071 {
5072   edge e;
5073   edge_iterator ei;
5074
5075   FOR_EACH_EDGE (e, ei, bb->preds)
5076     fprintf (file, "bb_%d", e->src->index);
5077 }
5078
5079
5080 /* Print the successors indexes of edge E on FILE.  */
5081
5082 static void
5083 print_succ_bbs (FILE *file, basic_block bb)
5084 {
5085   edge e;
5086   edge_iterator ei;
5087
5088   FOR_EACH_EDGE (e, ei, bb->succs)
5089     fprintf (file, "bb_%d", e->src->index);
5090 }
5091
5092
5093 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5094
5095 static void
5096 print_loop (FILE *file, struct loop *loop, int indent)
5097 {
5098   char *s_indent;
5099   basic_block bb;
5100   
5101   if (loop == NULL)
5102     return;
5103
5104   s_indent = (char *) alloca ((size_t) indent + 1);
5105   memset ((void *) s_indent, ' ', (size_t) indent);
5106   s_indent[indent] = '\0';
5107
5108   /* Print the loop's header.  */
5109   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5110   
5111   /* Print the loop's body.  */
5112   fprintf (file, "%s{\n", s_indent);
5113   FOR_EACH_BB (bb)
5114     if (bb->loop_father == loop)
5115       {
5116         /* Print the basic_block's header.  */
5117         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5118         print_pred_bbs (file, bb);
5119         fprintf (file, "}, succs = {");
5120         print_succ_bbs (file, bb);
5121         fprintf (file, "})\n");
5122         
5123         /* Print the basic_block's body.  */
5124         fprintf (file, "%s  {\n", s_indent);
5125         tree_dump_bb (bb, file, indent + 4);
5126         fprintf (file, "%s  }\n", s_indent);
5127       }
5128   
5129   print_loop (file, loop->inner, indent + 2);
5130   fprintf (file, "%s}\n", s_indent);
5131   print_loop (file, loop->next, indent);
5132 }
5133
5134
5135 /* Follow a CFG edge from the entry point of the program, and on entry
5136    of a loop, pretty print the loop structure on FILE.  */
5137
5138 void 
5139 print_loop_ir (FILE *file)
5140 {
5141   basic_block bb;
5142   
5143   bb = BASIC_BLOCK (0);
5144   if (bb && bb->loop_father)
5145     print_loop (file, bb->loop_father, 0);
5146 }
5147
5148
5149 /* Debugging loops structure at tree level.  */
5150
5151 void 
5152 debug_loop_ir (void)
5153 {
5154   print_loop_ir (stderr);
5155 }
5156
5157
5158 /* Return true if BB ends with a call, possibly followed by some
5159    instructions that must stay with the call.  Return false,
5160    otherwise.  */
5161
5162 static bool
5163 tree_block_ends_with_call_p (basic_block bb)
5164 {
5165   block_stmt_iterator bsi = bsi_last (bb);
5166   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5167 }
5168
5169
5170 /* Return true if BB ends with a conditional branch.  Return false,
5171    otherwise.  */
5172
5173 static bool
5174 tree_block_ends_with_condjump_p (basic_block bb)
5175 {
5176   tree stmt = last_stmt (bb);
5177   return (stmt && TREE_CODE (stmt) == COND_EXPR);
5178 }
5179
5180
5181 /* Return true if we need to add fake edge to exit at statement T.
5182    Helper function for tree_flow_call_edges_add.  */
5183
5184 static bool
5185 need_fake_edge_p (tree t)
5186 {
5187   tree call;
5188
5189   /* NORETURN and LONGJMP calls already have an edge to exit.
5190      CONST and PURE calls do not need one.
5191      We don't currently check for CONST and PURE here, although
5192      it would be a good idea, because those attributes are
5193      figured out from the RTL in mark_constant_function, and
5194      the counter incrementation code from -fprofile-arcs
5195      leads to different results from -fbranch-probabilities.  */
5196   call = get_call_expr_in (t);
5197   if (call
5198       && !(call_expr_flags (call) & ECF_NORETURN))
5199     return true;
5200
5201   if (TREE_CODE (t) == ASM_EXPR
5202        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5203     return true;
5204
5205   return false;
5206 }
5207
5208
5209 /* Add fake edges to the function exit for any non constant and non
5210    noreturn calls, volatile inline assembly in the bitmap of blocks
5211    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5212    the number of blocks that were split.
5213
5214    The goal is to expose cases in which entering a basic block does
5215    not imply that all subsequent instructions must be executed.  */
5216
5217 static int
5218 tree_flow_call_edges_add (sbitmap blocks)
5219 {
5220   int i;
5221   int blocks_split = 0;
5222   int last_bb = last_basic_block;
5223   bool check_last_block = false;
5224
5225   if (n_basic_blocks == 0)
5226     return 0;
5227
5228   if (! blocks)
5229     check_last_block = true;
5230   else
5231     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5232
5233   /* In the last basic block, before epilogue generation, there will be
5234      a fallthru edge to EXIT.  Special care is required if the last insn
5235      of the last basic block is a call because make_edge folds duplicate
5236      edges, which would result in the fallthru edge also being marked
5237      fake, which would result in the fallthru edge being removed by
5238      remove_fake_edges, which would result in an invalid CFG.
5239
5240      Moreover, we can't elide the outgoing fake edge, since the block
5241      profiler needs to take this into account in order to solve the minimal
5242      spanning tree in the case that the call doesn't return.
5243
5244      Handle this by adding a dummy instruction in a new last basic block.  */
5245   if (check_last_block)
5246     {
5247       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5248       block_stmt_iterator bsi = bsi_last (bb);
5249       tree t = NULL_TREE;
5250       if (!bsi_end_p (bsi))
5251         t = bsi_stmt (bsi);
5252
5253       if (need_fake_edge_p (t))
5254         {
5255           edge e;
5256
5257           e = find_edge (bb, EXIT_BLOCK_PTR);
5258           if (e)
5259             {
5260               bsi_insert_on_edge (e, build_empty_stmt ());
5261               bsi_commit_edge_inserts ();
5262             }
5263         }
5264     }
5265
5266   /* Now add fake edges to the function exit for any non constant
5267      calls since there is no way that we can determine if they will
5268      return or not...  */
5269   for (i = 0; i < last_bb; i++)
5270     {
5271       basic_block bb = BASIC_BLOCK (i);
5272       block_stmt_iterator bsi;
5273       tree stmt, last_stmt;
5274
5275       if (!bb)
5276         continue;
5277
5278       if (blocks && !TEST_BIT (blocks, i))
5279         continue;
5280
5281       bsi = bsi_last (bb);
5282       if (!bsi_end_p (bsi))
5283         {
5284           last_stmt = bsi_stmt (bsi);
5285           do
5286             {
5287               stmt = bsi_stmt (bsi);
5288               if (need_fake_edge_p (stmt))
5289                 {
5290                   edge e;
5291                   /* The handling above of the final block before the
5292                      epilogue should be enough to verify that there is
5293                      no edge to the exit block in CFG already.
5294                      Calling make_edge in such case would cause us to
5295                      mark that edge as fake and remove it later.  */
5296 #ifdef ENABLE_CHECKING
5297                   if (stmt == last_stmt)
5298                     {
5299                       e = find_edge (bb, EXIT_BLOCK_PTR);
5300                       gcc_assert (e == NULL);
5301                     }
5302 #endif
5303
5304                   /* Note that the following may create a new basic block
5305                      and renumber the existing basic blocks.  */
5306                   if (stmt != last_stmt)
5307                     {
5308                       e = split_block (bb, stmt);
5309                       if (e)
5310                         blocks_split++;
5311                     }
5312                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5313                 }
5314               bsi_prev (&bsi);
5315             }
5316           while (!bsi_end_p (bsi));
5317         }
5318     }
5319
5320   if (blocks_split)
5321     verify_flow_info ();
5322
5323   return blocks_split;
5324 }
5325
5326 bool
5327 tree_purge_dead_eh_edges (basic_block bb)
5328 {
5329   bool changed = false;
5330   edge e;
5331   edge_iterator ei;
5332   tree stmt = last_stmt (bb);
5333
5334   if (stmt && tree_can_throw_internal (stmt))
5335     return false;
5336
5337   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5338     {
5339       if (e->flags & EDGE_EH)
5340         {
5341           remove_edge (e);
5342           changed = true;
5343         }
5344       else
5345         ei_next (&ei);
5346     }
5347
5348   /* Removal of dead EH edges might change dominators of not
5349      just immediate successors.  E.g. when bb1 is changed so that
5350      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5351      eh edges purged by this function in:
5352            0
5353           / \
5354          v   v
5355          1-->2
5356         / \  |
5357        v   v |
5358        3-->4 |
5359         \    v
5360          --->5
5361              |
5362              -
5363      idom(bb5) must be recomputed.  For now just free the dominance
5364      info.  */
5365   if (changed)
5366     free_dominance_info (CDI_DOMINATORS);
5367
5368   return changed;
5369 }
5370
5371 bool
5372 tree_purge_all_dead_eh_edges (bitmap blocks)
5373 {
5374   bool changed = false;
5375   unsigned i;
5376   bitmap_iterator bi;
5377
5378   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5379     {
5380       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5381     }
5382
5383   return changed;
5384 }
5385
5386 /* This function is called whenever a new edge is created or
5387    redirected.  */
5388
5389 static void
5390 tree_execute_on_growing_pred (edge e)
5391 {
5392   basic_block bb = e->dest;
5393
5394   if (phi_nodes (bb))
5395     reserve_phi_args_for_new_edge (bb);
5396 }
5397
5398 /* This function is called immediately before edge E is removed from
5399    the edge vector E->dest->preds.  */
5400
5401 static void
5402 tree_execute_on_shrinking_pred (edge e)
5403 {
5404   if (phi_nodes (e->dest))
5405     remove_phi_args (e);
5406 }
5407
5408 /*---------------------------------------------------------------------------
5409   Helper functions for Loop versioning
5410   ---------------------------------------------------------------------------*/
5411
5412 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
5413    of 'first'. Both of them are dominated by 'new_head' basic block. When
5414    'new_head' was created by 'second's incoming edge it received phi arguments
5415    on the edge by split_edge(). Later, additional edge 'e' was created to
5416    connect 'new_head' and 'first'. Now this routine adds phi args on this 
5417    additional edge 'e' that new_head to second edge received as part of edge 
5418    splitting.
5419 */
5420
5421 static void
5422 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
5423                                 basic_block new_head, edge e)
5424 {
5425   tree phi1, phi2;
5426   edge e2 = find_edge (new_head, second);
5427
5428   /* Because NEW_HEAD has been created by splitting SECOND's incoming
5429      edge, we should always have an edge from NEW_HEAD to SECOND.  */
5430   gcc_assert (e2 != NULL);
5431
5432   /* Browse all 'second' basic block phi nodes and add phi args to
5433      edge 'e' for 'first' head. PHI args are always in correct order.  */
5434
5435   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); 
5436        phi2 && phi1; 
5437        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
5438     {
5439       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
5440       add_phi_arg (phi1, def, e);
5441     }
5442 }
5443
5444 /* Adds a if else statement to COND_BB with condition COND_EXPR.  
5445    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is 
5446    the destination of the ELSE part.  */
5447 static void
5448 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
5449                             basic_block cond_bb, void *cond_e)
5450 {
5451   block_stmt_iterator bsi;
5452   tree goto1 = NULL_TREE;
5453   tree goto2 = NULL_TREE;
5454   tree new_cond_expr = NULL_TREE;
5455   tree cond_expr = (tree) cond_e;
5456   edge e0;
5457
5458   /* Build new conditional expr */
5459   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
5460   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
5461   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
5462
5463   /* Add new cond in cond_bb.  */ 
5464   bsi = bsi_start (cond_bb); 
5465   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
5466   /* Adjust edges appropriately to connect new head with first head
5467      as well as second head.  */
5468   e0 = single_succ_edge (cond_bb);
5469   e0->flags &= ~EDGE_FALLTHRU;
5470   e0->flags |= EDGE_FALSE_VALUE;
5471 }
5472
5473 struct cfg_hooks tree_cfg_hooks = {
5474   "tree",
5475   tree_verify_flow_info,
5476   tree_dump_bb,                 /* dump_bb  */
5477   create_bb,                    /* create_basic_block  */
5478   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5479   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5480   remove_bb,                    /* delete_basic_block  */
5481   tree_split_block,             /* split_block  */
5482   tree_move_block_after,        /* move_block_after  */
5483   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5484   tree_merge_blocks,            /* merge_blocks  */
5485   tree_predict_edge,            /* predict_edge  */
5486   tree_predicted_by_p,          /* predicted_by_p  */
5487   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5488   tree_duplicate_bb,            /* duplicate_block  */
5489   tree_split_edge,              /* split_edge  */
5490   tree_make_forwarder_block,    /* make_forward_block  */
5491   NULL,                         /* tidy_fallthru_edge  */
5492   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5493   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5494   tree_flow_call_edges_add,     /* flow_call_edges_add */
5495   tree_execute_on_growing_pred, /* execute_on_growing_pred */
5496   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
5497   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
5498   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5499   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
5500   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
5501   flush_pending_stmts           /* flush_pending_stmts */  
5502 };
5503
5504
5505 /* Split all critical edges.  */
5506
5507 static void
5508 split_critical_edges (void)
5509 {
5510   basic_block bb;
5511   edge e;
5512   edge_iterator ei;
5513
5514   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5515      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5516      mappings around the calls to split_edge.  */
5517   start_recording_case_labels ();
5518   FOR_ALL_BB (bb)
5519     {
5520       FOR_EACH_EDGE (e, ei, bb->succs)
5521         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5522           {
5523             split_edge (e);
5524           }
5525     }
5526   end_recording_case_labels ();
5527 }
5528
5529 struct tree_opt_pass pass_split_crit_edges = 
5530 {
5531   "crited",                          /* name */
5532   NULL,                          /* gate */
5533   split_critical_edges,          /* execute */
5534   NULL,                          /* sub */
5535   NULL,                          /* next */
5536   0,                             /* static_pass_number */
5537   TV_TREE_SPLIT_EDGES,           /* tv_id */
5538   PROP_cfg,                      /* properties required */
5539   PROP_no_crit_edges,            /* properties_provided */
5540   0,                             /* properties_destroyed */
5541   0,                             /* todo_flags_start */
5542   TODO_dump_func,                /* todo_flags_finish */
5543   0                              /* letter */
5544 };
5545
5546 \f
5547 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5548    a temporary, make sure and register it to be renamed if necessary,
5549    and finally return the temporary.  Put the statements to compute
5550    EXP before the current statement in BSI.  */
5551
5552 tree
5553 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5554 {
5555   tree t, new_stmt, orig_stmt;
5556
5557   if (is_gimple_val (exp))
5558     return exp;
5559
5560   t = make_rename_temp (type, NULL);
5561   new_stmt = build (MODIFY_EXPR, type, t, exp);
5562
5563   orig_stmt = bsi_stmt (*bsi);
5564   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5565   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5566
5567   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5568
5569   return t;
5570 }
5571
5572 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5573    Return the gimple_val holding the result.  */
5574
5575 tree
5576 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5577                  tree type, tree a, tree b, tree c)
5578 {
5579   tree ret;
5580
5581   ret = fold (build3 (code, type, a, b, c));
5582   STRIP_NOPS (ret);
5583
5584   return gimplify_val (bsi, type, ret);
5585 }
5586
5587 /* Build a binary operation and gimplify it.  Emit code before BSI.
5588    Return the gimple_val holding the result.  */
5589
5590 tree
5591 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5592                  tree type, tree a, tree b)
5593 {
5594   tree ret;
5595
5596   ret = fold (build2 (code, type, a, b));
5597   STRIP_NOPS (ret);
5598
5599   return gimplify_val (bsi, type, ret);
5600 }
5601
5602 /* Build a unary operation and gimplify it.  Emit code before BSI.
5603    Return the gimple_val holding the result.  */
5604
5605 tree
5606 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5607                  tree a)
5608 {
5609   tree ret;
5610
5611   ret = fold (build1 (code, type, a));
5612   STRIP_NOPS (ret);
5613
5614   return gimplify_val (bsi, type, ret);
5615 }
5616
5617
5618 \f
5619 /* Emit return warnings.  */
5620
5621 static void
5622 execute_warn_function_return (void)
5623 {
5624 #ifdef USE_MAPPED_LOCATION
5625   source_location location;
5626 #else
5627   location_t *locus;
5628 #endif
5629   tree last;
5630   edge e;
5631   edge_iterator ei;
5632
5633   /* If we have a path to EXIT, then we do return.  */
5634   if (TREE_THIS_VOLATILE (cfun->decl)
5635       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5636     {
5637 #ifdef USE_MAPPED_LOCATION
5638       location = UNKNOWN_LOCATION;
5639 #else
5640       locus = NULL;
5641 #endif
5642       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5643         {
5644           last = last_stmt (e->src);
5645           if (TREE_CODE (last) == RETURN_EXPR
5646 #ifdef USE_MAPPED_LOCATION
5647               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5648 #else
5649               && (locus = EXPR_LOCUS (last)) != NULL)
5650 #endif
5651             break;
5652         }
5653 #ifdef USE_MAPPED_LOCATION
5654       if (location == UNKNOWN_LOCATION)
5655         location = cfun->function_end_locus;
5656       warning (0, "%H%<noreturn%> function does return", &location);
5657 #else
5658       if (!locus)
5659         locus = &cfun->function_end_locus;
5660       warning (0, "%H%<noreturn%> function does return", locus);
5661 #endif
5662     }
5663
5664   /* If we see "return;" in some basic block, then we do reach the end
5665      without returning a value.  */
5666   else if (warn_return_type
5667            && !TREE_NO_WARNING (cfun->decl)
5668            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5669            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5670     {
5671       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5672         {
5673           tree last = last_stmt (e->src);
5674           if (TREE_CODE (last) == RETURN_EXPR
5675               && TREE_OPERAND (last, 0) == NULL)
5676             {
5677 #ifdef USE_MAPPED_LOCATION
5678               location = EXPR_LOCATION (last);
5679               if (location == UNKNOWN_LOCATION)
5680                   location = cfun->function_end_locus;
5681               warning (0, "%Hcontrol reaches end of non-void function", &location);
5682 #else
5683               locus = EXPR_LOCUS (last);
5684               if (!locus)
5685                 locus = &cfun->function_end_locus;
5686               warning (0, "%Hcontrol reaches end of non-void function", locus);
5687 #endif
5688               TREE_NO_WARNING (cfun->decl) = 1;
5689               break;
5690             }
5691         }
5692     }
5693 }
5694
5695
5696 /* Given a basic block B which ends with a conditional and has
5697    precisely two successors, determine which of the edges is taken if
5698    the conditional is true and which is taken if the conditional is
5699    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5700
5701 void
5702 extract_true_false_edges_from_block (basic_block b,
5703                                      edge *true_edge,
5704                                      edge *false_edge)
5705 {
5706   edge e = EDGE_SUCC (b, 0);
5707
5708   if (e->flags & EDGE_TRUE_VALUE)
5709     {
5710       *true_edge = e;
5711       *false_edge = EDGE_SUCC (b, 1);
5712     }
5713   else
5714     {
5715       *false_edge = e;
5716       *true_edge = EDGE_SUCC (b, 1);
5717     }
5718 }
5719
5720 struct tree_opt_pass pass_warn_function_return =
5721 {
5722   NULL,                                 /* name */
5723   NULL,                                 /* gate */
5724   execute_warn_function_return,         /* execute */
5725   NULL,                                 /* sub */
5726   NULL,                                 /* next */
5727   0,                                    /* static_pass_number */
5728   0,                                    /* tv_id */
5729   PROP_cfg,                             /* properties_required */
5730   0,                                    /* properties_provided */
5731   0,                                    /* properties_destroyed */
5732   0,                                    /* todo_flags_start */
5733   0,                                    /* todo_flags_finish */
5734   0                                     /* letter */
5735 };
5736
5737 /* Emit noreturn warnings.  */
5738
5739 static void
5740 execute_warn_function_noreturn (void)
5741 {
5742   if (warn_missing_noreturn
5743       && !TREE_THIS_VOLATILE (cfun->decl)
5744       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5745       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5746     warning (0, "%Jfunction might be possible candidate for "
5747              "attribute %<noreturn%>",
5748              cfun->decl);
5749 }
5750
5751 struct tree_opt_pass pass_warn_function_noreturn =
5752 {
5753   NULL,                                 /* name */
5754   NULL,                                 /* gate */
5755   execute_warn_function_noreturn,       /* execute */
5756   NULL,                                 /* sub */
5757   NULL,                                 /* next */
5758   0,                                    /* static_pass_number */
5759   0,                                    /* tv_id */
5760   PROP_cfg,                             /* properties_required */
5761   0,                                    /* properties_provided */
5762   0,                                    /* properties_destroyed */
5763   0,                                    /* todo_flags_start */
5764   0,                                    /* todo_flags_finish */
5765   0                                     /* letter */
5766 };