OSDN Git Service

PR tree-optimization/51596
[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  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 between integral types and pointers 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 from and
3347            to ptrofftype.  */
3348         if ((POINTER_TYPE_P (lhs_type)
3349              && INTEGRAL_TYPE_P (rhs1_type)
3350              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3351                  || ptrofftype_p (rhs1_type)))
3352             || (POINTER_TYPE_P (rhs1_type)
3353                 && INTEGRAL_TYPE_P (lhs_type)
3354                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3355                     || ptrofftype_p (sizetype))))
3356           return false;
3357
3358         /* Allow conversion from integer to offset type and vice versa.  */
3359         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3360              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3361             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3362                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3363           return false;
3364
3365         /* Otherwise assert we are converting between types of the
3366            same kind.  */
3367         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3368           {
3369             error ("invalid types in nop conversion");
3370             debug_generic_expr (lhs_type);
3371             debug_generic_expr (rhs1_type);
3372             return true;
3373           }
3374
3375         return false;
3376       }
3377
3378     case ADDR_SPACE_CONVERT_EXPR:
3379       {
3380         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3381             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3382                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3383           {
3384             error ("invalid types in address space conversion");
3385             debug_generic_expr (lhs_type);
3386             debug_generic_expr (rhs1_type);
3387             return true;
3388           }
3389
3390         return false;
3391       }
3392
3393     case FIXED_CONVERT_EXPR:
3394       {
3395         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3396             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3397           {
3398             error ("invalid types in fixed-point conversion");
3399             debug_generic_expr (lhs_type);
3400             debug_generic_expr (rhs1_type);
3401             return true;
3402           }
3403
3404         return false;
3405       }
3406
3407     case FLOAT_EXPR:
3408       {
3409         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3410             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3411                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3412           {
3413             error ("invalid types in conversion to floating point");
3414             debug_generic_expr (lhs_type);
3415             debug_generic_expr (rhs1_type);
3416             return true;
3417           }
3418
3419         return false;
3420       }
3421
3422     case FIX_TRUNC_EXPR:
3423       {
3424         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3425             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3426                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3427           {
3428             error ("invalid types in conversion to integer");
3429             debug_generic_expr (lhs_type);
3430             debug_generic_expr (rhs1_type);
3431             return true;
3432           }
3433
3434         return false;
3435       }
3436
3437     case VEC_UNPACK_HI_EXPR:
3438     case VEC_UNPACK_LO_EXPR:
3439     case REDUC_MAX_EXPR:
3440     case REDUC_MIN_EXPR:
3441     case REDUC_PLUS_EXPR:
3442     case VEC_UNPACK_FLOAT_HI_EXPR:
3443     case VEC_UNPACK_FLOAT_LO_EXPR:
3444       /* FIXME.  */
3445       return false;
3446
3447     case NEGATE_EXPR:
3448     case ABS_EXPR:
3449     case BIT_NOT_EXPR:
3450     case PAREN_EXPR:
3451     case NON_LVALUE_EXPR:
3452     case CONJ_EXPR:
3453       break;
3454
3455     default:
3456       gcc_unreachable ();
3457     }
3458
3459   /* For the remaining codes assert there is no conversion involved.  */
3460   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3461     {
3462       error ("non-trivial conversion in unary operation");
3463       debug_generic_expr (lhs_type);
3464       debug_generic_expr (rhs1_type);
3465       return true;
3466     }
3467
3468   return false;
3469 }
3470
3471 /* Verify a gimple assignment statement STMT with a binary rhs.
3472    Returns true if anything is wrong.  */
3473
3474 static bool
3475 verify_gimple_assign_binary (gimple stmt)
3476 {
3477   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3478   tree lhs = gimple_assign_lhs (stmt);
3479   tree lhs_type = TREE_TYPE (lhs);
3480   tree rhs1 = gimple_assign_rhs1 (stmt);
3481   tree rhs1_type = TREE_TYPE (rhs1);
3482   tree rhs2 = gimple_assign_rhs2 (stmt);
3483   tree rhs2_type = TREE_TYPE (rhs2);
3484
3485   if (!is_gimple_reg (lhs))
3486     {
3487       error ("non-register as LHS of binary operation");
3488       return true;
3489     }
3490
3491   if (!is_gimple_val (rhs1)
3492       || !is_gimple_val (rhs2))
3493     {
3494       error ("invalid operands in binary operation");
3495       return true;
3496     }
3497
3498   /* First handle operations that involve different types.  */
3499   switch (rhs_code)
3500     {
3501     case COMPLEX_EXPR:
3502       {
3503         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3504             || !(INTEGRAL_TYPE_P (rhs1_type)
3505                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3506             || !(INTEGRAL_TYPE_P (rhs2_type)
3507                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3508           {
3509             error ("type mismatch in complex expression");
3510             debug_generic_expr (lhs_type);
3511             debug_generic_expr (rhs1_type);
3512             debug_generic_expr (rhs2_type);
3513             return true;
3514           }
3515
3516         return false;
3517       }
3518
3519     case LSHIFT_EXPR:
3520     case RSHIFT_EXPR:
3521     case LROTATE_EXPR:
3522     case RROTATE_EXPR:
3523       {
3524         /* Shifts and rotates are ok on integral types, fixed point
3525            types and integer vector types.  */
3526         if ((!INTEGRAL_TYPE_P (rhs1_type)
3527              && !FIXED_POINT_TYPE_P (rhs1_type)
3528              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3529                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3530             || (!INTEGRAL_TYPE_P (rhs2_type)
3531                 /* Vector shifts of vectors are also ok.  */
3532                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3533                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3534                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3535                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3536             || !useless_type_conversion_p (lhs_type, rhs1_type))
3537           {
3538             error ("type mismatch in shift expression");
3539             debug_generic_expr (lhs_type);
3540             debug_generic_expr (rhs1_type);
3541             debug_generic_expr (rhs2_type);
3542             return true;
3543           }
3544
3545         return false;
3546       }
3547
3548     case VEC_LSHIFT_EXPR:
3549     case VEC_RSHIFT_EXPR:
3550       {
3551         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3552             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3553                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3554                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3555                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3556             || (!INTEGRAL_TYPE_P (rhs2_type)
3557                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3558                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3559             || !useless_type_conversion_p (lhs_type, rhs1_type))
3560           {
3561             error ("type mismatch in vector shift expression");
3562             debug_generic_expr (lhs_type);
3563             debug_generic_expr (rhs1_type);
3564             debug_generic_expr (rhs2_type);
3565             return true;
3566           }
3567         /* For shifting a vector of non-integral components we
3568            only allow shifting by a constant multiple of the element size.  */
3569         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3570             && (TREE_CODE (rhs2) != INTEGER_CST
3571                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3572                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3573           {
3574             error ("non-element sized vector shift of floating point vector");
3575             return true;
3576           }
3577
3578         return false;
3579       }
3580
3581     case WIDEN_LSHIFT_EXPR:
3582       {
3583         if (!INTEGRAL_TYPE_P (lhs_type)
3584             || !INTEGRAL_TYPE_P (rhs1_type)
3585             || TREE_CODE (rhs2) != INTEGER_CST
3586             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3587           {
3588             error ("type mismatch in widening vector shift expression");
3589             debug_generic_expr (lhs_type);
3590             debug_generic_expr (rhs1_type);
3591             debug_generic_expr (rhs2_type);
3592             return true;
3593           }
3594
3595         return false;
3596       }
3597
3598     case VEC_WIDEN_LSHIFT_HI_EXPR:
3599     case VEC_WIDEN_LSHIFT_LO_EXPR:
3600       {
3601         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3602             || TREE_CODE (lhs_type) != VECTOR_TYPE
3603             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3604             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3605             || TREE_CODE (rhs2) != INTEGER_CST
3606             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3607                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3608           {
3609             error ("type mismatch in widening vector shift expression");
3610             debug_generic_expr (lhs_type);
3611             debug_generic_expr (rhs1_type);
3612             debug_generic_expr (rhs2_type);
3613             return true;
3614           }