OSDN Git Service

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