OSDN Git Service

Daily bump.
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfg.c
1 /* Control flow functions for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3    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
2883               || TREE_CODE (x) == PARM_DECL
2884               || TREE_CODE (x) == RESULT_DECL))
2885           return NULL;
2886         if (!TREE_ADDRESSABLE (x))
2887           {
2888             error ("address taken, but ADDRESSABLE bit not set");
2889             return x;
2890           }
2891         if (DECL_GIMPLE_REG_P (x))
2892           {
2893             error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2894             return x;
2895           }
2896
2897         break;
2898       }
2899
2900     case COND_EXPR:
2901       x = COND_EXPR_COND (t);
2902       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2903         {
2904           error ("non-integral used in condition");
2905           return x;
2906         }
2907       if (!is_gimple_condexpr (x))
2908         {
2909           error ("invalid conditional operand");
2910           return x;
2911         }
2912       break;
2913
2914     case NON_LVALUE_EXPR:
2915         gcc_unreachable ();
2916
2917     CASE_CONVERT:
2918     case FIX_TRUNC_EXPR:
2919     case FLOAT_EXPR:
2920     case NEGATE_EXPR:
2921     case ABS_EXPR:
2922     case BIT_NOT_EXPR:
2923     case TRUTH_NOT_EXPR:
2924       CHECK_OP (0, "invalid operand to unary operator");
2925       break;
2926
2927     case REALPART_EXPR:
2928     case IMAGPART_EXPR:
2929     case COMPONENT_REF:
2930     case ARRAY_REF:
2931     case ARRAY_RANGE_REF:
2932     case BIT_FIELD_REF:
2933     case VIEW_CONVERT_EXPR:
2934       /* We have a nest of references.  Verify that each of the operands
2935          that determine where to reference is either a constant or a variable,
2936          verify that the base is valid, and then show we've already checked
2937          the subtrees.  */
2938       while (handled_component_p (t))
2939         {
2940           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2941             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2942           else if (TREE_CODE (t) == ARRAY_REF
2943                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2944             {
2945               CHECK_OP (1, "invalid array index");
2946               if (TREE_OPERAND (t, 2))
2947                 CHECK_OP (2, "invalid array lower bound");
2948               if (TREE_OPERAND (t, 3))
2949                 CHECK_OP (3, "invalid array stride");
2950             }
2951           else if (TREE_CODE (t) == BIT_FIELD_REF)
2952             {
2953               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2954                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2955                 {
2956                   error ("invalid position or size operand to BIT_FIELD_REF");
2957                   return t;
2958                 }
2959               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2960                        && (TYPE_PRECISION (TREE_TYPE (t))
2961                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2962                 {
2963                   error ("integral result type precision does not match "
2964                          "field size of BIT_FIELD_REF");
2965                   return t;
2966                 }
2967               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2968                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2969                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2970                 {
2971                   error ("mode precision of non-integral result does not "
2972                          "match field size of BIT_FIELD_REF");
2973                   return t;
2974                 }
2975             }
2976
2977           t = TREE_OPERAND (t, 0);
2978         }
2979
2980       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2981         {
2982           error ("invalid reference prefix");
2983           return t;
2984         }
2985       *walk_subtrees = 0;
2986       break;
2987     case PLUS_EXPR:
2988     case MINUS_EXPR:
2989       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2990          POINTER_PLUS_EXPR. */
2991       if (POINTER_TYPE_P (TREE_TYPE (t)))
2992         {
2993           error ("invalid operand to plus/minus, type is a pointer");
2994           return t;
2995         }
2996       CHECK_OP (0, "invalid operand to binary operator");
2997       CHECK_OP (1, "invalid operand to binary operator");
2998       break;
2999
3000     case POINTER_PLUS_EXPR:
3001       /* Check to make sure the first operand is a pointer or reference type. */
3002       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3003         {
3004           error ("invalid operand to pointer plus, first operand is not a pointer");
3005           return t;
3006         }
3007       /* Check to make sure the second operand is an integer with type of
3008          sizetype.  */
3009       if (!useless_type_conversion_p (sizetype,
3010                                      TREE_TYPE (TREE_OPERAND (t, 1))))
3011         {
3012           error ("invalid operand to pointer plus, second operand is not an "
3013                  "integer with type of sizetype.");
3014           return t;
3015         }
3016       /* FALLTHROUGH */
3017     case LT_EXPR:
3018     case LE_EXPR:
3019     case GT_EXPR:
3020     case GE_EXPR:
3021     case EQ_EXPR:
3022     case NE_EXPR:
3023     case UNORDERED_EXPR:
3024     case ORDERED_EXPR:
3025     case UNLT_EXPR:
3026     case UNLE_EXPR:
3027     case UNGT_EXPR:
3028     case UNGE_EXPR:
3029     case UNEQ_EXPR:
3030     case LTGT_EXPR:
3031     case MULT_EXPR:
3032     case TRUNC_DIV_EXPR:
3033     case CEIL_DIV_EXPR:
3034     case FLOOR_DIV_EXPR:
3035     case ROUND_DIV_EXPR:
3036     case TRUNC_MOD_EXPR:
3037     case CEIL_MOD_EXPR:
3038     case FLOOR_MOD_EXPR:
3039     case ROUND_MOD_EXPR:
3040     case RDIV_EXPR:
3041     case EXACT_DIV_EXPR:
3042     case MIN_EXPR:
3043     case MAX_EXPR:
3044     case LSHIFT_EXPR:
3045     case RSHIFT_EXPR:
3046     case LROTATE_EXPR:
3047     case RROTATE_EXPR:
3048     case BIT_IOR_EXPR:
3049     case BIT_XOR_EXPR:
3050     case BIT_AND_EXPR:
3051       CHECK_OP (0, "invalid operand to binary operator");
3052       CHECK_OP (1, "invalid operand to binary operator");
3053       break;
3054
3055     case CONSTRUCTOR:
3056       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3057         *walk_subtrees = 0;
3058       break;
3059
3060     default:
3061       break;
3062     }
3063   return NULL;
3064
3065 #undef CHECK_OP
3066 }
3067
3068
3069 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3070    Returns true if there is an error, otherwise false.  */
3071
3072 static bool
3073 verify_types_in_gimple_min_lval (tree expr)
3074 {
3075   tree op;
3076
3077   if (is_gimple_id (expr))
3078     return false;
3079
3080   if (!INDIRECT_REF_P (expr)
3081       && TREE_CODE (expr) != TARGET_MEM_REF)
3082     {
3083       error ("invalid expression for min lvalue");
3084       return true;
3085     }
3086
3087   /* TARGET_MEM_REFs are strange beasts.  */
3088   if (TREE_CODE (expr) == TARGET_MEM_REF)
3089     return false;
3090
3091   op = TREE_OPERAND (expr, 0);
3092   if (!is_gimple_val (op))
3093     {
3094       error ("invalid operand in indirect reference");
3095       debug_generic_stmt (op);
3096       return true;
3097     }
3098   if (!useless_type_conversion_p (TREE_TYPE (expr),
3099                                   TREE_TYPE (TREE_TYPE (op))))
3100     {
3101       error ("type mismatch in indirect reference");
3102       debug_generic_stmt (TREE_TYPE (expr));
3103       debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3104       return true;
3105     }
3106
3107   return false;
3108 }
3109
3110 /* Verify if EXPR is a valid GIMPLE reference expression.  Returns true
3111    if there is an error, otherwise false.  */
3112
3113 static bool
3114 verify_types_in_gimple_reference (tree expr)
3115 {
3116   while (handled_component_p (expr))
3117     {
3118       tree op = TREE_OPERAND (expr, 0);
3119
3120       if (TREE_CODE (expr) == ARRAY_REF
3121           || TREE_CODE (expr) == ARRAY_RANGE_REF)
3122         {
3123           if (!is_gimple_val (TREE_OPERAND (expr, 1))
3124               || (TREE_OPERAND (expr, 2)
3125                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
3126               || (TREE_OPERAND (expr, 3)
3127                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
3128             {
3129               error ("invalid operands to array reference");
3130               debug_generic_stmt (expr);
3131               return true;
3132             }
3133         }
3134
3135       /* Verify if the reference array element types are compatible.  */
3136       if (TREE_CODE (expr) == ARRAY_REF
3137           && !useless_type_conversion_p (TREE_TYPE (expr),
3138                                          TREE_TYPE (TREE_TYPE (op))))
3139         {
3140           error ("type mismatch in array reference");
3141           debug_generic_stmt (TREE_TYPE (expr));
3142           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3143           return true;
3144         }
3145       if (TREE_CODE (expr) == ARRAY_RANGE_REF
3146           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3147                                          TREE_TYPE (TREE_TYPE (op))))
3148         {
3149           error ("type mismatch in array range reference");
3150           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3151           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3152           return true;
3153         }
3154
3155       if ((TREE_CODE (expr) == REALPART_EXPR
3156            || TREE_CODE (expr) == IMAGPART_EXPR)
3157           && !useless_type_conversion_p (TREE_TYPE (expr),
3158                                          TREE_TYPE (TREE_TYPE (op))))
3159         {
3160           error ("type mismatch in real/imagpart reference");
3161           debug_generic_stmt (TREE_TYPE (expr));
3162           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3163           return true;
3164         }
3165
3166       if (TREE_CODE (expr) == COMPONENT_REF
3167           && !useless_type_conversion_p (TREE_TYPE (expr),
3168                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3169         {
3170           error ("type mismatch in component reference");
3171           debug_generic_stmt (TREE_TYPE (expr));
3172           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3173           return true;
3174         }
3175
3176       /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3177          is nothing to verify.  Gross mismatches at most invoke
3178          undefined behavior.  */
3179       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR
3180           && !handled_component_p (op))
3181         return false;
3182
3183       expr = op;
3184     }
3185
3186   return verify_types_in_gimple_min_lval (expr);
3187 }
3188
3189 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3190    list of pointer-to types that is trivially convertible to DEST.  */
3191
3192 static bool
3193 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3194 {
3195   tree src;
3196
3197   if (!TYPE_POINTER_TO (src_obj))
3198     return true;
3199
3200   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3201     if (useless_type_conversion_p (dest, src))
3202       return true;
3203
3204   return false;
3205 }
3206
3207 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3208    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3209
3210 static bool
3211 valid_fixed_convert_types_p (tree type1, tree type2)
3212 {
3213   return (FIXED_POINT_TYPE_P (type1)
3214           && (INTEGRAL_TYPE_P (type2)
3215               || SCALAR_FLOAT_TYPE_P (type2)
3216               || FIXED_POINT_TYPE_P (type2)));
3217 }
3218
3219 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3220    is a problem, otherwise false.  */
3221
3222 static bool
3223 verify_gimple_call (gimple stmt)
3224 {
3225   tree fn = gimple_call_fn (stmt);
3226   tree fntype;
3227
3228   if (!POINTER_TYPE_P (TREE_TYPE  (fn))
3229       || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3230           && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE))
3231     {
3232       error ("non-function in gimple call");
3233       return true;
3234     }
3235
3236   if (gimple_call_lhs (stmt)
3237       && !is_gimple_lvalue (gimple_call_lhs (stmt)))
3238     {
3239       error ("invalid LHS in gimple call");
3240       return true;
3241     }
3242
3243   fntype = TREE_TYPE (TREE_TYPE (fn));
3244   if (gimple_call_lhs (stmt)
3245       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3246                                      TREE_TYPE (fntype))
3247       /* ???  At least C++ misses conversions at assignments from
3248          void * call results.
3249          ???  Java is completely off.  Especially with functions
3250          returning java.lang.Object.
3251          For now simply allow arbitrary pointer type conversions.  */
3252       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3253            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3254     {
3255       error ("invalid conversion in gimple call");
3256       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3257       debug_generic_stmt (TREE_TYPE (fntype));
3258       return true;
3259     }
3260
3261   /* ???  The C frontend passes unpromoted arguments in case it
3262      didn't see a function declaration before the call.  So for now
3263      leave the call arguments unverified.  Once we gimplify
3264      unit-at-a-time we have a chance to fix this.  */
3265
3266   return false;
3267 }
3268
3269 /* Verifies the gimple comparison with the result type TYPE and
3270    the operands OP0 and OP1.  */
3271
3272 static bool
3273 verify_gimple_comparison (tree type, tree op0, tree op1)
3274 {
3275   tree op0_type = TREE_TYPE (op0);
3276   tree op1_type = TREE_TYPE (op1);
3277
3278   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3279     {
3280       error ("invalid operands in gimple comparison");
3281       return true;
3282     }
3283
3284   /* For comparisons we do not have the operations type as the
3285      effective type the comparison is carried out in.  Instead
3286      we require that either the first operand is trivially
3287      convertible into the second, or the other way around.
3288      The resulting type of a comparison may be any integral type.
3289      Because we special-case pointers to void we allow
3290      comparisons of pointers with the same mode as well.  */
3291   if ((!useless_type_conversion_p (op0_type, op1_type)
3292        && !useless_type_conversion_p (op1_type, op0_type)
3293        && (!POINTER_TYPE_P (op0_type)
3294            || !POINTER_TYPE_P (op1_type)
3295            || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3296       || !INTEGRAL_TYPE_P (type))
3297     {
3298       error ("type mismatch in comparison expression");
3299       debug_generic_expr (type);
3300       debug_generic_expr (op0_type);
3301       debug_generic_expr (op1_type);
3302       return true;
3303     }
3304
3305   return false;
3306 }
3307
3308 /* Verify a gimple assignment statement STMT with an unary rhs.
3309    Returns true if anything is wrong.  */
3310
3311 static bool
3312 verify_gimple_assign_unary (gimple stmt)
3313 {
3314   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3315   tree lhs = gimple_assign_lhs (stmt);
3316   tree lhs_type = TREE_TYPE (lhs);
3317   tree rhs1 = gimple_assign_rhs1 (stmt);
3318   tree rhs1_type = TREE_TYPE (rhs1);
3319
3320   if (!is_gimple_reg (lhs)
3321       && !(optimize == 0
3322            && TREE_CODE (lhs_type) == COMPLEX_TYPE))
3323     {
3324       error ("non-register as LHS of unary operation");
3325       return true;
3326     }
3327
3328   if (!is_gimple_val (rhs1))
3329     {
3330       error ("invalid operand in unary operation");
3331       return true;
3332     }
3333
3334   /* First handle conversions.  */
3335   switch (rhs_code)
3336     {
3337     CASE_CONVERT:
3338       {
3339         /* Allow conversions between integral types and pointers only if
3340            there is no sign or zero extension involved.
3341            For targets were the precision of sizetype doesn't match that
3342            of pointers we need to allow arbitrary conversions from and
3343            to sizetype.  */
3344         if ((POINTER_TYPE_P (lhs_type)
3345              && INTEGRAL_TYPE_P (rhs1_type)
3346              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3347                  || rhs1_type == sizetype))
3348             || (POINTER_TYPE_P (rhs1_type)
3349                 && INTEGRAL_TYPE_P (lhs_type)
3350                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3351                     || lhs_type == sizetype)))
3352           return false;
3353
3354         /* Allow conversion from integer to offset type and vice versa.  */
3355         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3356              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3357             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3358                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3359           return false;
3360
3361         /* Otherwise assert we are converting between types of the
3362            same kind.  */
3363         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3364           {
3365             error ("invalid types in nop conversion");
3366             debug_generic_expr (lhs_type);
3367             debug_generic_expr (rhs1_type);
3368             return true;
3369           }
3370
3371         return false;
3372       }
3373
3374     case FIXED_CONVERT_EXPR:
3375       {
3376         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3377             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3378           {
3379             error ("invalid types in fixed-point conversion");
3380             debug_generic_expr (lhs_type);
3381             debug_generic_expr (rhs1_type);
3382             return true;
3383           }
3384
3385         return false;
3386       }
3387
3388     case FLOAT_EXPR:
3389       {
3390         if (!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3391           {
3392             error ("invalid types in conversion to floating point");
3393             debug_generic_expr (lhs_type);
3394             debug_generic_expr (rhs1_type);
3395             return true;
3396           }
3397
3398         return false;
3399       }
3400
3401     case FIX_TRUNC_EXPR:
3402       {
3403         if (!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3404           {
3405             error ("invalid types in conversion to integer");
3406             debug_generic_expr (lhs_type);
3407             debug_generic_expr (rhs1_type);
3408             return true;
3409           }
3410
3411         return false;
3412       }
3413
3414     case TRUTH_NOT_EXPR:
3415       {
3416       }
3417
3418     case NEGATE_EXPR:
3419     case ABS_EXPR:
3420     case BIT_NOT_EXPR:
3421     case PAREN_EXPR:
3422     case NON_LVALUE_EXPR:
3423     case CONJ_EXPR:
3424     case REDUC_MAX_EXPR:
3425     case REDUC_MIN_EXPR:
3426     case REDUC_PLUS_EXPR:
3427     case VEC_UNPACK_HI_EXPR:
3428     case VEC_UNPACK_LO_EXPR:
3429     case VEC_UNPACK_FLOAT_HI_EXPR:
3430     case VEC_UNPACK_FLOAT_LO_EXPR:
3431       break;
3432
3433     default:
3434       gcc_unreachable ();
3435     }
3436
3437   /* For the remaining codes assert there is no conversion involved.  */
3438   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3439     {
3440       error ("non-trivial conversion in unary operation");
3441       debug_generic_expr (lhs_type);
3442       debug_generic_expr (rhs1_type);
3443       return true;
3444     }
3445
3446   return false;
3447 }
3448
3449 /* Verify a gimple assignment statement STMT with a binary rhs.
3450    Returns true if anything is wrong.  */
3451
3452 static bool
3453 verify_gimple_assign_binary (gimple stmt)
3454 {
3455   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3456   tree lhs = gimple_assign_lhs (stmt);
3457   tree lhs_type = TREE_TYPE (lhs);
3458   tree rhs1 = gimple_assign_rhs1 (stmt);
3459   tree rhs1_type = TREE_TYPE (rhs1);
3460   tree rhs2 = gimple_assign_rhs2 (stmt);
3461   tree rhs2_type = TREE_TYPE (rhs2);
3462
3463   if (!is_gimple_reg (lhs)
3464       && !(optimize == 0
3465            && TREE_CODE (lhs_type) == COMPLEX_TYPE))
3466     {
3467       error ("non-register as LHS of binary operation");
3468       return true;
3469     }
3470
3471   if (!is_gimple_val (rhs1)
3472       || !is_gimple_val (rhs2))
3473     {
3474       error ("invalid operands in binary operation");
3475       return true;
3476     }
3477
3478   /* First handle operations that involve different types.  */
3479   switch (rhs_code)
3480     {
3481     case COMPLEX_EXPR:
3482       {
3483         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3484             || !(INTEGRAL_TYPE_P (rhs1_type)
3485                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3486             || !(INTEGRAL_TYPE_P (rhs2_type)
3487                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3488           {
3489             error ("type mismatch in complex expression");
3490             debug_generic_expr (lhs_type);
3491             debug_generic_expr (rhs1_type);
3492             debug_generic_expr (rhs2_type);
3493             return true;
3494           }
3495
3496         return false;
3497       }
3498
3499     case LSHIFT_EXPR:
3500     case RSHIFT_EXPR:
3501       if (FIXED_POINT_TYPE_P (rhs1_type)
3502           && INTEGRAL_TYPE_P (rhs2_type)
3503           && useless_type_conversion_p (lhs_type, rhs1_type))
3504         return false;
3505       /* Fall through.  */
3506
3507     case LROTATE_EXPR:
3508     case RROTATE_EXPR:
3509       {
3510         if (!INTEGRAL_TYPE_P (rhs1_type)
3511             || !INTEGRAL_TYPE_P (rhs2_type)
3512             || !useless_type_conversion_p (lhs_type, rhs1_type))
3513           {
3514             error ("type mismatch in shift expression");
3515             debug_generic_expr (lhs_type);
3516             debug_generic_expr (rhs1_type);
3517             debug_generic_expr (rhs2_type);
3518             return true;
3519           }
3520
3521         return false;
3522       }
3523
3524     case VEC_LSHIFT_EXPR:
3525     case VEC_RSHIFT_EXPR:
3526       {
3527         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3528             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3529                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type)))
3530             || (!INTEGRAL_TYPE_P (rhs2_type)
3531                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3532                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3533             || !useless_type_conversion_p (lhs_type, rhs1_type))
3534           {
3535             error ("type mismatch in vector shift expression");
3536             debug_generic_expr (lhs_type);
3537             debug_generic_expr (rhs1_type);
3538             debug_generic_expr (rhs2_type);
3539             return true;
3540           }
3541
3542         return false;
3543       }
3544
3545     case POINTER_PLUS_EXPR:
3546       {
3547         if (!POINTER_TYPE_P (rhs1_type)
3548             || !useless_type_conversion_p (lhs_type, rhs1_type)
3549             || !useless_type_conversion_p (sizetype, rhs2_type))
3550           {
3551             error ("type mismatch in pointer plus expression");
3552             debug_generic_stmt (lhs_type);
3553             debug_generic_stmt (rhs1_type);
3554             debug_generic_stmt (rhs2_type);
3555             return true;
3556           }
3557
3558         return false;
3559       } 
3560
3561     case TRUTH_ANDIF_EXPR:
3562     case TRUTH_ORIF_EXPR:
3563       gcc_unreachable ();
3564
3565     case TRUTH_AND_EXPR:
3566     case TRUTH_OR_EXPR:
3567     case TRUTH_XOR_EXPR:
3568       {
3569         /* We allow any kind of integral typed argument and result.  */
3570         if (!INTEGRAL_TYPE_P (rhs1_type)
3571             || !INTEGRAL_TYPE_P (rhs2_type)
3572             || !INTEGRAL_TYPE_P (lhs_type))
3573           {
3574             error ("type mismatch in binary truth expression");
3575             debug_generic_expr (lhs_type);
3576             debug_generic_expr (rhs1_type);
3577             debug_generic_expr (rhs2_type);
3578             return true;
3579           }
3580
3581         return false;
3582       }
3583
3584     case LT_EXPR:
3585     case LE_EXPR:
3586     case GT_EXPR:
3587     case GE_EXPR:
3588     case EQ_EXPR:
3589     case NE_EXPR:
3590     case UNORDERED_EXPR:
3591     case ORDERED_EXPR:
3592     case UNLT_EXPR:
3593     case UNLE_EXPR:
3594     case UNGT_EXPR:
3595     case UNGE_EXPR:
3596     case UNEQ_EXPR:
3597     case LTGT_EXPR:
3598       /* Comparisons are also binary, but the result type is not
3599          connected to the operand types.  */
3600       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3601
3602     case PLUS_EXPR:
3603     case MINUS_EXPR:
3604       {
3605         if (POINTER_TYPE_P (lhs_type)
3606             || POINTER_TYPE_P (rhs1_type)
3607             || POINTER_TYPE_P (rhs2_type))
3608           {
3609             error ("invalid (pointer) operands to plus/minus");
3610             return true;
3611           }
3612
3613         /* Continue with generic binary expression handling.  */
3614         break;
3615       }
3616
3617     case MULT_EXPR:
3618     case TRUNC_DIV_EXPR:
3619     case CEIL_DIV_EXPR:
3620     case FLOOR_DIV_EXPR:
3621     case ROUND_DIV_EXPR:
3622     case TRUNC_MOD_EXPR:
3623     case CEIL_MOD_EXPR:
3624     case FLOOR_MOD_EXPR:
3625     case ROUND_MOD_EXPR:
3626     case RDIV_EXPR:
3627     case EXACT_DIV_EXPR:
3628     case MIN_EXPR:
3629     case MAX_EXPR:
3630     case BIT_IOR_EXPR:
3631     case BIT_XOR_EXPR:
3632     case BIT_AND_EXPR:
3633     case WIDEN_SUM_EXPR:
3634     case WIDEN_MULT_EXPR:
3635     case VEC_WIDEN_MULT_HI_EXPR:
3636     case VEC_WIDEN_MULT_LO_EXPR:
3637     case VEC_PACK_TRUNC_EXPR:
3638     case VEC_PACK_SAT_EXPR:
3639     case VEC_PACK_FIX_TRUNC_EXPR:
3640     case VEC_EXTRACT_EVEN_EXPR:
3641     case VEC_EXTRACT_ODD_EXPR:
3642     case VEC_INTERLEAVE_HIGH_EXPR:
3643     case VEC_INTERLEAVE_LOW_EXPR:
3644       /* Continue with generic binary expression handling.  */
3645       break;
3646
3647     default:
3648       gcc_unreachable ();
3649     }
3650
3651   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3652       || !useless_type_conversion_p (lhs_type, rhs2_type))
3653     {
3654       error ("type mismatch in binary expression");
3655       debug_generic_stmt (lhs_type);
3656       debug_generic_stmt (rhs1_type);
3657       debug_generic_stmt (rhs2_type);
3658       return true;
3659     }
3660
3661   return false;
3662 }
3663
3664 /* Verify a gimple assignment statement STMT with a single rhs.
3665    Returns true if anything is wrong.  */
3666
3667 static bool
3668 verify_gimple_assign_single (gimple stmt)
3669 {
3670   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3671   tree lhs = gimple_assign_lhs (stmt);
3672   tree lhs_type = TREE_TYPE (lhs);
3673   tree rhs1 = gimple_assign_rhs1 (stmt);
3674   tree rhs1_type = TREE_TYPE (rhs1);
3675   bool res = false;
3676
3677   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3678     {
3679       error ("non-trivial conversion at assignment");
3680       debug_generic_expr (lhs_type);
3681       debug_generic_expr (rhs1_type);
3682       return true;
3683     }
3684
3685   if (handled_component_p (lhs))
3686     res |= verify_types_in_gimple_reference (lhs);
3687
3688   /* Special codes we cannot handle via their class.  */
3689   switch (rhs_code)
3690     {
3691     case ADDR_EXPR:
3692       {
3693         tree op = TREE_OPERAND (rhs1, 0);
3694         if (!is_gimple_addressable (op))
3695           {
3696             error ("invalid operand in unary expression");
3697             return true;
3698           }
3699
3700         if (!one_pointer_to_useless_type_conversion_p (lhs_type,
3701                                                        TREE_TYPE (op)))
3702           {
3703             error ("type mismatch in address expression");
3704             debug_generic_stmt (lhs_type);
3705             debug_generic_stmt (TYPE_POINTER_TO (TREE_TYPE (op)));
3706             return true;
3707           }
3708
3709         return verify_types_in_gimple_reference (op);
3710       }
3711
3712     /* tcc_reference  */
3713     case COMPONENT_REF:
3714     case BIT_FIELD_REF:
3715     case INDIRECT_REF:
3716     case ALIGN_INDIRECT_REF:
3717     case MISALIGNED_INDIRECT_REF:
3718     case ARRAY_REF:
3719     case ARRAY_RANGE_REF:
3720     case VIEW_CONVERT_EXPR:
3721     case REALPART_EXPR:
3722     case IMAGPART_EXPR:
3723     case TARGET_MEM_REF:
3724       if (!is_gimple_reg (lhs)
3725           && is_gimple_reg_type (TREE_TYPE (lhs)))
3726         {
3727           error ("invalid rhs for gimple memory store");
3728           debug_generic_stmt (lhs);
3729           debug_generic_stmt (rhs1);
3730           return true;
3731         }
3732       return res || verify_types_in_gimple_reference (rhs1);
3733
3734     /* tcc_constant  */
3735     case SSA_NAME:
3736     case INTEGER_CST:
3737     case REAL_CST:
3738     case FIXED_CST:
3739     case COMPLEX_CST:
3740     case VECTOR_CST:
3741     case STRING_CST:
3742       return res;
3743
3744     /* tcc_declaration  */
3745     case CONST_DECL:
3746       return res;
3747     case VAR_DECL:
3748     case PARM_DECL:
3749       if (!is_gimple_reg (lhs)
3750           && !is_gimple_reg (rhs1)
3751           && is_gimple_reg_type (TREE_TYPE (lhs)))
3752         {
3753           error ("invalid rhs for gimple memory store");
3754           debug_generic_stmt (lhs);
3755           debug_generic_stmt (rhs1);
3756           return true;
3757         }
3758       return res;
3759
3760     case COND_EXPR:
3761     case CONSTRUCTOR:
3762     case OBJ_TYPE_REF:
3763     case ASSERT_EXPR:
3764     case WITH_SIZE_EXPR:
3765     case EXC_PTR_EXPR:
3766     case FILTER_EXPR:
3767     case POLYNOMIAL_CHREC:
3768     case DOT_PROD_EXPR:
3769     case VEC_COND_EXPR:
3770     case REALIGN_LOAD_EXPR:
3771       /* FIXME.  */
3772       return res;
3773
3774     default:;
3775     }
3776
3777   return res;
3778 }
3779
3780 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
3781    is a problem, otherwise false.  */
3782
3783 static bool
3784 verify_gimple_assign (gimple stmt)
3785 {
3786   switch (gimple_assign_rhs_class (stmt))
3787     {
3788     case GIMPLE_SINGLE_RHS:
3789       return verify_gimple_assign_single (stmt);
3790
3791     case GIMPLE_UNARY_RHS:
3792       return verify_gimple_assign_unary (stmt);
3793
3794     case GIMPLE_BINARY_RHS:
3795       return verify_gimple_assign_binary (stmt);
3796
3797     default:
3798       gcc_unreachable ();
3799     }
3800 }
3801
3802 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
3803    is a problem, otherwise false.  */
3804
3805 static bool
3806 verify_gimple_return (gimple stmt)
3807 {
3808   tree op = gimple_return_retval (stmt);
3809   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
3810
3811   /* We cannot test for present return values as we do not fix up missing
3812      return values from the original source.  */
3813   if (op == NULL)
3814     return false;
3815  
3816   if (!is_gimple_val (op)
3817       && TREE_CODE (op) != RESULT_DECL)
3818     {
3819       error ("invalid operand in return statement");
3820       debug_generic_stmt (op);
3821       return true;
3822     }
3823
3824   if (!useless_type_conversion_p (restype, TREE_TYPE (op))
3825       /* ???  With C++ we can have the situation that the result
3826          decl is a reference type while the return type is an aggregate.  */
3827       && !(TREE_CODE (op) == RESULT_DECL
3828            && TREE_CODE (TREE_TYPE (op)) == REFERENCE_TYPE
3829            && useless_type_conversion_p (restype, TREE_TYPE (TREE_TYPE (op)))))
3830     {
3831       error ("invalid conversion in return statement");
3832       debug_generic_stmt (restype);
3833       debug_generic_stmt (TREE_TYPE (op));
3834       return true;
3835     }
3836
3837   return false;
3838 }
3839
3840
3841 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
3842    is a problem, otherwise false.  */
3843
3844 static bool
3845 verify_gimple_goto (gimple stmt)
3846 {
3847   tree dest = gimple_goto_dest (stmt);
3848
3849   /* ???  We have two canonical forms of direct goto destinations, a
3850      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
3851   if (TREE_CODE (dest) != LABEL_DECL
3852       && (!is_gimple_val (dest)
3853           || !POINTER_TYPE_P (TREE_TYPE (dest))))
3854     {
3855       error ("goto destination is neither a label nor a pointer");
3856       return true;
3857     }
3858
3859   return false;
3860 }
3861
3862 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
3863    is a problem, otherwise false.  */
3864
3865 static bool
3866 verify_gimple_switch (gimple stmt)
3867 {
3868   if (!is_gimple_val (gimple_switch_index (stmt)))
3869     {
3870       error ("invalid operand to switch statement");
3871       debug_generic_stmt (gimple_switch_index (stmt));
3872       return true;
3873     }
3874
3875   return false;
3876 }
3877
3878
3879 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
3880    and false otherwise.  */
3881
3882 static bool
3883 verify_gimple_phi (gimple stmt)
3884 {
3885   tree type = TREE_TYPE (gimple_phi_result (stmt));
3886   unsigned i;
3887
3888   if (!is_gimple_variable (gimple_phi_result (stmt)))
3889     {
3890       error ("Invalid PHI result");
3891       return true;
3892     }
3893
3894   for (i = 0; i < gimple_phi_num_args (stmt); i++)
3895     {
3896       tree arg = gimple_phi_arg_def (stmt, i);
3897       if ((is_gimple_reg (gimple_phi_result (stmt))
3898            && !is_gimple_val (arg))
3899           || (!is_gimple_reg (gimple_phi_result (stmt))
3900               && !is_gimple_addressable (arg)))
3901         {
3902           error ("Invalid PHI argument");
3903           debug_generic_stmt (arg);
3904           return true;
3905         }
3906       if (!useless_type_conversion_p (type, TREE_TYPE (arg)))
3907         {
3908           error ("Incompatible types in PHI argument");
3909           debug_generic_stmt (type);
3910           debug_generic_stmt (TREE_TYPE (arg));
3911           return true;
3912         }
3913     }
3914
3915   return false;
3916 }
3917
3918
3919 /* Verify the GIMPLE statement STMT.  Returns true if there is an
3920    error, otherwise false.  */
3921
3922 static bool
3923 verify_types_in_gimple_stmt (gimple stmt)
3924 {
3925   if (is_gimple_omp (stmt))
3926     {
3927       /* OpenMP directives are validated by the FE and never operated
3928          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
3929          non-gimple expressions when the main index variable has had
3930          its address taken.  This does not affect the loop itself
3931          because the header of an GIMPLE_OMP_FOR is merely used to determine
3932          how to setup the parallel iteration.  */
3933       return false;
3934     }
3935
3936   switch (gimple_code (stmt))
3937     {
3938     case GIMPLE_ASSIGN:
3939       return verify_gimple_assign (stmt);
3940
3941     case GIMPLE_LABEL:
3942       return TREE_CODE (gimple_label_label (stmt)) != LABEL_DECL;
3943
3944     case GIMPLE_CALL:
3945       return verify_gimple_call (stmt);
3946
3947     case GIMPLE_COND:
3948       return verify_gimple_comparison (boolean_type_node,
3949                                        gimple_cond_lhs (stmt),
3950                                        gimple_cond_rhs (stmt));
3951
3952     case GIMPLE_GOTO:
3953       return verify_gimple_goto (stmt);
3954
3955     case GIMPLE_SWITCH:
3956       return verify_gimple_switch (stmt);
3957
3958     case GIMPLE_RETURN:
3959       return verify_gimple_return (stmt);
3960
3961     case GIMPLE_ASM:
3962       return false;
3963
3964     case GIMPLE_CHANGE_DYNAMIC_TYPE:
3965       return (!is_gimple_val (gimple_cdt_location (stmt))
3966               || !POINTER_TYPE_P (TREE_TYPE (gimple_cdt_location (stmt))));
3967
3968     case GIMPLE_PHI:
3969       return verify_gimple_phi (stmt);
3970
3971     /* Tuples that do not have tree operands.  */
3972     case GIMPLE_NOP:
3973     case GIMPLE_RESX:
3974     case GIMPLE_PREDICT:
3975       return false;
3976
3977     default:
3978       gcc_unreachable ();
3979     }
3980 }
3981
3982 /* Verify the GIMPLE statements inside the sequence STMTS.  */
3983
3984 static bool
3985 verify_types_in_gimple_seq_2 (gimple_seq stmts)
3986 {
3987   gimple_stmt_iterator ittr;
3988   bool err = false;
3989
3990   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
3991     {
3992       gimple stmt = gsi_stmt (ittr);
3993
3994       switch (gimple_code (stmt))
3995         {
3996         case GIMPLE_BIND:
3997           err |= verify_types_in_gimple_seq_2 (gimple_bind_body (stmt));
3998           break;
3999
4000         case GIMPLE_TRY:
4001           err |= verify_types_in_gimple_seq_2 (gimple_try_eval (stmt));
4002           err |= verify_types_in_gimple_seq_2 (gimple_try_cleanup (stmt));
4003           break;
4004
4005         case GIMPLE_EH_FILTER:
4006           err |= verify_types_in_gimple_seq_2 (gimple_eh_filter_failure (stmt));
4007           break;
4008
4009         case GIMPLE_CATCH:
4010           err |= verify_types_in_gimple_seq_2 (gimple_catch_handler (stmt));
4011           break;
4012
4013         default:
4014           {
4015             bool err2 = verify_types_in_gimple_stmt (stmt);
4016             if (err2)
4017               debug_gimple_stmt (stmt);
4018             err |= err2;
4019           }
4020         }
4021     }
4022
4023   return err;
4024 }
4025
4026
4027 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4028
4029 void
4030 verify_types_in_gimple_seq (gimple_seq stmts)
4031 {
4032   if (verify_types_in_gimple_seq_2 (stmts))
4033     internal_error ("verify_gimple failed");
4034 }
4035
4036
4037 /* Verify STMT, return true if STMT is not in GIMPLE form.
4038    TODO: Implement type checking.  */
4039
4040 static bool
4041 verify_stmt (gimple_stmt_iterator *gsi)
4042 {
4043   tree addr;
4044   struct walk_stmt_info wi;
4045   bool last_in_block = gsi_one_before_end_p (*gsi);
4046   gimple stmt = gsi_stmt (*gsi);
4047
4048   if (is_gimple_omp (stmt))
4049     {
4050       /* OpenMP directives are validated by the FE and never operated
4051          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4052          non-gimple expressions when the main index variable has had
4053          its address taken.  This does not affect the loop itself
4054          because the header of an GIMPLE_OMP_FOR is merely used to determine
4055          how to setup the parallel iteration.  */
4056       return false;
4057     }
4058
4059   /* FIXME.  The C frontend passes unpromoted arguments in case it
4060      didn't see a function declaration before the call.  */
4061   if (is_gimple_call (stmt))
4062     {
4063       tree decl;
4064
4065       if (!is_gimple_call_addr (gimple_call_fn (stmt)))
4066         {
4067           error ("invalid function in call statement");
4068           return true;
4069         }
4070
4071       decl = gimple_call_fndecl (stmt);
4072       if (decl
4073           && TREE_CODE (decl) == FUNCTION_DECL
4074           && DECL_LOOPING_CONST_OR_PURE_P (decl)
4075           && (!DECL_PURE_P (decl))
4076           && (!TREE_READONLY (decl)))
4077         {
4078           error ("invalid pure const state for function");
4079           return true;
4080         }
4081     }
4082
4083   memset (&wi, 0, sizeof (wi));
4084   addr = walk_gimple_op (gsi_stmt (*gsi), verify_expr, &wi);
4085   if (addr)
4086     {
4087       debug_generic_expr (addr);
4088       inform (input_location, "in statement");
4089       debug_gimple_stmt (stmt);
4090       return true;
4091     }
4092
4093   /* If the statement is marked as part of an EH region, then it is
4094      expected that the statement could throw.  Verify that when we
4095      have optimizations that simplify statements such that we prove
4096      that they cannot throw, that we update other data structures
4097      to match.  */
4098   if (lookup_stmt_eh_region (stmt) >= 0)
4099     {
4100       if (!stmt_could_throw_p (stmt))
4101         {
4102           error ("statement marked for throw, but doesn%'t");
4103           goto fail;
4104         }
4105       if (!last_in_block && stmt_can_throw_internal (stmt))
4106         {
4107           error ("statement marked for throw in middle of block");
4108           goto fail;
4109         }
4110     }
4111
4112   return false;
4113
4114  fail:
4115   debug_gimple_stmt (stmt);
4116   return true;
4117 }
4118
4119
4120 /* Return true when the T can be shared.  */
4121
4122 static bool
4123 tree_node_can_be_shared (tree t)
4124 {
4125   if (IS_TYPE_OR_DECL_P (t)
4126       || is_gimple_min_invariant (t)
4127       || TREE_CODE (t) == SSA_NAME
4128       || t == error_mark_node
4129       || TREE_CODE (t) == IDENTIFIER_NODE)
4130     return true;
4131
4132   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4133     return true;
4134
4135   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4136            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4137          || TREE_CODE (t) == COMPONENT_REF
4138          || TREE_CODE (t) == REALPART_EXPR
4139          || TREE_CODE (t) == IMAGPART_EXPR)
4140     t = TREE_OPERAND (t, 0);
4141
4142   if (DECL_P (t))
4143     return true;
4144
4145   return false;
4146 }
4147
4148
4149 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4150
4151 static tree
4152 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4153 {
4154   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4155   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4156
4157   if (tree_node_can_be_shared (*tp))
4158     {
4159       *walk_subtrees = false;
4160       return NULL;
4161     }
4162
4163   if (pointer_set_insert (visited, *tp))
4164     return *tp;
4165
4166   return NULL;
4167 }
4168
4169
4170 static bool eh_error_found;
4171 static int
4172 verify_eh_throw_stmt_node (void **slot, void *data)
4173 {
4174   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4175   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4176
4177   if (!pointer_set_contains (visited, node->stmt))
4178     {
4179       error ("Dead STMT in EH table");
4180       debug_gimple_stmt (node->stmt);
4181       eh_error_found = true;
4182     }
4183   return 1;
4184 }
4185
4186
4187 /* Verify the GIMPLE statements in every basic block.  */
4188
4189 void
4190 verify_stmts (void)
4191 {
4192   basic_block bb;
4193   gimple_stmt_iterator gsi;
4194   bool err = false;
4195   struct pointer_set_t *visited, *visited_stmts;
4196   tree addr;
4197   struct walk_stmt_info wi;
4198
4199   timevar_push (TV_TREE_STMT_VERIFY);
4200   visited = pointer_set_create ();
4201   visited_stmts = pointer_set_create ();
4202
4203   memset (&wi, 0, sizeof (wi));
4204   wi.info = (void *) visited;
4205
4206   FOR_EACH_BB (bb)
4207     {
4208       gimple phi;
4209       size_t i;
4210
4211       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4212         {
4213           phi = gsi_stmt (gsi);
4214           pointer_set_insert (visited_stmts, phi);
4215           if (gimple_bb (phi) != bb)
4216             {
4217               error ("gimple_bb (phi) is set to a wrong basic block");
4218               err |= true;
4219             }
4220
4221           for (i = 0; i < gimple_phi_num_args (phi); i++)
4222             {
4223               tree t = gimple_phi_arg_def (phi, i);
4224               tree addr;
4225
4226               if (!t)
4227                 {
4228                   error ("missing PHI def");
4229                   debug_gimple_stmt (phi);
4230                   err |= true;
4231                   continue;
4232                 }
4233               /* Addressable variables do have SSA_NAMEs but they
4234                  are not considered gimple values.  */
4235               else if (TREE_CODE (t) != SSA_NAME
4236                        && TREE_CODE (t) != FUNCTION_DECL
4237                        && !is_gimple_min_invariant (t))
4238                 {
4239                   error ("PHI argument is not a GIMPLE value");
4240                   debug_gimple_stmt (phi);
4241                   debug_generic_expr (t);
4242                   err |= true;
4243                 }
4244
4245               addr = walk_tree (&t, verify_node_sharing, visited, NULL);
4246               if (addr)
4247                 {
4248                   error ("incorrect sharing of tree nodes");
4249                   debug_gimple_stmt (phi);
4250                   debug_generic_expr (addr);
4251                   err |= true;
4252                 }
4253             }
4254         }
4255
4256       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
4257         {
4258           gimple stmt = gsi_stmt (gsi);
4259
4260           if (gimple_code (stmt) == GIMPLE_WITH_CLEANUP_EXPR
4261               || gimple_code (stmt) == GIMPLE_BIND)
4262             {
4263               error ("invalid GIMPLE statement");
4264               debug_gimple_stmt (stmt);
4265               err |= true;
4266             }
4267
4268           pointer_set_insert (visited_stmts, stmt);
4269
4270           if (gimple_bb (stmt) != bb)
4271             {
4272               error ("gimple_bb (stmt) is set to a wrong basic block");
4273               err |= true;
4274             }
4275
4276           if (gimple_code (stmt) == GIMPLE_LABEL)
4277             {
4278               tree decl = gimple_label_label (stmt);
4279               int uid = LABEL_DECL_UID (decl);
4280
4281               if (uid == -1
4282                   || VEC_index (basic_block, label_to_block_map, uid) != bb)
4283                 {
4284                   error ("incorrect entry in label_to_block_map.\n");
4285                   err |= true;
4286                 }
4287             }
4288
4289           err |= verify_stmt (&gsi);
4290           addr = walk_gimple_op (gsi_stmt (gsi), verify_node_sharing, &wi);
4291           if (addr)
4292             {
4293               error ("incorrect sharing of tree nodes");
4294               debug_gimple_stmt (stmt);
4295               debug_generic_expr (addr);
4296               err |= true;
4297             }
4298           gsi_next (&gsi);
4299         }
4300     }
4301
4302   eh_error_found = false;
4303   if (get_eh_throw_stmt_table (cfun))
4304     htab_traverse (get_eh_throw_stmt_table (cfun),
4305                    verify_eh_throw_stmt_node,
4306                    visited_stmts);
4307
4308   if (err | eh_error_found)
4309     internal_error ("verify_stmts failed");
4310
4311   pointer_set_destroy (visited);
4312   pointer_set_destroy (visited_stmts);
4313   verify_histograms ();
4314   timevar_pop (TV_TREE_STMT_VERIFY);
4315 }
4316
4317
4318 /* Verifies that the flow information is OK.  */
4319
4320 static int
4321 gimple_verify_flow_info (void)
4322 {
4323   int err = 0;
4324   basic_block bb;
4325   gimple_stmt_iterator gsi;
4326   gimple stmt;
4327   edge e;
4328   edge_iterator ei;
4329
4330   if (ENTRY_BLOCK_PTR->il.gimple)
4331     {
4332       error ("ENTRY_BLOCK has IL associated with it");
4333       err = 1;
4334     }
4335
4336   if (EXIT_BLOCK_PTR->il.gimple)
4337     {
4338       error ("EXIT_BLOCK has IL associated with it");
4339       err = 1;
4340     }
4341
4342   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4343     if (e->flags & EDGE_FALLTHRU)
4344       {
4345         error ("fallthru to exit from bb %d", e->src->index);
4346         err = 1;
4347       }
4348
4349   FOR_EACH_BB (bb)
4350     {
4351       bool found_ctrl_stmt = false;
4352
4353       stmt = NULL;
4354
4355       /* Skip labels on the start of basic block.  */
4356       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4357         {
4358           tree label;
4359           gimple prev_stmt = stmt;
4360
4361           stmt = gsi_stmt (gsi);
4362
4363           if (gimple_code (stmt) != GIMPLE_LABEL)
4364             break;
4365
4366           label = gimple_label_label (stmt);
4367           if (prev_stmt && DECL_NONLOCAL (label))
4368             {
4369               error ("nonlocal label ");
4370               print_generic_expr (stderr, label, 0);
4371               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4372                        bb->index);
4373               err = 1;
4374             }
4375
4376           if (label_to_block (label) != bb)
4377             {
4378               error ("label ");
4379               print_generic_expr (stderr, label, 0);
4380               fprintf (stderr, " to block does not match in bb %d",
4381                        bb->index);
4382               err = 1;
4383             }
4384
4385           if (decl_function_context (label) != current_function_decl)
4386             {
4387               error ("label ");
4388               print_generic_expr (stderr, label, 0);
4389               fprintf (stderr, " has incorrect context in bb %d",
4390                        bb->index);
4391               err = 1;
4392             }
4393         }
4394
4395       /* Verify that body of basic block BB is free of control flow.  */
4396       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4397         {
4398           gimple stmt = gsi_stmt (gsi);
4399
4400           if (found_ctrl_stmt)
4401             {
4402               error ("control flow in the middle of basic block %d",
4403                      bb->index);
4404               err = 1;
4405             }
4406
4407           if (stmt_ends_bb_p (stmt))
4408             found_ctrl_stmt = true;
4409
4410           if (gimple_code (stmt) == GIMPLE_LABEL)
4411             {
4412               error ("label ");
4413               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4414               fprintf (stderr, " in the middle of basic block %d", bb->index);
4415               err = 1;
4416             }
4417         }
4418
4419       gsi = gsi_last_bb (bb);
4420       if (gsi_end_p (gsi))
4421         continue;
4422
4423       stmt = gsi_stmt (gsi);
4424
4425       err |= verify_eh_edges (stmt);
4426
4427       if (is_ctrl_stmt (stmt))
4428         {
4429           FOR_EACH_EDGE (e, ei, bb->succs)
4430             if (e->flags & EDGE_FALLTHRU)
4431               {
4432                 error ("fallthru edge after a control statement in bb %d",
4433                        bb->index);
4434                 err = 1;
4435               }
4436         }
4437
4438       if (gimple_code (stmt) != GIMPLE_COND)
4439         {
4440           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4441              after anything else but if statement.  */
4442           FOR_EACH_EDGE (e, ei, bb->succs)
4443             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4444               {
4445                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4446                        bb->index);
4447                 err = 1;
4448               }
4449         }
4450
4451       switch (gimple_code (stmt))
4452         {
4453         case GIMPLE_COND:
4454           {
4455             edge true_edge;
4456             edge false_edge;
4457   
4458             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4459
4460             if (!true_edge
4461                 || !false_edge
4462                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4463                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4464                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4465                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4466                 || EDGE_COUNT (bb->succs) >= 3)
4467               {
4468                 error ("wrong outgoing edge flags at end of bb %d",
4469                        bb->index);
4470                 err = 1;
4471               }
4472           }
4473           break;
4474
4475         case GIMPLE_GOTO:
4476           if (simple_goto_p (stmt))
4477             {
4478               error ("explicit goto at end of bb %d", bb->index);
4479               err = 1;
4480             }
4481           else
4482             {
4483               /* FIXME.  We should double check that the labels in the
4484                  destination blocks have their address taken.  */
4485               FOR_EACH_EDGE (e, ei, bb->succs)
4486                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4487                                  | EDGE_FALSE_VALUE))
4488                     || !(e->flags & EDGE_ABNORMAL))
4489                   {
4490                     error ("wrong outgoing edge flags at end of bb %d",
4491                            bb->index);
4492                     err = 1;
4493                   }
4494             }
4495           break;
4496
4497         case GIMPLE_RETURN:
4498           if (!single_succ_p (bb)
4499               || (single_succ_edge (bb)->flags
4500                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4501                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4502             {
4503               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4504               err = 1;
4505             }
4506           if (single_succ (bb) != EXIT_BLOCK_PTR)
4507             {
4508               error ("return edge does not point to exit in bb %d",
4509                      bb->index);
4510               err = 1;
4511             }
4512           break;
4513
4514         case GIMPLE_SWITCH:
4515           {
4516             tree prev;
4517             edge e;
4518             size_t i, n;
4519
4520             n = gimple_switch_num_labels (stmt);
4521
4522             /* Mark all the destination basic blocks.  */
4523             for (i = 0; i < n; ++i)
4524               {
4525                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4526                 basic_block label_bb = label_to_block (lab);
4527                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4528                 label_bb->aux = (void *)1;
4529               }
4530
4531             /* Verify that the case labels are sorted.  */
4532             prev = gimple_switch_label (stmt, 0);
4533             for (i = 1; i < n; ++i)
4534               {
4535                 tree c = gimple_switch_label (stmt, i);
4536                 if (!CASE_LOW (c))
4537                   {
4538                     error ("found default case not at the start of "
4539                            "case vector");
4540                     err = 1;
4541                     continue;
4542                   }
4543                 if (CASE_LOW (prev)
4544                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4545                   {
4546                     error ("case labels not sorted: ");
4547                     print_generic_expr (stderr, prev, 0);
4548                     fprintf (stderr," is greater than ");
4549                     print_generic_expr (stderr, c, 0);
4550                     fprintf (stderr," but comes before it.\n");
4551                     err = 1;
4552                   }
4553                 prev = c;
4554               }
4555             /* VRP will remove the default case if it can prove it will
4556                never be executed.  So do not verify there always exists
4557                a default case here.  */
4558
4559             FOR_EACH_EDGE (e, ei, bb->succs)
4560               {
4561                 if (!e->dest->aux)
4562                   {
4563                     error ("extra outgoing edge %d->%d",
4564                            bb->index, e->dest->index);
4565                     err = 1;
4566                   }
4567
4568                 e->dest->aux = (void *)2;
4569                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4570                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4571                   {
4572                     error ("wrong outgoing edge flags at end of bb %d",
4573                            bb->index);
4574                     err = 1;
4575                   }
4576               }
4577
4578             /* Check that we have all of them.  */
4579             for (i = 0; i < n; ++i)
4580               {
4581                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4582                 basic_block label_bb = label_to_block (lab);
4583
4584                 if (label_bb->aux != (void *)2)
4585                   {
4586                     error ("missing edge %i->%i", bb->index, label_bb->index);
4587                     err = 1;
4588                   }
4589               }
4590
4591             FOR_EACH_EDGE (e, ei, bb->succs)
4592               e->dest->aux = (void *)0;
4593           }
4594
4595         default: ;
4596         }
4597     }
4598
4599   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4600     verify_dominators (CDI_DOMINATORS);
4601
4602   return err;
4603 }
4604
4605
4606 /* Updates phi nodes after creating a forwarder block joined
4607    by edge FALLTHRU.  */
4608
4609 static void
4610 gimple_make_forwarder_block (edge fallthru)
4611 {
4612   edge e;
4613   edge_iterator ei;
4614   basic_block dummy, bb;
4615   tree var;
4616   gimple_stmt_iterator gsi;
4617
4618   dummy = fallthru->src;
4619   bb = fallthru->dest;
4620
4621   if (single_pred_p (bb))
4622     return;
4623
4624   /* If we redirected a branch we must create new PHI nodes at the
4625      start of BB.  */
4626   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
4627     {
4628       gimple phi, new_phi;
4629       
4630       phi = gsi_stmt (gsi);
4631       var = gimple_phi_result (phi);
4632       new_phi = create_phi_node (var, bb);
4633       SSA_NAME_DEF_STMT (var) = new_phi;
4634       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4635       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru);
4636     }
4637
4638   /* Add the arguments we have stored on edges.  */
4639   FOR_EACH_EDGE (e, ei, bb->preds)
4640     {
4641       if (e == fallthru)
4642         continue;
4643
4644       flush_pending_stmts (e);
4645     }
4646 }
4647
4648
4649 /* Return a non-special label in the head of basic block BLOCK.
4650    Create one if it doesn't exist.  */
4651
4652 tree
4653 gimple_block_label (basic_block bb)
4654 {
4655   gimple_stmt_iterator i, s = gsi_start_bb (bb);
4656   bool first = true;
4657   tree label;
4658   gimple stmt;
4659
4660   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
4661     {
4662       stmt = gsi_stmt (i);
4663       if (gimple_code (stmt) != GIMPLE_LABEL)
4664         break;
4665       label = gimple_label_label (stmt);
4666       if (!DECL_NONLOCAL (label))
4667         {
4668           if (!first)
4669             gsi_move_before (&i, &s);
4670           return label;
4671         }
4672     }
4673
4674   label = create_artificial_label ();
4675   stmt = gimple_build_label (label);
4676   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
4677   return label;
4678 }
4679
4680
4681 /* Attempt to perform edge redirection by replacing a possibly complex
4682    jump instruction by a goto or by removing the jump completely.
4683    This can apply only if all edges now point to the same block.  The
4684    parameters and return values are equivalent to
4685    redirect_edge_and_branch.  */
4686
4687 static edge
4688 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
4689 {
4690   basic_block src = e->src;
4691   gimple_stmt_iterator i;
4692   gimple stmt;
4693
4694   /* We can replace or remove a complex jump only when we have exactly
4695      two edges.  */
4696   if (EDGE_COUNT (src->succs) != 2
4697       /* Verify that all targets will be TARGET.  Specifically, the
4698          edge that is not E must also go to TARGET.  */
4699       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4700     return NULL;
4701
4702   i = gsi_last_bb (src);
4703   if (gsi_end_p (i))
4704     return NULL;
4705
4706   stmt = gsi_stmt (i);
4707
4708   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
4709     {
4710       gsi_remove (&i, true);
4711       e = ssa_redirect_edge (e, target);
4712       e->flags = EDGE_FALLTHRU;
4713       return e;
4714     }
4715
4716   return NULL;
4717 }
4718
4719
4720 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4721    edge representing the redirected branch.  */
4722
4723 static edge
4724 gimple_redirect_edge_and_branch (edge e, basic_block dest)
4725 {
4726   basic_block bb = e->src;
4727   gimple_stmt_iterator gsi;
4728   edge ret;
4729   gimple stmt;
4730
4731   if (e->flags & EDGE_ABNORMAL)
4732     return NULL;
4733
4734   if (e->src != ENTRY_BLOCK_PTR
4735       && (ret = gimple_try_redirect_by_replacing_jump (e, dest)))
4736     return ret;
4737
4738   if (e->dest == dest)
4739     return NULL;
4740
4741   gsi = gsi_last_bb (bb);
4742   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
4743
4744   switch (stmt ? gimple_code (stmt) : ERROR_MARK)
4745     {
4746     case GIMPLE_COND:
4747       /* For COND_EXPR, we only need to redirect the edge.  */
4748       break;
4749
4750     case GIMPLE_GOTO:
4751       /* No non-abnormal edges should lead from a non-simple goto, and
4752          simple ones should be represented implicitly.  */
4753       gcc_unreachable ();
4754
4755     case GIMPLE_SWITCH:
4756       {
4757         tree label = gimple_block_label (dest);
4758         tree cases = get_cases_for_edge (e, stmt);
4759
4760         /* If we have a list of cases associated with E, then use it
4761            as it's a lot faster than walking the entire case vector.  */
4762         if (cases)
4763           {
4764             edge e2 = find_edge (e->src, dest);
4765             tree last, first;
4766
4767             first = cases;
4768             while (cases)
4769               {
4770                 last = cases;
4771                 CASE_LABEL (cases) = label;
4772                 cases = TREE_CHAIN (cases);
4773               }
4774
4775             /* If there was already an edge in the CFG, then we need
4776                to move all the cases associated with E to E2.  */
4777             if (e2)
4778               {
4779                 tree cases2 = get_cases_for_edge (e2, stmt);
4780
4781                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4782                 TREE_CHAIN (cases2) = first;
4783               }
4784           }
4785         else
4786           {
4787             size_t i, n = gimple_switch_num_labels (stmt);
4788
4789             for (i = 0; i < n; i++)
4790               {
4791                 tree elt = gimple_switch_label (stmt, i);
4792                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4793                   CASE_LABEL (elt) = label;
4794               }
4795           }
4796
4797         break;
4798       }
4799
4800     case GIMPLE_RETURN:
4801       gsi_remove (&gsi, true);
4802       e->flags |= EDGE_FALLTHRU;
4803       break;
4804
4805     case GIMPLE_OMP_RETURN:
4806     case GIMPLE_OMP_CONTINUE:
4807     case GIMPLE_OMP_SECTIONS_SWITCH:
4808     case GIMPLE_OMP_FOR:
4809       /* The edges from OMP constructs can be simply redirected.  */
4810       break;
4811
4812     default:
4813       /* Otherwise it must be a fallthru edge, and we don't need to
4814          do anything besides redirecting it.  */
4815       gcc_assert (e->flags & EDGE_FALLTHRU);
4816       break;
4817     }
4818
4819   /* Update/insert PHI nodes as necessary.  */
4820
4821   /* Now update the edges in the CFG.  */
4822   e = ssa_redirect_edge (e, dest);
4823
4824   return e;
4825 }
4826
4827 /* Returns true if it is possible to remove edge E by redirecting
4828    it to the destination of the other edge from E->src.  */
4829
4830 static bool
4831 gimple_can_remove_branch_p (const_edge e)
4832 {
4833   if (e->flags & EDGE_ABNORMAL)
4834     return false;
4835
4836   return true;
4837 }
4838
4839 /* Simple wrapper, as we can always redirect fallthru edges.  */
4840
4841 static basic_block
4842 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
4843 {
4844   e = gimple_redirect_edge_and_branch (e, dest);
4845   gcc_assert (e);
4846
4847   return NULL;
4848 }
4849
4850
4851 /* Splits basic block BB after statement STMT (but at least after the
4852    labels).  If STMT is NULL, BB is split just after the labels.  */
4853
4854 static basic_block
4855 gimple_split_block (basic_block bb, void *stmt)
4856 {
4857   gimple_stmt_iterator gsi;
4858   gimple_stmt_iterator gsi_tgt;
4859   gimple act;
4860   gimple_seq list;
4861   basic_block new_bb;
4862   edge e;
4863   edge_iterator ei;
4864
4865   new_bb = create_empty_bb (bb);
4866
4867   /* Redirect the outgoing edges.  */
4868   new_bb->succs = bb->succs;
4869   bb->succs = NULL;
4870   FOR_EACH_EDGE (e, ei, new_bb->succs)
4871     e->src = new_bb;
4872
4873   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
4874     stmt = NULL;
4875
4876   /* Move everything from GSI to the new basic block.  */
4877   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4878     {
4879       act = gsi_stmt (gsi);
4880       if (gimple_code (act) == GIMPLE_LABEL)
4881         continue;
4882
4883       if (!stmt)
4884         break;
4885
4886       if (stmt == act)
4887         {
4888           gsi_next (&gsi);
4889           break;
4890         }
4891     }
4892
4893   if (gsi_end_p (gsi))
4894     return new_bb;
4895
4896   /* Split the statement list - avoid re-creating new containers as this
4897      brings ugly quadratic memory consumption in the inliner.  
4898      (We are still quadratic since we need to update stmt BB pointers,
4899      sadly.)  */
4900   list = gsi_split_seq_before (&gsi);
4901   set_bb_seq (new_bb, list);
4902   for (gsi_tgt = gsi_start (list);
4903        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
4904     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
4905
4906   return new_bb;
4907 }
4908
4909
4910 /* Moves basic block BB after block AFTER.  */
4911
4912 static bool
4913 gimple_move_block_after (basic_block bb, basic_block after)
4914 {
4915   if (bb->prev_bb == after)
4916     return true;
4917
4918   unlink_block (bb);
4919   link_block (bb, after);
4920
4921   return true;
4922 }
4923
4924
4925 /* Return true if basic_block can be duplicated.  */
4926
4927 static bool
4928 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
4929 {
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       region = lookup_stmt_eh_region (stmt);
4972       if (region >= 0)
4973         add_stmt_to_eh_region (copy, region);
4974       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4975
4976       /* Create new names for all the definitions created by COPY and
4977          add replacement mappings for each new name.  */
4978       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4979         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4980     }
4981
4982   return new_bb;
4983 }
4984
4985 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
4986
4987 static void
4988 add_phi_args_after_copy_edge (edge e_copy)
4989 {
4990   basic_block bb, bb_copy = e_copy->src, dest;
4991   edge e;
4992   edge_iterator ei;
4993   gimple phi, phi_copy;
4994   tree def;
4995   gimple_stmt_iterator psi, psi_copy;
4996
4997   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
4998     return;
4999
5000   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5001
5002   if (e_copy->dest->flags & BB_DUPLICATED)
5003     dest = get_bb_original (e_copy->dest);
5004   else
5005     dest = e_copy->dest;
5006
5007   e = find_edge (bb, dest);
5008   if (!e)
5009     {
5010       /* During loop unrolling the target of the latch edge is copied.
5011          In this case we are not looking for edge to dest, but to
5012          duplicated block whose original was dest.  */
5013       FOR_EACH_EDGE (e, ei, bb->succs)
5014         {
5015           if ((e->dest->flags & BB_DUPLICATED)
5016               && get_bb_original (e->dest) == dest)
5017             break;
5018         }
5019
5020       gcc_assert (e != NULL);
5021     }
5022
5023   for (psi = gsi_start_phis (e->dest),
5024        psi_copy = gsi_start_phis (e_copy->dest);
5025        !gsi_end_p (psi);
5026        gsi_next (&psi), gsi_next (&psi_copy))
5027     {
5028       phi = gsi_stmt (psi);
5029       phi_copy = gsi_stmt (psi_copy);
5030       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5031       add_phi_arg (phi_copy, def, e_copy);
5032     }
5033 }
5034
5035
5036 /* Basic block BB_COPY was created by code duplication.  Add phi node
5037    arguments for edges going out of BB_COPY.  The blocks that were
5038    duplicated have BB_DUPLICATED set.  */
5039
5040 void
5041 add_phi_args_after_copy_bb (basic_block bb_copy)
5042 {
5043   edge e_copy;
5044   edge_iterator ei;
5045
5046   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5047     {
5048       add_phi_args_after_copy_edge (e_copy);
5049     }
5050 }
5051
5052 /* Blocks in REGION_COPY array of length N_REGION were created by
5053    duplication of basic blocks.  Add phi node arguments for edges
5054    going from these blocks.  If E_COPY is not NULL, also add
5055    phi node arguments for its destination.*/
5056
5057 void
5058 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5059                          edge e_copy)
5060 {
5061   unsigned i;
5062
5063   for (i = 0; i < n_region; i++)
5064     region_copy[i]->flags |= BB_DUPLICATED;
5065
5066   for (i = 0; i < n_region; i++)
5067     add_phi_args_after_copy_bb (region_copy[i]);
5068   if (e_copy)
5069     add_phi_args_after_copy_edge (e_copy);
5070
5071   for (i = 0; i < n_region; i++)
5072     region_copy[i]->flags &= ~BB_DUPLICATED;
5073 }
5074
5075 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5076    important exit edge EXIT.  By important we mean that no SSA name defined
5077    inside region is live over the other exit edges of the region.  All entry
5078    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5079    to the duplicate of the region.  SSA form, dominance and loop information
5080    is updated.  The new basic blocks are stored to REGION_COPY in the same
5081    order as they had in REGION, provided that REGION_COPY is not NULL.
5082    The function returns false if it is unable to copy the region,
5083    true otherwise.  */
5084
5085 bool
5086 gimple_duplicate_sese_region (edge entry, edge exit,
5087                             basic_block *region, unsigned n_region,
5088                             basic_block *region_copy)
5089 {
5090   unsigned i;
5091   bool free_region_copy = false, copying_header = false;
5092   struct loop *loop = entry->dest->loop_father;
5093   edge exit_copy;
5094   VEC (basic_block, heap) *doms;
5095   edge redirected;
5096   int total_freq = 0, entry_freq = 0;
5097   gcov_type total_count = 0, entry_count = 0;
5098
5099   if (!can_copy_bbs_p (region, n_region))
5100     return false;
5101
5102   /* Some sanity checking.  Note that we do not check for all possible
5103      missuses of the functions.  I.e. if you ask to copy something weird,
5104      it will work, but the state of structures probably will not be
5105      correct.  */
5106   for (i = 0; i < n_region; i++)
5107     {
5108       /* We do not handle subloops, i.e. all the blocks must belong to the
5109          same loop.  */
5110       if (region[i]->loop_father != loop)
5111         return false;
5112
5113       if (region[i] != entry->dest
5114           && region[i] == loop->header)
5115         return false;
5116     }
5117
5118   set_loop_copy (loop, loop);
5119
5120   /* In case the function is used for loop header copying (which is the primary
5121      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5122   if (loop->header == entry->dest)
5123     {
5124       copying_header = true;
5125       set_loop_copy (loop, loop_outer (loop));
5126
5127       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5128         return false;
5129
5130       for (i = 0; i < n_region; i++)
5131         if (region[i] != exit->src
5132             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5133           return false;
5134     }
5135
5136   if (!region_copy)
5137     {
5138       region_copy = XNEWVEC (basic_block, n_region);
5139       free_region_copy = true;
5140     }
5141
5142   gcc_assert (!need_ssa_update_p (cfun));
5143
5144   /* Record blocks outside the region that are dominated by something
5145      inside.  */
5146   doms = NULL;
5147   initialize_original_copy_tables ();
5148
5149   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5150
5151   if (entry->dest->count)
5152     {
5153       total_count = entry->dest->count;
5154       entry_count = entry->count;
5155       /* Fix up corner cases, to avoid division by zero or creation of negative
5156          frequencies.  */
5157       if (entry_count > total_count)
5158         entry_count = total_count;
5159     }
5160   else
5161     {
5162       total_freq = entry->dest->frequency;
5163       entry_freq = EDGE_FREQUENCY (entry);
5164       /* Fix up corner cases, to avoid division by zero or creation of negative
5165          frequencies.  */
5166       if (total_freq == 0)
5167         total_freq = 1;
5168       else if (entry_freq > total_freq)
5169         entry_freq = total_freq;
5170     }
5171
5172   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5173             split_edge_bb_loc (entry));
5174   if (total_count)
5175     {
5176       scale_bbs_frequencies_gcov_type (region, n_region,
5177                                        total_count - entry_count,
5178                                        total_count);
5179       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5180                                        total_count);
5181     }
5182   else
5183     {
5184       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5185                                  total_freq);
5186       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5187     }
5188
5189   if (copying_header)
5190     {
5191       loop->header = exit->dest;
5192       loop->latch = exit->src;
5193     }
5194
5195   /* Redirect the entry and add the phi node arguments.  */
5196   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5197   gcc_assert (redirected != NULL);
5198   flush_pending_stmts (entry);
5199
5200   /* Concerning updating of dominators:  We must recount dominators
5201      for entry block and its copy.  Anything that is outside of the
5202      region, but was dominated by something inside needs recounting as
5203      well.  */
5204   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5205   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5206   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5207   VEC_free (basic_block, heap, doms);
5208
5209   /* Add the other PHI node arguments.  */
5210   add_phi_args_after_copy (region_copy, n_region, NULL);
5211
5212   /* Update the SSA web.  */
5213   update_ssa (TODO_update_ssa);
5214
5215   if (free_region_copy)
5216     free (region_copy);
5217
5218   free_original_copy_tables ();
5219   return true;
5220 }
5221
5222 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5223    are stored to REGION_COPY in the same order in that they appear
5224    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5225    the region, EXIT an exit from it.  The condition guarding EXIT
5226    is moved to ENTRY.  Returns true if duplication succeeds, false
5227    otherwise.
5228
5229    For example, 
5230  
5231    some_code;
5232    if (cond)
5233      A;
5234    else
5235      B;
5236
5237    is transformed to
5238
5239    if (cond)
5240      {
5241        some_code;
5242        A;
5243      }
5244    else
5245      {
5246        some_code;
5247        B;
5248      }
5249 */
5250
5251 bool
5252 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5253                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5254                           basic_block *region_copy ATTRIBUTE_UNUSED)
5255 {
5256   unsigned i;
5257   bool free_region_copy = false;
5258   struct loop *loop = exit->dest->loop_father;
5259   struct loop *orig_loop = entry->dest->loop_father;
5260   basic_block switch_bb, entry_bb, nentry_bb;
5261   VEC (basic_block, heap) *doms;
5262   int total_freq = 0, exit_freq = 0;
5263   gcov_type total_count = 0, exit_count = 0;
5264   edge exits[2], nexits[2], e;
5265   gimple_stmt_iterator gsi;
5266   gimple cond_stmt;
5267   edge sorig, snew;
5268
5269   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5270   exits[0] = exit;
5271   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5272
5273   if (!can_copy_bbs_p (region, n_region))
5274     return false;
5275
5276   /* Some sanity checking.  Note that we do not check for all possible
5277      missuses of the functions.  I.e. if you ask to copy something weird
5278      (e.g., in the example, if there is a jump from inside to the middle
5279      of some_code, or come_code defines some of the values used in cond)
5280      it will work, but the resulting code will not be correct.  */
5281   for (i = 0; i < n_region; i++)
5282     {
5283       /* We do not handle subloops, i.e. all the blocks must belong to the
5284          same loop.  */
5285       if (region[i]->loop_father != orig_loop)
5286         return false;
5287
5288       if (region[i] == orig_loop->latch)
5289         return false;
5290     }
5291
5292   initialize_original_copy_tables ();
5293   set_loop_copy (orig_loop, loop);
5294
5295   if (!region_copy)
5296     {
5297       region_copy = XNEWVEC (basic_block, n_region);
5298       free_region_copy = true;
5299     }
5300
5301   gcc_assert (!need_ssa_update_p (cfun));
5302
5303   /* Record blocks outside the region that are dominated by something
5304      inside.  */
5305   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5306
5307   if (exit->src->count)
5308     {
5309       total_count = exit->src->count;
5310       exit_count = exit->count;
5311       /* Fix up corner cases, to avoid division by zero or creation of negative
5312          frequencies.  */
5313       if (exit_count > total_count)
5314         exit_count = total_count;
5315     }
5316   else
5317     {
5318       total_freq = exit->src->frequency;
5319       exit_freq = EDGE_FREQUENCY (exit);
5320       /* Fix up corner cases, to avoid division by zero or creation of negative
5321          frequencies.  */
5322       if (total_freq == 0)
5323         total_freq = 1;
5324       if (exit_freq > total_freq)
5325         exit_freq = total_freq;
5326     }
5327
5328   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5329             split_edge_bb_loc (exit));
5330   if (total_count)
5331     {
5332       scale_bbs_frequencies_gcov_type (region, n_region,
5333                                        total_count - exit_count,
5334                                        total_count);
5335       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5336                                        total_count);
5337     }
5338   else
5339     {
5340       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5341                                  total_freq);
5342       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5343     }
5344
5345   /* Create the switch block, and put the exit condition to it.  */
5346   entry_bb = entry->dest;
5347   nentry_bb = get_bb_copy (entry_bb);
5348   if (!last_stmt (entry->src)
5349       || !stmt_ends_bb_p (last_stmt (entry->src)))
5350     switch_bb = entry->src;
5351   else
5352     switch_bb = split_edge (entry);
5353   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5354
5355   gsi = gsi_last_bb (switch_bb);
5356   cond_stmt = last_stmt (exit->src);
5357   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5358   cond_stmt = gimple_copy (cond_stmt);
5359   gimple_cond_set_lhs (cond_stmt, unshare_expr (gimple_cond_lhs (cond_stmt)));
5360   gimple_cond_set_rhs (cond_stmt, unshare_expr (gimple_cond_rhs (cond_stmt)));
5361   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5362
5363   sorig = single_succ_edge (switch_bb);
5364   sorig->flags = exits[1]->flags;
5365   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5366
5367   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5368   rescan_loop_exit (snew, true, false);
5369
5370   /* Add the PHI node arguments.  */
5371   add_phi_args_after_copy (region_copy, n_region, snew);
5372
5373   /* Get rid of now superfluous conditions and associated edges (and phi node
5374      arguments).  */
5375   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5376   PENDING_STMT (e) = NULL;
5377   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5378   PENDING_STMT (e) = NULL;
5379
5380   /* Anything that is outside of the region, but was dominated by something
5381      inside needs to update dominance info.  */
5382   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5383   VEC_free (basic_block, heap, doms);
5384
5385   /* Update the SSA web.  */
5386   update_ssa (TODO_update_ssa);
5387
5388   if (free_region_copy)
5389     free (region_copy);
5390
5391   free_original_copy_tables ();
5392   return true;
5393 }
5394
5395 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5396    adding blocks when the dominator traversal reaches EXIT.  This
5397    function silently assumes that ENTRY strictly dominates EXIT.  */
5398
5399 void
5400 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5401                               VEC(basic_block,heap) **bbs_p)
5402 {
5403   basic_block son;
5404
5405   for (son = first_dom_son (CDI_DOMINATORS, entry);
5406        son;
5407        son = next_dom_son (CDI_DOMINATORS, son))
5408     {
5409       VEC_safe_push (basic_block, heap, *bbs_p, son);
5410       if (son != exit)
5411         gather_blocks_in_sese_region (son, exit, bbs_p);
5412     }
5413 }
5414
5415 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5416    The duplicates are recorded in VARS_MAP.  */
5417
5418 static void
5419 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5420                            tree to_context)
5421 {
5422   tree t = *tp, new_t;
5423   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5424   void **loc;
5425
5426   if (DECL_CONTEXT (t) == to_context)
5427     return;
5428
5429   loc = pointer_map_contains (vars_map, t);
5430
5431   if (!loc)
5432     {
5433       loc = pointer_map_insert (vars_map, t);
5434
5435       if (SSA_VAR_P (t))
5436         {
5437           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5438           f->local_decls = tree_cons (NULL_TREE, new_t, f->local_decls);
5439         }
5440       else
5441         {
5442           gcc_assert (TREE_CODE (t) == CONST_DECL);
5443           new_t = copy_node (t);
5444         }
5445       DECL_CONTEXT (new_t) = to_context;
5446
5447       *loc = new_t;
5448     }
5449   else
5450     new_t = (tree) *loc;
5451
5452   *tp = new_t;
5453 }
5454
5455
5456 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5457    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5458
5459 static tree
5460 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5461                   tree to_context)
5462 {
5463   void **loc;
5464   tree new_name, decl = SSA_NAME_VAR (name);
5465
5466   gcc_assert (is_gimple_reg (name));
5467
5468   loc = pointer_map_contains (vars_map, name);
5469
5470   if (!loc)
5471     {
5472       replace_by_duplicate_decl (&decl, vars_map, to_context);
5473
5474       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5475       if (gimple_in_ssa_p (cfun))
5476         add_referenced_var (decl);
5477
5478       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5479       if (SSA_NAME_IS_DEFAULT_DEF (name))
5480         set_default_def (decl, new_name);
5481       pop_cfun ();
5482
5483       loc = pointer_map_insert (vars_map, name);
5484       *loc = new_name;
5485     }
5486   else
5487     new_name = (tree) *loc;
5488
5489   return new_name;
5490 }
5491
5492 struct move_stmt_d
5493 {
5494   tree orig_block;
5495   tree new_block;
5496   tree from_context;
5497   tree to_context;
5498   struct pointer_map_t *vars_map;
5499   htab_t new_label_map;
5500   bool remap_decls_p;
5501 };
5502
5503 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5504    contained in *TP if it has been ORIG_BLOCK previously and change the
5505    DECL_CONTEXT of every local variable referenced in *TP.  */
5506
5507 static tree
5508 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5509 {
5510   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5511   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5512   tree t = *tp;
5513
5514   if (EXPR_P (t))
5515     /* We should never have TREE_BLOCK set on non-statements.  */
5516     gcc_assert (!TREE_BLOCK (t));
5517
5518   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5519     {
5520       if (TREE_CODE (t) == SSA_NAME)
5521         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5522       else if (TREE_CODE (t) == LABEL_DECL)
5523         {
5524           if (p->new_label_map)
5525             {
5526               struct tree_map in, *out;
5527               in.base.from = t;
5528               out = (struct tree_map *)
5529                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5530               if (out)
5531                 *tp = t = out->to;
5532             }
5533
5534           DECL_CONTEXT (t) = p->to_context;
5535         }
5536       else if (p->remap_decls_p)
5537         {
5538           /* Replace T with its duplicate.  T should no longer appear in the
5539              parent function, so this looks wasteful; however, it may appear
5540              in referenced_vars, and more importantly, as virtual operands of
5541              statements, and in alias lists of other variables.  It would be
5542              quite difficult to expunge it from all those places.  ??? It might
5543              suffice to do this for addressable variables.  */
5544           if ((TREE_CODE (t) == VAR_DECL
5545                && !is_global_var (t))
5546               || TREE_CODE (t) == CONST_DECL)
5547             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5548           
5549           if (SSA_VAR_P (t)
5550               && gimple_in_ssa_p (cfun))
5551             {
5552               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5553               add_referenced_var (*tp);
5554               pop_cfun ();
5555             }
5556         }
5557       *walk_subtrees = 0;
5558     }
5559   else if (TYPE_P (t))
5560     *walk_subtrees = 0;
5561
5562   return NULL_TREE;
5563 }
5564
5565 /* Like move_stmt_op, but for gimple statements.
5566
5567    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
5568    contained in the current statement in *GSI_P and change the
5569    DECL_CONTEXT of every local variable referenced in the current
5570    statement.  */
5571
5572 static tree
5573 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
5574              struct walk_stmt_info *wi)
5575 {
5576   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5577   gimple stmt = gsi_stmt (*gsi_p);
5578   tree block = gimple_block (stmt);
5579
5580   if (p->orig_block == NULL_TREE
5581       || block == p->orig_block
5582       || block == NULL_TREE)
5583     gimple_set_block (stmt, p->new_block);
5584 #ifdef ENABLE_CHECKING
5585   else if (block != p->new_block)
5586     {
5587       while (block && block != p->orig_block)
5588         block = BLOCK_SUPERCONTEXT (block);
5589       gcc_assert (block);
5590     }
5591 #endif
5592
5593   if (is_gimple_omp (stmt)
5594       && gimple_code (stmt) != GIMPLE_OMP_RETURN
5595       && gimple_code (stmt) != GIMPLE_OMP_CONTINUE)
5596     {
5597       /* Do not remap variables inside OMP directives.  Variables
5598          referenced in clauses and directive header belong to the
5599          parent function and should not be moved into the child
5600          function.  */
5601       bool save_remap_decls_p = p->remap_decls_p;
5602       p->remap_decls_p = false;
5603       *handled_ops_p = true;
5604
5605       walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r, move_stmt_op, wi);
5606
5607       p->remap_decls_p = save_remap_decls_p;
5608     }
5609
5610   return NULL_TREE;
5611 }
5612
5613 /* Marks virtual operands of all statements in basic blocks BBS for
5614    renaming.  */
5615
5616 void
5617 mark_virtual_ops_in_bb (basic_block bb)
5618 {
5619   gimple_stmt_iterator gsi;
5620
5621   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5622     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
5623
5624   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5625     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
5626 }
5627
5628 /* Move basic block BB from function CFUN to function DEST_FN.  The
5629    block is moved out of the original linked list and placed after
5630    block AFTER in the new list.  Also, the block is removed from the
5631    original array of blocks and placed in DEST_FN's array of blocks.
5632    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5633    updated to reflect the moved edges.
5634
5635    The local variables are remapped to new instances, VARS_MAP is used
5636    to record the mapping.  */
5637
5638 static void
5639 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5640                   basic_block after, bool update_edge_count_p,
5641                   struct move_stmt_d *d, int eh_offset)
5642 {
5643   struct control_flow_graph *cfg;
5644   edge_iterator ei;
5645   edge e;
5646   gimple_stmt_iterator si;
5647   unsigned old_len, new_len;
5648
5649   /* Remove BB from dominance structures.  */
5650   delete_from_dominance_info (CDI_DOMINATORS, bb);
5651   if (current_loops)
5652     remove_bb_from_loops (bb);
5653
5654   /* Link BB to the new linked list.  */
5655   move_block_after (bb, after);
5656
5657   /* Update the edge count in the corresponding flowgraphs.  */
5658   if (update_edge_count_p)
5659     FOR_EACH_EDGE (e, ei, bb->succs)
5660       {
5661         cfun->cfg->x_n_edges--;
5662         dest_cfun->cfg->x_n_edges++;
5663       }
5664
5665   /* Remove BB from the original basic block array.  */
5666   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5667   cfun->cfg->x_n_basic_blocks--;
5668
5669   /* Grow DEST_CFUN's basic block array if needed.  */
5670   cfg = dest_cfun->cfg;
5671   cfg->x_n_basic_blocks++;
5672   if (bb->index >= cfg->x_last_basic_block)
5673     cfg->x_last_basic_block = bb->index + 1;
5674
5675   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5676   if ((unsigned) cfg->x_last_basic_block >= old_len)
5677     {
5678       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5679       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5680                              new_len);
5681     }
5682
5683   VEC_replace (basic_block, cfg->x_basic_block_info,
5684                bb->index, bb);
5685
5686   /* Remap the variables in phi nodes.  */
5687   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
5688     {
5689       gimple phi = gsi_stmt (si);
5690       use_operand_p use;
5691       tree op = PHI_RESULT (phi);
5692       ssa_op_iter oi;
5693
5694       if (!is_gimple_reg (op))
5695         {
5696           /* Remove the phi nodes for virtual operands (alias analysis will be
5697              run for the new function, anyway).  */
5698           remove_phi_node (&si, true);
5699           continue;
5700         }
5701
5702       SET_PHI_RESULT (phi,
5703                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
5704       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5705         {
5706           op = USE_FROM_PTR (use);
5707           if (TREE_CODE (op) == SSA_NAME)
5708             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
5709         }
5710
5711       gsi_next (&si);
5712     }
5713
5714   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5715     {
5716       gimple stmt = gsi_stmt (si);
5717       int region;
5718       struct walk_stmt_info wi;
5719
5720       memset (&wi, 0, sizeof (wi));
5721       wi.info = d;
5722       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
5723
5724       if (gimple_code (stmt) == GIMPLE_LABEL)
5725         {
5726           tree label = gimple_label_label (stmt);
5727           int uid = LABEL_DECL_UID (label);
5728
5729           gcc_assert (uid > -1);
5730
5731           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5732           if (old_len <= (unsigned) uid)
5733             {
5734               new_len = 3 * uid / 2 + 1;
5735               VEC_safe_grow_cleared (basic_block, gc,
5736                                      cfg->x_label_to_block_map, new_len);
5737             }
5738
5739           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5740           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5741
5742           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5743
5744           if (uid >= dest_cfun->cfg->last_label_uid)
5745             dest_cfun->cfg->last_label_uid = uid + 1;
5746         }
5747       else if (gimple_code (stmt) == GIMPLE_RESX && eh_offset != 0)
5748         gimple_resx_set_region (stmt, gimple_resx_region (stmt) + eh_offset);
5749
5750       region = lookup_stmt_eh_region (stmt);
5751       if (region >= 0)
5752         {
5753           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
5754           remove_stmt_from_eh_region (stmt);
5755           gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5756           gimple_remove_stmt_histograms (cfun, stmt);
5757         }
5758
5759       /* We cannot leave any operands allocated from the operand caches of
5760          the current function.  */
5761       free_stmt_operands (stmt);
5762       push_cfun (dest_cfun);
5763       update_stmt (stmt);
5764       pop_cfun ();
5765     }
5766
5767   FOR_EACH_EDGE (e, ei, bb->succs)
5768     if (e->goto_locus)
5769       {
5770         tree block = e->goto_block;
5771         if (d->orig_block == NULL_TREE
5772             || block == d->orig_block)
5773           e->goto_block = d->new_block;
5774 #ifdef ENABLE_CHECKING
5775         else if (block != d->new_block)
5776           {
5777             while (block && block != d->orig_block)
5778               block = BLOCK_SUPERCONTEXT (block);
5779             gcc_assert (block);
5780           }
5781 #endif
5782       }
5783 }
5784
5785 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5786    the outermost EH region.  Use REGION as the incoming base EH region.  */
5787
5788 static int
5789 find_outermost_region_in_block (struct function *src_cfun,
5790                                 basic_block bb, int region)
5791 {
5792   gimple_stmt_iterator si;
5793
5794   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5795     {
5796       gimple stmt = gsi_stmt (si);
5797       int stmt_region;
5798
5799       if (gimple_code (stmt) == GIMPLE_RESX)
5800         stmt_region = gimple_resx_region (stmt);
5801       else
5802         stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
5803       if (stmt_region > 0)
5804         {
5805           if (region < 0)
5806             region = stmt_region;
5807           else if (stmt_region != region)
5808             {
5809               region = eh_region_outermost (src_cfun, stmt_region, region);
5810               gcc_assert (region != -1);
5811             }
5812         }
5813     }
5814
5815   return region;
5816 }
5817
5818 static tree
5819 new_label_mapper (tree decl, void *data)
5820 {
5821   htab_t hash = (htab_t) data;
5822   struct tree_map *m;
5823   void **slot;
5824
5825   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
5826
5827   m = XNEW (struct tree_map);
5828   m->hash = DECL_UID (decl);
5829   m->base.from = decl;
5830   m->to = create_artificial_label ();
5831   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
5832   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
5833     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
5834
5835   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
5836   gcc_assert (*slot == NULL);
5837
5838   *slot = m;
5839
5840   return m->to;
5841 }
5842
5843 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
5844    subblocks.  */
5845
5846 static void
5847 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
5848                                   tree to_context)
5849 {
5850   tree *tp, t;
5851
5852   for (tp = &BLOCK_VARS (block); *tp; tp = &TREE_CHAIN (*tp))
5853     {
5854       t = *tp;
5855       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
5856         continue;
5857       replace_by_duplicate_decl (&t, vars_map, to_context);
5858       if (t != *tp)
5859         {
5860           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
5861             {
5862               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
5863               DECL_HAS_VALUE_EXPR_P (t) = 1;
5864             }
5865           TREE_CHAIN (t) = TREE_CHAIN (*tp);
5866           *tp = t;
5867         }
5868     }
5869
5870   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
5871     replace_block_vars_by_duplicates (block, vars_map, to_context);
5872 }
5873
5874 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5875    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
5876    single basic block in the original CFG and the new basic block is
5877    returned.  DEST_CFUN must not have a CFG yet.
5878
5879    Note that the region need not be a pure SESE region.  Blocks inside
5880    the region may contain calls to abort/exit.  The only restriction
5881    is that ENTRY_BB should be the only entry point and it must
5882    dominate EXIT_BB.
5883
5884    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
5885    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
5886    to the new function.
5887
5888    All local variables referenced in the region are assumed to be in
5889    the corresponding BLOCK_VARS and unexpanded variable lists
5890    associated with DEST_CFUN.  */
5891
5892 basic_block
5893 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
5894                         basic_block exit_bb, tree orig_block)
5895 {
5896   VEC(basic_block,heap) *bbs, *dom_bbs;
5897   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
5898   basic_block after, bb, *entry_pred, *exit_succ, abb;
5899   struct function *saved_cfun = cfun;
5900   int *entry_flag, *exit_flag, eh_offset;
5901   unsigned *entry_prob, *exit_prob;
5902   unsigned i, num_entry_edges, num_exit_edges;
5903   edge e;
5904   edge_iterator ei;
5905   htab_t new_label_map;
5906   struct pointer_map_t *vars_map;
5907   struct loop *loop = entry_bb->loop_father;
5908   struct move_stmt_d d;
5909
5910   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5911      region.  */
5912   gcc_assert (entry_bb != exit_bb
5913               && (!exit_bb
5914                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
5915
5916   /* Collect all the blocks in the region.  Manually add ENTRY_BB
5917      because it won't be added by dfs_enumerate_from.  */
5918   bbs = NULL;
5919   VEC_safe_push (basic_block, heap, bbs, entry_bb);
5920   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5921
5922   /* The blocks that used to be dominated by something in BBS will now be
5923      dominated by the new block.  */
5924   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
5925                                      VEC_address (basic_block, bbs),
5926                                      VEC_length (basic_block, bbs));
5927
5928   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
5929      the predecessor edges to ENTRY_BB and the successor edges to
5930      EXIT_BB so that we can re-attach them to the new basic block that
5931      will replace the region.  */
5932   num_entry_edges = EDGE_COUNT (entry_bb->preds);
5933   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
5934   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
5935   entry_prob = XNEWVEC (unsigned, num_entry_edges);
5936   i = 0;
5937   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
5938     {
5939       entry_prob[i] = e->probability;
5940       entry_flag[i] = e->flags;
5941       entry_pred[i++] = e->src;
5942       remove_edge (e);
5943     }
5944
5945   if (exit_bb)
5946     {
5947       num_exit_edges = EDGE_COUNT (exit_bb->succs);
5948       exit_succ = (basic_block *) xcalloc (num_exit_edges,
5949                                            sizeof (basic_block));
5950       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
5951       exit_prob = XNEWVEC (unsigned, num_exit_edges);
5952       i = 0;
5953       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
5954         {
5955           exit_prob[i] = e->probability;
5956           exit_flag[i] = e->flags;
5957           exit_succ[i++] = e->dest;
5958           remove_edge (e);
5959         }
5960     }
5961   else
5962     {
5963       num_exit_edges = 0;
5964       exit_succ = NULL;
5965       exit_flag = NULL;
5966       exit_prob = NULL;
5967     }
5968
5969   /* Switch context to the child function to initialize DEST_FN's CFG.  */
5970   gcc_assert (dest_cfun->cfg == NULL);
5971   push_cfun (dest_cfun);
5972
5973   init_empty_tree_cfg ();
5974
5975   /* Initialize EH information for the new function.  */
5976   eh_offset = 0;
5977   new_label_map = NULL;
5978   if (saved_cfun->eh)
5979     {
5980       int region = -1;
5981
5982       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5983         region = find_outermost_region_in_block (saved_cfun, bb, region);
5984
5985       init_eh_for_function ();
5986       if (region != -1)
5987         {
5988           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
5989           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
5990                                             new_label_map, region, 0);
5991         }
5992     }
5993
5994   pop_cfun ();
5995
5996   /* Move blocks from BBS into DEST_CFUN.  */
5997   gcc_assert (VEC_length (basic_block, bbs) >= 2);
5998   after = dest_cfun->cfg->x_entry_block_ptr;
5999   vars_map = pointer_map_create ();
6000
6001   memset (&d, 0, sizeof (d));
6002   d.vars_map = vars_map;
6003   d.from_context = cfun->decl;
6004   d.to_context = dest_cfun->decl;
6005   d.new_label_map = new_label_map;
6006   d.remap_decls_p = true;
6007   d.orig_block = orig_block;
6008   d.new_block = DECL_INITIAL (dest_cfun->decl);
6009
6010   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6011     {
6012       /* No need to update edge counts on the last block.  It has
6013          already been updated earlier when we detached the region from
6014          the original CFG.  */
6015       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d, eh_offset);
6016       after = bb;
6017     }
6018
6019   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6020   if (orig_block)
6021     {
6022       tree block;
6023       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6024                   == NULL_TREE);
6025       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6026         = BLOCK_SUBBLOCKS (orig_block);
6027       for (block = BLOCK_SUBBLOCKS (orig_block);
6028            block; block = BLOCK_CHAIN (block))
6029         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6030       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6031     }
6032
6033   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6034                                     vars_map, dest_cfun->decl);
6035
6036   if (new_label_map)
6037     htab_delete (new_label_map);
6038   pointer_map_destroy (vars_map);
6039
6040   /* Rewire the entry and exit blocks.  The successor to the entry
6041      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6042      the child function.  Similarly, the predecessor of DEST_FN's
6043      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6044      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6045      various CFG manipulation function get to the right CFG.
6046
6047      FIXME, this is silly.  The CFG ought to become a parameter to
6048      these helpers.  */
6049   push_cfun (dest_cfun);
6050   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6051   if (exit_bb)
6052     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6053   pop_cfun ();
6054
6055   /* Back in the original function, the SESE region has disappeared,
6056      create a new basic block in its place.  */
6057   bb = create_empty_bb (entry_pred[0]);
6058   if (current_loops)
6059     add_bb_to_loop (bb, loop);
6060   for (i = 0; i < num_entry_edges; i++)
6061     {
6062       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6063       e->probability = entry_prob[i];
6064     }
6065
6066   for (i = 0; i < num_exit_edges; i++)
6067     {
6068       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6069       e->probability = exit_prob[i];
6070     }
6071
6072   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6073   for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
6074     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6075   VEC_free (basic_block, heap, dom_bbs);
6076
6077   if (exit_bb)
6078     {
6079       free (exit_prob);
6080       free (exit_flag);
6081       free (exit_succ);
6082     }
6083   free (entry_prob);
6084   free (entry_flag);
6085   free (entry_pred);
6086   VEC_free (basic_block, heap, bbs);
6087
6088   return bb;
6089 }
6090
6091
6092 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6093    */
6094
6095 void
6096 dump_function_to_file (tree fn, FILE *file, int flags)
6097 {
6098   tree arg, vars, var;
6099   struct function *dsf;
6100   bool ignore_topmost_bind = false, any_var = false;
6101   basic_block bb;
6102   tree chain;
6103
6104   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6105
6106   arg = DECL_ARGUMENTS (fn);
6107   while (arg)
6108     {
6109       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6110       fprintf (file, " ");
6111       print_generic_expr (file, arg, dump_flags);
6112       if (flags & TDF_VERBOSE)
6113         print_node (file, "", arg, 4);
6114       if (TREE_CHAIN (arg))
6115         fprintf (file, ", ");
6116       arg = TREE_CHAIN (arg);
6117     }
6118   fprintf (file, ")\n");
6119
6120   if (flags & TDF_VERBOSE)
6121     print_node (file, "", fn, 2);
6122
6123   dsf = DECL_STRUCT_FUNCTION (fn);
6124   if (dsf && (flags & TDF_DETAILS))
6125     dump_eh_tree (file, dsf);
6126
6127   if (flags & TDF_RAW && !gimple_has_body_p (fn))
6128     {
6129       dump_node (fn, TDF_SLIM | flags, file);
6130       return;
6131     }
6132
6133   /* Switch CFUN to point to FN.  */
6134   push_cfun (DECL_STRUCT_FUNCTION (fn));
6135
6136   /* When GIMPLE is lowered, the variables are no longer available in
6137      BIND_EXPRs, so display them separately.  */
6138   if (cfun && cfun->decl == fn && cfun->local_decls)
6139     {
6140       ignore_topmost_bind = true;
6141
6142       fprintf (file, "{\n");
6143       for (vars = cfun->local_decls; vars; vars = TREE_CHAIN (vars))
6144         {
6145           var = TREE_VALUE (vars);
6146
6147           print_generic_decl (file, var, flags);
6148           if (flags & TDF_VERBOSE)
6149             print_node (file, "", var, 4);
6150           fprintf (file, "\n");
6151
6152           any_var = true;
6153         }
6154     }
6155
6156   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6157     {
6158       /* If the CFG has been built, emit a CFG-based dump.  */
6159       check_bb_profile (ENTRY_BLOCK_PTR, file);
6160       if (!ignore_topmost_bind)
6161         fprintf (file, "{\n");
6162
6163       if (any_var && n_basic_blocks)
6164         fprintf (file, "\n");
6165
6166       FOR_EACH_BB (bb)
6167         gimple_dump_bb (bb, file, 2, flags);
6168
6169       fprintf (file, "}\n");
6170       check_bb_profile (EXIT_BLOCK_PTR, file);
6171     }
6172   else if (DECL_SAVED_TREE (fn) == NULL)
6173     {
6174       /* The function is now in GIMPLE form but the CFG has not been
6175          built yet.  Emit the single sequence of GIMPLE statements
6176          that make up its body.  */
6177       gimple_seq body = gimple_body (fn);
6178
6179       if (gimple_seq_first_stmt (body)
6180           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6181           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6182         print_gimple_seq (file, body, 0, flags);
6183       else
6184         {
6185           if (!ignore_topmost_bind)
6186             fprintf (file, "{\n");
6187
6188           if (any_var)
6189             fprintf (file, "\n");
6190
6191           print_gimple_seq (file, body, 2, flags);
6192           fprintf (file, "}\n");
6193         }
6194     }
6195   else
6196     {
6197       int indent;
6198
6199       /* Make a tree based dump.  */
6200       chain = DECL_SAVED_TREE (fn);
6201
6202       if (chain && TREE_CODE (chain) == BIND_EXPR)
6203         {
6204           if (ignore_topmost_bind)
6205             {
6206               chain = BIND_EXPR_BODY (chain);
6207               indent = 2;
6208             }
6209           else
6210             indent = 0;
6211         }
6212       else
6213         {
6214           if (!ignore_topmost_bind)
6215             fprintf (file, "{\n");
6216           indent = 2;
6217         }
6218
6219       if (any_var)
6220         fprintf (file, "\n");
6221
6222       print_generic_stmt_indented (file, chain, flags, indent);
6223       if (ignore_topmost_bind)
6224         fprintf (file, "}\n");
6225     }
6226
6227   fprintf (file, "\n\n");
6228
6229   /* Restore CFUN.  */
6230   pop_cfun ();
6231 }
6232
6233
6234 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6235
6236 void
6237 debug_function (tree fn, int flags)
6238 {
6239   dump_function_to_file (fn, stderr, flags);
6240 }
6241
6242
6243 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6244
6245 static void
6246 print_pred_bbs (FILE *file, basic_block bb)
6247 {
6248   edge e;
6249   edge_iterator ei;
6250
6251   FOR_EACH_EDGE (e, ei, bb->preds)
6252     fprintf (file, "bb_%d ", e->src->index);
6253 }
6254
6255
6256 /* Print on FILE the indexes for the successors of basic_block BB.  */
6257
6258 static void
6259 print_succ_bbs (FILE *file, basic_block bb)
6260 {
6261   edge e;
6262   edge_iterator ei;
6263
6264   FOR_EACH_EDGE (e, ei, bb->succs)
6265     fprintf (file, "bb_%d ", e->dest->index);
6266 }
6267
6268 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6269
6270 void 
6271 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6272 {
6273   char *s_indent = (char *) alloca ((size_t) indent + 1);
6274   memset ((void *) s_indent, ' ', (size_t) indent);
6275   s_indent[indent] = '\0';
6276
6277   /* Print basic_block's header.  */
6278   if (verbosity >= 2)
6279     {
6280       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6281       print_pred_bbs (file, bb);
6282       fprintf (file, "}, succs = {");
6283       print_succ_bbs (file, bb);
6284       fprintf (file, "})\n");
6285     }
6286
6287   /* Print basic_block's body.  */
6288   if (verbosity >= 3)
6289     {
6290       fprintf (file, "%s  {\n", s_indent);
6291       gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6292       fprintf (file, "%s  }\n", s_indent);
6293     }
6294 }
6295
6296 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6297
6298 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6299    VERBOSITY level this outputs the contents of the loop, or just its
6300    structure.  */
6301
6302 static void
6303 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6304 {
6305   char *s_indent;
6306   basic_block bb;
6307
6308   if (loop == NULL)
6309     return;
6310
6311   s_indent = (char *) alloca ((size_t) indent + 1);
6312   memset ((void *) s_indent, ' ', (size_t) indent);
6313   s_indent[indent] = '\0';
6314
6315   /* Print loop's header.  */
6316   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent, 
6317            loop->num, loop->header->index, loop->latch->index);
6318   fprintf (file, ", niter = ");
6319   print_generic_expr (file, loop->nb_iterations, 0);
6320
6321   if (loop->any_upper_bound)
6322     {
6323       fprintf (file, ", upper_bound = ");
6324       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6325     }
6326
6327   if (loop->any_estimate)
6328     {
6329       fprintf (file, ", estimate = ");
6330       dump_double_int (file, loop->nb_iterations_estimate, true);
6331     }
6332   fprintf (file, ")\n");
6333
6334   /* Print loop's body.  */
6335   if (verbosity >= 1)
6336     {
6337       fprintf (file, "%s{\n", s_indent);
6338       FOR_EACH_BB (bb)
6339         if (bb->loop_father == loop)
6340           print_loops_bb (file, bb, indent, verbosity);
6341
6342       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6343       fprintf (file, "%s}\n", s_indent);
6344     }
6345 }
6346
6347 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6348    spaces.  Following VERBOSITY level this outputs the contents of the
6349    loop, or just its structure.  */
6350
6351 static void
6352 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6353 {
6354   if (loop == NULL)
6355     return;
6356
6357   print_loop (file, loop, indent, verbosity);
6358   print_loop_and_siblings (file, loop->next, indent, verbosity);
6359 }
6360
6361 /* Follow a CFG edge from the entry point of the program, and on entry
6362    of a loop, pretty print the loop structure on FILE.  */
6363
6364 void
6365 print_loops (FILE *file, int verbosity)
6366 {
6367   basic_block bb;
6368
6369   bb = ENTRY_BLOCK_PTR;
6370   if (bb && bb->loop_father)
6371     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6372 }
6373
6374
6375 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6376
6377 void
6378 debug_loops (int verbosity)
6379 {
6380   print_loops (stderr, verbosity);
6381 }
6382
6383 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6384
6385 void
6386 debug_loop (struct loop *loop, int verbosity)
6387 {
6388   print_loop (stderr, loop, 0, verbosity);
6389 }
6390
6391 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6392    level.  */
6393
6394 void
6395 debug_loop_num (unsigned num, int verbosity)
6396 {
6397   debug_loop (get_loop (num), verbosity);
6398 }
6399
6400 /* Return true if BB ends with a call, possibly followed by some
6401    instructions that must stay with the call.  Return false,
6402    otherwise.  */
6403
6404 static bool
6405 gimple_block_ends_with_call_p (basic_block bb)
6406 {
6407   gimple_stmt_iterator gsi = gsi_last_bb (bb);
6408   return is_gimple_call (gsi_stmt (gsi));
6409 }
6410
6411
6412 /* Return true if BB ends with a conditional branch.  Return false,
6413    otherwise.  */
6414
6415 static bool
6416 gimple_block_ends_with_condjump_p (const_basic_block bb)
6417 {
6418   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6419   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6420 }
6421
6422
6423 /* Return true if we need to add fake edge to exit at statement T.
6424    Helper function for gimple_flow_call_edges_add.  */
6425
6426 static bool
6427 need_fake_edge_p (gimple t)
6428 {
6429   tree fndecl = NULL_TREE;
6430   int call_flags = 0;
6431
6432   /* NORETURN and LONGJMP calls already have an edge to exit.
6433      CONST and PURE calls do not need one.
6434      We don't currently check for CONST and PURE here, although
6435      it would be a good idea, because those attributes are
6436      figured out from the RTL in mark_constant_function, and
6437      the counter incrementation code from -fprofile-arcs
6438      leads to different results from -fbranch-probabilities.  */
6439   if (is_gimple_call (t))
6440     {
6441       fndecl = gimple_call_fndecl (t);
6442       call_flags = gimple_call_flags (t);
6443     }
6444
6445   if (is_gimple_call (t)
6446       && fndecl
6447       && DECL_BUILT_IN (fndecl)
6448       && (call_flags & ECF_NOTHROW)
6449       && !(call_flags & ECF_RETURNS_TWICE)
6450       /* fork() doesn't really return twice, but the effect of
6451          wrapping it in __gcov_fork() which calls __gcov_flush()
6452          and clears the counters before forking has the same
6453          effect as returning twice.  Force a fake edge.  */
6454       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6455            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6456     return false;
6457
6458   if (is_gimple_call (t)
6459       && !(call_flags & ECF_NORETURN))
6460     return true;
6461
6462   if (gimple_code (t) == GIMPLE_ASM
6463        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
6464     return true;
6465
6466   return false;
6467 }
6468
6469
6470 /* Add fake edges to the function exit for any non constant and non
6471    noreturn calls, volatile inline assembly in the bitmap of blocks
6472    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
6473    the number of blocks that were split.
6474
6475    The goal is to expose cases in which entering a basic block does
6476    not imply that all subsequent instructions must be executed.  */
6477
6478 static int
6479 gimple_flow_call_edges_add (sbitmap blocks)
6480 {
6481   int i;
6482   int blocks_split = 0;
6483   int last_bb = last_basic_block;
6484   bool check_last_block = false;
6485
6486   if (n_basic_blocks == NUM_FIXED_BLOCKS)
6487     return 0;
6488
6489   if (! blocks)
6490     check_last_block = true;
6491   else
6492     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6493
6494   /* In the last basic block, before epilogue generation, there will be
6495      a fallthru edge to EXIT.  Special care is required if the last insn
6496      of the last basic block is a call because make_edge folds duplicate
6497      edges, which would result in the fallthru edge also being marked
6498      fake, which would result in the fallthru edge being removed by
6499      remove_fake_edges, which would result in an invalid CFG.
6500
6501      Moreover, we can't elide the outgoing fake edge, since the block
6502      profiler needs to take this into account in order to solve the minimal
6503      spanning tree in the case that the call doesn't return.
6504
6505      Handle this by adding a dummy instruction in a new last basic block.  */
6506   if (check_last_block)
6507     {
6508       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6509       gimple_stmt_iterator gsi = gsi_last_bb (bb);
6510       gimple t = NULL;
6511
6512       if (!gsi_end_p (gsi))
6513         t = gsi_stmt (gsi);
6514
6515       if (t && need_fake_edge_p (t))
6516         {
6517           edge e;
6518
6519           e = find_edge (bb, EXIT_BLOCK_PTR);
6520           if (e)
6521             {
6522               gsi_insert_on_edge (e, gimple_build_nop ());
6523               gsi_commit_edge_inserts ();
6524             }
6525         }
6526     }
6527
6528   /* Now add fake edges to the function exit for any non constant
6529      calls since there is no way that we can determine if they will
6530      return or not...  */
6531   for (i = 0; i < last_bb; i++)
6532     {
6533       basic_block bb = BASIC_BLOCK (i);
6534       gimple_stmt_iterator gsi;
6535       gimple stmt, last_stmt;
6536
6537       if (!bb)
6538         continue;
6539
6540       if (blocks && !TEST_BIT (blocks, i))
6541         continue;
6542
6543       gsi = gsi_last_bb (bb);
6544       if (!gsi_end_p (gsi))
6545         {
6546           last_stmt = gsi_stmt (gsi);
6547           do
6548             {
6549               stmt = gsi_stmt (gsi);
6550               if (need_fake_edge_p (stmt))
6551                 {
6552                   edge e;
6553
6554                   /* The handling above of the final block before the
6555                      epilogue should be enough to verify that there is
6556                      no edge to the exit block in CFG already.
6557                      Calling make_edge in such case would cause us to
6558                      mark that edge as fake and remove it later.  */
6559 #ifdef ENABLE_CHECKING
6560                   if (stmt == last_stmt)
6561                     {
6562                       e = find_edge (bb, EXIT_BLOCK_PTR);
6563                       gcc_assert (e == NULL);
6564                     }
6565 #endif
6566
6567                   /* Note that the following may create a new basic block
6568                      and renumber the existing basic blocks.  */
6569                   if (stmt != last_stmt)
6570                     {
6571                       e = split_block (bb, stmt);
6572                       if (e)
6573                         blocks_split++;
6574                     }
6575                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6576                 }
6577               gsi_prev (&gsi);
6578             }
6579           while (!gsi_end_p (gsi));
6580         }
6581     }
6582
6583   if (blocks_split)
6584     verify_flow_info ();
6585
6586   return blocks_split;
6587 }
6588
6589 /* Purge dead abnormal call edges from basic block BB.  */
6590
6591 bool
6592 gimple_purge_dead_abnormal_call_edges (basic_block bb)
6593 {
6594   bool changed = gimple_purge_dead_eh_edges (bb);
6595
6596   if (cfun->has_nonlocal_label)
6597     {
6598       gimple stmt = last_stmt (bb);
6599       edge_iterator ei;
6600       edge e;
6601
6602       if (!(stmt && stmt_can_make_abnormal_goto (stmt)))
6603         for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6604           {
6605             if (e->flags & EDGE_ABNORMAL)
6606               {
6607                 remove_edge (e);
6608                 changed = true;
6609               }
6610             else
6611               ei_next (&ei);
6612           }
6613
6614       /* See gimple_purge_dead_eh_edges below.  */
6615       if (changed)
6616         free_dominance_info (CDI_DOMINATORS);
6617     }
6618
6619   return changed;
6620 }
6621
6622 /* Stores all basic blocks dominated by BB to DOM_BBS.  */
6623
6624 static void
6625 get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
6626 {
6627   basic_block son;
6628
6629   VEC_safe_push (basic_block, heap, *dom_bbs, bb);
6630   for (son = first_dom_son (CDI_DOMINATORS, bb);
6631        son;
6632        son = next_dom_son (CDI_DOMINATORS, son))
6633     get_all_dominated_blocks (son, dom_bbs);
6634 }
6635
6636 /* Removes edge E and all the blocks dominated by it, and updates dominance
6637    information.  The IL in E->src needs to be updated separately.
6638    If dominance info is not available, only the edge E is removed.*/
6639
6640 void
6641 remove_edge_and_dominated_blocks (edge e)
6642 {
6643   VEC (basic_block, heap) *bbs_to_remove = NULL;
6644   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6645   bitmap df, df_idom;
6646   edge f;
6647   edge_iterator ei;
6648   bool none_removed = false;
6649   unsigned i;
6650   basic_block bb, dbb;
6651   bitmap_iterator bi;
6652
6653   if (!dom_info_available_p (CDI_DOMINATORS))
6654     {
6655       remove_edge (e);
6656       return;
6657     }
6658
6659   /* No updating is needed for edges to exit.  */
6660   if (e->dest == EXIT_BLOCK_PTR)
6661     {
6662       if (cfgcleanup_altered_bbs)
6663         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6664       remove_edge (e);
6665       return;
6666     }
6667
6668   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
6669      that is not dominated by E->dest, then this set is empty.  Otherwise,
6670      all the basic blocks dominated by E->dest are removed.
6671
6672      Also, to DF_IDOM we store the immediate dominators of the blocks in
6673      the dominance frontier of E (i.e., of the successors of the
6674      removed blocks, if there are any, and of E->dest otherwise).  */
6675   FOR_EACH_EDGE (f, ei, e->dest->preds)
6676     {
6677       if (f == e)
6678         continue;
6679
6680       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6681         {
6682           none_removed = true;
6683           break;
6684         }
6685     }
6686
6687   df = BITMAP_ALLOC (NULL);
6688   df_idom = BITMAP_ALLOC (NULL);
6689
6690   if (none_removed)
6691     bitmap_set_bit (df_idom,
6692                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6693   else
6694     {
6695       get_all_dominated_blocks (e->dest, &bbs_to_remove);
6696       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6697         {
6698           FOR_EACH_EDGE (f, ei, bb->succs)
6699             {
6700               if (f->dest != EXIT_BLOCK_PTR)
6701                 bitmap_set_bit (df, f->dest->index);
6702             }
6703         }
6704       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6705         bitmap_clear_bit (df, bb->index);
6706
6707       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6708         {
6709           bb = BASIC_BLOCK (i);
6710           bitmap_set_bit (df_idom,
6711                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6712         }
6713     }
6714
6715   if (cfgcleanup_altered_bbs)
6716     {
6717       /* Record the set of the altered basic blocks.  */
6718       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6719       bitmap_ior_into (cfgcleanup_altered_bbs, df);
6720     }
6721
6722   /* Remove E and the cancelled blocks.  */
6723   if (none_removed)
6724     remove_edge (e);
6725   else
6726     {
6727       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6728         delete_basic_block (bb);
6729     }
6730
6731   /* Update the dominance information.  The immediate dominator may change only
6732      for blocks whose immediate dominator belongs to DF_IDOM:
6733    
6734      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6735      removal.  Let Z the arbitrary block such that idom(Z) = Y and
6736      Z dominates X after the removal.  Before removal, there exists a path P
6737      from Y to X that avoids Z.  Let F be the last edge on P that is
6738      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
6739      dominates W, and because of P, Z does not dominate W), and W belongs to
6740      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */ 
6741   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6742     {
6743       bb = BASIC_BLOCK (i);
6744       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6745            dbb;
6746            dbb = next_dom_son (CDI_DOMINATORS, dbb))
6747         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6748     }
6749
6750   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6751
6752   BITMAP_FREE (df);
6753   BITMAP_FREE (df_idom);
6754   VEC_free (basic_block, heap, bbs_to_remove);
6755   VEC_free (basic_block, heap, bbs_to_fix_dom);
6756 }
6757
6758 /* Purge dead EH edges from basic block BB.  */
6759
6760 bool
6761 gimple_purge_dead_eh_edges (basic_block bb)
6762 {
6763   bool changed = false;
6764   edge e;
6765   edge_iterator ei;
6766   gimple stmt = last_stmt (bb);
6767
6768   if (stmt && stmt_can_throw_internal (stmt))
6769     return false;
6770
6771   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6772     {
6773       if (e->flags & EDGE_EH)
6774         {
6775           remove_edge_and_dominated_blocks (e);
6776           changed = true;
6777         }
6778       else
6779         ei_next (&ei);
6780     }
6781
6782   return changed;
6783 }
6784
6785 bool
6786 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
6787 {
6788   bool changed = false;
6789   unsigned i;
6790   bitmap_iterator bi;
6791
6792   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6793     {
6794       basic_block bb = BASIC_BLOCK (i);
6795
6796       /* Earlier gimple_purge_dead_eh_edges could have removed
6797          this basic block already.  */
6798       gcc_assert (bb || changed);
6799       if (bb != NULL)
6800         changed |= gimple_purge_dead_eh_edges (bb);
6801     }
6802
6803   return changed;
6804 }
6805
6806 /* This function is called whenever a new edge is created or
6807    redirected.  */
6808
6809 static void
6810 gimple_execute_on_growing_pred (edge e)
6811 {
6812   basic_block bb = e->dest;
6813
6814   if (phi_nodes (bb))
6815     reserve_phi_args_for_new_edge (bb);
6816 }
6817
6818 /* This function is called immediately before edge E is removed from
6819    the edge vector E->dest->preds.  */
6820
6821 static void
6822 gimple_execute_on_shrinking_pred (edge e)
6823 {
6824   if (phi_nodes (e->dest))
6825     remove_phi_args (e);
6826 }
6827
6828 /*---------------------------------------------------------------------------
6829   Helper functions for Loop versioning
6830   ---------------------------------------------------------------------------*/
6831
6832 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
6833    of 'first'. Both of them are dominated by 'new_head' basic block. When
6834    'new_head' was created by 'second's incoming edge it received phi arguments
6835    on the edge by split_edge(). Later, additional edge 'e' was created to
6836    connect 'new_head' and 'first'. Now this routine adds phi args on this
6837    additional edge 'e' that new_head to second edge received as part of edge
6838    splitting.  */
6839
6840 static void
6841 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
6842                                   basic_block new_head, edge e)
6843 {
6844   gimple phi1, phi2;
6845   gimple_stmt_iterator psi1, psi2;
6846   tree def;
6847   edge e2 = find_edge (new_head, second);
6848
6849   /* Because NEW_HEAD has been created by splitting SECOND's incoming
6850      edge, we should always have an edge from NEW_HEAD to SECOND.  */
6851   gcc_assert (e2 != NULL);
6852
6853   /* Browse all 'second' basic block phi nodes and add phi args to
6854      edge 'e' for 'first' head. PHI args are always in correct order.  */
6855
6856   for (psi2 = gsi_start_phis (second),
6857        psi1 = gsi_start_phis (first);
6858        !gsi_end_p (psi2) && !gsi_end_p (psi1);
6859        gsi_next (&psi2),  gsi_next (&psi1))
6860     {
6861       phi1 = gsi_stmt (psi1);
6862       phi2 = gsi_stmt (psi2);
6863       def = PHI_ARG_DEF (phi2, e2->dest_idx);
6864       add_phi_arg (phi1, def, e);
6865     }
6866 }
6867
6868
6869 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6870    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6871    the destination of the ELSE part.  */
6872
6873 static void
6874 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
6875                                basic_block second_head ATTRIBUTE_UNUSED,
6876                                basic_block cond_bb, void *cond_e)
6877 {
6878   gimple_stmt_iterator gsi;
6879   gimple new_cond_expr;
6880   tree cond_expr = (tree) cond_e;
6881   edge e0;
6882
6883   /* Build new conditional expr */
6884   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
6885                                                NULL_TREE, NULL_TREE);
6886
6887   /* Add new cond in cond_bb.  */
6888   gsi = gsi_last_bb (cond_bb);
6889   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
6890
6891   /* Adjust edges appropriately to connect new head with first head
6892      as well as second head.  */
6893   e0 = single_succ_edge (cond_bb);
6894   e0->flags &= ~EDGE_FALLTHRU;
6895   e0->flags |= EDGE_FALSE_VALUE;
6896 }
6897
6898 struct cfg_hooks gimple_cfg_hooks = {
6899   "gimple",
6900   gimple_verify_flow_info,
6901   gimple_dump_bb,               /* dump_bb  */
6902   create_bb,                    /* create_basic_block  */
6903   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
6904   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
6905   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
6906   remove_bb,                    /* delete_basic_block  */
6907   gimple_split_block,           /* split_block  */
6908   gimple_move_block_after,      /* move_block_after  */
6909   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
6910   gimple_merge_blocks,          /* merge_blocks  */
6911   gimple_predict_edge,          /* predict_edge  */
6912   gimple_predicted_by_p,                /* predicted_by_p  */
6913   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
6914   gimple_duplicate_bb,          /* duplicate_block  */
6915   gimple_split_edge,            /* split_edge  */
6916   gimple_make_forwarder_block,  /* make_forward_block  */
6917   NULL,                         /* tidy_fallthru_edge  */
6918   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
6919   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
6920   gimple_flow_call_edges_add,     /* flow_call_edges_add */
6921   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
6922   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
6923   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
6924   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
6925   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
6926   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
6927   flush_pending_stmts           /* flush_pending_stmts */
6928 };
6929
6930
6931 /* Split all critical edges.  */
6932
6933 static unsigned int
6934 split_critical_edges (void)
6935 {
6936   basic_block bb;
6937   edge e;
6938   edge_iterator ei;
6939
6940   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6941      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
6942      mappings around the calls to split_edge.  */
6943   start_recording_case_labels ();
6944   FOR_ALL_BB (bb)
6945     {
6946       FOR_EACH_EDGE (e, ei, bb->succs)
6947         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
6948           {
6949             split_edge (e);
6950           }
6951     }
6952   end_recording_case_labels ();
6953   return 0;
6954 }
6955
6956 struct gimple_opt_pass pass_split_crit_edges =
6957 {
6958  {
6959   GIMPLE_PASS,
6960   "crited",                          /* name */
6961   NULL,                          /* gate */
6962   split_critical_edges,          /* execute */
6963   NULL,                          /* sub */
6964   NULL,                          /* next */
6965   0,                             /* static_pass_number */
6966   TV_TREE_SPLIT_EDGES,           /* tv_id */
6967   PROP_cfg,                      /* properties required */
6968   PROP_no_crit_edges,            /* properties_provided */
6969   0,                             /* properties_destroyed */
6970   0,                             /* todo_flags_start */
6971   TODO_dump_func                 /* todo_flags_finish */
6972  }
6973 };
6974
6975
6976 /* Build a ternary operation and gimplify it.  Emit code before GSI.
6977    Return the gimple_val holding the result.  */
6978
6979 tree
6980 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
6981                  tree type, tree a, tree b, tree c)
6982 {
6983   tree ret;
6984
6985   ret = fold_build3 (code, type, a, b, c);
6986   STRIP_NOPS (ret);
6987
6988   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
6989                                    GSI_SAME_STMT);
6990 }
6991
6992 /* Build a binary operation and gimplify it.  Emit code before GSI.
6993    Return the gimple_val holding the result.  */
6994
6995 tree
6996 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
6997                  tree type, tree a, tree b)
6998 {
6999   tree ret;
7000
7001   ret = fold_build2 (code, type, a, b);
7002   STRIP_NOPS (ret);
7003
7004   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7005                                    GSI_SAME_STMT);
7006 }
7007
7008 /* Build a unary operation and gimplify it.  Emit code before GSI.
7009    Return the gimple_val holding the result.  */
7010
7011 tree
7012 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7013                  tree a)
7014 {
7015   tree ret;
7016
7017   ret = fold_build1 (code, type, a);
7018   STRIP_NOPS (ret);
7019
7020   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7021                                    GSI_SAME_STMT);
7022 }
7023
7024
7025 \f
7026 /* Emit return warnings.  */
7027
7028 static unsigned int
7029 execute_warn_function_return (void)
7030 {
7031   source_location location;
7032   gimple last;
7033   edge e;
7034   edge_iterator ei;
7035
7036   /* If we have a path to EXIT, then we do return.  */
7037   if (TREE_THIS_VOLATILE (cfun->decl)
7038       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7039     {
7040       location = UNKNOWN_LOCATION;
7041       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7042         {
7043           last = last_stmt (e->src);
7044           if (gimple_code (last) == GIMPLE_RETURN
7045               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7046             break;
7047         }
7048       if (location == UNKNOWN_LOCATION)
7049         location = cfun->function_end_locus;
7050       warning (0, "%H%<noreturn%> function does return", &location);
7051     }
7052
7053   /* If we see "return;" in some basic block, then we do reach the end
7054      without returning a value.  */
7055   else if (warn_return_type
7056            && !TREE_NO_WARNING (cfun->decl)
7057            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7058            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7059     {
7060       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7061         {
7062           gimple last = last_stmt (e->src);
7063           if (gimple_code (last) == GIMPLE_RETURN
7064               && gimple_return_retval (last) == NULL
7065               && !gimple_no_warning_p (last))
7066             {
7067               location = gimple_location (last);
7068               if (location == UNKNOWN_LOCATION)
7069                   location = cfun->function_end_locus;
7070               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7071               TREE_NO_WARNING (cfun->decl) = 1;
7072               break;
7073             }
7074         }
7075     }
7076   return 0;
7077 }
7078
7079
7080 /* Given a basic block B which ends with a conditional and has
7081    precisely two successors, determine which of the edges is taken if
7082    the conditional is true and which is taken if the conditional is
7083    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7084
7085 void
7086 extract_true_false_edges_from_block (basic_block b,
7087                                      edge *true_edge,
7088                                      edge *false_edge)
7089 {
7090   edge e = EDGE_SUCC (b, 0);
7091
7092   if (e->flags & EDGE_TRUE_VALUE)
7093     {
7094       *true_edge = e;
7095       *false_edge = EDGE_SUCC (b, 1);
7096     }
7097   else
7098     {
7099       *false_edge = e;
7100       *true_edge = EDGE_SUCC (b, 1);
7101     }
7102 }
7103
7104 struct gimple_opt_pass pass_warn_function_return =
7105 {
7106  {
7107   GIMPLE_PASS,
7108   NULL,                                 /* name */
7109   NULL,                                 /* gate */
7110   execute_warn_function_return,         /* execute */
7111   NULL,                                 /* sub */
7112   NULL,                                 /* next */
7113   0,                                    /* static_pass_number */
7114   0,                                    /* tv_id */
7115   PROP_cfg,                             /* properties_required */
7116   0,                                    /* properties_provided */
7117   0,                                    /* properties_destroyed */
7118   0,                                    /* todo_flags_start */
7119   0                                     /* todo_flags_finish */
7120  }
7121 };
7122
7123 /* Emit noreturn warnings.  */
7124
7125 static unsigned int
7126 execute_warn_function_noreturn (void)
7127 {
7128   if (warn_missing_noreturn
7129       && !TREE_THIS_VOLATILE (cfun->decl)
7130       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
7131       && !lang_hooks.missing_noreturn_ok_p (cfun->decl))
7132     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
7133              "for attribute %<noreturn%>",
7134              cfun->decl);
7135   return 0;
7136 }
7137
7138 struct gimple_opt_pass pass_warn_function_noreturn =
7139 {
7140  {
7141   GIMPLE_PASS,
7142   NULL,                                 /* name */
7143   NULL,                                 /* gate */
7144   execute_warn_function_noreturn,       /* execute */
7145   NULL,                                 /* sub */
7146   NULL,                                 /* next */
7147   0,                                    /* static_pass_number */
7148   0,                                    /* tv_id */
7149   PROP_cfg,                             /* properties_required */
7150   0,                                    /* properties_provided */
7151   0,                                    /* properties_destroyed */
7152   0,                                    /* todo_flags_start */
7153   0                                     /* todo_flags_finish */
7154  }
7155 };