OSDN Git Service

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