1 /* Control flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
37 #include "langhooks.h"
38 #include "diagnostic.h"
39 #include "tree-flow.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
47 /* This file contains functions for building the Control Flow Graph (CFG)
48 for a function tree. */
50 /* Local declarations. */
52 /* Initial capacity for the basic block array. */
53 static const int initial_cfg_capacity
= 20;
55 /* Mapping of labels to their associated blocks. This can greatly speed up
56 building of the CFG in code with lots of gotos. */
57 static GTY(()) varray_type label_to_block_map
;
62 long num_merged_labels
;
65 static struct cfg_stats_d cfg_stats
;
67 /* Nonzero if we found a computed goto while building basic blocks. */
68 static bool found_computed_goto
;
70 /* Basic blocks and flowgraphs. */
71 static basic_block
create_bb (void *, void *, basic_block
);
72 static void create_block_annotation (basic_block
);
73 static void free_blocks_annotations (void);
74 static void clear_blocks_annotations (void);
75 static void make_blocks (tree
);
76 static void factor_computed_gotos (void);
79 static void make_edges (void);
80 static void make_ctrl_stmt_edges (basic_block
);
81 static void make_exit_edges (basic_block
);
82 static void make_cond_expr_edges (basic_block
);
83 static void make_switch_expr_edges (basic_block
);
84 static void make_goto_expr_edges (basic_block
);
85 static edge
tree_redirect_edge_and_branch (edge
, basic_block
);
86 static edge
tree_try_redirect_by_replacing_jump (edge
, basic_block
);
87 static void split_critical_edges (void);
89 /* Various helpers. */
90 static inline bool stmt_starts_bb_p (tree
, tree
);
91 static int tree_verify_flow_info (void);
92 static void tree_make_forwarder_block (edge
);
93 static bool thread_jumps (void);
94 static bool tree_forwarder_block_p (basic_block
);
95 static void bsi_commit_edge_inserts_1 (edge e
);
96 static void tree_cfg2vcg (FILE *);
98 /* Flowgraph optimization and cleanup. */
99 static void tree_merge_blocks (basic_block
, basic_block
);
100 static bool tree_can_merge_blocks_p (basic_block
, basic_block
);
101 static void remove_bb (basic_block
);
102 static void group_case_labels (void);
103 static void cleanup_dead_labels (void);
104 static bool cleanup_control_flow (void);
105 static bool cleanup_control_expr_graph (basic_block
, block_stmt_iterator
);
106 static edge
find_taken_edge_cond_expr (basic_block
, tree
);
107 static edge
find_taken_edge_switch_expr (basic_block
, tree
);
108 static tree
find_case_label_for_value (tree
, tree
);
109 static bool phi_alternatives_equal (basic_block
, edge
, edge
);
112 /*---------------------------------------------------------------------------
114 ---------------------------------------------------------------------------*/
116 /* Entry point to the CFG builder for trees. TP points to the list of
117 statements to be added to the flowgraph. */
120 build_tree_cfg (tree
*tp
)
122 /* Register specific tree functions. */
123 tree_register_cfg_hooks ();
125 /* Initialize rbi_pool. */
128 /* Initialize the basic block array. */
131 last_basic_block
= 0;
132 VARRAY_BB_INIT (basic_block_info
, initial_cfg_capacity
, "basic_block_info");
133 memset ((void *) &cfg_stats
, 0, sizeof (cfg_stats
));
135 /* Build a mapping of labels to their associated blocks. */
136 VARRAY_BB_INIT (label_to_block_map
, initial_cfg_capacity
,
137 "label to block map");
139 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
140 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
142 found_computed_goto
= 0;
145 /* Computed gotos are hell to deal with, especially if there are
146 lots of them with a large number of destinations. So we factor
147 them to a common computed goto location before we build the
148 edge list. After we convert back to normal form, we will un-factor
149 the computed gotos since factoring introduces an unwanted jump. */
150 if (found_computed_goto
)
151 factor_computed_gotos ();
153 /* Make sure there is always at least one block, even if its empty. */
154 if (n_basic_blocks
== 0)
155 create_empty_bb (ENTRY_BLOCK_PTR
);
157 create_block_annotation (ENTRY_BLOCK_PTR
);
158 create_block_annotation (EXIT_BLOCK_PTR
);
160 /* Adjust the size of the array. */
161 VARRAY_GROW (basic_block_info
, n_basic_blocks
);
163 /* To speed up statement iterator walks, we first purge dead labels. */
164 cleanup_dead_labels ();
166 /* Group case nodes to reduce the number of edges.
167 We do this after cleaning up dead labels because otherwise we miss
168 a lot of obvious case merging opportunities. */
169 group_case_labels ();
171 /* Create the edges of the flowgraph. */
174 /* Debugging dumps. */
176 /* Write the flowgraph to a VCG file. */
178 int local_dump_flags
;
179 FILE *dump_file
= dump_begin (TDI_vcg
, &local_dump_flags
);
182 tree_cfg2vcg (dump_file
);
183 dump_end (TDI_vcg
, dump_file
);
187 /* Dump a textual representation of the flowgraph. */
189 dump_tree_cfg (dump_file
, dump_flags
);
193 execute_build_cfg (void)
195 build_tree_cfg (&DECL_SAVED_TREE (current_function_decl
));
198 struct tree_opt_pass pass_build_cfg
=
202 execute_build_cfg
, /* execute */
205 0, /* static_pass_number */
206 TV_TREE_CFG
, /* tv_id */
207 PROP_gimple_leh
, /* properties_required */
208 PROP_cfg
, /* properties_provided */
209 0, /* properties_destroyed */
210 0, /* todo_flags_start */
211 TODO_verify_stmts
/* todo_flags_finish */
214 /* Search the CFG for any computed gotos. If found, factor them to a
215 common computed goto site. Also record the location of that site so
216 that we can un-factor the gotos after we have converted back to
220 factor_computed_gotos (void)
223 tree factored_label_decl
= NULL
;
225 tree factored_computed_goto_label
= NULL
;
226 tree factored_computed_goto
= NULL
;
228 /* We know there are one or more computed gotos in this function.
229 Examine the last statement in each basic block to see if the block
230 ends with a computed goto. */
234 block_stmt_iterator bsi
= bsi_last (bb
);
239 last
= bsi_stmt (bsi
);
241 /* Ignore the computed goto we create when we factor the original
243 if (last
== factored_computed_goto
)
246 /* If the last statement is a computed goto, factor it. */
247 if (computed_goto_p (last
))
251 /* The first time we find a computed goto we need to create
252 the factored goto block and the variable each original
253 computed goto will use for their goto destination. */
254 if (! factored_computed_goto
)
256 basic_block new_bb
= create_empty_bb (bb
);
257 block_stmt_iterator new_bsi
= bsi_start (new_bb
);
259 /* Create the destination of the factored goto. Each original
260 computed goto will put its desired destination into this
261 variable and jump to the label we create immediately
263 var
= create_tmp_var (ptr_type_node
, "gotovar");
265 /* Build a label for the new block which will contain the
266 factored computed goto. */
267 factored_label_decl
= create_artificial_label ();
268 factored_computed_goto_label
269 = build1 (LABEL_EXPR
, void_type_node
, factored_label_decl
);
270 bsi_insert_after (&new_bsi
, factored_computed_goto_label
,
273 /* Build our new computed goto. */
274 factored_computed_goto
= build1 (GOTO_EXPR
, void_type_node
, var
);
275 bsi_insert_after (&new_bsi
, factored_computed_goto
,
279 /* Copy the original computed goto's destination into VAR. */
280 assignment
= build (MODIFY_EXPR
, ptr_type_node
,
281 var
, GOTO_DESTINATION (last
));
282 bsi_insert_before (&bsi
, assignment
, BSI_SAME_STMT
);
284 /* And re-vector the computed goto to the new destination. */
285 GOTO_DESTINATION (last
) = factored_label_decl
;
291 /* Create annotations for a single basic block. */
294 create_block_annotation (basic_block bb
)
296 /* Verify that the tree_annotations field is clear. */
297 if (bb
->tree_annotations
)
299 bb
->tree_annotations
= ggc_alloc_cleared (sizeof (struct bb_ann_d
));
303 /* Free the annotations for all the basic blocks. */
305 static void free_blocks_annotations (void)
307 clear_blocks_annotations ();
311 /* Clear the annotations for all the basic blocks. */
314 clear_blocks_annotations (void)
318 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, NULL
, next_bb
)
319 bb
->tree_annotations
= NULL
;
323 /* Build a flowgraph for the statement_list STMT_LIST. */
326 make_blocks (tree stmt_list
)
328 tree_stmt_iterator i
= tsi_start (stmt_list
);
330 bool start_new_block
= true;
331 bool first_stmt_of_list
= true;
332 basic_block bb
= ENTRY_BLOCK_PTR
;
334 while (!tsi_end_p (i
))
341 /* If the statement starts a new basic block or if we have determined
342 in a previous pass that we need to create a new block for STMT, do
344 if (start_new_block
|| stmt_starts_bb_p (stmt
, prev_stmt
))
346 if (!first_stmt_of_list
)
347 stmt_list
= tsi_split_statement_list_before (&i
);
348 bb
= create_basic_block (stmt_list
, NULL
, bb
);
349 start_new_block
= false;
352 /* Now add STMT to BB and create the subgraphs for special statement
354 set_bb_for_stmt (stmt
, bb
);
356 if (computed_goto_p (stmt
))
357 found_computed_goto
= true;
359 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
361 if (stmt_ends_bb_p (stmt
))
362 start_new_block
= true;
365 first_stmt_of_list
= false;
370 /* Create and return a new empty basic block after bb AFTER. */
373 create_bb (void *h
, void *e
, basic_block after
)
380 /* Create and initialize a new basic block. */
382 memset (bb
, 0, sizeof (*bb
));
384 bb
->index
= last_basic_block
;
386 bb
->stmt_list
= h
? h
: alloc_stmt_list ();
388 /* Add the new block to the linked list of blocks. */
389 link_block (bb
, after
);
391 /* Grow the basic block array if needed. */
392 if ((size_t) last_basic_block
== VARRAY_SIZE (basic_block_info
))
394 size_t new_size
= last_basic_block
+ (last_basic_block
+ 3) / 4;
395 VARRAY_GROW (basic_block_info
, new_size
);
398 /* Add the newly created block to the array. */
399 BASIC_BLOCK (last_basic_block
) = bb
;
401 create_block_annotation (bb
);
406 initialize_bb_rbi (bb
);
411 /*---------------------------------------------------------------------------
413 ---------------------------------------------------------------------------*/
415 /* Join all the blocks in the flowgraph. */
422 /* Create an edge from entry to the first block with executable
424 make_edge (ENTRY_BLOCK_PTR
, BASIC_BLOCK (0), EDGE_FALLTHRU
);
426 /* Traverse basic block array placing edges. */
429 tree first
= first_stmt (bb
);
430 tree last
= last_stmt (bb
);
434 /* Edges for statements that always alter flow control. */
435 if (is_ctrl_stmt (last
))
436 make_ctrl_stmt_edges (bb
);
438 /* Edges for statements that sometimes alter flow control. */
439 if (is_ctrl_altering_stmt (last
))
440 make_exit_edges (bb
);
443 /* Finally, if no edges were created above, this is a regular
444 basic block that only needs a fallthru edge. */
445 if (bb
->succ
== NULL
)
446 make_edge (bb
, bb
->next_bb
, EDGE_FALLTHRU
);
449 /* We do not care about fake edges, so remove any that the CFG
450 builder inserted for completeness. */
451 remove_fake_edges ();
453 /* Clean up the graph and warn for unreachable code. */
458 /* Create edges for control statement at basic block BB. */
461 make_ctrl_stmt_edges (basic_block bb
)
463 tree last
= last_stmt (bb
);
464 tree first
= first_stmt (bb
);
466 #if defined ENABLE_CHECKING
467 if (last
== NULL_TREE
)
471 if (TREE_CODE (first
) == LABEL_EXPR
472 && DECL_NONLOCAL (LABEL_EXPR_LABEL (first
)))
473 make_edge (ENTRY_BLOCK_PTR
, bb
, EDGE_ABNORMAL
);
475 switch (TREE_CODE (last
))
478 make_goto_expr_edges (bb
);
482 make_edge (bb
, EXIT_BLOCK_PTR
, 0);
486 make_cond_expr_edges (bb
);
490 make_switch_expr_edges (bb
);
494 make_eh_edges (last
);
495 /* Yet another NORETURN hack. */
496 if (bb
->succ
== NULL
)
497 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
506 /* Create exit edges for statements in block BB that alter the flow of
507 control. Statements that alter the control flow are 'goto', 'return'
508 and calls to non-returning functions. */
511 make_exit_edges (basic_block bb
)
513 tree last
= last_stmt (bb
);
515 if (last
== NULL_TREE
)
518 switch (TREE_CODE (last
))
521 /* If this function receives a nonlocal goto, then we need to
522 make edges from this call site to all the nonlocal goto
524 if (TREE_SIDE_EFFECTS (last
)
525 && current_function_has_nonlocal_label
)
526 make_goto_expr_edges (bb
);
528 /* If this statement has reachable exception handlers, then
529 create abnormal edges to them. */
530 make_eh_edges (last
);
532 /* Some calls are known not to return. For such calls we create
535 We really need to revamp how we build edges so that it's not
536 such a bloody pain to avoid creating edges for this case since
537 all we do is remove these edges when we're done building the
539 if (call_expr_flags (last
) & (ECF_NORETURN
| ECF_LONGJMP
))
541 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
545 /* Don't forget the fall-thru edge. */
546 make_edge (bb
, bb
->next_bb
, EDGE_FALLTHRU
);
550 /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
551 may have an abnormal edge. Search the RHS for this case and
552 create any required edges. */
553 if (TREE_CODE (TREE_OPERAND (last
, 1)) == CALL_EXPR
554 && TREE_SIDE_EFFECTS (TREE_OPERAND (last
, 1))
555 && current_function_has_nonlocal_label
)
556 make_goto_expr_edges (bb
);
558 make_eh_edges (last
);
559 make_edge (bb
, bb
->next_bb
, EDGE_FALLTHRU
);
568 /* Create the edges for a COND_EXPR starting at block BB.
569 At this point, both clauses must contain only simple gotos. */
572 make_cond_expr_edges (basic_block bb
)
574 tree entry
= last_stmt (bb
);
575 basic_block then_bb
, else_bb
;
576 tree then_label
, else_label
;
578 #if defined ENABLE_CHECKING
579 if (entry
== NULL_TREE
|| TREE_CODE (entry
) != COND_EXPR
)
583 /* Entry basic blocks for each component. */
584 then_label
= GOTO_DESTINATION (COND_EXPR_THEN (entry
));
585 else_label
= GOTO_DESTINATION (COND_EXPR_ELSE (entry
));
586 then_bb
= label_to_block (then_label
);
587 else_bb
= label_to_block (else_label
);
589 make_edge (bb
, then_bb
, EDGE_TRUE_VALUE
);
590 make_edge (bb
, else_bb
, EDGE_FALSE_VALUE
);
594 /* Create the edges for a SWITCH_EXPR starting at block BB.
595 At this point, the switch body has been lowered and the
596 SWITCH_LABELS filled in, so this is in effect a multi-way branch. */
599 make_switch_expr_edges (basic_block bb
)
601 tree entry
= last_stmt (bb
);
605 vec
= SWITCH_LABELS (entry
);
606 n
= TREE_VEC_LENGTH (vec
);
608 for (i
= 0; i
< n
; ++i
)
610 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
611 basic_block label_bb
= label_to_block (lab
);
612 make_edge (bb
, label_bb
, 0);
617 /* Return the basic block holding label DEST. */
620 label_to_block (tree dest
)
622 int uid
= LABEL_DECL_UID (dest
);
624 /* We would die hard when faced by undefined label. Emit label to
625 very first basic block. This will hopefully make even the dataflow
626 and undefined variable warnings quite right. */
627 if ((errorcount
|| sorrycount
) && uid
< 0)
629 block_stmt_iterator bsi
= bsi_start (BASIC_BLOCK (0));
632 stmt
= build1 (LABEL_EXPR
, void_type_node
, dest
);
633 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
634 uid
= LABEL_DECL_UID (dest
);
636 return VARRAY_BB (label_to_block_map
, uid
);
640 /* Create edges for a goto statement at block BB. */
643 make_goto_expr_edges (basic_block bb
)
646 basic_block target_bb
;
648 block_stmt_iterator last
= bsi_last (bb
);
650 goto_t
= bsi_stmt (last
);
652 /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
653 CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
654 from a nonlocal goto. */
655 if (TREE_CODE (goto_t
) != GOTO_EXPR
)
657 dest
= error_mark_node
;
662 dest
= GOTO_DESTINATION (goto_t
);
665 /* A GOTO to a local label creates normal edges. */
666 if (simple_goto_p (goto_t
))
668 edge e
= make_edge (bb
, label_to_block (dest
), EDGE_FALLTHRU
);
669 e
->goto_locus
= EXPR_LOCUS (goto_t
);
674 /* Nothing more to do for nonlocal gotos. */
675 if (TREE_CODE (dest
) == LABEL_DECL
)
678 /* Computed gotos remain. */
681 /* Look for the block starting with the destination label. In the
682 case of a computed goto, make an edge to any label block we find
684 FOR_EACH_BB (target_bb
)
686 block_stmt_iterator bsi
;
688 for (bsi
= bsi_start (target_bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
690 tree target
= bsi_stmt (bsi
);
692 if (TREE_CODE (target
) != LABEL_EXPR
)
696 /* Computed GOTOs. Make an edge to every label block that has
697 been marked as a potential target for a computed goto. */
698 (FORCED_LABEL (LABEL_EXPR_LABEL (target
)) && for_call
== 0)
699 /* Nonlocal GOTO target. Make an edge to every label block
700 that has been marked as a potential target for a nonlocal
702 || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target
)) && for_call
== 1))
704 make_edge (bb
, target_bb
, EDGE_ABNORMAL
);
710 /* Degenerate case of computed goto with no labels. */
711 if (!for_call
&& !bb
->succ
)
712 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
716 /*---------------------------------------------------------------------------
718 ---------------------------------------------------------------------------*/
720 /* Remove unreachable blocks and other miscellaneous clean up work. */
723 cleanup_tree_cfg (void)
725 bool something_changed
= true;
727 timevar_push (TV_TREE_CLEANUP_CFG
);
729 /* These three transformations can cascade, so we iterate on them until
731 while (something_changed
)
733 something_changed
= cleanup_control_flow ();
734 something_changed
|= thread_jumps ();
735 something_changed
|= delete_unreachable_blocks ();
738 /* Merging the blocks creates no new opportunities for the other
739 optimizations, so do it here. */
744 #ifdef ENABLE_CHECKING
747 timevar_pop (TV_TREE_CLEANUP_CFG
);
751 /* Cleanup useless labels in basic blocks. This is something we wish
752 to do early because it allows us to group case labels before creating
753 the edges for the CFG, and it speeds up block statement iterators in
755 We only run this pass once, running it more than once is probably not
758 /* A map from basic block index to the leading label of that block. */
759 static tree
*label_for_bb
;
761 /* Callback for for_each_eh_region. Helper for cleanup_dead_labels. */
763 update_eh_label (struct eh_region
*region
)
765 tree old_label
= get_eh_region_tree_label (region
);
768 tree new_label
= label_for_bb
[label_to_block (old_label
)->index
];
769 set_eh_region_tree_label (region
, new_label
);
773 /* Given LABEL return the first label in the same basic block. */
775 main_block_label (tree label
)
777 basic_block bb
= label_to_block (label
);
779 /* label_to_block possibly inserted undefined label into the chain. */
780 if (!label_for_bb
[bb
->index
])
781 label_for_bb
[bb
->index
] = label
;
782 return label_for_bb
[bb
->index
];
785 /* Cleanup redundant labels. This is a three-steo process:
786 1) Find the leading label for each block.
787 2) Redirect all references to labels to the leading labels.
788 3) Cleanup all useless labels. */
791 cleanup_dead_labels (void)
794 label_for_bb
= xcalloc (last_basic_block
, sizeof (tree
));
796 /* Find a suitable label for each block. We use the first user-defined
797 label is there is one, or otherwise just the first label we see. */
800 block_stmt_iterator i
;
802 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
804 tree label
, stmt
= bsi_stmt (i
);
806 if (TREE_CODE (stmt
) != LABEL_EXPR
)
809 label
= LABEL_EXPR_LABEL (stmt
);
811 /* If we have not yet seen a label for the current block,
812 remember this one and see if there are more labels. */
813 if (! label_for_bb
[bb
->index
])
815 label_for_bb
[bb
->index
] = label
;
819 /* If we did see a label for the current block already, but it
820 is an artificially created label, replace it if the current
821 label is a user defined label. */
822 if (! DECL_ARTIFICIAL (label
)
823 && DECL_ARTIFICIAL (label_for_bb
[bb
->index
]))
825 label_for_bb
[bb
->index
] = label
;
831 /* Now redirect all jumps/branches to the selected label.
832 First do so for each block ending in a control statement. */
835 tree stmt
= last_stmt (bb
);
839 switch (TREE_CODE (stmt
))
843 tree true_branch
, false_branch
;
845 true_branch
= COND_EXPR_THEN (stmt
);
846 false_branch
= COND_EXPR_ELSE (stmt
);
848 GOTO_DESTINATION (true_branch
)
849 = main_block_label (GOTO_DESTINATION (true_branch
));
850 GOTO_DESTINATION (false_branch
)
851 = main_block_label (GOTO_DESTINATION (false_branch
));
859 tree vec
= SWITCH_LABELS (stmt
);
860 size_t n
= TREE_VEC_LENGTH (vec
);
862 /* Replace all destination labels. */
863 for (i
= 0; i
< n
; ++i
)
864 CASE_LABEL (TREE_VEC_ELT (vec
, i
))
865 = main_block_label (CASE_LABEL (TREE_VEC_ELT (vec
, i
)));
870 /* We have to handle GOTO_EXPRs until they're removed, and we don't
871 remove them until after we've created the CFG edges. */
873 if (! computed_goto_p (stmt
))
875 GOTO_DESTINATION (stmt
)
876 = main_block_label (GOTO_DESTINATION (stmt
));
885 for_each_eh_region (update_eh_label
);
887 /* Finally, purge dead labels. All user-defined labels and labels that
888 can be the target of non-local gotos are preserved. */
891 block_stmt_iterator i
;
892 tree label_for_this_bb
= label_for_bb
[bb
->index
];
894 if (! label_for_this_bb
)
897 for (i
= bsi_start (bb
); !bsi_end_p (i
); )
899 tree label
, stmt
= bsi_stmt (i
);
901 if (TREE_CODE (stmt
) != LABEL_EXPR
)
904 label
= LABEL_EXPR_LABEL (stmt
);
906 if (label
== label_for_this_bb
907 || ! DECL_ARTIFICIAL (label
)
908 || DECL_NONLOCAL (label
))
918 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
919 and scan the sorted vector of cases. Combine the ones jumping to the
921 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
924 group_case_labels (void)
930 tree stmt
= last_stmt (bb
);
931 if (stmt
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
933 tree labels
= SWITCH_LABELS (stmt
);
934 int old_size
= TREE_VEC_LENGTH (labels
);
935 int i
, j
, new_size
= old_size
;
937 /* Look for possible opportunities to merge cases.
938 Ignore the last element of the label vector because it
939 must be the default case. */
941 while (i
< old_size
- 2)
943 tree base_case
, base_label
, base_high
, type
;
944 base_case
= TREE_VEC_ELT (labels
, i
);
949 type
= TREE_TYPE (CASE_LOW (base_case
));
950 base_label
= CASE_LABEL (base_case
);
951 base_high
= CASE_HIGH (base_case
) ?
952 CASE_HIGH (base_case
) : CASE_LOW (base_case
);
954 /* Try to merge case labels. Break out when we reach the end
955 of the label vector or when we cannot merge the next case
956 label with the current one. */
957 while (i
< old_size
- 2)
959 tree merge_case
= TREE_VEC_ELT (labels
, ++i
);
960 tree merge_label
= CASE_LABEL (merge_case
);
961 tree t
= int_const_binop (PLUS_EXPR
, base_high
,
962 integer_one_node
, 1);
964 /* Merge the cases if they jump to the same place,
965 and their ranges are consecutive. */
966 if (merge_label
== base_label
967 && tree_int_cst_equal (CASE_LOW (merge_case
), t
))
969 base_high
= CASE_HIGH (merge_case
) ?
970 CASE_HIGH (merge_case
) : CASE_LOW (merge_case
);
971 CASE_HIGH (base_case
) = base_high
;
972 TREE_VEC_ELT (labels
, i
) = NULL_TREE
;
980 /* Compress the case labels in the label vector, and adjust the
981 length of the vector. */
982 for (i
= 0, j
= 0; i
< new_size
; i
++)
984 while (! TREE_VEC_ELT (labels
, j
))
986 TREE_VEC_ELT (labels
, i
) = TREE_VEC_ELT (labels
, j
++);
988 TREE_VEC_LENGTH (labels
) = new_size
;
993 /* Checks whether we can merge block B into block A. */
996 tree_can_merge_blocks_p (basic_block a
, basic_block b
)
999 block_stmt_iterator bsi
;
1002 || a
->succ
->succ_next
)
1005 if (a
->succ
->flags
& EDGE_ABNORMAL
)
1008 if (a
->succ
->dest
!= b
)
1011 if (b
== EXIT_BLOCK_PTR
)
1014 if (b
->pred
->pred_next
)
1017 /* If A ends by a statement causing exceptions or something similar, we
1018 cannot merge the blocks. */
1019 stmt
= last_stmt (a
);
1020 if (stmt
&& stmt_ends_bb_p (stmt
))
1023 /* Do not allow a block with only a non-local label to be merged. */
1024 if (stmt
&& TREE_CODE (stmt
) == LABEL_EXPR
1025 && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt
)))
1028 /* There may be no phi nodes at the start of b. Most of these degenerate
1029 phi nodes should be cleaned up by kill_redundant_phi_nodes. */
1033 /* Do not remove user labels. */
1034 for (bsi
= bsi_start (b
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1036 stmt
= bsi_stmt (bsi
);
1037 if (TREE_CODE (stmt
) != LABEL_EXPR
)
1039 if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt
)))
1047 /* Merge block B into block A. */
1050 tree_merge_blocks (basic_block a
, basic_block b
)
1052 block_stmt_iterator bsi
;
1053 tree_stmt_iterator last
;
1056 fprintf (dump_file
, "Merging blocks %d and %d\n", a
->index
, b
->index
);
1058 /* Ensure that B follows A. */
1059 move_block_after (b
, a
);
1061 if (!(a
->succ
->flags
& EDGE_FALLTHRU
))
1065 && stmt_ends_bb_p (last_stmt (a
)))
1068 /* Remove labels from B and set bb_for_stmt to A for other statements. */
1069 for (bsi
= bsi_start (b
); !bsi_end_p (bsi
);)
1071 if (TREE_CODE (bsi_stmt (bsi
)) == LABEL_EXPR
)
1075 set_bb_for_stmt (bsi_stmt (bsi
), a
);
1080 /* Merge the chains. */
1081 last
= tsi_last (a
->stmt_list
);
1082 tsi_link_after (&last
, b
->stmt_list
, TSI_NEW_STMT
);
1083 b
->stmt_list
= NULL
;
1087 /* Walk the function tree removing unnecessary statements.
1089 * Empty statement nodes are removed
1091 * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1093 * Unnecessary COND_EXPRs are removed
1095 * Some unnecessary BIND_EXPRs are removed
1097 Clearly more work could be done. The trick is doing the analysis
1098 and removal fast enough to be a net improvement in compile times.
1100 Note that when we remove a control structure such as a COND_EXPR
1101 BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1102 to ensure we eliminate all the useless code. */
1113 static void remove_useless_stmts_1 (tree
*, struct rus_data
*);
1116 remove_useless_stmts_warn_notreached (tree stmt
)
1118 if (EXPR_LOCUS (stmt
))
1120 warning ("%Hwill never be executed", EXPR_LOCUS (stmt
));
1124 switch (TREE_CODE (stmt
))
1126 case STATEMENT_LIST
:
1128 tree_stmt_iterator i
;
1129 for (i
= tsi_start (stmt
); !tsi_end_p (i
); tsi_next (&i
))
1130 if (remove_useless_stmts_warn_notreached (tsi_stmt (i
)))
1136 if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt
)))
1138 if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt
)))
1140 if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt
)))
1144 case TRY_FINALLY_EXPR
:
1145 case TRY_CATCH_EXPR
:
1146 if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt
, 0)))
1148 if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt
, 1)))
1153 return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt
));
1154 case EH_FILTER_EXPR
:
1155 return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt
));
1157 return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt
));
1160 /* Not a live container. */
1168 remove_useless_stmts_cond (tree
*stmt_p
, struct rus_data
*data
)
1170 tree then_clause
, else_clause
, cond
;
1171 bool save_has_label
, then_has_label
, else_has_label
;
1173 save_has_label
= data
->has_label
;
1174 data
->has_label
= false;
1175 data
->last_goto
= NULL
;
1177 remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p
), data
);
1179 then_has_label
= data
->has_label
;
1180 data
->has_label
= false;
1181 data
->last_goto
= NULL
;
1183 remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p
), data
);
1185 else_has_label
= data
->has_label
;
1186 data
->has_label
= save_has_label
| then_has_label
| else_has_label
;
1189 then_clause
= COND_EXPR_THEN (*stmt_p
);
1190 else_clause
= COND_EXPR_ELSE (*stmt_p
);
1191 cond
= COND_EXPR_COND (*stmt_p
);
1193 /* If neither arm does anything at all, we can remove the whole IF. */
1194 if (!TREE_SIDE_EFFECTS (then_clause
) && !TREE_SIDE_EFFECTS (else_clause
))
1196 *stmt_p
= build_empty_stmt ();
1197 data
->repeat
= true;
1200 /* If there are no reachable statements in an arm, then we can
1201 zap the entire conditional. */
1202 else if (integer_nonzerop (cond
) && !else_has_label
)
1204 if (warn_notreached
)
1205 remove_useless_stmts_warn_notreached (else_clause
);
1206 *stmt_p
= then_clause
;
1207 data
->repeat
= true;
1209 else if (integer_zerop (cond
) && !then_has_label
)
1211 if (warn_notreached
)
1212 remove_useless_stmts_warn_notreached (then_clause
);
1213 *stmt_p
= else_clause
;
1214 data
->repeat
= true;
1217 /* Check a couple of simple things on then/else with single stmts. */
1220 tree then_stmt
= expr_only (then_clause
);
1221 tree else_stmt
= expr_only (else_clause
);
1223 /* Notice branches to a common destination. */
1224 if (then_stmt
&& else_stmt
1225 && TREE_CODE (then_stmt
) == GOTO_EXPR
1226 && TREE_CODE (else_stmt
) == GOTO_EXPR
1227 && (GOTO_DESTINATION (then_stmt
) == GOTO_DESTINATION (else_stmt
)))
1229 *stmt_p
= then_stmt
;
1230 data
->repeat
= true;
1233 /* If the THEN/ELSE clause merely assigns a value to a variable or
1234 parameter which is already known to contain that value, then
1235 remove the useless THEN/ELSE clause. */
1236 else if (TREE_CODE (cond
) == VAR_DECL
|| TREE_CODE (cond
) == PARM_DECL
)
1239 && TREE_CODE (else_stmt
) == MODIFY_EXPR
1240 && TREE_OPERAND (else_stmt
, 0) == cond
1241 && integer_zerop (TREE_OPERAND (else_stmt
, 1)))
1242 COND_EXPR_ELSE (*stmt_p
) = alloc_stmt_list ();
1244 else if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
1245 && (TREE_CODE (TREE_OPERAND (cond
, 0)) == VAR_DECL
1246 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PARM_DECL
)
1247 && TREE_CONSTANT (TREE_OPERAND (cond
, 1)))
1249 tree stmt
= (TREE_CODE (cond
) == EQ_EXPR
1250 ? then_stmt
: else_stmt
);
1251 tree
*location
= (TREE_CODE (cond
) == EQ_EXPR
1252 ? &COND_EXPR_THEN (*stmt_p
)
1253 : &COND_EXPR_ELSE (*stmt_p
));
1256 && TREE_CODE (stmt
) == MODIFY_EXPR
1257 && TREE_OPERAND (stmt
, 0) == TREE_OPERAND (cond
, 0)
1258 && TREE_OPERAND (stmt
, 1) == TREE_OPERAND (cond
, 1))
1259 *location
= alloc_stmt_list ();
1263 /* Protect GOTOs in the arm of COND_EXPRs from being removed. They
1264 would be re-introduced during lowering. */
1265 data
->last_goto
= NULL
;
1270 remove_useless_stmts_tf (tree
*stmt_p
, struct rus_data
*data
)
1272 bool save_may_branch
, save_may_throw
;
1273 bool this_may_branch
, this_may_throw
;
1275 /* Collect may_branch and may_throw information for the body only. */
1276 save_may_branch
= data
->may_branch
;
1277 save_may_throw
= data
->may_throw
;
1278 data
->may_branch
= false;
1279 data
->may_throw
= false;
1280 data
->last_goto
= NULL
;
1282 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 0), data
);
1284 this_may_branch
= data
->may_branch
;
1285 this_may_throw
= data
->may_throw
;
1286 data
->may_branch
|= save_may_branch
;
1287 data
->may_throw
|= save_may_throw
;
1288 data
->last_goto
= NULL
;
1290 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 1), data
);
1292 /* If the body is empty, then we can emit the FINALLY block without
1293 the enclosing TRY_FINALLY_EXPR. */
1294 if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p
, 0)))
1296 *stmt_p
= TREE_OPERAND (*stmt_p
, 1);
1297 data
->repeat
= true;
1300 /* If the handler is empty, then we can emit the TRY block without
1301 the enclosing TRY_FINALLY_EXPR. */
1302 else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p
, 1)))
1304 *stmt_p
= TREE_OPERAND (*stmt_p
, 0);
1305 data
->repeat
= true;
1308 /* If the body neither throws, nor branches, then we can safely
1309 string the TRY and FINALLY blocks together. */
1310 else if (!this_may_branch
&& !this_may_throw
)
1312 tree stmt
= *stmt_p
;
1313 *stmt_p
= TREE_OPERAND (stmt
, 0);
1314 append_to_statement_list (TREE_OPERAND (stmt
, 1), stmt_p
);
1315 data
->repeat
= true;
1321 remove_useless_stmts_tc (tree
*stmt_p
, struct rus_data
*data
)
1323 bool save_may_throw
, this_may_throw
;
1324 tree_stmt_iterator i
;
1327 /* Collect may_throw information for the body only. */
1328 save_may_throw
= data
->may_throw
;
1329 data
->may_throw
= false;
1330 data
->last_goto
= NULL
;
1332 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 0), data
);
1334 this_may_throw
= data
->may_throw
;
1335 data
->may_throw
= save_may_throw
;
1337 /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR. */
1338 if (!this_may_throw
)
1340 if (warn_notreached
)
1341 remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p
, 1));
1342 *stmt_p
= TREE_OPERAND (*stmt_p
, 0);
1343 data
->repeat
= true;
1347 /* Process the catch clause specially. We may be able to tell that
1348 no exceptions propagate past this point. */
1350 this_may_throw
= true;
1351 i
= tsi_start (TREE_OPERAND (*stmt_p
, 1));
1352 stmt
= tsi_stmt (i
);
1353 data
->last_goto
= NULL
;
1355 switch (TREE_CODE (stmt
))
1358 for (; !tsi_end_p (i
); tsi_next (&i
))
1360 stmt
= tsi_stmt (i
);
1361 /* If we catch all exceptions, then the body does not
1362 propagate exceptions past this point. */
1363 if (CATCH_TYPES (stmt
) == NULL
)
1364 this_may_throw
= false;
1365 data
->last_goto
= NULL
;
1366 remove_useless_stmts_1 (&CATCH_BODY (stmt
), data
);
1370 case EH_FILTER_EXPR
:
1371 if (EH_FILTER_MUST_NOT_THROW (stmt
))
1372 this_may_throw
= false;
1373 else if (EH_FILTER_TYPES (stmt
) == NULL
)
1374 this_may_throw
= false;
1375 remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt
), data
);
1379 /* Otherwise this is a cleanup. */
1380 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 1), data
);
1382 /* If the cleanup is empty, then we can emit the TRY block without
1383 the enclosing TRY_CATCH_EXPR. */
1384 if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p
, 1)))
1386 *stmt_p
= TREE_OPERAND (*stmt_p
, 0);
1387 data
->repeat
= true;
1391 data
->may_throw
|= this_may_throw
;
1396 remove_useless_stmts_bind (tree
*stmt_p
, struct rus_data
*data
)
1400 /* First remove anything underneath the BIND_EXPR. */
1401 remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p
), data
);
1403 /* If the BIND_EXPR has no variables, then we can pull everything
1404 up one level and remove the BIND_EXPR, unless this is the toplevel
1405 BIND_EXPR for the current function or an inlined function.
1407 When this situation occurs we will want to apply this
1408 optimization again. */
1409 block
= BIND_EXPR_BLOCK (*stmt_p
);
1410 if (BIND_EXPR_VARS (*stmt_p
) == NULL_TREE
1411 && *stmt_p
!= DECL_SAVED_TREE (current_function_decl
)
1413 || ! BLOCK_ABSTRACT_ORIGIN (block
)
1414 || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block
))
1417 *stmt_p
= BIND_EXPR_BODY (*stmt_p
);
1418 data
->repeat
= true;
1424 remove_useless_stmts_goto (tree
*stmt_p
, struct rus_data
*data
)
1426 tree dest
= GOTO_DESTINATION (*stmt_p
);
1428 data
->may_branch
= true;
1429 data
->last_goto
= NULL
;
1431 /* Record the last goto expr, so that we can delete it if unnecessary. */
1432 if (TREE_CODE (dest
) == LABEL_DECL
)
1433 data
->last_goto
= stmt_p
;
1438 remove_useless_stmts_label (tree
*stmt_p
, struct rus_data
*data
)
1440 tree label
= LABEL_EXPR_LABEL (*stmt_p
);
1442 data
->has_label
= true;
1444 /* We do want to jump across non-local label receiver code. */
1445 if (DECL_NONLOCAL (label
))
1446 data
->last_goto
= NULL
;
1448 else if (data
->last_goto
&& GOTO_DESTINATION (*data
->last_goto
) == label
)
1450 *data
->last_goto
= build_empty_stmt ();
1451 data
->repeat
= true;
1454 /* ??? Add something here to delete unused labels. */
1458 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1459 decl. This allows us to eliminate redundant or useless
1460 calls to "const" functions.
1462 Gimplifier already does the same operation, but we may notice functions
1463 being const and pure once their calls has been gimplified, so we need
1464 to update the flag. */
1467 update_call_expr_flags (tree call
)
1469 tree decl
= get_callee_fndecl (call
);
1472 if (call_expr_flags (call
) & (ECF_CONST
| ECF_PURE
))
1473 TREE_SIDE_EFFECTS (call
) = 0;
1474 if (TREE_NOTHROW (decl
))
1475 TREE_NOTHROW (call
) = 1;
1479 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1482 notice_special_calls (tree t
)
1484 int flags
= call_expr_flags (t
);
1486 if (flags
& ECF_MAY_BE_ALLOCA
)
1487 current_function_calls_alloca
= true;
1488 if (flags
& ECF_RETURNS_TWICE
)
1489 current_function_calls_setjmp
= true;
1493 /* Clear flags set by notice_special_calls. Used by dead code removal
1494 to update the flags. */
1497 clear_special_calls (void)
1499 current_function_calls_alloca
= false;
1500 current_function_calls_setjmp
= false;
1505 remove_useless_stmts_1 (tree
*tp
, struct rus_data
*data
)
1509 switch (TREE_CODE (t
))
1512 remove_useless_stmts_cond (tp
, data
);
1515 case TRY_FINALLY_EXPR
:
1516 remove_useless_stmts_tf (tp
, data
);
1519 case TRY_CATCH_EXPR
:
1520 remove_useless_stmts_tc (tp
, data
);
1524 remove_useless_stmts_bind (tp
, data
);
1528 remove_useless_stmts_goto (tp
, data
);
1532 remove_useless_stmts_label (tp
, data
);
1537 data
->last_goto
= NULL
;
1538 data
->may_branch
= true;
1543 data
->last_goto
= NULL
;
1544 notice_special_calls (t
);
1545 update_call_expr_flags (t
);
1546 if (tree_could_throw_p (t
))
1547 data
->may_throw
= true;
1551 data
->last_goto
= NULL
;
1553 if (TREE_CODE (TREE_OPERAND (t
, 1)) == CALL_EXPR
)
1555 update_call_expr_flags (TREE_OPERAND (t
, 1));
1556 notice_special_calls (TREE_OPERAND (t
, 1));
1558 if (tree_could_throw_p (t
))
1559 data
->may_throw
= true;
1562 case STATEMENT_LIST
:
1564 tree_stmt_iterator i
= tsi_start (t
);
1565 while (!tsi_end_p (i
))
1568 if (IS_EMPTY_STMT (t
))
1574 remove_useless_stmts_1 (tsi_stmt_ptr (i
), data
);
1577 if (TREE_CODE (t
) == STATEMENT_LIST
)
1579 tsi_link_before (&i
, t
, TSI_SAME_STMT
);
1589 data
->last_goto
= NULL
;
1593 data
->last_goto
= NULL
;
1599 remove_useless_stmts (void)
1601 struct rus_data data
;
1603 clear_special_calls ();
1607 memset (&data
, 0, sizeof (data
));
1608 remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl
), &data
);
1610 while (data
.repeat
);
1614 struct tree_opt_pass pass_remove_useless_stmts
=
1616 "useless", /* name */
1618 remove_useless_stmts
, /* execute */
1621 0, /* static_pass_number */
1623 PROP_gimple_any
, /* properties_required */
1624 0, /* properties_provided */
1625 0, /* properties_destroyed */
1626 0, /* todo_flags_start */
1627 TODO_dump_func
/* todo_flags_finish */
1631 /* Remove obviously useless statements in basic block BB. */
1634 cfg_remove_useless_stmts_bb (basic_block bb
)
1636 block_stmt_iterator bsi
;
1637 tree stmt
= NULL_TREE
;
1638 tree cond
, var
= NULL_TREE
, val
= NULL_TREE
;
1639 struct var_ann_d
*ann
;
1641 /* Check whether we come here from a condition, and if so, get the
1644 || bb
->pred
->pred_next
1645 || !(bb
->pred
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1648 cond
= COND_EXPR_COND (last_stmt (bb
->pred
->src
));
1650 if (TREE_CODE (cond
) == VAR_DECL
|| TREE_CODE (cond
) == PARM_DECL
)
1653 val
= (bb
->pred
->flags
& EDGE_FALSE_VALUE
1654 ? boolean_false_node
: boolean_true_node
);
1656 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
1657 && (TREE_CODE (TREE_OPERAND (cond
, 0)) == VAR_DECL
1658 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PARM_DECL
))
1660 var
= TREE_OPERAND (cond
, 0);
1661 val
= (bb
->pred
->flags
& EDGE_FALSE_VALUE
1662 ? boolean_true_node
: boolean_false_node
);
1666 if (bb
->pred
->flags
& EDGE_FALSE_VALUE
)
1667 cond
= invert_truthvalue (cond
);
1668 if (TREE_CODE (cond
) == EQ_EXPR
1669 && (TREE_CODE (TREE_OPERAND (cond
, 0)) == VAR_DECL
1670 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PARM_DECL
)
1671 && (TREE_CODE (TREE_OPERAND (cond
, 1)) == VAR_DECL
1672 || TREE_CODE (TREE_OPERAND (cond
, 1)) == PARM_DECL
1673 || TREE_CONSTANT (TREE_OPERAND (cond
, 1))))
1675 var
= TREE_OPERAND (cond
, 0);
1676 val
= TREE_OPERAND (cond
, 1);
1682 /* Only work for normal local variables. */
1683 ann
= var_ann (var
);
1686 || TREE_ADDRESSABLE (var
))
1689 if (! TREE_CONSTANT (val
))
1691 ann
= var_ann (val
);
1694 || TREE_ADDRESSABLE (val
))
1698 /* Ignore floating point variables, since comparison behaves weird for
1700 if (FLOAT_TYPE_P (TREE_TYPE (var
)))
1703 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
);)
1705 stmt
= bsi_stmt (bsi
);
1707 /* If the THEN/ELSE clause merely assigns a value to a variable/parameter
1708 which is already known to contain that value, then remove the useless
1709 THEN/ELSE clause. */
1710 if (TREE_CODE (stmt
) == MODIFY_EXPR
1711 && TREE_OPERAND (stmt
, 0) == var
1712 && operand_equal_p (val
, TREE_OPERAND (stmt
, 1), 0))
1718 /* Invalidate the var if we encounter something that could modify it. */
1719 if (TREE_CODE (stmt
) == ASM_EXPR
1720 || TREE_CODE (stmt
) == VA_ARG_EXPR
1721 || (TREE_CODE (stmt
) == MODIFY_EXPR
1722 && (TREE_OPERAND (stmt
, 0) == var
1723 || TREE_OPERAND (stmt
, 0) == val
1724 || TREE_CODE (TREE_OPERAND (stmt
, 1)) == VA_ARG_EXPR
)))
1732 /* A CFG-aware version of remove_useless_stmts. */
1735 cfg_remove_useless_stmts (void)
1739 #ifdef ENABLE_CHECKING
1740 verify_flow_info ();
1745 cfg_remove_useless_stmts_bb (bb
);
1750 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1753 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb
)
1757 /* Since this block is no longer reachable, we can just delete all
1758 of its PHI nodes. */
1759 phi
= phi_nodes (bb
);
1762 tree next
= PHI_CHAIN (phi
);
1763 remove_phi_node (phi
, NULL_TREE
, bb
);
1767 /* Remove edges to BB's successors. */
1768 while (bb
->succ
!= NULL
)
1769 ssa_remove_edge (bb
->succ
);
1773 /* Remove statements of basic block BB. */
1776 remove_bb (basic_block bb
)
1778 block_stmt_iterator i
;
1779 location_t
*loc
= NULL
;
1783 fprintf (dump_file
, "Removing basic block %d\n", bb
->index
);
1784 if (dump_flags
& TDF_DETAILS
)
1786 dump_bb (bb
, dump_file
, 0);
1787 fprintf (dump_file
, "\n");
1791 /* Remove all the instructions in the block. */
1792 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_remove (&i
))
1794 tree stmt
= bsi_stmt (i
);
1796 set_bb_for_stmt (stmt
, NULL
);
1798 /* Don't warn for removed gotos. Gotos are often removed due to
1799 jump threading, thus resulting in bogus warnings. Not great,
1800 since this way we lose warnings for gotos in the original
1801 program that are indeed unreachable. */
1802 if (TREE_CODE (stmt
) != GOTO_EXPR
&& EXPR_LOCUS (stmt
) && !loc
)
1803 loc
= EXPR_LOCUS (stmt
);
1806 /* If requested, give a warning that the first statement in the
1807 block is unreachable. We walk statements backwards in the
1808 loop above, so the last statement we process is the first statement
1810 if (warn_notreached
&& loc
)
1811 warning ("%Hwill never be executed", loc
);
1813 remove_phi_nodes_and_edges_for_unreachable_block (bb
);
1817 /* Examine BB to determine if it is a forwarding block (a block which only
1818 transfers control to a new destination). If BB is a forwarding block,
1819 then return the edge leading to the ultimate destination. */
1822 tree_block_forwards_to (basic_block bb
)
1824 block_stmt_iterator bsi
;
1825 bb_ann_t ann
= bb_ann (bb
);
1828 /* If this block is not forwardable, then avoid useless work. */
1829 if (! ann
->forwardable
)
1832 /* Set this block to not be forwardable. This prevents infinite loops since
1833 any block currently under examination is considered non-forwardable. */
1834 ann
->forwardable
= 0;
1836 /* No forwarding is possible if this block is a special block (ENTRY/EXIT),
1837 this block has more than one successor, this block's single successor is
1838 reached via an abnormal edge, this block has phi nodes, or this block's
1839 single successor has phi nodes. */
1840 if (bb
== EXIT_BLOCK_PTR
1841 || bb
== ENTRY_BLOCK_PTR
1843 || bb
->succ
->succ_next
1844 || bb
->succ
->dest
== EXIT_BLOCK_PTR
1845 || (bb
->succ
->flags
& EDGE_ABNORMAL
) != 0
1847 || phi_nodes (bb
->succ
->dest
))
1850 /* Walk past any labels at the start of this block. */
1851 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1853 stmt
= bsi_stmt (bsi
);
1854 if (TREE_CODE (stmt
) != LABEL_EXPR
)
1858 /* If we reached the end of this block we may be able to optimize this
1860 if (bsi_end_p (bsi
))
1864 /* Recursive call to pick up chains of forwarding blocks. */
1865 dest
= tree_block_forwards_to (bb
->succ
->dest
);
1867 /* If none found, we forward to bb->succ at minimum. */
1871 ann
->forwardable
= 1;
1875 /* No forwarding possible. */
1880 /* Try to remove superfluous control structures. */
1883 cleanup_control_flow (void)
1886 block_stmt_iterator bsi
;
1887 bool retval
= false;
1892 bsi
= bsi_last (bb
);
1894 if (bsi_end_p (bsi
))
1897 stmt
= bsi_stmt (bsi
);
1898 if (TREE_CODE (stmt
) == COND_EXPR
1899 || TREE_CODE (stmt
) == SWITCH_EXPR
)
1900 retval
|= cleanup_control_expr_graph (bb
, bsi
);
1906 /* Disconnect an unreachable block in the control expression starting
1910 cleanup_control_expr_graph (basic_block bb
, block_stmt_iterator bsi
)
1913 bool retval
= false;
1914 tree expr
= bsi_stmt (bsi
), val
;
1916 if (bb
->succ
->succ_next
)
1920 switch (TREE_CODE (expr
))
1923 val
= COND_EXPR_COND (expr
);
1927 val
= SWITCH_COND (expr
);
1928 if (TREE_CODE (val
) != INTEGER_CST
)
1936 taken_edge
= find_taken_edge (bb
, val
);
1940 /* Remove all the edges except the one that is always executed. */
1941 for (e
= bb
->succ
; e
; e
= next
)
1943 next
= e
->succ_next
;
1944 if (e
!= taken_edge
)
1946 taken_edge
->probability
+= e
->probability
;
1947 taken_edge
->count
+= e
->count
;
1948 ssa_remove_edge (e
);
1952 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
1953 taken_edge
->probability
= REG_BR_PROB_BASE
;
1956 taken_edge
= bb
->succ
;
1959 taken_edge
->flags
= EDGE_FALLTHRU
;
1961 /* We removed some paths from the cfg. */
1962 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
1963 dom_computed
[CDI_DOMINATORS
] = DOM_CONS_OK
;
1969 /* Given a control block BB and a constant value VAL, return the edge that
1970 will be taken out of the block. If VAL does not match a unique edge,
1971 NULL is returned. */
1974 find_taken_edge (basic_block bb
, tree val
)
1978 stmt
= last_stmt (bb
);
1980 #if defined ENABLE_CHECKING
1981 if (stmt
== NULL_TREE
|| !is_ctrl_stmt (stmt
))
1985 /* If VAL is not a constant, we can't determine which edge might
1987 if (val
== NULL
|| !really_constant_p (val
))
1990 if (TREE_CODE (stmt
) == COND_EXPR
)
1991 return find_taken_edge_cond_expr (bb
, val
);
1993 if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1994 return find_taken_edge_switch_expr (bb
, val
);
2000 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2001 statement, determine which of the two edges will be taken out of the
2002 block. Return NULL if either edge may be taken. */
2005 find_taken_edge_cond_expr (basic_block bb
, tree val
)
2007 edge true_edge
, false_edge
;
2009 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
2011 /* If both edges of the branch lead to the same basic block, it doesn't
2012 matter which edge is taken. */
2013 if (true_edge
->dest
== false_edge
->dest
)
2016 /* Otherwise, try to determine which branch of the if() will be taken.
2017 If VAL is a constant but it can't be reduced to a 0 or a 1, then
2018 we don't really know which edge will be taken at runtime. This
2019 may happen when comparing addresses (e.g., if (&var1 == 4)). */
2020 if (integer_nonzerop (val
))
2022 else if (integer_zerop (val
))
2029 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
2030 statement, determine which edge will be taken out of the block. Return
2031 NULL if any edge may be taken. */
2034 find_taken_edge_switch_expr (basic_block bb
, tree val
)
2036 tree switch_expr
, taken_case
;
2037 basic_block dest_bb
;
2040 if (TREE_CODE (val
) != INTEGER_CST
)
2043 switch_expr
= last_stmt (bb
);
2044 taken_case
= find_case_label_for_value (switch_expr
, val
);
2045 dest_bb
= label_to_block (CASE_LABEL (taken_case
));
2047 e
= find_edge (bb
, dest_bb
);
2054 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2055 We can make optimal use here of the fact that the case labels are
2056 sorted: We can do a binary search for a case matching VAL. */
2059 find_case_label_for_value (tree switch_expr
, tree val
)
2061 tree vec
= SWITCH_LABELS (switch_expr
);
2062 size_t low
, high
, n
= TREE_VEC_LENGTH (vec
);
2063 tree default_case
= TREE_VEC_ELT (vec
, n
- 1);
2065 for (low
= -1, high
= n
- 1; high
- low
> 1; )
2067 size_t i
= (high
+ low
) / 2;
2068 tree t
= TREE_VEC_ELT (vec
, i
);
2071 /* Cache the result of comparing CASE_LOW and val. */
2072 cmp
= tree_int_cst_compare (CASE_LOW (t
), val
);
2079 if (CASE_HIGH (t
) == NULL
)
2081 /* A singe-valued case label. */
2087 /* A case range. We can only handle integer ranges. */
2088 if (cmp
<= 0 && tree_int_cst_compare (CASE_HIGH (t
), val
) >= 0)
2093 return default_case
;
2097 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
2098 those alternatives are equal in each of the PHI nodes, then return
2099 true, else return false. */
2102 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
2104 tree phi
, val1
, val2
;
2107 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
2109 n1
= phi_arg_from_edge (phi
, e1
);
2110 n2
= phi_arg_from_edge (phi
, e2
);
2112 #ifdef ENABLE_CHECKING
2113 if (n1
< 0 || n2
< 0)
2117 val1
= PHI_ARG_DEF (phi
, n1
);
2118 val2
= PHI_ARG_DEF (phi
, n2
);
2120 if (!operand_equal_p (val1
, val2
, 0))
2128 /* Computing the Dominance Frontier:
2130 As described in Morgan, section 3.5, this may be done simply by
2131 walking the dominator tree bottom-up, computing the frontier for
2132 the children before the parent. When considering a block B,
2133 there are two cases:
2135 (1) A flow graph edge leaving B that does not lead to a child
2136 of B in the dominator tree must be a block that is either equal
2137 to B or not dominated by B. Such blocks belong in the frontier
2140 (2) Consider a block X in the frontier of one of the children C
2141 of B. If X is not equal to B and is not dominated by B, it
2142 is in the frontier of B. */
2145 compute_dominance_frontiers_1 (bitmap
*frontiers
, basic_block bb
, sbitmap done
)
2150 SET_BIT (done
, bb
->index
);
2152 /* Do the frontier of the children first. Not all children in the
2153 dominator tree (blocks dominated by this one) are children in the
2154 CFG, so check all blocks. */
2155 for (c
= first_dom_son (CDI_DOMINATORS
, bb
);
2157 c
= next_dom_son (CDI_DOMINATORS
, c
))
2159 if (! TEST_BIT (done
, c
->index
))
2160 compute_dominance_frontiers_1 (frontiers
, c
, done
);
2163 /* Find blocks conforming to rule (1) above. */
2164 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2166 if (e
->dest
== EXIT_BLOCK_PTR
)
2168 if (get_immediate_dominator (CDI_DOMINATORS
, e
->dest
) != bb
)
2169 bitmap_set_bit (frontiers
[bb
->index
], e
->dest
->index
);
2172 /* Find blocks conforming to rule (2). */
2173 for (c
= first_dom_son (CDI_DOMINATORS
, bb
);
2175 c
= next_dom_son (CDI_DOMINATORS
, c
))
2179 EXECUTE_IF_SET_IN_BITMAP (frontiers
[c
->index
], 0, x
,
2181 if (get_immediate_dominator (CDI_DOMINATORS
, BASIC_BLOCK (x
)) != bb
)
2182 bitmap_set_bit (frontiers
[bb
->index
], x
);
2189 compute_dominance_frontiers (bitmap
*frontiers
)
2191 sbitmap done
= sbitmap_alloc (last_basic_block
);
2193 timevar_push (TV_DOM_FRONTIERS
);
2195 sbitmap_zero (done
);
2197 compute_dominance_frontiers_1 (frontiers
, ENTRY_BLOCK_PTR
->succ
->dest
, done
);
2199 sbitmap_free (done
);
2201 timevar_pop (TV_DOM_FRONTIERS
);
2206 /*---------------------------------------------------------------------------
2208 ---------------------------------------------------------------------------*/
2210 /* Dump tree-specific information of block BB to file OUTF. */
2213 tree_dump_bb (basic_block bb
, FILE *outf
, int indent
)
2215 dump_generic_bb (outf
, bb
, indent
, TDF_VOPS
);
2219 /* Dump a basic block on stderr. */
2222 debug_tree_bb (basic_block bb
)
2224 dump_bb (bb
, stderr
, 0);
2228 /* Dump basic block with index N on stderr. */
2231 debug_tree_bb_n (int n
)
2233 debug_tree_bb (BASIC_BLOCK (n
));
2234 return BASIC_BLOCK (n
);
2238 /* Dump the CFG on stderr.
2240 FLAGS are the same used by the tree dumping functions
2241 (see TDF_* in tree.h). */
2244 debug_tree_cfg (int flags
)
2246 dump_tree_cfg (stderr
, flags
);
2250 /* Dump the program showing basic block boundaries on the given FILE.
2252 FLAGS are the same used by the tree dumping functions (see TDF_* in
2256 dump_tree_cfg (FILE *file
, int flags
)
2258 if (flags
& TDF_DETAILS
)
2260 const char *funcname
2261 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2264 fprintf (file
, ";; Function %s\n\n", funcname
);
2265 fprintf (file
, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2266 n_basic_blocks
, n_edges
, last_basic_block
);
2268 brief_dump_cfg (file
);
2269 fprintf (file
, "\n");
2272 if (flags
& TDF_STATS
)
2273 dump_cfg_stats (file
);
2275 dump_function_to_file (current_function_decl
, file
, flags
| TDF_BLOCKS
);
2279 /* Dump CFG statistics on FILE. */
2282 dump_cfg_stats (FILE *file
)
2284 static long max_num_merged_labels
= 0;
2285 unsigned long size
, total
= 0;
2288 const char * const fmt_str
= "%-30s%-13s%12s\n";
2289 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
2290 const char * const fmt_str_3
= "%-43s%11lu%c\n";
2291 const char *funcname
2292 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2295 fprintf (file
, "\nCFG Statistics for %s\n\n", funcname
);
2297 fprintf (file
, "---------------------------------------------------------\n");
2298 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
2299 fprintf (file
, fmt_str
, "", " instances ", "used ");
2300 fprintf (file
, "---------------------------------------------------------\n");
2302 size
= n_basic_blocks
* sizeof (struct basic_block_def
);
2304 fprintf (file
, fmt_str_1
, "Basic blocks", n_basic_blocks
, SCALE (size
),
2311 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2314 size
= n_edges
* sizeof (struct edge_def
);
2316 fprintf (file
, fmt_str_1
, "Edges", n_edges
, SCALE (size
), LABEL (size
));
2318 size
= n_basic_blocks
* sizeof (struct bb_ann_d
);
2320 fprintf (file
, fmt_str_1
, "Basic block annotations", n_basic_blocks
,
2321 SCALE (size
), LABEL (size
));
2323 fprintf (file
, "---------------------------------------------------------\n");
2324 fprintf (file
, fmt_str_3
, "Total memory used by CFG data", SCALE (total
),
2326 fprintf (file
, "---------------------------------------------------------\n");
2327 fprintf (file
, "\n");
2329 if (cfg_stats
.num_merged_labels
> max_num_merged_labels
)
2330 max_num_merged_labels
= cfg_stats
.num_merged_labels
;
2332 fprintf (file
, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2333 cfg_stats
.num_merged_labels
, max_num_merged_labels
);
2335 fprintf (file
, "\n");
2339 /* Dump CFG statistics on stderr. Keep extern so that it's always
2340 linked in the final executable. */
2343 debug_cfg_stats (void)
2345 dump_cfg_stats (stderr
);
2349 /* Dump the flowgraph to a .vcg FILE. */
2352 tree_cfg2vcg (FILE *file
)
2356 const char *funcname
2357 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2359 /* Write the file header. */
2360 fprintf (file
, "graph: { title: \"%s\"\n", funcname
);
2361 fprintf (file
, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2362 fprintf (file
, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2364 /* Write blocks and edges. */
2365 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2367 fprintf (file
, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2370 if (e
->flags
& EDGE_FAKE
)
2371 fprintf (file
, " linestyle: dotted priority: 10");
2373 fprintf (file
, " linestyle: solid priority: 100");
2375 fprintf (file
, " }\n");
2381 enum tree_code head_code
, end_code
;
2382 const char *head_name
, *end_name
;
2385 tree first
= first_stmt (bb
);
2386 tree last
= last_stmt (bb
);
2390 head_code
= TREE_CODE (first
);
2391 head_name
= tree_code_name
[head_code
];
2392 head_line
= get_lineno (first
);
2395 head_name
= "no-statement";
2399 end_code
= TREE_CODE (last
);
2400 end_name
= tree_code_name
[end_code
];
2401 end_line
= get_lineno (last
);
2404 end_name
= "no-statement";
2406 fprintf (file
, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2407 bb
->index
, bb
->index
, head_name
, head_line
, end_name
,
2410 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2412 if (e
->dest
== EXIT_BLOCK_PTR
)
2413 fprintf (file
, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb
->index
);
2415 fprintf (file
, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb
->index
, e
->dest
->index
);
2417 if (e
->flags
& EDGE_FAKE
)
2418 fprintf (file
, " priority: 10 linestyle: dotted");
2420 fprintf (file
, " priority: 100 linestyle: solid");
2422 fprintf (file
, " }\n");
2425 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2429 fputs ("}\n\n", file
);
2434 /*---------------------------------------------------------------------------
2435 Miscellaneous helpers
2436 ---------------------------------------------------------------------------*/
2438 /* Return true if T represents a stmt that always transfers control. */
2441 is_ctrl_stmt (tree t
)
2443 return (TREE_CODE (t
) == COND_EXPR
2444 || TREE_CODE (t
) == SWITCH_EXPR
2445 || TREE_CODE (t
) == GOTO_EXPR
2446 || TREE_CODE (t
) == RETURN_EXPR
2447 || TREE_CODE (t
) == RESX_EXPR
);
2451 /* Return true if T is a statement that may alter the flow of control
2452 (e.g., a call to a non-returning function). */
2455 is_ctrl_altering_stmt (tree t
)
2459 #if defined ENABLE_CHECKING
2464 switch (TREE_CODE (t
))
2467 /* A MODIFY_EXPR with a rhs of a call has the characteristics
2469 call
= TREE_OPERAND (t
, 1);
2470 if (TREE_CODE (call
) != CALL_EXPR
)
2475 /* A non-pure/const CALL_EXPR alters flow control if the current
2476 function has nonlocal labels. */
2477 if (TREE_SIDE_EFFECTS (t
)
2478 && current_function_has_nonlocal_label
)
2481 /* A CALL_EXPR also alters control flow if it does not return. */
2482 if (call_expr_flags (call
) & (ECF_NORETURN
| ECF_LONGJMP
))
2490 /* If a statement can throw, it alters control flow. */
2491 return tree_can_throw_internal (t
);
2495 /* Return true if T is a computed goto. */
2498 computed_goto_p (tree t
)
2500 return (TREE_CODE (t
) == GOTO_EXPR
2501 && TREE_CODE (GOTO_DESTINATION (t
)) != LABEL_DECL
);
2505 /* Checks whether EXPR is a simple local goto. */
2508 simple_goto_p (tree expr
)
2510 return (TREE_CODE (expr
) == GOTO_EXPR
2511 && TREE_CODE (GOTO_DESTINATION (expr
)) == LABEL_DECL
2512 && (decl_function_context (GOTO_DESTINATION (expr
))
2513 == current_function_decl
));
2517 /* Return true if T should start a new basic block. PREV_T is the
2518 statement preceding T. It is used when T is a label or a case label.
2519 Labels should only start a new basic block if their previous statement
2520 wasn't a label. Otherwise, sequence of labels would generate
2521 unnecessary basic blocks that only contain a single label. */
2524 stmt_starts_bb_p (tree t
, tree prev_t
)
2526 enum tree_code code
;
2531 /* LABEL_EXPRs start a new basic block only if the preceding
2532 statement wasn't a label of the same type. This prevents the
2533 creation of consecutive blocks that have nothing but a single
2535 code
= TREE_CODE (t
);
2536 if (code
== LABEL_EXPR
)
2538 /* Nonlocal and computed GOTO targets always start a new block. */
2539 if (code
== LABEL_EXPR
2540 && (DECL_NONLOCAL (LABEL_EXPR_LABEL (t
))
2541 || FORCED_LABEL (LABEL_EXPR_LABEL (t
))))
2544 if (prev_t
&& TREE_CODE (prev_t
) == code
)
2546 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t
)))
2549 cfg_stats
.num_merged_labels
++;
2560 /* Return true if T should end a basic block. */
2563 stmt_ends_bb_p (tree t
)
2565 return is_ctrl_stmt (t
) || is_ctrl_altering_stmt (t
);
2569 /* Add gotos that used to be represented implicitly in the CFG. */
2572 disband_implicit_edges (void)
2575 block_stmt_iterator last
;
2581 last
= bsi_last (bb
);
2582 stmt
= last_stmt (bb
);
2584 if (stmt
&& TREE_CODE (stmt
) == COND_EXPR
)
2586 /* Remove superfluous gotos from COND_EXPR branches. Moved
2587 from cfg_remove_useless_stmts here since it violates the
2588 invariants for tree--cfg correspondence and thus fits better
2589 here where we do it anyway. */
2590 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2592 if (e
->dest
!= bb
->next_bb
)
2595 if (e
->flags
& EDGE_TRUE_VALUE
)
2596 COND_EXPR_THEN (stmt
) = build_empty_stmt ();
2597 else if (e
->flags
& EDGE_FALSE_VALUE
)
2598 COND_EXPR_ELSE (stmt
) = build_empty_stmt ();
2601 e
->flags
|= EDGE_FALLTHRU
;
2607 if (stmt
&& TREE_CODE (stmt
) == RETURN_EXPR
)
2609 /* Remove the RETURN_EXPR if we may fall though to the exit
2612 || bb
->succ
->succ_next
2613 || bb
->succ
->dest
!= EXIT_BLOCK_PTR
)
2616 if (bb
->next_bb
== EXIT_BLOCK_PTR
2617 && !TREE_OPERAND (stmt
, 0))
2620 bb
->succ
->flags
|= EDGE_FALLTHRU
;
2625 /* There can be no fallthru edge if the last statement is a control
2627 if (stmt
&& is_ctrl_stmt (stmt
))
2630 /* Find a fallthru edge and emit the goto if necessary. */
2631 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2632 if (e
->flags
& EDGE_FALLTHRU
)
2635 if (!e
|| e
->dest
== bb
->next_bb
)
2638 if (e
->dest
== EXIT_BLOCK_PTR
)
2641 label
= tree_block_label (e
->dest
);
2643 stmt
= build1 (GOTO_EXPR
, void_type_node
, label
);
2644 SET_EXPR_LOCUS (stmt
, e
->goto_locus
);
2645 bsi_insert_after (&last
, stmt
, BSI_NEW_STMT
);
2646 e
->flags
&= ~EDGE_FALLTHRU
;
2650 /* Remove block annotations and other datastructures. */
2653 delete_tree_cfg_annotations (void)
2656 if (n_basic_blocks
> 0)
2657 free_blocks_annotations ();
2659 label_to_block_map
= NULL
;
2666 /* Return the first statement in basic block BB. */
2669 first_stmt (basic_block bb
)
2671 block_stmt_iterator i
= bsi_start (bb
);
2672 return !bsi_end_p (i
) ? bsi_stmt (i
) : NULL_TREE
;
2676 /* Return the last statement in basic block BB. */
2679 last_stmt (basic_block bb
)
2681 block_stmt_iterator b
= bsi_last (bb
);
2682 return !bsi_end_p (b
) ? bsi_stmt (b
) : NULL_TREE
;
2686 /* Return a pointer to the last statement in block BB. */
2689 last_stmt_ptr (basic_block bb
)
2691 block_stmt_iterator last
= bsi_last (bb
);
2692 return !bsi_end_p (last
) ? bsi_stmt_ptr (last
) : NULL
;
2696 /* Return the last statement of an otherwise empty block. Return NULL
2697 if the block is totally empty, or if it contains more than one
2701 last_and_only_stmt (basic_block bb
)
2703 block_stmt_iterator i
= bsi_last (bb
);
2709 last
= bsi_stmt (i
);
2714 /* Empty statements should no longer appear in the instruction stream.
2715 Everything that might have appeared before should be deleted by
2716 remove_useless_stmts, and the optimizers should just bsi_remove
2717 instead of smashing with build_empty_stmt.
2719 Thus the only thing that should appear here in a block containing
2720 one executable statement is a label. */
2721 prev
= bsi_stmt (i
);
2722 if (TREE_CODE (prev
) == LABEL_EXPR
)
2729 /* Mark BB as the basic block holding statement T. */
2732 set_bb_for_stmt (tree t
, basic_block bb
)
2734 if (TREE_CODE (t
) == STATEMENT_LIST
)
2736 tree_stmt_iterator i
;
2737 for (i
= tsi_start (t
); !tsi_end_p (i
); tsi_next (&i
))
2738 set_bb_for_stmt (tsi_stmt (i
), bb
);
2742 stmt_ann_t ann
= get_stmt_ann (t
);
2745 /* If the statement is a label, add the label to block-to-labels map
2746 so that we can speed up edge creation for GOTO_EXPRs. */
2747 if (TREE_CODE (t
) == LABEL_EXPR
)
2751 t
= LABEL_EXPR_LABEL (t
);
2752 uid
= LABEL_DECL_UID (t
);
2755 LABEL_DECL_UID (t
) = uid
= cfun
->last_label_uid
++;
2756 if (VARRAY_SIZE (label_to_block_map
) <= (unsigned) uid
)
2757 VARRAY_GROW (label_to_block_map
, 3 * uid
/ 2);
2761 #ifdef ENABLE_CHECKING
2762 /* We're moving an existing label. Make sure that we've
2763 removed it from the old block. */
2764 if (bb
&& VARRAY_BB (label_to_block_map
, uid
))
2768 VARRAY_BB (label_to_block_map
, uid
) = bb
;
2774 /* Insert statement (or statement list) T before the statement
2775 pointed-to by iterator I. M specifies how to update iterator I
2776 after insertion (see enum bsi_iterator_update). */
2779 bsi_insert_before (block_stmt_iterator
*i
, tree t
, enum bsi_iterator_update m
)
2781 set_bb_for_stmt (t
, i
->bb
);
2783 tsi_link_before (&i
->tsi
, t
, m
);
2787 /* Insert statement (or statement list) T after the statement
2788 pointed-to by iterator I. M specifies how to update iterator I
2789 after insertion (see enum bsi_iterator_update). */
2792 bsi_insert_after (block_stmt_iterator
*i
, tree t
, enum bsi_iterator_update m
)
2794 set_bb_for_stmt (t
, i
->bb
);
2796 tsi_link_after (&i
->tsi
, t
, m
);
2800 /* Remove the statement pointed to by iterator I. The iterator is updated
2801 to the next statement. */
2804 bsi_remove (block_stmt_iterator
*i
)
2806 tree t
= bsi_stmt (*i
);
2807 set_bb_for_stmt (t
, NULL
);
2809 tsi_delink (&i
->tsi
);
2813 /* Move the statement at FROM so it comes right after the statement at TO. */
2816 bsi_move_after (block_stmt_iterator
*from
, block_stmt_iterator
*to
)
2818 tree stmt
= bsi_stmt (*from
);
2820 bsi_insert_after (to
, stmt
, BSI_SAME_STMT
);
2824 /* Move the statement at FROM so it comes right before the statement at TO. */
2827 bsi_move_before (block_stmt_iterator
*from
, block_stmt_iterator
*to
)
2829 tree stmt
= bsi_stmt (*from
);
2831 bsi_insert_before (to
, stmt
, BSI_SAME_STMT
);
2835 /* Move the statement at FROM to the end of basic block BB. */
2838 bsi_move_to_bb_end (block_stmt_iterator
*from
, basic_block bb
)
2840 block_stmt_iterator last
= bsi_last (bb
);
2842 /* Have to check bsi_end_p because it could be an empty block. */
2843 if (!bsi_end_p (last
) && is_ctrl_stmt (bsi_stmt (last
)))
2844 bsi_move_before (from
, &last
);
2846 bsi_move_after (from
, &last
);
2850 /* Replace the contents of the statement pointed to by iterator BSI
2851 with STMT. If PRESERVE_EH_INFO is true, the exception handling
2852 information of the original statement is preserved. */
2855 bsi_replace (const block_stmt_iterator
*bsi
, tree stmt
, bool preserve_eh_info
)
2858 tree orig_stmt
= bsi_stmt (*bsi
);
2860 SET_EXPR_LOCUS (stmt
, EXPR_LOCUS (orig_stmt
));
2861 set_bb_for_stmt (stmt
, bsi
->bb
);
2863 /* Preserve EH region information from the original statement, if
2864 requested by the caller. */
2865 if (preserve_eh_info
)
2867 eh_region
= lookup_stmt_eh_region (orig_stmt
);
2869 add_stmt_to_eh_region (stmt
, eh_region
);
2872 *bsi_stmt_ptr (*bsi
) = stmt
;
2877 /* Insert the statement pointed-to by BSI into edge E. Every attempt
2878 is made to place the statement in an existing basic block, but
2879 sometimes that isn't possible. When it isn't possible, the edge is
2880 split and the statement is added to the new block.
2882 In all cases, the returned *BSI points to the correct location. The
2883 return value is true if insertion should be done after the location,
2884 or false if it should be done before the location. */
2887 tree_find_edge_insert_loc (edge e
, block_stmt_iterator
*bsi
)
2889 basic_block dest
, src
;
2895 /* If the destination has one predecessor which has no PHI nodes,
2896 insert there. Except for the exit block.
2898 The requirement for no PHI nodes could be relaxed. Basically we
2899 would have to examine the PHIs to prove that none of them used
2900 the value set by the statement we want to insert on E. That
2901 hardly seems worth the effort. */
2902 if (dest
->pred
->pred_next
== NULL
2903 && ! phi_nodes (dest
)
2904 && dest
!= EXIT_BLOCK_PTR
)
2906 *bsi
= bsi_start (dest
);
2907 if (bsi_end_p (*bsi
))
2910 /* Make sure we insert after any leading labels. */
2911 tmp
= bsi_stmt (*bsi
);
2912 while (TREE_CODE (tmp
) == LABEL_EXPR
)
2915 if (bsi_end_p (*bsi
))
2917 tmp
= bsi_stmt (*bsi
);
2920 if (bsi_end_p (*bsi
))
2922 *bsi
= bsi_last (dest
);
2929 /* If the source has one successor, the edge is not abnormal and
2930 the last statement does not end a basic block, insert there.
2931 Except for the entry block. */
2933 if ((e
->flags
& EDGE_ABNORMAL
) == 0
2934 && src
->succ
->succ_next
== NULL
2935 && src
!= ENTRY_BLOCK_PTR
)
2937 *bsi
= bsi_last (src
);
2938 if (bsi_end_p (*bsi
))
2941 tmp
= bsi_stmt (*bsi
);
2942 if (!stmt_ends_bb_p (tmp
))
2945 /* Insert code just before returning the value. We may need to decompose
2946 the return in the case it contains non-trivial operand. */
2947 if (TREE_CODE (tmp
) == RETURN_EXPR
)
2949 tree op
= TREE_OPERAND (tmp
, 0);
2950 if (!is_gimple_val (op
))
2952 if (TREE_CODE (op
) != MODIFY_EXPR
)
2954 bsi_insert_before (bsi
, op
, BSI_NEW_STMT
);
2955 TREE_OPERAND (tmp
, 0) = TREE_OPERAND (op
, 0);
2962 /* Otherwise, create a new basic block, and split this edge. */
2963 dest
= split_edge (e
);
2969 /* This routine will commit all pending edge insertions, creating any new
2970 basic blocks which are necessary.
2972 If specified, NEW_BLOCKS returns a count of the number of new basic
2973 blocks which were created. */
2976 bsi_commit_edge_inserts (int *new_blocks
)
2982 blocks
= n_basic_blocks
;
2984 bsi_commit_edge_inserts_1 (ENTRY_BLOCK_PTR
->succ
);
2987 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2988 bsi_commit_edge_inserts_1 (e
);
2991 *new_blocks
= n_basic_blocks
- blocks
;
2995 /* Commit insertions pending at edge E. */
2998 bsi_commit_edge_inserts_1 (edge e
)
3000 if (PENDING_STMT (e
))
3002 block_stmt_iterator bsi
;
3003 tree stmt
= PENDING_STMT (e
);
3005 PENDING_STMT (e
) = NULL_TREE
;
3007 if (tree_find_edge_insert_loc (e
, &bsi
))
3008 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
3010 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
3015 /* Add STMT to the pending list of edge E. No actual insertion is
3016 made until a call to bsi_commit_edge_inserts () is made. */
3019 bsi_insert_on_edge (edge e
, tree stmt
)
3021 append_to_statement_list (stmt
, &PENDING_STMT (e
));
3025 /* Specialized edge insertion for SSA-PRE. FIXME: This should
3026 probably disappear. The only reason it's here is because PRE needs
3027 the call to tree_find_edge_insert_loc(). */
3029 void pre_insert_on_edge (edge e
, tree stmt
);
3032 pre_insert_on_edge (edge e
, tree stmt
)
3034 block_stmt_iterator bsi
;
3036 if (PENDING_STMT (e
))
3039 if (tree_find_edge_insert_loc (e
, &bsi
))
3040 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
3042 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
3046 /*---------------------------------------------------------------------------
3047 Tree specific functions for CFG manipulation
3048 ---------------------------------------------------------------------------*/
3050 /* Split a (typically critical) edge EDGE_IN. Return the new block.
3051 Abort on abnormal edges. */
3054 tree_split_edge (edge edge_in
)
3056 basic_block new_bb
, after_bb
, dest
, src
;
3061 /* Abnormal edges cannot be split. */
3062 if (edge_in
->flags
& EDGE_ABNORMAL
)
3066 dest
= edge_in
->dest
;
3068 /* Place the new block in the block list. Try to keep the new block
3069 near its "logical" location. This is of most help to humans looking
3070 at debugging dumps. */
3071 for (e
= dest
->pred
; e
; e
= e
->pred_next
)
3072 if (e
->src
->next_bb
== dest
)
3075 after_bb
= dest
->prev_bb
;
3077 after_bb
= edge_in
->src
;
3079 new_bb
= create_empty_bb (after_bb
);
3080 new_edge
= make_edge (new_bb
, dest
, EDGE_FALLTHRU
);
3082 /* Find all the PHI arguments on the original edge, and change them to
3083 the new edge. Do it before redirection, so that the argument does not
3085 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
3087 num_elem
= PHI_NUM_ARGS (phi
);
3088 for (i
= 0; i
< num_elem
; i
++)
3089 if (PHI_ARG_EDGE (phi
, i
) == edge_in
)
3091 PHI_ARG_EDGE (phi
, i
) = new_edge
;
3096 if (!redirect_edge_and_branch (edge_in
, new_bb
))
3099 if (PENDING_STMT (edge_in
))
3106 /* Return true when BB has label LABEL in it. */
3109 has_label_p (basic_block bb
, tree label
)
3111 block_stmt_iterator bsi
;
3113 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3115 tree stmt
= bsi_stmt (bsi
);
3117 if (TREE_CODE (stmt
) != LABEL_EXPR
)
3119 if (LABEL_EXPR_LABEL (stmt
) == label
)
3126 /* Callback for walk_tree, check that all elements with address taken are
3127 properly noticed as such. */
3130 verify_expr (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
3131 void *data ATTRIBUTE_UNUSED
)
3138 switch (TREE_CODE (t
))
3141 if (SSA_NAME_IN_FREE_LIST (t
))
3143 error ("SSA name in freelist but still referenced");
3149 x
= TREE_OPERAND (t
, 0);
3150 if (TREE_CODE (x
) == BIT_FIELD_REF
3151 && is_gimple_reg (TREE_OPERAND (x
, 0)))
3153 error ("GIMPLE register modified with BIT_FIELD_REF");
3159 x
= TREE_OPERAND (t
, 0);
3160 while (TREE_CODE (x
) == ARRAY_REF
3161 || TREE_CODE (x
) == COMPONENT_REF
3162 || TREE_CODE (x
) == REALPART_EXPR
3163 || TREE_CODE (x
) == IMAGPART_EXPR
)
3164 x
= TREE_OPERAND (x
, 0);
3165 if (TREE_CODE (x
) != VAR_DECL
&& TREE_CODE (x
) != PARM_DECL
)
3167 if (!TREE_ADDRESSABLE (x
))
3169 error ("address taken, but ADDRESSABLE bit not set");
3175 x
= TREE_OPERAND (t
, 0);
3176 if (TREE_CODE (TREE_TYPE (x
)) != BOOLEAN_TYPE
)
3178 error ("non-boolean used in condition");
3185 case FIX_TRUNC_EXPR
:
3187 case FIX_FLOOR_EXPR
:
3188 case FIX_ROUND_EXPR
:
3193 case NON_LVALUE_EXPR
:
3194 case TRUTH_NOT_EXPR
:
3195 x
= TREE_OPERAND (t
, 0);
3196 /* We check for constants explicitly since they are not considered
3197 gimple invariants if they overflowed. */
3198 if (TREE_CODE_CLASS (TREE_CODE (x
)) != 'c'
3199 && !is_gimple_val (x
))
3201 error ("Invalid operand to unary operator");
3216 case UNORDERED_EXPR
:
3227 case TRUNC_DIV_EXPR
:
3229 case FLOOR_DIV_EXPR
:
3230 case ROUND_DIV_EXPR
:
3231 case TRUNC_MOD_EXPR
:
3233 case FLOOR_MOD_EXPR
:
3234 case ROUND_MOD_EXPR
:
3236 case EXACT_DIV_EXPR
:
3246 x
= TREE_OPERAND (t
, 0);
3247 /* We check for constants explicitly since they are not considered
3248 gimple invariants if they overflowed. */
3249 if (TREE_CODE_CLASS (TREE_CODE (x
)) != 'c'
3250 && !is_gimple_val (x
))
3252 error ("Invalid operand to binary operator");
3255 x
= TREE_OPERAND (t
, 1);
3256 /* We check for constants explicitly since they are not considered
3257 gimple invariants if they overflowed. */
3258 if (TREE_CODE_CLASS (TREE_CODE (x
)) != 'c'
3259 && !is_gimple_val (x
))
3261 error ("Invalid operand to binary operator");
3273 /* Verify STMT, return true if STMT is not in GIMPLE form.
3274 TODO: Implement type checking. */
3277 verify_stmt (tree stmt
)
3281 if (!is_gimple_stmt (stmt
))
3283 error ("Is not a valid GIMPLE statement.");
3284 debug_generic_stmt (stmt
);
3288 addr
= walk_tree (&stmt
, verify_expr
, NULL
, NULL
);
3291 debug_generic_stmt (addr
);
3299 /* Return true when the T can be shared. */
3302 tree_node_can_be_shared (tree t
)
3304 if (TYPE_P (t
) || DECL_P (t
)
3305 /* We check for constants explicitly since they are not considered
3306 gimple invariants if they overflowed. */
3307 || TREE_CODE_CLASS (TREE_CODE (t
)) == 'c'
3308 || is_gimple_min_invariant (t
)
3309 || TREE_CODE (t
) == SSA_NAME
)
3312 while ((TREE_CODE (t
) == ARRAY_REF
3313 /* We check for constants explicitly since they are not considered
3314 gimple invariants if they overflowed. */
3315 && (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t
, 1))) == 'c'
3316 || is_gimple_min_invariant (TREE_OPERAND (t
, 1))))
3317 || (TREE_CODE (t
) == COMPONENT_REF
3318 || TREE_CODE (t
) == REALPART_EXPR
3319 || TREE_CODE (t
) == IMAGPART_EXPR
))
3320 t
= TREE_OPERAND (t
, 0);
3329 /* Called via walk_trees. Verify tree sharing. */
3332 verify_node_sharing (tree
* tp
, int *walk_subtrees
, void *data
)
3334 htab_t htab
= (htab_t
) data
;
3337 if (tree_node_can_be_shared (*tp
))
3339 *walk_subtrees
= false;
3343 slot
= htab_find_slot (htab
, *tp
, INSERT
);
3352 /* Verify the GIMPLE statement chain. */
3358 block_stmt_iterator bsi
;
3363 timevar_push (TV_TREE_STMT_VERIFY
);
3364 htab
= htab_create (37, htab_hash_pointer
, htab_eq_pointer
, NULL
);
3371 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
3373 int phi_num_args
= PHI_NUM_ARGS (phi
);
3375 for (i
= 0; i
< phi_num_args
; i
++)
3377 tree t
= PHI_ARG_DEF (phi
, i
);
3380 /* Addressable variables do have SSA_NAMEs but they
3381 are not considered gimple values. */
3382 if (TREE_CODE (t
) != SSA_NAME
3383 && TREE_CODE (t
) != FUNCTION_DECL
3384 && !is_gimple_val (t
))
3386 error ("PHI def is not a GIMPLE value");
3387 debug_generic_stmt (phi
);
3388 debug_generic_stmt (t
);
3392 addr
= walk_tree (&t
, verify_expr
, NULL
, NULL
);
3395 debug_generic_stmt (addr
);
3399 addr
= walk_tree (&t
, verify_node_sharing
, htab
, NULL
);
3402 error ("Incorrect sharing of tree nodes");
3403 debug_generic_stmt (phi
);
3404 debug_generic_stmt (addr
);
3410 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3412 tree stmt
= bsi_stmt (bsi
);
3413 err
|= verify_stmt (stmt
);
3414 addr
= walk_tree (&stmt
, verify_node_sharing
, htab
, NULL
);
3417 error ("Incorrect sharing of tree nodes");
3418 debug_generic_stmt (stmt
);
3419 debug_generic_stmt (addr
);
3426 internal_error ("verify_stmts failed.");
3429 timevar_pop (TV_TREE_STMT_VERIFY
);
3433 /* Verifies that the flow information is OK. */
3436 tree_verify_flow_info (void)
3440 block_stmt_iterator bsi
;
3444 if (ENTRY_BLOCK_PTR
->stmt_list
)
3446 error ("ENTRY_BLOCK has a statement list associated with it\n");
3450 if (EXIT_BLOCK_PTR
->stmt_list
)
3452 error ("EXIT_BLOCK has a statement list associated with it\n");
3456 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
3457 if (e
->flags
& EDGE_FALLTHRU
)
3459 error ("Fallthru to exit from bb %d\n", e
->src
->index
);
3465 bool found_ctrl_stmt
= false;
3467 /* Skip labels on the start of basic block. */
3468 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3470 if (TREE_CODE (bsi_stmt (bsi
)) != LABEL_EXPR
)
3473 if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi
))) != bb
)
3475 error ("Label %s to block does not match in bb %d\n",
3476 IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi
))),
3481 if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi
)))
3482 != current_function_decl
)
3484 error ("Label %s has incorrect context in bb %d\n",
3485 IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi
))),
3491 /* Verify that body of basic block BB is free of control flow. */
3492 for (; !bsi_end_p (bsi
); bsi_next (&bsi
))
3494 tree stmt
= bsi_stmt (bsi
);
3496 if (found_ctrl_stmt
)
3498 error ("Control flow in the middle of basic block %d\n",
3503 if (stmt_ends_bb_p (stmt
))
3504 found_ctrl_stmt
= true;
3506 if (TREE_CODE (stmt
) == LABEL_EXPR
)
3508 error ("Label %s in the middle of basic block %d\n",
3509 IDENTIFIER_POINTER (DECL_NAME (stmt
)),
3514 bsi
= bsi_last (bb
);
3515 if (bsi_end_p (bsi
))
3518 stmt
= bsi_stmt (bsi
);
3520 if (is_ctrl_stmt (stmt
))
3522 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3523 if (e
->flags
& EDGE_FALLTHRU
)
3525 error ("Fallthru edge after a control statement in bb %d \n",
3531 switch (TREE_CODE (stmt
))
3537 if (TREE_CODE (COND_EXPR_THEN (stmt
)) != GOTO_EXPR
3538 || TREE_CODE (COND_EXPR_ELSE (stmt
)) != GOTO_EXPR
)
3540 error ("Structured COND_EXPR at the end of bb %d\n", bb
->index
);
3544 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
3546 if (!true_edge
|| !false_edge
3547 || !(true_edge
->flags
& EDGE_TRUE_VALUE
)
3548 || !(false_edge
->flags
& EDGE_FALSE_VALUE
)
3549 || (true_edge
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
))
3550 || (false_edge
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
))
3551 || bb
->succ
->succ_next
->succ_next
)
3553 error ("Wrong outgoing edge flags at end of bb %d\n",
3558 if (!has_label_p (true_edge
->dest
,
3559 GOTO_DESTINATION (COND_EXPR_THEN (stmt
))))
3561 error ("`then' label does not match edge at end of bb %d\n",
3566 if (!has_label_p (false_edge
->dest
,
3567 GOTO_DESTINATION (COND_EXPR_ELSE (stmt
))))
3569 error ("`else' label does not match edge at end of bb %d\n",
3577 if (simple_goto_p (stmt
))
3579 error ("Explicit goto at end of bb %d\n", bb
->index
);
3584 /* FIXME. We should double check that the labels in the
3585 destination blocks have their address taken. */
3586 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3587 if ((e
->flags
& (EDGE_FALLTHRU
| EDGE_TRUE_VALUE
3588 | EDGE_FALSE_VALUE
))
3589 || !(e
->flags
& EDGE_ABNORMAL
))
3591 error ("Wrong outgoing edge flags at end of bb %d\n",
3599 if (!bb
->succ
|| bb
->succ
->succ_next
3600 || (bb
->succ
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
3601 | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
3603 error ("Wrong outgoing edge flags at end of bb %d\n", bb
->index
);
3606 if (bb
->succ
->dest
!= EXIT_BLOCK_PTR
)
3608 error ("Return edge does not point to exit in bb %d\n",
3621 vec
= SWITCH_LABELS (stmt
);
3622 n
= TREE_VEC_LENGTH (vec
);
3624 /* Mark all the destination basic blocks. */
3625 for (i
= 0; i
< n
; ++i
)
3627 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
3628 basic_block label_bb
= label_to_block (lab
);
3630 if (label_bb
->aux
&& label_bb
->aux
!= (void *)1)
3632 label_bb
->aux
= (void *)1;
3635 /* Verify that the case labels are sorted. */
3636 prev
= TREE_VEC_ELT (vec
, 0);
3637 for (i
= 1; i
< n
- 1; ++i
)
3639 tree c
= TREE_VEC_ELT (vec
, i
);
3642 error ("Found default case not at end of case vector");
3646 if (! tree_int_cst_lt (CASE_LOW (prev
), CASE_LOW (c
)))
3648 error ("Case labels not sorted:\n ");
3649 print_generic_expr (stderr
, prev
, 0);
3650 fprintf (stderr
," is greater than ");
3651 print_generic_expr (stderr
, c
, 0);
3652 fprintf (stderr
," but comes before it.\n");
3657 if (CASE_LOW (TREE_VEC_ELT (vec
, n
- 1)))
3659 error ("No default case found at end of case vector");
3663 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3667 error ("Extra outgoing edge %d->%d\n",
3668 bb
->index
, e
->dest
->index
);
3671 e
->dest
->aux
= (void *)2;
3672 if ((e
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
3673 | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
3675 error ("Wrong outgoing edge flags at end of bb %d\n",
3681 /* Check that we have all of them. */
3682 for (i
= 0; i
< n
; ++i
)
3684 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
3685 basic_block label_bb
= label_to_block (lab
);
3687 if (label_bb
->aux
!= (void *)2)
3689 error ("Missing edge %i->%i\n",
3690 bb
->index
, label_bb
->index
);
3695 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3696 e
->dest
->aux
= (void *)0;
3703 if (dom_computed
[CDI_DOMINATORS
] >= DOM_NO_FAST_QUERY
)
3704 verify_dominators (CDI_DOMINATORS
);
3710 /* Updates phi nodes after creating forwarder block joined
3711 by edge FALLTHRU. */
3714 tree_make_forwarder_block (edge fallthru
)
3717 basic_block dummy
, bb
;
3718 tree phi
, new_phi
, var
, prev
, next
;
3720 dummy
= fallthru
->src
;
3721 bb
= fallthru
->dest
;
3723 if (!bb
->pred
->pred_next
)
3726 /* If we redirected a branch we must create new phi nodes at the
3728 for (phi
= phi_nodes (dummy
); phi
; phi
= PHI_CHAIN (phi
))
3730 var
= PHI_RESULT (phi
);
3731 new_phi
= create_phi_node (var
, bb
);
3732 SSA_NAME_DEF_STMT (var
) = new_phi
;
3733 SET_PHI_RESULT (phi
, make_ssa_name (SSA_NAME_VAR (var
), phi
));
3734 add_phi_arg (&new_phi
, PHI_RESULT (phi
), fallthru
);
3737 /* Ensure that the PHI node chain is in the same order. */
3739 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
3741 next
= PHI_CHAIN (phi
);
3742 PHI_CHAIN (phi
) = prev
;
3745 set_phi_nodes (bb
, prev
);
3747 /* Add the arguments we have stored on edges. */
3748 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
3753 for (phi
= phi_nodes (bb
), var
= PENDING_STMT (e
);
3755 phi
= PHI_CHAIN (phi
), var
= TREE_CHAIN (var
))
3756 add_phi_arg (&phi
, TREE_VALUE (var
), e
);
3758 PENDING_STMT (e
) = NULL
;
3763 /* Return true if basic block BB does nothing except pass control
3764 flow to another block and that we can safely insert a label at
3765 the start of the successor block. */
3768 tree_forwarder_block_p (basic_block bb
)
3770 block_stmt_iterator bsi
;
3773 /* If we have already determined that this block is not forwardable,
3774 then no further checks are necessary. */
3775 if (! bb_ann (bb
)->forwardable
)
3778 /* BB must have a single outgoing normal edge. Otherwise it can not be
3779 a forwarder block. */
3781 || bb
->succ
->succ_next
3782 || bb
->succ
->dest
== EXIT_BLOCK_PTR
3783 || (bb
->succ
->flags
& EDGE_ABNORMAL
)
3784 || bb
== ENTRY_BLOCK_PTR
)
3786 bb_ann (bb
)->forwardable
= 0;
3790 /* Successors of the entry block are not forwarders. */
3791 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
3794 bb_ann (bb
)->forwardable
= 0;
3798 /* BB can not have any PHI nodes. This could potentially be relaxed
3799 early in compilation if we re-rewrote the variables appearing in
3800 any PHI nodes in forwarder blocks. */
3803 bb_ann (bb
)->forwardable
= 0;
3807 /* Now walk through the statements. We can ignore labels, anything else
3808 means this is not a forwarder block. */
3809 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3811 tree stmt
= bsi_stmt (bsi
);
3813 switch (TREE_CODE (stmt
))
3816 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt
)))
3821 bb_ann (bb
)->forwardable
= 0;
3830 /* Thread jumps over empty statements.
3832 This code should _not_ thread over obviously equivalent conditions
3833 as that requires nontrivial updates to the SSA graph. */
3838 edge e
, next
, last
, old
;
3839 basic_block bb
, dest
, tmp
;
3842 bool retval
= false;
3845 bb_ann (bb
)->forwardable
= 1;
3847 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
3849 /* Don't waste time on unreachable blocks. */
3853 /* Nor on forwarders. */
3854 if (tree_forwarder_block_p (bb
))
3857 /* This block is now part of a forwarding path, mark it as not
3858 forwardable so that we can detect loops. This bit will be
3860 bb_ann (bb
)->forwardable
= 0;
3862 /* Examine each of our block's successors to see if it is
3864 for (e
= bb
->succ
; e
; e
= next
)
3866 next
= e
->succ_next
;
3868 /* If the edge is abnormal or its destination is not
3869 forwardable, then there's nothing to do. */
3870 if ((e
->flags
& EDGE_ABNORMAL
)
3871 || !tree_forwarder_block_p (e
->dest
))
3874 /* Now walk through as many forwarder block as possible to
3875 find the ultimate destination we want to thread our jump
3877 last
= e
->dest
->succ
;
3878 bb_ann (e
->dest
)->forwardable
= 0;
3879 for (dest
= e
->dest
->succ
->dest
;
3880 tree_forwarder_block_p (dest
);
3882 dest
= dest
->succ
->dest
)
3884 /* An infinite loop detected. We redirect the edge anyway, so
3885 that the loop is shrinked into single basic block. */
3886 if (!bb_ann (dest
)->forwardable
)
3889 if (dest
->succ
->dest
== EXIT_BLOCK_PTR
)
3892 bb_ann (dest
)->forwardable
= 0;
3895 /* Reset the forwardable marks to 1. */
3898 tmp
= tmp
->succ
->dest
)
3899 bb_ann (tmp
)->forwardable
= 1;
3901 if (dest
== e
->dest
)
3904 old
= find_edge (bb
, dest
);
3907 /* If there already is an edge, check whether the values
3908 in phi nodes differ. */
3909 if (!phi_alternatives_equal (dest
, last
, old
))
3911 /* The previous block is forwarder. Redirect our jump
3912 to that target instead since we know it has no PHI
3913 nodes that will need updating. */
3916 /* That might mean that no forwarding at all is possible. */
3917 if (dest
== e
->dest
)
3920 old
= find_edge (bb
, dest
);
3924 /* Perform the redirection. */
3926 e
= redirect_edge_and_branch (e
, dest
);
3928 /* TODO -- updating dominators in this case is simple. */
3929 free_dominance_info (CDI_DOMINATORS
);
3933 /* Update PHI nodes. We know that the new argument should
3934 have the same value as the argument associated with LAST.
3935 Otherwise we would have changed our target block above. */
3936 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
3938 arg
= phi_arg_from_edge (phi
, last
);
3941 add_phi_arg (&phi
, PHI_ARG_DEF (phi
, arg
), e
);
3946 /* Reset the forwardable bit on our block since it's no longer in
3947 a forwarding chain path. */
3948 bb_ann (bb
)->forwardable
= 1;
3955 /* Return a non-special label in the head of basic block BLOCK.
3956 Create one if it doesn't exist. */
3959 tree_block_label (basic_block bb
)
3961 block_stmt_iterator i
, s
= bsi_start (bb
);
3965 for (i
= s
; !bsi_end_p (i
); first
= false, bsi_next (&i
))
3967 stmt
= bsi_stmt (i
);
3968 if (TREE_CODE (stmt
) != LABEL_EXPR
)
3970 label
= LABEL_EXPR_LABEL (stmt
);
3971 if (!DECL_NONLOCAL (label
))
3974 bsi_move_before (&i
, &s
);
3979 label
= create_artificial_label ();
3980 stmt
= build1 (LABEL_EXPR
, void_type_node
, label
);
3981 bsi_insert_before (&s
, stmt
, BSI_NEW_STMT
);
3986 /* Attempt to perform edge redirection by replacing a possibly complex
3987 jump instruction by a goto or by removing the jump completely.
3988 This can apply only if all edges now point to the same block. The
3989 parameters and return values are equivalent to
3990 redirect_edge_and_branch. */
3993 tree_try_redirect_by_replacing_jump (edge e
, basic_block target
)
3995 basic_block src
= e
->src
;
3997 block_stmt_iterator b
;
4000 /* Verify that all targets will be TARGET. */
4001 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
4002 if (tmp
->dest
!= target
&& tmp
!= e
)
4011 stmt
= bsi_stmt (b
);
4013 if (TREE_CODE (stmt
) == COND_EXPR
4014 || TREE_CODE (stmt
) == SWITCH_EXPR
)
4017 e
= ssa_redirect_edge (e
, target
);
4018 e
->flags
= EDGE_FALLTHRU
;
4026 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
4027 edge representing the redirected branch. */
4030 tree_redirect_edge_and_branch (edge e
, basic_block dest
)
4032 basic_block bb
= e
->src
;
4033 block_stmt_iterator bsi
;
4037 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4040 if (e
->src
!= ENTRY_BLOCK_PTR
4041 && (ret
= tree_try_redirect_by_replacing_jump (e
, dest
)))
4044 if (e
->dest
== dest
)
4047 label
= tree_block_label (dest
);
4049 bsi
= bsi_last (bb
);
4050 stmt
= bsi_end_p (bsi
) ? NULL
: bsi_stmt (bsi
);
4052 switch (stmt
? TREE_CODE (stmt
) : ERROR_MARK
)
4055 stmt
= (e
->flags
& EDGE_TRUE_VALUE
4056 ? COND_EXPR_THEN (stmt
)
4057 : COND_EXPR_ELSE (stmt
));
4058 GOTO_DESTINATION (stmt
) = label
;
4062 /* No non-abnormal edges should lead from a non-simple goto, and
4063 simple ones should be represented implicitly. */
4068 tree vec
= SWITCH_LABELS (stmt
);
4069 size_t i
, n
= TREE_VEC_LENGTH (vec
);
4071 for (i
= 0; i
< n
; ++i
)
4073 tree elt
= TREE_VEC_ELT (vec
, i
);
4074 if (label_to_block (CASE_LABEL (elt
)) == e
->dest
)
4075 CASE_LABEL (elt
) = label
;
4082 e
->flags
|= EDGE_FALLTHRU
;
4086 /* Otherwise it must be a fallthru edge, and we don't need to
4087 do anything besides redirecting it. */
4088 if (!(e
->flags
& EDGE_FALLTHRU
))
4093 /* Update/insert PHI nodes as necessary. */
4095 /* Now update the edges in the CFG. */
4096 e
= ssa_redirect_edge (e
, dest
);
4102 /* Simple wrapper, as we can always redirect fallthru edges. */
4105 tree_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4107 e
= tree_redirect_edge_and_branch (e
, dest
);
4115 /* Splits basic block BB after statement STMT (but at least after the
4116 labels). If STMT is NULL, BB is split just after the labels. */
4119 tree_split_block (basic_block bb
, void *stmt
)
4121 block_stmt_iterator bsi
, bsi_tgt
;
4126 new_bb
= create_empty_bb (bb
);
4128 /* Redirect the outgoing edges. */
4129 new_bb
->succ
= bb
->succ
;
4131 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
4134 if (stmt
&& TREE_CODE ((tree
) stmt
) == LABEL_EXPR
)
4137 /* Move everything from BSI to the new basic block. */
4138 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4140 act
= bsi_stmt (bsi
);
4141 if (TREE_CODE (act
) == LABEL_EXPR
)
4154 bsi_tgt
= bsi_start (new_bb
);
4155 while (!bsi_end_p (bsi
))
4157 act
= bsi_stmt (bsi
);
4159 bsi_insert_after (&bsi_tgt
, act
, BSI_NEW_STMT
);
4166 /* Moves basic block BB after block AFTER. */
4169 tree_move_block_after (basic_block bb
, basic_block after
)
4171 if (bb
->prev_bb
== after
)
4175 link_block (bb
, after
);
4181 /* Return true if basic_block can be duplicated. */
4184 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED
)
4190 /* Create a duplicate of the basic block BB. NOTE: This does not
4191 preserve SSA form. */
4194 tree_duplicate_bb (basic_block bb
)
4197 block_stmt_iterator bsi
, bsi_tgt
;
4199 new_bb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
4200 bsi_tgt
= bsi_start (new_bb
);
4201 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4203 tree stmt
= bsi_stmt (bsi
);
4205 if (TREE_CODE (stmt
) == LABEL_EXPR
)
4208 bsi_insert_after (&bsi_tgt
, unshare_expr (stmt
), BSI_NEW_STMT
);
4215 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
4218 dump_function_to_file (tree fn
, FILE *file
, int flags
)
4220 tree arg
, vars
, var
;
4221 bool ignore_topmost_bind
= false, any_var
= false;
4225 fprintf (file
, "%s (", lang_hooks
.decl_printable_name (fn
, 2));
4227 arg
= DECL_ARGUMENTS (fn
);
4230 print_generic_expr (file
, arg
, dump_flags
);
4231 if (TREE_CHAIN (arg
))
4232 fprintf (file
, ", ");
4233 arg
= TREE_CHAIN (arg
);
4235 fprintf (file
, ")\n");
4237 if (flags
& TDF_RAW
)
4239 dump_node (fn
, TDF_SLIM
| flags
, file
);
4243 /* When GIMPLE is lowered, the variables are no longer available in
4244 BIND_EXPRs, so display them separately. */
4245 if (cfun
&& cfun
->unexpanded_var_list
)
4247 ignore_topmost_bind
= true;
4249 fprintf (file
, "{\n");
4250 for (vars
= cfun
->unexpanded_var_list
; vars
; vars
= TREE_CHAIN (vars
))
4252 var
= TREE_VALUE (vars
);
4254 print_generic_decl (file
, var
, flags
);
4255 fprintf (file
, "\n");
4261 if (basic_block_info
)
4263 /* Make a CFG based dump. */
4264 if (!ignore_topmost_bind
)
4265 fprintf (file
, "{\n");
4267 if (any_var
&& n_basic_blocks
)
4268 fprintf (file
, "\n");
4271 dump_generic_bb (file
, bb
, 2, flags
);
4273 fprintf (file
, "}\n");
4279 /* Make a tree based dump. */
4280 chain
= DECL_SAVED_TREE (fn
);
4282 if (TREE_CODE (chain
) == BIND_EXPR
)
4284 if (ignore_topmost_bind
)
4286 chain
= BIND_EXPR_BODY (chain
);
4294 if (!ignore_topmost_bind
)
4295 fprintf (file
, "{\n");
4300 fprintf (file
, "\n");
4302 print_generic_stmt_indented (file
, chain
, flags
, indent
);
4303 if (ignore_topmost_bind
)
4304 fprintf (file
, "}\n");
4307 fprintf (file
, "\n\n");
4311 /* Pretty print of the loops intermediate representation. */
4312 static void print_loop (FILE *, struct loop
*, int);
4313 static void print_pred_bbs (FILE *, edge
);
4314 static void print_succ_bbs (FILE *, edge
);
4317 /* Print the predecessors indexes of edge E on FILE. */
4320 print_pred_bbs (FILE *file
, edge e
)
4325 else if (e
->pred_next
== NULL
)
4326 fprintf (file
, "bb_%d", e
->src
->index
);
4330 fprintf (file
, "bb_%d, ", e
->src
->index
);
4331 print_pred_bbs (file
, e
->pred_next
);
4336 /* Print the successors indexes of edge E on FILE. */
4339 print_succ_bbs (FILE *file
, edge e
)
4343 else if (e
->succ_next
== NULL
)
4344 fprintf (file
, "bb_%d", e
->dest
->index
);
4347 fprintf (file
, "bb_%d, ", e
->dest
->index
);
4348 print_succ_bbs (file
, e
->succ_next
);
4353 /* Pretty print LOOP on FILE, indented INDENT spaces. */
4356 print_loop (FILE *file
, struct loop
*loop
, int indent
)
4364 s_indent
= (char *) alloca ((size_t) indent
+ 1);
4365 memset ((void *) s_indent
, ' ', (size_t) indent
);
4366 s_indent
[indent
] = '\0';
4368 /* Print the loop's header. */
4369 fprintf (file
, "%sloop_%d\n", s_indent
, loop
->num
);
4371 /* Print the loop's body. */
4372 fprintf (file
, "%s{\n", s_indent
);
4374 if (bb
->loop_father
== loop
)
4376 /* Print the basic_block's header. */
4377 fprintf (file
, "%s bb_%d (preds = {", s_indent
, bb
->index
);
4378 print_pred_bbs (file
, bb
->pred
);
4379 fprintf (file
, "}, succs = {");
4380 print_succ_bbs (file
, bb
->succ
);
4381 fprintf (file
, "})\n");
4383 /* Print the basic_block's body. */
4384 fprintf (file
, "%s {\n", s_indent
);
4385 tree_dump_bb (bb
, file
, indent
+ 4);
4386 fprintf (file
, "%s }\n", s_indent
);
4389 print_loop (file
, loop
->inner
, indent
+ 2);
4390 fprintf (file
, "%s}\n", s_indent
);
4391 print_loop (file
, loop
->next
, indent
);
4395 /* Follow a CFG edge from the entry point of the program, and on entry
4396 of a loop, pretty print the loop structure on FILE. */
4399 print_loop_ir (FILE *file
)
4403 bb
= BASIC_BLOCK (0);
4404 if (bb
&& bb
->loop_father
)
4405 print_loop (file
, bb
->loop_father
, 0);
4409 /* Debugging loops structure at tree level. */
4412 debug_loop_ir (void)
4414 print_loop_ir (stderr
);
4418 /* Return true if BB ends with a call, possibly followed by some
4419 instructions that must stay with the call. Return false,
4423 tree_block_ends_with_call_p (basic_block bb
)
4425 block_stmt_iterator bsi
= bsi_last (bb
);
4426 tree t
= tsi_stmt (bsi
.tsi
);
4428 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
4429 t
= TREE_OPERAND (t
, 0);
4431 if (TREE_CODE (t
) == MODIFY_EXPR
)
4432 t
= TREE_OPERAND (t
, 1);
4434 return TREE_CODE (t
) == CALL_EXPR
;
4438 /* Return true if BB ends with a conditional branch. Return false,
4442 tree_block_ends_with_condjump_p (basic_block bb
)
4444 tree stmt
= tsi_stmt (bsi_last (bb
).tsi
);
4445 return (TREE_CODE (stmt
) == COND_EXPR
);
4449 /* Return true if we need to add fake edge to exit at statement T.
4450 Helper function for tree_flow_call_edges_add. */
4453 need_fake_edge_p (tree t
)
4455 if (TREE_CODE (t
) == RETURN_EXPR
&& TREE_OPERAND (t
, 0))
4456 t
= TREE_OPERAND (t
, 0);
4458 if (TREE_CODE (t
) == MODIFY_EXPR
)
4459 t
= TREE_OPERAND (t
, 1);
4461 /* NORETURN and LONGJMP calls already have an edge to exit.
4462 CONST, PURE and ALWAYS_RETURN calls do not need one.
4463 We don't currently check for CONST and PURE here, although
4464 it would be a good idea, because those attributes are
4465 figured out from the RTL in mark_constant_function, and
4466 the counter incrementation code from -fprofile-arcs
4467 leads to different results from -fbranch-probabilities. */
4468 if (TREE_CODE (t
) == CALL_EXPR
4469 && !(call_expr_flags (t
) &
4470 (ECF_NORETURN
| ECF_LONGJMP
| ECF_ALWAYS_RETURN
)))
4473 if (TREE_CODE (t
) == ASM_EXPR
4474 && (ASM_VOLATILE_P (t
) || ASM_INPUT_P (t
)))
4481 /* Add fake edges to the function exit for any non constant and non
4482 noreturn calls, volatile inline assembly in the bitmap of blocks
4483 specified by BLOCKS or to the whole CFG if BLOCKS is zero. Return
4484 the number of blocks that were split.
4486 The goal is to expose cases in which entering a basic block does
4487 not imply that all subsequent instructions must be executed. */
4490 tree_flow_call_edges_add (sbitmap blocks
)
4493 int blocks_split
= 0;
4494 int last_bb
= last_basic_block
;
4495 bool check_last_block
= false;
4497 if (n_basic_blocks
== 0)
4501 check_last_block
= true;
4503 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
4505 /* In the last basic block, before epilogue generation, there will be
4506 a fallthru edge to EXIT. Special care is required if the last insn
4507 of the last basic block is a call because make_edge folds duplicate
4508 edges, which would result in the fallthru edge also being marked
4509 fake, which would result in the fallthru edge being removed by
4510 remove_fake_edges, which would result in an invalid CFG.
4512 Moreover, we can't elide the outgoing fake edge, since the block
4513 profiler needs to take this into account in order to solve the minimal
4514 spanning tree in the case that the call doesn't return.
4516 Handle this by adding a dummy instruction in a new last basic block. */
4517 if (check_last_block
)
4519 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
4520 block_stmt_iterator bsi
= bsi_last (bb
);
4522 if (!bsi_end_p (bsi
))
4525 if (need_fake_edge_p (t
))
4529 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4530 if (e
->dest
== EXIT_BLOCK_PTR
)
4532 bsi_insert_on_edge (e
, build_empty_stmt ());
4533 bsi_commit_edge_inserts ((int *)NULL
);
4539 /* Now add fake edges to the function exit for any non constant
4540 calls since there is no way that we can determine if they will
4542 for (i
= 0; i
< last_bb
; i
++)
4544 basic_block bb
= BASIC_BLOCK (i
);
4545 block_stmt_iterator bsi
;
4546 tree stmt
, last_stmt
;
4551 if (blocks
&& !TEST_BIT (blocks
, i
))
4554 bsi
= bsi_last (bb
);
4555 if (!bsi_end_p (bsi
))
4557 last_stmt
= bsi_stmt (bsi
);
4560 stmt
= bsi_stmt (bsi
);
4561 if (need_fake_edge_p (stmt
))
4564 /* The handling above of the final block before the
4565 epilogue should be enough to verify that there is
4566 no edge to the exit block in CFG already.
4567 Calling make_edge in such case would cause us to
4568 mark that edge as fake and remove it later. */
4569 #ifdef ENABLE_CHECKING
4570 if (stmt
== last_stmt
)
4571 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4572 if (e
->dest
== EXIT_BLOCK_PTR
)
4576 /* Note that the following may create a new basic block
4577 and renumber the existing basic blocks. */
4578 if (stmt
!= last_stmt
)
4580 e
= split_block (bb
, stmt
);
4584 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
4588 while (!bsi_end_p (bsi
));
4593 verify_flow_info ();
4595 return blocks_split
;
4599 struct cfg_hooks tree_cfg_hooks
= {
4601 tree_verify_flow_info
,
4602 tree_dump_bb
, /* dump_bb */
4603 create_bb
, /* create_basic_block */
4604 tree_redirect_edge_and_branch
,/* redirect_edge_and_branch */
4605 tree_redirect_edge_and_branch_force
,/* redirect_edge_and_branch_force */
4606 remove_bb
, /* delete_basic_block */
4607 tree_split_block
, /* split_block */
4608 tree_move_block_after
, /* move_block_after */
4609 tree_can_merge_blocks_p
, /* can_merge_blocks_p */
4610 tree_merge_blocks
, /* merge_blocks */
4611 tree_predict_edge
, /* predict_edge */
4612 tree_predicted_by_p
, /* predicted_by_p */
4613 tree_can_duplicate_bb_p
, /* can_duplicate_block_p */
4614 tree_duplicate_bb
, /* duplicate_block */
4615 tree_split_edge
, /* split_edge */
4616 tree_make_forwarder_block
, /* make_forward_block */
4617 NULL
, /* tidy_fallthru_edge */
4618 tree_block_ends_with_call_p
, /* block_ends_with_call_p */
4619 tree_block_ends_with_condjump_p
, /* block_ends_with_condjump_p */
4620 tree_flow_call_edges_add
/* flow_call_edges_add */
4624 /* Split all critical edges. */
4627 split_critical_edges (void)
4634 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4635 if (EDGE_CRITICAL_P (e
) && !(e
->flags
& EDGE_ABNORMAL
))
4642 struct tree_opt_pass pass_split_crit_edges
=
4644 "crited", /* name */
4646 split_critical_edges
, /* execute */
4649 0, /* static_pass_number */
4650 TV_TREE_SPLIT_EDGES
, /* tv_id */
4651 PROP_cfg
, /* properties required */
4652 PROP_no_crit_edges
, /* properties_provided */
4653 0, /* properties_destroyed */
4654 0, /* todo_flags_start */
4655 TODO_dump_func
, /* todo_flags_finish */
4658 /* Emit return warnings. */
4661 execute_warn_function_return (void)
4667 if (warn_missing_noreturn
4668 && !TREE_THIS_VOLATILE (cfun
->decl
)
4669 && EXIT_BLOCK_PTR
->pred
== NULL
4670 && !lang_hooks
.function
.missing_noreturn_ok_p (cfun
->decl
))
4671 warning ("%Jfunction might be possible candidate for attribute `noreturn'",
4674 /* If we have a path to EXIT, then we do return. */
4675 if (TREE_THIS_VOLATILE (cfun
->decl
)
4676 && EXIT_BLOCK_PTR
->pred
!= NULL
)
4679 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
4681 last
= last_stmt (e
->src
);
4682 if (TREE_CODE (last
) == RETURN_EXPR
4683 && (locus
= EXPR_LOCUS (last
)) != NULL
)
4687 locus
= &cfun
->function_end_locus
;
4688 warning ("%H`noreturn' function does return", locus
);
4691 /* If we see "return;" in some basic block, then we do reach the end
4692 without returning a value. */
4693 else if (warn_return_type
4694 && EXIT_BLOCK_PTR
->pred
!= NULL
4695 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun
->decl
))))
4697 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
4699 tree last
= last_stmt (e
->src
);
4700 if (TREE_CODE (last
) == RETURN_EXPR
4701 && TREE_OPERAND (last
, 0) == NULL
)
4703 locus
= EXPR_LOCUS (last
);
4705 locus
= &cfun
->function_end_locus
;
4706 warning ("%Hcontrol reaches end of non-void function", locus
);
4714 /* Given a basic block B which ends with a conditional and has
4715 precisely two successors, determine which of the edges is taken if
4716 the conditional is true and which is taken if the conditional is
4717 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
4720 extract_true_false_edges_from_block (basic_block b
,
4726 if (e
->flags
& EDGE_TRUE_VALUE
)
4729 *false_edge
= e
->succ_next
;
4734 *true_edge
= e
->succ_next
;
4738 struct tree_opt_pass pass_warn_function_return
=
4742 execute_warn_function_return
, /* execute */
4745 0, /* static_pass_number */
4747 PROP_ssa
, /* properties_required */
4748 0, /* properties_provided */
4749 0, /* properties_destroyed */
4750 0, /* todo_flags_start */
4751 0 /* todo_flags_finish */
4754 #include "gt-tree-cfg.h"