OSDN Git Service

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