OSDN Git Service

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