OSDN Git Service

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