OSDN Git Service

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