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 bool cleanup_control_flow (void);
103 static bool cleanup_control_expr_graph (basic_block
, block_stmt_iterator
);
104 static edge
find_taken_edge_cond_expr (basic_block
, tree
);
105 static edge
find_taken_edge_switch_expr (basic_block
, tree
);
106 static tree
find_case_label_for_value (tree
, tree
);
107 static bool phi_alternatives_equal (basic_block
, edge
, edge
);
110 /*---------------------------------------------------------------------------
112 ---------------------------------------------------------------------------*/
114 /* Entry point to the CFG builder for trees. TP points to the list of
115 statements to be added to the flowgraph. */
118 build_tree_cfg (tree
*tp
)
120 /* Register specific tree functions. */
121 tree_register_cfg_hooks ();
123 /* Initialize rbi_pool. */
126 /* Initialize the basic block array. */
128 profile_status
= PROFILE_ABSENT
;
130 last_basic_block
= 0;
131 VARRAY_BB_INIT (basic_block_info
, initial_cfg_capacity
, "basic_block_info");
132 memset ((void *) &cfg_stats
, 0, sizeof (cfg_stats
));
134 /* Build a mapping of labels to their associated blocks. */
135 VARRAY_BB_INIT (label_to_block_map
, initial_cfg_capacity
,
136 "label to block map");
138 ENTRY_BLOCK_PTR
->next_bb
= EXIT_BLOCK_PTR
;
139 EXIT_BLOCK_PTR
->prev_bb
= ENTRY_BLOCK_PTR
;
141 found_computed_goto
= 0;
144 /* Computed gotos are hell to deal with, especially if there are
145 lots of them with a large number of destinations. So we factor
146 them to a common computed goto location before we build the
147 edge list. After we convert back to normal form, we will un-factor
148 the computed gotos since factoring introduces an unwanted jump. */
149 if (found_computed_goto
)
150 factor_computed_gotos ();
152 /* Make sure there is always at least one block, even if its empty. */
153 if (n_basic_blocks
== 0)
154 create_empty_bb (ENTRY_BLOCK_PTR
);
156 create_block_annotation (ENTRY_BLOCK_PTR
);
157 create_block_annotation (EXIT_BLOCK_PTR
);
159 /* Adjust the size of the array. */
160 VARRAY_GROW (basic_block_info
, n_basic_blocks
);
162 /* To speed up statement iterator walks, we first purge dead labels. */
163 cleanup_dead_labels ();
165 /* Group case nodes to reduce the number of edges.
166 We do this after cleaning up dead labels because otherwise we miss
167 a lot of obvious case merging opportunities. */
168 group_case_labels ();
170 /* Create the edges of the flowgraph. */
173 /* Debugging dumps. */
175 /* Write the flowgraph to a VCG file. */
177 int local_dump_flags
;
178 FILE *dump_file
= dump_begin (TDI_vcg
, &local_dump_flags
);
181 tree_cfg2vcg (dump_file
);
182 dump_end (TDI_vcg
, dump_file
);
186 /* Dump a textual representation of the flowgraph. */
188 dump_tree_cfg (dump_file
, dump_flags
);
192 execute_build_cfg (void)
194 build_tree_cfg (&DECL_SAVED_TREE (current_function_decl
));
197 struct tree_opt_pass pass_build_cfg
=
201 execute_build_cfg
, /* execute */
204 0, /* static_pass_number */
205 TV_TREE_CFG
, /* tv_id */
206 PROP_gimple_leh
, /* properties_required */
207 PROP_cfg
, /* properties_provided */
208 0, /* properties_destroyed */
209 0, /* todo_flags_start */
210 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_exit_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
);
465 #if defined ENABLE_CHECKING
466 if (last
== NULL_TREE
)
470 switch (TREE_CODE (last
))
473 make_goto_expr_edges (bb
);
477 make_edge (bb
, EXIT_BLOCK_PTR
, 0);
481 make_cond_expr_edges (bb
);
485 make_switch_expr_edges (bb
);
489 make_eh_edges (last
);
490 /* Yet another NORETURN hack. */
491 if (bb
->succ
== NULL
)
492 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
501 /* Create exit edges for statements in block BB that alter the flow of
502 control. Statements that alter the control flow are 'goto', 'return'
503 and calls to non-returning functions. */
506 make_exit_edges (basic_block bb
)
508 tree last
= last_stmt (bb
), op
;
510 if (last
== NULL_TREE
)
513 switch (TREE_CODE (last
))
516 /* If this function receives a nonlocal goto, then we need to
517 make edges from this call site to all the nonlocal goto
519 if (TREE_SIDE_EFFECTS (last
)
520 && current_function_has_nonlocal_label
)
521 make_goto_expr_edges (bb
);
523 /* If this statement has reachable exception handlers, then
524 create abnormal edges to them. */
525 make_eh_edges (last
);
527 /* Some calls are known not to return. For such calls we create
530 We really need to revamp how we build edges so that it's not
531 such a bloody pain to avoid creating edges for this case since
532 all we do is remove these edges when we're done building the
534 if (call_expr_flags (last
) & (ECF_NORETURN
| ECF_LONGJMP
))
536 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
540 /* Don't forget the fall-thru edge. */
541 make_edge (bb
, bb
->next_bb
, EDGE_FALLTHRU
);
545 /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the CALL_EXPR
546 may have an abnormal edge. Search the RHS for this case and
547 create any required edges. */
548 op
= get_call_expr_in (last
);
549 if (op
&& TREE_SIDE_EFFECTS (op
)
550 && current_function_has_nonlocal_label
)
551 make_goto_expr_edges (bb
);
553 make_eh_edges (last
);
554 make_edge (bb
, bb
->next_bb
, EDGE_FALLTHRU
);
563 /* Create the edges for a COND_EXPR starting at block BB.
564 At this point, both clauses must contain only simple gotos. */
567 make_cond_expr_edges (basic_block bb
)
569 tree entry
= last_stmt (bb
);
570 basic_block then_bb
, else_bb
;
571 tree then_label
, else_label
;
573 #if defined ENABLE_CHECKING
574 if (entry
== NULL_TREE
|| TREE_CODE (entry
) != COND_EXPR
)
578 /* Entry basic blocks for each component. */
579 then_label
= GOTO_DESTINATION (COND_EXPR_THEN (entry
));
580 else_label
= GOTO_DESTINATION (COND_EXPR_ELSE (entry
));
581 then_bb
= label_to_block (then_label
);
582 else_bb
= label_to_block (else_label
);
584 make_edge (bb
, then_bb
, EDGE_TRUE_VALUE
);
585 make_edge (bb
, else_bb
, EDGE_FALSE_VALUE
);
589 /* Create the edges for a SWITCH_EXPR starting at block BB.
590 At this point, the switch body has been lowered and the
591 SWITCH_LABELS filled in, so this is in effect a multi-way branch. */
594 make_switch_expr_edges (basic_block bb
)
596 tree entry
= last_stmt (bb
);
600 vec
= SWITCH_LABELS (entry
);
601 n
= TREE_VEC_LENGTH (vec
);
603 for (i
= 0; i
< n
; ++i
)
605 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
606 basic_block label_bb
= label_to_block (lab
);
607 make_edge (bb
, label_bb
, 0);
612 /* Return the basic block holding label DEST. */
615 label_to_block (tree dest
)
617 int uid
= LABEL_DECL_UID (dest
);
619 /* We would die hard when faced by undefined label. Emit label to
620 very first basic block. This will hopefully make even the dataflow
621 and undefined variable warnings quite right. */
622 if ((errorcount
|| sorrycount
) && uid
< 0)
624 block_stmt_iterator bsi
= bsi_start (BASIC_BLOCK (0));
627 stmt
= build1 (LABEL_EXPR
, void_type_node
, dest
);
628 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
629 uid
= LABEL_DECL_UID (dest
);
631 return VARRAY_BB (label_to_block_map
, uid
);
635 /* Create edges for a goto statement at block BB. */
638 make_goto_expr_edges (basic_block bb
)
641 basic_block target_bb
;
643 block_stmt_iterator last
= bsi_last (bb
);
645 goto_t
= bsi_stmt (last
);
647 /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
648 CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
649 from a nonlocal goto. */
650 if (TREE_CODE (goto_t
) != GOTO_EXPR
)
652 dest
= error_mark_node
;
657 dest
= GOTO_DESTINATION (goto_t
);
660 /* A GOTO to a local label creates normal edges. */
661 if (simple_goto_p (goto_t
))
663 edge e
= make_edge (bb
, label_to_block (dest
), EDGE_FALLTHRU
);
664 #ifdef USE_MAPPED_LOCATION
665 e
->goto_locus
= EXPR_LOCATION (goto_t
);
667 e
->goto_locus
= EXPR_LOCUS (goto_t
);
673 /* Nothing more to do for nonlocal gotos. */
674 if (TREE_CODE (dest
) == LABEL_DECL
)
677 /* Computed gotos remain. */
680 /* Look for the block starting with the destination label. In the
681 case of a computed goto, make an edge to any label block we find
683 FOR_EACH_BB (target_bb
)
685 block_stmt_iterator bsi
;
687 for (bsi
= bsi_start (target_bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
689 tree target
= bsi_stmt (bsi
);
691 if (TREE_CODE (target
) != LABEL_EXPR
)
695 /* Computed GOTOs. Make an edge to every label block that has
696 been marked as a potential target for a computed goto. */
697 (FORCED_LABEL (LABEL_EXPR_LABEL (target
)) && for_call
== 0)
698 /* Nonlocal GOTO target. Make an edge to every label block
699 that has been marked as a potential target for a nonlocal
701 || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target
)) && for_call
== 1))
703 make_edge (bb
, target_bb
, EDGE_ABNORMAL
);
709 /* Degenerate case of computed goto with no labels. */
710 if (!for_call
&& !bb
->succ
)
711 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
715 /*---------------------------------------------------------------------------
717 ---------------------------------------------------------------------------*/
719 /* Remove unreachable blocks and other miscellaneous clean up work. */
722 cleanup_tree_cfg (void)
724 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
|= delete_unreachable_blocks ();
735 something_changed
|= thread_jumps ();
736 retval
|= something_changed
;
739 /* Merging the blocks creates no new opportunities for the other
740 optimizations, so do it here. */
745 #ifdef ENABLE_CHECKING
748 timevar_pop (TV_TREE_CLEANUP_CFG
);
753 /* Cleanup useless labels in basic blocks. This is something we wish
754 to do early because it allows us to group case labels before creating
755 the edges for the CFG, and it speeds up block statement iterators in
757 We only run this pass once, running it more than once is probably not
760 /* A map from basic block index to the leading label of that block. */
761 static tree
*label_for_bb
;
763 /* Callback for for_each_eh_region. Helper for cleanup_dead_labels. */
765 update_eh_label (struct eh_region
*region
)
767 tree old_label
= get_eh_region_tree_label (region
);
771 basic_block bb
= label_to_block (old_label
);
773 /* ??? After optimizing, there may be EH regions with labels
774 that have already been removed from the function body, so
775 there is no basic block for them. */
779 new_label
= label_for_bb
[bb
->index
];
780 set_eh_region_tree_label (region
, new_label
);
784 /* Given LABEL return the first label in the same basic block. */
786 main_block_label (tree label
)
788 basic_block bb
= label_to_block (label
);
790 /* label_to_block possibly inserted undefined label into the chain. */
791 if (!label_for_bb
[bb
->index
])
792 label_for_bb
[bb
->index
] = label
;
793 return label_for_bb
[bb
->index
];
796 /* Cleanup redundant labels. This is a three-steo process:
797 1) Find the leading label for each block.
798 2) Redirect all references to labels to the leading labels.
799 3) Cleanup all useless labels. */
802 cleanup_dead_labels (void)
805 label_for_bb
= xcalloc (last_basic_block
, sizeof (tree
));
807 /* Find a suitable label for each block. We use the first user-defined
808 label is there is one, or otherwise just the first label we see. */
811 block_stmt_iterator i
;
813 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_next (&i
))
815 tree label
, stmt
= bsi_stmt (i
);
817 if (TREE_CODE (stmt
) != LABEL_EXPR
)
820 label
= LABEL_EXPR_LABEL (stmt
);
822 /* If we have not yet seen a label for the current block,
823 remember this one and see if there are more labels. */
824 if (! label_for_bb
[bb
->index
])
826 label_for_bb
[bb
->index
] = label
;
830 /* If we did see a label for the current block already, but it
831 is an artificially created label, replace it if the current
832 label is a user defined label. */
833 if (! DECL_ARTIFICIAL (label
)
834 && DECL_ARTIFICIAL (label_for_bb
[bb
->index
]))
836 label_for_bb
[bb
->index
] = label
;
842 /* Now redirect all jumps/branches to the selected label.
843 First do so for each block ending in a control statement. */
846 tree stmt
= last_stmt (bb
);
850 switch (TREE_CODE (stmt
))
854 tree true_branch
, false_branch
;
856 true_branch
= COND_EXPR_THEN (stmt
);
857 false_branch
= COND_EXPR_ELSE (stmt
);
859 GOTO_DESTINATION (true_branch
)
860 = main_block_label (GOTO_DESTINATION (true_branch
));
861 GOTO_DESTINATION (false_branch
)
862 = main_block_label (GOTO_DESTINATION (false_branch
));
870 tree vec
= SWITCH_LABELS (stmt
);
871 size_t n
= TREE_VEC_LENGTH (vec
);
873 /* Replace all destination labels. */
874 for (i
= 0; i
< n
; ++i
)
875 CASE_LABEL (TREE_VEC_ELT (vec
, i
))
876 = main_block_label (CASE_LABEL (TREE_VEC_ELT (vec
, i
)));
881 /* We have to handle GOTO_EXPRs until they're removed, and we don't
882 remove them until after we've created the CFG edges. */
884 if (! computed_goto_p (stmt
))
886 GOTO_DESTINATION (stmt
)
887 = main_block_label (GOTO_DESTINATION (stmt
));
896 for_each_eh_region (update_eh_label
);
898 /* Finally, purge dead labels. All user-defined labels and labels that
899 can be the target of non-local gotos are preserved. */
902 block_stmt_iterator i
;
903 tree label_for_this_bb
= label_for_bb
[bb
->index
];
905 if (! label_for_this_bb
)
908 for (i
= bsi_start (bb
); !bsi_end_p (i
); )
910 tree label
, stmt
= bsi_stmt (i
);
912 if (TREE_CODE (stmt
) != LABEL_EXPR
)
915 label
= LABEL_EXPR_LABEL (stmt
);
917 if (label
== label_for_this_bb
918 || ! DECL_ARTIFICIAL (label
)
919 || DECL_NONLOCAL (label
))
929 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
930 and scan the sorted vector of cases. Combine the ones jumping to the
932 Eg. three separate entries 1: 2: 3: become one entry 1..3: */
935 group_case_labels (void)
941 tree stmt
= last_stmt (bb
);
942 if (stmt
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
944 tree labels
= SWITCH_LABELS (stmt
);
945 int old_size
= TREE_VEC_LENGTH (labels
);
946 int i
, j
, new_size
= old_size
;
947 tree default_label
= TREE_VEC_ELT (labels
, old_size
- 1);
949 /* Look for possible opportunities to merge cases.
950 Ignore the last element of the label vector because it
951 must be the default case. */
953 while (i
< old_size
- 2)
955 tree base_case
, base_label
, base_high
, type
;
956 base_case
= TREE_VEC_ELT (labels
, i
);
961 base_label
= CASE_LABEL (base_case
);
963 /* Discard cases that have the same destination as the
965 if (base_label
== default_label
)
967 TREE_VEC_ELT (labels
, i
) = NULL_TREE
;
972 type
= TREE_TYPE (CASE_LOW (base_case
));
973 base_high
= CASE_HIGH (base_case
) ?
974 CASE_HIGH (base_case
) : CASE_LOW (base_case
);
976 /* Try to merge case labels. Break out when we reach the end
977 of the label vector or when we cannot merge the next case
978 label with the current one. */
979 while (i
< old_size
- 2)
981 tree merge_case
= TREE_VEC_ELT (labels
, ++i
);
982 tree merge_label
= CASE_LABEL (merge_case
);
983 tree t
= int_const_binop (PLUS_EXPR
, base_high
,
984 integer_one_node
, 1);
986 /* Merge the cases if they jump to the same place,
987 and their ranges are consecutive. */
988 if (merge_label
== base_label
989 && tree_int_cst_equal (CASE_LOW (merge_case
), t
))
991 base_high
= CASE_HIGH (merge_case
) ?
992 CASE_HIGH (merge_case
) : CASE_LOW (merge_case
);
993 CASE_HIGH (base_case
) = base_high
;
994 TREE_VEC_ELT (labels
, i
) = NULL_TREE
;
1002 /* Compress the case labels in the label vector, and adjust the
1003 length of the vector. */
1004 for (i
= 0, j
= 0; i
< new_size
; i
++)
1006 while (! TREE_VEC_ELT (labels
, j
))
1008 TREE_VEC_ELT (labels
, i
) = TREE_VEC_ELT (labels
, j
++);
1010 TREE_VEC_LENGTH (labels
) = new_size
;
1015 /* Checks whether we can merge block B into block A. */
1018 tree_can_merge_blocks_p (basic_block a
, basic_block b
)
1021 block_stmt_iterator bsi
;
1024 || a
->succ
->succ_next
)
1027 if (a
->succ
->flags
& EDGE_ABNORMAL
)
1030 if (a
->succ
->dest
!= b
)
1033 if (b
== EXIT_BLOCK_PTR
)
1036 if (b
->pred
->pred_next
)
1039 /* If A ends by a statement causing exceptions or something similar, we
1040 cannot merge the blocks. */
1041 stmt
= last_stmt (a
);
1042 if (stmt
&& stmt_ends_bb_p (stmt
))
1045 /* Do not allow a block with only a non-local label to be merged. */
1046 if (stmt
&& TREE_CODE (stmt
) == LABEL_EXPR
1047 && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt
)))
1050 /* There may be no phi nodes at the start of b. Most of these degenerate
1051 phi nodes should be cleaned up by kill_redundant_phi_nodes. */
1055 /* Do not remove user labels. */
1056 for (bsi
= bsi_start (b
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1058 stmt
= bsi_stmt (bsi
);
1059 if (TREE_CODE (stmt
) != LABEL_EXPR
)
1061 if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt
)))
1069 /* Merge block B into block A. */
1072 tree_merge_blocks (basic_block a
, basic_block b
)
1074 block_stmt_iterator bsi
;
1075 tree_stmt_iterator last
;
1078 fprintf (dump_file
, "Merging blocks %d and %d\n", a
->index
, b
->index
);
1080 /* Ensure that B follows A. */
1081 move_block_after (b
, a
);
1083 if (!(a
->succ
->flags
& EDGE_FALLTHRU
))
1087 && stmt_ends_bb_p (last_stmt (a
)))
1090 /* Remove labels from B and set bb_for_stmt to A for other statements. */
1091 for (bsi
= bsi_start (b
); !bsi_end_p (bsi
);)
1093 if (TREE_CODE (bsi_stmt (bsi
)) == LABEL_EXPR
)
1097 set_bb_for_stmt (bsi_stmt (bsi
), a
);
1102 /* Merge the chains. */
1103 last
= tsi_last (a
->stmt_list
);
1104 tsi_link_after (&last
, b
->stmt_list
, TSI_NEW_STMT
);
1105 b
->stmt_list
= NULL
;
1109 /* Walk the function tree removing unnecessary statements.
1111 * Empty statement nodes are removed
1113 * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1115 * Unnecessary COND_EXPRs are removed
1117 * Some unnecessary BIND_EXPRs are removed
1119 Clearly more work could be done. The trick is doing the analysis
1120 and removal fast enough to be a net improvement in compile times.
1122 Note that when we remove a control structure such as a COND_EXPR
1123 BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1124 to ensure we eliminate all the useless code. */
1135 static void remove_useless_stmts_1 (tree
*, struct rus_data
*);
1138 remove_useless_stmts_warn_notreached (tree stmt
)
1140 if (EXPR_HAS_LOCATION (stmt
))
1142 location_t loc
= EXPR_LOCATION (stmt
);
1143 warning ("%Hwill never be executed", &loc
);
1147 switch (TREE_CODE (stmt
))
1149 case STATEMENT_LIST
:
1151 tree_stmt_iterator i
;
1152 for (i
= tsi_start (stmt
); !tsi_end_p (i
); tsi_next (&i
))
1153 if (remove_useless_stmts_warn_notreached (tsi_stmt (i
)))
1159 if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt
)))
1161 if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt
)))
1163 if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt
)))
1167 case TRY_FINALLY_EXPR
:
1168 case TRY_CATCH_EXPR
:
1169 if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt
, 0)))
1171 if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt
, 1)))
1176 return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt
));
1177 case EH_FILTER_EXPR
:
1178 return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt
));
1180 return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt
));
1183 /* Not a live container. */
1191 remove_useless_stmts_cond (tree
*stmt_p
, struct rus_data
*data
)
1193 tree then_clause
, else_clause
, cond
;
1194 bool save_has_label
, then_has_label
, else_has_label
;
1196 save_has_label
= data
->has_label
;
1197 data
->has_label
= false;
1198 data
->last_goto
= NULL
;
1200 remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p
), data
);
1202 then_has_label
= data
->has_label
;
1203 data
->has_label
= false;
1204 data
->last_goto
= NULL
;
1206 remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p
), data
);
1208 else_has_label
= data
->has_label
;
1209 data
->has_label
= save_has_label
| then_has_label
| else_has_label
;
1212 then_clause
= COND_EXPR_THEN (*stmt_p
);
1213 else_clause
= COND_EXPR_ELSE (*stmt_p
);
1214 cond
= COND_EXPR_COND (*stmt_p
);
1216 /* If neither arm does anything at all, we can remove the whole IF. */
1217 if (!TREE_SIDE_EFFECTS (then_clause
) && !TREE_SIDE_EFFECTS (else_clause
))
1219 *stmt_p
= build_empty_stmt ();
1220 data
->repeat
= true;
1223 /* If there are no reachable statements in an arm, then we can
1224 zap the entire conditional. */
1225 else if (integer_nonzerop (cond
) && !else_has_label
)
1227 if (warn_notreached
)
1228 remove_useless_stmts_warn_notreached (else_clause
);
1229 *stmt_p
= then_clause
;
1230 data
->repeat
= true;
1232 else if (integer_zerop (cond
) && !then_has_label
)
1234 if (warn_notreached
)
1235 remove_useless_stmts_warn_notreached (then_clause
);
1236 *stmt_p
= else_clause
;
1237 data
->repeat
= true;
1240 /* Check a couple of simple things on then/else with single stmts. */
1243 tree then_stmt
= expr_only (then_clause
);
1244 tree else_stmt
= expr_only (else_clause
);
1246 /* Notice branches to a common destination. */
1247 if (then_stmt
&& else_stmt
1248 && TREE_CODE (then_stmt
) == GOTO_EXPR
1249 && TREE_CODE (else_stmt
) == GOTO_EXPR
1250 && (GOTO_DESTINATION (then_stmt
) == GOTO_DESTINATION (else_stmt
)))
1252 *stmt_p
= then_stmt
;
1253 data
->repeat
= true;
1256 /* If the THEN/ELSE clause merely assigns a value to a variable or
1257 parameter which is already known to contain that value, then
1258 remove the useless THEN/ELSE clause. */
1259 else if (TREE_CODE (cond
) == VAR_DECL
|| TREE_CODE (cond
) == PARM_DECL
)
1262 && TREE_CODE (else_stmt
) == MODIFY_EXPR
1263 && TREE_OPERAND (else_stmt
, 0) == cond
1264 && integer_zerop (TREE_OPERAND (else_stmt
, 1)))
1265 COND_EXPR_ELSE (*stmt_p
) = alloc_stmt_list ();
1267 else if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
1268 && (TREE_CODE (TREE_OPERAND (cond
, 0)) == VAR_DECL
1269 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PARM_DECL
)
1270 && TREE_CONSTANT (TREE_OPERAND (cond
, 1)))
1272 tree stmt
= (TREE_CODE (cond
) == EQ_EXPR
1273 ? then_stmt
: else_stmt
);
1274 tree
*location
= (TREE_CODE (cond
) == EQ_EXPR
1275 ? &COND_EXPR_THEN (*stmt_p
)
1276 : &COND_EXPR_ELSE (*stmt_p
));
1279 && TREE_CODE (stmt
) == MODIFY_EXPR
1280 && TREE_OPERAND (stmt
, 0) == TREE_OPERAND (cond
, 0)
1281 && TREE_OPERAND (stmt
, 1) == TREE_OPERAND (cond
, 1))
1282 *location
= alloc_stmt_list ();
1286 /* Protect GOTOs in the arm of COND_EXPRs from being removed. They
1287 would be re-introduced during lowering. */
1288 data
->last_goto
= NULL
;
1293 remove_useless_stmts_tf (tree
*stmt_p
, struct rus_data
*data
)
1295 bool save_may_branch
, save_may_throw
;
1296 bool this_may_branch
, this_may_throw
;
1298 /* Collect may_branch and may_throw information for the body only. */
1299 save_may_branch
= data
->may_branch
;
1300 save_may_throw
= data
->may_throw
;
1301 data
->may_branch
= false;
1302 data
->may_throw
= false;
1303 data
->last_goto
= NULL
;
1305 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 0), data
);
1307 this_may_branch
= data
->may_branch
;
1308 this_may_throw
= data
->may_throw
;
1309 data
->may_branch
|= save_may_branch
;
1310 data
->may_throw
|= save_may_throw
;
1311 data
->last_goto
= NULL
;
1313 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 1), data
);
1315 /* If the body is empty, then we can emit the FINALLY block without
1316 the enclosing TRY_FINALLY_EXPR. */
1317 if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p
, 0)))
1319 *stmt_p
= TREE_OPERAND (*stmt_p
, 1);
1320 data
->repeat
= true;
1323 /* If the handler is empty, then we can emit the TRY block without
1324 the enclosing TRY_FINALLY_EXPR. */
1325 else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p
, 1)))
1327 *stmt_p
= TREE_OPERAND (*stmt_p
, 0);
1328 data
->repeat
= true;
1331 /* If the body neither throws, nor branches, then we can safely
1332 string the TRY and FINALLY blocks together. */
1333 else if (!this_may_branch
&& !this_may_throw
)
1335 tree stmt
= *stmt_p
;
1336 *stmt_p
= TREE_OPERAND (stmt
, 0);
1337 append_to_statement_list (TREE_OPERAND (stmt
, 1), stmt_p
);
1338 data
->repeat
= true;
1344 remove_useless_stmts_tc (tree
*stmt_p
, struct rus_data
*data
)
1346 bool save_may_throw
, this_may_throw
;
1347 tree_stmt_iterator i
;
1350 /* Collect may_throw information for the body only. */
1351 save_may_throw
= data
->may_throw
;
1352 data
->may_throw
= false;
1353 data
->last_goto
= NULL
;
1355 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 0), data
);
1357 this_may_throw
= data
->may_throw
;
1358 data
->may_throw
= save_may_throw
;
1360 /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR. */
1361 if (!this_may_throw
)
1363 if (warn_notreached
)
1364 remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p
, 1));
1365 *stmt_p
= TREE_OPERAND (*stmt_p
, 0);
1366 data
->repeat
= true;
1370 /* Process the catch clause specially. We may be able to tell that
1371 no exceptions propagate past this point. */
1373 this_may_throw
= true;
1374 i
= tsi_start (TREE_OPERAND (*stmt_p
, 1));
1375 stmt
= tsi_stmt (i
);
1376 data
->last_goto
= NULL
;
1378 switch (TREE_CODE (stmt
))
1381 for (; !tsi_end_p (i
); tsi_next (&i
))
1383 stmt
= tsi_stmt (i
);
1384 /* If we catch all exceptions, then the body does not
1385 propagate exceptions past this point. */
1386 if (CATCH_TYPES (stmt
) == NULL
)
1387 this_may_throw
= false;
1388 data
->last_goto
= NULL
;
1389 remove_useless_stmts_1 (&CATCH_BODY (stmt
), data
);
1393 case EH_FILTER_EXPR
:
1394 if (EH_FILTER_MUST_NOT_THROW (stmt
))
1395 this_may_throw
= false;
1396 else if (EH_FILTER_TYPES (stmt
) == NULL
)
1397 this_may_throw
= false;
1398 remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt
), data
);
1402 /* Otherwise this is a cleanup. */
1403 remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p
, 1), data
);
1405 /* If the cleanup is empty, then we can emit the TRY block without
1406 the enclosing TRY_CATCH_EXPR. */
1407 if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p
, 1)))
1409 *stmt_p
= TREE_OPERAND (*stmt_p
, 0);
1410 data
->repeat
= true;
1414 data
->may_throw
|= this_may_throw
;
1419 remove_useless_stmts_bind (tree
*stmt_p
, struct rus_data
*data
)
1423 /* First remove anything underneath the BIND_EXPR. */
1424 remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p
), data
);
1426 /* If the BIND_EXPR has no variables, then we can pull everything
1427 up one level and remove the BIND_EXPR, unless this is the toplevel
1428 BIND_EXPR for the current function or an inlined function.
1430 When this situation occurs we will want to apply this
1431 optimization again. */
1432 block
= BIND_EXPR_BLOCK (*stmt_p
);
1433 if (BIND_EXPR_VARS (*stmt_p
) == NULL_TREE
1434 && *stmt_p
!= DECL_SAVED_TREE (current_function_decl
)
1436 || ! BLOCK_ABSTRACT_ORIGIN (block
)
1437 || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block
))
1440 *stmt_p
= BIND_EXPR_BODY (*stmt_p
);
1441 data
->repeat
= true;
1447 remove_useless_stmts_goto (tree
*stmt_p
, struct rus_data
*data
)
1449 tree dest
= GOTO_DESTINATION (*stmt_p
);
1451 data
->may_branch
= true;
1452 data
->last_goto
= NULL
;
1454 /* Record the last goto expr, so that we can delete it if unnecessary. */
1455 if (TREE_CODE (dest
) == LABEL_DECL
)
1456 data
->last_goto
= stmt_p
;
1461 remove_useless_stmts_label (tree
*stmt_p
, struct rus_data
*data
)
1463 tree label
= LABEL_EXPR_LABEL (*stmt_p
);
1465 data
->has_label
= true;
1467 /* We do want to jump across non-local label receiver code. */
1468 if (DECL_NONLOCAL (label
))
1469 data
->last_goto
= NULL
;
1471 else if (data
->last_goto
&& GOTO_DESTINATION (*data
->last_goto
) == label
)
1473 *data
->last_goto
= build_empty_stmt ();
1474 data
->repeat
= true;
1477 /* ??? Add something here to delete unused labels. */
1481 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1482 decl. This allows us to eliminate redundant or useless
1483 calls to "const" functions.
1485 Gimplifier already does the same operation, but we may notice functions
1486 being const and pure once their calls has been gimplified, so we need
1487 to update the flag. */
1490 update_call_expr_flags (tree call
)
1492 tree decl
= get_callee_fndecl (call
);
1495 if (call_expr_flags (call
) & (ECF_CONST
| ECF_PURE
))
1496 TREE_SIDE_EFFECTS (call
) = 0;
1497 if (TREE_NOTHROW (decl
))
1498 TREE_NOTHROW (call
) = 1;
1502 /* T is CALL_EXPR. Set current_function_calls_* flags. */
1505 notice_special_calls (tree t
)
1507 int flags
= call_expr_flags (t
);
1509 if (flags
& ECF_MAY_BE_ALLOCA
)
1510 current_function_calls_alloca
= true;
1511 if (flags
& ECF_RETURNS_TWICE
)
1512 current_function_calls_setjmp
= true;
1516 /* Clear flags set by notice_special_calls. Used by dead code removal
1517 to update the flags. */
1520 clear_special_calls (void)
1522 current_function_calls_alloca
= false;
1523 current_function_calls_setjmp
= false;
1528 remove_useless_stmts_1 (tree
*tp
, struct rus_data
*data
)
1532 switch (TREE_CODE (t
))
1535 remove_useless_stmts_cond (tp
, data
);
1538 case TRY_FINALLY_EXPR
:
1539 remove_useless_stmts_tf (tp
, data
);
1542 case TRY_CATCH_EXPR
:
1543 remove_useless_stmts_tc (tp
, data
);
1547 remove_useless_stmts_bind (tp
, data
);
1551 remove_useless_stmts_goto (tp
, data
);
1555 remove_useless_stmts_label (tp
, data
);
1560 data
->last_goto
= NULL
;
1561 data
->may_branch
= true;
1566 data
->last_goto
= NULL
;
1567 notice_special_calls (t
);
1568 update_call_expr_flags (t
);
1569 if (tree_could_throw_p (t
))
1570 data
->may_throw
= true;
1574 data
->last_goto
= NULL
;
1576 op
= get_call_expr_in (t
);
1579 update_call_expr_flags (op
);
1580 notice_special_calls (op
);
1582 if (tree_could_throw_p (t
))
1583 data
->may_throw
= true;
1586 case STATEMENT_LIST
:
1588 tree_stmt_iterator i
= tsi_start (t
);
1589 while (!tsi_end_p (i
))
1592 if (IS_EMPTY_STMT (t
))
1598 remove_useless_stmts_1 (tsi_stmt_ptr (i
), data
);
1601 if (TREE_CODE (t
) == STATEMENT_LIST
)
1603 tsi_link_before (&i
, t
, TSI_SAME_STMT
);
1613 data
->last_goto
= NULL
;
1617 data
->last_goto
= NULL
;
1623 remove_useless_stmts (void)
1625 struct rus_data data
;
1627 clear_special_calls ();
1631 memset (&data
, 0, sizeof (data
));
1632 remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl
), &data
);
1634 while (data
.repeat
);
1638 struct tree_opt_pass pass_remove_useless_stmts
=
1640 "useless", /* name */
1642 remove_useless_stmts
, /* execute */
1645 0, /* static_pass_number */
1647 PROP_gimple_any
, /* properties_required */
1648 0, /* properties_provided */
1649 0, /* properties_destroyed */
1650 0, /* todo_flags_start */
1651 TODO_dump_func
, /* todo_flags_finish */
1656 /* Remove obviously useless statements in basic block BB. */
1659 cfg_remove_useless_stmts_bb (basic_block bb
)
1661 block_stmt_iterator bsi
;
1662 tree stmt
= NULL_TREE
;
1663 tree cond
, var
= NULL_TREE
, val
= NULL_TREE
;
1664 struct var_ann_d
*ann
;
1666 /* Check whether we come here from a condition, and if so, get the
1669 || bb
->pred
->pred_next
1670 || !(bb
->pred
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1673 cond
= COND_EXPR_COND (last_stmt (bb
->pred
->src
));
1675 if (TREE_CODE (cond
) == VAR_DECL
|| TREE_CODE (cond
) == PARM_DECL
)
1678 val
= (bb
->pred
->flags
& EDGE_FALSE_VALUE
1679 ? boolean_false_node
: boolean_true_node
);
1681 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
1682 && (TREE_CODE (TREE_OPERAND (cond
, 0)) == VAR_DECL
1683 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PARM_DECL
))
1685 var
= TREE_OPERAND (cond
, 0);
1686 val
= (bb
->pred
->flags
& EDGE_FALSE_VALUE
1687 ? boolean_true_node
: boolean_false_node
);
1691 if (bb
->pred
->flags
& EDGE_FALSE_VALUE
)
1692 cond
= invert_truthvalue (cond
);
1693 if (TREE_CODE (cond
) == EQ_EXPR
1694 && (TREE_CODE (TREE_OPERAND (cond
, 0)) == VAR_DECL
1695 || TREE_CODE (TREE_OPERAND (cond
, 0)) == PARM_DECL
)
1696 && (TREE_CODE (TREE_OPERAND (cond
, 1)) == VAR_DECL
1697 || TREE_CODE (TREE_OPERAND (cond
, 1)) == PARM_DECL
1698 || TREE_CONSTANT (TREE_OPERAND (cond
, 1))))
1700 var
= TREE_OPERAND (cond
, 0);
1701 val
= TREE_OPERAND (cond
, 1);
1707 /* Only work for normal local variables. */
1708 ann
= var_ann (var
);
1711 || TREE_ADDRESSABLE (var
))
1714 if (! TREE_CONSTANT (val
))
1716 ann
= var_ann (val
);
1719 || TREE_ADDRESSABLE (val
))
1723 /* Ignore floating point variables, since comparison behaves weird for
1725 if (FLOAT_TYPE_P (TREE_TYPE (var
)))
1728 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
);)
1730 stmt
= bsi_stmt (bsi
);
1732 /* If the THEN/ELSE clause merely assigns a value to a variable/parameter
1733 which is already known to contain that value, then remove the useless
1734 THEN/ELSE clause. */
1735 if (TREE_CODE (stmt
) == MODIFY_EXPR
1736 && TREE_OPERAND (stmt
, 0) == var
1737 && operand_equal_p (val
, TREE_OPERAND (stmt
, 1), 0))
1743 /* Invalidate the var if we encounter something that could modify it.
1744 Likewise for the value it was previously set to. Note that we only
1745 consider values that are either a VAR_DECL or PARM_DECL so we
1746 can test for conflict very simply. */
1747 if (TREE_CODE (stmt
) == ASM_EXPR
1748 || (TREE_CODE (stmt
) == MODIFY_EXPR
1749 && (TREE_OPERAND (stmt
, 0) == var
1750 || TREE_OPERAND (stmt
, 0) == val
)))
1758 /* A CFG-aware version of remove_useless_stmts. */
1761 cfg_remove_useless_stmts (void)
1765 #ifdef ENABLE_CHECKING
1766 verify_flow_info ();
1771 cfg_remove_useless_stmts_bb (bb
);
1776 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */
1779 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb
)
1783 /* Since this block is no longer reachable, we can just delete all
1784 of its PHI nodes. */
1785 phi
= phi_nodes (bb
);
1788 tree next
= PHI_CHAIN (phi
);
1789 remove_phi_node (phi
, NULL_TREE
, bb
);
1793 /* Remove edges to BB's successors. */
1794 while (bb
->succ
!= NULL
)
1795 ssa_remove_edge (bb
->succ
);
1799 /* Remove statements of basic block BB. */
1802 remove_bb (basic_block bb
)
1804 block_stmt_iterator i
;
1805 source_locus loc
= 0;
1809 fprintf (dump_file
, "Removing basic block %d\n", bb
->index
);
1810 if (dump_flags
& TDF_DETAILS
)
1812 dump_bb (bb
, dump_file
, 0);
1813 fprintf (dump_file
, "\n");
1817 /* Remove all the instructions in the block. */
1818 for (i
= bsi_start (bb
); !bsi_end_p (i
); bsi_remove (&i
))
1820 tree stmt
= bsi_stmt (i
);
1822 set_bb_for_stmt (stmt
, NULL
);
1824 /* Don't warn for removed gotos. Gotos are often removed due to
1825 jump threading, thus resulting in bogus warnings. Not great,
1826 since this way we lose warnings for gotos in the original
1827 program that are indeed unreachable. */
1828 if (TREE_CODE (stmt
) != GOTO_EXPR
&& EXPR_HAS_LOCATION (stmt
) && !loc
)
1829 #ifdef USE_MAPPED_LOCATION
1830 loc
= EXPR_LOCATION (stmt
);
1832 loc
= EXPR_LOCUS (stmt
);
1836 /* If requested, give a warning that the first statement in the
1837 block is unreachable. We walk statements backwards in the
1838 loop above, so the last statement we process is the first statement
1840 if (warn_notreached
&& loc
)
1841 #ifdef USE_MAPPED_LOCATION
1842 warning ("%Hwill never be executed", &loc
);
1844 warning ("%Hwill never be executed", loc
);
1847 remove_phi_nodes_and_edges_for_unreachable_block (bb
);
1851 /* Examine BB to determine if it is a forwarding block (a block which only
1852 transfers control to a new destination). If BB is a forwarding block,
1853 then return the edge leading to the ultimate destination. */
1856 tree_block_forwards_to (basic_block bb
)
1858 block_stmt_iterator bsi
;
1859 bb_ann_t ann
= bb_ann (bb
);
1862 /* If this block is not forwardable, then avoid useless work. */
1863 if (! ann
->forwardable
)
1866 /* Set this block to not be forwardable. This prevents infinite loops since
1867 any block currently under examination is considered non-forwardable. */
1868 ann
->forwardable
= 0;
1870 /* No forwarding is possible if this block is a special block (ENTRY/EXIT),
1871 this block has more than one successor, this block's single successor is
1872 reached via an abnormal edge, this block has phi nodes, or this block's
1873 single successor has phi nodes. */
1874 if (bb
== EXIT_BLOCK_PTR
1875 || bb
== ENTRY_BLOCK_PTR
1877 || bb
->succ
->succ_next
1878 || bb
->succ
->dest
== EXIT_BLOCK_PTR
1879 || (bb
->succ
->flags
& EDGE_ABNORMAL
) != 0
1881 || phi_nodes (bb
->succ
->dest
))
1884 /* Walk past any labels at the start of this block. */
1885 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1887 stmt
= bsi_stmt (bsi
);
1888 if (TREE_CODE (stmt
) != LABEL_EXPR
)
1892 /* If we reached the end of this block we may be able to optimize this
1894 if (bsi_end_p (bsi
))
1898 /* Recursive call to pick up chains of forwarding blocks. */
1899 dest
= tree_block_forwards_to (bb
->succ
->dest
);
1901 /* If none found, we forward to bb->succ at minimum. */
1905 ann
->forwardable
= 1;
1909 /* No forwarding possible. */
1914 /* Try to remove superfluous control structures. */
1917 cleanup_control_flow (void)
1920 block_stmt_iterator bsi
;
1921 bool retval
= false;
1926 bsi
= bsi_last (bb
);
1928 if (bsi_end_p (bsi
))
1931 stmt
= bsi_stmt (bsi
);
1932 if (TREE_CODE (stmt
) == COND_EXPR
1933 || TREE_CODE (stmt
) == SWITCH_EXPR
)
1934 retval
|= cleanup_control_expr_graph (bb
, bsi
);
1940 /* Disconnect an unreachable block in the control expression starting
1944 cleanup_control_expr_graph (basic_block bb
, block_stmt_iterator bsi
)
1947 bool retval
= false;
1948 tree expr
= bsi_stmt (bsi
), val
;
1950 if (bb
->succ
->succ_next
)
1954 switch (TREE_CODE (expr
))
1957 val
= COND_EXPR_COND (expr
);
1961 val
= SWITCH_COND (expr
);
1962 if (TREE_CODE (val
) != INTEGER_CST
)
1970 taken_edge
= find_taken_edge (bb
, val
);
1974 /* Remove all the edges except the one that is always executed. */
1975 for (e
= bb
->succ
; e
; e
= next
)
1977 next
= e
->succ_next
;
1978 if (e
!= taken_edge
)
1980 taken_edge
->probability
+= e
->probability
;
1981 taken_edge
->count
+= e
->count
;
1982 ssa_remove_edge (e
);
1986 if (taken_edge
->probability
> REG_BR_PROB_BASE
)
1987 taken_edge
->probability
= REG_BR_PROB_BASE
;
1990 taken_edge
= bb
->succ
;
1993 taken_edge
->flags
= EDGE_FALLTHRU
;
1995 /* We removed some paths from the cfg. */
1996 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
1997 dom_computed
[CDI_DOMINATORS
] = DOM_CONS_OK
;
2003 /* Given a control block BB and a predicate VAL, return the edge that
2004 will be taken out of the block. If VAL does not match a unique
2005 edge, NULL is returned. */
2008 find_taken_edge (basic_block bb
, tree val
)
2012 stmt
= last_stmt (bb
);
2014 #if defined ENABLE_CHECKING
2015 if (stmt
== NULL_TREE
|| !is_ctrl_stmt (stmt
))
2019 /* If VAL is a predicate of the form N RELOP N, where N is an
2020 SSA_NAME, we can always determine its truth value (except when
2021 doing floating point comparisons that may involve NaNs). */
2023 && TREE_CODE_CLASS (TREE_CODE (val
)) == '<'
2024 && TREE_OPERAND (val
, 0) == TREE_OPERAND (val
, 1)
2025 && TREE_CODE (TREE_OPERAND (val
, 0)) == SSA_NAME
2026 && (TREE_CODE (TREE_TYPE (TREE_OPERAND (val
, 0))) != REAL_TYPE
2027 || !HONOR_NANS (TYPE_MODE (TREE_TYPE (TREE_OPERAND (val
, 0))))))
2029 enum tree_code code
= TREE_CODE (val
);
2031 if (code
== EQ_EXPR
|| code
== LE_EXPR
|| code
== GE_EXPR
)
2032 val
= boolean_true_node
;
2033 else if (code
== LT_EXPR
|| code
== GT_EXPR
|| code
== NE_EXPR
)
2034 val
= boolean_false_node
;
2037 /* If VAL is not a constant, we can't determine which edge might
2039 if (val
== NULL
|| !really_constant_p (val
))
2042 if (TREE_CODE (stmt
) == COND_EXPR
)
2043 return find_taken_edge_cond_expr (bb
, val
);
2045 if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2046 return find_taken_edge_switch_expr (bb
, val
);
2052 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2053 statement, determine which of the two edges will be taken out of the
2054 block. Return NULL if either edge may be taken. */
2057 find_taken_edge_cond_expr (basic_block bb
, tree val
)
2059 edge true_edge
, false_edge
;
2061 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
2063 /* If both edges of the branch lead to the same basic block, it doesn't
2064 matter which edge is taken. */
2065 if (true_edge
->dest
== false_edge
->dest
)
2068 /* Otherwise, try to determine which branch of the if() will be taken.
2069 If VAL is a constant but it can't be reduced to a 0 or a 1, then
2070 we don't really know which edge will be taken at runtime. This
2071 may happen when comparing addresses (e.g., if (&var1 == 4)). */
2072 if (integer_nonzerop (val
))
2074 else if (integer_zerop (val
))
2081 /* Given a constant value VAL and the entry block BB to a SWITCH_EXPR
2082 statement, determine which edge will be taken out of the block. Return
2083 NULL if any edge may be taken. */
2086 find_taken_edge_switch_expr (basic_block bb
, tree val
)
2088 tree switch_expr
, taken_case
;
2089 basic_block dest_bb
;
2092 if (TREE_CODE (val
) != INTEGER_CST
)
2095 switch_expr
= last_stmt (bb
);
2096 taken_case
= find_case_label_for_value (switch_expr
, val
);
2097 dest_bb
= label_to_block (CASE_LABEL (taken_case
));
2099 e
= find_edge (bb
, dest_bb
);
2106 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2107 We can make optimal use here of the fact that the case labels are
2108 sorted: We can do a binary search for a case matching VAL. */
2111 find_case_label_for_value (tree switch_expr
, tree val
)
2113 tree vec
= SWITCH_LABELS (switch_expr
);
2114 size_t low
, high
, n
= TREE_VEC_LENGTH (vec
);
2115 tree default_case
= TREE_VEC_ELT (vec
, n
- 1);
2117 for (low
= -1, high
= n
- 1; high
- low
> 1; )
2119 size_t i
= (high
+ low
) / 2;
2120 tree t
= TREE_VEC_ELT (vec
, i
);
2123 /* Cache the result of comparing CASE_LOW and val. */
2124 cmp
= tree_int_cst_compare (CASE_LOW (t
), val
);
2131 if (CASE_HIGH (t
) == NULL
)
2133 /* A singe-valued case label. */
2139 /* A case range. We can only handle integer ranges. */
2140 if (cmp
<= 0 && tree_int_cst_compare (CASE_HIGH (t
), val
) >= 0)
2145 return default_case
;
2149 /* If all the PHI nodes in DEST have alternatives for E1 and E2 and
2150 those alternatives are equal in each of the PHI nodes, then return
2151 true, else return false. */
2154 phi_alternatives_equal (basic_block dest
, edge e1
, edge e2
)
2156 tree phi
, val1
, val2
;
2159 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
2161 n1
= phi_arg_from_edge (phi
, e1
);
2162 n2
= phi_arg_from_edge (phi
, e2
);
2164 #ifdef ENABLE_CHECKING
2165 if (n1
< 0 || n2
< 0)
2169 val1
= PHI_ARG_DEF (phi
, n1
);
2170 val2
= PHI_ARG_DEF (phi
, n2
);
2172 if (!operand_equal_p (val1
, val2
, 0))
2180 /*---------------------------------------------------------------------------
2182 ---------------------------------------------------------------------------*/
2184 /* Dump tree-specific information of block BB to file OUTF. */
2187 tree_dump_bb (basic_block bb
, FILE *outf
, int indent
)
2189 dump_generic_bb (outf
, bb
, indent
, TDF_VOPS
);
2193 /* Dump a basic block on stderr. */
2196 debug_tree_bb (basic_block bb
)
2198 dump_bb (bb
, stderr
, 0);
2202 /* Dump basic block with index N on stderr. */
2205 debug_tree_bb_n (int n
)
2207 debug_tree_bb (BASIC_BLOCK (n
));
2208 return BASIC_BLOCK (n
);
2212 /* Dump the CFG on stderr.
2214 FLAGS are the same used by the tree dumping functions
2215 (see TDF_* in tree.h). */
2218 debug_tree_cfg (int flags
)
2220 dump_tree_cfg (stderr
, flags
);
2224 /* Dump the program showing basic block boundaries on the given FILE.
2226 FLAGS are the same used by the tree dumping functions (see TDF_* in
2230 dump_tree_cfg (FILE *file
, int flags
)
2232 if (flags
& TDF_DETAILS
)
2234 const char *funcname
2235 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2238 fprintf (file
, ";; Function %s\n\n", funcname
);
2239 fprintf (file
, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2240 n_basic_blocks
, n_edges
, last_basic_block
);
2242 brief_dump_cfg (file
);
2243 fprintf (file
, "\n");
2246 if (flags
& TDF_STATS
)
2247 dump_cfg_stats (file
);
2249 dump_function_to_file (current_function_decl
, file
, flags
| TDF_BLOCKS
);
2253 /* Dump CFG statistics on FILE. */
2256 dump_cfg_stats (FILE *file
)
2258 static long max_num_merged_labels
= 0;
2259 unsigned long size
, total
= 0;
2262 const char * const fmt_str
= "%-30s%-13s%12s\n";
2263 const char * const fmt_str_1
= "%-30s%13d%11lu%c\n";
2264 const char * const fmt_str_3
= "%-43s%11lu%c\n";
2265 const char *funcname
2266 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2269 fprintf (file
, "\nCFG Statistics for %s\n\n", funcname
);
2271 fprintf (file
, "---------------------------------------------------------\n");
2272 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
2273 fprintf (file
, fmt_str
, "", " instances ", "used ");
2274 fprintf (file
, "---------------------------------------------------------\n");
2276 size
= n_basic_blocks
* sizeof (struct basic_block_def
);
2278 fprintf (file
, fmt_str_1
, "Basic blocks", n_basic_blocks
,
2279 SCALE (size
), LABEL (size
));
2285 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2288 size
= n_edges
* sizeof (struct edge_def
);
2290 fprintf (file
, fmt_str_1
, "Edges", n_edges
, SCALE (size
), LABEL (size
));
2292 size
= n_basic_blocks
* sizeof (struct bb_ann_d
);
2294 fprintf (file
, fmt_str_1
, "Basic block annotations", n_basic_blocks
,
2295 SCALE (size
), LABEL (size
));
2297 fprintf (file
, "---------------------------------------------------------\n");
2298 fprintf (file
, fmt_str_3
, "Total memory used by CFG data", SCALE (total
),
2300 fprintf (file
, "---------------------------------------------------------\n");
2301 fprintf (file
, "\n");
2303 if (cfg_stats
.num_merged_labels
> max_num_merged_labels
)
2304 max_num_merged_labels
= cfg_stats
.num_merged_labels
;
2306 fprintf (file
, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2307 cfg_stats
.num_merged_labels
, max_num_merged_labels
);
2309 fprintf (file
, "\n");
2313 /* Dump CFG statistics on stderr. Keep extern so that it's always
2314 linked in the final executable. */
2317 debug_cfg_stats (void)
2319 dump_cfg_stats (stderr
);
2323 /* Dump the flowgraph to a .vcg FILE. */
2326 tree_cfg2vcg (FILE *file
)
2330 const char *funcname
2331 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2333 /* Write the file header. */
2334 fprintf (file
, "graph: { title: \"%s\"\n", funcname
);
2335 fprintf (file
, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2336 fprintf (file
, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2338 /* Write blocks and edges. */
2339 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
2341 fprintf (file
, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2344 if (e
->flags
& EDGE_FAKE
)
2345 fprintf (file
, " linestyle: dotted priority: 10");
2347 fprintf (file
, " linestyle: solid priority: 100");
2349 fprintf (file
, " }\n");
2355 enum tree_code head_code
, end_code
;
2356 const char *head_name
, *end_name
;
2359 tree first
= first_stmt (bb
);
2360 tree last
= last_stmt (bb
);
2364 head_code
= TREE_CODE (first
);
2365 head_name
= tree_code_name
[head_code
];
2366 head_line
= get_lineno (first
);
2369 head_name
= "no-statement";
2373 end_code
= TREE_CODE (last
);
2374 end_name
= tree_code_name
[end_code
];
2375 end_line
= get_lineno (last
);
2378 end_name
= "no-statement";
2380 fprintf (file
, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2381 bb
->index
, bb
->index
, head_name
, head_line
, end_name
,
2384 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2386 if (e
->dest
== EXIT_BLOCK_PTR
)
2387 fprintf (file
, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb
->index
);
2389 fprintf (file
, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb
->index
, e
->dest
->index
);
2391 if (e
->flags
& EDGE_FAKE
)
2392 fprintf (file
, " priority: 10 linestyle: dotted");
2394 fprintf (file
, " priority: 100 linestyle: solid");
2396 fprintf (file
, " }\n");
2399 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2403 fputs ("}\n\n", file
);
2408 /*---------------------------------------------------------------------------
2409 Miscellaneous helpers
2410 ---------------------------------------------------------------------------*/
2412 /* Return true if T represents a stmt that always transfers control. */
2415 is_ctrl_stmt (tree t
)
2417 return (TREE_CODE (t
) == COND_EXPR
2418 || TREE_CODE (t
) == SWITCH_EXPR
2419 || TREE_CODE (t
) == GOTO_EXPR
2420 || TREE_CODE (t
) == RETURN_EXPR
2421 || TREE_CODE (t
) == RESX_EXPR
);
2425 /* Return true if T is a statement that may alter the flow of control
2426 (e.g., a call to a non-returning function). */
2429 is_ctrl_altering_stmt (tree t
)
2433 #if defined ENABLE_CHECKING
2438 call
= get_call_expr_in (t
);
2441 /* A non-pure/const CALL_EXPR alters flow control if the current
2442 function has nonlocal labels. */
2443 if (TREE_SIDE_EFFECTS (call
) && current_function_has_nonlocal_label
)
2446 /* A CALL_EXPR also alters control flow if it does not return. */
2447 if (call_expr_flags (call
) & (ECF_NORETURN
| ECF_LONGJMP
))
2451 /* If a statement can throw, it alters control flow. */
2452 return tree_can_throw_internal (t
);
2456 /* Return true if T is a computed goto. */
2459 computed_goto_p (tree t
)
2461 return (TREE_CODE (t
) == GOTO_EXPR
2462 && TREE_CODE (GOTO_DESTINATION (t
)) != LABEL_DECL
);
2466 /* Checks whether EXPR is a simple local goto. */
2469 simple_goto_p (tree expr
)
2471 return (TREE_CODE (expr
) == GOTO_EXPR
2472 && TREE_CODE (GOTO_DESTINATION (expr
)) == LABEL_DECL
);
2476 /* Return true if T should start a new basic block. PREV_T is the
2477 statement preceding T. It is used when T is a label or a case label.
2478 Labels should only start a new basic block if their previous statement
2479 wasn't a label. Otherwise, sequence of labels would generate
2480 unnecessary basic blocks that only contain a single label. */
2483 stmt_starts_bb_p (tree t
, tree prev_t
)
2485 enum tree_code code
;
2490 /* LABEL_EXPRs start a new basic block only if the preceding
2491 statement wasn't a label of the same type. This prevents the
2492 creation of consecutive blocks that have nothing but a single
2494 code
= TREE_CODE (t
);
2495 if (code
== LABEL_EXPR
)
2497 /* Nonlocal and computed GOTO targets always start a new block. */
2498 if (code
== LABEL_EXPR
2499 && (DECL_NONLOCAL (LABEL_EXPR_LABEL (t
))
2500 || FORCED_LABEL (LABEL_EXPR_LABEL (t
))))
2503 if (prev_t
&& TREE_CODE (prev_t
) == code
)
2505 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t
)))
2508 cfg_stats
.num_merged_labels
++;
2519 /* Return true if T should end a basic block. */
2522 stmt_ends_bb_p (tree t
)
2524 return is_ctrl_stmt (t
) || is_ctrl_altering_stmt (t
);
2528 /* Add gotos that used to be represented implicitly in the CFG. */
2531 disband_implicit_edges (void)
2534 block_stmt_iterator last
;
2540 last
= bsi_last (bb
);
2541 stmt
= last_stmt (bb
);
2543 if (stmt
&& TREE_CODE (stmt
) == COND_EXPR
)
2545 /* Remove superfluous gotos from COND_EXPR branches. Moved
2546 from cfg_remove_useless_stmts here since it violates the
2547 invariants for tree--cfg correspondence and thus fits better
2548 here where we do it anyway. */
2549 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2551 if (e
->dest
!= bb
->next_bb
)
2554 if (e
->flags
& EDGE_TRUE_VALUE
)
2555 COND_EXPR_THEN (stmt
) = build_empty_stmt ();
2556 else if (e
->flags
& EDGE_FALSE_VALUE
)
2557 COND_EXPR_ELSE (stmt
) = build_empty_stmt ();
2560 e
->flags
|= EDGE_FALLTHRU
;
2566 if (stmt
&& TREE_CODE (stmt
) == RETURN_EXPR
)
2568 /* Remove the RETURN_EXPR if we may fall though to the exit
2571 || bb
->succ
->succ_next
2572 || bb
->succ
->dest
!= EXIT_BLOCK_PTR
)
2575 if (bb
->next_bb
== EXIT_BLOCK_PTR
2576 && !TREE_OPERAND (stmt
, 0))
2579 bb
->succ
->flags
|= EDGE_FALLTHRU
;
2584 /* There can be no fallthru edge if the last statement is a control
2586 if (stmt
&& is_ctrl_stmt (stmt
))
2589 /* Find a fallthru edge and emit the goto if necessary. */
2590 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2591 if (e
->flags
& EDGE_FALLTHRU
)
2594 if (!e
|| e
->dest
== bb
->next_bb
)
2597 if (e
->dest
== EXIT_BLOCK_PTR
)
2600 label
= tree_block_label (e
->dest
);
2602 stmt
= build1 (GOTO_EXPR
, void_type_node
, label
);
2603 #ifdef USE_MAPPED_LOCATION
2604 SET_EXPR_LOCATION (stmt
, e
->goto_locus
);
2606 SET_EXPR_LOCUS (stmt
, e
->goto_locus
);
2608 bsi_insert_after (&last
, stmt
, BSI_NEW_STMT
);
2609 e
->flags
&= ~EDGE_FALLTHRU
;
2613 /* Remove block annotations and other datastructures. */
2616 delete_tree_cfg_annotations (void)
2619 if (n_basic_blocks
> 0)
2620 free_blocks_annotations ();
2622 label_to_block_map
= NULL
;
2629 /* Return the first statement in basic block BB. */
2632 first_stmt (basic_block bb
)
2634 block_stmt_iterator i
= bsi_start (bb
);
2635 return !bsi_end_p (i
) ? bsi_stmt (i
) : NULL_TREE
;
2639 /* Return the last statement in basic block BB. */
2642 last_stmt (basic_block bb
)
2644 block_stmt_iterator b
= bsi_last (bb
);
2645 return !bsi_end_p (b
) ? bsi_stmt (b
) : NULL_TREE
;
2649 /* Return a pointer to the last statement in block BB. */
2652 last_stmt_ptr (basic_block bb
)
2654 block_stmt_iterator last
= bsi_last (bb
);
2655 return !bsi_end_p (last
) ? bsi_stmt_ptr (last
) : NULL
;
2659 /* Return the last statement of an otherwise empty block. Return NULL
2660 if the block is totally empty, or if it contains more than one
2664 last_and_only_stmt (basic_block bb
)
2666 block_stmt_iterator i
= bsi_last (bb
);
2672 last
= bsi_stmt (i
);
2677 /* Empty statements should no longer appear in the instruction stream.
2678 Everything that might have appeared before should be deleted by
2679 remove_useless_stmts, and the optimizers should just bsi_remove
2680 instead of smashing with build_empty_stmt.
2682 Thus the only thing that should appear here in a block containing
2683 one executable statement is a label. */
2684 prev
= bsi_stmt (i
);
2685 if (TREE_CODE (prev
) == LABEL_EXPR
)
2692 /* Mark BB as the basic block holding statement T. */
2695 set_bb_for_stmt (tree t
, basic_block bb
)
2697 if (TREE_CODE (t
) == STATEMENT_LIST
)
2699 tree_stmt_iterator i
;
2700 for (i
= tsi_start (t
); !tsi_end_p (i
); tsi_next (&i
))
2701 set_bb_for_stmt (tsi_stmt (i
), bb
);
2705 stmt_ann_t ann
= get_stmt_ann (t
);
2708 /* If the statement is a label, add the label to block-to-labels map
2709 so that we can speed up edge creation for GOTO_EXPRs. */
2710 if (TREE_CODE (t
) == LABEL_EXPR
)
2714 t
= LABEL_EXPR_LABEL (t
);
2715 uid
= LABEL_DECL_UID (t
);
2718 LABEL_DECL_UID (t
) = uid
= cfun
->last_label_uid
++;
2719 if (VARRAY_SIZE (label_to_block_map
) <= (unsigned) uid
)
2720 VARRAY_GROW (label_to_block_map
, 3 * uid
/ 2);
2724 #ifdef ENABLE_CHECKING
2725 /* We're moving an existing label. Make sure that we've
2726 removed it from the old block. */
2727 if (bb
&& VARRAY_BB (label_to_block_map
, uid
))
2731 VARRAY_BB (label_to_block_map
, uid
) = bb
;
2736 /* Finds iterator for STMT. */
2738 extern block_stmt_iterator
2739 stmt_for_bsi (tree stmt
)
2741 block_stmt_iterator bsi
;
2743 for (bsi
= bsi_start (bb_for_stmt (stmt
)); !bsi_end_p (bsi
); bsi_next (&bsi
))
2744 if (bsi_stmt (bsi
) == stmt
)
2750 /* Insert statement (or statement list) T before the statement
2751 pointed-to by iterator I. M specifies how to update iterator I
2752 after insertion (see enum bsi_iterator_update). */
2755 bsi_insert_before (block_stmt_iterator
*i
, tree t
, enum bsi_iterator_update m
)
2757 set_bb_for_stmt (t
, i
->bb
);
2758 tsi_link_before (&i
->tsi
, t
, m
);
2763 /* Insert statement (or statement list) T after the statement
2764 pointed-to by iterator I. M specifies how to update iterator I
2765 after insertion (see enum bsi_iterator_update). */
2768 bsi_insert_after (block_stmt_iterator
*i
, tree t
, enum bsi_iterator_update m
)
2770 set_bb_for_stmt (t
, i
->bb
);
2771 tsi_link_after (&i
->tsi
, t
, m
);
2776 /* Remove the statement pointed to by iterator I. The iterator is updated
2777 to the next statement. */
2780 bsi_remove (block_stmt_iterator
*i
)
2782 tree t
= bsi_stmt (*i
);
2783 set_bb_for_stmt (t
, NULL
);
2784 tsi_delink (&i
->tsi
);
2788 /* Move the statement at FROM so it comes right after the statement at TO. */
2791 bsi_move_after (block_stmt_iterator
*from
, block_stmt_iterator
*to
)
2793 tree stmt
= bsi_stmt (*from
);
2795 bsi_insert_after (to
, stmt
, BSI_SAME_STMT
);
2799 /* Move the statement at FROM so it comes right before the statement at TO. */
2802 bsi_move_before (block_stmt_iterator
*from
, block_stmt_iterator
*to
)
2804 tree stmt
= bsi_stmt (*from
);
2806 bsi_insert_before (to
, stmt
, BSI_SAME_STMT
);
2810 /* Move the statement at FROM to the end of basic block BB. */
2813 bsi_move_to_bb_end (block_stmt_iterator
*from
, basic_block bb
)
2815 block_stmt_iterator last
= bsi_last (bb
);
2817 /* Have to check bsi_end_p because it could be an empty block. */
2818 if (!bsi_end_p (last
) && is_ctrl_stmt (bsi_stmt (last
)))
2819 bsi_move_before (from
, &last
);
2821 bsi_move_after (from
, &last
);
2825 /* Replace the contents of the statement pointed to by iterator BSI
2826 with STMT. If PRESERVE_EH_INFO is true, the exception handling
2827 information of the original statement is preserved. */
2830 bsi_replace (const block_stmt_iterator
*bsi
, tree stmt
, bool preserve_eh_info
)
2833 tree orig_stmt
= bsi_stmt (*bsi
);
2835 SET_EXPR_LOCUS (stmt
, EXPR_LOCUS (orig_stmt
));
2836 set_bb_for_stmt (stmt
, bsi
->bb
);
2838 /* Preserve EH region information from the original statement, if
2839 requested by the caller. */
2840 if (preserve_eh_info
)
2842 eh_region
= lookup_stmt_eh_region (orig_stmt
);
2844 add_stmt_to_eh_region (stmt
, eh_region
);
2847 *bsi_stmt_ptr (*bsi
) = stmt
;
2852 /* Insert the statement pointed-to by BSI into edge E. Every attempt
2853 is made to place the statement in an existing basic block, but
2854 sometimes that isn't possible. When it isn't possible, the edge is
2855 split and the statement is added to the new block.
2857 In all cases, the returned *BSI points to the correct location. The
2858 return value is true if insertion should be done after the location,
2859 or false if it should be done before the location. If new basic block
2860 has to be created, it is stored in *NEW_BB. */
2863 tree_find_edge_insert_loc (edge e
, block_stmt_iterator
*bsi
,
2864 basic_block
*new_bb
)
2866 basic_block dest
, src
;
2872 /* If the destination has one predecessor which has no PHI nodes,
2873 insert there. Except for the exit block.
2875 The requirement for no PHI nodes could be relaxed. Basically we
2876 would have to examine the PHIs to prove that none of them used
2877 the value set by the statement we want to insert on E. That
2878 hardly seems worth the effort. */
2879 if (dest
->pred
->pred_next
== NULL
2880 && ! phi_nodes (dest
)
2881 && dest
!= EXIT_BLOCK_PTR
)
2883 *bsi
= bsi_start (dest
);
2884 if (bsi_end_p (*bsi
))
2887 /* Make sure we insert after any leading labels. */
2888 tmp
= bsi_stmt (*bsi
);
2889 while (TREE_CODE (tmp
) == LABEL_EXPR
)
2892 if (bsi_end_p (*bsi
))
2894 tmp
= bsi_stmt (*bsi
);
2897 if (bsi_end_p (*bsi
))
2899 *bsi
= bsi_last (dest
);
2906 /* If the source has one successor, the edge is not abnormal and
2907 the last statement does not end a basic block, insert there.
2908 Except for the entry block. */
2910 if ((e
->flags
& EDGE_ABNORMAL
) == 0
2911 && src
->succ
->succ_next
== NULL
2912 && src
!= ENTRY_BLOCK_PTR
)
2914 *bsi
= bsi_last (src
);
2915 if (bsi_end_p (*bsi
))
2918 tmp
= bsi_stmt (*bsi
);
2919 if (!stmt_ends_bb_p (tmp
))
2922 /* Insert code just before returning the value. We may need to decompose
2923 the return in the case it contains non-trivial operand. */
2924 if (TREE_CODE (tmp
) == RETURN_EXPR
)
2926 tree op
= TREE_OPERAND (tmp
, 0);
2927 if (!is_gimple_val (op
))
2929 if (TREE_CODE (op
) != MODIFY_EXPR
)
2931 bsi_insert_before (bsi
, op
, BSI_NEW_STMT
);
2932 TREE_OPERAND (tmp
, 0) = TREE_OPERAND (op
, 0);
2939 /* Otherwise, create a new basic block, and split this edge. */
2940 dest
= split_edge (e
);
2948 /* This routine will commit all pending edge insertions, creating any new
2949 basic blocks which are necessary.
2951 If specified, NEW_BLOCKS returns a count of the number of new basic
2952 blocks which were created. */
2955 bsi_commit_edge_inserts (int *new_blocks
)
2961 blocks
= n_basic_blocks
;
2963 bsi_commit_edge_inserts_1 (ENTRY_BLOCK_PTR
->succ
);
2966 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2967 bsi_commit_edge_inserts_1 (e
);
2970 *new_blocks
= n_basic_blocks
- blocks
;
2974 /* Commit insertions pending at edge E. */
2977 bsi_commit_edge_inserts_1 (edge e
)
2979 if (PENDING_STMT (e
))
2981 block_stmt_iterator bsi
;
2982 tree stmt
= PENDING_STMT (e
);
2984 PENDING_STMT (e
) = NULL_TREE
;
2986 if (tree_find_edge_insert_loc (e
, &bsi
, NULL
))
2987 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
2989 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
2994 /* Add STMT to the pending list of edge E. No actual insertion is
2995 made until a call to bsi_commit_edge_inserts () is made. */
2998 bsi_insert_on_edge (edge e
, tree stmt
)
3000 append_to_statement_list (stmt
, &PENDING_STMT (e
));
3003 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts. If new block has to
3004 be created, it is returned. */
3007 bsi_insert_on_edge_immediate (edge e
, tree stmt
)
3009 block_stmt_iterator bsi
;
3010 basic_block new_bb
= NULL
;
3012 if (PENDING_STMT (e
))
3015 if (tree_find_edge_insert_loc (e
, &bsi
, &new_bb
))
3016 bsi_insert_after (&bsi
, stmt
, BSI_NEW_STMT
);
3018 bsi_insert_before (&bsi
, stmt
, BSI_NEW_STMT
);
3023 /*---------------------------------------------------------------------------
3024 Tree specific functions for CFG manipulation
3025 ---------------------------------------------------------------------------*/
3027 /* Split a (typically critical) edge EDGE_IN. Return the new block.
3028 Abort on abnormal edges. */
3031 tree_split_edge (edge edge_in
)
3033 basic_block new_bb
, after_bb
, dest
, src
;
3038 /* Abnormal edges cannot be split. */
3039 if (edge_in
->flags
& EDGE_ABNORMAL
)
3043 dest
= edge_in
->dest
;
3045 /* Place the new block in the block list. Try to keep the new block
3046 near its "logical" location. This is of most help to humans looking
3047 at debugging dumps. */
3048 for (e
= dest
->pred
; e
; e
= e
->pred_next
)
3049 if (e
->src
->next_bb
== dest
)
3052 after_bb
= dest
->prev_bb
;
3054 after_bb
= edge_in
->src
;
3056 new_bb
= create_empty_bb (after_bb
);
3057 new_edge
= make_edge (new_bb
, dest
, EDGE_FALLTHRU
);
3059 /* Find all the PHI arguments on the original edge, and change them to
3060 the new edge. Do it before redirection, so that the argument does not
3062 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
3064 num_elem
= PHI_NUM_ARGS (phi
);
3065 for (i
= 0; i
< num_elem
; i
++)
3066 if (PHI_ARG_EDGE (phi
, i
) == edge_in
)
3068 PHI_ARG_EDGE (phi
, i
) = new_edge
;
3073 if (!redirect_edge_and_branch (edge_in
, new_bb
))
3076 if (PENDING_STMT (edge_in
))
3083 /* Return true when BB has label LABEL in it. */
3086 has_label_p (basic_block bb
, tree label
)
3088 block_stmt_iterator bsi
;
3090 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3092 tree stmt
= bsi_stmt (bsi
);
3094 if (TREE_CODE (stmt
) != LABEL_EXPR
)
3096 if (LABEL_EXPR_LABEL (stmt
) == label
)
3103 /* Callback for walk_tree, check that all elements with address taken are
3104 properly noticed as such. */
3107 verify_expr (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
3114 /* Check operand N for being valid GIMPLE and give error MSG if not.
3115 We check for constants explicitly since they are not considered
3116 gimple invariants if they overflowed. */
3117 #define CHECK_OP(N, MSG) \
3118 do { if (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, N))) != 'c' \
3119 && !is_gimple_val (TREE_OPERAND (t, N))) \
3120 { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3122 switch (TREE_CODE (t
))
3125 if (SSA_NAME_IN_FREE_LIST (t
))
3127 error ("SSA name in freelist but still referenced");
3133 x
= TREE_OPERAND (t
, 0);
3134 if (TREE_CODE (x
) == BIT_FIELD_REF
3135 && is_gimple_reg (TREE_OPERAND (x
, 0)))
3137 error ("GIMPLE register modified with BIT_FIELD_REF");
3143 /* Skip any references (they will be checked when we recurse down the
3144 tree) and ensure that any variable used as a prefix is marked
3146 for (x
= TREE_OPERAND (t
, 0);
3147 (handled_component_p (x
)
3148 || TREE_CODE (x
) == REALPART_EXPR
3149 || TREE_CODE (x
) == IMAGPART_EXPR
);
3150 x
= TREE_OPERAND (x
, 0))
3153 if (TREE_CODE (x
) != VAR_DECL
&& TREE_CODE (x
) != PARM_DECL
)
3155 if (!TREE_ADDRESSABLE (x
))
3157 error ("address taken, but ADDRESSABLE bit not set");
3163 x
= TREE_OPERAND (t
, 0);
3164 if (TREE_CODE (TREE_TYPE (x
)) != BOOLEAN_TYPE
)
3166 error ("non-boolean used in condition");
3173 case FIX_TRUNC_EXPR
:
3175 case FIX_FLOOR_EXPR
:
3176 case FIX_ROUND_EXPR
:
3181 case NON_LVALUE_EXPR
:
3182 case TRUTH_NOT_EXPR
:
3183 CHECK_OP (0, "Invalid operand to unary operator");
3190 case ARRAY_RANGE_REF
:
3192 case VIEW_CONVERT_EXPR
:
3193 /* We have a nest of references. Verify that each of the operands
3194 that determine where to reference is either a constant or a variable,
3195 verify that the base is valid, and then show we've already checked
3197 while (TREE_CODE (t
) == REALPART_EXPR
|| TREE_CODE (t
) == IMAGPART_EXPR
3198 || handled_component_p (t
))
3200 if (TREE_CODE (t
) == COMPONENT_REF
&& TREE_OPERAND (t
, 2))
3201 CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3202 else if (TREE_CODE (t
) == ARRAY_REF
3203 || TREE_CODE (t
) == ARRAY_RANGE_REF
)
3205 CHECK_OP (1, "Invalid array index.");
3206 if (TREE_OPERAND (t
, 2))
3207 CHECK_OP (2, "Invalid array lower bound.");
3208 if (TREE_OPERAND (t
, 3))
3209 CHECK_OP (3, "Invalid array stride.");
3211 else if (TREE_CODE (t
) == BIT_FIELD_REF
)
3213 CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3214 CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3217 t
= TREE_OPERAND (t
, 0);
3220 if (TREE_CODE_CLASS (TREE_CODE (t
)) != 'c'
3221 && !is_gimple_lvalue (t
))
3223 error ("Invalid reference prefix.");
3235 case UNORDERED_EXPR
:
3246 case TRUNC_DIV_EXPR
:
3248 case FLOOR_DIV_EXPR
:
3249 case ROUND_DIV_EXPR
:
3250 case TRUNC_MOD_EXPR
:
3252 case FLOOR_MOD_EXPR
:
3253 case ROUND_MOD_EXPR
:
3255 case EXACT_DIV_EXPR
:
3265 CHECK_OP (0, "Invalid operand to binary operator");
3266 CHECK_OP (1, "Invalid operand to binary operator");
3278 /* Verify STMT, return true if STMT is not in GIMPLE form.
3279 TODO: Implement type checking. */
3282 verify_stmt (tree stmt
, bool last_in_block
)
3286 if (!is_gimple_stmt (stmt
))
3288 error ("Is not a valid GIMPLE statement.");
3292 addr
= walk_tree (&stmt
, verify_expr
, NULL
, NULL
);
3295 debug_generic_stmt (addr
);
3299 /* If the statement is marked as part of an EH region, then it is
3300 expected that the statement could throw. Verify that when we
3301 have optimizations that simplify statements such that we prove
3302 that they cannot throw, that we update other data structures
3304 if (lookup_stmt_eh_region (stmt
) >= 0)
3306 if (!tree_could_throw_p (stmt
))
3308 error ("Statement marked for throw, but doesn't.");
3311 if (!last_in_block
&& tree_can_throw_internal (stmt
))
3313 error ("Statement marked for throw in middle of block.");
3321 debug_generic_stmt (stmt
);
3326 /* Return true when the T can be shared. */
3329 tree_node_can_be_shared (tree t
)
3331 if (TYPE_P (t
) || DECL_P (t
)
3332 /* We check for constants explicitly since they are not considered
3333 gimple invariants if they overflowed. */
3334 || TREE_CODE_CLASS (TREE_CODE (t
)) == 'c'
3335 || is_gimple_min_invariant (t
)
3336 || TREE_CODE (t
) == SSA_NAME
)
3339 while (((TREE_CODE (t
) == ARRAY_REF
|| TREE_CODE (t
) == ARRAY_RANGE_REF
)
3340 /* We check for constants explicitly since they are not considered
3341 gimple invariants if they overflowed. */
3342 && (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t
, 1))) == 'c'
3343 || is_gimple_min_invariant (TREE_OPERAND (t
, 1))))
3344 || (TREE_CODE (t
) == COMPONENT_REF
3345 || TREE_CODE (t
) == REALPART_EXPR
3346 || TREE_CODE (t
) == IMAGPART_EXPR
))
3347 t
= TREE_OPERAND (t
, 0);
3356 /* Called via walk_trees. Verify tree sharing. */
3359 verify_node_sharing (tree
* tp
, int *walk_subtrees
, void *data
)
3361 htab_t htab
= (htab_t
) data
;
3364 if (tree_node_can_be_shared (*tp
))
3366 *walk_subtrees
= false;
3370 slot
= htab_find_slot (htab
, *tp
, INSERT
);
3379 /* Verify the GIMPLE statement chain. */
3385 block_stmt_iterator bsi
;
3390 timevar_push (TV_TREE_STMT_VERIFY
);
3391 htab
= htab_create (37, htab_hash_pointer
, htab_eq_pointer
, NULL
);
3398 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
3400 int phi_num_args
= PHI_NUM_ARGS (phi
);
3402 for (i
= 0; i
< phi_num_args
; i
++)
3404 tree t
= PHI_ARG_DEF (phi
, i
);
3407 /* Addressable variables do have SSA_NAMEs but they
3408 are not considered gimple values. */
3409 if (TREE_CODE (t
) != SSA_NAME
3410 && TREE_CODE (t
) != FUNCTION_DECL
3411 && !is_gimple_val (t
))
3413 error ("PHI def is not a GIMPLE value");
3414 debug_generic_stmt (phi
);
3415 debug_generic_stmt (t
);
3419 addr
= walk_tree (&t
, verify_expr
, NULL
, NULL
);
3422 debug_generic_stmt (addr
);
3426 addr
= walk_tree (&t
, verify_node_sharing
, htab
, NULL
);
3429 error ("Incorrect sharing of tree nodes");
3430 debug_generic_stmt (phi
);
3431 debug_generic_stmt (addr
);
3437 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); )
3439 tree stmt
= bsi_stmt (bsi
);
3441 err
|= verify_stmt (stmt
, bsi_end_p (bsi
));
3442 addr
= walk_tree (&stmt
, verify_node_sharing
, htab
, NULL
);
3445 error ("Incorrect sharing of tree nodes");
3446 debug_generic_stmt (stmt
);
3447 debug_generic_stmt (addr
);
3454 internal_error ("verify_stmts failed.");
3457 timevar_pop (TV_TREE_STMT_VERIFY
);
3461 /* Verifies that the flow information is OK. */
3464 tree_verify_flow_info (void)
3468 block_stmt_iterator bsi
;
3472 if (ENTRY_BLOCK_PTR
->stmt_list
)
3474 error ("ENTRY_BLOCK has a statement list associated with it\n");
3478 if (EXIT_BLOCK_PTR
->stmt_list
)
3480 error ("EXIT_BLOCK has a statement list associated with it\n");
3484 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
3485 if (e
->flags
& EDGE_FALLTHRU
)
3487 error ("Fallthru to exit from bb %d\n", e
->src
->index
);
3493 bool found_ctrl_stmt
= false;
3495 /* Skip labels on the start of basic block. */
3496 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3498 if (TREE_CODE (bsi_stmt (bsi
)) != LABEL_EXPR
)
3501 if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi
))) != bb
)
3503 error ("Label %s to block does not match in bb %d\n",
3504 IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi
))),
3509 if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi
)))
3510 != current_function_decl
)
3512 error ("Label %s has incorrect context in bb %d\n",
3513 IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi
))),
3519 /* Verify that body of basic block BB is free of control flow. */
3520 for (; !bsi_end_p (bsi
); bsi_next (&bsi
))
3522 tree stmt
= bsi_stmt (bsi
);
3524 if (found_ctrl_stmt
)
3526 error ("Control flow in the middle of basic block %d\n",
3531 if (stmt_ends_bb_p (stmt
))
3532 found_ctrl_stmt
= true;
3534 if (TREE_CODE (stmt
) == LABEL_EXPR
)
3536 error ("Label %s in the middle of basic block %d\n",
3537 IDENTIFIER_POINTER (DECL_NAME (stmt
)),
3542 bsi
= bsi_last (bb
);
3543 if (bsi_end_p (bsi
))
3546 stmt
= bsi_stmt (bsi
);
3548 if (is_ctrl_stmt (stmt
))
3550 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3551 if (e
->flags
& EDGE_FALLTHRU
)
3553 error ("Fallthru edge after a control statement in bb %d \n",
3559 switch (TREE_CODE (stmt
))
3565 if (TREE_CODE (COND_EXPR_THEN (stmt
)) != GOTO_EXPR
3566 || TREE_CODE (COND_EXPR_ELSE (stmt
)) != GOTO_EXPR
)
3568 error ("Structured COND_EXPR at the end of bb %d\n", bb
->index
);
3572 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
3574 if (!true_edge
|| !false_edge
3575 || !(true_edge
->flags
& EDGE_TRUE_VALUE
)
3576 || !(false_edge
->flags
& EDGE_FALSE_VALUE
)
3577 || (true_edge
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
))
3578 || (false_edge
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
))
3579 || bb
->succ
->succ_next
->succ_next
)
3581 error ("Wrong outgoing edge flags at end of bb %d\n",
3586 if (!has_label_p (true_edge
->dest
,
3587 GOTO_DESTINATION (COND_EXPR_THEN (stmt
))))
3589 error ("`then' label does not match edge at end of bb %d\n",
3594 if (!has_label_p (false_edge
->dest
,
3595 GOTO_DESTINATION (COND_EXPR_ELSE (stmt
))))
3597 error ("`else' label does not match edge at end of bb %d\n",
3605 if (simple_goto_p (stmt
))
3607 error ("Explicit goto at end of bb %d\n", bb
->index
);
3612 /* FIXME. We should double check that the labels in the
3613 destination blocks have their address taken. */
3614 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3615 if ((e
->flags
& (EDGE_FALLTHRU
| EDGE_TRUE_VALUE
3616 | EDGE_FALSE_VALUE
))
3617 || !(e
->flags
& EDGE_ABNORMAL
))
3619 error ("Wrong outgoing edge flags at end of bb %d\n",
3627 if (!bb
->succ
|| bb
->succ
->succ_next
3628 || (bb
->succ
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
3629 | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
3631 error ("Wrong outgoing edge flags at end of bb %d\n", bb
->index
);
3634 if (bb
->succ
->dest
!= EXIT_BLOCK_PTR
)
3636 error ("Return edge does not point to exit in bb %d\n",
3649 vec
= SWITCH_LABELS (stmt
);
3650 n
= TREE_VEC_LENGTH (vec
);
3652 /* Mark all the destination basic blocks. */
3653 for (i
= 0; i
< n
; ++i
)
3655 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
3656 basic_block label_bb
= label_to_block (lab
);
3658 if (label_bb
->aux
&& label_bb
->aux
!= (void *)1)
3660 label_bb
->aux
= (void *)1;
3663 /* Verify that the case labels are sorted. */
3664 prev
= TREE_VEC_ELT (vec
, 0);
3665 for (i
= 1; i
< n
- 1; ++i
)
3667 tree c
= TREE_VEC_ELT (vec
, i
);
3670 error ("Found default case not at end of case vector");
3674 if (! tree_int_cst_lt (CASE_LOW (prev
), CASE_LOW (c
)))
3676 error ("Case labels not sorted:\n ");
3677 print_generic_expr (stderr
, prev
, 0);
3678 fprintf (stderr
," is greater than ");
3679 print_generic_expr (stderr
, c
, 0);
3680 fprintf (stderr
," but comes before it.\n");
3685 if (CASE_LOW (TREE_VEC_ELT (vec
, n
- 1)))
3687 error ("No default case found at end of case vector");
3691 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3695 error ("Extra outgoing edge %d->%d\n",
3696 bb
->index
, e
->dest
->index
);
3699 e
->dest
->aux
= (void *)2;
3700 if ((e
->flags
& (EDGE_FALLTHRU
| EDGE_ABNORMAL
3701 | EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
3703 error ("Wrong outgoing edge flags at end of bb %d\n",
3709 /* Check that we have all of them. */
3710 for (i
= 0; i
< n
; ++i
)
3712 tree lab
= CASE_LABEL (TREE_VEC_ELT (vec
, i
));
3713 basic_block label_bb
= label_to_block (lab
);
3715 if (label_bb
->aux
!= (void *)2)
3717 error ("Missing edge %i->%i\n",
3718 bb
->index
, label_bb
->index
);
3723 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
3724 e
->dest
->aux
= (void *)0;
3731 if (dom_computed
[CDI_DOMINATORS
] >= DOM_NO_FAST_QUERY
)
3732 verify_dominators (CDI_DOMINATORS
);
3738 /* Updates phi nodes after creating forwarder block joined
3739 by edge FALLTHRU. */
3742 tree_make_forwarder_block (edge fallthru
)
3745 basic_block dummy
, bb
;
3746 tree phi
, new_phi
, var
, prev
, next
;
3748 dummy
= fallthru
->src
;
3749 bb
= fallthru
->dest
;
3751 if (!bb
->pred
->pred_next
)
3754 /* If we redirected a branch we must create new phi nodes at the
3756 for (phi
= phi_nodes (dummy
); phi
; phi
= PHI_CHAIN (phi
))
3758 var
= PHI_RESULT (phi
);
3759 new_phi
= create_phi_node (var
, bb
);
3760 SSA_NAME_DEF_STMT (var
) = new_phi
;
3761 SET_PHI_RESULT (phi
, make_ssa_name (SSA_NAME_VAR (var
), phi
));
3762 add_phi_arg (&new_phi
, PHI_RESULT (phi
), fallthru
);
3765 /* Ensure that the PHI node chain is in the same order. */
3767 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
3769 next
= PHI_CHAIN (phi
);
3770 PHI_CHAIN (phi
) = prev
;
3773 set_phi_nodes (bb
, prev
);
3775 /* Add the arguments we have stored on edges. */
3776 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
3781 for (phi
= phi_nodes (bb
), var
= PENDING_STMT (e
);
3783 phi
= PHI_CHAIN (phi
), var
= TREE_CHAIN (var
))
3784 add_phi_arg (&phi
, TREE_VALUE (var
), e
);
3786 PENDING_STMT (e
) = NULL
;
3791 /* Return true if basic block BB does nothing except pass control
3792 flow to another block and that we can safely insert a label at
3793 the start of the successor block. */
3796 tree_forwarder_block_p (basic_block bb
)
3798 block_stmt_iterator bsi
;
3801 /* If we have already determined that this block is not forwardable,
3802 then no further checks are necessary. */
3803 if (! bb_ann (bb
)->forwardable
)
3806 /* BB must have a single outgoing normal edge. Otherwise it can not be
3807 a forwarder block. */
3809 || bb
->succ
->succ_next
3810 || bb
->succ
->dest
== EXIT_BLOCK_PTR
3811 || (bb
->succ
->flags
& EDGE_ABNORMAL
)
3812 || bb
== ENTRY_BLOCK_PTR
)
3814 bb_ann (bb
)->forwardable
= 0;
3818 /* Successors of the entry block are not forwarders. */
3819 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
3822 bb_ann (bb
)->forwardable
= 0;
3826 /* BB can not have any PHI nodes. This could potentially be relaxed
3827 early in compilation if we re-rewrote the variables appearing in
3828 any PHI nodes in forwarder blocks. */
3831 bb_ann (bb
)->forwardable
= 0;
3835 /* Now walk through the statements. We can ignore labels, anything else
3836 means this is not a forwarder block. */
3837 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3839 tree stmt
= bsi_stmt (bsi
);
3841 switch (TREE_CODE (stmt
))
3844 if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt
)))
3849 bb_ann (bb
)->forwardable
= 0;
3858 /* Thread jumps over empty statements.
3860 This code should _not_ thread over obviously equivalent conditions
3861 as that requires nontrivial updates to the SSA graph. */
3866 edge e
, next
, last
, old
;
3867 basic_block bb
, dest
, tmp
, old_dest
, dom
;
3870 bool retval
= false;
3873 bb_ann (bb
)->forwardable
= 1;
3875 FOR_BB_BETWEEN (bb
, ENTRY_BLOCK_PTR
, EXIT_BLOCK_PTR
, next_bb
)
3877 /* Don't waste time on unreachable blocks. */
3881 /* Nor on forwarders. */
3882 if (tree_forwarder_block_p (bb
))
3885 /* This block is now part of a forwarding path, mark it as not
3886 forwardable so that we can detect loops. This bit will be
3888 bb_ann (bb
)->forwardable
= 0;
3890 /* Examine each of our block's successors to see if it is
3892 for (e
= bb
->succ
; e
; e
= next
)
3894 next
= e
->succ_next
;
3896 /* If the edge is abnormal or its destination is not
3897 forwardable, then there's nothing to do. */
3898 if ((e
->flags
& EDGE_ABNORMAL
)
3899 || !tree_forwarder_block_p (e
->dest
))
3902 /* Now walk through as many forwarder block as possible to
3903 find the ultimate destination we want to thread our jump
3905 last
= e
->dest
->succ
;
3906 bb_ann (e
->dest
)->forwardable
= 0;
3907 for (dest
= e
->dest
->succ
->dest
;
3908 tree_forwarder_block_p (dest
);
3910 dest
= dest
->succ
->dest
)
3912 /* An infinite loop detected. We redirect the edge anyway, so
3913 that the loop is shrunk into single basic block. */
3914 if (!bb_ann (dest
)->forwardable
)
3917 if (dest
->succ
->dest
== EXIT_BLOCK_PTR
)
3920 bb_ann (dest
)->forwardable
= 0;
3923 /* Reset the forwardable marks to 1. */
3926 tmp
= tmp
->succ
->dest
)
3927 bb_ann (tmp
)->forwardable
= 1;
3929 if (dest
== e
->dest
)
3932 old
= find_edge (bb
, dest
);
3935 /* If there already is an edge, check whether the values
3936 in phi nodes differ. */
3937 if (!phi_alternatives_equal (dest
, last
, old
))
3939 /* The previous block is forwarder. Redirect our jump
3940 to that target instead since we know it has no PHI
3941 nodes that will need updating. */
3944 /* That might mean that no forwarding at all is possible. */
3945 if (dest
== e
->dest
)
3948 old
= find_edge (bb
, dest
);
3952 /* Perform the redirection. */
3955 e
= redirect_edge_and_branch (e
, dest
);
3959 /* Update PHI nodes. We know that the new argument should
3960 have the same value as the argument associated with LAST.
3961 Otherwise we would have changed our target block above. */
3962 for (phi
= phi_nodes (dest
); phi
; phi
= PHI_CHAIN (phi
))
3964 arg
= phi_arg_from_edge (phi
, last
);
3967 add_phi_arg (&phi
, PHI_ARG_DEF (phi
, arg
), e
);
3971 /* Update the dominators. */
3972 if (dom_computed
[CDI_DOMINATORS
] >= DOM_CONS_OK
)
3974 /* Remove the unreachable blocks (observe that if all blocks
3975 were reachable before, only those in the path we threaded
3976 over and did not have any predecessor outside of the path
3977 become unreachable). */
3978 for (; old_dest
!= dest
; old_dest
= tmp
)
3980 tmp
= old_dest
->succ
->dest
;
3985 delete_basic_block (old_dest
);
3987 /* If the dominator of the destination was in the path, set its
3988 dominator to the start of the redirected edge. */
3989 if (get_immediate_dominator (CDI_DOMINATORS
, old_dest
) == NULL
)
3990 set_immediate_dominator (CDI_DOMINATORS
, old_dest
, bb
);
3992 /* Now proceed like if we forwarded just over one edge at a time.
3993 Algorithm for forwarding over edge A --> B then is
3996 idom (B) = idom (A);
3997 recount_idom (A); */
3999 for (; old_dest
!= dest
; old_dest
= tmp
)
4001 tmp
= old_dest
->succ
->dest
;
4003 if (get_immediate_dominator (CDI_DOMINATORS
, tmp
) == old_dest
)
4005 dom
= get_immediate_dominator (CDI_DOMINATORS
, old_dest
);
4006 set_immediate_dominator (CDI_DOMINATORS
, tmp
, dom
);
4009 dom
= recount_dominator (CDI_DOMINATORS
, old_dest
);
4010 set_immediate_dominator (CDI_DOMINATORS
, old_dest
, dom
);
4015 /* Reset the forwardable bit on our block since it's no longer in
4016 a forwarding chain path. */
4017 bb_ann (bb
)->forwardable
= 1;
4024 /* Return a non-special label in the head of basic block BLOCK.
4025 Create one if it doesn't exist. */
4028 tree_block_label (basic_block bb
)
4030 block_stmt_iterator i
, s
= bsi_start (bb
);
4034 for (i
= s
; !bsi_end_p (i
); first
= false, bsi_next (&i
))
4036 stmt
= bsi_stmt (i
);
4037 if (TREE_CODE (stmt
) != LABEL_EXPR
)
4039 label
= LABEL_EXPR_LABEL (stmt
);
4040 if (!DECL_NONLOCAL (label
))
4043 bsi_move_before (&i
, &s
);
4048 label
= create_artificial_label ();
4049 stmt
= build1 (LABEL_EXPR
, void_type_node
, label
);
4050 bsi_insert_before (&s
, stmt
, BSI_NEW_STMT
);
4055 /* Attempt to perform edge redirection by replacing a possibly complex
4056 jump instruction by a goto or by removing the jump completely.
4057 This can apply only if all edges now point to the same block. The
4058 parameters and return values are equivalent to
4059 redirect_edge_and_branch. */
4062 tree_try_redirect_by_replacing_jump (edge e
, basic_block target
)
4064 basic_block src
= e
->src
;
4066 block_stmt_iterator b
;
4069 /* Verify that all targets will be TARGET. */
4070 for (tmp
= src
->succ
; tmp
; tmp
= tmp
->succ_next
)
4071 if (tmp
->dest
!= target
&& tmp
!= e
)
4080 stmt
= bsi_stmt (b
);
4082 if (TREE_CODE (stmt
) == COND_EXPR
4083 || TREE_CODE (stmt
) == SWITCH_EXPR
)
4086 e
= ssa_redirect_edge (e
, target
);
4087 e
->flags
= EDGE_FALLTHRU
;
4095 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the
4096 edge representing the redirected branch. */
4099 tree_redirect_edge_and_branch (edge e
, basic_block dest
)
4101 basic_block bb
= e
->src
;
4102 block_stmt_iterator bsi
;
4106 if (e
->flags
& (EDGE_ABNORMAL_CALL
| EDGE_EH
))
4109 if (e
->src
!= ENTRY_BLOCK_PTR
4110 && (ret
= tree_try_redirect_by_replacing_jump (e
, dest
)))
4113 if (e
->dest
== dest
)
4116 label
= tree_block_label (dest
);
4118 bsi
= bsi_last (bb
);
4119 stmt
= bsi_end_p (bsi
) ? NULL
: bsi_stmt (bsi
);
4121 switch (stmt
? TREE_CODE (stmt
) : ERROR_MARK
)
4124 stmt
= (e
->flags
& EDGE_TRUE_VALUE
4125 ? COND_EXPR_THEN (stmt
)
4126 : COND_EXPR_ELSE (stmt
));
4127 GOTO_DESTINATION (stmt
) = label
;
4131 /* No non-abnormal edges should lead from a non-simple goto, and
4132 simple ones should be represented implicitly. */
4137 tree vec
= SWITCH_LABELS (stmt
);
4138 size_t i
, n
= TREE_VEC_LENGTH (vec
);
4140 for (i
= 0; i
< n
; ++i
)
4142 tree elt
= TREE_VEC_ELT (vec
, i
);
4143 if (label_to_block (CASE_LABEL (elt
)) == e
->dest
)
4144 CASE_LABEL (elt
) = label
;
4151 e
->flags
|= EDGE_FALLTHRU
;
4155 /* Otherwise it must be a fallthru edge, and we don't need to
4156 do anything besides redirecting it. */
4157 if (!(e
->flags
& EDGE_FALLTHRU
))
4162 /* Update/insert PHI nodes as necessary. */
4164 /* Now update the edges in the CFG. */
4165 e
= ssa_redirect_edge (e
, dest
);
4171 /* Simple wrapper, as we can always redirect fallthru edges. */
4174 tree_redirect_edge_and_branch_force (edge e
, basic_block dest
)
4176 e
= tree_redirect_edge_and_branch (e
, dest
);
4184 /* Splits basic block BB after statement STMT (but at least after the
4185 labels). If STMT is NULL, BB is split just after the labels. */
4188 tree_split_block (basic_block bb
, void *stmt
)
4190 block_stmt_iterator bsi
, bsi_tgt
;
4195 new_bb
= create_empty_bb (bb
);
4197 /* Redirect the outgoing edges. */
4198 new_bb
->succ
= bb
->succ
;
4200 for (e
= new_bb
->succ
; e
; e
= e
->succ_next
)
4203 if (stmt
&& TREE_CODE ((tree
) stmt
) == LABEL_EXPR
)
4206 /* Move everything from BSI to the new basic block. */
4207 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4209 act
= bsi_stmt (bsi
);
4210 if (TREE_CODE (act
) == LABEL_EXPR
)
4223 bsi_tgt
= bsi_start (new_bb
);
4224 while (!bsi_end_p (bsi
))
4226 act
= bsi_stmt (bsi
);
4228 bsi_insert_after (&bsi_tgt
, act
, BSI_NEW_STMT
);
4235 /* Moves basic block BB after block AFTER. */
4238 tree_move_block_after (basic_block bb
, basic_block after
)
4240 if (bb
->prev_bb
== after
)
4244 link_block (bb
, after
);
4250 /* Return true if basic_block can be duplicated. */
4253 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED
)
4259 /* Create a duplicate of the basic block BB. NOTE: This does not
4260 preserve SSA form. */
4263 tree_duplicate_bb (basic_block bb
)
4266 block_stmt_iterator bsi
, bsi_tgt
;
4268 ssa_op_iter op_iter
;
4270 new_bb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
4272 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
4274 mark_for_rewrite (PHI_RESULT (phi
));
4277 bsi_tgt
= bsi_start (new_bb
);
4278 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
4280 tree stmt
= bsi_stmt (bsi
);
4283 if (TREE_CODE (stmt
) == LABEL_EXPR
)
4286 /* Record the definitions. */
4287 get_stmt_operands (stmt
);
4289 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, op_iter
, SSA_OP_ALL_DEFS
)
4290 mark_for_rewrite (val
);
4292 copy
= unshare_expr (stmt
);
4294 /* Copy also the virtual operands. */
4295 get_stmt_ann (copy
);
4296 copy_virtual_operands (copy
, stmt
);
4298 bsi_insert_after (&bsi_tgt
, copy
, BSI_NEW_STMT
);
4305 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h) */
4308 dump_function_to_file (tree fn
, FILE *file
, int flags
)
4310 tree arg
, vars
, var
;
4311 bool ignore_topmost_bind
= false, any_var
= false;
4315 fprintf (file
, "%s (", lang_hooks
.decl_printable_name (fn
, 2));
4317 arg
= DECL_ARGUMENTS (fn
);
4320 print_generic_expr (file
, arg
, dump_flags
);
4321 if (TREE_CHAIN (arg
))
4322 fprintf (file
, ", ");
4323 arg
= TREE_CHAIN (arg
);
4325 fprintf (file
, ")\n");
4327 if (flags
& TDF_RAW
)
4329 dump_node (fn
, TDF_SLIM
| flags
, file
);
4333 /* When GIMPLE is lowered, the variables are no longer available in
4334 BIND_EXPRs, so display them separately. */
4335 if (cfun
&& cfun
->unexpanded_var_list
)
4337 ignore_topmost_bind
= true;
4339 fprintf (file
, "{\n");
4340 for (vars
= cfun
->unexpanded_var_list
; vars
; vars
= TREE_CHAIN (vars
))
4342 var
= TREE_VALUE (vars
);
4344 print_generic_decl (file
, var
, flags
);
4345 fprintf (file
, "\n");
4351 if (basic_block_info
)
4353 /* Make a CFG based dump. */
4354 check_bb_profile (ENTRY_BLOCK_PTR
, file
);
4355 if (!ignore_topmost_bind
)
4356 fprintf (file
, "{\n");
4358 if (any_var
&& n_basic_blocks
)
4359 fprintf (file
, "\n");
4362 dump_generic_bb (file
, bb
, 2, flags
);
4364 fprintf (file
, "}\n");
4365 check_bb_profile (EXIT_BLOCK_PTR
, file
);
4371 /* Make a tree based dump. */
4372 chain
= DECL_SAVED_TREE (fn
);
4374 if (TREE_CODE (chain
) == BIND_EXPR
)
4376 if (ignore_topmost_bind
)
4378 chain
= BIND_EXPR_BODY (chain
);
4386 if (!ignore_topmost_bind
)
4387 fprintf (file
, "{\n");
4392 fprintf (file
, "\n");
4394 print_generic_stmt_indented (file
, chain
, flags
, indent
);
4395 if (ignore_topmost_bind
)
4396 fprintf (file
, "}\n");
4399 fprintf (file
, "\n\n");
4403 /* Pretty print of the loops intermediate representation. */
4404 static void print_loop (FILE *, struct loop
*, int);
4405 static void print_pred_bbs (FILE *, edge
);
4406 static void print_succ_bbs (FILE *, edge
);
4409 /* Print the predecessors indexes of edge E on FILE. */
4412 print_pred_bbs (FILE *file
, edge e
)
4417 else if (e
->pred_next
== NULL
)
4418 fprintf (file
, "bb_%d", e
->src
->index
);
4422 fprintf (file
, "bb_%d, ", e
->src
->index
);
4423 print_pred_bbs (file
, e
->pred_next
);
4428 /* Print the successors indexes of edge E on FILE. */
4431 print_succ_bbs (FILE *file
, edge e
)
4435 else if (e
->succ_next
== NULL
)
4436 fprintf (file
, "bb_%d", e
->dest
->index
);
4439 fprintf (file
, "bb_%d, ", e
->dest
->index
);
4440 print_succ_bbs (file
, e
->succ_next
);
4445 /* Pretty print LOOP on FILE, indented INDENT spaces. */
4448 print_loop (FILE *file
, struct loop
*loop
, int indent
)
4456 s_indent
= (char *) alloca ((size_t) indent
+ 1);
4457 memset ((void *) s_indent
, ' ', (size_t) indent
);
4458 s_indent
[indent
] = '\0';
4460 /* Print the loop's header. */
4461 fprintf (file
, "%sloop_%d\n", s_indent
, loop
->num
);
4463 /* Print the loop's body. */
4464 fprintf (file
, "%s{\n", s_indent
);
4466 if (bb
->loop_father
== loop
)
4468 /* Print the basic_block's header. */
4469 fprintf (file
, "%s bb_%d (preds = {", s_indent
, bb
->index
);
4470 print_pred_bbs (file
, bb
->pred
);
4471 fprintf (file
, "}, succs = {");
4472 print_succ_bbs (file
, bb
->succ
);
4473 fprintf (file
, "})\n");
4475 /* Print the basic_block's body. */
4476 fprintf (file
, "%s {\n", s_indent
);
4477 tree_dump_bb (bb
, file
, indent
+ 4);
4478 fprintf (file
, "%s }\n", s_indent
);
4481 print_loop (file
, loop
->inner
, indent
+ 2);
4482 fprintf (file
, "%s}\n", s_indent
);
4483 print_loop (file
, loop
->next
, indent
);
4487 /* Follow a CFG edge from the entry point of the program, and on entry
4488 of a loop, pretty print the loop structure on FILE. */
4491 print_loop_ir (FILE *file
)
4495 bb
= BASIC_BLOCK (0);
4496 if (bb
&& bb
->loop_father
)
4497 print_loop (file
, bb
->loop_father
, 0);
4501 /* Debugging loops structure at tree level. */
4504 debug_loop_ir (void)
4506 print_loop_ir (stderr
);
4510 /* Return true if BB ends with a call, possibly followed by some
4511 instructions that must stay with the call. Return false,
4515 tree_block_ends_with_call_p (basic_block bb
)
4517 block_stmt_iterator bsi
= bsi_last (bb
);
4518 return get_call_expr_in (bsi_stmt (bsi
)) != NULL
;
4522 /* Return true if BB ends with a conditional branch. Return false,
4526 tree_block_ends_with_condjump_p (basic_block bb
)
4528 tree stmt
= tsi_stmt (bsi_last (bb
).tsi
);
4529 return (TREE_CODE (stmt
) == COND_EXPR
);
4533 /* Return true if we need to add fake edge to exit at statement T.
4534 Helper function for tree_flow_call_edges_add. */
4537 need_fake_edge_p (tree t
)
4541 /* NORETURN and LONGJMP calls already have an edge to exit.
4542 CONST, PURE and ALWAYS_RETURN calls do not need one.
4543 We don't currently check for CONST and PURE here, although
4544 it would be a good idea, because those attributes are
4545 figured out from the RTL in mark_constant_function, and
4546 the counter incrementation code from -fprofile-arcs
4547 leads to different results from -fbranch-probabilities. */
4548 call
= get_call_expr_in (t
);
4550 && !(call_expr_flags (call
) &
4551 (ECF_NORETURN
| ECF_LONGJMP
| ECF_ALWAYS_RETURN
)))
4554 if (TREE_CODE (t
) == ASM_EXPR
4555 && (ASM_VOLATILE_P (t
) || ASM_INPUT_P (t
)))
4562 /* Add fake edges to the function exit for any non constant and non
4563 noreturn calls, volatile inline assembly in the bitmap of blocks
4564 specified by BLOCKS or to the whole CFG if BLOCKS is zero. Return
4565 the number of blocks that were split.
4567 The goal is to expose cases in which entering a basic block does
4568 not imply that all subsequent instructions must be executed. */
4571 tree_flow_call_edges_add (sbitmap blocks
)
4574 int blocks_split
= 0;
4575 int last_bb
= last_basic_block
;
4576 bool check_last_block
= false;
4578 if (n_basic_blocks
== 0)
4582 check_last_block
= true;
4584 check_last_block
= TEST_BIT (blocks
, EXIT_BLOCK_PTR
->prev_bb
->index
);
4586 /* In the last basic block, before epilogue generation, there will be
4587 a fallthru edge to EXIT. Special care is required if the last insn
4588 of the last basic block is a call because make_edge folds duplicate
4589 edges, which would result in the fallthru edge also being marked
4590 fake, which would result in the fallthru edge being removed by
4591 remove_fake_edges, which would result in an invalid CFG.
4593 Moreover, we can't elide the outgoing fake edge, since the block
4594 profiler needs to take this into account in order to solve the minimal
4595 spanning tree in the case that the call doesn't return.
4597 Handle this by adding a dummy instruction in a new last basic block. */
4598 if (check_last_block
)
4600 basic_block bb
= EXIT_BLOCK_PTR
->prev_bb
;
4601 block_stmt_iterator bsi
= bsi_last (bb
);
4603 if (!bsi_end_p (bsi
))
4606 if (need_fake_edge_p (t
))
4610 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4611 if (e
->dest
== EXIT_BLOCK_PTR
)
4613 bsi_insert_on_edge (e
, build_empty_stmt ());
4614 bsi_commit_edge_inserts ((int *)NULL
);
4620 /* Now add fake edges to the function exit for any non constant
4621 calls since there is no way that we can determine if they will
4623 for (i
= 0; i
< last_bb
; i
++)
4625 basic_block bb
= BASIC_BLOCK (i
);
4626 block_stmt_iterator bsi
;
4627 tree stmt
, last_stmt
;
4632 if (blocks
&& !TEST_BIT (blocks
, i
))
4635 bsi
= bsi_last (bb
);
4636 if (!bsi_end_p (bsi
))
4638 last_stmt
= bsi_stmt (bsi
);
4641 stmt
= bsi_stmt (bsi
);
4642 if (need_fake_edge_p (stmt
))
4645 /* The handling above of the final block before the
4646 epilogue should be enough to verify that there is
4647 no edge to the exit block in CFG already.
4648 Calling make_edge in such case would cause us to
4649 mark that edge as fake and remove it later. */
4650 #ifdef ENABLE_CHECKING
4651 if (stmt
== last_stmt
)
4652 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4653 if (e
->dest
== EXIT_BLOCK_PTR
)
4657 /* Note that the following may create a new basic block
4658 and renumber the existing basic blocks. */
4659 if (stmt
!= last_stmt
)
4661 e
= split_block (bb
, stmt
);
4665 make_edge (bb
, EXIT_BLOCK_PTR
, EDGE_FAKE
);
4669 while (!bsi_end_p (bsi
));
4674 verify_flow_info ();
4676 return blocks_split
;
4680 tree_purge_dead_eh_edges (basic_block bb
)
4682 bool changed
= false;
4684 tree stmt
= last_stmt (bb
);
4686 if (stmt
&& tree_can_throw_internal (stmt
))
4689 for (e
= bb
->succ
; e
; e
= next
)
4691 next
= e
->succ_next
;
4692 if (e
->flags
& EDGE_EH
)
4694 ssa_remove_edge (e
);
4703 tree_purge_all_dead_eh_edges (bitmap blocks
)
4705 bool changed
= false;
4708 EXECUTE_IF_SET_IN_BITMAP (blocks
, 0, i
,
4709 { changed
|= tree_purge_dead_eh_edges (BASIC_BLOCK (i
)); });
4714 struct cfg_hooks tree_cfg_hooks
= {
4716 tree_verify_flow_info
,
4717 tree_dump_bb
, /* dump_bb */
4718 create_bb
, /* create_basic_block */
4719 tree_redirect_edge_and_branch
,/* redirect_edge_and_branch */
4720 tree_redirect_edge_and_branch_force
,/* redirect_edge_and_branch_force */
4721 remove_bb
, /* delete_basic_block */
4722 tree_split_block
, /* split_block */
4723 tree_move_block_after
, /* move_block_after */
4724 tree_can_merge_blocks_p
, /* can_merge_blocks_p */
4725 tree_merge_blocks
, /* merge_blocks */
4726 tree_predict_edge
, /* predict_edge */
4727 tree_predicted_by_p
, /* predicted_by_p */
4728 tree_can_duplicate_bb_p
, /* can_duplicate_block_p */
4729 tree_duplicate_bb
, /* duplicate_block */
4730 tree_split_edge
, /* split_edge */
4731 tree_make_forwarder_block
, /* make_forward_block */
4732 NULL
, /* tidy_fallthru_edge */
4733 tree_block_ends_with_call_p
, /* block_ends_with_call_p */
4734 tree_block_ends_with_condjump_p
, /* block_ends_with_condjump_p */
4735 tree_flow_call_edges_add
/* flow_call_edges_add */
4739 /* Split all critical edges. */
4742 split_critical_edges (void)
4749 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
4750 if (EDGE_CRITICAL_P (e
) && !(e
->flags
& EDGE_ABNORMAL
))
4757 struct tree_opt_pass pass_split_crit_edges
=
4759 "crited", /* name */
4761 split_critical_edges
, /* execute */
4764 0, /* static_pass_number */
4765 TV_TREE_SPLIT_EDGES
, /* tv_id */
4766 PROP_cfg
, /* properties required */
4767 PROP_no_crit_edges
, /* properties_provided */
4768 0, /* properties_destroyed */
4769 0, /* todo_flags_start */
4770 TODO_dump_func
, /* todo_flags_finish */
4775 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
4776 a temporary, make sure and register it to be renamed if necessary,
4777 and finally return the temporary. Put the statements to compute
4778 EXP before the current statement in BSI. */
4781 gimplify_val (block_stmt_iterator
*bsi
, tree type
, tree exp
)
4783 tree t
, new_stmt
, orig_stmt
;
4785 if (is_gimple_val (exp
))
4788 t
= make_rename_temp (type
, NULL
);
4789 new_stmt
= build (MODIFY_EXPR
, type
, t
, exp
);
4791 orig_stmt
= bsi_stmt (*bsi
);
4792 SET_EXPR_LOCUS (new_stmt
, EXPR_LOCUS (orig_stmt
));
4793 TREE_BLOCK (new_stmt
) = TREE_BLOCK (orig_stmt
);
4795 bsi_insert_before (bsi
, new_stmt
, BSI_SAME_STMT
);
4800 /* Build a ternary operation and gimplify it. Emit code before BSI.
4801 Return the gimple_val holding the result. */
4804 gimplify_build3 (block_stmt_iterator
*bsi
, enum tree_code code
,
4805 tree type
, tree a
, tree b
, tree c
)
4809 ret
= fold (build3 (code
, type
, a
, b
, c
));
4812 return gimplify_val (bsi
, type
, ret
);
4815 /* Build a binary operation and gimplify it. Emit code before BSI.
4816 Return the gimple_val holding the result. */
4819 gimplify_build2 (block_stmt_iterator
*bsi
, enum tree_code code
,
4820 tree type
, tree a
, tree b
)
4824 ret
= fold (build2 (code
, type
, a
, b
));
4827 return gimplify_val (bsi
, type
, ret
);
4830 /* Build a unary operation and gimplify it. Emit code before BSI.
4831 Return the gimple_val holding the result. */
4834 gimplify_build1 (block_stmt_iterator
*bsi
, enum tree_code code
, tree type
,
4839 ret
= fold (build1 (code
, type
, a
));
4842 return gimplify_val (bsi
, type
, ret
);
4847 /* Emit return warnings. */
4850 execute_warn_function_return (void)
4852 #ifdef USE_MAPPED_LOCATION
4853 source_location location
;
4860 if (warn_missing_noreturn
4861 && !TREE_THIS_VOLATILE (cfun
->decl
)
4862 && EXIT_BLOCK_PTR
->pred
== NULL
4863 && !lang_hooks
.function
.missing_noreturn_ok_p (cfun
->decl
))
4864 warning ("%Jfunction might be possible candidate for attribute `noreturn'",
4867 /* If we have a path to EXIT, then we do return. */
4868 if (TREE_THIS_VOLATILE (cfun
->decl
)
4869 && EXIT_BLOCK_PTR
->pred
!= NULL
)
4871 #ifdef USE_MAPPED_LOCATION
4872 location
= UNKNOWN_LOCATION
;
4876 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
4878 last
= last_stmt (e
->src
);
4879 if (TREE_CODE (last
) == RETURN_EXPR
4880 #ifdef USE_MAPPED_LOCATION
4881 && (location
= EXPR_LOCATION (last
)) != UNKNOWN_LOCATION
)
4883 && (locus
= EXPR_LOCUS (last
)) != NULL
)
4887 #ifdef USE_MAPPED_LOCATION
4888 if (location
== UNKNOWN_LOCATION
)
4889 location
= cfun
->function_end_locus
;
4890 warning ("%H`noreturn' function does return", &location
);
4893 locus
= &cfun
->function_end_locus
;
4894 warning ("%H`noreturn' function does return", locus
);
4898 /* If we see "return;" in some basic block, then we do reach the end
4899 without returning a value. */
4900 else if (warn_return_type
4901 && EXIT_BLOCK_PTR
->pred
!= NULL
4902 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun
->decl
))))
4904 for (e
= EXIT_BLOCK_PTR
->pred
; e
; e
= e
->pred_next
)
4906 tree last
= last_stmt (e
->src
);
4907 if (TREE_CODE (last
) == RETURN_EXPR
4908 && TREE_OPERAND (last
, 0) == NULL
)
4910 #ifdef USE_MAPPED_LOCATION
4911 location
= EXPR_LOCATION (last
);
4912 if (location
== UNKNOWN_LOCATION
)
4913 location
= cfun
->function_end_locus
;
4914 warning ("%Hcontrol reaches end of non-void function", &location
);
4916 locus
= EXPR_LOCUS (last
);
4918 locus
= &cfun
->function_end_locus
;
4919 warning ("%Hcontrol reaches end of non-void function", locus
);
4928 /* Given a basic block B which ends with a conditional and has
4929 precisely two successors, determine which of the edges is taken if
4930 the conditional is true and which is taken if the conditional is
4931 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */
4934 extract_true_false_edges_from_block (basic_block b
,
4940 if (e
->flags
& EDGE_TRUE_VALUE
)
4943 *false_edge
= e
->succ_next
;
4948 *true_edge
= e
->succ_next
;
4952 struct tree_opt_pass pass_warn_function_return
=
4956 execute_warn_function_return
, /* execute */
4959 0, /* static_pass_number */
4961 PROP_cfg
, /* properties_required */
4962 0, /* properties_provided */
4963 0, /* properties_destroyed */
4964 0, /* todo_flags_start */
4965 0, /* todo_flags_finish */
4969 #include "gt-tree-cfg.h"