1 /* Control flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
36 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-flow.h"
40 #include "tree-dump.h"
41 #include "tree-pass.h"
45 #include "cfglayout.h"
46 #include "tree-ssa-propagate.h"
47 #include "value-prof.h"
48 #include "pointer-set.h"
49 #include "tree-inline.h"
51 /* This file contains functions for building the Control Flow Graph (CFG)
52 for a function tree. */
54 /* Local declarations. */
56 /* Initial capacity for the basic block array. */
57 static const int initial_cfg_capacity = 20;
59 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
60 which use a particular edge. The CASE_LABEL_EXPRs are chained together
61 via their TREE_CHAIN field, which we clear after we're done with the
62 hash table to prevent problems with duplication of SWITCH_EXPRs.
64 Access to this list of CASE_LABEL_EXPRs allows us to efficiently
65 update the case vector in response to edge redirections.
67 Right now this table is set up and torn down at key points in the
68 compilation process. It would be nice if we could make the table
69 more persistent. The key is getting notification of changes to
70 the CFG (particularly edge removal, creation and redirection). */
72 static struct pointer_map_t *edge_to_cases;
77 long num_merged_labels;
80 static struct cfg_stats_d cfg_stats;
82 /* Nonzero if we found a computed goto while building basic blocks. */
83 static bool found_computed_goto;
85 /* Basic blocks and flowgraphs. */
86 static basic_block create_bb (void *, void *, basic_block);
87 static void make_blocks (tree);
88 static void factor_computed_gotos (void);
91 static void make_edges (void);
92 static void make_cond_expr_edges (basic_block);
93 static void make_switch_expr_edges (basic_block);
94 static void make_goto_expr_edges (basic_block);
95 static edge tree_redirect_edge_and_branch (edge, basic_block);
96 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
97 static unsigned int split_critical_edges (void);
99 /* Various helpers. */
100 static inline bool stmt_starts_bb_p (const_tree, const_tree);
101 static int tree_verify_flow_info (void);
102 static void tree_make_forwarder_block (edge);
103 static void tree_cfg2vcg (FILE *);
104 static inline void change_bb_for_stmt (tree t, basic_block bb);
106 /* Flowgraph optimization and cleanup. */
107 static void tree_merge_blocks (basic_block, basic_block);
108 static bool tree_can_merge_blocks_p (basic_block, basic_block);
109 static void remove_bb (basic_block);
110 static edge find_taken_edge_computed_goto (basic_block, tree);
111 static edge find_taken_edge_cond_expr (basic_block, tree);
112 static edge find_taken_edge_switch_expr (basic_block, tree);
113 static tree find_case_label_for_value (tree, tree);
116 init_empty_tree_cfg (void)
118 /* Initialize the basic block array. */
120 profile_status = PROFILE_ABSENT;
121 n_basic_blocks = NUM_FIXED_BLOCKS;
122 last_basic_block = NUM_FIXED_BLOCKS;
123 basic_block_info = VEC_alloc (basic_block, gc, initial_cfg_capacity);
124 VEC_safe_grow_cleared (basic_block, gc, basic_block_info,
125 initial_cfg_capacity);
127 /* Build a mapping of labels to their associated blocks. */
128 label_to_block_map = VEC_alloc (basic_block, gc, initial_cfg_capacity);
129 VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
130 initial_cfg_capacity);
132 SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
133 SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
134 ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
135 EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
138 /*---------------------------------------------------------------------------
140 ---------------------------------------------------------------------------*/
142 /* Entry point to the CFG builder for trees. TP points to the list of
143 statements to be added to the flowgraph. */
146 build_tree_cfg (tree *tp)
148 /* Register specific tree functions. */
149 tree_register_cfg_hooks ();
151 memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
153 init_empty_tree_cfg ();
155 found_computed_goto = 0;
158 /* Computed gotos are hell to deal with, especially if there are
159 lots of them with a large number of destinations. So we factor
160 them to a common computed goto location before we build the
161 edge list. After we convert back to normal form, we will un-factor
162 the computed gotos since factoring introduces an unwanted jump. */
163 if (found_computed_goto)
164 factor_computed_gotos ();
166 /* Make sure there is always at least one block, even if it's empty. */
167 if (n_basic_blocks == NUM_FIXED_BLOCKS)
168 create_empty_bb (ENTRY_BLOCK_PTR);
170 /* Adjust the size of the array. */
171 if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
172 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
174 /* To speed up statement iterator walks, we first purge dead labels. */
175 cleanup_dead_labels ();
177 /* Group case nodes to reduce the number of edges.
178 We do this after cleaning up dead labels because otherwise we miss
179 a lot of obvious case merging opportunities. */
180 group_case_labels ();
182 /* Create the edges of the flowgraph. */
184 cleanup_dead_labels ();
186 /* Debugging dumps. */
188 /* Write the flowgraph to a VCG file. */
190 int local_dump_flags;
191 FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
194 tree_cfg2vcg (vcg_file);
195 dump_end (TDI_vcg, vcg_file);
199 #ifdef ENABLE_CHECKING
203 /* Dump a textual representation of the flowgraph. */
205 dump_tree_cfg (dump_file, dump_flags);
209 execute_build_cfg (void)
211 build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
215 struct gimple_opt_pass pass_build_cfg =
221 execute_build_cfg, /* execute */
224 0, /* static_pass_number */
225 TV_TREE_CFG, /* tv_id */
226 PROP_gimple_leh, /* properties_required */
227 PROP_cfg, /* properties_provided */
228 0, /* properties_destroyed */
229 0, /* todo_flags_start */
230 TODO_verify_stmts | TODO_cleanup_cfg /* todo_flags_finish */
234 /* Search the CFG for any computed gotos. If found, factor them to a
235 common computed goto site. Also record the location of that site so
236 that we can un-factor the gotos after we have converted back to
240 factor_computed_gotos (void)
243 tree factored_label_decl = NULL;
245 tree factored_computed_goto_label = NULL;
246 tree factored_computed_goto = NULL;
248 /* We know there are one or more computed gotos in this function.
249 Examine the last statement in each basic block to see if the block
250 ends with a computed goto. */
254 block_stmt_iterator bsi = bsi_last (bb);
259 last = bsi_stmt (bsi);
261 /* Ignore the computed goto we create when we factor the original
263 if (last == factored_computed_goto)
266 /* If the last statement is a computed goto, factor it. */
267 if (computed_goto_p (last))
271 /* The first time we find a computed goto we need to create
272 the factored goto block and the variable each original
273 computed goto will use for their goto destination. */
274 if (! factored_computed_goto)
276 basic_block new_bb = create_empty_bb (bb);
277 block_stmt_iterator new_bsi = bsi_start (new_bb);
279 /* Create the destination of the factored goto. Each original
280 computed goto will put its desired destination into this
281 variable and jump to the label we create immediately
283 var = create_tmp_var (ptr_type_node, "gotovar");
285 /* Build a label for the new block which will contain the
286 factored computed goto. */
287 factored_label_decl = create_artificial_label ();
288 factored_computed_goto_label
289 = build1 (LABEL_EXPR, void_type_node, factored_label_decl);
290 bsi_insert_after (&new_bsi, factored_computed_goto_label,
293 /* Build our new computed goto. */
294 factored_computed_goto = build1 (GOTO_EXPR, void_type_node, var);
295 bsi_insert_after (&new_bsi, factored_computed_goto,
299 /* Copy the original computed goto's destination into VAR. */
300 assignment = build_gimple_modify_stmt (var,
301 GOTO_DESTINATION (last));
302 bsi_insert_before (&bsi, assignment, BSI_SAME_STMT);
304 /* And re-vector the computed goto to the new destination. */
305 GOTO_DESTINATION (last) = factored_label_decl;
311 /* Build a flowgraph for the statement_list STMT_LIST. */
314 make_blocks (tree stmt_list)
316 tree_stmt_iterator i = tsi_start (stmt_list);
318 bool start_new_block = true;
319 bool first_stmt_of_list = true;
320 basic_block bb = ENTRY_BLOCK_PTR;
322 while (!tsi_end_p (i))
329 /* If the statement starts a new basic block or if we have determined
330 in a previous pass that we need to create a new block for STMT, do
332 if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
334 if (!first_stmt_of_list)
335 stmt_list = tsi_split_statement_list_before (&i);
336 bb = create_basic_block (stmt_list, NULL, bb);
337 start_new_block = false;
340 /* Now add STMT to BB and create the subgraphs for special statement
342 set_bb_for_stmt (stmt, bb);
344 if (computed_goto_p (stmt))
345 found_computed_goto = true;
347 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
349 if (stmt_ends_bb_p (stmt))
350 start_new_block = true;
353 first_stmt_of_list = false;
358 /* Create and return a new empty basic block after bb AFTER. */
361 create_bb (void *h, void *e, basic_block after)
367 /* Create and initialize a new basic block. Since alloc_block uses
368 ggc_alloc_cleared to allocate a basic block, we do not have to
369 clear the newly allocated basic block here. */
372 bb->index = last_basic_block;
374 bb->il.tree = GGC_CNEW (struct tree_bb_info);
375 set_bb_stmt_list (bb, h ? (tree) h : alloc_stmt_list ());
377 /* Add the new block to the linked list of blocks. */
378 link_block (bb, after);
380 /* Grow the basic block array if needed. */
381 if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
383 size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
384 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
387 /* Add the newly created block to the array. */
388 SET_BASIC_BLOCK (last_basic_block, bb);
397 /*---------------------------------------------------------------------------
399 ---------------------------------------------------------------------------*/
401 /* Fold COND_EXPR_COND of each COND_EXPR. */
404 fold_cond_expr_cond (void)
410 tree stmt = last_stmt (bb);
413 && TREE_CODE (stmt) == COND_EXPR)
418 fold_defer_overflow_warnings ();
419 cond = fold (COND_EXPR_COND (stmt));
420 zerop = integer_zerop (cond);
421 onep = integer_onep (cond);
422 fold_undefer_overflow_warnings (zerop || onep,
424 WARN_STRICT_OVERFLOW_CONDITIONAL);
426 COND_EXPR_COND (stmt) = boolean_false_node;
428 COND_EXPR_COND (stmt) = boolean_true_node;
433 /* Join all the blocks in the flowgraph. */
439 struct omp_region *cur_region = NULL;
441 /* Create an edge from entry to the first block with executable
443 make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
445 /* Traverse the basic block array placing edges. */
448 tree last = last_stmt (bb);
453 enum tree_code code = TREE_CODE (last);
457 make_goto_expr_edges (bb);
461 make_edge (bb, EXIT_BLOCK_PTR, 0);
465 make_cond_expr_edges (bb);
469 make_switch_expr_edges (bb);
473 make_eh_edges (last);
478 /* If this function receives a nonlocal goto, then we need to
479 make edges from this call site to all the nonlocal goto
481 if (tree_can_make_abnormal_goto (last))
482 make_abnormal_goto_edges (bb, true);
484 /* If this statement has reachable exception handlers, then
485 create abnormal edges to them. */
486 make_eh_edges (last);
488 /* Some calls are known not to return. */
489 fallthru = !(call_expr_flags (last) & ECF_NORETURN);
495 case GIMPLE_MODIFY_STMT:
496 if (is_ctrl_altering_stmt (last))
498 /* A GIMPLE_MODIFY_STMT may have a CALL_EXPR on its RHS and
499 the CALL_EXPR may have an abnormal edge. Search the RHS
500 for this case and create any required edges. */
501 if (tree_can_make_abnormal_goto (last))
502 make_abnormal_goto_edges (bb, true);
504 make_eh_edges (last);
516 cur_region = new_omp_region (bb, code, cur_region);
521 cur_region = new_omp_region (bb, code, cur_region);
525 case OMP_SECTIONS_SWITCH:
530 case OMP_ATOMIC_LOAD:
531 case OMP_ATOMIC_STORE:
537 /* In the case of an OMP_SECTION, the edge will go somewhere
538 other than the next block. This will be created later. */
539 cur_region->exit = bb;
540 fallthru = cur_region->type != OMP_SECTION;
541 cur_region = cur_region->outer;
545 cur_region->cont = bb;
546 switch (cur_region->type)
549 /* Mark all OMP_FOR and OMP_CONTINUE succs edges as abnormal
550 to prevent splitting them. */
551 single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
552 /* Make the loopback edge. */
553 make_edge (bb, single_succ (cur_region->entry),
556 /* Create an edge from OMP_FOR to exit, which corresponds to
557 the case that the body of the loop is not executed at
559 make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
560 make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
565 /* Wire up the edges into and out of the nested sections. */
567 basic_block switch_bb = single_succ (cur_region->entry);
569 struct omp_region *i;
570 for (i = cur_region->inner; i ; i = i->next)
572 gcc_assert (i->type == OMP_SECTION);
573 make_edge (switch_bb, i->entry, 0);
574 make_edge (i->exit, bb, EDGE_FALLTHRU);
577 /* Make the loopback edge to the block with
578 OMP_SECTIONS_SWITCH. */
579 make_edge (bb, switch_bb, 0);
581 /* Make the edge from the switch to exit. */
582 make_edge (switch_bb, bb->next_bb, 0);
593 gcc_assert (!stmt_ends_bb_p (last));
601 make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
607 /* Fold COND_EXPR_COND of each COND_EXPR. */
608 fold_cond_expr_cond ();
612 /* Create the edges for a COND_EXPR starting at block BB.
613 At this point, both clauses must contain only simple gotos. */
616 make_cond_expr_edges (basic_block bb)
618 tree entry = last_stmt (bb);
619 basic_block then_bb, else_bb;
620 tree then_label, else_label;
624 gcc_assert (TREE_CODE (entry) == COND_EXPR);
626 /* Entry basic blocks for each component. */
627 then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
628 else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
629 then_bb = label_to_block (then_label);
630 else_bb = label_to_block (else_label);
632 e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
633 e->goto_locus = EXPR_LOCATION (COND_EXPR_THEN (entry));
634 e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
636 e->goto_locus = EXPR_LOCATION (COND_EXPR_ELSE (entry));
638 /* We do not need the gotos anymore. */
639 COND_EXPR_THEN (entry) = NULL_TREE;
640 COND_EXPR_ELSE (entry) = NULL_TREE;
644 /* Called for each element in the hash table (P) as we delete the
645 edge to cases hash table.
647 Clear all the TREE_CHAINs to prevent problems with copying of
648 SWITCH_EXPRs and structure sharing rules, then free the hash table
652 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
653 void *data ATTRIBUTE_UNUSED)
657 for (t = (tree) *value; t; t = next)
659 next = TREE_CHAIN (t);
660 TREE_CHAIN (t) = NULL;
667 /* Start recording information mapping edges to case labels. */
670 start_recording_case_labels (void)
672 gcc_assert (edge_to_cases == NULL);
673 edge_to_cases = pointer_map_create ();
676 /* Return nonzero if we are recording information for case labels. */
679 recording_case_labels_p (void)
681 return (edge_to_cases != NULL);
684 /* Stop recording information mapping edges to case labels and
685 remove any information we have recorded. */
687 end_recording_case_labels (void)
689 pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
690 pointer_map_destroy (edge_to_cases);
691 edge_to_cases = NULL;
694 /* If we are inside a {start,end}_recording_cases block, then return
695 a chain of CASE_LABEL_EXPRs from T which reference E.
697 Otherwise return NULL. */
700 get_cases_for_edge (edge e, tree t)
706 /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
707 chains available. Return NULL so the caller can detect this case. */
708 if (!recording_case_labels_p ())
711 slot = pointer_map_contains (edge_to_cases, e);
715 /* If we did not find E in the hash table, then this must be the first
716 time we have been queried for information about E & T. Add all the
717 elements from T to the hash table then perform the query again. */
719 vec = SWITCH_LABELS (t);
720 n = TREE_VEC_LENGTH (vec);
721 for (i = 0; i < n; i++)
723 tree elt = TREE_VEC_ELT (vec, i);
724 tree lab = CASE_LABEL (elt);
725 basic_block label_bb = label_to_block (lab);
726 edge this_edge = find_edge (e->src, label_bb);
728 /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
730 slot = pointer_map_insert (edge_to_cases, this_edge);
731 TREE_CHAIN (elt) = (tree) *slot;
735 return (tree) *pointer_map_contains (edge_to_cases, e);
738 /* Create the edges for a SWITCH_EXPR starting at block BB.
739 At this point, the switch body has been lowered and the
740 SWITCH_LABELS filled in, so this is in effect a multi-way branch. */
743 make_switch_expr_edges (basic_block bb)
745 tree entry = last_stmt (bb);
749 vec = SWITCH_LABELS (entry);
750 n = TREE_VEC_LENGTH (vec);
752 for (i = 0; i < n; ++i)
754 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
755 basic_block label_bb = label_to_block (lab);
756 make_edge (bb, label_bb, 0);
761 /* Return the basic block holding label DEST. */
764 label_to_block_fn (struct function *ifun, tree dest)
766 int uid = LABEL_DECL_UID (dest);
768 /* We would die hard when faced by an undefined label. Emit a label to
769 the very first basic block. This will hopefully make even the dataflow
770 and undefined variable warnings quite right. */
771 if ((errorcount || sorrycount) && uid < 0)
773 block_stmt_iterator bsi =
774 bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
777 stmt = build1 (LABEL_EXPR, void_type_node, dest);
778 bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
779 uid = LABEL_DECL_UID (dest);
781 if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
782 <= (unsigned int) uid)
784 return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
787 /* Create edges for an abnormal goto statement at block BB. If FOR_CALL
788 is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR. */
791 make_abnormal_goto_edges (basic_block bb, bool for_call)
793 basic_block target_bb;
794 block_stmt_iterator bsi;
796 FOR_EACH_BB (target_bb)
797 for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
799 tree target = bsi_stmt (bsi);
801 if (TREE_CODE (target) != LABEL_EXPR)
804 target = LABEL_EXPR_LABEL (target);
806 /* Make an edge to every label block that has been marked as a
807 potential target for a computed goto or a non-local goto. */
808 if ((FORCED_LABEL (target) && !for_call)
809 || (DECL_NONLOCAL (target) && for_call))
811 make_edge (bb, target_bb, EDGE_ABNORMAL);
817 /* Create edges for a goto statement at block BB. */
820 make_goto_expr_edges (basic_block bb)
822 block_stmt_iterator last = bsi_last (bb);
823 tree goto_t = bsi_stmt (last);
825 /* A simple GOTO creates normal edges. */
826 if (simple_goto_p (goto_t))
828 tree dest = GOTO_DESTINATION (goto_t);
829 edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
830 e->goto_locus = EXPR_LOCATION (goto_t);
831 bsi_remove (&last, true);
835 /* A computed GOTO creates abnormal edges. */
836 make_abnormal_goto_edges (bb, false);
840 /*---------------------------------------------------------------------------
842 ---------------------------------------------------------------------------*/
844 /* Cleanup useless labels in basic blocks. This is something we wish
845 to do early because it allows us to group case labels before creating
846 the edges for the CFG, and it speeds up block statement iterators in
848 We rerun this pass after CFG is created, to get rid of the labels that
849 are no longer referenced. After then we do not run it any more, since
850 (almost) no new labels should be created. */
852 /* A map from basic block index to the leading label of that block. */
853 static struct label_record
858 /* True if the label is referenced from somewhere. */
862 /* Callback for for_each_eh_region. Helper for cleanup_dead_labels. */
864 update_eh_label (struct eh_region *region)
866 tree old_label = get_eh_region_tree_label (region);
870 basic_block bb = label_to_block (old_label);
872 /* ??? After optimizing, there may be EH regions with labels
873 that have already been removed from the function body, so
874 there is no basic block for them. */
878 new_label = label_for_bb[bb->index].label;
879 label_for_bb[bb->index].used = true;
880 set_eh_region_tree_label (region, new_label);
884 /* Given LABEL return the first label in the same basic block. */
886 main_block_label (tree label)
888 basic_block bb = label_to_block (label);
889 tree main_label = label_for_bb[bb->index].label;
891 /* label_to_block possibly inserted undefined label into the chain. */
894 label_for_bb[bb->index].label = label;
898 label_for_bb[bb->index].used = true;
902 /* Cleanup redundant labels. This is a three-step process:
903 1) Find the leading label for each block.
904 2) Redirect all references to labels to the leading labels.
905 3) Cleanup all useless labels. */
908 cleanup_dead_labels (void)
911 label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
913 /* Find a suitable label for each block. We use the first user-defined
914 label if there is one, or otherwise just the first label we see. */
917 block_stmt_iterator i;
919 for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
921 tree label, stmt = bsi_stmt (i);
923 if (TREE_CODE (stmt) != LABEL_EXPR)
926 label = LABEL_EXPR_LABEL (stmt);
928 /* If we have not yet seen a label for the current block,
929 remember this one and see if there are more labels. */
930 if (!label_for_bb[bb->index].label)
932 label_for_bb[bb->index].label = label;
936 /* If we did see a label for the current block already, but it
937 is an artificially created label, replace it if the current
938 label is a user defined label. */
939 if (!DECL_ARTIFICIAL (label)
940 && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
942 label_for_bb[bb->index].label = label;
948 /* Now redirect all jumps/branches to the selected label.
949 First do so for each block ending in a control statement. */
952 tree stmt = last_stmt (bb);
956 switch (TREE_CODE (stmt))
960 tree true_branch, false_branch;
962 true_branch = COND_EXPR_THEN (stmt);
963 false_branch = COND_EXPR_ELSE (stmt);
966 GOTO_DESTINATION (true_branch)
967 = main_block_label (GOTO_DESTINATION (true_branch));
969 GOTO_DESTINATION (false_branch)
970 = main_block_label (GOTO_DESTINATION (false_branch));
978 tree vec = SWITCH_LABELS (stmt);
979 size_t n = TREE_VEC_LENGTH (vec);
981 /* Replace all destination labels. */
982 for (i = 0; i < n; ++i)
984 tree elt = TREE_VEC_ELT (vec, i);
985 tree label = main_block_label (CASE_LABEL (elt));
986 CASE_LABEL (elt) = label;
991 /* We have to handle GOTO_EXPRs until they're removed, and we don't
992 remove them until after we've created the CFG edges. */
994 if (! computed_goto_p (stmt))
996 GOTO_DESTINATION (stmt)
997 = main_block_label (GOTO_DESTINATION (stmt));
1006 for_each_eh_region (update_eh_label);
1008 /* Finally, purge dead labels. All user-defined labels and labels that
1009 can be the target of non-local gotos and labels which have their
1010 address taken are preserved. */
1013 block_stmt_iterator i;
1014 tree label_for_this_bb = label_for_bb[bb->index].label;
1016 if (!label_for_this_bb)
1019 /* If the main label of the block is unused, we may still remove it. */
1020 if (!label_for_bb[bb->index].used)
1021 label_for_this_bb = NULL;
1023 for (i = bsi_start (bb); !bsi_end_p (i); )
1025 tree label, stmt = bsi_stmt (i);
1027 if (TREE_CODE (stmt) != LABEL_EXPR)
1030 label = LABEL_EXPR_LABEL (stmt);
1032 if (label == label_for_this_bb
1033 || ! DECL_ARTIFICIAL (label)
1034 || DECL_NONLOCAL (label)
1035 || FORCED_LABEL (label))
1038 bsi_remove (&i, true);
1042 free (label_for_bb);
1045 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1046 and scan the sorted vector of cases. Combine the ones jumping to the
1048 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
1051 group_case_labels (void)
1057 tree stmt = last_stmt (bb);
1058 if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1060 tree labels = SWITCH_LABELS (stmt);
1061 int old_size = TREE_VEC_LENGTH (labels);
1062 int i, j, new_size = old_size;
1063 tree default_case = NULL_TREE;
1064 tree default_label = NULL_TREE;
1066 /* The default label is always the last case in a switch
1067 statement after gimplification if it was not optimized
1069 if (!CASE_LOW (TREE_VEC_ELT (labels, old_size - 1))
1070 && !CASE_HIGH (TREE_VEC_ELT (labels, old_size - 1)))
1072 default_case = TREE_VEC_ELT (labels, old_size - 1);
1073 default_label = CASE_LABEL (default_case);
1077 /* Look for possible opportunities to merge cases. */
1079 while (i < old_size)
1081 tree base_case, base_label, base_high;
1082 base_case = TREE_VEC_ELT (labels, i);
1084 gcc_assert (base_case);
1085 base_label = CASE_LABEL (base_case);
1087 /* Discard cases that have the same destination as the
1089 if (base_label == default_label)
1091 TREE_VEC_ELT (labels, i) = NULL_TREE;
1097 base_high = CASE_HIGH (base_case) ?
1098 CASE_HIGH (base_case) : CASE_LOW (base_case);
1100 /* Try to merge case labels. Break out when we reach the end
1101 of the label vector or when we cannot merge the next case
1102 label with the current one. */
1103 while (i < old_size)
1105 tree merge_case = TREE_VEC_ELT (labels, i);
1106 tree merge_label = CASE_LABEL (merge_case);
1107 tree t = int_const_binop (PLUS_EXPR, base_high,
1108 integer_one_node, 1);
1110 /* Merge the cases if they jump to the same place,
1111 and their ranges are consecutive. */
1112 if (merge_label == base_label
1113 && tree_int_cst_equal (CASE_LOW (merge_case), t))
1115 base_high = CASE_HIGH (merge_case) ?
1116 CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1117 CASE_HIGH (base_case) = base_high;
1118 TREE_VEC_ELT (labels, i) = NULL_TREE;
1127 /* Compress the case labels in the label vector, and adjust the
1128 length of the vector. */
1129 for (i = 0, j = 0; i < new_size; i++)
1131 while (! TREE_VEC_ELT (labels, j))
1133 TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1135 TREE_VEC_LENGTH (labels) = new_size;
1140 /* Checks whether we can merge block B into block A. */
1143 tree_can_merge_blocks_p (basic_block a, basic_block b)
1146 block_stmt_iterator bsi;
1149 if (!single_succ_p (a))
1152 if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1155 if (single_succ (a) != b)
1158 if (!single_pred_p (b))
1161 if (b == EXIT_BLOCK_PTR)
1164 /* If A ends by a statement causing exceptions or something similar, we
1165 cannot merge the blocks. */
1166 /* This CONST_CAST is okay because last_stmt doesn't modify its
1167 argument and the return value is assign to a const_tree. */
1168 stmt = last_stmt (CONST_CAST_BB (a));
1169 if (stmt && stmt_ends_bb_p (stmt))
1172 /* Do not allow a block with only a non-local label to be merged. */
1173 if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1174 && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1177 /* It must be possible to eliminate all phi nodes in B. If ssa form
1178 is not up-to-date, we cannot eliminate any phis; however, if only
1179 some symbols as whole are marked for renaming, this is not a problem,
1180 as phi nodes for those symbols are irrelevant in updating anyway. */
1181 phi = phi_nodes (b);
1184 if (name_mappings_registered_p ())
1187 for (; phi; phi = PHI_CHAIN (phi))
1188 if (!is_gimple_reg (PHI_RESULT (phi))
1189 && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
1193 /* Do not remove user labels. */
1194 for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1196 stmt = bsi_stmt (bsi);
1197 if (TREE_CODE (stmt) != LABEL_EXPR)
1199 if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1203 /* Protect the loop latches. */
1205 && b->loop_father->latch == b)
1211 /* Replaces all uses of NAME by VAL. */
1214 replace_uses_by (tree name, tree val)
1216 imm_use_iterator imm_iter;
1221 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1223 if (TREE_CODE (stmt) != PHI_NODE)
1224 push_stmt_changes (&stmt);
1226 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1228 replace_exp (use, val);
1230 if (TREE_CODE (stmt) == PHI_NODE)
1232 e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
1233 if (e->flags & EDGE_ABNORMAL)
1235 /* This can only occur for virtual operands, since
1236 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1237 would prevent replacement. */
1238 gcc_assert (!is_gimple_reg (name));
1239 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1244 if (TREE_CODE (stmt) != PHI_NODE)
1248 fold_stmt_inplace (stmt);
1249 if (cfgcleanup_altered_bbs)
1250 bitmap_set_bit (cfgcleanup_altered_bbs, bb_for_stmt (stmt)->index);
1252 /* FIXME. This should go in pop_stmt_changes. */
1253 rhs = get_rhs (stmt);
1254 if (TREE_CODE (rhs) == ADDR_EXPR)
1255 recompute_tree_invariant_for_addr_expr (rhs);
1257 maybe_clean_or_replace_eh_stmt (stmt, stmt);
1259 pop_stmt_changes (&stmt);
1263 gcc_assert (has_zero_uses (name));
1265 /* Also update the trees stored in loop structures. */
1271 FOR_EACH_LOOP (li, loop, 0)
1273 substitute_in_loop_info (loop, name, val);
1278 /* Merge block B into block A. */
1281 tree_merge_blocks (basic_block a, basic_block b)
1283 block_stmt_iterator bsi;
1284 tree_stmt_iterator last;
1288 fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1290 /* Remove all single-valued PHI nodes from block B of the form
1291 V_i = PHI <V_j> by propagating V_j to all the uses of V_i. */
1293 for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1295 tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1297 bool may_replace_uses = may_propagate_copy (def, use);
1299 /* In case we maintain loop closed ssa form, do not propagate arguments
1300 of loop exit phi nodes. */
1302 && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1303 && is_gimple_reg (def)
1304 && TREE_CODE (use) == SSA_NAME
1305 && a->loop_father != b->loop_father)
1306 may_replace_uses = false;
1308 if (!may_replace_uses)
1310 gcc_assert (is_gimple_reg (def));
1312 /* Note that just emitting the copies is fine -- there is no problem
1313 with ordering of phi nodes. This is because A is the single
1314 predecessor of B, therefore results of the phi nodes cannot
1315 appear as arguments of the phi nodes. */
1316 copy = build_gimple_modify_stmt (def, use);
1317 bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1318 SSA_NAME_DEF_STMT (def) = copy;
1319 remove_phi_node (phi, NULL, false);
1323 /* If we deal with a PHI for virtual operands, we can simply
1324 propagate these without fussing with folding or updating
1326 if (!is_gimple_reg (def))
1328 imm_use_iterator iter;
1329 use_operand_p use_p;
1332 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1333 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1334 SET_USE (use_p, use);
1337 replace_uses_by (def, use);
1338 remove_phi_node (phi, NULL, true);
1342 /* Ensure that B follows A. */
1343 move_block_after (b, a);
1345 gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1346 gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1348 /* Remove labels from B and set bb_for_stmt to A for other statements. */
1349 for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1351 if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1353 tree label = bsi_stmt (bsi);
1355 bsi_remove (&bsi, false);
1356 /* Now that we can thread computed gotos, we might have
1357 a situation where we have a forced label in block B
1358 However, the label at the start of block B might still be
1359 used in other ways (think about the runtime checking for
1360 Fortran assigned gotos). So we can not just delete the
1361 label. Instead we move the label to the start of block A. */
1362 if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1364 block_stmt_iterator dest_bsi = bsi_start (a);
1365 bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1370 change_bb_for_stmt (bsi_stmt (bsi), a);
1375 /* Merge the chains. */
1376 last = tsi_last (bb_stmt_list (a));
1377 tsi_link_after (&last, bb_stmt_list (b), TSI_NEW_STMT);
1378 set_bb_stmt_list (b, NULL_TREE);
1380 if (cfgcleanup_altered_bbs)
1381 bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1385 /* Return the one of two successors of BB that is not reachable by a
1386 reached by a complex edge, if there is one. Else, return BB. We use
1387 this in optimizations that use post-dominators for their heuristics,
1388 to catch the cases in C++ where function calls are involved. */
1391 single_noncomplex_succ (basic_block bb)
1394 if (EDGE_COUNT (bb->succs) != 2)
1397 e0 = EDGE_SUCC (bb, 0);
1398 e1 = EDGE_SUCC (bb, 1);
1399 if (e0->flags & EDGE_COMPLEX)
1401 if (e1->flags & EDGE_COMPLEX)
1408 /* Walk the function tree removing unnecessary statements.
1410 * Empty statement nodes are removed
1412 * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1414 * Unnecessary COND_EXPRs are removed
1416 * Some unnecessary BIND_EXPRs are removed
1418 Clearly more work could be done. The trick is doing the analysis
1419 and removal fast enough to be a net improvement in compile times.
1421 Note that when we remove a control structure such as a COND_EXPR
1422 BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1423 to ensure we eliminate all the useless code. */
1434 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1437 remove_useless_stmts_warn_notreached (tree stmt)
1439 if (EXPR_HAS_LOCATION (stmt))
1441 location_t loc = EXPR_LOCATION (stmt);
1442 if (LOCATION_LINE (loc) > 0)
1444 warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
1449 switch (TREE_CODE (stmt))
1451 case STATEMENT_LIST:
1453 tree_stmt_iterator i;
1454 for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1455 if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1461 if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1463 if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1465 if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1469 case TRY_FINALLY_EXPR:
1470 case TRY_CATCH_EXPR:
1471 if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1473 if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1478 return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1479 case EH_FILTER_EXPR:
1480 return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1482 return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1485 /* Not a live container. */
1493 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1495 tree then_clause, else_clause, cond;
1496 bool save_has_label, then_has_label, else_has_label;
1498 save_has_label = data->has_label;
1499 data->has_label = false;
1500 data->last_goto = NULL;
1502 remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1504 then_has_label = data->has_label;
1505 data->has_label = false;
1506 data->last_goto = NULL;
1508 remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1510 else_has_label = data->has_label;
1511 data->has_label = save_has_label | then_has_label | else_has_label;
1513 then_clause = COND_EXPR_THEN (*stmt_p);
1514 else_clause = COND_EXPR_ELSE (*stmt_p);
1515 cond = fold (COND_EXPR_COND (*stmt_p));
1517 /* If neither arm does anything at all, we can remove the whole IF. */
1518 if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1520 *stmt_p = build_empty_stmt ();
1521 data->repeat = true;
1524 /* If there are no reachable statements in an arm, then we can
1525 zap the entire conditional. */
1526 else if (integer_nonzerop (cond) && !else_has_label)
1528 if (warn_notreached)
1529 remove_useless_stmts_warn_notreached (else_clause);
1530 *stmt_p = then_clause;
1531 data->repeat = true;
1533 else if (integer_zerop (cond) && !then_has_label)
1535 if (warn_notreached)
1536 remove_useless_stmts_warn_notreached (then_clause);
1537 *stmt_p = else_clause;
1538 data->repeat = true;
1541 /* Check a couple of simple things on then/else with single stmts. */
1544 tree then_stmt = expr_only (then_clause);
1545 tree else_stmt = expr_only (else_clause);
1547 /* Notice branches to a common destination. */
1548 if (then_stmt && else_stmt
1549 && TREE_CODE (then_stmt) == GOTO_EXPR
1550 && TREE_CODE (else_stmt) == GOTO_EXPR
1551 && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1553 *stmt_p = then_stmt;
1554 data->repeat = true;
1557 /* If the THEN/ELSE clause merely assigns a value to a variable or
1558 parameter which is already known to contain that value, then
1559 remove the useless THEN/ELSE clause. */
1560 else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1563 && TREE_CODE (else_stmt) == GIMPLE_MODIFY_STMT
1564 && GIMPLE_STMT_OPERAND (else_stmt, 0) == cond
1565 && integer_zerop (GIMPLE_STMT_OPERAND (else_stmt, 1)))
1566 COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1568 else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1569 && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1570 || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1571 && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1573 tree stmt = (TREE_CODE (cond) == EQ_EXPR
1574 ? then_stmt : else_stmt);
1575 tree *location = (TREE_CODE (cond) == EQ_EXPR
1576 ? &COND_EXPR_THEN (*stmt_p)
1577 : &COND_EXPR_ELSE (*stmt_p));
1580 && TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1581 && GIMPLE_STMT_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1582 && GIMPLE_STMT_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1583 *location = alloc_stmt_list ();
1587 /* Protect GOTOs in the arm of COND_EXPRs from being removed. They
1588 would be re-introduced during lowering. */
1589 data->last_goto = NULL;
1594 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1596 bool save_may_branch, save_may_throw;
1597 bool this_may_branch, this_may_throw;
1599 /* Collect may_branch and may_throw information for the body only. */
1600 save_may_branch = data->may_branch;
1601 save_may_throw = data->may_throw;
1602 data->may_branch = false;
1603 data->may_throw = false;
1604 data->last_goto = NULL;
1606 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1608 this_may_branch = data->may_branch;
1609 this_may_throw = data->may_throw;
1610 data->may_branch |= save_may_branch;
1611 data->may_throw |= save_may_throw;
1612 data->last_goto = NULL;
1614 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1616 /* If the body is empty, then we can emit the FINALLY block without
1617 the enclosing TRY_FINALLY_EXPR. */
1618 if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1620 *stmt_p = TREE_OPERAND (*stmt_p, 1);
1621 data->repeat = true;
1624 /* If the handler is empty, then we can emit the TRY block without
1625 the enclosing TRY_FINALLY_EXPR. */
1626 else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1628 *stmt_p = TREE_OPERAND (*stmt_p, 0);
1629 data->repeat = true;
1632 /* If the body neither throws, nor branches, then we can safely
1633 string the TRY and FINALLY blocks together. */
1634 else if (!this_may_branch && !this_may_throw)
1636 tree stmt = *stmt_p;
1637 *stmt_p = TREE_OPERAND (stmt, 0);
1638 append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1639 data->repeat = true;
1645 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1647 bool save_may_throw, this_may_throw;
1648 tree_stmt_iterator i;
1651 /* Collect may_throw information for the body only. */
1652 save_may_throw = data->may_throw;
1653 data->may_throw = false;
1654 data->last_goto = NULL;
1656 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1658 this_may_throw = data->may_throw;
1659 data->may_throw = save_may_throw;
1661 /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR. */
1662 if (!this_may_throw)
1664 if (warn_notreached)
1665 remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1666 *stmt_p = TREE_OPERAND (*stmt_p, 0);
1667 data->repeat = true;
1671 /* Process the catch clause specially. We may be able to tell that
1672 no exceptions propagate past this point. */
1674 this_may_throw = true;
1675 i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1676 stmt = tsi_stmt (i);
1677 data->last_goto = NULL;
1679 switch (TREE_CODE (stmt))
1682 for (; !tsi_end_p (i); tsi_next (&i))
1684 stmt = tsi_stmt (i);
1685 /* If we catch all exceptions, then the body does not
1686 propagate exceptions past this point. */
1687 if (CATCH_TYPES (stmt) == NULL)
1688 this_may_throw = false;
1689 data->last_goto = NULL;
1690 remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1694 case EH_FILTER_EXPR:
1695 if (EH_FILTER_MUST_NOT_THROW (stmt))
1696 this_may_throw = false;
1697 else if (EH_FILTER_TYPES (stmt) == NULL)
1698 this_may_throw = false;
1699 remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1703 /* Otherwise this is a cleanup. */
1704 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1706 /* If the cleanup is empty, then we can emit the TRY block without
1707 the enclosing TRY_CATCH_EXPR. */
1708 if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1710 *stmt_p = TREE_OPERAND (*stmt_p, 0);
1711 data->repeat = true;
1715 data->may_throw |= this_may_throw;
1720 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1724 /* First remove anything underneath the BIND_EXPR. */
1725 remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1727 /* If the BIND_EXPR has no variables, then we can pull everything
1728 up one level and remove the BIND_EXPR, unless this is the toplevel
1729 BIND_EXPR for the current function or an inlined function.
1731 When this situation occurs we will want to apply this
1732 optimization again. */
1733 block = BIND_EXPR_BLOCK (*stmt_p);
1734 if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1735 && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1737 || ! BLOCK_ABSTRACT_ORIGIN (block)
1738 || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1741 *stmt_p = BIND_EXPR_BODY (*stmt_p);
1742 data->repeat = true;
1748 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1750 tree dest = GOTO_DESTINATION (*stmt_p);
1752 data->may_branch = true;
1753 data->last_goto = NULL;
1755 /* Record the last goto expr, so that we can delete it if unnecessary. */
1756 if (TREE_CODE (dest) == LABEL_DECL)
1757 data->last_goto = stmt_p;
1762 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1764 tree label = LABEL_EXPR_LABEL (*stmt_p);
1766 data->has_label = true;
1768 /* We do want to jump across non-local label receiver code. */
1769 if (DECL_NONLOCAL (label))
1770 data->last_goto = NULL;
1772 else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1774 *data->last_goto = build_empty_stmt ();
1775 data->repeat = true;
1778 /* ??? Add something here to delete unused labels. */
1782 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1783 decl. This allows us to eliminate redundant or useless
1784 calls to "const" functions.
1786 Gimplifier already does the same operation, but we may notice functions
1787 being const and pure once their calls has been gimplified, so we need
1788 to update the flag. */
1791 update_call_expr_flags (tree call)
1793 tree decl = get_callee_fndecl (call);
1796 if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1797 TREE_SIDE_EFFECTS (call) = 0;
1798 if (TREE_NOTHROW (decl))
1799 TREE_NOTHROW (call) = 1;
1803 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1806 notice_special_calls (tree t)
1808 int flags = call_expr_flags (t);
1810 if (flags & ECF_MAY_BE_ALLOCA)
1811 current_function_calls_alloca = true;
1812 if (flags & ECF_RETURNS_TWICE)
1813 current_function_calls_setjmp = true;
1817 /* Clear flags set by notice_special_calls. Used by dead code removal
1818 to update the flags. */
1821 clear_special_calls (void)
1823 current_function_calls_alloca = false;
1824 current_function_calls_setjmp = false;
1829 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1833 switch (TREE_CODE (t))
1836 remove_useless_stmts_cond (tp, data);
1839 case TRY_FINALLY_EXPR:
1840 remove_useless_stmts_tf (tp, data);
1843 case TRY_CATCH_EXPR:
1844 remove_useless_stmts_tc (tp, data);
1848 remove_useless_stmts_bind (tp, data);
1852 remove_useless_stmts_goto (tp, data);
1856 remove_useless_stmts_label (tp, data);
1861 data->last_goto = NULL;
1862 data->may_branch = true;
1867 data->last_goto = NULL;
1868 notice_special_calls (t);
1869 update_call_expr_flags (t);
1870 if (tree_could_throw_p (t))
1871 data->may_throw = true;
1877 case GIMPLE_MODIFY_STMT:
1878 data->last_goto = NULL;
1880 op = get_call_expr_in (t);
1883 update_call_expr_flags (op);
1884 notice_special_calls (op);
1886 if (tree_could_throw_p (t))
1887 data->may_throw = true;
1890 case STATEMENT_LIST:
1892 tree_stmt_iterator i = tsi_start (t);
1893 while (!tsi_end_p (i))
1896 if (IS_EMPTY_STMT (t))
1902 remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1905 if (TREE_CODE (t) == STATEMENT_LIST)
1907 tsi_link_before (&i, t, TSI_SAME_STMT);
1917 data->last_goto = NULL;
1921 data->last_goto = NULL;
1927 remove_useless_stmts (void)
1929 struct rus_data data;
1931 clear_special_calls ();
1935 memset (&data, 0, sizeof (data));
1936 remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1938 while (data.repeat);
1943 struct gimple_opt_pass pass_remove_useless_stmts =
1947 "useless", /* name */
1949 remove_useless_stmts, /* execute */
1952 0, /* static_pass_number */
1954 PROP_gimple_any, /* properties_required */
1955 0, /* properties_provided */
1956 0, /* properties_destroyed */
1957 0, /* todo_flags_start */
1958 TODO_dump_func /* todo_flags_finish */
1962 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1965 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1969 /* Since this block is no longer reachable, we can just delete all
1970 of its PHI nodes. */
1971 phi = phi_nodes (bb);
1974 tree next = PHI_CHAIN (phi);
1975 remove_phi_node (phi, NULL_TREE, true);
1979 /* Remove edges to BB's successors. */
1980 while (EDGE_COUNT (bb->succs) > 0)
1981 remove_edge (EDGE_SUCC (bb, 0));
1985 /* Remove statements of basic block BB. */
1988 remove_bb (basic_block bb)
1990 block_stmt_iterator i;
1991 source_location loc = UNKNOWN_LOCATION;
1995 fprintf (dump_file, "Removing basic block %d\n", bb->index);
1996 if (dump_flags & TDF_DETAILS)
1998 dump_bb (bb, dump_file, 0);
1999 fprintf (dump_file, "\n");
2005 struct loop *loop = bb->loop_father;
2007 /* If a loop gets removed, clean up the information associated
2009 if (loop->latch == bb
2010 || loop->header == bb)
2011 free_numbers_of_iterations_estimates_loop (loop);
2014 /* Remove all the instructions in the block. */
2015 if (bb_stmt_list (bb) != NULL_TREE)
2017 for (i = bsi_start (bb); !bsi_end_p (i);)
2019 tree stmt = bsi_stmt (i);
2020 if (TREE_CODE (stmt) == LABEL_EXPR
2021 && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
2022 || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
2025 block_stmt_iterator new_bsi;
2027 /* A non-reachable non-local label may still be referenced.
2028 But it no longer needs to carry the extra semantics of
2030 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
2032 DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
2033 FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
2036 new_bb = bb->prev_bb;
2037 new_bsi = bsi_start (new_bb);
2038 bsi_remove (&i, false);
2039 bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2043 /* Release SSA definitions if we are in SSA. Note that we
2044 may be called when not in SSA. For example,
2045 final_cleanup calls this function via
2046 cleanup_tree_cfg. */
2047 if (gimple_in_ssa_p (cfun))
2048 release_defs (stmt);
2050 bsi_remove (&i, true);
2053 /* Don't warn for removed gotos. Gotos are often removed due to
2054 jump threading, thus resulting in bogus warnings. Not great,
2055 since this way we lose warnings for gotos in the original
2056 program that are indeed unreachable. */
2057 if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2059 if (EXPR_HAS_LOCATION (stmt))
2060 loc = EXPR_LOCATION (stmt);
2065 /* If requested, give a warning that the first statement in the
2066 block is unreachable. We walk statements backwards in the
2067 loop above, so the last statement we process is the first statement
2069 if (loc > BUILTINS_LOCATION && LOCATION_LINE (loc) > 0)
2070 warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2072 remove_phi_nodes_and_edges_for_unreachable_block (bb);
2077 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2078 predicate VAL, return the edge that will be taken out of the block.
2079 If VAL does not match a unique edge, NULL is returned. */
2082 find_taken_edge (basic_block bb, tree val)
2086 stmt = last_stmt (bb);
2089 gcc_assert (is_ctrl_stmt (stmt));
2092 if (! is_gimple_min_invariant (val))
2095 if (TREE_CODE (stmt) == COND_EXPR)
2096 return find_taken_edge_cond_expr (bb, val);
2098 if (TREE_CODE (stmt) == SWITCH_EXPR)
2099 return find_taken_edge_switch_expr (bb, val);
2101 if (computed_goto_p (stmt))
2103 /* Only optimize if the argument is a label, if the argument is
2104 not a label then we can not construct a proper CFG.
2106 It may be the case that we only need to allow the LABEL_REF to
2107 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2108 appear inside a LABEL_EXPR just to be safe. */
2109 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2110 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2111 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2118 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2119 statement, determine which of the outgoing edges will be taken out of the
2120 block. Return NULL if either edge may be taken. */
2123 find_taken_edge_computed_goto (basic_block bb, tree val)
2128 dest = label_to_block (val);
2131 e = find_edge (bb, dest);
2132 gcc_assert (e != NULL);
2138 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2139 statement, determine which of the two edges will be taken out of the
2140 block. Return NULL if either edge may be taken. */
2143 find_taken_edge_cond_expr (basic_block bb, tree val)
2145 edge true_edge, false_edge;
2147 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2149 gcc_assert (TREE_CODE (val) == INTEGER_CST);
2150 return (integer_zerop (val) ? false_edge : true_edge);
2153 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2154 statement, determine which edge will be taken out of the block. Return
2155 NULL if any edge may be taken. */
2158 find_taken_edge_switch_expr (basic_block bb, tree val)
2160 tree switch_expr, taken_case;
2161 basic_block dest_bb;
2164 switch_expr = last_stmt (bb);
2165 taken_case = find_case_label_for_value (switch_expr, val);
2166 dest_bb = label_to_block (CASE_LABEL (taken_case));
2168 e = find_edge (bb, dest_bb);
2174 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2175 We can make optimal use here of the fact that the case labels are
2176 sorted: We can do a binary search for a case matching VAL. */
2179 find_case_label_for_value (tree switch_expr, tree val)
2181 tree vec = SWITCH_LABELS (switch_expr);
2182 size_t low, high, n = TREE_VEC_LENGTH (vec);
2183 tree default_case = TREE_VEC_ELT (vec, n - 1);
2185 for (low = -1, high = n - 1; high - low > 1; )
2187 size_t i = (high + low) / 2;
2188 tree t = TREE_VEC_ELT (vec, i);
2191 /* Cache the result of comparing CASE_LOW and val. */
2192 cmp = tree_int_cst_compare (CASE_LOW (t), val);
2199 if (CASE_HIGH (t) == NULL)
2201 /* A singe-valued case label. */
2207 /* A case range. We can only handle integer ranges. */
2208 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2213 return default_case;
2219 /*---------------------------------------------------------------------------
2221 ---------------------------------------------------------------------------*/
2223 /* Dump tree-specific information of block BB to file OUTF. */
2226 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2228 dump_generic_bb (outf, bb, indent, TDF_VOPS|TDF_MEMSYMS);
2232 /* Dump a basic block on stderr. */
2235 debug_tree_bb (basic_block bb)
2237 dump_bb (bb, stderr, 0);
2241 /* Dump basic block with index N on stderr. */
2244 debug_tree_bb_n (int n)
2246 debug_tree_bb (BASIC_BLOCK (n));
2247 return BASIC_BLOCK (n);
2251 /* Dump the CFG on stderr.
2253 FLAGS are the same used by the tree dumping functions
2254 (see TDF_* in tree-pass.h). */
2257 debug_tree_cfg (int flags)
2259 dump_tree_cfg (stderr, flags);
2263 /* Dump the program showing basic block boundaries on the given FILE.
2265 FLAGS are the same used by the tree dumping functions (see TDF_* in
2269 dump_tree_cfg (FILE *file, int flags)
2271 if (flags & TDF_DETAILS)
2273 const char *funcname
2274 = lang_hooks.decl_printable_name (current_function_decl, 2);
2277 fprintf (file, ";; Function %s\n\n", funcname);
2278 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2279 n_basic_blocks, n_edges, last_basic_block);
2281 brief_dump_cfg (file);
2282 fprintf (file, "\n");
2285 if (flags & TDF_STATS)
2286 dump_cfg_stats (file);
2288 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2292 /* Dump CFG statistics on FILE. */
2295 dump_cfg_stats (FILE *file)
2297 static long max_num_merged_labels = 0;
2298 unsigned long size, total = 0;
2301 const char * const fmt_str = "%-30s%-13s%12s\n";
2302 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2303 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2304 const char * const fmt_str_3 = "%-43s%11lu%c\n";
2305 const char *funcname
2306 = lang_hooks.decl_printable_name (current_function_decl, 2);
2309 fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2311 fprintf (file, "---------------------------------------------------------\n");
2312 fprintf (file, fmt_str, "", " Number of ", "Memory");
2313 fprintf (file, fmt_str, "", " instances ", "used ");
2314 fprintf (file, "---------------------------------------------------------\n");
2316 size = n_basic_blocks * sizeof (struct basic_block_def);
2318 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2319 SCALE (size), LABEL (size));
2323 num_edges += EDGE_COUNT (bb->succs);
2324 size = num_edges * sizeof (struct edge_def);
2326 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2328 fprintf (file, "---------------------------------------------------------\n");
2329 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2331 fprintf (file, "---------------------------------------------------------\n");
2332 fprintf (file, "\n");
2334 if (cfg_stats.num_merged_labels > max_num_merged_labels)
2335 max_num_merged_labels = cfg_stats.num_merged_labels;
2337 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2338 cfg_stats.num_merged_labels, max_num_merged_labels);
2340 fprintf (file, "\n");
2344 /* Dump CFG statistics on stderr. Keep extern so that it's always
2345 linked in the final executable. */
2348 debug_cfg_stats (void)
2350 dump_cfg_stats (stderr);
2354 /* Dump the flowgraph to a .vcg FILE. */
2357 tree_cfg2vcg (FILE *file)
2362 const char *funcname
2363 = lang_hooks.decl_printable_name (current_function_decl, 2);
2365 /* Write the file header. */
2366 fprintf (file, "graph: { title: \"%s\"\n", funcname);
2367 fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2368 fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2370 /* Write blocks and edges. */
2371 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2373 fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2376 if (e->flags & EDGE_FAKE)
2377 fprintf (file, " linestyle: dotted priority: 10");
2379 fprintf (file, " linestyle: solid priority: 100");
2381 fprintf (file, " }\n");
2387 enum tree_code head_code, end_code;
2388 const char *head_name, *end_name;
2391 tree first = first_stmt (bb);
2392 tree last = last_stmt (bb);
2396 head_code = TREE_CODE (first);
2397 head_name = tree_code_name[head_code];
2398 head_line = get_lineno (first);
2401 head_name = "no-statement";
2405 end_code = TREE_CODE (last);
2406 end_name = tree_code_name[end_code];
2407 end_line = get_lineno (last);
2410 end_name = "no-statement";
2412 fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2413 bb->index, bb->index, head_name, head_line, end_name,
2416 FOR_EACH_EDGE (e, ei, bb->succs)
2418 if (e->dest == EXIT_BLOCK_PTR)
2419 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2421 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2423 if (e->flags & EDGE_FAKE)
2424 fprintf (file, " priority: 10 linestyle: dotted");
2426 fprintf (file, " priority: 100 linestyle: solid");
2428 fprintf (file, " }\n");
2431 if (bb->next_bb != EXIT_BLOCK_PTR)
2435 fputs ("}\n\n", file);
2440 /*---------------------------------------------------------------------------
2441 Miscellaneous helpers
2442 ---------------------------------------------------------------------------*/
2444 /* Return true if T represents a stmt that always transfers control. */
2447 is_ctrl_stmt (const_tree t)
2449 return (TREE_CODE (t) == COND_EXPR
2450 || TREE_CODE (t) == SWITCH_EXPR
2451 || TREE_CODE (t) == GOTO_EXPR
2452 || TREE_CODE (t) == RETURN_EXPR
2453 || TREE_CODE (t) == RESX_EXPR);
2457 /* Return true if T is a statement that may alter the flow of control
2458 (e.g., a call to a non-returning function). */
2461 is_ctrl_altering_stmt (const_tree t)
2466 call = get_call_expr_in (CONST_CAST_TREE (t));
2469 /* A non-pure/const CALL_EXPR alters flow control if the current
2470 function has nonlocal labels. */
2471 if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2474 /* A CALL_EXPR also alters control flow if it does not return. */
2475 if (call_expr_flags (call) & ECF_NORETURN)
2479 /* OpenMP directives alter control flow. */
2480 if (OMP_DIRECTIVE_P (t))
2483 /* If a statement can throw, it alters control flow. */
2484 return tree_can_throw_internal (t);
2488 /* Return true if T is a computed goto. */
2491 computed_goto_p (const_tree t)
2493 return (TREE_CODE (t) == GOTO_EXPR
2494 && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2498 /* Return true if T is a simple local goto. */
2501 simple_goto_p (const_tree t)
2503 return (TREE_CODE (t) == GOTO_EXPR
2504 && TREE_CODE (GOTO_DESTINATION (t)) == LABEL_DECL);
2508 /* Return true if T can make an abnormal transfer of control flow.
2509 Transfers of control flow associated with EH are excluded. */
2512 tree_can_make_abnormal_goto (const_tree t)
2514 if (computed_goto_p (t))
2516 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
2517 t = GIMPLE_STMT_OPERAND (t, 1);
2518 if (TREE_CODE (t) == WITH_SIZE_EXPR)
2519 t = TREE_OPERAND (t, 0);
2520 if (TREE_CODE (t) == CALL_EXPR)
2521 return TREE_SIDE_EFFECTS (t) && current_function_has_nonlocal_label;
2526 /* Return true if T should start a new basic block. PREV_T is the
2527 statement preceding T. It is used when T is a label or a case label.
2528 Labels should only start a new basic block if their previous statement
2529 wasn't a label. Otherwise, sequence of labels would generate
2530 unnecessary basic blocks that only contain a single label. */
2533 stmt_starts_bb_p (const_tree t, const_tree prev_t)
2538 /* LABEL_EXPRs start a new basic block only if the preceding
2539 statement wasn't a label of the same type. This prevents the
2540 creation of consecutive blocks that have nothing but a single
2542 if (TREE_CODE (t) == LABEL_EXPR)
2544 /* Nonlocal and computed GOTO targets always start a new block. */
2545 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2546 || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2549 if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2551 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2554 cfg_stats.num_merged_labels++;
2565 /* Return true if T should end a basic block. */
2568 stmt_ends_bb_p (const_tree t)
2570 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2573 /* Remove block annotations and other datastructures. */
2576 delete_tree_cfg_annotations (void)
2579 block_stmt_iterator bsi;
2581 /* Remove annotations from every tree in the function. */
2583 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2585 tree stmt = bsi_stmt (bsi);
2586 ggc_free (stmt->base.ann);
2587 stmt->base.ann = NULL;
2589 label_to_block_map = NULL;
2593 /* Return the first statement in basic block BB. */
2596 first_stmt (basic_block bb)
2598 block_stmt_iterator i = bsi_start (bb);
2599 return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2602 /* Return the last statement in basic block BB. */
2605 last_stmt (basic_block bb)
2607 block_stmt_iterator b = bsi_last (bb);
2608 return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2611 /* Return the last statement of an otherwise empty block. Return NULL
2612 if the block is totally empty, or if it contains more than one
2616 last_and_only_stmt (basic_block bb)
2618 block_stmt_iterator i = bsi_last (bb);
2624 last = bsi_stmt (i);
2629 /* Empty statements should no longer appear in the instruction stream.
2630 Everything that might have appeared before should be deleted by
2631 remove_useless_stmts, and the optimizers should just bsi_remove
2632 instead of smashing with build_empty_stmt.
2634 Thus the only thing that should appear here in a block containing
2635 one executable statement is a label. */
2636 prev = bsi_stmt (i);
2637 if (TREE_CODE (prev) == LABEL_EXPR)
2644 /* Mark BB as the basic block holding statement T. */
2647 set_bb_for_stmt (tree t, basic_block bb)
2649 if (TREE_CODE (t) == PHI_NODE)
2651 else if (TREE_CODE (t) == STATEMENT_LIST)
2653 tree_stmt_iterator i;
2654 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2655 set_bb_for_stmt (tsi_stmt (i), bb);
2659 stmt_ann_t ann = get_stmt_ann (t);
2662 /* If the statement is a label, add the label to block-to-labels map
2663 so that we can speed up edge creation for GOTO_EXPRs. */
2664 if (TREE_CODE (t) == LABEL_EXPR)
2668 t = LABEL_EXPR_LABEL (t);
2669 uid = LABEL_DECL_UID (t);
2672 unsigned old_len = VEC_length (basic_block, label_to_block_map);
2673 LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2674 if (old_len <= (unsigned) uid)
2676 unsigned new_len = 3 * uid / 2;
2678 VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
2683 /* We're moving an existing label. Make sure that we've
2684 removed it from the old block. */
2686 || !VEC_index (basic_block, label_to_block_map, uid));
2687 VEC_replace (basic_block, label_to_block_map, uid, bb);
2692 /* Faster version of set_bb_for_stmt that assume that statement is being moved
2693 from one basic block to another.
2694 For BB splitting we can run into quadratic case, so performance is quite
2695 important and knowing that the tables are big enough, change_bb_for_stmt
2696 can inline as leaf function. */
2698 change_bb_for_stmt (tree t, basic_block bb)
2700 get_stmt_ann (t)->bb = bb;
2701 if (TREE_CODE (t) == LABEL_EXPR)
2702 VEC_replace (basic_block, label_to_block_map,
2703 LABEL_DECL_UID (LABEL_EXPR_LABEL (t)), bb);
2706 /* Finds iterator for STMT. */
2708 extern block_stmt_iterator
2709 bsi_for_stmt (tree stmt)
2711 block_stmt_iterator bsi;
2713 for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2714 if (bsi_stmt (bsi) == stmt)
2720 /* Mark statement T as modified, and update it. */
2722 update_modified_stmts (tree t)
2724 if (!ssa_operands_active ())
2726 if (TREE_CODE (t) == STATEMENT_LIST)
2728 tree_stmt_iterator i;
2730 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2732 stmt = tsi_stmt (i);
2733 update_stmt_if_modified (stmt);
2737 update_stmt_if_modified (t);
2740 /* Insert statement (or statement list) T before the statement
2741 pointed-to by iterator I. M specifies how to update iterator I
2742 after insertion (see enum bsi_iterator_update). */
2745 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2747 set_bb_for_stmt (t, i->bb);
2748 update_modified_stmts (t);
2749 tsi_link_before (&i->tsi, t, m);
2753 /* Insert statement (or statement list) T after the statement
2754 pointed-to by iterator I. M specifies how to update iterator I
2755 after insertion (see enum bsi_iterator_update). */
2758 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2760 set_bb_for_stmt (t, i->bb);
2761 update_modified_stmts (t);
2762 tsi_link_after (&i->tsi, t, m);
2766 /* Remove the statement pointed to by iterator I. The iterator is updated
2767 to the next statement.
2769 When REMOVE_EH_INFO is true we remove the statement pointed to by
2770 iterator I from the EH tables. Otherwise we do not modify the EH
2773 Generally, REMOVE_EH_INFO should be true when the statement is going to
2774 be removed from the IL and not reinserted elsewhere. */
2777 bsi_remove (block_stmt_iterator *i, bool remove_eh_info)
2779 tree t = bsi_stmt (*i);
2780 set_bb_for_stmt (t, NULL);
2781 delink_stmt_imm_use (t);
2782 tsi_delink (&i->tsi);
2783 mark_stmt_modified (t);
2786 remove_stmt_from_eh_region (t);
2787 gimple_remove_stmt_histograms (cfun, t);
2792 /* Move the statement at FROM so it comes right after the statement at TO. */
2795 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2797 tree stmt = bsi_stmt (*from);
2798 bsi_remove (from, false);
2799 /* We must have BSI_NEW_STMT here, as bsi_move_after is sometimes used to
2800 move statements to an empty block. */
2801 bsi_insert_after (to, stmt, BSI_NEW_STMT);
2805 /* Move the statement at FROM so it comes right before the statement at TO. */
2808 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2810 tree stmt = bsi_stmt (*from);
2811 bsi_remove (from, false);
2812 /* For consistency with bsi_move_after, it might be better to have
2813 BSI_NEW_STMT here; however, that breaks several places that expect
2814 that TO does not change. */
2815 bsi_insert_before (to, stmt, BSI_SAME_STMT);
2819 /* Move the statement at FROM to the end of basic block BB. */
2822 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2824 block_stmt_iterator last = bsi_last (bb);
2826 /* Have to check bsi_end_p because it could be an empty block. */
2827 if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2828 bsi_move_before (from, &last);
2830 bsi_move_after (from, &last);
2834 /* Replace the contents of the statement pointed to by iterator BSI
2835 with STMT. If UPDATE_EH_INFO is true, the exception handling
2836 information of the original statement is moved to the new statement. */
2839 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
2842 tree orig_stmt = bsi_stmt (*bsi);
2844 if (stmt == orig_stmt)
2846 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2847 set_bb_for_stmt (stmt, bsi->bb);
2849 /* Preserve EH region information from the original statement, if
2850 requested by the caller. */
2853 eh_region = lookup_stmt_eh_region (orig_stmt);
2856 remove_stmt_from_eh_region (orig_stmt);
2857 add_stmt_to_eh_region (stmt, eh_region);
2861 gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
2862 gimple_remove_stmt_histograms (cfun, orig_stmt);
2863 delink_stmt_imm_use (orig_stmt);
2864 *bsi_stmt_ptr (*bsi) = stmt;
2865 mark_stmt_modified (stmt);
2866 update_modified_stmts (stmt);
2870 /* Insert the statement pointed-to by BSI into edge E. Every attempt
2871 is made to place the statement in an existing basic block, but
2872 sometimes that isn't possible. When it isn't possible, the edge is
2873 split and the statement is added to the new block.
2875 In all cases, the returned *BSI points to the correct location. The
2876 return value is true if insertion should be done after the location,
2877 or false if it should be done before the location. If new basic block
2878 has to be created, it is stored in *NEW_BB. */
2881 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2882 basic_block *new_bb)
2884 basic_block dest, src;
2890 /* If the destination has one predecessor which has no PHI nodes,
2891 insert there. Except for the exit block.
2893 The requirement for no PHI nodes could be relaxed. Basically we
2894 would have to examine the PHIs to prove that none of them used
2895 the value set by the statement we want to insert on E. That
2896 hardly seems worth the effort. */
2897 if (single_pred_p (dest)
2898 && ! phi_nodes (dest)
2899 && dest != EXIT_BLOCK_PTR)
2901 *bsi = bsi_start (dest);
2902 if (bsi_end_p (*bsi))
2905 /* Make sure we insert after any leading labels. */
2906 tmp = bsi_stmt (*bsi);
2907 while (TREE_CODE (tmp) == LABEL_EXPR)
2910 if (bsi_end_p (*bsi))
2912 tmp = bsi_stmt (*bsi);
2915 if (bsi_end_p (*bsi))
2917 *bsi = bsi_last (dest);
2924 /* If the source has one successor, the edge is not abnormal and
2925 the last statement does not end a basic block, insert there.
2926 Except for the entry block. */
2928 if ((e->flags & EDGE_ABNORMAL) == 0
2929 && single_succ_p (src)
2930 && src != ENTRY_BLOCK_PTR)
2932 *bsi = bsi_last (src);
2933 if (bsi_end_p (*bsi))
2936 tmp = bsi_stmt (*bsi);
2937 if (!stmt_ends_bb_p (tmp))
2940 /* Insert code just before returning the value. We may need to decompose
2941 the return in the case it contains non-trivial operand. */
2942 if (TREE_CODE (tmp) == RETURN_EXPR)
2944 tree op = TREE_OPERAND (tmp, 0);
2945 if (op && !is_gimple_val (op))
2947 gcc_assert (TREE_CODE (op) == GIMPLE_MODIFY_STMT);
2948 bsi_insert_before (bsi, op, BSI_NEW_STMT);
2949 TREE_OPERAND (tmp, 0) = GIMPLE_STMT_OPERAND (op, 0);
2956 /* Otherwise, create a new basic block, and split this edge. */
2957 dest = split_edge (e);
2960 e = single_pred_edge (dest);
2965 /* This routine will commit all pending edge insertions, creating any new
2966 basic blocks which are necessary. */
2969 bsi_commit_edge_inserts (void)
2975 bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
2978 FOR_EACH_EDGE (e, ei, bb->succs)
2979 bsi_commit_one_edge_insert (e, NULL);
2983 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
2984 to this block, otherwise set it to NULL. */
2987 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
2991 if (PENDING_STMT (e))
2993 block_stmt_iterator bsi;
2994 tree stmt = PENDING_STMT (e);
2996 PENDING_STMT (e) = NULL_TREE;
2998 if (tree_find_edge_insert_loc (e, &bsi, new_bb))
2999 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3001 bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3006 /* Add STMT to the pending list of edge E. No actual insertion is
3007 made until a call to bsi_commit_edge_inserts () is made. */
3010 bsi_insert_on_edge (edge e, tree stmt)
3012 append_to_statement_list (stmt, &PENDING_STMT (e));
3015 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If a new
3016 block has to be created, it is returned. */
3019 bsi_insert_on_edge_immediate (edge e, tree stmt)
3021 block_stmt_iterator bsi;
3022 basic_block new_bb = NULL;
3024 gcc_assert (!PENDING_STMT (e));
3026 if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3027 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3029 bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3034 /*---------------------------------------------------------------------------
3035 Tree specific functions for CFG manipulation
3036 ---------------------------------------------------------------------------*/
3038 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */
3041 reinstall_phi_args (edge new_edge, edge old_edge)
3044 edge_var_map_vector v;
3048 v = redirect_edge_var_map_vector (old_edge);
3052 for (i = 0, phi = phi_nodes (new_edge->dest);
3053 VEC_iterate (edge_var_map, v, i, vm) && phi;
3054 i++, phi = PHI_CHAIN (phi))
3056 tree result = redirect_edge_var_map_result (vm);
3057 tree arg = redirect_edge_var_map_def (vm);
3059 gcc_assert (result == PHI_RESULT (phi));
3061 add_phi_arg (phi, arg, new_edge);
3064 redirect_edge_var_map_clear (old_edge);
3067 /* Returns the basic block after which the new basic block created
3068 by splitting edge EDGE_IN should be placed. Tries to keep the new block
3069 near its "logical" location. This is of most help to humans looking
3070 at debugging dumps. */
3073 split_edge_bb_loc (edge edge_in)
3075 basic_block dest = edge_in->dest;
3077 if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3078 return edge_in->src;
3080 return dest->prev_bb;
3083 /* Split a (typically critical) edge EDGE_IN. Return the new block.
3084 Abort on abnormal edges. */
3087 tree_split_edge (edge edge_in)
3089 basic_block new_bb, after_bb, dest;
3092 /* Abnormal edges cannot be split. */
3093 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3095 dest = edge_in->dest;
3097 after_bb = split_edge_bb_loc (edge_in);
3099 new_bb = create_empty_bb (after_bb);
3100 new_bb->frequency = EDGE_FREQUENCY (edge_in);
3101 new_bb->count = edge_in->count;
3102 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3103 new_edge->probability = REG_BR_PROB_BASE;
3104 new_edge->count = edge_in->count;
3106 e = redirect_edge_and_branch (edge_in, new_bb);
3107 gcc_assert (e == edge_in);
3108 reinstall_phi_args (new_edge, e);
3113 /* Callback for walk_tree, check that all elements with address taken are
3114 properly noticed as such. The DATA is an int* that is 1 if TP was seen
3115 inside a PHI node. */
3118 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3125 /* Check operand N for being valid GIMPLE and give error MSG if not. */
3126 #define CHECK_OP(N, MSG) \
3127 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
3128 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3130 switch (TREE_CODE (t))
3133 if (SSA_NAME_IN_FREE_LIST (t))
3135 error ("SSA name in freelist but still referenced");
3141 x = fold (ASSERT_EXPR_COND (t));
3142 if (x == boolean_false_node)
3144 error ("ASSERT_EXPR with an always-false condition");
3152 case GIMPLE_MODIFY_STMT:
3153 x = GIMPLE_STMT_OPERAND (t, 0);
3154 if (TREE_CODE (x) == BIT_FIELD_REF
3155 && is_gimple_reg (TREE_OPERAND (x, 0)))
3157 error ("GIMPLE register modified with BIT_FIELD_REF");
3166 bool old_side_effects;
3169 bool new_side_effects;
3171 old_invariant = TREE_INVARIANT (t);
3172 old_constant = TREE_CONSTANT (t);
3173 old_side_effects = TREE_SIDE_EFFECTS (t);
3175 recompute_tree_invariant_for_addr_expr (t);
3176 new_invariant = TREE_INVARIANT (t);
3177 new_side_effects = TREE_SIDE_EFFECTS (t);
3178 new_constant = TREE_CONSTANT (t);
3180 if (old_invariant != new_invariant)
3182 error ("invariant not recomputed when ADDR_EXPR changed");
3186 if (old_constant != new_constant)
3188 error ("constant not recomputed when ADDR_EXPR changed");
3191 if (old_side_effects != new_side_effects)
3193 error ("side effects not recomputed when ADDR_EXPR changed");
3197 /* Skip any references (they will be checked when we recurse down the
3198 tree) and ensure that any variable used as a prefix is marked
3200 for (x = TREE_OPERAND (t, 0);
3201 handled_component_p (x);
3202 x = TREE_OPERAND (x, 0))
3205 if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3207 if (!TREE_ADDRESSABLE (x))
3209 error ("address taken, but ADDRESSABLE bit not set");
3217 x = COND_EXPR_COND (t);
3218 if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
3220 error ("non-integral used in condition");
3223 if (!is_gimple_condexpr (x))
3225 error ("invalid conditional operand");
3232 case FIX_TRUNC_EXPR:
3237 case NON_LVALUE_EXPR:
3238 case TRUTH_NOT_EXPR:
3239 CHECK_OP (0, "invalid operand to unary operator");
3246 case ARRAY_RANGE_REF:
3248 case VIEW_CONVERT_EXPR:
3249 /* We have a nest of references. Verify that each of the operands
3250 that determine where to reference is either a constant or a variable,
3251 verify that the base is valid, and then show we've already checked
3253 while (handled_component_p (t))
3255 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3256 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3257 else if (TREE_CODE (t) == ARRAY_REF
3258 || TREE_CODE (t) == ARRAY_RANGE_REF)
3260 CHECK_OP (1, "invalid array index");
3261 if (TREE_OPERAND (t, 2))
3262 CHECK_OP (2, "invalid array lower bound");
3263 if (TREE_OPERAND (t, 3))
3264 CHECK_OP (3, "invalid array stride");
3266 else if (TREE_CODE (t) == BIT_FIELD_REF)
3268 if (!host_integerp (TREE_OPERAND (t, 1), 1)
3269 || !host_integerp (TREE_OPERAND (t, 2), 1))
3271 error ("invalid position or size operand to BIT_FIELD_REF");
3274 else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
3275 && (TYPE_PRECISION (TREE_TYPE (t))
3276 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3278 error ("integral result type precision does not match "
3279 "field size of BIT_FIELD_REF");
3282 if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
3283 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
3284 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3286 error ("mode precision of non-integral result does not "
3287 "match field size of BIT_FIELD_REF");
3292 t = TREE_OPERAND (t, 0);
3295 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
3297 error ("invalid reference prefix");
3304 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3305 POINTER_PLUS_EXPR. */
3306 if (POINTER_TYPE_P (TREE_TYPE (t)))
3308 error ("invalid operand to plus/minus, type is a pointer");
3311 CHECK_OP (0, "invalid operand to binary operator");
3312 CHECK_OP (1, "invalid operand to binary operator");
3315 case POINTER_PLUS_EXPR:
3316 /* Check to make sure the first operand is a pointer or reference type. */
3317 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3319 error ("invalid operand to pointer plus, first operand is not a pointer");
3322 /* Check to make sure the second operand is an integer with type of
3324 if (!useless_type_conversion_p (sizetype,
3325 TREE_TYPE (TREE_OPERAND (t, 1))))
3327 error ("invalid operand to pointer plus, second operand is not an "
3328 "integer with type of sizetype.");
3338 case UNORDERED_EXPR:
3347 case TRUNC_DIV_EXPR:
3349 case FLOOR_DIV_EXPR:
3350 case ROUND_DIV_EXPR:
3351 case TRUNC_MOD_EXPR:
3353 case FLOOR_MOD_EXPR:
3354 case ROUND_MOD_EXPR:
3356 case EXACT_DIV_EXPR:
3366 CHECK_OP (0, "invalid operand to binary operator");
3367 CHECK_OP (1, "invalid operand to binary operator");
3371 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3383 /* Verifies if EXPR is a valid GIMPLE unary expression. Returns true
3384 if there is an error, otherwise false. */
3387 verify_gimple_unary_expr (const_tree expr)
3389 tree op = TREE_OPERAND (expr, 0);
3390 tree type = TREE_TYPE (expr);
3392 if (!is_gimple_val (op))
3394 error ("invalid operand in unary expression");
3398 /* For general unary expressions we have the operations type
3399 as the effective type the operation is carried out on. So all
3400 we need to require is that the operand is trivially convertible
3402 if (!useless_type_conversion_p (type, TREE_TYPE (op)))
3404 error ("type mismatch in unary expression");
3405 debug_generic_expr (type);
3406 debug_generic_expr (TREE_TYPE (op));
3413 /* Verifies if EXPR is a valid GIMPLE binary expression. Returns true
3414 if there is an error, otherwise false. */
3417 verify_gimple_binary_expr (const_tree expr)
3419 tree op0 = TREE_OPERAND (expr, 0);
3420 tree op1 = TREE_OPERAND (expr, 1);
3421 tree type = TREE_TYPE (expr);
3423 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3425 error ("invalid operands in binary expression");
3429 /* For general binary expressions we have the operations type
3430 as the effective type the operation is carried out on. So all
3431 we need to require is that both operands are trivially convertible
3433 if (!useless_type_conversion_p (type, TREE_TYPE (op0))
3434 || !useless_type_conversion_p (type, TREE_TYPE (op1)))
3436 error ("type mismatch in binary expression");
3437 debug_generic_stmt (type);
3438 debug_generic_stmt (TREE_TYPE (op0));
3439 debug_generic_stmt (TREE_TYPE (op1));
3446 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3447 Returns true if there is an error, otherwise false. */
3450 verify_gimple_min_lval (tree expr)
3454 if (is_gimple_id (expr))
3457 if (TREE_CODE (expr) != INDIRECT_REF
3458 && TREE_CODE (expr) != ALIGN_INDIRECT_REF
3459 && TREE_CODE (expr) != MISALIGNED_INDIRECT_REF)
3461 error ("invalid expression for min lvalue");
3465 op = TREE_OPERAND (expr, 0);
3466 if (!is_gimple_val (op))
3468 error ("invalid operand in indirect reference");
3469 debug_generic_stmt (op);
3472 if (!useless_type_conversion_p (TREE_TYPE (expr),
3473 TREE_TYPE (TREE_TYPE (op))))
3475 error ("type mismatch in indirect reference");
3476 debug_generic_stmt (TREE_TYPE (expr));
3477 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3484 /* Verify if EXPR is a valid GIMPLE reference expression. Returns true
3485 if there is an error, otherwise false. */
3488 verify_gimple_reference (tree expr)
3490 while (handled_component_p (expr))
3492 tree op = TREE_OPERAND (expr, 0);
3494 if (TREE_CODE (expr) == ARRAY_REF
3495 || TREE_CODE (expr) == ARRAY_RANGE_REF)
3497 if (!is_gimple_val (TREE_OPERAND (expr, 1))
3498 || (TREE_OPERAND (expr, 2)
3499 && !is_gimple_val (TREE_OPERAND (expr, 2)))
3500 || (TREE_OPERAND (expr, 3)
3501 && !is_gimple_val (TREE_OPERAND (expr, 3))))
3503 error ("invalid operands to array reference");
3504 debug_generic_stmt (expr);
3509 /* Verify if the reference array element types are compatible. */
3510 if (TREE_CODE (expr) == ARRAY_REF
3511 && !useless_type_conversion_p (TREE_TYPE (expr),
3512 TREE_TYPE (TREE_TYPE (op))))
3514 error ("type mismatch in array reference");
3515 debug_generic_stmt (TREE_TYPE (expr));
3516 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3519 if (TREE_CODE (expr) == ARRAY_RANGE_REF
3520 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3521 TREE_TYPE (TREE_TYPE (op))))
3523 error ("type mismatch in array range reference");
3524 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3525 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3529 if ((TREE_CODE (expr) == REALPART_EXPR
3530 || TREE_CODE (expr) == IMAGPART_EXPR)
3531 && !useless_type_conversion_p (TREE_TYPE (expr),
3532 TREE_TYPE (TREE_TYPE (op))))
3534 error ("type mismatch in real/imagpart reference");
3535 debug_generic_stmt (TREE_TYPE (expr));
3536 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3540 if (TREE_CODE (expr) == COMPONENT_REF
3541 && !useless_type_conversion_p (TREE_TYPE (expr),
3542 TREE_TYPE (TREE_OPERAND (expr, 1))))
3544 error ("type mismatch in component reference");
3545 debug_generic_stmt (TREE_TYPE (expr));
3546 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3550 /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3551 is nothing to verify. Gross mismatches at most invoke
3552 undefined behavior. */
3557 return verify_gimple_min_lval (expr);
3560 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3561 list of pointer-to types that is trivially convertible to DEST. */
3564 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3568 if (!TYPE_POINTER_TO (src_obj))
3571 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3572 if (useless_type_conversion_p (dest, src))
3578 /* Verify the GIMPLE expression EXPR. Returns true if there is an
3579 error, otherwise false. */
3582 verify_gimple_expr (tree expr)
3584 tree type = TREE_TYPE (expr);
3586 if (is_gimple_val (expr))
3589 /* Special codes we cannot handle via their class. */
3590 switch (TREE_CODE (expr))
3595 tree op = TREE_OPERAND (expr, 0);
3596 if (!is_gimple_val (op))
3598 error ("invalid operand in conversion");
3602 /* Allow conversions between integral types and between
3604 if ((INTEGRAL_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3605 || (POINTER_TYPE_P (type) && POINTER_TYPE_P (TREE_TYPE (op))))
3608 /* Allow conversions between integral types and pointers only if
3609 there is no sign or zero extension involved. */
3610 if (((POINTER_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3611 || (POINTER_TYPE_P (TREE_TYPE (op)) && INTEGRAL_TYPE_P (type)))
3612 && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op)))
3615 /* Allow conversion from integer to offset type and vice versa. */
3616 if ((TREE_CODE (type) == OFFSET_TYPE
3617 && TREE_CODE (TREE_TYPE (op)) == INTEGER_TYPE)
3618 || (TREE_CODE (type) == INTEGER_TYPE
3619 && TREE_CODE (TREE_TYPE (op)) == OFFSET_TYPE))
3622 /* Otherwise assert we are converting between types of the
3624 if (TREE_CODE (type) != TREE_CODE (TREE_TYPE (op)))
3626 error ("invalid types in nop conversion");
3627 debug_generic_expr (type);
3628 debug_generic_expr (TREE_TYPE (op));
3637 tree op = TREE_OPERAND (expr, 0);
3638 if (!is_gimple_val (op))
3640 error ("invalid operand in int to float conversion");
3643 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3644 || !SCALAR_FLOAT_TYPE_P (type))
3646 error ("invalid types in conversion to floating point");
3647 debug_generic_expr (type);
3648 debug_generic_expr (TREE_TYPE (op));
3654 case FIX_TRUNC_EXPR:
3656 tree op = TREE_OPERAND (expr, 0);
3657 if (!is_gimple_val (op))
3659 error ("invalid operand in float to int conversion");
3662 if (!INTEGRAL_TYPE_P (type)
3663 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
3665 error ("invalid types in conversion to integer");
3666 debug_generic_expr (type);
3667 debug_generic_expr (TREE_TYPE (op));
3675 tree op0 = TREE_OPERAND (expr, 0);
3676 tree op1 = TREE_OPERAND (expr, 1);
3677 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3679 error ("invalid operands in complex expression");
3682 if (!TREE_CODE (type) == COMPLEX_TYPE
3683 || !(TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
3684 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0)))
3685 || !(TREE_CODE (TREE_TYPE (op1)) == INTEGER_TYPE
3686 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op1)))
3687 || !useless_type_conversion_p (TREE_TYPE (type),
3689 || !useless_type_conversion_p (TREE_TYPE (type),
3692 error ("type mismatch in complex expression");
3693 debug_generic_stmt (TREE_TYPE (expr));
3694 debug_generic_stmt (TREE_TYPE (op0));
3695 debug_generic_stmt (TREE_TYPE (op1));
3703 /* This is used like COMPLEX_EXPR but for vectors. */
3704 if (TREE_CODE (type) != VECTOR_TYPE)
3706 error ("constructor not allowed for non-vector types");
3707 debug_generic_stmt (type);
3710 /* FIXME: verify constructor arguments. */
3719 tree op0 = TREE_OPERAND (expr, 0);
3720 tree op1 = TREE_OPERAND (expr, 1);
3721 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3723 error ("invalid operands in shift expression");
3726 if (!TREE_CODE (TREE_TYPE (op1)) == INTEGER_TYPE
3727 || !useless_type_conversion_p (type, TREE_TYPE (op0)))
3729 error ("type mismatch in shift expression");
3730 debug_generic_stmt (TREE_TYPE (expr));
3731 debug_generic_stmt (TREE_TYPE (op0));
3732 debug_generic_stmt (TREE_TYPE (op1));
3741 tree op0 = TREE_OPERAND (expr, 0);
3742 tree op1 = TREE_OPERAND (expr, 1);
3743 if (POINTER_TYPE_P (type)
3744 || POINTER_TYPE_P (TREE_TYPE (op0))
3745 || POINTER_TYPE_P (TREE_TYPE (op1)))
3747 error ("invalid (pointer) operands to plus/minus");
3750 /* Continue with generic binary expression handling. */
3754 case POINTER_PLUS_EXPR:
3756 tree op0 = TREE_OPERAND (expr, 0);
3757 tree op1 = TREE_OPERAND (expr, 1);
3758 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3760 error ("invalid operands in pointer plus expression");
3763 if (!POINTER_TYPE_P (TREE_TYPE (op0))
3764 || !useless_type_conversion_p (type, TREE_TYPE (op0))
3765 || !useless_type_conversion_p (sizetype, TREE_TYPE (op1)))
3767 error ("type mismatch in pointer plus expression");
3768 debug_generic_stmt (type);
3769 debug_generic_stmt (TREE_TYPE (op0));
3770 debug_generic_stmt (TREE_TYPE (op1));
3778 tree op0 = TREE_OPERAND (expr, 0);
3779 tree op1 = TREE_OPERAND (expr, 1);
3780 tree op2 = TREE_OPERAND (expr, 2);
3781 if ((!is_gimple_val (op1)
3782 && TREE_CODE (TREE_TYPE (op1)) != VOID_TYPE)
3783 || (!is_gimple_val (op2)
3784 && TREE_CODE (TREE_TYPE (op2)) != VOID_TYPE))
3786 error ("invalid operands in conditional expression");
3789 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3790 || (TREE_CODE (TREE_TYPE (op1)) != VOID_TYPE
3791 && !useless_type_conversion_p (type, TREE_TYPE (op1)))
3792 || (TREE_CODE (TREE_TYPE (op2)) != VOID_TYPE
3793 && !useless_type_conversion_p (type, TREE_TYPE (op2))))
3795 error ("type mismatch in conditional expression");
3796 debug_generic_stmt (type);
3797 debug_generic_stmt (TREE_TYPE (op0));
3798 debug_generic_stmt (TREE_TYPE (op1));
3799 debug_generic_stmt (TREE_TYPE (op2));
3802 return verify_gimple_expr (op0);
3807 tree op = TREE_OPERAND (expr, 0);
3808 if (!is_gimple_addressable (op))
3810 error ("invalid operand in unary expression");
3813 if (!one_pointer_to_useless_type_conversion_p (type, TREE_TYPE (op))
3814 /* FIXME: a longstanding wart, &a == &a[0]. */
3815 && (TREE_CODE (TREE_TYPE (op)) != ARRAY_TYPE
3816 || !one_pointer_to_useless_type_conversion_p (type,
3817 TREE_TYPE (TREE_TYPE (op)))))
3819 error ("type mismatch in address expression");
3820 debug_generic_stmt (TREE_TYPE (expr));
3821 debug_generic_stmt (TYPE_POINTER_TO (TREE_TYPE (op)));
3825 return verify_gimple_reference (op);
3828 case TRUTH_ANDIF_EXPR:
3829 case TRUTH_ORIF_EXPR:
3830 case TRUTH_AND_EXPR:
3832 case TRUTH_XOR_EXPR:
3834 tree op0 = TREE_OPERAND (expr, 0);
3835 tree op1 = TREE_OPERAND (expr, 1);
3837 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3839 error ("invalid operands in truth expression");
3843 /* We allow any kind of integral typed argument and result. */
3844 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3845 || !INTEGRAL_TYPE_P (TREE_TYPE (op1))
3846 || !INTEGRAL_TYPE_P (type))
3848 error ("type mismatch in binary truth expression");
3849 debug_generic_stmt (type);
3850 debug_generic_stmt (TREE_TYPE (op0));
3851 debug_generic_stmt (TREE_TYPE (op1));
3858 case TRUTH_NOT_EXPR:
3860 tree op = TREE_OPERAND (expr, 0);
3862 if (!is_gimple_val (op))
3864 error ("invalid operand in unary not");
3868 /* For TRUTH_NOT_EXPR we can have any kind of integral
3869 typed arguments and results. */
3870 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3871 || !INTEGRAL_TYPE_P (type))
3873 error ("type mismatch in not expression");
3874 debug_generic_expr (TREE_TYPE (expr));
3875 debug_generic_expr (TREE_TYPE (op));
3883 /* FIXME. The C frontend passes unpromoted arguments in case it
3884 didn't see a function declaration before the call. */
3894 /* Generic handling via classes. */
3895 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3898 return verify_gimple_unary_expr (expr);
3901 return verify_gimple_binary_expr (expr);
3904 return verify_gimple_reference (expr);
3906 case tcc_comparison:
3908 tree op0 = TREE_OPERAND (expr, 0);
3909 tree op1 = TREE_OPERAND (expr, 1);
3910 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3912 error ("invalid operands in comparison expression");
3915 /* For comparisons we do not have the operations type as the
3916 effective type the comparison is carried out in. Instead
3917 we require that either the first operand is trivially
3918 convertible into the second, or the other way around.
3919 The resulting type of a comparison may be any integral type.
3920 Because we special-case pointers to void we allow
3921 comparisons of pointers with the same mode as well. */
3922 if ((!useless_type_conversion_p (TREE_TYPE (op0), TREE_TYPE (op1))
3923 && !useless_type_conversion_p (TREE_TYPE (op1), TREE_TYPE (op0))
3924 && (!POINTER_TYPE_P (TREE_TYPE (op0))
3925 || !POINTER_TYPE_P (TREE_TYPE (op1))
3926 || TYPE_MODE (TREE_TYPE (op0)) != TYPE_MODE (TREE_TYPE (op1))))
3927 || !INTEGRAL_TYPE_P (type))
3929 error ("type mismatch in comparison expression");
3930 debug_generic_stmt (TREE_TYPE (expr));
3931 debug_generic_stmt (TREE_TYPE (op0));
3932 debug_generic_stmt (TREE_TYPE (op1));
3945 /* Verify the GIMPLE assignment statement STMT. Returns true if there
3946 is an error, otherwise false. */
3949 verify_gimple_modify_stmt (const_tree stmt)
3951 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3952 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3954 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
3956 if (!useless_type_conversion_p (TREE_TYPE (lhs),
3959 error ("non-trivial conversion at assignment");
3960 debug_generic_expr (TREE_TYPE (lhs));
3961 debug_generic_expr (TREE_TYPE (rhs));
3965 /* Loads/stores from/to a variable are ok. */
3966 if ((is_gimple_val (lhs)
3967 && is_gimple_variable (rhs))
3968 || (is_gimple_val (rhs)
3969 && is_gimple_variable (lhs)))
3972 /* Aggregate copies are ok. */
3973 if (!is_gimple_reg_type (TREE_TYPE (lhs))
3974 && !is_gimple_reg_type (TREE_TYPE (rhs)))
3977 /* We might get 'loads' from a parameter which is not a gimple value. */
3978 if (TREE_CODE (rhs) == PARM_DECL)
3979 return verify_gimple_expr (lhs);
3981 if (!is_gimple_variable (lhs)
3982 && verify_gimple_expr (lhs))
3985 if (!is_gimple_variable (rhs)
3986 && verify_gimple_expr (rhs))
3992 /* Verify the GIMPLE statement STMT. Returns true if there is an
3993 error, otherwise false. */
3996 verify_gimple_stmt (tree stmt)
3998 if (!is_gimple_stmt (stmt))
4000 error ("is not a valid GIMPLE statement");
4004 if (OMP_DIRECTIVE_P (stmt))
4006 /* OpenMP directives are validated by the FE and never operated
4007 on by the optimizers. Furthermore, OMP_FOR may contain
4008 non-gimple expressions when the main index variable has had
4009 its address taken. This does not affect the loop itself
4010 because the header of an OMP_FOR is merely used to determine
4011 how to setup the parallel iteration. */
4015 switch (TREE_CODE (stmt))
4017 case GIMPLE_MODIFY_STMT:
4018 return verify_gimple_modify_stmt (stmt);
4025 if (!is_gimple_val (TREE_OPERAND (stmt, 0)))
4027 error ("invalid operand to switch statement");
4028 debug_generic_expr (TREE_OPERAND (stmt, 0));
4034 tree op = TREE_OPERAND (stmt, 0);
4036 if (TREE_CODE (TREE_TYPE (stmt)) != VOID_TYPE)
4038 error ("type error in return expression");
4043 || TREE_CODE (op) == RESULT_DECL)
4046 return verify_gimple_modify_stmt (op);
4051 return verify_gimple_expr (stmt);
4054 case CHANGE_DYNAMIC_TYPE_EXPR:
4064 /* Verify the GIMPLE statements inside the statement list STMTS.
4065 Returns true if there were any errors. */
4068 verify_gimple_2 (tree stmts)
4070 tree_stmt_iterator tsi;
4073 for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
4075 tree stmt = tsi_stmt (tsi);
4077 switch (TREE_CODE (stmt))
4080 err |= verify_gimple_2 (BIND_EXPR_BODY (stmt));
4083 case TRY_CATCH_EXPR:
4084 case TRY_FINALLY_EXPR:
4085 err |= verify_gimple_2 (TREE_OPERAND (stmt, 0));
4086 err |= verify_gimple_2 (TREE_OPERAND (stmt, 1));
4090 err |= verify_gimple_2 (CATCH_BODY (stmt));
4093 case EH_FILTER_EXPR:
4094 err |= verify_gimple_2 (EH_FILTER_FAILURE (stmt));
4099 bool err2 = verify_gimple_stmt (stmt);
4101 debug_generic_expr (stmt);
4111 /* Verify the GIMPLE statements inside the statement list STMTS. */
4114 verify_gimple_1 (tree stmts)
4116 if (verify_gimple_2 (stmts))
4117 internal_error ("verify_gimple failed");
4120 /* Verify the GIMPLE statements inside the current function. */
4123 verify_gimple (void)
4125 verify_gimple_1 (BIND_EXPR_BODY (DECL_SAVED_TREE (cfun->decl)));
4128 /* Verify STMT, return true if STMT is not in GIMPLE form.
4129 TODO: Implement type checking. */
4132 verify_stmt (tree stmt, bool last_in_block)
4136 if (OMP_DIRECTIVE_P (stmt))
4138 /* OpenMP directives are validated by the FE and never operated
4139 on by the optimizers. Furthermore, OMP_FOR may contain
4140 non-gimple expressions when the main index variable has had
4141 its address taken. This does not affect the loop itself
4142 because the header of an OMP_FOR is merely used to determine
4143 how to setup the parallel iteration. */
4147 if (!is_gimple_stmt (stmt))
4149 error ("is not a valid GIMPLE statement");
4153 addr = walk_tree (&stmt, verify_expr, NULL, NULL);
4156 debug_generic_stmt (addr);
4160 /* If the statement is marked as part of an EH region, then it is
4161 expected that the statement could throw. Verify that when we
4162 have optimizations that simplify statements such that we prove
4163 that they cannot throw, that we update other data structures
4165 if (lookup_stmt_eh_region (stmt) >= 0)
4167 if (!tree_could_throw_p (stmt))
4169 error ("statement marked for throw, but doesn%'t");
4172 if (!last_in_block && tree_can_throw_internal (stmt))
4174 error ("statement marked for throw in middle of block");
4182 debug_generic_stmt (stmt);
4187 /* Return true when the T can be shared. */
4190 tree_node_can_be_shared (tree t)
4192 if (IS_TYPE_OR_DECL_P (t)
4193 || is_gimple_min_invariant (t)
4194 || TREE_CODE (t) == SSA_NAME
4195 || t == error_mark_node
4196 || TREE_CODE (t) == IDENTIFIER_NODE)
4199 if (TREE_CODE (t) == CASE_LABEL_EXPR)
4202 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4203 && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4204 || TREE_CODE (t) == COMPONENT_REF
4205 || TREE_CODE (t) == REALPART_EXPR
4206 || TREE_CODE (t) == IMAGPART_EXPR)
4207 t = TREE_OPERAND (t, 0);
4216 /* Called via walk_trees. Verify tree sharing. */
4219 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
4221 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4223 if (tree_node_can_be_shared (*tp))
4225 *walk_subtrees = false;
4229 if (pointer_set_insert (visited, *tp))
4236 /* Helper function for verify_gimple_tuples. */
4239 verify_gimple_tuples_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
4240 void *data ATTRIBUTE_UNUSED)
4242 switch (TREE_CODE (*tp))
4245 error ("unexpected non-tuple");
4255 /* Verify that there are no trees that should have been converted to
4256 gimple tuples. Return true if T contains a node that should have
4257 been converted to a gimple tuple, but hasn't. */
4260 verify_gimple_tuples (tree t)
4262 return walk_tree (&t, verify_gimple_tuples_1, NULL, NULL) != NULL;
4265 static bool eh_error_found;
4267 verify_eh_throw_stmt_node (void **slot, void *data)
4269 struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4270 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4272 if (!pointer_set_contains (visited, node->stmt))
4274 error ("Dead STMT in EH table");
4275 debug_generic_stmt (node->stmt);
4276 eh_error_found = true;
4281 /* Verify the GIMPLE statement chain. */
4287 block_stmt_iterator bsi;
4289 struct pointer_set_t *visited, *visited_stmts;
4292 timevar_push (TV_TREE_STMT_VERIFY);
4293 visited = pointer_set_create ();
4294 visited_stmts = pointer_set_create ();
4301 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4303 int phi_num_args = PHI_NUM_ARGS (phi);
4305 pointer_set_insert (visited_stmts, phi);
4306 if (bb_for_stmt (phi) != bb)
4308 error ("bb_for_stmt (phi) is set to a wrong basic block");
4312 for (i = 0; i < phi_num_args; i++)
4314 tree t = PHI_ARG_DEF (phi, i);
4319 error ("missing PHI def");
4320 debug_generic_stmt (phi);
4324 /* Addressable variables do have SSA_NAMEs but they
4325 are not considered gimple values. */
4326 else if (TREE_CODE (t) != SSA_NAME
4327 && TREE_CODE (t) != FUNCTION_DECL
4328 && !is_gimple_min_invariant (t))
4330 error ("PHI def is not a GIMPLE value");
4331 debug_generic_stmt (phi);
4332 debug_generic_stmt (t);
4336 addr = walk_tree (&t, verify_node_sharing, visited, NULL);
4339 error ("incorrect sharing of tree nodes");
4340 debug_generic_stmt (phi);
4341 debug_generic_stmt (addr);
4347 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
4349 tree stmt = bsi_stmt (bsi);
4351 pointer_set_insert (visited_stmts, stmt);
4352 err |= verify_gimple_tuples (stmt);
4354 if (bb_for_stmt (stmt) != bb)
4356 error ("bb_for_stmt (stmt) is set to a wrong basic block");
4361 err |= verify_stmt (stmt, bsi_end_p (bsi));
4362 addr = walk_tree (&stmt, verify_node_sharing, visited, NULL);
4365 error ("incorrect sharing of tree nodes");
4366 debug_generic_stmt (stmt);
4367 debug_generic_stmt (addr);
4372 eh_error_found = false;
4373 if (get_eh_throw_stmt_table (cfun))
4374 htab_traverse (get_eh_throw_stmt_table (cfun),
4375 verify_eh_throw_stmt_node,
4378 if (err | eh_error_found)
4379 internal_error ("verify_stmts failed");
4381 pointer_set_destroy (visited);
4382 pointer_set_destroy (visited_stmts);
4383 verify_histograms ();
4384 timevar_pop (TV_TREE_STMT_VERIFY);
4388 /* Verifies that the flow information is OK. */
4391 tree_verify_flow_info (void)
4395 block_stmt_iterator bsi;
4400 if (ENTRY_BLOCK_PTR->il.tree)
4402 error ("ENTRY_BLOCK has IL associated with it");
4406 if (EXIT_BLOCK_PTR->il.tree)
4408 error ("EXIT_BLOCK has IL associated with it");
4412 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4413 if (e->flags & EDGE_FALLTHRU)
4415 error ("fallthru to exit from bb %d", e->src->index);
4421 bool found_ctrl_stmt = false;
4425 /* Skip labels on the start of basic block. */
4426 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4428 tree prev_stmt = stmt;
4430 stmt = bsi_stmt (bsi);
4432 if (TREE_CODE (stmt) != LABEL_EXPR)
4435 if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
4437 error ("nonlocal label ");
4438 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4439 fprintf (stderr, " is not first in a sequence of labels in bb %d",
4444 if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
4447 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4448 fprintf (stderr, " to block does not match in bb %d",
4453 if (decl_function_context (LABEL_EXPR_LABEL (stmt))
4454 != current_function_decl)
4457 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4458 fprintf (stderr, " has incorrect context in bb %d",
4464 /* Verify that body of basic block BB is free of control flow. */
4465 for (; !bsi_end_p (bsi); bsi_next (&bsi))
4467 tree stmt = bsi_stmt (bsi);
4469 if (found_ctrl_stmt)
4471 error ("control flow in the middle of basic block %d",
4476 if (stmt_ends_bb_p (stmt))
4477 found_ctrl_stmt = true;
4479 if (TREE_CODE (stmt) == LABEL_EXPR)
4482 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4483 fprintf (stderr, " in the middle of basic block %d", bb->index);
4488 bsi = bsi_last (bb);
4489 if (bsi_end_p (bsi))
4492 stmt = bsi_stmt (bsi);
4494 err |= verify_eh_edges (stmt);
4496 if (is_ctrl_stmt (stmt))
4498 FOR_EACH_EDGE (e, ei, bb->succs)
4499 if (e->flags & EDGE_FALLTHRU)
4501 error ("fallthru edge after a control statement in bb %d",
4507 if (TREE_CODE (stmt) != COND_EXPR)
4509 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4510 after anything else but if statement. */
4511 FOR_EACH_EDGE (e, ei, bb->succs)
4512 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4514 error ("true/false edge after a non-COND_EXPR in bb %d",
4520 switch (TREE_CODE (stmt))
4527 if (COND_EXPR_THEN (stmt) != NULL_TREE
4528 || COND_EXPR_ELSE (stmt) != NULL_TREE)
4530 error ("COND_EXPR with code in branches at the end of bb %d",
4535 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4537 if (!true_edge || !false_edge
4538 || !(true_edge->flags & EDGE_TRUE_VALUE)
4539 || !(false_edge->flags & EDGE_FALSE_VALUE)
4540 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4541 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4542 || EDGE_COUNT (bb->succs) >= 3)
4544 error ("wrong outgoing edge flags at end of bb %d",
4552 if (simple_goto_p (stmt))
4554 error ("explicit goto at end of bb %d", bb->index);
4559 /* FIXME. We should double check that the labels in the
4560 destination blocks have their address taken. */
4561 FOR_EACH_EDGE (e, ei, bb->succs)
4562 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4563 | EDGE_FALSE_VALUE))
4564 || !(e->flags & EDGE_ABNORMAL))
4566 error ("wrong outgoing edge flags at end of bb %d",
4574 if (!single_succ_p (bb)
4575 || (single_succ_edge (bb)->flags
4576 & (EDGE_FALLTHRU | EDGE_ABNORMAL
4577 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4579 error ("wrong outgoing edge flags at end of bb %d", bb->index);
4582 if (single_succ (bb) != EXIT_BLOCK_PTR)
4584 error ("return edge does not point to exit in bb %d",
4597 vec = SWITCH_LABELS (stmt);
4598 n = TREE_VEC_LENGTH (vec);
4600 /* Mark all the destination basic blocks. */
4601 for (i = 0; i < n; ++i)
4603 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4604 basic_block label_bb = label_to_block (lab);
4606 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4607 label_bb->aux = (void *)1;
4610 /* Verify that the case labels are sorted. */
4611 prev = TREE_VEC_ELT (vec, 0);
4612 for (i = 1; i < n; ++i)
4614 tree c = TREE_VEC_ELT (vec, i);
4619 error ("found default case not at end of case vector");
4624 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4626 error ("case labels not sorted: ");
4627 print_generic_expr (stderr, prev, 0);
4628 fprintf (stderr," is greater than ");
4629 print_generic_expr (stderr, c, 0);
4630 fprintf (stderr," but comes before it.\n");
4635 /* VRP will remove the default case if it can prove it will
4636 never be executed. So do not verify there always exists
4637 a default case here. */
4639 FOR_EACH_EDGE (e, ei, bb->succs)
4643 error ("extra outgoing edge %d->%d",
4644 bb->index, e->dest->index);
4647 e->dest->aux = (void *)2;
4648 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4649 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4651 error ("wrong outgoing edge flags at end of bb %d",
4657 /* Check that we have all of them. */
4658 for (i = 0; i < n; ++i)
4660 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4661 basic_block label_bb = label_to_block (lab);
4663 if (label_bb->aux != (void *)2)
4665 error ("missing edge %i->%i",
4666 bb->index, label_bb->index);
4671 FOR_EACH_EDGE (e, ei, bb->succs)
4672 e->dest->aux = (void *)0;
4679 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4680 verify_dominators (CDI_DOMINATORS);
4686 /* Updates phi nodes after creating a forwarder block joined
4687 by edge FALLTHRU. */
4690 tree_make_forwarder_block (edge fallthru)
4694 basic_block dummy, bb;
4695 tree phi, new_phi, var;
4697 dummy = fallthru->src;
4698 bb = fallthru->dest;
4700 if (single_pred_p (bb))
4703 /* If we redirected a branch we must create new PHI nodes at the
4705 for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
4707 var = PHI_RESULT (phi);
4708 new_phi = create_phi_node (var, bb);
4709 SSA_NAME_DEF_STMT (var) = new_phi;
4710 SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4711 add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
4714 /* Ensure that the PHI node chain is in the same order. */
4715 set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
4717 /* Add the arguments we have stored on edges. */
4718 FOR_EACH_EDGE (e, ei, bb->preds)
4723 flush_pending_stmts (e);
4728 /* Return a non-special label in the head of basic block BLOCK.
4729 Create one if it doesn't exist. */
4732 tree_block_label (basic_block bb)
4734 block_stmt_iterator i, s = bsi_start (bb);
4738 for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4740 stmt = bsi_stmt (i);
4741 if (TREE_CODE (stmt) != LABEL_EXPR)
4743 label = LABEL_EXPR_LABEL (stmt);
4744 if (!DECL_NONLOCAL (label))
4747 bsi_move_before (&i, &s);
4752 label = create_artificial_label ();
4753 stmt = build1 (LABEL_EXPR, void_type_node, label);
4754 bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4759 /* Attempt to perform edge redirection by replacing a possibly complex
4760 jump instruction by a goto or by removing the jump completely.
4761 This can apply only if all edges now point to the same block. The
4762 parameters and return values are equivalent to
4763 redirect_edge_and_branch. */
4766 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4768 basic_block src = e->src;
4769 block_stmt_iterator b;
4772 /* We can replace or remove a complex jump only when we have exactly
4774 if (EDGE_COUNT (src->succs) != 2
4775 /* Verify that all targets will be TARGET. Specifically, the
4776 edge that is not E must also go to TARGET. */
4777 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4783 stmt = bsi_stmt (b);
4785 if (TREE_CODE (stmt) == COND_EXPR
4786 || TREE_CODE (stmt) == SWITCH_EXPR)
4788 bsi_remove (&b, true);
4789 e = ssa_redirect_edge (e, target);
4790 e->flags = EDGE_FALLTHRU;
4798 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
4799 edge representing the redirected branch. */
4802 tree_redirect_edge_and_branch (edge e, basic_block dest)
4804 basic_block bb = e->src;
4805 block_stmt_iterator bsi;
4809 if (e->flags & EDGE_ABNORMAL)
4812 if (e->src != ENTRY_BLOCK_PTR
4813 && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4816 if (e->dest == dest)
4819 bsi = bsi_last (bb);
4820 stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4822 switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4825 /* For COND_EXPR, we only need to redirect the edge. */
4829 /* No non-abnormal edges should lead from a non-simple goto, and
4830 simple ones should be represented implicitly. */
4835 tree cases = get_cases_for_edge (e, stmt);
4836 tree label = tree_block_label (dest);
4838 /* If we have a list of cases associated with E, then use it
4839 as it's a lot faster than walking the entire case vector. */
4842 edge e2 = find_edge (e->src, dest);
4849 CASE_LABEL (cases) = label;
4850 cases = TREE_CHAIN (cases);
4853 /* If there was already an edge in the CFG, then we need
4854 to move all the cases associated with E to E2. */
4857 tree cases2 = get_cases_for_edge (e2, stmt);
4859 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4860 TREE_CHAIN (cases2) = first;
4865 tree vec = SWITCH_LABELS (stmt);
4866 size_t i, n = TREE_VEC_LENGTH (vec);
4868 for (i = 0; i < n; i++)
4870 tree elt = TREE_VEC_ELT (vec, i);
4872 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4873 CASE_LABEL (elt) = label;
4881 bsi_remove (&bsi, true);
4882 e->flags |= EDGE_FALLTHRU;
4887 case OMP_SECTIONS_SWITCH:
4889 /* The edges from OMP constructs can be simply redirected. */
4893 /* Otherwise it must be a fallthru edge, and we don't need to
4894 do anything besides redirecting it. */
4895 gcc_assert (e->flags & EDGE_FALLTHRU);
4899 /* Update/insert PHI nodes as necessary. */
4901 /* Now update the edges in the CFG. */
4902 e = ssa_redirect_edge (e, dest);
4907 /* Returns true if it is possible to remove edge E by redirecting
4908 it to the destination of the other edge from E->src. */
4911 tree_can_remove_branch_p (const_edge e)
4913 if (e->flags & EDGE_ABNORMAL)
4919 /* Simple wrapper, as we can always redirect fallthru edges. */
4922 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4924 e = tree_redirect_edge_and_branch (e, dest);
4931 /* Splits basic block BB after statement STMT (but at least after the
4932 labels). If STMT is NULL, BB is split just after the labels. */
4935 tree_split_block (basic_block bb, void *stmt)
4937 block_stmt_iterator bsi;
4938 tree_stmt_iterator tsi_tgt;
4944 new_bb = create_empty_bb (bb);
4946 /* Redirect the outgoing edges. */
4947 new_bb->succs = bb->succs;
4949 FOR_EACH_EDGE (e, ei, new_bb->succs)
4952 if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4955 /* Move everything from BSI to the new basic block. */
4956 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4958 act = bsi_stmt (bsi);
4959 if (TREE_CODE (act) == LABEL_EXPR)
4972 if (bsi_end_p (bsi))
4975 /* Split the statement list - avoid re-creating new containers as this
4976 brings ugly quadratic memory consumption in the inliner.
4977 (We are still quadratic since we need to update stmt BB pointers,
4979 list = tsi_split_statement_list_before (&bsi.tsi);
4980 set_bb_stmt_list (new_bb, list);
4981 for (tsi_tgt = tsi_start (list);
4982 !tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
4983 change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
4989 /* Moves basic block BB after block AFTER. */
4992 tree_move_block_after (basic_block bb, basic_block after)
4994 if (bb->prev_bb == after)
4998 link_block (bb, after);
5004 /* Return true if basic_block can be duplicated. */
5007 tree_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5013 /* Create a duplicate of the basic block BB. NOTE: This does not
5014 preserve SSA form. */
5017 tree_duplicate_bb (basic_block bb)
5020 block_stmt_iterator bsi, bsi_tgt;
5023 new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5025 /* Copy the PHI nodes. We ignore PHI node arguments here because
5026 the incoming edges have not been setup yet. */
5027 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5029 tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
5030 create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
5033 /* Keep the chain of PHI nodes in the same order so that they can be
5034 updated by ssa_redirect_edge. */
5035 set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
5037 bsi_tgt = bsi_start (new_bb);
5038 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5040 def_operand_p def_p;
5041 ssa_op_iter op_iter;
5045 stmt = bsi_stmt (bsi);
5046 if (TREE_CODE (stmt) == LABEL_EXPR)
5049 /* Create a new copy of STMT and duplicate STMT's virtual
5051 copy = unshare_expr (stmt);
5052 bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
5053 copy_virtual_operands (copy, stmt);
5054 region = lookup_stmt_eh_region (stmt);
5056 add_stmt_to_eh_region (copy, region);
5057 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5059 /* Create new names for all the definitions created by COPY and
5060 add replacement mappings for each new name. */
5061 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5062 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5068 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5071 add_phi_args_after_copy_edge (edge e_copy)
5073 basic_block bb, bb_copy = e_copy->src, dest;
5076 tree phi, phi_copy, phi_next, def;
5078 if (!phi_nodes (e_copy->dest))
5081 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5083 if (e_copy->dest->flags & BB_DUPLICATED)
5084 dest = get_bb_original (e_copy->dest);
5086 dest = e_copy->dest;
5088 e = find_edge (bb, dest);
5091 /* During loop unrolling the target of the latch edge is copied.
5092 In this case we are not looking for edge to dest, but to
5093 duplicated block whose original was dest. */
5094 FOR_EACH_EDGE (e, ei, bb->succs)
5096 if ((e->dest->flags & BB_DUPLICATED)
5097 && get_bb_original (e->dest) == dest)
5101 gcc_assert (e != NULL);
5104 for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
5106 phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
5108 phi_next = PHI_CHAIN (phi);
5109 def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5110 add_phi_arg (phi_copy, def, e_copy);
5115 /* Basic block BB_COPY was created by code duplication. Add phi node
5116 arguments for edges going out of BB_COPY. The blocks that were
5117 duplicated have BB_DUPLICATED set. */
5120 add_phi_args_after_copy_bb (basic_block bb_copy)
5125 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5127 add_phi_args_after_copy_edge (e_copy);
5131 /* Blocks in REGION_COPY array of length N_REGION were created by
5132 duplication of basic blocks. Add phi node arguments for edges
5133 going from these blocks. If E_COPY is not NULL, also add
5134 phi node arguments for its destination.*/
5137 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5142 for (i = 0; i < n_region; i++)
5143 region_copy[i]->flags |= BB_DUPLICATED;
5145 for (i = 0; i < n_region; i++)
5146 add_phi_args_after_copy_bb (region_copy[i]);
5148 add_phi_args_after_copy_edge (e_copy);
5150 for (i = 0; i < n_region; i++)
5151 region_copy[i]->flags &= ~BB_DUPLICATED;
5154 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5155 important exit edge EXIT. By important we mean that no SSA name defined
5156 inside region is live over the other exit edges of the region. All entry
5157 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5158 to the duplicate of the region. SSA form, dominance and loop information
5159 is updated. The new basic blocks are stored to REGION_COPY in the same
5160 order as they had in REGION, provided that REGION_COPY is not NULL.
5161 The function returns false if it is unable to copy the region,
5165 tree_duplicate_sese_region (edge entry, edge exit,
5166 basic_block *region, unsigned n_region,
5167 basic_block *region_copy)
5170 bool free_region_copy = false, copying_header = false;
5171 struct loop *loop = entry->dest->loop_father;
5173 VEC (basic_block, heap) *doms;
5175 int total_freq = 0, entry_freq = 0;
5176 gcov_type total_count = 0, entry_count = 0;
5178 if (!can_copy_bbs_p (region, n_region))
5181 /* Some sanity checking. Note that we do not check for all possible
5182 missuses of the functions. I.e. if you ask to copy something weird,
5183 it will work, but the state of structures probably will not be
5185 for (i = 0; i < n_region; i++)
5187 /* We do not handle subloops, i.e. all the blocks must belong to the
5189 if (region[i]->loop_father != loop)
5192 if (region[i] != entry->dest
5193 && region[i] == loop->header)
5197 set_loop_copy (loop, loop);
5199 /* In case the function is used for loop header copying (which is the primary
5200 use), ensure that EXIT and its copy will be new latch and entry edges. */
5201 if (loop->header == entry->dest)
5203 copying_header = true;
5204 set_loop_copy (loop, loop_outer (loop));
5206 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5209 for (i = 0; i < n_region; i++)
5210 if (region[i] != exit->src
5211 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5217 region_copy = XNEWVEC (basic_block, n_region);
5218 free_region_copy = true;
5221 gcc_assert (!need_ssa_update_p ());
5223 /* Record blocks outside the region that are dominated by something
5226 initialize_original_copy_tables ();
5228 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5230 if (entry->dest->count)
5232 total_count = entry->dest->count;
5233 entry_count = entry->count;
5234 /* Fix up corner cases, to avoid division by zero or creation of negative
5236 if (entry_count > total_count)
5237 entry_count = total_count;
5241 total_freq = entry->dest->frequency;
5242 entry_freq = EDGE_FREQUENCY (entry);
5243 /* Fix up corner cases, to avoid division by zero or creation of negative
5245 if (total_freq == 0)
5247 else if (entry_freq > total_freq)
5248 entry_freq = total_freq;
5251 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5252 split_edge_bb_loc (entry));
5255 scale_bbs_frequencies_gcov_type (region, n_region,
5256 total_count - entry_count,
5258 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5263 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5265 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5270 loop->header = exit->dest;
5271 loop->latch = exit->src;
5274 /* Redirect the entry and add the phi node arguments. */
5275 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5276 gcc_assert (redirected != NULL);
5277 flush_pending_stmts (entry);
5279 /* Concerning updating of dominators: We must recount dominators
5280 for entry block and its copy. Anything that is outside of the
5281 region, but was dominated by something inside needs recounting as
5283 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5284 VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5285 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5286 VEC_free (basic_block, heap, doms);
5288 /* Add the other PHI node arguments. */
5289 add_phi_args_after_copy (region_copy, n_region, NULL);
5291 /* Update the SSA web. */
5292 update_ssa (TODO_update_ssa);
5294 if (free_region_copy)
5297 free_original_copy_tables ();
5301 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
5302 are stored to REGION_COPY in the same order in that they appear
5303 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
5304 the region, EXIT an exit from it. The condition guarding EXIT
5305 is moved to ENTRY. Returns true if duplication succeeds, false
5331 tree_duplicate_sese_tail (edge entry, edge exit,
5332 basic_block *region, unsigned n_region,
5333 basic_block *region_copy)
5336 bool free_region_copy = false;
5337 struct loop *loop = exit->dest->loop_father;
5338 struct loop *orig_loop = entry->dest->loop_father;
5339 basic_block switch_bb, entry_bb, nentry_bb;
5340 VEC (basic_block, heap) *doms;
5341 int total_freq = 0, exit_freq = 0;
5342 gcov_type total_count = 0, exit_count = 0;
5343 edge exits[2], nexits[2], e;
5344 block_stmt_iterator bsi;
5348 gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5350 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5352 if (!can_copy_bbs_p (region, n_region))
5355 /* Some sanity checking. Note that we do not check for all possible
5356 missuses of the functions. I.e. if you ask to copy something weird
5357 (e.g., in the example, if there is a jump from inside to the middle
5358 of some_code, or come_code defines some of the values used in cond)
5359 it will work, but the resulting code will not be correct. */
5360 for (i = 0; i < n_region; i++)
5362 /* We do not handle subloops, i.e. all the blocks must belong to the
5364 if (region[i]->loop_father != orig_loop)
5367 if (region[i] == orig_loop->latch)
5371 initialize_original_copy_tables ();
5372 set_loop_copy (orig_loop, loop);
5376 region_copy = XNEWVEC (basic_block, n_region);
5377 free_region_copy = true;
5380 gcc_assert (!need_ssa_update_p ());
5382 /* Record blocks outside the region that are dominated by something
5384 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5386 if (exit->src->count)
5388 total_count = exit->src->count;
5389 exit_count = exit->count;
5390 /* Fix up corner cases, to avoid division by zero or creation of negative
5392 if (exit_count > total_count)
5393 exit_count = total_count;
5397 total_freq = exit->src->frequency;
5398 exit_freq = EDGE_FREQUENCY (exit);
5399 /* Fix up corner cases, to avoid division by zero or creation of negative
5401 if (total_freq == 0)
5403 if (exit_freq > total_freq)
5404 exit_freq = total_freq;
5407 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5408 split_edge_bb_loc (exit));
5411 scale_bbs_frequencies_gcov_type (region, n_region,
5412 total_count - exit_count,
5414 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5419 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5421 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5424 /* Create the switch block, and put the exit condition to it. */
5425 entry_bb = entry->dest;
5426 nentry_bb = get_bb_copy (entry_bb);
5427 if (!last_stmt (entry->src)
5428 || !stmt_ends_bb_p (last_stmt (entry->src)))
5429 switch_bb = entry->src;
5431 switch_bb = split_edge (entry);
5432 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5434 bsi = bsi_last (switch_bb);
5435 cond = last_stmt (exit->src);
5436 gcc_assert (TREE_CODE (cond) == COND_EXPR);
5437 bsi_insert_after (&bsi, unshare_expr (cond), BSI_NEW_STMT);
5439 sorig = single_succ_edge (switch_bb);
5440 sorig->flags = exits[1]->flags;
5441 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5443 /* Register the new edge from SWITCH_BB in loop exit lists. */
5444 rescan_loop_exit (snew, true, false);
5446 /* Add the PHI node arguments. */
5447 add_phi_args_after_copy (region_copy, n_region, snew);
5449 /* Get rid of now superfluous conditions and associated edges (and phi node
5451 e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5452 PENDING_STMT (e) = NULL_TREE;
5453 e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5454 PENDING_STMT (e) = NULL_TREE;
5456 /* Anything that is outside of the region, but was dominated by something
5457 inside needs to update dominance info. */
5458 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5459 VEC_free (basic_block, heap, doms);
5461 /* Update the SSA web. */
5462 update_ssa (TODO_update_ssa);
5464 if (free_region_copy)
5467 free_original_copy_tables ();
5472 DEF_VEC_P(basic_block);
5473 DEF_VEC_ALLOC_P(basic_block,heap);
5476 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
5477 adding blocks when the dominator traversal reaches EXIT. This
5478 function silently assumes that ENTRY strictly dominates EXIT. */
5481 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5482 VEC(basic_block,heap) **bbs_p)
5486 for (son = first_dom_son (CDI_DOMINATORS, entry);
5488 son = next_dom_son (CDI_DOMINATORS, son))
5490 VEC_safe_push (basic_block, heap, *bbs_p, son);
5492 gather_blocks_in_sese_region (son, exit, bbs_p);
5496 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5497 The duplicates are recorded in VARS_MAP. */
5500 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5503 tree t = *tp, new_t;
5504 struct function *f = DECL_STRUCT_FUNCTION (to_context);
5507 if (DECL_CONTEXT (t) == to_context)
5510 loc = pointer_map_contains (vars_map, t);
5514 loc = pointer_map_insert (vars_map, t);
5518 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5519 f->unexpanded_var_list
5520 = tree_cons (NULL_TREE, new_t, f->unexpanded_var_list);
5524 gcc_assert (TREE_CODE (t) == CONST_DECL);
5525 new_t = copy_node (t);
5527 DECL_CONTEXT (new_t) = to_context;
5537 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5538 VARS_MAP maps old ssa names and var_decls to the new ones. */
5541 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5545 tree new_name, decl = SSA_NAME_VAR (name);
5547 gcc_assert (is_gimple_reg (name));
5549 loc = pointer_map_contains (vars_map, name);
5553 replace_by_duplicate_decl (&decl, vars_map, to_context);
5555 push_cfun (DECL_STRUCT_FUNCTION (to_context));
5556 if (gimple_in_ssa_p (cfun))
5557 add_referenced_var (decl);
5559 new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5560 if (SSA_NAME_IS_DEFAULT_DEF (name))
5561 set_default_def (decl, new_name);
5564 loc = pointer_map_insert (vars_map, name);
5578 struct pointer_map_t *vars_map;
5579 htab_t new_label_map;
5583 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
5584 contained in *TP and change the DECL_CONTEXT of every local
5585 variable referenced in *TP. */
5588 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
5590 struct move_stmt_d *p = (struct move_stmt_d *) data;
5594 && (EXPR_P (t) || GIMPLE_STMT_P (t)))
5595 TREE_BLOCK (t) = p->block;
5597 if (OMP_DIRECTIVE_P (t)
5598 && TREE_CODE (t) != OMP_RETURN
5599 && TREE_CODE (t) != OMP_CONTINUE)
5601 /* Do not remap variables inside OMP directives. Variables
5602 referenced in clauses and directive header belong to the
5603 parent function and should not be moved into the child
5605 bool save_remap_decls_p = p->remap_decls_p;
5606 p->remap_decls_p = false;
5609 walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
5611 p->remap_decls_p = save_remap_decls_p;
5613 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5615 if (TREE_CODE (t) == SSA_NAME)
5616 *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5617 else if (TREE_CODE (t) == LABEL_DECL)
5619 if (p->new_label_map)
5621 struct tree_map in, *out;
5623 out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5628 DECL_CONTEXT (t) = p->to_context;
5630 else if (p->remap_decls_p)
5632 /* Replace T with its duplicate. T should no longer appear in the
5633 parent function, so this looks wasteful; however, it may appear
5634 in referenced_vars, and more importantly, as virtual operands of
5635 statements, and in alias lists of other variables. It would be
5636 quite difficult to expunge it from all those places. ??? It might
5637 suffice to do this for addressable variables. */
5638 if ((TREE_CODE (t) == VAR_DECL
5639 && !is_global_var (t))
5640 || TREE_CODE (t) == CONST_DECL)
5641 replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5644 && gimple_in_ssa_p (cfun))
5646 push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5647 add_referenced_var (*tp);
5653 else if (TYPE_P (t))
5659 /* Marks virtual operands of all statements in basic blocks BBS for
5663 mark_virtual_ops_in_bb (basic_block bb)
5666 block_stmt_iterator bsi;
5668 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5669 mark_virtual_ops_for_renaming (phi);
5671 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5672 mark_virtual_ops_for_renaming (bsi_stmt (bsi));
5675 /* Marks virtual operands of all statements in basic blocks BBS for
5679 mark_virtual_ops_in_region (VEC (basic_block,heap) *bbs)
5684 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5685 mark_virtual_ops_in_bb (bb);
5688 /* Move basic block BB from function CFUN to function DEST_FN. The
5689 block is moved out of the original linked list and placed after
5690 block AFTER in the new list. Also, the block is removed from the
5691 original array of blocks and placed in DEST_FN's array of blocks.
5692 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5693 updated to reflect the moved edges.
5695 The local variables are remapped to new instances, VARS_MAP is used
5696 to record the mapping. */
5699 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5700 basic_block after, bool update_edge_count_p,
5701 struct pointer_map_t *vars_map, htab_t new_label_map,
5704 struct control_flow_graph *cfg;
5707 block_stmt_iterator si;
5708 struct move_stmt_d d;
5709 unsigned old_len, new_len;
5712 /* Remove BB from dominance structures. */
5713 delete_from_dominance_info (CDI_DOMINATORS, bb);
5715 remove_bb_from_loops (bb);
5717 /* Link BB to the new linked list. */
5718 move_block_after (bb, after);
5720 /* Update the edge count in the corresponding flowgraphs. */
5721 if (update_edge_count_p)
5722 FOR_EACH_EDGE (e, ei, bb->succs)
5724 cfun->cfg->x_n_edges--;
5725 dest_cfun->cfg->x_n_edges++;
5728 /* Remove BB from the original basic block array. */
5729 VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5730 cfun->cfg->x_n_basic_blocks--;
5732 /* Grow DEST_CFUN's basic block array if needed. */
5733 cfg = dest_cfun->cfg;
5734 cfg->x_n_basic_blocks++;
5735 if (bb->index >= cfg->x_last_basic_block)
5736 cfg->x_last_basic_block = bb->index + 1;
5738 old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5739 if ((unsigned) cfg->x_last_basic_block >= old_len)
5741 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5742 VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5746 VEC_replace (basic_block, cfg->x_basic_block_info,
5749 /* Remap the variables in phi nodes. */
5750 for (phi = phi_nodes (bb); phi; phi = next_phi)
5753 tree op = PHI_RESULT (phi);
5756 next_phi = PHI_CHAIN (phi);
5757 if (!is_gimple_reg (op))
5759 /* Remove the phi nodes for virtual operands (alias analysis will be
5760 run for the new function, anyway). */
5761 remove_phi_node (phi, NULL, true);
5765 SET_PHI_RESULT (phi, replace_ssa_name (op, vars_map, dest_cfun->decl));
5766 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5768 op = USE_FROM_PTR (use);
5769 if (TREE_CODE (op) == SSA_NAME)
5770 SET_USE (use, replace_ssa_name (op, vars_map, dest_cfun->decl));
5774 /* The statements in BB need to be associated with a new TREE_BLOCK.
5775 Labels need to be associated with a new label-to-block map. */
5776 memset (&d, 0, sizeof (d));
5777 d.vars_map = vars_map;
5778 d.from_context = cfun->decl;
5779 d.to_context = dest_cfun->decl;
5780 d.new_label_map = new_label_map;
5782 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5784 tree stmt = bsi_stmt (si);
5787 d.remap_decls_p = true;
5788 if (TREE_BLOCK (stmt))
5789 d.block = DECL_INITIAL (dest_cfun->decl);
5791 walk_tree (&stmt, move_stmt_r, &d, NULL);
5793 if (TREE_CODE (stmt) == LABEL_EXPR)
5795 tree label = LABEL_EXPR_LABEL (stmt);
5796 int uid = LABEL_DECL_UID (label);
5798 gcc_assert (uid > -1);
5800 old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5801 if (old_len <= (unsigned) uid)
5803 new_len = 3 * uid / 2;
5804 VEC_safe_grow_cleared (basic_block, gc,
5805 cfg->x_label_to_block_map, new_len);
5808 VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5809 VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5811 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5813 if (uid >= dest_cfun->last_label_uid)
5814 dest_cfun->last_label_uid = uid + 1;
5816 else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
5817 TREE_OPERAND (stmt, 0) =
5818 build_int_cst (NULL_TREE,
5819 TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
5822 region = lookup_stmt_eh_region (stmt);
5825 add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
5826 remove_stmt_from_eh_region (stmt);
5827 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5828 gimple_remove_stmt_histograms (cfun, stmt);
5831 /* We cannot leave any operands allocated from the operand caches of
5832 the current function. */
5833 free_stmt_operands (stmt);
5834 push_cfun (dest_cfun);
5840 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5841 the outermost EH region. Use REGION as the incoming base EH region. */
5844 find_outermost_region_in_block (struct function *src_cfun,
5845 basic_block bb, int region)
5847 block_stmt_iterator si;
5849 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5851 tree stmt = bsi_stmt (si);
5854 if (TREE_CODE (stmt) == RESX_EXPR)
5855 stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
5857 stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
5858 if (stmt_region > 0)
5861 region = stmt_region;
5862 else if (stmt_region != region)
5864 region = eh_region_outermost (src_cfun, stmt_region, region);
5865 gcc_assert (region != -1);
5874 new_label_mapper (tree decl, void *data)
5876 htab_t hash = (htab_t) data;
5880 gcc_assert (TREE_CODE (decl) == LABEL_DECL);
5882 m = xmalloc (sizeof (struct tree_map));
5883 m->hash = DECL_UID (decl);
5884 m->base.from = decl;
5885 m->to = create_artificial_label ();
5886 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
5887 if (LABEL_DECL_UID (m->to) >= cfun->last_label_uid)
5888 cfun->last_label_uid = LABEL_DECL_UID (m->to) + 1;
5890 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
5891 gcc_assert (*slot == NULL);
5898 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5899 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
5900 single basic block in the original CFG and the new basic block is
5901 returned. DEST_CFUN must not have a CFG yet.
5903 Note that the region need not be a pure SESE region. Blocks inside
5904 the region may contain calls to abort/exit. The only restriction
5905 is that ENTRY_BB should be the only entry point and it must
5908 All local variables referenced in the region are assumed to be in
5909 the corresponding BLOCK_VARS and unexpanded variable lists
5910 associated with DEST_CFUN. */
5913 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
5914 basic_block exit_bb)
5916 VEC(basic_block,heap) *bbs, *dom_bbs;
5917 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
5918 basic_block after, bb, *entry_pred, *exit_succ, abb;
5919 struct function *saved_cfun = cfun;
5920 int *entry_flag, *exit_flag, eh_offset;
5921 unsigned *entry_prob, *exit_prob;
5922 unsigned i, num_entry_edges, num_exit_edges;
5925 htab_t new_label_map;
5926 struct pointer_map_t *vars_map;
5927 struct loop *loop = entry_bb->loop_father;
5929 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5931 gcc_assert (entry_bb != exit_bb
5933 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
5935 /* Collect all the blocks in the region. Manually add ENTRY_BB
5936 because it won't be added by dfs_enumerate_from. */
5938 VEC_safe_push (basic_block, heap, bbs, entry_bb);
5939 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5941 /* The blocks that used to be dominated by something in BBS will now be
5942 dominated by the new block. */
5943 dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
5944 VEC_address (basic_block, bbs),
5945 VEC_length (basic_block, bbs));
5947 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
5948 the predecessor edges to ENTRY_BB and the successor edges to
5949 EXIT_BB so that we can re-attach them to the new basic block that
5950 will replace the region. */
5951 num_entry_edges = EDGE_COUNT (entry_bb->preds);
5952 entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
5953 entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
5954 entry_prob = XNEWVEC (unsigned, num_entry_edges);
5956 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
5958 entry_prob[i] = e->probability;
5959 entry_flag[i] = e->flags;
5960 entry_pred[i++] = e->src;
5966 num_exit_edges = EDGE_COUNT (exit_bb->succs);
5967 exit_succ = (basic_block *) xcalloc (num_exit_edges,
5968 sizeof (basic_block));
5969 exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
5970 exit_prob = XNEWVEC (unsigned, num_exit_edges);
5972 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
5974 exit_prob[i] = e->probability;
5975 exit_flag[i] = e->flags;
5976 exit_succ[i++] = e->dest;
5988 /* Switch context to the child function to initialize DEST_FN's CFG. */
5989 gcc_assert (dest_cfun->cfg == NULL);
5990 push_cfun (dest_cfun);
5992 init_empty_tree_cfg ();
5994 /* Initialize EH information for the new function. */
5996 new_label_map = NULL;
6001 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6002 region = find_outermost_region_in_block (saved_cfun, bb, region);
6004 init_eh_for_function ();
6007 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6008 eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
6009 new_label_map, region, 0);
6015 /* The ssa form for virtual operands in the source function will have to
6016 be repaired. We do not care for the real operands -- the sese region
6017 must be closed with respect to those. */
6018 mark_virtual_ops_in_region (bbs);
6020 /* Move blocks from BBS into DEST_CFUN. */
6021 gcc_assert (VEC_length (basic_block, bbs) >= 2);
6022 after = dest_cfun->cfg->x_entry_block_ptr;
6023 vars_map = pointer_map_create ();
6024 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6026 /* No need to update edge counts on the last block. It has
6027 already been updated earlier when we detached the region from
6028 the original CFG. */
6029 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_map,
6030 new_label_map, eh_offset);
6035 htab_delete (new_label_map);
6036 pointer_map_destroy (vars_map);
6038 /* Rewire the entry and exit blocks. The successor to the entry
6039 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6040 the child function. Similarly, the predecessor of DEST_FN's
6041 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
6042 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6043 various CFG manipulation function get to the right CFG.
6045 FIXME, this is silly. The CFG ought to become a parameter to
6047 push_cfun (dest_cfun);
6048 make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6050 make_edge (exit_bb, EXIT_BLOCK_PTR, 0);
6053 /* Back in the original function, the SESE region has disappeared,
6054 create a new basic block in its place. */
6055 bb = create_empty_bb (entry_pred[0]);
6057 add_bb_to_loop (bb, loop);
6058 for (i = 0; i < num_entry_edges; i++)
6060 e = make_edge (entry_pred[i], bb, entry_flag[i]);
6061 e->probability = entry_prob[i];
6064 for (i = 0; i < num_exit_edges; i++)
6066 e = make_edge (bb, exit_succ[i], exit_flag[i]);
6067 e->probability = exit_prob[i];
6070 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6071 for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
6072 set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6073 VEC_free (basic_block, heap, dom_bbs);
6084 VEC_free (basic_block, heap, bbs);
6090 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
6093 dump_function_to_file (tree fn, FILE *file, int flags)
6095 tree arg, vars, var;
6096 struct function *dsf;
6097 bool ignore_topmost_bind = false, any_var = false;
6101 fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6103 arg = DECL_ARGUMENTS (fn);
6106 print_generic_expr (file, arg, dump_flags);
6107 if (TREE_CHAIN (arg))
6108 fprintf (file, ", ");
6109 arg = TREE_CHAIN (arg);
6111 fprintf (file, ")\n");
6113 dsf = DECL_STRUCT_FUNCTION (fn);
6114 if (dsf && (flags & TDF_DETAILS))
6115 dump_eh_tree (file, dsf);
6117 if (flags & TDF_RAW)
6119 dump_node (fn, TDF_SLIM | flags, file);
6123 /* Switch CFUN to point to FN. */
6124 push_cfun (DECL_STRUCT_FUNCTION (fn));
6126 /* When GIMPLE is lowered, the variables are no longer available in
6127 BIND_EXPRs, so display them separately. */
6128 if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
6130 ignore_topmost_bind = true;
6132 fprintf (file, "{\n");
6133 for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
6135 var = TREE_VALUE (vars);
6137 print_generic_decl (file, var, flags);
6138 fprintf (file, "\n");
6144 if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6146 /* Make a CFG based dump. */
6147 check_bb_profile (ENTRY_BLOCK_PTR, file);
6148 if (!ignore_topmost_bind)
6149 fprintf (file, "{\n");
6151 if (any_var && n_basic_blocks)
6152 fprintf (file, "\n");
6155 dump_generic_bb (file, bb, 2, flags);
6157 fprintf (file, "}\n");
6158 check_bb_profile (EXIT_BLOCK_PTR, file);
6164 /* Make a tree based dump. */
6165 chain = DECL_SAVED_TREE (fn);
6167 if (chain && TREE_CODE (chain) == BIND_EXPR)
6169 if (ignore_topmost_bind)
6171 chain = BIND_EXPR_BODY (chain);
6179 if (!ignore_topmost_bind)
6180 fprintf (file, "{\n");
6185 fprintf (file, "\n");
6187 print_generic_stmt_indented (file, chain, flags, indent);
6188 if (ignore_topmost_bind)
6189 fprintf (file, "}\n");
6192 fprintf (file, "\n\n");
6199 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
6202 debug_function (tree fn, int flags)
6204 dump_function_to_file (fn, stderr, flags);
6208 /* Print on FILE the indexes for the predecessors of basic_block BB. */
6211 print_pred_bbs (FILE *file, basic_block bb)
6216 FOR_EACH_EDGE (e, ei, bb->preds)
6217 fprintf (file, "bb_%d ", e->src->index);
6221 /* Print on FILE the indexes for the successors of basic_block BB. */
6224 print_succ_bbs (FILE *file, basic_block bb)
6229 FOR_EACH_EDGE (e, ei, bb->succs)
6230 fprintf (file, "bb_%d ", e->dest->index);
6233 /* Print to FILE the basic block BB following the VERBOSITY level. */
6236 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6238 char *s_indent = (char *) alloca ((size_t) indent + 1);
6239 memset ((void *) s_indent, ' ', (size_t) indent);
6240 s_indent[indent] = '\0';
6242 /* Print basic_block's header. */
6245 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
6246 print_pred_bbs (file, bb);
6247 fprintf (file, "}, succs = {");
6248 print_succ_bbs (file, bb);
6249 fprintf (file, "})\n");
6252 /* Print basic_block's body. */
6255 fprintf (file, "%s {\n", s_indent);
6256 tree_dump_bb (bb, file, indent + 4);
6257 fprintf (file, "%s }\n", s_indent);
6261 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6263 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
6264 VERBOSITY level this outputs the contents of the loop, or just its
6268 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6276 s_indent = (char *) alloca ((size_t) indent + 1);
6277 memset ((void *) s_indent, ' ', (size_t) indent);
6278 s_indent[indent] = '\0';
6280 /* Print loop's header. */
6281 fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6282 loop->num, loop->header->index, loop->latch->index);
6283 fprintf (file, ", niter = ");
6284 print_generic_expr (file, loop->nb_iterations, 0);
6286 if (loop->any_upper_bound)
6288 fprintf (file, ", upper_bound = ");
6289 dump_double_int (file, loop->nb_iterations_upper_bound, true);
6292 if (loop->any_estimate)
6294 fprintf (file, ", estimate = ");
6295 dump_double_int (file, loop->nb_iterations_estimate, true);
6297 fprintf (file, ")\n");
6299 /* Print loop's body. */
6302 fprintf (file, "%s{\n", s_indent);
6304 if (bb->loop_father == loop)
6305 print_loops_bb (file, bb, indent, verbosity);
6307 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6308 fprintf (file, "%s}\n", s_indent);
6312 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6313 spaces. Following VERBOSITY level this outputs the contents of the
6314 loop, or just its structure. */
6317 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6322 print_loop (file, loop, indent, verbosity);
6323 print_loop_and_siblings (file, loop->next, indent, verbosity);
6326 /* Follow a CFG edge from the entry point of the program, and on entry
6327 of a loop, pretty print the loop structure on FILE. */
6330 print_loops (FILE *file, int verbosity)
6334 bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
6335 if (bb && bb->loop_father)
6336 print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6340 /* Debugging loops structure at tree level, at some VERBOSITY level. */
6343 debug_loops (int verbosity)
6345 print_loops (stderr, verbosity);
6348 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
6351 debug_loop (struct loop *loop, int verbosity)
6353 print_loop (stderr, loop, 0, verbosity);
6356 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6360 debug_loop_num (unsigned num, int verbosity)
6362 debug_loop (get_loop (num), verbosity);
6365 /* Return true if BB ends with a call, possibly followed by some
6366 instructions that must stay with the call. Return false,
6370 tree_block_ends_with_call_p (basic_block bb)
6372 block_stmt_iterator bsi = bsi_last (bb);
6373 return get_call_expr_in (bsi_stmt (bsi)) != NULL;
6377 /* Return true if BB ends with a conditional branch. Return false,
6381 tree_block_ends_with_condjump_p (const_basic_block bb)
6383 /* This CONST_CAST is okay because last_stmt doesn't modify its
6384 argument and the return value is not modified. */
6385 const_tree stmt = last_stmt (CONST_CAST_BB(bb));
6386 return (stmt && TREE_CODE (stmt) == COND_EXPR);
6390 /* Return true if we need to add fake edge to exit at statement T.
6391 Helper function for tree_flow_call_edges_add. */
6394 need_fake_edge_p (tree t)
6398 /* NORETURN and LONGJMP calls already have an edge to exit.
6399 CONST and PURE calls do not need one.
6400 We don't currently check for CONST and PURE here, although
6401 it would be a good idea, because those attributes are
6402 figured out from the RTL in mark_constant_function, and
6403 the counter incrementation code from -fprofile-arcs
6404 leads to different results from -fbranch-probabilities. */
6405 call = get_call_expr_in (t);
6407 && !(call_expr_flags (call) & ECF_NORETURN))
6410 if (TREE_CODE (t) == ASM_EXPR
6411 && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
6418 /* Add fake edges to the function exit for any non constant and non
6419 noreturn calls, volatile inline assembly in the bitmap of blocks
6420 specified by BLOCKS or to the whole CFG if BLOCKS is zero. Return
6421 the number of blocks that were split.
6423 The goal is to expose cases in which entering a basic block does
6424 not imply that all subsequent instructions must be executed. */
6427 tree_flow_call_edges_add (sbitmap blocks)
6430 int blocks_split = 0;
6431 int last_bb = last_basic_block;
6432 bool check_last_block = false;
6434 if (n_basic_blocks == NUM_FIXED_BLOCKS)
6438 check_last_block = true;
6440 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6442 /* In the last basic block, before epilogue generation, there will be
6443 a fallthru edge to EXIT. Special care is required if the last insn
6444 of the last basic block is a call because make_edge folds duplicate
6445 edges, which would result in the fallthru edge also being marked
6446 fake, which would result in the fallthru edge being removed by
6447 remove_fake_edges, which would result in an invalid CFG.
6449 Moreover, we can't elide the outgoing fake edge, since the block
6450 profiler needs to take this into account in order to solve the minimal
6451 spanning tree in the case that the call doesn't return.
6453 Handle this by adding a dummy instruction in a new last basic block. */
6454 if (check_last_block)
6456 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6457 block_stmt_iterator bsi = bsi_last (bb);
6459 if (!bsi_end_p (bsi))
6462 if (t && need_fake_edge_p (t))
6466 e = find_edge (bb, EXIT_BLOCK_PTR);
6469 bsi_insert_on_edge (e, build_empty_stmt ());
6470 bsi_commit_edge_inserts ();
6475 /* Now add fake edges to the function exit for any non constant
6476 calls since there is no way that we can determine if they will
6478 for (i = 0; i < last_bb; i++)
6480 basic_block bb = BASIC_BLOCK (i);
6481 block_stmt_iterator bsi;
6482 tree stmt, last_stmt;
6487 if (blocks && !TEST_BIT (blocks, i))
6490 bsi = bsi_last (bb);
6491 if (!bsi_end_p (bsi))
6493 last_stmt = bsi_stmt (bsi);
6496 stmt = bsi_stmt (bsi);
6497 if (need_fake_edge_p (stmt))
6500 /* The handling above of the final block before the
6501 epilogue should be enough to verify that there is
6502 no edge to the exit block in CFG already.
6503 Calling make_edge in such case would cause us to
6504 mark that edge as fake and remove it later. */
6505 #ifdef ENABLE_CHECKING
6506 if (stmt == last_stmt)
6508 e = find_edge (bb, EXIT_BLOCK_PTR);
6509 gcc_assert (e == NULL);
6513 /* Note that the following may create a new basic block
6514 and renumber the existing basic blocks. */
6515 if (stmt != last_stmt)
6517 e = split_block (bb, stmt);
6521 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6525 while (!bsi_end_p (bsi));
6530 verify_flow_info ();
6532 return blocks_split;
6535 /* Purge dead abnormal call edges from basic block BB. */
6538 tree_purge_dead_abnormal_call_edges (basic_block bb)
6540 bool changed = tree_purge_dead_eh_edges (bb);
6542 if (current_function_has_nonlocal_label)
6544 tree stmt = last_stmt (bb);
6548 if (!(stmt && tree_can_make_abnormal_goto (stmt)))
6549 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6551 if (e->flags & EDGE_ABNORMAL)
6560 /* See tree_purge_dead_eh_edges below. */
6562 free_dominance_info (CDI_DOMINATORS);
6568 /* Stores all basic blocks dominated by BB to DOM_BBS. */
6571 get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
6575 VEC_safe_push (basic_block, heap, *dom_bbs, bb);
6576 for (son = first_dom_son (CDI_DOMINATORS, bb);
6578 son = next_dom_son (CDI_DOMINATORS, son))
6579 get_all_dominated_blocks (son, dom_bbs);
6582 /* Removes edge E and all the blocks dominated by it, and updates dominance
6583 information. The IL in E->src needs to be updated separately.
6584 If dominance info is not available, only the edge E is removed.*/
6587 remove_edge_and_dominated_blocks (edge e)
6589 VEC (basic_block, heap) *bbs_to_remove = NULL;
6590 VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6594 bool none_removed = false;
6596 basic_block bb, dbb;
6599 if (!dom_info_available_p (CDI_DOMINATORS))
6605 /* No updating is needed for edges to exit. */
6606 if (e->dest == EXIT_BLOCK_PTR)
6608 if (cfgcleanup_altered_bbs)
6609 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6614 /* First, we find the basic blocks to remove. If E->dest has a predecessor
6615 that is not dominated by E->dest, then this set is empty. Otherwise,
6616 all the basic blocks dominated by E->dest are removed.
6618 Also, to DF_IDOM we store the immediate dominators of the blocks in
6619 the dominance frontier of E (i.e., of the successors of the
6620 removed blocks, if there are any, and of E->dest otherwise). */
6621 FOR_EACH_EDGE (f, ei, e->dest->preds)
6626 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6628 none_removed = true;
6633 df = BITMAP_ALLOC (NULL);
6634 df_idom = BITMAP_ALLOC (NULL);
6637 bitmap_set_bit (df_idom,
6638 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6641 get_all_dominated_blocks (e->dest, &bbs_to_remove);
6642 for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6644 FOR_EACH_EDGE (f, ei, bb->succs)
6646 if (f->dest != EXIT_BLOCK_PTR)
6647 bitmap_set_bit (df, f->dest->index);
6650 for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6651 bitmap_clear_bit (df, bb->index);
6653 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6655 bb = BASIC_BLOCK (i);
6656 bitmap_set_bit (df_idom,
6657 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6661 if (cfgcleanup_altered_bbs)
6663 /* Record the set of the altered basic blocks. */
6664 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6665 bitmap_ior_into (cfgcleanup_altered_bbs, df);
6668 /* Remove E and the cancelled blocks. */
6673 for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6674 delete_basic_block (bb);
6677 /* Update the dominance information. The immediate dominator may change only
6678 for blocks whose immediate dominator belongs to DF_IDOM:
6680 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6681 removal. Let Z the arbitrary block such that idom(Z) = Y and
6682 Z dominates X after the removal. Before removal, there exists a path P
6683 from Y to X that avoids Z. Let F be the last edge on P that is
6684 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
6685 dominates W, and because of P, Z does not dominate W), and W belongs to
6686 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
6687 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6689 bb = BASIC_BLOCK (i);
6690 for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6692 dbb = next_dom_son (CDI_DOMINATORS, dbb))
6693 VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6696 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6699 BITMAP_FREE (df_idom);
6700 VEC_free (basic_block, heap, bbs_to_remove);
6701 VEC_free (basic_block, heap, bbs_to_fix_dom);
6704 /* Purge dead EH edges from basic block BB. */
6707 tree_purge_dead_eh_edges (basic_block bb)
6709 bool changed = false;
6712 tree stmt = last_stmt (bb);
6714 if (stmt && tree_can_throw_internal (stmt))
6717 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6719 if (e->flags & EDGE_EH)
6721 remove_edge_and_dominated_blocks (e);
6732 tree_purge_all_dead_eh_edges (const_bitmap blocks)
6734 bool changed = false;
6738 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6740 changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
6746 /* This function is called whenever a new edge is created or
6750 tree_execute_on_growing_pred (edge e)
6752 basic_block bb = e->dest;
6755 reserve_phi_args_for_new_edge (bb);
6758 /* This function is called immediately before edge E is removed from
6759 the edge vector E->dest->preds. */
6762 tree_execute_on_shrinking_pred (edge e)
6764 if (phi_nodes (e->dest))
6765 remove_phi_args (e);
6768 /*---------------------------------------------------------------------------
6769 Helper functions for Loop versioning
6770 ---------------------------------------------------------------------------*/
6772 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
6773 of 'first'. Both of them are dominated by 'new_head' basic block. When
6774 'new_head' was created by 'second's incoming edge it received phi arguments
6775 on the edge by split_edge(). Later, additional edge 'e' was created to
6776 connect 'new_head' and 'first'. Now this routine adds phi args on this
6777 additional edge 'e' that new_head to second edge received as part of edge
6782 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
6783 basic_block new_head, edge e)
6786 edge e2 = find_edge (new_head, second);
6788 /* Because NEW_HEAD has been created by splitting SECOND's incoming
6789 edge, we should always have an edge from NEW_HEAD to SECOND. */
6790 gcc_assert (e2 != NULL);
6792 /* Browse all 'second' basic block phi nodes and add phi args to
6793 edge 'e' for 'first' head. PHI args are always in correct order. */
6795 for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
6797 phi2 = PHI_CHAIN (phi2), phi1 = PHI_CHAIN (phi1))
6799 tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
6800 add_phi_arg (phi1, def, e);
6804 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6805 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6806 the destination of the ELSE part. */
6808 tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
6809 basic_block second_head ATTRIBUTE_UNUSED,
6810 basic_block cond_bb, void *cond_e)
6812 block_stmt_iterator bsi;
6813 tree new_cond_expr = NULL_TREE;
6814 tree cond_expr = (tree) cond_e;
6817 /* Build new conditional expr */
6818 new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
6819 NULL_TREE, NULL_TREE);
6821 /* Add new cond in cond_bb. */
6822 bsi = bsi_start (cond_bb);
6823 bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
6824 /* Adjust edges appropriately to connect new head with first head
6825 as well as second head. */
6826 e0 = single_succ_edge (cond_bb);
6827 e0->flags &= ~EDGE_FALLTHRU;
6828 e0->flags |= EDGE_FALSE_VALUE;
6831 struct cfg_hooks tree_cfg_hooks = {
6833 tree_verify_flow_info,
6834 tree_dump_bb, /* dump_bb */
6835 create_bb, /* create_basic_block */
6836 tree_redirect_edge_and_branch,/* redirect_edge_and_branch */
6837 tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force */
6838 tree_can_remove_branch_p, /* can_remove_branch_p */
6839 remove_bb, /* delete_basic_block */
6840 tree_split_block, /* split_block */
6841 tree_move_block_after, /* move_block_after */
6842 tree_can_merge_blocks_p, /* can_merge_blocks_p */
6843 tree_merge_blocks, /* merge_blocks */
6844 tree_predict_edge, /* predict_edge */
6845 tree_predicted_by_p, /* predicted_by_p */
6846 tree_can_duplicate_bb_p, /* can_duplicate_block_p */
6847 tree_duplicate_bb, /* duplicate_block */
6848 tree_split_edge, /* split_edge */
6849 tree_make_forwarder_block, /* make_forward_block */
6850 NULL, /* tidy_fallthru_edge */
6851 tree_block_ends_with_call_p, /* block_ends_with_call_p */
6852 tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
6853 tree_flow_call_edges_add, /* flow_call_edges_add */
6854 tree_execute_on_growing_pred, /* execute_on_growing_pred */
6855 tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
6856 tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
6857 tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
6858 tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
6859 extract_true_false_edges_from_block, /* extract_cond_bb_edges */
6860 flush_pending_stmts /* flush_pending_stmts */
6864 /* Split all critical edges. */
6867 split_critical_edges (void)
6873 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6874 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
6875 mappings around the calls to split_edge. */
6876 start_recording_case_labels ();
6879 FOR_EACH_EDGE (e, ei, bb->succs)
6880 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
6885 end_recording_case_labels ();
6889 struct gimple_opt_pass pass_split_crit_edges =
6893 "crited", /* name */
6895 split_critical_edges, /* execute */
6898 0, /* static_pass_number */
6899 TV_TREE_SPLIT_EDGES, /* tv_id */
6900 PROP_cfg, /* properties required */
6901 PROP_no_crit_edges, /* properties_provided */
6902 0, /* properties_destroyed */
6903 0, /* todo_flags_start */
6904 TODO_dump_func /* todo_flags_finish */
6909 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
6910 a temporary, make sure and register it to be renamed if necessary,
6911 and finally return the temporary. Put the statements to compute
6912 EXP before the current statement in BSI. */
6915 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
6917 tree t, new_stmt, orig_stmt;
6919 if (is_gimple_val (exp))
6922 t = make_rename_temp (type, NULL);
6923 new_stmt = build_gimple_modify_stmt (t, exp);
6925 orig_stmt = bsi_stmt (*bsi);
6926 SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
6927 TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
6929 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
6930 if (gimple_in_ssa_p (cfun))
6931 mark_symbols_for_renaming (new_stmt);
6936 /* Build a ternary operation and gimplify it. Emit code before BSI.
6937 Return the gimple_val holding the result. */
6940 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
6941 tree type, tree a, tree b, tree c)
6945 ret = fold_build3 (code, type, a, b, c);
6948 return gimplify_val (bsi, type, ret);
6951 /* Build a binary operation and gimplify it. Emit code before BSI.
6952 Return the gimple_val holding the result. */
6955 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
6956 tree type, tree a, tree b)
6960 ret = fold_build2 (code, type, a, b);
6963 return gimplify_val (bsi, type, ret);
6966 /* Build a unary operation and gimplify it. Emit code before BSI.
6967 Return the gimple_val holding the result. */
6970 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
6975 ret = fold_build1 (code, type, a);
6978 return gimplify_val (bsi, type, ret);
6983 /* Emit return warnings. */
6986 execute_warn_function_return (void)
6988 source_location location;
6993 /* If we have a path to EXIT, then we do return. */
6994 if (TREE_THIS_VOLATILE (cfun->decl)
6995 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
6997 location = UNKNOWN_LOCATION;
6998 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7000 last = last_stmt (e->src);
7001 if (TREE_CODE (last) == RETURN_EXPR
7002 && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
7005 if (location == UNKNOWN_LOCATION)
7006 location = cfun->function_end_locus;
7007 warning (0, "%H%<noreturn%> function does return", &location);
7010 /* If we see "return;" in some basic block, then we do reach the end
7011 without returning a value. */
7012 else if (warn_return_type
7013 && !TREE_NO_WARNING (cfun->decl)
7014 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7015 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7017 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7019 tree last = last_stmt (e->src);
7020 if (TREE_CODE (last) == RETURN_EXPR
7021 && TREE_OPERAND (last, 0) == NULL
7022 && !TREE_NO_WARNING (last))
7024 location = EXPR_LOCATION (last);
7025 if (location == UNKNOWN_LOCATION)
7026 location = cfun->function_end_locus;
7027 warning (OPT_Wreturn_type, "%Hcontrol reaches end of non-void function", &location);
7028 TREE_NO_WARNING (cfun->decl) = 1;
7037 /* Given a basic block B which ends with a conditional and has
7038 precisely two successors, determine which of the edges is taken if
7039 the conditional is true and which is taken if the conditional is
7040 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
7043 extract_true_false_edges_from_block (basic_block b,
7047 edge e = EDGE_SUCC (b, 0);
7049 if (e->flags & EDGE_TRUE_VALUE)
7052 *false_edge = EDGE_SUCC (b, 1);
7057 *true_edge = EDGE_SUCC (b, 1);
7061 struct gimple_opt_pass pass_warn_function_return =
7067 execute_warn_function_return, /* execute */
7070 0, /* static_pass_number */
7072 PROP_cfg, /* properties_required */
7073 0, /* properties_provided */
7074 0, /* properties_destroyed */
7075 0, /* todo_flags_start */
7076 0 /* todo_flags_finish */
7080 /* Emit noreturn warnings. */
7083 execute_warn_function_noreturn (void)
7085 if (warn_missing_noreturn
7086 && !TREE_THIS_VOLATILE (cfun->decl)
7087 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
7088 && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
7089 warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
7090 "for attribute %<noreturn%>",
7095 struct gimple_opt_pass pass_warn_function_noreturn =
7101 execute_warn_function_noreturn, /* execute */
7104 0, /* static_pass_number */
7106 PROP_cfg, /* properties_required */
7107 0, /* properties_provided */
7108 0, /* properties_destroyed */
7109 0, /* todo_flags_start */
7110 0 /* todo_flags_finish */