OSDN Git Service

2011-11-09 Richard Guenther <rguenther@suse.de>
[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_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           size_t i;
1605
1606           fold_stmt (&gsi);
1607           stmt = gsi_stmt (gsi);
1608           if (cfgcleanup_altered_bbs && !is_gimple_debug (stmt))
1609             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1610
1611           /* FIXME.  This should go in update_stmt.  */
1612           for (i = 0; i < gimple_num_ops (stmt); i++)
1613             {
1614               tree op = gimple_op (stmt, i);
1615               /* Operands may be empty here.  For example, the labels
1616                  of a GIMPLE_COND are nulled out following the creation
1617                  of the corresponding CFG edges.  */
1618               if (op && TREE_CODE (op) == ADDR_EXPR)
1619                 recompute_tree_invariant_for_addr_expr (op);
1620             }
1621
1622           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1623           update_stmt (stmt);
1624         }
1625     }
1626
1627   gcc_assert (has_zero_uses (name));
1628
1629   /* Also update the trees stored in loop structures.  */
1630   if (current_loops)
1631     {
1632       struct loop *loop;
1633       loop_iterator li;
1634
1635       FOR_EACH_LOOP (li, loop, 0)
1636         {
1637           substitute_in_loop_info (loop, name, val);
1638         }
1639     }
1640 }
1641
1642 /* Merge block B into block A.  */
1643
1644 static void
1645 gimple_merge_blocks (basic_block a, basic_block b)
1646 {
1647   gimple_stmt_iterator last, gsi, psi;
1648   gimple_seq phis = phi_nodes (b);
1649
1650   if (dump_file)
1651     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1652
1653   /* Remove all single-valued PHI nodes from block B of the form
1654      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1655   gsi = gsi_last_bb (a);
1656   for (psi = gsi_start (phis); !gsi_end_p (psi); )
1657     {
1658       gimple phi = gsi_stmt (psi);
1659       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1660       gimple copy;
1661       bool may_replace_uses = !is_gimple_reg (def)
1662                               || may_propagate_copy (def, use);
1663
1664       /* In case we maintain loop closed ssa form, do not propagate arguments
1665          of loop exit phi nodes.  */
1666       if (current_loops
1667           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1668           && is_gimple_reg (def)
1669           && TREE_CODE (use) == SSA_NAME
1670           && a->loop_father != b->loop_father)
1671         may_replace_uses = false;
1672
1673       if (!may_replace_uses)
1674         {
1675           gcc_assert (is_gimple_reg (def));
1676
1677           /* Note that just emitting the copies is fine -- there is no problem
1678              with ordering of phi nodes.  This is because A is the single
1679              predecessor of B, therefore results of the phi nodes cannot
1680              appear as arguments of the phi nodes.  */
1681           copy = gimple_build_assign (def, use);
1682           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1683           remove_phi_node (&psi, false);
1684         }
1685       else
1686         {
1687           /* If we deal with a PHI for virtual operands, we can simply
1688              propagate these without fussing with folding or updating
1689              the stmt.  */
1690           if (!is_gimple_reg (def))
1691             {
1692               imm_use_iterator iter;
1693               use_operand_p use_p;
1694               gimple stmt;
1695
1696               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1697                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1698                   SET_USE (use_p, use);
1699
1700               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1701                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1702             }
1703           else
1704             replace_uses_by (def, use);
1705
1706           remove_phi_node (&psi, true);
1707         }
1708     }
1709
1710   /* Ensure that B follows A.  */
1711   move_block_after (b, a);
1712
1713   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1714   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1715
1716   /* Remove labels from B and set gimple_bb to A for other statements.  */
1717   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1718     {
1719       gimple stmt = gsi_stmt (gsi);
1720       if (gimple_code (stmt) == GIMPLE_LABEL)
1721         {
1722           tree label = gimple_label_label (stmt);
1723           int lp_nr;
1724
1725           gsi_remove (&gsi, false);
1726
1727           /* Now that we can thread computed gotos, we might have
1728              a situation where we have a forced label in block B
1729              However, the label at the start of block B might still be
1730              used in other ways (think about the runtime checking for
1731              Fortran assigned gotos).  So we can not just delete the
1732              label.  Instead we move the label to the start of block A.  */
1733           if (FORCED_LABEL (label))
1734             {
1735               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1736               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1737             }
1738           /* Other user labels keep around in a form of a debug stmt.  */
1739           else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1740             {
1741               gimple dbg = gimple_build_debug_bind (label,
1742                                                     integer_zero_node,
1743                                                     stmt);
1744               gimple_debug_bind_reset_value (dbg);
1745               gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1746             }
1747
1748           lp_nr = EH_LANDING_PAD_NR (label);
1749           if (lp_nr)
1750             {
1751               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1752               lp->post_landing_pad = NULL;
1753             }
1754         }
1755       else
1756         {
1757           gimple_set_bb (stmt, a);
1758           gsi_next (&gsi);
1759         }
1760     }
1761
1762   /* Merge the sequences.  */
1763   last = gsi_last_bb (a);
1764   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1765   set_bb_seq (b, NULL);
1766
1767   if (cfgcleanup_altered_bbs)
1768     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1769 }
1770
1771
1772 /* Return the one of two successors of BB that is not reachable by a
1773    complex edge, if there is one.  Else, return BB.  We use
1774    this in optimizations that use post-dominators for their heuristics,
1775    to catch the cases in C++ where function calls are involved.  */
1776
1777 basic_block
1778 single_noncomplex_succ (basic_block bb)
1779 {
1780   edge e0, e1;
1781   if (EDGE_COUNT (bb->succs) != 2)
1782     return bb;
1783
1784   e0 = EDGE_SUCC (bb, 0);
1785   e1 = EDGE_SUCC (bb, 1);
1786   if (e0->flags & EDGE_COMPLEX)
1787     return e1->dest;
1788   if (e1->flags & EDGE_COMPLEX)
1789     return e0->dest;
1790
1791   return bb;
1792 }
1793
1794 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1795
1796 void
1797 notice_special_calls (gimple call)
1798 {
1799   int flags = gimple_call_flags (call);
1800
1801   if (flags & ECF_MAY_BE_ALLOCA)
1802     cfun->calls_alloca = true;
1803   if (flags & ECF_RETURNS_TWICE)
1804     cfun->calls_setjmp = true;
1805 }
1806
1807
1808 /* Clear flags set by notice_special_calls.  Used by dead code removal
1809    to update the flags.  */
1810
1811 void
1812 clear_special_calls (void)
1813 {
1814   cfun->calls_alloca = false;
1815   cfun->calls_setjmp = false;
1816 }
1817
1818 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1819
1820 static void
1821 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1822 {
1823   /* Since this block is no longer reachable, we can just delete all
1824      of its PHI nodes.  */
1825   remove_phi_nodes (bb);
1826
1827   /* Remove edges to BB's successors.  */
1828   while (EDGE_COUNT (bb->succs) > 0)
1829     remove_edge (EDGE_SUCC (bb, 0));
1830 }
1831
1832
1833 /* Remove statements of basic block BB.  */
1834
1835 static void
1836 remove_bb (basic_block bb)
1837 {
1838   gimple_stmt_iterator i;
1839
1840   if (dump_file)
1841     {
1842       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1843       if (dump_flags & TDF_DETAILS)
1844         {
1845           dump_bb (bb, dump_file, 0);
1846           fprintf (dump_file, "\n");
1847         }
1848     }
1849
1850   if (current_loops)
1851     {
1852       struct loop *loop = bb->loop_father;
1853
1854       /* If a loop gets removed, clean up the information associated
1855          with it.  */
1856       if (loop->latch == bb
1857           || loop->header == bb)
1858         free_numbers_of_iterations_estimates_loop (loop);
1859     }
1860
1861   /* Remove all the instructions in the block.  */
1862   if (bb_seq (bb) != NULL)
1863     {
1864       /* Walk backwards so as to get a chance to substitute all
1865          released DEFs into debug stmts.  See
1866          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1867          details.  */
1868       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1869         {
1870           gimple stmt = gsi_stmt (i);
1871           if (gimple_code (stmt) == GIMPLE_LABEL
1872               && (FORCED_LABEL (gimple_label_label (stmt))
1873                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1874             {
1875               basic_block new_bb;
1876               gimple_stmt_iterator new_gsi;
1877
1878               /* A non-reachable non-local label may still be referenced.
1879                  But it no longer needs to carry the extra semantics of
1880                  non-locality.  */
1881               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1882                 {
1883                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1884                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1885                 }
1886
1887               new_bb = bb->prev_bb;
1888               new_gsi = gsi_start_bb (new_bb);
1889               gsi_remove (&i, false);
1890               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1891             }
1892           else
1893             {
1894               /* Release SSA definitions if we are in SSA.  Note that we
1895                  may be called when not in SSA.  For example,
1896                  final_cleanup calls this function via
1897                  cleanup_tree_cfg.  */
1898               if (gimple_in_ssa_p (cfun))
1899                 release_defs (stmt);
1900
1901               gsi_remove (&i, true);
1902             }
1903
1904           if (gsi_end_p (i))
1905             i = gsi_last_bb (bb);
1906           else
1907             gsi_prev (&i);
1908         }
1909     }
1910
1911   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1912   bb->il.gimple = NULL;
1913 }
1914
1915
1916 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1917    predicate VAL, return the edge that will be taken out of the block.
1918    If VAL does not match a unique edge, NULL is returned.  */
1919
1920 edge
1921 find_taken_edge (basic_block bb, tree val)
1922 {
1923   gimple stmt;
1924
1925   stmt = last_stmt (bb);
1926
1927   gcc_assert (stmt);
1928   gcc_assert (is_ctrl_stmt (stmt));
1929
1930   if (val == NULL)
1931     return NULL;
1932
1933   if (!is_gimple_min_invariant (val))
1934     return NULL;
1935
1936   if (gimple_code (stmt) == GIMPLE_COND)
1937     return find_taken_edge_cond_expr (bb, val);
1938
1939   if (gimple_code (stmt) == GIMPLE_SWITCH)
1940     return find_taken_edge_switch_expr (bb, val);
1941
1942   if (computed_goto_p (stmt))
1943     {
1944       /* Only optimize if the argument is a label, if the argument is
1945          not a label then we can not construct a proper CFG.
1946
1947          It may be the case that we only need to allow the LABEL_REF to
1948          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1949          appear inside a LABEL_EXPR just to be safe.  */
1950       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1951           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1952         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1953       return NULL;
1954     }
1955
1956   gcc_unreachable ();
1957 }
1958
1959 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1960    statement, determine which of the outgoing edges will be taken out of the
1961    block.  Return NULL if either edge may be taken.  */
1962
1963 static edge
1964 find_taken_edge_computed_goto (basic_block bb, tree val)
1965 {
1966   basic_block dest;
1967   edge e = NULL;
1968
1969   dest = label_to_block (val);
1970   if (dest)
1971     {
1972       e = find_edge (bb, dest);
1973       gcc_assert (e != NULL);
1974     }
1975
1976   return e;
1977 }
1978
1979 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1980    statement, determine which of the two edges will be taken out of the
1981    block.  Return NULL if either edge may be taken.  */
1982
1983 static edge
1984 find_taken_edge_cond_expr (basic_block bb, tree val)
1985 {
1986   edge true_edge, false_edge;
1987
1988   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1989
1990   gcc_assert (TREE_CODE (val) == INTEGER_CST);
1991   return (integer_zerop (val) ? false_edge : true_edge);
1992 }
1993
1994 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1995    statement, determine which edge will be taken out of the block.  Return
1996    NULL if any edge may be taken.  */
1997
1998 static edge
1999 find_taken_edge_switch_expr (basic_block bb, tree val)
2000 {
2001   basic_block dest_bb;
2002   edge e;
2003   gimple switch_stmt;
2004   tree taken_case;
2005
2006   switch_stmt = last_stmt (bb);
2007   taken_case = find_case_label_for_value (switch_stmt, val);
2008   dest_bb = label_to_block (CASE_LABEL (taken_case));
2009
2010   e = find_edge (bb, dest_bb);
2011   gcc_assert (e);
2012   return e;
2013 }
2014
2015
2016 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2017    We can make optimal use here of the fact that the case labels are
2018    sorted: We can do a binary search for a case matching VAL.  */
2019
2020 static tree
2021 find_case_label_for_value (gimple switch_stmt, tree val)
2022 {
2023   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2024   tree default_case = gimple_switch_default_label (switch_stmt);
2025
2026   for (low = 0, high = n; high - low > 1; )
2027     {
2028       size_t i = (high + low) / 2;
2029       tree t = gimple_switch_label (switch_stmt, i);
2030       int cmp;
2031
2032       /* Cache the result of comparing CASE_LOW and val.  */
2033       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2034
2035       if (cmp > 0)
2036         high = i;
2037       else
2038         low = i;
2039
2040       if (CASE_HIGH (t) == NULL)
2041         {
2042           /* A singe-valued case label.  */
2043           if (cmp == 0)
2044             return t;
2045         }
2046       else
2047         {
2048           /* A case range.  We can only handle integer ranges.  */
2049           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2050             return t;
2051         }
2052     }
2053
2054   return default_case;
2055 }
2056
2057
2058 /* Dump a basic block on stderr.  */
2059
2060 void
2061 gimple_debug_bb (basic_block bb)
2062 {
2063   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2064 }
2065
2066
2067 /* Dump basic block with index N on stderr.  */
2068
2069 basic_block
2070 gimple_debug_bb_n (int n)
2071 {
2072   gimple_debug_bb (BASIC_BLOCK (n));
2073   return BASIC_BLOCK (n);
2074 }
2075
2076
2077 /* Dump the CFG on stderr.
2078
2079    FLAGS are the same used by the tree dumping functions
2080    (see TDF_* in tree-pass.h).  */
2081
2082 void
2083 gimple_debug_cfg (int flags)
2084 {
2085   gimple_dump_cfg (stderr, flags);
2086 }
2087
2088
2089 /* Dump the program showing basic block boundaries on the given FILE.
2090
2091    FLAGS are the same used by the tree dumping functions (see TDF_* in
2092    tree.h).  */
2093
2094 void
2095 gimple_dump_cfg (FILE *file, int flags)
2096 {
2097   if (flags & TDF_DETAILS)
2098     {
2099       dump_function_header (file, current_function_decl, flags);
2100       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2101                n_basic_blocks, n_edges, last_basic_block);
2102
2103       brief_dump_cfg (file);
2104       fprintf (file, "\n");
2105     }
2106
2107   if (flags & TDF_STATS)
2108     dump_cfg_stats (file);
2109
2110   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2111 }
2112
2113
2114 /* Dump CFG statistics on FILE.  */
2115
2116 void
2117 dump_cfg_stats (FILE *file)
2118 {
2119   static long max_num_merged_labels = 0;
2120   unsigned long size, total = 0;
2121   long num_edges;
2122   basic_block bb;
2123   const char * const fmt_str   = "%-30s%-13s%12s\n";
2124   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2125   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2126   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2127   const char *funcname
2128     = lang_hooks.decl_printable_name (current_function_decl, 2);
2129
2130
2131   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2132
2133   fprintf (file, "---------------------------------------------------------\n");
2134   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2135   fprintf (file, fmt_str, "", "  instances  ", "used ");
2136   fprintf (file, "---------------------------------------------------------\n");
2137
2138   size = n_basic_blocks * sizeof (struct basic_block_def);
2139   total += size;
2140   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2141            SCALE (size), LABEL (size));
2142
2143   num_edges = 0;
2144   FOR_EACH_BB (bb)
2145     num_edges += EDGE_COUNT (bb->succs);
2146   size = num_edges * sizeof (struct edge_def);
2147   total += size;
2148   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2149
2150   fprintf (file, "---------------------------------------------------------\n");
2151   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2152            LABEL (total));
2153   fprintf (file, "---------------------------------------------------------\n");
2154   fprintf (file, "\n");
2155
2156   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2157     max_num_merged_labels = cfg_stats.num_merged_labels;
2158
2159   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2160            cfg_stats.num_merged_labels, max_num_merged_labels);
2161
2162   fprintf (file, "\n");
2163 }
2164
2165
2166 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2167    linked in the final executable.  */
2168
2169 DEBUG_FUNCTION void
2170 debug_cfg_stats (void)
2171 {
2172   dump_cfg_stats (stderr);
2173 }
2174
2175
2176 /* Dump the flowgraph to a .vcg FILE.  */
2177
2178 static void
2179 gimple_cfg2vcg (FILE *file)
2180 {
2181   edge e;
2182   edge_iterator ei;
2183   basic_block bb;
2184   const char *funcname
2185     = lang_hooks.decl_printable_name (current_function_decl, 2);
2186
2187   /* Write the file header.  */
2188   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2189   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2190   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2191
2192   /* Write blocks and edges.  */
2193   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2194     {
2195       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2196                e->dest->index);
2197
2198       if (e->flags & EDGE_FAKE)
2199         fprintf (file, " linestyle: dotted priority: 10");
2200       else
2201         fprintf (file, " linestyle: solid priority: 100");
2202
2203       fprintf (file, " }\n");
2204     }
2205   fputc ('\n', file);
2206
2207   FOR_EACH_BB (bb)
2208     {
2209       enum gimple_code head_code, end_code;
2210       const char *head_name, *end_name;
2211       int head_line = 0;
2212       int end_line = 0;
2213       gimple first = first_stmt (bb);
2214       gimple last = last_stmt (bb);
2215
2216       if (first)
2217         {
2218           head_code = gimple_code (first);
2219           head_name = gimple_code_name[head_code];
2220           head_line = get_lineno (first);
2221         }
2222       else
2223         head_name = "no-statement";
2224
2225       if (last)
2226         {
2227           end_code = gimple_code (last);
2228           end_name = gimple_code_name[end_code];
2229           end_line = get_lineno (last);
2230         }
2231       else
2232         end_name = "no-statement";
2233
2234       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2235                bb->index, bb->index, head_name, head_line, end_name,
2236                end_line);
2237
2238       FOR_EACH_EDGE (e, ei, bb->succs)
2239         {
2240           if (e->dest == EXIT_BLOCK_PTR)
2241             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2242           else
2243             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2244
2245           if (e->flags & EDGE_FAKE)
2246             fprintf (file, " priority: 10 linestyle: dotted");
2247           else
2248             fprintf (file, " priority: 100 linestyle: solid");
2249
2250           fprintf (file, " }\n");
2251         }
2252
2253       if (bb->next_bb != EXIT_BLOCK_PTR)
2254         fputc ('\n', file);
2255     }
2256
2257   fputs ("}\n\n", file);
2258 }
2259
2260
2261
2262 /*---------------------------------------------------------------------------
2263                              Miscellaneous helpers
2264 ---------------------------------------------------------------------------*/
2265
2266 /* Return true if T represents a stmt that always transfers control.  */
2267
2268 bool
2269 is_ctrl_stmt (gimple t)
2270 {
2271   switch (gimple_code (t))
2272     {
2273     case GIMPLE_COND:
2274     case GIMPLE_SWITCH:
2275     case GIMPLE_GOTO:
2276     case GIMPLE_RETURN:
2277     case GIMPLE_RESX:
2278       return true;
2279     default:
2280       return false;
2281     }
2282 }
2283
2284
2285 /* Return true if T is a statement that may alter the flow of control
2286    (e.g., a call to a non-returning function).  */
2287
2288 bool
2289 is_ctrl_altering_stmt (gimple t)
2290 {
2291   gcc_assert (t);
2292
2293   switch (gimple_code (t))
2294     {
2295     case GIMPLE_CALL:
2296       {
2297         int flags = gimple_call_flags (t);
2298
2299         /* A non-pure/const call alters flow control if the current
2300            function has nonlocal labels.  */
2301         if (!(flags & (ECF_CONST | ECF_PURE | ECF_LEAF))
2302             && cfun->has_nonlocal_label)
2303           return true;
2304
2305         /* A call also alters control flow if it does not return.  */
2306         if (flags & ECF_NORETURN)
2307           return true;
2308
2309         /* TM ending statements have backedges out of the transaction.
2310            Return true so we split the basic block containing them.
2311            Note that the TM_BUILTIN test is merely an optimization.  */
2312         if ((flags & ECF_TM_BUILTIN)
2313             && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2314           return true;
2315
2316         /* BUILT_IN_RETURN call is same as return statement.  */
2317         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2318           return true;
2319       }
2320       break;
2321
2322     case GIMPLE_EH_DISPATCH:
2323       /* EH_DISPATCH branches to the individual catch handlers at
2324          this level of a try or allowed-exceptions region.  It can
2325          fallthru to the next statement as well.  */
2326       return true;
2327
2328     case GIMPLE_ASM:
2329       if (gimple_asm_nlabels (t) > 0)
2330         return true;
2331       break;
2332
2333     CASE_GIMPLE_OMP:
2334       /* OpenMP directives alter control flow.  */
2335       return true;
2336
2337     case GIMPLE_TRANSACTION:
2338       /* A transaction start alters control flow.  */
2339       return true;
2340
2341     default:
2342       break;
2343     }
2344
2345   /* If a statement can throw, it alters control flow.  */
2346   return stmt_can_throw_internal (t);
2347 }
2348
2349
2350 /* Return true if T is a simple local goto.  */
2351
2352 bool
2353 simple_goto_p (gimple t)
2354 {
2355   return (gimple_code (t) == GIMPLE_GOTO
2356           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2357 }
2358
2359
2360 /* Return true if T can make an abnormal transfer of control flow.
2361    Transfers of control flow associated with EH are excluded.  */
2362
2363 bool
2364 stmt_can_make_abnormal_goto (gimple t)
2365 {
2366   if (computed_goto_p (t))
2367     return true;
2368   if (is_gimple_call (t))
2369     return (gimple_has_side_effects (t) && cfun->has_nonlocal_label
2370             && !(gimple_call_flags (t) & ECF_LEAF));
2371   return false;
2372 }
2373
2374
2375 /* Return true if STMT should start a new basic block.  PREV_STMT is
2376    the statement preceding STMT.  It is used when STMT is a label or a
2377    case label.  Labels should only start a new basic block if their
2378    previous statement wasn't a label.  Otherwise, sequence of labels
2379    would generate unnecessary basic blocks that only contain a single
2380    label.  */
2381
2382 static inline bool
2383 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2384 {
2385   if (stmt == NULL)
2386     return false;
2387
2388   /* Labels start a new basic block only if the preceding statement
2389      wasn't a label of the same type.  This prevents the creation of
2390      consecutive blocks that have nothing but a single label.  */
2391   if (gimple_code (stmt) == GIMPLE_LABEL)
2392     {
2393       /* Nonlocal and computed GOTO targets always start a new block.  */
2394       if (DECL_NONLOCAL (gimple_label_label (stmt))
2395           || FORCED_LABEL (gimple_label_label (stmt)))
2396         return true;
2397
2398       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2399         {
2400           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2401             return true;
2402
2403           cfg_stats.num_merged_labels++;
2404           return false;
2405         }
2406       else
2407         return true;
2408     }
2409
2410   return false;
2411 }
2412
2413
2414 /* Return true if T should end a basic block.  */
2415
2416 bool
2417 stmt_ends_bb_p (gimple t)
2418 {
2419   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2420 }
2421
2422 /* Remove block annotations and other data structures.  */
2423
2424 void
2425 delete_tree_cfg_annotations (void)
2426 {
2427   label_to_block_map = NULL;
2428 }
2429
2430
2431 /* Return the first statement in basic block BB.  */
2432
2433 gimple
2434 first_stmt (basic_block bb)
2435 {
2436   gimple_stmt_iterator i = gsi_start_bb (bb);
2437   gimple stmt = NULL;
2438
2439   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2440     {
2441       gsi_next (&i);
2442       stmt = NULL;
2443     }
2444   return stmt;
2445 }
2446
2447 /* Return the first non-label statement in basic block BB.  */
2448
2449 static gimple
2450 first_non_label_stmt (basic_block bb)
2451 {
2452   gimple_stmt_iterator i = gsi_start_bb (bb);
2453   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2454     gsi_next (&i);
2455   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2456 }
2457
2458 /* Return the last statement in basic block BB.  */
2459
2460 gimple
2461 last_stmt (basic_block bb)
2462 {
2463   gimple_stmt_iterator i = gsi_last_bb (bb);
2464   gimple stmt = NULL;
2465
2466   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2467     {
2468       gsi_prev (&i);
2469       stmt = NULL;
2470     }
2471   return stmt;
2472 }
2473
2474 /* Return the last statement of an otherwise empty block.  Return NULL
2475    if the block is totally empty, or if it contains more than one
2476    statement.  */
2477
2478 gimple
2479 last_and_only_stmt (basic_block bb)
2480 {
2481   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2482   gimple last, prev;
2483
2484   if (gsi_end_p (i))
2485     return NULL;
2486
2487   last = gsi_stmt (i);
2488   gsi_prev_nondebug (&i);
2489   if (gsi_end_p (i))
2490     return last;
2491
2492   /* Empty statements should no longer appear in the instruction stream.
2493      Everything that might have appeared before should be deleted by
2494      remove_useless_stmts, and the optimizers should just gsi_remove
2495      instead of smashing with build_empty_stmt.
2496
2497      Thus the only thing that should appear here in a block containing
2498      one executable statement is a label.  */
2499   prev = gsi_stmt (i);
2500   if (gimple_code (prev) == GIMPLE_LABEL)
2501     return last;
2502   else
2503     return NULL;
2504 }
2505
2506 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2507
2508 static void
2509 reinstall_phi_args (edge new_edge, edge old_edge)
2510 {
2511   edge_var_map_vector v;
2512   edge_var_map *vm;
2513   int i;
2514   gimple_stmt_iterator phis;
2515
2516   v = redirect_edge_var_map_vector (old_edge);
2517   if (!v)
2518     return;
2519
2520   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2521        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2522        i++, gsi_next (&phis))
2523     {
2524       gimple phi = gsi_stmt (phis);
2525       tree result = redirect_edge_var_map_result (vm);
2526       tree arg = redirect_edge_var_map_def (vm);
2527
2528       gcc_assert (result == gimple_phi_result (phi));
2529
2530       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2531     }
2532
2533   redirect_edge_var_map_clear (old_edge);
2534 }
2535
2536 /* Returns the basic block after which the new basic block created
2537    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2538    near its "logical" location.  This is of most help to humans looking
2539    at debugging dumps.  */
2540
2541 static basic_block
2542 split_edge_bb_loc (edge edge_in)
2543 {
2544   basic_block dest = edge_in->dest;
2545   basic_block dest_prev = dest->prev_bb;
2546
2547   if (dest_prev)
2548     {
2549       edge e = find_edge (dest_prev, dest);
2550       if (e && !(e->flags & EDGE_COMPLEX))
2551         return edge_in->src;
2552     }
2553   return dest_prev;
2554 }
2555
2556 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2557    Abort on abnormal edges.  */
2558
2559 static basic_block
2560 gimple_split_edge (edge edge_in)
2561 {
2562   basic_block new_bb, after_bb, dest;
2563   edge new_edge, e;
2564
2565   /* Abnormal edges cannot be split.  */
2566   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2567
2568   dest = edge_in->dest;
2569
2570   after_bb = split_edge_bb_loc (edge_in);
2571
2572   new_bb = create_empty_bb (after_bb);
2573   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2574   new_bb->count = edge_in->count;
2575   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2576   new_edge->probability = REG_BR_PROB_BASE;
2577   new_edge->count = edge_in->count;
2578
2579   e = redirect_edge_and_branch (edge_in, new_bb);
2580   gcc_assert (e == edge_in);
2581   reinstall_phi_args (new_edge, e);
2582
2583   return new_bb;
2584 }
2585
2586
2587 /* Verify properties of the address expression T with base object BASE.  */
2588
2589 static tree
2590 verify_address (tree t, tree base)
2591 {
2592   bool old_constant;
2593   bool old_side_effects;
2594   bool new_constant;
2595   bool new_side_effects;
2596
2597   old_constant = TREE_CONSTANT (t);
2598   old_side_effects = TREE_SIDE_EFFECTS (t);
2599
2600   recompute_tree_invariant_for_addr_expr (t);
2601   new_side_effects = TREE_SIDE_EFFECTS (t);
2602   new_constant = TREE_CONSTANT (t);
2603
2604   if (old_constant != new_constant)
2605     {
2606       error ("constant not recomputed when ADDR_EXPR changed");
2607       return t;
2608     }
2609   if (old_side_effects != new_side_effects)
2610     {
2611       error ("side effects not recomputed when ADDR_EXPR changed");
2612       return t;
2613     }
2614
2615   if (!(TREE_CODE (base) == VAR_DECL
2616         || TREE_CODE (base) == PARM_DECL
2617         || TREE_CODE (base) == RESULT_DECL))
2618     return NULL_TREE;
2619
2620   if (DECL_GIMPLE_REG_P (base))
2621     {
2622       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2623       return base;
2624     }
2625
2626   return NULL_TREE;
2627 }
2628
2629 /* Callback for walk_tree, check that all elements with address taken are
2630    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2631    inside a PHI node.  */
2632
2633 static tree
2634 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2635 {
2636   tree t = *tp, x;
2637
2638   if (TYPE_P (t))
2639     *walk_subtrees = 0;
2640
2641   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2642 #define CHECK_OP(N, MSG) \
2643   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2644        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2645
2646   switch (TREE_CODE (t))
2647     {
2648     case SSA_NAME:
2649       if (SSA_NAME_IN_FREE_LIST (t))
2650         {
2651           error ("SSA name in freelist but still referenced");
2652           return *tp;
2653         }
2654       break;
2655
2656     case INDIRECT_REF:
2657       error ("INDIRECT_REF in gimple IL");
2658       return t;
2659
2660     case MEM_REF:
2661       x = TREE_OPERAND (t, 0);
2662       if (!POINTER_TYPE_P (TREE_TYPE (x))
2663           || !is_gimple_mem_ref_addr (x))
2664         {
2665           error ("invalid first operand of MEM_REF");
2666           return x;
2667         }
2668       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2669           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2670         {
2671           error ("invalid offset operand of MEM_REF");
2672           return TREE_OPERAND (t, 1);
2673         }
2674       if (TREE_CODE (x) == ADDR_EXPR
2675           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2676         return x;
2677       *walk_subtrees = 0;
2678       break;
2679
2680     case ASSERT_EXPR:
2681       x = fold (ASSERT_EXPR_COND (t));
2682       if (x == boolean_false_node)
2683         {
2684           error ("ASSERT_EXPR with an always-false condition");
2685           return *tp;
2686         }
2687       break;
2688
2689     case MODIFY_EXPR:
2690       error ("MODIFY_EXPR not expected while having tuples");
2691       return *tp;
2692
2693     case ADDR_EXPR:
2694       {
2695         tree tem;
2696
2697         gcc_assert (is_gimple_address (t));
2698
2699         /* Skip any references (they will be checked when we recurse down the
2700            tree) and ensure that any variable used as a prefix is marked
2701            addressable.  */
2702         for (x = TREE_OPERAND (t, 0);
2703              handled_component_p (x);
2704              x = TREE_OPERAND (x, 0))
2705           ;
2706
2707         if ((tem = verify_address (t, x)))
2708           return tem;
2709
2710         if (!(TREE_CODE (x) == VAR_DECL
2711               || TREE_CODE (x) == PARM_DECL
2712               || TREE_CODE (x) == RESULT_DECL))
2713           return NULL;
2714
2715         if (!TREE_ADDRESSABLE (x))
2716           {
2717             error ("address taken, but ADDRESSABLE bit not set");
2718             return x;
2719           }
2720
2721         break;
2722       }
2723
2724     case COND_EXPR:
2725       x = COND_EXPR_COND (t);
2726       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2727         {
2728           error ("non-integral used in condition");
2729           return x;
2730         }
2731       if (!is_gimple_condexpr (x))
2732         {
2733           error ("invalid conditional operand");
2734           return x;
2735         }
2736       break;
2737
2738     case NON_LVALUE_EXPR:
2739     case TRUTH_NOT_EXPR:
2740       gcc_unreachable ();
2741
2742     CASE_CONVERT:
2743     case FIX_TRUNC_EXPR:
2744     case FLOAT_EXPR:
2745     case NEGATE_EXPR:
2746     case ABS_EXPR:
2747     case BIT_NOT_EXPR:
2748       CHECK_OP (0, "invalid operand to unary operator");
2749       break;
2750
2751     case REALPART_EXPR:
2752     case IMAGPART_EXPR:
2753     case COMPONENT_REF:
2754     case ARRAY_REF:
2755     case ARRAY_RANGE_REF:
2756     case BIT_FIELD_REF:
2757     case VIEW_CONVERT_EXPR:
2758       /* We have a nest of references.  Verify that each of the operands
2759          that determine where to reference is either a constant or a variable,
2760          verify that the base is valid, and then show we've already checked
2761          the subtrees.  */
2762       while (handled_component_p (t))
2763         {
2764           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2765             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2766           else if (TREE_CODE (t) == ARRAY_REF
2767                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2768             {
2769               CHECK_OP (1, "invalid array index");
2770               if (TREE_OPERAND (t, 2))
2771                 CHECK_OP (2, "invalid array lower bound");
2772               if (TREE_OPERAND (t, 3))
2773                 CHECK_OP (3, "invalid array stride");
2774             }
2775           else if (TREE_CODE (t) == BIT_FIELD_REF)
2776             {
2777               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2778                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2779                 {
2780                   error ("invalid position or size operand to BIT_FIELD_REF");
2781                   return t;
2782                 }
2783               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2784                        && (TYPE_PRECISION (TREE_TYPE (t))
2785                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2786                 {
2787                   error ("integral result type precision does not match "
2788                          "field size of BIT_FIELD_REF");
2789                   return t;
2790                 }
2791               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2792                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2793                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2794                 {
2795                   error ("mode precision of non-integral result does not "
2796                          "match field size of BIT_FIELD_REF");
2797                   return t;
2798                 }
2799             }
2800
2801           t = TREE_OPERAND (t, 0);
2802         }
2803
2804       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2805         {
2806           error ("invalid reference prefix");
2807           return t;
2808         }
2809       *walk_subtrees = 0;
2810       break;
2811     case PLUS_EXPR:
2812     case MINUS_EXPR:
2813       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2814          POINTER_PLUS_EXPR. */
2815       if (POINTER_TYPE_P (TREE_TYPE (t)))
2816         {
2817           error ("invalid operand to plus/minus, type is a pointer");
2818           return t;
2819         }
2820       CHECK_OP (0, "invalid operand to binary operator");
2821       CHECK_OP (1, "invalid operand to binary operator");
2822       break;
2823
2824     case POINTER_PLUS_EXPR:
2825       /* Check to make sure the first operand is a pointer or reference type. */
2826       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2827         {
2828           error ("invalid operand to pointer plus, first operand is not a pointer");
2829           return t;
2830         }
2831       /* Check to make sure the second operand is a ptrofftype.  */
2832       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2833         {
2834           error ("invalid operand to pointer plus, second operand is not an "
2835                  "integer type of appropriate width");
2836           return t;
2837         }
2838       /* FALLTHROUGH */
2839     case LT_EXPR:
2840     case LE_EXPR:
2841     case GT_EXPR:
2842     case GE_EXPR:
2843     case EQ_EXPR:
2844     case NE_EXPR:
2845     case UNORDERED_EXPR:
2846     case ORDERED_EXPR:
2847     case UNLT_EXPR:
2848     case UNLE_EXPR:
2849     case UNGT_EXPR:
2850     case UNGE_EXPR:
2851     case UNEQ_EXPR:
2852     case LTGT_EXPR:
2853     case MULT_EXPR:
2854     case TRUNC_DIV_EXPR:
2855     case CEIL_DIV_EXPR:
2856     case FLOOR_DIV_EXPR:
2857     case ROUND_DIV_EXPR:
2858     case TRUNC_MOD_EXPR:
2859     case CEIL_MOD_EXPR:
2860     case FLOOR_MOD_EXPR:
2861     case ROUND_MOD_EXPR:
2862     case RDIV_EXPR:
2863     case EXACT_DIV_EXPR:
2864     case MIN_EXPR:
2865     case MAX_EXPR:
2866     case LSHIFT_EXPR:
2867     case RSHIFT_EXPR:
2868     case LROTATE_EXPR:
2869     case RROTATE_EXPR:
2870     case BIT_IOR_EXPR:
2871     case BIT_XOR_EXPR:
2872     case BIT_AND_EXPR:
2873       CHECK_OP (0, "invalid operand to binary operator");
2874       CHECK_OP (1, "invalid operand to binary operator");
2875       break;
2876
2877     case CONSTRUCTOR:
2878       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2879         *walk_subtrees = 0;
2880       break;
2881
2882     case CASE_LABEL_EXPR:
2883       if (CASE_CHAIN (t))
2884         {
2885           error ("invalid CASE_CHAIN");
2886           return t;
2887         }
2888       break;
2889
2890     default:
2891       break;
2892     }
2893   return NULL;
2894
2895 #undef CHECK_OP
2896 }
2897
2898
2899 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2900    Returns true if there is an error, otherwise false.  */
2901
2902 static bool
2903 verify_types_in_gimple_min_lval (tree expr)
2904 {
2905   tree op;
2906
2907   if (is_gimple_id (expr))
2908     return false;
2909
2910   if (TREE_CODE (expr) != TARGET_MEM_REF
2911       && TREE_CODE (expr) != MEM_REF)
2912     {
2913       error ("invalid expression for min lvalue");
2914       return true;
2915     }
2916
2917   /* TARGET_MEM_REFs are strange beasts.  */
2918   if (TREE_CODE (expr) == TARGET_MEM_REF)
2919     return false;
2920
2921   op = TREE_OPERAND (expr, 0);
2922   if (!is_gimple_val (op))
2923     {
2924       error ("invalid operand in indirect reference");
2925       debug_generic_stmt (op);
2926       return true;
2927     }
2928   /* Memory references now generally can involve a value conversion.  */
2929
2930   return false;
2931 }
2932
2933 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2934    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2935    if there is an error, otherwise false.  */
2936
2937 static bool
2938 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2939 {
2940   while (handled_component_p (expr))
2941     {
2942       tree op = TREE_OPERAND (expr, 0);
2943
2944       if (TREE_CODE (expr) == ARRAY_REF
2945           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2946         {
2947           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2948               || (TREE_OPERAND (expr, 2)
2949                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2950               || (TREE_OPERAND (expr, 3)
2951                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2952             {
2953               error ("invalid operands to array reference");
2954               debug_generic_stmt (expr);
2955               return true;
2956             }
2957         }
2958
2959       /* Verify if the reference array element types are compatible.  */
2960       if (TREE_CODE (expr) == ARRAY_REF
2961           && !useless_type_conversion_p (TREE_TYPE (expr),
2962                                          TREE_TYPE (TREE_TYPE (op))))
2963         {
2964           error ("type mismatch in array reference");
2965           debug_generic_stmt (TREE_TYPE (expr));
2966           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2967           return true;
2968         }
2969       if (TREE_CODE (expr) == ARRAY_RANGE_REF
2970           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2971                                          TREE_TYPE (TREE_TYPE (op))))
2972         {
2973           error ("type mismatch in array range reference");
2974           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2975           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2976           return true;
2977         }
2978
2979       if ((TREE_CODE (expr) == REALPART_EXPR
2980            || TREE_CODE (expr) == IMAGPART_EXPR)
2981           && !useless_type_conversion_p (TREE_TYPE (expr),
2982                                          TREE_TYPE (TREE_TYPE (op))))
2983         {
2984           error ("type mismatch in real/imagpart reference");
2985           debug_generic_stmt (TREE_TYPE (expr));
2986           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2987           return true;
2988         }
2989
2990       if (TREE_CODE (expr) == COMPONENT_REF
2991           && !useless_type_conversion_p (TREE_TYPE (expr),
2992                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
2993         {
2994           error ("type mismatch in component reference");
2995           debug_generic_stmt (TREE_TYPE (expr));
2996           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
2997           return true;
2998         }
2999
3000       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3001         {
3002           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
3003              that their operand is not an SSA name or an invariant when
3004              requiring an lvalue (this usually means there is a SRA or IPA-SRA
3005              bug).  Otherwise there is nothing to verify, gross mismatches at
3006              most invoke undefined behavior.  */
3007           if (require_lvalue
3008               && (TREE_CODE (op) == SSA_NAME
3009                   || is_gimple_min_invariant (op)))
3010             {
3011               error ("conversion of an SSA_NAME on the left hand side");
3012               debug_generic_stmt (expr);
3013               return true;
3014             }
3015           else if (TREE_CODE (op) == SSA_NAME
3016                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
3017             {
3018               error ("conversion of register to a different size");
3019               debug_generic_stmt (expr);
3020               return true;
3021             }
3022           else if (!handled_component_p (op))
3023             return false;
3024         }
3025
3026       expr = op;
3027     }
3028
3029   if (TREE_CODE (expr) == MEM_REF)
3030     {
3031       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
3032         {
3033           error ("invalid address operand in MEM_REF");
3034           debug_generic_stmt (expr);
3035           return true;
3036         }
3037       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
3038           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
3039         {
3040           error ("invalid offset operand in MEM_REF");
3041           debug_generic_stmt (expr);
3042           return true;
3043         }
3044     }
3045   else if (TREE_CODE (expr) == TARGET_MEM_REF)
3046     {
3047       if (!TMR_BASE (expr)
3048           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3049         {
3050           error ("invalid address operand in TARGET_MEM_REF");
3051           return true;
3052         }
3053       if (!TMR_OFFSET (expr)
3054           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3055           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3056         {
3057           error ("invalid offset operand in TARGET_MEM_REF");
3058           debug_generic_stmt (expr);
3059           return true;
3060         }
3061     }
3062
3063   return ((require_lvalue || !is_gimple_min_invariant (expr))
3064           && verify_types_in_gimple_min_lval (expr));
3065 }
3066
3067 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3068    list of pointer-to types that is trivially convertible to DEST.  */
3069
3070 static bool
3071 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3072 {
3073   tree src;
3074
3075   if (!TYPE_POINTER_TO (src_obj))
3076     return true;
3077
3078   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3079     if (useless_type_conversion_p (dest, src))
3080       return true;
3081
3082   return false;
3083 }
3084
3085 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3086    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3087
3088 static bool
3089 valid_fixed_convert_types_p (tree type1, tree type2)
3090 {
3091   return (FIXED_POINT_TYPE_P (type1)
3092           && (INTEGRAL_TYPE_P (type2)
3093               || SCALAR_FLOAT_TYPE_P (type2)
3094               || FIXED_POINT_TYPE_P (type2)));
3095 }
3096
3097 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3098    is a problem, otherwise false.  */
3099
3100 static bool
3101 verify_gimple_call (gimple stmt)
3102 {
3103   tree fn = gimple_call_fn (stmt);
3104   tree fntype, fndecl;
3105   unsigned i;
3106
3107   if (gimple_call_internal_p (stmt))
3108     {
3109       if (fn)
3110         {
3111           error ("gimple call has two targets");
3112           debug_generic_stmt (fn);
3113           return true;
3114         }
3115     }
3116   else
3117     {
3118       if (!fn)
3119         {
3120           error ("gimple call has no target");
3121           return true;
3122         }
3123     }
3124
3125   if (fn && !is_gimple_call_addr (fn))
3126     {
3127       error ("invalid function in gimple call");
3128       debug_generic_stmt (fn);
3129       return true;
3130     }
3131
3132   if (fn
3133       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3134           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3135               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3136     {
3137       error ("non-function in gimple call");
3138       return true;
3139     }
3140
3141    fndecl = gimple_call_fndecl (stmt);
3142    if (fndecl
3143        && TREE_CODE (fndecl) == FUNCTION_DECL
3144        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3145        && !DECL_PURE_P (fndecl)
3146        && !TREE_READONLY (fndecl))
3147      {
3148        error ("invalid pure const state for function");
3149        return true;
3150      }
3151
3152   if (gimple_call_lhs (stmt)
3153       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3154           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3155     {
3156       error ("invalid LHS in gimple call");
3157       return true;
3158     }
3159
3160   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3161     {
3162       error ("LHS in noreturn call");
3163       return true;
3164     }
3165
3166   fntype = gimple_call_fntype (stmt);
3167   if (fntype
3168       && gimple_call_lhs (stmt)
3169       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3170                                      TREE_TYPE (fntype))
3171       /* ???  At least C++ misses conversions at assignments from
3172          void * call results.
3173          ???  Java is completely off.  Especially with functions
3174          returning java.lang.Object.
3175          For now simply allow arbitrary pointer type conversions.  */
3176       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3177            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3178     {
3179       error ("invalid conversion in gimple call");
3180       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3181       debug_generic_stmt (TREE_TYPE (fntype));
3182       return true;
3183     }
3184
3185   if (gimple_call_chain (stmt)
3186       && !is_gimple_val (gimple_call_chain (stmt)))
3187     {
3188       error ("invalid static chain in gimple call");
3189       debug_generic_stmt (gimple_call_chain (stmt));
3190       return true;
3191     }
3192
3193   /* If there is a static chain argument, this should not be an indirect
3194      call, and the decl should have DECL_STATIC_CHAIN set.  */
3195   if (gimple_call_chain (stmt))
3196     {
3197       if (!gimple_call_fndecl (stmt))
3198         {
3199           error ("static chain in indirect gimple call");
3200           return true;
3201         }
3202       fn = TREE_OPERAND (fn, 0);
3203
3204       if (!DECL_STATIC_CHAIN (fn))
3205         {
3206           error ("static chain with function that doesn%'t use one");
3207           return true;
3208         }
3209     }
3210
3211   /* ???  The C frontend passes unpromoted arguments in case it
3212      didn't see a function declaration before the call.  So for now
3213      leave the call arguments mostly unverified.  Once we gimplify
3214      unit-at-a-time we have a chance to fix this.  */
3215
3216   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3217     {
3218       tree arg = gimple_call_arg (stmt, i);
3219       if ((is_gimple_reg_type (TREE_TYPE (arg))
3220            && !is_gimple_val (arg))
3221           || (!is_gimple_reg_type (TREE_TYPE (arg))
3222               && !is_gimple_lvalue (arg)))
3223         {
3224           error ("invalid argument to gimple call");
3225           debug_generic_expr (arg);
3226           return true;
3227         }
3228     }
3229
3230   return false;
3231 }
3232
3233 /* Verifies the gimple comparison with the result type TYPE and
3234    the operands OP0 and OP1.  */
3235
3236 static bool
3237 verify_gimple_comparison (tree type, tree op0, tree op1)
3238 {
3239   tree op0_type = TREE_TYPE (op0);
3240   tree op1_type = TREE_TYPE (op1);
3241
3242   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3243     {
3244       error ("invalid operands in gimple comparison");
3245       return true;
3246     }
3247
3248   /* For comparisons we do not have the operations type as the
3249      effective type the comparison is carried out in.  Instead
3250      we require that either the first operand is trivially
3251      convertible into the second, or the other way around.
3252      Because we special-case pointers to void we allow
3253      comparisons of pointers with the same mode as well.  */
3254   if (!useless_type_conversion_p (op0_type, op1_type)
3255       && !useless_type_conversion_p (op1_type, op0_type)
3256       && (!POINTER_TYPE_P (op0_type)
3257           || !POINTER_TYPE_P (op1_type)
3258           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3259     {
3260       error ("mismatching comparison operand types");
3261       debug_generic_expr (op0_type);
3262       debug_generic_expr (op1_type);
3263       return true;
3264     }
3265
3266   /* The resulting type of a comparison may be an effective boolean type.  */
3267   if (INTEGRAL_TYPE_P (type)
3268       && (TREE_CODE (type) == BOOLEAN_TYPE
3269           || TYPE_PRECISION (type) == 1))
3270     ;
3271   /* Or an integer vector type with the same size and element count
3272      as the comparison operand types.  */
3273   else if (TREE_CODE (type) == VECTOR_TYPE
3274            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3275     {
3276       if (TREE_CODE (op0_type) != VECTOR_TYPE
3277           || TREE_CODE (op1_type) != VECTOR_TYPE)
3278         {
3279           error ("non-vector operands in vector comparison");
3280           debug_generic_expr (op0_type);
3281           debug_generic_expr (op1_type);
3282           return true;
3283         }
3284
3285       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3286           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3287               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3288         {
3289           error ("invalid vector comparison resulting type");
3290           debug_generic_expr (type);
3291           return true;
3292         }
3293     }
3294   else
3295     {
3296       error ("bogus comparison result type");
3297       debug_generic_expr (type);
3298       return true;
3299     }
3300
3301   return false;
3302 }
3303
3304 /* Verify a gimple assignment statement STMT with an unary rhs.
3305    Returns true if anything is wrong.  */
3306
3307 static bool
3308 verify_gimple_assign_unary (gimple stmt)
3309 {
3310   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3311   tree lhs = gimple_assign_lhs (stmt);
3312   tree lhs_type = TREE_TYPE (lhs);
3313   tree rhs1 = gimple_assign_rhs1 (stmt);
3314   tree rhs1_type = TREE_TYPE (rhs1);
3315
3316   if (!is_gimple_reg (lhs))
3317     {
3318       error ("non-register as LHS of unary operation");
3319       return true;
3320     }
3321
3322   if (!is_gimple_val (rhs1))
3323     {
3324       error ("invalid operand in unary operation");
3325       return true;
3326     }
3327
3328   /* First handle conversions.  */
3329   switch (rhs_code)
3330     {
3331     CASE_CONVERT:
3332       {
3333         /* Allow conversions between integral types and pointers only if
3334            there is no sign or zero extension involved.
3335            For targets were the precision of ptrofftype doesn't match that
3336            of pointers we need to allow arbitrary conversions from and
3337            to ptrofftype.  */
3338         if ((POINTER_TYPE_P (lhs_type)
3339              && INTEGRAL_TYPE_P (rhs1_type)
3340              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3341                  || ptrofftype_p (rhs1_type)))
3342             || (POINTER_TYPE_P (rhs1_type)
3343                 && INTEGRAL_TYPE_P (lhs_type)
3344                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3345                     || ptrofftype_p (sizetype))))
3346           return false;
3347
3348         /* Allow conversion from integer to offset type and vice versa.  */
3349         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3350              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3351             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3352                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3353           return false;
3354
3355         /* Otherwise assert we are converting between types of the
3356            same kind.  */
3357         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3358           {
3359             error ("invalid types in nop conversion");
3360             debug_generic_expr (lhs_type);
3361             debug_generic_expr (rhs1_type);
3362             return true;
3363           }
3364
3365         return false;
3366       }
3367
3368     case ADDR_SPACE_CONVERT_EXPR:
3369       {
3370         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3371             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3372                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3373           {
3374             error ("invalid types in address space conversion");
3375             debug_generic_expr (lhs_type);
3376             debug_generic_expr (rhs1_type);
3377             return true;
3378           }
3379
3380         return false;
3381       }
3382
3383     case FIXED_CONVERT_EXPR:
3384       {
3385         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3386             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3387           {
3388             error ("invalid types in fixed-point conversion");
3389             debug_generic_expr (lhs_type);
3390             debug_generic_expr (rhs1_type);
3391             return true;
3392           }
3393
3394         return false;
3395       }
3396
3397     case FLOAT_EXPR:
3398       {
3399         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3400             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3401                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3402           {
3403             error ("invalid types in conversion to floating point");
3404             debug_generic_expr (lhs_type);
3405             debug_generic_expr (rhs1_type);
3406             return true;
3407           }
3408
3409         return false;
3410       }
3411
3412     case FIX_TRUNC_EXPR:
3413       {
3414         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3415             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3416                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3417           {
3418             error ("invalid types in conversion to integer");
3419             debug_generic_expr (lhs_type);
3420             debug_generic_expr (rhs1_type);
3421             return true;
3422           }
3423
3424         return false;
3425       }
3426
3427     case VEC_UNPACK_HI_EXPR:
3428     case VEC_UNPACK_LO_EXPR:
3429     case REDUC_MAX_EXPR:
3430     case REDUC_MIN_EXPR:
3431     case REDUC_PLUS_EXPR:
3432     case VEC_UNPACK_FLOAT_HI_EXPR:
3433     case VEC_UNPACK_FLOAT_LO_EXPR:
3434       /* FIXME.  */
3435       return false;
3436
3437     case NEGATE_EXPR:
3438     case ABS_EXPR:
3439     case BIT_NOT_EXPR:
3440     case PAREN_EXPR:
3441     case NON_LVALUE_EXPR:
3442     case CONJ_EXPR:
3443       break;
3444
3445     default:
3446       gcc_unreachable ();
3447     }
3448
3449   /* For the remaining codes assert there is no conversion involved.  */
3450   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3451     {
3452       error ("non-trivial conversion in unary operation");
3453       debug_generic_expr (lhs_type);
3454       debug_generic_expr (rhs1_type);
3455       return true;
3456     }
3457
3458   return false;
3459 }
3460
3461 /* Verify a gimple assignment statement STMT with a binary rhs.
3462    Returns true if anything is wrong.  */
3463
3464 static bool
3465 verify_gimple_assign_binary (gimple stmt)
3466 {
3467   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3468   tree lhs = gimple_assign_lhs (stmt);
3469   tree lhs_type = TREE_TYPE (lhs);
3470   tree rhs1 = gimple_assign_rhs1 (stmt);
3471   tree rhs1_type = TREE_TYPE (rhs1);
3472   tree rhs2 = gimple_assign_rhs2 (stmt);
3473   tree rhs2_type = TREE_TYPE (rhs2);
3474
3475   if (!is_gimple_reg (lhs))
3476     {
3477       error ("non-register as LHS of binary operation");
3478       return true;
3479     }
3480
3481   if (!is_gimple_val (rhs1)
3482       || !is_gimple_val (rhs2))
3483     {
3484       error ("invalid operands in binary operation");
3485       return true;
3486     }
3487
3488   /* First handle operations that involve different types.  */
3489   switch (rhs_code)
3490     {
3491     case COMPLEX_EXPR:
3492       {
3493         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3494             || !(INTEGRAL_TYPE_P (rhs1_type)
3495                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3496             || !(INTEGRAL_TYPE_P (rhs2_type)
3497                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3498           {
3499             error ("type mismatch in complex expression");
3500             debug_generic_expr (lhs_type);
3501             debug_generic_expr (rhs1_type);
3502             debug_generic_expr (rhs2_type);
3503             return true;
3504           }
3505
3506         return false;
3507       }
3508
3509     case LSHIFT_EXPR:
3510     case RSHIFT_EXPR:
3511     case LROTATE_EXPR:
3512     case RROTATE_EXPR:
3513       {
3514         /* Shifts and rotates are ok on integral types, fixed point
3515            types and integer vector types.  */
3516         if ((!INTEGRAL_TYPE_P (rhs1_type)
3517              && !FIXED_POINT_TYPE_P (rhs1_type)
3518              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3519                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3520             || (!INTEGRAL_TYPE_P (rhs2_type)
3521                 /* Vector shifts of vectors are also ok.  */
3522                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3523                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3524                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3525                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3526             || !useless_type_conversion_p (lhs_type, rhs1_type))
3527           {
3528             error ("type mismatch in shift expression");
3529             debug_generic_expr (lhs_type);
3530             debug_generic_expr (rhs1_type);
3531             debug_generic_expr (rhs2_type);
3532             return true;
3533           }
3534
3535         return false;
3536       }
3537
3538     case VEC_LSHIFT_EXPR:
3539     case VEC_RSHIFT_EXPR:
3540       {
3541         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3542             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3543                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3544                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3545                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3546             || (!INTEGRAL_TYPE_P (rhs2_type)
3547                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3548                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3549             || !useless_type_conversion_p (lhs_type, rhs1_type))
3550           {
3551             error ("type mismatch in vector shift expression");
3552             debug_generic_expr (lhs_type);
3553             debug_generic_expr (rhs1_type);
3554             debug_generic_expr (rhs2_type);
3555             return true;
3556           }
3557         /* For shifting a vector of non-integral components we
3558            only allow shifting by a constant multiple of the element size.  */
3559         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3560             && (TREE_CODE (rhs2) != INTEGER_CST
3561                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3562                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3563           {
3564             error ("non-element sized vector shift of floating point vector");
3565             return true;
3566           }
3567
3568         return false;
3569       }
3570
3571     case WIDEN_LSHIFT_EXPR:
3572       {
3573         if (!INTEGRAL_TYPE_P (lhs_type)
3574             || !INTEGRAL_TYPE_P (rhs1_type)
3575             || TREE_CODE (rhs2) != INTEGER_CST
3576             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3577           {
3578             error ("type mismatch in widening vector shift expression");
3579             debug_generic_expr (lhs_type);
3580             debug_generic_expr (rhs1_type);
3581             debug_generic_expr (rhs2_type);
3582             return true;
3583           }
3584
3585         return false;
3586       }
3587
3588     case VEC_WIDEN_LSHIFT_HI_EXPR:
3589     case VEC_WIDEN_LSHIFT_LO_EXPR:
3590       {
3591         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3592             || TREE_CODE (lhs_type) != VECTOR_TYPE
3593             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3594             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3595             || TREE_CODE (rhs2) != INTEGER_CST
3596             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3597                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3598           {
3599             error ("type mismatch in widening vector shift expression");
3600             debug_generic_expr (lhs_type);
3601             debug_generic_expr (rhs1_type);
3602             debug_generic_expr (rhs2_type);
3603             return true;
3604           }
3605
3606         return false;
3607       }
3608
3609     case PLUS_EXPR:
3610     case MINUS_EXPR:
3611       {
3612         /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3613            ???  This just makes the checker happy and may not be what is
3614            intended.  */
3615         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3616             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))