OSDN Git Service

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