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 cfun
->calls_alloca
= true;
1812 if (flags
& ECF_RETURNS_TWICE
)
1813 cfun
->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 cfun
->calls_alloca
= false;
1824 cfun
->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
) && cfun
->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
) && cfun
->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");
3192 bool old_side_effects
;
3194 bool new_side_effects
;
3196 gcc_assert (is_gimple_address (t
));
3198 old_constant
= TREE_CONSTANT (t
);
3199 old_side_effects
= TREE_SIDE_EFFECTS (t
);
3201 recompute_tree_invariant_for_addr_expr (t
);
3202 new_side_effects
= TREE_SIDE_EFFECTS (t
);
3203 new_constant
= TREE_CONSTANT (t
);
3205 if (old_constant
!= new_constant
)
3207 error ("constant not recomputed when ADDR_EXPR changed");
3210 if (old_side_effects
!= new_side_effects
)
3212 error ("side effects not recomputed when ADDR_EXPR changed");
3216 /* Skip any references (they will be checked when we recurse down the
3217 tree) and ensure that any variable used as a prefix is marked
3219 for (x
= TREE_OPERAND (t
, 0);
3220 handled_component_p (x
);
3221 x
= TREE_OPERAND (x
, 0))
3224 if (TREE_CODE (x
) != VAR_DECL
&& TREE_CODE (x
) != PARM_DECL
)
3226 if (!TREE_ADDRESSABLE (x
))
3228 error ("address taken, but ADDRESSABLE bit not set");
3236 x
= COND_EXPR_COND (t
);
3237 if (!INTEGRAL_TYPE_P (TREE_TYPE (x
)))
3239 error ("non-integral used in condition");
3242 if (!is_gimple_condexpr (x
))
3244 error ("invalid conditional operand");
3249 case NON_LVALUE_EXPR
:
3254 case FIX_TRUNC_EXPR
:
3259 case TRUTH_NOT_EXPR
:
3260 CHECK_OP (0, "invalid operand to unary operator");
3267 case ARRAY_RANGE_REF
:
3269 case VIEW_CONVERT_EXPR
:
3270 /* We have a nest of references. Verify that each of the operands
3271 that determine where to reference is either a constant or a variable,
3272 verify that the base is valid, and then show we've already checked
3274 while (handled_component_p (t
))
3276 if (TREE_CODE (t
) == COMPONENT_REF
&& TREE_OPERAND (t
, 2))
3277 CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3278 else if (TREE_CODE (t
) == ARRAY_REF
3279 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
3281 CHECK_OP (1, "invalid array index");
3282 if (TREE_OPERAND (t
, 2))
3283 CHECK_OP (2, "invalid array lower bound");
3284 if (TREE_OPERAND (t
, 3))
3285 CHECK_OP (3, "invalid array stride");
3287 else if (TREE_CODE (t
) == BIT_FIELD_REF
)
3289 if (!host_integerp (TREE_OPERAND (t
, 1), 1)
3290 || !host_integerp (TREE_OPERAND (t
, 2), 1))
3292 error ("invalid position or size operand to BIT_FIELD_REF");
3295 else if (INTEGRAL_TYPE_P (TREE_TYPE (t
))
3296 && (TYPE_PRECISION (TREE_TYPE (t
))
3297 != TREE_INT_CST_LOW (TREE_OPERAND (t
, 1))))
3299 error ("integral result type precision does not match "
3300 "field size of BIT_FIELD_REF");
3303 if (!INTEGRAL_TYPE_P (TREE_TYPE (t
))
3304 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t
)))
3305 != TREE_INT_CST_LOW (TREE_OPERAND (t
, 1))))
3307 error ("mode precision of non-integral result does not "
3308 "match field size of BIT_FIELD_REF");
3313 t
= TREE_OPERAND (t
, 0);
3316 if (!is_gimple_min_invariant (t
) && !is_gimple_lvalue (t
))
3318 error ("invalid reference prefix");
3325 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3326 POINTER_PLUS_EXPR. */
3327 if (POINTER_TYPE_P (TREE_TYPE (t
)))
3329 error ("invalid operand to plus/minus, type is a pointer");
3332 CHECK_OP (0, "invalid operand to binary operator");
3333 CHECK_OP (1, "invalid operand to binary operator");
3336 case POINTER_PLUS_EXPR
:
3337 /* Check to make sure the first operand is a pointer or reference type. */
3338 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t
, 0))))
3340 error ("invalid operand to pointer plus, first operand is not a pointer");
3343 /* Check to make sure the second operand is an integer with type of
3345 if (!useless_type_conversion_p (sizetype
,
3346 TREE_TYPE (TREE_OPERAND (t
, 1))))
3348 error ("invalid operand to pointer plus, second operand is not an "
3349 "integer with type of sizetype.");
3359 case UNORDERED_EXPR
:
3368 case TRUNC_DIV_EXPR
:
3370 case FLOOR_DIV_EXPR
:
3371 case ROUND_DIV_EXPR
:
3372 case TRUNC_MOD_EXPR
:
3374 case FLOOR_MOD_EXPR
:
3375 case ROUND_MOD_EXPR
:
3377 case EXACT_DIV_EXPR
:
3387 CHECK_OP (0, "invalid operand to binary operator");
3388 CHECK_OP (1, "invalid operand to binary operator");
3392 if (TREE_CONSTANT (t
) && TREE_CODE (TREE_TYPE (t
)) == VECTOR_TYPE
)
3404 /* Verifies if EXPR is a valid GIMPLE unary expression. Returns true
3405 if there is an error, otherwise false. */
3408 verify_gimple_unary_expr (const_tree expr
)
3410 tree op
= TREE_OPERAND (expr
, 0);
3411 tree type
= TREE_TYPE (expr
);
3413 if (!is_gimple_val (op
))
3415 error ("invalid operand in unary expression");
3419 /* For general unary expressions we have the operations type
3420 as the effective type the operation is carried out on. So all
3421 we need to require is that the operand is trivially convertible
3423 if (!useless_type_conversion_p (type
, TREE_TYPE (op
)))
3425 error ("type mismatch in unary expression");
3426 debug_generic_expr (type
);
3427 debug_generic_expr (TREE_TYPE (op
));
3434 /* Verifies if EXPR is a valid GIMPLE binary expression. Returns true
3435 if there is an error, otherwise false. */
3438 verify_gimple_binary_expr (const_tree expr
)
3440 tree op0
= TREE_OPERAND (expr
, 0);
3441 tree op1
= TREE_OPERAND (expr
, 1);
3442 tree type
= TREE_TYPE (expr
);
3444 if (!is_gimple_val (op0
) || !is_gimple_val (op1
))
3446 error ("invalid operands in binary expression");
3450 /* For general binary expressions we have the operations type
3451 as the effective type the operation is carried out on. So all
3452 we need to require is that both operands are trivially convertible
3454 if (!useless_type_conversion_p (type
, TREE_TYPE (op0
))
3455 || !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
3457 error ("type mismatch in binary expression");
3458 debug_generic_stmt (type
);
3459 debug_generic_stmt (TREE_TYPE (op0
));
3460 debug_generic_stmt (TREE_TYPE (op1
));
3467 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3468 Returns true if there is an error, otherwise false. */
3471 verify_gimple_min_lval (tree expr
)
3475 if (is_gimple_id (expr
))
3478 if (TREE_CODE (expr
) != INDIRECT_REF
3479 && TREE_CODE (expr
) != ALIGN_INDIRECT_REF
3480 && TREE_CODE (expr
) != MISALIGNED_INDIRECT_REF
)
3482 error ("invalid expression for min lvalue");
3486 op
= TREE_OPERAND (expr
, 0);
3487 if (!is_gimple_val (op
))
3489 error ("invalid operand in indirect reference");
3490 debug_generic_stmt (op
);
3493 if (!useless_type_conversion_p (TREE_TYPE (expr
),
3494 TREE_TYPE (TREE_TYPE (op
))))
3496 error ("type mismatch in indirect reference");
3497 debug_generic_stmt (TREE_TYPE (expr
));
3498 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op
)));
3505 /* Verify if EXPR is a valid GIMPLE reference expression. Returns true
3506 if there is an error, otherwise false. */
3509 verify_gimple_reference (tree expr
)
3511 while (handled_component_p (expr
))
3513 tree op
= TREE_OPERAND (expr
, 0);
3515 if (TREE_CODE (expr
) == ARRAY_REF
3516 || TREE_CODE (expr
) == ARRAY_RANGE_REF
)
3518 if (!is_gimple_val (TREE_OPERAND (expr
, 1))
3519 || (TREE_OPERAND (expr
, 2)
3520 && !is_gimple_val (TREE_OPERAND (expr
, 2)))
3521 || (TREE_OPERAND (expr
, 3)
3522 && !is_gimple_val (TREE_OPERAND (expr
, 3))))
3524 error ("invalid operands to array reference");
3525 debug_generic_stmt (expr
);
3530 /* Verify if the reference array element types are compatible. */
3531 if (TREE_CODE (expr
) == ARRAY_REF
3532 && !useless_type_conversion_p (TREE_TYPE (expr
),
3533 TREE_TYPE (TREE_TYPE (op
))))
3535 error ("type mismatch in array reference");
3536 debug_generic_stmt (TREE_TYPE (expr
));
3537 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op
)));
3540 if (TREE_CODE (expr
) == ARRAY_RANGE_REF
3541 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr
)),
3542 TREE_TYPE (TREE_TYPE (op
))))
3544 error ("type mismatch in array range reference");
3545 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr
)));
3546 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op
)));
3550 if ((TREE_CODE (expr
) == REALPART_EXPR
3551 || TREE_CODE (expr
) == IMAGPART_EXPR
)
3552 && !useless_type_conversion_p (TREE_TYPE (expr
),
3553 TREE_TYPE (TREE_TYPE (op
))))
3555 error ("type mismatch in real/imagpart reference");
3556 debug_generic_stmt (TREE_TYPE (expr
));
3557 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op
)));
3561 if (TREE_CODE (expr
) == COMPONENT_REF
3562 && !useless_type_conversion_p (TREE_TYPE (expr
),
3563 TREE_TYPE (TREE_OPERAND (expr
, 1))))
3565 error ("type mismatch in component reference");
3566 debug_generic_stmt (TREE_TYPE (expr
));
3567 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr
, 1)));
3571 /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3572 is nothing to verify. Gross mismatches at most invoke
3573 undefined behavior. */
3578 return verify_gimple_min_lval (expr
);
3581 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3582 list of pointer-to types that is trivially convertible to DEST. */
3585 one_pointer_to_useless_type_conversion_p (tree dest
, tree src_obj
)
3589 if (!TYPE_POINTER_TO (src_obj
))
3592 for (src
= TYPE_POINTER_TO (src_obj
); src
; src
= TYPE_NEXT_PTR_TO (src
))
3593 if (useless_type_conversion_p (dest
, src
))
3599 /* Verify the GIMPLE expression EXPR. Returns true if there is an
3600 error, otherwise false. */
3603 verify_gimple_expr (tree expr
)
3605 tree type
= TREE_TYPE (expr
);
3607 if (is_gimple_val (expr
))
3610 /* Special codes we cannot handle via their class. */
3611 switch (TREE_CODE (expr
))
3616 tree op
= TREE_OPERAND (expr
, 0);
3617 if (!is_gimple_val (op
))
3619 error ("invalid operand in conversion");
3623 /* Allow conversions between integral types and between
3625 if ((INTEGRAL_TYPE_P (type
) && INTEGRAL_TYPE_P (TREE_TYPE (op
)))
3626 || (POINTER_TYPE_P (type
) && POINTER_TYPE_P (TREE_TYPE (op
))))
3629 /* Allow conversions between integral types and pointers only if
3630 there is no sign or zero extension involved. */
3631 if (((POINTER_TYPE_P (type
) && INTEGRAL_TYPE_P (TREE_TYPE (op
)))
3632 || (POINTER_TYPE_P (TREE_TYPE (op
)) && INTEGRAL_TYPE_P (type
)))
3633 && TYPE_PRECISION (type
) == TYPE_PRECISION (TREE_TYPE (op
)))
3636 /* Allow conversion from integer to offset type and vice versa. */
3637 if ((TREE_CODE (type
) == OFFSET_TYPE
3638 && TREE_CODE (TREE_TYPE (op
)) == INTEGER_TYPE
)
3639 || (TREE_CODE (type
) == INTEGER_TYPE
3640 && TREE_CODE (TREE_TYPE (op
)) == OFFSET_TYPE
))
3643 /* Otherwise assert we are converting between types of the
3645 if (TREE_CODE (type
) != TREE_CODE (TREE_TYPE (op
)))
3647 error ("invalid types in nop conversion");
3648 debug_generic_expr (type
);
3649 debug_generic_expr (TREE_TYPE (op
));
3658 tree op
= TREE_OPERAND (expr
, 0);
3659 if (!is_gimple_val (op
))
3661 error ("invalid operand in int to float conversion");
3664 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
))
3665 || !SCALAR_FLOAT_TYPE_P (type
))
3667 error ("invalid types in conversion to floating point");
3668 debug_generic_expr (type
);
3669 debug_generic_expr (TREE_TYPE (op
));
3675 case FIX_TRUNC_EXPR
:
3677 tree op
= TREE_OPERAND (expr
, 0);
3678 if (!is_gimple_val (op
))
3680 error ("invalid operand in float to int conversion");
3683 if (!INTEGRAL_TYPE_P (type
)
3684 || !SCALAR_FLOAT_TYPE_P (TREE_TYPE (op
)))
3686 error ("invalid types in conversion to integer");
3687 debug_generic_expr (type
);
3688 debug_generic_expr (TREE_TYPE (op
));
3696 tree op0
= TREE_OPERAND (expr
, 0);
3697 tree op1
= TREE_OPERAND (expr
, 1);
3698 if (!is_gimple_val (op0
) || !is_gimple_val (op1
))
3700 error ("invalid operands in complex expression");
3703 if (!TREE_CODE (type
) == COMPLEX_TYPE
3704 || !(TREE_CODE (TREE_TYPE (op0
)) == INTEGER_TYPE
3705 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0
)))
3706 || !(TREE_CODE (TREE_TYPE (op1
)) == INTEGER_TYPE
3707 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (op1
)))
3708 || !useless_type_conversion_p (TREE_TYPE (type
),
3710 || !useless_type_conversion_p (TREE_TYPE (type
),
3713 error ("type mismatch in complex expression");
3714 debug_generic_stmt (TREE_TYPE (expr
));
3715 debug_generic_stmt (TREE_TYPE (op0
));
3716 debug_generic_stmt (TREE_TYPE (op1
));
3724 /* This is used like COMPLEX_EXPR but for vectors. */
3725 if (TREE_CODE (type
) != VECTOR_TYPE
)
3727 error ("constructor not allowed for non-vector types");
3728 debug_generic_stmt (type
);
3731 /* FIXME: verify constructor arguments. */
3740 tree op0
= TREE_OPERAND (expr
, 0);
3741 tree op1
= TREE_OPERAND (expr
, 1);
3742 if (!is_gimple_val (op0
) || !is_gimple_val (op1
))
3744 error ("invalid operands in shift expression");
3747 if (!TREE_CODE (TREE_TYPE (op1
)) == INTEGER_TYPE
3748 || !useless_type_conversion_p (type
, TREE_TYPE (op0
)))
3750 error ("type mismatch in shift expression");
3751 debug_generic_stmt (TREE_TYPE (expr
));
3752 debug_generic_stmt (TREE_TYPE (op0
));
3753 debug_generic_stmt (TREE_TYPE (op1
));
3762 tree op0
= TREE_OPERAND (expr
, 0);
3763 tree op1
= TREE_OPERAND (expr
, 1);
3764 if (POINTER_TYPE_P (type
)
3765 || POINTER_TYPE_P (TREE_TYPE (op0
))
3766 || POINTER_TYPE_P (TREE_TYPE (op1
)))
3768 error ("invalid (pointer) operands to plus/minus");
3771 /* Continue with generic binary expression handling. */
3775 case POINTER_PLUS_EXPR
:
3777 tree op0
= TREE_OPERAND (expr
, 0);
3778 tree op1
= TREE_OPERAND (expr
, 1);
3779 if (!is_gimple_val (op0
) || !is_gimple_val (op1
))
3781 error ("invalid operands in pointer plus expression");
3784 if (!POINTER_TYPE_P (TREE_TYPE (op0
))
3785 || !useless_type_conversion_p (type
, TREE_TYPE (op0
))
3786 || !useless_type_conversion_p (sizetype
, TREE_TYPE (op1
)))
3788 error ("type mismatch in pointer plus expression");
3789 debug_generic_stmt (type
);
3790 debug_generic_stmt (TREE_TYPE (op0
));
3791 debug_generic_stmt (TREE_TYPE (op1
));
3799 tree op0
= TREE_OPERAND (expr
, 0);
3800 tree op1
= TREE_OPERAND (expr
, 1);
3801 tree op2
= TREE_OPERAND (expr
, 2);
3802 if ((!is_gimple_val (op1
)
3803 && TREE_CODE (TREE_TYPE (op1
)) != VOID_TYPE
)
3804 || (!is_gimple_val (op2
)
3805 && TREE_CODE (TREE_TYPE (op2
)) != VOID_TYPE
))
3807 error ("invalid operands in conditional expression");
3810 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3811 || (TREE_CODE (TREE_TYPE (op1
)) != VOID_TYPE
3812 && !useless_type_conversion_p (type
, TREE_TYPE (op1
)))
3813 || (TREE_CODE (TREE_TYPE (op2
)) != VOID_TYPE
3814 && !useless_type_conversion_p (type
, TREE_TYPE (op2
))))
3816 error ("type mismatch in conditional expression");
3817 debug_generic_stmt (type
);
3818 debug_generic_stmt (TREE_TYPE (op0
));
3819 debug_generic_stmt (TREE_TYPE (op1
));
3820 debug_generic_stmt (TREE_TYPE (op2
));
3823 return verify_gimple_expr (op0
);
3828 tree op
= TREE_OPERAND (expr
, 0);
3829 if (!is_gimple_addressable (op
))
3831 error ("invalid operand in unary expression");
3834 if (!one_pointer_to_useless_type_conversion_p (type
, TREE_TYPE (op
))
3835 /* FIXME: a longstanding wart, &a == &a[0]. */
3836 && (TREE_CODE (TREE_TYPE (op
)) != ARRAY_TYPE
3837 || !one_pointer_to_useless_type_conversion_p (type
,
3838 TREE_TYPE (TREE_TYPE (op
)))))
3840 error ("type mismatch in address expression");
3841 debug_generic_stmt (TREE_TYPE (expr
));
3842 debug_generic_stmt (TYPE_POINTER_TO (TREE_TYPE (op
)));
3846 return verify_gimple_reference (op
);
3849 case TRUTH_ANDIF_EXPR
:
3850 case TRUTH_ORIF_EXPR
:
3853 case TRUTH_AND_EXPR
:
3855 case TRUTH_XOR_EXPR
:
3857 tree op0
= TREE_OPERAND (expr
, 0);
3858 tree op1
= TREE_OPERAND (expr
, 1);
3860 if (!is_gimple_val (op0
) || !is_gimple_val (op1
))
3862 error ("invalid operands in truth expression");
3866 /* We allow any kind of integral typed argument and result. */
3867 if (!INTEGRAL_TYPE_P (TREE_TYPE (op0
))
3868 || !INTEGRAL_TYPE_P (TREE_TYPE (op1
))
3869 || !INTEGRAL_TYPE_P (type
))
3871 error ("type mismatch in binary truth expression");
3872 debug_generic_stmt (type
);
3873 debug_generic_stmt (TREE_TYPE (op0
));
3874 debug_generic_stmt (TREE_TYPE (op1
));
3881 case TRUTH_NOT_EXPR
:
3883 tree op
= TREE_OPERAND (expr
, 0);
3885 if (!is_gimple_val (op
))
3887 error ("invalid operand in unary not");
3891 /* For TRUTH_NOT_EXPR we can have any kind of integral
3892 typed arguments and results. */
3893 if (!INTEGRAL_TYPE_P (TREE_TYPE (op
))
3894 || !INTEGRAL_TYPE_P (type
))
3896 error ("type mismatch in not expression");
3897 debug_generic_expr (TREE_TYPE (expr
));
3898 debug_generic_expr (TREE_TYPE (op
));
3906 /* FIXME. The C frontend passes unpromoted arguments in case it
3907 didn't see a function declaration before the call. */
3917 /* Generic handling via classes. */
3918 switch (TREE_CODE_CLASS (TREE_CODE (expr
)))
3921 return verify_gimple_unary_expr (expr
);
3924 return verify_gimple_binary_expr (expr
);
3927 return verify_gimple_reference (expr
);
3929 case tcc_comparison
:
3931 tree op0
= TREE_OPERAND (expr
, 0);
3932 tree op1
= TREE_OPERAND (expr
, 1);
3933 if (!is_gimple_val (op0
) || !is_gimple_val (op1
))
3935 error ("invalid operands in comparison expression");
3938 /* For comparisons we do not have the operations type as the
3939 effective type the comparison is carried out in. Instead
3940 we require that either the first operand is trivially
3941 convertible into the second, or the other way around.
3942 The resulting type of a comparison may be any integral type.
3943 Because we special-case pointers to void we allow
3944 comparisons of pointers with the same mode as well. */
3945 if ((!useless_type_conversion_p (TREE_TYPE (op0
), TREE_TYPE (op1
))
3946 && !useless_type_conversion_p (TREE_TYPE (op1
), TREE_TYPE (op0
))
3947 && (!POINTER_TYPE_P (TREE_TYPE (op0
))
3948 || !POINTER_TYPE_P (TREE_TYPE (op1
))
3949 || TYPE_MODE (TREE_TYPE (op0
)) != TYPE_MODE (TREE_TYPE (op1
))))
3950 || !INTEGRAL_TYPE_P (type
))
3952 error ("type mismatch in comparison expression");
3953 debug_generic_stmt (TREE_TYPE (expr
));
3954 debug_generic_stmt (TREE_TYPE (op0
));
3955 debug_generic_stmt (TREE_TYPE (op1
));
3968 /* Verify the GIMPLE assignment statement STMT. Returns true if there
3969 is an error, otherwise false. */
3972 verify_gimple_modify_stmt (const_tree stmt
)
3974 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
3975 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
3977 gcc_assert (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
);
3979 if (!useless_type_conversion_p (TREE_TYPE (lhs
),
3982 error ("non-trivial conversion at assignment");
3983 debug_generic_expr (TREE_TYPE (lhs
));
3984 debug_generic_expr (TREE_TYPE (rhs
));
3988 /* Loads/stores from/to a variable are ok. */
3989 if ((is_gimple_val (lhs
)
3990 && is_gimple_variable (rhs
))
3991 || (is_gimple_val (rhs
)
3992 && is_gimple_variable (lhs
)))
3995 /* Aggregate copies are ok. */
3996 if (!is_gimple_reg_type (TREE_TYPE (lhs
))
3997 && !is_gimple_reg_type (TREE_TYPE (rhs
)))
4000 /* We might get 'loads' from a parameter which is not a gimple value. */
4001 if (TREE_CODE (rhs
) == PARM_DECL
)
4002 return verify_gimple_expr (lhs
);
4004 if (!is_gimple_variable (lhs
)
4005 && verify_gimple_expr (lhs
))
4008 if (!is_gimple_variable (rhs
)
4009 && verify_gimple_expr (rhs
))
4015 /* Verify the GIMPLE statement STMT. Returns true if there is an
4016 error, otherwise false. */
4019 verify_gimple_stmt (tree stmt
)
4021 if (!is_gimple_stmt (stmt
))
4023 error ("is not a valid GIMPLE statement");
4027 if (OMP_DIRECTIVE_P (stmt
))
4029 /* OpenMP directives are validated by the FE and never operated
4030 on by the optimizers. Furthermore, OMP_FOR may contain
4031 non-gimple expressions when the main index variable has had
4032 its address taken. This does not affect the loop itself
4033 because the header of an OMP_FOR is merely used to determine
4034 how to setup the parallel iteration. */
4038 switch (TREE_CODE (stmt
))
4040 case GIMPLE_MODIFY_STMT
:
4041 return verify_gimple_modify_stmt (stmt
);
4048 if (!is_gimple_val (TREE_OPERAND (stmt
, 0)))
4050 error ("invalid operand to switch statement");
4051 debug_generic_expr (TREE_OPERAND (stmt
, 0));
4057 tree op
= TREE_OPERAND (stmt
, 0);
4059 if (TREE_CODE (TREE_TYPE (stmt
)) != VOID_TYPE
)
4061 error ("type error in return expression");
4066 || TREE_CODE (op
) == RESULT_DECL
)
4069 return verify_gimple_modify_stmt (op
);
4074 return verify_gimple_expr (stmt
);
4077 case CHANGE_DYNAMIC_TYPE_EXPR
:
4087 /* Verify the GIMPLE statements inside the statement list STMTS.
4088 Returns true if there were any errors. */
4091 verify_gimple_2 (tree stmts
)
4093 tree_stmt_iterator tsi
;
4096 for (tsi
= tsi_start (stmts
); !tsi_end_p (tsi
); tsi_next (&tsi
))
4098 tree stmt
= tsi_stmt (tsi
);
4100 switch (TREE_CODE (stmt
))
4103 err
|= verify_gimple_2 (BIND_EXPR_BODY (stmt
));
4106 case TRY_CATCH_EXPR
:
4107 case TRY_FINALLY_EXPR
:
4108 err
|= verify_gimple_2 (TREE_OPERAND (stmt
, 0));
4109 err
|= verify_gimple_2 (TREE_OPERAND (stmt
, 1));
4113 err
|= verify_gimple_2 (CATCH_BODY (stmt
));
4116 case EH_FILTER_EXPR
:
4117 err
|= verify_gimple_2 (EH_FILTER_FAILURE (stmt
));
4122 bool err2
= verify_gimple_stmt (stmt
);
4124 debug_generic_expr (stmt
);
4134 /* Verify the GIMPLE statements inside the statement list STMTS. */
4137 verify_gimple_1 (tree stmts
)
4139 if (verify_gimple_2 (stmts
))
4140 internal_error ("verify_gimple failed");
4143 /* Verify the GIMPLE statements inside the current function. */
4146 verify_gimple (void)
4148 verify_gimple_1 (BIND_EXPR_BODY (DECL_SAVED_TREE (cfun
->decl
)));
4151 /* Verify STMT, return true if STMT is not in GIMPLE form.
4152 TODO: Implement type checking. */
4155 verify_stmt (tree stmt
, bool last_in_block
)
4159 if (OMP_DIRECTIVE_P (stmt
))
4161 /* OpenMP directives are validated by the FE and never operated
4162 on by the optimizers. Furthermore, OMP_FOR may contain
4163 non-gimple expressions when the main index variable has had
4164 its address taken. This does not affect the loop itself
4165 because the header of an OMP_FOR is merely used to determine
4166 how to setup the parallel iteration. */
4170 if (!is_gimple_stmt (stmt
))
4172 error ("is not a valid GIMPLE statement");
4176 addr
= walk_tree (&stmt
, verify_expr
, NULL
, NULL
);
4179 debug_generic_stmt (addr
);
4182 inform ("in statement");
4183 debug_generic_stmt (stmt
);
4188 /* If the statement is marked as part of an EH region, then it is
4189 expected that the statement could throw. Verify that when we
4190 have optimizations that simplify statements such that we prove
4191 that they cannot throw, that we update other data structures
4193 if (lookup_stmt_eh_region (stmt
) >= 0)
4195 if (!tree_could_throw_p (stmt
))
4197 error ("statement marked for throw, but doesn%'t");
4200 if (!last_in_block
&& tree_can_throw_internal (stmt
))
4202 error ("statement marked for throw in middle of block");
4210 debug_generic_stmt (stmt
);
4215 /* Return true when the T can be shared. */
4218 tree_node_can_be_shared (tree t
)
4220 if (IS_TYPE_OR_DECL_P (t
)
4221 || is_gimple_min_invariant (t
)
4222 || TREE_CODE (t
) == SSA_NAME
4223 || t
== error_mark_node
4224 || TREE_CODE (t
) == IDENTIFIER_NODE
)
4227 if (TREE_CODE (t
) == CASE_LABEL_EXPR
)
4230 while (((TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
4231 && is_gimple_min_invariant (TREE_OPERAND (t
, 1)))
4232 || TREE_CODE (t
) == COMPONENT_REF
4233 || TREE_CODE (t
) == REALPART_EXPR
4234 || TREE_CODE (t
) == IMAGPART_EXPR
)
4235 t
= TREE_OPERAND (t
, 0);
4244 /* Called via walk_trees. Verify tree sharing. */
4247 verify_node_sharing (tree
* tp
, int *walk_subtrees
, void *data
)
4249 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
4251 if (tree_node_can_be_shared (*tp
))
4253 *walk_subtrees
= false;
4257 if (pointer_set_insert (visited
, *tp
))
4264 /* Helper function for verify_gimple_tuples. */
4267 verify_gimple_tuples_1 (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
4268 void *data ATTRIBUTE_UNUSED
)
4270 switch (TREE_CODE (*tp
))
4273 error ("unexpected non-tuple");
4283 /* Verify that there are no trees that should have been converted to
4284 gimple tuples. Return true if T contains a node that should have
4285 been converted to a gimple tuple, but hasn't. */
4288 verify_gimple_tuples (tree t
)
4290 return walk_tree (&t
, verify_gimple_tuples_1
, NULL
, NULL
) != NULL
;
4293 static bool eh_error_found
;
4295 verify_eh_throw_stmt_node (void **slot
, void *data
)
4297 struct throw_stmt_node
*node
= (struct throw_stmt_node
*)*slot
;
4298 struct pointer_set_t
*visited
= (struct pointer_set_t
*) data
;
4300 if (!pointer_set_contains (visited
, node
->stmt
))
4302 error ("Dead STMT in EH table");
4303 debug_generic_stmt (node
->stmt
);
4304 eh_error_found
= true;
4309 /* Verify the GIMPLE statement chain. */
4315 block_stmt_iterator bsi
;
4317 struct pointer_set_t
*visited
, *visited_stmts
;
4320 timevar_push (TV_TREE_STMT_VERIFY
);
4321 visited
= pointer_set_create ();
4322 visited_stmts
= pointer_set_create ();
4329 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
4331 int phi_num_args
= PHI_NUM_ARGS (phi
);
4333 pointer_set_insert (visited_stmts
, phi
);
4334 if (bb_for_stmt (phi
) != bb
)
4336 error ("bb_for_stmt (phi) is set to a wrong basic block");
4340 for (i
= 0; i
< phi_num_args
; i
++)
4342 tree t
= PHI_ARG_DEF (phi
, i
);
4347 error ("missing PHI def");
4348 debug_generic_stmt (phi
);
4352 /* Addressable variables do have SSA_NAMEs but they
4353 are not considered gimple values. */
4354 else if (TREE_CODE (t
) != SSA_NAME
4355 && TREE_CODE (t
) != FUNCTION_DECL
4356 && !is_gimple_min_invariant (t
))
4358 error ("PHI def is not a GIMPLE value");
4359 debug_generic_stmt (phi
);
4360 debug_generic_stmt (t
);
4364 addr
= walk_tree (&t
, verify_node_sharing
, visited
, NULL
);
4367 error ("incorrect sharing of tree nodes");
4368 debug_generic_stmt (phi
);
4369 debug_generic_stmt (addr
);
4375 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
4377 tree stmt
= bsi_stmt (bsi
);
4379 pointer_set_insert (visited_stmts
, stmt
);
4380 err
|= verify_gimple_tuples (stmt
);
4382 if (bb_for_stmt (stmt
) != bb
)
4384 error ("bb_for_stmt (stmt) is set to a wrong basic block");
4389 err
|= verify_stmt (stmt
, bsi_end_p (bsi
));
4390 addr
= walk_tree (&stmt
, verify_node_sharing
, visited
, NULL
);
4393 error ("incorrect sharing of tree nodes");
4394 debug_generic_stmt (stmt
);
4395 debug_generic_stmt (addr
);
4400 eh_error_found
= false;
4401 if (get_eh_throw_stmt_table (cfun
))
4402 htab_traverse (get_eh_throw_stmt_table (cfun
),
4403 verify_eh_throw_stmt_node
,
4406 if (err
| eh_error_found
)
4407 internal_error ("verify_stmts failed");
4409 pointer_set_destroy (visited
);
4410 pointer_set_destroy (visited_stmts
);
4411 verify_histograms ();
4412 timevar_pop (TV_TREE_STMT_VERIFY
);
4416 /* Verifies that the flow information is OK. */
4419 tree_verify_flow_info (void)
4423 block_stmt_iterator bsi
;
4428 if (ENTRY_BLOCK_PTR
->il
.tree
)
4430 error ("ENTRY_BLOCK has IL associated with it");
4434 if (EXIT_BLOCK_PTR
->il
.tree
)
4436 error ("EXIT_BLOCK has IL associated with it");
4440 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
4441 if (e
->flags
& EDGE_FALLTHRU
)
4443 error ("fallthru to exit from bb %d", e
->src
->index
);
4449 bool found_ctrl_stmt
= false;
4453 /* Skip labels on the start of basic block. */
4454 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4456 tree prev_stmt
= stmt
;
4458 stmt
= bsi_stmt (bsi
);
4460 if (TREE_CODE (stmt
) != LABEL_EXPR
)
4463 if (prev_stmt
&& DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt
)))
4465 error ("nonlocal label ");
4466 print_generic_expr (stderr
, LABEL_EXPR_LABEL (stmt
), 0);
4467 fprintf (stderr
, " is not first in a sequence of labels in bb %d",
4472 if (label_to_block (LABEL_EXPR_LABEL (stmt
)) != bb
)
4475 print_generic_expr (stderr
, LABEL_EXPR_LABEL (stmt
), 0);
4476 fprintf (stderr
, " to block does not match in bb %d",
4481 if (decl_function_context (LABEL_EXPR_LABEL (stmt
))
4482 != current_function_decl
)
4485 print_generic_expr (stderr
, LABEL_EXPR_LABEL (stmt
), 0);
4486 fprintf (stderr
, " has incorrect context in bb %d",
4492 /* Verify that body of basic block BB is free of control flow. */
4493 for (; !bsi_end_p (bsi
); bsi_next (&bsi
))
4495 tree stmt
= bsi_stmt (bsi
);
4497 if (found_ctrl_stmt
)
4499 error ("control flow in the middle of basic block %d",
4504 if (stmt_ends_bb_p (stmt
))
4505 found_ctrl_stmt
= true;
4507 if (TREE_CODE (stmt
) == LABEL_EXPR
)
4510 print_generic_expr (stderr
, LABEL_EXPR_LABEL (stmt
), 0);
4511 fprintf (stderr
, " in the middle of basic block %d", bb
->index
);
4516 bsi
= bsi_last (bb
);
4517 if (bsi_end_p (bsi
))
4520 stmt
= bsi_stmt (bsi
);
4522 err
|= verify_eh_edges (stmt
);
4524 if (is_ctrl_stmt (stmt
))
4526 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4527 if (e
->flags
& EDGE_FALLTHRU
)
4529 error ("fallthru edge after a control statement in bb %d",
4535 if (TREE_CODE (stmt
) != COND_EXPR
)
4537 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4538 after anything else but if statement. */
4539 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4540 if (e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
))
4542 error ("true/false edge after a non-COND_EXPR in bb %d",
4548 switch (TREE_CODE (stmt
))
4555 if (COND_EXPR_THEN (stmt
) != NULL_TREE
4556 || COND_EXPR_ELSE (stmt
) != NULL_TREE
)
4558 error ("COND_EXPR with code in branches at the end of bb %d",
4563 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
4565 if (!true_edge
|| !false_edge
4566 || !(true_edge
->flags
& EDGE_TRUE_VALUE
)
4567 || !(false_edge
->flags
& EDGE_FALSE_VALUE
)
4568 || (true_edge
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
))
4569 || (false_edge
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
))
4570 || EDGE_COUNT (bb
->succs
) >= 3)
4572 error ("wrong outgoing edge flags at end of bb %d",
4580 if (simple_goto_p (stmt
))
4582 error ("explicit goto at end of bb %d", bb
->index
);
4587 /* FIXME. We should double check that the labels in the
4588 destination blocks have their address taken. */
4589 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4590 if ((e
->flags
& (EDGE_FALLTHRU
| EDGE_TRUE_VALUE
4591 | EDGE_FALSE_VALUE
))
4592 || !(e
->flags
& EDGE_ABNORMAL
))
4594 error ("wrong outgoing edge flags at end of bb %d",
4602 if (!single_succ_p (bb
)
4603 || (single_succ_edge (bb
)->flags
4604 & (EDGE_FALLTHRU
| EDGE_ABNORMAL
4605 | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
4607 error ("wrong outgoing edge flags at end of bb %d", bb
->index
);
4610 if (single_succ (bb
) != EXIT_BLOCK_PTR
)
4612 error ("return edge does not point to exit in bb %d",
4625 vec
= SWITCH_LABELS (stmt
);
4626 n
= TREE_VEC_LENGTH (vec
);
4628 /* Mark all the destination basic blocks. */
4629 for (i
= 0; i
< n
; ++i
)
4631 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
4632 basic_block label_bb
= label_to_block (lab
);
4634 gcc_assert (!label_bb
->aux
|| label_bb
->aux
== (void *)1);
4635 label_bb
->aux
= (void *)1;
4638 /* Verify that the case labels are sorted. */
4639 prev
= TREE_VEC_ELT (vec
, 0);
4640 for (i
= 1; i
< n
; ++i
)
4642 tree c
= TREE_VEC_ELT (vec
, i
);
4647 error ("found default case not at end of case vector");
4652 if (! tree_int_cst_lt (CASE_LOW (prev
), CASE_LOW (c
)))
4654 error ("case labels not sorted: ");
4655 print_generic_expr (stderr
, prev
, 0);
4656 fprintf (stderr
," is greater than ");
4657 print_generic_expr (stderr
, c
, 0);
4658 fprintf (stderr
," but comes before it.\n");
4663 /* VRP will remove the default case if it can prove it will
4664 never be executed. So do not verify there always exists
4665 a default case here. */
4667 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4671 error ("extra outgoing edge %d->%d",
4672 bb
->index
, e
->dest
->index
);
4675 e
->dest
->aux
= (void *)2;
4676 if ((e
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
4677 | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
4679 error ("wrong outgoing edge flags at end of bb %d",
4685 /* Check that we have all of them. */
4686 for (i
= 0; i
< n
; ++i
)
4688 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
4689 basic_block label_bb
= label_to_block (lab
);
4691 if (label_bb
->aux
!= (void *)2)
4693 error ("missing edge %i->%i",
4694 bb
->index
, label_bb
->index
);
4699 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4700 e
->dest
->aux
= (void *)0;
4707 if (dom_info_state (CDI_DOMINATORS
) >= DOM_NO_FAST_QUERY
)
4708 verify_dominators (CDI_DOMINATORS
);
4714 /* Updates phi nodes after creating a forwarder block joined
4715 by edge FALLTHRU. */
4718 tree_make_forwarder_block (edge fallthru
)
4722 basic_block dummy
, bb
;
4723 tree phi
, new_phi
, var
;
4725 dummy
= fallthru
->src
;
4726 bb
= fallthru
->dest
;
4728 if (single_pred_p (bb
))
4731 /* If we redirected a branch we must create new PHI nodes at the
4733 for (phi
= phi_nodes (dummy
); phi
; phi
= PHI_CHAIN (phi
))
4735 var
= PHI_RESULT (phi
);
4736 new_phi
= create_phi_node (var
, bb
);
4737 SSA_NAME_DEF_STMT (var
) = new_phi
;
4738 SET_PHI_RESULT (phi
, make_ssa_name (SSA_NAME_VAR (var
), phi
));
4739 add_phi_arg (new_phi
, PHI_RESULT (phi
), fallthru
);
4742 /* Ensure that the PHI node chain is in the same order. */
4743 set_phi_nodes (bb
, phi_reverse (phi_nodes (bb
)));
4745 /* Add the arguments we have stored on edges. */
4746 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
4751 flush_pending_stmts (e
);
4756 /* Return a non-special label in the head of basic block BLOCK.
4757 Create one if it doesn't exist. */
4760 tree_block_label (basic_block bb
)
4762 block_stmt_iterator i
, s
= bsi_start (bb
);
4766 for (i
= s
; !bsi_end_p (i
); first
= false, bsi_next (&i
))
4768 stmt
= bsi_stmt (i
);
4769 if (TREE_CODE (stmt
) != LABEL_EXPR
)
4771 label
= LABEL_EXPR_LABEL (stmt
);
4772 if (!DECL_NONLOCAL (label
))
4775 bsi_move_before (&i
, &s
);
4780 label
= create_artificial_label ();
4781 stmt
= build1 (LABEL_EXPR
, void_type_node
, label
);
4782 bsi_insert_before (&s
, stmt
, BSI_NEW_STMT
);
4787 /* Attempt to perform edge redirection by replacing a possibly complex
4788 jump instruction by a goto or by removing the jump completely.
4789 This can apply only if all edges now point to the same block. The
4790 parameters and return values are equivalent to
4791 redirect_edge_and_branch. */
4794 tree_try_redirect_by_replacing_jump (edge e
, basic_block target
)
4796 basic_block src
= e
->src
;
4797 block_stmt_iterator b
;
4800 /* We can replace or remove a complex jump only when we have exactly
4802 if (EDGE_COUNT (src
->succs
) != 2
4803 /* Verify that all targets will be TARGET. Specifically, the
4804 edge that is not E must also go to TARGET. */
4805 || EDGE_SUCC (src
, EDGE_SUCC (src
, 0) == e
)->dest
!= target
)
4811 stmt
= bsi_stmt (b
);
4813 if (TREE_CODE (stmt
) == COND_EXPR
4814 || TREE_CODE (stmt
) == SWITCH_EXPR
)
4816 bsi_remove (&b
, true);
4817 e
= ssa_redirect_edge (e
, target
);
4818 e
->flags
= EDGE_FALLTHRU
;
4826 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
4827 edge representing the redirected branch. */
4830 tree_redirect_edge_and_branch (edge e
, basic_block dest
)
4832 basic_block bb
= e
->src
;
4833 block_stmt_iterator bsi
;
4837 if (e
->flags
& EDGE_ABNORMAL
)
4840 if (e
->src
!= ENTRY_BLOCK_PTR
4841 && (ret
= tree_try_redirect_by_replacing_jump (e
, dest
)))
4844 if (e
->dest
== dest
)
4847 bsi
= bsi_last (bb
);
4848 stmt
= bsi_end_p (bsi
) ? NULL
: bsi_stmt (bsi
);
4850 switch (stmt
? TREE_CODE (stmt
) : ERROR_MARK
)
4853 /* For COND_EXPR, we only need to redirect the edge. */
4857 /* No non-abnormal edges should lead from a non-simple goto, and
4858 simple ones should be represented implicitly. */
4863 tree cases
= get_cases_for_edge (e
, stmt
);
4864 tree label
= tree_block_label (dest
);
4866 /* If we have a list of cases associated with E, then use it
4867 as it's a lot faster than walking the entire case vector. */
4870 edge e2
= find_edge (e
->src
, dest
);
4877 CASE_LABEL (cases
) = label
;
4878 cases
= TREE_CHAIN (cases
);
4881 /* If there was already an edge in the CFG, then we need
4882 to move all the cases associated with E to E2. */
4885 tree cases2
= get_cases_for_edge (e2
, stmt
);
4887 TREE_CHAIN (last
) = TREE_CHAIN (cases2
);
4888 TREE_CHAIN (cases2
) = first
;
4893 tree vec
= SWITCH_LABELS (stmt
);
4894 size_t i
, n
= TREE_VEC_LENGTH (vec
);
4896 for (i
= 0; i
< n
; i
++)
4898 tree elt
= TREE_VEC_ELT (vec
, i
);
4900 if (label_to_block (CASE_LABEL (elt
)) == e
->dest
)
4901 CASE_LABEL (elt
) = label
;
4909 bsi_remove (&bsi
, true);
4910 e
->flags
|= EDGE_FALLTHRU
;
4915 case OMP_SECTIONS_SWITCH
:
4917 /* The edges from OMP constructs can be simply redirected. */
4921 /* Otherwise it must be a fallthru edge, and we don't need to
4922 do anything besides redirecting it. */
4923 gcc_assert (e
->flags
& EDGE_FALLTHRU
);
4927 /* Update/insert PHI nodes as necessary. */
4929 /* Now update the edges in the CFG. */
4930 e
= ssa_redirect_edge (e
, dest
);
4935 /* Returns true if it is possible to remove edge E by redirecting
4936 it to the destination of the other edge from E->src. */
4939 tree_can_remove_branch_p (const_edge e
)
4941 if (e
->flags
& EDGE_ABNORMAL
)
4947 /* Simple wrapper, as we can always redirect fallthru edges. */
4950 tree_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4952 e
= tree_redirect_edge_and_branch (e
, dest
);
4959 /* Splits basic block BB after statement STMT (but at least after the
4960 labels). If STMT is NULL, BB is split just after the labels. */
4963 tree_split_block (basic_block bb
, void *stmt
)
4965 block_stmt_iterator bsi
;
4966 tree_stmt_iterator tsi_tgt
;
4972 new_bb
= create_empty_bb (bb
);
4974 /* Redirect the outgoing edges. */
4975 new_bb
->succs
= bb
->succs
;
4977 FOR_EACH_EDGE (e
, ei
, new_bb
->succs
)
4980 if (stmt
&& TREE_CODE ((tree
) stmt
) == LABEL_EXPR
)
4983 /* Move everything from BSI to the new basic block. */
4984 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4986 act
= bsi_stmt (bsi
);
4987 if (TREE_CODE (act
) == LABEL_EXPR
)
5000 if (bsi_end_p (bsi
))
5003 /* Split the statement list - avoid re-creating new containers as this
5004 brings ugly quadratic memory consumption in the inliner.
5005 (We are still quadratic since we need to update stmt BB pointers,
5007 list
= tsi_split_statement_list_before (&bsi
.tsi
);
5008 set_bb_stmt_list (new_bb
, list
);
5009 for (tsi_tgt
= tsi_start (list
);
5010 !tsi_end_p (tsi_tgt
); tsi_next (&tsi_tgt
))
5011 change_bb_for_stmt (tsi_stmt (tsi_tgt
), new_bb
);
5017 /* Moves basic block BB after block AFTER. */
5020 tree_move_block_after (basic_block bb
, basic_block after
)
5022 if (bb
->prev_bb
== after
)
5026 link_block (bb
, after
);
5032 /* Return true if basic_block can be duplicated. */
5035 tree_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED
)
5041 /* Create a duplicate of the basic block BB. NOTE: This does not
5042 preserve SSA form. */
5045 tree_duplicate_bb (basic_block bb
)
5048 block_stmt_iterator bsi
, bsi_tgt
;
5051 new_bb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
5053 /* Copy the PHI nodes. We ignore PHI node arguments here because
5054 the incoming edges have not been setup yet. */
5055 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
5057 tree copy
= create_phi_node (PHI_RESULT (phi
), new_bb
);
5058 create_new_def_for (PHI_RESULT (copy
), copy
, PHI_RESULT_PTR (copy
));
5061 /* Keep the chain of PHI nodes in the same order so that they can be
5062 updated by ssa_redirect_edge. */
5063 set_phi_nodes (new_bb
, phi_reverse (phi_nodes (new_bb
)));
5065 bsi_tgt
= bsi_start (new_bb
);
5066 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
5068 def_operand_p def_p
;
5069 ssa_op_iter op_iter
;
5073 stmt
= bsi_stmt (bsi
);
5074 if (TREE_CODE (stmt
) == LABEL_EXPR
)
5077 /* Create a new copy of STMT and duplicate STMT's virtual
5079 copy
= unshare_expr (stmt
);
5080 bsi_insert_after (&bsi_tgt
, copy
, BSI_NEW_STMT
);
5081 copy_virtual_operands (copy
, stmt
);
5082 region
= lookup_stmt_eh_region (stmt
);
5084 add_stmt_to_eh_region (copy
, region
);
5085 gimple_duplicate_stmt_histograms (cfun
, copy
, cfun
, stmt
);
5087 /* Create new names for all the definitions created by COPY and
5088 add replacement mappings for each new name. */
5089 FOR_EACH_SSA_DEF_OPERAND (def_p
, copy
, op_iter
, SSA_OP_ALL_DEFS
)
5090 create_new_def_for (DEF_FROM_PTR (def_p
), copy
, def_p
);
5096 /* Adds phi node arguments for edge E_COPY after basic block duplication. */
5099 add_phi_args_after_copy_edge (edge e_copy
)
5101 basic_block bb
, bb_copy
= e_copy
->src
, dest
;
5104 tree phi
, phi_copy
, phi_next
, def
;
5106 if (!phi_nodes (e_copy
->dest
))
5109 bb
= bb_copy
->flags
& BB_DUPLICATED
? get_bb_original (bb_copy
) : bb_copy
;
5111 if (e_copy
->dest
->flags
& BB_DUPLICATED
)
5112 dest
= get_bb_original (e_copy
->dest
);
5114 dest
= e_copy
->dest
;
5116 e
= find_edge (bb
, dest
);
5119 /* During loop unrolling the target of the latch edge is copied.
5120 In this case we are not looking for edge to dest, but to
5121 duplicated block whose original was dest. */
5122 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
5124 if ((e
->dest
->flags
& BB_DUPLICATED
)
5125 && get_bb_original (e
->dest
) == dest
)
5129 gcc_assert (e
!= NULL
);
5132 for (phi
= phi_nodes (e
->dest
), phi_copy
= phi_nodes (e_copy
->dest
);
5134 phi
= phi_next
, phi_copy
= PHI_CHAIN (phi_copy
))
5136 phi_next
= PHI_CHAIN (phi
);
5137 def
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
5138 add_phi_arg (phi_copy
, def
, e_copy
);
5143 /* Basic block BB_COPY was created by code duplication. Add phi node
5144 arguments for edges going out of BB_COPY. The blocks that were
5145 duplicated have BB_DUPLICATED set. */
5148 add_phi_args_after_copy_bb (basic_block bb_copy
)
5153 FOR_EACH_EDGE (e_copy
, ei
, bb_copy
->succs
)
5155 add_phi_args_after_copy_edge (e_copy
);
5159 /* Blocks in REGION_COPY array of length N_REGION were created by
5160 duplication of basic blocks. Add phi node arguments for edges
5161 going from these blocks. If E_COPY is not NULL, also add
5162 phi node arguments for its destination.*/
5165 add_phi_args_after_copy (basic_block
*region_copy
, unsigned n_region
,
5170 for (i
= 0; i
< n_region
; i
++)
5171 region_copy
[i
]->flags
|= BB_DUPLICATED
;
5173 for (i
= 0; i
< n_region
; i
++)
5174 add_phi_args_after_copy_bb (region_copy
[i
]);
5176 add_phi_args_after_copy_edge (e_copy
);
5178 for (i
= 0; i
< n_region
; i
++)
5179 region_copy
[i
]->flags
&= ~BB_DUPLICATED
;
5182 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5183 important exit edge EXIT. By important we mean that no SSA name defined
5184 inside region is live over the other exit edges of the region. All entry
5185 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected
5186 to the duplicate of the region. SSA form, dominance and loop information
5187 is updated. The new basic blocks are stored to REGION_COPY in the same
5188 order as they had in REGION, provided that REGION_COPY is not NULL.
5189 The function returns false if it is unable to copy the region,
5193 tree_duplicate_sese_region (edge entry
, edge exit
,
5194 basic_block
*region
, unsigned n_region
,
5195 basic_block
*region_copy
)
5198 bool free_region_copy
= false, copying_header
= false;
5199 struct loop
*loop
= entry
->dest
->loop_father
;
5201 VEC (basic_block
, heap
) *doms
;
5203 int total_freq
= 0, entry_freq
= 0;
5204 gcov_type total_count
= 0, entry_count
= 0;
5206 if (!can_copy_bbs_p (region
, n_region
))
5209 /* Some sanity checking. Note that we do not check for all possible
5210 missuses of the functions. I.e. if you ask to copy something weird,
5211 it will work, but the state of structures probably will not be
5213 for (i
= 0; i
< n_region
; i
++)
5215 /* We do not handle subloops, i.e. all the blocks must belong to the
5217 if (region
[i
]->loop_father
!= loop
)
5220 if (region
[i
] != entry
->dest
5221 && region
[i
] == loop
->header
)
5225 set_loop_copy (loop
, loop
);
5227 /* In case the function is used for loop header copying (which is the primary
5228 use), ensure that EXIT and its copy will be new latch and entry edges. */
5229 if (loop
->header
== entry
->dest
)
5231 copying_header
= true;
5232 set_loop_copy (loop
, loop_outer (loop
));
5234 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
5237 for (i
= 0; i
< n_region
; i
++)
5238 if (region
[i
] != exit
->src
5239 && dominated_by_p (CDI_DOMINATORS
, region
[i
], exit
->src
))
5245 region_copy
= XNEWVEC (basic_block
, n_region
);
5246 free_region_copy
= true;
5249 gcc_assert (!need_ssa_update_p ());
5251 /* Record blocks outside the region that are dominated by something
5254 initialize_original_copy_tables ();
5256 doms
= get_dominated_by_region (CDI_DOMINATORS
, region
, n_region
);
5258 if (entry
->dest
->count
)
5260 total_count
= entry
->dest
->count
;
5261 entry_count
= entry
->count
;
5262 /* Fix up corner cases, to avoid division by zero or creation of negative
5264 if (entry_count
> total_count
)
5265 entry_count
= total_count
;
5269 total_freq
= entry
->dest
->frequency
;
5270 entry_freq
= EDGE_FREQUENCY (entry
);
5271 /* Fix up corner cases, to avoid division by zero or creation of negative
5273 if (total_freq
== 0)
5275 else if (entry_freq
> total_freq
)
5276 entry_freq
= total_freq
;
5279 copy_bbs (region
, n_region
, region_copy
, &exit
, 1, &exit_copy
, loop
,
5280 split_edge_bb_loc (entry
));
5283 scale_bbs_frequencies_gcov_type (region
, n_region
,
5284 total_count
- entry_count
,
5286 scale_bbs_frequencies_gcov_type (region_copy
, n_region
, entry_count
,
5291 scale_bbs_frequencies_int (region
, n_region
, total_freq
- entry_freq
,
5293 scale_bbs_frequencies_int (region_copy
, n_region
, entry_freq
, total_freq
);
5298 loop
->header
= exit
->dest
;
5299 loop
->latch
= exit
->src
;
5302 /* Redirect the entry and add the phi node arguments. */
5303 redirected
= redirect_edge_and_branch (entry
, get_bb_copy (entry
->dest
));
5304 gcc_assert (redirected
!= NULL
);
5305 flush_pending_stmts (entry
);
5307 /* Concerning updating of dominators: We must recount dominators
5308 for entry block and its copy. Anything that is outside of the
5309 region, but was dominated by something inside needs recounting as
5311 set_immediate_dominator (CDI_DOMINATORS
, entry
->dest
, entry
->src
);
5312 VEC_safe_push (basic_block
, heap
, doms
, get_bb_original (entry
->dest
));
5313 iterate_fix_dominators (CDI_DOMINATORS
, doms
, false);
5314 VEC_free (basic_block
, heap
, doms
);
5316 /* Add the other PHI node arguments. */
5317 add_phi_args_after_copy (region_copy
, n_region
, NULL
);
5319 /* Update the SSA web. */
5320 update_ssa (TODO_update_ssa
);
5322 if (free_region_copy
)
5325 free_original_copy_tables ();
5329 /* Duplicates REGION consisting of N_REGION blocks. The new blocks
5330 are stored to REGION_COPY in the same order in that they appear
5331 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to
5332 the region, EXIT an exit from it. The condition guarding EXIT
5333 is moved to ENTRY. Returns true if duplication succeeds, false
5359 tree_duplicate_sese_tail (edge entry
, edge exit
,
5360 basic_block
*region
, unsigned n_region
,
5361 basic_block
*region_copy
)
5364 bool free_region_copy
= false;
5365 struct loop
*loop
= exit
->dest
->loop_father
;
5366 struct loop
*orig_loop
= entry
->dest
->loop_father
;
5367 basic_block switch_bb
, entry_bb
, nentry_bb
;
5368 VEC (basic_block
, heap
) *doms
;
5369 int total_freq
= 0, exit_freq
= 0;
5370 gcov_type total_count
= 0, exit_count
= 0;
5371 edge exits
[2], nexits
[2], e
;
5372 block_stmt_iterator bsi
;
5376 gcc_assert (EDGE_COUNT (exit
->src
->succs
) == 2);
5378 exits
[1] = EDGE_SUCC (exit
->src
, EDGE_SUCC (exit
->src
, 0) == exit
);
5380 if (!can_copy_bbs_p (region
, n_region
))
5383 /* Some sanity checking. Note that we do not check for all possible
5384 missuses of the functions. I.e. if you ask to copy something weird
5385 (e.g., in the example, if there is a jump from inside to the middle
5386 of some_code, or come_code defines some of the values used in cond)
5387 it will work, but the resulting code will not be correct. */
5388 for (i
= 0; i
< n_region
; i
++)
5390 /* We do not handle subloops, i.e. all the blocks must belong to the
5392 if (region
[i
]->loop_father
!= orig_loop
)
5395 if (region
[i
] == orig_loop
->latch
)
5399 initialize_original_copy_tables ();
5400 set_loop_copy (orig_loop
, loop
);
5404 region_copy
= XNEWVEC (basic_block
, n_region
);
5405 free_region_copy
= true;
5408 gcc_assert (!need_ssa_update_p ());
5410 /* Record blocks outside the region that are dominated by something
5412 doms
= get_dominated_by_region (CDI_DOMINATORS
, region
, n_region
);
5414 if (exit
->src
->count
)
5416 total_count
= exit
->src
->count
;
5417 exit_count
= exit
->count
;
5418 /* Fix up corner cases, to avoid division by zero or creation of negative
5420 if (exit_count
> total_count
)
5421 exit_count
= total_count
;
5425 total_freq
= exit
->src
->frequency
;
5426 exit_freq
= EDGE_FREQUENCY (exit
);
5427 /* Fix up corner cases, to avoid division by zero or creation of negative
5429 if (total_freq
== 0)
5431 if (exit_freq
> total_freq
)
5432 exit_freq
= total_freq
;
5435 copy_bbs (region
, n_region
, region_copy
, exits
, 2, nexits
, orig_loop
,
5436 split_edge_bb_loc (exit
));
5439 scale_bbs_frequencies_gcov_type (region
, n_region
,
5440 total_count
- exit_count
,
5442 scale_bbs_frequencies_gcov_type (region_copy
, n_region
, exit_count
,
5447 scale_bbs_frequencies_int (region
, n_region
, total_freq
- exit_freq
,
5449 scale_bbs_frequencies_int (region_copy
, n_region
, exit_freq
, total_freq
);
5452 /* Create the switch block, and put the exit condition to it. */
5453 entry_bb
= entry
->dest
;
5454 nentry_bb
= get_bb_copy (entry_bb
);
5455 if (!last_stmt (entry
->src
)
5456 || !stmt_ends_bb_p (last_stmt (entry
->src
)))
5457 switch_bb
= entry
->src
;
5459 switch_bb
= split_edge (entry
);
5460 set_immediate_dominator (CDI_DOMINATORS
, nentry_bb
, switch_bb
);
5462 bsi
= bsi_last (switch_bb
);
5463 cond
= last_stmt (exit
->src
);
5464 gcc_assert (TREE_CODE (cond
) == COND_EXPR
);
5465 bsi_insert_after (&bsi
, unshare_expr (cond
), BSI_NEW_STMT
);
5467 sorig
= single_succ_edge (switch_bb
);
5468 sorig
->flags
= exits
[1]->flags
;
5469 snew
= make_edge (switch_bb
, nentry_bb
, exits
[0]->flags
);
5471 /* Register the new edge from SWITCH_BB in loop exit lists. */
5472 rescan_loop_exit (snew
, true, false);
5474 /* Add the PHI node arguments. */
5475 add_phi_args_after_copy (region_copy
, n_region
, snew
);
5477 /* Get rid of now superfluous conditions and associated edges (and phi node
5479 e
= redirect_edge_and_branch (exits
[0], exits
[1]->dest
);
5480 PENDING_STMT (e
) = NULL_TREE
;
5481 e
= redirect_edge_and_branch (nexits
[1], nexits
[0]->dest
);
5482 PENDING_STMT (e
) = NULL_TREE
;
5484 /* Anything that is outside of the region, but was dominated by something
5485 inside needs to update dominance info. */
5486 iterate_fix_dominators (CDI_DOMINATORS
, doms
, false);
5487 VEC_free (basic_block
, heap
, doms
);
5489 /* Update the SSA web. */
5490 update_ssa (TODO_update_ssa
);
5492 if (free_region_copy
)
5495 free_original_copy_tables ();
5500 DEF_VEC_P(basic_block);
5501 DEF_VEC_ALLOC_P(basic_block,heap);
5504 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop
5505 adding blocks when the dominator traversal reaches EXIT. This
5506 function silently assumes that ENTRY strictly dominates EXIT. */
5509 gather_blocks_in_sese_region (basic_block entry
, basic_block exit
,
5510 VEC(basic_block
,heap
) **bbs_p
)
5514 for (son
= first_dom_son (CDI_DOMINATORS
, entry
);
5516 son
= next_dom_son (CDI_DOMINATORS
, son
))
5518 VEC_safe_push (basic_block
, heap
, *bbs_p
, son
);
5520 gather_blocks_in_sese_region (son
, exit
, bbs_p
);
5524 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5525 The duplicates are recorded in VARS_MAP. */
5528 replace_by_duplicate_decl (tree
*tp
, struct pointer_map_t
*vars_map
,
5531 tree t
= *tp
, new_t
;
5532 struct function
*f
= DECL_STRUCT_FUNCTION (to_context
);
5535 if (DECL_CONTEXT (t
) == to_context
)
5538 loc
= pointer_map_contains (vars_map
, t
);
5542 loc
= pointer_map_insert (vars_map
, t
);
5546 new_t
= copy_var_decl (t
, DECL_NAME (t
), TREE_TYPE (t
));
5547 f
->local_decls
= tree_cons (NULL_TREE
, new_t
, f
->local_decls
);
5551 gcc_assert (TREE_CODE (t
) == CONST_DECL
);
5552 new_t
= copy_node (t
);
5554 DECL_CONTEXT (new_t
) = to_context
;
5564 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5565 VARS_MAP maps old ssa names and var_decls to the new ones. */
5568 replace_ssa_name (tree name
, struct pointer_map_t
*vars_map
,
5572 tree new_name
, decl
= SSA_NAME_VAR (name
);
5574 gcc_assert (is_gimple_reg (name
));
5576 loc
= pointer_map_contains (vars_map
, name
);
5580 replace_by_duplicate_decl (&decl
, vars_map
, to_context
);
5582 push_cfun (DECL_STRUCT_FUNCTION (to_context
));
5583 if (gimple_in_ssa_p (cfun
))
5584 add_referenced_var (decl
);
5586 new_name
= make_ssa_name (decl
, SSA_NAME_DEF_STMT (name
));
5587 if (SSA_NAME_IS_DEFAULT_DEF (name
))
5588 set_default_def (decl
, new_name
);
5591 loc
= pointer_map_insert (vars_map
, name
);
5605 struct pointer_map_t
*vars_map
;
5606 htab_t new_label_map
;
5610 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression
5611 contained in *TP and change the DECL_CONTEXT of every local
5612 variable referenced in *TP. */
5615 move_stmt_r (tree
*tp
, int *walk_subtrees
, void *data
)
5617 struct move_stmt_d
*p
= (struct move_stmt_d
*) data
;
5621 && (EXPR_P (t
) || GIMPLE_STMT_P (t
)))
5622 TREE_BLOCK (t
) = p
->block
;
5624 if (OMP_DIRECTIVE_P (t
)
5625 && TREE_CODE (t
) != OMP_RETURN
5626 && TREE_CODE (t
) != OMP_CONTINUE
)
5628 /* Do not remap variables inside OMP directives. Variables
5629 referenced in clauses and directive header belong to the
5630 parent function and should not be moved into the child
5632 bool save_remap_decls_p
= p
->remap_decls_p
;
5633 p
->remap_decls_p
= false;
5636 walk_tree (&OMP_BODY (t
), move_stmt_r
, p
, NULL
);
5638 p
->remap_decls_p
= save_remap_decls_p
;
5640 else if (DECL_P (t
) || TREE_CODE (t
) == SSA_NAME
)
5642 if (TREE_CODE (t
) == SSA_NAME
)
5643 *tp
= replace_ssa_name (t
, p
->vars_map
, p
->to_context
);
5644 else if (TREE_CODE (t
) == LABEL_DECL
)
5646 if (p
->new_label_map
)
5648 struct tree_map in
, *out
;
5650 out
= htab_find_with_hash (p
->new_label_map
, &in
, DECL_UID (t
));
5655 DECL_CONTEXT (t
) = p
->to_context
;
5657 else if (p
->remap_decls_p
)
5659 /* Replace T with its duplicate. T should no longer appear in the
5660 parent function, so this looks wasteful; however, it may appear
5661 in referenced_vars, and more importantly, as virtual operands of
5662 statements, and in alias lists of other variables. It would be
5663 quite difficult to expunge it from all those places. ??? It might
5664 suffice to do this for addressable variables. */
5665 if ((TREE_CODE (t
) == VAR_DECL
5666 && !is_global_var (t
))
5667 || TREE_CODE (t
) == CONST_DECL
)
5668 replace_by_duplicate_decl (tp
, p
->vars_map
, p
->to_context
);
5671 && gimple_in_ssa_p (cfun
))
5673 push_cfun (DECL_STRUCT_FUNCTION (p
->to_context
));
5674 add_referenced_var (*tp
);
5680 else if (TYPE_P (t
))
5686 /* Marks virtual operands of all statements in basic blocks BBS for
5690 mark_virtual_ops_in_bb (basic_block bb
)
5693 block_stmt_iterator bsi
;
5695 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
5696 mark_virtual_ops_for_renaming (phi
);
5698 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
5699 mark_virtual_ops_for_renaming (bsi_stmt (bsi
));
5702 /* Marks virtual operands of all statements in basic blocks BBS for
5706 mark_virtual_ops_in_region (VEC (basic_block
,heap
) *bbs
)
5711 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, bb
); i
++)
5712 mark_virtual_ops_in_bb (bb
);
5715 /* Move basic block BB from function CFUN to function DEST_FN. The
5716 block is moved out of the original linked list and placed after
5717 block AFTER in the new list. Also, the block is removed from the
5718 original array of blocks and placed in DEST_FN's array of blocks.
5719 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5720 updated to reflect the moved edges.
5722 The local variables are remapped to new instances, VARS_MAP is used
5723 to record the mapping. */
5726 move_block_to_fn (struct function
*dest_cfun
, basic_block bb
,
5727 basic_block after
, bool update_edge_count_p
,
5728 struct pointer_map_t
*vars_map
, htab_t new_label_map
,
5731 struct control_flow_graph
*cfg
;
5734 block_stmt_iterator si
;
5735 struct move_stmt_d d
;
5736 unsigned old_len
, new_len
;
5739 /* Remove BB from dominance structures. */
5740 delete_from_dominance_info (CDI_DOMINATORS
, bb
);
5742 remove_bb_from_loops (bb
);
5744 /* Link BB to the new linked list. */
5745 move_block_after (bb
, after
);
5747 /* Update the edge count in the corresponding flowgraphs. */
5748 if (update_edge_count_p
)
5749 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
5751 cfun
->cfg
->x_n_edges
--;
5752 dest_cfun
->cfg
->x_n_edges
++;
5755 /* Remove BB from the original basic block array. */
5756 VEC_replace (basic_block
, cfun
->cfg
->x_basic_block_info
, bb
->index
, NULL
);
5757 cfun
->cfg
->x_n_basic_blocks
--;
5759 /* Grow DEST_CFUN's basic block array if needed. */
5760 cfg
= dest_cfun
->cfg
;
5761 cfg
->x_n_basic_blocks
++;
5762 if (bb
->index
>= cfg
->x_last_basic_block
)
5763 cfg
->x_last_basic_block
= bb
->index
+ 1;
5765 old_len
= VEC_length (basic_block
, cfg
->x_basic_block_info
);
5766 if ((unsigned) cfg
->x_last_basic_block
>= old_len
)
5768 new_len
= cfg
->x_last_basic_block
+ (cfg
->x_last_basic_block
+ 3) / 4;
5769 VEC_safe_grow_cleared (basic_block
, gc
, cfg
->x_basic_block_info
,
5773 VEC_replace (basic_block
, cfg
->x_basic_block_info
,
5776 /* Remap the variables in phi nodes. */
5777 for (phi
= phi_nodes (bb
); phi
; phi
= next_phi
)
5780 tree op
= PHI_RESULT (phi
);
5783 next_phi
= PHI_CHAIN (phi
);
5784 if (!is_gimple_reg (op
))
5786 /* Remove the phi nodes for virtual operands (alias analysis will be
5787 run for the new function, anyway). */
5788 remove_phi_node (phi
, NULL
, true);
5792 SET_PHI_RESULT (phi
, replace_ssa_name (op
, vars_map
, dest_cfun
->decl
));
5793 FOR_EACH_PHI_ARG (use
, phi
, oi
, SSA_OP_USE
)
5795 op
= USE_FROM_PTR (use
);
5796 if (TREE_CODE (op
) == SSA_NAME
)
5797 SET_USE (use
, replace_ssa_name (op
, vars_map
, dest_cfun
->decl
));
5801 /* The statements in BB need to be associated with a new TREE_BLOCK.
5802 Labels need to be associated with a new label-to-block map. */
5803 memset (&d
, 0, sizeof (d
));
5804 d
.vars_map
= vars_map
;
5805 d
.from_context
= cfun
->decl
;
5806 d
.to_context
= dest_cfun
->decl
;
5807 d
.new_label_map
= new_label_map
;
5809 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
5811 tree stmt
= bsi_stmt (si
);
5814 d
.remap_decls_p
= true;
5815 if (TREE_BLOCK (stmt
))
5816 d
.block
= DECL_INITIAL (dest_cfun
->decl
);
5818 walk_tree (&stmt
, move_stmt_r
, &d
, NULL
);
5820 if (TREE_CODE (stmt
) == LABEL_EXPR
)
5822 tree label
= LABEL_EXPR_LABEL (stmt
);
5823 int uid
= LABEL_DECL_UID (label
);
5825 gcc_assert (uid
> -1);
5827 old_len
= VEC_length (basic_block
, cfg
->x_label_to_block_map
);
5828 if (old_len
<= (unsigned) uid
)
5830 new_len
= 3 * uid
/ 2;
5831 VEC_safe_grow_cleared (basic_block
, gc
,
5832 cfg
->x_label_to_block_map
, new_len
);
5835 VEC_replace (basic_block
, cfg
->x_label_to_block_map
, uid
, bb
);
5836 VEC_replace (basic_block
, cfun
->cfg
->x_label_to_block_map
, uid
, NULL
);
5838 gcc_assert (DECL_CONTEXT (label
) == dest_cfun
->decl
);
5840 if (uid
>= dest_cfun
->cfg
->last_label_uid
)
5841 dest_cfun
->cfg
->last_label_uid
= uid
+ 1;
5843 else if (TREE_CODE (stmt
) == RESX_EXPR
&& eh_offset
!= 0)
5844 TREE_OPERAND (stmt
, 0) =
5845 build_int_cst (NULL_TREE
,
5846 TREE_INT_CST_LOW (TREE_OPERAND (stmt
, 0))
5849 region
= lookup_stmt_eh_region (stmt
);
5852 add_stmt_to_eh_region_fn (dest_cfun
, stmt
, region
+ eh_offset
);
5853 remove_stmt_from_eh_region (stmt
);
5854 gimple_duplicate_stmt_histograms (dest_cfun
, stmt
, cfun
, stmt
);
5855 gimple_remove_stmt_histograms (cfun
, stmt
);
5858 /* We cannot leave any operands allocated from the operand caches of
5859 the current function. */
5860 free_stmt_operands (stmt
);
5861 push_cfun (dest_cfun
);
5867 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5868 the outermost EH region. Use REGION as the incoming base EH region. */
5871 find_outermost_region_in_block (struct function
*src_cfun
,
5872 basic_block bb
, int region
)
5874 block_stmt_iterator si
;
5876 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
5878 tree stmt
= bsi_stmt (si
);
5881 if (TREE_CODE (stmt
) == RESX_EXPR
)
5882 stmt_region
= TREE_INT_CST_LOW (TREE_OPERAND (stmt
, 0));
5884 stmt_region
= lookup_stmt_eh_region_fn (src_cfun
, stmt
);
5885 if (stmt_region
> 0)
5888 region
= stmt_region
;
5889 else if (stmt_region
!= region
)
5891 region
= eh_region_outermost (src_cfun
, stmt_region
, region
);
5892 gcc_assert (region
!= -1);
5901 new_label_mapper (tree decl
, void *data
)
5903 htab_t hash
= (htab_t
) data
;
5907 gcc_assert (TREE_CODE (decl
) == LABEL_DECL
);
5909 m
= xmalloc (sizeof (struct tree_map
));
5910 m
->hash
= DECL_UID (decl
);
5911 m
->base
.from
= decl
;
5912 m
->to
= create_artificial_label ();
5913 LABEL_DECL_UID (m
->to
) = LABEL_DECL_UID (decl
);
5914 if (LABEL_DECL_UID (m
->to
) >= cfun
->cfg
->last_label_uid
)
5915 cfun
->cfg
->last_label_uid
= LABEL_DECL_UID (m
->to
) + 1;
5917 slot
= htab_find_slot_with_hash (hash
, m
, m
->hash
, INSERT
);
5918 gcc_assert (*slot
== NULL
);
5925 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5926 EXIT_BB to function DEST_CFUN. The whole region is replaced by a
5927 single basic block in the original CFG and the new basic block is
5928 returned. DEST_CFUN must not have a CFG yet.
5930 Note that the region need not be a pure SESE region. Blocks inside
5931 the region may contain calls to abort/exit. The only restriction
5932 is that ENTRY_BB should be the only entry point and it must
5935 All local variables referenced in the region are assumed to be in
5936 the corresponding BLOCK_VARS and unexpanded variable lists
5937 associated with DEST_CFUN. */
5940 move_sese_region_to_fn (struct function
*dest_cfun
, basic_block entry_bb
,
5941 basic_block exit_bb
)
5943 VEC(basic_block
,heap
) *bbs
, *dom_bbs
;
5944 basic_block dom_entry
= get_immediate_dominator (CDI_DOMINATORS
, entry_bb
);
5945 basic_block after
, bb
, *entry_pred
, *exit_succ
, abb
;
5946 struct function
*saved_cfun
= cfun
;
5947 int *entry_flag
, *exit_flag
, eh_offset
;
5948 unsigned *entry_prob
, *exit_prob
;
5949 unsigned i
, num_entry_edges
, num_exit_edges
;
5952 htab_t new_label_map
;
5953 struct pointer_map_t
*vars_map
;
5954 struct loop
*loop
= entry_bb
->loop_father
;
5956 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5958 gcc_assert (entry_bb
!= exit_bb
5960 || dominated_by_p (CDI_DOMINATORS
, exit_bb
, entry_bb
)));
5962 /* Collect all the blocks in the region. Manually add ENTRY_BB
5963 because it won't be added by dfs_enumerate_from. */
5965 VEC_safe_push (basic_block
, heap
, bbs
, entry_bb
);
5966 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &bbs
);
5968 /* The blocks that used to be dominated by something in BBS will now be
5969 dominated by the new block. */
5970 dom_bbs
= get_dominated_by_region (CDI_DOMINATORS
,
5971 VEC_address (basic_block
, bbs
),
5972 VEC_length (basic_block
, bbs
));
5974 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember
5975 the predecessor edges to ENTRY_BB and the successor edges to
5976 EXIT_BB so that we can re-attach them to the new basic block that
5977 will replace the region. */
5978 num_entry_edges
= EDGE_COUNT (entry_bb
->preds
);
5979 entry_pred
= (basic_block
*) xcalloc (num_entry_edges
, sizeof (basic_block
));
5980 entry_flag
= (int *) xcalloc (num_entry_edges
, sizeof (int));
5981 entry_prob
= XNEWVEC (unsigned, num_entry_edges
);
5983 for (ei
= ei_start (entry_bb
->preds
); (e
= ei_safe_edge (ei
)) != NULL
;)
5985 entry_prob
[i
] = e
->probability
;
5986 entry_flag
[i
] = e
->flags
;
5987 entry_pred
[i
++] = e
->src
;
5993 num_exit_edges
= EDGE_COUNT (exit_bb
->succs
);
5994 exit_succ
= (basic_block
*) xcalloc (num_exit_edges
,
5995 sizeof (basic_block
));
5996 exit_flag
= (int *) xcalloc (num_exit_edges
, sizeof (int));
5997 exit_prob
= XNEWVEC (unsigned, num_exit_edges
);
5999 for (ei
= ei_start (exit_bb
->succs
); (e
= ei_safe_edge (ei
)) != NULL
;)
6001 exit_prob
[i
] = e
->probability
;
6002 exit_flag
[i
] = e
->flags
;
6003 exit_succ
[i
++] = e
->dest
;
6015 /* Switch context to the child function to initialize DEST_FN's CFG. */
6016 gcc_assert (dest_cfun
->cfg
== NULL
);
6017 push_cfun (dest_cfun
);
6019 init_empty_tree_cfg ();
6021 /* Initialize EH information for the new function. */
6023 new_label_map
= NULL
;
6028 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, bb
); i
++)
6029 region
= find_outermost_region_in_block (saved_cfun
, bb
, region
);
6031 init_eh_for_function ();
6034 new_label_map
= htab_create (17, tree_map_hash
, tree_map_eq
, free
);
6035 eh_offset
= duplicate_eh_regions (saved_cfun
, new_label_mapper
,
6036 new_label_map
, region
, 0);
6042 /* The ssa form for virtual operands in the source function will have to
6043 be repaired. We do not care for the real operands -- the sese region
6044 must be closed with respect to those. */
6045 mark_virtual_ops_in_region (bbs
);
6047 /* Move blocks from BBS into DEST_CFUN. */
6048 gcc_assert (VEC_length (basic_block
, bbs
) >= 2);
6049 after
= dest_cfun
->cfg
->x_entry_block_ptr
;
6050 vars_map
= pointer_map_create ();
6051 for (i
= 0; VEC_iterate (basic_block
, bbs
, i
, bb
); i
++)
6053 /* No need to update edge counts on the last block. It has
6054 already been updated earlier when we detached the region from
6055 the original CFG. */
6056 move_block_to_fn (dest_cfun
, bb
, after
, bb
!= exit_bb
, vars_map
,
6057 new_label_map
, eh_offset
);
6062 htab_delete (new_label_map
);
6063 pointer_map_destroy (vars_map
);
6065 /* Rewire the entry and exit blocks. The successor to the entry
6066 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6067 the child function. Similarly, the predecessor of DEST_FN's
6068 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We
6069 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6070 various CFG manipulation function get to the right CFG.
6072 FIXME, this is silly. The CFG ought to become a parameter to
6074 push_cfun (dest_cfun
);
6075 make_edge (ENTRY_BLOCK_PTR
, entry_bb
, EDGE_FALLTHRU
);
6077 make_edge (exit_bb
, EXIT_BLOCK_PTR
, 0);
6080 /* Back in the original function, the SESE region has disappeared,
6081 create a new basic block in its place. */
6082 bb
= create_empty_bb (entry_pred
[0]);
6084 add_bb_to_loop (bb
, loop
);
6085 for (i
= 0; i
< num_entry_edges
; i
++)
6087 e
= make_edge (entry_pred
[i
], bb
, entry_flag
[i
]);
6088 e
->probability
= entry_prob
[i
];
6091 for (i
= 0; i
< num_exit_edges
; i
++)
6093 e
= make_edge (bb
, exit_succ
[i
], exit_flag
[i
]);
6094 e
->probability
= exit_prob
[i
];
6097 set_immediate_dominator (CDI_DOMINATORS
, bb
, dom_entry
);
6098 for (i
= 0; VEC_iterate (basic_block
, dom_bbs
, i
, abb
); i
++)
6099 set_immediate_dominator (CDI_DOMINATORS
, abb
, bb
);
6100 VEC_free (basic_block
, heap
, dom_bbs
);
6111 VEC_free (basic_block
, heap
, bbs
);
6117 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
6120 dump_function_to_file (tree fn
, FILE *file
, int flags
)
6122 tree arg
, vars
, var
;
6123 struct function
*dsf
;
6124 bool ignore_topmost_bind
= false, any_var
= false;
6128 fprintf (file
, "%s (", lang_hooks
.decl_printable_name (fn
, 2));
6130 arg
= DECL_ARGUMENTS (fn
);
6133 print_generic_expr (file
, TREE_TYPE (arg
), dump_flags
);
6134 fprintf (file
, " ");
6135 print_generic_expr (file
, arg
, dump_flags
);
6136 if (TREE_CHAIN (arg
))
6137 fprintf (file
, ", ");
6138 arg
= TREE_CHAIN (arg
);
6140 fprintf (file
, ")\n");
6142 dsf
= DECL_STRUCT_FUNCTION (fn
);
6143 if (dsf
&& (flags
& TDF_DETAILS
))
6144 dump_eh_tree (file
, dsf
);
6146 if (flags
& TDF_RAW
)
6148 dump_node (fn
, TDF_SLIM
| flags
, file
);
6152 /* Switch CFUN to point to FN. */
6153 push_cfun (DECL_STRUCT_FUNCTION (fn
));
6155 /* When GIMPLE is lowered, the variables are no longer available in
6156 BIND_EXPRs, so display them separately. */
6157 if (cfun
&& cfun
->decl
== fn
&& cfun
->local_decls
)
6159 ignore_topmost_bind
= true;
6161 fprintf (file
, "{\n");
6162 for (vars
= cfun
->local_decls
; vars
; vars
= TREE_CHAIN (vars
))
6164 var
= TREE_VALUE (vars
);
6166 print_generic_decl (file
, var
, flags
);
6167 fprintf (file
, "\n");
6173 if (cfun
&& cfun
->decl
== fn
&& cfun
->cfg
&& basic_block_info
)
6175 /* Make a CFG based dump. */
6176 check_bb_profile (ENTRY_BLOCK_PTR
, file
);
6177 if (!ignore_topmost_bind
)
6178 fprintf (file
, "{\n");
6180 if (any_var
&& n_basic_blocks
)
6181 fprintf (file
, "\n");
6184 dump_generic_bb (file
, bb
, 2, flags
);
6186 fprintf (file
, "}\n");
6187 check_bb_profile (EXIT_BLOCK_PTR
, file
);
6193 /* Make a tree based dump. */
6194 chain
= DECL_SAVED_TREE (fn
);
6196 if (chain
&& TREE_CODE (chain
) == BIND_EXPR
)
6198 if (ignore_topmost_bind
)
6200 chain
= BIND_EXPR_BODY (chain
);
6208 if (!ignore_topmost_bind
)
6209 fprintf (file
, "{\n");
6214 fprintf (file
, "\n");
6216 print_generic_stmt_indented (file
, chain
, flags
, indent
);
6217 if (ignore_topmost_bind
)
6218 fprintf (file
, "}\n");
6221 fprintf (file
, "\n\n");
6228 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */
6231 debug_function (tree fn
, int flags
)
6233 dump_function_to_file (fn
, stderr
, flags
);
6237 /* Print on FILE the indexes for the predecessors of basic_block BB. */
6240 print_pred_bbs (FILE *file
, basic_block bb
)
6245 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
6246 fprintf (file
, "bb_%d ", e
->src
->index
);
6250 /* Print on FILE the indexes for the successors of basic_block BB. */
6253 print_succ_bbs (FILE *file
, basic_block bb
)
6258 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6259 fprintf (file
, "bb_%d ", e
->dest
->index
);
6262 /* Print to FILE the basic block BB following the VERBOSITY level. */
6265 print_loops_bb (FILE *file
, basic_block bb
, int indent
, int verbosity
)
6267 char *s_indent
= (char *) alloca ((size_t) indent
+ 1);
6268 memset ((void *) s_indent
, ' ', (size_t) indent
);
6269 s_indent
[indent
] = '\0';
6271 /* Print basic_block's header. */
6274 fprintf (file
, "%s bb_%d (preds = {", s_indent
, bb
->index
);
6275 print_pred_bbs (file
, bb
);
6276 fprintf (file
, "}, succs = {");
6277 print_succ_bbs (file
, bb
);
6278 fprintf (file
, "})\n");
6281 /* Print basic_block's body. */
6284 fprintf (file
, "%s {\n", s_indent
);
6285 tree_dump_bb (bb
, file
, indent
+ 4);
6286 fprintf (file
, "%s }\n", s_indent
);
6290 static void print_loop_and_siblings (FILE *, struct loop
*, int, int);
6292 /* Pretty print LOOP on FILE, indented INDENT spaces. Following
6293 VERBOSITY level this outputs the contents of the loop, or just its
6297 print_loop (FILE *file
, struct loop
*loop
, int indent
, int verbosity
)
6305 s_indent
= (char *) alloca ((size_t) indent
+ 1);
6306 memset ((void *) s_indent
, ' ', (size_t) indent
);
6307 s_indent
[indent
] = '\0';
6309 /* Print loop's header. */
6310 fprintf (file
, "%sloop_%d (header = %d, latch = %d", s_indent
,
6311 loop
->num
, loop
->header
->index
, loop
->latch
->index
);
6312 fprintf (file
, ", niter = ");
6313 print_generic_expr (file
, loop
->nb_iterations
, 0);
6315 if (loop
->any_upper_bound
)
6317 fprintf (file
, ", upper_bound = ");
6318 dump_double_int (file
, loop
->nb_iterations_upper_bound
, true);
6321 if (loop
->any_estimate
)
6323 fprintf (file
, ", estimate = ");
6324 dump_double_int (file
, loop
->nb_iterations_estimate
, true);
6326 fprintf (file
, ")\n");
6328 /* Print loop's body. */
6331 fprintf (file
, "%s{\n", s_indent
);
6333 if (bb
->loop_father
== loop
)
6334 print_loops_bb (file
, bb
, indent
, verbosity
);
6336 print_loop_and_siblings (file
, loop
->inner
, indent
+ 2, verbosity
);
6337 fprintf (file
, "%s}\n", s_indent
);
6341 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6342 spaces. Following VERBOSITY level this outputs the contents of the
6343 loop, or just its structure. */
6346 print_loop_and_siblings (FILE *file
, struct loop
*loop
, int indent
, int verbosity
)
6351 print_loop (file
, loop
, indent
, verbosity
);
6352 print_loop_and_siblings (file
, loop
->next
, indent
, verbosity
);
6355 /* Follow a CFG edge from the entry point of the program, and on entry
6356 of a loop, pretty print the loop structure on FILE. */
6359 print_loops (FILE *file
, int verbosity
)
6363 bb
= BASIC_BLOCK (NUM_FIXED_BLOCKS
);
6364 if (bb
&& bb
->loop_father
)
6365 print_loop_and_siblings (file
, bb
->loop_father
, 0, verbosity
);
6369 /* Debugging loops structure at tree level, at some VERBOSITY level. */
6372 debug_loops (int verbosity
)
6374 print_loops (stderr
, verbosity
);
6377 /* Print on stderr the code of LOOP, at some VERBOSITY level. */
6380 debug_loop (struct loop
*loop
, int verbosity
)
6382 print_loop (stderr
, loop
, 0, verbosity
);
6385 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6389 debug_loop_num (unsigned num
, int verbosity
)
6391 debug_loop (get_loop (num
), verbosity
);
6394 /* Return true if BB ends with a call, possibly followed by some
6395 instructions that must stay with the call. Return false,
6399 tree_block_ends_with_call_p (basic_block bb
)
6401 block_stmt_iterator bsi
= bsi_last (bb
);
6402 return get_call_expr_in (bsi_stmt (bsi
)) != NULL
;
6406 /* Return true if BB ends with a conditional branch. Return false,
6410 tree_block_ends_with_condjump_p (const_basic_block bb
)
6412 /* This CONST_CAST is okay because last_stmt doesn't modify its
6413 argument and the return value is not modified. */
6414 const_tree stmt
= last_stmt (CONST_CAST_BB(bb
));
6415 return (stmt
&& TREE_CODE (stmt
) == COND_EXPR
);
6419 /* Return true if we need to add fake edge to exit at statement T.
6420 Helper function for tree_flow_call_edges_add. */
6423 need_fake_edge_p (tree t
)
6425 tree call
, fndecl
= NULL_TREE
;
6428 /* NORETURN and LONGJMP calls already have an edge to exit.
6429 CONST and PURE calls do not need one.
6430 We don't currently check for CONST and PURE here, although
6431 it would be a good idea, because those attributes are
6432 figured out from the RTL in mark_constant_function, and
6433 the counter incrementation code from -fprofile-arcs
6434 leads to different results from -fbranch-probabilities. */
6435 call
= get_call_expr_in (t
);
6438 fndecl
= get_callee_fndecl (call
);
6439 call_flags
= call_expr_flags (call
);
6442 if (call
&& fndecl
&& DECL_BUILT_IN (fndecl
)
6443 && (call_flags
& ECF_NOTHROW
)
6444 && !(call_flags
& ECF_NORETURN
)
6445 && !(call_flags
& ECF_RETURNS_TWICE
))
6448 if (call
&& !(call_flags
& ECF_NORETURN
))
6451 if (TREE_CODE (t
) == ASM_EXPR
6452 && (ASM_VOLATILE_P (t
) || ASM_INPUT_P (t
)))
6459 /* Add fake edges to the function exit for any non constant and non
6460 noreturn calls, volatile inline assembly in the bitmap of blocks
6461 specified by BLOCKS or to the whole CFG if BLOCKS is zero. Return
6462 the number of blocks that were split.
6464 The goal is to expose cases in which entering a basic block does
6465 not imply that all subsequent instructions must be executed. */
6468 tree_flow_call_edges_add (sbitmap blocks
)
6471 int blocks_split
= 0;
6472 int last_bb
= last_basic_block
;
6473 bool check_last_block
= false;
6475 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
6479 check_last_block
= true;
6481 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
6483 /* In the last basic block, before epilogue generation, there will be
6484 a fallthru edge to EXIT. Special care is required if the last insn
6485 of the last basic block is a call because make_edge folds duplicate
6486 edges, which would result in the fallthru edge also being marked
6487 fake, which would result in the fallthru edge being removed by
6488 remove_fake_edges, which would result in an invalid CFG.
6490 Moreover, we can't elide the outgoing fake edge, since the block
6491 profiler needs to take this into account in order to solve the minimal
6492 spanning tree in the case that the call doesn't return.
6494 Handle this by adding a dummy instruction in a new last basic block. */
6495 if (check_last_block
)
6497 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
6498 block_stmt_iterator bsi
= bsi_last (bb
);
6500 if (!bsi_end_p (bsi
))
6503 if (t
&& need_fake_edge_p (t
))
6507 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
6510 bsi_insert_on_edge (e
, build_empty_stmt ());
6511 bsi_commit_edge_inserts ();
6516 /* Now add fake edges to the function exit for any non constant
6517 calls since there is no way that we can determine if they will
6519 for (i
= 0; i
< last_bb
; i
++)
6521 basic_block bb
= BASIC_BLOCK (i
);
6522 block_stmt_iterator bsi
;
6523 tree stmt
, last_stmt
;
6528 if (blocks
&& !TEST_BIT (blocks
, i
))
6531 bsi
= bsi_last (bb
);
6532 if (!bsi_end_p (bsi
))
6534 last_stmt
= bsi_stmt (bsi
);
6537 stmt
= bsi_stmt (bsi
);
6538 if (need_fake_edge_p (stmt
))
6541 /* The handling above of the final block before the
6542 epilogue should be enough to verify that there is
6543 no edge to the exit block in CFG already.
6544 Calling make_edge in such case would cause us to
6545 mark that edge as fake and remove it later. */
6546 #ifdef ENABLE_CHECKING
6547 if (stmt
== last_stmt
)
6549 e
= find_edge (bb
, EXIT_BLOCK_PTR
);
6550 gcc_assert (e
== NULL
);
6554 /* Note that the following may create a new basic block
6555 and renumber the existing basic blocks. */
6556 if (stmt
!= last_stmt
)
6558 e
= split_block (bb
, stmt
);
6562 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
6566 while (!bsi_end_p (bsi
));
6571 verify_flow_info ();
6573 return blocks_split
;
6576 /* Purge dead abnormal call edges from basic block BB. */
6579 tree_purge_dead_abnormal_call_edges (basic_block bb
)
6581 bool changed
= tree_purge_dead_eh_edges (bb
);
6583 if (cfun
->has_nonlocal_label
)
6585 tree stmt
= last_stmt (bb
);
6589 if (!(stmt
&& tree_can_make_abnormal_goto (stmt
)))
6590 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
6592 if (e
->flags
& EDGE_ABNORMAL
)
6601 /* See tree_purge_dead_eh_edges below. */
6603 free_dominance_info (CDI_DOMINATORS
);
6609 /* Stores all basic blocks dominated by BB to DOM_BBS. */
6612 get_all_dominated_blocks (basic_block bb
, VEC (basic_block
, heap
) **dom_bbs
)
6616 VEC_safe_push (basic_block
, heap
, *dom_bbs
, bb
);
6617 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
6619 son
= next_dom_son (CDI_DOMINATORS
, son
))
6620 get_all_dominated_blocks (son
, dom_bbs
);
6623 /* Removes edge E and all the blocks dominated by it, and updates dominance
6624 information. The IL in E->src needs to be updated separately.
6625 If dominance info is not available, only the edge E is removed.*/
6628 remove_edge_and_dominated_blocks (edge e
)
6630 VEC (basic_block
, heap
) *bbs_to_remove
= NULL
;
6631 VEC (basic_block
, heap
) *bbs_to_fix_dom
= NULL
;
6635 bool none_removed
= false;
6637 basic_block bb
, dbb
;
6640 if (!dom_info_available_p (CDI_DOMINATORS
))
6646 /* No updating is needed for edges to exit. */
6647 if (e
->dest
== EXIT_BLOCK_PTR
)
6649 if (cfgcleanup_altered_bbs
)
6650 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
6655 /* First, we find the basic blocks to remove. If E->dest has a predecessor
6656 that is not dominated by E->dest, then this set is empty. Otherwise,
6657 all the basic blocks dominated by E->dest are removed.
6659 Also, to DF_IDOM we store the immediate dominators of the blocks in
6660 the dominance frontier of E (i.e., of the successors of the
6661 removed blocks, if there are any, and of E->dest otherwise). */
6662 FOR_EACH_EDGE (f
, ei
, e
->dest
->preds
)
6667 if (!dominated_by_p (CDI_DOMINATORS
, f
->src
, e
->dest
))
6669 none_removed
= true;
6674 df
= BITMAP_ALLOC (NULL
);
6675 df_idom
= BITMAP_ALLOC (NULL
);
6678 bitmap_set_bit (df_idom
,
6679 get_immediate_dominator (CDI_DOMINATORS
, e
->dest
)->index
);
6682 get_all_dominated_blocks (e
->dest
, &bbs_to_remove
);
6683 for (i
= 0; VEC_iterate (basic_block
, bbs_to_remove
, i
, bb
); i
++)
6685 FOR_EACH_EDGE (f
, ei
, bb
->succs
)
6687 if (f
->dest
!= EXIT_BLOCK_PTR
)
6688 bitmap_set_bit (df
, f
->dest
->index
);
6691 for (i
= 0; VEC_iterate (basic_block
, bbs_to_remove
, i
, bb
); i
++)
6692 bitmap_clear_bit (df
, bb
->index
);
6694 EXECUTE_IF_SET_IN_BITMAP (df
, 0, i
, bi
)
6696 bb
= BASIC_BLOCK (i
);
6697 bitmap_set_bit (df_idom
,
6698 get_immediate_dominator (CDI_DOMINATORS
, bb
)->index
);
6702 if (cfgcleanup_altered_bbs
)
6704 /* Record the set of the altered basic blocks. */
6705 bitmap_set_bit (cfgcleanup_altered_bbs
, e
->src
->index
);
6706 bitmap_ior_into (cfgcleanup_altered_bbs
, df
);
6709 /* Remove E and the cancelled blocks. */
6714 for (i
= 0; VEC_iterate (basic_block
, bbs_to_remove
, i
, bb
); i
++)
6715 delete_basic_block (bb
);
6718 /* Update the dominance information. The immediate dominator may change only
6719 for blocks whose immediate dominator belongs to DF_IDOM:
6721 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6722 removal. Let Z the arbitrary block such that idom(Z) = Y and
6723 Z dominates X after the removal. Before removal, there exists a path P
6724 from Y to X that avoids Z. Let F be the last edge on P that is
6725 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y
6726 dominates W, and because of P, Z does not dominate W), and W belongs to
6727 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */
6728 EXECUTE_IF_SET_IN_BITMAP (df_idom
, 0, i
, bi
)
6730 bb
= BASIC_BLOCK (i
);
6731 for (dbb
= first_dom_son (CDI_DOMINATORS
, bb
);
6733 dbb
= next_dom_son (CDI_DOMINATORS
, dbb
))
6734 VEC_safe_push (basic_block
, heap
, bbs_to_fix_dom
, dbb
);
6737 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
6740 BITMAP_FREE (df_idom
);
6741 VEC_free (basic_block
, heap
, bbs_to_remove
);
6742 VEC_free (basic_block
, heap
, bbs_to_fix_dom
);
6745 /* Purge dead EH edges from basic block BB. */
6748 tree_purge_dead_eh_edges (basic_block bb
)
6750 bool changed
= false;
6753 tree stmt
= last_stmt (bb
);
6755 if (stmt
&& tree_can_throw_internal (stmt
))
6758 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
)); )
6760 if (e
->flags
& EDGE_EH
)
6762 remove_edge_and_dominated_blocks (e
);
6773 tree_purge_all_dead_eh_edges (const_bitmap blocks
)
6775 bool changed
= false;
6779 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
, bi
)
6781 changed
|= tree_purge_dead_eh_edges (BASIC_BLOCK (i
));
6787 /* This function is called whenever a new edge is created or
6791 tree_execute_on_growing_pred (edge e
)
6793 basic_block bb
= e
->dest
;
6796 reserve_phi_args_for_new_edge (bb
);
6799 /* This function is called immediately before edge E is removed from
6800 the edge vector E->dest->preds. */
6803 tree_execute_on_shrinking_pred (edge e
)
6805 if (phi_nodes (e
->dest
))
6806 remove_phi_args (e
);
6809 /*---------------------------------------------------------------------------
6810 Helper functions for Loop versioning
6811 ---------------------------------------------------------------------------*/
6813 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy
6814 of 'first'. Both of them are dominated by 'new_head' basic block. When
6815 'new_head' was created by 'second's incoming edge it received phi arguments
6816 on the edge by split_edge(). Later, additional edge 'e' was created to
6817 connect 'new_head' and 'first'. Now this routine adds phi args on this
6818 additional edge 'e' that new_head to second edge received as part of edge
6823 tree_lv_adjust_loop_header_phi (basic_block first
, basic_block second
,
6824 basic_block new_head
, edge e
)
6827 edge e2
= find_edge (new_head
, second
);
6829 /* Because NEW_HEAD has been created by splitting SECOND's incoming
6830 edge, we should always have an edge from NEW_HEAD to SECOND. */
6831 gcc_assert (e2
!= NULL
);
6833 /* Browse all 'second' basic block phi nodes and add phi args to
6834 edge 'e' for 'first' head. PHI args are always in correct order. */
6836 for (phi2
= phi_nodes (second
), phi1
= phi_nodes (first
);
6838 phi2
= PHI_CHAIN (phi2
), phi1
= PHI_CHAIN (phi1
))
6840 tree def
= PHI_ARG_DEF (phi2
, e2
->dest_idx
);
6841 add_phi_arg (phi1
, def
, e
);
6845 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6846 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6847 the destination of the ELSE part. */
6849 tree_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED
,
6850 basic_block second_head ATTRIBUTE_UNUSED
,
6851 basic_block cond_bb
, void *cond_e
)
6853 block_stmt_iterator bsi
;
6854 tree new_cond_expr
= NULL_TREE
;
6855 tree cond_expr
= (tree
) cond_e
;
6858 /* Build new conditional expr */
6859 new_cond_expr
= build3 (COND_EXPR
, void_type_node
, cond_expr
,
6860 NULL_TREE
, NULL_TREE
);
6862 /* Add new cond in cond_bb. */
6863 bsi
= bsi_start (cond_bb
);
6864 bsi_insert_after (&bsi
, new_cond_expr
, BSI_NEW_STMT
);
6865 /* Adjust edges appropriately to connect new head with first head
6866 as well as second head. */
6867 e0
= single_succ_edge (cond_bb
);
6868 e0
->flags
&= ~EDGE_FALLTHRU
;
6869 e0
->flags
|= EDGE_FALSE_VALUE
;
6872 struct cfg_hooks tree_cfg_hooks
= {
6874 tree_verify_flow_info
,
6875 tree_dump_bb
, /* dump_bb */
6876 create_bb
, /* create_basic_block */
6877 tree_redirect_edge_and_branch
,/* redirect_edge_and_branch */
6878 tree_redirect_edge_and_branch_force
,/* redirect_edge_and_branch_force */
6879 tree_can_remove_branch_p
, /* can_remove_branch_p */
6880 remove_bb
, /* delete_basic_block */
6881 tree_split_block
, /* split_block */
6882 tree_move_block_after
, /* move_block_after */
6883 tree_can_merge_blocks_p
, /* can_merge_blocks_p */
6884 tree_merge_blocks
, /* merge_blocks */
6885 tree_predict_edge
, /* predict_edge */
6886 tree_predicted_by_p
, /* predicted_by_p */
6887 tree_can_duplicate_bb_p
, /* can_duplicate_block_p */
6888 tree_duplicate_bb
, /* duplicate_block */
6889 tree_split_edge
, /* split_edge */
6890 tree_make_forwarder_block
, /* make_forward_block */
6891 NULL
, /* tidy_fallthru_edge */
6892 tree_block_ends_with_call_p
, /* block_ends_with_call_p */
6893 tree_block_ends_with_condjump_p
, /* block_ends_with_condjump_p */
6894 tree_flow_call_edges_add
, /* flow_call_edges_add */
6895 tree_execute_on_growing_pred
, /* execute_on_growing_pred */
6896 tree_execute_on_shrinking_pred
, /* execute_on_shrinking_pred */
6897 tree_duplicate_loop_to_header_edge
, /* duplicate loop for trees */
6898 tree_lv_add_condition_to_bb
, /* lv_add_condition_to_bb */
6899 tree_lv_adjust_loop_header_phi
, /* lv_adjust_loop_header_phi*/
6900 extract_true_false_edges_from_block
, /* extract_cond_bb_edges */
6901 flush_pending_stmts
/* flush_pending_stmts */
6905 /* Split all critical edges. */
6908 split_critical_edges (void)
6914 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6915 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR
6916 mappings around the calls to split_edge. */
6917 start_recording_case_labels ();
6920 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
6921 if (EDGE_CRITICAL_P (e
) && !(e
->flags
& EDGE_ABNORMAL
))
6926 end_recording_case_labels ();
6930 struct gimple_opt_pass pass_split_crit_edges
=
6934 "crited", /* name */
6936 split_critical_edges
, /* execute */
6939 0, /* static_pass_number */
6940 TV_TREE_SPLIT_EDGES
, /* tv_id */
6941 PROP_cfg
, /* properties required */
6942 PROP_no_crit_edges
, /* properties_provided */
6943 0, /* properties_destroyed */
6944 0, /* todo_flags_start */
6945 TODO_dump_func
/* todo_flags_finish */
6950 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
6951 a temporary, make sure and register it to be renamed if necessary,
6952 and finally return the temporary. Put the statements to compute
6953 EXP before the current statement in BSI. */
6956 gimplify_val (block_stmt_iterator
*bsi
, tree type
, tree exp
)
6958 tree t
, new_stmt
, orig_stmt
;
6960 if (is_gimple_val (exp
))
6963 t
= make_rename_temp (type
, NULL
);
6964 new_stmt
= build_gimple_modify_stmt (t
, exp
);
6966 orig_stmt
= bsi_stmt (*bsi
);
6967 SET_EXPR_LOCUS (new_stmt
, EXPR_LOCUS (orig_stmt
));
6968 TREE_BLOCK (new_stmt
) = TREE_BLOCK (orig_stmt
);
6970 bsi_insert_before (bsi
, new_stmt
, BSI_SAME_STMT
);
6971 if (gimple_in_ssa_p (cfun
))
6972 mark_symbols_for_renaming (new_stmt
);
6977 /* Build a ternary operation and gimplify it. Emit code before BSI.
6978 Return the gimple_val holding the result. */
6981 gimplify_build3 (block_stmt_iterator
*bsi
, enum tree_code code
,
6982 tree type
, tree a
, tree b
, tree c
)
6986 ret
= fold_build3 (code
, type
, a
, b
, c
);
6989 return gimplify_val (bsi
, type
, ret
);
6992 /* Build a binary operation and gimplify it. Emit code before BSI.
6993 Return the gimple_val holding the result. */
6996 gimplify_build2 (block_stmt_iterator
*bsi
, enum tree_code code
,
6997 tree type
, tree a
, tree b
)
7001 ret
= fold_build2 (code
, type
, a
, b
);
7004 return gimplify_val (bsi
, type
, ret
);
7007 /* Build a unary operation and gimplify it. Emit code before BSI.
7008 Return the gimple_val holding the result. */
7011 gimplify_build1 (block_stmt_iterator
*bsi
, enum tree_code code
, tree type
,
7016 ret
= fold_build1 (code
, type
, a
);
7019 return gimplify_val (bsi
, type
, ret
);
7024 /* Emit return warnings. */
7027 execute_warn_function_return (void)
7029 source_location location
;
7034 /* If we have a path to EXIT, then we do return. */
7035 if (TREE_THIS_VOLATILE (cfun
->decl
)
7036 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) > 0)
7038 location
= UNKNOWN_LOCATION
;
7039 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
7041 last
= last_stmt (e
->src
);
7042 if (TREE_CODE (last
) == RETURN_EXPR
7043 && (location
= EXPR_LOCATION (last
)) != UNKNOWN_LOCATION
)
7046 if (location
== UNKNOWN_LOCATION
)
7047 location
= cfun
->function_end_locus
;
7048 warning (0, "%H%<noreturn%> function does return", &location
);
7051 /* If we see "return;" in some basic block, then we do reach the end
7052 without returning a value. */
7053 else if (warn_return_type
7054 && !TREE_NO_WARNING (cfun
->decl
)
7055 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) > 0
7056 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun
->decl
))))
7058 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
7060 tree last
= last_stmt (e
->src
);
7061 if (TREE_CODE (last
) == RETURN_EXPR
7062 && TREE_OPERAND (last
, 0) == NULL
7063 && !TREE_NO_WARNING (last
))
7065 location
= EXPR_LOCATION (last
);
7066 if (location
== UNKNOWN_LOCATION
)
7067 location
= cfun
->function_end_locus
;
7068 warning (OPT_Wreturn_type
, "%Hcontrol reaches end of non-void function", &location
);
7069 TREE_NO_WARNING (cfun
->decl
) = 1;
7078 /* Given a basic block B which ends with a conditional and has
7079 precisely two successors, determine which of the edges is taken if
7080 the conditional is true and which is taken if the conditional is
7081 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
7084 extract_true_false_edges_from_block (basic_block b
,
7088 edge e
= EDGE_SUCC (b
, 0);
7090 if (e
->flags
& EDGE_TRUE_VALUE
)
7093 *false_edge
= EDGE_SUCC (b
, 1);
7098 *true_edge
= EDGE_SUCC (b
, 1);
7102 struct gimple_opt_pass pass_warn_function_return
=
7108 execute_warn_function_return
, /* execute */
7111 0, /* static_pass_number */
7113 PROP_cfg
, /* properties_required */
7114 0, /* properties_provided */
7115 0, /* properties_destroyed */
7116 0, /* todo_flags_start */
7117 0 /* todo_flags_finish */
7121 /* Emit noreturn warnings. */
7124 execute_warn_function_noreturn (void)
7126 if (warn_missing_noreturn
7127 && !TREE_THIS_VOLATILE (cfun
->decl
)
7128 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 0
7129 && !lang_hooks
.missing_noreturn_ok_p (cfun
->decl
))
7130 warning (OPT_Wmissing_noreturn
, "%Jfunction might be possible candidate "
7131 "for attribute %<noreturn%>",
7136 struct gimple_opt_pass pass_warn_function_noreturn
=
7142 execute_warn_function_noreturn
, /* execute */
7145 0, /* static_pass_number */
7147 PROP_cfg
, /* properties_required */
7148 0, /* properties_provided */
7149 0, /* properties_destroyed */
7150 0, /* todo_flags_start */
7151 0 /* todo_flags_finish */