OSDN Git Service

PR middle-end/27328
[pf3gnuchains/gcc-fork.git] / gcc / tree-cfg.c
1 /* Control flow functions for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
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 2, 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 COPYING.  If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA.  */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "output.h"
33 #include "flags.h"
34 #include "function.h"
35 #include "expr.h"
36 #include "ggc.h"
37 #include "langhooks.h"
38 #include "diagnostic.h"
39 #include "tree-flow.h"
40 #include "timevar.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
43 #include "toplev.h"
44 #include "except.h"
45 #include "cfgloop.h"
46 #include "cfglayout.h"
47 #include "hashtab.h"
48 #include "tree-ssa-propagate.h"
49
50 /* This file contains functions for building the Control Flow Graph (CFG)
51    for a function tree.  */
52
53 /* Local declarations.  */
54
55 /* Initial capacity for the basic block array.  */
56 static const int initial_cfg_capacity = 20;
57
58 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
59    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
60    via their TREE_CHAIN field, which we clear after we're done with the
61    hash table to prevent problems with duplication of SWITCH_EXPRs.
62
63    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
64    update the case vector in response to edge redirections.
65
66    Right now this table is set up and torn down at key points in the
67    compilation process.  It would be nice if we could make the table
68    more persistent.  The key is getting notification of changes to
69    the CFG (particularly edge removal, creation and redirection).  */
70
71 struct edge_to_cases_elt
72 {
73   /* The edge itself.  Necessary for hashing and equality tests.  */
74   edge e;
75
76   /* The case labels associated with this edge.  We link these up via
77      their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
78      when we destroy the hash table.  This prevents problems when copying
79      SWITCH_EXPRs.  */
80   tree case_labels;
81 };
82
83 static htab_t edge_to_cases;
84
85 /* CFG statistics.  */
86 struct cfg_stats_d
87 {
88   long num_merged_labels;
89 };
90
91 static struct cfg_stats_d cfg_stats;
92
93 /* Nonzero if we found a computed goto while building basic blocks.  */
94 static bool found_computed_goto;
95
96 /* Basic blocks and flowgraphs.  */
97 static basic_block create_bb (void *, void *, basic_block);
98 static void make_blocks (tree);
99 static void factor_computed_gotos (void);
100
101 /* Edges.  */
102 static void make_edges (void);
103 static void make_cond_expr_edges (basic_block);
104 static void make_switch_expr_edges (basic_block);
105 static void make_goto_expr_edges (basic_block);
106 static edge tree_redirect_edge_and_branch (edge, basic_block);
107 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
108 static unsigned int split_critical_edges (void);
109
110 /* Various helpers.  */
111 static inline bool stmt_starts_bb_p (tree, tree);
112 static int tree_verify_flow_info (void);
113 static void tree_make_forwarder_block (edge);
114 static void tree_cfg2vcg (FILE *);
115
116 /* Flowgraph optimization and cleanup.  */
117 static void tree_merge_blocks (basic_block, basic_block);
118 static bool tree_can_merge_blocks_p (basic_block, basic_block);
119 static void remove_bb (basic_block);
120 static edge find_taken_edge_computed_goto (basic_block, tree);
121 static edge find_taken_edge_cond_expr (basic_block, tree);
122 static edge find_taken_edge_switch_expr (basic_block, tree);
123 static tree find_case_label_for_value (tree, tree);
124
125 void
126 init_empty_tree_cfg (void)
127 {
128   /* Initialize the basic block array.  */
129   init_flow ();
130   profile_status = PROFILE_ABSENT;
131   n_basic_blocks = NUM_FIXED_BLOCKS;
132   last_basic_block = NUM_FIXED_BLOCKS;
133   basic_block_info = VEC_alloc (basic_block, gc, initial_cfg_capacity);
134   VEC_safe_grow (basic_block, gc, basic_block_info, initial_cfg_capacity);
135   memset (VEC_address (basic_block, basic_block_info), 0,
136           sizeof (basic_block) * initial_cfg_capacity);
137
138   /* Build a mapping of labels to their associated blocks.  */
139   label_to_block_map = VEC_alloc (basic_block, gc, initial_cfg_capacity);
140   VEC_safe_grow (basic_block, gc, label_to_block_map, initial_cfg_capacity);
141   memset (VEC_address (basic_block, label_to_block_map),
142           0, sizeof (basic_block) * initial_cfg_capacity);
143
144   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
145   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
146   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
147   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
148 }
149
150 /*---------------------------------------------------------------------------
151                               Create basic blocks
152 ---------------------------------------------------------------------------*/
153
154 /* Entry point to the CFG builder for trees.  TP points to the list of
155    statements to be added to the flowgraph.  */
156
157 static void
158 build_tree_cfg (tree *tp)
159 {
160   /* Register specific tree functions.  */
161   tree_register_cfg_hooks ();
162
163   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
164
165   init_empty_tree_cfg ();
166
167   found_computed_goto = 0;
168   make_blocks (*tp);
169
170   /* Computed gotos are hell to deal with, especially if there are
171      lots of them with a large number of destinations.  So we factor
172      them to a common computed goto location before we build the
173      edge list.  After we convert back to normal form, we will un-factor
174      the computed gotos since factoring introduces an unwanted jump.  */
175   if (found_computed_goto)
176     factor_computed_gotos ();
177
178   /* Make sure there is always at least one block, even if it's empty.  */
179   if (n_basic_blocks == NUM_FIXED_BLOCKS)
180     create_empty_bb (ENTRY_BLOCK_PTR);
181
182   /* Adjust the size of the array.  */
183   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
184     {
185       size_t old_size = VEC_length (basic_block, basic_block_info);
186       basic_block *p;
187       VEC_safe_grow (basic_block, gc, basic_block_info, n_basic_blocks);
188       p = VEC_address (basic_block, basic_block_info);
189       memset (&p[old_size], 0,
190               sizeof (basic_block) * (n_basic_blocks - old_size));
191     }
192
193   /* To speed up statement iterator walks, we first purge dead labels.  */
194   cleanup_dead_labels ();
195
196   /* Group case nodes to reduce the number of edges.
197      We do this after cleaning up dead labels because otherwise we miss
198      a lot of obvious case merging opportunities.  */
199   group_case_labels ();
200
201   /* Create the edges of the flowgraph.  */
202   make_edges ();
203
204   /* Debugging dumps.  */
205
206   /* Write the flowgraph to a VCG file.  */
207   {
208     int local_dump_flags;
209     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
210     if (vcg_file)
211       {
212         tree_cfg2vcg (vcg_file);
213         dump_end (TDI_vcg, vcg_file);
214       }
215   }
216
217 #ifdef ENABLE_CHECKING
218   verify_stmts ();
219 #endif
220
221   /* Dump a textual representation of the flowgraph.  */
222   if (dump_file)
223     dump_tree_cfg (dump_file, dump_flags);
224 }
225
226 static unsigned int
227 execute_build_cfg (void)
228 {
229   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
230   return 0;
231 }
232
233 struct tree_opt_pass pass_build_cfg =
234 {
235   "cfg",                                /* name */
236   NULL,                                 /* gate */
237   execute_build_cfg,                    /* execute */
238   NULL,                                 /* sub */
239   NULL,                                 /* next */
240   0,                                    /* static_pass_number */
241   TV_TREE_CFG,                          /* tv_id */
242   PROP_gimple_leh,                      /* properties_required */
243   PROP_cfg,                             /* properties_provided */
244   0,                                    /* properties_destroyed */
245   0,                                    /* todo_flags_start */
246   TODO_verify_stmts,                    /* todo_flags_finish */
247   0                                     /* letter */
248 };
249
250 /* Search the CFG for any computed gotos.  If found, factor them to a 
251    common computed goto site.  Also record the location of that site so
252    that we can un-factor the gotos after we have converted back to 
253    normal form.  */
254
255 static void
256 factor_computed_gotos (void)
257 {
258   basic_block bb;
259   tree factored_label_decl = NULL;
260   tree var = NULL;
261   tree factored_computed_goto_label = NULL;
262   tree factored_computed_goto = NULL;
263
264   /* We know there are one or more computed gotos in this function.
265      Examine the last statement in each basic block to see if the block
266      ends with a computed goto.  */
267         
268   FOR_EACH_BB (bb)
269     {
270       block_stmt_iterator bsi = bsi_last (bb);
271       tree last;
272
273       if (bsi_end_p (bsi))
274         continue;
275       last = bsi_stmt (bsi);
276
277       /* Ignore the computed goto we create when we factor the original
278          computed gotos.  */
279       if (last == factored_computed_goto)
280         continue;
281
282       /* If the last statement is a computed goto, factor it.  */
283       if (computed_goto_p (last))
284         {
285           tree assignment;
286
287           /* The first time we find a computed goto we need to create
288              the factored goto block and the variable each original
289              computed goto will use for their goto destination.  */
290           if (! factored_computed_goto)
291             {
292               basic_block new_bb = create_empty_bb (bb);
293               block_stmt_iterator new_bsi = bsi_start (new_bb);
294
295               /* Create the destination of the factored goto.  Each original
296                  computed goto will put its desired destination into this
297                  variable and jump to the label we create immediately
298                  below.  */
299               var = create_tmp_var (ptr_type_node, "gotovar");
300
301               /* Build a label for the new block which will contain the
302                  factored computed goto.  */
303               factored_label_decl = create_artificial_label ();
304               factored_computed_goto_label
305                 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
306               bsi_insert_after (&new_bsi, factored_computed_goto_label,
307                                 BSI_NEW_STMT);
308
309               /* Build our new computed goto.  */
310               factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
311               bsi_insert_after (&new_bsi, factored_computed_goto,
312                                 BSI_NEW_STMT);
313             }
314
315           /* Copy the original computed goto's destination into VAR.  */
316           assignment = build2 (MODIFY_EXPR, ptr_type_node,
317                                var, GOTO_DESTINATION (last));
318           bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
319
320           /* And re-vector the computed goto to the new destination.  */
321           GOTO_DESTINATION (last) = factored_label_decl;
322         }
323     }
324 }
325
326
327 /* Build a flowgraph for the statement_list STMT_LIST.  */
328
329 static void
330 make_blocks (tree stmt_list)
331 {
332   tree_stmt_iterator i = tsi_start (stmt_list);
333   tree stmt = NULL;
334   bool start_new_block = true;
335   bool first_stmt_of_list = true;
336   basic_block bb = ENTRY_BLOCK_PTR;
337
338   while (!tsi_end_p (i))
339     {
340       tree prev_stmt;
341
342       prev_stmt = stmt;
343       stmt = tsi_stmt (i);
344
345       /* If the statement starts a new basic block or if we have determined
346          in a previous pass that we need to create a new block for STMT, do
347          so now.  */
348       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
349         {
350           if (!first_stmt_of_list)
351             stmt_list = tsi_split_statement_list_before (&i);
352           bb = create_basic_block (stmt_list, NULL, bb);
353           start_new_block = false;
354         }
355
356       /* Now add STMT to BB and create the subgraphs for special statement
357          codes.  */
358       set_bb_for_stmt (stmt, bb);
359
360       if (computed_goto_p (stmt))
361         found_computed_goto = true;
362
363       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
364          next iteration.  */
365       if (stmt_ends_bb_p (stmt))
366         start_new_block = true;
367
368       tsi_next (&i);
369       first_stmt_of_list = false;
370     }
371 }
372
373
374 /* Create and return a new empty basic block after bb AFTER.  */
375
376 static basic_block
377 create_bb (void *h, void *e, basic_block after)
378 {
379   basic_block bb;
380
381   gcc_assert (!e);
382
383   /* Create and initialize a new basic block.  Since alloc_block uses
384      ggc_alloc_cleared to allocate a basic block, we do not have to
385      clear the newly allocated basic block here.  */
386   bb = alloc_block ();
387
388   bb->index = last_basic_block;
389   bb->flags = BB_NEW;
390   bb->stmt_list = h ? (tree) h : alloc_stmt_list ();
391
392   /* Add the new block to the linked list of blocks.  */
393   link_block (bb, after);
394
395   /* Grow the basic block array if needed.  */
396   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
397     {
398       size_t old_size = VEC_length (basic_block, basic_block_info);
399       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
400       basic_block *p;
401       VEC_safe_grow (basic_block, gc, basic_block_info, new_size);
402       p = VEC_address (basic_block, basic_block_info);
403       memset (&p[old_size], 0, sizeof (basic_block) * (new_size - old_size));
404     }
405
406   /* Add the newly created block to the array.  */
407   SET_BASIC_BLOCK (last_basic_block, bb);
408
409   n_basic_blocks++;
410   last_basic_block++;
411
412   return bb;
413 }
414
415
416 /*---------------------------------------------------------------------------
417                                  Edge creation
418 ---------------------------------------------------------------------------*/
419
420 /* Fold COND_EXPR_COND of each COND_EXPR.  */
421
422 void
423 fold_cond_expr_cond (void)
424 {
425   basic_block bb;
426
427   FOR_EACH_BB (bb)
428     {
429       tree stmt = last_stmt (bb);
430
431       if (stmt
432           && TREE_CODE (stmt) == COND_EXPR)
433         {
434           tree cond = fold (COND_EXPR_COND (stmt));
435           if (integer_zerop (cond))
436             COND_EXPR_COND (stmt) = boolean_false_node;
437           else if (integer_onep (cond))
438             COND_EXPR_COND (stmt) = boolean_true_node;
439         }
440     }
441 }
442
443 /* Join all the blocks in the flowgraph.  */
444
445 static void
446 make_edges (void)
447 {
448   basic_block bb;
449   struct omp_region *cur_region = NULL;
450
451   /* Create an edge from entry to the first block with executable
452      statements in it.  */
453   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
454
455   /* Traverse the basic block array placing edges.  */
456   FOR_EACH_BB (bb)
457     {
458       tree last = last_stmt (bb);
459       bool fallthru;
460
461       if (last)
462         {
463           enum tree_code code = TREE_CODE (last);
464           switch (code)
465             {
466             case GOTO_EXPR:
467               make_goto_expr_edges (bb);
468               fallthru = false;
469               break;
470             case RETURN_EXPR:
471               make_edge (bb, EXIT_BLOCK_PTR, 0);
472               fallthru = false;
473               break;
474             case COND_EXPR:
475               make_cond_expr_edges (bb);
476               fallthru = false;
477               break;
478             case SWITCH_EXPR:
479               make_switch_expr_edges (bb);
480               fallthru = false;
481               break;
482             case RESX_EXPR:
483               make_eh_edges (last);
484               fallthru = false;
485               break;
486
487             case CALL_EXPR:
488               /* If this function receives a nonlocal goto, then we need to
489                  make edges from this call site to all the nonlocal goto
490                  handlers.  */
491               if (TREE_SIDE_EFFECTS (last)
492                   && current_function_has_nonlocal_label)
493                 make_goto_expr_edges (bb);
494
495               /* If this statement has reachable exception handlers, then
496                  create abnormal edges to them.  */
497               make_eh_edges (last);
498
499               /* Some calls are known not to return.  */
500               fallthru = !(call_expr_flags (last) & ECF_NORETURN);
501               break;
502
503             case MODIFY_EXPR:
504               if (is_ctrl_altering_stmt (last))
505                 {
506                   /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the
507                      CALL_EXPR may have an abnormal edge.  Search the RHS for
508                      this case and create any required edges.  */
509                   tree op = get_call_expr_in (last);
510                   if (op && TREE_SIDE_EFFECTS (op)
511                       && current_function_has_nonlocal_label)
512                     make_goto_expr_edges (bb);
513
514                   make_eh_edges (last);
515                 }
516               fallthru = true;
517               break;
518
519             case OMP_PARALLEL:
520             case OMP_FOR:
521             case OMP_SINGLE:
522             case OMP_MASTER:
523             case OMP_ORDERED:
524             case OMP_CRITICAL:
525             case OMP_SECTION:
526               cur_region = new_omp_region (bb, code, cur_region);
527               fallthru = true;
528               break;
529
530             case OMP_SECTIONS:
531               cur_region = new_omp_region (bb, code, cur_region);
532               fallthru = false;
533               break;
534
535             case OMP_RETURN:
536               /* In the case of an OMP_SECTION, the edge will go somewhere
537                  other than the next block.  This will be created later.  */
538               cur_region->exit = bb;
539               fallthru = cur_region->type != OMP_SECTION;
540               cur_region = cur_region->outer;
541               break;
542
543             case OMP_CONTINUE:
544               cur_region->cont = bb;
545               switch (cur_region->type)
546                 {
547                 case OMP_FOR:
548                   /* ??? Technically there should be a some sort of loopback
549                      edge here, but it goes to a block that doesn't exist yet,
550                      and without it, updating the ssa form would be a real
551                      bear.  Fortunately, we don't yet do ssa before expanding
552                      these nodes.  */
553                   break;
554
555                 case OMP_SECTIONS:
556                   /* Wire up the edges into and out of the nested sections.  */
557                   /* ??? Similarly wrt loopback.  */
558                   {
559                     struct omp_region *i;
560                     for (i = cur_region->inner; i ; i = i->next)
561                       {
562                         gcc_assert (i->type == OMP_SECTION);
563                         make_edge (cur_region->entry, i->entry, 0);
564                         make_edge (i->exit, bb, EDGE_FALLTHRU);
565                       }
566                   }
567                   break;
568                      
569                 default:
570                   gcc_unreachable ();
571                 }
572               fallthru = true;
573               break;
574
575             default:
576               gcc_assert (!stmt_ends_bb_p (last));
577               fallthru = true;
578             }
579         }
580       else
581         fallthru = true;
582
583       if (fallthru)
584         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
585     }
586
587   if (root_omp_region)
588     free_omp_regions ();
589
590   /* Fold COND_EXPR_COND of each COND_EXPR.  */
591   fold_cond_expr_cond ();
592
593   /* Clean up the graph and warn for unreachable code.  */
594   cleanup_tree_cfg ();
595 }
596
597
598 /* Create the edges for a COND_EXPR starting at block BB.
599    At this point, both clauses must contain only simple gotos.  */
600
601 static void
602 make_cond_expr_edges (basic_block bb)
603 {
604   tree entry = last_stmt (bb);
605   basic_block then_bb, else_bb;
606   tree then_label, else_label;
607   edge e;
608
609   gcc_assert (entry);
610   gcc_assert (TREE_CODE (entry) == COND_EXPR);
611
612   /* Entry basic blocks for each component.  */
613   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
614   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
615   then_bb = label_to_block (then_label);
616   else_bb = label_to_block (else_label);
617
618   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
619 #ifdef USE_MAPPED_LOCATION
620   e->goto_locus = EXPR_LOCATION (COND_EXPR_THEN (entry));
621 #else
622   e->goto_locus = EXPR_LOCUS (COND_EXPR_THEN (entry));
623 #endif
624   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
625   if (e)
626     {
627 #ifdef USE_MAPPED_LOCATION
628       e->goto_locus = EXPR_LOCATION (COND_EXPR_ELSE (entry));
629 #else
630       e->goto_locus = EXPR_LOCUS (COND_EXPR_ELSE (entry));
631 #endif
632     }
633 }
634
635 /* Hashing routine for EDGE_TO_CASES.  */
636
637 static hashval_t
638 edge_to_cases_hash (const void *p)
639 {
640   edge e = ((struct edge_to_cases_elt *)p)->e;
641
642   /* Hash on the edge itself (which is a pointer).  */
643   return htab_hash_pointer (e);
644 }
645
646 /* Equality routine for EDGE_TO_CASES, edges are unique, so testing
647    for equality is just a pointer comparison.  */
648
649 static int
650 edge_to_cases_eq (const void *p1, const void *p2)
651 {
652   edge e1 = ((struct edge_to_cases_elt *)p1)->e;
653   edge e2 = ((struct edge_to_cases_elt *)p2)->e;
654
655   return e1 == e2;
656 }
657
658 /* Called for each element in the hash table (P) as we delete the
659    edge to cases hash table.
660
661    Clear all the TREE_CHAINs to prevent problems with copying of 
662    SWITCH_EXPRs and structure sharing rules, then free the hash table
663    element.  */
664
665 static void
666 edge_to_cases_cleanup (void *p)
667 {
668   struct edge_to_cases_elt *elt = (struct edge_to_cases_elt *) p;
669   tree t, next;
670
671   for (t = elt->case_labels; t; t = next)
672     {
673       next = TREE_CHAIN (t);
674       TREE_CHAIN (t) = NULL;
675     }
676   free (p);
677 }
678
679 /* Start recording information mapping edges to case labels.  */
680
681 void
682 start_recording_case_labels (void)
683 {
684   gcc_assert (edge_to_cases == NULL);
685
686   edge_to_cases = htab_create (37,
687                                edge_to_cases_hash,
688                                edge_to_cases_eq,
689                                edge_to_cases_cleanup);
690 }
691
692 /* Return nonzero if we are recording information for case labels.  */
693
694 static bool
695 recording_case_labels_p (void)
696 {
697   return (edge_to_cases != NULL);
698 }
699
700 /* Stop recording information mapping edges to case labels and
701    remove any information we have recorded.  */
702 void
703 end_recording_case_labels (void)
704 {
705   htab_delete (edge_to_cases);
706   edge_to_cases = NULL;
707 }
708
709 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
710
711 static void
712 record_switch_edge (edge e, tree case_label)
713 {
714   struct edge_to_cases_elt *elt;
715   void **slot;
716
717   /* Build a hash table element so we can see if E is already
718      in the table.  */
719   elt = XNEW (struct edge_to_cases_elt);
720   elt->e = e;
721   elt->case_labels = case_label;
722
723   slot = htab_find_slot (edge_to_cases, elt, INSERT);
724
725   if (*slot == NULL)
726     {
727       /* E was not in the hash table.  Install E into the hash table.  */
728       *slot = (void *)elt;
729     }
730   else
731     {
732       /* E was already in the hash table.  Free ELT as we do not need it
733          anymore.  */
734       free (elt);
735
736       /* Get the entry stored in the hash table.  */
737       elt = (struct edge_to_cases_elt *) *slot;
738
739       /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
740       TREE_CHAIN (case_label) = elt->case_labels;
741       elt->case_labels = case_label;
742     }
743 }
744
745 /* If we are inside a {start,end}_recording_cases block, then return
746    a chain of CASE_LABEL_EXPRs from T which reference E.
747
748    Otherwise return NULL.  */
749
750 static tree
751 get_cases_for_edge (edge e, tree t)
752 {
753   struct edge_to_cases_elt elt, *elt_p;
754   void **slot;
755   size_t i, n;
756   tree vec;
757
758   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
759      chains available.  Return NULL so the caller can detect this case.  */
760   if (!recording_case_labels_p ())
761     return NULL;
762   
763 restart:
764   elt.e = e;
765   elt.case_labels = NULL;
766   slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
767
768   if (slot)
769     {
770       elt_p = (struct edge_to_cases_elt *)*slot;
771       return elt_p->case_labels;
772     }
773
774   /* If we did not find E in the hash table, then this must be the first
775      time we have been queried for information about E & T.  Add all the
776      elements from T to the hash table then perform the query again.  */
777
778   vec = SWITCH_LABELS (t);
779   n = TREE_VEC_LENGTH (vec);
780   for (i = 0; i < n; i++)
781     {
782       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
783       basic_block label_bb = label_to_block (lab);
784       record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
785     }
786   goto restart;
787 }
788
789 /* Create the edges for a SWITCH_EXPR starting at block BB.
790    At this point, the switch body has been lowered and the
791    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
792
793 static void
794 make_switch_expr_edges (basic_block bb)
795 {
796   tree entry = last_stmt (bb);
797   size_t i, n;
798   tree vec;
799
800   vec = SWITCH_LABELS (entry);
801   n = TREE_VEC_LENGTH (vec);
802
803   for (i = 0; i < n; ++i)
804     {
805       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
806       basic_block label_bb = label_to_block (lab);
807       make_edge (bb, label_bb, 0);
808     }
809 }
810
811
812 /* Return the basic block holding label DEST.  */
813
814 basic_block
815 label_to_block_fn (struct function *ifun, tree dest)
816 {
817   int uid = LABEL_DECL_UID (dest);
818
819   /* We would die hard when faced by an undefined label.  Emit a label to
820      the very first basic block.  This will hopefully make even the dataflow
821      and undefined variable warnings quite right.  */
822   if ((errorcount || sorrycount) && uid < 0)
823     {
824       block_stmt_iterator bsi = 
825         bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
826       tree stmt;
827
828       stmt = build1 (LABEL_EXPR, void_type_node, dest);
829       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
830       uid = LABEL_DECL_UID (dest);
831     }
832   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
833       <= (unsigned int) uid)
834     return NULL;
835   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
836 }
837
838 /* Create edges for a goto statement at block BB.  */
839
840 static void
841 make_goto_expr_edges (basic_block bb)
842 {
843   tree goto_t;
844   basic_block target_bb;
845   bool for_call;
846   block_stmt_iterator last = bsi_last (bb);
847
848   goto_t = bsi_stmt (last);
849
850   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
851      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
852      from a nonlocal goto.  */
853   if (TREE_CODE (goto_t) != GOTO_EXPR)
854     for_call = true;
855   else
856     {
857       tree dest = GOTO_DESTINATION (goto_t);
858       for_call = false;
859
860       /* A GOTO to a local label creates normal edges.  */
861       if (simple_goto_p (goto_t))
862         {
863           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
864 #ifdef USE_MAPPED_LOCATION
865           e->goto_locus = EXPR_LOCATION (goto_t);
866 #else
867           e->goto_locus = EXPR_LOCUS (goto_t);
868 #endif
869           bsi_remove (&last, true);
870           return;
871         }
872
873       /* Nothing more to do for nonlocal gotos.  */
874       if (TREE_CODE (dest) == LABEL_DECL)
875         return;
876
877       /* Computed gotos remain.  */
878     }
879
880   /* Look for the block starting with the destination label.  In the
881      case of a computed goto, make an edge to any label block we find
882      in the CFG.  */
883   FOR_EACH_BB (target_bb)
884     {
885       block_stmt_iterator bsi;
886
887       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
888         {
889           tree target = bsi_stmt (bsi);
890
891           if (TREE_CODE (target) != LABEL_EXPR)
892             break;
893
894           if (
895               /* Computed GOTOs.  Make an edge to every label block that has
896                  been marked as a potential target for a computed goto.  */
897               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && !for_call)
898               /* Nonlocal GOTO target.  Make an edge to every label block
899                  that has been marked as a potential target for a nonlocal
900                  goto.  */
901               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call))
902             {
903               make_edge (bb, target_bb, EDGE_ABNORMAL);
904               break;
905             }
906         }
907     }
908 }
909
910
911 /*---------------------------------------------------------------------------
912                                Flowgraph analysis
913 ---------------------------------------------------------------------------*/
914
915 /* Cleanup useless labels in basic blocks.  This is something we wish
916    to do early because it allows us to group case labels before creating
917    the edges for the CFG, and it speeds up block statement iterators in
918    all passes later on.
919    We only run this pass once, running it more than once is probably not
920    profitable.  */
921
922 /* A map from basic block index to the leading label of that block.  */
923 static tree *label_for_bb;
924
925 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
926 static void
927 update_eh_label (struct eh_region *region)
928 {
929   tree old_label = get_eh_region_tree_label (region);
930   if (old_label)
931     {
932       tree new_label;
933       basic_block bb = label_to_block (old_label);
934
935       /* ??? After optimizing, there may be EH regions with labels
936          that have already been removed from the function body, so
937          there is no basic block for them.  */
938       if (! bb)
939         return;
940
941       new_label = label_for_bb[bb->index];
942       set_eh_region_tree_label (region, new_label);
943     }
944 }
945
946 /* Given LABEL return the first label in the same basic block.  */
947 static tree
948 main_block_label (tree label)
949 {
950   basic_block bb = label_to_block (label);
951
952   /* label_to_block possibly inserted undefined label into the chain.  */
953   if (!label_for_bb[bb->index])
954     label_for_bb[bb->index] = label;
955   return label_for_bb[bb->index];
956 }
957
958 /* Cleanup redundant labels.  This is a three-step process:
959      1) Find the leading label for each block.
960      2) Redirect all references to labels to the leading labels.
961      3) Cleanup all useless labels.  */
962
963 void
964 cleanup_dead_labels (void)
965 {
966   basic_block bb;
967   label_for_bb = XCNEWVEC (tree, last_basic_block);
968
969   /* Find a suitable label for each block.  We use the first user-defined
970      label if there is one, or otherwise just the first label we see.  */
971   FOR_EACH_BB (bb)
972     {
973       block_stmt_iterator i;
974
975       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
976         {
977           tree label, stmt = bsi_stmt (i);
978
979           if (TREE_CODE (stmt) != LABEL_EXPR)
980             break;
981
982           label = LABEL_EXPR_LABEL (stmt);
983
984           /* If we have not yet seen a label for the current block,
985              remember this one and see if there are more labels.  */
986           if (! label_for_bb[bb->index])
987             {
988               label_for_bb[bb->index] = label;
989               continue;
990             }
991
992           /* If we did see a label for the current block already, but it
993              is an artificially created label, replace it if the current
994              label is a user defined label.  */
995           if (! DECL_ARTIFICIAL (label)
996               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
997             {
998               label_for_bb[bb->index] = label;
999               break;
1000             }
1001         }
1002     }
1003
1004   /* Now redirect all jumps/branches to the selected label.
1005      First do so for each block ending in a control statement.  */
1006   FOR_EACH_BB (bb)
1007     {
1008       tree stmt = last_stmt (bb);
1009       if (!stmt)
1010         continue;
1011
1012       switch (TREE_CODE (stmt))
1013         {
1014         case COND_EXPR:
1015           {
1016             tree true_branch, false_branch;
1017
1018             true_branch = COND_EXPR_THEN (stmt);
1019             false_branch = COND_EXPR_ELSE (stmt);
1020
1021             GOTO_DESTINATION (true_branch)
1022               = main_block_label (GOTO_DESTINATION (true_branch));
1023             GOTO_DESTINATION (false_branch)
1024               = main_block_label (GOTO_DESTINATION (false_branch));
1025
1026             break;
1027           }
1028   
1029         case SWITCH_EXPR:
1030           {
1031             size_t i;
1032             tree vec = SWITCH_LABELS (stmt);
1033             size_t n = TREE_VEC_LENGTH (vec);
1034   
1035             /* Replace all destination labels.  */
1036             for (i = 0; i < n; ++i)
1037               {
1038                 tree elt = TREE_VEC_ELT (vec, i);
1039                 tree label = main_block_label (CASE_LABEL (elt));
1040                 CASE_LABEL (elt) = label;
1041               }
1042             break;
1043           }
1044
1045         /* We have to handle GOTO_EXPRs until they're removed, and we don't
1046            remove them until after we've created the CFG edges.  */
1047         case GOTO_EXPR:
1048           if (! computed_goto_p (stmt))
1049             {
1050               GOTO_DESTINATION (stmt)
1051                 = main_block_label (GOTO_DESTINATION (stmt));
1052               break;
1053             }
1054
1055         default:
1056           break;
1057       }
1058     }
1059
1060   for_each_eh_region (update_eh_label);
1061
1062   /* Finally, purge dead labels.  All user-defined labels and labels that
1063      can be the target of non-local gotos and labels which have their
1064      address taken are preserved.  */
1065   FOR_EACH_BB (bb)
1066     {
1067       block_stmt_iterator i;
1068       tree label_for_this_bb = label_for_bb[bb->index];
1069
1070       if (! label_for_this_bb)
1071         continue;
1072
1073       for (i = bsi_start (bb); !bsi_end_p (i); )
1074         {
1075           tree label, stmt = bsi_stmt (i);
1076
1077           if (TREE_CODE (stmt) != LABEL_EXPR)
1078             break;
1079
1080           label = LABEL_EXPR_LABEL (stmt);
1081
1082           if (label == label_for_this_bb
1083               || ! DECL_ARTIFICIAL (label)
1084               || DECL_NONLOCAL (label)
1085               || FORCED_LABEL (label))
1086             bsi_next (&i);
1087           else
1088             bsi_remove (&i, true);
1089         }
1090     }
1091
1092   free (label_for_bb);
1093 }
1094
1095 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1096    and scan the sorted vector of cases.  Combine the ones jumping to the
1097    same label.
1098    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1099
1100 void
1101 group_case_labels (void)
1102 {
1103   basic_block bb;
1104
1105   FOR_EACH_BB (bb)
1106     {
1107       tree stmt = last_stmt (bb);
1108       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1109         {
1110           tree labels = SWITCH_LABELS (stmt);
1111           int old_size = TREE_VEC_LENGTH (labels);
1112           int i, j, new_size = old_size;
1113           tree default_case = TREE_VEC_ELT (labels, old_size - 1);
1114           tree default_label;
1115
1116           /* The default label is always the last case in a switch
1117              statement after gimplification.  */
1118           default_label = CASE_LABEL (default_case);
1119
1120           /* Look for possible opportunities to merge cases.
1121              Ignore the last element of the label vector because it
1122              must be the default case.  */
1123           i = 0;
1124           while (i < old_size - 1)
1125             {
1126               tree base_case, base_label, base_high;
1127               base_case = TREE_VEC_ELT (labels, i);
1128
1129               gcc_assert (base_case);
1130               base_label = CASE_LABEL (base_case);
1131
1132               /* Discard cases that have the same destination as the
1133                  default case.  */
1134               if (base_label == default_label)
1135                 {
1136                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1137                   i++;
1138                   new_size--;
1139                   continue;
1140                 }
1141
1142               base_high = CASE_HIGH (base_case) ?
1143                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1144               i++;
1145               /* Try to merge case labels.  Break out when we reach the end
1146                  of the label vector or when we cannot merge the next case
1147                  label with the current one.  */
1148               while (i < old_size - 1)
1149                 {
1150                   tree merge_case = TREE_VEC_ELT (labels, i);
1151                   tree merge_label = CASE_LABEL (merge_case);
1152                   tree t = int_const_binop (PLUS_EXPR, base_high,
1153                                             integer_one_node, 1);
1154
1155                   /* Merge the cases if they jump to the same place,
1156                      and their ranges are consecutive.  */
1157                   if (merge_label == base_label
1158                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1159                     {
1160                       base_high = CASE_HIGH (merge_case) ?
1161                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1162                       CASE_HIGH (base_case) = base_high;
1163                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1164                       new_size--;
1165                       i++;
1166                     }
1167                   else
1168                     break;
1169                 }
1170             }
1171
1172           /* Compress the case labels in the label vector, and adjust the
1173              length of the vector.  */
1174           for (i = 0, j = 0; i < new_size; i++)
1175             {
1176               while (! TREE_VEC_ELT (labels, j))
1177                 j++;
1178               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1179             }
1180           TREE_VEC_LENGTH (labels) = new_size;
1181         }
1182     }
1183 }
1184
1185 /* Checks whether we can merge block B into block A.  */
1186
1187 static bool
1188 tree_can_merge_blocks_p (basic_block a, basic_block b)
1189 {
1190   tree stmt;
1191   block_stmt_iterator bsi;
1192   tree phi;
1193
1194   if (!single_succ_p (a))
1195     return false;
1196
1197   if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1198     return false;
1199
1200   if (single_succ (a) != b)
1201     return false;
1202
1203   if (!single_pred_p (b))
1204     return false;
1205
1206   if (b == EXIT_BLOCK_PTR)
1207     return false;
1208   
1209   /* If A ends by a statement causing exceptions or something similar, we
1210      cannot merge the blocks.  */
1211   stmt = last_stmt (a);
1212   if (stmt && stmt_ends_bb_p (stmt))
1213     return false;
1214
1215   /* Do not allow a block with only a non-local label to be merged.  */
1216   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1217       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1218     return false;
1219
1220   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1221      is not up-to-date, we cannot eliminate any phis.  */
1222   phi = phi_nodes (b);
1223   if (phi)
1224     {
1225       if (need_ssa_update_p ())
1226         return false;
1227
1228       for (; phi; phi = PHI_CHAIN (phi))
1229         if (!is_gimple_reg (PHI_RESULT (phi))
1230             && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
1231           return false;
1232     }
1233
1234   /* Do not remove user labels.  */
1235   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1236     {
1237       stmt = bsi_stmt (bsi);
1238       if (TREE_CODE (stmt) != LABEL_EXPR)
1239         break;
1240       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1241         return false;
1242     }
1243
1244   /* Protect the loop latches.  */
1245   if (current_loops
1246       && b->loop_father->latch == b)
1247     return false;
1248
1249   return true;
1250 }
1251
1252 /* Replaces all uses of NAME by VAL.  */
1253
1254 void
1255 replace_uses_by (tree name, tree val)
1256 {
1257   imm_use_iterator imm_iter;
1258   use_operand_p use;
1259   tree stmt;
1260   edge e;
1261   unsigned i;
1262
1263
1264   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1265     {
1266       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1267         {
1268           replace_exp (use, val);
1269
1270           if (TREE_CODE (stmt) == PHI_NODE)
1271             {
1272               e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
1273               if (e->flags & EDGE_ABNORMAL)
1274                 {
1275                   /* This can only occur for virtual operands, since
1276                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1277                      would prevent replacement.  */
1278                   gcc_assert (!is_gimple_reg (name));
1279                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1280                 }
1281             }
1282         }
1283       if (TREE_CODE (stmt) != PHI_NODE)
1284         {
1285           tree rhs;
1286
1287           fold_stmt_inplace (stmt);
1288           rhs = get_rhs (stmt);
1289           if (TREE_CODE (rhs) == ADDR_EXPR)
1290             recompute_tree_invariant_for_addr_expr (rhs);
1291
1292           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1293           mark_new_vars_to_rename (stmt);
1294         }
1295     }
1296  
1297   gcc_assert (num_imm_uses (name) == 0);
1298
1299   /* Also update the trees stored in loop structures.  */
1300   if (current_loops)
1301     {
1302       struct loop *loop;
1303
1304       for (i = 0; i < current_loops->num; i++)
1305         {
1306           loop = current_loops->parray[i];
1307           if (loop)
1308             substitute_in_loop_info (loop, name, val);
1309         }
1310     }
1311 }
1312
1313 /* Merge block B into block A.  */
1314
1315 static void
1316 tree_merge_blocks (basic_block a, basic_block b)
1317 {
1318   block_stmt_iterator bsi;
1319   tree_stmt_iterator last;
1320   tree phi;
1321
1322   if (dump_file)
1323     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1324
1325   /* Remove all single-valued PHI nodes from block B of the form
1326      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1327   bsi = bsi_last (a);
1328   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1329     {
1330       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1331       tree copy;
1332       bool may_replace_uses = may_propagate_copy (def, use);
1333
1334       /* In case we have loops to care about, do not propagate arguments of
1335          loop closed ssa phi nodes.  */
1336       if (current_loops
1337           && is_gimple_reg (def)
1338           && TREE_CODE (use) == SSA_NAME
1339           && a->loop_father != b->loop_father)
1340         may_replace_uses = false;
1341
1342       if (!may_replace_uses)
1343         {
1344           gcc_assert (is_gimple_reg (def));
1345
1346           /* Note that just emitting the copies is fine -- there is no problem
1347              with ordering of phi nodes.  This is because A is the single
1348              predecessor of B, therefore results of the phi nodes cannot
1349              appear as arguments of the phi nodes.  */
1350           copy = build2 (MODIFY_EXPR, void_type_node, def, use);
1351           bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1352           SET_PHI_RESULT (phi, NULL_TREE);
1353           SSA_NAME_DEF_STMT (def) = copy;
1354         }
1355       else
1356         replace_uses_by (def, use);
1357
1358       remove_phi_node (phi, NULL);
1359     }
1360
1361   /* Ensure that B follows A.  */
1362   move_block_after (b, a);
1363
1364   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1365   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1366
1367   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1368   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1369     {
1370       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1371         {
1372           tree label = bsi_stmt (bsi);
1373
1374           bsi_remove (&bsi, false);
1375           /* Now that we can thread computed gotos, we might have
1376              a situation where we have a forced label in block B
1377              However, the label at the start of block B might still be
1378              used in other ways (think about the runtime checking for
1379              Fortran assigned gotos).  So we can not just delete the
1380              label.  Instead we move the label to the start of block A.  */
1381           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1382             {
1383               block_stmt_iterator dest_bsi = bsi_start (a);
1384               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1385             }
1386         }
1387       else
1388         {
1389           set_bb_for_stmt (bsi_stmt (bsi), a);
1390           bsi_next (&bsi);
1391         }
1392     }
1393
1394   /* Merge the chains.  */
1395   last = tsi_last (a->stmt_list);
1396   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1397   b->stmt_list = NULL;
1398 }
1399
1400
1401 /* Return the one of two successors of BB that is not reachable by a
1402    reached by a complex edge, if there is one.  Else, return BB.  We use
1403    this in optimizations that use post-dominators for their heuristics,
1404    to catch the cases in C++ where function calls are involved.  */
1405     
1406 basic_block
1407 single_noncomplex_succ (basic_block bb)  
1408 {
1409   edge e0, e1;
1410   if (EDGE_COUNT (bb->succs) != 2)
1411     return bb;
1412    
1413   e0 = EDGE_SUCC (bb, 0);
1414   e1 = EDGE_SUCC (bb, 1);
1415   if (e0->flags & EDGE_COMPLEX)
1416     return e1->dest;
1417   if (e1->flags & EDGE_COMPLEX)
1418     return e0->dest;
1419    
1420   return bb;
1421 }       
1422         
1423
1424
1425 /* Walk the function tree removing unnecessary statements.
1426
1427      * Empty statement nodes are removed
1428
1429      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1430
1431      * Unnecessary COND_EXPRs are removed
1432
1433      * Some unnecessary BIND_EXPRs are removed
1434
1435    Clearly more work could be done.  The trick is doing the analysis
1436    and removal fast enough to be a net improvement in compile times.
1437
1438    Note that when we remove a control structure such as a COND_EXPR
1439    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1440    to ensure we eliminate all the useless code.  */
1441
1442 struct rus_data
1443 {
1444   tree *last_goto;
1445   bool repeat;
1446   bool may_throw;
1447   bool may_branch;
1448   bool has_label;
1449 };
1450
1451 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1452
1453 static bool
1454 remove_useless_stmts_warn_notreached (tree stmt)
1455 {
1456   if (EXPR_HAS_LOCATION (stmt))
1457     {
1458       location_t loc = EXPR_LOCATION (stmt);
1459       if (LOCATION_LINE (loc) > 0)
1460         {
1461           warning (0, "%Hwill never be executed", &loc);
1462           return true;
1463         }
1464     }
1465
1466   switch (TREE_CODE (stmt))
1467     {
1468     case STATEMENT_LIST:
1469       {
1470         tree_stmt_iterator i;
1471         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1472           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1473             return true;
1474       }
1475       break;
1476
1477     case COND_EXPR:
1478       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1479         return true;
1480       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1481         return true;
1482       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1483         return true;
1484       break;
1485
1486     case TRY_FINALLY_EXPR:
1487     case TRY_CATCH_EXPR:
1488       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1489         return true;
1490       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1491         return true;
1492       break;
1493
1494     case CATCH_EXPR:
1495       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1496     case EH_FILTER_EXPR:
1497       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1498     case BIND_EXPR:
1499       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1500
1501     default:
1502       /* Not a live container.  */
1503       break;
1504     }
1505
1506   return false;
1507 }
1508
1509 static void
1510 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1511 {
1512   tree then_clause, else_clause, cond;
1513   bool save_has_label, then_has_label, else_has_label;
1514
1515   save_has_label = data->has_label;
1516   data->has_label = false;
1517   data->last_goto = NULL;
1518
1519   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1520
1521   then_has_label = data->has_label;
1522   data->has_label = false;
1523   data->last_goto = NULL;
1524
1525   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1526
1527   else_has_label = data->has_label;
1528   data->has_label = save_has_label | then_has_label | else_has_label;
1529
1530   then_clause = COND_EXPR_THEN (*stmt_p);
1531   else_clause = COND_EXPR_ELSE (*stmt_p);
1532   cond = fold (COND_EXPR_COND (*stmt_p));
1533
1534   /* If neither arm does anything at all, we can remove the whole IF.  */
1535   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1536     {
1537       *stmt_p = build_empty_stmt ();
1538       data->repeat = true;
1539     }
1540
1541   /* If there are no reachable statements in an arm, then we can
1542      zap the entire conditional.  */
1543   else if (integer_nonzerop (cond) && !else_has_label)
1544     {
1545       if (warn_notreached)
1546         remove_useless_stmts_warn_notreached (else_clause);
1547       *stmt_p = then_clause;
1548       data->repeat = true;
1549     }
1550   else if (integer_zerop (cond) && !then_has_label)
1551     {
1552       if (warn_notreached)
1553         remove_useless_stmts_warn_notreached (then_clause);
1554       *stmt_p = else_clause;
1555       data->repeat = true;
1556     }
1557
1558   /* Check a couple of simple things on then/else with single stmts.  */
1559   else
1560     {
1561       tree then_stmt = expr_only (then_clause);
1562       tree else_stmt = expr_only (else_clause);
1563
1564       /* Notice branches to a common destination.  */
1565       if (then_stmt && else_stmt
1566           && TREE_CODE (then_stmt) == GOTO_EXPR
1567           && TREE_CODE (else_stmt) == GOTO_EXPR
1568           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1569         {
1570           *stmt_p = then_stmt;
1571           data->repeat = true;
1572         }
1573
1574       /* If the THEN/ELSE clause merely assigns a value to a variable or
1575          parameter which is already known to contain that value, then
1576          remove the useless THEN/ELSE clause.  */
1577       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1578         {
1579           if (else_stmt
1580               && TREE_CODE (else_stmt) == MODIFY_EXPR
1581               && TREE_OPERAND (else_stmt, 0) == cond
1582               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1583             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1584         }
1585       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1586                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1587                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1588                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1589         {
1590           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1591                        ? then_stmt : else_stmt);
1592           tree *location = (TREE_CODE (cond) == EQ_EXPR
1593                             ? &COND_EXPR_THEN (*stmt_p)
1594                             : &COND_EXPR_ELSE (*stmt_p));
1595
1596           if (stmt
1597               && TREE_CODE (stmt) == MODIFY_EXPR
1598               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1599               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1600             *location = alloc_stmt_list ();
1601         }
1602     }
1603
1604   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1605      would be re-introduced during lowering.  */
1606   data->last_goto = NULL;
1607 }
1608
1609
1610 static void
1611 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1612 {
1613   bool save_may_branch, save_may_throw;
1614   bool this_may_branch, this_may_throw;
1615
1616   /* Collect may_branch and may_throw information for the body only.  */
1617   save_may_branch = data->may_branch;
1618   save_may_throw = data->may_throw;
1619   data->may_branch = false;
1620   data->may_throw = false;
1621   data->last_goto = NULL;
1622
1623   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1624
1625   this_may_branch = data->may_branch;
1626   this_may_throw = data->may_throw;
1627   data->may_branch |= save_may_branch;
1628   data->may_throw |= save_may_throw;
1629   data->last_goto = NULL;
1630
1631   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1632
1633   /* If the body is empty, then we can emit the FINALLY block without
1634      the enclosing TRY_FINALLY_EXPR.  */
1635   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1636     {
1637       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1638       data->repeat = true;
1639     }
1640
1641   /* If the handler is empty, then we can emit the TRY block without
1642      the enclosing TRY_FINALLY_EXPR.  */
1643   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1644     {
1645       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1646       data->repeat = true;
1647     }
1648
1649   /* If the body neither throws, nor branches, then we can safely
1650      string the TRY and FINALLY blocks together.  */
1651   else if (!this_may_branch && !this_may_throw)
1652     {
1653       tree stmt = *stmt_p;
1654       *stmt_p = TREE_OPERAND (stmt, 0);
1655       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1656       data->repeat = true;
1657     }
1658 }
1659
1660
1661 static void
1662 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1663 {
1664   bool save_may_throw, this_may_throw;
1665   tree_stmt_iterator i;
1666   tree stmt;
1667
1668   /* Collect may_throw information for the body only.  */
1669   save_may_throw = data->may_throw;
1670   data->may_throw = false;
1671   data->last_goto = NULL;
1672
1673   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1674
1675   this_may_throw = data->may_throw;
1676   data->may_throw = save_may_throw;
1677
1678   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1679   if (!this_may_throw)
1680     {
1681       if (warn_notreached)
1682         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1683       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1684       data->repeat = true;
1685       return;
1686     }
1687
1688   /* Process the catch clause specially.  We may be able to tell that
1689      no exceptions propagate past this point.  */
1690
1691   this_may_throw = true;
1692   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1693   stmt = tsi_stmt (i);
1694   data->last_goto = NULL;
1695
1696   switch (TREE_CODE (stmt))
1697     {
1698     case CATCH_EXPR:
1699       for (; !tsi_end_p (i); tsi_next (&i))
1700         {
1701           stmt = tsi_stmt (i);
1702           /* If we catch all exceptions, then the body does not
1703              propagate exceptions past this point.  */
1704           if (CATCH_TYPES (stmt) == NULL)
1705             this_may_throw = false;
1706           data->last_goto = NULL;
1707           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1708         }
1709       break;
1710
1711     case EH_FILTER_EXPR:
1712       if (EH_FILTER_MUST_NOT_THROW (stmt))
1713         this_may_throw = false;
1714       else if (EH_FILTER_TYPES (stmt) == NULL)
1715         this_may_throw = false;
1716       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1717       break;
1718
1719     default:
1720       /* Otherwise this is a cleanup.  */
1721       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1722
1723       /* If the cleanup is empty, then we can emit the TRY block without
1724          the enclosing TRY_CATCH_EXPR.  */
1725       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1726         {
1727           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1728           data->repeat = true;
1729         }
1730       break;
1731     }
1732   data->may_throw |= this_may_throw;
1733 }
1734
1735
1736 static void
1737 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1738 {
1739   tree block;
1740
1741   /* First remove anything underneath the BIND_EXPR.  */
1742   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1743
1744   /* If the BIND_EXPR has no variables, then we can pull everything
1745      up one level and remove the BIND_EXPR, unless this is the toplevel
1746      BIND_EXPR for the current function or an inlined function.
1747
1748      When this situation occurs we will want to apply this
1749      optimization again.  */
1750   block = BIND_EXPR_BLOCK (*stmt_p);
1751   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1752       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1753       && (! block
1754           || ! BLOCK_ABSTRACT_ORIGIN (block)
1755           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1756               != FUNCTION_DECL)))
1757     {
1758       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1759       data->repeat = true;
1760     }
1761 }
1762
1763
1764 static void
1765 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1766 {
1767   tree dest = GOTO_DESTINATION (*stmt_p);
1768
1769   data->may_branch = true;
1770   data->last_goto = NULL;
1771
1772   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1773   if (TREE_CODE (dest) == LABEL_DECL)
1774     data->last_goto = stmt_p;
1775 }
1776
1777
1778 static void
1779 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1780 {
1781   tree label = LABEL_EXPR_LABEL (*stmt_p);
1782
1783   data->has_label = true;
1784
1785   /* We do want to jump across non-local label receiver code.  */
1786   if (DECL_NONLOCAL (label))
1787     data->last_goto = NULL;
1788
1789   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1790     {
1791       *data->last_goto = build_empty_stmt ();
1792       data->repeat = true;
1793     }
1794
1795   /* ??? Add something here to delete unused labels.  */
1796 }
1797
1798
1799 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1800    decl.  This allows us to eliminate redundant or useless
1801    calls to "const" functions. 
1802
1803    Gimplifier already does the same operation, but we may notice functions
1804    being const and pure once their calls has been gimplified, so we need
1805    to update the flag.  */
1806
1807 static void
1808 update_call_expr_flags (tree call)
1809 {
1810   tree decl = get_callee_fndecl (call);
1811   if (!decl)
1812     return;
1813   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1814     TREE_SIDE_EFFECTS (call) = 0;
1815   if (TREE_NOTHROW (decl))
1816     TREE_NOTHROW (call) = 1;
1817 }
1818
1819
1820 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1821
1822 void
1823 notice_special_calls (tree t)
1824 {
1825   int flags = call_expr_flags (t);
1826
1827   if (flags & ECF_MAY_BE_ALLOCA)
1828     current_function_calls_alloca = true;
1829   if (flags & ECF_RETURNS_TWICE)
1830     current_function_calls_setjmp = true;
1831 }
1832
1833
1834 /* Clear flags set by notice_special_calls.  Used by dead code removal
1835    to update the flags.  */
1836
1837 void
1838 clear_special_calls (void)
1839 {
1840   current_function_calls_alloca = false;
1841   current_function_calls_setjmp = false;
1842 }
1843
1844
1845 static void
1846 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1847 {
1848   tree t = *tp, op;
1849
1850   switch (TREE_CODE (t))
1851     {
1852     case COND_EXPR:
1853       remove_useless_stmts_cond (tp, data);
1854       break;
1855
1856     case TRY_FINALLY_EXPR:
1857       remove_useless_stmts_tf (tp, data);
1858       break;
1859
1860     case TRY_CATCH_EXPR:
1861       remove_useless_stmts_tc (tp, data);
1862       break;
1863
1864     case BIND_EXPR:
1865       remove_useless_stmts_bind (tp, data);
1866       break;
1867
1868     case GOTO_EXPR:
1869       remove_useless_stmts_goto (tp, data);
1870       break;
1871
1872     case LABEL_EXPR:
1873       remove_useless_stmts_label (tp, data);
1874       break;
1875
1876     case RETURN_EXPR:
1877       fold_stmt (tp);
1878       data->last_goto = NULL;
1879       data->may_branch = true;
1880       break;
1881
1882     case CALL_EXPR:
1883       fold_stmt (tp);
1884       data->last_goto = NULL;
1885       notice_special_calls (t);
1886       update_call_expr_flags (t);
1887       if (tree_could_throw_p (t))
1888         data->may_throw = true;
1889       break;
1890
1891     case MODIFY_EXPR:
1892       data->last_goto = NULL;
1893       fold_stmt (tp);
1894       op = get_call_expr_in (t);
1895       if (op)
1896         {
1897           update_call_expr_flags (op);
1898           notice_special_calls (op);
1899         }
1900       if (tree_could_throw_p (t))
1901         data->may_throw = true;
1902       break;
1903
1904     case STATEMENT_LIST:
1905       {
1906         tree_stmt_iterator i = tsi_start (t);
1907         while (!tsi_end_p (i))
1908           {
1909             t = tsi_stmt (i);
1910             if (IS_EMPTY_STMT (t))
1911               {
1912                 tsi_delink (&i);
1913                 continue;
1914               }
1915             
1916             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1917
1918             t = tsi_stmt (i);
1919             if (TREE_CODE (t) == STATEMENT_LIST)
1920               {
1921                 tsi_link_before (&i, t, TSI_SAME_STMT);
1922                 tsi_delink (&i);
1923               }
1924             else
1925               tsi_next (&i);
1926           }
1927       }
1928       break;
1929     case ASM_EXPR:
1930       fold_stmt (tp);
1931       data->last_goto = NULL;
1932       break;
1933
1934     default:
1935       data->last_goto = NULL;
1936       break;
1937     }
1938 }
1939
1940 static unsigned int
1941 remove_useless_stmts (void)
1942 {
1943   struct rus_data data;
1944
1945   clear_special_calls ();
1946
1947   do
1948     {
1949       memset (&data, 0, sizeof (data));
1950       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1951     }
1952   while (data.repeat);
1953   return 0;
1954 }
1955
1956
1957 struct tree_opt_pass pass_remove_useless_stmts = 
1958 {
1959   "useless",                            /* name */
1960   NULL,                                 /* gate */
1961   remove_useless_stmts,                 /* execute */
1962   NULL,                                 /* sub */
1963   NULL,                                 /* next */
1964   0,                                    /* static_pass_number */
1965   0,                                    /* tv_id */
1966   PROP_gimple_any,                      /* properties_required */
1967   0,                                    /* properties_provided */
1968   0,                                    /* properties_destroyed */
1969   0,                                    /* todo_flags_start */
1970   TODO_dump_func,                       /* todo_flags_finish */
1971   0                                     /* letter */
1972 };
1973
1974 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1975
1976 static void
1977 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1978 {
1979   tree phi;
1980
1981   /* Since this block is no longer reachable, we can just delete all
1982      of its PHI nodes.  */
1983   phi = phi_nodes (bb);
1984   while (phi)
1985     {
1986       tree next = PHI_CHAIN (phi);
1987       remove_phi_node (phi, NULL_TREE);
1988       phi = next;
1989     }
1990
1991   /* Remove edges to BB's successors.  */
1992   while (EDGE_COUNT (bb->succs) > 0)
1993     remove_edge (EDGE_SUCC (bb, 0));
1994 }
1995
1996
1997 /* Remove statements of basic block BB.  */
1998
1999 static void
2000 remove_bb (basic_block bb)
2001 {
2002   block_stmt_iterator i;
2003 #ifdef USE_MAPPED_LOCATION
2004   source_location loc = UNKNOWN_LOCATION;
2005 #else
2006   source_locus loc = 0;
2007 #endif
2008
2009   if (dump_file)
2010     {
2011       fprintf (dump_file, "Removing basic block %d\n", bb->index);
2012       if (dump_flags & TDF_DETAILS)
2013         {
2014           dump_bb (bb, dump_file, 0);
2015           fprintf (dump_file, "\n");
2016         }
2017     }
2018
2019   /* If we remove the header or the latch of a loop, mark the loop for
2020      removal by setting its header and latch to NULL.  */
2021   if (current_loops)
2022     {
2023       struct loop *loop = bb->loop_father;
2024
2025       if (loop->latch == bb
2026           || loop->header == bb)
2027         {
2028           loop->latch = NULL;
2029           loop->header = NULL;
2030
2031           /* Also clean up the information associated with the loop.  Updating
2032              it would waste time. More importantly, it may refer to ssa
2033              names that were defined in other removed basic block -- these
2034              ssa names are now removed and invalid.  */
2035           free_numbers_of_iterations_estimates_loop (loop);
2036         }
2037     }
2038
2039   /* Remove all the instructions in the block.  */
2040   for (i = bsi_start (bb); !bsi_end_p (i);)
2041     {
2042       tree stmt = bsi_stmt (i);
2043       if (TREE_CODE (stmt) == LABEL_EXPR
2044           && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
2045               || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
2046         {
2047           basic_block new_bb;
2048           block_stmt_iterator new_bsi;
2049
2050           /* A non-reachable non-local label may still be referenced.
2051              But it no longer needs to carry the extra semantics of
2052              non-locality.  */
2053           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
2054             {
2055               DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
2056               FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
2057             }
2058                   
2059           new_bb = bb->prev_bb;
2060           new_bsi = bsi_start (new_bb);
2061           bsi_remove (&i, false);
2062           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2063         }
2064       else
2065         {
2066           /* Release SSA definitions if we are in SSA.  Note that we
2067              may be called when not in SSA.  For example,
2068              final_cleanup calls this function via
2069              cleanup_tree_cfg.  */
2070           if (in_ssa_p)
2071             release_defs (stmt);
2072
2073           bsi_remove (&i, true);
2074         }
2075
2076       /* Don't warn for removed gotos.  Gotos are often removed due to
2077          jump threading, thus resulting in bogus warnings.  Not great,
2078          since this way we lose warnings for gotos in the original
2079          program that are indeed unreachable.  */
2080       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2081         {
2082 #ifdef USE_MAPPED_LOCATION
2083           if (EXPR_HAS_LOCATION (stmt))
2084             loc = EXPR_LOCATION (stmt);
2085 #else
2086           source_locus t;
2087           t = EXPR_LOCUS (stmt);
2088           if (t && LOCATION_LINE (*t) > 0)
2089             loc = t;
2090 #endif
2091         }
2092     }
2093
2094   /* If requested, give a warning that the first statement in the
2095      block is unreachable.  We walk statements backwards in the
2096      loop above, so the last statement we process is the first statement
2097      in the block.  */
2098 #ifdef USE_MAPPED_LOCATION
2099   if (loc > BUILTINS_LOCATION)
2100     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2101 #else
2102   if (loc)
2103     warning (OPT_Wunreachable_code, "%Hwill never be executed", loc);
2104 #endif
2105
2106   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2107 }
2108
2109
2110 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2111    predicate VAL, return the edge that will be taken out of the block.
2112    If VAL does not match a unique edge, NULL is returned.  */
2113
2114 edge
2115 find_taken_edge (basic_block bb, tree val)
2116 {
2117   tree stmt;
2118
2119   stmt = last_stmt (bb);
2120
2121   gcc_assert (stmt);
2122   gcc_assert (is_ctrl_stmt (stmt));
2123   gcc_assert (val);
2124
2125   if (! is_gimple_min_invariant (val))
2126     return NULL;
2127
2128   if (TREE_CODE (stmt) == COND_EXPR)
2129     return find_taken_edge_cond_expr (bb, val);
2130
2131   if (TREE_CODE (stmt) == SWITCH_EXPR)
2132     return find_taken_edge_switch_expr (bb, val);
2133
2134   if (computed_goto_p (stmt))
2135     return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
2136
2137   gcc_unreachable ();
2138 }
2139
2140 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2141    statement, determine which of the outgoing edges will be taken out of the
2142    block.  Return NULL if either edge may be taken.  */
2143
2144 static edge
2145 find_taken_edge_computed_goto (basic_block bb, tree val)
2146 {
2147   basic_block dest;
2148   edge e = NULL;
2149
2150   dest = label_to_block (val);
2151   if (dest)
2152     {
2153       e = find_edge (bb, dest);
2154       gcc_assert (e != NULL);
2155     }
2156
2157   return e;
2158 }
2159
2160 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2161    statement, determine which of the two edges will be taken out of the
2162    block.  Return NULL if either edge may be taken.  */
2163
2164 static edge
2165 find_taken_edge_cond_expr (basic_block bb, tree val)
2166 {
2167   edge true_edge, false_edge;
2168
2169   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2170   
2171   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2172   return (zero_p (val) ? false_edge : true_edge);
2173 }
2174
2175 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2176    statement, determine which edge will be taken out of the block.  Return
2177    NULL if any edge may be taken.  */
2178
2179 static edge
2180 find_taken_edge_switch_expr (basic_block bb, tree val)
2181 {
2182   tree switch_expr, taken_case;
2183   basic_block dest_bb;
2184   edge e;
2185
2186   switch_expr = last_stmt (bb);
2187   taken_case = find_case_label_for_value (switch_expr, val);
2188   dest_bb = label_to_block (CASE_LABEL (taken_case));
2189
2190   e = find_edge (bb, dest_bb);
2191   gcc_assert (e);
2192   return e;
2193 }
2194
2195
2196 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2197    We can make optimal use here of the fact that the case labels are
2198    sorted: We can do a binary search for a case matching VAL.  */
2199
2200 static tree
2201 find_case_label_for_value (tree switch_expr, tree val)
2202 {
2203   tree vec = SWITCH_LABELS (switch_expr);
2204   size_t low, high, n = TREE_VEC_LENGTH (vec);
2205   tree default_case = TREE_VEC_ELT (vec, n - 1);
2206
2207   for (low = -1, high = n - 1; high - low > 1; )
2208     {
2209       size_t i = (high + low) / 2;
2210       tree t = TREE_VEC_ELT (vec, i);
2211       int cmp;
2212
2213       /* Cache the result of comparing CASE_LOW and val.  */
2214       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2215
2216       if (cmp > 0)
2217         high = i;
2218       else
2219         low = i;
2220
2221       if (CASE_HIGH (t) == NULL)
2222         {
2223           /* A singe-valued case label.  */
2224           if (cmp == 0)
2225             return t;
2226         }
2227       else
2228         {
2229           /* A case range.  We can only handle integer ranges.  */
2230           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2231             return t;
2232         }
2233     }
2234
2235   return default_case;
2236 }
2237
2238
2239
2240
2241 /*---------------------------------------------------------------------------
2242                               Debugging functions
2243 ---------------------------------------------------------------------------*/
2244
2245 /* Dump tree-specific information of block BB to file OUTF.  */
2246
2247 void
2248 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2249 {
2250   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2251 }
2252
2253
2254 /* Dump a basic block on stderr.  */
2255
2256 void
2257 debug_tree_bb (basic_block bb)
2258 {
2259   dump_bb (bb, stderr, 0);
2260 }
2261
2262
2263 /* Dump basic block with index N on stderr.  */
2264
2265 basic_block
2266 debug_tree_bb_n (int n)
2267 {
2268   debug_tree_bb (BASIC_BLOCK (n));
2269   return BASIC_BLOCK (n);
2270 }        
2271
2272
2273 /* Dump the CFG on stderr.
2274
2275    FLAGS are the same used by the tree dumping functions
2276    (see TDF_* in tree.h).  */
2277
2278 void
2279 debug_tree_cfg (int flags)
2280 {
2281   dump_tree_cfg (stderr, flags);
2282 }
2283
2284
2285 /* Dump the program showing basic block boundaries on the given FILE.
2286
2287    FLAGS are the same used by the tree dumping functions (see TDF_* in
2288    tree.h).  */
2289
2290 void
2291 dump_tree_cfg (FILE *file, int flags)
2292 {
2293   if (flags & TDF_DETAILS)
2294     {
2295       const char *funcname
2296         = lang_hooks.decl_printable_name (current_function_decl, 2);
2297
2298       fputc ('\n', file);
2299       fprintf (file, ";; Function %s\n\n", funcname);
2300       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2301                n_basic_blocks, n_edges, last_basic_block);
2302
2303       brief_dump_cfg (file);
2304       fprintf (file, "\n");
2305     }
2306
2307   if (flags & TDF_STATS)
2308     dump_cfg_stats (file);
2309
2310   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2311 }
2312
2313
2314 /* Dump CFG statistics on FILE.  */
2315
2316 void
2317 dump_cfg_stats (FILE *file)
2318 {
2319   static long max_num_merged_labels = 0;
2320   unsigned long size, total = 0;
2321   long num_edges;
2322   basic_block bb;
2323   const char * const fmt_str   = "%-30s%-13s%12s\n";
2324   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2325   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2326   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2327   const char *funcname
2328     = lang_hooks.decl_printable_name (current_function_decl, 2);
2329
2330
2331   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2332
2333   fprintf (file, "---------------------------------------------------------\n");
2334   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2335   fprintf (file, fmt_str, "", "  instances  ", "used ");
2336   fprintf (file, "---------------------------------------------------------\n");
2337
2338   size = n_basic_blocks * sizeof (struct basic_block_def);
2339   total += size;
2340   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2341            SCALE (size), LABEL (size));
2342
2343   num_edges = 0;
2344   FOR_EACH_BB (bb)
2345     num_edges += EDGE_COUNT (bb->succs);
2346   size = num_edges * sizeof (struct edge_def);
2347   total += size;
2348   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2349
2350   fprintf (file, "---------------------------------------------------------\n");
2351   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2352            LABEL (total));
2353   fprintf (file, "---------------------------------------------------------\n");
2354   fprintf (file, "\n");
2355
2356   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2357     max_num_merged_labels = cfg_stats.num_merged_labels;
2358
2359   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2360            cfg_stats.num_merged_labels, max_num_merged_labels);
2361
2362   fprintf (file, "\n");
2363 }
2364
2365
2366 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2367    linked in the final executable.  */
2368
2369 void
2370 debug_cfg_stats (void)
2371 {
2372   dump_cfg_stats (stderr);
2373 }
2374
2375
2376 /* Dump the flowgraph to a .vcg FILE.  */
2377
2378 static void
2379 tree_cfg2vcg (FILE *file)
2380 {
2381   edge e;
2382   edge_iterator ei;
2383   basic_block bb;
2384   const char *funcname
2385     = lang_hooks.decl_printable_name (current_function_decl, 2);
2386
2387   /* Write the file header.  */
2388   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2389   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2390   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2391
2392   /* Write blocks and edges.  */
2393   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2394     {
2395       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2396                e->dest->index);
2397
2398       if (e->flags & EDGE_FAKE)
2399         fprintf (file, " linestyle: dotted priority: 10");
2400       else
2401         fprintf (file, " linestyle: solid priority: 100");
2402
2403       fprintf (file, " }\n");
2404     }
2405   fputc ('\n', file);
2406
2407   FOR_EACH_BB (bb)
2408     {
2409       enum tree_code head_code, end_code;
2410       const char *head_name, *end_name;
2411       int head_line = 0;
2412       int end_line = 0;
2413       tree first = first_stmt (bb);
2414       tree last = last_stmt (bb);
2415
2416       if (first)
2417         {
2418           head_code = TREE_CODE (first);
2419           head_name = tree_code_name[head_code];
2420           head_line = get_lineno (first);
2421         }
2422       else
2423         head_name = "no-statement";
2424
2425       if (last)
2426         {
2427           end_code = TREE_CODE (last);
2428           end_name = tree_code_name[end_code];
2429           end_line = get_lineno (last);
2430         }
2431       else
2432         end_name = "no-statement";
2433
2434       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2435                bb->index, bb->index, head_name, head_line, end_name,
2436                end_line);
2437
2438       FOR_EACH_EDGE (e, ei, bb->succs)
2439         {
2440           if (e->dest == EXIT_BLOCK_PTR)
2441             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2442           else
2443             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2444
2445           if (e->flags & EDGE_FAKE)
2446             fprintf (file, " priority: 10 linestyle: dotted");
2447           else
2448             fprintf (file, " priority: 100 linestyle: solid");
2449
2450           fprintf (file, " }\n");
2451         }
2452
2453       if (bb->next_bb != EXIT_BLOCK_PTR)
2454         fputc ('\n', file);
2455     }
2456
2457   fputs ("}\n\n", file);
2458 }
2459
2460
2461
2462 /*---------------------------------------------------------------------------
2463                              Miscellaneous helpers
2464 ---------------------------------------------------------------------------*/
2465
2466 /* Return true if T represents a stmt that always transfers control.  */
2467
2468 bool
2469 is_ctrl_stmt (tree t)
2470 {
2471   return (TREE_CODE (t) == COND_EXPR
2472           || TREE_CODE (t) == SWITCH_EXPR
2473           || TREE_CODE (t) == GOTO_EXPR
2474           || TREE_CODE (t) == RETURN_EXPR
2475           || TREE_CODE (t) == RESX_EXPR);
2476 }
2477
2478
2479 /* Return true if T is a statement that may alter the flow of control
2480    (e.g., a call to a non-returning function).  */
2481
2482 bool
2483 is_ctrl_altering_stmt (tree t)
2484 {
2485   tree call;
2486
2487   gcc_assert (t);
2488   call = get_call_expr_in (t);
2489   if (call)
2490     {
2491       /* A non-pure/const CALL_EXPR alters flow control if the current
2492          function has nonlocal labels.  */
2493       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2494         return true;
2495
2496       /* A CALL_EXPR also alters control flow if it does not return.  */
2497       if (call_expr_flags (call) & ECF_NORETURN)
2498         return true;
2499     }
2500
2501   /* OpenMP directives alter control flow.  */
2502   if (OMP_DIRECTIVE_P (t))
2503     return true;
2504
2505   /* If a statement can throw, it alters control flow.  */
2506   return tree_can_throw_internal (t);
2507 }
2508
2509
2510 /* Return true if T is a computed goto.  */
2511
2512 bool
2513 computed_goto_p (tree t)
2514 {
2515   return (TREE_CODE (t) == GOTO_EXPR
2516           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2517 }
2518
2519
2520 /* Checks whether EXPR is a simple local goto.  */
2521
2522 bool
2523 simple_goto_p (tree expr)
2524 {
2525   return (TREE_CODE (expr) == GOTO_EXPR
2526           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2527 }
2528
2529
2530 /* Return true if T should start a new basic block.  PREV_T is the
2531    statement preceding T.  It is used when T is a label or a case label.
2532    Labels should only start a new basic block if their previous statement
2533    wasn't a label.  Otherwise, sequence of labels would generate
2534    unnecessary basic blocks that only contain a single label.  */
2535
2536 static inline bool
2537 stmt_starts_bb_p (tree t, tree prev_t)
2538 {
2539   if (t == NULL_TREE)
2540     return false;
2541
2542   /* LABEL_EXPRs start a new basic block only if the preceding
2543      statement wasn't a label of the same type.  This prevents the
2544      creation of consecutive blocks that have nothing but a single
2545      label.  */
2546   if (TREE_CODE (t) == LABEL_EXPR)
2547     {
2548       /* Nonlocal and computed GOTO targets always start a new block.  */
2549       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2550           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2551         return true;
2552
2553       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2554         {
2555           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2556             return true;
2557
2558           cfg_stats.num_merged_labels++;
2559           return false;
2560         }
2561       else
2562         return true;
2563     }
2564
2565   return false;
2566 }
2567
2568
2569 /* Return true if T should end a basic block.  */
2570
2571 bool
2572 stmt_ends_bb_p (tree t)
2573 {
2574   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2575 }
2576
2577
2578 /* Add gotos that used to be represented implicitly in the CFG.  */
2579
2580 void
2581 disband_implicit_edges (void)
2582 {
2583   basic_block bb;
2584   block_stmt_iterator last;
2585   edge e;
2586   edge_iterator ei;
2587   tree stmt, label;
2588
2589   FOR_EACH_BB (bb)
2590     {
2591       last = bsi_last (bb);
2592       stmt = last_stmt (bb);
2593
2594       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2595         {
2596           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2597              from cfg_remove_useless_stmts here since it violates the
2598              invariants for tree--cfg correspondence and thus fits better
2599              here where we do it anyway.  */
2600           e = find_edge (bb, bb->next_bb);
2601           if (e)
2602             {
2603               if (e->flags & EDGE_TRUE_VALUE)
2604                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2605               else if (e->flags & EDGE_FALSE_VALUE)
2606                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2607               else
2608                 gcc_unreachable ();
2609               e->flags |= EDGE_FALLTHRU;
2610             }
2611
2612           continue;
2613         }
2614
2615       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2616         {
2617           /* Remove the RETURN_EXPR if we may fall though to the exit
2618              instead.  */
2619           gcc_assert (single_succ_p (bb));
2620           gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2621
2622           if (bb->next_bb == EXIT_BLOCK_PTR
2623               && !TREE_OPERAND (stmt, 0))
2624             {
2625               bsi_remove (&last, true);
2626               single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2627             }
2628           continue;
2629         }
2630
2631       /* There can be no fallthru edge if the last statement is a control
2632          one.  */
2633       if (stmt && is_ctrl_stmt (stmt))
2634         continue;
2635
2636       /* Find a fallthru edge and emit the goto if necessary.  */
2637       FOR_EACH_EDGE (e, ei, bb->succs)
2638         if (e->flags & EDGE_FALLTHRU)
2639           break;
2640
2641       if (!e || e->dest == bb->next_bb)
2642         continue;
2643
2644       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2645       label = tree_block_label (e->dest);
2646
2647       stmt = build1 (GOTO_EXPR, void_type_node, label);
2648 #ifdef USE_MAPPED_LOCATION
2649       SET_EXPR_LOCATION (stmt, e->goto_locus);
2650 #else
2651       SET_EXPR_LOCUS (stmt, e->goto_locus);
2652 #endif
2653       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2654       e->flags &= ~EDGE_FALLTHRU;
2655     }
2656 }
2657
2658 /* Remove block annotations and other datastructures.  */
2659
2660 void
2661 delete_tree_cfg_annotations (void)
2662 {
2663   label_to_block_map = NULL;
2664 }
2665
2666
2667 /* Return the first statement in basic block BB.  */
2668
2669 tree
2670 first_stmt (basic_block bb)
2671 {
2672   block_stmt_iterator i = bsi_start (bb);
2673   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2674 }
2675
2676
2677 /* Return the last statement in basic block BB.  */
2678
2679 tree
2680 last_stmt (basic_block bb)
2681 {
2682   block_stmt_iterator b = bsi_last (bb);
2683   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2684 }
2685
2686
2687 /* Return a pointer to the last statement in block BB.  */
2688
2689 tree *
2690 last_stmt_ptr (basic_block bb)
2691 {
2692   block_stmt_iterator last = bsi_last (bb);
2693   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2694 }
2695
2696
2697 /* Return the last statement of an otherwise empty block.  Return NULL
2698    if the block is totally empty, or if it contains more than one
2699    statement.  */
2700
2701 tree
2702 last_and_only_stmt (basic_block bb)
2703 {
2704   block_stmt_iterator i = bsi_last (bb);
2705   tree last, prev;
2706
2707   if (bsi_end_p (i))
2708     return NULL_TREE;
2709
2710   last = bsi_stmt (i);
2711   bsi_prev (&i);
2712   if (bsi_end_p (i))
2713     return last;
2714
2715   /* Empty statements should no longer appear in the instruction stream.
2716      Everything that might have appeared before should be deleted by
2717      remove_useless_stmts, and the optimizers should just bsi_remove
2718      instead of smashing with build_empty_stmt.
2719
2720      Thus the only thing that should appear here in a block containing
2721      one executable statement is a label.  */
2722   prev = bsi_stmt (i);
2723   if (TREE_CODE (prev) == LABEL_EXPR)
2724     return last;
2725   else
2726     return NULL_TREE;
2727 }
2728
2729
2730 /* Mark BB as the basic block holding statement T.  */
2731
2732 void
2733 set_bb_for_stmt (tree t, basic_block bb)
2734 {
2735   if (TREE_CODE (t) == PHI_NODE)
2736     PHI_BB (t) = bb;
2737   else if (TREE_CODE (t) == STATEMENT_LIST)
2738     {
2739       tree_stmt_iterator i;
2740       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2741         set_bb_for_stmt (tsi_stmt (i), bb);
2742     }
2743   else
2744     {
2745       stmt_ann_t ann = get_stmt_ann (t);
2746       ann->bb = bb;
2747
2748       /* If the statement is a label, add the label to block-to-labels map
2749         so that we can speed up edge creation for GOTO_EXPRs.  */
2750       if (TREE_CODE (t) == LABEL_EXPR)
2751         {
2752           int uid;
2753
2754           t = LABEL_EXPR_LABEL (t);
2755           uid = LABEL_DECL_UID (t);
2756           if (uid == -1)
2757             {
2758               unsigned old_len = VEC_length (basic_block, label_to_block_map);
2759               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2760               if (old_len <= (unsigned) uid)
2761                 {
2762                   basic_block *addr;
2763                   unsigned new_len = 3 * uid / 2;
2764
2765                   VEC_safe_grow (basic_block, gc, label_to_block_map,
2766                                  new_len);
2767                   addr = VEC_address (basic_block, label_to_block_map);
2768                   memset (&addr[old_len],
2769                           0, sizeof (basic_block) * (new_len - old_len));
2770                 }
2771             }
2772           else
2773             /* We're moving an existing label.  Make sure that we've
2774                 removed it from the old block.  */
2775             gcc_assert (!bb
2776                         || !VEC_index (basic_block, label_to_block_map, uid));
2777           VEC_replace (basic_block, label_to_block_map, uid, bb);
2778         }
2779     }
2780 }
2781
2782 /* Finds iterator for STMT.  */
2783
2784 extern block_stmt_iterator
2785 bsi_for_stmt (tree stmt)
2786 {
2787   block_stmt_iterator bsi;
2788
2789   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2790     if (bsi_stmt (bsi) == stmt)
2791       return bsi;
2792
2793   gcc_unreachable ();
2794 }
2795
2796 /* Mark statement T as modified, and update it.  */
2797 static inline void
2798 update_modified_stmts (tree t)
2799 {
2800   if (TREE_CODE (t) == STATEMENT_LIST)
2801     {
2802       tree_stmt_iterator i;
2803       tree stmt;
2804       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2805         {
2806           stmt = tsi_stmt (i);
2807           update_stmt_if_modified (stmt);
2808         }
2809     }
2810   else
2811     update_stmt_if_modified (t);
2812 }
2813
2814 /* Insert statement (or statement list) T before the statement
2815    pointed-to by iterator I.  M specifies how to update iterator I
2816    after insertion (see enum bsi_iterator_update).  */
2817
2818 void
2819 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2820 {
2821   set_bb_for_stmt (t, i->bb);
2822   update_modified_stmts (t);
2823   tsi_link_before (&i->tsi, t, m);
2824 }
2825
2826
2827 /* Insert statement (or statement list) T after the statement
2828    pointed-to by iterator I.  M specifies how to update iterator I
2829    after insertion (see enum bsi_iterator_update).  */
2830
2831 void
2832 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2833 {
2834   set_bb_for_stmt (t, i->bb);
2835   update_modified_stmts (t);
2836   tsi_link_after (&i->tsi, t, m);
2837 }
2838
2839
2840 /* Remove the statement pointed to by iterator I.  The iterator is updated
2841    to the next statement. 
2842
2843    When REMOVE_EH_INFO is true we remove the statement pointed to by
2844    iterator I from the EH tables.  Otherwise we do not modify the EH
2845    tables.
2846
2847    Generally, REMOVE_EH_INFO should be true when the statement is going to
2848    be removed from the IL and not reinserted elsewhere.  */
2849
2850 void
2851 bsi_remove (block_stmt_iterator *i, bool remove_eh_info)
2852 {
2853   tree t = bsi_stmt (*i);
2854   set_bb_for_stmt (t, NULL);
2855   delink_stmt_imm_use (t);
2856   tsi_delink (&i->tsi);
2857   mark_stmt_modified (t);
2858   if (remove_eh_info)
2859     remove_stmt_from_eh_region (t);
2860 }
2861
2862
2863 /* Move the statement at FROM so it comes right after the statement at TO.  */
2864
2865 void 
2866 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2867 {
2868   tree stmt = bsi_stmt (*from);
2869   bsi_remove (from, false);
2870   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2871
2872
2873
2874 /* Move the statement at FROM so it comes right before the statement at TO.  */
2875
2876 void 
2877 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2878 {
2879   tree stmt = bsi_stmt (*from);
2880   bsi_remove (from, false);
2881   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2882 }
2883
2884
2885 /* Move the statement at FROM to the end of basic block BB.  */
2886
2887 void
2888 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2889 {
2890   block_stmt_iterator last = bsi_last (bb);
2891   
2892   /* Have to check bsi_end_p because it could be an empty block.  */
2893   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2894     bsi_move_before (from, &last);
2895   else
2896     bsi_move_after (from, &last);
2897 }
2898
2899
2900 /* Replace the contents of the statement pointed to by iterator BSI
2901    with STMT.  If UPDATE_EH_INFO is true, the exception handling
2902    information of the original statement is moved to the new statement.  */
2903   
2904
2905 void
2906 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
2907 {
2908   int eh_region;
2909   tree orig_stmt = bsi_stmt (*bsi);
2910
2911   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2912   set_bb_for_stmt (stmt, bsi->bb);
2913
2914   /* Preserve EH region information from the original statement, if
2915      requested by the caller.  */
2916   if (update_eh_info)
2917     {
2918       eh_region = lookup_stmt_eh_region (orig_stmt);
2919       if (eh_region >= 0)
2920         {
2921           remove_stmt_from_eh_region (orig_stmt);
2922           add_stmt_to_eh_region (stmt, eh_region);
2923         }
2924     }
2925
2926   delink_stmt_imm_use (orig_stmt);
2927   *bsi_stmt_ptr (*bsi) = stmt;
2928   mark_stmt_modified (stmt);
2929   update_modified_stmts (stmt);
2930 }
2931
2932
2933 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2934    is made to place the statement in an existing basic block, but
2935    sometimes that isn't possible.  When it isn't possible, the edge is
2936    split and the statement is added to the new block.
2937
2938    In all cases, the returned *BSI points to the correct location.  The
2939    return value is true if insertion should be done after the location,
2940    or false if it should be done before the location.  If new basic block
2941    has to be created, it is stored in *NEW_BB.  */
2942
2943 static bool
2944 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2945                            basic_block *new_bb)
2946 {
2947   basic_block dest, src;
2948   tree tmp;
2949
2950   dest = e->dest;
2951  restart:
2952
2953   /* If the destination has one predecessor which has no PHI nodes,
2954      insert there.  Except for the exit block. 
2955
2956      The requirement for no PHI nodes could be relaxed.  Basically we
2957      would have to examine the PHIs to prove that none of them used
2958      the value set by the statement we want to insert on E.  That
2959      hardly seems worth the effort.  */
2960   if (single_pred_p (dest)
2961       && ! phi_nodes (dest)
2962       && dest != EXIT_BLOCK_PTR)
2963     {
2964       *bsi = bsi_start (dest);
2965       if (bsi_end_p (*bsi))
2966         return true;
2967
2968       /* Make sure we insert after any leading labels.  */
2969       tmp = bsi_stmt (*bsi);
2970       while (TREE_CODE (tmp) == LABEL_EXPR)
2971         {
2972           bsi_next (bsi);
2973           if (bsi_end_p (*bsi))
2974             break;
2975           tmp = bsi_stmt (*bsi);
2976         }
2977
2978       if (bsi_end_p (*bsi))
2979         {
2980           *bsi = bsi_last (dest);
2981           return true;
2982         }
2983       else
2984         return false;
2985     }
2986
2987   /* If the source has one successor, the edge is not abnormal and
2988      the last statement does not end a basic block, insert there.
2989      Except for the entry block.  */
2990   src = e->src;
2991   if ((e->flags & EDGE_ABNORMAL) == 0
2992       && single_succ_p (src)
2993       && src != ENTRY_BLOCK_PTR)
2994     {
2995       *bsi = bsi_last (src);
2996       if (bsi_end_p (*bsi))
2997         return true;
2998
2999       tmp = bsi_stmt (*bsi);
3000       if (!stmt_ends_bb_p (tmp))
3001         return true;
3002
3003       /* Insert code just before returning the value.  We may need to decompose
3004          the return in the case it contains non-trivial operand.  */
3005       if (TREE_CODE (tmp) == RETURN_EXPR)
3006         {
3007           tree op = TREE_OPERAND (tmp, 0);
3008           if (op && !is_gimple_val (op))
3009             {
3010               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
3011               bsi_insert_before (bsi, op, BSI_NEW_STMT);
3012               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
3013             }
3014           bsi_prev (bsi);
3015           return true;
3016         }
3017     }
3018
3019   /* Otherwise, create a new basic block, and split this edge.  */
3020   dest = split_edge (e);
3021   if (new_bb)
3022     *new_bb = dest;
3023   e = single_pred_edge (dest);
3024   goto restart;
3025 }
3026
3027
3028 /* This routine will commit all pending edge insertions, creating any new
3029    basic blocks which are necessary.  */
3030
3031 void
3032 bsi_commit_edge_inserts (void)
3033 {
3034   basic_block bb;
3035   edge e;
3036   edge_iterator ei;
3037
3038   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
3039
3040   FOR_EACH_BB (bb)
3041     FOR_EACH_EDGE (e, ei, bb->succs)
3042       bsi_commit_one_edge_insert (e, NULL);
3043 }
3044
3045
3046 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3047    to this block, otherwise set it to NULL.  */
3048
3049 void
3050 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3051 {
3052   if (new_bb)
3053     *new_bb = NULL;
3054   if (PENDING_STMT (e))
3055     {
3056       block_stmt_iterator bsi;
3057       tree stmt = PENDING_STMT (e);
3058
3059       PENDING_STMT (e) = NULL_TREE;
3060
3061       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3062         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3063       else
3064         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3065     }
3066 }
3067
3068
3069 /* Add STMT to the pending list of edge E.  No actual insertion is
3070    made until a call to bsi_commit_edge_inserts () is made.  */
3071
3072 void
3073 bsi_insert_on_edge (edge e, tree stmt)
3074 {
3075   append_to_statement_list (stmt, &PENDING_STMT (e));
3076 }
3077
3078 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
3079    block has to be created, it is returned.  */
3080
3081 basic_block
3082 bsi_insert_on_edge_immediate (edge e, tree stmt)
3083 {
3084   block_stmt_iterator bsi;
3085   basic_block new_bb = NULL;
3086
3087   gcc_assert (!PENDING_STMT (e));
3088
3089   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3090     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3091   else
3092     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3093
3094   return new_bb;
3095 }
3096
3097 /*---------------------------------------------------------------------------
3098              Tree specific functions for CFG manipulation
3099 ---------------------------------------------------------------------------*/
3100
3101 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3102
3103 static void
3104 reinstall_phi_args (edge new_edge, edge old_edge)
3105 {
3106   tree var, phi;
3107
3108   if (!PENDING_STMT (old_edge))
3109     return;
3110   
3111   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3112        var && phi;
3113        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3114     {
3115       tree result = TREE_PURPOSE (var);
3116       tree arg = TREE_VALUE (var);
3117
3118       gcc_assert (result == PHI_RESULT (phi));
3119
3120       add_phi_arg (phi, arg, new_edge);
3121     }
3122
3123   PENDING_STMT (old_edge) = NULL;
3124 }
3125
3126 /* Returns the basic block after that the new basic block created
3127    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
3128    near its "logical" location.  This is of most help to humans looking
3129    at debugging dumps.  */
3130
3131 static basic_block
3132 split_edge_bb_loc (edge edge_in)
3133 {
3134   basic_block dest = edge_in->dest;
3135
3136   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3137     return edge_in->src;
3138   else
3139     return dest->prev_bb;
3140 }
3141
3142 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3143    Abort on abnormal edges.  */
3144
3145 static basic_block
3146 tree_split_edge (edge edge_in)
3147 {
3148   basic_block new_bb, after_bb, dest, src;
3149   edge new_edge, e;
3150
3151   /* Abnormal edges cannot be split.  */
3152   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3153
3154   src = edge_in->src;
3155   dest = edge_in->dest;
3156
3157   after_bb = split_edge_bb_loc (edge_in);
3158
3159   new_bb = create_empty_bb (after_bb);
3160   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3161   new_bb->count = edge_in->count;
3162   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3163   new_edge->probability = REG_BR_PROB_BASE;
3164   new_edge->count = edge_in->count;
3165
3166   e = redirect_edge_and_branch (edge_in, new_bb);
3167   gcc_assert (e);
3168   reinstall_phi_args (new_edge, e);
3169
3170   return new_bb;
3171 }
3172
3173
3174 /* Return true when BB has label LABEL in it.  */
3175
3176 static bool
3177 has_label_p (basic_block bb, tree label)
3178 {
3179   block_stmt_iterator bsi;
3180
3181   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3182     {
3183       tree stmt = bsi_stmt (bsi);
3184
3185       if (TREE_CODE (stmt) != LABEL_EXPR)
3186         return false;
3187       if (LABEL_EXPR_LABEL (stmt) == label)
3188         return true;
3189     }
3190   return false;
3191 }
3192
3193
3194 /* Callback for walk_tree, check that all elements with address taken are
3195    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3196    inside a PHI node.  */
3197
3198 static tree
3199 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3200 {
3201   tree t = *tp, x;
3202   bool in_phi = (data != NULL);
3203
3204   if (TYPE_P (t))
3205     *walk_subtrees = 0;
3206   
3207   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3208 #define CHECK_OP(N, MSG) \
3209   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3210        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3211
3212   switch (TREE_CODE (t))
3213     {
3214     case SSA_NAME:
3215       if (SSA_NAME_IN_FREE_LIST (t))
3216         {
3217           error ("SSA name in freelist but still referenced");
3218           return *tp;
3219         }
3220       break;
3221
3222     case ASSERT_EXPR:
3223       x = fold (ASSERT_EXPR_COND (t));
3224       if (x == boolean_false_node)
3225         {
3226           error ("ASSERT_EXPR with an always-false condition");
3227           return *tp;
3228         }
3229       break;
3230
3231     case MODIFY_EXPR:
3232       x = TREE_OPERAND (t, 0);
3233       if (TREE_CODE (x) == BIT_FIELD_REF
3234           && is_gimple_reg (TREE_OPERAND (x, 0)))
3235         {
3236           error ("GIMPLE register modified with BIT_FIELD_REF");
3237           return t;
3238         }
3239       break;
3240
3241     case ADDR_EXPR:
3242       {
3243         bool old_invariant;
3244         bool old_constant;
3245         bool old_side_effects;
3246         bool new_invariant;
3247         bool new_constant;
3248         bool new_side_effects;
3249
3250         /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
3251            dead PHIs that take the address of something.  But if the PHI
3252            result is dead, the fact that it takes the address of anything
3253            is irrelevant.  Because we can not tell from here if a PHI result
3254            is dead, we just skip this check for PHIs altogether.  This means
3255            we may be missing "valid" checks, but what can you do?
3256            This was PR19217.  */
3257         if (in_phi)
3258           break;
3259
3260         old_invariant = TREE_INVARIANT (t);
3261         old_constant = TREE_CONSTANT (t);
3262         old_side_effects = TREE_SIDE_EFFECTS (t);
3263
3264         recompute_tree_invariant_for_addr_expr (t);
3265         new_invariant = TREE_INVARIANT (t);
3266         new_side_effects = TREE_SIDE_EFFECTS (t);
3267         new_constant = TREE_CONSTANT (t);
3268
3269         if (old_invariant != new_invariant)
3270           {
3271             error ("invariant not recomputed when ADDR_EXPR changed");
3272             return t;
3273           }
3274
3275         if (old_constant != new_constant)
3276           {
3277             error ("constant not recomputed when ADDR_EXPR changed");
3278             return t;
3279           }
3280         if (old_side_effects != new_side_effects)
3281           {
3282             error ("side effects not recomputed when ADDR_EXPR changed");
3283             return t;
3284           }
3285
3286         /* Skip any references (they will be checked when we recurse down the
3287            tree) and ensure that any variable used as a prefix is marked
3288            addressable.  */
3289         for (x = TREE_OPERAND (t, 0);
3290              handled_component_p (x);
3291              x = TREE_OPERAND (x, 0))
3292           ;
3293
3294         if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3295           return NULL;
3296         if (!TREE_ADDRESSABLE (x))
3297           {
3298             error ("address taken, but ADDRESSABLE bit not set");
3299             return x;
3300           }
3301         break;
3302       }
3303
3304     case COND_EXPR:
3305       x = COND_EXPR_COND (t);
3306       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3307         {
3308           error ("non-boolean used in condition");
3309           return x;
3310         }
3311       if (!is_gimple_condexpr (x))
3312         {
3313           error ("invalid conditional operand");
3314           return x;
3315         }
3316       break;
3317
3318     case NOP_EXPR:
3319     case CONVERT_EXPR:
3320     case FIX_TRUNC_EXPR:
3321     case FIX_CEIL_EXPR:
3322     case FIX_FLOOR_EXPR:
3323     case FIX_ROUND_EXPR:
3324     case FLOAT_EXPR:
3325     case NEGATE_EXPR:
3326     case ABS_EXPR:
3327     case BIT_NOT_EXPR:
3328     case NON_LVALUE_EXPR:
3329     case TRUTH_NOT_EXPR:
3330       CHECK_OP (0, "invalid operand to unary operator");
3331       break;
3332
3333     case REALPART_EXPR:
3334     case IMAGPART_EXPR:
3335     case COMPONENT_REF:
3336     case ARRAY_REF:
3337     case ARRAY_RANGE_REF:
3338     case BIT_FIELD_REF:
3339     case VIEW_CONVERT_EXPR:
3340       /* We have a nest of references.  Verify that each of the operands
3341          that determine where to reference is either a constant or a variable,
3342          verify that the base is valid, and then show we've already checked
3343          the subtrees.  */
3344       while (handled_component_p (t))
3345         {
3346           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3347             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3348           else if (TREE_CODE (t) == ARRAY_REF
3349                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3350             {
3351               CHECK_OP (1, "invalid array index");
3352               if (TREE_OPERAND (t, 2))
3353                 CHECK_OP (2, "invalid array lower bound");
3354               if (TREE_OPERAND (t, 3))
3355                 CHECK_OP (3, "invalid array stride");
3356             }
3357           else if (TREE_CODE (t) == BIT_FIELD_REF)
3358             {
3359               CHECK_OP (1, "invalid operand to BIT_FIELD_REF");
3360               CHECK_OP (2, "invalid operand to BIT_FIELD_REF");
3361             }
3362
3363           t = TREE_OPERAND (t, 0);
3364         }
3365
3366       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3367         {
3368           error ("invalid reference prefix");
3369           return t;
3370         }
3371       *walk_subtrees = 0;
3372       break;
3373
3374     case LT_EXPR:
3375     case LE_EXPR:
3376     case GT_EXPR:
3377     case GE_EXPR:
3378     case EQ_EXPR:
3379     case NE_EXPR:
3380     case UNORDERED_EXPR:
3381     case ORDERED_EXPR:
3382     case UNLT_EXPR:
3383     case UNLE_EXPR:
3384     case UNGT_EXPR:
3385     case UNGE_EXPR:
3386     case UNEQ_EXPR:
3387     case LTGT_EXPR:
3388     case PLUS_EXPR:
3389     case MINUS_EXPR:
3390     case MULT_EXPR:
3391     case TRUNC_DIV_EXPR:
3392     case CEIL_DIV_EXPR:
3393     case FLOOR_DIV_EXPR:
3394     case ROUND_DIV_EXPR:
3395     case TRUNC_MOD_EXPR:
3396     case CEIL_MOD_EXPR:
3397     case FLOOR_MOD_EXPR:
3398     case ROUND_MOD_EXPR:
3399     case RDIV_EXPR:
3400     case EXACT_DIV_EXPR:
3401     case MIN_EXPR:
3402     case MAX_EXPR:
3403     case LSHIFT_EXPR:
3404     case RSHIFT_EXPR:
3405     case LROTATE_EXPR:
3406     case RROTATE_EXPR:
3407     case BIT_IOR_EXPR:
3408     case BIT_XOR_EXPR:
3409     case BIT_AND_EXPR:
3410       CHECK_OP (0, "invalid operand to binary operator");
3411       CHECK_OP (1, "invalid operand to binary operator");
3412       break;
3413
3414     default:
3415       break;
3416     }
3417   return NULL;
3418
3419 #undef CHECK_OP
3420 }
3421
3422
3423 /* Verify STMT, return true if STMT is not in GIMPLE form.
3424    TODO: Implement type checking.  */
3425
3426 static bool
3427 verify_stmt (tree stmt, bool last_in_block)
3428 {
3429   tree addr;
3430
3431   if (OMP_DIRECTIVE_P (stmt))
3432     {
3433       /* OpenMP directives are validated by the FE and never operated
3434          on by the optimizers.  Furthermore, OMP_FOR may contain
3435          non-gimple expressions when the main index variable has had
3436          its address taken.  This does not affect the loop itself
3437          because the header of an OMP_FOR is merely used to determine
3438          how to setup the parallel iteration.  */
3439       return false;
3440     }
3441
3442   if (!is_gimple_stmt (stmt))
3443     {
3444       error ("is not a valid GIMPLE statement");
3445       goto fail;
3446     }
3447
3448   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3449   if (addr)
3450     {
3451       debug_generic_stmt (addr);
3452       return true;
3453     }
3454
3455   /* If the statement is marked as part of an EH region, then it is
3456      expected that the statement could throw.  Verify that when we
3457      have optimizations that simplify statements such that we prove
3458      that they cannot throw, that we update other data structures
3459      to match.  */
3460   if (lookup_stmt_eh_region (stmt) >= 0)
3461     {
3462       if (!tree_could_throw_p (stmt))
3463         {
3464           error ("statement marked for throw, but doesn%'t");
3465           goto fail;
3466         }
3467       if (!last_in_block && tree_can_throw_internal (stmt))
3468         {
3469           error ("statement marked for throw in middle of block");
3470           goto fail;
3471         }
3472     }
3473
3474   return false;
3475
3476  fail:
3477   debug_generic_stmt (stmt);
3478   return true;
3479 }
3480
3481
3482 /* Return true when the T can be shared.  */
3483
3484 static bool
3485 tree_node_can_be_shared (tree t)
3486 {
3487   if (IS_TYPE_OR_DECL_P (t)
3488       || is_gimple_min_invariant (t)
3489       || TREE_CODE (t) == SSA_NAME
3490       || t == error_mark_node
3491       || TREE_CODE (t) == IDENTIFIER_NODE)
3492     return true;
3493
3494   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3495     return true;
3496
3497   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3498            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
3499          || TREE_CODE (t) == COMPONENT_REF
3500          || TREE_CODE (t) == REALPART_EXPR
3501          || TREE_CODE (t) == IMAGPART_EXPR)
3502     t = TREE_OPERAND (t, 0);
3503
3504   if (DECL_P (t))
3505     return true;
3506
3507   return false;
3508 }
3509
3510
3511 /* Called via walk_trees.  Verify tree sharing.  */
3512
3513 static tree
3514 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3515 {
3516   htab_t htab = (htab_t) data;
3517   void **slot;
3518
3519   if (tree_node_can_be_shared (*tp))
3520     {
3521       *walk_subtrees = false;
3522       return NULL;
3523     }
3524
3525   slot = htab_find_slot (htab, *tp, INSERT);
3526   if (*slot)
3527     return (tree) *slot;
3528   *slot = *tp;
3529
3530   return NULL;
3531 }
3532
3533
3534 /* Verify the GIMPLE statement chain.  */
3535
3536 void
3537 verify_stmts (void)
3538 {
3539   basic_block bb;
3540   block_stmt_iterator bsi;
3541   bool err = false;
3542   htab_t htab;
3543   tree addr;
3544
3545   timevar_push (TV_TREE_STMT_VERIFY);
3546   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3547
3548   FOR_EACH_BB (bb)
3549     {
3550       tree phi;
3551       int i;
3552
3553       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3554         {
3555           int phi_num_args = PHI_NUM_ARGS (phi);
3556
3557           if (bb_for_stmt (phi) != bb)
3558             {
3559               error ("bb_for_stmt (phi) is set to a wrong basic block");
3560               err |= true;
3561             }
3562
3563           for (i = 0; i < phi_num_args; i++)
3564             {
3565               tree t = PHI_ARG_DEF (phi, i);
3566               tree addr;
3567
3568               /* Addressable variables do have SSA_NAMEs but they
3569                  are not considered gimple values.  */
3570               if (TREE_CODE (t) != SSA_NAME
3571                   && TREE_CODE (t) != FUNCTION_DECL
3572                   && !is_gimple_val (t))
3573                 {
3574                   error ("PHI def is not a GIMPLE value");
3575                   debug_generic_stmt (phi);
3576                   debug_generic_stmt (t);
3577                   err |= true;
3578                 }
3579
3580               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
3581               if (addr)
3582                 {
3583                   debug_generic_stmt (addr);
3584                   err |= true;
3585                 }
3586
3587               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3588               if (addr)
3589                 {
3590                   error ("incorrect sharing of tree nodes");
3591                   debug_generic_stmt (phi);
3592                   debug_generic_stmt (addr);
3593                   err |= true;
3594                 }
3595             }
3596         }
3597
3598       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3599         {
3600           tree stmt = bsi_stmt (bsi);
3601
3602           if (bb_for_stmt (stmt) != bb)
3603             {
3604               error ("bb_for_stmt (stmt) is set to a wrong basic block");
3605               err |= true;
3606             }
3607
3608           bsi_next (&bsi);
3609           err |= verify_stmt (stmt, bsi_end_p (bsi));
3610           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3611           if (addr)
3612             {
3613               error ("incorrect sharing of tree nodes");
3614               debug_generic_stmt (stmt);
3615               debug_generic_stmt (addr);
3616               err |= true;
3617             }
3618         }
3619     }
3620
3621   if (err)
3622     internal_error ("verify_stmts failed");
3623
3624   htab_delete (htab);
3625   timevar_pop (TV_TREE_STMT_VERIFY);
3626 }
3627
3628
3629 /* Verifies that the flow information is OK.  */
3630
3631 static int
3632 tree_verify_flow_info (void)
3633 {
3634   int err = 0;
3635   basic_block bb;
3636   block_stmt_iterator bsi;
3637   tree stmt;
3638   edge e;
3639   edge_iterator ei;
3640
3641   if (ENTRY_BLOCK_PTR->stmt_list)
3642     {
3643       error ("ENTRY_BLOCK has a statement list associated with it");
3644       err = 1;
3645     }
3646
3647   if (EXIT_BLOCK_PTR->stmt_list)
3648     {
3649       error ("EXIT_BLOCK has a statement list associated with it");
3650       err = 1;
3651     }
3652
3653   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3654     if (e->flags & EDGE_FALLTHRU)
3655       {
3656         error ("fallthru to exit from bb %d", e->src->index);
3657         err = 1;
3658       }
3659
3660   FOR_EACH_BB (bb)
3661     {
3662       bool found_ctrl_stmt = false;
3663
3664       stmt = NULL_TREE;
3665
3666       /* Skip labels on the start of basic block.  */
3667       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3668         {
3669           tree prev_stmt = stmt;
3670
3671           stmt = bsi_stmt (bsi);
3672
3673           if (TREE_CODE (stmt) != LABEL_EXPR)
3674             break;
3675
3676           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3677             {
3678               error ("nonlocal label ");
3679               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3680               fprintf (stderr, " is not first in a sequence of labels in bb %d",
3681                        bb->index);
3682               err = 1;
3683             }
3684
3685           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3686             {
3687               error ("label ");
3688               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3689               fprintf (stderr, " to block does not match in bb %d",
3690                        bb->index);
3691               err = 1;
3692             }
3693
3694           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3695               != current_function_decl)
3696             {
3697               error ("label ");
3698               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3699               fprintf (stderr, " has incorrect context in bb %d",
3700                        bb->index);
3701               err = 1;
3702             }
3703         }
3704
3705       /* Verify that body of basic block BB is free of control flow.  */
3706       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3707         {
3708           tree stmt = bsi_stmt (bsi);
3709
3710           if (found_ctrl_stmt)
3711             {
3712               error ("control flow in the middle of basic block %d",
3713                      bb->index);
3714               err = 1;
3715             }
3716
3717           if (stmt_ends_bb_p (stmt))
3718             found_ctrl_stmt = true;
3719
3720           if (TREE_CODE (stmt) == LABEL_EXPR)
3721             {
3722               error ("label ");
3723               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3724               fprintf (stderr, " in the middle of basic block %d", bb->index);
3725               err = 1;
3726             }
3727         }
3728
3729       bsi = bsi_last (bb);
3730       if (bsi_end_p (bsi))
3731         continue;
3732
3733       stmt = bsi_stmt (bsi);
3734
3735       err |= verify_eh_edges (stmt);
3736
3737       if (is_ctrl_stmt (stmt))
3738         {
3739           FOR_EACH_EDGE (e, ei, bb->succs)
3740             if (e->flags & EDGE_FALLTHRU)
3741               {
3742                 error ("fallthru edge after a control statement in bb %d",
3743                        bb->index);
3744                 err = 1;
3745               }
3746         }
3747
3748       switch (TREE_CODE (stmt))
3749         {
3750         case COND_EXPR:
3751           {
3752             edge true_edge;
3753             edge false_edge;
3754             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3755                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3756               {
3757                 error ("structured COND_EXPR at the end of bb %d", bb->index);
3758                 err = 1;
3759               }
3760
3761             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3762
3763             if (!true_edge || !false_edge
3764                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3765                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3766                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3767                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3768                 || EDGE_COUNT (bb->succs) >= 3)
3769               {
3770                 error ("wrong outgoing edge flags at end of bb %d",
3771                        bb->index);
3772                 err = 1;
3773               }
3774
3775             if (!has_label_p (true_edge->dest,
3776                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3777               {
3778                 error ("%<then%> label does not match edge at end of bb %d",
3779                        bb->index);
3780                 err = 1;
3781               }
3782
3783             if (!has_label_p (false_edge->dest,
3784                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3785               {
3786                 error ("%<else%> label does not match edge at end of bb %d",
3787                        bb->index);
3788                 err = 1;
3789               }
3790           }
3791           break;
3792
3793         case GOTO_EXPR:
3794           if (simple_goto_p (stmt))
3795             {
3796               error ("explicit goto at end of bb %d", bb->index);
3797               err = 1;
3798             }
3799           else
3800             {
3801               /* FIXME.  We should double check that the labels in the 
3802                  destination blocks have their address taken.  */
3803               FOR_EACH_EDGE (e, ei, bb->succs)
3804                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3805                                  | EDGE_FALSE_VALUE))
3806                     || !(e->flags & EDGE_ABNORMAL))
3807                   {
3808                     error ("wrong outgoing edge flags at end of bb %d",
3809                            bb->index);
3810                     err = 1;
3811                   }
3812             }
3813           break;
3814
3815         case RETURN_EXPR:
3816           if (!single_succ_p (bb)
3817               || (single_succ_edge (bb)->flags
3818                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
3819                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3820             {
3821               error ("wrong outgoing edge flags at end of bb %d", bb->index);
3822               err = 1;
3823             }
3824           if (single_succ (bb) != EXIT_BLOCK_PTR)
3825             {
3826               error ("return edge does not point to exit in bb %d",
3827                      bb->index);
3828               err = 1;
3829             }
3830           break;
3831
3832         case SWITCH_EXPR:
3833           {
3834             tree prev;
3835             edge e;
3836             size_t i, n;
3837             tree vec;
3838
3839             vec = SWITCH_LABELS (stmt);
3840             n = TREE_VEC_LENGTH (vec);
3841
3842             /* Mark all the destination basic blocks.  */
3843             for (i = 0; i < n; ++i)
3844               {
3845                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3846                 basic_block label_bb = label_to_block (lab);
3847
3848                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3849                 label_bb->aux = (void *)1;
3850               }
3851
3852             /* Verify that the case labels are sorted.  */
3853             prev = TREE_VEC_ELT (vec, 0);
3854             for (i = 1; i < n - 1; ++i)
3855               {
3856                 tree c = TREE_VEC_ELT (vec, i);
3857                 if (! CASE_LOW (c))
3858                   {
3859                     error ("found default case not at end of case vector");
3860                     err = 1;
3861                     continue;
3862                   }
3863                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3864                   {
3865                     error ("case labels not sorted: ");
3866                     print_generic_expr (stderr, prev, 0);
3867                     fprintf (stderr," is greater than ");
3868                     print_generic_expr (stderr, c, 0);
3869                     fprintf (stderr," but comes before it.\n");
3870                     err = 1;
3871                   }
3872                 prev = c;
3873               }
3874             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3875               {
3876                 error ("no default case found at end of case vector");
3877                 err = 1;
3878               }
3879
3880             FOR_EACH_EDGE (e, ei, bb->succs)
3881               {
3882                 if (!e->dest->aux)
3883                   {
3884                     error ("extra outgoing edge %d->%d",
3885                            bb->index, e->dest->index);
3886                     err = 1;
3887                   }
3888                 e->dest->aux = (void *)2;
3889                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3890                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3891                   {
3892                     error ("wrong outgoing edge flags at end of bb %d",
3893                            bb->index);
3894                     err = 1;
3895                   }
3896               }
3897
3898             /* Check that we have all of them.  */
3899             for (i = 0; i < n; ++i)
3900               {
3901                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3902                 basic_block label_bb = label_to_block (lab);
3903
3904                 if (label_bb->aux != (void *)2)
3905                   {
3906                     error ("missing edge %i->%i",
3907                            bb->index, label_bb->index);
3908                     err = 1;
3909                   }
3910               }
3911
3912             FOR_EACH_EDGE (e, ei, bb->succs)
3913               e->dest->aux = (void *)0;
3914           }
3915
3916         default: ;
3917         }
3918     }
3919
3920   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3921     verify_dominators (CDI_DOMINATORS);
3922
3923   return err;
3924 }
3925
3926
3927 /* Updates phi nodes after creating a forwarder block joined
3928    by edge FALLTHRU.  */
3929
3930 static void
3931 tree_make_forwarder_block (edge fallthru)
3932 {
3933   edge e;
3934   edge_iterator ei;
3935   basic_block dummy, bb;
3936   tree phi, new_phi, var;
3937
3938   dummy = fallthru->src;
3939   bb = fallthru->dest;
3940
3941   if (single_pred_p (bb))
3942     return;
3943
3944   /* If we redirected a branch we must create new phi nodes at the
3945      start of BB.  */
3946   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3947     {
3948       var = PHI_RESULT (phi);
3949       new_phi = create_phi_node (var, bb);
3950       SSA_NAME_DEF_STMT (var) = new_phi;
3951       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3952       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3953     }
3954
3955   /* Ensure that the PHI node chain is in the same order.  */
3956   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3957
3958   /* Add the arguments we have stored on edges.  */
3959   FOR_EACH_EDGE (e, ei, bb->preds)
3960     {
3961       if (e == fallthru)
3962         continue;
3963
3964       flush_pending_stmts (e);
3965     }
3966 }
3967
3968
3969 /* Return a non-special label in the head of basic block BLOCK.
3970    Create one if it doesn't exist.  */
3971
3972 tree
3973 tree_block_label (basic_block bb)
3974 {
3975   block_stmt_iterator i, s = bsi_start (bb);
3976   bool first = true;
3977   tree label, stmt;
3978
3979   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
3980     {
3981       stmt = bsi_stmt (i);
3982       if (TREE_CODE (stmt) != LABEL_EXPR)
3983         break;
3984       label = LABEL_EXPR_LABEL (stmt);
3985       if (!DECL_NONLOCAL (label))
3986         {
3987           if (!first)
3988             bsi_move_before (&i, &s);
3989           return label;
3990         }
3991     }
3992
3993   label = create_artificial_label ();
3994   stmt = build1 (LABEL_EXPR, void_type_node, label);
3995   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
3996   return label;
3997 }
3998
3999
4000 /* Attempt to perform edge redirection by replacing a possibly complex
4001    jump instruction by a goto or by removing the jump completely.
4002    This can apply only if all edges now point to the same block.  The
4003    parameters and return values are equivalent to
4004    redirect_edge_and_branch.  */
4005
4006 static edge
4007 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4008 {
4009   basic_block src = e->src;
4010   block_stmt_iterator b;
4011   tree stmt;
4012
4013   /* We can replace or remove a complex jump only when we have exactly
4014      two edges.  */
4015   if (EDGE_COUNT (src->succs) != 2
4016       /* Verify that all targets will be TARGET.  Specifically, the
4017          edge that is not E must also go to TARGET.  */
4018       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4019     return NULL;
4020
4021   b = bsi_last (src);
4022   if (bsi_end_p (b))
4023     return NULL;
4024   stmt = bsi_stmt (b);
4025
4026   if (TREE_CODE (stmt) == COND_EXPR
4027       || TREE_CODE (stmt) == SWITCH_EXPR)
4028     {
4029       bsi_remove (&b, true);
4030       e = ssa_redirect_edge (e, target);
4031       e->flags = EDGE_FALLTHRU;
4032       return e;
4033     }
4034
4035   return NULL;
4036 }
4037
4038
4039 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4040    edge representing the redirected branch.  */
4041
4042 static edge
4043 tree_redirect_edge_and_branch (edge e, basic_block dest)
4044 {
4045   basic_block bb = e->src;
4046   block_stmt_iterator bsi;
4047   edge ret;
4048   tree label, stmt;
4049
4050   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4051     return NULL;
4052
4053   if (e->src != ENTRY_BLOCK_PTR 
4054       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4055     return ret;
4056
4057   if (e->dest == dest)
4058     return NULL;
4059
4060   label = tree_block_label (dest);
4061
4062   bsi = bsi_last (bb);
4063   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4064
4065   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4066     {
4067     case COND_EXPR:
4068       stmt = (e->flags & EDGE_TRUE_VALUE
4069               ? COND_EXPR_THEN (stmt)
4070               : COND_EXPR_ELSE (stmt));
4071       GOTO_DESTINATION (stmt) = label;
4072       break;
4073
4074     case GOTO_EXPR:
4075       /* No non-abnormal edges should lead from a non-simple goto, and
4076          simple ones should be represented implicitly.  */
4077       gcc_unreachable ();
4078
4079     case SWITCH_EXPR:
4080       {
4081         tree cases = get_cases_for_edge (e, stmt);
4082
4083         /* If we have a list of cases associated with E, then use it
4084            as it's a lot faster than walking the entire case vector.  */
4085         if (cases)
4086           {
4087             edge e2 = find_edge (e->src, dest);
4088             tree last, first;
4089
4090             first = cases;
4091             while (cases)
4092               {
4093                 last = cases;
4094                 CASE_LABEL (cases) = label;
4095                 cases = TREE_CHAIN (cases);
4096               }
4097
4098             /* If there was already an edge in the CFG, then we need
4099                to move all the cases associated with E to E2.  */
4100             if (e2)
4101               {
4102                 tree cases2 = get_cases_for_edge (e2, stmt);
4103
4104                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4105                 TREE_CHAIN (cases2) = first;
4106               }
4107           }
4108         else
4109           {
4110             tree vec = SWITCH_LABELS (stmt);
4111             size_t i, n = TREE_VEC_LENGTH (vec);
4112
4113             for (i = 0; i < n; i++)
4114               {
4115                 tree elt = TREE_VEC_ELT (vec, i);
4116
4117                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4118                   CASE_LABEL (elt) = label;
4119               }
4120           }
4121
4122         break;
4123       }
4124
4125     case RETURN_EXPR:
4126       bsi_remove (&bsi, true);
4127       e->flags |= EDGE_FALLTHRU;
4128       break;
4129
4130     default:
4131       /* Otherwise it must be a fallthru edge, and we don't need to
4132          do anything besides redirecting it.  */
4133       gcc_assert (e->flags & EDGE_FALLTHRU);
4134       break;
4135     }
4136
4137   /* Update/insert PHI nodes as necessary.  */
4138
4139   /* Now update the edges in the CFG.  */
4140   e = ssa_redirect_edge (e, dest);
4141
4142   return e;
4143 }
4144
4145
4146 /* Simple wrapper, as we can always redirect fallthru edges.  */
4147
4148 static basic_block
4149 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4150 {
4151   e = tree_redirect_edge_and_branch (e, dest);
4152   gcc_assert (e);
4153
4154   return NULL;
4155 }
4156
4157
4158 /* Splits basic block BB after statement STMT (but at least after the
4159    labels).  If STMT is NULL, BB is split just after the labels.  */
4160
4161 static basic_block
4162 tree_split_block (basic_block bb, void *stmt)
4163 {
4164   block_stmt_iterator bsi, bsi_tgt;
4165   tree act;
4166   basic_block new_bb;
4167   edge e;
4168   edge_iterator ei;
4169
4170   new_bb = create_empty_bb (bb);
4171
4172   /* Redirect the outgoing edges.  */
4173   new_bb->succs = bb->succs;
4174   bb->succs = NULL;
4175   FOR_EACH_EDGE (e, ei, new_bb->succs)
4176     e->src = new_bb;
4177
4178   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4179     stmt = NULL;
4180
4181   /* Move everything from BSI to the new basic block.  */
4182   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4183     {
4184       act = bsi_stmt (bsi);
4185       if (TREE_CODE (act) == LABEL_EXPR)
4186         continue;
4187
4188       if (!stmt)
4189         break;
4190
4191       if (stmt == act)
4192         {
4193           bsi_next (&bsi);
4194           break;
4195         }
4196     }
4197
4198   bsi_tgt = bsi_start (new_bb);
4199   while (!bsi_end_p (bsi))
4200     {
4201       act = bsi_stmt (bsi);
4202       bsi_remove (&bsi, false);
4203       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4204     }
4205
4206   return new_bb;
4207 }
4208
4209
4210 /* Moves basic block BB after block AFTER.  */
4211
4212 static bool
4213 tree_move_block_after (basic_block bb, basic_block after)
4214 {
4215   if (bb->prev_bb == after)
4216     return true;
4217
4218   unlink_block (bb);
4219   link_block (bb, after);
4220
4221   return true;
4222 }
4223
4224
4225 /* Return true if basic_block can be duplicated.  */
4226
4227 static bool
4228 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4229 {
4230   return true;
4231 }
4232
4233
4234 /* Create a duplicate of the basic block BB.  NOTE: This does not
4235    preserve SSA form.  */
4236
4237 static basic_block
4238 tree_duplicate_bb (basic_block bb)
4239 {
4240   basic_block new_bb;
4241   block_stmt_iterator bsi, bsi_tgt;
4242   tree phi;
4243
4244   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4245
4246   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4247      the incoming edges have not been setup yet.  */
4248   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4249     {
4250       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4251       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4252     }
4253
4254   /* Keep the chain of PHI nodes in the same order so that they can be
4255      updated by ssa_redirect_edge.  */
4256   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4257
4258   bsi_tgt = bsi_start (new_bb);
4259   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4260     {
4261       def_operand_p def_p;
4262       ssa_op_iter op_iter;
4263       tree stmt, copy;
4264       int region;
4265
4266       stmt = bsi_stmt (bsi);
4267       if (TREE_CODE (stmt) == LABEL_EXPR)
4268         continue;
4269
4270       /* Create a new copy of STMT and duplicate STMT's virtual
4271          operands.  */
4272       copy = unshare_expr (stmt);
4273       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4274       copy_virtual_operands (copy, stmt);
4275       region = lookup_stmt_eh_region (stmt);
4276       if (region >= 0)
4277         add_stmt_to_eh_region (copy, region);
4278
4279       /* Create new names for all the definitions created by COPY and
4280          add replacement mappings for each new name.  */
4281       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4282         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4283     }
4284
4285   return new_bb;
4286 }
4287
4288
4289 /* Basic block BB_COPY was created by code duplication.  Add phi node
4290    arguments for edges going out of BB_COPY.  The blocks that were
4291    duplicated have BB_DUPLICATED set.  */
4292
4293 void
4294 add_phi_args_after_copy_bb (basic_block bb_copy)
4295 {
4296   basic_block bb, dest;
4297   edge e, e_copy;
4298   edge_iterator ei;
4299   tree phi, phi_copy, phi_next, def;
4300       
4301   bb = get_bb_original (bb_copy);
4302
4303   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4304     {
4305       if (!phi_nodes (e_copy->dest))
4306         continue;
4307
4308       if (e_copy->dest->flags & BB_DUPLICATED)
4309         dest = get_bb_original (e_copy->dest);
4310       else
4311         dest = e_copy->dest;
4312
4313       e = find_edge (bb, dest);
4314       if (!e)
4315         {
4316           /* During loop unrolling the target of the latch edge is copied.
4317              In this case we are not looking for edge to dest, but to
4318              duplicated block whose original was dest.  */
4319           FOR_EACH_EDGE (e, ei, bb->succs)
4320             if ((e->dest->flags & BB_DUPLICATED)
4321                 && get_bb_original (e->dest) == dest)
4322               break;
4323
4324           gcc_assert (e != NULL);
4325         }
4326
4327       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4328            phi;
4329            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4330         {
4331           phi_next = PHI_CHAIN (phi);
4332           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4333           add_phi_arg (phi_copy, def, e_copy);
4334         }
4335     }
4336 }
4337
4338 /* Blocks in REGION_COPY array of length N_REGION were created by
4339    duplication of basic blocks.  Add phi node arguments for edges
4340    going from these blocks.  */
4341
4342 void
4343 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4344 {
4345   unsigned i;
4346
4347   for (i = 0; i < n_region; i++)
4348     region_copy[i]->flags |= BB_DUPLICATED;
4349
4350   for (i = 0; i < n_region; i++)
4351     add_phi_args_after_copy_bb (region_copy[i]);
4352
4353   for (i = 0; i < n_region; i++)
4354     region_copy[i]->flags &= ~BB_DUPLICATED;
4355 }
4356
4357 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4358    important exit edge EXIT.  By important we mean that no SSA name defined
4359    inside region is live over the other exit edges of the region.  All entry
4360    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4361    to the duplicate of the region.  SSA form, dominance and loop information
4362    is updated.  The new basic blocks are stored to REGION_COPY in the same
4363    order as they had in REGION, provided that REGION_COPY is not NULL.
4364    The function returns false if it is unable to copy the region,
4365    true otherwise.  */
4366
4367 bool
4368 tree_duplicate_sese_region (edge entry, edge exit,
4369                             basic_block *region, unsigned n_region,
4370                             basic_block *region_copy)
4371 {
4372   unsigned i, n_doms;
4373   bool free_region_copy = false, copying_header = false;
4374   struct loop *loop = entry->dest->loop_father;
4375   edge exit_copy;
4376   basic_block *doms;
4377   edge redirected;
4378   int total_freq = 0, entry_freq = 0;
4379   gcov_type total_count = 0, entry_count = 0;
4380
4381   if (!can_copy_bbs_p (region, n_region))
4382     return false;
4383
4384   /* Some sanity checking.  Note that we do not check for all possible
4385      missuses of the functions.  I.e. if you ask to copy something weird,
4386      it will work, but the state of structures probably will not be
4387      correct.  */
4388   for (i = 0; i < n_region; i++)
4389     {
4390       /* We do not handle subloops, i.e. all the blocks must belong to the
4391          same loop.  */
4392       if (region[i]->loop_father != loop)
4393         return false;
4394
4395       if (region[i] != entry->dest
4396           && region[i] == loop->header)
4397         return false;
4398     }
4399
4400   loop->copy = loop;
4401
4402   /* In case the function is used for loop header copying (which is the primary
4403      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4404   if (loop->header == entry->dest)
4405     {
4406       copying_header = true;
4407       loop->copy = loop->outer;
4408
4409       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4410         return false;
4411
4412       for (i = 0; i < n_region; i++)
4413         if (region[i] != exit->src
4414             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4415           return false;
4416     }
4417
4418   if (!region_copy)
4419     {
4420       region_copy = XNEWVEC (basic_block, n_region);
4421       free_region_copy = true;
4422     }
4423
4424   gcc_assert (!need_ssa_update_p ());
4425
4426   /* Record blocks outside the region that are dominated by something
4427      inside.  */
4428   doms = XNEWVEC (basic_block, n_basic_blocks);
4429   initialize_original_copy_tables ();
4430
4431   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4432
4433   if (entry->dest->count)
4434     {
4435       total_count = entry->dest->count;
4436       entry_count = entry->count;
4437       /* Fix up corner cases, to avoid division by zero or creation of negative
4438          frequencies.  */
4439       if (entry_count > total_count)
4440         entry_count = total_count;
4441     }
4442   else
4443     {
4444       total_freq = entry->dest->frequency;
4445       entry_freq = EDGE_FREQUENCY (entry);
4446       /* Fix up corner cases, to avoid division by zero or creation of negative
4447          frequencies.  */
4448       if (total_freq == 0)
4449         total_freq = 1;
4450       else if (entry_freq > total_freq)
4451         entry_freq = total_freq;
4452     }
4453
4454   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
4455             split_edge_bb_loc (entry));
4456   if (total_count)
4457     {
4458       scale_bbs_frequencies_gcov_type (region, n_region,
4459                                        total_count - entry_count,
4460                                        total_count);
4461       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
4462                                        total_count);
4463     }
4464   else
4465     {
4466       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4467                                  total_freq);
4468       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4469     }
4470
4471   if (copying_header)
4472     {
4473       loop->header = exit->dest;
4474       loop->latch = exit->src;
4475     }
4476
4477   /* Redirect the entry and add the phi node arguments.  */
4478   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
4479   gcc_assert (redirected != NULL);
4480   flush_pending_stmts (entry);
4481
4482   /* Concerning updating of dominators:  We must recount dominators
4483      for entry block and its copy.  Anything that is outside of the
4484      region, but was dominated by something inside needs recounting as
4485      well.  */
4486   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4487   doms[n_doms++] = get_bb_original (entry->dest);
4488   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4489   free (doms);
4490
4491   /* Add the other PHI node arguments.  */
4492   add_phi_args_after_copy (region_copy, n_region);
4493
4494   /* Update the SSA web.  */
4495   update_ssa (TODO_update_ssa);
4496
4497   if (free_region_copy)
4498     free (region_copy);
4499
4500   free_original_copy_tables ();
4501   return true;
4502 }
4503
4504 /*
4505 DEF_VEC_P(basic_block);
4506 DEF_VEC_ALLOC_P(basic_block,heap);
4507 */
4508
4509 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
4510    adding blocks when the dominator traversal reaches EXIT.  This
4511    function silently assumes that ENTRY strictly dominates EXIT.  */
4512
4513 static void
4514 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
4515                               VEC(basic_block,heap) **bbs_p)
4516 {
4517   basic_block son;
4518
4519   for (son = first_dom_son (CDI_DOMINATORS, entry);
4520        son;
4521        son = next_dom_son (CDI_DOMINATORS, son))
4522     {
4523       VEC_safe_push (basic_block, heap, *bbs_p, son);
4524       if (son != exit)
4525         gather_blocks_in_sese_region (son, exit, bbs_p);
4526     }
4527 }
4528
4529
4530 struct move_stmt_d
4531 {
4532   tree block;
4533   tree from_context;
4534   tree to_context;
4535   bitmap vars_to_remove;
4536   htab_t new_label_map;
4537   bool remap_decls_p;
4538 };
4539
4540 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
4541    contained in *TP and change the DECL_CONTEXT of every local
4542    variable referenced in *TP.  */
4543
4544 static tree
4545 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
4546 {
4547   struct move_stmt_d *p = (struct move_stmt_d *) data;
4548   tree t = *tp;
4549
4550   if (p->block && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (t))))
4551     TREE_BLOCK (t) = p->block;
4552
4553   if (OMP_DIRECTIVE_P (t)
4554       && TREE_CODE (t) != OMP_RETURN
4555       && TREE_CODE (t) != OMP_CONTINUE)
4556     {
4557       /* Do not remap variables inside OMP directives.  Variables
4558          referenced in clauses and directive header belong to the
4559          parent function and should not be moved into the child
4560          function.  */
4561       bool save_remap_decls_p = p->remap_decls_p;
4562       p->remap_decls_p = false;
4563       *walk_subtrees = 0;
4564
4565       walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
4566
4567       p->remap_decls_p = save_remap_decls_p;
4568     }
4569   else if (DECL_P (t) && DECL_CONTEXT (t) == p->from_context)
4570     {
4571       if (TREE_CODE (t) == LABEL_DECL)
4572         {
4573           if (p->new_label_map)
4574             {
4575               struct tree_map in, *out;
4576               in.from = t;
4577               out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
4578               if (out)
4579                 *tp = t = out->to;
4580             }
4581
4582           DECL_CONTEXT (t) = p->to_context;
4583         }
4584       else if (p->remap_decls_p)
4585         {
4586           DECL_CONTEXT (t) = p->to_context;
4587
4588           if (TREE_CODE (t) == VAR_DECL)
4589             {
4590               struct function *f = DECL_STRUCT_FUNCTION (p->to_context);
4591               f->unexpanded_var_list
4592                 = tree_cons (0, t, f->unexpanded_var_list);
4593
4594               /* Mark T to be removed from the original function,
4595                  otherwise it will be given a DECL_RTL when the
4596                  original function is expanded.  */
4597               bitmap_set_bit (p->vars_to_remove, DECL_UID (t));
4598             }
4599         }
4600     }
4601   else if (TYPE_P (t))
4602     *walk_subtrees = 0;
4603
4604   return NULL_TREE;
4605 }
4606
4607
4608 /* Move basic block BB from function CFUN to function DEST_FN.  The
4609    block is moved out of the original linked list and placed after
4610    block AFTER in the new list.  Also, the block is removed from the
4611    original array of blocks and placed in DEST_FN's array of blocks.
4612    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
4613    updated to reflect the moved edges.
4614    
4615    On exit, local variables that need to be removed from
4616    CFUN->UNEXPANDED_VAR_LIST will have been added to VARS_TO_REMOVE.  */
4617
4618 static void
4619 move_block_to_fn (struct function *dest_cfun, basic_block bb,
4620                   basic_block after, bool update_edge_count_p,
4621                   bitmap vars_to_remove, htab_t new_label_map, int eh_offset)
4622 {
4623   struct control_flow_graph *cfg;
4624   edge_iterator ei;
4625   edge e;
4626   block_stmt_iterator si;
4627   struct move_stmt_d d;
4628   unsigned old_len, new_len;
4629   basic_block *addr;
4630
4631   /* Link BB to the new linked list.  */
4632   move_block_after (bb, after);
4633
4634   /* Update the edge count in the corresponding flowgraphs.  */
4635   if (update_edge_count_p)
4636     FOR_EACH_EDGE (e, ei, bb->succs)
4637       {
4638         cfun->cfg->x_n_edges--;
4639         dest_cfun->cfg->x_n_edges++;
4640       }
4641
4642   /* Remove BB from the original basic block array.  */
4643   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
4644   cfun->cfg->x_n_basic_blocks--;
4645
4646   /* Grow DEST_CFUN's basic block array if needed.  */
4647   cfg = dest_cfun->cfg;
4648   cfg->x_n_basic_blocks++;
4649   if (bb->index > cfg->x_last_basic_block)
4650     cfg->x_last_basic_block = bb->index;
4651
4652   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
4653   if ((unsigned) cfg->x_last_basic_block >= old_len)
4654     {
4655       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
4656       VEC_safe_grow (basic_block, gc, cfg->x_basic_block_info, new_len);
4657       addr = VEC_address (basic_block, cfg->x_basic_block_info);
4658       memset (&addr[old_len], 0, sizeof (basic_block) * (new_len - old_len));
4659     }
4660
4661   VEC_replace (basic_block, cfg->x_basic_block_info,
4662                cfg->x_last_basic_block, bb);
4663
4664   /* The statements in BB need to be associated with a new TREE_BLOCK.
4665      Labels need to be associated with a new label-to-block map.  */
4666   memset (&d, 0, sizeof (d));
4667   d.vars_to_remove = vars_to_remove;
4668
4669   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4670     {
4671       tree stmt = bsi_stmt (si);
4672       int region;
4673
4674       d.from_context = cfun->decl;
4675       d.to_context = dest_cfun->decl;
4676       d.remap_decls_p = true;
4677       d.new_label_map = new_label_map;
4678       if (TREE_BLOCK (stmt))
4679         d.block = DECL_INITIAL (dest_cfun->decl);
4680
4681       walk_tree (&stmt, move_stmt_r, &d, NULL);
4682
4683       if (TREE_CODE (stmt) == LABEL_EXPR)
4684         {
4685           tree label = LABEL_EXPR_LABEL (stmt);
4686           int uid = LABEL_DECL_UID (label);
4687
4688           gcc_assert (uid > -1);
4689
4690           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
4691           if (old_len <= (unsigned) uid)
4692             {
4693               new_len = 3 * uid / 2;
4694               VEC_safe_grow (basic_block, gc, cfg->x_label_to_block_map,
4695                              new_len);
4696               addr = VEC_address (basic_block, cfg->x_label_to_block_map);
4697               memset (&addr[old_len], 0,
4698                       sizeof (basic_block) * (new_len - old_len));
4699             }
4700
4701           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
4702           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
4703
4704           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
4705
4706           if (uid >= dest_cfun->last_label_uid)
4707             dest_cfun->last_label_uid = uid + 1;
4708         }
4709       else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
4710         TREE_OPERAND (stmt, 0) =
4711           build_int_cst (NULL_TREE,
4712                          TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
4713                          + eh_offset);
4714
4715       region = lookup_stmt_eh_region (stmt);
4716       if (region >= 0)
4717         {
4718           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
4719           remove_stmt_from_eh_region (stmt);
4720         }
4721     }
4722 }
4723
4724 /* Examine the statements in BB (which is in SRC_CFUN); find and return
4725    the outermost EH region.  Use REGION as the incoming base EH region.  */
4726
4727 static int
4728 find_outermost_region_in_block (struct function *src_cfun,
4729                                 basic_block bb, int region)
4730 {
4731   block_stmt_iterator si;
4732   
4733   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4734     {
4735       tree stmt = bsi_stmt (si);
4736       int stmt_region;
4737
4738       if (TREE_CODE (stmt) == RESX_EXPR)
4739         stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
4740       else
4741         stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
4742       if (stmt_region > 0)
4743         {
4744           if (region < 0)
4745             region = stmt_region;
4746           else if (stmt_region != region)
4747             {
4748               region = eh_region_outermost (src_cfun, stmt_region, region);
4749               gcc_assert (region != -1);
4750             }
4751         }
4752     }
4753
4754   return region;
4755 }
4756
4757 static tree
4758 new_label_mapper (tree decl, void *data)
4759 {
4760   htab_t hash = (htab_t) data;
4761   struct tree_map *m;
4762   void **slot;
4763
4764   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
4765
4766   m = xmalloc (sizeof (struct tree_map));
4767   m->hash = DECL_UID (decl);
4768   m->from = decl;
4769   m->to = create_artificial_label ();
4770   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
4771
4772   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
4773   gcc_assert (*slot == NULL);
4774
4775   *slot = m;
4776
4777   return m->to;
4778 }
4779
4780 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
4781    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
4782    single basic block in the original CFG and the new basic block is
4783    returned.  DEST_CFUN must not have a CFG yet.
4784
4785    Note that the region need not be a pure SESE region.  Blocks inside
4786    the region may contain calls to abort/exit.  The only restriction
4787    is that ENTRY_BB should be the only entry point and it must
4788    dominate EXIT_BB.
4789
4790    All local variables referenced in the region are assumed to be in
4791    the corresponding BLOCK_VARS and unexpanded variable lists
4792    associated with DEST_CFUN.  */
4793
4794 basic_block
4795 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
4796                         basic_block exit_bb)
4797 {
4798   VEC(basic_block,heap) *bbs;
4799   basic_block after, bb, *entry_pred, *exit_succ;
4800   struct function *saved_cfun;
4801   int *entry_flag, *exit_flag, eh_offset;
4802   unsigned i, num_entry_edges, num_exit_edges;
4803   edge e;
4804   edge_iterator ei;
4805   bitmap vars_to_remove;
4806   htab_t new_label_map;
4807
4808   saved_cfun = cfun;
4809
4810   /* Collect all the blocks in the region.  Manually add ENTRY_BB
4811      because it won't be added by dfs_enumerate_from.  */
4812   calculate_dominance_info (CDI_DOMINATORS);
4813
4814   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
4815      region.  */
4816   gcc_assert (entry_bb != exit_bb
4817               && (!exit_bb
4818                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
4819
4820   bbs = NULL;
4821   VEC_safe_push (basic_block, heap, bbs, entry_bb);
4822   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4823
4824   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
4825      the predecessor edges to ENTRY_BB and the successor edges to
4826      EXIT_BB so that we can re-attach them to the new basic block that
4827      will replace the region.  */
4828   num_entry_edges = EDGE_COUNT (entry_bb->preds);
4829   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
4830   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
4831   i = 0;
4832   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
4833     {
4834       entry_flag[i] = e->flags;
4835       entry_pred[i++] = e->src;
4836       remove_edge (e);
4837     }
4838
4839   if (exit_bb)
4840     {
4841       num_exit_edges = EDGE_COUNT (exit_bb->succs);
4842       exit_succ = (basic_block *) xcalloc (num_exit_edges,
4843                                            sizeof (basic_block));
4844       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
4845       i = 0;
4846       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
4847         {
4848           exit_flag[i] = e->flags;
4849           exit_succ[i++] = e->dest;
4850           remove_edge (e);
4851         }
4852     }
4853   else
4854     {
4855       num_exit_edges = 0;
4856       exit_succ = NULL;
4857       exit_flag = NULL;
4858     }
4859
4860   /* Switch context to the child function to initialize DEST_FN's CFG.  */
4861   gcc_assert (dest_cfun->cfg == NULL);
4862   cfun = dest_cfun;
4863
4864   init_empty_tree_cfg ();
4865
4866   /* Initialize EH information for the new function.  */
4867   eh_offset = 0;
4868   new_label_map = NULL;
4869   if (saved_cfun->eh)
4870     {
4871       int region = -1;
4872
4873       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4874         region = find_outermost_region_in_block (saved_cfun, bb, region);
4875
4876       init_eh_for_function ();
4877       if (region != -1)
4878         {
4879           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
4880           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
4881                                             new_label_map, region, 0);
4882         }
4883     }
4884
4885   cfun = saved_cfun;
4886
4887   /* Move blocks from BBS into DEST_CFUN.  */
4888   gcc_assert (VEC_length (basic_block, bbs) >= 2);
4889   after = dest_cfun->cfg->x_entry_block_ptr;
4890   vars_to_remove = BITMAP_ALLOC (NULL);
4891   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4892     {
4893       /* No need to update edge counts on the last block.  It has
4894          already been updated earlier when we detached the region from
4895          the original CFG.  */
4896       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_to_remove,
4897                         new_label_map, eh_offset);
4898       after = bb;
4899     }
4900
4901   if (new_label_map)
4902     htab_delete (new_label_map);
4903
4904   /* Remove the variables marked in VARS_TO_REMOVE from
4905      CFUN->UNEXPANDED_VAR_LIST.  Otherwise, they will be given a
4906      DECL_RTL in the context of CFUN.  */
4907   if (!bitmap_empty_p (vars_to_remove))
4908     {
4909       tree *p;
4910
4911       for (p = &cfun->unexpanded_var_list; *p; )
4912         {
4913           tree var = TREE_VALUE (*p);
4914           if (bitmap_bit_p (vars_to_remove, DECL_UID (var)))
4915             {
4916               *p = TREE_CHAIN (*p);
4917               continue;
4918             }
4919
4920           p = &TREE_CHAIN (*p);
4921         }
4922     }
4923
4924   BITMAP_FREE (vars_to_remove);
4925
4926   /* Rewire the entry and exit blocks.  The successor to the entry
4927      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
4928      the child function.  Similarly, the predecessor of DEST_FN's
4929      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
4930      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
4931      various CFG manipulation function get to the right CFG.
4932
4933      FIXME, this is silly.  The CFG ought to become a parameter to
4934      these helpers.  */
4935   cfun = dest_cfun;
4936   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
4937   if (exit_bb)
4938     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
4939   cfun = saved_cfun;
4940
4941   /* Back in the original function, the SESE region has disappeared,
4942      create a new basic block in its place.  */
4943   bb = create_empty_bb (entry_pred[0]);
4944   for (i = 0; i < num_entry_edges; i++)
4945     make_edge (entry_pred[i], bb, entry_flag[i]);
4946
4947   for (i = 0; i < num_exit_edges; i++)
4948     make_edge (bb, exit_succ[i], exit_flag[i]);
4949
4950   if (exit_bb)
4951     {
4952       free (exit_flag);
4953       free (exit_succ);
4954     }
4955   free (entry_flag);
4956   free (entry_pred);
4957   free_dominance_info (CDI_DOMINATORS);
4958   free_dominance_info (CDI_POST_DOMINATORS);
4959   VEC_free (basic_block, heap, bbs);
4960
4961   return bb;
4962 }
4963
4964
4965 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4966
4967 void
4968 dump_function_to_file (tree fn, FILE *file, int flags)
4969 {
4970   tree arg, vars, var;
4971   bool ignore_topmost_bind = false, any_var = false;
4972   basic_block bb;
4973   tree chain;
4974   struct function *saved_cfun;
4975   
4976   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4977
4978   arg = DECL_ARGUMENTS (fn);
4979   while (arg)
4980     {
4981       print_generic_expr (file, arg, dump_flags);
4982       if (TREE_CHAIN (arg))
4983         fprintf (file, ", ");
4984       arg = TREE_CHAIN (arg);
4985     }
4986   fprintf (file, ")\n");
4987
4988   if (flags & TDF_DETAILS)
4989     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
4990   if (flags & TDF_RAW)
4991     {
4992       dump_node (fn, TDF_SLIM | flags, file);
4993       return;
4994     }
4995
4996   /* Switch CFUN to point to FN.  */
4997   saved_cfun = cfun;
4998   cfun = DECL_STRUCT_FUNCTION (fn);
4999
5000   /* When GIMPLE is lowered, the variables are no longer available in
5001      BIND_EXPRs, so display them separately.  */
5002   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
5003     {
5004       ignore_topmost_bind = true;
5005
5006       fprintf (file, "{\n");
5007       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
5008         {
5009           var = TREE_VALUE (vars);
5010
5011           print_generic_decl (file, var, flags);
5012           fprintf (file, "\n");
5013
5014           any_var = true;
5015         }
5016     }
5017
5018   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
5019     {
5020       /* Make a CFG based dump.  */
5021       check_bb_profile (ENTRY_BLOCK_PTR, file);
5022       if (!ignore_topmost_bind)
5023         fprintf (file, "{\n");
5024
5025       if (any_var && n_basic_blocks)
5026         fprintf (file, "\n");
5027
5028       FOR_EACH_BB (bb)
5029         dump_generic_bb (file, bb, 2, flags);
5030         
5031       fprintf (file, "}\n");
5032       check_bb_profile (EXIT_BLOCK_PTR, file);
5033     }
5034   else
5035     {
5036       int indent;
5037
5038       /* Make a tree based dump.  */
5039       chain = DECL_SAVED_TREE (fn);
5040
5041       if (chain && TREE_CODE (chain) == BIND_EXPR)
5042         {
5043           if (ignore_topmost_bind)
5044             {
5045               chain = BIND_EXPR_BODY (chain);
5046               indent = 2;
5047             }
5048           else
5049             indent = 0;
5050         }
5051       else
5052         {
5053           if (!ignore_topmost_bind)
5054             fprintf (file, "{\n");
5055           indent = 2;
5056         }
5057
5058       if (any_var)
5059         fprintf (file, "\n");
5060
5061       print_generic_stmt_indented (file, chain, flags, indent);
5062       if (ignore_topmost_bind)
5063         fprintf (file, "}\n");
5064     }
5065
5066   fprintf (file, "\n\n");
5067
5068   /* Restore CFUN.  */
5069   cfun = saved_cfun;
5070 }
5071
5072
5073 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
5074
5075 void
5076 debug_function (tree fn, int flags)
5077 {
5078   dump_function_to_file (fn, stderr, flags);
5079 }
5080
5081
5082 /* Pretty print of the loops intermediate representation.  */
5083 static void print_loop (FILE *, struct loop *, int);
5084 static void print_pred_bbs (FILE *, basic_block bb);
5085 static void print_succ_bbs (FILE *, basic_block bb);
5086
5087
5088 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
5089
5090 static void
5091 print_pred_bbs (FILE *file, basic_block bb)
5092 {
5093   edge e;
5094   edge_iterator ei;
5095
5096   FOR_EACH_EDGE (e, ei, bb->preds)
5097     fprintf (file, "bb_%d ", e->src->index);
5098 }
5099
5100
5101 /* Print on FILE the indexes for the successors of basic_block BB.  */
5102
5103 static void
5104 print_succ_bbs (FILE *file, basic_block bb)
5105 {
5106   edge e;
5107   edge_iterator ei;
5108
5109   FOR_EACH_EDGE (e, ei, bb->succs)
5110     fprintf (file, "bb_%d ", e->dest->index);
5111 }
5112
5113
5114 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5115
5116 static void
5117 print_loop (FILE *file, struct loop *loop, int indent)
5118 {
5119   char *s_indent;
5120   basic_block bb;
5121   
5122   if (loop == NULL)
5123     return;
5124
5125   s_indent = (char *) alloca ((size_t) indent + 1);
5126   memset ((void *) s_indent, ' ', (size_t) indent);
5127   s_indent[indent] = '\0';
5128
5129   /* Print the loop's header.  */
5130   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5131   
5132   /* Print the loop's body.  */
5133   fprintf (file, "%s{\n", s_indent);
5134   FOR_EACH_BB (bb)
5135     if (bb->loop_father == loop)
5136       {
5137         /* Print the basic_block's header.  */
5138         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5139         print_pred_bbs (file, bb);
5140         fprintf (file, "}, succs = {");
5141         print_succ_bbs (file, bb);
5142         fprintf (file, "})\n");
5143         
5144         /* Print the basic_block's body.  */
5145         fprintf (file, "%s  {\n", s_indent);
5146         tree_dump_bb (bb, file, indent + 4);
5147         fprintf (file, "%s  }\n", s_indent);
5148       }
5149   
5150   print_loop (file, loop->inner, indent + 2);
5151   fprintf (file, "%s}\n", s_indent);
5152   print_loop (file, loop->next, indent);
5153 }
5154
5155
5156 /* Follow a CFG edge from the entry point of the program, and on entry
5157    of a loop, pretty print the loop structure on FILE.  */
5158
5159 void 
5160 print_loop_ir (FILE *file)
5161 {
5162   basic_block bb;
5163   
5164   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
5165   if (bb && bb->loop_father)
5166     print_loop (file, bb->loop_father, 0);
5167 }
5168
5169
5170 /* Debugging loops structure at tree level.  */
5171
5172 void 
5173 debug_loop_ir (void)
5174 {
5175   print_loop_ir (stderr);
5176 }
5177
5178
5179 /* Return true if BB ends with a call, possibly followed by some
5180    instructions that must stay with the call.  Return false,
5181    otherwise.  */
5182
5183 static bool
5184 tree_block_ends_with_call_p (basic_block bb)
5185 {
5186   block_stmt_iterator bsi = bsi_last (bb);
5187   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5188 }
5189
5190
5191 /* Return true if BB ends with a conditional branch.  Return false,
5192    otherwise.  */
5193
5194 static bool
5195 tree_block_ends_with_condjump_p (basic_block bb)
5196 {
5197   tree stmt = last_stmt (bb);
5198   return (stmt && TREE_CODE (stmt) == COND_EXPR);
5199 }
5200
5201
5202 /* Return true if we need to add fake edge to exit at statement T.
5203    Helper function for tree_flow_call_edges_add.  */
5204
5205 static bool
5206 need_fake_edge_p (tree t)
5207 {
5208   tree call;
5209
5210   /* NORETURN and LONGJMP calls already have an edge to exit.
5211      CONST and PURE calls do not need one.
5212      We don't currently check for CONST and PURE here, although
5213      it would be a good idea, because those attributes are
5214      figured out from the RTL in mark_constant_function, and
5215      the counter incrementation code from -fprofile-arcs
5216      leads to different results from -fbranch-probabilities.  */
5217   call = get_call_expr_in (t);
5218   if (call
5219       && !(call_expr_flags (call) & ECF_NORETURN))
5220     return true;
5221
5222   if (TREE_CODE (t) == ASM_EXPR
5223        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5224     return true;
5225
5226   return false;
5227 }
5228
5229
5230 /* Add fake edges to the function exit for any non constant and non
5231    noreturn calls, volatile inline assembly in the bitmap of blocks
5232    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5233    the number of blocks that were split.
5234
5235    The goal is to expose cases in which entering a basic block does
5236    not imply that all subsequent instructions must be executed.  */
5237
5238 static int
5239 tree_flow_call_edges_add (sbitmap blocks)
5240 {
5241   int i;
5242   int blocks_split = 0;
5243   int last_bb = last_basic_block;
5244   bool check_last_block = false;
5245
5246   if (n_basic_blocks == NUM_FIXED_BLOCKS)
5247     return 0;
5248
5249   if (! blocks)
5250     check_last_block = true;
5251   else
5252     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5253
5254   /* In the last basic block, before epilogue generation, there will be
5255      a fallthru edge to EXIT.  Special care is required if the last insn
5256      of the last basic block is a call because make_edge folds duplicate
5257      edges, which would result in the fallthru edge also being marked
5258      fake, which would result in the fallthru edge being removed by
5259      remove_fake_edges, which would result in an invalid CFG.
5260
5261      Moreover, we can't elide the outgoing fake edge, since the block
5262      profiler needs to take this into account in order to solve the minimal
5263      spanning tree in the case that the call doesn't return.
5264
5265      Handle this by adding a dummy instruction in a new last basic block.  */
5266   if (check_last_block)
5267     {
5268       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5269       block_stmt_iterator bsi = bsi_last (bb);
5270       tree t = NULL_TREE;
5271       if (!bsi_end_p (bsi))
5272         t = bsi_stmt (bsi);
5273
5274       if (t && need_fake_edge_p (t))
5275         {
5276           edge e;
5277
5278           e = find_edge (bb, EXIT_BLOCK_PTR);
5279           if (e)
5280             {
5281               bsi_insert_on_edge (e, build_empty_stmt ());
5282               bsi_commit_edge_inserts ();
5283             }
5284         }
5285     }
5286
5287   /* Now add fake edges to the function exit for any non constant
5288      calls since there is no way that we can determine if they will
5289      return or not...  */
5290   for (i = 0; i < last_bb; i++)
5291     {
5292       basic_block bb = BASIC_BLOCK (i);
5293       block_stmt_iterator bsi;
5294       tree stmt, last_stmt;
5295
5296       if (!bb)
5297         continue;
5298
5299       if (blocks && !TEST_BIT (blocks, i))
5300         continue;
5301
5302       bsi = bsi_last (bb);
5303       if (!bsi_end_p (bsi))
5304         {
5305           last_stmt = bsi_stmt (bsi);
5306           do
5307             {
5308               stmt = bsi_stmt (bsi);
5309               if (need_fake_edge_p (stmt))
5310                 {
5311                   edge e;
5312                   /* The handling above of the final block before the
5313                      epilogue should be enough to verify that there is
5314                      no edge to the exit block in CFG already.
5315                      Calling make_edge in such case would cause us to
5316                      mark that edge as fake and remove it later.  */
5317 #ifdef ENABLE_CHECKING
5318                   if (stmt == last_stmt)
5319                     {
5320                       e = find_edge (bb, EXIT_BLOCK_PTR);
5321                       gcc_assert (e == NULL);
5322                     }
5323 #endif
5324
5325                   /* Note that the following may create a new basic block
5326                      and renumber the existing basic blocks.  */
5327                   if (stmt != last_stmt)
5328                     {
5329                       e = split_block (bb, stmt);
5330                       if (e)
5331                         blocks_split++;
5332                     }
5333                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5334                 }
5335               bsi_prev (&bsi);
5336             }
5337           while (!bsi_end_p (bsi));
5338         }
5339     }
5340
5341   if (blocks_split)
5342     verify_flow_info ();
5343
5344   return blocks_split;
5345 }
5346
5347 bool
5348 tree_purge_dead_eh_edges (basic_block bb)
5349 {
5350   bool changed = false;
5351   edge e;
5352   edge_iterator ei;
5353   tree stmt = last_stmt (bb);
5354
5355   if (stmt && tree_can_throw_internal (stmt))
5356     return false;
5357
5358   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5359     {
5360       if (e->flags & EDGE_EH)
5361         {
5362           remove_edge (e);
5363           changed = true;
5364         }
5365       else
5366         ei_next (&ei);
5367     }
5368
5369   /* Removal of dead EH edges might change dominators of not
5370      just immediate successors.  E.g. when bb1 is changed so that
5371      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5372      eh edges purged by this function in:
5373            0
5374           / \
5375          v   v
5376          1-->2
5377         / \  |
5378        v   v |
5379        3-->4 |
5380         \    v
5381          --->5
5382              |
5383              -
5384      idom(bb5) must be recomputed.  For now just free the dominance
5385      info.  */
5386   if (changed)
5387     free_dominance_info (CDI_DOMINATORS);
5388
5389   return changed;
5390 }
5391
5392 bool
5393 tree_purge_all_dead_eh_edges (bitmap blocks)
5394 {
5395   bool changed = false;
5396   unsigned i;
5397   bitmap_iterator bi;
5398
5399   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5400     {
5401       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5402     }
5403
5404   return changed;
5405 }
5406
5407 /* This function is called whenever a new edge is created or
5408    redirected.  */
5409
5410 static void
5411 tree_execute_on_growing_pred (edge e)
5412 {
5413   basic_block bb = e->dest;
5414
5415   if (phi_nodes (bb))
5416     reserve_phi_args_for_new_edge (bb);
5417 }
5418
5419 /* This function is called immediately before edge E is removed from
5420    the edge vector E->dest->preds.  */
5421
5422 static void
5423 tree_execute_on_shrinking_pred (edge e)
5424 {
5425   if (phi_nodes (e->dest))
5426     remove_phi_args (e);
5427 }
5428
5429 /*---------------------------------------------------------------------------
5430   Helper functions for Loop versioning
5431   ---------------------------------------------------------------------------*/
5432
5433 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
5434    of 'first'. Both of them are dominated by 'new_head' basic block. When
5435    'new_head' was created by 'second's incoming edge it received phi arguments
5436    on the edge by split_edge(). Later, additional edge 'e' was created to
5437    connect 'new_head' and 'first'. Now this routine adds phi args on this 
5438    additional edge 'e' that new_head to second edge received as part of edge 
5439    splitting.
5440 */
5441
5442 static void
5443 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
5444                                 basic_block new_head, edge e)
5445 {
5446   tree phi1, phi2;
5447   edge e2 = find_edge (new_head, second);
5448
5449   /* Because NEW_HEAD has been created by splitting SECOND's incoming
5450      edge, we should always have an edge from NEW_HEAD to SECOND.  */
5451   gcc_assert (e2 != NULL);
5452
5453   /* Browse all 'second' basic block phi nodes and add phi args to
5454      edge 'e' for 'first' head. PHI args are always in correct order.  */
5455
5456   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); 
5457        phi2 && phi1; 
5458        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
5459     {
5460       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
5461       add_phi_arg (phi1, def, e);
5462     }
5463 }
5464
5465 /* Adds a if else statement to COND_BB with condition COND_EXPR.  
5466    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is 
5467    the destination of the ELSE part.  */
5468 static void
5469 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
5470                             basic_block cond_bb, void *cond_e)
5471 {
5472   block_stmt_iterator bsi;
5473   tree goto1 = NULL_TREE;
5474   tree goto2 = NULL_TREE;
5475   tree new_cond_expr = NULL_TREE;
5476   tree cond_expr = (tree) cond_e;
5477   edge e0;
5478
5479   /* Build new conditional expr */
5480   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
5481   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
5482   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
5483
5484   /* Add new cond in cond_bb.  */ 
5485   bsi = bsi_start (cond_bb); 
5486   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
5487   /* Adjust edges appropriately to connect new head with first head
5488      as well as second head.  */
5489   e0 = single_succ_edge (cond_bb);
5490   e0->flags &= ~EDGE_FALLTHRU;
5491   e0->flags |= EDGE_FALSE_VALUE;
5492 }
5493
5494 struct cfg_hooks tree_cfg_hooks = {
5495   "tree",
5496   tree_verify_flow_info,
5497   tree_dump_bb,                 /* dump_bb  */
5498   create_bb,                    /* create_basic_block  */
5499   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5500   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5501   remove_bb,                    /* delete_basic_block  */
5502   tree_split_block,             /* split_block  */
5503   tree_move_block_after,        /* move_block_after  */
5504   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5505   tree_merge_blocks,            /* merge_blocks  */
5506   tree_predict_edge,            /* predict_edge  */
5507   tree_predicted_by_p,          /* predicted_by_p  */
5508   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5509   tree_duplicate_bb,            /* duplicate_block  */
5510   tree_split_edge,              /* split_edge  */
5511   tree_make_forwarder_block,    /* make_forward_block  */
5512   NULL,                         /* tidy_fallthru_edge  */
5513   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5514   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5515   tree_flow_call_edges_add,     /* flow_call_edges_add */
5516   tree_execute_on_growing_pred, /* execute_on_growing_pred */
5517   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
5518   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
5519   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5520   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
5521   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
5522   flush_pending_stmts           /* flush_pending_stmts */  
5523 };
5524
5525
5526 /* Split all critical edges.  */
5527
5528 static unsigned int
5529 split_critical_edges (void)
5530 {
5531   basic_block bb;
5532   edge e;
5533   edge_iterator ei;
5534
5535   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5536      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5537      mappings around the calls to split_edge.  */
5538   start_recording_case_labels ();
5539   FOR_ALL_BB (bb)
5540     {
5541       FOR_EACH_EDGE (e, ei, bb->succs)
5542         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5543           {
5544             split_edge (e);
5545           }
5546     }
5547   end_recording_case_labels ();
5548   return 0;
5549 }
5550
5551 struct tree_opt_pass pass_split_crit_edges = 
5552 {
5553   "crited",                          /* name */
5554   NULL,                          /* gate */
5555   split_critical_edges,          /* execute */
5556   NULL,                          /* sub */
5557   NULL,                          /* next */
5558   0,                             /* static_pass_number */
5559   TV_TREE_SPLIT_EDGES,           /* tv_id */
5560   PROP_cfg,                      /* properties required */
5561   PROP_no_crit_edges,            /* properties_provided */
5562   0,                             /* properties_destroyed */
5563   0,                             /* todo_flags_start */
5564   TODO_dump_func,                /* todo_flags_finish */
5565   0                              /* letter */
5566 };
5567
5568 \f
5569 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5570    a temporary, make sure and register it to be renamed if necessary,
5571    and finally return the temporary.  Put the statements to compute
5572    EXP before the current statement in BSI.  */
5573
5574 tree
5575 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5576 {
5577   tree t, new_stmt, orig_stmt;
5578
5579   if (is_gimple_val (exp))
5580     return exp;
5581
5582   t = make_rename_temp (type, NULL);
5583   new_stmt = build2 (MODIFY_EXPR, type, t, exp);
5584
5585   orig_stmt = bsi_stmt (*bsi);
5586   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5587   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5588
5589   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5590
5591   return t;
5592 }
5593
5594 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5595    Return the gimple_val holding the result.  */
5596
5597 tree
5598 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5599                  tree type, tree a, tree b, tree c)
5600 {
5601   tree ret;
5602
5603   ret = fold_build3 (code, type, a, b, c);
5604   STRIP_NOPS (ret);
5605
5606   return gimplify_val (bsi, type, ret);
5607 }
5608
5609 /* Build a binary operation and gimplify it.  Emit code before BSI.
5610    Return the gimple_val holding the result.  */
5611
5612 tree
5613 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5614                  tree type, tree a, tree b)
5615 {
5616   tree ret;
5617
5618   ret = fold_build2 (code, type, a, b);
5619   STRIP_NOPS (ret);
5620
5621   return gimplify_val (bsi, type, ret);
5622 }
5623
5624 /* Build a unary operation and gimplify it.  Emit code before BSI.
5625    Return the gimple_val holding the result.  */
5626
5627 tree
5628 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5629                  tree a)
5630 {
5631   tree ret;
5632
5633   ret = fold_build1 (code, type, a);
5634   STRIP_NOPS (ret);
5635
5636   return gimplify_val (bsi, type, ret);
5637 }
5638
5639
5640 \f
5641 /* Emit return warnings.  */
5642
5643 static unsigned int
5644 execute_warn_function_return (void)
5645 {
5646 #ifdef USE_MAPPED_LOCATION
5647   source_location location;
5648 #else
5649   location_t *locus;
5650 #endif
5651   tree last;
5652   edge e;
5653   edge_iterator ei;
5654
5655   /* If we have a path to EXIT, then we do return.  */
5656   if (TREE_THIS_VOLATILE (cfun->decl)
5657       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5658     {
5659 #ifdef USE_MAPPED_LOCATION
5660       location = UNKNOWN_LOCATION;
5661 #else
5662       locus = NULL;
5663 #endif
5664       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5665         {
5666           last = last_stmt (e->src);
5667           if (TREE_CODE (last) == RETURN_EXPR
5668 #ifdef USE_MAPPED_LOCATION
5669               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5670 #else
5671               && (locus = EXPR_LOCUS (last)) != NULL)
5672 #endif
5673             break;
5674         }
5675 #ifdef USE_MAPPED_LOCATION
5676       if (location == UNKNOWN_LOCATION)
5677         location = cfun->function_end_locus;
5678       warning (0, "%H%<noreturn%> function does return", &location);
5679 #else
5680       if (!locus)
5681         locus = &cfun->function_end_locus;
5682       warning (0, "%H%<noreturn%> function does return", locus);
5683 #endif
5684     }
5685
5686   /* If we see "return;" in some basic block, then we do reach the end
5687      without returning a value.  */
5688   else if (warn_return_type
5689            && !TREE_NO_WARNING (cfun->decl)
5690            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5691            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5692     {
5693       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5694         {
5695           tree last = last_stmt (e->src);
5696           if (TREE_CODE (last) == RETURN_EXPR
5697               && TREE_OPERAND (last, 0) == NULL
5698               && !TREE_NO_WARNING (last))
5699             {
5700 #ifdef USE_MAPPED_LOCATION
5701               location = EXPR_LOCATION (last);
5702               if (location == UNKNOWN_LOCATION)
5703                   location = cfun->function_end_locus;
5704               warning (0, "%Hcontrol reaches end of non-void function", &location);
5705 #else
5706               locus = EXPR_LOCUS (last);
5707               if (!locus)
5708                 locus = &cfun->function_end_locus;
5709               warning (0, "%Hcontrol reaches end of non-void function", locus);
5710 #endif
5711               TREE_NO_WARNING (cfun->decl) = 1;
5712               break;
5713             }
5714         }
5715     }
5716   return 0;
5717 }
5718
5719
5720 /* Given a basic block B which ends with a conditional and has
5721    precisely two successors, determine which of the edges is taken if
5722    the conditional is true and which is taken if the conditional is
5723    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5724
5725 void
5726 extract_true_false_edges_from_block (basic_block b,
5727                                      edge *true_edge,
5728                                      edge *false_edge)
5729 {
5730   edge e = EDGE_SUCC (b, 0);
5731
5732   if (e->flags & EDGE_TRUE_VALUE)
5733     {
5734       *true_edge = e;
5735       *false_edge = EDGE_SUCC (b, 1);
5736     }
5737   else
5738     {
5739       *false_edge = e;
5740       *true_edge = EDGE_SUCC (b, 1);
5741     }
5742 }
5743
5744 struct tree_opt_pass pass_warn_function_return =
5745 {
5746   NULL,                                 /* name */
5747   NULL,                                 /* gate */
5748   execute_warn_function_return,         /* execute */
5749   NULL,                                 /* sub */
5750   NULL,                                 /* next */
5751   0,                                    /* static_pass_number */
5752   0,                                    /* tv_id */
5753   PROP_cfg,                             /* properties_required */
5754   0,                                    /* properties_provided */
5755   0,                                    /* properties_destroyed */
5756   0,                                    /* todo_flags_start */
5757   0,                                    /* todo_flags_finish */
5758   0                                     /* letter */
5759 };
5760
5761 /* Emit noreturn warnings.  */
5762
5763 static unsigned int
5764 execute_warn_function_noreturn (void)
5765 {
5766   if (warn_missing_noreturn
5767       && !TREE_THIS_VOLATILE (cfun->decl)
5768       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5769       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5770     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
5771              "for attribute %<noreturn%>",
5772              cfun->decl);
5773   return 0;
5774 }
5775
5776 struct tree_opt_pass pass_warn_function_noreturn =
5777 {
5778   NULL,                                 /* name */
5779   NULL,                                 /* gate */
5780   execute_warn_function_noreturn,       /* execute */
5781   NULL,                                 /* sub */
5782   NULL,                                 /* next */
5783   0,                                    /* static_pass_number */
5784   0,                                    /* tv_id */
5785   PROP_cfg,                             /* properties_required */
5786   0,                                    /* properties_provided */
5787   0,                                    /* properties_destroyed */
5788   0,                                    /* todo_flags_start */
5789   0,                                    /* todo_flags_finish */
5790   0                                     /* letter */
5791 };