OSDN Git Service

2008-05-16 Kenneth Zadeck <zadeck@naturalbridge.com>
[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
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 SWITCH_EXPRs.
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 basic_block create_bb (void *, void *, basic_block);
87 static void make_blocks (tree);
88 static void factor_computed_gotos (void);
89
90 /* Edges.  */
91 static void make_edges (void);
92 static void make_cond_expr_edges (basic_block);
93 static void make_switch_expr_edges (basic_block);
94 static void make_goto_expr_edges (basic_block);
95 static edge tree_redirect_edge_and_branch (edge, basic_block);
96 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
97 static unsigned int split_critical_edges (void);
98
99 /* Various helpers.  */
100 static inline bool stmt_starts_bb_p (const_tree, const_tree);
101 static int tree_verify_flow_info (void);
102 static void tree_make_forwarder_block (edge);
103 static void tree_cfg2vcg (FILE *);
104 static inline void change_bb_for_stmt (tree t, basic_block bb);
105 static bool computed_goto_p (const_tree);
106
107 /* Flowgraph optimization and cleanup.  */
108 static void tree_merge_blocks (basic_block, basic_block);
109 static bool tree_can_merge_blocks_p (basic_block, basic_block);
110 static void remove_bb (basic_block);
111 static edge find_taken_edge_computed_goto (basic_block, tree);
112 static edge find_taken_edge_cond_expr (basic_block, tree);
113 static edge find_taken_edge_switch_expr (basic_block, tree);
114 static tree find_case_label_for_value (tree, tree);
115
116 void
117 init_empty_tree_cfg (void)
118 {
119   /* Initialize the basic block array.  */
120   init_flow ();
121   profile_status = PROFILE_ABSENT;
122   n_basic_blocks = NUM_FIXED_BLOCKS;
123   last_basic_block = NUM_FIXED_BLOCKS;
124   basic_block_info = VEC_alloc (basic_block, gc, initial_cfg_capacity);
125   VEC_safe_grow_cleared (basic_block, gc, basic_block_info,
126                          initial_cfg_capacity);
127
128   /* Build a mapping of labels to their associated blocks.  */
129   label_to_block_map = VEC_alloc (basic_block, gc, initial_cfg_capacity);
130   VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
131                          initial_cfg_capacity);
132
133   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
134   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
135   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
136   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
137 }
138
139 /*---------------------------------------------------------------------------
140                               Create basic blocks
141 ---------------------------------------------------------------------------*/
142
143 /* Entry point to the CFG builder for trees.  TP points to the list of
144    statements to be added to the flowgraph.  */
145
146 static void
147 build_tree_cfg (tree *tp)
148 {
149   /* Register specific tree functions.  */
150   tree_register_cfg_hooks ();
151
152   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
153
154   init_empty_tree_cfg ();
155
156   found_computed_goto = 0;
157   make_blocks (*tp);
158
159   /* Computed gotos are hell to deal with, especially if there are
160      lots of them with a large number of destinations.  So we factor
161      them to a common computed goto location before we build the
162      edge list.  After we convert back to normal form, we will un-factor
163      the computed gotos since factoring introduces an unwanted jump.  */
164   if (found_computed_goto)
165     factor_computed_gotos ();
166
167   /* Make sure there is always at least one block, even if it's empty.  */
168   if (n_basic_blocks == NUM_FIXED_BLOCKS)
169     create_empty_bb (ENTRY_BLOCK_PTR);
170
171   /* Adjust the size of the array.  */
172   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
173     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
174
175   /* To speed up statement iterator walks, we first purge dead labels.  */
176   cleanup_dead_labels ();
177
178   /* Group case nodes to reduce the number of edges.
179      We do this after cleaning up dead labels because otherwise we miss
180      a lot of obvious case merging opportunities.  */
181   group_case_labels ();
182
183   /* Create the edges of the flowgraph.  */
184   make_edges ();
185   cleanup_dead_labels ();
186
187   /* Debugging dumps.  */
188
189   /* Write the flowgraph to a VCG file.  */
190   {
191     int local_dump_flags;
192     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
193     if (vcg_file)
194       {
195         tree_cfg2vcg (vcg_file);
196         dump_end (TDI_vcg, vcg_file);
197       }
198   }
199
200 #ifdef ENABLE_CHECKING
201   verify_stmts ();
202 #endif
203
204   /* Dump a textual representation of the flowgraph.  */
205   if (dump_file)
206     dump_tree_cfg (dump_file, dump_flags);
207 }
208
209 static unsigned int
210 execute_build_cfg (void)
211 {
212   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
213   return 0;
214 }
215
216 struct gimple_opt_pass pass_build_cfg =
217 {
218  {
219   GIMPLE_PASS,
220   "cfg",                                /* name */
221   NULL,                                 /* gate */
222   execute_build_cfg,                    /* execute */
223   NULL,                                 /* sub */
224   NULL,                                 /* next */
225   0,                                    /* static_pass_number */
226   TV_TREE_CFG,                          /* tv_id */
227   PROP_gimple_leh,                      /* properties_required */
228   PROP_cfg,                             /* properties_provided */
229   0,                                    /* properties_destroyed */
230   0,                                    /* todo_flags_start */
231   TODO_verify_stmts | TODO_cleanup_cfg  /* todo_flags_finish */
232  }
233 };
234
235 /* Search the CFG for any computed gotos.  If found, factor them to a
236    common computed goto site.  Also record the location of that site so
237    that we can un-factor the gotos after we have converted back to
238    normal form.  */
239
240 static void
241 factor_computed_gotos (void)
242 {
243   basic_block bb;
244   tree factored_label_decl = NULL;
245   tree var = NULL;
246   tree factored_computed_goto_label = NULL;
247   tree factored_computed_goto = NULL;
248
249   /* We know there are one or more computed gotos in this function.
250      Examine the last statement in each basic block to see if the block
251      ends with a computed goto.  */
252
253   FOR_EACH_BB (bb)
254     {
255       block_stmt_iterator bsi = bsi_last (bb);
256       tree last;
257
258       if (bsi_end_p (bsi))
259         continue;
260       last = bsi_stmt (bsi);
261
262       /* Ignore the computed goto we create when we factor the original
263          computed gotos.  */
264       if (last == factored_computed_goto)
265         continue;
266
267       /* If the last statement is a computed goto, factor it.  */
268       if (computed_goto_p (last))
269         {
270           tree assignment;
271
272           /* The first time we find a computed goto we need to create
273              the factored goto block and the variable each original
274              computed goto will use for their goto destination.  */
275           if (! factored_computed_goto)
276             {
277               basic_block new_bb = create_empty_bb (bb);
278               block_stmt_iterator new_bsi = bsi_start (new_bb);
279
280               /* Create the destination of the factored goto.  Each original
281                  computed goto will put its desired destination into this
282                  variable and jump to the label we create immediately
283                  below.  */
284               var = create_tmp_var (ptr_type_node, "gotovar");
285
286               /* Build a label for the new block which will contain the
287                  factored computed goto.  */
288               factored_label_decl = create_artificial_label ();
289               factored_computed_goto_label
290                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
291               bsi_insert_after (&new_bsi, factored_computed_goto_label,
292                                 BSI_NEW_STMT);
293
294               /* Build our new computed goto.  */
295               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
296               bsi_insert_after (&new_bsi, factored_computed_goto,
297                                 BSI_NEW_STMT);
298             }
299
300           /* Copy the original computed goto's destination into VAR.  */
301           assignment = build_gimple_modify_stmt (var,
302                                                  GOTO_DESTINATION (last));
303           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
304
305           /* And re-vector the computed goto to the new destination.  */
306           GOTO_DESTINATION (last) = factored_label_decl;
307         }
308     }
309 }
310
311
312 /* Build a flowgraph for the statement_list STMT_LIST.  */
313
314 static void
315 make_blocks (tree stmt_list)
316 {
317   tree_stmt_iterator i = tsi_start (stmt_list);
318   tree stmt = NULL;
319   bool start_new_block = true;
320   bool first_stmt_of_list = true;
321   basic_block bb = ENTRY_BLOCK_PTR;
322
323   while (!tsi_end_p (i))
324     {
325       tree prev_stmt;
326
327       prev_stmt = stmt;
328       stmt = tsi_stmt (i);
329
330       /* If the statement starts a new basic block or if we have determined
331          in a previous pass that we need to create a new block for STMT, do
332          so now.  */
333       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
334         {
335           if (!first_stmt_of_list)
336             stmt_list = tsi_split_statement_list_before (&i);
337           bb = create_basic_block (stmt_list, NULL, bb);
338           start_new_block = false;
339         }
340
341       /* Now add STMT to BB and create the subgraphs for special statement
342          codes.  */
343       set_bb_for_stmt (stmt, bb);
344
345       if (computed_goto_p (stmt))
346         found_computed_goto = true;
347
348       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
349          next iteration.  */
350       if (stmt_ends_bb_p (stmt))
351         start_new_block = true;
352
353       tsi_next (&i);
354       first_stmt_of_list = false;
355     }
356 }
357
358
359 /* Create and return a new empty basic block after bb AFTER.  */
360
361 static basic_block
362 create_bb (void *h, void *e, basic_block after)
363 {
364   basic_block bb;
365
366   gcc_assert (!e);
367
368   /* Create and initialize a new basic block.  Since alloc_block uses
369      ggc_alloc_cleared to allocate a basic block, we do not have to
370      clear the newly allocated basic block here.  */
371   bb = alloc_block ();
372
373   bb->index = last_basic_block;
374   bb->flags = BB_NEW;
375   bb->il.tree = GGC_CNEW (struct tree_bb_info);
376   set_bb_stmt_list (bb, h ? (tree) h : alloc_stmt_list ());
377
378   /* Add the new block to the linked list of blocks.  */
379   link_block (bb, after);
380
381   /* Grow the basic block array if needed.  */
382   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
383     {
384       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
385       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
386     }
387
388   /* Add the newly created block to the array.  */
389   SET_BASIC_BLOCK (last_basic_block, bb);
390
391   n_basic_blocks++;
392   last_basic_block++;
393
394   return bb;
395 }
396
397
398 /*---------------------------------------------------------------------------
399                                  Edge creation
400 ---------------------------------------------------------------------------*/
401
402 /* Fold COND_EXPR_COND of each COND_EXPR.  */
403
404 void
405 fold_cond_expr_cond (void)
406 {
407   basic_block bb;
408
409   FOR_EACH_BB (bb)
410     {
411       tree stmt = last_stmt (bb);
412
413       if (stmt
414           && TREE_CODE (stmt) == COND_EXPR)
415         {
416           tree cond;
417           bool zerop, onep;
418
419           fold_defer_overflow_warnings ();
420           cond = fold (COND_EXPR_COND (stmt));
421           zerop = integer_zerop (cond);
422           onep = integer_onep (cond);
423           fold_undefer_overflow_warnings (zerop || onep,
424                                           stmt,
425                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
426           if (zerop)
427             COND_EXPR_COND (stmt) = boolean_false_node;
428           else if (onep)
429             COND_EXPR_COND (stmt) = boolean_true_node;
430         }
431     }
432 }
433
434 /* Join all the blocks in the flowgraph.  */
435
436 static void
437 make_edges (void)
438 {
439   basic_block bb;
440   struct omp_region *cur_region = NULL;
441
442   /* Create an edge from entry to the first block with executable
443      statements in it.  */
444   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
445
446   /* Traverse the basic block array placing edges.  */
447   FOR_EACH_BB (bb)
448     {
449       tree last = last_stmt (bb);
450       bool fallthru;
451
452       if (last)
453         {
454           enum tree_code code = TREE_CODE (last);
455           switch (code)
456             {
457             case GOTO_EXPR:
458               make_goto_expr_edges (bb);
459               fallthru = false;
460               break;
461             case RETURN_EXPR:
462               make_edge (bb, EXIT_BLOCK_PTR, 0);
463               fallthru = false;
464               break;
465             case COND_EXPR:
466               make_cond_expr_edges (bb);
467               fallthru = false;
468               break;
469             case SWITCH_EXPR:
470               make_switch_expr_edges (bb);
471               fallthru = false;
472               break;
473             case RESX_EXPR:
474               make_eh_edges (last);
475               fallthru = false;
476               break;
477
478             case CALL_EXPR:
479               /* If this function receives a nonlocal goto, then we need to
480                  make edges from this call site to all the nonlocal goto
481                  handlers.  */
482               if (tree_can_make_abnormal_goto (last))
483                 make_abnormal_goto_edges (bb, true);
484
485               /* If this statement has reachable exception handlers, then
486                  create abnormal edges to them.  */
487               make_eh_edges (last);
488
489               /* Some calls are known not to return.  */
490               fallthru = !(call_expr_flags (last) & ECF_NORETURN);
491               break;
492
493             case MODIFY_EXPR:
494               gcc_unreachable ();
495
496             case GIMPLE_MODIFY_STMT:
497               if (is_ctrl_altering_stmt (last))
498                 {
499                   /* A GIMPLE_MODIFY_STMT may have a CALL_EXPR on its RHS and
500                      the CALL_EXPR may have an abnormal edge.  Search the RHS
501                      for this case and create any required edges.  */
502                   if (tree_can_make_abnormal_goto (last))
503                     make_abnormal_goto_edges (bb, true);  
504
505                   make_eh_edges (last);
506                 }
507               fallthru = true;
508               break;
509
510             case OMP_PARALLEL:
511             case OMP_FOR:
512             case OMP_SINGLE:
513             case OMP_MASTER:
514             case OMP_ORDERED:
515             case OMP_CRITICAL:
516             case OMP_SECTION:
517               cur_region = new_omp_region (bb, code, cur_region);
518               fallthru = true;
519               break;
520
521             case OMP_SECTIONS:
522               cur_region = new_omp_region (bb, code, cur_region);
523               fallthru = true;
524               break;
525
526             case OMP_SECTIONS_SWITCH:
527               fallthru = false;
528               break;
529
530
531             case OMP_ATOMIC_LOAD:
532             case OMP_ATOMIC_STORE:
533                fallthru = true;
534                break;
535
536
537             case OMP_RETURN:
538               /* In the case of an OMP_SECTION, the edge will go somewhere
539                  other than the next block.  This will be created later.  */
540               cur_region->exit = bb;
541               fallthru = cur_region->type != OMP_SECTION;
542               cur_region = cur_region->outer;
543               break;
544
545             case OMP_CONTINUE:
546               cur_region->cont = bb;
547               switch (cur_region->type)
548                 {
549                 case OMP_FOR:
550                   /* Mark all OMP_FOR and OMP_CONTINUE succs edges as abnormal
551                      to prevent splitting them.  */
552                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
553                   /* Make the loopback edge.  */
554                   make_edge (bb, single_succ (cur_region->entry),
555                              EDGE_ABNORMAL);
556
557                   /* Create an edge from OMP_FOR to exit, which corresponds to
558                      the case that the body of the loop is not executed at
559                      all.  */
560                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
561                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
562                   fallthru = false;
563                   break;
564
565                 case OMP_SECTIONS:
566                   /* Wire up the edges into and out of the nested sections.  */
567                   {
568                     basic_block switch_bb = single_succ (cur_region->entry);
569
570                     struct omp_region *i;
571                     for (i = cur_region->inner; i ; i = i->next)
572                       {
573                         gcc_assert (i->type == OMP_SECTION);
574                         make_edge (switch_bb, i->entry, 0);
575                         make_edge (i->exit, bb, EDGE_FALLTHRU);
576                       }
577
578                     /* Make the loopback edge to the block with
579                        OMP_SECTIONS_SWITCH.  */
580                     make_edge (bb, switch_bb, 0);
581
582                     /* Make the edge from the switch to exit.  */
583                     make_edge (switch_bb, bb->next_bb, 0);
584                     fallthru = false;
585                   }
586                   break;
587
588                 default:
589                   gcc_unreachable ();
590                 }
591               break;
592
593             default:
594               gcc_assert (!stmt_ends_bb_p (last));
595               fallthru = true;
596             }
597         }
598       else
599         fallthru = true;
600
601       if (fallthru)
602         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
603     }
604
605   if (root_omp_region)
606     free_omp_regions ();
607
608   /* Fold COND_EXPR_COND of each COND_EXPR.  */
609   fold_cond_expr_cond ();
610 }
611
612
613 /* Create the edges for a COND_EXPR starting at block BB.
614    At this point, both clauses must contain only simple gotos.  */
615
616 static void
617 make_cond_expr_edges (basic_block bb)
618 {
619   tree entry = last_stmt (bb);
620   basic_block then_bb, else_bb;
621   tree then_label, else_label;
622   edge e;
623
624   gcc_assert (entry);
625   gcc_assert (TREE_CODE (entry) == COND_EXPR);
626
627   /* Entry basic blocks for each component.  */
628   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
629   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
630   then_bb = label_to_block (then_label);
631   else_bb = label_to_block (else_label);
632
633   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
634   e->goto_locus = EXPR_LOCATION (COND_EXPR_THEN (entry));
635   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
636   if (e)
637     e->goto_locus = EXPR_LOCATION (COND_EXPR_ELSE (entry));
638
639   /* We do not need the gotos anymore.  */
640   COND_EXPR_THEN (entry) = NULL_TREE;
641   COND_EXPR_ELSE (entry) = NULL_TREE;
642 }
643
644
645 /* Called for each element in the hash table (P) as we delete the
646    edge to cases hash table.
647
648    Clear all the TREE_CHAINs to prevent problems with copying of
649    SWITCH_EXPRs and structure sharing rules, then free the hash table
650    element.  */
651
652 static bool
653 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
654                        void *data ATTRIBUTE_UNUSED)
655 {
656   tree t, next;
657
658   for (t = (tree) *value; t; t = next)
659     {
660       next = TREE_CHAIN (t);
661       TREE_CHAIN (t) = NULL;
662     }
663
664   *value = NULL;
665   return false;
666 }
667
668 /* Start recording information mapping edges to case labels.  */
669
670 void
671 start_recording_case_labels (void)
672 {
673   gcc_assert (edge_to_cases == NULL);
674   edge_to_cases = pointer_map_create ();
675 }
676
677 /* Return nonzero if we are recording information for case labels.  */
678
679 static bool
680 recording_case_labels_p (void)
681 {
682   return (edge_to_cases != NULL);
683 }
684
685 /* Stop recording information mapping edges to case labels and
686    remove any information we have recorded.  */
687 void
688 end_recording_case_labels (void)
689 {
690   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
691   pointer_map_destroy (edge_to_cases);
692   edge_to_cases = NULL;
693 }
694
695 /* If we are inside a {start,end}_recording_cases block, then return
696    a chain of CASE_LABEL_EXPRs from T which reference E.
697
698    Otherwise return NULL.  */
699
700 static tree
701 get_cases_for_edge (edge e, tree t)
702 {
703   void **slot;
704   size_t i, n;
705   tree vec;
706
707   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
708      chains available.  Return NULL so the caller can detect this case.  */
709   if (!recording_case_labels_p ())
710     return NULL;
711
712   slot = pointer_map_contains (edge_to_cases, e);
713   if (slot)
714     return (tree) *slot;
715
716   /* If we did not find E in the hash table, then this must be the first
717      time we have been queried for information about E & T.  Add all the
718      elements from T to the hash table then perform the query again.  */
719
720   vec = SWITCH_LABELS (t);
721   n = TREE_VEC_LENGTH (vec);
722   for (i = 0; i < n; i++)
723     {
724       tree elt = TREE_VEC_ELT (vec, i);
725       tree lab = CASE_LABEL (elt);
726       basic_block label_bb = label_to_block (lab);
727       edge this_edge = find_edge (e->src, label_bb);
728
729       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
730          a new chain.  */
731       slot = pointer_map_insert (edge_to_cases, this_edge);
732       TREE_CHAIN (elt) = (tree) *slot;
733       *slot = elt;
734     }
735
736   return (tree) *pointer_map_contains (edge_to_cases, e);
737 }
738
739 /* Create the edges for a SWITCH_EXPR starting at block BB.
740    At this point, the switch body has been lowered and the
741    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
742
743 static void
744 make_switch_expr_edges (basic_block bb)
745 {
746   tree entry = last_stmt (bb);
747   size_t i, n;
748   tree vec;
749
750   vec = SWITCH_LABELS (entry);
751   n = TREE_VEC_LENGTH (vec);
752
753   for (i = 0; i < n; ++i)
754     {
755       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
756       basic_block label_bb = label_to_block (lab);
757       make_edge (bb, label_bb, 0);
758     }
759 }
760
761
762 /* Return the basic block holding label DEST.  */
763
764 basic_block
765 label_to_block_fn (struct function *ifun, tree dest)
766 {
767   int uid = LABEL_DECL_UID (dest);
768
769   /* We would die hard when faced by an undefined label.  Emit a label to
770      the very first basic block.  This will hopefully make even the dataflow
771      and undefined variable warnings quite right.  */
772   if ((errorcount || sorrycount) && uid < 0)
773     {
774       block_stmt_iterator bsi =
775         bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
776       tree stmt;
777
778       stmt = build1 (LABEL_EXPR, void_type_node, dest);
779       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
780       uid = LABEL_DECL_UID (dest);
781     }
782   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
783       <= (unsigned int) uid)
784     return NULL;
785   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
786 }
787
788 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
789    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
790
791 void
792 make_abnormal_goto_edges (basic_block bb, bool for_call)
793 {
794   basic_block target_bb;
795   block_stmt_iterator bsi;
796
797   FOR_EACH_BB (target_bb)
798     for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
799       {
800         tree target = bsi_stmt (bsi);
801
802         if (TREE_CODE (target) != LABEL_EXPR)
803           break;
804
805         target = LABEL_EXPR_LABEL (target);
806
807         /* Make an edge to every label block that has been marked as a
808            potential target for a computed goto or a non-local goto.  */
809         if ((FORCED_LABEL (target) && !for_call)
810             || (DECL_NONLOCAL (target) && for_call))
811           {
812             make_edge (bb, target_bb, EDGE_ABNORMAL);
813             break;
814           }
815       }
816 }
817
818 /* Create edges for a goto statement at block BB.  */
819
820 static void
821 make_goto_expr_edges (basic_block bb)
822 {
823   block_stmt_iterator last = bsi_last (bb);
824   tree goto_t = bsi_stmt (last);
825
826   /* A simple GOTO creates normal edges.  */
827   if (simple_goto_p (goto_t))
828     {
829       tree dest = GOTO_DESTINATION (goto_t);
830       edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
831       e->goto_locus = EXPR_LOCATION (goto_t);
832       bsi_remove (&last, true);
833       return;
834     }
835
836   /* A computed GOTO creates abnormal edges.  */
837   make_abnormal_goto_edges (bb, false);
838 }
839
840
841 /*---------------------------------------------------------------------------
842                                Flowgraph analysis
843 ---------------------------------------------------------------------------*/
844
845 /* Cleanup useless labels in basic blocks.  This is something we wish
846    to do early because it allows us to group case labels before creating
847    the edges for the CFG, and it speeds up block statement iterators in
848    all passes later on.
849    We rerun this pass after CFG is created, to get rid of the labels that
850    are no longer referenced.  After then we do not run it any more, since
851    (almost) no new labels should be created.  */
852
853 /* A map from basic block index to the leading label of that block.  */
854 static struct label_record
855 {
856   /* The label.  */
857   tree label;
858
859   /* True if the label is referenced from somewhere.  */
860   bool used;
861 } *label_for_bb;
862
863 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
864 static void
865 update_eh_label (struct eh_region *region)
866 {
867   tree old_label = get_eh_region_tree_label (region);
868   if (old_label)
869     {
870       tree new_label;
871       basic_block bb = label_to_block (old_label);
872
873       /* ??? After optimizing, there may be EH regions with labels
874          that have already been removed from the function body, so
875          there is no basic block for them.  */
876       if (! bb)
877         return;
878
879       new_label = label_for_bb[bb->index].label;
880       label_for_bb[bb->index].used = true;
881       set_eh_region_tree_label (region, new_label);
882     }
883 }
884
885 /* Given LABEL return the first label in the same basic block.  */
886 static tree
887 main_block_label (tree label)
888 {
889   basic_block bb = label_to_block (label);
890   tree main_label = label_for_bb[bb->index].label;
891
892   /* label_to_block possibly inserted undefined label into the chain.  */
893   if (!main_label)
894     {
895       label_for_bb[bb->index].label = label;
896       main_label = label;
897     }
898
899   label_for_bb[bb->index].used = true;
900   return main_label;
901 }
902
903 /* Cleanup redundant labels.  This is a three-step process:
904      1) Find the leading label for each block.
905      2) Redirect all references to labels to the leading labels.
906      3) Cleanup all useless labels.  */
907
908 void
909 cleanup_dead_labels (void)
910 {
911   basic_block bb;
912   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
913
914   /* Find a suitable label for each block.  We use the first user-defined
915      label if there is one, or otherwise just the first label we see.  */
916   FOR_EACH_BB (bb)
917     {
918       block_stmt_iterator i;
919
920       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
921         {
922           tree label, stmt = bsi_stmt (i);
923
924           if (TREE_CODE (stmt) != LABEL_EXPR)
925             break;
926
927           label = LABEL_EXPR_LABEL (stmt);
928
929           /* If we have not yet seen a label for the current block,
930              remember this one and see if there are more labels.  */
931           if (!label_for_bb[bb->index].label)
932             {
933               label_for_bb[bb->index].label = label;
934               continue;
935             }
936
937           /* If we did see a label for the current block already, but it
938              is an artificially created label, replace it if the current
939              label is a user defined label.  */
940           if (!DECL_ARTIFICIAL (label)
941               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
942             {
943               label_for_bb[bb->index].label = label;
944               break;
945             }
946         }
947     }
948
949   /* Now redirect all jumps/branches to the selected label.
950      First do so for each block ending in a control statement.  */
951   FOR_EACH_BB (bb)
952     {
953       tree stmt = last_stmt (bb);
954       if (!stmt)
955         continue;
956
957       switch (TREE_CODE (stmt))
958         {
959         case COND_EXPR:
960           {
961             tree true_branch, false_branch;
962
963             true_branch = COND_EXPR_THEN (stmt);
964             false_branch = COND_EXPR_ELSE (stmt);
965
966             if (true_branch)
967               GOTO_DESTINATION (true_branch)
968                       = main_block_label (GOTO_DESTINATION (true_branch));
969             if (false_branch)
970               GOTO_DESTINATION (false_branch)
971                       = main_block_label (GOTO_DESTINATION (false_branch));
972
973             break;
974           }
975
976         case SWITCH_EXPR:
977           {
978             size_t i;
979             tree vec = SWITCH_LABELS (stmt);
980             size_t n = TREE_VEC_LENGTH (vec);
981
982             /* Replace all destination labels.  */
983             for (i = 0; i < n; ++i)
984               {
985                 tree elt = TREE_VEC_ELT (vec, i);
986                 tree label = main_block_label (CASE_LABEL (elt));
987                 CASE_LABEL (elt) = label;
988               }
989             break;
990           }
991
992         /* We have to handle GOTO_EXPRs until they're removed, and we don't
993            remove them until after we've created the CFG edges.  */
994         case GOTO_EXPR:
995           if (! computed_goto_p (stmt))
996             {
997               GOTO_DESTINATION (stmt)
998                 = main_block_label (GOTO_DESTINATION (stmt));
999               break;
1000             }
1001
1002         default:
1003           break;
1004       }
1005     }
1006
1007   for_each_eh_region (update_eh_label);
1008
1009   /* Finally, purge dead labels.  All user-defined labels and labels that
1010      can be the target of non-local gotos and labels which have their
1011      address taken are preserved.  */
1012   FOR_EACH_BB (bb)
1013     {
1014       block_stmt_iterator i;
1015       tree label_for_this_bb = label_for_bb[bb->index].label;
1016
1017       if (!label_for_this_bb)
1018         continue;
1019
1020       /* If the main label of the block is unused, we may still remove it.  */
1021       if (!label_for_bb[bb->index].used)
1022         label_for_this_bb = NULL;
1023
1024       for (i = bsi_start (bb); !bsi_end_p (i); )
1025         {
1026           tree label, stmt = bsi_stmt (i);
1027
1028           if (TREE_CODE (stmt) != LABEL_EXPR)
1029             break;
1030
1031           label = LABEL_EXPR_LABEL (stmt);
1032
1033           if (label == label_for_this_bb
1034               || ! DECL_ARTIFICIAL (label)
1035               || DECL_NONLOCAL (label)
1036               || FORCED_LABEL (label))
1037             bsi_next (&i);
1038           else
1039             bsi_remove (&i, true);
1040         }
1041     }
1042
1043   free (label_for_bb);
1044 }
1045
1046 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1047    and scan the sorted vector of cases.  Combine the ones jumping to the
1048    same label.
1049    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1050
1051 void
1052 group_case_labels (void)
1053 {
1054   basic_block bb;
1055
1056   FOR_EACH_BB (bb)
1057     {
1058       tree stmt = last_stmt (bb);
1059       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1060         {
1061           tree labels = SWITCH_LABELS (stmt);
1062           int old_size = TREE_VEC_LENGTH (labels);
1063           int i, j, new_size = old_size;
1064           tree default_case = NULL_TREE;
1065           tree default_label = NULL_TREE;
1066
1067           /* The default label is always the last case in a switch
1068              statement after gimplification if it was not optimized
1069              away.  */
1070           if (!CASE_LOW (TREE_VEC_ELT (labels, old_size - 1))
1071               && !CASE_HIGH (TREE_VEC_ELT (labels, old_size - 1)))
1072             {
1073               default_case = TREE_VEC_ELT (labels, old_size - 1);
1074               default_label = CASE_LABEL (default_case);
1075               old_size--;
1076             }
1077
1078           /* Look for possible opportunities to merge cases.  */
1079           i = 0;
1080           while (i < old_size)
1081             {
1082               tree base_case, base_label, base_high;
1083               base_case = TREE_VEC_ELT (labels, i);
1084
1085               gcc_assert (base_case);
1086               base_label = CASE_LABEL (base_case);
1087
1088               /* Discard cases that have the same destination as the
1089                  default case.  */
1090               if (base_label == default_label)
1091                 {
1092                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1093                   i++;
1094                   new_size--;
1095                   continue;
1096                 }
1097
1098               base_high = CASE_HIGH (base_case) ?
1099                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1100               i++;
1101               /* Try to merge case labels.  Break out when we reach the end
1102                  of the label vector or when we cannot merge the next case
1103                  label with the current one.  */
1104               while (i < old_size)
1105                 {
1106                   tree merge_case = TREE_VEC_ELT (labels, i);
1107                   tree merge_label = CASE_LABEL (merge_case);
1108                   tree t = int_const_binop (PLUS_EXPR, base_high,
1109                                             integer_one_node, 1);
1110
1111                   /* Merge the cases if they jump to the same place,
1112                      and their ranges are consecutive.  */
1113                   if (merge_label == base_label
1114                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1115                     {
1116                       base_high = CASE_HIGH (merge_case) ?
1117                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1118                       CASE_HIGH (base_case) = base_high;
1119                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1120                       new_size--;
1121                       i++;
1122                     }
1123                   else
1124                     break;
1125                 }
1126             }
1127
1128           /* Compress the case labels in the label vector, and adjust the
1129              length of the vector.  */
1130           for (i = 0, j = 0; i < new_size; i++)
1131             {
1132               while (! TREE_VEC_ELT (labels, j))
1133                 j++;
1134               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1135             }
1136           TREE_VEC_LENGTH (labels) = new_size;
1137         }
1138     }
1139 }
1140
1141 /* Checks whether we can merge block B into block A.  */
1142
1143 static bool
1144 tree_can_merge_blocks_p (basic_block a, basic_block b)
1145 {
1146   const_tree stmt;
1147   block_stmt_iterator bsi;
1148   tree phi;
1149
1150   if (!single_succ_p (a))
1151     return false;
1152
1153   if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1154     return false;
1155
1156   if (single_succ (a) != b)
1157     return false;
1158
1159   if (!single_pred_p (b))
1160     return false;
1161
1162   if (b == EXIT_BLOCK_PTR)
1163     return false;
1164
1165   /* If A ends by a statement causing exceptions or something similar, we
1166      cannot merge the blocks.  */
1167   /* This CONST_CAST is okay because last_stmt doesn't modify its
1168      argument and the return value is assign to a const_tree.  */
1169   stmt = last_stmt (CONST_CAST_BB (a));
1170   if (stmt && stmt_ends_bb_p (stmt))
1171     return false;
1172
1173   /* Do not allow a block with only a non-local label to be merged.  */
1174   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1175       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1176     return false;
1177
1178   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1179      is not up-to-date, we cannot eliminate any phis; however, if only
1180      some symbols as whole are marked for renaming, this is not a problem,
1181      as phi nodes for those symbols are irrelevant in updating anyway.  */
1182   phi = phi_nodes (b);
1183   if (phi)
1184     {
1185       if (name_mappings_registered_p ())
1186         return false;
1187
1188       for (; phi; phi = PHI_CHAIN (phi))
1189         if (!is_gimple_reg (PHI_RESULT (phi))
1190             && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
1191           return false;
1192     }
1193
1194   /* Do not remove user labels.  */
1195   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1196     {
1197       stmt = bsi_stmt (bsi);
1198       if (TREE_CODE (stmt) != LABEL_EXPR)
1199         break;
1200       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1201         return false;
1202     }
1203
1204   /* Protect the loop latches.  */
1205   if (current_loops
1206       && b->loop_father->latch == b)
1207     return false;
1208
1209   return true;
1210 }
1211
1212 /* Replaces all uses of NAME by VAL.  */
1213
1214 void
1215 replace_uses_by (tree name, tree val)
1216 {
1217   imm_use_iterator imm_iter;
1218   use_operand_p use;
1219   tree stmt;
1220   edge e;
1221
1222   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1223     {
1224       if (TREE_CODE (stmt) != PHI_NODE)
1225         push_stmt_changes (&stmt);
1226
1227       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1228         {
1229           replace_exp (use, val);
1230
1231           if (TREE_CODE (stmt) == PHI_NODE)
1232             {
1233               e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
1234               if (e->flags & EDGE_ABNORMAL)
1235                 {
1236                   /* This can only occur for virtual operands, since
1237                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1238                      would prevent replacement.  */
1239                   gcc_assert (!is_gimple_reg (name));
1240                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1241                 }
1242             }
1243         }
1244
1245       if (TREE_CODE (stmt) != PHI_NODE)
1246         {
1247           tree rhs;
1248
1249           fold_stmt_inplace (stmt);
1250           if (cfgcleanup_altered_bbs)
1251             bitmap_set_bit (cfgcleanup_altered_bbs, bb_for_stmt (stmt)->index);
1252
1253           /* FIXME.  This should go in pop_stmt_changes.  */
1254           rhs = get_rhs (stmt);
1255           if (TREE_CODE (rhs) == ADDR_EXPR)
1256             recompute_tree_invariant_for_addr_expr (rhs);
1257
1258           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1259
1260           pop_stmt_changes (&stmt);
1261         }
1262     }
1263
1264   gcc_assert (has_zero_uses (name));
1265
1266   /* Also update the trees stored in loop structures.  */
1267   if (current_loops)
1268     {
1269       struct loop *loop;
1270       loop_iterator li;
1271
1272       FOR_EACH_LOOP (li, loop, 0)
1273         {
1274           substitute_in_loop_info (loop, name, val);
1275         }
1276     }
1277 }
1278
1279 /* Merge block B into block A.  */
1280
1281 static void
1282 tree_merge_blocks (basic_block a, basic_block b)
1283 {
1284   block_stmt_iterator bsi;
1285   tree_stmt_iterator last;
1286   tree phi;
1287
1288   if (dump_file)
1289     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1290
1291   /* Remove all single-valued PHI nodes from block B of the form
1292      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1293   bsi = bsi_last (a);
1294   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1295     {
1296       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1297       tree copy;
1298       bool may_replace_uses = may_propagate_copy (def, use);
1299
1300       /* In case we maintain loop closed ssa form, do not propagate arguments
1301          of loop exit phi nodes.  */
1302       if (current_loops
1303           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1304           && is_gimple_reg (def)
1305           && TREE_CODE (use) == SSA_NAME
1306           && a->loop_father != b->loop_father)
1307         may_replace_uses = false;
1308
1309       if (!may_replace_uses)
1310         {
1311           gcc_assert (is_gimple_reg (def));
1312
1313           /* Note that just emitting the copies is fine -- there is no problem
1314              with ordering of phi nodes.  This is because A is the single
1315              predecessor of B, therefore results of the phi nodes cannot
1316              appear as arguments of the phi nodes.  */
1317           copy = build_gimple_modify_stmt (def, use);
1318           bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1319           SSA_NAME_DEF_STMT (def) = copy;
1320           remove_phi_node (phi, NULL, false);
1321         }
1322       else
1323         {
1324           /* If we deal with a PHI for virtual operands, we can simply
1325              propagate these without fussing with folding or updating
1326              the stmt.  */
1327           if (!is_gimple_reg (def))
1328             {
1329               imm_use_iterator iter;
1330               use_operand_p use_p;
1331               tree stmt;
1332
1333               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1334                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1335                   SET_USE (use_p, use);
1336             }
1337           else
1338             replace_uses_by (def, use);
1339           remove_phi_node (phi, NULL, true);
1340         }
1341     }
1342
1343   /* Ensure that B follows A.  */
1344   move_block_after (b, a);
1345
1346   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1347   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1348
1349   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1350   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1351     {
1352       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1353         {
1354           tree label = bsi_stmt (bsi);
1355
1356           bsi_remove (&bsi, false);
1357           /* Now that we can thread computed gotos, we might have
1358              a situation where we have a forced label in block B
1359              However, the label at the start of block B might still be
1360              used in other ways (think about the runtime checking for
1361              Fortran assigned gotos).  So we can not just delete the
1362              label.  Instead we move the label to the start of block A.  */
1363           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1364             {
1365               block_stmt_iterator dest_bsi = bsi_start (a);
1366               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1367             }
1368         }
1369       else
1370         {
1371           change_bb_for_stmt (bsi_stmt (bsi), a);
1372           bsi_next (&bsi);
1373         }
1374     }
1375
1376   /* Merge the chains.  */
1377   last = tsi_last (bb_stmt_list (a));
1378   tsi_link_after (&last, bb_stmt_list (b), TSI_NEW_STMT);
1379   set_bb_stmt_list (b, NULL_TREE);
1380
1381   if (cfgcleanup_altered_bbs)
1382     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1383 }
1384
1385
1386 /* Return the one of two successors of BB that is not reachable by a
1387    reached by a complex edge, if there is one.  Else, return BB.  We use
1388    this in optimizations that use post-dominators for their heuristics,
1389    to catch the cases in C++ where function calls are involved.  */
1390
1391 basic_block
1392 single_noncomplex_succ (basic_block bb)
1393 {
1394   edge e0, e1;
1395   if (EDGE_COUNT (bb->succs) != 2)
1396     return bb;
1397
1398   e0 = EDGE_SUCC (bb, 0);
1399   e1 = EDGE_SUCC (bb, 1);
1400   if (e0->flags & EDGE_COMPLEX)
1401     return e1->dest;
1402   if (e1->flags & EDGE_COMPLEX)
1403     return e0->dest;
1404
1405   return bb;
1406 }
1407
1408
1409 /* Walk the function tree removing unnecessary statements.
1410
1411      * Empty statement nodes are removed
1412
1413      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1414
1415      * Unnecessary COND_EXPRs are removed
1416
1417      * Some unnecessary BIND_EXPRs are removed
1418
1419    Clearly more work could be done.  The trick is doing the analysis
1420    and removal fast enough to be a net improvement in compile times.
1421
1422    Note that when we remove a control structure such as a COND_EXPR
1423    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1424    to ensure we eliminate all the useless code.  */
1425
1426 struct rus_data
1427 {
1428   tree *last_goto;
1429   bool repeat;
1430   bool may_throw;
1431   bool may_branch;
1432   bool has_label;
1433 };
1434
1435 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1436
1437 static bool
1438 remove_useless_stmts_warn_notreached (tree stmt)
1439 {
1440   if (EXPR_HAS_LOCATION (stmt))
1441     {
1442       location_t loc = EXPR_LOCATION (stmt);
1443       if (LOCATION_LINE (loc) > 0)
1444         {
1445           warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
1446           return true;
1447         }
1448     }
1449
1450   switch (TREE_CODE (stmt))
1451     {
1452     case STATEMENT_LIST:
1453       {
1454         tree_stmt_iterator i;
1455         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1456           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1457             return true;
1458       }
1459       break;
1460
1461     case COND_EXPR:
1462       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1463         return true;
1464       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1465         return true;
1466       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1467         return true;
1468       break;
1469
1470     case TRY_FINALLY_EXPR:
1471     case TRY_CATCH_EXPR:
1472       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1473         return true;
1474       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1475         return true;
1476       break;
1477
1478     case CATCH_EXPR:
1479       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1480     case EH_FILTER_EXPR:
1481       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1482     case BIND_EXPR:
1483       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1484
1485     default:
1486       /* Not a live container.  */
1487       break;
1488     }
1489
1490   return false;
1491 }
1492
1493 static void
1494 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1495 {
1496   tree then_clause, else_clause, cond;
1497   bool save_has_label, then_has_label, else_has_label;
1498
1499   save_has_label = data->has_label;
1500   data->has_label = false;
1501   data->last_goto = NULL;
1502
1503   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1504
1505   then_has_label = data->has_label;
1506   data->has_label = false;
1507   data->last_goto = NULL;
1508
1509   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1510
1511   else_has_label = data->has_label;
1512   data->has_label = save_has_label | then_has_label | else_has_label;
1513
1514   then_clause = COND_EXPR_THEN (*stmt_p);
1515   else_clause = COND_EXPR_ELSE (*stmt_p);
1516   cond = fold (COND_EXPR_COND (*stmt_p));
1517
1518   /* If neither arm does anything at all, we can remove the whole IF.  */
1519   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1520     {
1521       *stmt_p = build_empty_stmt ();
1522       data->repeat = true;
1523     }
1524
1525   /* If there are no reachable statements in an arm, then we can
1526      zap the entire conditional.  */
1527   else if (integer_nonzerop (cond) && !else_has_label)
1528     {
1529       if (warn_notreached)
1530         remove_useless_stmts_warn_notreached (else_clause);
1531       *stmt_p = then_clause;
1532       data->repeat = true;
1533     }
1534   else if (integer_zerop (cond) && !then_has_label)
1535     {
1536       if (warn_notreached)
1537         remove_useless_stmts_warn_notreached (then_clause);
1538       *stmt_p = else_clause;
1539       data->repeat = true;
1540     }
1541
1542   /* Check a couple of simple things on then/else with single stmts.  */
1543   else
1544     {
1545       tree then_stmt = expr_only (then_clause);
1546       tree else_stmt = expr_only (else_clause);
1547
1548       /* Notice branches to a common destination.  */
1549       if (then_stmt && else_stmt
1550           && TREE_CODE (then_stmt) == GOTO_EXPR
1551           && TREE_CODE (else_stmt) == GOTO_EXPR
1552           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1553         {
1554           *stmt_p = then_stmt;
1555           data->repeat = true;
1556         }
1557
1558       /* If the THEN/ELSE clause merely assigns a value to a variable or
1559          parameter which is already known to contain that value, then
1560          remove the useless THEN/ELSE clause.  */
1561       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1562         {
1563           if (else_stmt
1564               && TREE_CODE (else_stmt) == GIMPLE_MODIFY_STMT
1565               && GIMPLE_STMT_OPERAND (else_stmt, 0) == cond
1566               && integer_zerop (GIMPLE_STMT_OPERAND (else_stmt, 1)))
1567             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1568         }
1569       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1570                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1571                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1572                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1573         {
1574           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1575                        ? then_stmt : else_stmt);
1576           tree *location = (TREE_CODE (cond) == EQ_EXPR
1577                             ? &COND_EXPR_THEN (*stmt_p)
1578                             : &COND_EXPR_ELSE (*stmt_p));
1579
1580           if (stmt
1581               && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1582               && GIMPLE_STMT_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1583               && GIMPLE_STMT_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1584             *location = alloc_stmt_list ();
1585         }
1586     }
1587
1588   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1589      would be re-introduced during lowering.  */
1590   data->last_goto = NULL;
1591 }
1592
1593
1594 static void
1595 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1596 {
1597   bool save_may_branch, save_may_throw;
1598   bool this_may_branch, this_may_throw;
1599
1600   /* Collect may_branch and may_throw information for the body only.  */
1601   save_may_branch = data->may_branch;
1602   save_may_throw = data->may_throw;
1603   data->may_branch = false;
1604   data->may_throw = false;
1605   data->last_goto = NULL;
1606
1607   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1608
1609   this_may_branch = data->may_branch;
1610   this_may_throw = data->may_throw;
1611   data->may_branch |= save_may_branch;
1612   data->may_throw |= save_may_throw;
1613   data->last_goto = NULL;
1614
1615   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1616
1617   /* If the body is empty, then we can emit the FINALLY block without
1618      the enclosing TRY_FINALLY_EXPR.  */
1619   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1620     {
1621       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1622       data->repeat = true;
1623     }
1624
1625   /* If the handler is empty, then we can emit the TRY block without
1626      the enclosing TRY_FINALLY_EXPR.  */
1627   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1628     {
1629       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1630       data->repeat = true;
1631     }
1632
1633   /* If the body neither throws, nor branches, then we can safely
1634      string the TRY and FINALLY blocks together.  */
1635   else if (!this_may_branch && !this_may_throw)
1636     {
1637       tree stmt = *stmt_p;
1638       *stmt_p = TREE_OPERAND (stmt, 0);
1639       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1640       data->repeat = true;
1641     }
1642 }
1643
1644
1645 static void
1646 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1647 {
1648   bool save_may_throw, this_may_throw;
1649   tree_stmt_iterator i;
1650   tree stmt;
1651
1652   /* Collect may_throw information for the body only.  */
1653   save_may_throw = data->may_throw;
1654   data->may_throw = false;
1655   data->last_goto = NULL;
1656
1657   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1658
1659   this_may_throw = data->may_throw;
1660   data->may_throw = save_may_throw;
1661
1662   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1663   if (!this_may_throw)
1664     {
1665       if (warn_notreached)
1666         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1667       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1668       data->repeat = true;
1669       return;
1670     }
1671
1672   /* Process the catch clause specially.  We may be able to tell that
1673      no exceptions propagate past this point.  */
1674
1675   this_may_throw = true;
1676   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1677   stmt = tsi_stmt (i);
1678   data->last_goto = NULL;
1679
1680   switch (TREE_CODE (stmt))
1681     {
1682     case CATCH_EXPR:
1683       for (; !tsi_end_p (i); tsi_next (&i))
1684         {
1685           stmt = tsi_stmt (i);
1686           /* If we catch all exceptions, then the body does not
1687              propagate exceptions past this point.  */
1688           if (CATCH_TYPES (stmt) == NULL)
1689             this_may_throw = false;
1690           data->last_goto = NULL;
1691           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1692         }
1693       break;
1694
1695     case EH_FILTER_EXPR:
1696       if (EH_FILTER_MUST_NOT_THROW (stmt))
1697         this_may_throw = false;
1698       else if (EH_FILTER_TYPES (stmt) == NULL)
1699         this_may_throw = false;
1700       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1701       break;
1702
1703     default:
1704       /* Otherwise this is a cleanup.  */
1705       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1706
1707       /* If the cleanup is empty, then we can emit the TRY block without
1708          the enclosing TRY_CATCH_EXPR.  */
1709       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1710         {
1711           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1712           data->repeat = true;
1713         }
1714       break;
1715     }
1716   data->may_throw |= this_may_throw;
1717 }
1718
1719
1720 static void
1721 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1722 {
1723   tree block;
1724
1725   /* First remove anything underneath the BIND_EXPR.  */
1726   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1727
1728   /* If the BIND_EXPR has no variables, then we can pull everything
1729      up one level and remove the BIND_EXPR, unless this is the toplevel
1730      BIND_EXPR for the current function or an inlined function.
1731
1732      When this situation occurs we will want to apply this
1733      optimization again.  */
1734   block = BIND_EXPR_BLOCK (*stmt_p);
1735   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1736       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1737       && (! block
1738           || ! BLOCK_ABSTRACT_ORIGIN (block)
1739           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1740               != FUNCTION_DECL)))
1741     {
1742       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1743       data->repeat = true;
1744     }
1745 }
1746
1747
1748 static void
1749 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1750 {
1751   tree dest = GOTO_DESTINATION (*stmt_p);
1752
1753   data->may_branch = true;
1754   data->last_goto = NULL;
1755
1756   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1757   if (TREE_CODE (dest) == LABEL_DECL)
1758     data->last_goto = stmt_p;
1759 }
1760
1761
1762 static void
1763 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1764 {
1765   tree label = LABEL_EXPR_LABEL (*stmt_p);
1766
1767   data->has_label = true;
1768
1769   /* We do want to jump across non-local label receiver code.  */
1770   if (DECL_NONLOCAL (label))
1771     data->last_goto = NULL;
1772
1773   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1774     {
1775       *data->last_goto = build_empty_stmt ();
1776       data->repeat = true;
1777     }
1778
1779   /* ??? Add something here to delete unused labels.  */
1780 }
1781
1782
1783 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1784    decl.  This allows us to eliminate redundant or useless
1785    calls to "const" functions.
1786
1787    Gimplifier already does the same operation, but we may notice functions
1788    being const and pure once their calls has been gimplified, so we need
1789    to update the flag.  */
1790
1791 static void
1792 update_call_expr_flags (tree call)
1793 {
1794   tree decl = get_callee_fndecl (call);
1795   int flags;
1796   if (!decl)
1797     return;
1798   flags = call_expr_flags (call);
1799   if (flags & (ECF_CONST | ECF_PURE) && !(flags & ECF_LOOPING_CONST_OR_PURE))
1800     TREE_SIDE_EFFECTS (call) = 0;
1801   if (TREE_NOTHROW (decl))
1802     TREE_NOTHROW (call) = 1;
1803 }
1804
1805
1806 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1807
1808 void
1809 notice_special_calls (tree t)
1810 {
1811   int flags = call_expr_flags (t);
1812
1813   if (flags & ECF_MAY_BE_ALLOCA)
1814     cfun->calls_alloca = true;
1815   if (flags & ECF_RETURNS_TWICE)
1816     cfun->calls_setjmp = true;
1817 }
1818
1819
1820 /* Clear flags set by notice_special_calls.  Used by dead code removal
1821    to update the flags.  */
1822
1823 void
1824 clear_special_calls (void)
1825 {
1826   cfun->calls_alloca = false;
1827   cfun->calls_setjmp = false;
1828 }
1829
1830
1831 static void
1832 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1833 {
1834   tree t = *tp, op;
1835
1836   switch (TREE_CODE (t))
1837     {
1838     case COND_EXPR:
1839       remove_useless_stmts_cond (tp, data);
1840       break;
1841
1842     case TRY_FINALLY_EXPR:
1843       remove_useless_stmts_tf (tp, data);
1844       break;
1845
1846     case TRY_CATCH_EXPR:
1847       remove_useless_stmts_tc (tp, data);
1848       break;
1849
1850     case BIND_EXPR:
1851       remove_useless_stmts_bind (tp, data);
1852       break;
1853
1854     case GOTO_EXPR:
1855       remove_useless_stmts_goto (tp, data);
1856       break;
1857
1858     case LABEL_EXPR:
1859       remove_useless_stmts_label (tp, data);
1860       break;
1861
1862     case RETURN_EXPR:
1863       fold_stmt (tp);
1864       data->last_goto = NULL;
1865       data->may_branch = true;
1866       break;
1867
1868     case CALL_EXPR:
1869       fold_stmt (tp);
1870       data->last_goto = NULL;
1871       notice_special_calls (t);
1872       update_call_expr_flags (t);
1873       if (tree_could_throw_p (t))
1874         data->may_throw = true;
1875       break;
1876
1877     case MODIFY_EXPR:
1878       gcc_unreachable ();
1879
1880     case GIMPLE_MODIFY_STMT:
1881       data->last_goto = NULL;
1882       fold_stmt (tp);
1883       op = get_call_expr_in (t);
1884       if (op)
1885         {
1886           update_call_expr_flags (op);
1887           notice_special_calls (op);
1888         }
1889       if (tree_could_throw_p (t))
1890         data->may_throw = true;
1891       break;
1892
1893     case STATEMENT_LIST:
1894       {
1895         tree_stmt_iterator i = tsi_start (t);
1896         while (!tsi_end_p (i))
1897           {
1898             t = tsi_stmt (i);
1899             if (IS_EMPTY_STMT (t))
1900               {
1901                 tsi_delink (&i);
1902                 continue;
1903               }
1904
1905             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1906
1907             t = tsi_stmt (i);
1908             if (TREE_CODE (t) == STATEMENT_LIST)
1909               {
1910                 tsi_link_before (&i, t, TSI_SAME_STMT);
1911                 tsi_delink (&i);
1912               }
1913             else
1914               tsi_next (&i);
1915           }
1916       }
1917       break;
1918     case ASM_EXPR:
1919       fold_stmt (tp);
1920       data->last_goto = NULL;
1921       break;
1922
1923     case OMP_PARALLEL:
1924       /* Make sure the outermost BIND_EXPR in OMP_BODY isn't removed
1925          as useless.  */
1926       remove_useless_stmts_1 (&BIND_EXPR_BODY (OMP_BODY (*tp)), data);
1927       data->last_goto = NULL;
1928       break;
1929
1930     case OMP_SECTIONS:
1931     case OMP_SINGLE:
1932     case OMP_SECTION:
1933     case OMP_MASTER :
1934     case OMP_ORDERED:
1935     case OMP_CRITICAL:
1936       remove_useless_stmts_1 (&OMP_BODY (*tp), data);
1937       data->last_goto = NULL;
1938       break;
1939
1940     case OMP_FOR:
1941       remove_useless_stmts_1 (&OMP_FOR_BODY (*tp), data);
1942       data->last_goto = NULL;
1943       if (OMP_FOR_PRE_BODY (*tp))
1944         {
1945           remove_useless_stmts_1 (&OMP_FOR_PRE_BODY (*tp), data);
1946           data->last_goto = NULL;
1947         }
1948       break;
1949
1950     default:
1951       data->last_goto = NULL;
1952       break;
1953     }
1954 }
1955
1956 static unsigned int
1957 remove_useless_stmts (void)
1958 {
1959   struct rus_data data;
1960
1961   clear_special_calls ();
1962
1963   do
1964     {
1965       memset (&data, 0, sizeof (data));
1966       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1967     }
1968   while (data.repeat);
1969   return 0;
1970 }
1971
1972
1973 struct gimple_opt_pass pass_remove_useless_stmts =
1974 {
1975  {
1976   GIMPLE_PASS,
1977   "useless",                            /* name */
1978   NULL,                                 /* gate */
1979   remove_useless_stmts,                 /* execute */
1980   NULL,                                 /* sub */
1981   NULL,                                 /* next */
1982   0,                                    /* static_pass_number */
1983   0,                                    /* tv_id */
1984   PROP_gimple_any,                      /* properties_required */
1985   0,                                    /* properties_provided */
1986   0,                                    /* properties_destroyed */
1987   0,                                    /* todo_flags_start */
1988   TODO_dump_func                        /* todo_flags_finish */
1989  }
1990 };
1991
1992 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1993
1994 static void
1995 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1996 {
1997   tree phi;
1998
1999   /* Since this block is no longer reachable, we can just delete all
2000      of its PHI nodes.  */
2001   phi = phi_nodes (bb);
2002   while (phi)
2003     {
2004       tree next = PHI_CHAIN (phi);
2005       remove_phi_node (phi, NULL_TREE, true);
2006       phi = next;
2007     }
2008
2009   /* Remove edges to BB's successors.  */
2010   while (EDGE_COUNT (bb->succs) > 0)
2011     remove_edge (EDGE_SUCC (bb, 0));
2012 }
2013
2014
2015 /* Remove statements of basic block BB.  */
2016
2017 static void
2018 remove_bb (basic_block bb)
2019 {
2020   block_stmt_iterator i;
2021   source_location loc = UNKNOWN_LOCATION;
2022
2023   if (dump_file)
2024     {
2025       fprintf (dump_file, "Removing basic block %d\n", bb->index);
2026       if (dump_flags & TDF_DETAILS)
2027         {
2028           dump_bb (bb, dump_file, 0);
2029           fprintf (dump_file, "\n");
2030         }
2031     }
2032
2033   if (current_loops)
2034     {
2035       struct loop *loop = bb->loop_father;
2036
2037       /* If a loop gets removed, clean up the information associated
2038          with it.  */
2039       if (loop->latch == bb
2040           || loop->header == bb)
2041         free_numbers_of_iterations_estimates_loop (loop);
2042     }
2043
2044   /* Remove all the instructions in the block.  */
2045   if (bb_stmt_list (bb) != NULL_TREE)
2046     {
2047       for (i = bsi_start (bb); !bsi_end_p (i);)
2048         {
2049           tree stmt = bsi_stmt (i);
2050           if (TREE_CODE (stmt) == LABEL_EXPR
2051               && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
2052                   || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
2053             {
2054               basic_block new_bb;
2055               block_stmt_iterator new_bsi;
2056
2057               /* A non-reachable non-local label may still be referenced.
2058                  But it no longer needs to carry the extra semantics of
2059                  non-locality.  */
2060               if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
2061                 {
2062                   DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
2063                   FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
2064                 }
2065
2066               new_bb = bb->prev_bb;
2067               new_bsi = bsi_start (new_bb);
2068               bsi_remove (&i, false);
2069               bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2070             }
2071           else
2072             {
2073               /* Release SSA definitions if we are in SSA.  Note that we
2074                  may be called when not in SSA.  For example,
2075                  final_cleanup calls this function via
2076                  cleanup_tree_cfg.  */
2077               if (gimple_in_ssa_p (cfun))
2078                 release_defs (stmt);
2079
2080               bsi_remove (&i, true);
2081             }
2082
2083           /* Don't warn for removed gotos.  Gotos are often removed due to
2084              jump threading, thus resulting in bogus warnings.  Not great,
2085              since this way we lose warnings for gotos in the original
2086              program that are indeed unreachable.  */
2087           if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2088             {
2089               if (EXPR_HAS_LOCATION (stmt))
2090                 loc = EXPR_LOCATION (stmt);
2091             }
2092         }
2093     }
2094
2095   /* If requested, give a warning that the first statement in the
2096      block is unreachable.  We walk statements backwards in the
2097      loop above, so the last statement we process is the first statement
2098      in the block.  */
2099   if (loc > BUILTINS_LOCATION && LOCATION_LINE (loc) > 0)
2100     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2101
2102   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2103   bb->il.tree = NULL;
2104 }
2105
2106
2107 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2108    predicate VAL, return the edge that will be taken out of the block.
2109    If VAL does not match a unique edge, NULL is returned.  */
2110
2111 edge
2112 find_taken_edge (basic_block bb, tree val)
2113 {
2114   tree stmt;
2115
2116   stmt = last_stmt (bb);
2117
2118   gcc_assert (stmt);
2119   gcc_assert (is_ctrl_stmt (stmt));
2120   gcc_assert (val);
2121
2122   if (! is_gimple_min_invariant (val))
2123     return NULL;
2124
2125   if (TREE_CODE (stmt) == COND_EXPR)
2126     return find_taken_edge_cond_expr (bb, val);
2127
2128   if (TREE_CODE (stmt) == SWITCH_EXPR)
2129     return find_taken_edge_switch_expr (bb, val);
2130
2131   if (computed_goto_p (stmt))
2132     {
2133       /* Only optimize if the argument is a label, if the argument is
2134          not a label then we can not construct a proper CFG.
2135
2136          It may be the case that we only need to allow the LABEL_REF to
2137          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2138          appear inside a LABEL_EXPR just to be safe.  */
2139       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2140           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2141         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2142       return NULL;
2143     }
2144
2145   gcc_unreachable ();
2146 }
2147
2148 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2149    statement, determine which of the outgoing edges will be taken out of the
2150    block.  Return NULL if either edge may be taken.  */
2151
2152 static edge
2153 find_taken_edge_computed_goto (basic_block bb, tree val)
2154 {
2155   basic_block dest;
2156   edge e = NULL;
2157
2158   dest = label_to_block (val);
2159   if (dest)
2160     {
2161       e = find_edge (bb, dest);
2162       gcc_assert (e != NULL);
2163     }
2164
2165   return e;
2166 }
2167
2168 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2169    statement, determine which of the two edges will be taken out of the
2170    block.  Return NULL if either edge may be taken.  */
2171
2172 static edge
2173 find_taken_edge_cond_expr (basic_block bb, tree val)
2174 {
2175   edge true_edge, false_edge;
2176
2177   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2178
2179   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2180   return (integer_zerop (val) ? false_edge : true_edge);
2181 }
2182
2183 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2184    statement, determine which edge will be taken out of the block.  Return
2185    NULL if any edge may be taken.  */
2186
2187 static edge
2188 find_taken_edge_switch_expr (basic_block bb, tree val)
2189 {
2190   tree switch_expr, taken_case;
2191   basic_block dest_bb;
2192   edge e;
2193
2194   switch_expr = last_stmt (bb);
2195   taken_case = find_case_label_for_value (switch_expr, val);
2196   dest_bb = label_to_block (CASE_LABEL (taken_case));
2197
2198   e = find_edge (bb, dest_bb);
2199   gcc_assert (e);
2200   return e;
2201 }
2202
2203
2204 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2205    We can make optimal use here of the fact that the case labels are
2206    sorted: We can do a binary search for a case matching VAL.  */
2207
2208 static tree
2209 find_case_label_for_value (tree switch_expr, tree val)
2210 {
2211   tree vec = SWITCH_LABELS (switch_expr);
2212   size_t low, high, n = TREE_VEC_LENGTH (vec);
2213   tree default_case = TREE_VEC_ELT (vec, n - 1);
2214
2215   for (low = -1, high = n - 1; high - low > 1; )
2216     {
2217       size_t i = (high + low) / 2;
2218       tree t = TREE_VEC_ELT (vec, i);
2219       int cmp;
2220
2221       /* Cache the result of comparing CASE_LOW and val.  */
2222       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2223
2224       if (cmp > 0)
2225         high = i;
2226       else
2227         low = i;
2228
2229       if (CASE_HIGH (t) == NULL)
2230         {
2231           /* A singe-valued case label.  */
2232           if (cmp == 0)
2233             return t;
2234         }
2235       else
2236         {
2237           /* A case range.  We can only handle integer ranges.  */
2238           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2239             return t;
2240         }
2241     }
2242
2243   return default_case;
2244 }
2245
2246
2247
2248
2249 /*---------------------------------------------------------------------------
2250                               Debugging functions
2251 ---------------------------------------------------------------------------*/
2252
2253 /* Dump tree-specific information of block BB to file OUTF.  */
2254
2255 void
2256 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2257 {
2258   dump_generic_bb (outf, bb, indent, TDF_VOPS|TDF_MEMSYMS);
2259 }
2260
2261
2262 /* Dump a basic block on stderr.  */
2263
2264 void
2265 debug_tree_bb (basic_block bb)
2266 {
2267   dump_bb (bb, stderr, 0);
2268 }
2269
2270
2271 /* Dump basic block with index N on stderr.  */
2272
2273 basic_block
2274 debug_tree_bb_n (int n)
2275 {
2276   debug_tree_bb (BASIC_BLOCK (n));
2277   return BASIC_BLOCK (n);
2278 }
2279
2280
2281 /* Dump the CFG on stderr.
2282
2283    FLAGS are the same used by the tree dumping functions
2284    (see TDF_* in tree-pass.h).  */
2285
2286 void
2287 debug_tree_cfg (int flags)
2288 {
2289   dump_tree_cfg (stderr, flags);
2290 }
2291
2292
2293 /* Dump the program showing basic block boundaries on the given FILE.
2294
2295    FLAGS are the same used by the tree dumping functions (see TDF_* in
2296    tree.h).  */
2297
2298 void
2299 dump_tree_cfg (FILE *file, int flags)
2300 {
2301   if (flags & TDF_DETAILS)
2302     {
2303       const char *funcname
2304         = lang_hooks.decl_printable_name (current_function_decl, 2);
2305
2306       fputc ('\n', file);
2307       fprintf (file, ";; Function %s\n\n", funcname);
2308       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2309                n_basic_blocks, n_edges, last_basic_block);
2310
2311       brief_dump_cfg (file);
2312       fprintf (file, "\n");
2313     }
2314
2315   if (flags & TDF_STATS)
2316     dump_cfg_stats (file);
2317
2318   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2319 }
2320
2321
2322 /* Dump CFG statistics on FILE.  */
2323
2324 void
2325 dump_cfg_stats (FILE *file)
2326 {
2327   static long max_num_merged_labels = 0;
2328   unsigned long size, total = 0;
2329   long num_edges;
2330   basic_block bb;
2331   const char * const fmt_str   = "%-30s%-13s%12s\n";
2332   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2333   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2334   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2335   const char *funcname
2336     = lang_hooks.decl_printable_name (current_function_decl, 2);
2337
2338
2339   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2340
2341   fprintf (file, "---------------------------------------------------------\n");
2342   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2343   fprintf (file, fmt_str, "", "  instances  ", "used ");
2344   fprintf (file, "---------------------------------------------------------\n");
2345
2346   size = n_basic_blocks * sizeof (struct basic_block_def);
2347   total += size;
2348   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2349            SCALE (size), LABEL (size));
2350
2351   num_edges = 0;
2352   FOR_EACH_BB (bb)
2353     num_edges += EDGE_COUNT (bb->succs);
2354   size = num_edges * sizeof (struct edge_def);
2355   total += size;
2356   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2357
2358   fprintf (file, "---------------------------------------------------------\n");
2359   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2360            LABEL (total));
2361   fprintf (file, "---------------------------------------------------------\n");
2362   fprintf (file, "\n");
2363
2364   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2365     max_num_merged_labels = cfg_stats.num_merged_labels;
2366
2367   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2368            cfg_stats.num_merged_labels, max_num_merged_labels);
2369
2370   fprintf (file, "\n");
2371 }
2372
2373
2374 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2375    linked in the final executable.  */
2376
2377 void
2378 debug_cfg_stats (void)
2379 {
2380   dump_cfg_stats (stderr);
2381 }
2382
2383
2384 /* Dump the flowgraph to a .vcg FILE.  */
2385
2386 static void
2387 tree_cfg2vcg (FILE *file)
2388 {
2389   edge e;
2390   edge_iterator ei;
2391   basic_block bb;
2392   const char *funcname
2393     = lang_hooks.decl_printable_name (current_function_decl, 2);
2394
2395   /* Write the file header.  */
2396   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2397   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2398   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2399
2400   /* Write blocks and edges.  */
2401   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2402     {
2403       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2404                e->dest->index);
2405
2406       if (e->flags & EDGE_FAKE)
2407         fprintf (file, " linestyle: dotted priority: 10");
2408       else
2409         fprintf (file, " linestyle: solid priority: 100");
2410
2411       fprintf (file, " }\n");
2412     }
2413   fputc ('\n', file);
2414
2415   FOR_EACH_BB (bb)
2416     {
2417       enum tree_code head_code, end_code;
2418       const char *head_name, *end_name;
2419       int head_line = 0;
2420       int end_line = 0;
2421       tree first = first_stmt (bb);
2422       tree last = last_stmt (bb);
2423
2424       if (first)
2425         {
2426           head_code = TREE_CODE (first);
2427           head_name = tree_code_name[head_code];
2428           head_line = get_lineno (first);
2429         }
2430       else
2431         head_name = "no-statement";
2432
2433       if (last)
2434         {
2435           end_code = TREE_CODE (last);
2436           end_name = tree_code_name[end_code];
2437           end_line = get_lineno (last);
2438         }
2439       else
2440         end_name = "no-statement";
2441
2442       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2443                bb->index, bb->index, head_name, head_line, end_name,
2444                end_line);
2445
2446       FOR_EACH_EDGE (e, ei, bb->succs)
2447         {
2448           if (e->dest == EXIT_BLOCK_PTR)
2449             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2450           else
2451             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2452
2453           if (e->flags & EDGE_FAKE)
2454             fprintf (file, " priority: 10 linestyle: dotted");
2455           else
2456             fprintf (file, " priority: 100 linestyle: solid");
2457
2458           fprintf (file, " }\n");
2459         }
2460
2461       if (bb->next_bb != EXIT_BLOCK_PTR)
2462         fputc ('\n', file);
2463     }
2464
2465   fputs ("}\n\n", file);
2466 }
2467
2468
2469
2470 /*---------------------------------------------------------------------------
2471                              Miscellaneous helpers
2472 ---------------------------------------------------------------------------*/
2473
2474 /* Return true if T represents a stmt that always transfers control.  */
2475
2476 bool
2477 is_ctrl_stmt (const_tree t)
2478 {
2479   return (TREE_CODE (t) == COND_EXPR
2480           || TREE_CODE (t) == SWITCH_EXPR
2481           || TREE_CODE (t) == GOTO_EXPR
2482           || TREE_CODE (t) == RETURN_EXPR
2483           || TREE_CODE (t) == RESX_EXPR);
2484 }
2485
2486
2487 /* Return true if T is a statement that may alter the flow of control
2488    (e.g., a call to a non-returning function).  */
2489
2490 bool
2491 is_ctrl_altering_stmt (const_tree t)
2492 {
2493   const_tree call;
2494
2495   gcc_assert (t);
2496   call = get_call_expr_in (CONST_CAST_TREE (t));
2497   if (call)
2498     {
2499       /* A non-pure/const CALL_EXPR alters flow control if the current
2500          function has nonlocal labels.  */
2501       if (TREE_SIDE_EFFECTS (call) && cfun->has_nonlocal_label)
2502         return true;
2503
2504       /* A CALL_EXPR also alters control flow if it does not return.  */
2505       if (call_expr_flags (call) & ECF_NORETURN)
2506         return true;
2507     }
2508
2509   /* OpenMP directives alter control flow.  */
2510   if (OMP_DIRECTIVE_P (t))
2511     return true;
2512
2513   /* If a statement can throw, it alters control flow.  */
2514   return tree_can_throw_internal (t);
2515 }
2516
2517
2518 /* Return true if T is a computed goto.  */
2519
2520 static bool
2521 computed_goto_p (const_tree t)
2522 {
2523   return (TREE_CODE (t) == GOTO_EXPR
2524           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2525 }
2526
2527
2528 /* Return true if T is a simple local goto.  */
2529
2530 bool
2531 simple_goto_p (const_tree t)
2532 {
2533   return (TREE_CODE (t) == GOTO_EXPR
2534           && TREE_CODE (GOTO_DESTINATION (t)) == LABEL_DECL);
2535 }
2536
2537
2538 /* Return true if T can make an abnormal transfer of control flow.
2539    Transfers of control flow associated with EH are excluded.  */
2540
2541 bool
2542 tree_can_make_abnormal_goto (const_tree t)
2543 {
2544   if (computed_goto_p (t))
2545     return true;
2546   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
2547     t = GIMPLE_STMT_OPERAND (t, 1);
2548   if (TREE_CODE (t) == WITH_SIZE_EXPR)
2549     t = TREE_OPERAND (t, 0);
2550   if (TREE_CODE (t) == CALL_EXPR)
2551     return TREE_SIDE_EFFECTS (t) && cfun->has_nonlocal_label;
2552   return false;
2553 }
2554
2555
2556 /* Return true if T should start a new basic block.  PREV_T is the
2557    statement preceding T.  It is used when T is a label or a case label.
2558    Labels should only start a new basic block if their previous statement
2559    wasn't a label.  Otherwise, sequence of labels would generate
2560    unnecessary basic blocks that only contain a single label.  */
2561
2562 static inline bool
2563 stmt_starts_bb_p (const_tree t, const_tree prev_t)
2564 {
2565   if (t == NULL_TREE)
2566     return false;
2567
2568   /* LABEL_EXPRs start a new basic block only if the preceding
2569      statement wasn't a label of the same type.  This prevents the
2570      creation of consecutive blocks that have nothing but a single
2571      label.  */
2572   if (TREE_CODE (t) == LABEL_EXPR)
2573     {
2574       /* Nonlocal and computed GOTO targets always start a new block.  */
2575       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2576           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2577         return true;
2578
2579       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2580         {
2581           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2582             return true;
2583
2584           cfg_stats.num_merged_labels++;
2585           return false;
2586         }
2587       else
2588         return true;
2589     }
2590
2591   return false;
2592 }
2593
2594
2595 /* Return true if T should end a basic block.  */
2596
2597 bool
2598 stmt_ends_bb_p (const_tree t)
2599 {
2600   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2601 }
2602
2603 /* Remove block annotations and other datastructures.  */
2604
2605 void
2606 delete_tree_cfg_annotations (void)
2607 {
2608   basic_block bb;
2609   block_stmt_iterator bsi;
2610
2611   /* Remove annotations from every tree in the function.  */
2612   FOR_EACH_BB (bb)
2613     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2614       {
2615         tree stmt = bsi_stmt (bsi);
2616         ggc_free (stmt->base.ann);
2617         stmt->base.ann = NULL;
2618       }
2619   label_to_block_map = NULL;
2620 }
2621
2622
2623 /* Return the first statement in basic block BB.  */
2624
2625 tree
2626 first_stmt (basic_block bb)
2627 {
2628   block_stmt_iterator i = bsi_start (bb);
2629   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2630 }
2631
2632 /* Return the last statement in basic block BB.  */
2633
2634 tree
2635 last_stmt (basic_block bb)
2636 {
2637   block_stmt_iterator b = bsi_last (bb);
2638   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2639 }
2640
2641 /* Return the last statement of an otherwise empty block.  Return NULL
2642    if the block is totally empty, or if it contains more than one
2643    statement.  */
2644
2645 tree
2646 last_and_only_stmt (basic_block bb)
2647 {
2648   block_stmt_iterator i = bsi_last (bb);
2649   tree last, prev;
2650
2651   if (bsi_end_p (i))
2652     return NULL_TREE;
2653
2654   last = bsi_stmt (i);
2655   bsi_prev (&i);
2656   if (bsi_end_p (i))
2657     return last;
2658
2659   /* Empty statements should no longer appear in the instruction stream.
2660      Everything that might have appeared before should be deleted by
2661      remove_useless_stmts, and the optimizers should just bsi_remove
2662      instead of smashing with build_empty_stmt.
2663
2664      Thus the only thing that should appear here in a block containing
2665      one executable statement is a label.  */
2666   prev = bsi_stmt (i);
2667   if (TREE_CODE (prev) == LABEL_EXPR)
2668     return last;
2669   else
2670     return NULL_TREE;
2671 }
2672
2673
2674 /* Mark BB as the basic block holding statement T.  */
2675
2676 void
2677 set_bb_for_stmt (tree t, basic_block bb)
2678 {
2679   if (TREE_CODE (t) == PHI_NODE)
2680     PHI_BB (t) = bb;
2681   else if (TREE_CODE (t) == STATEMENT_LIST)
2682     {
2683       tree_stmt_iterator i;
2684       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2685         set_bb_for_stmt (tsi_stmt (i), bb);
2686     }
2687   else
2688     {
2689       stmt_ann_t ann = get_stmt_ann (t);
2690       ann->bb = bb;
2691
2692       /* If the statement is a label, add the label to block-to-labels map
2693         so that we can speed up edge creation for GOTO_EXPRs.  */
2694       if (TREE_CODE (t) == LABEL_EXPR)
2695         {
2696           int uid;
2697
2698           t = LABEL_EXPR_LABEL (t);
2699           uid = LABEL_DECL_UID (t);
2700           if (uid == -1)
2701             {
2702               unsigned old_len = VEC_length (basic_block, label_to_block_map);
2703               LABEL_DECL_UID (t) = uid = cfun->cfg->last_label_uid++;
2704               if (old_len <= (unsigned) uid)
2705                 {
2706                   unsigned new_len = 3 * uid / 2;
2707
2708                   VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
2709                                          new_len);
2710                 }
2711             }
2712           else
2713             /* We're moving an existing label.  Make sure that we've
2714                 removed it from the old block.  */
2715             gcc_assert (!bb
2716                         || !VEC_index (basic_block, label_to_block_map, uid));
2717           VEC_replace (basic_block, label_to_block_map, uid, bb);
2718         }
2719     }
2720 }
2721
2722 /* Faster version of set_bb_for_stmt that assume that statement is being moved
2723    from one basic block to another.  
2724    For BB splitting we can run into quadratic case, so performance is quite
2725    important and knowing that the tables are big enough, change_bb_for_stmt
2726    can inline as leaf function.  */
2727 static inline void
2728 change_bb_for_stmt (tree t, basic_block bb)
2729 {
2730   get_stmt_ann (t)->bb = bb;
2731   if (TREE_CODE (t) == LABEL_EXPR)
2732     VEC_replace (basic_block, label_to_block_map,
2733                  LABEL_DECL_UID (LABEL_EXPR_LABEL (t)), bb);
2734 }
2735
2736 /* Finds iterator for STMT.  */
2737
2738 extern block_stmt_iterator
2739 bsi_for_stmt (tree stmt)
2740 {
2741   block_stmt_iterator bsi;
2742
2743   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2744     if (bsi_stmt (bsi) == stmt)
2745       return bsi;
2746
2747   gcc_unreachable ();
2748 }
2749
2750 /* Mark statement T as modified, and update it.  */
2751 static inline void
2752 update_modified_stmts (tree t)
2753 {
2754   if (!ssa_operands_active ())
2755     return;
2756   if (TREE_CODE (t) == STATEMENT_LIST)
2757     {
2758       tree_stmt_iterator i;
2759       tree stmt;
2760       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2761         {
2762           stmt = tsi_stmt (i);
2763           update_stmt_if_modified (stmt);
2764         }
2765     }
2766   else
2767     update_stmt_if_modified (t);
2768 }
2769
2770 /* Insert statement (or statement list) T before the statement
2771    pointed-to by iterator I.  M specifies how to update iterator I
2772    after insertion (see enum bsi_iterator_update).  */
2773
2774 void
2775 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2776 {
2777   set_bb_for_stmt (t, i->bb);
2778   update_modified_stmts (t);
2779   tsi_link_before (&i->tsi, t, m);
2780 }
2781
2782
2783 /* Insert statement (or statement list) T after the statement
2784    pointed-to by iterator I.  M specifies how to update iterator I
2785    after insertion (see enum bsi_iterator_update).  */
2786
2787 void
2788 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2789 {
2790   set_bb_for_stmt (t, i->bb);
2791   update_modified_stmts (t);
2792   tsi_link_after (&i->tsi, t, m);
2793 }
2794
2795
2796 /* Remove the statement pointed to by iterator I.  The iterator is updated
2797    to the next statement.
2798
2799    When REMOVE_EH_INFO is true we remove the statement pointed to by
2800    iterator I from the EH tables.  Otherwise we do not modify the EH
2801    tables.
2802
2803    Generally, REMOVE_EH_INFO should be true when the statement is going to
2804    be removed from the IL and not reinserted elsewhere.  */
2805
2806 void
2807 bsi_remove (block_stmt_iterator *i, bool remove_eh_info)
2808 {
2809   tree t = bsi_stmt (*i);
2810   set_bb_for_stmt (t, NULL);
2811   delink_stmt_imm_use (t);
2812   tsi_delink (&i->tsi);
2813   mark_stmt_modified (t);
2814   if (remove_eh_info)
2815     {
2816       remove_stmt_from_eh_region (t);
2817       gimple_remove_stmt_histograms (cfun, t);
2818     }
2819 }
2820
2821
2822 /* Move the statement at FROM so it comes right after the statement at TO.  */
2823
2824 void
2825 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2826 {
2827   tree stmt = bsi_stmt (*from);
2828   bsi_remove (from, false);
2829   /* We must have BSI_NEW_STMT here, as bsi_move_after is sometimes used to
2830      move statements to an empty block.  */
2831   bsi_insert_after (to, stmt, BSI_NEW_STMT);
2832 }
2833
2834
2835 /* Move the statement at FROM so it comes right before the statement at TO.  */
2836
2837 void
2838 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2839 {
2840   tree stmt = bsi_stmt (*from);
2841   bsi_remove (from, false);
2842   /* For consistency with bsi_move_after, it might be better to have
2843      BSI_NEW_STMT here; however, that breaks several places that expect
2844      that TO does not change.  */
2845   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2846 }
2847
2848
2849 /* Move the statement at FROM to the end of basic block BB.  */
2850
2851 void
2852 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2853 {
2854   block_stmt_iterator last = bsi_last (bb);
2855
2856   /* Have to check bsi_end_p because it could be an empty block.  */
2857   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2858     bsi_move_before (from, &last);
2859   else
2860     bsi_move_after (from, &last);
2861 }
2862
2863
2864 /* Replace the contents of the statement pointed to by iterator BSI
2865    with STMT.  If UPDATE_EH_INFO is true, the exception handling
2866    information of the original statement is moved to the new statement.  */
2867
2868 void
2869 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
2870 {
2871   int eh_region;
2872   tree orig_stmt = bsi_stmt (*bsi);
2873
2874   if (stmt == orig_stmt)
2875     return;
2876   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2877   set_bb_for_stmt (stmt, bsi->bb);
2878
2879   /* Preserve EH region information from the original statement, if
2880      requested by the caller.  */
2881   if (update_eh_info)
2882     {
2883       eh_region = lookup_stmt_eh_region (orig_stmt);
2884       if (eh_region >= 0)
2885         {
2886           remove_stmt_from_eh_region (orig_stmt);
2887           add_stmt_to_eh_region (stmt, eh_region);
2888         }
2889     }
2890
2891   gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
2892   gimple_remove_stmt_histograms (cfun, orig_stmt);
2893   delink_stmt_imm_use (orig_stmt);
2894   *bsi_stmt_ptr (*bsi) = stmt;
2895   mark_stmt_modified (stmt);
2896   update_modified_stmts (stmt);
2897 }
2898
2899
2900 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2901    is made to place the statement in an existing basic block, but
2902    sometimes that isn't possible.  When it isn't possible, the edge is
2903    split and the statement is added to the new block.
2904
2905    In all cases, the returned *BSI points to the correct location.  The
2906    return value is true if insertion should be done after the location,
2907    or false if it should be done before the location.  If new basic block
2908    has to be created, it is stored in *NEW_BB.  */
2909
2910 static bool
2911 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2912                            basic_block *new_bb)
2913 {
2914   basic_block dest, src;
2915   tree tmp;
2916
2917   dest = e->dest;
2918  restart:
2919
2920   /* If the destination has one predecessor which has no PHI nodes,
2921      insert there.  Except for the exit block.
2922
2923      The requirement for no PHI nodes could be relaxed.  Basically we
2924      would have to examine the PHIs to prove that none of them used
2925      the value set by the statement we want to insert on E.  That
2926      hardly seems worth the effort.  */
2927   if (single_pred_p (dest)
2928       && ! phi_nodes (dest)
2929       && dest != EXIT_BLOCK_PTR)
2930     {
2931       *bsi = bsi_start (dest);
2932       if (bsi_end_p (*bsi))
2933         return true;
2934
2935       /* Make sure we insert after any leading labels.  */
2936       tmp = bsi_stmt (*bsi);
2937       while (TREE_CODE (tmp) == LABEL_EXPR)
2938         {
2939           bsi_next (bsi);
2940           if (bsi_end_p (*bsi))
2941             break;
2942           tmp = bsi_stmt (*bsi);
2943         }
2944
2945       if (bsi_end_p (*bsi))
2946         {
2947           *bsi = bsi_last (dest);
2948           return true;
2949         }
2950       else
2951         return false;
2952     }
2953
2954   /* If the source has one successor, the edge is not abnormal and
2955      the last statement does not end a basic block, insert there.
2956      Except for the entry block.  */
2957   src = e->src;
2958   if ((e->flags & EDGE_ABNORMAL) == 0
2959       && single_succ_p (src)
2960       && src != ENTRY_BLOCK_PTR)
2961     {
2962       *bsi = bsi_last (src);
2963       if (bsi_end_p (*bsi))
2964         return true;
2965
2966       tmp = bsi_stmt (*bsi);
2967       if (!stmt_ends_bb_p (tmp))
2968         return true;
2969
2970       /* Insert code just before returning the value.  We may need to decompose
2971          the return in the case it contains non-trivial operand.  */
2972       if (TREE_CODE (tmp) == RETURN_EXPR)
2973         {
2974           tree op = TREE_OPERAND (tmp, 0);
2975           if (op && !is_gimple_val (op))
2976             {
2977               gcc_assert (TREE_CODE (op) == GIMPLE_MODIFY_STMT);
2978               bsi_insert_before (bsi, op, BSI_NEW_STMT);
2979               TREE_OPERAND (tmp, 0) = GIMPLE_STMT_OPERAND (op, 0);
2980             }
2981           bsi_prev (bsi);
2982           return true;
2983         }
2984     }
2985
2986   /* Otherwise, create a new basic block, and split this edge.  */
2987   dest = split_edge (e);
2988   if (new_bb)
2989     *new_bb = dest;
2990   e = single_pred_edge (dest);
2991   goto restart;
2992 }
2993
2994
2995 /* This routine will commit all pending edge insertions, creating any new
2996    basic blocks which are necessary.  */
2997
2998 void
2999 bsi_commit_edge_inserts (void)
3000 {
3001   basic_block bb;
3002   edge e;
3003   edge_iterator ei;
3004
3005   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
3006
3007   FOR_EACH_BB (bb)
3008     FOR_EACH_EDGE (e, ei, bb->succs)
3009       bsi_commit_one_edge_insert (e, NULL);
3010 }
3011
3012
3013 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3014    to this block, otherwise set it to NULL.  */
3015
3016 void
3017 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3018 {
3019   if (new_bb)
3020     *new_bb = NULL;
3021   if (PENDING_STMT (e))
3022     {
3023       block_stmt_iterator bsi;
3024       tree stmt = PENDING_STMT (e);
3025
3026       PENDING_STMT (e) = NULL_TREE;
3027
3028       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3029         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3030       else
3031         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3032     }
3033 }
3034
3035
3036 /* Add STMT to the pending list of edge E.  No actual insertion is
3037    made until a call to bsi_commit_edge_inserts () is made.  */
3038
3039 void
3040 bsi_insert_on_edge (edge e, tree stmt)
3041 {
3042   append_to_statement_list (stmt, &PENDING_STMT (e));
3043 }
3044
3045 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
3046    block has to be created, it is returned.  */
3047
3048 basic_block
3049 bsi_insert_on_edge_immediate (edge e, tree stmt)
3050 {
3051   block_stmt_iterator bsi;
3052   basic_block new_bb = NULL;
3053
3054   gcc_assert (!PENDING_STMT (e));
3055
3056   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3057     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3058   else
3059     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3060
3061   return new_bb;
3062 }
3063
3064 /*---------------------------------------------------------------------------
3065              Tree specific functions for CFG manipulation
3066 ---------------------------------------------------------------------------*/
3067
3068 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3069
3070 static void
3071 reinstall_phi_args (edge new_edge, edge old_edge)
3072 {
3073   tree phi;
3074   edge_var_map_vector v;
3075   edge_var_map *vm;
3076   int i;
3077
3078   v = redirect_edge_var_map_vector (old_edge);
3079   if (!v)
3080     return;
3081
3082   for (i = 0, phi = phi_nodes (new_edge->dest);
3083        VEC_iterate (edge_var_map, v, i, vm) && phi;
3084        i++, phi = PHI_CHAIN (phi))
3085     {
3086       tree result = redirect_edge_var_map_result (vm);
3087       tree arg = redirect_edge_var_map_def (vm);
3088
3089       gcc_assert (result == PHI_RESULT (phi));
3090
3091       add_phi_arg (phi, arg, new_edge);
3092     }
3093
3094   redirect_edge_var_map_clear (old_edge);
3095 }
3096
3097 /* Returns the basic block after which the new basic block created
3098    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
3099    near its "logical" location.  This is of most help to humans looking
3100    at debugging dumps.  */
3101
3102 static basic_block
3103 split_edge_bb_loc (edge edge_in)
3104 {
3105   basic_block dest = edge_in->dest;
3106
3107   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3108     return edge_in->src;
3109   else
3110     return dest->prev_bb;
3111 }
3112
3113 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3114    Abort on abnormal edges.  */
3115
3116 static basic_block
3117 tree_split_edge (edge edge_in)
3118 {
3119   basic_block new_bb, after_bb, dest;
3120   edge new_edge, e;
3121
3122   /* Abnormal edges cannot be split.  */
3123   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3124
3125   dest = edge_in->dest;
3126
3127   after_bb = split_edge_bb_loc (edge_in);
3128
3129   new_bb = create_empty_bb (after_bb);
3130   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3131   new_bb->count = edge_in->count;
3132   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3133   new_edge->probability = REG_BR_PROB_BASE;
3134   new_edge->count = edge_in->count;
3135
3136   e = redirect_edge_and_branch (edge_in, new_bb);
3137   gcc_assert (e == edge_in);
3138   reinstall_phi_args (new_edge, e);
3139
3140   return new_bb;
3141 }
3142
3143 /* Callback for walk_tree, check that all elements with address taken are
3144    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3145    inside a PHI node.  */
3146
3147 static tree
3148 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3149 {
3150   tree t = *tp, x;
3151
3152   if (TYPE_P (t))
3153     *walk_subtrees = 0;
3154
3155   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3156 #define CHECK_OP(N, MSG) \
3157   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3158        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3159
3160   switch (TREE_CODE (t))
3161     {
3162     case SSA_NAME:
3163       if (SSA_NAME_IN_FREE_LIST (t))
3164         {
3165           error ("SSA name in freelist but still referenced");
3166           return *tp;
3167         }
3168       break;
3169
3170     case ASSERT_EXPR:
3171       x = fold (ASSERT_EXPR_COND (t));
3172       if (x == boolean_false_node)
3173         {
3174           error ("ASSERT_EXPR with an always-false condition");
3175           return *tp;
3176         }
3177       break;
3178
3179     case MODIFY_EXPR:
3180       gcc_unreachable ();
3181
3182     case GIMPLE_MODIFY_STMT:
3183       x = GIMPLE_STMT_OPERAND (t, 0);
3184       if (TREE_CODE (x) == BIT_FIELD_REF
3185           && is_gimple_reg (TREE_OPERAND (x, 0)))
3186         {
3187           error ("GIMPLE register modified with BIT_FIELD_REF");
3188           return t;
3189         }
3190       break;
3191
3192     case ADDR_EXPR:
3193       {
3194         bool old_constant;
3195         bool old_side_effects;
3196         bool new_constant;
3197         bool new_side_effects;
3198
3199         gcc_assert (is_gimple_address (t));
3200
3201         old_constant = TREE_CONSTANT (t);
3202         old_side_effects = TREE_SIDE_EFFECTS (t);
3203
3204         recompute_tree_invariant_for_addr_expr (t);
3205         new_side_effects = TREE_SIDE_EFFECTS (t);
3206         new_constant = TREE_CONSTANT (t);
3207
3208         if (old_constant != new_constant)
3209           {
3210             error ("constant not recomputed when ADDR_EXPR changed");
3211             return t;
3212           }
3213         if (old_side_effects != new_side_effects)
3214           {
3215             error ("side effects not recomputed when ADDR_EXPR changed");
3216             return t;
3217           }
3218
3219         /* Skip any references (they will be checked when we recurse down the
3220            tree) and ensure that any variable used as a prefix is marked
3221            addressable.  */
3222         for (x = TREE_OPERAND (t, 0);
3223              handled_component_p (x);
3224              x = TREE_OPERAND (x, 0))
3225           ;
3226
3227         if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3228           return NULL;
3229         if (!TREE_ADDRESSABLE (x))
3230           {
3231             error ("address taken, but ADDRESSABLE bit not set");
3232             return x;
3233           }
3234
3235         break;
3236       }
3237
3238     case COND_EXPR:
3239       x = COND_EXPR_COND (t);
3240       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
3241         {
3242           error ("non-integral used in condition");
3243           return x;
3244         }
3245       if (!is_gimple_condexpr (x))
3246         {
3247           error ("invalid conditional operand");
3248           return x;
3249         }
3250       break;
3251
3252     case NON_LVALUE_EXPR:
3253         gcc_unreachable ();
3254
3255     CASE_CONVERT:
3256     case FIX_TRUNC_EXPR:
3257     case FLOAT_EXPR:
3258     case NEGATE_EXPR:
3259     case ABS_EXPR:
3260     case BIT_NOT_EXPR:
3261     case TRUTH_NOT_EXPR:
3262       CHECK_OP (0, "invalid operand to unary operator");
3263       break;
3264
3265     case REALPART_EXPR:
3266     case IMAGPART_EXPR:
3267     case COMPONENT_REF:
3268     case ARRAY_REF:
3269     case ARRAY_RANGE_REF:
3270     case BIT_FIELD_REF:
3271     case VIEW_CONVERT_EXPR:
3272       /* We have a nest of references.  Verify that each of the operands
3273          that determine where to reference is either a constant or a variable,
3274          verify that the base is valid, and then show we've already checked
3275          the subtrees.  */
3276       while (handled_component_p (t))
3277         {
3278           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3279             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3280           else if (TREE_CODE (t) == ARRAY_REF
3281                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3282             {
3283               CHECK_OP (1, "invalid array index");
3284               if (TREE_OPERAND (t, 2))
3285                 CHECK_OP (2, "invalid array lower bound");
3286               if (TREE_OPERAND (t, 3))
3287                 CHECK_OP (3, "invalid array stride");
3288             }
3289           else if (TREE_CODE (t) == BIT_FIELD_REF)
3290             {
3291               if (!host_integerp (TREE_OPERAND (t, 1), 1)
3292                   || !host_integerp (TREE_OPERAND (t, 2), 1))
3293                 {
3294                   error ("invalid position or size operand to BIT_FIELD_REF");
3295                   return t;
3296                 }
3297               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
3298                        && (TYPE_PRECISION (TREE_TYPE (t))
3299                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3300                 {
3301                   error ("integral result type precision does not match "
3302                          "field size of BIT_FIELD_REF");
3303                   return t;
3304                 }
3305               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
3306                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
3307                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3308                 {
3309                   error ("mode precision of non-integral result does not "
3310                          "match field size of BIT_FIELD_REF");
3311                   return t;
3312                 }
3313             }
3314
3315           t = TREE_OPERAND (t, 0);
3316         }
3317
3318       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
3319         {
3320           error ("invalid reference prefix");
3321           return t;
3322         }
3323       *walk_subtrees = 0;
3324       break;
3325     case PLUS_EXPR:
3326     case MINUS_EXPR:
3327       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3328          POINTER_PLUS_EXPR. */
3329       if (POINTER_TYPE_P (TREE_TYPE (t)))
3330         {
3331           error ("invalid operand to plus/minus, type is a pointer");
3332           return t;
3333         }
3334       CHECK_OP (0, "invalid operand to binary operator");
3335       CHECK_OP (1, "invalid operand to binary operator");
3336       break;
3337
3338     case POINTER_PLUS_EXPR:
3339       /* Check to make sure the first operand is a pointer or reference type. */
3340       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3341         {
3342           error ("invalid operand to pointer plus, first operand is not a pointer");
3343           return t;
3344         }
3345       /* Check to make sure the second operand is an integer with type of
3346          sizetype.  */
3347       if (!useless_type_conversion_p (sizetype,
3348                                      TREE_TYPE (TREE_OPERAND (t, 1))))
3349         {
3350           error ("invalid operand to pointer plus, second operand is not an "
3351                  "integer with type of sizetype.");
3352           return t;
3353         }
3354       /* FALLTHROUGH */
3355     case LT_EXPR:
3356     case LE_EXPR:
3357     case GT_EXPR:
3358     case GE_EXPR:
3359     case EQ_EXPR:
3360     case NE_EXPR:
3361     case UNORDERED_EXPR:
3362     case ORDERED_EXPR:
3363     case UNLT_EXPR:
3364     case UNLE_EXPR:
3365     case UNGT_EXPR:
3366     case UNGE_EXPR:
3367     case UNEQ_EXPR:
3368     case LTGT_EXPR:
3369     case MULT_EXPR:
3370     case TRUNC_DIV_EXPR:
3371     case CEIL_DIV_EXPR:
3372     case FLOOR_DIV_EXPR:
3373     case ROUND_DIV_EXPR:
3374     case TRUNC_MOD_EXPR:
3375     case CEIL_MOD_EXPR:
3376     case FLOOR_MOD_EXPR:
3377     case ROUND_MOD_EXPR:
3378     case RDIV_EXPR:
3379     case EXACT_DIV_EXPR:
3380     case MIN_EXPR:
3381     case MAX_EXPR:
3382     case LSHIFT_EXPR:
3383     case RSHIFT_EXPR:
3384     case LROTATE_EXPR:
3385     case RROTATE_EXPR:
3386     case BIT_IOR_EXPR:
3387     case BIT_XOR_EXPR:
3388     case BIT_AND_EXPR:
3389       CHECK_OP (0, "invalid operand to binary operator");
3390       CHECK_OP (1, "invalid operand to binary operator");
3391       break;
3392
3393     case CONSTRUCTOR:
3394       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3395         *walk_subtrees = 0;
3396       break;
3397
3398     default:
3399       break;
3400     }
3401   return NULL;
3402
3403 #undef CHECK_OP
3404 }
3405
3406 /* Verifies if EXPR is a valid GIMPLE unary expression.  Returns true
3407    if there is an error, otherwise false.  */
3408
3409 static bool
3410 verify_gimple_unary_expr (const_tree expr)
3411 {
3412   tree op = TREE_OPERAND (expr, 0);
3413   tree type = TREE_TYPE (expr);
3414
3415   if (!is_gimple_val (op))
3416     {
3417       error ("invalid operand in unary expression");
3418       return true;
3419     }
3420
3421   /* For general unary expressions we have the operations type
3422      as the effective type the operation is carried out on.  So all
3423      we need to require is that the operand is trivially convertible
3424      to that type.  */
3425   if (!useless_type_conversion_p (type, TREE_TYPE (op)))
3426     {
3427       error ("type mismatch in unary expression");
3428       debug_generic_expr (type);
3429       debug_generic_expr (TREE_TYPE (op));
3430       return true;
3431     }
3432
3433   return false;
3434 }
3435
3436 /* Verifies if EXPR is a valid GIMPLE binary expression.  Returns true
3437    if there is an error, otherwise false.  */
3438
3439 static bool
3440 verify_gimple_binary_expr (const_tree expr)
3441 {
3442   tree op0 = TREE_OPERAND (expr, 0);
3443   tree op1 = TREE_OPERAND (expr, 1);
3444   tree type = TREE_TYPE (expr);
3445
3446   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3447     {
3448       error ("invalid operands in binary expression");
3449       return true;
3450     }
3451
3452   /* For general binary expressions we have the operations type
3453      as the effective type the operation is carried out on.  So all
3454      we need to require is that both operands are trivially convertible
3455      to that type.  */
3456   if (!useless_type_conversion_p (type, TREE_TYPE (op0))
3457       || !useless_type_conversion_p (type, TREE_TYPE (op1)))
3458     {
3459       error ("type mismatch in binary expression");
3460       debug_generic_stmt (type);
3461       debug_generic_stmt (TREE_TYPE (op0));
3462       debug_generic_stmt (TREE_TYPE (op1));
3463       return true;
3464     }
3465
3466   return false;
3467 }
3468
3469 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3470    Returns true if there is an error, otherwise false.  */
3471
3472 static bool
3473 verify_gimple_min_lval (tree expr)
3474 {
3475   tree op;
3476
3477   if (is_gimple_id (expr))
3478     return false;
3479
3480   if (TREE_CODE (expr) != INDIRECT_REF
3481       && TREE_CODE (expr) != ALIGN_INDIRECT_REF
3482       && TREE_CODE (expr) != MISALIGNED_INDIRECT_REF)
3483     {
3484       error ("invalid expression for min lvalue");
3485       return true;
3486     }
3487
3488   op = TREE_OPERAND (expr, 0);
3489   if (!is_gimple_val (op))
3490     {
3491       error ("invalid operand in indirect reference");
3492       debug_generic_stmt (op);
3493       return true;
3494     }
3495   if (!useless_type_conversion_p (TREE_TYPE (expr),
3496                                   TREE_TYPE (TREE_TYPE (op))))
3497     {
3498       error ("type mismatch in indirect reference");
3499       debug_generic_stmt (TREE_TYPE (expr));
3500       debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3501       return true;
3502     }
3503
3504   return false;
3505 }
3506
3507 /* Verify if EXPR is a valid GIMPLE reference expression.  Returns true
3508    if there is an error, otherwise false.  */
3509
3510 static bool
3511 verify_gimple_reference (tree expr)
3512 {
3513   while (handled_component_p (expr))
3514     {
3515       tree op = TREE_OPERAND (expr, 0);
3516
3517       if (TREE_CODE (expr) == ARRAY_REF
3518           || TREE_CODE (expr) == ARRAY_RANGE_REF)
3519         {
3520           if (!is_gimple_val (TREE_OPERAND (expr, 1))
3521               || (TREE_OPERAND (expr, 2)
3522                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
3523               || (TREE_OPERAND (expr, 3)
3524                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
3525             {
3526               error ("invalid operands to array reference");
3527               debug_generic_stmt (expr);
3528               return true;
3529             }
3530         }
3531
3532       /* Verify if the reference array element types are compatible.  */
3533       if (TREE_CODE (expr) == ARRAY_REF
3534           && !useless_type_conversion_p (TREE_TYPE (expr),
3535                                          TREE_TYPE (TREE_TYPE (op))))
3536         {
3537           error ("type mismatch in array reference");
3538           debug_generic_stmt (TREE_TYPE (expr));
3539           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3540           return true;
3541         }
3542       if (TREE_CODE (expr) == ARRAY_RANGE_REF
3543           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3544                                          TREE_TYPE (TREE_TYPE (op))))
3545         {
3546           error ("type mismatch in array range reference");
3547           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3548           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3549           return true;
3550         }
3551
3552       if ((TREE_CODE (expr) == REALPART_EXPR
3553            || TREE_CODE (expr) == IMAGPART_EXPR)
3554           && !useless_type_conversion_p (TREE_TYPE (expr),
3555                                          TREE_TYPE (TREE_TYPE (op))))
3556         {
3557           error ("type mismatch in real/imagpart reference");
3558           debug_generic_stmt (TREE_TYPE (expr));
3559           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3560           return true;
3561         }
3562
3563       if (TREE_CODE (expr) == COMPONENT_REF
3564           && !useless_type_conversion_p (TREE_TYPE (expr),
3565                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3566         {
3567           error ("type mismatch in component reference");
3568           debug_generic_stmt (TREE_TYPE (expr));
3569           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3570           return true;
3571         }
3572
3573       /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3574          is nothing to verify.  Gross mismatches at most invoke
3575          undefined behavior.  */
3576
3577       expr = op;
3578     }
3579
3580   return verify_gimple_min_lval (expr);
3581 }
3582
3583 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3584    list of pointer-to types that is trivially convertible to DEST.  */
3585
3586 static bool
3587 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3588 {
3589   tree src;
3590
3591   if (!TYPE_POINTER_TO (src_obj))
3592     return true;
3593
3594   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3595     if (useless_type_conversion_p (dest, src))
3596       return true;
3597
3598   return false;
3599 }
3600
3601 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3602    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3603
3604 static bool
3605 valid_fixed_convert_types_p (tree type1, tree type2)
3606 {
3607   return (FIXED_POINT_TYPE_P (type1)
3608           && (INTEGRAL_TYPE_P (type2)
3609               || SCALAR_FLOAT_TYPE_P (type2)
3610               || FIXED_POINT_TYPE_P (type2)));
3611 }
3612
3613 /* Verify the GIMPLE expression EXPR.  Returns true if there is an
3614    error, otherwise false.  */
3615
3616 static bool
3617 verify_gimple_expr (tree expr)
3618 {
3619   tree type = TREE_TYPE (expr);
3620
3621   if (is_gimple_val (expr))
3622     return false;
3623
3624   /* Special codes we cannot handle via their class.  */
3625   switch (TREE_CODE (expr))
3626     {
3627     CASE_CONVERT:
3628       {
3629         tree op = TREE_OPERAND (expr, 0);
3630         if (!is_gimple_val (op))
3631           {
3632             error ("invalid operand in conversion");
3633             return true;
3634           }
3635
3636         /* Allow conversions between integral types and between
3637            pointer types.  */
3638         if ((INTEGRAL_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3639             || (POINTER_TYPE_P (type) && POINTER_TYPE_P (TREE_TYPE (op))))
3640           return false;
3641
3642         /* Allow conversions between integral types and pointers only if
3643            there is no sign or zero extension involved.  */
3644         if (((POINTER_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3645              || (POINTER_TYPE_P (TREE_TYPE (op)) && INTEGRAL_TYPE_P (type)))
3646             && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op)))
3647           return false;
3648