1 /* Tree lowering pass. Lowers GIMPLE into unstructured form.
3 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "tree-gimple.h"
29 #include "tree-inline.h"
30 #include "diagnostic.h"
31 #include "langhooks.h"
32 #include "langhooks-def.h"
33 #include "tree-flow.h"
41 #include "tree-pass.h"
45 /* Block the current statement belongs to. */
48 /* A TREE_LIST of label and return statements to be moved to the end
50 tree return_statements
;
52 /* True if the function calls __builtin_setjmp. */
53 bool calls_builtin_setjmp
;
56 static void lower_stmt (tree_stmt_iterator
*, struct lower_data
*);
57 static void lower_bind_expr (tree_stmt_iterator
*, struct lower_data
*);
58 static void lower_cond_expr (tree_stmt_iterator
*, struct lower_data
*);
59 static void lower_return_expr (tree_stmt_iterator
*, struct lower_data
*);
60 static void lower_builtin_setjmp (tree_stmt_iterator
*);
62 /* Lower the body of current_function_decl. */
65 lower_function_body (void)
67 struct lower_data data
;
68 tree
*body_p
= &DECL_SAVED_TREE (current_function_decl
);
73 gcc_assert (TREE_CODE (bind
) == BIND_EXPR
);
75 memset (&data
, 0, sizeof (data
));
76 data
.block
= DECL_INITIAL (current_function_decl
);
77 BLOCK_SUBBLOCKS (data
.block
) = NULL_TREE
;
78 BLOCK_CHAIN (data
.block
) = NULL_TREE
;
79 TREE_ASM_WRITTEN (data
.block
) = 1;
81 *body_p
= alloc_stmt_list ();
82 i
= tsi_start (*body_p
);
83 tsi_link_after (&i
, bind
, TSI_NEW_STMT
);
84 lower_bind_expr (&i
, &data
);
86 i
= tsi_last (*body_p
);
88 /* If the function falls off the end, we need a null return statement.
89 If we've already got one in the return_statements list, we don't
90 need to do anything special. Otherwise build one by hand. */
91 if (block_may_fallthru (*body_p
)
92 && (data
.return_statements
== NULL
93 || TREE_OPERAND (TREE_VALUE (data
.return_statements
), 0) != NULL
))
95 x
= build1 (RETURN_EXPR
, void_type_node
, NULL
);
96 SET_EXPR_LOCATION (x
, cfun
->function_end_locus
);
97 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
100 /* If we lowered any return statements, emit the representative
101 at the end of the function. */
102 for (t
= data
.return_statements
; t
; t
= TREE_CHAIN (t
))
104 x
= build1 (LABEL_EXPR
, void_type_node
, TREE_PURPOSE (t
));
105 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
107 /* Remove the line number from the representative return statement.
108 It now fills in for many such returns. Failure to remove this
109 will result in incorrect results for coverage analysis. */
111 SET_EXPR_LOCATION (x
, UNKNOWN_LOCATION
);
112 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
115 /* If the function calls __builtin_setjmp, we need to emit the computed
116 goto that will serve as the unique dispatcher for all the receivers. */
117 if (data
.calls_builtin_setjmp
)
119 tree disp_label
, disp_var
, arg
;
121 /* Build 'DISP_LABEL:' and insert. */
122 disp_label
= create_artificial_label ();
123 /* This mark will create forward edges from every call site. */
124 DECL_NONLOCAL (disp_label
) = 1;
125 current_function_has_nonlocal_label
= 1;
126 x
= build1 (LABEL_EXPR
, void_type_node
, disp_label
);
127 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
129 /* Build 'DISP_VAR = __builtin_setjmp_dispatcher (DISP_LABEL);'
131 disp_var
= create_tmp_var (ptr_type_node
, "setjmpvar");
132 arg
= build_addr (disp_label
, current_function_decl
);
133 t
= implicit_built_in_decls
[BUILT_IN_SETJMP_DISPATCHER
];
134 t
= build_call_expr (t
, 1, arg
);
135 x
= build_gimple_modify_stmt (disp_var
, t
);
137 /* Build 'goto DISP_VAR;' and insert. */
138 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
139 x
= build1 (GOTO_EXPR
, void_type_node
, disp_var
);
140 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
143 gcc_assert (data
.block
== DECL_INITIAL (current_function_decl
));
144 BLOCK_SUBBLOCKS (data
.block
)
145 = blocks_nreverse (BLOCK_SUBBLOCKS (data
.block
));
147 clear_block_marks (data
.block
);
151 struct gimple_opt_pass pass_lower_cf
=
157 lower_function_body
, /* execute */
160 0, /* static_pass_number */
162 PROP_gimple_any
, /* properties_required */
163 PROP_gimple_lcf
, /* properties_provided */
164 0, /* properties_destroyed */
165 0, /* todo_flags_start */
166 TODO_dump_func
/* todo_flags_finish */
171 /* Lower the EXPR. Unlike gimplification the statements are not relowered
172 when they are changed -- if this has to be done, the lowering routine must
173 do it explicitly. DATA is passed through the recursion. */
176 lower_stmt_body (tree expr
, struct lower_data
*data
)
178 tree_stmt_iterator tsi
;
180 for (tsi
= tsi_start (expr
); !tsi_end_p (tsi
); )
181 lower_stmt (&tsi
, data
);
185 /* Lower the OpenMP directive statement pointed by TSI. DATA is
186 passed through the recursion. */
189 lower_omp_directive (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
193 stmt
= tsi_stmt (*tsi
);
195 lower_stmt_body (OMP_BODY (stmt
), data
);
196 tsi_link_before (tsi
, stmt
, TSI_SAME_STMT
);
197 tsi_link_before (tsi
, OMP_BODY (stmt
), TSI_SAME_STMT
);
198 OMP_BODY (stmt
) = NULL_TREE
;
203 /* Lower statement TSI. DATA is passed through the recursion. */
206 lower_stmt (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
208 tree stmt
= tsi_stmt (*tsi
);
210 if (EXPR_HAS_LOCATION (stmt
) && data
)
211 TREE_BLOCK (stmt
) = data
->block
;
213 switch (TREE_CODE (stmt
))
216 lower_bind_expr (tsi
, data
);
219 lower_cond_expr (tsi
, data
);
222 lower_return_expr (tsi
, data
);
225 case TRY_FINALLY_EXPR
:
227 lower_stmt_body (TREE_OPERAND (stmt
, 0), data
);
228 lower_stmt_body (TREE_OPERAND (stmt
, 1), data
);
231 lower_stmt_body (CATCH_BODY (stmt
), data
);
234 lower_stmt_body (EH_FILTER_FAILURE (stmt
), data
);
243 case CHANGE_DYNAMIC_TYPE_EXPR
:
246 case OMP_SECTIONS_SWITCH
:
253 case OMP_ATOMIC_LOAD
:
254 case OMP_ATOMIC_STORE
:
258 case GIMPLE_MODIFY_STMT
:
259 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CALL_EXPR
)
260 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
267 tree decl
= get_callee_fndecl (stmt
);
269 && DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
270 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_SETJMP
)
272 data
->calls_builtin_setjmp
= true;
273 lower_builtin_setjmp (tsi
);
280 lower_omp_directive (tsi
, data
);
290 /* Lower a bind_expr TSI. DATA is passed through the recursion. */
293 lower_bind_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
295 tree old_block
= data
->block
;
296 tree stmt
= tsi_stmt (*tsi
);
297 tree new_block
= BIND_EXPR_BLOCK (stmt
);
301 if (new_block
== old_block
)
303 /* The outermost block of the original function may not be the
304 outermost statement chain of the gimplified function. So we
305 may see the outermost block just inside the function. */
306 gcc_assert (new_block
== DECL_INITIAL (current_function_decl
));
311 /* We do not expect to handle duplicate blocks. */
312 gcc_assert (!TREE_ASM_WRITTEN (new_block
));
313 TREE_ASM_WRITTEN (new_block
) = 1;
315 /* Block tree may get clobbered by inlining. Normally this would
316 be fixed in rest_of_decl_compilation using block notes, but
317 since we are not going to emit them, it is up to us. */
318 BLOCK_CHAIN (new_block
) = BLOCK_SUBBLOCKS (old_block
);
319 BLOCK_SUBBLOCKS (old_block
) = new_block
;
320 BLOCK_SUBBLOCKS (new_block
) = NULL_TREE
;
321 BLOCK_SUPERCONTEXT (new_block
) = old_block
;
323 data
->block
= new_block
;
327 record_vars (BIND_EXPR_VARS (stmt
));
328 lower_stmt_body (BIND_EXPR_BODY (stmt
), data
);
332 gcc_assert (data
->block
== new_block
);
334 BLOCK_SUBBLOCKS (new_block
)
335 = blocks_nreverse (BLOCK_SUBBLOCKS (new_block
));
336 data
->block
= old_block
;
339 /* The BIND_EXPR no longer carries any useful information -- kill it. */
340 tsi_link_before (tsi
, BIND_EXPR_BODY (stmt
), TSI_SAME_STMT
);
344 /* Try to determine whether a TRY_CATCH expression can fall through.
345 This is a subroutine of block_may_fallthru. */
348 try_catch_may_fallthru (const_tree stmt
)
350 tree_stmt_iterator i
;
352 /* If the TRY block can fall through, the whole TRY_CATCH can
354 if (block_may_fallthru (TREE_OPERAND (stmt
, 0)))
357 i
= tsi_start (TREE_OPERAND (stmt
, 1));
358 switch (TREE_CODE (tsi_stmt (i
)))
361 /* We expect to see a sequence of CATCH_EXPR trees, each with a
362 catch expression and a body. The whole TRY_CATCH may fall
363 through iff any of the catch bodies falls through. */
364 for (; !tsi_end_p (i
); tsi_next (&i
))
366 if (block_may_fallthru (CATCH_BODY (tsi_stmt (i
))))
372 /* The exception filter expression only matters if there is an
373 exception. If the exception does not match EH_FILTER_TYPES,
374 we will execute EH_FILTER_FAILURE, and we will fall through
375 if that falls through. If the exception does match
376 EH_FILTER_TYPES, the stack unwinder will continue up the
377 stack, so we will not fall through. We don't know whether we
378 will throw an exception which matches EH_FILTER_TYPES or not,
379 so we just ignore EH_FILTER_TYPES and assume that we might
380 throw an exception which doesn't match. */
381 return block_may_fallthru (EH_FILTER_FAILURE (tsi_stmt (i
)));
384 /* This case represents statements to be executed when an
385 exception occurs. Those statements are implicitly followed
386 by a RESX_EXPR to resume execution after the exception. So
387 in this case the TRY_CATCH never falls through. */
392 /* Try to determine if we can fall out of the bottom of BLOCK. This guess
393 need not be 100% accurate; simply be conservative and return true if we
394 don't know. This is used only to avoid stupidly generating extra code.
395 If we're wrong, we'll just delete the extra code later. */
398 block_may_fallthru (const_tree block
)
400 /* This CONST_CAST is okay because expr_last returns it's argument
401 unmodified and we assign it to a const_tree. */
402 const_tree stmt
= expr_last (CONST_CAST_TREE(block
));
404 switch (stmt
? TREE_CODE (stmt
) : ERROR_MARK
)
409 /* Easy cases. If the last statement of the block implies
410 control transfer, then we can't fall through. */
414 /* If SWITCH_LABELS is set, this is lowered, and represents a
415 branch to a selected label and hence can not fall through.
416 Otherwise SWITCH_BODY is set, and the switch can fall
418 return SWITCH_LABELS (stmt
) == NULL_TREE
;
421 if (block_may_fallthru (COND_EXPR_THEN (stmt
)))
423 return block_may_fallthru (COND_EXPR_ELSE (stmt
));
426 return block_may_fallthru (BIND_EXPR_BODY (stmt
));
429 return try_catch_may_fallthru (stmt
);
431 case TRY_FINALLY_EXPR
:
432 /* The finally clause is always executed after the try clause,
433 so if it does not fall through, then the try-finally will not
434 fall through. Otherwise, if the try clause does not fall
435 through, then when the finally clause falls through it will
436 resume execution wherever the try clause was going. So the
437 whole try-finally will only fall through if both the try
438 clause and the finally clause fall through. */
439 return (block_may_fallthru (TREE_OPERAND (stmt
, 0))
440 && block_may_fallthru (TREE_OPERAND (stmt
, 1)));
442 case GIMPLE_MODIFY_STMT
:
443 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CALL_EXPR
)
444 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
450 /* Functions that do not return do not fall through. */
451 return (call_expr_flags (stmt
) & ECF_NORETURN
) == 0;
453 case CLEANUP_POINT_EXPR
:
454 return block_may_fallthru (TREE_OPERAND (stmt
, 0));
461 /* Lower a cond_expr TSI. DATA is passed through the recursion. */
464 lower_cond_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
466 tree stmt
= tsi_stmt (*tsi
);
467 bool then_is_goto
, else_is_goto
;
468 tree then_branch
, else_branch
;
469 tree then_goto
, else_goto
;
471 then_branch
= COND_EXPR_THEN (stmt
);
472 else_branch
= COND_EXPR_ELSE (stmt
);
474 lower_stmt_body (then_branch
, data
);
475 lower_stmt_body (else_branch
, data
);
477 then_goto
= expr_only (then_branch
);
478 then_is_goto
= then_goto
&& simple_goto_p (then_goto
);
480 else_goto
= expr_only (else_branch
);
481 else_is_goto
= else_goto
&& simple_goto_p (else_goto
);
483 if (!then_is_goto
|| !else_is_goto
)
485 tree then_label
, else_label
, end_label
, t
;
487 then_label
= NULL_TREE
;
488 else_label
= NULL_TREE
;
489 end_label
= NULL_TREE
;
491 /* Replace the cond_expr with explicit gotos. */
494 t
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
495 if (TREE_SIDE_EFFECTS (then_branch
))
499 then_goto
= build_and_jump (&LABEL_EXPR_LABEL (t
));
504 t
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
505 if (TREE_SIDE_EFFECTS (else_branch
))
509 /* Both THEN and ELSE can be no-ops if one or both contained an
510 empty BIND_EXPR that was associated with the toplevel block
511 of an inlined function. In that case remove_useless_stmts
512 can't have cleaned things up for us; kill the whole
522 else_goto
= build_and_jump (&LABEL_EXPR_LABEL (t
));
527 bool may_fallthru
= block_may_fallthru (then_branch
);
529 tsi_link_after (tsi
, then_label
, TSI_CONTINUE_LINKING
);
530 tsi_link_after (tsi
, then_branch
, TSI_CONTINUE_LINKING
);
532 if (else_label
&& may_fallthru
)
534 end_label
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
535 t
= build_and_jump (&LABEL_EXPR_LABEL (end_label
));
536 tsi_link_after (tsi
, t
, TSI_CONTINUE_LINKING
);
542 tsi_link_after (tsi
, else_label
, TSI_CONTINUE_LINKING
);
543 tsi_link_after (tsi
, else_branch
, TSI_CONTINUE_LINKING
);
547 tsi_link_after (tsi
, end_label
, TSI_CONTINUE_LINKING
);
550 COND_EXPR_THEN (stmt
) = then_goto
;
551 COND_EXPR_ELSE (stmt
) = else_goto
;
556 /* Lower a return_expr TSI. DATA is passed through the recursion. */
559 lower_return_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
561 tree stmt
= tsi_stmt (*tsi
);
562 tree value
, t
, label
;
564 /* Extract the value being returned. */
565 value
= TREE_OPERAND (stmt
, 0);
566 if (value
&& TREE_CODE (value
) == GIMPLE_MODIFY_STMT
)
567 value
= GIMPLE_STMT_OPERAND (value
, 1);
569 /* Match this up with an existing return statement that's been created. */
570 for (t
= data
->return_statements
; t
; t
= TREE_CHAIN (t
))
572 tree tvalue
= TREE_OPERAND (TREE_VALUE (t
), 0);
573 if (tvalue
&& TREE_CODE (tvalue
) == GIMPLE_MODIFY_STMT
)
574 tvalue
= GIMPLE_STMT_OPERAND (tvalue
, 1);
578 label
= TREE_PURPOSE (t
);
583 /* Not found. Create a new label and record the return statement. */
584 label
= create_artificial_label ();
585 data
->return_statements
= tree_cons (label
, stmt
, data
->return_statements
);
587 /* Generate a goto statement and remove the return statement. */
589 t
= build1 (GOTO_EXPR
, void_type_node
, label
);
590 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
591 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
595 /* Lower a __builtin_setjmp TSI.
597 __builtin_setjmp is passed a pointer to an array of five words (not
598 all will be used on all machines). It operates similarly to the C
599 library function of the same name, but is more efficient.
601 It is lowered into 3 other builtins, namely __builtin_setjmp_setup,
602 __builtin_setjmp_dispatcher and __builtin_setjmp_receiver, but with
603 __builtin_setjmp_dispatcher shared among all the instances; that's
604 why it is only emitted at the end by lower_function_body.
606 After full lowering, the body of the function should look like:
615 __builtin_setjmp_setup (&buf, &<D1847>);
619 __builtin_setjmp_receiver (&<D1847>);
622 if (D.1844 == 0) goto <D1848>; else goto <D1849>;
626 __builtin_setjmp_setup (&buf, &<D2847>);
630 __builtin_setjmp_receiver (&<D2847>);
633 if (D.2844 == 0) goto <D2848>; else goto <D2849>;
639 <D3853>: [non-local];
640 setjmpvar.0 = __builtin_setjmp_dispatcher (&<D3853>);
644 The dispatcher block will be both the unique destination of all the
645 abnormal call edges and the unique source of all the abnormal edges
646 to the receivers, thus keeping the complexity explosion localized. */
649 lower_builtin_setjmp (tree_stmt_iterator
*tsi
)
651 tree stmt
= tsi_stmt (*tsi
);
652 tree cont_label
= create_artificial_label ();
653 tree next_label
= create_artificial_label ();
656 /* NEXT_LABEL is the label __builtin_longjmp will jump to. Its address is
657 passed to both __builtin_setjmp_setup and __builtin_setjmp_receiver. */
658 FORCED_LABEL (next_label
) = 1;
660 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
662 dest
= GIMPLE_STMT_OPERAND (stmt
, 0);
663 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
668 /* Build '__builtin_setjmp_setup (BUF, NEXT_LABEL)' and insert. */
669 arg
= build_addr (next_label
, current_function_decl
);
670 t
= implicit_built_in_decls
[BUILT_IN_SETJMP_SETUP
];
671 t
= build_call_expr (t
, 2, CALL_EXPR_ARG (stmt
, 0), arg
);
672 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
673 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
675 /* Build 'DEST = 0' and insert. */
678 t
= build_gimple_modify_stmt (dest
, fold_convert (TREE_TYPE (dest
),
680 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
681 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
684 /* Build 'goto CONT_LABEL' and insert. */
685 t
= build1 (GOTO_EXPR
, void_type_node
, cont_label
);
686 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
688 /* Build 'NEXT_LABEL:' and insert. */
689 t
= build1 (LABEL_EXPR
, void_type_node
, next_label
);
690 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
692 /* Build '__builtin_setjmp_receiver (NEXT_LABEL)' and insert. */
693 arg
= build_addr (next_label
, current_function_decl
);
694 t
= implicit_built_in_decls
[BUILT_IN_SETJMP_RECEIVER
];
695 t
= build_call_expr (t
, 1, arg
);
696 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
697 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
699 /* Build 'DEST = 1' and insert. */
702 t
= build_gimple_modify_stmt (dest
, fold_convert (TREE_TYPE (dest
),
704 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
705 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
708 /* Build 'CONT_LABEL:' and insert. */
709 t
= build1 (LABEL_EXPR
, void_type_node
, cont_label
);
710 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
712 /* Remove the call to __builtin_setjmp. */
717 /* Record the variables in VARS into function FN. */
720 record_vars_into (tree vars
, tree fn
)
722 if (fn
!= current_function_decl
)
723 push_cfun (DECL_STRUCT_FUNCTION (fn
));
725 for (; vars
; vars
= TREE_CHAIN (vars
))
729 /* BIND_EXPRs contains also function/type/constant declarations
730 we don't need to care about. */
731 if (TREE_CODE (var
) != VAR_DECL
)
734 /* Nothing to do in this case. */
735 if (DECL_EXTERNAL (var
))
738 /* Record the variable. */
739 cfun
->unexpanded_var_list
= tree_cons (NULL_TREE
, var
,
740 cfun
->unexpanded_var_list
);
743 if (fn
!= current_function_decl
)
748 /* Record the variables in VARS into current_function_decl. */
751 record_vars (tree vars
)
753 record_vars_into (vars
, current_function_decl
);
757 /* Mark BLOCK used if it has a used variable in it, then recurse over its
761 mark_blocks_with_used_vars (tree block
)
766 if (!TREE_USED (block
))
768 for (var
= BLOCK_VARS (block
);
770 var
= TREE_CHAIN (var
))
774 TREE_USED (block
) = true;
779 for (subblock
= BLOCK_SUBBLOCKS (block
);
781 subblock
= BLOCK_CHAIN (subblock
))
782 mark_blocks_with_used_vars (subblock
);
785 /* Mark the used attribute on blocks correctly. */
788 mark_used_blocks (void)
790 mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl
));
795 struct gimple_opt_pass pass_mark_used_blocks
=
801 mark_used_blocks
, /* execute */
804 0, /* static_pass_number */
806 0, /* properties_required */
807 0, /* properties_provided */
808 0, /* properties_destroyed */
809 0, /* todo_flags_start */
810 TODO_dump_func
/* todo_flags_finish */