1 /* Tree lowering pass. Lowers GIMPLE into unstructured form.
3 Copyright (C) 2003, 2004, 2005, 2006, 2007 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 #ifdef USE_MAPPED_LOCATION
112 SET_EXPR_LOCATION (x
, UNKNOWN_LOCATION
);
114 SET_EXPR_LOCUS (x
, NULL
);
116 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
119 /* If the function calls __builtin_setjmp, we need to emit the computed
120 goto that will serve as the unique dispatcher for all the receivers. */
121 if (data
.calls_builtin_setjmp
)
123 tree disp_label
, disp_var
, arg
;
125 /* Build 'DISP_LABEL:' and insert. */
126 disp_label
= create_artificial_label ();
127 /* This mark will create forward edges from every call site. */
128 DECL_NONLOCAL (disp_label
) = 1;
129 current_function_has_nonlocal_label
= 1;
130 x
= build1 (LABEL_EXPR
, void_type_node
, disp_label
);
131 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
133 /* Build 'DISP_VAR = __builtin_setjmp_dispatcher (DISP_LABEL);'
135 disp_var
= create_tmp_var (ptr_type_node
, "setjmpvar");
136 arg
= build_addr (disp_label
, current_function_decl
);
137 t
= implicit_built_in_decls
[BUILT_IN_SETJMP_DISPATCHER
];
138 t
= build_call_expr (t
, 1, arg
);
139 x
= build_gimple_modify_stmt (disp_var
, t
);
141 /* Build 'goto DISP_VAR;' and insert. */
142 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
143 x
= build1 (GOTO_EXPR
, void_type_node
, disp_var
);
144 tsi_link_after (&i
, x
, TSI_CONTINUE_LINKING
);
147 gcc_assert (data
.block
== DECL_INITIAL (current_function_decl
));
148 BLOCK_SUBBLOCKS (data
.block
)
149 = blocks_nreverse (BLOCK_SUBBLOCKS (data
.block
));
151 clear_block_marks (data
.block
);
155 struct tree_opt_pass pass_lower_cf
=
159 lower_function_body
, /* execute */
162 0, /* static_pass_number */
164 PROP_gimple_any
, /* properties_required */
165 PROP_gimple_lcf
, /* properties_provided */
166 0, /* properties_destroyed */
167 0, /* todo_flags_start */
168 TODO_dump_func
, /* todo_flags_finish */
173 /* Lower the EXPR. Unlike gimplification the statements are not relowered
174 when they are changed -- if this has to be done, the lowering routine must
175 do it explicitly. DATA is passed through the recursion. */
178 lower_stmt_body (tree expr
, struct lower_data
*data
)
180 tree_stmt_iterator tsi
;
182 for (tsi
= tsi_start (expr
); !tsi_end_p (tsi
); )
183 lower_stmt (&tsi
, data
);
187 /* Lower the OpenMP directive statement pointed by TSI. DATA is
188 passed through the recursion. */
191 lower_omp_directive (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
195 stmt
= tsi_stmt (*tsi
);
197 lower_stmt_body (OMP_BODY (stmt
), data
);
198 tsi_link_before (tsi
, stmt
, TSI_SAME_STMT
);
199 tsi_link_before (tsi
, OMP_BODY (stmt
), TSI_SAME_STMT
);
200 OMP_BODY (stmt
) = NULL_TREE
;
205 /* Lower statement TSI. DATA is passed through the recursion. */
208 lower_stmt (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
210 tree stmt
= tsi_stmt (*tsi
);
212 if (EXPR_HAS_LOCATION (stmt
) && data
)
213 TREE_BLOCK (stmt
) = data
->block
;
215 switch (TREE_CODE (stmt
))
218 lower_bind_expr (tsi
, data
);
221 lower_cond_expr (tsi
, data
);
224 lower_return_expr (tsi
, data
);
227 case TRY_FINALLY_EXPR
:
229 lower_stmt_body (TREE_OPERAND (stmt
, 0), data
);
230 lower_stmt_body (TREE_OPERAND (stmt
, 1), data
);
233 lower_stmt_body (CATCH_BODY (stmt
), data
);
236 lower_stmt_body (EH_FILTER_FAILURE (stmt
), data
);
244 case CHANGE_DYNAMIC_TYPE_EXPR
:
247 case OMP_SECTIONS_SWITCH
:
257 case GIMPLE_MODIFY_STMT
:
258 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CALL_EXPR
)
259 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
266 tree decl
= get_callee_fndecl (stmt
);
268 && DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
269 && DECL_FUNCTION_CODE (decl
) == BUILT_IN_SETJMP
)
271 data
->calls_builtin_setjmp
= true;
272 lower_builtin_setjmp (tsi
);
279 lower_omp_directive (tsi
, data
);
289 /* Lower a bind_expr TSI. DATA is passed through the recursion. */
292 lower_bind_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
294 tree old_block
= data
->block
;
295 tree stmt
= tsi_stmt (*tsi
);
296 tree new_block
= BIND_EXPR_BLOCK (stmt
);
300 if (new_block
== old_block
)
302 /* The outermost block of the original function may not be the
303 outermost statement chain of the gimplified function. So we
304 may see the outermost block just inside the function. */
305 gcc_assert (new_block
== DECL_INITIAL (current_function_decl
));
310 /* We do not expect to handle duplicate blocks. */
311 gcc_assert (!TREE_ASM_WRITTEN (new_block
));
312 TREE_ASM_WRITTEN (new_block
) = 1;
314 /* Block tree may get clobbered by inlining. Normally this would
315 be fixed in rest_of_decl_compilation using block notes, but
316 since we are not going to emit them, it is up to us. */
317 BLOCK_CHAIN (new_block
) = BLOCK_SUBBLOCKS (old_block
);
318 BLOCK_SUBBLOCKS (old_block
) = new_block
;
319 BLOCK_SUBBLOCKS (new_block
) = NULL_TREE
;
320 BLOCK_SUPERCONTEXT (new_block
) = old_block
;
322 data
->block
= new_block
;
326 record_vars (BIND_EXPR_VARS (stmt
));
327 lower_stmt_body (BIND_EXPR_BODY (stmt
), data
);
331 gcc_assert (data
->block
== new_block
);
333 BLOCK_SUBBLOCKS (new_block
)
334 = blocks_nreverse (BLOCK_SUBBLOCKS (new_block
));
335 data
->block
= old_block
;
338 /* The BIND_EXPR no longer carries any useful information -- kill it. */
339 tsi_link_before (tsi
, BIND_EXPR_BODY (stmt
), TSI_SAME_STMT
);
343 /* Try to determine whether a TRY_CATCH expression can fall through.
344 This is a subroutine of block_may_fallthru. */
347 try_catch_may_fallthru (tree stmt
)
349 tree_stmt_iterator i
;
351 /* If the TRY block can fall through, the whole TRY_CATCH can
353 if (block_may_fallthru (TREE_OPERAND (stmt
, 0)))
356 i
= tsi_start (TREE_OPERAND (stmt
, 1));
357 switch (TREE_CODE (tsi_stmt (i
)))
360 /* We expect to see a sequence of CATCH_EXPR trees, each with a
361 catch expression and a body. The whole TRY_CATCH may fall
362 through iff any of the catch bodies falls through. */
363 for (; !tsi_end_p (i
); tsi_next (&i
))
365 if (block_may_fallthru (CATCH_BODY (tsi_stmt (i
))))
371 /* The exception filter expression only matters if there is an
372 exception. If the exception does not match EH_FILTER_TYPES,
373 we will execute EH_FILTER_FAILURE, and we will fall through
374 if that falls through. If the exception does match
375 EH_FILTER_TYPES, the stack unwinder will continue up the
376 stack, so we will not fall through. We don't know whether we
377 will throw an exception which matches EH_FILTER_TYPES or not,
378 so we just ignore EH_FILTER_TYPES and assume that we might
379 throw an exception which doesn't match. */
380 return block_may_fallthru (EH_FILTER_FAILURE (tsi_stmt (i
)));
383 /* This case represents statements to be executed when an
384 exception occurs. Those statements are implicitly followed
385 by a RESX_EXPR to resume execution after the exception. So
386 in this case the TRY_CATCH never falls through. */
391 /* Try to determine if we can fall out of the bottom of BLOCK. This guess
392 need not be 100% accurate; simply be conservative and return true if we
393 don't know. This is used only to avoid stupidly generating extra code.
394 If we're wrong, we'll just delete the extra code later. */
397 block_may_fallthru (tree block
)
399 tree stmt
= expr_last (block
);
401 switch (stmt
? TREE_CODE (stmt
) : ERROR_MARK
)
406 /* Easy cases. If the last statement of the block implies
407 control transfer, then we can't fall through. */
411 /* If SWITCH_LABELS is set, this is lowered, and represents a
412 branch to a selected label and hence can not fall through.
413 Otherwise SWITCH_BODY is set, and the switch can fall
415 return SWITCH_LABELS (stmt
) == NULL_TREE
;
418 if (block_may_fallthru (COND_EXPR_THEN (stmt
)))
420 return block_may_fallthru (COND_EXPR_ELSE (stmt
));
423 return block_may_fallthru (BIND_EXPR_BODY (stmt
));
426 return try_catch_may_fallthru (stmt
);
428 case TRY_FINALLY_EXPR
:
429 /* The finally clause is always executed after the try clause,
430 so if it does not fall through, then the try-finally will not
431 fall through. Otherwise, if the try clause does not fall
432 through, then when the finally clause falls through it will
433 resume execution wherever the try clause was going. So the
434 whole try-finally will only fall through if both the try
435 clause and the finally clause fall through. */
436 return (block_may_fallthru (TREE_OPERAND (stmt
, 0))
437 && block_may_fallthru (TREE_OPERAND (stmt
, 1)));
439 case GIMPLE_MODIFY_STMT
:
440 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CALL_EXPR
)
441 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
447 /* Functions that do not return do not fall through. */
448 return (call_expr_flags (stmt
) & ECF_NORETURN
) == 0;
450 case CLEANUP_POINT_EXPR
:
451 return block_may_fallthru (TREE_OPERAND (stmt
, 0));
458 /* Lower a cond_expr TSI. DATA is passed through the recursion. */
461 lower_cond_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
463 tree stmt
= tsi_stmt (*tsi
);
464 bool then_is_goto
, else_is_goto
;
465 tree then_branch
, else_branch
;
466 tree then_goto
, else_goto
;
468 then_branch
= COND_EXPR_THEN (stmt
);
469 else_branch
= COND_EXPR_ELSE (stmt
);
471 lower_stmt_body (then_branch
, data
);
472 lower_stmt_body (else_branch
, data
);
474 then_goto
= expr_only (then_branch
);
475 then_is_goto
= then_goto
&& simple_goto_p (then_goto
);
477 else_goto
= expr_only (else_branch
);
478 else_is_goto
= else_goto
&& simple_goto_p (else_goto
);
480 if (!then_is_goto
|| !else_is_goto
)
482 tree then_label
, else_label
, end_label
, t
;
484 then_label
= NULL_TREE
;
485 else_label
= NULL_TREE
;
486 end_label
= NULL_TREE
;
488 /* Replace the cond_expr with explicit gotos. */
491 t
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
492 if (TREE_SIDE_EFFECTS (then_branch
))
496 then_goto
= build_and_jump (&LABEL_EXPR_LABEL (t
));
501 t
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
502 if (TREE_SIDE_EFFECTS (else_branch
))
506 /* Both THEN and ELSE can be no-ops if one or both contained an
507 empty BIND_EXPR that was associated with the toplevel block
508 of an inlined function. In that case remove_useless_stmts
509 can't have cleaned things up for us; kill the whole
519 else_goto
= build_and_jump (&LABEL_EXPR_LABEL (t
));
524 bool may_fallthru
= block_may_fallthru (then_branch
);
526 tsi_link_after (tsi
, then_label
, TSI_CONTINUE_LINKING
);
527 tsi_link_after (tsi
, then_branch
, TSI_CONTINUE_LINKING
);
529 if (else_label
&& may_fallthru
)
531 end_label
= build1 (LABEL_EXPR
, void_type_node
, NULL_TREE
);
532 t
= build_and_jump (&LABEL_EXPR_LABEL (end_label
));
533 tsi_link_after (tsi
, t
, TSI_CONTINUE_LINKING
);
539 tsi_link_after (tsi
, else_label
, TSI_CONTINUE_LINKING
);
540 tsi_link_after (tsi
, else_branch
, TSI_CONTINUE_LINKING
);
544 tsi_link_after (tsi
, end_label
, TSI_CONTINUE_LINKING
);
547 COND_EXPR_THEN (stmt
) = then_goto
;
548 COND_EXPR_ELSE (stmt
) = else_goto
;
553 /* Lower a return_expr TSI. DATA is passed through the recursion. */
556 lower_return_expr (tree_stmt_iterator
*tsi
, struct lower_data
*data
)
558 tree stmt
= tsi_stmt (*tsi
);
559 tree value
, t
, label
;
561 /* Extract the value being returned. */
562 value
= TREE_OPERAND (stmt
, 0);
563 if (value
&& TREE_CODE (value
) == GIMPLE_MODIFY_STMT
)
564 value
= GIMPLE_STMT_OPERAND (value
, 1);
566 /* Match this up with an existing return statement that's been created. */
567 for (t
= data
->return_statements
; t
; t
= TREE_CHAIN (t
))
569 tree tvalue
= TREE_OPERAND (TREE_VALUE (t
), 0);
570 if (tvalue
&& TREE_CODE (tvalue
) == GIMPLE_MODIFY_STMT
)
571 tvalue
= GIMPLE_STMT_OPERAND (tvalue
, 1);
575 label
= TREE_PURPOSE (t
);
580 /* Not found. Create a new label and record the return statement. */
581 label
= create_artificial_label ();
582 data
->return_statements
= tree_cons (label
, stmt
, data
->return_statements
);
584 /* Generate a goto statement and remove the return statement. */
586 t
= build1 (GOTO_EXPR
, void_type_node
, label
);
587 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
588 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
592 /* Lower a __builtin_setjmp TSI.
594 __builtin_setjmp is passed a pointer to an array of five words (not
595 all will be used on all machines). It operates similarly to the C
596 library function of the same name, but is more efficient.
598 It is lowered into 3 other builtins, namely __builtin_setjmp_setup,
599 __builtin_setjmp_dispatcher and __builtin_setjmp_receiver, but with
600 __builtin_setjmp_dispatcher shared among all the instances; that's
601 why it is only emitted at the end by lower_function_body.
603 After full lowering, the body of the function should look like:
612 __builtin_setjmp_setup (&buf, &<D1847>);
616 __builtin_setjmp_receiver (&<D1847>);
619 if (D.1844 == 0) goto <D1848>; else goto <D1849>;
623 __builtin_setjmp_setup (&buf, &<D2847>);
627 __builtin_setjmp_receiver (&<D2847>);
630 if (D.2844 == 0) goto <D2848>; else goto <D2849>;
636 <D3853>: [non-local];
637 setjmpvar.0 = __builtin_setjmp_dispatcher (&<D3853>);
641 The dispatcher block will be both the unique destination of all the
642 abnormal call edges and the unique source of all the abnormal edges
643 to the receivers, thus keeping the complexity explosion localized. */
646 lower_builtin_setjmp (tree_stmt_iterator
*tsi
)
648 tree stmt
= tsi_stmt (*tsi
);
649 tree cont_label
= create_artificial_label ();
650 tree next_label
= create_artificial_label ();
653 /* NEXT_LABEL is the label __builtin_longjmp will jump to. Its address is
654 passed to both __builtin_setjmp_setup and __builtin_setjmp_receiver. */
655 FORCED_LABEL (next_label
) = 1;
657 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
659 dest
= GIMPLE_STMT_OPERAND (stmt
, 0);
660 stmt
= GIMPLE_STMT_OPERAND (stmt
, 1);
665 /* Build '__builtin_setjmp_setup (BUF, NEXT_LABEL)' and insert. */
666 arg
= build_addr (next_label
, current_function_decl
);
667 t
= implicit_built_in_decls
[BUILT_IN_SETJMP_SETUP
];
668 t
= build_call_expr (t
, 2, CALL_EXPR_ARG (stmt
, 0), arg
);
669 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
670 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
672 /* Build 'DEST = 0' and insert. */
675 t
= build_gimple_modify_stmt (dest
, fold_convert (TREE_TYPE (dest
),
677 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
678 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
681 /* Build 'goto CONT_LABEL' and insert. */
682 t
= build1 (GOTO_EXPR
, void_type_node
, cont_label
);
683 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
685 /* Build 'NEXT_LABEL:' and insert. */
686 t
= build1 (LABEL_EXPR
, void_type_node
, next_label
);
687 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
689 /* Build '__builtin_setjmp_receiver (NEXT_LABEL)' and insert. */
690 arg
= build_addr (next_label
, current_function_decl
);
691 t
= implicit_built_in_decls
[BUILT_IN_SETJMP_RECEIVER
];
692 t
= build_call_expr (t
, 1, arg
);
693 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
694 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
696 /* Build 'DEST = 1' and insert. */
699 t
= build_gimple_modify_stmt (dest
, fold_convert (TREE_TYPE (dest
),
701 SET_EXPR_LOCUS (t
, EXPR_LOCUS (stmt
));
702 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
705 /* Build 'CONT_LABEL:' and insert. */
706 t
= build1 (LABEL_EXPR
, void_type_node
, cont_label
);
707 tsi_link_before (tsi
, t
, TSI_SAME_STMT
);
709 /* Remove the call to __builtin_setjmp. */
714 /* Record the variables in VARS into function FN. */
717 record_vars_into (tree vars
, tree fn
)
719 struct function
*saved_cfun
= cfun
;
721 if (fn
!= current_function_decl
)
722 cfun
= DECL_STRUCT_FUNCTION (fn
);
724 for (; vars
; vars
= TREE_CHAIN (vars
))
728 /* BIND_EXPRs contains also function/type/constant declarations
729 we don't need to care about. */
730 if (TREE_CODE (var
) != VAR_DECL
)
733 /* Nothing to do in this case. */
734 if (DECL_EXTERNAL (var
))
737 /* Record the variable. */
738 cfun
->unexpanded_var_list
= tree_cons (NULL_TREE
, var
,
739 cfun
->unexpanded_var_list
);
742 if (fn
!= current_function_decl
)
747 /* Record the variables in VARS into current_function_decl. */
750 record_vars (tree vars
)
752 record_vars_into (vars
, current_function_decl
);
756 /* Mark BLOCK used if it has a used variable in it, then recurse over its
760 mark_blocks_with_used_vars (tree block
)
765 if (!TREE_USED (block
))
767 for (var
= BLOCK_VARS (block
);
769 var
= TREE_CHAIN (var
))
773 TREE_USED (block
) = true;
778 for (subblock
= BLOCK_SUBBLOCKS (block
);
780 subblock
= BLOCK_CHAIN (subblock
))
781 mark_blocks_with_used_vars (subblock
);
784 /* Mark the used attribute on blocks correctly. */
787 mark_used_blocks (void)
789 mark_blocks_with_used_vars (DECL_INITIAL (current_function_decl
));
794 struct tree_opt_pass pass_mark_used_blocks
=
798 mark_used_blocks
, /* execute */
801 0, /* static_pass_number */
803 0, /* properties_required */
804 0, /* properties_provided */
805 0, /* properties_destroyed */
806 0, /* todo_flags_start */
807 TODO_dump_func
, /* todo_flags_finish */