OSDN Git Service

875dd8ead94c0500b57e32ecfa1950bee239c77a
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfg.c
1 /* Control flow functions for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3    Free Software Foundation, Inc.
4    Contributed by Diego Novillo <dnovillo@redhat.com>
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
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 "flags.h"
33 #include "function.h"
34 #include "expr.h"
35 #include "ggc.h"
36 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-flow.h"
39 #include "timevar.h"
40 #include "tree-dump.h"
41 #include "tree-pass.h"
42 #include "toplev.h"
43 #include "except.h"
44 #include "cfgloop.h"
45 #include "cfglayout.h"
46 #include "tree-ssa-propagate.h"
47 #include "value-prof.h"
48 #include "pointer-set.h"
49 #include "tree-inline.h"
50
51 /* This file contains functions for building the Control Flow Graph (CFG)
52    for a function tree.  */
53
54 /* Local declarations.  */
55
56 /* Initial capacity for the basic block array.  */
57 static const int initial_cfg_capacity = 20;
58
59 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
60    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
61    via their TREE_CHAIN field, which we clear after we're done with the
62    hash table to prevent problems with duplication of GIMPLE_SWITCHes.
63
64    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
65    update the case vector in response to edge redirections.
66
67    Right now this table is set up and torn down at key points in the
68    compilation process.  It would be nice if we could make the table
69    more persistent.  The key is getting notification of changes to
70    the CFG (particularly edge removal, creation and redirection).  */
71
72 static struct pointer_map_t *edge_to_cases;
73
74 /* CFG statistics.  */
75 struct cfg_stats_d
76 {
77   long num_merged_labels;
78 };
79
80 static struct cfg_stats_d cfg_stats;
81
82 /* Nonzero if we found a computed goto while building basic blocks.  */
83 static bool found_computed_goto;
84
85 /* Basic blocks and flowgraphs.  */
86 static void make_blocks (gimple_seq);
87 static void factor_computed_gotos (void);
88
89 /* Edges.  */
90 static void make_edges (void);
91 static void make_cond_expr_edges (basic_block);
92 static void make_gimple_switch_edges (basic_block);
93 static void make_goto_expr_edges (basic_block);
94 static edge gimple_redirect_edge_and_branch (edge, basic_block);
95 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
96 static unsigned int split_critical_edges (void);
97
98 /* Various helpers.  */
99 static inline bool stmt_starts_bb_p (gimple, gimple);
100 static int gimple_verify_flow_info (void);
101 static void gimple_make_forwarder_block (edge);
102 static void gimple_cfg2vcg (FILE *);
103
104 /* Flowgraph optimization and cleanup.  */
105 static void gimple_merge_blocks (basic_block, basic_block);
106 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
107 static void remove_bb (basic_block);
108 static edge find_taken_edge_computed_goto (basic_block, tree);
109 static edge find_taken_edge_cond_expr (basic_block, tree);
110 static edge find_taken_edge_switch_expr (basic_block, tree);
111 static tree find_case_label_for_value (gimple, tree);
112
113 void
114 init_empty_tree_cfg_for_function (struct function *fn)
115 {
116   /* Initialize the basic block array.  */
117   init_flow (fn);
118   profile_status_for_function (fn) = PROFILE_ABSENT;
119   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
120   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
121   basic_block_info_for_function (fn)
122     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
123   VEC_safe_grow_cleared (basic_block, gc,
124                          basic_block_info_for_function (fn),
125                          initial_cfg_capacity);
126
127   /* Build a mapping of labels to their associated blocks.  */
128   label_to_block_map_for_function (fn)
129     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
130   VEC_safe_grow_cleared (basic_block, gc,
131                          label_to_block_map_for_function (fn),
132                          initial_cfg_capacity);
133
134   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK, 
135                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
136   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK, 
137                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
138
139   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
140     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
141   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
142     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
143 }
144
145 void
146 init_empty_tree_cfg (void)
147 {
148   init_empty_tree_cfg_for_function (cfun);
149 }
150
151 /*---------------------------------------------------------------------------
152                               Create basic blocks
153 ---------------------------------------------------------------------------*/
154
155 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
156    statements to be added to the flowgraph.  */
157
158 static void
159 build_gimple_cfg (gimple_seq seq)
160 {
161   /* Register specific gimple functions.  */
162   gimple_register_cfg_hooks ();
163
164   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
165
166   init_empty_tree_cfg ();
167
168   found_computed_goto = 0;
169   make_blocks (seq);
170
171   /* Computed gotos are hell to deal with, especially if there are
172      lots of them with a large number of destinations.  So we factor
173      them to a common computed goto location before we build the
174      edge list.  After we convert back to normal form, we will un-factor
175      the computed gotos since factoring introduces an unwanted jump.  */
176   if (found_computed_goto)
177     factor_computed_gotos ();
178
179   /* Make sure there is always at least one block, even if it's empty.  */
180   if (n_basic_blocks == NUM_FIXED_BLOCKS)
181     create_empty_bb (ENTRY_BLOCK_PTR);
182
183   /* Adjust the size of the array.  */
184   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
185     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
186
187   /* To speed up statement iterator walks, we first purge dead labels.  */
188   cleanup_dead_labels ();
189
190   /* Group case nodes to reduce the number of edges.
191      We do this after cleaning up dead labels because otherwise we miss
192      a lot of obvious case merging opportunities.  */
193   group_case_labels ();
194
195   /* Create the edges of the flowgraph.  */
196   make_edges ();
197   cleanup_dead_labels ();
198
199   /* Debugging dumps.  */
200
201   /* Write the flowgraph to a VCG file.  */
202   {
203     int local_dump_flags;
204     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
205     if (vcg_file)
206       {
207         gimple_cfg2vcg (vcg_file);
208         dump_end (TDI_vcg, vcg_file);
209       }
210   }
211
212 #ifdef ENABLE_CHECKING
213   verify_stmts ();
214 #endif
215 }
216
217 static unsigned int
218 execute_build_cfg (void)
219 {
220   gimple_seq body = gimple_body (current_function_decl);
221
222   build_gimple_cfg (body);
223   gimple_set_body (current_function_decl, NULL);
224   if (dump_file && (dump_flags & TDF_DETAILS))
225     {
226       fprintf (dump_file, "Scope blocks:\n");
227       dump_scope_blocks (dump_file, dump_flags);
228     }
229   return 0;
230 }
231
232 struct gimple_opt_pass pass_build_cfg =
233 {
234  {
235   GIMPLE_PASS,
236   "cfg",                                /* name */
237   NULL,                                 /* gate */
238   execute_build_cfg,                    /* execute */
239   NULL,                                 /* sub */
240   NULL,                                 /* next */
241   0,                                    /* static_pass_number */
242   TV_TREE_CFG,                          /* tv_id */
243   PROP_gimple_leh,                      /* properties_required */
244   PROP_cfg,                             /* properties_provided */
245   0,                                    /* properties_destroyed */
246   0,                                    /* todo_flags_start */
247   TODO_verify_stmts | TODO_cleanup_cfg
248   | TODO_dump_func                      /* todo_flags_finish */
249  }
250 };
251
252
253 /* Return true if T is a computed goto.  */
254
255 static bool
256 computed_goto_p (gimple t)
257 {
258   return (gimple_code (t) == GIMPLE_GOTO
259           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
260 }
261
262
263 /* Search the CFG for any computed gotos.  If found, factor them to a
264    common computed goto site.  Also record the location of that site so
265    that we can un-factor the gotos after we have converted back to
266    normal form.  */
267
268 static void
269 factor_computed_gotos (void)
270 {
271   basic_block bb;
272   tree factored_label_decl = NULL;
273   tree var = NULL;
274   gimple factored_computed_goto_label = NULL;
275   gimple factored_computed_goto = NULL;
276
277   /* We know there are one or more computed gotos in this function.
278      Examine the last statement in each basic block to see if the block
279      ends with a computed goto.  */
280
281   FOR_EACH_BB (bb)
282     {
283       gimple_stmt_iterator gsi = gsi_last_bb (bb);
284       gimple last;
285
286       if (gsi_end_p (gsi))
287         continue;
288
289       last = gsi_stmt (gsi);
290
291       /* Ignore the computed goto we create when we factor the original
292          computed gotos.  */
293       if (last == factored_computed_goto)
294         continue;
295
296       /* If the last statement is a computed goto, factor it.  */
297       if (computed_goto_p (last))
298         {
299           gimple assignment;
300
301           /* The first time we find a computed goto we need to create
302              the factored goto block and the variable each original
303              computed goto will use for their goto destination.  */
304           if (!factored_computed_goto)
305             {
306               basic_block new_bb = create_empty_bb (bb);
307               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
308
309               /* Create the destination of the factored goto.  Each original
310                  computed goto will put its desired destination into this
311                  variable and jump to the label we create immediately
312                  below.  */
313               var = create_tmp_var (ptr_type_node, "gotovar");
314
315               /* Build a label for the new block which will contain the
316                  factored computed goto.  */
317               factored_label_decl = create_artificial_label ();
318               factored_computed_goto_label
319                 = gimple_build_label (factored_label_decl);
320               gsi_insert_after (&new_gsi, factored_computed_goto_label,
321                                 GSI_NEW_STMT);
322
323               /* Build our new computed goto.  */
324               factored_computed_goto = gimple_build_goto (var);
325               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
326             }
327
328           /* Copy the original computed goto's destination into VAR.  */
329           assignment = gimple_build_assign (var, gimple_goto_dest (last));
330           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
331
332           /* And re-vector the computed goto to the new destination.  */
333           gimple_goto_set_dest (last, factored_label_decl);
334         }
335     }
336 }
337
338
339 /* Build a flowgraph for the sequence of stmts SEQ.  */
340
341 static void
342 make_blocks (gimple_seq seq)
343 {
344   gimple_stmt_iterator i = gsi_start (seq);
345   gimple stmt = NULL;
346   bool start_new_block = true;
347   bool first_stmt_of_seq = true;
348   basic_block bb = ENTRY_BLOCK_PTR;
349
350   while (!gsi_end_p (i))
351     {
352       gimple prev_stmt;
353
354       prev_stmt = stmt;
355       stmt = gsi_stmt (i);
356
357       /* If the statement starts a new basic block or if we have determined
358          in a previous pass that we need to create a new block for STMT, do
359          so now.  */
360       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
361         {
362           if (!first_stmt_of_seq)
363             seq = gsi_split_seq_before (&i);
364           bb = create_basic_block (seq, NULL, bb);
365           start_new_block = false;
366         }
367
368       /* Now add STMT to BB and create the subgraphs for special statement
369          codes.  */
370       gimple_set_bb (stmt, bb);
371
372       if (computed_goto_p (stmt))
373         found_computed_goto = true;
374
375       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
376          next iteration.  */
377       if (stmt_ends_bb_p (stmt))
378         {
379           /* If the stmt can make abnormal goto use a new temporary
380              for the assignment to the LHS.  This makes sure the old value
381              of the LHS is available on the abnormal edge.  Otherwise
382              we will end up with overlapping life-ranges for abnormal
383              SSA names.  */
384           if (gimple_has_lhs (stmt)
385               && stmt_can_make_abnormal_goto (stmt)
386               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
387             {
388               tree lhs = gimple_get_lhs (stmt);
389               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
390               gimple s = gimple_build_assign (lhs, tmp);
391               gimple_set_location (s, gimple_location (stmt));
392               gimple_set_block (s, gimple_block (stmt));
393               gimple_set_lhs (stmt, tmp);
394               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
395                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
396                 DECL_GIMPLE_REG_P (tmp) = 1;
397               gsi_insert_after (&i, s, GSI_SAME_STMT);
398             }
399           start_new_block = true;
400         }
401
402       gsi_next (&i);
403       first_stmt_of_seq = false;
404     }
405 }
406
407
408 /* Create and return a new empty basic block after bb AFTER.  */
409
410 static basic_block
411 create_bb (void *h, void *e, basic_block after)
412 {
413   basic_block bb;
414
415   gcc_assert (!e);
416
417   /* Create and initialize a new basic block.  Since alloc_block uses
418      ggc_alloc_cleared to allocate a basic block, we do not have to
419      clear the newly allocated basic block here.  */
420   bb = alloc_block ();
421
422   bb->index = last_basic_block;
423   bb->flags = BB_NEW;
424   bb->il.gimple = GGC_CNEW (struct gimple_bb_info);
425   set_bb_seq (bb, h ? (gimple_seq) h : gimple_seq_alloc ());
426
427   /* Add the new block to the linked list of blocks.  */
428   link_block (bb, after);
429
430   /* Grow the basic block array if needed.  */
431   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
432     {
433       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
434       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
435     }
436
437   /* Add the newly created block to the array.  */
438   SET_BASIC_BLOCK (last_basic_block, bb);
439
440   n_basic_blocks++;
441   last_basic_block++;
442
443   return bb;
444 }
445
446
447 /*---------------------------------------------------------------------------
448                                  Edge creation
449 ---------------------------------------------------------------------------*/
450
451 /* Fold COND_EXPR_COND of each COND_EXPR.  */
452
453 void
454 fold_cond_expr_cond (void)
455 {
456   basic_block bb;
457
458   FOR_EACH_BB (bb)
459     {
460       gimple stmt = last_stmt (bb);
461
462       if (stmt && gimple_code (stmt) == GIMPLE_COND)
463         {
464           tree cond;
465           bool zerop, onep;
466
467           fold_defer_overflow_warnings ();
468           cond = fold_binary (gimple_cond_code (stmt), boolean_type_node,
469                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
470           if (cond)
471             {
472               zerop = integer_zerop (cond);
473               onep = integer_onep (cond);
474             }
475           else
476             zerop = onep = false;
477
478           fold_undefer_overflow_warnings (zerop || onep,
479                                           stmt,
480                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
481           if (zerop)
482             gimple_cond_make_false (stmt);
483           else if (onep)
484             gimple_cond_make_true (stmt);
485         }
486     }
487 }
488
489 /* Join all the blocks in the flowgraph.  */
490
491 static void
492 make_edges (void)
493 {
494   basic_block bb;
495   struct omp_region *cur_region = NULL;
496
497   /* Create an edge from entry to the first block with executable
498      statements in it.  */
499   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
500
501   /* Traverse the basic block array placing edges.  */
502   FOR_EACH_BB (bb)
503     {
504       gimple last = last_stmt (bb);
505       bool fallthru;
506
507       if (last)
508         {
509           enum gimple_code code = gimple_code (last);
510           switch (code)
511             {
512             case GIMPLE_GOTO:
513               make_goto_expr_edges (bb);
514               fallthru = false;
515               break;
516             case GIMPLE_RETURN:
517               make_edge (bb, EXIT_BLOCK_PTR, 0);
518               fallthru = false;
519               break;
520             case GIMPLE_COND:
521               make_cond_expr_edges (bb);
522               fallthru = false;
523               break;
524             case GIMPLE_SWITCH:
525               make_gimple_switch_edges (bb);
526               fallthru = false;
527               break;
528             case GIMPLE_RESX:
529               make_eh_edges (last);
530               fallthru = false;
531               break;
532
533             case GIMPLE_CALL:
534               /* If this function receives a nonlocal goto, then we need to
535                  make edges from this call site to all the nonlocal goto
536                  handlers.  */
537               if (stmt_can_make_abnormal_goto (last))
538                 make_abnormal_goto_edges (bb, true);
539
540               /* If this statement has reachable exception handlers, then
541                  create abnormal edges to them.  */
542               make_eh_edges (last);
543
544               /* Some calls are known not to return.  */
545               fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
546               break;
547
548             case GIMPLE_ASSIGN:
549                /* A GIMPLE_ASSIGN may throw internally and thus be considered
550                   control-altering. */
551               if (is_ctrl_altering_stmt (last))
552                 {
553                   make_eh_edges (last);
554                 }
555               fallthru = true;
556               break;
557
558             case GIMPLE_OMP_PARALLEL:
559             case GIMPLE_OMP_TASK:
560             case GIMPLE_OMP_FOR:
561             case GIMPLE_OMP_SINGLE:
562             case GIMPLE_OMP_MASTER:
563             case GIMPLE_OMP_ORDERED:
564             case GIMPLE_OMP_CRITICAL:
565             case GIMPLE_OMP_SECTION:
566               cur_region = new_omp_region (bb, code, cur_region);
567               fallthru = true;
568               break;
569
570             case GIMPLE_OMP_SECTIONS:
571               cur_region = new_omp_region (bb, code, cur_region);
572               fallthru = true;
573               break;
574
575             case GIMPLE_OMP_SECTIONS_SWITCH:
576               fallthru = false;
577               break;
578
579
580             case GIMPLE_OMP_ATOMIC_LOAD:
581             case GIMPLE_OMP_ATOMIC_STORE:
582                fallthru = true;
583                break;
584
585
586             case GIMPLE_OMP_RETURN:
587               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
588                  somewhere other than the next block.  This will be
589                  created later.  */
590               cur_region->exit = bb;
591               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
592               cur_region = cur_region->outer;
593               break;
594
595             case GIMPLE_OMP_CONTINUE:
596               cur_region->cont = bb;
597               switch (cur_region->type)
598                 {
599                 case GIMPLE_OMP_FOR:
600                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
601                      succs edges as abnormal to prevent splitting
602                      them.  */
603                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
604                   /* Make the loopback edge.  */
605                   make_edge (bb, single_succ (cur_region->entry),
606                              EDGE_ABNORMAL);
607
608                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
609                      corresponds to the case that the body of the loop
610                      is not executed at all.  */
611                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
612                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
613                   fallthru = false;
614                   break;
615
616                 case GIMPLE_OMP_SECTIONS:
617                   /* Wire up the edges into and out of the nested sections.  */
618                   {
619                     basic_block switch_bb = single_succ (cur_region->entry);
620
621                     struct omp_region *i;
622                     for (i = cur_region->inner; i ; i = i->next)
623                       {
624                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
625                         make_edge (switch_bb, i->entry, 0);
626                         make_edge (i->exit, bb, EDGE_FALLTHRU);
627                       }
628
629                     /* Make the loopback edge to the block with
630                        GIMPLE_OMP_SECTIONS_SWITCH.  */
631                     make_edge (bb, switch_bb, 0);
632
633                     /* Make the edge from the switch to exit.  */
634                     make_edge (switch_bb, bb->next_bb, 0);
635                     fallthru = false;
636                   }
637                   break;
638
639                 default:
640                   gcc_unreachable ();
641                 }
642               break;
643
644             default:
645               gcc_assert (!stmt_ends_bb_p (last));
646               fallthru = true;
647             }
648         }
649       else
650         fallthru = true;
651
652       if (fallthru)
653         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
654     }
655
656   if (root_omp_region)
657     free_omp_regions ();
658
659   /* Fold COND_EXPR_COND of each COND_EXPR.  */
660   fold_cond_expr_cond ();
661 }
662
663
664 /* Create the edges for a GIMPLE_COND starting at block BB.  */
665
666 static void
667 make_cond_expr_edges (basic_block bb)
668 {
669   gimple entry = last_stmt (bb);
670   gimple then_stmt, else_stmt;
671   basic_block then_bb, else_bb;
672   tree then_label, else_label;
673   edge e;
674
675   gcc_assert (entry);
676   gcc_assert (gimple_code (entry) == GIMPLE_COND);
677
678   /* Entry basic blocks for each component.  */
679   then_label = gimple_cond_true_label (entry);
680   else_label = gimple_cond_false_label (entry);
681   then_bb = label_to_block (then_label);
682   else_bb = label_to_block (else_label);
683   then_stmt = first_stmt (then_bb);
684   else_stmt = first_stmt (else_bb);
685
686   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
687   e->goto_locus = gimple_location (then_stmt);
688   if (e->goto_locus)
689     e->goto_block = gimple_block (then_stmt);
690   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
691   if (e)
692     {
693       e->goto_locus = gimple_location (else_stmt);
694       if (e->goto_locus)
695         e->goto_block = gimple_block (else_stmt);
696     }
697
698   /* We do not need the labels anymore.  */
699   gimple_cond_set_true_label (entry, NULL_TREE);
700   gimple_cond_set_false_label (entry, NULL_TREE);
701 }
702
703
704 /* Called for each element in the hash table (P) as we delete the
705    edge to cases hash table.
706
707    Clear all the TREE_CHAINs to prevent problems with copying of
708    SWITCH_EXPRs and structure sharing rules, then free the hash table
709    element.  */
710
711 static bool
712 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
713                        void *data ATTRIBUTE_UNUSED)
714 {
715   tree t, next;
716
717   for (t = (tree) *value; t; t = next)
718     {
719       next = TREE_CHAIN (t);
720       TREE_CHAIN (t) = NULL;
721     }
722
723   *value = NULL;
724   return false;
725 }
726
727 /* Start recording information mapping edges to case labels.  */
728
729 void
730 start_recording_case_labels (void)
731 {
732   gcc_assert (edge_to_cases == NULL);
733   edge_to_cases = pointer_map_create ();
734 }
735
736 /* Return nonzero if we are recording information for case labels.  */
737
738 static bool
739 recording_case_labels_p (void)
740 {
741   return (edge_to_cases != NULL);
742 }
743
744 /* Stop recording information mapping edges to case labels and
745    remove any information we have recorded.  */
746 void
747 end_recording_case_labels (void)
748 {
749   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
750   pointer_map_destroy (edge_to_cases);
751   edge_to_cases = NULL;
752 }
753
754 /* If we are inside a {start,end}_recording_cases block, then return
755    a chain of CASE_LABEL_EXPRs from T which reference E.
756
757    Otherwise return NULL.  */
758
759 static tree
760 get_cases_for_edge (edge e, gimple t)
761 {
762   void **slot;
763   size_t i, n;
764
765   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
766      chains available.  Return NULL so the caller can detect this case.  */
767   if (!recording_case_labels_p ())
768     return NULL;
769
770   slot = pointer_map_contains (edge_to_cases, e);
771   if (slot)
772     return (tree) *slot;
773
774   /* If we did not find E in the hash table, then this must be the first
775      time we have been queried for information about E & T.  Add all the
776      elements from T to the hash table then perform the query again.  */
777
778   n = gimple_switch_num_labels (t);
779   for (i = 0; i < n; i++)
780     {
781       tree elt = gimple_switch_label (t, i);
782       tree lab = CASE_LABEL (elt);
783       basic_block label_bb = label_to_block (lab);
784       edge this_edge = find_edge (e->src, label_bb);
785
786       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
787          a new chain.  */
788       slot = pointer_map_insert (edge_to_cases, this_edge);
789       TREE_CHAIN (elt) = (tree) *slot;
790       *slot = elt;
791     }
792
793   return (tree) *pointer_map_contains (edge_to_cases, e);
794 }
795
796 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
797
798 static void
799 make_gimple_switch_edges (basic_block bb)
800 {
801   gimple entry = last_stmt (bb);
802   size_t i, n;
803
804   n = gimple_switch_num_labels (entry);
805
806   for (i = 0; i < n; ++i)
807     {
808       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
809       basic_block label_bb = label_to_block (lab);
810       make_edge (bb, label_bb, 0);
811     }
812 }
813
814
815 /* Return the basic block holding label DEST.  */
816
817 basic_block
818 label_to_block_fn (struct function *ifun, tree dest)
819 {
820   int uid = LABEL_DECL_UID (dest);
821
822   /* We would die hard when faced by an undefined label.  Emit a label to
823      the very first basic block.  This will hopefully make even the dataflow
824      and undefined variable warnings quite right.  */
825   if ((errorcount || sorrycount) && uid < 0)
826     {
827       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
828       gimple stmt;
829
830       stmt = gimple_build_label (dest);
831       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
832       uid = LABEL_DECL_UID (dest);
833     }
834   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
835       <= (unsigned int) uid)
836     return NULL;
837   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
838 }
839
840 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
841    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
842
843 void
844 make_abnormal_goto_edges (basic_block bb, bool for_call)
845 {
846   basic_block target_bb;
847   gimple_stmt_iterator gsi;
848
849   FOR_EACH_BB (target_bb)
850     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
851       {
852         gimple label_stmt = gsi_stmt (gsi);
853         tree target;
854
855         if (gimple_code (label_stmt) != GIMPLE_LABEL)
856           break;
857
858         target = gimple_label_label (label_stmt);
859
860         /* Make an edge to every label block that has been marked as a
861            potential target for a computed goto or a non-local goto.  */
862         if ((FORCED_LABEL (target) && !for_call)
863             || (DECL_NONLOCAL (target) && for_call))
864           {
865             make_edge (bb, target_bb, EDGE_ABNORMAL);
866             break;
867           }
868       }
869 }
870
871 /* Create edges for a goto statement at block BB.  */
872
873 static void
874 make_goto_expr_edges (basic_block bb)
875 {
876   gimple_stmt_iterator last = gsi_last_bb (bb);
877   gimple goto_t = gsi_stmt (last);
878
879   /* A simple GOTO creates normal edges.  */
880   if (simple_goto_p (goto_t))
881     {
882       tree dest = gimple_goto_dest (goto_t);
883       edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
884       e->goto_locus = gimple_location (goto_t);
885       if (e->goto_locus)
886         e->goto_block = gimple_block (goto_t);
887       gsi_remove (&last, true);
888       return;
889     }
890
891   /* A computed GOTO creates abnormal edges.  */
892   make_abnormal_goto_edges (bb, false);
893 }
894
895
896 /*---------------------------------------------------------------------------
897                                Flowgraph analysis
898 ---------------------------------------------------------------------------*/
899
900 /* Cleanup useless labels in basic blocks.  This is something we wish
901    to do early because it allows us to group case labels before creating
902    the edges for the CFG, and it speeds up block statement iterators in
903    all passes later on.
904    We rerun this pass after CFG is created, to get rid of the labels that
905    are no longer referenced.  After then we do not run it any more, since
906    (almost) no new labels should be created.  */
907
908 /* A map from basic block index to the leading label of that block.  */
909 static struct label_record
910 {
911   /* The label.  */
912   tree label;
913
914   /* True if the label is referenced from somewhere.  */
915   bool used;
916 } *label_for_bb;
917
918 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
919 static void
920 update_eh_label (struct eh_region_d *region)
921 {
922   tree old_label = get_eh_region_tree_label (region);
923   if (old_label)
924     {
925       tree new_label;
926       basic_block bb = label_to_block (old_label);
927
928       /* ??? After optimizing, there may be EH regions with labels
929          that have already been removed from the function body, so
930          there is no basic block for them.  */
931       if (! bb)
932         return;
933
934       new_label = label_for_bb[bb->index].label;
935       label_for_bb[bb->index].used = true;
936       set_eh_region_tree_label (region, new_label);
937     }
938 }
939
940
941 /* Given LABEL return the first label in the same basic block.  */
942
943 static tree
944 main_block_label (tree label)
945 {
946   basic_block bb = label_to_block (label);
947   tree main_label = label_for_bb[bb->index].label;
948
949   /* label_to_block possibly inserted undefined label into the chain.  */
950   if (!main_label)
951     {
952       label_for_bb[bb->index].label = label;
953       main_label = label;
954     }
955
956   label_for_bb[bb->index].used = true;
957   return main_label;
958 }
959
960 /* Cleanup redundant labels.  This is a three-step process:
961      1) Find the leading label for each block.
962      2) Redirect all references to labels to the leading labels.
963      3) Cleanup all useless labels.  */
964
965 void
966 cleanup_dead_labels (void)
967 {
968   basic_block bb;
969   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
970
971   /* Find a suitable label for each block.  We use the first user-defined
972      label if there is one, or otherwise just the first label we see.  */
973   FOR_EACH_BB (bb)
974     {
975       gimple_stmt_iterator i;
976
977       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
978         {
979           tree label;
980           gimple stmt = gsi_stmt (i);
981
982           if (gimple_code (stmt) != GIMPLE_LABEL)
983             break;
984
985           label = gimple_label_label (stmt);
986
987           /* If we have not yet seen a label for the current block,
988              remember this one and see if there are more labels.  */
989           if (!label_for_bb[bb->index].label)
990             {
991               label_for_bb[bb->index].label = label;
992               continue;
993             }
994
995           /* If we did see a label for the current block already, but it
996              is an artificially created label, replace it if the current
997              label is a user defined label.  */
998           if (!DECL_ARTIFICIAL (label)
999               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1000             {
1001               label_for_bb[bb->index].label = label;
1002               break;
1003             }
1004         }
1005     }
1006
1007   /* Now redirect all jumps/branches to the selected label.
1008      First do so for each block ending in a control statement.  */
1009   FOR_EACH_BB (bb)
1010     {
1011       gimple stmt = last_stmt (bb);
1012       if (!stmt)
1013         continue;
1014
1015       switch (gimple_code (stmt))
1016         {
1017         case GIMPLE_COND:
1018           {
1019             tree true_label = gimple_cond_true_label (stmt);
1020             tree false_label = gimple_cond_false_label (stmt);
1021
1022             if (true_label)
1023               gimple_cond_set_true_label (stmt, main_block_label (true_label));
1024             if (false_label)
1025               gimple_cond_set_false_label (stmt, main_block_label (false_label));
1026             break;
1027           }
1028
1029         case GIMPLE_SWITCH:
1030           {
1031             size_t i, n = gimple_switch_num_labels (stmt);
1032
1033             /* Replace all destination labels.  */
1034             for (i = 0; i < n; ++i)
1035               {
1036                 tree case_label = gimple_switch_label (stmt, i);
1037                 tree label = main_block_label (CASE_LABEL (case_label));
1038                 CASE_LABEL (case_label) = label;
1039               }
1040             break;
1041           }
1042
1043         /* We have to handle gotos until they're removed, and we don't
1044            remove them until after we've created the CFG edges.  */
1045         case GIMPLE_GOTO:
1046           if (!computed_goto_p (stmt))
1047             {
1048               tree new_dest = main_block_label (gimple_goto_dest (stmt));
1049               gimple_goto_set_dest (stmt, new_dest);
1050               break;
1051             }
1052
1053         default:
1054           break;
1055       }
1056     }
1057
1058   for_each_eh_region (update_eh_label);
1059
1060   /* Finally, purge dead labels.  All user-defined labels and labels that
1061      can be the target of non-local gotos and labels which have their
1062      address taken are preserved.  */
1063   FOR_EACH_BB (bb)
1064     {
1065       gimple_stmt_iterator i;
1066       tree label_for_this_bb = label_for_bb[bb->index].label;
1067
1068       if (!label_for_this_bb)
1069         continue;
1070
1071       /* If the main label of the block is unused, we may still remove it.  */
1072       if (!label_for_bb[bb->index].used)
1073         label_for_this_bb = NULL;
1074
1075       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1076         {
1077           tree label;
1078           gimple stmt = gsi_stmt (i);
1079
1080           if (gimple_code (stmt) != GIMPLE_LABEL)
1081             break;
1082
1083           label = gimple_label_label (stmt);
1084
1085           if (label == label_for_this_bb
1086               || !DECL_ARTIFICIAL (label)
1087               || DECL_NONLOCAL (label)
1088               || FORCED_LABEL (label))
1089             gsi_next (&i);
1090           else
1091             gsi_remove (&i, true);
1092         }
1093     }
1094
1095   free (label_for_bb);
1096 }
1097
1098 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1099    and scan the sorted vector of cases.  Combine the ones jumping to the
1100    same label.
1101    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1102
1103 void
1104 group_case_labels (void)
1105 {
1106   basic_block bb;
1107
1108   FOR_EACH_BB (bb)
1109     {
1110       gimple stmt = last_stmt (bb);
1111       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1112         {
1113           int old_size = gimple_switch_num_labels (stmt);
1114           int i, j, new_size = old_size;
1115           tree default_case = NULL_TREE;
1116           tree default_label = NULL_TREE;
1117           bool has_default;
1118
1119           /* The default label is always the first case in a switch
1120              statement after gimplification if it was not optimized
1121              away */
1122           if (!CASE_LOW (gimple_switch_default_label (stmt))
1123               && !CASE_HIGH (gimple_switch_default_label (stmt)))
1124             {
1125               default_case = gimple_switch_default_label (stmt);
1126               default_label = CASE_LABEL (default_case);
1127               has_default = true;
1128             }
1129           else
1130             has_default = false;
1131
1132           /* Look for possible opportunities to merge cases.  */
1133           if (has_default)
1134             i = 1;
1135           else
1136             i = 0;
1137           while (i < old_size)
1138             {
1139               tree base_case, base_label, base_high;
1140               base_case = gimple_switch_label (stmt, i);
1141
1142               gcc_assert (base_case);
1143               base_label = CASE_LABEL (base_case);
1144
1145               /* Discard cases that have the same destination as the
1146                  default case.  */
1147               if (base_label == default_label)
1148                 {
1149                   gimple_switch_set_label (stmt, i, NULL_TREE);
1150                   i++;
1151                   new_size--;
1152                   continue;
1153                 }
1154
1155               base_high = CASE_HIGH (base_case)
1156                           ? CASE_HIGH (base_case)
1157                           : CASE_LOW (base_case);
1158               i++;
1159
1160               /* Try to merge case labels.  Break out when we reach the end
1161                  of the label vector or when we cannot merge the next case
1162                  label with the current one.  */
1163               while (i < old_size)
1164                 {
1165                   tree merge_case = gimple_switch_label (stmt, i);
1166                   tree merge_label = CASE_LABEL (merge_case);
1167                   tree t = int_const_binop (PLUS_EXPR, base_high,
1168                                             integer_one_node, 1);
1169
1170                   /* Merge the cases if they jump to the same place,
1171                      and their ranges are consecutive.  */
1172                   if (merge_label == base_label
1173                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1174                     {
1175                       base_high = CASE_HIGH (merge_case) ?
1176                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1177                       CASE_HIGH (base_case) = base_high;
1178                       gimple_switch_set_label (stmt, i, NULL_TREE);
1179                       new_size--;
1180                       i++;
1181                     }
1182                   else
1183                     break;
1184                 }
1185             }
1186
1187           /* Compress the case labels in the label vector, and adjust the
1188              length of the vector.  */
1189           for (i = 0, j = 0; i < new_size; i++)
1190             {
1191               while (! gimple_switch_label (stmt, j))
1192                 j++;
1193               gimple_switch_set_label (stmt, i,
1194                                        gimple_switch_label (stmt, j++));
1195             }
1196
1197           gcc_assert (new_size <= old_size);
1198           gimple_switch_set_num_labels (stmt, new_size);
1199         }
1200     }
1201 }
1202
1203 /* Checks whether we can merge block B into block A.  */
1204
1205 static bool
1206 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1207 {
1208   gimple stmt;
1209   gimple_stmt_iterator gsi;
1210   gimple_seq phis;
1211
1212   if (!single_succ_p (a))
1213     return false;
1214
1215   if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH))
1216     return false;
1217
1218   if (single_succ (a) != b)
1219     return false;
1220
1221   if (!single_pred_p (b))
1222     return false;
1223
1224   if (b == EXIT_BLOCK_PTR)
1225     return false;
1226
1227   /* If A ends by a statement causing exceptions or something similar, we
1228      cannot merge the blocks.  */
1229   stmt = last_stmt (a);
1230   if (stmt && stmt_ends_bb_p (stmt))
1231     return false;
1232
1233   /* Do not allow a block with only a non-local label to be merged.  */
1234   if (stmt
1235       && gimple_code (stmt) == GIMPLE_LABEL
1236       && DECL_NONLOCAL (gimple_label_label (stmt)))
1237     return false;
1238
1239   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1240      is not up-to-date, we cannot eliminate any phis; however, if only
1241      some symbols as whole are marked for renaming, this is not a problem,
1242      as phi nodes for those symbols are irrelevant in updating anyway.  */
1243   phis = phi_nodes (b);
1244   if (!gimple_seq_empty_p (phis))
1245     {
1246       gimple_stmt_iterator i;
1247
1248       if (name_mappings_registered_p ())
1249         return false;
1250
1251       for (i = gsi_start (phis); !gsi_end_p (i); gsi_next (&i))
1252         {
1253           gimple phi = gsi_stmt (i);
1254
1255           if (!is_gimple_reg (gimple_phi_result (phi))
1256               && !may_propagate_copy (gimple_phi_result (phi),
1257                                       gimple_phi_arg_def (phi, 0)))
1258             return false;
1259         }
1260     }
1261
1262   /* Do not remove user labels.  */
1263   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1264     {
1265       stmt = gsi_stmt (gsi);
1266       if (gimple_code (stmt) != GIMPLE_LABEL)
1267         break;
1268       if (!DECL_ARTIFICIAL (gimple_label_label (stmt)))
1269         return false;
1270     }
1271
1272   /* Protect the loop latches.  */
1273   if (current_loops
1274       && b->loop_father->latch == b)
1275     return false;
1276
1277   return true;
1278 }
1279
1280 /* Replaces all uses of NAME by VAL.  */
1281
1282 void
1283 replace_uses_by (tree name, tree val)
1284 {
1285   imm_use_iterator imm_iter;
1286   use_operand_p use;
1287   gimple stmt;
1288   edge e;
1289
1290   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1291     {
1292       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1293         {
1294           replace_exp (use, val);
1295
1296           if (gimple_code (stmt) == GIMPLE_PHI)
1297             {
1298               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1299               if (e->flags & EDGE_ABNORMAL)
1300                 {
1301                   /* This can only occur for virtual operands, since
1302                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1303                      would prevent replacement.  */
1304                   gcc_assert (!is_gimple_reg (name));
1305                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1306                 }
1307             }
1308         }
1309
1310       if (gimple_code (stmt) != GIMPLE_PHI)
1311         {
1312           size_t i;
1313
1314           fold_stmt_inplace (stmt);
1315           if (cfgcleanup_altered_bbs)
1316             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1317
1318           /* FIXME.  This should go in update_stmt.  */
1319           for (i = 0; i < gimple_num_ops (stmt); i++)
1320             {
1321               tree op = gimple_op (stmt, i);
1322               /* Operands may be empty here.  For example, the labels
1323                  of a GIMPLE_COND are nulled out following the creation
1324                  of the corresponding CFG edges.  */
1325               if (op && TREE_CODE (op) == ADDR_EXPR)
1326                 recompute_tree_invariant_for_addr_expr (op);
1327             }
1328
1329           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1330           update_stmt (stmt);
1331         }
1332     }
1333
1334   gcc_assert (has_zero_uses (name));
1335
1336   /* Also update the trees stored in loop structures.  */
1337   if (current_loops)
1338     {
1339       struct loop *loop;
1340       loop_iterator li;
1341
1342       FOR_EACH_LOOP (li, loop, 0)
1343         {
1344           substitute_in_loop_info (loop, name, val);
1345         }
1346     }
1347 }
1348
1349 /* Merge block B into block A.  */
1350
1351 static void
1352 gimple_merge_blocks (basic_block a, basic_block b)
1353 {
1354   gimple_stmt_iterator last, gsi, psi;
1355   gimple_seq phis = phi_nodes (b);
1356
1357   if (dump_file)
1358     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1359
1360   /* Remove all single-valued PHI nodes from block B of the form
1361      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1362   gsi = gsi_last_bb (a);
1363   for (psi = gsi_start (phis); !gsi_end_p (psi); )
1364     {
1365       gimple phi = gsi_stmt (psi);
1366       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1367       gimple copy;
1368       bool may_replace_uses = !is_gimple_reg (def)
1369                               || may_propagate_copy (def, use);
1370
1371       /* In case we maintain loop closed ssa form, do not propagate arguments
1372          of loop exit phi nodes.  */
1373       if (current_loops
1374           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1375           && is_gimple_reg (def)
1376           && TREE_CODE (use) == SSA_NAME
1377           && a->loop_father != b->loop_father)
1378         may_replace_uses = false;
1379
1380       if (!may_replace_uses)
1381         {
1382           gcc_assert (is_gimple_reg (def));
1383
1384           /* Note that just emitting the copies is fine -- there is no problem
1385              with ordering of phi nodes.  This is because A is the single
1386              predecessor of B, therefore results of the phi nodes cannot
1387              appear as arguments of the phi nodes.  */
1388           copy = gimple_build_assign (def, use);
1389           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1390           remove_phi_node (&psi, false);
1391         }
1392       else
1393         {
1394           /* If we deal with a PHI for virtual operands, we can simply
1395              propagate these without fussing with folding or updating
1396              the stmt.  */
1397           if (!is_gimple_reg (def))
1398             {
1399               imm_use_iterator iter;
1400               use_operand_p use_p;
1401               gimple stmt;
1402
1403               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1404                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1405                   SET_USE (use_p, use);
1406             }
1407           else
1408             replace_uses_by (def, use);
1409
1410           remove_phi_node (&psi, true);
1411         }
1412     }
1413
1414   /* Ensure that B follows A.  */
1415   move_block_after (b, a);
1416
1417   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1418   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1419
1420   /* Remove labels from B and set gimple_bb to A for other statements.  */
1421   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1422     {
1423       if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1424         {
1425           gimple label = gsi_stmt (gsi);
1426
1427           gsi_remove (&gsi, false);
1428
1429           /* Now that we can thread computed gotos, we might have
1430              a situation where we have a forced label in block B
1431              However, the label at the start of block B might still be
1432              used in other ways (think about the runtime checking for
1433              Fortran assigned gotos).  So we can not just delete the
1434              label.  Instead we move the label to the start of block A.  */
1435           if (FORCED_LABEL (gimple_label_label (label)))
1436             {
1437               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1438               gsi_insert_before (&dest_gsi, label, GSI_NEW_STMT);
1439             }
1440         }
1441       else
1442         {
1443           gimple_set_bb (gsi_stmt (gsi), a);
1444           gsi_next (&gsi);
1445         }
1446     }
1447
1448   /* Merge the sequences.  */
1449   last = gsi_last_bb (a);
1450   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1451   set_bb_seq (b, NULL);
1452
1453   if (cfgcleanup_altered_bbs)
1454     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1455 }
1456
1457
1458 /* Return the one of two successors of BB that is not reachable by a
1459    reached by a complex edge, if there is one.  Else, return BB.  We use
1460    this in optimizations that use post-dominators for their heuristics,
1461    to catch the cases in C++ where function calls are involved.  */
1462
1463 basic_block
1464 single_noncomplex_succ (basic_block bb)
1465 {
1466   edge e0, e1;
1467   if (EDGE_COUNT (bb->succs) != 2)
1468     return bb;
1469
1470   e0 = EDGE_SUCC (bb, 0);
1471   e1 = EDGE_SUCC (bb, 1);
1472   if (e0->flags & EDGE_COMPLEX)
1473     return e1->dest;
1474   if (e1->flags & EDGE_COMPLEX)
1475     return e0->dest;
1476
1477   return bb;
1478 }
1479
1480
1481 /* Walk the function tree removing unnecessary statements.
1482
1483      * Empty statement nodes are removed
1484
1485      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1486
1487      * Unnecessary COND_EXPRs are removed
1488
1489      * Some unnecessary BIND_EXPRs are removed
1490
1491      * GOTO_EXPRs immediately preceding destination are removed.
1492
1493    Clearly more work could be done.  The trick is doing the analysis
1494    and removal fast enough to be a net improvement in compile times.
1495
1496    Note that when we remove a control structure such as a COND_EXPR
1497    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1498    to ensure we eliminate all the useless code.  */
1499
1500 struct rus_data
1501 {
1502   bool repeat;
1503   bool may_throw;
1504   bool may_branch;
1505   bool has_label;
1506   bool last_was_goto;
1507   gimple_stmt_iterator last_goto_gsi;
1508 };
1509
1510
1511 static void remove_useless_stmts_1 (gimple_stmt_iterator *gsi, struct rus_data *);
1512
1513 /* Given a statement sequence, find the first executable statement with
1514    location information, and warn that it is unreachable.  When searching,
1515    descend into containers in execution order.  */
1516
1517 static bool
1518 remove_useless_stmts_warn_notreached (gimple_seq stmts)
1519 {
1520   gimple_stmt_iterator gsi;
1521
1522   for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
1523     {
1524       gimple stmt = gsi_stmt (gsi);
1525
1526       if (gimple_has_location (stmt))
1527         {
1528           location_t loc = gimple_location (stmt);
1529           if (LOCATION_LINE (loc) > 0)
1530             {
1531               warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
1532               return true;
1533             }
1534         }
1535
1536       switch (gimple_code (stmt))
1537         {
1538         /* Unfortunately, we need the CFG now to detect unreachable
1539            branches in a conditional, so conditionals are not handled here.  */
1540
1541         case GIMPLE_TRY:
1542           if (remove_useless_stmts_warn_notreached (gimple_try_eval (stmt)))
1543             return true;
1544           if (remove_useless_stmts_warn_notreached (gimple_try_cleanup (stmt)))
1545             return true;
1546           break;
1547
1548         case GIMPLE_CATCH:
1549           return remove_useless_stmts_warn_notreached (gimple_catch_handler (stmt));
1550
1551         case GIMPLE_EH_FILTER:
1552           return remove_useless_stmts_warn_notreached (gimple_eh_filter_failure (stmt));
1553
1554         case GIMPLE_BIND:
1555           return remove_useless_stmts_warn_notreached (gimple_bind_body (stmt));
1556
1557         default:
1558           break;
1559         }
1560     }
1561
1562   return false;
1563 }
1564
1565 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_COND statements.  */
1566
1567 static void
1568 remove_useless_stmts_cond (gimple_stmt_iterator *gsi, struct rus_data *data)
1569 {
1570   gimple stmt = gsi_stmt (*gsi);
1571
1572   /* The folded result must still be a conditional statement.  */
1573   fold_stmt (gsi);
1574   gcc_assert (gsi_stmt (*gsi) == stmt);
1575
1576   data->may_branch = true;
1577
1578   /* Replace trivial conditionals with gotos. */
1579   if (gimple_cond_true_p (stmt))
1580     {
1581       /* Goto THEN label.  */
1582       tree then_label = gimple_cond_true_label (stmt);
1583
1584       gsi_replace (gsi, gimple_build_goto (then_label), false);
1585       data->last_goto_gsi = *gsi;
1586       data->last_was_goto = true;
1587       data->repeat = true;
1588     }
1589   else if (gimple_cond_false_p (stmt))
1590     {
1591       /* Goto ELSE label.  */
1592       tree else_label = gimple_cond_false_label (stmt);
1593
1594       gsi_replace (gsi, gimple_build_goto (else_label), false);
1595       data->last_goto_gsi = *gsi;
1596       data->last_was_goto = true;
1597       data->repeat = true;
1598     }
1599   else
1600     {
1601       tree then_label = gimple_cond_true_label (stmt);
1602       tree else_label = gimple_cond_false_label (stmt);
1603
1604       if (then_label == else_label)
1605         {
1606           /* Goto common destination.  */
1607           gsi_replace (gsi, gimple_build_goto (then_label), false);
1608           data->last_goto_gsi = *gsi;
1609           data->last_was_goto = true;
1610           data->repeat = true;
1611         }
1612     }
1613
1614   gsi_next (gsi);
1615
1616   data->last_was_goto = false;
1617 }
1618
1619 /* Helper for remove_useless_stmts_1. 
1620    Handle the try-finally case for GIMPLE_TRY statements.  */
1621
1622 static void
1623 remove_useless_stmts_tf (gimple_stmt_iterator *gsi, struct rus_data *data)
1624 {
1625   bool save_may_branch, save_may_throw;
1626   bool this_may_branch, this_may_throw;
1627
1628   gimple_seq eval_seq, cleanup_seq;
1629   gimple_stmt_iterator eval_gsi, cleanup_gsi;
1630
1631   gimple stmt = gsi_stmt (*gsi);
1632
1633   /* Collect may_branch and may_throw information for the body only.  */
1634   save_may_branch = data->may_branch;
1635   save_may_throw = data->may_throw;
1636   data->may_branch = false;
1637   data->may_throw = false;
1638   data->last_was_goto = false;
1639
1640   eval_seq = gimple_try_eval (stmt);
1641   eval_gsi = gsi_start (eval_seq);
1642   remove_useless_stmts_1 (&eval_gsi, data);
1643
1644   this_may_branch = data->may_branch;
1645   this_may_throw = data->may_throw;
1646   data->may_branch |= save_may_branch;
1647   data->may_throw |= save_may_throw;
1648   data->last_was_goto = false;
1649
1650   cleanup_seq = gimple_try_cleanup (stmt);
1651   cleanup_gsi = gsi_start (cleanup_seq);
1652   remove_useless_stmts_1 (&cleanup_gsi, data);
1653
1654   /* If the body is empty, then we can emit the FINALLY block without
1655      the enclosing TRY_FINALLY_EXPR.  */
1656   if (gimple_seq_empty_p (eval_seq))
1657     {
1658       gsi_insert_seq_before (gsi, cleanup_seq, GSI_SAME_STMT);
1659       gsi_remove (gsi, false);
1660       data->repeat = true;
1661     }
1662
1663   /* If the handler is empty, then we can emit the TRY block without
1664      the enclosing TRY_FINALLY_EXPR.  */
1665   else if (gimple_seq_empty_p (cleanup_seq))
1666     {
1667       gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1668       gsi_remove (gsi, false);
1669       data->repeat = true;
1670     }
1671
1672   /* If the body neither throws, nor branches, then we can safely
1673      string the TRY and FINALLY blocks together.  */
1674   else if (!this_may_branch && !this_may_throw)
1675     {
1676       gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1677       gsi_insert_seq_before (gsi, cleanup_seq, GSI_SAME_STMT);
1678       gsi_remove (gsi, false);
1679       data->repeat = true;
1680     }
1681   else
1682     gsi_next (gsi);
1683 }
1684
1685 /* Helper for remove_useless_stmts_1. 
1686    Handle the try-catch case for GIMPLE_TRY statements.  */
1687
1688 static void
1689 remove_useless_stmts_tc (gimple_stmt_iterator *gsi, struct rus_data *data)
1690 {
1691   bool save_may_throw, this_may_throw;
1692
1693   gimple_seq eval_seq, cleanup_seq, handler_seq, failure_seq;
1694   gimple_stmt_iterator eval_gsi, cleanup_gsi, handler_gsi, failure_gsi;
1695
1696   gimple stmt = gsi_stmt (*gsi);
1697
1698   /* Collect may_throw information for the body only.  */
1699   save_may_throw = data->may_throw;
1700   data->may_throw = false;
1701   data->last_was_goto = false;
1702
1703   eval_seq = gimple_try_eval (stmt);
1704   eval_gsi = gsi_start (eval_seq);
1705   remove_useless_stmts_1 (&eval_gsi, data);
1706
1707   this_may_throw = data->may_throw;
1708   data->may_throw = save_may_throw;
1709
1710   cleanup_seq = gimple_try_cleanup (stmt);
1711
1712   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1713   if (!this_may_throw)
1714     {
1715       if (warn_notreached)
1716         {
1717           remove_useless_stmts_warn_notreached (cleanup_seq);
1718         }
1719       gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1720       gsi_remove (gsi, false);
1721       data->repeat = true;
1722       return;
1723     }
1724
1725   /* Process the catch clause specially.  We may be able to tell that
1726      no exceptions propagate past this point.  */
1727
1728   this_may_throw = true;
1729   cleanup_gsi = gsi_start (cleanup_seq);
1730   stmt = gsi_stmt (cleanup_gsi);
1731   data->last_was_goto = false;
1732
1733   switch (gimple_code (stmt))
1734     {
1735     case GIMPLE_CATCH:
1736       /* If the first element is a catch, they all must be.  */
1737       while (!gsi_end_p (cleanup_gsi))
1738         {
1739           stmt = gsi_stmt (cleanup_gsi);
1740           /* If we catch all exceptions, then the body does not
1741              propagate exceptions past this point.  */
1742           if (gimple_catch_types (stmt) == NULL)
1743             this_may_throw = false;
1744           data->last_was_goto = false;
1745           handler_seq = gimple_catch_handler (stmt);
1746           handler_gsi = gsi_start (handler_seq);
1747           remove_useless_stmts_1 (&handler_gsi, data);
1748           gsi_next (&cleanup_gsi);
1749         }
1750       gsi_next (gsi);
1751       break;
1752
1753     case GIMPLE_EH_FILTER:
1754       /* If the first element is an eh_filter, it should stand alone.  */
1755       if (gimple_eh_filter_must_not_throw (stmt))
1756         this_may_throw = false;
1757       else if (gimple_eh_filter_types (stmt) == NULL)
1758         this_may_throw = false;
1759       failure_seq = gimple_eh_filter_failure (stmt);
1760       failure_gsi = gsi_start (failure_seq);
1761       remove_useless_stmts_1 (&failure_gsi, data);
1762       gsi_next (gsi);
1763       break;
1764
1765     default:
1766       /* Otherwise this is a list of cleanup statements.  */
1767       remove_useless_stmts_1 (&cleanup_gsi, data);
1768
1769       /* If the cleanup is empty, then we can emit the TRY block without
1770          the enclosing TRY_CATCH_EXPR.  */
1771       if (gimple_seq_empty_p (cleanup_seq))
1772         {
1773           gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1774           gsi_remove(gsi, false);
1775           data->repeat = true;
1776         }
1777       else
1778         gsi_next (gsi);
1779       break;
1780     }
1781
1782   data->may_throw |= this_may_throw;
1783 }
1784
1785 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_BIND statements.  */
1786
1787 static void
1788 remove_useless_stmts_bind (gimple_stmt_iterator *gsi, struct rus_data *data ATTRIBUTE_UNUSED)
1789 {
1790   tree block;
1791   gimple_seq body_seq, fn_body_seq;
1792   gimple_stmt_iterator body_gsi;
1793
1794   gimple stmt = gsi_stmt (*gsi);
1795
1796   /* First remove anything underneath the BIND_EXPR.  */
1797   
1798   body_seq = gimple_bind_body (stmt);
1799   body_gsi = gsi_start (body_seq);
1800   remove_useless_stmts_1 (&body_gsi, data);
1801
1802   /* If the GIMPLE_BIND has no variables, then we can pull everything
1803      up one level and remove the GIMPLE_BIND, unless this is the toplevel
1804      GIMPLE_BIND for the current function or an inlined function.
1805
1806      When this situation occurs we will want to apply this
1807      optimization again.  */
1808   block = gimple_bind_block (stmt);
1809   fn_body_seq = gimple_body (current_function_decl);
1810   if (gimple_bind_vars (stmt) == NULL_TREE
1811       && (gimple_seq_empty_p (fn_body_seq)
1812           || stmt != gimple_seq_first_stmt (fn_body_seq))
1813       && (! block
1814           || ! BLOCK_ABSTRACT_ORIGIN (block)
1815           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1816               != FUNCTION_DECL)))
1817     {
1818       tree var = NULL_TREE;
1819       /* Even if there are no gimple_bind_vars, there might be other
1820          decls in BLOCK_VARS rendering the GIMPLE_BIND not useless.  */
1821       if (block && !BLOCK_NUM_NONLOCALIZED_VARS (block))
1822         for (var = BLOCK_VARS (block); var; var = TREE_CHAIN (var))
1823           if (TREE_CODE (var) == IMPORTED_DECL)
1824             break;
1825       if (var || (block && BLOCK_NUM_NONLOCALIZED_VARS (block)))
1826         gsi_next (gsi);
1827       else
1828         {
1829           gsi_insert_seq_before (gsi, body_seq, GSI_SAME_STMT);
1830           gsi_remove (gsi, false);
1831           data->repeat = true;
1832         }
1833     }
1834   else
1835     gsi_next (gsi);
1836 }
1837
1838 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_GOTO statements.  */
1839
1840 static void
1841 remove_useless_stmts_goto (gimple_stmt_iterator *gsi, struct rus_data *data)
1842 {
1843   gimple stmt = gsi_stmt (*gsi);
1844
1845   tree dest = gimple_goto_dest (stmt);
1846
1847   data->may_branch = true;
1848   data->last_was_goto = false;
1849
1850   /* Record iterator for last goto expr, so that we can delete it if unnecessary.  */
1851   if (TREE_CODE (dest) == LABEL_DECL)
1852     {
1853       data->last_goto_gsi = *gsi;
1854       data->last_was_goto = true;
1855     }
1856
1857   gsi_next(gsi);
1858 }
1859
1860 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_LABEL statements.  */
1861
1862 static void
1863 remove_useless_stmts_label (gimple_stmt_iterator *gsi, struct rus_data *data)
1864 {
1865   gimple stmt = gsi_stmt (*gsi);
1866
1867   tree label = gimple_label_label (stmt);
1868
1869   data->has_label = true;
1870
1871   /* We do want to jump across non-local label receiver code.  */
1872   if (DECL_NONLOCAL (label))
1873     data->last_was_goto = false;
1874
1875   else if (data->last_was_goto
1876            && gimple_goto_dest (gsi_stmt (data->last_goto_gsi)) == label)
1877     {
1878       /* Replace the preceding GIMPLE_GOTO statement with
1879          a GIMPLE_NOP, which will be subsequently removed.
1880          In this way, we avoid invalidating other iterators
1881          active on the statement sequence.  */
1882       gsi_replace(&data->last_goto_gsi, gimple_build_nop(), false);
1883       data->last_was_goto = false;
1884       data->repeat = true;
1885     }
1886
1887   /* ??? Add something here to delete unused labels.  */
1888
1889   gsi_next (gsi);
1890 }
1891
1892
1893 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1894
1895 void
1896 notice_special_calls (gimple call)
1897 {
1898   int flags = gimple_call_flags (call);
1899
1900   if (flags & ECF_MAY_BE_ALLOCA)
1901     cfun->calls_alloca = true;
1902   if (flags & ECF_RETURNS_TWICE)
1903     cfun->calls_setjmp = true;
1904 }
1905
1906
1907 /* Clear flags set by notice_special_calls.  Used by dead code removal
1908    to update the flags.  */
1909
1910 void
1911 clear_special_calls (void)
1912 {
1913   cfun->calls_alloca = false;
1914   cfun->calls_setjmp = false;
1915 }
1916
1917 /* Remove useless statements from a statement sequence, and perform
1918    some preliminary simplifications.  */
1919
1920 static void
1921 remove_useless_stmts_1 (gimple_stmt_iterator *gsi, struct rus_data *data)
1922 {
1923   while (!gsi_end_p (*gsi))
1924     {
1925       gimple stmt = gsi_stmt (*gsi);
1926
1927       switch (gimple_code (stmt))
1928         {
1929         case GIMPLE_COND:
1930           remove_useless_stmts_cond (gsi, data);
1931           break;
1932
1933         case GIMPLE_GOTO:
1934           remove_useless_stmts_goto (gsi, data);
1935           break;
1936
1937         case GIMPLE_LABEL:
1938           remove_useless_stmts_label (gsi, data);
1939           break;
1940
1941         case GIMPLE_ASSIGN:
1942           fold_stmt (gsi);
1943           stmt = gsi_stmt (*gsi);
1944           data->last_was_goto = false;
1945           if (stmt_could_throw_p (stmt))
1946             data->may_throw = true;
1947           gsi_next (gsi);
1948           break;
1949
1950         case GIMPLE_ASM:
1951           fold_stmt (gsi);
1952           data->last_was_goto = false;
1953           gsi_next (gsi);
1954           break;
1955
1956         case GIMPLE_CALL:
1957           fold_stmt (gsi);
1958           stmt = gsi_stmt (*gsi);
1959           data->last_was_goto = false;
1960           if (is_gimple_call (stmt))
1961             notice_special_calls (stmt);
1962
1963           /* We used to call update_gimple_call_flags here,
1964              which copied side-effects and nothrows status
1965              from the function decl to the call.  In the new
1966              tuplified GIMPLE, the accessors for this information
1967              always consult the function decl, so this copying
1968              is no longer necessary.  */
1969           if (stmt_could_throw_p (stmt))
1970             data->may_throw = true;
1971           gsi_next (gsi);
1972           break;
1973
1974         case GIMPLE_RETURN:
1975           fold_stmt (gsi);
1976           data->last_was_goto = false;
1977           data->may_branch = true;
1978           gsi_next (gsi);
1979           break;
1980
1981         case GIMPLE_BIND:
1982           remove_useless_stmts_bind (gsi, data);
1983           break;
1984
1985         case GIMPLE_TRY:
1986           if (gimple_try_kind (stmt) == GIMPLE_TRY_CATCH)
1987             remove_useless_stmts_tc (gsi, data);
1988           else if (gimple_try_kind (stmt) == GIMPLE_TRY_FINALLY)
1989             remove_useless_stmts_tf (gsi, data);
1990           else
1991             gcc_unreachable ();
1992           break;
1993
1994         case GIMPLE_CATCH:
1995           gcc_unreachable ();
1996           break;
1997
1998         case GIMPLE_NOP:
1999           gsi_remove (gsi, false);
2000           break;
2001
2002         case GIMPLE_OMP_FOR:
2003           {
2004             gimple_seq pre_body_seq = gimple_omp_for_pre_body (stmt);
2005             gimple_stmt_iterator pre_body_gsi = gsi_start (pre_body_seq);
2006
2007             remove_useless_stmts_1 (&pre_body_gsi, data);
2008             data->last_was_goto = false;
2009           }
2010           /* FALLTHROUGH */
2011         case GIMPLE_OMP_CRITICAL:
2012         case GIMPLE_OMP_CONTINUE:
2013         case GIMPLE_OMP_MASTER:
2014         case GIMPLE_OMP_ORDERED:
2015         case GIMPLE_OMP_SECTION:
2016         case GIMPLE_OMP_SECTIONS:
2017         case GIMPLE_OMP_SINGLE:
2018           {
2019             gimple_seq body_seq = gimple_omp_body (stmt);
2020             gimple_stmt_iterator body_gsi = gsi_start (body_seq);
2021
2022             remove_useless_stmts_1 (&body_gsi, data);
2023             data->last_was_goto = false;
2024             gsi_next (gsi);
2025           }
2026           break;
2027
2028         case GIMPLE_OMP_PARALLEL:
2029         case GIMPLE_OMP_TASK:
2030           {
2031             /* Make sure the outermost GIMPLE_BIND isn't removed
2032                as useless.  */
2033             gimple_seq body_seq = gimple_omp_body (stmt);
2034             gimple bind = gimple_seq_first_stmt (body_seq);
2035             gimple_seq bind_seq = gimple_bind_body (bind);
2036             gimple_stmt_iterator bind_gsi = gsi_start (bind_seq);
2037
2038             remove_useless_stmts_1 (&bind_gsi, data);
2039             data->last_was_goto = false;
2040             gsi_next (gsi);
2041           }
2042           break;
2043
2044         default:
2045           data->last_was_goto = false;
2046           gsi_next (gsi);
2047           break;
2048         }
2049     }
2050 }
2051
2052 /* Walk the function tree, removing useless statements and performing
2053    some preliminary simplifications.  */
2054
2055 static unsigned int
2056 remove_useless_stmts (void)
2057 {
2058   struct rus_data data;
2059
2060   clear_special_calls ();
2061
2062   do
2063     {
2064       gimple_stmt_iterator gsi;
2065
2066       gsi = gsi_start (gimple_body (current_function_decl));
2067       memset (&data, 0, sizeof (data));
2068       remove_useless_stmts_1 (&gsi, &data);
2069     }
2070   while (data.repeat);
2071
2072 #ifdef ENABLE_TYPES_CHECKING
2073   verify_types_in_gimple_seq (gimple_body (current_function_decl));
2074 #endif
2075
2076   return 0;
2077 }
2078
2079
2080 struct gimple_opt_pass pass_remove_useless_stmts =
2081 {
2082  {
2083   GIMPLE_PASS,
2084   "useless",                            /* name */
2085   NULL,                                 /* gate */
2086   remove_useless_stmts,                 /* execute */
2087   NULL,                                 /* sub */
2088   NULL,                                 /* next */
2089   0,                                    /* static_pass_number */
2090   TV_NONE,                              /* tv_id */
2091   PROP_gimple_any,                      /* properties_required */
2092   0,                                    /* properties_provided */
2093   0,                                    /* properties_destroyed */
2094   0,                                    /* todo_flags_start */
2095   TODO_dump_func                        /* todo_flags_finish */
2096  }
2097 };
2098
2099 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
2100
2101 static void
2102 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
2103 {
2104   /* Since this block is no longer reachable, we can just delete all
2105      of its PHI nodes.  */
2106   remove_phi_nodes (bb);
2107
2108   /* Remove edges to BB's successors.  */
2109   while (EDGE_COUNT (bb->succs) > 0)
2110     remove_edge (EDGE_SUCC (bb, 0));
2111 }
2112
2113
2114 /* Remove statements of basic block BB.  */
2115
2116 static void
2117 remove_bb (basic_block bb)
2118 {
2119   gimple_stmt_iterator i;
2120   source_location loc = UNKNOWN_LOCATION;
2121
2122   if (dump_file)
2123     {
2124       fprintf (dump_file, "Removing basic block %d\n", bb->index);
2125       if (dump_flags & TDF_DETAILS)
2126         {
2127           dump_bb (bb, dump_file, 0);
2128           fprintf (dump_file, "\n");
2129         }
2130     }
2131
2132   if (current_loops)
2133     {
2134       struct loop *loop = bb->loop_father;
2135
2136       /* If a loop gets removed, clean up the information associated
2137          with it.  */
2138       if (loop->latch == bb
2139           || loop->header == bb)
2140         free_numbers_of_iterations_estimates_loop (loop);
2141     }
2142
2143   /* Remove all the instructions in the block.  */
2144   if (bb_seq (bb) != NULL)
2145     {
2146       for (i = gsi_start_bb (bb); !gsi_end_p (i);)
2147         {
2148           gimple stmt = gsi_stmt (i);
2149           if (gimple_code (stmt) == GIMPLE_LABEL
2150               && (FORCED_LABEL (gimple_label_label (stmt))
2151                   || DECL_NONLOCAL (gimple_label_label (stmt))))
2152             {
2153               basic_block new_bb;
2154               gimple_stmt_iterator new_gsi;
2155
2156               /* A non-reachable non-local label may still be referenced.
2157                  But it no longer needs to carry the extra semantics of
2158                  non-locality.  */
2159               if (DECL_NONLOCAL (gimple_label_label (stmt)))
2160                 {
2161                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
2162                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
2163                 }
2164
2165               new_bb = bb->prev_bb;
2166               new_gsi = gsi_start_bb (new_bb);
2167               gsi_remove (&i, false);
2168               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
2169             }
2170           else
2171             {
2172               /* Release SSA definitions if we are in SSA.  Note that we
2173                  may be called when not in SSA.  For example,
2174                  final_cleanup calls this function via
2175                  cleanup_tree_cfg.  */
2176               if (gimple_in_ssa_p (cfun))
2177                 release_defs (stmt);
2178
2179               gsi_remove (&i, true);
2180             }
2181
2182           /* Don't warn for removed gotos.  Gotos are often removed due to
2183              jump threading, thus resulting in bogus warnings.  Not great,
2184              since this way we lose warnings for gotos in the original
2185              program that are indeed unreachable.  */
2186           if (gimple_code (stmt) != GIMPLE_GOTO
2187               && gimple_has_location (stmt)
2188               && !loc)
2189             loc = gimple_location (stmt);
2190         }
2191     }
2192
2193   /* If requested, give a warning that the first statement in the
2194      block is unreachable.  We walk statements backwards in the
2195      loop above, so the last statement we process is the first statement
2196      in the block.  */
2197   if (loc > BUILTINS_LOCATION && LOCATION_LINE (loc) > 0)
2198     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2199
2200   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2201   bb->il.gimple = NULL;
2202 }
2203
2204
2205 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2206    predicate VAL, return the edge that will be taken out of the block.
2207    If VAL does not match a unique edge, NULL is returned.  */
2208
2209 edge
2210 find_taken_edge (basic_block bb, tree val)
2211 {
2212   gimple stmt;
2213
2214   stmt = last_stmt (bb);
2215
2216   gcc_assert (stmt);
2217   gcc_assert (is_ctrl_stmt (stmt));
2218
2219   if (val == NULL)
2220     return NULL;
2221
2222   if (!is_gimple_min_invariant (val))
2223     return NULL;
2224
2225   if (gimple_code (stmt) == GIMPLE_COND)
2226     return find_taken_edge_cond_expr (bb, val);
2227
2228   if (gimple_code (stmt) == GIMPLE_SWITCH)
2229     return find_taken_edge_switch_expr (bb, val);
2230
2231   if (computed_goto_p (stmt))
2232     {
2233       /* Only optimize if the argument is a label, if the argument is
2234          not a label then we can not construct a proper CFG.
2235
2236          It may be the case that we only need to allow the LABEL_REF to
2237          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2238          appear inside a LABEL_EXPR just to be safe.  */
2239       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2240           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2241         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2242       return NULL;
2243     }
2244
2245   gcc_unreachable ();
2246 }
2247
2248 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2249    statement, determine which of the outgoing edges will be taken out of the
2250    block.  Return NULL if either edge may be taken.  */
2251
2252 static edge
2253 find_taken_edge_computed_goto (basic_block bb, tree val)
2254 {
2255   basic_block dest;
2256   edge e = NULL;
2257
2258   dest = label_to_block (val);
2259   if (dest)
2260     {
2261       e = find_edge (bb, dest);
2262       gcc_assert (e != NULL);
2263     }
2264
2265   return e;
2266 }
2267
2268 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2269    statement, determine which of the two edges will be taken out of the
2270    block.  Return NULL if either edge may be taken.  */
2271
2272 static edge
2273 find_taken_edge_cond_expr (basic_block bb, tree val)
2274 {
2275   edge true_edge, false_edge;
2276
2277   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2278
2279   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2280   return (integer_zerop (val) ? false_edge : true_edge);
2281 }
2282
2283 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2284    statement, determine which edge will be taken out of the block.  Return
2285    NULL if any edge may be taken.  */
2286
2287 static edge
2288 find_taken_edge_switch_expr (basic_block bb, tree val)
2289 {
2290   basic_block dest_bb;
2291   edge e;
2292   gimple switch_stmt;
2293   tree taken_case;
2294
2295   switch_stmt = last_stmt (bb);
2296   taken_case = find_case_label_for_value (switch_stmt, val);
2297   dest_bb = label_to_block (CASE_LABEL (taken_case));
2298
2299   e = find_edge (bb, dest_bb);
2300   gcc_assert (e);
2301   return e;
2302 }
2303
2304
2305 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2306    We can make optimal use here of the fact that the case labels are
2307    sorted: We can do a binary search for a case matching VAL.  */
2308
2309 static tree
2310 find_case_label_for_value (gimple switch_stmt, tree val)
2311 {
2312   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2313   tree default_case = gimple_switch_default_label (switch_stmt);
2314
2315   for (low = 0, high = n; high - low > 1; )
2316     {
2317       size_t i = (high + low) / 2;
2318       tree t = gimple_switch_label (switch_stmt, i);
2319       int cmp;
2320
2321       /* Cache the result of comparing CASE_LOW and val.  */
2322       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2323
2324       if (cmp > 0)
2325         high = i;
2326       else
2327         low = i;
2328
2329       if (CASE_HIGH (t) == NULL)
2330         {
2331           /* A singe-valued case label.  */
2332           if (cmp == 0)
2333             return t;
2334         }
2335       else
2336         {
2337           /* A case range.  We can only handle integer ranges.  */
2338           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2339             return t;
2340         }
2341     }
2342
2343   return default_case;
2344 }
2345
2346
2347 /* Dump a basic block on stderr.  */
2348
2349 void
2350 gimple_debug_bb (basic_block bb)
2351 {
2352   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2353 }
2354
2355
2356 /* Dump basic block with index N on stderr.  */
2357
2358 basic_block
2359 gimple_debug_bb_n (int n)
2360 {
2361   gimple_debug_bb (BASIC_BLOCK (n));
2362   return BASIC_BLOCK (n);
2363 }
2364
2365
2366 /* Dump the CFG on stderr.
2367
2368    FLAGS are the same used by the tree dumping functions
2369    (see TDF_* in tree-pass.h).  */
2370
2371 void
2372 gimple_debug_cfg (int flags)
2373 {
2374   gimple_dump_cfg (stderr, flags);
2375 }
2376
2377
2378 /* Dump the program showing basic block boundaries on the given FILE.
2379
2380    FLAGS are the same used by the tree dumping functions (see TDF_* in
2381    tree.h).  */
2382
2383 void
2384 gimple_dump_cfg (FILE *file, int flags)
2385 {
2386   if (flags & TDF_DETAILS)
2387     {
2388       const char *funcname
2389         = lang_hooks.decl_printable_name (current_function_decl, 2);
2390
2391       fputc ('\n', file);
2392       fprintf (file, ";; Function %s\n\n", funcname);
2393       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2394                n_basic_blocks, n_edges, last_basic_block);
2395
2396       brief_dump_cfg (file);
2397       fprintf (file, "\n");
2398     }
2399
2400   if (flags & TDF_STATS)
2401     dump_cfg_stats (file);
2402
2403   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2404 }
2405
2406
2407 /* Dump CFG statistics on FILE.  */
2408
2409 void
2410 dump_cfg_stats (FILE *file)
2411 {
2412   static long max_num_merged_labels = 0;
2413   unsigned long size, total = 0;
2414   long num_edges;
2415   basic_block bb;
2416   const char * const fmt_str   = "%-30s%-13s%12s\n";
2417   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2418   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2419   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2420   const char *funcname
2421     = lang_hooks.decl_printable_name (current_function_decl, 2);
2422
2423
2424   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2425
2426   fprintf (file, "---------------------------------------------------------\n");
2427   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2428   fprintf (file, fmt_str, "", "  instances  ", "used ");
2429   fprintf (file, "---------------------------------------------------------\n");
2430
2431   size = n_basic_blocks * sizeof (struct basic_block_def);
2432   total += size;
2433   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2434            SCALE (size), LABEL (size));
2435
2436   num_edges = 0;
2437   FOR_EACH_BB (bb)
2438     num_edges += EDGE_COUNT (bb->succs);
2439   size = num_edges * sizeof (struct edge_def);
2440   total += size;
2441   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2442
2443   fprintf (file, "---------------------------------------------------------\n");
2444   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2445            LABEL (total));
2446   fprintf (file, "---------------------------------------------------------\n");
2447   fprintf (file, "\n");
2448
2449   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2450     max_num_merged_labels = cfg_stats.num_merged_labels;
2451
2452   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2453            cfg_stats.num_merged_labels, max_num_merged_labels);
2454
2455   fprintf (file, "\n");
2456 }
2457
2458
2459 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2460    linked in the final executable.  */
2461
2462 void
2463 debug_cfg_stats (void)
2464 {
2465   dump_cfg_stats (stderr);
2466 }
2467
2468
2469 /* Dump the flowgraph to a .vcg FILE.  */
2470
2471 static void
2472 gimple_cfg2vcg (FILE *file)
2473 {
2474   edge e;
2475   edge_iterator ei;
2476   basic_block bb;
2477   const char *funcname
2478     = lang_hooks.decl_printable_name (current_function_decl, 2);
2479
2480   /* Write the file header.  */
2481   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2482   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2483   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2484
2485   /* Write blocks and edges.  */
2486   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2487     {
2488       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2489                e->dest->index);
2490
2491       if (e->flags & EDGE_FAKE)
2492         fprintf (file, " linestyle: dotted priority: 10");
2493       else
2494         fprintf (file, " linestyle: solid priority: 100");
2495
2496       fprintf (file, " }\n");
2497     }
2498   fputc ('\n', file);
2499
2500   FOR_EACH_BB (bb)
2501     {
2502       enum gimple_code head_code, end_code;
2503       const char *head_name, *end_name;
2504       int head_line = 0;
2505       int end_line = 0;
2506       gimple first = first_stmt (bb);
2507       gimple last = last_stmt (bb);
2508
2509       if (first)
2510         {
2511           head_code = gimple_code (first);
2512           head_name = gimple_code_name[head_code];
2513           head_line = get_lineno (first);
2514         }
2515       else
2516         head_name = "no-statement";
2517
2518       if (last)
2519         {
2520           end_code = gimple_code (last);
2521           end_name = gimple_code_name[end_code];
2522           end_line = get_lineno (last);
2523         }
2524       else
2525         end_name = "no-statement";
2526
2527       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2528                bb->index, bb->index, head_name, head_line, end_name,
2529                end_line);
2530
2531       FOR_EACH_EDGE (e, ei, bb->succs)
2532         {
2533           if (e->dest == EXIT_BLOCK_PTR)
2534             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2535           else
2536             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2537
2538           if (e->flags & EDGE_FAKE)
2539             fprintf (file, " priority: 10 linestyle: dotted");
2540           else
2541             fprintf (file, " priority: 100 linestyle: solid");
2542
2543           fprintf (file, " }\n");
2544         }
2545
2546       if (bb->next_bb != EXIT_BLOCK_PTR)
2547         fputc ('\n', file);
2548     }
2549
2550   fputs ("}\n\n", file);
2551 }
2552
2553
2554
2555 /*---------------------------------------------------------------------------
2556                              Miscellaneous helpers
2557 ---------------------------------------------------------------------------*/
2558
2559 /* Return true if T represents a stmt that always transfers control.  */
2560
2561 bool
2562 is_ctrl_stmt (gimple t)
2563 {
2564   return gimple_code (t) == GIMPLE_COND
2565     || gimple_code (t) == GIMPLE_SWITCH
2566     || gimple_code (t) == GIMPLE_GOTO
2567     || gimple_code (t) == GIMPLE_RETURN
2568     || gimple_code (t) == GIMPLE_RESX;
2569 }
2570
2571
2572 /* Return true if T is a statement that may alter the flow of control
2573    (e.g., a call to a non-returning function).  */
2574
2575 bool
2576 is_ctrl_altering_stmt (gimple t)
2577 {
2578   gcc_assert (t);
2579
2580   if (is_gimple_call (t))
2581     {
2582       int flags = gimple_call_flags (t);
2583
2584       /* A non-pure/const call alters flow control if the current
2585          function has nonlocal labels.  */
2586       if (!(flags & (ECF_CONST | ECF_PURE))
2587           && cfun->has_nonlocal_label)
2588         return true;
2589
2590       /* A call also alters control flow if it does not return.  */
2591       if (gimple_call_flags (t) & ECF_NORETURN)
2592         return true;
2593     }
2594
2595   /* OpenMP directives alter control flow.  */
2596   if (is_gimple_omp (t))
2597     return true;
2598
2599   /* If a statement can throw, it alters control flow.  */
2600   return stmt_can_throw_internal (t);
2601 }
2602
2603
2604 /* Return true if T is a simple local goto.  */
2605
2606 bool
2607 simple_goto_p (gimple t)
2608 {
2609   return (gimple_code (t) == GIMPLE_GOTO
2610           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2611 }
2612
2613
2614 /* Return true if T can make an abnormal transfer of control flow.
2615    Transfers of control flow associated with EH are excluded.  */
2616
2617 bool
2618 stmt_can_make_abnormal_goto (gimple t)
2619 {
2620   if (computed_goto_p (t))
2621     return true;
2622   if (is_gimple_call (t))
2623     return gimple_has_side_effects (t) && cfun->has_nonlocal_label;
2624   return false;
2625 }
2626
2627
2628 /* Return true if STMT should start a new basic block.  PREV_STMT is
2629    the statement preceding STMT.  It is used when STMT is a label or a
2630    case label.  Labels should only start a new basic block if their
2631    previous statement wasn't a label.  Otherwise, sequence of labels
2632    would generate unnecessary basic blocks that only contain a single
2633    label.  */
2634
2635 static inline bool
2636 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2637 {
2638   if (stmt == NULL)
2639     return false;
2640
2641   /* Labels start a new basic block only if the preceding statement
2642      wasn't a label of the same type.  This prevents the creation of
2643      consecutive blocks that have nothing but a single label.  */
2644   if (gimple_code (stmt) == GIMPLE_LABEL)
2645     {
2646       /* Nonlocal and computed GOTO targets always start a new block.  */
2647       if (DECL_NONLOCAL (gimple_label_label (stmt))
2648           || FORCED_LABEL (gimple_label_label (stmt)))
2649         return true;
2650
2651       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2652         {
2653           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2654             return true;
2655
2656           cfg_stats.num_merged_labels++;
2657           return false;
2658         }
2659       else
2660         return true;
2661     }
2662
2663   return false;
2664 }
2665
2666
2667 /* Return true if T should end a basic block.  */
2668
2669 bool
2670 stmt_ends_bb_p (gimple t)
2671 {
2672   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2673 }
2674
2675 /* Remove block annotations and other data structures.  */
2676
2677 void
2678 delete_tree_cfg_annotations (void)
2679 {
2680   label_to_block_map = NULL;
2681 }
2682
2683
2684 /* Return the first statement in basic block BB.  */
2685
2686 gimple
2687 first_stmt (basic_block bb)
2688 {
2689   gimple_stmt_iterator i = gsi_start_bb (bb);
2690   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2691 }
2692
2693 /* Return the last statement in basic block BB.  */
2694
2695 gimple
2696 last_stmt (basic_block bb)
2697 {
2698   gimple_stmt_iterator b = gsi_last_bb (bb);
2699   return !gsi_end_p (b) ? gsi_stmt (b) : NULL;
2700 }
2701
2702 /* Return the last statement of an otherwise empty block.  Return NULL
2703    if the block is totally empty, or if it contains more than one
2704    statement.  */
2705
2706 gimple
2707 last_and_only_stmt (basic_block bb)
2708 {
2709   gimple_stmt_iterator i = gsi_last_bb (bb);
2710   gimple last, prev;
2711
2712   if (gsi_end_p (i))
2713     return NULL;
2714
2715   last = gsi_stmt (i);
2716   gsi_prev (&i);
2717   if (gsi_end_p (i))
2718     return last;
2719
2720   /* Empty statements should no longer appear in the instruction stream.
2721      Everything that might have appeared before should be deleted by
2722      remove_useless_stmts, and the optimizers should just gsi_remove
2723      instead of smashing with build_empty_stmt.
2724
2725      Thus the only thing that should appear here in a block containing
2726      one executable statement is a label.  */
2727   prev = gsi_stmt (i);
2728   if (gimple_code (prev) == GIMPLE_LABEL)
2729     return last;
2730   else
2731     return NULL;
2732 }
2733
2734 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2735
2736 static void
2737 reinstall_phi_args (edge new_edge, edge old_edge)
2738 {
2739   edge_var_map_vector v;
2740   edge_var_map *vm;
2741   int i;
2742   gimple_stmt_iterator phis;
2743   
2744   v = redirect_edge_var_map_vector (old_edge);
2745   if (!v)
2746     return;
2747   
2748   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2749        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2750        i++, gsi_next (&phis))
2751     {
2752       gimple phi = gsi_stmt (phis);
2753       tree result = redirect_edge_var_map_result (vm);
2754       tree arg = redirect_edge_var_map_def (vm);
2755  
2756       gcc_assert (result == gimple_phi_result (phi));
2757   
2758       add_phi_arg (phi, arg, new_edge);
2759     }
2760   
2761   redirect_edge_var_map_clear (old_edge);
2762 }
2763
2764 /* Returns the basic block after which the new basic block created
2765    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2766    near its "logical" location.  This is of most help to humans looking
2767    at debugging dumps.  */
2768
2769 static basic_block
2770 split_edge_bb_loc (edge edge_in)
2771 {
2772   basic_block dest = edge_in->dest;
2773
2774   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
2775     return edge_in->src;
2776   else
2777     return dest->prev_bb;
2778 }
2779
2780 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2781    Abort on abnormal edges.  */
2782
2783 static basic_block
2784 gimple_split_edge (edge edge_in)
2785 {
2786   basic_block new_bb, after_bb, dest;
2787   edge new_edge, e;
2788
2789   /* Abnormal edges cannot be split.  */
2790   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2791
2792   dest = edge_in->dest;
2793
2794   after_bb = split_edge_bb_loc (edge_in);
2795
2796   new_bb = create_empty_bb (after_bb);
2797   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2798   new_bb->count = edge_in->count;
2799   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2800   new_edge->probability = REG_BR_PROB_BASE;
2801   new_edge->count = edge_in->count;
2802
2803   e = redirect_edge_and_branch (edge_in, new_bb);
2804   gcc_assert (e == edge_in);
2805   reinstall_phi_args (new_edge, e);
2806
2807   return new_bb;
2808 }
2809
2810 /* Callback for walk_tree, check that all elements with address taken are
2811    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2812    inside a PHI node.  */
2813
2814 static tree
2815 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2816 {
2817   tree t = *tp, x;
2818
2819   if (TYPE_P (t))
2820     *walk_subtrees = 0;
2821
2822   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2823 #define CHECK_OP(N, MSG) \
2824   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2825        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2826
2827   switch (TREE_CODE (t))
2828     {
2829     case SSA_NAME:
2830       if (SSA_NAME_IN_FREE_LIST (t))
2831         {
2832           error ("SSA name in freelist but still referenced");
2833           return *tp;
2834         }
2835       break;
2836
2837     case INDIRECT_REF:
2838       x = TREE_OPERAND (t, 0);
2839       if (!is_gimple_reg (x) && !is_gimple_min_invariant (x))
2840         {
2841           error ("Indirect reference's operand is not a register or a constant.");
2842           return x;
2843         }
2844       break;
2845
2846     case ASSERT_EXPR:
2847       x = fold (ASSERT_EXPR_COND (t));
2848       if (x == boolean_false_node)
2849         {
2850           error ("ASSERT_EXPR with an always-false condition");
2851           return *tp;
2852         }
2853       break;
2854
2855     case MODIFY_EXPR:
2856       error ("MODIFY_EXPR not expected while having tuples.");
2857       return *tp;
2858
2859     case ADDR_EXPR:
2860       {
2861         bool old_constant;
2862         bool old_side_effects;
2863         bool new_constant;
2864         bool new_side_effects;
2865
2866         gcc_assert (is_gimple_address (t));
2867
2868         old_constant = TREE_CONSTANT (t);
2869         old_side_effects = TREE_SIDE_EFFECTS (t);
2870
2871         recompute_tree_invariant_for_addr_expr (t);
2872         new_side_effects = TREE_SIDE_EFFECTS (t);
2873         new_constant = TREE_CONSTANT (t);
2874
2875         if (old_constant != new_constant)
2876           {
2877             error ("constant not recomputed when ADDR_EXPR changed");
2878             return t;
2879           }
2880         if (old_side_effects != new_side_effects)
2881           {
2882             error ("side effects not recomputed when ADDR_EXPR changed");
2883             return t;
2884           }
2885
2886         /* Skip any references (they will be checked when we recurse down the
2887            tree) and ensure that any variable used as a prefix is marked
2888            addressable.  */
2889         for (x = TREE_OPERAND (t, 0);
2890              handled_component_p (x);
2891              x = TREE_OPERAND (x, 0))
2892           ;
2893
2894         if (!(TREE_CODE (x) == VAR_DECL
2895               || TREE_CODE (x) == PARM_DECL
2896               || TREE_CODE (x) == RESULT_DECL))
2897           return NULL;
2898         if (!TREE_ADDRESSABLE (x))
2899           {
2900             error ("address taken, but ADDRESSABLE bit not set");
2901             return x;
2902           }
2903         if (DECL_GIMPLE_REG_P (x))
2904           {
2905             error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2906             return x;
2907           }
2908
2909         break;
2910       }
2911
2912     case COND_EXPR:
2913       x = COND_EXPR_COND (t);
2914       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2915         {
2916           error ("non-integral used in condition");
2917           return x;
2918         }
2919       if (!is_gimple_condexpr (x))
2920         {
2921           error ("invalid conditional operand");
2922           return x;
2923         }
2924       break;
2925
2926     case NON_LVALUE_EXPR:
2927         gcc_unreachable ();
2928
2929     CASE_CONVERT:
2930     case FIX_TRUNC_EXPR:
2931     case FLOAT_EXPR:
2932     case NEGATE_EXPR:
2933     case ABS_EXPR:
2934     case BIT_NOT_EXPR:
2935     case TRUTH_NOT_EXPR:
2936       CHECK_OP (0, "invalid operand to unary operator");
2937       break;
2938
2939     case REALPART_EXPR:
2940     case IMAGPART_EXPR:
2941     case COMPONENT_REF:
2942     case ARRAY_REF:
2943     case ARRAY_RANGE_REF:
2944     case BIT_FIELD_REF:
2945     case VIEW_CONVERT_EXPR:
2946       /* We have a nest of references.  Verify that each of the operands
2947          that determine where to reference is either a constant or a variable,
2948          verify that the base is valid, and then show we've already checked
2949          the subtrees.  */
2950       while (handled_component_p (t))
2951         {
2952           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2953             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2954           else if (TREE_CODE (t) == ARRAY_REF
2955                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2956             {
2957               CHECK_OP (1, "invalid array index");
2958               if (TREE_OPERAND (t, 2))
2959                 CHECK_OP (2, "invalid array lower bound");
2960               if (TREE_OPERAND (t, 3))
2961                 CHECK_OP (3, "invalid array stride");
2962             }
2963           else if (TREE_CODE (t) == BIT_FIELD_REF)
2964             {
2965               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2966                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2967                 {
2968                   error ("invalid position or size operand to BIT_FIELD_REF");
2969                   return t;
2970                 }
2971               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2972                        && (TYPE_PRECISION (TREE_TYPE (t))
2973                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2974                 {
2975                   error ("integral result type precision does not match "
2976                          "field size of BIT_FIELD_REF");
2977                   return t;
2978                 }
2979               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2980                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2981                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2982                 {
2983                   error ("mode precision of non-integral result does not "
2984                          "match field size of BIT_FIELD_REF");
2985                   return t;
2986                 }
2987             }
2988
2989           t = TREE_OPERAND (t, 0);
2990         }
2991
2992       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2993         {
2994           error ("invalid reference prefix");
2995           return t;
2996         }
2997       *walk_subtrees = 0;
2998       break;
2999     case PLUS_EXPR:
3000     case MINUS_EXPR:
3001       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3002          POINTER_PLUS_EXPR. */
3003       if (POINTER_TYPE_P (TREE_TYPE (t)))
3004         {
3005           error ("invalid operand to plus/minus, type is a pointer");
3006           return t;
3007         }
3008       CHECK_OP (0, "invalid operand to binary operator");
3009       CHECK_OP (1, "invalid operand to binary operator");
3010       break;
3011
3012     case POINTER_PLUS_EXPR:
3013       /* Check to make sure the first operand is a pointer or reference type. */
3014       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3015         {
3016           error ("invalid operand to pointer plus, first operand is not a pointer");
3017           return t;
3018         }
3019       /* Check to make sure the second operand is an integer with type of
3020          sizetype.  */
3021       if (!useless_type_conversion_p (sizetype,
3022                                      TREE_TYPE (TREE_OPERAND (t, 1))))
3023         {
3024           error ("invalid operand to pointer plus, second operand is not an "
3025                  "integer with type of sizetype.");
3026           return t;
3027         }
3028       /* FALLTHROUGH */
3029     case LT_EXPR:
3030     case LE_EXPR:
3031     case GT_EXPR:
3032     case GE_EXPR:
3033     case EQ_EXPR:
3034     case NE_EXPR:
3035     case UNORDERED_EXPR:
3036     case ORDERED_EXPR:
3037     case UNLT_EXPR:
3038     case UNLE_EXPR:
3039     case UNGT_EXPR:
3040     case UNGE_EXPR:
3041     case UNEQ_EXPR:
3042     case LTGT_EXPR:
3043     case MULT_EXPR:
3044     case TRUNC_DIV_EXPR:
3045     case CEIL_DIV_EXPR:
3046     case FLOOR_DIV_EXPR:
3047     case ROUND_DIV_EXPR:
3048     case TRUNC_MOD_EXPR:
3049     case CEIL_MOD_EXPR:
3050     case FLOOR_MOD_EXPR:
3051     case ROUND_MOD_EXPR:
3052     case RDIV_EXPR:
3053     case EXACT_DIV_EXPR:
3054     case MIN_EXPR:
3055     case MAX_EXPR:
3056     case LSHIFT_EXPR:
3057     case RSHIFT_EXPR:
3058     case LROTATE_EXPR:
3059     case RROTATE_EXPR:
3060     case BIT_IOR_EXPR:
3061     case BIT_XOR_EXPR:
3062     case BIT_AND_EXPR:
3063       CHECK_OP (0, "invalid operand to binary operator");
3064       CHECK_OP (1, "invalid operand to binary operator");
3065       break;
3066
3067     case CONSTRUCTOR:
3068       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3069         *walk_subtrees = 0;
3070       break;
3071
3072     default:
3073       break;
3074     }
3075   return NULL;
3076
3077 #undef CHECK_OP
3078 }
3079
3080
3081 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3082    Returns true if there is an error, otherwise false.  */
3083
3084 static bool
3085 verify_types_in_gimple_min_lval (tree expr)
3086 {
3087   tree op;
3088
3089   if (is_gimple_id (expr))
3090     return false;
3091
3092   if (!INDIRECT_REF_P (expr)
3093       && TREE_CODE (expr) != TARGET_MEM_REF)
3094     {
3095       error ("invalid expression for min lvalue");
3096       return true;
3097     }
3098
3099   /* TARGET_MEM_REFs are strange beasts.  */
3100   if (TREE_CODE (expr) == TARGET_MEM_REF)
3101     return false;
3102
3103   op = TREE_OPERAND (expr, 0);
3104   if (!is_gimple_val (op))
3105     {
3106       error ("invalid operand in indirect reference");
3107       debug_generic_stmt (op);
3108       return true;
3109     }
3110   if (!useless_type_conversion_p (TREE_TYPE (expr),
3111                                   TREE_TYPE (TREE_TYPE (op))))
3112     {
3113       error ("type mismatch in indirect reference");
3114       debug_generic_stmt (TREE_TYPE (expr));
3115       debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3116       return true;
3117     }
3118
3119   return false;
3120 }
3121
3122 /* Verify if EXPR is a valid GIMPLE reference expression.  If
3123    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
3124    if there is an error, otherwise false.  */
3125
3126 static bool
3127 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
3128 {
3129   while (handled_component_p (expr))
3130     {
3131       tree op = TREE_OPERAND (expr, 0);
3132
3133       if (TREE_CODE (expr) == ARRAY_REF
3134           || TREE_CODE (expr) == ARRAY_RANGE_REF)
3135         {
3136           if (!is_gimple_val (TREE_OPERAND (expr, 1))
3137               || (TREE_OPERAND (expr, 2)
3138                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
3139               || (TREE_OPERAND (expr, 3)
3140                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
3141             {
3142               error ("invalid operands to array reference");
3143               debug_generic_stmt (expr);
3144               return true;
3145             }
3146         }
3147
3148       /* Verify if the reference array element types are compatible.  */
3149       if (TREE_CODE (expr) == ARRAY_REF
3150           && !useless_type_conversion_p (TREE_TYPE (expr),
3151                                          TREE_TYPE (TREE_TYPE (op))))
3152         {
3153           error ("type mismatch in array reference");
3154           debug_generic_stmt (TREE_TYPE (expr));
3155           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3156           return true;
3157         }
3158       if (TREE_CODE (expr) == ARRAY_RANGE_REF
3159           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3160                                          TREE_TYPE (TREE_TYPE (op))))
3161         {
3162           error ("type mismatch in array range reference");
3163           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3164           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3165           return true;
3166         }
3167
3168       if ((TREE_CODE (expr) == REALPART_EXPR
3169            || TREE_CODE (expr) == IMAGPART_EXPR)
3170           && !useless_type_conversion_p (TREE_TYPE (expr),
3171                                          TREE_TYPE (TREE_TYPE (op))))
3172         {
3173           error ("type mismatch in real/imagpart reference");
3174           debug_generic_stmt (TREE_TYPE (expr));
3175           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3176           return true;
3177         }
3178
3179       if (TREE_CODE (expr) == COMPONENT_REF
3180           && !useless_type_conversion_p (TREE_TYPE (expr),
3181                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3182         {
3183           error ("type mismatch in component reference");
3184           debug_generic_stmt (TREE_TYPE (expr));
3185           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3186           return true;
3187         }
3188
3189       /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3190          is nothing to verify.  Gross mismatches at most invoke
3191          undefined behavior.  */
3192       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR
3193           && !handled_component_p (op))
3194         return false;
3195
3196       expr = op;
3197     }
3198
3199   return ((require_lvalue || !is_gimple_min_invariant (expr))
3200           && verify_types_in_gimple_min_lval (expr));
3201 }
3202
3203 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3204    list of pointer-to types that is trivially convertible to DEST.  */
3205
3206 static bool
3207 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3208 {
3209   tree src;
3210
3211   if (!TYPE_POINTER_TO (src_obj))
3212     return true;
3213
3214   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3215     if (useless_type_conversion_p (dest, src))
3216       return true;
3217
3218   return false;
3219 }
3220
3221 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3222    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3223
3224 static bool
3225 valid_fixed_convert_types_p (tree type1, tree type2)
3226 {
3227   return (FIXED_POINT_TYPE_P (type1)
3228           && (INTEGRAL_TYPE_P (type2)
3229               || SCALAR_FLOAT_TYPE_P (type2)
3230               || FIXED_POINT_TYPE_P (type2)));
3231 }
3232
3233 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3234    is a problem, otherwise false.  */
3235
3236 static bool
3237 verify_gimple_call (gimple stmt)
3238 {
3239   tree fn = gimple_call_fn (stmt);
3240   tree fntype;
3241
3242   if (!POINTER_TYPE_P (TREE_TYPE  (fn))
3243       || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3244           && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE))
3245     {
3246       error ("non-function in gimple call");
3247       return true;
3248     }
3249
3250   if (gimple_call_lhs (stmt)
3251       && !is_gimple_lvalue (gimple_call_lhs (stmt)))
3252     {
3253       error ("invalid LHS in gimple call");
3254       return true;
3255     }
3256
3257   fntype = TREE_TYPE (TREE_TYPE (fn));
3258   if (gimple_call_lhs (stmt)
3259       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3260                                      TREE_TYPE (fntype))
3261       /* ???  At least C++ misses conversions at assignments from
3262          void * call results.
3263          ???  Java is completely off.  Especially with functions
3264          returning java.lang.Object.
3265          For now simply allow arbitrary pointer type conversions.  */
3266       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3267            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3268     {
3269       error ("invalid conversion in gimple call");
3270       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3271       debug_generic_stmt (TREE_TYPE (fntype));
3272       return true;
3273     }
3274
3275   /* ???  The C frontend passes unpromoted arguments in case it
3276      didn't see a function declaration before the call.  So for now
3277      leave the call arguments unverified.  Once we gimplify
3278      unit-at-a-time we have a chance to fix this.  */
3279
3280   return false;
3281 }
3282
3283 /* Verifies the gimple comparison with the result type TYPE and
3284    the operands OP0 and OP1.  */
3285
3286 static bool
3287 verify_gimple_comparison (tree type, tree op0, tree op1)
3288 {
3289   tree op0_type = TREE_TYPE (op0);
3290   tree op1_type = TREE_TYPE (op1);
3291
3292   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3293     {
3294       error ("invalid operands in gimple comparison");
3295       return true;
3296     }
3297
3298   /* For comparisons we do not have the operations type as the
3299      effective type the comparison is carried out in.  Instead
3300      we require that either the first operand is trivially
3301      convertible into the second, or the other way around.
3302      The resulting type of a comparison may be any integral type.
3303      Because we special-case pointers to void we allow
3304      comparisons of pointers with the same mode as well.  */
3305   if ((!useless_type_conversion_p (op0_type, op1_type)
3306        && !useless_type_conversion_p (op1_type, op0_type)
3307        && (!POINTER_TYPE_P (op0_type)
3308            || !POINTER_TYPE_P (op1_type)
3309            || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3310       || !INTEGRAL_TYPE_P (type))
3311     {
3312       error ("type mismatch in comparison expression");
3313       debug_generic_expr (type);
3314       debug_generic_expr (op0_type);
3315       debug_generic_expr (op1_type);
3316       return true;
3317     }
3318
3319   return false;
3320 }
3321
3322 /* Verify a gimple assignment statement STMT with an unary rhs.
3323    Returns true if anything is wrong.  */
3324
3325 static bool
3326 verify_gimple_assign_unary (gimple stmt)
3327 {
3328   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3329   tree lhs = gimple_assign_lhs (stmt);
3330   tree lhs_type = TREE_TYPE (lhs);
3331   tree rhs1 = gimple_assign_rhs1 (stmt);
3332   tree rhs1_type = TREE_TYPE (rhs1);
3333
3334   if (!is_gimple_reg (lhs)
3335       && !(optimize == 0
3336            && TREE_CODE (lhs_type) == COMPLEX_TYPE))
3337     {
3338       error ("non-register as LHS of unary operation");
3339       return true;
3340     }
3341
3342   if (!is_gimple_val (rhs1))
3343     {
3344       error ("invalid operand in unary operation");
3345       return true;
3346     }
3347
3348   /* First handle conversions.  */
3349   switch (rhs_code)
3350     {
3351     CASE_CONVERT:
3352       {
3353         /* Allow conversions between integral types and pointers only if
3354            there is no sign or zero extension involved.
3355            For targets were the precision of sizetype doesn't match that
3356            of pointers we need to allow arbitrary conversions from and
3357            to sizetype.  */
3358         if ((POINTER_TYPE_P (lhs_type)
3359              && INTEGRAL_TYPE_P (rhs1_type)
3360              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3361                  || rhs1_type == sizetype))
3362             || (POINTER_TYPE_P (rhs1_type)
3363                 && INTEGRAL_TYPE_P (lhs_type)
3364                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3365                     || lhs_type == sizetype)))
3366           return false;
3367
3368         /* Allow conversion from integer to offset type and vice versa.  */
3369         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3370              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3371             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3372                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3373           return false;
3374
3375         /* Otherwise assert we are converting between types of the
3376            same kind.  */
3377         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3378           {
3379             error ("invalid types in nop conversion");
3380             debug_generic_expr (lhs_type);
3381             debug_generic_expr (rhs1_type);
3382             return true;
3383           }
3384
3385         return false;
3386       }
3387
3388     case FIXED_CONVERT_EXPR:
3389       {
3390         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3391             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3392           {
3393             error ("invalid types in fixed-point conversion");
3394             debug_generic_expr (lhs_type);
3395             debug_generic_expr (rhs1_type);
3396             return true;
3397           }
3398
3399         return false;
3400       }
3401
3402     case FLOAT_EXPR:
3403       {
3404         if (!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3405           {
3406             error ("invalid types in conversion to floating point");
3407             debug_generic_expr (lhs_type);
3408             debug_generic_expr (rhs1_type);
3409             return true;
3410           }
3411
3412         return false;
3413       }
3414
3415     case FIX_TRUNC_EXPR:
3416       {
3417         if (!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3418           {
3419             error ("invalid types in conversion to integer");
3420             debug_generic_expr (lhs_type);
3421             debug_generic_expr (rhs1_type);
3422             return true;
3423           }
3424
3425         return false;
3426       }
3427
3428     case VEC_UNPACK_HI_EXPR:
3429     case VEC_UNPACK_LO_EXPR:
3430     case REDUC_MAX_EXPR:
3431     case REDUC_MIN_EXPR:
3432     case REDUC_PLUS_EXPR:
3433     case VEC_UNPACK_FLOAT_HI_EXPR:
3434     case VEC_UNPACK_FLOAT_LO_EXPR:
3435       /* FIXME.  */
3436       return false;
3437
3438     case TRUTH_NOT_EXPR:
3439     case NEGATE_EXPR:
3440     case ABS_EXPR:
3441     case BIT_NOT_EXPR:
3442     case PAREN_EXPR:
3443     case NON_LVALUE_EXPR:
3444     case CONJ_EXPR:
3445       break;
3446
3447     default:
3448       gcc_unreachable ();
3449     }
3450
3451   /* For the remaining codes assert there is no conversion involved.  */
3452   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3453     {
3454       error ("non-trivial conversion in unary operation");
3455       debug_generic_expr (lhs_type);
3456       debug_generic_expr (rhs1_type);
3457       return true;
3458     }
3459
3460   return false;
3461 }
3462
3463 /* Verify a gimple assignment statement STMT with a binary rhs.
3464    Returns true if anything is wrong.  */
3465
3466 static bool
3467 verify_gimple_assign_binary (gimple stmt)
3468 {
3469   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3470   tree lhs = gimple_assign_lhs (stmt);
3471   tree lhs_type = TREE_TYPE (lhs);
3472   tree rhs1 = gimple_assign_rhs1 (stmt);
3473   tree rhs1_type = TREE_TYPE (rhs1);
3474   tree rhs2 = gimple_assign_rhs2 (stmt);
3475   tree rhs2_type = TREE_TYPE (rhs2);
3476
3477   if (!is_gimple_reg (lhs)
3478       && !(optimize == 0
3479            && TREE_CODE (lhs_type) == COMPLEX_TYPE))
3480     {
3481       error ("non-register as LHS of binary operation");
3482       return true;
3483     }
3484
3485   if (!is_gimple_val (rhs1)
3486       || !is_gimple_val (rhs2))
3487     {
3488       error ("invalid operands in binary operation");
3489       return true;
3490     }
3491
3492   /* First handle operations that involve different types.  */
3493   switch (rhs_code)
3494     {
3495     case COMPLEX_EXPR:
3496       {
3497         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3498             || !(INTEGRAL_TYPE_P (rhs1_type)
3499                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3500             || !(INTEGRAL_TYPE_P (rhs2_type)
3501                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3502           {
3503             error ("type mismatch in complex expression");
3504             debug_generic_expr (lhs_type);
3505             debug_generic_expr (rhs1_type);
3506             debug_generic_expr (rhs2_type);
3507             return true;
3508           }
3509
3510         return false;
3511       }
3512
3513     case LSHIFT_EXPR:
3514     case RSHIFT_EXPR:
3515     case LROTATE_EXPR:
3516     case RROTATE_EXPR:
3517       {
3518         /* Shifts and rotates are ok on integral types, fixed point
3519            types and integer vector types.  */
3520         if ((!INTEGRAL_TYPE_P (rhs1_type)
3521              && !FIXED_POINT_TYPE_P (rhs1_type)
3522              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3523                   && TREE_CODE (TREE_TYPE (rhs1_type)) == INTEGER_TYPE))
3524             || (!INTEGRAL_TYPE_P (rhs2_type)
3525                 /* Vector shifts of vectors are also ok.  */
3526                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3527                      && TREE_CODE (TREE_TYPE (rhs1_type)) == INTEGER_TYPE
3528                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3529                      && TREE_CODE (TREE_TYPE (rhs2_type)) == INTEGER_TYPE))
3530             || !useless_type_conversion_p (lhs_type, rhs1_type))
3531           {
3532             error ("type mismatch in shift expression");
3533             debug_generic_expr (lhs_type);
3534             debug_generic_expr (rhs1_type);
3535             debug_generic_expr (rhs2_type);
3536             return true;
3537           }
3538
3539         return false;
3540       }
3541
3542     case VEC_LSHIFT_EXPR:
3543     case VEC_RSHIFT_EXPR:
3544       {
3545         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3546             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3547                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3548                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3549             || (!INTEGRAL_TYPE_P (rhs2_type)
3550                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3551                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3552             || !useless_type_conversion_p (lhs_type, rhs1_type))
3553           {
3554             error ("type mismatch in vector shift expression");
3555             debug_generic_expr (lhs_type);
3556             debug_generic_expr (rhs1_type);
3557             debug_generic_expr (rhs2_type);
3558             return true;
3559           }
3560         /* For shifting a vector of floating point components we
3561            only allow shifting by a constant multiple of the element size.  */
3562         if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type))
3563             && (TREE_CODE (rhs2) != INTEGER_CST
3564                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3565                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3566           {
3567             error ("non-element sized vector shift of floating point vector");
3568             return true;
3569           }
3570
3571         return false;
3572       }
3573
3574     case PLUS_EXPR:
3575       {
3576         /* We use regular PLUS_EXPR for vectors.
3577            ???  This just makes the checker happy and may not be what is
3578            intended.  */
3579         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3580             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3581           {
3582             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3583                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3584               {
3585                 error ("invalid non-vector operands to vector valued plus");
3586                 return true;
3587               }
3588             lhs_type = TREE_TYPE (lhs_type);
3589             rhs1_type = TREE_TYPE (rhs1_type);
3590             rhs2_type = TREE_TYPE (rhs2_type);
3591             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3592                the pointer to 2nd place.  */
3593             if (POINTER_TYPE_P (rhs2_type))
3594               {
3595                 tree tem = rhs1_type;
3596                 rhs1_type = rhs2_type;
3597                 rhs2_type = tem;
3598               }
3599             goto do_pointer_plus_expr_check;
3600           }
3601       }
3602     /* Fallthru.  */
3603     case MINUS_EXPR:
3604       {
3605         if (POINTER_TYPE_P (lhs_type)
3606             || POINTER_TYPE_P (rhs1_type)
3607             || POINTER_TYPE_P (rhs2_type))
3608           {
3609             error ("invalid (pointer) operands to plus/minus");
3610             return true;
3611           }
3612
3613         /* Continue with generic binary expression handling.  */
3614         break;
3615       }
3616
3617     case POINTER_PLUS_EXPR:
3618       {
3619 do_pointer_plus_expr_check:
3620         if (!POINTER_TYPE_P (rhs1_type)
3621             || !useless_type_conversion_p (lhs_type, rhs1_type)
3622             || !useless_type_conversion_p (sizetype, rhs2_type))
3623           {
3624             error ("type mismatch in pointer plus expression");
3625             debug_generic_stmt (lhs_type);
3626             debug_generic_stmt (rhs1_type);
3627             debug_generic_stmt (rhs2_type);
3628             return true;
3629           }
3630
3631         return false;
3632       } 
3633
3634     case TRUTH_ANDIF_EXPR:
3635     case TRUTH_ORIF_EXPR:
3636       gcc_unreachable ();
3637
3638     case TRUTH_AND_EXPR:
3639     case TRUTH_OR_EXPR:
3640     case TRUTH_XOR_EXPR:
3641       {
3642         /* We allow any kind of integral typed argument and result.  */
3643         if (!INTEGRAL_TYPE_P (rhs1_type)
3644             || !INTEGRAL_TYPE_P (rhs2_type)
3645             || !INTEGRAL_TYPE_P (lhs_type))
3646           {
3647             error ("type mismatch in binary truth expression");
3648             debug_generic_expr (lhs_type);
3649             debug_generic_expr (rhs1_type);
3650             debug_generic_expr (rhs2_type);
3651             return true;
3652           }
3653
3654         return false;
3655       }
3656
3657     case LT_EXPR:
3658     case LE_EXPR:
3659     case GT_EXPR:
3660     case GE_EXPR:
3661     case EQ_EXPR:
3662     case NE_EXPR:
3663     case UNORDERED_EXPR:
3664     case ORDERED_EXPR:
3665     case UNLT_EXPR:
3666     case UNLE_EXPR:
3667     case UNGT_EXPR:
3668     case UNGE_EXPR:
3669     case UNEQ_EXPR:
3670     case LTGT_EXPR:
3671       /* Comparisons are also binary, but the result type is not
3672          connected to the operand types.  */
3673       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3674
3675     case WIDEN_SUM_EXPR:
3676     case WIDEN_MULT_EXPR:
3677     case VEC_WIDEN_MULT_HI_EXPR:
3678     case VEC_WIDEN_MULT_LO_EXPR:
3679     case VEC_PACK_TRUNC_EXPR:
3680     case VEC_PACK_SAT_EXPR:
3681     case VEC_PACK_FIX_TRUNC_EXPR:
3682     case VEC_EXTRACT_EVEN_EXPR:
3683     case VEC_EXTRACT_ODD_EXPR:
3684     case VEC_INTERLEAVE_HIGH_EXPR:
3685     case VEC_INTERLEAVE_LOW_EXPR:
3686       /* FIXME.  */
3687       return false;
3688
3689     case MULT_EXPR:
3690     case TRUNC_DIV_EXPR:
3691     case CEIL_DIV_EXPR:
3692     case FLOOR_DIV_EXPR:
3693     case ROUND_DIV_EXPR:
3694     case TRUNC_MOD_EXPR:
3695     case CEIL_MOD_EXPR:
3696     case FLOOR_MOD_EXPR:
3697     case ROUND_MOD_EXPR:
3698     case RDIV_EXPR:
3699     case EXACT_DIV_EXPR:
3700     case MIN_EXPR:
3701     case MAX_EXPR:
3702     case BIT_IOR_EXPR:
3703     case BIT_XOR_EXPR:
3704     case BIT_AND_EXPR:
3705       /* Continue with generic binary expression handling.  */
3706       break;
3707
3708     default:
3709       gcc_unreachable ();
3710     }
3711
3712   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3713       || !useless_type_conversion_p (lhs_type, rhs2_type))
3714     {
3715       error ("type mismatch in binary expression");
3716       debug_generic_stmt (lhs_type);
3717       debug_generic_stmt (rhs1_type);
3718       debug_generic_stmt (rhs2_type);
3719       return true;
3720     }
3721
3722   return false;
3723 }
3724
3725 /* Verify a gimple assignment statement STMT with a single rhs.
3726    Returns true if anything is wrong.  */
3727
3728 static bool
3729 verify_gimple_assign_single (gimple stmt)
3730 {
3731   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3732   tree lhs = gimple_assign_lhs (stmt);
3733   tree lhs_type = TREE_TYPE (lhs);
3734   tree rhs1 = gimple_assign_rhs1 (stmt);
3735   tree rhs1_type = TREE_TYPE (rhs1);
3736   bool res = false;
3737
3738   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3739     {
3740       error ("non-trivial conversion at assignment");
3741       debug_generic_expr (lhs_type);
3742       debug_generic_expr (rhs1_type);
3743       return true;
3744     }
3745
3746   if (handled_component_p (lhs))
3747     res |= verify_types_in_gimple_reference (lhs, true);
3748
3749   /* Special codes we cannot handle via their class.  */
3750   switch (rhs_code)
3751     {
3752     case ADDR_EXPR:
3753       {
3754         tree op = TREE_OPERAND (rhs1, 0);
3755         if (!is_gimple_addressable (op))
3756           {
3757             error ("invalid operand in unary expression");
3758             return true;
3759           }
3760
3761         if (!one_pointer_to_useless_type_conversion_p (lhs_type,
3762                                                        TREE_TYPE (op)))
3763           {
3764             error ("type mismatch in address expression");
3765             debug_generic_stmt (lhs_type);
3766             debug_generic_stmt (TYPE_POINTER_TO (TREE_TYPE (op)));
3767             return true;
3768           }
3769
3770         return verify_types_in_gimple_reference (op, true);
3771       }
3772
3773     /* tcc_reference  */
3774     case COMPONENT_REF:
3775     case BIT_FIELD_REF:
3776     case INDIRECT_REF:
3777     case ALIGN_INDIRECT_REF:
3778     case MISALIGNED_INDIRECT_REF:
3779     case ARRAY_REF:
3780     case ARRAY_RANGE_REF:
3781     case VIEW_CONVERT_EXPR:
3782     case REALPART_EXPR:
3783     case IMAGPART_EXPR:
3784     case TARGET_MEM_REF:
3785       if (!is_gimple_reg (lhs)
3786           && is_gimple_reg_type (TREE_TYPE (lhs)))
3787         {
3788           error ("invalid rhs for gimple memory store");
3789           debug_generic_stmt (lhs);
3790           debug_generic_stmt (rhs1);
3791           return true;
3792         }
3793       return res || verify_types_in_gimple_reference (rhs1, false);
3794
3795     /* tcc_constant  */
3796     case SSA_NAME:
3797     case INTEGER_CST:
3798     case REAL_CST:
3799     case FIXED_CST:
3800     case COMPLEX_CST:
3801     case VECTOR_CST:
3802     case STRING_CST:
3803       return res;
3804
3805     /* tcc_declaration  */
3806     case CONST_DECL:
3807       return res;
3808     case VAR_DECL:
3809     case PARM_DECL:
3810       if (!is_gimple_reg (lhs)
3811           && !is_gimple_reg (rhs1)
3812           && is_gimple_reg_type (TREE_TYPE (lhs)))
3813         {
3814           error ("invalid rhs for gimple memory store");
3815           debug_generic_stmt (lhs);
3816           debug_generic_stmt (rhs1);
3817           return true;
3818         }
3819       return res;
3820
3821     case COND_EXPR:
3822     case CONSTRUCTOR:
3823     case OBJ_TYPE_REF:
3824     case ASSERT_EXPR:
3825     case WITH_SIZE_EXPR:
3826     case EXC_PTR_EXPR:
3827     case FILTER_EXPR:
3828     case POLYNOMIAL_CHREC:
3829     case DOT_PROD_EXPR:
3830     case VEC_COND_EXPR:
3831     case REALIGN_LOAD_EXPR:
3832       /* FIXME.  */
3833       return res;
3834
3835     default:;
3836     }
3837
3838   return res;
3839 }
3840
3841 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
3842    is a problem, otherwise false.  */
3843
3844 static bool
3845 verify_gimple_assign (gimple stmt)
3846 {
3847   switch (gimple_assign_rhs_class (stmt))
3848     {
3849     case GIMPLE_SINGLE_RHS:
3850       return verify_gimple_assign_single (stmt);
3851
3852     case GIMPLE_UNARY_RHS:
3853       return verify_gimple_assign_unary (stmt);
3854
3855     case GIMPLE_BINARY_RHS:
3856       return verify_gimple_assign_binary (stmt);
3857
3858     default:
3859       gcc_unreachable ();
3860     }
3861 }
3862
3863 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
3864    is a problem, otherwise false.  */
3865
3866 static bool
3867 verify_gimple_return (gimple stmt)
3868 {
3869   tree op = gimple_return_retval (stmt);
3870   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
3871
3872   /* We cannot test for present return values as we do not fix up missing
3873      return values from the original source.  */
3874   if (op == NULL)
3875     return false;
3876  
3877   if (!is_gimple_val (op)
3878       && TREE_CODE (op) != RESULT_DECL)
3879     {
3880       error ("invalid operand in return statement");
3881       debug_generic_stmt (op);
3882       return true;
3883     }
3884
3885   if (!useless_type_conversion_p (restype, TREE_TYPE (op))
3886       /* ???  With C++ we can have the situation that the result
3887          decl is a reference type while the return type is an aggregate.  */
3888       && !(TREE_CODE (op) == RESULT_DECL
3889            && TREE_CODE (TREE_TYPE (op)) == REFERENCE_TYPE
3890            && useless_type_conversion_p (restype, TREE_TYPE (TREE_TYPE (op)))))
3891     {
3892       error ("invalid conversion in return statement");
3893       debug_generic_stmt (restype);
3894       debug_generic_stmt (TREE_TYPE (op));
3895       return true;
3896     }
3897
3898   return false;
3899 }
3900
3901
3902 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
3903    is a problem, otherwise false.  */
3904
3905 static bool
3906 verify_gimple_goto (gimple stmt)
3907 {
3908   tree dest = gimple_goto_dest (stmt);
3909
3910   /* ???  We have two canonical forms of direct goto destinations, a
3911      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
3912   if (TREE_CODE (dest) != LABEL_DECL
3913       && (!is_gimple_val (dest)
3914           || !POINTER_TYPE_P (TREE_TYPE (dest))))
3915     {
3916       error ("goto destination is neither a label nor a pointer");
3917       return true;
3918     }
3919
3920   return false;
3921 }
3922
3923 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
3924    is a problem, otherwise false.  */
3925
3926 static bool
3927 verify_gimple_switch (gimple stmt)
3928 {
3929   if (!is_gimple_val (gimple_switch_index (stmt)))
3930     {
3931       error ("invalid operand to switch statement");
3932       debug_generic_stmt (gimple_switch_index (stmt));
3933       return true;
3934     }
3935
3936   return false;
3937 }
3938
3939
3940 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
3941    and false otherwise.  */
3942
3943 static bool
3944 verify_gimple_phi (gimple stmt)
3945 {
3946   tree type = TREE_TYPE (gimple_phi_result (stmt));
3947   unsigned i;
3948
3949   if (!is_gimple_variable (gimple_phi_result (stmt)))
3950     {
3951       error ("Invalid PHI result");
3952       return true;
3953     }
3954
3955   for (i = 0; i < gimple_phi_num_args (stmt); i++)
3956     {
3957       tree arg = gimple_phi_arg_def (stmt, i);
3958       if ((is_gimple_reg (gimple_phi_result (stmt))
3959            && !is_gimple_val (arg))
3960           || (!is_gimple_reg (gimple_phi_result (stmt))
3961               && !is_gimple_addressable (arg)))
3962         {
3963           error ("Invalid PHI argument");
3964           debug_generic_stmt (arg);
3965           return true;
3966         }
3967       if (!useless_type_conversion_p (type, TREE_TYPE (arg)))
3968         {
3969           error ("Incompatible types in PHI argument %u", i);
3970           debug_generic_stmt (type);
3971           debug_generic_stmt (TREE_TYPE (arg));
3972           return true;
3973         }
3974     }
3975
3976   return false;
3977 }
3978
3979
3980 /* Verify the GIMPLE statement STMT.  Returns true if there is an
3981    error, otherwise false.  */
3982
3983 static bool
3984 verify_types_in_gimple_stmt (gimple stmt)
3985 {
3986   if (is_gimple_omp (stmt))
3987     {
3988       /* OpenMP directives are validated by the FE and never operated
3989          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
3990          non-gimple expressions when the main index variable has had
3991          its address taken.  This does not affect the loop itself
3992          because the header of an GIMPLE_OMP_FOR is merely used to determine
3993          how to setup the parallel iteration.  */
3994       return false;
3995     }
3996
3997   switch (gimple_code (stmt))
3998     {
3999     case GIMPLE_ASSIGN:
4000       return verify_gimple_assign (stmt);
4001
4002     case GIMPLE_LABEL:
4003       return TREE_CODE (gimple_label_label (stmt)) != LABEL_DECL;
4004
4005     case GIMPLE_CALL:
4006       return verify_gimple_call (stmt);
4007
4008     case GIMPLE_COND:
4009       return verify_gimple_comparison (boolean_type_node,
4010                                        gimple_cond_lhs (stmt),
4011                                        gimple_cond_rhs (stmt));
4012
4013     case GIMPLE_GOTO:
4014       return verify_gimple_goto (stmt);
4015
4016     case GIMPLE_SWITCH:
4017       return verify_gimple_switch (stmt);
4018
4019     case GIMPLE_RETURN:
4020       return verify_gimple_return (stmt);
4021
4022     case GIMPLE_ASM:
4023       return false;
4024
4025     case GIMPLE_PHI:
4026       return verify_gimple_phi (stmt);
4027
4028     /* Tuples that do not have tree operands.  */
4029     case GIMPLE_NOP:
4030     case GIMPLE_RESX:
4031     case GIMPLE_PREDICT:
4032       return false;
4033
4034     default:
4035       gcc_unreachable ();
4036     }
4037 }
4038
4039 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4040
4041 static bool
4042 verify_types_in_gimple_seq_2 (gimple_seq stmts)
4043 {
4044   gimple_stmt_iterator ittr;
4045   bool err = false;
4046
4047   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4048     {
4049       gimple stmt = gsi_stmt (ittr);
4050
4051       switch (gimple_code (stmt))
4052         {
4053         case GIMPLE_BIND:
4054           err |= verify_types_in_gimple_seq_2 (gimple_bind_body (stmt));
4055           break;
4056
4057         case GIMPLE_TRY:
4058           err |= verify_types_in_gimple_seq_2 (gimple_try_eval (stmt));
4059           err |= verify_types_in_gimple_seq_2 (gimple_try_cleanup (stmt));
4060           break;
4061
4062         case GIMPLE_EH_FILTER:
4063           err |= verify_types_in_gimple_seq_2 (gimple_eh_filter_failure (stmt));
4064           break;
4065
4066         case GIMPLE_CATCH:
4067           err |= verify_types_in_gimple_seq_2 (gimple_catch_handler (stmt));
4068           break;
4069
4070         default:
4071           {
4072             bool err2 = verify_types_in_gimple_stmt (stmt);
4073             if (err2)
4074               debug_gimple_stmt (stmt);
4075             err |= err2;
4076           }
4077         }
4078     }
4079
4080   return err;
4081 }
4082
4083
4084 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4085
4086 void
4087 verify_types_in_gimple_seq (gimple_seq stmts)
4088 {
4089   if (verify_types_in_gimple_seq_2 (stmts))
4090     internal_error ("verify_gimple failed");
4091 }
4092
4093
4094 /* Verify STMT, return true if STMT is not in GIMPLE form.
4095    TODO: Implement type checking.  */
4096
4097 static bool
4098 verify_stmt (gimple_stmt_iterator *gsi)
4099 {
4100   tree addr;
4101   struct walk_stmt_info wi;
4102   bool last_in_block = gsi_one_before_end_p (*gsi);
4103   gimple stmt = gsi_stmt (*gsi);
4104
4105   if (is_gimple_omp (stmt))
4106     {
4107       /* OpenMP directives are validated by the FE and never operated
4108          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4109          non-gimple expressions when the main index variable has had
4110          its address taken.  This does not affect the loop itself
4111          because the header of an GIMPLE_OMP_FOR is merely used to determine
4112          how to setup the parallel iteration.  */
4113       return false;
4114     }
4115
4116   /* FIXME.  The C frontend passes unpromoted arguments in case it
4117      didn't see a function declaration before the call.  */
4118   if (is_gimple_call (stmt))
4119     {
4120       tree decl;
4121
4122       if (!is_gimple_call_addr (gimple_call_fn (stmt)))
4123         {
4124           error ("invalid function in call statement");
4125           return true;
4126         }
4127
4128       decl = gimple_call_fndecl (stmt);
4129       if (decl
4130           && TREE_CODE (decl) == FUNCTION_DECL
4131           && DECL_LOOPING_CONST_OR_PURE_P (decl)
4132           && (!DECL_PURE_P (decl))
4133           && (!TREE_READONLY (decl)))
4134         {
4135           error ("invalid pure const state for function");
4136           return true;
4137         }
4138     }
4139
4140   memset (&wi, 0, sizeof (wi));
4141   addr = walk_gimple_op (gsi_stmt (*gsi), verify_expr, &wi);
4142   if (addr)
4143     {
4144       debug_generic_expr (addr);
4145       inform (input_location, "in statement");
4146       debug_gimple_stmt (stmt);
4147       return true;
4148     }
4149
4150   /* If the statement is marked as part of an EH region, then it is
4151      expected that the statement could throw.  Verify that when we
4152      have optimizations that simplify statements such that we prove
4153      that they cannot throw, that we update other data structures
4154      to match.  */
4155   if (lookup_stmt_eh_region (stmt) >= 0)
4156     {
4157       /* During IPA passes, ipa-pure-const sets nothrow flags on calls
4158          and they are updated on statements only after fixup_cfg
4159          is executed at beggining of expansion stage.  */
4160       if (!stmt_could_throw_p (stmt) && cgraph_state != CGRAPH_STATE_IPA_SSA)
4161         {
4162           error ("statement marked for throw, but doesn%'t");
4163           goto fail;
4164         }
4165       if (!last_in_block && stmt_can_throw_internal (stmt))
4166         {
4167           error ("statement marked for throw in middle of block");
4168           goto fail;
4169         }
4170     }
4171
4172   return false;
4173
4174  fail:
4175   debug_gimple_stmt (stmt);
4176   return true;
4177 }
4178
4179
4180 /* Return true when the T can be shared.  */
4181
4182 static bool
4183 tree_node_can_be_shared (tree t)
4184 {
4185   if (IS_TYPE_OR_DECL_P (t)
4186       || is_gimple_min_invariant (t)
4187       || TREE_CODE (t) == SSA_NAME
4188       || t == error_mark_node
4189       || TREE_CODE (t) == IDENTIFIER_NODE)
4190     return true;
4191
4192   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4193     return true;
4194
4195   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4196            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4197          || TREE_CODE (t) == COMPONENT_REF
4198          || TREE_CODE (t) == REALPART_EXPR
4199          || TREE_CODE (t) == IMAGPART_EXPR)
4200     t = TREE_OPERAND (t, 0);
4201
4202   if (DECL_P (t))
4203     return true;
4204
4205   return false;
4206 }
4207
4208
4209 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4210
4211 static tree
4212 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4213 {
4214   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4215   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4216
4217   if (tree_node_can_be_shared (*tp))
4218     {
4219       *walk_subtrees = false;
4220       return NULL;
4221     }
4222
4223   if (pointer_set_insert (visited, *tp))
4224     return *tp;
4225
4226   return NULL;
4227 }
4228
4229
4230 static bool eh_error_found;
4231 static int
4232 verify_eh_throw_stmt_node (void **slot, void *data)
4233 {
4234   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4235   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4236
4237   if (!pointer_set_contains (visited, node->stmt))
4238     {
4239       error ("Dead STMT in EH table");
4240       debug_gimple_stmt (node->stmt);
4241       eh_error_found = true;
4242     }
4243   return 1;
4244 }
4245
4246
4247 /* Verify the GIMPLE statements in every basic block.  */
4248
4249 void
4250 verify_stmts (void)
4251 {
4252   basic_block bb;
4253   gimple_stmt_iterator gsi;
4254   bool err = false;
4255   struct pointer_set_t *visited, *visited_stmts;
4256   tree addr;
4257   struct walk_stmt_info wi;
4258
4259   timevar_push (TV_TREE_STMT_VERIFY);
4260   visited = pointer_set_create ();
4261   visited_stmts = pointer_set_create ();
4262
4263   memset (&wi, 0, sizeof (wi));
4264   wi.info = (void *) visited;
4265
4266   FOR_EACH_BB (bb)
4267     {
4268       gimple phi;
4269       size_t i;
4270
4271       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4272         {
4273           phi = gsi_stmt (gsi);
4274           pointer_set_insert (visited_stmts, phi);
4275           if (gimple_bb (phi) != bb)
4276             {
4277               error ("gimple_bb (phi) is set to a wrong basic block");
4278               err |= true;
4279             }
4280
4281           for (i = 0; i < gimple_phi_num_args (phi); i++)
4282             {
4283               tree t = gimple_phi_arg_def (phi, i);
4284               tree addr;
4285
4286               if (!t)
4287                 {
4288                   error ("missing PHI def");
4289                   debug_gimple_stmt (phi);