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 /* Make sure the outermost BIND_EXPR in OMP_BODY isn't removed
1923 remove_useless_stmts_1 (&BIND_EXPR_BODY (OMP_BODY (*tp)), data);
1924 data->last_goto = NULL;
1933 remove_useless_stmts_1 (&OMP_BODY (*tp), data);
1934 data->last_goto = NULL;
1938 remove_useless_stmts_1 (&OMP_FOR_BODY (*tp), data);
1939 data->last_goto = NULL;
1940 if (OMP_FOR_PRE_BODY (*tp))
1942 remove_useless_stmts_1 (&OMP_FOR_PRE_BODY (*tp), data);
1943 data->last_goto = NULL;
1948 data->last_goto = NULL;
1954 remove_useless_stmts (void)
1956 struct rus_data data;
1958 clear_special_calls ();
1962 memset (&data, 0, sizeof (data));
1963 remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1965 while (data.repeat);
1970 struct gimple_opt_pass pass_remove_useless_stmts =
1974 "useless", /* name */
1976 remove_useless_stmts, /* execute */
1979 0, /* static_pass_number */
1981 PROP_gimple_any, /* properties_required */
1982 0, /* properties_provided */
1983 0, /* properties_destroyed */
1984 0, /* todo_flags_start */
1985 TODO_dump_func /* todo_flags_finish */
1989 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1992 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1996 /* Since this block is no longer reachable, we can just delete all
1997 of its PHI nodes. */
1998 phi = phi_nodes (bb);
2001 tree next = PHI_CHAIN (phi);
2002 remove_phi_node (phi, NULL_TREE, true);
2006 /* Remove edges to BB's successors. */
2007 while (EDGE_COUNT (bb->succs) > 0)
2008 remove_edge (EDGE_SUCC (bb, 0));
2012 /* Remove statements of basic block BB. */
2015 remove_bb (basic_block bb)
2017 block_stmt_iterator i;
2018 source_location loc = UNKNOWN_LOCATION;
2022 fprintf (dump_file, "Removing basic block %d\n", bb->index);
2023 if (dump_flags & TDF_DETAILS)
2025 dump_bb (bb, dump_file, 0);
2026 fprintf (dump_file, "\n");
2032 struct loop *loop = bb->loop_father;
2034 /* If a loop gets removed, clean up the information associated
2036 if (loop->latch == bb
2037 || loop->header == bb)
2038 free_numbers_of_iterations_estimates_loop (loop);
2041 /* Remove all the instructions in the block. */
2042 if (bb_stmt_list (bb) != NULL_TREE)
2044 for (i = bsi_start (bb); !bsi_end_p (i);)
2046 tree stmt = bsi_stmt (i);
2047 if (TREE_CODE (stmt) == LABEL_EXPR
2048 && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
2049 || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
2052 block_stmt_iterator new_bsi;
2054 /* A non-reachable non-local label may still be referenced.
2055 But it no longer needs to carry the extra semantics of
2057 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
2059 DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
2060 FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
2063 new_bb = bb->prev_bb;
2064 new_bsi = bsi_start (new_bb);
2065 bsi_remove (&i, false);
2066 bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2070 /* Release SSA definitions if we are in SSA. Note that we
2071 may be called when not in SSA. For example,
2072 final_cleanup calls this function via
2073 cleanup_tree_cfg. */
2074 if (gimple_in_ssa_p (cfun))
2075 release_defs (stmt);
2077 bsi_remove (&i, true);
2080 /* Don't warn for removed gotos. Gotos are often removed due to
2081 jump threading, thus resulting in bogus warnings. Not great,
2082 since this way we lose warnings for gotos in the original
2083 program that are indeed unreachable. */
2084 if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2086 if (EXPR_HAS_LOCATION (stmt))
2087 loc = EXPR_LOCATION (stmt);
2092 /* If requested, give a warning that the first statement in the
2093 block is unreachable. We walk statements backwards in the
2094 loop above, so the last statement we process is the first statement
2096 if (loc > BUILTINS_LOCATION && LOCATION_LINE (loc) > 0)
2097 warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2099 remove_phi_nodes_and_edges_for_unreachable_block (bb);
2104 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2105 predicate VAL, return the edge that will be taken out of the block.
2106 If VAL does not match a unique edge, NULL is returned. */
2109 find_taken_edge (basic_block bb, tree val)
2113 stmt = last_stmt (bb);
2116 gcc_assert (is_ctrl_stmt (stmt));
2119 if (! is_gimple_min_invariant (val))
2122 if (TREE_CODE (stmt) == COND_EXPR)
2123 return find_taken_edge_cond_expr (bb, val);
2125 if (TREE_CODE (stmt) == SWITCH_EXPR)
2126 return find_taken_edge_switch_expr (bb, val);
2128 if (computed_goto_p (stmt))
2130 /* Only optimize if the argument is a label, if the argument is
2131 not a label then we can not construct a proper CFG.
2133 It may be the case that we only need to allow the LABEL_REF to
2134 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2135 appear inside a LABEL_EXPR just to be safe. */
2136 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2137 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2138 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2145 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2146 statement, determine which of the outgoing edges will be taken out of the
2147 block. Return NULL if either edge may be taken. */
2150 find_taken_edge_computed_goto (basic_block bb, tree val)
2155 dest = label_to_block (val);
2158 e = find_edge (bb, dest);
2159 gcc_assert (e != NULL);
2165 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2166 statement, determine which of the two edges will be taken out of the
2167 block. Return NULL if either edge may be taken. */
2170 find_taken_edge_cond_expr (basic_block bb, tree val)
2172 edge true_edge, false_edge;
2174 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2176 gcc_assert (TREE_CODE (val) == INTEGER_CST);
2177 return (integer_zerop (val) ? false_edge : true_edge);
2180 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2181 statement, determine which edge will be taken out of the block. Return
2182 NULL if any edge may be taken. */
2185 find_taken_edge_switch_expr (basic_block bb, tree val)
2187 tree switch_expr, taken_case;
2188 basic_block dest_bb;
2191 switch_expr = last_stmt (bb);
2192 taken_case = find_case_label_for_value (switch_expr, val);
2193 dest_bb = label_to_block (CASE_LABEL (taken_case));
2195 e = find_edge (bb, dest_bb);
2201 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2202 We can make optimal use here of the fact that the case labels are
2203 sorted: We can do a binary search for a case matching VAL. */
2206 find_case_label_for_value (tree switch_expr, tree val)
2208 tree vec = SWITCH_LABELS (switch_expr);
2209 size_t low, high, n = TREE_VEC_LENGTH (vec);
2210 tree default_case = TREE_VEC_ELT (vec, n - 1);
2212 for (low = -1, high = n - 1; high - low > 1; )
2214 size_t i = (high + low) / 2;
2215 tree t = TREE_VEC_ELT (vec, i);
2218 /* Cache the result of comparing CASE_LOW and val. */
2219 cmp = tree_int_cst_compare (CASE_LOW (t), val);
2226 if (CASE_HIGH (t) == NULL)
2228 /* A singe-valued case label. */
2234 /* A case range. We can only handle integer ranges. */
2235 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2240 return default_case;
2246 /*---------------------------------------------------------------------------
2248 ---------------------------------------------------------------------------*/
2250 /* Dump tree-specific information of block BB to file OUTF. */
2253 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2255 dump_generic_bb (outf, bb, indent, TDF_VOPS|TDF_MEMSYMS);
2259 /* Dump a basic block on stderr. */
2262 debug_tree_bb (basic_block bb)
2264 dump_bb (bb, stderr, 0);
2268 /* Dump basic block with index N on stderr. */
2271 debug_tree_bb_n (int n)
2273 debug_tree_bb (BASIC_BLOCK (n));
2274 return BASIC_BLOCK (n);
2278 /* Dump the CFG on stderr.
2280 FLAGS are the same used by the tree dumping functions
2281 (see TDF_* in tree-pass.h). */
2284 debug_tree_cfg (int flags)
2286 dump_tree_cfg (stderr, flags);
2290 /* Dump the program showing basic block boundaries on the given FILE.
2292 FLAGS are the same used by the tree dumping functions (see TDF_* in
2296 dump_tree_cfg (FILE *file, int flags)
2298 if (flags & TDF_DETAILS)
2300 const char *funcname
2301 = lang_hooks.decl_printable_name (current_function_decl, 2);
2304 fprintf (file, ";; Function %s\n\n", funcname);
2305 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2306 n_basic_blocks, n_edges, last_basic_block);
2308 brief_dump_cfg (file);
2309 fprintf (file, "\n");
2312 if (flags & TDF_STATS)
2313 dump_cfg_stats (file);
2315 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2319 /* Dump CFG statistics on FILE. */
2322 dump_cfg_stats (FILE *file)
2324 static long max_num_merged_labels = 0;
2325 unsigned long size, total = 0;
2328 const char * const fmt_str = "%-30s%-13s%12s\n";
2329 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2330 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2331 const char * const fmt_str_3 = "%-43s%11lu%c\n";
2332 const char *funcname
2333 = lang_hooks.decl_printable_name (current_function_decl, 2);
2336 fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2338 fprintf (file, "---------------------------------------------------------\n");
2339 fprintf (file, fmt_str, "", " Number of ", "Memory");
2340 fprintf (file, fmt_str, "", " instances ", "used ");
2341 fprintf (file, "---------------------------------------------------------\n");
2343 size = n_basic_blocks * sizeof (struct basic_block_def);
2345 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2346 SCALE (size), LABEL (size));
2350 num_edges += EDGE_COUNT (bb->succs);
2351 size = num_edges * sizeof (struct edge_def);
2353 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2355 fprintf (file, "---------------------------------------------------------\n");
2356 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2358 fprintf (file, "---------------------------------------------------------\n");
2359 fprintf (file, "\n");
2361 if (cfg_stats.num_merged_labels > max_num_merged_labels)
2362 max_num_merged_labels = cfg_stats.num_merged_labels;
2364 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2365 cfg_stats.num_merged_labels, max_num_merged_labels);
2367 fprintf (file, "\n");
2371 /* Dump CFG statistics on stderr. Keep extern so that it's always
2372 linked in the final executable. */
2375 debug_cfg_stats (void)
2377 dump_cfg_stats (stderr);
2381 /* Dump the flowgraph to a .vcg FILE. */
2384 tree_cfg2vcg (FILE *file)
2389 const char *funcname
2390 = lang_hooks.decl_printable_name (current_function_decl, 2);
2392 /* Write the file header. */
2393 fprintf (file, "graph: { title: \"%s\"\n", funcname);
2394 fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2395 fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2397 /* Write blocks and edges. */
2398 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2400 fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2403 if (e->flags & EDGE_FAKE)
2404 fprintf (file, " linestyle: dotted priority: 10");
2406 fprintf (file, " linestyle: solid priority: 100");
2408 fprintf (file, " }\n");
2414 enum tree_code head_code, end_code;
2415 const char *head_name, *end_name;
2418 tree first = first_stmt (bb);
2419 tree last = last_stmt (bb);
2423 head_code = TREE_CODE (first);
2424 head_name = tree_code_name[head_code];
2425 head_line = get_lineno (first);
2428 head_name = "no-statement";
2432 end_code = TREE_CODE (last);
2433 end_name = tree_code_name[end_code];
2434 end_line = get_lineno (last);
2437 end_name = "no-statement";
2439 fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2440 bb->index, bb->index, head_name, head_line, end_name,
2443 FOR_EACH_EDGE (e, ei, bb->succs)
2445 if (e->dest == EXIT_BLOCK_PTR)
2446 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2448 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2450 if (e->flags & EDGE_FAKE)
2451 fprintf (file, " priority: 10 linestyle: dotted");
2453 fprintf (file, " priority: 100 linestyle: solid");
2455 fprintf (file, " }\n");
2458 if (bb->next_bb != EXIT_BLOCK_PTR)
2462 fputs ("}\n\n", file);
2467 /*---------------------------------------------------------------------------
2468 Miscellaneous helpers
2469 ---------------------------------------------------------------------------*/
2471 /* Return true if T represents a stmt that always transfers control. */
2474 is_ctrl_stmt (const_tree t)
2476 return (TREE_CODE (t) == COND_EXPR
2477 || TREE_CODE (t) == SWITCH_EXPR
2478 || TREE_CODE (t) == GOTO_EXPR
2479 || TREE_CODE (t) == RETURN_EXPR
2480 || TREE_CODE (t) == RESX_EXPR);
2484 /* Return true if T is a statement that may alter the flow of control
2485 (e.g., a call to a non-returning function). */
2488 is_ctrl_altering_stmt (const_tree t)
2493 call = get_call_expr_in (CONST_CAST_TREE (t));
2496 /* A non-pure/const CALL_EXPR alters flow control if the current
2497 function has nonlocal labels. */
2498 if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2501 /* A CALL_EXPR also alters control flow if it does not return. */
2502 if (call_expr_flags (call) & ECF_NORETURN)
2506 /* OpenMP directives alter control flow. */
2507 if (OMP_DIRECTIVE_P (t))
2510 /* If a statement can throw, it alters control flow. */
2511 return tree_can_throw_internal (t);
2515 /* Return true if T is a computed goto. */
2518 computed_goto_p (const_tree t)
2520 return (TREE_CODE (t) == GOTO_EXPR
2521 && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2525 /* Return true if T is a simple local goto. */
2528 simple_goto_p (const_tree t)
2530 return (TREE_CODE (t) == GOTO_EXPR
2531 && TREE_CODE (GOTO_DESTINATION (t)) == LABEL_DECL);
2535 /* Return true if T can make an abnormal transfer of control flow.
2536 Transfers of control flow associated with EH are excluded. */
2539 tree_can_make_abnormal_goto (const_tree t)
2541 if (computed_goto_p (t))
2543 if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
2544 t = GIMPLE_STMT_OPERAND (t, 1);
2545 if (TREE_CODE (t) == WITH_SIZE_EXPR)
2546 t = TREE_OPERAND (t, 0);
2547 if (TREE_CODE (t) == CALL_EXPR)
2548 return TREE_SIDE_EFFECTS (t) && current_function_has_nonlocal_label;
2553 /* Return true if T should start a new basic block. PREV_T is the
2554 statement preceding T. It is used when T is a label or a case label.
2555 Labels should only start a new basic block if their previous statement
2556 wasn't a label. Otherwise, sequence of labels would generate
2557 unnecessary basic blocks that only contain a single label. */
2560 stmt_starts_bb_p (const_tree t, const_tree prev_t)
2565 /* LABEL_EXPRs start a new basic block only if the preceding
2566 statement wasn't a label of the same type. This prevents the
2567 creation of consecutive blocks that have nothing but a single
2569 if (TREE_CODE (t) == LABEL_EXPR)
2571 /* Nonlocal and computed GOTO targets always start a new block. */
2572 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2573 || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2576 if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2578 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2581 cfg_stats.num_merged_labels++;
2592 /* Return true if T should end a basic block. */
2595 stmt_ends_bb_p (const_tree t)
2597 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2600 /* Remove block annotations and other datastructures. */
2603 delete_tree_cfg_annotations (void)
2606 block_stmt_iterator bsi;
2608 /* Remove annotations from every tree in the function. */
2610 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2612 tree stmt = bsi_stmt (bsi);
2613 ggc_free (stmt->base.ann);
2614 stmt->base.ann = NULL;
2616 label_to_block_map = NULL;
2620 /* Return the first statement in basic block BB. */
2623 first_stmt (basic_block bb)
2625 block_stmt_iterator i = bsi_start (bb);
2626 return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2629 /* Return the last statement in basic block BB. */
2632 last_stmt (basic_block bb)
2634 block_stmt_iterator b = bsi_last (bb);
2635 return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2638 /* Return the last statement of an otherwise empty block. Return NULL
2639 if the block is totally empty, or if it contains more than one
2643 last_and_only_stmt (basic_block bb)
2645 block_stmt_iterator i = bsi_last (bb);
2651 last = bsi_stmt (i);
2656 /* Empty statements should no longer appear in the instruction stream.
2657 Everything that might have appeared before should be deleted by
2658 remove_useless_stmts, and the optimizers should just bsi_remove
2659 instead of smashing with build_empty_stmt.
2661 Thus the only thing that should appear here in a block containing
2662 one executable statement is a label. */
2663 prev = bsi_stmt (i);
2664 if (TREE_CODE (prev) == LABEL_EXPR)
2671 /* Mark BB as the basic block holding statement T. */
2674 set_bb_for_stmt (tree t, basic_block bb)
2676 if (TREE_CODE (t) == PHI_NODE)
2678 else if (TREE_CODE (t) == STATEMENT_LIST)
2680 tree_stmt_iterator i;
2681 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2682 set_bb_for_stmt (tsi_stmt (i), bb);
2686 stmt_ann_t ann = get_stmt_ann (t);
2689 /* If the statement is a label, add the label to block-to-labels map
2690 so that we can speed up edge creation for GOTO_EXPRs. */
2691 if (TREE_CODE (t) == LABEL_EXPR)
2695 t = LABEL_EXPR_LABEL (t);
2696 uid = LABEL_DECL_UID (t);
2699 unsigned old_len = VEC_length (basic_block, label_to_block_map);
2700 LABEL_DECL_UID (t) = uid = cfun->cfg->last_label_uid++;
2701 if (old_len <= (unsigned) uid)
2703 unsigned new_len = 3 * uid / 2;
2705 VEC_safe_grow_cleared (basic_block, gc, label_to_block_map,
2710 /* We're moving an existing label. Make sure that we've
2711 removed it from the old block. */
2713 || !VEC_index (basic_block, label_to_block_map, uid));
2714 VEC_replace (basic_block, label_to_block_map, uid, bb);
2719 /* Faster version of set_bb_for_stmt that assume that statement is being moved
2720 from one basic block to another.
2721 For BB splitting we can run into quadratic case, so performance is quite
2722 important and knowing that the tables are big enough, change_bb_for_stmt
2723 can inline as leaf function. */
2725 change_bb_for_stmt (tree t, basic_block bb)
2727 get_stmt_ann (t)->bb = bb;
2728 if (TREE_CODE (t) == LABEL_EXPR)
2729 VEC_replace (basic_block, label_to_block_map,
2730 LABEL_DECL_UID (LABEL_EXPR_LABEL (t)), bb);
2733 /* Finds iterator for STMT. */
2735 extern block_stmt_iterator
2736 bsi_for_stmt (tree stmt)
2738 block_stmt_iterator bsi;
2740 for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2741 if (bsi_stmt (bsi) == stmt)
2747 /* Mark statement T as modified, and update it. */
2749 update_modified_stmts (tree t)
2751 if (!ssa_operands_active ())
2753 if (TREE_CODE (t) == STATEMENT_LIST)
2755 tree_stmt_iterator i;
2757 for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2759 stmt = tsi_stmt (i);
2760 update_stmt_if_modified (stmt);
2764 update_stmt_if_modified (t);
2767 /* Insert statement (or statement list) T before the statement
2768 pointed-to by iterator I. M specifies how to update iterator I
2769 after insertion (see enum bsi_iterator_update). */
2772 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2774 set_bb_for_stmt (t, i->bb);
2775 update_modified_stmts (t);
2776 tsi_link_before (&i->tsi, t, m);
2780 /* Insert statement (or statement list) T after the statement
2781 pointed-to by iterator I. M specifies how to update iterator I
2782 after insertion (see enum bsi_iterator_update). */
2785 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2787 set_bb_for_stmt (t, i->bb);
2788 update_modified_stmts (t);
2789 tsi_link_after (&i->tsi, t, m);
2793 /* Remove the statement pointed to by iterator I. The iterator is updated
2794 to the next statement.
2796 When REMOVE_EH_INFO is true we remove the statement pointed to by
2797 iterator I from the EH tables. Otherwise we do not modify the EH
2800 Generally, REMOVE_EH_INFO should be true when the statement is going to
2801 be removed from the IL and not reinserted elsewhere. */
2804 bsi_remove (block_stmt_iterator *i, bool remove_eh_info)
2806 tree t = bsi_stmt (*i);
2807 set_bb_for_stmt (t, NULL);
2808 delink_stmt_imm_use (t);
2809 tsi_delink (&i->tsi);
2810 mark_stmt_modified (t);
2813 remove_stmt_from_eh_region (t);
2814 gimple_remove_stmt_histograms (cfun, t);
2819 /* Move the statement at FROM so it comes right after the statement at TO. */
2822 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2824 tree stmt = bsi_stmt (*from);
2825 bsi_remove (from, false);
2826 /* We must have BSI_NEW_STMT here, as bsi_move_after is sometimes used to
2827 move statements to an empty block. */
2828 bsi_insert_after (to, stmt, BSI_NEW_STMT);
2832 /* Move the statement at FROM so it comes right before the statement at TO. */
2835 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2837 tree stmt = bsi_stmt (*from);
2838 bsi_remove (from, false);
2839 /* For consistency with bsi_move_after, it might be better to have
2840 BSI_NEW_STMT here; however, that breaks several places that expect
2841 that TO does not change. */
2842 bsi_insert_before (to, stmt, BSI_SAME_STMT);
2846 /* Move the statement at FROM to the end of basic block BB. */
2849 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2851 block_stmt_iterator last = bsi_last (bb);
2853 /* Have to check bsi_end_p because it could be an empty block. */
2854 if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2855 bsi_move_before (from, &last);
2857 bsi_move_after (from, &last);
2861 /* Replace the contents of the statement pointed to by iterator BSI
2862 with STMT. If UPDATE_EH_INFO is true, the exception handling
2863 information of the original statement is moved to the new statement. */
2866 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
2869 tree orig_stmt = bsi_stmt (*bsi);
2871 if (stmt == orig_stmt)
2873 SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2874 set_bb_for_stmt (stmt, bsi->bb);
2876 /* Preserve EH region information from the original statement, if
2877 requested by the caller. */
2880 eh_region = lookup_stmt_eh_region (orig_stmt);
2883 remove_stmt_from_eh_region (orig_stmt);
2884 add_stmt_to_eh_region (stmt, eh_region);
2888 gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
2889 gimple_remove_stmt_histograms (cfun, orig_stmt);
2890 delink_stmt_imm_use (orig_stmt);
2891 *bsi_stmt_ptr (*bsi) = stmt;
2892 mark_stmt_modified (stmt);
2893 update_modified_stmts (stmt);
2897 /* Insert the statement pointed-to by BSI into edge E. Every attempt
2898 is made to place the statement in an existing basic block, but
2899 sometimes that isn't possible. When it isn't possible, the edge is
2900 split and the statement is added to the new block.
2902 In all cases, the returned *BSI points to the correct location. The
2903 return value is true if insertion should be done after the location,
2904 or false if it should be done before the location. If new basic block
2905 has to be created, it is stored in *NEW_BB. */
2908 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2909 basic_block *new_bb)
2911 basic_block dest, src;
2917 /* If the destination has one predecessor which has no PHI nodes,
2918 insert there. Except for the exit block.
2920 The requirement for no PHI nodes could be relaxed. Basically we
2921 would have to examine the PHIs to prove that none of them used
2922 the value set by the statement we want to insert on E. That
2923 hardly seems worth the effort. */
2924 if (single_pred_p (dest)
2925 && ! phi_nodes (dest)
2926 && dest != EXIT_BLOCK_PTR)
2928 *bsi = bsi_start (dest);
2929 if (bsi_end_p (*bsi))
2932 /* Make sure we insert after any leading labels. */
2933 tmp = bsi_stmt (*bsi);
2934 while (TREE_CODE (tmp) == LABEL_EXPR)
2937 if (bsi_end_p (*bsi))
2939 tmp = bsi_stmt (*bsi);
2942 if (bsi_end_p (*bsi))
2944 *bsi = bsi_last (dest);
2951 /* If the source has one successor, the edge is not abnormal and
2952 the last statement does not end a basic block, insert there.
2953 Except for the entry block. */
2955 if ((e->flags & EDGE_ABNORMAL) == 0
2956 && single_succ_p (src)
2957 && src != ENTRY_BLOCK_PTR)
2959 *bsi = bsi_last (src);
2960 if (bsi_end_p (*bsi))
2963 tmp = bsi_stmt (*bsi);
2964 if (!stmt_ends_bb_p (tmp))
2967 /* Insert code just before returning the value. We may need to decompose
2968 the return in the case it contains non-trivial operand. */
2969 if (TREE_CODE (tmp) == RETURN_EXPR)
2971 tree op = TREE_OPERAND (tmp, 0);
2972 if (op && !is_gimple_val (op))
2974 gcc_assert (TREE_CODE (op) == GIMPLE_MODIFY_STMT);
2975 bsi_insert_before (bsi, op, BSI_NEW_STMT);
2976 TREE_OPERAND (tmp, 0) = GIMPLE_STMT_OPERAND (op, 0);
2983 /* Otherwise, create a new basic block, and split this edge. */
2984 dest = split_edge (e);
2987 e = single_pred_edge (dest);
2992 /* This routine will commit all pending edge insertions, creating any new
2993 basic blocks which are necessary. */
2996 bsi_commit_edge_inserts (void)
3002 bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
3005 FOR_EACH_EDGE (e, ei, bb->succs)
3006 bsi_commit_one_edge_insert (e, NULL);
3010 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3011 to this block, otherwise set it to NULL. */
3014 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3018 if (PENDING_STMT (e))
3020 block_stmt_iterator bsi;
3021 tree stmt = PENDING_STMT (e);
3023 PENDING_STMT (e) = NULL_TREE;
3025 if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3026 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3028 bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3033 /* Add STMT to the pending list of edge E. No actual insertion is
3034 made until a call to bsi_commit_edge_inserts () is made. */
3037 bsi_insert_on_edge (edge e, tree stmt)
3039 append_to_statement_list (stmt, &PENDING_STMT (e));
3042 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If a new
3043 block has to be created, it is returned. */
3046 bsi_insert_on_edge_immediate (edge e, tree stmt)
3048 block_stmt_iterator bsi;
3049 basic_block new_bb = NULL;
3051 gcc_assert (!PENDING_STMT (e));
3053 if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3054 bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3056 bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3061 /*---------------------------------------------------------------------------
3062 Tree specific functions for CFG manipulation
3063 ---------------------------------------------------------------------------*/
3065 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */
3068 reinstall_phi_args (edge new_edge, edge old_edge)
3071 edge_var_map_vector v;
3075 v = redirect_edge_var_map_vector (old_edge);
3079 for (i = 0, phi = phi_nodes (new_edge->dest);
3080 VEC_iterate (edge_var_map, v, i, vm) && phi;
3081 i++, phi = PHI_CHAIN (phi))
3083 tree result = redirect_edge_var_map_result (vm);
3084 tree arg = redirect_edge_var_map_def (vm);
3086 gcc_assert (result == PHI_RESULT (phi));
3088 add_phi_arg (phi, arg, new_edge);
3091 redirect_edge_var_map_clear (old_edge);
3094 /* Returns the basic block after which the new basic block created
3095 by splitting edge EDGE_IN should be placed. Tries to keep the new block
3096 near its "logical" location. This is of most help to humans looking
3097 at debugging dumps. */
3100 split_edge_bb_loc (edge edge_in)
3102 basic_block dest = edge_in->dest;
3104 if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3105 return edge_in->src;
3107 return dest->prev_bb;
3110 /* Split a (typically critical) edge EDGE_IN. Return the new block.
3111 Abort on abnormal edges. */
3114 tree_split_edge (edge edge_in)
3116 basic_block new_bb, after_bb, dest;
3119 /* Abnormal edges cannot be split. */
3120 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3122 dest = edge_in->dest;
3124 after_bb = split_edge_bb_loc (edge_in);
3126 new_bb = create_empty_bb (after_bb);
3127 new_bb->frequency = EDGE_FREQUENCY (edge_in);
3128 new_bb->count = edge_in->count;
3129 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3130 new_edge->probability = REG_BR_PROB_BASE;
3131 new_edge->count = edge_in->count;
3133 e = redirect_edge_and_branch (edge_in, new_bb);
3134 gcc_assert (e == edge_in);
3135 reinstall_phi_args (new_edge, e);
3140 /* Callback for walk_tree, check that all elements with address taken are
3141 properly noticed as such. The DATA is an int* that is 1 if TP was seen
3142 inside a PHI node. */
3145 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3152 /* Check operand N for being valid GIMPLE and give error MSG if not. */
3153 #define CHECK_OP(N, MSG) \
3154 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
3155 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3157 switch (TREE_CODE (t))
3160 if (SSA_NAME_IN_FREE_LIST (t))
3162 error ("SSA name in freelist but still referenced");
3168 x = fold (ASSERT_EXPR_COND (t));
3169 if (x == boolean_false_node)
3171 error ("ASSERT_EXPR with an always-false condition");
3179 case GIMPLE_MODIFY_STMT:
3180 x = GIMPLE_STMT_OPERAND (t, 0);
3181 if (TREE_CODE (x) == BIT_FIELD_REF
3182 && is_gimple_reg (TREE_OPERAND (x, 0)))
3184 error ("GIMPLE register modified with BIT_FIELD_REF");
3193 bool old_side_effects;
3196 bool new_side_effects;
3198 old_invariant = TREE_INVARIANT (t);
3199 old_constant = TREE_CONSTANT (t);
3200 old_side_effects = TREE_SIDE_EFFECTS (t);
3202 recompute_tree_invariant_for_addr_expr (t);
3203 new_invariant = TREE_INVARIANT (t);
3204 new_side_effects = TREE_SIDE_EFFECTS (t);
3205 new_constant = TREE_CONSTANT (t);
3207 if (old_invariant != new_invariant)
3209 error ("invariant not recomputed when ADDR_EXPR changed");
3213 if (old_constant != new_constant)
3215 error ("constant not recomputed when ADDR_EXPR changed");
3218 if (old_side_effects != new_side_effects)
3220 error ("side effects not recomputed when ADDR_EXPR changed");
3224 /* Skip any references (they will be checked when we recurse down the
3225 tree) and ensure that any variable used as a prefix is marked
3227 for (x = TREE_OPERAND (t, 0);
3228 handled_component_p (x);
3229 x = TREE_OPERAND (x, 0))
3232 if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3234 if (!TREE_ADDRESSABLE (x))
3236 error ("address taken, but ADDRESSABLE bit not set");
3244 x = COND_EXPR_COND (t);
3245 if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
3247 error ("non-integral used in condition");
3250 if (!is_gimple_condexpr (x))
3252 error ("invalid conditional operand");
3257 case NON_LVALUE_EXPR:
3262 case FIX_TRUNC_EXPR:
3267 case TRUTH_NOT_EXPR:
3268 CHECK_OP (0, "invalid operand to unary operator");
3275 case ARRAY_RANGE_REF:
3277 case VIEW_CONVERT_EXPR:
3278 /* We have a nest of references. Verify that each of the operands
3279 that determine where to reference is either a constant or a variable,
3280 verify that the base is valid, and then show we've already checked
3282 while (handled_component_p (t))
3284 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3285 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3286 else if (TREE_CODE (t) == ARRAY_REF
3287 || TREE_CODE (t) == ARRAY_RANGE_REF)
3289 CHECK_OP (1, "invalid array index");
3290 if (TREE_OPERAND (t, 2))
3291 CHECK_OP (2, "invalid array lower bound");
3292 if (TREE_OPERAND (t, 3))
3293 CHECK_OP (3, "invalid array stride");
3295 else if (TREE_CODE (t) == BIT_FIELD_REF)
3297 if (!host_integerp (TREE_OPERAND (t, 1), 1)
3298 || !host_integerp (TREE_OPERAND (t, 2), 1))
3300 error ("invalid position or size operand to BIT_FIELD_REF");
3303 else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
3304 && (TYPE_PRECISION (TREE_TYPE (t))
3305 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3307 error ("integral result type precision does not match "
3308 "field size of BIT_FIELD_REF");
3311 if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
3312 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
3313 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3315 error ("mode precision of non-integral result does not "
3316 "match field size of BIT_FIELD_REF");
3321 t = TREE_OPERAND (t, 0);
3324 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
3326 error ("invalid reference prefix");
3333 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3334 POINTER_PLUS_EXPR. */
3335 if (POINTER_TYPE_P (TREE_TYPE (t)))
3337 error ("invalid operand to plus/minus, type is a pointer");
3340 CHECK_OP (0, "invalid operand to binary operator");
3341 CHECK_OP (1, "invalid operand to binary operator");
3344 case POINTER_PLUS_EXPR:
3345 /* Check to make sure the first operand is a pointer or reference type. */
3346 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3348 error ("invalid operand to pointer plus, first operand is not a pointer");
3351 /* Check to make sure the second operand is an integer with type of
3353 if (!useless_type_conversion_p (sizetype,
3354 TREE_TYPE (TREE_OPERAND (t, 1))))
3356 error ("invalid operand to pointer plus, second operand is not an "
3357 "integer with type of sizetype.");
3367 case UNORDERED_EXPR:
3376 case TRUNC_DIV_EXPR:
3378 case FLOOR_DIV_EXPR:
3379 case ROUND_DIV_EXPR:
3380 case TRUNC_MOD_EXPR:
3382 case FLOOR_MOD_EXPR:
3383 case ROUND_MOD_EXPR:
3385 case EXACT_DIV_EXPR:
3395 CHECK_OP (0, "invalid operand to binary operator");
3396 CHECK_OP (1, "invalid operand to binary operator");
3400 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3412 /* Verifies if EXPR is a valid GIMPLE unary expression. Returns true
3413 if there is an error, otherwise false. */
3416 verify_gimple_unary_expr (const_tree expr)
3418 tree op = TREE_OPERAND (expr, 0);
3419 tree type = TREE_TYPE (expr);
3421 if (!is_gimple_val (op))
3423 error ("invalid operand in unary expression");
3427 /* For general unary expressions we have the operations type
3428 as the effective type the operation is carried out on. So all
3429 we need to require is that the operand is trivially convertible
3431 if (!useless_type_conversion_p (type, TREE_TYPE (op)))
3433 error ("type mismatch in unary expression");
3434 debug_generic_expr (type);
3435 debug_generic_expr (TREE_TYPE (op));
3442 /* Verifies if EXPR is a valid GIMPLE binary expression. Returns true
3443 if there is an error, otherwise false. */
3446 verify_gimple_binary_expr (const_tree expr)
3448 tree op0 = TREE_OPERAND (expr, 0);
3449 tree op1 = TREE_OPERAND (expr, 1);
3450 tree type = TREE_TYPE (expr);
3452 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3454 error ("invalid operands in binary expression");
3458 /* For general binary expressions we have the operations type
3459 as the effective type the operation is carried out on. So all
3460 we need to require is that both operands are trivially convertible
3462 if (!useless_type_conversion_p (type, TREE_TYPE (op0))
3463 || !useless_type_conversion_p (type, TREE_TYPE (op1)))
3465 error ("type mismatch in binary expression");
3466 debug_generic_stmt (type);
3467 debug_generic_stmt (TREE_TYPE (op0));
3468 debug_generic_stmt (TREE_TYPE (op1));
3475 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3476 Returns true if there is an error, otherwise false. */
3479 verify_gimple_min_lval (tree expr)
3483 if (is_gimple_id (expr))
3486 if (TREE_CODE (expr) != INDIRECT_REF
3487 && TREE_CODE (expr) != ALIGN_INDIRECT_REF
3488 && TREE_CODE (expr) != MISALIGNED_INDIRECT_REF)
3490 error ("invalid expression for min lvalue");
3494 op = TREE_OPERAND (expr, 0);
3495 if (!is_gimple_val (op))
3497 error ("invalid operand in indirect reference");
3498 debug_generic_stmt (op);
3501 if (!useless_type_conversion_p (TREE_TYPE (expr),
3502 TREE_TYPE (TREE_TYPE (op))))
3504 error ("type mismatch in indirect reference");
3505 debug_generic_stmt (TREE_TYPE (expr));
3506 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3513 /* Verify if EXPR is a valid GIMPLE reference expression. Returns true
3514 if there is an error, otherwise false. */
3517 verify_gimple_reference (tree expr)
3519 while (handled_component_p (expr))
3521 tree op = TREE_OPERAND (expr, 0);
3523 if (TREE_CODE (expr) == ARRAY_REF
3524 || TREE_CODE (expr) == ARRAY_RANGE_REF)
3526 if (!is_gimple_val (TREE_OPERAND (expr, 1))
3527 || (TREE_OPERAND (expr, 2)
3528 && !is_gimple_val (TREE_OPERAND (expr, 2)))
3529 || (TREE_OPERAND (expr, 3)
3530 && !is_gimple_val (TREE_OPERAND (expr, 3))))
3532 error ("invalid operands to array reference");
3533 debug_generic_stmt (expr);
3538 /* Verify if the reference array element types are compatible. */
3539 if (TREE_CODE (expr) == ARRAY_REF
3540 && !useless_type_conversion_p (TREE_TYPE (expr),
3541 TREE_TYPE (TREE_TYPE (op))))
3543 error ("type mismatch in array reference");
3544 debug_generic_stmt (TREE_TYPE (expr));
3545 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3548 if (TREE_CODE (expr) == ARRAY_RANGE_REF
3549 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3550 TREE_TYPE (TREE_TYPE (op))))
3552 error ("type mismatch in array range reference");
3553 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3554 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3558 if ((TREE_CODE (expr) == REALPART_EXPR
3559 || TREE_CODE (expr) == IMAGPART_EXPR)
3560 && !useless_type_conversion_p (TREE_TYPE (expr),
3561 TREE_TYPE (TREE_TYPE (op))))
3563 error ("type mismatch in real/imagpart reference");
3564 debug_generic_stmt (TREE_TYPE (expr));
3565 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3569 if (TREE_CODE (expr) == COMPONENT_REF
3570 && !useless_type_conversion_p (TREE_TYPE (expr),
3571 TREE_TYPE (TREE_OPERAND (expr, 1))))
3573 error ("type mismatch in component reference");
3574 debug_generic_stmt (TREE_TYPE (expr));
3575 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3579 /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3580 is nothing to verify. Gross mismatches at most invoke
3581 undefined behavior. */
3586 return verify_gimple_min_lval (expr);
3589 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3590 list of pointer-to types that is trivially convertible to DEST. */
3593 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3597 if (!TYPE_POINTER_TO (src_obj))
3600 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3601 if (useless_type_conversion_p (dest, src))
3607 /* Verify the GIMPLE expression EXPR. Returns true if there is an
3608 error, otherwise false. */
3611 verify_gimple_expr (tree expr)
3613 tree type = TREE_TYPE (expr);
3615 if (is_gimple_val (expr))
3618 /* Special codes we cannot handle via their class. */
3619 switch (TREE_CODE (expr))
3624 tree op = TREE_OPERAND (expr, 0);
3625 if (!is_gimple_val (op))
3627 error ("invalid operand in conversion");
3631 /* Allow conversions between integral types and between
3633 if ((INTEGRAL_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3634 || (POINTER_TYPE_P (type) && POINTER_TYPE_P (TREE_TYPE (op))))
3637 /* Allow conversions between integral types and pointers only if
3638 there is no sign or zero extension involved. */
3639 if (((POINTER_TYPE_P (type) && INTEGRAL_TYPE_P (TREE_TYPE (op)))
3640 || (POINTER_TYPE_P (TREE_TYPE (op)) && INTEGRAL_TYPE_P (type)))
3641 && TYPE_PRECISION (type) == TYPE_PRECISION (TREE_TYPE (op)))
3644 /* Allow conversion from integer to offset type and vice versa. */
3645 if ((TREE_CODE (type) == OFFSET_TYPE
3646 && TREE_CODE (TREE_TYPE (op)) == INTEGER_TYPE)
3647 || (TREE_CODE (type) == INTEGER_TYPE
3648 && TREE_CODE (TREE_TYPE (op)) == OFFSET_TYPE))
3651 /* Otherwise assert we are converting between types of the
3653 if (TREE_CODE (type) != TREE_CODE (TREE_TYPE (op)))
3655 error ("invalid types in nop conversion");
3656 debug_generic_expr (type);
3657 debug_generic_expr (TREE_TYPE (op));
3666 tree op = TREE_OPERAND (expr, 0);
3667 if (!is_gimple_val (op))
3669 error ("invalid operand in int to float conversion");
3672 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3673 || !SCALAR_FLOAT_TYPE_P (type))
3675 error ("invalid types in conversion to floating point");
3676 debug_generic_expr (type);
3677 debug_generic_expr (TREE_TYPE (op));
3683 case FIX_TRUNC_EXPR:
3685 tree op = TREE_OPERAND (expr, 0);
3686 if (!is_gimple_val (op))
3688 error ("invalid operand in float to int conversion");
3691 if (!INTEGRAL_TYPE_P (type)
3692 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
3694 error ("invalid types in conversion to integer");
3695 debug_generic_expr (type);
3696 debug_generic_expr (TREE_TYPE (op));
3704 tree op0 = TREE_OPERAND (expr, 0);
3705 tree op1 = TREE_OPERAND (expr, 1);
3706 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3708 error ("invalid operands in complex expression");
3711 if (!TREE_CODE (type) == COMPLEX_TYPE
3712 || !(TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
3713 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0)))
3714 || !(TREE_CODE (TREE_TYPE (op1)) == INTEGER_TYPE
3715 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op1)))
3716 || !useless_type_conversion_p (TREE_TYPE (type),
3718 || !useless_type_conversion_p (TREE_TYPE (type),
3721 error ("type mismatch in complex expression");
3722 debug_generic_stmt (TREE_TYPE (expr));
3723 debug_generic_stmt (TREE_TYPE (op0));
3724 debug_generic_stmt (TREE_TYPE (op1));
3732 /* This is used like COMPLEX_EXPR but for vectors. */
3733 if (TREE_CODE (type) != VECTOR_TYPE)
3735 error ("constructor not allowed for non-vector types");
3736 debug_generic_stmt (type);
3739 /* FIXME: verify constructor arguments. */
3748 tree op0 = TREE_OPERAND (expr, 0);
3749 tree op1 = TREE_OPERAND (expr, 1);
3750 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3752 error ("invalid operands in shift expression");
3755 if (!TREE_CODE (TREE_TYPE (op1)) == INTEGER_TYPE
3756 || !useless_type_conversion_p (type, TREE_TYPE (op0)))
3758 error ("type mismatch in shift expression");
3759 debug_generic_stmt (TREE_TYPE (expr));
3760 debug_generic_stmt (TREE_TYPE (op0));
3761 debug_generic_stmt (TREE_TYPE (op1));
3770 tree op0 = TREE_OPERAND (expr, 0);
3771 tree op1 = TREE_OPERAND (expr, 1);
3772 if (POINTER_TYPE_P (type)
3773 || POINTER_TYPE_P (TREE_TYPE (op0))
3774 || POINTER_TYPE_P (TREE_TYPE (op1)))
3776 error ("invalid (pointer) operands to plus/minus");
3779 /* Continue with generic binary expression handling. */
3783 case POINTER_PLUS_EXPR:
3785 tree op0 = TREE_OPERAND (expr, 0);
3786 tree op1 = TREE_OPERAND (expr, 1);
3787 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3789 error ("invalid operands in pointer plus expression");
3792 if (!POINTER_TYPE_P (TREE_TYPE (op0))
3793 || !useless_type_conversion_p (type, TREE_TYPE (op0))
3794 || !useless_type_conversion_p (sizetype, TREE_TYPE (op1)))
3796 error ("type mismatch in pointer plus expression");
3797 debug_generic_stmt (type);
3798 debug_generic_stmt (TREE_TYPE (op0));
3799 debug_generic_stmt (TREE_TYPE (op1));
3807 tree op0 = TREE_OPERAND (expr, 0);
3808 tree op1 = TREE_OPERAND (expr, 1);
3809 tree op2 = TREE_OPERAND (expr, 2);
3810 if ((!is_gimple_val (op1)
3811 && TREE_CODE (TREE_TYPE (op1)) != VOID_TYPE)
3812 || (!is_gimple_val (op2)
3813 && TREE_CODE (TREE_TYPE (op2)) != VOID_TYPE))
3815 error ("invalid operands in conditional expression");
3818 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3819 || (TREE_CODE (TREE_TYPE (op1)) != VOID_TYPE
3820 && !useless_type_conversion_p (type, TREE_TYPE (op1)))
3821 || (TREE_CODE (TREE_TYPE (op2)) != VOID_TYPE
3822 && !useless_type_conversion_p (type, TREE_TYPE (op2))))
3824 error ("type mismatch in conditional expression");
3825 debug_generic_stmt (type);
3826 debug_generic_stmt (TREE_TYPE (op0));
3827 debug_generic_stmt (TREE_TYPE (op1));
3828 debug_generic_stmt (TREE_TYPE (op2));
3831 return verify_gimple_expr (op0);
3836 tree op = TREE_OPERAND (expr, 0);
3837 if (!is_gimple_addressable (op))
3839 error ("invalid operand in unary expression");
3842 if (!one_pointer_to_useless_type_conversion_p (type, TREE_TYPE (op))
3843 /* FIXME: a longstanding wart, &a == &a[0]. */
3844 && (TREE_CODE (TREE_TYPE (op)) != ARRAY_TYPE
3845 || !one_pointer_to_useless_type_conversion_p (type,
3846 TREE_TYPE (TREE_TYPE (op)))))
3848 error ("type mismatch in address expression");
3849 debug_generic_stmt (TREE_TYPE (expr));
3850 debug_generic_stmt (TYPE_POINTER_TO (TREE_TYPE (op)));
3854 return verify_gimple_reference (op);
3857 case TRUTH_ANDIF_EXPR:
3858 case TRUTH_ORIF_EXPR:
3861 case TRUTH_AND_EXPR:
3863 case TRUTH_XOR_EXPR:
3865 tree op0 = TREE_OPERAND (expr, 0);
3866 tree op1 = TREE_OPERAND (expr, 1);
3868 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3870 error ("invalid operands in truth expression");
3874 /* We allow any kind of integral typed argument and result. */
3875 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
3876 || !INTEGRAL_TYPE_P (TREE_TYPE (op1))
3877 || !INTEGRAL_TYPE_P (type))
3879 error ("type mismatch in binary truth expression");
3880 debug_generic_stmt (type);
3881 debug_generic_stmt (TREE_TYPE (op0));
3882 debug_generic_stmt (TREE_TYPE (op1));
3889 case TRUTH_NOT_EXPR:
3891 tree op = TREE_OPERAND (expr, 0);
3893 if (!is_gimple_val (op))
3895 error ("invalid operand in unary not");
3899 /* For TRUTH_NOT_EXPR we can have any kind of integral
3900 typed arguments and results. */
3901 if (!INTEGRAL_TYPE_P (TREE_TYPE (op))
3902 || !INTEGRAL_TYPE_P (type))
3904 error ("type mismatch in not expression");
3905 debug_generic_expr (TREE_TYPE (expr));
3906 debug_generic_expr (TREE_TYPE (op));
3914 /* FIXME. The C frontend passes unpromoted arguments in case it
3915 didn't see a function declaration before the call. */
3925 /* Generic handling via classes. */
3926 switch (TREE_CODE_CLASS (TREE_CODE (expr)))
3929 return verify_gimple_unary_expr (expr);
3932 return verify_gimple_binary_expr (expr);
3935 return verify_gimple_reference (expr);
3937 case tcc_comparison:
3939 tree op0 = TREE_OPERAND (expr, 0);
3940 tree op1 = TREE_OPERAND (expr, 1);
3941 if (!is_gimple_val (op0) || !is_gimple_val (op1))
3943 error ("invalid operands in comparison expression");
3946 /* For comparisons we do not have the operations type as the
3947 effective type the comparison is carried out in. Instead
3948 we require that either the first operand is trivially
3949 convertible into the second, or the other way around.
3950 The resulting type of a comparison may be any integral type.
3951 Because we special-case pointers to void we allow
3952 comparisons of pointers with the same mode as well. */
3953 if ((!useless_type_conversion_p (TREE_TYPE (op0), TREE_TYPE (op1))
3954 && !useless_type_conversion_p (TREE_TYPE (op1), TREE_TYPE (op0))
3955 && (!POINTER_TYPE_P (TREE_TYPE (op0))
3956 || !POINTER_TYPE_P (TREE_TYPE (op1))
3957 || TYPE_MODE (TREE_TYPE (op0)) != TYPE_MODE (TREE_TYPE (op1))))
3958 || !INTEGRAL_TYPE_P (type))
3960 error ("type mismatch in comparison expression");
3961 debug_generic_stmt (TREE_TYPE (expr));
3962 debug_generic_stmt (TREE_TYPE (op0));
3963 debug_generic_stmt (TREE_TYPE (op1));
3976 /* Verify the GIMPLE assignment statement STMT. Returns true if there
3977 is an error, otherwise false. */
3980 verify_gimple_modify_stmt (const_tree stmt)
3982 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
3983 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
3985 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
3987 if (!useless_type_conversion_p (TREE_TYPE (lhs),
3990 error ("non-trivial conversion at assignment");
3991 debug_generic_expr (TREE_TYPE (lhs));
3992 debug_generic_expr (TREE_TYPE (rhs));
3996 /* Loads/stores from/to a variable are ok. */
3997 if ((is_gimple_val (lhs)
3998 && is_gimple_variable (rhs))
3999 || (is_gimple_val (rhs)
4000 && is_gimple_variable (lhs)))
4003 /* Aggregate copies are ok. */
4004 if (!is_gimple_reg_type (TREE_TYPE (lhs))
4005 && !is_gimple_reg_type (TREE_TYPE (rhs)))
4008 /* We might get 'loads' from a parameter which is not a gimple value. */
4009 if (TREE_CODE (rhs) == PARM_DECL)
4010 return verify_gimple_expr (lhs);
4012 if (!is_gimple_variable (lhs)
4013 && verify_gimple_expr (lhs))
4016 if (!is_gimple_variable (rhs)
4017 && verify_gimple_expr (rhs))
4023 /* Verify the GIMPLE statement STMT. Returns true if there is an
4024 error, otherwise false. */
4027 verify_gimple_stmt (tree stmt)
4029 if (!is_gimple_stmt (stmt))
4031 error ("is not a valid GIMPLE statement");
4035 if (OMP_DIRECTIVE_P (stmt))
4037 /* OpenMP directives are validated by the FE and never operated
4038 on by the optimizers. Furthermore, OMP_FOR may contain
4039 non-gimple expressions when the main index variable has had
4040 its address taken. This does not affect the loop itself
4041 because the header of an OMP_FOR is merely used to determine
4042 how to setup the parallel iteration. */
4046 switch (TREE_CODE (stmt))
4048 case GIMPLE_MODIFY_STMT:
4049 return verify_gimple_modify_stmt (stmt);
4056 if (!is_gimple_val (TREE_OPERAND (stmt, 0)))
4058 error ("invalid operand to switch statement");
4059 debug_generic_expr (TREE_OPERAND (stmt, 0));
4065 tree op = TREE_OPERAND (stmt, 0);
4067 if (TREE_CODE (TREE_TYPE (stmt)) != VOID_TYPE)
4069 error ("type error in return expression");
4074 || TREE_CODE (op) == RESULT_DECL)
4077 return verify_gimple_modify_stmt (op);
4082 return verify_gimple_expr (stmt);
4085 case CHANGE_DYNAMIC_TYPE_EXPR:
4095 /* Verify the GIMPLE statements inside the statement list STMTS.
4096 Returns true if there were any errors. */
4099 verify_gimple_2 (tree stmts)
4101 tree_stmt_iterator tsi;
4104 for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi))
4106 tree stmt = tsi_stmt (tsi);
4108 switch (TREE_CODE (stmt))
4111 err |= verify_gimple_2 (BIND_EXPR_BODY (stmt));
4114 case TRY_CATCH_EXPR:
4115 case TRY_FINALLY_EXPR:
4116 err |= verify_gimple_2 (TREE_OPERAND (stmt, 0));
4117 err |= verify_gimple_2 (TREE_OPERAND (stmt, 1));
4121 err |= verify_gimple_2 (CATCH_BODY (stmt));
4124 case EH_FILTER_EXPR:
4125 err |= verify_gimple_2 (EH_FILTER_FAILURE (stmt));
4130 bool err2 = verify_gimple_stmt (stmt);
4132 debug_generic_expr (stmt);
4142 /* Verify the GIMPLE statements inside the statement list STMTS. */
4145 verify_gimple_1 (tree stmts)
4147 if (verify_gimple_2 (stmts))
4148 internal_error ("verify_gimple failed");
4151 /* Verify the GIMPLE statements inside the current function. */
4154 verify_gimple (void)
4156 verify_gimple_1 (BIND_EXPR_BODY (DECL_SAVED_TREE (cfun->decl)));
4159 /* Verify STMT, return true if STMT is not in GIMPLE form.
4160 TODO: Implement type checking. */
4163 verify_stmt (tree stmt, bool last_in_block)
4167 if (OMP_DIRECTIVE_P (stmt))
4169 /* OpenMP directives are validated by the FE and never operated
4170 on by the optimizers. Furthermore, OMP_FOR may contain
4171 non-gimple expressions when the main index variable has had
4172 its address taken. This does not affect the loop itself
4173 because the header of an OMP_FOR is merely used to determine
4174 how to setup the parallel iteration. */
4178 if (!is_gimple_stmt (stmt))
4180 error ("is not a valid GIMPLE statement");
4184 addr = walk_tree (&stmt, verify_expr, NULL, NULL);
4187 debug_generic_stmt (addr);
4190 inform ("in statement");
4191 debug_generic_stmt (stmt);
4196 /* If the statement is marked as part of an EH region, then it is
4197 expected that the statement could throw. Verify that when we
4198 have optimizations that simplify statements such that we prove
4199 that they cannot throw, that we update other data structures
4201 if (lookup_stmt_eh_region (stmt) >= 0)
4203 if (!tree_could_throw_p (stmt))
4205 error ("statement marked for throw, but doesn%'t");
4208 if (!last_in_block && tree_can_throw_internal (stmt))
4210 error ("statement marked for throw in middle of block");
4218 debug_generic_stmt (stmt);
4223 /* Return true when the T can be shared. */
4226 tree_node_can_be_shared (tree t)
4228 if (IS_TYPE_OR_DECL_P (t)
4229 || is_gimple_min_invariant (t)
4230 || TREE_CODE (t) == SSA_NAME
4231 || t == error_mark_node
4232 || TREE_CODE (t) == IDENTIFIER_NODE)
4235 if (TREE_CODE (t) == CASE_LABEL_EXPR)
4238 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4239 && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4240 || TREE_CODE (t) == COMPONENT_REF
4241 || TREE_CODE (t) == REALPART_EXPR
4242 || TREE_CODE (t) == IMAGPART_EXPR)
4243 t = TREE_OPERAND (t, 0);
4252 /* Called via walk_trees. Verify tree sharing. */
4255 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
4257 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4259 if (tree_node_can_be_shared (*tp))
4261 *walk_subtrees = false;
4265 if (pointer_set_insert (visited, *tp))
4272 /* Helper function for verify_gimple_tuples. */
4275 verify_gimple_tuples_1 (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
4276 void *data ATTRIBUTE_UNUSED)
4278 switch (TREE_CODE (*tp))
4281 error ("unexpected non-tuple");
4291 /* Verify that there are no trees that should have been converted to
4292 gimple tuples. Return true if T contains a node that should have
4293 been converted to a gimple tuple, but hasn't. */
4296 verify_gimple_tuples (tree t)
4298 return walk_tree (&t, verify_gimple_tuples_1, NULL, NULL) != NULL;
4301 static bool eh_error_found;
4303 verify_eh_throw_stmt_node (void **slot, void *data)
4305 struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4306 struct pointer_set_t *visited = (struct pointer_set_t *) data;
4308 if (!pointer_set_contains (visited, node->stmt))
4310 error ("Dead STMT in EH table");
4311 debug_generic_stmt (node->stmt);
4312 eh_error_found = true;
4317 /* Verify the GIMPLE statement chain. */
4323 block_stmt_iterator bsi;
4325 struct pointer_set_t *visited, *visited_stmts;
4328 timevar_push (TV_TREE_STMT_VERIFY);
4329 visited = pointer_set_create ();
4330 visited_stmts = pointer_set_create ();
4337 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4339 int phi_num_args = PHI_NUM_ARGS (phi);
4341 pointer_set_insert (visited_stmts, phi);
4342 if (bb_for_stmt (phi) != bb)
4344 error ("bb_for_stmt (phi) is set to a wrong basic block");
4348 for (i = 0; i < phi_num_args; i++)
4350 tree t = PHI_ARG_DEF (phi, i);
4355 error ("missing PHI def");
4356 debug_generic_stmt (phi);
4360 /* Addressable variables do have SSA_NAMEs but they
4361 are not considered gimple values. */
4362 else if (TREE_CODE (t) != SSA_NAME
4363 && TREE_CODE (t) != FUNCTION_DECL
4364 && !is_gimple_min_invariant (t))
4366 error ("PHI def is not a GIMPLE value");
4367 debug_generic_stmt (phi);
4368 debug_generic_stmt (t);
4372 addr = walk_tree (&t, verify_node_sharing, visited, NULL);
4375 error ("incorrect sharing of tree nodes");
4376 debug_generic_stmt (phi);
4377 debug_generic_stmt (addr);
4383 for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
4385 tree stmt = bsi_stmt (bsi);
4387 pointer_set_insert (visited_stmts, stmt);
4388 err |= verify_gimple_tuples (stmt);
4390 if (bb_for_stmt (stmt) != bb)
4392 error ("bb_for_stmt (stmt) is set to a wrong basic block");
4397 err |= verify_stmt (stmt, bsi_end_p (bsi));
4398 addr = walk_tree (&stmt, verify_node_sharing, visited, NULL);
4401 error ("incorrect sharing of tree nodes");
4402 debug_generic_stmt (stmt);
4403 debug_generic_stmt (addr);
4408 eh_error_found = false;
4409 if (get_eh_throw_stmt_table (cfun))
4410 htab_traverse (get_eh_throw_stmt_table (cfun),
4411 verify_eh_throw_stmt_node,
4414 if (err | eh_error_found)
4415 internal_error ("verify_stmts failed");
4417 pointer_set_destroy (visited);
4418 pointer_set_destroy (visited_stmts);
4419 verify_histograms ();
4420 timevar_pop (TV_TREE_STMT_VERIFY);
4424 /* Verifies that the flow information is OK. */
4427 tree_verify_flow_info (void)
4431 block_stmt_iterator bsi;
4436 if (ENTRY_BLOCK_PTR->il.tree)
4438 error ("ENTRY_BLOCK has IL associated with it");
4442 if (EXIT_BLOCK_PTR->il.tree)
4444 error ("EXIT_BLOCK has IL associated with it");
4448 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4449 if (e->flags & EDGE_FALLTHRU)
4451 error ("fallthru to exit from bb %d", e->src->index);
4457 bool found_ctrl_stmt = false;
4461 /* Skip labels on the start of basic block. */
4462 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4464 tree prev_stmt = stmt;
4466 stmt = bsi_stmt (bsi);
4468 if (TREE_CODE (stmt) != LABEL_EXPR)
4471 if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
4473 error ("nonlocal label ");
4474 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4475 fprintf (stderr, " is not first in a sequence of labels in bb %d",
4480 if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
4483 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4484 fprintf (stderr, " to block does not match in bb %d",
4489 if (decl_function_context (LABEL_EXPR_LABEL (stmt))
4490 != current_function_decl)
4493 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4494 fprintf (stderr, " has incorrect context in bb %d",
4500 /* Verify that body of basic block BB is free of control flow. */
4501 for (; !bsi_end_p (bsi); bsi_next (&bsi))
4503 tree stmt = bsi_stmt (bsi);
4505 if (found_ctrl_stmt)
4507 error ("control flow in the middle of basic block %d",
4512 if (stmt_ends_bb_p (stmt))
4513 found_ctrl_stmt = true;
4515 if (TREE_CODE (stmt) == LABEL_EXPR)
4518 print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
4519 fprintf (stderr, " in the middle of basic block %d", bb->index);
4524 bsi = bsi_last (bb);
4525 if (bsi_end_p (bsi))
4528 stmt = bsi_stmt (bsi);
4530 err |= verify_eh_edges (stmt);
4532 if (is_ctrl_stmt (stmt))
4534 FOR_EACH_EDGE (e, ei, bb->succs)
4535 if (e->flags & EDGE_FALLTHRU)
4537 error ("fallthru edge after a control statement in bb %d",
4543 if (TREE_CODE (stmt) != COND_EXPR)
4545 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4546 after anything else but if statement. */
4547 FOR_EACH_EDGE (e, ei, bb->succs)
4548 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4550 error ("true/false edge after a non-COND_EXPR in bb %d",
4556 switch (TREE_CODE (stmt))
4563 if (COND_EXPR_THEN (stmt) != NULL_TREE
4564 || COND_EXPR_ELSE (stmt) != NULL_TREE)
4566 error ("COND_EXPR with code in branches at the end of bb %d",
4571 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4573 if (!true_edge || !false_edge
4574 || !(true_edge->flags & EDGE_TRUE_VALUE)
4575 || !(false_edge->flags & EDGE_FALSE_VALUE)
4576 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4577 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4578 || EDGE_COUNT (bb->succs) >= 3)
4580 error ("wrong outgoing edge flags at end of bb %d",
4588 if (simple_goto_p (stmt))
4590 error ("explicit goto at end of bb %d", bb->index);
4595 /* FIXME. We should double check that the labels in the
4596 destination blocks have their address taken. */
4597 FOR_EACH_EDGE (e, ei, bb->succs)
4598 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4599 | EDGE_FALSE_VALUE))
4600 || !(e->flags & EDGE_ABNORMAL))
4602 error ("wrong outgoing edge flags at end of bb %d",
4610 if (!single_succ_p (bb)
4611 || (single_succ_edge (bb)->flags
4612 & (EDGE_FALLTHRU | EDGE_ABNORMAL
4613 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4615 error ("wrong outgoing edge flags at end of bb %d", bb->index);
4618 if (single_succ (bb) != EXIT_BLOCK_PTR)
4620 error ("return edge does not point to exit in bb %d",
4633 vec = SWITCH_LABELS (stmt);
4634 n = TREE_VEC_LENGTH (vec);
4636 /* Mark all the destination basic blocks. */
4637 for (i = 0; i < n; ++i)
4639 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4640 basic_block label_bb = label_to_block (lab);
4642 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4643 label_bb->aux = (void *)1;
4646 /* Verify that the case labels are sorted. */
4647 prev = TREE_VEC_ELT (vec, 0);
4648 for (i = 1; i < n; ++i)
4650 tree c = TREE_VEC_ELT (vec, i);
4655 error ("found default case not at end of case vector");
4660 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4662 error ("case labels not sorted: ");
4663 print_generic_expr (stderr, prev, 0);
4664 fprintf (stderr," is greater than ");
4665 print_generic_expr (stderr, c, 0);
4666 fprintf (stderr," but comes before it.\n");
4671 /* VRP will remove the default case if it can prove it will
4672 never be executed. So do not verify there always exists
4673 a default case here. */
4675 FOR_EACH_EDGE (e, ei, bb->succs)
4679 error ("extra outgoing edge %d->%d",
4680 bb->index, e->dest->index);
4683 e->dest->aux = (void *)2;
4684 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4685 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4687 error ("wrong outgoing edge flags at end of bb %d",
4693 /* Check that we have all of them. */
4694 for (i = 0; i < n; ++i)
4696 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
4697 basic_block label_bb = label_to_block (lab);
4699 if (label_bb->aux != (void *)2)
4701 error ("missing edge %i->%i",
4702 bb->index, label_bb->index);
4707 FOR_EACH_EDGE (e, ei, bb->succs)
4708 e->dest->aux = (void *)0;
4715 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4716 verify_dominators (CDI_DOMINATORS);
4722 /* Updates phi nodes after creating a forwarder block joined
4723 by edge FALLTHRU. */
4726 tree_make_forwarder_block (edge fallthru)
4730 basic_block dummy, bb;
4731 tree phi, new_phi, var;
4733 dummy = fallthru->src;
4734 bb = fallthru->dest;
4736 if (single_pred_p (bb))
4739 /* If we redirected a branch we must create new PHI nodes at the
4741 for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
4743 var = PHI_RESULT (phi);
4744 new_phi = create_phi_node (var, bb);
4745 SSA_NAME_DEF_STMT (var) = new_phi;
4746 SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4747 add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
4750 /* Ensure that the PHI node chain is in the same order. */
4751 set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
4753 /* Add the arguments we have stored on edges. */
4754 FOR_EACH_EDGE (e, ei, bb->preds)
4759 flush_pending_stmts (e);
4764 /* Return a non-special label in the head of basic block BLOCK.
4765 Create one if it doesn't exist. */
4768 tree_block_label (basic_block bb)
4770 block_stmt_iterator i, s = bsi_start (bb);
4774 for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4776 stmt = bsi_stmt (i);
4777 if (TREE_CODE (stmt) != LABEL_EXPR)
4779 label = LABEL_EXPR_LABEL (stmt);
4780 if (!DECL_NONLOCAL (label))
4783 bsi_move_before (&i, &s);
4788 label = create_artificial_label ();
4789 stmt = build1 (LABEL_EXPR, void_type_node, label);
4790 bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4795 /* Attempt to perform edge redirection by replacing a possibly complex
4796 jump instruction by a goto or by removing the jump completely.
4797 This can apply only if all edges now point to the same block. The
4798 parameters and return values are equivalent to
4799 redirect_edge_and_branch. */
4802 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4804 basic_block src = e->src;
4805 block_stmt_iterator b;
4808 /* We can replace or remove a complex jump only when we have exactly
4810 if (EDGE_COUNT (src->succs) != 2
4811 /* Verify that all targets will be TARGET. Specifically, the
4812 edge that is not E must also go to TARGET. */
4813 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4819 stmt = bsi_stmt (b);
4821 if (TREE_CODE (stmt) == COND_EXPR
4822 || TREE_CODE (stmt) == SWITCH_EXPR)
4824 bsi_remove (&b, true);
4825 e = ssa_redirect_edge (e, target);
4826 e->flags = EDGE_FALLTHRU;
4834 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
4835 edge representing the redirected branch. */
4838 tree_redirect_edge_and_branch (edge e, basic_block dest)
4840 basic_block bb = e->src;
4841 block_stmt_iterator bsi;
4845 if (e->flags & EDGE_ABNORMAL)
4848 if (e->src != ENTRY_BLOCK_PTR
4849 && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4852 if (e->dest == dest)
4855 bsi = bsi_last (bb);
4856 stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4858 switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4861 /* For COND_EXPR, we only need to redirect the edge. */
4865 /* No non-abnormal edges should lead from a non-simple goto, and
4866 simple ones should be represented implicitly. */
4871 tree cases = get_cases_for_edge (e, stmt);
4872 tree label = tree_block_label (dest);
4874 /* If we have a list of cases associated with E, then use it
4875 as it's a lot faster than walking the entire case vector. */
4878 edge e2 = find_edge (e->src, dest);
4885 CASE_LABEL (cases) = label;
4886 cases = TREE_CHAIN (cases);
4889 /* If there was already an edge in the CFG, then we need
4890 to move all the cases associated with E to E2. */
4893 tree cases2 = get_cases_for_edge (e2, stmt);
4895 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4896 TREE_CHAIN (cases2) = first;
4901 tree vec = SWITCH_LABELS (stmt);
4902 size_t i, n = TREE_VEC_LENGTH (vec);
4904 for (i = 0; i < n; i++)
4906 tree elt = TREE_VEC_ELT (vec, i);
4908 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4909 CASE_LABEL (elt) = label;
4917 bsi_remove (&bsi, true);
4918 e->flags |= EDGE_FALLTHRU;
4923 case OMP_SECTIONS_SWITCH:
4925 /* The edges from OMP constructs can be simply redirected. */
4929 /* Otherwise it must be a fallthru edge, and we don't need to
4930 do anything besides redirecting it. */
4931 gcc_assert (e->flags & EDGE_FALLTHRU);
4935 /* Update/insert PHI nodes as necessary. */
4937 /* Now update the edges in the CFG. */
4938 e = ssa_redirect_edge (e, dest);
4943 /* Returns true if it is possible to remove edge E by redirecting
4944 it to the destination of the other edge from E->src. */
4947 tree_can_remove_branch_p (const_edge e)
4949 if (e->flags & EDGE_ABNORMAL)
4955 /* Simple wrapper, as we can always redirect fallthru edges. */
4958 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4960 e = tree_redirect_edge_and_branch (e, dest);
4967 /* Splits basic block BB after statement STMT (but at least after the
4968 labels). If STMT is NULL, BB is split just after the labels. */
4971 tree_split_block (basic_block bb, void *stmt)
4973 block_stmt_iterator bsi;
4974 tree_stmt_iterator tsi_tgt;
4980 new_bb = create_empty_bb (bb);
4982 /* Redirect the outgoing edges. */
4983 new_bb->succs = bb->succs;
4985 FOR_EACH_EDGE (e, ei, new_bb->succs)
4988 if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4991 /* Move everything from BSI to the new basic block. */
4992 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4994 act = bsi_stmt (bsi);
4995 if (TREE_CODE (act) == LABEL_EXPR)
5008 if (bsi_end_p (bsi))
5011 /* Split the statement list - avoid re-creating new containers as this
5012 brings ugly quadratic memory consumption in the inliner.
5013 (We are still quadratic since we need to update stmt BB pointers,
5015 list = tsi_split_statement_list_before (&bsi.tsi);
5016 set_bb_stmt_list (new_bb, list);
5017 for (tsi_tgt = tsi_start (list);
5018 !tsi_end_p (tsi_tgt); tsi_next (&tsi_tgt))
5019 change_bb_for_stmt (tsi_stmt (tsi_tgt), new_bb);
5025 /* Moves basic block BB after block AFTER. */
5028 tree_move_block_after (basic_block bb, basic_block after)
5030 if (bb->prev_bb == after)
5034 link_block (bb, after);
5040 /* Return true if basic_block can be duplicated. */
5043 tree_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5049 /* Create a duplicate of the basic block BB. NOTE: This does not
5050 preserve SSA form. */
5053 tree_duplicate_bb (basic_block bb)
5056 block_stmt_iterator bsi, bsi_tgt;
5059 new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5061 /* Copy the PHI nodes. We ignore PHI node arguments here because
5062 the incoming edges have not been setup yet. */
5063 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5065 tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
5066 create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
5069 /* Keep the chain of PHI nodes in the same order so that they can be
5070 updated by ssa_redirect_edge. */
5071 set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
5073 bsi_tgt = bsi_start (new_bb);
5074 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5076 def_operand_p def_p;
5077 ssa_op_iter op_iter;
5081 stmt = bsi_stmt (bsi);
5082 if (TREE_CODE (stmt) == LABEL_EXPR)
5085 /* Create a new copy of STMT and duplicate STMT's virtual
5087 copy = unshare_expr (stmt);
5088 bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
5089 copy_virtual_operands (copy, stmt);
5090 region = lookup_stmt_eh_region (stmt);
5092 add_stmt_to_eh_region (copy, region);
5093 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5095 /* Create new names for all the definitions created by COPY and
5096 add replacement mappings for each new name. */
5097 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5098 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5104 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5107 add_phi_args_after_copy_edge (edge e_copy)
5109 basic_block bb, bb_copy = e_copy->src, dest;
5112 tree phi, phi_copy, phi_next, def;
5114 if (!phi_nodes (e_copy->dest))
5117 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5119 if (e_copy->dest->flags & BB_DUPLICATED)
5120 dest = get_bb_original (e_copy->dest);
5122 dest = e_copy->dest;
5124 e = find_edge (bb, dest);
5127 /* During loop unrolling the target of the latch edge is copied.
5128 In this case we are not looking for edge to dest, but to
5129 duplicated block whose original was dest. */
5130 FOR_EACH_EDGE (e, ei, bb->succs)
5132 if ((e->dest->flags & BB_DUPLICATED)
5133 && get_bb_original (e->dest) == dest)
5137 gcc_assert (e != NULL);
5140 for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
5142 phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
5144 phi_next = PHI_CHAIN (phi);
5145 def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5146 add_phi_arg (phi_copy, def, e_copy);
5151 /* Basic block BB_COPY was created by code duplication. Add phi node
5152 arguments for edges going out of BB_COPY. The blocks that were
5153 duplicated have BB_DUPLICATED set. */
5156 add_phi_args_after_copy_bb (basic_block bb_copy)
5161 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5163 add_phi_args_after_copy_edge (e_copy);
5167 /* Blocks in REGION_COPY array of length N_REGION were created by
5168 duplication of basic blocks. Add phi node arguments for edges
5169 going from these blocks. If E_COPY is not NULL, also add
5170 phi node arguments for its destination.*/
5173 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5178 for (i = 0; i < n_region; i++)
5179 region_copy[i]->flags |= BB_DUPLICATED;
5181 for (i = 0; i < n_region; i++)
5182 add_phi_args_after_copy_bb (region_copy[i]);
5184 add_phi_args_after_copy_edge (e_copy);
5186 for (i = 0; i < n_region; i++)
5187 region_copy[i]->flags &= ~BB_DUPLICATED;
5190 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5191 important exit edge EXIT. By important we mean that no SSA name defined
5192 inside region is live over the other exit edges of the region. All entry
5193 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5194 to the duplicate of the region. SSA form, dominance and loop information
5195 is updated. The new basic blocks are stored to REGION_COPY in the same
5196 order as they had in REGION, provided that REGION_COPY is not NULL.
5197 The function returns false if it is unable to copy the region,
5201 tree_duplicate_sese_region (edge entry, edge exit,
5202 basic_block *region, unsigned n_region,
5203 basic_block *region_copy)
5206 bool free_region_copy = false, copying_header = false;
5207 struct loop *loop = entry->dest->loop_father;
5209 VEC (basic_block, heap) *doms;
5211 int total_freq = 0, entry_freq = 0;
5212 gcov_type total_count = 0, entry_count = 0;
5214 if (!can_copy_bbs_p (region, n_region))
5217 /* Some sanity checking. Note that we do not check for all possible
5218 missuses of the functions. I.e. if you ask to copy something weird,
5219 it will work, but the state of structures probably will not be
5221 for (i = 0; i < n_region; i++)
5223 /* We do not handle subloops, i.e. all the blocks must belong to the
5225 if (region[i]->loop_father != loop)
5228 if (region[i] != entry->dest
5229 && region[i] == loop->header)
5233 set_loop_copy (loop, loop);
5235 /* In case the function is used for loop header copying (which is the primary
5236 use), ensure that EXIT and its copy will be new latch and entry edges. */
5237 if (loop->header == entry->dest)
5239 copying_header = true;
5240 set_loop_copy (loop, loop_outer (loop));
5242 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5245 for (i = 0; i < n_region; i++)
5246 if (region[i] != exit->src
5247 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5253 region_copy = XNEWVEC (basic_block, n_region);
5254 free_region_copy = true;
5257 gcc_assert (!need_ssa_update_p ());
5259 /* Record blocks outside the region that are dominated by something
5262 initialize_original_copy_tables ();
5264 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5266 if (entry->dest->count)
5268 total_count = entry->dest->count;
5269 entry_count = entry->count;
5270 /* Fix up corner cases, to avoid division by zero or creation of negative
5272 if (entry_count > total_count)
5273 entry_count = total_count;
5277 total_freq = entry->dest->frequency;
5278 entry_freq = EDGE_FREQUENCY (entry);
5279 /* Fix up corner cases, to avoid division by zero or creation of negative
5281 if (total_freq == 0)
5283 else if (entry_freq > total_freq)
5284 entry_freq = total_freq;
5287 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5288 split_edge_bb_loc (entry));
5291 scale_bbs_frequencies_gcov_type (region, n_region,
5292 total_count - entry_count,
5294 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5299 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5301 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5306 loop->header = exit->dest;
5307 loop->latch = exit->src;
5310 /* Redirect the entry and add the phi node arguments. */
5311 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5312 gcc_assert (redirected != NULL);
5313 flush_pending_stmts (entry);
5315 /* Concerning updating of dominators: We must recount dominators
5316 for entry block and its copy. Anything that is outside of the
5317 region, but was dominated by something inside needs recounting as
5319 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5320 VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5321 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5322 VEC_free (basic_block, heap, doms);
5324 /* Add the other PHI node arguments. */
5325 add_phi_args_after_copy (region_copy, n_region, NULL);
5327 /* Update the SSA web. */
5328 update_ssa (TODO_update_ssa);
5330 if (free_region_copy)
5333 free_original_copy_tables ();
5337 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
5338 are stored to REGION_COPY in the same order in that they appear
5339 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
5340 the region, EXIT an exit from it. The condition guarding EXIT
5341 is moved to ENTRY. Returns true if duplication succeeds, false
5367 tree_duplicate_sese_tail (edge entry, edge exit,
5368 basic_block *region, unsigned n_region,
5369 basic_block *region_copy)
5372 bool free_region_copy = false;
5373 struct loop *loop = exit->dest->loop_father;
5374 struct loop *orig_loop = entry->dest->loop_father;
5375 basic_block switch_bb, entry_bb, nentry_bb;
5376 VEC (basic_block, heap) *doms;
5377 int total_freq = 0, exit_freq = 0;
5378 gcov_type total_count = 0, exit_count = 0;
5379 edge exits[2], nexits[2], e;
5380 block_stmt_iterator bsi;
5384 gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5386 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5388 if (!can_copy_bbs_p (region, n_region))
5391 /* Some sanity checking. Note that we do not check for all possible
5392 missuses of the functions. I.e. if you ask to copy something weird
5393 (e.g., in the example, if there is a jump from inside to the middle
5394 of some_code, or come_code defines some of the values used in cond)
5395 it will work, but the resulting code will not be correct. */
5396 for (i = 0; i < n_region; i++)
5398 /* We do not handle subloops, i.e. all the blocks must belong to the
5400 if (region[i]->loop_father != orig_loop)
5403 if (region[i] == orig_loop->latch)
5407 initialize_original_copy_tables ();
5408 set_loop_copy (orig_loop, loop);
5412 region_copy = XNEWVEC (basic_block, n_region);
5413 free_region_copy = true;
5416 gcc_assert (!need_ssa_update_p ());
5418 /* Record blocks outside the region that are dominated by something
5420 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5422 if (exit->src->count)
5424 total_count = exit->src->count;
5425 exit_count = exit->count;
5426 /* Fix up corner cases, to avoid division by zero or creation of negative
5428 if (exit_count > total_count)
5429 exit_count = total_count;
5433 total_freq = exit->src->frequency;
5434 exit_freq = EDGE_FREQUENCY (exit);
5435 /* Fix up corner cases, to avoid division by zero or creation of negative
5437 if (total_freq == 0)
5439 if (exit_freq > total_freq)
5440 exit_freq = total_freq;
5443 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5444 split_edge_bb_loc (exit));
5447 scale_bbs_frequencies_gcov_type (region, n_region,
5448 total_count - exit_count,
5450 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5455 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5457 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5460 /* Create the switch block, and put the exit condition to it. */
5461 entry_bb = entry->dest;
5462 nentry_bb = get_bb_copy (entry_bb);
5463 if (!last_stmt (entry->src)
5464 || !stmt_ends_bb_p (last_stmt (entry->src)))
5465 switch_bb = entry->src;
5467 switch_bb = split_edge (entry);
5468 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5470 bsi = bsi_last (switch_bb);
5471 cond = last_stmt (exit->src);
5472 gcc_assert (TREE_CODE (cond) == COND_EXPR);
5473 bsi_insert_after (&bsi, unshare_expr (cond), BSI_NEW_STMT);
5475 sorig = single_succ_edge (switch_bb);
5476 sorig->flags = exits[1]->flags;
5477 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5479 /* Register the new edge from SWITCH_BB in loop exit lists. */
5480 rescan_loop_exit (snew, true, false);
5482 /* Add the PHI node arguments. */
5483 add_phi_args_after_copy (region_copy, n_region, snew);
5485 /* Get rid of now superfluous conditions and associated edges (and phi node
5487 e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5488 PENDING_STMT (e) = NULL_TREE;
5489 e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5490 PENDING_STMT (e) = NULL_TREE;
5492 /* Anything that is outside of the region, but was dominated by something
5493 inside needs to update dominance info. */
5494 iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5495 VEC_free (basic_block, heap, doms);
5497 /* Update the SSA web. */
5498 update_ssa (TODO_update_ssa);
5500 if (free_region_copy)
5503 free_original_copy_tables ();
5508 DEF_VEC_P(basic_block);
5509 DEF_VEC_ALLOC_P(basic_block,heap);
5512 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
5513 adding blocks when the dominator traversal reaches EXIT. This
5514 function silently assumes that ENTRY strictly dominates EXIT. */
5517 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5518 VEC(basic_block,heap) **bbs_p)
5522 for (son = first_dom_son (CDI_DOMINATORS, entry);
5524 son = next_dom_son (CDI_DOMINATORS, son))
5526 VEC_safe_push (basic_block, heap, *bbs_p, son);
5528 gather_blocks_in_sese_region (son, exit, bbs_p);
5532 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5533 The duplicates are recorded in VARS_MAP. */
5536 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5539 tree t = *tp, new_t;
5540 struct function *f = DECL_STRUCT_FUNCTION (to_context);
5543 if (DECL_CONTEXT (t) == to_context)
5546 loc = pointer_map_contains (vars_map, t);
5550 loc = pointer_map_insert (vars_map, t);
5554 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5555 f->local_decls = tree_cons (NULL_TREE, new_t, f->local_decls);
5559 gcc_assert (TREE_CODE (t) == CONST_DECL);
5560 new_t = copy_node (t);
5562 DECL_CONTEXT (new_t) = to_context;
5572 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5573 VARS_MAP maps old ssa names and var_decls to the new ones. */
5576 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5580 tree new_name, decl = SSA_NAME_VAR (name);
5582 gcc_assert (is_gimple_reg (name));
5584 loc = pointer_map_contains (vars_map, name);
5588 replace_by_duplicate_decl (&decl, vars_map, to_context);
5590 push_cfun (DECL_STRUCT_FUNCTION (to_context));
5591 if (gimple_in_ssa_p (cfun))
5592 add_referenced_var (decl);
5594 new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5595 if (SSA_NAME_IS_DEFAULT_DEF (name))
5596 set_default_def (decl, new_name);
5599 loc = pointer_map_insert (vars_map, name);
5613 struct pointer_map_t *vars_map;
5614 htab_t new_label_map;
5618 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
5619 contained in *TP and change the DECL_CONTEXT of every local
5620 variable referenced in *TP. */
5623 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
5625 struct move_stmt_d *p = (struct move_stmt_d *) data;
5629 && (EXPR_P (t) || GIMPLE_STMT_P (t)))
5630 TREE_BLOCK (t) = p->block;
5632 if (OMP_DIRECTIVE_P (t)
5633 && TREE_CODE (t) != OMP_RETURN
5634 && TREE_CODE (t) != OMP_CONTINUE)
5636 /* Do not remap variables inside OMP directives. Variables
5637 referenced in clauses and directive header belong to the
5638 parent function and should not be moved into the child
5640 bool save_remap_decls_p = p->remap_decls_p;
5641 p->remap_decls_p = false;
5644 walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
5646 p->remap_decls_p = save_remap_decls_p;
5648 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5650 if (TREE_CODE (t) == SSA_NAME)
5651 *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5652 else if (TREE_CODE (t) == LABEL_DECL)
5654 if (p->new_label_map)
5656 struct tree_map in, *out;
5658 out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5663 DECL_CONTEXT (t) = p->to_context;
5665 else if (p->remap_decls_p)
5667 /* Replace T with its duplicate. T should no longer appear in the
5668 parent function, so this looks wasteful; however, it may appear
5669 in referenced_vars, and more importantly, as virtual operands of
5670 statements, and in alias lists of other variables. It would be
5671 quite difficult to expunge it from all those places. ??? It might
5672 suffice to do this for addressable variables. */
5673 if ((TREE_CODE (t) == VAR_DECL
5674 && !is_global_var (t))
5675 || TREE_CODE (t) == CONST_DECL)
5676 replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5679 && gimple_in_ssa_p (cfun))
5681 push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5682 add_referenced_var (*tp);
5688 else if (TYPE_P (t))
5694 /* Marks virtual operands of all statements in basic blocks BBS for
5698 mark_virtual_ops_in_bb (basic_block bb)
5701 block_stmt_iterator bsi;
5703 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5704 mark_virtual_ops_for_renaming (phi);
5706 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
5707 mark_virtual_ops_for_renaming (bsi_stmt (bsi));
5710 /* Marks virtual operands of all statements in basic blocks BBS for
5714 mark_virtual_ops_in_region (VEC (basic_block,heap) *bbs)
5719 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5720 mark_virtual_ops_in_bb (bb);
5723 /* Move basic block BB from function CFUN to function DEST_FN. The
5724 block is moved out of the original linked list and placed after
5725 block AFTER in the new list. Also, the block is removed from the
5726 original array of blocks and placed in DEST_FN's array of blocks.
5727 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5728 updated to reflect the moved edges.
5730 The local variables are remapped to new instances, VARS_MAP is used
5731 to record the mapping. */
5734 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5735 basic_block after, bool update_edge_count_p,
5736 struct pointer_map_t *vars_map, htab_t new_label_map,
5739 struct control_flow_graph *cfg;
5742 block_stmt_iterator si;
5743 struct move_stmt_d d;
5744 unsigned old_len, new_len;
5747 /* Remove BB from dominance structures. */
5748 delete_from_dominance_info (CDI_DOMINATORS, bb);
5750 remove_bb_from_loops (bb);
5752 /* Link BB to the new linked list. */
5753 move_block_after (bb, after);
5755 /* Update the edge count in the corresponding flowgraphs. */
5756 if (update_edge_count_p)
5757 FOR_EACH_EDGE (e, ei, bb->succs)
5759 cfun->cfg->x_n_edges--;
5760 dest_cfun->cfg->x_n_edges++;
5763 /* Remove BB from the original basic block array. */
5764 VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5765 cfun->cfg->x_n_basic_blocks--;
5767 /* Grow DEST_CFUN's basic block array if needed. */
5768 cfg = dest_cfun->cfg;
5769 cfg->x_n_basic_blocks++;
5770 if (bb->index >= cfg->x_last_basic_block)
5771 cfg->x_last_basic_block = bb->index + 1;
5773 old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5774 if ((unsigned) cfg->x_last_basic_block >= old_len)
5776 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5777 VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5781 VEC_replace (basic_block, cfg->x_basic_block_info,
5784 /* Remap the variables in phi nodes. */
5785 for (phi = phi_nodes (bb); phi; phi = next_phi)
5788 tree op = PHI_RESULT (phi);
5791 next_phi = PHI_CHAIN (phi);
5792 if (!is_gimple_reg (op))
5794 /* Remove the phi nodes for virtual operands (alias analysis will be
5795 run for the new function, anyway). */
5796 remove_phi_node (phi, NULL, true);
5800 SET_PHI_RESULT (phi, replace_ssa_name (op, vars_map, dest_cfun->decl));
5801 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5803 op = USE_FROM_PTR (use);
5804 if (TREE_CODE (op) == SSA_NAME)
5805 SET_USE (use, replace_ssa_name (op, vars_map, dest_cfun->decl));
5809 /* The statements in BB need to be associated with a new TREE_BLOCK.
5810 Labels need to be associated with a new label-to-block map. */
5811 memset (&d, 0, sizeof (d));
5812 d.vars_map = vars_map;
5813 d.from_context = cfun->decl;
5814 d.to_context = dest_cfun->decl;
5815 d.new_label_map = new_label_map;
5817 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5819 tree stmt = bsi_stmt (si);
5822 d.remap_decls_p = true;
5823 if (TREE_BLOCK (stmt))
5824 d.block = DECL_INITIAL (dest_cfun->decl);
5826 walk_tree (&stmt, move_stmt_r, &d, NULL);
5828 if (TREE_CODE (stmt) == LABEL_EXPR)
5830 tree label = LABEL_EXPR_LABEL (stmt);
5831 int uid = LABEL_DECL_UID (label);
5833 gcc_assert (uid > -1);
5835 old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5836 if (old_len <= (unsigned) uid)
5838 new_len = 3 * uid / 2;
5839 VEC_safe_grow_cleared (basic_block, gc,
5840 cfg->x_label_to_block_map, new_len);
5843 VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5844 VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5846 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5848 if (uid >= dest_cfun->cfg->last_label_uid)
5849 dest_cfun->cfg->last_label_uid = uid + 1;
5851 else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
5852 TREE_OPERAND (stmt, 0) =
5853 build_int_cst (NULL_TREE,
5854 TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
5857 region = lookup_stmt_eh_region (stmt);
5860 add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
5861 remove_stmt_from_eh_region (stmt);
5862 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5863 gimple_remove_stmt_histograms (cfun, stmt);
5866 /* We cannot leave any operands allocated from the operand caches of
5867 the current function. */
5868 free_stmt_operands (stmt);
5869 push_cfun (dest_cfun);
5875 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5876 the outermost EH region. Use REGION as the incoming base EH region. */
5879 find_outermost_region_in_block (struct function *src_cfun,
5880 basic_block bb, int region)
5882 block_stmt_iterator si;
5884 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5886 tree stmt = bsi_stmt (si);
5889 if (TREE_CODE (stmt) == RESX_EXPR)
5890 stmt_region = TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0));
5892 stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
5893 if (stmt_region > 0)
5896 region = stmt_region;
5897 else if (stmt_region != region)
5899 region = eh_region_outermost (src_cfun, stmt_region, region);
5900 gcc_assert (region != -1);
5909 new_label_mapper (tree decl, void *data)
5911 htab_t hash = (htab_t) data;
5915 gcc_assert (TREE_CODE (decl) == LABEL_DECL);
5917 m = xmalloc (sizeof (struct tree_map));
5918 m->hash = DECL_UID (decl);
5919 m->base.from = decl;
5920 m->to = create_artificial_label ();
5921 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
5922 if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
5923 cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
5925 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
5926 gcc_assert (*slot == NULL);
5933 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5934 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
5935 single basic block in the original CFG and the new basic block is
5936 returned. DEST_CFUN must not have a CFG yet.
5938 Note that the region need not be a pure SESE region. Blocks inside
5939 the region may contain calls to abort/exit. The only restriction
5940 is that ENTRY_BB should be the only entry point and it must
5943 All local variables referenced in the region are assumed to be in
5944 the corresponding BLOCK_VARS and unexpanded variable lists
5945 associated with DEST_CFUN. */
5948 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
5949 basic_block exit_bb)
5951 VEC(basic_block,heap) *bbs, *dom_bbs;
5952 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
5953 basic_block after, bb, *entry_pred, *exit_succ, abb;
5954 struct function *saved_cfun = cfun;
5955 int *entry_flag, *exit_flag, eh_offset;
5956 unsigned *entry_prob, *exit_prob;
5957 unsigned i, num_entry_edges, num_exit_edges;
5960 htab_t new_label_map;
5961 struct pointer_map_t *vars_map;
5962 struct loop *loop = entry_bb->loop_father;
5964 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5966 gcc_assert (entry_bb != exit_bb
5968 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
5970 /* Collect all the blocks in the region. Manually add ENTRY_BB
5971 because it won't be added by dfs_enumerate_from. */
5973 VEC_safe_push (basic_block, heap, bbs, entry_bb);
5974 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5976 /* The blocks that used to be dominated by something in BBS will now be
5977 dominated by the new block. */
5978 dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
5979 VEC_address (basic_block, bbs),
5980 VEC_length (basic_block, bbs));
5982 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
5983 the predecessor edges to ENTRY_BB and the successor edges to
5984 EXIT_BB so that we can re-attach them to the new basic block that
5985 will replace the region. */
5986 num_entry_edges = EDGE_COUNT (entry_bb->preds);
5987 entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
5988 entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
5989 entry_prob = XNEWVEC (unsigned, num_entry_edges);
5991 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
5993 entry_prob[i] = e->probability;
5994 entry_flag[i] = e->flags;
5995 entry_pred[i++] = e->src;
6001 num_exit_edges = EDGE_COUNT (exit_bb->succs);
6002 exit_succ = (basic_block *) xcalloc (num_exit_edges,
6003 sizeof (basic_block));
6004 exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6005 exit_prob = XNEWVEC (unsigned, num_exit_edges);
6007 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6009 exit_prob[i] = e->probability;
6010 exit_flag[i] = e->flags;
6011 exit_succ[i++] = e->dest;
6023 /* Switch context to the child function to initialize DEST_FN's CFG. */
6024 gcc_assert (dest_cfun->cfg == NULL);
6025 push_cfun (dest_cfun);
6027 init_empty_tree_cfg ();
6029 /* Initialize EH information for the new function. */
6031 new_label_map = NULL;
6036 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6037 region = find_outermost_region_in_block (saved_cfun, bb, region);
6039 init_eh_for_function ();
6042 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6043 eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
6044 new_label_map, region, 0);
6050 /* The ssa form for virtual operands in the source function will have to
6051 be repaired. We do not care for the real operands -- the sese region
6052 must be closed with respect to those. */
6053 mark_virtual_ops_in_region (bbs);
6055 /* Move blocks from BBS into DEST_CFUN. */
6056 gcc_assert (VEC_length (basic_block, bbs) >= 2);
6057 after = dest_cfun->cfg->x_entry_block_ptr;
6058 vars_map = pointer_map_create ();
6059 for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6061 /* No need to update edge counts on the last block. It has
6062 already been updated earlier when we detached the region from
6063 the original CFG. */
6064 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_map,
6065 new_label_map, eh_offset);
6070 htab_delete (new_label_map);
6071 pointer_map_destroy (vars_map);
6073 /* Rewire the entry and exit blocks. The successor to the entry
6074 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6075 the child function. Similarly, the predecessor of DEST_FN's
6076 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
6077 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6078 various CFG manipulation function get to the right CFG.
6080 FIXME, this is silly. The CFG ought to become a parameter to
6082 push_cfun (dest_cfun);
6083 make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6085 make_edge (exit_bb, EXIT_BLOCK_PTR, 0);
6088 /* Back in the original function, the SESE region has disappeared,
6089 create a new basic block in its place. */
6090 bb = create_empty_bb (entry_pred[0]);
6092 add_bb_to_loop (bb, loop);
6093 for (i = 0; i < num_entry_edges; i++)
6095 e = make_edge (entry_pred[i], bb, entry_flag[i]);
6096 e->probability = entry_prob[i];
6099 for (i = 0; i < num_exit_edges; i++)
6101 e = make_edge (bb, exit_succ[i], exit_flag[i]);
6102 e->probability = exit_prob[i];
6105 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6106 for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
6107 set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6108 VEC_free (basic_block, heap, dom_bbs);
6119 VEC_free (basic_block, heap, bbs);
6125 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
6128 dump_function_to_file (tree fn, FILE *file, int flags)
6130 tree arg, vars, var;
6131 struct function *dsf;
6132 bool ignore_topmost_bind = false, any_var = false;
6136 fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6138 arg = DECL_ARGUMENTS (fn);
6141 print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6142 fprintf (file, " ");
6143 print_generic_expr (file, arg, dump_flags);
6144 if (TREE_CHAIN (arg))
6145 fprintf (file, ", ");
6146 arg = TREE_CHAIN (arg);
6148 fprintf (file, ")\n");
6150 dsf = DECL_STRUCT_FUNCTION (fn);
6151 if (dsf && (flags & TDF_DETAILS))
6152 dump_eh_tree (file, dsf);
6154 if (flags & TDF_RAW)
6156 dump_node (fn, TDF_SLIM | flags, file);
6160 /* Switch CFUN to point to FN. */
6161 push_cfun (DECL_STRUCT_FUNCTION (fn));
6163 /* When GIMPLE is lowered, the variables are no longer available in
6164 BIND_EXPRs, so display them separately. */
6165 if (cfun && cfun->decl == fn && cfun->local_decls)
6167 ignore_topmost_bind = true;
6169 fprintf (file, "{\n");
6170 for (vars = cfun->local_decls; vars; vars = TREE_CHAIN (vars))
6172 var = TREE_VALUE (vars);
6174 print_generic_decl (file, var, flags);
6175 fprintf (file, "\n");
6181 if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6183 /* Make a CFG based dump. */
6184 check_bb_profile (ENTRY_BLOCK_PTR, file);
6185 if (!ignore_topmost_bind)
6186 fprintf (file, "{\n");
6188 if (any_var && n_basic_blocks)
6189 fprintf (file, "\n");
6192 dump_generic_bb (file, bb, 2, flags);
6194 fprintf (file, "}\n");
6195 check_bb_profile (EXIT_BLOCK_PTR, file);
6201 /* Make a tree based dump. */
6202 chain = DECL_SAVED_TREE (fn);
6204 if (chain && TREE_CODE (chain) == BIND_EXPR)
6206 if (ignore_topmost_bind)
6208 chain = BIND_EXPR_BODY (chain);
6216 if (!ignore_topmost_bind)
6217 fprintf (file, "{\n");
6222 fprintf (file, "\n");
6224 print_generic_stmt_indented (file, chain, flags, indent);
6225 if (ignore_topmost_bind)
6226 fprintf (file, "}\n");
6229 fprintf (file, "\n\n");
6236 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
6239 debug_function (tree fn, int flags)
6241 dump_function_to_file (fn, stderr, flags);
6245 /* Print on FILE the indexes for the predecessors of basic_block BB. */
6248 print_pred_bbs (FILE *file, basic_block bb)
6253 FOR_EACH_EDGE (e, ei, bb->preds)
6254 fprintf (file, "bb_%d ", e->src->index);
6258 /* Print on FILE the indexes for the successors of basic_block BB. */
6261 print_succ_bbs (FILE *file, basic_block bb)
6266 FOR_EACH_EDGE (e, ei, bb->succs)
6267 fprintf (file, "bb_%d ", e->dest->index);
6270 /* Print to FILE the basic block BB following the VERBOSITY level. */
6273 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6275 char *s_indent = (char *) alloca ((size_t) indent + 1);
6276 memset ((void *) s_indent, ' ', (size_t) indent);
6277 s_indent[indent] = '\0';
6279 /* Print basic_block's header. */
6282 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index);
6283 print_pred_bbs (file, bb);
6284 fprintf (file, "}, succs = {");
6285 print_succ_bbs (file, bb);
6286 fprintf (file, "})\n");
6289 /* Print basic_block's body. */
6292 fprintf (file, "%s {\n", s_indent);
6293 tree_dump_bb (bb, file, indent + 4);
6294 fprintf (file, "%s }\n", s_indent);
6298 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6300 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
6301 VERBOSITY level this outputs the contents of the loop, or just its
6305 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6313 s_indent = (char *) alloca ((size_t) indent + 1);
6314 memset ((void *) s_indent, ' ', (size_t) indent);
6315 s_indent[indent] = '\0';
6317 /* Print loop's header. */
6318 fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6319 loop->num, loop->header->index, loop->latch->index);
6320 fprintf (file, ", niter = ");
6321 print_generic_expr (file, loop->nb_iterations, 0);
6323 if (loop->any_upper_bound)
6325 fprintf (file, ", upper_bound = ");
6326 dump_double_int (file, loop->nb_iterations_upper_bound, true);
6329 if (loop->any_estimate)
6331 fprintf (file, ", estimate = ");
6332 dump_double_int (file, loop->nb_iterations_estimate, true);
6334 fprintf (file, ")\n");
6336 /* Print loop's body. */
6339 fprintf (file, "%s{\n", s_indent);
6341 if (bb->loop_father == loop)
6342 print_loops_bb (file, bb, indent, verbosity);
6344 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6345 fprintf (file, "%s}\n", s_indent);
6349 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6350 spaces. Following VERBOSITY level this outputs the contents of the
6351 loop, or just its structure. */
6354 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6359 print_loop (file, loop, indent, verbosity);
6360 print_loop_and_siblings (file, loop->next, indent, verbosity);
6363 /* Follow a CFG edge from the entry point of the program, and on entry
6364 of a loop, pretty print the loop structure on FILE. */
6367 print_loops (FILE *file, int verbosity)
6371 bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
6372 if (bb && bb->loop_father)
6373 print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6377 /* Debugging loops structure at tree level, at some VERBOSITY level. */
6380 debug_loops (int verbosity)
6382 print_loops (stderr, verbosity);
6385 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
6388 debug_loop (struct loop *loop, int verbosity)
6390 print_loop (stderr, loop, 0, verbosity);
6393 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6397 debug_loop_num (unsigned num, int verbosity)
6399 debug_loop (get_loop (num), verbosity);
6402 /* Return true if BB ends with a call, possibly followed by some
6403 instructions that must stay with the call. Return false,
6407 tree_block_ends_with_call_p (basic_block bb)
6409 block_stmt_iterator bsi = bsi_last (bb);
6410 return get_call_expr_in (bsi_stmt (bsi)) != NULL;
6414 /* Return true if BB ends with a conditional branch. Return false,
6418 tree_block_ends_with_condjump_p (const_basic_block bb)
6420 /* This CONST_CAST is okay because last_stmt doesn't modify its
6421 argument and the return value is not modified. */
6422 const_tree stmt = last_stmt (CONST_CAST_BB(bb));
6423 return (stmt && TREE_CODE (stmt) == COND_EXPR);
6427 /* Return true if we need to add fake edge to exit at statement T.
6428 Helper function for tree_flow_call_edges_add. */
6431 need_fake_edge_p (tree t)
6433 tree call, fndecl = NULL_TREE;
6436 /* NORETURN and LONGJMP calls already have an edge to exit.
6437 CONST and PURE calls do not need one.
6438 We don't currently check for CONST and PURE here, although
6439 it would be a good idea, because those attributes are
6440 figured out from the RTL in mark_constant_function, and
6441 the counter incrementation code from -fprofile-arcs
6442 leads to different results from -fbranch-probabilities. */
6443 call = get_call_expr_in (t);
6446 fndecl = get_callee_fndecl (call);
6447 call_flags = call_expr_flags (call);
6450 if (call && fndecl && DECL_BUILT_IN (fndecl)
6451 && (call_flags & ECF_NOTHROW)
6452 && !(call_flags & ECF_NORETURN)
6453 && !(call_flags & ECF_RETURNS_TWICE))
6456 if (call && !(call_flags & ECF_NORETURN))
6459 if (TREE_CODE (t) == ASM_EXPR
6460 && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
6467 /* Add fake edges to the function exit for any non constant and non
6468 noreturn calls, volatile inline assembly in the bitmap of blocks
6469 specified by BLOCKS or to the whole CFG if BLOCKS is zero. Return
6470 the number of blocks that were split.
6472 The goal is to expose cases in which entering a basic block does
6473 not imply that all subsequent instructions must be executed. */
6476 tree_flow_call_edges_add (sbitmap blocks)
6479 int blocks_split = 0;
6480 int last_bb = last_basic_block;
6481 bool check_last_block = false;
6483 if (n_basic_blocks == NUM_FIXED_BLOCKS)
6487 check_last_block = true;
6489 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6491 /* In the last basic block, before epilogue generation, there will be
6492 a fallthru edge to EXIT. Special care is required if the last insn
6493 of the last basic block is a call because make_edge folds duplicate
6494 edges, which would result in the fallthru edge also being marked
6495 fake, which would result in the fallthru edge being removed by
6496 remove_fake_edges, which would result in an invalid CFG.
6498 Moreover, we can't elide the outgoing fake edge, since the block
6499 profiler needs to take this into account in order to solve the minimal
6500 spanning tree in the case that the call doesn't return.
6502 Handle this by adding a dummy instruction in a new last basic block. */
6503 if (check_last_block)
6505 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6506 block_stmt_iterator bsi = bsi_last (bb);
6508 if (!bsi_end_p (bsi))
6511 if (t && need_fake_edge_p (t))
6515 e = find_edge (bb, EXIT_BLOCK_PTR);
6518 bsi_insert_on_edge (e, build_empty_stmt ());
6519 bsi_commit_edge_inserts ();
6524 /* Now add fake edges to the function exit for any non constant
6525 calls since there is no way that we can determine if they will
6527 for (i = 0; i < last_bb; i++)
6529 basic_block bb = BASIC_BLOCK (i);
6530 block_stmt_iterator bsi;
6531 tree stmt, last_stmt;
6536 if (blocks && !TEST_BIT (blocks, i))
6539 bsi = bsi_last (bb);
6540 if (!bsi_end_p (bsi))
6542 last_stmt = bsi_stmt (bsi);
6545 stmt = bsi_stmt (bsi);
6546 if (need_fake_edge_p (stmt))
6549 /* The handling above of the final block before the
6550 epilogue should be enough to verify that there is
6551 no edge to the exit block in CFG already.
6552 Calling make_edge in such case would cause us to
6553 mark that edge as fake and remove it later. */
6554 #ifdef ENABLE_CHECKING
6555 if (stmt == last_stmt)
6557 e = find_edge (bb, EXIT_BLOCK_PTR);
6558 gcc_assert (e == NULL);
6562 /* Note that the following may create a new basic block
6563 and renumber the existing basic blocks. */
6564 if (stmt != last_stmt)
6566 e = split_block (bb, stmt);
6570 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6574 while (!bsi_end_p (bsi));
6579 verify_flow_info ();
6581 return blocks_split;
6584 /* Purge dead abnormal call edges from basic block BB. */
6587 tree_purge_dead_abnormal_call_edges (basic_block bb)
6589 bool changed = tree_purge_dead_eh_edges (bb);
6591 if (current_function_has_nonlocal_label)
6593 tree stmt = last_stmt (bb);
6597 if (!(stmt && tree_can_make_abnormal_goto (stmt)))
6598 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6600 if (e->flags & EDGE_ABNORMAL)
6609 /* See tree_purge_dead_eh_edges below. */
6611 free_dominance_info (CDI_DOMINATORS);
6617 /* Stores all basic blocks dominated by BB to DOM_BBS. */
6620 get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
6624 VEC_safe_push (basic_block, heap, *dom_bbs, bb);
6625 for (son = first_dom_son (CDI_DOMINATORS, bb);
6627 son = next_dom_son (CDI_DOMINATORS, son))
6628 get_all_dominated_blocks (son, dom_bbs);
6631 /* Removes edge E and all the blocks dominated by it, and updates dominance
6632 information. The IL in E->src needs to be updated separately.
6633 If dominance info is not available, only the edge E is removed.*/
6636 remove_edge_and_dominated_blocks (edge e)
6638 VEC (basic_block, heap) *bbs_to_remove = NULL;
6639 VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6643 bool none_removed = false;
6645 basic_block bb, dbb;
6648 if (!dom_info_available_p (CDI_DOMINATORS))
6654 /* No updating is needed for edges to exit. */
6655 if (e->dest == EXIT_BLOCK_PTR)
6657 if (cfgcleanup_altered_bbs)
6658 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6663 /* First, we find the basic blocks to remove. If E->dest has a predecessor
6664 that is not dominated by E->dest, then this set is empty. Otherwise,
6665 all the basic blocks dominated by E->dest are removed.
6667 Also, to DF_IDOM we store the immediate dominators of the blocks in
6668 the dominance frontier of E (i.e., of the successors of the
6669 removed blocks, if there are any, and of E->dest otherwise). */
6670 FOR_EACH_EDGE (f, ei, e->dest->preds)
6675 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6677 none_removed = true;
6682 df = BITMAP_ALLOC (NULL);
6683 df_idom = BITMAP_ALLOC (NULL);
6686 bitmap_set_bit (df_idom,
6687 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6690 get_all_dominated_blocks (e->dest, &bbs_to_remove);
6691 for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6693 FOR_EACH_EDGE (f, ei, bb->succs)
6695 if (f->dest != EXIT_BLOCK_PTR)
6696 bitmap_set_bit (df, f->dest->index);
6699 for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6700 bitmap_clear_bit (df, bb->index);
6702 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6704 bb = BASIC_BLOCK (i);
6705 bitmap_set_bit (df_idom,
6706 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6710 if (cfgcleanup_altered_bbs)
6712 /* Record the set of the altered basic blocks. */
6713 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6714 bitmap_ior_into (cfgcleanup_altered_bbs, df);
6717 /* Remove E and the cancelled blocks. */
6722 for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6723 delete_basic_block (bb);
6726 /* Update the dominance information. The immediate dominator may change only
6727 for blocks whose immediate dominator belongs to DF_IDOM:
6729 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6730 removal. Let Z the arbitrary block such that idom(Z) = Y and
6731 Z dominates X after the removal. Before removal, there exists a path P
6732 from Y to X that avoids Z. Let F be the last edge on P that is
6733 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
6734 dominates W, and because of P, Z does not dominate W), and W belongs to
6735 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
6736 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6738 bb = BASIC_BLOCK (i);
6739 for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6741 dbb = next_dom_son (CDI_DOMINATORS, dbb))
6742 VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6745 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6748 BITMAP_FREE (df_idom);
6749 VEC_free (basic_block, heap, bbs_to_remove);
6750 VEC_free (basic_block, heap, bbs_to_fix_dom);
6753 /* Purge dead EH edges from basic block BB. */
6756 tree_purge_dead_eh_edges (basic_block bb)
6758 bool changed = false;
6761 tree stmt = last_stmt (bb);
6763 if (stmt && tree_can_throw_internal (stmt))
6766 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6768 if (e->flags & EDGE_EH)
6770 remove_edge_and_dominated_blocks (e);
6781 tree_purge_all_dead_eh_edges (const_bitmap blocks)
6783 bool changed = false;
6787 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6789 changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
6795 /* This function is called whenever a new edge is created or
6799 tree_execute_on_growing_pred (edge e)
6801 basic_block bb = e->dest;
6804 reserve_phi_args_for_new_edge (bb);
6807 /* This function is called immediately before edge E is removed from
6808 the edge vector E->dest->preds. */
6811 tree_execute_on_shrinking_pred (edge e)
6813 if (phi_nodes (e->dest))
6814 remove_phi_args (e);
6817 /*---------------------------------------------------------------------------
6818 Helper functions for Loop versioning
6819 ---------------------------------------------------------------------------*/
6821 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
6822 of 'first'. Both of them are dominated by 'new_head' basic block. When
6823 'new_head' was created by 'second's incoming edge it received phi arguments
6824 on the edge by split_edge(). Later, additional edge 'e' was created to
6825 connect 'new_head' and 'first'. Now this routine adds phi args on this
6826 additional edge 'e' that new_head to second edge received as part of edge
6831 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
6832 basic_block new_head, edge e)
6835 edge e2 = find_edge (new_head, second);
6837 /* Because NEW_HEAD has been created by splitting SECOND's incoming
6838 edge, we should always have an edge from NEW_HEAD to SECOND. */
6839 gcc_assert (e2 != NULL);
6841 /* Browse all 'second' basic block phi nodes and add phi args to
6842 edge 'e' for 'first' head. PHI args are always in correct order. */
6844 for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
6846 phi2 = PHI_CHAIN (phi2), phi1 = PHI_CHAIN (phi1))
6848 tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
6849 add_phi_arg (phi1, def, e);
6853 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6854 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6855 the destination of the ELSE part. */
6857 tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
6858 basic_block second_head ATTRIBUTE_UNUSED,
6859 basic_block cond_bb, void *cond_e)
6861 block_stmt_iterator bsi;
6862 tree new_cond_expr = NULL_TREE;
6863 tree cond_expr = (tree) cond_e;
6866 /* Build new conditional expr */
6867 new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr,
6868 NULL_TREE, NULL_TREE);
6870 /* Add new cond in cond_bb. */
6871 bsi = bsi_start (cond_bb);
6872 bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
6873 /* Adjust edges appropriately to connect new head with first head
6874 as well as second head. */
6875 e0 = single_succ_edge (cond_bb);
6876 e0->flags &= ~EDGE_FALLTHRU;
6877 e0->flags |= EDGE_FALSE_VALUE;
6880 struct cfg_hooks tree_cfg_hooks = {
6882 tree_verify_flow_info,
6883 tree_dump_bb, /* dump_bb */
6884 create_bb, /* create_basic_block */
6885 tree_redirect_edge_and_branch,/* redirect_edge_and_branch */
6886 tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force */
6887 tree_can_remove_branch_p, /* can_remove_branch_p */
6888 remove_bb, /* delete_basic_block */
6889 tree_split_block, /* split_block */
6890 tree_move_block_after, /* move_block_after */
6891 tree_can_merge_blocks_p, /* can_merge_blocks_p */
6892 tree_merge_blocks, /* merge_blocks */
6893 tree_predict_edge, /* predict_edge */
6894 tree_predicted_by_p, /* predicted_by_p */
6895 tree_can_duplicate_bb_p, /* can_duplicate_block_p */
6896 tree_duplicate_bb, /* duplicate_block */
6897 tree_split_edge, /* split_edge */
6898 tree_make_forwarder_block, /* make_forward_block */
6899 NULL, /* tidy_fallthru_edge */
6900 tree_block_ends_with_call_p, /* block_ends_with_call_p */
6901 tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
6902 tree_flow_call_edges_add, /* flow_call_edges_add */
6903 tree_execute_on_growing_pred, /* execute_on_growing_pred */
6904 tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
6905 tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
6906 tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
6907 tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
6908 extract_true_false_edges_from_block, /* extract_cond_bb_edges */
6909 flush_pending_stmts /* flush_pending_stmts */
6913 /* Split all critical edges. */
6916 split_critical_edges (void)
6922 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6923 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
6924 mappings around the calls to split_edge. */
6925 start_recording_case_labels ();
6928 FOR_EACH_EDGE (e, ei, bb->succs)
6929 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
6934 end_recording_case_labels ();
6938 struct gimple_opt_pass pass_split_crit_edges =
6942 "crited", /* name */
6944 split_critical_edges, /* execute */
6947 0, /* static_pass_number */
6948 TV_TREE_SPLIT_EDGES, /* tv_id */
6949 PROP_cfg, /* properties required */
6950 PROP_no_crit_edges, /* properties_provided */
6951 0, /* properties_destroyed */
6952 0, /* todo_flags_start */
6953 TODO_dump_func /* todo_flags_finish */
6958 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
6959 a temporary, make sure and register it to be renamed if necessary,
6960 and finally return the temporary. Put the statements to compute
6961 EXP before the current statement in BSI. */
6964 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
6966 tree t, new_stmt, orig_stmt;
6968 if (is_gimple_val (exp))
6971 t = make_rename_temp (type, NULL);
6972 new_stmt = build_gimple_modify_stmt (t, exp);
6974 orig_stmt = bsi_stmt (*bsi);
6975 SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
6976 TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
6978 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
6979 if (gimple_in_ssa_p (cfun))
6980 mark_symbols_for_renaming (new_stmt);
6985 /* Build a ternary operation and gimplify it. Emit code before BSI.
6986 Return the gimple_val holding the result. */
6989 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
6990 tree type, tree a, tree b, tree c)
6994 ret = fold_build3 (code, type, a, b, c);
6997 return gimplify_val (bsi, type, ret);
7000 /* Build a binary operation and gimplify it. Emit code before BSI.
7001 Return the gimple_val holding the result. */
7004 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
7005 tree type, tree a, tree b)
7009 ret = fold_build2 (code, type, a, b);
7012 return gimplify_val (bsi, type, ret);
7015 /* Build a unary operation and gimplify it. Emit code before BSI.
7016 Return the gimple_val holding the result. */
7019 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
7024 ret = fold_build1 (code, type, a);
7027 return gimplify_val (bsi, type, ret);
7032 /* Emit return warnings. */
7035 execute_warn_function_return (void)
7037 source_location location;
7042 /* If we have a path to EXIT, then we do return. */
7043 if (TREE_THIS_VOLATILE (cfun->decl)
7044 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7046 location = UNKNOWN_LOCATION;
7047 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7049 last = last_stmt (e->src);
7050 if (TREE_CODE (last) == RETURN_EXPR
7051 && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
7054 if (location == UNKNOWN_LOCATION)
7055 location = cfun->function_end_locus;
7056 warning (0, "%H%<noreturn%> function does return", &location);
7059 /* If we see "return;" in some basic block, then we do reach the end
7060 without returning a value. */
7061 else if (warn_return_type
7062 && !TREE_NO_WARNING (cfun->decl)
7063 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7064 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7066 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7068 tree last = last_stmt (e->src);
7069 if (TREE_CODE (last) == RETURN_EXPR
7070 && TREE_OPERAND (last, 0) == NULL
7071 && !TREE_NO_WARNING (last))
7073 location = EXPR_LOCATION (last);
7074 if (location == UNKNOWN_LOCATION)
7075 location = cfun->function_end_locus;
7076 warning (OPT_Wreturn_type, "%Hcontrol reaches end of non-void function", &location);
7077 TREE_NO_WARNING (cfun->decl) = 1;
7086 /* Given a basic block B which ends with a conditional and has
7087 precisely two successors, determine which of the edges is taken if
7088 the conditional is true and which is taken if the conditional is
7089 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
7092 extract_true_false_edges_from_block (basic_block b,
7096 edge e = EDGE_SUCC (b, 0);
7098 if (e->flags & EDGE_TRUE_VALUE)
7101 *false_edge = EDGE_SUCC (b, 1);
7106 *true_edge = EDGE_SUCC (b, 1);
7110 struct gimple_opt_pass pass_warn_function_return =
7116 execute_warn_function_return, /* execute */
7119 0, /* static_pass_number */
7121 PROP_cfg, /* properties_required */
7122 0, /* properties_provided */
7123 0, /* properties_destroyed */
7124 0, /* todo_flags_start */
7125 0 /* todo_flags_finish */
7129 /* Emit noreturn warnings. */
7132 execute_warn_function_noreturn (void)
7134 if (warn_missing_noreturn
7135 && !TREE_THIS_VOLATILE (cfun->decl)
7136 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
7137 && !lang_hooks.missing_noreturn_ok_p (cfun->decl))
7138 warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
7139 "for attribute %<noreturn%>",
7144 struct gimple_opt_pass pass_warn_function_noreturn =
7150 execute_warn_function_noreturn, /* execute */
7153 0, /* static_pass_number */
7155 PROP_cfg, /* properties_required */
7156 0, /* properties_provided */
7157 0, /* properties_destroyed */
7158 0, /* todo_flags_start */
7159 0 /* todo_flags_finish */