1 /* Tree lowering pass. Lowers GIMPLE into unstructured form.
3 Copyright (C) 2003, 2005 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
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 the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
29 #include "tree-gimple.h"
30 #include "tree-inline.h"
31 #include "diagnostic.h"
32 #include "langhooks.h"
33 #include "langhooks-def.h"
34 #include "tree-flow.h"
42 #include "tree-pass.h"
46 /* Block the current statement belongs to. */
49 /* A TREE_LIST of label and return statements to be moved to the end
51 tree return_statements
;
54 static void lower_stmt (tree_stmt_iterator
*, struct lower_data
*);
55 static void lower_bind_expr (tree_stmt_iterator
*, struct lower_data
*);
56 static void lower_cond_expr (tree_stmt_iterator
*, struct lower_data
*);
57 static void lower_return_expr (tree_stmt_iterator
*, struct lower_data
*);
59 /* Lowers the body of current_function_decl. */
62 lower_function_body (void)
64 struct lower_data data
;
65 tree
*body_p
= &DECL_SAVED_TREE (current_function_decl
);
70 gcc_assert (TREE_CODE (bind
) == BIND_EXPR
);
72 memset (&data
, 0, sizeof (data
));
73 data
.block
= DECL_INITIAL (current_function_decl
);
74 BLOCK_SUBBLOCKS (data
.block
) = NULL_TREE
;
75 BLOCK_CHAIN (data
.block
) = NULL_TREE
;
76 TREE_ASM_WRITTEN (data
.block
) = 1;
78 *body_p
= alloc_stmt_list ();
79 i
= tsi_start (*body_p
);
80 tsi_link_after (&i
, bind
, TSI_NEW_STMT
);
81 lower_bind_expr (&i
, &data
);
83 i
= tsi_last (*body_p
);
85 /* If the function falls off the end, we need a null return statement.
86 If we've already got one in the return_statements list, we don't
87 need to do anything special. Otherwise build one by hand. */
88 if (block_may_fallthru (*body_p
)
89 && (data
.return_statements
== NULL
90 || TREE_OPERAND (TREE_VALUE (data
.return_statements
), 0) != NULL
))
92 x
= build1 (RETURN_EXPR
, void_type_node
, NULL
);
93 SET_EXPR_LOCATION (x
, cfun
->function_end_locus
);
94 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
97 /* If we lowered any return statements, emit the representative
98 at the end of the function. */
99 for (t
= data
.return_statements
; t
; t
= TREE_CHAIN (t
))
101 x
= build1 (LABEL_EXPR
, void_type_node
, TREE_PURPOSE (t
));
102 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
104 /* Remove the line number from the representative return statement.
105 It now fills in for many such returns. Failure to remove this
106 will result in incorrect results for coverage analysis. */
108 #ifdef USE_MAPPED_LOCATION
109 SET_EXPR_LOCATION (x
, UNKNOWN_LOCATION
);
111 SET_EXPR_LOCUS (x
, NULL
);
113 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
116 gcc_assert (data
.block
== DECL_INITIAL (current_function_decl
));
117 BLOCK_SUBBLOCKS (data
.block
)
118 = blocks_nreverse (BLOCK_SUBBLOCKS (data
.block
));
120 clear_block_marks (data
.block
);
123 struct tree_opt_pass pass_lower_cf
=
127 lower_function_body
, /* execute */
130 0, /* static_pass_number */
132 PROP_gimple_any
, /* properties_required */
133 PROP_gimple_lcf
, /* properties_provided */
134 PROP_gimple_any
, /* properties_destroyed */
135 0, /* todo_flags_start */
136 TODO_dump_func
, /* todo_flags_finish */
141 /* Lowers the EXPR. Unlike gimplification the statements are not relowered
142 when they are changed -- if this has to be done, the lowering routine must
143 do it explicitly. DATA is passed through the recursion. */
146 lower_stmt_body (tree expr
, struct lower_data
*data
)
148 tree_stmt_iterator tsi
;
150 for (tsi
= tsi_start (expr
); !tsi_end_p (tsi
); )
151 lower_stmt (&tsi
, data
);
155 /* Lower the OpenMP directive statement pointed by TSI. DATA is
156 passed through the recursion. */
159 lower_omp_directive (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
163 stmt
= tsi_stmt (*tsi
);
165 clause
= (TREE_CODE (stmt
) >= OMP_PARALLEL
&& TREE_CODE (stmt
) <= OMP_SINGLE
)
169 lower_stmt_body (OMP_BODY (stmt
), data
);
170 tsi_link_before (tsi
, stmt
, TSI_SAME_STMT
);
171 tsi_link_before (tsi
, OMP_BODY (stmt
), TSI_SAME_STMT
);
172 OMP_BODY (stmt
) = NULL_TREE
;
177 /* Lowers statement TSI. DATA is passed through the recursion. */
180 lower_stmt (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
182 tree stmt
= tsi_stmt (*tsi
);
184 if (EXPR_HAS_LOCATION (stmt
) && data
)
185 TREE_BLOCK (stmt
) = data
->block
;
187 switch (TREE_CODE (stmt
))
190 lower_bind_expr (tsi
, data
);
193 lower_cond_expr (tsi
, data
);
196 lower_return_expr (tsi
, data
);
199 case TRY_FINALLY_EXPR
:
201 lower_stmt_body (TREE_OPERAND (stmt
, 0), data
);
202 lower_stmt_body (TREE_OPERAND (stmt
, 1), data
);
205 lower_stmt_body (CATCH_BODY (stmt
), data
);
208 lower_stmt_body (EH_FILTER_FAILURE (stmt
), data
);
218 case OMP_RETURN_EXPR
:
229 lower_omp_directive (tsi
, data
);
239 /* Lowers a bind_expr TSI. DATA is passed through the recursion. */
242 lower_bind_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
244 tree old_block
= data
->block
;
245 tree stmt
= tsi_stmt (*tsi
);
246 tree new_block
= BIND_EXPR_BLOCK (stmt
);
250 if (new_block
== old_block
)
252 /* The outermost block of the original function may not be the
253 outermost statement chain of the gimplified function. So we
254 may see the outermost block just inside the function. */
255 gcc_assert (new_block
== DECL_INITIAL (current_function_decl
));
260 /* We do not expect to handle duplicate blocks. */
261 gcc_assert (!TREE_ASM_WRITTEN (new_block
));
262 TREE_ASM_WRITTEN (new_block
) = 1;
264 /* Block tree may get clobbered by inlining. Normally this would
265 be fixed in rest_of_decl_compilation using block notes, but
266 since we are not going to emit them, it is up to us. */
267 BLOCK_CHAIN (new_block
) = BLOCK_SUBBLOCKS (old_block
);
268 BLOCK_SUBBLOCKS (old_block
) = new_block
;
269 BLOCK_SUBBLOCKS (new_block
) = NULL_TREE
;
270 BLOCK_SUPERCONTEXT (new_block
) = old_block
;
272 data
->block
= new_block
;
276 record_vars (BIND_EXPR_VARS (stmt
));
277 lower_stmt_body (BIND_EXPR_BODY (stmt
), data
);
281 gcc_assert (data
->block
== new_block
);
283 BLOCK_SUBBLOCKS (new_block
)
284 = blocks_nreverse (BLOCK_SUBBLOCKS (new_block
));
285 data
->block
= old_block
;
288 /* The BIND_EXPR no longer carries any useful information -- kill it. */
289 tsi_link_before (tsi
, BIND_EXPR_BODY (stmt
), TSI_SAME_STMT
);
293 /* Try to determine whether a TRY_CATCH expression can fall through.
294 This is a subroutine of block_may_fallthru. */
297 try_catch_may_fallthru (tree stmt
)
299 tree_stmt_iterator i
;
301 /* If the TRY block can fall through, the whole TRY_CATCH can
303 if (block_may_fallthru (TREE_OPERAND (stmt
, 0)))
306 i
= tsi_start (TREE_OPERAND (stmt
, 1));
307 switch (TREE_CODE (tsi_stmt (i
)))
310 /* We expect to see a sequence of CATCH_EXPR trees, each with a
311 catch expression and a body. The whole TRY_CATCH may fall
312 through iff any of the catch bodies falls through. */
313 for (; !tsi_end_p (i
); tsi_next (&i
))
315 if (block_may_fallthru (CATCH_BODY (tsi_stmt (i
))))
321 /* The exception filter expression only matters if there is an
322 exception. If the exception does not match EH_FILTER_TYPES,
323 we will execute EH_FILTER_FAILURE, and we will fall through
324 if that falls through. If the exception does match
325 EH_FILTER_TYPES, the stack unwinder will continue up the
326 stack, so we will not fall through. We don't know whether we
327 will throw an exception which matches EH_FILTER_TYPES or not,
328 so we just ignore EH_FILTER_TYPES and assume that we might
329 throw an exception which doesn't match. */
330 return block_may_fallthru (EH_FILTER_FAILURE (tsi_stmt (i
)));
333 /* This case represents statements to be executed when an
334 exception occurs. Those statements are implicitly followed
335 by a RESX_EXPR to resume execution after the exception. So
336 in this case the TRY_CATCH never falls through. */
341 /* Try to determine if we can fall out of the bottom of BLOCK. This guess
342 need not be 100% accurate; simply be conservative and return true if we
343 don't know. This is used only to avoid stupidly generating extra code.
344 If we're wrong, we'll just delete the extra code later. */
347 block_may_fallthru (tree block
)
349 tree stmt
= expr_last (block
);
351 switch (stmt
? TREE_CODE (stmt
) : ERROR_MARK
)
356 /* Easy cases. If the last statement of the block implies
357 control transfer, then we can't fall through. */
361 /* If SWITCH_LABELS is set, this is lowered, and represents a
362 branch to a selected label and hence can not fall through.
363 Otherwise SWITCH_BODY is set, and the switch can fall
365 return SWITCH_LABELS (stmt
) == NULL_TREE
;
368 if (block_may_fallthru (COND_EXPR_THEN (stmt
)))
370 return block_may_fallthru (COND_EXPR_ELSE (stmt
));
373 return block_may_fallthru (BIND_EXPR_BODY (stmt
));
376 return try_catch_may_fallthru (stmt
);
378 case TRY_FINALLY_EXPR
:
379 /* The finally clause is always executed after the try clause,
380 so if it does not fall through, then the try-finally will not
381 fall through. Otherwise, if the try clause does not fall
382 through, then when the finally clause falls through it will
383 resume execution wherever the try clause was going. So the
384 whole try-finally will only fall through if both the try
385 clause and the finally clause fall through. */
386 return (block_may_fallthru (TREE_OPERAND (stmt
, 0))
387 && block_may_fallthru (TREE_OPERAND (stmt
, 1)));
390 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == CALL_EXPR
)
391 stmt
= TREE_OPERAND (stmt
, 1);
397 /* Functions that do not return do not fall through. */
398 return (call_expr_flags (stmt
) & ECF_NORETURN
) == 0;
400 case CLEANUP_POINT_EXPR
:
401 return block_may_fallthru (TREE_OPERAND (stmt
, 0));
408 /* Lowers a cond_expr TSI. DATA is passed through the recursion. */
411 lower_cond_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
413 tree stmt
= tsi_stmt (*tsi
);
414 bool then_is_goto
, else_is_goto
;
415 tree then_branch
, else_branch
;
416 tree then_goto
, else_goto
;
418 then_branch
= COND_EXPR_THEN (stmt
);
419 else_branch
= COND_EXPR_ELSE (stmt
);
421 lower_stmt_body (then_branch
, data
);
422 lower_stmt_body (else_branch
, data
);
424 then_goto
= expr_only (then_branch
);
425 then_is_goto
= then_goto
&& simple_goto_p (then_goto
);
427 else_goto
= expr_only (else_branch
);
428 else_is_goto
= else_goto
&& simple_goto_p (else_goto
);
430 if (!then_is_goto
|| !else_is_goto
)
432 tree then_label
, else_label
, end_label
, t
;
434 then_label
= NULL_TREE
;
435 else_label
= NULL_TREE
;
436 end_label
= NULL_TREE
;
438 /* Replace the cond_expr with explicit gotos. */
441 t
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
442 if (TREE_SIDE_EFFECTS (then_branch
))
446 then_goto
= build_and_jump (&LABEL_EXPR_LABEL (t
));
451 t
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
452 if (TREE_SIDE_EFFECTS (else_branch
))
456 /* Both THEN and ELSE can be no-ops if one or both contained an
457 empty BIND_EXPR that was associated with the toplevel block
458 of an inlined function. In that case remove_useless_stmts
459 can't have cleaned things up for us; kill the whole
469 else_goto
= build_and_jump (&LABEL_EXPR_LABEL (t
));
474 bool may_fallthru
= block_may_fallthru (then_branch
);
476 tsi_link_after (tsi
, then_label
, TSI_CONTINUE_LINKING
);
477 tsi_link_after (tsi
, then_branch
, TSI_CONTINUE_LINKING
);
479 if (else_label
&& may_fallthru
)
481 end_label
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
482 t
= build_and_jump (&LABEL_EXPR_LABEL (end_label
));
483 tsi_link_after (tsi
, t
, TSI_CONTINUE_LINKING
);
489 tsi_link_after (tsi
, else_label
, TSI_CONTINUE_LINKING
);
490 tsi_link_after (tsi
, else_branch
, TSI_CONTINUE_LINKING
);
494 tsi_link_after (tsi
, end_label
, TSI_CONTINUE_LINKING
);
497 COND_EXPR_THEN (stmt
) = then_goto
;
498 COND_EXPR_ELSE (stmt
) = else_goto
;
504 lower_return_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
506 tree stmt
= tsi_stmt (*tsi
);
507 tree value
, t
, label
;
509 /* Extract the value being returned. */
510 value
= TREE_OPERAND (stmt
, 0);
511 if (value
&& TREE_CODE (value
) == MODIFY_EXPR
)
512 value
= TREE_OPERAND (value
, 1);
514 /* Match this up with an existing return statement that's been created. */
515 for (t
= data
->return_statements
; t
; t
= TREE_CHAIN (t
))
517 tree tvalue
= TREE_OPERAND (TREE_VALUE (t
), 0);
518 if (tvalue
&& TREE_CODE (tvalue
) == MODIFY_EXPR
)
519 tvalue
= TREE_OPERAND (tvalue
, 1);
523 label
= TREE_PURPOSE (t
);
528 /* Not found. Create a new label and record the return statement. */
529 label
= create_artificial_label ();
530 data
->return_statements
= tree_cons (label
, stmt
, data
->return_statements
);
532 /* Generate a goto statement and remove the return statement. */
534 t
= build1 (GOTO_EXPR
, void_type_node
, label
);
535 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
536 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
541 /* Record the variables in VARS into function FN. */
544 record_vars_into (tree vars
, tree fn
)
546 struct function
*saved_cfun
= cfun
;
548 if (fn
!= current_function_decl
)
549 cfun
= DECL_STRUCT_FUNCTION (fn
);
551 for (; vars
; vars
= TREE_CHAIN (vars
))
555 /* BIND_EXPRs contains also function/type/constant declarations
556 we don't need to care about. */
557 if (TREE_CODE (var
) != VAR_DECL
)
560 /* Nothing to do in this case. */
561 if (DECL_EXTERNAL (var
))
564 /* Record the variable. */
565 cfun
->unexpanded_var_list
= tree_cons (NULL_TREE
, var
,
566 cfun
->unexpanded_var_list
);
569 if (fn
!= current_function_decl
)
574 /* Record the variables in VARS into current_function_decl. */
577 record_vars (tree vars
)
579 record_vars_into (vars
, current_function_decl
);
583 /* Mark BLOCK used if it has a used variable in it, then recurse over its
587 mark_blocks_with_used_vars (tree block
)
592 if (!TREE_USED (block
))
594 for (var
= BLOCK_VARS (block
);
596 var
= TREE_CHAIN (var
))
600 TREE_USED (block
) = true;
605 for (subblock
= BLOCK_SUBBLOCKS (block
);
607 subblock
= BLOCK_CHAIN (subblock
))
608 mark_blocks_with_used_vars (subblock
);
611 /* Mark the used attribute on blocks correctly. */
614 mark_used_blocks (void)
616 mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl
));
620 struct tree_opt_pass pass_mark_used_blocks
=
624 mark_used_blocks
, /* execute */
627 0, /* static_pass_number */
629 0, /* properties_required */
630 0, /* properties_provided */
631 0, /* properties_destroyed */
632 0, /* todo_flags_start */
633 TODO_dump_func
, /* todo_flags_finish */