1 /* Tree lowering pass. This pass gimplifies the tree representation built
2 by the C-based front ends. The structure of gimplified, or
3 language-independent, trees is dictated by the grammar described in this
5 Copyright (C) 2002, 2003 Free Software Foundation, Inc.
6 Lowering of expressions contributed by Sebastian Pop <s.pop@laposte.net>
7 Re-written to support lowering of whole function trees, documentation
8 and miscellaneous cleanups by Diego Novillo <dnovillo@redhat.com>
10 This file is part of GCC.
12 GCC is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free
14 Software Foundation; either version 2, or (at your option) any later
17 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
18 WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 You should have received a copy of the GNU General Public License
23 along with GCC; see the file COPYING. If not, write to the Free
24 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
29 #include "coretypes.h"
36 #include "tree-gimple.h"
37 #include "hard-reg-set.h"
38 #include "basic-block.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
41 #include "diagnostic.h"
42 #include "langhooks.h"
43 #include "langhooks-def.h"
47 #include "tree-dump.h"
48 #include "c-pretty-print.h"
52 /* The gimplification pass converts the language-dependent trees
53 (ld-trees) emitted by the parser into language-independent trees
54 (li-trees) that are the target of SSA analysis and transformations.
56 Language-independent trees are based on the SIMPLE intermediate
57 representation used in the McCAT compiler framework:
59 "Designing the McCAT Compiler Based on a Family of Structured
60 Intermediate Representations,"
61 L. Hendren, C. Donawa, M. Emami, G. Gao, Justiani, and B. Sridharan,
62 Proceedings of the 5th International Workshop on Languages and
63 Compilers for Parallel Computing, no. 757 in Lecture Notes in
64 Computer Science, New Haven, Connecticut, pp. 406-420,
65 Springer-Verlag, August 3-5, 1992.
67 http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
69 Basically, we walk down gimplifying the nodes that we encounter. As we
70 walk back up, we check that they fit our constraints, and copy them
71 into temporaries if not. */
73 /* Local declarations. */
75 static enum gimplify_status gimplify_expr_stmt (tree *);
76 static enum gimplify_status gimplify_decl_stmt (tree *);
77 static enum gimplify_status gimplify_for_stmt (tree *, tree *);
78 static enum gimplify_status gimplify_while_stmt (tree *);
79 static enum gimplify_status gimplify_do_stmt (tree *);
80 static enum gimplify_status gimplify_if_stmt (tree *);
81 static enum gimplify_status gimplify_switch_stmt (tree *);
82 static enum gimplify_status gimplify_return_stmt (tree *);
83 static enum gimplify_status gimplify_compound_literal_expr (tree *);
84 static void gimplify_cleanup_stmts (tree);
85 static tree gimplify_c_loop (tree, tree, tree, bool);
86 static void push_context (void);
87 static void pop_context (void);
88 static void add_block_to_enclosing (tree);
89 static void gimplify_condition (tree *);
91 enum bc_t { bc_break = 0, bc_continue = 1 };
92 static tree begin_bc_block (enum bc_t);
93 static tree finish_bc_block (tree, tree);
94 static tree build_bc_goto (enum bc_t);
96 static struct c_gimplify_ctx
98 /* For handling break and continue. */
99 tree current_bc_label;
108 ctxp = (struct c_gimplify_ctx *) xcalloc (1, sizeof (struct c_gimplify_ctx));
109 ctxp->bc_id[bc_continue] = get_identifier ("continue");
110 ctxp->bc_id[bc_break] = get_identifier ("break");
116 if (!ctxp || ctxp->current_bc_label)
122 /* Gimplification of statement trees. */
124 /* Convert the tree representation of FNDECL from C frontend trees to
128 c_genericize (tree fndecl)
131 int local_dump_flags;
132 struct cgraph_node *cgn;
134 /* Dump the C-specific tree IR. */
135 dump_file = dump_begin (TDI_original, &local_dump_flags);
138 fprintf (dump_file, "\n;; Function %s",
139 lang_hooks.decl_printable_name (fndecl, 2));
140 fprintf (dump_file, " (%s)\n",
141 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)));
142 fprintf (dump_file, ";; enabled by -%s\n", dump_flag_name (TDI_original));
143 fprintf (dump_file, "\n");
145 if (local_dump_flags & TDF_RAW)
146 dump_node (DECL_SAVED_TREE (fndecl),
147 TDF_SLIM | local_dump_flags, dump_file);
149 print_c_tree (dump_file, DECL_SAVED_TREE (fndecl));
150 fprintf (dump_file, "\n");
152 dump_end (TDI_original, dump_file);
155 /* Go ahead and gimplify for now. */
157 gimplify_cleanup_stmts (fndecl);
158 gimplify_function_tree (fndecl);
161 /* Dump the genericized tree IR. */
162 dump_function (TDI_generic, fndecl);
164 /* Genericize all nested functions now. We do things in this order so
165 that items like VLA sizes are expanded properly in the context of
166 the correct function. */
167 cgn = cgraph_node (fndecl);
168 for (cgn = cgn->nested; cgn ; cgn = cgn->next_nested)
169 c_genericize (cgn->decl);
172 /* Genericize a CLEANUP_STMT. This just turns into a TRY_FINALLY or
173 TRY_CATCH depending on whether it's EH-only. */
176 gimplify_cleanup_stmt (tree *stmt_p, int *walk_subtrees,
177 void *data ATTRIBUTE_UNUSED)
181 if (DECL_P (stmt) || TYPE_P (stmt))
183 else if (TREE_CODE (stmt) == CLEANUP_STMT)
184 *stmt_p = build (CLEANUP_EH_ONLY (stmt) ? TRY_CATCH_EXPR : TRY_FINALLY_EXPR,
185 void_type_node, CLEANUP_BODY (stmt), CLEANUP_EXPR (stmt));
191 gimplify_cleanup_stmts (tree fndecl)
193 walk_tree (&DECL_SAVED_TREE (fndecl), gimplify_cleanup_stmt, NULL, NULL);
196 /* Entry point for the tree lowering pass. Recursively scan
197 *STMT_P and convert it to a GIMPLE tree. */
200 c_gimplify_stmt (tree *stmt_p)
204 int saved_stmts_are_full_exprs_p;
205 location_t stmt_locus;
206 enum gimplify_status ret;
208 /* PRE and POST are tree chains that contain the side-effects of the
209 gimplified tree. For instance, given the expression tree:
213 After gimplification, the tree will be re-written as:
218 b = b + 1; <-- POST */
220 /* Set up context appropriately for handling this statement. */
221 saved_stmts_are_full_exprs_p = stmts_are_full_exprs_p ();
223 stmt_locus = input_location;
228 switch (TREE_CODE (stmt))
231 stmt = COMPOUND_BODY (stmt);
236 ret = gimplify_for_stmt (&stmt, &pre);
240 ret = gimplify_while_stmt (&stmt);
244 ret = gimplify_do_stmt (&stmt);
248 ret = gimplify_if_stmt (&stmt);
252 ret = gimplify_switch_stmt (&stmt);
256 ret = gimplify_expr_stmt (&stmt);
260 ret = gimplify_return_stmt (&stmt);
264 ret = gimplify_decl_stmt (&stmt);
268 stmt = build_bc_goto (bc_continue);
273 stmt = build_bc_goto (bc_break);
278 if (lang_gimplify_stmt && (*lang_gimplify_stmt) (&stmt))
284 fprintf (stderr, "unhandled statement node in c_gimplify_stmt:\n");
295 gimplify_stmt (&stmt);
303 /* PRE and POST now contain a list of statements for all the
304 side-effects in STMT. */
306 append_to_statement_list (stmt, &pre);
307 append_to_statement_list (post, &pre);
308 annotate_all_with_locus (&pre, stmt_locus);
310 /* Restore saved state. */
311 current_stmt_tree ()->stmts_are_full_exprs_p = saved_stmts_are_full_exprs_p;
318 add_block_to_enclosing (tree block)
322 for (enclosing = gimple_current_bind_expr ();
323 enclosing; enclosing = TREE_CHAIN (enclosing))
324 if (BIND_EXPR_BLOCK (enclosing))
327 enclosing = BIND_EXPR_BLOCK (enclosing);
328 BLOCK_SUBBLOCKS (enclosing) = chainon (BLOCK_SUBBLOCKS (enclosing), block);
331 /* Genericize a scope by creating a new BIND_EXPR.
332 BLOCK is either a BLOCK representing the scope or a chain of _DECLs.
333 In the latter case, we need to create a new BLOCK and add it to the
334 BLOCK_SUBBLOCKS of the enclosing block.
335 BODY is a chain of C _STMT nodes for the contents of the scope, to be
339 c_build_bind_expr (tree block, tree body)
343 if (block == NULL_TREE)
345 else if (TREE_CODE (block) == BLOCK)
346 decls = BLOCK_VARS (block);
350 if (DECL_ARTIFICIAL (decls))
354 block = make_node (BLOCK);
355 BLOCK_VARS (block) = decls;
356 add_block_to_enclosing (block);
361 body = build_empty_stmt ();
364 bind = build (BIND_EXPR, void_type_node, decls, body, block);
365 TREE_SIDE_EFFECTS (bind) = 1;
373 /* Gimplify an EXPR_STMT node.
375 STMT is the statement node.
377 PRE_P points to the list where side effects that must happen before
378 STMT should be stored.
380 POST_P points to the list where side effects that must happen after
381 STMT should be stored. */
383 static enum gimplify_status
384 gimplify_expr_stmt (tree *stmt_p)
386 tree stmt = EXPR_STMT_EXPR (*stmt_p);
388 if (stmt == error_mark_node)
391 /* Gimplification of a statement expression will nullify the
392 statement if all its side effects are moved to *PRE_P and *POST_P.
394 In this case we will not want to emit the gimplified statement.
395 However, we may still want to emit a warning, so we do that before
397 if (stmt && (extra_warnings || warn_unused_value))
399 if (!TREE_SIDE_EFFECTS (stmt))
401 if (!IS_EMPTY_STMT (stmt)
402 && !VOID_TYPE_P (TREE_TYPE (stmt))
403 && !TREE_NO_WARNING (stmt))
404 warning ("statement with no effect");
406 else if (warn_unused_value)
408 /* Kludge for 20020220-2.c. warn_if_unused_value shouldn't use
409 the stmt file location info. */
410 set_file_and_line_for_stmt (input_location);
411 warn_if_unused_value (stmt);
415 if (stmt == NULL_TREE)
416 stmt = build_empty_stmt ();
417 else if (stmts_are_full_exprs_p ())
418 stmt = build1 (CLEANUP_POINT_EXPR, void_type_node, stmt);
425 /* If the condition for a loop (or the like) is a decl, it will be a
426 TREE_LIST where the TREE_PURPOSE is a DECL_STMT and the TREE_VALUE is
427 a use of the decl. Turn such a thing into a COMPOUND_EXPR. */
430 gimplify_condition (tree *cond_p)
433 if (cond && TREE_CODE (cond) == TREE_LIST)
435 tree decl = TREE_PURPOSE (cond);
436 tree value = TREE_VALUE (cond);
437 gimplify_stmt (&decl);
438 *cond_p = build (COMPOUND_EXPR, TREE_TYPE (value), decl, value);
442 /* Begin a scope which can be exited by a break or continue statement. BC
445 Just creates a label and pushes it into the current context. */
448 begin_bc_block (enum bc_t bc)
450 tree label = create_artificial_label ();
451 DECL_NAME (label) = ctxp->bc_id[bc];
452 TREE_CHAIN (label) = ctxp->current_bc_label;
453 ctxp->current_bc_label = label;
457 /* Finish a scope which can be exited by a break or continue statement.
458 LABEL was returned from the most recent call to begin_bc_block. BODY is
459 an expression for the contents of the scope.
461 If we saw a break (or continue) in the scope, append a LABEL_EXPR to
462 body. Otherwise, just forget the label. */
465 finish_bc_block (tree label, tree body)
467 if (label != ctxp->current_bc_label)
470 if (TREE_USED (label))
474 /* Clear the name so flow can delete the label. */
475 DECL_NAME (label) = NULL_TREE;
476 t = build1 (LABEL_EXPR, void_type_node, label);
478 append_to_statement_list (body, &sl);
479 append_to_statement_list (t, &sl);
483 ctxp->current_bc_label = TREE_CHAIN (label);
484 TREE_CHAIN (label) = NULL_TREE;
488 /* Build a GOTO_EXPR to represent a break or continue statement. BC
492 build_bc_goto (enum bc_t bc)
495 tree target_name = ctxp->bc_id[bc];
497 /* Look for the appropriate type of label. */
498 for (label = ctxp->current_bc_label;
500 label = TREE_CHAIN (label))
501 if (DECL_NAME (label) == target_name)
504 if (label == NULL_TREE)
507 error ("break statement not within loop or switch");
509 error ("continue statement not within loop or switch");
514 /* Mark the label used for finish_bc_block. */
515 TREE_USED (label) = 1;
516 return build1 (GOTO_EXPR, void_type_node, label);
519 /* Build a generic representation of one of the C loop forms. COND is the
520 loop condition or NULL_TREE. BODY is the (possibly compound) statement
521 controlled by the loop. INCR is the increment expression of a for-loop,
522 or NULL_TREE. COND_IS_FIRST indicates whether the condition is
523 evaluated before the loop body as in while and for loops, or after the
524 loop body as in do-while loops. */
527 gimplify_c_loop (tree cond, tree body, tree incr, bool cond_is_first)
529 tree top, entry, exit, cont_block, break_block, stmt_list, t;
530 location_t stmt_locus;
532 stmt_locus = input_location;
534 /* Detect do { ... } while (0) and don't generate loop construct. */
535 if (!cond_is_first && cond && integer_zerop (cond))
539 /* If we use a LOOP_EXPR here, we have to feed the whole thing
540 back through the main gimplifier to lower it. Given that we
541 have to gimplify the loop body NOW so that we can resolve
542 break/continue stmts, seems easier to just expand to gotos. */
543 top = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
546 break_block = begin_bc_block (bc_break);
550 /* If we have an exit condition, then we build an IF with gotos either
551 out of the loop, or to the top of it. If there's no exit condition,
552 then we just build a jump back to the top. */
553 exit = build_and_jump (&LABEL_EXPR_LABEL (top));
556 gimplify_condition (&cond);
557 t = build_bc_goto (bc_break);
558 exit = build (COND_EXPR, void_type_node, cond, exit, t);
560 gimplify_stmt (&exit);
566 cont_block = begin_bc_block (bc_continue);
568 gimplify_stmt (&body);
569 if (incr && stmts_are_full_exprs_p ())
570 incr = fold (build1 (CLEANUP_POINT_EXPR, void_type_node, incr));
571 gimplify_stmt (&incr);
573 body = finish_bc_block (cont_block, body);
577 if (cond_is_first && cond)
579 entry = build1 (LABEL_EXPR, void_type_node, NULL_TREE);
580 t = build_and_jump (&LABEL_EXPR_LABEL (entry));
581 append_to_statement_list (t, &stmt_list);
586 append_to_statement_list (top, &stmt_list);
587 append_to_statement_list (body, &stmt_list);
588 append_to_statement_list (incr, &stmt_list);
589 append_to_statement_list (entry, &stmt_list);
590 append_to_statement_list (exit, &stmt_list);
592 annotate_all_with_locus (&stmt_list, stmt_locus);
594 return finish_bc_block (break_block, stmt_list);
597 /* Gimplify a FOR_STMT node. Move the stuff in the for-init-stmt into the
598 prequeue and hand off to gimplify_c_loop. */
600 static enum gimplify_status
601 gimplify_for_stmt (tree *stmt_p, tree *pre_p)
605 if (FOR_INIT_STMT (stmt))
607 gimplify_stmt (&FOR_INIT_STMT (stmt));
608 append_to_statement_list (FOR_INIT_STMT (stmt), pre_p);
610 *stmt_p = gimplify_c_loop (FOR_COND (stmt), FOR_BODY (stmt),
616 /* Gimplify a WHILE_STMT node. */
618 static enum gimplify_status
619 gimplify_while_stmt (tree *stmt_p)
622 *stmt_p = gimplify_c_loop (WHILE_COND (stmt), WHILE_BODY (stmt),
627 /* Gimplify a DO_STMT node. */
629 static enum gimplify_status
630 gimplify_do_stmt (tree *stmt_p)
633 *stmt_p = gimplify_c_loop (DO_COND (stmt), DO_BODY (stmt),
638 /* Genericize an IF_STMT by turning it into a COND_EXPR. */
640 static enum gimplify_status
641 gimplify_if_stmt (tree *stmt_p)
643 tree stmt, then_, else_;
646 then_ = THEN_CLAUSE (stmt);
647 else_ = ELSE_CLAUSE (stmt);
650 then_ = build_empty_stmt ();
652 else_ = build_empty_stmt ();
654 stmt = build (COND_EXPR, void_type_node, IF_COND (stmt), then_, else_);
655 gimplify_condition (& TREE_OPERAND (stmt, 0));
661 /* Genericize a SWITCH_STMT by turning it into a SWITCH_EXPR. */
663 static enum gimplify_status
664 gimplify_switch_stmt (tree *stmt_p)
667 tree break_block, body;
668 location_t stmt_locus = input_location;
670 break_block = begin_bc_block (bc_break);
672 gimplify_condition (&SWITCH_COND (stmt));
674 body = SWITCH_BODY (stmt);
676 body = build_empty_stmt ();
678 *stmt_p = build (SWITCH_EXPR, SWITCH_TYPE (stmt), SWITCH_COND (stmt),
680 annotate_with_locus (*stmt_p, stmt_locus);
681 gimplify_stmt (stmt_p);
683 *stmt_p = finish_bc_block (break_block, *stmt_p);
687 /* Genericize a RETURN_STMT by turning it into a RETURN_EXPR. */
689 static enum gimplify_status
690 gimplify_return_stmt (tree *stmt_p)
692 tree expr = RETURN_STMT_EXPR (*stmt_p);
693 expr = build1 (RETURN_EXPR, void_type_node, expr);
694 if (stmts_are_full_exprs_p ())
695 expr = build1 (CLEANUP_POINT_EXPR, void_type_node, expr);
700 /* Gimplifies a DECL_STMT node *STMT_P by making any necessary allocation
701 and initialization explicit. */
703 static enum gimplify_status
704 gimplify_decl_stmt (tree *stmt_p)
707 tree decl = DECL_STMT_DECL (stmt);
708 tree pre = NULL_TREE;
709 tree post = NULL_TREE;
711 if (TREE_TYPE (decl) == error_mark_node)
717 if (TREE_CODE (decl) == TYPE_DECL)
719 tree type = TREE_TYPE (decl);
720 if (TYPE_SIZE_UNIT (type)
721 && !TREE_CONSTANT (TYPE_SIZE_UNIT (type)))
723 /* This is a variable-sized array type. Simplify its size. */
724 tree temp = TYPE_SIZE_UNIT (type);
725 gimplify_expr (&temp, &pre, &post, is_gimple_val, fb_rvalue);
729 if (TREE_CODE (decl) == VAR_DECL && !DECL_EXTERNAL (decl))
731 tree init = DECL_INITIAL (decl);
733 if (!TREE_CONSTANT (DECL_SIZE (decl)))
735 tree pt_type = build_pointer_type (TREE_TYPE (decl));
738 /* This is a variable-sized decl. Simplify its size and mark it
739 for deferred expansion. Note that mudflap depends on the format
740 of the emitted code: see mx_register_decls(). */
742 size = get_initialized_tmp_var (DECL_SIZE_UNIT (decl), &pre, &post);
743 DECL_DEFER_OUTPUT (decl) = 1;
744 alloc = build_function_call_expr
745 (implicit_built_in_decls[BUILT_IN_STACK_ALLOC],
746 tree_cons (NULL_TREE,
747 build1 (ADDR_EXPR, pt_type, decl),
748 tree_cons (NULL_TREE, size, NULL_TREE)));
749 append_to_compound_expr (alloc, &pre);
752 if (init && init != error_mark_node)
754 if (!TREE_STATIC (decl))
756 /* Do not warn about int x = x; as it is a GCC extension
757 to turn off this warning but only if warn_init_self
759 if (init == decl && !warn_init_self)
760 TREE_NO_WARNING (decl) = 1;
762 DECL_INITIAL (decl) = NULL_TREE;
763 init = build (MODIFY_EXPR, void_type_node, decl, init);
764 if (stmts_are_full_exprs_p ())
765 init = build1 (CLEANUP_POINT_EXPR, void_type_node, init);
766 append_to_compound_expr (init, &pre);
770 /* We must still examine initializers for static variables
771 as they may contain a label address. */
772 walk_tree (&init, force_labels_r, NULL, NULL);
776 /* This decl isn't mentioned in the enclosing block, so add it to the
777 list of temps. FIXME it seems a bit of a kludge to say that
778 anonymous artificial vars aren't pushed, but everything else is. */
779 if (DECL_ARTIFICIAL (decl) && DECL_NAME (decl) == NULL_TREE)
780 gimple_add_tmp_var (decl);
783 append_to_compound_expr (post, &pre);
788 /* Gimplification of expression trees. */
790 /* Gimplify a C99 compound literal expression. This just means adding the
791 DECL_STMT before the current EXPR_STMT and using its anonymous decl
794 static enum gimplify_status
795 gimplify_compound_literal_expr (tree *expr_p)
797 tree decl_s = COMPOUND_LITERAL_EXPR_DECL_STMT (*expr_p);
798 tree decl = DECL_STMT_DECL (decl_s);
800 /* This decl isn't mentioned in the enclosing block, so add it to the
801 list of temps. FIXME it seems a bit of a kludge to say that
802 anonymous artificial vars aren't pushed, but everything else is. */
803 if (DECL_NAME (decl) == NULL_TREE)
804 gimple_add_tmp_var (decl);
806 gimplify_decl_stmt (&decl_s);
807 *expr_p = decl_s ? decl_s : decl;
811 /* Do C-specific gimplification. Args are as for gimplify_expr. */
814 c_gimplify_expr (tree *expr_p, tree *pre_p ATTRIBUTE_UNUSED,
815 tree *post_p ATTRIBUTE_UNUSED)
817 enum tree_code code = TREE_CODE (*expr_p);
819 if (STATEMENT_CODE_P (code))
820 return c_gimplify_stmt (expr_p);
824 case COMPOUND_LITERAL_EXPR:
825 return gimplify_compound_literal_expr (expr_p);