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