remove unused files
[platform/upstream/gcc48.git] / gcc / tree-cfg.c
1 /* Control flow functions for trees.
2    Copyright (C) 2001-2013 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tm_p.h"
27 #include "basic-block.h"
28 #include "flags.h"
29 #include "function.h"
30 #include "ggc.h"
31 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "tree-pass.h"
35 #include "diagnostic-core.h"
36 #include "except.h"
37 #include "cfgloop.h"
38 #include "tree-ssa-propagate.h"
39 #include "value-prof.h"
40 #include "pointer-set.h"
41 #include "tree-inline.h"
42 #include "target.h"
43
44 /* This file contains functions for building the Control Flow Graph (CFG)
45    for a function tree.  */
46
47 /* Local declarations.  */
48
49 /* Initial capacity for the basic block array.  */
50 static const int initial_cfg_capacity = 20;
51
52 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
53    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
54    via their CASE_CHAIN field, which we clear after we're done with the
55    hash table to prevent problems with duplication of GIMPLE_SWITCHes.
56
57    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
58    update the case vector in response to edge redirections.
59
60    Right now this table is set up and torn down at key points in the
61    compilation process.  It would be nice if we could make the table
62    more persistent.  The key is getting notification of changes to
63    the CFG (particularly edge removal, creation and redirection).  */
64
65 static struct pointer_map_t *edge_to_cases;
66
67 /* If we record edge_to_cases, this bitmap will hold indexes
68    of basic blocks that end in a GIMPLE_SWITCH which we touched
69    due to edge manipulations.  */
70
71 static bitmap touched_switch_bbs;
72
73 /* CFG statistics.  */
74 struct cfg_stats_d
75 {
76   long num_merged_labels;
77 };
78
79 static struct cfg_stats_d cfg_stats;
80
81 /* Nonzero if we found a computed goto while building basic blocks.  */
82 static bool found_computed_goto;
83
84 /* Hash table to store last discriminator assigned for each locus.  */
85 struct locus_discrim_map
86 {
87   location_t locus;
88   int discriminator;
89 };
90 static htab_t discriminator_per_locus;
91
92 /* Basic blocks and flowgraphs.  */
93 static void make_blocks (gimple_seq);
94 static void factor_computed_gotos (void);
95
96 /* Edges.  */
97 static void make_edges (void);
98 static void make_cond_expr_edges (basic_block);
99 static void make_gimple_switch_edges (basic_block);
100 static void make_goto_expr_edges (basic_block);
101 static void make_gimple_asm_edges (basic_block);
102 static unsigned int locus_map_hash (const void *);
103 static int locus_map_eq (const void *, const void *);
104 static void assign_discriminator (location_t, basic_block);
105 static edge gimple_redirect_edge_and_branch (edge, basic_block);
106 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
107 static unsigned int split_critical_edges (void);
108
109 /* Various helpers.  */
110 static inline bool stmt_starts_bb_p (gimple, gimple);
111 static int gimple_verify_flow_info (void);
112 static void gimple_make_forwarder_block (edge);
113 static gimple first_non_label_stmt (basic_block);
114 static bool verify_gimple_transaction (gimple);
115
116 /* Flowgraph optimization and cleanup.  */
117 static void gimple_merge_blocks (basic_block, basic_block);
118 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
119 static void remove_bb (basic_block);
120 static edge find_taken_edge_computed_goto (basic_block, tree);
121 static edge find_taken_edge_cond_expr (basic_block, tree);
122 static edge find_taken_edge_switch_expr (basic_block, tree);
123 static tree find_case_label_for_value (gimple, tree);
124
125 void
126 init_empty_tree_cfg_for_function (struct function *fn)
127 {
128   /* Initialize the basic block array.  */
129   init_flow (fn);
130   profile_status_for_function (fn) = PROFILE_ABSENT;
131   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
132   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
133   vec_alloc (basic_block_info_for_function (fn), initial_cfg_capacity);
134   vec_safe_grow_cleared (basic_block_info_for_function (fn),
135                          initial_cfg_capacity);
136
137   /* Build a mapping of labels to their associated blocks.  */
138   vec_alloc (label_to_block_map_for_function (fn), initial_cfg_capacity);
139   vec_safe_grow_cleared (label_to_block_map_for_function (fn),
140                          initial_cfg_capacity);
141
142   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
143                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
144   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
145                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
146
147   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
148     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
149   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
150     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
151 }
152
153 void
154 init_empty_tree_cfg (void)
155 {
156   init_empty_tree_cfg_for_function (cfun);
157 }
158
159 /*---------------------------------------------------------------------------
160                               Create basic blocks
161 ---------------------------------------------------------------------------*/
162
163 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
164    statements to be added to the flowgraph.  */
165
166 static void
167 build_gimple_cfg (gimple_seq seq)
168 {
169   /* Register specific gimple functions.  */
170   gimple_register_cfg_hooks ();
171
172   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
173
174   init_empty_tree_cfg ();
175
176   found_computed_goto = 0;
177   make_blocks (seq);
178
179   /* Computed gotos are hell to deal with, especially if there are
180      lots of them with a large number of destinations.  So we factor
181      them to a common computed goto location before we build the
182      edge list.  After we convert back to normal form, we will un-factor
183      the computed gotos since factoring introduces an unwanted jump.  */
184   if (found_computed_goto)
185     factor_computed_gotos ();
186
187   /* Make sure there is always at least one block, even if it's empty.  */
188   if (n_basic_blocks == NUM_FIXED_BLOCKS)
189     create_empty_bb (ENTRY_BLOCK_PTR);
190
191   /* Adjust the size of the array.  */
192   if (basic_block_info->length () < (size_t) n_basic_blocks)
193     vec_safe_grow_cleared (basic_block_info, n_basic_blocks);
194
195   /* To speed up statement iterator walks, we first purge dead labels.  */
196   cleanup_dead_labels ();
197
198   /* Group case nodes to reduce the number of edges.
199      We do this after cleaning up dead labels because otherwise we miss
200      a lot of obvious case merging opportunities.  */
201   group_case_labels ();
202
203   /* Create the edges of the flowgraph.  */
204   discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
205                                          free);
206   make_edges ();
207   cleanup_dead_labels ();
208   htab_delete (discriminator_per_locus);
209 }
210
211 static unsigned int
212 execute_build_cfg (void)
213 {
214   gimple_seq body = gimple_body (current_function_decl);
215
216   build_gimple_cfg (body);
217   gimple_set_body (current_function_decl, NULL);
218   if (dump_file && (dump_flags & TDF_DETAILS))
219     {
220       fprintf (dump_file, "Scope blocks:\n");
221       dump_scope_blocks (dump_file, dump_flags);
222     }
223   return 0;
224 }
225
226 struct gimple_opt_pass pass_build_cfg =
227 {
228  {
229   GIMPLE_PASS,
230   "cfg",                                /* name */
231   OPTGROUP_NONE,                        /* optinfo_flags */
232   NULL,                                 /* gate */
233   execute_build_cfg,                    /* execute */
234   NULL,                                 /* sub */
235   NULL,                                 /* next */
236   0,                                    /* static_pass_number */
237   TV_TREE_CFG,                          /* tv_id */
238   PROP_gimple_leh,                      /* properties_required */
239   PROP_cfg,                             /* properties_provided */
240   0,                                    /* properties_destroyed */
241   0,                                    /* todo_flags_start */
242   TODO_verify_stmts | TODO_cleanup_cfg  /* todo_flags_finish */
243  }
244 };
245
246
247 /* Return true if T is a computed goto.  */
248
249 static bool
250 computed_goto_p (gimple t)
251 {
252   return (gimple_code (t) == GIMPLE_GOTO
253           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
254 }
255
256
257 /* Search the CFG for any computed gotos.  If found, factor them to a
258    common computed goto site.  Also record the location of that site so
259    that we can un-factor the gotos after we have converted back to
260    normal form.  */
261
262 static void
263 factor_computed_gotos (void)
264 {
265   basic_block bb;
266   tree factored_label_decl = NULL;
267   tree var = NULL;
268   gimple factored_computed_goto_label = NULL;
269   gimple factored_computed_goto = NULL;
270
271   /* We know there are one or more computed gotos in this function.
272      Examine the last statement in each basic block to see if the block
273      ends with a computed goto.  */
274
275   FOR_EACH_BB (bb)
276     {
277       gimple_stmt_iterator gsi = gsi_last_bb (bb);
278       gimple last;
279
280       if (gsi_end_p (gsi))
281         continue;
282
283       last = gsi_stmt (gsi);
284
285       /* Ignore the computed goto we create when we factor the original
286          computed gotos.  */
287       if (last == factored_computed_goto)
288         continue;
289
290       /* If the last statement is a computed goto, factor it.  */
291       if (computed_goto_p (last))
292         {
293           gimple assignment;
294
295           /* The first time we find a computed goto we need to create
296              the factored goto block and the variable each original
297              computed goto will use for their goto destination.  */
298           if (!factored_computed_goto)
299             {
300               basic_block new_bb = create_empty_bb (bb);
301               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
302
303               /* Create the destination of the factored goto.  Each original
304                  computed goto will put its desired destination into this
305                  variable and jump to the label we create immediately
306                  below.  */
307               var = create_tmp_var (ptr_type_node, "gotovar");
308
309               /* Build a label for the new block which will contain the
310                  factored computed goto.  */
311               factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
312               factored_computed_goto_label
313                 = gimple_build_label (factored_label_decl);
314               gsi_insert_after (&new_gsi, factored_computed_goto_label,
315                                 GSI_NEW_STMT);
316
317               /* Build our new computed goto.  */
318               factored_computed_goto = gimple_build_goto (var);
319               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
320             }
321
322           /* Copy the original computed goto's destination into VAR.  */
323           assignment = gimple_build_assign (var, gimple_goto_dest (last));
324           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
325
326           /* And re-vector the computed goto to the new destination.  */
327           gimple_goto_set_dest (last, factored_label_decl);
328         }
329     }
330 }
331
332
333 /* Build a flowgraph for the sequence of stmts SEQ.  */
334
335 static void
336 make_blocks (gimple_seq seq)
337 {
338   gimple_stmt_iterator i = gsi_start (seq);
339   gimple stmt = NULL;
340   bool start_new_block = true;
341   bool first_stmt_of_seq = true;
342   basic_block bb = ENTRY_BLOCK_PTR;
343
344   while (!gsi_end_p (i))
345     {
346       gimple prev_stmt;
347
348       prev_stmt = stmt;
349       stmt = gsi_stmt (i);
350
351       /* If the statement starts a new basic block or if we have determined
352          in a previous pass that we need to create a new block for STMT, do
353          so now.  */
354       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
355         {
356           if (!first_stmt_of_seq)
357             gsi_split_seq_before (&i, &seq);
358           bb = create_basic_block (seq, NULL, bb);
359           start_new_block = false;
360         }
361
362       /* Now add STMT to BB and create the subgraphs for special statement
363          codes.  */
364       gimple_set_bb (stmt, bb);
365
366       if (computed_goto_p (stmt))
367         found_computed_goto = true;
368
369       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
370          next iteration.  */
371       if (stmt_ends_bb_p (stmt))
372         {
373           /* If the stmt can make abnormal goto use a new temporary
374              for the assignment to the LHS.  This makes sure the old value
375              of the LHS is available on the abnormal edge.  Otherwise
376              we will end up with overlapping life-ranges for abnormal
377              SSA names.  */
378           if (gimple_has_lhs (stmt)
379               && stmt_can_make_abnormal_goto (stmt)
380               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
381             {
382               tree lhs = gimple_get_lhs (stmt);
383               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
384               gimple s = gimple_build_assign (lhs, tmp);
385               gimple_set_location (s, gimple_location (stmt));
386               gimple_set_block (s, gimple_block (stmt));
387               gimple_set_lhs (stmt, tmp);
388               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
389                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
390                 DECL_GIMPLE_REG_P (tmp) = 1;
391               gsi_insert_after (&i, s, GSI_SAME_STMT);
392             }
393           start_new_block = true;
394         }
395
396       gsi_next (&i);
397       first_stmt_of_seq = false;
398     }
399 }
400
401
402 /* Create and return a new empty basic block after bb AFTER.  */
403
404 static basic_block
405 create_bb (void *h, void *e, basic_block after)
406 {
407   basic_block bb;
408
409   gcc_assert (!e);
410
411   /* Create and initialize a new basic block.  Since alloc_block uses
412      GC allocation that clears memory to allocate a basic block, we do
413      not have to clear the newly allocated basic block here.  */
414   bb = alloc_block ();
415
416   bb->index = last_basic_block;
417   bb->flags = BB_NEW;
418   set_bb_seq (bb, h ? (gimple_seq) h : NULL);
419
420   /* Add the new block to the linked list of blocks.  */
421   link_block (bb, after);
422
423   /* Grow the basic block array if needed.  */
424   if ((size_t) last_basic_block == basic_block_info->length ())
425     {
426       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
427       vec_safe_grow_cleared (basic_block_info, new_size);
428     }
429
430   /* Add the newly created block to the array.  */
431   SET_BASIC_BLOCK (last_basic_block, bb);
432
433   n_basic_blocks++;
434   last_basic_block++;
435
436   return bb;
437 }
438
439
440 /*---------------------------------------------------------------------------
441                                  Edge creation
442 ---------------------------------------------------------------------------*/
443
444 /* Fold COND_EXPR_COND of each COND_EXPR.  */
445
446 void
447 fold_cond_expr_cond (void)
448 {
449   basic_block bb;
450
451   FOR_EACH_BB (bb)
452     {
453       gimple stmt = last_stmt (bb);
454
455       if (stmt && gimple_code (stmt) == GIMPLE_COND)
456         {
457           location_t loc = gimple_location (stmt);
458           tree cond;
459           bool zerop, onep;
460
461           fold_defer_overflow_warnings ();
462           cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
463                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
464           if (cond)
465             {
466               zerop = integer_zerop (cond);
467               onep = integer_onep (cond);
468             }
469           else
470             zerop = onep = false;
471
472           fold_undefer_overflow_warnings (zerop || onep,
473                                           stmt,
474                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
475           if (zerop)
476             gimple_cond_make_false (stmt);
477           else if (onep)
478             gimple_cond_make_true (stmt);
479         }
480     }
481 }
482
483 /* Join all the blocks in the flowgraph.  */
484
485 static void
486 make_edges (void)
487 {
488   basic_block bb;
489   struct omp_region *cur_region = NULL;
490
491   /* Create an edge from entry to the first block with executable
492      statements in it.  */
493   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
494
495   /* Traverse the basic block array placing edges.  */
496   FOR_EACH_BB (bb)
497     {
498       gimple last = last_stmt (bb);
499       bool fallthru;
500
501       if (last)
502         {
503           enum gimple_code code = gimple_code (last);
504           switch (code)
505             {
506             case GIMPLE_GOTO:
507               make_goto_expr_edges (bb);
508               fallthru = false;
509               break;
510             case GIMPLE_RETURN:
511               make_edge (bb, EXIT_BLOCK_PTR, 0);
512               fallthru = false;
513               break;
514             case GIMPLE_COND:
515               make_cond_expr_edges (bb);
516               fallthru = false;
517               break;
518             case GIMPLE_SWITCH:
519               make_gimple_switch_edges (bb);
520               fallthru = false;
521               break;
522             case GIMPLE_RESX:
523               make_eh_edges (last);
524               fallthru = false;
525               break;
526             case GIMPLE_EH_DISPATCH:
527               fallthru = make_eh_dispatch_edges (last);
528               break;
529
530             case GIMPLE_CALL:
531               /* If this function receives a nonlocal goto, then we need to
532                  make edges from this call site to all the nonlocal goto
533                  handlers.  */
534               if (stmt_can_make_abnormal_goto (last))
535                 make_abnormal_goto_edges (bb, true);
536
537               /* If this statement has reachable exception handlers, then
538                  create abnormal edges to them.  */
539               make_eh_edges (last);
540
541               /* BUILTIN_RETURN is really a return statement.  */
542               if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
543                 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
544               /* Some calls are known not to return.  */
545               else
546                 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
547               break;
548
549             case GIMPLE_ASSIGN:
550                /* A GIMPLE_ASSIGN may throw internally and thus be considered
551                   control-altering. */
552               if (is_ctrl_altering_stmt (last))
553                 make_eh_edges (last);
554               fallthru = true;
555               break;
556
557             case GIMPLE_ASM:
558               make_gimple_asm_edges (bb);
559               fallthru = true;
560               break;
561
562             case GIMPLE_OMP_PARALLEL:
563             case GIMPLE_OMP_TASK:
564             case GIMPLE_OMP_FOR:
565             case GIMPLE_OMP_SINGLE:
566             case GIMPLE_OMP_MASTER:
567             case GIMPLE_OMP_ORDERED:
568             case GIMPLE_OMP_CRITICAL:
569             case GIMPLE_OMP_SECTION:
570               cur_region = new_omp_region (bb, code, cur_region);
571               fallthru = true;
572               break;
573
574             case GIMPLE_OMP_SECTIONS:
575               cur_region = new_omp_region (bb, code, cur_region);
576               fallthru = true;
577               break;
578
579             case GIMPLE_OMP_SECTIONS_SWITCH:
580               fallthru = false;
581               break;
582
583             case GIMPLE_OMP_ATOMIC_LOAD:
584             case GIMPLE_OMP_ATOMIC_STORE:
585                fallthru = true;
586                break;
587
588             case GIMPLE_OMP_RETURN:
589               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
590                  somewhere other than the next block.  This will be
591                  created later.  */
592               cur_region->exit = bb;
593               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
594               cur_region = cur_region->outer;
595               break;
596
597             case GIMPLE_OMP_CONTINUE:
598               cur_region->cont = bb;
599               switch (cur_region->type)
600                 {
601                 case GIMPLE_OMP_FOR:
602                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
603                      succs edges as abnormal to prevent splitting
604                      them.  */
605                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
606                   /* Make the loopback edge.  */
607                   make_edge (bb, single_succ (cur_region->entry),
608                              EDGE_ABNORMAL);
609
610                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
611                      corresponds to the case that the body of the loop
612                      is not executed at all.  */
613                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
614                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
615                   fallthru = false;
616                   break;
617
618                 case GIMPLE_OMP_SECTIONS:
619                   /* Wire up the edges into and out of the nested sections.  */
620                   {
621                     basic_block switch_bb = single_succ (cur_region->entry);
622
623                     struct omp_region *i;
624                     for (i = cur_region->inner; i ; i = i->next)
625                       {
626                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
627                         make_edge (switch_bb, i->entry, 0);
628                         make_edge (i->exit, bb, EDGE_FALLTHRU);
629                       }
630
631                     /* Make the loopback edge to the block with
632                        GIMPLE_OMP_SECTIONS_SWITCH.  */
633                     make_edge (bb, switch_bb, 0);
634
635                     /* Make the edge from the switch to exit.  */
636                     make_edge (switch_bb, bb->next_bb, 0);
637                     fallthru = false;
638                   }
639                   break;
640
641                 default:
642                   gcc_unreachable ();
643                 }
644               break;
645
646             case GIMPLE_TRANSACTION:
647               {
648                 tree abort_label = gimple_transaction_label (last);
649                 if (abort_label)
650                   make_edge (bb, label_to_block (abort_label), EDGE_TM_ABORT);
651                 fallthru = true;
652               }
653               break;
654
655             default:
656               gcc_assert (!stmt_ends_bb_p (last));
657               fallthru = true;
658             }
659         }
660       else
661         fallthru = true;
662
663       if (fallthru)
664         {
665           make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
666           if (last)
667             assign_discriminator (gimple_location (last), bb->next_bb);
668         }
669     }
670
671   if (root_omp_region)
672     free_omp_regions ();
673
674   /* Fold COND_EXPR_COND of each COND_EXPR.  */
675   fold_cond_expr_cond ();
676 }
677
678 /* Trivial hash function for a location_t.  ITEM is a pointer to
679    a hash table entry that maps a location_t to a discriminator.  */
680
681 static unsigned int
682 locus_map_hash (const void *item)
683 {
684   return ((const struct locus_discrim_map *) item)->locus;
685 }
686
687 /* Equality function for the locus-to-discriminator map.  VA and VB
688    point to the two hash table entries to compare.  */
689
690 static int
691 locus_map_eq (const void *va, const void *vb)
692 {
693   const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
694   const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
695   return a->locus == b->locus;
696 }
697
698 /* Find the next available discriminator value for LOCUS.  The
699    discriminator distinguishes among several basic blocks that
700    share a common locus, allowing for more accurate sample-based
701    profiling.  */
702
703 static int
704 next_discriminator_for_locus (location_t locus)
705 {
706   struct locus_discrim_map item;
707   struct locus_discrim_map **slot;
708
709   item.locus = locus;
710   item.discriminator = 0;
711   slot = (struct locus_discrim_map **)
712       htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
713                                 (hashval_t) locus, INSERT);
714   gcc_assert (slot);
715   if (*slot == HTAB_EMPTY_ENTRY)
716     {
717       *slot = XNEW (struct locus_discrim_map);
718       gcc_assert (*slot);
719       (*slot)->locus = locus;
720       (*slot)->discriminator = 0;
721     }
722   (*slot)->discriminator++;
723   return (*slot)->discriminator;
724 }
725
726 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line.  */
727
728 static bool
729 same_line_p (location_t locus1, location_t locus2)
730 {
731   expanded_location from, to;
732
733   if (locus1 == locus2)
734     return true;
735
736   from = expand_location (locus1);
737   to = expand_location (locus2);
738
739   if (from.line != to.line)
740     return false;
741   if (from.file == to.file)
742     return true;
743   return (from.file != NULL
744           && to.file != NULL
745           && filename_cmp (from.file, to.file) == 0);
746 }
747
748 /* Assign a unique discriminator value to block BB if it begins at the same
749    LOCUS as its predecessor block.  */
750
751 static void
752 assign_discriminator (location_t locus, basic_block bb)
753 {
754   gimple first_in_to_bb, last_in_to_bb;
755
756   if (locus == 0 || bb->discriminator != 0)
757     return;
758
759   first_in_to_bb = first_non_label_stmt (bb);
760   last_in_to_bb = last_stmt (bb);
761   if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
762       || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
763     bb->discriminator = next_discriminator_for_locus (locus);
764 }
765
766 /* Create the edges for a GIMPLE_COND starting at block BB.  */
767
768 static void
769 make_cond_expr_edges (basic_block bb)
770 {
771   gimple entry = last_stmt (bb);
772   gimple then_stmt, else_stmt;
773   basic_block then_bb, else_bb;
774   tree then_label, else_label;
775   edge e;
776   location_t entry_locus;
777
778   gcc_assert (entry);
779   gcc_assert (gimple_code (entry) == GIMPLE_COND);
780
781   entry_locus = gimple_location (entry);
782
783   /* Entry basic blocks for each component.  */
784   then_label = gimple_cond_true_label (entry);
785   else_label = gimple_cond_false_label (entry);
786   then_bb = label_to_block (then_label);
787   else_bb = label_to_block (else_label);
788   then_stmt = first_stmt (then_bb);
789   else_stmt = first_stmt (else_bb);
790
791   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
792   assign_discriminator (entry_locus, then_bb);
793   e->goto_locus = gimple_location (then_stmt);
794   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
795   if (e)
796     {
797       assign_discriminator (entry_locus, else_bb);
798       e->goto_locus = gimple_location (else_stmt);
799     }
800
801   /* We do not need the labels anymore.  */
802   gimple_cond_set_true_label (entry, NULL_TREE);
803   gimple_cond_set_false_label (entry, NULL_TREE);
804 }
805
806
807 /* Called for each element in the hash table (P) as we delete the
808    edge to cases hash table.
809
810    Clear all the TREE_CHAINs to prevent problems with copying of
811    SWITCH_EXPRs and structure sharing rules, then free the hash table
812    element.  */
813
814 static bool
815 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
816                        void *data ATTRIBUTE_UNUSED)
817 {
818   tree t, next;
819
820   for (t = (tree) *value; t; t = next)
821     {
822       next = CASE_CHAIN (t);
823       CASE_CHAIN (t) = NULL;
824     }
825
826   *value = NULL;
827   return true;
828 }
829
830 /* Start recording information mapping edges to case labels.  */
831
832 void
833 start_recording_case_labels (void)
834 {
835   gcc_assert (edge_to_cases == NULL);
836   edge_to_cases = pointer_map_create ();
837   touched_switch_bbs = BITMAP_ALLOC (NULL);
838 }
839
840 /* Return nonzero if we are recording information for case labels.  */
841
842 static bool
843 recording_case_labels_p (void)
844 {
845   return (edge_to_cases != NULL);
846 }
847
848 /* Stop recording information mapping edges to case labels and
849    remove any information we have recorded.  */
850 void
851 end_recording_case_labels (void)
852 {
853   bitmap_iterator bi;
854   unsigned i;
855   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
856   pointer_map_destroy (edge_to_cases);
857   edge_to_cases = NULL;
858   EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
859     {
860       basic_block bb = BASIC_BLOCK (i);
861       if (bb)
862         {
863           gimple stmt = last_stmt (bb);
864           if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
865             group_case_labels_stmt (stmt);
866         }
867     }
868   BITMAP_FREE (touched_switch_bbs);
869 }
870
871 /* If we are inside a {start,end}_recording_cases block, then return
872    a chain of CASE_LABEL_EXPRs from T which reference E.
873
874    Otherwise return NULL.  */
875
876 static tree
877 get_cases_for_edge (edge e, gimple t)
878 {
879   void **slot;
880   size_t i, n;
881
882   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
883      chains available.  Return NULL so the caller can detect this case.  */
884   if (!recording_case_labels_p ())
885     return NULL;
886
887   slot = pointer_map_contains (edge_to_cases, e);
888   if (slot)
889     return (tree) *slot;
890
891   /* If we did not find E in the hash table, then this must be the first
892      time we have been queried for information about E & T.  Add all the
893      elements from T to the hash table then perform the query again.  */
894
895   n = gimple_switch_num_labels (t);
896   for (i = 0; i < n; i++)
897     {
898       tree elt = gimple_switch_label (t, i);
899       tree lab = CASE_LABEL (elt);
900       basic_block label_bb = label_to_block (lab);
901       edge this_edge = find_edge (e->src, label_bb);
902
903       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
904          a new chain.  */
905       slot = pointer_map_insert (edge_to_cases, this_edge);
906       CASE_CHAIN (elt) = (tree) *slot;
907       *slot = elt;
908     }
909
910   return (tree) *pointer_map_contains (edge_to_cases, e);
911 }
912
913 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
914
915 static void
916 make_gimple_switch_edges (basic_block bb)
917 {
918   gimple entry = last_stmt (bb);
919   location_t entry_locus;
920   size_t i, n;
921
922   entry_locus = gimple_location (entry);
923
924   n = gimple_switch_num_labels (entry);
925
926   for (i = 0; i < n; ++i)
927     {
928       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
929       basic_block label_bb = label_to_block (lab);
930       make_edge (bb, label_bb, 0);
931       assign_discriminator (entry_locus, label_bb);
932     }
933 }
934
935
936 /* Return the basic block holding label DEST.  */
937
938 basic_block
939 label_to_block_fn (struct function *ifun, tree dest)
940 {
941   int uid = LABEL_DECL_UID (dest);
942
943   /* We would die hard when faced by an undefined label.  Emit a label to
944      the very first basic block.  This will hopefully make even the dataflow
945      and undefined variable warnings quite right.  */
946   if (seen_error () && uid < 0)
947     {
948       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
949       gimple stmt;
950
951       stmt = gimple_build_label (dest);
952       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
953       uid = LABEL_DECL_UID (dest);
954     }
955   if (vec_safe_length (ifun->cfg->x_label_to_block_map) <= (unsigned int) uid)
956     return NULL;
957   return (*ifun->cfg->x_label_to_block_map)[uid];
958 }
959
960 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
961    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
962
963 void
964 make_abnormal_goto_edges (basic_block bb, bool for_call)
965 {
966   basic_block target_bb;
967   gimple_stmt_iterator gsi;
968
969   FOR_EACH_BB (target_bb)
970     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
971       {
972         gimple label_stmt = gsi_stmt (gsi);
973         tree target;
974
975         if (gimple_code (label_stmt) != GIMPLE_LABEL)
976           break;
977
978         target = gimple_label_label (label_stmt);
979
980         /* Make an edge to every label block that has been marked as a
981            potential target for a computed goto or a non-local goto.  */
982         if ((FORCED_LABEL (target) && !for_call)
983             || (DECL_NONLOCAL (target) && for_call))
984           {
985             make_edge (bb, target_bb, EDGE_ABNORMAL);
986             break;
987           }
988       }
989 }
990
991 /* Create edges for a goto statement at block BB.  */
992
993 static void
994 make_goto_expr_edges (basic_block bb)
995 {
996   gimple_stmt_iterator last = gsi_last_bb (bb);
997   gimple goto_t = gsi_stmt (last);
998
999   /* A simple GOTO creates normal edges.  */
1000   if (simple_goto_p (goto_t))
1001     {
1002       tree dest = gimple_goto_dest (goto_t);
1003       basic_block label_bb = label_to_block (dest);
1004       edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1005       e->goto_locus = gimple_location (goto_t);
1006       assign_discriminator (e->goto_locus, label_bb);
1007       gsi_remove (&last, true);
1008       return;
1009     }
1010
1011   /* A computed GOTO creates abnormal edges.  */
1012   make_abnormal_goto_edges (bb, false);
1013 }
1014
1015 /* Create edges for an asm statement with labels at block BB.  */
1016
1017 static void
1018 make_gimple_asm_edges (basic_block bb)
1019 {
1020   gimple stmt = last_stmt (bb);
1021   location_t stmt_loc = gimple_location (stmt);
1022   int i, n = gimple_asm_nlabels (stmt);
1023
1024   for (i = 0; i < n; ++i)
1025     {
1026       tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1027       basic_block label_bb = label_to_block (label);
1028       make_edge (bb, label_bb, 0);
1029       assign_discriminator (stmt_loc, label_bb);
1030     }
1031 }
1032
1033 /*---------------------------------------------------------------------------
1034                                Flowgraph analysis
1035 ---------------------------------------------------------------------------*/
1036
1037 /* Cleanup useless labels in basic blocks.  This is something we wish
1038    to do early because it allows us to group case labels before creating
1039    the edges for the CFG, and it speeds up block statement iterators in
1040    all passes later on.
1041    We rerun this pass after CFG is created, to get rid of the labels that
1042    are no longer referenced.  After then we do not run it any more, since
1043    (almost) no new labels should be created.  */
1044
1045 /* A map from basic block index to the leading label of that block.  */
1046 static struct label_record
1047 {
1048   /* The label.  */
1049   tree label;
1050
1051   /* True if the label is referenced from somewhere.  */
1052   bool used;
1053 } *label_for_bb;
1054
1055 /* Given LABEL return the first label in the same basic block.  */
1056
1057 static tree
1058 main_block_label (tree label)
1059 {
1060   basic_block bb = label_to_block (label);
1061   tree main_label = label_for_bb[bb->index].label;
1062
1063   /* label_to_block possibly inserted undefined label into the chain.  */
1064   if (!main_label)
1065     {
1066       label_for_bb[bb->index].label = label;
1067       main_label = label;
1068     }
1069
1070   label_for_bb[bb->index].used = true;
1071   return main_label;
1072 }
1073
1074 /* Clean up redundant labels within the exception tree.  */
1075
1076 static void
1077 cleanup_dead_labels_eh (void)
1078 {
1079   eh_landing_pad lp;
1080   eh_region r;
1081   tree lab;
1082   int i;
1083
1084   if (cfun->eh == NULL)
1085     return;
1086
1087   for (i = 1; vec_safe_iterate (cfun->eh->lp_array, i, &lp); ++i)
1088     if (lp && lp->post_landing_pad)
1089       {
1090         lab = main_block_label (lp->post_landing_pad);
1091         if (lab != lp->post_landing_pad)
1092           {
1093             EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1094             EH_LANDING_PAD_NR (lab) = lp->index;
1095           }
1096       }
1097
1098   FOR_ALL_EH_REGION (r)
1099     switch (r->type)
1100       {
1101       case ERT_CLEANUP:
1102       case ERT_MUST_NOT_THROW:
1103         break;
1104
1105       case ERT_TRY:
1106         {
1107           eh_catch c;
1108           for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1109             {
1110               lab = c->label;
1111               if (lab)
1112                 c->label = main_block_label (lab);
1113             }
1114         }
1115         break;
1116
1117       case ERT_ALLOWED_EXCEPTIONS:
1118         lab = r->u.allowed.label;
1119         if (lab)
1120           r->u.allowed.label = main_block_label (lab);
1121         break;
1122       }
1123 }
1124
1125
1126 /* Cleanup redundant labels.  This is a three-step process:
1127      1) Find the leading label for each block.
1128      2) Redirect all references to labels to the leading labels.
1129      3) Cleanup all useless labels.  */
1130
1131 void
1132 cleanup_dead_labels (void)
1133 {
1134   basic_block bb;
1135   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1136
1137   /* Find a suitable label for each block.  We use the first user-defined
1138      label if there is one, or otherwise just the first label we see.  */
1139   FOR_EACH_BB (bb)
1140     {
1141       gimple_stmt_iterator i;
1142
1143       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1144         {
1145           tree label;
1146           gimple stmt = gsi_stmt (i);
1147
1148           if (gimple_code (stmt) != GIMPLE_LABEL)
1149             break;
1150
1151           label = gimple_label_label (stmt);
1152
1153           /* If we have not yet seen a label for the current block,
1154              remember this one and see if there are more labels.  */
1155           if (!label_for_bb[bb->index].label)
1156             {
1157               label_for_bb[bb->index].label = label;
1158               continue;
1159             }
1160
1161           /* If we did see a label for the current block already, but it
1162              is an artificially created label, replace it if the current
1163              label is a user defined label.  */
1164           if (!DECL_ARTIFICIAL (label)
1165               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1166             {
1167               label_for_bb[bb->index].label = label;
1168               break;
1169             }
1170         }
1171     }
1172
1173   /* Now redirect all jumps/branches to the selected label.
1174      First do so for each block ending in a control statement.  */
1175   FOR_EACH_BB (bb)
1176     {
1177       gimple stmt = last_stmt (bb);
1178       tree label, new_label;
1179
1180       if (!stmt)
1181         continue;
1182
1183       switch (gimple_code (stmt))
1184         {
1185         case GIMPLE_COND:
1186           label = gimple_cond_true_label (stmt);
1187           if (label)
1188             {
1189               new_label = main_block_label (label);
1190               if (new_label != label)
1191                 gimple_cond_set_true_label (stmt, new_label);
1192             }
1193
1194           label = gimple_cond_false_label (stmt);
1195           if (label)
1196             {
1197               new_label = main_block_label (label);
1198               if (new_label != label)
1199                 gimple_cond_set_false_label (stmt, new_label);
1200             }
1201           break;
1202
1203         case GIMPLE_SWITCH:
1204           {
1205             size_t i, n = gimple_switch_num_labels (stmt);
1206
1207             /* Replace all destination labels.  */
1208             for (i = 0; i < n; ++i)
1209               {
1210                 tree case_label = gimple_switch_label (stmt, i);
1211                 label = CASE_LABEL (case_label);
1212                 new_label = main_block_label (label);
1213                 if (new_label != label)
1214                   CASE_LABEL (case_label) = new_label;
1215               }
1216             break;
1217           }
1218
1219         case GIMPLE_ASM:
1220           {
1221             int i, n = gimple_asm_nlabels (stmt);
1222
1223             for (i = 0; i < n; ++i)
1224               {
1225                 tree cons = gimple_asm_label_op (stmt, i);
1226                 tree label = main_block_label (TREE_VALUE (cons));
1227                 TREE_VALUE (cons) = label;
1228               }
1229             break;
1230           }
1231
1232         /* We have to handle gotos until they're removed, and we don't
1233            remove them until after we've created the CFG edges.  */
1234         case GIMPLE_GOTO:
1235           if (!computed_goto_p (stmt))
1236             {
1237               label = gimple_goto_dest (stmt);
1238               new_label = main_block_label (label);
1239               if (new_label != label)
1240                 gimple_goto_set_dest (stmt, new_label);
1241             }
1242           break;
1243
1244         case GIMPLE_TRANSACTION:
1245           {
1246             tree label = gimple_transaction_label (stmt);
1247             if (label)
1248               {
1249                 tree new_label = main_block_label (label);
1250                 if (new_label != label)
1251                   gimple_transaction_set_label (stmt, new_label);
1252               }
1253           }
1254           break;
1255
1256         default:
1257           break;
1258       }
1259     }
1260
1261   /* Do the same for the exception region tree labels.  */
1262   cleanup_dead_labels_eh ();
1263
1264   /* Finally, purge dead labels.  All user-defined labels and labels that
1265      can be the target of non-local gotos and labels which have their
1266      address taken are preserved.  */
1267   FOR_EACH_BB (bb)
1268     {
1269       gimple_stmt_iterator i;
1270       tree label_for_this_bb = label_for_bb[bb->index].label;
1271
1272       if (!label_for_this_bb)
1273         continue;
1274
1275       /* If the main label of the block is unused, we may still remove it.  */
1276       if (!label_for_bb[bb->index].used)
1277         label_for_this_bb = NULL;
1278
1279       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1280         {
1281           tree label;
1282           gimple stmt = gsi_stmt (i);
1283
1284           if (gimple_code (stmt) != GIMPLE_LABEL)
1285             break;
1286
1287           label = gimple_label_label (stmt);
1288
1289           if (label == label_for_this_bb
1290               || !DECL_ARTIFICIAL (label)
1291               || DECL_NONLOCAL (label)
1292               || FORCED_LABEL (label))
1293             gsi_next (&i);
1294           else
1295             gsi_remove (&i, true);
1296         }
1297     }
1298
1299   free (label_for_bb);
1300 }
1301
1302 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1303    the ones jumping to the same label.
1304    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1305
1306 void
1307 group_case_labels_stmt (gimple stmt)
1308 {
1309   int old_size = gimple_switch_num_labels (stmt);
1310   int i, j, new_size = old_size;
1311   basic_block default_bb = NULL;
1312
1313   default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));
1314
1315   /* Look for possible opportunities to merge cases.  */
1316   i = 1;
1317   while (i < old_size)
1318     {
1319       tree base_case, base_high;
1320       basic_block base_bb;
1321
1322       base_case = gimple_switch_label (stmt, i);
1323
1324       gcc_assert (base_case);
1325       base_bb = label_to_block (CASE_LABEL (base_case));
1326
1327       /* Discard cases that have the same destination as the
1328          default case.  */
1329       if (base_bb == default_bb)
1330         {
1331           gimple_switch_set_label (stmt, i, NULL_TREE);
1332           i++;
1333           new_size--;
1334           continue;
1335         }
1336
1337       base_high = CASE_HIGH (base_case)
1338           ? CASE_HIGH (base_case)
1339           : CASE_LOW (base_case);
1340       i++;
1341
1342       /* Try to merge case labels.  Break out when we reach the end
1343          of the label vector or when we cannot merge the next case
1344          label with the current one.  */
1345       while (i < old_size)
1346         {
1347           tree merge_case = gimple_switch_label (stmt, i);
1348           basic_block merge_bb = label_to_block (CASE_LABEL (merge_case));
1349           double_int bhp1 = tree_to_double_int (base_high) + double_int_one;
1350
1351           /* Merge the cases if they jump to the same place,
1352              and their ranges are consecutive.  */
1353           if (merge_bb == base_bb
1354               && tree_to_double_int (CASE_LOW (merge_case)) == bhp1)
1355             {
1356               base_high = CASE_HIGH (merge_case) ?
1357                   CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1358               CASE_HIGH (base_case) = base_high;
1359               gimple_switch_set_label (stmt, i, NULL_TREE);
1360               new_size--;
1361               i++;
1362             }
1363           else
1364             break;
1365         }
1366     }
1367
1368   /* Compress the case labels in the label vector, and adjust the
1369      length of the vector.  */
1370   for (i = 0, j = 0; i < new_size; i++)
1371     {
1372       while (! gimple_switch_label (stmt, j))
1373         j++;
1374       gimple_switch_set_label (stmt, i,
1375                                gimple_switch_label (stmt, j++));
1376     }
1377
1378   gcc_assert (new_size <= old_size);
1379   gimple_switch_set_num_labels (stmt, new_size);
1380 }
1381
1382 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1383    and scan the sorted vector of cases.  Combine the ones jumping to the
1384    same label.  */
1385
1386 void
1387 group_case_labels (void)
1388 {
1389   basic_block bb;
1390
1391   FOR_EACH_BB (bb)
1392     {
1393       gimple stmt = last_stmt (bb);
1394       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1395         group_case_labels_stmt (stmt);
1396     }
1397 }
1398
1399 /* Checks whether we can merge block B into block A.  */
1400
1401 static bool
1402 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1403 {
1404   gimple stmt;
1405   gimple_stmt_iterator gsi;
1406
1407   if (!single_succ_p (a))
1408     return false;
1409
1410   if (single_succ_edge (a)->flags & EDGE_COMPLEX)
1411     return false;
1412
1413   if (single_succ (a) != b)
1414     return false;
1415
1416   if (!single_pred_p (b))
1417     return false;
1418
1419   if (b == EXIT_BLOCK_PTR)
1420     return false;
1421
1422   /* If A ends by a statement causing exceptions or something similar, we
1423      cannot merge the blocks.  */
1424   stmt = last_stmt (a);
1425   if (stmt && stmt_ends_bb_p (stmt))
1426     return false;
1427
1428   /* Do not allow a block with only a non-local label to be merged.  */
1429   if (stmt
1430       && gimple_code (stmt) == GIMPLE_LABEL
1431       && DECL_NONLOCAL (gimple_label_label (stmt)))
1432     return false;
1433
1434   /* Examine the labels at the beginning of B.  */
1435   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1436     {
1437       tree lab;
1438       stmt = gsi_stmt (gsi);
1439       if (gimple_code (stmt) != GIMPLE_LABEL)
1440         break;
1441       lab = gimple_label_label (stmt);
1442
1443       /* Do not remove user forced labels or for -O0 any user labels.  */
1444       if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1445         return false;
1446     }
1447
1448   /* Protect the loop latches.  */
1449   if (current_loops && b->loop_father->latch == b)
1450     return false;
1451
1452   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1453      is not up-to-date and a name-mapping is registered, we cannot eliminate
1454      any phis.  Symbols marked for renaming are never a problem though.  */
1455   for (gsi = gsi_start_phis (b); !gsi_end_p (gsi); gsi_next (&gsi))
1456     {
1457       gimple phi = gsi_stmt (gsi);
1458       /* Technically only new names matter.  */
1459       if (name_registered_for_update_p (PHI_RESULT (phi)))
1460         return false;
1461     }
1462
1463   /* When not optimizing, don't merge if we'd lose goto_locus.  */
1464   if (!optimize
1465       && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1466     {
1467       location_t goto_locus = single_succ_edge (a)->goto_locus;
1468       gimple_stmt_iterator prev, next;
1469       prev = gsi_last_nondebug_bb (a);
1470       next = gsi_after_labels (b);
1471       if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1472         gsi_next_nondebug (&next);
1473       if ((gsi_end_p (prev)
1474            || gimple_location (gsi_stmt (prev)) != goto_locus)
1475           && (gsi_end_p (next)
1476               || gimple_location (gsi_stmt (next)) != goto_locus))
1477         return false;
1478     }
1479
1480   return true;
1481 }
1482
1483 /* Return true if the var whose chain of uses starts at PTR has no
1484    nondebug uses.  */
1485 bool
1486 has_zero_uses_1 (const ssa_use_operand_t *head)
1487 {
1488   const ssa_use_operand_t *ptr;
1489
1490   for (ptr = head->next; ptr != head; ptr = ptr->next)
1491     if (!is_gimple_debug (USE_STMT (ptr)))
1492       return false;
1493
1494   return true;
1495 }
1496
1497 /* Return true if the var whose chain of uses starts at PTR has a
1498    single nondebug use.  Set USE_P and STMT to that single nondebug
1499    use, if so, or to NULL otherwise.  */
1500 bool
1501 single_imm_use_1 (const ssa_use_operand_t *head,
1502                   use_operand_p *use_p, gimple *stmt)
1503 {
1504   ssa_use_operand_t *ptr, *single_use = 0;
1505
1506   for (ptr = head->next; ptr != head; ptr = ptr->next)
1507     if (!is_gimple_debug (USE_STMT (ptr)))
1508       {
1509         if (single_use)
1510           {
1511             single_use = NULL;
1512             break;
1513           }
1514         single_use = ptr;
1515       }
1516
1517   if (use_p)
1518     *use_p = single_use;
1519
1520   if (stmt)
1521     *stmt = single_use ? single_use->loc.stmt : NULL;
1522
1523   return !!single_use;
1524 }
1525
1526 /* Replaces all uses of NAME by VAL.  */
1527
1528 void
1529 replace_uses_by (tree name, tree val)
1530 {
1531   imm_use_iterator imm_iter;
1532   use_operand_p use;
1533   gimple stmt;
1534   edge e;
1535
1536   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1537     {
1538       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1539         {
1540           replace_exp (use, val);
1541
1542           if (gimple_code (stmt) == GIMPLE_PHI)
1543             {
1544               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1545               if (e->flags & EDGE_ABNORMAL)
1546                 {
1547                   /* This can only occur for virtual operands, since
1548                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1549                      would prevent replacement.  */
1550                   gcc_checking_assert (virtual_operand_p (name));
1551                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1552                 }
1553             }
1554         }
1555
1556       if (gimple_code (stmt) != GIMPLE_PHI)
1557         {
1558           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1559           gimple orig_stmt = stmt;
1560           size_t i;
1561
1562           /* Mark the block if we changed the last stmt in it.  */
1563           if (cfgcleanup_altered_bbs
1564               && stmt_ends_bb_p (stmt))
1565             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1566
1567           /* FIXME.  It shouldn't be required to keep TREE_CONSTANT
1568              on ADDR_EXPRs up-to-date on GIMPLE.  Propagation will
1569              only change sth from non-invariant to invariant, and only
1570              when propagating constants.  */
1571           if (is_gimple_min_invariant (val))
1572             for (i = 0; i < gimple_num_ops (stmt); i++)
1573               {
1574                 tree op = gimple_op (stmt, i);
1575                 /* Operands may be empty here.  For example, the labels
1576                    of a GIMPLE_COND are nulled out following the creation
1577                    of the corresponding CFG edges.  */
1578                 if (op && TREE_CODE (op) == ADDR_EXPR)
1579                   recompute_tree_invariant_for_addr_expr (op);
1580               }
1581
1582           if (fold_stmt (&gsi))
1583             stmt = gsi_stmt (gsi);
1584
1585           if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1586             gimple_purge_dead_eh_edges (gimple_bb (stmt));
1587
1588           update_stmt (stmt);
1589         }
1590     }
1591
1592   gcc_checking_assert (has_zero_uses (name));
1593
1594   /* Also update the trees stored in loop structures.  */
1595   if (current_loops)
1596     {
1597       struct loop *loop;
1598       loop_iterator li;
1599
1600       FOR_EACH_LOOP (li, loop, 0)
1601         {
1602           substitute_in_loop_info (loop, name, val);
1603         }
1604     }
1605 }
1606
1607 /* Merge block B into block A.  */
1608
1609 static void
1610 gimple_merge_blocks (basic_block a, basic_block b)
1611 {
1612   gimple_stmt_iterator last, gsi, psi;
1613
1614   if (dump_file)
1615     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1616
1617   /* Remove all single-valued PHI nodes from block B of the form
1618      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1619   gsi = gsi_last_bb (a);
1620   for (psi = gsi_start_phis (b); !gsi_end_p (psi); )
1621     {
1622       gimple phi = gsi_stmt (psi);
1623       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1624       gimple copy;
1625       bool may_replace_uses = (virtual_operand_p (def)
1626                                || may_propagate_copy (def, use));
1627
1628       /* In case we maintain loop closed ssa form, do not propagate arguments
1629          of loop exit phi nodes.  */
1630       if (current_loops
1631           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1632           && !virtual_operand_p (def)
1633           && TREE_CODE (use) == SSA_NAME
1634           && a->loop_father != b->loop_father)
1635         may_replace_uses = false;
1636
1637       if (!may_replace_uses)
1638         {
1639           gcc_assert (!virtual_operand_p (def));
1640
1641           /* Note that just emitting the copies is fine -- there is no problem
1642              with ordering of phi nodes.  This is because A is the single
1643              predecessor of B, therefore results of the phi nodes cannot
1644              appear as arguments of the phi nodes.  */
1645           copy = gimple_build_assign (def, use);
1646           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1647           remove_phi_node (&psi, false);
1648         }
1649       else
1650         {
1651           /* If we deal with a PHI for virtual operands, we can simply
1652              propagate these without fussing with folding or updating
1653              the stmt.  */
1654           if (virtual_operand_p (def))
1655             {
1656               imm_use_iterator iter;
1657               use_operand_p use_p;
1658               gimple stmt;
1659
1660               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1661                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1662                   SET_USE (use_p, use);
1663
1664               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1665                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1666             }
1667           else
1668             replace_uses_by (def, use);
1669
1670           remove_phi_node (&psi, true);
1671         }
1672     }
1673
1674   /* Ensure that B follows A.  */
1675   move_block_after (b, a);
1676
1677   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1678   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1679
1680   /* Remove labels from B and set gimple_bb to A for other statements.  */
1681   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1682     {
1683       gimple stmt = gsi_stmt (gsi);
1684       if (gimple_code (stmt) == GIMPLE_LABEL)
1685         {
1686           tree label = gimple_label_label (stmt);
1687           int lp_nr;
1688
1689           gsi_remove (&gsi, false);
1690
1691           /* Now that we can thread computed gotos, we might have
1692              a situation where we have a forced label in block B
1693              However, the label at the start of block B might still be
1694              used in other ways (think about the runtime checking for
1695              Fortran assigned gotos).  So we can not just delete the
1696              label.  Instead we move the label to the start of block A.  */
1697           if (FORCED_LABEL (label))
1698             {
1699               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1700               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1701             }
1702           /* Other user labels keep around in a form of a debug stmt.  */
1703           else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1704             {
1705               gimple dbg = gimple_build_debug_bind (label,
1706                                                     integer_zero_node,
1707                                                     stmt);
1708               gimple_debug_bind_reset_value (dbg);
1709               gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1710             }
1711
1712           lp_nr = EH_LANDING_PAD_NR (label);
1713           if (lp_nr)
1714             {
1715               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1716               lp->post_landing_pad = NULL;
1717             }
1718         }
1719       else
1720         {
1721           gimple_set_bb (stmt, a);
1722           gsi_next (&gsi);
1723         }
1724     }
1725
1726   /* Merge the sequences.  */
1727   last = gsi_last_bb (a);
1728   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1729   set_bb_seq (b, NULL);
1730
1731   if (cfgcleanup_altered_bbs)
1732     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1733 }
1734
1735
1736 /* Return the one of two successors of BB that is not reachable by a
1737    complex edge, if there is one.  Else, return BB.  We use
1738    this in optimizations that use post-dominators for their heuristics,
1739    to catch the cases in C++ where function calls are involved.  */
1740
1741 basic_block
1742 single_noncomplex_succ (basic_block bb)
1743 {
1744   edge e0, e1;
1745   if (EDGE_COUNT (bb->succs) != 2)
1746     return bb;
1747
1748   e0 = EDGE_SUCC (bb, 0);
1749   e1 = EDGE_SUCC (bb, 1);
1750   if (e0->flags & EDGE_COMPLEX)
1751     return e1->dest;
1752   if (e1->flags & EDGE_COMPLEX)
1753     return e0->dest;
1754
1755   return bb;
1756 }
1757
1758 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1759
1760 void
1761 notice_special_calls (gimple call)
1762 {
1763   int flags = gimple_call_flags (call);
1764
1765   if (flags & ECF_MAY_BE_ALLOCA)
1766     cfun->calls_alloca = true;
1767   if (flags & ECF_RETURNS_TWICE)
1768     cfun->calls_setjmp = true;
1769 }
1770
1771
1772 /* Clear flags set by notice_special_calls.  Used by dead code removal
1773    to update the flags.  */
1774
1775 void
1776 clear_special_calls (void)
1777 {
1778   cfun->calls_alloca = false;
1779   cfun->calls_setjmp = false;
1780 }
1781
1782 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1783
1784 static void
1785 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1786 {
1787   /* Since this block is no longer reachable, we can just delete all
1788      of its PHI nodes.  */
1789   remove_phi_nodes (bb);
1790
1791   /* Remove edges to BB's successors.  */
1792   while (EDGE_COUNT (bb->succs) > 0)
1793     remove_edge (EDGE_SUCC (bb, 0));
1794 }
1795
1796
1797 /* Remove statements of basic block BB.  */
1798
1799 static void
1800 remove_bb (basic_block bb)
1801 {
1802   gimple_stmt_iterator i;
1803
1804   if (dump_file)
1805     {
1806       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1807       if (dump_flags & TDF_DETAILS)
1808         {
1809           dump_bb (dump_file, bb, 0, dump_flags);
1810           fprintf (dump_file, "\n");
1811         }
1812     }
1813
1814   if (current_loops)
1815     {
1816       struct loop *loop = bb->loop_father;
1817
1818       /* If a loop gets removed, clean up the information associated
1819          with it.  */
1820       if (loop->latch == bb
1821           || loop->header == bb)
1822         free_numbers_of_iterations_estimates_loop (loop);
1823     }
1824
1825   /* Remove all the instructions in the block.  */
1826   if (bb_seq (bb) != NULL)
1827     {
1828       /* Walk backwards so as to get a chance to substitute all
1829          released DEFs into debug stmts.  See
1830          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1831          details.  */
1832       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1833         {
1834           gimple stmt = gsi_stmt (i);
1835           if (gimple_code (stmt) == GIMPLE_LABEL
1836               && (FORCED_LABEL (gimple_label_label (stmt))
1837                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1838             {
1839               basic_block new_bb;
1840               gimple_stmt_iterator new_gsi;
1841
1842               /* A non-reachable non-local label may still be referenced.
1843                  But it no longer needs to carry the extra semantics of
1844                  non-locality.  */
1845               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1846                 {
1847                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1848                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1849                 }
1850
1851               new_bb = bb->prev_bb;
1852               new_gsi = gsi_start_bb (new_bb);
1853               gsi_remove (&i, false);
1854               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1855             }
1856           else
1857             {
1858               /* Release SSA definitions if we are in SSA.  Note that we
1859                  may be called when not in SSA.  For example,
1860                  final_cleanup calls this function via
1861                  cleanup_tree_cfg.  */
1862               if (gimple_in_ssa_p (cfun))
1863                 release_defs (stmt);
1864
1865               gsi_remove (&i, true);
1866             }
1867
1868           if (gsi_end_p (i))
1869             i = gsi_last_bb (bb);
1870           else
1871             gsi_prev (&i);
1872         }
1873     }
1874
1875   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1876   bb->il.gimple.seq = NULL;
1877   bb->il.gimple.phi_nodes = NULL;
1878 }
1879
1880
1881 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1882    predicate VAL, return the edge that will be taken out of the block.
1883    If VAL does not match a unique edge, NULL is returned.  */
1884
1885 edge
1886 find_taken_edge (basic_block bb, tree val)
1887 {
1888   gimple stmt;
1889
1890   stmt = last_stmt (bb);
1891
1892   gcc_assert (stmt);
1893   gcc_assert (is_ctrl_stmt (stmt));
1894
1895   if (val == NULL)
1896     return NULL;
1897
1898   if (!is_gimple_min_invariant (val))
1899     return NULL;
1900
1901   if (gimple_code (stmt) == GIMPLE_COND)
1902     return find_taken_edge_cond_expr (bb, val);
1903
1904   if (gimple_code (stmt) == GIMPLE_SWITCH)
1905     return find_taken_edge_switch_expr (bb, val);
1906
1907   if (computed_goto_p (stmt))
1908     {
1909       /* Only optimize if the argument is a label, if the argument is
1910          not a label then we can not construct a proper CFG.
1911
1912          It may be the case that we only need to allow the LABEL_REF to
1913          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1914          appear inside a LABEL_EXPR just to be safe.  */
1915       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1916           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1917         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1918       return NULL;
1919     }
1920
1921   gcc_unreachable ();
1922 }
1923
1924 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1925    statement, determine which of the outgoing edges will be taken out of the
1926    block.  Return NULL if either edge may be taken.  */
1927
1928 static edge
1929 find_taken_edge_computed_goto (basic_block bb, tree val)
1930 {
1931   basic_block dest;
1932   edge e = NULL;
1933
1934   dest = label_to_block (val);
1935   if (dest)
1936     {
1937       e = find_edge (bb, dest);
1938       gcc_assert (e != NULL);
1939     }
1940
1941   return e;
1942 }
1943
1944 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1945    statement, determine which of the two edges will be taken out of the
1946    block.  Return NULL if either edge may be taken.  */
1947
1948 static edge
1949 find_taken_edge_cond_expr (basic_block bb, tree val)
1950 {
1951   edge true_edge, false_edge;
1952
1953   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1954
1955   gcc_assert (TREE_CODE (val) == INTEGER_CST);
1956   return (integer_zerop (val) ? false_edge : true_edge);
1957 }
1958
1959 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1960    statement, determine which edge will be taken out of the block.  Return
1961    NULL if any edge may be taken.  */
1962
1963 static edge
1964 find_taken_edge_switch_expr (basic_block bb, tree val)
1965 {
1966   basic_block dest_bb;
1967   edge e;
1968   gimple switch_stmt;
1969   tree taken_case;
1970
1971   switch_stmt = last_stmt (bb);
1972   taken_case = find_case_label_for_value (switch_stmt, val);
1973   dest_bb = label_to_block (CASE_LABEL (taken_case));
1974
1975   e = find_edge (bb, dest_bb);
1976   gcc_assert (e);
1977   return e;
1978 }
1979
1980
1981 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
1982    We can make optimal use here of the fact that the case labels are
1983    sorted: We can do a binary search for a case matching VAL.  */
1984
1985 static tree
1986 find_case_label_for_value (gimple switch_stmt, tree val)
1987 {
1988   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
1989   tree default_case = gimple_switch_default_label (switch_stmt);
1990
1991   for (low = 0, high = n; high - low > 1; )
1992     {
1993       size_t i = (high + low) / 2;
1994       tree t = gimple_switch_label (switch_stmt, i);
1995       int cmp;
1996
1997       /* Cache the result of comparing CASE_LOW and val.  */
1998       cmp = tree_int_cst_compare (CASE_LOW (t), val);
1999
2000       if (cmp > 0)
2001         high = i;
2002       else
2003         low = i;
2004
2005       if (CASE_HIGH (t) == NULL)
2006         {
2007           /* A singe-valued case label.  */
2008           if (cmp == 0)
2009             return t;
2010         }
2011       else
2012         {
2013           /* A case range.  We can only handle integer ranges.  */
2014           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2015             return t;
2016         }
2017     }
2018
2019   return default_case;
2020 }
2021
2022
2023 /* Dump a basic block on stderr.  */
2024
2025 void
2026 gimple_debug_bb (basic_block bb)
2027 {
2028   dump_bb (stderr, bb, 0, TDF_VOPS|TDF_MEMSYMS|TDF_BLOCKS);
2029 }
2030
2031
2032 /* Dump basic block with index N on stderr.  */
2033
2034 basic_block
2035 gimple_debug_bb_n (int n)
2036 {
2037   gimple_debug_bb (BASIC_BLOCK (n));
2038   return BASIC_BLOCK (n);
2039 }
2040
2041
2042 /* Dump the CFG on stderr.
2043
2044    FLAGS are the same used by the tree dumping functions
2045    (see TDF_* in dumpfile.h).  */
2046
2047 void
2048 gimple_debug_cfg (int flags)
2049 {
2050   gimple_dump_cfg (stderr, flags);
2051 }
2052
2053
2054 /* Dump the program showing basic block boundaries on the given FILE.
2055
2056    FLAGS are the same used by the tree dumping functions (see TDF_* in
2057    tree.h).  */
2058
2059 void
2060 gimple_dump_cfg (FILE *file, int flags)
2061 {
2062   if (flags & TDF_DETAILS)
2063     {
2064       dump_function_header (file, current_function_decl, flags);
2065       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2066                n_basic_blocks, n_edges, last_basic_block);
2067
2068       brief_dump_cfg (file, flags | TDF_COMMENT);
2069       fprintf (file, "\n");
2070     }
2071
2072   if (flags & TDF_STATS)
2073     dump_cfg_stats (file);
2074
2075   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2076 }
2077
2078
2079 /* Dump CFG statistics on FILE.  */
2080
2081 void
2082 dump_cfg_stats (FILE *file)
2083 {
2084   static long max_num_merged_labels = 0;
2085   unsigned long size, total = 0;
2086   long num_edges;
2087   basic_block bb;
2088   const char * const fmt_str   = "%-30s%-13s%12s\n";
2089   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2090   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2091   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2092   const char *funcname = current_function_name ();
2093
2094   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2095
2096   fprintf (file, "---------------------------------------------------------\n");
2097   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2098   fprintf (file, fmt_str, "", "  instances  ", "used ");
2099   fprintf (file, "---------------------------------------------------------\n");
2100
2101   size = n_basic_blocks * sizeof (struct basic_block_def);
2102   total += size;
2103   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2104            SCALE (size), LABEL (size));
2105
2106   num_edges = 0;
2107   FOR_EACH_BB (bb)
2108     num_edges += EDGE_COUNT (bb->succs);
2109   size = num_edges * sizeof (struct edge_def);
2110   total += size;
2111   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2112
2113   fprintf (file, "---------------------------------------------------------\n");
2114   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2115            LABEL (total));
2116   fprintf (file, "---------------------------------------------------------\n");
2117   fprintf (file, "\n");
2118
2119   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2120     max_num_merged_labels = cfg_stats.num_merged_labels;
2121
2122   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2123            cfg_stats.num_merged_labels, max_num_merged_labels);
2124
2125   fprintf (file, "\n");
2126 }
2127
2128
2129 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2130    linked in the final executable.  */
2131
2132 DEBUG_FUNCTION void
2133 debug_cfg_stats (void)
2134 {
2135   dump_cfg_stats (stderr);
2136 }
2137
2138 /*---------------------------------------------------------------------------
2139                              Miscellaneous helpers
2140 ---------------------------------------------------------------------------*/
2141
2142 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2143    flow.  Transfers of control flow associated with EH are excluded.  */
2144
2145 static bool
2146 call_can_make_abnormal_goto (gimple t)
2147 {
2148   /* If the function has no non-local labels, then a call cannot make an
2149      abnormal transfer of control.  */
2150   if (!cfun->has_nonlocal_label)
2151    return false;
2152
2153   /* Likewise if the call has no side effects.  */
2154   if (!gimple_has_side_effects (t))
2155     return false;
2156
2157   /* Likewise if the called function is leaf.  */
2158   if (gimple_call_flags (t) & ECF_LEAF)
2159     return false;
2160
2161   return true;
2162 }
2163
2164
2165 /* Return true if T can make an abnormal transfer of control flow.
2166    Transfers of control flow associated with EH are excluded.  */
2167
2168 bool
2169 stmt_can_make_abnormal_goto (gimple t)
2170 {
2171   if (computed_goto_p (t))
2172     return true;
2173   if (is_gimple_call (t))
2174     return call_can_make_abnormal_goto (t);
2175   return false;
2176 }
2177
2178
2179 /* Return true if T represents a stmt that always transfers control.  */
2180
2181 bool
2182 is_ctrl_stmt (gimple t)
2183 {
2184   switch (gimple_code (t))
2185     {
2186     case GIMPLE_COND:
2187     case GIMPLE_SWITCH:
2188     case GIMPLE_GOTO:
2189     case GIMPLE_RETURN:
2190     case GIMPLE_RESX:
2191       return true;
2192     default:
2193       return false;
2194     }
2195 }
2196
2197
2198 /* Return true if T is a statement that may alter the flow of control
2199    (e.g., a call to a non-returning function).  */
2200
2201 bool
2202 is_ctrl_altering_stmt (gimple t)
2203 {
2204   gcc_assert (t);
2205
2206   switch (gimple_code (t))
2207     {
2208     case GIMPLE_CALL:
2209       {
2210         int flags = gimple_call_flags (t);
2211
2212         /* A call alters control flow if it can make an abnormal goto.  */
2213         if (call_can_make_abnormal_goto (t))
2214           return true;
2215
2216         /* A call also alters control flow if it does not return.  */
2217         if (flags & ECF_NORETURN)
2218           return true;
2219
2220         /* TM ending statements have backedges out of the transaction.
2221            Return true so we split the basic block containing them.
2222            Note that the TM_BUILTIN test is merely an optimization.  */
2223         if ((flags & ECF_TM_BUILTIN)
2224             && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2225           return true;
2226
2227         /* BUILT_IN_RETURN call is same as return statement.  */
2228         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2229           return true;
2230       }
2231       break;
2232
2233     case GIMPLE_EH_DISPATCH:
2234       /* EH_DISPATCH branches to the individual catch handlers at
2235          this level of a try or allowed-exceptions region.  It can
2236          fallthru to the next statement as well.  */
2237       return true;
2238
2239     case GIMPLE_ASM:
2240       if (gimple_asm_nlabels (t) > 0)
2241         return true;
2242       break;
2243
2244     CASE_GIMPLE_OMP:
2245       /* OpenMP directives alter control flow.  */
2246       return true;
2247
2248     case GIMPLE_TRANSACTION:
2249       /* A transaction start alters control flow.  */
2250       return true;
2251
2252     default:
2253       break;
2254     }
2255
2256   /* If a statement can throw, it alters control flow.  */
2257   return stmt_can_throw_internal (t);
2258 }
2259
2260
2261 /* Return true if T is a simple local goto.  */
2262
2263 bool
2264 simple_goto_p (gimple t)
2265 {
2266   return (gimple_code (t) == GIMPLE_GOTO
2267           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2268 }
2269
2270
2271 /* Return true if STMT should start a new basic block.  PREV_STMT is
2272    the statement preceding STMT.  It is used when STMT is a label or a
2273    case label.  Labels should only start a new basic block if their
2274    previous statement wasn't a label.  Otherwise, sequence of labels
2275    would generate unnecessary basic blocks that only contain a single
2276    label.  */
2277
2278 static inline bool
2279 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2280 {
2281   if (stmt == NULL)
2282     return false;
2283
2284   /* Labels start a new basic block only if the preceding statement
2285      wasn't a label of the same type.  This prevents the creation of
2286      consecutive blocks that have nothing but a single label.  */
2287   if (gimple_code (stmt) == GIMPLE_LABEL)
2288     {
2289       /* Nonlocal and computed GOTO targets always start a new block.  */
2290       if (DECL_NONLOCAL (gimple_label_label (stmt))
2291           || FORCED_LABEL (gimple_label_label (stmt)))
2292         return true;
2293
2294       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2295         {
2296           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2297             return true;
2298
2299           cfg_stats.num_merged_labels++;
2300           return false;
2301         }
2302       else
2303         return true;
2304     }
2305
2306   return false;
2307 }
2308
2309
2310 /* Return true if T should end a basic block.  */
2311
2312 bool
2313 stmt_ends_bb_p (gimple t)
2314 {
2315   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2316 }
2317
2318 /* Remove block annotations and other data structures.  */
2319
2320 void
2321 delete_tree_cfg_annotations (void)
2322 {
2323   vec_free (label_to_block_map);
2324 }
2325
2326
2327 /* Return the first statement in basic block BB.  */
2328
2329 gimple
2330 first_stmt (basic_block bb)
2331 {
2332   gimple_stmt_iterator i = gsi_start_bb (bb);
2333   gimple stmt = NULL;
2334
2335   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2336     {
2337       gsi_next (&i);
2338       stmt = NULL;
2339     }
2340   return stmt;
2341 }
2342
2343 /* Return the first non-label statement in basic block BB.  */
2344
2345 static gimple
2346 first_non_label_stmt (basic_block bb)
2347 {
2348   gimple_stmt_iterator i = gsi_start_bb (bb);
2349   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2350     gsi_next (&i);
2351   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2352 }
2353
2354 /* Return the last statement in basic block BB.  */
2355
2356 gimple
2357 last_stmt (basic_block bb)
2358 {
2359   gimple_stmt_iterator i = gsi_last_bb (bb);
2360   gimple stmt = NULL;
2361
2362   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2363     {
2364       gsi_prev (&i);
2365       stmt = NULL;
2366     }
2367   return stmt;
2368 }
2369
2370 /* Return the last statement of an otherwise empty block.  Return NULL
2371    if the block is totally empty, or if it contains more than one
2372    statement.  */
2373
2374 gimple
2375 last_and_only_stmt (basic_block bb)
2376 {
2377   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2378   gimple last, prev;
2379
2380   if (gsi_end_p (i))
2381     return NULL;
2382
2383   last = gsi_stmt (i);
2384   gsi_prev_nondebug (&i);
2385   if (gsi_end_p (i))
2386     return last;
2387
2388   /* Empty statements should no longer appear in the instruction stream.
2389      Everything that might have appeared before should be deleted by
2390      remove_useless_stmts, and the optimizers should just gsi_remove
2391      instead of smashing with build_empty_stmt.
2392
2393      Thus the only thing that should appear here in a block containing
2394      one executable statement is a label.  */
2395   prev = gsi_stmt (i);
2396   if (gimple_code (prev) == GIMPLE_LABEL)
2397     return last;
2398   else
2399     return NULL;
2400 }
2401
2402 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2403
2404 static void
2405 reinstall_phi_args (edge new_edge, edge old_edge)
2406 {
2407   edge_var_map_vector *v;
2408   edge_var_map *vm;
2409   int i;
2410   gimple_stmt_iterator phis;
2411
2412   v = redirect_edge_var_map_vector (old_edge);
2413   if (!v)
2414     return;
2415
2416   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2417        v->iterate (i, &vm) && !gsi_end_p (phis);
2418        i++, gsi_next (&phis))
2419     {
2420       gimple phi = gsi_stmt (phis);
2421       tree result = redirect_edge_var_map_result (vm);
2422       tree arg = redirect_edge_var_map_def (vm);
2423
2424       gcc_assert (result == gimple_phi_result (phi));
2425
2426       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2427     }
2428
2429   redirect_edge_var_map_clear (old_edge);
2430 }
2431
2432 /* Returns the basic block after which the new basic block created
2433    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2434    near its "logical" location.  This is of most help to humans looking
2435    at debugging dumps.  */
2436
2437 static basic_block
2438 split_edge_bb_loc (edge edge_in)
2439 {
2440   basic_block dest = edge_in->dest;
2441   basic_block dest_prev = dest->prev_bb;
2442
2443   if (dest_prev)
2444     {
2445       edge e = find_edge (dest_prev, dest);
2446       if (e && !(e->flags & EDGE_COMPLEX))
2447         return edge_in->src;
2448     }
2449   return dest_prev;
2450 }
2451
2452 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2453    Abort on abnormal edges.  */
2454
2455 static basic_block
2456 gimple_split_edge (edge edge_in)
2457 {
2458   basic_block new_bb, after_bb, dest;
2459   edge new_edge, e;
2460
2461   /* Abnormal edges cannot be split.  */
2462   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2463
2464   dest = edge_in->dest;
2465
2466   after_bb = split_edge_bb_loc (edge_in);
2467
2468   new_bb = create_empty_bb (after_bb);
2469   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2470   new_bb->count = edge_in->count;
2471   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2472   new_edge->probability = REG_BR_PROB_BASE;
2473   new_edge->count = edge_in->count;
2474
2475   e = redirect_edge_and_branch (edge_in, new_bb);
2476   gcc_assert (e == edge_in);
2477   reinstall_phi_args (new_edge, e);
2478
2479   return new_bb;
2480 }
2481
2482
2483 /* Verify properties of the address expression T with base object BASE.  */
2484
2485 static tree
2486 verify_address (tree t, tree base)
2487 {
2488   bool old_constant;
2489   bool old_side_effects;
2490   bool new_constant;
2491   bool new_side_effects;
2492
2493   old_constant = TREE_CONSTANT (t);
2494   old_side_effects = TREE_SIDE_EFFECTS (t);
2495
2496   recompute_tree_invariant_for_addr_expr (t);
2497   new_side_effects = TREE_SIDE_EFFECTS (t);
2498   new_constant = TREE_CONSTANT (t);
2499
2500   if (old_constant != new_constant)
2501     {
2502       error ("constant not recomputed when ADDR_EXPR changed");
2503       return t;
2504     }
2505   if (old_side_effects != new_side_effects)
2506     {
2507       error ("side effects not recomputed when ADDR_EXPR changed");
2508       return t;
2509     }
2510
2511   if (!(TREE_CODE (base) == VAR_DECL
2512         || TREE_CODE (base) == PARM_DECL
2513         || TREE_CODE (base) == RESULT_DECL))
2514     return NULL_TREE;
2515
2516   if (DECL_GIMPLE_REG_P (base))
2517     {
2518       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2519       return base;
2520     }
2521
2522   return NULL_TREE;
2523 }
2524
2525 /* Callback for walk_tree, check that all elements with address taken are
2526    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2527    inside a PHI node.  */
2528
2529 static tree
2530 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2531 {
2532   tree t = *tp, x;
2533
2534   if (TYPE_P (t))
2535     *walk_subtrees = 0;
2536
2537   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2538 #define CHECK_OP(N, MSG) \
2539   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2540        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2541
2542   switch (TREE_CODE (t))
2543     {
2544     case SSA_NAME:
2545       if (SSA_NAME_IN_FREE_LIST (t))
2546         {
2547           error ("SSA name in freelist but still referenced");
2548           return *tp;
2549         }
2550       break;
2551
2552     case INDIRECT_REF:
2553       error ("INDIRECT_REF in gimple IL");
2554       return t;
2555
2556     case MEM_REF:
2557       x = TREE_OPERAND (t, 0);
2558       if (!POINTER_TYPE_P (TREE_TYPE (x))
2559           || !is_gimple_mem_ref_addr (x))
2560         {
2561           error ("invalid first operand of MEM_REF");
2562           return x;
2563         }
2564       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2565           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2566         {
2567           error ("invalid offset operand of MEM_REF");
2568           return TREE_OPERAND (t, 1);
2569         }
2570       if (TREE_CODE (x) == ADDR_EXPR
2571           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2572         return x;
2573       *walk_subtrees = 0;
2574       break;
2575
2576     case ASSERT_EXPR:
2577       x = fold (ASSERT_EXPR_COND (t));
2578       if (x == boolean_false_node)
2579         {
2580           error ("ASSERT_EXPR with an always-false condition");
2581           return *tp;
2582         }
2583       break;
2584
2585     case MODIFY_EXPR:
2586       error ("MODIFY_EXPR not expected while having tuples");
2587       return *tp;
2588
2589     case ADDR_EXPR:
2590       {
2591         tree tem;
2592
2593         gcc_assert (is_gimple_address (t));
2594
2595         /* Skip any references (they will be checked when we recurse down the
2596            tree) and ensure that any variable used as a prefix is marked
2597            addressable.  */
2598         for (x = TREE_OPERAND (t, 0);
2599              handled_component_p (x);
2600              x = TREE_OPERAND (x, 0))
2601           ;
2602
2603         if ((tem = verify_address (t, x)))
2604           return tem;
2605
2606         if (!(TREE_CODE (x) == VAR_DECL
2607               || TREE_CODE (x) == PARM_DECL
2608               || TREE_CODE (x) == RESULT_DECL))
2609           return NULL;
2610
2611         if (!TREE_ADDRESSABLE (x))
2612           {
2613             error ("address taken, but ADDRESSABLE bit not set");
2614             return x;
2615           }
2616
2617         break;
2618       }
2619
2620     case COND_EXPR:
2621       x = COND_EXPR_COND (t);
2622       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2623         {
2624           error ("non-integral used in condition");
2625           return x;
2626         }
2627       if (!is_gimple_condexpr (x))
2628         {
2629           error ("invalid conditional operand");
2630           return x;
2631         }
2632       break;
2633
2634     case NON_LVALUE_EXPR:
2635     case TRUTH_NOT_EXPR:
2636       gcc_unreachable ();
2637
2638     CASE_CONVERT:
2639     case FIX_TRUNC_EXPR:
2640     case FLOAT_EXPR:
2641     case NEGATE_EXPR:
2642     case ABS_EXPR:
2643     case BIT_NOT_EXPR:
2644       CHECK_OP (0, "invalid operand to unary operator");
2645       break;
2646
2647     case REALPART_EXPR:
2648     case IMAGPART_EXPR:
2649     case COMPONENT_REF:
2650     case ARRAY_REF:
2651     case ARRAY_RANGE_REF:
2652     case BIT_FIELD_REF:
2653     case VIEW_CONVERT_EXPR:
2654       /* We have a nest of references.  Verify that each of the operands
2655          that determine where to reference is either a constant or a variable,
2656          verify that the base is valid, and then show we've already checked
2657          the subtrees.  */
2658       while (handled_component_p (t))
2659         {
2660           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2661             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2662           else if (TREE_CODE (t) == ARRAY_REF
2663                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2664             {
2665               CHECK_OP (1, "invalid array index");
2666               if (TREE_OPERAND (t, 2))
2667                 CHECK_OP (2, "invalid array lower bound");
2668               if (TREE_OPERAND (t, 3))
2669                 CHECK_OP (3, "invalid array stride");
2670             }
2671           else if (TREE_CODE (t) == BIT_FIELD_REF)
2672             {
2673               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2674                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2675                 {
2676                   error ("invalid position or size operand to BIT_FIELD_REF");
2677                   return t;
2678                 }
2679               if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2680                   && (TYPE_PRECISION (TREE_TYPE (t))
2681                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2682                 {
2683                   error ("integral result type precision does not match "
2684                          "field size of BIT_FIELD_REF");
2685                   return t;
2686                 }
2687               else if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2688                        && !AGGREGATE_TYPE_P (TREE_TYPE (t))
2689                        && TYPE_MODE (TREE_TYPE (t)) != BLKmode
2690                        && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2691                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2692                 {
2693                   error ("mode precision of non-integral result does not "
2694                          "match field size of BIT_FIELD_REF");
2695                   return t;
2696                 }
2697             }
2698
2699           t = TREE_OPERAND (t, 0);
2700         }
2701
2702       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2703         {
2704           error ("invalid reference prefix");
2705           return t;
2706         }
2707       *walk_subtrees = 0;
2708       break;
2709     case PLUS_EXPR:
2710     case MINUS_EXPR:
2711       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2712          POINTER_PLUS_EXPR. */
2713       if (POINTER_TYPE_P (TREE_TYPE (t)))
2714         {
2715           error ("invalid operand to plus/minus, type is a pointer");
2716           return t;
2717         }
2718       CHECK_OP (0, "invalid operand to binary operator");
2719       CHECK_OP (1, "invalid operand to binary operator");
2720       break;
2721
2722     case POINTER_PLUS_EXPR:
2723       /* Check to make sure the first operand is a pointer or reference type. */
2724       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2725         {
2726           error ("invalid operand to pointer plus, first operand is not a pointer");
2727           return t;
2728         }
2729       /* Check to make sure the second operand is a ptrofftype.  */
2730       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2731         {
2732           error ("invalid operand to pointer plus, second operand is not an "
2733                  "integer type of appropriate width");
2734           return t;
2735         }
2736       /* FALLTHROUGH */
2737     case LT_EXPR:
2738     case LE_EXPR:
2739     case GT_EXPR:
2740     case GE_EXPR:
2741     case EQ_EXPR:
2742     case NE_EXPR:
2743     case UNORDERED_EXPR:
2744     case ORDERED_EXPR:
2745     case UNLT_EXPR:
2746     case UNLE_EXPR:
2747     case UNGT_EXPR:
2748     case UNGE_EXPR:
2749     case UNEQ_EXPR:
2750     case LTGT_EXPR:
2751     case MULT_EXPR:
2752     case TRUNC_DIV_EXPR:
2753     case CEIL_DIV_EXPR:
2754     case FLOOR_DIV_EXPR:
2755     case ROUND_DIV_EXPR:
2756     case TRUNC_MOD_EXPR:
2757     case CEIL_MOD_EXPR:
2758     case FLOOR_MOD_EXPR:
2759     case ROUND_MOD_EXPR:
2760     case RDIV_EXPR:
2761     case EXACT_DIV_EXPR:
2762     case MIN_EXPR:
2763     case MAX_EXPR:
2764     case LSHIFT_EXPR:
2765     case RSHIFT_EXPR:
2766     case LROTATE_EXPR:
2767     case RROTATE_EXPR:
2768     case BIT_IOR_EXPR:
2769     case BIT_XOR_EXPR:
2770     case BIT_AND_EXPR:
2771       CHECK_OP (0, "invalid operand to binary operator");
2772       CHECK_OP (1, "invalid operand to binary operator");
2773       break;
2774
2775     case CONSTRUCTOR:
2776       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2777         *walk_subtrees = 0;
2778       break;
2779
2780     case CASE_LABEL_EXPR:
2781       if (CASE_CHAIN (t))
2782         {
2783           error ("invalid CASE_CHAIN");
2784           return t;
2785         }
2786       break;
2787
2788     default:
2789       break;
2790     }
2791   return NULL;
2792
2793 #undef CHECK_OP
2794 }
2795
2796
2797 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2798    Returns true if there is an error, otherwise false.  */
2799
2800 static bool
2801 verify_types_in_gimple_min_lval (tree expr)
2802 {
2803   tree op;
2804
2805   if (is_gimple_id (expr))
2806     return false;
2807
2808   if (TREE_CODE (expr) != TARGET_MEM_REF
2809       && TREE_CODE (expr) != MEM_REF)
2810     {
2811       error ("invalid expression for min lvalue");
2812       return true;
2813     }
2814
2815   /* TARGET_MEM_REFs are strange beasts.  */
2816   if (TREE_CODE (expr) == TARGET_MEM_REF)
2817     return false;
2818
2819   op = TREE_OPERAND (expr, 0);
2820   if (!is_gimple_val (op))
2821     {
2822       error ("invalid operand in indirect reference");
2823       debug_generic_stmt (op);
2824       return true;
2825     }
2826   /* Memory references now generally can involve a value conversion.  */
2827
2828   return false;
2829 }
2830
2831 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2832    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2833    if there is an error, otherwise false.  */
2834
2835 static bool
2836 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2837 {
2838   while (handled_component_p (expr))
2839     {
2840       tree op = TREE_OPERAND (expr, 0);
2841
2842       if (TREE_CODE (expr) == ARRAY_REF
2843           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2844         {
2845           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2846               || (TREE_OPERAND (expr, 2)
2847                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2848               || (TREE_OPERAND (expr, 3)
2849                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2850             {
2851               error ("invalid operands to array reference");
2852               debug_generic_stmt (expr);
2853               return true;
2854             }
2855         }
2856
2857       /* Verify if the reference array element types are compatible.  */
2858       if (TREE_CODE (expr) == ARRAY_REF
2859           && !useless_type_conversion_p (TREE_TYPE (expr),
2860                                          TREE_TYPE (TREE_TYPE (op))))
2861         {
2862           error ("type mismatch in array reference");
2863           debug_generic_stmt (TREE_TYPE (expr));
2864           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2865           return true;
2866         }
2867       if (TREE_CODE (expr) == ARRAY_RANGE_REF
2868           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2869                                          TREE_TYPE (TREE_TYPE (op))))
2870         {
2871           error ("type mismatch in array range reference");
2872           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2873           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2874           return true;
2875         }
2876
2877       if ((TREE_CODE (expr) == REALPART_EXPR
2878            || TREE_CODE (expr) == IMAGPART_EXPR)
2879           && !useless_type_conversion_p (TREE_TYPE (expr),
2880                                          TREE_TYPE (TREE_TYPE (op))))
2881         {
2882           error ("type mismatch in real/imagpart reference");
2883           debug_generic_stmt (TREE_TYPE (expr));
2884           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2885           return true;
2886         }
2887
2888       if (TREE_CODE (expr) == COMPONENT_REF
2889           && !useless_type_conversion_p (TREE_TYPE (expr),
2890                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
2891         {
2892           error ("type mismatch in component reference");
2893           debug_generic_stmt (TREE_TYPE (expr));
2894           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
2895           return true;
2896         }
2897
2898       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2899         {
2900           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
2901              that their operand is not an SSA name or an invariant when
2902              requiring an lvalue (this usually means there is a SRA or IPA-SRA
2903              bug).  Otherwise there is nothing to verify, gross mismatches at
2904              most invoke undefined behavior.  */
2905           if (require_lvalue
2906               && (TREE_CODE (op) == SSA_NAME
2907                   || is_gimple_min_invariant (op)))
2908             {
2909               error ("conversion of an SSA_NAME on the left hand side");
2910               debug_generic_stmt (expr);
2911               return true;
2912             }
2913           else if (TREE_CODE (op) == SSA_NAME
2914                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
2915             {
2916               error ("conversion of register to a different size");
2917               debug_generic_stmt (expr);
2918               return true;
2919             }
2920           else if (!handled_component_p (op))
2921             return false;
2922         }
2923
2924       expr = op;
2925     }
2926
2927   if (TREE_CODE (expr) == MEM_REF)
2928     {
2929       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
2930         {
2931           error ("invalid address operand in MEM_REF");
2932           debug_generic_stmt (expr);
2933           return true;
2934         }
2935       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
2936           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
2937         {
2938           error ("invalid offset operand in MEM_REF");
2939           debug_generic_stmt (expr);
2940           return true;
2941         }
2942     }
2943   else if (TREE_CODE (expr) == TARGET_MEM_REF)
2944     {
2945       if (!TMR_BASE (expr)
2946           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
2947         {
2948           error ("invalid address operand in TARGET_MEM_REF");
2949           return true;
2950         }
2951       if (!TMR_OFFSET (expr)
2952           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
2953           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
2954         {
2955           error ("invalid offset operand in TARGET_MEM_REF");
2956           debug_generic_stmt (expr);
2957           return true;
2958         }
2959     }
2960
2961   return ((require_lvalue || !is_gimple_min_invariant (expr))
2962           && verify_types_in_gimple_min_lval (expr));
2963 }
2964
2965 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
2966    list of pointer-to types that is trivially convertible to DEST.  */
2967
2968 static bool
2969 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
2970 {
2971   tree src;
2972
2973   if (!TYPE_POINTER_TO (src_obj))
2974     return true;
2975
2976   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
2977     if (useless_type_conversion_p (dest, src))
2978       return true;
2979
2980   return false;
2981 }
2982
2983 /* Return true if TYPE1 is a fixed-point type and if conversions to and
2984    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
2985
2986 static bool
2987 valid_fixed_convert_types_p (tree type1, tree type2)
2988 {
2989   return (FIXED_POINT_TYPE_P (type1)
2990           && (INTEGRAL_TYPE_P (type2)
2991               || SCALAR_FLOAT_TYPE_P (type2)
2992               || FIXED_POINT_TYPE_P (type2)));
2993 }
2994
2995 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
2996    is a problem, otherwise false.  */
2997
2998 static bool
2999 verify_gimple_call (gimple stmt)
3000 {
3001   tree fn = gimple_call_fn (stmt);
3002   tree fntype, fndecl;
3003   unsigned i;
3004
3005   if (gimple_call_internal_p (stmt))
3006     {
3007       if (fn)
3008         {
3009           error ("gimple call has two targets");
3010           debug_generic_stmt (fn);
3011           return true;
3012         }
3013     }
3014   else
3015     {
3016       if (!fn)
3017         {
3018           error ("gimple call has no target");
3019           return true;
3020         }
3021     }
3022
3023   if (fn && !is_gimple_call_addr (fn))
3024     {
3025       error ("invalid function in gimple call");
3026       debug_generic_stmt (fn);
3027       return true;
3028     }
3029
3030   if (fn
3031       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3032           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3033               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3034     {
3035       error ("non-function in gimple call");
3036       return true;
3037     }
3038
3039    fndecl = gimple_call_fndecl (stmt);
3040    if (fndecl
3041        && TREE_CODE (fndecl) == FUNCTION_DECL
3042        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3043        && !DECL_PURE_P (fndecl)
3044        && !TREE_READONLY (fndecl))
3045      {
3046        error ("invalid pure const state for function");
3047        return true;
3048      }
3049
3050   if (gimple_call_lhs (stmt)
3051       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3052           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3053     {
3054       error ("invalid LHS in gimple call");
3055       return true;
3056     }
3057
3058   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3059     {
3060       error ("LHS in noreturn call");
3061       return true;
3062     }
3063
3064   fntype = gimple_call_fntype (stmt);
3065   if (fntype
3066       && gimple_call_lhs (stmt)
3067       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3068                                      TREE_TYPE (fntype))
3069       /* ???  At least C++ misses conversions at assignments from
3070          void * call results.
3071          ???  Java is completely off.  Especially with functions
3072          returning java.lang.Object.
3073          For now simply allow arbitrary pointer type conversions.  */
3074       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3075            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3076     {
3077       error ("invalid conversion in gimple call");
3078       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3079       debug_generic_stmt (TREE_TYPE (fntype));
3080       return true;
3081     }
3082
3083   if (gimple_call_chain (stmt)
3084       && !is_gimple_val (gimple_call_chain (stmt)))
3085     {
3086       error ("invalid static chain in gimple call");
3087       debug_generic_stmt (gimple_call_chain (stmt));
3088       return true;
3089     }
3090
3091   /* If there is a static chain argument, this should not be an indirect
3092      call, and the decl should have DECL_STATIC_CHAIN set.  */
3093   if (gimple_call_chain (stmt))
3094     {
3095       if (!gimple_call_fndecl (stmt))
3096         {
3097           error ("static chain in indirect gimple call");
3098           return true;
3099         }
3100       fn = TREE_OPERAND (fn, 0);
3101
3102       if (!DECL_STATIC_CHAIN (fn))
3103         {
3104           error ("static chain with function that doesn%'t use one");
3105           return true;
3106         }
3107     }
3108
3109   /* ???  The C frontend passes unpromoted arguments in case it
3110      didn't see a function declaration before the call.  So for now
3111      leave the call arguments mostly unverified.  Once we gimplify
3112      unit-at-a-time we have a chance to fix this.  */
3113
3114   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3115     {
3116       tree arg = gimple_call_arg (stmt, i);
3117       if ((is_gimple_reg_type (TREE_TYPE (arg))
3118            && !is_gimple_val (arg))
3119           || (!is_gimple_reg_type (TREE_TYPE (arg))
3120               && !is_gimple_lvalue (arg)))
3121         {
3122           error ("invalid argument to gimple call");
3123           debug_generic_expr (arg);
3124           return true;
3125         }
3126     }
3127
3128   return false;
3129 }
3130
3131 /* Verifies the gimple comparison with the result type TYPE and
3132    the operands OP0 and OP1.  */
3133
3134 static bool
3135 verify_gimple_comparison (tree type, tree op0, tree op1)
3136 {
3137   tree op0_type = TREE_TYPE (op0);
3138   tree op1_type = TREE_TYPE (op1);
3139
3140   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3141     {
3142       error ("invalid operands in gimple comparison");
3143       return true;
3144     }
3145
3146   /* For comparisons we do not have the operations type as the
3147      effective type the comparison is carried out in.  Instead
3148      we require that either the first operand is trivially
3149      convertible into the second, or the other way around.
3150      Because we special-case pointers to void we allow
3151      comparisons of pointers with the same mode as well.  */
3152   if (!useless_type_conversion_p (op0_type, op1_type)
3153       && !useless_type_conversion_p (op1_type, op0_type)
3154       && (!POINTER_TYPE_P (op0_type)
3155           || !POINTER_TYPE_P (op1_type)
3156           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3157     {
3158       error ("mismatching comparison operand types");
3159       debug_generic_expr (op0_type);
3160       debug_generic_expr (op1_type);
3161       return true;
3162     }
3163
3164   /* The resulting type of a comparison may be an effective boolean type.  */
3165   if (INTEGRAL_TYPE_P (type)
3166       && (TREE_CODE (type) == BOOLEAN_TYPE
3167           || TYPE_PRECISION (type) == 1))
3168     {
3169       if (TREE_CODE (op0_type) == VECTOR_TYPE
3170           || TREE_CODE (op1_type) == VECTOR_TYPE)
3171         {
3172           error ("vector comparison returning a boolean");
3173           debug_generic_expr (op0_type);
3174           debug_generic_expr (op1_type);
3175           return true;
3176         }
3177     }
3178   /* Or an integer vector type with the same size and element count
3179      as the comparison operand types.  */
3180   else if (TREE_CODE (type) == VECTOR_TYPE
3181            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3182     {
3183       if (TREE_CODE (op0_type) != VECTOR_TYPE
3184           || TREE_CODE (op1_type) != VECTOR_TYPE)
3185         {
3186           error ("non-vector operands in vector comparison");
3187           debug_generic_expr (op0_type);
3188           debug_generic_expr (op1_type);
3189           return true;
3190         }
3191
3192       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3193           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3194               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3195         {
3196           error ("invalid vector comparison resulting type");
3197           debug_generic_expr (type);
3198           return true;
3199         }
3200     }
3201   else
3202     {
3203       error ("bogus comparison result type");
3204       debug_generic_expr (type);
3205       return true;
3206     }
3207
3208   return false;
3209 }
3210
3211 /* Verify a gimple assignment statement STMT with an unary rhs.
3212    Returns true if anything is wrong.  */
3213
3214 static bool
3215 verify_gimple_assign_unary (gimple stmt)
3216 {
3217   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3218   tree lhs = gimple_assign_lhs (stmt);
3219   tree lhs_type = TREE_TYPE (lhs);
3220   tree rhs1 = gimple_assign_rhs1 (stmt);
3221   tree rhs1_type = TREE_TYPE (rhs1);
3222
3223   if (!is_gimple_reg (lhs))
3224     {
3225       error ("non-register as LHS of unary operation");
3226       return true;
3227     }
3228
3229   if (!is_gimple_val (rhs1))
3230     {
3231       error ("invalid operand in unary operation");
3232       return true;
3233     }
3234
3235   /* First handle conversions.  */
3236   switch (rhs_code)
3237     {
3238     CASE_CONVERT:
3239       {
3240         /* Allow conversions from pointer type to integral type only if
3241            there is no sign or zero extension involved.
3242            For targets were the precision of ptrofftype doesn't match that
3243            of pointers we need to allow arbitrary conversions to ptrofftype.  */
3244         if ((POINTER_TYPE_P (lhs_type)
3245              && INTEGRAL_TYPE_P (rhs1_type))
3246             || (POINTER_TYPE_P (rhs1_type)
3247                 && INTEGRAL_TYPE_P (lhs_type)
3248                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3249                     || ptrofftype_p (sizetype))))
3250           return false;
3251
3252         /* Allow conversion from integral to offset type and vice versa.  */
3253         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3254              && INTEGRAL_TYPE_P (rhs1_type))
3255             || (INTEGRAL_TYPE_P (lhs_type)
3256                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3257           return false;
3258
3259         /* Otherwise assert we are converting between types of the
3260            same kind.  */
3261         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3262           {
3263             error ("invalid types in nop conversion");
3264             debug_generic_expr (lhs_type);
3265             debug_generic_expr (rhs1_type);
3266             return true;
3267           }
3268
3269         return false;
3270       }
3271
3272     case ADDR_SPACE_CONVERT_EXPR:
3273       {
3274         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3275             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3276                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3277           {
3278             error ("invalid types in address space conversion");
3279             debug_generic_expr (lhs_type);
3280             debug_generic_expr (rhs1_type);
3281             return true;
3282           }
3283
3284         return false;
3285       }
3286
3287     case FIXED_CONVERT_EXPR:
3288       {
3289         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3290             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3291           {
3292             error ("invalid types in fixed-point conversion");
3293             debug_generic_expr (lhs_type);
3294             debug_generic_expr (rhs1_type);
3295             return true;
3296           }
3297
3298         return false;
3299       }
3300
3301     case FLOAT_EXPR:
3302       {
3303         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3304             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3305                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3306           {
3307             error ("invalid types in conversion to floating point");
3308             debug_generic_expr (lhs_type);
3309             debug_generic_expr (rhs1_type);
3310             return true;
3311           }
3312
3313         return false;
3314       }
3315
3316     case FIX_TRUNC_EXPR:
3317       {
3318         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3319             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3320                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3321           {
3322             error ("invalid types in conversion to integer");
3323             debug_generic_expr (lhs_type);
3324             debug_generic_expr (rhs1_type);
3325             return true;
3326           }
3327
3328         return false;
3329       }
3330
3331     case VEC_UNPACK_HI_EXPR:
3332     case VEC_UNPACK_LO_EXPR:
3333     case REDUC_MAX_EXPR:
3334     case REDUC_MIN_EXPR:
3335     case REDUC_PLUS_EXPR:
3336     case VEC_UNPACK_FLOAT_HI_EXPR:
3337     case VEC_UNPACK_FLOAT_LO_EXPR:
3338       /* FIXME.  */
3339       return false;
3340
3341     case NEGATE_EXPR:
3342     case ABS_EXPR:
3343     case BIT_NOT_EXPR:
3344     case PAREN_EXPR:
3345     case NON_LVALUE_EXPR:
3346     case CONJ_EXPR:
3347       break;
3348
3349     default:
3350       gcc_unreachable ();
3351     }
3352
3353   /* For the remaining codes assert there is no conversion involved.  */
3354   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3355     {
3356       error ("non-trivial conversion in unary operation");
3357       debug_generic_expr (lhs_type);
3358       debug_generic_expr (rhs1_type);
3359       return true;
3360     }
3361
3362   return false;
3363 }
3364
3365 /* Verify a gimple assignment statement STMT with a binary rhs.
3366    Returns true if anything is wrong.  */
3367
3368 static bool
3369 verify_gimple_assign_binary (gimple stmt)
3370 {
3371   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3372   tree lhs = gimple_assign_lhs (stmt);
3373   tree lhs_type = TREE_TYPE (lhs);
3374   tree rhs1 = gimple_assign_rhs1 (stmt);
3375   tree rhs1_type = TREE_TYPE (rhs1);
3376   tree rhs2 = gimple_assign_rhs2 (stmt);
3377   tree rhs2_type = TREE_TYPE (rhs2);
3378
3379   if (!is_gimple_reg (lhs))
3380     {
3381       error ("non-register as LHS of binary operation");
3382       return true;
3383     }
3384
3385   if (!is_gimple_val (rhs1)
3386       || !is_gimple_val (rhs2))
3387     {
3388       error ("invalid operands in binary operation");
3389       return true;
3390     }
3391
3392   /* First handle operations that involve different types.  */
3393   switch (rhs_code)
3394     {
3395     case COMPLEX_EXPR:
3396       {
3397         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3398             || !(INTEGRAL_TYPE_P (rhs1_type)
3399                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3400             || !(INTEGRAL_TYPE_P (rhs2_type)
3401                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3402           {
3403             error ("type mismatch in complex expression");
3404             debug_generic_expr (lhs_type);
3405             debug_generic_expr (rhs1_type);
3406             debug_generic_expr (rhs2_type);
3407             return true;
3408           }
3409
3410         return false;
3411       }
3412
3413     case LSHIFT_EXPR:
3414     case RSHIFT_EXPR:
3415     case LROTATE_EXPR:
3416     case RROTATE_EXPR:
3417       {
3418         /* Shifts and rotates are ok on integral types, fixed point
3419            types and integer vector types.  */
3420         if ((!INTEGRAL_TYPE_P (rhs1_type)
3421              && !FIXED_POINT_TYPE_P (rhs1_type)
3422              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3423                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3424             || (!INTEGRAL_TYPE_P (rhs2_type)
3425                 /* Vector shifts of vectors are also ok.  */
3426                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3427                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3428                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3429                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3430             || !useless_type_conversion_p (lhs_type, rhs1_type))
3431           {
3432             error ("type mismatch in shift expression");
3433             debug_generic_expr (lhs_type);
3434             debug_generic_expr (rhs1_type);
3435             debug_generic_expr (rhs2_type);
3436             return true;
3437           }
3438
3439         return false;
3440       }
3441
3442     case VEC_LSHIFT_EXPR:
3443     case VEC_RSHIFT_EXPR:
3444       {
3445         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3446             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3447                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3448                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3449                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3450             || (!INTEGRAL_TYPE_P (rhs2_type)
3451                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3452                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3453             || !useless_type_conversion_p (lhs_type, rhs1_type))
3454           {
3455             error ("type mismatch in vector shift expression");
3456             debug_generic_expr (lhs_type);
3457             debug_generic_expr (rhs1_type);
3458             debug_generic_expr (rhs2_type);
3459             return true;
3460           }
3461         /* For shifting a vector of non-integral components we
3462            only allow shifting by a constant multiple of the element size.  */
3463         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3464             && (TREE_CODE (rhs2) != INTEGER_CST
3465                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3466                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3467           {
3468             error ("non-element sized vector shift of floating point vector");
3469             return true;
3470           }
3471
3472         return false;
3473       }
3474
3475     case WIDEN_LSHIFT_EXPR:
3476       {
3477         if (!INTEGRAL_TYPE_P (lhs_type)
3478             || !INTEGRAL_TYPE_P (rhs1_type)
3479             || TREE_CODE (rhs2) != INTEGER_CST
3480             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3481           {
3482             error ("type mismatch in widening vector shift expression");
3483             debug_generic_expr (lhs_type);
3484             debug_generic_expr (rhs1_type);
3485             debug_generic_expr (rhs2_type);
3486             return true;
3487           }
3488
3489         return false;
3490       }
3491
3492     case VEC_WIDEN_LSHIFT_HI_EXPR:
3493     case VEC_WIDEN_LSHIFT_LO_EXPR:
3494       {
3495         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3496             || TREE_CODE (lhs_type) != VECTOR_TYPE
3497             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3498             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3499             || TREE_CODE (rhs2) != INTEGER_CST
3500             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3501                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3502           {
3503             error ("type mismatch in widening vector shift expression");
3504             debug_generic_expr (lhs_type);
3505             debug_generic_expr (rhs1_type);
3506             debug_generic_expr (rhs2_type);
3507             return true;
3508           }
3509
3510         return false;
3511       }
3512
3513     case PLUS_EXPR:
3514     case MINUS_EXPR:
3515       {
3516         /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3517            ???  This just makes the checker happy and may not be what is
3518            intended.  */
3519         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3520             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3521           {
3522             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3523                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3524               {
3525                 error ("invalid non-vector operands to vector valued plus");
3526                 return true;
3527               }
3528             lhs_type = TREE_TYPE (lhs_type);
3529             rhs1_type = TREE_TYPE (rhs1_type);
3530             rhs2_type = TREE_TYPE (rhs2_type);
3531             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3532                the pointer to 2nd place.  */
3533             if (POINTER_TYPE_P (rhs2_type))
3534               {
3535                 tree tem = rhs1_type;
3536                 rhs1_type = rhs2_type;
3537                 rhs2_type = tem;
3538               }
3539             goto do_pointer_plus_expr_check;
3540           }
3541         if (POINTER_TYPE_P (lhs_type)
3542             || POINTER_TYPE_P (rhs1_type)
3543             || POINTER_TYPE_P (rhs2_type))
3544           {
3545             error ("invalid (pointer) operands to plus/minus");
3546             return true;
3547           }
3548
3549         /* Continue with generic binary expression handling.  */
3550         break;
3551       }
3552
3553     case POINTER_PLUS_EXPR:
3554       {
3555 do_pointer_plus_expr_check:
3556         if (!POINTER_TYPE_P (rhs1_type)
3557             || !useless_type_conversion_p (lhs_type, rhs1_type)
3558             || !ptrofftype_p (rhs2_type))
3559           {
3560             error ("type mismatch in pointer plus expression");
3561             debug_generic_stmt (lhs_type);
3562             debug_generic_stmt (rhs1_type);
3563             debug_generic_stmt (rhs2_type);
3564             return true;
3565           }
3566
3567         return false;
3568       }
3569
3570     case TRUTH_ANDIF_EXPR:
3571     case TRUTH_ORIF_EXPR:
3572     case TRUTH_AND_EXPR:
3573     case TRUTH_OR_EXPR:
3574     case TRUTH_XOR_EXPR:
3575
3576       gcc_unreachable ();
3577
3578     case LT_EXPR:
3579     case LE_EXPR:
3580     case GT_EXPR:
3581     case GE_EXPR:
3582     case EQ_EXPR:
3583     case NE_EXPR:
3584     case UNORDERED_EXPR:
3585     case ORDERED_EXPR:
3586     case UNLT_EXPR:
3587     case UNLE_EXPR:
3588     case UNGT_EXPR:
3589     case UNGE_EXPR:
3590     case UNEQ_EXPR:
3591     case LTGT_EXPR:
3592       /* Comparisons are also binary, but the result type is not
3593          connected to the operand types.  */
3594       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3595
3596     case WIDEN_MULT_EXPR:
3597       if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3598         return true;
3599       return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3600               || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3601
3602     case WIDEN_SUM_EXPR:
3603     case VEC_WIDEN_MULT_HI_EXPR:
3604     case VEC_WIDEN_MULT_LO_EXPR:
3605     case VEC_WIDEN_MULT_EVEN_EXPR:
3606     case VEC_WIDEN_MULT_ODD_EXPR:
3607     case VEC_PACK_TRUNC_EXPR:
3608     case VEC_PACK_SAT_EXPR:
3609     case VEC_PACK_FIX_TRUNC_EXPR:
3610       /* FIXME.  */
3611       return false;
3612
3613     case MULT_EXPR:
3614     case MULT_HIGHPART_EXPR:
3615     case TRUNC_DIV_EXPR:
3616     case CEIL_DIV_EXPR:
3617     case FLOOR_DIV_EXPR:
3618     case ROUND_DIV_EXPR:
3619     case TRUNC_MOD_EXPR:
3620     case CEIL_MOD_EXPR:
3621     case FLOOR_MOD_EXPR:
3622     case ROUND_MOD_EXPR:
3623     case RDIV_EXPR:
3624     case EXACT_DIV_EXPR:
3625     case MIN_EXPR:
3626     case MAX_EXPR:
3627     case BIT_IOR_EXPR:
3628     case BIT_XOR_EXPR:
3629     case BIT_AND_EXPR:
3630       /* Continue with generic binary expression handling.  */
3631       break;
3632
3633     default:
3634       gcc_unreachable ();
3635     }
3636
3637   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3638       || !useless_type_conversion_p (lhs_type, rhs2_type))
3639     {
3640       error ("type mismatch in binary expression");
3641       debug_generic_stmt (lhs_type);
3642       debug_generic_stmt (rhs1_type);
3643       debug_generic_stmt (rhs2_type);
3644       return true;
3645     }
3646
3647   return false;
3648 }
3649
3650 /* Verify a gimple assignment statement STMT with a ternary rhs.
3651    Returns true if anything is wrong.  */
3652
3653 static bool
3654 verify_gimple_assign_ternary (gimple stmt)
3655 {
3656   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3657   tree lhs = gimple_assign_lhs (stmt);
3658   tree lhs_type = TREE_TYPE (lhs);
3659   tree rhs1 = gimple_assign_rhs1 (stmt);
3660   tree rhs1_type = TREE_TYPE (rhs1);
3661   tree rhs2 = gimple_assign_rhs2 (stmt);
3662   tree rhs2_type = TREE_TYPE (rhs2);
3663   tree rhs3 = gimple_assign_rhs3 (stmt);
3664   tree rhs3_type = TREE_TYPE (rhs3);
3665
3666   if (!is_gimple_reg (lhs))
3667     {
3668       error ("non-register as LHS of ternary operation");
3669       return true;
3670     }
3671
3672   if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3673        ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3674       || !is_gimple_val (rhs2)
3675       || !is_gimple_val (rhs3))
3676     {
3677       error ("invalid operands in ternary operation");
3678       return true;
3679     }
3680
3681   /* First handle operations that involve different types.  */
3682   switch (rhs_code)
3683     {
3684     case WIDEN_MULT_PLUS_EXPR:
3685     case WIDEN_MULT_MINUS_EXPR:
3686       if ((!INTEGRAL_TYPE_P (rhs1_type)
3687            && !FIXED_POINT_TYPE_P (rhs1_type))
3688           || !useless_type_conversion_p (rhs1_type, rhs2_type)
3689           || !useless_type_conversion_p (lhs_type, rhs3_type)
3690           || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3691           || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3692         {
3693           error ("type mismatch in widening multiply-accumulate expression");
3694           debug_generic_expr (lhs_type);
3695           debug_generic_expr (rhs1_type);
3696           debug_generic_expr (rhs2_type);
3697           debug_generic_expr (rhs3_type);
3698           return true;
3699         }
3700       break;
3701
3702     case FMA_EXPR:
3703       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3704           || !useless_type_conversion_p (lhs_type, rhs2_type)
3705           || !useless_type_conversion_p (lhs_type, rhs3_type))
3706         {
3707           error ("type mismatch in fused multiply-add expression");
3708           debug_generic_expr (lhs_type);
3709           debug_generic_expr (rhs1_type);
3710           debug_generic_expr (rhs2_type);
3711           debug_generic_expr (rhs3_type);
3712           return true;
3713         }
3714       break;
3715
3716     case COND_EXPR:
3717     case VEC_COND_EXPR:
3718       if (!useless_type_conversion_p (lhs_type, rhs2_type)
3719           || !useless_type_conversion_p (lhs_type, rhs3_type))
3720         {
3721           error ("type mismatch in conditional expression");
3722           debug_generic_expr (lhs_type);
3723           debug_generic_expr (rhs2_type);
3724           debug_generic_expr (rhs3_type);
3725           return true;
3726         }
3727       break;
3728
3729     case VEC_PERM_EXPR:
3730       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3731           || !useless_type_conversion_p (lhs_type, rhs2_type))
3732         {
3733           error ("type mismatch in vector permute expression");
3734           debug_generic_expr (lhs_type);
3735           debug_generic_expr (rhs1_type);
3736           debug_generic_expr (rhs2_type);
3737           debug_generic_expr (rhs3_type);
3738           return true;
3739         }
3740
3741       if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3742           || TREE_CODE (rhs2_type) != VECTOR_TYPE
3743           || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3744         {
3745           error ("vector types expected in vector permute expression");
3746           debug_generic_expr (lhs_type);
3747           debug_generic_expr (rhs1_type);
3748           debug_generic_expr (rhs2_type);
3749           debug_generic_expr (rhs3_type);
3750           return true;
3751         }
3752
3753       if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3754           || TYPE_VECTOR_SUBPARTS (rhs2_type)
3755              != TYPE_VECTOR_SUBPARTS (rhs3_type)
3756           || TYPE_VECTOR_SUBPARTS (rhs3_type)
3757              != TYPE_VECTOR_SUBPARTS (lhs_type))
3758         {
3759           error ("vectors with different element number found "
3760                  "in vector permute expression");
3761           debug_generic_expr (lhs_type);
3762           debug_generic_expr (rhs1_type);
3763           debug_generic_expr (rhs2_type);
3764           debug_generic_expr (rhs3_type);
3765           return true;
3766         }
3767
3768       if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3769           || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3770              != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3771         {
3772           error ("invalid mask type in vector permute expression");
3773           debug_generic_expr (lhs_type);
3774           debug_generic_expr (rhs1_type);
3775           debug_generic_expr (rhs2_type);
3776           debug_generic_expr (rhs3_type);
3777           return true;
3778         }
3779
3780       return false;
3781
3782     case DOT_PROD_EXPR:
3783     case REALIGN_LOAD_EXPR:
3784       /* FIXME.  */
3785       return false;
3786
3787     default:
3788       gcc_unreachable ();
3789     }
3790   return false;
3791 }
3792
3793 /* Verify a gimple assignment statement STMT with a single rhs.
3794    Returns true if anything is wrong.  */
3795
3796 static bool
3797 verify_gimple_assign_single (gimple stmt)
3798 {
3799   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3800   tree lhs = gimple_assign_lhs (stmt);
3801   tree lhs_type = TREE_TYPE (lhs);
3802   tree rhs1 = gimple_assign_rhs1 (stmt);
3803   tree rhs1_type = TREE_TYPE (rhs1);
3804   bool res = false;
3805
3806   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3807     {
3808       error ("non-trivial conversion at assignment");
3809       debug_generic_expr (lhs_type);
3810       debug_generic_expr (rhs1_type);
3811       return true;
3812     }
3813
3814   if (gimple_clobber_p (stmt)
3815       && !DECL_P (lhs))
3816     {
3817       error ("non-decl LHS in clobber statement");
3818       debug_generic_expr (lhs);
3819       return true;
3820     }
3821
3822   if (handled_component_p (lhs))
3823     res |= verify_types_in_gimple_reference (lhs, true);
3824
3825   /* Special codes we cannot handle via their class.  */
3826   switch (rhs_code)
3827     {
3828     case ADDR_EXPR:
3829       {
3830         tree op = TREE_OPERAND (rhs1, 0);
3831         if (!is_gimple_addressable (op))
3832           {
3833             error ("invalid operand in unary expression");
3834             return true;
3835           }
3836
3837         /* Technically there is no longer a need for matching types, but
3838            gimple hygiene asks for this check.  In LTO we can end up
3839            combining incompatible units and thus end up with addresses
3840            of globals that change their type to a common one.  */
3841         if (!in_lto_p
3842             && !types_compatible_p (TREE_TYPE (op),
3843                                     TREE_TYPE (TREE_TYPE (rhs1)))
3844             && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3845                                                           TREE_TYPE (op)))
3846           {
3847             error ("type mismatch in address expression");
3848             debug_generic_stmt (TREE_TYPE (rhs1));
3849             debug_generic_stmt (TREE_TYPE (op));
3850             return true;
3851           }
3852
3853         return verify_types_in_gimple_reference (op, true);
3854       }
3855
3856     /* tcc_reference  */
3857     case INDIRECT_REF:
3858       error ("INDIRECT_REF in gimple IL");
3859       return true;
3860
3861     case COMPONENT_REF:
3862     case BIT_FIELD_REF:
3863     case ARRAY_REF:
3864     case ARRAY_RANGE_REF:
3865     case VIEW_CONVERT_EXPR:
3866     case REALPART_EXPR:
3867     case IMAGPART_EXPR:
3868     case TARGET_MEM_REF:
3869     case MEM_REF:
3870       if (!is_gimple_reg (lhs)
3871           && is_gimple_reg_type (TREE_TYPE (lhs)))
3872         {
3873           error ("invalid rhs for gimple memory store");
3874           debug_generic_stmt (lhs);
3875           debug_generic_stmt (rhs1);
3876           return true;
3877         }
3878       return res || verify_types_in_gimple_reference (rhs1, false);
3879
3880     /* tcc_constant  */
3881     case SSA_NAME:
3882     case INTEGER_CST:
3883     case REAL_CST:
3884     case FIXED_CST:
3885     case COMPLEX_CST:
3886     case VECTOR_CST:
3887     case STRING_CST:
3888       return res;
3889
3890     /* tcc_declaration  */
3891     case CONST_DECL:
3892       return res;
3893     case VAR_DECL:
3894     case PARM_DECL:
3895       if (!is_gimple_reg (lhs)
3896           && !is_gimple_reg (rhs1)
3897           && is_gimple_reg_type (TREE_TYPE (lhs)))
3898         {
3899           error ("invalid rhs for gimple memory store");
3900           debug_generic_stmt (lhs);
3901           debug_generic_stmt (rhs1);
3902           return true;
3903         }
3904       return res;
3905
3906     case CONSTRUCTOR:
3907       if (TREE_CODE (rhs1_type) == VECTOR_TYPE)
3908         {
3909           unsigned int i;
3910           tree elt_i, elt_v, elt_t = NULL_TREE;
3911
3912           if (CONSTRUCTOR_NELTS (rhs1) == 0)
3913             return res;
3914           /* For vector CONSTRUCTORs we require that either it is empty
3915              CONSTRUCTOR, or it is a CONSTRUCTOR of smaller vector elements
3916              (then the element count must be correct to cover the whole
3917              outer vector and index must be NULL on all elements, or it is
3918              a CONSTRUCTOR of scalar elements, where we as an exception allow
3919              smaller number of elements (assuming zero filling) and
3920              consecutive indexes as compared to NULL indexes (such
3921              CONSTRUCTORs can appear in the IL from FEs).  */
3922           FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (rhs1), i, elt_i, elt_v)
3923             {
3924               if (elt_t == NULL_TREE)
3925                 {
3926                   elt_t = TREE_TYPE (elt_v);
3927                   if (TREE_CODE (elt_t) == VECTOR_TYPE)
3928                     {
3929                       tree elt_t = TREE_TYPE (elt_v);
3930                       if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
3931                                                       TREE_TYPE (elt_t)))
3932                         {
3933                           error ("incorrect type of vector CONSTRUCTOR"
3934                                  " elements");
3935                           debug_generic_stmt (rhs1);
3936                           return true;
3937                         }
3938                       else if (CONSTRUCTOR_NELTS (rhs1)
3939                                * TYPE_VECTOR_SUBPARTS (elt_t)
3940                                != TYPE_VECTOR_SUBPARTS (rhs1_type))
3941                         {
3942                           error ("incorrect number of vector CONSTRUCTOR"
3943                                  " elements");
3944                           debug_generic_stmt (rhs1);
3945                           return true;
3946                         }
3947                     }
3948                   else if (!useless_type_conversion_p (TREE_TYPE (rhs1_type),
3949                                                        elt_t))
3950                     {
3951                       error ("incorrect type of vector CONSTRUCTOR elements");
3952                       debug_generic_stmt (rhs1);
3953                       return true;
3954                     }
3955                   else if (CONSTRUCTOR_NELTS (rhs1)
3956                            > TYPE_VECTOR_SUBPARTS (rhs1_type))
3957                     {
3958                       error ("incorrect number of vector CONSTRUCTOR elements");
3959                       debug_generic_stmt (rhs1);
3960                       return true;
3961                     }
3962                 }
3963               else if (!useless_type_conversion_p (elt_t, TREE_TYPE (elt_v)))
3964                 {
3965                   error ("incorrect type of vector CONSTRUCTOR elements");
3966                   debug_generic_stmt (rhs1);
3967                   return true;
3968                 }
3969               if (elt_i != NULL_TREE
3970                   && (TREE_CODE (elt_t) == VECTOR_TYPE
3971                       || TREE_CODE (elt_i) != INTEGER_CST
3972                       || compare_tree_int (elt_i, i) != 0))
3973                 {
3974                   error ("vector CONSTRUCTOR with non-NULL element index");
3975                   debug_generic_stmt (rhs1);
3976                   return true;
3977                 }
3978             }
3979         }
3980       return res;
3981     case OBJ_TYPE_REF:
3982     case ASSERT_EXPR:
3983     case WITH_SIZE_EXPR:
3984       /* FIXME.  */
3985       return res;
3986
3987     default:;
3988     }
3989
3990   return res;
3991 }
3992
3993 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
3994    is a problem, otherwise false.  */
3995
3996 static bool
3997 verify_gimple_assign (gimple stmt)
3998 {
3999   switch (gimple_assign_rhs_class (stmt))
4000     {
4001     case GIMPLE_SINGLE_RHS:
4002       return verify_gimple_assign_single (stmt);
4003
4004     case GIMPLE_UNARY_RHS:
4005       return verify_gimple_assign_unary (stmt);
4006
4007     case GIMPLE_BINARY_RHS:
4008       return verify_gimple_assign_binary (stmt);
4009
4010     case GIMPLE_TERNARY_RHS:
4011       return verify_gimple_assign_ternary (stmt);
4012
4013     default:
4014       gcc_unreachable ();
4015     }
4016 }
4017
4018 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
4019    is a problem, otherwise false.  */
4020
4021 static bool
4022 verify_gimple_return (gimple stmt)
4023 {
4024   tree op = gimple_return_retval (stmt);
4025   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4026
4027   /* We cannot test for present return values as we do not fix up missing
4028      return values from the original source.  */
4029   if (op == NULL)
4030     return false;
4031
4032   if (!is_gimple_val (op)
4033       && TREE_CODE (op) != RESULT_DECL)
4034     {
4035       error ("invalid operand in return statement");
4036       debug_generic_stmt (op);
4037       return true;
4038     }
4039
4040   if ((TREE_CODE (op) == RESULT_DECL
4041        && DECL_BY_REFERENCE (op))
4042       || (TREE_CODE (op) == SSA_NAME
4043           && SSA_NAME_VAR (op)
4044           && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4045           && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4046     op = TREE_TYPE (op);
4047
4048   if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4049     {
4050       error ("invalid conversion in return statement");
4051       debug_generic_stmt (restype);
4052       debug_generic_stmt (TREE_TYPE (op));
4053       return true;
4054     }
4055
4056   return false;
4057 }
4058
4059
4060 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
4061    is a problem, otherwise false.  */
4062
4063 static bool
4064 verify_gimple_goto (gimple stmt)
4065 {
4066   tree dest = gimple_goto_dest (stmt);
4067
4068   /* ???  We have two canonical forms of direct goto destinations, a
4069      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
4070   if (TREE_CODE (dest) != LABEL_DECL
4071       && (!is_gimple_val (dest)
4072           || !POINTER_TYPE_P (TREE_TYPE (dest))))
4073     {
4074       error ("goto destination is neither a label nor a pointer");
4075       return true;
4076     }
4077
4078   return false;
4079 }
4080
4081 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
4082    is a problem, otherwise false.  */
4083
4084 static bool
4085 verify_gimple_switch (gimple stmt)
4086 {
4087   unsigned int i, n;
4088   tree elt, prev_upper_bound = NULL_TREE;
4089   tree index_type, elt_type = NULL_TREE;
4090
4091   if (!is_gimple_val (gimple_switch_index (stmt)))
4092     {
4093       error ("invalid operand to switch statement");
4094       debug_generic_stmt (gimple_switch_index (stmt));
4095       return true;
4096     }
4097
4098   index_type = TREE_TYPE (gimple_switch_index (stmt));
4099   if (! INTEGRAL_TYPE_P (index_type))
4100     {
4101       error ("non-integral type switch statement");
4102       debug_generic_expr (index_type);
4103       return true;
4104     }
4105
4106   elt = gimple_switch_label (stmt, 0);
4107   if (CASE_LOW (elt) != NULL_TREE || CASE_HIGH (elt) != NULL_TREE)
4108     {
4109       error ("invalid default case label in switch statement");
4110       debug_generic_expr (elt);
4111       return true;
4112     }
4113
4114   n = gimple_switch_num_labels (stmt);
4115   for (i = 1; i < n; i++)
4116     {
4117       elt = gimple_switch_label (stmt, i);
4118
4119       if (! CASE_LOW (elt))
4120         {
4121           error ("invalid case label in switch statement");
4122           debug_generic_expr (elt);
4123           return true;
4124         }
4125       if (CASE_HIGH (elt)
4126           && ! tree_int_cst_lt (CASE_LOW (elt), CASE_HIGH (elt)))
4127         {
4128           error ("invalid case range in switch statement");
4129           debug_generic_expr (elt);
4130           return true;
4131         }
4132
4133       if (elt_type)
4134         {
4135           if (TREE_TYPE (CASE_LOW (elt)) != elt_type
4136               || (CASE_HIGH (elt) && TREE_TYPE (CASE_HIGH (elt)) != elt_type))
4137             {
4138               error ("type mismatch for case label in switch statement");
4139               debug_generic_expr (elt);
4140               return true;
4141             }
4142         }
4143       else
4144         {
4145           elt_type = TREE_TYPE (CASE_LOW (elt));
4146           if (TYPE_PRECISION (index_type) < TYPE_PRECISION (elt_type))
4147             {
4148               error ("type precision mismatch in switch statement");
4149               return true;
4150             }
4151         }
4152
4153       if (prev_upper_bound)
4154         {
4155           if (! tree_int_cst_lt (prev_upper_bound, CASE_LOW (elt)))
4156             {
4157               error ("case labels not sorted in switch statement");
4158               return true;
4159             }
4160         }
4161
4162       prev_upper_bound = CASE_HIGH (elt);
4163       if (! prev_upper_bound)
4164         prev_upper_bound = CASE_LOW (elt);
4165     }
4166
4167   return false;
4168 }
4169
4170 /* Verify a gimple debug statement STMT.
4171    Returns true if anything is wrong.  */
4172
4173 static bool
4174 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4175 {
4176   /* There isn't much that could be wrong in a gimple debug stmt.  A
4177      gimple debug bind stmt, for example, maps a tree, that's usually
4178      a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4179      component or member of an aggregate type, to another tree, that
4180      can be an arbitrary expression.  These stmts expand into debug
4181      insns, and are converted to debug notes by var-tracking.c.  */
4182   return false;
4183 }
4184
4185 /* Verify a gimple label statement STMT.
4186    Returns true if anything is wrong.  */
4187
4188 static bool
4189 verify_gimple_label (gimple stmt)
4190 {
4191   tree decl = gimple_label_label (stmt);
4192   int uid;
4193   bool err = false;
4194
4195   if (TREE_CODE (decl) != LABEL_DECL)
4196     return true;
4197
4198   uid = LABEL_DECL_UID (decl);
4199   if (cfun->cfg
4200       && (uid == -1 || (*label_to_block_map)[uid] != gimple_bb (stmt)))
4201     {
4202       error ("incorrect entry in label_to_block_map");
4203       err |= true;
4204     }
4205
4206   uid = EH_LANDING_PAD_NR (decl);
4207   if (uid)
4208     {
4209       eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4210       if (decl != lp->post_landing_pad)
4211         {
4212           error ("incorrect setting of landing pad number");
4213           err |= true;
4214         }
4215     }
4216
4217   return err;
4218 }
4219
4220 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4221    error, otherwise false.  */
4222
4223 static bool
4224 verify_gimple_stmt (gimple stmt)
4225 {
4226   switch (gimple_code (stmt))
4227     {
4228     case GIMPLE_ASSIGN:
4229       return verify_gimple_assign (stmt);
4230
4231     case GIMPLE_LABEL:
4232       return verify_gimple_label (stmt);
4233
4234     case GIMPLE_CALL:
4235       return verify_gimple_call (stmt);
4236
4237     case GIMPLE_COND:
4238       if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4239         {
4240           error ("invalid comparison code in gimple cond");
4241           return true;
4242         }
4243       if (!(!gimple_cond_true_label (stmt)
4244             || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4245           || !(!gimple_cond_false_label (stmt)
4246                || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4247         {
4248           error ("invalid labels in gimple cond");
4249           return true;
4250         }
4251           
4252       return verify_gimple_comparison (boolean_type_node,
4253                                        gimple_cond_lhs (stmt),
4254                                        gimple_cond_rhs (stmt));
4255
4256     case GIMPLE_GOTO:
4257       return verify_gimple_goto (stmt);
4258
4259     case GIMPLE_SWITCH:
4260       return verify_gimple_switch (stmt);
4261
4262     case GIMPLE_RETURN:
4263       return verify_gimple_return (stmt);
4264
4265     case GIMPLE_ASM:
4266       return false;
4267
4268     case GIMPLE_TRANSACTION:
4269       return verify_gimple_transaction (stmt);
4270
4271     /* Tuples that do not have tree operands.  */
4272     case GIMPLE_NOP:
4273     case GIMPLE_PREDICT:
4274     case GIMPLE_RESX:
4275     case GIMPLE_EH_DISPATCH:
4276     case GIMPLE_EH_MUST_NOT_THROW:
4277       return false;
4278
4279     CASE_GIMPLE_OMP:
4280       /* OpenMP directives are validated by the FE and never operated
4281          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4282          non-gimple expressions when the main index variable has had
4283          its address taken.  This does not affect the loop itself
4284          because the header of an GIMPLE_OMP_FOR is merely used to determine
4285          how to setup the parallel iteration.  */
4286       return false;
4287
4288     case GIMPLE_DEBUG:
4289       return verify_gimple_debug (stmt);
4290
4291     default:
4292       gcc_unreachable ();
4293     }
4294 }
4295
4296 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
4297    and false otherwise.  */
4298
4299 static bool
4300 verify_gimple_phi (gimple phi)
4301 {
4302   bool err = false;
4303   unsigned i;
4304   tree phi_result = gimple_phi_result (phi);
4305   bool virtual_p;
4306
4307   if (!phi_result)
4308     {
4309       error ("invalid PHI result");
4310       return true;
4311     }
4312
4313   virtual_p = virtual_operand_p (phi_result);
4314   if (TREE_CODE (phi_result) != SSA_NAME
4315       || (virtual_p
4316           && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4317     {
4318       error ("invalid PHI result");
4319       err = true;
4320     }
4321
4322   for (i = 0; i < gimple_phi_num_args (phi); i++)
4323     {
4324       tree t = gimple_phi_arg_def (phi, i);
4325
4326       if (!t)
4327         {
4328           error ("missing PHI def");
4329           err |= true;
4330           continue;
4331         }
4332       /* Addressable variables do have SSA_NAMEs but they
4333          are not considered gimple values.  */
4334       else if ((TREE_CODE (t) == SSA_NAME
4335                 && virtual_p != virtual_operand_p (t))
4336                || (virtual_p
4337                    && (TREE_CODE (t) != SSA_NAME
4338                        || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4339                || (!virtual_p
4340                    && !is_gimple_val (t)))
4341         {
4342           error ("invalid PHI argument");
4343           debug_generic_expr (t);
4344           err |= true;
4345         }
4346 #ifdef ENABLE_TYPES_CHECKING
4347       if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4348         {
4349           error ("incompatible types in PHI argument %u", i);
4350           debug_generic_stmt (TREE_TYPE (phi_result));
4351           debug_generic_stmt (TREE_TYPE (t));
4352           err |= true;
4353         }
4354 #endif
4355     }
4356
4357   return err;
4358 }
4359
4360 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4361
4362 static bool
4363 verify_gimple_in_seq_2 (gimple_seq stmts)
4364 {
4365   gimple_stmt_iterator ittr;
4366   bool err = false;
4367
4368   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4369     {
4370       gimple stmt = gsi_stmt (ittr);
4371
4372       switch (gimple_code (stmt))
4373         {
4374         case GIMPLE_BIND:
4375           err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4376           break;
4377
4378         case GIMPLE_TRY:
4379           err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4380           err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4381           break;
4382
4383         case GIMPLE_EH_FILTER:
4384           err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4385           break;
4386
4387         case GIMPLE_EH_ELSE:
4388           err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt));
4389           err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt));
4390           break;
4391
4392         case GIMPLE_CATCH:
4393           err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4394           break;
4395
4396         case GIMPLE_TRANSACTION:
4397           err |= verify_gimple_transaction (stmt);
4398           break;
4399
4400         default:
4401           {
4402             bool err2 = verify_gimple_stmt (stmt);
4403             if (err2)
4404               debug_gimple_stmt (stmt);
4405             err |= err2;
4406           }
4407         }
4408     }
4409
4410   return err;
4411 }
4412
4413 /* Verify the contents of a GIMPLE_TRANSACTION.  Returns true if there
4414    is a problem, otherwise false.  */
4415
4416 static bool
4417 verify_gimple_transaction (gimple stmt)
4418 {
4419   tree lab = gimple_transaction_label (stmt);
4420   if (lab != NULL && TREE_CODE (lab) != LABEL_DECL)
4421     return true;
4422   return verify_gimple_in_seq_2 (gimple_transaction_body (stmt));
4423 }
4424
4425
4426 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4427
4428 DEBUG_FUNCTION void
4429 verify_gimple_in_seq (gimple_seq stmts)
4430 {
4431   timevar_push (TV_TREE_STMT_VERIFY);
4432   if (verify_gimple_in_seq_2 (stmts))
4433     internal_error ("verify_gimple failed");
4434   timevar_pop (TV_TREE_STMT_VERIFY);
4435 }
4436
4437 /* Return true when the T can be shared.  */
4438
4439 bool
4440 tree_node_can_be_shared (tree t)
4441 {
4442   if (IS_TYPE_OR_DECL_P (t)
4443       || is_gimple_min_invariant (t)
4444       || TREE_CODE (t) == SSA_NAME
4445       || t == error_mark_node
4446       || TREE_CODE (t) == IDENTIFIER_NODE)
4447     return true;
4448
4449   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4450     return true;
4451
4452   if (DECL_P (t))
4453     return true;
4454
4455   return false;
4456 }
4457
4458 /* Called via walk_tree.  Verify tree sharing.  */
4459
4460 static tree
4461 verify_node_sharing_1 (tree *tp, int *walk_subtrees, void *data)
4462 {
4463   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4464
4465   if (tree_node_can_be_shared (*tp))
4466     {
4467       *walk_subtrees = false;
4468       return NULL;
4469     }
4470
4471   if (pointer_set_insert (visited, *tp))
4472     return *tp;
4473
4474   return NULL;
4475 }
4476
4477 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4478
4479 static tree
4480 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4481 {
4482   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4483   return verify_node_sharing_1 (tp, walk_subtrees, wi->info);
4484 }
4485
4486 static bool eh_error_found;
4487 static int
4488 verify_eh_throw_stmt_node (void **slot, void *data)
4489 {
4490   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4491   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4492
4493   if (!pointer_set_contains (visited, node->stmt))
4494     {
4495       error ("dead STMT in EH table");
4496       debug_gimple_stmt (node->stmt);
4497       eh_error_found = true;
4498     }
4499   return 1;
4500 }
4501
4502 /* Verify if the location LOCs block is in BLOCKS.  */
4503
4504 static bool
4505 verify_location (pointer_set_t *blocks, location_t loc)
4506 {
4507   tree block = LOCATION_BLOCK (loc);
4508   if (block != NULL_TREE
4509       && !pointer_set_contains (blocks, block))
4510     {
4511       error ("location references block not in block tree");
4512       return true;
4513     }
4514   if (block != NULL_TREE)
4515     return verify_location (blocks, BLOCK_SOURCE_LOCATION (block));
4516   return false;
4517 }
4518
4519 /* Called via walk_tree.  Verify locations of expressions.  */
4520
4521 static tree
4522 verify_expr_location_1 (tree *tp, int *walk_subtrees, void *data)
4523 {
4524   struct pointer_set_t *blocks = (struct pointer_set_t *) data;
4525
4526   if (TREE_CODE (*tp) == VAR_DECL
4527       && DECL_DEBUG_EXPR_IS_FROM (*tp))
4528     {
4529       tree t = DECL_DEBUG_EXPR (*tp);
4530       tree addr = walk_tree (&t, verify_expr_location_1, blocks, NULL);
4531       if (addr)
4532         return addr;
4533     }
4534
4535   if (!EXPR_P (*tp))
4536     {
4537       *walk_subtrees = false;
4538       return NULL;
4539     }
4540
4541   location_t loc = EXPR_LOCATION (*tp);
4542   if (verify_location (blocks, loc))
4543     return *tp;
4544
4545   return NULL;
4546 }
4547
4548 /* Called via walk_gimple_op.  Verify locations of expressions.  */
4549
4550 static tree
4551 verify_expr_location (tree *tp, int *walk_subtrees, void *data)
4552 {
4553   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4554   return verify_expr_location_1 (tp, walk_subtrees, wi->info);
4555 }
4556
4557 /* Insert all subblocks of BLOCK into BLOCKS and recurse.  */
4558
4559 static void
4560 collect_subblocks (pointer_set_t *blocks, tree block)
4561 {
4562   tree t;
4563   for (t = BLOCK_SUBBLOCKS (block); t; t = BLOCK_CHAIN (t))
4564     {
4565       pointer_set_insert (blocks, t);
4566       collect_subblocks (blocks, t);
4567     }
4568 }
4569
4570 /* Verify the GIMPLE statements in the CFG of FN.  */
4571
4572 DEBUG_FUNCTION void
4573 verify_gimple_in_cfg (struct function *fn)
4574 {
4575   basic_block bb;
4576   bool err = false;
4577   struct pointer_set_t *visited, *visited_stmts, *blocks;
4578
4579   timevar_push (TV_TREE_STMT_VERIFY);
4580   visited = pointer_set_create ();
4581   visited_stmts = pointer_set_create ();
4582
4583   /* Collect all BLOCKs referenced by the BLOCK tree of FN.  */
4584   blocks = pointer_set_create ();
4585   if (DECL_INITIAL (fn->decl))
4586     {
4587       pointer_set_insert (blocks, DECL_INITIAL (fn->decl));
4588       collect_subblocks (blocks, DECL_INITIAL (fn->decl));
4589     }
4590
4591   FOR_EACH_BB_FN (bb, fn)
4592     {
4593       gimple_stmt_iterator gsi;
4594
4595       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4596         {
4597           gimple phi = gsi_stmt (gsi);
4598           bool err2 = false;
4599           unsigned i;
4600
4601           pointer_set_insert (visited_stmts, phi);
4602
4603           if (gimple_bb (phi) != bb)
4604             {
4605               error ("gimple_bb (phi) is set to a wrong basic block");
4606               err2 = true;
4607             }
4608
4609           err2 |= verify_gimple_phi (phi);
4610
4611           /* Only PHI arguments have locations.  */
4612           if (gimple_location (phi) != UNKNOWN_LOCATION)
4613             {
4614               error ("PHI node with location");
4615               err2 = true;
4616             }
4617
4618           for (i = 0; i < gimple_phi_num_args (phi); i++)
4619             {
4620               tree arg = gimple_phi_arg_def (phi, i);
4621               tree addr = walk_tree (&arg, verify_node_sharing_1,
4622                                      visited, NULL);
4623               if (addr)
4624                 {
4625                   error ("incorrect sharing of tree nodes");
4626                   debug_generic_expr (addr);
4627                   err2 |= true;
4628                 }
4629               location_t loc = gimple_phi_arg_location (phi, i);
4630               if (virtual_operand_p (gimple_phi_result (phi))
4631                   && loc != UNKNOWN_LOCATION)
4632                 {
4633                   error ("virtual PHI with argument locations");
4634                   err2 = true;
4635                 }
4636               addr = walk_tree (&arg, verify_expr_location_1, blocks, NULL);
4637               if (addr)
4638                 {
4639                   debug_generic_expr (addr);
4640                   err2 = true;
4641                 }
4642               err2 |= verify_location (blocks, loc);
4643             }
4644
4645           if (err2)
4646             debug_gimple_stmt (phi);
4647           err |= err2;
4648         }
4649
4650       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4651         {
4652           gimple stmt = gsi_stmt (gsi);
4653           bool err2 = false;
4654           struct walk_stmt_info wi;
4655           tree addr;
4656           int lp_nr;
4657
4658           pointer_set_insert (visited_stmts, stmt);
4659
4660           if (gimple_bb (stmt) != bb)
4661             {
4662               error ("gimple_bb (stmt) is set to a wrong basic block");
4663               err2 = true;
4664             }
4665
4666           err2 |= verify_gimple_stmt (stmt);
4667           err2 |= verify_location (blocks, gimple_location (stmt));
4668
4669           memset (&wi, 0, sizeof (wi));
4670           wi.info = (void *) visited;
4671           addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4672           if (addr)
4673             {
4674               error ("incorrect sharing of tree nodes");
4675               debug_generic_expr (addr);
4676               err2 |= true;
4677             }
4678
4679           memset (&wi, 0, sizeof (wi));
4680           wi.info = (void *) blocks;
4681           addr = walk_gimple_op (stmt, verify_expr_location, &wi);
4682           if (addr)
4683             {
4684               debug_generic_expr (addr);
4685               err2 |= true;
4686             }
4687
4688           /* ???  Instead of not checking these stmts at all the walker
4689              should know its context via wi.  */
4690           if (!is_gimple_debug (stmt)
4691               && !is_gimple_omp (stmt))
4692             {
4693               memset (&wi, 0, sizeof (wi));
4694               addr = walk_gimple_op (stmt, verify_expr, &wi);
4695               if (addr)
4696                 {
4697                   debug_generic_expr (addr);
4698                   inform (gimple_location (stmt), "in statement");
4699                   err2 |= true;
4700                 }
4701             }
4702
4703           /* If the statement is marked as part of an EH region, then it is
4704              expected that the statement could throw.  Verify that when we
4705              have optimizations that simplify statements such that we prove
4706              that they cannot throw, that we update other data structures
4707              to match.  */
4708           lp_nr = lookup_stmt_eh_lp (stmt);
4709           if (lp_nr != 0)
4710             {
4711               if (!stmt_could_throw_p (stmt))
4712                 {
4713                   error ("statement marked for throw, but doesn%'t");
4714                   err2 |= true;
4715                 }
4716               else if (lp_nr > 0
4717                        && !gsi_one_before_end_p (gsi)
4718                        && stmt_can_throw_internal (stmt))
4719                 {
4720                   error ("statement marked for throw in middle of block");
4721                   err2 |= true;
4722                 }
4723             }
4724
4725           if (err2)
4726             debug_gimple_stmt (stmt);
4727           err |= err2;
4728         }
4729     }
4730
4731   eh_error_found = false;
4732   if (get_eh_throw_stmt_table (cfun))
4733     htab_traverse (get_eh_throw_stmt_table (cfun),
4734                    verify_eh_throw_stmt_node,
4735                    visited_stmts);
4736
4737   if (err || eh_error_found)
4738     internal_error ("verify_gimple failed");
4739
4740   pointer_set_destroy (visited);
4741   pointer_set_destroy (visited_stmts);
4742   pointer_set_destroy (blocks);
4743   verify_histograms ();
4744   timevar_pop (TV_TREE_STMT_VERIFY);
4745 }
4746
4747
4748 /* Verifies that the flow information is OK.  */
4749
4750 static int
4751 gimple_verify_flow_info (void)
4752 {
4753   int err = 0;
4754   basic_block bb;
4755   gimple_stmt_iterator gsi;
4756   gimple stmt;
4757   edge e;
4758   edge_iterator ei;
4759
4760   if (ENTRY_BLOCK_PTR->il.gimple.seq || ENTRY_BLOCK_PTR->il.gimple.phi_nodes)
4761     {
4762       error ("ENTRY_BLOCK has IL associated with it");
4763       err = 1;
4764     }
4765
4766   if (EXIT_BLOCK_PTR->il.gimple.seq || EXIT_BLOCK_PTR->il.gimple.phi_nodes)
4767     {
4768       error ("EXIT_BLOCK has IL associated with it");
4769       err = 1;
4770     }
4771
4772   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4773     if (e->flags & EDGE_FALLTHRU)
4774       {
4775         error ("fallthru to exit from bb %d", e->src->index);
4776         err = 1;
4777       }
4778
4779   FOR_EACH_BB (bb)
4780     {
4781       bool found_ctrl_stmt = false;
4782
4783       stmt = NULL;
4784
4785       /* Skip labels on the start of basic block.  */
4786       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4787         {
4788           tree label;
4789           gimple prev_stmt = stmt;
4790
4791           stmt = gsi_stmt (gsi);
4792
4793           if (gimple_code (stmt) != GIMPLE_LABEL)
4794             break;
4795
4796           label = gimple_label_label (stmt);
4797           if (prev_stmt && DECL_NONLOCAL (label))
4798             {
4799               error ("nonlocal label ");
4800               print_generic_expr (stderr, label, 0);
4801               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4802                        bb->index);
4803               err = 1;
4804             }
4805
4806           if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4807             {
4808               error ("EH landing pad label ");
4809               print_generic_expr (stderr, label, 0);
4810               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4811                        bb->index);
4812               err = 1;
4813             }
4814
4815           if (label_to_block (label) != bb)
4816             {
4817               error ("label ");
4818               print_generic_expr (stderr, label, 0);
4819               fprintf (stderr, " to block does not match in bb %d",
4820                        bb->index);
4821               err = 1;
4822             }
4823
4824           if (decl_function_context (label) != current_function_decl)
4825             {
4826               error ("label ");
4827               print_generic_expr (stderr, label, 0);
4828               fprintf (stderr, " has incorrect context in bb %d",
4829                        bb->index);
4830               err = 1;
4831             }
4832         }
4833
4834       /* Verify that body of basic block BB is free of control flow.  */
4835       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4836         {
4837           gimple stmt = gsi_stmt (gsi);
4838
4839           if (found_ctrl_stmt)
4840             {
4841               error ("control flow in the middle of basic block %d",
4842                      bb->index);
4843               err = 1;
4844             }
4845
4846           if (stmt_ends_bb_p (stmt))
4847             found_ctrl_stmt = true;
4848
4849           if (gimple_code (stmt) == GIMPLE_LABEL)
4850             {
4851               error ("label ");
4852               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4853               fprintf (stderr, " in the middle of basic block %d", bb->index);
4854               err = 1;
4855             }
4856         }
4857
4858       gsi = gsi_last_bb (bb);
4859       if (gsi_end_p (gsi))
4860         continue;
4861
4862       stmt = gsi_stmt (gsi);
4863
4864       if (gimple_code (stmt) == GIMPLE_LABEL)
4865         continue;
4866
4867       err |= verify_eh_edges (stmt);
4868
4869       if (is_ctrl_stmt (stmt))
4870         {
4871           FOR_EACH_EDGE (e, ei, bb->succs)
4872             if (e->flags & EDGE_FALLTHRU)
4873               {
4874                 error ("fallthru edge after a control statement in bb %d",
4875                        bb->index);
4876                 err = 1;
4877               }
4878         }
4879
4880       if (gimple_code (stmt) != GIMPLE_COND)
4881         {
4882           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4883              after anything else but if statement.  */
4884           FOR_EACH_EDGE (e, ei, bb->succs)
4885             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4886               {
4887                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4888                        bb->index);
4889                 err = 1;
4890               }
4891         }
4892
4893       switch (gimple_code (stmt))
4894         {
4895         case GIMPLE_COND:
4896           {
4897             edge true_edge;
4898             edge false_edge;
4899
4900             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4901
4902             if (!true_edge
4903                 || !false_edge
4904                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4905                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4906                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4907                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4908                 || EDGE_COUNT (bb->succs) >= 3)
4909               {
4910                 error ("wrong outgoing edge flags at end of bb %d",
4911                        bb->index);
4912                 err = 1;
4913               }
4914           }
4915           break;
4916
4917         case GIMPLE_GOTO:
4918           if (simple_goto_p (stmt))
4919             {
4920               error ("explicit goto at end of bb %d", bb->index);
4921               err = 1;
4922             }
4923           else
4924             {
4925               /* FIXME.  We should double check that the labels in the
4926                  destination blocks have their address taken.  */
4927               FOR_EACH_EDGE (e, ei, bb->succs)
4928                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4929                                  | EDGE_FALSE_VALUE))
4930                     || !(e->flags & EDGE_ABNORMAL))
4931                   {
4932                     error ("wrong outgoing edge flags at end of bb %d",
4933                            bb->index);
4934                     err = 1;
4935                   }
4936             }
4937           break;
4938
4939         case GIMPLE_CALL:
4940           if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
4941             break;
4942           /* ... fallthru ... */
4943         case GIMPLE_RETURN:
4944           if (!single_succ_p (bb)
4945               || (single_succ_edge (bb)->flags
4946                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4947                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4948             {
4949               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4950               err = 1;
4951             }
4952           if (single_succ (bb) != EXIT_BLOCK_PTR)
4953             {
4954               error ("return edge does not point to exit in bb %d",
4955                      bb->index);
4956               err = 1;
4957             }
4958           break;
4959
4960         case GIMPLE_SWITCH:
4961           {
4962             tree prev;
4963             edge e;
4964             size_t i, n;
4965
4966             n = gimple_switch_num_labels (stmt);
4967
4968             /* Mark all the destination basic blocks.  */
4969             for (i = 0; i < n; ++i)
4970               {
4971                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4972                 basic_block label_bb = label_to_block (lab);
4973                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4974                 label_bb->aux = (void *)1;
4975               }
4976
4977             /* Verify that the case labels are sorted.  */
4978             prev = gimple_switch_label (stmt, 0);
4979             for (i = 1; i < n; ++i)
4980               {
4981                 tree c = gimple_switch_label (stmt, i);
4982                 if (!CASE_LOW (c))
4983                   {
4984                     error ("found default case not at the start of "
4985                            "case vector");
4986                     err = 1;
4987                     continue;
4988                   }
4989                 if (CASE_LOW (prev)
4990                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4991                   {
4992                     error ("case labels not sorted: ");
4993                     print_generic_expr (stderr, prev, 0);
4994                     fprintf (stderr," is greater than ");
4995                     print_generic_expr (stderr, c, 0);
4996                     fprintf (stderr," but comes before it.\n");
4997                     err = 1;
4998                   }
4999                 prev = c;
5000               }
5001             /* VRP will remove the default case if it can prove it will
5002                never be executed.  So do not verify there always exists
5003                a default case here.  */
5004
5005             FOR_EACH_EDGE (e, ei, bb->succs)
5006               {
5007                 if (!e->dest->aux)
5008                   {
5009                     error ("extra outgoing edge %d->%d",
5010                            bb->index, e->dest->index);
5011                     err = 1;
5012                   }
5013
5014                 e->dest->aux = (void *)2;
5015                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
5016                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5017                   {
5018                     error ("wrong outgoing edge flags at end of bb %d",
5019                            bb->index);
5020                     err = 1;
5021                   }
5022               }
5023
5024             /* Check that we have all of them.  */
5025             for (i = 0; i < n; ++i)
5026               {
5027                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5028                 basic_block label_bb = label_to_block (lab);
5029
5030                 if (label_bb->aux != (void *)2)
5031                   {
5032                     error ("missing edge %i->%i", bb->index, label_bb->index);
5033                     err = 1;
5034                   }
5035               }
5036
5037             FOR_EACH_EDGE (e, ei, bb->succs)
5038               e->dest->aux = (void *)0;
5039           }
5040           break;
5041
5042         case GIMPLE_EH_DISPATCH:
5043           err |= verify_eh_dispatch_edge (stmt);
5044           break;
5045
5046         default:
5047           break;
5048         }
5049     }
5050
5051   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
5052     verify_dominators (CDI_DOMINATORS);
5053
5054   return err;
5055 }
5056
5057
5058 /* Updates phi nodes after creating a forwarder block joined
5059    by edge FALLTHRU.  */
5060
5061 static void
5062 gimple_make_forwarder_block (edge fallthru)
5063 {
5064   edge e;
5065   edge_iterator ei;
5066   basic_block dummy, bb;
5067   tree var;
5068   gimple_stmt_iterator gsi;
5069
5070   dummy = fallthru->src;
5071   bb = fallthru->dest;
5072
5073   if (single_pred_p (bb))
5074     return;
5075
5076   /* If we redirected a branch we must create new PHI nodes at the
5077      start of BB.  */
5078   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5079     {
5080       gimple phi, new_phi;
5081
5082       phi = gsi_stmt (gsi);
5083       var = gimple_phi_result (phi);
5084       new_phi = create_phi_node (var, bb);
5085       gimple_phi_set_result (phi, copy_ssa_name (var, phi));
5086       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5087                    UNKNOWN_LOCATION);
5088     }
5089
5090   /* Add the arguments we have stored on edges.  */
5091   FOR_EACH_EDGE (e, ei, bb->preds)
5092     {
5093       if (e == fallthru)
5094         continue;
5095
5096       flush_pending_stmts (e);
5097     }
5098 }
5099
5100
5101 /* Return a non-special label in the head of basic block BLOCK.
5102    Create one if it doesn't exist.  */
5103
5104 tree
5105 gimple_block_label (basic_block bb)
5106 {
5107   gimple_stmt_iterator i, s = gsi_start_bb (bb);
5108   bool first = true;
5109   tree label;
5110   gimple stmt;
5111
5112   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5113     {
5114       stmt = gsi_stmt (i);
5115       if (gimple_code (stmt) != GIMPLE_LABEL)
5116         break;
5117       label = gimple_label_label (stmt);
5118       if (!DECL_NONLOCAL (label))
5119         {
5120           if (!first)
5121             gsi_move_before (&i, &s);
5122           return label;
5123         }
5124     }
5125
5126   label = create_artificial_label (UNKNOWN_LOCATION);
5127   stmt = gimple_build_label (label);
5128   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5129   return label;
5130 }
5131
5132
5133 /* Attempt to perform edge redirection by replacing a possibly complex
5134    jump instruction by a goto or by removing the jump completely.
5135    This can apply only if all edges now point to the same block.  The
5136    parameters and return values are equivalent to
5137    redirect_edge_and_branch.  */
5138
5139 static edge
5140 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5141 {
5142   basic_block src = e->src;
5143   gimple_stmt_iterator i;
5144   gimple stmt;
5145
5146   /* We can replace or remove a complex jump only when we have exactly
5147      two edges.  */
5148   if (EDGE_COUNT (src->succs) != 2
5149       /* Verify that all targets will be TARGET.  Specifically, the
5150          edge that is not E must also go to TARGET.  */
5151       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5152     return NULL;
5153
5154   i = gsi_last_bb (src);
5155   if (gsi_end_p (i))
5156     return NULL;
5157
5158   stmt = gsi_stmt (i);
5159
5160   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5161     {
5162       gsi_remove (&i, true);
5163       e = ssa_redirect_edge (e, target);
5164       e->flags = EDGE_FALLTHRU;
5165       return e;
5166     }
5167
5168   return NULL;
5169 }
5170
5171
5172 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
5173    edge representing the redirected branch.  */
5174
5175 static edge
5176 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5177 {
5178   basic_block bb = e->src;
5179   gimple_stmt_iterator gsi;
5180   edge ret;
5181   gimple stmt;
5182
5183   if (e->flags & EDGE_ABNORMAL)
5184     return NULL;
5185
5186   if (e->dest == dest)
5187     return NULL;
5188
5189   if (e->flags & EDGE_EH)
5190     return redirect_eh_edge (e, dest);
5191
5192   if (e->src != ENTRY_BLOCK_PTR)
5193     {
5194       ret = gimple_try_redirect_by_replacing_jump (e, dest);
5195       if (ret)
5196         return ret;
5197     }
5198
5199   gsi = gsi_last_bb (bb);
5200   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5201
5202   switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5203     {
5204     case GIMPLE_COND:
5205       /* For COND_EXPR, we only need to redirect the edge.  */
5206       break;
5207
5208     case GIMPLE_GOTO:
5209       /* No non-abnormal edges should lead from a non-simple goto, and
5210          simple ones should be represented implicitly.  */
5211       gcc_unreachable ();
5212
5213     case GIMPLE_SWITCH:
5214       {
5215         tree label = gimple_block_label (dest);
5216         tree cases = get_cases_for_edge (e, stmt);
5217
5218         /* If we have a list of cases associated with E, then use it
5219            as it's a lot faster than walking the entire case vector.  */
5220         if (cases)
5221           {
5222             edge e2 = find_edge (e->src, dest);
5223             tree last, first;
5224
5225             first = cases;
5226             while (cases)
5227               {
5228                 last = cases;
5229                 CASE_LABEL (cases) = label;
5230                 cases = CASE_CHAIN (cases);
5231               }
5232
5233             /* If there was already an edge in the CFG, then we need
5234                to move all the cases associated with E to E2.  */
5235             if (e2)
5236               {
5237                 tree cases2 = get_cases_for_edge (e2, stmt);
5238
5239                 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5240                 CASE_CHAIN (cases2) = first;
5241               }
5242             bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5243           }
5244         else
5245           {
5246             size_t i, n = gimple_switch_num_labels (stmt);
5247
5248             for (i = 0; i < n; i++)
5249               {
5250                 tree elt = gimple_switch_label (stmt, i);
5251                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5252                   CASE_LABEL (elt) = label;
5253               }
5254           }
5255       }
5256       break;
5257
5258     case GIMPLE_ASM:
5259       {
5260         int i, n = gimple_asm_nlabels (stmt);
5261         tree label = NULL;
5262
5263         for (i = 0; i < n; ++i)
5264           {
5265             tree cons = gimple_asm_label_op (stmt, i);
5266             if (label_to_block (TREE_VALUE (cons)) == e->dest)
5267               {
5268                 if (!label)
5269                   label = gimple_block_label (dest);
5270                 TREE_VALUE (cons) = label;
5271               }
5272           }
5273
5274         /* If we didn't find any label matching the former edge in the
5275            asm labels, we must be redirecting the fallthrough
5276            edge.  */
5277         gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5278       }
5279       break;
5280
5281     case GIMPLE_RETURN:
5282       gsi_remove (&gsi, true);
5283       e->flags |= EDGE_FALLTHRU;
5284       break;
5285
5286     case GIMPLE_OMP_RETURN:
5287     case GIMPLE_OMP_CONTINUE:
5288     case GIMPLE_OMP_SECTIONS_SWITCH:
5289     case GIMPLE_OMP_FOR:
5290       /* The edges from OMP constructs can be simply redirected.  */
5291       break;
5292
5293     case GIMPLE_EH_DISPATCH:
5294       if (!(e->flags & EDGE_FALLTHRU))
5295         redirect_eh_dispatch_edge (stmt, e, dest);
5296       break;
5297
5298     case GIMPLE_TRANSACTION:
5299       /* The ABORT edge has a stored label associated with it, otherwise
5300          the edges are simply redirectable.  */
5301       if (e->flags == 0)
5302         gimple_transaction_set_label (stmt, gimple_block_label (dest));
5303       break;
5304
5305     default:
5306       /* Otherwise it must be a fallthru edge, and we don't need to
5307          do anything besides redirecting it.  */
5308       gcc_assert (e->flags & EDGE_FALLTHRU);
5309       break;
5310     }
5311
5312   /* Update/insert PHI nodes as necessary.  */
5313
5314   /* Now update the edges in the CFG.  */
5315   e = ssa_redirect_edge (e, dest);
5316
5317   return e;
5318 }
5319
5320 /* Returns true if it is possible to remove edge E by redirecting
5321    it to the destination of the other edge from E->src.  */
5322
5323 static bool
5324 gimple_can_remove_branch_p (const_edge e)
5325 {
5326   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5327     return false;
5328
5329   return true;
5330 }
5331
5332 /* Simple wrapper, as we can always redirect fallthru edges.  */
5333
5334 static basic_block
5335 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5336 {
5337   e = gimple_redirect_edge_and_branch (e, dest);
5338   gcc_assert (e);
5339
5340   return NULL;
5341 }
5342
5343
5344 /* Splits basic block BB after statement STMT (but at least after the
5345    labels).  If STMT is NULL, BB is split just after the labels.  */
5346
5347 static basic_block
5348 gimple_split_block (basic_block bb, void *stmt)
5349 {
5350   gimple_stmt_iterator gsi;
5351   gimple_stmt_iterator gsi_tgt;
5352   gimple act;
5353   gimple_seq list;
5354   basic_block new_bb;
5355   edge e;
5356   edge_iterator ei;
5357
5358   new_bb = create_empty_bb (bb);
5359
5360   /* Redirect the outgoing edges.  */
5361   new_bb->succs = bb->succs;
5362   bb->succs = NULL;
5363   FOR_EACH_EDGE (e, ei, new_bb->succs)
5364     e->src = new_bb;
5365
5366   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5367     stmt = NULL;
5368
5369   /* Move everything from GSI to the new basic block.  */
5370   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5371     {
5372       act = gsi_stmt (gsi);
5373       if (gimple_code (act) == GIMPLE_LABEL)
5374         continue;
5375
5376       if (!stmt)
5377         break;
5378
5379       if (stmt == act)
5380         {
5381           gsi_next (&gsi);
5382           break;
5383         }
5384     }
5385
5386   if (gsi_end_p (gsi))
5387     return new_bb;
5388
5389   /* Split the statement list - avoid re-creating new containers as this
5390      brings ugly quadratic memory consumption in the inliner.
5391      (We are still quadratic since we need to update stmt BB pointers,
5392      sadly.)  */
5393   gsi_split_seq_before (&gsi, &list);
5394   set_bb_seq (new_bb, list);
5395   for (gsi_tgt = gsi_start (list);
5396        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5397     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5398
5399   return new_bb;
5400 }
5401
5402
5403 /* Moves basic block BB after block AFTER.  */
5404
5405 static bool
5406 gimple_move_block_after (basic_block bb, basic_block after)
5407 {
5408   if (bb->prev_bb == after)
5409     return true;
5410
5411   unlink_block (bb);
5412   link_block (bb, after);
5413
5414   return true;
5415 }
5416
5417
5418 /* Return TRUE if block BB has no executable statements, otherwise return
5419    FALSE.  */
5420
5421 bool
5422 gimple_empty_block_p (basic_block bb)
5423 {
5424   /* BB must have no executable statements.  */
5425   gimple_stmt_iterator gsi = gsi_after_labels (bb);
5426   if (phi_nodes (bb))
5427     return false;
5428   if (gsi_end_p (gsi))
5429     return true;
5430   if (is_gimple_debug (gsi_stmt (gsi)))
5431     gsi_next_nondebug (&gsi);
5432   return gsi_end_p (gsi);
5433 }
5434
5435
5436 /* Split a basic block if it ends with a conditional branch and if the
5437    other part of the block is not empty.  */
5438
5439 static basic_block
5440 gimple_split_block_before_cond_jump (basic_block bb)
5441 {
5442   gimple last, split_point;
5443   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
5444   if (gsi_end_p (gsi))
5445     return NULL;
5446   last = gsi_stmt (gsi);
5447   if (gimple_code (last) != GIMPLE_COND
5448       && gimple_code (last) != GIMPLE_SWITCH)
5449     return NULL;
5450   gsi_prev_nondebug (&gsi);
5451   split_point = gsi_stmt (gsi);
5452   return split_block (bb, split_point)->dest;
5453 }
5454
5455
5456 /* Return true if basic_block can be duplicated.  */
5457
5458 static bool
5459 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5460 {
5461   return true;
5462 }
5463
5464 /* Create a duplicate of the basic block BB.  NOTE: This does not
5465    preserve SSA form.  */
5466
5467 static basic_block
5468 gimple_duplicate_bb (basic_block bb)
5469 {
5470   basic_block new_bb;
5471   gimple_stmt_iterator gsi, gsi_tgt;
5472   gimple_seq phis = phi_nodes (bb);
5473   gimple phi, stmt, copy;
5474
5475   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5476
5477   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5478      the incoming edges have not been setup yet.  */
5479   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5480     {
5481       phi = gsi_stmt (gsi);
5482       copy = create_phi_node (NULL_TREE, new_bb);
5483       create_new_def_for (gimple_phi_result (phi), copy,
5484                           gimple_phi_result_ptr (copy));
5485     }
5486
5487   gsi_tgt = gsi_start_bb (new_bb);
5488   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5489     {
5490       def_operand_p def_p;
5491       ssa_op_iter op_iter;
5492       tree lhs;
5493
5494       stmt = gsi_stmt (gsi);
5495       if (gimple_code (stmt) == GIMPLE_LABEL)
5496         continue;
5497
5498       /* Don't duplicate label debug stmts.  */
5499       if (gimple_debug_bind_p (stmt)
5500           && TREE_CODE (gimple_debug_bind_get_var (stmt))
5501              == LABEL_DECL)
5502         continue;
5503
5504       /* Create a new copy of STMT and duplicate STMT's virtual
5505          operands.  */
5506       copy = gimple_copy (stmt);
5507       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5508
5509       maybe_duplicate_eh_stmt (copy, stmt);
5510       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5511
5512       /* When copying around a stmt writing into a local non-user
5513          aggregate, make sure it won't share stack slot with other
5514          vars.  */
5515       lhs = gimple_get_lhs (stmt);
5516       if (lhs && TREE_CODE (lhs) != SSA_NAME)
5517         {
5518           tree base = get_base_address (lhs);
5519           if (base
5520               && (TREE_CODE (base) == VAR_DECL
5521                   || TREE_CODE (base) == RESULT_DECL)
5522               && DECL_IGNORED_P (base)
5523               && !TREE_STATIC (base)
5524               && !DECL_EXTERNAL (base)
5525               && (TREE_CODE (base) != VAR_DECL
5526                   || !DECL_HAS_VALUE_EXPR_P (base)))
5527             DECL_NONSHAREABLE (base) = 1;
5528         }
5529
5530       /* Create new names for all the definitions created by COPY and
5531          add replacement mappings for each new name.  */
5532       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5533         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5534     }
5535
5536   return new_bb;
5537 }
5538
5539 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5540
5541 static void
5542 add_phi_args_after_copy_edge (edge e_copy)
5543 {
5544   basic_block bb, bb_copy = e_copy->src, dest;
5545   edge e;
5546   edge_iterator ei;
5547   gimple phi, phi_copy;
5548   tree def;
5549   gimple_stmt_iterator psi, psi_copy;
5550
5551   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5552     return;
5553
5554   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5555
5556   if (e_copy->dest->flags & BB_DUPLICATED)
5557     dest = get_bb_original (e_copy->dest);
5558   else
5559     dest = e_copy->dest;
5560
5561   e = find_edge (bb, dest);
5562   if (!e)
5563     {
5564       /* During loop unrolling the target of the latch edge is copied.
5565          In this case we are not looking for edge to dest, but to
5566          duplicated block whose original was dest.  */
5567       FOR_EACH_EDGE (e, ei, bb->succs)
5568         {
5569           if ((e->dest->flags & BB_DUPLICATED)
5570               && get_bb_original (e->dest) == dest)
5571             break;
5572         }
5573
5574       gcc_assert (e != NULL);
5575     }
5576
5577   for (psi = gsi_start_phis (e->dest),
5578        psi_copy = gsi_start_phis (e_copy->dest);
5579        !gsi_end_p (psi);
5580        gsi_next (&psi), gsi_next (&psi_copy))
5581     {
5582       phi = gsi_stmt (psi);
5583       phi_copy = gsi_stmt (psi_copy);
5584       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5585       add_phi_arg (phi_copy, def, e_copy,
5586                    gimple_phi_arg_location_from_edge (phi, e));
5587     }
5588 }
5589
5590
5591 /* Basic block BB_COPY was created by code duplication.  Add phi node
5592    arguments for edges going out of BB_COPY.  The blocks that were
5593    duplicated have BB_DUPLICATED set.  */
5594
5595 void
5596 add_phi_args_after_copy_bb (basic_block bb_copy)
5597 {
5598   edge e_copy;
5599   edge_iterator ei;
5600
5601   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5602     {
5603       add_phi_args_after_copy_edge (e_copy);
5604     }
5605 }
5606
5607 /* Blocks in REGION_COPY array of length N_REGION were created by
5608    duplication of basic blocks.  Add phi node arguments for edges
5609    going from these blocks.  If E_COPY is not NULL, also add
5610    phi node arguments for its destination.*/
5611
5612 void
5613 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5614                          edge e_copy)
5615 {
5616   unsigned i;
5617
5618   for (i = 0; i < n_region; i++)
5619     region_copy[i]->flags |= BB_DUPLICATED;
5620
5621   for (i = 0; i < n_region; i++)
5622     add_phi_args_after_copy_bb (region_copy[i]);
5623   if (e_copy)
5624     add_phi_args_after_copy_edge (e_copy);
5625
5626   for (i = 0; i < n_region; i++)
5627     region_copy[i]->flags &= ~BB_DUPLICATED;
5628 }
5629
5630 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5631    important exit edge EXIT.  By important we mean that no SSA name defined
5632    inside region is live over the other exit edges of the region.  All entry
5633    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5634    to the duplicate of the region.  Dominance and loop information is
5635    updated, but not the SSA web.  The new basic blocks are stored to
5636    REGION_COPY in the same order as they had in REGION, provided that
5637    REGION_COPY is not NULL.
5638    The function returns false if it is unable to copy the region,
5639    true otherwise.  */
5640
5641 bool
5642 gimple_duplicate_sese_region (edge entry, edge exit,
5643                             basic_block *region, unsigned n_region,
5644                             basic_block *region_copy)
5645 {
5646   unsigned i;
5647   bool free_region_copy = false, copying_header = false;
5648   struct loop *loop = entry->dest->loop_father;
5649   edge exit_copy;
5650   vec<basic_block> doms;
5651   edge redirected;
5652   int total_freq = 0, entry_freq = 0;
5653   gcov_type total_count = 0, entry_count = 0;
5654
5655   if (!can_copy_bbs_p (region, n_region))
5656     return false;
5657
5658   /* Some sanity checking.  Note that we do not check for all possible
5659      missuses of the functions.  I.e. if you ask to copy something weird,
5660      it will work, but the state of structures probably will not be
5661      correct.  */
5662   for (i = 0; i < n_region; i++)
5663     {
5664       /* We do not handle subloops, i.e. all the blocks must belong to the
5665          same loop.  */
5666       if (region[i]->loop_father != loop)
5667         return false;
5668
5669       if (region[i] != entry->dest
5670           && region[i] == loop->header)
5671         return false;
5672     }
5673
5674   set_loop_copy (loop, loop);
5675
5676   /* In case the function is used for loop header copying (which is the primary
5677      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5678   if (loop->header == entry->dest)
5679     {
5680       copying_header = true;
5681       set_loop_copy (loop, loop_outer (loop));
5682
5683       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5684         return false;
5685
5686       for (i = 0; i < n_region; i++)
5687         if (region[i] != exit->src
5688             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5689           return false;
5690     }
5691
5692   if (!region_copy)
5693     {
5694       region_copy = XNEWVEC (basic_block, n_region);
5695       free_region_copy = true;
5696     }
5697
5698   /* Record blocks outside the region that are dominated by something
5699      inside.  */
5700   doms.create (0);
5701   initialize_original_copy_tables ();
5702
5703   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5704
5705   if (entry->dest->count)
5706     {
5707       total_count = entry->dest->count;
5708       entry_count = entry->count;
5709       /* Fix up corner cases, to avoid division by zero or creation of negative
5710          frequencies.  */
5711       if (entry_count > total_count)
5712         entry_count = total_count;
5713     }
5714   else
5715     {
5716       total_freq = entry->dest->frequency;
5717       entry_freq = EDGE_FREQUENCY (entry);
5718       /* Fix up corner cases, to avoid division by zero or creation of negative
5719          frequencies.  */
5720       if (total_freq == 0)
5721         total_freq = 1;
5722       else if (entry_freq > total_freq)
5723         entry_freq = total_freq;
5724     }
5725
5726   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5727             split_edge_bb_loc (entry));
5728   if (total_count)
5729     {
5730       scale_bbs_frequencies_gcov_type (region, n_region,
5731                                        total_count - entry_count,
5732                                        total_count);
5733       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5734                                        total_count);
5735     }
5736   else
5737     {
5738       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5739                                  total_freq);
5740       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5741     }
5742
5743   if (copying_header)
5744     {
5745       loop->header = exit->dest;
5746       loop->latch = exit->src;
5747     }
5748
5749   /* Redirect the entry and add the phi node arguments.  */
5750   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5751   gcc_assert (redirected != NULL);
5752   flush_pending_stmts (entry);
5753
5754   /* Concerning updating of dominators:  We must recount dominators
5755      for entry block and its copy.  Anything that is outside of the
5756      region, but was dominated by something inside needs recounting as
5757      well.  */
5758   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5759   doms.safe_push (get_bb_original (entry->dest));
5760   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5761   doms.release ();
5762
5763   /* Add the other PHI node arguments.  */
5764   add_phi_args_after_copy (region_copy, n_region, NULL);
5765
5766   if (free_region_copy)
5767     free (region_copy);
5768
5769   free_original_copy_tables ();
5770   return true;
5771 }
5772
5773 /* Checks if BB is part of the region defined by N_REGION BBS.  */
5774 static bool 
5775 bb_part_of_region_p (basic_block bb, basic_block* bbs, unsigned n_region)
5776 {
5777   unsigned int n;
5778
5779   for (n = 0; n < n_region; n++)
5780     {
5781      if (bb == bbs[n])
5782        return true;
5783     }
5784   return false;
5785 }
5786
5787 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5788    are stored to REGION_COPY in the same order in that they appear
5789    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5790    the region, EXIT an exit from it.  The condition guarding EXIT
5791    is moved to ENTRY.  Returns true if duplication succeeds, false
5792    otherwise.
5793
5794    For example,
5795
5796    some_code;
5797    if (cond)
5798      A;
5799    else
5800      B;
5801
5802    is transformed to
5803
5804    if (cond)
5805      {
5806        some_code;
5807        A;
5808      }
5809    else
5810      {
5811        some_code;
5812        B;
5813      }
5814 */
5815
5816 bool
5817 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5818                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5819                           basic_block *region_copy ATTRIBUTE_UNUSED)
5820 {
5821   unsigned i;
5822   bool free_region_copy = false;
5823   struct loop *loop = exit->dest->loop_father;
5824   struct loop *orig_loop = entry->dest->loop_father;
5825   basic_block switch_bb, entry_bb, nentry_bb;
5826   vec<basic_block> doms;
5827   int total_freq = 0, exit_freq = 0;
5828   gcov_type total_count = 0, exit_count = 0;
5829   edge exits[2], nexits[2], e;
5830   gimple_stmt_iterator gsi;
5831   gimple cond_stmt;
5832   edge sorig, snew;
5833   basic_block exit_bb;
5834   gimple_stmt_iterator psi;
5835   gimple phi;
5836   tree def;
5837   struct loop *target, *aloop, *cloop;
5838
5839   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5840   exits[0] = exit;
5841   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5842
5843   if (!can_copy_bbs_p (region, n_region))
5844     return false;
5845
5846   initialize_original_copy_tables ();
5847   set_loop_copy (orig_loop, loop);
5848
5849   target= loop;
5850   for (aloop = orig_loop->inner; aloop; aloop = aloop->next)
5851     {
5852       if (bb_part_of_region_p (aloop->header, region, n_region))
5853         {
5854           cloop = duplicate_loop (aloop, target);
5855           duplicate_subloops (aloop, cloop);
5856         }
5857     }
5858
5859   if (!region_copy)
5860     {
5861       region_copy = XNEWVEC (basic_block, n_region);
5862       free_region_copy = true;
5863     }
5864
5865   gcc_assert (!need_ssa_update_p (cfun));
5866
5867   /* Record blocks outside the region that are dominated by something
5868      inside.  */
5869   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5870
5871   if (exit->src->count)
5872     {
5873       total_count = exit->src->count;
5874       exit_count = exit->count;
5875       /* Fix up corner cases, to avoid division by zero or creation of negative
5876          frequencies.  */
5877       if (exit_count > total_count)
5878         exit_count = total_count;
5879     }
5880   else
5881     {
5882       total_freq = exit->src->frequency;
5883       exit_freq = EDGE_FREQUENCY (exit);
5884       /* Fix up corner cases, to avoid division by zero or creation of negative
5885          frequencies.  */
5886       if (total_freq == 0)
5887         total_freq = 1;
5888       if (exit_freq > total_freq)
5889         exit_freq = total_freq;
5890     }
5891
5892   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5893             split_edge_bb_loc (exit));
5894   if (total_count)
5895     {
5896       scale_bbs_frequencies_gcov_type (region, n_region,
5897                                        total_count - exit_count,
5898                                        total_count);
5899       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5900                                        total_count);
5901     }
5902   else
5903     {
5904       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5905                                  total_freq);
5906       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5907     }
5908
5909   /* Create the switch block, and put the exit condition to it.  */
5910   entry_bb = entry->dest;
5911   nentry_bb = get_bb_copy (entry_bb);
5912   if (!last_stmt (entry->src)
5913       || !stmt_ends_bb_p (last_stmt (entry->src)))
5914     switch_bb = entry->src;
5915   else
5916     switch_bb = split_edge (entry);
5917   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5918
5919   gsi = gsi_last_bb (switch_bb);
5920   cond_stmt = last_stmt (exit->src);
5921   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5922   cond_stmt = gimple_copy (cond_stmt);
5923
5924   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5925
5926   sorig = single_succ_edge (switch_bb);
5927   sorig->flags = exits[1]->flags;
5928   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5929
5930   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5931   rescan_loop_exit (snew, true, false);
5932
5933   /* Add the PHI node arguments.  */
5934   add_phi_args_after_copy (region_copy, n_region, snew);
5935
5936   /* Get rid of now superfluous conditions and associated edges (and phi node
5937      arguments).  */
5938   exit_bb = exit->dest;
5939
5940   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5941   PENDING_STMT (e) = NULL;
5942
5943   /* The latch of ORIG_LOOP was copied, and so was the backedge 
5944      to the original header.  We redirect this backedge to EXIT_BB.  */
5945   for (i = 0; i < n_region; i++)
5946     if (get_bb_original (region_copy[i]) == orig_loop->latch)
5947       {
5948         gcc_assert (single_succ_edge (region_copy[i]));
5949         e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
5950         PENDING_STMT (e) = NULL;
5951         for (psi = gsi_start_phis (exit_bb);
5952              !gsi_end_p (psi);
5953              gsi_next (&psi))
5954           {
5955             phi = gsi_stmt (psi);
5956             def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
5957             add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
5958           }
5959       }
5960   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5961   PENDING_STMT (e) = NULL;
5962   
5963   /* Anything that is outside of the region, but was dominated by something
5964      inside needs to update dominance info.  */
5965   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5966   doms.release ();
5967   /* Update the SSA web.  */
5968   update_ssa (TODO_update_ssa);
5969
5970   if (free_region_copy)
5971     free (region_copy);
5972
5973   free_original_copy_tables ();
5974   return true;
5975 }
5976
5977 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5978    adding blocks when the dominator traversal reaches EXIT.  This
5979    function silently assumes that ENTRY strictly dominates EXIT.  */
5980
5981 void
5982 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5983                               vec<basic_block> *bbs_p)
5984 {
5985   basic_block son;
5986
5987   for (son = first_dom_son (CDI_DOMINATORS, entry);
5988        son;
5989        son = next_dom_son (CDI_DOMINATORS, son))
5990     {
5991       bbs_p->safe_push (son);
5992       if (son != exit)
5993         gather_blocks_in_sese_region (son, exit, bbs_p);
5994     }
5995 }
5996
5997 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5998    The duplicates are recorded in VARS_MAP.  */
5999
6000 static void
6001 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
6002                            tree to_context)
6003 {
6004   tree t = *tp, new_t;
6005   struct function *f = DECL_STRUCT_FUNCTION (to_context);
6006   void **loc;
6007
6008   if (DECL_CONTEXT (t) == to_context)
6009     return;
6010
6011   loc = pointer_map_contains (vars_map, t);
6012
6013   if (!loc)
6014     {
6015       loc = pointer_map_insert (vars_map, t);
6016
6017       if (SSA_VAR_P (t))
6018         {
6019           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
6020           add_local_decl (f, new_t);
6021         }
6022       else
6023         {
6024           gcc_assert (TREE_CODE (t) == CONST_DECL);
6025           new_t = copy_node (t);
6026         }
6027       DECL_CONTEXT (new_t) = to_context;
6028
6029       *loc = new_t;
6030     }
6031   else
6032     new_t = (tree) *loc;
6033
6034   *tp = new_t;
6035 }
6036
6037
6038 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
6039    VARS_MAP maps old ssa names and var_decls to the new ones.  */
6040
6041 static tree
6042 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
6043                   tree to_context)
6044 {
6045   void **loc;
6046   tree new_name;
6047
6048   gcc_assert (!virtual_operand_p (name));
6049
6050   loc = pointer_map_contains (vars_map, name);
6051
6052   if (!loc)
6053     {
6054       tree decl = SSA_NAME_VAR (name);
6055       if (decl)
6056         {
6057           replace_by_duplicate_decl (&decl, vars_map, to_context);
6058           new_name = make_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6059                                        decl, SSA_NAME_DEF_STMT (name));
6060           if (SSA_NAME_IS_DEFAULT_DEF (name))
6061             set_ssa_default_def (DECL_STRUCT_FUNCTION (to_context),
6062                                  decl, new_name);
6063         }
6064       else
6065         new_name = copy_ssa_name_fn (DECL_STRUCT_FUNCTION (to_context),
6066                                      name, SSA_NAME_DEF_STMT (name));
6067
6068       loc = pointer_map_insert (vars_map, name);
6069       *loc = new_name;
6070     }
6071   else
6072     new_name = (tree) *loc;
6073
6074   return new_name;
6075 }
6076
6077 struct move_stmt_d
6078 {
6079   tree orig_block;
6080   tree new_block;
6081   tree from_context;
6082   tree to_context;
6083   struct pointer_map_t *vars_map;
6084   htab_t new_label_map;
6085   struct pointer_map_t *eh_map;
6086   bool remap_decls_p;
6087 };
6088
6089 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
6090    contained in *TP if it has been ORIG_BLOCK previously and change the
6091    DECL_CONTEXT of every local variable referenced in *TP.  */
6092
6093 static tree
6094 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
6095 {
6096   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
6097   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6098   tree t = *tp;
6099
6100   if (EXPR_P (t))
6101     {
6102       tree block = TREE_BLOCK (t);
6103       if (block == p->orig_block
6104           || (p->orig_block == NULL_TREE
6105               && block != NULL_TREE))
6106         TREE_SET_BLOCK (t, p->new_block);
6107 #ifdef ENABLE_CHECKING
6108       else if (block != NULL_TREE)
6109         {
6110           while (block && TREE_CODE (block) == BLOCK && block != p->orig_block)
6111             block = BLOCK_SUPERCONTEXT (block);
6112           gcc_assert (block == p->orig_block);
6113         }
6114 #endif
6115     }
6116   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
6117     {
6118       if (TREE_CODE (t) == SSA_NAME)
6119         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
6120       else if (TREE_CODE (t) == LABEL_DECL)
6121         {
6122           if (p->new_label_map)
6123             {
6124               struct tree_map in, *out;
6125               in.base.from = t;
6126               out = (struct tree_map *)
6127                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
6128               if (out)
6129                 *tp = t = out->to;
6130             }
6131
6132           DECL_CONTEXT (t) = p->to_context;
6133         }
6134       else if (p->remap_decls_p)
6135         {
6136           /* Replace T with its duplicate.  T should no longer appear in the
6137              parent function, so this looks wasteful; however, it may appear
6138              in referenced_vars, and more importantly, as virtual operands of
6139              statements, and in alias lists of other variables.  It would be
6140              quite difficult to expunge it from all those places.  ??? It might
6141              suffice to do this for addressable variables.  */
6142           if ((TREE_CODE (t) == VAR_DECL
6143                && !is_global_var (t))
6144               || TREE_CODE (t) == CONST_DECL)
6145             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6146         }
6147       *walk_subtrees = 0;
6148     }
6149   else if (TYPE_P (t))
6150     *walk_subtrees = 0;
6151
6152   return NULL_TREE;
6153 }
6154
6155 /* Helper for move_stmt_r.  Given an EH region number for the source
6156    function, map that to the duplicate EH regio number in the dest.  */
6157
6158 static int
6159 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6160 {
6161   eh_region old_r, new_r;
6162   void **slot;
6163
6164   old_r = get_eh_region_from_number (old_nr);
6165   slot = pointer_map_contains (p->eh_map, old_r);
6166   new_r = (eh_region) *slot;
6167
6168   return new_r->index;
6169 }
6170
6171 /* Similar, but operate on INTEGER_CSTs.  */
6172
6173 static tree
6174 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6175 {
6176   int old_nr, new_nr;
6177
6178   old_nr = tree_low_cst (old_t_nr, 0);
6179   new_nr = move_stmt_eh_region_nr (old_nr, p);
6180
6181   return build_int_cst (integer_type_node, new_nr);
6182 }
6183
6184 /* Like move_stmt_op, but for gimple statements.
6185
6186    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
6187    contained in the current statement in *GSI_P and change the
6188    DECL_CONTEXT of every local variable referenced in the current
6189    statement.  */
6190
6191 static tree
6192 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6193              struct walk_stmt_info *wi)
6194 {
6195   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6196   gimple stmt = gsi_stmt (*gsi_p);
6197   tree block = gimple_block (stmt);
6198
6199   if (block == p->orig_block
6200       || (p->orig_block == NULL_TREE
6201           && block != NULL_TREE))
6202     gimple_set_block (stmt, p->new_block);
6203
6204   switch (gimple_code (stmt))
6205     {
6206     case GIMPLE_CALL:
6207       /* Remap the region numbers for __builtin_eh_{pointer,filter}.  */
6208       {
6209         tree r, fndecl = gimple_call_fndecl (stmt);
6210         if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6211           switch (DECL_FUNCTION_CODE (fndecl))
6212             {
6213             case BUILT_IN_EH_COPY_VALUES:
6214               r = gimple_call_arg (stmt, 1);
6215               r = move_stmt_eh_region_tree_nr (r, p);
6216               gimple_call_set_arg (stmt, 1, r);
6217               /* FALLTHRU */
6218
6219             case BUILT_IN_EH_POINTER:
6220             case BUILT_IN_EH_FILTER:
6221               r = gimple_call_arg (stmt, 0);
6222               r = move_stmt_eh_region_tree_nr (r, p);
6223               gimple_call_set_arg (stmt, 0, r);
6224               break;
6225
6226             default:
6227               break;
6228             }
6229       }
6230       break;
6231
6232     case GIMPLE_RESX:
6233       {
6234         int r = gimple_resx_region (stmt);
6235         r = move_stmt_eh_region_nr (r, p);
6236         gimple_resx_set_region (stmt, r);
6237       }
6238       break;
6239
6240     case GIMPLE_EH_DISPATCH:
6241       {
6242         int r = gimple_eh_dispatch_region (stmt);
6243         r = move_stmt_eh_region_nr (r, p);
6244         gimple_eh_dispatch_set_region (stmt, r);
6245       }
6246       break;
6247
6248     case GIMPLE_OMP_RETURN:
6249     case GIMPLE_OMP_CONTINUE:
6250       break;
6251     default:
6252       if (is_gimple_omp (stmt))
6253         {
6254           /* Do not remap variables inside OMP directives.  Variables
6255              referenced in clauses and directive header belong to the
6256              parent function and should not be moved into the child
6257              function.  */
6258           bool save_remap_decls_p = p->remap_decls_p;
6259           p->remap_decls_p = false;
6260           *handled_ops_p = true;
6261
6262           walk_gimple_seq_mod (gimple_omp_body_ptr (stmt), move_stmt_r,
6263                                move_stmt_op, wi);
6264
6265           p->remap_decls_p = save_remap_decls_p;
6266         }
6267       break;
6268     }
6269
6270   return NULL_TREE;
6271 }
6272
6273 /* Move basic block BB from function CFUN to function DEST_FN.  The
6274    block is moved out of the original linked list and placed after
6275    block AFTER in the new list.  Also, the block is removed from the
6276    original array of blocks and placed in DEST_FN's array of blocks.
6277    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6278    updated to reflect the moved edges.
6279
6280    The local variables are remapped to new instances, VARS_MAP is used
6281    to record the mapping.  */
6282
6283 static void
6284 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6285                   basic_block after, bool update_edge_count_p,
6286                   struct move_stmt_d *d)
6287 {
6288   struct control_flow_graph *cfg;
6289   edge_iterator ei;
6290   edge e;
6291   gimple_stmt_iterator si;
6292   unsigned old_len, new_len;
6293
6294   /* Remove BB from dominance structures.  */
6295   delete_from_dominance_info (CDI_DOMINATORS, bb);
6296   if (current_loops)
6297     remove_bb_from_loops (bb);
6298
6299   /* Link BB to the new linked list.  */
6300   move_block_after (bb, after);
6301
6302   /* Update the edge count in the corresponding flowgraphs.  */
6303   if (update_edge_count_p)
6304     FOR_EACH_EDGE (e, ei, bb->succs)
6305       {
6306         cfun->cfg->x_n_edges--;
6307         dest_cfun->cfg->x_n_edges++;
6308       }
6309
6310   /* Remove BB from the original basic block array.  */
6311   (*cfun->cfg->x_basic_block_info)[bb->index] = NULL;
6312   cfun->cfg->x_n_basic_blocks--;
6313
6314   /* Grow DEST_CFUN's basic block array if needed.  */
6315   cfg = dest_cfun->cfg;
6316   cfg->x_n_basic_blocks++;
6317   if (bb->index >= cfg->x_last_basic_block)
6318     cfg->x_last_basic_block = bb->index + 1;
6319
6320   old_len = vec_safe_length (cfg->x_basic_block_info);
6321   if ((unsigned) cfg->x_last_basic_block >= old_len)
6322     {
6323       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6324       vec_safe_grow_cleared (cfg->x_basic_block_info, new_len);
6325     }
6326
6327   (*cfg->x_basic_block_info)[bb->index] = bb;
6328
6329   /* Remap the variables in phi nodes.  */
6330   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6331     {
6332       gimple phi = gsi_stmt (si);
6333       use_operand_p use;
6334       tree op = PHI_RESULT (phi);
6335       ssa_op_iter oi;
6336       unsigned i;
6337
6338       if (virtual_operand_p (op))
6339         {
6340           /* Remove the phi nodes for virtual operands (alias analysis will be
6341              run for the new function, anyway).  */
6342           remove_phi_node (&si, true);
6343           continue;
6344         }
6345
6346       SET_PHI_RESULT (phi,
6347                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6348       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6349         {
6350           op = USE_FROM_PTR (use);
6351           if (TREE_CODE (op) == SSA_NAME)
6352             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6353         }
6354
6355       for (i = 0; i < EDGE_COUNT (bb->preds); i++)
6356         {
6357           location_t locus = gimple_phi_arg_location (phi, i);
6358           tree block = LOCATION_BLOCK (locus);
6359
6360           if (locus == UNKNOWN_LOCATION)
6361             continue;
6362           if (d->orig_block == NULL_TREE || block == d->orig_block)
6363             {
6364               if (d->new_block == NULL_TREE)
6365                 locus = LOCATION_LOCUS (locus);
6366               else
6367                 locus = COMBINE_LOCATION_DATA (line_table, locus, d->new_block);
6368               gimple_phi_arg_set_location (phi, i, locus);
6369             }
6370         }
6371
6372       gsi_next (&si);
6373     }
6374
6375   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6376     {
6377       gimple stmt = gsi_stmt (si);
6378       struct walk_stmt_info wi;
6379
6380       memset (&wi, 0, sizeof (wi));
6381       wi.info = d;
6382       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6383
6384       if (gimple_code (stmt) == GIMPLE_LABEL)
6385         {
6386           tree label = gimple_label_label (stmt);
6387           int uid = LABEL_DECL_UID (label);
6388
6389           gcc_assert (uid > -1);
6390
6391           old_len = vec_safe_length (cfg->x_label_to_block_map);
6392           if (old_len <= (unsigned) uid)
6393             {
6394               new_len = 3 * uid / 2 + 1;
6395               vec_safe_grow_cleared (cfg->x_label_to_block_map, new_len);
6396             }
6397
6398           (*cfg->x_label_to_block_map)[uid] = bb;
6399           (*cfun->cfg->x_label_to_block_map)[uid] = NULL;
6400
6401           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6402
6403           if (uid >= dest_cfun->cfg->last_label_uid)
6404             dest_cfun->cfg->last_label_uid = uid + 1;
6405         }
6406
6407       maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6408       remove_stmt_from_eh_lp_fn (cfun, stmt);
6409
6410       gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6411       gimple_remove_stmt_histograms (cfun, stmt);
6412
6413       /* We cannot leave any operands allocated from the operand caches of
6414          the current function.  */
6415       free_stmt_operands (stmt);
6416       push_cfun (dest_cfun);
6417       update_stmt (stmt);
6418       pop_cfun ();
6419     }
6420
6421   FOR_EACH_EDGE (e, ei, bb->succs)
6422     if (e->goto_locus != UNKNOWN_LOCATION)
6423       {
6424         tree block = LOCATION_BLOCK (e->goto_locus);
6425         if (d->orig_block == NULL_TREE
6426             || block == d->orig_block)
6427           e->goto_locus = d->new_block ?
6428               COMBINE_LOCATION_DATA (line_table, e->goto_locus, d->new_block) :
6429               LOCATION_LOCUS (e->goto_locus);
6430       }
6431 }
6432
6433 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6434    the outermost EH region.  Use REGION as the incoming base EH region.  */
6435
6436 static eh_region
6437 find_outermost_region_in_block (struct function *src_cfun,
6438                                 basic_block bb, eh_region region)
6439 {
6440   gimple_stmt_iterator si;
6441
6442   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6443     {
6444       gimple stmt = gsi_stmt (si);
6445       eh_region stmt_region;
6446       int lp_nr;
6447
6448       lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6449       stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6450       if (stmt_region)
6451         {
6452           if (region == NULL)
6453             region = stmt_region;
6454           else if (stmt_region != region)
6455             {
6456               region = eh_region_outermost (src_cfun, stmt_region, region);
6457               gcc_assert (region != NULL);
6458             }
6459         }
6460     }
6461
6462   return region;
6463 }
6464
6465 static tree
6466 new_label_mapper (tree decl, void *data)
6467 {
6468   htab_t hash = (htab_t) data;
6469   struct tree_map *m;
6470   void **slot;
6471
6472   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6473
6474   m = XNEW (struct tree_map);
6475   m->hash = DECL_UID (decl);
6476   m->base.from = decl;
6477   m->to = create_artificial_label (UNKNOWN_LOCATION);
6478   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6479   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6480     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6481
6482   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6483   gcc_assert (*slot == NULL);
6484
6485   *slot = m;
6486
6487   return m->to;
6488 }
6489
6490 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6491    subblocks.  */
6492
6493 static void
6494 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6495                                   tree to_context)
6496 {
6497   tree *tp, t;
6498
6499   for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6500     {
6501       t = *tp;
6502       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6503         continue;
6504       replace_by_duplicate_decl (&t, vars_map, to_context);
6505       if (t != *tp)
6506         {
6507           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6508             {
6509               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6510               DECL_HAS_VALUE_EXPR_P (t) = 1;
6511             }
6512           DECL_CHAIN (t) = DECL_CHAIN (*tp);
6513           *tp = t;
6514         }
6515     }
6516
6517   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6518     replace_block_vars_by_duplicates (block, vars_map, to_context);
6519 }
6520
6521 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6522    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
6523    single basic block in the original CFG and the new basic block is
6524    returned.  DEST_CFUN must not have a CFG yet.
6525
6526    Note that the region need not be a pure SESE region.  Blocks inside
6527    the region may contain calls to abort/exit.  The only restriction
6528    is that ENTRY_BB should be the only entry point and it must
6529    dominate EXIT_BB.
6530
6531    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6532    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6533    to the new function.
6534
6535    All local variables referenced in the region are assumed to be in
6536    the corresponding BLOCK_VARS and unexpanded variable lists
6537    associated with DEST_CFUN.  */
6538
6539 basic_block
6540 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6541                         basic_block exit_bb, tree orig_block)
6542 {
6543   vec<basic_block> bbs, dom_bbs;
6544   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6545   basic_block after, bb, *entry_pred, *exit_succ, abb;
6546   struct function *saved_cfun = cfun;
6547   int *entry_flag, *exit_flag;
6548   unsigned *entry_prob, *exit_prob;
6549   unsigned i, num_entry_edges, num_exit_edges;
6550   edge e;
6551   edge_iterator ei;
6552   htab_t new_label_map;
6553   struct pointer_map_t *vars_map, *eh_map;
6554   struct loop *loop = entry_bb->loop_father;
6555   struct move_stmt_d d;
6556
6557   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6558      region.  */
6559   gcc_assert (entry_bb != exit_bb
6560               && (!exit_bb
6561                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6562
6563   /* Collect all the blocks in the region.  Manually add ENTRY_BB
6564      because it won't be added by dfs_enumerate_from.  */
6565   bbs.create (0);
6566   bbs.safe_push (entry_bb);
6567   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6568
6569   /* The blocks that used to be dominated by something in BBS will now be
6570      dominated by the new block.  */
6571   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6572                                      bbs.address (),
6573                                      bbs.length ());
6574
6575   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
6576      the predecessor edges to ENTRY_BB and the successor edges to
6577      EXIT_BB so that we can re-attach them to the new basic block that
6578      will replace the region.  */
6579   num_entry_edges = EDGE_COUNT (entry_bb->preds);
6580   entry_pred = XNEWVEC (basic_block, num_entry_edges);
6581   entry_flag = XNEWVEC (int, num_entry_edges);
6582   entry_prob = XNEWVEC (unsigned, num_entry_edges);
6583   i = 0;
6584   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6585     {
6586       entry_prob[i] = e->probability;
6587       entry_flag[i] = e->flags;
6588       entry_pred[i++] = e->src;
6589       remove_edge (e);
6590     }
6591
6592   if (exit_bb)
6593     {
6594       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6595       exit_succ = XNEWVEC (basic_block, num_exit_edges);
6596       exit_flag = XNEWVEC (int, num_exit_edges);
6597       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6598       i = 0;
6599       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6600         {
6601           exit_prob[i] = e->probability;
6602           exit_flag[i] = e->flags;
6603           exit_succ[i++] = e->dest;
6604           remove_edge (e);
6605         }
6606     }
6607   else
6608     {
6609       num_exit_edges = 0;
6610       exit_succ = NULL;
6611       exit_flag = NULL;
6612       exit_prob = NULL;
6613     }
6614
6615   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6616   gcc_assert (dest_cfun->cfg == NULL);
6617   push_cfun (dest_cfun);
6618
6619   init_empty_tree_cfg ();
6620
6621   /* Initialize EH information for the new function.  */
6622   eh_map = NULL;
6623   new_label_map = NULL;
6624   if (saved_cfun->eh)
6625     {
6626       eh_region region = NULL;
6627
6628       FOR_EACH_VEC_ELT (bbs, i, bb)
6629         region = find_outermost_region_in_block (saved_cfun, bb, region);
6630
6631       init_eh_for_function ();
6632       if (region != NULL)
6633         {
6634           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6635           eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6636                                          new_label_mapper, new_label_map);
6637         }
6638     }
6639
6640   pop_cfun ();
6641
6642   /* Move blocks from BBS into DEST_CFUN.  */
6643   gcc_assert (bbs.length () >= 2);
6644   after = dest_cfun->cfg->x_entry_block_ptr;
6645   vars_map = pointer_map_create ();
6646
6647   memset (&d, 0, sizeof (d));
6648   d.orig_block = orig_block;
6649   d.new_block = DECL_INITIAL (dest_cfun->decl);
6650   d.from_context = cfun->decl;
6651   d.to_context = dest_cfun->decl;
6652   d.vars_map = vars_map;
6653   d.new_label_map = new_label_map;
6654   d.eh_map = eh_map;
6655   d.remap_decls_p = true;
6656
6657   FOR_EACH_VEC_ELT (bbs, i, bb)
6658     {
6659       /* No need to update edge counts on the last block.  It has
6660          already been updated earlier when we detached the region from
6661          the original CFG.  */
6662       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6663       after = bb;
6664     }
6665
6666   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6667   if (orig_block)
6668     {
6669       tree block;
6670       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6671                   == NULL_TREE);
6672       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6673         = BLOCK_SUBBLOCKS (orig_block);
6674       for (block = BLOCK_SUBBLOCKS (orig_block);
6675            block; block = BLOCK_CHAIN (block))
6676         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6677       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6678     }
6679
6680   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6681                                     vars_map, dest_cfun->decl);
6682
6683   if (new_label_map)
6684     htab_delete (new_label_map);
6685   if (eh_map)
6686     pointer_map_destroy (eh_map);
6687   pointer_map_destroy (vars_map);
6688
6689   /* Rewire the entry and exit blocks.  The successor to the entry
6690      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6691      the child function.  Similarly, the predecessor of DEST_FN's
6692      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6693      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6694      various CFG manipulation function get to the right CFG.
6695
6696      FIXME, this is silly.  The CFG ought to become a parameter to
6697      these helpers.  */
6698   push_cfun (dest_cfun);
6699   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6700   if (exit_bb)
6701     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6702   pop_cfun ();
6703
6704   /* Back in the original function, the SESE region has disappeared,
6705      create a new basic block in its place.  */
6706   bb = create_empty_bb (entry_pred[0]);
6707   if (current_loops)
6708     add_bb_to_loop (bb, loop);
6709   for (i = 0; i < num_entry_edges; i++)
6710     {
6711       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6712       e->probability = entry_prob[i];
6713     }
6714
6715   for (i = 0; i < num_exit_edges; i++)
6716     {
6717       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6718       e->probability = exit_prob[i];
6719     }
6720
6721   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6722   FOR_EACH_VEC_ELT (dom_bbs, i, abb)
6723     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6724   dom_bbs.release ();
6725
6726   if (exit_bb)
6727     {
6728       free (exit_prob);
6729       free (exit_flag);
6730       free (exit_succ);
6731     }
6732   free (entry_prob);
6733   free (entry_flag);
6734   free (entry_pred);
6735   bbs.release ();
6736
6737   return bb;
6738 }
6739
6740
6741 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in dumpfile.h)
6742    */
6743
6744 void
6745 dump_function_to_file (tree fndecl, FILE *file, int flags)
6746 {
6747   tree arg, var, old_current_fndecl = current_function_decl;
6748   struct function *dsf;
6749   bool ignore_topmost_bind = false, any_var = false;
6750   basic_block bb;
6751   tree chain;
6752   bool tmclone = (TREE_CODE (fndecl) == FUNCTION_DECL
6753                   && decl_is_tm_clone (fndecl));
6754   struct function *fun = DECL_STRUCT_FUNCTION (fndecl);
6755
6756   current_function_decl = fndecl;
6757   fprintf (file, "%s %s(", function_name (fun), tmclone ? "[tm-clone] " : "");
6758
6759   arg = DECL_ARGUMENTS (fndecl);
6760   while (arg)
6761     {
6762       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6763       fprintf (file, " ");
6764       print_generic_expr (file, arg, dump_flags);
6765       if (flags & TDF_VERBOSE)
6766         print_node (file, "", arg, 4);
6767       if (DECL_CHAIN (arg))
6768         fprintf (file, ", ");
6769       arg = DECL_CHAIN (arg);
6770     }
6771   fprintf (file, ")\n");
6772
6773   if (flags & TDF_VERBOSE)
6774     print_node (file, "", fndecl, 2);
6775
6776   dsf = DECL_STRUCT_FUNCTION (fndecl);
6777   if (dsf && (flags & TDF_EH))
6778     dump_eh_tree (file, dsf);
6779
6780   if (flags & TDF_RAW && !gimple_has_body_p (fndecl))
6781     {
6782       dump_node (fndecl, TDF_SLIM | flags, file);
6783       current_function_decl = old_current_fndecl;
6784       return;
6785     }
6786
6787   /* When GIMPLE is lowered, the variables are no longer available in
6788      BIND_EXPRs, so display them separately.  */
6789   if (fun && fun->decl == fndecl && (fun->curr_properties & PROP_gimple_lcf))
6790     {
6791       unsigned ix;
6792       ignore_topmost_bind = true;
6793
6794       fprintf (file, "{\n");
6795       if (!vec_safe_is_empty (fun->local_decls))
6796         FOR_EACH_LOCAL_DECL (fun, ix, var)
6797           {
6798             print_generic_decl (file, var, flags);
6799             if (flags & TDF_VERBOSE)
6800               print_node (file, "", var, 4);
6801             fprintf (file, "\n");
6802
6803             any_var = true;
6804           }
6805       if (gimple_in_ssa_p (cfun))
6806         for (ix = 1; ix < num_ssa_names; ++ix)
6807           {
6808             tree name = ssa_name (ix);
6809             if (name && !SSA_NAME_VAR (name))
6810               {
6811                 fprintf (file, "  ");
6812                 print_generic_expr (file, TREE_TYPE (name), flags);
6813                 fprintf (file, " ");
6814                 print_generic_expr (file, name, flags);
6815                 fprintf (file, ";\n");
6816
6817                 any_var = true;
6818               }
6819           }
6820     }
6821
6822   if (fun && fun->decl == fndecl
6823       && fun->cfg
6824       && basic_block_info_for_function (fun))
6825     {
6826       /* If the CFG has been built, emit a CFG-based dump.  */
6827       if (!ignore_topmost_bind)
6828         fprintf (file, "{\n");
6829
6830       if (any_var && n_basic_blocks_for_function (fun))
6831         fprintf (file, "\n");
6832
6833       FOR_EACH_BB_FN (bb, fun)
6834         dump_bb (file, bb, 2, flags | TDF_COMMENT);
6835
6836       fprintf (file, "}\n");
6837     }
6838   else if (DECL_SAVED_TREE (fndecl) == NULL)
6839     {
6840       /* The function is now in GIMPLE form but the CFG has not been
6841          built yet.  Emit the single sequence of GIMPLE statements
6842          that make up its body.  */
6843       gimple_seq body = gimple_body (fndecl);
6844
6845       if (gimple_seq_first_stmt (body)
6846           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6847           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6848         print_gimple_seq (file, body, 0, flags);
6849       else
6850         {
6851           if (!ignore_topmost_bind)
6852             fprintf (file, "{\n");
6853
6854           if (any_var)
6855             fprintf (file, "\n");
6856
6857           print_gimple_seq (file, body, 2, flags);
6858           fprintf (file, "}\n");
6859         }
6860     }
6861   else
6862     {
6863       int indent;
6864
6865       /* Make a tree based dump.  */
6866       chain = DECL_SAVED_TREE (fndecl);
6867       if (chain && TREE_CODE (chain) == BIND_EXPR)
6868         {
6869           if (ignore_topmost_bind)
6870             {
6871               chain = BIND_EXPR_BODY (chain);
6872               indent = 2;
6873             }
6874           else
6875             indent = 0;
6876         }
6877       else
6878         {
6879           if (!ignore_topmost_bind)
6880             fprintf (file, "{\n");
6881           indent = 2;
6882         }
6883
6884       if (any_var)
6885         fprintf (file, "\n");
6886
6887       print_generic_stmt_indented (file, chain, flags, indent);
6888       if (ignore_topmost_bind)
6889         fprintf (file, "}\n");
6890     }
6891
6892   if (flags & TDF_ENUMERATE_LOCALS)
6893     dump_enumerated_decls (file, flags);
6894   fprintf (file, "\n\n");
6895
6896   current_function_decl = old_current_fndecl;
6897 }
6898
6899 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6900
6901 DEBUG_FUNCTION void
6902 debug_function (tree fn, int flags)
6903 {
6904   dump_function_to_file (fn, stderr, flags);
6905 }
6906
6907
6908 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6909
6910 static void
6911 print_pred_bbs (FILE *file, basic_block bb)
6912 {
6913   edge e;
6914   edge_iterator ei;
6915
6916   FOR_EACH_EDGE (e, ei, bb->preds)
6917     fprintf (file, "bb_%d ", e->src->index);
6918 }
6919
6920
6921 /* Print on FILE the indexes for the successors of basic_block BB.  */
6922
6923 static void
6924 print_succ_bbs (FILE *file, basic_block bb)
6925 {
6926   edge e;
6927   edge_iterator ei;
6928
6929   FOR_EACH_EDGE (e, ei, bb->succs)
6930     fprintf (file, "bb_%d ", e->dest->index);
6931 }
6932
6933 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6934
6935 void
6936 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6937 {
6938   char *s_indent = (char *) alloca ((size_t) indent + 1);
6939   memset ((void *) s_indent, ' ', (size_t) indent);
6940   s_indent[indent] = '\0';
6941
6942   /* Print basic_block's header.  */
6943   if (verbosity >= 2)
6944     {
6945       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6946       print_pred_bbs (file, bb);
6947       fprintf (file, "}, succs = {");
6948       print_succ_bbs (file, bb);
6949       fprintf (file, "})\n");
6950     }
6951
6952   /* Print basic_block's body.  */
6953   if (verbosity >= 3)
6954     {
6955       fprintf (file, "%s  {\n", s_indent);
6956       dump_bb (file, bb, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6957       fprintf (file, "%s  }\n", s_indent);
6958     }
6959 }
6960
6961 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6962
6963 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6964    VERBOSITY level this outputs the contents of the loop, or just its
6965    structure.  */
6966
6967 static void
6968 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6969 {
6970   char *s_indent;
6971   basic_block bb;
6972
6973   if (loop == NULL)
6974     return;
6975
6976   s_indent = (char *) alloca ((size_t) indent + 1);
6977   memset ((void *) s_indent, ' ', (size_t) indent);
6978   s_indent[indent] = '\0';
6979
6980   /* Print loop's header.  */
6981   fprintf (file, "%sloop_%d (", s_indent, loop->num);
6982   if (loop->header)
6983     fprintf (file, "header = %d", loop->header->index);
6984   else
6985     {
6986       fprintf (file, "deleted)\n");
6987       return;
6988     }
6989   if (loop->latch)
6990     fprintf (file, ", latch = %d", loop->latch->index);
6991   else
6992     fprintf (file, ", multiple latches");
6993   fprintf (file, ", niter = ");
6994   print_generic_expr (file, loop->nb_iterations, 0);
6995
6996   if (loop->any_upper_bound)
6997     {
6998       fprintf (file, ", upper_bound = ");
6999       dump_double_int (file, loop->nb_iterations_upper_bound, true);
7000     }
7001
7002   if (loop->any_estimate)
7003     {
7004       fprintf (file, ", estimate = ");
7005       dump_double_int (file, loop->nb_iterations_estimate, true);
7006     }
7007   fprintf (file, ")\n");
7008
7009   /* Print loop's body.  */
7010   if (verbosity >= 1)
7011     {
7012       fprintf (file, "%s{\n", s_indent);
7013       FOR_EACH_BB (bb)
7014         if (bb->loop_father == loop)
7015           print_loops_bb (file, bb, indent, verbosity);
7016
7017       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
7018       fprintf (file, "%s}\n", s_indent);
7019     }
7020 }
7021
7022 /* Print the LOOP and its sibling loops on FILE, indented INDENT
7023    spaces.  Following VERBOSITY level this outputs the contents of the
7024    loop, or just its structure.  */
7025
7026 static void
7027 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
7028 {
7029   if (loop == NULL)
7030     return;
7031
7032   print_loop (file, loop, indent, verbosity);
7033   print_loop_and_siblings (file, loop->next, indent, verbosity);
7034 }
7035
7036 /* Follow a CFG edge from the entry point of the program, and on entry
7037    of a loop, pretty print the loop structure on FILE.  */
7038
7039 void
7040 print_loops (FILE *file, int verbosity)
7041 {
7042   basic_block bb;
7043
7044   bb = ENTRY_BLOCK_PTR;
7045   if (bb && bb->loop_father)
7046     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
7047 }
7048
7049
7050 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
7051
7052 DEBUG_FUNCTION void
7053 debug_loops (int verbosity)
7054 {
7055   print_loops (stderr, verbosity);
7056 }
7057
7058 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
7059
7060 DEBUG_FUNCTION void
7061 debug_loop (struct loop *loop, int verbosity)
7062 {
7063   print_loop (stderr, loop, 0, verbosity);
7064 }
7065
7066 /* Print on stderr the code of loop number NUM, at some VERBOSITY
7067    level.  */
7068
7069 DEBUG_FUNCTION void
7070 debug_loop_num (unsigned num, int verbosity)
7071 {
7072   debug_loop (get_loop (num), verbosity);
7073 }
7074
7075 /* Return true if BB ends with a call, possibly followed by some
7076    instructions that must stay with the call.  Return false,
7077    otherwise.  */
7078
7079 static bool
7080 gimple_block_ends_with_call_p (basic_block bb)
7081 {
7082   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7083   return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
7084 }
7085
7086
7087 /* Return true if BB ends with a conditional branch.  Return false,
7088    otherwise.  */
7089
7090 static bool
7091 gimple_block_ends_with_condjump_p (const_basic_block bb)
7092 {
7093   gimple stmt = last_stmt (CONST_CAST_BB (bb));
7094   return (stmt && gimple_code (stmt) == GIMPLE_COND);
7095 }
7096
7097
7098 /* Return true if we need to add fake edge to exit at statement T.
7099    Helper function for gimple_flow_call_edges_add.  */
7100
7101 static bool
7102 need_fake_edge_p (gimple t)
7103 {
7104   tree fndecl = NULL_TREE;
7105   int call_flags = 0;
7106
7107   /* NORETURN and LONGJMP calls already have an edge to exit.
7108      CONST and PURE calls do not need one.
7109      We don't currently check for CONST and PURE here, although
7110      it would be a good idea, because those attributes are
7111      figured out from the RTL in mark_constant_function, and
7112      the counter incrementation code from -fprofile-arcs
7113      leads to different results from -fbranch-probabilities.  */
7114   if (is_gimple_call (t))
7115     {
7116       fndecl = gimple_call_fndecl (t);
7117       call_flags = gimple_call_flags (t);
7118     }
7119
7120   if (is_gimple_call (t)
7121       && fndecl
7122       && DECL_BUILT_IN (fndecl)
7123       && (call_flags & ECF_NOTHROW)
7124       && !(call_flags & ECF_RETURNS_TWICE)
7125       /* fork() doesn't really return twice, but the effect of
7126          wrapping it in __gcov_fork() which calls __gcov_flush()
7127          and clears the counters before forking has the same
7128          effect as returning twice.  Force a fake edge.  */
7129       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
7130            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
7131     return false;
7132
7133   if (is_gimple_call (t))
7134     {
7135       edge_iterator ei;
7136       edge e;
7137       basic_block bb;
7138
7139       if (!(call_flags & ECF_NORETURN))
7140         return true;
7141
7142       bb = gimple_bb (t);
7143       FOR_EACH_EDGE (e, ei, bb->succs)
7144         if ((e->flags & EDGE_FAKE) == 0)
7145           return true;
7146     }
7147
7148   if (gimple_code (t) == GIMPLE_ASM
7149        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7150     return true;
7151
7152   return false;
7153 }
7154
7155
7156 /* Add fake edges to the function exit for any non constant and non
7157    noreturn calls (or noreturn calls with EH/abnormal edges),
7158    volatile inline assembly in the bitmap of blocks specified by BLOCKS
7159    or to the whole CFG if BLOCKS is zero.  Return the number of blocks
7160    that were split.
7161
7162    The goal is to expose cases in which entering a basic block does
7163    not imply that all subsequent instructions must be executed.  */
7164
7165 static int
7166 gimple_flow_call_edges_add (sbitmap blocks)
7167 {
7168   int i;
7169   int blocks_split = 0;
7170   int last_bb = last_basic_block;
7171   bool check_last_block = false;
7172
7173   if (n_basic_blocks == NUM_FIXED_BLOCKS)
7174     return 0;
7175
7176   if (! blocks)
7177     check_last_block = true;
7178   else
7179     check_last_block = bitmap_bit_p (blocks, EXIT_BLOCK_PTR->prev_bb->index);
7180
7181   /* In the last basic block, before epilogue generation, there will be
7182      a fallthru edge to EXIT.  Special care is required if the last insn
7183      of the last basic block is a call because make_edge folds duplicate
7184      edges, which would result in the fallthru edge also being marked
7185      fake, which would result in the fallthru edge being removed by
7186      remove_fake_edges, which would result in an invalid CFG.
7187
7188      Moreover, we can't elide the outgoing fake edge, since the block
7189      profiler needs to take this into account in order to solve the minimal
7190      spanning tree in the case that the call doesn't return.
7191
7192      Handle this by adding a dummy instruction in a new last basic block.  */
7193   if (check_last_block)
7194     {
7195       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
7196       gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
7197       gimple t = NULL;
7198
7199       if (!gsi_end_p (gsi))
7200         t = gsi_stmt (gsi);
7201
7202       if (t && need_fake_edge_p (t))
7203         {
7204           edge e;
7205
7206           e = find_edge (bb, EXIT_BLOCK_PTR);
7207           if (e)
7208             {
7209               gsi_insert_on_edge (e, gimple_build_nop ());
7210               gsi_commit_edge_inserts ();
7211             }
7212         }
7213     }
7214
7215   /* Now add fake edges to the function exit for any non constant
7216      calls since there is no way that we can determine if they will
7217      return or not...  */
7218   for (i = 0; i < last_bb; i++)
7219     {
7220       basic_block bb = BASIC_BLOCK (i);
7221       gimple_stmt_iterator gsi;
7222       gimple stmt, last_stmt;
7223
7224       if (!bb)
7225         continue;
7226
7227       if (blocks && !bitmap_bit_p (blocks, i))
7228         continue;
7229
7230       gsi = gsi_last_nondebug_bb (bb);
7231       if (!gsi_end_p (gsi))
7232         {
7233           last_stmt = gsi_stmt (gsi);
7234           do
7235             {
7236               stmt = gsi_stmt (gsi);
7237               if (need_fake_edge_p (stmt))
7238                 {
7239                   edge e;
7240
7241                   /* The handling above of the final block before the
7242                      epilogue should be enough to verify that there is
7243                      no edge to the exit block in CFG already.
7244                      Calling make_edge in such case would cause us to
7245                      mark that edge as fake and remove it later.  */
7246 #ifdef ENABLE_CHECKING
7247                   if (stmt == last_stmt)
7248                     {
7249                       e = find_edge (bb, EXIT_BLOCK_PTR);
7250                       gcc_assert (e == NULL);
7251                     }
7252 #endif
7253
7254                   /* Note that the following may create a new basic block
7255                      and renumber the existing basic blocks.  */
7256                   if (stmt != last_stmt)
7257                     {
7258                       e = split_block (bb, stmt);
7259                       if (e)
7260                         blocks_split++;
7261                     }
7262                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
7263                 }
7264               gsi_prev (&gsi);
7265             }
7266           while (!gsi_end_p (gsi));
7267         }
7268     }
7269
7270   if (blocks_split)
7271     verify_flow_info ();
7272
7273   return blocks_split;
7274 }
7275
7276 /* Removes edge E and all the blocks dominated by it, and updates dominance
7277    information.  The IL in E->src needs to be updated separately.
7278    If dominance info is not available, only the edge E is removed.*/
7279
7280 void
7281 remove_edge_and_dominated_blocks (edge e)
7282 {
7283   vec<basic_block> bbs_to_remove = vNULL;
7284   vec<basic_block> bbs_to_fix_dom = vNULL;
7285   bitmap df, df_idom;
7286   edge f;
7287   edge_iterator ei;
7288   bool none_removed = false;
7289   unsigned i;
7290   basic_block bb, dbb;
7291   bitmap_iterator bi;
7292
7293   if (!dom_info_available_p (CDI_DOMINATORS))
7294     {
7295       remove_edge (e);
7296       return;
7297     }
7298
7299   /* No updating is needed for edges to exit.  */
7300   if (e->dest == EXIT_BLOCK_PTR)
7301     {
7302       if (cfgcleanup_altered_bbs)
7303         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7304       remove_edge (e);
7305       return;
7306     }
7307
7308   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
7309      that is not dominated by E->dest, then this set is empty.  Otherwise,
7310      all the basic blocks dominated by E->dest are removed.
7311
7312      Also, to DF_IDOM we store the immediate dominators of the blocks in
7313      the dominance frontier of E (i.e., of the successors of the
7314      removed blocks, if there are any, and of E->dest otherwise).  */
7315   FOR_EACH_EDGE (f, ei, e->dest->preds)
7316     {
7317       if (f == e)
7318         continue;
7319
7320       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7321         {
7322           none_removed = true;
7323           break;
7324         }
7325     }
7326
7327   df = BITMAP_ALLOC (NULL);
7328   df_idom = BITMAP_ALLOC (NULL);
7329
7330   if (none_removed)
7331     bitmap_set_bit (df_idom,
7332                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7333   else
7334     {
7335       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7336       FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7337         {
7338           FOR_EACH_EDGE (f, ei, bb->succs)
7339             {
7340               if (f->dest != EXIT_BLOCK_PTR)
7341                 bitmap_set_bit (df, f->dest->index);
7342             }
7343         }
7344       FOR_EACH_VEC_ELT (bbs_to_remove, i, bb)
7345         bitmap_clear_bit (df, bb->index);
7346
7347       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7348         {
7349           bb = BASIC_BLOCK (i);
7350           bitmap_set_bit (df_idom,
7351                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7352         }
7353     }
7354
7355   if (cfgcleanup_altered_bbs)
7356     {
7357       /* Record the set of the altered basic blocks.  */
7358       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7359       bitmap_ior_into (cfgcleanup_altered_bbs, df);
7360     }
7361
7362   /* Remove E and the cancelled blocks.  */
7363   if (none_removed)
7364     remove_edge (e);
7365   else
7366     {
7367       /* Walk backwards so as to get a chance to substitute all
7368          released DEFs into debug stmts.  See
7369          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7370          details.  */
7371       for (i = bbs_to_remove.length (); i-- > 0; )
7372         delete_basic_block (bbs_to_remove[i]);
7373     }
7374
7375   /* Update the dominance information.  The immediate dominator may change only
7376      for blocks whose immediate dominator belongs to DF_IDOM:
7377
7378      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7379      removal.  Let Z the arbitrary block such that idom(Z) = Y and
7380      Z dominates X after the removal.  Before removal, there exists a path P
7381      from Y to X that avoids Z.  Let F be the last edge on P that is
7382      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
7383      dominates W, and because of P, Z does not dominate W), and W belongs to
7384      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
7385   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7386     {
7387       bb = BASIC_BLOCK (i);
7388       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7389            dbb;
7390            dbb = next_dom_son (CDI_DOMINATORS, dbb))
7391         bbs_to_fix_dom.safe_push (dbb);
7392     }
7393
7394   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7395
7396   BITMAP_FREE (df);
7397   BITMAP_FREE (df_idom);
7398   bbs_to_remove.release ();
7399   bbs_to_fix_dom.release ();
7400 }
7401
7402 /* Purge dead EH edges from basic block BB.  */
7403
7404 bool
7405 gimple_purge_dead_eh_edges (basic_block bb)
7406 {
7407   bool changed = false;
7408   edge e;
7409   edge_iterator ei;
7410   gimple stmt = last_stmt (bb);
7411
7412   if (stmt && stmt_can_throw_internal (stmt))
7413     return false;
7414
7415   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7416     {
7417       if (e->flags & EDGE_EH)
7418         {
7419           remove_edge_and_dominated_blocks (e);
7420           changed = true;
7421         }
7422       else
7423         ei_next (&ei);
7424     }
7425
7426   return changed;
7427 }
7428
7429 /* Purge dead EH edges from basic block listed in BLOCKS.  */
7430
7431 bool
7432 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7433 {
7434   bool changed = false;
7435   unsigned i;
7436   bitmap_iterator bi;
7437
7438   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7439     {
7440       basic_block bb = BASIC_BLOCK (i);
7441
7442       /* Earlier gimple_purge_dead_eh_edges could have removed
7443          this basic block already.  */
7444       gcc_assert (bb || changed);
7445       if (bb != NULL)
7446         changed |= gimple_purge_dead_eh_edges (bb);
7447     }
7448
7449   return changed;
7450 }
7451
7452 /* Purge dead abnormal call edges from basic block BB.  */
7453
7454 bool
7455 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7456 {
7457   bool changed = false;
7458   edge e;
7459   edge_iterator ei;
7460   gimple stmt = last_stmt (bb);
7461
7462   if (!cfun->has_nonlocal_label)
7463     return false;
7464
7465   if (stmt && stmt_can_make_abnormal_goto (stmt))
7466     return false;
7467
7468   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7469     {
7470       if (e->flags & EDGE_ABNORMAL)
7471         {
7472           remove_edge_and_dominated_blocks (e);
7473           changed = true;
7474         }
7475       else
7476         ei_next (&ei);
7477     }
7478
7479   return changed;
7480 }
7481
7482 /* Purge dead abnormal call edges from basic block listed in BLOCKS.  */
7483
7484 bool
7485 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7486 {
7487   bool changed = false;
7488   unsigned i;
7489   bitmap_iterator bi;
7490
7491   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7492     {
7493       basic_block bb = BASIC_BLOCK (i);
7494
7495       /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7496          this basic block already.  */
7497       gcc_assert (bb || changed);
7498       if (bb != NULL)
7499         changed |= gimple_purge_dead_abnormal_call_edges (bb);
7500     }
7501
7502   return changed;
7503 }
7504
7505 /* This function is called whenever a new edge is created or
7506    redirected.  */
7507
7508 static void
7509 gimple_execute_on_growing_pred (edge e)
7510 {
7511   basic_block bb = e->dest;
7512
7513   if (!gimple_seq_empty_p (phi_nodes (bb)))
7514     reserve_phi_args_for_new_edge (bb);
7515 }
7516
7517 /* This function is called immediately before edge E is removed from
7518    the edge vector E->dest->preds.  */
7519
7520 static void
7521 gimple_execute_on_shrinking_pred (edge e)
7522 {
7523   if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7524     remove_phi_args (e);
7525 }
7526
7527 /*---------------------------------------------------------------------------
7528   Helper functions for Loop versioning
7529   ---------------------------------------------------------------------------*/
7530
7531 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
7532    of 'first'. Both of them are dominated by 'new_head' basic block. When
7533    'new_head' was created by 'second's incoming edge it received phi arguments
7534    on the edge by split_edge(). Later, additional edge 'e' was created to
7535    connect 'new_head' and 'first'. Now this routine adds phi args on this
7536    additional edge 'e' that new_head to second edge received as part of edge
7537    splitting.  */
7538
7539 static void
7540 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7541                                   basic_block new_head, edge e)
7542 {
7543   gimple phi1, phi2;
7544   gimple_stmt_iterator psi1, psi2;
7545   tree def;
7546   edge e2 = find_edge (new_head, second);
7547
7548   /* Because NEW_HEAD has been created by splitting SECOND's incoming
7549      edge, we should always have an edge from NEW_HEAD to SECOND.  */
7550   gcc_assert (e2 != NULL);
7551
7552   /* Browse all 'second' basic block phi nodes and add phi args to
7553      edge 'e' for 'first' head. PHI args are always in correct order.  */
7554
7555   for (psi2 = gsi_start_phis (second),
7556        psi1 = gsi_start_phis (first);
7557        !gsi_end_p (psi2) && !gsi_end_p (psi1);
7558        gsi_next (&psi2),  gsi_next (&psi1))
7559     {
7560       phi1 = gsi_stmt (psi1);
7561       phi2 = gsi_stmt (psi2);
7562       def = PHI_ARG_DEF (phi2, e2->dest_idx);
7563       add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7564     }
7565 }
7566
7567
7568 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7569    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7570    the destination of the ELSE part.  */
7571
7572 static void
7573 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7574                                basic_block second_head ATTRIBUTE_UNUSED,
7575                                basic_block cond_bb, void *cond_e)
7576 {
7577   gimple_stmt_iterator gsi;
7578   gimple new_cond_expr;
7579   tree cond_expr = (tree) cond_e;
7580   edge e0;
7581
7582   /* Build new conditional expr */
7583   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7584                                                NULL_TREE, NULL_TREE);
7585
7586   /* Add new cond in cond_bb.  */
7587   gsi = gsi_last_bb (cond_bb);
7588   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7589
7590   /* Adjust edges appropriately to connect new head with first head
7591      as well as second head.  */
7592   e0 = single_succ_edge (cond_bb);
7593   e0->flags &= ~EDGE_FALLTHRU;
7594   e0->flags |= EDGE_FALSE_VALUE;
7595 }
7596
7597
7598 /* Do book-keeping of basic block BB for the profile consistency checker.
7599    If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
7600    then do post-pass accounting.  Store the counting in RECORD.  */
7601 static void
7602 gimple_account_profile_record (basic_block bb, int after_pass,
7603                                struct profile_record *record)
7604 {
7605   gimple_stmt_iterator i;
7606   for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
7607     {
7608       record->size[after_pass]
7609         += estimate_num_insns (gsi_stmt (i), &eni_size_weights);
7610       if (profile_status == PROFILE_READ)
7611         record->time[after_pass]
7612           += estimate_num_insns (gsi_stmt (i),
7613                                  &eni_time_weights) * bb->count;
7614       else if (profile_status == PROFILE_GUESSED)
7615         record->time[after_pass]
7616           += estimate_num_insns (gsi_stmt (i),
7617                                  &eni_time_weights) * bb->frequency;
7618     }
7619 }
7620
7621 struct cfg_hooks gimple_cfg_hooks = {
7622   "gimple",
7623   gimple_verify_flow_info,
7624   gimple_dump_bb,               /* dump_bb  */
7625   gimple_dump_bb_for_graph,     /* dump_bb_for_graph  */
7626   create_bb,                    /* create_basic_block  */
7627   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
7628   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
7629   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
7630   remove_bb,                    /* delete_basic_block  */
7631   gimple_split_block,           /* split_block  */
7632   gimple_move_block_after,      /* move_block_after  */
7633   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
7634   gimple_merge_blocks,          /* merge_blocks  */
7635   gimple_predict_edge,          /* predict_edge  */
7636   gimple_predicted_by_p,        /* predicted_by_p  */
7637   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
7638   gimple_duplicate_bb,          /* duplicate_block  */
7639   gimple_split_edge,            /* split_edge  */
7640   gimple_make_forwarder_block,  /* make_forward_block  */
7641   NULL,                         /* tidy_fallthru_edge  */
7642   NULL,                         /* force_nonfallthru */
7643   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7644   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7645   gimple_flow_call_edges_add,   /* flow_call_edges_add */
7646   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
7647   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7648   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7649   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7650   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7651   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7652   flush_pending_stmts,          /* flush_pending_stmts */  
7653   gimple_empty_block_p,           /* block_empty_p */
7654   gimple_split_block_before_cond_jump, /* split_block_before_cond_jump */
7655   gimple_account_profile_record,
7656 };
7657
7658
7659 /* Split all critical edges.  */
7660
7661 static unsigned int
7662 split_critical_edges (void)
7663 {
7664   basic_block bb;
7665   edge e;
7666   edge_iterator ei;
7667
7668   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7669      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
7670      mappings around the calls to split_edge.  */
7671   start_recording_case_labels ();
7672   FOR_ALL_BB (bb)
7673     {
7674       FOR_EACH_EDGE (e, ei, bb->succs)
7675         {
7676           if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7677             split_edge (e);
7678           /* PRE inserts statements to edges and expects that
7679              since split_critical_edges was done beforehand, committing edge
7680              insertions will not split more edges.  In addition to critical
7681              edges we must split edges that have multiple successors and
7682              end by control flow statements, such as RESX.
7683              Go ahead and split them too.  This matches the logic in
7684              gimple_find_edge_insert_loc.  */
7685           else if ((!single_pred_p (e->dest)
7686                     || !gimple_seq_empty_p (phi_nodes (e->dest))
7687                     || e->dest == EXIT_BLOCK_PTR)
7688                    && e->src != ENTRY_BLOCK_PTR
7689                    && !(e->flags & EDGE_ABNORMAL))
7690             {
7691               gimple_stmt_iterator gsi;
7692
7693               gsi = gsi_last_bb (e->src);
7694               if (!gsi_end_p (gsi)
7695                   && stmt_ends_bb_p (gsi_stmt (gsi))
7696                   && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7697                       && !gimple_call_builtin_p (gsi_stmt (gsi),
7698                                                  BUILT_IN_RETURN)))
7699                 split_edge (e);
7700             }
7701         }
7702     }
7703   end_recording_case_labels ();
7704   return 0;
7705 }
7706
7707 struct gimple_opt_pass pass_split_crit_edges =
7708 {
7709  {
7710   GIMPLE_PASS,
7711   "crited",                          /* name */
7712   OPTGROUP_NONE,                 /* optinfo_flags */
7713   NULL,                          /* gate */
7714   split_critical_edges,          /* execute */
7715   NULL,                          /* sub */
7716   NULL,                          /* next */
7717   0,                             /* static_pass_number */
7718   TV_TREE_SPLIT_EDGES,           /* tv_id */
7719   PROP_cfg,                      /* properties required */
7720   PROP_no_crit_edges,            /* properties_provided */
7721   0,                             /* properties_destroyed */
7722   0,                             /* todo_flags_start */
7723   TODO_verify_flow               /* todo_flags_finish */
7724  }
7725 };
7726
7727
7728 /* Build a ternary operation and gimplify it.  Emit code before GSI.
7729    Return the gimple_val holding the result.  */
7730
7731 tree
7732 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7733                  tree type, tree a, tree b, tree c)
7734 {
7735   tree ret;
7736   location_t loc = gimple_location (gsi_stmt (*gsi));
7737
7738   ret = fold_build3_loc (loc, code, type, a, b, c);
7739   STRIP_NOPS (ret);
7740
7741   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7742                                    GSI_SAME_STMT);
7743 }
7744
7745 /* Build a binary operation and gimplify it.  Emit code before GSI.
7746    Return the gimple_val holding the result.  */
7747
7748 tree
7749 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7750                  tree type, tree a, tree b)
7751 {
7752   tree ret;
7753
7754   ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7755   STRIP_NOPS (ret);
7756
7757   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7758                                    GSI_SAME_STMT);
7759 }
7760
7761 /* Build a unary operation and gimplify it.  Emit code before GSI.
7762    Return the gimple_val holding the result.  */
7763
7764 tree
7765 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7766                  tree a)
7767 {
7768   tree ret;
7769
7770   ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7771   STRIP_NOPS (ret);
7772
7773   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7774                                    GSI_SAME_STMT);
7775 }
7776
7777
7778 \f
7779 /* Emit return warnings.  */
7780
7781 static unsigned int
7782 execute_warn_function_return (void)
7783 {
7784   source_location location;
7785   gimple last;
7786   edge e;
7787   edge_iterator ei;
7788
7789   if (!targetm.warn_func_return (cfun->decl))
7790     return 0;
7791
7792   /* If we have a path to EXIT, then we do return.  */
7793   if (TREE_THIS_VOLATILE (cfun->decl)
7794       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7795     {
7796       location = UNKNOWN_LOCATION;
7797       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7798         {
7799           last = last_stmt (e->src);
7800           if ((gimple_code (last) == GIMPLE_RETURN
7801                || gimple_call_builtin_p (last, BUILT_IN_RETURN))
7802               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7803             break;
7804         }
7805       if (location == UNKNOWN_LOCATION)
7806         location = cfun->function_end_locus;
7807       warning_at (location, 0, "%<noreturn%> function does return");
7808     }
7809
7810   /* If we see "return;" in some basic block, then we do reach the end
7811      without returning a value.  */
7812   else if (warn_return_type
7813            && !TREE_NO_WARNING (cfun->decl)
7814            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7815            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7816     {
7817       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7818         {
7819           gimple last = last_stmt (e->src);
7820           if (gimple_code (last) == GIMPLE_RETURN
7821               && gimple_return_retval (last) == NULL
7822               && !gimple_no_warning_p (last))
7823             {
7824               location = gimple_location (last);
7825               if (location == UNKNOWN_LOCATION)
7826                   location = cfun->function_end_locus;
7827               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7828               TREE_NO_WARNING (cfun->decl) = 1;
7829               break;
7830             }
7831         }
7832     }
7833   return 0;
7834 }
7835
7836
7837 /* Given a basic block B which ends with a conditional and has
7838    precisely two successors, determine which of the edges is taken if
7839    the conditional is true and which is taken if the conditional is
7840    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7841
7842 void
7843 extract_true_false_edges_from_block (basic_block b,
7844                                      edge *true_edge,
7845                                      edge *false_edge)
7846 {
7847   edge e = EDGE_SUCC (b, 0);
7848
7849   if (e->flags & EDGE_TRUE_VALUE)
7850     {
7851       *true_edge = e;
7852       *false_edge = EDGE_SUCC (b, 1);
7853     }
7854   else
7855     {
7856       *false_edge = e;
7857       *true_edge = EDGE_SUCC (b, 1);
7858     }
7859 }
7860
7861 struct gimple_opt_pass pass_warn_function_return =
7862 {
7863  {
7864   GIMPLE_PASS,
7865   "*warn_function_return",              /* name */
7866   OPTGROUP_NONE,                        /* optinfo_flags */
7867   NULL,                                 /* gate */
7868   execute_warn_function_return,         /* execute */
7869   NULL,                                 /* sub */
7870   NULL,                                 /* next */
7871   0,                                    /* static_pass_number */
7872   TV_NONE,                              /* tv_id */
7873   PROP_cfg,                             /* properties_required */
7874   0,                                    /* properties_provided */
7875   0,                                    /* properties_destroyed */
7876   0,                                    /* todo_flags_start */
7877   0                                     /* todo_flags_finish */
7878  }
7879 };
7880
7881 /* Emit noreturn warnings.  */
7882
7883 static unsigned int
7884 execute_warn_function_noreturn (void)
7885 {
7886   if (!TREE_THIS_VOLATILE (current_function_decl)
7887       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
7888     warn_function_noreturn (current_function_decl);
7889   return 0;
7890 }
7891
7892 static bool
7893 gate_warn_function_noreturn (void)
7894 {
7895   return warn_suggest_attribute_noreturn;
7896 }
7897
7898 struct gimple_opt_pass pass_warn_function_noreturn =
7899 {
7900  {
7901   GIMPLE_PASS,
7902   "*warn_function_noreturn",            /* name */
7903   OPTGROUP_NONE,                        /* optinfo_flags */
7904   gate_warn_function_noreturn,          /* gate */
7905   execute_warn_function_noreturn,       /* execute */
7906   NULL,                                 /* sub */
7907   NULL,                                 /* next */
7908   0,                                    /* static_pass_number */
7909   TV_NONE,                              /* tv_id */
7910   PROP_cfg,                             /* properties_required */
7911   0,                                    /* properties_provided */
7912   0,                                    /* properties_destroyed */
7913   0,                                    /* todo_flags_start */
7914   0                                     /* todo_flags_finish */
7915  }
7916 };
7917
7918
7919 /* Walk a gimplified function and warn for functions whose return value is
7920    ignored and attribute((warn_unused_result)) is set.  This is done before
7921    inlining, so we don't have to worry about that.  */
7922
7923 static void
7924 do_warn_unused_result (gimple_seq seq)
7925 {
7926   tree fdecl, ftype;
7927   gimple_stmt_iterator i;
7928
7929   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7930     {
7931       gimple g = gsi_stmt (i);
7932
7933       switch (gimple_code (g))
7934         {
7935         case GIMPLE_BIND:
7936           do_warn_unused_result (gimple_bind_body (g));
7937           break;
7938         case GIMPLE_TRY:
7939           do_warn_unused_result (gimple_try_eval (g));
7940           do_warn_unused_result (gimple_try_cleanup (g));
7941           break;
7942         case GIMPLE_CATCH:
7943           do_warn_unused_result (gimple_catch_handler (g));
7944           break;
7945         case GIMPLE_EH_FILTER:
7946           do_warn_unused_result (gimple_eh_filter_failure (g));
7947           break;
7948
7949         case GIMPLE_CALL:
7950           if (gimple_call_lhs (g))
7951             break;
7952           if (gimple_call_internal_p (g))
7953             break;
7954
7955           /* This is a naked call, as opposed to a GIMPLE_CALL with an
7956              LHS.  All calls whose value is ignored should be
7957              represented like this.  Look for the attribute.  */
7958           fdecl = gimple_call_fndecl (g);
7959           ftype = gimple_call_fntype (g);
7960
7961           if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7962             {
7963               location_t loc = gimple_location (g);
7964
7965               if (fdecl)
7966                 warning_at (loc, OPT_Wunused_result,
7967                             "ignoring return value of %qD, "
7968                             "declared with attribute warn_unused_result",
7969                             fdecl);
7970               else
7971                 warning_at (loc, OPT_Wunused_result,
7972                             "ignoring return value of function "
7973                             "declared with attribute warn_unused_result");
7974             }
7975           break;
7976
7977         default:
7978           /* Not a container, not a call, or a call whose value is used.  */
7979           break;
7980         }
7981     }
7982 }
7983
7984 static unsigned int
7985 run_warn_unused_result (void)
7986 {
7987   do_warn_unused_result (gimple_body (current_function_decl));
7988   return 0;
7989 }
7990
7991 static bool
7992 gate_warn_unused_result (void)
7993 {
7994   return flag_warn_unused_result;
7995 }
7996
7997 struct gimple_opt_pass pass_warn_unused_result =
7998 {
7999   {
8000     GIMPLE_PASS,
8001     "*warn_unused_result",              /* name */
8002     OPTGROUP_NONE,                        /* optinfo_flags */
8003     gate_warn_unused_result,            /* gate */
8004     run_warn_unused_result,             /* execute */
8005     NULL,                               /* sub */
8006     NULL,                               /* next */
8007     0,                                  /* static_pass_number */
8008     TV_NONE,                            /* tv_id */
8009     PROP_gimple_any,                    /* properties_required */
8010     0,                                  /* properties_provided */
8011     0,                                  /* properties_destroyed */
8012     0,                                  /* todo_flags_start */
8013     0,                                  /* todo_flags_finish */
8014   }
8015 };
8016
8017
8018 /* Garbage collection support for edge_def.  */
8019
8020 extern void gt_ggc_mx (tree&);
8021 extern void gt_ggc_mx (gimple&);
8022 extern void gt_ggc_mx (rtx&);
8023 extern void gt_ggc_mx (basic_block&);
8024
8025 void
8026 gt_ggc_mx (edge_def *e)
8027 {
8028   tree block = LOCATION_BLOCK (e->goto_locus);
8029   gt_ggc_mx (e->src);
8030   gt_ggc_mx (e->dest);
8031   if (current_ir_type () == IR_GIMPLE)
8032     gt_ggc_mx (e->insns.g);
8033   else
8034     gt_ggc_mx (e->insns.r);
8035   gt_ggc_mx (block);
8036 }
8037
8038 /* PCH support for edge_def.  */
8039
8040 extern void gt_pch_nx (tree&);
8041 extern void gt_pch_nx (gimple&);
8042 extern void gt_pch_nx (rtx&);
8043 extern void gt_pch_nx (basic_block&);
8044
8045 void
8046 gt_pch_nx (edge_def *e)
8047 {
8048   tree block = LOCATION_BLOCK (e->goto_locus);
8049   gt_pch_nx (e->src);
8050   gt_pch_nx (e->dest);
8051   if (current_ir_type () == IR_GIMPLE)
8052     gt_pch_nx (e->insns.g);
8053   else
8054     gt_pch_nx (e->insns.r);
8055   gt_pch_nx (block);
8056 }
8057
8058 void
8059 gt_pch_nx (edge_def *e, gt_pointer_operator op, void *cookie)
8060 {
8061   tree block = LOCATION_BLOCK (e->goto_locus);
8062   op (&(e->src), cookie);
8063   op (&(e->dest), cookie);
8064   if (current_ir_type () == IR_GIMPLE)
8065     op (&(e->insns.g), cookie);
8066   else
8067     op (&(e->insns.r), cookie);
8068   op (&(block), cookie);
8069 }